Permutations with orders coprime to a given integer
John Bamberg S. P. Glasby Scott Harper Cheryl E. Praeger















 












Myenumerate






[enumerate]label=(*)


definition
definitionDefinition
remark[definition]Remark
plain
conjecture[definition]Conjecture
question[definition]Question
theorem[definition]Theorem
proposition[definition]Proposition
lemma[definition]Lemma
corollary[definition]Corollary



scaled y ticks=false







J. Bamberg, S. P. Glasby, C. E. Praeger: Centre for the Mathematics of Symmetry and Computation, University of Western Australia, 35 Stirling Highway, Perth 6009, Australia.
E-mail: 



 

S. Harper: School of Mathematics, University of Bristol, Bristol, BS8 1TW, UK.
E-mail: 



Acknowledgements: The work on this paper began at the 2018 Research Retreat of the Centre for the Mathematics of Symmetry and Computation. The third author is grateful for the Cecil King Travel Scholarship from the London Mathematical Society and the hospitality of the University of Western Australia; he also thanks the Engineering and Physical Sciences Research Council and the Heilbronn Institute for Mathematical Research for their financial support. The problem forms part of an Australian Research Council Discovery Project.2010 Math Subject Classification: 20B30, 05A15, 68W20.


 
Permutations with orders coprime to a given integer]Permutations with orders
 coprime to a given integer

[2010]






Let m be a positive integer and let ρ(m,n) be the proportion of permutations of the symmetric group (n) whose order is coprime to m. In 2002, Pouyanne proved that
ρ(n,m)n^1-ϕ(m)/m∼κ_m where κ_m is a complicated
(unbounded) function of m.
We show that there exists a positive constant C(m) such that,
for all n ≥ m,

    C(m) (n/m)^ϕ(m)/m-1≤ρ(n,m) ≤(n/m)^ϕ(m)/m-1

where ϕ is Euler's totient function. 


[
    Cheryl E. Praeger
    December 30, 2023
=====================





§ INTRODUCTION

In a series of papers between 1965 and 1972, Erdős and Turán initiated a systematic study of probabilistic aspects of group theory (see, for example, <cit.>). One topic which has been of particular interest since this time is the distribution of element orders in finite symmetric groups, and their most relevant work for us on this topic began in  <cit.> where they studied the proportion p_ m(n) of elements in (n) with no cycle of length divisible by a fixed prime m. Erdős and Turán  obtained an explicit formula for p_ m(n) and determined the limiting proportion, as n grows, as

    p_ m(n) = k(m) (n/m)^-1/m + O(n^-1-1/m),

where k(m) = Γ(1-1/m)^-1, noting that π^-1/2≤ k(m) <1 <cit.>. Although m was assumed to be a prime in <cit.>, the formula for p_ m(n) in (<ref>) holds for an arbitrary positive integer m, see <cit.>, and their asymptotic arguments can be extended to give explicit  convergence bounds <cit.>, again for arbitrary m. These explicit bounds, together with analogous results for alternating groups <cit.>, were used to analyse algorithms for constructing transpositions and 3-cycles <cit.>, procedures used as components of the constructive recognition algorithms for black-box alternating and symmetric groups in <cit.>. Many other authors have also considered the proportion p_ m(n), see for example <cit.> and the discussion in <cit.>.  

Let us introduce the specific topic of interest for this paper. For positive integers n and m, let R(n,m) be the set of elements of (n) whose order is coprime to m, and write

    ρ(n,m) |R(n,m)|/n!.

The proportion ρ(n,m) is equal to the proportion  p_ m(n) of Erdős and Turán discussed above if and only if m is a prime power.  Moreover, in <cit.>, Erdős and Turán demonstrate that if n is sufficiently large and m is the product of two distinct primes p and q satisfying (logn)^3/4≤ p,q ≤ 10logn/loglogn, then

    ρ(n,m) = n^-1/p-1/q(1+O(log^-1/2n)).


Pouyanne <cit.> used a singularity analysis
on the generating function C(x)=∑_i≥  0ρ(n,m)X^m for ρ(n,m)
to give an asymptotic value of ρ(n,m) for arbitrary m. He gives a
nice proof that ρ(n,m)n^1-ϕ(m)/m∼κ_m where κ_m is a
function of m involving Gamma and Möbius functions,
see (<ref>). Unfortunately the elusive
nature <cit.> of
κ_m makes it hard to apply this result.
In particular, upper and lower bounds ρ(n,m) cannot be extracted from
the asymptotics in <cit.>, and our major contribution is to
bound the quantity λ_m:=κ_m/m^1-ϕ(m)/m, where ϕ is
Euler's totient function.
We need these bounds for applications to randomised
(1-sided Monte Carlo) permutation group algorithms where explicit bounds
on the probability/proportions are required to assign explicit upper
bounds on the probability that the algorithm returns an incorrect answer,
i.e. to prove that it is a Monte Carlo algorithm. Examples of the
use of such probability bounds for exhibiting a Monte Carlo algorithm,
and analysing its complexity, are given for example in <cit.>.
Specifically, our algorithm for testing whether a subgroup ⟨ X⟩ of (n) contains the alternating group (n) either returns
the answer “Yes” with no chance of error, or returns an answer “No” with
a (preset arbitrarily) small probability of error, say 10^-6.

The set π(m) of prime divisors of m is significant as ρ(n,m)=ρ(n,m') and ϕ(m)/m=ϕ(m')/m' when π(m)=π(m'). Given this fact, we will henceforth assume that m is square-free. We implicitly also assume that the primes in π(m) are
at most n, since ρ(n,m)=ρ(n,mp) for primes p>n. With this in mind,
and observing that ϕ(m)/m-1≤ 0, we now present our main result. 


