[#P2622] Largest four-term-progression-free subset of Z_101

A neutral schematic of the objects and relations in the statement.

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$.

1Context

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

2Problem setup

Convention 1. Progressions and all arithmetic are taken modulo 101.

Remark 1. For nonzero $d$, the four terms $x,x+d,x+2d,x+3d$ are automatically distinct because 101 is prime.

3What 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.

1Status

Current status (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.^[1]

1Records

Record	Kind	Assessment
	Result	Reproduced
claim · Computation 1 An explicit 30-set supplies the lower endpoint. Exact incidence counting in the progression design gives the upper endpoint.^[1] Relevance to this problem For Largest four-term-progression-free subset of Z_101, record z101-four-ap-free-claim-certified-interval-30-67 (“The certified interval is 30 through 67”) records a bound, answer, status fact, or structural consequence. The record states: An explicit 30-set supplies the lower endpoint. Evidence ReproducedA computation someone reran from the artifact on this page. Record state open Scope subsets of Z/101Z containing no four distinct terms x, x+d, x+2d, x+3d with d nonzero Sources Reference 1 Details 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. Open full record →
	Trace	Inconclusive
attempt · Route 1 The checked cyclic-group paper supplies the framework but no value for these parameters. A small, auditable SAT instance would decide the optimum.^[1][2] Relevance to this problem For Largest four-term-progression-free subset of Z_101, record z101-four-ap-free-attempt-literature-audit-and-exact-plan (“Literature audit and exact-search specification”) documents a concrete method, search boundary, or failed route. The record states: The checked cyclic-group paper supplies the framework but no value for these parameters. Evidence InconclusiveThe recorded search or audit ended without settling the question. Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened Halbeisen and Halbeisen define $\alpha(n,r)$ as the independence number of the modular progression hypergraph and give exact values for selected smaller parameters. Their table has no row for $(101,4)$. The broader primary literature checked for four-term progression bounds is asymptotic and does not certify a sharper order-101 value. An exact computation can encode one Boolean variable $x_i$ for each residue. Each of the 5,050 edges contributes the clause $\bigvee_{i\in E}\neg x_i$. To test a target $k$, add an exact cardinality constraint $\sum_i x_i\geq k$. Affine maps $x\mapsto ux+v$, with $u\ne0$, preserve the hypergraph. For every solution of size at least two, one ordered selected pair can therefore be normalized to $0,1$. A complete upper certificate should use a proof-logging SAT or pseudo-Boolean solver, record the generator hash and normalized case split, and replay the emitted proof with an independent checker. Running targets downward until satisfiable would determine the exact value; the satisfying assignment supplies the matching lower witness. Related: Computation 1 Open full record →
	Artifact	Reproduced
artifact · Artifact 1 Standard-library Python verifies the 30-set and every vertex and pair incidence used in the upper-bound proof.^[1] Relevance to this problem For Largest four-term-progression-free subset of Z_101, record z101-four-ap-free-artifact-witness-and-design-bound (“Exact witness and incidence verifier”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python verifies the 30-set and every vertex and pair incidence used in the upper-bound proof. Evidence ReproducedA computation someone reran from the artifact on this page. Record state available Scope the complete four-term progression hypergraph on Z/101Z and the displayed 30-element independent set Sources Reference 1 Entry point `join source_lines with newline and run with python3` Runtime CPython 3, standard library only Details The verifier generates progressions using every $a\in\mathbb Z/101\mathbb Z$ and every nonzero $d$, then removes the reversal duplication by storing each progression as a sorted tuple. It obtains 5,050 edges. It checks all 20,200 vertex-edge incidences and all 30,300 pair-edge incidences, establishing degrees 200 and pair codegrees six. It then checks the displayed set against every edge and evaluates the final inequality at 68, the first excluded cardinality. The canonical report digest is `6edf6fac68fe92ce3563d0f3573215ee33c474019800b84a1dc15a57076f3a43`. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN as of 2026-07-25. An explicit 30-set supplies the lower endpoint. Exact incidence counting in the progression design gives the upper endpoint. The checked sources do not settle the full acceptance condition.

The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: An explicit 30-set supplies the lower endpoint. Exact incidence counting in the progression design gives the upper endpoint.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.

Recorded example 1. 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}.

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.

How the 3 records connectTyped relations and evidence flow

ProblemLargest four-term-progression-free subset of Z_101

Computation 1The certified interval is 30 through 67in this packetReproduced
Artifact 1Exact witness and incidence verifiersupportsReproduced
Route 1Literature audit and exact-search specificationcontextualizesInconclusive

2See also

Erdős Problem 152: isolated sums in Sidon setsadditive combinatorics
Infinitely many ones in the greedy three-term-progression-free sequenceadditive combinatorics
Difference size of Z_127additive combinatorics

How to cite

TheoremDB contributors, “Largest four-term-progression-free subset of Z_101,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/z101-four-ap-free

This page as plain text: z101-four-ap-free.md

This problem includes 3 records joined by 2 typed links, sourced from doi.org^[1], current as of July 25, 2026.

1References

Packet source. 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. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.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. 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.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.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.
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). ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.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.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.

CC0 finite extremal target with a directly checked lower-bound witness.

[#P2622] Largest four-term-progression-free subset of Z_101

1Context

2Problem setup

3What counts as a solution

1Status

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance