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.



Eccentricity in the number of representations for sets too large to be Sidon sets
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.


