Paper 2026/2680

(Balanced) Boolean Functions on 375 Variables with Nonlinearity Exceeding the Patterson-Wiedemann Direct-Sum Bound

Abstract

Patterson and Wiedemann [IEEE-IT 1983] constructed Boolean functions on 15 variables with nonlinearity 16276, which is strictly greater than the bent concatenation bound. Taking their direct sum with a bent function gives nonlinearity $2^{n-1}-27\cdot2^{(n-11)/2}$ for every odd $n\ge15$. Much later, Schmidt [JCT-A 2019] proved that the asymptotic maximum nonlinearity is $2^{n-1}-(1+o(1))2^{n/2-1}$ as $n\to\infty$. In this work, we construct Boolean functions $f$ on 375 variables such that the nonlinearity is greater than $2^{374}-442367\cdot2^{168}=2^{374}-2^{187}+81921\cdot2^{168}$, which exceeds the direct sum of a 15-variable Patterson-Wiedemann function and a bent function on 360 variables. To be specific, the direct sum of a 15-variable Patterson-Wiedemann function and a 360-variable bent function has nonlinearity $2^{374}-2^{187}+20\cdot2^{180}=2^{374} 2^{187}+81920\cdot2^{168}$. Thus our construction improves on this direct-sum value by more than $2^{168}$. Our construction idea is as follows. Let $H$ be the multiplicative subgroup of order $(2^{375}-1)/751$ in $\mathbb F_{2^{375}}^*$. The support of $f$ is the disjoint union of 375 prescribed cosets and a subset $B\subseteq H$. The evaluation of Gauss sums reduces the contribution of the prescribed cosets to a computation of 751 integers. The conditions on $B$ form a $0$-$1$ linear feasibility problem. Using a potential criterion for simultaneous linear constraints, we prove the existence of a single subset $B\subseteq H$ satisfying the constraints at all frequencies. Taking direct sums with bent functions extends the result to every odd $n\ge375$. The support construction does not require balancedness. As a natural follow-up, we also obtain balanced functions with the same strict lower bound by changing the minimum possible number of values, using sampling without replacement. The subsets $B$ and the sets of modified points are obtained by existence proofs.