AFTD Auto-Formalizing Theoretical Domains

ternary_single_point_repair_card

theoremverified

For 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 ternary_affine_hyperplane n a b, and every vector ε : Fin n → ZMod 3 with all coordinates nonzero, the finite set ternary_single_point_repair n (ternary_affine_hyperplane n a b) p ε has cardinality 3^(n - 1) + n - 1.

Statement

theorem ternary_single_point_repair_card (n : ℕ) (hn : 1 ≤ n) (a : Fin n → ZMod 3) (ha : ∀ i, a i ≠ 0) (b : ZMod 3) (p : Fin n → ZMod 3) (hp : p ∈ ternary_affine_hyperplane n a b) (ε : Fin n → ZMod 3) (hε : ∀ i, ε i ≠ 0) : (ternary_single_point_repair n (ternary_affine_hyperplane n a b) p ε).card = 3 ^ (n - 1) + n - 1
Source
arXiv:2610.32789, Section 3.1
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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…
  • ternary_single_point_repairGiven an explicit natural number n, a finite set H : Finset (Fin n → ZMod 3), a point p : Fin n → ZMod 3, and an offset vector ε : Fin n →…
  • ternary_affine_hyperplane_cardFor every natural number $n \ge 1$, every vector $a \in (\mathbb{Z}/3\mathbb{Z})^n$ with all non-zero coordinates, and every…

Read back from the Lean

