Spencer: six standard deviations suffice
ProvedKomlos.spencer_six_deviations(Spencer 1985.) For any sets over elements — any matrix with entries in — there are signs with
Random signs give ; Spencer's theorem removes the logarithm, which no direct probabilistic argument can do. The constant is as in the original paper.
import Mathlib import Definitions.Def_Komlos_model
namespace Komlos
theorem spencer_six_deviations (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 KomlosRead-back
What the Lean code literally says, in plain math · claude-fable-5
Read-back: Komlos.spencer_six_deviations
For every natural number (including ) and every square real matrix , with rows and columns both indexed by and entries , under the hypothesis that every entry is either or (that is, for all : or ), the statement asserts the existence of a vector which is a sign vector — meaning, by the bundle's definition IsSignVector, that every entry satisfies or — such that every row of the signed column combination satisfies
where the inequality is non-strict (), the sum runs over all columns, and is the real square root of (so the right-hand side is , not and not with an unspecified constant — the constant is literally ).
Points the quantifiers silently include: when the matrix is empty, the empty function is vacuously a sign vector, and the conclusion is vacuously true (there are no rows ), so the statement holds trivially in that case. The matrix is required to be square: the number of "set/element" rows equals the number of columns, both being ; there is no separate row count. The theorem claims only existence of one such sign vector (plain , not unique existence), and the bound is required for every row simultaneously (an -type bound on the vector ). No relation to the definition KomlosBound from the imported file is asserted — the statement uses only IsSignVector.
Confirmed by the mission captain (proposal self-audit).