Certified Minimum Estimates

Computing a very low value of a waveform proves that such a value occurs. It does not prove that no lower value occurs elsewhere. A useful approximation framework makes the direction of every estimate explicit and eventually places the true minimum inside a controlled interval.

Turning nonnegative weights into bounds

For $f=f_A$ and any nonzero real polynomial $p$, the function $p(f)^2$ is a nonnegative weight. Its weighted average of $f$ cannot be less than $\min f$. Therefore

$$R(p)=-\frac{\mathbb E[fp(f)^2]}{\mathbb E[p(f)^2]}\le K(A).$$

Optimizing $R$ over degree at most $d$ defines $B_d(A)$. Increasing the degree enlarges the choice of weights, so $B_d$ is nondecreasing. This construction is an instance of Lasserre's pushforward measure hierarchy. Its general mechanism and convergence are established results, not discoveries claimed by this report. Lasserre2021

If $p(t)=\sum_{i=0}^d c_it^i$ and $\mu_k=\mathbb E[f^k]$, the two quadratic forms use the matrices

$$H_0=(\mu_{i+j})_{0\le i,j\le d},\qquad H_1=(\mu_{i+j+1})_{0\le i,j\le d}.$$

Thus $B_d$ is minus the least generalized eigenvalue of $(H_1,H_0)$. For a cosine sum, moments can be computed from coefficients of a Laurent polynomial: integration selects its constant coefficient. Exact integer and rational arithmetic can verify a specified trial quotient without relying on numerical quadrature.

Why Chebyshev polynomials help

Chebyshev polynomials remain bounded on $[-1,1]$ and grow rapidly outside that interval. After rescaling the signal range, this lets a polynomial give much greater weight to values near the minimum than to values farther away. That contrast, together with a lower bound on the measure of the near-minimum region, controls the weighted average. This is closely related to the needle-polynomial convergence analyses of Slot and Laurent. SlotLaurent2021 SlotLaurent2022 NISTDLMF

The appendix proves a version uniform in the largest frequency. For $0<\varepsilon\le N$, define $M=\lceil8\pi N/\varepsilon\rceil$. The sufficient degree is

$$d\ge\left\lceil\sqrt{\frac N\varepsilon}\left[N\log M+\log(16N/\varepsilon)\right]\right\rceil.$$

At this degree, $0\le K(A)-B_d(A)\le\varepsilon$ for every set of $N$ distinct positive integer frequencies. The proof uses the geometry of all $N$ phases together rather than a derivative bound involving the largest frequency. The formula is a sufficient bound, not an optimal one. Its constants are supplied for verification; priority for this specialization has not been established.

The proof also has a certificate using positive integers. One can choose $M_0,s,q,p$ with $M_0\varepsilon\ge32N$, $s^2\varepsilon\ge N$, $2^q\ge M_0$, and $2^p\varepsilon\ge16N$. Then $d=s(Nq+p)$ is sufficient. Requiring $s>0$ is essential. This form avoids trusting a floating-point logarithm when checking the sufficient degree for rational input.

A concrete exact illustration

For $A=\{1,2\}$, the true depth is $9/8$. Choose the specific trial polynomial $T_d((2t-1)/3)$, where $T_d$ is the Chebyshev polynomial of degree $d$. Exact moment arithmetic gives the following values of the associated quotient.

What the result does and does not compute

The uniform degree bound removes dependence on frequency scale from this particular approximation guarantee. It does not make moment generation free. Large degrees can require many large integers, and a monomial moment matrix can be ill-conditioned in floating point. A plotted generalized eigenvalue without a certified numerical error is still an estimate.

There is also an unavoidable distinction between approximation and an extremal theorem. Approximating $K(A)$ for each input does not prove that the resulting values are all at least $c\sqrt N$. That further inequality is exactly the unresolved target of Chowla's problem. The approximation theorem is useful because it states clearly what accuracy can be obtained and under which assumptions, not because it bypasses that target.