# In what cases are the counting function and representation functions strongly related?

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?

-

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.

-
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. –  quid 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. –  quid Feb 16 '11 at 17:28