PaperlayerView exact revision on arXiv

Source-linked AI summary

Explicit Nonlinear Functions beyond the Fourier bound

Swastik Kopparty, Rishabh Kothary, Shanthanu S. Rai

arXiv:2610.06362v1cs.CRcs.CCmath.CO

TL;DR

For cryptography and pseudorandomness, the paper seeks functions with provably small maxagree(F, deg 1) and higher-degree analogues. The paper constructs polynomial maps using hypergraphs and applies Macaulay’s theorem to bound agreement through polynomial-system solution counts and independent sets. For every fixed γ > 0 and sufficiently large n, explicit maps with m ≥ Ωγ(n) attain maxagree(F, deg 1) ≤ (1 + γ)^n; degree-d constructions also improve earlier bounds and bypass the degree-1 Fourier bound.

  • Problem

    For cryptography and pseudorandomness, the paper seeks functions with provably small maxagree(F, deg 1) and higher-degree analogues.

    Source: §1 · p. 2

  • Method

    The paper constructs polynomial maps using hypergraphs and applies Macaulay’s theorem to bound agreement through polynomial-system solution counts and independent sets.

    Source: §1 · p. 1, §4 · p. 10

  • Results

    For every fixed γ > 0 and sufficiently large n, explicit maps with m ≥ Ωγ(n) attain maxagree(F, deg 1) ≤ (1 + γ)^n; degree-d constructions also improve earlier bounds and bypass the degree-1 Fourier bound.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The framework connects explicit low-agreement constructions to designing graphs and hypergraphs with few independent sets.

    Source: §1 · p. 1

    The optimal extremal family of hypergraphs for the framework’s degree-d question is unclear.

    Source: §5.2 · p. 22

Abstract

from arXiv · show

