line_cubic_nat_family_exists
Every n at least five admits a bounded natural-index support family of size 2n+1 with the required line cubic moments and the boundary invariant.
Statement
theorem line_cubic_nat_family_exists (n : ℕ) (hn : 5 ≤ n) : ∃ S : Finset (Finset ℕ), LineBuild.Good n S- Source
- Auxiliary construction for OP-4, the line cubic exact-count question in arXiv:2610.01024; new boundary induction developed here.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- line_cubic_boundary_extensionRemoving the two designated boundary supports, adjoining the new index to every other support and adding four boundary supports preserves…
- Used by 1
- open_problem_line_cubic_t_countFor every integer n ≥ 5, there exists a parity representation of the line cubic syndrome of cardinality 2n + 1.
The proof, explained
To show that every n ≥ 5 admits a good support family of size 2n + 1, we first verify that an explicit 11-subset collection on five elements forms a valid base family (good_base). We then define family k by iterating an extension step that advances any good family for m to one for m + 1, and prove by induction on k that family k is good for k + 5 (good_family). Finally, setting k = n - 5 produces the desired family for any n ≥ 5.
The base family of 11 subsets on 5 elements satisfies Good 5 base. automation
The Good structure requires nine conditions: boundedness of elements below 5, nonemptiness of each set, the cardinality being 2 · 5 + 1 = 11, the boundary conditions {3} ∈ base, {3, 4} ∈ base, and {4} ∉ base, and vanishing first, second, and non-adjacent third moments with unit moment on consecutive triples. Decomposing the structure with constructor leaves nine finite verification goals, all of which are checked and closed automatically by kernel computation (decide +kernel).
constructor <;> decide +kernel
The family construction satisfies Good (0 + 5) (family 0) at the base case k = 0.
By definition, family 0 is base and 0 + 5 = 5, so the goal Good (0 + 5) (family 0) matches good_base directly.
uses
good_baseinduction k with | zero => exact good_base
Assuming family k satisfies Good (k + 5), family (k + 1) satisfies Good (k + 1 + 5).
Since 5 ≤ k + 5 holds by linear arithmetic, good_step applies to family k and the induction hypothesis hk to produce Good ((k + 5) + 1) (step (k + 5) (family k)). Unfolding the definition of family (k + 1) to step (k + 5) (family k) and using the associativity and commutativity of addition to rewrite (k + 5) + 1 as k + 1 + 5, simpa closes the inductive step.
uses
family,Nat.add_assoc,Nat.add_left_comm,Nat.add_comm,good_stepsimpa [family, Nat.add_assoc, Nat.add_left_comm, Nat.add_comm] using good_step (k+5) (by omega) (family k) hk
For any n ≥ 5, there exists a support family S satisfying LineBuild.Good n S.
Since n ≥ 5, linear arithmetic shows that (n - 5) + 5 = n. Specializing good_family to k = n - 5 yields Good (n - 5 + 5) (family (n - 5)). Rewriting with the arithmetic identity gives Good n (family (n - 5)), so family (n - 5) provides the required witness.
uses
LineBuild.good_familyhave he : n-5+5 = n := by omega have hg := LineBuild.good_family (n-5) rw [he] at hg exact ⟨LineBuild.family (n-5),hg⟩
good_base- The explicit 11-element base family on {0, 1, 2, 3, 4} satisfies all conditions of Good 5.
Nat.add_assoc- Addition of natural numbers is associative: (n + m) + k = n + (m + k).
Nat.add_left_comm- Addition of natural numbers satisfies left-commutativity: n + (m + k) = m + (n + k).
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
good_step- Given n ≥ 5 and a good family S for n, step n S is a good family for n + 1.
family- The recursively defined family of support collections, defined by family 0 = base and family (k + 1) = step (k + 5) (family k).
LineBuild.good_family- For every natural number k, family k satisfies Good (k + 5).
- The base case for n = 5 (good_base) is verified purely computationally by the Lean kernel using decide +kernel, checking all nine structural conditions across the 11 subsets of base.
- The inductive step relies on good_step, an auxiliary lemma proved earlier in the development showing that LineBuild.step extends any good family for n to one for n + 1.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option maxHeartbeats 4000000set_option maxRecDepth 4096namespace LineBuilddef base : Finset (Finset ℕ) := {{0,3,4},{0,1,3,4},{1,4},{1,2,4},{0,2,3,4},{0,1,2,3,4}, {2,3,4},{2},{2,3},{3},{3,4}}theorem good_base : Good 5 base := by constructor <;> decide +kerneldef family : ℕ → Finset (Finset ℕ) | 0 => base | k+1 => step (k+5) (family k)theorem good_family (k : ℕ) : Good (k+5) (family k) := by induction k with | zero => exact good_base | succ k hk => simpa [family, Nat.add_assoc, Nat.add_left_comm, Nat.add_comm] using good_step (k+5) (by omega) (family k) hkend LineBuildtheorem line_cubic_nat_family_exists (n : ℕ) (hn : 5 ≤ n) : ∃ S : Finset (Finset ℕ), LineBuild.Good n S := by have he : n-5+5 = n := by omega have hg := LineBuild.good_family (n-5) rw [he] at hg exact ⟨LineBuild.family (n-5),hg⟩