# Bounding $p$-adic valuations in inequality

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!

-
If by "letting some examples go through" you mean that your test does not reject some examples that it should reject, the reason is that the condition that $\mathrm{ord}_p(c_db^d)$ be greater than the minimum of all $(\mathrm{ord}_p(c_i)-\mathrm{ord}_p(c_d))/(d-i)$ in the case where $\mathrm{ord}_p(c_db^d)\leq \alpha$ is a necessary condition for $\mathrm{ord}_p(c(b))\gt\alpha$, but it is not sufficient. You could have some $c_ib^i$ with $p$-valuation higher than $c_db^d$, and yet still the valuation of $c(b)$ be less than $\alpha$ (e.g., if all the $c_ib^i$ have distinct valuations). –  Arturo Magidin Jun 16 '11 at 3:56
Hm, that is true.. I suppose I'll have to think a little more about strengthen things. Thanks! –  Alex Jun 16 '11 at 5:30
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.$