Submit progress

on Golay's Merit Factor (AlphaEvolve problem 28)

The statement

For $n \geq 1$ , let $\mathbb{U}_{n}$ denote the set of polynomials $p(z)$ of degree $n$ with coefficients $\pm 1$ . Define

C^-(n) \coloneqq \max_{p \in \mathbb{U}_{n}} \left(min_{|z|=1}\frac{|p(z)|}{\sqrt{n+1}}\right)

C^+(n) \coloneqq \min_{p \in \mathbb{U}_{n}}\left(\max_{|z|=1}\frac{|p(z)|}{\sqrt{n+1}}\right)

C^w(n) \coloneqq \min_{p \in \mathbb{U}_{n}}\left(\max_{|z|=1}\frac{|p(z)|}{\sqrt{n+1}} - \min_{|z|=1}\frac{|p(z)|}{\sqrt{n+1}}\right)

C^4(n) \coloneqq \min_{p \in \mathbb{U}_{n}} \frac{(n+1)^2}{\int_0^1 |p(e^{2\pi \theta})|^4 d\theta - (n+1)^2}

(The quantity being minimized for $C^4(n)$ is known as Golay's merit factor for $p$ .) What is the behavior of $C^-(n)$ , $C^+(n)$ , $C^w(n)$ , $C^4(n)$ as $n \to \infty$ ?

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.