🔢 mathematics

Almost Affine Invariance Over Prime Fields: Green Problem 90

This paper resolves Ben Green's Open Problem 90 by proving that for a subset of the finite field $\mathbb{F}_p$ with density 1/2, the threshold for simultaneous almost affine invariance under all transformations $\phi(x)=ax+b$ with $|a|, |b| \le K$ is $K=o(\log p)$ .

Original authors: Jie Ma, Quanyu Tang, Max Wenqiang Xu

Published 2026-05-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jie Ma, Quanyu Tang, 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 have a giant, circular clock face with $p$ numbers on it (where $p$ is a very large prime number). You decide to paint exactly half of these numbers black and leave the other half white. This is your set $A$ .

Now, imagine you have a set of rules for moving these numbers around. A rule looks like this: "Take every number $x$ , multiply it by $a$ , add $b$ , and see where it lands." This is called an affine transformation.

The big question Ben Green asked (and this paper answers) is: How many different rules can you have before your black-and-white pattern gets completely messed up?

If you apply a rule and the pattern looks almost exactly the same (maybe just a few dots shifted), we call it "almost invariant." The paper investigates how large the range of numbers $a$ and $b$ can be before it becomes impossible to keep the pattern looking the same.

The Main Discovery: The "Logarithmic" Limit

The authors found a very specific "tipping point" or threshold.

The Result: The range of rules you can use is limited by a number that grows very slowly, specifically $o(\log p)$ .
The Analogy: Imagine the clock face is the size of a stadium. The number of rules you can use is limited to something like the number of letters in a short sentence. Even if the stadium gets the size of the Earth, the number of rules you can use only grows as fast as the number of letters in a paragraph.
What this means: If you try to use more rules than this tiny limit (for example, if you try to use rules where the numbers go up to the square root of the stadium size), it is mathematically impossible to keep half the clock black and half white while keeping the pattern stable. The pattern must break.

How They Proved It: Two Sides of the Coin

The paper proves this in two parts, like solving a puzzle from both ends.

