ternary_affine_hyperplane_is_minimal_line_cover
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$.
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$.
uses
Finset.sum_erase_add,Finset.mem_univ,Finset.sum_congr,Finset.ne_of_mem_erase,Function.update_applyrw [← 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
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.
unfold is_minimal_ternary_line_cover refine ⟨?_, ?_⟩
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.
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
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$.
uses
Finset.Subset.antisymm· intro B' hB' hcover apply Finset.Subset.antisymm hB' intro x hx
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$.
uses
ternary_affine_hyperplane,Finset.mem_filter,Finset.mem_univ,true_andlet 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
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$.
uses
ternary_affine_hyperplane_is_minimal_line_cover_sum_mul_update,Finset.sum_erase_add,Finset.mem_univ,mul_left_cancel₀,add_left_cancelhave 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)
$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'$.
uses
Function.update_applyhave 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$.
- Updating a function at a single index is represented in Lean by `Function.update c i t`, which corresponds on paper to replacing the $i$-th coordinate of $c$ with $t$.
- The choice of direction $i$ on line 29 uses the hypothesis $n \ge 1$ to form $0 \in \mathrm{Fin}\ n$ as a valid coordinate index.
- On line 25, the `ring` tactic verifies the cancellation $(\sum_{j \ne i} a_j c_j) + (b - \sum_{j \ne i} a_j c_j) = b$ in the ring $\mathbb{Z}/3\mathbb{Z}$.
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.
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