A result of Bui–Pratt–Zaharescu, and Erdös problem #437

What's new 2024-08-09

The following problem was posed by Erdös and Graham (and is listed as problem #437 on the Erdös problems website):

Problem 1 Let ${1 \leq a_1 < \dots < a_k \leq x}$ be integers. How many of the partial products ${a_1}$ , ${a_1 a_2}$ , ${\dots}$ , ${a_1 \dots a_k}$ can be squares? Is it true that, for any ${\varepsilon>0}$ , there can be more than ${x^{1-\varepsilon}}$ squares?

If one lets ${L(x)}$ denote the maximal number of squares amongst such partial products, it was observed in the paper of Erdös and Graham that the bound ${L(x) = o(x)}$ is “trivial” (no proof was provided, but one can for instance argue using the fact that the number of integer solutions to hyperelliptic equations of the form ${(n+h_1) \dots (n+h_d) = m^2}$ for fixed ${h_1 < \dots < h_d}$ is quite sparse, and in fact finite for ${d>2}$ thanks to Siegel’s theorem), and the problem then asks if ${L(x) = x^{1-o(1)}}$ .

It turns out that this problem was essentially solved (though not explicitly) by a recently published paper of Bui, Pratt, and Zaharescu, who studied a closely related quantity ${t_n}$ introduced by Erdös, Graham, and Selfridge (see also Problem B30 of Guy’s book), defined for any natural number ${n}$ as the least natural number ${t_n}$ such that some subset of ${n+1,\dots,n+t_{n}}$ , when multiplied together with ${n}$ , produced a square. Among the several results proven about ${t_n}$ in that paper was the following:

Theorem 2 (Bui–Pratt–Zaharescu, Theorem 1.2) For ${x}$ sufficiently large, there exist ${\gg x \exp(-(3\sqrt{2}/2+o(1)) \sqrt{\log x} \sqrt{\log\log x})}$ integers ${1 \leq n \leq x}$ such that ${t_n \leq \exp((\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})}$ .

The arguments were in fact quite elementary, with the main tool being the theory of smooth numbers (the theory of hyperelliptic equations is used elsewhere in the paper, but not for this particular result).

If one uses this result as a “black box”, then an easy greedy algorithm argument gives the lower bound

$\displaystyle L(x) \geq x\exp(-(5\sqrt{2}/2+o(1)) \sqrt{\log x} \sqrt{\log\log x}),$

but with a small amount of additional work, one can modify the proof of the theorem to give a slightly better bound:

Theorem 3 (Bounds for ${L}$ ) As ${x \rightarrow \infty}$ , we have the lower bound
$\displaystyle L(x) \geq x\exp(-(\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})$
and the upper bound
$\displaystyle L(x) \leq x\exp(-(1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x}).$
In particular, for any ${\varepsilon>0}$ , one has ${L(x) \geq x^{1-\varepsilon}}$ for sufficiently large ${x}$ .

The purpose of this blog post is to record this modification of the argument, which is short enough to present immediately. For a large ${x}$ , let ${u}$ denote the quantity

$\displaystyle u := \sqrt{2} \sqrt{\log x} / \sqrt{\log\log x}.$

We call a natural number ${x^{1/u}}$ -smooth if all of its prime factors are at most ${x^{1/u}}$ . From a result of Hildebrand (or the older results of de Bruijn), we know that the number ${\pi(x, x^{1/u})}$ of ${x^{1/u}}$ -smooth numbers less than or equal to ${x}$ is

$\displaystyle \pi(x, x^{1/u}) = x \exp( - (1+o(1)) u \log u ) \ \ \ \ \ (1)$

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

Let ${\pi(x^{1/u})}$ be the number of primes up to ${x^{1/u}}$ . From the prime number theorem we have

$\displaystyle \pi(x^{1/u}) = (1+o(1)) x^{1/u} / \log x^{1/u} \ \ \ \ \ (2)$

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

To prove the lower bound on ${L(x)}$ , which is a variant of Theorem 2. The key observation is that given any ${\pi(x^{1/u})+1}$ ${x^{1/u}}$ -smooth numbers ${b_1,\dots,b_{\pi(x^{1/u})+1}}$ , some non-trivial subcollection of them will multiply to a square. This is essentially Lemma 4.2 of Bui–Pratt–Zaharescu, but for the convenience of the reader we give a full proof here. Consider the multiplicative homomorphism ${f: {\bf N} \rightarrow ({\bf Z}/2{\bf Z})^{\pi(x^{1/u})}}$ defined by

$\displaystyle f(n) := (\nu_{p_i}(n) \mod 2)_{i=1}^{\pi(x^{1/u})},$

where ${p_i}$ is the ${i^{\mathrm{th}}}$ prime and ${\nu_{p_i}(n)}$ is the number of times ${p_i}$ divides ${n}$ . The vectors ${f(b_1),\dots,f(b_{\pi(x^{1/u})+1})}$ lie in a ${\pi(x^{1/u})}$ -dimensional vector space over ${{\bf Z}/2{\bf Z}}$ , and thus are linearly dependent. Thus there exists a non-trivial collection of these vectors that sums to zero, which implies that the corresponding elements of the sequence ${b_1,\dots,b_{\pi(x^{1/u})+1}}$ multiply to a square.

From (1), (2) we can find ${x \exp( - (\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x} )}$ sequences of ${x^{1/u}}$ -smooth numbers ${b_1 < \dots < b_{\pi(x^{1/u})+1}}$ in ${\{1,\dots,x\}}$ , with each sequence being to the right of the previous sequence. By the above observation, each sequence contains some non-trivial subcollection that multiplies to a square. Concatenating all these subsequences together, we obtain a single sequence ${1 \leq a_1 < \dots < a_k \leq x}$ with at least ${x \exp( - (\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x} )}$ partial products multiplying to a square, giving the desired lower bound on ${L(x)}$ .

Next, we prove the upper bound on ${L(x)}$ . Suppose that a sequence ${1 \leq a_1 < \dots < a_k \leq x}$ has ${L(x)}$ partial products ${a_1 \dots a_{i_l}}$ that are squares for some ${1 \leq i_1 < \dots < i_{L(x)} \leq k}$ . Then we have ${a_{i_l+1} \dots a_{i_{l+1}}}$ a square for all ${0 \leq l < L(x)}$ (with the convention ${i_0=0}$ ). The key observation (essentially Lemma 3.4 of Bui–Pratt–Zaharescu) is that, for each ${0 \leq l < L(x)}$ , one of the following must hold:

(i) At least one of the ${a_{i_l+1},\dots,a_{i_{l+1}}}$ is ${x^{1/u}}$ -smooth.
(ii) At least one of the ${a_{i_l+1},\dots,a_{i_{l+1}}}$ is divisible by ${p^2}$ for some prime ${p>x^{1/u}}$ .
(iii) ${a_{i_{l+1}} - a_{i_l+1} > x^{1/u}}$ .

Indeed, suppose that (i) and (ii) are not true, then one of the terms in the sequence ${a_{i_l+1},\dots,a_{i_{l+1}}}$ is divisible by exactly one copy of ${p}$ for some prime ${p > x^{1/u}}$ . In order for the product ${a_{i_l+1} \dots a_{i_{l+1}}}$ to be a square, another element of the sequence must also be divisible by the same prime; but this implies (iii).

From (1) we see that the number of ${l}$ for which (i) occurs is at most ${x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})}$ . From the union bound we see that the number of ${l}$ for which (ii) occurs is at most

$\displaystyle \ll \sum_{p > x^{1/u}} x/p^2 \ll x^{1-1/u} = x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x}).$

Finally, from the pigeonhole principle we see that the number of ${l}$ for which (iii) occurs is also at most

$\displaystyle x^{1-1/u} = x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x}).$

Thus one has ${L(x) \ll x \exp( - (1/\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})}$ , as desired. This completes the proof.

The upper bound arguments seem more crude to the author than the lower bound arguments, so I conjecture that the lower bound is in fact the truth: ${L(x) = x\exp(-(\sqrt{2}+o(1)) \sqrt{\log x} \sqrt{\log\log x})}$ .