On the diameter and distribution of Sidon sets
math.CO
Submitted: 2026-10-26
Updated: 2026-10-26
Comments: 33 pages, 9 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: A Sidon set is a set A of integers with the property that if 0 not equal to a-b=c-d and a,b,c,d in A, then (a,b)=(c,d).
Abstract
A Sidon set is a set A of integers with the property that if 0 not equal to a-b=c-d and a,b,c,d in A, then (a,b)=(c,d). Our main result is an improved and explicit bound on the diameter of a Sidon set: if A is a Sidon set with k at least 1 elements, then diam(A) at least k squared (1 over 1 + 0.945/sqrt k-0.945 over sqrt k) -1; in particular, diam(A) at least k 2-1.89 k 3/2. This implies that if A [1,N] is a Sidon set, then A at most N 1/2+0.945, N 1/4+0.447. Our technique also gives an improved bound for the case of large k, namely diam(A) at least k 2-1.88607 k 3/2 for k at least 483. A γ-Golomb ruler is a set A of integers with the property that there are not γ+1 distinct pairs (a i,b i) in A squared with 0 not equal to a 1-b 1= =a γ+1-b γ+1. Our diameter bounds extend in a natural way to the case of Golomb rulers. Our techniques can also be adapted to address a number of questions on the distribution of Golomb rulers: we provide upper bounds on the two quantities a-a 1 --1 over k-1(a k-a 1) and 1 at most i<k (a i+1-a i), where A=a 1< <a k is a γ-Golomb ruler with diam(A) at most (k 2-bk 3/2)/γ (where b in R is a free parameter).
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality