Sparse ruler

Many optimal rulers are of the form ${\displaystyle W(r,s)=1^{r},r+1,(2r+1)^{r},(4r+3)^{s},(2r+2)^{(r+1)},1^{r},}$ where ${\displaystyle a^{b}}$ represents ${\displaystyle b}$ segments of length ${\displaystyle a}$. Thus, if ${\displaystyle r=1}$ and ${\displaystyle s=2}$, then ${\displaystyle W(1,2)}$ has (in order):
1 segment of length 1,
1 segment of length 2,
1 segment of length 3,
2 segments of length 7,
2 segments of length 4,
1 segment of length 1

That gives the ruler {0, 1, 3, 6, 13, 20, 24, 28, 29}. The length of a Wichmann ruler is ${\displaystyle 4r(r+s+2)+3(s+1)}$ and the number of marks is ${\displaystyle 4r+s+3}$. Note that not all Wichmann rulers are optimal and not all optimal rulers can be generated this way. None of the optimal rulers of length 1, 13, 17, 23 and 58 follow this pattern. That sequence ends with 58 if the Optimal Ruler Conjecture of Peter Luschny is correct. The conjecture is known to be true to length 213.[1]

For every ${\displaystyle n}$ let ${\displaystyle l(n)}$ be the smallest number of marks for a ruler of length ${\displaystyle n}$. For example, ${\displaystyle l(6)=4}$. The asymptotic of the function ${\displaystyle l(n)}$ was studied by Erdos, Gal[2] (1948) and continued by Leech[3] (1956) who proved that the limit ${\displaystyle \lim _{n\to \infty }{l(n)^{2}}/n}$ exists and is lower and upper bounded by
${\displaystyle 2+{\tfrac {4}{3\pi }}=2.424...<2.434...=\max _{0<\theta <2\pi }2(1-{\tfrac {\sin(\theta )}{\theta }})\leq \lim _{n\to \infty }{\frac {l(n)^{2}}{n}}\leq {\frac {375}{112}}=3.348...}$

Much better upper bounds exist for ${\displaystyle n}$-perfect rulers. Those are subsets ${\displaystyle A}$ of ${\displaystyle \mathbb {N} }$ such that each positive number ${\displaystyle k\leq n}$ can be written as a difference ${\displaystyle k=a-b}$ for some ${\displaystyle a,b\in A}$. For every number ${\displaystyle n}$ let ${\displaystyle k(n)}$ be the smallest cardinality of an ${\displaystyle n}$-perfect ruler. It is clear that ${\displaystyle k(n)\leq l(n)}$. The asymptotics of the sequence ${\displaystyle k(n)}$ was studied by Redei, Renyi[4] (1949) and then by Leech (1956) and Golay[5] (1972). Due to their efforts the following upper and lower bounds were obtained:
${\displaystyle \max _{0<\theta <2\pi }2(1-{\tfrac {\sin(\theta )}{\theta }})\leq \lim _{n\to \infty }{\frac {k(n)^{2}}{n}}=\inf _{n\in \mathbb {N} }{\frac {k(n)^{2}}{n}}\leq {\frac {128^{2}}{6166}}=2.6571...<{\frac {8}{3}}.}$

Define the excess as ${\displaystyle E(n)=l(n)-\lceil {\sqrt {3n+{\tfrac {9}{4}}}}\rfloor }$. In 2020, Pegg proved by construction that ${\displaystyle E(n)}$ ≤ 1 for all lengths ${\displaystyle n}$.[6] If the Optimal Ruler Conjecture is true, then ${\displaystyle E(n)=0|1}$ for all ${\displaystyle n}$, leading to the ″dark mills″ pattern when arranged in columns, OEIS A326499.[7] None of the best known sparse rulers ${\displaystyle n>213}$ are proven minimal as of Sep 2020. Many of the current best known ${\displaystyle E=1}$ constructions for ${\displaystyle n>213}$ are believed to non-minimal, especially the "cloud" values.

The following are examples of minimal sparse rulers. Optimal rulers are highlighted. When there are too many to list, not all are included. Mirror images are not shown.

A few incomplete rulers can fully measure up to a longer distance than an optimal sparse ruler with the same number of marks. ${\displaystyle \{0,2,7,14,15,18,24\}}$, ${\displaystyle \{0,2,7,13,16,17,25\}}$, ${\displaystyle \{0,5,7,13,16,17,31\}}$, and ${\displaystyle \{0,6,10,15,17,18,31\}}$ can each measure up to 18, while an optimal sparse ruler with 7 marks can measure only up to 17. The table below lists these rulers, up to rulers with 13 marks. Mirror images are not shown. Rulers that can fully measure up to a longer distance than any shorter ruler with the same number of marks are highlighted.

• Gauge block
• Golomb ruler
• Perfect ruler

• http://www.luschny.de/math/rulers/prulers.html
• http://oeis.org/wiki/User:Peter_Luschny/PerfectRulers
• http://www.iwriteiam.nl/Ha_sparse_rulers.html
• http://www.maa.org/editorial/mathgames/mathgames_11_15_04.html
• http://www.contestcen.com/scale.htm
• http://members.cox.net/wnmyers/sparse_rulers.txt