close

Category Archive

You are currently browsing the category archive for the ‘paper’ category.

Primitive sets and von Mangoldt chains: Erdős Problem #1196 and beyond

3 May, 2026 in math.NT, paper | Tags: , , , , , , , , , | by | 24 comments

Boris Alexeev, Kevin Barreto, Yanyang Li, Jared Duker Lichtman, Liam Price, Jibran Iqbal Shah, Quanyu Tang, and I have just uploaded to the arXiv our paper Primitive sets and von Mangoldt chains: Erdős Problem #1196 and beyond. This paper (which is a work in progress) represents our efforts to digest and document the recent flurry of developments around the following problem of Erdős, Sárközy, and Szemerédi on primitive sets:

Conjecture 1 (Erdős problem #1196) Suppose that {A \subset [x,+\infty)} is a primitive set of integers, which means that no element of {A} divides another. Then

\displaystyle \sum_{n \in A} \frac{1}{n \log n} \le 1 + o(1)

as {x \rightarrow \infty}.

One can show that the upper bound of {1 + o(1)} is best possible up to the {o(1)} error by taking {A} to be the set of products of {k} primes for some suitable parameter {k}. This was one of the most well-known open problems in the study of primitive sets, and had attracted some number of partial results (for instance, Lichtman was able to show the upper bound of {e^\gamma \frac{\pi}{4} + o(1) \approx 1.399}). It was thus notable that this problem was first solved by an autonomous AI query (by the fifth author) a few weeks ago. This solution introduced a proof technique – based on Markov chains in the divisibility poset – which in retrospect is very natural for controlling primitive sets, but which had not been explicitly used in previous literature, though in retrospect many of the arguments in that literature involved a specific Markov chain which we call the downwards Mertens chain. The proof instead revolved around a different Markov chain, which we call the downwards von Mangoldt chain, which manages to neatly avoid the “{e^\gamma}” type losses in the previous Mertens-based arguments, and resolve Conjecture 1. In this paper we develop the Markov chain approach more systematically, and show that it settles several further conjectures concerning primitive sets, and also provides simpler proofs of some previous results in the literature. More precisely, in addition to Conjecture 1, we establish the following:

Theorem 2 (Erdős primitive set conjecture, #164) For any primitive {A} consisting of numbers greater than {1},

\displaystyle \sum_{n \in A} \frac{1}{n \log n} \le \sum_p \frac{1}{p \log p}.

Theorem 3 (Odd Banks–Martin) Let {k\ge 1} and suppose {A} is a primitive set consisting of odd numbers with at most {k} prime factors. Then

\displaystyle \sum_{n \in A} \frac{1}{n \log n} \leq \sum_{n \in \mathbb N_k(\mathcal Q)} \frac{1}{n \log n},

where {\mathcal Q} denotes the primes appearing as factors of elements of {A}, and {\mathbb N_k({\mathcal Q})} is the collection of products of {k} primes from {\mathcal Q}.

Theorem 4 ({2} is Erdős-strong) If {A} is a primitive set consisting of even numbers, then

\displaystyle \sum_{n \in A} \frac{1}{n \log n} \le \frac{1}{2\log 2}.

Theorem 5 (Ahlswede–Khachatrian–Sárközy) If {A} is a primitive set, then

\displaystyle \sum_{n \in A \cap [y/x,y]} \frac{1}{n} \ll \frac{\log x}{\sqrt{\log\log x}}

whenever {3 \leq x \leq y}.

Theorem 6 (Erdős–Sárközy–Szemerédi, #1217) Let {A \subset {\bf N}} be such that the upper doubly logarithmic density

\displaystyle \Delta := \limsup_{x\rightarrow\infty}\frac{1}{\log\log x} \sum_{n \in A \cap [2,x]} \frac{1}{n \log n}

is positive. Then there exists a strictly increasing infinite divisibility chain

\displaystyle n_0 | n_1 | n_2 | \dots

in {A} such that

\displaystyle \limsup_{x\rightarrow\infty}\frac{1}{\log\log x} \# \{ i: n_i \leq x \} \geq \Delta.

Theorem 2 and Theorem 5 had been previously established by Lichtman and Ahlswede–Khachatrian–Sárközy respectively, but the Markov chain formalism gives shorter (and more unified) proofs of both. Theorems 3, 4, 6 were open conjectures that can now be settled by this method. These results were obtained with varying levels of AI involvement, ranging from completely autonomous AI queries to traditional pen-and-paper calculations, to various hybrid approaches (for instance, with humans suggesting key inequalities that could then be rapidly tested numerically or even proved by various AI tools).

Read the rest of this entry »

Products of consecutive integers with unusual anatomy

31 March, 2026 in math.NT, paper | Tags: , , | by | 16 comments

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Theorem 1
  • The number of numbers up to {x} that lie in a bad interval of length {H>1} is {O(1/\log^{1-o(1)} x)} of the number of bad points up to {x}.
  • The number of numbers up to {x} that lie in a very bad interval of length {H>1} is {O(x^{2/5+o(1)})}.
  • The number of numbers up to {x} of the form {N+H} for a solution to (1) is {O(x^{1/2+o(1)})}.

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

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

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

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

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

Mathematical methods and human thought in the age of AI

29 March, 2026 in math.HO, non-technical, paper | Tags: , , | by | 38 comments

Tanya Klowden and I have uploaded to the arXiv our preprint “Mathematical methods and human thought in the age of AI“. This is an unabridged version of a solicited article for a forthcoming Blackwell Companion to the Philosophy of Mathematics. I rarely write article-length essays of a philosophical nature (perhaps the last one was in 2007), but given the topical interest in AI and formalization for mathematics, which has begun to raise increasingly fundamental questions about what the nature, purpose and practice of mathematics actually is (or ought to be), it seemed like it was a timely opportunity to write about these matters. Other mathematicians seem to have recently come to this conclusion also; see for instance this paper of Avigad, or this paper of Commelin, Jamnik, Ochigame, Taelman, and Venkatesh, both of which have come out in the last few weeks.

Our piece took over a year to write – which means, at the current pace of development in the field, that some of it is already slightly out of date. Nevertheless, it was an instructive exercise for both of us to try to look beyond the immediate technical issues presented by current AI and formalization tools and try to point out the philosophical questions that we will have to grapple with as these tools become increasingly capable and integrated into our profession, using prior examples of technological advancement as a guide. We don’t pretend to have definitive answers to most of these questions, but as with mathematics itself, the first step is to pose the questions and then try to make partial progress on them (or at least identify some negative results and eliminate some failed approaches). One point we particularly felt worth stressing is that AI tools and applications (in mathematics or elsewhere) should not be viewed purely through the technical lens of what microscale problems they solve and how effective or efficient they are at solving them, but also through the macroscopic humanitarian lens of how our society, our shared body of knowledge and understanding, and our species benefits (or is harmed) as a whole from these technologies.

Our initial submission ended up significantly exceeding the page limits of the submission and ventured beyond the philosophy of mathematics into broader philosophical and ethical questions about AI in general. A streamlined version of the paper will appear in the forthcoming companion, but we have decided to make the original longer version available on the arXiv.

Local Bernstein theory, and lower bounds for Lebesgue constants

23 March, 2026 in math.CA, math.CV, paper | Tags: , , , | by | 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.)

Six Math Essentials

16 February, 2026 in advertising, book, math.GM | Tags: | by | 22 comments

Just a brief announcement that I have been working with Quanta Books to publish a short book in popular mathematics entitled “Six Math Essentials“, which will cover six of the fundamental concepts in mathematics — numbers, algebra, geometry, probability, analysis, and dynamics — and how they connect with our real-world intuition, the history of math and science, and to modern practice of mathematics, both in theory and in applications. The scheduled publication date is Oct 27, but it is currently available for preorder.

Polynomial towers and inverse Gowers theory for bounded-exponent groups

6 January, 2026 in math.CO, math.DS, paper | Tags: , , , | by | 5 comments

Asgar Jamneshan, Or Shalom and I have uploaded to the arXiv our paper “ Polynomial towers and inverse Gowers theory for bounded-exponent groups“. This continues our investigation into the ergodic-theory approach to the inverse theory of Gowers norms over finite abelian groups {G}. In this regard, our main result establishes a satisfactory (qualitative) inverse theorem for groups {G} of bounded exponent:

Theorem 1 Let {G} be a finite abelian group of some exponent {m}, and let {f: G \rightarrow {\bf C}} be {1}-bounded with {\|f\|_{U^{k+1}(G)} > \delta}. Then there exists a polynomial {P: G \rightarrow {\bf R}/{\bf Z}} of degree at most {k} such that

\displaystyle |\mathop{\bf E}_{x \in G} f(x) e(-P(x))| \gg_{k,m,\delta} 1.

This type of result was previously known in the case of vector spaces over finite fields (by work of myself and Ziegler), groups of squarefree order (by work of Candela, González-Sánchez, and Szegedy), and in the {k \leq 2} case (by work of Jamneshan and myself). The case {G = ({\bf Z}/4{\bf Z})^n}, for instance, is treated by this theorem but not covered by previous results. In the aforementioned paper of Candela et al., a result similar to the above theorem was also established, except that the polynomial {P} was defined in an extension of {G} rather than in {G} itself (or equivalently, {f} correlated with a projection of a phase polynomial, rather than directly with a phase polynomial on {G}). This result is consistent with a conjecture of Jamneshan and myself regarding what the “right” inverse theorem should be in any finite abelian group {G} (not necessarily of bounded exponent).

In contrast to previous work, we do not need to treat the “high characteristic” and “low characteristic” cases separately; in fact, many of the delicate algebraic questions about polynomials in low characteristic do not need to be directly addressed in our approach, although this is at the cost of making the inductive arguments rather intricate and opaque.

As mentioned above, our approach is ergodic-theoretic, deriving the above combinatorial inverse theorem from an ergodic structure theorem of Host–Kra type. The most natural ergodic structure theorem one could establish here, which would imply the above theorem, would be the statement that if {\Gamma} is a countable abelian group of bounded exponent, and {X} is an ergodic {\Gamma}-system of order at most {k} in the Host–Kra sense, then {X} would be an Abramov system – generated by polynomials of degree at most {k}. This statement was conjectured many years ago by Bergelson, Ziegler, and myself, and is true in many “high characteristic” cases, but unfortunately fails in low characteristic, as recently shown by Jamneshan, Shalom, and myself. However, we are able to recover a weaker version of this statement here, namely that {X} admits an extension which is an Abramov system. (This result was previously established by Candela et al. in the model case when {\Gamma} is a vector space over a finite field.) By itself, this weaker result would only recover a correlation with a projected phase polynomial, as in the work of Candela et al.; but the extension we construct arises as a tower of abelian extensions, and in the bounded exponent case there is an algebraic argument (hinging on a certain short exact sequence of abelian groups splitting) that allows one to map the functions in this tower back to the original combinatorial group {G} rather than an extension thereof, thus recovering the full strength of the above theorem.

It remains to prove the ergodic structure theorem. The standard approach would be to describe the system {X} as a Host–Kra tower

\displaystyle Z^{\leq 0}(X) \leq Z^{\leq 1}(X) \leq \dots \leq Z^{\leq k}(X) = X,

where each extension {Z^{\leq j+1}(X)} of {Z^{\leq j}(X)} is a compact abelian group extension by a cocycle of “type” {j}, and them attempt to show that each such cocycle is cohomologous to a polynomial cocycle. However, this appears to be impossible in general, particularly in low characteristic, as certain key short exact sequences fail to split in the required ways. To get around this, we have to work with a different tower, extending various levels of this tower as needed to obtain additional good algebraic properties of each level that enables one to split the required short exact sequences. The precise properties needed are rather technical, but the main ones can be described informally as follows:

  • We need the cocycles to obey an “exactness” property, in that there is a sharp correspondence between the type of the cocycle (or any of its components) and its degree as a polynomial cocycle. (By general nonsense, any polynomial cocycle of degree {\leq d-1} is automatically of type {\leq d}; exactness, roughly speaking, asserts the converse.) Informally, the cocycles should be “as polynomial as possible”.
  • The systems in the tower need to have “large spectrum” in that the set of eigenvalues of the system form a countable dense subgroup of the Pontryagin dual of the acting group {\Gamma} (in fact we demand that a specific countable dense subgroup {\tilde \Gamma} is represented).
  • The systems need to be “pure” in the sense that the sampling map {\iota_{x_0} P(\gamma) := P(T^\gamma x_0)} that maps polynomials on the system to polynomials on the group {\Gamma} is injective for a.e. {x_0}, with the image being a pure subgroup. Informally, this means that the problem of taking roots of a polynomial in the system is equivalent to the problem of taking roots of the corresponding polynomial on the group {\Gamma}. In low characteristic, the root-taking problem becomes quite complicated, and we do not give a good solution to this problem either in the ergodic theory setting or the combinatorial one; however, purity at least lets one show that the two problems are (morally) equivalent to each other, which turns out to be what is actually needed to make the arguments work. There is also a technical “relative purity” condition we need to impose at each level of the extension to ensure that this purity property propagates up the tower, but I will not describe it in detail here.

It is then possible to recursively construct a tower of extensions that eventually reaches an extension of {X}, for which the above useful properties of exactness, large spectrum, and purity are obeyed, and that the system remains Abramov at each level of the tower. This requires a lengthy process of “straightening” the cocycle by differentiating it, obtaining various “Conze–Lesigne” type equations for the derivatives, and then “integrating” those equations to place the original cocycle in a good form. At multiple stages in this process it becomes necessary to have various short exact sequences of (topological) abelian groups split, which necessitates the various good properties mentioned above. To close the induction one then has to verify that these properties can be maintained as one ascends the tower, which is a non-trivial task in itself.

The maximal length of the Erdős–Herzog–Piranian lemniscate in high degree

15 December, 2025 in math.CV, paper | Tags: , , | by | 20 comments

I’ve just uploaded to the arXiv my preprint The maximal length of the Erdős–Herzog–Piranian lemniscate in high degree. This paper resolves (in the asymptotic regime of sufficiently high degree) an old question about the polynomial lemniscates

\displaystyle \partial E_1(p) := \{ z: |p(z)| = 1\}

attached to monic polynomials {p} of a given degree {n}, and specifically the question of bounding the arclength {\ell(\partial E_1(p))} of such lemniscates. For instance, when {p(z)=z^n}, the lemniscate is the unit circle and the arclength is {2\pi}; this in fact turns out to be the minimum possible length amongst all (connected) lemniscates, a result of Pommerenke. However, the question of the largest lemniscate length is open. The leading candidate for the extremizer is the polynomial

\displaystyle p_0(z)= z^n-1

whose lemniscate is quite convoluted, with an arclength that can be computed asymptotically as

\displaystyle \ell(\partial E_1(p_0)) = B(1/2,n/2) = 2n + 4 \log 2 + O(1/n)

where {B} is the beta function.

BERJAYA

(The images here were generated using AlphaEvolve and Gemini.) A reasonably well-known conjecture of Erdős, Herzog, and Piranian (Erdős problem 114) asserts that this is indeed the maximizer, thus {\ell(\partial E_1(p)) \leq \ell(\partial E_1(p_0))} for all monic polynomials of degree {n}.

There have been several partial results towards this conjecture. For instance, Eremenko and Hayman verified the conjecture when {n=2}. Asympotically, bounds of the form {\ell(\partial E_1(p)) \leq (C+o(1)) n} had been known for various {C} such as {\pi}, {2\pi}, or {4\pi}; a significant advance was made by Fryntov and Nazarov, who obtained the asymptotically sharp upper bound

\displaystyle \ell(\partial E_1(p)) \leq 2n + O(n^{7/8})

and also obtained the sharp conjecture {\ell(\partial E_1(p)) \leq \ell(\partial E_1(p_0))} for {p} sufficiently close to {p_0}. In that paper, the authors comment that the {O(n^{7/8})} error could be improved, but that {O(n^{1/2})} seemed to be the limit of their method.

I recently explored this problem with the optimization tool AlphaEvolve, where I found that when I assigned this tool the task of optimizing {\ell(\partial E_1(p))} for a given degree {n}, that the tool rapidly converged to choosing {p} to be equal to {p_0} (up to the rotation and translation symmetries of the problem). This suggested to me that the conjecture was true for all {n}, though of course this was far from a rigorous proof. AlphaEvolve also provided some useful visualization code for these lemniscates which I have incorporated into the paper (and this blog post), and which helped build my intuition for this problem; I view this sort of “vibe-coded visualization” as another practical use-case of present-day AI tools.

In this paper, we iteratively improve upon the Fryntov-Nazarov method to obtain the following bounds, in increasing order of strength:

  • (i) {\ell(\partial E_1(p)) \leq 2n + O(n^{1/2})}.
  • (ii) {\ell(\partial E_1(p)) \leq 2n + O(1)}.
  • (iii) {\ell(\partial E_1(p)) \leq 2n + 4 \log 2 + o(1)}.
  • (iv) {\ell(\partial E_1(p)) \leq \ell(\partial E_1(p_0))} for sufficiently large {n}.
In particular, the Erdős–Herzog–Piranian conjecture is now verified for sufficiently large {n}.

The proof of these bounds is somewhat circuitious and technical, with the analysis from each part of this result used as a starting point for the next one. For this blog post, I would like to focus on the main ideas of the arguments.

A key difficulty is that there are relatively few tools for upper bounding the arclength of a curve; indeed, the coastline paradox already shows that curves can have infinite length even when bounded. Thus, one needs to utilize some smooth or algebraic structure on the curve to hope for good upper bounds. One possible approach is via the Crofton formula, using Bezout’s theorem to control the intersection of the curve with various lines. This is already good enough to get bounds of the form {\ell(\partial E_1(p)) \leq O(n)} (for instance by combining it with other known tools to control the diameter of the lemniscate), but it seems challenging to use this approach to get bounds close to the optimal {\sim 2n}.

Instead, we follow Fryntov–Nazarov and utilize Stokes’ theorem to convert the arclength into an area integral. A typical identity used in that paper is

\displaystyle \ell(\partial E_1(p)) = 2 \int_{E_1(p)} |p'|\ dA - \int_{E_1(p)} \frac{|p\varphi|}{\varphi} \psi\ dA

where {dA} is area measure, {\varphi = p'/p} is the log-derivative of {p}, {\psi = p''/p'} is the log-derivative of {p'}, and {E_1(p)} is the region {\{ |p| \leq 1 \}}. This and the triangle inequality already lets one prove bounds of the form {\ell(\partial E_1(p)) \leq 2\pi n + O(n^{1/2})} by controlling {\int_{E_1(p)} |\psi|\ dA} using the triangle inequality, the Hardy-Littlewood rearrangement inequality, and the Polya capacity inequality.

But this argument does not fully capture the oscillating nature of the phase {\frac{|\varphi|}{\varphi}} on one hand, and the oscillating nature of {E_1(p)} on the other. Fryntov–Nazarov exploited these oscillations with some additional decompositions and integration by parts arguments. By optimizing these arguments, I was able to establish an inequality of the form

\displaystyle \ell(\partial E_1(p)) \leq \frac{1}{\pi} \int_{E_2(p)} |\psi|\ dA + O(X_1+X_2+X_3+X_4+X_5) \ \ \ \ \ (1)

where {E_2(p) = \{ |p| \leq 2\}} is an enlargement of {E_1(p)} (that is significantly less oscillatory, as displayed in the figure below), and {X_1,\dots,X_5} are certain error terms that can be controlled by a number of standard tools (e.g., the Grönwall area theorem).

One can heuristically justify (1) as follows. Suppose we work in a region where the functions {\psi}, {p} are roughly constant: {\psi(z) \approx \psi_0}, {p(z) \approx c_0}. For simplicity let us normalize {\psi_0} to be real, and {c_0} to be negative real. In order to have a non-trivial lemniscate in this region, {c_0} should be close to {-1}. Because the unit circle {\partial D(0,1)} is tangent to the line {\{ w: \Re w = -1\}} at {-1}, the lemniscate condition {|p(z)|=1} is then heuristically approximated by the condition that {\Re (p(z) + 1) = 0}. On the other hand, the hypothesis {\psi(z) \approx \psi_0} suggests that {p'(z) \approx A e^{\psi_0 z}} for some amplitude {z}, which heuristically integrates to {p(z) \approx c_0 + \frac{A}{\psi_0} e^{\psi_0 z}}. Writing {\frac{A}{\psi_0}} in polar coordinates as {Re^{i\theta}} and {z} in Cartesian coordinates as {x+iy}, the condition {\Re(p(z)+1)=0} can then be rearranged after some algebra as

\displaystyle \cos (\psi_0 y + \theta) \approx -\frac{1+c_0}{Re^{\psi_0 x}}.

If the right-hand side is much larger than {1} in magnitude, we thus expect the lemniscate to be empty in this region; but if instead the right-hand side is much less than {1} in magnitude, we expect the lemniscate to behave like a periodic sequence of horizontal lines of spacing {\frac{\pi}{\psi_0}}. This makes the main terms on both sides of (1) approximately agree (per unit area).

A graphic illustration of (1) (provided by Gemini) is shown below, where the dark spots correspond to small values of {\psi} that act to “repel” (and shorten) the lemniscate. (The bright spots correspond to the critical points of {p}, which in this case consist of six critical points at the origin and one at both of {+1/2} and {-1/2}.)

BERJAYA

By choosing parameters appropriately, one can show that {X_1,\dots,X_5 = O(\sqrt{n})} and {\frac{1}{\pi} \int_{E_2(p)} |\psi|\ dA \leq 2n + O(1)}, yielding the first bound {\ell(\partial E_1(p)) \leq 2n + O(n^{1/2})}. However, by a more careful inspection of the arguments, and in particular measuring the defect in the triangle inequality

\displaystyle |\psi(z)| = |\sum_\zeta \frac{1}{z-\zeta}| \leq \sum_\zeta \frac{1}{|z-\zeta|},

where {\zeta} ranges over critical points. From some elementary geometry, one can show that the more the critical points {\zeta} are dispersed away from each other (in an {\ell^1} sense), the more one can gain over the triangle inequality here; conversely, the {L^1} dispersion {\sum_\zeta |\zeta|} of the critical points (after normalizing so that these critical points have mean zero) can be used to improve the control on the error terms {X_1,\dots,X_5}. Optimizing this strategy leads to the second bound

\displaystyle \ell(\partial E_1(p)) \leq 2n + O(1).

At this point, the only remaining cases that need to be handled are the ones with bounded dispersion: {\sum_\zeta |\zeta| \leq 1}. In this case, one can do some elementary manipulations of the factorization

\displaystyle p'(z) = n \prod_\zeta (z-\zeta)

to obtain some quite precise control on the asymptotics of {p(z)} and {p'(z)}; for instance, we will be able to obtain an approximation of the form

\displaystyle p(z) \approx -1 + \frac{z p'(z)}{n}

with high accuracy, as long as {z} is not too close to the origin or to critical points. This, combined with direct arclength computations, can eventually lead to the third estimate

\displaystyle \ell(\partial E_1(p)) \leq 2n + 4 \log 2 + o(1).

The last remaining cases to handle are those of small dispersion, {\sum_\zeta |\zeta| = o(1)}. An extremely careful version of the previous analysis can now give an estimate of the shape

\displaystyle \ell(\partial E_1(p)) \leq \ell(\partial E_1(p_0)) - c \|p\| + o(\|p\|)

for an absolute constant {c>0}, where {\|p\|} is a measure of how close {p} is to {p_0} (it is equal to the dispersion {\sum_\zeta |\zeta|} plus an additional term {n |1 + p(0)|^{1/n}} to deal with the constant term {p(0)}). This establishes the final bound (for {n} large enough), and even shows that the only extremizer is {p_0} (up to translation and rotation symmetry).

The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale

9 December, 2025 in math.RA, paper | Tags: , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , | by | 19 comments

Matthew Bolan, Joachim Breitner, Jose Brox, Nicholas Carlini, Mario Carneiro, Floris van Doorn, Martin Dvorak, Andrés Goens, Aaron Hill, Harald Husum, Hernán Ibarra Mejia, Zoltan Kocsis, Bruno Le Floch, Amir Livne Bar-on, Lorenzo Luccioli, Douglas McNeil, Alex Meiburg, Pietro Monticone, Pace P. Nielsen, Emmanuel Osalotioman Osazuwa, Giovanni Paolini, Marco Petracci, Bernhard Reinke, David Renshaw, Marcus Rossel, Cody Roux, Jérémy Scanvic, Shreyas Srinivas, Anand Rao Tadipatri, Vlad Tsyrklevich, Fernando Vaquerizo-Villar, Daniel Weber, Fan Zheng, and I have just uploaded to the arXiv our preprint The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale. This is the final report for the Equational Theories Project, which was proposed in this blog post and also showcased in this subsequent blog post. The aim of this project was to see whether one could collaboratively achieve a large-scale systematic exploration of a mathematical space, which in this case was the implication graph between 4694 equational laws of magmas. A magma is a set {G} equipped with a binary operation {\diamond: G \times G \rightarrow G} (or, equivalently, a {G \times G} multiplication table). An equational law is an equation involving this operation and a number of indeterminate variables. Some examples of equational laws, together with the number that we assigned to that law, include

Up to relabeling and symmetry, there turn out to be 4694 equational laws that involve at most four invocations of the magma operation {\diamond}; one can explore them in our “Equation Explorer” tool.

The aim of the project was to work out which of these laws imply which others. For instance, all laws imply the trivial law {E1}, and conversely the singleton law {E2} implies all the others. On the other hand, the commutative law {E43} does not imply the associative law {E4512} (because there exist magmas that are commutative but not associative), nor is the converse true. All in all, there are {22,028,942} implications of this type to settle; most of these are relatively easy and could be resolved in a matter of minutes by an expert in college-level algebra, but prior to this project, it was impractical to actually do so in a manner that could be feasibly verified. Also, this problem is known to become undecidable for sufficiently long equational laws. Nevertheless, we were able to resolve all the implications informally after two months, and have them completely formalized in Lean after a further five months.

After a rather hectic setup process (documented in this personal log), progress came in various waves. Initially, huge swathes of implications could be resolved first by very simple-minded techniques, such as brute-force searching all small finite magmas to refute implications; then, automated theorem provers such as Vampire or Mace4 / Prover9 were deployed to handle a large fraction of the remainder. A few equations had existing literature that allowed for many implications involving them to be determined. This left a core of just under a thousand implications that did not fall to any of the “cheap” methods, and which occupied the bulk of the efforts of the project. As it turns out, all of the remaining implications were negative; the difficulty was to construct explicit magmas that obeyed one law but not another. To do this, we discovered a number of general constructions of magmas that were effective at this task. For instance:

  • Linear models, in which the carrier {G} was a (commutative or noncommutative) ring and the magma operation took the form {x \diamond y = ax + by} for some coefficients {a,b}, turned out to resolve many cases.
  • We discovered a new invariant of an equational law, which we call the “twisting semigroup” of that law, which also allowed us to construct further examples of magmas that obeyed one law {E} but not another {E'}, by starting with a base magma {M} that obeyed both laws, taking a Cartesian power {M^n} of that magma, and then “twisting” the magma operation by certain permutations of {\{1,\dots,n\}} designed to preserve {E} but not {E'}.
  • We developed a theory of “abelian magma extensions”, similar to the notion of an abelian extension of a group, which allowed us to flexibly build new magmas out of old ones in a manner controlled by a certain “magma cohomology group {H^1_E(G,M)}” which were tractable to compute, and again gave ways to construct magmas that obeyed one law {E} but not another {E'}.
  • Greedy methods, in which one fills out an infinite multiplication table in a greedy manner (somewhat akin to naively solving a Sudoku puzzle), subject to some rules designed to avoid collisions and maintain a law {E}, as well as some seed entries designed to enforce a counterexample to a separate law {E'}. Despite the apparent complexity of this method, it can be automated in a manner that allowed for many outstanding implications to be refuted.
  • Smarter ways to utilize automated theorem provers, such as strategically adding in additional axioms to the magma to help narrow the search space, were developed over the course of the project.

Even after applying all these general techniques, though, there were about a dozen particularly difficult implications that resisted even these more powerful methods. Several ad hoc constructions were needed in order to understand the behavior of magmas obeying such equations as E854, E906, E1323, E1516, and E1729, with the latter taking months of effort to finally solve and then formalize.

A variety of GUI interfaces were also developed to facilitate the collaboration (most notably the Equation Explorer tool mentioned above), and several side projects were also created within the project, such as the exploration of the implication graph when the magma was also restricted to be finite. In this case, we resolved all of the {22,028,942} implications except for one (and its dual):

Problem 1 Does the law {x = y \diamond (x \diamond ((y \diamond x) \diamond y))} (E677) imply the law {x = ((x \diamond x) \diamond x) \diamond x} (E255) for finite magmas?

See this blueprint page for some partial results on this problem, which we were unable to resolve even after months of effort.

Interestingly, modern AI tools did not play a major role in this project (but it was largely completed in 2024, before the most recent advanced models became available); while they could resolve many implications, the older “good old-fashioned AI” of automated theorem provers were far cheaper to run and already handled the overwhelming majority of the implications that the advanced AI tools could. But I could imagine that such tools would play a more prominent role in future similar projects.

Quantitative correlations and some problems on prime factors of consecutive integers

1 December, 2025 in math.NT, paper | Tags: , , | by | 4 comments

Joni Teravainen and I have uploaded to the arXiv our paper “Quantitative correlations and some problems on prime factors of consecutive integers“. This paper applies modern analytic number theory tools – most notably, the Maynard sieve and the recent correlation estimates for bounded multiplicative functions of Pilatte – to resolve (either partially or fully) some old problems of Erdős, Strauss, Pomerance, Sárközy, and Hildebrand, mostly regarding the prime counting function

\displaystyle \omega(n) := \sum_{p|n} 1

and its relatives. The famous Hardy–Ramanujan and Erdős–Kac laws tell us that asymptotically for {n \sim x}, {\omega(n)} should behave like a gaussian random variable with mean and variance both close to {\log\log x}; but the question of the joint distribution of consecutive values such as {\omega(n), \omega(n+1)} is still only partially understood. Aside from some lower order correlations at small primes (arising from such observations as the fact that precisely one of {n,n+1} will be divisible by {2}), the expectation is that such consecutive values behave like independent random variables. As an indication of the state of the art, it was recently shown by Charamaras and Richter that any bounded observables {f(\omega(n))}, {g(\omega(n+1))} will be asymptotically decorrelated in the limit {n \rightarrow \infty} if one performs a logarithmic statistical averaging. Roughly speaking, this confirms the independence heuristic at the scale {\sqrt{\log\log x}} of the standard deviation, but does not resolve finer-grained information, such as precisely estimating the probability of the event {\omega(n)=\omega(n+1)}.

Our first result, answering a question of Erdős, shows that there are infinitely many {n} for which one has the bound

\displaystyle \omega(n+k) \ll k

for all {k \geq 1}. For {k \gg \log\log n}, such a bound is already to be expected (though not completely universal) from the Hardy–Ramanujan law; the main difficulty is thus with the short shifts {k = o(\log\log n)}. If one only had to demonstrate this type of bound for a bounded number of {k}, then this type of result is well within standard sieve theory methods, which can make any bounded number of shifts {n+k} “almost prime” in the sense that {\omega(n+k)} becomes bounded. Thus the problem is that the “sieve dimension” {\sim \log\log n} grows (slowly) with {n}. When writing about this problem in 1980, Erdős and Graham write “we just know too little about sieves to be able to handle such a question (“we” here means not just us but the collective wisdom (?) of our poor struggling human race)”.

However, with the advent of the Maynard sieve (also sometimes referred to as the Maynard–Tao sieve), it turns out to be possible to sieve for the conditions {\omega(n+k) \ll k} for all {k = o(\log\log n)} simultaneously (roughly speaking, by sieving out any {n} for which {n+k} is divisible by a prime {p \ll x^{1/\exp(Ck)}} for a large {C}), and then performing a moment calculation analogous to the standard proof (due to Turán) of the Hardy–Ramanujan law, but weighted by the Maynard sieve. (In order to get good enough convergence, one needs to control fourth moments as well as second moments, but these are standard, if somewhat tedious, calculations).

Our second result, which answers a separate question of Erdős, establishes that the quantity

\displaystyle \sum_n \frac{\omega(n)}{2^n} = 0.5169428\dots

is irrational; this had recently been established by Pratt under the assumption of the prime tuples conjecture, but we are able to establish this result unconditoinally. The binary expansion of this number is of course closely related to the distribution of {\omega}, but in view of the Hardy–Ramanujan law, the {n^{th}} digit of this number is influenced by about {\log\log\log n} nearby values of {\omega}, which is too many correlations for current technology to handle. However, it is possible to do some “Gowers norm” type calculations to decouple things to the point where pairwise correlation information is sufficient. To see this, suppose for contradiction that this number was a rational {a/q}, thus

\displaystyle q \sum_n \frac{\omega(n)}{2^n} = 0 \hbox{ mod } 1.

Multiplying by {2^n}, we obtain some relations between shifts {\omega(n+h)}:

\displaystyle q \sum_{h=1}^\infty \frac{\omega(n+h)}{2^h} = 0 \hbox{ mod } 1.

Using the additive nature of {\omega}, one then also gets similar relations on arithmetic progressions, for many {n} and {p}:

\displaystyle q \sum_{h=1}^\infty \frac{\omega(n+ph)}{2^h} = 0 \hbox{ mod } 1.

Taking alternating sums of this sort of identity for various {n} and {p} (in analogy to how averages involving arithmetic progressions can be related to Gowers norm-type expressions over cubes), one can eventually arrive eliminate the contribution of small {H}, and arrive at an identity of the form

\displaystyle q \sum_{h=1}^\infty \frac{\sum_{\epsilon \in \{0,1\}^K} (-1)^{|\epsilon|} \omega(n + r_{\epsilon,h+K})}{2^{h+K}} = 0 \hbox{ mod } 1 \ \ \ \ \ (1)

 for many {n}, where {K} is a parameter (we eventually take {K \sim \log\log\log\log n}) and {r_{\epsilon,h+K}} are various shifts that we will not write out explicitly here. This looks like quite a messy expression; however, one can adapt proofs of the Erdős–Kac law and show that, as long as one ignores the contribution of really large prime factors (of order {\gg n^{1/10}}, say) to the {\omega(n + r_{\epsilon,h+K})}, that this sort of sum behaves like a gaussian, and in particular once one can show a suitable local limit theorem, one can contradict (1). The contribution of the large prime factors does cause a problem though, as a naive application of the triangle inequality bounds this contribution by {O(1)}, which is an error that overwhelms the information provided by (1). To resolve this we have to adapt the pairwise correlation estimates of Pilatte mentioned earlier to demonstrate that the these contributions are in fact {o(1)}. Here it is important that the error estimates of Pilatte are quite strong (of order {O(\log^{-c} n)}); previous correlation estimates of this type (such as those used in this earlier paper with Joni) turn out to be too weak for this argument to close.

Our final result concerns the asymptotic behavior of the density

\displaystyle \frac{1}{x} \{n \leq x: \omega(n+1) = \omega(n)\}

(we also address similar questions for {\Omega(n+1)=\Omega(n)} and {\tau(n+1)=\tau(n)}). Heuristic arguments led Erdős, Pomerance, and Sárközy to conjecture that this quantity was asymptotically {\frac{1}{2\sqrt{\pi \log\log x}}}. They were able to establish an upper bound of {O(1/\log\log x)}, while Hildebrand obtained a lower bound of {\gg 1/(\log\log x)^3}, due to Hildebrand. Here, we obtain the asymptotic for almost all {x} (the limitation here is the standard one, which is that the current technology on pairwise correlation estimates either requires logarithmic averaging, or is restricted to almost all scales rather than all scales). Roughly speaking, the idea is to use the circle method to rewrite the above density in terms of expressions

\displaystyle \frac{1}{x} \sum_{n \leq x} e(\alpha \omega(n+1)) e(-\alpha \omega(n))

for various frequencies {\alpha}, use the estimates of Pilatte to handle the minor arc {\alpha}, and convert the major arc contribution back into physical space (in which {\omega(n+1)} and {\omega(n)} are now permitted to differ by a large amount) and use more traditional sieve theoretic methods to estimate the result.

Growth rates of sequences governed by the squarefree properties of its translates

1 December, 2025 in math.NT, paper | Tags: , | by | 3 comments

Wouter van Doorn and I have uploaded to the arXiv our paper “Growth rates of sequences governed by the squarefree properties of its translates“. In this paper we answer a number of questions of Erdős} (Problem 1102 and Problem 1103 on the Erdős problem web site) regarding how quickly a sequence {A = \{a_1 < a_2 < \dots\}} of increasing natural numbers can grow if one constrains its translates {n+A} to interact with the set {\mathcal{SF} = \{1,2,3,5,6,7,10,\dots\}} of squarefree numbers in various ways. For instance, Erdős defined a sequence {A} to have “Property {P}” if each of its translates {n+A} only intersected {\mathcal{SF}} in finitely many points. Erdős believed this to be quite a restrictive condition on {A}, writing “Probably a sequence having property P must increase fairly fast, but I have no results in this direction.”. Perhaps surprisingly, we show that while these sequences must be of density zero, they can in fact grow arbitrary slowly in the sense that one can have {a_j \leq j f(j)} for all sufficiently large {j} and any specified function {f(j)} that tends to infinity as {j \rightarrow \infty}. For instance, one can find a sequence that grows like {O(j \log\log\log j)}. The density zero claim can be proven by a version of the Maier matrix method, and also follows from known moment estimates on the gaps between squarefree numbers; the latter claim is proven by a greedy construction in which one slowly imposes more and more congruence conditions on the sequence to ensure that various translates of the sequence stop being squarefree after a certain point.

Erdős also defined a somewhat complementary property {Q}, which asserts that for infinitely many {n}, all the elements {n+a} of {A} for {a \leq n} are square-free. Since the squarefree numbers themselves have density {6/\pi^2}, it is easy to see that a sequence with property {Q} must have (upper) density at most {6/\pi^2} (because it must be “admissible” in the sense of avoiding one residue class modulo {p^2} for each {p}). Erdős observed that any sufficiently rapidly growing (admissible) sequence would obey property {Q} but beyond that, Erdős writes “I have no precise information about the rate of increase a sequence having property Q must have.”. Our results in this direction may also be surprising: we show that there exist sequences with property {Q} with density exactly {6/\pi^2} (or equivalently, {a_j \sim \frac{\pi^2}{6} j}). This requires a recursive sieve construction, in which one starts with an initial scale {n} and finds a much larger number {n'} such that {n'+a} is squarefree for most of the squarefree numbers {a \leq n'} (and all of the squarefree numbers {a \leq n}). We quantify Erdős’s remark by showing that an (admissible) sequence will necessarily obey property {Q} once it grows significantly faster than {\exp( C j \log j)}, but need not obey this property if it only grows like {\exp(O(j^{1/2} \log^{1/2} j))}. This is achieved through further application of sieve methods.

A third property studied by Erdős is the property of having squarefree sums, so that {a_i + a_j} is squarefree for all {i,j}. Erdős writes, “In fact one can find a sequence which grows exponentially. Must such a sequence really increase so fast? I do not expect that there is such a sequence of polynomial growth.” Here our results are relatively weak: we can construct such a sequence that grows like {\exp(O(j \log j))}, but do not know if this is optimal; the best lower bound we can produce on the growth, coming from the large sieve, is {\gg j^{4/3}}. (Somewhat annoyingly, the precise form of the large sieve inequality we needed was not in the literature, so we have an appendix supplying it.) We suspect that further progress on this problem requires advances in inverse sieve theory.

A weaker property than squarefree sums (but stronger than property {Q}), referred to by Erdős as property {\overline{P}}, asserts that there are infinitely many {n} such that all elements of {n+A} (not just the small ones) are square-free. Here, the situation is close to, but not quite the same, as that for property {Q}; we show that sequences with property {\overline{P}} must have upper density strictly less than {6/\pi^2}, but can have density arbitrarily close to this value.

Finally, we looked at a further question of Erdős on the size of an admissible set {A}. Because the squarefree numbers are admissible, the maximum number {A(x)} of elements of an admissible set {A} up to {x} (OEIS A083544) is at least the number {|{\mathcal SF} \cap [x]|} of squarefree elements up to {x} (A013928). It was observed by Ruzsa that the former sequence is greater than the latter for infinitely many {x}. Erdős asked, “Probably this holds for all large x. It would be of some interest to estimate A(x) as accurately as possible.”

We are able to show

\displaystyle \frac{\sqrt{x}}{\log x} \ll A(x) - \frac{6}{\pi^2} x \ll x^{4/5},

with the upper bound coming from the large sieve and the lower bound from a probabilistic construction. In contrast, a classical result of Walfisz shows that

\displaystyle |{\mathcal SF} \cap [x]| - \frac{6}{\pi^2} x \ll x^{1/2} \exp(-c \log^{3/5} x / (\log\log x)^{1/5}).

Together, this implies that Erdős’s conjecture holds {A(x) > |{\mathcal SF} \cap [x]|} for all sufficiently large {x}. Numerically, it appears that in fact this conjecture holds for all {n>17}:

BERJAYA

However, we do not currently have enough numerical data for the sequence {A(x)} to completely confirm the conjecture in all cases. This could potentially be a crowdsourced project (similar to the Erdős-Guy-Selfridge project reported on in this previous blog post).

Archives