# Nonlinearity of Boolean functions

The nonlinearity of a Boolean function measures how far it is from being a linear Boolean function. It is the smallest Hamming distance of its truth table to that of a linear. As an integer it is a soft property (i.e. dependent on arity). But it can be easily defined as a fraction, which is a hard property.
    arity $a$, soft nonlinearity $n$, hard nonlinearity ${\frac {n}{2^{a}}}$
Let $b=2^{a-1}-2^{{\frac {a}{2}}-1}$. The highest nonlinearity for arity $a$ is $\lfloor b\rfloor$. A Boolean function with nonlinearity $b$ is a bent function. They exist when $b$ is an integer, i.e. for even $a$.
The finite sequences A207676 and A207328 show the nonlinearities for arities 3 and 4. (The indices encode the truth tables.)
For a given arity the nonlinearity is an integer. They are the column indices of the following number triangle.
triangle Hazel with integer nonlinearity :
| arity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | total |
| arity | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | total |
| 1 | 4 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 4 |
| 2 | 8 | 8 | | | | | | | | | | | | | | | | | | | | | | | | | | | | 16 |
| 3 | 16 | 128 | 112 | | | | | | | | | | | | | | | | | | | | | | | | | | | 256 |
| 4 | 32 | 512 | 3840 | 17920 | 28000 | 14336 | 896 | | | | | | | | | | | | | | | | | | | | | | | 65536 |
| 5 | 64 | 2048 | 31744 | 317440 | 2301440 | 12888064 | 57996288 | 215414784 | 647666880 | 1362452480 | 1412100096 | 556408832 | 27387136 | | | | | | | | | | | | | | | | | 4294967296 |
| 6 | 128 | 8192 | 258048 | 5332992 | 81328128 | 975937536 | 9596719104 | 79515672576 | 566549167104 | 3525194817536 | 19388571496448 | 95180260073472 | 420379481991168 | 1681517927964672 | 6125529594728448 | 20418431982428160 | 62526600834171264 | 176395152249028608 | 458313050588725248 | 1087405010755682304 | 2291582136636334080 | 4011570131804454912 | 5097726702198767616 | 3821934098435833856 | 1305039828998603264 | 103868560519987200 | 1617838297055232 | 347227553792 | 5425430528 | 18446744073709551616 |
But the columns make more sense, when the nonlinearity is defined as a fraction:
| arity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | total |
| arity | $0$ | ${\frac {1}{64}}$ | ${\frac {1}{32}}$ | ${\frac {3}{64}}$ | ${\frac {1}{16}}$ | ${\frac {5}{64}}$ | ${\frac {3}{32}}$ | ${\frac {7}{64}}$ | ${\frac {1}{8}}$ | ${\frac {9}{64}}$ | ${\frac {5}{32}}$ | ${\frac {11}{64}}$ | ${\frac {3}{16}}$ | ${\frac {13}{64}}$ | ${\frac {7}{32}}$ | ${\frac {15}{64}}$ | ${\frac {1}{4}}$ | ${\frac {17}{64}}$ | ${\frac {9}{32}}$ | ${\frac {19}{64}}$ | ${\frac {5}{16}}$ | ${\frac {21}{64}}$ | ${\frac {11}{32}}$ | ${\frac {23}{64}}$ | ${\frac {3}{8}}$ | ${\frac {25}{64}}$ | ${\frac {13}{32}}$ | ${\frac {27}{64}}$ | ${\frac {7}{16}}$ | total |
| 1 | 4 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 4 |
| 2 | 8 | | | | | | | | | | | | | | | | 8 | | | | | | | | | | | | | 16 |
| 3 | 16 | | | | | | | | 128 | | | | | | | | 112 | | | | | | | | | | | | | 256 |
| 4 | 32 | | | | 512 | | | | 3840 | | | | 17920 | | | | 28000 | | | | 14336 | | | | 896 | | | | | 65536 |
| 5 | 64 | | 2048 | | 31744 | | 317440 | | 2301440 | | 12888064 | | 57996288 | | 215414784 | | 647666880 | | 1362452480 | | 1412100096 | | 556408832 | | 27387136 | | | | | 4294967296 |
| 6 | 128 | 8192 | 258048 | 5332992 | 81328128 | 975937536 | 9596719104 | 79515672576 | 566549167104 | 3525194817536 | 19388571496448 | 95180260073472 | 420379481991168 | 1681517927964672 | 6125529594728448 | 20418431982428160 | 62526600834171264 | 176395152249028608 | 458313050588725248 | 1087405010755682304 | 2291582136636334080 | 4011570131804454912 | 5097726702198767616 | 3821934098435833856 | 1305039828998603264 | 103868560519987200 | 1617838297055232 | 347227553792 | 5425430528 | 18446744073709551616 |
reduced rows :
| arity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | total |
| arity | $0$ | ${\frac {1}{64}}$ | ${\frac {1}{32}}$ | ${\frac {3}{64}}$ | ${\frac {1}{16}}$ | ${\frac {5}{64}}$ | ${\frac {3}{32}}$ | ${\frac {7}{64}}$ | ${\frac {1}{8}}$ | ${\frac {9}{64}}$ | ${\frac {5}{32}}$ | ${\frac {11}{64}}$ | ${\frac {3}{16}}$ | ${\frac {13}{64}}$ | ${\frac {7}{32}}$ | ${\frac {15}{64}}$ | ${\frac {1}{4}}$ | ${\frac {17}{64}}$ | ${\frac {9}{32}}$ | ${\frac {19}{64}}$ | ${\frac {5}{16}}$ | ${\frac {21}{64}}$ | ${\frac {11}{32}}$ | ${\frac {23}{64}}$ | ${\frac {3}{8}}$ | ${\frac {25}{64}}$ | ${\frac {13}{32}}$ | ${\frac {27}{64}}$ | ${\frac {7}{16}}$ | total |
| 1 | 1 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 1 |
| 2 | 1 | | | | | | | | | | | | | | | | 1 | | | | | | | | | | | | | 2 |
| 3 | 1 | | | | | | | | 8 | | | | | | | | 7 | | | | | | | | | | | | | 16 |
| 4 | 1 | | | | 16 | | | | 120 | | | | 560 | | | | 875 | | | | 448 | | | | 28 | | | | | 2048 |
| 5 | 1 | | 32 | | 496 | | 4960 | | 35960 | | 201376 | | 906192 | | 3365856 | | 10119795 | | 21288320 | | 22064064 | | 8693888 | | 427924 | | | | | 67108864 |
| 6 | 1 | 64 | 2016 | 41664 | 635376 | 7624512 | 74974368 | 621216192 | 4426165368 | 27540584512 | 151473214816 | 743595781824 | 3284214703056 | 13136858812224 | 47855699958816 | 159518999862720 | 488489069016963 | 1378087126945536 | 3580570707724416 | 8495351646528768 | 17902985442471360 | 31340391654722304 | 39825989860927872 | 29858860144029952 | 10195623664051588 | 811473129062400 | 12639361695744 | 2712715264 | 42386176 | 144115188075855872 |
unit fractions :
| arity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | total |
| arity | ${\frac {1}{64}}$ | ${\frac {1}{32}}$ | ${\frac {1}{16}}$ | ${\frac {1}{8}}$ | ${\frac {1}{4}}$ | total |
| 1 | | | | | | 0 |
| 2 | | | | | 1 | 1 |
| 3 | | | | 8 | 7 | 15 |
| 4 | | | 16 | 120 | 875 | 1011 |
| 5 | | 32 | 496 | 35960 | 10119795 | 10156283 |
| 6 | 64 | 2016 | 635376 | 4426165368 | 488489069016963 | 488493495819787 |
| arity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | nonlinearity | total |
| arity | ${\frac {1}{64}}$ | ${\frac {1}{32}}$ | ${\frac {1}{16}}$ | ${\frac {1}{8}}$ | ${\frac {1}{4}}$ | total |
| 1 | | | | | | 0 |
| 2 | | | | | 1 | 1 |
| 3 | | | | 1 | 7 | 8 |
| 4 | | | 1 | 15 | 875 | 891 |
| 5 | | 1 | 31 | 4495 | 10119795 | 10124322 |
| 6 | 1 | 63 | 39711 | 553270671 | 488489069016963 | 488489622327409 |
nonlinearity

## Zhegalkin deviation

The terminology used here is likely to be changed again.
Each BF can be assigned a Zhegalkin index – a unique integer, independent of arity. Its binary exponents shall be called Zhegalkin exponents. For Walsh functions they are only powers of two (see here). For negated Walsh functions also 0. Here is a way to define a different kind of Hamming distance from linears: The Zhegalkin exponents of the BF are split into those that are 0 or powers of two, and those that are not. So one BF is split in two BF, which shall be called its Zhegalkin linear and deviation. The Zhegalkin weight of the deviation (the number of Zhegalkin exponents that are not 0 or powers of two) is also a degree, to which the BF is not linear.
Zhegalkin linear (reverse prefect)  Z.l. signed weight (reverse prefect signed weight)
Zhegalkin deviation (twin prefect)  Z.d. faction (twin prefect signed weight)  Z.d. weight 
Z.d. patron  Z.d. is odious
reverse and twin prefect signed weight