Spencer's bound from the partial colouring step and the residual colouring
ProvedKomlos.spencer_recursionAssume both of the following.
- (Partial colouring step.) For every matrix, every nonempty active set of columns and all parameters , obeying , there is a partial colouring of leaving at most a fraction of uncoloured whose row sums are at most in absolute value.
- (Residual colouring.) Every set of columns carries a colouring whose row sums are at most in absolute value.
Then every matrix with entries in admits signs with
which is Spencer's theorem. What has to be supplied is the scheduling: the fraction colored at each application, the parameter used there, the point at which the recursion is stopped in favour of the residual colouring, and the verification that the resulting geometric series of costs stays below . The constant is the one from the original paper, and it is what makes the schedule delicate: a random colouring alone gives , and the recursion has to pay for every round.
Formalization Note The two inputs appear as explicit hypotheses so that this statement is exactly the combinatorial bookkeeping of the argument and nothing else; they are the separately stated partial colouring and residual colouring problems. Colourings are encoded as real-valued vectors, with marking an uncoloured coordinate in the partial colourings.
import Mathlib import Definitions.Def_Komlos_model open Finset
namespace Komlos
theorem spencer_recursion
(pcl : ∀ (n : ℕ) (A : Fin n → Fin n → ℝ), (∀ i j, A i j = 0 ∨ A i j = 1) →
∀ (T : Finset (Fin n)), 0 < T.card → ∀ θ ν : ℝ, 0 < θ → θ ≤ 1 / 2 → 2 ≤ ν →
(n : ℝ) * (2 * Real.exp (-(ν ^ 2) / 2) * (3 * ν ^ 2 / 4 + 2))
≤ (2 / 3) * θ ^ 2 * (T.card : ℝ) →
∃ χ : Fin n → ℝ,
(∀ j, χ j = 1 ∨ χ j = -1 ∨ χ j = 0) ∧
(∀ j, j ∉ T → χ j = 0) ∧
(1 - θ) * (T.card : ℝ) ≤ ((T.filter (fun j => χ j ≠ 0)).card : ℝ) ∧
(∀ i, |∑ j ∈ T, A i j * χ j| ≤ ν * Real.sqrt (T.card : ℝ)))
(fin : ∀ (n : ℕ), 0 < n → ∀ (A : Fin n → Fin n → ℝ), (∀ i j, A i j = 0 ∨ A i j = 1) →
∀ (T : Finset (Fin n)),
∃ χ : Fin n → ℝ,
(∀ j, j ∈ T → (χ j = 1 ∨ χ j = -1)) ∧
(∀ j, j ∉ T → χ j = 0) ∧
(∀ i, |∑ j ∈ T, A i j * χ j|
≤ Real.sqrt (2 * (T.card : ℝ) * Real.log (4 * n))))
(n : ℕ) (A : Fin n → Fin n → ℝ) (h01 : ∀ i j, A i j = 0 ∨ A i j = 1) :
∃ ε : Fin n → ℝ, IsSignVector ε ∧
∀ i, |∑ j, A i j * ε j| ≤ 6 * Real.sqrt n := by sorry
end Komlos