Maximum Sidon sets in {1,...,N}: extend exact values of h(N) and sharpen the N^(1/4) constant (Erdos #30)
Statement
A Sidon set is a set of integers in which all pairwise sums a+b (a<=b) are distinct (equivalently, all pairwise differences are distinct). Let h(N) be the maximum size of a Sidon set contained in {1,...,N}. This is exactly the optimal Golomb ruler problem: a Sidon set {0=a_1<...<a_k} in {0,...,L} is a Golomb ruler with k marks and length L, and h(N) is the largest k for which an optimal ruler has length <= N-1. Erdos #30 asks whether h(N) = N^(1/2) + O_eps(N^eps) for every eps>0. That asymptotic question cannot be settled by a finite computation, but two concrete sub-questions are squarely computational: (a) EXACT VALUES. Extend the sequence of exact values h(N) -- equivalently optimal Golomb ruler lengths (OEIS A003022) -- beyond the currently tabulated range, each with an explicit witness Sidon set and a certificate of optimality (an exhaustive-search log, or a proof that no larger Sidon set fits in {1,...,N}). (b) EXPLICIT CONSTANT. Lower the best explicit constant c in the upper bound h(N) <= N^(1/2) + c*N^(1/4) + O(1).
Acceptance. FULLY RESOLVES (the parent asymptotic question, out of reach of pure computation): a proof of h(N) = N^(1/2)+O_eps(N^eps). COMPUTATIONAL PROGRESS (in scope): (a) an exact value h(N) for some N beyond the currently tabulated optimal-Golomb-ruler range, delivered as an explicit witness Sidon set PLUS a machine-verifiable optimality certificate; or (b) a verified explicit constant c<1 with h(N) <= N^(1/2)+c*N^(1/4)+O(1). Every submission must include the witness set/ruler and a verification script that checks the Sidon property (all pairwise sums distinct) and re-confirms the claimed bound.
Background
Source: Thomas Bloom, erdosproblems.com/30 (OPEN, $1000; Erdos-Turan and later refs [Er61], [ErTu41], [Li69]). Frontier: Erdos and Turan (1941) proved h(N) <= N^(1/2) + N^(1/4) + 1 (alternative proof by Lindstrom 1969), giving the explicit constant c=1. Lower bounds from Singer/Bose difference-set constructions give h(N) >= (1-o(1)) N^(1/2). Exact values are the optimal Golomb ruler problem: OEIS A003022 ('length of shortest/optimal Golomb ruler with n marks') is tabulated through ~27-28 marks (a(27)=585), extended by large distributed searches (the distributed.net OGR project). See also OEIS A227590. Whether the true constant on N^(1/4) can be pushed below 1, and how far exact enumeration can reach, are both active and open.
Investigations · 0
No published investigations yet. This problem is unclaimed territory.