ternary_affine_hyperplane_card
For every natural number $n \ge 1$, every vector $a \in (\mathbb{Z}/3\mathbb{Z})^n$ with all non-zero coordinates, and every $b \in \mathbb{Z}/3\mathbb{Z}$, the ternary affine hyperplane $\{x \in (\mathbb{Z}/3\mathbb{Z})^n \mid \sum_{i} a_i x_i = b\}$ has cardinality $3^{n - 1}$.
Statement
theorem ternary_affine_hyperplane_card (n : ℕ) (hn : 1 ≤ n) (a : Fin n → ZMod 3) (ha : ∀ i, a i ≠ 0) (b : ZMod 3) : (ternary_affine_hyperplane n a b).card = 3 ^ (n - 1)- Source
- arXiv:2610.32789, Section 3.1
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 1
- ternary_single_point_repair_cardFor every explicit integer n ≥ 1, every vector a : Fin n → ZMod 3 with all coordinates nonzero, every scalar b : ZMod 3, every point p in…
Read back from the Lean
For every natural number $n$ with $n \ge 1$, every vector $a : \text{Fin } n \to \mathbb{Z}/3\mathbb{Z}$ such that $a(i) \ne 0$ for all $i \in \text{Fin } n$, and every scalar $b \in \mathbb{Z}/3\mathbb{Z}$, the cardinality of ternary_affine_hyperplane n a b is $3^{n - 1}$.
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
The theorem is proved by case analysis on n: the case n = 0 is ruled out by the hypothesis 1 ≤ n, reducing the problem to the successor case n = m + 1. For n = m + 1, the auxiliary lemma `ternary_affine_hyperplane_card_succ` establishes that the hyperplane has cardinality 3^m by constructing a bijection with (ZMod 3)^m via the projection that drops the first coordinate (where a 0 ≠ 0). Injectivity and surjectivity hold because, once the remaining m coordinates are fixed, the hyperplane condition becomes a linear equation in a single variable over ZMod 3 with a nonzero coefficient, which has a unique solution.
The universe of functions Fin m → ZMod 3 has cardinality 3^m, reducing the goal to showing that the hyperplane has the same cardinality as this universe.
The size of Finset.univ on functions Fin m → ZMod 3 is computed as |ZMod 3|^|Fin m| = 3^m using cardinality formulas for function spaces (`Fintype.card_fun`), `Fin m` (`Fintype.card_fin`), and `ZMod 3` (`ZMod.card`). Rewriting by this fact substitutes Finset.univ.card for 3^m in the goal.
uses
Finset.card_univ,Fintype.card_fun,Fintype.card_fin,ZMod.cardhave hc : (Finset.univ : Finset (Fin m → ZMod 3)).card = 3 ^ m := by simp only [Finset.card_univ, Fintype.card_fun, Fintype.card_fin, ZMod.card] rw [← hc]
It suffices to show that the coordinate projection x ↦ (i ↦ x(i + 1)) is a bijection from the hyperplane to (ZMod 3)^m.
By `Finset.card_bij`, two finite sets have equal cardinality if there exists a map between them that is well-defined, injective, and surjective. The projection drops the 0-th coordinate, sending x ∈ (ZMod 3)^(m + 1) to x ∘ Fin.succ. Because the codomain is Finset.univ, the well-definedness goal is satisfied automatically by `Finset.mem_univ`.
uses
Finset.card_bij,Finset.mem_univapply Finset.card_bij (fun x _ => fun i : Fin m => x i.succ) · intro x hx exact Finset.mem_univ _
The coordinate projection is injective on the hyperplane.
Assume x₁ and x₂ are points in the hyperplane whose projections agree, so x₁(i + 1) = x₂(i + 1) for all i < m by functional extensionality (`funext_iff.mp`). Unfolding the definition of the hyperplane with `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, both points satisfy ∑ i, a i * x i = b. Splitting the sums at 0 with `Fin.sum_univ_succ`, the tail sums over positive indices match because the coordinates agree there. Subtracting the two equations isolates a 0 * x₁ 0 = a 0 * x₂ 0. Since a 0 ≠ 0, left cancellation (`mul_left_cancel₀`) yields x₁ 0 = x₂ 0. Combining equality at 0 and equality on all successors via `Fin.cases` establishes x₁ = x₂.
uses
ternary_affine_hyperplane,Finset.mem_filter,Finset.mem_univ,true_and,funext_iff.mp,Fin.sum_univ_succ,mul_left_cancel₀,Fin.cases· intro x₁ hx₁ x₂ hx₂ heq simp only [ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and] at hx₁ hx₂ have heq_succ : ∀ i : Fin m, x₁ i.succ = x₂ i.succ := funext_iff.mp heq rw [Fin.sum_univ_succ] at hx₁ hx₂ have hsum : (∑ i : Fin m, a i.succ * x₁ i.succ) = (∑ i : Fin m, a i.succ * x₂ i.succ) := by congr 1 ext i rw [heq_succ i] rw [hsum] at hx₁ have ha0x : a 0 * x₁ 0 = a 0 * x₂ 0 := by linear_combination hx₁ - hx₂ have hx0 : x₁ 0 = x₂ 0 := mul_left_cancel₀ ha0 ha0x ext i refine Fin.cases ?_ ?_ i · exact hx0 · intro j exact heq_succ j
The coordinate projection is surjective onto (ZMod 3)^m.
Given y ∈ (ZMod 3)^m, we construct a preimage using `Fin.cons` by setting the 0-th coordinate to (a 0)⁻¹ * (b - ∑ i, a (i + 1) * y i) and the remaining coordinates to y. The projection of this vector to positive indices is definitionally y. To verify that it lies in the hyperplane, we unfold the definition and split the sum at 0 with `Fin.sum_univ_succ`. Since a 0 ≠ 0, the product a 0 * (a 0)⁻¹ simplifies to 1 via `mul_inv_cancel₀`, `mul_assoc`, and `one_mul`, and `ring` simplifies (b - S) + S = b.
uses
Fin.cons,ternary_affine_hyperplane,Finset.mem_filter,Finset.mem_univ,true_and,Fin.sum_univ_succ,mul_assoc,mul_inv_cancel₀,one_mul· intro y _ refine ⟨Fin.cons ((a 0)⁻¹ * (b - ∑ i : Fin m, a i.succ * y i)) y, ?_, rfl⟩ simp only [ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and] rw [Fin.sum_univ_succ] change a 0 * ((a 0)⁻¹ * (b - ∑ i : Fin m, a i.succ * y i)) + (∑ i : Fin m, a i.succ * y i) = b rw [← mul_assoc, mul_inv_cancel₀ ha0, one_mul] ring
For every n ≥ 1, the ternary affine hyperplane has cardinality 3^(n - 1).
Case analysis on n: the case n = 0 contradicts 1 ≤ n, which `omega` rules out by linear arithmetic. When n = m + 1, the assumption that all coordinates of a are nonzero ensures a 0 ≠ 0, so the successor lemma `ternary_affine_hyperplane_card_succ` applies directly, giving cardinality 3^m = 3^((m + 1) - 1).
uses
ternary_affine_hyperplane_card_succcases n with | zero => omega | succ m => exact ternary_affine_hyperplane_card_succ m a (ha 0) b
Finset.card_univ- The cardinality of the universal finset `Finset.univ` of a finite type α equals the cardinality of α as a fintype.
Fintype.card_fun- The cardinality of the function space α → β between finite types is |β|^|α|.
Fintype.card_fin- The finite set Fin n of natural numbers strictly less than n has cardinality n.
ZMod.card- The ring of integers modulo n, ZMod n, has cardinality n.
Finset.card_bij- Two finite sets s and t have the same cardinality if there exists a map from s to t that is well-defined, injective, and surjective.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
ternary_affine_hyperplane- The ternary affine hyperplane of vectors x ∈ (ZMod 3)^n satisfying ∑ i, a i * x i = b, defined by filtering Finset.univ.
Finset.mem_filter- An element belongs to Finset.filter p s if and only if it belongs to s and satisfies the predicate p.
true_and- The proposition True ∧ p simplifies to p.
funext_iff.mp- If two functions are equal, then their values agree on every input.
Fin.sum_univ_succ- A sum over Fin (n + 1) equals its value at 0 plus the sum of its values on successors over Fin n.
mul_left_cancel₀- In a structure with no zero divisors, multiplying on the left by a nonzero element is injective (a * b = a * c implies b = c).
Fin.cases- Every element of Fin (n + 1) is either 0 or the successor of an element of Fin n.
Fin.cons- Constructs a function on Fin (n + 1) from a head value at 0 and a tail function on Fin n.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
mul_inv_cancel₀- Multiplying a nonzero element by its multiplicative inverse yields 1.
one_mul- Multiplying an element by 1 on the left leaves it unchanged.
ternary_affine_hyperplane_card_succ- An affine hyperplane in (ZMod 3)^(m + 1) whose normal vector has a nonzero first coefficient has cardinality 3^m.
- The formal proof works with functions on `Fin (m + 1)` rather than coordinate tuples, representing the separation of the 0-th coordinate from the remaining m coordinates via `Fin.cases`, `Fin.cons`, and `Fin.sum_univ_succ`.
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.
lemma ternary_affine_hyperplane_card_succ (m : ℕ) (a : Fin (m + 1) → ZMod 3) (ha0 : a 0 ≠ 0) (b : ZMod 3) : (ternary_affine_hyperplane (m + 1) a b).card = 3 ^ m := by have hc : (Finset.univ : Finset (Fin m → ZMod 3)).card = 3 ^ m := by simp only [Finset.card_univ, Fintype.card_fun, Fintype.card_fin, ZMod.card] rw [← hc] apply Finset.card_bij (fun x _ => fun i : Fin m => x i.succ) · intro x hx exact Finset.mem_univ _ · intro x₁ hx₁ x₂ hx₂ heq simp only [ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and] at hx₁ hx₂ have heq_succ : ∀ i : Fin m, x₁ i.succ = x₂ i.succ := funext_iff.mp heq rw [Fin.sum_univ_succ] at hx₁ hx₂ have hsum : (∑ i : Fin m, a i.succ * x₁ i.succ) = (∑ i : Fin m, a i.succ * x₂ i.succ) := by congr 1 ext i rw [heq_succ i] rw [hsum] at hx₁ have ha0x : a 0 * x₁ 0 = a 0 * x₂ 0 := by linear_combination hx₁ - hx₂ have hx0 : x₁ 0 = x₂ 0 := mul_left_cancel₀ ha0 ha0x ext i refine Fin.cases ?_ ?_ i · exact hx0 · intro j exact heq_succ j · intro y _ refine ⟨Fin.cons ((a 0)⁻¹ * (b - ∑ i : Fin m, a i.succ * y i)) y, ?_, rfl⟩ simp only [ternary_affine_hyperplane, Finset.mem_filter, Finset.mem_univ, true_and] rw [Fin.sum_univ_succ] change a 0 * ((a 0)⁻¹ * (b - ∑ i : Fin m, a i.succ * y i)) + (∑ i : Fin m, a i.succ * y i) = b rw [← mul_assoc, mul_inv_cancel₀ ha0, one_mul] ring/-- Every affine hyperplane with nonzero normal coefficients has size 3^(n-1). -/theorem ternary_affine_hyperplane_card (n : ℕ) (hn : 1 ≤ n) (a : Fin n → ZMod 3) (ha : ∀ i, a i ≠ 0) (b : ZMod 3) : (ternary_affine_hyperplane n a b).card = 3 ^ (n - 1) := by cases n with | zero => omega | succ m => exact ternary_affine_hyperplane_card_succ m a (ha 0) b