The set of primes $\mathbb{P}$ has many interesting properties in additive number theory and some of the most famous open problems about $\mathbb{P}$ are the well-known Goldbach's strong and weak conjectures. The weak conjecture was proven by Vinogradov for all sufficiently large integers. Moreover, Chen was able to prove that every sufficiently large even integer is the sum of a prime and a semiprime, which is either a prime or a product of two primes.

The purpose of this question is to find out how much do these additive properties of $\mathbb{P}$ result from the special (e.g. multiplicative) properties of the set of primes and how much do they just rely on the relatively large number of primes $\leq x$.

The density of a set seems to have a large effect on its additive properties; one may for instance define the Schnirelmann density (of course there are many other densities, too) of a set as $\sigma A=\displaystyle \inf_{n\in \mathbb{Z_+}} \frac{A(n)}{n}$, where $A(n)$ is the number of elements of $A$ that are $\leq n$, and it was proven by Schnirelmann that if $A$ is any set with $\sigma A>0$, there exists a positive integer $k$ such that $kA = \mathbb{Z}_+$.

Also if $A+B\neq {\mathbb{Z}}_+$, we have $\sigma (A+B)\geq \sigma A+\sigma B$ as was proven by Mann. It is clear that if $1 \not \in A$, we have $\sigma A=0,$ but by cosidering $B=A\cup \{1,2,..,N\}$ and using Schnirelmann's theorem, one might be able to prove that all sufficiently large integers belong to $kA$ for $k$ large enough (for certain sets $A$). Using his theorem and Brun's sieve, Schnirelmann proved that every integer $>1$ is the sum of at most $C$ primes for some constant $C$.

By the prime number theorem, the set of primes that are not greater than $x$ has size $\pi(x) \sim li(x) \sim \frac{x}{\log x}$, where $li(x)$ is the logarithmic integral. Therefore, the set of primes is very large (in this sense) when compared to, say, perfect $k$-th powers. If one assumes the Riemann hypothesis, the set of primes also does not have very large gaps, more precisely, there is a prime on the interval $[x,x+\sqrt x \log x]$ for large values of $x$ as was proven by Schoenfeld under Riemann hypothesis. On the other hand, the behavior of primes seems to be locally very random, and therefore one might guess that a set with similar number of elements $\leq x$ and same maximum gap size would be a finite additive basis for the positive integers that are greater than some constant.

The question is: given an arbitrary set $A\subset \mathbb{Z}_+$ with $A(x)>> \frac{x}{\log{x}}$, and the difference of consecutive elements $x,y\in A$ is $O(\sqrt x \log x)$, and for every positive integer $n>1$ there are infinitely many elements of $A$ not divisible by $n$ (this condition is to prevent $A$ from having only even numbers, for example), is it known that there exists $k$ (which may depend on $A$) such that every positive integer large enough is the sum of at most $k$ numbers from $A$? If not, is there a known counterexample? In case of a counterexample, could some conditions that hold for $\mathbb{P}$ but that do not characterize the set of primes be given such that the question is true? In particular, does the claim hold for $A= \{\lfloor n\log n\rfloor, n \geq 2\}$?

  • $\begingroup$ "such that for each n, there is a multiple of n which is in A (this condition is to prevent A from having only even numbers, for example)" You mean "non multiple of $n$", i.e. just that elements of $A$ are mutually coprime? $\endgroup$ Apr 19, 2012 at 20:07
  • $\begingroup$ I changed the condition, thanks. I would only require that for each n there are infinitely many elements of A not divisible by n, but if the condition that all the elments are mutually comprime turns out to be better, then I shall change to that. $\endgroup$ Apr 19, 2012 at 20:18
  • 2
    $\begingroup$ This isn't an answer, but for $k=2$ fixed nothing of this nature can be true. Select a random set with this density. The number of integers involved in a solution of x+y=n for a fixed n will have zero relative density in the entire set and thus can be removed (for infinity many of $n$) without essentially changing the density properties of the set and preserving the existence of infinitely many numbers with your divisibility property. Something along these lines may work for higher $k$, but it isn't immediately clear. $\endgroup$
    – Mark Lewko
    Apr 19, 2012 at 21:25
  • 2
    $\begingroup$ @Mark, When I read 'the number of integers involved in a solution of $x + y = n$ for a fixed $n$ will have zero relative density in the entire set' I thought 'well, that's trivial, because that number is finite for every fixed $n$, while the entire set is infinite. But that does't mean you can remove these for infinitely many $n$.' But after some thought I realized that you probably mean that, if $A_1(n)$ is the number of solutions to $x + y = n$, then $\displaystyle \lim_{n \rightarrow \infty} \frac{A_1(n)}{A(n)} = 0$ with high probability, right? $\endgroup$
    – Woett
    Apr 20, 2012 at 0:49
  • 1
    $\begingroup$ @Woett, yes that is what I meant. To see this, let $p_a$ denote the probability that $a$ is in $A$. Now the probability that any particular $x$ solves the equation x+y=n is $p_x \times p_{n-x}$ (since $x$ is a solution if and only if both $x$ and $n-x$ is in $A$). Thus the expected number of solutions will be $n/\log^2(n)$. $\endgroup$
    – Mark Lewko
    Apr 20, 2012 at 1:16

