arxiv: 2605.14229 · v1 · pith:JDLRTLVBnew · submitted 2026-05-14 · 🧮 math.CO

Optimal Diameters of High Multiplicity g-Golomb Rulers

Aditya Gupta , Kevin O'Bryant This is my paper

Pith reviewed 2026-05-15 02:53 UTC · model grok-4.3

classification 🧮 math.CO

keywords g-Golomb rulersLM rulersdiameter boundsSidon setsB2 setsdifference setscombinatorial number theorymultiplicity

0 comments

The pith

For g at least roughly 1.75 times b to the 3/2 power, the shortest g-Golomb ruler with g plus b marks has diameter exactly g plus 2b minus 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an exact formula for the minimal diameter G(g, g + b) of g-Golomb rulers once g grows large enough relative to the excess number of marks b. It does so by deriving a lower bound from the arithmetic constraints on integers that cannot belong to such a ruler, which leads to the introduction of LM rulers where each distance d appears at most d minus 1 times. The same technique yields matching upper and lower bounds on the minimal diameter L(n) of any n-element LM ruler. These results give precise constructions in the regime of high multiplicity, extending classical results on Sidon sets and B2-sets to the g-multiplicity case. Sharper numerical bounds are supplied for all b up to 18.

Core claim

We prove that for all b greater than or equal to 1, if g is at least 7/4 times (b to the 3/2 minus b) plus 1, then G(g, g + b) equals g + 2b - 2. The argument proceeds by showing that the complement of any g-Golomb ruler must satisfy a strong arithmetic property, which in turn implies that the ruler's diameter is at least that of the shortest LM ruler; explicit constructions then match this lower bound under the stated hypothesis on g.

What carries the argument

LM rulers: an auxiliary class of integer sets in which every distance d occurs as a difference at most d-1 times, used to force the diameter lower bound on g-Golomb rulers via the arithmetic structure of their complements.

If this is right

G(g, g + b) is known exactly for all sufficiently large g in terms of b.
The minimal diameter of an n-element LM ruler satisfies the explicit sandwich sqrt(8/9)(n-1)^{3/2} less than or equal to L(n) less than or equal to 7/4 times ((n+1)^{3/2} minus (n+1)).
Sharper explicit values of G(g, g + b) hold for every b from 1 to 18.
Optimal g-Golomb rulers in the high-multiplicity regime can be built by taking the shortest LM ruler and adding a controlled number of extra marks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The LM-ruler lower-bound technique may extend to other multiplicity functions or to weighted difference sets.
Computational enumeration of small LM rulers could test how tight the sqrt(8/9) constant is for moderate n.
The exact diameter formula supplies a concrete benchmark for heuristic search algorithms that construct large Golomb rulers.

Load-bearing premise

The integers excluded from any g-Golomb ruler must obey an arithmetic property strong enough to guarantee that the ruler's diameter is at least the minimal diameter of an LM ruler.

What would settle it

Exhibit either a g-Golomb ruler with g + b marks whose diameter is strictly less than g + 2b - 2 for some g satisfying the given lower bound on g, or an n-element LM ruler whose diameter is smaller than sqrt(8/9) times (n-1) to the 3/2.

Figures

Figures reproduced from arXiv: 2605.14229 by Aditya Gupta, Kevin O'Bryant.

read the original abstract

A set $\cG$ of integers is called a $g$-Golomb ruler of length $n$ if the difference between any two distinct elements of $\cG $ is repeated at most $g$ times. If $g=1$, these are also called $B_2$-sets, Sidon sets, and Babcock sets. We define $G(g,n)$ to represent the minimum diameter of a $g$-Golomb Ruler. In this paper, we prove that for all $b\ge 1$, if $g \ge \frac{7}{4}\left(b^{3/2} -b\right)+1,$ then $G(g,g+b)=g+2b-2$. Sharper bounds are given for $b\le 18$. The main technique is through an arithmetic property of the integers that are \emph{not} in a $g$-Golomb ruler, leading us to introduce LM rulers, a new class of rulers where every distance $d$ occurs as a difference at most $d-1$ times. We show that the minimum diameter of an $n$-element LM ruler $L(n)$ is $\sqrt{8/9} \cdot (n-1)^{3/2} \le L(n) \le \frac{7}{4}\left((n+1)^{3/2}-(n+1)\right).$

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper pins down the exact value G(g, g+b) = g + 2b - 2 once g exceeds a threshold linear in b to the 3/2, via an explicit construction and a reduction to newly defined LM rulers.

read the letter

