The Fourier bound caps agreement at 2^{n/2}
The paper studies vectorial Boolean functions F: F_2^n → F_2^m, also called S-boxes in symmetric-key cryptography. The quantity of interest is maxagree(F, deg 1): the largest number of inputs x on which F(x) equals some affine map L(x) = Mx + b, minimized over all affine L. Equivalently, nonlinearity nl(F) = 2^n − maxagree(F, deg 1) counts how far F is from every affine map.
A classical route builds F from bent functions and Fourier analysis: if every nonzero projection F_y(x) = ⟨F(x), y⟩ is almost bent, then maxagree(F, deg 1) ≤ 2^n/2^m + O(2^{n/2}). The best bound this method can ever certify is A(m,n) = Θ(2^{n−m} + 2^{n/2}), which is never below 2^{n/2}. The paper shows this is not a defect of the constructions but a ceiling of the method: there exist F with large maxagree(F, deg 1) whose Fourier coefficients are all essentially as small as possible, so no Fourier-coefficient argument can push below 2^{n/2}.
Random functions are hard, but explicit ones were missing
The probabilistic method shows that for m ≥ n there exist F: F_2^n → F_2^m with maxagree(F, deg 1) ≤ poly(n), and more generally maxagree(F, deg d) ≥ M(q,n,d), the number of n-variate monomials of degree at most d and individual degree at most q−1. For m = O_ε(n), a random F achieves maxagree(F, deg d) ≤ (1+ε)M(q,n,d), close to the interpolation lower bound.
The gap the paper closes is constructive: no explicit F was known to reach this regime. For m ≥ n, the Fourier method is significantly suboptimal, and the best known upper bound provable through it is 2^{n/2}. The paper's contribution is an explicit construction, not a new existence proof.
Agreement equals the number of independent sets
The construction starts from an r-uniform hypergraph H = (V, E) with V = [n] and |E| = m. Each edge e = (i_1, …, i_r) defines a monomial, and the associated function F_H: F_2^n → F_2^m is given by F_H(x)_e = ∏_{j∈[r]} x_{i_j}. The paper proves that for any 1 ≤ d < r, maxagree(F_H, deg d) = |Ind(H)|, the number of independent sets in H.
This identity converts a question about polynomial approximation into a combinatorial one: to make F_H hard, choose an r-uniform hypergraph on n vertices with m = O(n) edges that has as few independent sets as possible. The bound is obtained via Macaulay's theorem, also known as the footprint bound, which bounds the solution set of a polynomial system by the dimension of a space of polynomial functions on that set.
Disjoint unions of cliques already cross the barrier
Instantiating the framework with H as a disjoint union of n/k copies of the complete r-uniform hypergraph K_k^{(r)} yields explicit functions. For d = 1, taking r = 2 gives, for every integer k, m = ((k−1)/2)·n and maxagree(F, deg 1) ≤ (k+1)n/k. For large enough k = O_γ(1), this is at most (1+γ)n, and it goes beyond the Fourier bound for every k ≥ 6.
For general degree d, the disjoint union of hypercliques gives m/n = (1/k)·C(k, d+1) for arbitrary k and maxagree(F, deg d) = O(k n^{d/k}). The previously best bound for m = O(n) and d ≥ 2 was maxagree(F, deg d) ≤ 2^{−n/2^{d+1}}·2^n, due to Ben-Sasson and Kopparty and based on Gowers-norm-type arguments. The new bounds for constant d even bypass the d = 1 Fourier bound.
Degree-d hardness follows from a direct product lemma
The same framework extends to agreement with m-tuples of degree-d polynomials Q: F_2^n → F_2^m, where maxagree(F, deg d) is the largest number of x with F(x) = Q(x) over all such tuples. For a disjoint union H = H_1 ⊔ ⋯ ⊔ H_t of r-uniform hypergraphs, the paper proves maxagree(F_H, deg d) ≤ ∏_i |N_{H_i}(q)|, with equality at d = r−1.
This direct product behavior is exact in the framework, in contrast to the lossy general direct-product theorem of Viola and Wigderson. It is what lets the construction scale: the agreement bound multiplies across components while the output dimension m adds, so m = O_{γ,d}(n) suffices to reach maxagree(F, deg d) ≤ (1+γ)n for every fixed γ > 0 and d ∈ N.
The construction generalizes to all finite fields
All results extend from F_2 to F_q. Over F_q, non-multilinear monomials appear, and the combinatorial problem becomes a multiset analogue: instead of edges versus independent sets, one counts multisets of edges versus a multiset analogue of independent sets. The disjoint-union-of-cliques instantiation still yields explicit functions that go below the Fourier bound, with |M_{H_clique(k,r),q}| and maxagree(F_{H_clique(k,r),q}, deg d) given by inclusion–exclusion sums over k and r.
For q > r, the formulas simplify: |M_{H_clique(k,r),q}| = C(k+r−1, r)·(n/k) and maxagree(F_{H_clique(k,r),q}, deg d) ≤ C(k+r−1, r−1)^{n/k} for d < r, with equality at d = r−1.
Cliques are optimal for d = 1 but not for d ≥ 2
For d = 1, the framework reduces to finding graphs with m edges minimizing independent sets, and a theorem of Sah, Sawhney, Stoner and Zhao shows the disjoint union of constant-size cliques is optimal. For larger d, the disjoint union of constant-size complete hypergraphs is not optimal. For sufficiently large fixed d, Turán hypergraphs beat the clique construction: with |M_{H_Turán(k,r),q}| = λ·(n/k)·C(k+r−1, r) and |N_{H_Turán(k,r)}(q)| ≤ C(k, r)^{n/k}, where λ ≤ 2/(1+⌊(r+1)/2⌋) + o(1).
Turán hypergraphs are not always optimal either. For d = 2 and m = n, an ad hoc 8-vertex 3-uniform hypergraph H* gives maxagree = 1^{115n/8} via disjoint unions, beating every other construction the authors know in that regime. The paper states it is not clear what the optimal extremal family of r-uniform hypergraphs is for the underlying question, and discusses the limitations of the hypergraph framework in an appendix.
The practical threshold is k ≥ 6 for degree 1
For a reader deciding whether this construction is relevant, the operative comparison is between the Fourier bound's floor of 2^{n/2} and the new explicit bound of (1+γ)n at output ratio m = O_γ(n). The degree-1 instantiation crosses that floor as soon as k ≥ 6, where the disjoint union of cliques gives maxagree(F, deg 1) ≤ (k+1)n/k. The degree-d analogue is stronger still: for constant d it bypasses the d = 1 Fourier bound entirely, and the exact direct-product equality at d = r−1 makes the agreement bound predictable from the component hypergraphs rather than merely upper-bounded.
The open edge is quantitative, not qualitative. For d = 1 the framework's limits are understood because cliques are optimal; for d ≥ 2 the best choice among hypergraphs is unsettled, with Turán hypergraphs winning for large fixed d and an ad hoc H* winning for d = 2 at m = n. Readers comparing constructions should therefore track which hypergraph family is used, since the same framework yields different agreement bounds depending on that choice.
Sources used in this answer
Explicit Nonlinear Functions beyond the Fourier bound
The paper gives the first explicit construction of vectorial maps F: F_2^n → F_2^m with m = O_γ(n) achieving maxagree(F, deg 1) ≤ (1+γ)n for every γ>0, going below the classical Fourier bound of Θ(2^{n−m} + 2^{n/2}), and extends the same quantitative behavior to agreement with m-tuples of degree-d polynomials.