Newton Polygons and Factoring polynomials over Local Fields

Andrei Jorza

March 8, 2005

1 Generalities

Let K be a number field. We have seen that a finite place of K is a valuation v : K → ℤ ∪ {∞} such that v(xy) = v(x) + v(y), v(x + y) ≥ min(v(x), v(y)) and v(0) = ∞. This defines the metric |x|_{v} = q_{v}^{−v(x)} where q_{v} = #k_{v} the size of the residue field k_{v} = O_{v}/℘_{v}. Here K_{v} is the completion of K at v, O_{v} is the ring of integers of K_{v} and ℘_{v} is the maximal ideal of the local ring O_{v}.

Let v be a finite place. Let f(x) ∈ K_{v}[x] be a polynomial f(x) = f_{0} + f_{1}x + ⋯ + f_{n}x^{n}. The Newton polygon NP (f) is the lower convex hull of the points {(0, ∞), (n, ∞)} ∪ {P_{i} = (i, v(f_{i}))|i = 0, 1, …, n}. The NP (f) is a polygonal like formed by two vertical lines together with a set of lines of various slopes.

Proposition 1.1. Let f be a polynomial of degree n. If u is a root of f then there exists a segment in NP (f) of slope equal to −v(u).

Proof. We have f_{0} + f_{1}u + ⋯ + f_{n}u^{n} = 0. If min v(f_{i}u^{i}) is uniquely attained, then the nonarchimedean property of v would imply that v(f_{0} + f_{1}u + ⋯ + f_{n}u^{n}) = min(v(f_{i}u^{i})) = v(0) = ∞ which cannot be. So ∃i ≠ j such that v(f_{i}u^{i}) = v(f_{j}u^{j}). But this corresponds to the line of slope −v(u) through P_{i} and P_{j}. The valuation v(f_{i}u^{i}) is the place where this line intersects the vertical axis and the fact that this valuation is minimal implies that all the points on NP (f) are on or above this line. So this line contains a segment of NP (f) which proves the lemma.

Example 1.2. Let p be a prime number and let f(x) = x^{3} + px^{2} + px + p^{2} ∈ ℚ_{p}[x]. According to the theory this will have one root of valuation 1 and two roots of valuation 1/2.

Proposition 1.3. Let f, g ∈ K_{v}[x] be two polynomials (f = f_{0} + ⋯ + f_{d}x^{d}, g = g_{0} + ⋯ + g_{e}x^{e}) such that all the slopes of NP (f) are less or equal to all the slopes of NP (g). Then NP (fg) is obtained by adjoining NP (f) and NP (g) in the following explicit manner (here we interpret NP (f) as a piecewise linear function in x)

NP (fg)(x) = \begin{cases}NP (f)(x) + NP (g)(0), x ∈ [0, d] \\ NP (f)(d) + NP (g)(x − d), x ∈ [d, d + e] \end{cases}

Example 1.4. f(x) = x^{3} + px^{2} + px + p^{2}, g(x) = px^{2} + x + 1 and

(fg)(x) = px^{5} + (p^{2} + 1)x^{4} + (p^{2} + p + 1)x^{3} + px^{2} + px + p^{2}.

Proof. (fg)(x) = ∑_{0}^{d+e} h_{i}x^{i} where h_{i} = ∑ f_{j}g_{i−j}. If i ∈ [0, d] then

v(h_{i}) = v(g_{0}f_{i} + ⋯ + g_{j}f_{i−j} + ⋯)

and v(g_{0}f_{i}) = v(g_{0}) + v(f_{i}) ≥ NP (g)(0) + NP (f)(i) with equality if NP (f)(i) = v(f_{i}). For j > 0 we still have v(g_{j}f_{i−j}) ≥ NP (g)(j) + NP (f)(i − j) > NP (g)(0) + NP (f)(i) because of the slope condition (⟺ NP (g)(j) − NP (g)(0) > NP (f)(i) − NP (f)(i − j)). This takes care of the case i ∈ [0, d].

Now assume that i ∈ [d, d + e]. Then h_{i} = f_{d}g_{i−d} + ⋯ + f_{d−j}g_{i+j−d} + ⋯ and the proof is similar.

2 Factorization

This is a very nice theorem since it tells you that you can compose Newton polygons when multiplying polynomials. Can we go the other way around? The answer is yes. But first we need a technical lemma:

Lemma 2.1. Let c ∈ ℝ. Write v_{c}(f) = min(v(f_{i})+ic). Then v_{c}(fg) = v_{c}(f)+v_{c}(g), v_{c}(f +g) ≥ min(v_{c}(f), v_{c}(g)).

