Modular Constructions of g-Golomb Rulers

Aditya Gupta

Modular Constructions of g-Golomb Rulers

T0 review · 0 major / 5 minor · reviewed 2026-07-10 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A modular g-Golomb ruler forces a strictly larger cut than the average gap, tightening upper bounds on G(g,n) for four classical constructions.

desk verdict Solid incremental note: multiplicity forces a larger modular gap cut than the average, then ranks four classical families on a big grid. read the letter →

arxiv 2607.07931 v1 pith:U6T2WCC5 submitted 2026-07-08 math.CO math.NT

Aditya Gupta This is my paper · ORCID

classification math.COmath.NT MSC 05B1011B83

keywords g-GolombrulersmodularconstructionsrelativedifferencesetsSingerRuzsa–SpencePaleyquadraticresiduesgapextractionSidon

topics The Collatz Conjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

A g-Golomb ruler is a set of integers in which every positive difference appears at most g times. The shortest possible length of such a set with n marks is written G(g,n). Most good upper bounds come from modular constructions: marks placed on a circle that are later cut open into an ordinary line. Earlier work cut only at an average-sized empty gap. This paper observes that, because each gap length is itself a modular difference, no gap length can appear more than g times. That multiplicity constraint forces a larger guaranteed empty gap than the average alone, and therefore a shorter ordinary ruler. The improved extraction is applied to four classical modular sources—cyclic relative difference sets, Singer sets, Ruzsa–Spence rulers, and Paley quadratic residues—producing four competing families of upper bounds. A computation over a 500-by-500 grid of parameters shows which family wins most often and by how much.

What carries the argument

The gap-extraction lemma (Lemma 2): because no positive gap length can occur more than g times, the sum of the n gaps is maximized only when the lengths take the form g copies of each successive integer down from the maximum; rearranging immediately produces the improved lower bound on the largest gap.

What would settle it

For any concrete pair (g,n) on the comparison grid, recompute the four modular constructions, apply the new extraction formula, and check whether the numerical diameter matches the value claimed by the paper’s code; a single mismatch falsifies the extraction arithmetic or the existence claim used for that pair.

Watch

Extended reading notes

Core claim

In any modular g-Golomb ruler the cyclic gaps themselves obey the multiplicity bound of g. Consequently the largest gap is at least the ceiling of (N + ga(a−1)/2 + ra)/n, where n = ag + r. Cutting at that gap yields an ordinary g-Golomb ruler whose diameter is strictly smaller than the diameter obtained from the classical average-gap cut. The same extraction applies after a controlled folding that converts a modular Golomb ruler into a modular g-Golomb ruler.

Load-bearing premise

Every concrete bound rests on the classical existence of the four modular input objects (cyclic relative difference sets, Singer sets, Ruzsa–Spence rulers, and Paley residues); if any of those existence claims fails for a claimed parameter range, the corresponding family of upper bounds collapses.

Editorial extensions

If this is right

Every modular Golomb ruler whose modulus is divisible by g immediately yields an improved ordinary g-Golomb ruler after the new cut.
The four classical families now supply explicit, closed-form upper bounds for G(g,n) on large ranges of g and n.
On the 500-by-500 grid the Ruzsa–Spence family wins most often while the cyclic-RDS family wins by the largest margins and stays within 1 percent of the best bound at nearly 90 percent of points.
The same extraction works for every larger target multiplicity, so the bounds remain valid when one relaxes the allowed number of repetitions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same multiplicity-forced-gap idea can be applied to any other modular Sidon-type object whose difference multiplicities are known, not merely the four families treated here.
Because the improvement term grows with a^{2}, the relative gain becomes more pronounced precisely when n is a large multiple of g—the sparse regime where modular constructions are usually weakest.
A matching lower-bound construction that forces many equal gaps would show that the new extraction is asymptotically tight.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The one thing worth knowing is Lemma 2 / Theorem 3. Once you have a modular g-Golomb ruler, no cyclic gap length can appear more than g times, so the largest gap is forced larger than the plain average N/n. That single counting improvement is new relative to the usual modular-to-linear arguments, and everything else is just feeding classical inputs into it.

The paper does this cleanly. Lemmas 1–2 are elementary and fully written; the improvement term ga(a-1)/2 + ra drops straight out of the multiplicity hypothesis. It then applies the extraction to four standard sources (Elliott–Butson cyclic RDS, Singer, Ruzsa–Spence, Paley residues) without inventing new modular objects, and ranks the resulting families on the full 500 imes500 grid of (g, n=g+b). Code is public. Ruzsa–Spence wins most often, RDS wins by bigger margins when it does, Paley is a steady second, Singer is rare. That ranking is useful data for anyone who actually needs concrete upper bounds on G(g,n).

Soft spots are minor and proportionate. Existence of the modular inputs is taken as black-box (standard practice for a short note; the citations are correct). The work is incremental: better extraction, not new constructions or asymptotics. The grid stays in the dense regime n ≈ g + O(g), so it does not speak to sparse rulers. None of that undercuts the central claim.