The main result is the equality G(g, g+b) = g + 2b - 2 for g ≥ (7/4)(b^{3/2} - b) + 1. They achieve this with a construction that hits the bound and a lower bound proof that reduces the problem to bounding the diameter of LM rulers. The construction side is explicit and works for all b. On the LM rulers, they define them so that each possible difference d appears at most d-1 times, which is a relaxation of the g=1 case but with a linear bound in d. The lower bound they give is sqrt(8/9) (n-1)^{3/2} and the upper is (7/4)((n+1)^{3/2} - (n+1)). These seem derived from counting arguments on the number of differences. What the paper does well is giving a clean threshold on g in terms of b and providing sharper bounds for small b up to 18. The introduction of the LM class is a reasonable way to handle the complement set. The soft spot is the step where they claim that the complement of a g-Golomb ruler with small diameter must be an LM ruler. This relies on the g-multiplicity condition forcing the missing distances to satisfy the d-1 bound. The abstract says it comes from an arithmetic property of the non-elements, but without the full details it's the part that could use more explanation to confirm it holds without additional assumptions on the ruler's structure. If the proof shows this inheritance directly, then the argument is fine; the stress test highlights this as the least routine part. Overall, the paper is for researchers in additive combinatorics who study variants of Sidon sets and Golomb rulers. It provides a concrete advance with explicit constants rather than asymptotic results. I would recommend sending it for peer review. The result is precise, the new definition is motivated, and the bounds are stated clearly enough to be checked.

Referee Report

1 major / 2 minor

Summary. The paper claims to prove that for all b≥1, if g ≥ (7/4)(b^{3/2} - b) +1, then G(g,g+b)=g+2b-2. It does so by providing an explicit construction achieving the diameter g+2b-2 and a matching lower bound derived from the complement of the ruler forming an LM ruler whose size and diameter contradict the upper bound L(m) ≤ (7/4)((m+1)^{3/2} - (m+1)). Bounds on the minimal diameter L(n) of n-element LM rulers are also established: √(8/9)·(n-1)^{3/2} ≤ L(n) ≤ (7/4)((n+1)^{3/2}-(n+1)). Sharper results are given for b≤18.

Significance. If the result holds, it determines the exact minimal diameter G(g,g+b) for g-Golomb rulers in the regime g ≳ b^{3/2}. This extends classical results on Sidon sets (g=1) to higher multiplicities with an explicit construction and a combinatorial lower-bound argument. The newly introduced LM rulers and their diameter bounds appear to be of independent interest in additive combinatorics. Credit is given for the parameter-free derivation of the bounds and the attempt to obtain an exact equality rather than an asymptotic statement.

major comments (1)

[Lower bound argument via LM rulers (complement construction)] The assertion that the complement of a g-Golomb ruler S with |S|=g+b and diameter D < g+2b-2 in [0,D] forms an LM ruler (each distance d appears at most d-1 times) is the load-bearing step for the lower bound. This inheritance from the g-multiplicity condition on differences in S to the (d-1)-multiplicity condition on the complement must be derived explicitly from the definitions; the current argument leaves this implication unexamined and it is not immediate.

minor comments (2)

[Abstract] The abstract sketches the technique via missing integers and LM rulers but does not indicate the section or equation where the complement-to-LM-ruler property is proved.
[LM ruler diameter bounds] The lower bound √(8/9)·(n-1)^{3/2} for L(n) should include a brief indication of the counting argument or inequality used to obtain it.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address the major comment below.

read point-by-point responses

Referee: The assertion that the complement of a g-Golomb ruler S with |S|=g+b and diameter D < g+2b-2 in [0,D] forms an LM ruler (each distance d appears at most d-1 times) is the load-bearing step for the lower bound. This inheritance from the g-multiplicity condition on differences in S to the (d-1)-multiplicity condition on the complement must be derived explicitly from the definitions; the current argument leaves this implication unexamined and it is not immediate.

Authors: We agree that the implication requires an explicit derivation from the definitions, as it is not immediate. In the revised manuscript we will insert a new lemma that derives the LM-ruler property of the complement directly: assuming S is a g-Golomb ruler of size g+b with diameter D < g+2b-2, we count the total number of ordered differences in [0,D] and use the g-multiplicity bound on S together with the exact size |S|=g+b to show that the complement C=[0,D]∖S satisfies that every distance d appears at most d-1 times. The argument proceeds by contradiction on the first violating distance and uses the interval structure of [0,D]. This addition will make the lower-bound argument fully rigorous while leaving the main theorems unchanged. revision: yes

