Paper 2026/386

Determining those Boolean functions whose restrictions to affine spaces are plateaued

Darrion Thornburgh, Department of Mathematics, Vanderbilt University, USA.

Abstract

Quadratic Boolean functions (that is, Boolean functions of algebraic degree at most 2), bent Boolean functions (i.e. maximally nonlinear Boolean functions in even numbers of variables) and, as we prove in this paper, partially-bent Boolean functions (i.e. affine extensions of bent functions to linear super-spaces), share a strong property: all their restrictions to affine hyperplanes are plateaued (i.e. have a Walsh transform valued in a set of the form $\{0,\pm \lambda\}$, where $\lambda$ is a positive integer called the amplitude). In this paper we determine for any $n$ and $k<n$ the class $C^n_k$ of those $n$-variable Boolean functions whose restrictions to all $k$-dimensional affine subspaces of $\mathbb F_2^n$ are plateaued (of any amplitude). We characterize partially-bent (resp., quadratic) Boolean functions as those functions that are plateaued on any affine hyperplane (resp., any affine subspace of dimension $k$, where $3 \leq k \leq n-2$, while these are all Boolean functions for $0\leq k\leq 2$). For $n\geq 5$, each of the following classes of Boolean functions happens then to be strictly included in the next one: quadratic functions, partially-bent functions, the restrictions of partially-bent functions to affine hyperplanes, plateaued functions, the restrictions of plateaued functions to affine hyperplanes, and all Boolean functions. We leave open the two problems of determining exactly what are the third and fifth of these classes (we begin the study of the first of these two classes by giving a non-trivial characterization). Our characterization of partially-bent (resp., quadratic) functions extends to strongly plateaued vectorial functions. We state an open question on vectorial functions that happens to be related to an important one on crooked functions.