EWENS SAMPLING AND INVARIABLE GENERATION

arXiv:1610.04212v2 [math.PR] 15 Oct 2016

GERANDY BRITO, CHRISTOPHER FOWLER, MATTHEW JUNGE, AND AVI LEVY

Abstract. We study the number of random permutations needed to invariably generate the symmetric group, Sn , when the distribution of cycle counts has the strong
α-logarithmic property. The canonical example is the Ewens sampling formula, for which
the number of k-cycles relates to a conditioned Poisson random variable with mean α/k.
The special case α = 1 corresponds to uniformly random permutations, for which it was
recently shown that exactly four are needed.
measures, and almost every α, we show that precisely
 For strong−1α-logarithmic

(1 − α log 2)
permutations are needed to invariably generate Sn . A corollary is that
for many other probability measures on Sn no bounded number of permutations will
invariably generate Sn with positive probability. Along the way we generalize classic
theorems of Erdős, Tehran, Pyber, Luczak and Bovey to permutations obtained from the
Ewens sampling formula.

Contents
1. Introduction
1.1. Ewens sampling and the logarithmic property
1.2. Statement of Theorem 1
1.3. Generalizations for the Ewens sampling formula
1.4. Overview of proof and result for sumsets
1.5. Further questions
1.6. Notation
1.7. Outline of paper
1.8. Acknowledgements
2. Proof of Theorem 1
3. The upper bound for mα
3.1. The Feller Coupling
3.2. Proofs of Theorem 3, Theorem 4, and Theorem 5
3.3. Proving Proposition 7
4. The upper bound for sα
5. The lower bound for sα
References

1
2
3
5
6
7
8
9
9
9
11
11
17
24
25
28
33

1. Introduction
In 1934, van der Waerden raised the question of the minimal number of uniformly random
permutations required to invariably generate Sn with positive probability [Wae34]. Recent
breakthroughs by Pemantle, Peres, Rivin [PPR15] and Eberhard, Ford, Green [EFG15a]
resolved van der Waerden’s question, showing that precisely four permutations are required.
1

2

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

We consider the same question in the context of more general permutation measures related
to the cycle structure, primarily the Ewens sampling formula (1) introduced in [Ewe72].
It aligns a permutation’s cycle structure with conditioned independent Poisson random
variables.
Elements g1 , . . . , gm of a group G generate the group if the smallest subgroup containing
them is G itself. The symmetric group Sn is the group of permutations of the set [n] :=
{1, . . . , n}. Permutations π1 , . . . , πm invariably generate Sn if for all σ1 , . . . , σm ∈ Sn the
−1
elements σ1 π1 σ1−1 , . . . , σm πm σm
generate Sn . The definition of invariable generation is
conjugacy invariant. Conjugacy classes of the symmetric group are parametrized by the cycle
type of a permutation, defined to be the multiset of cycle lengths in the cycle decomposition
of a permutation. For this reason, invariable generation concerns only the cycle structure of
permutations, rather than the action on [n].
Recent developments show that cycle counts converge to independent Poisson random
variables for many measures on Sn as n tends to infinity. Arratia, Barbour and Tavare have
shown that strong α-logarithmic measures have this property and numerous further results
[AT92, ABT92, ABT00, ABT16]. Measures with general cycle weights are considered in
[BUV11, EU14] and related permutons are introduced in [KKRW15]. Following this work,
Mukherjee used Stein’s method to deduce that a variety of permutation measures have
Poisson limiting cycle counts [Muk16]. Furthermore, the structure of the short cycles in the
Mallows measure was characterized in [GP16].
In addition to its intrinsic interest, the minimal number of permutations required for
invariable generation has applications to computational Galois theory. One may use this
quantity to estimate the runtime of a Monte Carlo polynomial factorization algorithm
[Mus78, Hei86, DS00, PPR15]. This establishes a connection between the irreducible factors
of polynomials and the cycle structure of permutations. The cycle structure of a permutation
is also compared with prime factorization of integers in the survey [Gra08]. An analogy
between divisors of large integers and invariable generation of permutations is then mentioned
in the introduction of [EFG15a], postulating a link between the threshold for invariable
generation and small divisors of a set of random integers.
Despite the age of van der Waerden’s question, it was only recently shown that the number
of uniformly
random permutations required to invariably generate Sn is bounded. A bound
√
of O( log n) was first established in [Dix92]. This was improved to O(1) in [LP93], but
the constant was large (≈ 2100 ). Pemantle, Peres and Rivin reduced the bound to four in
[PPR15], which was then shown to be sharp by Eberhard, Ford and Green in [EFG15a].
We extend the results for uniform permutations to the Ewens’ sampling formula and
beyond. Along the way, we extend results in [ET67, LP93, Bov80], replacing counting
arguments with a tool known as the Feller coupling (8) introduced in [Fel45, p. 815].
1.1. Ewens sampling and the logarithmic property. The Ewens sampling formula
appears throughout mathematics, statistics and the sciences. In the words of Harry Crane
it, “exemplifies the harmony of mathematical theory, statistical application, and scientific
discovery.” This is stated in his survey [Cra16b]. It and its followup [Cra16a] give a nice
tour of the formula’s universal character, describing applications to evolutionary molecular
genetics, the neutral theory of biodiversity, Bayesian nonparametrics, combinatorial stochastic
processes, and inductive inference, to name a few. The sampling formula also underpins
foundational mathematics in number theory, stochastic processes, and algebra.
We start by formally defining the Ewens sampling formula, as well as the strong αlogarithmic property. Let Poi(λ) denote the law of a Poisson random variable with mean

EWENS SAMPLING AND INVARIABLE GENERATION

3

λ. Fix α > 0 and let X1 , . . . , Xn be independent random variables in which Xk has law
Poi(α/k). For a permutation π ∈ Sn let Ck denote the number of k-cycles in π. More
precisely, Ck is the number of disjoint k-element subsets of [n] on which π restricts to a
cyclic permutation. We say that the vector C = (C1 , . . . , Cn ) has distribution ESF(α, n) if
it satisfies the joint distribution:
(1)

h
P[C1 = x1 , . . . , Cn = xn ] = P X1 = x1 , . . . , Xn = xn

n
X

i
kXk = n .

1

The tuple (C1 , . . . , Cn ) uniquely specifies the cycle type of a permutation. Furthermore,
it is easy to see that as π ranges over Sn , the tuple (C1 , . . . , Cn ) associated to π ranges over
the set
(
)
n
X
n
(C1 , . . . , Cn ) ∈ {0, . . . , n} :
kCk = n .
k=1

Thus, (1) specifies a measure on the conjugacy classes of Sn . We extend this to a measure
on Sn (also denoted by ESF(α, n)) by weighting all elements of the same class uniformly.
Note that ESF(1, n) is the uniform measure, and therefore the results we establish regarding
ESF(α, n) will generalize the corresponding results about uniform permutations appearing
in [PPR15, EFG15a].
A more general family that includes ESF(α, n) is obtained by replacing the Xk in (1) with
an arbitrary sequence of independent nonnegative integerP
valued random variables Z1 , Z2 , . . ..
kZk = n, logarithmic growth of
To
avoid
intractable
distortions
when
conditioning
on
P
Zk is traditionally assumed (see [ABT00]). For our purposes, we require the Zk satisfy
the strong α-logarithmic condition:
(2)

