Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I show that the order of $\mathrm{Aut}(G)$ is less than $(n-1)(n-2)\cdots(n-2^k)$ where $k=[\log 2(n-1)]$?

The book suggests me to use the following result:

Let $d(G)$ be the smallest number of elements necessary to generate a finite group $G$. By convention $d(G)=0$ if $|G|=1$. Then $|G| \ge 2^{d(G)}$.

Thank you so much!

share|improve this question
    
"less" stands for <= –  Carmine Monetta May 2 '12 at 17:54
    
Kindly asking; what is the $n$? Is it the order of $G$? –  Babak S. May 2 '12 at 18:01
    
of course... Sorry! –  Carmine Monetta May 2 '12 at 18:09
1  
This question is related. –  Mikko Korhonen May 3 '12 at 8:09

2 Answers 2

Presumably $n = |G|$? Let $g_1,g_2,\ldots,g_m$ generate $G$, where $m=d(G)$. For $0 \le i \le m$, let $G_i$ be the subgroup of $G$ generated by $g_1,\ldots,g_i$. Then $G_0 < G_1 < \cdots G_{n-1} < G_m = G$, and the containments must all be proper, since otherwise one of the generators would be redundant. So $|G_{i+1}:G_i| \ge 2$ and hence $|G_i| \ge 2^i$ and $|G| \ge 2^m$. So $m \le \log_2(|G|)$.

Let $\alpha \in {\rm Aut}(G)$. Then there are $n-1$ possibilities for $\alpha(g_1)$. Given $\alpha(g_1),\alpha(g_2),\ldots, \alpha(g_i)$ for some $i<m$, $\alpha(g_{i+1})$ cannot lie in the subgroup generated by $\alpha(g_1),\alpha(g_2),\ldots, \alpha(g_i)$, which has order at least $2^i$, so there at most $(n-2^i)$ possibilities for $\alpha(g_{i+1})$. Multiplying the numbers of possible $\alpha(g_i)$ together gives the required bound on $|{\rm Aut}(G)|$ (but I don't think you have got the definition of $k$ quite right).

share|improve this answer
    
Ok, but at the end I find that |Aut(G)| is less than (n-1)...(n-2^m) where m is less than log2(n)! Do you think that there is some problem in the proposition??? anyway thank you! –  Carmine Monetta May 2 '12 at 18:39
    
You mean $|{\rm Aut(G)}| \le (n-1) \cdots (n-2^m)$ (not less than). Apart from that its OK, because $m < \log_2(n)$ implies $m \le \log_2(n-1)$ at least for $n>1$. –  Derek Holt May 2 '12 at 22:07
    
Or did you mean $\lfloor \log_2(n)-1 \rfloor$ rather than $\lfloor \log_2(n-1)\rfloor$? –  Derek Holt May 3 '12 at 7:43
    
m<=log2(n) not m<log2(n)... so I'm going out of my mind!However ⌊log2(n−1)⌋ it's Right. –  Carmine Monetta May 3 '12 at 13:56
up vote 0 down vote accepted

Let $G$ be a group of order $n> 1$ and let $\{x_1, \ldots, x_{d(G)}\}$ be a minimal set of generators for $G$. Taken, however, an automorphism $f$ of $G$, then it is in particular an application bijective fixing the unit of $G$, therefore, for $f(x_1)$ there are $n-1$ choices, as the order of $G \ {1}$. Choose $f(x_1)$, for $f(x_2)$ there are $| G \setminus \langle {f(x_1 )}\rangle |$ choices because, not being $x_2$ in $\langle{x_1}\rangle$, then $f(x_2) \not\in \langle{f(x_1 )}\rangle$: so the choices for $f(x_2)$ are $n-2$ because, for the exercise above, $|\langle {f(x_1 )}\rangle | \geq 2$. Assigned values to $f(x_1)$ and $f(x_2)$, from the exercise above follows that for $f(x_3)$ there are $|G \setminus \langle{f(x_1),f(x_2 )}\rangle | \leq (n-2^2)$ choices. So proceeding, for $f(x_{d(G)})$ remain at most $(n-2^{d(G) -1})$ choices. Then $|\operatorname{Aut}(G)| \leq \prod_{i = 0}^{d (G) -1} (n-2)^i$. In conclusion, observing that $d(G) \leq log_2 (n)$ then $d(G) -1 < log_2〖(n)〗$, or $2 ^{d(G) -1} < n$; therefore $2^{d(G) -1} \leq n-1$ and thus $d(G) -1 \leq log_2(n-1)$. Then $0 \leq i \leq d(​​G) -1 \leq \lfloor log_2(n-1) \rfloor$ and exercise is proven.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.