Barker polynomials
edit · history · discussion · files · short url · combinatorics polynomial
Polynomials
$n$
$a$ 
$B_a(x)$
2
++:
x + 1
3
++-:
-x^2 + x + 1
4
+++-:
-x^3 + x^2 + x + 1
4
++-+:
x^3 - x^2 + x + 1
5
+++-+:
x^4 - x^3 + x^2 + x + 1
7
+++--+-:
-x^6 + x^5 - x^4 - x^3 + x^2 + x + 1
11
+++---+--+-:
-x^10 + x^9 - x^8 - x^7 + x^6 - x^5 - x^4 - x^3 + x^2 + x + 1
13
+++++--++-+-+:
x^12 - x^11 + x^10 - x^9 + x^8 + x^7 - x^6 - x^5 + x^4 + x^3 + x^2 + x + 1
Definition
A Barker sequence $a=(a_0,\ldots,a_{n-1})$ has $a_j=\pm1$ and $|c_k|\leq1$ for $c_k=\sum_{j=0}^{n-1-k}a_ja_{j+k}$, $1\leq k<n$ [3]. This table holds $B_a(x)=\sum_{j=0}^{n-1}a_jx^j$ for the normalization $a_0=a_1=1$ [1].
Parameters
$n$
—   length ($n\geq2$: the normalization $a_0=a_1=1$ needs two terms)
$a$
—   normalized Barker sequence (a word in + and - of length $n$, where + means $1$ and - means $-1$, normalized by $a_0=a_1=1$)
Formulas
(1)
If $B_a(x)=\sum_{j=0}^{n-1}a_jx^j$, then $B_a(x)x^{n-1}B_a(1/x)=\sum_{k=-(n-1)}^{n-1}c_{|k|}x^{n-1+k}$, where $c_k=\sum_{j=0}^{n-1-k}a_ja_{j+k}$ and $c_0=n$.
(2)
The aperiodic merit factor of the sequence is $F=n^2/(2\sum_{k=1}^{n-1}c_k^2)$. For the length-$13$ sequence, $F=169/12$.
Comments
(3)
Negating every term and replacing $a_j$ by $(-1)^ja_j$ preserve the magnitudes of the aperiodic autocorrelations, so a nontrivial Barker sequence can be represented with $a_0=a_1=1$. This table stores the normalized sign words listed by Borwein and Mossinghoff [1].
(4)
Coefficients run low degree first: the sign in position $j$ of the sequence is the coefficient of $x^j$. With this indexing, $c_0=n$.
(5)
Apart from the trivial sequence of length $1$, Barker sequences are known only for lengths $2,3,4,5,7,11,13$, and it is conjectured that no longer Barker sequence exists [2]. The nonexistence is proved for odd lengths greater than $13$, while the existence of an even Barker sequence longer than $4$ is open.
Programs
(P1)
Sage
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

R = PolynomialRing(ZZ, "x")
x = R.gen()

def barker_polynomial(signs):
    return sum((ZZ(1) if sign == "+" else ZZ(-1)) * x**j
               for j, sign in enumerate(signs))

barker_polynomial("+++++--++-+-+")
References
[1]
Peter Borwein and Michael J. Mossinghoff, Barker sequences and flat polynomials, in Number Theory and Polynomials, London Mathematical Society Lecture Note Series 352, Cambridge University Press, 2008, 71-88. (doi) (MR)
[2]
J. Willms, A note on Barker sequences of even length, 2021. (arXiv) (doi)
Links
Similar tables
Shapiro polynomials $P_n$ —   use the Rudin-Shapiro sign rule for a family of binary sequences with small aperiodic autocorrelations
Complementary Shapiro polynomials $Q_n$ —   form the second polynomial sequence in the Rudin-Shapiro pair, another family of binary sequences with small aperiodic autocorrelations
Merit factors of the Legendre sequences —   stores exact aperiodic merit factors for another binary-sequence family, rather than the sign polynomials themselves
Fekete polynomials $f_p$ —   use Legendre-symbol coefficients, with zero constant term, rather than Barker sign words normalized by their first two signs
Data properties
Entries are of type: integral polynomial
Table is complete: no (it holds every normalized Barker sequence presently known, namely the eight sequences listed by [1], whose lengths are $2,3,4,4,5,7,11,13$)
How they were obtained:

The values are exact polynomials over $\mathbb Z$.

more

The generator builds each polynomial from the sign word listed by [1] and checks the Barker autocorrelation condition, the autocorrelation polynomial identity in (1), the aperiodic merit factor in (2), and the source sign words against a brute-force enumeration of all normalized sign words through length $13$.