Closing the Gaps with the AW Schedules: The Exact Minimum Diameter of Linear-Multiplicity Rulers

How short can an integer ruler be if each positive distance d can occur at most d − 1 times? Gupta and O’Bryant asked whether the lower bound obtained by filling the smallest consecutive gaps to capacity is attained for every number of marks. This preprint answers their Problem 7 by giving two explicit schedules, one for each parity of the largest gap. Write N(k) = 1 + k(k − 1)/2. For N(k) ≤ n ≤ N(k + 1), the minimum diameter is (k³ − k)/3 + (k + 1)(n − N(k)). The schedules place all copies of their largest gap at the end, so removing the last marks one at a time gives optimal rulers at every intermediate size. In particular, the consecutive increments in minimum diameter follow the pattern 2, 3, 3, 4, 4, 4, … recorded by Gupta in OEIS A392517. The proof bounds short and long distances analytically. For middle distances it classifies consecutive runs of gaps and verifies a finite system of rational inequalities that covers all remaining heights. The supporting archive contains the paper, its LaTeX source, the exact certificates, and Python 3.12 programs for reproducing the calculations.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24362077
Citations
1
Primary Topic
Advanced Combinatorial Mathematics
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Closing the Gaps with the AW Schedules: The Exact Minimum Diameter of Linear-Multiplicity Rulers

Ariel Williams
1 citations
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

Closing the Gaps with the AW Schedules: The Exact Minimum Diameter of Linear-Multiplicity Rulers

Ariel Williams
preprint en
1 citations

Abstract

How short can an integer ruler be if each positive distance d can occur at most d − 1 times? Gupta and O’Bryant asked whether the lower bound obtained by filling the smallest consecutive gaps to capacity is attained for every number of marks. This preprint answers their Problem 7 by giving two explicit schedules, one for each parity of the largest gap. Write N(k) = 1 + k(k − 1)/2. For N(k) ≤ n ≤ N(k + 1), the minimum diameter is (k³ − k)/3 + (k + 1)(n − N(k)). The schedules place all copies of their largest gap at the end, so removing the last marks one at a time gives optimal rulers at every intermediate size. In particular, the consecutive increments in minimum diameter follow the pattern 2, 3, 3, 4, 4, 4, … recorded by Gupta in OEIS A392517. The proof bounds short and long distances analytically. For middle distances it classifies consecutive runs of gaps and verifies a finite system of rational inequalities that covers all remaining heights. The supporting archive contains the paper, its LaTeX source, the exact certificates, and Python 3.12 programs for reproducing the calculations.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon