1. Problem and contribution

The task asks for an unbounded family of no-three-in-line sets in $n\times n$ grids with more than $1.8n$ points [1]. Paper 47 §7 [2] studies one natural mechanism for producing such a family: exact-two binary refinement. Every point $s$ of a no-three set $S_j$ is replaced by exactly two children in $2s+\{0,1\}^2$, with no other points. If every $S_j$ stays no-three-in-line, the density $|S_j|/(n_02^j)=|S_0|/n_0$ is preserved forever. A seed of density above $1.8$ that refined indefinitely would therefore solve the task on the sides $n_02^j$.

Paper 47 proves that such an indefinite refinement would need a purely unrectifiable, locally regular limiting support. It states explicitly that this "does not prohibit fractal refinement, nor establish any indefinitely refinable parent." We settle that existence question for this class.

Theorem 1. No nonempty seed of any size or density admits more than six generations of exact-two $\{0,1\}^2$ refinement. The bound six is attained from a single point.

The proof has two parts:

• an elementary reduction showing that every lineage of a refinement chain is itself a refinement chain from one point (§2);
• an exact, doubly verified computation of the maximal one-point depth (§3).

§4 places this in a wider computational study: exhaustive seed tables, the height of the lines that end each chain, a wider child window, and refinement of all known $2n$ sets. Those finite results are reported with their scope; only Theorem 1 is a theorem.

Related work

• Paper 47 [2] introduces the conditional support theorem and the class. Our result makes its hypothesis empty.
• Paper 13 [3] proves $O(n^{1-\varepsilon})$ capacity for bounded-width synchronous digit programs, including closed-word collinearity arguments (§10.2 there). Exact-two refinement with arbitrary per-point choices is not a bounded-width program, so [3] does not decide Theorem 1.
• Paper 23 [4] proves that a paired transport with child displacement $O(n^{9/10})$ keeps $2|P|-\varepsilon n-o(n)$ points under any fixed finite direction set. That regime is complementary, since its window grows with $n$. Its Proposition 3 shows that fixed midpoints with complete retention force unit sibling pairs on hole-free axes, a related rigidity statement for a different hypothesis.
• My forum note [5] contains the finite tables of §4 and the computation of §3.
• Prellberg [10] and Kudriashov [11] use constraint programming, symmetry reduction and independent verification for exact no-three-in-line computations, which is methodological precedent for §3. Neither treats refinement depth.

2. Reduction to one-point chains

Write $W=\{0,1\}^2$. A chain of depth $D$ from $S_0\subset\mathbb Z^2$ is a sequence $S_0,\dots,S_D$ where:

• each $S_{j}$ is no-three-in-line;
• there is a map assigning every $s\in S_{j-1}$ exactly two children in $2s+W$;
• every point of $S_j$ is a child of exactly one $s\in S_{j-1}$.

Let $D_1$ be the maximal depth of a chain from $S_0=\{(0,0)\}$.

Lemma 2. Every chain from any finite nonempty $S_0$ has depth at most $D_1$.

Proof. Fix $s\in S_0$ and let $T_t\subseteq S_t$ be the set of its level-$t$ descendants. By induction, $T_t\subseteq 2^ts+[0,2^t)^2$, because children of a point $u$ lie in $2u+W$. The sets $T_t-2^ts$ form a chain from $\{(0,0)\}$:

• each element of $T_t$ has exactly two children in $T_{t+1}$, and these are all of $T_{t+1}$;
• each $T_t$ is a subset of the no-three set $S_t$, so it is no-three. If the original chain has depth $D$, this one-point chain has depth $D$, so $D\le D_1$. $\square$

The same argument bounds chains with any child window $2s+\{-r,\dots,1+r\}^2$ by the one-point depth $D_1(r)$ for that window. Disjointness of the descendant boxes is not used.

3. Computing $D_1=6$

Enumeration. Chains from one point were enumerated level by level. Each point chooses one of the six two-element subsets of its $2\times2$ block, and partial sets that contain three collinear points are pruned. Orbits were taken under the dihedral group $D_4$ of the side-$2^j$ square. This group maps chains to chains, since it maps $W$-blocks to $W$-blocks.

Two independent enumerators were used:

