PaperlayerView exact revision on arXiv

Source-linked AI summary

Deterministic NC Quadratic Root Counting in Characteristic Two

Sanyam Agarwal, Gorav Jindal

arXiv:2609.12669v1cs.CC

TL;DR

Counting polynomial systems over F2 remains hard even when each equation has degree at most two, motivating the study of a single quadratic equation. The paper gives a deterministic logspace-uniform NC algorithm for exact root counting over every fixed finite field of characteristic two.

  • Problem

    Counting systems of polynomial equations over F2 remains hard even when every equation has degree at most two, motivating the structured task of counting roots of a single quadratic equation.

    Source: §1 · pp. 1–2

  • Method

    The algorithm separates the radical, uses the absolute trace to form a quadratic form over F2, and recovers the quotient’s type bit from a determinant modulo eight.

    Source: §1.2 · pp. 3–4, §7 · p. 12

  • Results

    The exact counting function for a single quadratic polynomial over any fixed finite field of characteristic two belongs to logspace-uniform NC.

    Source: §1 · p. 2, §7 · p. 12

  • Takeaways & Limitations

    Browder’s determinant criterion recovers the quotient’s type bit deterministically without a binary decomposition.

    Source: §1.2 · pp. 3–4

    The result assumes a fixed finite field and encoding, with the field not part of the input.

    Source: §1 · p. 2, §2 · p. 5

Abstract

from arXiv · show

Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem. More generally, counting the solutions of a system of polynomial equations over $\F_2$ is $\SharpP$-complete. Here we focus on the more structured problem of counting the solutions of a single polynomial equation. For polynomial equations over finite fields, Ehrenfeucht and Karpinski \cite{computationalcomplexityofxorandcountingproblems1990} showed a sharp difference between degrees two and three: quadratic root counting is solvable in polynomial time, while the degree-three problem is $\SharpP$-complete. Their quadratic algorithm is sequential. For fixed finite fields, Ishai et al.~\cite{ishai2012randomizing} later gave deterministic parallel algorithms in odd characteristic and randomized parallel algorithms in characteristic two. We give a deterministic $\NC$ algorithm for exactly counting the solutions of a quadratic polynomial equation over every fixed finite field of characteristic two. Our algorithm separates the radical and uses the absolute trace to realize the bit distinguishing the two nondegenerate finite-field types as the Arf invariant \cite{arf1941untersuchungen} of a quadratic form over $\F_2$. It then recovers that invariant from an integral matrix using Browder's determinant criterion \cite{browder2006complete}. This replaces the randomized canonical-form step in the algorithm of Ishai et al.

1 Introduction

The paper gives a deterministic, logspace-uniform NC algorithm for exactly counting roots of a single quadratic polynomial over any fixed finite field of characteristic two. It replaces the randomized binary-decomposition step of the prior parallel approach by recovering the quotient’s type bit from a determinant.

1.1 Background and related work

  • Quadratic root counting has a sequential polynomial-time algorithm, but the earlier parallel algorithm for characteristic two was randomized.The corresponding degree-three counting problem is #P-hard [EK90, GGL08].Source: §1 · pp. 1–2, §1.1 · p. 3

1 Introduction

  • The algorithm counts roots of a single quadratic polynomial over every fixed finite field of characteristic two using logspace-uniform NC circuits.The circuits have polynomial size, polylogarithmic depth, and O(n) output bits.Source: §1 · p. 2

1.2 Proof ideas

  • Taking the absolute trace converts the quotient over K into a quadratic form over F2 whose Arf invariant encodes the quotient’s type bit.The trace form is nondegenerate whenever the original quotient is nondegenerate.Source: §1.2 · pp. 3–4
  • Browder’s criterion recovers the Arf invariant from an integral symmetric matrix’s determinant modulo eight, avoiding binary decomposition.The determinant residue distinguishes the two types through ε(h).Source: §1.2 · pp. 3–4
  • The algorithm separates the radical, reduces to a nondegenerate quotient, and handles linear terms by homogenization.If the quadratic form is nonzero on its radical, every target fiber has size κ^(n−1); otherwise the quotient has κ^(n−2r) lifts per input.Source: §1.2 · pp. 3–5
  • The circuit evaluates a determinant for each possible positive rank in parallel, then uses the computed rank to select the relevant branch.Rank, basis, and determinant stages have polynomial size and polylogarithmic depth.Source: §1.2 · p. 5

2 Preliminaries

The preliminaries fix the finite-field and circuit conventions used throughout and establish the parallel linear-algebra tools for the algorithm. They also define the polar matrix and radical used to analyze quadratic forms.

