A Note on Binary Quadratic Systems and their relation to complexity theory

Deciding whether a system of multivariate quadratic equations over F 2 has a solution is a classical NP-complete problem, and remains so for square systems, with as many equations as variables. The hardness of this problem is one of the cornerstones of nowadays post-quantum cryptography. Let 0(n) and 1(n) denote the sets of square quadratic systems in n variables having respectively no solutions and exactly one solution. n at least 2 0(n) is a coNP-complete language, while n at least 2 1(n) lies in DP. It is known that n to infinity 1(n)/ 0(n)=1. Here we prove the explicit finite- n bounds 0(n)< 1(n) (1+ 1 over 2 n-1) 0(n), More generally, let Q d be the space of polynomial functions (2) n to F 2 of degree at most d, and let α k count square systems in (Q d) n having exactly k solutions. Then α 0<α 1 (1+ 1 over 2 n-1)α 0,, 2 d n,. The proof combines matroid and coding-theoretic methods. We interpret (2) n as the ground set of the evaluation matroid of Q d, express α 0 and α 1 through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push α 1-α 0 below α 1/2 n come from the elements of a matroid port. These are identified with minimal-support words of the Reed--Muller code (n-d-1,n)= (d,n); the required estimate then follows from the MacWilliams identity, the minimum-distance bound 2 d+1, and the even-weight structure of the code.