we-solve (beta)

Math-518 · mathematics · Combinatorics

Progressions in Subsets of Z/NZ

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For an abelian group $G$, let $r_k(G)$ be the largest size of a subset containing no progression $a,a+d,\ldots,a+(k-1)d$ with distinct terms. The second target explicitly uses $G={\mathbb{F}}_5^n$, $|G|=N=5^n$. In the first target, $r_5(N)$ denotes the largest size of a subset of $[N]=\{1,\ldots,N\}$ containing no five distinct terms in arithmetic progression (the interval convention of the cited problem list). In either inequality $c>0$ must be independent of $N$. [S1] [S2]

Statement recorded in the supplied source.
Is $r_5(N) \ll N(\log N)^{-c}$? Is $r_4(\mathbb{F}_5^n) \ll N^{1-c}$ where $N = 5^n$? [S1]
Scope and interpretation.

The archive title mentions a cyclic group, while its cited problem-list notation uses an integer interval in the first question. The interval convention is explicit above; the source statement itself is retained below. [S1]

Residual task reported by the archive.

The embedded review (2026-08-17) records: Obtain polynomial logarithmic/exponential savings in the stated settings. [S1]

Short English statement

Can five-term-progression-free integer sets be bounded by a logarithmic density loss, and four-term-progression-free sets over the five-element field by a power loss?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-518-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-518

Progression-free density and reciprocal sums: The interval r_5(N) clause receives a stronger-than-logarithmic density decay. The independent four-term progression problem in vector spaces over F_5 is not addressed.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Progressions in Subsets of Z/NZ

OpenAI's claim

Progression-free density and reciprocal sums: For each fixed length $k\ge3$, the claimed progression-free density decays as $\exp(-c_k(\log N)^{\varepsilon_k})$ up to a fixed factor. This quantitative estimate is used to deduce arbitrarily long progressions from a divergent reciprocal sum.

Mathematical statement of the claimed result

Mathematical claim 1.
For each fixed integer $k\ge3$, let $r_k(N)$ denote maximal cardinality among subsets of $\{1,\ldots,N\}$ containing no arithmetic progression $a,a+d,\ldots,a+(k-1)d$ with $d\ne0$. The claim gives constants $C_k,c_k,\epsilon_k>0$ with \[r_k(N)\le C_kN\exp\{-c_k(\log N)^{\epsilon_k}\}\quad(N\ge2).\] Its divergent-reciprocal-sums corollary asserts \[A\subset\mathbb N,\ \sum_{a\in A}a^{-1}=\infty\quad\Longrightarrow\quad A\text{ contains a nonconstant progression of every finite length}.\] This concerns sets of distinct positive integers. It does not settle a separate finite-field progression clause.

Outline of the argument

Progression-free density and reciprocal sums: Density increments take place inside triangular polynomial cells rather than repeatedly discarding inherited structure. Integer coordinate blocks and exact substitution retain old constraints when new ones are added. A hierarchy of precision costs bounds the total logarithmic length loss by a polynomial in the logarithmic density parameter, enabling the quasipolynomial estimate and the reciprocal-sum consequence.

Formal verification

Family 159 describes Lean coverage for the divergent-reciprocal-sum progression consequence; the quantitative progression-free density bound is not selected.

Progression-free density and reciprocal sums: The manuscript links ErdosReciprocal.lean.

The documented selection does not cover the entire manuscript assertion relevant here.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →

Math-518-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-518

Longer Progressions in Dense Sets

Definitions and mathematical statement

Shared notation.
Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For an abelian group $G$, let $r_k(G)$ be the largest size of a subset containing no progression $a,a+d,\ldots,a+(k-1)d$ with distinct terms. The second target explicitly uses $G={\mathbb{F}}_5^n$, $|G|=N=5^n$. In the first target, $r_5(N)$ denotes the largest size of a subset of $[N]=\{1,\ldots,N\}$ containing no five distinct terms in arithmetic progression (the interval convention of the cited problem list). In either inequality $c>0$ must be independent of $N$. [S1] [S2]

Statement recorded in the supplied source.
Is $r_5(N) \ll N(\log N)^{-c}$? Is $r_4(\mathbb{F}_5^n) \ll N^{1-c}$ where $N = 5^n$? [S1]
Scope and interpretation.

