TOPICS
Search

Merit Factor Problem


The merit factor problem asks for binary sequences with small off-zero correlations. Let A_n be the set of sequences {a_k}_(k=0)^n with a_0=1 and a_i=+/-1 for i=1, ..., n, and define

 c_k=sum_(j=0)^(n-k)a_ja_(j+k)
(1)

for k=0, 1, ..., n. Then the merit factor problem requires the minimization of sum_(k=0)^(n)c_k^2 over A_n for a fixed positive integer n.

For n=1, 2, ..., the first few minima are 5, 10, 18, 27, 43, 52, 72, ... (OEIS A091386).

Finding optimal sequences is computationally difficult (Borwein and Bailey 2003, p. 6).

For a sequence A=(a_0,...,a_n) of length N=n+1>=2, its merit factor is

 F(A)=(N^2)/(2sum_(k=1)^(N-1)c_k^2),
(2)

where the c_k are its aperiodic autocorrelations. The zero-shift value c_0=N is excluded from this denominator. Consequently, maximizing F(A) is equivalent to the minimization above, where c_0^2 is fixed. Changing every sign preserves F(A), so requiring a_0=1 does not affect the extremum.

For the associated Littlewood polynomial P_A(z)=sum_(j=0)^(N-1)a_jz^j, Parseval's theorem gives

 int_0^1|P_A(e^(2piit))|^4dt=N^2+2sum_(k=1)^(N-1)c_k^2.
(3)

Thus large merit factor is equivalent to a normalized fourth raw moment close to 1 (Jedwab et al. 2013). OpenAI (2026) announced that the largest merit factor at length N tends to infinity as N->infty through all integers. This follows already from the reported construction with max_(|z|=1)|P_A(z)|<=(1+eta)sqrt(N) for every fixed eta>0 and all sufficiently large N. Indeed, the fourth raw moment is at most (1+eta)^2N^2, so

 max_(A in {-1,1}^N)F(A)>=1/((1+eta)^2-1).
(4)

This consequence does not require the stronger two-sided uniform claim about Littlewood polynomials.


See also

Aperiodic Autocorrelation, Littlewood Polynomial, Sequence

Explore with Wolfram|Alpha

References

Borwein, J. and Bailey, D. Mathematics by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A K Peters, 2003.Borwein, P. B. Computational Excursions in Analysis and Number Theory. New York: Springer-Verlag, 2002.Jedwab, J.; Katz, D. J.; and Schmidt, K.-U. "Advances in the Merit Factor Problem for Binary Sequences." J. Combin. Th. Ser. A 120, 882-906, 2013. https://doi.org/10.1016/j.jcta.2013.01.010.OpenAI. "Asymptotically Minimal Maxima of Real Littlewood Polynomials." Sep. 23, 2026. https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Asymptotically-minimal-maxima-of-real-Littlewood-polynomials-September-23-2026/paper.pdf.Sloane, N. J. A. Sequence A091386 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Merit Factor Problem

Cite this as:

Weisstein, Eric W. "Merit Factor Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MeritFactorProblem.html

Subject classifications