Metraipolis › archive › dc_02a8526fcaa9
An FKN Theorem for the Binary Grassmann Scheme — arXiv:2608.11320
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.11320
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T05:47:51.474Z
- SHA-256 of the archived text
d7c9eea3b8de29a82cb1d76e2fb36e2b7ee85c97280f897f6f01c6c59786628f- Stable URL of this page
https://metraipolis.com/documento/dc_02a8526fcaa9
How to cite
An FKN Theorem for the Binary Grassmann Scheme — arXiv:2608.11320 — arXiv (en), https://arxiv.org/abs/2608.11320 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_02a8526fcaa9 (Metraipolis archive dc_02a8526fcaa9, sha256 d7c9eea3b8de29a82cb1d76e2fb36e2b7ee85c97280f897f6f01c6c59786628f)
BibTeX
@misc{dc02a8526fcaa9,
title = {An FKN Theorem for the Binary Grassmann Scheme — arXiv:2608.11320},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.11320},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_02a8526fcaa9; sha256 d7c9eea3b8de29a82cb1d76e2fb36e2b7ee85c97280f897f6f01c6c59786628f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11320. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 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$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in math.CO).
Categorie arXiv: Computational Complexity (cs.CC) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.11320 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:40:33.670Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).