The archive title mentions a cyclic group, while its cited problem-list notation uses an integer interval in the first question. The interval convention is explicit above; the source statement itself is retained below. [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Obtain polynomial logarithmic/exponential savings in the stated settings. [S1]

Short English statement

Can five-term-progression-free integer sets be bounded by a logarithmic density loss, and four-term-progression-free sets over the five-element field by a power loss?

Research attempt

Provenance and scope.
This individual attempt was generated by GPT-6 Astra Ultra on 1 October 2026. The method was to derive explicit partial results and test the first proposed extension adversarially. The original statement and sources below are retained. No claim of mathematical novelty or complete solution is made.
Formal targets and context.
There are two different questions: an upper bound $r_5(N)\ll N/(\log N)^c$ for intervals, and $r_4({\mathbb{F}}_5^n)\ll5^{(1-c)n}$ for some fixed positive $c$. The interval and finite-field statements are not interchangeable. The primary problem list retains these two targets separately. We work on the finite-field question, where four points of a progression have a useful geometric interpretation, and then test whether product constructions can give the desired upper bound.
Four-term progressions are four points of a five-point line.
Every affine line in ${\mathbb{F}}_5^n$ has five points. Any four distinct points of that line form a four-term progression in some order. To prove the latter statement, identify the line with ${\mathbb{F}}_5$ and let $m$ be its omitted point. Choose any nonzero $d$, and take $a=m+d$. Then $a,a+d,a+2d,a+3d$ are precisely the four points other than $m$. Thus four-term-progression-free sets are exactly sets meeting every affine line in at most three points. This equivalence uses the field order five and would be false in this form over a general larger field.

Fix $a\in A$. Distinct lines through $a$ partition all other points of the space, and their number is $(5^n-1)/4$: nonzero direction vectors are grouped into their four nonzero scalar multiples. Each such line contains at most two further points of $A$. Hence \[ |A|-1\leq\frac{5^n-1}{2},\qquad r_4({\mathbb{F}}_5^n)\leq\frac{5^n+1}{2}. \] The proof is elementary and provides only a constant density saving. It is weaker than the qualitative and quantitative methods relevant to the research frontier; it is included as a completely checked baseline for the proposed iteration. For $n=1$ it gives three, which is exact. For $n=0$ the ambient space has one point and the formula also gives one.

An exponential lower construction and a restriction on any answer.
The Cartesian product $\{0,1,2\}^n$ has no four-term progression. If its difference vector is nonzero, some coordinate difference is nonzero, and the four values in that coordinate are distinct. They cannot all belong to a three-element set. Therefore \[ 3^n\leq r_4({\mathbb{F}}_5^n)\leq (5^n+1)/2. \] In particular any claimed exponent in $r_4({\mathbb{F}}_5^n)\leq C5^{(1-c)n}$ must satisfy $c\leq1-\log_5 3$. This follows by taking logarithms and letting $n$ tend to infinity; a fixed multiplicative constant disappears. The construction does not refute the existence of a smaller positive $c$.

More generally, if $B\subset{\mathbb{F}}_5^r$ and $C\subset{\mathbb{F}}_5^s$ are both progression-free, then $B\times C$ is progression-free. A nonzero difference has a nonzero projection in at least one block, where it would create a forbidden progression. Consequently the extremal sequence is supermultiplicative: \[ r_4({\mathbb{F}}_5^{r+s})\geq r_4({\mathbb{F}}_5^r)r_4({\mathbb{F}}_5^s). \] This is a lower-bound operation. Reversing this inequality is an unjustified step, and would turn a construction into the desired theorem without supplying any upper-bound argument.

The failed upper-bound iteration, precisely located.
Partition the coordinates into blocks of length $m$. Every fibre obtained by fixing the other coordinates is progression-free, so one obtains $|A|\leq r_4({\mathbb{F}}_5^m)5^{n-m}$. Applying the same observation to another block gives the same global inequality again. It does not multiply the density losses: after projecting away the first block, the resulting support can be the full smaller space and need not be progression-free. An explicit warning is the parabola $\{(t,t^2):t\in{\mathbb{F}}_5\}$. It contains no nonconstant three-term progression, since the second-coordinate midpoint equation forces $2d^2=0$, yet its projection onto the first coordinate is all of ${\mathbb{F}}_5$. Thus even a progression-free set can have a projection containing every possible progression. The forbidden configurations in different fibres must therefore be coordinated before repeated losses are legitimate.

This identifies a useful missing lemma rather than merely an unspecified need for a stronger estimate: one would need a dimension-independent block decomposition in which a fixed density deficit is forced on the conditional distributions at a positive proportion of stages. The line-incidence argument above gives no such statement. Its estimates count lines through one point, with dependencies shared across all stages.

Verification and remaining gap.
The line equivalence checks all omitted points and all nonzero directions, including progressions that wrap around the field. Degenerate difference zero is excluded throughout. The lower construction can be verified directly coordinate by coordinate, so no finite computation is being promoted to an asymptotic proof. The interval question remains untouched by these bounds: embedding a grid into integers introduces carry and ordering constraints and does not automatically transfer the four-term target to the five-term target. Both catalogue questions remain unresolved here. The concrete progress is the exact line reformulation, an explicit exponential obstruction to overly strong exponents, and a diagnosis of why naive fibre iteration cannot produce a power saving.

Sources

Go to contribution →