Partial colouring step for sets on points
ProvedKomlos.spencer_partial_coloringLet be an matrix with entries in , let be a nonempty set of columns, and let and satisfy the budget inequality
Then there is a partial colouring , vanishing outside , which colours at least a fraction of ,
and keeps every row balanced to within :
This is the step that the partial colouring method of Beck and Spencer iterates: one colours a constant fraction of the remaining points at a time, at a cost that shrinks geometrically, instead of colouring everything at once. The two parameters trade against each other — a smaller colours more points per application but demands a larger — and the budget inequality is exactly the constraint linking them. The quantity on its left is a closed form in ; on the right, the constant is a safely sub-critical stand-in for .
Formalization Note Partial colourings are encoded as real-valued vectors taking the three values , with marking an uncoloured coordinate; the requirement that vanish outside makes the restriction to the active set explicit. Both conclusions are stated for the sum over only, so the statement composes directly with itself when it is applied again to the uncoloured part.
import Mathlib open Finset
namespace Komlos
theorem spencer_partial_coloring
(n : ℕ) (A : Fin n → Fin n → ℝ) (h01 : ∀ i j, A i j = 0 ∨ A i j = 1)
(T : Finset (Fin n)) (hT : 0 < T.card)
(θ ν : ℝ) (hθ0 : 0 < θ) (hθ1 : θ ≤ 1 / 2) (hν : 2 ≤ ν)
(hbudget : (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 : ℝ)) := by sorry
end Komlos