Proof. Let v_{c}(f) = v(f_{i}) + ic, v_{c}(g) = v(g_{j}) + jc. So v_{c}(f) + v_{c}(g) = v(f_{i}g_{j}) + (i + j)c ≤ v(∑ f_{u}g_{i+j−u}) + (i + j)c) ≤ v_{c}(fg) because v(h_{i}) ≥ min v(f_{j}) + v(g_{i−j}). In the other direction, v_{c}(fg) ≤ v(h_{i+j}) + (i + j)c = v(∑ f_{i−k}g_{j+k}) + (i + j)c. If k ≠ 0 then v(f_{i−k}g_{j+k}) + (i + j)c > v_{c}(f) + v_{c}(g) by choice of i and j. So v(∑ f_{i−k}g_{j+k}) + (i + j)c = v(f_{i}g_{j}) + (i + j)c = v_{c}(f) + v_{c}(g).

Lemma 2.2. This essentially bounds the quantities in the division with remainder. Let f, h ∈ K_{v}[x] with deg f = d and v_{c}(f) = v(f_{d}) + dc. Write h = qf + r division with remainder. Then v_{c}(q) ≥ v_{c}(h) − v_{c}(f) which in turn implies that v_{c}(r) ≥ v_{c}(h).

Proof. If h has degree n and let deg f = d; write q = q_{0} + ⋯ + q_{n−d}x^{n−d}. If we show by induction on i that v_{c}(q_{n−d−i}x^{n−d−i}) ≥ v_{c}(h) − v_{c}(f) then we are done.

For each i ≤ n − d there is no contribution from r in the formula for h_{n−i} so h_{n−i}x^{n−i} = f_{d}q_{n−d−i}x^{n−i} + f_{d−1}q_{n−d−i+1}x^{n−i} + · · ·.

Note that v_{c}(f_{d}q_{n−d−i}x^{n−i}) = v_{c}(f) + v_{c}(q_{n−d−i}x^{n−i−d}) by the hypothesis on f. Also, from the inductive hypothesis we get that v_{c}(q_{n−d−(i−j)}x^{n−d−(i−j)}) ≥ v_{c}(h) − v_{c}(f) which implies that v_{c}(f_{d−j}q_{n−d−i+j}x^{n−i}) ≥ v_{c}(h). So

v_{c}(f_{d}q_{n−d−i}x^{n−i}) = v_{c}(h_{n−i}x^{n−i} − ∑_{j>0} f_{d−j}q_{n−d−i+j}x^{n−i}) ≥ v_{c}(H),

which implies the result for i given the result for i − j for j > 0.

Now v_{c}(r) = v_{c}(h − fq) ≥ min(v_{c}(h), v_{c}(f) + v_{c}(q)) = v_{c}(h).

The reason why this technical lemma is important is that it gives an algorithmic way to approximate factorizations of polynomials.

Theorem 2.3. Let h ∈ K_{v}[x] be a polynomial of degree d+e and let d be a point of discontinuity in NP (h). We saw in Proposition 1.3 that such Newton polygons arise when h is the product of a polynomial of degree d and one of degree e. This theorem states that each h arise in such manner.

Proof. As mentioned, the prood will be algorithmic. Let f_{0} = h_{0} + ⋯ h_{d}x^{d}, the first d terms in the expansion of h and let g_{0} = 1. Choose c such that v_{c}(h) = v_{c}(h_{d}x^{d}) and such that d is the smallest index with this property (v_{c}(h) ≠ v_{c}(h_{i}x^{i}), i > d).

Now v_{c}(h − f_{0}g_{0}) = ε > 0 and v_{c}(f_{0}) = v_{c}(h). We’ll construct f_{i}, g_{i} such that deg f_{i} = d, deg g_{i} ≤ n − d, v_{c}(f_{i}) = v_{c}(h), v_{c}(f_{i} − f_{i+1}) ≥ v_{c}(h) + iε, v_{c}(g_{i} − g_{i−1}) ≥ iε and finally v_{c}(h − f_{i}g_{i}) ≥ v_{c}(h) + (i + 1)ε. Clearly this implies that f_{i} → f, g_{i} → g, f_{i}g_{i} → fg, h so h = fg.

Write h − f_{i}g_{i} = qf_{i} + r, division with remainder. Take f_{i+1} = f_{i} + r, g_{i+1} = g_{i} + q. Let’s show that the conditions are satisfied. The conditions on the degrees are clearly satisfied.

Now v_{c}(f_{i+1} − f_{i}) = v_{c}(r) ≥ v_{c}(h − f_{i}g_{i}) and v_{c}(g_{i+1} − g_{i}) = v_{c}(q) ≥ v_{c}(h − f_{i}g_{i}) − v_{c}(f_{i}) by Lemma 2.2. In particular this shows that v_{c}(f_{i+1}) = v_{c}(f_{i}) = v_{c}(h).

