{
  "abstract": "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 $\\MQ_0(n)$ and $\\MQ_1(n)$ denote the sets of square quadratic systems in $n$ variables having respectively no solutions and exactly one solution. $\\cup_{n\\geq 2} \\MQ_0(n)$ is a coNP-complete language, while $\\cup_{n\\geq 2} \\MQ_1(n)$ lies in DP. It is known that $\\lim_{n\\to \\infty} |\\MQ_1(n)|/|\\MQ_0(n)|=1$. Here we prove the explicit finite-$n$ bounds \\[ |\\MQ_0(n)|<|\\MQ_1(n)| \\le \\left(1+\\frac{1}{2^n-1}\\right)|\\MQ_0(n)|, \\] More generally, let $Q_d$ be the space of polynomial functions $(\\FF_2)^n\\to\\mathbb F_2$ of degree at most $d$, and let $α_k$ count square systems in $(Q_d)^n$ having exactly $k$ solutions. Then \\[ α_0<α_1 \\le \\left(1+\\frac{1}{2^n-1}\\right)α_0\\,, \\qquad 2\\le d\\le n \\,. \\] The proof combines matroid and coding-theoretic methods. We interpret $(\\FF_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 $\\RM(n-d-1,n)=\\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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.07769",
  "author_total": 2,
  "authors": [
    {
      "name": "Gabriele Radici"
    },
    {
      "name": "Massimiliano Sala"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/7ef6a199xnrk4.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.07769",
  "fulltext_url": null,
  "id": "7ef6a199xnrk4",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.07769",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "cs.CR"
    ],
    [
      "arxiv",
      "cs.IT"
    ],
    [
      "arxiv",
      "math.AC"
    ],
    [
      "arxiv",
      "math.AG"
    ],
    [
      "arxiv",
      "math.IT"
    ],
    [
      "openalex",
      "1702|Coding theory and cryptography"
    ]
  ],
  "openalex": "W7212034157",
  "pdf_url": "https://arxiv.org/pdf/2609.07769",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-07",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/7ef6a199xnrk4.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:19:58Z",
      "native_id": "2609.07769",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.07769"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.AC",
      "subfield": "algebra-number-theory"
    }
  ],
  "title": "A Note on Binary Quadratic Systems and their relation to complexity theory",
  "title_text": "A Note on Binary Quadratic Systems and their relation to complexity theory",
  "type": "preprint",
  "updated_at": "2026-10-30T12:19:58Z",
  "url": "https://research.draconitic.com/paper/7ef6a199xnrk4",
  "venue": "arXiv",
  "versions": []
}