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

Deciding whether a system of multivariate quadratic equations over ${\mathbb{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 ${\text{MQ}}_0(n)$ and ${\text{MQ}}_1(n)$ denote the sets of square quadratic systems in $n$ variables having respectively no solutions and exactly one solution. ${\cup }_{n\ge 2}{\text{MQ}}_0(n)$ is a coNP-complete language, while ${\cup }_{n\ge 2}{\text{MQ}}_1(n)$ lies in DP. It is known that ${\lim }_{n\to \mathrm{\infty }}\mathrm{\mid }{\text{MQ}}_1(n)\mathrm{\mid }\mathrm{/}\mathrm{\mid }{\text{MQ}}_0(n)\mathrm{\mid }=1$. Here we prove the explicit finite-$n$ bounds $$\mathrm{\mid }{\text{MQ}}_0(n)\mathrm{\mid }<\mathrm{\mid }{\text{MQ}}_1(n)\mathrm{\mid }\le (1+\frac{1}{2^n-1})\mathrm{\mid }{\text{MQ}}_0(n)\mathrm{\mid },$$ More generally, let $Q_d$ be the space of polynomial functions $({\text{FF}}_2{)}^n\to {\mathbb{F}}_2$ of degree at most $d$, and let ${\alpha }_k$ count square systems in $(Q_d{)}^n$ having exactly $k$ solutions. Then $${\alpha }_0<{\alpha }_1\le (1+\frac{1}{2^n-1}){\alpha }_0,2\le d\le n\mathrm{.}$$ The proof combines matroid and coding-theoretic methods. We interpret $({\text{FF}}_2{)}^n$ as the ground set of the evaluation matroid of $Q_d$, express ${\alpha }_0$ and ${\alpha }_1$ through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push ${\alpha }_1-{\alpha }_0$ below ${\alpha }_1\mathrm{/}{2}^n$ come from the elements of a matroid port. These are identified with minimal-support words of the Reed–Muller code $\text{RM}(n-d-1,n)=\text{RM}(d,n{)}^{\perp }$; the required estimate then follows from the MacWilliams identity, the minimum-distance bound $2^{d+1}$, and the even-weight structure of the code.