The Markoff Group of Transformations in Prime and Composite Moduli
Chen Meiri Doron Puder Dan Carmon

rot 
rot 
Alt 
P 
F 
Tr 
tr 
Soc 





The Markoff Group of Transformations

in Prime and Composite Moduli
    Chen Meiri and Doron Puder

with an Appendix by Dan Carmon
    December 30, 2023
===================================================================


The Markoff group of transformations is a group Γ of affine
integral morphisms, which is known to act transitively on the set
of all positive integer solutions to the equation x^2+y^2+z^2=xyz.
The fundamental strong approximation conjecture for the Markoff equation
states that for every prime p, the group Γ acts transitively
on the set X^*(p) of non-zero solutions to the same
equation over ℤ/pℤ. Recently, Bourgain,
Gamburd and Sarnak proved this conjecture for all primes outside a
small exceptional set.

In the current paper, we study a group of permutations obtained by
the action of Γ on X^*(p), and show that for
most primes, it is the full symmetric or alternating group. We use
this result to deduce that Γ acts transitively also on the
set of non-zero solutions in a big class of composite moduli. 

Our result is also related to a well-known theorem of Gilman and Evans,
stating that for any finite non-abelian simple group G and r≥3,
the group Aut(_r) acts on at least one
“T_r-system” of G as the alternating or symmetric group.
In this language, our main result translates to that for most primes
p, the group Aut(_2) acts on a particular
T_2-system of PSL(2,p) as the alternating
or symmetric group.





§ INTRODUCTION


The Markoff surface 𝕏 is the affine surface in 𝔸^3
defined by the equation[Sometimes the Markoff equation is written as x^2+y^2+z^2=3xyz.
However, these two equations are equivalent in the sense that their
integer solutions are related bijectively by (x,y,z)⟷(3x,3y,3z).
This bijection holds also for solutions in ℤ/pℤ
for every prime p≠3.]

    x^2+y^2+z^2=xyz.

The Markoff triples MM is the set
of positive integer solutions to Equation (<ref>), such
as (3,3,3). The Markoff group of automorphisms of 𝕏
is the group ΓΓ generated by permutations
of the coordinates and the Vieta involutions R_1, R_2 and
R_3R_i where R_3(x,y,z)=(x,y,xy-z)
and R_1 and R_2 are defined analogously. It is easy to see
that M is invariant under Γ and Markoff proved that
Γ acts transitively on M <cit.>.
Let Δ be the group generated by Γ and the involutions
that replace two of the coordinates by their negatives. Then the set
𝕏(ℤ) of integer solutions to (<ref>)
has two Δ-orbits: {(0,0,0)} and
its complement X^*(ℤ)def=𝕏(ℤ)∖{(0,0,0)}. 



 §.§ Prime Moduli


If p is a prime number, then 𝕏(ℤ/pℤ)
is the finite set of solutions to (<ref>) in ℤ/pℤ,
and we denote X^*(p)=𝕏(ℤ/pℤ)∖{(0,0,0)}X^*(p).
The strong approximation conjecture for the Markoff equation (<ref>)
states that for every prime p, the reduction mod p of the set
of Markoff triples M→ X^*(p) is onto. This
is clearly equivalent to Γ acting transitively on X^*(p).
Recently, Bourgain, Gamburd and Sarnak proved this conjecture for
all primes outside of a small exceptional set:

Let E be the set of primes for which Γ
does not act transitively on X^*(p). For any ε>0,
the number of primes p≤ T with p∈ E is at most T^ε,
for T large enough.

Moreover, for any ε>0, the largest Γ-orbit in
X^*(p) is of size at least |X^*(p)|-p^ε,
for p large enough (whereas |X^*(p)|∼ p^2).

Let Γ_pΓ_p be the finite permutation
group induced by the action of Γ on X^*(p).
In the current work we study the nature of this group. The first step
here is to notice that Γ_p preserves a block structure as
follows: 

For (x,y,z)∈ X^*(p) denote by [x,y,z][x,y,z]
the block of all solutions obtained from (x,y,z) by
sign changes, so 

    [x,y,z]def={(x,y,z),(x,-y,-z),(-x,y,-z),(-x,-y,z)} .

Then Γ_p preserves this block structure. Let Y^*(p)Y^*(p) 
denote the set of blocks in X^*(p), and Q_pQ_p
denote the permutation group induced by the action of Γ (or
Γ_p) on Y^*(p). Simulations suggest the
following conjecture:

For every p≥5, the permutation
group Q_p is the full alternating or symmetric group.

This conjecture was also raised, independently, in <cit.>,
where the authors also state precisely for which primes one can expect
the alternating group (p≡316) and for which the full symmetric
group (p≢316). If this conjecture holds, then roughly
speaking (we give the precise formulation in Theorem <ref>
below), Γ acts transitively on the solutions of (<ref>)
modulo n, for every square free.

Here we prove this conjecture for most primes. More particularly,
we prove it for every p≡1(4) outside the exceptional
set from Theorem <ref>, and for density-1 of the primes p≡3(4): 

If p≡1(4) and Q_p is transitive,
then Q_p is the full alternating or symmetric group on Y^*(p). 

Namely, Q_p is the full alternating or symmetric group for all
p≡1(4) outside the exceptional set from Theorem
<ref>. In fact, our proof yields that for every p≡1(4),
the group Γ acts as the full alternating or symmetric group
on the large component described in Theorem <ref>. In the
case p≡3(4), our proof is more involved and requires
one further assumption:

Let p
be a prime. Assume that:



  * p≡3(4).

  * Q_p is transitive.

  * The order of 3+√(5)/2∈𝔽_p^2 is at least
32√(p+1).

Then Q_p is the full alternating or symmetric group on Y^*(p).

The number 3+√(5)/2 is related to the special solution
[3,3,3]∈ Y^*(p): its order inside 𝔽_p^2
gives the length of the cycle of the transformation [x,y,z]↦[x,z,xz-y]
containing the element [3,3,3]. For details see Sections
<ref> and <ref>.

As shown in Appendix <ref>, the condition regarding
the order of 3+√(5)/2 is satisfied for density-1 of
the primes[A set of primes A has density 1 if lim_n→∞| A∩ P_n|/| P_n|=1,
where P_n={ 1<p≤ n | p is prime}.
In fact, the set of primes for which 3+√(5)/2 has order
at least 32√(p+1) satisfies something slightly stronger than
density 1 – see Appendix <ref>.], hence

For density-1 of all
primes p≡3(4), the group Q_p is the full alternating
or symmetric group on Y^*(p).




 §.§ Composite Moduli


Let n be a positive integer which is square-free, so n=p_1⋯ p_k
where p_1,…,p_k are distinct primes. Let 𝕏(n)𝕏(n)
denote the set of solutions to the Markoff equation (<ref>)
in ℤ/nℤ. By the Chinese Remainder
Theorem, 𝕏(n)=𝕏(p_1)×…×𝕏(p_k),
and let X^*(n)=X^*(p_1)×…× X^*(p_k)X^*(n) 
be the set of solutions which are non-zero modulo any of the primes
composing n. The action of Γ on 𝕏(n)
is the diagonal action on the 𝕏(p_i), and
the subset X^*(n) is invariant under this action.
Denote the corresponding permutation group Γ_nΓ_n.
Is the action on X^*(n) transitive? It turns out that
this would follow from Conjecture <ref> and
indeed holds true for the cases of that conjecture we establish:

Let n=p_1⋯ p_k
be a product of distinct primes. If for every j=1,…,k, Q_p_j≥Alt(Y^*(p_j)),
then Γ acts transitively on X^*(n).

In particular, if conjecture <ref> holds,
then Γ acts transitively on X^*(n) for every
square-free n.


Let 
denote the set of primes that satisfy the assumptions of Theorem <ref>
or of Theorem <ref>.
Then for every set of distinct primes p_1,…,p_k∈,
Γ acts transitively on X^*(p_1⋯ p_k).

Bourgain, Gamburd and Sarnak already proved Corollary <ref>
for primes p≡1(4) for which Γ_p is transitive.
This result should appear in the series announced in <cit.>.
We stress that our proof is entirely different: while Bourgain, Gamburd
and Sarnak improve their techniques from the proof of Theorem <ref>
so that the argument work for several primes simultaneously, our proof
is group-theoretic and uses Theorem <ref> as a black box.
Both proofs rely on solutions containing the parabolic elements ±2
– see Figure <ref> and Section
<ref>. 

For n=p_1⋯ p_k as above, we use the notation Y^*(n)=Y^*(p_1)×…× Y^*(p_k)Y^*(n)
for the set of blocks in X^*(n) and Q_nQ_n
for the permutation group induced by the action of Γ on Y^*(n).
Note that these blocks are given by sign changes modulo every prime
separately and are usually of size 4^k each (if all primes are
odd). It is quite straight-forward to prove that under the assumptions
of Theorem <ref>,
Γ acts transitively on Y^*(n), using composition
factors of Q_n. It requires some further argument to show that
Γ acts transitively on the full set X^*(n).
We elaborate in Section <ref>.

 At this point we would like to remark on the dependence of our results
on the Classification of Finite Simple Groups (CFSG)CFSG.
We use the classification only in the proof of Theorem <ref>:
we first give an elementary proof that for a prime p satisfying
the assumptions in the theorem, Q_p is a primitive permutation
group[Recall that a permutation group G≤Sym(m)
is called primitive if it does not preserve any non-trivial block-structure.
In particular, if m≥3, G must be transitive.], and then rely on (results depending on) the CFSG to deduce that
Q_p is the full alternating or symmetric group. If we rely on
Theorem <ref>
to deduce Corollary <ref>,
the latter also becomes partly dependent on the CFSG. This can be
avoided, however, and to this aim we also give a proof that Γ
acts transitively on X^*(n) assuming only that Q_p_1,…,Q_p_k
are primitive permutation groups, without using the CFSG (see Theorem
<ref> below). To sum
up, the only results depending on the CFSG are Theorem <ref>,
Corollary <ref>, and the
part of Theorem <ref> relating to primes
p≡3(4). In contrast, Theorems <ref>
and <ref> and
Corollary <ref>
do not depend on the CFSG. We illustrate this in Figure <ref>.

Indeed, the following result does not depend on the CFSG:

Let n=p_1⋯ p_k
be a product of distinct primes. If Q_p_1,…,Q_p_k
are primitive permutation groups, then Γ acts transitively
on X^*(n).






 §.§ T_2-systems


Let G be a finitely generated group and _r the free group
on r generators. A normal subgroup N⊴_r is
said to be G-defining if _r/N≅ G.
Denote by Σ_r(G)Σ_r(G)
the set of G-defining normal subgroups in _r. Consider the
action of Aut(_r) (in fact, of Out(_r))
on Σ_r(G). The orbits of this action are called
T_r-systems of G. 

The following theorem is due to Gilman (for r≥4) and Evans (who
extended to r=3):

<cit.> Let G be
a finite non-abelian simple group and r≥3. Then Aut(_r)
acts on at least one T_r-system of G as the alternating or
symmetric group.

In fact, Gilman and Evans provide more information about the special
T_r-system on which Aut(_r) acts as
the full alternating or symmetric group, and show it is especially
large. Gilman also showed that for G=PSL(2,p)
with p≥5 prime, there is only one T_r-system for r≥3.
Namely, he proved that Aut(_r) acts transitively
on Σ_r(G). Theorem <ref> says, of
course, that the permutation group in this case is the alternating
or symmetric group. For more details we refer the reader to the beautiful
surveys <cit.>.

When r=2, the action of Aut(_2) on Σ_2(G)
is not transitive for any finite non-abelian simple group G. In
fact, the number of T_2-systems tends to infinity as |G|→∞
<cit.>. The main reason for this phenomenon
is that if { a,b} are a set of generators of _2,
and φ_2↠ G an epimorphism, then
the set of conjugacy classes of[Here, [a,b] denotes the commutator aba^-1b^-1.]
φ([a,b]) and of φ([a,b])^-1
is a well-defined invariant of the G-defining subgroup N=φ,
which is also invariant under Aut(_2).
We elaborate more in Section <ref>.

