{"id":"arxiv/2608.11320","url":"https://arxiv.org/abs/2608.11320","tags":["cs.CC","math.CO"],"score":0,"title":"An FKN Theorem for the Binary Grassmann Scheme","domain":"cs.CC","source":"arxiv","authors":["Yuval Filmus","Anqi Li","Dor Minzer"],"reviews":0,"subject":"cs.CC","summary":"A classical theorem due to Friedgut, Kalai and Naor asserts that if a function $f\\colon \\{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\\colon \\genfrac{[}{]}{0pt}{}{\\mathbb{F}_2^n}{\\ell}\\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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}