AFTD Auto-Formalizing Theoretical Domains

ternary_affine_hyperplane_is_minimal_line_cover

theoremverifiedformalization

For any integer $n \ge 1$, any vector $a : \mathrm{Fin}\ n \to \mathbb{Z}/3\mathbb{Z}$ with all coordinates nonzero, and any scalar $b \in \mathbb{Z}/3\mathbb{Z}$, the affine hyperplane $\{x \in (\mathbb{Z}/3\mathbb{Z})^n \mid \sum_{i} a(i) x(i) = b\}$ is an inclusion-minimal ternary line cover of $(\mathbb{Z}/3\mathbb{Z})^n$.

Statement

theorem ternary_affine_hyperplane_is_minimal_line_cover (n : ℕ) (hn : 1 ≤ n) (a : Fin n → ZMod 3) (ha : ∀ i, a i ≠ 0) (b : ZMod 3) : is_minimal_ternary_line_cover n (ternary_affine_hyperplane n a b)
Formalizes
arXiv:2610.32789, Section 3.1
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_minimal_ternary_line_coverGiven an explicit natural number n, a finite set B : Finset (Fin n → ZMod 3) is an inclusion-minimal ternary line cover if B is a ternary…
  • ternary_affine_hyperplaneGiven an explicit natural number n, a vector a : Fin n → ZMod 3, and a scalar b : ZMod 3, the ternary affine hyperplane is the finite set…
  • is_ternary_line_coverGiven an explicit natural number n, a finite set B : Finset (Fin n → ZMod 3) is a ternary line cover if for every coordinate i : Fin n and…

Read back from the Lean