|iP[Zi = 1] − α| < e(i)c1 ,
iP[Zi = `] ≤ e(i)c` ,
l ≥ 2,
P −1
P
where
i e(i) and
`c` are both finite.

Besides Poisson, the most commonly used distributions for the Zi are the negative-binomial
and binomial distributions. These are called assemblies, multisets, and selections, respectively
(see [ABT00] for more discussion). The proof that all three of these different distributional
choices for the Zi satisfy the strong α-logarithmic property is in [ABT00, Proposition 1.1].
It is no trouble to work at this level of generality, because the limiting cycle structure of
any family satisfying the strong α-logarithmic property is the same as that for an ESF(α, n)
permutation. We will describe this in more detail in Section 1.4, but in short, the number of
`-cycles converges to an independent Poisson with mean α/`.
1.2. Statement of Theorem 1. We state our result in terms of random variables Z1 , Z2 , . . .
satisfying the strong α-logarithmic property at (2). The example to keep in mind though is
the measure ESF(α, n), since all of these have the same limiting cycle counts.
Given such a collection let µn (α, Z1 , Z2 , . . . , Zn ) be the measure induced on Sn via the
relation at (1) with Xk replaced by Zk . We define mα = mα (Z1 , Z2 , . . .) to be the minimum
number of permutations sampled according to µn to invariably generate Sn with positive
probability as n → ∞:
n
o


(3) mα = inf m : inf P {π1 , . . . , πm } ⊂ Sn , πi ∼ µn , invariably generate Sn > 0 .
m≥2

n≥2

4

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

20

15

10

5

0.0

0.2

0.4

0.6

0.8

1.0

1.2

1.4

Figure 1. The graph h(α) defined at (4), and thus the behavior of mα and
sα . We are not sure about the value at the points of discontinuity in h. See
Question 1 for more discussion.
Our theorem gives a closed formula for mα (see Figure 1), save for a countable exceptional
set. Because we will reference it several times, we write the expression here:
(

(1 − α log 2)−1 , 0 < α < 1/ log 2
(4)
h(α) =
.
∞,
α ≥ 1/ log 2
Theorem 1. Let Z1 , Z2 , . . . be a collection of random variables satisfying the strong αlogarithmic condition at (2). Let mα = mα (Z1 , Z2 , . . .), as in (3), be the minimum number
of permutations to invariably generate Sn with positive probability. Let h(α) be as in (4).
For points of continuity of h it holds that mα = h(α). At points of discontinuity we have
h(α) ≤ mα ≤ h(α) + 1.
This has broader implications beyond measures that have the strong α-logarithmic property.
We use it to deduce that any finite collection of random permutations with cycle counts
asymptotically dominating a Poi(1/j log 2) random variable will fail to generate a transitive
subgroup of Sn .
Corollary 2. Suppose that cj ≥ 1/ log 2 and Xk ∼ Poi(cj /j). Let κn be a sequence of
probability measures on Sn such that for random permutations π ∼ κn the cycle structure, C
satisfies
d ((C1 , . . . , Ck0 ), (X1 , . . . , Xk0 ))TV → 0
for all fixed k0 . Then, the probability that any fixed number of permutations sampled according
to κn invariably generate a transitive subgroup of Sn goes to 0 as n → ∞.
This corollary is particularly relevant to the results in [BUV11] and [EU14]. They describe
measures on Sn that are formed by weighting cycle lengths by parameters cj . The limiting
cycle structure has Cj ∼ Poi(cj /j). Thus, we can create any limiting Poisson cycle structure
we like. In particular, those satisfying Corollary 2.
Another source of alternate measures with limiting Poisson cycle counts comes from
[Muk16]. This fits into the larger body of work on permutons initiated in [KKRW15]. Of

EWENS SAMPLING AND INVARIABLE GENERATION

5

particular interest is Mallow’s measure (introduced in [Mal57]). This measure specifies a
parameter qn > 0 that biases towards more or less inversions in a permutation. A permutation
inv(π)
π has probability proportional to qn
, where inv(π) := |{(s, t)|s < t and πs > πt}|.
The recent article ([GP16]) begins to characterize the cycle structure of Mallow’s measure.
They find that for (1 − qn )−2  n all cycles are on the order of o(n). The high density of
small cycles, along with [Muk16, Theorem 1.4], which proves a limiting Poisson cycle profile,
suggests that no finite collection of permutations sampled according to Mallow’s measure in
this regime will invariable generate Sn . Note that in the regime (1 − qn )−2  n the cycle
counts converge to those of a uniformly random permutation. This is a new and exciting
area. We are hopeful our result will find more applications as these objects become better
understood.
1.3. Generalizations for the Ewens sampling formula. In proving Theorem 1 we
connect an approximation sumset model (described in Section 1.4) back to fixed-set sizes in
random permutations. This also takes place in [PPR15] and [EFG15a]. These two articles
use a small-cycle limit theorem for uniformly random permutations ([AT92, Theorem 1]).
Namely, that the number of `-cycles in a uniformly random permutation converges to a
Poisson random variable with mean 1/` that is independent of the other small cycles.
Permutations sampled from µn have an analogous limit theorem ([ABT00, Theorem 3.2]).
Except now the `-cycles behave like Poisson random variables with mean α/`. This lets
us use similar ideas to analyze the corresponding sumset model. However, our approach
diverges significantly when we connect back to random permutations. Especially in obtaining
an upper bound on mα . The difference is that both [PPR15] and [EFG15a] have access to
a large canon of results for uniformly random permutations. We do not. This requires a
deep excavation where we extend classical results to π ∼ ESF(α, n). Along the way we prove
many new estimates (see Lemma 10, Lemma 11, Lemma 12, Proposition 13, Lemma 17, and
Lemma 19) for larger cycle lengths in ESF(α, n) permutations.
We begin by showing that with high probability the only transitive subgroups containing
a permutation π sampled with distribution ESF(α, n) are An and Sn . This is the analogue
of what [LP93, Theorem 1] proves for uniformly random permutations. This was recently
studied in more detail by Eberhard, Ford, Green in [EFG15b]. We plan to explore this vein
for ESF(α, n) permutations in future work. For our current purposes, the following result
suffices.
Theorem 3. Let π ∼ ESF(α, n). Then with probability 1 − o(1) the only transitive subgroups
containing π are An and Sn .
Pyber and Luczak rely on an important theorem of Bovey regarding primitive subgroups.
We need the analogue of it for ESF(α, n) permutations. The minimal degree of hπi =
{π k : k ∈ Z} is the minimum number of elements of {1, . . . , n} displaced by some power of π.
[Bov80, Theorem 1] says that if π is a uniformly random permutation, then for each ε > 0
and 0 < β < 1 we have
P[minimal degree of hπi > nβ ] < Cε,β nε−β .
We establish a weaker analogue of this result.
Theorem 4. Let π ∼ ESF(α, n). For each 0 < β < 1 and any α it holds that
P[minimal degree of hπi > nβ ] = o(1).
Establishing Theorem 3 also requires a generalization of a classical theorem of Erdös and
Turán (see [ET67, Theorem V]).

6

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

Theorem 5. Q
Let π ∼ ESF(α, n) and ω(n) → ∞.√The probability that the largest prime
n
which divides `=1 `C` is larger than n exp(−ω(n) log n) is 1 − o(1).
The proof of Theorem 3 uses both Theorem 4 and Theorem 5. For all three generalizations
we follow a somewhat similar blueprint to their predecessors. However, the previous work
often uses special features of uniformly random permutations. Counting arguments are
heavily employed. In general, these techniques do not translate to ESF(α, n) permutations.
Our approach is to use the Feller coupling (see Section 3.1) to directly relate the cycle
structure to independent Poisson random variables. In some places this yields more elegant
proofs, in others it becomes a bit technical. Keeping in mind that ESF(1, n) is the uniform
measure, this is a nice high-level approach to extending these results.
1.4. Overview of proof and result for sumsets. Because a fixed set’s size is a sum of
cycle lengths of a permutation, invariable generation is related to sumsets formed from
random multisets. The link is developed over a collaborative arc of Arratia, Barbour and
Tavaré, [ABT92, ABT00, AT13, ABT16]. They study the relationship between α-logarithmic
structures and Poisson random variables. Most relevant for our purposes are the descriptions
of the cycle counts C = (C1 , . . . , Cn ) for permutations sampled according to µn .
They prove in [ABT00, Theorem 3.1, Theorem 3.2] that, for permutations induced by
the strong α-logarithmic property, the small cycle counts evolve to be independent Poisson
random variables, and the large cycle counts follow Ewens sampling formula. Furthermore,
[ABT92, Lemma 1] (also discussed in [ABT16]) shows that the Ewens sampling formula can
be cleanly related via the Feller coupling to independent Poi(α/k) random variables. The
payoff is that we can model the sizes of fixed sets in a permutation with independent Poisson
random variables.
Let X(α) = (X1 , X2 , . . .) be a sequence of Poisson random variables where Xj has mean
α/j. The coupling discussed in the previous paragraph allows us to model the sizes of fixed
sets in a permutation with the random sumset


X

L (X(α)) =
jxj : 0 ≤ xj ≤ Xj .


j≥1

Returning to our opening question, we can bound the required number of permutations
from above if no fixed set size is common to all permutations. And we can bound the number
from below if there is guaranteed to be a common fixed set size. Consider independent
realizations X(1) (α), . . . , X(m) (α). The upper and lower bounds correspond to finding
extremal values of m such that
Tm
(i) i=1 L (X(i) (α)) = {0} with positive probability, and
Tm
(ii) | i=1 L (X(i) (α))| = ∞ almost surely.
Since common elements among independent sumsets correspond to common fixed-set sizes of
independent permutations, invariable generation is analogous to a trivial sumset intersection.
On the other hand, an infinite intersection means that common fixed-sets persist among
the permutations. For the case α = 1, the results of [PPR15, Theorem 1.6] and [EFG15a,
Corollary 2.5] each imply that four sets suffice in (i). That (ii) holds with three sets is due
to [EFG15a, Corollary 3.9]. Here is the analogue for general α > 0.
(i)
Theorem 6. Let sα := inf{m : P[∩m
1 L (X (α)) = {0}] > 0} be the smallest number of
i.i.d. sumset intersections so that the resulting set is trivial with positive probability. Let h(α)

EWENS SAMPLING AND INVARIABLE GENERATION

7

be as in (4), and mα as in Theorem 1. At points where h is continuous we have sα = h(α),
and at the discontinuities h(α) ≤ sα ≤ h(α) + 1.
To establish this result for sumsets, we build upon the ideas in [PPR15] and [EFG15a] to
prove matching lower and upper bounds for sα . These bounds can be found in Proposition 23
and Proposition 24. Parts of the argument are as simple as swapping 1’s for α’s, but in
others, particularly the lower bound, some care is required.
A relevant quantity for establishing the upper bound is pk = pk (α), the probability the
element n appears in L (X). Estimating pk (1) is the major probabilistic hurdle in [PPR15].
There are two difficulties. The first is called a lottery effect; certain unlikely events greatly
skew pk . This is circumvented by using
P quenched
P probabilities p̃k , which ignore an o(1)
portion of the probability space (that
Xj and
jXj are uncharacteristically large). With
this restriction, it is shown in [PPR15, Lemma 2.3] that p̃k (1) ≤ k log(2)−1 . Notice that
4(log 2 − 1) < −1 and a Borel-Cantelli type argument implies finiteness of the intersection.
Establishing the quenched formula is the second hurdle. It requires a clever counting and
partitioning of L (X). We generalize these ideas in Lemma 22 to obtain the upper bound
p̃k (α) ≤ Cε k −1+α log 2+ε
for any ε > 0. Taking into account the lottery effect, and ignoring
Qm a vanishing porm
(i)
tion
of
the
probability
space,
we
can
write
P[k
∈
∩
L
(X
)]
=
1
1 p̃k . When m ≥


(1 − α log 2 + ε)−1 , the product is smaller than n−1 ,and the probabilities are summable.
With this, the Borel-Cantelli lemma implies the intersection is almost surely finite, and thus
it is trivial with positive probability.
The lower bound in Proposition 24 requires more care. We generalize the framework in
[EFG15a, Section 3] to higher dimensions to incorporate more than three sumsets as well as
different values of α. Given I ⊆ N and m sumsets we consider the set of differences
S(I; X(1) , . . . , X(m) ) := {(n1 − nm , n2 − nm , . . . , nm−1 − nm ) : ni ∈ L (X(i) ) ∩ I}.
We use Fourier analysis (as in [EFG15a] and [MT84]) to study a smoothed version of
the indicator function of this set. In particular, we will work with its Fourier transform
F : Tm−1 → C. After obtaining a pointwise bound on F , we integrate around that torus to
obtain, for sufficiently large k and I = (k 1−β , k], that |S(I, M1 , . . . , Mm )|  k m−1 and lies
in the cube [−ck, ck]m−1 for some c > 0. The density of these sets is sufficiently high that if
we look in a larger interval, with positive probability we can find j1 , . . . , jm ∈ (k, Dk] such
(1)
(m)
that Xj1 , . . . , Xjm > 0 and
(jm − j1 , . . . , jm − jm−1 ) ∈ S(I; X(1) , . . . , X(m) ).
Combining this with the corresponding point in the set of differences then produces a number
in L (X(1) ) ∩ · · · ∩ L (X (m) ) made solely from values in (k 1−β , Dk] for some constants
β, D > 0. By partitioning N into infinitely many disjoint sets of this form and repeating this
argument for each of them, we conclude that the set of intersections is almost surely infinite.
1.5. Further questions. There is still much to be done for both components of this paper—
random permutations and random sumsets. Recall that Theorem 1 and Theorem 6 do not pin
down the exact behavior at points of discontinuity of h. A glaring question is to characterize
mα and sα at these points. We are doubtful our approach generalizes. Characterizing the
behavior at the critical values is likely difficult, and will require a new idea.
Question 1. What are mα and sα at discontinuity points of h?

8

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

For random permutations we would like a more complete characterization than in Corollary 2. In particular an upper bound.
Question 2. Show that if a permutations has cycle counts that are asymptotically dominated
by Poisson random variables with mean h−1 (2)/k, then two will invariably generate Sn with
positive probability.
Corollary 2 shows that for many permutation measures no finite number will invariably
generate Sn . Possibly if we let the number of permutations grow with n we will see different
behavior.
Question 3. Let α > 1/ log 2. Prove that there are constants β < β 0 such that the probability
β log n Ewens-α permutations generate Sn is bounded away from 0, while β 0 log n fail to
generate Sn with high probability?
We believe that log n is the correct order by the following approximation model. When
α > 1/ log 2 the fixed set sizes in a random permutation are dense in [n]. So, we can model
the occurrence of each fixed size by independent Bernoulli random variables with some
parameter pα > 0. If one performs N independent thinnings of [n] by including each integer
k with probability pα , then the probability k belongs to all N subsets is pN
α . Hence, the
n
probability there are no common elements in the N -fold intersection is (1 − pN
α ) . If we
choose N = c log n this will converge to either 0 or a positive number as we increase c. The
difficulty in answering the question for permutations is we do not have independence for
fixing different fixed set sizes.
We also have a question in the simpler setting of generating Sn . Dixon’s theorem [Dix92]
implies that two uniformly random permutations will generate either An or Sn with high
probability. Does the analogue hold for ESF(α, n) permutations? Because generation relies
on more than just cycle structure, this may be a hard question.
Question 4. How many ESF(α, n) permutations are needed to generate one of An or Sn
with high probability?
1.6. Notation. Note that α > 0 is fixed throughout. As already discussed, we denote
cycle counts of a permutation by C = (C1 , . . . , Cn ) with Cj the number of j-cycles. Unless
otherwise noted, our permutations and cycle vectors come from an ESF(α, n) distribution.
We will let Y(α) denote a vector of independent Poi(α/k) random variables that are obtained
from the Feller coupling in (8). We will also take X(α) to be a vector of independent Poi(α/k)
random variables. This is done to distinguish the permutation and random sumset settings.
Henceforth we will suppress the α dependence unless there is reason to call attention to it.
For an infinite vector, such as Y, we will use the notation Y[i, j] to denote the sub-vector
(Yi , Yi+1 , . . . , Yj ).
For I an interval in N define the sumset


X

L (I, X) :=
jxj : 0 ≤ xj ≤ Xj ,


j∈I

and set L (X) := L (N, X). Given X define
X
(5)
Xj ,
f`,k (X) =
`<j≤k

g`,k (X) =

X

jXj .

`<j≤k

It will be convenient to abbreviate fk := f1,k (X) and gk := g1,k (X). Thus, fk is the number
of available summands smaller than k, and gk is the largest sum attainable with them.

EWENS SAMPLING AND INVARIABLE GENERATION

9

We will use the notation f  g and f (n) = O(g(n)) interchangeably for the existence of c
such that for all large enough n it holds that f (n) ≤ cg(n). When the c depends on our choice
of ε we will use f ε g, similarly f m,ε denotes dependence of the constant on both ε and
the number of intersections m. We use the little-o notation f (n) = o(g(n)) to mean that
f (n)/g(n) → 0. Also, f (n) = Õ(g(n)) means there is k > 0 such that f (n) = O(logk (n)g(n)).
The symbol f (n) ≈ g(n) means that f (n)/g(n) → c for some c > 0. A sequence of events
En occurs with high probability if lim inf P[En ] = 1. Also i | j means that i divides j (i.e.
there is an integer k with ik = j.)
1.7. Outline of paper. We will lead off with a proof of Theorem 1. This comes in two
parts: an upper bound from Theorem 6, and a matching lower bound in Proposition 9.
The upper bound in Theorem 6 has two distinct components. We connect random sumsets
to ESF(α, n) permutations in Section 3.1. This section includes the proofs of Theorem 3,
Theorem 4, and Theorem 5. The second component is analyzing the random sumset model.
We do this in Section 4 and provide an upper bound on sα at Proposition 23. The lower
bound is Proposition 9 and proven in Section 5.
1.8. Acknowledgements. We would like to thank Robin Pemantle for several helpful
conversations. We are very grateful for Richard Arratia’s correspondence. He made us aware
of the indispensable Feller coupling. Also, thanks to Clayton Barnes, Emily Dinan, and
Jacob Richey for their assistance in the formative stages of this project.
2. Proof of Theorem 1
First we show that h(α) + 1 is an upper bound for the number of ESF(α, n) permutations
to invariably generate Sn .
Proposition 7. Suppose α is a continuity point of h. A collection of h(α) independent permutations sampled according to an ESF(α, n) invariably generates Sn with positive probability
as n → ∞.
Proof. Let m = h(α). Call the permutations π (1) , . . . , π (m) . Condition π (1) to be odd.
Lemma 19 guarantees this happens with probability bounded away from zero. Define the
events
En,k = {π (1) , . . . , π (m) fix an `-set for some k ≤ ` ≤ n/2},
Fn,k = {π (2) has no `-cycles with ` ≤ k}.
The probability of a common fixed set size amongst all of the permutations is bounded above
by
(6)

c
c
P[En,k ∪ Fn,k
] ≤ P[En,k ] + P[Fn,k
].

Therefore, the π (i) will invariably generate a transitive subgroup of Sn if this quantity is less
than 1.
Now α is a continuity point of h, so
m = h(α) = d(1 − α log 2)−1 )e > (1 − α log 2)−1 .
It follows that there exists some ε > 0 such that
m = (1 − (α + ε) log 2)−1 .
Fix ε0 such that 0 < ε0 < ε. By Lemma 18 for any k and i = 2, . . . , m,
P[π (i) fixes a k-set] ≤ ck −δ ,

10

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

where
δ = 1 − (α + ε0 ) log 2.
Similarly, by Corollary 21 for any k,


α+1 α+1
(1)
−δ
P[π fixes a k-set] ≤ ck · max
,
.
α
1
By independence of the π (i) , we conclude
P[En,k ] ≤ (ck −δ )m · max



α+1 α+1
,
α
1


.

By construction we have that δm > 1. A union bound for k0 ≤ k ≤ n/2 ensures that, given
some β > 0, we can choose k0 such that P[En,k0 ] < β. Moreover, [ABT00, Theorem 3.1]
(2)
ensures that the cycle counts C[1, k0 ] of πn converge in total variation to Y[1, k0 ]. Hence,
lim inf P[Fn,k0 ] > 0.
n→∞

Set β equal to half this limit infimum. Now, for an appropriate k0 and large enough n, it
holds that (6) is strictly less than 1. This means that with positive probability the collection
invariably generates a transitive subgroup of Sn . By Theorem 3 we know this transitive
subgroup is with high probability either An or Sn . Because π (1) is odd, it must be Sn . 
Remark 8. The argument above implies that mα ≤ mα+η for all η > 0, since any appropriate
choice of ε0 in the latter case will hold for the former. It follows that h(α) + 1 permutations
will invariably generate with positive probability at discontinuity points of h.
Now we prove a matching lower bound.
Proposition 9. A collection of m < h(α) permutations sampled independently according to
an ESF (α, n) with high probability do not invariably generate Sn , or any transitive subgroup
of Sn .
Proof. Let m < h(α), and fix
Tmsome ε > 0. By Proposition 24 the intersection of the i.i.d.
sumsets with parameter α, i=1 L (X(i) ), is almost surely infinite. It follows that there is
Tm
some k0 = k0 (ε) such that if k ≥ k0 then i=1 L (X(i) ) ∩ [1, k] 6= ∅ with probability at least
1 − ε/2.
Fix some k ≥ k0 and call the random permutations π (1) , . . . , π (m) . By [ABT00, Theorem
3.1] the cycle counts C(i) [1, k] of π (i) converge in total variation to X(i) ∩ [1, k]. Then there
exists some n0 = n0 (ε, k) such that if n ≥ n0 , with probability greater than 1 − ε/2 we have
C(i) [1, k] = X(i) ∩ [1, k] for all i = 1, . . . , m. Since
m
m


\
\
L (X(i) ) ∩ [1, k] ⊂
L X(i) ∩ [1, k] ,
i=1

i=1

with probability at least 1 − ε we have that π (1) , . . . , π (m) each fix a set of size ` for some
` ≤ k. As ε was arbitrary, this completes our proof.

Theorem 1 is a straightforward consequence of the last two propositions.
Proof of Theorem 1. Together [ABT00, Theorem 3.1, Theorem 3.2] guarantee that the cycle
counts of any measure satisfying the strong α-logarithmic property converge in total variation
to the same distribution as an ESF(α, n) permutation. Hence it suffices to consider ESF(α, n)
permutations.

EWENS SAMPLING AND INVARIABLE GENERATION

11

By Proposition 7 we have mα ≤ h(α) at point of continuity of h. At points of discontinuity,
we use Remark 8 to deduce that mα ≤ mα+η ≤ h(α) + 1. Then, by Proposition 9 we have
that h(α) ≤ mα for all α, completing our proof.


3. The upper bound for mα
The main goal of this section is to prove that mα ≤ sα . Our primary tool for relating
Poisson sumsets to permutations is the Feller coupling. This is described at the onset of
Section 3.1. We then use it in that section to prove several estimates on the cycle structure
of ESF(α, n) permutations. With these we prove Theorem 3, Theorem 4, and Theorem 5 in
Section 3.2. We put all of this together and establish Proposition 7 in Section 3.3.

3.1. The Feller Coupling. The Ewens sampling formula can be obtained via an elegant
coupling attributed to Feller [Fel45, p. 815] for uniform permutations. The articles [ABT92,
ABT16] have nice descriptions. We start with a sequence ξ1 , ξ2 , . . . of mixed Bernoulli
α
i−1
random variables with P[ξi = 1] = α+i−1
and P[ξi = 0] = α+i−1
. Define an `-spacing to
be any occurrence of ` − 1 zeros enclosed by a 1 on the left and right (e.g. 1, 0, 0, 0, 1 is
a 4 spacing). Remarkably, the total number of `-spacings, Y` , is distributed as Poi(α/`).
Moreover, the collection Y1 , Y2 , . . . are independent (see [ABT16, ABT92]).
The counts of spacings in ξ1 , . . . , ξn , 1 generate a partition of n, which can be filled in
uniformly randomly to form a permutation with C` cycles of size `, where C` are sampled
according to an ESF (α, n) distribution. Explicitly,
C` = the number of `-spacings in ξ1 , . . . , ξn , 1
(7)

= ξn−`+1 (1 − ξn−`+2 ) · · · (1 − ξn ) +

n−`
X

ξk (1 − ξk+1 ) · · · (1 − ξk+`−1 )ξk+` .

k=1

This gives an intuition for why ESF (1, n) corresponds to a uniformly random permutation.
Indeed, we can inductively construct such a permutation by letting ξi indicate the decision
to complete a cycle, when there is an i-way choice for the next element.
Letting Rn be the index of the rightmost 1 in ξ1 , . . . , ξn and Jn = n + 1 − Rn it follows
from the previous discussion that
(8)

C` ≤ Y` + 1{Jn = `}.

This says that the cycle counts can be obtained from independent Poisson random variables
through a random number of deletions, and possibly one insertion. We require a few estimates
on the behavior of these perturbations.
Lemma 10. Let Jn be as defined above, and Dn =
of deletions. The following four inequalities hold:

Pn

`=1

Y` − 1{Jn = `} − C` be the number

12

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

α
,
n−`

(9)

P[Jn = `] ≤

(10)

P[Jn = `] ≤ cn−α(1−γ) ,

(11)

P[Jn = `] = O(n−α/(1+α) ),

(12)

` < n.

n − nγ < ` < n,

0 < γ < 1, for some c = c(γ) > 0.

` < n.

EDn = O(1).

Proof. The inequality in (9) follows from the formula given in [ABT92, Remark following
(n)
(17)], which says P[Jn = `] = `EC` /n. The coupling at (8) ensures that P[Jn = `] ≤
(α + `P[Jn = `])/n. Solving for P[Jn = `] gives (9).
Fix some γ ∈ (0, 1). For the case ` > n − nγ in (10) we use that when Jn = ` we must
have ξn−`+1 = 1 and ξk = 0 for all larger index terms up to ξn . The probability of this can
be computed explicitly as
P[Jn = `] =

n
n
Y
Y
α
i−1
i−1
≤
.
α+n−`
α+i−1
α+i−1
n−`+2

n−`+1

We estimate the product by converting it to a sum
 X

 Z n

n
n
Y
i−1
α+i−1
α+x−1
log
= exp −
≤ exp −
dx .
log
α+i−1
i−1
x−1
n−`+1
n−`+1

n−`+1

The last inequality follows from the fact that log α+x−1
x−1 is a decreasing function, and the sum
can be viewed as a right-sided Riemann (over-)approximation. This integral has a closed
form






Z n
α+x−1
(α + n − 1)α+n−1
(α + n − `)α+n−`
−
log
dx = − log
+
log
.
x−1
(n − 1)n−1
(n − `)n−`
n−`+1
Hence, exponentiating the above line gives
(13)

n
Y
n−`+1

(n − 1)n−1
(α + n − `)α+n−`
i−1
≤
×
.
α+n−1
α+i−1
(α + n − 1)
(n − ` − 1)n−`

The leftmost product is less than n−α . The rightmost product can be written as
!n−`
n−`

α
1 + n−`
n−`+α
α
α
(14)
= (α + n − `)
.
(α + n − `)
1
n−`−1
1 − n−`
The rightmost product in (14) is asymptotic to eα /e−1 as n − ` → ∞, and thus may be
bounded by some constant for all values of n − `. Using the hypothesis that n − ` ≤ nγ , it
follows that (14) is universally bounded by cnαγ for some constant c. We conclude that (13)
is less than cn−α+αγ = cn−α(1−γ) . This establishes (10).
To obtain the universal bound at (11), observe when ` ≤ n − nα/(1+α) we can input this
into (9) to obtain
α
P[Jn = `] ≤
= O(n−α/(1+α) ).
n − (n − nα/(1+α) )

