# Erdős–Turán conjecture on additive bases

The Erdős–Turán conjecture on additive bases is an open problem in additive number theory stating that if a set of nonnegative integers represents every sufficiently large integer as a sum of two of its elements, then the number of such representations cannot be bounded. [Paul Erdős](https://www.edgepedia.org/paul-erdos) and [Pál Turán](https://www.edgepedia.org/pal-turan) posed it in 1941, in a paper on a problem of Sidon, and it has resisted proof since.<sup>[1](https://www.math.tau.ac.il/~samotij/papers/Sidon.pdf)</sup><sup> • </sup><sup>[2](https://users.renyi.hu/~sos/1997_On_additive_representation_functions.pdf)</sup>

| Key fact | Detail |
|---|---|
| Statement | If \( A \subseteq \mathbb{N} \) is an asymptotic basis of order 2, then \( \limsup_{n\to\infty} r_2(A,n) = +\infty \); the representation function of any basis of order 2 is unbounded<sup>[2](https://users.renyi.hu/~sos/1997_On_additive_representation_functions.pdf)</sup> |
| Origin | Erdős and Turán, "On a problem of Sidon in additive number theory, and on some related problems," *J. London Math. Soc.* **16** (1941), 212–215<sup>[1](https://www.math.tau.ac.il/~samotij/papers/Sidon.pdf)</sup> |
| Best known thin bases | Erdős (1956) proved by probabilistic methods that bases exist with \( r_A(n) = \Theta(\log n) \), answering a question of Sidon<sup>[3](https://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-or)</sup> |
| Higher orders | Erdős and Tetali (1990) constructed \( A \subseteq \mathbb{Z}_{\ge 0} \) with \( r_{A,h}(n) \asymp \log n \); Vu (2000) handled general coefficients \( b_1, \dots, b_h \)<sup>[4](https://doi.org/10.1002/rsa.70088)</sup> |
| Where it fails | Over \( \mathbb{Z} \) the analogous statement is false: bases with bounded, even unique, representations exist, so any proof must use the one-sided structure of \( \mathbb{N} \)<sup>[5](https://api.scinet.pub/p/c24c8b25-cb70-48da-a5b8-87a128d5992f)</sup> |
| Finite reformulation | Nathanson (2003), using König's lemma, showed a general additive problem containing the conjecture is equivalent to a problem about finite sets of nonnegative integers<sup>[6](https://arxiv.org/abs/math/0302155)</sup> |
| Status | Open; listed as problem 28 (and problem 3) in Thomas Bloom's Erdős problems collection<sup>[7](https://mathworld.wolfram.com/Erdos-TuranConjecture.html)</sup> |

## Definitions and statement

Given a set \( A \) of nonnegative integers and a positive integer \( h \), define \( r_{A}(n,h) \) as the count of ways to write \( n \) as \( n = a_1 + a_2 + \cdots + a_h \), where the \( a_i \) are elements of \( A \) arranged so that \( a_1 \le a_2 \le \cdots \le a_h \). The set \( A \) is a basis of order \( h \) if \( r_A(n,h) \ge 1 \) for every nonnegative integer \( n \), and an asymptotic basis of order 2 if \( r_2(A,n) > 0 \) for all sufficiently large \( n \).<sup>[6](https://arxiv.org/abs/math/0302155)</sup><sup> • </sup><sup>[2](https://users.renyi.hu/~sos/1997_On_additive_representation_functions.pdf)</sup>

The 1941 conjecture reads: if \( A \subseteq \mathbb{N} \) and \( r_2(A,n) > 0 \) for \( n > n_0 \), then \( r_2(A,n) \) cannot be bounded; that is, \( \limsup_{n\to\infty} r_2(A,n) = +\infty \). Sárközy and Sós, surveying the area, described it as harmlessly looking but extremely difficult, noting that no serious advance had been made between 1941 and their survey.<sup>[2](https://users.renyi.hu/~sos/1997_On_additive_representation_functions.pdf)</sup> In the language of convolution, writing \( 1_A \ast 1_A(n) \) for the two-term representation count, the conjecture asks whether \( 1_A \ast 1_A(n) \ll 1 \) is possible for a basis; Erdős and Turán conjectured that it is not.<sup>[8](https://www.erdosproblems.com/forum/thread/blog%3A5?embed=1)</sup>

## Origin in Sidon's problem

The conjecture appeared in Erdős and Turán's 1941 paper on a problem of Sidon in additive number theory, published in the *Journal of the London Mathematical Society*.<sup>[1](https://www.math.tau.ac.il/~samotij/papers/Sidon.pdf)</sup> Sidon had asked how thin a basis of order 2 can be, and the conjecture records the expectation that the thinnest possible bases still have representation functions growing without bound. Erdős returned to the problem repeatedly; in a 1989 problem paper he called it an old and very interesting conjecture of Turán and himself, for which he often offered 500 dollars.<sup>[9](https://users.renyi.hu/~p_erdos/1989-35.pdf)</sup>

## Thin bases and the logarithmic barrier

**Erdős's 1956 construction.** In 1956 Erdős proved, by a random construction, that there exists an efficient basis in which \( 1_A \ast 1_A(n) \ll \log n \); in modern notation, a number \( n \) is included in \( A \) with probability proportional to \( C(\log n)^{1/2} n^{-1/2} \).<sup>[8](https://www.erdosproblems.com/forum/thread/blog%3A5?embed=1)</sup><sup> • </sup><sup>[10](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/an-explicit-economical-additive-basis/F749896F8A541F7CF51238D198C9B064)</sup> This answered Sidon's old question by producing bases with \( r_A(n) = \Theta(\log n) \), and it is an open conjecture, attributed to Erdős and Turán, whether every basis of order 2 satisfies \( \limsup_{n\to\infty} r_A(n)/\log n > 0 \); if true, Erdős's thin basis would be as thin as possible up to constants in this sense.<sup>[3](https://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-or)</sup><sup> • </sup><sup>[10](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/an-explicit-economical-additive-basis/F749896F8A541F7CF51238D198C9B064)</sup>

The gap between \( \Theta(\log n) \) and boundedness is exactly what the conjecture addresses. It is a major open problem whether the factor of \( \log N \) can be replaced by an absolute constant; Erdős and Turán famously conjectured that this is impossible.<sup>[10](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/an-explicit-economical-additive-basis/F749896F8A541F7CF51238D198C9B064)</sup> Erdős also asked several times for an *explicit* set answering Sidon's question, offering 100 dollars for a solution; Kolountzakis later derandomized a variation of Erdős's proof so that the elements of \( A \cap \{0, \ldots, N\} \) can be generated deterministically in time \( N^{O(1)} \), and an explicit economical construction has since been given unconditionally.<sup>[10](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/an-explicit-economical-additive-basis/F749896F8A541F7CF51238D198C9B064)</sup>

For higher orders the analogous thin-basis results are known: Erdős and Tetali showed in 1990 that there exists \( A \subseteq \mathbb{Z}_{\ge 0} \) with \( r_{A,h}(n) \asymp \log n \), and Vu extended this in 2000 to general integer coefficients \( b_1, \dots, b_h \).<sup>[4](https://doi.org/10.1002/rsa.70088)</sup>

## Strengthened forms and neighboring results

Erdős and Turán also formulated a stronger conjecture: if \( a_1 < a_2 < \cdots \) is an infinite sequence of positive integers with \( a_k < ck^2 \) for some \( c > 0 \) and all \( k \), then \( \limsup r_2(A,n) = +\infty \). Erdős and Fuchs remarked that under the same assumptions the mean square of the representation function can be bounded, and Ruzsa proved the analogous result: there is an infinite set \( A \subseteq \mathbb{N} \) with \( r_2(A,n) > 0 \) for all \( n > n_0 \) whose mean square remains bounded.<sup>[2](https://users.renyi.hu/~sos/1997_On_additive_representation_functions.pdf)</sup>

Sárközy and Sós studied what boundedness would force. If the conjecture is true and \( r_2(A,n) \) is bounded, then \( r_2(A,n) \) must assume the value 0 infinitely often. Erdős and Freud conjectured that the value 1 must also occur infinitely often, and guessed that uniquely represented integers outnumber multiply represented ones; Sárközy and Sós showed this latter guess is false for sets in \( B_2[g] \) with \( g \ge 3 \), constructing sets for which the two counts have comparable sizes.<sup>[2](https://users.renyi.hu/~sos/1997_On_additive_representation_functions.pdf)</sup>

## Equivalences and finite variants

**Reduction to finite problems.** Melvyn B. Nathanson, a mathematician at Lehman College known for his work and textbooks on additive number theory, introduced in 2003 a class of generalized additive bases and a general additive problem whose special case is the Erdős–Turán conjecture; using König's lemma on infinite paths in graphs, he proved this general problem equivalent to a related problem about finite sets of nonnegative integers.<sup>[6](https://arxiv.org/abs/math/0302155)</sup> Earlier, Dowd had proved that a set \( A \) with \( r_A(n,2) \in [1,c] \) for all \( n \) exists if and only if, for every \( N \), there is a finite set \( A_N \) with \( \max(A_N) \ge N \) and \( r_A(n,2) \in [1,c] \) for all \( n = 0, 1, \ldots, \max(A_N) \).<sup>[6](https://arxiv.org/abs/math/0302155)</sup> A paper in the *SIAM Journal on Discrete Mathematics* showed the Erdős–Turán conjecture equivalent to the corresponding finite problem, and that the conjecture for \( \mathbb{N} \) follows from the corresponding statement for \( \mathbb{Z} \).<sup>[11](https://epubs.siam.org/doi/10.1137/0401016)</sup>

## Where the analog fails

The conjecture is specific to the nonnegative integers. Over \( \mathbb{Z} \), bases with bounded, even unique, representation exist, so any proof must exploit the one-sided structure of \( \mathbb{N} \).<sup>[5](https://api.scinet.pub/p/c24c8b25-cb70-48da-a5b8-87a128d5992f)</sup> Nathanson proved that the group of integers possesses a perfect basis, one representing every element uniquely up to the order of summands.<sup>[12](https://math.haifa.ac.il/seva/Papers/ErTur.pdf)</sup>

Sergei V. Konyagin and Vsevolod F. Lev resolved the Erdős–Turán problem for infinite abelian groups. Ruzsa had shown that if \( p \) is a prime with \( \binom{2}{p} = -1 \), the group \( \mathbb{F}_p \times \mathbb{F}_p \) has a basis in which every element has at most 18 representations, and Haddad and Helou extended this to \( \mathbb{F} \times \mathbb{F} \) for any finite field of odd characteristic. Konyagin and Lev proved that an infinite abelian group \( G \) with \( |2G| = |G| \) has a perfect basis unless \( G \) is the direct sum of a group of exponent 3 and the group of order 2; in that exceptional case no perfect basis exists, but there is a basis in which every element has at most two representations. Each abelian group of exponent 2 has a basis in which every nonzero element has at most 36 representations.<sup>[12](https://math.haifa.ac.il/seva/Papers/ErTur.pdf)</sup>

## Partial results and status

The full conjecture remains open. Work on it includes a generating-function and level-set framework of Konstantoulas, who showed that assuming \( r_A(n) \le 5 \) eventually, a fixed lower bound holds in a special case, while an eventual bound of 6 or any larger constant remains compatible with the theorem.<sup>[13](https://erdosproblems.ai/wiki/library/additive_bases/konstantoulas_2013_lower_bounds_conjecture_erdos_turan)</sup> Related work studies \( B_2[g] \) sequences, sets in which no integer has more than \( g \) representations; Sidon bases, which combine the \( B_2 \) property with being an asymptotic basis, are known for order 7 by a construction of Deshouillers and Plagne, with later improvements at orders 5 and beyond.<sup>[14](https://arxiv.org/abs/2405.04154)</sup> A 2020 preprint by Theophilus Agama reformulates the conjecture using circles of partition, a combinatorial device for visualizing the representations of a fixed integer.<sup>[15](https://arxiv.org/abs/2010.11857)</sup>

The problem carries monetary weight in the Erdős tradition: Erdős offered 500 dollars for its resolution, alongside the 100 dollar prize for an explicit thin basis.<sup>[9](https://users.renyi.hu/~p_erdos/1989-35.pdf)</sup> Bloom's Erdős problems database, which tracks the status of more than a thousand Erdős questions, lists the conjecture among its open problems.<sup>[7](https://mathworld.wolfram.com/Erdos-TuranConjecture.html)</sup>

## References

1. [P. Erdős and P. Turán (1941). On a problem of Sidon in additive number theory, and on some related problems. *J. London Math. Soc.* **16**, 212–215.](https://www.math.tau.ac.il/~samotij/papers/Sidon.pdf)
2. [A. Sárközy and V. T. Sós. On additive representation functions.](https://users.renyi.hu/~sos/1997_On_additive_representation_functions.pdf)
3. [MathOverflow: Are any good strategies known for Erdős–Turán conjecture on additive bases of order two?](https://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-or)
4. [Táfula (2026). Representation Functions With Prescribed Rates of Growth. *Random Structures & Algorithms*.](https://doi.org/10.1002/rsa.70088)
5. [SciNet: Erdős–Turán conjecture — must an additive basis of order 2 have unbounded representation function? (Erdős #28)](https://api.scinet.pub/p/c24c8b25-cb70-48da-a5b8-87a128d5992f)
6. [M. B. Nathanson (2003). Generalized additive bases, König's lemma, and the Erdős–Turán conjecture. arXiv:math/0302155.](https://arxiv.org/abs/math/0302155)
7. [Erdős–Turán Conjecture, Wolfram MathWorld](https://mathworld.wolfram.com/Erdos-TuranConjecture.html)
8. [Erdős Problems forum thread on the Erdős–Turán conjecture](https://www.erdosproblems.com/forum/thread/blog%3A5?embed=1)
9. [P. Erdős (1989). Some problems and results on combinatorial number theory.](https://users.renyi.hu/~p_erdos/1989-35.pdf)
10. [An explicit economical additive basis. *Combinatorics, Probability and Computing* (Cambridge Core).](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/an-explicit-economical-additive-basis/F749896F8A541F7CF51238D198C9B064)
11. [Questions Related to the Erdős–Turán Conjecture. *SIAM Journal on Discrete Mathematics*.](https://epubs.siam.org/doi/10.1137/0401016)
12. [S. V. Konyagin and V. F. Lev. The Erdős–Turán problem in infinite groups.](https://math.haifa.ac.il/seva/Papers/ErTur.pdf)
13. [Konstantoulas: Lower bounds for a conjecture of Erdős and Turán, Erdős Problems library](https://erdosproblems.ai/wiki/library/additive_bases/konstantoulas_2013_lower_bounds_conjecture_erdos_turan)
14. [On the Erdős–Turán Conjecture and the growth of \( B_2[g] \) sequences. arXiv:2405.04154.](https://arxiv.org/abs/2405.04154)
15. [T. Agama (2020). On the Erdős–Turán additive base conjecture. arXiv:2010.11857.](https://arxiv.org/abs/2010.11857)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Numbers and algebra › Number theory › Analytic number theory › Additive number theory › Additive bases and asymptotic bases*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license