Polynomial expressions of roots of unity with integer norm Say a nonconstant polynomial $p(z)$ is $k$-magical if it satisfies the following properties:


*

*$p$ is of the form $$p(z) = a_{k-1} z^{k-1} + a_{k-2} z^{k-2} + \cdots + a_1 z + 1$$ where each $a_i \in \{0, 1\}$.

*None of the roots of $p$ are roots of unity.

*$|p(\omega)|^2 \in \mathbb{N}$ for all $k$th roots of unity $\omega$.


There is a $7$-magical polynomial: $p(z) = z^3 + z+ 1$. 
Also, a $13$-magical polynomial: $p(z) = z^6 + z^5 + z^2 + 1$.
My question: for which $k$ does a $k$-magical polynomial exist? 
Follow-up: What if we only require $|p(\omega)|^2 \in \mathbb{N}$ when $\omega$ is a primitive root of unity? Then, as Gerry Myerson mentions in the comments below, every even $k$ has a $k$-magical polynomial.
 A: Not a complete answer, but a partial result. Assume that $p\in{\mathbb Z}[X]$ is such that $|p(\omega)|^2=m\in{\mathbb N}$ for some primitive $k$-th root of unity $\omega$. Let $\phi_k$ be the cyclotomic polynomial (irreducible over ${\mathbb Q}$). It is reciprocal, thus the primitive roots $\alpha$ satisfy actually a polynomial identity $R_k(\alpha+\alpha^{-1})=0$ with $R_k\in{\mathbb Z}[X]$ irreducible. By assumption,
$$m=p(\omega)p(\bar\omega)=p(\omega)p(\omega^{-1}).$$
There exists a $q\in{\mathbb Z}[X]$ such that $p(X)p(X^{-1})=q(X+X^{-1})$. Therefore $R_k$ and $q-m$ have a common root $\omega+\omega^{-1}$. Because $R_k$ is irreducible, we see that $R_k$ divides $q-m$. We conclude that actually

$|p(\alpha)|^2$ is constant when $\alpha$ runs over the primitive $k$-th roots.

In particular, $|p(\alpha)|^2$ is an integer for every primitive $k$-th root.
Now, the problem posed in the MO question is to find pairs $(m,S)$ with $m\ge1$ an integer, $S\in{\mathbb Z}[X]$, such that 
$$m+(SR_k)(X+X^{-1})$$ splits as $p(X)p(X^{-1})$ where $p$ has coefficients in $\{0,1\}$.
A: For every prime $k = -1 \mod 4$, and every primitive root $a$ modulo $p$, the polynomials $P(x) = 1 + x^{a^2} + x^{a^4} + ... + x^{a^{k-1}}$ and $Q(x) = 1 + x^a + x^{a^3}+\cdots+ x^{a^{k-2}}$ are magicals 
(of course, reduce the exponents modulo $k$ in order to make the degrees of the polynomials $<k$). 
Indeed, it is easy to see that $\overline{P(\omega)} = Q(\omega)$ (because the conjugation sends $\omega$ to $\omega^{-1}=\omega^{a^{\frac{k-1}{2}}}$).
Every automorphism of the galois group of ${\mathbb Q}(\omega)/{\mathbb Q}$ sends
$\omega$ (a primitive element of the extension) to $w^{a^i}$ for some $i$. 
So, the expression $|P(\omega)|^2=P(\omega)Q(\omega)$ is fixed by the Galois group, hence belongs to $\mathbb Q$.
Therefore, $|P(\omega)|^2\in {\mathbb Q} \cap Z[\omega] = Z$ because $Z$ is integrally closed (a consequence, say, of the symmetric functions theorem). 
Thus $|P(\omega)|^2 \in \mathbb N$ and $|Q(\omega)|^2\in \mathbb N$, as desired.
Next, for every prime $k = 5 \mod 8$, and every primitive root $a$ modulo $p$, the polynomials 
$P_1(x) = 1 + x^{a} + x^{a^5} + x^{a^9} + \cdots$, 
$Q_1(x) = 1 + x^{a^2} + x^{a^{6}} + x^{a^{10}} + \cdots $, 
and
$P_2(x) = 1 + x^{a^3} + x^{a^7} + x^{a^{11}} + \cdots$ 
$Q_2(x) = 1 + x^{a^4} + x^{a^8} + x^{a^{12}} + \cdots $,
are (not checked very carefully) magicals. 
You have to use the pigeon hole principle to show first that $P_1P_2(\omega) = Q_1Q_2(\omega)$ (let me leave this point, this may be wrong for every $p=5\mod 8$, even if it is true for some primes like p=13). 
Once this is done, it is easily seen that the complex conjugation sends 
$P_1(\omega)$ to $P_2(\omega)$, and $Q_1(\omega)$ to $Q_2(\omega)$. The generator $\omega\to \omega^a$ of the cyclic Galois group sends $P_1$ to $Q_1$ and $P_2$ to $Q_2$. Hence $P_1P_2$ and $Q_1Q_2$ are fixed by the Galois group, and the conclusion follows as previously.
These cases cover the given examples.
A: Not an answer, but a formulation of the problem in term of additive number theory (this is probably what the tag of the post suggested).
It is clear that a sufficient condition for $k$ to be "magical" is that there exists a subset $A$ of $\{0,1,2,\ldots, k-1\} \mod k$ such that, the multiset $A - A$ is composed of a certain number of copies of $0$, and of another number of copies of $\{1,2,\ldots,k-1\}$ (this condition is also necessary if $k$ is prime).
In other words, $A$ is a so called "$\lambda$-difference set" of the additive groupe ${\mathbb Z}/k\mathbb Z$ (notice that I have in fact shown in the previous answer that $\lambda$-difference sets exist for all primes $k=-1\mod 4$ (Paley difference set).
Notice also that this condition is realized if $A$ is a perfect difference set modulo $k$, and these are known to exist whenever $k$ is of the form $r^2+r+1$ and $r$ is a power of some prime $p$.
But this condition is not necessary if $k$ is not prime : in this case, it is sufficient to replace the copies of $\{1,2,\ldots,k-1\}$ (related to the non-zero $x$ powers of the polynomial $m(1+x+x^2\cdots+x^{k-1})$, $m\in \mathbb N$)) by a subset comming from the non-zero $x$ powers a polynomial of the form $R(x)\Phi(x)$, where $\Phi$ is the kth cyclotomic polynomial, and $R$ is a polynomial with integer coefficients and of degree at most $k-1-\deg(\Phi)$. 