This is for people who track explicit bounds on generalized Sidon / g-Golomb rulers or who convert modular difference sets to linear ones. The math is sound, the computation is reproducible, and the citation pattern is ordinary. It deserves a serious referee rather than a desk reject. I would engage with it if I needed the bounds or the extraction trick; otherwise it is a clean specialist note.

Referee Report

0 major / 5 minor

Summary. The paper studies upper bounds on G(g,n), the minimal diameter of a g-Golomb ruler with n marks. Its central contribution is a refined modular-to-linear extraction: Lemma 1 folds a modular Golomb ruler modulo N (with g|N) into a modular g-Golomb ruler modulo N/g after deleting at most ⌊g/2⌋ marks; Lemma 2 then uses the fact that no gap length can appear more than g times to guarantee a removable gap of size at least ⌈(N + ga(a-1)/2 + ra)/n⌉ when n=ag+r. Theorem 3 packages this into a general bound. The extraction is applied to four classical modular sources—Elliott–Butson cyclic relative difference sets (Theorem 5), Singer difference sets (Theorem 7), Ruzsa–Spence rulers (Theorem 8 and Corollary 9), and Paley quadratic residues (Theorem 10 and Corollary 11)—and the resulting families are compared on the 500 imes499 grid 1≤g≤500, n=g+b with 2≤b≤500.

Significance. The extraction improvement is elementary but clean and strictly stronger than the classical average-gap cut; the term ga(a-1)/2 + ra is forced by a pure extremal counting argument on gap multisets and is therefore parameter-free. The applications recover and refine known Bose–Chowla, Singer, Ruzsa–Spence and Paley constructions under a uniform framework, and the public grid computation (with code repository) supplies a concrete ranking of the four families. For a short combinatorial note this is a solid, self-contained contribution that will be useful to anyone working on g-Golomb rulers or Sidon-type sets.

minor comments (5)

In the abstract and Introduction the improvement is described as “larger guaranteed cut than the previous average gap argument”; a one-sentence explicit comparison with the classical ⌈N/n⌉ cut (already present in Remark 4) would make the novelty immediately visible to a casual reader.
Section 6 reports win counts and mean margins but does not display even a small sample of the actual numerical bounds. A short table of representative (g,n) values (or a pointer to the repository data file) would let readers verify the ranking without re-running the code.
Typographical inconsistencies appear throughout: missing spaces after commas and periods (“ag-Golomb”, “modularg-Golomb”), and occasional capitalisation slips (“we have” after a period in the Paley paragraph of the Introduction). A light copy-edit would remove them.
The date line “June 2026” and the arXiv identifier 2607.07931 are future-dated; if this is intentional it should be flagged, otherwise corrected before final publication.
References [1] and [8] are somewhat dated survey-style citations for frequency-assignment applications; a more recent pointer (if available) would strengthen the applied motivation paragraph.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: extraction lemmas are elementary counting arguments applied to classical external modular inputs.

full rationale

The paper's central claim (Theorem 3 via Lemmas 1–2) is a self-contained combinatorial argument: folding a modular Golomb ruler modulo N when g|N deletes at most ⌊g/2⌋ marks (by pairing opposite collision residues that each appear at most once), and the resulting modular g-Golomb ruler has no gap length repeating more than g times, which forces a removable gap of size at least ⌈(N + ga(a−1)/2 + ra)/n⌉ rather than the average-gap ⌈N/n⌉. This is pure extremal counting on positive integer multisets and does not define any quantity in terms of the target G(g,n). Subsequent theorems simply plug classical, externally cited modular objects (Elliott–Butson cyclic RDS, Singer difference sets, Ruzsa–Spence modular Golomb rulers, Paley quadratic residues) into the extraction; those existence statements are standard black-box inputs, not re-derived from the paper's own conclusions. The grid computation compares the resulting upper bounds and cites only the author's public code repository for reproducibility; that citation is not load-bearing for any mathematical claim. No parameter is fitted to G(g,n), no uniqueness theorem is imported from overlapping authors, and no equation reduces to a self-referential definition. Score 0 is therefore the correct outcome.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper contributes a pure combinatorial extraction lemma; every concrete bound is obtained by feeding a classical modular object into that lemma. No free parameters are fitted, no new entities are postulated, and the only external inputs are well-known existence theorems for difference sets and modular Golomb rulers.

assumptions (5)

domain assumption Cyclic relative difference sets with parameters ((q^d−1)/(q−1), q−1, q^{d−1}, q^{d−2}) exist for every prime power q and d≥2 (Elliott–Butson).
Invoked as the starting modular object in Section 3 / Theorem 5; existence is classical and not re-proved.
domain assumption Singer difference sets give modular Golomb rulers with q+1 marks modulo q^{2}+q+1 for every prime power q.
Used as black-box input for Theorem 7 (Section 4).
domain assumption Ruzsa–Spence modular Golomb rulers with p−1 marks modulo p(p−1) exist for every odd prime p.
Used as black-box input for Theorem 8 and Corollary 9.
domain assumption Nonzero quadratic residues modulo an odd prime p form a modular g-Golomb ruler with g=⌊(p−1)/4⌋ (Paley difference-set / partial-difference-set theory).
Used as black-box input for Theorem 10 / Corollary 11.
standard math Standard elementary counting: among n positive integers each value appears at most g times, the maximal sum is achieved by taking g copies of the largest possible values.
Core of the gap lower bound in Lemma 2.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Modular Constructions of g-Golomb Rulers." pith.science (2026). https://pith.science/paper/U6T2WCC5

