COUNTING ROOTS OF POLYNOMIALS OVER Z/p2 Z

arXiv:1708.04713v2 [math.NT] 12 Dec 2017

TRAJAN HAMMONDS, JEREMY JOHNSON, ANGELA PATINI, AND ROBERT M. WALKER

Abstract. Until recently, the only known method of finding the roots of polynomials over prime
power rings, other than fields, was brute force. One reason for this is the lack of a division algorithm,
obstructing the use of greatest common divisors. Fix a prime p ∈ Z and f ∈ (Z/pn Z)[x] any nonzero
polynomial of degree d whose coefficients are not all divisible by p. For the case n = 2, we prove a
new efficient algorithm to count the roots of f in Z/p2 Z within time polynomial in (d+size(f )+log p),
and record a concise formula for the number of roots, formulated by Cheng, Gao, Rojas, and Wan.

1. Introduction
Since the days of Diophantus, mathematicians have been interested in finding rational or integer
solutions to polynomial equations. In the 1940s, André 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:
√
|Nq − (q + 1)| ≤ 2g q,

where q is a prime power and Nq is the number of points over F2q 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/pk Z. That said, the usual approaches do not
work since the polynomial ring (Z/pk 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/pk 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[x1 , . . . xv ] is a nonzero
polynomial with at least one coefficient being a unit modulo p, and Nm (f ) denotes the number of
solutions to f ≡ 0 mod pm in the ring (Z/pm Z)v . Consider the Igusa Poincaré Series [6]:
X
Q(f ; t) =
Nm (f ) · tm ∈ Z[[t]].
m>0

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 Nm (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 N2 (f ) when
2010 Mathematics Subject Classification: Primary: 11Y05, 11Y16, 13F20. Secondary: 11M38, 11S05, 11T06.
Keywords: algebraic complexity theory, Hensel’s lemma, prime power rings, univariate polynomial root counting.
1

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/pk Z := {0, 1, . . . , pk − 1}
as a ring, and let πpk : Z[x] ։ (Z/pk Z)[x] denote the surjective ring homomorphism defined by
!
e
e
X
X
e−i
ci x
:=
πp k
ci · xe−i ,
i=0

i=0

Z/pk Z

when c ∈ Z [3, Ch. 9]. Given a polynomial g ∈ (Z/pk Z)[x], we let
where c := πpk (c) ∈
g ) = g–whose coefficients all lie between 0 and pk − 1. Also,
ge ∈ Z[x] denote the lift of g–read, πpk (e
for g ∈ (Z/pZ)[x], we say a root of multiplicity one is simple, and a root is degenerate otherwise.

Definition 1.1. For any nonconstant polynomial f ∈ Z[x], any prime p ∈ Z+ , and any k ∈ Z+ ,
let Vpk (f ) = {ζ ∈ Z/pk Z : [πpk (f )](ζ) = 0 ∈ Z/pk Z}. Also, we set Ak (p) := {0, 1, . . . , pk − 1} ⊆ Z.

Definition 1.2. Let f ∈ Z[x] \ {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 f1 , . . . , fℓ , g, h1 , h2 , t all in (Z/pZ)[x] and polynomials L1 , . . . , Lℓ ∈ Z[x].
(1) We can factor h1 := πp (f ) as
h1 = πp (f ) = f1 f22 · · · fℓℓ g ∈ (Z/pZ)[x],

(1.0.1)

where
(a) ℓ is the maximal multiplicity of a root r ∈ Z/pZ of h1 –if h1 has any;
(b) the fi ∈ (Z/pZ)[x] are monic, separable, and pairwise coprime; and
(c) g ∈ (Z/pZ)[x] has no roots in Z/pZ.
Thus the degree of fi equals the number of distinct roots of h1 in Z/pZ of multiplicity i.
The reader can consult [3, Ch. 8,9,13] for relevant background definitions in the setting of
univariate polynomial rings over a field.
Qdeg(f )
(2) Suppose that fi = j=1 i Li,j as a product (possibly empty) of distinct linear terms in
Qdeg(fi ) g
Li,j . Note that πp (Li ) = fi .
(Z/pZ)[x]. We define Li ∈ Z[x] to be Li =
j=1

(3) We also define polynomials t, h2 ∈ (Z/pZ)[x] via
!
ℓ
i
h1
Y
Lii , h2 := gcd(f2 · · · fℓ , t).
f − ge ·
t := πp
p
i=1

Definition 1.3. Fix a degree-d polynomial f ∈ Z[x] \ {0} written as f (x) = c0 + c1 x + ... + cd xd .
In terms of the natural logarithm, we define the computational size of f to be
size(f ) =

d
X
i=0

log(2 + |ci |);

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


#Vp2 (f ) = # a ∈ A2 (p) : f (a) ≡ 0 mod p2 = deg(f1 ) + p · deg(h2 ),

where deg stands for polynomial degree.

2

(1.0.2)

(2) The polynomials t, f1 , and h2 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 p2 that descend to simple roots
modulo p, the second term counts the roots modulo p2 that descend to degenerate roots modulo p.
2. Preliminaries for the Proof
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
r ∈ Z/pZ such that (x − r) | g but (x − r)2 ∤ g, then g ′ (r) 6= 0 in Z/pZ.
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 ∈ A1 (p) with [πp (f )](r) = 0. If [πp (f )]′ (r) 6= 0, then there exists an s ∈ A2 (p) such that

−1
[πp2 (f )](s) = 0 in Z/p2 Z and s ≡ r mod p, namely, s = e
t where t := r − f ′ (r)
· f (r) ∈ Z/p2 Z.
Moreover, s is unique.
Lemma 2.3 (Hensel’s Lemma Version II). Let f ∈ Z[x] be nonconstant, and suppose there exists
r in A1 (p) such that f (r) ≡ 0 mod pk , where k ∈ Z+ . If f ′ (r) ≡ 0 mod p, then
s≡r

mod pk =⇒ f (s) ≡ f (r) mod pk+1 .

That is, f (r + tpk ) ≡ f (r) mod pk+1 for all 0 ≤ t ≤ p − 1, indeed for all t ∈ Z.
Notably, we have p roots mod pk+1 when f (r) ≡ 0 mod pk+1 . Thus Lemma 2.3 can lift roots
modulo pk to roots modulo pk+1 . Conversely, all the roots modulo pk+1 are obtained this way.
3. Proof of the Main Theorem
Proof of Theorem 1.4(1). Recall that in Definition 1.2 we defined polynomials Li ∈ Z[x] such that
πp (Li ) = fi . Let U := {ζe ∈ A2 (p) : ζ ∈ Vp2 (f )}, which is the disjoint union of the two sets
S := {u ∈ U : u ∈ Vp (L1 )}, and T := U \ S.

Recall that we defined h2 = gcd(f2 · · · fℓ , t) ∈ (Z/pZ)[x]; this monic polynomial is a product
(possibly empty) of distinct linear terms. Let D(x) ∈ Z[x] be the lift of h2 constructed analogously
to the Li , taking the corresponding product of the e
• lifts of the linear factors. To get 1.4(1), it
suffices to show that as maps of sets (a) πp |S : S → Vp (L1 ) is a bijection, and (b) πp |T : T → Vp (D)
is a p-to-1 surjection. But first, we record a lemma.

Lemma 3.1. Let ρ : A2 (p) → A1 (p) be the map of sets sending an element a ∈ A2 (p) to its
remainder after long division by p. Fix r ∈ A2 (p). If f (r) ≡ 0 mod p2 , then f (ρ(r)) ≡ 0 mod p.
Equivalently, if r ∈ Vp2 (f ), then ρ(r) ∈ Vp (f ) in terms of the bar notation preceding Definition 1.1.
3

Indeed, if f (a) =

Pd

i=0 cd−i a

d−i

for any a ∈ Z, then f (r) ≡

Pd

d−i
i=0 cd−i (ρ(r))

= f (ρ(r)) mod p.

(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)) ∈ Vp (f ), meeting the first hypothesis
of Hensel’s Lemma 2.2. Because of our stipulations in defining the polynomials fi in (1.0.1),
Proposition 2.1 applied to h1 = πp (f ) implies that πp (ρ(r)) satisfies the second hypothesis under
Hensel’s Lemma 2.2 if and only if πp (ρ(r)) ∈ Vp (L1 ). Equivalently, r ∈ S and it will be the unique
lift to A2 (p) of ρ(r) ∈ A1 (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 ∈ A1 (p) and r := πp (r) ∈ Z/pZ, the following assertions are equivalent to
saying (x − r)2 | h1 :
(1) r is a degenerate root of h1 , i.e., both f (r) ≡ 0 mod p and f ′ (r) ≡ 0 mod p.
(2) (x − r) | fi for some unique i ≥ 2.
(3) (x − r) | f2 · . . . · fℓ .
Indeed, per the stipulations on the fi in (1.0.1), all of these assertions mean f1 (r) 6= 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 ) ⊆ Vp (L2 · · · Lℓ ): given r ∈ T , Lemmas 3.1 and 3.2 apply to ρ(r). Let
E(x) := f (x) − e
g(x) ·

ℓ
Y
i=1

Lii (x) ∈ pZ[x] = ker πp .

Then the integer polynomial (1/p) · E(x) is a lift of t(x). Next, since h2 divides h1 in (Z/pZ)[x],
we note that any r ∈ A1 (p) for which D(r) ≡ 0 mod p also satisfies Li (r) ≡ 0 mod p for some
i ≥ 2 by Lemma 3.2. Thus f (r) ≡ E(r) mod p2 . Additionally, t(r) = 0 ∈ Z/pZ, so (1/p)E(r) ≡ 0
mod p, hence E(r) ≡ 0 mod p2 . Then f (r) ≡ 0 mod p2 , so Hensel’s Lemma 2.3 says that r can be
lifted to p distinct roots sj = r + j ·p ∈ T of f modulo p2 where 0 ≤ j ≤ p − 1. Thus Vp (D) ⊆ πp (T ).
To conclude that πp |T is a p-to-1 surjection onto Vp (D), it remains to show that conversely,
given u ∈ T , u := πp (u) ∈ Vp (D). Since πp (T ) ⊆ Vp (L2 · · · Lℓ ), we have (f2 · · · fℓ )(u) = 0 ∈ Z/pZ
and (Li (u))i ≡ 0 mod p2 for some i ≥ 2. Thus f (u) ≡ E(u) ≡ 0 mod p2 : indeed, since u ∈ T ,
f (u) ≡ 0 mod p2 . It follows that (1/p)E(u) ≡ 0 mod p. Equivalently, t(u) = 0 ∈ Z/pZ. We may
conclude that (x − u)|(f2 · · · fℓ ) and (x − u)|t in (Z/pZ)[x], so by the definition of greatest common
divisor (x − u)|h2 in (Z/pZ)[x]. Thus u ∈ Vp (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
mod p2 } = deg(f2 · · · fℓ ) − deg(h2 )

#{a ∈ A1 (p) : a ∈ Vp (L2 · · · Lℓ ), f (a) 6≡ 0

(3.0.1)

degenerate roots of f modulo p fail to lift to roots of f modulo p2 .

Proof. To start, continuing from the proof of Theorem 1.4(1), the right-hand side is equal to
#Vp (L2 · · · Lℓ ) − #Vp (D), since f2 · · · fℓ and h2 are separable. Our argument for claim (b) in the
proof of Theorem 1.4(1) suffices to show that πp (T ) = Vp (D) = Vp (L2 · · · Lℓ ) ∩ Vp [(1/p)E], and that

the set stated in the corollary coincides with {a ∈ A1 (p) : a ∈ Vp (L2 · · · Lℓ ) − Vp [(1/p)E]}.
4

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(d1+o(1) (log p)1+o(1) ), per an algorithm of Knuth
and Schönhage [2, Ch. 3]. Also, division with remainder for polynomials of degree ≤ d in (Z/pZ)[x]
takes time O(d1+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 h1 and xp − x can
be computed in time O(d1+o(1) (log p)1+o(1) ) by applying the binary method to the computation of
xp mod h1 (see, e.g., [1, pp. 102-104, 121-122, & 170-171]).
Going forward, we may assume that the maximal multiplicity ℓ ≥ 1. Now observe that s1 :=
gcd (h1 , xp − x) ∈ (Z/pZ)[x] has the property that Vp (h1 ) = Vp (s1 ) and s1 has exactly deg(s1 )
distinct linear factors. In particular, s1 factors as f1 f2 · · · fℓ . Next, note that s2 := h1 /s1 factors
Q
Q
as g · ℓi=1 fii−1 . So then, s3 := gcd(s1 , s2 ) = ℓi=2 fi . So we can then compute f1 as s1 /s3 and
h2 as gcd(s3 , 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 (x3 + 2x + 1) + 5(x + 2)(x + 4)

= x25 + 66x24 + 2073x23 + 41225x22 + 582597x21 + 6225421x20 + 52256469x19
+ 353428921x18 + 1960388179x17 + 9032286149x16 + 34894415443x15
+ 113842103703x14 + 315375403239x13 + 745101000855x12 + 1506289490631x11
+ 2610867590739x10 + 3879338706288x9 + 4921047219861x8 + 5275209809592x7
+ 4688604525204x6 + 3350344836816x5 + 1835957176704x4
+ 716433486336x3 + 174686782469x2 + 19591041054x + 40.
In particular, invoking language in the proof of Theorem 1.4(1), we have
h1 (x) = x(x − 3)2 (x − 1)5 (x − 2)14 (x3 + 2x + 1) ∈ (Z/pZ)[x]
f1 = x,

f2 = (x − 3),

t(x) = (x − 3)(x − 1),

Thus Theorem 1.4(1) says that

f5 = (x − 1),

f14 = (x − 2),

g = x3 + 2x + 1,

h2 = gcd(f2 f5 f14 , t) = (x − 3)(x − 1) ∈ (Z/5Z)[x].

#{a ∈ A2 (5) : f (a) ≡ 0 mod 25} = deg(f1 ) + 5 · deg(h2 ) = 1 + 5(2) = 11.

Now, f (x) ≡ 0 mod 5 when x = 0, 1, 2, 3 ∈ A1 (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 ∈ A2 (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.
5

4. Acknowledgements
This research was conducted during the MSRI Undergraduate Program in Summer 2017 with
Dr. Federico Ardila serving as the on-site program director; we thank the Mathematical Sciences
Research Institute and Dr. Ardila for the opportunity. The first three authors would like to
thank their research advisor, Dr. J. Maurice Rojas, for exceptional guidance throughout the REU
program. We thank two anonymous referees for feedback that improved the quality of exposition.
Indeed, we thank one referee for asking whether we could deduce Corollary 3.3 above. We thank
the Alfred P. Sloan Foundation and the National Science Foundation (Grant No. DMS-1659138) for
providing financial support to run MSRI-UP this summer. We also acknowledge the partial REU
support of MSRI’s NSF grant (DMS-1440140), NSF grant CCF-1409020, and NSF DMS-1460766.
Robert Walker was supported by a NSF GRF under Grant Number PGF-031543, NSF RTG grant
0943832, and a Ford Foundation Dissertation Fellowship.
References
[1] E. Bach and J. Shallit. Algorithmic Number Theory, Vol. I: Efficient Algorithms. MIT Press, Cambridge, MA,
1996.
[2] P. Burgisser, M. Clausen, and M.A. Shokrollahi. Algebraic complexity theory, with the collaboration of Thomas
Lickteig, Grundlehren der Mathematischen Wissenschaften, 315. Springer-Verlag, Berlin, Cambridge, MA, 1997.
[3] D.S. Dummit and R.M. Foote. Abstract Algebra, 3rd Edition. Wiley Publishing, Hoboken, NJ, 2004.
[4] H. Hironaka. Resolution of singularities of an algebraic variety over a field of characteristic zero: I. Annals of
Mathematics, 79(1):109–203, 1964.
[5] J-I. Igusa. Forms of higher degree, Tata Institute of Fundamental Research, Bombay. Narosa Publishing House,
New Delhi, 1978.
[6] J-I. Igusa. An Introduction to the Theory of Local Zeta Functions, AMS/IP Studies in Advanced Mathematics.
AMS, Providence, RI, 2000.
[7] H. Montgomery, I. Niven, and H. Zuckerman. An Introduction to the Theory of Numbers, 5th Edition. John
Wiley and Sons, Inc. New York, 1991.
[8] A. Weil. Sur les courbes algébriques et les variétés qui s’ en déduisent. Number 1041. Hermann, 1948.
[9] A. Weil. Numbers of solutions of equations in finite fields. Bull. Amer. Math. Soc., 55, 1949. pp. 497–508.
[10] W.A. Zuniga-Galindo. Computing Igusa’s local zeta functions of univariate polynomials, and linear feedback
shift registers. Journal of Integer Sequences, 6(2):3, 2003.
Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA, 15289
E-mail address: thammond@andrew.cmu.edu
Department of Mathematics, Humboldt State University, Arcata, CA, 95521
E-mail address: jsj132@humboldt.edu
Department of Mathematics, University of Pennsylvania, Philadelphia, PA, 19104
E-mail address: apatini@sas.upenn.edu
Department of Mathematics, University of Michigan, Ann Arbor, MI, 48109
E-mail address: robmarsw@umich.edu

6

