betaFeedback

WorksMathematics

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 GR(n)G_R(n) of such a real ruler with nn marks is at most the optimal Golomb length GZ(n)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 GR(n)=GZ(n)G_R(n) = G_Z(n) for n≤10n \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≤7n \le 7, and shows that there the shortest real rulers are exactly the optimal integer rulers and their mirror images. For every nn we show n(n−1)2≤GR(n)≤GZ(n)n(\sqrt{n}-1)^2 \le G_R(n) \le G_Z(n), so that GR(n)∼GZ(n)∼n2G_R(n) \sim G_Z(n) \sim n^2. Non-integral chamber vertices first appear at n=7n = 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.

Introduction

A Golomb ruler with nn marks is a set of integers 0=x1<x2<⋯<xn0 = x_1 < x_2 < \cdots< x_n whose differences xj−xix_j - x_i (i<ji < j) are pairwise distinct. Let GZ(n)G_Z(n) be the least possible length xnx_n. For n=2,…,10n = 2, \ldots, 10 it is 1, 3, 6, 11, 17, 25, 34, 44, 55 (OEIS A003022 [13]). It is known for n≤28n \le28, in each case by exhaustive computer search; the last cases were completed by distributed.net in 2022 [5].

Definition 1. A real 1-separated ruler with nn marks is a sequence of real numbers 0=x1<⋯<xn0 = x_1 < \cdots< x_n with xj−xi≥1x_j - x_i \ge1 for all i<ji < j and ∣(xj−xi)−(xl−xk)∣≥1\lvert(x_j - x_i) - (x_l - x_k)\rvert\ge1 for all pairs (i,j)≠(k,l)(i, j) \ne(k, l) with i<ji < j and k<lk < l. Let GR(n)G_R(n) be the infimum of xnx_n over such rulers.

For integer marks, distinct differences are automatically at least 1 apart, so every Golomb ruler is a real 1-separated ruler and GR(n)≤GZ(n)G_R(n) \le G_Z(n). The question is whether real marks can ever do better. The same relaxation of the Erdős distinct subset sums problem was studied in [12], where the real and integer optima agree for n≤8n \le8. For rulers the structure is simpler, because every condition involves only two differences.

Results. Real and integer optima agree for every n≤10(Theorem1)n \le10 (Theorem 1). The proof is a certified branch-and-bound (Section 3). For n≤7n \le7 an exhaustive enumeration of all chamber vertices gives an independent proof, identifies all shortest real rulers (Theorem 2), and shows the first non-integral vertices. Section 6 shows that most of these are shortest points of their chambers, with a short certificate for one of them (Proposition 1), and gives a twelve-mark example from Singer's construction (Proposition 2). So chamber optima can be non-integral even where the global optimum is integral, and Section 6 also shows that no universal floor/ceiling rounding explains the integral optima. Section 7 shows that every Singer ruler for a prime power up to 103 is the only shortest point of its chamber, and conjectures this in general. Section 8 proves n(n−1)2≤GR(n)n(\sqrt{n}-1)^2 \le G_{\mathrm{R}}(n) for all nn (Theorem 3), so that GR(n)∼GZ(n)∼n2G_{\mathrm{R}}(n) \sim G_{\mathrm{Z}}(n) \sim n^2.

Chambers, vertices and valid inequalities

Write k=n−1k=n-1 and use the gaps gt=xt+1−xtg_t=x_{t+1}-x_t as coordinates. Every difference xj−xix_j-x_i equals 1I⋅g\mathbf{1}_I\cdot g for the interval I={i,…,j−1}I=\{i,\ldots,j-1\}, where 1I\mathbf{1}_I is its indicator vector. Hence every condition of Definition 1 reads ∣e⋅g∣≥1|e\cdot g|\ge1 for ee in the relation set RnR_n: the interval indicators 1I\mathbf{1}_I (among them the unit vectors, giving gt≥1g_t\ge1) and the differences 1I−1J\mathbf{1}_I-\mathbf{1}_J of two distinct intervals, each normalized so that its first nonzero entry is +1+1, with repetitions removed. ∣Rn∣=4,12,30,65,126|R_n|=4, 12, 30, 65, 126 for n=3,…,7n=3,\ldots,7.

For a sign vector σ\sigma on RnR_n with σe=+1\sigma_e=+1 on the unit vectors, the chamber PσP_\sigma is the set of gg with σee⋅g≥1\sigma_e e\cdot g\ge1 for all e∈Rne\in R_n. The real 1-separated rulers form the disjoint union of the nonempty chambers. A chamber corresponds to a choice of the order of all differences, which is a combinatorial type of real Golomb ruler in the sense of Beck, Bogart and Pham [2].

Lemma 1 (vertices). GR(n)G_{\mathrm{R}}(n) is attained. It is the least total length g1+⋯+gkg_1+\cdots+g_k over the finite set of points gg such that (i) g=M−1sg=M^{-1}s for a k×kk\times k matrix MM whose rows are linearly independent elements of RnR_n and a sign vector s∈{−1,1}ks\in\{-1,1\}^k, and (ii) gt≥1g_t\ge1 for all tt and ∣e⋅g∣≥1|e\cdot g|\ge1 for all e∈Rne\in R_n.