EWENS SAMPLING AND INVARIABLE GENERATION

13

And, for ` > n − nα we substitute γ = α/(1 + α) into (10) to obtain the same asymptotic
inequality: O(n−α/(1+α) ).
Lastly, (12) is proven in [ABT92, Theorem 2].

We will also require a bound on the joint probability that two cycles occur simultaneously.
There will be some poly-log terms that, besides being a minor nuisance, do not effect the tack
of our proof. Recall the Õ notation that ignores logarithmic contribution. It is described
carefully in Section 1.6.
Lemma 11. For any i < j ≤ n it holds that
P[Ci Cj > 0] = Õ(i−1 j −α/(1+α) ).
Proof. We start by using the formula at (7) to bound Ci with the ξk ,
Ci ≤ ξn−i+1 (1 − ξn−i+2 ) · · · (1 − ξn ) +

n−i
X

ξk ξk+i .

k=1

Thus,
n−i


X
Ci Cj ≤ ξn−i+1 (1 − ξn−i+2 ) · · · (1 − ξn ) +
ξk ξk+i
k=1



× ξn−j+1 (1 − ξn−j+2 ) · · · (1 − ξn ) +

n−j
X

ξ` ξ`+j



`=1

= (x + y)(z + w).
The last line is just labeling the terms in the product immediately above in the natural
Pn−i
way (i.e. y = k=1 ξk ξk+i ). This is so we can bound E[xz + xw + yw + yz] in an organized
fashion, one term at a time.
Term xz: First, consider ξn−i+1 (1−ξn−i+2 ) · · · (1−ξn )ξn−j+1 (1−ξn−j+2 ) · · · (1−ξn ). When
i < j this product contains the term ξn−i+1 (1 − ξn−i+1 ) ≡ 0, thus it is always zero.
We conclude that
(15)