Let m be a positive square-free integer. There exists a positive constant C(m) such that, for all n ≥ m,

    C(m) (n/m)^ϕ(m)/m-1≤ρ(n,m) ≤(n/m)^ϕ(m)/m-1.



The exponent ϕ(m)/m-1 in Theorem <ref> is negative, and hence ⌈n/m⌉^ϕ(m)/m-1≤ (n/m)^ϕ(m)/m-1 and ⌊n/m⌋^ϕ(m)/m-1≥ (n/m)^ϕ(m)/m-1, for n≥ m.  Thus, in order to prove Theorem <ref>  it is sufficient to prove that 

    C(m) ⌊n/m⌋^ϕ(m)/m-1≤ρ(n,m) ≤⌈n/m⌉^ϕ(m)/m-1.

We prove these inequalities in Section <ref>. In fact the upper bound holds for n≥1. We conclude with a conjecture in Section <ref> based on computational evidence.

First we make a few remarks concerning the constant C(m) and links between Theorem <ref> and the results  (<ref>) and (<ref>).


  * We prove Theorem <ref> with the constant

    C(m) min{ρ(n, m) | m ≤ n ≤ 2m-1 }.

In particular, if m is a prime then C(m) = 1-1/m.


  * If an element of (n) has order coprime to m, then the length of each of its cycles is certainly not divisible by m. Hence, we have the upper bound ρ(n,m)≤ p_ m(n)=∏_i=1^⌊n/m⌋(1-1/im) by <cit.>. However, this bound grows too quickly as remarked on in (c).


  * If m is prime, then the exponent is ϕ(m)/m-1 = m-1/m-1 = -1/m, and we obtain from  Theorem <ref> the result (<ref>), apart from determining the constant k(m). In fact, the exponent  ϕ(m)/m-1 is equal to  -1/m if and only if m is a power of a prime, and in all other cases the exponent is strictly less than   -1/m. In other words, if m is divisible by at least two primes then ρ(n,m) grows more slowly, as n increases, than p_ m(n) does. 


  * Suppose m=pq where p<q are primes. Then ϕ(m)/m-1 = -1/p-1/q + 1/pq and Theorem <ref> appears to differ from (<ref>) by a multiplicative factor of n^1/pq. However, in our context m is fixed and n increases without bound, whereas Erdős and Turán assume for (<ref>) that both p and q are bounded:

    (log n)^3/4≤ p<q ≤10log n/loglog n.

Thus, both m and n are assumed to increase in (<ref>). The apparent inconsistency can be resolved by showing that (<ref>) implies

    n^1pq = 1 + O((log n)^-1/2).

For an upper bound, from (<ref>) we have

    n^1/(pq)≤ n^(log n)^-3/2 = n^(log n)^-1 (log n)^-1/2
    = e^(log n)^-1/2 = 1 + O((log n)^-1/2).

For a lower bound we show 

    n^1pq≥ n^(loglog n)^2/(100(log n)^2)≥ 1 + O((log n)^-1/2).

