Products of consecutive integers with unusual anatomy

I’ve just uploaded to the arXiv my paper “Products of consecutive integers with unusual anatomy“. This paper answers some questions of Erdős and Graham which were initially motivated by the study of the Diophantine factorial equation

$\displaystyle a_1! a_2! a_3! = m^2$

where ${a_1 < a_2 < a_3}$ and ${m}$ are positive integers. Writing ${(a,N,N+H) = (a_1,a_2,a_3)}$ , one can rewrite this equation as

$\displaystyle s( (N+1) \dots (N+H) ) = s(a!) \ \ \ \ \ (1)$

where ${s(n)}$ denotes the squarefree part of ${n}$ (the smallest factor of ${n}$ formed by dividing out a perfect square). For instance, we have

$\displaystyle s(8 \times 9 \times 10) = 5 = s(6!)$

which corresponds to the solution ${6! 7! 10! = (6!\times 7!)^2}$ to the original equation.

The equation (1) ties into the general question of what the anatomy (prime factorization) of the product ${(N+1) \dots (N+H)}$ looks like. This is a venerable topic, with the first major result being the Sylvester-Schur theorem from 1892 that the largest prime factor of ${(N+1) \dots (N+H)}$ is greater than ${H}$ . Another notable result is the Erdős-Selfridge theorem that the product ${(N+1) \dots (N+H)}$ is never a perfect power for ${H > 1}$ .

Erdős and Graham were able to show that solutions to (1) were somewhat rare, in that the set of possible values of ${N+H}$ had density zero. For them, the hardest case to treat was when the interval ${\{N+1,\dots,N+H\}}$ was what they called bad, in the sense that ${(N+1) \dots (N+H)}$ was divisible by the square of its largest prime factor. They were able, with some effort, to show that the union of all bad intervals also had density zero, which was a key ingredient in to prove the previous result about solutions to (1). They isolated a subcase of the bad intervals, which they called the very bad intervals, in which the product ${(N+1) \dots (N+H)}$ was a powerful number (divisible by the square of every prime factor).

A later paper of Luca, Saradha, and Shorey made the bounds more quantitative, showing that both the set of values of ${N+H}$ , as well as the union of bad intervals, had density ${O( \exp(-c \log^{1/4} x (\log\log x)^{3/4})}$ for some absolute constant ${c>0}$ . In the other direction, just by considering the case ${H=1}$ , one can show that the number of possible values of ${N+H}$ up to ${x}$ is ${\gtrsim c_3^1 \sqrt{x}}$ , where ${c_3^1}$ is the constant

$\displaystyle c_3^1 = 1 + \sum_{a \geq 2: a \neq n^2 \forall n} \frac{1}{s(a!)^{1/2}} = 3.70951\dots.$

As for the bad intervals, by again considering the case ${H=1}$ , it is possible to show that the number of bad points up to ${x}$ is

$\displaystyle x / \exp((\sqrt{2}+o(1)) \sqrt{\log x \log\log x});$

see for instance this paper of Ivic. Similarly, the union of the very bad intervals contains as the set of powerful numbers; Golomb worked out that the number of powerful numbers up to ${x}$ is ${\sim \frac{\zeta(3/2)}{\zeta(3)} \sqrt{x}}$ .

It was conjectured by Erdős and Graham that all of these lower bounds are in fact sharp (up to ${1+o(1)}$ multiplicative factors); this is Erdos Problem 380 (and a portion of Erdos Problem 374). The main result of this paper is to confirm this conjecture in two cases and come close in the third:

Theorem 1

Not surprisingly, the methods of proof involve many standard tools in analytic number theory, such as the prime number theorem (and its variants in short intervals), zero density estimates, Vinogradov’s bounds on exponential sums, asymptotics for smooth numbers, the large sieve, the fundamental lemma of sieve theory, and the Burgess bound for character sums. There was one point where I needed a small amount of algebraic number theory (the classification of solutions to a generalized Pell equation), which was the one place where I turned to AI for assistance (though I ended up rewriting the AI argument myself). One amusing point is that I specifically needed the recent zero density theorem of Guth and Maynard (as converted to a bound on exceptions to the prime number theorem in short intervals by Gafni and myself); previous zero density theorems were barely not strong enough to close the arguments.

A few more details on the methods of proof. It turns out that very bad intervals, or intervals solving (1), are both rather short, in that the bound ${H \leq \exp(\log^{2/3+o(1)} N)}$ holds. The reason for this is that the primes ${p}$ that are larger than ${H}$ (in the very bad case) or ${C H \log N}$ for a large constant ${C}$ (in the (1) case) cannot actually divide any of the ${N+1,\dots,N+H}$ unless they divide it at least twice. This creates a constraint on the fractional parts of ${N/p}$ and ${N/p^2}$ that turns out to be inconsistent with the equidistribution results on those fractional parts coming from Vinogradov’s bounds on exponential sums unless ${H}$ is small. In the very bad case, this forces a linear relation between two powerful numbers; expressing powerful numbers as the product of a square and a cube, matters then boil down to counting solutions to an equation such as

$\displaystyle n_1^2 n_2^3 + 1 = m_1^2 m_2^3$

with say ${n_1,n_2,m_1,m_2 \leq x^{1/5}}$ . The number of solutions here turns out to be ${O(x^{2/5})}$ by work of Aktas-Murty and of Chan; we generalize the arguments in the former to handle a slightly more general equation. A similar argument handles solutions to (1), except in one regime where the parameter ${a}$ is somewhat large (comparable to ${H \log N}$ ), in which case one instead collects some congruence conditions on ${N}$ and applies the large sieve.

The situation with bad intervals is more delicate, because there is no obvious way to make ${H}$ small in all cases. However, by the large sieve (as well as the Guth–Maynard theorem), one can show that the contribution of large ${H}$ is negligible, and from bounds on smooth numbers one can show that the interval ${\{N+1,\dots,N+H\}}$ contains a number with a particularly specific anatomy, of the form ${p_0^2 p_1 \dots p_{1000} m'}$ where ${p_0, \dots, p_{1000}}$ are all primes of roughly the same size, and ${m'}$ is a smoother factor involving smaller primes. The rest of the bad interval creates some congruence conditions on the product ${p_1 \dots p_{1000}}$ . Using some character sum estimates coming from the Burgess bounds, we find that the residue of ${p_1\dots p_{1000}}$ becomes fairly equidistributed amongst the primitive congruence classes to a given modulus when one perturbs the primes ${p_1,\dots,p_{1000}}$ randomly (there are some complications from exceptional characters of Siegel zero type, but we can use a large values estimate to keep their total contribution under control). This allows us to show that the congruence conditions coming from the bad interval are restrictive enough to make non-trivial bad intervals quite rare compared to bad points. One innovation in this regard is to set up an “anti-sieve”: the elements of a bad interval tend to have an elevated chance of being divisible by small primes, and one can use moment methods to show that an excessive number of small prime divisors is somewhat rare. This can be compared to standard sieve arguments, which often seek to limit the event that a number has an unexpectedly deficient number of small prime divisors.