Tag Archive

You are currently browsing the tag archive for the ‘Paul Erdos’ tag.

Local Bernstein theory, and lower bounds for Lebesgue constants

23 March, 2026 in math.CA, math.CV, paper | Tags: exponential type, Lagrange interpolation, Paul Erdos, trigonometric polynomials | by Terence Tao | 10 comments

I’ve just uploaded to the arXiv my paper “Local Bernstein theory, and lower bounds for Lebesgue constants“. This paper was initially motivated by a problem of Erdős} on Lagrange interpolation, but in the course of solving that problem, I ended up modifying some very classical arguments of Bernstein and his contemporaries (Boas, Duffin, Schaeffer, Riesz, etc.) to obtain “local” versions of these classical “Bernstein-type inequalities” that may be of independent interest.

Bernstein proved many estimates concerning the derivatives of polynomials, trigonometric polynomials, and entire functions of exponential type, but perhaps his most famous inequality in this direction is:

Lemma 1 (Bernstein’s inequality for trigonometric polynomials) Let ${P: {\bf R} \rightarrow {\bf C}}$ be a trigonometric polynomial of degree at most ${n}$ , with ${|P(x)| \leq A}$ for all ${x}$ . Then ${|P'(x)| \leq n A}$ for all ${x}$ .

Similar inequalities concerning ${L^p}$ norms of derivatives of Littlewood-Paley components of functions are now ubiquitious in the modern theory of nonlinear dispersive PDE (where they are also called Bernstein estimates), but this will not be the focus of this current post.

A trigonometric polynomial ${P}$ of degree ${n}$ is of exponential type ${n}$ in the sense that ${P(z) = O(\exp(n|z|))}$ for complex ${z}$ . Bernstein in fact proved a more general result:

Lemma 2 (Bernstein’s inequality for functions of exponential type) Let ${f: {\bf C} \rightarrow {\bf C}}$ be an entire function of exponential type at most ${\lambda}$ , with ${|f(x)| \leq A}$ for all ${x \in {\bf R}}$ . Then ${|f'(x)| \leq \lambda A}$ for all ${x \in {\bf R}}$ .

There are several proofs of this lemma – see for instance this survey of Queffélec and Zarouf. In the case that ${f}$ is real-valued on ${{\bf R}}$ , there is a nice proof by Duffin and Schaeffer, which we sketch as follows. Suppose we normalize ${A=\lambda=1}$ , and adjust ${f}$ by a suitable damping factor so that ${f(z)}$ actually decays slower than ${\exp(|z|)}$ as ${z \rightarrow \infty}$ . Then, for any ${0 < \alpha < 1}$ and ${x_0 \in {\bf R}}$ , one can use Rouche’s theorem to show that the function ${\cos(x-x_0) - \alpha f(x)}$ has the same number of zeroes as ${\cos(x-x_0)}$ in a suitable large rectangle; but on the other hand one can use the intermediate value theorem to show that ${\cos(x-x_0) - \alpha f(x)}$ has at least as many zeroes than ${\cos(x-x_0)}$ in the same rectangle. Among other things, this prevents double zeroes from occuring, which turns out to give the desired claim ${|f'(x)| \leq 1}$ after some routine calculations (in fact one obtains the stronger bound ${|f(x)|^2 + |f'(x)|^2 \leq 1}$ for all real ${x}$ ).

The first main result of the paper is to obtain localized versions of Lemma 2 (as well as some related estimates). Roughly speaking, these estimates assert that if ${f}$ is holomorphic on a wide thin rectangle passing through the real axis, is bounded by ${A}$ on the intersection of the real axis with this rectangle, and is “locally of exponential type” in the sense that it is bounded by ${O(\exp( \lambda |\mathrm{Im} z|))}$ on the upper and lower edges of this rectangle (and obeys some very mild growth conditions on the remaining sides of this rectangle), then ${|f'(x)|}$ can be bounded by ${\lambda A}$ plus small errors on the real line, with some additional estimates away from the real line also available. The proof proceeds by a modification of the Duffin–Schaeffer argument, together with the two-constant theorem of Nevanlinna (and some standard estimates of harmonic measures on rectangles) to deal with the effect of the localization. (As a side note, this latter argument was provided to me by ChatGPT, as I was not previously aware of the Nevanlinna two-constant theorem.)

Once one localizes this “Bernstein theory”, it becomes suitable for the analysis of (real-rooted, monic) polynomials ${P}$ of a high degree ${n}$ , which are not bounded globally on ${{\bf R}}$ (and grow polynomially rather than exponentially at infinity), but which can exhibit “local exponential type” behavior on various intervals, particularly in regions where the logarithmic potential

$\displaystyle U_\mu(z) := \frac{1}{n} \log \frac{1}{|P(z)|} = \int \log \frac{1}{|z-x|}\ d\mu(x)$

behaves like a smooth function (here ${\mu = \frac{1}{n} \sum_{j=1}^k \delta_{x_j}}$ is the empirical measure of the roots ${x_1,\dots,x_n}$ of ${P}$ ). A key example is the (monic) Chebyshev polynomials ${2^{1-n} T_n(x)}$ , which locally behave like sinusoids on the interval ${[-1,1]}$ (and are locally of exponential type above and below this interval):

BERJAYA

This becomes relevant in the theory of Lagrange interpolation. Recall that if ${x_1 < \dots < x_n}$ are real numbers and ${Q}$ is a polynomial of degree less than ${n}$ then one has the interpolation formula

$\displaystyle Q(z) = \sum_{j=1}^k Q(x_k) \ell_j(z)$

where the Lagrange basis functions ${\ell_j(z)}$ are defined by the formula

$\displaystyle \ell_k(z) := \prod_{i \neq k} \frac{z - x_i}{x_k - x_i}.$

In terms of the monic polynomial ${P(z) := \prod_{j=1}^n (z-x_j)}$ , we can write

$\displaystyle \ell_k(z) = \frac{P(z)}{(z-x_k) P'(x_k)}.$

The stability and convergence properties of Lagrange interpolation are closely related to the Lebesgue function

$\displaystyle \Lambda(z) := \sum_{k=1}^n |\ell_k(z)|,$

and for a given interval ${I}$ , the quantity ${\sup_{x \in I} \Lambda(x)}$ is known as the Lebesgue constant for that interval.

If one chooses the interpolation points ${x_1,\dots,x_n}$ poorly, then the Lebesgue constant can be extremely large. However, if one selects these points to be the roots of the aforementioned monic Chebyshev polynomials, then it is known that ${\sup_{x \in I} \Lambda(x) = \frac{2}{\pi} \log n - O(1)}$ for all fixed intervals ${I}$ in ${[-1,1]}$ . In the case ${I = [-1,1]}$ , it was shown by Erdős} that this is the best possible value of the Lebesgue constant up to ${O(1)}$ errors for interpolation on ${[-1,1]}$ , thus

$\displaystyle \sup_{x \in [-1,1]} \Lambda(x) \geq \frac{2}{\pi} \log n - O(1)$

whenever ${-1 \leq x_1 < \dots < x_n \leq 1}$ (a more precise bound was later shown by Vertesi). Erdős and Turán then asked if the same lower bound

$\displaystyle \sup_{x \in I} \Lambda(x) \geq \frac{2}{\pi} \log n - O(1) \ \ \ \ \ (1)$

held for more general intervals ${I}$ . This is shown in our paper; a variant integral bound

$\displaystyle \int_I \Lambda(x)\ dx \geq \frac{4}{\pi^2} |I| \log n - o(\log n) \ \ \ \ \ (2)$

is also established, answering a separate question of Erdős. These lower bounds had previously obtained up to constants by Erdős and Szabados}; the main issue was to obtain the sharp constant in the main term.

In terms of the monic polynomial ${P}$ , these two estimates can be written as

$\displaystyle \sup_{x \in I} \sum_{k=1}^n \frac{|P(x)|}{|x-x_k||P'(x_k)|} \geq \frac{2}{\pi} \log n - O(1)$

and

$\displaystyle \int_I \sum_{k=1}^n \frac{|P(x)|}{|x-x_k||P'(x_k)|}\ dx \geq \frac{4}{\pi^2} |I| \log n - o(\log n).$

Using the intuition that ${P}$ should behave locally like a trigonometric polynomial, and performing some renormalizations, one can extract the following toy problem to work with first:

Problem 3 Let ${P: {\bf R} \rightarrow {\bf R}}$ be a trigonometric polynomial of degree ${n}$ with ${2n}$ roots ${x_1 < \dots < x_{2n}}$ in ${[0, 2\pi)}$ .

(i) Show that
$\displaystyle \sup_{x \in [0,2\pi)} \sum_{k=1}^{2n} \frac{|P(x)|}{|P'(x_k)|} \geq 2. \ \ \ \ \ (3)$

(ii) Show that
$\displaystyle \int_0^{2\pi} \sum_{k=1}^{2n} \frac{|P(x)|}{|P'(x_k)|}\ dx \geq 8. \ \ \ \ \ (4)$

It is easy to check that the lower bounds of ${2}$ and ${8}$ are sharp by considering the case when ${P}$ is a sinusoid ${P(x) = A \sin(n(x-x_0))}$ .

The bound (3) is immediate from Bernstein’s inequality (Lemma 1). By applying a local version of this inequality, I was able to get a weak version of the claim (1) in which ${O(1)}$ was replaced with ${o(\log n)}$ ; see this early version of the paper, which was developed through conversations with Nat Sothanaphan and Aron Bhalla. By combining this argument with ideas from the older work of Erdős}, I was able to establish (1).

The bound (2) took me longer to establish, and involved a non-trivial amount of playing around with AI tools, the story of which I would like to share here. I had discovered the toy problem (4), but initially was not able to establish this inequality; AlphaEvolve seemed to confirm it numerically (with sinusoids appearing to be the extremizer), but did not offer direct clues on how to prove this rigorously. At some point I realized that the left-hand side factorized into the expressions ${\int_0^{2\pi} |P(x)|\ dx}$ and ${\sum_{k=1}^{2n} \frac{1}{|P'(x_k)|}}$ , and tried to bound these expressions separately. Perturbing around a sinusoid ${A \sin(n(x-x_0))}$ , I was able to show that the ${L^1}$ norm ${\int_0^{2\pi} |P(x)|\ dx}$ was a local minimum as long as one only perturbed by lower order Fourier modes, keeping the frequency ${n}$ coefficients unchanged. Guessing that this local minimum was actually a global minimum, this led me to conjecture the general lower bound

$\displaystyle \int_0^{2\pi} |P(x)|\ dx \geq 4 |a_n+ib_n|$

whenever ${P}$ was a degree ${n}$ trigonometric polynomial with highest frequency components ${a_n \cos(nx) + b_n \sin(nx)}$ . AlphaEvolve numerically confirmed this inequality to be likely to be true also. I still did not see how to prove this inequality, but I decided to try my luck giving it to ChatGPT Pro, which recognized it as an ${L^1}$ approximation problem and gave me a duality-based proof (based ultimately on the Fourier expansion of the square wave). With some further discussion, I was able to adapt this proof to functions of global exponential type (replacing the Fourier manipulations with contour shifting arguments, in the spirit of the Paley-Wiener theorem), which roughly speaking gave me half of what I needed to establish (2). However, I still needed the matching lower bound

$\displaystyle \sum_{k=1}^{2n} \frac{1}{|P'(x_k)|} \geq \frac{2}{|a_n+ib_n|}$

on the other factor in the toy problem. Again, AlphaEvolve could numerically confirm that this inequality was likely to be true, but now the quantity I was trying to control did not look convex or linear in ${P}$ , and so the previous duality method did not seem to apply. At this point I switched to pen and paper; eventually I realized that the expression almost looked like a sum of residues, and eventually after playing around with contour integrals of ${\frac{e^{inz}}{P(z)}}$ using the residue theorem I was able to establish (4), and then with a bit more (human) effort I could move from the toy problem back to the original problem to obtain (2). Quite possibly AI tools would also have been able to assist with these steps, but they were not necessary here; their main value for me was in quickly confirming that the approach I had in mind was numerically plausible, and in recognizing the right technique to solve one part of the toy problem I had isolated. (I also used AI tools for several other secondary tasks, such as literature review, proofreading, and generating pictures, but these applications of AI have matured to the point where using them for this purpose is almost mundane.)

Rogers’ theorem on sieving

19 January, 2026 in expository, math.CO, math.NT | Tags: Paul Erdos, Rogers' theorem, sieving | by Terence Tao | 16 comments

A basic problem in sieve theory is to understand what happens when we start with the integers ${{\bf Z}}$ (or some subinterval of the integers) and remove some congruence classes ${a_i \pmod{q_i}}$ for various moduli ${q_i}$ . Here we shall concern ourselves with the simple setting where we are sieving the entire integers rather than an interval, and are only removing a finite number of congruence classes ${a_1 \pmod{q_1}, \ldots, a_k \pmod{q_k}}$ . In this case, the set of integers that remain after the sieving is periodic with period ${Q = \mathrm{lcm}(q_1,\dots,q_k)}$ , so one work without loss of generality in the cyclic group ${{\bf Z}/Q{\bf Z}}$ . One can then ask: what is the density of the sieved set

$\displaystyle \{ n \in {\bf Z}/Q{\bf Z}: n \neq a_i \hbox{ mod } q_i \hbox{ for all } i=1,\ldots,k \}? \ \ \ \ \ (1)$

If the ${q_i}$ were all coprime, then it is easy to see from the Chinese remainder theorem that the density is given by the product

$\displaystyle \prod_{i=1}^k \left(1 - \frac{1}{q_i}\right).$

However, when the ${q_i}$ are not coprime, the situation is more complicated. One can use the inclusion-exclusion formula to get a complicated expression for the density, but it is not easy to work with. Sieve theory also supplies one with various useful upper and lower bounds (starting with the classical Bonferroni inequalities), but do not give exact formulae.

In this blog post I would like to note one simple fact, due to Rogers, that one can say about this problem:

Theorem 1 (Rogers’ theorem) For fixed ${q_1,\dots,q_k}$ , the density of the sieved set is maximized when all the ${a_i}$ vanish. Thus,
$\displaystyle |\{ n \in {\bf Z}/Q{\bf Z}: n \neq a_i \hbox{ mod } q_i \hbox{ for all } i=1,\ldots,k \}|$

$\displaystyle \leq |\{ n \in {\bf Z}/Q{\bf Z}: n \neq 0 \hbox{ mod } q_i \hbox{ for all } i=1,\ldots,k \}|.$

Example 2 If one sieves out ${1 \pmod{2}}$ , ${1 \pmod{3}}$ , and ${2 \pmod{6}}$ , then only ${0 \pmod{6}}$ remains, giving a density of ${1/6}$ . On the other hand, if one sieves out ${0 \pmod{2}}$ , ${0 \pmod{3}}$ , and ${0 \pmod{6}}$ , then the remaining elements are ${1}$ and ${5 \pmod{6}}$ , giving the larger density of ${2/6}$ .

This theorem is somewhat obscure: its only appearance in print is in pages 242-244 of this 1966 text of Halberstam and Roth, where the authors write in a footnote that the result is “unpublished; communicated to the authors by Professor Rogers”. I have only been able to find it cited in three places in the literature: in this 1996 paper of Lewis, in this 2007 paper of Filaseta, Ford, Konyagin, Pomerance, and Yu (where they credit Tenenbaum for bringing the reference to their attention), and is also briefly mentioned in this 2008 paper of Ford. As far as I can tell, the result is not available online, which could explain why it is rarely cited (and also not known to AI tools). This became relevant recently with regards to Erdös problem 281, posed by Erdös and Graham in 1980, which was solved recently by Neel Somani through an AI query by an elegant ergodic theory argument. However, shortly after this solution was located, it was discovered by KoishiChan that Rogers’ theorem reduced this problem immediately to a very old result of Davenport and Erdös from 1936. Apparently, Rogers’ theorem was so obscure that even Erdös was unaware of it when posing the problem!

Modern readers may see some similarities between Rogers’ theorem and various rearrangement or monotonicity inequalites, suggesting that the result may be proven by some sort of “symmetrization” or “compression” method. This is indeed the case, and is basically Rogers’ original proof. We can modernize a bit as follows. Firstly, we can abstract ${{\bf Z}/Q{\bf Z}}$ into a finite cyclic abelian group ${G}$ , with residue classes now becoming cosets of various subgroups of ${G}$ . We can take complements and restate Rogers’ theorem as follows:

Theorem 3 (Rogers’ theorem, again) Let ${a_1+H_1, \dots, a_k+H_k}$ be cosets of a finite cyclic abelian group ${G}$ . Then
$\displaystyle |\bigcup_{j=1}^k a_j + H_j| \geq |\bigcup_{j=1}^k H_j|.$

Example 4 Take ${G = {\bf Z}/6{\bf Z}}$ , ${H_1 = 2{\bf Z}/6{\bf Z}}$ , ${H_2 = 3{\bf Z}/6{\bf Z}}$ , and ${H_3 = 6{\bf Z}/6{\bf Z}}$ . Then the cosets ${1 + H_1}$ , ${1 + H_2}$ , and ${2 + H_3}$ cover the residues ${\{1,2,3,4,5\}}$ , with a cardinality of ${5}$ ; but the subgroups ${H_1,H_2,H_3}$ cover the residues ${\{0,2,3,4\}}$ , having the smaller cardinality of ${4}$ .

Intuitively: “sliding” the cosets ${a_i+H_i}$ together reduces the total amount of space that these cosets occupy. As pointed out in comments, the requirement of cyclicity is crucial; four lines in a finite affine plane already suffice to be a counterexample otherwise.

By factoring the cyclic group into $p$ -groups, Rogers’ theorem is an immediate consequence of two observations:

Theorem 5 (Rogers’ theorem for cyclic groups of prime order) Rogers’ theorem holds when ${G = {\bf Z}/p^n {\bf Z}}$ for some prime power ${p^n}$ .

Theorem 6 (Rogers’ theorem preserved under products) If Rogers’ theorem holds for two finite abelian groups ${G_1, G_2}$ of coprime orders, then it also holds for the product ${G_1 \times G_2}$ .

The case of cyclic groups of prime order is trivial, because the subgroups of ${G}$ are totally ordered. In this case ${\bigcup_{j=1}^k H_j}$ is simply the largest of the ${H_j}$ , which has the same size as ${a_j + H_j}$ and thus has lesser or equal cardinality to ${\bigcup_{j=1}^k a_j + H_j}$ .

The preservation of Rogers’ theorem under products is also routine to verify. By the coprime orders of ${G_1,G_2}$ and standard group theoretic arguments (e.g., Goursat’s lemma, the Schur–Zassenhaus theorem, or the classification of finite abelian groups), one can see that any subgroup ${H_j}$ of ${G_1 \times G_2}$ splits as a direct product ${H_j = H_{j,1} \times H_{j,2}}$ of subgroups of ${G_1,G_2}$ respectively, so the cosets ${a_j + H_j}$ also split as

$\displaystyle a_j + H_j = (a_{j,1} + H_{j,1}) \times (a_{j,2} + H_{j,2}).$

Applying Rogers’ theorem for ${G_2}$ to each “vertical slice” of ${G_1 \times G_2}$ and summing, we see that

$\displaystyle |\bigcup_{j=1}^k (a_{j,1} + H_{j,1}) \times (a_{j,2} + H_{j,2})| \geq |\bigcup_{j=1}^k (a_{j,1} + H_{j,1}) \times H_{j,2}|$

and then applying Rogers’ theorem for ${G_1}$ to each “horizontal slice” of ${G_1 \times G_2}$ and summing, we obtain

$\displaystyle |\bigcup_{j=1}^k (a_{j,1} + H_{j,1}) \times H_{j,2}| \geq |\bigcup_{j=1}^k H_{j,1} \times H_{j,2}|.$

Combining the two inequalities, we obtain the claim.

A crowdsourced project to link up erdosproblems.com to the OEIS

31 August, 2025 in admin, advertising, Mathematics, polymath, question | Tags: Paul Erdos, Thomas Bloom | by Terence Tao | 19 comments

Thomas Bloom’s erdosproblems.com site hosts nearly a thousand questions that originated, or were communicated by, Paul Erdős, as well as the current status of these questions (about a third of which are currently solved). The site is now a couple years old, and has been steadily adding features, the most recent of which has been a discussion forum for each individual question. For instance, a discussion I had with Stijn Cambie and Vjeko Kovac on one of these problems recently led to it being solved (and even formalized in Lean!).

A significantly older site is the On-line Encyclopedia of Integer Sequences (OEIS), which records hundreds of thousands of integer sequences that have some mathematician has encountered at some point. It is a highly useful resource, enabling researchers to discover relevant literature for a given problem so long as they can calculate enough of some integer sequence that is “canonically” attached to that problem that they can search for it in the OEIS.

A large fraction of problems in the Erdos problem webpage involve (either explicitly or implicitly) some sort of integer sequence – typically the largest or smallest size ${f(n)}$ of some ${n}$ -dependent structure (such as a graph of ${n}$ vertices, or a subset of ${\{1,\dots,n\}}$ ) that obeys a certain property. In some cases, the sequence is already in the OEIS, and is noted in the Erdos problem web page. But in a large number of cases, the sequence either has not yet been entered into the OEIS, or it does appear but has not yet been noted on the Erdos web page.

Thomas Bloom and I are therefore proposing a crowdsourced project to systematically compute the hundreds of sequences associated to the Erdos problems and cross-check them against the OEIS. We have created a github repository to coordinate this process; as a by-product, this repository will also be tracking other relevant statistics about the Erdos problem website, such as the current status of formalizing the statements of these problems in the Formal Conjectures Repository.

The main feature of our repository is a large table recording the current status of each Erdos problem. For instance, Erdos problem #3 is currently listed as open, and additionally has the status of linkage with the OEIS listed as “possible”. This means that there are one or more sequences attached to this problem which *might* already be in the OEIS, or would be suitable for submission to the OEIS. Specifically, if one reads the commentary for that problem, one finds mention of the functions ${r_k(N)}$ for ${k=3,4,\dots}$ , defined as the size of the largest subset of ${\{1,\dots,N\}}$ without a ${k}$ -term progression. It is likely that several of the sequences ${r_3(N)}$ , ${r_4(N)}$ , etc. are in the OEIS, but it is a matter of locating them, either by searching for key words, or by calculating the first few values of these sequences and then looking for a match. (EDIT: a contributor has noted that the first foursequences appear as A003002, A003003, A003004, and A003005 in the OEIS, and the table has been updated accordingly.)

We have set things up so that new contributions (such as the addition of an OEIS number to the table) can be made by a Github pull request, specifically to modify this YAML file. Alternatively, one can create a Github issue for such changes, or simply leave a comment either on the appropriate Erdos problem forum page, or here on this blog.

Many of the sequences do not require advanced mathematical training to compute, and so we hope that this will be a good “citizen mathematics” project that can bring in the broader math-adjacent community to contribute to research-level mathematics problems, by providing experimental data, and potentially locating relevant references or connections that would otherwise be overlooked. This may also be a use case for AI assistance in mathematics through generating code to calculate the sequences in question, although of course one should always stay mindful of potential bugs or hallucinations in any AI-generated code, and find ways to independently verify the output. (But if the AI-generated sequence leads to a match with an existing sequence in the OEIS that is clearly relevant to the problem, then the task has been successfully accomplished, and no AI output needs to be directly incorporated into the database in such cases.)

This is an experimental project, and we may need to adjust the workflow as the project progresses, but we hope that it will be successful and lead to further progress on some fraction of these problems. The comment section of this blog can be used as a general discussion forum for the project, while the github issue page and the erdosproblems.com forum pages can be used for more specialized discussions of specific problems.

Rough numbers between consecutive primes

10 August, 2025 in math.NT, paper | Tags: Ayla Gafni, Paul Erdos, prime gaps, rough numbers | by Terence Tao | 25 comments

First things first: due to an abrupt suspension of NSF funding to my home university of UCLA, the Institute of Pure and Applied Mathematics (which had been preliminarily approved for a five-year NSF grant to run the institute) is currently fundraising to ensure continuity of operations during the suspension, with a goal of raising $500,000. Donations can be made at this page. As incoming Director of Special Projects at IPAM, I am grateful for the support (both moral and financial) that we have already received in the last few days, but we are still short of our fundraising goal.

Back to math. Ayla Gafni and I have just uploaded to the arXiv the paper “Rough numbers between consecutive primes“. In this paper we resolve a question of Erdös concerning rough numbers between consecutive gaps, and with the assistance of modern sieve theory calculations, we in fact obtain quite precise asymptotics for the problem. (As a side note, this research was supported by my personal NSF grant which is also currently suspended; I am grateful to recent donations to my own research fund which have helped me complete this research.)

Define a prime gap to be an interval ${(p_n, p_{n+1})}$ between consecutive primes. We say that a prime gap contains a rough number if there is an integer ${m \in (p_n,p_{n+1})}$ whose least prime factor is at least the length ${p_{n+1}-p_n}$ of the gap. For instance, the prime gap ${(3,5)}$ contains the rough number ${4}$ , but the prime gap ${(7,11)}$ does not (all integers between ${7}$ and ${11}$ have a prime factor less than ${4}$ ). The first few ${n}$ for which the ${n^\mathrm{th}}$ prime gap contains a rough number are

$\displaystyle 2, 3, 5, 7, 10, 13, 15, 17, 20, \dots.$

Numerically, the proportion of ${n}$ for which the ${n^\mathrm{th}}$ prime gap does not contain a rough number decays slowly as ${n}$ increases:

BERJAYA

Erdös initially thought that all but finitely many prime gaps should contain a rough number, but changed his mind, as per the following quote:

…I am now sure that this is not true and I “almost” have a counterexample. Pillai and Szekeres observed that for every ${t \leq 16}$ , a set of ${t}$ consecutive integers always contains one which is relatively prime to the others. This is false for ${t = 17}$ , the smallest counterexample being ${2184, 2185, \dots, 2200}$ . Consider now the two arithmetic progressions ${2183 + d \cdot 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13}$ and ${2201 + d \cdot 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13}$ . There certainly will be infinitely many values of ${d}$ for which the progressions simultaneously represent primes; this follows at once from hypothesis H of Schinzel, but cannot at present be proved. These primes are consecutive and give the required counterexample. I expect that this situation is rather exceptional and that the integers ${k}$ for which there is no ${m}$ satisfying ${p_k < m < p_{k+1}}$ and ${p(m) > p_{k+1} - p_k}$ have density ${0}$ .

In fact Erdös’s observation can be made simpler: any pair of cousin primes ${p_{n+1}=p_n+4}$ for ${p_n > 3}$ (of which ${(7,11)}$ is the first example) will produce a prime gap that does not contain any rough numbers.

The latter question of Erdös is listed as problem #682 on Thomas Bloom’s Erdös problems website. In this paper we answer Erdös’s question, and in fact give a rather precise bound for the number of counterexamples:

Theorem 1 (Erdos #682) For ${X>2}$ , let ${N(X)}$ be the number of prime gaps ${(p_n, p_{n+1})}$ with ${p_n \in [X,2X]}$ that do not contain a rough number. Then
$\displaystyle N(X) \ll \frac{X}{\log^2 X}. \ \ \ \ \ (1)$
Assuming the Dickson–Hardy–Littlewood prime tuples conjecture, we can improve this to
$\displaystyle N(X) \sim c \frac{X}{\log^2 X} \ \ \ \ \ (2)$
for some (explicitly describable) constant ${c>0}$ .

In fact we believe that ${c \approx 2.8}$ , although the formula we have to compute ${c}$ converges very slowly. This is (weakly) supported by numerical evidence:

BERJAYA

While many questions about prime gaps remain open, the theory of rough numbers is much better understood, thanks to modern sieve theoretic tools such as the fundamental lemma of sieve theory. The main idea is to frame the problem in terms of counting the number of rough numbers in short intervals ${[x,x+H]}$ , where ${x}$ ranges in some dyadic interval ${[X,2X]}$ and ${H}$ is a much smaller quantity, such as ${H = \log^\alpha X}$ for some ${0 < \alpha < 1}$ . Here, one has to tweak the definition of “rough” to mean “no prime factors less than ${z}$ ” for some intermediate ${z}$ (e.g., ${z = \exp(\log^\beta X)}$ for some ${0 < \beta < \alpha}$ turns out to be a reasonable choice). These problems are very analogous to the extremely well studied problem of counting primes in short intervals, but one can make more progress without needing powerful conjectures such as the Hardy–Littlewood prime tuples conjecture. In particular, because of the fundamental lemma of sieve theory, one can compute the mean and variance (i.e., the first two moments) of such counts to high accuracy, using in particular some calculations on the mean values of singular series that go back at least to the work of Montgomery from 1970. This second moment analysis turns out to be enough (after optimizing all the parameters) to answer Erdös’s problem with a weaker bound

$\displaystyle N(X) \ll \frac{X}{\log^{4/3-o(1)} X}.$

To do better, we need to work with higher moments. The fundamental lemma also works in this setting; one now needs precise asymptotics for the mean value of singular series of ${k}$ -tuples, but this was fortunately worked out (in more or less exactly the format we needed) by Montgomery and Soundararajan in 2004. Their focus was establishing a central limit theorem for the distribution of primes in short intervals (conditional on the prime tuples conjecture), but their analysis can be adapted to show (unconditionally) good concentration of measure results for rough numbers in short intervals. A direct application of their estimates improves the upper bound on ${N(X)}$ to

$\displaystyle N(X) \ll \frac{X}{\log^{2-o(1)} X}$

and some more careful tweaking of parameters allows one to remove the ${o(1)}$ error. This latter analysis reveals that in fact the dominant contribution to ${N(X)}$ will come with prime gaps of bounded length, of which our understanding is still relatively poor (it was only in 2014 that Yitang Zhang famously showed that infinitely many such gaps exist). At this point we finally have to resort to (a Dickson-type form of) the prime tuples conjecture to get the asymptotic (2).

On several irrationality problems for Ahmes series

27 November, 2024 in math.NT, paper | Tags: Ahmes series, irrationality, Paul Erdos, Vjekoslav Kovac | by Terence Tao | 6 comments

Vjeko Kovac and I have just uploaded to the arXiv our paper “On several irrationality problems for Ahmes series“. This paper resolves (or at least makes partial progress on) some open questions of Erdős and others on the irrationality of Ahmes series, which are infinite series of the form ${\sum_{k=1}^\infty \frac{1}{a_k}}$ for some increasing sequence ${a_k}$ of natural numbers. Of course, since most real numbers are irrational, one expects such series to “generically” be irrational, and we make this intuition precise (in both a probabilistic sense and a Baire category sense) in our paper. However, it is often difficult to establish the irrationality of any specific series. For example, it is already a non-trivial result of Erdős that the series ${\sum_{k=1}^\infty \frac{1}{2^k-1}}$ is irrational, while the irrationality of ${\sum_{p \hbox{ prime}} \frac{1}{2^p-1}}$ (equivalent to Erdős problem #69) remains open, although very recently Pratt established this conditionally on the Hardy–Littlewood prime tuples conjecture. Finally, the irrationality of ${\sum_n \frac{1}{n!-1}}$ (Erdős problem #68) is completely open.

On the other hand, it has long been known that if the sequence ${a_k}$ grows faster than ${C^{2^k}}$ for any ${C}$ , then the Ahmes series is necessarily irrational, basically because the fractional parts of ${a_1 \dots a_m \sum_{k=1}^\infty \frac{1}{a_k}}$ can be arbitrarily small positive quantities, which is inconsistent with ${\sum_{k=1}^\infty \frac{1}{a_k}}$ being rational. This growth rate is sharp, as can be seen by iterating the identity ${\frac{1}{n} = \frac{1}{n+1} + \frac{1}{n(n+1)}}$ to obtain a rational Ahmes series of growth rate ${(C+o(1))^{2^k}}$ for any fixed ${C>1}$ .

In our paper we show that if ${a_k}$ grows somewhat slower than the above sequences in the sense that ${a_{k+1} = o(a_k^2)}$ , for instance if ${a_k \asymp 2^{(2-\varepsilon)^k}}$ for a fixed ${0 < \varepsilon < 1}$ , then one can find a comparable sequence ${b_k \asymp a_k}$ for which ${\sum_{k=1}^\infty \frac{1}{b_k}}$ is rational. This partially addresses Erdős problem #263, which asked if the sequence ${a_k = 2^{2^k}}$ had this property, and whether any sequence of exponential or slower growth (but with ${\sum_{k=1}^\infty 1/a_k}$ convergent) had this property. Unfortunately we barely miss a full solution of both parts of the problem, since the condition ${a_{k+1} = o(a_k^2)}$ we need just fails to cover the case ${a_k = 2^{2^k}}$ , and also does not quite hold for all sequences going to infinity at an exponential or slower rate.

We also show the following variant; if ${a_k}$ has exponential growth in the sense that ${a_{k+1} = O(a_k)}$ with ${\sum_{k=1}^\infty \frac{1}{a_k}}$ convergent, then there exists nearby natural numbers ${b_k = a_k + O(1)}$ such that ${\sum_{k=1}^\infty \frac{1}{b_k}}$ is rational. This answers the first part of Erdős problem #264 which asked about the case ${a_k = 2^k}$ , although the second part (which asks about ${a_k = k!}$ ) is slightly out of reach of our methods. Indeed, we show that the exponential growth hypothesis is best possible in the sense a random sequence ${a_k}$ that grows faster than exponentially will not have this property, this result does not address any specific superexponential sequence such as ${a_k = k!}$ , although it does apply to some sequence ${a_k}$ of the shape ${a_k = k! + O(\log\log k)}$ .

Our methods can also handle higher dimensional variants in which multiple series are simultaneously set to be rational. Perhaps the most striking result is this: we can find an increasing sequence ${a_k}$ of natural numbers with the property that ${\sum_{k=1}^\infty \frac{1}{a_k + t}}$ is rational for every rational ${t}$ (excluding the cases ${t = - a_k}$ to avoid division by zero)! This answers (in the negative) a question of Stolarsky Erdős problem #266, and also reproves Erdős problem #265 (and in the latter case one can even make ${a_k}$ grow double exponentially fast).

Our methods are elementary and avoid any number-theoretic considerations, relying primarily on the countable dense nature of the rationals and an iterative approximation technique. The first observation is that the task of representing a given number ${q}$ as an Ahmes series ${\sum_{k=1}^\infty \frac{1}{a_k}}$ with each ${a_k}$ lying in some interval ${I_k}$ (with the ${I_k}$ disjoint, and going to infinity fast enough to ensure convergence of the series), is possible if and only if the infinite sumset

$\displaystyle \frac{1}{I_1} + \frac{1}{I_2} + \dots$

to contain ${q}$ , where ${\frac{1}{I_k} = \{ \frac{1}{a}: a \in I_k \}}$ . More generally, to represent a tuple of numbers ${(q_t)_{t \in T}}$ indexed by some set ${T}$ of numbers simultaneously as ${\sum_{k=1}^\infty \frac{1}{a_k+t}}$ with ${a_k \in I_k}$ , this is the same as asking for the infinite sumset

$\displaystyle E_1 + E_2 + \dots$

to contain ${(q_t)_{t \in T}}$ , where now

$\displaystyle E_k = \{ (\frac{1}{a+t})_{t \in T}: a \in I_k \}. \ \ \ \ \ (1)$

So the main problem is to get control on such infinite sumsets. Here we use a very simple observation:

Proposition 1 (Iterative approximation) Let ${V}$ be a Banach space, let ${E_1,E_2,\dots}$ be sets with each ${E_k}$ contained in the ball of radius ${\varepsilon_k>0}$ around the origin for some ${\varepsilon_k}$ with ${\sum_{k=1}^\infty \varepsilon_k}$ convergent, so that the infinite sumset ${E_1 + E_2 + \dots}$ is well-defined. Suppose that one has some convergent series ${\sum_{k=1}^\infty v_k}$ in ${V}$ , and sets ${B_1,B_2,\dots}$ converging in norm to zero, such that
$\displaystyle v_k + B_k \subset E_k + B_{k+1} \ \ \ \ \ (2)$
for all ${k \geq 1}$ . Then the infinite sumset ${E_1 + E_2 + \dots}$ contains ${\sum_{k=1}^\infty v_k + B_1}$ .

Informally, the condition (2) asserts that ${E_k}$ occupies all of ${v_k + B_k}$ “at the scale ${B_{k+1}}$ “.

Proof: Let ${w_1 \in B_1}$ . Our task is to express ${\sum_{k=1}^\infty v_k + w_1}$ as a series ${\sum_{k=1}^\infty e_k}$ with ${e_k \in E_k}$ . From (2) we may write

$\displaystyle \sum_{k=1}^\infty v_k + w_1 = \sum_{k=2}^\infty v_k + e_1 + w_2$

for some ${e_1 \in E_1}$ and ${w_2 \in B_2}$ . Iterating this, we may find ${e_k \in E_k}$ and ${w_k \in B_k}$ such that

$\displaystyle \sum_{k=1}^\infty v_k + w_1 = \sum_{k=m+1}^\infty v_k + e_1 + e_2 + \dots + e_m + w_{m+1}$

for all ${m}$ . Sending ${m \rightarrow \infty}$ , we obtain

$\displaystyle \sum_{k=1}^\infty v_k + w_1 = e_1 + e_2 + \dots$

as required. $\Box$

In one dimension, sets of the form ${\frac{1}{I_k}}$ are dense enough that the condition (2) can be satisfied in a large number of situations, leading to most of our one-dimensional results. In higher dimension, the sets ${E_k}$ lie on curves in a high-dimensional space, and so do not directly obey usable inclusions of the form (2); however, for suitable choices of intervals ${I_k}$ , one can take some finite sums ${E_{k+1} + \dots + E_{k+d}}$ which will become dense enough to obtain usable inclusions of the form (2) once ${d}$ reaches the dimension of the ambient space, basically thanks to the inverse function theorem (and the non-vanishing curvatures of the curve in question). For the Stolarsky problem, which is an infinite-dimensional problem, it turns out that one can modify this approach by letting ${d}$ grow slowly to infinity with ${k}$ .

Planar point sets with forbidden four-point patterns and few distinct distances

3 September, 2024 in math.CO, paper | Tags: Erdos distance problem, Paul Erdos | by Terence Tao | 18 comments

I’ve just uploaded to the arXiv my paper “Planar point sets with forbidden ${4}$ -point patterns and few distinct distance“. This (very) short paper was a byproduct of my recent explorations of the Erdös problem website in recent months, with a vague emerging plan to locate a suitable problem that might be suitable for some combination of a crowdsourced “Polymath” style project and/or a test case for emerging AI tools. The question below was one potential candidate; however, upon reviewing the literature on the problem, I noticed that the existing techniques only needed one additional tweak to fully resolve the problem. So I ended up writing this note instead to close off the problem.

I’ve arranged this post so that this additional trick is postponed to below the fold, so that the reader can, if desired, try to guess for themselves what the final missing ingredient needed to solve the problem was. Here is the problem (Erdös problem #135), which was asked multiple times by Erdös over more than two decades (and who even offered a small prize for the solution on one of these occasions):

Problem 1 (Erdös #135) Let ${A \subset {\bf R}^2}$ be a set of ${n}$ points such that any four points in the set determine at least five distinct distances. Must ${A}$ determine ${\gg n^2}$ many distances?

This is a cousin of the significantly more famous Erdös distinct distances problem (Erdös problem #89), which asks what is the minimum number of distances determined by a set ${A \subset {\bf R}^2}$ of ${n}$ points in the plane, without the restriction on four-point configurations. The example of a square grid ${\{0,\dots,\sqrt{n}-1\}^2}$ (assuming for sake of argument that ${n}$ is a perfect square), together with some standard analytic number theory calculations, shows that ${A}$ can determine ${\asymp n/\sqrt{\log n}}$ distances, and it is conjectured that this is best possible up to constants. A celebrated result of Guth and Katz, discussed in this previous blog post, shows that ${A}$ will determine at least ${\gg n/\log n}$ distances. Note that the lower bound ${\gg n^2}$ here is far larger, and in fact comparable to the total number ${\binom{n}{2}}$ of distances available, thus expressing the belief that the “local” condition that every four points determine at least five distances forces the global collection distances to be almost completely distinct. In fact, in one of the papers posing the problem, Erdös made the even stronger conjecture that the set ${A}$ must contain a subset ${A'}$ of cardinality ${\gg n}$ for which all the ${\binom{|A'|}{2}}$ distances generated by ${A}$ are distinct.

A paper of Dumitrescu came close to resolving this problem. Firstly, the number of ways in which four points could fail to determine five distinct distances was classified in that paper, with the four-point configurations necessarily being one of the following eight patterns:

${\pi_1}$ : An equilateral triangle plus an arbitrary vertex.
${\pi_2}$ : A parallelogram.
${\pi_3}$ : An isosceles trapezoid (four points on a line, ${P_1,P_2,P_3,P_4}$ , where ${\overleftrightarrow{P_1P_2} = \overleftrightarrow{P_3P_4}}$ , form a degenerate isosceles trapezoid).
${\pi_4}$ : A star with three edges of the same length.
${\pi_5}$ : A path with three edges of the same length.
${\pi_6}$ : A kite.
${\pi_7}$ : An isosceles triangle plus an edge incident to a base endpoint, and whose length equals the length of the base.
${\pi_8}$ : An isosceles triangle plus an edge incident to the apex, and whose length equals the length of the base.

(See Figure 1 and Lemma 1 of Dumitrescu’s paper.) So the question is asking whether if an ${n}$ point set ${A}$ avoids all of these patterns ${\pi_1,\dots,\pi_8}$ , then it must generate ${\gg n^2}$ distances.

Given that the grid ${\{0,\dots,n-1\}^2}$ determine only ${\asymp n^2 / \sqrt{\log n}}$ distances, one could seek a counterexample to this by finding a set of ${\asymp n}$ points in the grid ${\{0,\dots,n-1\}^2}$ that avoided all of the eight patterns ${\pi_1,\dots,\pi_8}$ .

Dumitrescu then counted how often each of the patterns ${\pi_1,\dots,\pi_8}$ occured inside the grid ${\{0,\dots,n-1\}^2}$ . The answer is:

${\pi_1}$ does not occur at all. (This is related to the irrationality of ${\sin \pi/3 = \sqrt{3}/2}$ .)
${\pi_2}$ occurs ${\asymp n^6}$ times.
${\pi_3}$ occurs ${\asymp n^5}$ times.
${\pi_4}$ occurs ${O(n^{14/3} \log n)}$ times.
${\pi_5}$ occurs ${O(n^{14/3} \log n)}$ times.
${\pi_6}$ occurs ${\asymp n^5}$ times.
${\pi_7}$ occurs ${O(n^{14/3} \log n)}$ times.
${\pi_8}$ occurs ${O(n^{14/3} \log n)}$ times.

(The bounds involving ${O(n^{14/3} \log n)}$ were obtained using the Szemerédi-Trotter theorem, and might not be optimal for this problem.) In particular, with the exception of the parallelogram pattern ${\pi_2}$ , the other seven forbidden ${4}$ -point patterns ${\pi_1,\pi_3,\dots,\pi_8}$ occur at most ${O(n^5)}$ times.

Using this and a standard probabilistic argument, Dumitrescu then established the following “near miss” to a negative answer to the above problem:

Theorem 2 (First near miss) If ${n}$ is sufficiently large, then there exists a subset of ${\{0,\dots,n-1\}^2}$ of cardinality ${\asymp n}$ which avoids all of the patterms ${\pi_1, \pi_3,\dots,\pi_8}$ .

In particular, this generates a set of ${\asymp n}$ points with ${O(n^2/\sqrt{\log n})}$ distances that avoids seven out of the eight required forbidden patterns; it is only the parallelograms ${\pi_2}$ that are not avoided, and are the only remaining obstacle to a negative answer to the problem.

Proof: Let ${\varepsilon>0}$ be a small constant, and let ${A}$ be a random subset of ${\{0,\dots,n-1\}^2}$ , formed by placing each element of ${\{0,\dots,n-1\}^2}$ with an independent probability of ${\varepsilon/n}$ . A standard application of Hoeffding’s inequality (or even the second moment method) shows that this set ${A}$ will have cardinality ${\asymp \varepsilon n}$ with high probability if ${n}$ is large enough. On the other hand, each of the ${O(n^5)}$ patterns ${\pi_1,\pi_3,\dots,\pi_8}$ has a probability ${\varepsilon^4/n^4}$ of lying inside ${A}$ , so by linearity of expectation, the total number of such patterns inside ${A}$ is ${O( n^5 \varepsilon^4 / n^4 ) = O(\varepsilon^4 n)}$ on the average. In particular, by Markov’s inequality, we can find a set ${A}$ of cardinality ${\asymp \varepsilon n}$ with only ${O(\varepsilon^4 n)}$ such patterns. Deleting all of these patterns from ${A}$ , we obtain a set ${A'}$ of cardinality ${\asymp \varepsilon n - O(\varepsilon^4 n)}$ , which is ${\asymp n}$ if ${\varepsilon}$ is a sufficiently small constant. This establishes the claim. $\Box$

Unfortunately, this random set contains far too many parallelograms ${\pi_2}$ ( ${\asymp n^2}$ such parallelograms, in fact) for this deletion argument to work. On the other hand, in earlier work of Thiele and of Dumitrescu, a separate construction of a set of ${\asymp n}$ points in ${\{0,\dots,n-1\}^2}$ that avoids all of the parallelograms ${\pi_2}$ was given:

Theorem 3 (Second near miss) For ${n}$ large, there exists a subset ${S}$ of ${\{0,\dots,n-1\}^2}$ of cardinality ${\asymp n}$ which contains no parallelograms ${\pi_2}$ . Furthermore, this set is in general position: no three points in ${S}$ are collinear, and no four are concyclic. As a consequence, this set ${S}$ in fact avoids the three patterns ${\pi_1, \pi_2, \pi_3}$ (the pattern in ${\pi_3}$ is concyclic, and the pattern ${\pi_1}$ does not occur at all in the grid).

Proof: One uses an explicit algebraic construction, going back to an old paper of Erdös and Turán involving constructions of Sidon sets. Namely, one considers the set

$\displaystyle S := \{ (x,y) \in \{0,\dots,n-1\}^2: y = x^2 \hbox{ mod } p \} \ \ \ \ \ (1)$

where ${p}$ is a prime between ${4n}$ and ${8n}$ (the existence of which is guaranteed by Bertrand’s postulate). Standard Gauss sum estimates can be used to show that ${S}$ has cardinality ${\asymp n}$ . If ${S}$ contained four points that were in a parallelogram or on a circle, or three points in a line, then one could lift up from ${\{0,\dots,n-1\}^2}$ to the finite field plane ${{\mathbf F}_p^2}$ and conclude that the finite field parabola ${\{ (x,x^2): x \in {\bf F}_p \}}$ also contained four points in a parallelogram or a circle, or three points on a line. But straightforward algebraic calculations can be performed to show that none of these scenarios can occur. For instance, if ${P, P+H, P+K, P+H+K}$ were four points on a parallelogram that were contained in a parabola, this would imply that an alternating sum of the form

$\displaystyle (x, x^2) - (x+h, (x+h)^2) - (x+k, (x+k)^2) + (x+h+k, (x+h+k)^2)$

would vanish for some non-zero ${h,k}$ ; but this expression simplifies to ${(0, 2hk)}$ , which cannot vanish for non-zero ${h,k}$ as ${p}$ is odd. (For the concylic claim, the parabola in ${{\mathbf F}_p^2}$ can in fact contain four points on a circle, but only if their ${x}$ coordinates sum to zero, and this cannot happen in ${S}$ )

Given that we have one “near-miss” in the literature that avoids ${\pi_1, \pi_3, \dots, \pi_8}$ , and another “near-miss” that avoids ${\pi_1, \pi_2, \pi_3}$ , it is natural to try to combine these two constructions to obtain a set that avoids all eight patterns ${\pi_1,\dots,\pi_8}$ . This inspired the following problem of Dumitrescu (see Problem 2 of this paper):

Problem 4 Does the set ${S}$ in (1) contain a subset of cardinality ${\gg n}$ that avoids all eight of the patterns ${\pi_1, \dots, \pi_8}$ ?

Unfortunately, this problem looked difficult, as the number-theoretic task of counting the patterns ${\pi_4,\dots,\pi_8}$ in ${S}$ looked quite daunting.

This ends the survey of the prior literature on this problem. Can you guess the missing ingredient needed to resolve the problem? I will place the answer below the fold.

Read the rest of this entry »

Erdos problem #385, the parity problem, and Siegel zeroes

19 August, 2024 in expository, math.NT | Tags: parity problem, Paul Erdos, Siegel zero | by Terence Tao | 24 comments

The Erdös problem site was created last year, and announced earlier this year on this blog. Every so often, I have taken a look at a random problem from the site for fun. A few times, I was able to make progress on one of the problems, leading to a couple papers; but the more common outcome is that I play around with the problem for a while, see why the problem is difficult, and then eventually give up and do something else. But, as is common in this field, I don’t make public the observations that I made, and the next person who looks at the same problem would likely have to go through the same process of trial and error to work out what the main obstructions that are present are.

So, as an experiment, I thought I would record here my preliminary observations on one such problem – Erdös problem #385 – to discuss why it looks difficult to solve with our current understanding of the primes. Here is the problem:

Problem 1 (Erdös Problem #385) Let
$\displaystyle F(n) =\max_{\stackrel{m<n}{m\hbox{\ composite}}} m+p(m),$
where ${p(m)}$ is the least prime divisor of ${m}$ . Is it true that ${F(n)>n}$ for all sufficiently large ${n}$ ? Does ${F(n)-n \rightarrow \infty}$ as ${n \rightarrow \infty}$ ?

This problem is mentioned on page 73 of this 1979 paper of Erdös (where he attributes the problem to an unpublished work of Eggelton, Erdös, and Selfridge that, to my knowledge, has never actually appeared), as well as briefly in page 92 of this 1980 paper of Erdös and Graham.

At first glance, this looks like a somewhat arbitrary problem (as many of Erdös’s problems initially do), as the function ${F}$ is not obviously related to any other well-known function or problem. However, it turns out that this problem is closely related to the parity barrier in sieve theory (as discussed in this previous post), with the possibility of Siegel zeroes presenting a particular obstruction. I suspect that Erdös was well aware of this connection; certainly he mentions the relation with questions on gaps between primes (or almost primes), which is in turn connected to the parity problem and Siegel zeroes (as is discussed recently in my paper with Banks and Ford, and in more depth in these papers of Ford and of Granville).

Let us now explore the problem further. Let us call a natural number ${n}$ bad if ${F(n) \leq n}$ , so the first part of the problem is asking whether there exist bad numbers that are sufficiently large. We unpack the definitions: ${n}$ is bad if and only if ${m+p(m) \leq n}$ for any composite ${m}$ , so placing ${m}$ in intervals of the form ${[n-h,n]}$ we are asking to show that

$\displaystyle p(m) \leq h \hbox{ for all composite } m \in [n-h, n]$

for each ${1 \leq h \leq n}$ . To put it another way, the badness of ${n}$ asserts that for each ${1 \leq h \leq n}$ that the residue classes ${0 \hbox{ mod } p}$ for ${p \leq h}$ cover all the natural numbers in the interval ${[n-h,n]}$ except for the primes.

It is now natural to try to understand this problem for a specific choice of interval ${h}$ as a function of ${n}$ . If ${h}$ is large in the sense that ${h > \sqrt{n}}$ , then the claimed covering property is automatic, since every composite number less than or equal to ${n}$ has a prime factor less than or equal to ${\sqrt{n}}$ . On the other hand, for ${h}$ very small, in particular ${h = o(\log n)}$ , it is also possible to find ${n}$ with this property. Indeed, if one takes ${n}$ to lie in the residue class ${0 \hbox{ mod } \prod_{p \leq h}}$ , then we see that the residue classes cover all of ${[n-h,n]}$ except for ${n-1}$ , and from Linnik’s theorem we can ensure that ${n-1}$ is prime. Thus, to rule out bad numbers, we need to understand the covering problem at intermediate scales ${\log n \ll h \ll \sqrt{n}}$ .

A key case is when ${h = n^{1/u}}$ for some ${2 < u < 3}$ . Here, the residue classes ${0 \hbox{ mod } p}$ for ${p \leq h}$ sieve out everything in ${[n-h,n]}$ except for primes and semiprimes, and specifically the semiprimes that are product of two primes between ${n^{1/u}}$ and ${n^{1-1/u}}$ . If one can show for some ${2 < u < 3}$ that the largest gap between semiprimes in say ${[x,2x]}$ with prime factors in ${[x^{1/u}, x^{1-1/u}]}$ is ${o( x^{1/u} )}$ , then this would affirmatively answer the first part of this problem (and also the second). This is certainly very plausible – it would follow from a semiprime version of the Cramér conjecture (and this would also make the more precise prediction ${F(n) = n + n^{1/2-o(1)}}$ ) – but remains well out of reach for now. Even assuming the Riemann hypothesis, the best upper bound on prime gaps in ${[x,2x]}$ is ${O( \sqrt{x} \log x )}$ , and the best upper bound on semiprime gaps is not significantly better than this – in particular, one cannot reach ${x^{1/u}}$ for any ${2 < u < 3}$ . (There is a remote possibility that an extremely delicate analysis near ${u=2}$ , together with additional strong conjectures on the zeta function, such as a sufficiently quantitative version of the GUE hypothesis, may barely be able to resolve this problem, but I am skeptical of this, absent some further major breakthrough in analytic number theory.)

Given that multiplicative number theory does not seem powerful enough (even on RH) to resolve these problems, the other main approach would be to use sieve theory. In this theory, we do not really know how to exploit the specific location of the interval ${[n-h,n]}$ or the specific congruence classes used, so one can study the more general problem of trying to cover an interval ${I}$ of length ${h}$ by one residue class mod ${p}$ for each ${p \leq h}$ , and only leaving a small number of survivors which could potentially be classified as “primes”. The discussion of the small ${h}$ case already reveals a problem with this level of generality: one can sieve out the interval ${[-h, 1]}$ by the residue classes ${0 \hbox{ mod } p}$ for ${p \leq h}$ , and leave only one survivor, ${-1}$ . Indeed, thanks to known bounds on Jacobsthal’s function, one can be more efficient than this; for instance, using equation (1.2) from this paper of Ford, Green, Konyagin, Maynard, and myself, it is possible to completely sieve out any interval of sufficiently large length ${h}$ using only those primes ${p}$ up to ${O(\frac{h \log\log h}{\log h \log\log\log h})}$ . On the other hand, from the work of Iwaniec, we know that sieving up to ${o(h^{1/2})}$ is insufficient to completely sieve out such an interval; related to this, if one only sieves up to ${h^{1/u}}$ for some ${2 < u < 3}$ , the linear sieve (see e.g., Theorem 2 of this previous blog post) shows that one must have at least ${(f(u)+o(1)) \frac{h}{\log h}}$ survivors, where ${f(u)}$ can be given explicitly in the regime ${2 < u < 3}$ by the formula

$\displaystyle f(u) := \frac{2e^\gamma}{u} \log(u-1).$

These lower bounds are not believed to be best possible. For instance, the Maier–Pomerance conjecture on Jacobsthal’s function would indicate that one needs to sieve out primes up to ${\gg h/\log^2 h}$ in order to completely sieve out an interval of length ${h}$ , and it is also believed that sieving up to ${h^{1-\varepsilon}}$ should leave ${\gg_\varepsilon h/\log h}$ survivors, although even these strong conjectures are not enough to positively resolve this problem, since we are permitted to sieve all the way up to ${h}$ (and we are allowed to leave every prime number as a survivor, which in view of the Brun–Titchmarsh theorem could permit as many as ${O(h/\log n)}$ survivors).

Unfortunately, as discussed in this previous blog post, the parity problem blocks such improvements from taking place from most standard analytic number theory methods, in particular sieve theory. A particularly dangerous enemy arises from Siegel zeroes. This is discussed in detail in the papers of of Ford and of Granville mentioned previously, but an informal discussion is as follows. If there is a Siegel zero associated to the quadratic character of some conductor ${q}$ , this roughly speaking means that almost all primes ${p}$ (in certain ranges) will be quadratic non-residues mod ${q}$ . In particular, if one restricts attention to numbers ${n}$ in a residue class ${a \hbox{ mod } q}$ that is a quadratic residue, we then expect most numbers in this class to have an even number of prime factors, rather than an odd number.

This alters the effect of sieving in such residue classes. Consider for instance the classical sieve of Eratosthenes. If one sieves out ${0 \hbox{ mod } p}$ for each prime ${p \leq \sqrt{h}}$ , the sieve of Eratosthenes tells us that the surviving elements of ${[1,h]}$ are simply the primes between ${\sqrt{h}}$ and ${h}$ , of which there are about ${h/\log h}$ many. However, if one restricts attention to ${[1,h] \cap a \hbox{ mod } q}$ for a quadratic residue class ${a \hbox{ mod } q}$ (and taking ${h}$ to be somewhat large compared to ${q}$ ), then by the preceding discussion, this eliminates most primes, and so now sieving out ${0 \hbox{ mod } p}$ should leave almost no survivors. Shifting this example by ${a}$ and then dividing by ${q}$ , one can end up with an example of an interval ${I}$ of length ${h}$ that can be sieved by residue classes ${b_p \hbox{ mod } p}$ for each ${p \leq \sqrt{h}}$ in such a manner as to leave almost no survivors (in particular, ${o(h/\log h)}$ many). In the presence of a Siegel zero, it seems quite difficult to prevent this scenario from “infecting” the above problem, creating a bad scenario in which for all ${\log n \ll h \ll \sqrt{n}}$ , the residue classes ${0 \hbox{ mod } p}$ for ${p \leq \sqrt{h}}$ already eliminate almost all elements of ${[n-h,n]}$ , leaving it mathematically possible for the remaining survivors to either be prime, or eliminated by the remaining residue classes ${0 \hbox{ mod } p}$ for ${\sqrt{h} < p \leq h}$ .

Because of this, I suspect that it will not be possible to resolve this Erdös problem without a major breakthrough on the parity problem that (at a bare minimum) is enough to exclude the possibility of Siegel zeroes existing. (But it is not clear at all that Siegel zeroes are be the only “enemy” here, so absent a major advance in “inverse sieve theory”, one cannot simply assume GRH to run away from this problem).

— 0.1. Addendum: heuristics for Siegel zero scenarios —

This post also provides a good opportunity to refine some heuristics I had previously proposed regarding Siegel zeroes and their impact on various problems in analytic number theory. In this previous blog post, I wrote

“The parity problem can also be sometimes be overcome when there is an exceptional Siegel zero … [this] suggests that to break the parity barrier, we may assume without loss of generality that there are no Siegel zeroes.”

On the other hand, it was pointed out in a more recent article of Granville that (as with the current situation), Siegel zeroes can sometimes serve to enforce the parity barrier, rather than overcome it, and responds to my previous statement with the comment “this claim needs to be treated with caution, since its truth depends on the context”.

I actually agree with Granville here, and I propose here a synthesis of the two situations. In the absence of a Siegel zero, standard heuristic models in analytic number theory (such as the ones discussed in this post) typically suggest that a given quantity ${X}$ of interest in number theory (e.g., the number of primes in a certain set) obey an asymptotic law of the form

$\displaystyle X = \mathrm{Main\ term} + \mathrm{Error\ term}$

where ${\mathrm{Main\ term}}$ is generally fairly well understood, while ${\mathrm{Error\ term}}$ is expected to fluctuate “randomly” (or more precisely, pseudorandomly) and thus be smaller than the main term. However, a major difficulty in analytic number theory is that we often cannot prevent a “conspiracy” from occurring in which the error term becomes as large as, or even larger than the main term: the fluctuations present in that term are often too poorly understood to be under good control. The parity barrier manifests by providing examples of analogous situations in which the error term is indeed as large as the main term (with an unfavorable sign).

However, the presence of a Siegel zero tends to “magnetize” the error term by pulling most of the fluctuations in a particular direction. In many situations, what this means is that one can obtain a refined asymptotic of the form

$\displaystyle X = \mathrm{Main\ term} + \mathrm{Siegel\ correction} + \mathrm{Better\ error\ term}$

where ${\mathrm{Better\ error\ term}}$ now fluctuates less than the original ${\mathrm{Error\ term}}$ , and in particular can (in some cases) be shown to be lower order than ${\mathrm{Main\ term}}$ , while ${\mathrm{Siegel\ correction}}$ is a new term that is often explicitly describable in terms of the exceptional character ${\chi}$ associated to the Siegel zero, as well as the location ${\beta}$ of the Siegel zero ${L(\beta,\chi)=0}$ . A typical example is the problem of estimating the sum ${\sum_{n \leq x: n = a\ (q)} \Lambda(n)}$ of primes in an arithmetic progression. The Siegel–Walfisz theorem gives a bound of the form

$\displaystyle \sum_{n \leq x: n = a\ (q)} \Lambda(n) = \frac{x}{\varphi(q)} + O_A( x \log^{-A} x )$

for any ${A>0}$ (with an ineffective constant); in the regime ${q = O(\log^{O(1)} x)}$ one can improve the error term to ${O( x \exp(-c \log^{1/2} x) )}$ , but for large ${q}$ one cannot do better than the Brun–Titchmarsh bound of ${O(x / \varphi(q))}$ . However, when there is a Siegel zero ${L(\beta,\chi)}$ in an appropriate range, we can obtain the refined bound

$\displaystyle \sum_{n \leq x: n = a\ (q)} \Lambda(n) = \frac{x}{\varphi(q)} - \chi(a) 1_{q_0|q} 1_{(a,q)=1} \frac{x^{\beta-1}}{\beta} + O( x \exp(\log^{-c} x))$

for some ${c>0}$ , where ${q_0}$ is the conductor of ${\chi}$ ; see e.g., Theorem 5.27 of Iwaniec–Kowalski. Thus we see the error term is much improved (and in fact can even be made effective), at the cost of introduicing a Siegel correction term which (for ${\beta}$ close to ${1}$ and ${x}$ not too large) is of comparable size to the main term, and can either be aligned with or against the main term depending on the sign of ${\chi(a)}$ .

The implications of this refined asymptotic then depend rather crucially on how the Siegel correction term is aligned with the main term, and also whether it is of comparable order or lower order. In many situations (particularly those concerning “average case” problems, in which one wants to understand the behavior for typical choices of parameters), the Siegel correction term ends up being lower order, and so one ends up with the situation described in my initial blog post, where we are able to get the predicted asymptotic ${X \approx \mathrm{Main\ term}}$ in the Siegel zero case. However, as pointed out by Granville, there are other situations (particularly those involving “worst case” problems, in which some key parameter can be chosen adversarially) in which the Siegel correction term can align to completely cancel (or to highly reinforce) the main term. In such cases, the Siegel zero becomes a very concrete manifestation of the parity barrier, rather than a means to avoid it. (There is a tiny chance that there may be some sort of “repulsion” phenomenon in which having no semiprimes in ${[n-h,n]}$ for one value of ${h}$ somehow generates semiprimes in ${[n-h',n]}$ for another value of ${h'}$ , which would allow one to solve the problem without having to directly address the Siegel issue, but I don’t see how two such intervals could “communicate” in order to achieve such a repulsion effect.)

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

9 August, 2024 in expository, math.NT | Tags: Alexandru Zaharescu, Hung Bui, Kyle Pratt, Paul Erdos | by Terence Tao | 14 comments

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})}$ .

Dense sets of natural numbers with unusually large least common multiples

8 July, 2024 in math.NT, paper | Tags: least common multiples, Paul Erdos | by Terence Tao | 13 comments

I’ve just uploaded to the arXiv my paper “Dense sets of natural numbers with unusually large least common multiples“. This short paper answers (in the negative) a somewhat obscure question of Erdős and Graham:

Problem 1 Is it true that if ${A}$ is a set of natural numbers for which
$\displaystyle \frac{1}{\log\log x} \sum_{n \in A: n \leq x} \frac{1}{n} \ \ \ \ \ (1)$
goes to infinity as ${x \rightarrow \infty}$ , then the quantity
$\displaystyle \frac{1}{(\sum_{n \in A: n \leq x} \frac{1}{n})^2} \sum_{n,m \in A: n < m \leq x} \frac{1}{\mathrm{lcm}(n,m)} \ \ \ \ \ (2)$
also goes to infinity as ${x \rightarrow \infty}$ ?

At first glance, this problem may seem rather arbitrary, but it can be motivated as follows. The hypothesis that (1) goes to infinity is a largeness condition on ${A}$ ; in view of Mertens’ theorem, it can be viewed as an assertion that ${A}$ is denser than the set of primes. On the other hand, the conclusion that (2) grows is an assertion that ${\frac{1}{\mathrm{lcm}(n,m)}}$ becomes significantly larger than ${\frac{1}{nm}}$ on the average for large ${n,m \in A}$ ; that is to say, that many pairs of numbers in ${A}$ share a common factor. Intuitively, the problem is then asking whether sets that are significantly denser than the primes must start having lots of common factors on average.

For sake of comparison, it is easy to see that if (1) goes to infinity, then at least one pair ${(n,m)}$ of distinct elements in ${A}$ must have a non-trivial common factor. For if this were not the case, then the elements of ${A}$ are pairwise coprime, so each prime ${p}$ has at most one multiple in ${A}$ , and so can contribute at most ${1/p}$ to the sum in (1), and hence by Mertens’ theorem, and the fact that every natural number greater than one is divisible by at least one prime ${p}$ , the quantity (1) stays bounded, a contradiction.

It turns out, though, that the answer to the above problem is negative; one can find sets ${A}$ that are denser than the primes, but for which (2) stays bounded, so that the least common multiples in the set are unusually large. It was a bit surprising to me that this question had not been resolved long ago (in fact, I was not able to find any prior literature on the problem beyond the original reference of Erdős and Graham); in contrast, another problem of Erdős and Graham concerning sets with unusually small least common multiples was extensively studied (and essentially solved) about twenty years ago, while the study of sets with unusually large greatest common divisor for many pairs in the set has recently become somewhat popular, due to their role in the proof of the Duffin-Schaeffer conjecture by Koukoulopoulos and Maynard.

To search for counterexamples, it is natural to look for numbers with relatively few prime factors, in order to reduce their common factors and increase their least common multiple. A particularly simple example, whose verification is on the level of an exercise in a graduate analytic number theory course, is the set of semiprimes (products of two primes), for which one can readily verify that (1) grows like ${\log\log x}$ but (2) stays bounded. With a bit more effort, I was able to optimize the construction and uncover the true threshold for boundedness of (2), which was a little unexpected:

Theorem 2

(i) For any ${C>0}$ , there exists a set of natural numbers ${A}$ with
$\displaystyle \sum_{n \in A: n \leq x} \frac{1}{n} = \exp( (C+o(1)) (\log\log x)^{1/2} \log\log\log x )$
for all large ${x}$ , for which (2) stays bounded.
(ii) Conversely, if (2) stays bounded, then
$\displaystyle \sum_{n \in A: n \leq x} \frac{1}{n} \ll \exp( O( (\log\log x)^{1/2} \log\log\log x ) )$
for all large ${x}$ .

The proofs are not particularly long or deep, but I thought I would record here some of the process towards finding them. My first step was to try to simplify the condition that (2) stays bounded. In order to use probabilistic intuition, I first expressed this condition in probabilistic terms as

$\displaystyle \mathbb{E} \frac{\mathbf{n} \mathbf{m}}{\mathrm{lcm}(\mathbf{n}, \mathbf{m})} \ll 1$

for large ${x}$ , where ${\mathbf{n}, \mathbf{m}}$ are independent random variables drawn from ${\{ n \in A: n \leq x \}}$ with probability density function

$\displaystyle \mathbb{P} (\mathbf{n} = n) = \frac{1}{\sum_{m \in A: m \leq x} \frac{1}{m}} \frac{1}{n}.$

The presence of the least common multiple in the denominator is annoying, but one can easily flip the expression to the greatest common divisor:

$\displaystyle \mathbb{E} \mathrm{gcd}(\mathbf{n}, \mathbf{m}) \ll 1.$

If the expression ${\mathrm{gcd}(\mathbf{n}, \mathbf{m})}$ was a product of a function of ${\mathbf{n}}$ and a function of ${\mathbf{m}}$ , then by independence this expectation would decouple into simpler averages involving just one random variable instead of two. Of course, the greatest common divisor is not of this form, but there is a standard trick in analytic number theory to decouple the greatest common divisor, namely to use the classic Gauss identity ${n = \sum_{d|n} \varphi(d)}$ , with ${\varphi}$ the Euler totient function, to write

$\displaystyle \mathrm{gcd}(\mathbf{n}, \mathbf{m}) = \sum_{d | \mathbf{n}, \mathbf{m}} \varphi(d).$

Inserting this formula and interchanging the sum and expectation, we can now express the condition as bounding a sum of squares:

$\displaystyle \sum_d \varphi(d) \mathbb{P}(d|\mathbf{n})^2 \ll 1.$

Thus, the condition (2) is really an assertion to the effect that typical elements of ${A}$ do not have many divisors. From experience in sieve theory, the probabilities ${\mathbb{P}(d|\mathbf{n})}$ tend to behave multiplicatively in ${d}$ , so the expression here heuristically behaves like an Euler product that looks something like

$\displaystyle \prod_p (1 + \varphi(p) \mathbb{P}(p|\mathbf{n})^2)$

and so the condition (2) is morally something like

$\displaystyle \sum_p p \mathbb{P}(p|\mathbf{n})^2 \ll 1. \ \ \ \ \ (3)$

Comparing this with the Mertens’ theorems, this leads to the heuristic prediction that ${\mathbb{P}(p|\mathbf{n})}$ (for a typical prie ${p}$ much smaller than ${x}$ ) should decay somewhat like ${\frac{1}{p (\log\log p)^{1/2}}}$ (ignoring for now factors of ${\log\log\log p}$ ). This can be compared to the example of the set of primes or semiprimes on one hand, where the probability is like ${\frac{1}{p \log\log p}}$ , and the set of all natural numbers on the other hand, where the probability is like ${\frac{1}{p}}$ . So the critical behavior should come from sets that are in some sense “halfway” between the primes and the natural numbers.

It is then natural to try a random construction, in which one sieves out the natural numbers by permitting each natural number ${n}$ to survive with a probability resembling ${\prod_{p|n} \frac{1}{(\log\log p)^{1/2}}}$ , in order to get the predicted behavior for ${\mathbb{P}(p|\mathbf{n})}$ . Performing some standard calculations, this construction could ensure (2) bounded with a density a little bit less than the one stated in the main theorem; after optimizing the parameters, I could only get something like

$\displaystyle \sum_{n \in A: n \leq x} \frac{1}{n} = \exp( (\log\log x)^{1/2} (\log\log\log x)^{-1/2-o(1)} ).$

I was stuck on optimising the construction further, so I turned my attention to a positive result in the spirit of (ii) of the main theorem. On playing around with (3), I observed that one could use Cauchy-Schwarz and Mertens’ theorem to obtain the bound

$\displaystyle \sum_{p \leq x} \mathbb{P}(p|\mathbf{n}) \ll (\log\log x)^{1/2}$

which was in line with the previous heuristic that ${\mathbb{P}(p|\mathbf{n})}$ should behave like ${\frac{1}{p (\log\log p)^{1/2}}}$ . The left-hand side had a simple interpretation: by linearity of expectation, it was the expected number ${\mathbb{E} \omega(\mathbf{n})}$ of prime factors of ${\mathbf{n}}$ . So the boundedness of (2) implied that a typical element of ${A}$ only had about ${(\log\log x)^{1/2}}$ prime factors, in contrast to the ${\log\log x}$ predicted by the Hardy-Ramanujan law. Standard methods from the anatomy of integers can then be used to see how dense a set with that many prime factors could be, and this soon led to a short proof of part (ii) of the main theorem (I eventually found for instance that Jensen’s inequality could be used to create a particularly slick argument).

It then remained to improve the lower bound construction to eliminate the ${\log\log\log x}$ losses in the exponents. By deconstructing the proof of the upper bound, it became natural to consider something like the set of natural numbers ${n}$ that had at most ${(\log\log n)^{1/2}}$ prime factors. This construction actually worked for some scales ${x}$ – namely those ${x}$ for which ${(\log\log x)^{1/2}}$ was a natural number – but there was some strange “discontinuities” in the analysis that prevented me from establishing the boundedness of (2) for arbitrary scales ${x}$ . The basic problem was that increasing the number of permitted prime factors from one natural number threshold ${k}$ to another ${k+1}$ ended up increasing the density of the set by an unbounded factor (of the order of ${k}$ , in practice), which heavily disrupted the task of trying to keep the ratio (2) bounded. Usually the resolution to these sorts of discontinuities is to use some sort of random “average” of two or more deterministic constructions – for instance, by taking some random union of some numbers with ${k}$ prime factors and some numbers with ${k+1}$ prime factors – but the numerology turned out to be somewhat unfavorable, allowing for some improvement in the lower bounds over my previous construction, but not enough to close the gap entirely. It was only after substantial trial and error that I was able to find a working deterministic construction, where at a given scale one collected either numbers with at most ${k}$ prime factors, or numbers with ${k+1}$ prime factors but with the largest prime factor in a specific range, in which I could finally get the numerator and denominator in (2) to be in balance for every ${x}$ . But once the construction was written down, the verification of the required properties ended up being quite routine.

On product representations of squares

20 May, 2024 in math.NT, paper | Tags: Paul Erdos | by Terence Tao | 24 comments

I’ve just uploaded to the arXiv my paper “On product representations of squares“. This short paper answers (in the negative) a (somewhat obscure) question of Erdös. Namely, for any ${k \geq 1}$ , let ${F_k(N)}$ be the size of the largest subset ${A}$ of ${\{1,\dots,N\}}$ with the property that no ${k}$ distinct elements of ${A}$ multiply to a square. In a paper by Erdös, Sárközy, and Sós, the following asymptotics were shown for fixed ${k}$ :

${F_1(N) = (1+o(1)) N}$ .
${F_2(N) = (\frac{6}{\pi^2} + o(1)) N}$ .
${F_3(N) = (1+o(1)) N}$ .
${F_{4k}(N) = (1+o(1)) \frac{N}{\log N}}$ for ${k \geq 1}$ .
${F_{4k+2}(N) = (\frac{3}{2}+o(1)) \frac{N}{\log N}}$ for ${k \geq 1}$ .
${(\log 2 + o(1)) N \leq F_{2k+1}(N) \leq N}$ for ${k \geq 2}$ .

Thus the asymptotics for ${F_k(N)}$ for odd ${k \geq 5}$ were not completely settled. Erdös asked if one had ${F_k(N) = (1-o(1)) N}$ for odd ${k \geq 5}$ . The main result of this paper is that this is not the case; that is to say, there exists ${c_k>0}$ such that any subset ${A}$ of ${\{1,\dots,N\}}$ of cardinality at least ${(1-c_k) N}$ will contain ${k}$ distinct elements that multiply to a square, if ${N}$ is large enough. In fact, the argument works for all ${k \geq 4}$ , although it is not new in the even case. I will also note that there are now quite sharp upper and lower bounds on ${F_k}$ for even ${k \geq 4}$ , using methods from graph theory: see this recent paper of Pach and Vizer for the latest results in this direction. Thanks to the results of Granville and Soundararajan, we know that the constant ${c_k}$ cannot exceed the Hall-Montgomery constant

$\displaystyle 1 - \log(1+\sqrt{e}) + 2 \int_1^{\sqrt{e}} \frac{\log t}{t+1}\ dt = 0.171500\dots$

and I (very tentatively) conjecture that this is in fact the optimal value for this constant. This looks somewhat difficult, but a more feasible conjecture would be that the ${c_k}$ asymptotically approach the Hall-Montgomery constant as ${k \rightarrow \infty}$ , since the aforementioned result of Granville and Soundararajan morally corresponds to the ${k=\infty}$ case.

In the end, the argument turned out to be relatively simple; no advanced results from additive combinatorics, graph theory, or analytic number theory were required. I found it convenient to proceed via the probabilistic method (although the more combinatorial technique of double counting would also suffice here). The main idea is to generate a tuple ${(\mathbf{n}_1,\dots,\mathbf{n}_k)}$ of distinct random natural numbers in ${\{1,\dots,N\}}$ which multiply to a square, and which are reasonably uniformly distributed throughout ${\{1,\dots,N\}}$ , in that each individual number ${1 \leq n \leq N}$ is attained by one of the random variables ${\mathbf{n}_i}$ with a probability of ${O(1/N)}$ . If one can find such a distribution, then if the density of ${A}$ is sufficienly close to ${1}$ , it will happen with positive probability that each of the ${\mathbf{n}_i}$ will lie in ${A}$ , giving the claim.

When ${k=3}$ , this strategy cannot work, as it contradicts the arguments of Erdös, Särközy, and Sós. The reason can be explained as follows. The most natural way to generate a triple ${(\mathbf{n}_1,\mathbf{n}_2,\mathbf{n}_3)}$ of random natural numbers in ${\{1,\dots,N\}}$ which multiply to a square is to set

$\displaystyle \mathbf{n}_1 := \mathbf{d}_{12} \mathbf{d}_{13}, \mathbf{n}_2 := \mathbf{d}_{12} \mathbf{d}_{23}, \mathbf{n}_3 := \mathbf{d}_{13} \mathbf{d}_{23}$

for some random natural numbers ${\mathbf{d}_{12} \mathbf{d}_{13}, \mathbf{d}_{23}}$ . But if one wants all these numbers to have magnitude ${\asymp N}$ , one sees on taking logarithms that one would need

$\displaystyle \log \mathbf{d}_{12} + \log \mathbf{d}_{13}, \log \mathbf{d}_{12} + \log \mathbf{d}_{23}, \log \mathbf{d}_{13} + \log \mathbf{d}_{23} = \log N + O(1)$

which by elementary linear algebra forces

$\displaystyle \log \mathbf{d}_{12}, \log \mathbf{d}_{13}, \log \mathbf{d}_{23} = \frac{1}{2} \log N + O(1),$

so in particular each of the ${\mathbf{n}_i}$ would have a factor comparable to ${\sqrt{N}}$ . However, it follows from known results on the “multiplication table problem” (how many distinct integers are there in the ${n \times n}$ multiplication table?) that most numbers up to ${N}$ do not have a factor comparable to ${\sqrt{N}}$ . (Quick proof: by the Hardy–Ramanujan law, a typical number of size ${N}$ or of size ${\sqrt{N}}$ has ${(1+o(1)) \log\log N}$ factors, hence typically a number of size ${N}$ will not factor into two factors of size ${\sqrt{N}}$ .) So the above strategy cannot work for ${k=3}$ .

However, the situation changes for larger ${k}$ . For instance, for ${k=4}$ , we can try the same strategy with the ansatz

$\displaystyle \mathbf{n}_1 = \mathbf{d}_{12} \mathbf{d}_{13} \mathbf{d}_{14}; \quad \mathbf{n}_2 = \mathbf{d}_{12} \mathbf{d}_{23} \mathbf{d}_{24}; \quad \mathbf{n}_3 = \mathbf{d}_{13} \mathbf{d}_{23} \mathbf{d}_{34}; \quad \mathbf{n}_4 = \mathbf{d}_{14} \mathbf{d}_{24} \mathbf{d}_{34}.$

Whereas before there were three (approximate) equations constraining three unknowns, now we would have four equations and six unknowns, and so we no longer have strong constraints on any of the ${\mathbf{d}_{ij}}$ . So in principle we now have a chance to find a suitable random choice of the ${\mathbf{d}_{ij}}$ . The most significant remaining obstacle is the Hardy–Ramanujan law: since the ${\mathbf{n}_i}$ typically have ${(1+o(1))\log\log N}$ prime factors, it is natural in this ${k=4}$ case to choose each ${\mathbf{d}_{ij}}$ to have ${(\frac{1}{3}+o(1)) \log\log N}$ prime factors. As it turns out, if one does this (basically by requiring each prime ${p \leq N^{\varepsilon^2}}$ to divide ${\mathbf{d}_{ij}}$ with an independent probability of about ${\frac{1}{3p}}$ , for some small ${\varepsilon>0}$ , and then also adding in one large prime to bring the magnitude of the ${\mathbf{n}_i}$ to be comparable to ${N}$ ), the calculations all work out, and one obtains the claimed result.

	Anonymous on A partial digestion of the HRT…
	jennifer suzuki on The three-dimensional Kakeya c…
	Anonymous on A digestion of the Jacobian co…
	Anonymous on A digestion of the Jacobian co…
	Anonymous on A digestion of the Jacobian co…
	Terence Tao on A partial digestion of the HRT…
	Anonymous on A digestion of the Jacobian co…
	Anonymous on How to assign partial credit o…
	Anonymous on A partial digestion of the HRT…
	pirategenerously045d… on About
	Terence Tao on A partial digestion of the HRT…
	Michael M. Ross on A digestion of the Jacobian co…
	Anonymous on A direct proof of the stationa…
	Anonymous on A partial digestion of the HRT…
	Anonymous on A digestion of the Jacobian co…

Tag Archive

Local Bernstein theory, and lower bounds for Lebesgue constants

Rogers’ theorem on sieving

A crowdsourced project to link up erdosproblems.com to the OEIS

Rough numbers between consecutive primes

On several irrationality problems for Ahmes series

Planar point sets with forbidden four-point patterns and few distinct distances

Erdos problem #385, the parity problem, and Siegel zeroes

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

Dense sets of natural numbers with unusually large least common multiples

On product representations of squares

Recent Comments

Top Posts

Archives

Categories

The Polymath Blog

For commenters