Proof. A nonempty chamber is a polyhedron contained in {g:g≥1}\{g:g\ge1\}. It contains no line, and the length is bounded below on it and strictly increasing along every recession direction. By the fundamental theorem of linear programming its minimum over the chamber is attained, at a vertex, where kk linearly independent defining inequalities hold with equality: e⋅g=σee\cdot g=\sigma_e for kk independent rows ee. Such a point has the form (i), and it satisfies (ii) because it lies in the chamber. Conversely, every point satisfying (ii) is a real 1-separated ruler. ■

By Cramer's rule ∣det⁡M∣⋅g|\det M|\cdot g is an integer vector. A feasible vertex is integral if gg is an integer vector; it is then an integer Golomb ruler.

Lemma 2 (packing). Any rr distinct differences of a real 1-separated ruler have sum at least 1+2+⋯+r=r(r+1)/21+2+\cdots+r=r(r+1)/2, because they are at least 1 and pairwise at least 1 apart. In particular the largest difference, xnx_n, is at least n(n−1)/2n(n-1)/2. Since {0,1}\{0,1\}, {0,1,3}\{0,1,3\} and {0,1,4,6}\{0,1,4,6\} are Golomb rulers, GR(n)=GZ(n)=n(n−1)/2G_{\mathrm{R}}(n)=G_{\mathrm{Z}}(n)=n(n-1)/2 for n≤4n\le4.

Lemma 3 (sub-rulers). For i<ji<j the marks xi,…,xjx_i,\ldots,x_j form, after translation, a real 1-separated ruler with m=j−i+1m=j-i+1 marks, so xj−xi≥GR(m)x_j-x_i\ge G_{\mathrm{R}}(m).

Lemma 4 (symmetry). The mirror image x↦xn−xx\mapsto x_n-x of a real 1-separated ruler is again one, of the same length, with the gaps in reverse order. The gaps g1g_1 and gkg_k (k≥2k\ge2) are two distinct differences, so ∣g1−gk∣≥1|g_1-g_k|\ge1. Hence a lower bound proved for all rulers with gk−g1≥1g_k-g_1\ge1 holds for all rulers.

The certified branch-and-bound

To prove GR(n)≥TG_{\mathrm{R}}(n)\ge T we search a binary tree. A node is described by its path, a list of branching rows σe⋅g≥1\sigma_e\cdot g\ge1 with e∈Rne\in R_n; the root has an empty path. At each node we solve the linear program: minimize g1+⋯+gkg_1+\cdots+g_k subject to the rows valid at the node, which are

  • ut\mathbf{u}_t: gt≥1g_t\ge1 (Definition 1);

  • sI\mathbf{s}_I: 1I⋅g≥L(m)\mathbf{1}_I\cdot g\ge L(m) for every interval II of mm marks with 3≤m≤n−13\le m\le n-1 (Lemma 3), where L(m)=m(m−1)/2L(m)=m(m-1)/2 for m≤4m\le4 (Lemma 2) and L(m)=GZ(m)L(m)=G_{\mathrm{Z}}(m) for 5≤m≤n−15\le m\le n-1, as certified by the proofs for smaller nn;

  • p\mathbf{p}: packing cuts ∑I∈S1I⋅g≥r(r+1)/2\sum_{I\in S}\mathbf{1}_I\cdot g\ge r(r+1)/2 for a set SS of rr distinct intervals (Lemma 2), added when the LP point violates one;

  • y\mathbf{y}: gk−g1≥1g_k-g_1\ge1 (Lemma 4);

  • bd\mathbf{b}_d: the branching rows of the path.

If the LP value is at least TT, the node is a leaf and receives a certificate: multipliers yi≥0y_i \ge0 with ∑yiai=(1,…,1)\sum y_i a_i = (1,\ldots,1) and ∑yibi≥T\sum y_i b_i \ge T for rows ai⋅g≥bia_i \cdot g \ge b_i valid at the node. For every point of the node, the length then equals ∑yiai⋅g≥∑yibi≥T\sum y_i a_i \cdot g \ge\sum y_i b_i \ge T. (An empty node would instead receive a Farkas certificate, ∑yiai=0\sum y_i a_i = 0 with ∑yibi>0\sum y_i b_i > 0; none was needed.) Otherwise we add a violated packing cut if there is one, and then branch on the relation e∈Rne \in R_n with the smallest ∣e⋅g∣|e \cdot g| at the LP point: the children add e⋅g≥1e \cdot g \ge1 and −e⋅g≥1-e \cdot g \ge1. Every ruler satisfies ∣e⋅g∣≥1|e \cdot g| \ge1, so the two children cover the node. If the LP point satisfied every relation, it would be a real ruler shorter than TT, and the proof would fail.

The LP is solved in floating point by HiGHS 1.15.1 [17]. The certificates are exact: the kk rows that are tight in HiGHS's optimal basis are taken, and the multipliers are obtained from them by solving a k×kk \times k linear system in rational arithmetic. They are kept only if they are nonnegative and give ∑yibi≥T\sum y_i b_i \ge T exactly. Floating point therefore only guides the search; the proof rests on the certificates.

