grid_arrangement_column_deviation_subset_sum_le
For any grid arrangement $S$ of order $n \ge 3$ and any column subset $J$ of cardinality $p$, the column-deviation sum $\sum_{j \in J} \gamma_j$ is bounded above by $pn(N-pn)/2$.
Statement
theorem grid_arrangement_column_deviation_subset_sum_le {n : ℕ} (hn : 3 ≤ n) (S : Fin n × Fin n → ℤ) (hS_inj : Function.Injective S) (hS_range : ∀ c, 1 ≤ S c ∧ S c ≤ (n : ℤ) ^ 2) (J : Finset (Fin n)) : let γ := fun j => (∑ i : Fin n, S (i, j)) - (n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2 let p := J.card let N := (n : ℤ) ^ 2 ∑ j ∈ J, γ j ≤ (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 2
- Source
- arXiv:2610.38386 Lemma 3.8
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
Read back from the Lean
Given a natural number $n \ge 3$, an injective function $S : \text{Fin } n \times \text{Fin } n \to \mathbb{Z}$ such that $1 \le S(c) \le n^2$ for all $c \in \text{Fin } n \times \text{Fin } n$, and a subset of column indices $J \subseteq \text{Fin } n$: Let $\gamma(j) = \left(\sum_{i \in \text{Fin } n} S(i, j)\right) - n(n^2 + 1) / 2$ (where $/$ is integer division), let $p = |J|$, and let $N = n^2$. Then the sum over $j \in J$ of $\gamma(j)$ is at most $p \cdot n \cdot (N - p \cdot n) / 2$ (in $\mathbb{Z}$).
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 proof bounds the column-deviation subset sum $\sum_{j \in J} \gamma_j$ by recognizing that it equals the total sum of the grid entries in the $p$ chosen columns minus $p \cdot \frac{n(n^2+1)}{2}$. Since the arrangement $S$ is injective with entries in $\{1, \dots, n^2\}$, these $pn$ entries form a subset of $\{1, \dots, n^2\}$. An auxiliary lemma, proved by induction on the upper bound $B$, shows that the sum of any subset $T \subseteq \{1, \dots, B\}$ is maximized by taking the $|T|$ largest elements, which sum to $|T|(2B - |T| + 1)/2$. Finally, an exact integer arithmetic identity verifies that subtracting the mean column sum $p \cdot \frac{n(n^2+1)}{2}$ from this upper bound simplifies algebraically to $pn(n^2 - pn)/2$.
For $B = 0$, any finite subset $T \subseteq \{1, \dots, 0\}$ is empty and satisfies $\sum_{x \in T} x \le |T|(2B - |T| + 1)/2$.
The main goal is simplified, and an auxiliary lemma `hmaxsum` is set up: for any $B \in \mathbb{N}$ and any finite subset $T$ of integers bounded between $1$ and $B$, the sum of $T$ is at most $|T|(2B - |T| + 1)/2$ (the sum of the $|T|$ largest integers in $\{1, \dots, B\}$). The lemma is proved by induction on $B$. In the base case $B = 0$, any $x \in T$ must satisfy $1 \le x \le 0$, which is impossible by linear arithmetic (`omega`). Thus $T = \emptyset$ by `Finset.eq_empty_iff_forall_notMem`, and both sides evaluate to 0.
uses
Finset.eq_empty_iff_forall_notMemdsimp only have hmaxsum : ∀ (B : ℕ) (T : Finset ℤ), (∀ x ∈ T, 1 ≤ x ∧ x ≤ (B : ℤ)) → ∑ x ∈ T, x ≤ (T.card : ℤ) * (2 * (B : ℤ) - (T.card : ℤ) + 1) / 2 := by intro B T hT induction B generalizing T with | zero => have hTe : T = ∅ := by rw [Finset.eq_empty_iff_forall_notMem] intro x hx have h := hT x hx omega subst hTe simp
In the induction step for `hmaxsum`, the inequality holds when the maximal element $B+1$ is in $T$.
If $B+1 \in T$, we remove it to form $T' = T \setminus \{B+1\}$. The elements of $T'$ lie in $\{1, \dots, B\}$, and its cardinality is $|T| - 1 \ge 0$ (by `Finset.card_erase_of_mem` and `Nat.cast_sub`). Applying the induction hypothesis to $T'$ bounds $\sum_{x \in T'} x$. Adding $B+1$ back via $\sum_{x \in T} x = \sum_{x \in T'} x + (B+1)$ (`Finset.sum_erase_add`) and rewriting the bound using the algebraic identity $|T|(2(B+1) - |T| + 1) = (|T|-1)(2B - (|T|-1) + 1) + 2(B+1)$ together with integer division arithmetic (`Int.add_mul_ediv_right`), linear arithmetic completes this case.
uses
Finset.card_pos.mpr,Finset.mem_erase,Nat.cast_succ,Finset.card_erase_of_mem,Nat.cast_sub,Nat.cast_one,Finset.sum_erase_add,Int.add_mul_ediv_right| succ B ih => by_cases hmem : ((B : ℤ) + 1) ∈ T · have hcard_ge : 1 ≤ T.card := Finset.card_pos.mpr ⟨_, hmem⟩ have hT' : ∀ x ∈ T.erase ((B:ℤ)+1), 1 ≤ x ∧ x ≤ (B:ℤ) := by intro x hx simp only [Finset.mem_erase] at hx have h := hT x hx.2 refine ⟨h.1, ?_⟩ rw [Nat.cast_succ] at h omega have key := ih (T.erase ((B:ℤ)+1)) hT' rw [Finset.card_erase_of_mem hmem, Nat.cast_sub hcard_ge, Nat.cast_one] at key have hsum : ∑ x ∈ T.erase ((B:ℤ)+1), x + ((B:ℤ)+1) = ∑ x ∈ T, x := Finset.sum_erase_add _ _ hmem rw [← hsum] push_cast have hb : (T.card : ℤ) * (2 * ((B : ℤ) + 1) - (T.card : ℤ) + 1) = ((T.card : ℤ) - 1) * (2 * (B : ℤ) - ((T.card : ℤ) - 1) + 1) + ((B:ℤ)+1) * 2 := by ring rw [hb, Int.add_mul_ediv_right _ _ (by norm_num : (2:ℤ) ≠ 0)] linarith [key]In the induction step for `hmaxsum`, the inequality holds when $B+1 \notin T$.
If $B+1 \notin T$, every element of $T$ is already at most $B$. Applying the induction hypothesis directly to $T$ gives $\sum_{x \in T} x \le |T|(2B - |T| + 1)/2$. Since $|T|(2(B+1) - |T| + 1) = |T|(2B - |T| + 1) + 2|T|$, dividing by 2 yields $|T|(2B - |T| + 1)/2 + |T|$ via `Int.add_mul_ediv_right`. Because $|T| \ge 0$ (`positivity`), this upper bound is at least the induction hypothesis bound, which concludes the proof of `hmaxsum`.
uses
Nat.cast_succ,Int.add_mul_ediv_right· have hT' : ∀ x ∈ T, 1 ≤ x ∧ x ≤ (B:ℤ) := by intro x hx have h := hT x hx refine ⟨h.1, ?_⟩ rw [Nat.cast_succ] at h by_contra hc push Not at hc have : x = (B:ℤ)+1 := by omega exact hmem (this ▸ hx) have key := ih T hT' push_cast have hb : (T.card : ℤ) * (2 * ((B : ℤ) + 1) - (T.card : ℤ) + 1) = (T.card : ℤ) * (2 * (B : ℤ) - (T.card : ℤ) + 1) + (T.card : ℤ) * 2 := by ring rw [hb, Int.add_mul_ediv_right _ _ (by norm_num : (2:ℤ) ≠ 0)] have hnn : (0:ℤ) ≤ (T.card : ℤ) := by positivity linarith [key]
For any integers $m$ and $p$, $(pm)(2m^2 - pm + 1)/2 - p \cdot \frac{m(m^2+1)}{2} = \frac{pm(m^2 - pm)}{2}$.
We check that $m(m^2+1)$ is always divisible by 2: if $m$ is even, $m$ provides a factor of 2; if $m$ is odd, $m^2+1$ is even (`Int.even_or_odd`). Hence $2 \cdot \frac{m(m^2+1)}{2} = m(m^2+1)$ (`Int.mul_ediv_cancel'`). Expanding the first numerator as $pm(m^2 - pm) + 2 \cdot [p \cdot m(m^2+1)/2]$ allows canceling the division by 2 via `Int.add_mul_ediv_right`, yielding the algebraic identity.
uses
Int.even_or_odd,Int.mul_ediv_cancel',Int.add_mul_ediv_righthave harith : ∀ (m p : ℤ), (p*m) * (2*m^2 - p*m + 1) / 2 - p*(m*(m^2+1)/2) = p*m*(m^2 - p*m)/2 := by intro m p have hB : (2:ℤ) ∣ m*(m^2+1) := by rcases Int.even_or_odd m with h | h · obtain ⟨k, hk⟩ := h exact ⟨k*(m^2+1), by rw [hk]; ring⟩ · obtain ⟨k, hk⟩ := h exact ⟨m*(2*k^2+2*k+1), by rw [hk]; ring⟩ have hBhalf : 2*(m*(m^2+1)/2) = m*(m^2+1) := Int.mul_ediv_cancel' hB have hA : (p*m)*(2*m^2 - p*m+1) = p*m*(m^2-p*m) + p*(m*(m^2+1)) := by ring have hpB : p*(m*(m^2+1)) = (p*(m*(m^2+1)/2))*2 := by calc p*(m*(m^2+1)) = p*(2*(m*(m^2+1)/2)) := by rw [hBhalf] _ = (p*(m*(m^2+1)/2))*2 := by ring rw [hA, hpB, Int.add_mul_ediv_right _ _ (by norm_num : (2:ℤ) ≠ 0)] ring
The set of cells $C = \text{univ} \times J$ has $|C| = n|J|$, and its image $T = S(C)$ satisfies $|T| = n|J|$ and $T \subseteq \{1, \dots, n^2\}$, so `hmaxsum` applies to $T$.
We define $C$ as the set of grid cells in the selected columns $J$, and $T = S(C)$ as the set of their entries. By injectivity of $S$, $|T| = |C| = n|J|$ (by `Finset.card_product` and `Finset.card_image_of_injOn`). The hypothesis on the range of $S$ ensures each element of $T$ lies in $\{1, \dots, n^2\}$. Specializing `hmaxsum` with $B = n^2$ gives an upper bound on $\sum_{x \in T} x$.
uses
Finset.card_product,Finset.card_image_of_injOn,Finset.mem_imageset C : Finset (Fin n × Fin n) := Finset.univ ×ˢ J with hCdef set T : Finset ℤ := C.image S with hTdef have hInj : Set.InjOn S ↑C := fun a _ b _ h => hS_inj h have hCcard : C.card = n * J.card := by rw [hCdef, Finset.card_product]; simp have hTcard : T.card = n * J.card := by rw [hTdef, Finset.card_image_of_injOn hInj, hCcard] have hTbound : ∀ x ∈ T, 1 ≤ x ∧ x ≤ ((n^2 : ℕ) : ℤ) := by intro x hx rw [hTdef, Finset.mem_image] at hx obtain ⟨c, hc, hcS⟩ := hx rw [← hcS] obtain ⟨h1, h2⟩ := hS_range c refine ⟨h1, ?_⟩ push_cast exact h2 have hmax := hmaxsum (n^2) T hTbound
The sum of the grid entries in columns $J$ is bounded by $(|J|n)(2n^2 - |J|n + 1)/2$.
Because $S$ is injective on $C$, the sum over $T = S(C)$ equals the sum of $S(c)$ over all cells $c \in C$ (`Finset.sum_image`). Interchanging summation order on $C = \text{univ} \times J$ shows $\sum_{c \in C} S(c) = \sum_{j \in J} \sum_{i} S(i, j)$ (`Finset.sum_product`, `Finset.sum_comm`). Substituting $|T| = |J|n$ and $B = n^2$ into the bound from `hmaxsum` gives the desired bound on $\sum_{c \in C} S(c)$.
uses
Finset.sum_image,Finset.sum_product,Finset.sum_commhave hTsum : ∑ x ∈ T, x = ∑ c ∈ C, S c := by rw [hTdef]; exact Finset.sum_image hInj have hcol : ∑ c ∈ C, S c = ∑ j ∈ J, ∑ i : Fin n, S (i, j) := by rw [hCdef, Finset.sum_product, Finset.sum_comm] have hbound1 : ∑ c ∈ C, S c ≤ ((J.card:ℤ)*(n:ℤ)) * (2*((n:ℤ)^2) - ((J.card:ℤ)*(n:ℤ)) + 1) / 2 := by rw [← hTsum] have e1 : (T.card : ℤ) = (J.card:ℤ)*(n:ℤ) := by rw [hTcard]; push_cast; ring have e2 : ((n^2:ℕ):ℤ) = (n:ℤ)^2 := by push_cast; ring rw [e1, e2] at hmax exact hmax
The column-deviation subset sum $\sum_{j \in J} \gamma_j$ is bounded above by $pn(N - pn)/2$.
Expanding the definition of $\gamma_j$ and distributing the sum over $j \in J$ expresses $\sum_{j \in J} \gamma_j$ as $\sum_{c \in C} S(c) - |J| \cdot \frac{n(n^2+1)}{2}$ (`Finset.sum_sub_distrib`, `Finset.sum_const`, `nsmul_eq_mul`). Combining this with the upper bound on $\sum_{c \in C} S(c)$ and applying the algebraic identity `harith` with $m = n$ and $p = |J|$ proves the theorem via linear arithmetic (`linarith`).
uses
Finset.sum_sub_distrib,Finset.sum_const,nsmul_eq_mulhave hgamma : ∑ j ∈ J, ((∑ i : Fin n, S (i,j)) - (n:ℤ)*((n:ℤ)^2+1)/2) = (∑ c ∈ C, S c) - (J.card:ℤ)*((n:ℤ)*((n:ℤ)^2+1)/2) := by rw [Finset.sum_sub_distrib, ← hcol, Finset.sum_const, nsmul_eq_mul] rw [hgamma] have hfe := harith (n:ℤ) (J.card:ℤ) linarith [hbound1, hfe]
Finset.eq_empty_iff_forall_notMem- A finite set is empty if and only if no element belongs to it.
Finset.card_pos.mpr- A finite set has strictly positive cardinality (at least 1) if it contains at least one element.
Finset.mem_erase- An element $x$ belongs to $s \setminus \{a\}$ if and only if $x \ne a$ and $x \in s$.
Nat.cast_succ- The cast of $n + 1$ to a ring equals the cast of $n$ plus 1.
Finset.card_erase_of_mem- Removing an element that belongs to a finite set decreases its cardinality by 1.
Nat.cast_sub- For natural numbers $m \le n$, the cast of $n - m$ to an additive group with one equals the cast of $n$ minus the cast of $m$.
Nat.cast_one- The cast of $1 \in \mathbb{N}$ to a ring is 1.
Finset.sum_erase_add- For a finite set $s$ and an element $a \in s$, the sum of $f$ over $s \setminus \{a\}$ plus $f(a)$ equals the sum of $f$ over $s$.
Int.add_mul_ediv_right- For integers $a, b, c$ with $c \ne 0$, $(a + b \cdot c) / c = a / c + b$.
Int.even_or_odd- Every integer is either even or odd.
Int.mul_ediv_cancel'- If $a$ divides $b$, then $a \cdot (b / a) = b$.
Finset.card_product- The cardinality of a Cartesian product of two finite sets is the product of their cardinalities.
Finset.card_image_of_injOn- If $f$ is injective on a finite set $s$, then its image $f(s)$ has the same cardinality as $s$.
Finset.mem_image- An element is in the image $f(s)$ if and only if it is of the form $f(a)$ for some $a \in s$.
Finset.sum_image- If $g$ is injective on $s$, the sum of $f$ over the image $g(s)$ equals the sum of $f \circ g$ over $s$.
Finset.sum_product- A sum of $f(x, y)$ over a Cartesian product $s \times t$ equals the iterated sum $\sum_{x \in s} \sum_{y \in t} f(x, y)$.
Finset.sum_comm- Iterated finite sums commute: $\sum_{x \in s} \sum_{y \in t} f(x, y) = \sum_{y \in t} \sum_{x \in s} f(x, y)$.
Finset.sum_sub_distrib- The sum of a difference of functions over a finite set equals the difference of their sums.
Finset.sum_const- The sum of a constant value $b$ over a finite set $s$ equals $|s| \cdot b$.
nsmul_eq_mul- Scalar multiplication of an element $a$ by a natural number $n$ equals $n \cdot a$.
- All divisions by 2 in the proof are Lean integer divisions (`/ 2`), which correspond to exact divisions in $\mathbb{Z}$ because the quantities involved (such as $m(m^2+1)$) are provably even.
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.
/-- Upper bound for column-deviation subset sum by the sum of the largest entries. -/theorem grid_arrangement_column_deviation_subset_sum_le {n : ℕ} (hn : 3 ≤ n) (S : Fin n × Fin n → ℤ) (hS_inj : Function.Injective S) (hS_range : ∀ c, 1 ≤ S c ∧ S c ≤ (n : ℤ) ^ 2) (J : Finset (Fin n)) : let γ := fun j => (∑ i : Fin n, S (i, j)) - (n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2 let p := J.card let N := (n : ℤ) ^ 2 ∑ j ∈ J, γ j ≤ (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 2 := by dsimp only have hmaxsum : ∀ (B : ℕ) (T : Finset ℤ), (∀ x ∈ T, 1 ≤ x ∧ x ≤ (B : ℤ)) → ∑ x ∈ T, x ≤ (T.card : ℤ) * (2 * (B : ℤ) - (T.card : ℤ) + 1) / 2 := by intro B T hT induction B generalizing T with | zero => have hTe : T = ∅ := by rw [Finset.eq_empty_iff_forall_notMem] intro x hx have h := hT x hx omega subst hTe simp | succ B ih => by_cases hmem : ((B : ℤ) + 1) ∈ T · have hcard_ge : 1 ≤ T.card := Finset.card_pos.mpr ⟨_, hmem⟩ have hT' : ∀ x ∈ T.erase ((B:ℤ)+1), 1 ≤ x ∧ x ≤ (B:ℤ) := by intro x hx simp only [Finset.mem_erase] at hx have h := hT x hx.2 refine ⟨h.1, ?_⟩ rw [Nat.cast_succ] at h omega have key := ih (T.erase ((B:ℤ)+1)) hT' rw [Finset.card_erase_of_mem hmem, Nat.cast_sub hcard_ge, Nat.cast_one] at key have hsum : ∑ x ∈ T.erase ((B:ℤ)+1), x + ((B:ℤ)+1) = ∑ x ∈ T, x := Finset.sum_erase_add _ _ hmem rw [← hsum] push_cast have hb : (T.card : ℤ) * (2 * ((B : ℤ) + 1) - (T.card : ℤ) + 1) = ((T.card : ℤ) - 1) * (2 * (B : ℤ) - ((T.card : ℤ) - 1) + 1) + ((B:ℤ)+1) * 2 := by ring rw [hb, Int.add_mul_ediv_right _ _ (by norm_num : (2:ℤ) ≠ 0)] linarith [key] · have hT' : ∀ x ∈ T, 1 ≤ x ∧ x ≤ (B:ℤ) := by intro x hx have h := hT x hx refine ⟨h.1, ?_⟩ rw [Nat.cast_succ] at h by_contra hc push Not at hc have : x = (B:ℤ)+1 := by omega exact hmem (this ▸ hx) have key := ih T hT' push_cast have hb : (T.card : ℤ) * (2 * ((B : ℤ) + 1) - (T.card : ℤ) + 1) = (T.card : ℤ) * (2 * (B : ℤ) - (T.card : ℤ) + 1) + (T.card : ℤ) * 2 := by ring rw [hb, Int.add_mul_ediv_right _ _ (by norm_num : (2:ℤ) ≠ 0)] have hnn : (0:ℤ) ≤ (T.card : ℤ) := by positivity linarith [key] have harith : ∀ (m p : ℤ), (p*m) * (2*m^2 - p*m + 1) / 2 - p*(m*(m^2+1)/2) = p*m*(m^2 - p*m)/2 := by intro m p have hB : (2:ℤ) ∣ m*(m^2+1) := by rcases Int.even_or_odd m with h | h · obtain ⟨k, hk⟩ := h exact ⟨k*(m^2+1), by rw [hk]; ring⟩ · obtain ⟨k, hk⟩ := h exact ⟨m*(2*k^2+2*k+1), by rw [hk]; ring⟩ have hBhalf : 2*(m*(m^2+1)/2) = m*(m^2+1) := Int.mul_ediv_cancel' hB have hA : (p*m)*(2*m^2 - p*m+1) = p*m*(m^2-p*m) + p*(m*(m^2+1)) := by ring have hpB : p*(m*(m^2+1)) = (p*(m*(m^2+1)/2))*2 := by calc p*(m*(m^2+1)) = p*(2*(m*(m^2+1)/2)) := by rw [hBhalf] _ = (p*(m*(m^2+1)/2))*2 := by ring rw [hA, hpB, Int.add_mul_ediv_right _ _ (by norm_num : (2:ℤ) ≠ 0)] ring set C : Finset (Fin n × Fin n) := Finset.univ ×ˢ J with hCdef set T : Finset ℤ := C.image S with hTdef have hInj : Set.InjOn S ↑C := fun a _ b _ h => hS_inj h have hCcard : C.card = n * J.card := by rw [hCdef, Finset.card_product]; simp have hTcard : T.card = n * J.card := by rw [hTdef, Finset.card_image_of_injOn hInj, hCcard] have hTbound : ∀ x ∈ T, 1 ≤ x ∧ x ≤ ((n^2 : ℕ) : ℤ) := by intro x hx rw [hTdef, Finset.mem_image] at hx obtain ⟨c, hc, hcS⟩ := hx rw [← hcS] obtain ⟨h1, h2⟩ := hS_range c refine ⟨h1, ?_⟩ push_cast exact h2 have hmax := hmaxsum (n^2) T hTbound have hTsum : ∑ x ∈ T, x = ∑ c ∈ C, S c := by rw [hTdef]; exact Finset.sum_image hInj have hcol : ∑ c ∈ C, S c = ∑ j ∈ J, ∑ i : Fin n, S (i, j) := by rw [hCdef, Finset.sum_product, Finset.sum_comm] have hbound1 : ∑ c ∈ C, S c ≤ ((J.card:ℤ)*(n:ℤ)) * (2*((n:ℤ)^2) - ((J.card:ℤ)*(n:ℤ)) + 1) / 2 := by rw [← hTsum] have e1 : (T.card : ℤ) = (J.card:ℤ)*(n:ℤ) := by rw [hTcard]; push_cast; ring have e2 : ((n^2:ℕ):ℤ) = (n:ℤ)^2 := by push_cast; ring rw [e1, e2] at hmax exact hmax have hgamma : ∑ j ∈ J, ((∑ i : Fin n, S (i,j)) - (n:ℤ)*((n:ℤ)^2+1)/2) = (∑ c ∈ C, S c) - (J.card:ℤ)*((n:ℤ)*((n:ℤ)^2+1)/2) := by rw [Finset.sum_sub_distrib, ← hcol, Finset.sum_const, nsmul_eq_mul] rw [hgamma] have hfe := harith (n:ℤ) (J.card:ℤ) linarith [hbound1, hfe]