MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

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.

share|cite|improve this question
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. – user9072 Sep 7 '11 at 14:00
I suppose you mean this Erdos-Turan conjecture.… Please be more self-contained. – Gil Kalai Sep 7 '11 at 14:38
Nice problem!!! – Gil Kalai Sep 7 '11 at 14:40

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.

share|cite|improve this answer

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

share|cite|improve this answer
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

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

share|cite|improve this answer

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.