login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Ground states of the Bernasconi model; or, greatest merit factor of a binary sequence of length n.
2

%I #50 Jan 08 2024 07:40:58

%S 0,1,1,2,2,7,3,8,12,13,5,10,6,19,15,24,32,25,29,26,26,39,47,36,36,45,

%T 37,50,62,59,67,64,64,65,73,82,86,87,99,108,108,101,109,122,118,131,

%U 135,140,136,153,153,166,170,175,171,192,188,197,205,218,226,235,207,208,240,257

%N Ground states of the Bernasconi model; or, greatest merit factor of a binary sequence of length n.

%C Binary sequences of +1 and -1 with low autocorrelations have many applications in communication engineering. Their construction has a long tradition and has turned out to be a very hard mathematical problem. This problem is also called the low autocorrelation binary sequences (LABS) problem.

%C Bernasconi introduced an Ising spin model that allows one to formulate the construction problem in the framework of statistical mechanics.

%C Consider a sequence of binary variables or Ising spins of length N: S=(s_1, s_2, ..., s_N) s_i in {-1, +1} and their autocorrelations C_g = sum_{i=1..n-g} s_i s_{i + g}.

%C Bernasconi defined a Hamiltonian H(S) by H(S) = Sum_{g = 1..N-1} (C_g)^2. The ground states (that minimize H(S)) of this model are the low autocorrelation binary sequences we are looking for.

%D Tom Hoholdt, "The merit factor problem for binary sequences." Lecture notes in computer science, Vol. 3857 (2006): 51.

%D Jonathan Jedwab, "A survey of the merit factor problem for binary sequences." In Sequences and Their Applications-SETA 2004, pp. 30-55. Springer Berlin Heidelberg, 2005.

%H Heiko Bauke, <a href="https://web.archive.org/web/20061209154340/http://tina.nat.uni-magdeburg.de/heiko/LABS/index.php">The Bernasconi Model</a>.

%H J. Bernasconi, <a href="http://dx.doi.org/10.1051/jphys:01987004804055900">Low autocorrelation binary sequences: statistical mechanics and configuration space analysis</a>, J. Physique, 48:559, 1987.

%H Peter Borwein, Kwok-Kwong Stephen Choi, and Jonathan Jedwab, <a href="http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P179.pdf">Binary sequences with merit factor greater than 6.34</a>, Information Theory, IEEE Transactions on 50.12 (2004): 3234-3249.

%H Peter Borwein, Ron Ferguson, and Joshua Knauer, <a href="http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P218.pdf">The merit factor problem</a>, London Mathematical Society Lecture Note Series, 352 (2008): pp. 52ff.

%H Steven Finch, <a href="/A091386/a091386.pdf">Golay-Littlewood Problem</a>, Mar 05 2014. [Cached copy, with permission of the author]

%H M. J. E. Golay, <a href="http://dx.doi.org/10.1109/TIT.1982.1056505">The merit factor of long low autocorrelation binary sequences</a>, IEEE Trans. Inform. Theory, IT-28, 1982, 543-549.

%H Joshua Knauer, <a href="http://www.cecm.sfu.ca/~jknauer/labs/records.html">Merit Factor Records</a>. Gives best results known at that time for n <= 304 [Broken link]

%H Joshua Knauer, <a href="/A102780/a102780.pdf">Merit Factor Records</a> [Cached copy, showing results for n <= 136. Scanned copy of printout of original.]

%H Stephan Mertens, <a href="http://dx.doi.org/10.1088/0305-4470/29/18/005">Exhaustive search for low-autocorrelation binary sequences</a>, J. Phys. A, 29:L473-L481, 1996.

%H Stephen Mertens, <a href="http://www-e.uni-magdeburg.de/mertens/research/labs/open.dat">Ground states of the Bernasconi model with open boundary conditions</a>. [Table of records for n <= 60]

%H Tom Packebusch and Stephan Mertens, <a href="https://doi.org/10.1088/1751-8113/49/16/165001">Low autocorrelation binary sequences</a>, J. Phys. A: Math. Theor. 49 (2016) 165001. Gives sequence for n <= 66.

%e From _Steven Finch_, Mar 03 2014: (Start)

%e The merit factor for the 13-term Barker sequence {1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1} is 13^2/(2*a(13)) = 169/12 = 14.083...

%e The merit factor for the 11-term Barker sequence {1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1} is 11^2/(2*a(11)) = 121/10 = 12.1. (End)

%Y Cf. A091386.

%K nonn

%O 1,4

%A Heiko Bauke (heiko.bauke(AT)physik.uni-magdeburg.de), Feb 11 2005

%E a(61)-a(66) from Packebusch and Mertens (2016) added by _Stephan Mertens_, Jan 08 2024