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\}$?
Best Answer
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!