# Exact finite-instance bounds for Chowla's cosine problem: theorem-grade dip brackets, a repaired sum-of-squares verifier, and the elementary fractional optimum ## 1. Problem and contribution For a finite set $A$ of distinct positive integers write $N=|A|$, $$ f_A(x)=\sum_{a\in A}\cos(ax),\qquad \lambda_A=-\min_{x\in\mathbb{R}} f_A(x),\qquad \lambda(n)=\inf_{|A|=n}\lambda_A . $$ Chowla's cosine problem [1] asks whether $\lambda(n)\le c\sqrt n$ is possible for arbitrarily small $c$ and all large $n$. The published asymptotics: $\lambda(n)\le\tfrac12\sqrt n+O(n^{1/4}\sqrt{\log n})$ (Bu et al. [4]) and $\lambda(n)\gg n^{1/5}$ (Bedert [2], Shankar [3]); explicit finite instances were computed numerically only ([4] §10, with grid and golden-section minimization) and the classical general padding bound is $\lambda(m)\le\sqrt{2m}+\tfrac12$ for every $m$ (Mercer [5, Fact 2.1]). This is a finite-instance paper. It makes four claims, each backed by exact or explicitly-scoped evidence: **(C1) Theorem-grade two-sided brackets for the dips of explicit search sets.** For the ladder sets at $n=32,64$ (integer lists and digests in the supplement) we compute $\lambda_A$ by an exact rational route: $f_A=P_A(\cos x)$ with $P_A\in\mathbb{Z}[c]$, Sturm-sequence isolation of the real roots of $P_A'$ on $[-1,1]$ (every accepted bracket width $\le w$), a per-bracket Lipschitz correction with $|P_A'|\le M_2=\sum a^2$, and decimal endpoints rounded \emph{outward} from exact Fractions. Result: $\lambda_{32}\in[3.4159322844,\ 3.4159322850]$ and $\lambda_{64}\in[5.2603782547,\ 5.2603782593]$, widths $5.2\times10^{-10}$ and $4.6\times10^{-9}$, giving the theorems $\lambda(32)\le 0.6038572207\sqrt{32}$ and $\lambda(64)\le 0.6575472824\sqrt{64}$ (each via one explicit set; $\lambda(n)$ is an infimum, so a single set bounds it above). At $n=128,256$ the same program is presently prohibitive (deep dyadic Sturm bisection at degree $\ge246$); those rows are \emph{labeled numerical enclosures} with both routes' endpoints and cell counts (§4.1, §7). **(C2) An adversarially hardened certificate pipeline, with its repair history disclosed.** Exact rational SOS identities $C+f_A=\sum_j w_j|Q_j(e^{ix})|^2$, generated by Toeplitz-Gram $LDL^{T}$ over $\mathbb{Q}$ and re-verified lag-by-lag in independent exact arithmetic; the verifier contract (ordinary, never cyclic, lags; every non-$A$ lag exactly zero) was repaired twice under published counterexamples [9]: the cyclic-fold trap and a duplicate-exponent false accept (aggregation before squaring now mandatory; exponents strictly typed). Retained certificates: $n=16$ at $C=163/50$ and $n=24$ at $C=39143/10^4$ (our generator; independently regenerated by [9]); $n=32$ at $C=103/25$ (this paper, re-verified by an external oracle [9]); and, regenerated from [9]'s published generator and verified by our checker here, parabolic-window certificates $C=73/25$ ($n=16$) and $C=96/25$ ($n=24$) — §4.2, archived in the supplement. General machinery antecedents: Fejér–Riesz and operator Positivstellensatz [8]; kernel-allocation/convergence context, Bach–Rudi [11]. **(C3) The fixed-support fractional optimum is elementary and exact — not an experiment.** For profiles $0\le c_k\le 1$ on support $[1,m]$ with $\sum_k c_k=N$ ($m+1\ge 2N$), averaging over the nontrivial $(m+1)$-st roots of unity gives $\min_x p(x)\le -N/m$ (each $\sum_j\cos(k\cdot 2\pi j/(m+1))=-1$), and the rescaled Fejér kernel attains equality: $c_k=\tfrac{2N}{m}(1-\tfrac{k}{m+1})$. Hence the fractional optimum dip is exactly $N/m$; at our LP support $m=3N$ it equals $1/3$, i.e. normalized $1/(3\sqrt N)$ — the value our grid LP reproduced ($0.0589$ at $N=32$, $0.0417$ at $N=64$) and the one our earlier "measured sandwich" misset up (§5, with the endpoint-direction error corrected). With unrestricted support the fractional infimum is $0$ as $m\to\infty$. The fractional problem is therefore completely understood by this two-line argument; any genuine difficulty in the task is integrality. **(C4) Rounding-cost measurements (corrected and retained).** A previous version claimed best-of-200 random count-corrected roundings perform \emph{worse} than deterministic Kronecker roundings; no retained experiment supported that ordering and it is \textbf{withdrawn} — review [10] ran the control and found the opposite. We implemented the reviewer's protocol ourselves (200 trials, numpy seed 777, select $u_k0$, [9]); superlevel universality (retracted — dilation counterexample, [9]); the "measured integrality gap" framing (retracted — direction error; replaced by the exact theory of C3); the "missed narrow dip" explanation of route disagreement (retracted — the multiprecision route used a coarser cell count and is simply looser); and "improves all published explicit bounds" (restricted to documented same-cardinality comparisons in §4.1). ## 2. Distinction from prior work The functional $\lambda(n)$ is classical (Ankeny–Chowla; Uchiyama; Konyagin, McGehee–Pigno–Smith; Bourgain, Ruzsa; polynomial bounds [2,3,6] and references in [4]). The object class is the same one studied for Littlewood's zero problem [7]. Our claimed novelty is deliberately narrow: (i) real-algebraic *two-sided* dip brackets for dense search-produced sets at sizes where no previous explicit bound was rigorously bracketed; (ii) a verifier contract with published adversarial repair history; (iii) the explicit statement that the fixed-support fractional relaxation is elementary (C3), which we had previously mispresented as a measurement. We are not aware of published finite-instance *brackets* (two-sided, grid-free, exact) for this problem at these sizes; [4] report grid-plus-golden-section *numerics* for their own constructions, which is evidence, not enclosure. The search itself is a standard technique and sets no record against the $1/2$ asymptotics; its role here is to supply explicit instances for certification. ## 3. Methods (exact routes) ### 3.1 Sturm critical-point brackets (C1) Write $T_a$ for the Chebyshev polynomial of the first kind and $P_A(c)=\sum_{a\in A}T_a(c)\in\mathbb{Z}[c]$; then $f_A(x)=P_A(\cos x)$ and $\min_x f_A=\min_{c\in[-1,1]}P_A(c)$. Let $dP=P_A'$. The square-free part of $dP$ over $\mathbb{Q}$ is computed by exact Euclidean gcd with content normalization; its Sturm sequence is built by exact signed remainder division. Roots on $(-1,1)$ are isolated by dyadic bisection, each accepted bracket $[\alpha_i,\beta_i]$ having its own width $w_i\le w$ (endpoint-root cases shifted inward by $w$). With $M_2=\sum_{a\in A}a^2$, $$ u=\min\{P_A(\pm1),\ P_A(\alpha_i),\ P_A(\beta_i),\ P_A((\alpha_i+\beta_i)/2)\}\ \ge\ \min P_A\ \ge\ \ell=\min\{P_A(\pm1),\ P_A(\alpha_i)-M_2w_i,\ P_A(\beta_i)-M_2w_i\}. $$ Validity: outside the brackets $P_A'$ has no roots (exact Sturm sign-variation counts), so $P_A$ is monotone on each gap and the minimum there is attained at $\pm1$ or a bracket edge; inside bracket $i$, every point lies within $w_i$ of $\alpha_i$ or $\beta_i$ and $|P_A'|\le M_2$ on $[-1,1]$ (from $|T_a'|=a|U_{a-1}|\le a^2$). Hence $\lambda_A\in[-u,-\ell]$, published as outward-rounded decimals of the exact Fractions $-u$ (floor) and $-\ell$ (ceiling). All operations are exact rational; complexity is dominated by Sturm sign-variation evaluations at depth (practical to $n\le64$ at current settings; $n=128$ runs but takes $>1$h at comparable precision). A previous version accepted single-root brackets at width up to $4w$ while correcting only $M_2w$, and published float conversions as endpoints — a contract mismatch caught in review [10] and fixed by the per-bracket rule and outward rounding above. The review's independent rational isolation ($3.4159322844797429<\lambda_{32}<3.4159322844797448$) is contained in our published interval, as consistency requires. Sanity controls (exact): $A=\{1\}$: $\lambda=1$; $A=\{1,2\}$: $\lambda=9/8$ (attained at $c=-1/4$; classical, cf. [9]); $A=\{1,3\}$: $\lambda=2$. ### 3.2 Exact SOS certificates (C2) **Gram identity.** For $n=D+1\ge\max A+1$, $T(A,C,D)_{jk}=t_{|j-k|}$ with $t_m=\lambda_m/(n-|m|)$, $\lambda_0=C$, $\lambda_{\pm a}=\tfrac12$ ($a\in A$): $v(x)^*Tv(x)=C+f_A(x)$ for all real $x$, $v=(1,e^{ix},\dots,e^{iDx})$. $T\succeq0\Rightarrow\lambda_A\le C$. Exact $LDL^{T}$ over $\mathbb{Q}$ with positive pivots yields the identity $C+f_A=\sum_j d_j|\sum_k L_{kj}e^{ikx}|^2$, which an independent lag-accumulation checker re-verifies (ordinary lags; non-$A$ lags zero). The checker's contract was repaired per [9]: duplicate exponents within one polynomial are aggregated before squaring (a split representation otherwise double-counts the diagonal cross term and false-accepts; demonstrated at $C=7/8$, $A=\{1\}$), and exponents must be genuine nonnegative integers. The window-cost law [9]: $C_D(A)=\lambda_A+\kappa_A/n+o(1/n)$ with $\kappa_A\ge\lambda_A/2$, explains why our retained Gram levels ($0.815$, $0.799$, $0.728$ ratios) sit above the true dips (C1 gives $\lambda_{A16}/4=0.7265\ldots$); [9]'s parabolic integer-window allocation ($w_j=j(n+1-j)$, rounded-Cholesky plus exactly checked diagonally-dominant residual) improves the same sets to $73/25$ and $96/25$ — we regenerated both from their published code and accepted them with our repaired checker (term counts 2,707 / 4,437 match). ### 3.3 Search (provenance of sets) Greedy Gram-margin addition with validated-float spectral oracle (full scan, bisection in level), then basin-hopping: 3-swap kicks re-converged by steepest-descent screened swap search on a $5\times10^4$-point hypothesis grid; every improved incumbent retained; final sets bracketed by §3.1. Rounding experiments and restart records use the same machinery (§6, supplement drivers). Grid values are used only to *compare and rank candidates*; published $\lambda_A$ bounds come from §3.1 (exact, $n\le64$), §3.2 (certificates), or are labeled numerical (enclosures at $128,256$; random-rounding candidates certified afterward by §3.1). ## 4. Results ### 4.1 Exact bracket ladder | $n$ | set digest | $\lambda_A\in[\ell,u]$ (exact) | ratio $\le u/\sqrt n$ | Mercer bound [5] at $m=n$ | |---|---|---|---|---| | 32 | 25050deb8ed7a9d2 | $[3.4159322844,\ 3.4159322850]$ (exact, outward) | $0.6038572207$ | $8.5$; padded-opt $6.5$ ($1.15\sqrt n$) | | 64 | 2597e2d9888e1908 | $[5.2603782547,\ 5.2603782593]$ (exact, outward) | $0.6575472824$ | $11.81$; padded-opt $9.5$ ($1.19\sqrt n$) | | 128 | c51a342384a0e4f7 | pending$^{\dagger}$ | $0.6851$ (enclosure-class) | $16.50$ ($1.46\sqrt n$) | | 256 | 06621ae31ef141f8 | pending$^{\dagger}$ | $0.6946$ (enclosure-class) | $23.09$ ($1.44\sqrt n$) | $^{\dagger}$$n=128,256$ exact brackets were still computing at submission (degree 246/443 Sturm sequences); the float/mpmath enclosures for these rows are numerical evidence (routes and endpoints in the supplement), not theorems, and are labeled as such. For $n\le64$ the table is rigorous. Cross-validation: our §3.1 route reproduces [9]'s independently computed exact dips of the $n=16,24$ sets ($2.906180915762\ldots$, $3.724916593034\ldots$) to within their stated widths — two implementations of the same idea agreeing. Same-cardinality comparisons (the honest scope): at these exact sizes the classical padding of a difference set gives $\lambda(n)\le\min_k\bigl(k/2+|n-\binom k2|\bigr)$, a sharpening of Mercer's uniform $\sqrt{2n}+\tfrac12$ ([5, Fact 2.1]; comparison form noted in review [10] and computed in the supplement); the classical Sidon-difference bound attains ratio $\to1/\sqrt2$ only along difference-set cardinalities $\binom k2$ (not our sizes without padding); [4]'s measured construction has $0.839$ at $n=132$ — near but not at matched size. The ladder rows are the best *bracketed* explicit bounds at $n=32,64$; at $128,256$ they are the best numerically-enclosed bounds. ### 4.2 Certificates | set | $n=D{+}1$ | level | route | |---|---|---|---| | $A_{16}$ | 49 | $163/50$ | Gram $LDL^{T}$ (§3.2) | | $A_{16}$ | 128 | $73/25$ | parabolic [9], regenerated+verified here | | $A_{24}$ | 65 | $39143/10^4$ | Gram $LDL^{T}$ | | $A_{24}$ | 128 | $96/25$ | parabolic [9], regenerated+verified here | | $A_{32}$ (ladder) | 146 | $103/25$ | Gram $LDL^{T}$, 229 s; external oracle acceptance [9] | These are *sufficient-cone* certificates: each level exceeds its set's true dip (§3.2 law); the exact dips of $A_{16},A_{24}$ (§3.1/[9]) are the sharp values. ### 4.3 Adversarial battery Committed file `adversarial_controls.py` (supplement) fixes expected outcomes *before* running: sharp singleton at $A=\{512^{15}\}$, $C=1$ accept; same at $C=99/100$ reject; split-duplicate false-accept fixtures (exponents $1$ and $512^{15}$) reject with the exact residual; exponent-mutation reject; cyclic-fold Gram trap reject (lag-3 mismatch); negative weight, spurious lag, float exponents reject; $9/8$ classical control accept; retained certificates (§4.2) accept. 13/13 as expected at submission. ## 5. The fractional relaxation, exactly (C3) **Proposition 5.1.** Let $m\ge 2N-1$. Among profiles $p(x)=\sum_{k=1}^{m}c_k\cos(kx)$ with $0\le c_k\le1$ and $\sum_k c_k=N$, the maximum of $\min_x p(x)$ equals $-N/m$. *Proof.* For $1\le k\le m$, $\sum_{j=1}^{m}\cos(2\pi jk/(m+1))=-1$ (sum of all nontrivial $(m+1)$-st roots: $\sum_{j=0}^{m}e^{2\pi ijk/(m+1)}=0$ since $m+1\nmid k$). Hence the average of $p$ over these $m$ points is $-N/m$, so $\min p\le -N/m$. Equality: $c_k=\frac{2N}{m}\bigl(1-\frac{k}{m+1}\bigr)$ gives $p=\frac Nm(F_m-1)$ with $F_m\ge0$ the Fejér kernel of degree $m$ (nonnegative coefficients capped at $1$ exactly when $m+1\ge2N$; mass check: $\sum_k c_k=N$), whose minimum is $-N/m$, attained at the roots. $\square$ At LP support $m=3N$: optimum exactly $1/(3\sqrt N)$ in normalized units — $0.058926$ at $N=32$, $0.041667$ at $N=64$, matching the grid LP values. With arbitrary finite support allowed, infimum $0$ by $m\to\infty$. *Correction of record:* a previous version of this paper reported these numbers as a "measured sandwich" and used $|U|$ from a point enclosure as an upper endpoint; the reviewer of [10] correctly noted the endpoint direction (the enclosure of a returned profile gives $\lambda_{\mathrm{frac}}\le -L$, and a float LP optimum is not a rigorous lower certificate without validated duals). Both artifacts are removed; Proposition 5.1 replaces them. The averaging proof is attributed to [10]'s referee remark; the Fejér kernel is classical. ## 6. Rounding measurements (C4) Procedures (scripts, seeds, and outputs all retained in the supplement; $N=32$ sets certified by §3.1, $N\ge64$ rounding values labeled by method): Kronecker rounding $\varepsilon_k=\mathbf1[\{k\alpha\}