Difference Triangles

Question

In a difference triangle, a row of $n$ integers is given, then their differences are written underneath, and then another row of difference is added, until there is a triangle of $n (n+1)/2$ integers. For example:

The above triangle also has the property that it has 15 distinct values with no values from 1 to 15 either missing or repeated. According to this query, this is the last difference triangle with nothing missing and nothing repeated.

That's similar to the last perfect ruler, with marks ${0,1,3,6}$. These marks measure all differences 1 to 6 with no lengths missing or repeated. For longer rulers, there are two options.

1. No repeats allowed. The smallest ruler with $n$ marks is called a Golomb ruler.
2. No missing values. The longest ruler with $n$ marks is an optimal sparse ruler.

We can look at difference triangles with these same conditions.

Order 6. $T_6 = 21$.
The smallest difference triangle with no repeats has large value 22 ($T_6 +1$) and misses 15.
The largest difference triangle with no misses has large value 20 ($T_6 -1$) and repeats 4.

Order 7. $T_7=28$.
The smallest known difference triangle with no repeats has large value 33 ($T_7 +5$) and misses ${16, 20, 22, 29, 30}$.
The largest known difference triangle with no misses has large value 24 ($T_7 -4$) and repeats 1 and 3.

What happens with orders 8 and beyond? With $T_8=36$, how close can we get to $36$ with either no repeats or no misses?

Answer 1

(Not an answer. Simply short algorithm description and some of results)

If denote upper row of the triangle as $$ (t_1, t_2, \ldots, t_{n-1}, t_n), \tag{1} $$ then (w.l.o.g.) we'll consider only rows with $t_1 \le t_n$ (if $t_1=t_n$, then $t_2 \le t_{n-1}$ and so on).

---

To find largest difference triangle with no misses for relatively small $n$ $(n \le 9)$, one can apply exhaustive search for upper row (I'm unable to find smarter deterministic algorithm).
Rough estimation:
$n=7$:
up to $28^7 \approx 13.5 \times 10^9$ tests to check the value $28$ for optimality;
up to $27^7 \approx 10.5 \times 10^9$ tests to check the value $27$ for optimality;
...

$n=8$:
up to $36^8 \approx 2.8 \times 10^{12}$ tests to check the value $36$ for optimality;
up to $35^8 \approx 2.3 \times 10^{12}$ tests to check the value $35$ for optimality;
...

This way,
"$8$-no-misses" problem has three $30$-solutions (only upper rows are listed here):

(9, 28, 30, 5, 27, 24, 3, 29)

(16, 30, 28, 1, 5, 3, 29, 20)

(18, 4, 28, 26, 1, 30, 21, 27)

and there are no $k$-solutions for $k\ge 31$.

"$9$-no-misses" problem has at least one $38$-solution

(19, 35, 34, 3, 36, 38, 11, 37, 32)

(I didn't check it completely for this time).

---

To find smallest difference triangle with no repeats for relatively small $n$ $(n\le 10)$, I used recursive triangle construction.

Let $(n,k)$-no-repeats triangle is triangle with upper row $(1)$, where $$t_j \le k, \; j=1,2,\ldots,n.$$ Then if $n$-triangle is $(n,k)$-no-repeats triangle, then its left $(n-1)$-triangle (with upper row $(t_1,t_2,\ldots,t_{n-1})$) has the same property:
it is $(n-1,k)$-no-repeats triangle. Which admits to apply recursion.

This way,
"$8$-no-repeats" problem has only one $44$-solution:

 (7, 33, 42, 3, 44, 43, 6, 29)

and no $k$-solutions for $k\le 43$.

"$9$-no-repeats" problem has only one $59$-solution:

 (17, 49, 58, 1, 55, 59, 13, 53, 43)

and no $k$-solutions for $k\le 58$.

"$10$-no-repeats" problem has only one $76$-solution:

 (45, 69, 12, 76, 73, 15, 75, 66, 16, 52) 

and no $k$-solutions for $k\le 75$.

"$11$-no-repeats" problem has at least one $102$-solution:

 (12, 77, 98, 19, 100, 95, 8, 102, 99, 16, 70) 

and no $k$-solutions for $k\le 78$ (currently checking cases $k\in[79 .. 102]$).

---

For larger $n$ heuristic or randomized algorithms can probably give (almost) optimal solutions. Actually algorithm developed by Dmitry Kamenetsky works pretty nice and fast: when I've seen his $(8,44)$ and $(9,59)$ (optimal!) results for smallest difference triangle with no repeats, my "records" were $(8, 45)$ and $(9, 66)$ at that time.

Answer 2

I don't have a nontrivial solution yet, but we can easily see that the "minimal default" $$ m(N) := T_N - \max_{S\in {\rm NoMiss}(N)} S, $$ where $T_N = N(N+1)/2$ and NoMiss($N$) is the set of all no-miss solutions of order $N$, satisfies the relation $$m(N+1) \le m(N)+ N-1.$$ Indeed, we can simply "grow" an order $N$ solution $S$ to $S'\in{\rm NoMiss}(N+1)$ by adjoining $\max(S)+1$ to the left or right of the first row of $S$. So we do know that $m(8) \le 11$, by adding a column starting with 25 to the left of the triangle $S_{20,21,3,22,9,24,23}$ you gave for $N=7$, with $m = 4 \ge m(7)$.

Answer 3

I wrote a hill-climbing algorithm that finds solutions. Here are my best results, but I don't know if any of them are optimal.

For order 7 no misses, I found 3 other solutions. Here is one:

10 24 21 22 3 23 8
14 3 1 19 20 15
11 2 18 1 5
9 16 17 4
7 1 13
6 12
6

For order 8 no repeats, I found one with largest value 44. It misses: 12, 20, 21, 25, 27, 31, 32, 35.

29 6 43 44 3 42 33 7
23 37 1 41 39 9 26
14 36 40 2 30 17
22 4 38 28 13
18 34 10 15
16 24 5
8 19
11

For order 8 no misses, I found a solution with largest value 30:

16 30 28 1 5 3 29 20
14 2 27 4 2 26 9
12 25 23 2 24 17
13 2 21 22 7
11 19 1 15
8 18 14
10 4
6

For order 9 no repeats, I found one with largest value 59. It misses: 15, 22, 27, 29, 31, 33, 34, 35, 38, 41, 44, 51, 52, 56.

43 53 13 59 55 1 58 49 17
10 40 46 4 54 57 9 32
30 6 42 50 3 48 23
24 36 8 47 45 25
12 28 39 2 20
16 11 37 18
5 26 19
21 7
14

For order 9 no misses, I found one with largest value 36:

36 5 34 33 27 32 2 35 14
31 29 1 6 5 30 33 21
2 28 5 1 25 3 12
26 23 4 24 22 9
3 19 20 2 13
16 1 18 11
15 17 7
2 10
8

For order 10 no misses, I found one with largest value 41:

22 38 2 41 37 3 36 40 5 19
16 36 39 4 34 33 4 35 14
20 3 35 30 1 29 31 21
17 32 5 29 28 2 10
15 27 24 1 26 8
12 3 23 25 18
9 20 2 7
11 18 5
7 13
6

For order 11 no misses, I found one with largest value 47:

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