Since the days of Diophantus, mathematicians have been interested in finding rational or integer solutions to polynomial equations. In the 1940s, André Weil proved the Riemann hypothesis for zeta-functions of nonsingular curves over finite fields [8]. In 1949, Weil proposed enticing conjectures that connect finding solutions to polynomials over finite fields with studying the geometry of complex algebraic varieties [9]. Weil proved these conjectures in the case of curves, yielding a bound for counting the number of points on a curve over a finite field-the Hasse-Weil bound:
where q is a prime power and N q is the number of points over F 2 q on a curve with genus g. Such bounds on point counts extend to higher dimensions, per work of Weil, Deligne, Dwork, and others.
We wish to count roots over the prime power ring Z/p k Z. That said, the usual approaches do not work since the polynomial ring (Z/p k Z)[x] does not have unique factorization when k ≥ 2. Thus we must sleuth for alternate approaches to count roots of nonconstant univariate polynomials over Z/p k Z, since traditional methods for factoring and root counting over finite fields are unavailable.
As a backdrop, suppose p ∈ Z is a prime, both m, v ∈ Z + , f ∈ Z[x 1 , . . . x v ] is a nonzero polynomial with at least one coefficient being a unit modulo p, and N m (f ) denotes the number of solutions to f ≡ 0 mod p m in the ring (Z/p m Z) v . Consider the Igusa Poincaré Series [6]:
Igusa's proof that Q(f ; t) is rational [5], solving a conjecture of Borevich and Shafarevich, relied on Hironaka's resolution of singularities [4], which runs in exponential time. Zuniga-Galindo [10] later derived an algorithm to compute Q(f ; t), where the dependence on v in the complexity was of order 8. While one could in principle use standard generating function tricks to then extract N m (f ) for any given m, Zuniga-Galindo's algorithm only works in the case where f splits completely into linear factors over Q -a severe restriction. Cheng, Gao, Rojas, and Wan, during a meeting at the American Institute for Mathematics (AIM) in May 2017, found an explicit formula for N 2 (f ) when v = 1, but without a proof or complexity bound. We prove their formula is correct and that it has near-quadratic complexity.
Going forward, given a prime p ∈ Z + , and k ∈ Z + , we view the set Z/p k Z := {0, 1, . . . , p k -1} as a ring, and let π p k : Z[x] ։ (Z/p k Z)[x] denote the surjective ring homomorphism defined by
where c := π p k (c) ∈ Z/p k Z when c ∈ Z [3, Ch. 9]. Given a polynomial g ∈ (Z/p k Z)[x], we let g ∈ Z[x] denote the lift of g-read, π p k ( g) = g-whose coefficients all lie between 0 and p k -1. Also, for g ∈ (Z/pZ)[x], we say a root of multiplicity one is simple, and a root is degenerate otherwise.
\ {0} be a nonconstant polynomial of degree d. Fix any prime p not dividing every coefficient of f . We define the maximal multiplicity ℓ of a root of f modulo p, and a series of polynomials f 1 , . . . , f ℓ , g, h 1 , h 2 , t all in (Z/pZ)[x] and polynomials L 1 , . . . , L ℓ ∈ Z[x].
(1) We can factor h 1 := π p (f ) as L i,j as a product (possibly empty) of distinct linear terms in
In terms of the natural logarithm, we define the computational size of f to be
it is simply the number of bits needed to record the above monomial term expansion of f .
We now state the main result of this note.
Main Theorem 1.4. With notation as in Definitions 1.1, 1.2, and 1.3,
(1) We have
where deg stands for polynomial degree.
(2) The polynomials t, f 1 , and h 2 can be computed deterministically in time that is polynomial in d + size(f ) + log(p), where d = deg(f ), counting the necessary arithmetic operations.
While the first term in formula (1.0.2) counts the roots modulo p 2 that descend to simple roots modulo p, the second term counts the roots modulo p 2 that descend to degenerate roots modulo p.
Throughout, p is an arbitrary prime number. We state a proposition together with two versions of Hensel's Lemma, a crucial tool for proving Theorem 1.4(1).
Proposition 2.1 (Cf., [3, Sec. 13.5, Prop. 33]). If g ∈ (Z/pZ)[x] is nonconstant, and there is an
In [7, Sec. 2.6, Thm. 2.23 + paragraph between Examples 11-12], a derivation of both versions of Hensel's Lemma below is given via Taylor expansion. We note that [7, Sec. 2.6] phrases both versions of Hensel's Lemma in terms of an arbitrary integer r rather than stipulating 0 ≤ r ≤ p -1.
Lemma 2.2 (Hensel's Lemma Version I). Let f ∈ Z[x] be nonconstant, and suppose there is an r
Moreover, s is unique. That is, f (r + tp k ) ≡ f (r) mod p k+1 for all 0 ≤ t ≤ p -1, indeed for all t ∈ Z.
Notably, we have p roots mod p k+1 when f (r) ≡ 0 mod p k+1 . Thus Lemma 2.3 can lift roots modulo p k to roots modulo p k+1 . Conversely, all the roots modulo p k+1 are obtained this way.
Proof of Theorem 1.4 (1). Recall that in Definition 1.2 we defined polynomials
; this monic polynomial is a product (possibly empty) of distinct linear terms. Let D(x) ∈ Z[x] be the lift of h 2 constructed analogously to the L i , taking the corresponding product of the • lifts of the linear factors. To get 1.4(1), it suffices to show that as maps of sets (a) π p | S : S → V p (L 1 ) is a bijection, and (b) π p | T : T → V p (D) is a p-to-1 surjection. But first, we record a lemma. Lemma 3.1. Let ρ : A 2 (p) → A 1 (p) be the map of sets sending an element a ∈ A 2 (p) to its remainder after long division by p. Fix r ∈ A 2 (p). If f (r) ≡ 0 mod p 2 , then f (ρ(r)) ≡ 0 mod p. Equivalently, if r ∈ V p 2 (f ), then ρ(r) ∈ V p (f ) in terms of the bar notation preceding Definition 1.1.
(a) π p | S is a bijection: This is vacuous if S is empty, so we may assume S is non-empty. First, given any element r ∈ U , Lemma 3.1 says π p (r) = π p (ρ(r)) ∈ V p (f ), meeting the first hypothesis of Hensel's Lemma 2.2. Because of our stipulations in defining the polynomials f i in (1.0.1), Proposition 2.1 applied to h 1 = π p (f ) implies that π p (ρ(r)) satisfies the second hypothesis under Hensel's Lemma 2.2 if and only if π p (ρ(r)) ∈ V p (L 1 ). Equivalently, r ∈ S and it will be the unique lift to A 2 (p) of ρ(r) ∈ A 1 (p) as stipulated in Hensel's Lemma 2.2, since r ≡ ρ(r) mod p. Thus we may conclude that π p | S is both surjective and injective, hence bijective.
Before proceeding, we record another lemma.
Lemma 3.2. Given r ∈ A 1 (p) and r := π p (r) ∈ Z/pZ, the following assertions are equivalent to saying (x -r) 2 | h 1 :
(1) r is a degenerate root of h 1 , i.e., both f (r) ≡ 0 mod p and f ′ (r) ≡ 0 mod p.
(
Indeed, per the stipulations on the f i in (1.0.1), all of these assertions mean f 1 (r) = 0 in Z/pZ.
(b) π p | T is a p-to-1 surjection: This is vacuous if T is empty, so we may assume T is non-empty. We note that π p (T )
given r ∈ T , Lemmas 3.1 and 3.2 apply to ρ(r). Let
Then the integer polynomial (1/p) • E(x) is a lift of t(x). Next, since h 2 divides h 1 in (Z/pZ)[x], we note that any r ∈ A 1 (p) for which D(r) ≡ 0 mod p also satisfies L i (r) ≡ 0 mod p for some i ≥ 2 by Lemma 3.2. Thus f (r) ≡ E(r) mod p 2 . Additionally, t(r) = 0 ∈ Z/pZ, so (1/p)E(r) ≡ 0 mod p, hence E(r) ≡ 0 mod p 2 . Then f (r) ≡ 0 mod p 2 , so Hensel's Lemma 2.3 says that r can be lifted to p distinct roots s j = r + j •p ∈ T of f modulo p 2 where 0 ≤ j ≤ p -1. Thus V p (D) ⊆ π p (T ).
To conclude that π p | T is a p-to-1 surjection onto V p (D), it remains to show that conversely,
, so by the definition of greatest common divisor (x -u)|h 2 in (Z/pZ)[x]. Thus u V p (D). This completes the proof of claim (b), so we are done.
Corollary 3.3. With notation as in Definitions 1.1 and 1.2, exactly
degenerate roots of f modulo p fail to lift to roots of f modulo p 2 .
Proof. To start, continuing from the proof of Theorem 1.4(1), the right-hand side is equal to
and that the set stated in the corollary coincides with {a ∈ A 1 (p) :
Proof of Theorem 1.4 (2). First note that the decomposition (1.0.1) stated under Definition 1.2 can be found via any classical factoring algorithm (see, e.g., [1,2]). The gcd of polynomials in (Z/pZ)[x] of degree ≤ d can be computed in near linear time O(d 1+o (1) (log p) 1+o (1) ), per an algorithm of Knuth and Schönhage [2,Ch. 3]. Also, division with remainder for polynomials of degree ≤ d in (Z/pZ)[x] takes time O(d 1+o (1) log p), and reduction mod p of a polynomial f ∈ Z[x] can be done in time linear in size(f ) + log p (see, e.g., [2,Ch. 3] and [1,Ch. 7]). Finally, note that the gcd of h 1 and x p -x can be computed in time O(d 1+o (1) (log p) 1+o (1) ) by applying the binary method to the computation of x p mod h 1 (see, e.g., [1, pp. 102-104, 121-122, & 170-171]).
Going forward, we may assume that the maximal multiplicity ℓ ≥ 1. Now observe that s 1 := gcd (h 1 , x p -x) ∈ (Z/pZ)[x] has the property that V p (h 1 ) = V p (s 1 ) and s 1 has exactly deg(s 1 ) distinct linear factors. In particular, s 1 factors as
. So then, s 3 := gcd(s 1 , s 2 ) = ℓ i=2 f i . So we can then compute f 1 as s 1 /s 3 and h 2 as gcd(s 3 , t) within (Z/pZ)[x]. This amounts to 3 gcds and 2 divisions in (Z/pZ)[x], which is clearly within the stated complexity bound -provided we can compute t efficiently. That t can be computed efficiently is immediate since it only involves a distinct degree factorization in (Z/pZ)[x], a subtraction in Z[x], and a single polynomial division (by p) in Z[x].
To conclude, now that the main arguments have been recorded, we certainly invite readers to either: (a) generate many simple examples to better appreciate the root counting formula under Theorem 1.4(1); or (b) try implementing the algorithm in a computer algebra system they find palatable. We close the paper by providing the following example.
Example 3.4. Fix the prime p = 5, and consider the polynomial f ∈ Z[x] defined by f (x) = x(x + 2) 2 (x + 4) 5 (x + 3) 14 (x 3 + 2x + 1) + 5(x + 2)(x + 4) = x 25 + 66x 24 + 2073x 23 + 41225x 22 + 582597x 21 + 6225421x 20 + 52256469x 19 + 353428921x 18 + 1960388179x 17 + 9032286149x 16 + 34894415443x 15 + 113842103703x 14 + 315375403239x 13 + 745101000855x 12 + 1506289490631x 11 + 2610867590739x 10 + 3879338706288x 9 + 4921047219861x 8 + 5275209809592x 7 + 4688604525204x 6 + 3350344836816x 5 + 1835957176704x 4 + 716433486336x 3 + 174686782469x 2 + 19591041054x + 40.
In particular, invoking language in the proof of Theorem 1.4(1), we have h 1 (x) = x(x -3) 2 (x -1) 5 (x -2) 14 (x 3 + 2x + 1) ∈ (Z/pZ)[x] f 1 = x, f 2 = (x -3), f 5 = (x -1), f 14 = (x -2), g = x 3 + 2x + 1, t(x) = (x -3)(x -1), h 2 = gcd(f 2 f 5 f 14 , t) = (x -3)(x -1) ∈ (Z/5Z)[x].
Thus Theorem 1.4(1) says that #{a ∈ A 2 (5) : f (a) ≡ 0 mod 25} = deg(f 1 ) + 5 • deg(h 2 ) = 1 + 5(2) = 11. Now, f (x) ≡ 0 mod 5 when x = 0, 1, 2, 3 ∈ A 1 (5). The simple root x = 0 mod 5 lifts uniquely to the root x = 15 mod 25 per Hensel's Lemma 2.2. Among the three degenerate roots mod 5, only x = 1 and x = 3 satisfy f (x) ≡ 0 mod 25, and Hensel's Lemma 2.3 lifts them 5-to-1. The values x ∈ A 2 (5) for which f (x) ≡ 0 mod 25 are 1, 3, 6, 8, 11, 13, 15, 16, 18, 21, and 23. We note that 1 ≡ 6 ≡ 11 ≡ 16 ≡ 21 mod 5, while 3 ≡ 8 ≡ 13 ≡ 18 ≡ 23 mod 5, as indicated under our discussion of Hensel's Lemma 2.3. In line with formula 3.0.1 under Corollary 3.3, we note in passing that only x = 2 fails to lift to a root modulo 25.