TOPICS
Search

Boolean Function Nonlinearity

The Boolean function nonlinearity of a Boolean function f:{0,1}^m->{0,1} is its least Hamming distance from an affine Boolean function:

nl(f)=min_(a in {0,1}^m, b in {0,1})#{x in {0,1}^m:f(x)!=a·x+b}.

Here addition and the dot product are taken modulo 2. Equivalently, this is the distance of the truth table of f from the first-order Reed-Muller code RM(1,m). Thus the largest possible nonlinearity on m variables is its code covering radius.

Wang et al. (2026) proved that the maximum for nine variables is 242.

See also

Boolean Function, Code Covering Radius, Hamming Distance, Reed-Muller Code

Explore with Wolfram|Alpha

References

Wang, Q.; Lou, Y.; and Wang, Z. "The Covering Radius of the Reed-Muller Code RM(1,9) Is 242." 13 Oct 2026. https://arxiv.org/abs/2610.17871.

Cite this as:

Weisstein, Eric W. "Boolean Function Nonlinearity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BooleanFunctionNonlinearity.html

Subject classifications