🔢 mathematics

Small complete 3-term progression free sets in cyclic groups and vector spaces

This paper resolves two open problems by providing explicit constructions that demonstrate the minimum size of complete 3-term arithmetic progression-free sets in cyclic groups and finite vector spaces is essentially tight with the square-root lower bound, specifically achieving sizes less than $2\sqrt{m}$ for cyclic groups and $p^{n/2+o(n)}$ for vector spaces.

Original authors: Bence Csajbók, Zoltán Lóránt Nagy

Published 2026-06-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Bence Csajbók, Zoltán Lóránt Nagy

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 party in a room with a very specific rule: No three guests can stand in a perfectly straight line.

In the world of mathematics, this "straight line" is called an arithmetic progression. If you have three numbers like 2, 4, and 6, they are in a straight line because they go up by the same amount (2) each time. The goal of this paper is to figure out the smallest possible group of people you need to invite to the party so that:

No three people in your group form a straight line.
If you try to add anyone else from the outside world to the group, they will immediately create a straight line with two people already inside.

Mathematicians call this a "complete progression-free set." It's like a puzzle where you want the smallest team that is "maximally safe" against forming lines.

The paper tackles this problem in two different "rooms" (mathematical structures): Cyclic Groups (like a clock face) and Vector Spaces (multi-dimensional grids).

The Big Question: How Small Can the Team Be?

Mathematicians already knew that the team size couldn't be tiny. If the room has $N$ spots, the team needs to be at least roughly the square root of $N$ (e.g., if the room has 100 spots, you need at least 10 people).

The big question this paper answers is: Is that square root limit the best we can do, or do we need a much bigger team?

The authors say: "You don't need a much bigger team. The square root limit is basically the best we can do."

Here is how they solved it for the two different rooms:

1. The Clock Room (Cyclic Groups)

Imagine a clock with $m$ hours. The numbers wrap around (after 12 comes 1).

The Problem: Find the smallest group of numbers on this clock that has no straight lines, but if you add any other number, a line appears.
The Old Guess: Previous work suggested you might need about $1.5 \times \sqrt{m}$ people.
The New Result: The authors built a specific recipe to create these groups. They proved that for any clock size, you can always find a group smaller than $2 \times \sqrt{m}$ .
- Analogy: If you have a clock with 10,000 hours, you don't need 10,000 people. You only need about 200 people to satisfy the rules.
The "Super" Rule: For most large clocks, they didn't just avoid lines; they avoided a specific, stricter type of line pattern called a "(2, -1) pattern." This is like saying, "Not only can't you stand in a straight line, you can't even stand in a specific zig-zag pattern."
The Catch: For very small clocks (fewer than 81 hours), the "super" rule doesn't always work, so they checked those specific small cases one by one using a computer.

2. The Multi-Dimensional Grid (Vector Spaces)

Now imagine a room that isn't just a clock, but a grid that stretches in many directions (dimensions). Think of it like a 3D video game world, but with $n$ dimensions.

The Problem: Find the smallest team in this $n$ -dimensional grid that has no straight lines but is "complete" (cannot be added to).
The Challenge: In these grids, the math gets very tricky, especially when the grid uses a specific type of number system (odd prime fields).
The New Result: The authors used a clever trick involving curved surfaces (quadratic graphs).
- Analogy: Imagine placing people on a curved hill. Because the hill is curved, it's very hard for three people to accidentally line up perfectly.
- They built a team on a large part of the grid using this curved hill method. For the remaining empty spots, they filled them in with a standard "safe" team.
The Outcome: They proved that for any fixed type of grid, the team size is roughly $\sqrt{N}$ (where $N$ $N$ is the total number of spots), plus a tiny bit of extra "fuzziness" that becomes negligible as the grid gets huge.
- In plain English: The team size grows at the same speed as the square root of the total room size. You don't need a massive army; the square root limit is essentially the perfect size.

The "Secret Sauce" of the Paper

The authors used two main tools to build their teams:

The "Binary" Recipe (for Clocks): They created a set of numbers based on a special pattern of adding and skipping numbers (like a binary code). This allowed them to pack the team tightly without forming lines, ensuring that every empty spot on the clock was "covered" by the team.
The "Curved Hill" Trick (for Grids): They used algebraic curves (equations that look like parabolas) to place people. Because curves naturally resist straight lines, this method creates very efficient teams. They then combined these curved teams with standard teams to cover every possible dimension.

What They Did Not Say

They did not say this has immediate uses in cryptography, medicine, or engineering. This is pure mathematics about the structure of numbers.
They did not claim they found the absolute smallest team for every single case (the "perfect" team). They found teams that are very close to the theoretical limit (within a small constant factor).
They did not solve the problem for every type of number system (specifically, they focused on odd prime fields for the grids).

Summary

Think of this paper as a master builder showing us how to build the smallest possible fence around a field.

The Goal: The fence must be strong enough that if you try to add one more post, the fence breaks (a line forms).
The Discovery: The builder proved that you don't need a fence that is huge. You only need a fence whose length is roughly the square root of the field's size.
The Method: They used clever patterns (like binary codes) and curved shapes (like hills) to pack the fence posts as tightly as mathematically possible without them forming a straight line.

This confirms that the "square root" rule isn't just a lower limit; it's essentially the true size of the problem.

Technical Summary: Small Complete 3-Term Progression Free Sets in Cyclic Groups and Vector Spaces

