ZEROS OF SPARSE POLYNOMIALS OVER LOCAL FIELDS OF CHARACTERISTIC p

BJORN POONEN

1. Statement of results

Let K be a field of characteristic p > 0 equipped with a valuation v : K^{∗} → G taking values in an ordered abelian group G. Let O_{K} = {α ∈ K : v(α) ≥ 0} and 𝔪_{K} = {α ∈ K : v(α) > 0} be the valuation ring and maximal ideal, respectively, and suppose that the residue field O_{K}/𝔪_{K} is finite, with q elements. Theorem 1. If f(x) = a_{0}x^{n_{0}} + a_{1}x^{n_{1}} + ⋯ + a_{k}x^{n_{k}} is a polynomial with k + 1 nonzero coefficients a_{i} ∈ K^{∗}, then f has at most q^{k} distinct zeros in K.

This upper bound is sharp: if K is F_{q}((T)) with the usual discrete valuation v : K^{∗} → Z, if V ⊂ K is an F_{q}-subspace of dimension k, and if c ∈ K is nonzero, then the polynomial f(x) := c ∏_{α∈V} (x − α) has the form a_{0}x + a_{1}x^{q} + ⋯ + a_{k}x^{q^{k}} for some a_{0}, a_{1}, …, a_{k} ∈ K^{∗}.

Theorem 1 is the case d = 1 of the following generalization, which bounds the number of distinct zeros of bounded degree. Let μ(n) be the Möbius μ-function. Theorem 2. Fix d ≥ 1. If f(x) = a_{0}x^{n_{0}} + a_{1}x^{n_{1}} + ⋯ + a_{k}x^{n_{k}} is a polynomial with k + 1 nonzero coefficients a_{i} ∈ K^{∗}, then the number of distinct zeros of f in \overline{K} of degree at most d over K is at most ∑_{j=1}^{d} ∑_{i|j} q^{ik}μ(j/i).

This upper bound is sharp as well, for every q, k, and d. Let K = F_{q}((T)) and v be as before. Let F be a finite field containing F_{q^{i}} for i ≤ d. Let V ⊂ F((T)) be a k-dimensional F-vector space that is Gal(F/F_{q})-stable (or equivalently, has an F-basis of elements of K). Then equality is attained in Theorem 2 for f(x) := c ∏_{α∈V} (x − α) for any c ∈ K^{∗}. (The inner sum in Theorem 2 performs the inclusion-exclusion to count zeros of exact degree j.)

We make no claim that these are the only polynomials that attain equality; in fact there are many others. For example, if K, V, and f are as in the previous paragraph, and if the F-basis of V consists of elements of K of distinct valuation, with all these valuations divisible by a single integer e ≥ 1, then f(x^{e}) also attains equality, as a short argument involving Hensel’s lemma shows. Other examples can be constructed using the observation that if f(x) ∈ K[x] has N zeros in a given field extension L of K, one of which is 0, then the same holds for x^{m}f(1/x) when m > deg f. Remark. H. W. Lenstra, Jr. [Le1] proves related facts for finite extensions L of Q_{p}, using very different methods. One of his results is that for any such L and any positive integer k, there exists a positive integer B = B(k, L) with the following property: if f ∈ L[x] is a nonzero polynomial with at most k + 1 nonzero terms and f(0) ≠ 0, then f has at most B zeros in L, counted with multiplicities. His bound B(k, L) is explicit, but almost certainly not sharp. Finding a sharp bound seems difficult in general, although Lenstra does this for the case k = 2 and L = Q_{2} (the bound then is 6). He also applies his local result to bound uniformly the number of factors of given degree over number fields. In [Le2] he shows that if f is represented sparsely, then these factors can be found in polynomial time. Remark. We cannot count multiplicities in either of our theorems and hope to obtain a bound depending only on k and K (and d, for Theorem 2), because of examples like f(x) = (1+x)^{q^{m}} with m → ∞. Requiring that f not be a p-th power would not eliminate the problem, because one could also take f(x) = (1 + x)^{q^{m}+1}.

