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.

  • 3
    $\begingroup$ If $k$ is even, then $z^{k/2}+z+1$ is "magical". $\endgroup$ – Gerry Myerson Jan 21 '15 at 3:31
  • $\begingroup$ This works with $z = \exp(2\pi i j/k)$ when $j$ is odd, but if $j$ is even, this polynomial isn't magical. I have clarified in the problem statement my intention that a $k$-magical polynomial evaluated at any $k$th root of unity should have integral norm. $\endgroup$ – user61921 Jan 21 '15 at 3:51
  • 2
    $\begingroup$ Isn't $p(x)=x$ a "magical" polynomial for all $k>1$? It is non-contant, has coefficients in $\{0,1\}$ and has degree $<k$, its only root is $0$ which is not a root of unity, and $|p(\omega)|^2=1\in \mathbb{N}$ for all $k$th roots of unity $\omega$. This last fact comes from noting that $|x|^2=1$ for any complex number on the unit circle. $\endgroup$ – Pace Nielsen Jan 21 '15 at 4:02
  • $\begingroup$ You are correct, and I forgot to exclude this case. I am interested in finding "nontrivial" examples of magical polynomials, and I suppose the identity polynomial should count as "trivial." $\endgroup$ – user61921 Jan 21 '15 at 4:05
  • 2
    $\begingroup$ @Gerry Myerson. I disagree. Say $k=2p$, so that your polynomial is $z^p+z+1$. The $k$th roots split into two subsets, those such that $\omega^p+1=0$ and those such that $\omega^p=1$. The first case is OK because $|p(\omega)|^2=|\omega|^2=1$. But the second case yields $|p(\omega)|^2=|\omega+2|^2=5+2(\omega+\omega^{-1})$, which is not an integer in general. $\endgroup$ – Denis Serre Jan 21 '15 at 10:10

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\}$.


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.


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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy