AFTD Auto-Formalizing Theoretical Domains

latin_hypercube_is_affine

theoremverified

Every order-3 Latin hypercube f : (Fin m → ZMod 3) → ZMod 3 (a function whose restriction to every 1D coordinate line is a bijection) is an affine function f(x) = (∑ i, a i * x i) + b with all coefficients a i nonzero.

Statement

theorem latin_hypercube_is_affine (m : ℕ) (f : (Fin m → ZMod 3) → ZMod 3) (hf : ∀ (i : Fin m) (c : Fin m → ZMod 3), Function.Bijective (fun t => f (Function.update c i t))) : ∃ (a : Fin m → ZMod 3) (ha : ∀ i, a i ≠ 0) (b : ZMod 3), ∀ x, f x = (∑ i, a i * x i) + b
Source
step towards ternary_minimal_line_cover_minimum_card_eq_hyperplane
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • zmod3_perm_is_affineEvery bijection f : ZMod 3 → ZMod 3 is affine: there exist a, b ∈ ZMod 3 with a ≠ 0 such that f(t) = a * t + b for all t ∈ ZMod 3.
  • nowhere_zero_affine_is_constantIf 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.
Used by 1

The proof, explained

The theorem is proved by induction on the dimension m. For the inductive step, slicing the Latin hypercube f by fixing its first coordinate to 0 and 1 produces two Latin hypercubes of dimension m, which are affine with nonzero coefficients by the induction hypothesis. Because every coordinate line in the first direction is a bijection of ZMod 3 and therefore an affine permutation, the difference between these two slices is nowhere zero, which forces their directional coefficients to coincide and their difference to be a nonzero constant d. This implies that f is linear in its first coordinate with slope d, which combines with the affine representation of the slice at 0 to yield the full affine form of f with all coefficients nonzero.

  1. When m = 0, f is an affine function whose constant term is f(Fin.elim0) and whose coefficient vector is empty.

    We proceed by induction on m. In the base case m = 0, the domain Fin 0 → ZMod 3 contains only the empty tuple Fin.elim0. Choosing the empty function for the directional coefficients, the requirement that every coefficient is nonzero holds vacuously. Since every element x of the domain equals the empty tuple, the sum over the empty index set Fin 0 vanishes, and f(x) = 0 + f(Fin.elim0) holds trivially.

    lines 3–14

    uses Fin.elim0

      revert f
      induction m with
      | zero =>
          intro f hf
          refine ⟨fun i => Fin.elim0 i, ?_, f (fun i => Fin.elim0 i), ?_⟩
          · intro i; exact Fin.elim0 i
          · intro x
            have hx : x = fun i => Fin.elim0 i := by
              funext i
              exact Fin.elim0 i
            rw [hx]
            simp
  2. For the inductive step, the slices g(0, -) and g(1, -) obtained by fixing the first coordinate to 0 and 1 are affine functions on (ZMod 3)^m with nonzero directional coefficients.

    Assuming the induction hypothesis holds for dimension m, let f be a Latin hypercube on (ZMod 3)^(m + 1). Slicing f by fixing the first coordinate to c gives g(c, y) = f(c, y). Varying any coordinate of y in g(c, -) corresponds via Fin.cons_update to varying a non-initial coordinate of f, so each slice g(c, -) is a Latin hypercube on (ZMod 3)^m. By the induction hypothesis, both g(0, -) and g(1, -) are affine functions with all directional coefficients nonzero. We define d = b1 - b0 as the difference between their constant terms.

    lines 15–23

    uses Fin.cons_update

      | succ m ih =>
          intro f hf
          let g : ZMod 3 → (Fin m → ZMod 3) → ZMod 3 := fun c y => f (Fin.cons c y)
          have hg : ∀ c, ∀ (i : Fin m) (cc : Fin m → ZMod 3), Function.Bijective (fun t => g c (Function.update cc i t)) := by
            intro c i cc
            simpa only [g, Fin.cons_update] using hf (Fin.succ i) (Fin.cons c cc)
          obtain ⟨a0, ha0, b0, h0⟩ := ih (g 0) (hg 0)
          obtain ⟨a1, ha1, b1, h1⟩ := ih (g 1) (hg 1)
          let d : ZMod 3 := b1 - b0
  3. The directional coefficients of the slices g(1, -) and g(0, -) coincide: a1 i = a0 i for all i.

    For any fixed y, the 1D restriction t ↦ f(t, y) along the first coordinate is a bijection of ZMod 3 by Fin.update_cons_zero. By zmod3_perm_is_affine, every bijection of ZMod 3 is affine of the form t ↦ A * t + B with A ≠ 0, so the difference g(1, y) - g(0, y) = f(1, y) - f(0, y) = A is never 0. On the other hand, subtracting the affine formulas for g(1, y) and g(0, y) using Finset.sum_sub_distrib and sub_mul shows that g(1, y) - g(0, y) = (∑ i, (a1 i - a0 i) * y i) + (b1 - b0). Since this affine function never vanishes on (ZMod 3)^m, nowhere_zero_affine_is_constant guarantees that all its directional coefficients are 0, whence a1 i = a0 i by sub_eq_zero.mp.

    lines 24–48

    uses Fin.update_cons_zero, nowhere_zero_affine_is_constant, Finset.sum_sub_distrib, sub_mul, zmod3_perm_is_affine, sub_eq_zero.mp

          have hline : ∀ y : Fin m → ZMod 3, Function.Bijective (fun t => f (Fin.cons t y)) := by
            intro y
            simpa only [Fin.update_cons_zero] using hf 0 (Fin.cons (0 : ZMod 3) y)
          have hcoef : ∀ i, a1 i - a0 i = 0 := by
            apply nowhere_zero_affine_is_constant m (fun i => a1 i - a0 i) (b1 - b0)
            intro y
            have hsum : (∑ i, (a1 i - a0 i) * y i) = (∑ i, a1 i * y i) - (∑ i, a0 i * y i) := by
              rw [← Finset.sum_sub_distrib]
              congr 1
              ext i
              rw [sub_mul]
            have hd : (∑ i, (a1 i - a0 i) * y i) + (b1 - b0) = g 1 y - g 0 y := by
              rw [h1 y, h0 y, hsum]
              ring
            rw [hd]
            obtain ⟨A, B, hA, hAB⟩ := zmod3_perm_is_affine (fun t => f (Fin.cons t y)) (hline y)
            have hdiff : g 1 y - g 0 y = A := by
              change f (Fin.cons (1 : ZMod 3) y) - f (Fin.cons (0 : ZMod 3) y) = A
              rw [hAB 1, hAB 0]
              ring
            rw [hdiff]
            exact hA
          have hdeq : ∀ i, a1 i = a0 i := by
            intro i
            exact sub_eq_zero.mp (hcoef i)
  4. The difference g(1, y) - g(0, y) is identically equal to the nonzero constant d = b1 - b0.

    Because a1 = a0, the linear terms in g(1, y) - g(0, y) cancel, leaving g(1, y) - g(0, y) = b1 - b0 = d for every y. Specializing to y = 0, the coordinate line t ↦ f(t, 0) is an affine bijection A * t + B with A ≠ 0 by zmod3_perm_is_affine. Since A = f(1, 0) - f(0, 0) = g(1, 0) - g(0, 0) = d, we conclude that d ≠ 0.

    lines 49–67

    uses zmod3_perm_is_affine

          have hdiffd : ∀ y : Fin m → ZMod 3, g 1 y - g 0 y = d := by
            intro y
            rw [h1 y, h0 y]
            simp only [hdeq]
            ring
          have hb : d ≠ 0 := by
            let y : Fin m → ZMod 3 := fun _ => 0
            obtain ⟨A, B, hA, hAB⟩ := zmod3_perm_is_affine (fun t => f (Fin.cons t y)) (hline y)
            have hAeq : A = d := by
              calc
                A = A * 1 + B - B := by ring
                _ = f (Fin.cons (1 : ZMod 3) y) - B := by rw [hAB 1]
                _ = f (Fin.cons (1 : ZMod 3) y) - f (Fin.cons (0 : ZMod 3) y) := by
                  rw [hAB 0]
                  ring
                _ = g 1 y - g 0 y := rfl
                _ = d := hdiffd y
            rw [← hAeq]
            exact hA
  5. For every c ∈ ZMod 3 and y ∈ (ZMod 3)^m, the slice function satisfies g(c, y) = c * d + g(0, y).

    For any fixed y, the restriction t ↦ f(t, y) is an affine bijection A * t + B by zmod3_perm_is_affine. Setting t = 0 identifies the intercept as B = f(0, y) = g(0, y), while the difference f(1, y) - f(0, y) identifies the slope as A = d. Thus g(c, y) = f(c, y) = A * c + B = c * d + g(0, y).

    lines 68–87

    uses zmod3_perm_is_affine

          have hmain : ∀ (c : ZMod 3) (y : Fin m → ZMod 3), g c y = c * d + g 0 y := by
            intro c y
            obtain ⟨A, B, hA, hAB⟩ := zmod3_perm_is_affine (fun t => f (Fin.cons t y)) (hline y)
            have hB : B = g 0 y := by
              have h0c := hAB 0
              change f (Fin.cons (0 : ZMod 3) y) = A * 0 + B at h0c
              simpa [g] using h0c.symm
            have hAeq : A = d := by
              calc
                A = A * 1 + B - B := by ring
                _ = f (Fin.cons (1 : ZMod 3) y) - B := by rw [hAB 1]
                _ = f (Fin.cons (1 : ZMod 3) y) - f (Fin.cons (0 : ZMod 3) y) := by
                  rw [hAB 0]
                  ring
                _ = g 1 y - g 0 y := rfl
                _ = d := hdiffd y
            calc
              g c y = f (Fin.cons c y) := rfl
              _ = A * c + B := hAB c
              _ = c * d + g 0 y := by rw [hAeq, hB]; ring
  6. The function f is affine on (ZMod 3)^(m + 1) with nonzero directional coefficients.

    We define the extended coefficient vector a by setting a 0 = d and a (i + 1) = a0 i via Fin.cases. Since d ≠ 0 and each a0 i ≠ 0, all coefficients of a are nonzero. Any input x decomposes into its head x 0 and tail via Fin.cons_self_tail, so f(x) = g(x 0, Fin.tail x) = (x 0) * d + g(0, Fin.tail x). Expanding g(0, Fin.tail x) via the induction hypothesis and combining the terms using Fin.sum_univ_succ, Fin.cases_zero, Fin.cases_succ, Fin.cons_zero, and Fin.cons_succ establishes that f(x) = (∑ i, a i * x i) + b0.

    lines 88–102

    uses Fin.cases, Fin.cons_self_tail, Fin.sum_univ_succ, Fin.cases_zero, Fin.cases_succ, Fin.cons_zero, Fin.cons_succ

          let a : Fin (m+1) → ZMod 3 := fun j => Fin.cases d a0 j
          refine ⟨a, ?_, b0, ?_⟩
          · intro j
            cases j using Fin.cases with
            | zero => simpa [a] using hb
            | succ i => simpa [a] using ha0 i
          · intro x
            have hx : Fin.cons (x 0) (Fin.tail x) = x := Fin.cons_self_tail x
            rw [← hx]
            change g (x 0) (Fin.tail x) = (∑ i, a i * Fin.cons (x 0) (Fin.tail x) i) + b0
            rw [hmain (x 0) (Fin.tail x)]
            rw [h0 (Fin.tail x)]
            rw [Fin.sum_univ_succ]
            simp only [a, Fin.cases_zero, Fin.cases_succ, Fin.tail, Fin.cons_zero, Fin.cons_succ]
            ring
