On the largest Sidon subset in a finite subset of ${\mathbb{R}}^N$

Abstract

We obtain a new lower bound on the largest Sidon subset of an arbitrary finite set of integers. If $H(n)$ denotes the minimum, over all $n$-element subsets of $\mathbb{Z}$, of the largest Sidon subset they contain, we prove that $H(n)⩾\left(\frac{1}{3\sqrt{3}}+o(1)\right)\sqrt{n}\gtrsim 0.19\sqrt{n}$. This improves a lower bound of Abbott related to a conjecture of Erdős on Sidon subsets of arbitrary sets of integers. The main ingredient is a compression lemma which produces, from any finite set of integers, a large subset admitting an injective Freiman $2$-morphism into a cyclic group. Combined with Singer's covering of $\mathbb{Z}/(q^2+q+1)\mathbb{Z}$ by Sidon sets, this yields the stated bound. We further extend the result to finite subsets of ${\mathbb{R}}^N$, uniformly in the dimension, by means of a projection argument and a Dirichlet approximation preserving Sidon's equation. As a consequence, every set of $n$ points in ${\mathbb{R}}^N$ contains a Sidon subset of cardinality at least $\left(\frac{1}{3\sqrt{3}}+o(1)\right)\sqrt{n}$. We also discuss an adaptation to $B_2[g]$ sets, obtaining a lower bound of order $\frac{1}{3\sqrt{3}}\sqrt{gn}$, and explain how the method can be adapted to other linear additive constraints.

11 pages, 2 figures. Comments welcome!