🔢 mathematics

Roth-type theorems in $K_{s,t}$ -free sets

This paper extends Roth-type theorems for Sidon sets to the broader family of $K_{s,t}$ -free sets, proving that sufficiently large such subsets of integers or finite vector spaces must contain nontrivial solutions to any fixed translation-invariant linear equation in at least five variables, with stronger quantitative bounds achieved in the finite field setting via a combination of Fourier analysis and polynomial methods.

Original authors: Yifan Jing, Cosmin Pohoata, Max Wenqiang Xu

Published 2026-01-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Yifan Jing, Cosmin Pohoata, Max Wenqiang Xu

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 organizing a massive party in a city with $N$ houses. You want to invite a group of people (a subset of the city) to your party, but you have a very specific rule: No "Kissing Squares."

In the world of math, a "Kissing Square" (or $K_{s,t}$ -free condition) is a pattern where you have $s$ people and $t$ other people, and every single one of the first group can be paired with every single one of the second group to form a specific relationship (like a sum). If your party guests contain even one tiny version of this pattern, you've broken the rule.

The authors of this paper, Jing, Pohoata, and Xu, are asking a fascinating question: If you manage to invite a huge number of people while strictly avoiding this "Kissing Square" pattern, does your guest list still have to have some hidden, predictable structure?

Specifically, they are looking for "non-trivial solutions" to a type of math puzzle called a translation-invariant linear equation.

The Puzzle: Imagine an equation like $x_1 + x_2 + x_3 + x_4 + x_5 = 0$ (where the numbers add up to zero).
The Trivial Solution: Everyone picks the same number (e.g., $0+0+0+0+0=0$ ). This is boring and expected.
The Non-Trivial Solution: Everyone picks different numbers that still add up to zero. This is the "magic" the authors are hunting for.

The Main Discovery: The "Five-Variable" Threshold

The paper proves a surprising threshold. If your party is large enough (specifically, if you have about $N^{1 - 1/s}$ guests), and you have successfully avoided the "Kissing Square" pattern, you cannot avoid having a non-trivial solution to any equation with 5 or more variables.

Think of it like this:

If you try to build a guest list that is "chaotic" (avoiding the $K_{s,t}$ pattern) but also "random" (avoiding 5-variable equations), you will fail.
The math says: You can't have your cake and eat it too. If you are big enough to be interesting, you are forced to have structure.

The authors show that if you do manage to avoid these 5-variable solutions, your party size must be tiny—so tiny that it's almost negligible compared to the city size.

The Two Worlds: Integers and Finite Fields

The paper tackles this problem in two different "universes":

1. The Integer Universe (The City of Whole Numbers)
Here, the numbers are $1, 2, 3, \dots, N$ .

The Result: If you have a large $K_{s,t}$ -free set, it must contain a solution to any 5-variable equation.
The "How": The authors use a clever trick called Fourier Analysis. Imagine the guest list as a sound wave. They show that if the list is "sparse" (avoiding the pattern), the sound wave has a specific shape. They then prove that this shape forces the existence of the 5-variable solution.
The Catch: The proof is a bit "fuzzy." It shows the set must be small, but the bound isn't perfectly sharp. It's like saying, "If you don't have the solution, your party is smaller than $N$ divided by a very complicated, slowly growing number."

2. The Finite Field Universe (The Digital Grid)
Here, the numbers wrap around like a clock (e.g., in a world where $10 + 1 = 1$ ).

The Result: The same rule applies, but the math is much sharper here.
The "How": Because the "grid" is more structured, the authors can use a powerful tool called the Polynomial Method (famous for solving the "Cap Set" problem). This is like having a high-resolution microscope instead of a fuzzy telescope.
The Payoff: They get a much stronger result. They prove that if you avoid the solution, your party size is smaller by a factor of a polylogarithm (a power of a logarithm). This is a "cleaner" and more precise bound than in the integer world.

The Secret Sauce: How They Did It

The authors didn't just guess; they used a three-step "transference" strategy, which is like a magic trick with three phases:

The "Dense Model" (The Blurry Photo):
They take their sparse, weird guest list and "blur" it into a smooth, dense cloud of numbers. This cloud is easier to analyze. They prove that this cloud looks almost exactly like the original list, but it's "dense" enough to use standard math tools on.
The "Counting" (The Crowd Check):
They use known results to count how many solutions exist in this "dense cloud." Because the cloud is dense, standard math says there must be a huge number of 5-variable solutions.
The "Transfer" (The Reality Check):
They compare the "blurry cloud" back to the "real guest list." They show that the difference between the two is so small that if the cloud has solutions, the real list must have them too.
- The Twist: If the real list didn't have these solutions, the math would lead to a contradiction (the list would have to be impossibly small). Therefore, the list must have the solutions.

Why 5 Variables?

You might wonder, "Why 5? Why not 3 or 4?"
The paper explains that for 3 or 4 variables, the "Kissing Square" rule (Sidon sets) is so strong that it naturally blocks those specific equations. For example, in a Sidon set, the equation $x + y = z + w$ (4 variables) is impossible to solve with distinct numbers.
However, once you hit 5 variables, the "Kissing Square" rule isn't strong enough to block the equation anymore. The math forces the structure to appear.

Summary

In simple terms, this paper proves that large groups of numbers that avoid a specific "grid" pattern are forced to contain complex, hidden relationships (solutions to 5-variable equations).

In the real world (integers), this is true, but the proof is a bit rough around the edges.
In the digital world (finite fields), the proof is precise and sharp, thanks to modern polynomial tools.

