AFTD Auto-Formalizing Theoretical Domains

nowhere_zero_affine_is_constant

theoremverified

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

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.

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

    lines 3–5

      intro i
      by_contra hi
      let x : Fin m → ZMod 3 := Function.update (fun _ => 0) i (-(a i)⁻¹ * b)
  2. 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).

    lines 6–13

    uses Finset.sum_eq_single, Finset.mem_univ

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

    lines 14–16

    uses neg_mul, mul_neg, mul_assoc, mul_inv_cancel₀

        rw [hsum]
        rw [neg_mul, mul_neg, ← mul_assoc, mul_inv_cancel₀ hi]
        ring
  4. 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.

    line 17

      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.

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

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