# Chowla cosine problem: finite computation and exact certificates Date: 2026-10-18 UTC / 2026-10-17 America/Chicago. For a nonempty finite set A of distinct positive integers, define lambda(A) = -min_theta sum_{a in A} cos(a theta). The open asymptotic problem asks for a positive absolute constant c such that lambda(A) >= c sqrt(|A|) for all A. **Nothing in these computations solves that open problem, disproves it, or establishes mathematical novelty.** ## Main rigorously certified finite result For A* = {1,2,3,4,5,6,7,8,10,11,13,14,15,16,17,21}, exact rational Sturm arithmetic proves 2.4548327530 < lambda(A*) < 2.4548327531, 0.613708188250 < lambda(A*) / 4 < 0.613708188275. In addition, a finite exhaustive calculation with **integer interval arithmetic** proves A* is the unique minimizer of lambda(A)/sqrt(|A|) among all 4,194,303 nonempty subsets of {1,...,22}. Every other set in that universe has ratio at least 0.613708188275, strictly above the certified ratio of A*. This is a complete result only for the stated finite universe. Frequencies can be arbitrarily large in the original problem. We did not perform a literature novelty check for this finite optimum. ### How the finite proof works 1. `certify.py` constructs the integer Chebyshev polynomial P_A(x)=sum T_a(x). The identity cos(a theta)=T_a(cos theta) identifies the entire continuum theta with x in [-1,1]. 2. For the claimed rational upper bound b, a Sturm sequence proves P_A+b has zero roots in [-1,1] and positive endpoint values. Thus lambda(A)a. All arithmetic in these certificates uses exact Python integers/Fractions. 4. `exact_grid.py` bounds cos(k pi/4096), for 0<=k<=4096, without floating point. Starting from cos(pi)=-1, repeated half-angle square roots construct the angle step with 96-bit integer intervals. Exact outward-rounded interval angle addition gives every grid value, then outward conversion gives rational upper bounds with denominator 2^40. Each final interval has width at most one unit of 2^-40. 5. Integer-frequency grid values are obtained by exact modular indexing and reflection. For each A, the most negative *upper* bound for its sampled values is a rigorous lower bound on lambda(A). 6. All 2^22-1 nonempty subsets are visited in Gray-code order. The only set whose resulting lower bound falls below the rigorous ratio bound of A* is A* itself. Thresholds for sqrt(|A|) are compared using exact integer squares and `isqrt`; there is no floating-point square root in this step. 7. Grid sums use signed int64, which cannot overflow here: 22 terms each have magnitude <=2^40, well below the 2^63 limit. See `certificate_N16.json` and `exact_finite_M22_certificate.json`. The JSON certificate stores the Chebyshev polynomial, the complete Sturm sequence, endpoint signs, rational witness, bound, and finite-search counts. The finite-search JSON is a report of a reproducible computation, not a replacement for running/auditing the script. ## Additional rigorously bounded examples | A | N | Exact certified interval for lambda(A) | |---|---:|---:| | {1,2,4,6,7,8} | 6 | (1.5918323293, 1.5918323294) | | {1,2,3,4,5,6,8,9,10,11,14} | 11 | (2.1023812792, 2.1023812793) | | A* above | 16 | (2.4548327530, 2.4548327531) | Their exact certificates are `certificate_N6.json`, `certificate_N11.json`, and `certificate_N16.json`. The first two are certified extrema for those specific sets; we did not prove they minimize the ratio for their cardinality among arbitrarily large frequencies. ## Numerical search coverage and limitations - Exhaustive sampled search over every nonempty subset of {1,...,16}, then {1,...,22}, then {1,...,24}. The largest universe contains 16,777,215 distinct sets. Earlier searches are contained in it; do not add their counts and present that total as distinct sets. - Each sampled search uses 4,097 equally spaced points in [0,pi], retains eight candidates per cardinality, and refines local minima numerically. A* was the best observed ratio throughout the largest universe. - The finite ranking is rigorously certified only through maximum frequency 22, as described above. The M24 scan remains a floating-point experiment. - Heuristic searches made 4,560,000 proposed swaps over 60 restarts: M48/N28 (12 x 60,000 proposals), M64/N24, M96/N36 and M128/N48 (16 x 80,000 each). They found no ratio lower than A*. They make no claim of global optimality. - Heuristic seed is reproducible: base 20261018 + 1000*M + N. - Derivative-based grid-error estimates in `exhaustive_M*.json` describe discretization, not rigorous floating-point roundoff bounds. Do not call those sampled scans exact by themselves. ## Exact two-frequency subcase An elementary proof, independently found by root and compute agents, gives lambda({a,b}) >= 9/8 for **all** distinct positive integers a,b, with equality precisely when {a,b}={d,2d}. This is not claimed to be new. Divide frequencies by their gcd. If both are odd, theta=pi gives -2. Otherwise let o be odd and e even. If o>=3, evaluate theta=(2j+1)pi/o. The even-frequency cosines range through real parts of all o-th roots of unity, so some sum is at most -1-cos(pi/o)<=-3/2. If o=1 and e>=4, theta=(e-1)pi/e gives -1-cos(pi/e)<=-1-sqrt(2)/2. The remaining normalized pair is {1,2}, where cos(theta)+cos(2theta) = 2(x+1/4)^2 - 9/8, x=cos(theta), so the minimum is exactly -9/8. ## Reproduction Requirements: Python 3, NumPy and SciPy. The exact-extremum arithmetic uses only standard-library `fractions`; the exhaustive integer grid uses NumPy for exact int64 vector operations. SymPy and mpmath were unavailable and are not required. Run from this directory: python certify.py python exact_grid.py python search.py --M 24 python anneal.py --M 48 --N 28 --restarts 12 --steps 60000 python anneal.py --M 64 --N 24 --restarts 16 --steps 80000 python anneal.py --M 96 --N 36 --restarts 16 --steps 80000 python anneal.py --M 128 --N 48 --restarts 16 --steps 80000 The main block of `certify.py` recreates N6/N11 certificates. To recreate N16, call `certify` with the A* list, lower='2.4548327530', upper='2.4548327531', witness='4001706657/5000000000', save_name='certificate_N16.json'. All are exact rational inputs. The rational witness approximates cos(theta) near the minimizer, but its sign check is exact and does not rely on that approximation.