The checker (Real_Golomb_rulers_check.py) uses only the Python standard library and exact fractions. For a proof file it recomputes RnR_n and the intervals from nn and compares them with the file. It checks that the tree has one root, that every internal node has exactly the two children e⋅g≥1e \cdot g \ge1 and −e⋅g≥1-e \cdot g \ge1 for a relation e∈Rne \in R_n, and that every leaf has a valid certificate. It checks that every row used is one of the kinds listed above, with an index in range, and with each packing cut and sub-ruler bound within what Lemmas 2 and 3 allow. Sub-ruler bounds for m≥5m \ge5 are accepted only together with the proof for mm, which is checked recursively. Finally, it checks an optimal integer ruler for the upper bound. Checking the proof for n=10n = 10, with its whole chain for n=5,…,9n = 5,\ldots,9, takes about 3 seconds.

Tests. With the target raised by 1 (T=GZ(n)+1T = G_Z(n) + 1), the search must fail. For n=5,…,8n = 5,\ldots,8 it does: it finds exactly the optimal integer rulers, one of each mirror pair. The checker rejects a proof with open leaves, a proof in which one multiplier was changed, and proofs with malformed or out-of-range row references (for example a row gt≥1g_t \ge1 with tt outside 1,…,k1,\ldots,k, which would read 0≥10 \ge1). For n≤7n \le7 the result agrees with the enumeration of Section 5.

Results

Theorem 1. For 2≤n≤102 \le n \le10, GR(n)=GZ(n)G_R(n) = G_Z(n), that is, 1, 3, 6, 11, 17, 25, 34, 44, 55.

Proof. For n≤4n \le4 this is Lemma 2. For 5≤n≤105 \le n \le10 the proof files of Table 1 give GR(n)≥GZ(n)G_R(n) \ge G_Z(n). They are built in the order n=5,6,…,10n = 5, 6,\ldots,10, each using the bounds for smaller mm as sub-ruler rows. The upper bound comes from optimal integer rulers {0,1,4,9,11}\{0, 1, 4, 9, 11\}, {0,1,4,10,12,17}\{0, 1, 4, 10, 12, 17\}, {0,1,4,10,18,23,25}\{0, 1, 4, 10, 18, 23, 25\}, {0,1,4,9,15,22,32,34}\{0, 1, 4, 9, 15, 22, 32, 34\}, {0,1,5,12,25,27,35,41,44}\{0, 1, 5, 12, 25, 27, 35, 41, 44\} and {0,1,6,10,23,26,34,41,53,55}\{0, 1, 6, 10, 23, 26, 34, 41, 53, 55\}.

nntargetnodesleavespacking cutsmax depthtimeproof file
511116740.01 s2.5 KB
61747241660.03 s8.7 KB
72564332255150.4 s94 KB
8343,8231,912128233.3 s0.57 MB
94415,9297,9652983219 s2.5 MB
105518,4259,2133322933 s3.1 MB

Table 1. The certified proofs of GR(n)≥GZ(n)G_R(n) \ge G_Z(n), each run on one process of a laptop (Intel Core Ultra 7 155U).

The proof is computer-assisted. Every step can be checked with the published checker, without the LP solver.

Exhaustive enumeration of the vertices for n≤7n \le7

Lemma 1 also gives a direct method. Enumerate every kk-element subset of Rn\mathbb{R}_n. For each subset, fraction-free Gauss–Jordan elimination in exact integer arithmetic gives D=±det⁡MD = \pm\det M and A=D⋅M−1A = D\cdot M^{-1}; every division is checked to be exact, and M⋅A=D⋅IM\cdot A = D\cdot I is checked afterwards. All integers involved are small: in Bareiss's fraction-free elimination [1] every intermediate entry is, up to sign, a minor of [M∣I][M \mid I], hence by Hadamard's inequality at most 63=2166^3 = 216 in absolute value for n=7n = 7, so no numerator exceeds 2⋅2162<1052\cdot216^2 < 10^5 and the 64-bit arithmetic cannot overflow; the floating-point product AsA s has integer partial sums below 400, so it is exact. For each sign vector ss, keep the point g=As/Dg = A s / D if it satisfies (ii). We ran this in pure Python for n≤6n \le6 and in a vectorized numpy version for n=7n = 7: 4,925,156,775 subsets, 6.3 hours on 10 worker processes. The numpy version reproduces every count of the Python version for n=5n = 5 and 6.

Every feasible vertex lies in exactly one chamber, and every chamber contains a feasible vertex (Lemma 1). The vertices found meet 2, 10, 114, 2,608 and 107,498 chambers for n=3,…,7n = 3, \ldots, 7. These are exactly the numbers of combinatorially different real Golomb rulers listed by Beck, Bogart and Pham [2 Section 5], which also form OEIS A237749 [13]. So the enumeration met every chamber.

nn∣Rn∣|R_n|subsetsnonsingularsolutions by ∣det⁡M∣|\det M|feasible verticeschambersnon-integral
34661: 2220
4122201891: 1010100
53027,40521,0351: 1761181140
6658,259,8885,903,7101: 6,296; 2: 23,1442,6080
71264,925,156,7753,365,649,1241: 425,802; 2: 1,378; 3: 2165,522107,49884