Our result sheds more light on the case of T_2-systems for G=PSL(2,p).
If A,B∈SL(2,p) and we denote x=tr(A),
y=tr(B) and z=tr(AB),
then 

    tr([A,B])=x^2+y^2+z^2-xyz-2.

In Section <ref> it is explained why the map (A,B)↦(tr(A),tr(B),tr(AB))
yields a bijection between the elements in Σ_2(PSL(2,p))
with associated trace -2 and the elements of Y^*(p).
In this language, the main result of <cit.> –
Theorem <ref> above – says that outside the exceptional
set of primes, these elements form a single T_2-system. See <cit.>
for an extensive survey of the connection between the Markoff equation
(<ref>) and T_2-systems of PSL(2,p).
Through this connection, Theorems (<ref>) and (<ref>)
translate to a result in the spirit of Theorem <ref>:

Assume that the prime p satisfies
the assumptions of Theorem <ref> or of Theorem <ref>.
Then Aut(_2) acts on the trace-(-2)
T_2-system of PSL(2,p) as the full alternating
or symmetric group.

The paper is organized as follows. Section <ref>
gives some more notation and collects some results from <cit.>
we use here. In the short Section <ref>
and longer Section <ref> we prove
Theorem <ref> for p≡1(4) and Theorem
<ref> for p≡3(4),
respectively. Section <ref>
is dedicated to proving the transitivity of Γ in certain composite
moduli: first assuming the groups Q_p contain the alternating
group (in Section <ref>), and then assuming
only that Q_p is primitive (Section <ref>).
In Section <ref> we give some background on T-systems
and prove Theorem <ref>. Finally, Appendix
<ref>, by Dan Carmon, shows that the assumption in
Theorem <ref> regarding the order
of 3+√(5)/2∈𝔽_p^2 holds for most primes. 



 §.§ Acknowledgments


We are indebted to Peter Sarnak for his encouragement, and for stimulating
discussions, enlightening suggestions and clever advice. We would
also like to thank Zeev Rudnick and Pär Kurlberg for beneficial comments,
and to Dan Carmon for writing the useful Appendix <ref>.
We have benefited much from the mathematical open source community,
and in particular from SageMath. Author Meiri was supported by BSF
grant 2014099 and ISF grant 662/15. Author Puder was supported by
the Rothschild fellowship, by the NSF under agreement No. DMS-1128155
and by the ISF grant 1071/16. Author Carmon was supported by the European
Research Council under the European Union's Seventh Framework Programme
(FP7/2007-2013) / ERC grant agreement n^o 320755. 



§ PRELIMINARIES


Before proving our main results, let us describe some further notation
and collect further results from <cit.> that we
use below.



 §.§ Further notation



  * We already introduced above the notation [x,y,z] for
the block of the solution (x,y,z) in X^*(p),
so [x,y,z]∈ Y^*(p). We also use this
notation for a composite (square-free) modulo n: here [x,y,z]
is the element (block) in Y^*(n) containing the solution
(x,y,z).

  * Some elements in Γ are permutations of the three coordinates
of solutions. We denote these elements by τ_(12)τ_(12),τ_(123)
for the permutation exchanging the first and second coordinates, by
τ_(123) for the cyclic permutation and so on. By
abuse of notation, we use the same notation for the corresponding
elements in Γ, Γ_p, Q_p, Γ_n and
Q_n. 

  * The analysis in <cit.>, as well as in the current
work, relies heavily on three “rotation” elements
_1,_2,_3∈Γ_i.
They are defined by

    _jdef=R_j+2∘τ_(j+1  j+2)

(the indices are taken modulo 3). For example, (x,y,z)_1↦(x,z,xz-y).
The rotation _j fixes the j-th coordinate and its action
on X^*(p) and on Y^*(p) is completely
analyzed in <cit.> – see Lemmas <ref>
and <ref> below. Again, by abuse
of notation we write _i for the rotation element in the different
groups Γ, Γ_p, Q_p, Γ_n and Q_n. 

  * Following <cit.>, we denote the “conic sections”
by C_j(a) C_j(a), j=1,2,3.
These are defined as

    C_j(a)={(x_1,x_2,x_3)∈ X^*(p) | x_j=a} .

When we write C_j(± a)C_j(± a),
we mean the conic section in Y^*(p):

    C_j(± a)={[x_1,x_2,x_3]∈ Y^*(p) | x_j=a} .


  * For every prime p we let ii denote a square root
of -1 (in 𝔽_p or in 𝔽_p^2).

  * For x∈ℤ/pℤ we use the standard
Legendre symbol (x/p)(x/p)
to denote the image of x under the character of order 2. Namely,

    (x/p)=
    1     x is a square in 𝔽_p^*
    
    -1     x is a non-square in 𝔽_p^*
    
    0     x=0
    .


  * The notation |x| is used to denote the order of the
group element x∈ G in the group G.




 §.§ Rotation elements


The action of _1 on the conic section C_1(x)⊆ X^*(p)
is a linear map on the last two coordinates given by the matrix

    ([  0  1; -1  x ]).

The eigenvalues of this matrix are given by x±√(x^2-4)/2.
This leads to the following definitions and lemmas from <cit.>:




  * An element x∈𝔽_p if called hyperbolichyperbolic
if (x^2-4) is a square in 𝔽_p^*.

  * An element x∈𝔽_p if called ellipticelliptic
if (x^2-4) is a non-square in 𝔽_p^*.

  * An element x∈𝔽_p if called parabolicparabolic
if (x^2-4)=0 in 𝔽_p, namely, if x=±2.


Notice that this categorization of the elements is invariant under
sign change x↦-x. The following lemmas are based on Lemmas
3-5 of <cit.> which describe the action of _i
on X^*(p). We adapt them below in order to describe
the action of _i on Y^*(p) and add some further
details, all follow easily from Section 2.1 in <cit.>.
We state the lemmas for C_1(± x), but the same statements
holds, evidently, for C_2(± x) and for C_3(± x).

<cit.>
Let p≡1(4) be prime. Then,


  * |Y^*(p)|=p(p+3)/4.

  * |C_1(±2)|=p; The permutation induced
by _1 on C_1(±2) consists of a single p-cycle. 

  * There are p-1/4 hyperbolic elements up to sign. For x
hyperbolic, |C_1(± x)|=p-1/2.
Let ω^±1∈𝔽_p be the eigenvalues of the matrix
(<ref>), so x=ω+ω^-1. The permutation
induced by _1 on C_1(± x) consists of p-1/2d
cycles of length d each, where d=max(|ω|,|-ω|)/2
and |ω| is the order of ω in the multiplicative
group 𝔽_p^*. The solutions in C_1(x)
have the form (x,α+β,αω+βω^-1)
for α,β∈𝔽_p^* with αβ=x^2/x^2-4,
and 

    (x,α+β,αω+βω^-1)_1↦(x,αω+βω^-1,αω^2+βω^-2).


  * There are p-1/4 elliptic elements up to sign. For x
elliptic, |C_1(± x)|=p+1/2. Define
ω as for hyperbolic elements by x=ω+ω^-1, only
now ω∈𝔽_p^2∖𝔽_p. The permutation
induced by _1 on C_1(± x) consists of p+1/2d
cycles of length d each, where d=max(|ω|,|-ω|)/2
and |ω| is the order of ω in the multiplicative
group 𝔽_p^2^ *. Moreover, ω^p+1=1, i.e. |ω| | (p+1).
The solutions in C_1(x) have the form (x,A+A^p,Aω+A^pω^-1)
with A∈𝔽_p^2^* and A^p+1=x^2/x^2-4,
and 

    (x,A+A^p,Aω+A^pω^-1)_1↦(x,Aω+A^pω^-1,Aω^2+A^pω^-2).



We sum up the content of Lemma <ref>
in Table <ref>.



When p≡3(4), our results are somewhat weaker and
the proofs more involved. The main reason for that is the lack of
solutions with the parabolic elements ±2:

<cit.>
Let p≡3(4) be prime. Then,


  * |Y^*(p)|=p(p-3)/4

  * There are no solutions in Y^*(p) involving the parabolic
elements ±2, nor the elliptic element 0.

  * There are p-3/4 hyperbolic elements up to sign. For x
hyperbolic, the size and structure of C_1(± x) and
the action of _1 on C_1(± x) have the same
properties as for x hyperbolic when p≡1(4) (see
Lemma <ref>).

  * There are p-3/4 non-zero elliptic elements up to sign.
For x elliptic, the size and structure of C_1(± x)
and the action of _1 on C_1(± x) have the
same properties as for x elliptic when p≡1(4)
(see Lemma <ref>).


We sum up the content of Lemma <ref>
in Table <ref>.



For x∈𝔽_p, denote by d_p(± x)d_p(± x)
the order of _1∈ Q_p in its action on C_1(± x).
Namely, the solutions with first coordinate ± x in Y^*(p)
belong to cycles of length d_p(± x).



§ ALTERNATING GROUP FOR P≡1(4) 


This section contains the proof of Theorem <ref>, which
states that if p≡1(4) and Q_p is transitive,
then Q_p contains the entire alternating group Alt(Y^*(p)).
As mentioned above, the existence of parabolic elements when p≡1(4)
allows a rather short argument in this case.

We use the following classical theorem of Jordan:

 Let G≤Sym(n) be a primitive
permutation group containing a cycle of prime length p≤ n-3.
Then G≥Alt(n).


 Assume p≡1(4), and let _1∈ Q_p be
the rotation element defined on Page rotations. This element
has one p-cycle, while all its other cycles have length coprime
to p (see Table <ref>). Thus its power σ=_1^ |_1|/p∈ Q_p
is a p-cycle. As |Y^*(p)|=p(p+3)/4≥ p+3,
it is now sufficient to show, by Jordan's Theorem (Theorem <ref>
above), that Q_p is primitive in Sym(Y^*(p)). 

We need to show that the group Q_p preserves no non-trivial block
structure. Assume there is a block structure { B_1,…,B_m}
preserved by Q_p. So ⋃ B_i=Y^*(p) and
B_i∩ B_j=∅ for i j, and for every g∈ Q_p
and every i, g(B_i)=B_j for some j.

Consider C_1(±2)⊂ Y^*(p), the
p elements contained in the cycle of size p in σ. The
set C_1(±2) must be contained in a block, for otherwise
it has to be the union of several equally-sized blocks, but p is
prime. Say C_1(±2)⊆ B_1. So B_1 contains
all solutions with ±2 in the first coordinate. In particular,
it contains [2,2,2+2i] and [2,2+2i,2].
But the same argument with _2 and _3 shows that
B_1 contains all solutions with ±2 in any coordinate. So
B_1 is invariant under all three rotations and under all permutations
of coordinates, and therefore invariant under the action of the whole
group Q_p. By the transitivity of Q_p, B_1=Y^*(p).


The proof of Theorem <ref> in <cit.> shows
that for every prime p, the large component of X^*(p)
contains all solutions with parabolic (±2) coordinates.
Thus, our proof of Theorem <ref> applies to the general
case: the group Γ acts on the large component of Y^*(p)
as the alternating or symmetric group.




§ ALTERNATING GROUP FOR P≡3 (4)


In the case where p≡3(4), there are no parabolic
elements, and in Sections <ref>
and <ref> we establish the primitivity
of Q_p for density-1 of these primes rather than for all those
outside the exceptional set from Theorem <ref>. We also rely
on much deeper theorems, involving the classification of finite simple
groups (CFSG), to conclude in Section <ref>
that whenever Q_p is primitive, it contains Alt(Y^*(p)).
Throughout this section, we assume that p≡3(4).



 §.§ Primitivity of Q_p when p≡3(4)


In this subsection we prove that under the assumptions of Theorem
<ref>, the permutation
group Q_p is primitive. Namely,

Let p be prime with p≡3(4).
Assume that Q_p is transitive and that the order of 3+√(5)/2∈𝔽_p^2
is at least 32√(p+1). Then Q_p is primitive.

To establish primitivity of Q_p, one needs to show there are
no non-trivial blocks in the action of Q_p on Y^*(p):
a block is a subset B⊆ Y^*(p), such that for
every g∈ Q_p, either g.B=B or g.B∩ B=∅. As
Q_p is assumed to be transitive, if B is proper (B⫋ Y^*(p))
and of size at least two, then the subsets { g.B | g∈ Q_p}
constitute a partition of Y^*(p) which is a non-trivial
block structure preserved under the action of Q_p. So proving
Q_p is primitive is equivalent to showing that every proper block
is a singleton.

The proof of Theorem <ref> relies
on the following two propositions which contain properties of blocks
in Y^*(p). We defer the proofs of these two propositions
to the next subsection, and complete the proof of Theorem <ref>
in the current subsection, assuming the two propositions.

We say that some coordinate j∈{ 1,2,3} is homogeneous
in a block B⊆ Y^*(p) if the j-th coordinate
of every solution in B is of the same type (either all hyperbolic
or all elliptic). 

Let p≡3(4).
Assume that Q_p acts transitively on Y^*(p),
and let B⫋ Y^*(p) be a proper Q_p-block.
Then at least two of the coordinates { 1,2,3} are
homogeneous in B.

The most technical ingredient of the proof of primitivity is the following.
Recall that d_p(± x) denotes the length of the cycles
of _1∈ Q_p containing elements of C_1(± x).

Assume
that Q_p is transitive and let x∈𝔽_p∖{ 0,±2}
satisfy d_p(± x)≥16√(p+1). Then, for every
j∈{ 1,2,3}, every proper Q_p-block B⫋ Y^*(p)
contains at most one solution with j-th coordinate ± x.

The idea of the proof of this proposition is the following: assume
there are two solutions in the block B with first coordinate ± x.
Say these are [x,y_0,y_1] and [x,z_0,z_1].
Then for every 1≤ m, the block _1^ m(B)
contains the solutions [x,y_m,y_m+1] and [x,z_m,z_m+1]
with y_m and z_m defined recursively by y_m+1=xy_m-y_m-1
and z_m+1=xz_m-z_m-1. By Proposition <ref>,
at least one of the two coordinates 2,3 in every block is homogeneous,
meaning that for every m, either y_m and z_m have the
same type (hyperbolic or elliptic), or y_m+1 and z_m+1 have
the same type. Using classical results in number theory, we show such
“high correlation” between two cycles of _1 is impossible
whenever these cycles are long enough.

Section <ref> gives the details of the
proof, and assuming it, we finish the proof of Theorem <ref>.
We need the following corollary showing that elements of high order
in the sense of Proposition <ref>
appear in the same block and the same coordinate only with other elements
of the same type and the same order:

