# An “Average” Erdős–Turán conjecture

Right, so the Erdős–Turán conjecture for additive bases (of order 2) says, with the usual notations, that $\sup r_B (n) = \infty$. Let’s look instead at the average number of representations, i.e.: the function

$$F(N) = \frac1N \sum_{n=1}^{N} r_B (n)$$

This seems entirely natural to me, indeed more natural than looking at $(\lim)\sup r_B (n)$, if the idea is to demonstrate that a basis must have some “thickness”. There are examples known where $\sup F(N) < \infty$, indeed any so-called “thin” basis has this property. Recall that a basis is “thin” if there exists $c > 0$ such that the $k$th element of the basis is at least $c \cdot k^2$. Now an obvious question to ask is whether $\limsup F(N)$ can equal one? (It must be at least one if $B$ is a basis.) I have searched the literature in vain for an answer. In particular, I have not found any result on thin bases which directly translates into an answer to this question, though that may because I am too stupid to see some connection. Any comments most welcome.

-
Hi Peter, welcome to MO! –  Johan Wästlund Sep 7 '11 at 13:32
Sorry, I gave a wrong asnwer, as I misread a definition in a source I was quoting. –  quid Sep 7 '11 at 14:00
I suppose you mean this Erdos-Turan conjecture. garden.irmacs.sfu.ca/?q=op/… Please be more self-contained. –  Gil Kalai Sep 7 '11 at 14:38
Nice problem!!! –  Gil Kalai Sep 7 '11 at 14:40

The following (I have not enough money here to write a comment) may be useful:

MR2357652 (2008j:11004) Grekos, G.(F-SETN); Haddad, L.(1-PASME); Helou, C.; Pihko, J.(FIN-HELS-MS) Representation functions, Sidon sets and bases. Acta Arith. 130 (2007), no. 2, 149–156. 11B34 (11B13 11B75) PDF Clipboard Journal Article Make Link

Let $A\subseteq\Bbb N=\{0,1,2,\ldots\}$, and consider the $h$-representation function $$r_h(A,n)=|\{\langle a_1,\dots,a_h\rangle\in A^h\colon \ a_1+\cdots+a_h=n\}|.$$ $A$ is said to be an $h$-basis (resp., an asymptotic $h$-basis) of $\Bbb N$ if $r_h(A,n)>0$ for all $n\in\Bbb N$ (resp., for all sufficiently large $n\in\Bbb N$). We call $A$ a Sidon set if $r_2(A,n)\le 2$ for all $n\in\Bbb N$ (i.e., all the sums $a_1+a_2$ with $a_1,a_2\in A$ and $a_1\le a_2$ are distinct). In 1994, P. Erdős, A. Sárközy and V. T. Sós [Discrete Math. 136 (1994), no. 1-3, 75--99; MR1313282 (96d:11014)] asked whether there exists a Sidon set which is also an asymptotic 3-basis of $\Bbb N$. In the paper under review, the authors show that a Sidon set cannot be a 3-basis of $\Bbb N$, and also give a simple proof of the known fact that a Sidon set cannot be an asymptotic 2-basis of $\Bbb N$. Reviewed by Zhi-Wei Sun

-
I'm aware of that paper, I don't think it contains anything which bears on my question. Note, by the way, that they consider ordered representations, in which case my question is whether limsup F(N) can equal 2 ? –  Peter Hegarty Sep 7 '11 at 15:28
Another thing : The review of that 2007 paper is misleading. Their proof that a Sidon set cannot be an asymptotic 2-basis is exactly the same generating function proof given by Erdos, even if they use different notation. There is nothing whatsoever "simpler" about it. I can prove that result without generating functions (don't know if it's written down anywhere, but I gave it as a problem on my last number theory exam), but the argument I have is so far much too weak to say anything about the average number of representations. –  Peter Hegarty Sep 8 '11 at 12:05
Yous should contact the authors, I am afraid not to understand both the review and your comment, ... –  Luis H Gallardo Sep 8 '11 at 19:55
In a funny way, it is easy to show that an additive basis $B$ cannot be thin both in the sense of Erdős-Turán and in your sense; that is, either $\sup r_B=\infty$, or $\limsup F_B(N)>1$ hold true. To see this, we assume that $\sup r_B<\infty$ and invoke a theorem of Erdős-Fuchs which (stripping out some extras irrelevant to our present purposes) says that for any $c>0$, and any non-decreasing infinite sequence $B$ of non-negative integers (not necessarily a basis), one has $$\limsup \frac1N\sum_{n=1}^N (r_B(n)-c)^2 > 0.$$ Applying this with $c=1$ and observing that in our case we have $0\le r_B(n)-1<C$, with a constant $C$ (possibly depending on $B$), we readily derive $$\limsup \frac1N\sum_{n=1}^N (r_B(n)-1) > 0;$$ that is, $\limsup F(N)>1$, as wanted.
@Seva : Yes, I had also noticed this, and in fact it has an elementary proof. First, if $B$ is an asymptotic basis then there must be some $\epsilon > 0$ such that $b_n \leq n^{2}/(2+\epsilon)$ for infinitely many $n$. To see this, observe that all but $O(1)$ of the numbers up to $b_n$ must be expressible as $b_i + b_j$, for some $1 \leq i,j < n$. There are $n^{2}/2 + O(n)$ such sums, hence $b_n \leq n^{2}/2 + O(n)$. But if we also had $b_i \geq i^{2}/(2+\epsilon)$ for all $i \gg 0$ and some sufficiently small $\epsilon$, then $\Theta(n^2)$ of all these sums $b_i + b_j$ would necessarily be greater than $b_n$. Unwinding this, we see that there must be infinitely many $n$ such that $b_n \leq n^{2}/(2+\epsilon)$, for some $\epsilon > 0$, as claimed.
Now fix such an $\epsilon$ and consider a sufficiently large $n$. Then amongst the differences $b_{i+1}-b_i$, for $1 \leq i < n$, there can only appear at most $(1-\epsilon_2)n$ distinct numbers, where $\epsilon_2$ depends only on $\epsilon$. Any repeated difference leads to a repeated sum of the form $b_{i+1}+b_j = b_{j+1} + b_i$. There are thus at least $\Theta(n)$ such pairs. We can apply the same argument to differences $b_{i+t}-b_i$, for any fixed $t \in [1,\epsilon_3 n]$, where $\epsilon_3$ depends only on $\epsilon$. Then in total we will get at least $\Theta(n^2)$ pairs of equal sums, with no repititions. But if the representation function $r_B$ were bounded, any particular sum could only arise from $O(1)$ pairs. This would therefore imply that there are $\Theta(n^2)$ numbers $x \in [1,2b_n]$ such that $r_B (x) > 1$. Since $b_n = O(n^2)$, we conclude that the average value of $r_B$ on the interval $[1,2b_n]$ is bounded away from one. Since this is true for infinitely many $n$, we have that the limsup of the average is bounded away from one.