Eccentricity in the number of representations for sets too large to be Sidon sets

Question

Let $A=\{a_1<a_2<a_3<\dots< a_k\}\subset\{1,2,\dots,N\}$ be a set of integers. Let $r_A(n)=\#\{(a_i,a_j):a_i+a_j=n\}$ be the number of representations of $n$ as a sum of two elements from $A$. In typical parlance, $A$ is a Sidon set (or $B_2$ set) if $r_A(n)\le 2$ for all $n$. It is known that the maximum size of a Sidon set that is a subset of $\{1,2,\dots,N\}$ is $\sqrt{N}(1+o(1))$.

My question, in general terms, is to ask if we can measure how often (and how much) $r_A(n)$ must exceed $2$, if $A$ contains at least $(1+\epsilon)\sqrt{N}$ elements, for some $\epsilon>0$?

More concretely, let $E(A)$ denote the "eccentricity" of $A$, given by $$E(A) = \sum_n \max\{r_A(n)-2,0\}. $$ If $|A|>(1+\epsilon)\sqrt{N}$ for some $\epsilon>0$, then must there exist some $\delta>0$ such that $E(A)>\delta N$?

---

My impetus for asking this question comes from my attempts to understand the binary digits of $\sqrt{2}$. Currently it is known that the number of $1$'s in the first $N$ binary digits of $\sqrt{2}$ is $\ge \sqrt{2N}(1+o(1))$, and for some infinite sequence of $N$'s this can be improved to $\ge \sqrt{8N/\pi}(1+o(1))$. However, this bound comes in part from assuming that the set of indices of the $1$'s behaves like a Sidon set, which it is too large to actually be. If it could be shown that $E(A)>\delta N$, then I believe a stronger lower bound could be proven.

Answer 1

There exists a set $A$ on $\{1,...,N\}$ where $ |A|\geq\frac{2}{\sqrt{3}}\sqrt{N}$ and $E(A)=o(N)$.

Let $B$ be a Sidon set on $\{1,...,n\}$. Let $C = \{3n+1-b | b\in B\}$. Let $A=B\cup C$.

Suppose $a<b\leq c<d$ and $a+d=c+b$, where $a,b,c,d$ are elements of $A$. Now I will analyze the possibilities of $a,b,c,d$.

• They can't be all in $B$ or all in $C$, as $B$ and $C$ are Sidon sets.

• They can't be 3 in $B$ and 1 in $C$, or vice versa. To see this, note that the sum of any two elements in $B$ is smaller than any element in $C$.

• So $a,b\in B$ and $c,d \in C$. Since $b-a=d-c$, it follows that $(3n+1-c)-(3n+1-d)=b-a$. Observe that $(3n+1-c)$, $(3n+1-d)$, $b$ and $a$ are all elements of the Sidon set $B$, so we have $(3n+1-c)=b$ and $(3n+1-d)=a$, i.e. $a+d=c+b=3n+1$.

So it's clear that $r_A(k)$ is larger than $2$ only if $k=3n+1$, where it's $O(\sqrt{n})$, which implies $E(A)=o(n)$.

Let $N$ be the largest element of $A$. $ |A|\geq\frac{2}{\sqrt{3}}\sqrt{N}$ and $E(A)=o(N)$, as required.