We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb F_2^n \to \mathbb F_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: \mathbb F_2^n \to \mathbb F_2^m$ (of the form $L(x) = M x + b $) we have: $$\mathrm{agree}(F, L) := |\{ x \in \mathbb F_2^n \mid F(x) = L(x) \}| \leq 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) = \Theta(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 $\gamma>0$, a function $F: \mathbb F_2^n \to \mathbb F_2^m$ with $m = O_{\gamma}(n)$, achieving $$ A(m,n) \leq (1 + \gamma)^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: \mathbb F_2^n \to \mathbb F_2^m$, with $m = O_{\gamma, d}(n)$. Here the previously best bounds were of the form $A(m,n) = O( 2^{-\frac{n}{2^{d+1}}} \cdot 2^n )$ of Ben-Sasson and Kopparty (2010), based on Gowers-norm-type arguments. All our results generalize to all finite fields $\mathbb F_q$ in place of $\mathbb F_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.

1 Introduction

The introduction presents explicit constructions of vectorial Boolean functions whose agreement with affine maps can beat the classical Fourier bound, and extends the goal to agreement with low-degree polynomial maps. Its approach connects algebraic solution counting with finding graphs and hypergraphs that have few independent sets.

1.1 Techniques and Related Work

  • The construction framework selects polynomial maps so agreement counting becomes bounding solutions to polynomial systems, with Macaulay’s theorem linking that count to independent sets in a hypergraph.For a (d + 1)-uniform hypergraph with n vertices and m edges, the resulting bound is precisely the number of independent sets.Source: §1 · p. 1, §1.1 · p. 3

1 Introduction

  • For m ≥ n, the best upper bound from the Fourier method is 2^(n/2), and no better upper bound was known for an explicit function.This motivates techniques beyond Fourier analysis for proving small maximum agreement.Source: §1 · p. 2
  • For every fixed γ > 0 and sufficiently large n, explicit functions with m ≥ Ωγ(n) achieve maxagree(F, deg 1) ≤ (1 + γ)^n.This improves beyond the classical Fourier bound.Source: §1 · p. 2
  • For every fixed γ > 0 and constant d, the paper gives explicit degree-d constructions that improve prior bounds and bypass the degree-1 Fourier bound.The stated output dimension is m ≥ Ωγ,d(n), for sufficiently large n.Source: §1 · p. 3

1.1 Techniques and Related Work

  • Simple disjoint unions of constant-size complete hypergraphs already yield the main qualitative results, and for d = 1 the construction beats the Fourier bound for k ≥ 6.For sufficiently large k = Oγ(1), the bound is at most (1 + γ)^n.Source: §1.1 · p. 3
  • The framework’s functions have a perfect direct product theorem for agreement with degree-d polynomials, unlike the lossy general theorem of Viola and Wigderson.Source: §1.1 · p. 4

1.2 Refinements

  • For d = 1, disjoint unions of constant-sized cliques minimize independent sets among graphs with a given number of edges, as shown by Sah, Sawhney, Stoner and Zhao [SSSZ19].Source: §1.2 · p. 4
  • For d ≥ 2, disjoint unions of complete hypergraphs are not always optimal: Turán hypergraphs can do better for sufficiently large fixed d, while an 8-vertex 3-uniform example improves known constructions for d = 2 and m = n.The paper notes that Turán hypergraphs are not always optimal either, and that the finer extremal questions remain open.Source: §1.2 · p. 4

2 Preliminaries

This section fixes notation and recalls polynomial, hypergraph, Turán-system, and Fourier-analysis tools used in the paper.

2 Preliminaries

  • For a prime power q, Fq is the field of size q; [n] means {1, 2, ..., n}, and X̄ denotes (X1, ..., Xn).Source: §2 · p. 5

2.1 Polynomials and Functions

  • Multilinear monomials correspond to subsets of [n], and the Combinatorial Nullstellensatz guarantees a nonzero evaluation when each Si has size at least ti + 1.The lemma applies to a nonzero polynomial with degXi(P) ≤ ti for each variable.Source: §2.1 · pp. 5–6

2.2 Hypergraphs

  • An r-uniform hypergraph has r-element edges; its k-shadow records k-subsets contained in edges, and an independent set contains no edge.The independence number α(H) is the size of the largest independent set.Source: §2.2 · p. 6

2.3 Hypergraph Turán Problem

  • A Turán(n,s,r) system has independence number s − 1, and T(n,s,r) is the minimum edge count among such systems.For s > r ≥ 3, determining the associated density t(s,r) is a major open problem.Source: §2.3 · p. 6

2.4 Fourier Analysis

  • For finite abelian groups, characters form a group isomorphic to the original group; for Fq, the characters form an orthonormal basis for complex-valued functions.Fourier coefficients are inner products with characters, and the unitary change of basis yields Parseval’s identity.Source: §2.4 · p. 7

3 Nonlinearity, maxagree(F, deg d), and the Fourier bound

The section defines nonlinearity through agreement with affine maps and extends the measure to degree-d polynomial tuples. It compares interpolation-based existence bounds with the ceiling of the basic Fourier method.

3 Nonlinearity, maxagree(F, deg d), and the Fourier bound

  • The section defines affine agreement and its degree-d extension, measuring nonlinearity by minimizing agreement over affine maps.Source: §3 · p. 8
  • For every F, maxagree(F, deg d) is at least M(q, n, d), the count of monomials of degree at most d and individual degree at most q−1.Source: §3 · p. 8, §3.1 · p. 9

3.1 Existence of Hard Functions

  • There exists an F with maxagree(F, deg d) ≤ (1 + ε)M(q, n, d), close to the interpolation lower bound, using a probabilistic existence argument.Source: §3 · p. 8, §3.1 · p. 9
  • For m = n and constant q,d, the stated existence estimate is O_q,d(n^{d+1} log n).Source: §3.1 · p. 9

3.2 The Basic Fourier Bound

  • The basic Fourier route cannot certify maxagree(F, deg 1) ≤ o(q^{n/2}) and is essentially best possible using only small Fourier coefficients of projections.Source: §3.2 · pp. 9–10

4 Hard Functions over F2 using Hypergraphs

This section relates agreement with low-degree polynomial tuples to independent-set counts in uniform hypergraphs and uses clique and Turán-system constructions to build explicit hard functions over F2. It gives a sparse 3-uniform hypergraph construction for low degree-2 agreement and shows that disjoint unions of hypercliques are not optimal in the sparse regime.

4.1 Hypergraph Framework

  • For every r-uniform hypergraph H and d < r, the constructed function F_H has maximum agreement with degree-d polynomial tuples exactly |Ind(H)|.The upper bound uses indestructible monomials to span functions on the agreement set; the zero tuple realizes at least one agreement for each independent set.Source: §4.1 · pp. 11–12

4.2 Instantiating the Hypergraphs

  • For F_G at degree 1, maxagree(F_G, deg 1) = 7^(n/6) ≈ 1.383^n, beating the Fourier-method agreement of 2^(n/2) ≈ 1.414^n.Source: §4.2 · p. 14
  • For every constant c, sufficiently large k gives maxagree(F_G, deg 1) ≤ 2^(n/c) with O(kn) output coordinates, but this framework cannot achieve subexponential agreement when m = O(n).The bound comes from setting k to a sufficiently large constant; the passage identifies this as a limitation of the graph framework.Source: §4.2 · p. 14
  • For fixed large d, a complete (d+1)-uniform clique construction gives polynomial agreement with degree-d tuples, while a general lower bound of Ω(n^d) is stated.The construction has O(n^(d+1)) output coordinates.Source: §4.2 · p. 14
  • For sufficiently large uniformity, the section introduces explicit disjoint unions of Turán systems as a way to beat the disjoint-clique construction.The supplied passages give no quantitative agreement bound for this improvement.Source: §4.2 · pp. 14–15
  • For fixed r, the number of independent sets in the k-uniform Turán hypergraph is much smaller than in the corresponding clique hypergraph.The section states this comparison in Lemma 4.20.Source: §4.2 · p. 16
  • H* is a 3-uniform hypergraph on 8 vertices whose edges are affine lines not passing through the origin, and it has 115 independent sets.The vertex set is F_2^3 with the origin removed.Source: §4.2 · p. 16
  • For 8|n, an explicit function F: F_2^n → F_2^n has maxagree(F, deg 2) = 115^(n/8).The construction takes n/8 disjoint copies of the 3-uniform hypergraph H* and applies the direct product lemma.Source: §4.2 · p. 17
  • With n edges, n/8 copies of H* have 115n/8 independent sets, fewer than the 11n/4 from n/4 copies of K^(3)_4.Thus disjoint unions of hypercliques are not optimal for Question 4.9 in the sparse regime.Source: §4.2 · p. 17

5 Hard Functions over Fq using Hypergraphs

The hypergraph framework extends constructions of hard functions from F2 to Fq, where a new hypergraph quantity characterizes polynomial agreement. It then uses hypergraph choices to obtain explicit functions and compare constructions.

5.1 Hypergraph Framework

  • For an r-uniform hypergraph over Fq, maxagree(FH,q, deg d) ≤ |NH(q)| for d < r, with equality at d = r − 1.When q = 2, NH(2) is the set of independent sets of H.Source: §5.1 · pp. 18–19
  • The framework’s direct product lemma lets agreement bounds for disjoint-union hypergraphs follow from the bounds for their component hypergraphs.The theorem on NH(q) underlies this lemma.Source: §5.1 · p. 20

5.2 Instantiating the Hypergraph

  • For q > r, disjoint unions of equal-sized hypercliques yield explicit functions beyond the Fourier bound, with agreement bounded using |NH(q)|.The passages state this construction and its agreement bound but do not provide the bound’s full expression.Source: §5.2 · p. 20
  • For fixed r ≥ 2 with r < q, Turán hypergraphs can outperform clique unions, while the optimal hypergraph family remains unknown.The cited construction is given for sufficiently large k and n.Source: §5.2 · pp. 21–22

A Proof of the Interpolation Bound

The proof constructs an interpolation matrix for low-degree polynomials and shows it can be evaluated at points where it is nonsingular. Those points then allow interpolation of a polynomial tuple matching the function.

A Proof of the Interpolation Bound

  • The formal matrix has rows indexed by bounded-degree monomials and entries given by evaluating each monomial at a formal input point.Its matrix-vector product expresses polynomial evaluations at chosen points.Source: A Proof of the Interpolation Bound · p. 24
  • Distinct monomials and disjoint variables prevent determinant terms from canceling, so the determinant is nonzero.The determinant has individual degree at most q − 1, allowing a field-point evaluation where it remains nonzero.Source: A Proof of the Interpolation Bound · pp. 24–25
  • The resulting points form an interpolation set, allowing a polynomial tuple to match F at every point in that set.The set has M(q, n, d) points.Source: A Proof of the Interpolation Bound · p. 25

B Proof of Existence of Hard Functions

A random-function argument bounds the probability that any degree-d polynomial tuple agrees with the sampled function on at least t points. Choosing t to make this probability less than one establishes existence of a function with agreement below t.

B Proof of Existence of Hard Functions

C Proof of the Fourier Bound

The proof relates agreement with an affine map to Fourier coefficients of a derived function. It uses character orthogonality to express that agreement in Fourier terms.

C Proof of the Fourier Bound

D.1 Over F2

Over F2, the section bounds the number of independent sets in a sparse uniform hypergraph by first finding a large independent set. It then uses this bound to state a limitation of the hypergraph framework.

D.1 Over F2

  • The proof presents the sparse-hypergraph independent-set lemma as standard and notes that a proof is included for completeness.It attributes the standard proof to.Source: §D.1 · p. 26
  • For an r-uniform hypergraph, the section establishes a lower bound on the size of an independent set and uses its subsets to lower-bound |Ind(H)|.The displayed bound is not legible enough here to report its quantitative form.Source: §D.1 · pp. 26–27
  • A probabilistic argument constructs an independent set by ordering vertices uniformly and selecting vertices according to their neighborhoods.The proof evaluates the expected size of the resulting set using indicator random variables and linearity of expectation.Source: §D.1 · p. 27
  • The resulting corollary is used to rule out certain low-agreement functions through the hypergraph framework.The supplied statement does not preserve the target bound clearly enough to specify it.Source: §D.1 · p. 27

D.2 Over Fq

Over Fq, the section lower-bounds the relevant set of vectors by relating it to independent sets of a uniform hypergraph. It also states a limitation of the corresponding hypergraph framework.

D.2 Over Fq

  • For W ∈ Ind(H), the indicator vector 1W belongs to NH(q), so |NH(q)| is at least |Ind(H)|.Source: §D.2 · p. 28
  • A lower bound on |NH(q)| follows by lower-bounding the number of independent sets, using a large independent set and its subsets.The section applies the independent-set bound to a hypergraph with at most m edges.Source: §D.2 · p. 28
  • The section states that the (d + 1)-uniform hypergraph framework cannot produce the specified low-agreement functions for any d and q.The exact agreement threshold is not legible in the supplied text.Source: §D.2 · p. 28

E Proof of Lemma 5.16

The proof of Lemma 5.16 modifies a uniform hypergraph and uses its independent sets to analyze a related set of vectors. It also uses an edge-covering property to bound the number of edges.

E Proof of Lemma 5.16

Loading 2610.06362v1…