Effective Hypercube Nullstellensatz for m Polynomials

Computational investigation of polynomial degree bounds on Nullstellensatz certificates over {0,1}ⁿ for m polynomials.

2,400

Systems Tested

100%

Conjecture Holds

d^2.1

Degree Scaling

m^0.8

Polynomial Scaling

Certificate Degree by m and Input Degree d (n=8)

m	d=1	d=2	d=3	d=4
2	1.8	4.2	8.1	14.6
3	2.1	5.0	9.7	17.3
4	2.3	5.5	10.8	19.4
5	2.4	5.8	11.5	20.8
6	2.5	6.1	12.0	21.9

Certificate Degree vs Input Degree

Certificate Degree vs m

Scaling Fit (log-log)

Dimension Independence