Journal de Théorie des Nombres de Bordeaux

Steffen Löbrich

A Gap in the Spectrum of the Faltings Height

Oleksiy Klurman

Marc Munsch

Oleksiy KLURMAN et Marc MUNSCH
Distribution of factorials modulo p
Tome 29, no 1 (2017), p. 169-177.
<http://jtnb.cedram.org/item?id=JTNB_2017__29_1_169_0>
© Société Arithmétique de Bordeaux, 2017, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.cedram.org/), implique l’accord
avec les conditions générales d’utilisation (http://jtnb.cedram.
org/legal/). Toute reproduction en tout ou partie de cet article sous
quelque forme que ce soit pour tout usage autre que l’utilisation à
fin strictement personnelle du copiste est constitutive d’une infrac-
tion pénale. Toute copie ou impression de ce fichier doit contenir la
présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Journal de Théorie des Nombres
de Bordeaux 29 (2017), 169–177
Distribution of factorials modulo p
par Oleksiy KLURMAN et Marc MUNSCH
Résumé. On s’intéresse à l’estimation du nombre de valeurs
prises par la suite n! (mod p). Principalement, on obtient en
moyenne sur les nombres premiers p ≤ x, une minoration du
nombre de classes modulo p évitées par la suite n! (mod p).
Abstract. We estimate the average number of residue classes
missed by the sequence n! (mod p) for p ≤ x.
1. Introduction
Following [7], for each odd prime p let V (H,N) denote the number of
distinct residue classes modulo p that are taken by the sequence {n!, n =
2, 3 . . . , p − 1}, H ≤ n ≤ H + N. Very little seems to be known about the
behaviour of V (H,N). P. Erdős conjectured that 2!, 3! . . . , (p − 1)! cannot
be all distinct modulo p, in other words V (0, p− 1) 6= p− 2. Although the
conjecture is open, B. Rokowska and A. Schinzel [16] proved that this con-
dition implies some restrictions on the values of p. This allows Trudgian to
verify that the conjecture holds true for p < 109 (see [18]). More generally,
the following asymptotic is conjectured in [9]:
V (0, p− 1) ∼
(
1− 1
e
)
p.
In [4], C. Cobeli, M. Vâjâitu and A. Zaharescu provide a strong sup-
port towards this conjecture (see also [2]). They proved that for a random
permutation σ of the set {1, · · · , p− 1}, the products{
n∏
i=1
σ(i), n = 1, · · · , p− 1
}
cover the expected number of residue classes. This implies in particular
that in case the sequence {n!, n = 2, 3 . . . , p − 1} did not satisfy Guy’s
observation then it would not, in some sense, be a “standard” sequence
amongst the set of all sequences of length p.
In a series of papers, [6], [7] and [8], M. Garaev, F. Luca and I. Shparlinski
initiated an extensive study of the distribution properties of n!(mod p). In
Manuscrit reçu le 27 mars 2015, révisé le 10 avril 2016, accepté le 13 avril 2016.
Mathematics Subject Classification. 11B50, 11B83, 11R09, 11R45.
Mots-clefs. Distribution of sequences mod p, polynomials, density results.
170 Oleksiy Klurman, Marc Munsch
particular, in [7] the authors remark that the only known lower bound for
V (H,N) is a trivial one, namely
V (H,N) ≥
√
N − 1.
Indeed, this immediately follows from the fact that the remainders n!(n−1)! =
n are all distinct for 1 ≤ n ≤ p− 1.
Motivated by this question, V. Lev considered a similar problem in every
finite abelian group G. He showed [14, Theorem 2] that there is a permu-
tation (g1, · · · , g|G|) of the elements of G such that the number of distinct
sums of the form
g1 + · · ·+ gj (1 ≤ j ≤ |G|)
is O(
√
|G|) and noticed that this is the smallest size possible. By fixing a
primitive root g modulo p and passing to indices with respect to g, the ques-
tion about the distribution of factorials reduces to considering the cyclic
group of order p− 1 and the permutation given by the indices. V. Lev ob-
serves that the conclusion one can draw concerning the sequence n! is of a
negative sort: in order to improve the lower bound on V (H,N), combina-
torics is not sufficient and one has to exploit the special properties of this
particular sequence.
In the preprint version of the present paper [11], we gave an elementary
way to obtain nontrivial lower bound on V (H,N) for all N  p
1
4 +ε proving
Theorem. The set of n! (mod p), H ≤ n ≤ H +N contains at least
√
3
2N
distinct values for all N  p
1
4 +ε.
This was subsequently improved by J. Hernandez and M. Garaev in [5].
In the other direction, it was proved in [1] that there exists infinitely many
primes p such that n!(mod p) omits at least
(1.1) p− V (0, p− 1) log log plog log log p
residue classes. Applying the method of [1] and replacing the unconditional
bound for the least prime ideal by the one derived in [13] using the Gener-
alized Riemann hypothesis (GRH) yields infinitely many primes such that
(1.2) p− V (0, p− 1) log plog log p ·
We remark that in [1], due to the use of the bound on the least prime
ideal from [12], one gets an extremely sparse set of primes satisfying (1.1)
and (1.2). We are going to prove an average analog of this result in the
following form.
Distribution of factorials modulo p 171
Theorem. We have
1
π(x)
∑
p≤x
(p− V (0, p− 1)) log log xlog log log x ·
Under GRH, we have the bound
1
π(x)
∑
p≤x
(p− V (0, p− 1)) x
1
4
log x ·
Thus, under GRH, our result immediately implies the existence of infin-
itely many primes with
p− V (0, p− 1) p
1
4
log p ·
2. Upper bound for V (0, p − 1) on average
As was mentioned in the introduction, it was proved in [1] that there
exists infinitely many primes p such that n! (mod p) omits at least
(2.1) p− V (0, p− 1) log log plog log log p
residue classes. In this section, we show that the number of “missing”
residue classes tends to infinity on average.
We fix a few notations. Let L/Q be a finite extension of degree nL. For
any ideal I of the ring of integers OL, we denote the norm of an ideal
by NL/Q(I) and write N(I). We also denote by f (p/p) the inertial degree
| [OL/p : Fp] | of the ideal p above the rational prime p. The function πL(x)
will count the number of prime ideals p such that N(p) ≤ x. Finally, denote
by dL the absolute discriminant of L.
Theorem 2.1. We have
1
π(x)
∑
p≤x
(p− V (0, p− 1)) log log xlog log log x ·
Proof. Let N be a parameter which will be determined later. For n ≥ 1 we
consider the family of polynomials
fn(t) = t(t+ 1) . . . (t+ n− 1)− 1.
It is well-known (see [15, 9, part viii, chapter 2, section 3, Pb 121] that
fn(t) is irreducible over Q for all n ≥ 1. Let ρn(p) denote the number of
roots of fn(t) modulo p. We observe that fn(t0) ≡ 0 (mod p) implies
(t0 + n− 1)! = (t0 − 1)! (mod p).
Therefore, each distinct root of fn(t) modulo p increases the number of
“missing” values by 1. We thus want to produce a lot of roots of fn for
many values of n.
172 Oleksiy Klurman, Marc Munsch
Let Kn = Q(α) be the extension of Q obtained by adjoining a root of
fn. By Ck we denote the subset of all non ramified primes in Kn such that
fn has exactly k roots modulo p. Observe, that
(2.2)
∑
p≤x
ρn(p) ≥
n∑
k=1
∑
p≤x
p∈Ck
k.
By Dedekind’s theorem, up to finitely many exceptions, the primes p such
that fn has a root modulo p correspond to the primes p such that there
exists a prime ideal p in OKn above p with inertial degree f (p/p) = 1.
Instead of working in the splitting field of fn and using Chebotarev’s
theorem as in [1], we will directly count prime ideals in Kn using prime
ideal theorem. By the standard argument, the prime ideals of degree > 1
will give negligible contribution. More precisely, we remark that counting
prime ideals in Kn of degree 1 is equivalent to counting the rational primes
p with weight k when fn has k roots modulo p. Thus, we have
(2.3)
n∑
k=1
∑
p≤x
p∈Ck
k =
∑
N(p)≤x
f(p/p)=1
1.
By the effective prime ideal theorem (see [10, Theorem 5.33])1, there
exists an absolute constant c > 0 such that for all n ≥ 1
(2.4)
∑
N(p)≤x
f(p/p)=1
1 = π(x) +O
Li(xβn) + xlog x exp
−c
√
log x
n2

where βn is the potential positive real zero of the Dedekind zeta function
ζKn and
0 < 1− βn 
1
log dKn
·
We now restrict ourselves to the family of polynomials {f2n+1, 1 ≤ n ≤ N} .
Recall that by the result of Stark [17, Lemma 8], we can control potential
Siegel zeroes provided that the original extension does not contain any
quadratic sub-extension. We do so here since K2n+1 = Q(α) is of an odd
degree. Latter yields the bound
(2.5) β2n+1 ≤ 1−
1
4(2n+ 1)! log |dK2n+1 |
·
1We could equally apply effective version of Chebotarev theorem [13] for the trivial extension
Kn/Kn.
Distribution of factorials modulo p 173
Using (2.2) together with (2.4), we derive
1
π(x)
∑
p≤x
(p− V (0, p− 1)) ≥
N∑
n=1
1
π(x)
∑
p≤x
ρ2n+1(p)
≥
N∑
n=1
1
π(x)
2n+1∑
k=1
k
∑
p≤x
p∈Ck
1(2.6)
≥ N + ET,(2.7)
where
ET = O
(
1
π(x)
{
N∑
n=1
Li(xβ2n+1) + xlog x exp
(
−c
√
log x
(2n+ 1)2
)})
·
Hence, we have to choose parameter N such that
(2.8) N 
N∑
n=1
1
π(x)
{
Li(xβ2n+1) + xlog x exp
(
−c
√
log x
(2n+ 1)2
)}
.
The sum of the exponential terms in (2.8) satisfies this as long as
N  log1/2 x.
Since K2n+1 is generated by the single root of f2n+1, we can bound its
discriminant by the discriminant of the polynomial f2n+1. Hence, denoting
by αi the roots of f2n+1 we derive
(2.9) dK2n+1 ≤
2n+1∏
i,j
i<j
|αi − αj |2  n10n
2
,
where we used the bound |αi − αj |  n which is proved in [1, Lemma 2].
To bound the contribution coming from the potential Siegel zeroes, we
apply the result of Stark (2.5) together with the discriminant bound (2.9)
to arrive at
(2.10)
N∑
n=1
1
π(x)Li(x
β2n+1)
N∑
n=1
x
− 1
n! log(nn2 )  Nx−
1
NN N2 .
Using the previous bound (2.10) and standard computations, we deduce
that inequality (2.8) is true as long as
(2.11) N  log log xlog log log x ·
We are left to note that the “bad” primes which do not satisfy Dedekind’s
theorem are exactly the primes dividing
[
OK2n+1 : Z [α]
]
. We have at most
174 Oleksiy Klurman, Marc Munsch
ω(2n+1)) logn of such primes and, using (2.11), their total contribution
is at most
1
π(x)
∑
n≤N
∑
p≤x
p ’bad’ for K2n+1
ρn(p)
1
π(x)
∑
n≤N
n logn N
2 logN
π(x) = o(N). 
Assuming the Generalized Riemann Hypothesis (GRH) the bound from
Theorem 2.1 can be significantly improved.
Theorem 2.2. Assume that GRH is true. Then,
1
π(x)
∑
p≤x
(p− V (0, p− 1)) x
1/4
log x ·
Proof. We consider as before the family of polynomials fn and the associ-
ated family of extensions Kn of degree n. Here, we do not need to restrict
to odd n because we use GRH instead of Stark’s result.
Following the same lines as in the proof of Theorem 2.1 and replacing
the error term in the prime ideal theorem by the conditional one, we obtain
(2.12)
∑
p≤x
ρn(p) ≥ π(x) +O
(
x
1
2 (log dKn + n log x)
)
.
Averaging over the family of polynomials {fn(x), 1 ≤ n ≤ N} and perform-
ing the same computation as in (2.6), we arrive at
1
π(x)
∑
p≤x
(p− V (0, p− 1)) ≥
N∑
n=1
1
π(x)
∑
p≤x
ρn(p) N + ET.
Using the discriminant bound (2.9) we can bound error term by
ET 
N∑
n=1
{
x−
1
2 log x(log(nn2) + n log x)
}
 log
