# Local repairs and reconfiguration barriers in no-three-in-line sets

**Athanor lab (Aleksei Kudriashov with AI research agents)**

**Contributions.** Aleksei Kudriashov initiated and directed the research
programme. The public submission account is athanor_lab. Astra (gpt-6-astra)
developed the repair formulation and prepared the mathematical exposition.
Guide (Claude Code) coordinated the research records and integrated sources.
Four independent research-core roles, each using gpt-6.1-sol, are credited:
the \(G_6\) enumerator; the representation-note outside reader; the
matching/carrier auditor and \(G_7,G_8\) certificate searcher; and the final
external reader, which independently replayed \(n\le6\) and audited proofs,
literature, and attribution. These named AI contributions do not replace the
mathematical evidence and certificates described below.

## 1. Introduction

The no-three-in-line problem is usually posed as an extremal question: how
large can a subset of a carrier be if it contains no three collinear points?
Here the object is the landscape below a maximum.  A safe set can be maximal
without being maximum.  How much must it shrink before it can grow into a
maximum configuration?

This question has a local and a global part.  At a specified empty site,
selected pairs on lines through that site record exactly how many deletions
make the insertion possible.  But that insertion may enter a component that
cannot reach any maximum at the same cardinality floor.  The first
full-square separation of these two notions among the boards exhaustively
enumerated here occurs in the complete \(6\times6\) census: some 11-point
maximal sets have a one-deletion insertion, yet
every path to a 12-point maximum falls to nine points.

The paper develops the language needed to state that phenomenon without
overclaiming it.

1. Section 3 gives the matching and vertex-cover repair calculus.
2. Sections 4–5 turn a path-floor question into a threshold-connectivity
   question and give a compact matching certificate for a one-extra-loss
   barrier.
3. Sections 6–7 record the complete \(G_6\) census and its four exceptional
   component types.
4. Sections 8–9 separate an unbounded restricted-carrier theorem from the
   still open complete-square problem, with certified exclusions and
   specified-layer path bounds on \(G_7,G_8\).

The local matching observation and the add/remove versus swap translation are
elementary or standard.  The prospective contribution is the exact
Euclidean-grid barrier classification, with reproducible certificates, not a
claim of a new general reconfiguration formalism.  In particular, the
six-state C4 component was publicly exhibited earlier by
u/cedar_conics [10].  Section 7 identifies its representative under the
reflection \((x,y)\mapsto(5-x,y)\); the contribution here is the exhaustive
classification of all 124 labelled strict examples into four component
types, together with the accompanying finite certificates.

## 2. Definitions and move models

Let \(X\subset\mathbb R^2\) be finite.  A subset \(S\subseteq X\) is
**safe** if no three distinct points of \(S\) are collinear.  Write
\(\mathcal I(X)\) for the hereditary family of safe sets and

\[
  \alpha(X)=\max\{|S|:S\in\mathcal I(X)\}.
\]

A safe set is **maximal** if it has no safe one-point extension, and
**maximum** if it has size \(\alpha(X)\).  The main carrier is the ordinary
integer square

\[
  G_n=\{0,\ldots,n-1\}^2,
\]

with all Euclidean slopes allowed.  A later construction uses a finite
restricted carrier \(X\subset\mathbb Z^2\).  Such a carrier remains
restricted even if it is embedded in a larger square.

For safe \(S\) and \(x\in X\setminus S\), define the **blocker matching**

\[
 M_x(S)=\bigl\{\{p,q\}\subseteq S:p,q,x\text{ are collinear}\bigr\},
 \qquad b_S(x)=|M_x(S)|.
 \tag{2.1}
\]

Whenever \(X\setminus S\ne\varnothing\), define

\[
  \beta(S)=\min_{x\in X\setminus S}b_S(x).
  \tag{2.2}
\]

We use comparisons involving \(\beta\) only for submaximum sets.  A maximum
can have exterior points and therefore can have a defined \(\beta\), but it
has path deficit zero and is not a repair-barrier candidate.

For a submaximum safe \(k\)-set, its **direct improvement depth** is

\[
 d(S)=\min_{\substack{T\in\mathcal I(X)\\ |T|=k+1}}|S\setminus T|.
 \tag{2.3}
\]

For every safe \(S\), its **escape floor** is

\[
 F(S)=\max_{\gamma:S\leadsto Q,\ |Q|=\alpha(X)}
               \ \min_{U\in\gamma}|U|,
 \tag{2.4}
\]

where \(\gamma\) uses one insertion or deletion per step and remains safe.
The **path deficit** is

\[
  \delta(S)=|S|-F(S).
  \tag{2.5}
\]

Thus a maximum has \(\delta(S)=0\).  An atomic neutral swap abbreviates a deletion followed by an insertion.  It
therefore visits the next lower cardinality level and is not a zero-cost
operation in the definition of \(F\).

## 3. Exact local repair calculus

### 3.1 One prescribed insertion

**Proposition 3.1.**  For safe \(S\) and \(x\notin S\), \(M_x(S)\) is a
matching.  The point \(x\) is insertable exactly when \(b_S(x)=0\), and the
minimum number of selected points that must be deleted before inserting this
specified \(x\) is \(b_S(x)\).

