Thin subbases for the primes? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T20:29:15Z http://mathoverflow.net/feeds/question/56965 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56965/thin-subbases-for-the-primes Thin subbases for the primes? Stanley Yao Xiao 2011-03-01T05:16:02Z 2011-03-01T07:39:48Z <p>Hi all,</p> <p>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 <em>additive basis</em> 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. </p> <p>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)$. </p> <p>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 <strong>all</strong> 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.</p> <p>So the main question is this:</p> <p>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)})$?</p> <p>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.</p> <p>Thanks in advance!</p> http://mathoverflow.net/questions/56965/thin-subbases-for-the-primes/56973#56973 Answer by Mark Lewko for Thin subbases for the primes? Mark Lewko 2011-03-01T06:33:04Z 2011-03-01T07:39:48Z <p>Two papers on this topic are: Granville's <a href="http://www.ams.org/mathscinet-getitem?mr=2357316" rel="nofollow">Refinements of Goldbachâ€™s conjecture, and the generalized Riemann hypothesis</a> and Wirsing's <a href="http://www.ams.org/mathscinet-getitem?mr=832752" rel="nofollow">Thin subbases</a>.</p> <p>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.</p> <p>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.</p>