On the diameter of finite Sidon sets

Abstract We prove that the diameter of a Sidon set (also known as a Babcock sequence, Golomb ruler, or $$B_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>B</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> set) with $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> elements is at least $$k^2-b k^{3/2}-O(k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mi>b</mml:mi> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>-</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> where $$b\le 1.96365$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>b</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>1.96365</mml:mn> </mml:mrow> </mml:math> , a comparatively large improvement on past results. Equivalently, a Sidon set with diameter $$n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> has at most $$n^{1/2}+0.98183n^{1/4}+O(1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>+</mml:mo> <mml:mn>0.98183</mml:mn> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> elements. The proof is conceptually simple but very computationally intensive, and the proof uses substantial computer assistance. We also provide a proof of $$b\le 1.99058$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>b</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>1.99058</mml:mn> </mml:mrow> </mml:math> that can be verified by hand, which still improves on past results. Finally, we prove that $$g$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>g</mml:mi> </mml:math> -thin Sidon sets (aka $$g$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>g</mml:mi> </mml:math> -Golomb rulers) with $$k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> elements have diameter at least $$g^{-1} k^2 - (2-\varepsilon)g^{-1}k^{3/2} - O(k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>g</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>-</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:mi>ε</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:msup> <mml:mi>g</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>-</mml:mo> <mml:mi>O</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , with $$\varepsilon\ge 0.0062g^{-4}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>0.0062</mml:mn> <mml:msup> <mml:mi>g</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>4</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> .