Journal de Théorie des Nombres de Bordeaux

Razvan Barbulescu

Jishnu Ray

Numerical verification of the Cohen–Lenstra–Martinet heuristics and of Greenberg’s $p$-rationality conjecture

Brandon Alberts

Cohen–Lenstra Moments for Some Nonabelian Groups

Stephan Baier

Marc Technau

On the distribution of $\alpha p$ modulo one in imaginary quadratic number fields with class number one

Ashwin Sah

Ashwin SAH
An improved bound on the least common multiple of polynomial sequences
Tome 32, no 3 (2020), p. 891-899.
<http://jtnb.centre-mersenne.org/item?id=JTNB_2020__32_3_891_0>
© Société Arithmétique de Bordeaux, 2020, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.centre-mersenne.org/), implique
l’accord avec les conditions générales d’utilisation (http://jtnb.
centre-mersenne.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 con-
stitutive d’une infraction 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.centre-mersenne.org/
Journal de Théorie des Nombres
de Bordeaux 32 (2020), 891–899
An improved bound on the least common
multiple of polynomial sequences
par Ashwin SAH
Résumé. Cilleruelo a conjecturé que si f ∈ Z[x] de degré d ≥ 2 est irréductible
sur les rationnels, alors log lcm(f(1), . . . , f(N)) ∼ (d−1)N logN quand N →
∞. Il l’a prouvé dans le cas d = 2. Très récemment, Maynard et Rudnick ont
prouvé qu’il existe cd > 0 tel que log lcm(f(1), . . . , f(N)) & cdN logN , et ont
montré qu’on peut prendre cd = d−1d2 . Nous donnons une preuve alternative de
ce résultat avec la constante améliorée cd = 1. De plus, nous prouvons la mi-
noration log rad lcm(f(1), . . . , f(N)) & 2dN logN et proposons une conjecture
plus forte affirmant que log rad lcm(f(1), . . . , f(N)) ∼ (d − 1)N logN quand
N →∞.
Abstract. Cilleruelo conjectured that if f ∈ Z[x] of degree d ≥ 2 is irre-
ducible over the rationals, then log lcm(f(1), . . . , f(N)) ∼ (d − 1)N logN as
N → ∞. He proved it for the case d = 2. Very recently, Maynard and Rud-
nick proved there exists cd > 0 with log lcm(f(1), . . . , f(N)) & cdN logN ,
and showed one can take cd = d−1d2 . We give an alternative proof of this re-
sult with the improved constant cd = 1. We additionally prove the bound
log rad lcm(f(1), . . . , f(N)) & 2dN logN and make the stronger conjecture
that log rad lcm(f(1), . . . , f(N)) ∼ (d− 1)N logN as N →∞.
1. Introduction
If f ∈ Z[x], let Lf (N) = lcm{f(n) : 1 ≤ n ≤ N}, where say we ignore
values of 0 in the LCM and set the LCM of an empty set to be 1. It is a
well-known consequence of the Prime Number Theorem that
log lcm(1, . . . , N) ∼ N
as N → ∞. Therefore, a similar linear behavior should occur if f is a
product of linear polynomials. See the work of Hong, Qian, and Tan [4] for
a more precise analysis of this case. On the other hand, if f is irreducible
over Q and has degree d ≥ 2, logLf (N) ought to grow as N logN rather
than linearly. In particular, Cilleruelo [2] conjectured the following growth
rate.
Manuscrit reçu le 22 février 2020, révisé le 8 septembre 2020, accepté le 18 septembre 2020.
2010 Mathematics Subject Classification. 11N32.
Mots-clefs. Least common multiple, polynomial sequence.
892 Ashwin Sah
Conjecture 1.1 ([2]). If f ∈ Z[x] is irreducible over Q and has degree
d ≥ 2, then
logLf (N) ∼ (d− 1)N logN
as N →∞.
He proved this for d = 2. As noted in [7], his argument demonstrates
(1.1) logLf (N) . (d− 1)N logN.
Hong, Luo, Qian, and Wang [3] showed that logLf (N)  N , which was
for some time the best known lower bound. Then, very recently, Maynard
and Rudnick [5] provided a lower bound of the correct magnitude.
Theorem 1.2 ([5, Theorem 1.2]). Let f ∈ Z[x] be irreducible over Q with
degree d ≥ 2. Then there is c = cf > 0 such that
logLf (N) & cN logN.
The proof given produces cf = d−1d2 , although a minor modification pro-
duces cf = 1d . We prove the following improved bound, which in particular
recovers Conjecture 1.1 when d = 2. It also does not decrease with d, unlike
the previous bound.
Theorem 1.3. Let f ∈ Z[x] be irreducible over Q with degree d ≥ 2. Then
logLf (N) & N logN.
It is also interesting to consider the problem of estimating the quantity
`f (N) = rad lcm(f(1), . . . , f(n)). (Recall that rad(n) is the product of the
distinct primes dividing n.) It is easy to see that the proof of Theorem 1.2
that was given in [5] implies
log `f (N) & cfN logN
for the same constant cf = d−1d2 (or cf =
1
d after slight modifications). We
demonstrate an improved bound.
Theorem 1.4. Let f ∈ Z[x] be irreducible over Q with degree d ≥ 2. Then
log `f (N) &
2
d
N logN.
We conjecture that the radical of the LCM should be the same order of
magnitude as the LCM.
Conjecture 1.5. If f ∈ Z[x] is irreducible over Q with degree d ≥ 2, then
log `f (N) ∼ (d− 1)N logN
as N →∞.
LCM of polynomial sequences 893
Finally, we note that Theorem 1.4 proves Conjecture 1.5 for d = 2.
In a couple of different directions, Rudnick and Zehavi [7] have studied
the growth of Lf along a shifted family of polynomials fa(x) = f0(x) − a,
and Cilleruelo has asked for similar bounds in cases when f is not irreducible
as detailed by Candela, Rué, and Serra [1, Problem 4], which may also be
tractable directions to pursue.
1.1. Commentary and setup. Interestingly, we avoid analysis of what
is known as “Chebyshev’s problem” regarding the greatest prime factor
P+(f(n)) of f(n), which is an essential element of the argument in [5]. Our
approach is to study the product
Q(N) =
N∏
n=1
|f(n)|.
We first analyze the contribution of small primes and linear-sized primes,
which we show we can remove and retain a large product. Then we show
that each large prime appears in the product a fixed number of times,
hence providing a lower bound for the LCM and radical of the LCM. For
convenience of our later analysis we write
Q(N) =
∏
p
pαp(N).
Note that logQ(N) = dN logN + O(N) by Stirling’s approximation, if
d is the degree of f . Finally, let ρf (m) denote the number of roots of f
modulo m.
Remark on notation. Throughout, we use g(n) h(n) to mean |g(n)| ≤
ch(n) for some constant c, g(n) . h(n) to mean for every ε > 0 we have
|g(n)| ≤ (1 + ε)h(n) for sufficiently large n, and g(n) ∼ h(n) to mean
limn→∞ g(n)h(n) = 1. Additionally, throughout, we will fix a single f ∈ Z[x]
that is irreducible over Q and has degree d ≥ 2. We will often suppress the
dependence of constants on f . We will also write
f(x) =
d∑
i=0
fix
i.
Acknowledgements. I thank Ze’ev Rudnick, Juanjo Rué, and Mark Shus-
terman for helpful comments, suggestions, and references.
2. Bounding small primes
The analysis in this section is very similar to that of [5, Section 3], except
that we do not use the resulting bounds to study the Chebyshev problem.
894 Ashwin Sah
We define
QS(N) =
∏
p≤N
pαp(N),
the part of Q(N) =
∏N
n=1 |f(n)| containing small prime factors. The main
result of this section is the following asymptotic.
Proposition 2.1. We have logQS(N) ∼ N logN .
Remark 2.2. This asymptotic directly implies the earlier stated Equa-
tion (1.1).
The argument is a simple analysis involving Hensel’s Lemma and the
Chebotarev density theorem. The Hensel-related work has already been
done in [5].
Lemma 2.3 ([5, Lemma 3.1]). Fix f ∈ Z[x] and assume that it has no
rational zeros. Let ρf (m) denote the number of roots of f modulo m. Then
if p - disc(f) we have
αp(N) = N
ρf (p)
p− 1 +O
( logN
log p
)
and if p | disc(f) we have
αp(N)
N
p
,
where the implicit constant depends only on f .
Proof of Proposition 2.1. We use Lemma 2.3. Noting that the deviation of
the finitely many ramified primes from the typical formula is linear-sized,
we will be able to ignore them with an error of O(N). We thus have
logQS(N) =
∑
p≤N
αp(N) log p =
∑
p≤N
N
log p
p− 1ρf (p) +O
(
N +
∑
p≤N
logN
)
= N
∑
p≤N
log p
p− 1ρf (p) +O(N) = N logN +O(N),
using the Chebotarev density theorem alongside the fact that f is irre-
ducible over Q in the last equation (see e.g. [6, Equation (4)]). 
3. Removing linear-sized primes
We define
QLI(N) =
∏
N<p≤DN
pαp(N),
for appropriately chosen constant D = Df . We will end up choosing D =
1 + d|fd| or so, although any greater constant will also work for the final
argument. The result main result of this section is the following.
LCM of polynomial sequences 895
Proposition 3.1. We have logQLI(N) = O(N).
In order to prove this, we show that all large primes appear in the product
Q(N) a limited number of times.
Lemma 3.2. Let N be sufficiently large depending on f , and let p > N be
prime. Then
αp(N) ≤ d2.
Proof. Note that f ≡ 0 (mod p) has at most d solutions, hence at most d
values of n ∈ [1, N ] satisfy p|f(n) since p > N . For those values, we see
pd+1 > Nd+1 ≥ |f(n)| for all n ∈ [1, N ] if N is sufficiently large, and f is
irreducible hence has no roots. Thus pd+1 does not divide any f(n) when
n ∈ [1, N ].
Therefore αp(N) is the sum of at most d terms coming from the val-
ues f(n) that are divisible by p. Each term, by the above analysis, has
multiplicity at most d. This immediately gives the desired bound. 
Proof of Proposition 3.1. Using Lemma 3.2 we find
logQLI(N) ≤ d2
∑
N<p≤DN
log p = O(N)
by the Prime Number Theorem. 
4. Multiplicity of large primes
Note that Lemma 3.2 is already enough to recreate Theorem 1.2. Indeed,
we see that
log Q(N)
QS(N)
= (d− 1)N logN +O(N)
from Q(N) = dN logN +O(N) and Proposition 2.1. Furthermore, by def-
inition and by Lemma 3.2,
Q(N)
QS(N)
=
∏
p>N
pαp(N) ≤
∏
p>N,p|Q(N)
pd
2 ≤ `f (N)d
2 ≤ Lf (N)d
2
.
This immediately gives the desired result (and recreates the constant d−1
d2
appearing in the proof given in [5]).
In order to improve this bound, we will provide a more refined analysis of
the multiplicity of large primes. More specifically, we will show that we have
a multiplicity of d(d−1)2 for primes p > DN , with D chosen as in Section 3.
Lemma 4.1. Let N be sufficiently large depending on f , and let p > DN
be prime, where D = 1 + d|fd|. Then
αp(N) ≤
d(d− 1)
2 .
896 Ashwin Sah
Proof. Fix prime p > DN . As in the proof of Lemma 3.2, when N is
large enough in terms of f , we have that pd+1 never divides any f(n) for
n ∈ [1, N ]. Thus for 1 ≤ i ≤ d + 1 let bi = #{n ∈ [1, N ] : pi|f(n)}, where
we see bd+1 = 0. Note that
αp(N) =
d∑
i=1
i(bi − bi+1) =
d∑
i=1
bi.
We claim that bi ≤ d − i for all 1 ≤ i ≤ d, which immediately implies the
desired result.
Suppose for the sake of contradiction that bi ≥ d−i+1 for some 1 ≤ i ≤ d.
Then let m1, . . . ,md−i+1 be distinct values of m ∈ [1, N ] such that pi|f(m).
Consider the value
A = Ai =
d−i+1∑
j=1
f(mj)∏
k 6=j(mj −mk)
.
We have from the standard theory of polynomial identities that
A =
d∑
`=0
f`
d−i+1∑
j=1
m`j∏
k 6=j(mj −mk)
=
d∑
`=d−i
f`
∑
a1+···+ad−i+1=`−(d−i)
d−i+1∏
j=1
m
aj
j ,
where the inner sum is over all tuples (a1, . . . , ad−i+1) of nonnegative inte-
gers that sum to `− (d− i). Therefore A ∈ Z. Furthermore, since pi|f(mj)
for all 1 ≤ j ≤ d− i+ 1, we have from the definition of A that
pi|A
∏
1≤j<k≤d−i+1
(mj −mk).
Note that each mj −mk is nonzero and bounded in magnitude by N < p,
hence we deduce pi|A.
But from the above formula and the triangle inequality we have
|A| =
∣∣∣∣∣
d∑
`=d−i
f`
∑
a1+···+ad−i+1=`−(d−i)
d−i+1∏
j=1
m
aj
j
∣∣∣∣∣
≤
d∑
`=d−i
|f`|
(
`
d− i
)
N `−(d−i)
≤ (1 + |fd|di)N i
for sufficiently large N in terms of f , using the fact that there are
( `
d−i
)
tuples of nonnegative integers (a1, . . . , ad−i+1) with sum `−(d− i) and that
|mj | ≤ N for all 1 ≤ j ≤ d− i+ 1.
LCM of polynomial sequences 897
Thus, as p > DN ≥ (1 + |fd|d)N , we have
|A| ≤ (1 + |fd|di)N i ≤ (1 + |fd|d)iN i < pi.
Combining this with pi|A, we deduce A = 0.
However, we will see that this leads to a contradiction as the “top-degree”
term of A is too large in magnitude for this to occur. First, we claim that
if 1 ≤ i ≤ d and d− i ≤ ` ≤ d, then
(4.1)
∑
a1+···+ad−i+1=`−(d−i)
∏d−i+1
j=1 m
aj
j∑d−i+1
j=1 m
`−(d−i)
j
∈ [1, 2d].
Indeed, note that each mj > 0 and the denominator occurs as a subset of
the terms in the numerator, hence the desired fraction is always at least 1.
For an upper bound, simply use the well-known AM-GM inequality. As it
turns out, a sharp upper bound for the above is 1d−i+1
( `
d−i
)
, which does not
exceed 2d for the given range of i and `.
Next, we see that, using Equation (4.1) and the triangle inequality,
|A| =
∣∣∣∣∣
d∑
`=d−i
f`
∑
a1+···+ad−i+1=`−(d−i)
d−i+1∏
j=1
m
aj
j
∣∣∣∣∣
≥ |fd|
∑
a1+···+ad−i+1=i
d−i+1∏
j=1
m
aj
j −
d−1∑
`=d−i
|f`|
∑
a1+···+ad−i+1=`−(d−i)
d−i+1∏
j=1
m
aj
j
≥ |fd|
d−i+1∑
j=1
mij − 2d
d−1∑
`=d−i
|f`|
d−i+1∑
j=1
m
`−(d−i)
j
=
d−i+1∑
j=1
f∗(mj),
where we define f∗(x) = |fd|xi−2d
∑d−1
`=d−i |f`|x`−(d−i). But since A = 0 and
f∗ clearly has a global minimum over the positive integers, we immediately
deduce that |mj | for all 1 ≤ j ≤ d − i + 1 is bounded in terms of some
constant depending only on f and d = deg f .
But then, in particular, we also have |f(m1)| < Cf for some constant Cf
depending only on f , yet it is divisible by p > DN . For N sufficiently large
in terms of f , this can only happen if f(m1) = 0, but since f is irreducible
over Q and deg f = d ≥ 2 this is a contradiction! Therefore we conclude
that in fact bi ≤ d − i for all 1 ≤ i ≤ d, which as remarked above finishes
the proof. 
We have actually proven something stronger, namely that for this range
of p we have at most d− i values n ∈ [1, N ] with pi|f(n). In particular, this
898 Ashwin Sah
implies that for p > DN we have
(4.2) #{n ∈ [1, N ] : p|f(n)} ≤ d− 1.
5. Finishing the argument
Proof of Theorem 1.3. The argument is similar to the one at the beginning
of Section 4, but refined. We have
log Q(N)
QS(N)QLI(N)
= (d− 1)N logN +O(N)
by Q(N) = dN logN + O(N) and Propositions 2.1 and 3.1. Furthermore,
by definition and by Equation (4.2),
Q(N)
QS(N)QLI(N)
=
∏
p>DN
pαp(N) ≤ Lf (N)d−1.
The inequality comes from the fact that for p > DN > N , there are at
most d − 1 values of n ∈ [1, N ] with p|f(n) from Equation (4.2), and the
LCM takes the largest power of p from those involved hence has a power
of at least αp(N)d−1 on p. Taking logarithms, we deduce
(d− 1) logLf (N) ≥ (d− 1)N logN +O(N),
which immediately implies the result since d ≥ 2. 
Proof of Theorem 1.4. The argument is essentially identical to the one at
the beginning of Section 4, but with a better multiplicity bound from
Lemma 4.1. We have
log Q(N)
QS(N)QLI(N)
= (d− 1)N logN +O(N)
by Q(N) = dN logN + O(N) and Propositions 2.1 and 3.1. Furthermore,
by definition and by Lemma 4.1,
Q(N)
QS(N)QLI(N)
=
∏
p>DN
pαp(N) ≤
∏
p>DN,p|Q(N)
p
d(d−1)
2 ≤ `f (N)
d(d−1)
2 .
Taking logarithms, we deduce
d(d− 1)
2 log `f (N) ≥ (d− 1)N logN +O(N),
which immediately implies the result since d ≥ 2. 
LCM of polynomial sequences 899
6. Discussion
We see from our approach that the major obstruction to proving Conjec-
ture 1.1 is the potential for large prime factors p > N to appear multiple
times in the product Q(N). In particular, it is possible to show that Con-
jecture 1.5 is equivalent to the assertion that
lim
N→∞
#{p prime : p2|Q(N)}
#{p prime : p|Q(N)} = 0.
Indeed, the bounds we have given are sufficient to show that there are
Θ(N) prime factors of Q(N), of which only O
(
N
logN
)
are less than DN .
Therefore the asymptotic size of the LCM is purely controlled by whether
multiplicities for large primes in
[
2, d(d−1)2
]
appear a constant fraction of
the time or not (noting that log p = Θ(logN) for these large primes, so
that the sizes of their contributions are the same up to constant factors).
Similarly, Conjecture 1.1 is equivalent to the assertion that
lim
N→∞
#{p prime : ∃ 1 ≤ m < n ≤ N : p|f(m), p|f(n)}
#{p prime : p|Q(N)} = 0.
Our bound for Conjecture 1.5 corresponds to using the fact that we can
upper bound the multiplicities for all primes p > DN by d(d−1)2 . In general,
smaller multiplicities other than 1 could be possible but infrequent, which
may be a direction to further approach Conjecture 1.1 and Conjecture 1.5.
References
[1] P. Candela, J. Rué & O. Serra, “Memorial to Javier Cilleruelo: a problem list”, Integers
18 (2018), article no. A28 (9 pages).
[2] J. Cilleruelo, “The least common multiple of a quadratic sequence”, Compos. Math. 147
(2011), no. 4, p. 1129-1150.
[3] S. Hong, Y. Luo, G. Qian & C. Wang, “Uniform lower bound for the least common multiple
of a polynomial sequence”, C. R. Math. Acad. Sci. Paris 351 (2013), no. 21-22, p. 781-785.
[4] S. Hong, G. Qian & Q. Tan, “The least common multiple of a sequence of products of linear
polynomials”, Acta Math. Hung. 135 (2012), no. 1-2, p. 160-167.
[5] J. Maynard & Z. Rudnick, “A lower bound on the least common multiple of polynomial
sequences”, to appear in Riv. Mat. Univ. Parma.
[6] T. Nagel, “Généralisation d’un théorème de Tchebycheff”, Journ. de Math. 8 (1921), no. 4,
p. 343-356.
[7] Z. Rudnick & S. Zehavi, “On Cilleruelo’s conjecture for the least common multiple of poly-
nomial sequences”, https://arxiv.org/abs/1902.01102, 2019.
Ashwin Sah
Department of Mathematics
Massachusetts Institute of Technology
Cambridge, MA 02139, USA
E-mail: asah@mit.edu
URL: www.mit.edu/~asah


An improved bound on the least common multiple of polynomial sequences

Shalini Bhattacharya

Reduction of certain crystalline representations and local constancy in the weight space

Laurent Moret-Bailly

Points rationnels dans leur fibre :  compléments à un théorème de Poonen

Jianing Li

Chia-Fu Yu

The Chevalley–Gras formula over global fields

Po-Han Hsu

Peng-Jie Wong

On Selberg’s Central Limit Theorem for Dirichlet $L$-functions

Greg Martin

Lee Troupe

The distribution of sums and products of  additive functions

Rémi Lodh

On Tate’s conjecture for the elliptic modular surface of level $N$ over a prime field of characteristic $1\ \protect \mathrm{mod}\ N$

Not a member yet

Numerical verification of the Cohen–Lenstra–Martinet heuristics and of Greenberg’s $p$ -rationality conjecture

Cohen–Lenstra Moments for Some Nonabelian Groups

On the distribution of $\alpha p$ modulo one in imaginary quadratic number fields with class number one

An improved bound on the least common multiple of polynomial sequences

Reduction of certain crystalline representations and local constancy in the weight space

Points rationnels dans leur fibre : compléments à un théorème de Poonen

The Chevalley–Gras formula over global fields

On Selberg’s Central Limit Theorem for Dirichlet $L$ -functions

The distribution of sums and products of additive functions

On Tate’s conjecture for the elliptic modular surface of level $N$ over a prime field of characteristic 1\ \protect \mathrm{mod}\ N

1,235

1,351