Tightness of the 16 · rdeg(f)⁴ Upper Bound

Computational investigation of whether D(f) ≤ 16 · rdeg(f)⁴ is tight, analyzing 282 Boolean functions on up to 4 variables.

282

Functions Analyzed

0.25

Max Ratio (far from 1.0)

0.0078

Mean Ratio

0.0023

Median Ratio

AND/OR

Best Candidates

Tightness Analysis

Tightness Ratio: Named Function Families

D(f) vs 16*rdeg^4 Bound

AND_n Ratio Growth (n/16)

Bound Comparison for Named Functions

Detailed Results

Named Boolean Function Families

Function	n	D(f)	deg	sdeg	rdeg	16*rdeg^4	Ratio
AND_2	2	2	2	1	1	16	0.125
OR_2	2	2	2	1	1	16	0.125
AND_3	3	3	3	1	1	16	0.188
OR_3	3	3	3	1	1	16	0.188
AND_4	4	4	4	1	1	16	0.250
OR_4	4	4	4	1	1	16	0.250
PARITY_2	2	2	2	2	2	256	0.0078
PARITY_3	3	3	3	3	3	1296	0.0023
PARITY_4	4	4	4	4	4	4096	0.0010
MAJ_3	3	3	3	1	3	1296	0.0023
TRIBES_4,2	4	4	4	2	4	4096	0.0010
ADDR_4	4	3	4	2	4	4096	0.0007
NAND-d1	2	2	2	1	2	256	0.0078
NAND-d2	4	4	4	2	4	4096	0.0010

Summary Statistics

Statistic	D/(2*rdeg^4)	D/(16*rdeg^4)
Maximum	2.000	0.250
Mean	0.062	0.0078
Std Dev	0.231	0.029
Median	0.019	0.0023