Integer-valued polynomials divisible by 2 or 3

Question

I would like some help with the following problem:

Suppose that $p \in \operatorname{Int}(\mathbb{Z}) = \{p \in \mathbb{Q}[X] : p(\mathbb{Z}) \subseteq \mathbb{Z}\}$ is such that for all $z \in \mathbb{Z}$, either $2$ divides $p(z)$ or $3$ divides $p(z)$. Show that the quantifiers may be reversed, i.e., that either for all $z \in \mathbb{Z}$ we have $2$ divides $p(z)$, or for all $z \in \mathbb{Z}$ we have $3$ divides $p(z)$.

I thought of using the fact that $\{\binom{X}{k} \mid k \in \mathbb{N}\}$ is a $\mathbb{Z}$-basis of $\operatorname{Int}(\mathbb{Z})$, where $$\binom{X}{k} = \frac{X (X - 1) \cdots (X - k + 1)}{k!}$$ (in particular $\binom{X}{0} = 1$). Therefore, for a fixed $p \in \operatorname{Int}(\mathbb{Z})$, I can write $$p = \sum_{i=1}^k a_i \binom{X}{i}$$ for some $k \in \mathbb{N}$ and $a_1, \ldots, a_k \in \mathbb{Z}$.

I tried to show the contrapositive: suppose that there is $z_2, z_3 \in \mathbb{Z}$ such that $2 \nmid p(z_2)$ and $3 \nmid p(z_3)$. Then there is $1 \leq i, j \leq k$ such that $2 \nmid a_i$ and $3 \nmid a_j$. But then I don't quite know how to find a $z$ with both $2 \nmid p(z)$ and $3 \nmid p(z)$, just as I don't see how "for all $z \in \mathbb{Z}$, either $2$ divides $p(z)$ or $3$ divides $p(z)$" relates to the coefficients of $p(z)$.

Is my approach correct, and how should I proceed?

Answer 1

Let $q$ be an integer valued polynomial and let $x,y$ be integers. Then $x-y$ divides $q(x)-q(y)$.

Well, we wish this was true. It is not : take $P_2(x) = \frac{x(x-1)}{2}$ then $P_2(4) - P_2(2) = 6-1 = 5$ is not a multiple of $4-2$.

Let's imagine it was the case. Then, we could do the following : let $a_1$ be such that $2$ doesn't divide $p(a_1)$ and $a_2$ be such that $3$ doesn't divide $p(a_2)$. We'd know that for all integers $k,l$, we have $p(a_1+2k) \equiv p(a_1) \pmod{2}$ and $p(a_2 + 3l) \equiv p(a_2) \pmod{3}$. In particular, for any $k,l$ integers, $p(a_1+2k)$ is never a multiple of $2$ and $p(a_2+3l)$ is never a multiple of $3$. However, because $2$ and $3$ are co prime we can find $k,l$ integers such that $a_2-a_1 = 2k-3l$. That is , $a_1+2k = a_2+3l = K$, say. But then $p(K)$ is not a multiple of $2$ or $3$, a contradiction.

---

Now, the wish we want is not granted by the mathematical gods. But we can do something very interesting, that makes the above argument a possibility. I state a lemma in general, which I then exploit to show the answer. First a definition.

Let $p$ be a prime and $K$ an integer. Then $\nu_p(K)$ is the largest power of $p$ which divides $K$ i.e. such that $p^{\nu_p(K)}$ divides $K$ but $p^{\nu_p(K)+1}$ does not divide $K$. We refer to this as the $p$-adic valuation.

Now, the $p$-adic valuation is non-negative. However, one can also easily verify that $\nu_p(a+b) \geq \min\{\nu_p(a),\nu_p(b)\}$, and $\nu_p(ab) = \nu_p(a)+\nu_p(b)$ quite easily.

Lemma[Cahen-Chabert] : Let $f$ be an integer valued polynomial, with $\deg(f) < p^h$ for some positive integer $h$. Then $$ \nu_p(f(b)-f(a)) \geq \nu_p(b-a) -h+1 $$ for all integers $a,b$.

Proof : Replacing $f(x)$ by $x \to f(a+x) - f(a)$ we can assume that $a=0$ and $f(0) = 0$. Thus it is enough to show that $\nu_p(f(b)) \geq \nu_p(b) - h+1$. We know that $f_n(x) = \binom xn$ forms a basis of integer valued polynomials, so we can verify that this holds for $f_n$ with $n<p^h$.

Well, for $n=0,1$ it is pretty obvious. For $n \geq 2$, write : $$ f_n(x) = \frac xn g(x) $$ where $g(x) = \frac{\prod_{i=1}^{n-1}(x-i)}{(n-1)!}$. Now, for any $b$ we get $nf_n(b) = bg(b)$ and therefore $$ \nu_p(f_n(b)) = \nu_p(b) + \nu_p(g(b)) - \nu_p(n) $$

but $g$ is a well known integer polynomial, since the product of any $n$ consecutive integers is a multiple of $n!$ (this can be shown in multiple ways). Also, $n<p^h$ so $\nu_p(n) \leq h-1$. Therefore, the result follows.

---

So we have the Cahen-Chabert lemma. This plays a very important role in the proposed proof.

Indeed, let $p$ be an integer valued polynomial such that $p(z)$ is either a multiple of $2$ or $3$ for every $z$. Then we know that there exist $D,D' > 1$ such that $\deg p < 2^D$ and $\deg p < 3^{D'}$.

Now, let $a_1$ be any integer. Then consider $a_1 + k2^{D}$. Then let $a = a_1$ and $b = a_1 + k2^D$ in the Cahen-Chabert lemma. We get : $$ \nu_2(f(a_1+k2^D) - f(a_1)) \geq \nu_2(k2^D) - D+1 \geq 1 $$

Therefore, $f(a_1+k2^D) - f(a_1)$ is a multiple of $2$ for all integers $k$.

In similar fashion, for all $a_2$, we know that $f(a_2 + l3^{D'}) - f(a_2)$ is a multiple of $3$ for all integers $l$.

Now, can you figure out the rest, using the argument we wished was the case?

Note : I call this lemma the Cahen-Chabert lemma : in truth, I do not know where one can find it. It does seem to be a useful result, though, judging on this question at least.

---

I'd like to think there are generalizations. For example, one can probably replace $2,3$ by any pair of coprime integers. I also think one can replace a pair of coprime integers by any set of integers with gcd $1$ (for example, an integer valued polynomial such at every $z$ we have $p(z)$ is a multiple of $6,15$ or $10$ then $p(z)$ is divisible by one of them for all $z$).

These can be tried as exercises. I will elaborate upon requirement the way to do these, but roughly it's about playing with the $h$ and $p$ in the Cahen-Chabert lemma.

Answer 2

Let $f$ denote the polynomial $p$ in OP, $r,s\in\Bbb N$ and $u\in\Bbb Z\setminus\{0\}$ such that $2\nmid u$, $3\nmid u$ and $g=2^r3^suf$ is a polynomial with integer coefficients.

Assume that there exists $a,b\in\Bbb Z$ such that $2\nmid f(a)$  and $3\nmid f(b)$. By chinese remainder theorem, there exists $c\in\Bbb Z$ such that \begin{align} c&\equiv a\pmod{2^{r+1}}& c&\equiv b\pmod{3^{s+1}} \end{align} hence \begin{align} g(c)&\equiv g(a)\not\equiv 0\pmod{2^{r+1}}& g(c)&\equiv g(b)\not\equiv 0\pmod{3^{s+1}} \end{align} consequently, $2\nmid f(c)$ and $3\nmid f(c)$ - a contradiction.