Table 2. The enumeration. “Solutions” are the (subset, sign) pairs that give a feasible vertex, by ∣det⁡M∣|\det M|. “Chambers” is the number of distinct chambers containing a feasible vertex.

Theorem 2. For n=5,6,7n = 5, 6, 7 the real 1-separated rulers of length GZ(n)G_{\mathbb{Z}}(n) are exactly the optimal Golomb rulers below and their mirror images:

  • n=5n = 5: {0,1,4,9,11}\{0, 1, 4, 9, 11\} and {0,2,7,8,11}\{0, 2, 7, 8, 11\};

  • n=6n = 6: {0,1,4,10,12,17}\{0, 1, 4, 10, 12, 17\}, {0,1,4,10,15,17}\{0, 1, 4, 10, 15, 17\}, {0,1,8,11,13,17}\{0, 1, 8, 11, 13, 17\} and {0,1,8,12,14,17}\{0, 1, 8, 12, 14, 17\};

  • n=7n = 7: {0,1,4,10,18,23,25}\{0, 1, 4, 10, 18, 23, 25\}, {0,1,7,11,20,23,25}\{0, 1, 7, 11, 20, 23, 25\}, {0,1,11,16,19,23,25}\{0, 1, 11, 16, 19, 23, 25\}, {0,2,3,10,16,21,25}\{0, 2, 3, 10, 16, 21, 25\} and {0,2,7,13,21,22,25}\{0, 2, 7, 13, 21, 22, 25\}.

Proof. The enumeration finds the least length over the finite set of Lemma 1, attained only at these rulers and their mirror images (4, 8 and 10 vertices). They lie in pairwise different chambers. In each chamber the length is minimized on a bounded face, the convex hull of the optimal vertices of that chamber, so each of these chambers has a unique shortest ruler, and no other real ruler has length GZ(n)G_{\mathbb{Z}}(n). The next shortest feasible vertices have lengths 12, 18 and 26. ■

Non-integral vertices and optima

Up to n=6n = 6 every feasible vertex is integral. At n=6n = 6, two solutions come from subsets with ∣det⁡M∣=2|\det M| = 2, but their vertices are integral and are also reached by subsets with ∣det⁡M∣=1|\det M| = 1. At n=7n = 7 the first non-integral feasible vertices appear: 84 of them, all half-integral. Two solutions come from subsets with ∣det⁡M∣=3|\det M| = 3, but no vertex has denominator 3. The shortest non-integral vertex has length 33, far above $G_{\mathbb{Z}}(7) = 25:

0,7/2,6,11,20,21,330, 7/2, 6, 11, 20, 21, 33, with differences 1,5/2,7/2,5,6,15/2,9,10,11,12,13,14,15,33/2,35/2,20,21,22,27,59/2,331, 5/2, 7/2, 5, 6, 15/2, 9, 10, 11, 12, 13, 14, 15, 33/2, 35/2, 20, 21, 22, 27, 59/2, 33, which are pairwise at least 1 apart. So the simple route to GR(n)=GZ(n)G_{\mathrm{R}}(n)=G_{\mathrm{Z}}(n) for all nn, “every vertex is integral”, fails. A sharper question is whether a non-integral vertex can be the shortest point of its chamber. For each of the 84 vertices we solved the linear program of its chamber and recorded an exact certificate. For 80 of them a multiplier vector y≥0\mathbf{y}\ge0 with ∑yiai=(1,…,1)\sum y_i\mathbf{a}_i=(1,\ldots,1) over rows of the chamber has ∑yi\sum y_i equal to the length of the vertex, so the vertex is a shortest point of its chamber. For 40 of these the rows with yi>0y_i>0 have rank 6, so the vertex is the only shortest point; for the other 40 a second point of the chamber with the same length is given. Each of the remaining 4 comes with a shorter point of its chamber (Table 3). These verdicts do not depend on the completeness of the enumeration; only the list of 84 vertices does.

the vertex isverticesshortest of them
the only shortest point of its chamber4042
a shortest point, not the only one4033
not a shortest point438

Table 3. The chambers of the 84 non-integral vertices at n=7n=7.

So non-integral chamber optima occur already at n=7n=7, the first nn with non-integral vertices, although GR(7)=25G_{\mathrm{R}}(7)=25 is attained only at integer rulers (Theorem 2). The shortest of them, 0,7/2,6,11,20,21,330, 7/2, 6, 11, 20, 21, 33, shares the optimal face of its chamber with the integer ruler {0,4,6,11,20,21,33}\{0, 4, 6, 11, 20, 21, 33\}. The same happens for separated subset sums [12]: some chambers there have non-integral optimal vertices, but none beats the integer optimum for n≤8n\le8. The shortest unique example has a short certificate.

Proposition 1 (seven marks). The real 1-separated ruler P=0,9,14,33/2,20,32,42P=0, 9, 14, 33/2, 20, 32, 42 is the only shortest point of its chamber.