Assume
that Q_p is transitive and that x∈𝔽_p∖{ 0,±2}
satisfies d_p(± x)≥16√(p+1). If B⫋ Y^*(p)
is a proper Q_p-block containing some solution with first coordinate
± x, and another solution with first coordinate ± x', then
d_p(± x)=d_p(± x'). In particular,
x and x' are of the same type (both hyperbolic or both elliptic).


Note that _1^ d_p(± x)(B)=B.
By Proposition <ref>,
_1^ m(B) B for 1≤ m<d_p(± x).
Hence, d_p(± x') is some multiple of d_p(± x).
In particular, the assumption of Proposition <ref>
holds for x', and by symmetry, d_p(± x) is a
multiple of d_p(± x'). Hence d_p(± x')=d_p(± x).



 Assume that Q_p is transitive and ω=3+√(5)/2∈𝔽_p^2^ *
has order at least 32√(p+1). We need to show that Q_p
is primitive. We use the special symmetric solution [3,3,3]∈ Y^*(p).
Whenever ω∈𝔽_p^2 has high order in the multiplicative
group 𝔽_p^2^*, the cycle of _1∈ Q_p
containing the solution [3,3,3] is long. More concretely,
3=ω+ω^-1, and by Lemma <ref>
and Table <ref>, d_p(±3) is either
|ω| or |ω|/2, where
|ω| is the order of ω in the multiplicative
group 𝔽_p^2^  *. So d_p(±3)≥16√(p+1).

Assume that [a,b,c] and [3,3,3] are two
distinct solutions lying in the same proper Q_p-block B⫋ Y^*(p).
By Lemma <ref>, d_p(±3)≥16√(p+1),
and by Corollary <ref>,
d_p(± a)=d_p(± b)=d_p(± c)=d_p(±3).
As [3,3,3] is the only solution of the form [x,x,x]
or [x,x,-x], we can assume without loss of generality
that {± b}{± c}. Since τ_(2 3)
stabilizes [3,3,3], we have τ_(2 3)(B)=B,
so the two distinct solutions [a,b,c] and [a,c,b]
both belong to B. This contradicts Proposition <ref>:
d_p(± a)=d_p(±3) is large and thus
a cannot appear twice in the same coordinate in the same block.

As mentioned in Section <ref>, the assumptions in
Theorem <ref> hold for density-1
of the primes p≡3(4). Indeed, relying on strong
results of Ford <cit.>, Dan Carmon proves in
Proposition <ref> in Appendix <ref>
that under some assumptions, the order of a quadratic integer modulo
primes is high for density-1 of the primes. From Proposition <ref>
we deduce:

For density-1 of all primes,
the element ω=3+√(5)/2∈𝔽_p^2 has
order at least 32√(p+1) in the multiplicative group 𝔽_p^2^  *,
in which case d_p(±3)≥16√(p+1).

Combining Theorem <ref> with Corollary <ref>
shows why the assumptions in Theorem <ref>
hold for density-1 of all primes p≡3(4), hence:

For density-1
of all primes p≡3(4), the group Q_p is primitive
in its action on Y^*(p).


It is conceivable that there
is a stronger version of Proposition <ref>
which states there cannot be correlation between two long cycles of
_1∈ Q_p even with two different first coordinates. Were
we able to prove this, we could omit the condition about the order
of 3+√(5)/2 in the statements of Theorems <ref>
and <ref> and assume only that Q_p
is transitive to conclude that it is primitive and, moreover, contains
Alt(Y^*(p)). (This would make
Theorem <ref>
completely parallel to Theorem <ref> dealing with p≡1(4).)
In Remark <ref>
below we explain the obstacle to proving this more general version
of Proposition <ref>.




 §.§ Properties of blocks in the action of Q_p on Y^*(p)


In the current subsection we prove the two propositions that were
stated without proof in the previous subsection. Proposition <ref>
is proved in Section <ref>, and
Proposition <ref>
proved in Sections <ref> (the hyperbolic
case) and <ref> (the elliptic case).



  §.§.§ Homogeneity of coordinates in blocks


The subgroup H=⟨_1,_2,_3⟩≤Γ
has index at most 2 in Γ.


By definition, Γ is generated by the three Vieta involutions
and permutations of coordinates. Since R_3=_1·τ_(2 3)
and likewise for R_1 and R_2, since τ_(1 3 2)=_3·_1
and since S_3=⟨(12),(132)⟩,
we obtain that Γ=⟨_1,_2,_3,τ_(1 2)⟩ =⟨ H,τ_(1 2)⟩.
It is easy to check that τ_(1 2)_jτ_(1 2)∈ H
for j=1,2,3, so H⊴Γ and Γ=H·⟨τ_(1 2)⟩.
This finishes the proof.

Recall that Proposition <ref> says
that if Q_p acts transitively on Y^*(p), and
if B⫋ Y^*(p) is a proper block of the action
of Q_p on Y^*(p), then at least two of the coordinates
{ 1,2,3} are homogeneous in B.

Assume that some coordinate, say j=1, is not homogeneous in B.
We need to show that the second and third coordinates are homogeneous.
The element _1^(p-1)/2 fixes every solution
with first coordinate hyperbolic, while _1^(p+1)/2
fixes every solution with first coordinate elliptic. Hence B is
invariant under both elements, and thus by _1. 

By the same argument, if all three coordinates are not homogeneous,
B is invariant under H_p=⟨_1,_2,_3⟩≤ Q_p.
By Lemma <ref>, [Q_p:H_p]≤2,
and transitivity implies there are at most two blocks in the action:
B and B'=γ(B) for some γ∈ Q_p. But
the block containing [3,3,3] is also invariant under
τ_(1 2), hence is invariant under the whole of
Q_p – a contradiction.

Thus at least one coordinate – the second or the third
– is homogeneous. Notice that _1, which stabilizes
B, moves the third coordinate of the solutions to the second. Hence
both the second and third coordinates must be homogeneous. 


In fact, the proof of the last lemma yields something slightly stronger.
Denote the type of a solution in Y^*(p) by some triple
in { h,e} ^3, depending on whether every coordinate
is hyperbolic or elliptic. Then, every block B as above contains
either only solutions of the same type (homogeneous in all coordinates),
or only solutions of exactly two types: one type is (h,h,h)
or (e,e,e), and the other differs from the first type
in one coordinate (the sole non-homogeneous coordinate).




  §.§.§ No correlation between two long _1-cycles with the
same first hyperbolic coordinate


We now prove Proposition <ref>
stating that if Q_p is transitive and d_p(± x)≥16√(p+1),
then ± x cannot appear twice in the same coordinate in the same
proper Q_p-block B⫋ Y^*(p). What we
actually prove is the lack of correlation between two long enough
cycles of _j with the same j-th coordinate (including
the case of two different offsets of the same cycle). The proof of
Proposition <ref>
is split to the case where x is hyperbolic (in the current subsection)
and the case it is elliptic (given in Section <ref>).

We use the following classical number-theoretic result: 

 Let f(x)∈𝔽_p[x]
be a polynomial with m distinct roots in 𝔽_p
which is not a square in 𝔽_p[x].
Then 

    |∑_s∈𝔽_p(f(s)/p)|≤(m-1)√(p).



Assume that x is hyperbolic with d_p(± x)≥16√(p+1),
and that there are two elements in the proper Q_p-block B⫋ Y^*(p)
with ± x in the first coordinate. The same arguments holds, evidently,
for every coordinate j=1,2,3.

Assume that [x,y_0,y_1] and [x,z_0,z_1]
belong to B. By Lemma <ref>,
x=ω+ω^-1 with ω∈𝔽_p^* and we
can assume |ω|=2d≥32√(p-1): otherwise, replace
x with -x and ω with -ω. Write y_0=α+β
with α,β∈𝔽_p^* so that αβ=x^2/x^2-4
and y_1=αω+βω^-1 (see Lemma <ref>).
The cycle of _1 containing [x,y_0,y_1]
is 

    [x,y_0,y_1]=[x,y_d,y_d+1],[x,y_1,y_2],…,[x,y_d-2,y_d-1],[x,y_d-1,y_d]

with

    y_j=αω^j+βω^-j.

The set {ω^j} _0≤ j≤2d-1 is the same
as the set { s^m} _s∈𝔽_p^* where
m=p-1/2d (with every element in {ω^j}
covered by p-1/2d different values of s). So as sets,

    { y_0,…,y_2d-1} ={αω^j+βω^-j} _0≤ j≤2d-1={ f_α,β(s)def=α s^m+β s^-m} _s∈𝔽_p^*.

The same holds for the cycle of _1 containing [x,z_0,z_1]
with γ,δ∈𝔽_p^* in the role of α,β,
so that z_j=γω^j+δω^-j. We may assume
that γ±α, for otherwise [x,y_0,y_1]=[x,z_0,z_1].
Moreover, if s^m=ω^j then f_α,β(s)=y_j
and f_γ,δ(s)=z_j. 

Notice that y_j and z_j are of different types (one hyperbolic
and the other elliptic) if and only if 

    ((y_j^2-4)(z_j^2-4)/p)=-1.

Since [x,y_j,y_j+1] and [x,z_j,z_j+1]
both belong to the block _1^ j(B), we derive
from Proposition <ref> that (<ref>)
cannot hold for two consecutive values of j. In the parametrization
given by s∈𝔽_p^*, this means that 

    ((f_α,β(s)^2-4)(f_γ,δ(s)^2-4)/p)=((f_αω,βω^-1(s)^2-4)(f_γω,δω^-1(s)^2-4)/p)=-1

cannot hold for any s∈𝔽_p^*.

Write 

    g_α,β(s)def=(s^m)^2(f_α,β(s)^2-4)=[(α s^2m+β)^2-4s^2m]∈𝔽_p[s],

and k_1(s)=g_α,β(s)g_γ,δ(s)
and k_2(s)=g_αω,βω^-1(s)g_γω,δω^-1(s).
Now (<ref>) is equivalent to 

    (k_1(s)/p)=(k_2(s)/p)=-1.

Denote by N_(-1,-1) the number of s∈𝔽_p
for which (<ref>) holds. Our goal
is to show that N_(-1,-1)>0, whence (<ref>)
has some solution s0, yielding a contradiction (note that s=0
is not a solution to (<ref>)). Note
that k_1(s),k_2(s)0 for every s∈𝔽_p:
indeed, g_α,β(0)=β^20, and if 0 s∈𝔽_p
and g_α,β(s)=0 then f_α,β(s)=±2
is y_j for some j, but there are no solution in X^*(p)
containing ±2 when p≡3(4). Therefore (k_1(s)/p),(k_2(s)/p)0
for s∈𝔽_p and 

    N_(-1,-1)    =    1/4∑_s∈𝔽_p(1-(k_1(s)/p))(1-(k_2(s)/p))
        =    1/4[p-∑_p∈𝔽_p(k_1(s)/p)-∑_p∈𝔽_p(k_2(s)/p)+∑_p∈𝔽_p(k_1(s)k_2(s)/p)].

For every ∅ B⊆{ 1,2}, define 

    M_Bdef=∑_s∈𝔽_p(∏_j∈ Bk_j(s)/p).

Then (<ref>) becomes 

    N_(-1,-1)=1/4[p-M_{ 1}-M_{ 2}+M_{ 1,2}].

We use Theorem <ref> to estimate the M_B's. First,
we show that none of k_1,k_2 and k_1k_2 are squares
in 𝔽_p[x]. The roots of 

    g_α,β(s)=(α s^2m+β+2s^m)(α s^2m+β-2s^m)

satisfy 

    s^m=±2±√(4-4αβ)/2α=±1±√(1-x^2/x^2-4)/α=±1±√(-4/x^2-4)/α.

As x is hyperbolic and p≡3(4), we have that
-4/x^2-4 is not a square in 𝔽_p, so 1
and √(-4/x^2-4) are linearly independent over 𝔽_p,
and ±1±√(-4/x^2-4)/α are four distinct
values for S^m, different from zero. Moreover, the polynomial
s^m-ξ is separable for 0ξ∈𝔽_p^2 because
m=p-1/2d<p. So g_α,β(s), which
is of degree 4m, has 4m distinct roots in 𝔽_p,
and in particular is not a square in 𝔽_p[x]. 

This analysis shows that g_α,β and g_γ,δ
have a common root if and only if α=±γ. Since α±γ
by assumption, k_1=g_α,βg_γ,δ and k_2=g_αω,βω^-1g_γω,δω^-1
are both separable of degree 8m. Finally, k_1k_2, of degree
16m, is also not a square in 𝔽_p[x]:
for α±αω and if α=±γω then
αω±γ.

Theorem <ref> yields that |M_{ 1}|,|M_{ 2}|≤(8m-1)√(p)
and |M_{ 1,2}|≤(16m-1)√(p).
From (<ref>) we now obtain

    N_(-1,-1)   ≥   1/4[p-2(8m-1)√(p)-(16m-1)√(p)]
        =    1/4[p-32m√(p)+3√(p)]
       m=p-1/2d=   1/4[p-16(p-1)/d√(p)+3√(p)]
       d≥16√(p-1)≥   1/4[p-√((p-1)p)+3√(p)]>3√(p)/4>0.





  §.§.§ No correlation between two long _1-cycles with the
same first elliptic coordinate


The general proof strategy for the elliptic case is the same as for
the hyperbolic case, albeit with a few extra technical details. In
the hyperbolic case, we used a parametrization of the elements of
a cycle of _1 as a function over 𝔽_p^*, which
allowed us to use Weil's bound (Theorem <ref> above). In
the elliptic case, a similar approach requires that we go over the
elements in the cyclic subgroup of size p+1 in 𝔽_p^2^ *.
The following lemma allows us to parametrize this subgroup as a function
over 𝔽_p:

The multiplicative subgroupH H≤𝔽_p^2^  *
of order p+1 satisfies

    H={θ+iη | θ,η∈𝔽_p,  θ^2+η^2=1} ={2s/1+s^2+i1-s^2/1+s^2 | s∈𝔽_p}∪{ -i}

(where i=√(-1)∈𝔽_p^2).


Note that (θ+iη)^p=θ-iη (recall that
p≡3(4) so i^p=i^4k+3=i^3=-i). So (θ+iη)^p+1=(θ+iη)(θ-iη)=θ^2+η^2.
This gives the first equality in (<ref>). A straightforward
computation yields the second equality.



We assume that x is elliptic with
d_p(± x)≥16√(p+1), and assume that there are
two elements in the proper Q_p-block B⫋ Y^*(p)
with ± x in the first coordinate. We use the notation H for
the subgroup of order p+1 in 𝔽_p^2^ *, as in
Lemma <ref>. Assume that [x,y_0,y_1] and
[x,z_0,z_1] both belong to B. By Table <ref>,
x=ω+ω^-1 with ω∈ H, and we can assume that
|ω|=2d≥32√(p+1), for otherwise replace ω
by -ω and x by -x. Let A∈𝔽_p^2 satisfy
that A^p+1=x^2/x^2-4, that y_0=A+A^p and that
y_1=Aω+A^pω^-1 (see Lemma <ref>).
The cycle of _1 containing [x,y_0,y_1]
is 

    [x,y_0,y_1]=[x,y_d,y_d+1],[x,y_1,y_2],…,[x,y_d-2,y_d-1],[x,y_d-1,y_d]

with

    y_j=Aω^j+A^pω^-j.

The set {ω^j} _0≤ j≤2d-1 is the same
as the set { h^m} _h∈ H where m=p+1/2d,
with every element in {ω^j} covered by m
different values of h. So as sets, 

    { y_0,…,y_2d-1} ={ Aω^j+A^pω^-j} _0≤ j≤2d-1={ f_A(h)def=Ah^m+A^ph^-m} _h∈ H.

The same holds for the cycle of _1 containing [x,z_0,z_1]
with C∈𝔽_p^2 in the role of A, so that z_j=Cω^j+C^pω^-j.
We may assume that C± A, for otherwise [x,y_0,y_1]=[x,z_0,z_1].
Moreover, if h^m=ω^j then f_A(h)=y_j
and f_C(h)=z_j. 

As in the proof of the hyperbolic case, we derive from Proposition
<ref> that 

    ((f_A(h)^2-4)(f_C(h)^2-4)/p)=((f_Aω(h)^2-4)(f_Cω(h)^2-4)/p)=-1

cannot hold for any h∈ H. To be able to use Theorem <ref>,
we want to reparametrize (<ref>) as polynomials
in s∈𝔽_p, using Lemma <ref>. Denote

    g_A(s)def=(1+s^2)^2m[f_A(h(s))^2-4]

where 

    h(s)=2s+i(1-s^2)/1+s^2=-i(s+i)^2/1+s^2=-i(s+i)/(s-i).

Let also k_1=g_Ag_C and k_2=g_Aωg_Cω.
Then (<ref>) is equivalent to 

    (k_1(s)/p)=(k_2(s)/p)=-1.

As in the proof of the hyperbolic case, denote by N_(-1,-1)
the number of s∈𝔽_p for which (<ref>)
holds. Our goal is to get a contradiction by showing that N_(-1,-1)>0.
Note that g_A(s)0 for s∈𝔽_p because
g_A(s)=(1+s^2)^2m(y_j^2-4)
for some y_j as above, and s± i and y_j±2.
Thus k_i(s)0 neither, and (k_i(s)/p)∈{ 1,-1}.
As in equations (<ref>)-<ref>
in the hyperbolic case, we get that 

    N_(-1,-1)=1/4[p-M_{ 1}-M_{ 2}+M_{ 1,2}],

where for ∅ B∈{ 1,2}, we define M_Bdef=∑_s∈𝔽_p(∏_j∈ Bk_j(s)/p).

We use Theorem <ref> to estimate the M_B's. First,
we show that k_1,k_2∈𝔽_p[x]. Notice
that 

    h(s)^-1=(s-i)/-i(s+i)=i(s-i)/(s+i),

so 

    g_A(s)     =    (1+s^2)^2m[f_A(h(s))+2][f_A(h(s))-2]
        =    (1+s^2)^2m(Ah(s)^m+A^ph(s)^-m+2)(Ah(s)^m+A^ph(s)^-m-2)
        =    (A[-i(s+i)^2]^m+A^p[i(s-i)^2]^m+2[1+s^2]^m)·
          ·(A[-i(s+i)^2]^m+A^p[i(s-i)^2]^m-2[1+s^2]^m).

The last expression shows that g_A(s)∈𝔽_p^2[s].
Its degree is 4m: indeed, the leading coefficient is 

    (-1)^m(A^2+A^2p)+2A^p+1-4,

and for m even this coefficient equals (A+A^p)^2-4=y_0^2-4
which is not zero since y_0±2 (see Lemma <ref>).
For m odd, this coefficient is 

    -(A+A^p)^2+4(A^p+1-1)=-y_0^2+4(A^p+1-1),

which is not zero because A^p+1-1=4/x^2-4 is not a
square in 𝔽_p when x is elliptic. 

As 𝔽_p^2=𝔽_p+i𝔽_p, we can write
g_A=g'_A+ig”_A, where g'_A,g”_A∈𝔽_p[s].
By definition, for every s∈𝔽_p, we have h=h(s)∈ H,
and 

    g_A(s)=(1+s^2)^2m[f_A(h)^2-4]∈𝔽_p

so g”_A(s)=0 for every s∈𝔽_p. Since
(g”_A)≤4m<p, we conclude that g”_A is
the zero polynomial, hence g_A(s)=g_A'(s)∈𝔽_p[s]
and so k_1,k_2∈𝔽_p[x].

Next, we wish to show that k_1, k_2 and k_1k_2 are
not squares in 𝔽_p[x]. There is
a one-to-one correspondence between the roots of g_A in 𝔽_p
and the roots of

    r_A(h)def=(Ah^2m+2h^m+A^p)(Ah^2m-2h^m+A^p),

in 𝔽_p given by 

    α   ↦    h(α)=-i(α+i)/(α-i)
    1+ih/h+i=α(h)        h,

because ± i is never a root of g_A (recall that g_A(s)∈𝔽_p[s]
has the form from (<ref>)) and -i never a root
of r_A (because r_A(h)=h^2m(f_A(h)^2-4),
-i∈ H and thus f_A(-i)=y_j for some y_j
as above, and y_j±2). It is easier to analyze the roots
of r_A than those of g_A: if h is a root of r_A
then

    h^m=±1±√(1-κ(x))/A,

where κ(x)=A^p+1=x^2/x^2-4. Now note
the following:



  * The four possible values of h^m are distinct and different from
zero (this follows from κ(x)0,1).

  * Because (m,p)=1, the four polynomials h^m-±1±√(1-κ(x))/A
are separable, so r_A has 4m distinct roots in 𝔽_p,
and so does g_A.

  * If A± C, the 4m roots of r_A are distinct from the
4m roots of r_C: certainly 1+√(1-κ(x))/A±1+√(1-κ(x))/C,
and if 1+√(1-κ(x))/A=±1-√(1-κ(x))/C
we obtain

    C     =    ± A·1-√(1-κ(x))/1+√(1-κ(x))
    κ(x)=C^p+1    =     A^p+1(1-√(1-κ(x))/1+√(1-κ(x)))^p+1=κ(x)ξ^p+1

with ξ=1-√(1-κ(x))/1+√(1-κ(x))∈𝔽_p
because 1-κ(x)=-4/x^2-4 is a square in
𝔽_p. Then ξ=±1, that is, C=± A –
a contradiction. Hence k_1=g_Ag_C and k_2=g_Aωg_Cω
are separable of degree 8m each.

  * Finally, if C± A, the polynomial k_1k_2=g_Ag_Aωg_Cg_Cω
is not a square in 𝔽_p[x]: it
is separable unless A=± Cω or Aω=± C, but the
two cannot hold simultaneously.

We can now apply Theorem <ref> to obtain the same bounds
on the M_B's as in the hyperbolic case, and from (<ref>)
we now obtain

    N_(-1,-1)   ≥   1/4[p-2(8m-1)√(p)-(16m-1)√(p)]
        =    1/4[p-32m√(p)+3√(p)]
       m=p+1/2d=   1/4[p-16(p+1)/d√(p)+3√(p)]
       d≥16√(p+1)≥   √(p)/4[√(p)-√((p+1))+3]>0.




As we noted
in Remark <ref> above, it is conceivable
that a stronger version of Proposition <ref>
holds. Let us point to the phase in the current argument that fails
in this more general setting. The simplest case to consider if that
of x,x'∈𝔽_p both hyperbolic of maximal order, so d_p(x)=d_p(x')=p-1/2.
Assume that x=ω+ω^-1 and x'=ω'+ω'^-1,
and that ω'=ω^r. Then, in the notation of Section <ref>,
if y_j=α s+β s^-1, then y_j'=α's^r+β's^-r,
and our goal is to show that (α s+β s^-1)
and (α's^r+β's^-r) cannot be of the same
type (hyperbolic/elliptic) for too many values of s∈𝔽_p^*.
The problem is that r can be of any order, and is generically of
order ≥√(p). For polynomials of such degree Weil's Theorem
<ref> is useless. 




 §.§ Deducing Alternating group from primitivity


Finally, in this section, we show how to deduce that Q_p≥(Y^*(p))
whenever Q_p is primitive. Throughout this section we denote
the symmetric group Sym(n) by S_n and
Alt(n) by A_nS_n,A_n.
Here we use the following result of Guralnick and Magaard, classifying
primitive subgroups of S_n containing an element with at least
n/2 fixed points. This theorem relies heavily on the CFSG. We adjust
the statement of the theorem to our needs – the original
statement in <cit.> is more detailed. In the
statement we use the notation Soc(G) for the
socle of the group G (see Section <ref>
for details), and the standard notation G_1≀ G_2 for the
wreath product of two groups.

 Let G≤S_n be a primitive
group, and let x∈ G have at least n/2 fixed points. Then one
of the following holds:



  * G=Aff(2,k) is the affine
group acting on 𝔽_2^ k and x is a transvection[To be sure, x is a transvection when Aff(2,k)
is embedded in GL(2,k+1) as the matrices with
bottom row (0,…,0,1).] and is, in particular, an involution. In this case x has exactly
n/2 fixed points.

  * There are r≥1, m≥5 and
1≤ k≤ m/4 such that n=mk^r, the group S_m
acts on the set Δ of k-subsets of { 1,…,m}
in the natural way, G≤ S_m≀ S_r acts on Δ^r and
Soc(G)=A_m^ r.

  * For some r≥1, n=6^r, the group
S_6 acts on Δ={ 1,…,6} by applying
an outer automorphism[Namely, for some fixed φ∈Aut(S_6)∖Inn(S_6),
the permutation σ∈ S_6 acts on Δ by σ.i=φ(σ)(i).], G≤ S_6≀ S_r acts on Δ^r and Soc(G)=A_6^ r.

  * The group G is some variant of an orthogonal
group over the field of two elements acting on some collection of
1-spaces or hyperplanes, and the element x is an involution.


The following lemma helps us rule out Case <ref>
of the above theorem with r=1.

Consider the embedding ι S_m↪ S_n
given by the natural action of the symmetric group S_m on the
set Δ of n=mk k-subsets of m, for some
2≤ k≤m/4. If, for some π∈ S_m, the image ι(π)
has a cycle of size divisible by q and a cycle of size divisible
by s for some distinct primes q and s, then ι(π)
also has a cycle of size divisible by qs.


Assume that { a_1,…,a_k}∈Δ belongs
to a cycle α of length divisible by q in ι(π).
Assume that in π, the elements a_1,…,a_k belong to
t distinct cycles: the elements a_1,…,a_ℓ_1 belong
to the cycle σ_1, the elements a_ℓ_1+1,…,a_ℓ_2
belong to the cycle σ_2, and so on (each σ_j may
contain additional elements not from { a_1,…,a_k}).
Let o_1 be the smallest power of σ_1 that maps { a_1,…,a_ℓ_1}
to itself. Define o_2,…,o_t analogously. Then, q |lcm(o_1,…,o_t).
In particular, q | o_i for some i, and so q||σ_i|.
Without loss of generality, assume q||σ_1|,
so that a_1 belongs to a cycle σ=σ_1 of π
of size divisible by q. Likewise, assume that b_1 belongs
to a cycle τ of π of size divisible by s.

Denote A={ 1,…,m}∖(σ∪τ)
(namely, A consists of the elements not belonging to the cycle
σ nor to τ). Assume first that στ. If
|A|≥ k-2, then a k-subset containing a_1,
b_1 and k-2 elements from A belongs to a cycle of ι(π)
of size divisible by qs. If |A|<k-2, then, as k≤m/4,
at least one of σ or τ has more than k element. Assume
without loss of generality it is σ. Consider the k-subset
{ b_1,a_1,π(a_1),π^2(a_1),…,π^k-2(a_1)}.
This subset belongs to a cycle of ι(π) of size
lcm(|τ|,|σ|),
which, in particular, is a multiple of qs.

Finally, assume σ=τ. Then qs||σ|.
If the length of σ is at least k+1, the k-subset { a_1,π(a_1),π^2(a_1),…,π^k-2(a_1),π^k-1(a_1)}
belongs to a cycle of ι(π) of size dividing qs.
If |σ|≤ k then A contains more than k-1
elements, and the k-subset containing a_1 and k-1 elements
from A belongs to a cycle of ι(π) of size dividing
qs.


 Let p≡3(4)
be prime. If Q_p is primitive, then Q_p≥(Y^*(p)).


Consider _1∈ Q_p. Among the p(p-3)/4
elements in Y^*(p), (p-1)(p-3)/8
belong to cycles of length at least 3 and dividing p-1/2,
and (p+1)(p-3)/8 belong to cycles
of length at least 3 and dividing p+1/2 (see Table <ref>).
Since gcd(p-1/2,p+1/2)=1, the
permutation σ=_1^(p+1)/2 fixes exactly
(p+1)(p-3)/8>|Y^*(p)|/2
elements of Y^*(p). Thus Q_p satisfies the assumptions
in Theorem <ref>. We can now rule out all options
except for Q_p=(Y^*(p)) or Q_p=Sym(Y^*(p)).

Cases <ref> and <ref> are immediately
ruled out because the permutation σ∈ Q_p is not an involution.
Case <ref> with r≥2 and Case <ref>
are immediately ruled out because |Y^*(p)|=p(p-3)/4
is not a proper power nor equal to six. It remains to consider Case
<ref> with r=1. 

Let q be some prime factor of p-1/2, and let s be
some prime factor of p+1/2. By Table <ref>,
_1 contains cycles of size divisible by q (indeed, even
of size q exactly), and of size divisible by s. However, it
does not contain any cycle of size divisible by qs. Using Lemma
<ref>, this rules out Case <ref>
from Theorem <ref> with r=1 and k≥2.
The remaining case, that of Case <ref>
with r=k=1, is precisely the case that the group in question is
either A_n or S_n. 

This finishes the proofs of Theorem <ref>
and of Corollary <ref>: Theorem
<ref> is now a
consequence of Theorem <ref> and
Proposition <ref>, while
Corollary <ref> follows from
Corollary <ref> and
Proposition <ref>.



§ STRONG APPROXIMATION FOR SQUARE FREE COMPOSITE MODULI


In this section we derive our main application of the results on the
groups Q_p and show that Γ acts transitively on X^*(n)
for various square-free composite values n=p_1⋯ p_k. First,
in Section <ref>, we prove that if Q_p_j≥Alt(Y^*(p_j))
for every j=1,…,k, then Γ acts transitively on Y^*(n).
In Section <ref> we strengthen this
result to showing that, moreover, Γ acts transitively on X^*(n),
namely, that strong approximation for the Markoff equation holds in
modulo n, thus proving Theorem <ref>.

At this point, we are able to prove Theorem <ref>
that Q_p≥Alt(Y^*(p)) for p≡3(4)
satisfying the assumptions in the statement of Theorem <ref>,
only while relying on the classification of finite simple groups (CFSG)
– see Section <ref>.
However, the CFSG is not necessary for establishing the transitivity
of Γ on X^*(n) when n=p_1⋯ p_k
and p_1,…,p_k are distinct primes satisfying the assumptions
in Theorems <ref> or <ref>
(this is Corollary <ref>).
In Section <ref> we give
an alternative proof for the transitivity of Γ on X^*(n),
which uses only the primitivity of Q_p, as in Theorem <ref>,
thus proving Theorem <ref>.
The point is that we want to provide a proof of the transitivity on
X^*(n) which can be potentially understood in full,
from basic principles, by a motivated reader. This is practically
impossible if one relies on the CFSG.



 §.§ Transitivity of Γ on Y^*(n)


Here we prove the following lemma:

Let n=p_1⋯ p_k
be a product of distinct primes. If Q_p_j≥Alt(Y^*(p_j))
for j=1,…,k, then Γ acts transitively on Y^*(n).

Moreover, Q_n, which is a subgroup of Sym(Y^*(p_1))×…×Sym(Y^*(p_k)),
contains Alt(Y^*(p_1))×…×Alt(Y^*(p_k)).


We prove the proposition by induction on k, the case k=1 being
trivial. Assume k≥2. It is enough to show that for every j=1,…,k,

    Q_n≥1×…×1×Alt(Y^*(p_j))×1×…×1.

Recall that Y^*(3)=∅, so we may assume 3∤ n.
Without loss of generality we assume that j=k. We first prove (<ref>)
assuming p_k≥5. Note that |Y^*(p_k)|≥5
(see Lemmas <ref> and <ref>),
and so Alt(Y^*(p_k)) is simple.
This group is never a composition (Jordan-Hölder) factor of Alt(Y^*(p_ℓ))
when p_k p_ℓ, because[For p odd the size of |Y^*(p)| is p(p±3)/4
as given in Section <ref>, and |Y^*(2)|=4.] |Y^*(p_k)||Y^*(p_ℓ)|.
Now consider the normal series

    Q_n=Q_n∩[Sym(Y^*(p_1))×…×Sym(Y^*(p_k))]
    
    Q_n∩[1×…×1×Sym(Y^*(p_k))]@-[u]^⊴
    
    Q_n∩[1×…×1×Alt(Y^*(p_k))]@-[u]^⊴
    
    1@-[u]^⊴

The group Q_p_k is a quotient of Q_n, and so Alt(Y^*(p_k))
a composition factor of Q_n, and thus a composition factor of
one of the quotients in (<ref>). But the upper
quotient is isomorphic to Q_p_1⋯ p_k-1, which by the
induction hypothesis has composition factors Alt(Y^*(p_ℓ))
for ℓ k,p_ℓ2 and possibly some copies of ℤ/2ℤ
coming from Sym(Y^*(p_ℓ))/Alt(Y^*(p_ℓ))
or copies of ℤ/2ℤ and ℤ/3ℤ
coming from Sym(Y^*(2)). The middle
quotient is either trivial or ℤ/2ℤ.
Thus Alt(Y^*(p_k)) must be a
composition factor of the bottom quotient, so 1×…×1×Alt(Y^*(p_k))≤ Q_n.

Finally, if p_k=2, note that |Y^*(2)|=4.
The composition factors of Alt(4) are one copy
of ℤ/3ℤ and two copies of ℤ/2ℤ.
By an argument as above, the factor ℤ/3ℤ
must belong to the bottom quotient in (<ref>).
Denote 

    Hdef=Q_n∩[1×…×1×Alt(Y^*(2))]=1×…×1× H'.

It is easy to check that H⊴ Q_n. For every g_k∈Alt(Y^*(2))
there are g_1,…,g_k-1 with g_j∈Sym(Y^*(p_j))
such that (g_1,…,g_k)∈ Q_n, thus H'⊴Alt(Y^*(2))≅Alt(4).
But the only normal subgroup of Alt(4) containing
the composition factor ℤ/3ℤ is Alt(4)
itself.





 §.§ Transitivity of Γ on X^*(n)


We now finish the proof of Theorem <ref>
and prove that if n=p_1⋯ p_k is a product of distinct
primes with Q_p_j≥Alt(Y^*(p_j))
for every 1≤ j≤ k, then Γ acts transitively on X^*(n).

We want the proof of this section to work in a slightly greater generality
than the assumption that Q_p_j≥Alt(Y^*(p_j)),
so that it applies also for the next section, where we do not rely
on the CFSG. This is part of the motivation for the following notation:

 Let n=p_1⋯ p_k
be a product of distinct primes for which Q_p_j is primitive.
We assume further that


  * The primes are ordered by the order of the rotations _i in
the groups Q_p_j, which is 

    |_1| in Q_p=
    3     p=2
    p(p^2-1)/4    p≡1(4)
    p^2-1/4    p≡3(4)
    .

For instance, 7 comes before 5. We break potential ties by putting
the larger prime first: for example, we put 11 before 5.

  * Without loss of generality, 2,5,7,11| n and so the first four
primes are 2,7,11,5 (in that order). This assumption is possible
because in these four cases, computer simulations indicate that Q_p=Sym(Y^*(p))
is the full symmetric group, so our assumptions always hold.

Furthermore, for j=1,…,k,


  * Let M_j=p_1⋯ p_jM_j denote the product
of the first j primes. 

  * Let Ω_jΩ_j⊴Γ denote
the kernel of the action of Γ on Y^*(M_j).
Note than Ω_j+1⊴Ω_j.

  * Let Λ_jΛ_j⊴Γ
denote the kernel of the action of Γ on X^*(M_j).
Note that Λ_j+1⊴Λ_j⊴Ω_j.

Finally, for every prime p, we let π_pΓ→ Q_pπ_p
denote the projection.

 

In Section <ref> we shall
prove the following lemma without relying on the CFSG:

Let
n=p_1⋯ p_k with Q_p_j primitive for j=1,…,k
as in Notation <ref>. Then, for every j=2,…,k,
the image of Ω_j-1 in Q_p_j contains a subgroup H_j≤Sym(Y^*(p_j))
satisfying:


  * H_j is transitive on Y^*(p_j)

  * H_j is isomorphic to a direct product of non-abelian simple groups[Note that we assume j≥2. Indeed, this does not hold for p_1=2:
there are no simple non-abelian subgroups inside Sym(Y^*(2))≅Sym(4).] T_1×…× T_m for some m=m(j)∈ℤ_≥1.

In particular, Ω_j-1 acts transitively on Y^*(p_j)
and Γ acts transitively on Y^*(n).

Note that if we assume that Q_p_j≥Alt(Y^*(p_j)),
the conclusion of Lemma <ref>
follows immediately from Lemma <ref>:
indeed, for p≥5, Alt(Y^*(p))
is indeed transitive on Y^*(p) and is a product of
a single non-abelian simple group. So Lemma <ref>
is already proven relying on the CFSG, or if one assumes that p_j≡1(4)
for j=1,…,k. In the remaining part of this subsection we rely
only on the conclusion of Lemma <ref>.
We assume Notation <ref> throughout.

For j=2,…,k, the group
Λ_j-1 acts transitively on Y^*(p_j).


Consider the normal series 

    Γ
    Ω_j-1@-[u]^⊴
    Λ_j-1@-[u]^⊴

and its projection on Q_p_j via π_jΓ↠ Q_p_j.
By Lemma <ref>,
π_j(Ω_j-1)≥ H_j where H_j acts transitively
on Y^*(p_j) and is a direct product of non-abelian
simple groups. As Ω_j-1 fixes Y^*(M_j-1)=Y^*(p_1)×…× Y^*(p_j-1),
its action on X^*(M_j-1) fixes every 4-block
and only permutes elements inside the 4-blocks, hence the image
of Ω_j-1 in Γ_M_j-1 is a subgroup of Sym(4)^|Y^*(p_1)|+…+|Y^*(p_j-1)|.
Hence this image is solvable of order 2^α·3^β
for some α,β∈ℤ_≥0, so all its composition
factors are either ℤ/2ℤ or ℤ/3Z.
We deduce that the quotient Ω_j-1/Λ_j-1
has only composition factors ℤ/2ℤ
and\or ℤ/3ℤ. Let 

    Ω_j-1=N_0⊵ N_1⊵…⊵ N_r=Λ_j-1

be a normal series with quotients ℤ/2ℤ
and\or ℤ/3ℤ. Note
that the index [H_jπ_j(N_1)∩ H_j]
is at most 3, but as H_j is a direct product of non-abelian
simple groups, it has no proper subgroups of index[To be sure, the reason that H=T_1×…× T_m with
T_1,…,T_m finite non-abelian simple groups has no subgroups
of index 2 or 3 is that the normal subgroups of H are B_1×…× B_m
where B_i∈{ 1,T_i} for every i (this is
standard: if N⊴ H and N∩ T_11, then 1[N,T_1]⊴ T_1,
and so [N,T_1]=T_1 and N≥ T_1). In particular,
since the smallest non-abelian simple group is Alt(5),
any proper normal subgroup of H is of index at least 60. If
K≤ H has index 2 or 3, then its core, ∩_h∈ HhKh^-1,
is proper normal subgroup of index at most 6, which is impossible.] ≤3, hence π_j(N_1)≥ H_j. By induction,
the same argument shows that π_j(N_ℓ)≥ H_j
for every ℓ, and, in particular, π_j(Λ_j-1)≥ H_j.


For j=5,…,k (so p_j≥13),
Λ_j-1 acts transitively on X^*(p_j).


Our strategy is to find a triple (x,y,z)∈ X^*(p_j)
and elements in Λ_j-1 mapping (x,y,z) to
the other elements in its 4-block: (x,-y,-z), (-x,y,-z)
and (-x,-y,z). Together with the transitivity of Λ_j-1
on Y^*(p_k) established in Lemma <ref>,
this would complete the proof. As in other places in this paper, we
deal separately with the case p_j≡1(4) and the
case p_j≡3(4), the argument in the former case
being simpler.


Case 1: p=p_j≡1(4)

Take some x∈𝔽_p hyperbolic of maximal order
(namely, the _1-cycles in C_1(x) are of length
p-1≥12 each). Since 0 has order 4, x0 and (0,x,ix)∈ X^*(p).
Let (r,s,t)∈ X^*(p) be another solution
with r elliptic. As all _1-cycles in C_1(0)
have length 4 and (p+1≡24), we get that _1^ p+1
fixes all four elements in [r,s,t] while mapping (0,x,ix)↦(0,-x,-ix).
By Lemma <ref>, there is some g∈Λ_j-1
mapping [0,x,ix]↦[r,s,t]. The element
h_1=g^-1·_1^ -(p+1)· g·_1^ p+1
is in Λ_j-1 (as Λ_j-1⊴Γ)
and maps (0,x,ix)↦(0,-x,-ix). 

Since x is maximal hyperbolic, its order is (p-1)
which is divisible by 4. Hence -x is also maximal hyperbolic.
Let now (r',s',t')∈ X^*(p) be a solution
with s' elliptic. Note that (p^2-1/4≡0 p+1)
while (p^2-1/4≡p-1/2 p-1).
Thus _2^ (p^2-1)/4 fixes all four elements
in [r',s',t'] while mapping (0,x,ix)↦(0,x,-ix)
and (0,-x,-ix)↦(0,-x,ix). By Lemma
<ref>, there is some g'∈Λ_j-1
mapping [0,x,ix]↦[r',s',t']. The element
h_1=(g')^-1·_1^ -(p^2-1)/4· g'·_1^ (p^2-1)/4
is in Λ_j-1 and maps (0,x,ix)↦(0,x,-ix)
and (0,-x,-ix)↦(0,-x,ix).


Case 2: p=p_j≡3(4)

In Proposition <ref>
below, we prove there is a solution (x,y,z)∈ X^*(p)
with both x and y elliptic of order divisible by 4. In this
case, -x has the same order as x, say this order is 4m and
note that 4m|(p+1). Let (r,s,t)∈ X^*(p)
be another solution with r hyperbolic. As p-1≡2(4),
there is a number q with (q≡2m4m) and (q≡0 p-1).
We get that _1^ q fixes all four elements in [r,s,t]
while mapping (x,y,z)↦(x,-y,-z) and
(-x,-y,z)↦(-x,y,-z). By Lemma <ref>,
there is some g∈Λ_j-1 mapping [x,y,z]↦[r,s,t].
The element h_1=g^-1·_1^ -q· g·_1^ q
is in Λ_j-1 and maps (x,y,z)↦(x,-y,-z)
and (-x,-y,z)↦(-x,y,-z). In the same
fashion, we find an element of Λ_j-1 mapping (x,y,z)↦(-x,y,-z)
and we are done. 

Modulo Proposition <ref> which
we prove at the end of this subsection, we can now complete the proofs
of Theorem <ref>
and Corollary <ref>:

 We use Notation <ref>. We need to show
that Γ acts transitively on X^*(n). We prove
that Γ acts transitively on X^*(M_j) for
j=1,…,k (recall that M_k=n). For j=4 we verified by
computer that Γ is transitive on X^*(2·5·7·11).
For j≥5, we use induction and assume that Γ acts transitively
on X^*(M_j-1). From Lemma <ref>
it follows that Γ is transitive on X^*(M_j). 


We complete the subsection with the proposition we use in the proof
of case 2 in Lemma <ref>:

For every prime p3,11
with p≡3(4), there is a solution (x,y,z)∈ X^*(p)
with two coordinates elliptic of order divisible by 4.

In the proof of Proposition <ref>
we use notation as in Section <ref>.
As 4|(p+1), if ω∈ H is not a square then 4||ω|.
Thus, it is enough to find a solution (x,y,z)∈ X^*(p)
with x,y elliptic and the corresponding ω_x,ω_y
not squares in H.

Assume y=ω+ω^-1
is elliptic (so ω∈ H). Then ω is a square in H
if and only if y+2 is a square in 𝔽_p.


Note that y+2=ω+ω^-1+2=(ω^1/2+ω^-1/2)^2.
If ω^1/2∈ H then ω^1/2+ω^-1/2∈𝔽_p.
On the other hand, if ω^1/2∉ H, then ω^(p+1)/2=-1
and so ω^1/2+ω^-1/2∉𝔽_p, because

    (ω^1/2+ω^-1/2)^p=ω^(p+1)/2ω^-1/2+ω^-(p+1)/2ω^1/2=-(ω^-1/2+ω^1/2)(ω^1/2+ω^-1/2)

(the last inequality stems from (ω^1/2+ω^-1/2)^2=y+20). 



 Fix x∈𝔽_p elliptic of maximal order (p+1). So
4||ω_x|=p+1. By Lemma <ref>,
it is enough to find y,z∈𝔽_p such that (x,y,z)∈ X^*(p)
is a solution, y is elliptic and y+2 is a non-square. Since
y elliptic means that y^2-4=(y+2)(y-2)
is not a square, we need to find y,z with (x,y,z)∈ X^*(p)
and y+2 a non-square and y-2 a square.

Imitating the notation from Section <ref>,
assume x=ω+ω^-1 with ω∈ H, choose some A∈𝔽_p^2
for which A^p+1=x^2/x^2-4, and let f_A(h)=Ah+A^ph^-1
for h∈ H. Then, 

    {(f_A(h),f_Aω(h)) | h∈ H} ={(y,z) | (x,y,z)∈ X^*(p)} .

Recall the parametrization of H∖{ -i} by
elements from 𝔽_p described in Lemma <ref>: h(s)=2s+i(1-s^2)/1+s^2=-i(s+i)/s-i.
Define g_1,g_2∈𝔽_p[s] as follows:

    g_1(s)    def=   (1+s^2)^2[f_A(h(s))+2]=(1+s^2)[2s(A+A^p)+(1-s^2)i(A-A^p)+2(1+s^2)]
    
    g_2(s)    def=   (1+s^2)^2[f_A(h(s))-2]=(1+s^2)[2s(A+A^p)+(1-s^2)i(A-A^p)-2(1+s^2)].

It is not hard to see that g_j(s)∈𝔽_p[s]:
indeed, A+A^p,i(A-A^p)∈𝔽_p. We now
show that for large enough p, there is some s∈𝔽_p
for which 

    (g_1(s)/p)=-1  and  (g_2(s)/p)=1.

Denote by N_(-1,1) the number of s∈𝔽_p
for which (<ref>) holds. Our goal is to show that for large
enough p, N_(-1,1)>0. As in the proof of Proposition
<ref>, g_1
and g_2 have no zeros inside 𝔽_p because there
are no solutions in X^*(p) involving ±2. So

    N_(-1,1)=1/4∑_s∈𝔽_p(1-(g_1(s)/p))(1+(g_2(s)/p)).

For ∅ B⊆{ 1,2}, let M_Bdef=∑_s∈𝔽_p(∏_j∈ Bg_j(s)/p)
and then (<ref>) becomes

    N_(-1,1)=1/4(p-M_{ 1}+M_{ 2}-M_{ 1,2}).

Note that 

    g_1(s)g_2(s)=(1+s^2)^4[f_A(h(s))^2-4]=(1+s^2)^2g_A(s)

where g_A(s) is defined as in Equation (<ref>)
in Section <ref> for m=1. As our analysis
in Section <ref> shows, all roots of
g_A, except for ± i, have multiplicity 1. Thus, none
of g_1, g_2 or g_1g_2 is a square in 𝔽_p[x].
Now g_1 and g_2 have each at most 4 distinct roots and by
Theorem <ref>, |M_{ 1}|,|M_⌊ 2⌋|≤3√(p).
Their product g_1g_2 has at most 6 distinct roots, hence
by Theorem <ref> |M_{ 1,2}|≤5√(p).
From (<ref>) we get

    N_(-1,1)   ≥   1/4(p-2·3√(p)-5√(p))=p-11√(p)/4.

So for p>11^2=121 we have N_(-1,1)>0 and we are
done.

For all primes p with p≡3(4), p≤121 and
p3,11, we verified by a computer there is a solution (x,y,z)∈ X^*(p)
with x,y elliptic and of order divisible by 4. For example,
one can take (3,3,3)∈ X^*(7), (6,6,8)∈ X^*(19),
(3,3,3)∈ X^*(23) and (4,4,9)∈ X^*(31).




 §.§ Transitivity without the classification


In this section we prove Theorem <ref>
concerning the transitivity of Γ in square free composite
moduli without relying on the CFSG. We are going to use some strong
results from the theory of permutation groups, mostly revolving around
O'Nan-Scott theorem. While strong, the proofs of these results are
completely contained in the book <cit.> and
are not more than a few-page-long each. We stress that if all primes
in the decomposition of n are 2 or (14), then
already the proof in the previous sections does not rely on the CFSG. 

More concretely, let n=p_1⋯ p_k be a product of distinct
primes, and we assume that Q_p_j is a primitive permutation
group in its action on Y^*(p_j) for every j=1,…,k.
Our goal is to show then that Γ acts transitively on X^*(n).
It is enough to prove Lemma <ref>
above, as we already showed in Section <ref>
how it yields the conclusion we seek. Throughout this subsection we
assume Notation <ref>.

The CFSG-free proof of Lemma <ref>
uses the important concept of the socle:

A minimal normal subgroup of a non-trivial group
G is a normal subgroup K1 of G which does not contain
properly any other non-trivial normal subgroup of G. The socle
of G, denoted (G)(G),
is the subgroup generated by the set of all minimal normal subgroups
of G. Note that (G) is generated by normal subgroups
of G and thus (G) G.

For example, if m≥5 then (Sym(m))=(Alt(m))=Alt(m).
In contrast, (Sym(4))=(Alt(4))={ 1,(12)(34),(13)(24),(14)(23)}. 

 Let G≤Sym(n)
be a primitive subgroup. Then exactly one of the following holds:


  * For some prime p and some integer d, the group G is permutation
isomorphic[Two permutation groups are permutation isomorphic if they are the
same permutation groups except for, possibly, the labeling of the
points in the sets they act on.] to a subgroup of the affine group Aff(p,d)
acting on 𝔽_p^ d, so, in particular, n=p^d. In
this case, (G) is a regular[A permutation group H≤Sym(n) is called regular
if it is sharply transitive. Namely, it is transitive and free. In
other words, it is transitive and of order n. The name originates
from the observation that such subgroups are obtained as the (left
or right) regular representation of order-n groups.] elementary abelian subgroup of order p^d.

  * (G)=K_1× K_2 where K_1,K_2 G
are minimal normal subgroups of G, which are regular, non-abelian
and permutation isomorphic to each other. Moreover[For G a group and K≤ G a subgroup, C_G(K)={ g∈ G | gk=kg ∀ k∈ K}
is the centralizer of K in G.], C_G(K_1)=K_2 and C_G(K_2)=K_1.
In addition, K_1≅ K_2≅ T^m for some finite simple
non-abelian group T and some m∈ℤ_≥1.

  * (G) is a minimal normal subgroup of G. Moreover,
C_G((G))=1 and (G)≅ T^m
for some finite simple non-abelian group T and some m∈ℤ_≥1.




 If G≤Sym(n)
is a primitive permutation group and 1 H G
is a non-trivial normal subgroup, then H is transitive.


If p≥5 is prime and
Q_p is primitive, then (p)(p)def=(Q_p)
acts transitively on Y^*(p) and is a direct product
of non-abelian simple groups.


Transitivity follows from Theorem <ref>
and the fact that the socle is a normal subgroup. Case (1) of Theorem
<ref> is ruled out because |Y^*(p)|=p(p±3)/4
is not a prime power (or, alternatively, because Aff(p,d)
has no non-identity elements fixing more than half of the points,
such as _1^p(p+1)/2∈ Q_p). So either Q_p
falls into case (2) or it falls into case (3).

We also use the following result giving strong limitations on primitive
groups:

 Let GSym(n),
GAlt(n), be a primitive permutation group. 


  * If G is not 2-transitive then |G|<exp{ 4√(n)(ln n)^2}.

  * If n≥216 and G is 2-transitive and contains a section[A section of a group is some quotient of a subgroup.]
isomorphic to Alt(k), then k<6ln n.



Let
p and q be distinct primes with Q_p and Q_q primitive,
and such that p precedes q in the order defined in Notation
<ref>. Then Q_pq≥1×(q)
(sitting inside Sym(Y^*(p))×Sym(Y^*(q))).


Recall that the primes are sorted by the order of rotation elements.
So if o_p (o_q, respectively) is the order of _1
in Q_p (Q_q, respectively) then o_p≤ o_q. 


Case 1: o_p<o_q

If the inequality is strict, then the image of g=_1^o_p∈Γ
in Q_p is the identity whereas its image g in Q_q
is not. By Corollary <ref>, (q)
falls under one of cases (2) or (3) from
Theorem <ref>.

Assume first that (q) falls under case (3). Since
C_Q_p((q))=1, there is some h∈(q)
not commuting with g∈ Q_q, so e[g,h]=ghg^-1h^-1∈(q)∩π_q((Γ↠ Q_p)).
Since (q) is a minimal normal subgroup of Q_q,
it is generated by the conjugates of [g,h]
in Q_q, all of which also belong to π_q((Γ↠ Q_p)).
Thus (q)≤π_q((Γ↠ Q_p)).

Now assume that (q) falls under case (2). Since
regular subgroups of Sym(n) are obtained as
the (left or right) regular representation of a group of order n,
every element of a regular permutation group has all its cycles with
equal length. Since _1∈ Q_q contains cycles of coprime
lengths, no non-trivial power of it can belong to a regular subgroup,
so g=_1^o_p∉ K_1∪ K_2. So there
are h_1∈ K_1 and h_2∈ K_2 not commuting with g.
Consider h=h_1h_2∈ K_1× K_2=(q).
Then [g,h]=([g,h_1],[g,h_1])∈ K_1× K_2=(q)
belongs also to π_q((Γ↠ Q_p))
but not to K_1∪ K_2. The only normal subgroups of Q_p
which are contained in K_1× K_2 are 1,K_1,K_2 and
K_1× K_2. Hence K_1× K_2 is generated by the
conjugates in Q_q of [g,h], all of which
belong to π_q((Γ↠ Q_p)).
Thus (q)≤π_p((Γ↠ Q_p)).


Case 2: o_p=o_q

We are left with the rare case[In fact, the only such case with p<1,000,000 is p=5.]
that o_p=o_q, as in p=11 and q=5. In this case p>q,
p≡3(4), q≡1(4) and (p^2-1)=q(q^2-1).
In particular, as Q_q is primitive, it contains the full alternating
group Alt(Y^*(q)) by the CFSG-free
Theorem <ref>. We claim that Q_p has no composition
factor isomorphic to Alt(Y^*(q)).
Using this, we can finish as in the proof of Lemma <ref>:
indeed, consider the following normal series of Q_pq

    1⊴ Q_pq∩[1×Alt(Y^*(q))]⊴ Q_pq∩[1×Sym(Y^*(q))]⊴ Q_pq.

Since Q_q is a quotient of Q_pq, Alt(Y^*(q))
is a composition factor of Q_pq, so it has to be a composition
factor of one of the quotients in (<ref>).
The rightmost quotient is Q_p which we show below has no composition
factor isomorphic to Alt(Y^*(q)).
The second quotient is ℤ/2ℤ or trivial.
Thus, the leftmost quotient contains Alt(Y^*(q))
as a composition factor, namely, Q_pq≥1×Alt(Y^*(q)),
and we are done as (q)=Alt(Y^*(q)).

So we have left to show that Q_p has no composition factor isomorphic
to Alt(Y^*(q)). This is certainly
the case if Q_p≥Alt(Y^*(p))
(as in the case p=11,q=5). So assume Q_pAlt(Y^*(p))
and proceed using Theorem <ref>. 

First, assume that Q_p is not 2-transitive. Asymptotically,
its order is smaller than that of Alt(Y^*(q)):
indeed, if n=|Y^*(p)|=p(p-3)/4
then n≈ q^3, and so by Theorem <ref>,

    ln|Alt(Y^*(q))|     =    ln(1/2·(q(q+3)/4)!)≈ q^2ln q
    ln|Q_p|    ≤    4√(n)(ln n)^2≈ q^1.5(ln q)^2.

In fact, this asymptotic reasoning starts taking effect for q≥203,897,
but for smaller values of q there are no cases for which o_p=o_q
except for q=5 (this was easily verified by computer). 

Finally, assume that Q_p is 2-transitive. Then, not only does
it not have a composition factor isomorphic to Alt(Y^*(q)),
it does not even have a section isomorphic to it: since p(p-3)/4≥216,
Theorem <ref> says that k=q(q+3)/4<6lnp(p-3)/4.
This is impossible when q≥13. 

We can now finish our CFSG-free proof of Lemma <ref>.

 Assume n=p_1⋯ p_k is a product of distinct primes with
Q_p_1,…,Q_p_k primitive and p_1,…,p_k
ordered as in Notation <ref>. We need to
show that for every j=2,…,k, the image of Ω_j-1
in Q_p_j, π_p_j(Ω_j-1) contains
a subgroup H_j≤Sym(Y^*(p_j))
which is transitive and isomorphic to a direct product of non-abelian
simple groups. We show that π_p_j(Ω_j-1)≥(p_j),
which is enough by Corollary <ref>.

Without loss of generality, it is enough to prove this when j=k.
As (p_k)≅∏_i=1^mT_i with T_1,…,T_m
non-abelian simple groups, each of them satisfies [T_i,T_i]=T_i.
Hence for any t∈ℤ_≥1 there is a sequence of elements
g_1,…,g_t∈(p_k)
so that the nested commutator 

    […[[g_1,g_2],g_3],…,g_t]

has non-trivial projection in each of the T_i's. Choose such
a sequence of length t=k-1. By Lemma <ref>,
for every i=1,…,k-1, there is an element g_i∈Γ
with π_p_i(g_i)=1 and π_p_k(g_i)=g_i.
The element 

    g=[…[[g_1,g_2],g_3],…,g_k-1]∈Γ

satisfies then that π_p_i(g)=1 for all i=1,…,k-1,
whereas π_p_k(g)∈(p_k) in not
contained in any proper normal subgroup of (p_k).
Hence every element of (p_k) is a product of conjugates
of π_p_k(g), and we obtain that π_p_k(Ω_k-1)≥(p_k).




§ T_2-SYSTEMS


This section explains why Theorem <ref> is
equivalent to Theorems <ref> and <ref>.
Namely, if we let Σ_2,-2(p) denote the set of
PSL(2,p)-defining subgroups of _2 with
associated trace -2, our goal here is to show:


  * A one-to-one correspondence between Y^*(p) and Σ_2,-2(p),
and

  * An isomorphism between Q_p, the group of permutations induced
by the action of Γ on Y^*(p), and the group
of permutations induced by the action of Aut(_2)
on Σ_2,-2(p).

First, let us define Σ_2,-2(p) properly. For
A,B∈PSL(2,p), define 

    (A,B)def=( A, B, AB)∈𝔽_p^ 3/∼,

where ∼ is the equivalence of changing the sign of two of the
coordinates (each of A and B is a well-defined matrix in SL(2,p)
up to a sign). Assume ⟨ A,B⟩ =PSL(2,p),
and let φ_2↠PSL(2,p)
be the epimorphism mapping the generators a and b of _2
to A and B, respectively. The kernel N=φ is a PSL(2,p)-defining
subgroup of _2, and define

    (N)def=(A,B).

Recall that Σ_2(G) denotes the set of G-defining
subgroups of _2.

The map Σ_2(PSL(2,p))→𝔽_p^ 3/∼
is well-defined.


Let G=PSL(2,p). Given N∈Σ_2(G),
all epimorphisms _2↠ G with kernel N are
obtained one from the other by post-composition with some automorphism
from Aut(G). But every automorphism of G
is obtained by a conjugation by some element from PGL(2,p).
Evidently, such conjugation does not effect the image of  on
the images of the generators a and b of _2.

Recall that ([A,B])=Q( A, B, AB)
where Q(x,y,z)=x^2+y^2+z^2-xyz-2. Thus, for N∈Σ_2(PSL(2,p)),
the element

    Q(N)def=Q((N))∈𝔽_p

is well-defined, and we denoteΣ_2,-2(p)

    Σ_2,-2(p)def=Q^-1(-2)⊆Σ_2(PSL(2,p)).

Note that, by definition, for every N∈Σ_2,-2(p)
the triple (N) is (an equivalence class up to sign
changes of) a solution to the Markoff equation (<ref>)
over ℤ/pℤ.

The map |_Σ_2,-2(p) is a bijection from
Σ_2,-2(p) to Y^*(p).


Consider the map SL(2,p)×SL(2,p)→𝔽_p^ 3
defined as in (<ref>). By <cit.>,
if (x,y,z)∈𝔽_p^ 3 is the image of some
generating pair in SL(2,p), then every two
pairs in ^-1((x,y,z)) are
conjugated one to the other by an element g∈SL(2,𝔽_p).
Since these pairs are generating, this conjugation by g is an automorphism
of SL(2,p). As every automorphism of SL(2,p)
is also an automorphism of PSL(2,p), we obtain
that 

    |_Σ_2,-2(p)Σ_2,-2(p)→𝔽_p^ 3/∼

is injective.

By <cit.>, the map 
is surjective. The analysis in <cit.>
shows that the only triple (x,y,z)∈𝔽_p^ 3
with Q(x,y,z)=-2 which does not correspond to generating
pairs is[To see that (0,0,0) is not associated with a generating
pair, note that if A∈PSL(2,p) has trace 0,
then A is an involution. If both A and B are involutions,
then ⟨ A,B⟩ is a dihedral group, which
is a proper subgroup of PSL(2,p). ] (0,0,0). This completes the proof of the claim.

We have left to show the isomorphism of Q_p and the permutation
group induced by Aut(_2) on Y^*(p)≅Σ_2,-2(p).
Recall that Q_p=⟨τ_(12),τ_(23),R_3⟩.
For _2=(a,b), Aut(_2)
is generated by the following Nielsen moves[We deliberately copy the notation for these Nielsen moves from <cit.>.]:
r(a,b)↦(a^-1,b), s(a,b)↦(b,a)
and t(a,b)↦(a^-1,ab). The induced
action of these three automorphisms on Y^*(p) is easily
seen to be the same action given by R_3, τ_(12)
and τ_(23), respectively. 



§ APPENDIX






§ ON THE ORDER OF A QUADRATIC INTEGER MODULO MOST PRIMES

BY DAN CARMON


Throughout this appendix, we use the notation f≪ g to mean that
there exists an absolute constant C>0 for which f≤ Cg for
all valid values of the implicit variables. The similar notation f≪_ag
means there exists a function C=C(a)>0 for which f≤ Cg. The
notation f≍ g is shorthand for “f≪ g and g≪ f”.



 §.§ The main claim


Let a∈ℚ(√(D)) be a fixed quadratic integer with
norm 1 and absolute value |a|>1 (e.g. a=3+√(5)/2).
For primes p∤ D, consider the residue a̅=(a p),
as an element of either 𝔽_p or 𝔽_p^2,
depending on whether D is a quadratic residue modulo p. In both
cases there are two possible choices for a̅, but its order
o_p(a), which is the smallest positive integer satisfying a̅^o_p(a)=1∈𝔽_p^2
is well-defined. Let π(x)=#{p≤ x:p– prime}π(x)
be the prime counting function. We prove the following claim:

 For any constant C≥1, 

    #{p≤ x:o_p(a)≤ C√(x)}≪_aπ(x)/(log x)^δ(loglog x)^3/2-δ,

where δ is the Erdős-Tenenbaum-Ford constant, 

    δ=1-1+loglog2/log2=0.086071....

In particular, the set of primes with o_p(a)>C√(p) has relative
density 1.




 §.§ Proof outline


Proposition <ref> follows from the combination
of two sub-lemmas: 

 Let α=α(x) tend to infinity arbitrarily
slowly with x, and let y=√(x/α). Then 

    #{p≤ x:o_p(a)≤ y}≪_aπ(x)/α.




 Let α,y be as in the previous Lemma. Define
z=C√(x), and u_0=logα/log x. Suppose further
that α∈(4/C^2,√(x)/C).
Then 

    #{p≤ x:∃ d∈(y,z], p≡±1 d}≪ u_0^δ(log2u_0)^-3/2π(x).


Indeed, since a has norm 1, o_p(a) is always a factor of either
p-1 when D is a quadratic residue modulo p, or of p+1
when D is a non-quadratic residue, i.e. p≡±1o_p(a)
in either case. Thus o_p(a)≤ C√(x) implies that p is
either included in the set of the first lemma if o_p(a)≤ y,
or in the set of the second lemma if o_p(a)∈(y,z]. Choosing
the optimal value 

    α=(log x)^δ(loglog x)^3/2-δ

yields the claimed value in the right hand side of both lemmas.



 §.§ Proofs of the lemmas


 The following proof is an adaptation of an argument from Erdős
and Murty <cit.>, in which only integral values
a and a specific choice of α were considered.

For every k≥1 define A_k=a^k-a^-k/√(D).
Note that A_k is always an integer, with |A_k|<|a|^k,
and that o_p(a)=k implies p| A_k. Define 

    B_y=∏_k=1^⌊ y⌋A_k,

so that o_p(a)≤ y implies p| B_y. We now observe that

    log B_y=∑_k=1^⌊ y⌋log A_k≤∑_k=1^⌊ y⌋klog|a|≪_ay^2=x/α,

and on the other hand 

    log B_y   ≥∑_p| B_ylog p≥∑_p : o_p(a)≤ ylog p≥∑_
    
    o_p(a)≤ y
    log√(x)
        =12log x·#{√(x)<p≤ x:o_p(a)≤ y},

whence 

    #{p≤ x:o_p(a)≤ y}≤π(√(x))+2log B_y/log x≪_a2/αx/log x≪π(x)/α.




 This lemma is a direct application of results due to Ford <cit.>.
We cite the relevant definitions and theorems. Ford's main object
of study is the function 

    H(x,y,z)=#{n≤ x:∃ d∈(y,z],d| n}.

We are particularly interested in the specialized function 

    H(x,y,z;P_λ)=#{n≤ x:n∈ P_λ,∃ d∈(y,z],d| n},

where P_λ={p+λ:p– prime} is a set of shifted
primes, and more specifically only for λ=±1.

In <cit.>, Ford estimates H(x,y,z)
for all possible choices of y≤ z≤ x. The relevant case for
our choice of y,z is the third subcase of case (v), wherein x,y,z
are all large, y≤√(x), and z∈[2y,y^2], all of which
are immediately validated for our values, due to the constraint on
α. For this case, the theorem states 

    H(x,y,z)/x≍ u^δ(log2u)^-3/2,

where u is the number satisfying z=y^1+u, or equivalently

    u=log(z/y)/log y=log(C√(α))/log(√(x/α))=logα+2log C/log x-logα≍logα/log x=u_0.

In <cit.>, Ford estimates H(x,y,z;P_λ),
for any fixed non-zero λ. The behaviour of the function is
determined by whether z is greater or lesser than y+(log y)^2/3.
The constraint on α implies z≥2y, so we are certainly
in the regime of z≥ y+(log y)^2/3, in which the theorem yields

    H(x,y,z;P_λ)≪_λH(x,y,z)/log x.

Combining the estimates (<ref>),(<ref>),(<ref>)
yields (<ref>), proving the lemma.



alpha


Chen Meiri,

Department of Mathematics,

Technion - Israel Institute of Technology

Haifa 32000 Israel

chenm@tx.technion.ac.il


Doron Puder, 

School of Mathematical Sciences,

Tel-Aviv University,

Tel-Aviv 69978 Israel

doronpuder@gmail.com


Dan Carmon, 

School of Mathematical Sciences,

Tel-Aviv University,

Tel-Aviv 69978 Israel

dancarmo@post.tau.ac.il
