On the Green-Tao theorem for sparse sets

This paper establishes a quantitative form of the Green-Tao theorem for sparse sets by proving that any subset of primes with relative density $\delta$ lacking nontrivial arithmetic progressions of length $k \geq 4$ must satisfy $\delta \ll \exp(-(\log \log \log N)^{c_k})$, an improvement achieved through a new quasipolynomial inverse theorem and a dense model theorem.

The Gist

Imagine you are a detective trying to find a very specific pattern in a massive, chaotic crowd. The pattern you are looking for is an arithmetic progression: a sequence of numbers where the gap between each step is the same (like 3, 7, 11, 15).

For a long time, mathematicians knew that if you look at all the whole numbers (1, 2, 3...), you will eventually find these patterns, no matter how long you make the sequence. This is a famous result called Szemerédi's Theorem.

Then, in 2004, Green and Tao made a huge discovery: The prime numbers (2, 3, 5, 7, 11...) also contain these patterns, no matter how long you want them to be. This was a landmark result.

However, there was a missing piece: How big does the crowd need to be before you are guaranteed to find the pattern?

The Problem: The "Sparse" Crowd

The primes are a "sparse" set. If you look at the first 1,000 numbers, half are even, but only 168 are prime. As numbers get bigger, primes become even rarer.

Previous mathematicians (like Rimanić and Wolf) tried to answer the question: "If I pick a random group of primes, how many do I need to pick to guarantee I find a pattern of length 4 or more?"

Their answer was: "You need to pick a lot, but the number of primes you need to pick is still quite large." Their formula involved "logarithms of logarithms of logarithms" (think of it as a very slow, weak signal).

The New Discovery: A Sharper Lens

The authors of this paper, Joni Teräväinen and Mengdi Wang, have built a sharper lens. They proved that you actually need far fewer primes to guarantee finding the pattern.

Their new formula shows that if you pick a group of primes that is even slightly larger than a tiny fraction (specifically, a fraction that shrinks very slowly), you are guaranteed to find the pattern. This is a massive improvement over the previous "weak signal" estimates.

How Did They Do It? (The Analogy)

To understand their method, imagine you are trying to find a hidden treasure in a vast, foggy forest (the set of prime numbers).

1. The Fog (The Problem of Sparsity)
The primes are scattered so thinly that standard mathematical tools (which work great in dense forests) get lost in the fog. You can't just look at the primes directly; the signal is too weak.

2. The "Majorant" (The Flashlight)
Green and Tao's original method involved using a "majorant." Imagine a flashlight that shines on the whole forest, but it's very bright and covers everything, including the empty spaces between trees. It's a bit messy, but it helps you see the general area.

3. The "Dense Model" (The Map)
The authors' breakthrough is a new way to turn that messy, bright flashlight into a clear, detailed map.

• Old Way: They had to assume the flashlight was perfect, which required very strict conditions that were hard to meet.
• New Way: They developed a technique (called a "Dense Model Theorem") that allows them to take the messy, sparse data (the primes) and approximate it with a "dense" model (a smooth, easy-to-analyze function).

Think of it like this:

• The Primes: A jagged, rocky mountain range.
• The Dense Model: A smooth, clay sculpture of that mountain.
• The Innovation: They proved that even if the mountain is jagged and sparse, you can mold a smooth clay version of it that is so accurate that any pattern you find in the clay will definitely exist in the real mountain.

4. The "Quasipolynomial" Breakthrough
The key to their success was a new mathematical tool (an "inverse theorem") that works much faster than before.

• Previous tools were like a snail; they took a long time to process the data, leading to weak results.
• The new tool is like a high-speed train. It processes the "jaggedness" of the primes much more efficiently. This speed allows them to prove that the "clay map" is accurate enough to guarantee the pattern exists with much less data than before.

Why Does This Matter?

In the world of math, "quantitative bounds" are like the difference between saying "It's possible to find a needle in a haystack" and "You will find the needle if you search the first 100 grains of straw."

Teräväinen and Wang have shown that you don't need to search the whole haystack. You only need to search a tiny, specific corner.

In summary:
They took a famous theorem about primes, realized the old math used to prove it was too "blurry," and invented a new, high-definition camera. This camera lets us see that patterns in primes appear much more frequently and predictably than we ever thought possible. It's a significant step forward in understanding the hidden order within the seemingly random world of prime numbers.

Technical Summary

Here is a detailed technical summary of the paper "On the Green–Tao Theorem for Sparse Sets" by Joni Teräväinen and Mengdi Wang.

1. Problem Statement and Context

The Core Problem:
The paper addresses the quantitative bounds of the Green–Tao theorem in the context of sparse sets, specifically subsets of the prime numbers. While the original Green–Tao theorem (2004) proved that the primes contain arbitrarily long arithmetic progressions (APs), it was non-quantitative. Subsequent work sought to determine how dense a subset of primes must be to guarantee the existence of a $k$-term AP.

Previous State of the Art:

• Integers ($[N]$): For $k=3$, the best bounds (Kelley–Meka, Bloom–Sisask) are of the form $\exp(-c(\log N)^{1/9})$. For $k \ge 4$, the bounds are significantly weaker, typically involving iterated logarithms (e.g., $(\log N)^{-c}$ for $k=4$ and $\exp(-(\log \log N)^c)$ for $k \ge 5$).
• Primes: Previous work by Rimanić and Wolf established that if a subset of primes up to $N$ lacks $k$-APs, its relative density $\delta$ satisfies bounds like $(\log \log \log N)^{-c}$ (for $k=4$) and $(\log \log \log \log N)^{-c}$ (for $k \ge 5$). These are "triple-logarithmic" or "quadruple-logarithmic" decays, which are very weak compared to the integer case.

The Gap:
The authors aim to improve these quantitative bounds for subsets of primes, specifically moving from iterated logarithmic decay to exponential decay in terms of iterated logarithms (e.g., $\exp(-(\log \log \log N)^c)$). This requires overcoming the limitations of Fourier-analytic methods which fail for $k \ge 4$ and dealing with the unbounded nature of the von Mangoldt function used to model primes.

---

2. Methodology and Framework

The proof relies on the Transference Principle, a framework introduced by Green and Tao that allows one to transfer results from dense sets (like $[N]$) to sparse sets (like the primes) by embedding the sparse set into a "pseudorandom" majorant.

The authors' approach involves three main technical pillars:

A. The Transference Principle with Unbounded Functions

The standard transference principle requires a function $f$ (modeling the subset of primes) to be bounded by a pseudorandom majorant $\nu$. The challenge here is that $f$ (derived from the von Mangoldt function $\Lambda$) is unbounded ($\|\Lambda\|_\infty \approx \log N$).

• Strategy: The authors use a "dense model" theorem to approximate the unbounded function $f$ with a bounded function $g$ in the Gowers uniformity norm ($U^k$).
• Key Innovation: They improve the dependency of the dense model theorem from exponential to quasipolynomial. Previous works (e.g., Green–Tao, Conlon–Fox–Zhang) had exponential dependencies on the error parameter $\epsilon$, which resulted in weak bounds. By achieving quasipolynomial bounds, they significantly tighten the final density estimates.

B. Quasipolynomial Inverse Theorem for Unbounded Functions

A critical component is the Inverse Theorem for Gowers Norms, which states that if a function has a large $U^k$ norm, it must correlate with a structured object (a nilsequence).

• Leng–Sah–Sawhney (2023): Recently proved a quasipolynomial inverse theorem for bounded ($1$-bounded) functions.
• Authors' Contribution: They extend this to unbounded functions dominated by a pseudorandom majorant. They prove a "Transferred Inverse Theorem" (Theorem 2.5) showing that if $|f| \le \nu$ and $\|f\|_{U^k} \ge \epsilon$, then $f$ correlates with a nilsequence with quasipolynomial complexity bounds. This is achieved by combining the inverse theorem for bounded functions with a "densification" argument and an induction on the structure of the correlation.

C. The Dense Model Theorem with Quasipolynomial Dependencies

The authors construct a dense model $g$ (a bounded function) that approximates $f$ in the $U^k$ norm.

• Energy Increment Argument: They use an iterative refinement of partitions (factors) based on nilsequences.
• Handling Unboundedness: Unlike the bounded case where the $L^2$ norm is controlled by 1, the unbounded $f$ has a large $L^2$ norm ($\approx \log N$). The authors overcome this by showing that for the specific partitions generated by the iteration, the conditional expectation $\Pi_B f$ remains $L^2$-bounded on "most" atoms, provided the iteration does not run too long.
• Result: They establish that $f$ can be approximated by a bounded function $g$ such that $\|f - g\|_{U^k} \le \exp(-(\log(1/\epsilon))^\gamma)$, where the exponent $\gamma$ is quasipolynomial rather than exponential.