Circularity Check

0 steps flagged

Derivation is self-contained combinatorial proof with no circular reductions

full rationale

The central result is obtained by an explicit construction achieving diameter g+2b-2 together with a matching lower bound proved by contradiction: a hypothetical g-Golomb ruler of smaller diameter has a complement that is shown (via direct arithmetic counting from the g-multiplicity definition) to be an LM ruler of size at least b whose diameter then exceeds the paper's independently established upper bound on L(m). Both the LM definition and the complement-inheritance argument are introduced and justified inside the paper from the given multiplicity conditions; no equation reduces to a quantity defined in terms of itself, no parameter is fitted and then relabeled as a prediction, and no load-bearing step relies on a self-citation chain. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The argument rests on the definition of g-Golomb rulers and the newly introduced LM rulers together with standard facts about integer differences; no numerical parameters are fitted to data and no new physical or mathematical entities beyond the defined ruler classes are postulated.

axioms (1)

standard math Standard arithmetic properties of differences in finite subsets of integers
Invoked when relating the missing integers to the multiplicity of differences in the ruler.

invented entities (1)

LM ruler no independent evidence
purpose: Auxiliary class of rulers in which each difference d occurs at most d-1 times, used to obtain the diameter lower bound for g-Golomb rulers
Newly defined in the paper to facilitate the proof; no independent existence proof or external verification is supplied beyond the definition itself.

pith-pipeline@v0.9.0 · 5555 in / 1432 out tokens · 44762 ms · 2026-05-15T02:53:21.968905+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

A set L of integers is an LM ruler if every positive integer d has at most d-1 representations as a difference of elements of L. ... diam(A) ≥ (2√2/3)(n-1)^{3/2}
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 4. If g ≥ L(b-1)+1, then G(g,g+b)=g+2b-2

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

[1]

M. D. Atkinson and A. Hassenklover,Sets of integers with distinct differences, Sch Comput. Sci. (Aug 1984). Rep. SCS-TR-63. 14

work page 1984
[2]

M. D. Atkinson, N. Santoro, and J. Urrutia,Integer Sets with Distinct Sums and Differences and Car- rier Frequency Assignments for Nonlinear Repeaters, IEEE Transactions on Communications34(June 1986), no. 6, 614–617, DOI unknown, available athttp://dl.comsoc.org/cocoon/comsoc/servlets/ GetPublication?id=150119

work page 1986
[3]

J´ ozsef Balogh, Zolt´ an F¨ uredi, and Souktik Roy,An upper bound on the size of Sidon sets, Amer. Math. Monthly130(2023), no. 5, 437–445, DOI 10.1080/00029890.2023.2176667.MR 4580380

work page doi:10.1080/00029890.2023.2176667.mr 2023
[4]

Martos, and Carlos A

Yadira Caicedo, Carlos A. Martos, and Carlos A. Trujillo,g-Golomb rulers, Rev. Integr. Temas Mat. 33(2015), no. 2, 161–172, DOI 10.18273/revint.v33n2-2015006 (English, with English and Spanish sum- maries).MR 3445964

work page doi:10.18273/revint.v33n2-2015006 2015
[5]

Carter, Z

D. Carter, Z. Hunter, and K. O’Bryant,On the diameter of finite Sidon sets, Acta Math. Hungar.175 (2025), no. 1, 108–126, DOI 10.1007/s10474-024-01499-8.MR 4880650

work page doi:10.1007/s10474-024-01499-8.mr 2025
[6]

Kevin O’Bryant,A complete annotated bibliography of work related to Sidon sequences, Electron. J. Combin.DS11(2004), 39.MR 4336213

work page 2004
[7]

Sloane and The OEIS Foundation Inc.,The on-line encyclopedia of integer sequences(2026),https: //oeis.org/

N. Sloane and The OEIS Foundation Inc.,The on-line encyclopedia of integer sequences(2026),https: //oeis.org/

work page 2026
[8]

2020Mathematics Subject Classification: Primary 05B10

Carlos Andres Martos Ojeda, David Fernando Daza Urbano, and Carlos Alberto Trujillo Solarte,Near- optimalg-Golomb rulers, IEEE Access9(2021), 65482–65489, DOI 10.1109/ACCESS.2021.3075877. 2020Mathematics Subject Classification: Primary 05B10. Secondary 11B13. Keywords:Sidon Set, Generalized Golomb Ruler,g-Golomb Ruler (Concerned with sequences) A392517, A...

work page doi:10.1109/access.2021.3075877 2021