# A congruence involving roots of unity

Let $f(x) \in \mathbb{Z}[x]$ and suppose $f(\omega^j) \in \mathbb{Z}$ for all $j= 1, \dots, n$ where $\omega = e^{2 \pi i/n}$ is a primitive $n^{\text{th}}$ root of unity.

Computational evidence suggests

$$f(\omega^{p^e}) \equiv f(\omega^{p^{e-1}}) (\text{mod } p^e),$$ for all primes $p$ and positive integers $e \geq 1$.

Is there a proof, or a counterexample?

Note that by Euler's theorem, for every $a \in \mathbb{Z}$ such that $\text{gcd}(a,n) = 1$ we have $$a^{\phi(n)} \equiv 1 (\text{mod }n),$$ where $\phi(n) = |\{ k \in [n] : \text{gcd}(n,j) = 1 \}|$ denotes Euler's totient function.

In particular if $n = p^e$, then $\phi(p^e) = p^e-p^{e-1}$ so

$$a^{p^e-p^{e-1}} \equiv 1 (\text{mod }p^e),$$ whenever $\text{gcd}(a,p) = 1$.

Thus by modular arithmetic we can move the modulo inside the argument and get

$$f(x^{p^e}) = f(x^{p^e-p^{e-1}} x^{p^{e-1}}) \equiv f(x^{p^{e-1}}) (\text{mod } p^e).$$

Therefore the congruence holds for all integer polynomials at all integer points relatively prime to $p$. My question is if this congruence can be lifted to $n^{\text{th}}$ roots of unity if $f(x)$ takes integer values at all $n^{\text{th}}$ roots of unity?

By the way, if $f(\omega^j) \in \mathbb{Z}$, then it is well-known that $f(\omega^j) \in \mathbb{Z}[\omega + \omega^{-1}]$, so (ignoring the constant term) $f(x)$ has palindromic coefficients.

• If $f(\omega^j)=a_j$, then $\prod_j(f(x)-a_j)$ vanishes at $\omega^j$ for all $j$, so it's a multiple of the minimal polynomial for $\omega$, so for some $j$, $f(x)-a_j$ is a multiple of the minimal polynomial for $\omega$. I'm not sure where to go from there. – Gerry Myerson Nov 1 '17 at 21:35
• Ah! WLOG assume that the polynomial $f$ has degree $< n$ (otherwise, we can simply reduce it modulo $x^n-1$). Then, this polynomial is "even modulo $n$" in the sense of Desarmenien's above paper. This means that if we write $f$ as $\sum_{i=0}^{n-1} a_i x^i$, then $a_i = a_{\gcd\left(i, n\right)}$ for each $i$. Thus, $f$ is a $\mathbb{Z}$-linear combination of polynomials of the form $\sum_{0\leq i<n;\ \gcd\left(i,n\right) = d} x^i$ for $d \mid n$. By an inclusion-exclusion-style argument, we thus conclude that $f$ is also ... – darij grinberg Nov 1 '17 at 22:08
• ... a $\mathbb{Z}$-linear combination of polynomials of the form $x^{0d} + x^{1d} + x^{2d} + \cdots + x^{n-d}$ for $d \mid n$. So we can WLOG assume that $f$ is one such polynomial; i.e., that we have $f = x^{0d} + x^{1d} + x^{2d} + \cdots + x^{n-d}$ for some $d \mid n$. Fix this $d$. Then, $f\left(\omega^k\right)$ equals $n/d$ if $n \mid kd$, and equals $0$ otherwise. From here, the claim is straightforward. – darij grinberg Nov 1 '17 at 22:09
• By the way, this proves a stronger statement: namely, $f\left(\omega^k\right) \equiv f\left(\omega^{k/p}\right) \mod p^{v_p\left(k\right)}$ for every positive integer $k$ and every prime divisor $p$ of $k$ (where $v_p$ denotes $p$-adic valuation). In other words, $\left(f\left(\omega^1\right), f\left(\omega^2\right), f\left(\omega^3\right), \ldots\right)$ is a ghost-Witt vector over $\mathbb{Z}$. – darij grinberg Nov 1 '17 at 22:15
• Wow, excellent! I think I now follow you argument, and you even characterize all integer polynomials taking integer values at root of unity via a basis. if you feel like making that an answer I will accept it. – user94267 Nov 1 '17 at 22:28