# Sparse Ruler Conjecture

Sparse Ruler Conjecture, hard: If a minimal sparse ruler of length $$n$$ has $$m$$ marks,
easy: $$m-\lceil \sqrt{3*n +9/4} \rfloor \in (0,1)$$.
hard: $$m+\frac{1}{2} \ge \sqrt{3 \times n +9/4} \ge m-1$$.

Can anyone find a counterexample? At Sparse Rulers I have data on sparse rulers up to length 1750.

||||...................|....|...|...|...|...|..|..| has marks at 0, 1, 2, 3, 23, 28, 32, 36, 40, 44, 47, 50.
This is a 12-mark ruler of length 50 that can measure any length from 1 to 50.

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. Up to length 213, $$k=0$$ except for lengths 51, 59, 69, ... ( A308766) where $$k=1$$, the black square values in the pattern below.. Minimal marks are listed in A046693. The best known $$k$$ values to 4443 are shown below, verified to length 213. Values increment down, then across. Bottom row values are Wichmann rulers A289761. Can any of these values be lowered?

These sparse rulers are vital for finding various high-valence graceful graphs, such as the one below, which was found with this data, along with hundreds of other previously undetermined graceful graphs. That link also has sparse rulers of length 601 to 1100. 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.

Sequence A103300, Number of perfect rulers, has zero values at positions 135, 136, 149, 150, 151, 164, 165, 166, 179, 180, 181, 195, 196, 209, 210, 211. The minimal rulers for these lengths have one more mark. I have examples of all these minimal rulers, but I'd like to get counts to make a sequence "Number of minimal sparse rulers".

The following length 69 sparse ruler has 15 marks.
0 1 2 3 4 5 6 7 16 25 34 43 52 61 69
gaps are 1 1 1 1 1 1 1 9  9  9  9  9  9  8  or 1×7 9×6 8×1
69 15 1 | 1×7 9×6 8×1 -- representation of ruler
length marks excess | gaps
excess = marks - round(sqrt(3×length + 9/4))
To length 1750 all minimal sparse rulers have excess 0 or 1

1 2 0 | 1×1
2 3 0 | 1×2
3 3 0 | 1×1 2×1
4 4 0 | 1×2 2×1
5 4 0 | 1×2 3×1
6 4 0 | 1×1 3×1 2×1
7 5 0 | 1×3 4×1
8 5 0 | 1×2 3×2
9 5 0 | 1×2 4×1 3×1
10 6 0 | 1×3 3×1 4×1
11 6 0 | 1×3 4×2
12 6 0 | 1×3 5×1 4×1
13 6 0 | 1×2 4×2 3×1
14 7 0 | 1×4 5×2
15 7 0 | 1×3 4×3
16 7 0 | 1×3 5×1 4×2
17 7 0 | 1×3 5×2 4×1
18 8 0 | 1×5 7×1 6×1
19 8 0 | 1×4 5×3
20 8 0 | 1×4 6×1 5×2
21 8 0 | 1×4 6×2 5×1
22 8 0 | 1×3 5×3 4×1
23 8 0 | 1×2 9×1 4×1 3×2 2×1
24 9 0 | 1×4 5×4
25 9 0 | 1×5 7×2 6×1
26 9 0 | 1×4 6×2 5×2
27 9 0 | 1×4 6×3 5×1
28 9 0 | 1×2 11×1 5×1 3×3 1×1
29 9 0 | 1×2 12×1 4×1 3×3 2×1
30 10 0 | 1×5 7×1 6×3
31 10 0 | 1×5 7×2 6×2
32 10 0 | 1×5 7×3 6×1
33 10 0 | 1×4 6×4 5×1
34 10 0 | 1×3 12×1 5×1 4×2 3×2
35 10 0 | 1×2 15×1 4×1 3×4 2×1
36 10 0 | 1×1 2×1 3×1 7×3 4×2 1×1
37 11 0 | 1×6 8×3 7×1
38 11 0 | 1×5 7×3 6×2
39 11 0 | 1×5 7×4 6×1
40 11 0 | 1×3 14×1 5×1 4×3 3×2
41 11 0 | 1×2 18×1 4×1 3×5 2×1
42 11 0 | 1×3 16×1 5×1 4×3 3×2
43 11 0 | 1×1 2×1 3×1 7×4 4×2 1×1
44 12 0 | 1×6 8×3 7×2
45 12 0 | 1×6 8×4 7×1
46 12 0 | 1×5 7×5 6×1
47 12 0 | 1×3 16×1 5×2 4×3 3×2
48 12 0 | 1×3 18×1 5×1 4×4 3×2
49 12 0 | 1×3 21×1 5×1 1×1 4×4 3×1
50 12 0 | 1×3 20×1 5×1 4×4 3×2

• Basic comment: The obvious lower bound is $\sqrt{2n}$, since we must have $\binom{m}{2} \geq n$. I agree that your data suggests that $\sqrt{3n}$, not $\sqrt{2n}$ is right. I wonder why. – David E Speyer Jul 12 '19 at 16:30
• I assume you are already familiar with the work of John Leech doi.org/10.1112/jlms/s1-31.2.160 ? He provides bounds with asymtotic behavior $\sqrt{2.434 n}$ and $\sqrt{3.348 n}$. Also, if you can achieve $(m_0, n_0)$, then he can achieve a growth rate of $\sqrt{ \tfrac{(m_0+2)^2}{n_0+1} n}$; combining that with your large examples should improve a lot on the upper bound. – David E Speyer Jul 12 '19 at 16:45
• I've found hundreds of Wichmann-style rules that can build sparse rulers for about 50% of higher n values with a lower bound of rounded $\sqrt{3n+9/4}$. There are likely thousands of Wichmann-style rules. – Ed Pegg Jul 12 '19 at 17:26
• This seems like you should publish it. Leech shows that $\lim_{n \to \infty} m^2/n$ exists, so if you can achieve $3$ infinitely often, then that is an upper bound for the limit. I skimmed the papers in MathSciNet that cite Leech, and they only make tiny improvements on $3.348$ . – David E Speyer Jul 12 '19 at 17:53
• That's really cool Ed! – Riley Carney Jul 15 '19 at 0:07