# P2622: Largest four-term-progression-free subset of Z_101

- ID: `P2622`
- Reference: `z101-four-ap-free`
- Page: https://theoremdb.org/statements/P2622
- Record maturity: Reviewed problem with recorded work

## Problem

Determine the maximum size of a subset \(A\subseteq\mathbb Z/101\mathbb Z\) containing no four distinct elements of the form \(x,x+d,x+2d,x+3d\) with \(d\ne0\).

### Context

This is a finite extremal problem for four-term arithmetic progressions in the prime cyclic group of order 101.

### Problem setup

- **Convention.** Progressions and all arithmetic are taken modulo 101.
- **Remark.** For nonzero \(d\), the four terms \(x,x+d,x+2d,x+3d\) are automatically distinct because 101 is prime.

### What counts as a solution

- Give a progression-free set attaining the maximum and a complete proof or independently checkable certificate that no larger progression-free subset of \(\mathbb Z/101\mathbb Z\) exists.

## Status

An explicit 30-set supplies the lower endpoint. Exact incidence counting in the progression design gives the upper endpoint. [2](#reference-2)

## Work

### Evidence for the current status

**Computation 1 (The certified interval is 30 through 67).** An explicit 30-set supplies the lower endpoint. Exact incidence counting in the progression design gives the upper endpoint.

Write \(\alpha(101,4)\) for the requested maximum. The independently replayed bounds are
\[
\boxed{30\leq\alpha(101,4)\leq67}.
\]
The lower bound is witnessed by
\[
\{0,10,18,23,27,29,35,37,39,40,45,47,48,49,56,61,65,68,69,70,72,76,78,79,84,85,87,91,93,95\}.
\]
The executable artifact generates all 5,050 distinct modular four-term progressions and checks that none lies inside this set.

For the upper bound, let \(H\) be the four-uniform progression hypergraph. Every vertex lies in 200 edges, and every unordered pair lies in six edges. If \(A\) is independent and \(j_E=|A\cap E|\), then \(j_E\leq3\). Double-counting selected pairs and selected vertex-edge incidences gives
\[
6\binom{|A|}{2}=\sum_E\binom{j_E}{2}\leq\sum_Ej_E=200|A|.
\]
For positive \(|A|\), this yields \(3(|A|-1)\leq200\), hence \(|A|\leq67\). The exact value remains open within this record.

### Background and intake notes

- Original intake status: Status remains unverified. Exact progression-free numbers for small cyclic groups may be tabulated.
- Model the 5050 distinct four-point progression sets as a hypergraph and solve maximum independent set with translation and multiplication symmetries fixed.
- Trap: checking integer progressions in representatives 0 through 100 misses progressions that wrap modulo 101.

- Recorded example: A verified 30-set is {0,10,18,23,27,29,35,37,39,40,45,47,48,49,56,61,65,68,69,70,72,76,78,79,84,85,87,91,93,95}.

### Prior approaches

- **Route 1** (inconclusive): The checked cyclic-group paper supplies the framework but no value for these parameters. A small, auditable SAT instance would decide the optimum. [2](#reference-2) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python verifies the 30-set and every vertex and pair incidence used in the upper-bound proof. [2](#reference-2)

### Computational notes

- The 5050 distinct modular four-term progressions were generated exactly. Thirty thousand seeded random greedy orders produced the displayed 30-set, and a direct scan verified that it contains none of those progressions.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `z101-four-ap-free`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Ben Green and Terence Tao, “AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM”. Proceedings of the Edinburgh Mathematical Society 51(1) (2008), 73-153. DOI 10.1017/S0013091505000325. Introduction and discussion of r_4(G) https://doi.org/10.1017/S0013091505000325
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Largest four-term-progression-free subset of Z_101: Literature audit and exact-search specification. The checked cyclic-group paper supplies the framework but no value for these parameters. A small, auditable SAT instance would decide the optimum.
2. <a id="reference-2"></a>Lorenz Halbeisen and Stephanie Halbeisen, “Avoiding arithmetic progressions in cyclic groups”. Elemente der Mathematik 60(3) (2005), 114-123. DOI 10.4171/EM/16. Lorenz and Stephanie Halbeisen, Avoiding arithmetic progressions in cyclic groups, Sections 0 and 3; the order-101 incidence calculation is independently derived here; Lorenz and Stephanie Halbeisen, Avoiding arithmetic progressions in cyclic groups, definition of alpha(n,r), hypergraph formulation, and summary https://doi.org/10.4171/EM/16
   - Also cited at Sections 0 and 3
   - Also cited at Lorenz and Stephanie Halbeisen, Avoiding arithmetic progressions in cyclic groups, Sections 0 and 3; the order-101 incidence calculation is independently derived here
   - Also cited at Lorenz and Stephanie Halbeisen, Avoiding arithmetic progressions in cyclic groups, definition of alpha(n,r), hypergraph formulation, and summary
   - Also cited at Independent exact computation, 2026-07-25
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Largest four-term-progression-free subset of Z_101: The checked cyclic-group paper supplies the framework but no value for these parameters. A small, auditable SAT instance would decide the optimum.
   - Source named by the research packet.