E[xz] ≡ 0.

Pn−j
Term xw: Next, we consider the cross-term ξn−i+1 (1 − ξn−i+2 ) · · · (1 − ξn ) `=1 ξ` ξ`+j .
Many of the summands are zero. In fact, the overlapping terms with n − j − i + 1 <
` ≤ n − j are identically zero. So, for the sake of obtaining disjoint terms, we consider
the smaller sum
ξn−i+1 (1 − ξn−i+2 ) · · · (1 − ξn )

n−j−i+1
X

ξ` ξ`+j .

`=1

Aside from the ` = n − j − i + 1 term, all the indices are all disjoint. Ignoring this
term for now, the expected value is
(16)

n−j−i
X
α
n−i+1
n−1
α2
···
.
α+n−iα+n−i+1
α+n−1
(α + ` − 1)(α + ` − 1 + j)
`=1

Now i and j correspond to cycle lengths, so we must have i + j ≤ n to have a
nonzero expectation at all. Since i < j we conclude that i < n/2. A simple bound

14

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

on the product outside the sum is to plug this value into the first term and ignore
the rest. This gives the bound
α
n−i+1
n−1
α
2α
···
<
<
.
α+n−iα+n−i+1
α+n−1
n − (n/2) + 1
n
Ignoring
R n 1 the product outside of it, the sum can be compared to the integral
dx to prove it is O(log(j)/j). Thus the expression in (16) is Õ(1/nj).
1 x(x+j)
Rather than using the rough bound from above, the full ` = n − j − i + 1 term is
2
ξn−j−i+1 (1 − ξn−j−i+2 ) · · · (1 − ξn−i )ξn−i+1
(1 − ξn−i+2 ) · · · (1 − ξn ).

The expectation of this term is


n−i
Y
α
α
k−1 

α+n−j−i
α+k−1 α+n−i
k=n−j−i+2

n
Y
k=n−i+2

k−1
α+k−1

!
.

But this is just
α
α+n−i
α
P[Jn = j + i] =
P[Jn = j + i]
α+n−i n−i
n−i
2α
≤
P[Jn = j + i].
n
Then by Lemma 10 (11) we have the bound
P[Jn = j + i] = O(n−α/(1+α) ).
Thus this term is O(i−1 j −α/(1+α) ), and
(17)

E[xw] = Õ(i−1 j −α/(1+α) ).

Pn−i
Term yw: Because i < j the term ξn−j+1 (1 − ξn−j+2 ) · · · (1 − ξn ) `=1 ξ` ξ`+i behaves
differently than the case just prior. In fact, it is the largest order term amongst the
four. The first step is the same as before though. A few of the terms are identically
zero. So, we can write yw as
ξn−j+1 (1 − ξn−j+2 ) · · · (1 − ξn )

n−i−j+1
X

ξ` ξ`+i .

`=1

Except for when ` = n − i − j + 1, all of the indices now disjoint. When we take
expectation of the terms with disjoint indices we obtain
n−j−i
X
n−j+1
n−1
α2
α
···
.
α+n−j α+n−j+1
α+n−1
(α + ` − 1)(α + ` + i − 1)
`=1

Notice that j could be quite large. The best bound we have for the product outside
the sum comes from (11). This implies it is O(n−α/(1+α) ). As with (16), the sum
term is O(log i/i). This yields that the whole expression is Õ(i−1 j −α/(1+α) ).
As before, the full ` = n − i − j + 1 term is
2
ξn−i−j+1 (1 − ξn−j−i+2 ) · · · (1 − ξn−j )ξn−j+1
(1 − ξn−i+2 ) · · · (1 − ξn ).

The expectation of this term is



n−j
Y
α
k
−
1
α



α+n−j−i
α+k−1 α+n−i
k=n−j−i+2

n
Y
k=n−j+2


k−1 
.
α+k−1

EWENS SAMPLING AND INVARIABLE GENERATION

15

This simplies to
α
α+n−j
α
P[Jn = j + i] =
P[Jn = j + i].
α+n−j n−j
n−j
By construction i ≤ n − j, and again by Lemma 10 (11), we have that P[Jn =
j + i] = O(n−α/(1+α) ). Thus this term has expectation that is O(i−1 j −α/(1+α) ). It
follows that
E[yw] = Õ(i−1 n−α/(1+α) ).

(18)

Term yz: The last step is to bound the product
n−i
X

(19)

ξk ξk+i

n−j
X

k=1

 n−i,n−j
X
ξ` ξ`+j =
ξk ξk+i ξ` ξ`+j .
k,`=1

`=1

Call the index set Λ = {(k, `) : k ∈ [1, . . . , n − i], ` ∈ [1, . . . , n − j]}. As i < j, we can
divide Λ into disjoint sets
Λ0 = {k, k + i, `, and ` + j are all distinct},
Λ1 = {k = `},
Λ2 = {k = ` + j},
Λ3 = {k + i = `},
Λ4 = {k + i = ` + j}.
This yields the following upper bound on (19):
X
X
X
X
X
ξk ξk+i ξ` ξ`+j +
ξk ξk+i ξ`+j +
ξk ξk+i ξ` +
ξk ξk+i ξ`+j +
ξk ξk+i ξ` .
Λ0

Λ1

Λ2

Λ3

Λ4

The payoff of this partition is that each product of ξ above is of distinct, independent
terms. This lets us tidily compute the expectation of each. For (k, `) ∈ Λ0 we have
the k, k + i, `, ` + j are all distinct. This gives
E[ξk ξk+i ξ` ξ`+j ] ≤

A
k(k + i)`(` + j)

for some constant A depending only on α. We can take the expectation of the entire
sum
E

X

ξk ξk+i ξ` ξ`+j ≤

Λ0

n
X

E[ξk ξk+i ξk+j ] ≤

k=1,`=1

n
X
k=1,`=1

A
= Õ(1/ij).
k(k + i)`(` + j)

We can parametrize Λ1 by k to write it as Λ1 = {(k, k) : k = 1, . . . , n − j}, this
gives the bound
E

X
Λ1

ξk ξk+i ξ`+j ≤

n
X
k=1

E[ξk ξk+i ξk+j ] ≤

n
X
k=1

A
= Õ(1/ij).
k(k + i)(k + j)

We can similarly parametrize the sums over Λ2 , Λ3 and Λ4 to obtain
(20)

E[yz] = Õ(1/ij)

16

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

All of the expressions at (15), (17), (18), and (20) are Õ(i−1 j −α/(1+α) ). Markov’s
inequality yields
P[Ci Cj > 0] = Õ(i−1 j −α/(1+α) ).

(21)

This proves the claimed inequality.



We also need a bound on the probability that cycles of the same size occur.
Lemma 12. For any i ≤ n it holds that
P[Ci ≥ 2] = Õ(i−2 + n−1−α/(1+α) ).
Proof. We start by bounding P[Ci > 2]. By (8) we have
P[Yi + 1{Jn = i} > 2] ≤ P[Yi > 1] = O(1/i2 ).

(22)

It remains to bound P[Ci = 2]. Conditioning on the value of Jn , we obtain the decomposition
(23)

P[Ci = 2] = P[Ci = 2 | Jn = i]P[Jn = i] + P[Ci = 2 | Jn 6= i]P[Jn 6= i].

First we estimate the first summand on the right hand side of (23). Because two cycles larger
than n/2 cannot occur, we must have i ≤ n/2. Then by Lemma 10 (9), P[Jn = i] ≤ 2α/n.
When Jn = i, it ensures that the sequence ξ1 , . . . , ξn has ξn−i+1 = 1 and the larger index ξk
are zero. The smaller index ξi are independent of this event. The value of Ci conditioned on
Jn = i is thus one more than the number of i-spacings in the sequence
ξ1 , . . . , ξn−i , 1,
with ξ1 , . . . ξn−i independent and distributed ESF (α, n − i). Call the number of i-spacings
in the above sequence Ci− . So, conditional on Jn = i we have Ci = Ci− + 1. By writing
explicitly what it means for an i-spacing to arise, we can bound Ci− in terms of the ξk :
Ci− ≤ ξn−2i+1 (1 − ξn−2i+2 ) · · · (1 − ξn−i ) +

n−2i
X

ξk ξk+i .

k=1

Looking to apply Markov’s inequality, we take the expectation of the above line and obtain
ECi− ≤

n−2i
X
n − 2i + 1
n−i−1
α2
α
···
+
.
α + n − 2i α + n − 2i + 1
α+n−i−1
(α + k − 1)(α + k − 1 + i)
k=1

The product above is equivalent to P[Jn−i = i], then we use Lemma 10 (11) and the fact
that i < n/2 to bound it by Õ((n − i)−α/(1+α) ) = Õ(n−α/(1+α) ). The sum, as we have seen
from (16), has order Õ(1/i). Recalling that (9) implies P[Jn = i] = O(1/n), it follows that
(24)

P[Ci = 2 | Jn = i]P[Jn = i] = Õ(n−1−α/(1+α) + 1/in) = Õ(i−2 + n−1−α/(1+α) ).

Now we estimate the second summand on the right hand side of (23). Under the event
{Jn 6= i}, for Ci to equal 2, it is necessary that two i-spacings occur in the infinite sequence
ξ1 , ξ2 , . . . . The count of i-spacings is distributed as Yi from (8). Therefore,
(25)

P[Ci = 2 and Jn 6= i] ≤ P[Yi ≥ 2] = O(1/i2 ).

Then (22), (24), and (25) imply that
(26)

P[Ci ≥ 2] = Õ(i−2 + n−1−α/(1+α) )

as desired.
Using the previous two lemmas we may prove the following.



EWENS SAMPLING AND INVARIABLE GENERATION

17

α
Proposition 13. Let π ∼ ESF (α, n) and a = 1 − 4α+3
. The probability that π has two
cycles whose lengths have a common divisor larger than na is o(1).

Proof. Call Ea the event that π has two cycles with common divisor larger than na . We
utilize a union bound, then apply Lemma 11 and Lemma 12 to write
P[Ea ] ≤

1−a
bnX
c
n
X

d=dna e

= Õ

bn1−a c

P[Cid Cjd > 0] +


P[Cid ≥ 2]

i=1

1≤i<j

 X
n

X

bn1−a c

X

(id)

−1

−α/(1+α)

(jd)

n
X

+

d=dna e 1≤i<j

d=dna e

bn1−a c 

X
i=1

1
+ n−1−α/(1+α)
(id)2


.

Since d ≥ na the above line is


Õ n1 n2(1−a) n−a−aα/(1+α) + n1 n1−a n−2a + n1−a−α/(1+α) .
We can simplify the exponents in each term to
3 − 3a − aα/(1 + α),

2 − 3a,

and

1 − a − α/(1 + α),

respectively. Some algebra shows that all are negative as long as a > 1 −
we have P[Ea ] = o(1).

α
4α+3 .

For such a


3.2. Proofs of Theorem 3, Theorem 4, and Theorem 5. We now have enough to
establish our bound on the minimal degree of an ESF(α, n) permutation.
Lemma 14. Let π ∼ ESF(α, n). For each 0 < β < 1, there exists λ ∈ (0, 1) such that if we
define the set
Qn = {d < nβ : there exists a prime p > nλβ with p | d},
then
(27)

P[∃Cd = 1 with d ∈ Qn ] = 1 − o(1).

Proof. We start with [ABT00, Theorem 3.1] which implies
X
TV
(28)
Cd → Poi(κn ),
d∈Qn

where
κn =

X α
.
d

d∈Qn

Borrowing an argument from [Bov80, p. 50] we have
X 1
X 1
X
1
=
−
d
d
d
β
β
d∈Qn

d<n

≥

d<n
p|d⇒p≤nλβ

X 1
Y
−
(1 − 1/p)−1
d
β
λβ

d<n

p≤n
∗

= β log n − eγ λβ log n + O(1)

18

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY
∗

where γ ∗ is Euler’s constant. When λ is such that eγ λβ < β/2 we have λn > β2 log n for all
n. It follows from (28) and standard estimates on the concentration of a Poisson random
variable that
X
P[
Cd > (β/4) log n] → P[Poi(λn ) > (β/4) log n] = 1 − o(1).
d∈Qn

To obtain (27), observe that the convergence statement in [ABT00, Theorem 3.1] implies
that P[Cd > 1] → P[Yd > 1] = O(1/d2 ). Here Yd is a Poisson random variable as inP
(8). The
Borel-Cantelli lemma implies that only finitely many Yd are larger than 1. Hence Yi >1 Yi
is almost surely bounded. We have seen that, for n large, the sum of Cd with d ∈ Qn is at
least Poi( β4 log n) with probability 1 − o(1). This diverges, and so one or more of the positive
Cd must be equal to one. Our claim follows.

Qn C`
For a random permutation π ∼ ESF(α, n), we define Φ(π) = `=1 ` . To prove
Theorem 4, it suffices to show that with high probability π has a cycle of length d such that
(29)

d ≤ nβ ,

(30)

d2 - Φ(π).

To that end we establish one more lemma.
Lemma 15. Let π, β, λ, and Qn be as in Lemma 14, then
(31)

P[∃d ∈ Qn such that d2 - Φ(π) and Cd = 1] = 1 − o(1).

Proof. Call the event in (31) Fn . Conditioning on the event that Cd = 1 for some d ∈ Qn ,
P[Fn ] ≥ P[Fn | ∃Cd = 1, d ∈ Qn ]P[∃Cd = 1, d ∈ Qn ].
By Lemma 14 we have that P[∃Cd = 1, d ∈ Qn ] = 1 − o(1), so it suffices to show that
P[Fn | ∃Cd = 1, d ∈ Qn ] = 1 − o(1).
Fix d ∈ Qn with Cd = 1, we will prove
P[d2 | Φ(π)] = o(1).
From our construction of Qn , there exists a prime p > nλβ such that
Φ(π)
}.
d
For such prime number p, the event on the right hand side above satisfies
{d2 | Φ(π)} ⊂ {p |

n/p
X
Φ(π)
{p |
}⊂{
Cip > 1}
d
i=1

Call the last event Gn . The Feller coupling at (8) allows us to bound the probability by
(32)

P[Gn ] ≤ P

hdn/de
X

i
Yip + 1{Jn = ip} > 1 .

i=1

This, in turn, is bounded by
dn/pe
h
i
hdn/pe
i
X α
X
P Poi
>0 +P
1{Jn = ip} > 0 .
ip
i=1
i=1

EWENS SAMPLING AND INVARIABLE GENERATION

19

The mean of the above Poisson random variable is asymptotically bounded by α log(n/p)/p,
which is o(1) since p ≥ nλβ . This ensures that the left summand is o(1). To bound the right
summand we write
hdn/pe
i
X
X
X
P
1{Jn = ip} > 0 ≤
P [Jn = ip] +
P [Jn = ip] .
ip>n−nγ

ip≤n−nγ

i=1

We begin by bounding the first summand of the right hand side. By Lemma 10 (9),
b(n−nγ )/pc

X

X

P [Jn = ip] ≤

ip≤n−nγ

i=1

Z

n−nγ
p

α
n − ip

+1

≤
1



log n
p
= o(1).

α
dx
n − px


=O

The last line follows since p ≥ nλβ . For the second summand, from Lemma 10 (10) there
exists some constant c > 0 such that
X
X
P [Jn = ip] ≤
cn−α(1−γ)
ip>n−nγ

ip>n−nγ

≤ cnγ−λβ n−α(1−γ) .
The last line follows as there are at most nγ−λβ different values of i such that n−nγ < ip ≤ n.
We therefore have that


P[Gn ] = O nγ−λβ−α(1−γ) .
An easy calculation confirms that γ satisfying
γ<

α + λβ
1+α

is sufficient to ensure
P[Gn ] = o(1).
Choosing a suitable γ, it follows that
P[Fn ] = 1 − o(1),
completing our proof.

Proof of Theorem 4. By Lemma 15 with probability 1 − o(1) there exists a cycle length of
length d satisfying (29) and (30). When these conditions are met, for K = Φ(π)/d, we have
π K displaces d ≤ nβ elements. Thus, with high probability π has minimal degree no more
than nβ . This completes our proof.

it also
Proof of Theorem 5. The theorem statement is such that if it holds for ω(n), then
√
4
holds for any ω 0 (n) ≥ ω(n). So, it suffices to prove
the
statement
for
all
ω(n)
≤
log
n.
√
Fix such an ω(n) and set bn = n exp(−ω(n) log n). Let P be the set of all primes and
define Pn = P ∩ [bn , n]. Given p ∈ Pn let Ip = [1, 2, . . . , bn/pc] be the set of all i for which pi

20

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

is a multiple of p between p and n. We also introduce the entire collection of such multiples
smaller than n
[
Wn =
{(p, i) : i ∈ Ip }.
p∈Pn

It suffices to show that the event
En = {∃(p, i) ∈ Wn : ip | Φ(π)}
occurs with high probability. We can write En as a union of events,
[
(n)
{Cip > 0}.
En =
(p,i)∈Wn

Notice that any two numbers in the set of products
{ip : (p, i) ∈ Wn }
are different. To see this we argue by contradiction, suppose that ip = i0 p0 with p < p0 .
0
Because of primality,
this could only happen
if p0 | i. Thus
√
√
√ i ≥ p . Also note that our
4
0
assumption ω(n) ≤ log n ensures bn > n. Thus, p, p > n. These two inequalities give
√ √
ip ≥ p0 p > n n = n.
But ip > n is a contradiction, since our construction of Ip ensures that ip ≤ n.
We have now shownPthat the occurrence of En is equivalent to the sum of cycle counts
being positive: En = { Wn Cip > 0}. The Feller coupling (8) ensures that
X
X
(33)
Cip ≥ −Dn +
Yip ,
Wn

Wn

with Dn the total number of deletions. It follows that
X
(34)
P[En ] ≥ P[−Dn +
Yip > 0].
Wn

Using additivity of independent Poisson random variables, the sum on the right of (33) is
distributed as a Poisson with mean
bn/(p)c

µn,α =
(35)

X

X

p∈Pn

i=1

X log(n/(p))
p
p∈Pn

X 1
X log p 
= α log n
−
.
p
p

α/ip ≈ α

p∈Pn

p∈Pn

Lemma 16 shows that µn,α → ∞. To establish that (34) occurs with high probability, we
will show that the number of deletions, Dn , in the Feller coupling is unlikely to remove every
successful Yip in (33).
As µn,α → ∞, we take any h(n) = o(µn,α ) with h(n) → ∞. By Lemma 10 (12) we know
that EDn ≤ c for some c = c(α). It follows from Markov’s inequality that
c
P[Dn ≥ h(n)] ≤
= o(1).
h(n)
Standard estimates on a Poisson random variable tell us that
P[Poi(µn,α ) ≤ h(n)] = 1 − o(1).
P
So Dn is with high probability smaller than Wn Yip , and combined with (33) we have
established that the right side of (34) occurs with high probability.


EWENS SAMPLING AND INVARIABLE GENERATION

21

Lemma 16. Let µn,α be as in the proof of Theorem 5. It holds that µn,α → ∞.
Proof. It suffices to show that (35) tends to infinity. Two classical theorems attributed to
Euler ([Eul37]) and Chebyshev ([Apo76]), respectively, state that for sums of primes smaller
than n
X1
X log p
= log log n + O(1) and
= log n + O(1).
p
p
p≤n

p≤n

Recalling that Pn = P ∩ [bn , n], it follows that (35) is asymptotic to
log n log

n
log n
− log .
log bn
bn

We can express the second term precisely


p
p
n
(36)
log
= log exp ω(n) log n = ω(n) log n.
bn
Similarly we compute the order of the first term. Notice


log n
log n
√
log
= log
log bn
log n − ω(n) log n
√


ω(n) log n
√
= log 1 +
(37)
.
log n − ω(n) log n
√
As ω(n) ≤ 4 log n the above term is log(1 − o(1)). Using the fact that log(1 − x) ≈ −x as
x → 0 we have (37) is asymptotic to
√
ω(n) log n
√
.
log n − ω(n) log n
Reintroducing the log n factor, we now have
(38)

log n

√
ω(n) log n
√
≈ log n
.
p
log n − ω(n) log n

X1
Pn

Combining (36) and (38) gives
√
p
ω(n) log n
√
− ω(n) log n
log n − ω(n) log n
log n
√
= ω(n)2
log n − ω(n) log n

µn,α ≈ log n

= ω(n)2 (1 − o(1))
Since ω(n) → ∞ we conclude that µn,α → ∞.

Now we set our sights on proving Theorem 3. This will require Theorem 4 and Theorem 5,
as well as a few additional lemmas.
Lemma 17. Let 0 < γ < 1 and ψ(n) → ∞ such that ψ(n) = o(log n). The probability that
simultaneously for all 2 ≤ r ≤ exp(ψ(n)) there exists Cjr > 0 such that jr > nγ and r - jr is
1 − o(1).

22

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

Proof. Let r0 = exp(ψ(n)) and consider the complement of the event in question:
E = {∃r < r0 : r | j for all nγ < j such that Cj > 0}.
It suffices to show that P[E] = o(1). In order to model the values Cj with independent
Poisson random variables we will work with a larger event. For any γ < γ 0 < 1, we consider
0

Eγ 0 = {∃r < r0 : r | j for all nγ < j < nγ such that Cj > 0}.
A union bound leads to
P[Eγ 0 ] ≤

r0
X

0

P[r | j for all nγ < j < nγ such that Cj > 0]

r=2

(39)

=

r0
X

0

P[Cj = 0 for all nγ < j < nγ such that r - j].

r=2
0

Let Ar be the set of integers in (nγ , nγ ] that r fails to divide. Formally,
0

Ar = [nγ , nγ ] ∩ ([n] \ {ir : i ≤ bn/rc}).
0

0

TV

0

As nγ = o(n) we can apply [ABT00, Theorem 3.1] to conclude that C[nγ , nγ ] → Y [nγ , nγ ].
Thus, the probabilities at (39) converge to
r0 Y
r0
 X α
X
X
P[Yj = 0] =
exp −
(40)
.
j
r=2 j∈Ar
r=2
j∈Ar
P
P
The quantity j∈Ar αj is minimized at r = 2, and in this case j∈A2 1j  log n. We can
apply this to (40) to obtain
P[Eγ 0 ] ≤

r0
X

n−δ ≤ r0 n−δ = o(1),

r=2

for some δ > 0. As E ⊆ E , this completes the proof.
γ0



Lemma 18. Let δ = δ(ε, α) = 1 − (α + ε) log 2. For any ε > 0, there exists a constant
c = c(ε, α) such that the probability of π fixing a set of size k is bounded by ck −δ uniformly
for all 1 ≤ k ≤ n/2.
Proof. In Lemma 22 we show that P[k ∈ L(X(α))] ≤ Ck −δ for some C and all k ≤ n. The
Feller coupling lets us relate the probability of a fixing a set size to this quantity, the only
complication is a possible contribution from 1{Jn = `}. However, the location of this extra
cycle is unconcentrated enough to not alter the order of these probabilities.
α
Lemma 10 (9) ensures that P[Jn = `] ≤ n−`
. We make use of this as we condition on the
value of Jn .
X
(41)
P[π has a k-cycle] ≤ P[k ∈ L(X(α))] +
P[k − ` ∈ L(X(α))]P[Jn = `]
`≤k

(42)

≤ Ck −δ +

X

C(k − `)−δ

`≤k

(43)

≤ Ck −δ +

2α X −δ
C`
n
`≤k

≤ Ck −δ + C 0 n−δ .

α
n−`

EWENS SAMPLING AND INVARIABLE GENERATION

23

Where at (42) we use our bound on P[k ∈ L(X(α))] from Lemma 22 and bound P[Jn = `]
with Lemma 10 (9). The next line, (43), reindexes the sum and uses that ` ≤ n/2 to bound
α
−δ
time some
n−` ≤ 2α/n. Our claim then follows by bounding the leftmost sum by n
0
−δ
−δ
constant C , and the fact that k > n .

We now prove a result analogous to [LP93, Theorem 1]. Namely, that if a permutation
sampled according to Ewen’s sampling formula is in a transitive subgroup, this subgroup is
likely to be either all of Sn or the alternating group, An . Though the lemmas culminating
to this used rather different arguments, our proof from here closely follows that in [LP93].
Recall that a primitive subgroup is a transitive subgroup that does not fix any partition of
[n].
Proof of Theorem 3. Let π ∈ G for a transitive subgroup G. According to [GM98], it follows
from results√of [Bab81] that the minimal degree of a primitive subgroup not containing An
is at least ( n − 1)/2. On the other hand, by Theorem 4 with high probability the minimal
degree of hπi is less than n0.4 . Thus, the probability that G is primitive is o(1).
Assume G is a non-primitive, transitive subgroup. Then it must fix some partition {Bi }ri=1
of [n]. By transitivity every block in such a partition will be mapped to every other, thus
the partition must be into blocks of equal size, that is
n
|Bi | = .
r
Note that any cycle of a permutation that preserves this partition must have the same
number of elements in each block it acts on. We will use this to establish that any π ∈ G
with high probability cannot fix this partition for any r.
We consider three cases for the possibly amount, r, of blocks:
√
Case 1: 2 ≤ r ≤ r0 = exp(log log n log n) √
By Lemma 17 with ψ(n) = log log n log n, with high probability for every r there
exists there exists jr > n.99 such that π contains a cycle of length jr and r - jr . Fix
some r and jr , and let B be the union of all blocks this cycle acts upon. Because r
does not divide jr , B is a proper invariant subset of [n] with size sn/r, where s is
the number of blocks in B. By Lemma 18 this occurs with probability bounded by
r0 X
r
X

c(sn/r)−δ ≤ cr02 (n/r0 )−δ = o(1).

r=2 s=1

Case 2: r0 ≤ r ≤ n/r0
By Theorem 5, with high probability there exists a prime q > n/r0 that divides
Ω(π). Thus there exists a cycle of length j such that q | j. Let t ≤ r be the number
of blocks this cycle intersects. Because of the bounds on r we have
j
n
n
≤ |Bi | = ≤
< q.
t
r
r0
Since q divides j = t jt and jt < q by the above inequality, we must have that q | t.
However, the total number of blocks r satisfies
n
r<
<q
r0
so this is impossible.

24

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

Case 3: n/r0 ≤ r < n
Let a be as in√Proposition 13 and ε > 0 such that a + ε < 1. Using Lemma 17 with
ψ(n) = log log n log n one more time, we now find j > na+ε such that π contains a
cycle of length j and the blocks size, s = n/r does not divide j. Again, let B be the
union of blocks which intersect this cycle. Because the size of the blocks does not
divide j, this intersection is a proper subset of B. We conclude that π must contain
another cycle of length j 0 that intersects each block in B. Hence both cycle lengths j
and j 0 are divisible by the number of blocks in B. We bound the number of blocks,
|B|
j
na+ε
> >
> na .
s
s
s
However, by Proposition 13 with probability 1 − o(1) no two cycle lengths have a
common divisor greater than na . This completes our proof.

3.3. Proving Proposition 7. To rule out generating An we need an estimate that shows
an ESF(α, n) permutation is odd with probability bounded away from zero. Of course this
probability ought to converge to 1/2, but we were unable to find a proof. We make due with
an absolute lower bound.
Lemma 19. Let π ∼ ESF (α, n), then

inf min{P[π is odd], P[π is even]} ≥ min

n≥2

1
α
,
α+1 α+1


.

Proof. We will proceed by induction. It is straightforward to check via the Feller coupling
α
that an ESF(α, 2) permutation is odd with probability α+1
, and it is even with probability
1
α
1 − α+1 = α+1 .
Suppose that for 2 ≤ m ≤ n − 1, if πm ∼ ESF (α, m) then
min{P[πm is odd], P[πm is even]} ≥ ε,
for some yet to be determined ε > 0. Now, it suffices to prove that
min{P[π is odd], P[π is even]} ≥ ε.

(44)

Consider the sequence ξ1 , ξ2 , . . . of Bernoulli random variables for the Feller coupling. Recall
that Jn = (n + 1) − Rn , with Rn the index of the rightmost 1 in ξ1 , . . . , ξn . We will condition
on the value of Jn , but need to also take into account the parity of n.
n is odd: We condition on the value of Jn . For convenience let q` = P[Jn = `]. If Jn =
`, then ξn+1−` = 1 and we can view the beginning sequence ξ1 , . . . , ξn−` , 1 as
corresponding to a random permutation sampled with distribution ESF (α, n − `).
We denote such a permutation by πn−` . Noting that when Jn = n, π is a single
n-cycle and therefore even, it follows that
P[π is odd] =

n−3
X

P[πn−` is even]q` +

` odd

