Progressions in F_3^n with Boolean Common Differences

Boolean-Step Progressions over the Three-Element Field

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.

Identify $\{0,1\}^n$ with the corresponding subset of ${\mathbb{F}}_3^n$. A permitted progression is $(x,x+d,x+2d)$ with $d\in\{0,1\}^n\setminus\{0\}$. Its terms are distinct. Let $b(n)$ be the largest cardinality of a set avoiding all such progressions. The requested density threshold is equivalently the extremal ratio $b(n)/3^n$. [S1] [S2]

Statement recorded in the supplied source.

Suppose that $A \subset \mathbb{F}_3^n$ is a set of density $\alpha$. Under what conditions on $\alpha$ is $A$ guaranteed to contain a 3-term progression with nonzero common difference in $\{0, 1\}^n$? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Determine the true threshold, including whether a bound of the form $1-c$^n suffices. [S1]

Short English statement

How dense must a subset of the three-element-field cube be before it contains a three-term progression whose step has only zero and one coordinates?

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 target and literature check.

We count progressions $x,x+d,x+2d$ in ${\mathbb{F}}_3^n$ with $d\in\{0,1\}^n\setminus\{0\}$. Because the characteristic is three, every such progression has three distinct points. The primary problem list distinguishes this restricted-direction problem from ordinary cap sets and records quantitative partial results. No unrestricted cap-set upper bound is used here: forbidding fewer directions permits larger sets. Our attack is to optimise a small block construction and determine exactly what tensorisation does to it.

An exact two-coordinate block.

Let \[ B=\{(a,b)\in{\mathbb{F}}_3^2:a+b\ne0\}. \] There are six points in $B$. For any nonzero $d\in\{0,1\}^2$, the sum of its coordinates is either one or two modulo three, hence nonzero. Along $x,x+d,x+2d$, the coordinate sum consequently takes all three values of ${\mathbb{F}}_3$. One point has sum zero and lies outside $B$. Thus $B$ avoids all allowed progressions.

This is best possible in dimension two. Partition the nine-point space into three horizontal lines. The allowed direction $(1,0)$ forces each horizontal line to contain at most two selected points, so every admissible set has at most six points. The construction meets the bound and is therefore an exact solution of this finite instance. The companion script independently enumerates all $2^9$ subsets and all allowed lines and obtains maximum six.

Tensor powers give a stronger lower obstruction.

Take $n=2m$ and group the coordinates into $m$ pairs. The set $B^m$ has $6^m$ elements. A nonzero allowed direction has a nonzero restriction in some pair. Projection to that pair would give a forbidden progression in $B$, so the product is admissible. If $n=2m+1$, append the one-coordinate set $\{0,1\}$, obtaining $2\cdot6^m$ points. Consequently the extremal density $\delta_n$ satisfies \[ \delta_{2m}\geq(2/3)^m,\qquad \delta_{2m+1}\geq(2/3)^{m+1}. \] The exponential base for even dimensions is $\sqrt{2/3}$. In particular a universal upper bound of the form $\delta_n\leq C\rho^n$ cannot hold with $\rho<\sqrt{2/3}$: along even $n$, the quotient of the construction's density by $\rho^n$ diverges. This restricts the possible strength of an affirmative exponential-threshold theorem without disproving that theorem for larger bases below one.

The simpler binary cube $\{0,1\}^n$ has only $2^n$ points. The two-coordinate construction is larger because it does not impose a separate two-value restriction on every coordinate. Its exclusion is coupled within each pair, and that coupling survives the product operation.

A plausible larger-block extension fails.

One might replace each pair by a block of arbitrary length $r$ and impose only $x_1+\cdots+x_r\ne0$. This does not work once $r\geq3$. The direction with ones in its first three coordinates and zeros elsewhere is allowed and has coordinate sum zero. A starting point with nonzero total sum keeps that sum unchanged along the whole progression, so all three points remain in the proposed set. For example, in dimension three take $x=(1,0,0)$ and $d=(1,1,1)$; the points $(1,0,0),(2,1,1),(0,2,2)$ all have total sum one modulo three. This is an explicit failure of the single-linear-condition generalisation.

More generally, a linear functional $L(x)=\sum c_ix_i$ can support this method only if $L(d)\ne0$ for every nonzero allowed $d$. If some coefficient is zero, a coordinate vector violates this. If there are at least three nonzero coefficients in ${\mathbb{F}}_3$, then either both signs occur, giving a zero sum from two coordinates, or three coefficients agree, giving a zero sum from three. Thus such a functional can involve at most two coordinates, and in the two-coordinate case their coefficients must agree. This proves that the successful pair block is already maximal within this particular single-functional scheme.

Verification and remaining gap.

Direction zero is excluded in each step, and all arithmetic in the explicit bad block is checked modulo three. The tensor proof does not assume the reverse direction $-d$ is itself allowed. The exact small extremum and the classification of the linear-functional construction are the established results of this attempt. The unresolved problem is an upper bound decaying exponentially in $n$, or a construction with subexponential density decay. The calculation shows precisely why enlarging the block while retaining only one linear condition cannot provide the latter.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 106 (GREEN-017), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Amey Bhangale, Subhash Khot, and Dor Minzer, Effective Bounds for Restricted 3-Arithmetic Progressions in F_p^n, arXiv:2308.06600; Discrete Analysis 2024:16. https://arxiv.org/abs/2308.06600. Bibliographic information from the supplied record.

• S3 Amey Bhangale, Subhash Khot, Yang P. Liu, and Dor Minzer, On Approximability of Satisfiable k-CSPs: VI, arXiv:2411.15133 (2024; FOCS 2025 version titled On inverse theorems and combinatorial lines). https://arxiv.org/abs/2411.15133. Bibliographic information from the supplied record.

• S4 Ben Green, 100 Open Problems, Problem 17 and 2023/2025 updates, . https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf. The author-hosted document was inspected on 27 September 2026; the archive’s local code is not a problem-number locator in this paper.