
> 
> Let $P(x) \in \mathbb{Z}[x]$ be a monic polynomial of degree $n$, with no integer roots, such that $\upsilon\_2(P(m))$ can assume $n$ different positive values, where $m \in \mathbb{Z}$ and $\upsilon\_2(P(m))$ is the $2$-adic order of $P(m)$. Hence $\upsilon\_2(P(m)) < \dfrac{3n^2}{2}$ for all integer $m$.
> 
> 
> 


This problem was proposed at a Korean math program for undergraduates.  

How this bound $\dfrac{3n^2}{2}$ can be obtained?


Can this problem be generalized, i.e., if the $p$-adic valuation of $P(x)$ can assume $k$ different positive values on integer arguments what bounds are known for $\upsilon\_p(P(m))$?



$2$-adic order bound for $P(x)$
Let $P$ be a monic polynomial of degree $n$ over $\mathbb Z$. Let $\alpha\_1,\dots, \alpha\_n$ be its roots, which we view as elements of $\overline{\mathbb Q\_p}$. Then all $p$-adic valuations of $P$ are at most


$$ n \left( k -1 + \frac{p}{(p-1)^2}\right)$$


and this is close to sharp.




---


Proof: Let $m$ be a value on which it attains a large $p$-adic valuation.


For each nonnegative integer $t$, let $$v\_t = \sum\_{i=1}^n \min( v\_p( \alpha\_i -m), t)$$


Then $v\_t$ is a strictly increasing sequence until it reaches its maximum value of $\sum\_{i=1}^n v\_p(\alpha\_i-m) = v\_p(P(m))$. We have $v\_0=0$ so $$v\_p(P(m)) = \sum\_{t=0}^{\infty} ( v\_{t+1} - v\_t).$$


For each value of $t$ before the maximum, there are two possibilities. Either some value in $[v\_t, v\_{t+1})$ occurs as $v\_p ( P (x))$ for some $x \in \mathbb Z$ or not.


Because none of these intervals contains the maximum, there are at most $k-1$ values of $t$ of the first type. For each one, $v\_{t+1} - v\_t \leq n$, so these values contribute at most $n(k-1)$ to the sum.


Now let's fix one $t$ of the second type. For any integer $u$ that's congruent to $1$ mod $p$, we have $$v\_p ( P (m + p^t u )) =\sum\_{i=1}^n v\_p ( \alpha\_i - m - p^t u ) \geq \sum\_{i=1}^n \min ( v\_p ( \alpha\_i - m ), t) = v\_t$$ so $v\_p ( P (m+p^t u ) ) \geq v\_{t+1}$ by assumption. Thus


$$ v\_{t+1} - v\_t \leq v\_p ( P ( m + p^t u)) - v\_t = \sum\_{i=1}^n ( v\_p ( \alpha\_i - m - p^t u ) - \min ( v\_p ( \alpha\_i - m ), t))$$


The difference $ v\_p ( \alpha\_i - m - p^t u ) - \min ( v\_p ( \alpha\_i - m ) $ vanishes unless $v\_p ( \alpha\_i -m ) =t$ , in which case it is $v\_p ( \frac{\alpha\_i -m}{p^t} - u ) $. So


$$ v\_{t+1} - v\_t \leq \sum\_{ i \mid v\_p (\alpha\_i -m)=t} v\_p \left( \frac{\alpha\_i -m}{p^t} - u \right)$$


This inequality, because it holds for all integers nonzero mod $p$, holds for all $p$-adic numbers nonzero mod $p$. Integrate it over all $p$-adic numbers nonzero mod $p$ (or sum over numbers nonzero mod $p$ in a large interval, divide by the length of the interval, and take the limit.


$$ \frac{p-1}{p} (v\_{t+1} - v\_t) \leq \sum\_{ i \mid v\_p (\alpha\_i -m)=t} \int\_{ u \in \mathbb Z\_p^\times} v\_p \left( \frac{\alpha\_i -m}{p^t} - u \right) du \leq \sum\_{ i \mid v\_p (\alpha\_i -m)=t} \left( \frac{1}{p} + \frac{1}{p^2} + \dots \right) = \sum\_{ i \mid v\_p (\alpha\_i -m)=t} \frac{1}{p-1} $$


because the function $v\_p ( \frac{\alpha\_i -m}{p^t} - u )$ is at most $1$ restricted to $u$ that are congruent to $\frac{\alpha\_i -m}{p^t}$ mod $p$ plus $1$ restricted to $u$ that are congruent to $\frac{\alpha\_i -m}{p^t}$ mod $p^2$ plus...


Thus


$$v\_{t+1} - v\_t= \left| \{ i \mid v\_p (\alpha\_i -m)=t\}\right| \frac{p} {(p-1)^2} $$


Summing this over all $t$, these terms contribute at most $ n \frac{p}{ (p-1)^2}$ since we can have $ v\_p (\alpha\_i -m)=t$ for at most one $t$. Adding the contribution of the two types of terms, we get the claim.




---


Construction:


Let $n = 2 \cdot p^r$ for $r>0$.


Take $$P(m) = \prod\_{i=0}^{p^{r}-1} (m - p^{k-1} (i + p^{r-1} \sqrt{p})) (m- p^{k-1} (i-p^{r-1} \sqrt{p})) = \prod\_{i=0}^{p^{r}-1} ( (m-p^{k-1} i)^2 -p^{2k+2r-3} )$$


which indeed is monic with integer coefficients.


Then $v\_p(P(m))$ takes the value $2 p^r v\_p(P (m))$ if $v\_p(P(m)) < k-1$. So to show it takes at most $k$ values, it suffices to show it takes the same value at all $m$ with $v\_p(m) \geq k-1$. For such $m$, we must have $m$ congruent to $j p^{k-1} \mod p^{ r+ k-1}$ for some $0 \leq j < p^{r}$.


Then


$$v \_p ( m- p^{k-1} ( i \pm p^{r-1} \sqrt{p} )) = v\_p ( p^{k-1} ( j-i \pm p^{r-1} \sqrt{p} + O ( p^r)))$$


which if $j-i$ has $p$-adic valuation $r$, is $k-1 + v\_p(j-i)$ because the $j-i$ term dominates, and if $j-1$ has $p$-adic valuation $r-1$, is $ k-1 + r - \frac{1}{2}$ because the $p^{r-1} \sqrt{p}$ term dominates.


For any $j$, we have $v\_p(j-i)=0$ for $p^r - p^{r-1}$ values of $i$, $=1$ for $p^{r-1} - p^{r-2}$ values of $i$, and so on, up to $p$-adic valuation at least $r$ for one value of $i$.


Summing over all $i$, we get $$ \sum\_{i=0}^{p^r-1} \left(k-1 + \min \left( v\_p (j-i), r-\frac{1}{2} \right) \right) =p^r (k-1) + p^{r-1} + p^{r-2} + \dots + 1 - \frac{1}{2},$$ and doubling to account for signs gives $$v\_p ( P(m)) = 2 p^r (k-1) + \frac{2(p^r -1)}{p-1} -1 = n \left( k-1 + \frac{1}{p-1} \right) - O(1),$$ which almost matches our upper bound.


