10
$\begingroup$

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?

Sparse Ruler Pattern

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".

octic graceful graph

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
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Jul 12, 2019 at 16:30
  • 3
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Jul 12, 2019 at 16:45
  • $\begingroup$ 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. $\endgroup$
    – Ed Pegg
    Jul 12, 2019 at 17:26
  • 3
    $\begingroup$ 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$ . $\endgroup$
    – David E Speyer
    Jul 12, 2019 at 17:53
  • 1
    $\begingroup$ That's really cool Ed! $\endgroup$
    – Riley Carney
    Jul 15, 2019 at 0:07

1 Answer 1

Reset to default
2
$\begingroup$

I proved it.
In short, for values over 120000, just add an extra mark or two at the end of a Wichmann construction to get an excess 0 or 1 ruler for all lengths.
For values under 12000, solutions for all tricky lengths like 1792 were found with a 3 month computer search.

See Hitting all the Marks for more details.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .