ternary_single_point_repair_is_minimal_line_cover
For every explicit integer n ≥ 3, 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 ε is an inclusion-minimal ternary line cover.
Statement
theorem ternary_single_point_repair_is_minimal_line_cover (n : ℕ) (hn : 3 ≤ 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) : is_minimal_ternary_line_cover n (ternary_single_point_repair n (ternary_affine_hyperplane n a b) p ε)- Formalizes
- arXiv:2610.32789, Section 3.1
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- 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 →…
- 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 3$, any vector $a \in (\mathbb{Z}/3\mathbb{Z})^n$ with all entries nonzero, any scalar $b \in \mathbb{Z}/3\mathbb{Z}$, any point $p$ in the affine hyperplane $H = \{x \in (\mathbb{Z}/3\mathbb{Z})^n \mid \sum_{i} a_i x_i = b\}$, and any vector $\varepsilon \in (\mathbb{Z}/3\mathbb{Z})^n$ with all entries nonzero: The set obtained by removing $p$ from $H$ and adding the $n$ points $\{p + \varepsilon_i e_i \mid i \in \text{Fin } n\}$ is an inclusion-minimal ternary axis-parallel line cover of $(\mathbb{Z}/3\mathbb{Z})^n$ (that is, every axis-parallel line intersects the set, and no proper subset has this property).
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 establishes that repairing an affine hyperplane H at a single point p by removing p and adding one point p + εⱼ eⱼ in each coordinate direction j yields an inclusion-minimal ternary line cover when n ≥ 3. To cover any axis-parallel line, we take its unique intersection with H; if that intersection is p, the line is instead covered by the corresponding repair point. For minimality, if a subcover B' ⊆ B omits a point x ∈ H \\ {p}, the assumption n ≥ 3 provides a coordinate direction where the line through x cannot meet any repair point, forcing x ∈ B'. Similarly, omitting any repair point leaves the line through p in that direction uncovered because the hyperplane contains no other points on that line.
Define the hyperplane H and repair set B, noting that the pivot point p lies in H.
We introduce abbreviations H for the affine hyperplane ternary_affine_hyperplane n a b and B for its single-point repair ternary_single_point_repair n H p ε, and record that p ∈ H.
set H := ternary_affine_hyperplane n a b with hH set B := ternary_single_point_repair n H p ε with hB have hp' : p ∈ H := by rw [hH]; exact hp
Evaluating the linear form on c updated at index i to value t splits into the sum over indices j ≠ i plus aᵢ * t.
Using Finset.sum_erase_add, we separate the i-th term from the total sum. For j ≠ i the updated vector evaluates to c j by Function.update_of_ne, while at index i it evaluates to t by Function.update_self.
uses
Finset.sum_erase_add,Finset.mem_univ,Finset.sum_congr,Function.update_of_ne,Finset.ne_of_mem_erase,Function.update_selfhave hsum : ∀ (c : Fin n → ZMod 3) (i : Fin n) (t : ZMod 3), ∑ j, a j * Function.update c i t j = (∑ j ∈ Finset.univ.erase i, a j * c j) + a i * t := by intro c i t rw [← Finset.sum_erase_add Finset.univ (fun j => a j * Function.update c i t j) (Finset.mem_univ i)] congr 1 · exact Finset.sum_congr rfl fun j hj => by rw [Function.update_of_ne (Finset.ne_of_mem_erase hj)] · rw [Function.update_self]
A point x belongs to H if and only if ∑ aⱼ xⱼ = b.
This unfolds the definition of ternary_affine_hyperplane.
uses
ternary_affine_hyperplanehave hmemH : ∀ x : Fin n → ZMod 3, x ∈ H ↔ ∑ j, a j * x j = b := by intro x; rw [hH]; simp [ternary_affine_hyperplane]
A point x belongs to B if and only if x ∈ H \\ {p} or x = p[j ↦ pⱼ + εⱼ] for some index j.
Unfolding B into the union (H \\ {p}) ∪ {p[j ↦ pⱼ + εⱼ] | j ∈ Fin n}, membership in B is characterized by the disjunction of belonging to H \\ {p} or being one of the n repaired points.
uses
Finset.mem_union,Finset.mem_erase,Finset.mem_image,Finset.mem_univ,true_andhave hBunf : B = H.erase p ∪ Finset.image (fun j => Function.update p j (p j + ε j)) Finset.univ := by rw [hB, hH]; rfl have hmemB : ∀ x : Fin n → ZMod 3, x ∈ B ↔ (x ∈ H ∧ x ≠ p) ∨ ∃ j, Function.update p j (p j + ε j) = x := by intro x rw [hBunf, Finset.mem_union, Finset.mem_erase, Finset.mem_image] simp only [Finset.mem_univ, true_and] tauto
Two points in H that agree on all coordinates except possibly coordinate i are identical.
If x, y ∈ H agree on all k ≠ i, their partial sums over indices distinct from i are equal. Since both points satisfy the hyperplane equation, canceling the common partial sum leaves aᵢ * xᵢ = aᵢ * yᵢ. Because aᵢ ≠ 0 in the field ℤ/3ℤ, we can cancel aᵢ using mul_left_cancel₀ to conclude xᵢ = yᵢ, hence x = y everywhere.
uses
Function.update_eq_self,Finset.sum_congr,Finset.ne_of_mem_erase,mul_left_cancel₀,add_left_cancelhave hagree : ∀ (i : Fin n) (x y : Fin n → ZMod 3), x ∈ H → y ∈ H → (∀ k, k ≠ i → x k = y k) → x = y := by intro i x y hx hy hag rw [hmemH] at hx hy have hx' := hsum x i (x i) simp only [Function.update_eq_self] at hx' have hy' := hsum y i (y i) simp only [Function.update_eq_self] at hy' have hS : ∑ j ∈ Finset.univ.erase i, a j * x j = ∑ j ∈ Finset.univ.erase i, a j * y j := Finset.sum_congr rfl fun j hj => by rw [hag j (Finset.ne_of_mem_erase hj)] have heq : (∑ j ∈ Finset.univ.erase i, a j * x j) + a i * x i = (∑ j ∈ Finset.univ.erase i, a j * y j) + a i * y i := by rw [← hx', ← hy', hx, hy] rw [hS] at heq have h4 : x i = y i := mul_left_cancel₀ (ha i) (add_left_cancel heq) funext k by_cases hk : k = i · subst hk; exact h4 · exact hag k hk
No repair point p[j ↦ pⱼ + εⱼ] belongs to the hyperplane H.
If a repair point were in H, evaluating the linear form would give ∑_{k ≠ j} aₖ pₖ + aⱼ(pⱼ + εⱼ) = b. But p ∈ H satisfies ∑_{k ≠ j} aₖ pₖ + aⱼ pⱼ = b. Subtracting the common terms yields aⱼ * εⱼ = 0. Since both aⱼ ≠ 0 and εⱼ ≠ 0 in ℤ/3ℤ, this is a contradiction.
uses
Function.update_eq_self,add_left_cancel,mul_add,add_zero,mul_eq_zero.mphave hP_notMem : ∀ j, Function.update p j (p j + ε j) ∉ H := by intro j hmem rw [hmemH] at hmem rw [hsum] at hmem have hpS : (∑ k ∈ Finset.univ.erase j, a k * p k) + a j * p j = b := by have h := hsum p j (p j) simp only [Function.update_eq_self] at h rw [← h] exact (hmemH p).mp hp' have h2 : a j * (p j + ε j) = a j * p j := add_left_cancel (hmem.trans hpS.symm) rw [mul_add] at h2 have h3 : a j * ε j = 0 := by have h4 : a j * p j + a j * ε j = a j * p j + 0 := by rw [add_zero]; exact h2 exact add_left_cancel h4 rcases mul_eq_zero.mp h3 with h0 | h0 · exact ha j h0 · exact hε j h0
The repair points are distinct from p, uniquely determined by their index, and cannot lie on a line through p in a different coordinate direction.
Each repair point is distinct from p because p ∈ H while repair points do not lie in H. If two repair points with indices j ≠ j' were equal, evaluating at coordinate j would force εⱼ = 0, a contradiction. Similarly, if a point p[i ↦ t] on the i-th axis-parallel line through p coincided with the j-th repair point for j ≠ i, inspecting coordinate j would yield εⱼ = 0.
uses
congr_fun,Function.update_self,Function.update_of_ne,add_zero,add_left_cancelhave hP_ne_p : ∀ j, Function.update p j (p j + ε j) ≠ p := by intro j h exact hP_notMem j (h.symm ▸ hp') have hP_inj : ∀ j j', Function.update p j (p j + ε j) = Function.update p j' (p j' + ε j') → j = j' := by intro j j' h by_contra hne have h1 := congr_fun h j rw [Function.update_self, Function.update_of_ne hne] at h1 have h2 : p j + ε j = p j + 0 := by rw [add_zero]; exact h1 exact hε j (add_left_cancel h2) have hP_notOnPline : ∀ (i j : Fin n), j ≠ i → ∀ t : ZMod 3, Function.update p i t ≠ Function.update p j (p j + ε j) := by intro i j hji t h have h1 := congr_fun h j rw [Function.update_of_ne hji, Function.update_self] at h1 have h2 : p j + ε j = p j + 0 := by rw [add_zero]; exact h1.symm exact hε j (add_left_cancel h2)
If updating x ∈ H \\ {p} at coordinate i yields the repair point p[j ↦ pⱼ + εⱼ], then j ≠ i, x differs from p at both i and j, and x matches p everywhere else.
For any coordinate k distinct from both i and j, evaluating both sides shows xₖ = pₖ. If j = i, then x would agree with p outside i, forcing x = p by our agreement lemma, contradicting x ≠ p; thus j ≠ i. If xᵢ = pᵢ, then x would agree with p outside j, again forcing x = p; thus xᵢ ≠ pᵢ. Finally, at coordinate j (which is not i), the left side is xⱼ and the right is pⱼ + εⱼ; if xⱼ = pⱼ, we would have εⱼ = 0, so xⱼ ≠ pⱼ.
uses
congr_fun,Function.update_of_ne,Function.update_self,add_zero,add_left_cancelhave hkey : ∀ (x : Fin n → ZMod 3) (i : Fin n) (t : ZMod 3) (j : Fin n), x ∈ H → x ≠ p → Function.update x i t = Function.update p j (p j + ε j) → j ≠ i ∧ x i ≠ p i ∧ x j ≠ p j ∧ ∀ k, k ≠ i → k ≠ j → x k = p k := by intro x i t j hx hxp h have hoff : ∀ k, k ≠ i → k ≠ j → x k = p k := by intro k hki hkj have h1 := congr_fun h k rw [Function.update_of_ne hki, Function.update_of_ne hkj] at h1 exact h1 have hji : j ≠ i := by intro h_eq exact hxp (hagree i x p hx hp' (fun k hk => hoff k hk (h_eq.symm ▸ hk))) have hxi : x i ≠ p i := by intro h_eq refine hxp (hagree j x p hx hp' (fun k hk => ?_)) by_cases hki : k = i · rw [hki]; exact h_eq · exact hoff k hki hk have hxj : x j ≠ p j := by have h1 := congr_fun h j rw [Function.update_of_ne hji, Function.update_self] at h1 intro h_eq have h3 : p j = p j + ε j := h_eq.symm.trans h1 have h4 : p j + 0 = p j + ε j := by rw [add_zero]; exact h3 have h5 : (0 : ZMod 3) = ε j := add_left_cancel h4 exact hε j h5.symm exact ⟨hji, hxi, hxj, hoff⟩
For any two coordinate indices i and j, there exists a third index k distinct from both.
Since n ≥ 3, the universe Fin n has cardinality at least 3, whereas the pair {i, j} has cardinality at most 2. By cardinality comparison, the universe cannot be a subset of {i, j}, so there exists some index k outside it.
uses
Finset.card_le_card,Finset.card_univ,Fintype.card_finhave hexists_ne_two : ∀ i j : Fin n, ∃ k : Fin n, k ≠ i ∧ k ≠ j := by intro i j by_contra h have hsub : (Finset.univ : Finset (Fin n)) ⊆ {i, j} := by intro k _ by_cases hki : k = i · simp [hki] · have hkj : k = j := by by_contra hkj exact h ⟨k, hki, hkj⟩ simp [hkj] have hc := Finset.card_le_card hsub rw [Finset.card_univ, Fintype.card_fin] at hc have h2 : ({i, j} : Finset (Fin n)).card ≤ 2 := by by_cases hij : i = j · simp [hij] · simp [hij] omega
The set B is a ternary line cover.
Given any direction i and base point c, the axis-parallel line through c meets the hyperplane H at a unique scalar t₀ = aᵢ⁻¹ * (b - ∑_{j ≠ i} aⱼ cⱼ) because aᵢ ≠ 0. If the intersection point c[i ↦ t₀] is not p, it belongs to H \\ {p} ⊆ B. If it equals p, then c agrees with p on all other coordinates and c[i ↦ pᵢ + εᵢ] is the i-th repair point p[i ↦ pᵢ + εᵢ], which belongs to B.
uses
mul_assoc,mul_inv_cancel₀,one_mul,Function.update_self,Function.update_of_ne,congr_fun,Or.inr,Or.inlhave hcover : is_ternary_line_cover n B := by intro i c obtain ⟨t₀, ht₀⟩ : ∃ t, Function.update c i t ∈ H := by refine ⟨(a i)⁻¹ * (b - ∑ j ∈ Finset.univ.erase i, a j * c j), ?_⟩ rw [hmemH, hsum, ← mul_assoc, mul_inv_cancel₀ (ha i), one_mul] ring by_cases hpc : Function.update c i t₀ = p · refine ⟨p i + ε i, ?_⟩ have heq : Function.update c i (p i + ε i) = Function.update p i (p i + ε i) := by funext k by_cases hk : k = i · rw [hk, Function.update_self, Function.update_self] · rw [Function.update_of_ne hk, Function.update_of_ne hk] have := congr_fun hpc k rw [Function.update_of_ne hk] at this exact this rw [heq, hmemB] exact Or.inr ⟨i, rfl⟩ · refine ⟨t₀, ?_⟩ rw [hmemB] exact Or.inl ⟨ht₀, hpc⟩
To prove inclusion-minimality, it suffices to show that any subcover B' ⊆ B contains every point of B.
By definition of minimal line cover, we assume B' ⊆ B is also a line cover. To establish B' = B via Finset.Subset.antisymm, it suffices to show B ⊆ B'. We take an arbitrary x ∈ B and split into two cases: x ∈ H \\ {p} or x is a repair point.
uses
Finset.Subset.antisymmrefine ⟨hcover, ?_⟩ intro B' hB'sub hB'cover apply Finset.Subset.antisymm hB'sub intro x hx rw [hmemB] at hx rcases hx with ⟨hxH, hxp⟩ | ⟨j, rfl⟩
Every point x ∈ H \\ {p} must belong to B'.
Since x ≠ p, x differs from p at some coordinate i₀. Since B' is a line cover, the line through x in direction i₀ meets B' at some point x[i₀ ↦ t₁] ∈ B. If this point lies in H \\ {p}, it agrees with x off i₀, so by the agreement lemma it equals x, proving x ∈ B'. If it is a repair point with index j₁, our key structural lemma shows j₁ ≠ i₀ and x agrees with p outside {i₀, j₁}. Because n ≥ 3, we pick a third coordinate k ∉ {i₀, j₁} and test the line through x in direction k. That line also meets B' at some x[k ↦ t₂]. If that point is in H, it again equals x; if it were another repair point with index j₂, the structural lemma would force j₂ = i₀ and j₂ = j₁, contradicting j₁ ≠ i₀. Thus x ∈ B'.
uses
Function.update_of_ne,Ne.symm· obtain ⟨i₀, hi₀⟩ : ∃ k, x k ≠ p k := by by_contra h exact hxp (funext fun k => by by_contra hk; exact h ⟨k, hk⟩) obtain ⟨t₁, ht₁⟩ := hB'cover i₀ x have h1B : Function.update x i₀ t₁ ∈ B := hB'sub ht₁ rw [hmemB] at h1B rcases h1B with ⟨hH1, _⟩ | ⟨j₁, hj₁⟩ · have heq : Function.update x i₀ t₁ = x := hagree i₀ _ x hH1 hxH (fun k hk => by rw [Function.update_of_ne hk]) rwa [heq] at ht₁ · obtain ⟨hji, _, hxj, hoff⟩ := hkey x i₀ t₁ j₁ hxH hxp hj₁.symm obtain ⟨k, hk1, hk2⟩ := hexists_ne_two i₀ j₁ obtain ⟨t₂, ht₂⟩ := hB'cover k x have h2B : Function.update x k t₂ ∈ B := hB'sub ht₂ rw [hmemB] at h2B rcases h2B with ⟨hH2, _⟩ | ⟨j₂, hj₂⟩ · have heq : Function.update x k t₂ = x := hagree k _ x hH2 hxH (fun m hm => by rw [Function.update_of_ne hm]) rwa [heq] at ht₂ · obtain ⟨_, _, _, hoff₂⟩ := hkey x k t₂ j₂ hxH hxp hj₂.symm have e1 : j₂ = i₀ := by by_contra hne exact hi₀ (hoff₂ i₀ hk1.symm (Ne.symm hne)) have e2 : j₂ = j₁ := by by_contra hne exact hxj (hoff₂ j₁ hk2.symm (Ne.symm hne)) exact absurd (e2.symm.trans e1) hji
Every repair point p[j ↦ pⱼ + εⱼ] must belong to B'.
Consider the line passing through p in direction j. Because B' covers this line, it contains a point p[j ↦ t] ∈ B' ⊆ B. It cannot belong to H \\ {p}, because agreeing with p off j would force it to equal p by the agreement lemma. Therefore it must be a repair point p[j' ↦ p_{j'} + ε_{j'}]. Because no point on the j-th line through p can coincide with a repair point of index j' ≠ j, we must have j' = j, meaning p[j ↦ t] is exactly the repair point p[j ↦ pⱼ + εⱼ]. Thus this point belongs to B'.
uses
Function.update_of_ne· obtain ⟨t, ht⟩ := hB'cover j p have h1B : Function.update p j t ∈ B := hB'sub ht rw [hmemB] at h1B rcases h1B with ⟨hH, hne⟩ | ⟨j', hj'⟩ · have heq : Function.update p j t = p := hagree j _ p hH hp' (fun k hk => by rw [Function.update_of_ne hk]) exact absurd heq hne · have hjj : j' = j := by by_contra hne exact hP_notOnPline j j' hne t hj'.symm rw [hjj] at hj' rw [hj'] exact ht
add_left_cancel- In an additive structure with left cancellation, a + b = a + c implies b = c.
add_zero- Adding zero on the right leaves an element unchanged: a + 0 = a.
congr_fun- Equal functions evaluate to equal values on any input: if f = g then f(a) = g(a).
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most that of t.
Finset.card_univ- The cardinality of the universal finset on a finite type equals the cardinality of the type.
Finset.mem_erase- An element belongs to s \\ {b} if and only if it is not equal to b and belongs to s.
Finset.mem_image- An element b belongs to the image f(s) if and only if b = f(a) for some a ∈ s.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.ne_of_mem_erase- An element in s \\ {a} cannot equal a.
Finset.Subset.antisymm- Two finite sets that are subsets of each other are equal.
Finset.sum_congr- If two finsets are equal and two summands agree on every element, their sums are equal.
Finset.sum_erase_add- For a finite set s and an element a ∈ s, the sum over s of f equals the sum over s \\ {a} plus f(a).
Fintype.card_fin- The cardinality of Fin n is n.
Function.update_eq_self- Updating a function at a with its existing value f(a) does not change the function.
Function.update_of_ne- Evaluating an updated function at a point different from the update location yields the original value.
Function.update_self- Evaluating an updated function at the update location yields the newly assigned value.
mul_add- Left distributivity of multiplication over addition: a * (b + c) = a * b + a * c.
mul_assoc- Associativity of multiplication: (a * b) * c = a * (b * c).
mul_eq_zero.mp- If a product is zero in a domain, at least one of the factors is zero.
mul_left_cancel₀- In a structure with cancellation of nonzero elements, if a ≠ 0 and a * b = a * c, then b = c.
mul_inv_cancel₀- A nonzero element in a group with zero multiplies with its inverse to yield 1: a * a⁻¹ = 1.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
one_mul- Multiplying by 1 on the left leaves an element unchanged: 1 * a = a.
Or.inr- Right injection for disjunction: if b holds, then a ∨ b holds.
Or.inl- Left injection for disjunction: if a holds, then a ∨ b holds.
ternary_affine_hyperplane- The affine hyperplane {x ∈ (ℤ/3ℤ)ⁿ | ∑ aᵢ xᵢ = b}.
true_and- The logical simplification (True ∧ p) ↔ p.
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.
/-- Every single-point repair of an affine hyperplane is an inclusion-minimal line cover for n ≥ 3. -/theorem ternary_single_point_repair_is_minimal_line_cover (n : ℕ) (hn : 3 ≤ 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) : is_minimal_ternary_line_cover n (ternary_single_point_repair n (ternary_affine_hyperplane n a b) p ε) := by set H := ternary_affine_hyperplane n a b with hH set B := ternary_single_point_repair n H p ε with hB have hp' : p ∈ H := by rw [hH]; exact hp have hsum : ∀ (c : Fin n → ZMod 3) (i : Fin n) (t : ZMod 3), ∑ j, a j * Function.update c i t j = (∑ j ∈ Finset.univ.erase i, a j * c j) + a i * t := by intro c i t rw [← Finset.sum_erase_add Finset.univ (fun j => a j * Function.update c i t j) (Finset.mem_univ i)] congr 1 · exact Finset.sum_congr rfl fun j hj => by rw [Function.update_of_ne (Finset.ne_of_mem_erase hj)] · rw [Function.update_self] have hmemH : ∀ x : Fin n → ZMod 3, x ∈ H ↔ ∑ j, a j * x j = b := by intro x; rw [hH]; simp [ternary_affine_hyperplane] have hBunf : B = H.erase p ∪ Finset.image (fun j => Function.update p j (p j + ε j)) Finset.univ := by rw [hB, hH]; rfl have hmemB : ∀ x : Fin n → ZMod 3, x ∈ B ↔ (x ∈ H ∧ x ≠ p) ∨ ∃ j, Function.update p j (p j + ε j) = x := by intro x rw [hBunf, Finset.mem_union, Finset.mem_erase, Finset.mem_image] simp only [Finset.mem_univ, true_and] tauto have hagree : ∀ (i : Fin n) (x y : Fin n → ZMod 3), x ∈ H → y ∈ H → (∀ k, k ≠ i → x k = y k) → x = y := by intro i x y hx hy hag rw [hmemH] at hx hy have hx' := hsum x i (x i) simp only [Function.update_eq_self] at hx' have hy' := hsum y i (y i) simp only [Function.update_eq_self] at hy' have hS : ∑ j ∈ Finset.univ.erase i, a j * x j = ∑ j ∈ Finset.univ.erase i, a j * y j := Finset.sum_congr rfl fun j hj => by rw [hag j (Finset.ne_of_mem_erase hj)] have heq : (∑ j ∈ Finset.univ.erase i, a j * x j) + a i * x i = (∑ j ∈ Finset.univ.erase i, a j * y j) + a i * y i := by rw [← hx', ← hy', hx, hy] rw [hS] at heq have h4 : x i = y i := mul_left_cancel₀ (ha i) (add_left_cancel heq) funext k by_cases hk : k = i · subst hk; exact h4 · exact hag k hk have hP_notMem : ∀ j, Function.update p j (p j + ε j) ∉ H := by intro j hmem rw [hmemH] at hmem rw [hsum] at hmem have hpS : (∑ k ∈ Finset.univ.erase j, a k * p k) + a j * p j = b := by have h := hsum p j (p j) simp only [Function.update_eq_self] at h rw [← h] exact (hmemH p).mp hp' have h2 : a j * (p j + ε j) = a j * p j := add_left_cancel (hmem.trans hpS.symm) rw [mul_add] at h2 have h3 : a j * ε j = 0 := by have h4 : a j * p j + a j * ε j = a j * p j + 0 := by rw [add_zero]; exact h2 exact add_left_cancel h4 rcases mul_eq_zero.mp h3 with h0 | h0 · exact ha j h0 · exact hε j h0 have hP_ne_p : ∀ j, Function.update p j (p j + ε j) ≠ p := by intro j h exact hP_notMem j (h.symm ▸ hp') have hP_inj : ∀ j j', Function.update p j (p j + ε j) = Function.update p j' (p j' + ε j') → j = j' := by intro j j' h by_contra hne have h1 := congr_fun h j rw [Function.update_self, Function.update_of_ne hne] at h1 have h2 : p j + ε j = p j + 0 := by rw [add_zero]; exact h1 exact hε j (add_left_cancel h2) have hP_notOnPline : ∀ (i j : Fin n), j ≠ i → ∀ t : ZMod 3, Function.update p i t ≠ Function.update p j (p j + ε j) := by intro i j hji t h have h1 := congr_fun h j rw [Function.update_of_ne hji, Function.update_self] at h1 have h2 : p j + ε j = p j + 0 := by rw [add_zero]; exact h1.symm exact hε j (add_left_cancel h2) have hkey : ∀ (x : Fin n → ZMod 3) (i : Fin n) (t : ZMod 3) (j : Fin n), x ∈ H → x ≠ p → Function.update x i t = Function.update p j (p j + ε j) → j ≠ i ∧ x i ≠ p i ∧ x j ≠ p j ∧ ∀ k, k ≠ i → k ≠ j → x k = p k := by intro x i t j hx hxp h have hoff : ∀ k, k ≠ i → k ≠ j → x k = p k := by intro k hki hkj have h1 := congr_fun h k rw [Function.update_of_ne hki, Function.update_of_ne hkj] at h1 exact h1 have hji : j ≠ i := by intro h_eq exact hxp (hagree i x p hx hp' (fun k hk => hoff k hk (h_eq.symm ▸ hk))) have hxi : x i ≠ p i := by intro h_eq refine hxp (hagree j x p hx hp' (fun k hk => ?_)) by_cases hki : k = i · rw [hki]; exact h_eq · exact hoff k hki hk have hxj : x j ≠ p j := by have h1 := congr_fun h j rw [Function.update_of_ne hji, Function.update_self] at h1 intro h_eq have h3 : p j = p j + ε j := h_eq.symm.trans h1 have h4 : p j + 0 = p j + ε j := by rw [add_zero]; exact h3 have h5 : (0 : ZMod 3) = ε j := add_left_cancel h4 exact hε j h5.symm exact ⟨hji, hxi, hxj, hoff⟩ have hexists_ne_two : ∀ i j : Fin n, ∃ k : Fin n, k ≠ i ∧ k ≠ j := by intro i j by_contra h have hsub : (Finset.univ : Finset (Fin n)) ⊆ {i, j} := by intro k _ by_cases hki : k = i · simp [hki] · have hkj : k = j := by by_contra hkj exact h ⟨k, hki, hkj⟩ simp [hkj] have hc := Finset.card_le_card hsub rw [Finset.card_univ, Fintype.card_fin] at hc have h2 : ({i, j} : Finset (Fin n)).card ≤ 2 := by by_cases hij : i = j · simp [hij] · simp [hij] omega have hcover : is_ternary_line_cover n B := by intro i c obtain ⟨t₀, ht₀⟩ : ∃ t, Function.update c i t ∈ H := by refine ⟨(a i)⁻¹ * (b - ∑ j ∈ Finset.univ.erase i, a j * c j), ?_⟩ rw [hmemH, hsum, ← mul_assoc, mul_inv_cancel₀ (ha i), one_mul] ring by_cases hpc : Function.update c i t₀ = p · refine ⟨p i + ε i, ?_⟩ have heq : Function.update c i (p i + ε i) = Function.update p i (p i + ε i) := by funext k by_cases hk : k = i · rw [hk, Function.update_self, Function.update_self] · rw [Function.update_of_ne hk, Function.update_of_ne hk] have := congr_fun hpc k rw [Function.update_of_ne hk] at this exact this rw [heq, hmemB] exact Or.inr ⟨i, rfl⟩ · refine ⟨t₀, ?_⟩ rw [hmemB] exact Or.inl ⟨ht₀, hpc⟩ refine ⟨hcover, ?_⟩ intro B' hB'sub hB'cover apply Finset.Subset.antisymm hB'sub intro x hx rw [hmemB] at hx rcases hx with ⟨hxH, hxp⟩ | ⟨j, rfl⟩ · obtain ⟨i₀, hi₀⟩ : ∃ k, x k ≠ p k := by by_contra h exact hxp (funext fun k => by by_contra hk; exact h ⟨k, hk⟩) obtain ⟨t₁, ht₁⟩ := hB'cover i₀ x have h1B : Function.update x i₀ t₁ ∈ B := hB'sub ht₁ rw [hmemB] at h1B rcases h1B with ⟨hH1, _⟩ | ⟨j₁, hj₁⟩ · have heq : Function.update x i₀ t₁ = x := hagree i₀ _ x hH1 hxH (fun k hk => by rw [Function.update_of_ne hk]) rwa [heq] at ht₁ · obtain ⟨hji, _, hxj, hoff⟩ := hkey x i₀ t₁ j₁ hxH hxp hj₁.symm obtain ⟨k, hk1, hk2⟩ := hexists_ne_two i₀ j₁ obtain ⟨t₂, ht₂⟩ := hB'cover k x have h2B : Function.update x k t₂ ∈ B := hB'sub ht₂ rw [hmemB] at h2B rcases h2B with ⟨hH2, _⟩ | ⟨j₂, hj₂⟩ · have heq : Function.update x k t₂ = x := hagree k _ x hH2 hxH (fun m hm => by rw [Function.update_of_ne hm]) rwa [heq] at ht₂ · obtain ⟨_, _, _, hoff₂⟩ := hkey x k t₂ j₂ hxH hxp hj₂.symm have e1 : j₂ = i₀ := by by_contra hne exact hi₀ (hoff₂ i₀ hk1.symm (Ne.symm hne)) have e2 : j₂ = j₁ := by by_contra hne exact hxj (hoff₂ j₁ hk2.symm (Ne.symm hne)) exact absurd (e2.symm.trans e1) hji · obtain ⟨t, ht⟩ := hB'cover j p have h1B : Function.update p j t ∈ B := hB'sub ht rw [hmemB] at h1B rcases h1B with ⟨hH, hne⟩ | ⟨j', hj'⟩ · have heq : Function.update p j t = p := hagree j _ p hH hp' (fun k hk => by rw [Function.update_of_ne hk]) exact absurd heq hne · have hjj : j' = j := by by_contra hne exact hP_notOnPline j j' hne t hj'.symm rw [hjj] at hj' rw [hj'] exact ht