latin_hypercube_is_affine
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
- 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 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.
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.
uses
Fin.elim0revert 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
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.
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 - b0The 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.
uses
Fin.update_cons_zero,nowhere_zero_affine_is_constant,Finset.sum_sub_distrib,sub_mul,zmod3_perm_is_affine,sub_eq_zero.mphave 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)
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.
uses
zmod3_perm_is_affinehave 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
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).
uses
zmod3_perm_is_affinehave 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
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.
uses
Fin.cases,Fin.cons_self_tail,Fin.sum_univ_succ,Fin.cases_zero,Fin.cases_succ,Fin.cons_zero,Fin.cons_succlet 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
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 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