Polynomial ring $\mathbb{Z}[X]/(X^{2^k} + 1)$ has property $X^{2^k} = −1$?

Question

I'm a BS in CS and reading a paper on homomorphic cryptography, "Secure Searching of Biomarkers Using Hybrid Homomorphic Encryption Scheme." (https://eprint.iacr.org/2017/294.pdf)

I have difficulty understanding the following paragraph from the paper.

Since we use the cyclotomic polynomial $\phi(X) = X^N +1$ of power-of-two degree, the polynomial ring $\mathcal{R}$ has the property $X^N = −1$. Thus, for any tag $d$, the constant term of the polynomial $\mathsf{DB}(X) \cdot X^{−d}$ is $\alpha_i$ if there is some index $i$ satisfying $d = d_i$, otherwise zero.

Here, the polynomial ring $\mathcal{R}$ is defined as in advance: $$ \mathcal{R} := \mathbb{Z}[X]/\phi(X) = \mathbb{Z}[X]/\left(X^{N} + 1\right) , $$ where $N = M/2$ is a power of two.

Question: What precisely does it mean that "the polynomial ring $\mathcal{R}$ has the property $X^N = −1$?"

I have tried to do some research by myself, and understand only the basic concepts (say, definitions) of polynomial ring, quotient ring and cyclotomic polynomial.

Answer 1

An element in $Z[x]$ is a polynomial with coefficients in $Z$. $R$ inherits this, but dividing out by an ideal has the effect of turning all members of that ideal into $0$. In our case, that would specifically mean that $x^n + 1 = 0$ as elements of $R$.

To be more correct, we should write $x^n + 1 + (x^n + 1) = 0 + (x^n + 1)$, in other words, the set you get from taking the ideal $(x^n + 1)$ and adding $x^n + 1$ to all of its elements is the same as the set you get from taking that same ideal and adding $0$ to all of the elements. Often, though, this notation is skipped to make writing and reading easier.

We also have that $x^n + (x^n + 1) = -1 + (x^n + 1)$. In other words, as far as $R$ is concerned, there is no way to differentiate between $x^n$ and $-1$, which we symbolise by setting a "$=$" between the two. When I say that there is no way to differentiate between the two, this extends to $x^{n+1}$ being the same as $-x$, and $x^n + 3x^2$ being the same as $3x^2 - 1$.

Side note: $R$ is not a polynomial ring, precicely because it has the property $x^n = -1$.

Answer 2

This is not a genuine polynomial ring, rather the quotient of the polynomial ring $\mathbb{Z}[x]$ by the ideal generated by $\varphi(x)=x^{n}+1$.

In other words, you are considering the remainder classes modulo this polynomial. Of course, the remainder class of $\varphi(x)$ itself is zero, so in $R$ you have the relation $x^{n}+1=0$, that is $x^{n}=-1$.

You can find all this (and much more) in any good book on Algebra or Ring Theory. For instance, you can have a look at Chapter 2 of Rotman, Advanced Modern Algebra.