An FKN Theorem for the Binary Grassmann Scheme

Abstract

A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f:\{0,1{\}}^n\to \{-1,1\}$ close to a degree $1$ function, then either $f$ or $-f$ is close to either the all $1$ function, or to $(-1{)}^{x_i}$ for some $i\in [n]$. We prove a version of their theorem for the Grassmann scheme over ${\mathbb{F}}_2$. More precisely, we prove if a function $f:\left[\genfrac{}{}{0ex}{}{{\mathbb{F}}_2^n}{\ell }\right]\to \{0,1\}$ is close to a degree $1$ function, then either $f$ or $1-f$ must be close to a function of the form $g(L)={\sum }_{x\in \mathcal{X}}{1}_{x\in L}+{\sum }_{W\in \mathcal{W}}{1}_{L\subseteq W}$, where $\mathcal{X}\subseteq {\mathbb{F}}_2^n$ is a set of points and $\mathcal{W}$ is a set of hyperplanes in ${\mathbb{F}}_2^n$.

16 pages