View source for Nonlinearity of Boolean functions

{{Boolf header}}

The {{w|Nonlinearity (disambiguation)|nonlinearity}} of a Boolean function measures how far it is from being a [[linear Boolean function]].<br>
It is the smallest {{w|Hamming distance}} of its truth table to that of a linear.<br>
As an integer it is a [[Soft properties of Boolean functions|soft property]] <small>(i.e. dependent on arity)</small>.
But it can be easily defined as a fraction, which is a [[Hard properties of Boolean functions|hard property]].<br>
: arity <math>a</math>, {{spaces|3}} soft nonlinearity <math>n</math>, {{spaces|3}} hard nonlinearity <math>\frac{n}{2^a}</math>

Let <math>b = 2^{a-1} - 2^{\frac{a}{2} - 1}</math>. The highest nonlinearity for arity <math>a</math> is <math>\lfloor b \rfloor</math>.<br>
A Boolean function with nonlinearity <math>b</math> is a {{w|bent function}}. They exist when <math>b</math> is an integer, i.e. for even <math>a</math>.

<small style="opacity: .5;">The finite sequences {{oeislink|A207676}} and {{oeislink|A207328}} show the nonlinearities for arities 3 and 4. <small>(The indices encode the truth tables.)</small></small>

For a given arity the nonlinearity is an integer. They are the column indices of the following number triangle.

{{Boolf triangle Hazel/integers}}

{{Boolf triangle Hazel/sources}}

But the columns make more sense, when the nonlinearity is defined as a fraction:

{{Boolf triangle Hazel}}

{{Collapsible START|reduced rows|collapsed light gap-below}}
Every entry can be divided by the first entry of the row:
{{Boolf triangle Hazel/reduced rows}}
{{Collapsible END}}

{{Collapsible START|unit fractions|collapsed light}}
{{Boolf triangle Hazel/reduced rows/unit fractions}}
Every entry can be divided by the first entry of the column:
{{Boolf triangle Hazel/reduced rows/unit fractions/reduced columns}}
{{Collapsible END}}

'''{{Boolf prop 3-ary|nonlinearity}}'''

==Zhegalkin deviation==

<small style="opacity: .5;">The terminology used here is likely to be changed again.</small>

Each BF can be assigned a [[Zhegalkin matrix|Zhegalkin index]] &ndash; a unique integer, independent of arity.<br>
Its binary exponents shall be called Zhegalkin exponents. For Walsh functions they are only powers of two <small style="opacity: .7;">([[c:File:Variadic logical connectives with up to 5 arguments; XOR twin.svg|see here]])</small>. For negated Walsh functions also 0.<br>
Here is a way to define '''a different kind of Hamming distance from linears''':<br>
The Zhegalkin exponents of the BF are split into those that are 0 or powers of two, and those that are not.<br>
So one BF is split in two BF, which shall be called its Zhegalkin linear and deviation.<br>
The Zhegalkin weight of the deviation <small>(the number of Zhegalkin exponents that are not 0 or powers of two)</small> is also a degree, to which the BF is not linear.

'''{{Boolf prop 3-ary|Zhegalkin linear}}''' <small style="font-size: 60%; opacity: .5;">(reverse prefect)</small> {{spaces|4}}
{{Boolf prop 3-ary|Zhegalkin linear signed weight|Z.l. signed weight}} <small style="font-size: 60%; opacity: .5;">(reverse prefect signed weight)</small>

'''{{Boolf prop 3-ary|Zhegalkin deviation}}''' <small style="font-size: 60%; opacity: .5;">(twin prefect)</small> {{spaces|4}}
{{Boolf prop 3-ary|Zhegalkin deviation faction|Z.d. faction}} <small style="font-size: 60%; opacity: .5;">(twin prefect signed weight)</small> {{spaces|4}}
{{Boolf prop 3-ary|Zhegalkin deviation weight|Z.d. weight}} {{spaces|4}}
<small>
{{Boolf prop 3-ary binary|Zhegalkin deviation patron|Z.d. patron}} {{spaces|4}}
{{Boolf prop 3-ary binary|Zhegalkin deviation is odious|Z.d. is odious}}
</small>

{{Boolf prop 3-ary|reverse and twin prefect signed weight}}





[[Category:Nonlinearity of Boolean functions]]