A subcase of Problem #42

Problem #42 on Bloom's website of Erdős Problems asks about a fascinating property of Sidon sets. While the problem itself is wide open, one can still salvage something when the set is "smaller than dense". This is what we will see here.

Theorem: Fix an integer $M\ge 1$. Then there exists $N_0=N_0(M)$ such that for every $N\ge N_0$ and every Sidon set $A\subset [N]:=\{1,2,\dots, N\}$ with $|A|=o(\sqrt N)$, there exists a Sidon set $B\subset [N]$ with $|B|=M$ such that $(A-A)\cap(B-B)=\{0\}$.

To begin with, for a finite set $S\subset \mathbb Z$, define $S-S := \{s-s': s,s'\in S\}$ and $\Delta(S) := \{s-s': s,s'\in S,\ s>s'\}\subset \mathbb N$. Then, $S-S \,=\, \{0\} \cup \Delta(S) \cup (-\Delta(S))$.

First consider the first two lemmas, which are obvious from definition, and then a third one whose proof is provided.

Lemma 1: If $S\subset\mathbb Z$ is Sidon, then the map
$$\phi:\{(s,s')\in S^2: s>s'\}\to \mathbb N,\quad \phi(s,s')=s-s'$$
is injective. In particular, $|\Delta(S)|=\binom{|S|}{2}$.

Lemma 2: Let $S\subset\mathbb Z$ be finite. If all elements of $\Delta(S)$ are distinct (equivalently, $\phi$ above is injective), then $S$ is Sidon.

Lemma 3: Let $N\ge 1$, $F\subset \{1,2,\dots, N-1\}$, and let $M\ge 1$. Let
$$C_M \,:=\, M \,+\, \sum_{r=1}^{M-1} r\binom{r}{2} \,=\, M+\frac12\sum_{r=1}^{M-1}(r^3-r^2)$$
be a constant depending only on $M$. If $N \ge \binom{M}{2} |F| + C_M$, then there exists a set $B=\{b_1<b_2<\cdots<b_M\}\subset [N]$ such that $\Delta(B)\cap F=\emptyset$, and all elements of $\Delta(B)$ are distinct (implying $B$ is Sidon by Lemma 2).

Proof: We build $b_1<b_2<\dots<b_M$ inductively, always choosing the new element to the right of the previous ones. Let $b_1:=1$. For $t\ge 2$, suppose $b_1<\dots<b_{t-1}$ have been chosen so that $\Delta({b_1,\dots,b_{t-1}})\cap F=\emptyset$ and all positive differences among $\{b_1,\dots,b_{t-1}\}$ are distinct. Let $E_{t-1}:=\Delta({b_1,\dots,b_{t-1}})$. Then, $|E_{t-1}|=\binom{t-1}{2}$.

We seek an integer $b_t>b_{t-1}$ such that for every $i\in\{1,\dots,t-1\}$, $b_t-b_i \notin F$ and $b_t-b_i \notin E_{t-1}$. For fixed $i$, the condition $b_t-b_i\in F$ is equivalent to $b_t\in b_i+F$. Similarly $b_t-b_i\in E_{t-1}$ is equivalent to $b_t\in b_i+E_{t-1}$. Therefore the set of "bad" values of $b_t$ is contained in
$$\mathcal B_t:=\bigcup_{i=1}^{t-1}(b_i+F)\ \cup\ \bigcup_{i=1}^{t-1}(b_i+E_{t-1})$$
implying
$$|\mathcal B_t|\le \sum_{i=1}^{t-1}|b_i+F| + \sum_{i=1}^{t-1}|b_i+E_{t-1}| = (t-1)|F| + (t-1)\binom{t-1}{2}$$
by a union bound.

Now consider the consecutive integers $b_{t-1}+1, b_{t-1}+2,\dots$. Among these, at most $|\mathcal B_t|$ are forbidden. Hence the least integer $>b_{t-1}$ satisfying the two required properties obeys $b_t \,\le\, b_{t-1} \,+\,  |\mathcal B_t| \,+\, 1 \,\le\, b_{t-1} \,+\, (t-1)|F| \,+\, (t-1)\binom{t-1}{2} \,+\, 1$. Define an explicit upper-bound sequence $U_t$ by $U_1:=1$ and
$$U_t:=U_{t-1} + (t-1)|F| + (t-1)\binom{t-1}{2}+1$$
for $t\ge 2$. Then, we can choose $b_t\le U_t$ at each step, so in particular $b_M\le U_M$. This gives
$$U_M = 1 + \sum_{t=2}^M \left((t-1)|F| + (t-1)\binom{t-1}{2}+1\right) = \binom{M}{2}|F| + C_M$$
on summing the recurrence. So, $U_M\le N$ and hence $b_M\le N$, so $B:=\{b_1,\dots,b_M\} \subset[N]$ exists. Finally, by construction, no new positive difference equals an old one, hence completing the proof. $\square$

Equipped with all these, we can finally provide a proof of the advertised theorem.

Proof of Theorem: Let $A\subset [N]$ be Sidon and let $|A|=o(\sqrt{N})$. Let $F:=\Delta(A)\subset{1,\dots,N-1}$. By Lemma 1, $|F| = |\Delta(A)| = \binom{|A|}{2} \le \frac{|A|^2}{2}=o(N)$. For a fixed $M$, we have
$$N \ge \binom{M}{2}|F| + C_M$$
for all sufficiently large $N$. So, there exists $B\subset[N]$ with $|B|=M$ and $B$ Sidon, so that
$$\Delta(B)\cap\Delta(A)=\emptyset$$
using Lemma 3.

It remains to show $(A-A)\cap(B-B)=\{0\}$. Let $x\neq 0$ and $x\in(A-A)\cap(B-B)$. Then $|x|\in\Delta(A)$ and $|x|\in\Delta(B)$, a contradiction. This gives
$$(A-A)\cap(B-B)=\{0\}$$
hence completing the proof. $\square$

On the Sidon Tails of $\left\{\left\lfloor x^n\right\rfloor\right\}$

A set of positive integers $A\subset \mathbb N$ is called a Sidon Set or a Sidon Sequence if the equation $a+b=c+d$ does not have any non-trivial solutions in $A$. It is known (and fairly easy to prove) that the sets

$$\mathbf S_x := \big\{\left\lfloor x^n\right\rfloor : n\in \mathbb N\big\}$$

are Sidon for $x\ge 2$. In a recent preprint, I investigated the tails of these sequences in the range $x\in (1,2)$. In particular, one of the results I proved is that $\mathbf S_x$ has Sidon tail for almost all $x\in (1,2)$. It was only after I uploaded the preprint, and it was only after I sent the paper to a journal, that I realised that an even stronger statement is true. This is what I will prove here.

To keep this post self-contained, we will call an $\mathbf S_x$ tail Sidon if there exists $N_0$ such that the set

$$\big\{\left\lfloor x^n\right\rfloor : n\ge N_0\big\}$$

is a Sidon set.

Theorem: If $\mathbf S_x$ is not tail Sidon, then $x$ is algebraic. In particular, one can produce integers $u> w\ge v\ge 1$ such that

$$1+y^u-y^v-y^w=0 \qquad\text{or}\qquad 1-y^v-y^w=0$$

for $y:=\frac 1x \in (0,1)$.

Proof: Assume an $x$ for which $\mathbf S_x$ is not tail Sidon. Note that $\mathbf S_x$ is eventually increasing - so, from now on, we will only work in this increasing tail. Let $\mathbf x_n:=\left\lfloor x^n\right\rfloor$. It is easy to show that if there are indices $a$, $b$, $c$ and $d$ such that $\mathbf x_d+ \mathbf x_a = \mathbf x_b+ \mathbf x_c$, then $a<b\le c<d$.

Now, write $\theta_n := x^n-\lfloor x^n\rfloor \in [0,1)$. If $\mathbf x_d+\mathbf x_a=\mathbf x_b+\mathbf x_c$, then

$$x^d+x^a-x^b-x^c = (\theta_d+\theta_a)-(\theta_b+\theta_c)$$

implying $\bigl|x^d+x^a-x^b-x^c\bigr|<2$.

Now, define

$$y:=\frac1x\in(0,1),\qquad u:=d-a,\quad w:=d-b,\quad v:=d-c$$

so that

$$\bigl|1+y^u-y^w-y^v\bigr|<2y^d$$

for infinitely many quadruples $(u,v,w,d)$ with $d\to\infty$.

Choose $D_0$ for which $4y^{D_0}<1$. Consider any collision $-2y^d < 1+y^u-y^w-y^v < 2y^d$ for $d\ge D_0$. This gives

$$y^v+y^w > 1+y^u-2y^d \ge 1-2y^d > \frac12$$

since $y^u\ge 0$ and $2y^d<\tfrac12$. Since $v\le w$ and $0<y<1$, we have $y^v\ge y^w$, hence $y^v+y^w \le 2y^v$. Therefore $2y^v>\tfrac12$, i.e. $y^v>\tfrac14$. Because $v\mapsto y^v$ is strictly decreasing, there is a bound $V=V(y)$ such that for every collision with $d\ge D_0$, one has $v\le V$.

Using $y^v+y^w > 1-2y^d$ in a similar way as in the last argument, we also get a bound $W=W(y)$ such that for every collision with $d\ge D_1$, one has $w\le W$. In other words, all sufficiently large collisions lie in the finite set $\{(v,w)\in\mathbb N^2:\ 1\le v\le w\le W\}$. Since there are infinitely many collisions with $d\to\infty$, by the pigeonhole principle there exist fixed integers $v_0$, $w_0$ and an infinite subsequence of collisions along which $(v,w)=(v_0,w_0)$ and $d\to\infty$.

Let $C:=C(y):=y^{v_0}+y^{w_0}$ so that

$$\bigl|1+y^{u}-C\bigr|<2y^{d}\xrightarrow[]{d\to\infty}0$$

so that $y^{u}\to C-1$.

If $C=1$, then $y^{v_0}+y^{w_0}=1$, i.e., $1-y^{v_0}-y^{w_0}=0$.

If $C>1$, then $y^{u}\to C-1>0$. Since $y^n\to 0$, the exponents $u$ cannot tend to $\infty$; more formally, choose $M$ such that $2y^M<C-1$. For all sufficiently large terms of the subsequence, $2y^{u}>C-1$ implying $u<M$. Thus, $u$ takes values in a finite set $\{1,2,\dots,M-1\}$, so there exists $u_0$ and a further infinite subsequence with $u=u_0$ constant.On that further subsequence, we have
$$\bigl|1+y^{u_0}-C\bigr|<2y^{d}\xrightarrow[]{d\to\infty}0$$

implying $1+y^{u_0}-C = 0$, and hence, $1+y^{u_0}-y^{v_0}-y^{w_0}=0$.

This completes the proof in both cases.