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

• Deciding whether a quadratic system over F2 has a solution is NP-complete, and this hardness underlies multivariate post-quantum cryptography.Source: §1 · pp. 1–2
• The language of square quadratic systems with exactly one solution lies in DP and is coNP-hard, as well as NP-hard under randomized reductions.Source: §1 · p. 2
• Exactly-one-solution square quadratic systems are more numerous than unsatisfiable systems, with relative excess of order 2^-n.For a uniformly random square quadratic system, the paper says an exactly-one-solution system is more likely than a system with no solutions.Source: §1 · p. 2
• The inequalities are equivalent to injections from unsatisfiable into uniquely solvable systems; whether such an injection can be efficiently computed or inverted remains open.The paper makes no complexity-theoretic claim about such an injection.Source: §1 · p. 2
• For 2≤d≤n, the main theorem treats square systems of degree at most d, with quadratic systems as a special case.The paper defines these systems as n-tuples of degree-at-most-d polynomial functions on F2^n.Source: §1 · pp. 2–3
• At d=n the upper bound has equality, whereas for d=1, α0>α1 for every n≥3, so the theorem's d≥2 condition cannot be dropped.For d=n, the number of solutions has a binomial distribution; the cited classical result is [11], and the linear-system distribution is governed by random-matrix rank [13].Source: §1 · p. 3
• The proof builds an evaluation matroid, applies a port-adapted sign-reversing involution, then identifies minimal port sets with Reed–Muller codewords.Source: §1 · p. 3
• MacWilliams identity, minimum distance, even-weight structure, and a sixth-moment estimate control the error term for the upper bound.The stated minimum distance is at least 8, giving agreement with the binomial model through the first seven moments.Source: §1 · p. 4

2 Preliminaries on matroids

• A matroid is specified by a finite ground set and a rank function satisfying axioms (R1)–(R3).Rank is defined as r(M) = r(E).Source: §2 · p. 4
• Rank functions and independence systems determine one another through mutually inverse constructions.The independence system consists of sets whose rank equals their size; the associated rank counts the largest independent subset.Source: §2 · p. 4
• Independent sets have rank equal to size, bases are maximal independent sets, and circuits are minimal dependent sets.Closure collects elements whose addition does not increase rank.Source: §2 · pp. 4–5
• Deletion restricts the matroid to the remaining ground set, while contraction adjusts rank by adjoining the contracted set first.The section also records standard rank and closure properties and a characteristic-polynomial identity for deletion and contraction.Source: §2 · p. 5

3.1 Rank function

• The evaluation matroid on V = F2^n has rank r(S) equal to the dimension of the span of the evaluation vectors for points in S.Its full ground set has rank D, the dimension of the polynomial space Q_d.Source: §3 · p. 5, §3.1 · p. 6

3.2 Translation of matroid concepts

• The rank function makes (V, r) a matroid, with points independent exactly when their polynomial-evaluation vectors are linearly independent.For 2 ≤ d ≤ n−1 it has no loops, parallel points, or coloops; at d = n every point is a coloop.Source: §3.1 · p. 6, §3.2 · p. 7
• In this matroid, circuits are minimal dependencies among evaluation vectors, while deletion restricts the points and contraction projects the coefficient space modulo their span.The circuits correspond to minimal-support nonzero words in the dual Reed–Muller code.Source: §3.2 · p. 7

3.3 Counting systems with 0 and 1 solutions

• The counts of square systems with zero and one solutions satisfy α0 = χM(N) and α1 = NχM/v(N).The affine group acts transitively on V, so the number of systems with a specified unique solution is the same for every point.Source: §3.3 · pp. 7–8

4 A sign-reversing involution and the matroid inequality

• Splitting along the port separates sets whose closure contains e from those whose closure does not, and a Whitney-style involution cancels paired terms of equal rank and opposite sign.The remaining terms are indexed by fixed sets, which are independent and therefore have rank equal to size.Source: §4 · p. 8, §4.1 · pp. 8–9, §4.2 · pp. 9–10

4.1 Matroid ports

• The e-port consists of circuits containing e with e removed, and its minimal members supply the exception terms in the coefficient bounds.The fixed-family structure gives a unique circuit through e for the relevant sets and a corresponding minimal port member.Source: §4.1 · p. 8, §4.3 · pp. 11–12

4.2 Involutions

• The involution toggles the least active element; non-fixed pairs have opposite signs and equal rank, leaving only fixed sets for the sum.Fixed sets have no active element and are independent.Source: §4.2 · pp. 9–10

4.3 The structure of the fixed families and the main inequality

