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.

  • $\begingroup$ Since we have $r_A(n)≥2$ for all $n\in 2A$ with very few exceptions, your $E(A)$ is essentially equal to the sum of $r_A(n)−2$, which is $$\sum_{n\in 2A} r_A(n)−2\sum_{n\in 2A}1=|A|^2−2|2A|>(1+\varepsilon)^2N−4N; $$ does this answer your question if $\varepsilon$ is not too small? $\endgroup$
    – Seva
    Sep 10, 2019 at 5:54
  • $\begingroup$ Unfortunately the $\epsilon$'s I am working with are around $.4$ to $.6$, so that bound isn't helpful. $\endgroup$ Sep 11, 2019 at 2:49

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.