Higher-order nonhomomorphicity under affine restrictions

Source abstract

We study the behavior of the $k$-th-order nonhomomorphicity of Boolean functions under restriction to affine subspaces. For odd $k\ge3$ and $0\le t<n$, we introduce the $t$-restriction $k$-th-order nonhomomorphicity $P_{k,t}(f)$, defined as the minimum of $P_k(f_{\mid A})$ over affine spaces of codimension at most $t$. For a direct sum of $m$ monomials of degrees at least two, we determine $P_{k,t}$ exactly. When $t<m$, a minimum is obtained by setting one variable equal to zero in each of the $t$ monomials of lowest degree. When $m\le t<n$, the minimum is zero. The proof combines multiplicativity of even Walsh moments with a contraction argument for affine restrictions. We establish a general formula for the Walsh transform of a Boolean function restricted to an affine subspace of arbitrary codimension, yielding an exact spectral characterization of the $t$-restriction normalized nonlinearity $\rnnl_t(f)$. As odd $k$ tends to infinity, $(1-2P_{k,t}(f))^{1/(k+1)}$ converges to $1-2\rnnl_t(f)$. We further prove that every non-affine function has a hyperplane restriction with strictly smaller odd-order nonhomomorphicity. Finally, we determine $\rnnl_1(T_{d,n})$ exactly for all threshold functions with $n\ge3$. This proves the two threshold-function conjectures left open in~\cite{SergeAnaPante2025}, including the previously unresolved odd-majority case, where a minimizing hyperplane is $x_1+x_2=0$.