Difference triangle sets

IBM - Personal communication

The tables below give the best lower bounds on the sizes of difference triangle sets known. Following each entry is a pointer to the appropriate reference in the list below the table. References are generally the first (known to me) to prove a particular bound. Values known to be optimal are linked to the appropriate place in a separate list of optimal difference triangle sets.

Last update May 17, 2004.

Table 1a - Lower bounds for M(I,J)

J\I 1 2 3 4 5 6 7 8
1 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8 T
2 3 T 7 F 10 F 12 T 15 T 19 F 22 F 24 T
3 6 T 13 RB 19 RB 24 T 30 T 36 T 42 T 48 T
4 11 RB 22 RB 32 GM 41 GM 51 F 60 T 71 F 80 T
5 17 RB 34 GM 49 GM 64 JS2 79 JS5 92 JS5 108 JS5 123 JS5
6 25 RB 51 GM 72 JS2 94 JS3 113 JS5 136 JS5 158 JS5 181 JS5
7 34 WM 70 JS2 100 JS5 124 JS5 155 JS5 186 JS5 217 JS5 247 JS5
8 44 WM 94 JS2 124 JS5 164 JS5 205 JS5 245 JS5 286 JS5 327 JS5
9 55 WM 121 JS5 158 JS5 209 JS5 261 JS5 313 JS5 365 JS5 417 JS5
10 72 WM 132 JS5 197 JS5 261 JS5 326 JS5 391 JS5 456 JS5 520 JS5
11 85 JR1 161 JS5 240 JS5 320 JS5 399 JS5 478 JS5 558 JS5 637 JS5
12 106 JR2 194 JS5 289 JS5 385 JS5 480 JS5 576 JS5 671 JS5 767 JS5
13 127 JS1 229 LN 343 JS5 456 JS5 569 JS5 683 JS5 796 JS5 909 JS5
14 151 JS1 268 LN 401 JS5 534 JS5 667 JS5 800 JS5 933 JS5 1066 JS5
15 177 JS1 311 JS5 464 JS5 618 JS5 772 JS5 926 JS5 1080 JS5 1234 JS5

Table 1a - Lower bounds for M(I,J)
J\I	1	2	3	4	5	6	7	8
1	1 T	2 T	3 T	4 T	5 T	6 T	7 T	8 T
2	3 T	7 F	10 F	12 T	15 T	19 F	22 F	24 T
3	6 T	13 RB	19 RB	24 T	30 T	36 T	42 T	48 T
4	11 RB	22 RB	32 GM	41 GM	51 F	60 T	71 F	80 T
5	17 RB	34 GM	49 GM	64 JS2	79 JS5	92 JS5	108 JS5	123 JS5
6	25 RB	51 GM	72 JS2	94 JS3	113 JS5	136 JS5	158 JS5	181 JS5
7	34 WM	70 JS2	100 JS5	124 JS5	155 JS5	186 JS5	217 JS5	247 JS5
8	44 WM	94 JS2	124 JS5	164 JS5	205 JS5	245 JS5	286 JS5	327 JS5
9	55 WM	121 JS5	158 JS5	209 JS5	261 JS5	313 JS5	365 JS5	417 JS5
10	72 WM	132 JS5	197 JS5	261 JS5	326 JS5	391 JS5	456 JS5	520 JS5
11	85 JR1	161 JS5	240 JS5	320 JS5	399 JS5	478 JS5	558 JS5	637 JS5
12	106 JR2	194 JS5	289 JS5	385 JS5	480 JS5	576 JS5	671 JS5	767 JS5
13	127 JS1	229 LN	343 JS5	456 JS5	569 JS5	683 JS5	796 JS5	909 JS5
14	151 JS1	268 LN	401 JS5	534 JS5	667 JS5	800 JS5	933 JS5	1066 JS5
15	177 JS1	311 JS5	464 JS5	618 JS5	772 JS5	926 JS5	1080 JS5	1234 JS5

Table 1b - Lower bounds for M(I,J)

J\I 9 10 11 12 13 14 15
1 9 T 10 T 11 T 12 T 13 T 14 T 15 T
2 27 T 31 F 34 F 36 T 39 T 43 F 46 F
3 54 T 60 T 66 T 72 T 78 T 84 T 90 T
4 91 F 100 T 111 F 120 T 131 F 140 T 151 F
5 138 JS5 153 JS5 168 JS5 183 JS5 199 JS5 214 JS5 229 JS5
6 203 JS5 225 JS5 248 JS5 270 JS5 292 JS5 315 JS5 337 JS5
7 278 JS5 309 JS5 339 JS5 370 JS5 401 JS5 431 JS5 462 JS5
8 367 JS5 408 JS5 448 JS5 489 JS5 529 JS5 570 JS5 610 JS5
9 469 JS5 521 JS5 572 JS5 624 JS5 676 JS5 728 JS5 780 JS5
10 585 JS5 650 JS5 715 JS5 780 JS5 844 JS5 909 JS5 974 JS5
11 716 JS5 796 JS5 875 JS5 954 JS5 1034 JS5 1113 JS5 1193 JS5
12 862 JS5 958 JS5 1054 JS5 1149 JS5 1245 JS5 1340 JS5 1436 JS5
13 1023 JS5 1136 JS5 1249 JS5 1363 JS5 1476 JS5 1589 JS5 1703 JS5
14 1198 JS5 1331 JS5 1464 JS5 1597 JS5 1730 JS5 1863 JS5 1996 JS5
15 1338 JS5 1542 JS5 1696 JS5 1850 JS5 2003 JS5 2157 JS5 2311 JS5

Table 1b - Lower bounds for M(I,J)
J\I	9	10	11	12	13	14	15
1	9 T	10 T	11 T	12 T	13 T	14 T	15 T
2	27 T	31 F	34 F	36 T	39 T	43 F	46 F
3	54 T	60 T	66 T	72 T	78 T	84 T	90 T
4	91 F	100 T	111 F	120 T	131 F	140 T	151 F
5	138 JS5	153 JS5	168 JS5	183 JS5	199 JS5	214 JS5	229 JS5
6	203 JS5	225 JS5	248 JS5	270 JS5	292 JS5	315 JS5	337 JS5
7	278 JS5	309 JS5	339 JS5	370 JS5	401 JS5	431 JS5	462 JS5
8	367 JS5	408 JS5	448 JS5	489 JS5	529 JS5	570 JS5	610 JS5
9	469 JS5	521 JS5	572 JS5	624 JS5	676 JS5	728 JS5	780 JS5
10	585 JS5	650 JS5	715 JS5	780 JS5	844 JS5	909 JS5	974 JS5
11	716 JS5	796 JS5	875 JS5	954 JS5	1034 JS5	1113 JS5	1193 JS5
12	862 JS5	958 JS5	1054 JS5	1149 JS5	1245 JS5	1340 JS5	1436 JS5
13	1023 JS5	1136 JS5	1249 JS5	1363 JS5	1476 JS5	1589 JS5	1703 JS5
14	1198 JS5	1331 JS5	1464 JS5	1597 JS5	1730 JS5	1863 JS5	1996 JS5
15	1338 JS5	1542 JS5	1696 JS5	1850 JS5	2003 JS5	2157 JS5	2311 JS5

References for the tables above.

T - trivial: The bound M(I,J)>= I*(J*(J+1))/2 follows trivially from the fact that all the differences are distinct.
F - folklore: The above trivial bound can be improved by 1 in some cases by a simple parity argument. When J is even the sum of the differences in the top J/2 rows of a difference triangle equals the sum of the differences in the bottom J/2 rows of the difference triangle. Hence the sum of all the differences is even. So M(I,J) = I*(J*(J+1))/2 is impossible when J is even and the sum of the first I*(J*(J+1))/2 integers is odd. This means M(I,2) >= 3*I + 1 when I = 2,3 mod 4 and M(I,4) >= 10*I + 1 when I = 1 mod 2.
RB - John P. Robinson and Arthur J. Bernstein: J. P. Robinson and A. J. Bernstein, "A class of binary recurrent codes with limited error propagation", IEEE Transactions on Information Theory, IT-13(1967), p. 106-113.
WM - William Mixon (unpublished, cited in): M. Gardner, "Mathematical games", Scientific American, June 1972, p. 116-118.
JR1 - John P. Robinson: J. P. Robinson "Optimal golomb rulers" IEEE Transactions on Computers, C-28(1979), p. 943-944.
JR2 - John P. Robinson: J. P. Robinson "Addendum to "Optimal golomb rulers"" IEEE Transactions on Computers, C-32(1983), p. 201.
GM - G. Martin: G. Martin, "Optimal convolutional self-orthogonal codes with an application to digital radio", Proc. IEEE International Conference on Communications, 1985, p. 1249-1253.
JS1 - James B. Shearer: J. B. Shearer, "Some New Optimum Golomb Rulers", IEEE Transactions on Information Theory, 36(1990), p. 183-184.
JS2 - James B. Shearer: J. B. Shearer, "Some New Difference Triangle Sets", IBM RC 16610, 3/5/1991.
published in part as
J. B. Shearer, "Some New Difference Triangle Sets", Journal of Combinatorial Mathematics and Combinatorial Computing, 27(1998), p. 65-72.
JS3 - James B. Shearer: Unpublished exhaustive search (completed May 17,2004) using a program similar to that described in JS2 .
JS5 - James B. Shearer: J. B. Shearer, "Improved LP Lower Bounds for Difference Triangle Sets", The Electronic Journal of Combinatorics, 6(1999), #R31.