A Note on Binary Quadratic Systems and their relation to complexity theory Gabriele Radici∗
Massimiliano Sala†
September 9, 2026
arXiv:2609.07769v1 [cs.IT] 7 Sep 2026
Abstract Deciding whether a system of multivariate quadratic equations over F2 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 MQ0 (n) and MQ1 (n) denote the sets of square quadratic systems in n variables having respectively no solutions and exactly one solution. ∪n≥2 MQ0 (n) is a coNP-complete language, while ∪n≥2 MQ1 (n) lies in DP. It is known that limn→∞ |MQ1 (n)|/|MQ0 (n)| = 1. Here we prove the explicit finite-n bounds 1 |MQ0 (n)|, |MQ0 (n)| < |MQ1 (n)| ≤ 1 + n 2 −1 We find of interest that the two previous inequalities are equivalent to the existence of some injections MQ0 (n) ,→ MQ1 (n) (whose images omit at most a 2−n fraction of MQ1 (n)). Whether such an injection can be given explicitly, or computed or inverted in polynomial time, is open. More generally, let Qd be the space of polynomial functions (F2 )n → F2 of degree at most d, and let αk count square systems in (Qd )n having exactly k solutions. Then 1 α0 , 2 ≤ d ≤ n. α0 < α1 ≤ 1 + n 2 −1 The proof combines matroid and coding-theoretic methods. We interpret (F2 )n as the ground set of the evaluation matroid of Qd , 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 /2n 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)⊥ ; the required estimate then follows from the MacWilliams identity, the minimum-distance bound 2d+1 , and the even-weight structure of the code.
1
Introduction
In this paper we will present results of an algebraic, geometric and combinatorial nature, but which may open the path to results in complexity theory. These results are also connected to post-quantum cryptography. The reader unfamiliar with complexity theory will find in Section 8 a collection of notions and statements useful to understand the connection with our algebraic results. Let F denote the finite field with 2 elements, usually denoted by F2 or GF(2). Deciding whether a system of multivariate quadratic equations over F has (at least) a solution is a classical NP-complete problem [7, 10]. As shown in Section 8, NP-completeness persists when ∗ †
Department of Mathematics, University of Trento, Italy. [email protected] Department of Mathematics, University of Trento, Italy. [email protected]
1
one restricts to square systems, that is, to systems with as many equations as variables. Beyond its complexity-theoretic status, the hardness of this problem (in the more general finite-field setting) is the main hardness assumption underlying multivariate post-quantum cryptography. For example, of the nine candidates advanced by NIST to the third round of its additional digital signature process in May 2026, four are variants of the Unbalanced Oil and Vinegar scheme [12]: UOV itself, MAYO [2], QR-UOV [8] and SNOVA [21], whose security rests on the difficulty of solving systems of quadratic equations over a finite field [16]. For n ≥ 2, let MQ0 (n) and MQ1 (n) denote the sets of square quadratic systems S in n variables over F having respectivelySno solutions and exactly one solution. The language n≥2 MQ0 (n) is coNP-complete, whereas n≥2 MQ1 (n) belongs to DP, not known to be either in NP or coNP. S Moreover, n≥2 MQ1 (n) is coNP-hard and, under randomized reductions, NP-hard. For the unique satisfiability problem these are the theorems of Blass and Gurevich [3] and of Valiant and Vazirani [20]; their transfer to square quadratic systems is discussed in Section 8. The two families have remarkably close cardinalities. It is known [9] that |MQ1 (n)| lim = 1. n→∞ |MQ0 (n)| Here we prove the explicit finite-n bounds |MQ0 (n)| < |MQ1 (n)| ≤ 1 +
1 n 2 −1
|MQ0 (n)|.
(1)
Therefore, with only a relative excess of order 2−n , a uniformly-random square quadratic system is more likely to have exactly one solution than none. The two inequalities in (1) are equivalent to the existence of an injection MQ0 (n) ,→ MQ1 (n) ,
for any n ≥ 2 ,
whose image omits at most a 2−n fraction of MQ1 (n). Whether such an injection can be given explicitly, or computed/inverted in polynomial time, is open: an injection of that kind would relate a coNP-complete language to a language in DP. While we make no complexity-theoretic claim in this paper, in Section 8 we will discuss some consequences. Our result for quadratic systems is a special case of the more general statement that we prove in this paper. Let n ≥ 2, V = Fn , N = |V | = 2n and write Q := F[x1 , . . . , xn ]/⟨x2i − xi ⟩ for the ring of polynomial functions V → F. For 0 ≤ d ≤P n, let Qd ⊆ Q be the subspace of functions of degree at most d, of dimension D = D(n, d) = dj=0 nj . A square system of degree ≤ d is an n-tuple F ∈ (Qd ) n with variety X(F ) ⊆ V , that is, F = (f1 , . . . , fn ) ∈ (Qd ) n ,
X(F ) := {v ∈ V | f1 (v) = · · · = fn (v) = 0}.
For 0 ≤ k ≤ N , set αk = αk (n, d) := {F ∈ (Qd ) n : |X(F )| = k} . Thus, for d = 2, |MQk (n)| = αk (n, 2).
2
Our main result is the following. Theorem 1.1 (restated with proof as Theorem 7.1). Let n ≥ 2 and 2 ≤ d ≤ n. Then (i) α1 − α0 ≤
α1 , N
with equality if and only if d = n; (ii) α1 > α0 ; (iii) if d ≤ n − 2, then α1 N D−3 α1 − ≤ α1 − α0 ≤ , N 3 N hence
1−
α1 (N − 1)(N − 2)(2N + 3) N D−1 ≥ N D−4 ≥ ; N 6 4 4 3N 2
α1 α1 ≤ α1 − α0 ≤ . N N
Theorem 1.1 specializes for quadratic systems to (1), since α1 1 α1 − α 0 ≤ ⇐⇒ α1 ≤ 1 + α0 . N N −1 The equality in its upper bound occurs if and only if n = 2. Two boundary cases of Theorem 1.1 are classical. For d = n, Qn is the space of all functions V → F, the number of solutions of a uniformly random square system is exactly binomial with parameters N and 1/N [11, Theorem 1], and (i) holds with equality; by Theorem 1.1(i) itself, d = n is the only degree ≥ 2 for which the number of solutions is binomial (compare [11, Corollary 3.6]: the events “F vanishes at v”, v ∈ V , are independent only in that case), which is what makes the case d < n non-trivial. For d = 1 the number of solutions of a random square linear system over F has the classical distribution governed by the rank of a random matrix [13, Chapter 3], and there the inequality goes the other way: α0 > α1 for every n ≥ 3 (Remark 7.2). So the hypothesis d ≥ 2 in Theorem 1.1 cannot be dropped. We briefly describe the proof. Section 2 collects the facts on matroids that we use. In Section 3, the point set V is made into a matroid M by declaring S ⊆ V independent when the evaluation vectors of its points on Qd are linearly independent. Inclusion–exclusion then gives α0 = χM (N ),
α1 = N χM/v (N ),
where χ denotes the characteristic polynomial and v ∈ V is arbitrary. In Section 4, a sign-reversing involution in the spirit of Whitney’s broken-circuit theorem, adapted to the port of M at v, shows that the only terms that can push α1 − α0 below α1 /N come from the minimal sets of the port of odd cardinality. More precisely, if µj denotes the number of minimal sets of the port of cardinality j, we obtain X α1 α1 − α 0 ≥ − µj N D+1−j . N j odd
In Section 5, these minimal sets are identified with the minimal-support words through v of the Reed–Muller code RM(n − d − 1, n) = RM(d, n)⊥ ,
3
so that the µj become weight-enumerator coefficients. In Section 6 the resulting error term is controlled through the MacWilliams identity: the minimum distance 2d+1 ≥ 8 implies agreement with the corresponding binomial model through the first seven moments, while the even-weight structure gives the required sign for the upper bound, and a sixth-moment estimate makes the error term small enough. Section 7 assembles these ingredients into a proof of Theorem 1.1, and shows that its hypothesis d ≥ 2 cannot be dropped. Finally, in Section 8 some comments are given on the relation between the research carried out in this paper and complexity theory.
2
Preliminaries on matroids
Matroids, introduced by Whitney [24], abstract linear dependence; we refer to [22, 18] for the basic theory. We use the rank-function axiomatization. Definition 2.1. A matroid M is a pair (E, r), where E is a finite set, the ground set, and r : 2E → Z≥0 satisfies, for all A, B ⊆ E: (R1) 0 ≤ r(A) ≤ |A|; (R2) if A ⊆ B then r(A) ≤ r(B); (R3) r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B). The rank of M is r(M ) := r(E). Matroids are also usually defined by axioms on the independent sets; the two axiomatizations are equivalent, in the following sense. Theorem 2.2 ([24, 22]). Call I ⊆ 2E an independence system if • ∅ ∈ I; • subsets of members of I are in I; • if I, J ∈ I and |I| < |J| there is e ∈ J \ I with I ∪ {e} ∈ I. The assignments r 7−→ Ir := {I ⊆ E : r(I) = |I|},
I 7−→ rI (A) := max{|I| : I ⊆ A, I ∈ I}
are mutually inverse bijections between the functions r : 2E → Z≥0 satisfying (R1)–(R3) and the independence systems on E. Remark 2.3. The correspondence must be stated in this form. It is not true that an arbitrary r : 2E → Z≥0 satisfies (R1)–(R3) as soon as Ir is an independence system: for E = {1, 2} and r(∅) = 0, r({1}) = r({2}) = 1, r({1, 2}) = 5 one gets Ir = {∅, {1}, {2}}, which satisfies the three axioms, while r violates (R1). What recovers r from Ir is the displayed formula r = rIr , valid for rank functions. Notation: If not better specified, throughout all the paper M will denote a matroid (E, r). By some abuse of notation, we will write S ∈ M , if S ∈ 2E , and T ⊆ M , if T ⊆ 2E . From [22] and [24], we also bring the following definition and basic facts on matroids. Definition 2.4. Let M = (E, r) be a matroid with rank function r. We define: 1. Independent sets: I := {I ⊆ E : r(I) = |I|}; the other subsets are dependent. 4
2. Bases: maximal independent sets. 3. Circuits C(M ): minimal dependent sets. 4. Loop: e ∈ E with r({e}) = 0. 5. Coloop: e ∈ E with r(E \ {e}) = r(E) − 1. 6. Two non-loops e ̸= f are parallel if r({e, f }) = 1. 7. Closure: cl : 2E → 2E , cl(A) := {e ∈ E : r(A ∪ {e}) = r(A)}. 8. Deletion: for T ⊆ E, M \ T is the matroid on E \ T with rank rM \T (A) = r(A). 9. Contraction: for T ⊆ E, M/T is the matroid on E \ T with rank rM/T (A) = r(A ∪ T ) − r(T ). P 10. Characteristic polynomial: χM (λ) = A⊆E (−1)|A| λr(M )−r(A) . Remark 2.5. The following are standard [22, 18]. (a) All bases have cardinality r(M ). (b) A subset C ⊆ E is a circuit iff r(C) = |C| − 1 and r(C \ {e}) = |C| − 1 for all e ∈ C. (c) The closure operator cl : 2E → 2E satisfies the following properties. For any set S ⊆ E: • Extensivity: S ⊆ cl(S); • Monotonicity: if S ⊆ S ′ then cl(S) ⊆ cl(S ′ ); • Idempotency: cl(cl(S)) = cl(S). (d) If I is independent and e ∈ cl(I) \ I, then I ∪ {e} contains exactly one circuit, and that circuit contains e. It is called fundamental circuit, we denote it as I e . (e) rM/T is still a rank function. We have that, since A ∩ T = ∅ and submodularity of r, r(A ∪ T ) − r(T ) ≤ |A|. To prove submodularity of rM/T , one notices that r(A ∪ B ∪ T ) + r((A ∩ B) ∪ T ) = r((A ∪ T ) ∪ (B ∪ T )) + r((A ∪ T ) ∩ (B ∪ T )) ≤ r(A ∪ T ) + r(B ∪ T ). P (f) The characteristic polynomial of M \ T is χM \T = S⊆E\T (−1)|S| λr(M \T )−r(S) ; (g) The characteristic polynomial of M/T is χM/T = P = S⊆E\T (−1)|S| λr(M )−r(S∪T )
|S|−|T | λr(M )−r(S) = T ⊆S⊆E (−1)
P
Characteristic polynomials of deletion and contraction matroids provide a useful identity: Proposition 2.6 ([22, 18]). If e ∈ E is neither a loop nor a coloop, then χM (λ) = χM \e (λ) − χM/e (λ) .
3
Boolean polynomial systems as matroids
The point set V = Fn carries a matroid structure in which a set of points is independent when the corresponding evaluation functionals on Qd are linearly independent. The purpose of this section is to set that structure up and to record its one consequence that the rest of the paper uses: the numbers α0 and α1 of systems with no solution and with exactly one solution are values of the characteristic polynomial of this matroid and of one of its contractions.
5
3.1
Rank function
Let F = F2 be the field with two elements, V = Fn be the n-dimensional vector space over F, and N = 2n = |V |. Set Q := F[x1 , . . . , xn ]/⟨x2i − xi : i = 1, . . . , n⟩ and, for 0 ≤ d ≤ n, let Qd denote the space of polynomials in Q up to degree d. The dimension of Qd is d X n D= . j j=0
Let Md be the set of monomials of Qd . Since Md is a basis for Qd , Qd is isomorphic to FD . We order monomials in Md with respect to the graded lexicographic ordering. Namely, let 1 < x1 < x2 < · · · < xn , then xi11 . . . xinn < xj11 . . . xjnn (with ik , jk ∈ {0, 1}) if and only if: Pn Pn • k=1 jk ; k=1 ik < Pn Pn • k=1 ik = k=1 jk and 0 = jk < ik = 1, where k := min{k | ik ̸= jk }. Define the evaluation map ev : V → FD , ev(v) := (m(v) : m ∈ Md ). Here FD carries two roles, identified throughout by the standard scalar product: it is the space of coefficient vectors of the polynomials of Qd , and, through f 7→ f · ev(v), it is also the space of linear functionals on Qd ; the vector ev(v) is the functional “evaluate at v”. Extending ev to the power set of V by ev(S) = {ev(v) : v ∈ S} for S ⊆ V , we define the set function: r(S) := Rank(ev(S)),
for S ⊆ V.
From now on, we assume d ≥ 2. So, Remark 3.1. ev is injective, indeed ev(v) = (1, v, (m(v))m∈Md ,deg m≥2 ). Hence ev(v) = ev(w) implies v = w. Lemma 3.2. The function S 7→ r(S) is a matroid rank function on ground set V . Proof. We directly verify axioms (R1)–(R3) of Definition 2.1 for r(S): (R1): ev(S) is a collection of |S| vectors in FD . The dimension of span(ev(S)) cannot exceed the number of vectors |S| nor can it be negative, so 0 ≤ r(S) ≤ |S|. (R2): If A ⊆ B ⊆ V , then ev(A) ⊆ ev(B). Taking linear spans yields span(ev(A)) ⊆ span(ev(B)), so dim span(ev(A)) ≤ dim span(ev(B)), i.e., r(A) ≤ r(B). (R3): Let A, B ⊆ V . Set U = span(ev(A)) and W = span(ev(B)). Then U + W = span(ev(A ∪ B)). Since ev(A ∩ B) ⊆ ev(A) ∩ ev(B) ⊆ U ∩ W , we have span(ev(A ∩ B)) ⊆ U ∩ W , so r(A ∩ B) ≤ dim(U ∩ W ). Applying the standard dimension formula for vector subspaces: r(A ∪ B) + r(A ∩ B) = dim(U + W ) + r(A ∩ B) ≤ dim(U + W ) + dim(U ∩ W ) = dim U + dim W = r(A) + r(B). Corollary 3.3. (V, r) is a matroid. We call it evaluation matroid (of degree d) Remark 3.4. ev(V ) spans the whole FD (since no non-zero polynomial vanishes on all V ) hence, r(V ) = dim FD = D. Notation: Established that r is a rank function on the powerset of V , for compactness we will write rS := r(S), S ⊆ V .
6
3.2
Translation of matroid concepts
Having proven that (V, r) is a matroid, we specialize general definitions in our particular case for better understanding. 1. Independent Sets I: Point sets I ⊆ V whose monomial evaluation vectors ev(I) are linearly independent in FD . 2. Bases B(M ): Maximal point sets in V whose evaluation vectors form a vector space basis for span(ev(V )) = FD . 3. Circuits C(M ): Minimal point sets C ⊆ V exhibiting a non-trivial linear dependency P v∈C cv ev(v) = 0 over F. As shown in Section 5, these correspond to minimal support non-zero codewords in the dual Reed-Muller code RM(d, n)⊥ = RM(n − (d + 1), n). 4. Deletion M \ T : Restricting evaluation to the subset of points V \ T . 5. Contraction M/T : Projecting the coefficient space FD modulo the subspace spanned by ev(T ). P |S| D−rS . 6. Characteristic Polynomial χM (λ): S⊆V (−1) λ Concerning loops, coloops and parallel elements in the evaluation matroid, we prove that Lemma 3.5. M has no loops, and no two points are parallel. If 2 ≤ d ≤ n − 1 then M has no coloops; if d = n every point is a coloop. Proof. For any v ∈ V , ev(v) has first coordinate 1(v) = 1, so it is non-zero, hence it cannot have zero rank. v, w ∈ V are parallel iff ev(v) = ev(w), impossible since ev is injective. If 2 ≤ d ≤ n − 1 then for any v ∈ V , {f ∈ Qd : f (w) = 0 ∀w ∈ V \ {v}} = {0}, because the only function vanishing on V \ {v} and not on v is the indicator of v, of degree n; hence r(V \ {v}) = D = rV . If d = n then Qd = Q and D = N , so ev(V ) is a basis of FN and every point is a coloop.
3.3
Counting systems with 0 and 1 solutions
For S ⊆ V let HS := {f ∈ Qd : f (v) = 0 ∀v ∈ S} Let f ∈ FD represent the vector of coefficients of the polynomial f = f (v) = f · ev(v) where · is the standard scalar product of FD .
P
fi mi , by construction
This implies that HS = ev(S)⊥ = ker(ev(S)), so |HS | = 2D−rS . Let X(F ) be the variety of F ∈ (Qd )n , denoting by φ(S) := |{F ∈ (Qd )n | S ⊆ X(F )}|, we have φ(S) = |HS |n = 2n(D−rS ) = N D−rS . Indeed the space of system vanishing at least on S is (HS )n , since a system vanishes on S if and only if all its polynomials vanish on S. For k = 0, . . . , 2n , let αk := |{F ∈ (Qd )n | |X(F )| = k}| denote the number of square systems with k solutions. Recalling that rV = D, we show Theorem 3.6. In the evaluation matroid M = (V, r), for any v ∈ V : α0 = χM (N )
and 7
α1 = χM/v (N )N.
Proof. Applying inclusion-exclusion directly to the complement of the arrangement of all the (Hv )n inside FnD : α0 = FnD \
[
X
Hvn =
v∈V
S⊆V
(−1)|S|
\
Hvn =
v∈S
X
(−1)|S| |HSn | =
S⊆V
X
(−1)|S| N D−r(S) = χM (N ).
S⊆V
For identity, fix v ∈ V . Systems whose unique solution is v correspond to Hvn \ S the second n n w̸=v (Hv ∩ Hw ). By inclusion-exclusion, their cardinality is: (Hv )n \
[
((Hv )n ∩ (Hw )n ) =
=
(−1)|S|
S⊆V \{v}
w̸=v
X
X X
(−1)|S| φ(S ∪ {v}) =
\
((Hv )n ∩ (Hw )n )
w∈S
(−1)|S| N D−rS∪{v} = χM/v (N ).
S⊆V \{v}
S⊆V \{v}
Furthermore, the affine transformation group of V acts transitively on its N points, preserves degree, induces an invertible linear transformation of the coefficient space FD , and thus preserves the count for every point, yielding α1 = χM/v (N )N .
4
A sign-reversing involution and the matroid inequality
In this section M = (E, r) is an arbitrary matroid and e ∈ E is neither a loop nor a coloop and has no parallel element. We reduce λχM/e (λ) − χM (λ) to sums over two families of independent sets, and then bound it from below. The three steps are as follows. In §4.1 the difference is split along the port of M at e: the sets S with e ∈ cl(S) contribute one sum, the remaining ones another. Neither sum is alternating in a useful way, because the ranks r(S) vary with S. In §4.2 we remove that obstacle with a signreversing involution in the spirit of Whitney’s broken-circuit theorem: on each family it pairs off all but the sets carrying no active element, and paired sets have equal rank and opposite sign, so they cancel. What survives is indexed by independent sets only, on which r(S) = |S|, so both sums become polynomials in λ with explicit integer coefficients ak and bk counting fixed sets of each size. In §4.3 we bound those coefficients: each family is closed under passing to subsets, up to the members of the port itself, which gives (k + 1)ak+1 ≤ (|E| − 1 − k)ak and a matching inequality for the bk with an error term µk+1 counting the elements of the port of size k + 1. Pairing consecutive terms then makes the first sum non-negative and the second small, which is Theorem 4.16.
4.1
Matroid ports
Lehman firstly introduced the port of a matroid in 1964 in a work on Shannon’s Switching Game [14]. Definition 4.1. Let e ∈ E, then the e-port of M , or the port of M at e, is the set of circuits containing e, without e. Pe := {C \ {e} | C ∈ C(M ), e ∈ C} Elements of Pe are called minimals of e. We define the upfilter generated by it and the associated polynomial. Definition 4.2. For e ∈ E, define the e-port upfilter as Te := {S ⊆ E \ {e} | ∃ C ∈ Pe s.t. C ⊆ S} and the e-port polynomial We (λ) =
X
(−1)|S| λr(M )−r(S) .
S∈Te
8
Observation 4.3. We observe that Te = {S ⊆ E \ {e} | e ∈ cl(S)}. Indeed e ∈ cl(S) iff there exists a circuit C ⊆ S ∪ {e}, with e ∈ C. Proposition 4.4. Let M be a matroid on ground set E. Then for every non-loop e ∈ E, χM/e (λ)(λ − 1) = χM (λ) + (λ − 1)We (λ), equivalently χM/e (λ)λ − χM (λ) = χM/e (λ) + (λ − 1)We (λ).
(2)
Proof. We prove the second equality applying the formula from Proposition 2.6. For any S ⊆ E \ {e}, consider the term differences between χM/e (λ)λ and χM \e (λ), i.e. (−1)|S| (λr(M )−r(S∪{e})+1 − λr(M )−r(S) ). If e ∈ / cl(S), adjoining e increases rank by 1, yielding matching terms. If e ∈ cl(S), the difference evaluates to (λ − 1)(−1)|S| λr(M )−r(S) . χM/e (λ)λ − χM (λ) = χM/e (λ)λ − (χM \e (λ) − χM/e (λ)) X X (−1)|S| λr(M )−r(S) + (−1)|S| λr(M )−r(S∪{e}) − =λ = (λ − 1)
X
(−1)|S| λr(M )−r(S) +
X
(−1)|S| λr(M )−r(S∪{e})
S⊆E\{e}
S⊆E\{e}
S⊆E\{e}
X
|S ′ |
(−1)
λ
r(M )−r(S ′ ∪{e})
S ′ ⊆E\{e}
S⊆E\{e} e∈cl(S)
= χM/e (λ) + (λ − 1)We (λ). This can be translated in the evaluation matroid as Corollary 4.5. α1 − α 0 =
X α1 + (N − 1) (−1)|S| φ(S) N S∈Tv
Proof. Recalling that α0 = χM (N ) and α1 = χM/v (N )N (hence χM/v = αN1 ), and evaluating the formula (2) in λ = N , we get the result.
4.2
Involutions
The sign of We (λ) is hard to read off because the ranks of the sets in Te vary. We use a sign-reversing involution, in the spirit of Whitney’s broken-circuit theorem [23] and its bijective proof by Blass and Sagan [4], to rewrite each of the sums in (2) as a sum over independent sets only. Fix a total order e1 < e2 < . . . on E. For S ⊆ E and p ∈ E let S>p := {s ∈ S : s > p}. Put E0 := E and Ei := E \ {e1 , . . . , ei }, for i ≥ 1. Definition 4.6. Let i ≥ 0 and S ⊆ Ei . An element p ∈ Ei is i-active for S if p ∈ cl(S>p ). If S has an i-active element, its i-pivot is pi (S) := min{p ∈ Ei : p i-active for S} and ιi (S) := S △ {pi (S)}; otherwise ιi (S) := S. Definition 4.7. Let T ⊆ M , then Fixi (T ) := {S ∈ T | ιi (S) = S}. Observation 4.8. p ∈ cl(S>p ) if and only if there is a circuit C ⊆ S>p ∪ {p} with p ∈ C. Moreover min C = p since C \ {p} ⊆ S>p and hence exceeds p. For any ei such that p > ei , C is therefore a circuit of M \ {e1 , . . . , ei }. Lemma 4.9. Let i ≥ 0. Then: (a) the map ιi : 2Ei → 2Ei is an involution, and every non-fixed orbit consists of two sets {S, ιi (S)} with |ιi (S)| = |S| ± 1; 9
(b) if S ∈ / Fixi (2Ei ) and p = pi (S), then p ∈ cl(S \ {p}); consequently r(S ∪ X) = r(ιi (S) ∪ X) for every X ⊆ E, and in particular r(S) = r(ιi (S)); (c) any S ∈ Fixi (2Ei ) is independent, so r(S) = |S|. Proof. Involution: We prove that for any S ⊆ M , pi (S) = pi (ιi (S)). This will give that ιi (ιi (S)) = ιi (S△{pi (S)}) = (S△{pi (S)})△{pi (S)} = S, i.e. ιi is an involution. Let p = pi (S) and S ′ = ιi (S) = S△{p}. Adding or removing p changes S>q only for q < p, and ′ = S , so p remains active for S ′ . leaves S>q unchanged for q ≥ p; in particular S>p >p We claim no q < p is active for S ′ . For q < p we have S>p ⊆ S>q , hence cl(S>p ) ⊆ cl(S>q ), and since p ∈ cl(S>p ) we get p ∈ cl(S>q ); therefore cl(S>q ∪ {p}) = cl(S>q )
and
cl(S>q \ {p}) ⊆ cl(S>q ).
The equality (when p is added) shows adjoining p to S>q is closure-neutral, so it cannot bring q into the closure; the inclusion (when p is removed) shows deleting p can only shrink the closure. ′ ) would force q ∈ cl(S ), equivalently q active for S, contradicting In both directions, q ∈ cl(S>q >q the minimality of p. Hence p is the least active element of S ′ , so p(S ′ ) = p and ι is an involution. Rank preservation and sign reversal: Write A = S \ {p}, so {S, ι(S)} = {A, A ∪ {p}}. The witnessing circuit C with min C = p and C \ {p} ⊆ S>p ⊆ A shows p ∈ cl(A). Since |ι(S)| = |S| ± 1, the two members of each non-fixed orbit carry opposite signs and equal rank. Fixed points: By definition of ιi , S is fixed iff it has no i-active element. Such an S is independent: if S contained a circuit C, then p := min C would satisfy C \ {p} ⊆ S>p , hence p ∈ cl(S>p ), so p would be i-active for S, a contradiction. Hence r(S) = |S|, which is (c). Corollary 4.10 (restricted Whitney theorem). If T ⊆ 2Ei satisfies ιi (T ) = T and X ⊆ E, then X X (−1)|S| λr(M )−r(S∪X) = (−1)|S| λr(M )−r(S∪X) . S∈T
S∈Fixi (T )
In particular, taking i = 0, T = 2E and X = ∅, X χM (λ) = (−1)|S| λr(M )−|S| . S∈Fix0 (2E )
Proof. By Lemma 4.9(a),(b) the non-fixed members of T split into pairs {S, ιi (S)} with |ιi (S)| = |S| ± 1 and r(S ∪ X) = r(ιi (S) ∪ X), whose contributions cancel. For the second formula use Lemma 4.9(c) to replace r(S) by |S| on the fixed sets. We now prove the ιi -invariance of two subsets of M , that will appear in the general formula in Corollary 4.12. Lemma 4.11. Let e := e1 . The following hold: 1. Te is ι1 -invariant and for S ∈ Fix1 (Te ), r(S) = r(S ∪ {e}) = |S|; / S} is ι0 -invariant and for S ∈ Fix0 (Te ), r(S) = |S|. 2. Te := {S ∈ M \ Te | e ∈ Proof. (1): Let ι = ι1 , S ∈ Te , S ∋ p = p(S) and A = S \{p}. The closure operator is monotone and idempotent, so p ∈ cl(A) forces cl(A) ⊆ cl(A ∪ {p}) ⊆ cl(cl(A)) = cl(A), that is, cl(A ∪ {p}) = cl(A). Thus A and A ∪ {p} have the same closure cl(A); in particular cl(ι(S)) = cl(S) = cl(A) and r(ι(S)) = r(S). Consequently membership of any fixed element in the closure is unaffected by the toggle: e ∈ cl(S) ⇐⇒ e ∈ cl(A) ⇐⇒ e ∈ cl(ι(S)). 10
Hence ι maps Te to itself. The rank formula is given directly by the definition of Te and Lemma 4.9(c). / S we have S>e = S, so e ∈ cl(S>e ) would mean S ∈ Te ; (2): Let S ∈ Te . Since e ∈ thus e is not 0-active for S, p0 (S) ̸= e if it exists, and ι0 (S) ⊆ E \ {e}. If S is not fixed, cl(ι0 (S)) = cl(S) ̸∋ e, so ι0 (S) ∈ Te . Fixed members are independent by Lemma 4.9(c), and r(S ∪ {e}) = r(S) + 1 since e ∈ / cl(S). Corollary 4.12. If e := e1 is not a loop then X (−1)|S| λr(M )−r(S∪{e}) + λ χM/e (λ)λ − χM (λ) =
X
(−1)|S| λr(M )−r(S) .
S∈Fix1 (Te )
S∈Fix0 (Te )
Proof. Both Te and Te consist of subsets of E \ {e}, and 2E\{e} = Te ⊔ Te . Splitting the contraction formula of Remark 2.5 accordingly, and using r(S ∪ {e}) = r(S) for S ∈ Te (by definition e ∈ cl(S) there), gives X X χM/e (λ) = (−1)|S| λr(M )−r(S∪{e}) + (−1)|S| λr(M )−r(S) . S∈Te
S∈Te
|
{z
}
=:A(λ)
|
{z
= We (λ)
}
By Proposition 4.4, λχM/e (λ)−χM (λ) = χM/e (λ)+(λ−1)We (λ) = A(λ)+We (λ) +(λ−1)We (λ) = A(λ)+λ We (λ). Finally, Te is ι0 -invariant and Te is ι1 -invariant by Lemma 4.11, so Corollary 4.10 applies to each sum: with (i, T, X) = (0, Te , {e}) it replaces A(λ) by the sum over Fix0 (Te ), and with (i, T, X) = (1, Te , ∅) it replaces We (λ) by the sum over Fix1 (Te ). This is the stated formula. As usual, this translates as Corollary 4.13. α1 − α 0 =
X
(−1)|S| φ(S) + N
(−1)|S| φ(S).
S∈Fix1 (Tv )
S∈Fix0 (Tv )
4.3
X
The structure of the fixed families and the main inequality
Lemma 4.14. Let S ∈ Fix1 (Te ). Then S ∪ {e} contains exactly one circuit C, and e ∈ C; the set S e := C \ {e} is the unique member of Pe contained in S; and every S ′ with S e ⊆ S ′ ⊆ S belongs to Fix1 (Te ). Proof. S is independent and e ∈ cl(S) \ S, so Remark 2.5(d) gives the unique circuit C ∋ e. If P ∈ Pe and P ⊆ S, then P ∪ {e} is a circuit in S ∪ {e}, hence equals C. Let S e ⊆ S ′ ⊆ S. Then ′ ) ⊆ cl(S ) e ∈ cl(S e ) ⊆ cl(S ′ ), so S ′ ∈ Te ; and if p ∈ E1 were 1-active for S ′ then p ∈ cl(S>p >p would be 1-active for S. So S ′ ∈ Fix1 (Te ). For k ≥ 0 set ak := {S ∈ Fix0 (Te ) : |S| = k} ,
bk := {S ∈ Fix1 (Te ) : |S| = k} ,
µk := {P ∈ Pe : |P | = k} .
Then a0 = 1 (∅ ∈ Fix0 (Te ) since e is not a loop) and b0 = b1 = 0 (e is not a loop and has no parallel element). Corollary 4.12 reads λχM/e (λ) − χM (λ) = S0 (λ) + λ S1 (λ), 11
(3)
where S0 (λ) :=
X (−1)k ak λr(M )−k−1 ,
S1 (λ) :=
k≥0
X (−1)k bk λr(M )−k , k≥0
and S1 (λ) = We (λ), S0 (λ) = χM/e (λ) − We (λ) by the proof of Corollary 4.12. Lemma 4.15 (shadow bounds). For every k ≥ 0: (i) (k + 1) ak+1 ≤ (|E| − 1 − k) ak ; (ii) bk+1 ≤ (|E| − 1 − k) bk + µk+1 . Proof. (i) Fix0 (Te ) is closed under taking subsets: if S ′ ⊆ S then e ∈ / cl(S ′ ) because cl(S ′ ) ⊆ ′ cl(S), and a 0-active element of S is 0-active for S. Count the pairs (T, S) with S ∈ Fix0 (Te ), |S| = k + 1, T ⊆ S, |T | = k: each S gives k + 1 pairs, each T at most |E| − 1 − k (the supersets of T of size k + 1 in E \ {e}). (ii) Let S ∈ Fix1 (Te ), |S| = k + 1. If S ∈ / Pe , then S e ⊊ S and for x ∈ S \ S e the set S \ {x} lies in Fix1 (Te ) by Lemma 4.14. Hence every such S has a subset of size k in Fix1 (Te ), each of which has at most |E| − 1 − k supersets of size k + 1; the members of Fix1 (Te ) of size k + 1 lying in Pe number at most µk+1 . Theorem 4.16. Let M = (E, r) be a matroid and e ∈ E be neither a loop nor a coloop and have no parallel element. Then, with the notation above, P (a) S0 (|E|) = k even |E| r(M )−k−2 |E|ak − ak+1 ≥ 0; P (b) |E| S1 (|E|) ≥ − j odd µj |E| r(M )+1−j ; (c) if every member of Pe has odd cardinality, then S1 (|E|) ≤ 0. Consequently X
|E| χM/e (|E|) − χM (|E|) ≥ S0 (|E|) −
µj |E| r(M )+1−j ,
j odd
and under the hypothesis of (c) also |E|χM/e (|E|) − χM (|E|) ≤ χM/e (|E|) and S0 (|E|) ≥ χM/e (|E|). Proof. Write λ = |E|. (a) Group the terms of S0 in pairs (k, k + 1) with k even; by Lemma 4.15(i), ak+1 ≤ λak . (b) Group the terms of S1 in pairs (k, k + 1) with k even: bk λr(M )−k − bk+1 λr(M )−k−1 = λr(M )−k−1 (λbk − bk+1 ) ≥ −µk+1 λr(M )−k−1 by Lemma 4.15(ii); multiply by λ and sum, writing j = k + 1. (c) Group S1 in pairs (k, k + 1) with k odd; then µk+1 = 0, so bk+1 ≤ λbk and each pair −λr(M )−k−1 (λbk − bk+1 ) is ≤ 0. The consequences follow from (3), from λχM/e − χM = χM/e + (λ − 1)S1 , and from S0 = χM/e − S1 .
5
The port of the evaluation matroid
We now specialise Theorem 4.16 to M = (V, r) and identify the port Pv in coding-theoretic terms. The identification is the point at which Reed–Muller codes enter: the minimal sets of the port turn out to be the minimal-support words of the dual code, so the arithmetic quantities µj governing the error term become weight-enumerator coefficients. Corollary 5.1. In the evaluation matroid with d ≤ n − 1, for any v ∈ V and with ak , bk , µk computed at e = v: 12
(a) α1 − α0 ≥ S0 (N ) −
P
j odd µj N
D+1−j , and S (N ) ≥ N D−2 (N − a ); 0 1
(b) if every member of Pv has odd cardinality, then α1 − α0 ≤ α1 /N and α1 /N ≤ S0 (N ). Proof. Theorem 4.16 with |E| = N , r(M ) = D, α0 = χM (N ), α1 /N = χM/v (N ). To do this, we connect our matroid construction to coding theory via Reed-Muller codes, which have been introduced by Muller in [17]. We recall here some basic definition and properties, more can be found at [15]. Definition 5.2 ([19, 17]). For 0 ≤ d ≤ n, the binary Reed-Muller code of order d and length N = 2n , denoted RM(d, n), is the subspace of FN obtained by evaluating all multilinear polynomials in Qd at all points v ∈ V = Fn : RM(d, n) := {(f (v))v∈V | f ∈ Qd }. In particular, for quadratic systems, RM(2, n) = {(f (v))v∈V | deg(f ) ≤ 2}. Proposition 5.3. The minimum distance of RM (d, n) is 2n−d . Definition 5.4. For a linear code C ⊆ Fν , its dual code C⊥ is defined with respect to the standard dot product: X C⊥ := {c ∈ Fν | ∀c′ ∈ C, cv c′v = 0}. v∈V
The support of a codeword c ∈ Fν is supp(c) := {v ∈ V
| cv = 1}, and its Hamming weight is |c| = |supp(c)|. c is a minimal support codeword [1, 5] if there is no other word c′ ̸= 0 such that supp(c′ ) ⊆ supp(c). Proposition 5.5. The dual of the Reed-Muller code RM(d, n) is another Reed-Muller code given by: RM(d, n)⊥ = RM(n − d − 1, n). In particular, for quadratic systems, RM(2, n)⊥ = RM(n − 3, n). Theorem 5.6. A set C ⊆ V is a circuit of the Boolean evaluation matroid M = (V, r) if and only if C = supp(c) for a non-zero codeword c ∈ RM(d, n)⊥ of minimal support. P Proof. Let c ∈ Fn . By definition, c ∈ RM(d, n)⊥ if and only if v∈V cv f (v) = 0 for all f ∈ Qd . Since Qd is spanned by the monomial basis Md , this condition holds if and only if P D v∈V cv m(v) = 0 for all m ∈ Md . Under the evaluation map ev(v) = (m(v))m∈Md ∈ F , this is equivalent to: X cv ev(v) = 0 in FD . v∈V
Thus, c ∈ RM(d, n)⊥ if and only if the evaluation vectors {ev(v) | v ∈ supp(c)} are linearly dependent over F. A circuit C of M is defined as a minimal dependent set of evaluation vectors. Therefore, C is a circuit of M if and only if C = supp(c) for a non-zero codeword c ∈ RM(d, n)⊥ whose support is minimal with respect to set inclusion. Corollary 5.7. A set S ⊆ V \ {v} is an element of the v-port of M if and only if S ∪ {v} = supp(c) for some minimal support codeword c ∈ RM(n − d − 1, n). Proof. This follows directly from Theorem 5.6.
13
Corollary 5.8. Pv = {supp(c) \ {v} : c ∈ C minimal-support, v ∈ supp(c)}. Every member of Pv has odd cardinality ≥ 2d+1 − 1, and (j + 1) Amin (j + 1) Aj+1 (C) j+1 (C) µj = ≤ N N
(j ≥ 0).
Proof. The first statement is Theorem 5.6; the parity and size statements are Proposition 5.3. The affine group of V acts transitively on V , maps C onto itself and preserves minimality of supports; hence every point lies in the same number of minimal-support words of weight j + 1, and counting incidences gives N µj = (j + 1)Amin j+1 (C). Remark 5.9. It is an open problem to determine the exact distribution of minimal support codewords of RM(d, n), with d > 2, hence we cannot determine precisely the number of minimal sets in Tv . A better dissertation about this can be found in [5]. Corollary 5.8 converts the error term of Theorem 4.16(b) into a weighted enumerator of C. Throughout the rest of the paper we assume d ≥ 2 and d ≤ n − 2, so that n ≥ 4, N ≥ 16 and d(C) = 2d+1 ≥ 8; we fix v ∈ V and compute ak , bk , µk at e = v, and we put X Φ := w Aw (C) N −w . w
Lemma 5.10. ak =
N −1 k
for 0 ≤ k ≤ 6. Consequently
S0 (N ) ≥ N D−2 + N D−4
(N − 1)(N − 2)(2N + 3) , 6
X
µj N D+1−j ≤ N D+1 Φ,
j odd
and (N − 1)(N − 2)(2N + 3)/6 ≥ N 3 /4 for N ≥ 16. Proof. Circuits have size ≥ d(C) ≥ 8. Let S ⊆ V \{v}, |S| ≤ 6. Then S ∪{v} contains no circuit, so v ∈ / cl(S); and S has no 0-active element, since a 0-active p would give a circuit C ′ with C ′ \ {p} ⊆ S>p ⊆ S and |C ′ \ {p}| ≥ 7. So S ∈ Fix0 (Tv ). The bound on S0 is Theorem 4.16(a) with N −1 N −1 N −1 N −1 a0 = 1, a1 = N P −1, a2 = 2 , a3 = 3 , using −1)(N −2)(2N +3)/6. P N 2 − 3 D−j= (NP D+1−w . The (j + 1)A N = The bound on j µj N D+1−j is Corollary 5.8: j+1 w wAw N j last claim is N 3 /12 − N 2 /2 − 5N/6 + 1 ≥ 0 for N ≥ 16.
6
Bounding the weighted enumerator
P It remains to bound Φ = w wAw (C)N −w , a weighted enumerator of C = RM(n − d − 1, n) evaluated near x = 1/N . Three facts drive the estimate. First, MacWilliams duality turns Φ into an average over the dual code C⊥ = RM(d, n) of an explicit function f (Yq ) = κeλYq (N Yq − 1) of the normalised weight Yq = 1 − 2w(q)/N ∈ [−1, 1] (Lemma 6.3). Second, because C has minimum distance M = 2d+1 , the first M − 1 moments of Y over C⊥ coincide with those over the whole of FN (Lemma 6.4, a Delsarte-type orthogonality), and the full-space average of any polynomial of degree < M in Y vanishes (Lemma 6.1). Hence the Taylor polynomial of f of order M − 1 contributes nothing, and Φ is exactly the average of the Taylor remainder. Third, that remainder is controlled by a single bound on f (M ) (Lemma 6.5) together with a d count of the minimum-weight words of C (Lemma 6.2). The outcome is Φ = O(N −2 ), which for d = 2 is all that Section 7 consumes. The constants below are deliberately crude: only the exponent of N matters downstream, and no attempt is made to optimise them. 14
Lemma 6.1 (a vanishing binomial sum). For any positive integer N , N X N N −1 w N +1
w
w=0
−1 N Proof. Let a = N N +1 . Using (1 + a) =
(N − 1 − 2w) = 0
P N w P N w N −1 = w w a : w a and N a(1 + a)
N X N w a (N − 1 − 2w) = (1 + a)N −1 [(N − 1)(1 + a) − 2N a] w w=0 2N N −1 Substituting 1 + a = N2N gives (N − 1) − 2N +1 N +1 N +1 = 0.
Lemma 6.2 (minimum-weight words of C). The minimum distance of C = RM (n − d − 1, n) is M = 2d+1 . The number of minimum-weight codewords satisfies: AM ≤
N d+2 2d+1 Kd
where Kd = 2d(d+1)/2
d+1 Y
(2i − 1)
i=1
Proof. Weight-M codewords are indicator functions of (d + 1)-dimensional affine subspaces of Fn2 . The number of (d + 1)-dimensional linear subspaces is given by the Gaussian binomial coefficient: Qd (N − 2i ) n = Qd i=0 d+1 − 2i ) d+1 2 i=0 (2 Bounding the numerator by N d+1 and factoring 2i out of each term in the denominator yields: d Y
Pd
(2d+1 − 2i ) = 2
i=0 i
i=0
Thus
n
d+1 2 <
N d+2 . 2d+1 Kd
N d+1 Kd .
d d+1 Y Y (2d+1−i − 1) = 2d(d+1)/2 (2j − 1) = Kd i=0
j=1
n N Multiplying by the N/2d+1 parallel cosets yields AM = 2d+1 d+1 2 <
Lemma 6.3 (MacWilliams form of Φ). Let C⊥ = RM (d, n) and 1 N + 1 N −1 N − 1 w−1 g(w) = (N − 1 − 2w). N +1 N N +1 Then: Φ=
1 X g(w(q)) |C⊥ | ⊥ q∈C
PN
C Differentiating gives Φ = N1 ∂W ∂x (1/N,1) . Applying P MacWilliams duality [15, Ch. 5] WC (x, y) = |C1⊥ | q∈C⊥ (y + x)N −w(q) (y − x)w(q) and differentiating term-by-term yields:
Proof. Let WC (x, y) =
w=0 Aw x
w y N −w .
1 ∂ (y + x)N −w (y − x)w = N ∂x (1/N,1) w−1 1 N + 1 N −w−1 N − 1 w−1 N = (N − 1 − 2w) = N N N +1 N +1 1 N + 1 N −1 N − 1 w−1 = (N − 1 − 2w) = g(w) N +1 N N +1
15
Lemma 6.4 (Delsarte orthogonality [6]). Let Yq = 1 − 2w(q) ∈ [−1, 1]. For every integer N d+1 0 ≤ k ≤ M − 1 where M = 2 : 1 X k 1 X k Y = Yu q 2N |C⊥ | N ⊥ q∈C
u∈F2
P 1 PN qx k q·v for v = 1 + Proof. Notice that Yq = N1 N x1 x1 ,...,xk =1 (−1) x=1 (−1) . Expanding Yq = N k · · · + 1xk , where 1xi is the vector of weight 1, with non-zero entry in the i-th position. Summing over C⊥ yields the indicator function of C, evaluated on v. Namely it is non-zero if and only if v ∈ (C⊥ )⊥ = C. Because v has weight at most k ≤ M − 1 < d(C), v ∈ C ⇐⇒ v = 0. The ⊥ same holds in the second summation, for (FN 2 ) = {0}. Lemma 6.5 (derivative bound). Let f (Yq ) = g(w(q)) = κeλYq (N Yq − 1), where λ = N2 ln ξ ∈ [−1, 1]:
N +1 N −1
and κ = N 1+1
N +1 N −1 N
N −1 N +1
N/2−1
. For any M = 2d+1 and all
f (M ) (ξ) ≤ e(M + 4) Proof. Differentiating f (Y ) M times via the product rule yields f (M ) (ξ) = κeλξ L(ξ), where L(ξ) = (N ξ − 1)λM + M N λM −1 . Moreover: d (M ) f (ξ) = f (M )+1 (ξ) = κλM eλξ [N λξ + (M + 1)N − λ] dξ Evaluating the linear factor at its minimum ξ = −1 yields (M +1)N −(N +1)λ > 144−18.13 > 0 d (M ) for all N ≥ 16, M ≥ 8. Thus dξ f (ξ) > 0 on [−1, 1], proving f (M ) (ξ) is strictly increasing on [−1, 1] and maximized uniquely at ξ = 1: f (M ) (ξ) ≤ f (M ) (1) = κeλ (N − 1)λM + M N λM −1 For the constant, 1 κe = N +1 λ
N +1 N
N −1
N +1 N −1
1 = N −1
1 N −1 e 1+ < . N N −1
For the bracket, factor out λM −1 and use λ > 1: L(1) = (N − 1)λM + M N λM −1 = λM −1 (N − 1)λ + M N . P N +1 1 1 1 1 Since ln N k≥0 (2k+1)N 2k+1 , we have λ = 1 + 3N 2 + 5N 4 + · · · ≤ 1 + 2N 2 , whence −1 = 2 2 M −1 λM −1 ≤ 1 + 2N1 2 < e(M −1)/(2N ) < e, because M − 1 < 2N 2 . Moreover (N − 1)λ + M N ≤ (N − 1)(M + 4): this is (N − 1)(λ − 1) ≤ 3N − M − 3, and the left side is at most 1 while 3N − M − 3 ≥ N − 3 > 1, using M ≤ N/2. Therefore L(1) < e (N − 1)(M + 4) and f (M ) (1) = κeλ L(1) <
e · e (N − 1)(M + 4) = e2 (M + 4). N −1
The three ingredients now combine.
16
Theorem 6.6 (the bound on Φ). Let C = RM (n − d − 1, n) be a binary Reed-Muller code of length N = 2n (n ≥ 4, 2 ≤ d ≤ n − 2) with dual C⊥ = P RM (d, n). Let M = 2d+1 Qd+1 N d(d+1)/2 i −w satisfies the and Kd = 2 i=1 (2 − 1). Then the weighted sum Φ = w=1 wAw N following inequality: M! e2 (M + 4) (M − 1)!! + d+1 Φ≤ M! N 2d 2 Kd · N 2d+1 −d−2 Proof. Set M = 2d+1 . Expand f (Yq ) in its (M − 1)-th degree Taylor polynomial around Y = 0: f (M ) (ξq ) M Yq where ξq ∈ [−1, 1] M! P P Averaging over C⊥ , Lemma 6.4 implies |C1⊥ | q∈C⊥ PM −1 (Yq ) = 21N u∈FN PM −1 (Yu ). Since f (M ) (ξu ) M 1 P Yu ≥ 0, u ) = 0 by Lemma 6.1 and the Taylor remainder RM (Yu ) = u∈FN PM −1 (YP M! 2N 1 we have Φ = |C⊥ | q∈C⊥ RM (Yq ). Applying Lemma 6.5 gives: f (Yq ) = PM −1 (Yq ) +
e2 (M + 4) 1 X M Φ≤ Yq M! |C⊥ | ⊥ q∈C
Expanding the M -th moment into character indicators v = 1x1 + · · · + 1xM : 1 1 X M Yq = M |{(x1 , . . . , xM ) | v ∈ C}| ⊥ N |C | ⊥ q∈C
d
Since wt(v) ≤ M = d(C), v ∈ C if and only if v = 0 (contributing (M − 1)!!N 2 paired tuples) or v ∈ C \ {0} (contributing M !AM weight-M tuples). Substituting Lemma 6.2 for AM : d+2 N 2d + M ! (M − 1)!!N X 1 (M − 1)!! M! 2d+1 Kd M Yq ≤ = + d+1 d+1 d 2 2 |C⊥ | N N 2 Kd · N 2d+1 −d−2 ⊥ q∈C
2
+4) Multiplying by e (M completes the proof. M!
Corollary 6.7. For any 2 ≤ d ≤ n − 2, Φ < 3N1 4 . Proof. Let bd represent the bound of the previous Theorem, then for any d ≥ 2, bd ≤ b2 , since the power of N grows exponentially. Explicitly computing b2 we have that for d = 2, M = 23 = 8, K2 = 23 · 21 = 168, 2d = 4, and 2d+1 − d − 2 = 4. Hence it evaluates to: 40320 12e2 105 + 30 1620e2 1 12e2 105 + = = < Φ≤ 40320 N 4 8 · 168 · N 4 40320 N4 40320N 4 3N 4
7
Proof of the main theorem
We can now prove Theorem 1.1, restated here as Theorem 7.1. The three cases d = n, d = n − 1 and d ≤ n − 2 are handled separately: the first two are direct computations, and only the last needs the machinery of Sections 4–6. A final remark shows that the hypothesis d ≥ 2 cannot be dropped. 17
Theorem 7.1. Let n ≥ 2 and 2 ≤ d ≤ n. Then (i) α1 − α0 ≤ α1 /N , with equality if and only if d = n; (ii) α1 > α0 ; (iii) if d ≤ n − 2, then α1 N D−3 α1 α1 (N − 1)(N − 2)(2N + 3) N D−1 − ≤ α 1 − α0 ≤ , ≥ N D−4 ≥ , N 3 N N 6 4 and hence 1 − 3N4 2 αN1 ≤ α1 − α0 ≤ αN1 . Proof. Case d = n. Qd = Q is the space of all functions V → F, so a system is an arbitrary map V → Fn and α0 = (N − 1)N , α1 = N (N − 1)N −1 (choose the unique zero and the non-zero values elsewhere; equivalently, the number of solutions is binomial with parameters N, 1/N , cf. [11, Theorem 1]). Thus α1 − α0 = α1 /N > 0. Case d = n − 1 (n ≥ 3). Here C = RM(0, n) = {0, 1}, so the only circuit is V and Tv = {V \ {v}}; moreover r(V \ {v}) = D by Lemma 3.5, so φ(V \ {v}) = 1 and Wv (N ) = (−1)N −1 = −1. Corollary 4.5 gives α1 − α0 = α1 /N − (N − 1) < α1 /N . Also α1 /N ≥Q|GL(n, F)| > N − 1 (every invertible linear system has 0 as its unique zero, and |GL(n, F)| = i<n (2n − 2i ) > 2n − 1 for n ≥ 2), so α1 > α0 . Case d ≤ n − 2. Then n ≥ 4, N ≥ 16 and d(C) = 2d+1 ≥ 8. By Corollary 5.8 every member of Pv has odd cardinality, so Corollary 5.1(b) gives α1 α1 α1 − α0 ≤ and S0 (N ) ≥ . N N By Corollary 5.1(a), Lemma 5.10 and Proposition 6.6, α1 − α0 ≥ S0 (N ) −
X
µj N D+1−j ≥ S0 (N ) − N D+1 Φ ≥
j odd
α1 N D−3 − . N 3
For the lower bound on α1 /N , note that α1 /N = χM/v (N ) = S0 (N ) + S1 (N ) by (3) and P Theorem 3.6, and S1 (N ) ≥ − N1 j odd µj N D+1−j ≥ −N D Φ ≥ −N D−4 /3 by Theorem 4.16(b), Lemma 5.10 and Proposition 6.6. Hence, by Lemma 5.10, α1 1 (N − 1)(N − 2)(2N + 3) ≥ N D−2 1 − + N D−4 N 3N 2 6 D−1 N (N − 1)(N − 2)(2N + 3) ≥ N D−4 ≥ . 6 4 Therefore N D−3 /3 ≤ 3N4 2 · αN1 , which proves (iii), and (ii) follows since α1 > 0. Strictness in (i) for d ≤ n − 2. Since α1 − α0 = α1 /N + (N − 1)Wv (N ) (Corollary 4.5), it suffices to show Wv (N ) < 0. The value Wv (N ) = S1 (N ) does not depend on the order chosen on V , so we may choose it: let P0 ∈ Pv have the minimum cardinality m (odd) and order V so that v comes first and the elements of P0 next. Then P0 ∈ Fix1 (Tv ): an element p ∈ P0 cannot be 1-active since P0 is independent, and an element p ∈ / P0 ∪ {v} has (P0 )>p = ∅. Hence bm ≥ 1, and in the proof of Theorem 4.16(c) the pair (m, m + 1) contributes −N D−m−1 (N bm − bm+1 ) ≤ −N D−m−1 (N − (N − 1 − m))bm < 0, all other pairs being ≤ 0. So S1 (N ) < 0. Remark 7.2. The hypothesis d ≥ 2 cannot be dropped. For d = 1 a system is an affine map S(x) = Ax + b with A ∈ Fn×n and b ∈ Fn , so D = n + 1 and the N D systems correspond to the pairs (A, b). The set S −1 (0) is empty when b ∈ / ℑA and is otherwise a coset of ker A, of size n−rank A 2 ; hence, writing gr for the number of A of rank r, α0 =
n X
gr N − 2r ,
α1 = N gn = N |GL(n, F)|,
r=0
18
Q i since a unique solution means rank A = n, and then every b occurs. Now gr = nr 2 r−1 i=0 (N −2 ), Qn−3 and writing P = i=0 (N − 2i ) one has (N −1)( N −1) N 3N 2 , g = (N − 1)P gn−2 = P. gn = P 3N n−1 4 2 4 , 3 Keeping only the terms r = n − 1 and r = n − 2 of α0 (all terms are non-negative, and the term r = n vanishes) gives 2 N N α0 ≥ gn−1 N2 + gn−2 3N = (N − 1)P − α1 = 38 P N 3 , 4 2 4 , so that
4N 2 − 6N + 2 α0 ≥ > 1 ⇐⇒ N 2 − 6N + 2 > 0, α1 3N 2 which holds for N ≥ 8. Hence α0 > α1 for every n ≥ 3, the reverse of the inequality of Theorem 7.1. (For n = 1, 2 one computes (α0 , α1 ) = (1, 2) and (21, 24), so α0 < α1 there; the ratio α0 /α1 increases to 4/3.) Proof of (1). Apply Theorem 7.1 with d = 2 and n ≥ 2, and use α1 − α0 ≤ α1 /N ⇐⇒ α1 ≤ (1 + N 1−1 )α0 . Equality on the right holds iff d = n, i.e. iff n = 2.
8
Remarks on complexity
We record the elementary facts used in the introduction. A quadratic system over F is a tuple F = (f1 , . . . , fm ) with fi ∈ Q2 (in some number n of variables), and X(F ) ⊆ Fn is its set of solutions. A polynomial-time map F 7→ F ′ between systems is parsimonious if |X(F ′ )| = |X(F )|. Proposition 8.1 (squaring). Let F be a quadratic system over F in n variables with m equations. (a) If m ≤ n, appending n − m equations 0 = 0 gives an n × n system with the same solution set. (b) If m > n, adjoining m − n variables not occurring in any equation gives an m × m system whose solution set is X(F ) × F m−n ; this is square but not parsimonious, the number of solutions being multiplied by 2 m−n . (c) If m > n, replacing a pair of equations f = 0, g = 0 by w + f = 0,
u + g = 0,
w + u + wu = 0
in two new variables w, u, and iterating m − n times, gives a (2m − n) × (2m − n) system with the same number of solutions. All three maps are computable in polynomial time. Proof. Only (c) needs a word. For each x the first two equations force w = f (x) and u = g(x), and w + u + wu = 0 holds iff w = u = 0; so the solutions of the new system are in bijection with those of the old one, and the equations are in Q2 . One step replaces two equations by three and adds two variables, so it leaves the number of equations minus the number of variables one lower than before: starting from the surplus m − n > 0, after m − n steps the system has m + (m − n) = 2m − n equations in n + 2(m − n) = 2m − n variables, hence is square. Proposition 8.2 (clauses). There is a parsimonious polynomial-time map from CNF formulas to quadratic systems over F. 19
Proof. Identify a literal ℓ in the variables x1 , . . . , xn with the affine function xi or 1 + xi , so that ℓ is true iff the function equals 1. For a clause C = ℓ1 ∨ · · · ∨ ℓk , k ≥ 2, introduce variables z1 , . . . , zk−2 and the equations z1 +ℓ1 +ℓ2 +ℓ1 ℓ2 = 0,
zj +zj−1 +ℓj+1 +zj−1 ℓj+1 = 0 (2 ≤ j ≤ k−2),
zk−2 +ℓk +zk−2 ℓk +1 = 0
(for k = 2 the single equation ℓ1 + ℓ2 + ℓ1 ℓ2 + 1 = 0; for k = 1 the equation ℓ1 + 1 = 0). Since a ∨ b is the function a + b + ab, the first k − 2 equations force zj = ℓ1 ∨ · · · ∨ ℓj+1 for every assignment of the xi , and the last one holds iff C is satisfied. The equations are in Q2 , and an assignment of the xi extends to a solution of the system in exactly one way iff it satisfies C, in no way otherwise. Doing this for every clause, with disjoint sets of auxiliary variables, gives the map. Corollary 8.3. Let MQ0 (n), MQ1 (n) be as in the introduction. (a) S Deciding whether a square quadratic system over F has a solution is NP-complete; hence n≥2 MQ0 (n) is coNP-complete. S (b) n≥2 MQ1 (n) is in DP, is coNP-hard, and is NP-hard under randomized polynomial-time reductions. Proof. Propositions 8.2 and 8.1 compose to a parsimonious polynomial-time reduction φ 7→ Fφ from CNF-SAT to square quadratic systems: φ has exactly s satisfying assignments iff Fφ has exactly s solutions. (a) Membership in NP is clear, hardness follows from the reduction (or from [7]), and the complement of an NP-complete language is coNP-complete. (b) A square system has exactly one solution iff it has at least one (an NP property) and at most one (a coNP property: two distinct solutions are a certificate of failure); so the language is in DP. The reduction maps the unique-satisfiability language {φ : φ has exactly one satisfying assignment} S into n MQ1 (n) and its complement into the complement, so it is a many-one reduction from unique satisfiability, which is coNP-hard [3] and NP-hard under randomized reductions [20]. By Theorem 7.1, for every n ≥ 2 there exist injections MQ0 (n) ,→ MQ1 (n) whose images omit at most a 2−n fraction of MQ1 (n). Nothing in this paper says how to compute such an injection; an injection computable in polynomial time, together with a polynomial-time inverse on its image, would give a rather unusual kind of reduction between a coNP-complete language and a language in DP. We leave this as an open question.
Acknowledgements These results are included in the first author’s MSC thesis, supervised by the second author. Several of the numerical claims were checked by computer algebra with the assistance of Anthropic Claude and OpenAI ChatGPT, which also reviewed the arguments and assisted with some proofs.
20
References [1] Alexei Ashikhmin and Alexander Barg. Minimal vectors in linear codes. IEEE Transactions on Information Theory, 44:2010–2017, 1998. [2] Ward Beullens. MAYO: Practical post-quantum signatures from oil-and-vinegar maps. In Selected Areas in Cryptography — SAC 2021, volume 13203 of Lecture Notes in Computer Science, pages 355–376. Springer, 2022. [3] Andreas Blass and Yuri Gurevich. On the unique satisfiability problem. Information and Control, 55:80–88, 1982. [4] Andreas Blass and Bruce E. Sagan. Bijective proofs of two broken circuit theorems. Journal of Graph Theory, 10:15–21, 1986. [5] Yuri Borissov and Nickolai Manev. Minimal codewords in linear codes. Serdica Mathematical Journal, 30, 01 2004. [6] Philippe Delsarte. Four fundamental parameters of a code and their combinatorial significance. Information and Control, 23:407–438, 1973. [7] Aviezri S. Fraenkel and Yaacov Yesha. Complexity of problems in games, graphs and algebraic equations. Discrete Applied Mathematics, 1:15–30, 1979. [8] Hiroki Furue, Yasuhiko Ikematsu, Yutaro Kiyomura, and Tsuyoshi Takagi. A new variant of unbalanced oil and vinegar using quotient ring: QR-UOV. In Advances in Cryptology — ASIACRYPT 2021, Part IV, volume 13093 of Lecture Notes in Computer Science, pages 187–217. Springer, 2021. [9] Giordano Fusco and Eric Bach. Phase transition of multivariate polynomial systems. Mathematical Structures in Computer Science, 19:9–23, 2009. [10] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [11] Ritik Jain. The number of solutions of a random system of polynomials over a finite field. arXiv preprint arXiv:2409.06866, 2024. https://arxiv.org/abs/2409.06866. [12] Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced oil and vinegar signature schemes. In Advances in Cryptology — EUROCRYPT 1999, volume 1592 of Lecture Notes in Computer Science, pages 206–222. Springer, 1999. [13] Valentin F. Kolchin. Random Graphs, volume 53 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1999. [14] Alfred Lehman. A solution of the shannon switching game. Journal of the Society for Industrial and Applied Mathematics, 12(4):687–725, 1964. [15] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes, volume 16 of North-Holland Mathematical Library. North-Holland, 1977. [16] Dustin Moody, Gorjan Alagic, Maxime Bros, Pierre Ciadoux, Quynh Dang, Thinh Dang, John Kelsey, Jacob Lichtinger, Yi-Kai Liu, Carl Miller, Rene Peralta, Ray Perlner, Angela Robinson, Hamilton Silberg, Daniel Smith-Tone, and Noah Waller. Status report on the second round of the additional digital signature schemes for the NIST post-quantum cryptography standardization process. NIST Internal Report NIST IR 8610, National Institute of Standards and Technology, 2026. 21
[17] D. E. Muller. Application of boolean algebra to switching circuit design and to error detection. Transactions of the I.R.E. Professional Group on Electronic Computers, EC3(3):6–12, 1954. [18] James Oxley. Matroid Theory. Oxford University Press, 2nd edition, 2011. [19] Irving S. Reed. A class of multiple-error-correcting codes and the decoding scheme. IRE Transactions on Information Theory, 4:38–49, 1954. [20] Leslie G. Valiant and Vijay V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85–93, 1986. [21] Lih-Chung Wang, Po-En Tseng, Yen-Liang Kuan, and Chun-Yen Chou. A simple noncommutative UOV scheme. Taiwanese Journal of Mathematics, 30(3):445–479, 2026. [22] D. J. A. Welsh. Matroid Theory. Academic Press, London, 1976. [23] Hassler Whitney. A logical expansion in mathematics. Bulletin of the American Mathematical Society, 38:572–579, 1932. [24] Hassler Whitney. On the abstract properties of linear dependence. American Journal of Mathematics, 57:509–533, 1935.
22