n−2
X

P[πn−` is odd]q` + qn−1 .

` even

By the inductive hypothesis
P[π is odd] ≥

n−2
X
`=1

εq` + qn−1 .

EWENS SAMPLING AND INVARIABLE GENERATION

25

Pn
Pn
Since 1 q` = 1 P[Jn = `] = 1, it suffices to prove that qn−1 ≥ ε(qn−1 + qn ).
Equivalently, this requires that (1 − ε)qn−1 ≥ εqn . Notice that
n
n
Y
Y
qn−1 = P[ξ2 = 1]
P[ξi = 0], and qn =
P[ξi = 0].
i=3

i=2

Much of this cancels when we solve (1−ε)qn−1 ≥ εqn , so we arrive at the requirement
(1 − ε)
The ratio
(45)

P[ξ2 =1]
P[ξ2 =0]

P[ξ2 = 1]
≥ ε.
P[ξ2 = 0]

= α, and thus we require
(1 − ε)α ≥ ε.

n even: The argument is similar. The key difference is that we instead need qn ≥ ε(qn−1 +qn ).
Rewriting as before this is the same as
(46)

εα ≤ (1 − ε).

After solving for ε in (45) and (46), we see that (44) holds whenever 0 < ε ≤ min

n

1
α
α+1 , α+1

o

.


Remark 20. When α = 1 this confirms the intuition that even and odd permutations occur
with probability 1/2 for all n ≥ 2.
Corollary 21. Let δ = δ(α, ε) and c = c(α, ε) be as in Lemma 18. It holds for all k ≤ n/2
that


α+1 α+1
−δ
P[π fixes a k-set | π is odd] ≤ ck · max
,
.
α
1
Proof. We start with the reformulation
P[π fixes a k-set | π is odd] =

P[π fixes a k-set and π is odd]
.
P[π is odd]

The numerator is bounded by P[π fixes a k-set] which is less than ck −δ by Lemma 18. We
bound the denominator way from zero by Lemma 19, completing our proof.

4. The upper bound for sα
We carry out the plan described in Section 1.4. First we bound the quenched probability
p̃k defined formally just below here. The proof is similar to [PPR15, Lemma 3.1]. We repeat
a selection of the details for clarity, and point out where the argument differs with general α.
Subsequently, we mirror [PPR15, Theorem 3.2] as we apply the Borel Cantelli lemma.
Recall the functions fk and gk from (5). Namely that fk is the number of available
summands smaller than k, and gk is the largest sum attainable with them. Also, define
τε := sup{k : fk ≥ (α + ε) log k},
τ := sup{n : gλk ≥ k},
j
k
k
where ε > 0 is yet to be chosen, but small, and λk := α log
k . The proofs of [PPR15, Lemma
2.1, Lemma 2.2] generalize in a straightforward way, so that T = T (ε, δ) := max{τε , τ } is
almost surely finite. As P[T > λk ] → 0, we define the quenched probabilities to avoid this
diminishing sequence of events
p̃k := P[T < λk and k ∈ L (X)].

26

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

Lemma 22. Suppose that α < 1/ log 2. For each ε > 0 there exists C = C(ε) such that for
all k ≥ 1,
p̃k (α) ≤ Ck −1+(α+ε) log 2 .
Proof. Fix ε > 0. Let Gk be the event that T < λk while also n ∈ L (X). Call a sequence
y = (y1 , y2 , . . .) admissible if it is coordinate-wise
less than or equal to X. When Gk occurs,
P
it is not possible for n to be a sum of j jyj for an admissible y with yj vanishing for j > λk .
P
Indeed, on the event Gk , we have j≤λk jXj < n. The event satisfying the following three
conditions contains Gk :
(i) fλk ≤ (α + ε) log λk .
(ii) gλk < n.
P
(iii) There is some k with k = j (yj0 + yj00 ) with y0 supported on [0, λk ] and y00 nonzero
and supported on [λk + 1, k] with both y0 and y00 admissible.
P
Define the probability p0k = P[fλk ≤ (α + ε) log λk and gλk < n and ` = j jyj0 ] where y0 is
P
admissible and supported on [1, λn ]. Also, define p00` = P[` = j jyj00 ] where y00 is admissible
and supported on [λk + 1, k]. Using independence we can obtain an upper bound on p̃k by
decomposing into these two admissible vectors:
k
X

p̃k ≤

p0k−` p00`

k=λk +1

(47)

k
X

≤

`=λk +1

!
p0k−`

max p00` .

λk ≤`≤k

The first factor above is (by Fubini’s theorem) equal to E|L (X) ∩ [0, λk ]|. Using the trivial
bound where we assume each sum from X is distinct, and that we are working on the event
fλk ≤ (α + ε) log λk we have
(48)

(α+ε) log 2

|L (X) ∩ [0, λk ]| ≤ 2Zm ≤ λk

.

We now bound the second term. We will show there exists a constant C such that
(49)

p00` ≤ C

log2 k
, for all ` ∈ [λk + 1, k].
k

Let H be the event that Xj ≥ 2 for some j ∈ [λk , k]. As P[Xj ≥ 2] ≤ α/j 2 we can write

(50)

P[H] ≤

k
X
j=λk

α/j 2 ≤ α/λk 

log k
.
k