Fin.elim0
The empty type Fin 0 has no elements, so any map from Fin 0 is vacuously defined.
Fin.cons_update
Prepending an element x to an updated tuple p[i ↦ y] equals updating the prepended tuple (x, p) at coordinate i + 1 with y.
Fin.update_cons_zero
Updating a prepended tuple (x, p) at coordinate 0 with z yields the tuple (z, p).
nowhere_zero_affine_is_constant
An affine function on (ZMod 3)^m that never takes the value 0 must have all its directional coefficients equal to 0.
zmod3_perm_is_affine
Every permutation of ZMod 3 is an affine map t ↦ a * t + b with nonzero slope a.
Finset.sum_sub_distrib
The sum of a difference of functions equals the difference of their sums.
sub_mul
Right-distributivity of multiplication over subtraction: (a - b) * c = a * c - b * c.
sub_eq_zero.mp
If a - b = 0, then a = b.
Fin.cases
Case analysis on an index in Fin (n + 1), splitting into index 0 and successor indices.
Fin.cons_self_tail
Any tuple in (ZMod 3)^(n + 1) is reconstructed by prepending its first coordinate to its tail.
Fin.sum_univ_succ
A sum over Fin (n + 1) decomposes into the term at 0 plus the sum over the remaining coordinates.
Fin.cases_zero
Fin.cases evaluated at index 0 yields the value for the zero case.
Fin.cases_succ
Fin.cases evaluated at a successor index i + 1 yields the successor branch evaluated at i.
Fin.cons_zero
The 0-th element of the tuple formed by prepending x to p is x.
Fin.cons_succ
The (i + 1)-th element of the tuple formed by prepending x to p is p i.

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