Establishing the last inequality is the same as bounding (above) the function

    f(n)  (n^x(log n)^-1 - 1)(log n)^1/2     x=(loglog n)^2/100log n.

Rewriting f(n) using the identity n^(log n)^-1=e gives

    f(n) = (e^x-1)(log n)^1/2.

Since x→ 0 as n→∞, we can choose n large enough so that x<1/2. However,
0⩽ e^x-1< 2x for 0⩽ x<1/2 so

    0≤ f(n) < 2x (log n)^1/2 = (loglog n)^2/50 (log n)^1/2.

Hence f(n)→ 0 as n→∞, so f(n) is bounded above as claimed.


  * The proofs by  Erdős and Turán of results such as (<ref>) and (<ref>) draw heavily on tools from complex analysis. In <cit.>, Erdős and Turán state that it would be desirable to obtain a proof of (<ref>) using more direct means:

     “A more direct (real-variable or algebraic) approach to the determination of this coefficient would be desirable.”

The proof of Theorem <ref> is principally algebraic: we determine and exploit a recursive formula for ρ.


  * In a different direction, restricting m to a prime number and determining the proportion ρ(G,m) of elements of an arbitrary finite group G whose order is coprime to m has been the subject of papers by many authors. For example, see <cit.> when G is a permutation group of degree n and see <cit.> when G is a finite simple classical group.


  * The set (n)^(m)={π^m|π∈(n)} of mth powers, and
  its cardinality, have been extensively studied, e.g. <cit.>. As
  every permutation of order coprime to m is an mth power, we have
  R(n,m)⊆(n)^(m). The containment is proper in general,
  for example
  (1,3)(2,4)∈(4)^(2)∖ R(4,2). However, if m divides
  the exponent e of (n) and (m,e/m)=1, then R(n,m)=(n)^(m).
  Hence, one may guess that |(n)^(m)| and |R(m,n)| have
  the same asymptotic density. This follows from <cit.>
  and <cit.>.






§ PROOF OF THEOREM <REF>
 
For the remainder of the paper, fix m as a square-free positive integer. Recall that R(n,m) is the set of elements in (n) of order coprime to m. Since m is fixed we will write  R(n):= R(n,m) and similarly (except in some formal statements) we write ρ(n):=ρ(n,m). Additionally, we denote the greatest common divisor of integers c and d by (c,d), and we write   

    Φ = Φ(m) { 1 ≤ i ≤ m | (i,m)=1 },
 
noting that ϕϕ(m) = |Φ|.

The following lemma generalises <cit.>.  For convenience, we adopt the convention that ρ(0) = 1.


The following recursive formula holds for integers n ≥ m>0, 

    nρ(n) = (n-m)ρ(n-m) + ∑_k ∈Φ^ρ(n-k).




The permutations x ∈ R(n) can be enumerated according to the length k of the cycle containing the point 1. The number of choices for the cycle (1,i_2,…,-1pt i_k) of x is (n-1)(n-2)⋯(n-k+1).  Note that (k,m)=1 and that the permutation induced by x on the n-k points outside {1,i_2,…,i_k} lies in R(n-k). Thus

    |R(n)| = ∑_1 ≤ k ≤ n 
     (k,m)=1(n-1)(n-2)⋯(n-k+1) |R(n-k)|.

Dividing this equation by (n-1)!, and noting that |R(a)|=a!ρ(a) for all a ∈, we obtain

    nρ(n) = ∑_1≤ k ≤ n 
     (k,m)=1ρ(n-k).

Replacing n above with n-m and observing that
(k+m,m)=(k,m) yields

    (n-m)ρ(n-m) = ∑_1≤ k ≤ n-m 
     (k,m)=1ρ(n-m-k) = 
      ∑_m+1≤ k ≤ n 
     (k,m)=1ρ(n-k).

Subtracting these two equations gives

    nρ(n) - (n-m)ρ(n-m) = ∑_k ∈Φρ(n-k).



We now present a technical lemma which will be of use in the proof of Theorem <ref>. 


Let y and a be real numbers such that -1 < y < 0 and a ≥ 2.
Then 

    0 < 1 - y+1/a(1-y/a) ≤(a-1/a)^y+1 
    < 1- y+1/a.