2 Preliminaries

  • The fixed field K and its encoding make field elements constant-size, with all asymptotic bounds measured in n.Circuit families are bounded-fan-in and logspace-uniform in their matrix and vector dimensions.Source: §2 · p. 5
  • NC means logspace-uniform Boolean circuits of polynomial size and polylogarithmic depth, with polynomially many output gates allowed.Source: §2 · p. 5
  • Fixed-field arithmetic, inversion of nonzero elements, zero testing, absolute trace, and basis-coordinate conversion have constant-size, constant-depth implementations.Each is a Boolean function on a constant number of bits because the field and encoding are fixed.Source: §2 · p. 6
  • Uniform parallel routines compute rank, kernel and image bases, complementary preimages, and determinants over fixed finite commutative rings, including Z/8Z.These routines have polynomial size and polylogarithmic depth.Source: §2 · p. 6
  • The polar matrix A_q represents B_q(x,y)=q(x+y)+q(x)+q(y); its kernel is the radical, and its rank is even.A quadratic form is nondegenerate exactly when its radical is zero, equivalently when A_q is invertible.Source: §2 · pp. 6–7

3 Counting values of a homogeneous quadratic form

For homogeneous quadratic forms, the exact number of solutions at each target is determined by the radical behavior, the rank, and a bit distinguishing the nondegenerate quotient types. This gives the fiber-count formula used by the algorithm.

3 Counting values of a homogeneous quadratic form

  • The exact fiber size for a homogeneous quadratic form is expressed through its rank and one bit distinguishing the two possible nondegenerate quotient types.The section's corollary combines the radical cases with the quotient count.Source: §3 · pp. 7–8
  • If the form is nonzero on its radical, every target value has exactly κ^(n−1) preimages.The radical test can be performed by evaluating the form on a basis of the radical.Source: §3 · p. 7
  • If the form vanishes on its radical, splitting off the radical reduces the count to a nondegenerate form on a complementary subspace, with each quotient input having κ^(n−2r) lifts.Source: §3 · p. 7
  • The type bit ε(h) labels the two linear-equivalence classes in each positive even dimension and records the sign of the normalized signed trace count.For K=F2 it is the usual Arf invariant; for general K the next section identifies it with the trace form's Arf invariant.Source: §3 · p. 8

4 Recovering the type bit in deterministic parallel time

The type bit of a nondegenerate form over K is recovered through restriction of scalars to F2: the trace form has the same Arf invariant. Browder's determinant criterion then computes that invariant from a matrix modulo eight.

4 Recovering the type bit in deterministic parallel time

  • The trace form T_h over F2 is nondegenerate whenever h over K is nondegenerate.Its polar form is Tr(B_h(x,y)); nondegeneracy follows from the nondegenerate trace pairing.Source: §4 · p. 9
  • The Arf invariant of T_h equals the type bit ε(h), since their signed sums have the same sign.The trace form is obtained by representing Tr(h(x)) as a homogeneous quadratic form over F2.Source: §4 · pp. 8–9
  • For a nondegenerate quadratic form g in 2d variables over F2, Browder’s criterion determines Arf(g) from det S(g): residues 1 or 7 modulo 8 yield 0, and 3 or 5 yield 1 [Bro79, Proposition 2.15].Source: §4 · p. 10

5 Algorithm for quadratic forms

The quadratic-form algorithm tests the radical, reduces the vanishing-radical case to a nondegenerate quotient, and computes its type bit through the trace-form determinant. Fixed parallel branches accommodate the input-dependent rank.

5 Algorithm for quadratic forms

  • The algorithm computes rank and radical bases, tests whether q vanishes on the radical, and returns κ^(n−1) when it does not.When the radical test passes and rank is zero, it returns κ^n if t=0 and zero otherwise.Source: §5 · p. 10
  • For positive rank with q vanishing on the radical, it forms the nondegenerate quotient, converts it to a trace form over F2, and uses a determinant modulo eight to recover its type bit.The resulting bit and target select the exact count given by the fiber formula.Source: §5 · p. 10
  • Because the rank is input-dependent, the circuit runs one fixed branch per possible positive rank and uses the computed rank to select the relevant branch.Rank, basis, field-arithmetic, trace, and determinant stages have polynomial size and polylogarithmic depth; the output uses O(n) bits.Source: §5 · pp. 10–11

6 General quadratic polynomials

The section reduces an affine quadratic equation to homogeneous zero counts, then combines those counts to recover the number of solutions. The construction preserves logspace-uniform NC complexity.

6 General quadratic polynomials

  • The construction writes f as a homogeneous quadratic part q plus a homogeneous linear part, after absorbing any constant into t.The field variables range over K; only the auxiliary trace form is over F2.Source: §6 · p. 11
  • Homogenization handles the linear terms by relating the solutions of f(y) = t to zeros of eqt with nonzero first coordinate.Each solution y has exactly κ −1 lifts; zeros with first coordinate zero correspond to zeros of q.Source: §6 · pp. 11–12
  • Subtracting the zero count of q from that of eqt and dividing by κ −1 yields Nf(t) in logspace-uniform NC.Both counts have O(n) bits, and the division is exact.Source: §6 · p. 12