/-- Every order-3 Latin hypercube over ZMod 3 is an affine function with nonzero directional coefficients. -/theorem latin_hypercube_is_affine (m : ℕ) (f : (Fin m → ZMod 3) → ZMod 3) (hf : ∀ (i : Fin m) (c : Fin m → ZMod 3), Function.Bijective (fun t => f (Function.update c i t))) : ∃ (a : Fin m → ZMod 3) (ha : ∀ i, a i ≠ 0) (b : ZMod 3), ∀ x, f x = (∑ i, a i * x i) + b := by  revert f  induction m with  | zero =>      intro f hf      refine ⟨fun i => Fin.elim0 i, ?_, f (fun i => Fin.elim0 i), ?_⟩      · intro i; exact Fin.elim0 i      · intro x        have hx : x = fun i => Fin.elim0 i := by          funext i          exact Fin.elim0 i        rw [hx]        simp  | succ m ih =>      intro f hf      let g : ZMod 3 → (Fin m → ZMod 3) → ZMod 3 := fun c y => f (Fin.cons c y)      have hg : ∀ c, ∀ (i : Fin m) (cc : Fin m → ZMod 3), Function.Bijective (fun t => g c (Function.update cc i t)) := by        intro c i cc        simpa only [g, Fin.cons_update] using hf (Fin.succ i) (Fin.cons c cc)      obtain ⟨a0, ha0, b0, h0⟩ := ih (g 0) (hg 0)      obtain ⟨a1, ha1, b1, h1⟩ := ih (g 1) (hg 1)      let d : ZMod 3 := b1 - b0      have hline : ∀ y : Fin m → ZMod 3, Function.Bijective (fun t => f (Fin.cons t y)) := by        intro y        simpa only [Fin.update_cons_zero] using hf 0 (Fin.cons (0 : ZMod 3) y)      have hcoef : ∀ i, a1 i - a0 i = 0 := by        apply nowhere_zero_affine_is_constant m (fun i => a1 i - a0 i) (b1 - b0)        intro y        have hsum : (∑ i, (a1 i - a0 i) * y i) = (∑ i, a1 i * y i) - (∑ i, a0 i * y i) := by          rw [← Finset.sum_sub_distrib]          congr 1          ext i          rw [sub_mul]        have hd : (∑ i, (a1 i - a0 i) * y i) + (b1 - b0) = g 1 y - g 0 y := by          rw [h1 y, h0 y, hsum]          ring        rw [hd]        obtain ⟨A, B, hA, hAB⟩ := zmod3_perm_is_affine (fun t => f (Fin.cons t y)) (hline y)        have hdiff : g 1 y - g 0 y = A := by          change f (Fin.cons (1 : ZMod 3) y) - f (Fin.cons (0 : ZMod 3) y) = A          rw [hAB 1, hAB 0]          ring        rw [hdiff]        exact hA      have hdeq : ∀ i, a1 i = a0 i := by        intro i        exact sub_eq_zero.mp (hcoef i)      have hdiffd : ∀ y : Fin m → ZMod 3, g 1 y - g 0 y = d := by        intro y        rw [h1 y, h0 y]        simp only [hdeq]        ring      have hb : d ≠ 0 := by        let y : Fin m → ZMod 3 := fun _ => 0        obtain ⟨A, B, hA, hAB⟩ := zmod3_perm_is_affine (fun t => f (Fin.cons t y)) (hline y)        have hAeq : A = d := by          calc            A = A * 1 + B - B := by ring            _ = f (Fin.cons (1 : ZMod 3) y) - B := by rw [hAB 1]            _ = f (Fin.cons (1 : ZMod 3) y) - f (Fin.cons (0 : ZMod 3) y) := by              rw [hAB 0]              ring            _ = g 1 y - g 0 y := rfl            _ = d := hdiffd y        rw [← hAeq]        exact hA      have hmain : ∀ (c : ZMod 3) (y : Fin m → ZMod 3), g c y = c * d + g 0 y := by        intro c y        obtain ⟨A, B, hA, hAB⟩ := zmod3_perm_is_affine (fun t => f (Fin.cons t y)) (hline y)        have hB : B = g 0 y := by          have h0c := hAB 0          change f (Fin.cons (0 : ZMod 3) y) = A * 0 + B at h0c          simpa [g] using h0c.symm        have hAeq : A = d := by          calc            A = A * 1 + B - B := by ring            _ = f (Fin.cons (1 : ZMod 3) y) - B := by rw [hAB 1]            _ = f (Fin.cons (1 : ZMod 3) y) - f (Fin.cons (0 : ZMod 3) y) := by              rw [hAB 0]              ring            _ = g 1 y - g 0 y := rfl            _ = d := hdiffd y        calc          g c y = f (Fin.cons c y) := rfl          _ = A * c + B := hAB c          _ = c * d + g 0 y := by rw [hAeq, hB]; ring      let a : Fin (m+1) → ZMod 3 := fun j => Fin.cases d a0 j      refine ⟨a, ?_, b0, ?_⟩      · intro j        cases j using Fin.cases with        | zero => simpa [a] using hb        | succ i => simpa [a] using ha0 i      · intro x        have hx : Fin.cons (x 0) (Fin.tail x) = x := Fin.cons_self_tail x        rw [← hx]        change g (x 0) (Fin.tail x) = (∑ i, a i * Fin.cons (x 0) (Fin.tail x) i) + b0        rw [hmain (x 0) (Fin.tail x)]        rw [h0 (Fin.tail x)]        rw [Fin.sum_univ_succ]        simp only [a, Fin.cases_zero, Fin.cases_succ, Fin.tail, Fin.cons_zero, Fin.cons_succ]        ring
See it in the graphDiscuss this resultChallenge it