Let x=-1/a and x_0=-1/2, and note that x_0 ≤ x < 0. We seek upper and lower bounds for f(x) := (1+x)^y+1 = (a-1/a)^y+1. As |x|<1, the binomial series below converges absolutely

    f(x) = ∑_i ≥ 0y+1i x^i.

Since -1<y < 0, for each i>0, the binomial coefficient 

    y+1i = (y+1)y(y-1)⋯(y-(i-2))/i!
 
has i-1 negative factors. Hence, the product y+1ix^i is 
negative for each i>0. Therefore, 

    f(x) = ∑_i ≥ 0y+1i x^i < 1 + (y+1)x
    = 1 - y+1/a

yielding the desired upper bound.

Now we consider the lower bound. Temporarily we assume that i ≥ 2. Since (y-1)⋯(y-(i-2)) has i-2 negative factors, the product (y-1)⋯(y-(i-2))x^i-2 is positive for each i≥ 2. Hence,

    0 < ∏_j=1^i-2 (y-j)x = ∏_j=1^i-2 (j-y)(-x) ≤∏_j=1^i-2 (j+1)(-x_0) =(i-1)!(-x_0)^i-2.

This in turn shows that

    0 > y+1ix^i = (y+1)y(y-1)⋯(y-(i-2))x^i/i!≥(y+1)y(-x_0)^i-2x^2/i.

Taking the terms with 0 ≤ i < 2, together with the above lower bound for the sum of the terms with i ≥ 2, gives

    f(x)   ≥1+(y+1)x+∑_i≥2(y+1)y(-x_0)^i-2x^2/i
       =1+(y+1)x+(y+1)y/x_0^2(∑_i≥2(-x_0)^i/i)x^2.

Now ∑_i ≥ 1(-x_0)^i/i = -log(1+x_0), and hence, 
since x_0 = -1/2, we have 

    x_0^-2∑_i≥2(-x_0)^i/i=x_0^-2(x_0-log(1+x_0)),

and this lies in the open interval (0,1). Then since (y+1)yx^2 < 0, we obtain the desired lower bound

    f(x)=(1+x)^y+1>1+(y+1)x+(y+1)yx^2 = 1 - y+1/a(1-y/a).

Finally, since -1<y<0 and a≥ 2, this lower bound is positive.


We now prove our main result.

The result is true when m=1 and C(1)=1.
Suppose n≥ m≥2. Recall the notation Φ = Φ(m) and ϕ = |Φ|, and write

    y ϕ/m-1.

Observe that -1 < y < 0. In addition, for 0 ≤ i ≤ m-1, write

    x_i = |{ k ∈Φ| k < m-i }|     
      y_i = |{ k ∈Φ| k ≤ i }|.

Note that x_i≤ m-i-1, y_i≤ i, x_i + i ≥ϕ(m) and y_i +(m-i)≥ϕ(m). In summary

    ϕ(m)-i≤ x_i≤ m-i-1    ϕ(m)-m+i≤ y_i≤ i.


We begin by proving the required upper bound, namely

    ρ(n) ≤⌈n/m⌉^y    .

Although we do not require it for this proof, the upper bound
above holds trivially if 1 ≤ n ≤ m as then ρ(n) ≤ 1 = ⌈n/m⌉^y=1.
We proceed by induction on n. 
Now let n ≥ m+1, so that a ⌈n/m⌉≥ 2. 
Write n=am-b, and note that 0 ≤ b ≤ m-1. Assume the upper bound in (<ref>) holds for all positive integers strictly less than n. By Lemma <ref>,   

    ρ(am-b) = (a-1)m-b/am-bρ((a-1)m-b) + 1/am-b∑_k ∈Φ^ρ(am-b-k).

By the inductive hypothesis, ρ((a-1)m-b) ≤ (a-1)^y. Similarly, for each k ∈Φ, if k < m-b then am-b-k > (a-1)m so by induction ρ(am-b-k) ≤ a^y, and if k ≥ m-b then ρ(am-b-k) ≤ (a-1)^y. Therefore, using the definition of x_i in (<ref>), we obtain

    ρ(am-b)    ≤(a-1)m-b/am-b(a-1)^y + x_ba^y + (ϕ-x_b)(a-1)^y/am-b
       =     a^y ( ( a-1/a - b/a/am-b)(a-1/a)^y + x_b + (ϕ-x_b)(a-1/a)^y/am-b) 
       =     a^y ( ( a-1/a)^y+1( 1 - b - aϕ + ax_b/(a-1)(am-b)) + x_b/am-b).

By Lemma <ref>, ( a-1/a)^y+1 < 1 - y+1/a, and as y+1=ϕ/m and a ≥ 2, we have




    ρ(am-b) ≤  a^y Y Y= (1-ϕ/am) ( 1 - b - aϕ + ax_b/(a-1)(am-b)) + x_b/am-b.

We want to show that Y≤ 1, so we write Y=1-Y_0 where Y_0 is an algebraic fraction in a,b,x_b,m,ϕ. It suffices, therefore, to show that Y_0≥0 for all input values satisfying a≥2, 0≤ b<m, and ϕ≤min{b+x_b,m} c.f. (<ref>). We use a computer to factor Y_0 giving
 
    Y_0= 1 - Y   =  (m-ϕ)(b+x_b-ϕ)/m(a-1)(am-b)≥ 0.

Thus Y≤ 1 and hence ρ(am-b) ≤ a^y, proving the upper bound (<ref>) for all n ≥ 1.

We now turn to the lower bound. Recall the definition of C := C(m) in (<ref>), and  note that C > 0 since ρ(n) > 0 for all n ≥ 1. We will prove that, 

    ρ(n) ≥ C ⌊n/m⌋^y

As for the proof of the upper bound, we use induction on n.  Observe that if m ≤ n ≤ 2m-1, then ⌊n/m⌋ = 1, and hence  
ρ(n) ≥ C = C ⌊n/m⌋^y
holds by (<ref>). Now suppose n ≥ 2m. Then a ⌊n/m⌋≥ 2. Write n=am+b, and note that 0 ≤ b ≤ m-1. (Be aware that the definitions of a and b differ from their definitions in the proof of the upper bound.) Assume that the lower bound (<ref>) holds for all positive integers strictly less than n. By Lemma <ref>,

    ρ(am+b) = (a-1)m+b/am+bρ((a-1)m+b) + 1/am+b∑_k ∈Φ^ρ(am+b-k).

By the inductive hypothesis, ρ((a-1)m+b) ≥ C(a-1)^y. Similarly, for each k ∈Φ, if k ≤ b then am+b-k≥ am so by induction, ρ(am+b-k) ≥ Ca^y, and if k > b then am > am+b-k≥  (a-1)m so by induction ρ(am+b-k) ≥ C(a-1)^y.  Therefore, using the definition of y_b in (<ref>), we obtain

    ρ(am+b)    ≥  C ( (a-1)m+b/am+b (a-1)^y + y_ba^y + (ϕ-y_b)(a-1)^y/am+b) 
       =     Ca^y ( ( a-1/a + b/a/am+b)(a-1/a)^y + y_b + (ϕ-y_b)(a-1/a)^y/am+b) 
       =     Ca^y ( ( a-1/a)^y+1( 1 + b + aϕ - ay_b/(a-1)(am+b)) + y_b/am+b).

By Lemma <ref>, since a ≥ 2, y=ϕ/m-1 and -1 < y < 0, we have (a-1/a)^y+1 > 1-y+1/a( 1-y/a), so

    ρ(am+b) ≥  Ca^y ( (1-ϕ/am( 1 + m-ϕ/am) )  ( 1 + b + aϕ - ay_b/(a-1)(am+b)) + y_b/am+b).

Write the above expression as Ca^yY where Y is an algebraic fraction in a,b,y_b,m,ϕ. We want to show that Y≥ 1, so we write Y=1+Y_0. It suffices, therefore, to show that Y_0≥0 for all input values satisfying a≥2, 0≤ b<m, m≥ϕ and ϕ -m+b≤ y_b≤ b (see (<ref>)). We use a computer to factor Y_0 giving

    Y_0=Y-1=
      (m-ϕ)(am(b-y_b)+ϕ(y_b-b+m-ϕ))/m^2 a (a-1)(am+b)≥0.

Therefore, ρ(am+b) ≥ Ca^yY≥ Ca^y and the claim in (<ref>) holds for all n ≥ m. This establishes the lower bound and completes the proof of the theorem.





§ COMPUTATIONAL EVIDENCE

