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

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, 37, 50, 62, 59, 67, 64, 64, 65, 73, 82, 86, 87, 99, 108, 108, 101, 109, 122, 118, 131, 135, 140, 136, 153, 153, 166, 170, 175, 171, 192, 188, 197, 205, 218, 226, 235, 207, 208, 240, 257

Offset

1,4

Comments

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.

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

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

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.

References

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

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.

Links

Table of n, a(n) for n=1..66.

Heiko Bauke, The Bernasconi Model.

J. Bernasconi, Low autocorrelation binary sequences: statistical mechanics and configuration space analysis, J. Physique, 48:559, 1987.

Peter Borwein, Kwok-Kwong Stephen Choi, and Jonathan Jedwab, Binary sequences with merit factor greater than 6.34, Information Theory, IEEE Transactions on 50.12 (2004): 3234-3249.

Peter Borwein, Ron Ferguson, and Joshua Knauer, The merit factor problem, London Mathematical Society Lecture Note Series, 352 (2008): pp. 52ff.

Steven Finch, Golay-Littlewood Problem, Mar 05 2014. [Cached copy, with permission of the author]

M. J. E. Golay, The merit factor of long low autocorrelation binary sequences, IEEE Trans. Inform. Theory, IT-28, 1982, 543-549.

Joshua Knauer, Merit Factor Records. Gives best results known at that time for n <= 304 [Broken link]

Joshua Knauer, Merit Factor Records [Cached copy, showing results for n <= 136. Scanned copy of printout of original.]

Stephan Mertens, Exhaustive search for low-autocorrelation binary sequences, J. Phys. A, 29:L473-L481, 1996.

Stephen Mertens, Ground states of the Bernasconi model with open boundary conditions. [Table of records for n <= 60]

Tom Packebusch and Stephan Mertens, Low autocorrelation binary sequences, J. Phys. A: Math. Theor. 49 (2016) 165001. Gives sequence for n <= 66.

Example

From Steven Finch, Mar 03 2014: (Start)
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...
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)

Crossrefs

Cf. A091386.

Sequence in context: A342453 A370393 A077218 * A227828 A115025 A245286

Adjacent sequences: A102777 A102778 A102779 * A102781 A102782 A102783

Keyword

nonn

Author

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

Extensions

a(61)-a(66) from Packebusch and Mertens (2016) added by Stephan Mertens, Jan 08 2024

Status

approved