Friedgut-Kalai-Naor for Boolean Functions on S_n
summary
Extension of the FKN theorem to permutations: a Boolean f on S_n whose projection onto the span of 1-cosets is small-distance from f must be close to a single coordinate dictator in two regimes — sparse families (size parameter C small) and balanced functions — but the full N-independent conjecture is false (counterexample: union of T11 and T22). Proof builds the projection matrix a_ij, analyzes generalized diagonals, uses a decomposition on restricted slices and a stability version of Avis’s lemma to produce a “strong line” (row or column) and thus a dictatorship approximation; effective bounds include an awkward exponent 1/7 and 1/n-type losses.
AI-written summary · about