Essays, Posts & Presentations

Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof

Ed Pegg

Author

Ed Pegg

Title

Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof

Description

An overview of the famous 'Representation of 1, 2, …, n by Differences' problem and an in-depth look at sparse rulers. Proof, solution and code included in downloadable notebook.

Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof

February 12, 2020

Ed Pegg Jr, Editor, Wolfram Demonstrations Project

The sparse ruler problem has been famously worked on by Paul Erdős, Marcel J. E. Golay, John Leech, Alfréd Rényi, László Rédei and Solomon W. Golomb, among many others. The problem is this: what is the smallest subset

{0,…,n}

so that the unsigned pairwise differences of

give all values from 1 to

? One way to look at this is to imagine a blank yardstick. At what positions on the yardstick would you add 10 marks, so that you can measure any number of inches up to 36?

Another simple example is

{0,1,3}

of size 3, which has differences

1-0=1

3-1=2

and

3-0=3

. The sets of size 2 have only one difference. The minimal subset

{0,1,3}

is not unique; the differences of

{0,2,3}

also give

{1,2,3}

Part of what makes the sparse ruler problem so compelling is its embodiment in an object inside every schoolchild’s desk—and its enduring appeal lies in its deceptive simplicity. Read on to see precisely just how complicated rulers, marks and recipes can be.

Some History

First, let’s review the rules and terminology used in the sparse ruler problem. A subset

of a set

covers

{

:

∈S}=T

For example, what is the smallest subset

{0,1,2…,13}

that covers the set

[13]={1,2,…,13}

? The greatest number of differences for a subset of size 5 is



=10

, which is not enough to get 13 values. But a subset of size 6, with



=15

differences, is large enough. In this case, the subset

{0,1,6,9,11,13}

covers

[13]

, and so the size of the smallest covering subset of

[13]

is at most 6.

Here are the differences using only

{0,1,6,9,11,13}

In[]:=

{1,13,9,13,6,6,13,9,9,11,11,13,13}-{0,11,6,9,1,0,6,1,0,1,0,1,0}

Out[]=

{1,2,3,4,5,6,7,8,9,10,11,12,13}

Of the 15 differences, two are achieved twice:

2=11-9=13-11

and

5=6-1=11-6

. Here is a way to list the pairs explicitly:

In[]:=

Column[SplitBy[SortBy[Subsets[{0,1,6,9,11,13},{2}],Differences],Differences]]

Out[]=

{{9,11},{11,13}}

{{1,6},{6,11}}

Let’s try another way to calculate the set of differences:

In[]:=

Union@Abs@Flatten@Outer[Subtract,{0,1,6,9,11,13},{0,1,6,9,11,13}]

Out[]=

{0,1,2,3,4,5,6,7,8,9,10,11,12,13}

Of the subsets that cover

[n]={1,2,3,…,n}

, let

be the size of a smallest subset (there may be more than one).

The following table summarizes the values of

for

n=1,2,…,12

. Both

{0,1,3}

and

{0,2,3}

of size 3 cover

[3]

; note that

3-{0,2,3}={3,1,0}={0,1,3}

after sorting:

Out[]=

a smallest subset	differences [n]	the smallestsubset size M n
{0,1}	[1]	2
{0,1,2}	[2]	3
{0,1,3}	[3]	3
{0,1,2,4}	[4]	4
{0,1,2,5}	[5]	4
{0,1,4,6}	[6]	4
{0,1,2,3,7}	[7]	5
{0,1,2,5,8}	[8]	5
{0,1,2,6,9}	[9]	5
{0,1,2,3,6,10}	[10]	6
{0,1,2,3,7,11}	[11]	6
{0,1,2,3,8,12}	[12]	6

In 1956, John Leech wrote “On the Representation of 1, 2, …, n by Differences,” which proved the bounds

2.434n

≤

3.348n

.
There are a few terms and “rules” to keep in mind when discussing the sparse ruler problem:

◼

A subset of

{0,1,…,n}

containing 0 and

is called an

-length ruler, and its elements are called marks. (The length

can be dropped when it is understood.)

◼

-length ruler is complete if the distances between marks cover

[n]

◼

A sparse ruler (or minimal complete ruler) is a length-

complete ruler such that no length-

ruler with fewer marks exists. An example of a sparse ruler is

{0,1,2,5,8}

◼

An optimal ruler is a sparse ruler where there is no longer sparse ruler with the same number of marks. An example is

{0,1,4,7,9}

. No longer sparse ruler with five marks exists.

◼

A perfect ruler is a sparse ruler where a longer sparse ruler with fewer marks does not exist. All sparse rulers of length less than 135 are perfect.

◼

A nonperfect ruler is a sparse ruler where a longer sparse ruler with fewer marks does exist.

This length-135 sparse ruler is nonperfect:

In[]:=

Length@{0,1,2,3,4,5,6,65,68,71,74,81,88,95,102,109,116,123,127,131,135}

Out[]=

This length-138 sparse ruler is optimal:

In[]:=

Length@{0,1,2,3,7,14,21,28,43,58,73,88,103,111,119,127,135,136,137,138}

Out[]=

Here is an optimal length-50 sparse ruler with 12 marks (i.e.

=12

). The list of positions of the marks is the ruler form:

In[]:=

ruler50={0,1,3,6,13,20,27,34,41,45,49,50};

This visualizes the marks:

Let the differences between the marks be the diff form. Here is the diff form for ruler50:

In[]:=

Differences[ruler50]

Out[]=

{1,2,3,7,7,7,7,7,4,4,1}

In 1963, B. Wichmann wrote “A Note on Restricted Difference Bases,” in which he constructed many sparse rulers. The following code has his original recipe and a function to read the recipe:

In[]:=

originalwichmannrecipe={{1,1+r,1+2r,3+4r,2+2r,1},{r,1,r,s,1+r,r}};

In[]:=

WichmannRuler[recipe_,{x_,y_}]:=Transpose[Select[Transpose[recipe/.Thread[{r,s}{x,y}]],Min[#]>0&]]

With that, we can set up function

for Wichmann recipe #1:

In[]:=

[r_,s_]:=WichmannRuler[originalwichmannrecipe,{r,s}];

There are thousands of Wichmann recipes. Here’s the second:

In[]:=

WichmannRecipes[[2]]

Out[]=

{{1,1+r,1+2r,3+4r,2+2r,1},{r,1,1+r,s,r,r}}

Here’s a function

for Wichmann recipe #2:

In[]:=

[r_,s_]:=WichmannRuler[WichmannRecipes[[2]],{r,s}];

Here,

and

in the recipes are replaced by 1 and 5, respectively. These representations are examples of the split form of a sparse ruler:

In[]:=

Column[{

[1,5],

[1,5]}]

Out[]=

{{1,2,3,7,4,1},{1,1,1,5,2,1}}

{{1,2,3,7,4,1},{1,1,2,5,1,1}}

We can use these functions to convert among the three forms of sparse ruler:

In[]:=

DiffToRuler[diff_]:=FoldList[Plus,0,diff]

In[]:=

DiffToSplit[diff_]:={First/@Split[diff],Length/@Split[diff]}

In[]:=

SplitToDiff[split_]:=Flatten[Table[#[[1]],{#[[2]]}]&/@Transpose[split]]

In[]:=

SplitToRuler[split_]:=DiffToRuler[SplitToDiff[split]]

In[]:=

RulerToSplit[ruler_]:=DiffToSplit[Differences[ruler]]

Here are the diff forms for both

and ruler50 from above; we can see from their identical outputs that they are in fact the same ruler:

In[]:=

SplitToDiff[

[1,5]]

Out[]=

{1,2,3,7,7,7,7,7,4,4,1}

In[]:=

Differences[ruler50]

Out[]=

{1,2,3,7,7,7,7,7,4,4,1}

The diff form can be used to remake the ruler:

In[]:=

DiffToRuler[%]

Out[]=

{0,1,3,6,13,20,27,34,41,45,49,50}

Here is the split form again:

In[]:=

[1,5]

Out[]=

{{1,2,3,7,4,1},{1,1,1,5,2,1}}

The split form can be written compactly and compared to Wichmann’s recipe with

r=1,s=5

1 1	1 2	1 3	5 7	2 4	1 1
r 1	1 (1+r)	r (1+2r)	s (3+4r)	1+r (2+2r)	r 1

This Wichmann ruler is one of an infinite list of Wichmann rulers. The length-57 sparse rulers show two examples for

=13

length	marks	recipe	r	s
50	12	1 1 1 2 1 3 5 7 2 4 1 1	1	5
57	13	1 1 1 2 1 3 6 7 2 4 1 1	1	6
57	13	2 1 1 3 2 5 2 11 3 6 2 1	2	2
90	16	2 1 1 3 2 5 5 11 3 6 2 1	2	5
93	17	3 1 1 4 3 7 2 15 4 8 3 1	3	2
101	17	2 1 1 3 2 5 6 11 3 6 2 1	2	6
108	18	3 1 1 4 3 7 3 15 4 8 3 1	3	3
112	18	2 1 1 3 2 5 7 11 3 6 2 1	2	7
123	19	2 1 1 3 2 5 8 11 3 6 2 1	2	8
123	19	3 1 1 4 3 7 4 15 4 8 3 1	3	4
138	20	3 1 1 4 3 7 5 15 4 8 3 1	3	5
153	21	3 1 1 4 3 7 6 15 4 8 3 1	3	6
168	22	3 1 1 4 3 7 7 15 4 8 3 1	3	7
183	23	3 1 1 4 3 7 8 15 4 8 3 1	3	8
198	24	3 1 1 4 3 7 9 15 4 8 3 1	3	9
213	25	4 1 1 5 4 9 6 19 5 10 4 1	4	6

Next is the length-58 optimal ruler showing that

≤13

. Using brute force,

=13

is provable. In 2011, Peter Luschny conjectured that the

=13

optimal ruler is the largest optimal ruler that does not use Wichmann’s recipe.

Text@Grid[Transpose[{{"split","diff","ruler","

"},{#,SplitToDiff[#],SplitToRuler[#],Length[SplitToRuler[#]]}&@sparsedata[[58]]}],FrameAll]

split	{{1,24,5,4,3},{3,1,1,5,2}}
diff	{1,1,1,24,5,4,4,4,4,4,3,3}
ruler	{0,1,2,3,27,32,36,40,44,48,52,55,58}
M n	13

In 2014, Arch D. Robison wrote “Parallel Computation of Sparse Rulers,” where months of computer time was spent on 256 Intel cores to calculate 106,535 sparse rulers up to length 213. Part of this run proved the existence of a length-135 nonperfect ruler.

So while we have identified all the sparse rulers up to length 213, we only have candidates beyond length 213. For the rest of this blog post, “conjectured sparse ruler” means a complete ruler with length greater than 213 and the minimal known number of marks. Above length 213, no sparse rulers have been proven minimal. Length 214 has the first conjectured sparse ruler:

minimal?	length	marks	compact split form
proven	213	25	4 1 1 5 4 9 6 19 5 10 4 1
conjectured	214	26	5 1 1 5 4 9 6 19 5 10 4 1

Robison’s run required 1.5 computer years to verify

208

=25

. Computationally verifying

227

=26

would require 3 computer years using current methods. Adding a single mark doubles the computational difficulty of verifying minimality with currently known methods.

You may have heard of sparse rulers, Golomb rulers and difference sets. How do these relate to each other?

◼

In a sparse ruler, all differences must be covered, but they can be repeated.

◼

In a Golomb ruler, differences can be missed, but none can be repeated.

◼

In a difference set, all modular distances must be covered, and none can be repeated.

◼

In 1967, Robinson and Bernstein predicted the best 24-mark Golomb ruler.

◼

In 1984, Atkinson and Hassenklover made predictions of the best Golomb rulers with under 100 marks.

◼

In 2014, distributed.net proved that the predicted Golomb rulers with 24 to 27 marks were indeed correct using thousands of years of computer time. The Robison run verified that predicted behavior for optimal rulers was correct up to 25 marks.

◼

In 2016, Rokicki and Dogon made predictions of the best Golomb rulers with under 40000 marks.

New Discoveries

In 2019, I devised a formula that expresses the excess

of a complete ruler in terms of the length

and the number of minimal marks

; here,

⌈·⌋

is the rounding function:

-

3n+9/4



For the first 50 lengths,

. Then

=13

, so

In[]:=

12-Round[

350+9/4

],13-Round[

351+9/4

]

Out[]=

{0,1}

The excess formula produces the exact number of minimal marks for sparse rulers up to length 213, with two lines of code. In the On-Line Encyclopedia of Integer Sequences (OEIS), this list of the number of minimal marks for a sparse ruler is sequence A046693:

In[]:=

A308766[n_]:=If[MemberQ[{51,59,69,113,124,125,135,136,139,149,150,151,164,165,166,179,180,181,195,196,199,209,210,211},n],1,0];A046693=TableRound[

3n+9/4

]+A308766[n],{n,213}

Out[]=

{2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,8,8,9,9,9,9,9,9,10,10,10,10,10,10,10,11,11,11,11,11,11,11,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,16,16,16,16,16,16,16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,17,18,18,18,18,18,18,18,18,18,18,18,19,19,19,19,19,19,19,19,19,19,19,20,20,20,20,20,20,20,20,20,20,20,21,21,20,20,21,21,21,21,21,21,21,21,21,21,22,22,22,21,21,22,22,22,22,22,22,22,22,22,22,23,23,23,22,22,23,23,23,23,23,23,23,23,23,23,24,24,24,23,23,24,24,24,24,24,24,24,24,24,24,24,25,25,24,24,25,25,25,25,25,25,25,25,25,25,26,26,26,25,25}

Based on the sparse rulers and conjectured sparse rulers to length 2020, the excess seems to be a chaotic sequence of 0s and 1s:

In[]:=

ListPlot[Take[rulerexcess,2020],JoinedTrue,AspectRatio1/30,AxesFalse,ImageSize520]

If Luschny’s conjecture is correct, then the lowest possible excess is 0 and all

E=0

conjectured sparse rulers are minimal.

Without rounding, a plot of the best-known number of minimal marks

minus

3n+9/4

shows some distinct patterns up to length 2020. Some points, such as

474

=1,

seem to float above and break the pattern, which makes their minimality questionable:

In[]:=

unroundedexcess=Tablen,Round[

3n+9/4

]+rulerexcess[[n]]-

3n+9/4

,{n,1,2020};ListPlot[unroundedexcess,AspectRatio1/4,ImageSize{520,130}]

Here are lengths of currently conjectured sparse rulers that break the pattern:

In[]:=

First/@Select[unroundedexcess,#[[2]]>1&]

{474,501,582,609,669,792,793,824,825,826,861,966,1000,1001,1036,1037,1038,1077,1194,1231,1272,1273,1274,1317,1356,1399,1446,1487,1488,1489,1532,1533,1534,1581,1624,1671,1722,1767,1768,1769,1817,1818,1863,1869,1916,1967,2016}

Here is a plot of the verified number of minimal marks

213

ListPlot[A046693,AspectRatio1/4,ImageSize520]

Robison discovered that the sequence

is not strictly increasing, as seen by the dips. Where do these dips occur?

In[]:=

Flatten[Position[Differences[A046693],-1]]

Out[]=

{136,151,166,181,196,211}

How are they spaced?

In[]:=

Differences[%]

Out[]=

{15,15,15,15,15}

In the previous table, the last six listed Wichmann rulers had these lengths:

In[]:=

{138,153,168,183,198,213};

These coincide with the positions of the dips:

In[]:=

{136,151,166,181,196,211}+2

Out[]=

{138,153,168,183,198,213}

We can plot and compare Leech’s bounds for the number of minimal marks to the actual number of minimal marks:

In[]:=

ListPlot[{Table[Sqrt[2.434n],{n,1,213}],Table[A046693[[n]],{n,1,213}],Table[Sqrt[3.348n],{n,1,213}]},AspectRatio1/5]

Out[]=

The furthest values in the lines of dots are almost always lengths of optimal Wichmann rulers, with the last known exception being

=13

. We saw that some of the lengths of optimal Wichmann rulers were

{138,153,168,183,198,213}

. Let us call these Wichmann values. These lengths (A289761) are given by:

WichmannValues=Table[(n^2-(Mod[n,6]-3)^2)/3+n,{n,1,24}]

{0,3,6,9,12,15,22,29,36,43,50,57,68,79,90,101,112,123,138,153,168,183,198,213}

Here I arrange numbers to 213 so that the bottom of each column is a Wichmann value. Under the blue line is the number of marks associated with the column. This is a numeric representation of the excess pattern:

E=0

values are gray.

E=1

values are bold black.

Grid[Append[Transpose[Table[PadLeft[Take[Style[If[rulerexcess[[#]]1,Style[#,Black,Bold,16],Style[#,Gray,14]]]&/@Range[213],{WichmannValues[[n]]+1,WichmannValues[[n+1]]}],15,""],{n,24-1}]],Range[3,25]],Spacings{.2,.2},Dividers{False,-2Blue}]

																	124	139	154	169	184	199
																	125	140	155	170	185	200
																	126	141	156	171	186	201
																	127	142	157	172	187	202
											58	69	80	91	102	113	128	143	158	173	188	203
											59	70	81	92	103	114	129	144	159	174	189	204
											60	71	82	93	104	115	130	145	160	175	190	205
											61	72	83	94	105	116	131	146	161	176	191	206
					16	23	30	37	44	51	62	73	84	95	106	117	132	147	162	177	192	207
					17	24	31	38	45	52	63	74	85	96	107	118	133	148	163	178	193	208
					18	25	32	39	46	53	64	75	86	97	108	119	134	149	164	179	194	209
					19	26	33	40	47	54	65	76	87	98	109	120	135	150	165	180	195	210
1	4	7	10	13	20	27	34	41	48	55	66	77	88	99	110	121	136	151	166	181	196	211
2	5	8	11	14	21	28	35	42	49	56	67	78	89	100	111	122	137	152	167	182	197	212
3	6	9	12	15	22	29	36	43	50	57	68	79	90	101	112	123	138	153	168	183	198	213
3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

For convenience, I’ll use various terms relating to the excess pattern:

◼

A column is a column in the excess pattern

◼

is the column for

E=0

rulers with

marks

◼

The height is the placement within a column; Wichmann values have height 0

◼

The rise is the number of entries in a column;

has 15 entries

◼

The excess coordinate is

(column,height)

for length

within the excess pattern

◼

The excess fraction (a normalized form) is

height+1

rise+1

for length

◼

A window is a contiguous set of

E=0

rulers within a column

◼

A mullion is a contiguous set of

E=1

rulers within a column (a space between windows is a mullion)

A few sample values for rulers in columns 19 and 25:

length	114	116	120	122	200	202	204	206	208	210	212	213
column	19	19	19	19	25	25	25	25	25	25	25	25
height	9	7	3	1	13	11	9	7	5	3	1	0
fraction	1 6	1 3	2 3	5 6	1 8	1 4	3 8	1 2	5 8	3 4	7 8	15 16
rise	11	11	11	11	15	15	15	15	15	15	15	15

Here is the excess pattern of the best-known excess values for lengths up to 10501.

E=0

is gray,

E=1

is black. This is a pixel representation of the excess pattern:

The creator of OEIS, N. J. A. Sloane, describes this pattern as “Dark Satanic Mills on a Cloudy Day.” This unique description refers to the solid black part of the pattern with many windows, dark mills and the irregular patches above, the clouds.

We calculate these coordinates for various lengths:

In[]:=

coordinated=Tablexy=ExcessCoordinates[n];col=Switchxy[[2]],

,

,

,

,

,

,_,

;{col[[rulerexcess[[n]]+1]],xy[[1]],{xy[[1,1]]/120,1-xy[[2]]},xy[[3]]},{n,1,10501};

Here is the excess pattern of the best-known excess values for lengths up to 10501.

E=0

E=1

.Some colors have exact excess fractions:

⟷

Row[{Graphics[{{#[[1]],Rectangle[#[[2]]]}&/@coordinated},ImageSize{480,318},PlotRange{{3,159},{0,106}}]}]

This plots the excess fractions. The excess fractions

and

occur in each column; they are the colored horizontal lines:

Graphics[{{#[[1]],Point[#[[3]]]}&/@coordinated},ImageSize{480,318}]

Here’s a version of the excess pattern where the excess fraction 1/2 makes a horizontal line. A crushed version of the normalized excess fraction pattern is shown on the right.

E=0

E=1

.Some colors have exact excess fractions as before:

⟷

=⟷

⟷

For the following diagram, on the left are columns

with cells representing lengths 1516 to 1797.

E=0

E=1

. On the right is the normalized excess fraction:

In the normalized excess pattern:

◼

0 to 1/4 has mostly excess 0

◼

1/4 to 1/2 has a chaotic pattern

◼

1/2 to 1 has mostly excess 1

Various sequences from OEIS:
A004137: maximal number of edges in a graceful graph on

nodes
A046693: minimal marks for a sparse ruler of length

A103300: number of perfect rulers with length

A289761: maximum length of an optimal Wichmann ruler with

marks.
A308766: lengths

of sparse rulers with excess 1
A309407: round(sqrt(3*

+ 9/4))
A326499: excess

of a length-

sparse ruler

You can also check out the “Sparse Rulers” Demonstration, which has thousands of these sparse rulers:

Producing two million sparse rulers required over two thousand Wichmann-like rulers, construction recipes that all work with arbitrarily large values. Substituting

and

values into a Wichmann recipe is computationally easy:

Out[]=

pick recipe (

)

variables (

)

split form

1	2	3	7	4	1
1	1	1	1	2	1

rule

1	r+1	2r+1	4r+3	2r+2	1
r	1	r	s	r+1	r

marks	4r+s+3
length	4 2 r +4rs+8r+3s+3

excess	0
best known	8
marks	8
length	22

differences form

{1,2,3,7,4,4,1}

ruler marks form

{0,1,3,6,13,17,21,22}

Proof That
E≤1

The excess

of a length-

sparse ruler with minimal number of marks

-

3n+9/4



Sparse ruler conjecture: E = 0 or 1 for all sparse rulers.

Part 1,
L>257992

Finding sparse rulers satisfying

E≤1

for all lengths under 257992 is difficult and likely couldn’t have been done without current-era computers. Finding longer-length sparse rulers turns out to be easy and could have been done back in 1963 with the following simple proof.

1	r+1	2r+1	4r+3	2r+2	1
r	1	r	s	r+1	r

is the split form of Wichmann recipe 1, or

1	3	5	11	6	1
2	1	2	3	3	2

r=2

s=3

(0,1,2,5,10,15,26,37,48,54,60,66,67,68)

(1,1,3,5,5,11,11,11,6,6,6,1,1)

in the diff form.

1	3	5	11	6	1	3
2	1	2	3	3	2	1

is an extension. A sparse ruler starting with

1s in the diff form can be extended by up to

b+1

1s with an extra mark at the end. This new ruler looks like

(0,1,2,5,10,15,26,37,48,54,60,66,67,68,71)

. The new lengths above

are handled by differences

69=71-2

70=71-1

and

71=71-0

. Note that

(0,1,2,5,10,15,26,37,48,54,60,66,67,68,72)

is not a sparse ruler since the length

cannot be expressed as a difference.

The “Wichmann Columns” Demonstration generates a column in the excess pattern by using only sparse rulers made by the first two Wichmann recipes,

and

, and extensions of these rulers.

indicates that a sparse ruler cannot be generated by

or by extending them.

indicates a generated sparse ruler with excess 0.

indicates a generated sparse ruler with excess 1.

We can see in the following Manipulate that length

18642-88=18554

cannot be covered by this method in the excess pattern column representing sparse rulers with 236 marks. Adjust the slider or hover over a value to get a Tooltip with the generated sparse ruler:

Out[]=

marks

250

{

166

165

164

163

162

161

160

159

158

157

156

155

154

153

152

151

150

149

148

147

146

145

144

143

142

141

140

139

138

137

136

135

134

133

132

131

130

129

128

127

126

125

124

123

122

121

120

119

118

117

116

115

114

113

112

111

110

109

108

107

106

105

104

103

102

101

100

}

rulers of length 20916 - x

Red pixels show where

extensions don’t solve

E≤1

in the excess pattern:

Out[]=

Lengths of sparse rulers generated by

and

are generated by order-2 polynomials differing by 1. The behavior of values generated by these polynomials is completely predictable and ultimately generates two weird sequences: sixsev and sixfiv:

Out[]=

recipe	length	marks
W 1	3+8r+4 2 r +3s+4rs	3+4r+s
W 2	2+8r+4 2 r +3s+4rs	3+4r+s

Sequence sixsev consists of infinite 6s and 7s. Similarly, the sequence sixfiv consists entirely of 6s and 5s:

cutoff=15;(*raisethecutofftogofarther*)sixsev=Drop[Flatten[Table[Table[{Table[6,{n}],7},{6}],{n,0,cutoff}]],1];sixfiv=Drop[Flatten[Table[Table[{Table[6,{n}],5},{6}],{n,0,cutoff}]],2];

In[]:=

Column[{Take[sixsev,80],Take[sixfiv,80]}]

Out[]=

{7,7,7,7,7,6,7,6,7,6,7,6,7,6,7,6,7,6,6,7,6,6,7,6,6,7,6,6,7,6,6,7,6,6,7,6,6,6,7,6,6,6,7,6,6,6,7,6,6,6,7,6,6,6,7,6,6,6,7,6,6,6,6,7,6,6,6,6,7,6,6,6,6,7,6,6,6,6,7,6}

{5,5,5,5,6,5,6,5,6,5,6,5,6,5,6,5,6,6,5,6,6,5,6,6,5,6,6,5,6,6,5,6,6,5,6,6,6,5,6,6,6,5,6,6,6,5,6,6,6,5,6,6,6,5,6,6,6,5,6,6,6,6,5,6,6,6,6,5,6,6,6,6,5,6,6,6,6,5,6,6}

What are the

(r,s)

values for the

and

recipe in column 236 with

E=0

? What are the Wichmann recipe column zeros (WRCZ)? Code for WRCZ, based on sixsev and sixfiv, is shown in the initialization section. Column 236 in the excess pattern has seven sets of

(r,s)

values. The height of a column is roughly (2/3)*column, 159 in this case. The average possible extension

(r+1)

is roughly a quarter of the column height:

In[]:=

WRCZ[236]

Out[]=

{{36,89},{37,85},{38,81},{39,77},{40,73},{41,69},{42,65}}

In the excess pattern, each column divides into quarter sections with the same size as the extension lengths of

and

. If we can show that eventually there are at least four reasonably spaced

and

zeros in each column, we’re done:

In[]:=

Row[{Graphics[{{#[[1]],Rectangle[#[[2]]]}&/@coordinated},ImageSize{480,318},PlotRange{{3,159},{0,106}}]}]

The last column in the excess pattern without four reasonably spaced

and

zeros is column 880:

In[]:=

WRCZ[880]

Out[]=

{{140,317},{141,313},{142,309},{143,305},{144,301},{145,297},{146,293},{147,289},{148,285},{149,281},{150,277},{151,273},{152,269}}

Here are the lengths generated by these pairs:

In[]:=

zero880=(3+8r+4r^2+3s+4rs)/.{r#[[1]],s#[[2]]}&/@WRCZ[880]

Out[]=

{257994,258126,258234,258318,258378,258414,258426,258414,258378,258318,258234,258126,257994}

Notice how the generated lengths for this column are palindromic, a worst-case scenario. Length 257992 isn’t covered by the zeros here and is out of reach of the last zero in the previous column,

257839+146+1=257986

The acceleration of change between

E=0

values generated by

is a constant –24. The spacing between zeros is predictable:

In[]:=

Differences[Differences[zero880]]

Out[]=

{-24,-24,-24,-24,-24,-24,-24,-24,-24,-24,-24}

Only four reasonably spaced zeros are needed per column. The polynomial

3+8r+4

+3s+4rs

inexorably offers more and more zeros. Column 880 is the last column where

extensions can fail:

In[]:=

ListPlot[Table[Length[WRCZ[n]],{n,50,3000}]]

Out[]=

Another plot showing that extensions overwhelm the differences:

Out[]=

All integer lengths greater than 257992 (corresponding to 880 marks) are excess-01 rulers made by extensions to Wichmann recipe 1.

All integer lengths greater than 119206 (corresponding to 598 marks) are excess-01 rulers made by extensions and double extensions to Wichmann recipe 1. Here’s an example double extension that covers length 257992:

In[]:=

SplitExtensions[Last[SplitExtensions[WichmannRuler[WichmannRecipes[[1]],{146,292}]]]][[6]]

Out[]=

{{1,147,293,587,294,1,147,6},{146,1,146,292,147,146,1,1}}

In[]:=

Dot@@%

Out[]=

257992

Part 2,
L≤257992

We can programmatically verify the conjecture with precalculated rulers to length 2020, or to length 257992 with more running time. This tallies the number of 0s and 1s for the excess, up to length 2020:

In[]:=

Tally[Sparseness[SplitToRuler[#]]&/@Take[sparsedata,2020]]

Out[]=

{{0,1289},{1,731}}

I knew Robison found rulers to length 213, so I wanted to show samples. But except for the counts, all the ruler data was lost. I rebuilt it, but without access to the Intel superclusters. This search started with trying to make an image showing a row of column-presented sparse rulers from length 1 to length 213.

First, here are sparse rulers up to length 36 with the mark positions converted into pixel positions. The gray rows indicate that the sparse ruler for that length is unique:

{0,1}

{0,1,2}

{0,1,3}

{0,1,2,4}

{0,1,2,5}

{0,1,4,6}

{0,1,2,3,7}

{0,1,2,5,8}

{0,1,2,6,9}

{0,1,2,3,6,10}

{0,1,2,3,7,11}

{0,1,2,3,8,12}

{0,1,2,6,10,13}

{0,1,2,3,4,9,14}

{0,1,2,3,4,10,15}

{0,1,2,3,8,12,16}

{0,1,2,3,8,13,17}

{0,1,2,3,4,5,12,18}

{0,1,2,3,4,9,14,19}

{0,1,2,3,4,10,15,20}

{0,1,2,3,4,10,16,21}

{0,1,2,3,8,13,18,22}

{0,1,2,11,15,18,21,23}

{0,1,2,3,4,5,12,18,24}

{0,1,2,3,4,5,12,19,25}

{0,1,2,3,4,10,16,21,26}

{0,1,2,3,4,10,16,22,27}

{0,1,2,13,18,21,24,27,28}

{0,1,2,14,18,21,24,27,29}

{0,1,2,3,4,5,12,18,24,30}

{0,1,2,3,4,5,12,19,25,31}

{0,1,2,3,4,5,12,19,26,32}

{0,1,2,3,4,10,16,22,28,33}

{0,1,2,3,15,20,24,28,31,34}

{0,1,2,17,21,24,27,30,33,35}

{0,1,3,6,13,20,27,31,35,36}

The following plot is a transpose of the previous plot, extended to a length of 213. Each column represents a sparse ruler, with gray columns indicating uniqueness. These columns line up with the log plot after the next paragraph:

And here is a log plot of the number of distinct sparse rulers of length

to length 213, which shows that there are usually fewer

E=0

(blue) rulers and more

E=1

(brown) rulers. Points on the bottom correspond to unique rulers (and a gray column in the previous image):

Length

n=59

has 15990 distinct sparse rulers. These counts are sequence A103300. Out of the first 213 lengths, 31 of them have a unique sparse ruler. I suspect many lengths above 213 have unique or hard-to-find minimal representations.

The following log plot shows the number of distinct sparse rulers and conjectured sparse rulers of length

to length 10501, found in the search that produced 2,016,735 sparse rulers and conjectured sparse rulers:

In the downloadable notebook I show many ways to use a sparse ruler to generate new sparse rulers, which can in turn make more sparse rulers. I call this process recursion. Processing shorter-length rulers gave better results and needed less time, so rulers of a length above 4000 were initially not used to produce more rulers. After cracking the particularly hard length 1792, I extended the new ruler processing to length 7000 in hopes of finding an example of length 5657. After checking

E∈(0,1)

to 10501, I temporarily stopped the search.

Various regularities and patterns can be seen, but part of the change in pattern is due to arbitrary cutoffs in processing at 4000 and 7000. One curious case is

n=2611

E=0

with 363 rulers. Nearby is

n=2627

E=1

with 3619 rulers. If an

E=-1

sparse ruler exists, the first clue will likely be an

E=0

length with an unusually high count of examples.

An infinite number of complete rulers with

E∈(0,1)

can be made using all 2069 Wichmann-like recipes. How well does the catalog of Wichmann recipes work? To find out, I tried the following overnight run:

In[]:=

addedrulers=Table[With[{wich=FindWichmann[hh][[1,1]]},WichmannRuler[WichmannRecipes[[wich[[1]]]],wich[[3]]]],{hh,10520,17553}]

How do these 7033 new complete rulers match up with the pattern? About 6448 rulers match the previous pattern well. About 587 rulers appear to be violations:

Adding an extension is the simplest way to make new complete rulers. Let us try that. This code (which will also require a long running time) finds 586 lengths that can be improved this simple way:

In[]:=

oldsparsedata=

List

;rulerexcess=oldrulerexcess;newrulers=First/@SplitBy[Sort[{Last[#],Length[#],RulerToSplit[#]}&/@Complement[Union[SparseCheckImprove/@Flatten[Table[With[{ruler=SplitToRuler[#]},Append[ruler,Last[ruler]+n]],{n,1,40}]&/@Drop[oldsparsedata,10501],1]],{False}]],First];Dolength=newrulers[[index,1]];rulerexcess[[length]]=newrulers[[index,2]]-Round

3length+9/4

;sparsedata[[length]]=newrulers[[index,3]],{index,1,Length[newrulers]};

After that trial, a single exception to the sparse ruler conjecture remains in this range, at

n=16617

. The pattern cleaned up nicely:

I did not expect this trial to work so well.

I had to find an example for

16617

. The tools in this notebook gave me an example in a few hours. The sparse ruler conjecture is true to at least 17553:

In[]:=

sparse16617={{1,75,1,75,149,74,42,1,19,1},{32,1,4,37,73,37,1,32,2,4}};temp=SplitToRuler[sparse16617];{Last[temp],Length[temp],Sparseness[temp]}

Out[]=

{16617,224,1}

Length 16617 is the final difficult value for

E=1

. All lengths 16618 to 257992 can be solved with the 2069 known Wichmann recipes or extensions.

After the initialization section in the notebook is ReasonableRuler, which will find a ruler with excess 0 or 1 for any given positive integer length. Here’s a ruler for length 100000:

In[]:=

ReasonableRuler[100000]

Out[]=

{{1,92,183,367,184,1,85},{91,1,91,180,92,91,1}}

The function generates example sparse rulers with E = 0 or 1 for all lengths up to 257992 within a few minutes.

QED.

Conjectures and Wrap-Up

The Leech bounds can be improved. The Leech upper and lower bounds drift far away from the best-known values for minimal marks

ListPlot[{Table[Sqrt[2.434n]-(Sqrt[3n+9/4]),{n,1,17553}],Table[rulerexcess[[n]]+Round[Sqrt[3n+9/4]]-Sqrt[3n+9/4],{n,1,17553}],Table[Sqrt[3.348n]-(Sqrt[3n+9/4]),{n,1,17553}]},AspectRatio1/5]

I know of 11 rulers with the following properties:
1.

E=0

and complete
2. Length greater than 213
3. Excess fraction ≥ 4/7
4. Not built with a Wichmann recipe

length	excess fraction	ruler
225	3/5	{{1,3,2,8,17,1,9,1},{3,1,1,3,9,1,4,3}}
225	3/5	{{1,4,8,17,9,6,3,9,1},{4,1,2,9,1,1,1,3,3}}
225	3/5	{{1,2,7,9,1,9,17,8,5,1},{3,1,1,2,1,1,9,3,1,3}}
225	3/5	{{1,3,5,3,8,17,9,2,7,2,9,1},{2,2,1,1,2,9,1,1,1,1,2,2}}
320	3/5	{{1,3,10,21,11,1,11,1},{4,2,4,10,1,1,4,4}}
320	3/5	{{1,2,9,11,1,11,21,10,6,1},{4,1,1,2,1,2,10,4,1,4}}
341	7/12	{{1,3,10,21,11,1,11,1},{4,2,4,11,1,1,4,4}}
341	7/12	{{1,2,9,11,1,11,21,10,6,1},{4,1,1,2,1,2,11,4,1,4}}
456	7/12	{{1,3,4,12,25,13,1,13,1},{5,1,1,5,12,2,1,4,5}}
481	4/7	{{1,3,4,12,25,13,1,13,1},{5,1,1,5,13,2,1,4,5}}
616	4/7	{{1,3,5,14,29,15,1,15,1},{6,1,1,6,14,3,1,4,6}}

Conjectures

(1) Peter Luschny’s optimal ruler conjecture is true;

=13

is the last non-Wichmann optimal sparse ruler(2) The lower bound for



3n+9/4



(3) The list of 11 rulers immediately above is complete

I’ve shown how approaching the problem computationally with the Wolfram Language can help not only to solve but also construct a proof for the sparse rulers problem that has historically fascinated so many. Make your own mark—to continue exploring, be sure to download this post's notebook, which features lots of additional code, the connection between sparse rulers and graceful graphs, and a longer discussion for finding sparse rulers. Can any of the current excess values be improved? Are there more excellent Wichmann-like recipes? I would love to know—submit your recipes in the comments or to Wolfram Community!

Many thanks to T. Sirgedas, A. Robison, G. Beck and N. J. A. Sloane for help with this search.

References

Leech, J. “On the Representation of 1, 2, ..., n by Differences.” Journal of the London Mathematical Society s1-31.2 (1956): 160–169.

Luschny, P. “The Optimal Ruler Conjecture.” The On-Line Encyclopedia of Integer Sequences.

Pegg, E. “Sparse Ruler Conjecture.” Wolfram Community.

Rédei, L. and A. Rényi. “On the Representation of the Numbers 1, 2, ..., n by Means of Differences.” Matematicheskii Sbornik 24(66), no. 3 (1949): 385–389.

Robison, A. D. “Parallel Computation of Sparse Rulers.” Intel Developer Zone.

Rokicki, T. and G. Dogon. “Golomb Rulers: Pushing the Limits.” cube20.org.

Wichmann, B. “A Note on Restricted Difference Bases.” Journal of the London Mathematical Society s1-38.1 (1963): 465–466. doi:10.1112/jlms/s1-38.1.465.

Wikipedia Contributors. “Sparse Ruler.” Wikipedia, the Free Encyclopedia.

For Downloadable Notebook

Lehmer Code and Graceful Graphs


Using Sparse Rulers: Graceful Graphs


Finding Sparse Rulers


Initialization


Reasonable Ruler


Cite this as: Ed Pegg, "Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof" from the Notebook Archive (2020), https://notebookarchive.org/2020-02-5kn77cd

																	124	139	154	169	184	199
																	125	140	155	170	185	200
																	126	141	156	171	186	201
																	127	142	157	172	187	202
											58	69	80	91	102	113	128	143	158	173	188	203
											59	70	81	92	103	114	129	144	159	174	189	204
											60	71	82	93	104	115	130	145	160	175	190	205
											61	72	83	94	105	116	131	146	161	176	191	206
					16	23	30	37	44	51	62	73	84	95	106	117	132	147	162	177	192	207
					17	24	31	38	45	52	63	74	85	96	107	118	133	148	163	178	193	208
					18	25	32	39	46	53	64	75	86	97	108	119	134	149	164	179	194	209
					19	26	33	40	47	54	65	76	87	98	109	120	135	150	165	180	195	210
1	4	7	10	13	20	27	34	41	48	55	66	77	88	99	110	121	136	151	166	181	196	211
2	5	8	11	14	21	28	35	42	49	56	67	78	89	100	111	122	137	152	167	182	197	212
3	6	9	12	15	22	29	36	43	50	57	68	79	90	101	112	123	138	153	168	183	198	213
3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

																	124	139	154	169	184	199
																	125	140	155	170	185	200
																	126	141	156	171	186	201
																	127	142	157	172	187	202
											58	69	80	91	102	113	128	143	158	173	188	203
											59	70	81	92	103	114	129	144	159	174	189	204
											60	71	82	93	104	115	130	145	160	175	190	205
											61	72	83	94	105	116	131	146	161	176	191	206
					16	23	30	37	44	51	62	73	84	95	106	117	132	147	162	177	192	207
					17	24	31	38	45	52	63	74	85	96	107	118	133	148	163	178	193	208
					18	25	32	39	46	53	64	75	86	97	108	119	134	149	164	179	194	209
					19	26	33	40	47	54	65	76	87	98	109	120	135	150	165	180	195	210
1	4	7	10	13	20	27	34	41	48	55	66	77	88	99	110	121	136	151	166	181	196	211
2	5	8	11	14	21	28	35	42	49	56	67	78	89	100	111	122	137	152	167	182	197	212
3	6	9	12	15	22	29	36	43	50	57	68	79	90	101	112	123	138	153	168	183	198	213
3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Hitting All the Marks: Exploring New Bounds for Sparse Rulers and a Wolfram Language Proof

Some History

New Discoveries

Proof That E≤1

Part 1, L>257992

Part 2, L≤257992

Conjectures and Wrap-Up

References

Lehmer Code and Graceful Graphs 

Using Sparse Rulers: Graceful Graphs

Finding Sparse Rulers

Initialization

Reasonable Ruler

Proof That
E≤1

Part 1,
L>257992

Part 2,
L≤257992

Lehmer Code and Graceful Graphs


Using Sparse Rulers: Graceful Graphs


Finding Sparse Rulers


Initialization


Reasonable Ruler


																	124	139	154	169	184	199
																	125	140	155	170	185	200
																	126	141	156	171	186	201
																	127	142	157	172	187	202
											58	69	80	91	102	113	128	143	158	173	188	203
											59	70	81	92	103	114	129	144	159	174	189	204
											60	71	82	93	104	115	130	145	160	175	190	205
											61	72	83	94	105	116	131	146	161	176	191	206
					16	23	30	37	44	51	62	73	84	95	106	117	132	147	162	177	192	207
					17	24	31	38	45	52	63	74	85	96	107	118	133	148	163	178	193	208
					18	25	32	39	46	53	64	75	86	97	108	119	134	149	164	179	194	209
					19	26	33	40	47	54	65	76	87	98	109	120	135	150	165	180	195	210
1	4	7	10	13	20	27	34	41	48	55	66	77	88	99	110	121	136	151	166	181	196	211
2	5	8	11	14	21	28	35	42	49	56	67	78	89	100	111	122	137	152	167	182	197	212
3	6	9	12	15	22	29	36	43	50	57	68	79	90	101	112	123	138	153	168	183	198	213
3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25