P
The event that ` = j jyj00 for an admissible ` supported on [λk , k], but that H does not occur
P
is contained in the union of events Ej that Xj = 1 and ` = j = i iyi00 for some admissible
y00 supported on [λk , k] \ {j}. Using independence of Xj from the other coordinates of X,

EWENS SAMPLING AND INVARIABLE GENERATION

27

along with our description of what must happen if H does not, we obtain
k
X
1 00
p
j `−j

p00` ≤ P[H] +

j=λk

≤ P[H] +

k
1 X 00
p`−j
λk
j=λk


≤

(51)

log k 
1+
k

k
X


p00`−j  .

j=λk

It remains to bound the summation in the last factor. Here taking α 6= 1 is a minor
nuisance, but we circumvent any difficulties with the crude bound α ≤ 2. The idea is to use
the generating function
Y
F (z, X) :=
(1 + z j ).
j∈[λk ,k]:Xj =1
j

Writing [z ]F for the jth coefficient of F . Observe that this corresponds to forming j using
the j ∈ [λk , k] for which Xj = 1. It follows that
k
X

k
X

p00`−j ≤

j=λk


E [z `−j ]F (z, X) .

j=λk

Using that [z j ]F (z, X) ≤ F (1, X) we can bound the above line by EF (1, X). This is tractable
using independence of the Xj . Carrying the calculation out we obtain
EF (1, X) =

n
Y

E[1 + 1{Xj = 1}]

j=λk
k 
Y


α
j
j=λk


n
Y
2
1+
.
≤
j
=

1+

j=λk

The last term can be expanded and written as
k 2 + 3k + 2
k2
 2  log2 k.
2
λk + λk
λk
Combine this with (51) and we have

log k
log3 k
1 + log2 k 
.
k
k
This yields (49). To conclude we plug (48) and (49) into (47) and arrive at
p00` 

p̃k ≤ C(k − λk )(α+ε) log 2

log3 k
.
k

This is bounded above by a constant multiple of k −1+(α+2ε) log 2 , which, after swapping all
ε’s for ε/2, establishes the lemma.


28

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

Proposition 23. Let sα be as in Theorem 6 and h(α) be as in (4). For continuity points
of h it holds that sα ≤ h(α), and sα ≤ h(α) + 1 for all α.


Proof of Proposition 23. Fix a small ε > 0 and let sα,ε = (1 − (α − 2ε) log 2)−1 . Sample
sα,ε vectors X(1) , . . . , X(sα,ε ) and let T (X(1) ), . . . , T (X(sα,ε ) ) be the a.s. random times diss
tributed as T . Take T ∗ = max{T (X(i) )}1α,ε . By independence of the X(i) and the bound in
Lemma 22 we have the probability that T ∗ < λk and k ∈ L (X(i) ) for all 1 ≤ i ≤ sα,ε is at
most a constant multiple of k sα,ε (−1+(α+ε) log 2) . Our choice of sα,ε ensures that the exponent
is less than −1. The series is thus summable. It follows that finitely many k > T ∗ belong to
the intersection of the L (X(i) ). As T ∗ is almost surely finite (the proof of this can be found
in [PPR15, Section 2]), the result follows by letting ε → 0 so that sα,ε → h(α).

5. The lower bound for sα
Here we establish the lower bounds on mα .
Proposition 24. Let sα be as in Theorem 6 and h(α) be as in (4). For 0 ≤ α < 1/ log 2, it
holds that sα ≥ h(α). When α ≥ 1/ log 2 it holds that sα = ∞.
We prove this by a Fourier-analytic argument. We begin by considering continuity points
α of h, and set m = h(α). We then fix m i.i.d. Poisson vectors X(1) , . . . , X(m) .
Lemma 25. Let I = (0, k] and let ε > 0. Then the event
(m

)
[
mk
(i)
A=
L (I, X ) ⊂ 0,
αε
i=1
holds with probability P[A] ≥ 1 − ε.
Proof. This is a straightforward application of Markov’s inequality.
(i) ∞
Recall our notation that X(i) = Xj i=1 .



Lemma 26. Fix ε ∈ (0, 1/2). For any δ > 0, there is a constant C = C(ε, δ, m, α) such that
the event




X
(i)
(52)
E = E(ε, δ, m, α) := min
Xj ≥ (1 − δ)α log(k/`) − C ∀1 ≤ ` ≤ k
 i

`<j≤k

holds with probability P[E] ≥ 1 − ε.
We remark that this is a straightforward generalization of [EFG15a, Lemma 3.3].
Proof. In fact, we will take C  αδ1 2 log(m/ε) while ensuring that C ≥ 1. Note that the
claim holds vacuously when ` ≥ e−C k, so we need only consider the case ` < e−C k.
P
(i)
Fix 1 ≤ i ≤ m and let B denote the event that `<j≤k Xj < (1 − δ)α log(k/`) − 1 for
some ` ≤ e−C k. Writing `0 for the smallest power of 2 with `0 > `, we thus have
X
(i)
(53)
Xj ≤ α(1 − δ) log(k/`0 )
`0 <j≤k

on B.
Let D = {2i }i≥0 denote the set of non-negative powers of 2. From (53) it follows that
P
X
(i)
0
(54)
1B ≤
(1 − δ) `0 <j≤` Xj −α(1−δ) log(k/` ) .
`0 ≤2e−C k,
`0 ∈D.

EWENS SAMPLING AND INVARIABLE GENERATION
(i)

29

(i)

are independent and Poisson with mean EXj = αj . For a Poisson
P
(i)
variable P with mean λ, we have EaP = eλ(a−1) . Moreover, the sum `0 <j≤k Xj is Poisson
0
with mean α log(k/` ) + O(1). Taking expectations on both sides of (54) therefore yields
X
P[B] 
exp [−αδ − α(1 − δ) log(1 − δ)] log(k/`0 )
Each of the variables Xj

`0 ≤2e−C k,
`0 ∈D.

Near zero, −δ − (1 − δ) log(1 − δ) = −(1 + o(1))δ 2 . Therefore
X
2
2
P[B] 
(k/`0 )−αδ  e−αδ C ,
`0 ≤2e−C k,
`0 ∈D.

since the sum of the geometric series is bounded by a constant multiple of its first term.
ε
Choosing C  αδ1 2 log(m/ε) ensures that P[B] ≤ m
, and now the claim follows by the union
of events bound.

An insight in [EFG15a] (to which they credit the idea to Maier and Tenenbaum from
[MT84]) is that Fourier analysis may be used to obtain a lower bound on the size of the set
n
o
(55)
S(I; X(1) , . . . , X(m) ) := (ni − nm )1≤i<m : ni ∈ L (I, X(i) ) .
We show that the technique extends to the present level of generality. Note that the analysis
of [EFG15a] may be regarded as the special case m = 3 and α = 1 of our arguments.
Let T = R/Z be the unit torus. For θ ∈ T, let kθk denote the distance to Z and set
e(z) = e2πiz . Write θ = (θ1 , . . . , θm ) ∈ Tm . Define
m
Tm
0 = {θ ∈ T : θ1 + · · · + θm = 0}.


Fix an interval I. We define the function F (θ) = FI θ, X(1) , . . . , X(m) via the formula
(i)

(56)

F (θ) :=

Xj
m 
YY
1 + e(jθi )
j∈I i=1

2

.

Writing θm = −θ1 − · · · − θm−1 , we regard F (θ) as a function on Tm−1 . It is straightforward
to verify that its Fourier transform is a function F̂ : Zm−1 → C supported on the set
S(I; X(1) , . . . , X(m) ) defined above in (55).
The Cauchy-Schwarz inequality yields that
"
#2
X
X
X
2
(57)
|F̂ (a)|
1≥
F̂ (a) .
a∈Zm−1

a : F̂ (a)6=0

a∈Zm−1

P
Recognizing that S(I; X(1) , . . . , X(m) ) ≥ {a : F̂ (a) 6= 0} , that a∈Zm−1 F̂ (a) = F (0) = 1,
R
P
and that by Parseval’s identity a∈Zm−1 |F̂ (a)|2 = Tm |F (θ)|2 dθ, it follows from (57) that
0
!−1
Z
(58)

|S(I; X(1) , . . . , X(m) )| ≥

|F (θ)|2 dθ

.

Tm
0

Our next task is to bound the integral appearing in (58). We will achieve this in two
steps: first, by obtaining a pointwise bound with respect to θ in Lemma 27, and second, by
integrating out the θ dependence in Corollary 28.

30

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

Let β ∈ (0, 1) be a real parameter satisfying
βα log 2 = 1 − m−1 + δ2 ,
where δ2 > 0 and δ2 = oδ (1) is the parameter occurring in (52). (Note that this is possible
since α is a continuity point of h, so m < (1 − α log 2)−1 .) Recall the event E = E(ε, δ, m, α)
from Lemma 26.
Lemma 27. Fix ε ∈ (0, 1/2) and let I denote the interval I := (k 1−β , k]. For a tuple
θ = (θ1 , . . . , θm ), let j(θ) denote an index for which kθj k is maximal. Then
Y
(59)
EX(1) ,...,X(m) 1E |F (θ)|2 ε,m
(kk θi k ∨ 1)−1+δ2 .
i : 1≤i≤m,
i6=j(θ)

Proof. For each 1 ≤ i ≤ m, set ti := k θi and

β

k ,
ki := kti k,


1,

define the cutoff parameter
kti k ≥ k β
1 < kti k < k β
kti k ≤ 1.

Note that ki ≥ 1 and ki ≥ kti kβ . For each 1 ≤ i ≤ m, let Yi denote the expression
X
(i)
Yi :=
Xj .
ki <j≤k

By definition of the event E, when it occurs we have that
m
m
X
X
Yi ≥ α(1 − δ)
log ki − C(ε).
i=1

i=1

It will be convenient to rewrite this bound in the form
m
m
Y
Y
−α(1−δ) log 2
(60)
1E ε
ki
2 Yi .
i=1

i=1

We define the quantity
(61)

m
Y

R = R θ, X(1) , . . . , X(m) , ε, δ, α := |F (θ)|2
2 Yi .
i=1

To establish the bound (59), we will first show that EX(1) ,...,X(m) R ε,m 1. Once this has
been established, it will follow directly from (60) that
m
Y
−α(1−δ) log 2
(62)
E1E |F (θ)|2 ε,m
ki
.
i=1

Obtaining (59) from (62) is a simple exercise in lower bounding the maximum of a sequence
by its geometric mean. Recalling the definition of j(θ) above, we have that
Y
1
kj(θ) ≥
kim−1 .
i : 1≤i≤m,
i6=j(θ)

Consequently
(63)

m
Y
i=1

−α(1−δ) log 2

ki

≤

Y
i : 1≤i≤m,
i6=j(θ)

m
− m−1
α(1−δ) log 2

ki

.

EWENS SAMPLING AND INVARIABLE GENERATION

31

β
Substituting the lower bound ki ≥ kk θi k ∨ 1 into (63), we see that (62) implies
Y
− m αβ(1−δ) log 2
E 1E |F (θ)|2 ε,m
,
kk θi k ∨ 1 m−1
i : 1≤i≤m,
i6=j
m
αβ(1 − δ) log 2 = 1 + oδ (1) by definition of β, the desired bound follows.
and since m−1
Finally we justify that EX(1) ,...,X(m) R ε,m 1. Substituting (56) into (61) yields that


(i)
m
Y
Y 1 + e(jθi ) 2Xj
.
2Yi
R=
2
i=1
j∈I

Recall that Yi =

(i)

P

R=

ki <j≤k

m
Y

Xj

and that I = (k 1−β , k]. Thus



(i)

Y


i=1

k1−β <j≤ki

1 + e(jθi )
2

2Xj

(i)

Y
ki <j≤k

1 + e(jθi )
√
2

2Xj


.

To compute ER, we recall that if P is a Poisson random variable with mean λ, then
(i)
log EaP = eλ(a−1) . Since the variables Xj are independent Poisson variables with mean
(i)

EXj =
(64)

α
j,

it follows after some simplification that



m
X
X
X α cos(2πjθi )
α cos(2πjθi ) − 1

.
+
ER = exp
2j
j
1−β
i=1
k

ki <j≤k

<j≤ki

Next we apply the following bound from [EFG15a, Lemma 3.4]:
X cos(2πjθ)
(65)
= log min(k, kθk−1 ) + O(1).
j
j≤k

Substituting into (64) yields that

m 
X
1
k β ∨ kk θi k 1
kβ
ki ∨ kk θi k
ER = exp α
log
− log
+ O(1) .
+ log
2
ki ∨ kk θi k
2
ki
1 ∨ kk θi k
i=1
By definition of ki , each summand is O(1). Therefore ER ε,m 1, as desired.



Finally we integrate the bound (59) with respect to θ to obtain a bound on the integral
appearing in (58).
Corollary 28. Let I = (k 1−β , k] and recall the function F (θ) = FI (θ) from (56). Then
Z
E1E |F (θ)|2 dθ ε,m k 1−m .
Tm
0

Proof. After the change of variables t = kθ, the bound reduces to verifying that
Z
E1E |F (θ)|2 dt ε,m 1.
k·Tm
0

Applying Lemma 27, we have
Z
Z
(66)
E1E |F (θ)|2 dt ε,m
k·Tm
0

Y

k·Tm
0 i : 1≤i≤m,
i6=j(t).

−(1+δ2 )
kti k ∨ 1
dt.

32

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

By symmetry, we may upper bound the integral (66) by
Z
(67)

m

m−1
Y

kti k ∨ 1

−(1+δ2 )

Z

!m−1

k/2

(|ti | ∨ 1)

dt = m

k·Tm
0
i=1

−(1+δ2 )

dti

.

−k/2

The rightmost integral in (67) is bounded above by
 Z ∞
m−1
−(1+δ2 )
m 2
ti
dti + 2
.
1

The desired result now follows since the latter integral is finite and independent of k.



Substituting the result of Corollary 28 into (58) lets us show |S(I; X(1) , . . . , X(m) )|  k m−1
with high probability.
Proposition 29. Let I = (k 1−β , k]. With probability greater than 1/2, S(I; X(1) , . . . , X(m) ) ⊂
[−ck, ck]m−1 for some constant c and |S(I; X(1) , . . . , X(m) )|  k m−1 .
Proof.
L (I, X(i) ) ⊂
 3mk By
 Lemma 25 with ε = 1/3, with probability greater than 2/3 we have
(1)
⊂ [0, ck] for some constant c and all i. It follows that S(I; X , . . . , X(m) ) ⊂
0, α
m−1
[−ck, ck]
.
By Lemma 26 with ε = 1/20, the event E(ε, δ, m, α) holds with probably greater 19/20
and by Corollary 28,
Z
E1E |F (θ)|2 dθ ε,m k 1−m .
Tm
0

It follows by Markov’s inequality that for some sufficiently large L,
"(Z
)c #
" Z
#
2
1−m
c
2
1−m
P
|F (θ)| dθ  k
≤ P [E ] + P 1E
|F (θ)| dθ > Lk
Tm
0

