Metraipolis › archive › dc_b462e7c7e752
Linearity bounds for APN functions — arXiv:2609.35689
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35689
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T23:29:19.165Z
- SHA-256 of the archived text
31ae38830d71dc0baa91e4f7f92a2959bc8a354038d168524aad57f1f6b54311- Stable URL of this page
https://metraipolis.com/documento/dc_b462e7c7e752
How to cite
Linearity bounds for APN functions — arXiv:2609.35689 — arXiv (en), https://arxiv.org/abs/2609.35689 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b462e7c7e752 (Metraipolis archive dc_b462e7c7e752, sha256 31ae38830d71dc0baa91e4f7f92a2959bc8a354038d168524aad57f1f6b54311)
BibTeX
@misc{dcb462e7c7e752,
title = {Linearity bounds for APN functions — arXiv:2609.35689},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35689},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b462e7c7e752; sha256 31ae38830d71dc0baa91e4f7f92a2959bc8a354038d168524aad57f1f6b54311},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35689. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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-10$ in even dimension and at most $N-6$ in odd dimension. This improves the general upper bound of $N-6$ in even dimension and $N-4$ in odd dimension. 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/\sqrt{k}$ as $n\to\infty$. The second and fourth largest coefficients are at most $2\lfloor N/3\rfloor$ 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 $\mathcal{L}(F)^2\le N(1+\sqrt{q(N-1)})$, so that $\mathcal{L}(F)/N\to1$ implies $q/N\to1$. In even dimension, for every $1/2\le C<1$, the condition $q\le(4C-C^2-1)N/4+1$ implies $\mathcal{L}(F)\le CN$. In particular, $q\le3N/16+2$ implies $\mathcal{L}(F)\le N/2$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.35689 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.871Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).