Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi all,

My question concerns a general problem concern the Erdos-Turan conjecture on additive bases; that of finding thin subbases in a given basis. For a given $A \subset \mathbb{N}$, define $r_{A,h}(n)$ to be the number of ways to write $n$ as $h$ (not necessarily distinct) elements of $A$. We say $A$ is an additive basis if $r_{A,h}(n) > 0$ for all $n \in \mathbb{N}$. From some trivial counting arguments, one can easily deduce that $$\displaystyle N \leq \sum_{n \leq N} r_{A,h}(n) \leq | A \cap [1,N]|^h \leq \sum_{n \leq hN} r_{A,h}(n).$$ We wish to investigate "thin" bases; namely those such that the lower bound is essentially achieved... that is $|A \cap [1,N]| = O(N^{1/h + o(1)})$. Erdos showed in 1956 that such bases exist when $h=2$, and Erdos-Tetalli showed that such bases exist for all $h$ in 1990. Their argument uses the probabilistic method, and the result is essentially achieved by proving that additive bases $B$ exist with $r_{B,h}(n) = \Theta(\log n)$, which easily implies that $B$ is thin by the above inequality.

A question, then, raised by Erdos, Nathanson, and several others, is whether or not a given basis contains a thin subbasis. That is, if $A$ is an additive basis, does it necessarily contain a subset $B$ such that $B$ is an additive basis, and $r_{B,h}(n) = O(\log n)$. A partial answer was initially given by Choi, Erdos, and Nathanson who showed that the squares $\mathbb{N}^2$ contains a subbasis $B$ such that $r_{B,4}(n) = O(n^{1/3} + \epsilon)$. Relatively recently, Van Vu proved in 2000 that in fact $\mathbb{N}^k$ contains a thin subbasis for all $k \geq 2$ such that $r_{B,h}(n) = O(\log n)$. Trevor Wooley in 2003 gave that in this case, $h = O(k \log k)$.

A very natural question to ask which I have not seen any results or works in progress on, is to do this for the primes. The result seems to be highly plausible given the much stronger conjecture which asserts thin subbases exist for all additive bases, but also the fact that the primes are 'thicker' than $\mathbb{N}^k$ for any $k \geq 2$. However, the primes suffer the disadvantage of being much less structured than $\mathbb{N}^k$ and hence it is not so clear how to adopt the probabilistic method, still the only way to generate thin bases, would apply.

So the main question is this:

If $\mathcal{P}$ is the set of primes, then it is known (Goldbach-Shirnel'man) that $\mathcal{P}$ is an additive basis of order at most 6 (and hence all higher orders). Can one show, for some $h > 1$, that $\mathcal{P}$ contains a subset $B$ such that $B$ is an additive basis of order $h$ (that is, $r_{B,h}(n) > 0$ for all $n$ sufficiently large) and $|B \cap [1,N]| = O(N^{1/h + o(1)})$?

So I would greatly appreciate if anyone would shed more insight on this problem, the best would be a paper where someone has done relevant work on this topic.

Thanks in advance!

share|improve this question
Doesn't Vinogradov's theorem give that the primes are a basis of order 4? –  Thomas Bloom Mar 1 '11 at 6:09
Thomas, not quite. As in bounds on Warings problem, there are finitely many numbers that require (something like) 9 cubes, while the rest are at most asum of 8 cubes. Vinogradov did not show that EVERY odd integer is tne sum of 3 primes, he showed all but finitely many are. O. Ramare was part of the team that arrived at the value 6. Gerhard "Ask Me About System Design" Paseman, 2011.02.28 –  Gerhard Paseman Mar 1 '11 at 7:55
add comment

1 Answer

Two papers on this topic are: Granville's Refinements of Goldbach’s conjecture, and the generalized Riemann hypothesis and Wirsing's Thin subbases.

In Granville's paper it is shown that if a quantitative form of Goldbach's conjecture is true, then there exists a set of primes, B, such that $|B \cap [N]| \ll (N \ln(N))^{1/2}$ and every even integer is the sum of two elements of B. In Wirsing's paper it is shown that For any $k \geq 3$ there is a set $B_{k}$ of primes, such that $|B_{k} \cap [N]| \ll (N \ln(N))^{1/k}$, that is a basis of order k for large $n \equiv k mod 2$. All of these constructions are probabilistic.

If you only care that the sumset is almost all of the even/odd integers, one can remove the $\ln^{1/k}(N)$ term in the above results.

share|improve this answer
Wirsing's result does the job for estimating $|B \cap [1,N]|$, but does not quite achieve the result of $r_{B,k}(n) = O(\log n)$. Is this result known? –  Stanley Yao Xiao Mar 2 '11 at 3:07
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.