Let n ≥ m > 1 and assume that m is square-free. First suppose that m is prime. Recall that p_ m(n) is the proportion of elements in (n) with no cycle of length divisible by m, so p_ m(n)=p_ m(n+i) for 0≤ i<m. Since ρ(n,m)=p_ m(n), it follows that for all a ≥ 1,

    ρ(am,m) = ρ(am+1,m) = ⋯ = ρ(am+(m-1),m).

Moreover, in this case (since m is prime),

    ρ(n,m) = k(m) (n/m)^ϕ(m)/m-1 + O(n^ϕ(m)/m-2),

where k(m)=Γ(1-1/m)^-1, noting that π^-1/2≤ k(m) < 1 (see <cit.> and <cit.>).

In this final section we investigate the extent to which an analogue of the relationship in (<ref>) holds for general positive integers m. We do this by presenting some computational evidence which led the authors to the statement of Theorem <ref> and to Question <ref> below.

The recursive formula for ρ in Lemma <ref> provides an efficient means of computing ρ(n,m) from the values ρ(0,m), ρ(1,m), …, ρ(m-1,m). In Figures <ref>–<ref> we fix the value of m as 6, 15 and 30, respectively, and we plot 

    f(n,m) ρ(n,m) ·(n/m)^1-ϕ(m)/m
 
against n for many values of n greater than m.









It is evident from Figures <ref>–<ref> that (<ref>) does not hold if m is composite.  Figures <ref>–<ref> suggest that  for fixed 0 ≤ b < m the function f(n,m) is either increasing or decreasing as n→∞ with n≡ b m, and moreover that the limit is independent of b.
This would imply <cit.> and give even sharper
bounds than in our main theorem as we explain below.
Pouyanne <cit.> defined
a constant κ_m (for not necessarily square-free m) as follows:

    κ_m=1/Γ(ϕ(m)/m)∏_d| md^-μ(d)/d    μ(d)=(-1)^|π(d)|   
    
      0



Thus f(n,m)∼λ_m:=κ_m/m^1-ϕ(m)/m as n→∞
paraphrases Pouyanne's result.
Theorem <ref> proves that C(m)≤λ_m≤1.
Figures 1–3 show that the convergence as n→∞
of f(n,m) to λ_m can be very slow. Computational evidence
suggests that the sequence ( f(am+b,m))_a=0^∞ is eventually
monotonic. This leads us to the following question.


  Let m be a positive square-free integer. Does there exists an
  integer a_0 such that for each b the sequence ( f(am+b,m))_a≥ a_0
  is monotonic? 



  If this is true, then for a≥ a_0, f(am+b,m) is bounded
  between f(a_0m+b,m) and λ_m=κ_m/m^1-ϕ(m)/m. When
  m=p is prime and 0≤ b≤p-1/2, Theorem <ref> below
  shows λ_p≤ f(ap+b,p)≤ 1-1/p and for all a≥1. This improves (<ref>).



We used the optimised Magma <cit.>
code in <cit.>, and the recurrence in
Lemma <ref>, to compute values of ρ(n,m) for n up to 10^5
and m≤30.
This allowed us to both test the veracity of Question <ref>,
and to discover some surprising patterns. The six curves in
Figure <ref> (unsurprisingly) correspond to the six possible choices for
b=n m, but in a strange order viz. b=1,6,2,5,3,4 going from
the highest curve to the lowest. (Incidentally, this observation
motivated our “modulo m” proof of Theorem 1.) We noticed also that for many choices of
m and b the sequence f(am+b,m) for 0≤ a≤ 1000 
was strictly decreasing, or strictly increasing. However, for very few choices
e.g. (m,b)=(26,24), the sequence initially increased (6 times), and
then increased (596 times) and then increased (397 times). (The graph
is a very flat sawtooth and so looks horizontal.)
These unusual patterns lead us to question the existence of
a simple proof of Question <ref>.


Question <ref> is true in the very special
case when p is a prime.


Let p be a prime. The sequence (f(ap+b,p))_a≥0
increases strictly for 0≤ b≤⌊p-1/2⌋, and for a≥p-1/2,
decreases strictly for ⌊p-1/2⌋<b≤ p-1.



Write n=ap+b where 0≤ b<p. It follows from the closed
formula 
ρ(n,p)=∏_i=1^a(1-1/ip) of <cit.>, that
ρ(n+p,p)=ρ(n,p)(1-1/(a+1)p). Hence

    f(n+p,p)/f(n,p)=(1-1/(a+1)p)(n+p/p)^1-ϕ(p)/p/(n/p)^1-ϕ(p)/p
      =(1-1/(a+1)p)(1+1/a+b/p)^1/p.


