Consider the group $\mbox{Aff}(p)$ of automorphisms of $\mathbb{A}^1(p)$ [that is, the transformations $x\rightarrow a x + b,$ for $a\neq 0 \mod p.$] Is it true that a random pair of elements generate $\mbox{Aff}(p)?,$ for large $p?$
$\begingroup$
$\endgroup$
3
asked Nov 4, 2016 at 11:10
-
2$\begingroup$ The group $H$ of units modulo $p$ is a cyclic group of order $p-1$. So for $p>2$ the group of squares $H^2$ has index 2. So the probability that a pair in $H$ lies in $H^2$ is 1/4. Thus the probability of generating is $\le 3/4$. For those $p$ such that $(p-1)/2$ is prime, the probability of generating $H$ is thus exactly $3/4$, and the probability of generating inside the affine group will tend to 3/4. (This is a particular case of Jan's answer) $\endgroup$– YCorCommented Nov 4, 2016 at 16:48
-
1$\begingroup$ @YCor. That's probably the easiest explanation why the probability in question can be at most $3/4$. I think the second part of your comment is not correct: the probability of generating $H$ is exactly $3/4$ iff $|H|$ is a power of $2$ (thus $p$ is a Fermat prime). Otherwise, there are other maximal subgroups of $H$ than the group of squares, and we must exclude the possibility that a pair is in these other subgroups. $\endgroup$– Frieder LadischCommented Nov 4, 2016 at 18:00
-
1$\begingroup$ @FriederLadisch: I assumed explicitly that $(p-1)/2$ is prime. So there are exactly two maximal subgroups: the group of squares, and the group $\{\pm 1\}$. So OK I forgot $-1$. Then the probability that a pair of elements in the multiplicative group lies in a maximal subgroup is $1/4+3/(p-1)^2$, i.e. the probability it generates is $3/4-3/(p-1)^2$. $\endgroup$– YCorCommented Nov 4, 2016 at 20:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
12
In general not. Consider the homomorphism $\mathrm{Aff}(p)\rightarrow\mathbb{F}_p^*$ mapping $ax+b$ to $a$. The probability that two random elements generate a subgroup for which the induced map is still surjective equals the probability that two random elements in $\mathbb{F}_p^*$ generate this group, which is $$\frac{1}{(p-1)^2}\sum_{d|p-1} \mu\left(\frac{p-1}{d}\right) d^2 = \sum_{t|p-1}\frac{\mu(t)}{t^2} = \prod_{q|p-1}\left(1-\frac{1}{q^2}\right),$$ where in the last product $q$ runs over primes only. Depending on the prime factors of $p-1$ this quantity is somewhere in the interval $[\frac{6}{\pi^2}, \frac{3}{4}]$.
On the other hand two random elements almost surely generate a subgroup containing a translation, and therefore all translations, thus the probability that two random elements generate $\mathrm{Aff}(p)$ is asymptotically equal to the quantity given above.
answered Nov 4, 2016 at 12:39
Jan-Christoph Schlage-PuchtaJan-Christoph Schlage-Puchta
9,1772 gold badges30 silver badges56 bronze badges
-
1$\begingroup$ Could you please elaborate on why this sum is less that $3/4$? $\endgroup$– SashaPCommented Nov 4, 2016 at 13:04
-
2$\begingroup$ I think you mean two random elements almost certainly generate a subgroup containing a translation. A single random element is very likely to have order dividing $p-1$. $\endgroup$ Commented Nov 4, 2016 at 13:26
-
1$\begingroup$ The assertion "a random element almost surely generates a translation" is not correct. An element $x\mapsto ax+b$, with $a\neq 1$, has no power that is a nonzero translation. Indeed, such a power has the form $x\mapsto a^kx+(a^k-1)/(a-1)$ (other interpretation: non-translations are conjugate to homotheties). On the other hand it's true that a random pair generates a subgroup containing a translation. $\endgroup$– YCorCommented Nov 4, 2016 at 17:00
-
2$\begingroup$ @IgorRivin A subgroup with no translation is abelian. Then count the number of commuting pairs. $\endgroup$– YCorCommented Nov 4, 2016 at 17:12
-
1$\begingroup$ @SashaP: When I expand "my" product, I get the second sum in Jan-Christoph's formula. My reasoning is so: write $C_n=C_{p-1}$ as direct product of cyclic groups $C_{q^k}$ of prime power order. Two elements generate $C_n$ iff their projections to every direct factor generate that factor. Two random elements of $C_{q^k}$ do not generate $C_{q^k}$ with probability $1/q^2$. $\endgroup$ Commented Nov 4, 2016 at 17:49