1. The "Upper Bound" (Why you can't go higher)

The Strategy: They used a technique called Fourier Analysis.
The Metaphor: Imagine your black-and-white pattern is a song. Fourier analysis breaks the song down into its individual musical notes (frequencies).

If the pattern stays the same when you shift the numbers (translation), the "song" must be missing the high-pitched, fast-vibrating notes. It only has low, slow notes.
If the pattern also stays the same when you stretch the numbers (multiplication), the "song" has to be even more restricted.
The authors showed that if you try to stretch the pattern too many different ways (too many rules), the song would have to be silent. But a silent song means you have no black dots and no white dots, which contradicts the rule that you must have half black and half white.
The "Valuation" Trick: A key insight (suggested by AI, according to the paper's disclosure) was looking at how many times a number can be divided by a prime number (like how many times you can divide 8 by 2 to get 4, then 2, then 1). They showed that for the pattern to survive all these rules, the numbers would need to be divisible by primes in a way that is mathematically impossible if the range of rules is too big.

2. The "Lower Bound" (Showing it is possible within the limit)

The Strategy: They used the Probabilistic Method.
The Metaphor: Instead of trying to build a perfect pattern by hand, they asked: "What if we just randomly paint the clock?"

If you paint the clock randomly, it won't be perfect. But they proved that if you restrict your rules to that small "logarithmic" range, there is a non-zero chance that a random painting will work.
They used a mathematical tool called the "bounded difference inequality." Think of this as a safety net. It proves that if you tweak your random painting slightly (changing a few dots), the overall pattern doesn't collapse.
Because the "safety net" holds, they proved that a perfect pattern must exist, even if we can't easily write down exactly what it looks like.

The "AI" Note

The authors were transparent about their process. They mentioned using an AI tool (ChatGPT) to help brainstorm.

The AI suggested the idea of looking at "prime valuations" (the division trick mentioned above), which turned out to be the key to solving the upper bound.
However, the AI also made logical mistakes, which the human authors had to fix. The final proof is a collaboration between human mathematical rigor and AI-assisted idea generation.

Summary

In simple terms: You can have a half-black, half-white pattern on a giant clock that survives a small number of stretching and shifting rules. But if you try to make the rules too complex (beyond a very slow-growing limit), the pattern is doomed to break. This paper found the exact speed limit for those rules.

Technical Summary: Almost Affine Invariance over Prime Fields

Problem Statement
This paper addresses Problem 90 from Ben Green's list of 100 open problems. The problem concerns the existence of a subset $A \subset \mathbb{F}_p$ with density $1/2$ that is "almost invariant" under a family of affine transformations $\phi(x) = ax + b$ . Specifically, a set $A$ is almost invariant under $\phi$ if the symmetric difference $|A \triangle \phi(A)| = o(p)$ as $p \to \infty$ . The central question is to determine the threshold range for the parameter $K = K(p)$ such that there exists a set $A$ satisfying this almost invariance condition simultaneously for all affine maps where $1 \le |a| \le K$ and $|b| \le K$ .

Methodology
The authors employ a two-pronged approach to determine the sharp threshold for $K$ : an analytic upper bound and a probabilistic lower bound.

Upper Bound (Fourier Analysis and Valuation Theory):
To prove that $K$ cannot be large, the authors utilize Fourier analytic tools. They define a function $f = 1_A - \alpha$ (where $\alpha \approx 1/2$ ) and analyze its Fourier transform $\hat{f}$ .
- Translation Invariance: The condition of almost invariance under translations ( $b$ ) implies that the Fourier mass of $f$ is concentrated on low frequencies, specifically $|r| \ll p/K$ .
- Multiplicative Invariance: The condition of almost invariance under dilations ( $a$ ) is analyzed by considering a probability measure $\mu$ on the frequencies, proportional to $|\hat{f}(r)|^2$ . The dilation invariance implies that $\mu$ is approximately invariant under the maps $r \mapsto qr$ for primes $q \le K$ .
- Valuation Argument: By restricting $\mu$ to a probability measure $\lambda$ on the integers $\{1, \dots, N\}$ (where $N \approx p/K$ ), the authors show that the $q$ -adic valuation $v_q(n)$ must be large for almost all $n$ under $\lambda$ for every prime $q \le K$ . This leads to a contradiction unless the sum of logarithms of primes up to $K$ is small, specifically $\sum_{q \le K} \log q = o(\log p)$ , which implies $K = o(\log p)$ .
Lower Bound (Probabilistic Construction and Concentration):
To prove that $K = o(\log p)$ is achievable, the authors construct such a set using the probabilistic method.
- Følner Sequences: The core of the construction relies on Lemma 3.3, which establishes the existence of large "Følner sequences" (sets $A$ with small symmetric difference under group actions) for a small family of affine transformations $S_p$ .
- Rational Models: The authors construct a family of rational affine maps over $\mathbb{Q}$ , parameterized by products of small primes, and reduce them modulo $p$ . This ensures the necessary injectivity and non-collision properties required for the probabilistic argument.
- Concentration Inequalities: A random set $A$ is defined based on a majority vote of random signs assigned to orbits of the involution $x \mapsto -x$ . While the expected size of $A$ and the expected symmetric difference are favorable, the authors employ the bounded difference inequality (McDiarmid's inequality) to show that these quantities concentrate sharply around their means, guaranteeing the existence of a specific set $A$ satisfying the conditions with positive probability.

Key Contributions and Results
The paper establishes the sharp threshold for the parameter $K$ :

Theorem 1.2: Let $p$ $p$ be a prime and $K = K(p)$ $K = K (p)$ be a positive integer.
- If there exists a set $A \subset \mathbb{F}_p$ with density $1/2 + o(1)$ that is almost invariant under all $\phi(x) = ax+b$ with $1 \le |a| \le K$ and $|b| \le K$ , then $K = o(\log p)$ .
- Conversely, if $K = o(\log p)$ , such a set $A$ exists.

This result resolves Green's Open Problem 90 by confirming that the threshold is indeed logarithmic in $p$ . It refines previous unpublished work by Eberhard, Mrazović, and Green, which suggested $K$ could grow slowly (e.g., $(\log p)^c$ ) but not as fast as $p^{1/100}$ . The current work narrows this down to $o(\log p)$ .

Significance
The paper provides a definitive answer to a specific structural question in additive combinatorics regarding the rigidity of sets under affine transformations. By combining Fourier analysis with probabilistic constructions, the authors demonstrate that the simultaneous satisfaction of almost invariance under a large family of affine maps imposes a strict logarithmic limit on the size of that family. The work also highlights the utility of amenability arguments in affine groups and the effectiveness of probabilistic methods in constructing sets with specific invariance properties over finite fields.

AI Disclosure
The authors note that AI (ChatGPT 5.4) was used in the development of the paper. Specifically, the idea of formulating the problem using $q$ -adic valuations (Lemma 2.4) and the initial application of amenability of the affine group were suggested by AI. However, the authors emphasize that the AI's initial arguments contained logical gaps and that the rigorous proofs and the final sharp bound are the result of human refinement and verification. The authors also acknowledge that the amenability approach was previously discussed in unpublished work and online forums (MathOverflow).