grid_arrangement_column_deviation_subset_sum_ge
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 below by $-pn(N-pn)/2$.
Statement
theorem grid_arrangement_column_deviation_subset_sum_ge {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 (-((p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 2)) ≤ ∑ j ∈ J, γ j
- Source
- arXiv:2610.38386 Lemma 3.8
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- grid_arrangement_column_deviation_subset_sum_boundLet $n \ge 3$, $N = n^2$, and let $S : \mathrm{Fin}\ n \times \mathrm{Fin}\ n \to \mathbb{Z}$ be an injective arrangement with entries in…
Read back from the Lean
For any natural number $n \ge 3$, any injective function $S : \text{Fin } n \times \text{Fin } n \to \mathbb{Z}$ whose values all lie between $1$ and $n^2$ inclusive, and any finite subset $J \subseteq \text{Fin } n$: Let $\gamma(j) = \left(\sum_{i : \text{Fin } n} S(i, j)\right) - n(n^2 + 1) / 2$ (using integer division in $\mathbb{Z}$), let $p = |J|$, and let $N = n^2$. Then: $$-\left( \frac{p \cdot n \cdot (N - p \cdot n)}{2} \right) \le \sum_{j \in J} \gamma(j)$$ (where the division is integer division in $\mathbb{Z}$, though the numerator is always even).
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 theorem follows directly from the absolute-value bound `grid_arrangement_column_deviation_subset_sum_bound`, which establishes that $|\\sum_{j \\in J} \\gamma_j| \\le pn(N - pn)/2$. Because $|x| \\le B$ implies $-B \\le x$, extracting the lower inequality immediately yields the desired lower bound on the column-deviation subset sum.
$|\\sum_{j \\in J} \\gamma_j| \\le pn(N - pn)/2$
Introduce the definitions of $\\gamma$ (the column deviation), $p = |J|$, and $N = n^2$. Applying `grid_arrangement_column_deviation_subset_sum_bound` with grid $S$ and column subset $J$ establishes that the absolute value of the column-deviation subset sum is bounded by $pn(N - pn)/2$.
uses
grid_arrangement_column_deviation_subset_sum_boundintro γ p N have h := grid_arrangement_column_deviation_subset_sum_bound hn S hS_inj hS_range J
$-pn(N - pn)/2 \\le \\sum_{j \\in J} \\gamma_j$
From $|x| \\le B$, the lemma `abs_le.mp` yields both $-B \\le x$ and $x \\le B$. Extracting the first conjunct gives the required lower bound.
uses
abs_le.mpexact (abs_le.mp h).1
grid_arrangement_column_deviation_subset_sum_bound- For a grid arrangement $S$ of order $n \\ge 3$ and any column subset $J$ of cardinality $p$, the absolute deviation sum satisfies $|\\sum_{j \\in J} \\gamma_j| \\le pn(N - pn)/2$, where $N = n^2$.
abs_le.mp- An absolute value inequality $|a| \\le b$ implies the conjunction $-b \\le a \\wedge a \\le b$.
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.
/-- Lower bound for column-deviation subset sum by the sum of the smallest entries. -/theorem grid_arrangement_column_deviation_subset_sum_ge {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 (-((p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 2)) ≤ ∑ j ∈ J, γ j := by intro γ p N have h := grid_arrangement_column_deviation_subset_sum_bound hn S hS_inj hS_range J exact (abs_le.mp h).1