ternary_single_point_repair_card
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.
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.
uses
add_sum_erase,mem_univ,sum_congr,mem_erase.mp,Function.update_of_ne,Function.update_selfopen 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
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.
uses
Finset.mem_filter,mul_eq_zero.mphave 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
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.
uses
congr_fun,Function.update_self,Function.update_of_nehave 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
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.
uses
Finset.disjoint_right,Finset.mem_image,Finset.mem_of_mem_erasehave 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''
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.
uses
ternary_affine_hyperplane_card,Finset.card_erase_of_mem,Finset.card_image_of_injective,Finset.card_univ,Fintype.card_finhave 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]
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.
uses
Finset.card_union_of_disjoint,Nat.one_le_powchange ((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
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.
/-- 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