Proof. The 21 differences of PP are 5/2,7/2,5,6,15/2,9,10,11,12,14,31/2,33/2,18,20,22,23,51/2,28,32,33,425/2, 7/2, 5, 6, 15/2, 9, 10, 11, 12, 14, 31/2, 33/2, 18, 20, 22, 23, 51/2, 28, 32, 33, 42. They are at least 1 and pairwise at least 1 apart, so PP lies in its chamber. Table 4 lists six rows of the chamber that are tight at PP, with multipliers 8, 4, 7, 6, 9, 8. Their weighted sum is g1+…+g6≥42g_1+\ldots+g_6\ge42, so no point of the chamber is shorter than 42, and a point of length 42 satisfies the six rows with equality. The six rows have determinant 2, so that point is PP. ■

row of the chambermultiplierdifferences at PP
−g3+g4≥1-g_3+g_4\ge185/2→7/25/2\to7/2
−g2+g3+g4≥1-g_2+g_3+g_4\ge145→65\to6
−g1+g6≥1-g_1+g_6\ge179→109\to10
g2+g3+g4−g6≥1g_2+g_3+g_4-g_6\ge1610→1110\to11
−g2−g3−g4+g5≥1-g_2-g_3-g_4+g_5\ge1911→1211\to12
g1+g2+g3−g4−g5≥1g_1+g_2+g_3-g_4-g_5\ge1831/2→33/231/2\to33/2

Table 4. The certificate of Proposition 1. Each row says that two differences that are consecutive in the order of PP differ by at least 1; the last column gives their values at PP.

With twelve marks there is an example from Singer's construction.

Proposition 2 (twelve marks). Let X={0,4,24,27,67,77,86,88,103,119,125,132}X=\{0, 4, 24, 27, 67, 77, 86, 88, 103, 119, 125, 132\}, a Golomb ruler with n=12n=12 marks. The only shortest point of its chamber is the half-integral ruler P=0,4,22,25,123/2,141/2,157/2,161/2,94,217/2,114,121P=0, 4, 22, 25, 123/2, 141/2, 157/2, 161/2, 94, 217/2, 114, 121, of length 121.

Proof. Let d(1)<d(2)<…<d(66)d_{(1)}<d_{(2)}<\ldots<d_{(66)} be the differences in the order they have in XX. The chamber of XX is the set of gg with d(1)(g)≥1d_{(1)}(g)\ge1 and d(r+1)(g)−d(r)(g)≥1d_{(r+1)}(g)-d_{(r)}(g)\ge1 for r=1,…,65r=1,\ldots,65; these rows imply all others. The differences of PP come in the same order as those of XX and are pairwise at least 1 apart, so PP lies in the chamber. Exactly 24 rows are tight at P. Table 5 lists them with multipliers yi≥1/2y_i \ge1/2, for which ∑yiai=(1,…,1)\sum y_i a_i = (1, \ldots, 1) and ∑yi=121\sum y_i = 121 in exact arithmetic. Hence every point gg of the chamber has length ∑yiai⋅g≥∑yi=121\sum y_i a_i \cdot g \ge\sum y_i = 121, with equality only if all 24 rows are tight at gg. These rows have rank 11, so g=Pg = P. ■\blacksquare

in Xin Pyin Xin Py
2 → 32 → 325/223 → 2421 → 221/2
3 → 43 → 41/229 → 3127 → 281/2
7 → 97 → 819/236 → 3765/2 → 67/21/2
9 → 108 → 911/239 → 4071/2 → 73/225/2
10 → 119 → 101/243 → 4479/2 → 81/223/2
13 → 1525/2 → 27/21/246 → 4885/2 → 87/21/2
15 → 1627/2 → 29/257/258 → 59105/2 → 107/21/2
16 → 1729/2 → 31/259/261 → 62111/2 → 113/21/2
19 → 2017 → 181/262 → 63113/2 → 115/21/2
20 → 2118 → 191/263 → 64115/2 → 117/21/2
21 → 2219 → 207/264 → 65117/2 → 119/21/2
22 → 2320 → 211/298 → 9989 → 901/2

Table 5. The 24 rows tight at P in Proposition 2. Each row says that two differences that are consecutive in the order of X differ by at least 1. It is given by the two differences in X and in P, and by its multiplier y.

X is a cut of a Singer perfect difference set modulo 133 [16], cut at a gap that is not the largest; it was found while testing whether Singer rulers are the shortest points of their chambers. Its mirror image gives the mirror case. Both examples are far above the integer optimum (42 against GZ(7)=25G_Z(7) = 25, and 121 against GZ(12)=85G_Z(12) = 85), so they do not bear on Theorem 1.

Remark (rounding). Simple rounding does not account for the integral global optima. Rounding each of the five half-integral marks of P in Proposition 2 to its floor or its ceiling never gives a Golomb ruler of length at most 121. At n=14n = 14, the half-integral real 1-separated ruler

0,3,55/2,48,57,58,90,104,279/2,283/2,157,163,168,176,0, 3, 55/2, 48, 57, 58, 90, 104, 279/2, 283/2, 157, 163, 168, 176,

a shortest point of the chamber of another Singer cut, is not even within 1 of an integer Golomb ruler of length at most 176: no such ruler has every mark between the floor of the corresponding mark minus 1 and its ceiling plus 1. Among 1,936 non-integral chamber optima and vertices for n≤14n \le14 (the 84 vertices of Table 3, four minima from the Singer test of § 7, and chamber optima found by a walk through neighbouring chambers), rounding to floors and ceilings fails for 1,050. These examples rule out a universal length-nonincreasing floor/ceiling rounding procedure, even one that may move each mark one step further.

