MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A \subset \mathbb{N}$ be a subset of the natural numbers and $h > 0$ be a natural number. Let $a(n) = |A \cap [1,n]|$ be the counting function of $A$, and let $r_{A,h}(n)$ be the number of ways to write $n$ as the sum of $h$ elements of $A$ be the representation function. We say $A$ is an additive basis $r_{A,h}(n) > 0$for every $n$ (or at least for all $n$ sufficiently large). In general, $a(n)$ and $r_{A,h}(n)$ are not too strongly correlated. For example, we can find sets such that $a(n) \sim \sqrt{n}$ but $r_{A,2}(n) \leq 1$ for all $n$. On the other hand, we have cases when the two functions are very strongly related such as is the case with the primes (Vinogradov's Theorem, for the case $h = 3$).

My question is, are there any conditions on $A$ that can guarantee that $a(n)$ and $r_{A,h}(n)$ are related? That is, some non-trivial bounds (either upper or lower) of one in terms of the other?

share|cite|improve this question

This is not a complete answer, but not quite a comment either.

One clarification to begin:

As I understand it the example with density $\sqrt{n}$ (Sidon) is not one where I find $a(n)$ and $r(n)$ rather unrelated; perhaps I am thus missing your point.

Let me elaborate why I find them quite related: the sum of two elements in $[1,n]$ will be in $[1,2n]$, with the $a(n)$ elements of $A$ in $[1,n]$ one can form about $a(n)^2/2$ sums. So if $a(n)$ is about $\sqrt{n}$ then in fact I expect (as a first heuristic) that no elment has more than $1$ representation, as for the $2n$ elements I only have about $n/2$ sums.

An example where I find them very unrelated is say all $n$ congruent $1$ modulo $3$ and $h=2$, then $a(n)$ is $n/3$ but still for some $n$ there is no representation while others have plenty of representations.

With my interpretation, I would say one property that tends to make them related is little additive structure in $A$, so more or less 'random' sets. Where by related I mean that the number of representations of each element is close to the one that one expects from the above counting/averaging argument and suitable generalizations.

In contrast, if there is some $M$ such that modulo $M$ the set $A$ is very unevenly distributed, then this will bias the representation function to be large/small on certain congruence classes modulo $M$.

A result due to Kneser roughly says that the number of elements with no representation is unexpectedly small (in a precise sense) if and only if the set is extremely badly distributed modulo some $M$.

Perhaps I should add that for the primes, as far as I know the standard assumption is, that in fact they behave, regarding this type of questions, like a random set with the appropriate desity, except for some bias comming from the fact that all but one prime is odd, all but one is not divisible by $3$ and so on. In fact, it is this assumption that is the foundation for various conjectures on the distribution of primes; in some cases it is possible to make this heuristic precise and to prove results in this direction.

share|cite|improve this answer
Right, linear bias is quite a strong indicator of whether $a(n)$ and $r_{A,h}(n)$ will be related or not. 'Random' or 'uniform' sets tend to enjoy having $a(n)$ and $r_{A,h}(n)$ be quite related. The problem is that a lot of the machinery for detecting linear bias, at least in Additive Combinatorics by Tao and Vu, rely on the ambient structure of a group, and the natural numbers of course are not a group. Hence I am looking for some other way to detect bias other than the Fourier-analytic ways in Tao-Vu. – Stanley Yao Xiao Feb 16 '11 at 3:08
Can't you just embed A into the integers and hence enjoy the ambient structure while only losing a factor of two or so? – Thomas Bloom Feb 16 '11 at 7:44
Regarding linking natural numbers to a group: another strategy is to not consider all of $A$ but to take some (variable) cutoff $N$ and to consider $A \cap [1,N]$ as a subset of the cyclic group integers modulo $N$; or also integers modulo some $N'$ that depends on $N$, say $2N$ or a prime of size about $2N$ to get even a prime cyclic group. Then one investigates the problem in the finite cyclic group(s), and then 'lifts' the information to the naturals. For example various proofs of Roth-type results, proving the existence of arith. prog. under density assumptions, work like this. – user9072 Feb 16 '11 at 17:16
I believe doing the Fourier-analysis in a finite group is actually desirable, even better would be if one could do it in a vector-space over a finite field. I cannot sketch why this is so, but this is a reason why analogues of questions for the naturals are considered intensely in vector spaces over finite fields; some problem go away in this setting yet others persist, and one tries to make progress on the persisting ones, first, in the simplified setting. – user9072 Feb 16 '11 at 17:28

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.