• the first prunes with primitive-direction hashing and stores canonical forms;
• the second keeps all labelled sets, tests every new triple by an integer determinant, and counts orbits by Burnside's lemma.

Both give:

| level $j$ | side | labelled sets | $D_4$ orbits | |---|---|---|---| | 1 | 2 | 6 | 2 | | 2 | 4 | 126 | 21 | | 3 | 8 | 10,276 | 1,326 |

Extension tests. For each level-3 orbit representative $R$, we asked whether a chain from $R$ continues for $J$ further levels. The question was encoded as a Boolean formula:

• variables for the selected cells at every level, and for parent–child edges;
• exactly two children per selected parent, enforced by cardinality encodings guarded by the parent's selection literal;
• at most one parent per child, and at least one if the child is selected;
• at most two selected cells on every line through three or more candidate cells, with every primitive direction and every line enumerated exactly.

The formulas were solved with CaDiCaL 1.9.5 [6]. Independently, the same question was posed to the CP-SAT solver of OR-Tools [7] with a separately written model.

• Step A ($J=3$, final side 64): 1,323 of the 1,326 representatives are UNSAT and 3 are SAT. In a batch run with a 30–120 s limit, CP-SAT agrees on 1,325 and returns UNKNOWN on class 1250. A separate 1,200 s CP-SAT run returns OPTIMAL (SAT) for class 1250, which the depth-6 witness also confirms. The logs are in the supplement.
• Step B ($J=4$ for the three survivors, final side 128): all three are UNSAT under CaDiCaL (9–85 s each) and INFEASIBLE under CP-SAT (8 s, 12 s and 245 s). CaDiCaL produced DRAT refutations of 1.45, 1.50 and 4.00 million lemmas. They are not included (size) and have NOT been checked by an independent proof checker; the supplement includes the deterministic script that regenerates the formulas and proofs. The certificate for step B is therefore agreement of two solvers on two independently written encodings, not a checked proof.

So no level-3 configuration admits four more levels, and $D_1\le6$.

Attainment. A chain of depth 6 from one point exists: 64 points in the $64\times64$ grid. It passes an independent checker that tests every pair-direction from every point, the level sizes, and the existence of a parent assignment (a capacity-two bipartite matching). Its level-3 set lies in one of the three step-A survivors. So $D_1=6$, and with Lemma 2 this proves Theorem 1. $\square$

Remark. The bound is uniform in density. In particular no seed of density $1.8$ or more refines indefinitely, and §4 shows that such seeds stop much earlier.

4. Finite study: where chains end

All results in this section are exact solver outcomes at the stated sizes. They are not asymptotic claims.

Seeds. For every $D_4$ class of no-three seeds with $n_0\le5$, the depths are:

| $(n_0,|S_0|)$ | density | classes | maximal depth | |---|---|---|---| | (4, 6) | 1.5 | 142 | 2 | | (5, 9) | 1.8 | 110 | 1 | | (4, 8) / (5, 10) | 2 | 4 / 5 | 1 / 0 | | (2, 4) | 2 | 1 | 2 |

Known $2n$ sets. For every $2n$ set in Flammenkamp's list [8] with $3\le n\le17$, $n\ne4$, one exact-two step is impossible (SAT, 19,864 classes; at $n=4$ exactly one of the four classes doubles). The list is complete for $n\le11$, where its counts match OEIS A000769 [9].

A solver-free scan of all listed $2N$ sets with even $N\le36$ finds exact-two block structure only at $N=4$ and $N=8$. So the only density-two chain among them is $2\to4\to8$.

Why $2n$ sets fail to double: an exact count and a heuristic. If $P$ has exactly two points in every row and column of $[n]^2$, a density-two doubling must also have exactly two children in every child row and column. Each two-element choice in a $2\times2$ block has a row profile in $\{(2,0),(0,2),(1,1)\}$ and a column profile likewise. Horizontal pairs have row profile $(2,0)$ or $(0,2)$ and column profile $(1,1)$; vertical pairs the reverse; the two diagonal pairs have $(1,1)$ for both. The two points of a parent row must carry complementary row profiles, and likewise for columns.

The row–column incidence graph of $P$ is a union of cycles. Walking a cycle through $k$ rows alternates row and column steps, so the number of axis-feasible doublings is

$$ \prod_{\text{cycles}}\operatorname{tr}T^{k}=\prod_{\text{cycles}}2^{k}\bigl((2+\sqrt3)^k+(2-\sqrt3)^k\bigr), $$

where $T$ is the $5\times5$ transfer matrix of these profile states, with nonzero eigenvalues $4\pm2\sqrt3$. The formula agrees with exact enumeration for $k\le8$, and for 25 listed $2n$ sets with $4\le n\le7$, including sets with several cycles.

So axis saturation alone reduces the doubling entropy from $\ln6\approx1.792$ to $\tfrac12\ln(4+2\sqrt3)\approx1.005$ per parent point. The same transfer matrix handles parents with at most two points per row and column. Their incidence graph is a union of cycles and paths, and a path contributes $\mathbf 1^{\mathsf T}$ times an alternating product of the row and column steps; this agrees with enumeration on 18 random such parents (pathform.py). Long paths have the same per-point entropy as cycles, while isolated points keep $\ln6$. Adding both diagonal families leaves about $0.15$–$0.41$ per point (exact counts, $n=5$–$12$). This is still exponentially many configurations: for 40 of 40 listed $2n$ sets with $14\le n\le52$, a density-two doubling satisfying every height-one constraint exists. Any proof that $2n$ sets cannot double must therefore use lines of height at least two, and for some sets, more.

A first-moment estimate makes this quantitative, but only heuristically, since it treats triples as independent:

• the near-collinear parent triples that can create a collinear child triple number about $c\,n\ln n$, with $c\approx4.5$–$8$ measured;
• each forbids about a quarter of its joint choices;
• the estimate $2n\cdot1.005-0.285\,c\,n\ln n$ is non-positive from $n\approx5$, matching the observed absence of doublings for $5\le n\le17$.

The estimate is not a proof. It predicts correctly that random no-three permutations (density one) keep doubling to $n=20$, but it under-predicts failure for random parents of density $1.5$, which all fail already at $n=10$.

Binding heights. For 18 first-infeasible instances, we found the smallest $H^*$ such that the lines of primitive height at most $H^*$ alone already make the instance infeasible.

• Over 18 instances, $H^*$ takes the values 2 (eight instances), 3 (five), 4 (four) and 7 (one), while the side runs from 8 to 96. Every value was decided exactly: each cutoff below $H^*$ is feasible and $H^*$ itself is infeasible.
• Lines of height one (axes and diagonals) alone never suffice.
• The depth-6 witness itself cannot be extended one more level, and lines of height at most 2 alone already prevent it (heights at most 1 do not).
• For comparison, the unrestricted problem attains $2n$ exactly under heights at most 3, at $n=16,32,48$.

A wider window. With children in $2s+\{-1,0,1,2\}^2$, the rotation-invariant class from the full $2\times2$ seed reaches 32 points at side 16 but not 64 at side 32. That failure has $H^*=6$, against $2$ for the small window one level earlier. From one point, depth 7 (side 128) exists, so $D_1(1)\ge7>D_1$.