7 Conclusion

The paper gives a deterministic logspace-uniform NC algorithm for exactly counting roots of a single quadratic polynomial over any fixed finite field of characteristic two. It separates the radical, recovers the quotient type from a determinant residue, and handles linear terms by homogenization.

7 Conclusion

  • The algorithm exactly counts roots of a single quadratic polynomial over every fixed finite field of characteristic two in deterministic logspace-uniform NC.It separates the radical, forms the absolute-trace form of the nondegenerate quotient, and recovers its type from a determinant modulo eight.Source: §7 · p. 12
  • The determinant residue supplies the Arf information needed by the counting formula, avoiding construction of a binary decomposition.The fixed circuit evaluates one determinant for each possible positive rank, and the computed rank selects the relevant value.Source: §7 · p. 12
  • Homogenization handles linear terms without changing the algorithm's parallel complexity.Source: §7 · p. 12

AI Disclosure

The authors report using ChatGPT 5.6 Pro for literature review and general exploration, and for manuscript work.

AI Disclosure

  • ChatGPT 5.6 Pro was used for literature review and general exploration related to the problem.Source: AI Disclosure · p. 12
  • The tool pointed the authors to, which they describe as essential for computing the Arf invariant in deterministic NC for quadratic forms over F2.Source: AI Disclosure · p. 12
  • The authors also used the tool to polish proofs and the manuscript.Source: AI Disclosure · p. 12

A Proofs for the homogeneous counting results

The appendix derives homogeneous quadratic root counts by separating the radical from a nondegenerate quotient and using its decomposition-independent type bit. It then combines fiber counts to obtain the exact count for each target value.

A Proofs for the homogeneous counting results

B Proof of the determinant test

The proof establishes that the determinant of an integral lift, reduced modulo eight, distinguishes the two Arf-invariant types of a nondegenerate quadratic form over F2. It shows this test is unchanged by invertible changes of variables and evaluates it on a binary-block form.

B Proof of the determinant test

  • For nondegenerate g, det S(g) is odd, and its residue is 1 or 7 modulo 8 for even Arf(g), versus 3 or 5 for odd Arf(g).The block calculation gives det S(g) ≡ 3^k(-1)^(d-k) (mod 8), with Arf(g) = k mod 2.Source: B Proof of the determinant test · pp. 17, 19
  • The determinant perturbation lemma supplies the modulo-eight stability needed in the coordinate-invariance argument.For the stated perturbation, det(P + 2D) ≡ det(P) (mod 8).Source: B Proof of the determinant test · pp. 17–19
  • The determinant residue modulo eight is invariant under invertible F2-linear changes of variables.The transformed lift differs from the congruent matrix by 2D, where D is integral symmetric and alternating modulo two; the permitted perturbation preserves the determinant modulo eight.Source: B Proof of the determinant test · pp. 18–19
  • A change of variables puts g in binary-block form, making S(g) block diagonal and reducing its determinant to the block determinants.The number k of indices with a_i b_i = 1 determines the determinant residue and satisfies Arf(g) = k mod 2.Source: B Proof of the determinant test · p. 19

C Parallel linear algebra in NC

This section gives logspace-uniform parallel constructions for rank, image and kernel bases, and determinants over fixed finite fields and rings. It explains how these constructions yield bounded-fan-in Boolean circuits and how a polynomial-ring simulation implements the rank reduction.

C Parallel linear algebra in NC

  • Rank, image and kernel bases, and determinants over fixed finite fields or rings admit logspace-uniform circuits of polynomial size and polylogarithmic depth.The basis construction outputs zero-padded matrices for the kernel and image; the determinant result applies in particular to Z/8Z.Source: C Parallel linear algebra in NC · p. 20
  • The parallel rank algorithm uses Mulmuley's reduction and division-free determinant circuits to identify rank from the least nonzero coefficient index.The reduction forms a symmetric block matrix, and the least j with c_j(ξ) nonzero is N − rank(B).Source: C Parallel linear algebra in NC · p. 20
  • Berkowitz's circuit is simulated over a truncated polynomial ring using coefficient vectors and balanced convolution and zero-test circuits.Because coefficient degrees are at most Δ = N(N − 1)/2, truncation at ξ^(Δ+1) loses no output information.Source: C Parallel linear algebra in NC · pp. 20–21
  • Selected independent columns and a nonsingular minor yield bases for the image and kernel through parallel selection, packing, and inversion.The kernel vectors are ordered by increasing nonselected column index, and the resulting vectors form a basis.Source: C Parallel linear algebra in NC · p. 21
Loading 2609.12669v1…