**Proof.**  Two edges of \(M_x(S)\) cannot share an endpoint: their three
selected endpoints would lie on the same line through \(x\), contradicting
safety.  Thus the edges are disjoint.  Inserting \(x\) creates exactly the
triples indexed by these edges.  Every deletion set has to meet each edge, and
one endpoint per edge suffices. \(\square\)

Consequently, \(S\) is maximal exactly when every empty site has positive
blocker number.  Two useful audit identities are

\[
 \sum_{x\in X\setminus S}b_S(x)
  =\sum_{\{p,q\}\subseteq S}(|X\cap\ell(p,q)|-2),
 \tag{3.1}
\]

and, if \(E(U)\) counts collinear triples in \(U\),

\[
 E(S\cup\{x\})-E(S)=b_S(x).
 \tag{3.2}
\]

The first double-counts a selected pair and an empty third carrier point on
its full line.  These identities do not imply that different empty sites act
independently.

### 3.2 Several prescribed insertions

Let \(A\subseteq X\setminus S\) itself be safe.  Define

\[
 D_A=\{s\in S:s\text{ is collinear with two distinct points of }A\}
\]

and

\[
 G_A=\bigcup_{a\in A}M_a(S)\big|_{S\setminus D_A}.
 \tag{3.3}
\]

The restriction in (3.3) deletes every vertex of \(D_A\), and
\(\tau\) denotes the minimum vertex-cover number.

**Proposition 3.2.**  The minimum number of points of \(S\) that must be
deleted before inserting all points of \(A\) is

\[
 r_S(A)=|D_A|+\tau(G_A).
 \tag{3.4}
\]

**Proof.**  A triple comprising two new points and one old point forces the
old point into \(D_A\).  Once these forced deletions are made, every remaining
mixed triple consists of one new point and one edge of \(G_A\).  Thus the
additional deleted old points must form a vertex cover.  The conditions are
sufficient because both \(S\) and \(A\) are safe. \(\square\)

For two inserted points, \(G_A\) is a union of two matchings, so each
component is a path or an even cycle.  This makes \(\tau(G_A)\) immediate.
For three inserted points, odd cycles can occur.  For example, with

\[
 S=\{(0,0),(2,0),(0,2)\},\qquad
 A=\{(1,0),(1,1),(0,1)\},
\]

the graph \(G_A\) is a triangle and has vertex-cover number two.

### 3.3 Prior-work boundary

Maximal general-position subsets of grids are studied as independent
geometric dominating sets by Aichholzer, Eppstein, and Hainzl [1].  Their
historical discussion credits Adena, Holton and Kelly (1974), and Martin
Gardner (1976), for the minimum-maximal problem. Nagy, Nagy and Woodroofe
use the term “saturated” for this maximality condition [7].  Wilhelmina's
public blocker/exchange computation [11] and Kudriashov's certified work on
nearby blocker and rigidity questions [12] are related local antecedents,
but do not establish the planar path-floor statements here. Multiple
saturation by secants in finite projective planes is another analogy [8],
not a transfer to integer squares.

Propositions 3.1–3.2 are elementary. This manuscript makes no novelty claim
for these identities, for vertex-cover language, or for local search.

## 4. Threshold components and local gates

For \(h\ge0\), let \(H_h\) be the add/delete graph induced by safe sets of
size at least \(h\).  Let \(\Sigma_h\) be the union of components of \(H_h\)
that meet a maximum set.  By definition,

\[
  F(S)=\max\{h:S\in\Sigma_h\}.
  \tag{4.1}
\]

The next statement says precisely what is absent from a scalar local repair
cost.

**Theorem 4.1 (gate criterion).**
Let \(S\) be a maximal submaximum
\(k\)-set and put \(b=\beta(S)\).  For every empty \(x\) with
\(b_S(x)=b\), let \(C\) range over the minimum vertex covers of \(M_x(S)\),
and put

\[
  P_{x,C}=S\setminus C,\qquad U_{x,C}=P_{x,C}\cup\{x\}.
\]

Then

\[
 \delta(S)=b
 \quad\Longleftrightarrow\quad
 P_{x,C}\in\Sigma_{k-b}\text{ for some }x,C.
 \tag{4.2}
\]

**Proof.**  Suppose a path from \(S\) to a maximum stays at size at least
\(k-b\), and consider its first inserted point \(x\notin S\).  Immediately
before that move the path is at a subset \(R\subseteq S\).  The deletion set
\(S\setminus R\) meets every edge of \(M_x(S)\), so it has at least
\(b_S(x)\) points.  The threshold bound gives at most \(b\).  Both
inequalities are equalities: \(b_S(x)=b\), \(R=P_{x,C}\), and \(C\) is a
minimum cover.  The converse follows by deleting \(C\), inserting \(x\), and
following a path within \(\Sigma_{k-b}\). \(\square\)

Hence \(\delta(S)\ge\beta(S)\) for every submaximum maximal state.  Equality
fails exactly when every minimum local gate lies in a maximum-free threshold
component.  This is an exact location of the missing global information, not
an efficient replacement for a component calculation: all gates remain
connected through \(S\) at the same threshold.

## 5. Swap layers and a matching certificate for a second loss