For any natural number $n \ge 1$, any vector $a : \mathrm{Fin}\ n \to \mathbb{Z}/3\mathbb{Z}$ such that $a(i) \ne 0$ for all $i \in \mathrm{Fin}\ n$, and any scalar $b \in \mathbb{Z}/3\mathbb{Z}$, the affine hyperplane $\{x \in (\mathbb{Z}/3\mathbb{Z})^n \mid \sum_{i} a(i) x(i) = b\}$ is a minimal ternary line cover of $(\mathbb{Z}/3\mathbb{Z})^n$ (that is, it intersects every axis-parallel line, and no proper subset of it intersects every axis-parallel line).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that the affine hyperplane $H = \{x \mid \sum a_i x_i = b\}$ is a ternary line cover, we fix any axis-parallel line and solve for the varying coordinate: since each coefficient $a_i$ is nonzero in the field $\mathbb{Z}/3\mathbb{Z}$, the linear equation uniquely determines the coordinate as $a_i^{-1}(b - \sum_{j \ne i} a_j c_j)$. To prove minimality, let $B' \subseteq H$ also cover all lines; for any $x \in H$, the line through $x$ in direction $0$ must intersect $B'$ at some point $x[0 \mapsto t]$. Since $B' \subseteq H$, both $x$ and $x[0 \mapsto t]$ satisfy the hyperplane equation, which by invertibility of $a_0$ forces $t = x_0$ and thus $x = x[0 \mapsto t] \in B'$, establishing $B' = H$.

  1. Updating coordinate $i$ of a vector $c$ to $t$ gives $\sum_{j=1}^n a_j (c[i \mapsto t])_j = (\sum_{j \ne i} a_j c_j) + a_i t$.

    We separate the $i$-th term from the sum over all coordinates using `Finset.sum_erase_add`. For every other coordinate $j \ne i$, the updated function agrees with $c$ by `Function.update_apply` and `Finset.ne_of_mem_erase`, so those terms sum to $\sum_{j \ne i} a_j c_j$ via `Finset.sum_congr`. At index $i$, the updated coordinate is $t$, giving the term $a_i t$.

    lines 5–14

    uses Finset.sum_erase_add, Finset.mem_univ, Finset.sum_congr, Finset.ne_of_mem_erase, Function.update_apply

      rw [← Finset.sum_erase_add (s := Finset.univ)
            (f := fun j => a j * (Function.update c i t) j) (a := i) (Finset.mem_univ i)]
      congr 1
      · apply Finset.sum_congr rfl
        intro j hj
        have hji : j ≠ i := Finset.ne_of_mem_erase hj
        rw [Function.update_apply]
        simp [hji]
      · rw [Function.update_apply]
        simp
  2. To show $H$ is a minimal ternary line cover, it suffices to prove that $H$ is a ternary line cover, and that any sub-cover $B' \subseteq H$ equals $H$.

    Unfolding the definition `is_minimal_ternary_line_cover`, we split the goal into two parts: verifying the covering property for $H$, and establishing minimality under inclusion.

    lines 18–19

      unfold is_minimal_ternary_line_cover
      refine ⟨?_, ?_⟩
  3. The affine hyperplane $H = \{x \mid \sum_{j} a_j x_j = b\}$ is a ternary line cover.

    Given any coordinate direction $i$ and point $c \in (\mathbb{Z}/3\mathbb{Z})^n$, we need to find $t \in \mathbb{Z}/3\mathbb{Z}$ such that $c[i \mapsto t] \in H$. Because $a_i \ne 0$ in the field $\mathbb{Z}/3\mathbb{Z}$, it has an inverse $a_i^{-1}$ by `mul_inv_cancel₀`. Setting $t = a_i^{-1}(b - \sum_{j \ne i} a_j c_j)$, the sum expands by our helper lemma to $(\sum_{j \ne i} a_j c_j) + a_i t$, where the $a_i$ and $a_i^{-1}$ cancel, leaving $b$ after ring simplification.

    lines 20–25

    uses ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and, ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update, mul_assoc, mul_inv_cancel₀, one_mul

      · intro i c
        refine ⟨(a i)⁻¹ * (b - ∑ j ∈ Finset.univ.erase i, a j * c j), ?_⟩
        simp only [ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and]
        rw [ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update]
        rw [← mul_assoc, mul_inv_cancel₀ (ha i), one_mul]
        ring
  4. For any sub-cover $B' \subseteq H$, to show $B' = H$ it suffices to prove $H \subseteq B'$.

    We introduce an arbitrary subset $B' \subseteq H$ that is also a ternary line cover. By antisymmetry of set inclusion (`Finset.Subset.antisymm`), since $B' \subseteq H$ is given, it remains only to show $H \subseteq B'$. We take an arbitrary $x \in H$.

    lines 26–28

    uses Finset.Subset.antisymm

      · intro B' hB' hcover
        apply Finset.Subset.antisymm hB'
        intro x hx
  5. There is a scalar $t$ such that $x[0 \mapsto t] \in B'$, and this point also lies in $H$.

    Since $n \ge 1$, we choose coordinate direction $i = 0$. Because $B'$ covers every axis-parallel line, the line through $x$ in direction $i$ intersects $B'$ at some point $x[i \mapsto t]$. Since $B' \subseteq H$, this point also belongs to $H$, so both $x$ and $x[i \mapsto t]$ satisfy the hyperplane equation with value $b$.

    lines 29–32

    uses ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and

        let i : Fin n := ⟨0, hn⟩
        obtain ⟨t, ht⟩ := hcover i x
        have htH : Function.update x i t ∈ ternary_affine_hyperplane n a b := hB' ht
        simp only [ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and] at hx htH
  6. The scalar $t$ must equal $x_i$.

    Since both $x$ and $x[i \mapsto t]$ lie on $H$, their linear forms both equal $b$, and hence equal each other. Applying the helper lemma to the left side and `Finset.sum_erase_add` to the right side gives $(\sum_{j \ne i} a_j x_j) + a_i t = (\sum_{j \ne i} a_j x_j) + a_i x_i$. Cancelling the common sum on the left with `add_left_cancel` yields $a_i t = a_i x_i$. Because $a_i \ne 0$, we cancel $a_i$ using `mul_left_cancel₀` to conclude $t = x_i$.

    lines 33–38

    uses ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update, Finset.sum_erase_add, Finset.mem_univ, mul_left_cancel₀, add_left_cancel

        have hti : t = x i := by
          have h1 : ∑ j : Fin n, a j * (Function.update x i t) j = ∑ j : Fin n, a j * x j := by
            rw [htH, hx]
          rw [ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update,
            ← Finset.sum_erase_add (s := Finset.univ) (f := fun j => a j * x j) (a := i) (Finset.mem_univ i)] at h1
          exact mul_left_cancel₀ (ha i) (add_left_cancel h1)
  7. $x \in B'$, completing the proof that $B' = H$.

    Since $t = x_i$, replacing the $i$-th coordinate of $x$ with $t$ does not change $x$ at all: by cases on $j = i$ using `Function.update_apply`, we have $(x[i \mapsto t])_j = x_j$ for all $j$, so $x[i \mapsto t] = x$ by function extensionality. Since $x[i \mapsto t] \in B'$, it follows that $x \in B'$.

    lines 39–46

    uses Function.update_apply

        have hux : Function.update x i t = x := by
          funext j
          rw [Function.update_apply]
          by_cases hji : j = i
          · simp [hji, hti]
          · simp [hji]
        rw [← hux]
        exact ht
