Korean, Edit

Erdős Reciprocal-Sum Conjecture

Recommended post: 【Modern Mathematics】 Table of Contents of Modern Mathematics

1. Overview

2. Proof

3. Applications

1. Overview

⑴ Theorem: If the sum of reciprocals of a set $A$ of natural numbers diverges to infinity, then the set necessarily contains arithmetic progressions of arbitrarily large finite length.

① Example 1. Since the set of all natural numbers satisfies $1 + \frac12 + \frac13 + \cdots = \infty$, it contains arithmetic progressions of arbitrary length, such as 10, 100, and 1000.

② Example 2. Since the set of perfect squares satisfies $1 + \frac14 + \frac19 + \cdots < \infty$, it does not satisfy the hypothesis of this conjecture.

○ In fact, Fermat proved that there is no arithmetic progression consisting of four distinct perfect squares (ref).

③ The statement asserts the existence of arithmetic progressions of every finite length, not the existence of a single infinite arithmetic progression.

④ The proof below was proposed by OpenAI on September 23, 2026, but has not yet been verified.

⑵ Incidentally, Paul Erdős is the central figure in the book The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth.

2. Proof

⑴ Step 1. Assume that there are too few arithmetic progressions → The set is not distributed randomly.

⑵ Step 2. Higher-order Fourier analysis: Detect hidden regularity.

① Arithmetic progression of length 3: $n, n+d, n+2d$

○ Classical Fourier analysis: This periodic structure can be represented by the complex number $\exp(2\pi i\theta n)$, which represents a rotation through an angle of $2\pi\theta n$.

② Arithmetic progression of length 4: $n, n+d, n+2d, n+3d$

○ For the quadratic function $q(n)=\theta n^2$, the identity $q(n+3d)-3q(n+2d)+3q(n+d)-q(n)=0$ always holds.

○ Such quadratic regularity is difficult to detect using classical Fourier analysis.

○ Reason: Classical Fourier analysis deals with constant rotation rates, whereas $q(n)$ does not have a constant rotation rate, as shown by $q(n+d)-q(n)=\theta(2nd+d^2)$.

○ Classical Fourier analysis and this quadratic regularity can be described using the same language of finite differences, with only the polynomial degree being different.

○ Finite differences of a linear function: $1\xrightarrow{+2}3\xrightarrow{+2}5\xrightarrow{+2}7$

○ Finite differences of a quadratic function: $0\xrightarrow{+1}1\xrightarrow{+3}4\xrightarrow{+5}9\xrightarrow{+7}16$

○ The finite-difference structure of a quadratic function also explains why identities such as $(n+h+k)^2-(n+h)^2-(n+k)^2+n^2=2hk$ hold.

○ Therefore, the third finite difference of a quadratic function is identically zero: $\Delta_\ell\Delta_k\Delta_h(\theta n^2)=0$.

○ Because the third finite difference of $q(n)=\theta n^2$ is zero, the Gowers $U^3$ norm of the complex-valued function $f(n)=\exp(2\pi iq(n))$ is exactly 1.

○ Inverse theorem for Gowers norms

○ Theorem: A quadratic phase produces a large $U^3$ norm, and conversely, the inverse theorem concerns whether a large $U^3$ norm necessarily implies the presence of quadratic structure.

○ On a suitable finite cyclic group, correlations associated with arithmetic progressions of length 4 are controlled by the $U^3$ norm: This follows from repeated applications of the Cauchy–Schwarz inequality.

③ Generalization: The existence of arithmetic progressions is closely connected to whether certain forms of regularity are satisfied.

Table 1. Arithmetic Progressions and Gowers Norms

④ Nilsequence

○ $\exp(\alpha n\lfloor\beta n\rfloor)$ (where $\lfloor x\rfloor$ denotes the floor function) exhibits quadratic variation similar to $n^2$, but also displays discontinuous changes because of the floor function → Such expressions are called generalized quadratic phases (bracket quadratic phases) → To establish the inverse theorem for Gowers norms in general, a broader class of functions than quadratic polynomial phases is required.

○ Nilsequence: A sequence obtained by observing regular motion on a space generated by a nilpotent group.

○ It captures not only linear, quadratic, and higher-degree polynomial phases, but also more complicated forms of regularity that cannot be expressed as ordinary polynomial phases.

