AFTD Auto-Formalizing Theoretical Domains

grid_arrangement_row_deviation_subset_sum_bound

theoremverifiedformalization

Let $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 $\{1, \dots, N\}$. For the row-deviation vector $\rho_i = \sum_{j=0}^{n-1} S(i,j) - n(N+1)/2$ and any subset of rows $I \subseteq \mathrm{Fin}\ n$ of cardinality $p = |I|$, $|\sum_{i \in I} \rho_i| \le pn(N-pn)/2$.

Statement

theorem grid_arrangement_row_deviation_subset_sum_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)
    (I : Finset (Fin n)) :
    let ρ := fun i => (∑ j : Fin n, S (i, j)) - (n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2
    let p := I.card
    let N := (n : ℤ) ^ 2
    |∑ i ∈ I, ρ i| ≤ (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 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 every natural number $n$ with $n \ge 3$, every injective function $S : \mathrm{Fin}(n) \times \mathrm{Fin}(n) \to \mathbb{Z}$ whose range is bounded by $1 \le S(c) \le n^2$ for all cells $c \in \mathrm{Fin}(n) \times \mathrm{Fin}(n)$, and every subset of row indices $I \subseteq \mathrm{Fin}(n)$: Letting $\rho(i) = \left(\sum_{j \in \mathrm{Fin}(n)} S(i, j)\right) - \frac{n(n^2 + 1)}{2}$ (using integer division in $\mathbb{Z}$), $p = |I|$, and $N = n^2$, the absolute value of the sum of row deviations over $I$ satisfies: $$\left| \sum_{i \in I} \rho(i) \right| \le \frac{p \cdot n \cdot (N - p \cdot n)}{2}$$ (where division is integer division 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 theorem is proved by reducing row deviations to column deviations via transposition. Transposing the grid swaps rows and columns while preserving injectivity and the value bounds. Applying the corresponding column-deviation bound to the transposed grid immediately yields the row-deviation bound, because the column deviations of the transposed grid are definitionally the row deviations of the original grid.

  1. Introduce local definitions and define the transposed grid $S_{\mathrm{trans}}$.

    We introduce the local names for the row-deviation vector $\rho$, the cardinality $p = |I|$, and $N = n^2$, and define the transposed grid arrangement $S_{\mathrm{trans}}(i, j) = S(j, i)$.

    lines 11–12

      intro ρ p N
      let S_trans : Fin n × Fin n → ℤ := fun c => S (c.2, c.1)
  2. $S_{\mathrm{trans}}$ is injective.

    If $S_{\mathrm{trans}}(a_1, b_1) = S_{\mathrm{trans}}(a_2, b_2)$, then by definition $S(b_1, a_1) = S(b_2, a_2)$. Because $S$ is injective, $(b_1, a_1) = (b_2, a_2)$, which implies $(a_1, b_1) = (a_2, b_2)$.

    lines 13–18

      have hS_trans_inj : Function.Injective S_trans := by
        intro ⟨a1, b1⟩ ⟨a2, b2⟩ h
        dsimp [S_trans] at h
        have := hS_inj h
        cases this
        rfl
  3. $S_{\mathrm{trans}}$ takes values in $\{1, \dots, n^2\}$.

    For any grid coordinate $c$, $S_{\mathrm{trans}}(c) = S(c.2, c.1)$, which satisfies $1 \le S(c.2, c.1) \le n^2$ by the range hypothesis on $S$.

    lines 19–21

      have hS_trans_range : ∀ c, 1 ≤ S_trans c ∧ S_trans c ≤ (n : ℤ) ^ 2 := by
        intro c
        exact hS_range (c.2, c.1)
  4. The row-deviation subset sum satisfies $|\sum_{i \in I} \rho_i| \le p n (N - p n) / 2$.

    We apply `grid_arrangement_column_deviation_subset_sum_bound` to $S_{\mathrm{trans}}$ and the index set $I$. The $j$-th column sum of $S_{\mathrm{trans}}$ is $\sum_i S_{\mathrm{trans}}(i, j) = \sum_i S(j, i)$, which is the $j$-th row sum of $S$. Consequently, the column deviations of $S_{\mathrm{trans}}$ are definitionally equal to the row deviations $\rho$ of $S$, completing the proof.

    lines 22–24

    uses grid_arrangement_column_deviation_subset_sum_bound

      have h_bound := grid_arrangement_column_deviation_subset_sum_bound hn S_trans hS_trans_inj hS_trans_range I
      dsimp at h_bound
      exact h_bound
grid_arrangement_column_deviation_subset_sum_bound
For any injective grid arrangement with values in $\{1, \dots, n^2\}$, the subset sum of column deviations $|\sum_{j \in J} \gamma_j|$ for a column subset $J$ is bounded by $|J| n (n^2 - |J| n) / 2$.

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

/-- Majorisation bound for row-deviation subset sums of a grid arrangement. -/theorem grid_arrangement_row_deviation_subset_sum_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)    (I : Finset (Fin n)) :    let ρ := fun i => (∑ j : Fin n, S (i, j)) - (n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2    let p := I.card    let N := (n : ℤ) ^ 2    |∑ i ∈ I, ρ i| ≤ (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 2 := by  intro ρ p N  let S_trans : Fin n × Fin n → ℤ := fun c => S (c.2, c.1)  have hS_trans_inj : Function.Injective S_trans := by    intro ⟨a1, b1⟩ ⟨a2, b2⟩ h    dsimp [S_trans] at h    have := hS_inj h    cases this    rfl  have hS_trans_range : ∀ c, 1 ≤ S_trans c ∧ S_trans c ≤ (n : ℤ) ^ 2 := by    intro c    exact hS_range (c.2, c.1)  have h_bound := grid_arrangement_column_deviation_subset_sum_bound hn S_trans hS_trans_inj hS_trans_range I  dsimp at h_bound  exact h_bound
See it in the graphDiscuss this resultChallenge it