The authors essentially showed that you cannot build a large, pattern-free structure that is also completely free of 5-variable arithmetic relationships. The universe of numbers demands a little bit of order, even in the most chaotic-looking sets.

Technical Summary: Roth-Type Theorems in $K_{s,t}$ -Free Sets

Problem Statement
This paper investigates the arithmetic structure of dense subsets of integers (and finite fields) that avoid specific additive configurations. Specifically, it considers $K_{s,t}$ -free sets. A set $A \subseteq [N]$ is defined as $K_{s,t}$ -free if it contains no configuration of the form $\{x_i + y_j : 1 \le i \le s, 1 \le j \le t\}$ where the $x_i$ are distinct and the $y_j$ are distinct. Equivalently, $A$ contains no subset of the form $B+C$ with $|B|=s$ and $|C|=t$ .

The central question is whether such sets, even when they are dense (specifically of size $\Omega(N^{1-1/s})$ , which matches the extremal bound from the Kővári–Sós–Turán theorem), must contain nontrivial solutions to fixed translation-invariant linear equations in at least five variables. The authors aim to extend previous results known for Sidon sets ( $K_{2,2}$ -free sets) to the general family of $K_{s,t}$ -free sets.

Methodology
The authors employ a Fourier-analytic transference principle, a framework previously utilized by Conlon, Fox, Sudakov, Zhao, and Prendiville for Sidon sets. The proof strategy is divided into three main components:

Dense Model Construction (Fourier Approximation):
Given a sparse $K_{s,t}$ -free set $A$ with density $\delta \approx N^{-1/s}$ , the authors construct a non-negative "dense model" function $f$ that approximates the renormalized indicator function of $A$ .
- Integers: They utilize a Bohr set constructed from the large spectrum of $A$ . A key technical challenge is controlling the rank of this Bohr set, which is achieved by leveraging the $K_{s,t}$ -freeness of $A$ to bound higher moment energies.
- Finite Fields: The construction simplifies significantly. The analogue of a Bohr set is an actual subspace. By choosing a subspace that annihilates the large spectrum of $A$ , they create a function $f$ that preserves large Fourier coefficients while maintaining good $L^s$ control.
Dense Counting (Supersaturation):
Once the dense model $f$ is established, the authors apply counting lemmas to show that $f$ must contain many solutions to the target linear equation $a_1 x_1 + \dots + a_k x_k = 0$ (where $\sum a_i = 0$ and $k \ge 5$ ).
- Integers: They rely on quantitative results for dense sets in $[N]$ , specifically refinements of Bloom-type bounds.
- Finite Fields: They utilize the polynomial method, specifically the arithmetic $k$ -cycle removal lemma by Fox, Lovász, and Sauermann, which provides polynomial supersaturation bounds derived from the cap set problem literature.
Transference (Telescoping and Moment Control):
The final step compares the number of solutions in the dense model $T(f)$ with the number of solutions in the original set $T(\nu)$ (where $\nu$ is the renormalized indicator of $A$ ). Using a telescoping identity and Hölder estimates, the authors bound the error term $|T(f) - T(\nu)|$ . This error depends on the $L^2$ energy (second moment) of the majorant function. The $K_{s,t}$ -freeness condition is crucial here, as it provides strong control over the second moment energy, allowing the transfer of the lower bound from the dense model back to the sparse set.

Key Contributions and Results

Theorem 1.1 (Integer Case):
For integers $2 \le s \le t$ , any $K_{s,t}$ -free subset $A \subseteq [N]$ that lacks nontrivial solutions to a translation-invariant linear equation in $k \ge 5$ variables satisfies:
$|A| \ll N^{1-1/s} \exp\left(-O_{a_i, s, t}((\log \log N)^{1/7})\right)$
This result generalizes the qualitative and quantitative bounds previously known for Sidon sets ( $s=t=2$ ) to the full family of $K_{s,t}$ -free sets. The proof relies on an $L^s$ -dense model theorem, extending the $L^2$ -based approaches used in prior work.
Theorem 1.2 (Finite Field Case):
In the vector space $\mathbb{F}_q^n$ (where $q$ is a fixed odd prime power), for any $K_{s,t}$ -free set $A$ lacking nontrivial solutions to the same class of equations:
$|A| \ll N^{1-1/s} (\log N)^{-c}$
for some constant $c > 0$ . This result achieves stronger quantitative bounds (polylogarithmic savings) compared to the integer case by combining Fourier transference with the polynomial method (specifically the Fox–Lovász–Sauermann lemma).
Optimality of $k \ge 5$ :
The authors note that the condition $k \ge 5$ is optimal. For $k=4$ (e.g., $x_1+x_2=x_3+x_4$ ) or $k=3$ (e.g., $x+y=2z$ ), the $K_{s,t}$ -free condition (specifically for $s=t=2$ , i.e., Sidon sets) already excludes nontrivial solutions by definition.

Significance
The paper claims to extend the understanding of arithmetic structure in sparse sets from the specific case of Sidon sets to the broader class of $K_{s,t}$ -free sets. By establishing that dense $K_{s,t}$ -free sets must contain solutions to 5-variable linear equations, the authors demonstrate that these sets possess significant arithmetic structure despite their sparsity.

The work bridges extremal graph theory (via the $K_{s,t}$ -free condition and Kővári–Sós–Turán bounds) with additive combinatorics. In the finite field setting, the paper highlights the power of combining Fourier analytic transference with polynomial method techniques to obtain sharper quantitative bounds than currently possible in the integer setting. The results represent a step toward a unified theory of Roth-type theorems for sets defined by forbidden additive configurations.