Singer rulers

For a prime power mm, Singer [16] constructs a set D of m+1m + 1 residues modulo q=m2+m+1q = m^2 + m + 1 whose differences cover every non-zero residue exactly once, a perfect difference set; so does every multiple t⋅Dt \cdot D with gcd⁡(t,q)=1\gcd(t, q) = 1. Cutting the circle Z/qZ\mathbb{Z}/q\mathbb{Z} at a gap between two consecutive elements of t⋅Dt \cdot D and reading the elements as integers in [0,q)[0, q) gives a Golomb ruler with n=m+1n = m + 1 marks, shortest when the cut is at the largest gap. We call these rulers, cut at the largest gap, Singer rulers. The shortest Singer ruler for each mm has length GZ(n)G_Z(n) for n=3,4,5,6,10,12,14,18,20,24,26n = 3, 4, 5, 6, 10, 12, 14, 18, 20, 24, 26 and 28, that is, for every n≤28n \le28 with n−1n - 1 a prime power except n=8,9n = 8, 9 and 17, where it is longer by 1, 1 and 2. The ruler of Theorem 1 for n=10n = 10 is itself a perfect difference set modulo 91.

Computation. For every prime power m≤103m \le103 (37 values of mm, up to 104 marks) and every multiplier tt, we solved the linear program of the chamber of the Singer ruler and certified the result exactly as in § 6: in each case a multiplier vector yy with ∑yiai=(1,…,1)\sum y_i a_i = (1,\ldots,1) and ∑yi\sum y_i equal to the length, positive on rows of rank n−1n-1. So each of these 24,450 distinct rulers is the only shortest point of its own chamber, including those for n=8n=8, 9 and 17, which are not globally optimal. For m≤47m \le47 we also tested the cuts at all other gaps (116,868 rulers in all), again with every verdict certified exactly: from m=19m=19 on each of them is the only shortest point of its chamber, while for m≤17m \le17 there are 396 that are not shortest points and 18 that are shortest but not the only one, each with an exact second point of the same length. Proposition 2 comes from one of these.

Conjecture. For every prime power mm, every Singer ruler is the only shortest point of its chamber.

Chamber optimality is local and does not bound GR(n)G_{\mathrm R}(n) by itself. For the analogous relaxation of distinct subset sums, the Conway–Guy and Bohman sets have structured dual certificates valid for all nn [12]; a certificate of that kind for Singer rulers, built from the cyclic structure of DD, would prove the conjecture.

Bounds for all n

Theorem 3. For every n≥2n \ge2, n(n−1)2=n2−2n3/2+n≤GR(n)≤GZ(n)≤n2+o(n2)n(\sqrt{n}-1)^2 = n^2 - 2n^{3/2} + n \le G_{\mathrm R}(n) \le G_{\mathbb Z}(n) \le n^2 + o(n^2). In particular GR(n)∼GZ(n)∼n2G_{\mathrm R}(n) \sim G_{\mathbb Z}(n) \sim n^2.

Proof. Let 0=x1<⋯<xn=L0 = x_1 < \cdots< x_n = L be a real 1-separated ruler, fix u>0u > 0, and for real tt let k(t)k(t) be the number of marks in [t,t+u)[t,t+u). Then k(t)=0k(t)=0 outside an interval of length L+uL+u, and ∫k(t) dt=nu\int k(t)\,\mathrm{d}t=nu. Two marks at distance dd both lie in [t,t+u)[t,t+u) for a set of tt of length max⁡(0,u−d)\max(0,u-d), so ∫k(t)(k(t)−1)/2 dt\int k(t)(k(t)-1)/2\,\mathrm{d}t is the sum of max⁡(0,u−d)\max(0,u-d) over the n(n−1)/2n(n-1)/2 differences dd. These are at least 1 and pairwise at least 1 apart, so the rr-th smallest is at least rr, and the sum is at most ∑r≥1max⁡(0,u−r)≤u2/2\sum_{r\ge1}\max(0,u-r)\le u^2/2. By the Cauchy–Schwarz inequality ∫k(t)2 dt≥(nu)2/(L+u)\int k(t)^2\,\mathrm{d}t\ge(nu)^2/(L+u). Hence n2u2/(L+u)−nu≤u2n^2u^2/(L+u)-nu\le u^2, that is, L≥n2u/(n+u)−uL\ge n^2u/(n+u)-u, and the choice u=n3/2−nu=n^{3/2}-n gives L≥n2−2n3/2+nL\ge n^2-2n^{3/2}+n. For the upper bound let pp be the least prime with p≥n−1p\ge n-1. A Singer set modulo p2+p+1p^2+p+1 has p+1≥np+1\ge n elements whose differences are distinct even modulo p2+p+1p^2+p+1, so any nn of them, read as integers in [0,p2+p][0,p^2+p], form a Golomb ruler of length at most p2+pp^2+p. By the prime number theorem p=n+o(n)p=n+o(n). ■