Let \(J_h\) be the graph on safe \(h\)-sets in which two vertices are
adjacent if they have a common safe \((h-1)\)-subset.  Thus a \(J_h\)-edge is
an atomic neutral swap.  Every pair of \(h\)-subsets of a fixed safe set of
size at least \(h\) lie in one \(J_h\)-component; call it \(j_h(U)\).

**Theorem 5.1 (threshold/TJ lemma).**  Let \(h\ge1\).  If \(S,Q\) are safe
and have size at least \(h\), then

\[
 S\text{ and }Q\text{ are connected in }H_{h-1}
 \quad\Longleftrightarrow\quad
 j_h(S)=j_h(Q).
 \tag{5.1}
\]

**Proof.**  A path at threshold \(h-1\) either moves above the \(h\)-layer,
which preserves the component of its \(h\)-subsets, or passes through a
configuration \(A\supset B\subset A'\) with \(|B|=h-1\), which is one
\(J_h\)-edge.  Conversely, shrink the endpoints to \(h\)-subsets, implement
each \(J_h\)-edge as delete then add through its common \((h-1)\)-subset, and
regrow. \(\square\)

This is the hereditary-family form of the familiar token
addition/removal–token jumping relation. For graph independent sets, see
Kamiński, Medvedev, and Milanič [2], and the threshold/buffer context of
de Berg, Jansen and Mukherjee [3].
The proof is included because no-three-in-line safety is independence in a
3-uniform hypergraph.

Define the maximum-target label set

\[
 T_h=\{R:|R|=h,\ R\subseteq Q\text{ for some maximum }Q\}.
 \tag{5.2}
\]

For \(1\le d\le |S|\), Theorem 5.1 gives

\[
  \delta(S)\le d
  \quad\Longleftrightarrow\quad
  j_{|S|-d+1}(S)\cap T_{|S|-d+1}\ne\varnothing.
  \tag{5.3}
\]

This is a connectivity characterization, not a claimed fast algorithm.

We now record a local closure certificate for the case \(\beta=1\).  For
safe \(U\) and any carrier point \(y\), selected or empty, let

\[
 L_y(U)=\{\{a,b\}\subseteq U\setminus\{y\}:a,b,y
              \text{ are collinear}\}.
 \tag{5.4}
\]

Suppose \(x\notin U\), \(L_x(U)=\{\{p,q\}\}\),
\(r\in\{p,q\}\), and \(U'=U-r+x\).  For \(y\notin U'\),

\[
 L_y(U')=L_y(U)|_{U\setminus\{r\}}
            \cup E_y(x;U\setminus\{r\}),
 \tag{5.5}
\]

where

\[
 E_y(x;W)=
 \begin{cases}
 \{\{x,s\}\},&\text{if a unique }s\in W\text{ is collinear with }x,y,\\
 \varnothing,&\text{otherwise.}
 \end{cases}
 \tag{5.6}
\]

There is at most one such \(s\), and this new edge is disjoint from all
retained edges, because \(U'\) is safe.  Equations (5.5)–(5.6) are therefore
an exact labelled-matching update.  Blocker numbers alone omit the
old–new–new incidence that decides whether the new edge is created.

**Theorem 5.2 (matching-closure certificate).** Let \(S\) be a
submaximum maximal safe \(k\)-set with \(\beta(S)=1\).  Let \(C\) be its
component in the labelled neutral-swap graph generated by singleton blocker
matchings, and suppose every \(U\in C\) is maximal.  Define

\[
 D(C)=\{P:|P|=k-1,\ P\subset U\text{ for some }U\in C\}.
\]

Then the component of \(S\) in \(H_{k-1}\) is exactly

\[
 C\cup D(C).
 \tag{5.7}
\]

In particular, \(\delta(S)\ge2\).

**Proof.**  No \(U\in C\) has a size-\(k+1\) coface.  Take
\(P=U\setminus\{r\}\in D(C)\), and let \(U'=P\cup\{x\}\) be another safe
\(k\)-coface.  Maximality of \(U\) makes \(M_x(U)\) nonempty.  Safety of
\(U'\) forces every edge of this matching to contain \(r\).  As it is a
matching, it has one edge, so \(U'\) is a declared singleton-blocker swap and
lies in \(C\).  Thus every threshold path alternates only between
\(C\) and \(D(C)\). Conversely, \(C\) is connected by its definition,
each neutral edge is realized through a member of \(D(C)\), and each
member of \(D(C)\) is adjacent to a member of \(C\). Thus their union
is connected and is the entire threshold component. \(\square\)

Connectedness matters: for an arbitrary swap-closed family of maximal
\(k\)-sets, the same boundary argument gives a closed **union** of threshold
components. It gives one component only if the family is connected. The
theorem explicitly takes \(C\) to be a component.

## 6. Exact \(G_6\) census

This section records **exactly checked finite computation**.  The results are
attributed to the complete-grid enumeration core and its independent verifier.  They
are reproducible mathematical evidence, not proof-assistant formalizations.

| \(n\) | safe subsets | maximal subsets | \(\alpha(G_n)\) | maximum subsets | maximal \(\delta=1\) | maximal \(\delta=2\) |
|---:|---:|---:|---:|---:|---:|---:|
| 1 | 2 | 1 | 1 | 1 | 0 | 0 |
| 2 | 16 | 1 | 4 | 1 | 0 | 0 |
| 3 | 230 | 23 | 6 | 2 | 21 | 0 |
| 4 | 4,812 | 347 | 8 | 11 | 336 | 0 |
| 5 | 109,536 | 5,646 | 10 | 32 | 5,586 | 28 |
| 6 | 3,599,697 | 116,411 | 12 | 50 | 115,876 | 485 |

The complete \(n\le5\) records have \(\beta=\delta\) for every submaximum
maximal state.  In \(G_6\), 124 labelled maximal 11-sets, in 16 dihedral
state orbits, satisfy

\[
  \beta=1,\qquad \delta=2.
 \tag{6.1}
\]

They occupy 28 labelled nontrivial \(J_{11}\)-components in four geometric
component orbits.  The other 361 maximal \(G_6\) states with \(\delta=2\)
have \(\beta=2\) and are neutral-swap isolated: one has size eight, four have
size nine, 28 size ten, and 328 size eleven.

The direct-depth distribution among submaximum maximal \(G_6\) states is:

| \(d\) | labelled states |
|---:|---:|
| 1 | 104,050 |
| 2 | 9,173 |
| 3 | 2,014 |
| 4 | 1,072 |
| 5 | 52 |

Forty-eight of the 52 depth-five states have \(\delta=1\).  This demonstrates
that direct replacement difficulty and path-floor difficulty are distinct.

The census also finds \(\delta\le2\) for every maximal \(G_6\) state.  The
underlying layer record is: \(J_h\) is connected for \(h\le7\); at
\(h=8,9,10\), there are respectively \(1,4,28\) maximum-free components, all
singleton maximal states; and every nonmaximal 11-set has a 12-point coface.
Thus every nonmaximal state has deficit at most one.  The following general
identity explains the asserted maximal-state bound.

**Lemma 6.2 (floor identity).**
For safe \(U\subseteq S\),

\[
 F(U)=\min\{|U|,F(S)\},\qquad
 \delta(U)=\max\{\delta(S)-(|S|-|U|),0\}.
 \tag{6.2}
\]

**Proof.**  Grow \(U\) to \(S\) within \(S\), then use an optimal path from
\(S\), for one inequality.  In the other direction, delete from \(S\) to
\(U\), then use an optimal path from \(U\); also \(F(U)\le|U|\). \(\square\)

It follows on any finite carrier that the assertion “every maximal state has
\(\delta\le2\)” is equivalent to “every nonmaximal state has
\(\delta\le1\).”  The equivalence is proved; its \(G_6\) hypothesis is a
finite checked fact, not an all-\(n\) theorem.

## 7. The four second-barrier motifs in \(G_6\)

Coordinates are zero based.  In each row, the listed core is common to every
state in a representative neutral component.  The residual description,
component count, and full threshold boundary are exactly checked in the
archived complete-grid certificate.  The visible local geometry does not, by itself,
exclude an escape through an unlisted grid site; that exclusion comes from
the complete labelled-matching boundary check.

| type | common core | variable sites | residual state description | components / states | \(H_{10}\) size |
|:--|:--|:--|:--|--:|--:|
| C1 | \((0,0),(0,4),(1,2),(2,1),(2,2),(3,5),(4,1),(4,3),(5,0)\) | \((1,5),(3,4),(5,3)\) | choose any two collinear variables | 8 / 24 | 33 |
| C2 | \((0,2),(0,5),(1,2),(2,0),(2,1),(3,4),(4,3),(4,4),(5,0)\) | \((1,5),(3,3),(5,1)\) | choose any two collinear variables | 4 / 12 | 33 |
| C3 | \((0,2),(1,4),(2,5),(3,3),(4,3),(4,5),(5,1)\) | \((0,4),(2,2),(3,1);(1,0),(2,0),(5,0)\) | one vacancy per triple, with one cross-pair forbidden | 8 / 40 | 54 |
| C4 | \((0,0),(0,4),(1,5),(2,1),(3,5),(4,0),(4,1)\) | \((1,2),(2,3),(3,3),(5,2),(5,3),(5,4)\) | choose four; vacancies hit all three lines | 8 / 48 | 64 |

In C1 and C2, the three variable points are collinear.  The missing variable
has the other two as its singleton blocker edge.  A neutral move therefore
rotates the vacancy around a triangle of maximal sets.

For C3, the variable triples are

\[
 L_1=\{(0,4),(2,2),(3,1)\},\qquad
 L_2=\{(1,0),(2,0),(5,0)\}.
\]

The core point \((2,5)\) forbids the cross-pair
\(\{(2,2),(2,0)\}\).  Of the nine nominal vacancy pairs, five remain.  Their
swap graph is two triangles sharing one vertex.

For C4, set

\[
 A=(1,2),\ B=(2,3),\ C=(3,3),\ D=(5,2),\ E=(5,3),\ F=(5,4).
\]

The collinear variable triples are \(\{B,C,E\}\), \(\{A,C,F\}\), and
\(\{D,E,F\}\).  A four-variable selection is safe exactly when its two
vacancies meet all three triples.  The six states form a 3-sun: a central
triangle with one further vertex attached to each edge.

This C4 component has a public antecedent: u/cedar_conics posted its
six-state family on 6 October 2026 [10]. The reflection
\((x,y)\mapsto(5-x,y)\) identifies that family exactly with the C4
representative above. The public example has 58 one-deletion states and a
closed 64-state component at height ten; every top state has \(\beta=1\)
and \(\delta=2\). The complete four-type classification in this section is
a separate finite result.

Every listed 11-point component consists of maximal states and has a closed
one-deletion layer.  Theorem 5.2 therefore supplies \(\delta\ge2\); saved
paths to a 12-point state at floor nine give equality.

A compact C1 witness is its core together with \((1,5)\) and \((3,4)\).  Its
three 11-point states and thirty 10-point deletion states form a closed
33-state component of \(H_{10}\).  It certifies

\[
  \beta=1<2=\delta.
\]

The classification is exactly checked finite computation. A determinant-based
reconstruction independently recovered the exchanges and one-deletion
boundaries, including the 28 labelled components and the threshold-component
sizes 33, 33, 54 and 64. A separate fresh enumeration recovered the complete
\(G_6\) census and its exhaustiveness claim; both receipts are in the
supplement.

## 8. Arbitrarily high barriers on restricted carriers

The next theorem is intentionally not a full-square result.

**Theorem 8.1 (restricted carriers).** For every
\(m\ge1\), there is a finite carrier \(X_m\subset\mathbb Z^2\) and an
inclusion-maximal submaximum safe set \(S_m\) satisfying

\[
 \beta_{X_m}(S_m)=\delta_{X_m}(S_m)=m.
 \tag{8.1}
\]

**Proof.** The rational realization used below is the edge-blocker
construction of Froese, Kanj, Nichterlein and Niedermeier [5, Proposition
1], applied to \(K_{m,m+1}\). Their construction credits the underlying
point-visibility transformation to Ghosh and Roy [6]. We include the
specialized argument because the subsequent barrier calculation uses its
exact incidence pattern. Choose rational points

\[
 B=\{b_1,\ldots,b_m\},\qquad W=\{w_1,\ldots,w_{m+1}\}
\]

in general position, fixing all of \(B\cup W\) before any anchor.
For each pair \((i,j)\), choose a rational anchor
\(a_{ij}\) on the line \(b_iw_j\), avoiding all existing points and the finitely many intersections
that would create a collinear triple other than the prescribed one.  This
finite-avoidance construction works because every rational line has
infinitely many rational points. Distinct prescribed \(B\)–\(W\) lines
are distinct by general position. Every future prescribed line already
joins an existing base pair, so each earlier anchor avoids it unless it
is that anchor's own prescribed line. Hence the designated pair is the
only old pair on the line chosen for a new anchor. It produces

\[
 X=B\cup W\cup A,\qquad
 A=\{a_{ij}:1\le i\le m,\ 1\le j\le m+1\},
\]

whose only collinear triples are

\[
 \{b_i,w_j,a_{ij}\}.
 \tag{8.2}
\]

Common rational scaling and translation put \(X\) in \(\mathbb Z^2\).

Let \(S=A\cup B\), \(Q=A\cup W\), and \(E=|A|=m(m+1)\).  At each absent
\(w_j\), the \(m\) disjoint pairs \(\{b_i,a_{ij}\}\) are its blockers.  Thus
\(S\) is maximal and \(\beta(S)=m\).

To show that \(Q\) is the unique maximum, let \(T\) be safe, and put
\(r=|T\cap B|\), \(s=|T\cap W|\).  Every selected pair \(b_i,w_j\) excludes
the distinct anchor \(a_{ij}\), giving

\[
 |T|\le E+r+s-rs.
 \tag{8.3}
\]

If \(r,s>0\), the right side is at most \(E+1\).  If \(r=0\), it is at
most \(E+m+1\), with equality only when \(T=Q\); if \(s=0\), it is at most
\(E+m\).  So \(Q\) is the unique maximum.

Before the first \(w_j\) can be inserted on a path from \(S\) to \(Q\), one
endpoint of every pair \(\{b_i,a_{ij}\}\) must be deleted.  The path reaches
size at most \(E\).  Deleting all \(b_i\) and then inserting all \(w_j\)
attains that floor.  Hence \(\delta(S)=m\). \(\square\)

For \(m\ge2\), adjoin an independent collinear triple \(\{u,v,w\}\), with no
mixed collinear triples, and start from \(S'=S\cup\{u,v\}\).  The missing
\(w\) has one blocker pair while every \(w_j\) retains \(m\) blockers.  Thus
\(\beta(S')=1\).  The neutral component on the added line is a triangle.
Every maximum is \(Q\) plus two points of this line; projecting a path onto
the original carrier forces a projected state of size at most \(E\).
At most two points can remain on the added line, so the full path has a
state of size at most \(E+2\).  Keeping the two added-line points while
using the original deletion/insertion path attains this floor.  Thus

\[
  \delta(S')=m.
  \tag{8.4}
\]

So a three-state closed neutral component, by itself, does not bound how far
below it eventual escape occurs. Exact exhaustive checks of supplied
19-site and 22-site carriers give deficit three, with 164,305 and 1,150,135
safe subsets respectively; these finite checks supplement the all-\(m\)
proof.

## 9. The full-square transfer gap

### 9.1 A conditional transfer theorem

Embedding the carrier of Theorem 8.1 in a large \(G_N\) does not preserve its
proof.  The extra lattice sites need not be blocked, so the old start need not
be maximal.  Greedily extending it can create low-cost gates and threshold
paths around the intended lock.  Square-grid maxima need not resemble \(Q\),
and the first point inserted on an escape path need not be one of the
\(w_j\).  Thus induced-subcarrier reasoning is invalid.

There is, however, a precise sufficient condition for transfer.  It tests
the whole component above a proposed cardinality floor, rather than only
the start.

**Proposition 9.1.**  Let
\(X\subseteq G_n\), let \(S\subseteq X\) be safe, fix
\(0\le h\le |S|\), and let \(C\) be its
component in \(H_h(X)\).  Suppose

\[
 M_z(U)\ne\varnothing
 \quad\text{for every }U\in C\text{ and }z\in G_n\setminus X.
 \tag{9.1}
\]

Then \(C\) is also the entire component of \(S\) in \(H_h(G_n)\).
If \(|U|\le |S|=k\) for all \(U\in C\) and a safe \((k+1)\)-set exists
in \(G_n\), then

\[
 \delta_{G_n}(S)\ge k-h+1.
 \tag{9.2}
\]

**Proof.**  An internal move stays in \(C\) by its definition.  A first
insertion outside \(X\) is forbidden by (9.1).  Thus no threshold path
leaves \(C\), whereas all its original paths remain available.  Every
maximum of \(G_n\) is larger than every state of \(C\), proving (9.2).
\(\square\)

For the carrier in Theorem 8.1, the component of \(S=A\cup B\) at height
\(E+1\) is exactly

\[
 \{S\setminus D:D\subseteq S,\ |D|\le m-1\}.
 \tag{9.3}
\]

Indeed, no \(w_j\) can be the first inserted new point until at least
\(m\) deletions have occurred, and every displayed deletion state is
reachable.  For an outside site \(z\), blocking at every state in (9.3)
is equivalent to \(b_S(z)\ge m\): at most \(m-1\) deletions cannot hit
\(m\) disjoint matching edges, while fewer than \(m\) edges can all be
hit by an allowed deletion set.  Therefore a full-square embedding with
this uniform outside guard would preserve \(\delta\ge m\), witnessed
by the old larger set \(A\cup W\).  No such embedding is asserted here.

For the \(\beta=1\) extension with \(m\ge2\), the relevant threshold is
\[
 h=E+3=|S'|-m+1.
\]
At that height the component is the union of the deletion families with at
most \(m-1\) deletions from each of the three neutral top states. The
uniform guard is \(b_T(z)\ge m\) for every outside site \(z\) and each top
state \(T\). The preceding base height \(E+1\) is not the extension
threshold: at that lower height the extension can escape. This specifies the
component to which Proposition 9.1 applies.

An elementary obstruction already excludes naive dilation.  Every pair of
a safe \(k\)-set blocks at most \(n-2\) additional grid sites, so
maximality requires

\[
 n^2-k\le {k\choose2}(n-2).
 \tag{9.4}
\]

The checked 17-point start on the 22-site restricted carrier fits inside
\(G_{147}\), but (9.4) leaves at least
\(147^2-17-{17\choose2}145=1872\) immediately free sites.  This proves
failure of maximality for that embedding, not a value of its full-square
path deficit.

### 9.2 A full-square obstruction pattern

A full-square certificate for one example with \(\delta\ge3\) would require:

1. a safe maximal \(S\subseteq G_n\) with blockers recorded at every empty
   grid site;
2. a threshold-component lower-bound certificate, not only a large blocker
   count at selected named sites;
3. a larger safe set, or a sharp maximum proof and an escape path.

An unbounded full-square family would additionally need a scaling mechanism
that keeps the extra lattice sites saturated and excludes alternative routes.

One decisive sufficient certificate would be a submaximum safe
\(S\subseteq G_n\) with \(b_S(x)\ge3\) for every empty \(x\), together with
any larger safe set.  The first-insertion bound then gives
\(\delta(S)\ge3\). This is a sufficient condition, not an existence
assertion; Section 9.3 excludes it on \(G_7,G_8\).

There is a useful reduction at size \(2n-1\).  If
\(S\subseteq G_n\) is safe with \(|S|=2n-1\), each row and column contains
at most two selected points.  Thus exactly one row \(r_0\) and one column
\(c_0\) contain one selected point; every other row and column contains two.
For an empty point \(x\),

\[
 b_S(x)=\mathbf 1[x\text{ is on a full row}]
       +\mathbf 1[x\text{ is on a full column}]
       +b_S^{\mathrm{obl}}(x),
 \tag{9.5}
\]

where \(b_S^{\mathrm{obl}}(x)\) counts non-axis-parallel blocker secants.
Therefore a size-\(2n-1\) candidate with \(\beta\ge3\) needs at least one
oblique blocker away from the deficient row and column, at least two on
either deficient axis away from their intersection, and, if their
intersection is empty, at least three there. Whenever a \(2n\)-point safe
comparison configuration is available, it is a larger witness. These are
full-square-specific requirements for a decisive search; they do not assert
that such a set exists.

Independent copies of small barriers do not add deficits.  If there are no
mixed collinear triples between the carriers, repair each part while holding
the others fixed.  Earlier repairs only increase the total cardinality, so
the combined deficit is at most the largest individual deficit.  Thus copies
of a fixed independent gadget alone cannot produce an unbounded family.

More generally, extra selected points can compensate for a projected loss
on the old carrier. None of the preceding conditions gives a universal bound
for complete squares.

### 9.3 Certified exclusions and path bounds on \(G_7,G_8\)

The following **exactly checked** results use the certificate package
described in Section 11. It distinguishes complete certificates from bounded
searches.

**Result 9.2 (high-blocker exclusion).** Every submaximum safe set on
\(G_7\) or \(G_8\) has \(\beta\le2\).

**Encoding and certificate.** Introduce occupation variables \(x_p\) and
pair variables \(e_{pq}\leftrightarrow(x_p\wedge x_q)\). Impose a
negative clause for every collinear triple and, for each site \(y\),

\[
 \sum_{\substack{\{p,q\}\subseteq G_n\setminus\{y\}\\p,q,y\text{ collinear}}}
       e_{pq}\ \ge\ 3(1-x_y).
 \tag{9.6}
\]

At an empty site the sum is precisely \(b_S(y)\); at an occupied site
the inequality is vacuous. Exact unary threshold equivalences encode these
sums and \(|S|\le2n-1\). For successive input literals \(\ell_i\),
the recurrence is
\(z_{i,t}\leftrightarrow z_{i-1,t}\vee(\ell_i\wedge z_{i-1,t-1})\),
with \(z_{i,0}=1\), \(z_{0,t}=0\) for \(t>0\), and explicit boundary
cases. Induction gives the intended threshold semantics. Thus satisfiability
is equivalent to the claimed obstruction; no symmetry restriction is used.
Independently checked 14- and 16-point witnesses, together with the row
bound, establish \(\alpha(G_7)=14\), \(\alpha(G_8)=16\).

| Board | Cardinality scope | Collinear triples | CNF variables | CNF clauses | DRAT-trim result |
|---|---|---:|---:|---:|---|
| \(G_7\) | \(0\le |S|\le13\) | 824 | 9,089 | 33,176 | VERIFIED UNSAT |
| \(G_8\) | \(0\le |S|\le15\) | 1,544 | 16,688 | 61,185 | VERIFIED UNSAT |

The supplement's proof receipt records hashes of the historical instances,
proofs, checker source and logs. Section 11 distinguishes these receipts
from the archived source and the regeneration procedure. This result excludes a local first-insertion barrier of
three on these boards. It
does **not** exclude \(\delta\ge3\) when \(\beta=1\) or 2.

**Result 9.3 (complete specified layers).** Every maximal safe set in
each of the following classes has \(\delta\le2\).

| Board | Size | All safe sets of that size | All labelled maximal sets | D4 representatives with paths |
|---|---:|---:|---:|---:|
| \(G_7\) | 12 | 471,860 | 305,960 | 38,493 |
| \(G_7\) | 13 | 15,532 | 13,684 | 1,722 |
| \(G_8\) | 15 | 79,968 | 73,888 | 9,251 |

For a maximal \(k\)-set, the search traverses \(J_{k-1}\), testing
whether a state extends all the way to a maximum. Each route is expanded
into ordinary insertions and deletions at floor at least \(k-2\).
Separate determinant code checks every move. A separate row-recursion
verifier considers every zero-, one- or two-point row choice, tests safety
and maximality, and checks each maximal leaf against the symmetry-expanded
path starts. This establishes coverage, rather than inferring it from a
search completion flag. The three coverage receipts are included in the
supplement.

In the first row the target test requires three compatible insertions
from an 11-set to reach size fourteen; extension merely to thirteen would
not certify a maximum route. Nonmaximal sets of sizes 13 on \(G_7\) and
15 on \(G_8\) insert directly to maxima. A nonmaximal 12-set on \(G_7\)
extends to the covered 13-layer and has \(\delta\le1\) by Lemma 6.2.

Additional bounded row searches, nonuniform random greedy samples and
targeted \(\beta=2\) candidates yielded no third-barrier witness. An
independent path audit verified 251,579 path records from **244,443 distinct
tested starts**, all reaching a maximum at floor at least their starting size
minus two. Its compact scope receipt is included in the supplement; the
large path list is omitted as described in Section 11.
The sample lists overlap; the complete-class counts above are separate
coverage statements. No whole-class conclusion is inferred for the
remaining sizes. These data settle neither \(\delta\le2\) for every
maximal state of \(G_7,G_8\) nor a bound for larger boards.

## 10. Open questions

1. Is \(\delta\le2\) for every maximal safe subset of every \(G_n\), or does
   a full-square example with \(\delta\ge3\) exist?
2. Does a submaximum \(S\subseteq G_n\) exist with \(b_S(x)\ge3\) at every
   empty \(x\)? The complete \(n\le6\) census and Result 9.2 exclude
   this on all boards through eight; the next possible board is \(G_9\).
   At size \(2n-1\), equation (9.5) supplies a particularly sharp necessary
   condition whenever a \(2n\)-point comparison set is available.
3. Can the four \(G_6\) motifs be coupled into serial threshold locks rather
   than placed as independent gadgets?
4. What statistics of the labelled matching field predict which threshold
   component contains a maximal set?
5. Is there prior work already containing a Euclidean-grid reconfiguration
   census, these component types, or the restricted-carrier construction?

## 11. Reproducibility, scope, and software

The accompanying supplement contains the source needed for deterministic
reconstruction of the finite enumerations, matching-component data, SAT
encodings, and coverage checks. It also contains compact result receipts and
SHA-256 hashes. A fresh external replay independently enumerated the
\(G_n\) state spaces for \(1\le n\le6\), recovered the \(G_6\) counts and
the C1–C4 classification, and checked the displayed path and component
certificates. The finite claims in Sections 6--7 are therefore **exactly
checked**; they are not proof-assistant formalizations.

The \(G_7,G_8\) high-blocker exclusions are certified by DRAT traces whose
raw compressed files exceed the venue's supplement limit. The archive
therefore includes the exact encoding generator, semantic checker, source
and result hashes, and independently checked verification receipts, but not
the raw traces or the large path lists. Those receipts are evidence of a
verification run, not substitutes for the omitted traces. The supplement supplies commands for regenerating the CNFs, new DRAT
proofs, and the three complete path classes, with independent checks. The
additional sampled-path aggregate is documented by receipts and original
hashes only; its entire historical sample is not archived in this package.
The three complete path classes in Result 9.3 are precisely the three rows
in its table. Across the combined, overlapping runs, 244,443 distinct tested
starts were checked; the bounded or sampled populations support no unlisted
whole-layer conclusion.

The certified SAT work used PySAT [13] with Glucose [14]; MiniSat [15] is
credited as an acknowledged basis of that solver lineage. DRAT validation
used DRAT-trim [16]. The supplied C++ and Python programs require a
standards-conforming C++ compiler and Python 3; exact package versions and
commands are listed in the supplement.

The literature review found a public prior C4 occurrence and established
realization/reconfiguration antecedents cited above. No claim of historical
priority is made. In particular, the results do not prove a full-square
unbounded-deficit theorem or a universal upper bound on \(\delta\).

## References

1. O. Aichholzer, D. Eppstein, and E.-M. Hainzl, *Geometric dominating
   sets -- A minimum version of the no-three-in-line problem*,
   *Computational Geometry* 108 (2023), 101913.
   https://arxiv.org/abs/2203.13170
2. M. Kamiński, P. Medvedev, and M. Milanič, *Complexity of independent
   set reconfigurability problems*, *Theoretical Computer Science* 439
   (2012), 9--15. https://doi.org/10.1016/j.tcs.2012.03.004
3. M. de Berg, B. M. P. Jansen, and D. Mukherjee, *Independent-Set
   Reconfiguration Thresholds of Hereditary Graph Classes*, FSTTCS 2016,
   34:1--34:15. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.34
4. M. A. Adena, D. A. Holton, and P. A. Kelly, *Some thoughts on the
   no-three-in-line problem*, in *Combinatorial Mathematics*, 1974.
5. V. Froese, I. Kanj, A. Nichterlein, and R. Niedermeier, *Finding Points
   in General Position*, *International Journal of Computational Geometry
   & Applications* 27(4) (2017), 277--296. Proposition 1.
   https://arxiv.org/abs/1508.01097
6. S. K. Ghosh and B. Roy, *Some results on point visibility graphs*,
   *Theoretical Computer Science* 575 (2015), 17--32.
   https://doi.org/10.1016/j.tcs.2014.10.042
7. D. T. Nagy, Z. L. Nagy, and R. Woodroofe, *The extensible
   No-Three-In-Line problem*, *European Journal of Combinatorics* 114
   (2023), 103796. https://arxiv.org/abs/2209.01447
8. D. Bartoli, A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco,
   *On upper bounds on the smallest size of a saturating set in a projective
   plane*. https://arxiv.org/abs/1505.01426
9. M. Gardner, *Mathematical Games* column, 1976; cited for historical
   context by [1].
10. u/cedar_conics, *Positive neutral mobility and positive C1 drift can
    remain inside a closed component*, r/no_three_in_line, 6 October 2026,
    11:51:13 UTC. https://rstation.ai/r/no_three_in_line/posts/26#comment-8e7ed041-54fd-4cf8-a50f-75274a27f6df
11. Wilhelmina, blocker/exchange computation, 17 September 2026.
    https://einsteinarena.com/problems/no-three-in-line-75/threads/267
12. 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.25133 (2026).
    https://arxiv.org/abs/2609.25133
13. A. Ignatiev, A. Morgado, and J. Marques-Silva, PySAT.
    https://pysathq.github.io/
14. G. Audemard and L. Simon, Glucose SAT solver.
    https://www.labri.fr/perso/lsimon/research/glucose/
15. N. Eén and N. Sörensson, MiniSat SAT solver.
    https://github.com/niklasso/minisat
16. N. Wetzler, M. J. H. Heule, and W. A. Hunt Jr., DRAT-trim:
    efficient checking and trimming using expressive clausal proofs.
    https://github.com/marijnheule/drat-trim