• When every member of the port has odd cardinality, S1(|E|) ≤ 0; the coefficient bounds also make S0(|E|) nonnegative.The shadow bounds control successive fixed-family counts, with an error term for port members.Source: §4.3 · p. 12

5 The port of the evaluation matroid

• Minimal sets in the evaluation-matroid port correspond to minimal-support words of RM(n−d−1, n), turning the error term into a weighted code enumerator.The dual of RM(d, n) is RM(n−d−1, n).Source: §5 · pp. 12–14
• The code connection gives α1−α0 ≤ α1/N, with α1/N bounded above by S0(N).The application uses the port members’ odd cardinality in the matroid inequality.Source: §5 · pp. 13–14
• A circuit of the evaluation matroid is exactly the support of a nonzero dual Reed–Muller codeword minimal under support inclusion.The correspondence follows because dual-code membership is equivalent to linear dependence among the evaluation vectors.Source: §5 · p. 13
• Every member of the port has odd cardinality and size at least 2^(d+1)−1.This follows from the parity and minimum-distance properties of the minimal-support codewords.Source: §5 · pp. 13–14
• For d > 2, the exact distribution of minimal-support words in RM(d, n) remains unknown, preventing precise determination of the number of minimal port sets.The paper notes that a better determination would require this weight distribution.Source: §5 · p. 14

6 Bounding the weighted enumerator

• MacWilliams duality rewrites Φ as an average over C⊥ = RM(d, n) of an explicit function of normalized codeword weight.The weighted enumerator is evaluated near x = 1/N.Source: §6 · p. 14
• Because C has minimum distance 2d+1, the first 2d moments over C⊥ match those over the full space, so the Taylor polynomial contributes nothing.The estimate therefore reduces to the Taylor remainder.Source: §6 · p. 14
• Φ = O(N^-2d), obtained by bounding the Taylor remainder and counting minimum-weight codewords of C.For d = 2, this is the order of bound used in Section 7; the constants are not optimized.Source: §6 · p. 14
• C has minimum distance 2d+1, and its minimum-weight codewords are indicator functions of (d + 1)-dimensional affine subspaces.Their count enters the bound on the Taylor remainder.Source: §6 · p. 15
• The weighted enumerator is bounded for C = RM(n − d − 1, n), with N = 2^n, n ≥ 4, and 2 ≤ d ≤ n − 2.The section states the resulting bound as Φ < 1/(3N^4) for this range.Source: §6 · p. 17

7 Proof of the main theorem

• The inequality α1 − α0 ≤ α1/N holds with equality iff d = n; when d = 2 and n ≥ 2, it is equivalent to α1 ≤ (1 + 1/(N − 1))α0, with equality iff n = 2.Source: §7 · pp. 18–19
• For d = n, the number of solutions is binomial with parameters N and 1/N, and α1 − α0 = α1/N.In this case Qd contains all functions V → F.Source: §7 · p. 18
• For d = n − 1, α1 − α0 = α1/N − (N − 1), which is strictly below α1/N.This direct computation applies for n ≥ 3.Source: §7 · p. 18
• For d ≤ n − 2, the port terms give the strict lower bound, while the estimate on their error term proves the upper bound.The proof uses the negative sign of the port sum and bounds its contribution using Φ.Source: §7 · p. 18
• The condition d ≥ 2 cannot be dropped: for d = 1, α0 > α1 for every n ≥ 3.For n = 1, 2, the respective pairs (α0, α1) are (1, 2) and (21, 24); the ratio α0/α1 increases to 4/3.Source: §7 · pp. 18–19

8 Remarks on complexity

• When a quadratic system has more equations than variables, replacing equation pairs with three equations and two new variables preserves its number of solutions and can be iterated to make it square.The construction is a polynomial-time map.Source: §8 · p. 19
• A parsimonious polynomial-time map from CNF formulas to quadratic systems is built by encoding each clause with auxiliary variables.The auxiliary equations make each satisfying assignment extend to exactly one solution, and an unsatisfied clause yields no extension.Source: §8 · pp. 19–20
• Deciding whether a square quadratic system over F has a solution is NP-complete, and the language of systems with no solutions is coNP-complete.The reduction from CNF-SAT preserves the number of satisfying assignments and solutions.Source: §8 · p. 20
• The language of square systems with exactly one solution is in DP, coNP-hard, and NP-hard under randomized polynomial-time reductions.Membership follows because having at least one solution is in NP and having at most one is in coNP.Source: §8 · p. 20
• Injections from MQ0(n) to MQ1(n) whose images omit at most a 2^-n fraction exist, but efficient computation or inversion remains open.The paper makes no complexity-theoretic claim about such an injection.Source: §8 · p. 20