Nonlinearity of Boolean functions

The Template:W of a Boolean function measures how far it is from being a linear Boolean function.
It is the smallest Template:W 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$, Template:Spaces soft nonlinearity $n$, Template:Spaces 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 Template:W. They exist when $b$ is an integer, i.e. for even $a$.

The finite sequences Template:Oeislink and Template:Oeislink 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.

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

arity	nonlinearity																													total
	$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}$
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

Template:Collapsible START Every entry can be divided by the first entry of the row:

arity	nonlinearity																													total
	$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}$
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

arity	nonlinearity					total
	$\frac{1}{64}$	$\frac{1}{32}$	$\frac{1}{16}$	$\frac{1}{8}$	$\frac{1}{4}$
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
	$\frac{1}{64}$	$\frac{1}{32}$	$\frac{1}{16}$	$\frac{1}{8}$	$\frac{1}{4}$
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

Template:Boolf prop 3-ary

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.

Template:Boolf prop 3-ary (reverse prefect) Template:Spaces Template:Boolf prop 3-ary (reverse prefect signed weight)

Template:Boolf prop 3-ary (twin prefect) Template:Spaces Template:Boolf prop 3-ary (twin prefect signed weight) Template:Spaces Template:Boolf prop 3-ary Template:Spaces Template:Boolf prop 3-ary binary Template:Spaces Template:Boolf prop 3-ary binary