AFTD Auto-Formalizing Theoretical Domains

ternary_affine_hyperplane_card

theoremverified

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.

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

    lines 3–5

    uses Finset.card_univ, Fintype.card_fun, Fintype.card_fin, ZMod.card

      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]
  2. 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`.

    lines 6–8

    uses Finset.card_bij, Finset.mem_univ

      apply Finset.card_bij (fun x _ => fun i : Fin m => x i.succ)
      · intro x hx
        exact Finset.mem_univ _
  3. 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₂.

    lines 9–25

    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
  4. 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.

    lines 26–32

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

    lines 36–39

    uses ternary_affine_hyperplane_card_succ

      cases 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.

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

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