Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove relation between generators and automorphisms of Z/nZ*

  1. Jun 5, 2015 #1
    Hi,

    I was wondering if anyone here could help me prove or disprove this empirical observation or explain why there seems to be a connection between automorphic generators described below and the automorphisms of these groups:

    Consider the p-group expansion:
    ##\mathbb{Z}_n^*\cong S_2\times S_{p_2}\times\cdots\times S_{p_n}##.

    Now define an automorphic generator ##G=\big<a_1,a_2,\cdots,a_n\big>## of ##\mathbb{Z}_n^*## as a generator meeting the following requirements:
    ## \displaystyle\bigcap^n \big<a_i\big> =\{1\}\quad \text{and} \quad \displaystyle \prod^n \big<a_i\big> =\mathbb{Z}_n^*
    ##
    and consider the set ##A=\{\big<b_1,b_2,\cdots,b_n\big>\}## of all automorphic generators in which the generator elements match the orders of the elements of ##G##, that is ##o(a_1)=o(b_1)##, ##o(a_2)=o(b_2)## and so forth. Show or provide a contradiction:
    ##\begin{aligned}(1)\quad &\big|\operatorname{aut}\mathbb{Z}_n^*\big|=\big|A\big|,\\
    (2)\quad &\operatorname{aut}\mathbb{Z}_n^*=\big<G,A\big>,\\
    (3)\quad &\text{min}|G|=|S_2|
    \end{aligned}
    ##
    where we interpret ##\big<G,A\big>## as meaning any mapping of a generator ##G## to a set of generator mappings ##A##, and the expression ##\text{min}|G|=|S_2|## reflects the empirical observation that the minimum number of elements of an automorphic generator appears to be equal to the number of factors of ##S_2##.

    Ok thanks,
    Jack
     
    Last edited: Jun 5, 2015
  2. jcsd
  3. Jun 6, 2015 #2
    I'm afraid I have to change this hypothesis a bit and can't edit the first post:

    Consider the p-group expansion:
    ##\mathbb{Z}_n^*\cong S_2\times S_{p_2}\times\cdots\times S_{p_n}##.

    Now define an automorphic generator ##G=\big<a_1,a_2,\cdots,a_n\big>## of ##\mathbb{Z}_n^*## with ## a_i\neq a_j## as a generator meeting the following requirements:

    ## \displaystyle\prod\limits^n \big|\big<a_i\big>\big|=\big|\mathbb{Z}_n^*\big|,\quad\displaystyle\bigcap\limits_{n} \big<a_i\big>=\{1\}\quad \text{and} \quad \displaystyle\prod\limits^n \big<a_i\big>=\mathbb{Z}_n^*
    ##

    and consider the set ##A=\{\big<b_1,b_2,\cdots,b_n\big>\}## of all automorphic generators in which the generator elements match the orders of the elements of ##G##, that is ##o(a_1)=o(b_1)##, ##o(a_2)=o(b_2)## and so forth. Show or provide a contradiction:
    ##\begin{aligned}(1)\quad &\big|\operatorname{aut}\mathbb{Z}_n^*\big|=\big|A\big|,\\
    (2)\quad &\operatorname{aut}\mathbb{Z}_n^*=\big<G,A\big>,\\
    (3)\quad &\text{min}|G|=|S_2| \quad \text{for}~n>2
    \end{aligned}
    ##
    where we interpret ##\big<G,A\big>## as meaning any mapping of a generator ##G## to a set of generator mappings ##A##, and the expression ##\text{min}|G|=|S_2|## reflects the empirical observation that the minimum number of elements of an automorphic generator appears to be equal to the number of factors of ##S_2##.

    For example, consider ##\mathbb{Z}_{24}^*## with all elements of order 2 except the identity element. Since the group size is 8, 3 generator elements are required to generate the group. However there are some 3-tuples (a,b,c) which meet the first two requirements of automorphic generators but not the third. Of these tuples, 168 meet all three requirements and lead to the creation of the automorphic set.
     
    Last edited by a moderator: Jun 7, 2015
  4. Jun 8, 2015 #3
    I have no choice but to risk looking foolish by changing this again:

    Consider the isomorphic relation between a multiplicative integer mod group and it's (non-trivial) additive group factors:
    ##\mathbb{Z}_n^*\cong \mathbb{Z}_{x_1}\times \mathbb{Z}_{x_2}\times\cdots\times \mathbb{Z}_{x_k}##
    for ## n>2## where I have explicitly not factored the group into p-groups. For example:
    ##\begin{aligned} \mathbb{Z}_{129}^*&\cong \mathbb{Z}_{3}^*\times\mathbb{Z}_{43}^* \\
    &\cong \mathbb{Z}_2\times \mathbb{Z}_{42} \\
    \end{aligned}
    ##

    Now, since these are isomorphic, they are actually the same group and since the additive group obviously has elements of orders ##2## and ##42##, that is, elements (1,0) and (0,1) respectively, then both the additive group ##H=\mathbb{Z}_2\times\mathbb{Z}_{42}## and the multiplicative group ##\mathbb{Z}_{129}^*## are generated by elements with these orders and so ##\mathbb{Z}_{n}^*## will always have elements in which the product of the orders of the elements is equal to the size of the group and that the number of such additive factors must be the minimum size of the generator needed to generate ##\mathbb{Z}_n^*##.

    That is, given ##\mathbb{Z}_n^*\cong \mathbb{Z}_{x_1}\times \mathbb{Z}_{x_2}\times\cdots\times \mathbb{Z}_{x_k}## there exists ##(a_1,a_2,\cdots,a_k)\in \mathbb{Z}_{n}^*## such that ##o(a_1)=x_1, o(a_2)=x_2,\cdots o(a_k)=x_k## and ##\mathbb{Z}_n^*=\big<a_1,a_2\cdots,a_k\big>## and so obviously, ##\displaystyle\mathop\prod\limits^k o(a_i)=\big|\mathbb{Z}_n^*\big|##. I didn't realize this until now as well as if the product of the orders is equal to the size of the group and the intersection of the orbits is ##\{1\}##, then obviously the generator generates the group without duplication (is exactly equal to it) so I wish to modify my hypothesis:


    Consider the additive group expansion:

    ##\mathbb{Z}_n^*\cong \mathbb{Z}_{x_1}\times\mathbb{Z}_{x_2} \cdots\times\ \mathbb{Z}_{x_k}## for ##n>2##.

    Then ##\mathbb{Z}_n^*## has elements with orders ##x_1, x_2,\cdots,x_k##.

    Now define an automorphic generator ##G=\big<a_1,a_2,\cdots,a_k\big>## of ##\mathbb{Z}_n^*## with ##o(a_1)=x_1,o(a_2)=x_2,\cdots o(a_k)=a_k## with ##a_i\neq a_j## and meeting the following requirement:

    ## \quad\displaystyle\bigcap\limits_{n} \big<a_i\big>=\{1\}##.

    Let ##A=\{g_i : g_i\; \text{is an automorphic generator}\}##, then prove or find a counter-example for the following:

    ##\begin{aligned}(1)\quad &\big|\operatorname{aut}\mathbb{Z}_n^*\big|=\big|A\big|,\\
    (2)\quad &\operatorname{aut}\mathbb{Z}_n^*=\{\big<g_i,g_j\big>, j=1,2,\cdots, |A|\},\\
    \end{aligned}
    ##

    where we interpret ##\big<g_i,g_j\big>## as meaning the (bijective) homomorphism generated by the mappings ##g_i\to g_j\;\forall g_j\in A##. And I don't know how to precisely say, ``start with the mapping ##(a_1,a_2,\cdots,a_k)\to (b_1,b_2,\cdots,b_k)##. Now this completely defines a homomorphic image, and in these cases, an automorphic image ##\sigma:\mathbb{Z}_{n}^*\to \mathbb{Z}_n^*## by imposing the requirement ##\sigma(a_1^{e_1}\cdots a_k^{e_k})=\sigma(a_1)^{e_1}\cdots\sigma(a_k)^{e_k}## but that's what I mean.''

    I think that's all correct but not 100% sure. Need to study it more.
     
    Last edited: Jun 8, 2015
  5. Jun 8, 2015 #4
    I hate leaving the last post as I said something that's not correct so I just have to make another one since I can't edit it:

    Consider the isomorphic relation between a multiplicative integer mod group and it's (non-trivial) additive group factors:
    ##\mathbb{Z}_n^*\cong \mathbb{Z}_{x_1}\times \mathbb{Z}_{x_2}\times\cdots\times \mathbb{Z}_{x_k}##
    for ## n>2## where I have explicitly not factored the group into p-groups. For example:
    ##\begin{aligned} \mathbb{Z}_{129}^*&\cong \mathbb{Z}_{3}^*\times\mathbb{Z}_{43}^* \\
    &\cong \mathbb{Z}_2\times \mathbb{Z}_{42} \\
    \end{aligned}
    ##

    Now, since these are isomorphic, they are actually the same group and since the additive group obviously has elements of orders ##2## and ##42##, that is, elements (1,0) and (0,1) respectively, then both the additive group ##H=\mathbb{Z}_2\times\mathbb{Z}_{42}## and the multiplicative group ##\mathbb{Z}_{129}^*## are generated by elements with these orders and so ##\mathbb{Z}_{n}^*## will always have elements in which the product of the orders of the elements is equal to the size of the group and that the number of such additive factors must be the minimum size of the generator needed to generate ##\mathbb{Z}_n^*##.

    That is, given ##\mathbb{Z}_n^*\cong \mathbb{Z}_{x_1}\times \mathbb{Z}_{x_2}\times\cdots\times \mathbb{Z}_{x_k}## there exists ##(a_1,a_2,\cdots,a_k)\in \mathbb{Z}_{n}^*## such that ##o(a_1)=x_1, o(a_2)=x_2,\cdots o(a_k)=x_k## and ##\mathbb{Z}_n^*=\big<a_1,a_2\cdots,a_k\big>## and so obviously, ##\displaystyle\mathop\prod\limits^k o(a_i)=\big|\mathbb{Z}_n^*\big|##. I didn't realize this until now. Also I incorrectly stated in the last post that if we choose the generator described above and if the intersection of the orbits is unity, then it generates the group. That's not correct. We have to check that the product of the orbits generate the group. So I wish to re-state this hypothesis:

    Consider the additive group expansion:

    ##\mathbb{Z}_n^*\cong \mathbb{Z}_{x_1}\times\mathbb{Z}_{x_2} \cdots\times\ \mathbb{Z}_{x_k}## for ##n>2##.

    Then ##\mathbb{Z}_n^*## has elements with orders ##x_1, x_2,\cdots,x_k##.

    Now define an automorphic generator ##G=\big<a_1,a_2,\cdots,a_k\big>## of ##\mathbb{Z}_n^*## with ##o(a_1)=x_1,o(a_2)=x_2,\cdots o(a_k)=a_k## with ##a_i\neq a_j## and meeting the following requirement:

    ##\displaystyle\bigcap\limits_{n} \big<a_i\big>=\{1\}\quad \text{and}\quad \displaystyle\prod\limits^k \big<a_i\big>=\mathbb{Z}_{n}^*##.

    Let ##A=\{g_i : g_i\; \text{is an automorphic generator}\}##, then prove or find a counter-example for the following:

    ##\begin{aligned}(1)\quad &\big|\operatorname{aut}\mathbb{Z}_n^*\big|=\big|A\big|,\\
    (2)\quad &\operatorname{aut}\mathbb{Z}_n^*=\{\big<g_i,g_j\big>, j=1,2,\cdots, |A|\},\\
    \end{aligned}
    ##

    where we interpret ##\big<g_i,g_j\big>## as meaning the (bijective) homomorphism generated by the mappings ##g_i\to g_j\;\forall g_j\in A##.

    Ok, I think that's really close to what I want.
     
  6. Jun 10, 2015 #5
    I wish to add a corollary to this hypothesis: empirically it appears if we map, between isomorphic groups, an automorphic generator of one group to the set of automorphic generators of the other group, we generate the set of isomorphisms between them.

    Therefore, given two isomorphic groups ##\mathbb{Z}_n^*\cong\mathbb{Z}_m^*## and their associated sets of automorphic generators ##A,B## respectively, then:
    ##\operatorname{isom} \big\{\mathbb{Z}_n^*,\mathbb{Z}_m^*\big\}=\big<a,B\big>,\quad a\in A,\; \forall\; b\in B##

    where the notation ##\operatorname{isom} \big\{\mathbb{Z}_n^*,\mathbb{Z}_m^*\big\}## is the set of group isomorphisms.

    So I guess I need to prove this too unless I or someone else finds a counter-example.
    Here's a simple example: ##\mathbb{Z}_{15}^*\cong \mathbb{Z}_{16}^*## with:

    ##A=\{\{11,2\},\{11,7\},\{11,8\},\{11,13\},\{14,2\},\{14,7\},\{14,8\},\{14,13\}\}##
    ##B=\{\{7,3\},\{7,5\},\{7,11\},\{7,13\},\{15,3\},\{15,5\},\{15,11\},\{15,13\}\}##

    Then the mappings ## (11,2)\to B## generates the group isomorphisms.
     
    Last edited: Jun 10, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove relation between generators and automorphisms of Z/nZ*
  1. Automorphisms of Z^2 (Replies: 2)

Loading...