2 x√
x
N3.
Easy computation shows that the error term is negligible compared to N
provided
N  x
1/4
log x,
and the result follows. As in the proof of Theorem 2.1, we can easily deal
with the additional restriction p - [OKn : Z [α]] .We bound the contribution
of “bad” primes in exactly the same way:
1
π(x)
∑
n≤N
∑
p≤x
p ’bad’ for Kn
ρn(p)
1
π(x)
∑
n≤N
n logn N
2 logN
π(x) = o(N). 
Distribution of factorials modulo p 175
Theorem 2.2 directly implies:
Corollary 2.3. Assume that GRH is true. There exists infinitely many
primes p such that
p− V (0, p− 1) p
1/4
log p ·
Remark 2.4. Working in Kn instead of the splitting field of fn allows us
to get the bound on the discriminant exponentially smaller than the one
used in [1]. The main improvement then comes from the fact that counting
prime ideals of degree 1 in Kn corresponds to counting primes with the
appropriate weight suitable for our problem.
3. Concluding remarks. Erdős conjecture on average
It might be possible to prove Erdős conjecture for almost all primes p.
Indeed, if a prime p satisfies Erdős conjecture, then at least two of the
fn(x) = x(x+ 1) · · · (x+n− 1)− 1, n = 1, . . . , p− 1 have a root modulo p.
Chebotarev’s theorem tells us that the density of primes p such that fn(x)
has no roots modulo p is equal to the proportion of elements inGal(Spl(fn))
without fixed points. The natural strategy would be to apply Chebotarev’s
theorem to the product f :=
∏
i fni (where ni is a suitable sequence of
integers) to control the density of primes failing Erdős conjecture. This
amounts to understanding the proportion of elements in the Galois group
without fixed points. The following lemma helps us to do that:
Lemma 3.1. Suppose that G is a subgroup of Sn acting on a set X of n
elements. Then the proportion σn of elements of G that do not have any
fixed point satisfies
(3.1) σn ≤ 1− 1/n.
Proof. We denote by Xσ the number of elements of X fixed by σ ∈ G and
X\G the number of orbits of the action of G on X. By Burnside’s lemma,
we have that
|X\G| = 1
|G|
∑
σ∈G
|Xσ|.
Hence
1 ≤ |{σ, Xσ 6= ∅}| n
|G|
and the result follows. 
Remark 3.2. Interesting lower bounds for σn can be found in [3].
If the splitting fields of fni(x) are disjoint we can apply Chebotarev’s
theorem to f and bound the number of permutations without fixed points
in
Gal(Spl(f)) ∼=
∏
i
Gal(Spl(fni)).
176 Oleksiy Klurman, Marc Munsch
Several computations provides support towards the following conjecture:
Conjecture 3.3. Let n1 6= n2 be positive integers. Then
Spl(fn1) ∩ Spl(fn2) = Q.
This conjecture together with Lemma 3.1 imply the Erdős conjecture
on average. Indeed, for each prime p failing to satisfy the aforementioned
conjecture, each fn has at most 1 root. Hence, the density of primes S
failing Erdős conjecture is
S ≤
N∑
n=2
(1− σn)
∏
j 6=n
σj  logN
N∏
n=2
(
1− 1
n
)
−−−−→
N→∞
0.
where we used Lemma 3.1. The last inequality follows by optimizing the
function f(σ1, · · · , σN ) =
N∑
n=2
(1− σn)
∏
j 6=n
σj over the domain defined by the
inequalities 0 ≤ σn ≤ 1− 1/n, n = 2, . . . , N.
We notice that proving Conjecture 3.3 for a good proportion of n would
suffice to obtain a zero density of primes failing Erdős conjecture.
Acknowledgements
The authors would like to thank Andrew Granville and Igor Shparlin-
ski for valuable comments. During the preparation of this manuscript, O.K.
was supported by the ISM doctoral grant and J. Armand Bombardier Foun-
dation excellence award. M.M. was supported by a postdoctoral grant in
CRM of Montreal under the supervision of Andrew Granville and Dimitris
Koukoulopoulos.
References
[1] W. D. Banks, F. Luca, I. E. Shparlinski & H. Stichtenoth, “On the value set of n!
modulo a prime”, Turkish J. Math. 29 (2005), no. 2, p. 169-174.
[2] K. A. Broughan & A. R. Barnett, “On the missing values of n! mod p”, J. Ramanujan
Math. Soc. 24 (2009), no. 3, p. 277-284.
[3] P. J. Cameron & A. M. Cohen, “On the number of fixed point free elements in a permu-
tation group”, Discrete Math. 106/107 (1992), p. 135-138, A collection of contributions in
honour of Jack van Lint.
[4] C. Cobeli, M. Vâjâitu & A. Zaharescu, “The sequence n! (mod p)”, J. Ramanujan Math.
Soc. 15 (2000), no. 2, p. 135-154.
[5] M. Z. Garaev & J. Hernández, “A note on n! modulo p”, To appear in Monatschefte für
Mathematic, http://arxiv.org/abs/1505.05912.
[6] M. Z. Garaev & F. Luca, “Character sums and products of factorials modulo p”, J. Théor.
Nombres Bordeaux 17 (2005), no. 1, p. 151-160.
[7] M. Z. Garaev, F. Luca & I. E. Shparlinski, “Character sums and congruences with n!”,
Trans. Amer. Math. Soc. 356 (2004), no. 12, p. 5089-5102 (electronic).
[8] ———, “Exponential sums and congruences with factorials”, J. Reine Angew. Math. 584
(2005), p. 29-44.
[9] R. K. Guy, Unsolved problems in number theory, Unsolved Problems in Intuitive Mathe-
matics, vol. 1, Springer-Verlag, New York-Berlin, 1981, xviii+161 pages.
Distribution of factorials modulo p 177
[10] H. Iwaniec & E. Kowalski, Analytic number theory, American Mathematical Society Col-
loquium Publications, vol. 53, American Mathematical Society, 2004, xi+615 pages.
[11] O. Klurman & M. Munsch, “Distribution of factorials modulo p”, Preprint, http://arxiv.
org/abs/1505.01198.
[12] J. C. Lagarias, H. L. Montgomery & A. M. Odlyzko, “A bound for the least prime ideal
in the Chebotarev density theorem”, Invent. Math. 54 (1979), no. 3, p. 271-296.
[13] J. C. Lagarias & A. M. Odlyzko, “Effective versions of the Chebotarev density theo-
rem”, in Algebraic number fields: L-functions and Galois properties (Proc. Sympos., Univ.
Durham, Durham, 1975), Academic Press, London, 1977, p. 409-464.
[14] V. F. Lev, “Permutations in abelian groups and the sequence n! (mod p)”, European J.
Combin. 27 (2006), no. 5, p. 635-643.
[15] G. Pólya & G. Szegő, Problems and theorems in analysis. Vol. II: Theory of functions,
zeros, polynomials, determinants, number theory, geometry, Die Grundlehren der mathe-
matischen Wissenschaften, vol. 216, Springer-Verlag, 1976, xi+391 pages.
[16] B. Rokowska & A. Schinzel, “Sur un problème de M. Erdős”, Elem. Math. 15 (1960),
p. 84-85.
[17] H. M. Stark, “Some effective cases of the Brauer-Siegel theorem”, Invent. Math. 23 (1974),
p. 135-152.
[18] T. Trudgian, “There are no socialist primes less than 109”, Integers 14 (2014), p. Paper
No. A63, 4.
Oleksiy Klurman
Départment de Mathématiques et de Statistique
Université de Montréal, CP 6128 succ. Centre-Ville
Montréal QC H3C 3J7, Canada
E-mail: lklurman@gmail.com
Marc Munsch
CRM, Université de Montréal
5357 Montréal, Québec, Canada
E-mail: munsch@dms.umontreal.ca


Distribution of factorials modulo $p$

Niels Lindner

Density of quasismooth hypersurfaces in simplicial toric varieties

Chris Jennings-Shaffer

Ranks For Two Partition Quadruple Functions

Xavier Caruso

Numerical stability of Euclidean algorithm  over ultrametric fields

Josep González

Constraints on the automorphism group of a curve

Federico Pellarin

A sum-shuffle formula for zeta values in Tate algebras

Yoshiyasu Ozeki

Lattices in potentially semi-stable representations and weak $(\varphi ,\hat{G})$-modules

Ernst-Ulrich Gekeler

On Drinfeld modular forms of higher rank

Hui June Zhu

On a theorem of Ax and Katz

Not a member yet

A Gap in the Spectrum of the Faltings Height

Distribution of factorials modulo $p$

Density of quasismooth hypersurfaces in simplicial toric varieties

Ranks For Two Partition Quadruple Functions

Numerical stability of Euclidean algorithm over ultrametric fields

Constraints on the automorphism group of a curve

A sum-shuffle formula for zeta values in Tate algebras

Lattices in potentially semi-stable representations and weak $(\varphi ,\hat{G})$ -modules

On Drinfeld modular forms of higher rank

On a theorem of Ax and Katz

1,235

1,351