Date: March 2, 1998.

This article has appeared in Math. Res. Lett. 5 (1998), 273–279, \begin{matrix}c \\ ◯ \end{matrix}MRL 1998.

2. Proof of Theorem 1

By a disk in a valued field K, we mean either an “open disk” D(x_{0}, g) := {x ∈ K : v(x − x_{0}) > g\}, or a “closed disk” \overline{D}(x_{0}, g) := \{x ∈ K : v(x − x_{0}) ≥ g\} where x_{0} ∈ K and g ∈ G.

Let σ_{1}, σ_{2}, …, σ_{t} be the non-vertical segments of the Newton polygon of f. Let −g_{j} ∈ G⊗ Q be the slope of σ_{j}. If e_{1}, e_{2}, …, e_{r} are the exponents of the monomials in f corresponding to points on a given σ_{j}, define N_{j} as the largest integer for which the images of (1 + x)^{e_{1}}, (1 + x)^{e_{2}}, …, (1 + x)^{e_{r}} in F_{p}[x]/(x^{N_{j}}) are linearly dependent over F_{p}. We say that the σ_{j} are in a proper order if N_{1} ≥ N_{2} ≥ ⋯ ≥ N_{t}. This particular ordering is crucial to the proof, but it is hard to motivate its definition. It was discovered by analyzing proofs of many special cases of Theorem 1. For instance, if the Newton polygon of f has k non-vertical segments (each associated with exactly two exponents), then the segments are being ordered according to the p-adic absolute values of their horizontal lengths. Lemma 3. Let L be a field of characteristic p > 0 with a valuation v : L^{∗} → G. Suppose f(x) = a_{0}x^{n_{0}} + a_{1}x^{n_{1}} + ⋯ + a_{k}x^{n_{k}} ∈ L[x] with each a_{i} nonzero. List the segments of the Newton polygon of f in a proper order as above. Fix u and let −g_{u} ∈ G ⊗ Q be the slope of the u-th segment σ_{u}. Suppose r ∈ L is not a zero of f, and v(r) = g_{u}. Let S be the set of zeros of f in L lying inside D(r, g_{u}). Then #{v(α − r) : α ∈ S} ≤ k + 1 − u.

Proof. Replacing f(x) by cf(rx) for suitable c ∈ L^{∗}, we may reduce to the case in which r = 1, g_{u} = 0, f ∈ O_{L}[x], and f mod 𝔪_{L} is nonzero. Write f(1 + x) = ∑_{j=0}^{n_{k}} b_{j}x^{j}, and let M be the smallest integer for which b_{M} is nonzero modulo 𝔪_{L}. By definition of N_{u}, f(1 + x) ≢ 0 mod (𝔪_{L}, x^{N_{u}+1}). Hence M ≤ N_{u}.

For each i ≤ u, we have N_{u} ≤ N_{i}, so M ≤ N_{i}, and there is some F_{p}-linear relation in F_{p}[x]/(x^{M}) between the (1 + x)^{e} for the exponents e associated to σ_{i}. The subspace of F_{p}[x]/(x^{M}) spanned by the (1 + x)^{e}, where e ranges over all the exponents in f, then has dimension at most (k + 1) − u, since the u relations above are independent, the largest e involved in each relation being distinct from the others. It follows that the F_{p}-subspace of K spanned by b_{0}, b_{1}, …, b_{M−1} is at most (k + 1 − u)-dimensional. Then #{v(b_{i}) : 0 ≤ i < M and b_{i} ≠ 0} ≤ k+1−u, because nonzero elements of distinct valuations are automatically F_{p}-independent. The left endpoints of the negative slope segments of the Newton polygon of f(1 + x) correspond to b_{i} of distinct valuations for i < M, so there are at most k + 1 − u such segments. Hence at most k + 1 − u positive elements of G can be valuations of zeros of f(1 + x), which is what we needed to prove. □

Remark. Note that there is no assumption on the residue field in Lemma 3; L could even be algebraically closed.

Let S be any finite subset of a field L with valuation v. We associate a tree T to S as follows. (See [St] for arboreal terminology.) Let T be the Hasse diagram of the finite poset (ordered by inclusion) of nonempty sets of the form S ∩ D where D is a disk. Clearly T is a tree, whose leaves are the singleton subsets of S. We would obtain the same tree if we required the disks D to be open (resp. closed), since S is finite.

Suppose r and S are as in Lemma 3. Let T_{0} > T_{1} > ⋯ > T_{ℓ} be the longest chain in T . Then T_{ℓ} is a leaf, and #T_{ℓ} = 1. Choose r_{0} ∈ D(r, g_{u}) \ S closer to the element of T_{ℓ} than to any other element of S. For various g > g_{u}, the set S ∩ D(r_{0}, g) can equal T_{0}, T_{1}, …, T_{ℓ}, or ∅. Hence

#{v(α − r_{0}) : α ∈ S} ≥ ℓ + 1.

On the other hand, Lemma 3 applied to r_{0} yields

#{v(α − r_{0}) : α ∈ S} ≤ k + 1 − u.

Combining these, we have that the length ℓ = ℓ(T ) of the tree satsifies ℓ ≤ k − u.

Suppose S_{0} ∈ T is not a leaf (i.e. #S_{0} > 1), and let g = min{v(s − t) : s, t ∈ S_{0}}, so that for any s ∈ S_{0}, \overline{D}(s, g) is the smallest disk containing S_{0}. Then the children of S_{0} in the tree are nonempty sets of the form S ∩ D(x_{0}, g) for some x_{0} ∈ \overline{D}(s, g). In particular the number of children is at most the size of the residue field of L.

Proof of Theorem 1. Let notation be as in Lemma 3, but take L = K. By the theory of Newton polygons, each nonzero zero of f has valuation equal to g_{u} for some u. Let us now fix u and let Z_{u} be the number of zeros in K of valuation g_{u}. We may assume g_{u} ∈ G, since otherwise Z_{u} = 0. Then {x ∈ K : v(x) = g_{u}} is the union of q − 1 open disks D_{j} of the form D(x_{j}, g_{u}). As above, the tree corresponding to the set of zeros in D_{j} has length at most k − u, and each vertex has at most q children. Hence the tree has at most q^{k−u} leaves, and Z_{u} ≤ (q − 1)q^{k−u}. Allowing for the possibility that 0 also is a zero of f, we find that the number of zeros of f in K is at most

1 + ∑_{u=1}^{t} Z_{u} ≤ 1 + ∑_{u=1}^{t}(q − 1)q^{k−u} ≤ 1 + ∑_{u=1}^{k}(q − 1)q^{k−u} = q^{k}.

□

3. Valuation theory

Before proving Theorem 2, we will need to recall some facts from valuation theory. We write (K, v) for a field K with a valuation v. We say that (L, w) is an extension of (K, v) if K ⊆ L and w|_{K} = v. In this case, when we say that L has the same value group (resp. residue field) as K, we mean that the inclusion of value groups (resp. residue fields) induced from the inclusion of (K, v) in (L, w) is an isomorphism. Recall that any valuation on a field K admits at least one extension to any field containing K. An abelian group G is divisible if for all g ∈ G and n ≥ 1, the equation nx = g has a solution x in G. Proposition 4. Any valued field can be embedded in another valued field having the same residue field, but divisible value group.

Proof. Let v : K^{∗} → G be the original valuation. If G is not already divisible, then there exists g ∈ G and a prime number n such that nx = g has no solution in G. Pick α ∈ K^{∗} with v(α) = g, and extend v to a valuation on L = K(α^{1/n}). Let e and f denote the ramification index and residue class degree for L/K. Then e = n, and the inequality ef ≤ n (Lemma 18 in Chapter 1 of [Sch]) forces f = 1. An easy Zorn’s lemma argument now shows that v extends to a valuation v : M^{∗} → G ⊗ Q where M is an extension with the same residue field as K, but with divisible value group. □

Recall that (L, w) is called an immediate extension of (K, v) if

(1) (L, w) is an extension of (K, v);

(2) (L, w) has the same value group as (K, v); and

(3) (L, w) has the same residue field as (K, v). Also recall that (K, v) is called maximally complete if it has no nontrivial immediate extensions. Proposition 5. Every valued field has a maximally complete immediate extension.

Proof. This is an old result of Krull: see Theorem 5 of Chapter 2 in [Sch]. □

Proposition 6. Suppose that (K, v) is maximally complete of characteristic p > 0, and that F_{q} is contained in the residue field. Then F_{q} can be embedded in K.

Proof. Apply a suitable version of Hensel’s lemma (combine Theorems 6 and 7 of Chapter 2 of [Sch]) to the factorization of x^{q} − x over F_{q}. □

Proposition 7. Suppose that (K, v) is maximally complete of characteristic p > 0, with divisible value group G and with residue field F_{q}. If L ⊂ \overline{K} is a finite extension of K of degree n, then L is the compositum of F_{q^{n}} and K in \overline{K}.

Proof. Extend v to L. Theorem 11 in Chapter 2 of [Sch] shows that L is maximally complete, and that ef = n holds for L/K. Since G is divisible, there are no ordered abelian groups G′ with 1 < (G′ : G) < ∞. Hence e = 1, f = n, and the residue field of L is F_{q^{n}}. Proposition 6 implies that the subfield F_{q^{n}} of \overline{K} is contained in L. But the compositum of the linearly disjoint fields F_{q^{n}} and K in \overline{K} is already n-dimensional over K, so the compositum must equal L. □

Remark. Lenstra notes that if one is interested in proving Theorem 2 only for polynomials over K_{0} = F_{q}((T)), then one can circumvent the theory of maximally complete fields by choosing σ ∈ Gal(\overline{K}_{0}/K_{0}) that acts as x ↦ x^{q} on \overline{F}_{q}, and by taking K to be the fixed field of σ. This K contains K_{0}, still has residue field F_{q}, and satisfies the conclusion of Proposition 7.

4. Proof of Theorem 2

In proving Theorem 2, we may first apply Propositions 4 and 5 to assume that the value group G is divisible and that (K, v) is maximally complete (still with residue field F_{q}). Let F = F_{q^{d!}} ⊂ \overline{K}. Proposition 7 shows that all elements of \overline{K} of degree at most d over K lie inside the compositum L := F · K of fields in \overline{K}. Extend v to L.

For each g ∈ G, choose β_{g} ∈ K with v(β_{g}) = g. Now suppose \overline{D} := \overline{D}(x_{0}, g) is a closed ball in L. Let I be the subgroup of Gal(L/K) ≅ Gal(F/F_{q}) that maps \overline{D} into \overline{D}. Division by β_{g} induces an isomorphism of I-modules \overline{D}(0, g)/D(0, g) ≅ F, so the cohomology group H^{1}(I, \overline{D}(0, g)/D(0, g)) is trivial. The long exact sequence associated with the exact sequence

0 → \frac{\overline{D}(0, g)}{D(0, g)} → \frac{L}{D(0, g)} → \frac{L}{\overline{D}(0, g)} → 0

of I-modules shows that \overline{D} contains an open disk D(x_{1}, g) mapped to itself by I. We then have a bijection of I-sets ϕ\overline{D} : \overline{D}/D(0, g) → F that maps the coset y + D(0, g) to the residue class of (y − x_{1})/β_{g}. We assume that the elements β_{g} and the maps ϕ\overline{D} are fixed once and for all.

Now let g_{u}, r, and S be as in Lemma 3, and let T be the tree associated to S as in Section 2, so that ℓ(T ) ≤ k −u. We now describe a labelling of the vertices of T by elements of F. Recall that if S_{0} ∈ T is not a leaf, and if \overline{D} = \overline{D}(s, g) is the smallest disk containing S_{0}, then the children of S_{0} are nonempty sets of the form S ∩ D(x_{0}, g) for some x_{0} ∈ \overline{D}. Label each child by ϕ\overline{D}(D(x_{0}, g)). Note that the children of S_{0} are labelled with distinct elements of F. Finally, label the root of T with the residue of r/β_{g_{u}} in F^{∗}.

Let R be the set of all roots of f in L, and let F[X]_{<k} denote the set of polynomials of the form a_{0} + a_{1}X + ⋯ + a_{k−1}X^{k−1} with a_{i} ∈ F. We now define a map Φ : R → F[X]_{<k}. First, if 0 ∈ R, define Φ(0) = 0 ∈ F[X]_{<k}. If z ∈ R is nonzero, then v(z) = g_{u} for some u. Let T_{0} > T_{1} > ⋯ > T_{n} be the maximal chain ending at T_{n} = {z} in the tree T associated to S := R ∩ D(z, g_{u}). Define Φ(z) = X^{u−1} ∑_{i=0}^{n} label(T_{i})X^{i}. Since n ≤ ℓ(T ) ≤ k − u, we have Φ(z) ∈ F[X]_{<k}. Lemma 8.

(1) The map Φ : R → F[X]_{<k} is injective.

(2) If z ∈ R is of degree j over K, then Φ(z) ∈ F_{q^{j}}[X].

Proof. To prove injectivity, we describe how to reconstruct z from Φ(z). If Φ(z) = 0, then z must be 0. Otherwise its lowest degree monomial involves X^{u−1} where v(z) = g_{u}. Hence, assuming from now on that z ≠ 0, we can reconstruct v(z) from Φ(z). Next, the coefficient of X^{u−1} determines which (nontrivial) coset of D(0, g_{u}) in \overline{D}(0, g_{u}) z belongs to. The other coefficients uniquely determine a path ending at the leaf {z} in the tree associated to this coset. Thus Φ(z) determines z.

For the second part, it suffices to show that if H is the subgroup of Gal(L/K) fixing z ∈ R, then H (or equivalently the isomorphic subgroup of Gal(F/F_{q})) fixes the coefficients of Φ(z) also. We may assume z ≠ 0. Let g_{u} = v(z), and let T_{0} > T_{1} > ⋯ > T_{n} = {z} be the maximal chain in the tree T associated to the coset z + D(0, g_{u}) in which z lies. Since H preserves the coset z + D(0, g_{u}), H fixes the label of T_{0}. Now suppose 1 ≤ i ≤ n. The smallest disk containing T_{i−1} is of the form \overline{D} := \overline{D}(z, g) for some g > g_{u}, so H is contained in the subgroup I ⊆ Gal(L/K) preserving this disk. The label of the child T_{i} is ϕ\overline{D}(z + D(0, g)), and ϕ\overline{D} respects the action of H ⊆ I, so H fixes this label. This holds for all i, so H fixes all coefficients of Φ(z). □

Lemma 8 shows that the number of zeros of f in \overline{K} of degree at most d is less than or equal to the number of polynomials in F[X]_{<k} that are defined over F_{q^{j}} for some j ≤ k. The number of such polynomials defined over F_{q^{j}} but no subfield is ∑_{i|j} q^{ik}μ(j/i), by Möbius inversion. Theorem 2 follows upon summing over j.

Acknowledgements

I thank Hendrik Lenstra for bringing the problems to my attention, and for suggesting that q^{k} might be the correct bound for Theorem 1.

References

[Le1] H. W. Lenstra, Jr., On the factorization of lacunary polynomials, to appear in Number Theory in Progress, De Gruyter, 1998.

[Le2] —, Finding small degree factors of lacunary polynomials, to appear in Number Theory in Progress, De Gruyter, 1998.

[Sch] O. Schilling, The theory of valuations, Mathematical Surveys, No. 4, Amer. Math. Soc., New York, 1950.

[St] R. Stanley, Enumerative Combinatorics, Volume 1, Cambridge University Press, 1997.

Department of Mathematics, University of California, Berkeley, CA 94720-3840, USA

  E-mail address: poonen@math.berkeley.edu