Linearity bounds for APN functions
Abstract
For n≥5, let F:𝔽2n→ 𝔽2n be almost perfect nonlinear and write N=2n. It is proven that the linearity ℒ(F) of F, i.e., the largest absolute Walsh coefficient of a nonzero component, is at most N−6. If n is even, it is further proven that ℒ(F)≤ N−√N/4−2. These bounds improve the general upper bound of N−4 in odd dimension and N−6 in even dimensions n ≥ 10. It is further proven that, for each fixed k, the k-th largest absolute Walsh coefficient among nonzero components, counted with multiplicity, is at most (1+Ok(2−n))N/√k as n→∞. The second and fourth largest coefficients are at most 2⌊ N/3⌋ and N/2, respectively. Finally, a bound on the linearity in terms of the number q of nonplateaued nonzero components is derived. In odd dimension, for q>0, we have ℒ(F)2≤ N(1+√(q(N−1))), so that ℒ(F)/N→1 implies q/N→1. In even dimension, for every 1/2≤ C<1, the condition q≤(4C−C2−1)N/4+1 implies ℒ(F)≤ CN. In particular, q≤3N/16+2 implies ℒ(F)≤ N/2.
Related
- Upper Bounds and Fekete–Szegö Problem for Bi-Univalent Functions Involving Bazilevič and λ-Pseudo Functions Related to Lucas-Balancing Polynomials
- Lower Bounds for Moments of L-functions
- Explicit upper and lower bounds on certain functions related to ζ(s) for s>1
- Bounds on Whittaker Functions for GL(n)
- Lower Bounds for Localised Moments of Automorphic L-functions
BibTeX
@misc{beierle2026linearity,
title = {{Linearity bounds for APN functions}},
author = {Christof Beierle and Lukas Kölsch},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.35689},
eprint = {2609.35689},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35689},
}
RIS
TY - UNPB
TI - Linearity bounds for APN functions
AU - Christof Beierle
AU - Lukas Kölsch
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2609.35689
UR - https://arxiv.org/abs/2609.35689
AB - For n≥5, let F:𝔽_2^n→ 𝔽_2^n be almost perfect nonlinear and write N=2^n. It is proven that the linearity ℒ(F) of F, i.e., the largest absolute Walsh coefficient of a nonzero component, is at most N−6. If n is even, it is further proven that ℒ(F)≤ N−√N/4−2. These bounds improve the general upper bound of N−4 in odd dimension and N−6 in even dimensions n ≥ 10. It is further proven that, for each fixed k, the k-th largest absolute Walsh coefficient among nonzero components, counted with multiplicity, is at most (1+O_k(2^−n))N/√k as n→∞. The second and fourth largest coefficients are at most 2⌊ N/3⌋ and N/2, respectively. Finally, a bound on the linearity in terms of the number q of nonplateaued nonzero components is derived. In odd dimension, for q>0, we have ℒ(F)^2≤ N(1+√(q(N−1))), so that ℒ(F)/N→1 implies q/N→1. In even dimension, for every 1/2≤ C<1, the condition q≤(4C−C^2−1)N/4+1 implies ℒ(F)≤ CN. In particular, q≤3N/16+2 implies ℒ(F)≤ N/2.
ER -