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

Let $$A=\{a_1 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.

• 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?
– Seva
Sep 10 '19 at 5:54
• Unfortunately the $\epsilon$'s I am working with are around $.4$ to $.6$, so that bound isn't helpful. Sep 11 '19 at 2:49

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