Tm
0

E1E Tm |F (θ)|2 dθ
1
0
+
20
Lk 1−m
1
≤
.
10
It then follows from (58) that with probability at least 9/10,
!−1
Z
R

≤

|S(I; X(1) , . . . X(m) )| ≥

|F (θ)|2 dθ

 k m−1 .

Tm
0

Both events then occur simultaneously with probability at least 1/2, completing our
proof.

Proposition 30. Let D be sufficiently large constant
and I = (k 1−β ,Dk]. With probability

(i)
bounded away from zero there exists an array xj : 1 ≤ i ≤ m, j ∈ I for which
(i)

(i)

0 ≤ xj ≤ Xj
for all i and j ∈ I, and
X
j∈I

(1)

jxj

= ··· =

X
j∈I

(m)

jxj

.

EWENS SAMPLING AND INVARIABLE GENERATION

33

Proof. We define the interval I 0 = (k 1−β , k]. By Proposition 29 with probability greater
than 1/2
S(I 0 ; X(1) , . . . , X(m) ) ⊂ [−ck, ck]m−1
and |S(I 0 ; X(1) , . . . , X(m) )|  k m−1 .
Let d = 2(5/2)1/α . Straightforward calculations tell us that independently with probability
(m)
greater than 1/2 there exists jm ∈ (2ck, cdk] such that Xjm > 0. Given this jm , there are
 k m−1 collections of constants {j` }m−1
∈ (ck, (d + 1)ck]m−1 such that
1
(jm − j1 , . . . , jm − jm−1 ) ∈ S(I 0 ; X(1) , . . . , X(m) ).
Therefore, independently with probability bounded away from zero, there is one such
(`)
collection {j` }m−1
such that Xj` > 0 for all `.
1
m
By the definition of S(I 0 ; X(1) , . . . , X(m) ) we have a set of values ni ∈ L (I 0 , X(i) ) i=1
such that
m−1
(n1 − nm )1
= (jm − j` )m−1
.
1
Manipulating the terms coordinate-wise yields
j1 + n1 = · · · = jm + nm .
Our claim follows by setting D = (d + 1)c.
Tm
Corollary 31. i=1 L (X(i) ) is almost surely infinite.



Proof. We define k1 to be sufficiently large for Proposition 30 to hold, then inductively define
1/(1−β)
ki+1 = (Dki )
. The intervals Ii = (ki1−β , Dki ] are pairwise disjoint and the set
m
\

L (Ii , X(j) )

j=1

is non-empty with probability bounded away from zero. Since these events are independent
for distinct values of i, the claim now follows from the second Borel-Cantelli lemma.

Proof of Proposition 24. As we had fixed m = h(α), by Corollary 31 sα ≥ h(α) holds
for continuity points of h. For points of discontinuity, we fix α0 < α such that h(α0 ) =
(m)
h(α) = m. We couple two sets of independent realizations X(1) (α),
Tm. . . , X (i)(α)0 and
(1)
0
(m)
0
(i)
0
(i)
X (α ), . . . , X (α ) such that X (α ) ⊆ X (α) for all i. Now i=1 L (X (α )) is
almost surely finite by Corollary 31. Our coupling ensures L (X(i) (α0 ) ⊆ L (X(i) (α)) for all
Tm
Tm
0
i, so i=1 L (X(i)(α ) ) ⊆ i=1 L (X(i) (α)). Thus the second intersection is almost surely
infinite, and our claim follows.

Proof of Theorem 6. This now follows immediately from Proposition 23 and Proposition 24.

References
[ABT92]
[ABT00]
[ABT16]
[Apo76]

Richard Arratia, A. D. Barbour, and Simon Tavaré, Poisson process approximations for the
ewens sampling formula, Ann. Appl. Probab. 2 (1992), no. 3, 519–535.
R. Arratia, A. D. Barbour, and S. Tavaré, Limits of logarithmic combinatorial structures, Ann.
Probab. 28 (2000), no. 4, 1620–1644.
Richard Arratia, A. D. Barbour, and Simon Tavaré, Exploiting the feller coupling for the ewens
sampling formula, Statist. Sci. 31 (2016), no. 1, 27–29.
Tom M. Apostol, Introduction to analytic number theory, Undergraduate texts in mathematics,
Springer, New York, Berlin, Heidelberg, 1976, Autres tirages : 1984, 1986, 1995, 1998, 2010.

34

[AT92]

G. BRITO, C. FOWLER, M. JUNGE, AND A. LEVY

Richard Arratia and Simon Tavaré, The cycle structure of random permutations, Ann. Probab.
20 (1992), no. 3, 1567–1591.
[AT13]
, Independent process approximations for random combinatorial structures, arXiv preprint
arXiv:1308.3279 (2013).
[Bab81]
László Babai, On the order of uniprimitive permutation groups, Annals of Mathematics 113
(1981), no. 3, 553–568.
JD Bovey, The probability that some power of a permutation has small degree, Bulletin of the
[Bov80]
London Mathematical Society 12 (1980), no. 1, 47–51.
[BUV11]
Volker Betz, Daniel Ueltschi, and Yvan Velenik, Random permutations with cycle weights, Ann.
Appl. Probab. 21 (2011), no. 1, 312–331.
[Cra16a]
Harry Crane, Rejoinder: The ubiquitous ewens sampling formula, Statist. Sci. 31 (2016), no. 1,
37–39.
[Cra16b]
, The ubiquitous ewens sampling formula, Statist. Sci. 31 (2016), no. 1, 1–19.
[Dix92]
John D. Dixon, Random sets which invariably generate the symmetric group, Discrete Mathematics 105 (1992), no. 1, 25 – 39.
J.H. Davenport and G.C. Smith, Fast recognition of alternating and symmetric galois groups,
[DS00]
Journal of Pure and Applied Algebra 153 (2000), no. 1, 17 – 25.
[EFG15a] S. Eberhard, K. Ford, and B. Green, Invariable generation of the symmetric group, ArXiv
e-prints (2015).
[EFG15b] Sean Eberhard, Kevin Ford, and Ben Green, Permutations fixing a k-set, International Mathematics Research Notices (2015).
P Erdős and P Turán, On some problems of a statistical group-theory. ii, Acta Mathematica
[ET67]
Hungarica 18 (1967), no. 1-2, 151–163.
[EU14]
Nicholas M. Ercolani and Daniel Ueltschi, Cycle structure of random permutations with cycle
weights, Random Structures & Algorithms 44 (2014), no. 1, 109–133.
[Eul37]
Leonhard Euler, Observationes circa series, infinitas, Commentarii Academiae Scientarum
Petropolitanae 9 (1737), 160–188.
[Fel45]
William Feller, The fundamental limit theorems in probability, Bulletin of the American Mathematical Society 51 (1945), no. 11, 800–832.
[GM98]
Robert Guralnick and Kay Magaard, On the minimal degree of a primitive permutation group,
Journal of Algebra 207 (1998), no. 1, 127–145.
A. Gladkich and R. Peled, On the Cycle Structure of Mallows Permutations, ArXiv e-prints
[GP16]
(2016).
[Gra08]
Andrew Granville, The anatomy of integers and permutations, preprint.[Ack] (2008).
Joos Heintz, On polynomials with symmetric galois group which are easy to compute, Theoretical
[Hei86]
Computer Science 47 (1986), 99 – 105.
[KKRW15] R. Kenyon, D. Kral, C. Radin, and P. Winkler, Permutations with fixed pattern densities, ArXiv
e-prints (2015).
Tomasz Luczak and Lászlò Pyber, On random generation of the symmetric group, Combinatorics,
[LP93]
Probability and Computing 2 (1993), 505–512.
[Mal57]
C. L. Mallows, Non-null ranking models. i, Biometrika 44 (1957), no. 1/2, 114–130.
[MT84]
H. Maier and G. Tenenbaum, On the set of divisors of an integer, Inventiones mathematicae 76
(1984), no. 1, 121–128.
[Muk16]
Sumit Mukherjee, Fixed points and cycle structure of random permutations, Electron. J. Probab.
21 (2016), 18 pp.
[Mus78]
David R. Musser, On the efficiency of a polynomial irreducibility test, J. ACM 25 (1978), no. 2,
271–282.
[PPR15]
Robin Pemantle, Yuval Peres, and Igor Rivin, Four random permutations conjugated by an
adversary generate sn with high probability, Random Structures & Algorithms (2015), n/a–n/a.
[Wae34]
B.L. van der Waerden, Die seltenheit der gleichungen mit affekt, Mathematische Annalen 109
(1934), 13–16.

EWENS SAMPLING AND INVARIABLE GENERATION

Department of Mathematics, University of Washington
E-mail address: gerandy@math.washington.edu
Department of Mathematics, University of Washington
E-mail address: cff2008@math.washington.edu
Department of Mathematics, Duke University
E-mail address: jungem@math.duke.edu
Department of Mathematics, University of Washington
E-mail address: avius@math.washington.edu

35