Fix p and b. Our proof has two cases. Case 1 proves that
the above ratio is at least 1 for 0≤ b≤⌊p-1/2⌋, and 
Case 2 shows the ratio is at most 1 for ⌊p-1/2⌋<b<p.

Case 1. 0≤ b≤⌊p-1/2⌋. The above ratio is at
least 1 if and only if

    (1-1/(a+1)p)^p≥a+c/a+c+1

Observe that 0≤ c<1, and for 0≤ c_1,c_2<1 we have

    a+c_1/a+c_1+1<a+c_2/a+c_2+1

The left-hand side of (<ref>) is independent of c, and
by (<ref>) the right-hand side of (<ref>) is largest when
c equals c_0:=1/2(1-1/p). Set x=(a+1)p. Then

    a+c_0/a+c_0+1=a+1/2(1-1/p)/a+1/2(1-1/p)+1
      =2ap+p-1/2ap+3p-1=2x-p-1/2x+p-1.

Hence (<ref>) is true if for all a≥0 and all integers p≥1,
we have

    (x-1/x)^p≥2x-p-1/2x+p-1


We now prove (<ref>) by induction on p for
all integers p≥1. The case p=1
is clearly true. In the following display,
the first inequality follows from the inductive hypothesis, and the second
requires proof:

    (x-1/x)^p+1=(x-1/x)^p(x-1/x) IH≥(2x-p-1/2x+p-1)(x-1/x)
    ?≥2x-p-2/2x+p.

The second inequality is equivalent to

    (2x+p)(2x-p-1)(x-1)≥ (2x-p-2)(2x+p-1)x.

The left minus the right side is p^2+p>0.

This proves Case 1.

Case 2. ⌊p-1/2⌋<b<p.
In this case it suffices to prove

    (1-1/(a+1)p)^p<a+c/a+c+1

First note that ⌊p-1/2⌋+1=⌈p/2⌉.
Hence b/2≤⌈p/2⌉≤ b and so 1/2≤ c.
For c≥1/2, the right-hand side of (<ref>) is
smallest for c=1/2 by (<ref>).
As before, set x=(a+1)p. We prove (<ref>) by establishing the
inequality below:

    (x-1/x)^p<a+1/2/a+3/2
      =2a+1/2a+3=2x-p/2x+p.

Reasoning as in Case 1, we prove (<ref>) for p≥1 by
induction on p. Certainly (<ref>) is true for p=1. Assume
it is true for some p≥1. By the inductive hypothesis:

    (x-1/x)^p+1=(x-1/x)^p(x-1/x) IH<(2x-p/2x+p)(x-1/x)
      ?≤2x-p-1/2x+p+1,

  where the last inequality is equivalent to

    (2x-p)(x-1)(2x+p+1)≤(2x-p-1)x(2x+p)     p^2+p≤ 2x.

Finally, 2x≥ p^2+p is true for a≥p-1/2.
This proves Case 2, and the theorem.




  As before, let x=(a+1)p. If p=2, then b=1, so c=1/2
  and (<ref>) becomes
  
    (x-1/x)^2≤a+1/2/a+3/2
      =2a+1/2a+3
      =x-1/x+1.

  Cancelling x-1, this is equivalent to x^2-1≤ x^2. Thus the claim is true   for p=2. Suppose now that p is an odd prime.
  The smallest value of b is b_0=p+1/2. By (<ref>),
  the right-hand side of (<ref>) is minimal for c equal to
  c_0=b_0/2=1/2(1+1/p). In this case,
  
  
    a+c_0/a+c_0+1=a+1/2(1+1/p)/a+1/2(1+1/p)+1
        =2ap+p+1/2ap-p+1=2x-p+1/2x+p+1.

  Hence (<ref>) is true, if for all a≥0, and all integers p≥2,
  we have
  
    (x-1/x)^p≤2x-p+1/2x+p+1

  In the following display,
  the first inequality follows from the inductive hypothesis, and the second
  inequality must be established:
  
    (x-1/x)^p+1 IH≤(2x-p+1/2x+p+1)(x-1/x)
      ?≤2x-(p+1)+1/2x+(p+1)+1.

  The second inequality is equivalent to
  
    (2x+p+2)(2x-p+1)(x-1)≤ (2x-p)(2x+p+1)x.

  This inequality is true since 4x^2-p^2-p+2≥3p^2-p+2≥0.
  This concludes the proof of the second case, and the theorem.












