grid_arrangement_column_deviation_entrywise_bound
For any grid arrangement $S$ of order $n \ge 3$ and any column index $j$, the column deviation satisfies $|\gamma_j| \le n^2(n-1)/2$.
Statement
theorem grid_arrangement_column_deviation_entrywise_bound {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 : Fin n) : let γ_j := (∑ i : Fin n, S (i, j)) - (n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2 |γ_j| ≤ (n : ℤ) ^ 2 * ((n : ℤ) - 1) / 2
- Formalizes
- 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 : \mathrm{Fin}(n) \times \mathrm{Fin}(n) \to \mathbb{Z}$ whose values satisfy $1 \le S(c) \le n^2$ for all $c \in \mathrm{Fin}(n) \times \mathrm{Fin}(n)$, and any column index $j \in \mathrm{Fin}(n)$: Let $\gamma_j = \left(\sum_{i \in \mathrm{Fin}(n)} S(i, j)\right) - n(n^2 + 1) / 2$ (evaluated via integer division in $\mathbb{Z}$, where $n(n^2+1)$ is always even so the division is exact). Then $|\gamma_j| \le n^2(n - 1) / 2$ (again evaluated via integer division in $\mathbb{Z}$, where $n^2(n-1)$ 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 is proved by specializing the general subset-sum bound on column deviations to the singleton column set $\{j\}$. For a singleton set, the sum of deviations reduces to the single column deviation $\gamma_j$, and the cardinality is $1$. Factoring the resulting upper bound $n(n^2 - n)/2$ algebraically as $n^2(n - 1)/2$ completes the proof.
For the single column $j$, the column deviation satisfies $|\sum_{i} S(i, j) - n(n^2 + 1)/2| \le n(n^2 - n)/2$.
We specialize the general subset deviation bound `grid_arrangement_column_deviation_subset_sum_bound` to the singleton column set $J = \{j\}$. Using `Finset.sum_singleton`, the sum over $\{j\}$ reduces to the single column deviation. Using `Finset.card_singleton`, `Nat.cast_one`, and `one_mul`, the subset size $|J| = 1$ is substituted into the general upper bound $|J| \cdot n(n^2 - |J|n)/2$, simplifying it to $n(n^2 - n)/2$.
uses
grid_arrangement_column_deviation_subset_sum_bound,Finset.sum_singleton,Finset.card_singleton,Nat.cast_one,one_mulhave h := grid_arrangement_column_deviation_subset_sum_bound hn S hS_inj hS_range {j} simp only [Finset.sum_singleton, Finset.card_singleton, Nat.cast_one, one_mul] at h
$|\gamma_j| \le n^2(n - 1) / 2$.
Introducing $\gamma_j$ as the column deviation from the goal's `let` binding, the previous step establishes $|\gamma_j| \le n(n^2 - n)/2$. Factoring an extra factor of $n$ yields the algebraic identity $n(n^2 - n) = n^2(n - 1)$, which holds by ring expansion. Rewriting the bound with this identity matches the goal and concludes the proof.
intro γ_j have heq : (n : ℤ) * ((n : ℤ) ^ 2 - (n : ℤ)) = (n : ℤ) ^ 2 * ((n : ℤ) - 1) := by ring rw [heq] at h exact h
grid_arrangement_column_deviation_subset_sum_bound- For any grid arrangement $S$ of order $n \ge 3$ and any subset of columns $J$, the absolute sum of column deviations over $J$ is bounded by $|J| \cdot n(n^2 - |J|n)/2$.
Finset.sum_singleton- The sum of a function over a singleton set $\{a\}$ equals the value of the function at $a$: $\sum_{x \in \{a\}} f(x) = f(a)$.
Finset.card_singleton- The cardinality of a singleton set is $1$: $|\{a\}| = 1$.
Nat.cast_one- The natural number $1$ coerced to another ring (such as the integers $\mathbb{Z}$) equals $1$.
one_mul- Multiplication by $1$ on the left is the identity: $1 \cdot a = a$.
- Line 11 (`intro γ_j`) is a formal Lean artifact: the `let` definition in the theorem statement must be introduced into the local context before the final goal can be closed by `exact h`. It has no counterpart on paper where $\gamma_j$ is already introduced in the theorem statement.
- In line 12, the `ring` tactic verifies the polynomial identity $n(n^2 - n) = n^2(n - 1)$ by simple algebraic expansion.
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.
/-- Individual column-deviation bound for an order-$n$ grid arrangement. -/theorem grid_arrangement_column_deviation_entrywise_bound {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 : Fin n) : let γ_j := (∑ i : Fin n, S (i, j)) - (n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2 |γ_j| ≤ (n : ℤ) ^ 2 * ((n : ℤ) - 1) / 2 := by have h := grid_arrangement_column_deviation_subset_sum_bound hn S hS_inj hS_range {j} simp only [Finset.sum_singleton, Finset.card_singleton, Nat.cast_one, one_mul] at h intro γ_j have heq : (n : ℤ) * ((n : ℤ) ^ 2 - (n : ℤ)) = (n : ℤ) ^ 2 * ((n : ℤ) - 1) := by ring rw [heq] at h exact h