D. Correlation with Nilsequences (Type I/II Estimates)

To apply the dense model theorem to the primes, one must verify that the majorant (related to the von Mangoldt function) does not correlate too strongly with nilsequences unless the nilsequence is trivial.

• Decomposition: They use Vaughan's identity to decompose the von Mangoldt function into Type I and Type II sums.
• New Estimates: They prove new Type I and Type II estimates for nilsequences along sparse arithmetic progressions (where the common difference is large). This is necessary because the standard estimates in the literature assume the common difference is small relative to the complexity of the nilsequence.
• Outcome: They show that the correlation between the majorant and any non-trivial nilsequence is negligible, satisfying the conditions for the dense model theorem.

---

3. Key Contributions

1. Quantitative Improvement: The paper establishes a quasipolynomial inverse theorem and dense model theorem for unbounded functions. This is a significant technical breakthrough, improving upon previous exponential dependencies.
2. New Density Bounds: They prove that if a subset $A$ of primes up to $N$ contains no non-trivial $k$-term APs, its relative density $\delta$ satisfies:
   • For $k=4$: $\delta \ll (\log \log N)^{-c_4}$
   • For $k \ge 5$: $\delta \ll \exp(-(\log \log \log N)^{c_k})$
     This represents a massive improvement over the previous $(\log \log \log \log N)^{-c}$ bounds.
3. Handling Sparse Progressions: The development of Type I/II estimates for nilsequences on sparse progressions (Appendix A) is a novel tool that may be useful in other areas of analytic number theory involving sparse sets.
4. Refinement of Transference: The paper refines the transference principle to handle the specific technical hurdles of the von Mangoldt function (unboundedness and $W$-tricking) with precise quantitative control.

---

4. Main Results

Theorem 1.1 (Density Bound):
Let $k \ge 4$ and $N \ge 100$. Let $A \subseteq [N] \cap \mathbb{P}$ be a subset of primes. If $A$ contains no non-trivial $k$-term arithmetic progression, then for some constant $c_k > 0$:
$$\frac{|A|}{|[N] \cap \mathbb{P}|} \ll \begin{cases} (\log \log N)^{-c_4} & \text{if } k = 4 \\ \exp(-(\log \log \log N)^{c_k}) & \text{if } k \ge 5 \end{cases}$$

Theorem 2.5 (Transferred Inverse Theorem):
A quasipolynomial inverse theorem for functions $f$ bounded by a pseudorandom majorant $\nu$. If $\|f\|_{U^k} \ge \epsilon$, then $f$ correlates with a nilsequence of degree $k-1$ with complexity and dimension bounded by $\exp((\log(1/\epsilon))^{C_k})$.

Proposition 3.12 (Dense Model):
A dense model theorem stating that under specific pseudorandomness and correlation conditions, a function $f$ can be approximated by a bounded function $g$ with an error in the $U^k$ norm of $\exp(-(\log(1/\epsilon))^{\gamma_k})$.

---

5. Significance

• Bridging the Gap: The results bring the quantitative understanding of arithmetic progressions in the primes much closer to the state of the art for integers. While the integer case for $k \ge 4$ still has room for improvement (moving from iterated logs to exponential), the prime case has now been pushed to the same "iterated logarithmic" frontier.
• Methodological Advancement: The shift from exponential to quasipolynomial dependencies in the inverse and dense model theorems is a major theoretical advance. It suggests that the "loss" incurred by transferring from dense to sparse sets is much smaller than previously thought.
• Independent Interest: The tools developed, particularly the Type I/II estimates for nilsequences on sparse progressions and the handling of unbounded functions in the inverse theorem, are likely to be applicable to other problems in additive combinatorics and number theory, such as polynomial progressions in primes or other sparse sets.
• Limitations: The authors note that their method currently suffers a "logarithmic loss" compared to the dense setting because the pseudorandom majorant (a $W$-tricked Selberg sieve) is only Gowers-uniform up to a certain accuracy determined by the parameter $W$. Overcoming this to reach the full strength of the integer bounds remains an open challenge.

In summary, this paper represents a significant leap forward in the quantitative theory of arithmetic progressions in primes, utilizing sophisticated refinements of the Green–Tao transference principle to achieve the best known bounds to date.