2
$\begingroup$

I'm developing an algorithm that comes across inequalities of the form \begin{align*} \operatorname{ord}_p(c(b)) > \alpha \end{align*} for some polynomial $c \in \mathbb{Q}[b]$, $c(b) = c_0 + c_1b + \ldots + c_db^d$ and integer $\alpha$. I need to find a lower bound on the valuation of $b$ that can satisfy the inequality and I'm having difficulty coming up with the bound.

We could suppose the valuation of $b$ is really small, so that $\operatorname{ord}_p(c_db^d) < \operatorname{ord}_p(c_ib^i)$ for $0 \leq i < d$ if $c_i \neq 0$. Then, by the non-archimedean triangle inequality, we would have that $\operatorname{ord}_p(c(b)) = \operatorname{ord}_p(c_db^d)$ and we have two cases to consider. Either $\operatorname{ord}_p(c_db^d) \leq \alpha$ or $\operatorname{ord}_p(c_db^d) > \alpha$. In the first case we know the polynomial $c(b)$ would have too small a valuation, so we require (at least) one monomial such that \begin{align*} \operatorname{ord}_p(c_ib^i) \leq \operatorname{ord}_p(c_db^d) \end{align*} and rearranging, this gives \begin{align*} \operatorname{ord}_p(b) \geq \frac{\operatorname{ord}_p(c_i) - \operatorname{ord}_p(c_d)}{d - i}. \end{align*} So, if $\operatorname{ord}_p(c_db^d) \leq \alpha$, we require

\begin{align*} \operatorname{ord}_p(b) \geq \min_i \frac{\operatorname{ord}_p(c_i) - \operatorname{ord}_p(c_d)}{d - i}. \end{align*} On the other hand, if $\operatorname{ord}_p(c_db^d) > \alpha$, then we may already see that \begin{align*} \operatorname{ord}_p(b) > \frac{\alpha - \operatorname{ord}_p(c_d)}{d}. \end{align*}

Putting both of these together, we always require \begin{align*} \operatorname{ord}_p(b) > \min \left(\min_i \frac{\operatorname{ord}_p(c_i) - \operatorname{ord}_p(c_d)}{d - i}, \frac{\alpha - \operatorname{ord}_p(c_d)}{d}\right) \end{align*}

I've tested a number of runs on the algorithm, and I know it's letting some examples go through (quite a few!), but I'm not too sure where the error is.

Thanks!

  • 0
    Hm, that is true.. I suppose I'll have to think a little more about strengthen things. Thanks!2011-06-16

1 Answers 1

4

For any $c\in\mathbb{Q}_p[X]$ and $b\in\mathbb{\overline{{Q}}}_p$ of $p$-adic valution not equal to that of a root of $c,$ the exact valuation of $c(b)$ can be read off from a geometric object called the newton copolygon of $c.$

For a description see section 2 of this paper by Li.

  • 0
    Alright, I got it up and running and it was working AND got to tell my supervisor about copolygons, so all in all, awesome!2011-06-17