Message Boards Message Boards

Sparse Ruler Conjecture

Posted 5 years ago

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]

enter image description here

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.
sparse ruler demo

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.

sparse rulers to 1750

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.

predicted excess pattern

These sparse rulers are vital for finding various high-valence graceful graphs, such as the one below.

octic graceful graph

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.

Dark Satanic Mills

With another overnight run I cleaned up the pattern more.

Dark Mills Aug 1

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. Wichmann-like rulers

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}]  

wichmannruler for 10000000

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}]  

wichmann 24!

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]

Leech Bounds versus construction

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. rulers 4211

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.

instant sparseness diagram

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.

slow sparseness diagram

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}]}, " "]

rulers of powers

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}}}

Dark Mills Sequence

POSTED BY: Ed Pegg
2 Replies

enter image description here - Congratulations! This post is now featured in our Staff Pick column as distinguished by a badge on your profile of a Featured Contributor! Thank you, keep it coming, and consider contributing your work to the The Notebook Archive!

POSTED BY: Moderation Team
Posted 5 years ago

Hi. I was doing some work you may find useful. I was just recently introduced to p-adic... stuff? So, I'm sorry in advanced if I get my terminology off.

I was introduced to these because of something I was working on in binary that begged for more convenient notation (infinite divergent series in binary).... anyway, for clarity everything below is in base 2 besides the rationals which are in standard base 10. Ie ...111.0 = 1+2+4... etc. So I let x=...1010.0 X/2=...10101.0 Then added 1 to x get. x+1=...101011.0 Then x+(x/2) to get = (-1/3)+(-2/3)=-1 What I found out was that the results I found where contrary to p-adic notation. I "should" have gotten plus or minus 1/3, but instead got -1/3 and -2/3. I also got that -...111.0=0(note the negative). I should have gotten that -...111.0=1.

I suspect that these differences may be due to the "first prime" in p-adic being considered a zero, and not a 1, but I have no idea. Like I said, I was just recently lead to this, and have basically no undergraduate mathematical training, but I hope it helps. I suspect it may be related.

POSTED BY: Chaz Byrne
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract