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
- Ariel Williams
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