AFTD Auto-Formalizing Theoretical Domains

grid_arrangement_column_deviation_subset_sum_ge

theoremverified

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

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.

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

    lines 11–12

    uses grid_arrangement_column_deviation_subset_sum_bound

      intro γ p N
      have h := grid_arrangement_column_deviation_subset_sum_bound hn S hS_inj hS_range J
  2. $-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.

    line 13

    uses abs_le.mp

      exact (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

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