Higher-order nonhomomorphicity under affine restrictions
Abstract
We study the behavior of the k-th-order nonhomomorphicity of Boolean functions under restriction to affine subspaces. For odd k≥3 and 0≤ t<n, we introduce the t-restriction k-th-order nonhomomorphicity Pk,t(f), defined as the minimum of Pk(f| A) over affine spaces of codimension at most t. For a direct sum of m monomials of degrees at least two, we determine Pk,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≤ 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 rnnlt(f). As odd k tends to infinity, (1−2Pk,t(f))1/(k+1) converges to 1−2rnnlt(f). We further prove that every non-affine function has a hyperplane restriction with strictly smaller odd-order nonhomomorphicity. Finally, we determine rnnl1(Td,n) exactly for all threshold functions with n≥3. This proves the two threshold-function conjectures left open in~\cite{SergeAnaPante2025}, including the previously unresolved odd-majority case, where a minimizing hyperplane is x1+x2=0.
Related
- Higher-Order QMC Galerkin FEM for Singular Perturbation: Reaction-Diffusion with Affine-Parametric Reaction
- The higher dimensional affine Bernstein and Plateau problems
- Hausdorff spectrum of Lyapunov exponents for higher-dimensional self-affine systems
- Affine Higher Bruhat Orders
- On the first-order deformations of seminormal affine toric varieties
BibTeX
@misc{feukoua2026higherorder,
title = {{Higher-order nonhomomorphicity under affine restrictions}},
author = {Serge Feukoua and Ana Sălăgean and Pantelimon Stănică},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15868},
eprint = {2610.15868},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15868},
}
RIS
TY - UNPB
TI - Higher-order nonhomomorphicity under affine restrictions
AU - Serge Feukoua
AU - Ana Sălăgean
AU - Pantelimon Stănică
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15868
UR - https://arxiv.org/abs/2610.15868
AB - We study the behavior of the k-th-order nonhomomorphicity of Boolean functions under restriction to affine subspaces. For odd k≥3 and 0≤ t<n, we introduce the t-restriction k-th-order nonhomomorphicity P_k,t(f), defined as the minimum of P_k(f_| 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≤ 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−2rnnl_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≥3. 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.
ER -