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).