Proof of the Barker array conjecture

Davis, James; Jedwab, Jonathan; Smith, Ken

doi:10.1090/S0002-9939-07-08703-5

Proof of the Barker array conjecture
HTML articles powered by AMS MathViewer

by James A. Davis, Jonathan Jedwab and Ken W. Smith

Proc. Amer. Math. Soc. 135 (2007), 2011-2018

DOI: https://doi.org/10.1090/S0002-9939-07-08703-5

Published electronically: March 2, 2007

PDF | Request permission

Abstract:

Using only elementary methods, we prove Alquaddoomi and Scholtz’s conjecture of 1989, that no $s \times t$ Barker array having $s, t > 1$ exists except when $s = t = 2$.

References

Sabah Alquaddoomi and Robert A. Scholtz, On the nonexistence of Barker arrays and related matters, IEEE Trans. Inform. Theory 35 (1989), no. 5, 1048–1057. MR 1023242, DOI 10.1109/18.42220
R.H. Barker, Group synchronizing of binary digital systems, Communication Theory (W. Jackson, ed.), Academic Press, New York, 1953, pp. 273–287.
Thomas Beth, Dieter Jungnickel, and Hanfried Lenz, Design theory. Vol. I, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 69, Cambridge University Press, Cambridge, 1999. MR 1729456, DOI 10.1017/CBO9780511549533
Y. K. Chan, M. K. Siu, and P. Tong, Two-dimensional binary arrays with good autocorrelation, Inform. and Control 42 (1979), no. 2, 125–130. MR 542326, DOI 10.1016/S0019-9958(79)90617-X
J. Jedwab, Nonexistence results for Barker arrays, Cryptography and coding, II (Cirencester, 1989) Inst. Math. Appl. Conf. Ser. New Ser., vol. 33, Oxford Univ. Press, New York, 1992, pp. 121–126. MR 1165734
Jonathan Jedwab, Barker arrays. I. Even number of elements, SIAM J. Discrete Math. 6 (1993), no. 2, 294–308. MR 1215236, DOI 10.1137/0406024
J. Jedwab, A survey of the merit factor problem for binary sequences, Sequences and Their Applications — Proceedings of SETA 2004 (T. Helleseth et al., eds.), Lecture Notes in Computer Science, vol. 3486, Springer-Verlag, Berlin, Heidelberg, 2005, pp. 30–55.
Jonathan Jedwab, Barker arrays. I. Even number of elements, SIAM J. Discrete Math. 6 (1993), no. 2, 294–308. MR 1215236, DOI 10.1137/0406024
J. Jedwab and K. Yoshida, The peak sidelobe level of families of binary sequences, IEEE Trans. Inform. Theory 52 (2006), 2247–2254.
Ka Hin Leung, Siu Lun Ma, and Bernhard Schmidt, Nonexistence of abelian difference sets: Lander’s conjecture for prime power orders, Trans. Amer. Math. Soc. 356 (2004), no. 11, 4343–4358. MR 2067122, DOI 10.1090/S0002-9947-03-03365-8
K.H. Leung and B. Schmidt, The field descent method, Designs, Codes and Cryptography 36 (2005), 171–188.
Alexander Pott, Finite geometry and character theory, Lecture Notes in Mathematics, vol. 1601, Springer-Verlag, Berlin, 1995. MR 1440858, DOI 10.1007/BFb0094449
G.S. Ramakrishna and W.H. Mow, A new search for optimal binary arrays with minimum peak sidelobe levels, Sequences and Their Applications — Proceedings of SETA 2004 (T. Helleseth et al., eds.), Lecture Notes in Computer Science, vol. 3486, Springer-Verlag, Berlin, Heidelberg, 2005, pp. 355–360.
H.D. Schotten and H.D. Lüke, On the search for low correlated binary sequences, AEU — Int. J. of Electronics and Communications 59 (2005), 67–78.
R. Turyn and J. Storer, On binary sequences, Proc. Amer. Math. Soc. 12 (1961), 394–399. MR 125026, DOI 10.1090/S0002-9939-1961-0125026-2
R. Turyn, Sequences with small correlation, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968), John Wiley, New York, 1968, pp. 195–228. MR 0242566
P. Wild, Infinite families of perfect binary arrays, Electron. Lett. 24 (1988), 845–847.