For any natural number $n$ such that $1 \le n$, any vector $a : \mathrm{Fin}\ n \to \mathbb{Z}/3\mathbb{Z}$ such that $a(i) \ne 0$ for all $i$, any scalar $b \in \mathbb{Z}/3\mathbb{Z}$, any point $p : \mathrm{Fin}\ n \to \mathbb{Z}/3\mathbb{Z}$ belonging to the ternary affine hyperplane defined by $a$ and $b$, and any vector $\varepsilon : \mathrm{Fin}\ n \to \mathbb{Z}/3\mathbb{Z}$ such that $\varepsilon(i) \ne 0$ for all $i$: the cardinality of the ternary single-point repair of the hyperplane at $p$ with perturbation vector $\varepsilon$ equals $3^{n - 1} + 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 single-point repair of the ternary affine hyperplane H replaces the point p ∈ H with the n points obtained by modifying each coordinate p_i to p_i + ε_i. Each such modification changes the defining linear sum by a_i * ε_i ≠ 0, so none of the n perturbed points lie in H, and distinct coordinates produce distinct points by injectivity. Consequently, the set of perturbed points has size n and is disjoint from H \ {p}, giving total cardinality |H \ {p}| + n = (3^(n - 1) - 1) + n = 3^(n - 1) + n - 1.

  1. Updating p at coordinate i by adding ε i changes the linear combination ∑ j, a j * x j by adding a i * ε i.

    Split both sums by separating the term at index i from the terms at indices j ≠ i using add_sum_erase and mem_univ. For j ≠ i, the updated vector agrees with p by Function.update_of_ne, so the sums over univ.erase i coincide by sum_congr and mem_erase.mp. At index i, the updated value is p i + ε i by Function.update_self. Combining these representations and simplifying with ring arithmetic yields the identity.

    lines 3–18

    uses add_sum_erase, mem_univ, sum_congr, mem_erase.mp, Function.update_of_ne, Function.update_self

      open Finset in
      have sum_update (i : Fin n) :
          (∑ j, a j * Function.update p i (p i + ε i) j) = (∑ j, a j * p j) + a i * ε i := by
        have h1 : (∑ j, a j * Function.update p i (p i + ε i) j) =
            a i * Function.update p i (p i + ε i) i + ∑ j ∈ univ.erase i, a j * Function.update p i (p i + ε i) j := by
          rw [← add_sum_erase univ (fun j => a j * Function.update p i (p i + ε i) j) (mem_univ i)]
        have h2 : (∑ j, a j * p j) = a i * p i + ∑ j ∈ univ.erase i, a j * p j := by
          rw [← add_sum_erase univ (fun j => a j * p j) (mem_univ i)]
        have h3 : (∑ j ∈ univ.erase i, a j * Function.update p i (p i + ε i) j) =
            ∑ j ∈ univ.erase i, a j * p j := by
          apply sum_congr rfl
          intro j hj
          have hj' : j ≠ i := mem_erase.mp hj |>.1
          rw [Function.update_of_ne hj']
        rw [h1, h2, h3, Function.update_self]
        ring
  2. For each coordinate i, the perturbed point p[i ↦ p i + ε i] does not belong to the hyperplane ternary_affine_hyperplane n a b.

    Suppose for contradiction that the perturbed point belongs to the hyperplane. By Finset.mem_filter, its linear evaluation equals b. Applying the previously proved sum_update identity and using that p lies in the hyperplane gives b + a i * ε i = b, which implies a i * ε i = 0. Since ℤ/3ℤ has no zero divisors (mul_eq_zero.mp), either a i = 0 or ε i = 0, contradicting the assumptions that both a and ε have non-zero coordinates.

    lines 20–34

    uses Finset.mem_filter, mul_eq_zero.mp

      have h_not_mem (i : Fin n) : Function.update p i (p i + ε i) ∉ ternary_affine_hyperplane n a b := by
        intro hmem
        rw [ternary_affine_hyperplane, Finset.mem_filter] at hmem hp
        have hmem' := hmem.2
        have hp' := hp.2
        rw [sum_update i] at hmem'
        rw [hp'] at hmem'
        have hzero : a i * ε i = 0 := by
          apply_fun (· - b) at hmem'
          ring_nf at hmem'
          exact hmem'
        cases mul_eq_zero.mp hzero with
        | inl ha0 => exact ha i ha0
        | inr hε0 => exact hε i hε0
    
  3. The coordinate perturbation map i ↦ p[i ↦ p i + ε i] is injective.

    Suppose two indices i and j produce the same perturbed point. If i ≠ j, evaluating both sides at index i via congr_fun gives p i + ε i on the left (by Function.update_self) and p i on the right (by Function.update_of_ne). Subtracting p i gives ε i = 0, contradicting the assumption that all coordinates of ε are non-zero. Hence i = j.

    lines 35–47

    uses congr_fun, Function.update_self, Function.update_of_ne

      have hinj : Function.Injective (fun i => Function.update p i (p i + ε i)) := by
        intro i j h
        by_contra hij
        dsimp only at h
        have h1 := congr_fun h i
        rw [Function.update_self] at h1
        rw [Function.update_of_ne hij] at h1
        have : ε i = 0 := by
          apply_fun (· - p i) at h1
          ring_nf at h1
          exact h1
        exact hε i this
    
  4. The set (ternary_affine_hyperplane n a b).erase p and the set of perturbed points are disjoint.

    By Finset.disjoint_right, it suffices to show that no point in the image of the perturbation map belongs to the hyperplane with p removed. Any element in the image has the form p[i ↦ p i + ε i] by Finset.mem_image. If it were in (ternary_affine_hyperplane n a b).erase p, then by Finset.mem_of_mem_erase it would belong to ternary_affine_hyperplane n a b, contradicting the earlier fact that no perturbed point belongs to the hyperplane.

    lines 48–58

    uses Finset.disjoint_right, Finset.mem_image, Finset.mem_of_mem_erase

      have hdisj : Disjoint ((ternary_affine_hyperplane n a b).erase p)
          (Finset.image (fun i => Function.update p i (p i + ε i)) Finset.univ) := by
        rw [Finset.disjoint_right]
        intro x hx
        rw [Finset.mem_image] at hx
        rcases hx with ⟨i, -, rfl⟩
        intro hx'
        have hx'' : Function.update p i (p i + ε i) ∈ ternary_affine_hyperplane n a b :=
          Finset.mem_of_mem_erase hx'
        exact h_not_mem i hx''
    
  5. The hyperplane with p removed has cardinality 3^(n - 1) - 1, and the set of perturbed points has cardinality n.

    By ternary_affine_hyperplane_card, the hyperplane has cardinality 3^(n - 1). Since p belongs to the hyperplane, removing p gives cardinality 3^(n - 1) - 1 by Finset.card_erase_of_mem. Furthermore, because the perturbation map is injective, the image on the universal set Finset.univ has cardinality equal to |Fin n| = n by Finset.card_image_of_injective, Finset.card_univ, and Fintype.card_fin.

    lines 59–67

    uses ternary_affine_hyperplane_card, Finset.card_erase_of_mem, Finset.card_image_of_injective, Finset.card_univ, Fintype.card_fin

      have hcard_H : (ternary_affine_hyperplane n a b).card = 3 ^ (n - 1) :=
        ternary_affine_hyperplane_card n hn a ha b
    
      have hcard_erase : ((ternary_affine_hyperplane n a b).erase p).card = 3 ^ (n - 1) - 1 := by
        rw [Finset.card_erase_of_mem hp, hcard_H]
    
      have hcard_image : (Finset.image (fun i => Function.update p i (p i + ε i)) Finset.univ).card = n := by
        rw [Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin]
    
  6. The cardinality of the single-point repair of the hyperplane is 3^(n - 1) + n - 1. automation

    Unfolding the definition of single-point repair as the union of the erased hyperplane and the image of the perturbation map, its cardinality is the sum of their cardinalities (3^(n - 1) - 1) + n by Finset.card_union_of_disjoint. Since 1 ≤ 3^(n - 1) by Nat.one_le_pow, linear arithmetic over ℕ (omega) simplifies (3^(n - 1) - 1) + n to 3^(n - 1) + n - 1.

    lines 68–72

    uses Finset.card_union_of_disjoint, Nat.one_le_pow

      change ((ternary_affine_hyperplane n a b).erase p ∪
          Finset.image (fun i => Function.update p i (p i + ε i)) Finset.univ).card = 3 ^ (n - 1) + n - 1
      rw [Finset.card_union_of_disjoint hdisj, hcard_erase, hcard_image]
      have : 1 ≤ 3 ^ (n - 1) := Nat.one_le_pow (n - 1) 3 (by decide)
      omega
add_sum_erase
A sum over a finite set equals the value at a chosen element plus the sum over the remaining elements.
mem_univ
Every element of a finite type belongs to its universal set.
sum_congr
Two sums over equal sets are equal if their terms agree elementwise.
mem_erase.mp
An element in a set with a point removed is distinct from that point and belongs to the original set.
Function.update_of_ne
Updating a function at a point does not change its value at any distinct point.
Function.update_self
Updating a function at a point yields the newly assigned value at that point.
Finset.mem_filter
An element is in a filtered set if and only if it belongs to the base set and satisfies the predicate.
mul_eq_zero.mp
In a ring without zero divisors, if a product is zero, then at least one of the factors is zero.
congr_fun
Equal functions take equal values on every input.
Finset.disjoint_right
Two finite sets are disjoint if no element of the second set belongs to the first.
Finset.mem_image
An element is in the image of a function on a finite set if and only if it is the value of the function at some element of the set.
Finset.mem_of_mem_erase
Erasing an element from a set yields a subset of the original set.
ternary_affine_hyperplane_card
An affine hyperplane in (ℤ/3ℤ)ⁿ defined by a linear form with all non-zero coefficients has cardinality 3^(n - 1).
Finset.card_erase_of_mem
Erasing an element from a finite set containing it reduces the cardinality by 1.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the original set.
Finset.card_univ
The cardinality of the universal set of a finite type equals the cardinality of the type.
Fintype.card_fin
The type Fin n has cardinality n.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Nat.one_le_pow
Any positive natural number raised to any natural power is at least 1.

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

/-- The single-point repair of an affine hyperplane has size 3^(n-1) + n - 1. -/theorem ternary_single_point_repair_card (n : ℕ) (hn : 1 ≤ n) (a : Fin n → ZMod 3) (ha : ∀ i, a i ≠ 0) (b : ZMod 3) (p : Fin n → ZMod 3) (hp : p ∈ ternary_affine_hyperplane n a b) (ε : Fin n → ZMod 3) (hε : ∀ i, ε i ≠ 0) : (ternary_single_point_repair n (ternary_affine_hyperplane n a b) p ε).card = 3 ^ (n - 1) + n - 1 := by  open Finset in  have sum_update (i : Fin n) :      (∑ j, a j * Function.update p i (p i + ε i) j) = (∑ j, a j * p j) + a i * ε i := by    have h1 : (∑ j, a j * Function.update p i (p i + ε i) j) =        a i * Function.update p i (p i + ε i) i + ∑ j ∈ univ.erase i, a j * Function.update p i (p i + ε i) j := by      rw [← add_sum_erase univ (fun j => a j * Function.update p i (p i + ε i) j) (mem_univ i)]    have h2 : (∑ j, a j * p j) = a i * p i + ∑ j ∈ univ.erase i, a j * p j := by      rw [← add_sum_erase univ (fun j => a j * p j) (mem_univ i)]    have h3 : (∑ j ∈ univ.erase i, a j * Function.update p i (p i + ε i) j) =        ∑ j ∈ univ.erase i, a j * p j := by      apply sum_congr rfl      intro j hj      have hj' : j ≠ i := mem_erase.mp hj |>.1      rw [Function.update_of_ne hj']    rw [h1, h2, h3, Function.update_self]    ring  have h_not_mem (i : Fin n) : Function.update p i (p i + ε i) ∉ ternary_affine_hyperplane n a b := by    intro hmem    rw [ternary_affine_hyperplane, Finset.mem_filter] at hmem hp    have hmem' := hmem.2    have hp' := hp.2    rw [sum_update i] at hmem'    rw [hp'] at hmem'    have hzero : a i * ε i = 0 := by      apply_fun (· - b) at hmem'      ring_nf at hmem'      exact hmem'    cases mul_eq_zero.mp hzero with    | inl ha0 => exact ha i ha0    | inr hε0 => exact hε i hε0  have hinj : Function.Injective (fun i => Function.update p i (p i + ε i)) := by    intro i j h    by_contra hij    dsimp only at h    have h1 := congr_fun h i    rw [Function.update_self] at h1    rw [Function.update_of_ne hij] at h1    have : ε i = 0 := by      apply_fun (· - p i) at h1      ring_nf at h1      exact h1    exact hε i this  have hdisj : Disjoint ((ternary_affine_hyperplane n a b).erase p)      (Finset.image (fun i => Function.update p i (p i + ε i)) Finset.univ) := by    rw [Finset.disjoint_right]    intro x hx    rw [Finset.mem_image] at hx    rcases hx with ⟨i, -, rfl⟩    intro hx'    have hx'' : Function.update p i (p i + ε i) ∈ ternary_affine_hyperplane n a b :=      Finset.mem_of_mem_erase hx'    exact h_not_mem i hx''  have hcard_H : (ternary_affine_hyperplane n a b).card = 3 ^ (n - 1) :=    ternary_affine_hyperplane_card n hn a ha b  have hcard_erase : ((ternary_affine_hyperplane n a b).erase p).card = 3 ^ (n - 1) - 1 := by    rw [Finset.card_erase_of_mem hp, hcard_H]  have hcard_image : (Finset.image (fun i => Function.update p i (p i + ε i)) Finset.univ).card = n := by    rw [Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin]  change ((ternary_affine_hyperplane n a b).erase p ∪      Finset.image (fun i => Function.update p i (p i + ε i)) Finset.univ).card = 3 ^ (n - 1) + n - 1  rw [Finset.card_union_of_disjoint hdisj, hcard_erase, hcard_image]  have : 1 ≤ 3 ^ (n - 1) := Nat.one_le_pow (n - 1) 3 (by decide)  omega
See it in the graphDiscuss this resultChallenge it