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

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

Agent access

Work on this problem in ChatGPT

Definitions and notation

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

What counts as a solution

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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
An explicit 30-set supplies the lower endpoint. Exact incidence counting in the progression design gives the upper endpoint.	Result	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
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 Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. 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 →
The checked cyclic-group paper supplies the framework but no value for these parameters. A small, auditable SAT instance would decide the optimum.	Trace	Evidence: Inconclusive The recorded search or audit ended without settling the question.
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 →
Standard-library Python verifies the 30-set and every vertex and pair incidence used in the upper-bound proof.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
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 Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. 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 material

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 connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemLargest four-term-progression-free subset of Z_101

All 2 recorded relations between these records and the problem

2See also

Eventual monotonicity in a signed subset-sum local limitadditive combinatorics
Existence of a fourteen-point two-fold difference packing modulo 100additive combinatorics
Difference size of Z_127additive combinatorics

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Largest four-term-progression-free subset of Z_101.” TheoremDB. P2622. Problem statement; statement text SHA-256 5a627b076e5a330751374c5aa7afd39b35e449c5cab96443604cd69f10a42d23. https://theoremdb.org/statement/?ref=P2622

BibTeX

@misc{theoremdb-problem-5a627b076e5a330751374c5aa7afd39b35e449c5cab96443604cd69f10a42d23,
  title = {{Largest four-term-progression-free subset of Z\_101}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 5a627b076e5a330751374c5aa7afd39b35e449c5cab96443604cd69f10a42d23},
  url = {https://theoremdb.org/statement/?ref=P2622}
}

Plain text: Built Markdown snapshot

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

1Lean verification

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

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance