IBM - Personal communication

The tables below give the sizes of the best constructions 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 find an example of the given size. Values known to be optimal are linked to the appropriate place in a separate list of optimal difference triangle sets.

Last update July 2, 2004.

Table 1a - Upper 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 TS2 10 TS2 12 TS1 15 TS1 19 RD 22 RD 24 TS1
3 6 T 13 RB 19 RB 24 BBR1 30 BBR2 36 BKT 42 GM 48 GM
4 11 WB 22 RB 32 GM 41 GM 51 KTG 60 PL 71 KTG 80 PL
5 17 WB 34 GM 49 GM 64 JS2 79 JS5 97 JS3 115 JS3 132 JS3
6 25 WB 51 GM 72 JS2 94 JS3 122 JS3 149 JS3 174 JS3 204 JS2
7 34 WB 70 JS2 100 JS5 139 JS3 177 JS3 214 JS3 252 JS4 288 JS4
8 44 WM 94 JS2 135 JS3 194 JS3 245 JS3 295 JS3 339 JS4 398 JS4
9 55 RB 121 JS5 189 JS3 256 JS3 319 JS4 387 JS4 459 JS4 521 JS4
10 72 RB 154 JS3 248 JS3 330 JS3 427 JS3 507 JS4 592 JS4 677 JS4
11 85 RB 195 RB 313 TK 416 TK 539 JS4 648 JS4 745 JS4 848 JS4
12 106 JR2 250 RB 370 TK 520 TK 664 TK 798 AL 935 TK 1089 JS3
13 127 RB 288 RB 447 TK 599 TK 800 TK 967 TK 1138 TK 1321 TK
14 151 JS1 334 TK 526 TK 690 TK 866 AL 1134 TK 1319 TK 1510 AL
15 177 JS1 365 TK 593 TK 820 AL 1043 TK 1261 AL 1517 TK 1713 TK

Table 1b - Upper 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 TS1 31 RD 34 RD 36 TS1 39 TS1 43 RD 46 RD
3 54 GM 60 GM 66 GM 72 KTG 78 KTG 84 TK 90 TK
4 91 JS5 100 KTG 112 JS4 124 JS4 135 JS4 145 JS4 156 JS4
5 149 JS3 167 JS3 184 JS4 202 JS4 218 JS4 235 JS4 253 JS4
6 227 JS4 252 JS4 276 JS4 307 JS4 328 JS4 354 JS4 380 JS4
7 324 JS4 364 JS4 401 JS4 436 JS4 475 JS4 511 JS4 524 ZC
8 449 JS4 497 JS4 549 JS4 593 JS4 647 JS4 696 JS4 746 JS4
9 587 JS4 658 JS4 726 JS4 788 JS4 854 JS4 925 JS4 988 JS4
10 761 JS4 840 JS4 937 JS4 1015 JS4 1105 JS4 1189 JS4 1273 JS4
11 956 JS4 1070 JS4 1177 JS4 1286 JS4 1334 CFJ 1491 JS4 1600 JS4
12 1247 JS3 1381 JS3 1484 AL 1551 ZC 1676 AL 1773 ZC 2072 JS4
13 1510 TK 1598 AL 1886 CFJ 1906 CFJ 1953 CFJ 2400 TK 2476 CFJ
14 1748 TK 1946 TK 2132 TK 2300 AL 2580 TK 2630 AL 2874 AL
15 2005 TK 2165 AL 2410 AL 2736 TK 2953 AL 3155 AL 3393 AL

References for the tables above.

T - trivial
WB - Wallace C. Babcock
W. C. Babcock, "Intermodulation Interference in Radio Systems", Bell System Technical Journal, 1953, p. 63-73.
TS1 - T. Skolem
T. Skolem, "On certain distributions of integers in pairs with given differences", Math. Scand., 6(1958), p. 57-68.
(considered more restrictive problem)
TS2 - T. Skolem
T. Skolem, "Some Remarks on the triple systems of Steiner", Math. Scand., 6(1958), p. 273-280.
(considered more restrictive problem)
RD - Roy O. Davis
R. O. Davis, "On Langford's Problem (II)", Math. Gazette, 43(1959), p. 253-255.
(considered more restrictive problem, see also
EO )
EO - Edward S. O'Keefe
E. S. O'Keefe, "Verification of a conjecture of Th. Skolem", Math. Scand., 9(1961), p. 80-82.
(considered more restrictive problem)
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.
BBR1 - F. Biraud, E. J. Blum and J. C. Ribes
F. Biraud, E. J. Blum and J. C. Ribes, "On optimum synthetic linear arrays with application to radioastronomy", IEEE Transactions on Antennas and Propagation, 22(1974), p. 108-109.
BBR2 - F. Biraud, E. J. Blum and J. C. Ribes (unpublished, quoted in)
D. G. Rogers, "Addition theorems for perfect systems of difference sets", J. London Math. Soc., 23(1981), p. 385-395.
BRB - E. J. Blum, J. C. Ribes and F. Biraud
E. J. Blum, J. C. Ribes and F. Biraud, "Some new possibilities of optimium synthetic linear arrays for radioastronomy", Astronomy and Astrophysics, 41(1975), p. 409-411.
BKT - J.-C. Bermond, A. Kotzig and J. Turgeon
J.-C. Bermond, A. Kotzig and J. Turgeon, "On a combinatorial problem of antennas in radioastronomy", in Proceedings 18-th Hungarian Combinatorial Colloquium (North-Holland, Amsterdam, 1976), p.135-149.
(using a result in BRB .)
PL - Philip J. Laufer
P. J. Laufer, "Regular perfect systems of difference sets of size 4 and extremal systems of size 3", Annals of Discrete Mathematics, 12(1982), p. 193-201.
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.
KTG - F. Khansefid, H. Taylor and R. Gagliardi
F. Khansefid, H. Taylor and R. Gagliardi, "Design of (0,1) sequence sets for pulsed coded systems", Communications Science Institute , University of Southern California, Los Angeles, Rep CSI-88-0-03, 1988.
TK - Torleiv Klove
T. Klove, "Bounds and Construction for Difference Triangle Sets", IEEE Transactions on Information Theory, 35(1989), p. 879-886.
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)
From ongoing searches (started October 30, 1998) using a program similar to that described in JS2 .
JS4 - James B. Shearer (unpublished)
From ongoing searches (started Fall 1999) using a program to find better difference triangle sets by local changes.
JS5 - James B. Shearer
J. B. Shearer, "Improved LP Lower Bounds for Difference Triangle Sets", The Electronic Journal of Combinatorics, 6(1999), #R31.
CFJ - Zhi Chen, Pingzhi Fan and Fan Jin
Z. Chen, P. Fan and F. Jin, "Disjoint Difference Triangle Sets", IEEE Transactions on Information Theory, IT-38(1992), p. 518-522.
ZC - Zhi Chen
Z. Chen, "Further Results on Difference Triangle Sets", IEEE Transactions on Information Theory, IT-40(1994), p. 1268-1270.
AL - Alan C. H. Ling
Ling, Alan C. H., "Difference Triangle Sets From Affine Planes", IEEE Transactions on Information Theory, IT-48(2002), p. 2399-2401.

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