🔢 mathematics

Polynomial bounds for the Chowla Cosine Problem

This paper establishes polynomial bounds for the Chowla cosine problem by proving that for any finite set of $n$ positive integers, the minimum value of the associated cosine sum is at most $-n^{1/5-o(1)}$ .

Original authors: Benjamin Bedert

Published 2026-07-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin Bedert

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a conductor standing before a massive orchestra, but instead of violins and trumpets, your musicians are invisible waves of sound. Each musician plays a single, pure note that repeats over and over. In the world of mathematics, this is called a "cosine polynomial." If you have a set of $n$ different notes, you can line them up and ask: "If I play all of them together, how loud can the silence get?"

Usually, when you mix sounds, they cancel each other out. Sometimes, they cancel perfectly, creating a moment of absolute quiet. But here is the puzzle: if you have a huge number of these notes, can you arrange them so that they never get very quiet? Or, conversely, is it impossible to avoid a moment where the sound drops to a very low, negative value? This is the heart of the "Chowla Cosine Problem." For decades, mathematicians wondered if there was a limit to how "quiet" these mixed waves could get. They knew that if you had a million notes, the sound would eventually dip below zero, but they didn't know how low it would go. Was it a tiny whisper, or a deep, resonant boom? Solving this helps us understand the hidden patterns in numbers and how they interact, much like figuring out the rules of a complex game.

This paper, written by Benjamin Bedert, steps into that game and changes the score. Before this work, the best we knew was that the sound would eventually get quiet enough to be described by a square root of the number of notes (roughly $\sqrt{n}$ ). It was a slow, steady climb. Bedert's paper proves something much stronger: the sound doesn't just get quiet; it gets very quiet, and it does so much faster than anyone thought possible.

The main finding is that if you have $n$ notes, the lowest point the sound reaches is guaranteed to be at least as low as $n^{1/5}$ (specifically, $n^{1/5-o(1)}$ ). To put that in perspective, if you have a million notes ($1,000,000$), the old math suggested the silence might be around $1,000$. Bedert's new math shows it's actually closer to $100$ (since $1,000,000^{1/5} = 100$ ). That is a massive difference in the depth of the silence. The paper proves this by showing that no matter how cleverly you arrange your notes, the universe of numbers forces a deep dip in the sound.

The author also tackles a more general version of the problem. Imagine that instead of every musician playing the same volume, some play louder and some play softer, but they all stick to a specific list of volume settings. Bedert shows that even in this messy, varied scenario, the sound still has to drop significantly. This is a big deal because previous methods were very fragile; they only worked if every note was exactly the same volume. Bedert's method is like a sturdy net that catches all these different arrangements, proving that the "deep silence" is a fundamental rule, not just a fluke of perfect symmetry.

However, the paper is careful not to claim it has solved the entire mystery. The ultimate question is whether the silence drops as low as the square root of $n$ (the $\sqrt{n}$ limit). Bedert's work proves it drops at least as fast as the fifth root, which is a huge leap forward, but it leaves a gap between the fifth root and the square root. The author suggests their method might be able to push the number even higher, perhaps getting closer to the square root, but that remains an open question. It's like finding a new, deeper valley in a mountain range; you've found a valley much deeper than anyone expected, but you haven't yet found the deepest possible point in the entire range.

The paper also explicitly rules out the idea that you could arrange these notes to keep the sound from dropping very low at all. It proves that for any large set of notes, a deep negative value is unavoidable. Furthermore, it warns that if you start allowing "multisets"—where you can pick the same note multiple times—the rules change completely, and the deep silence might not happen at all. This distinction is crucial: the magic of the deep silence relies on having a collection of unique notes.

In short, this paper is a mathematical tour de force that uses clever tricks with waves and numbers to prove that deep silence is inevitable in large collections of cosine waves. It moves the goalposts from a slow, logarithmic whisper to a powerful, polynomial boom, giving us a much clearer picture of how numbers behave when they dance together. While the final, perfect answer to the deepest possible silence is still out there, Bedert has definitely found a much deeper valley than we knew existed.

Technical Summary: Polynomial Bounds for the Chowla Cosine Problem

