Question

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.

Answer 1

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.

Answer 2

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

Answer 3

@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.