Let $B \subset \mathbb{N}$ be a set of natural numbers such that $|B \cap [1,N]| \sim N^\gamma$, for some $\gamma > 0$ with the following property:

For any pair of positive integers $k,n$ we define $B_{k,n} = \{b \in B: b \equiv k \pmod{n}\}$. Then $|B_{k,n} \cap [1,N]| \sim \frac{1}{n} |B \cap [1,N]|$ as $N \rightarrow \infty$.

Now suppose that $\gamma > 1/h$. Does it follow that $B$ is necessarily an additive basis of order $h$?

We say a set $A \subset \mathbb{N}$ is an (asymptotic) additive basis of order $h$ if $hA = A + \cdots + A$ is equal to $\mathbb{N} \setminus C$, for some finite set $C$.

The motivation to this question is that $B$ is well-mixed, meaning that it has no bias towards any congruence class with respect to any modulus. A weaker version of this property is held by the primes, where we require $\gcd(k,n) = 1$ and the proportion is $1/\phi(n)$. Note that the primes do not satisfy the desired conclusion, since even though they have density $N/\log N$ they are not an additive basis of order 2, for example (the Goldbach conjecture asserts that they are an additive basis of order 3). In some sense this tries to capture true 'randomness', by which I mean the sets obtained via the probabilistic method of Erdős, constructed by choosing natural numbers at random where the positive integer $x$ has probability $x^{-\gamma}$ of being in the random set $B$. Such a procedure almost surely produces a random set without any bias towards any modulus.

  • $\begingroup$ No. Using irrational rotations on tori, you can get a set with counting function $\sqrt N$ which is not a basis of any order. $\endgroup$ Apr 15 '14 at 3:54
  • $\begingroup$ How does one prove that such a set is not an additive basis of finite order? $\endgroup$ Apr 15 '14 at 4:02
  • $\begingroup$ I'm not sure of the above claim any more. Below is the proof of a weaker statement (which still answers your question in the negative). $\endgroup$ Apr 15 '14 at 4:58
  • $\begingroup$ Another example that goes strongly against the spirit of the question is this: pick $n_1\ll n_2\ll n_3\ll n_4\ll \ldots$ and set $B=\mathbb N\setminus\bigcup_k [n_k,k\cdot n_k]$. For fast enough growing $n_k$ ($2^{k^2}$ is ample), it's easy to see that this set is not a basis of any order, as you can't make $k\cdot n_k$ using $k$ terms from the set. Its counting function exceeds $N^{1-\epsilon}$ for any $\epsilon$ and it's well mixed. The only issue is that it doesn't have an actual growth rate, as the counting function is between $N^{1-o(1)}$ and $N$. $\endgroup$ Apr 15 '14 at 14:56

Fix an $h\in\mathbb N$. Choose your favourite irrational, $\alpha$. Let $B=\{n\in\mathbb N\colon \langle\alpha n\rangle\in [0,\frac{1}{2h})\}$. (Here $\langle x\rangle$ denotes the fractional part of $x$. Then if $n_1,\ldots,n_h\in B$, and $m=n_1+\ldots+n_h$, then $\langle m\alpha\rangle=\langle n_1\alpha\rangle +\ldots+\langle n_h\alpha\rangle\in [0,\frac 12)$. Hence not every $m$ can be expressed as a sum of $h$ elements of $B$.

By the ergodic theorem, or uniform distribution or whatever $|B\cap [1,N]|\approx N/(2h)$, so that your size condition is satisfied. Also $|B\cap [1,N]\cap B_{k,n}|\approx N/(2nh)$, so that the mixing is satisfied (in ergodic terms, irrational rotations are disjoint from rational rotations; more informally the irrational multiple condition is independent of the rational multiple condition).

  • $\begingroup$ Did you mean $|B_{k,n} \cap [1,N]| \sim N/(2nh)$ instead? $\endgroup$ Apr 15 '14 at 12:10
  • $\begingroup$ Yes. I've fixed this. $\endgroup$ Apr 15 '14 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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