Problem Statement
The paper addresses the problem of determining the minimum size of a complete 3-term arithmetic progression (3-AP) free set in algebraic structures, specifically cyclic groups ( $\mathbb{Z}_m$ ) and finite vector spaces ( $\mathbb{F}_p^n$ ). While the maximum size of 3-AP-free sets is a central theme in additive combinatorics (e.g., Roth's theorem, Croot-Lev-Pach, Ellenberg-Gijswijt), the minimum size of a complete set (a set that cannot be enlarged without creating a 3-AP) represents the lower-end analogue. A simple counting argument establishes that the order of magnitude for this minimum size is at least the square root of the cardinality of the structure. The authors investigate whether this lower bound is tight, addressing open problems regarding the existence of such sets with size $O(\sqrt{|G|})$ in cyclic groups and $p^{n/2}$ in vector spaces.

Methodology
The authors employ a combination of explicit combinatorial constructions, modular reduction techniques, and algebraic geometry over finite fields.

Cyclic Groups ( $\mathbb{Z}_m$ ):
- Stronger Property: The authors focus on complete (2, -1)-avoiding sets. A set $A$ is (2, -1)-avoiding if $A \cap (2A \dot{-} A) = \emptyset$ (where $2A \dot{-} A = \{2a - b : a, b \in A, a \neq b\}$ ). It is complete if $G = A \cup (2A \dot{-} A)$ . This property is stronger than being complete 3-AP-free, as it forces every outside point to be an endpoint of a progression with endpoints in $A$ , rather than allowing the outside point to be a midpoint.
- R-Complete Sets: The construction relies on "R-complete" sets—integer subsets of $[0, R]$ that are internally (2, -1)-avoiding and saturate the interval $[-R, 2R]$ .
- Binary Digit Construction: Using a generalized binary digit construction (Lemma 3.3), the authors generate sets $P$ of size $2^n$ that are $S_n$ -complete. By carefully choosing the digit sequence $d_i$ , they ensure the resulting set covers a wide range of moduli $m$ .
- Modular Reduction: Lemma 3.2 demonstrates that an $R$ -complete set in $\mathbb{Z}$ descends to a complete (2, -1)-avoiding set in $\mathbb{Z}_m$ whenever $2R < m \leq 3R + 1$ .
- Finite Verification: For small moduli ( $m < 81$ ) where the general construction does not apply or where complete (2, -1)-avoiding sets may not exist, the authors perform an exhaustive enumeration to determine exact minimum sizes.
Vector Spaces ( $\mathbb{F}_p^n$ ):
- Quadratic Graphs: The core construction utilizes graphs of homogeneous quadratic maps $Q: U \to W$ . Specifically, they construct sets of the form $A_Q = \{(u, Q(u)) : u \in U\}$ .
- Endpoint-Midpoint Completeness: The authors define "endpoint-midpoint complete" sets, where every outside point can be represented both as an endpoint ( $x = 2a - b$ ) and as a midpoint ( $2x = c + d$ ) of a progression formed by elements in $A$ . This property is crucial for the product construction.
- Subfield Construction: They construct a quadratic map $Q(x, s) = x^2 - \delta s^2$ over an extension field $E = \mathbb{F}_{p^{kL}}$ and a subfield $T = \mathbb{F}_{p^k}$ , where $\delta$ is a non-square. Using character sums and the Weil bound, they prove that this map is surjective and has a trivial kernel, yielding a complete (2, -1)-avoiding set in a specific dimension $n_0 = k(2L+1)$ .
- Product Lemma: To extend the result to all dimensions $n$ , they use a product lemma (Lemma 4.2). If $A$ is endpoint-midpoint complete in a subspace and $B$ is complete 3-AP-free in the remaining coordinates, their product $A \times B$ is complete 3-AP-free in the full space. This allows "padding" the special dimensions with smaller sets to cover arbitrary $n$ .

Key Contributions and Results

Cyclic Groups:
- Theorem 1.2: For every integer $m \geq 1$ , there exists a complete 3-AP-free set $A \subseteq \mathbb{Z}_m$ with size $|A| < 2\sqrt{m}$ .
- Stronger Result for Large $m$ : For $m \geq 81$ , the constructed set satisfies the stronger complete (2, -1)-avoiding property.
- Small Moduli: The paper provides a table of exact values for $a(3\text{-AP}, \mathbb{Z}_m)$ and $a(2, -1)(\mathbb{Z}_m)$ for $m \leq 80$ , noting that complete (2, -1)-avoiding sets do not exist for certain small moduli (e.g., $m \in \{2, 5, 6, 8, 17, 18, 19, 20\}$ ).
Vector Spaces:
- Theorem 1.3: For every fixed odd prime $p$ and $\epsilon > 0$ , there exists a constant $C_{p,\epsilon}$ such that for all $n \geq 1$ :
  $a(3\text{-AP}, \mathbb{F}_p^n) \leq C_{p,\epsilon} n^{1+\epsilon} p^{n/2} = p^{n/2 + o(n)}$
- This result resolves the vector space variant in the sense that the exponent of $p$ is exactly $n/2$ , matching the lower bound up to a sub-exponential factor.

Significance and Claims
The paper claims to resolve two open problems regarding the tightness of the square-root lower bound for complete progression-free sets:

Cyclic Groups: It establishes that the lower bound is tight up to an absolute constant (specifically 2) for all cyclic groups, and provides explicit constructions for the stronger (2, -1)-avoiding property for $m \geq 81$ .
Vector Spaces: It settles the exponent version of the problem for fixed odd prime fields, showing that the minimum size is $p^{n/2 + o(n)}$ . This confirms that the trivial counting bound is essentially sharp in terms of the exponential growth rate.

The authors note that while the constant factor in the cyclic group result ($2$) is above the $3/2$ target suggested in their previous work, the construction is deliberately restricted to the stronger (2, -1)-avoiding property. They suggest that exploiting the extra freedom of standard 3-AP-completeness (allowing outside points to be midpoints) might yield smaller constructions. Similarly, for vector spaces, the question of a uniform absolute constant independent of $n$ and the existence of such bounds for complete (2, -1)-avoiding sets in every dimension remain open. The work connects these additive combinatorics problems to finite geometry, specifically complete caps and saturating sets.