AFTD Auto-Formalizing Theoretical Domains

grid_arrangement_column_deviation_entrywise_bound

theoremverifiedformalization

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

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.

  1. 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$.

    lines 9–10

    uses grid_arrangement_column_deviation_subset_sum_bound, Finset.sum_singleton, Finset.card_singleton, Nat.cast_one, one_mul

      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
  2. $|\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.

    lines 11–14

      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$.

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

/-- 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
See it in the graphDiscuss this resultChallenge it