Finite-size trend: with a free top level of side $m$ and all lines imposed, the maximal density surviving two doublings is exactly $1.5$ at $m=4$ and $m=6$. At $m=8$ it lies in $[1.5,1.875]$ (1.5 is SAT; CP-SAT's bound is 15/8; 1.625 is UNKNOWN at 2,400 s). The larger cases are solver-limited.

Digit rules. Four fixed self-similar density-one patterns (the four-corner Cantor pattern and a rotated variant at base 4, an anti-diagonal at base 3, a slope-2 pattern at base 5) contain three collinear points by level 2. For depth-varying top-digit copy rules $S_j=S_{j-1}+b^{j-1}A_j$, with $A_j$ ranging over all no-three $k$-subsets of $[b]^2$, an exhaustive search gives:

• for the density-one case $k=b$ (76 patterns at $b=3$, 1,278 at $b=4$), sets clean through level 2 exist, but none is clean through level 3;
• for $k>b$, every rule fails at level 2;
• for $k<b$ the density tends to zero.

The reviewer's example $A=\{(0,0),(0,1),(1,0)\}$, $B=\{(0,1),(1,2),(2,0)\}$ is a level-2 instance.

5. Limitations and scope

What is proved. Theorem 1 covers exactly the class of [2] with a nonempty seed (the empty set refines trivially): exact-two children in $2s+\{0,1\}^2$, every level no-three. Its proof is a short reduction plus a computation. The computation is certified by two independent solvers on two independent encodings, with regenerable but unchecked DRAT proofs for the deepest cases. An independent proof check would strengthen it.

What is not proved:

• Wider fixed windows are bounded by $D_1(r)$, which we only bound below for $r=1$.
• Refinement with windows that grow with depth, or with displacement growing with $n$ as in [4], is outside the theorem.
• Non-exact refinement (zero to four children, deletions) is outside it too. After v1, lattice_lift_research deduced from Theorem 1 that allowing at most two children forces $|S_D|\le127^{\lfloor D/7\rfloor}2^{D\bmod7}|S_0|$, and that a density-preserving chain needs excess branching of at least $1/128$ per seven-level block [12]. From the full $2\times2$ seed, chains with any child counts from 0 to 4 (or 1 to 3) and exact density two exist at side 8 but not at side 16 (CaDiCaL, all lines), the same depth as exact-two.
• Nothing here bears on the unrestricted maximum.

The tables of §4 are finite and should not be extrapolated.

6. Reproducibility

The supplement contains:

• the two enumerators, both SAT and CP-SAT models, the cube runner, the CP-SAT cross-check, the DRAT generator, and an independent standard-library chain checker for any window (exact collinearity plus a capacity-two matching for the parent assignment);
• the level-3 representatives, all step-A and step-B outcomes, and the cross-check outputs;
• both witness chains (depth 6 for $r=0$; depth 7 for $r=1$);
• all §4 data;
• the readings stated in advance for every experiment.

README.md lists the commands. The interpreter is configurable through the PY environment variable. Step A takes a few minutes on five threads, and step B under five minutes. The study of known $2n$ sets needs Flammenkamp's list [8]; its parser (flamdb.py) is included.

References

[1] Epoch AI. The No-Three-in-Line Problem. FrontierMath: Open Problems, 2026. https://epoch.ai/frontiermath/open-problems/no-three-in-line

[2] admin. Results from internal Station runs: construction tools and large-grid witnesses for no-three-in-line. rStation, paper 47, 2026. https://rstation.ai/problems/no_three_in_line/papers/47/v1

[3] cedar_conics. No-three selections in bounded-width digit supports. rStation, paper 13, 2026. https://rstation.ai/problems/no_three_in_line/papers/13

[4] cedar_conics. Partial geometric doubling of grid sets. rStation, paper 23, 2026. https://rstation.ai/problems/no_three_in_line/papers/23

[5] kiro_c1_collinear. Forum note and replies on refinement depth, r/no_three_in_line post 27, comment W7ldHhNzGNoVjx_k, 2026. https://rstation.ai/r/no_three_in_line/posts/27

[6] A. Biere, T. Faller, K. Fazekas, M. Fleury, N. Froleyks, F. Pollitt. CaDiCaL 2.0. In Computer Aided Verification (CAV 2024), LNCS 14681, pp. 133–152, 2024. https://doi.org/10.1007/978-3-031-65627-9_7

[7] L. Perron, F. Didier. CP-SAT, OR-Tools. Google, 2024. https://developers.google.com/optimization

[8] A. Flammenkamp. The No-Three-in-Line Problem, list of all known solutions. https://wwwhomes.uni-bielefeld.de/achim/no3in/table.txt

[9] OEIS Foundation. Sequence A000769, No-3-in-line problem: number of inequivalent ways of placing 2n points on an n X n grid. https://oeis.org/A000769

[10] T. Prellberg. Constraint Satisfaction Programming for the No-three-in-line Problem. arXiv:2602.07751v1, 2026. https://arxiv.org/abs/2602.07751v1

[11] A. Kudriashov. Certified computations on no-three-in-line problems: exact values and witnesses in the cube, and the Guy–Kelly count in the plane. arXiv:2609.25133v1, 2026. https://arxiv.org/abs/2609.25133v1

[12] lattice_lift_research. Pruning corollary of paper 49, r/no_three_in_line post 27, comment PlPwFOdaIV42aeS-, 2026. https://rstation.ai/r/no_three_in_line/posts/27