99

ref:BabaiGuestPraegerWilson13
L. Babai, S. Guest, C. E. Praeger, R. A. Wilson, Proportions of r-regular elements in finite classical groups, J. London Math. Soc. 88 (2013), 202–226.

ref:BCP97
W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language,
  J. Symbolic Comput. 24 (1997), 235–265.
 
 
 
 
 

ref:BLGNPS02
R. Beals, C. R. Leedham-Green, A. C. Niemeyer, C. E. Praeger, A. Seress, Permutations with restricted cycle structure and an algorithmic application, Combin. Probab. Comput. 11 (2002), 447–464.

ref:BLGNPS03
R. Beals, C. R. Leedham-Green, A. C. Niemeyer, C. E. Praeger, A. Seress, A black-box algorithm for recognizing finite symmetric and alternating groups, I., Trans. Amer. Math. Soc. 355 (2003), 2097–2113.

ref:BG89
E. A. Bertram, B. Gordon, Counting special permutations, Eur. J. Comb. 10 (1989), 221–226.

ref:BMW00
M. Bóna, A. McLennan, D. White, Permutations with roots, Random Struct. Algorithm 17 (2000), 157–167. 

ref:ErdosTuran65
P. Erdős, P. Turán, On some problems of a statistical group-theory. I, Z. Wahrsch. Verw. Gebiete 4 (1965), 175–186.

ref:ErdosTuran67
P. Erdős, P. Turán, On some problems of a statistical group-theory. II, Acta Math. Acad. Sci. Hungar. 18 (1967), 151–163.

ref:ErdosTuran67b
P. Erdős, P. Turán, On some problems of a statistical group-theory. III, Acta Math. Acad. Sci. Hungar. 18 (1967), 309–320.

ref:ScottStephen
S. Harper and S. P. Glasby, Magma code for the asymptotic behaviour of ρ(n,m),
http://www.maths.uwa.edu.au/ glasby/research.htmlhttp://www.maths.uwa.edu.au/∼glasby/research.html.

ref:glasby
S. P. Glasby, Using recurrence relations to count certain elements in symmetric groups, Europ. J. Combin. 22 (2001), 497–501.

ref:GuestPraeger12
S. Guest, C. E. Praeger, Proportions of elements with given 2-part order in finite classical groups of odd characteristic, J. Algebra 372 (2012), 637–660.

ref:GuralnickLubeck01
R. M. Guralnick , F. Lübeck, On p-singular elements in Chevalley groups in characteristic p, In: Groups and computation, III (Columbus, OH, 1999), pp. 169–182,  Ohio State Univ. Math. Res. Inst. Publ., vol. 8, de Gruyter, Berlin, 2001. 

ref:IsaacsKantorSpaltenstein95
I. M. Isaacs, W. M. Kantor, N. Spaltenstein, On the probability that a group element is p-singular, J. Algebra 176 (1995), 139–181.




ref:MP
  M. P. Mineev and A.I. Pavlov, The number of permutations of a
    special form. (Russian) Mat. Sb. (N.S.) 99(141) (1976), no. 3,
  468–476, 480. 

ref:NPPY11
A. C. Niemeyer, T. Popiel, C. E. Praeger, S. Yalçınkaya, On semiregular permutations of a finite set,  Math. Comp. 81 (2011), 605–622.

ref:NPS13
  A. C. Niemeyer, C. E. Praeger, A. Seress, Estimation problems and randomised group algorithms, In: Probabilistic Group Theory, Combinatorics and Computing, Editors: A. Detinko, D. Flannery and E O'Brien, pp. 35–82, Lecture Notes in Mathematics, vol. 2070, Springer, Berlin, 2013.

ref:P
  A. I. Pavlov, Limit distribution of the number of cycles and of the
  logarithm of order of a class of permutations. (Russian)
  Mat. Sb. (N.S.) 114(156) (1981), no. 4, 611–642, 655. 

ref:Pouyanne02
  N. Pouyanne, On the number of permutations admitting an m-th root.
  Electron. J. Combin. 9 (2002), 1–12. 