3 Answers 3


Let $A_n = \{a : a \equiv 1 \mod 2^n \mbox{ and } 2^{2^{n-1}} \leq a < 2^{2^{n}} - 2^{2^{n-1}}\}$, and let $\displaystyle A = \bigcup_{n=1}^\infty A_n$.

Then, $A(x) >> \frac{x}{\log x}$, the gap sizes are $<< \sqrt{x}$, and $A$ contains infinitely many non-multiples of $m$ for every $m>1$.

However, $2^{2^n}$ cannot be written as a sum of fewer than $n-\log_2 n$ elements of $A$. To prove this, suppose the contrary; say $2^{2^{n}} = a_1 + \cdots + a_k$ for $k < n-\log_2 n$, $a_1 \leq \cdots \leq a_k$, $a_i \in A$. We know that $a_k \in A_n$, because if not, then all the $a_i < 2^{2^{n-1}}$, so, summing, $2^{2^n} < k \cdot 2^{2^{n-1}}$, implying $2^{2^{n-1}} < n$, which is false for positive $n$. One applies a similar argument to each of the partial sums of the $a_i$, in turn from largest to smallest, to show that $\displaystyle a_j \in \bigcup_{i=n-k+j}^n A_i$. In particular, each $a_j \equiv 1 \mod 2^{n-k+1}$, so the sum $2^{2^n} \equiv k \mod 2^{n-k+1}$. Thus, $2^{n-k+1} \mid k$; in particular, $2^{n-k+1} \leq k$. Using the bound $k < n-\log_2 n$ on both sides, we may deduce $2n < n-\log_2 n$, a contradiction.

For a possible fix, I would assume that $A$ is well-distributed modulo $m$ (for every $m$) in an appropriate sense. (I'm being purposefully vague here, and you might need something rather strong, like an analogue of Bombieri-Vinogradov). Good luck!


The claim holds for the specific example of $\lfloor n\log{n}\rfloor$. This follows from a theorem of Wirsing, which is discussed in pp. 208--210 of these notes:


(The book version of these notes has since been published by the AMS, but the relevant section was cut pre-publication.)


This is really a comment rather than an answer but it's too long for the comment box.

Halberstam and Roth's book Sequences (2nd edition, 1983) says:

It would therefore be extremely valuable to find conditions sufficient to ensure that a sequence $\mathscr B$ is a basis, which are less stringent than the [Schnirelmann density] condition $\ldots$ Unfortunately, known results in this direction are, up to the present, of rather a negative nature; for example, it has been proved [A. Stöhr, `Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I,' J. reine angew. Math. 194 (1955) 40–65, $\S$7] that for sequences $\mathscr B$ of zero asymptotic density, a lower bound for $B(n)$ (in terms of $n$) can never by itself ensure that $\mathscr B$ is a basis.

I took a quick look at Stöhr's paper and Stöhr's counterexample sequences have large gaps. Since you're excluding large gaps by fiat, Stöhr's results don't answer your question directly, but perhaps suggest that the kind of result you're looking for is difficult to prove.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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