Explicit Nonlinear Functions beyond the Fourier bound

Abstract

We study the problem of constructing highly nonlinear vectorial maps F: 𝔽₂ⁿ → 𝔽₂^m. Concretely, we want an F and an A = A(m,n)> 0 as small as possible, so that for every affine map L: 𝔽₂ⁿ → 𝔽₂^m (of the form $L(x) = M x + b $) we have: agree(F, L) := |{ x ∈ 𝔽₂ⁿ | F(x) = L(x) }| ≤ A. Such questions have been studied by Nyberg (1991,1993), Carlet and Ding (2004,2007), Liu, Mesnager and Chen (2017), Nagy (2025), and Biryukov, Turecek, and Udovenko (2026). There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is: A(m,n) = Θ(2^n−m + 2^n/2), and in particular, is never smaller than 2^n/2. In this work, we show how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we show how to construct for every γ>0, a function F: 𝔽₂ⁿ → 𝔽₂^m with m = O_γ(n), achieving A(m,n) ≤ (1 + γ)ⁿ. Surprisingly, we even achieve the same quantitative behavior for the much harder question of having low agreement with m-tuples of degree d polynomials Q: 𝔽₂ⁿ → 𝔽₂^m, with m = O_{γ, d}(n). Here the previously best bounds were of the form A(m,n) = O( 2^{−n/(2^d+1)} · 2ⁿ ) of Ben-Sasson and Kopparty (2010), based on Gowers-norm-type arguments. All our results generalize to all finite fields 𝔽_q in place of 𝔽₂. Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets.

A Two-regime Khintchine Inequality and an Improved Bound on the Degree-1 Fourier Weight for Linear Threshold Functions
Xuan Fang, Tianyu Wang
arXiv28 Aug 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv
An explicit refined Gan--Gross--Prasad identity for Fourier--Jacobi periods of degree 2 Siegel cusp forms
Biplab Paul, Ameya Pitale, Abhishek Saha +1
arXiv21 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
An explicit lower bound for the unit distance problem
Will Sawin
arXiv (Cornell University)20 May 2026PreprintLicence not statedFull text30 citedCombinatorics & discrete mathematicsOpenAlex
Optimizing Explicit Unit-Distance Lower-Bound Certificates
Michael T. M. Emmerich
arXiv (Cornell University)2 Jun 2026PreprintLicence not statedFull text9 citedCombinatorics & discrete mathematicsOpenAlex
Plotkin-Like Bound and Explicit Function-Correcting Code Constructions for Lee Metric Channels
K. Hareesh, Rashid Ummer N. T., Balaji Sundar Rajan
IEEE Transactions on Information Theory28 May 2026Peer-reviewedLicence not statedFull text10 citedCombinatorics & discrete mathematicsOpenAlex

Cite

BibTeX RIS

BibTeX

@misc{kopparty2026explicit,
  title = {{Explicit Nonlinear Functions beyond the Fourier bound}},
  author = {Swastik Kopparty and Rishabh Kothary and Shanthanu S. Rai},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.06362},
  eprint = {2610.06362},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.06362},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Explicit Nonlinear Functions beyond the Fourier bound
AU  - Swastik Kopparty
AU  - Rishabh Kothary
AU  - Shanthanu S. Rai
PY  - 2026
DA  - 2026/10/05
PB  - arXiv
DO  - 10.48550/arxiv.2610.06362
UR  - https://arxiv.org/abs/2610.06362
AB  - We study the problem of constructing highly nonlinear vectorial maps F: 𝔽_2^n → 𝔽_2^m. Concretely, we want an F and an A = A(m,n)> 0 as small as possible, so that for every affine map L: 𝔽_2^n → 𝔽_2^m (of the form $L(x) = M x + b $) we have: agree(F, L) := |{ x ∈ 𝔽_2^n | F(x) = L(x) }| ≤ A. Such questions have been studied by Nyberg (1991,1993), Carlet and Ding (2004,2007), Liu, Mesnager and Chen (2017), Nagy (2025), and Biryukov, Turecek, and Udovenko (2026). There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is: A(m,n) = Θ(2^n−m + 2^n/2), and in particular, is never smaller than 2^n/2. In this work, we show how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we show how to construct for every γ>0, a function F: 𝔽_2^n → 𝔽_2^m with m = O_γ(n), achieving A(m,n) ≤ (1 + γ)^n. Surprisingly, we even achieve the same quantitative behavior for the much harder question of having low agreement with m-tuples of degree d polynomials Q: 𝔽_2^n → 𝔽_2^m, with m = O_γ, d(n). Here the previously best bounds were of the form A(m,n) = O( 2^−n/(2^d+1) · 2^n ) of Ben-Sasson and Kopparty (2010), based on Gowers-norm-type arguments. All our results generalize to all finite fields 𝔽_q in place of 𝔽_2. Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets.
ER  -

Abstract

Related

Cite