Category: Uncategorized

Generating direct powers

Before continuing, prove or disprove: If {G} is a group, the direct power {G^{\times n}} is never generated by fewer than {n} elements.

Certainly this is the case if {G} is abelian, as in this case {G^{\times n}} has a quotient of the form {\mathbf{F}_p^n}, i.e., an {n}-dimensional vector space over {\mathbf{F}_p}. This is also the case if {n\leq 2}. Examples of small size are therefore a little hard to find.

Here is a nice example: Denote the {m}th prime by {p_m}, and let {G = A_{p_m}}. Then I claim that {G^{\times(m-1)}} can be generated with {3} elements. Indeed, take {\alpha,\beta\in G^{\times(m-1)}} to be in each factor equal to some two generators {\tilde{\alpha},\tilde{\beta}} of {G}, and take {\gamma} to be an element of the form

\displaystyle (\sigma_3, \sigma_5, \sigma_7, \dots, \sigma_{p_m}),

where, for each {p}, {\sigma_p} is any {p}-cycle. Then the {(p_2\cdots p_j p_{j+2}\cdots p_m)}th power of {\gamma} is a {p_{j+1}}-cycle in the {j}th factor. With {\alpha} and {\beta} we can generate all the conjugates of this cycle, and these together generate the whole {j}th factor by simplicity.

The probability of coprimality

A famous result: Two positive integers chosen at random will be coprime with probability {6/\pi^2}.

One has to say what one means by this, since there is no uniform distribution on the positive integers. What we mean is that if we choose {x} and {y} uniformly and independently at random from the integers {\{1,\ldots,N\}}, then {x} and {y} will be coprime with probability tending to {6/\pi^2} as {N\rightarrow\infty}.

Here is one classic proof: Consider the points {(x,y)\in\{1,\ldots,N\}^2} such that {\gcd(x,y)=1}. If we scale this picture by {M}, we will have exactly the points {(X,Y)\in\{1,\ldots,MN\}^2} such that {\gcd(X,Y)=M}. Therefore, whatever the limiting probability {P} of being coprime is, the probability of having {\gcd = M} is exactly {P/M^2}. The law of total probability then implies

\displaystyle 1 = \lim_{N\rightarrow\infty}\mathbf{P}(\gcd(x,y)\in\mathbf{N}) = P \sum_{M=1} \frac{1}{M^2} = P\,\zeta(2).

Another way of imagining a random element on a noncompact group {G} is to look at the profinite completion {\hat{G}}, which is always compact so always possesses a uniform distribution. Now by the Chinese Remainder Theorem,

\displaystyle \hat{\mathbf{Z}} = \prod_p \mathbf{Z}_p,

so choosing an element at random from {\hat{\mathbf{Z}}} is the same as choosing an element at random from {\mathbf{Z}_p} for each {p}. The probability that a random element of {\mathbf{Z}_p} is divisible by {p} is precisely {1/p}, so the probably that two elements from {\hat{\mathbf{Z}}} are coprime is precisely

\displaystyle \prod_p (1-1/p^2) = 1/\zeta(2).

This does not imply the asymtotic result in {\mathbf{Z}} mentioned above, but it is a nice way of thinking about it.

EDIT (28/4/12): As pointed out to me by Freddie Manners, the “classic proof” suggested above suffers from the fatal defect of not proving that the limit exists. Here is an alternative proof which does prove that the limit exists. More generally, let {d>1} and consider positive integers {x_1,\ldots,x_d\leq X} chosen uniformly at random. Let {G(X)} be the number of {(x_1,\ldots,x_d)\in[1,X]^d} such that {\gcd(x_1,\ldots,x_d)=1}, and observe that the number of {(x_1,\ldots,x_d)\in[1,X]^d} such that {\gcd(x_1,\ldots,x_d) = n} is precisely {G(X/n)}. Then

\displaystyle \lfloor X\rfloor^d = \sum_{n\geq1} G(X/n)

for all {X}. Inverting this relationship,

\displaystyle G(X) = \sum_{n\geq1} \mu(n) \lfloor X/n\rfloor^d.

Thus, the probability that {d} randomly and uniformly chosen integers {x_1,\ldots,x_d\leq X} are all coprime is exactly

\displaystyle P(X) = \sum_{n\geq1} \mu(n) \left(\frac{\lfloor X/n\rfloor}{\lfloor X\rfloor}\right)^d.

The {n}th term here is bounded by {n^{-d}}, so by the dominated convergence theorem {P(X)\rightarrow\sum_{n\geq1} \mu(n) n^{-d} = \zeta(d)^{-1}}.