Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks! I'll take a look. –  Alex Jun 15 '11 at 6:07
    
@Alex. Cool. If the notation gets confusing or you can't follow the paper, let me know and I'll expand the answer. –  jspecter Jun 15 '11 at 6:38
    
Alright, I got it up and running and it was working AND got to tell my supervisor about copolygons, so all in all, awesome! –  Alex Jun 17 '11 at 22:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.