The lower bound is the counting argument of Erdős and Turán [7] for Sidon sets. It uses only that the differences are at least 1 apart, so it applies to real rulers unchanged; no bound of this counting kind can tell GRG_{\mathrm R} from GZG_{\mathbb Z}. Theorem 3 gives GZ(n)−GR(n)=o(n2)G_{\mathbb Z}(n)-G_{\mathrm R}(n)=o(n^2); whether the difference is always 0 is the main open question.

Related work

Beck, Bogart and Pham [2] introduced real Golomb rulers and their combinatorial types in order to count integer rulers with Ehrhart theory for inside-out polytopes; Bogart and Cuéllar [3] extended this to generalized rulers. Neither paper studies the separated minimum GR(n)G_{\mathrm R}(n). Kocuk and van Hoeve [8] compare integer, constraint and quadratic programming methods for certifying optimal integer rulers, up to 14 marks. They make one of their models exact by branching on dij≤dkl−1d_{ij}\le d_{kl}-1 or dij≥dkl+1d_{ij}\ge d_{kl}+1, the dichotomy as our branching, but inside an integer model with integer bounds. Their bounds dij≥Gi+1−1d_{ij}\ge G_{i+1}-1 are the integer counterpart of our sub-ruler rows. The linear-programming lower bounds of Lorentzen and Nilsen [9] and others, shown to coincide by Meyer and Jaumard [10], rest on packing inequalities like those of Lemma 2, which also hold for real 1-separated rulers. Duxbury, Lavor and Salles-Neto [6] propose a different continuous model: the marks stay at integer positions, and the 0–1 variables that say which positions carry a mark are relaxed to [0,1][0,1]. They conjectured that this non-convex model is exact, on evidence from a local solver; Ouzia [14] presents a proof of the conjecture and corrects the outputs of their greedy heuristic. In that model the marks remain at integer positions, so the question does not bear on GR(n)G_{\mathrm R}(n). Nathanson [11] bounds the size of integer Sidon sets whose sumset is Δ\Delta-separated, for a positive integer Δ\Delta. The conditions of Definition 1 say exactly that the sums xi+xjx_i + x_j (i≤ji \le j) are pairwise at least 1 apart, so such a set with least element 0, divided by Δ\Delta, is a real 1-separated ruler with marks in (1/Δ)Z(1/\Delta)\mathbb{Z}, and conversely. Let DΔ(n)D_\Delta(n) be the least largest element of such a set with nn elements. Since GR(n)G_\mathrm{R}(n) is attained at a rational point (Lemma 1), GR(n)G_\mathrm{R}(n) is the minimum of DΔ(n)/ΔD_\Delta(n)/\Delta over the positive integers Δ\Delta, and GR(n)=GZ(n)G_\mathrm{R}(n) = G_\mathrm{Z}(n) says exactly that DΔ(n)=Δ⋅GZ(n)D_\Delta(n) = \Delta\cdot G_\mathrm{Z}(n) for every positive integer Δ\Delta. We found no earlier study of GR(n)G_\mathrm{R}(n) itself.

Open problems

  • Is GR(n)=GZ(n)G_\mathrm{R}(n) = G_\mathrm{Z}(n) for every nn? Theorem 3 gives GR(n)∼GZ(n)G_\mathrm{R}(n) \sim G_\mathrm{Z}(n). A first nn with GR(n)<GZ(n)G_\mathrm{R}(n) < G_\mathrm{Z}(n) would need a non-integral chamber optimum below GZ(n)G_\mathrm{Z}(n), and by the remark of § 6 no universal floor/ceiling rounding can rule this out.

  • n=11n = 11 and 12. Random-dive estimates of the tree size suggest about 33–7⋅1067\cdot10^6 nodes for n=11n = 11 and 0.80.8–1.4⋅1071.4\cdot10^7 for n=12n = 12, that is, hours on one process; we have not run them.

  • Uniqueness for n=8n = 8, 9, 10: are the shortest real rulers again exactly the optimal integer rulers? The proofs of Theorem 1 give only the length.

  • Non-integral chamber optima exist from n=7n = 7 on (§ 6), yet no global optimum found so far is non-integral. What keeps them away from the optimum? How close to GZ(n)G_\mathrm{Z}(n) can a non-integral chamber optimum come? At n=7n = 7 the shortest has length 33, against GZ(7)=25G_\mathrm{Z}(7) = 25.

  • Prove the conjecture of § 7 for all prime powers, for instance by structured dual certificates as for the Conway–Guy and Bohman sets in [12]; and ask the same for the rulers of Bose [4] and Ruzsa [15].

Data and code

The Zenodo record of this note, doi:10.5281/zenodo.23843508 (https://doi.org/10.5281/zenodo.23843508, which always resolves to the latest version), contains the archive Real_Golomb_rulers_code_data.zip, with these parts and a list of SHA-256 checksums:

  • the branch-and-bound (Real_Golomb_rulers_bnb.py, needs numpy and highspy);

  • the checker (Real_Golomb_rulers_check.py);

  • the six proof files for n=5n = 5, …, 10 (data/bnb/, JSON lines);

  • the exact check of Propositions 1 and 2 and of the remark of § 6 (Real_Golomb_rulers_propositions_check.py), which rebuilds the chambers, checks every entry of Tables 4 and 5, and searches all the roundings of the remark;

  • the certificates behind Table 3 (data/n7_nonintegral_chambers.json) and their checker (Real_Golomb_rulers_n7_chambers_check.py), which also recomputes the 84 vertices from the enumeration output;

  • the Singer chamber test of § 7 (Real_Golomb_rulers_singer_chambers.py, needs numpy and highspy) and the rounding search behind the remark of § 6 (Real_Golomb_rulers_rounding.py), with their outputs (data/singer_chambers/, data/rounding/);

  • the exact certificates for the 258 Singer chamber verdicts whose uniqueness the first run decided only in floating point (data/singer_chambers/recheck_2026-11-17.json), the program that produced them (Real_Golomb_rulers_singer_recheck.py, needs numpy and highspy) and their checker (Real_Golomb_rulers_singer_recheck_check.py);

  • the vertex enumeration in pure Python and numpy, with a C version that was not used;

  • all enumeration outputs (data/real_golomb_runs/).

To check Theorem 1 for n=10n = 10: `python -I Real_Golomb_rulers_check.py ../data/bnb/proof_n10_T55.json with --dep m:../data/bnb/proof_n<m>_T<G_Z(m)>.json for m = 5, ..., 9 and --upper 0,1,6,10,23,26,34,41,53,55. To check Propositions 1 and 2, the remark of Section 6 and Table 3: python -I Real_Golomb_rulers_propositions_check.py and python -I Real_Golomb_rulers_n7_chambers_check.py; for the certificates of Section 7: python -I Real_Golomb_rulers_singer_recheck_check.py. The four checkers use only the Python standard library, and every check raises an error explicitly, so they also check under python -O. The archive README gives the exact commands. License: CC BY 4.0.

Acknowledgements

The research was directed by the author, who used Claude (Anthropic) for the programs and a draft of the paper; the author checked the results.

References

  1. [1]E. H. Bareiss, Sylvester's identity and multistep integer-preserving Gaussian elimination, Math. Comp. 22 (1968), 565–578.DOI
  2. [2]M. Beck, T. Bogart, T. Pham, Enumeration of Golomb rulers and acyclic orientations of mixed graphs, Electron. J. Combin. 19(3) (2012), P42; arXiv:1110.6154.arxiv.org/abs/1110.6154
  3. [3]T. Bogart, D. F. Cuéllar, An Ehrhart theoretic approach to generalized Golomb rulers, arXiv:2308.11118 (2023).arxiv.org/abs/2308.11118
  4. [4]R. C. Bose, An affine analogue of Singer's theorem, J. Indian Math. Soc. (N.S.) 6 (1942), 1–15.DOI
  5. [5]distributed.net, Project OGR (optimal Golomb rulers), https://www.distributed.net.
  6. [6]P. Duxbury, C. Lavor, L. L. de Salles-Neto, A conjecture on a continuous optimization model for the Golomb ruler problem, RAIRO Oper. Res. 55 (2021), 2241–2246, doi:10.1051/ro/2021103.DOI
  7. [7]P. Erdős, P. Turán, On a problem of Sidon in additive number theory, and on some related problems, J. London Math. Soc. 16 (1941), 212–215.
  8. [8]B. Kocuk, W.-J. van Hoeve, A computational comparison of optimization methods for the Golomb ruler problem, in: CPAIOR 2019, Lecture Notes in Computer Science, Springer (2019), 409–425, doi:10.1007/978-3-030-19212-9_27.DOI
  9. [9]R. Lorentzen, R. Nilsen, Application of linear programming to the optimal difference triangle set problem, IEEE Trans. Inform. Theory 37 (1991), 1486–1488.DOI
  10. [10]C. Meyer, B. Jaumard, Equivalence of some LP-based lower bounds for the Golomb ruler problem, Discrete Appl. Math. 154(1) (2006), 120–144.
  11. [11]M. B. Nathanson, Sidon sets with Δ-separated sumsets in additive number theory, arXiv:2608.07416 (2026).arxiv.org/abs/2608.07416
  12. [12]E. Notik, Positive dual certificates for real separated subset sums: chamber optimality of the Conway–Guy and Bohman sets, and exact values up to eight, arXiv:2611.17360 (2026); also doi:10.5281/zenodo.23399289.DOI
  13. [13]The On-Line Encyclopedia of Integer Sequences, sequences A003022 and A237749, https://oeis.org.
  14. [14]H. Ouzia, Partial reformulation-linearization based optimization models for the Golomb ruler problem, RAIRO Oper. Res. 58(4) (2024), 3171–3188, doi:10.1051/ro/2024121.DOI
  15. [15]I. Z. Ruzsa, Solving a linear equation in a set of integers, Acta Arith. 65 (1993), 259–282, doi:10.4064/aa-65-3-259-282.
  16. [16]J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43 (1938), 377–385, doi:10.1090/S0002-9947-1938-1501951-4.DOI
  17. [17]HiGHS: high-performance software for linear optimization, version 1.15.1, https://highs.dev.

Paper details

vlnc:W_fj3uvtqv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude (Anthropic)

View statement
Looking for related papers…
Contents