# Difference Triangles

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?

• If there's no other condition than "no misses", isn't it trivial to "grow" a given difference triangle by adding the next larger integer to the left or to the right of the first row?
– Max
May 28, 2021 at 13:51
• For order 8 no misses, you could add a 25 and be 11 away from 36. But the optimal order 8 is closer to 36 than that. May 28, 2021 at 14:59
• Probably, but if you say "largest known is 7", that sounds as if you didn't knew any N=8 solution.
– Max
May 28, 2021 at 18:26

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

• I'm sure you can find order $8$ no misses solution with largest value $30$ ;) Jun 4, 2021 at 11:04
• Yes, this is the only improvement: for $8$-no-misses. And I have no better solutions for $n=9$. (my current "records" are: $40$ and $96$ for $n=10$; $44$ and $136$ for $n=11$ so far). Jun 4, 2021 at 14:30
• @Oleg567 I finally found the 30! It was hard. Jun 6, 2021 at 1:05
• Congrats! Now you have both optimal solutions for $n=8$. And optimal solution for $9$-no-repeats. (are you ready to next step: improve $9$-no-misses value a bit? ;) Jun 6, 2021 at 5:28
• I performed exhaustive check for $n=8$ and for $n=9$, no-repeats. Yes, described already the sketch of algorithm in another answer. Jun 6, 2021 at 15:21

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

• This is great work! So now we have optimal solutions up to $n \leq 10$ for both problem types? Are these results worth adding to the OEIS? Are we interested in solutions for $n > 10$? Jun 8, 2021 at 1:25
• Thank you, @Dmitry. Only $n$-no-repeats problem is checked for $n\le 10$. $n$-no-misses problem is much harder for me) (in terms of exhaustive search). I still checking $38$-solution existence for $n=9$. Don't know about adding to OEIS; any option. And yes, I'm interested in solutions for $n>10$: interesting to know the asymptotic behavior etc. Jun 8, 2021 at 7:05

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)$$.