Difference triangle sets

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

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.