@misc{pith2026260707931,
  author       = {Pith},
  title        = {Pith review of: Modular Constructions of g-Golomb Rulers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U6T2WCC5}},
  note         = {Machine review of arXiv:2607.07931}
}

abstract

A set \(\mathcal{G}\) of integers is a \(g\)-Golomb ruler if each positive difference appears at most \(g\) times between any 2 elements of the set, and \(G(g,n)\) denotes the minimum diameter of such a ruler with \(n\) marks. We prove a general lemma for passing from certain modular constructions to ordinary \(g\)-Golomb rulers. The key point is that, in a modular \(g\)-Golomb ruler, no cyclic gap length can occur more than \(g\) times. This gives a larger guaranteed cut than the previous average gap argument. We apply this lemma to cyclic relative difference sets, Singer sets, Ruzsa--Spence rulers, and Paley quadratic residues to provide many competing constructions for \(g\)-Golomb Rulers. A computation on the grid \(1\le g\le500\), \(n=g+b\), \(2\le b\le500\), compares the four resulting construction families.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

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

work page 1984
[2]

R. E. A. C. Paley,On orthogonal matrices, J. Math. Phys.12(1933), 311–320, DOI 10.1002/sapm1933121311

work page doi:10.1002/sapm1933121311 1933
[3]

Codes Cryptogr.4(1994), 221–261, DOI 10.1007/BF01388454

Siu Lun Ma,A survey of partial difference sets, Des. Codes Cryptogr.4(1994), 221–261, DOI 10.1007/BF01388454

work page doi:10.1007/bf01388454 1994
[4]

R. C. Bose,An affine analogue of Singer’s theorem, J. Indian Math. Soc. (N.S.)6(1942), 1–15

work page 1942
[5]

J. E. H. Elliott and A. T. Butson,Relative difference sets, Illinois J. Math.10(1966), 517–531

work page 1966
[6]

R. C. Bose and S. Chowla,On the construction of affine difference sets, Bull. Calcutta Math. Soc.37(1945), 107– 112.MR 7,365g

work page 1945
[7]

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

work page doi:10.1109/access.2021.3075877 2021
[8]

M. D. Atkinson, N. Santoro, and J. Urrutia,Integer sets with distinct sums and differences and carrier frequency assign- ments for nonlinear repeaters, IEEE Transactions on Communications34(1986), no. 6, 614–617

work page 1986

Show all 12 references

[9]

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

2004
[10]

Ruzsa,Sumsets of Sidon sets, Acta Arith.77(1996), no

Imre Z. Ruzsa,Sumsets of Sidon sets, Acta Arith.77(1996), no. 4, 353–359

1996
[11]

James Singer,A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc. 43(1938), no. 3, 377–385, DOI 10.1090/S0002-9947-1938-1501951-4

1938 doi
[12]

GitHub repository,https: //github.com/AdityaGupta3011/ModularConstructions

Aditya Gupta,Computational analysis of modular constructions ofg-Golomb rulers, 2026. GitHub repository,https: //github.com/AdityaGupta3011/ModularConstructions. 9

2026

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.

[1] [1]

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

work page 1984

[2] [2]

R. E. A. C. Paley,On orthogonal matrices, J. Math. Phys.12(1933), 311–320, DOI 10.1002/sapm1933121311

work page doi:10.1002/sapm1933121311 1933

[3] [3]

Codes Cryptogr.4(1994), 221–261, DOI 10.1007/BF01388454

Siu Lun Ma,A survey of partial difference sets, Des. Codes Cryptogr.4(1994), 221–261, DOI 10.1007/BF01388454

work page doi:10.1007/bf01388454 1994

[4] [4]

R. C. Bose,An affine analogue of Singer’s theorem, J. Indian Math. Soc. (N.S.)6(1942), 1–15

work page 1942

[5] [5]

J. E. H. Elliott and A. T. Butson,Relative difference sets, Illinois J. Math.10(1966), 517–531

work page 1966

[6] [6]

R. C. Bose and S. Chowla,On the construction of affine difference sets, Bull. Calcutta Math. Soc.37(1945), 107– 112.MR 7,365g

work page 1945

[7] [7]

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

work page doi:10.1109/access.2021.3075877 2021

[8] [8]

M. D. Atkinson, N. Santoro, and J. Urrutia,Integer sets with distinct sums and differences and carrier frequency assign- ments for nonlinear repeaters, IEEE Transactions on Communications34(1986), no. 6, 614–617

work page 1986