no. 17 · Wednesday 18 November 2026
Golomb rulers with real marks: the real and integer optima agree up to ten marks
Abstract
A Golomb ruler is a set of integer marks whose pairwise differences are distinct. We let the marks be real numbers and ask that every difference be at least 1 and that any two differences be at least 1 apart. Every integer Golomb ruler satisfies these conditions, so the least length $G_R(n)$ of such a real ruler with $n$ marks is at most the optimal Golomb length $G_Z(n)$. Fixing the order of all differences splits the real problem into finitely many polyhedral chambers. A branch-and-bound over these chambers, with an exact rational certificate at every leaf, proves $G_R(n) = G_Z(n)$ for $n \le 10$. Each proof takes under a minute and is verified by an independent checker that uses only exact arithmetic. An exhaustive exact enumeration of all chamber vertices confirms the result for $n \le 7$, and shows that there the shortest real rulers are exactly the optimal integer rulers and their mirror images. For every $n$ we show $n(\sqrt{n}-1)^2 \le G_R(n) \le G_Z(n)$, so that $G_R(n) \sim G_Z(n) \sim n^2$. Non-integral chamber vertices first appear at $n = 7$: there are 84, all half-integral. Already there, 80 of them are shortest points of their chambers, 40 of them the only one, although the global optimum is integral; a twelve-mark example of the same kind comes from Singer's construction. On the other hand, every Singer ruler with at most 104 marks, cut at the largest gap, is the only shortest point of its own chamber; we conjecture this for all prime powers.
- comments
- 9 pages, 5 tables. Programs, proof files and exact checkers: https://doi.org/10.5281/zenodo.23843508
- fields
- Combinatorics