{"id":"arxiv/2609.35689","url":"https://arxiv.org/abs/2609.35689","tags":["math.CO"],"score":0,"title":"Linearity bounds for APN functions","domain":"math.CO","source":"arxiv","authors":["Christof Beierle","Lukas Kölsch"],"reviews":0,"subject":"math.CO","summary":"For $n\\ge5$, let $F\\colon\\mathbb{F}_2^n\\to \\mathbb{F}_2^n$ be almost perfect nonlinear and write $N=2^n$. It is proven that the linearity $\\mathcal{L}(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 $\\mathcal{L}(F)\\le N-\\sqrt N/4-2$. These bounds improve the general upper bound of $N-4$ in odd dimension and $N-6$ in even dimensions $n \\geq 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}