grid_arrangement_column_deviation_subset_sum_bound
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 3
- grid_arrangement_row_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…
- grid_arrangement_column_deviation_entrywise_boundFor 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$.
- grid_arrangement_column_deviation_subset_sum_geFor any grid arrangement $S$ of order $n \ge 3$ and any column subset $J$ of cardinality $p$, the column-deviation sum…
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.
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.
uses
Even.mul_right,Int.not_even_iff_odd,Odd.pow,Odd.add_odd,odd_one,Even.mul_leftlemma 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 _
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.
uses
Even.mul_left,Int.not_even_iff_odd,Even.mul_right,Odd.sub_oddlemma 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 _
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.
uses
Finset.sum_range_id_mul_two,Nat.cast_sumlemma 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'
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.
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
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.
uses
Finset.card_product,Finset.card_univ,Fintype.card_fin,mul_comm,Finset.card_image_of_injective,Finset.sum_product_right,Finset.sum_imageset 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
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.
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_distribhave 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
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.
uses
Nat.cast_mul,grid_arrangement_column_deviation_subset_sum_bound_even_Eset 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
|∑_{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.
uses
abs_le.mpr,abs_mulhave 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.
- The proof relies on linear arithmetic and ring equality automation (linarith, ring, omega) to simplify algebraic expressions and handle division by 2 for even numbers.
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.
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