add_left_cancel
In an additive structure with left-cancellation, $a + b = a + c$ implies $b = c$.
Finset.mem_filter
An element $x$ belongs to $\mathrm{filter}(p, s)$ if and only if $x \in s$ and $p(x)$ holds.
Finset.mem_univ
Every element of a finite type belongs to its universal finset $\mathrm{univ}$.
Finset.ne_of_mem_erase
An element belonging to $s \setminus \{a\}$ cannot equal $a$.
Finset.sum_congr
If two finite sets are equal and their summands agree on every element, then the sums are equal.
Finset.sum_erase_add
For any element $a \in s$, the sum over $s$ splits as $\sum_{x \in s \setminus \{a\}} f(x) + f(a) = \sum_{x \in s} f(x)$.
Finset.Subset.antisymm
If $A \subseteq B$ and $B \subseteq A$, then $A = B$.
Function.update_apply
Evaluating an updated function $f[a' \mapsto b]$ at $a$ yields $b$ if $a = a'$, and $f(a)$ otherwise.
mul_assoc
Multiplication is associative: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$.
mul_inv_cancel₀
For any nonzero element $a$ in a group with zero (such as a field), $a \cdot a^{-1} = 1$.
mul_left_cancel₀
If $a \ne 0$ and $a \cdot b = a \cdot c$, then $b = c$.
one_mul
Multiplying by $1$ on the left leaves the element unchanged: $1 \cdot a = a$.
ternary_affine_hyperplane
The affine hyperplane of vectors $x \in (\mathbb{Z}/3\mathbb{Z})^n$ satisfying $\sum_{i} a_i x_i = b$.
ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update
Modifying a vector $c$ at coordinate $i$ to $t$ changes the linear form to $\sum_j a_j (c[i \mapsto t])_j = (\sum_{j \ne i} a_j c_j) + a_i t$.
true_and
The logical equivalence $(\mathrm{True} \land p) \leftrightarrow p$.

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

private lemma ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update    (n : ℕ) (a c : Fin n → ZMod 3) (i : Fin n) (t : ZMod 3) :    (∑ j : Fin n, a j * (Function.update c i t) j)      = (∑ j ∈ Finset.univ.erase i, a j * c j) + a i * t := by  rw [← Finset.sum_erase_add (s := Finset.univ)        (f := fun j => a j * (Function.update c i t) j) (a := i) (Finset.mem_univ i)]  congr 1  · apply Finset.sum_congr rfl    intro j hj    have hji : j ≠ i := Finset.ne_of_mem_erase hj    rw [Function.update_apply]    simp [hji]  · rw [Function.update_apply]    simp/-- Every affine hyperplane with nonzero normal coefficients is an inclusion-minimal line cover. -/theorem ternary_affine_hyperplane_is_minimal_line_cover (n : ℕ) (hn : 1 ≤ n) (a : Fin n → ZMod 3) (ha : ∀ i, a i ≠ 0) (b : ZMod 3) : is_minimal_ternary_line_cover n (ternary_affine_hyperplane n a b) := by  unfold is_minimal_ternary_line_cover  refine ⟨?_, ?_⟩  · intro i c    refine ⟨(a i)⁻¹ * (b - ∑ j ∈ Finset.univ.erase i, a j * c j), ?_⟩    simp only [ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and]    rw [ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update]    rw [← mul_assoc, mul_inv_cancel₀ (ha i), one_mul]    ring  · intro B' hB' hcover    apply Finset.Subset.antisymm hB'    intro x hx    let i : Fin n := ⟨0, hn⟩    obtain ⟨t, ht⟩ := hcover i x    have htH : Function.update x i t ∈ ternary_affine_hyperplane n a b := hB' ht    simp only [ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and] at hx htH    have hti : t = x i := by      have h1 : ∑ j : Fin n, a j * (Function.update x i t) j = ∑ j : Fin n, a j * x j := by        rw [htH, hx]      rw [ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update,        ← Finset.sum_erase_add (s := Finset.univ) (f := fun j => a j * x j) (a := i) (Finset.mem_univ i)] at h1      exact mul_left_cancel₀ (ha i) (add_left_cancel h1)    have hux : Function.update x i t = x := by      funext j      rw [Function.update_apply]      by_cases hji : j = i      · simp [hji, hti]      · simp [hji]    rw [← hux]    exact ht
See it in the graphDiscuss this resultChallenge it