What is the smallest set so that differences of members of the set give all values from
$1$ to
$n$? This is a famous problem worked on by Paul Erd?s, Marcel J. E. Golay, John Leech, Alfréd Rényi, László Rédei, Solomon W. Golomb, Alfred Brauer and C. Brian Haselgrove, among many others.
For example, {0, 1, 6, 9, 11, 13} covers 1 to 13. 1-0, 13-11, 9-6, 13-9, 6-1, 6-0, 13-6, 9-1, 9-0, 11-1, 11-0, 13-1, 13-0. For 13, the smallest set is 6.
John Leech ("On the "Representation of 1,2,...,n by Differences", J. of London Math Soc, April 1956) gave the definitive answer: a lower bound of
$\sqrt{2.434 n}$ (blue) and an "asymptotic" upper bound of
$\sqrt{3.348 n}$ (green). The 63 year Leech bounds are still widely cited and used. Even today the Wikipedia article on sparse rulers cites the bound as a disproof for the Optimal Ruler Conjecture of Peter Luschny. The Leech bound is cited by thousands of papers, some published just a few weeks ago. We can compare the Leech bounds to best known actual values (yellow) to 1750.
ListPlot[{Table[Sqrt[2.434 n] - ( Sqrt[3 n + 9/4]), {n, 1, 1750}],
Table[minimalSparse[[n]] - ( Sqrt[3 n + 9/4]), {n, 1, 1750}],
Table[ Sqrt[3.348 n] - ( Sqrt[3 n + 9/4]), {n, 1, 1750}]},
AspectRatio -> 1/5]
See all those lines of yellow dots? There is a deeper pattern to those lines. Now that I've extended results to 1750 and collected thousands of Wichmann-like ruler constructions, it seems the Leech bounds are wrong. This seems to be a computational problem rather than an analysis problem.
I can also strengthen Peter's conjecture.
Sparse Ruler Conjecture. If a minimal sparse ruler of length
$n$ has
$m$ marks,
easy (true to at least 1790):
$m-\lceil \sqrt{3*n +9/4} \rfloor \in (0,1)$.
hard (true to at least 473):
$m+\frac{1}{2} \ge \sqrt{3 \times n +9/4} \ge m-1$.
At Sparse Rulers I have a Wolfram Demonstration on sparse rulers up to length 1750.
A sparse ruler of length
$n$ has
$\lceil \sqrt{3*n +9/4} \rfloor + k$ marks, with
$\lceil x \rfloor$ intended as the round function and
$k $ as the excess. The excess
$k$ is 0 until 51, 59, 69, ... ( A308766) where
$k=1$, the black square values in the pattern below to 1750. Minimal marks
$m$ are listed in A046693 and verified to length 213. Values increment down, then across. Bottom row values are Wichmann rulers A289761. The columns correspond to lines in the pattern above. This grid with 1750 Tooltips is part of the Sparse Rulers Demonstration.
With more optimal sparse rulers the
$(0,1)$ pattern for
$m - \lceil \sqrt{3 \times n +9/4} \rfloor$ might look like the following if the hard form of the conjecture is true. Some of the 0-excess sparse rulers are really hard to find. It took trillions of computations to get to these patterns.
These sparse rulers are vital for finding various high-valence graceful graphs, such as the one below.
I was greatly helped by counts and code from Parallel Computation of Sparse Rulers by Arch Robison. I asked him if he still had his data, but he hadn't kept a copy of it. The data is lost. But Tomas Sirgedas was able to recreate some of the data to value 150.
You can compare the 63-year old mathematical bound to the data listed in the Sparse Rulers Wolfram Demonstration.
On 1st of August I identified about two thousand Wichmann-like ruler constructions that are infinite and built a few more algorithms to extend the pattern of A046693(n) - A309407(n) to n=4443. A lot of the black and green squares are likely white and black instead, but there's a definite weird pattern to this.
"Dark Satanic Mills on a cloudy day" -- NJA Sloane.
With another overnight run I cleaned up the pattern more.
Those green areas have excess 2 and are at positions {1792, 2096, 2097, 2098, 2099, 2429, 2782, 2783, 3161}.
The attached file (sparsedata.nb) has my sparse ruler collection as of Thu 1 Aug 2019. Can anyone find sparse rulers with fewer marks for a given length? I have nine improvements so far that aren't included in the notebook.
{0, 1966, {{1,14,27,55,28,55,28,1},{13,1,13,11,1,10,14,13}}}
{0, 2286, {{1,15,29,59,30,59,30,1},{14,1,14,12,1,11,15,14}}}
{0, 2630, {{1,16,31,63,32,63,32,1},{15,1,15,13,1,12,16,15}}}
{0, 2931, {{1,17,33,67,34,67,34,1},{16,1,16,13,1,13,17,16}}}
{0, 3319, {{1,18,35,71,36,71,36,1},{17,1,17,14,1,14,18,17}}}
{0, 3390, {{1,18,35,71,36,71,36,1},{17,1,17,15,1,14,18,17}}}
{0, 3806, {{1,19,37,75,38,75,38,1},{18,1,18,16,1,15,19,18}}}
{0, 4167, {{1,20,39,79,40,79,40,1},{19,1,19,16,1,16,20,19}}}
{0, 4246, {{1,20,39,79,40,79,40,1},{19,1,19,17,1,16,20,19}}}
If anyone has trouble using the notebook (sparsedata.nb) in the above post, let me know. The SparseRuleDemo might also be handy.
I submitted a new Wolfram Demonstration on Wichmann-like rulers (see attached WichmannLikeRulers.nb). You can get a sneak peak of it here.
The 2216 Wichmann rules presented each produces an infinite number of sparse rulers. For lengths under 4444, I have about half a million sparse rulers at the moment. A full third of them comes from this set of Wichmann-like rules.
If you'd like to produce sparse rulers with any integer length, this set of variants will provide a good start.
Are there any infinite rules I'm missing here?
The attached notebook, FindWichmann.nb, takes advantage of the 886 infinite Wichmann-like sparse ruler constructions given in the Wolfram Demonstration above. For any positive integer it will find the best sparse ruler that can be made from these Wichmann-like constructions within a few seconds.
For example, let's make a sparse ruler of length 10 million.
FindWichmann[10000000]
{{{500, 22, {835, 2151}}, {501, 22, {835, 2151}}}, {{828,
24, {832, 2165}}, {829, 24, {832, 2165}}, {830, 24, {832, 2163}}}}
WichmannRulerPlain[wichmannrules[[500]], {835, 2151}]
A sparseness value of 22 is really awful compared to what I usually see.
Sparseness is marks - round(sqrt(3 length +9/4)).
The Leech bound is floor(sqrt(3.348 length) - round(sqrt(3 length +9/4)) ).
So how bad is a sparseness of 22 compared to the Leech bound?
LeechBound[10000000]
309
My instant direct construction is considerably better than the upper bound given by Leech. Let's try a higher value, 24! (620448401733239439360000).
LeechBound[24!]
76959449642
FindWichmann[24!]
{{{605, 852645032, {235567620692, 422893418966}}, ....
WichmannRulerPlain[wichmannrules[[605]], {235567620692, 422893418966}]
That is a sparse ruler with an excess of 852645032, considerably better than the Leech bound of 76959449642. That very likely isn't the optimal sparse ruler for length 24!, but it's reasonably minimal for a fast construction.
Does this construction method ever exceed the Leech bound? It's not so good up to 117, where it exceed the Leech bound at lengths {1, 2, 3, 4, 5, 6, 13, 17, 23, 27, 34, 40, 41, 48, 51, 58, 59, 66, \
69, 75, 76, 77, 86, 87, 88, 95, 96, 97, 98, 99, 109, 110, 113, 117}. I've found one case so far after that, 4211 has a Leech bound sparseness of 6 and an instantaneous construction sparseness of 8.
ListPlot[{Table[values[[n]], {n, 1, 5813}], Table[ Sqrt[3.348 n] - ( Sqrt[3 n + 9/4]), {n, 1, 5813}]},
AspectRatio -> 1/5]
LeechBound[4211]
6
FindWichmann[4211]
{{46, 8, {13, 12}}, {258, 8, {11, 66}}, {272, 8, {11, 65}}, ...
Through much, much slower methods I have 10 sparse rulers of length 4211 with an excess of 1.
With instant constructions here's what a sparseness diagram looks like to length 5763, with gray=0, black=1, red=2, orange=3, yellow=4, green=5, green=6, purple=8.
For tedious slow constructions, here are the best known sparseness values to length 4443. Doing things the hard way gives much cleaner results. Some of the more optimal sparse rulers took months for me to find. No sparse rulers past length 213 have been proven optimal.
Looks like I need more of these infinite Wichmann-like ruler constructions and perhaps some hard-coded rulers for under 120. Still, it is handy to have near instant constructions.
Unsolved:
1. Does the FindWichmann construction ever exceed the Leech bound past 4211?
2. What are other Wichmann-like constructions that work infinitely for all input values?
EDIT: I was told I was lemon-picking, finding the worst possible outcomes. Here's some cherry-picking for likely optimal sparse rulers of some arbitrary large values.
FindWichmann[#][[1, 1]] & /@ {7^7, 2^27, 3^27}
{{166, 1, {268, 490}}, {1, 0, {3326, 6759}}, {255, 1, {398580, 1594322}}}
Row[{WichmannDisplay[wichmannrules[[166]], {268, 490}],
WichmannDisplay[wichmannrules[[1]], {3326, 6759}],
WichmannDisplay[wichmannrules[[255]], {398580, 1594322}]}, " "]
A046693[n]-A309407[n] -- Dark Mills pattern, 10501 terms.
Gray=0 , Black = 1, Red = 2.
Bottom row n values are https://oeis.org/A289761 .
On August 13. I managed to clean up a lot of dust on this sequence. Some of the 1's and 2's might be 1 lower.
Got to take a look at a three day run on another computer. Values for length 1313, 1358, 1448, 1583, 1673 are +1 dust in the image below due to the following sparse rulers:
{{{1,11,1,21,1,21,22,45,23,1},{10,1,1,1,1,1,9,18,10,10}},
{{1,11,1,21,1,21,22,45,23,1},{10,1,1,1,1,1,9,19,10,10}},
{{1,11,1,21,1,21,22,45,23,1},{10,1,1,1,1,1,9,21,10,10}},
{{1,11,1,21,1,21,22,45,23,1},{10,1,1,1,1,1,9,24,10,10}},
{{1,11,1,21,1,21,22,45,23,1},{10,1,1,1,1,1,9,26,10,10}}}
Attachments: