Nonlinearity of Boolean functions

Studies 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.

tiara Amber with integer nonlinearity
arity	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

sources

The Boolean functions with arities up to 4 have been checked with a Python script.

The numbers for arity 5 can be found here:

An analysis of cryptographically significant Boolean functions... by Etherington, 2010 (table 12 on page 32)

On the Affine Equivalence and Nonlinearity Preserving Bijective Mappings by Sertkaya and Doganaksoy, 2010 (table 2 on page 13)

Those for arity 6 here:

Analysis of Boolean functions with respect to Walsh spectrum by Uyan, 2013 (table 4.3 on page 26)

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

arity	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

Each row can be divided by its entry in column 0:

arity	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					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

Every entry can be divided by the first entry of the column:

arity	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