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

[ IBM Research home page | James B. Shearer's home page | Up ]
[ IBM home page | Order | Search | Contact IBM | Legal ]