○ The inverse theorem for Gowers norms guarantees that a function with a large $U^k$ norm has a significant correlation with a suitable $(k-1)$-step nilsequence.

⑶ Step 3. Higher-order Fourier analysis → Density increment

① Suppose that a set $A$ has density $\alpha$ in a finite space $X$: $f=\mathbf{1}$_𝛢, $\mathbb{E}_{n\in X}f(n)=\alpha$.

○ Density: The proportion of elements belonging to $A$ among all natural numbers under consideration.

○ The set $A$ is an arbitrary set assumed to contain no arithmetic progression of length $k$, and the divergence condition on the reciprocal sum is used in the final step.

② Suppose that higher-order Fourier analysis shows that $f-\alpha$ has a positive correlation with some real-valued nilsequence $F(n)$ satisfying $\left|F(n)\right|\leq 1$.

○ $\mathbb{E}_{n\in X}[(f(n)-\alpha)F(n)]\geq\delta>0$

○ This means that the elements of $A$ are distributed nonuniformly according to how the values of $F$ vary.

③ If $F$ is a function on a nilmanifold $G/\Gamma$, then the space can be partitioned into sufficiently small regions $(U_1,\ldots,U_m)$.

○ By making the partition sufficiently fine, $F(n)$ becomes approximately constant on each $C_j={n:g(n)\Gamma\in U_j}$.

④ General principle of density increments: Since the unweighted sum is zero while the weighted sum is positive, a combinatorial argument guarantees the existence of a region where the density increases in accordance with variations in $F$.

⑤ Conclusion

○ However, this principle is not specific to higher-order Fourier analysis; it is a general principle that follows from correlations.

○ Ultimately, the question is whether one can find a region exhibiting a substantial density increment. To apply higher-order Fourier analysis again, one needs a method for adding new regularity while preserving the regularity already discovered.

⑷ Step 4. Density increment → Triangular polynomial cell → Next density increment

① 4-1. Triangular polynomial cell: A structure that records polynomial conditions hierarchically.

○ Example 1. A region where the quadratic phase $\exp(2\pi i\theta n^2)$ is nearly constant.

○ $C={n:\left|\theta n^2-t\right|\leq w}$

○ This can be represented as a region where there exists a suitable integer $b_2$ satisfying $\left|b_2-(\theta n^2-t)\right|\leq w$.

○ Example 2. For more general nilsequences, lower-degree integer coordinates influence higher-degree polynomials, leading to conditions of the following form.

○ Suppose that the following condition is required for a density increment: $\left|\theta n-b_1\right|\leq w_1$, $b_1\in\mathbb{Z}$.

○ For the next density increment, suppose that the following condition must be satisfied: $\left|\beta n^2+\lambda nb_1-b_2\right|\leq w_2$, $b_2\in\mathbb{Z}$, where $b_1$ is the variable introduced by the first condition.

○ Repeatedly substituting approximate values in this way destroys the previously established regularity: In particular, as the term $nb_1$ illustrates, the approximation error can become very large when $n$ is large.

○ By preserving $b_1$ exactly rather than replacing it with its approximation $\theta n$, errors can be controlled throughout the iterative process.

② 4-2. Representation of a density increment: For a weight function $B(n)$,

○ $\displaystyle \rho_B=\frac{\sum_n\mathbf{1}_A(n)B(n)}{\sum_n B(n)}>(1+\eta)a$

○ In other words, assigning weights to numbers satisfying specific polynomial regularity conditions produces a density greater than the original reference density $a$.

○ The actual paper formalizes this through a density certificate using two weights, $B_-$ and $B_+$, to control errors.

③ 4-3. Next density increment

○ By choosing a suitable affine map $\psi(t)=x+Vt$, part of the complicated region can be examined inside a new integer box.

○ Since affine transformations preserve the structure of arithmetic progressions, higher-order Fourier analysis can be applied again inside this box to find another density increment.

○ The newly discovered conditions are then translated back into the original variables and added to the existing triangular polynomial cell, allowing the same procedure to be repeated.

④ Key technical improvements

○ Previous difficulty: As the iteration proceeds, the conditions become increasingly complicated and the tolerance $w$ becomes smaller, potentially making the region available for analysis excessively small.

○ The paper measures the precision at each level by $Q_h=\log(2/w_h)$ and controls the additional precision cost when introducing new conditions.

○ In particular, the key is to ensure that the additional precision cost at a given level does not depend on that level’s own current precision.

