AFTD Auto-Formalizing Theoretical Domains

grid_arrangement_column_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 column-deviation vector $\gamma_j = \sum_{i=0}^{n-1} S(i,j) - n(N+1)/2$ and any subset of columns $J \subseteq \mathrm{Fin}\ n$ of cardinality $p = |J|$, $|\sum_{j \in J} \gamma_j| \le pn(N-pn)/2$.

Statement

theorem grid_arrangement_column_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)
    (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
    |∑ j ∈ J, γ j| ≤ (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 2
Formalizes
arXiv:2610.38386 Lemma 3.8
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 3

Read back from the Lean

For every natural number $n \ge 3$, every injective function $S : \text{Fin } n \times \text{Fin } n \to \mathbb{Z}$ whose values satisfy $1 \le S(c) \le n^2$ for all $c \in \text{Fin } n \times \text{Fin } n$, and every subset $J \subseteq \text{Fin } n$: Defining for each column $j \in \text{Fin } n$ the deviation $$\gamma(j) = \left(\sum_{i \in \text{Fin } n} S(i, j)\right) - \frac{n(n^2 + 1)}{2}$$ (using integer division, which is exact since $n(n^2+1)$ is always even), and letting $p = |J|$ (the cardinality of $J$) and $N = n^2$, the absolute value of the sum of the deviations over columns in $J$ is bounded by: $$\left|\sum_{j \in J} \gamma(j)\right| \le \frac{p \cdot n \cdot (N - p \cdot n)}{2}$$ (evaluated using integer division on $\mathbb{Z}$, which is also exact).

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 bounds the deviation subset sum by extremal sums of M = pn distinct integers from {1, ..., N}. By injectivity of S, the entries in the p chosen columns form an M-element subset of {1, ..., N}. Its sum is majorised between the sum of the M smallest and M largest possible integers, which after subtracting the expected value pn(N+1)/2 yields the two-sided bound ±pn(N-pn)/2.

  1. For any n ∈ ℕ, n(n^2 + 1) is even as an integer.

    By case analysis on whether n is even or odd. If n is even, its product with n^2 + 1 is even. If n is odd, then n^2 is odd, so n^2 + 1 is the sum of two odd integers and hence even, which again makes the product even.

    lines 1–8

    uses Even.mul_right, Int.not_even_iff_odd, Odd.pow, Odd.add_odd, odd_one, Even.mul_left

    lemma grid_arrangement_column_deviation_subset_sum_bound_even_n (n : ℕ) :
        Even ((n : ℤ) * ((n : ℤ) ^ 2 + 1)) := by
      by_cases hn_even : Even (n : ℤ)
      · exact Even.mul_right hn_even _
      · have hodd : Odd (n : ℤ) := by rwa [← Int.not_even_iff_odd]
        have hodd2 : Odd ((n : ℤ) ^ 2) := Odd.pow hodd
        have heven : Even ((n : ℤ) ^ 2 + 1) := Odd.add_odd hodd2 odd_one
        exact Even.mul_left heven _
  2. When N = n^2, the quantity E = pn(N - pn) is even for any p, n ∈ ℕ.

    Factoring gives pn(N - pn) = p(n - p)n^2. If n is even, n^2 is even so the whole expression is even. If n is odd, we split on whether p is even or odd: if p is even, p(n - p) is even; if p is odd, n - p is the difference of two odd integers and therefore even. In every case, the product is even.

    lines 10–26

    uses Even.mul_left, Int.not_even_iff_odd, Even.mul_right, Odd.sub_odd

    lemma grid_arrangement_column_deviation_subset_sum_bound_even_E (n p : ℕ) (N : ℤ) (hN : N = (n : ℤ) ^ 2) :
        Even ((p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ))) := by
      have : (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) = (p : ℤ) * ((n : ℤ) - (p : ℤ)) * ((n : ℤ) * (n : ℤ)) := by
        rw [hN]
        ring
      rw [this]
      by_cases hn_even : Even (n : ℤ)
      · have hnn : Even ((n : ℤ) * (n : ℤ)) := Even.mul_left hn_even (n : ℤ)
        exact Even.mul_left hnn _
      · have hodd_n : Odd (n : ℤ) := by rwa [← Int.not_even_iff_odd]
        by_cases hp_even : Even (p : ℤ)
        · have hpn : Even ((p : ℤ) * ((n : ℤ) - (p : ℤ))) := Even.mul_right hp_even _
          exact Even.mul_right hpn _
        · have hodd_p : Odd (p : ℤ) := by rwa [← Int.not_even_iff_odd]
          have he : Even ((n : ℤ) - (p : ℤ)) := Odd.sub_odd hodd_n hodd_p
          have he2 : Even ((p : ℤ) * ((n : ℤ) - (p : ℤ))) := Even.mul_left he _
          exact Even.mul_right he2 _
  3. For any M ∈ ℕ, 2 ∑_{k=0}^{M-1} k = M(M - 1) in ℤ.

    Using the standard formula Finset.sum_range_id_mul_two for natural numbers and casting to integers. The base case M = 0 holds trivially by simplification, and the successor case M = M' + 1 follows by linear combination after expanding the predecessor.

    lines 28–41

    uses Finset.sum_range_id_mul_two, Nat.cast_sum

    lemma grid_arrangement_column_deviation_subset_sum_bound_sum_id (M : ℕ) :
        2 * (∑ k ∈ Finset.range M, (k : ℤ)) = (M : ℤ) * ((M : ℤ) - 1) := by
      have h := Finset.sum_range_id_mul_two M
      have hsum : (∑ k ∈ Finset.range M, (k : ℤ)) = ((∑ k ∈ Finset.range M, k : ℕ) : ℤ) := by
        rw [Nat.cast_sum]
      rw [hsum]
      rcases M with _ | M'
      · simp
      · have hsub : M' + 1 - 1 = M' := rfl
        rw [hsub] at h
        have h2' : ((∑ i ∈ Finset.range (M' + 1), i) * 2 : ℤ) = (((M' + 1) * M' : ℕ) : ℤ) := by
          exact_mod_cast h
        push_cast at h2' ⊢
        linear_combination h2'
  4. Twice the sum of deviations over J satisfies 2 ∑_{j ∈ J} γ_j = 2 ∑_{j ∈ J} ∑_{i} S(i, j) - M(N + 1), where M = pn.

    Since n(n^2 + 1) is even by the first helper lemma, division by 2 is exact, so 2 * (n(n^2+1)/2) = n(n^2+1). Expanding the definition of γ_j and distributing the summation over j ∈ J yields the result.

    lines 43–65

    uses grid_arrangement_column_deviation_subset_sum_bound_even_n, Finset.sum_sub_distrib, Finset.sum_const, nsmul_eq_mul

    /-- Majorisation bound for column-deviation subset sums of a grid arrangement (Lemma 3.8, eq. 10). -/
    theorem grid_arrangement_column_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)
        (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
        |∑ j ∈ J, γ j| ≤ (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 2 := by
      intro γ p N
      set M := p * n
      have hE_n := grid_arrangement_column_deviation_subset_sum_bound_even_n n
      have hdiv_n : 2 * ((n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2) = (n : ℤ) * ((n : ℤ) ^ 2 + 1) := by
        obtain ⟨k, hk⟩ := hE_n; omega
      have h_step1 : 2 * (∑ j ∈ J, γ j) = 2 * (∑ j ∈ J, ∑ i : Fin n, S (i, j)) - (M : ℤ) * (N + 1) := by
        dsimp [γ]
        rw [Finset.sum_sub_distrib, Finset.sum_const, nsmul_eq_mul]
        dsimp [p, N, M]
        calc 2 * (∑ x ∈ J, ∑ i, S (i, x) - (J.card : ℤ) * ((n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2))
          _ = 2 * (∑ x ∈ J, ∑ i, S (i, x)) - (J.card : ℤ) * (2 * ((n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2)) := by ring
          _ = 2 * (∑ x ∈ J, ∑ i, S (i, x)) - (J.card : ℤ) * ((n : ℤ) * ((n : ℤ) ^ 2 + 1)) := by rw [hdiv_n]
          _ = 2 * (∑ j ∈ J, ∑ i, S (i, j)) - (J.card * n : ℤ) * ((n : ℤ) ^ 2 + 1) := by ring
  5. The cells in the chosen columns form a set A of size M = pn, whose values under S form a set s ⊆ ℤ of size M with ∑_{j ∈ J} ∑_{i} S(i, j) = ∑_{x ∈ s} x.

    The index set A = univ × J consists of n * p = M cell positions. Because S is injective, the image s = S(A) also has cardinality M, and reindexing converts the double sum of S(i, j) over A into the sum of elements in s.

    lines 66–79

    uses Finset.card_product, Finset.card_univ, Fintype.card_fin, mul_comm, Finset.card_image_of_injective, Finset.sum_product_right, Finset.sum_image

      set A : Finset (Fin n × Fin n) := (Finset.univ : Finset (Fin n)) ×ˢ J
      set s : Finset ℤ := Finset.image S A
      have hA_card : A.card = M := by
        dsimp [A, M, p]
        rw [Finset.card_product, Finset.card_univ, Fintype.card_fin, mul_comm]
      have hs_card : s.card = M := by
        dsimp [s]
        rw [Finset.card_image_of_injective A hS_inj, hA_card]
      have hsum_eq : ∑ j ∈ J, ∑ i : Fin n, S (i, j) = ∑ x ∈ s, x := by
        rw [← Finset.sum_product_right]
        dsimp [s]
        rw [Finset.sum_image]
        intro x _ y _ h
        exact hS_inj h
  6. The sum of entries T = ∑_{x ∈ s} x satisfies 2M + M(M - 1) ≤ 2T ≤ 2MN - M(M - 1).

    Every entry x ∈ s satisfies 1 ≤ x ≤ N. By majorisation, any set of M distinct integers in this interval has sum at least the sum of the smallest M integers, ∑_{k=0}^{M-1} (1 + k), and at most the sum of the largest M integers, ∑_{k=0}^{M-1} (N - k). Doubling these sums and applying the integer summation identity yields the explicit bounds.

    lines 80–108

    uses Finset.mem_image, Finset.sum_range_le_sum, Finset.sum_le_sum_range, grid_arrangement_column_deviation_subset_sum_bound_sum_id, Finset.sum_add_distrib, Finset.sum_const, Finset.card_range, nsmul_eq_mul, mul_one, Finset.sum_sub_distrib

      have h1 : ∀ x ∈ s, 1 ≤ x := by
        intro x hx
        rw [Finset.mem_image] at hx
        rcases hx with ⟨c, _, rfl⟩
        exact (hS_range c).1
      have h2 : ∀ x ∈ s, x ≤ N := by
        intro x hx
        rw [Finset.mem_image] at hx
        rcases hx with ⟨c, _, rfl⟩
        exact (hS_range c).2
      have h_low := Finset.sum_range_le_sum (s := s) (c := 1) h1
      have h_upp := Finset.sum_le_sum_range (s := s) (c := N) h2
      rw [hs_card] at h_low h_upp
      have hsum_id := grid_arrangement_column_deviation_subset_sum_bound_sum_id M
      have h_low_eval : 2 * (∑ k ∈ Finset.range M, (1 + (k : ℤ))) = 2 * (M : ℤ) + (M : ℤ) * ((M : ℤ) - 1) := by
        rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_range, nsmul_eq_mul, mul_one]
        linarith
      have h_upp_eval : 2 * (∑ k ∈ Finset.range M, (N - (k : ℤ))) = 2 * (M : ℤ) * N - (M : ℤ) * ((M : ℤ) - 1) := by
        rw [Finset.sum_sub_distrib, Finset.sum_const, Finset.card_range, nsmul_eq_mul]
        linarith
      set T := ∑ x ∈ s, x
      have hT_low : 2 * (M : ℤ) + (M : ℤ) * ((M : ℤ) - 1) ≤ 2 * T := by
        calc 2 * (M : ℤ) + (M : ℤ) * ((M : ℤ) - 1)
          _ = 2 * (∑ k ∈ Finset.range M, (1 + (k : ℤ))) := h_low_eval.symm
          _ ≤ 2 * T := by linarith
      have hT_upp : 2 * T ≤ 2 * (M : ℤ) * N - (M : ℤ) * ((M : ℤ) - 1) := by
        calc 2 * T
          _ ≤ 2 * (∑ k ∈ Finset.range M, (N - (k : ℤ))) := by linarith
          _ = 2 * (M : ℤ) * N - (M : ℤ) * ((M : ℤ) - 1) := h_upp_eval
  7. The doubled sum of deviations is bounded: -E ≤ 2 ∑_{j ∈ J} γ_j ≤ E, where E = pn(N - pn).

    Algebraic simplification shows 2M + M(M - 1) - M(N + 1) = -M(N - M) = -E and 2MN - M(M - 1) - M(N + 1) = M(N - M) = E. Substituting the relation 2 ∑ γ_j = 2T - M(N + 1) and the bounds on 2T yields the inequalities.

    lines 109–127

    uses Nat.cast_mul, grid_arrangement_column_deviation_subset_sum_bound_even_E

      set E := (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ))
      have hM_eq : (M : ℤ) = (p : ℤ) * (n : ℤ) := Nat.cast_mul p n
      have hE_even : Even E := grid_arrangement_column_deviation_subset_sum_bound_even_E n p N rfl
      have h_bound_low : -E ≤ 2 * (∑ j ∈ J, γ j) := by
        rw [h_step1, hsum_eq]
        have hE_id : -E = 2 * (M : ℤ) + (M : ℤ) * ((M : ℤ) - 1) - (M : ℤ) * (N + 1) := by
          rw [hM_eq]
          dsimp [E]
          ring
        rw [hE_id]
        linarith
      have h_bound_upp : 2 * (∑ j ∈ J, γ j) ≤ E := by
        rw [h_step1, hsum_eq]
        have hE_id : E = 2 * (M : ℤ) * N - (M : ℤ) * ((M : ℤ) - 1) - (M : ℤ) * (N + 1) := by
          rw [hM_eq]
          dsimp [E]
          ring
        rw [hE_id]
        linarith
  8. |∑_{j ∈ J} γ_j| ≤ pn(N - pn) / 2.

    Because E is even, 2 * (E / 2) = E. The two bounds -E ≤ 2 ∑ γ_j ≤ E combine into |2 ∑ γ_j| ≤ 2 * (E / 2). Factoring out 2 from the absolute value and dividing by 2 completes the proof.

    lines 128–137

    uses abs_le.mpr, abs_mul

      have hdiv_E : 2 * (E / 2) = E := by
        obtain ⟨k, hk⟩ := hE_even
        omega
      have habs : |2 * (∑ j ∈ J, γ j)| ≤ 2 * (E / 2) := by
        rw [hdiv_E]
        exact abs_le.mpr ⟨h_bound_low, h_bound_upp⟩
      have : |2 * (∑ j ∈ J, γ j)| = 2 * |∑ j ∈ J, γ j| := by
        rw [abs_mul]
        norm_num
      linarith
Even.mul_right
If an integer a is even, then a * b is even for any b.
Int.not_even_iff_odd
An integer is odd if and only if it is not even.
Odd.pow
An odd integer raised to any natural power is odd.
Odd.add_odd
The sum of two odd integers is even.
odd_one
The integer 1 is odd.
Even.mul_left
If an integer a is even, then b * a is even for any b.
Odd.sub_odd
The difference of two odd integers is even.
Finset.sum_range_id_mul_two
Twice the sum of the first n natural numbers is n * (n - 1).
Nat.cast_sum
Casting a finite sum of natural numbers to integers equals the sum of the casts.
grid_arrangement_column_deviation_subset_sum_bound_even_n
For any natural number n, the product n * (n^2 + 1) is even.
Finset.sum_sub_distrib
The sum over a finite set distributes across subtraction.
Finset.sum_const
Summing a constant over a finite set equals the cardinality of the set times that constant.
nsmul_eq_mul
Scalar multiplication by a natural number equals multiplication by the natural cast.
Finset.card_product
The cardinality of a Cartesian product of two finite sets is the product of their cardinalities.
Finset.card_univ
The cardinality of the universal finset of a finite type is the type cardinality.
Fintype.card_fin
The cardinality of Fin n is n.
mul_comm
Multiplication is commutative.
Finset.card_image_of_injective
An injective map preserves the cardinality of a finite set.
Finset.sum_product_right
Reindexing a sum over a Cartesian product into iterated sums.
Finset.sum_image
Summing over the image of a finite set under an injective map equals summing over the domain.
Finset.mem_image
An element is in the image of a finset under f if and only if it is f of some element.
Finset.sum_range_le_sum
The sum of any set of M distinct integers, each at least c, is at least the sum of the smallest M such integers.
Finset.sum_le_sum_range
The sum of any set of M distinct integers, each at most c, is at most the sum of the largest M such integers.
grid_arrangement_column_deviation_subset_sum_bound_sum_id
Twice the sum of the first M integers in ℤ equals M * (M - 1).
Finset.sum_add_distrib
The sum over a finite set distributes across addition.
Finset.card_range
The cardinality of Finset.range n is n.
mul_one
Multiplying an element by 1 gives the element.
Nat.cast_mul
The cast of a product of natural numbers is the product of their casts.
grid_arrangement_column_deviation_subset_sum_bound_even_E
For N = n^2, the product p * n * (N - p * n) is always even.
abs_le.mpr
If -c ≤ x and x ≤ c, then |x| ≤ c.
abs_mul
The absolute value of a product is the product of the absolute values.

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

lemma grid_arrangement_column_deviation_subset_sum_bound_even_n (n : ℕ) :    Even ((n : ℤ) * ((n : ℤ) ^ 2 + 1)) := by  by_cases hn_even : Even (n : ℤ)  · exact Even.mul_right hn_even _  · have hodd : Odd (n : ℤ) := by rwa [← Int.not_even_iff_odd]    have hodd2 : Odd ((n : ℤ) ^ 2) := Odd.pow hodd    have heven : Even ((n : ℤ) ^ 2 + 1) := Odd.add_odd hodd2 odd_one    exact Even.mul_left heven _lemma grid_arrangement_column_deviation_subset_sum_bound_even_E (n p : ℕ) (N : ℤ) (hN : N = (n : ℤ) ^ 2) :    Even ((p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ))) := by  have : (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) = (p : ℤ) * ((n : ℤ) - (p : ℤ)) * ((n : ℤ) * (n : ℤ)) := by    rw [hN]    ring  rw [this]  by_cases hn_even : Even (n : ℤ)  · have hnn : Even ((n : ℤ) * (n : ℤ)) := Even.mul_left hn_even (n : ℤ)    exact Even.mul_left hnn _  · have hodd_n : Odd (n : ℤ) := by rwa [← Int.not_even_iff_odd]    by_cases hp_even : Even (p : ℤ)    · have hpn : Even ((p : ℤ) * ((n : ℤ) - (p : ℤ))) := Even.mul_right hp_even _      exact Even.mul_right hpn _    · have hodd_p : Odd (p : ℤ) := by rwa [← Int.not_even_iff_odd]      have he : Even ((n : ℤ) - (p : ℤ)) := Odd.sub_odd hodd_n hodd_p      have he2 : Even ((p : ℤ) * ((n : ℤ) - (p : ℤ))) := Even.mul_left he _      exact Even.mul_right he2 _lemma grid_arrangement_column_deviation_subset_sum_bound_sum_id (M : ℕ) :    2 * (∑ k ∈ Finset.range M, (k : ℤ)) = (M : ℤ) * ((M : ℤ) - 1) := by  have h := Finset.sum_range_id_mul_two M  have hsum : (∑ k ∈ Finset.range M, (k : ℤ)) = ((∑ k ∈ Finset.range M, k : ℕ) : ℤ) := by    rw [Nat.cast_sum]  rw [hsum]  rcases M with _ | M'  · simp  · have hsub : M' + 1 - 1 = M' := rfl    rw [hsub] at h    have h2' : ((∑ i ∈ Finset.range (M' + 1), i) * 2 : ℤ) = (((M' + 1) * M' : ℕ) : ℤ) := by      exact_mod_cast h    push_cast at h2' ⊢    linear_combination h2'/-- Majorisation bound for column-deviation subset sums of a grid arrangement (Lemma 3.8, eq. 10). -/theorem grid_arrangement_column_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)    (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    |∑ j ∈ J, γ j| ≤ (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ)) / 2 := by  intro γ p N  set M := p * n  have hE_n := grid_arrangement_column_deviation_subset_sum_bound_even_n n  have hdiv_n : 2 * ((n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2) = (n : ℤ) * ((n : ℤ) ^ 2 + 1) := by    obtain ⟨k, hk⟩ := hE_n; omega  have h_step1 : 2 * (∑ j ∈ J, γ j) = 2 * (∑ j ∈ J, ∑ i : Fin n, S (i, j)) - (M : ℤ) * (N + 1) := by    dsimp [γ]    rw [Finset.sum_sub_distrib, Finset.sum_const, nsmul_eq_mul]    dsimp [p, N, M]    calc 2 * (∑ x ∈ J, ∑ i, S (i, x) - (J.card : ℤ) * ((n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2))      _ = 2 * (∑ x ∈ J, ∑ i, S (i, x)) - (J.card : ℤ) * (2 * ((n : ℤ) * ((n : ℤ) ^ 2 + 1) / 2)) := by ring      _ = 2 * (∑ x ∈ J, ∑ i, S (i, x)) - (J.card : ℤ) * ((n : ℤ) * ((n : ℤ) ^ 2 + 1)) := by rw [hdiv_n]      _ = 2 * (∑ j ∈ J, ∑ i, S (i, j)) - (J.card * n : ℤ) * ((n : ℤ) ^ 2 + 1) := by ring  set A : Finset (Fin n × Fin n) := (Finset.univ : Finset (Fin n)) ×ˢ J  set s : Finset ℤ := Finset.image S A  have hA_card : A.card = M := by    dsimp [A, M, p]    rw [Finset.card_product, Finset.card_univ, Fintype.card_fin, mul_comm]  have hs_card : s.card = M := by    dsimp [s]    rw [Finset.card_image_of_injective A hS_inj, hA_card]  have hsum_eq : ∑ j ∈ J, ∑ i : Fin n, S (i, j) = ∑ x ∈ s, x := by    rw [← Finset.sum_product_right]    dsimp [s]    rw [Finset.sum_image]    intro x _ y _ h    exact hS_inj h  have h1 : ∀ x ∈ s, 1 ≤ x := by    intro x hx    rw [Finset.mem_image] at hx    rcases hx with ⟨c, _, rfl⟩    exact (hS_range c).1  have h2 : ∀ x ∈ s, x ≤ N := by    intro x hx    rw [Finset.mem_image] at hx    rcases hx with ⟨c, _, rfl⟩    exact (hS_range c).2  have h_low := Finset.sum_range_le_sum (s := s) (c := 1) h1  have h_upp := Finset.sum_le_sum_range (s := s) (c := N) h2  rw [hs_card] at h_low h_upp  have hsum_id := grid_arrangement_column_deviation_subset_sum_bound_sum_id M  have h_low_eval : 2 * (∑ k ∈ Finset.range M, (1 + (k : ℤ))) = 2 * (M : ℤ) + (M : ℤ) * ((M : ℤ) - 1) := by    rw [Finset.sum_add_distrib, Finset.sum_const, Finset.card_range, nsmul_eq_mul, mul_one]    linarith  have h_upp_eval : 2 * (∑ k ∈ Finset.range M, (N - (k : ℤ))) = 2 * (M : ℤ) * N - (M : ℤ) * ((M : ℤ) - 1) := by    rw [Finset.sum_sub_distrib, Finset.sum_const, Finset.card_range, nsmul_eq_mul]    linarith  set T := ∑ x ∈ s, x  have hT_low : 2 * (M : ℤ) + (M : ℤ) * ((M : ℤ) - 1) ≤ 2 * T := by    calc 2 * (M : ℤ) + (M : ℤ) * ((M : ℤ) - 1)      _ = 2 * (∑ k ∈ Finset.range M, (1 + (k : ℤ))) := h_low_eval.symm      _ ≤ 2 * T := by linarith  have hT_upp : 2 * T ≤ 2 * (M : ℤ) * N - (M : ℤ) * ((M : ℤ) - 1) := by    calc 2 * T      _ ≤ 2 * (∑ k ∈ Finset.range M, (N - (k : ℤ))) := by linarith      _ = 2 * (M : ℤ) * N - (M : ℤ) * ((M : ℤ) - 1) := h_upp_eval  set E := (p : ℤ) * (n : ℤ) * (N - (p : ℤ) * (n : ℤ))  have hM_eq : (M : ℤ) = (p : ℤ) * (n : ℤ) := Nat.cast_mul p n  have hE_even : Even E := grid_arrangement_column_deviation_subset_sum_bound_even_E n p N rfl  have h_bound_low : -E ≤ 2 * (∑ j ∈ J, γ j) := by    rw [h_step1, hsum_eq]    have hE_id : -E = 2 * (M : ℤ) + (M : ℤ) * ((M : ℤ) - 1) - (M : ℤ) * (N + 1) := by      rw [hM_eq]      dsimp [E]      ring    rw [hE_id]    linarith  have h_bound_upp : 2 * (∑ j ∈ J, γ j) ≤ E := by    rw [h_step1, hsum_eq]    have hE_id : E = 2 * (M : ℤ) * N - (M : ℤ) * ((M : ℤ) - 1) - (M : ℤ) * (N + 1) := by      rw [hM_eq]      dsimp [E]      ring    rw [hE_id]    linarith  have hdiv_E : 2 * (E / 2) = E := by    obtain ⟨k, hk⟩ := hE_even    omega  have habs : |2 * (∑ j ∈ J, γ j)| ≤ 2 * (E / 2) := by    rw [hdiv_E]    exact abs_le.mpr ⟨h_bound_low, h_bound_upp⟩  have : |2 * (∑ j ∈ J, γ j)| = 2 * |∑ j ∈ J, γ j| := by    rw [abs_mul]    norm_num  linarith
See it in the graphDiscuss this resultChallenge it