# 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, for every $c>0$ and every requested size $n_0$, there is a set $A$ with $|A|\ge n_0$ and $\lambda_A\le c\sqrt{|A|}$; the exact-cardinality variant $\lambda(n)\le c\sqrt n$ for all $n$ is stronger and untouched here. 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 *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 *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 *worse* than deterministic Kronecker roundings; no retained experiment supported that ordering and it is **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$ when $P_A'$ has a root at $\pm1$, the linear endpoint factor is removed exactly and the deflated polynomial isolated in the open interval, so the discarded endpoint strip holds no critical point by construction (a bare inward shift is not used as a substitute); the headline ladder sets have no endpoint critical points). 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\}