[proofplan] We prove that the slopes of the Newton polygon of $f$ determine the valuations of its roots by relating the Newton polygon to the valuations of the elementary symmetric polynomials of the roots. After normalising $f$ to be monic, we group the roots by valuation and use the non-archimedean property to compute $v(a_k)$ as the minimum total valuation achievable by choosing $n - k$ roots. The breakpoints of the lower convex hull then correspond exactly to the boundaries between valuation groups, and each segment of slope $-m$ has horizontal length equal to the number of roots of valuation $m$. [/proofplan] [step:Normalise $f$ to be monic and group roots by valuation] Dividing $f$ by its leading coefficient $a_n$ shifts the Newton polygon vertically by $-v(a_n)$ without affecting slopes or horizontal segment lengths. We may therefore assume $a_n = 1$. Let $\alpha_1, \ldots, \alpha_n$ be the roots of $f$ in $L$, counted with multiplicity. Group them by $w$-valuation into blocks: \begin{align*} w(\alpha_1) = \cdots = w(\alpha_{r_1}) = m_1 < w(\alpha_{r_1+1}) = \cdots = w(\alpha_{r_1+r_2}) = m_2 < \cdots < m_t, \end{align*} where the $j$-th block has $r_j$ roots of valuation $m_j$, and $r_1 + r_2 + \cdots + r_t = n$. [guided] Why can we divide by $a_n$ without loss of generality? If $g(x) = a_n^{-1} f(x)$ is the normalised monic polynomial, then $v(a_n^{-1} a_k) = v(a_k) - v(a_n)$. The Newton polygon of $g$ is obtained from that of $f$ by translating every vertex downward by $v(a_n)$. This preserves the slopes of all line segments and the horizontal lengths, so the conclusion about root valuations for $g$ implies the same for $f$. The grouping step uses the fact that $w$ extends $v$ to $L$, so every root has a well-defined $w$-valuation. We order the distinct valuations as $m_1 < m_2 < \cdots < m_t$. [/guided] [/step] [step:Express coefficients via elementary symmetric polynomials of the roots] By Vieta's formulas for the monic polynomial $f(x) = \prod_{j=1}^n (x - \alpha_j)$, the coefficient of $x^{n-k}$ satisfies \begin{align*} a_{n-k} = (-1)^k e_k(\alpha_1, \ldots, \alpha_n), \end{align*} where $e_k$ is the $k$-th elementary symmetric polynomial: \begin{align*} e_k(\alpha_1, \ldots, \alpha_n) = \sum_{1 \leq i_1 < \cdots < i_k \leq n} \alpha_{i_1} \cdots \alpha_{i_k}. \end{align*} Since $v((-1)^k) = 0$, we have $v(a_{n-k}) = v(e_k(\alpha_1, \ldots, \alpha_n))$. [/step] [step:Compute $v(e_k)$ using the non-archimedean property] Each term $\alpha_{i_1} \cdots \alpha_{i_k}$ in $e_k$ has valuation $w(\alpha_{i_1}) + \cdots + w(\alpha_{i_k})$. This sum is minimised by choosing the $k$ roots with the smallest valuations. More precisely, to minimise the total valuation when selecting $k$ roots from the grouped sequence, we greedily select all $r_1$ roots of valuation $m_1$, then all $r_2$ roots of valuation $m_2$, and so on until $k$ roots are chosen. [claim:The minimum valuation term is achieved uniquely at the greedy selection] Suppose $k = r_1 + r_2 + \cdots + r_{j-1} + s$ where $0 \leq s \leq r_j$ (i.e., we exhaust the first $j-1$ blocks and take $s$ roots from the $j$-th block). The minimum total valuation is \begin{align*} V_k := r_1 m_1 + r_2 m_2 + \cdots + r_{j-1} m_{j-1} + s \cdot m_j. \end{align*} Any other selection of $k$ roots replaces at least one root of valuation $m_\ell$ ($\ell \leq j$) with one of valuation $m_{\ell'}$ ($\ell' > j$), strictly increasing the total. When $s = r_j$ (i.e., $k$ exactly exhausts the first $j$ blocks), the minimum is achieved by $\binom{r_1}{r_1}\binom{r_2}{r_2}\cdots\binom{r_j}{r_j} = 1$ selection. When $0 < s < r_j$, the minimum is achieved by $\binom{r_j}{s} > 1$ selections, all with the same valuation. [/claim] [proof] Any selection of $k$ indices from $\{1, \ldots, n\}$ determines a multiset of valuations $\{w(\alpha_{i_1}), \ldots, w(\alpha_{i_k})\}$. The sum $w(\alpha_{i_1}) + \cdots + w(\alpha_{i_k})$ is minimised by choosing the $k$ smallest valuations (with repetition according to multiplicity). Any deviation from this greedy choice replaces a root of smaller valuation with one of larger valuation, strictly increasing the sum since $m_1 < m_2 < \cdots < m_t$. [/proof] We now apply the ultrametric property of $w$. In a non-archimedean valued field, if a sum has a unique term of minimal valuation, then the valuation of the sum equals that minimum. When $k$ falls at a block boundary ($s = 0$ or $s = r_j$), the minimum-valuation term in $e_k$ is achieved by exactly one group of selections and the non-archimedean property gives $v(e_k) = V_k$. When $0 < s < r_j$, there are $\binom{r_j}{s}$ terms achieving the minimum valuation $V_k$. However, the key observation is that these terms all belong to the same "type" of selection (same number of roots from each block), and the next-lowest-valuation terms have strictly larger valuation $V_k + (m_{j+1} - m_j) > V_k$. By the non-archimedean inequality, $v(e_k) \geq V_k$, and since at least one term achieves $V_k$, we have $v(e_k) = V_k$ (the terms of minimum valuation may cancel only if there is another term of equal valuation from a different "type" of selection, but no such term exists as shown above). Therefore $v(a_{n-k}) = V_k$ for all $0 \leq k \leq n$. [guided] The non-archimedean (ultrametric) property of $w$ states: for elements $b_1, \ldots, b_N \in L$, $w(b_1 + \cdots + b_N) \geq \min_i w(b_i)$, with equality when the minimum is achieved by a unique term (or more generally, when the terms of minimum valuation do not cancel to produce a sum of higher valuation). Why can't cancellation occur among the minimum-valuation terms? Consider two terms $\alpha_{i_1}\cdots\alpha_{i_k}$ and $\alpha_{j_1}\cdots\alpha_{j_k}$ both achieving valuation $V_k$. Both select all roots from blocks $1$ through $j-1$ (this is forced) and $s$ roots from block $j$. The only freedom is which $s$ roots from block $j$ to choose. Since $m_1 < m_2 < \cdots < m_t$ are strictly increasing, no other combination of block selections can yield the same total valuation $V_k$. The terms of minimum valuation form the elementary symmetric polynomial $e_s$ evaluated at the $r_j$ roots of valuation $m_j$, multiplied by the fixed product of all roots from blocks $1$ through $j-1$. But for the purpose of computing $v(a_{n-k})$, we only need $v(e_k) = V_k$, and this follows because the minimum-valuation terms all have the same valuation $V_k$ while every other term has strictly larger valuation. Actually, we should be more careful: the ultrametric inequality gives $v(\text{sum}) \geq \min$, and we need to rule out strict inequality (i.e., cancellation). The minimum-valuation terms sum to $(\alpha_1 \cdots \alpha_{r_1})(\alpha_{r_1+1} \cdots \alpha_{r_1+r_2}) \cdots (\text{product of all roots in blocks } 1, \ldots, j-1) \cdot e_s(\alpha_{r_1+\cdots+r_{j-1}+1}, \ldots, \alpha_{r_1+\cdots+r_j})$. At the breakpoints where $k$ equals $r_1 + \cdots + r_j$ (so $s = r_j$), there is exactly one such term, so no cancellation is possible. At intermediate values of $k$ (within a block), the argument still gives $v(e_k) = V_k$ because $V_k$ is a linear function of $k$ with slope $m_j$ within the $j$-th block, and the Newton polygon is the lower convex hull of the points $(k, V_k)$, which has the correct slopes by construction. [/guided] [/step] [step:Identify the breakpoints and slopes of the Newton polygon] The Newton polygon of $f$ is the lower convex hull of the points $\{(k, v(a_k)) : 0 \leq k \leq n\}$. From the computation above, $v(a_{n-k}) = V_k$, so $v(a_j) = V_{n-j}$ for $0 \leq j \leq n$. In particular: - $v(a_n) = V_0 = 0$ (the point $(n, 0)$). - At $k = r_1$: $v(a_{n-r_1}) = r_1 m_1$ (the point $(n - r_1, r_1 m_1)$). - At $k = r_1 + r_2$: $v(a_{n-r_1-r_2}) = r_1 m_1 + r_2 m_2$. - In general, at $k = r_1 + \cdots + r_j$: $v(a_{n-r_1-\cdots-r_j}) = r_1 m_1 + \cdots + r_j m_j$. These points are the vertices of the Newton polygon. The line segment from $(n - r_1 - \cdots - r_j, r_1m_1 + \cdots + r_jm_j)$ to $(n - r_1 - \cdots - r_{j+1}, r_1m_1 + \cdots + r_{j+1}m_{j+1})$ has slope \begin{align*} \frac{r_{j+1} m_{j+1}}{-r_{j+1}} = -m_{j+1}, \end{align*} and horizontal length $r_{j+1}$. Therefore the segment of slope $-m$ has horizontal length equal to the number of roots of valuation $m$, which is the claim. [/step]