nowhere_zero_affine_is_constant
If an affine form x ↦ (∑ i, a i * x i) + b on (Fin m → ZMod 3) is nowhere zero, then every coefficient a i is zero.
Statement
theorem nowhere_zero_affine_is_constant (m : ℕ) (a : Fin m → ZMod 3) (b : ZMod 3) (h : ∀ x : Fin m → ZMod 3, (∑ i, a i * x i) + b ≠ 0) : ∀ i, a i = 0- Source
- step towards ternary_minimal_line_cover_minimum_card_eq_hyperplane
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- latin_hypercube_is_affineEvery order-3 Latin hypercube f : (Fin m → ZMod 3) → ZMod 3 (a function whose restriction to every 1D coordinate line is a bijection) is…
- ternary_minimal_line_cover_minimum_card_eq_hyperplaneFor every natural number n ≥ 1 and every inclusion-minimal ternary line cover B in (Fin n → ZMod 3) with cardinality 3^(n - 1), B is an…
The proof, explained
The proof proceeds by contradiction: suppose some coefficient a i is non-zero. Since ℤ/3ℤ is a field, a i has a multiplicative inverse, so we can define a test vector x that vanishes at all coordinates except i, where x i = -(a i)⁻¹ * b. Evaluating the affine form at x, the sum collapses to a single term a i * x i = -b, which cancels + b to give 0. This contradicts the assumption that the affine form is nowhere zero, so every coefficient must be zero.
Suppose for contradiction that some coefficient a i is non-zero, and define a test vector x that is zero everywhere except at coordinate i, where x i = -(a i)⁻¹ * b.
Fix an index i and assume for contradiction that a i ≠ 0. Because ℤ/3ℤ is a field, the non-zero element a i has a multiplicative inverse. We define a vector x : Fin m → ℤ/3ℤ by starting with the constant zero function and updating its value at index i to -(a i)⁻¹ * b.
intro i by_contra hi let x : Fin m → ZMod 3 := Function.update (fun _ => 0) i (-(a i)⁻¹ * b)
The linear sum ∑ j, a j * x j collapses to the single term a i * (-(a i)⁻¹ * b).
Using `Finset.sum_eq_single` at index i, the sum over all coordinates reduces to the single term at i. For every j ≠ i, x j = 0 by definition of x, so a j * x j = 0. The case where i ∉ Finset.univ is dismissed using `Finset.mem_univ`. Thus the entire sum equals a i * x i = a i * (-(a i)⁻¹ * b).
uses
Finset.sum_eq_single,Finset.mem_univhave hx : (∑ j, a j * x j) + b = 0 := by have hsum : (∑ j, a j * x j) = a i * (-(a i)⁻¹ * b) := by rw [Finset.sum_eq_single i] · simp [x] · intro j _ hj simp [x, hj] · intro hnot exact absurd (Finset.mem_univ i) hnot
The affine form evaluates to zero at x: (∑ j, a j * x j) + b = 0.
Substituting the simplified sum into the affine form, we rewrite the product a i * (-(a i)⁻¹ * b) using `neg_mul`, `mul_neg`, and `mul_assoc`. Because a i ≠ 0, `mul_inv_cancel₀` simplifies a i * (a i)⁻¹ to 1, leaving -(1 * b) + b = 0, which holds by ring arithmetic.
uses
neg_mul,mul_neg,mul_assoc,mul_inv_cancel₀rw [hsum] rw [neg_mul, mul_neg, ← mul_assoc, mul_inv_cancel₀ hi] ring
A contradiction is reached, concluding that a i = 0 for every index i.
The hypothesis h asserts that the affine form is non-zero on all inputs, but hx shows it evaluates to 0 at x. Evaluating h at x contradicts hx, completing the proof.
exact h x hx
Finset.sum_eq_single- A sum over a finite set collapses to a single term if all other terms are zero and the chosen index belongs to the set.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
neg_mul- Multiplication distributes over negation on the left: (-a) * b = -(a * b).
mul_neg- Multiplication distributes over negation on the right: a * (-b) = -(a * b).
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
mul_inv_cancel₀- In a group with zero (such as a field), multiplying a non-zero element by its inverse yields 1: a * a⁻¹ = 1.
- The summation is taken over `Finset.univ`. Applying `Finset.sum_eq_single` generates a formal side condition that terms outside `Finset.univ` vanish; this is immediately discharged as contradictory using `Finset.mem_univ`.
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.
/-- A nowhere-vanishing affine form on (Fin m → ZMod 3) must have all linear coefficients zero. -/theorem nowhere_zero_affine_is_constant (m : ℕ) (a : Fin m → ZMod 3) (b : ZMod 3) (h : ∀ x : Fin m → ZMod 3, (∑ i, a i * x i) + b ≠ 0) : ∀ i, a i = 0 := by intro i by_contra hi let x : Fin m → ZMod 3 := Function.update (fun _ => 0) i (-(a i)⁻¹ * b) have hx : (∑ j, a j * x j) + b = 0 := by have hsum : (∑ j, a j * x j) = a i * (-(a i)⁻¹ * b) := by rw [Finset.sum_eq_single i] · simp [x] · intro j _ hj simp [x, hj] · intro hnot exact absurd (Finset.mem_univ i) hnot rw [hsum] rw [neg_mul, mul_neg, ← mul_assoc, mul_inv_cancel₀ hi] ring exact h x hx