Problem Statement
The paper addresses the Chowla cosine problem, which concerns the lower bounds of cosine polynomials with distinct integer frequencies. Let $A \subset \mathbb{N}$ be a finite set of $n$ positive integers, and consider the cosine sum $f_A(x) = \sum_{a \in A} \cos(ax)$ . Since the integral of $f_A$ over $[0, 2\pi]$ is zero, the function must assume negative values. The central question, posed by Chowla, is to determine the magnitude of the largest possible negative value, defined as:
$K(n) = \inf_{A \subset \mathbb{N}, |A|=n} \left( -\min_{x} f_A(x) \right).$
While simple constructions (e.g., using Sidon sets) show that $K(n) \ll \sqrt{n}$ , Chowla conjectured that this bound is sharp ( $K(n) \asymp \sqrt{n}$ ). Prior to this work, the best known lower bounds were quasipolynomial, specifically $K(n) \gg e^{(\log n)^\varepsilon}$ by Bourgain, and later refined to $K(n) \gg e^{c'(\log n)^{1/2}}$ by Ruzsa. The problem remained open whether $K(n)$ could be bounded by a polynomial in $n$ .

Methodology
The author, Benjamin Bedert, employs a combination of harmonic analysis and additive combinatorics to establish polynomial lower bounds. The core strategy involves analyzing the structure of the set $A$ under the assumption that the minimum of the cosine sum is small (i.e., $f_A(x) + K \geq 0$ for a small $K$ ).

Fourier Analysis and Convolution: The problem is reformulated using the Fourier transform of the indicator function of a symmetric set $A \subset \mathbb{Z} \setminus \{0\}$ , denoted $\hat{1}_A(x)$ . The condition $f_A(x) + K \geq 0$ is translated into a non-negativity condition on $\hat{1}_A(x) + K$ . The author utilizes convolution properties, specifically that the convolution of non-negative functions remains non-negative, to derive inequalities involving higher-order convolutions of modified functions.
Auxiliary Functions: The proof introduces auxiliary functions $f_t(x) = 2(1 + \sin(2\pi tx))\hat{1}_A(x)$ and $g_t(x) = 2(1 - \sin(2\pi tx))\hat{1}_A(x)$ . By analyzing the Fourier coefficients of these functions and their convolutions (specifically triple convolutions in the initial proof and double convolutions in the improved proof), the author derives pointwise inequalities relating different subsets of the spectrum of $A$ .
Additive Structure: The argument relies on the fact that if the minimum is small, the set $A$ must possess significant additive structure (large additive energy). The author leverages results from Roth, Bourgain, and Ruzsa to show that if the minimum is small, $A$ contains large arithmetic progressions or specific difference sets.
Iterative Refinement:
- Section 5 (Exponent 1/12): A streamlined argument uses triple convolutions to relate the size of a specific subset $B_t \subset A$ to the parameter $K$ , yielding $K \gg n^{1/12}$ .
- Section 6 (General Coefficients): The method is extended to cosine polynomials with arbitrary finite coefficients $S \subset \mathbb{R} \setminus \{0\}$ via induction on the size of $S$ .
- Section 7 (Exponent 1/5): To improve the exponent, the author replaces the triple convolution argument with a more refined double convolution approach inspired by Bourgain. This involves decomposing the indicator function of a subset into a "main term" controlled by the original set and an "error term" with small $L^2$ norm. This allows for tighter bounds on the size of the relevant subsets.

Key Results
The paper establishes the first polynomial lower bounds for the Chowla cosine problem.

Theorem 1.1: For any set $A \subset \mathbb{N}$ of size $n$ , the minimum of the cosine sum satisfies:
$\min_{x} \sum_{a \in A} \cos(ax) \leq -n^{1/5 - o(1)}.$
Consequently, $K(n) \gg n^{1/5 - o(1)}$ .
Theorem 1.2: The result is generalized to cosine polynomials with coefficients in an arbitrary finite set $S \subset \mathbb{R} \setminus \{0\}$ . If $f(x) = \sum_{a \in A} s_a e(ax)$ with $s_a \in S$ , then $\min f(x) \leq -c'_S n^{c_S}$ for constants depending on $S$ . This contrasts with previous results which were sensitive to coefficients being restricted to $\{0, 1\}$ .

The paper notes that a simpler version of the argument yields the exponent $1/12$ , while the refined analysis in Section 7 achieves $1/5 - o(1)$ .

Significance and Claims
The primary significance of this work is the breakthrough from quasipolynomial bounds to polynomial bounds for the Chowla cosine problem. The author explicitly states that this establishes the first polynomial bounds for the problem.

The paper acknowledges that the exponent $1/5$ is likely not optimal and that the conjectured sharp bound is $K(n) \asymp \sqrt{n}$ . The author notes that their method might be capable of producing even better exponents, though determining the truth of the $n^{1/2}$ conjecture remains an open problem.

Additionally, the paper highlights a limitation: the polynomial bound fails if one considers multisets of integers rather than sets of distinct integers, citing a construction by Belov and Konyagin where coefficients in a specific range yield only logarithmic bounds. The author also mentions an independent preprint by Jin et al. which establishes a polynomial bound with exponent $1/10 - o(1)$ using a different structural approach based on graph eigenvalues.

The work does not claim to resolve the full Chowla conjecture but provides a significant step forward by demonstrating that the minimum value grows polynomially with the number of terms, rather than merely logarithmically or quasipolynomially.

More like this