CS Paper Radar

Explicit Nonlinear Functions beyond the Fourier bound

Swastik Kopparty, Rishabh Kothary, Shanthanu S. Rai

cs.CR cs.CCmath.CO ·submitted 2026-10-05 14:00 UTC · v1
published

Abstract

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) = Θ(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: \mathbb F_2^n \to \mathbb F_2^m$ with $m = O_γ(n)$, achieving $$ A(m,n) \leq (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: \mathbb F_2^n \to \mathbb F_2^m$, with $m = O_{γ, 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.

Comment
29 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Resolving a conjecture on quadratic APN functions and a new quadratic $(n,n)$-function associated to crooked functions

cs.IT math.CO ·2026-08-24 ·Claude Carlet, Darrion Thornburgh
theory similarity 0.64
Abstract · 40 pages

We say an $(n,n)$-function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ is a crooked function if for any nonzero $a \in \mathbb{F}_2^n$, the image of $D_aF(x)=F(x)+F(x+a)$ is an affine hyperplane. The only known examples of crooked functions are all quadratic almost perfect nonlinear (APN), or equivalently, for every known crooked function, $D_aF$ is affine for all $a \in \mathbb{F}_2^n$. The ortho-derivative $π_F \colon\mathbb{F}_2^n \to \mathbb{F}_2^n$ of a crooked function $F$ is the function such that $π_F(0)=0$, and for any nonzero $a$, the set $\{0,π_F(a)\}^\perp$ is the underlying vector space of $\mathrm{Im}(D_aF)$. We prove that for $n \geq 4$ and a crooked function $F$, if $k$ is a non-negative integer such that $F$ has $2^k-1$ quadratic component functions, $π_F$ has at least $2^n-2^{n-k}$ component functions of algebraic degree $n-2$. In particular, we resolve Gorodilova's conjecture that every component function of $π_F$ has algebraic degree $n-2$ when $F$ is quadratic APN. As a second main result, for $n \geq 4$, we associate to a crooked function $F$ a quadratic function $\varepsilon_F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ that satisfies a strong geometric-combinatorial condition regarding the sums of $F$ over $2$-dimensional linear subspaces. As a corollary to both of our main results, we prove that for any even $n \geq 4$, any quadratic APN $(n,n)$-function has at least $n$ semi-bent components. Furthermore, we obtain a congruence result on a problem on $m$-sequences introduced by Johansen, Helleseth, and Kholosha, and we determine the exact algebraic degrees of some Boolean functions associated to the bent and near-bent components of particular classes of plateaued vectorial functions.

0.53

On different notions related to APN mappings

cs.IT math.CO ·2026-09-18 ·René Rodríguez-Aldama, Ajla Šehović, Enes Pasalic, Sadmir Kudin
similarity 0.51
Abstract · 30 pages, 2 figures, 3 tables. Example 3.2 has been added. As a consequence, Conjecture 3.1 was modified and renamed as Open Problem 1. The …

An APN mapping $F:\mathbb{F}_{2^n}\to \mathbb{F}_{2^n}$ is a polynomial characterized by the non-vanishing property on 2-flats. In this work, we analyze notions that are closely related to this property. To understand which $k$-flats of $\mathbb{F}_{2^n}$ remain flats under $F$, we study the $k$-breaking. The function $x^{-1}$ has been studied in the past in this context---we extend this study to general mappings and characterize the 2-breaking of APN functions. Recently, two generalizations of the APN property have been introduced: $k$-strongly non-normality and $k$-th-order sum-freedom. Sum-freedom generalizes the non-vanishing property of APN functions to higher dimensional flats. We provide in-depth observations of the relations between the breaking property, strongly non-normality and sum-freedom. We introduce a fourth concept called $k$-strongly breaking, which implies the breaking property. We derive several structural results for both notions and give a characterization of a subclass of APN functions in terms of the 2-strongly breaking property. We propose a different perspective of the non-vanishing property via a natural character transformation, which is closely related to the sum-of-square indicator of the components of $F$. We derive a precise value for the total sum of the sum-of-square indicators of $F$. With this approach, we provide a simple answer to Open Problem 4 in IEEE Trans. Inf. Theory 52(9): 4160-4170, 2006. Moreover, it allows us to explore balancedness properties of polynomials, one of which characterizes component-wise APNness, for odd $n$, and provides a natural extension to any dimension. We show that Dillon's APN permutation and the Gold functions satisfy a related property, termed $k$-balanced, which is presented under our framework.

0.34

Exponential Quantum Advantage in Testing Fourier Dimensionality

cs.CC quant-phcs.DS ·2026-09-22 ·Kenny Chen
theory similarity 0.50
Abstract · 38 pages; small fixes to existing sections, adding new sections on the tolerant version of the problem

A boolean function $f$ has Fourier dimension $k$ if its strings with nonzero Fourier coefficients span a subspace of dimension $k$. We first consider the property testing task of determining whether a function has Fourier dimension at most $k$, or is $ε$-far from being so. We show that there is an $O(k/\sqrtε)$-query quantum property tester for this problem, which we show to be almost optimal. Combined with Gopalan \etal's classical lower bound of $Ω(2^{k/2})$, this demonstrates an exponential quantum advantage for this task. We complement this result with a $\tilde{O}(2^{k/2}/ε)$ classical tester, giving a quadratic improvement over the previous best tester, and essentially settling the classical query complexity. We then introduce and study the tolerant version of this problem. That is, determining whether a function is $αε$-close to having Fourier dimension at most $k$, or is $ε$-far from being so. Perhaps surprisingly, we show that this tolerant version of the problem is essentially just as hard as the standard version of the problem. That is, we show this problem has a $\tilde{O}(k/ε)$ quantum tester, and a $\tilde{O}(2^{k/2}/ε)$ classical tester.

0.25

Generalized $p$-ary $\cPS$ Bent Functions

cs.IT cs.DM ·2026-09-16 ·Alexander Kholosha, Mohit Pal
similarity 0.50
Abstract

We use $m$-dimensional partial spreads of $\fp^{2n}$, where $p$ is an odd prime, $n$ is a positive integer and $m$ divides $n$, to construct two classes of bent functions from $\fp^{2n}$ to $\fp$. Our construction generalizes the classes of $p$-ary $\cPS^{-}$ and $\cPS^{+}$ bent functions proposed by P. Lison\v ek and H. Y. Lu (Des. Codes Cryptogr. 73 (2014), 209--216).

0.28

A Nonadaptive Sparse Fourier Transform in Every Dimension

cs.DS cs.ITmath.NA ·2026-11-19 ·Mahdi Cheraghchi, Jingyi Lyu
similarity 0.50
Abstract

Let $G=(\mathbb{Z}/2^a\mathbb{Z})^d$, of order $N=2^{ad}$. Given point-query access to any complex signal $X$ with Fourier transform $\hat{X}$ over $G$, we provide a randomized algorithm that constructs a $k$-sparse estimate $\widetilde{X}$ via non-adaptive queries such that, with large probability, $\|\widetilde{X}-\hat{X}\|_2^2 \leq C \cdot \|H_k(\hat{X})-\hat{X}\|_2^2$, for an absolute constant $C>0$, where $H_k(\cdot)$ denotes the best $k$-sparse approximation. The constant $C$ can be improved to any desired $1+\varepsilon$ by either supplying a constant-factor estimate on the $k$-sparse tail norm or allowing an arbitrarily small additive error term $δ\|\hat{X}\|_2^2$ on the right-hand side. With a supplied tail estimate, we can also satisfy an $\ell_\infty/\ell_2$ heavy hitters guarantee. For fixed $δ$, the number of samples is $O((k/\varepsilon^2)(\log N)\log(k/\varepsilon))$, and the recovery algorithm requires a polynomial in $(k/\varepsilon)\log N$ exact operations. The algorithm naturally extends to $G=(\mathbb{Z}/b^a\mathbb{Z})^d$ for any fixed integer $b>1$.

0.32

A new upper bound for Sidon sets in $\mathbb{F}_2^{4k+3}$

cs.IT math.CO ·2026-09-23 ·Darrion Thornburgh
theory similarity 0.50
Abstract · 7 pages

A subset $S \subseteq \mathbb{F}_2^n$ is called a Sidon set if no four distinct points of $S$ have zero sum. It is shown that if $n \geq 7$ and $n \equiv 3 \mod 4$, then $|S|\leq 2^{\frac{n+1}{2}}-3$. As a consequence, for any even $t \geq 4$, there does not exist a binary linear $[2^t-3,2^t-2t-2,5]$-code, strengthening a nonexistence result of Brouwer and Tolhuizen from 1993. As a second consequence, we also show that for an even integer $n \geq 4$, every almost perfect nonlinear (APN) function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ has nonlinearity at least $3$.

0.21

The APN Property of Two Families of functions over $\F_{2^{n}}$ from the Switching Construction

cs.IT ·2026-11-03 ·Chenmiao Shi, Longjiang Qu, Kangquan Li
theory similarity 0.49
Abstract

Let $m\geq5$ be odd with $3\nmid m$. Helleseth, Ichanska, and Kaleyski \cite{HIK} conjectured that two norm-perturbed Budaghyan--Helleseth--Kaleyski functions $F_2,F_3$ over $\F_{2^{2m}}$ are APN. In this paper, we prove this conjecture. First, by using the basis $(1,β)$ of $\F_{2^{2m}}$ over $\F_{2^m}$, we show that $F_2$ and $F_3$ are EA-equivalent to two functions $\mathcal G_1$ and $\mathcal G_0$, respectively. Their derivatives can be written as two trace equations for a matrix $P\in\mathrm{GL}(2,\F_{2^m})$. We then prove that these two equations have no solution. The proof uses only identities over finite fields, the characteristic polynomial of a $2\times2$ matrix, and elementary properties of Frobenius automorphisms. The repeated-root case and all parity cases are considered separately. It follows that the derivative of each function has kernel of size two in every nonzero direction, and hence both $F_2$ and $F_3$ are APN for every admissible $m$.

0.30

Optimal universal sets for submodular functions

cs.DS ·2026-11-18 ·Marek Adamczyk, Richard Ueltzen, Jan Vondrak
theory similarity 0.49
Abstract · Results obtained with the assistance of GPT-6 Astra

We resolve the question of deterministic non-adaptive algorithms for nonnegative submodular maximization: We prove that for every $n \geq 2$ and $ε\in (0,\frac{1}{4})$, there is a polynomial-size family ${F}_{n,ε}$, $|{F}_{n,ε}| = n^{O(1/ε^2 \log (1/ε))}$, such that for every nonnegative submodular function $f:2^{[n]} \to {\bf R}$, $\max_{S \in {F}_{n,ε}} f(S) \geq (1/4 - ε) \max_{S \subseteq [n]} f(S)$. It is also easy to show that a factor better than $1/4$ cannot be achieved by any fixed polynomial-size family. A related result that we prove is that there is a distribution ${D}_{n,ε}$ supported on polynomially many subsets of $[n]$ such that $(1 - ε) {\bf E}_{R \sim {U}_n}[f(R)] \leq {\bf E}_{R \sim {D}_{n,ε}}[f(R)] \leq {\bf E}_{R \sim {U}_n}[f(R)]$, where ${U}_n$ is the uniform distribution on $2^{[n]}$, and $f$ is any nonnegative submodular function. This is interesting in light of the fact that uniform convergence does not hold for submodular functions: Sampling polynomially many sets from ${U}_n$ and taking the empirical mean does not converge to the true expectation uniformly for all submodular functions. The construction of ${F}_{n,ε}$ and ${D}_{n,ε}$ is based on a new semidefinite extension of submodular functions: We show that the Goemans-Williamson rounding technique for a near-orthogonal arrangement of vectors gives a value close to the uniform expectation, and this rounding can be derandomized, since near-orthogonal vectors can be constructed in logarithmic dimension.

0.09