AFTD Auto-Formalizing Theoretical Domains

line_cubic_nat_family_exists

theoremverified

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

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.

  1. 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).

    line 10

      constructor <;> decide +kernel
  2. 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.

    lines 17–18

    uses good_base

      induction k with
      | zero => exact good_base
  3. 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.

    lines 20–21

    uses family, Nat.add_assoc, Nat.add_left_comm, Nat.add_comm, good_step

        simpa [family, Nat.add_assoc, Nat.add_left_comm, Nat.add_comm] using
          good_step (k+5) (by omega) (family k) hk
  4. 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.

    lines 27–30

    uses LineBuild.good_family

      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⟩
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).

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

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⟩
See it in the graphDiscuss this resultChallenge it