By the inductive hypothesis we have v_{c}(h − f_{i}g_{i}) ≥ v_{c}(h) + (i + 1)ε so we have v_{c}(r) ≥ v_{c}(h) + (i + 1)ε which implies that v_{c}(f_{i+1} − f_{i}) ≥ v_{c}(h) + (i + 1)ε, the first condition. Also v_{c}(q) ≥ v_{c}(h) + (i + 1)ε − v_{c}(f_{i}) = (i + 1)ε and so v_{c}(g_{i+1} − g_{i}) ≥ (i + 1)ε.

Lastly, v_{c}(h − (f_{i} + r)(g_{i} + q)) = v_{c}(h − f_{i}g_{i} − f_{i}q − rg_{i} − rq) = v_{c}(r − rg_{i} − rq) = v_{c}(r) + v_{c}(1 − g_{i} − q) but this is ≥ v_{c}(h) + (i + 1)ε + min(v_{c}(1 − g_{i}), v_{c}(q)). The condition on g_{i} implies that v_{c}(1 − g_{i}) ≥ ε and v_{c}(q) ≥ (i + 1)ε. So we get what we want.

Problem 2.4. Let f ∈ K_{v}[x] such that NP (f) consists of one segment that contains no other lattice points. Then f is irreducible.

Proof. Assume it is reducible. Then f = gh and each roots of g, h has to have the same valuation as f so the NP of g and h have the same slope as that of f. But then we can put NP (g) at the top of NP (f) and we get a lattice point on NP (f). So f is irreducible.

Problem 2.5. Factor the following polynomials x^{3} + 5x + 25, x^{3} + 5x^{2} + 25 ∈ ℚ_{5}[x].

3 Galois Groups

Let L_{w}/K_{v} be a Galois extension.

Lemma 3.1. Let α, β ∈ L_{w} such that v(β − σα) < v(σα − α) for any σ ∈ Gal(L_{w}/K_{v}) \ Gal(L_{w}/K_{v}(α)). Prove that α ∈ K_{v}(β).

Proof. Let σ ∈ Gal(L_{w}/K_{v}(β)). We want to show that σα = α which is enough to prove the lemma. Assume that σα ≠ α so v(α − σα) > v(β − σα) = v(σ(β − α)) = v(β − α) = v(β − σα + σα − α) ≥ min(v(β − σα), v(α − σα)) = v(α − σα) which is a contradiction.

Theorem 3.2 (Krasner). Let f ∈ K_{v}[x] be a monic irreducible polynomial of degree d. Let x_{1}, …, x_{d} be the roots of f and let ε = max_{i≠j} v(x_{i} −x_{j})/2 and let C = max(dε, v(f_{i})). Assume that g is a polynomial of degree d in K_{v}[x] such that v_{0}(f − g) > C. Then g is irreducible and K_{v}[x]/(f) ≅ K_{v}[x]/(g). (This essentially says that the two Galois groups are equal.)

Proof. Since C > v(f_{i}) the Newton polygon says that f ≅ g (mod p_{v}) so if g factors by Hensel’s lemma f factors. (I won’t prove Hensel’s lemma here.) So assume g is irreducible.

Let y_{1}, …, y_{d} be the roots of g. By dimension count enough to show that y_{i} ∈ K_{v}(x_{j}). For this it is enough by Lemma 3.1 to show that there exist i and j such that for all k we have v(y_{i}−x_{j}) > v(x_{k} −x_{j}), for then v(y_{i}−x_{j}) > v(x_{k} −x_{j}) ≥ min(v(x_{k} −y_{i}), v(y_{i}−x_{j})) = v(x_{k} −y_{i}) which gives the result.

Now, v(f(y_{j})) = v(f(y_{j}) − g(y_{j})) = v(∑(f_{i} − g_{i})y_{j}^{i}) = λ = \begin{cases}C \\ C + nv(y_{j}) \end{cases} . But here the

polynomials are monic so v(y_{i}) ≥ 0 so C ≤ v(f(y_{j})) = v(∏(y_{j} − x_{k})) = ∑ v(y_{i} − x_{k}). For at least one k we have v(y_{j} − x_{k}) ≥ C/d > ε so the hypotheses are satisfied.

Example 3.3. Let K/ℚ_{3} be the extension defined by the polynomial f(x) = x^{4} −10x^{2} +27x+1. Find Gal(K/ℚ_{3}).

Proof. The idea is that g(x) = x^{4} − 10x^{2} + 1 has roots ±\sqrt{2} + ±\sqrt{3} so the Galois group of g is (ℤ/2ℤ)^{2}.

So now all we need is that f and g satisfy the hypotheses of Theorem 3.2.

We start out with g instead of f. Would like to have C = v_{0}(f −g) = 3. Then C > v(g_{i}) = 0 so the only inequality we want to check is that C > 4ε. But ε = 1/2 so the hypotheses are satisfied.