○ As a result, the total cost can be controlled polynomially in the number of iterations, making it possible to repeat density increments when the initial interval is sufficiently large.

⑤ Conclusion: Triangular polynomial cells make repeated density increments possible while preserving the regularity discovered through higher-order Fourier analysis.

⑸ Step 5. Deriving a contradiction

① Starting from an initial density $a$ (e.g., 20%), sufficient space can be maintained for approximately $O(\log(1/\alpha))$ iterations of the form $a\to(1+\eta)a\to(1+\eta)^2a\to\cdots$.

② Eventually, this process could produce a region whose density exceeds 1, resulting in a contradiction.

③ Therefore, for a set of density $\alpha$ that avoids arithmetic progressions of length $k$ to exist, the size $N$ of the initial interval must satisfy a certain restriction.

⑹ Step 6. Proof of the Erdős Reciprocal-Sum Conjecture

① Result of the preceding proof: An upper bound is obtained on how large a set without arithmetic progressions of length $k$ can be.

○ $r_k(N)$: The maximum number of elements that can be selected from the natural numbers between 1 and $N$ without forming an arithmetic progression of length $k$.

○ By repeatedly applying the density-increment method, the following upper bound is obtained (where $C_k,c_k,\varepsilon_k>0$): $r_k(N)\leq C_kN\exp[-c_k(\log N)^{\varepsilon_k}]$.

○ This means that sets avoiding arithmetic progressions must become increasingly sparse as $N$ grows.

② Connection to reciprocal sums: Divide the natural numbers into intervals whose sizes double successively: $[1,2),[2,4),[4,8),[8,16),\ldots$.

○ Condition 1. A general interval $D_m=[2^m,2^{m+1})$ contains $2^m$ natural numbers.

○ Condition 2. If $A$ contains no arithmetic progression of length $k$, the number of elements of $A$ in this interval cannot exceed $r_k(2^m)$.

○ Condition 3. Since every element $a$ in the interval satisfies $a\geq 2^m$, its reciprocal satisfies $\frac1a\leq\frac1{2^m}$.

○ The reciprocal sum over all intervals is therefore bounded as follows:

○ $\displaystyle \sum_{a\in A}\frac1a\leq\sum_{m=0}^{\infty}\frac{\left|A\cap D_m\right|}{2^m}\leq\sum_{m=0}^{\infty}\frac{r_k(2^{m+1})}{2^m}\leq 2C_k\sum_{m=0}^{\infty}\exp[-c_k((m+1)\log 2)^{\varepsilon_k}]$

○ The series on the right converges because $\varepsilon_k>0$ → Thus, the reciprocal sum of any set containing no arithmetic progression of length $k$ must converge.

○ Since $k$ can be chosen arbitrarily, every set whose reciprocal sum diverges must contain arithmetic progressions of every finite length.

③ Difference between the set of all natural numbers and the set of perfect squares

○ Set of all natural numbers: The interval $[2^m,2^{m+1})$ contains $2^m$ elements, and the reciprocal of each element is approximately $2^{-m}$. Therefore, the reciprocal sum over each interval remains of constant order → Summing over all intervals gives a divergent series.

○ Set of perfect squares: The same interval contains only approximately $2^{m/2}$ perfect squares, so the reciprocal sum over each interval decreases on the order of $2^{-m/2}$ → The sum converges even after adding contributions from all intervals.

○ The difference arises from how many elements remain in each interval as the numbers become larger.

④ Conclusion: The key point is that divergence of the reciprocal sum is a stronger condition than merely having infinitely many elements.

3. Applications

⑴ Van der Waerden’s theorem: If the natural numbers are colored using finitely many colors, there exists a monochromatic arithmetic progression of any prescribed finite length.

⑵ Roth’s theorem → Szemerédi’s theorem: A set of positive density contains arbitrarily long arithmetic progressions.

① Positive density is a stronger condition than the hypothesis of the reciprocal-sum conjecture.

⑶ Green–Tao theorem: Arithmetic progressions of prime numbers.

① Euler had already proved that $\displaystyle\sum_{\substack{p\text{ prime}}}\frac1p=\infty$: This fact can also be easily derived from the prime number theorem.

② The Green–Tao theorem does not rely on the Erdős reciprocal-sum conjecture, but it can be easily deduced if the preceding reciprocal-sum conjecture is available.

Entered: 2026.10.25 13:26