Odd order nonhomomorphicity decreases on affine restrictions of boolean functions
Higher-order nonhomomorphicity under affine restrictions
Information Theory
Summary
This paper studies a special property of Boolean functions called "odd-order nonhomomorphicity," which measures how far a function is from being a simple affine function. The authors analyze how this property changes when restricting a function to smaller affine spaces defined by setting some variables. They find exact formulas for this change in many cases and prove that every non-affine function becomes simpler on some smaller affine subspace. They also solve remaining conjectures for popular threshold functions, identifying the best way to restrict these functions to reduce complexity.
What this means in practice
- •For cryptography engineers: Optimize Boolean functions to improve cryptographic primitives by understanding how complexity behaves under affine restrictions.
- •For coding theory developers: Use exact spectral characterizations of restricted Boolean functions to design error-correcting codes with better structural analysis.
A theory result. No direct application yet.
Authors
Serge Feukoua, Ana Sălăgean, Pantelimon Stănică
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$.