# Two families of circulant nut graphs

Ivan Damnjanović
University of Niš, Faculty of Electronic Engineering
<EMAIL_ADDRESS>
Diffine LLC
<EMAIL_ADDRESS>The author is supported by Diffine LLC.

###### Abstract

A circulant nut graph is a non-trivial simple graph whose adjacency matrix is
a circulant matrix of nullity one such that its non-zero null space vectors
have no zero elements. The study of circulant nut graphs was originally
initiated by Bašić et al. [Art Discrete Appl. Math. 5(2) (2021) #P2.01], where
a conjecture was made regarding the existence of all the possible pairs
$(n,d)$ for which there exists a $d$-regular circulant nut graph of order $n$.
Later on, it was proved by Damnjanović and Stevanović [Linear Algebra Appl.
633 (2022) 127–151] that for each odd $t\geq 3$ such that $t\not\equiv_{10}1$
and $t\not\equiv_{18}15$, the $4t$-regular circulant graph of order $n$ with
the generator set $\\{1,2,3,\ldots,2t+1\\}\setminus\\{t\\})$ must necessarily
be a nut graph for each even $n\geq 4t+4$. In this paper, we extend these
results by constructing two families of circulant nut graphs. The first family
comprises the $4t$-regular circulant graphs of order $n$ which correspond to
the generator sets
$\\{1,2,\ldots,t-1\\}\cup\left\\{\frac{n}{4},\frac{n}{4}+1\right\\}\cup\left\\{\frac{n}{2}-(t-1),\ldots,\frac{n}{2}-2,\frac{n}{2}-1\right\\}$,
for each odd $t\in\mathbb{N}$ and $n\geq 4t+4$ divisible by four. The second
family consists of the $4t$-regular circulant graphs of order $n$ which
correspond to the generator sets
$\\{1,2,\ldots,t-1\\}\cup\left\\{\frac{n+2}{4},\frac{n+6}{4}\right\\}\cup\left\\{\frac{n}{2}-(t-1),\ldots,\frac{n}{2}-2,\frac{n}{2}-1\right\\}$,
for each $t\in\mathbb{N}$ and $n\geq 4t+6$ such that $n\equiv_{4}2$. We prove
that all of the graphs which belong to these families are indeed nut graphs,
thereby fully resolving the $4t$-regular circulant nut graph order–degree
existence problem whenever $t$ is odd and partially solving this problem for
even values of $t$ as well.

Mathematics Subject Classification: 05C50, 12D05, 13P05, 11C08.
Keywords: Circulant graphs; Nut graphs; Graph spectra; Graph eigenvalues;
Cyclotomic polynomials.

##  1 Introduction

In this paper we will consider all graphs to be undirected, finite, simple and
non-null. Thus, every graph will have at least one vertex and there shall be
no loops or multiple edges. Also, for convenience, we will take that each
graph of order $n$ has the vertex set $\\{0,1,2,\ldots,n-1\\}$.

A graph $G$ is considered to be a circulant graph if its adjacency matrix $A$
has the form

$A=\begin{bmatrix}a_{0}&a_{1}&a_{2}&\cdots&a_{n-1}\\\
a_{n-1}&a_{0}&a_{1}&\cdots&a_{n-2}\\\ a_{n-2}&a_{n-1}&a_{0}&\cdots&a_{n-3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
a_{1}&a_{2}&a_{3}&\dots&a_{0}\end{bmatrix}.$

Here, we clearly have $a_{0}=0$, as well as $a_{j}=a_{n-j}$ for all
$j=\overline{1,n}$. A concise way of describing a circulant graph is by taking
into consideration the set of all the values $1\leq j\leq\frac{n}{2}$ such
that $a_{j}=a_{n-j}=1$. We shall refer to this set as the generator set of a
circulant graph and we will use $\mathrm{Circ}(n,S)$ to denote the circulant
graph of order $n$ whose generator set is $S$.

A nut graph is a non-trivial graph whose adjacency matrix has nullity one and
is such that its non-zero null space vectors have no zero elements, as first
described by Sciriha in [1]. Bearing this in mind, a circulant nut graph is
simply a nut graph whose adjacency matrix additionally represents a circulant
matrix. Bašić et al. [2] initiated the study of these graphs by providing
several results, alongside the following two conjectures.

######  Conjecture 1 (Bašić et al. [2]).

For every even $n,\,n\geq 16$, there exists a circulant nut graph
$\mathrm{Circ}(n,\\{s_{1},s_{2},s_{3},s_{4},s_{5},s_{6}\\})$ of degree $12$.

######  Conjecture 2 (Bašić et al. [2]).

For every $d$, where $d\equiv_{4}0$, and for every even $n,\,n\geq d+4$, there
exists a circulant nut graph
$\mathrm{Circ}(n,\\{a_{1},a_{2},a_{3},\ldots,a_{\frac{d}{2}}\\})$ of degree
$d$.

Later on, Damnjanović and Stevanović [3, Proposition 8] proved Conjecture 1 by
showing that $\mathrm{Circ}(n,\\{1,2,4,5,6,7\\})$ is a $12$-regular nut graph
for each even $n\geq 16$. In fact, it was shown that for infinitely many odd
values of $t$ it is possible to construct similar families of $4t$-regular
circulant nut graphs, as demonstrated in the next theorem.

######  Theorem 3 (Damnjanović and Stevanović [3]).

For each odd $t\geq 3$ such that $t\not\equiv_{10}1$ and $t\not\equiv_{18}15$,
the circulant graph
$\operatorname{Circ}(n,\\{1,2,3,\ldots,2t+1\\}\setminus\\{t\\})$ is a nut
graph for each even $n\geq 4t+4$.

The primary motivation behind this paper is to improve the currently existing
results regarding the circulant nut graph order–degree existence problem. In
other words, the goal is to answer the question whether there exists a
$d$-regular circulant nut graph of order $n$, for any such pair
$(n,d)\in\mathbb{N}^{2}$ of integers. As shown by Damnjanović and Stevanović
[3, Lemma 6], the order of each circulant nut graph must be even, while its
degree must be divisible by four. It is clear that a $4t$-regular circulant
nut graph cannot have an order of $4t+2$, since the adjacency matrix of such a
graph would obviously have a nullity greater than one, due to the fact that
its first $\frac{n}{2}$ rows would match its following $\frac{n}{2}$ rows,
respectively.

Furthermore, if $t$ is even, then the order of a $4t$-regular circulant nut
graph cannot be below $4t+6$, as demonstrated by Damnjanović and Stevanović
[3, Lemma 18]. Bearing this in mind, we deduct that for a given
$t\in\mathbb{N}$, all the $4t$-regular circulant nut graphs must have an even
order $n$ such that

  * •

$n\geq 4t+4$ if $2\nmid t$;

  * •

$n\geq 4t+6$ if $2\mid t$.

In this paper, we present the following two families of circulant graphs:

$\displaystyle\mathcal{D}^{\prime}_{t,n}$
$\displaystyle=\operatorname{Circ}(n,\mathcal{S}^{\prime}_{t,n}),\quad$
$\displaystyle\mbox{for each $2\nmid t$ and $4\mid n$ such that $n\geq
4t+4$},$ $\displaystyle\mathcal{D}^{\prime\prime}_{t,n}$
$\displaystyle=\operatorname{Circ}(n,\mathcal{S}^{\prime\prime}_{t,n}),\quad$
$\displaystyle\mbox{for each $t\in\mathbb{N}$ and $n\equiv_{4}2$ such that
$n\geq 4t+6$},$

where

$\displaystyle\mathcal{S}^{\prime}_{t,n}$
$\displaystyle=\\{1,2,\ldots,t-1\\}\cup\left\\{\frac{n}{4},\frac{n}{4}+1\right\\}\cup\left\\{\frac{n}{2}-(t-1),\ldots,\frac{n}{2}-2,\frac{n}{2}-1\right\\},$
$\displaystyle\mathcal{S}^{\prime\prime}_{t,n}$
$\displaystyle=\\{1,2,\ldots,t-1\\}\cup\left\\{\frac{n+2}{4},\frac{n+6}{4}\right\\}\cup\left\\{\frac{n}{2}-(t-1),\ldots,\frac{n}{2}-2,\frac{n}{2}-1\right\\}.$

Subsequently, we prove that all of the graphs which belong to these families
are nut graphs, thereby showing that for each odd $t$, there does exist a
$4t$-regular circulant nut graph of order $n$, for any even $n\geq 4t+4$. This
observation fully resolves the circulant nut graph order–degree existence
problem for $4t$-regular graphs whenever $t$ is odd.

When it comes to the even values of $t$, we get a partial resolution of the
existence problem, given the fact that the said constructions do cover the
case when $n\equiv_{4}2$. However, the case when $n$ is divisible by four is
not yet resolved, hence these graphs remain to be further inspected in the
future.

The remainder of this paper is structured as follows. In Section 2 we preview
certain theoretical facts regarding the circulant matrices, circulant nut
graphs and cyclotomic polynomials which are required in order to successfully
prove the two main theorems. Subsequently, Section 3 displays a full
mathematical proof of the fact that each $\mathcal{D}^{\prime}_{t,n}$
circulant graph is indeed a nut graph. Afterwards, Section 4 uses a similar
strategy in order to prove that every $\mathcal{D}^{\prime\prime}_{t,n}$ graph
must be a circulant nut graph as well. Finally, Section 5 provides a brief
conclusion to all the obtained results and discloses a new conjecture to be
solved later on.

##  2 Preliminaries

First of all, it is worth pointing out that the generator sets
$\mathcal{S}^{\prime}_{t,n}$ and $\mathcal{S}^{\prime\prime}_{t,n}$ are always
well defined. It is straightforward to check that

$1<2<\cdots<t-1<\frac{n}{4}<\frac{n}{4}+1<\frac{n}{2}-(t-1)<\cdots<\frac{n}{2}-2<\frac{n}{2}-1$

for each odd $t\geq 3$ and $n\geq 4t+4$ that is divisible by four. Similarly,
we have

$1<2<\cdots<t-1<\frac{n+2}{4}<\frac{n+6}{4}<\frac{n}{2}-(t-1)<\cdots<\frac{n}{2}-2<\frac{n}{2}-1$

for every $t\geq 2$ and $n\geq 4t+6$ such that $n\equiv_{4}2$. Finally, for
$t=1$ we have that

$1<\dfrac{n}{4}<\dfrac{n}{4}+1\leq\dfrac{n}{2}-1$

for every $n\geq 4t+4$ divisible by four, as well as

$1<\dfrac{n+2}{4}<\dfrac{n+6}{4}\leq\dfrac{n}{2}-1$

for each $n\geq 4t+6$ such that $n\equiv_{4}2$.

It is known from elementary linear algebra theory (see, for example, [4,
Section 3.1]) that the circulant matrix

$A=\begin{bmatrix}a_{0}&a_{1}&a_{2}&\cdots&a_{n-1}\\\
a_{n-1}&a_{0}&a_{1}&\cdots&a_{n-2}\\\ a_{n-2}&a_{n-1}&a_{0}&\cdots&a_{n-3}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
a_{1}&a_{2}&a_{3}&\dots&a_{0}\end{bmatrix}$

must have the eigenvalues

$P(1),P(\omega),P(\omega^{2}),\ldots,P(\omega^{n-1}),$

where $\omega=e^{i\frac{2\pi}{n}}$ is an $n$-th root of unity, and

$P(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{n-1}x^{n-1}.$

Starting from the aforementioned result, Damnjanović and Stevanović [3] have
managed to give the necessary and sufficient conditions for a circulant graph
to be a nut graph in the form of the following lemma.

######  Lemma 4 (Damnjanović and Stevanović [3]).

Let $G=\operatorname{Circ}(n,S)$ where $n\geq 2$. The graph $G$ is a nut graph
if and only if all of the following conditions hold:

  * •

$2\mid n$;

  * •

$S$ consists of $t$ odd and $t$ even integers from
$\left\\{1,2,3,\ldots,\frac{n}{2}-1\right\\}$, for some $t\geq 1$;

  * •

$P(\omega^{j})\neq 0$ for each
$j\in\left\\{1,2,3,\ldots,\frac{n}{2}-1\right\\}$.

All of the graphs $\mathcal{D}^{\prime}_{t,n}$ and
$\mathcal{D}^{\prime\prime}_{t,n}$ clearly satisfy the first condition from
Lemma 4. Besides that, it is easy to show that they necessarily satisfy the
second condition as well. For $\mathcal{D}^{\prime}_{t,n}$, it is enough to
point out that both $\\{1,2,\ldots,t-1\\}$ and
$\left\\{\frac{n}{2}-(t-1),\ldots,\frac{n}{2}-2,\frac{n}{2}-1\right\\}$
contain an even number of consecutive integers, due to the fact that $t-1$ is
even. Since $\frac{n}{4}$ and $\frac{n}{4}+1$ are surely of different
parities, it follows that $\mathcal{S}^{\prime}_{t,n}$ does contain equally
many odd and even integers. For $\mathcal{D}^{\prime\prime}_{t,n}$, it is
essential to notice that $j$ and $\frac{n}{2}-j$ must be of different
parities, for each $j=\overline{1,t-1}$, due to the fact that $\frac{n}{2}$ is
odd. Furthermore, $\frac{n+2}{4}$ and $\frac{n+6}{4}$ are certainly of
different parities, hence we obtain that $\mathcal{S}^{\prime\prime}_{t,n}$
contains equally many odd and even integers, too.

Taking into consideration Lemma 4, it becomes apparent that in order to show
that each graph $\mathcal{D}^{\prime}_{t,n}$ and
$\mathcal{D}^{\prime\prime}_{t,n}$ is a nut graph, it is sufficient to prove
that it satisfies the third condition given in the lemma. In other words, it
is enough to demonstrate that, for these graphs, the polynomial
$P(x)\in\mathbb{Z}[x]$ has no $n$-th roots of unity among its roots, except
potentially $-1$ or $1$.

It is clear that $\omega^{n-j}=\dfrac{1}{\omega^{j}}$ for each
$j=\overline{1,n-1}$. Bearing this in mind, we quickly obtain that

$P(\omega^{j})=\left(\omega^{js_{0}}+\frac{1}{\omega^{js_{0}}}\right)+\left(\omega^{js_{1}}+\frac{1}{\omega^{js_{1}}}\right)+\cdots+\left(\omega^{js_{k-1}}+\frac{1}{\omega^{js_{k-1}}}\right)$
(1)

for an arbitrary circulant graph $G=\mathrm{Circ}(n,S)$, where
$S=\\{s_{0},s_{1},s_{2},\ldots,s_{k-1}\\}$, provided all the generator set
elements are lower than $\frac{n}{2}$. Formula (1) will be heavily used
throughout Sections 3 and 4 while proving the two main theorems of the paper.

Last but not least, it is crucial to point out that the cyclotomic polynomials
shall play a key role in demonstrating whether or not certain polynomials of
interest contain the given roots of unity among their roots. The cyclotomic
polynomial $\Phi_{b}(x)$ can be defined for each $b\in\mathbb{N}$ via

$\Phi_{b}(x)=\prod_{\zeta}(x-\zeta),$

where $\zeta$ ranges over the primitive $b$-th roots of unity. It is known
that these polynomials have integer coefficients and that they are all
irreducible in $\mathbb{Q}[x]$ (see, for example, [5]). Hence, an arbitrary
polynomial in $\mathbb{Q}[x]$ has a primitive $b$-th root of unity among its
roots if and only if it is divisible by $\Phi_{b}(x)$.

While inspecting whether certain integer polynomials are divisible by
cyclotomic polynomials, we will strongly rely on the following theorem on the
divisibility of lacunary polynomials by cyclotomic polynomials.

######  Theorem 5 (Filaseta and Schinzel [6]).

Let $P(x)\in\mathbb{Z}[x]$ have $N$ nonzero terms and let $\Phi_{b}(x)\mid
P(x)$. Suppose that $p_{1},p_{2},\dots,p_{k}$ are distinct primes such that

$\sum_{j=1}^{k}(p_{j}-2)>N-2.$

Let $e_{j}$ be the largest exponent such that $p_{j}^{e_{j}}\mid b$. Then for
at least one $j$, $1\leq j\leq k$, we have that $\Phi_{b^{\prime}}(x)\mid
P(x)$, where $b^{\prime}=\dfrac{b}{p_{j}^{e_{j}}}$.

##  3 $\mathcal{D}^{\prime}_{t,n}$ family of circulant graphs

In this section, we will formulate and provide a full mathematical proof of
the first of the two central theorems given in the paper.

######  Theorem 6.

For each odd $t\in\mathbb{N}$ and $n\geq 4t+4$ such that $4\mid n$, the
circulant graph $\mathcal{D}^{\prime}_{t,n}$ must be a $4t$-regular nut graph
of order $n$.

In order to make the proof more concise, we will need a number of auxiliary
lemmas. To start with, let $Q_{t}(x)\in\mathbb{Z}[x]$ and
$R_{t}(x)\in\mathbb{Z}[x]$ be the following two integer polynomials

$\displaystyle Q_{t}(x)$
$\displaystyle=2x^{2t-1}+x^{t+1}-x^{t}+x^{t-1}-x^{t-2}-2,$ $\displaystyle
R_{t}(x)$ $\displaystyle=2x^{2t-1}-x^{t+1}-3x^{t}+3x^{t-1}+x^{t-2}-2,$

for each odd $t\geq 3$. It is clear that all of these polynomials must have
exactly six non-zero terms, due to the fact that

$0<t-2<t-1<t<t+1<2t-1$

for each odd $t\geq 3$. Now, if we let

$L_{t}=\\{0,t-2,t-1,t,t+1,2t-1\\}$

be the set consisting of the powers of these six terms, then it can be shown
that this set has one valuable property, as described in the following lemma.

######  Lemma 7.

For each odd $t\geq 3$ and each prime number $p\geq 5$, the set $L_{t}$
contains an element whose remainder modulo $p$ is unique within the set.

###### Proof.

The four integers $t-2,t-1,t,t+1$ are consecutive, hence it is clear that they
all have mutually distinct remainders modulo $p$. Regardless of what their
remainders modulo $p$ are, at least two of these integers must have a
remainder that is different from the remainders of both $0$ and $2t-1$. ∎

Lemma 7 proves to be useful while demonstrating one key property of the
$Q_{t}(x)$ and $R_{t}(x)$ polynomials regarding their division by cyclotomic
polynomials. This is shown in the next lemma.

######  Lemma 8.

For any odd $t\geq 3$, neither $Q_{t}(x)$ nor $R_{t}(x)$ can be divisible by a
cyclotomic polynomial $\Phi_{b}(x)$ such that $p^{2}\mid b$ for some prime
number $p$.

###### Proof.

Let $b\in\mathbb{N}$ be such that $p^{2}\mid b$ for some prime number $p$. In
this case, $\frac{b}{p}$ is a positive integer divisible by $p$, hence we get
that $\Phi_{b}(x)=\Phi_{\frac{b}{p}}(x^{p})$ (see, for example, [7, p. 160]).

Now, suppose that $\Phi_{b}(x)\mid Q_{t}(x)$ for some odd integer $t\geq 3$.
It follows that $Q_{t}(x)=V(x)\Phi_{b}(x)$ for some polynomial
$V(x)\in\mathbb{Q}[x]$. Let $Q_{t}^{(j)}(x)$ be the polynomial composed of all
the terms of $Q_{t}(x)$ whose powers are congruent to $j$ modulo $p$, for each
$j=\overline{0,p-1}$. Similarly, let $V^{(j)}(x)$ be the polynomial composed
of all the terms of $V(x)$ whose powers are congruent to $j$ modulo $p$, for
each $j=\overline{0,p-1}$. Given the fact that the powers of all the terms of
$\Phi_{b}(x)$ are divisible by $p$, it swiftly follows that

$Q_{t}^{(j)}(x)=V^{(j)}(x)\Phi_{b}(x)$

must hold for all the $j=\overline{0,p-1}$. In other words, we necessarily
have

$\Phi_{b}(x)\mid Q_{t}^{(j)}(x)$

for all the $j=\overline{0,p-1}$. The same reasoning and notation can be
applied in the case that we suppose that $\Phi_{b}(x)\mid R_{t}(x)$ is true
for some odd $t\geq 3$. We will finalize the proof of the lemma by taking into
consideration three separate cases depending on the value of the prime number
$p$.

_Case $p\geq 5$_. In this case, Lemma 7 dictates that the set $L_{t}$ must
contain an element whose remainder modulo $p$ is unique within that set. In
other words, there exists a $j,\,0\leq j\leq p-1$ such that both
$Q_{t}^{(j)}(x)$ and $R_{t}^{(j)}(x)$ consist of exactly one non-zero term,
i.e. have the form $c\,x^{a}$ for some $c\in\mathbb{Z}\setminus\\{0\\}$ and
$a\in\mathbb{N}_{0}$. If we suppose that either $\Phi_{b}(x)\mid Q_{t}(x)$ or
$\Phi_{b}(x)\mid R_{t}(x)$, this implies that $\Phi_{b}(x)$ must necessarily
divide a polynomial with the aforementioned form $c\,x^{a}$, which is clearly
impossible.

_Case $p=3$_. This case can be quickly resolved by taking into consideration
the modular values given in Table 1. We divide the case into three subcases
depending on the value of $t\bmod 3$.

| $t\equiv_{3}0$ | $t\equiv_{3}1$ | $t\equiv_{3}2$
---|---|---|---
$0\bmod 3$ | $0$ | $0$ | $0$
$(t-2)\bmod 3$ | $1$ | $2$ | $0$
$(t-1)\bmod 3$ | $2$ | $0$ | $1$
$t\bmod 3$ | $0$ | $1$ | $2$
$(t+1)\bmod 3$ | $1$ | $2$ | $0$
$(2t-1)\bmod 3$ | $2$ | $1$ | $0$
Table 1: The elements of the set $L_{t}$ modulo $3$.

_Subcase $t\equiv_{3}0$_. If we suppose that $\Phi_{b}(x)\mid Q_{t}(x)$, we
get $\Phi_{b}(x)\mid x^{t+1}-x^{t-2}$. Similarly, $\Phi_{b}(x)\mid R_{t}(x)$
would imply $\Phi_{b}(x)\mid-x^{t+1}+x^{t-2}$. Either way, we obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{t+1}-x^{t-2}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{t-2}(x^{3}-1)$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{3}-1,$

which is not possible.

_Subcase $t\equiv_{3}1$_. Regardless of whether we suppose that
$\Phi_{b}(x)\mid Q_{t}(x)$ holds or $\Phi_{b}(x)\mid R_{t}(x)$, we obtain that
$\Phi_{b}(x)\mid x^{t+1}-x^{t-2}$ must be true, which is impossible as we have
already demonstrated in the previous subcase.

_Subcase $t\equiv_{3}2$_. Bearing in mind the modular values given in Table 1,
we conclude that $\Phi_{b}(x)\mid Q_{t}(x)$ or $\Phi_{b}(x)\mid R_{t}(x)$
would surely imply that $\Phi_{b}(x)\mid y^{t}$, which is not possible.

_Case $p=2$_. In this case, we have that the integers $t-2,t,2t-1$ are odd,
while $0,t-1,t+1$ are even. We will resolve this case separately for
$Q_{t}(x)$ and $R_{t}(x)$, thus yielding two subcases.

_Subcase $\Phi_{b}(x)\mid Q_{t}(x)$_. Suppose that $\Phi_{b}(x)\mid Q_{t}(x)$.
We now get

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}-x^{t}-x^{t-2},$ (2)
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{t+1}+x^{t-1}-2.$ (3)

If we take into consideration that
$2x^{2t-1}-x^{t}-x^{t-2}=x^{t-2}(2x^{t+1}-x^{2}-1)$, Eq. (2) helps us obtain

$\Phi_{b}(x)\mid 2x^{t+1}-x^{2}-1.$ (4)

By subtracting the right-hand sides of Eqs. (3) and (4), we further conclude
that

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{t+1}-x^{t-1}-x^{2}+1$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(x^{t-1}-1)(x^{2}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{t-1}-1.$ (5)

Now, if we subtract the right-hand sides of Eqs. (3) and (5), we get

$\Phi_{b}(x)\mid x^{t+1}-1,$

which directly implies

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid(x^{t+1}-1)-(x^{t-1}-1)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{t+1}-x^{t-1}$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{t-1}(x^{2}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2}-1,$

which is not possible. Hence, $\Phi_{b}(x)\mid Q_{t}(x)$ cannot hold, as
desired.

_Subcase $\Phi_{b}(x)\mid R_{t}(x)$_. If we suppose that $\Phi_{b}(x)\mid
R_{t}(x)$, it follows that

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}-3x^{t}+x^{t-2},$ (6)
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{t+1}+3x^{t-1}-2.$ (7)

Given the fact that $2x^{2t-1}-3x^{t}+x^{t-2}=x^{t-2}(2x^{t+1}-3x^{2}+1)$, Eq.
(6) yields

$\Phi_{b}(x)\mid 2x^{t+1}-3x^{2}+1.$ (8)

Now, by subtracting the right-hand sides of Eqs. (7) and (8), we further
obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 3x^{t+1}-3x^{t-1}-3x^{2}+3$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
3(x^{t-1}-1)(x^{2}-1)$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{t-1}-1.$ (9)

If we take the right-hand side of Eq. (9), multiply it by two, then subtract
it from the right-hand side of Eq. (7), we will get another polynomial that is
divisible by $\Phi_{b}(x)$. In other words, we have

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(-x^{t+1}+3x^{t-1}-2)-2(x^{t-1}-1)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x^{t+1}+x^{t-1}$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{t-1}(1-x^{2})$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
1-x^{2},$

which is not possible. Thus, $\Phi_{b}(x)\mid R_{t}(x)$ cannot be true. ∎

Lemma 8 tells us that the only cyclotomic polynomials $\Phi_{b}(x)$ that could
divide either $Q_{t}(x)$ or $R_{t}(x)$ are those where $b\in\mathbb{N}$ is a
square-free integer. In fact, for any odd $t\geq 3$, the only cyclotomic
polynomials that divide these polynomials are $\Phi_{1}(b)$ and $\Phi_{2}(b)$.
This observation will prove to be of the utmost importance while formulating
the complete proof of Theorem 6 later on. However, in order to prove this
statement, we shall need two more additional lemmas. We begin with the next
one.

######  Lemma 9.

For each odd $t\geq 3$ and each prime number $p\geq 7$, neither $Q_{t}(x)$ nor
$R_{t}(x)$ can be divisible by the cyclotomic polynomial $\Phi_{p}(x)$ or the
cyclotomic polynomial $\Phi_{2p}(x)$.

###### Proof.

First of all, it is important to notice that for all prime numbers $p\geq 7$
we have

$\displaystyle\Phi_{p}(x)$ $\displaystyle=\sum_{j=0}^{p-1}x^{j},$
$\displaystyle\Phi_{2p}(x)$ $\displaystyle=\sum_{j=0}^{p-1}(-1)^{j}x^{j}.$

Here, it is clear that $\deg\Phi_{p}=\deg\Phi_{2p}=p-1$. We will finish the
proof of the lemma by splitting the problem to two separate cases depending on
whether we are dealing with $\Phi_{p}(x)$ or $\Phi_{2p}(x)$.

_Case $\Phi_{p}(x)$_. Let $Q_{t}^{\bmod p}(x)$ and $R_{t}^{\bmod p}(x)$ be the
following two polynomials:

$\displaystyle Q_{t}^{\bmod p}(x)$ $\displaystyle=2x^{(2t-1)\bmod
p}+x^{(t+1)\bmod p}-x^{t\bmod p}+x^{(t-1)\bmod p}-x^{(t-2)\bmod p}-2,$
$\displaystyle R_{t}^{\bmod p}(x)$ $\displaystyle=2x^{(2t-1)\bmod
p}-x^{(t+1)\bmod p}-3x^{t\bmod p}+3x^{(t-1)\bmod p}+x^{(t-2)\bmod p}-2.$

Suppose that $\Phi_{p}(x)\mid Q_{t}(x)$. In this case, it is clear that
$\Phi_{p}(x)\mid Q_{t}^{\bmod p}(x)$ must hold, too. Given the fact that $\deg
Q_{t}^{\bmod p}\leq p-1=\deg\Phi_{p}$, we further get two possibilities:

  * •

$Q_{t}^{\bmod p}(x)\equiv 0$;

  * •

$Q_{t}^{\bmod p}(x)=c\,\Phi_{p}(x)$ for some $c\in\mathbb{Q}\setminus\\{0\\}$.

By virtue of Lemma 7, there must exist a non-zero term in $Q_{t}(x)$ whose
power has a unique remainder modulo $p$. This directly implies that
$Q_{t}^{\bmod p}(x)\equiv 0$ cannot hold. On the other hand, $Q_{t}^{\bmod
p}(x)=c\,\Phi_{p}(x)$ implies that $Q_{t}^{\bmod p}(x)$ and $\Phi_{p}(x)$ must
have the same number of non-zero terms, i.e. $Q_{t}^{\bmod p}(x)$ needs to
have exactly $p$ non-zero terms. This is clearly impossible due to the fact
that $Q_{t}^{\bmod p}(x)$ has at most six non-zero terms. We conclude that
$\Phi_{p}(x)\mid Q_{t}(x)$ cannot be true.

The proof of $\Phi_{p}(x)\nmid R_{t}(x)$ is completely analogous to the
previously described proof of $\Phi_{p}(x)\nmid Q_{t}(x)$. Thus, it will be
left out.

_Case $\Phi_{2p}(x)$_. Let $\hat{Q}_{t}^{\bmod p}(x)$ and $\hat{R}_{t}^{\bmod
p}(x)$ be the following two polynomials:

$\displaystyle\hat{Q}_{t}^{\bmod p}(x)=2$
$\displaystyle(-1)^{\lfloor\frac{2t-1}{p}\rfloor}x^{(2t-1)\bmod
p}+(-1)^{\lfloor\frac{t+1}{p}\rfloor}x^{(t+1)\bmod
p}-(-1)^{\lfloor\frac{t}{p}\rfloor}x^{t\bmod p}$
$\displaystyle\qquad+(-1)^{\lfloor\frac{t-1}{p}\rfloor}x^{(t-1)\bmod
p}-(-1)^{\lfloor\frac{t-2}{p}\rfloor}x^{(t-2)\bmod p}-2,$
$\displaystyle\hat{R}_{t}^{\bmod p}(x)=2$
$\displaystyle(-1)^{\lfloor\frac{2t-1}{p}\rfloor}x^{(2t-1)\bmod
p}-(-1)^{\lfloor\frac{t+1}{p}\rfloor}x^{(t+1)\bmod
p}-3(-1)^{\lfloor\frac{t}{p}\rfloor}x^{t\bmod p}$
$\displaystyle\qquad+3(-1)^{\lfloor\frac{t-1}{p}\rfloor}x^{(t-1)\bmod
p}+(-1)^{\lfloor\frac{t-2}{p}\rfloor}x^{(t-2)\bmod p}-2.$

Since each primitive $2p$-th root of unity gives $-1$ when raised to the power
of $p$, it becomes evident that $\Phi_{2p}(x)\mid Q_{t}(x)$ is equivalent to
$\Phi_{2p}(x)\mid\hat{Q}_{t}^{\bmod p}(x)$. Likewise, $\Phi_{2p}(x)\mid
R_{t}(x)$ will hold if and only if $\Phi_{2p}(x)\mid\hat{R}_{t}^{\bmod p}(x)$
does, too.

Now, suppose that $\Phi_{2p}(x)\mid Q_{t}(x)$. In this case we obtain
$\Phi_{2p}\mid\hat{Q}_{t}^{\bmod p}(x)$, where $\deg\hat{Q}_{t}^{\bmod p}\leq
p-1=\deg\Phi_{2p}$. Like in the previous case, we get two possible options:

  * •

$\hat{Q}_{t}^{\bmod p}(x)\equiv 0$;

  * •

$\hat{Q}_{t}^{\bmod p}(x)=c\,\Phi_{2p}(x)$ for some
$c\in\mathbb{Q}\setminus\\{0\\}$.

Lemma 7 dictates that there must exist a non-zero term in $Q_{t}(x)$ whose
power has a unique remainder modulo $p$, which means that it is impossible for
$\hat{Q}_{t}^{\bmod p}(x)\equiv 0$ to be true. On the other hand, from
$\hat{Q}_{t}^{\bmod p}(x)=c\,\Phi_{2p}(x)$ we get that $\hat{Q}_{t}^{\bmod
p}(x)$ must have exactly $p$ non-zero terms. However, this is not possible
since it is clear that this polynomial cannot have more than six non-zero
terms. It swiftly follows that $\Phi_{2p}(x)\nmid Q_{t}(x)$.

The proof of $\Phi_{2p}(x)\nmid R_{t}(x)$ is entirely analogous to the
elaborated proof of $\Phi_{2p}(x)\nmid Q_{t}(x)$. For this reason, we choose
to leave it out. ∎

As the final piece of the puzzle, we will need to show that some concrete
cyclotomic polynomials cannot divide $Q_{t}(x)$ or $R_{t}(x)$, for each odd
integer $t\geq 3$. More precisely, we will turn our interest to the cyclotomic
polynomials $\Phi_{b}(x)$ where $b$ is a square-free integer all of whose
prime factors belong to the set $\\{2,3,5\\}$.

######  Lemma 10.

For each odd $t\geq 3$ and each positive integer $b\in\\{3,5,6,10,15,30\\}$,
the cyclotomic polynomial $\Phi_{b}(x)$ divides neither $Q_{t}(x)$ nor
$R_{t}(x)$.

###### Proof.

Similarly as in the proof of Lemma 9, let $Q_{t}^{\bmod b}(x)$ and
$R_{t}^{\bmod b}(x)$ be the next two polynomials:

$\displaystyle Q_{t}^{\bmod b}(x)$ $\displaystyle=2x^{(2t-1)\bmod
b}+x^{(t+1)\bmod b}-x^{t\bmod b}+x^{(t-1)\bmod b}-x^{(t-2)\bmod b}-2,$
$\displaystyle R_{t}^{\bmod b}(x)$ $\displaystyle=2x^{(2t-1)\bmod
b}-x^{(t+1)\bmod b}-3x^{t\bmod b}+3x^{(t-1)\bmod b}+x^{(t-2)\bmod b}-2.$

Here, it is imperative for us to notice that $\Phi_{b}(x)\mid
Q_{t}(x)\iff\Phi_{b}(x)\mid Q_{t}^{\bmod b}(x)$ and also that $\Phi_{b}(x)\mid
R_{t}(x)\iff\Phi_{b}(x)\mid R_{t}^{\bmod b}(x)$. However, for a fixed value of
$b\in\mathbb{N}$, there exist only finitely many polynomials $Q_{t}^{\bmod
b}(x)$ and $R_{t}^{\bmod b}(x)$, as $t$ ranges over the odd integers greater
than or equal to three. This is a direct consequence of the fact that $t$ can
only have finitely many remainders modulo $b$. Hence, if we are able to show
that $\Phi_{b}(x)$ divides none of these concrete polynomials, this is
sufficient to prove that $\Phi_{b}(x)$ divides neither $Q_{t}(x)$ nor
$R_{t}(x)$.

In order to prove the lemma, it is enough to demonstrate that
$\Phi_{b}(x)\nmid Q_{t}^{\bmod b}(x)$ and $\Phi_{b}(x)\nmid R_{t}^{\bmod
b}(x)$ for all the $b\in\\{3,5,6,10,15,30\\}$ and for all the possible
remainders $t\bmod b$. Doing this is trivial via computer with the help of
some symbolic computation software. We disclose the required computational
results in the form of two tables which are given in Appendices A and B. These
results clearly indicate that for each $b\in\\{3,5,6,10,15,30\\}$ the
remainders $Q_{t}^{\bmod b}(x)\bmod\Phi_{b}(x)$ and $R_{t}^{\bmod
b}(x)\bmod\Phi_{b}(x)$ can never be equal to the zero polynomial, regardless
of what the value of $t\bmod b$ is, which completes the proof of the lemma. ∎

It is important to notice that Theorem 5 can very conveniently be used on the
polynomials $Q_{t}(x)$ and $R_{t}(x)$, given the fact that they only have six
non-zero terms. This means that if $\Phi_{b}(x)\mid Q_{t}(x)$ and $p\mid b$
for some square-free integer $b$ and some prime number $p\geq 7$, we can
immediately deduct that $\Phi_{\frac{b}{p}}(x)\mid Q_{t}(x)$ is true as well.
The same can be said regarding $R_{t}(x)$. This practically means that if the
aforementioned division holds, we can cancel out as many prime factors of $b$
that are not below seven as we want, and the division will still have to hold.
Bearing this in mind, we are now able to formulate and prove the following
lemma regarding the divisibility of $Q_{t}(x)$ and $R_{t}(x)$ by cyclotomic
polynomials.

######  Lemma 11.

For each odd $t\geq 3$, neither $Q_{t}(x)$ nor $R_{t}(x)$ can be divisible by
a cyclotomic polynomial $\Phi_{b}(x)$ where $b\geq 3$.

###### Proof.

The proof will only be given for $Q_{t}(x)$, given the fact that the proof
regarding $R_{t}(x)$ is completely analogous. Suppose that $\Phi_{b}(x)\mid
Q_{t}(x)$ for some $b\geq 3$. By virtue of Lemma 8, we know that $b$ needs to
be a square-free integer. We now divide the problem into two separate cases,
depending on whether $b$ is divisible by either $3$ or $5$, or not.

_Case $3\nmid b$ and $5\nmid b$_. In this case, it is clear that $b$ has at
least one prime factor greater than $5$, since $b\notin\\{1,2\\}$. If we
repeatedly use Theorem 5 in order to cancel out all the prime factors of $b$
that are greater than $5$, until exactly one is left, we obtain that

$\Phi_{b^{\prime}}(x)\mid Q_{t}(x)$

must hold, where $b^{\prime}$ is square-free, not divisible by $3$ or $5$, and
has exactly one prime factor greater than $5$. In other words, we get that
either $\Phi_{p}(x)\mid Q_{t}(x)$ or $\Phi_{2p}\mid Q_{t}(x)$ holds, for some
prime number $p\geq 7$. However, this is not possible according to Lemma 9.

_Case $3\mid b$ or $5\mid b$_. Here, we can simply use Theorem 5 in order to
cancel out all the prime factors of $b$ that are greater than $5$, until there
are none left. This leads us to

$\Phi_{b^{\prime}}(x)\mid Q_{t}(x),$

where $b^{\prime}$ is square-free, divisible by $3$ or $5$, and has no prime
factors outside of the set $\\{2,3,5\\}$. These conditions imply that
$b^{\prime}\in\\{3,5,6,10,15,30\\}$. However, in this case
$\Phi_{b^{\prime}}(x)\mid Q_{t}(x)$ cannot possibly hold, as a direct
consequence of Lemma 10.

Both of the cases have led to a contradiction, which means that
$\Phi_{b}(x)\mid Q_{t}(x)$ cannot hold for any $b\geq 3$. ∎

Lemma 11 allows us to finish the proof of Theorem 6. We present the rest of
the proof in the remainder of this section.

_Proof of Theorem 6_. The proof for the case $t=1$ is fairly straightforward.
Due to the fact that
$\mathcal{S}^{\prime}_{1,n}=\left\\{\frac{n}{4},\frac{n}{4}+1\right\\}$, Eq.
(1) immediately gives us

$P(\zeta)=\zeta^{\frac{n}{4}}+\dfrac{1}{\zeta^{\frac{n}{4}}}+\zeta^{\frac{n}{4}+1}+\dfrac{1}{\zeta^{\frac{n}{4}+1}},$
(10)

where $\zeta$ is an arbitrary $n$-th root of unity different from $1$ and
$-1$. Now, the condition $P(\zeta)=0$ becomes equivalent to

$\displaystyle P(\zeta)$ $\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{\frac{n}{4}+1}\left(\zeta^{\frac{n}{4}}+\dfrac{1}{\zeta^{\frac{n}{4}}}+\zeta^{\frac{n}{4}+1}+\dfrac{1}{\zeta^{\frac{n}{4}+1}}\right)$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{\frac{n}{2}+2}+\zeta^{\frac{n}{2}+1}+\zeta+1$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle(\zeta+1)\left(\zeta^{\frac{n}{2}+1}+1\right)$ $\displaystyle=0$
$\displaystyle\iff\quad$ $\displaystyle\zeta^{\frac{n}{2}+1}+1$
$\displaystyle=0.$

Since we know that $\zeta^{\frac{n}{2}}\in\\{1,-1\\}$, we obtain that
$\zeta^{\frac{n}{2}+1}+1$ is equal to $\zeta+1$ or $-\zeta+1$. Either way,
this value cannot be equal to $0$, hence we conclude that $P(\zeta)\neq 0$.
Since the value $\zeta$ was arbitrarily chosen, we obtain that no $n$-th root
of unity different from $1$ and $-1$ can be a root of $P(x)$. According to
Lemma 4, this means that $\mathcal{D}^{\prime}_{1,n}$ is indeed a circulant
nut graph for any $n\geq 8$ divisble by four, as desired.

Now, we turn our attention to the case when $t\geq 3$. In this scenario, Eq.
(1) gives us

$P(\zeta)=\left(\zeta^{\frac{n}{4}}+\frac{1}{\zeta^{\frac{n}{4}}}\right)+\left(\zeta^{\frac{n}{4}+1}+\frac{1}{\zeta^{\frac{n}{4}+1}}\right)+\sum_{j=1}^{t-1}\left(\zeta^{j}+\frac{1}{\zeta^{j}}\right)+\sum_{j=\frac{n}{2}-t+1}^{\frac{n}{2}-1}\left(\zeta^{j}+\frac{1}{\zeta^{j}}\right),$

where $\zeta$ is an arbitrarily chosen $n$-th root of unity different from $1$
and $-1$. It is easy to further conclude that

$P(\zeta)=\left(\zeta^{\frac{n}{4}+1}+\zeta^{\frac{n}{4}}+\frac{1}{\zeta^{\frac{n}{4}}}+\frac{1}{\zeta^{\frac{n}{4}+1}}\right)+\sum_{j=1}^{t-1}\left(\zeta^{j}+\frac{1}{\zeta^{j}}+\zeta^{\frac{n}{2}-j}+\frac{1}{\zeta^{\frac{n}{2}-j}}\right).$
(11)

We will finish the proof by showing that $P(\zeta)\neq 0$ must necessarily
hold. In order to make the proof more concise, we will divide it into two
cases depending on whether $\zeta^{\frac{n}{2}}$ is equal to $1$ or $-1$.

_Case $\zeta^{\frac{n}{2}}=-1$_. In this case, we have that
$\zeta^{\frac{n}{2}-j}=-\dfrac{1}{\zeta^{j}}$ and
$\dfrac{1}{\zeta^{\frac{n}{2}-j}}=-\zeta^{j}$, which quickly implies

$\zeta^{j}+\frac{1}{\zeta^{j}}+\zeta^{\frac{n}{2}-j}+\frac{1}{\zeta^{\frac{n}{2}-j}}=0$

for any $j=\overline{1,t-1}$. Thus, Eq. (11) simplifies to the following
formula:

$P(\zeta)=\zeta^{\frac{n}{4}+1}+\zeta^{\frac{n}{4}}+\frac{1}{\zeta^{\frac{n}{4}}}+\frac{1}{\zeta^{\frac{n}{4}+1}}.$

However, this formula is exactly the same as Eq. (10), which we got while
dealing with the case $t=1$. Hence, an almost absolutely identical proof can
be used in order to show that $P(\zeta)\neq 0$.

_Case $\zeta^{\frac{n}{2}}=1$_. Here, we obtain that
$\zeta^{\frac{n}{2}-j}=\dfrac{1}{\zeta^{j}}$ and
$\dfrac{1}{\zeta^{\frac{n}{2}-j}}=\zeta^{j}$. This means that

$\zeta^{j}+\frac{1}{\zeta^{j}}+\zeta^{\frac{n}{2}-j}+\frac{1}{\zeta^{\frac{n}{2}-j}}=2\left(\zeta^{j}+\frac{1}{\zeta^{j}}\right)$

for any $j=\overline{1,t-1}$. According to Eq. (11), the condition
$P(\zeta)=0$ becomes equivalent to

$\displaystyle P(\zeta)$ $\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\left(\zeta^{\frac{n}{4}+1}+\zeta^{\frac{n}{4}}+\frac{1}{\zeta^{\frac{n}{4}}}+\frac{1}{\zeta^{\frac{n}{4}+1}}\right)+2\sum_{j=1}^{t-1}\left(\zeta^{j}+\frac{1}{\zeta^{j}}\right)$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\left(\zeta^{\frac{n}{4}+1}+\zeta^{\frac{n}{4}}+\frac{1}{\zeta^{\frac{n}{4}}}+\frac{1}{\zeta^{\frac{n}{4}+1}}\right)-2+2\sum_{j=1-t}^{t-1}\zeta^{j}$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{t-1}\left(\left(\zeta^{\frac{n}{4}+1}+\zeta^{\frac{n}{4}}+\frac{1}{\zeta^{\frac{n}{4}}}+\frac{1}{\zeta^{\frac{n}{4}+1}}\right)-2+2\sum_{j=1-t}^{t-1}\zeta^{j}\right)$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\left(\zeta^{t+\frac{n}{4}}+\zeta^{t+\frac{n}{4}-1}+\zeta^{t-\frac{n}{4}-1}+\zeta^{t-\frac{n}{4}-2}\right)-2\zeta^{t-1}+2\sum_{j=0}^{2t-2}\zeta^{j}$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle(\zeta-1)\left(\zeta^{t+\frac{n}{4}}+\zeta^{t+\frac{n}{4}-1}+\zeta^{t-\frac{n}{4}-1}+\zeta^{t-\frac{n}{4}-2}-2\zeta^{t-1}+2\sum_{j=0}^{2t-2}\zeta^{j}\right)$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{t+\frac{n}{4}+1}-\zeta^{t+\frac{n}{4}-1}+\zeta^{t-\frac{n}{4}}-\zeta^{t-\frac{n}{4}-2}-2\zeta^{t}+2\zeta^{t-1}+2\zeta^{2t-1}-2$
$\displaystyle=0.$ (12)

Now, we will divide the problem into two subcases depending on whether
$\zeta^{\frac{n}{4}}$ is equal to $1$ or $-1$.

_Subcase $\zeta^{\frac{n}{4}}=1$_. In this subcase, it is easy to see that Eq.
(12) further becomes equivalent to

$\displaystyle\zeta^{t+\frac{n}{4}+1}-\zeta^{t+\frac{n}{4}-1}+\zeta^{t-\frac{n}{4}}-\zeta^{t-\frac{n}{4}-2}-2\zeta^{t}+2\zeta^{t-1}+2\zeta^{2t-1}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{t+1}-\zeta^{t-1}+\zeta^{t}-\zeta^{t-2}-2\zeta^{t}+2\zeta^{t-1}+2\zeta^{2t-1}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$ $\displaystyle
2\zeta^{2t-1}+\zeta^{t+1}-\zeta^{t}+\zeta^{t-1}-\zeta^{t-2}-2$
$\displaystyle=0.$

Thus, if we suppose that $P(\zeta)=0$, we then get that $\zeta$ is a root of
the polynomial $Q_{t}(x)$. However, since $\zeta\neq 1,-1$ and $\zeta^{n}=1$,
this means that $\zeta$ is a primitive $b$-th root of unity for some $b\geq
3$. This implies that $\Phi_{b}(x)$ necessarily divides $Q_{t}(x)$, which is
impossible according to Lemma 11, hence $P(\zeta)=0$ cannot be true.

_Subcase $\zeta^{\frac{n}{4}}=-1$_. Here, Eq. (12) quickly becomes equivalent
to

$\displaystyle\zeta^{t+\frac{n}{4}+1}-\zeta^{t+\frac{n}{4}-1}+\zeta^{t-\frac{n}{4}}-\zeta^{t-\frac{n}{4}-2}-2\zeta^{t}+2\zeta^{t-1}+2\zeta^{2t-1}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle-\zeta^{t+1}+\zeta^{t-1}-\zeta^{t}+\zeta^{t-2}-2\zeta^{t}+2\zeta^{t-1}+2\zeta^{2t-1}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$ $\displaystyle
2\zeta^{2t-1}-\zeta^{t+1}-3\zeta^{t}+3\zeta^{t-1}+\zeta^{t-2}-2$
$\displaystyle=0.$

In a similar fashion, if we suppose that $P(\zeta)=0$, we conclude that
$\zeta$ must be a root of the polynomial $R_{t}(x)$. Due to the fact that
$\zeta\neq 1,-1$ and $\zeta^{n}=1$, we see that $\zeta$ is a primitive $b$-th
root of unity for some $b\geq 3$. Hence, $\Phi_{b}(x)\mid R_{t}(x)$, which is
again impossible by virtue of Lemma 11. Thus, $P(\zeta)\neq 0$. ∎

##  4 $\mathcal{D}^{\prime\prime}_{t,n}$ family of circulant graphs

Here, we give the second of the two central theorems disclosed in the paper.

######  Theorem 12.

For each $t\in\mathbb{N}$ and $n\geq 4t+6$ such that $n\equiv_{4}2$, the
circulant graph $\mathcal{D}^{\prime\prime}_{t,n}$ must be a $4t$-regular nut
graph of order $n$.

The complete proof of Theorem 12 will have a very similar structure as the
previously described proof of Theorem 6, albeit with more complexity. Instead
of the polynomials $Q_{t}(x)$ and $R_{t}(x)$, here we will rely on the integer
polynomials $U_{t},W_{t}\in\mathbb{Z}[x]$ that are defined as

$\displaystyle U_{t}(x)$
$\displaystyle=2x^{4t-1}+x^{2t+4}-2x^{2t+1}+2x^{2t-1}-x^{2t-4}-2x,$
$\displaystyle W_{t}(x)$
$\displaystyle=2x^{4t-1}-x^{2t+4}-2x^{2t+1}+2x^{2t-1}+x^{2t-4}-2x,$

for all the $t\in\mathbb{N},\,t\geq 2$. These polynomials are clearly well
defined for all the $t\geq 2$ and must have exactly six non-zero terms, due to
the fact that

$1<2t-4<2t-1<2t+1<2t+4<4t-1$

for each $t\geq 3$, while

$\displaystyle 4t-1$ $\displaystyle=7,$ $\displaystyle 2t+4$
$\displaystyle=8,$ $\displaystyle 2t+1$ $\displaystyle=5,$ $\displaystyle
2t-1$ $\displaystyle=3,$ $\displaystyle 2t-4$ $\displaystyle=0,$
$\displaystyle 1$ $\displaystyle=1,$

for $t=2$. By setting

$M_{t}=\\{1,2t-4,2t-1,2t+1,2t+4,4t-1\\}$

for each $t\geq 2$, we can show that the $M_{t}$ sets have a property that is
very similar to the one regarding the $L_{t}$ sets which was demonstrated
earlier in Lemma 7.

######  Lemma 13.

For each $t\geq 2$ and each prime number $p\geq 7$, the set $M_{t}$ contains
an element whose remainder modulo $p$ is unique within the set.

###### Proof.

It is easy to notice that the four integers $2t-4,2t-1,2t+1,2t+4$ necessarily
have mutually distinct remainders modulo $p$. This quickly implies that at
least two of them must have a remainder modulo $p$ that is different from the
remainders of both $1$ and $4t-1$. ∎

We will now implement Lemma 13 in order to prove a valuable property of the
$U_{t}(x)$ and $W_{t}(x)$ polynomials regarding their division by cyclotomic
polynomials, as demonstrated in the following lemma.

######  Lemma 14.

For any $t\geq 2$, neither $U_{t}(x)$ nor $W_{t}(x)$ can be divisible by a
cyclotomic polynomial $\Phi_{b}(x)$ such that $p^{2}\mid b$ for some prime
number $p\geq 3$.

###### Proof.

This proof will be done in a completely analogous manner as that of Lemma 8.
In case $b\in\mathbb{N}$ and $p^{2}\mid b$ for some prime number $p$, we will
again use the fact that $\Phi_{b}(x)=\Phi_{\frac{b}{p}}(x^{p})$.

Suppose that $\Phi_{b}(x)\mid U_{t}(x)$ for some $t\geq 2$ and
$b\in\mathbb{N}$ such that $p^{2}\mid b$ for some prime number $p\geq 3$. Let
$U_{t}^{(j)}(x)$ denote the polynomial composed of all the terms of $U_{t}(x)$
whose powers are congruent to $j$ modulo $p$, for each $j=\overline{0,p-1}$.
The same logic used in the proof of Lemma 8 allows us to conclude that

$\Phi_{b}(x)\mid U_{t}^{(j)}(x)$

must hold for all the $j=\overline{0,p-1}$. It is clear that the same notation
and implication can be used regarding the $W_{t}(x)$ polynomial in case
$\Phi_{b}(x)\mid W_{t}(x)$ is true. We will now finalize the proof of the
lemma by taking into consideration three separate cases depending on the value
of the prime number $p$.

_Case $p\geq 7$_. In this scenario, Lemma 13 tells us that the set $M_{t}$
must contain an element whose remainder modulo $p$ is unique within that set.
Hence, this case can be proved completely analogously to the case $p\geq 5$
from the proof of Lemma 8.

_Case $p=5$_. If $t\equiv_{5}2$ or $t\equiv_{5}4$, then there exists an
element of the set $M_{t}$ whose remainder modulo $5$ is unique with that set,
as shown in Table 2. In this subcase, a contradiction can easily be obtained
if we suppose that either $\Phi_{b}(x)\mid U_{t}(x)$ or $\Phi_{b}(x)\mid
W_{t}(x)$, by using the same logic as in the $p\geq 7$ case. We resolve the
remaining three subcases separately.

| $t\equiv_{5}0$ | $t\equiv_{5}1$ | $t\equiv_{5}2$ | $t\equiv_{5}3$ | $t\equiv_{5}4$
---|---|---|---|---|---
$1\bmod 5$ | $1$ | $1$ | $1$ | $1$ | $1$
$(2t-4)\bmod 5$ | $1$ | $3$ | $0$ | $2$ | $4$
$(2t-1)\bmod 5$ | $4$ | $1$ | $3$ | $0$ | $2$
$(2t+1)\bmod 5$ | $1$ | $3$ | $0$ | $2$ | $4$
$(2t+4)\bmod 5$ | $4$ | $1$ | $3$ | $0$ | $2$
$(4t-1)\bmod 5$ | $4$ | $3$ | $2$ | $1$ | $0$
Table 2: The elements of the set $M_{t}$ modulo $5$.

_Subcase $t\equiv_{5}0$_. If we suppose that $\Phi_{b}\mid U_{t}(x)$, then we
get

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{2t+1}-x^{2t-4}-2x,$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}+x^{2t+4}+2x^{2t-1}.$

Since $t\geq 5$, we quickly obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{2t+1}-x^{2t-4}-2x$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x(2x^{2t}+x^{2t-5}+2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t}+x^{2t-5}+2,$ (13)

as well as

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}+x^{2t+4}+2x^{2t-1}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-1}(2x^{2t}+x^{5}+2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t}+x^{5}+2.$ (14)

Furthermore, if we subtract the right-hand sides of Eqs. (13) and (14), this
leads us to

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(2x^{2t}+x^{2t-5}+2)-(2x^{2t}+x^{5}+2)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-5}-x^{5}$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{5}(x^{2t-10}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t-10}-1.$

Now, Eq. (14) helps us obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t}+x^{5}+2$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
2x^{2t}+x^{5}+2-2x^{10}(x^{2t-10}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{10}+x^{5}+2.$

However, none of the roots of the polynomial $2x^{10}+x^{5}+2$ are actually
roots of unity, as demonstrated in Appendix E, hence we obtain a
contradiction.

Similarly, if we suppose that $\Phi_{b}(x)\mid W_{t}(x)$, then we get

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{2t+1}+x^{2t-4}-2x,$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}-x^{2t+4}+2x^{2t-1}.$

Due to $t\geq 5$, we have

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{2t+1}+x^{2t-4}-2x$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x(2x^{2t}-x^{2t-5}+2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t}-x^{2t-5}+2$ (15)

and

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}-x^{2t+4}+2x^{2t-1}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-1}(2x^{2t}-x^{5}+2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t}-x^{5}+2.$ (16)

By subtracting the right-hand sides of Eqs. (15) and (16), it follows that

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(2x^{2t}-x^{2t-5}+2)-(2x^{2t}-x^{5}+2)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x^{2t-5}+x^{5}$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{5}(x^{2t-10}-1)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-10}-1.$

Hence, Eq. (16) is now able to give us

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t}-x^{5}+2$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
2x^{2t}-x^{5}+2-2x^{10}(x^{2t-10}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{10}-x^{5}+2.$

However, similarly as with $U_{t}(x)$, none of the roots of $2x^{10}-x^{5}+2$
are roots of unity, as shown in Appendix E, which leads to a contradiction.

_Subcase $t\equiv_{5}1$_. If we suppose that $\Phi_{b}\mid U_{t}(x)$, we
immediately get

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+4}+2x^{2t-1}-2x,$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}-2x^{2t+1}-x^{2t-4}.$

Since $t\geq 6$, it is easy to see that

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+4}+2x^{2t-1}-2x$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x(x^{2t+3}+2x^{2t-2}-2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+3}+2x^{2t-2}-2,$ (17)

as well as

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}-2x^{2t+1}-x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-4}(2x^{2t+3}-2x^{5}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t+3}-2x^{5}-1.$ (18)

By using Eqs. (17) and (18) together, we further obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
2(x^{2t+3}+2x^{2t-2}-2)-(2x^{2t+3}-2x^{5}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 4x^{2t-2}+2x^{5}-3.$ (19)

Now, by using Eqs. (18) and (19) together, we see that

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
2(2x^{2t+3}-2x^{5}-1)-x^{5}(4x^{2t-2}+2x^{5}-3)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{10}-x^{5}-2,$

which is not possible since the polynomial $2x^{10}+x^{5}+2$ has no roots of
unity among its roots, as discussed earlier.

In a similar fashion, if we suppose that $\Phi_{b}\mid W_{t}(x)$, this gives
us

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{2t+4}+2x^{2t-1}-2x,$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}-2x^{2t+1}+x^{2t-4}.$

Due to $t\geq 6$, we swiftly obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{2t+4}+2x^{2t-1}-2x$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x(x^{2t+3}-2x^{2t-2}+2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+3}-2x^{2t-2}+2$ (20)

and

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}-2x^{2t+1}+x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-4}(2x^{2t+3}-2x^{5}+1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t+3}-2x^{5}+1.$ (21)

If we use Eqs. (20) and (21) together, we conclude that

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(2x^{2t+3}-2x^{5}+1)-2(x^{2t+3}-2x^{2t-2}+2)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
4x^{2t-2}-2x^{5}-3.$ (22)

Furthermore, by using Eqs. (21) and (22) together, we get

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{5}(4x^{2t-2}-2x^{5}-3)-2(2x^{2t+3}-2x^{5}+1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{10}+x^{5}-2,$

which is impossible given the fact that the polynomial $2x^{10}-x^{5}+2$ has
no roots of unity among its roots, as we have already discussed.

_Subcase $t\equiv_{5}3$_. If we suppose that $\Phi_{b}(x)\mid U_{t}(x)$, we
obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+4}+2x^{2t-1},$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{2t+1}-x^{2t-4}.$

Since $t\geq 3$, this directly gives us

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+4}+2x^{2t-1}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-1}(x^{5}+2)$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{5}+2$ (23)

and

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{2t+1}-x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x^{2t-4}(2x^{5}+1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{5}+1.$ (24)

By combining Eqs. (23) and (24), we reach

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2(x^{5}+2)-(2x^{5}+1)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 3,$

thus yielding a contradiction.

On the other hand, if we suppose that $\Phi_{b}(x)\mid W_{t}(x)$, this gives
us

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{2t+4}+2x^{2t-1},$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{2t+1}+x^{2t-4},$

which further implies

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{2t+4}+2x^{2t-1}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x^{2t-1}(x^{5}-2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{5}-2,$ (25)

as well as

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{2t+1}+x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x^{2t-4}(2x^{5}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{5}-1.$ (26)

By combining Eqs. (25) and (26), we conclude that

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2(x^{5}-2)-(2x^{5}-1)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-3,$

which is not possible.

_Case $p=3$_. This case can be resolved by taking into consideration the
modular values given in Table 3. Thus, we divide the case into three subcases
depending on the value of $t\bmod 3$.

| $t\equiv_{3}0$ | $t\equiv_{3}1$ | $t\equiv_{3}2$
---|---|---|---
$1\bmod 3$ | $1$ | $1$ | $1$
$(2t-4)\bmod 3$ | $2$ | $1$ | $0$
$(2t-1)\bmod 3$ | $2$ | $1$ | $0$
$(2t+1)\bmod 3$ | $1$ | $0$ | $2$
$(2t+4)\bmod 3$ | $1$ | $0$ | $2$
$(4t-1)\bmod 3$ | $2$ | $0$ | $1$
Table 3: The elements of the set $M_{t}$ modulo $3$.

_Subcase $t\equiv_{3}0$_. In this subcase, if we suppose that $\Phi_{b}(x)\mid
U_{t}(x)$, we then have

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+4}-2x^{2t+1}-2x,$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}+2x^{2t-1}-x^{2t-4},$

which immediately gives

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+4}-2x^{2t+1}-2x$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x(x^{2t+3}-2x^{2t}-2)$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{2t+3}-2x^{2t}-2$ (27)

and

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}+2x^{2t-1}-x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-4}(2x^{2t+3}+2x^{3}-1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t+3}+2x^{3}-1.$ (28)

By using Eqs. (27) and (28) together, we obtain

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(2x^{2t+3}+2x^{3}-1)-2(x^{2t+3}-2x^{2t}-2)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
4x^{2t}+2x^{3}+3.$ (29)

Now, by using Eqs. (28) and (29), we get

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
2(2x^{2t+3}+2x^{3}-1)-x^{3}(4x^{2t}+2x^{3}+3)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-2x^{6}+x^{3}-2.$

However, none of the roots of the polynomial $2x^{6}-x^{3}+2$ are actually
roots of unity, as shown in Apprendix E, which leads us to a contradiction.

Similarly, if we suppose that $\Phi_{b}(x)\mid W_{t}(x)$, we obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{2t+4}-2x^{2t+1}-2x,$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}+2x^{2t-1}+x^{2t-4},$

which quickly leads us to

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{2t+4}-2x^{2t+1}-2x$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x(x^{2t+3}+2x^{2t}+2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+3}+2x^{2t}+2$ (30)

and

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}+2x^{2t-1}+x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-4}(2x^{2t+3}+2x^{3}+1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t+3}+2x^{3}+1.$ (31)

If we use Eqs. (30) and (31) together, we conclude that

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
2(x^{2t+3}+2x^{2t}+2)-(2x^{2t+3}+2x^{3}+1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 4x^{2t}-2x^{3}+3.$ (32)

Furthermore, by combining Eqs. (31) and (32), we reach

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
2(2x^{2t+3}+2x^{3}+1)-x^{3}(4x^{2t}-2x^{3}+3)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{6}+x^{3}+2,$

which leads to a contradiction, given the fact that the polynomial
$2x^{6}+x^{3}+2$ has no root which represents a root of unity, as demonstrated
in Apprendix E.

_Subcase $t\equiv_{3}1$_. In this scenario, supposing that $\Phi_{b}(x)\mid
U_{t}(x)$ is true leads to

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}-x^{2t-4}-2x,$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}+x^{2t+4}-2x^{2t+1}.$

Furthermore, we swiftly get

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}-x^{2t-4}-2x$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x(2x^{2t-2}-x^{2t-5}-2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-2}-x^{2t-5}-2,$ (33)

as well as

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}+x^{2t+4}-2x^{2t+1}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t+1}(2x^{2t-2}+x^{3}-2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-2}+x^{3}-2.$ (34)

Given the fact that $t\geq 4$, subtracting the right-hand sides of Eqs. (33)
and (34) helps us obtain

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(2x^{2t-2}+x^{3}-2)-(2x^{2t-2}-x^{2t-5}-2)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-5}+x^{3}$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{3}(x^{2t-8}+1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t-8}+1.$ (35)

Now, by combining Eqs. (34) and (35), we conclude that

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(2x^{2t-2}+x^{3}-2)-2x^{6}(x^{2t-8}+1)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-2x^{6}+x^{3}-2,$

thus yielding a contradiction due to the fact that the polynomial
$2x^{6}-x^{3}+2$ has no roots of unity among its roots, as discussed earlier.

In a similar fashion, supposing that $\Phi_{b}(x)\mid W_{t}(x)$ gives us

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}+x^{2t-4}-2x,$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}-x^{2t+4}-2x^{2t+1},$

which immediately leads to

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}+x^{2t-4}-2x$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x(2x^{2t-2}+x^{2t-5}-2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-2}+x^{2t-5}-2,$ (36)

as well as

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{4t-1}-x^{2t+4}-2x^{2t+1}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t+1}(2x^{2t-2}-x^{3}-2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-2}-x^{3}-2.$ (37)

We can now subtract the right-hand sides of Eqs. (36) and (37) and use the
fact that $t\geq 4$ in order to obtain

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(2x^{2t-2}+x^{2t-5}-2)-(2x^{2t-2}-x^{3}-2)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-5}+x^{3}$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{3}(x^{2t-8}+1)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t-8}+1.$ (38)

Furthermore, combining Eqs. (37) and (38) gives us

$\displaystyle\Phi_{b}(x)$
$\displaystyle\mid(2x^{2t-2}-x^{3}-2)-2x^{6}(x^{2t-8}+1)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-2x^{6}-x^{3}-2,$

which is impossible since the polynomial $2x^{6}+x^{3}+2$ has no roots of
unity among its roots, as we have already discussed.

_Subcase $t\equiv_{3}2$_. In this subcase, if we suppose that $\Phi_{b}(x)\mid
U_{t}(x)$, then we directly obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+4}-2x^{2t+1},$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}-x^{2t-4},$

which leads us to

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{2t+4}-2x^{2t+1}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t+1}(x^{3}-2)$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid x^{3}-2$ (39)

and

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}-x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-4}(2x^{3}-1)$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid 2x^{3}-1.$ (40)

By using Eqs. (39) and (40) together, we reach

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid(2x^{3}-1)-2(x^{3}-2)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 3,$

thus yielding a contradiction.

Similarly, if we suppose that $\Phi_{b}(x)\mid W_{t}(x)$, we obtain

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{2t+4}-2x^{2t+1},$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}+x^{2t-4},$

which further gives

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-x^{2t+4}-2x^{2t+1}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid-x^{2t+1}(x^{3}+2)$ $\displaystyle\implies\quad$
$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid x^{3}+2,$ (41)

as well as

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid 2x^{2t-1}+x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid
x^{2t-4}(2x^{3}+1)$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$
$\displaystyle\mid 2x^{3}+1.$ (42)

By combining Eqs. (41) and (42), we get

$\displaystyle\Phi_{b}(x)$ $\displaystyle\mid(2x^{3}+1)-2(x^{3}+2)$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}(x)$ $\displaystyle\mid-3,$

which is clearly not possible. ∎

If is clear that the formulation of Lemma 14 is very similar to that of the
previously proven Lemma 8 from Section 3. The key difference is that Lemma 14
does not cover the case for $p=2$. In fact, it can be shown that this property
does not hold for the $U_{t}(x)$ and $W_{t}(x)$ polynomials, i.e. it is
possible that they are divisible by a cyclotomic polynomial $\Phi_{b}(x)$ such
that $4\mid b$. However, although the condition $4\mid b$ can hold, it can be
shown that the only way for this to happen is if $b\in\\{4,8\\}$, as
demonstrated in the following lemma.

######  Lemma 15.

For any $t\geq 2$, if $U_{t}(x)$ or $W_{t}(x)$ are divisible by some
cyclotomic polynomial $\Phi_{b}(x)$ such that $4\mid b$, then $b=4$ or $b=8$.

###### Proof.

Suppose that $4\mid b$. Given the fact that $2\mid\frac{b}{2}$, it is clear
that $\Phi_{b}(x)=\Phi_{\frac{b}{2}}(x^{2})$ (see, for example, [7, p. 160]).
By using the same logic as in the proofs of Lemmas 8 and 14, we obtain that
$\Phi_{b}(x)\mid U_{t}(x)$ would imply

$\Phi_{b}(x)\mid U_{t}^{(j)}(x)$

for each $j=\overline{0,1}$, where $U_{t}^{(j)}(x)$ represents the polynomial
composed of the terms of $U_{t}(x)$ whose powers are congruent to $j$ modulo
$2$. The same conclusion and notation can be applied to $W_{t}(x)$, as well.

Since all the values $1,2t-1,2t+1,4t-1$ are odd, while $2t+4$ and $2t-4$ are
even, we conclude that $\Phi_{b}\mid U_{t}(x)$ would immediately imply

$\Phi_{b}\mid x^{2t+4}-x^{2t-4},$

while $\Phi_{b}\mid W_{t}(x)$ would give

$\Phi_{b}\mid-x^{2t+4}+x^{2t-4}.$

Either way, we would reach

$\displaystyle\Phi_{b}$ $\displaystyle\mid x^{2t+4}-x^{2t-4}$
$\displaystyle\implies\quad$ $\displaystyle\Phi_{b}$ $\displaystyle\mid
x^{2t-4}(x^{8}-1)$ $\displaystyle\implies\quad$ $\displaystyle\Phi_{b}$
$\displaystyle\mid x^{8}-1.$

This practically means that each primitive $b$-th root of unity must be an
eighth root of unity, i.e. $b\mid 8$. This is only possible if $b=4$ or $b=8$.
∎

A direct consequence of Lemmas 14 and 15 is that if the cyclotomic polynomial
$\Phi_{b}(x)$ divides $U_{t}(x)$ or $W_{t}(x)$, then the integer
$b\in\mathbb{N}$ needs to either be square-free, or be equal to $4$ or $8$. In
fact, for any $t\geq 2$, the only cyclotomic polynomials that could divide
$U_{t}(x)$ or $W_{t}(x)$ are actually
$\Phi_{1}(x),\Phi_{2}(x),\Phi_{4}(x),\Phi_{8}(x)$. This observation forms the
central part of the proof of Theorem 12. However, in order to prove this
claim, we will be in need of two more auxiliary lemmas, which hold a great
resemblance to the previously proven Lemmas 9 and 10 from Section 3.

######  Lemma 16.

For each $t\geq 2$ and each prime number $p\geq 7$, neither $U_{t}(x)$ nor
$W_{t}(x)$ can be divisible by the cyclotomic polynomial $\Phi_{p}(x)$ or the
cyclotomic polynomial $\Phi_{2p}(x)$.

###### Proof.

The proof can be done in an entirely analogous manner as the proof of Lemma 9
from Section 3, the only difference being that Lemma 13 is used to conclude
that there exists an element of the set $M_{t}$ that has a unique remainder
within that set, instead of Lemma 7. Thus, we choose to leave the proof out. ∎

######  Lemma 17.

For each $t\geq 2$ and each positive integer $b\in\\{3,5,6,10,15,30\\}$, the
cyclotomic polynomial $\Phi_{b}(x)$ divides neither $U_{t}(x)$ nor $W_{t}(x)$.

###### Proof.

The proof can be done by using an absolutely identical mechanism as the proof
of Lemma 10 from Section 3. We disclose the necessary computational results in
Appendices C and D. ∎

We shall now formulate and prove the central lemma regarding the divisibility
of the $U_{t}(x)$ and $W_{t}(x)$ polynomials by cyclotomic polynomials. Given
the fact that these polynomials also have six non-zero terms, like the
$Q_{t}(x)$ and $R_{t}(x)$ polynomials from Section 3, using Theorem 5 becomes
very convenient once more. The same prime number cancellation mechanism can be
implemented for each prime number $p\geq 7$ that divides $b$ whenever
$\Phi_{b}(x)$ divides either $U_{t}(x)$ or $W_{t}(x)$, as it was elaborated in
Section 3. Bearing this in mind, we give the following lemma.

######  Lemma 18.

For each $t\geq 2$, neither $U_{t}(x)$ nor $W_{t}(x)$ can be divisible by a
cyclotomic polynomial $\Phi_{b}(x)$ such that $b\notin\\{1,2,4,8\\}$.

###### Proof.

The proof will only be given for $U_{t}(x)$, given the fact that the proof
regarding $W_{t}(x)$ is completely analogous. Suppose that $\Phi_{b}(x)\mid
U_{t}(x)$, for some $b\in\mathbb{N}$ such that $b\notin\\{1,2,4,8\\}$. Since
$b$ is not equal to $4$ or $8$, Lemmas 14 and 15 tell us that $b$ must be a
square-free integer. We now divide the problem into two separate cases,
depending on whether $b$ is divisible by either $3$ or $5$, or not.

_Case $3\nmid b$ and $5\nmid b$_. This case is proved completely analogously
to the corresponding case from the proof of Lemma 11 from Section 3. The only
small difference is that Lemma 16 is used instead of Lemma 9.

_Case $3\mid b$ or $5\mid b$_. This case is also proved entirely analogously
to the corresponding case from the proof of Lemma 11. As expected, the only
minor difference is that Lemma 17 is used instead of Lemma 10. ∎

Taking into consideration all the results obtained in the previously disclosed
lemmas, we are finally able to complete the proof of Theorem 12. Thus, we
present the rest of the proof.

_Proof of Theorem 12_. The case $t=1$ is trivial to prove. Here, we simply
have $S^{\prime\prime}_{1,n}=\left\\{\frac{n+2}{4},\frac{n+6}{4}\right\\}$,
hence Eq. (1) directly gives us

$P(\zeta)=\zeta^{\frac{n+2}{4}}+\dfrac{1}{\zeta^{\frac{n+2}{4}}}+\zeta^{\frac{n+6}{4}}+\dfrac{1}{\zeta^{\frac{n+6}{4}}},$
(43)

where $\zeta$ is an arbitrary $n$-th root of unity different from $1$ and
$-1$. The condition $P(\zeta)=0$ is clearly equivalent to

$\displaystyle P(\zeta)$ $\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{\frac{n+6}{4}}\left(\zeta^{\frac{n+2}{4}}+\dfrac{1}{\zeta^{\frac{n+2}{4}}}+\zeta^{\frac{n+6}{4}}+\dfrac{1}{\zeta^{\frac{n+6}{4}}}\right)$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{\frac{n}{2}+3}+\zeta^{\frac{n}{2}+2}+\zeta+1$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle(\zeta+1)\left(\zeta^{\frac{n}{2}+2}+1\right)$ $\displaystyle=0$
$\displaystyle\iff\quad$ $\displaystyle\zeta^{\frac{n}{2}+2}+1$
$\displaystyle=0.$

Due to the fact that $\zeta^{\frac{n}{2}}\in\\{1,-1\\}$, it is obvious that
$\zeta^{\frac{n}{2}+2}$ is equal to either $\zeta^{2}+1$ or $-\zeta^{2}+1$.
However, both of these expressions cannot be equal to zero. If $\zeta^{2}+1$
were to equal zero, then we would have that $\zeta\in\\{i,-i\\}$, which is
impossible due to the fact that $n\equiv_{4}2$, hence both $i$ and $-i$ are
not $n$-th roots of unity. On the other hand, $-\zeta^{2}+1\neq 0$ purely
because $\zeta$ was chosen in such a way that it is distinct from both $1$ and
$-1$. Thus, we get that $P(\zeta)\neq 0$ for any $n$-th root of unity
different from $1$ and $-1$. By virtue of Lemma 4, we conclude that
$\mathcal{D}^{\prime\prime}_{1,n}$ truly is a circulant nut graph for any
$n\geq 10$ such that $n\equiv_{4}2$.

In the remainder of the proof, we will suppose that $t\geq 2$. Eq. (1) now
gives us

$P(\zeta)=\left(\zeta^{\frac{n+2}{4}}+\frac{1}{\zeta^{\frac{n+2}{4}}}\right)+\left(\zeta^{\frac{n+6}{4}}+\frac{1}{\zeta^{\frac{n+6}{4}}}\right)+\sum_{j=1}^{t-1}\left(\zeta^{j}+\frac{1}{\zeta^{j}}\right)+\sum_{j=\frac{n}{2}-t+1}^{\frac{n}{2}-1}\left(\zeta^{j}+\frac{1}{\zeta^{j}}\right),$

where $\zeta$ is an arbitrarily chosen $n$-th root of unity different from $1$
and $-1$. It is not difficult to further obtain

$P(\zeta)=\left(\zeta^{\frac{n+6}{4}}+\zeta^{\frac{n+2}{4}}+\frac{1}{\zeta^{\frac{n+2}{4}}}+\frac{1}{\zeta^{\frac{n+6}{4}}}\right)+\sum_{j=1}^{t-1}\left(\zeta^{j}+\frac{1}{\zeta^{j}}+\zeta^{\frac{n}{2}-j}+\frac{1}{\zeta^{\frac{n}{2}-j}}\right).$
(44)

We will finalize the proof by demonstrating that $P(\zeta)\neq 0$ must be
true. We will divide this proof into two cases in the same way as it was done
while proving Theorem 6.

_Case $\zeta^{\frac{n}{2}}=-1$_. In this case, it is straightforward to notice
that $\zeta^{\frac{n}{2}-j}=-\dfrac{1}{\zeta^{j}}$ and
$\dfrac{1}{\zeta^{\frac{n}{2}-j}}=-\zeta^{j}$, which directly leads us to

$\zeta^{j}+\frac{1}{\zeta^{j}}+\zeta^{\frac{n}{2}-j}+\frac{1}{\zeta^{\frac{n}{2}-j}}=0$

for any $j=\overline{1,t-1}$. Hence, it is convenient to simplify Eq. (44) in
order to get

$P(\zeta)=\zeta^{\frac{n+6}{4}}+\zeta^{\frac{n+2}{4}}+\frac{1}{\zeta^{\frac{n+2}{4}}}+\frac{1}{\zeta^{\frac{n+6}{4}}}.$

However, this formula is identical to Eq. (43), which we had to deal with
while solving the case $t=1$. An almost absolutely identical proof can be used
in order to show that $P(\zeta)\neq 0$ must hold, as desired, hence we choose
to leave it out.

_Case $\zeta^{\frac{n}{2}}=1$_. It is easy to see that
$\zeta^{\frac{n}{2}-j}=\dfrac{1}{\zeta^{j}}$ and
$\dfrac{1}{\zeta^{\frac{n}{2}-j}}=\zeta^{j}$. This implies

$\zeta^{j}+\frac{1}{\zeta^{j}}+\zeta^{\frac{n}{2}-j}+\frac{1}{\zeta^{\frac{n}{2}-j}}=2\left(\zeta^{j}+\frac{1}{\zeta^{j}}\right)$

for any $j=\overline{1,t-1}$. According to Eq. (44), the equality $P(\zeta)=0$
becomes equivalent to

$\displaystyle P(\zeta)$ $\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\left(\zeta^{\frac{n+6}{4}}+\zeta^{\frac{n+2}{4}}+\frac{1}{\zeta^{\frac{n+2}{4}}}+\frac{1}{\zeta^{\frac{n+6}{4}}}\right)+2\sum_{j=1}^{t-1}\left(\zeta^{j}+\frac{1}{\zeta^{j}}\right)$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\left(\zeta^{\frac{n+6}{4}}+\zeta^{\frac{n+2}{4}}+\frac{1}{\zeta^{\frac{n+2}{4}}}+\frac{1}{\zeta^{\frac{n+6}{4}}}\right)-2+2\sum_{j=1-t}^{t-1}\zeta^{j}$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{t-1}\left(\left(\zeta^{\frac{n+6}{4}}+\zeta^{\frac{n+2}{4}}+\frac{1}{\zeta^{\frac{n+2}{4}}}+\frac{1}{\zeta^{\frac{n+6}{4}}}\right)-2+2\sum_{j=1-t}^{t-1}\zeta^{j}\right)$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\left(\zeta^{t+\frac{n+2}{4}}+\zeta^{t+\frac{n-2}{4}}+\zeta^{t-\frac{n+6}{4}}+\zeta^{t-\frac{n+10}{4}}\right)-2\zeta^{t-1}+2\sum_{j=0}^{2t-2}\zeta^{j}$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle(\zeta-1)\left(\zeta^{t+\frac{n+2}{4}}+\zeta^{t+\frac{n-2}{4}}+\zeta^{t-\frac{n+6}{4}}+\zeta^{t-\frac{n+10}{4}}-2\zeta^{t-1}+2\sum_{j=0}^{2t-2}\zeta^{j}\right)$
$\displaystyle=0$ $\displaystyle\iff\quad$
$\displaystyle\zeta^{t+\frac{n+6}{4}}-\zeta^{t+\frac{n-2}{4}}+\zeta^{t-\frac{n+2}{4}}-\zeta^{t-\frac{n+10}{4}}-2\zeta^{t}+2\zeta^{t-1}+2\zeta^{2t-1}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$ $\displaystyle
2\zeta^{2t-1}+\zeta^{t+\frac{n+6}{4}}-\zeta^{t+\frac{n-2}{4}}-2\zeta^{t}+2\zeta^{t-1}+\zeta^{t-\frac{n+2}{4}}-\zeta^{t-\frac{n+10}{4}}-2$
$\displaystyle=0.$

Now, if we define $\psi$ to be one of the two possible square roots of
$\zeta$, i.e. a complex number such that $\psi^{2}=\zeta$, then it is easy to
see that the condition $P(\zeta)=0$ becomes equivalent to

$2\psi^{4t-2}+\psi^{2t+3+\frac{n}{2}}-\psi^{2t-1+\frac{n}{2}}-2\psi^{2t}+2\psi^{2t-2}+\psi^{2t-1-\frac{n}{2}}-\psi^{2t-5-\frac{n}{2}}-2=0.$
(45)

Taking into consideration that the condition $\zeta^{\frac{n}{2}}=1$
translates to $\psi^{n}=1$, it becomes clear that in order to prove that
$P(\zeta)\neq 0$ for any $n$-th root of unity $\zeta$ such that $\zeta\neq
1,-1$ and $\zeta^{\frac{n}{2}}=1$, it is enough to show that Eq. (45) does not
hold for any $n$-th root of unity $\psi$ such that
$\psi\notin\\{1,-1,i,-i\\}$. Since $i$ and $-i$ are not $n$-th roots of unity
to begin with, due to $n\equiv_{4}2$, it suffices to prove that Eq. (45) has
no $n$-th roots of unity among its roots, besides potentially $1$ and $-1$.

We now divide the case into two subcases, depending on whether
$\psi^{\frac{n}{2}}$ is equal to $1$ or $-1$.

_Subcase $\psi^{\frac{n}{2}}=1$_. Here, it is straightforward to deduct that
Eq. (45) is equivalent to

$\displaystyle
2\psi^{4t-2}+\psi^{2t+3}-\psi^{2t-1}-2\psi^{2t}+2\psi^{2t-2}+\psi^{2t-1}-\psi^{2t-5}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$ $\displaystyle
2\psi^{4t-2}+\psi^{2t+3}-2\psi^{2t}+2\psi^{2t-2}-\psi^{2t-5}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$ $\displaystyle
2\psi^{4t-1}+\psi^{2t+4}-2\psi^{2t+1}+2\psi^{2t-1}-\psi^{2t-4}-2\psi$
$\displaystyle=0.$

Now, suppose that Eq. (45) does hold for some $n$-th root of unity $\psi$
different from $1$ and $-1$. It is clear that $\psi$ must be a primitive
$b$-th root of unity for some $b\neq 1,2$, since $\psi\neq 1,-1$. Also, due to
the fact that $b\mid n$ and $n\equiv_{4}2$, we conclude that $b\neq 4,8$.
However, Eq. (45) directly implies that $\psi$ is a root of the polynomial
$U_{t}(x)$. Hence, we get that $U_{t}(x)$ is divisible by a cyclotomic
polynomial $\Phi_{b}(x)$ such that $b\neq 1,2,4,8$, which is not possible
according to Lemma 18, thus yielding a contradiction.

_Subcase $\psi^{\frac{n}{2}}=-1$_. In this subcase, Eq. (45) quickly becomes
equivalent to

$\displaystyle
2\psi^{4t-2}-\psi^{2t+3}+\psi^{2t-1}-2\psi^{2t}+2\psi^{2t-2}-\psi^{2t-1}+\psi^{2t-5}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$ $\displaystyle
2\psi^{4t-2}-\psi^{2t+3}-2\psi^{2t}+2\psi^{2t-2}+\psi^{2t-5}-2$
$\displaystyle=0$ $\displaystyle\iff\quad$ $\displaystyle
2\psi^{4t-1}-\psi^{2t+4}-2\psi^{2t+1}+2\psi^{2t-1}+\psi^{2t-4}-2\psi$
$\displaystyle=0.$

If we suppose that Eq. (45) is true for some $n$-th root of unity $\psi$
different from $1$ and $-1$, we can use the same logic implemented in the
previous subcase in order to immediately obtain that $\psi$ has to be a
primitive $b$-th root of unity for some $b\notin\\{1,2,4,8\\}$. However, Eq.
(45) implies that $\psi$ is a root of the polynomial $W_{t}(x)$, which further
means that this polynomial has to be divisible by a cyclotomic polynomial
$\Phi_{b}(x)$ such that $b\notin\\{1,2,4,8\\}$. By virtue of Lemma 18, this is
impossible, which completes the proof. ∎

##  5 Conclusion

In conclusion, Theorems 6 and 12 provide a construction for any $4t$-regular
circulant nut graph of order $n$, whenever

  * •

$t$ is odd and $n\geq 4t+4$;

  * •

$t$ is even and $n\geq 4t+6$ and such that $n\equiv_{4}2$.

For the odd values of $t$, these two theorems provide a way to construct a
$4t$-regular circulant nut graph of every possible order, thereby fully
resolving the circulant nut graph order–degree existence problem. On the other
hand, for the even values of $t$, Theorem 18 shows that there exists a
$4t$-regular circulant nut graph of each order $n\geq 4t+6$ such that
$n\equiv_{4}2$, without covering the case when $4\mid n$.

Damnjanović and Stevanović [3, Proposition 19] have shown that an interesting
irregularity exists for the case $t=2$. Moreover, there does not exist an
$8$-regular circulant nut graph of order $16$. In fact, the set of all the
values $n$ such that there exists an $8$-regular circulant nut graph of order
$n$ is given by the expression $\\{14\\}\cup\\{18,20,22,24,26,\ldots\\}$.

Despite the irregularity that occurs for $t=2$, the experimental results
obtained in [3] dictate that for each even integer $t$ such that $4\leq t\leq
1300$ there does exist a $4t$-regular circulant nut graph of order $n$ for
each even $n\geq 4t+6$. Bearing this mind, we end the paper with the following
conjecture.

######  Conjecture 19.

For each even $t\geq 4$ and each $n\geq 4t+8$ divisible by four, there exists
a $4t$-regular circulant nut graph of order $n$.

## References

  * [1] I. Sciriha,  _On the construction of graphs of nullity one_ ,  Discrete Math. 181(1–3) (1998) 193–211
  * [2] N. Bašić, M. Knor, R. Škrekovski,  _On $12$-regular nut graphs_,  Art Discret. Appl. Math. 5(2) (2021) #P2.01
  * [3] I. Damnjanović, D. Stevanović,  _On circulant nut graphs_ ,  Linear Algebra Appl. 633 (2022) 127–151
  * [4] R. M. Gray,  _Toeplitz and circulant matrices: A review_ ,  Found. Trends Commun. Inf. Theory 2(3) (2006) 155–239
  * [5] _Cyclotomic polynomials_ ,  Encyclopedia of Mathematics,
encyclopediaofmath.org/index.php?title=Cyclotomic_polynomials

  * [6] M. Filaseta, A. Schinzel,  _On testing the divisibility of lacunary polynomials by cyclotomic polynomials_ ,  Math. Comput. 73(246) (2003) 957–965
  * [7] T. Nagell,  _Introduction to Number Theory_ ,  Wiley, New York (1951)

##  Appendix A $Q_{t}^{\bmod b}(x)\bmod{\Phi_{b}(x)}$ table

$t\bmod 3$ | $Q_{t}^{\bmod 3}(x)$ | $Q_{t}^{\bmod 3}(x)\bmod{\Phi_{3}(x)}$
---|---|---
$0$ | $-3+3x^{2}$ | $-6-3x$
$1$ | $-1+x$ | $-1+x$
$2$ | $x-x^{2}$ | $1+2x$
$t\bmod 5$ | $Q_{t}^{\bmod 5}(x)$ | $Q_{t}^{\bmod 5}(x)\bmod{\Phi_{5}(x)}$
$0$ | $-3+x-x^{3}+3x^{4}$ | $-6-2x-3x^{2}-4x^{3}$
$1$ | $-1+x+x^{2}-x^{4}$ | $2x+2x^{2}+x^{3}$
$2$ | $-3+x-x^{2}+3x^{3}$ | $-3+x-x^{2}+3x^{3}$
$3$ | $-x+x^{2}-x^{3}+x^{4}$ | $-1-2x-2x^{3}$
$4$ | $-1+x^{2}+x^{3}-x^{4}$ | $x+2x^{2}+2x^{3}$
$t\bmod 6$ | $Q_{t}^{\bmod 6}(x)$ | $Q_{t}^{\bmod 6}(x)\bmod{\Phi_{6}(x)}$
$0$ | $-3+x-x^{4}+3x^{5}$ | $-x$
$1$ | $-1+x+x^{2}-x^{5}$ | $-3+3x$
$2$ | $-3+x-x^{2}+3x^{3}$ | $-5$
$3$ | $-2-x+x^{2}-x^{3}+x^{4}+2x^{5}$ | $-3x$
$4$ | $-2+2x-x^{2}+x^{3}-x^{4}+x^{5}$ | $-1+x$
$5$ | $-1+x^{3}+x^{4}-x^{5}$ | $-3$
$t\bmod 10$ | $Q_{t}^{\bmod 10}(x)$ | $Q_{t}^{\bmod 10}(x)\bmod{\Phi_{10}(x)}$
$0$ | $-3+x-x^{8}+3x^{9}$ | $-2x+3x^{2}-2x^{3}$
$1$ | $-1+x+x^{2}-x^{9}$ | $-2+2x+x^{3}$
$2$ | $-3+x-x^{2}+3x^{3}$ | $-3+x-x^{2}+3x^{3}$
$3$ | $-2-x+x^{2}-x^{3}+x^{4}+2x^{5}$ | $-5$
$4$ | $-2-x^{2}+x^{3}-x^{4}+x^{5}+2x^{7}$ | $-2-x-2x^{2}$
$5$ | $-2-x^{3}+x^{4}-x^{5}+x^{6}+2x^{9}$ | $-2x+x^{2}-2x^{3}$
$6$ | $-2+2x-x^{4}+x^{5}-x^{6}+x^{7}$ | $-2+2x-x^{3}$
$7$ | $-2+2x^{3}-x^{5}+x^{6}-x^{7}+x^{8}$ | $-1-x+x^{2}+x^{3}$
$8$ | $-2+2x^{5}-x^{6}+x^{7}-x^{8}+x^{9}$ | $-3$
$9$ | $-1+x^{7}+x^{8}-x^{9}$ | $-2+x-2x^{2}$
$t\bmod 15$ | $Q_{t}^{\bmod 15}(x)$ | $Q_{t}^{\bmod 15}(x)\bmod{\Phi_{15}(x)}$
$0$ | $-3+x-x^{13}+3x^{14}$ | $-1+2x-3x^{2}+3x^{3}-2x^{4}-x^{5}+3x^{6}-2x^{7}$
$1$ | $-1+x+x^{2}-x^{14}$ | $-2+x+2x^{2}-x^{3}+x^{4}-x^{6}+x^{7}$
$2$ | $-3+x-x^{2}+3x^{3}$ | $-3+x-x^{2}+3x^{3}$
$3$ | $-2-x+x^{2}-x^{3}+x^{4}+2x^{5}$ | $-2-x+x^{2}-x^{3}+x^{4}+2x^{5}$
$4$ | $-2-x^{2}+x^{3}-x^{4}+x^{5}+2x^{7}$ | $-2-x^{2}+x^{3}-x^{4}+x^{5}+2x^{7}$
$5$ | $-2-x^{3}+x^{4}-x^{5}+x^{6}+2x^{9}$ | $-4+2x^{2}-3x^{3}+x^{4}-x^{5}-x^{6}+2x^{7}$
$6$ | $-2-x^{4}+x^{5}-x^{6}+x^{7}+2x^{11}$ | $-2-2x-x^{4}+x^{5}-3x^{6}+x^{7}$
$7$ | $-2-x^{5}+x^{6}-x^{7}+x^{8}+2x^{13}$ | $-1-x-x^{3}-x^{4}+x^{6}-2x^{7}$
$8$ | $-x^{6}+x^{7}-x^{8}+x^{9}$ | $-x+x^{2}-x^{4}+x^{5}-2x^{6}+x^{7}$
$9$ | $-2+2x^{2}-x^{7}+x^{8}-x^{9}+x^{10}$ | $-3+x+x^{2}+x^{4}-2x^{5}+x^{6}-x^{7}$
$10$ | $-2+2x^{4}-x^{8}+x^{9}-x^{10}+x^{11}$ | $-1-2x+x^{2}+x^{4}+2x^{5}-2x^{6}$
$11$ | $-2+2x^{6}-x^{9}+x^{10}-x^{11}+x^{12}$ | $-2+x-2x^{2}+x^{3}-x^{5}+4x^{6}-2x^{7}$
$12$ | $-2+2x^{8}-x^{10}+x^{11}-x^{12}+x^{13}$ | $-2+x^{2}-2x^{3}+x^{4}-x^{6}+2x^{7}$
$13$ | $-2+2x^{10}-x^{11}+x^{12}-x^{13}+x^{14}$ | $-4+2x-2x^{2}+x^{3}-3x^{5}+2x^{6}-x^{7}$
$14$ | $-1+x^{12}+x^{13}-x^{14}$ | $-1-x-x^{3}+x^{5}-x^{6}-x^{7}$
$t\bmod 30$ | $Q_{t}^{\bmod 30}(x)$ | $Q_{t}^{\bmod 30}(x)\bmod{\Phi_{30}(x)}$
$0$ | $-3+x-x^{28}+3x^{29}$ | $-7+3x^{2}+3x^{3}+4x^{4}+x^{5}-3x^{6}-4x^{7}$
$1$ | $-1+x+x^{2}-x^{29}$ | $x-x^{3}-x^{4}+x^{6}+x^{7}$
$2$ | $-3+x-x^{2}+3x^{3}$ | $-3+x-x^{2}+3x^{3}$
$3$ | $-2-x+x^{2}-x^{3}+x^{4}+2x^{5}$ | $-2-x+x^{2}-x^{3}+x^{4}+2x^{5}$
$4$ | $-2-x^{2}+x^{3}-x^{4}+x^{5}+2x^{7}$ | $-2-x^{2}+x^{3}-x^{4}+x^{5}+2x^{7}$
$5$ | $-2-x^{3}+x^{4}-x^{5}+x^{6}+2x^{9}$ | $-2x^{2}-3x^{3}+x^{4}-x^{5}+3x^{6}+2x^{7}$
$6$ | $-2-x^{4}+x^{5}-x^{6}+x^{7}+2x^{11}$ | $-2-2x-x^{4}+x^{5}+x^{6}+x^{7}$
$7$ | $-2-x^{5}+x^{6}-x^{7}+x^{8}+2x^{13}$ | $-5-3x+x^{3}+3x^{4}+2x^{5}+x^{6}-4x^{7}$
$8$ | $-2-x^{6}+x^{7}-x^{8}+x^{9}+2x^{15}$ | $-2+x-x^{2}-2x^{3}-x^{4}-x^{5}+3x^{7}$
$9$ | $-2-x^{7}+x^{8}-x^{9}+x^{10}+2x^{17}$ | $-5-x-x^{2}+2x^{3}+x^{4}+2x^{5}-x^{6}-3x^{7}$
$10$ | $-2-x^{8}+x^{9}-x^{10}+x^{11}+2x^{19}$ | $1-x^{2}-2x^{3}-3x^{4}-2x^{5}+2x^{6}+2x^{7}$
$11$ | $-2-x^{9}+x^{10}-x^{11}+x^{12}+2x^{21}$ | $-4+x+x^{3}+x^{5}-4x^{6}$
$12$ | $-2-x^{10}+x^{11}-x^{12}+x^{13}+2x^{23}$ | $x^{2}-2x^{3}-x^{4}-2x^{5}+x^{6}$
$13$ | $-2-x^{11}+x^{12}-x^{13}+x^{14}+2x^{25}$ | $2+2x-2x^{2}-x^{3}-2x^{4}-3x^{5}+3x^{7}$
$14$ | $-2-x^{12}+x^{13}-x^{14}+x^{15}+2x^{27}$ | $-5-x+4x^{2}+x^{3}+2x^{4}+x^{5}-x^{6}-5x^{7}$
$15$ | $-2-x^{13}+x^{14}-x^{15}+x^{16}+2x^{29}$ | $-1+x^{2}+x^{3}-x^{5}-x^{6}$
$16$ | $-2+2x-x^{14}+x^{15}-x^{16}+x^{17}$ | $-4+3x+x^{3}+x^{4}-x^{6}-x^{7}$
$17$ | $-2+2x^{3}-x^{15}+x^{16}-x^{17}+x^{18}$ | $-1-x+x^{2}+x^{3}$
$18$ | $-2+2x^{5}-x^{16}+x^{17}-x^{18}+x^{19}$ | $-2+x-x^{2}+x^{3}-x^{4}+2x^{5}$
$19$ | $-2+2x^{7}-x^{17}+x^{18}-x^{19}+x^{20}$ | $-2+x^{2}-x^{3}+x^{4}-x^{5}+2x^{7}$
$20$ | $-2+2x^{9}-x^{18}+x^{19}-x^{20}+x^{21}$ | $-2x^{2}-x^{3}-x^{4}+x^{5}+x^{6}+2x^{7}$
$21$ | $-2+2x^{11}-x^{19}+x^{20}-x^{21}+x^{22}$ | $-2-2x+x^{4}-x^{5}+3x^{6}-x^{7}$
$22$ | $-2+2x^{13}-x^{20}+x^{21}-x^{22}+x^{23}$ | $-3-x-x^{3}+x^{4}+2x^{5}-x^{6}$
$23$ | $-2+2x^{15}-x^{21}+x^{22}-x^{23}+x^{24}$ | $-6-x+x^{2}+2x^{3}+x^{4}+x^{5}-3x^{7}$
$24$ | $-2+2x^{17}-x^{22}+x^{23}-x^{24}+x^{25}$ | $1+x-3x^{2}-2x^{3}-x^{4}-2x^{5}+x^{6}+3x^{7}$
$25$ | $-2+2x^{19}-x^{23}+x^{24}-x^{25}+x^{26}$ | $-5+x^{2}+2x^{3}-x^{4}+2x^{5}-2x^{6}-2x^{7}$
$26$ | $-2+2x^{21}-x^{24}+x^{25}-x^{26}+x^{27}$ | $-x-x^{3}-x^{5}$
$27$ | $-2+2x^{23}-x^{25}+x^{26}-x^{27}+x^{28}$ | $4x-x^{2}-2x^{3}-3x^{4}-2x^{5}-x^{6}+4x^{7}$
$28$ | $-2+2x^{25}-x^{26}+x^{27}-x^{28}+x^{29}$ | $-2-2x+2x^{2}+x^{3}+2x^{4}-x^{5}-3x^{7}$
$29$ | $-1+x^{27}+x^{28}-x^{29}$ | $1+x-x^{3}-2x^{4}-x^{5}+x^{6}+x^{7}$

##  Appendix B $R_{t}^{\bmod b}(x)\bmod{\Phi_{b}(x)}$ table

$t\bmod 3$ | $R_{t}^{\bmod 3}(x)$ | $R_{t}^{\bmod 3}(x)\bmod{\Phi_{3}(x)}$
---|---|---
$0$ | $-5+5x^{2}$ | $-10-5x$
$1$ | $1-x$ | $1-x$
$2$ | $3x-3x^{2}$ | $3+6x$
$t\bmod 5$ | $R_{t}^{\bmod 5}(x)$ | $R_{t}^{\bmod 5}(x)\bmod{\Phi_{5}(x)}$
$0$ | $-5-x+x^{3}+5x^{4}$ | $-10-6x-5x^{2}-4x^{3}$
$1$ | $1-x-x^{2}+x^{4}$ | $-2x-2x^{2}-x^{3}$
$2$ | $-1+3x-3x^{2}+x^{3}$ | $-1+3x-3x^{2}+x^{3}$
$3$ | $x+3x^{2}-3x^{3}-x^{4}$ | $1+2x+4x^{2}-2x^{3}$
$4$ | $-3+3x^{2}+3x^{3}-3x^{4}$ | $3x+6x^{2}+6x^{3}$
$t\bmod 6$ | $R_{t}^{\bmod 6}(x)$ | $R_{t}^{\bmod 6}(x)\bmod{\Phi_{6}(x)}$
$0$ | $-5-x+x^{4}+5x^{5}$ | $-7x$
$1$ | $1-x-x^{2}+x^{5}$ | $3-3x$
$2$ | $-1+3x-3x^{2}+x^{3}$ | $1$
$3$ | $-2+x+3x^{2}-3x^{3}-x^{4}+2x^{5}$ | $3x$
$4$ | $-2+2x+x^{2}+3x^{3}-3x^{4}-x^{5}$ | $-7+7x$
$5$ | $-3+3x^{3}+3x^{4}-3x^{5}$ | $-9$
$t\bmod 10$ | $R_{t}^{\bmod 10}(x)$ | $R_{t}^{\bmod 10}(x)\bmod{\Phi_{10}(x)}$
$0$ | $-5-x+x^{8}+5x^{9}$ | $-6x+5x^{2}-6x^{3}$
$1$ | $1-x-x^{2}+x^{9}$ | $2-2x-x^{3}$
$2$ | $-1+3x-3x^{2}+x^{3}$ | $-1+3x-3x^{2}+x^{3}$
$3$ | $-2+x+3x^{2}-3x^{3}-x^{4}+2x^{5}$ | $-3+4x^{2}-4x^{3}$
$4$ | $-2+x^{2}+3x^{3}-3x^{4}-x^{5}+2x^{7}$ | $2-3x+2x^{2}$
$5$ | $-2+x^{3}+3x^{4}-3x^{5}-x^{6}+2x^{9}$ | $2x-x^{2}+2x^{3}$
$6$ | $-2+2x+x^{4}+3x^{5}-3x^{6}-x^{7}$ | $-6+6x+x^{3}$
$7$ | $-2+2x^{3}+x^{5}+3x^{6}-3x^{7}-x^{8}$ | $-3-3x+3x^{2}+3x^{3}$
$8$ | $-2+2x^{5}+x^{6}+3x^{7}-3x^{8}-x^{9}$ | $-5-4x^{2}+4x^{3}$
$9$ | $-3+3x^{7}+3x^{8}-3x^{9}$ | $-6+3x-6x^{2}$
$t\bmod 15$ | $R_{t}^{\bmod 15}(x)$ | $R_{t}^{\bmod 15}(x)\bmod{\Phi_{15}(x)}$
$0$ | $-5-x+x^{13}+5x^{14}$ | $1-2x-5x^{2}+5x^{3}-6x^{4}+x^{5}+5x^{6}-6x^{7}$
$1$ | $1-x-x^{2}+x^{14}$ | $2-x-2x^{2}+x^{3}-x^{4}+x^{6}-x^{7}$
$2$ | $-1+3x-3x^{2}+x^{3}$ | $-1+3x-3x^{2}+x^{3}$
$3$ | $-2+x+3x^{2}-3x^{3}-x^{4}+2x^{5}$ | $-2+x+3x^{2}-3x^{3}-x^{4}+2x^{5}$
$4$ | $-2+x^{2}+3x^{3}-3x^{4}-x^{5}+2x^{7}$ | $-2+x^{2}+3x^{3}-3x^{4}-x^{5}+2x^{7}$
$5$ | $-2+x^{3}+3x^{4}-3x^{5}-x^{6}+2x^{9}$ | $-4+2x^{2}-x^{3}+3x^{4}-3x^{5}-3x^{6}+2x^{7}$
$6$ | $-2+x^{4}+3x^{5}-3x^{6}-x^{7}+2x^{11}$ | $-2-2x+x^{4}+3x^{5}-5x^{6}-x^{7}$
$7$ | $-2+x^{5}+3x^{6}-3x^{7}-x^{8}+2x^{13}$ | $1-3x+x^{3}-3x^{4}+4x^{5}+3x^{6}-6x^{7}$
$8$ | $x^{6}+3x^{7}-3x^{8}-x^{9}$ | $4-3x-x^{2}+4x^{3}-3x^{4}+3x^{5}+2x^{6}-x^{7}$
$9$ | $-2+2x^{2}+x^{7}+3x^{8}-3x^{9}-x^{10}$ | $-1+3x-x^{2}+3x^{4}-2x^{5}+3x^{6}+x^{7}$
$10$ | $-2+2x^{4}+x^{8}+3x^{9}-3x^{10}-x^{11}$ | $-3+2x+3x^{2}-4x^{3}+3x^{4}+2x^{5}-2x^{6}+4x^{7}$
$11$ | $-2+2x^{6}+x^{9}+3x^{10}-3x^{11}-x^{12}$ | $-6+3x+2x^{2}-x^{3}-3x^{5}+4x^{6}+2x^{7}$
$12$ | $-2+2x^{8}+x^{10}+3x^{11}-3x^{12}-x^{13}$ | $-6+3x^{2}-2x^{3}+3x^{4}-4x^{5}-3x^{6}+6x^{7}$
$13$ | $-2+2x^{10}+x^{11}+3x^{12}-3x^{13}-x^{14}$ | $-8+2x-2x^{2}-x^{3}+4x^{4}-5x^{5}-2x^{6}+x^{7}$
$14$ | $-3+3x^{12}+3x^{13}-3x^{14}$ | $-3-3x-3x^{3}+3x^{5}-3x^{6}-3x^{7}$
$t\bmod 30$ | $R_{t}^{\bmod 30}(x)$ | $R_{t}^{\bmod 30}(x)\bmod{\Phi_{30}(x)}$
$0$ | $-5-x+x^{28}+5x^{29}$ | $-9+5x^{2}+5x^{3}+4x^{4}-x^{5}-5x^{6}-4x^{7}$
$1$ | $1-x-x^{2}+x^{29}$ | $-x+x^{3}+x^{4}-x^{6}-x^{7}$
$2$ | $-1+3x-3x^{2}+x^{3}$ | $-1+3x-3x^{2}+x^{3}$
$3$ | $-2+x+3x^{2}-3x^{3}-x^{4}+2x^{5}$ | $-2+x+3x^{2}-3x^{3}-x^{4}+2x^{5}$
$4$ | $-2+x^{2}+3x^{3}-3x^{4}-x^{5}+2x^{7}$ | $-2+x^{2}+3x^{3}-3x^{4}-x^{5}+2x^{7}$
$5$ | $-2+x^{3}+3x^{4}-3x^{5}-x^{6}+2x^{9}$ | $-2x^{2}-x^{3}+3x^{4}-3x^{5}+x^{6}+2x^{7}$
$6$ | $-2+x^{4}+3x^{5}-3x^{6}-x^{7}+2x^{11}$ | $-2-2x+x^{4}+3x^{5}-x^{6}-x^{7}$
$7$ | $-2+x^{5}+3x^{6}-3x^{7}-x^{8}+2x^{13}$ | $-3-x-x^{3}+x^{4}+2x^{5}+3x^{6}-4x^{7}$
$8$ | $-2+x^{6}+3x^{7}-3x^{8}-x^{9}+2x^{15}$ | $-2+3x+x^{2}-2x^{3}-3x^{4}-3x^{5}+5x^{7}$
$9$ | $-2+x^{7}+3x^{8}-3x^{9}-x^{10}+2x^{17}$ | $-7-3x+x^{2}+6x^{3}+3x^{4}+2x^{5}-3x^{6}-5x^{7}$
$10$ | $-2+x^{8}+3x^{9}-3x^{10}-x^{11}+2x^{19}$ | $3-3x^{2}-2x^{3}-x^{4}-2x^{5}+2x^{6}+2x^{7}$
$11$ | $-2+x^{9}+3x^{10}-3x^{11}-x^{12}+2x^{21}$ | $-4+3x-x^{3}+3x^{5}-4x^{6}$
$12$ | $-2+x^{10}+3x^{11}-3x^{12}-x^{13}+2x^{23}$ | $3x^{2}-2x^{3}-3x^{4}-2x^{5}+3x^{6}$
$13$ | $-2+x^{11}+3x^{12}-3x^{13}-x^{14}+2x^{25}$ | $2+2x-2x^{2}+x^{3}-2x^{4}-5x^{5}+5x^{7}$
$14$ | $-2+x^{12}+3x^{13}-3x^{14}-x^{15}+2x^{27}$ | $-7-3x+4x^{2}+3x^{3}+6x^{4}+3x^{5}-3x^{6}-7x^{7}$
$15$ | $-2+x^{13}+3x^{14}-3x^{15}-x^{16}+2x^{29}$ | $1-x^{2}-x^{3}+x^{5}+x^{6}$
$16$ | $-2+2x+x^{14}+3x^{15}-3x^{16}-x^{17}$ | $-4+5x-x^{3}-x^{4}+x^{6}+x^{7}$
$17$ | $-2+2x^{3}+x^{15}+3x^{16}-3x^{17}-x^{18}$ | $-3-3x+3x^{2}+3x^{3}$
$18$ | $-2+2x^{5}+x^{16}+3x^{17}-3x^{18}-x^{19}$ | $-2-x-3x^{2}+3x^{3}+x^{4}+2x^{5}$
$19$ | $-2+2x^{7}+x^{17}+3x^{18}-3x^{19}-x^{20}$ | $-2-x^{2}-3x^{3}+3x^{4}+x^{5}+2x^{7}$
$20$ | $-2+2x^{9}+x^{18}+3x^{19}-3x^{20}-x^{21}$ | $-2x^{2}-3x^{3}-3x^{4}+3x^{5}+3x^{6}+2x^{7}$
$21$ | $-2+2x^{11}+x^{19}+3x^{20}-3x^{21}-x^{22}$ | $-2-2x-x^{4}-3x^{5}+5x^{6}+x^{7}$
$22$ | $-2+2x^{13}+x^{20}+3x^{21}-3x^{22}-x^{23}$ | $-5-3x+x^{3}+3x^{4}+2x^{5}-3x^{6}$
$23$ | $-2+2x^{15}+x^{21}+3x^{22}-3x^{23}-x^{24}$ | $-6-3x-x^{2}+2x^{3}+3x^{4}+3x^{5}-5x^{7}$
$24$ | $-2+2x^{17}+x^{22}+3x^{23}-3x^{24}-x^{25}$ | $3+3x-5x^{2}-6x^{3}-3x^{4}-2x^{5}+3x^{6}+5x^{7}$
$25$ | $-2+2x^{19}+x^{23}+3x^{24}-3x^{25}-x^{26}$ | $-7+3x^{2}+2x^{3}-3x^{4}+2x^{5}-2x^{6}-2x^{7}$
$26$ | $-2+2x^{21}+x^{24}+3x^{25}-3x^{26}-x^{27}$ | $-3x+x^{3}-3x^{5}$
$27$ | $-2+2x^{23}+x^{25}+3x^{26}-3x^{27}-x^{28}$ | $4x-3x^{2}-2x^{3}-x^{4}-2x^{5}-3x^{6}+4x^{7}$
$28$ | $-2+2x^{25}+x^{26}+3x^{27}-3x^{28}-x^{29}$ | $-2-2x+2x^{2}-x^{3}+2x^{4}+x^{5}-5x^{7}$
$29$ | $-3+3x^{27}+3x^{28}-3x^{29}$ | $3+3x-3x^{3}-6x^{4}-3x^{5}+3x^{6}+3x^{7}$

##  Appendix C $U_{t}^{\bmod b}(x)\bmod{\Phi_{b}(x)}$ table

$t\bmod 3$ | $U_{t}^{\bmod 3}(x)$ | $U_{t}^{\bmod 3}(x)\bmod{\Phi_{3}(x)}$
---|---|---
$0$ | $-3x+3x^{2}$ | $-3-6x$
$1$ | $1-x$ | $1-x$
$2$ | $1-x^{2}$ | $2+x$
$t\bmod 5$ | $U_{t}^{\bmod 5}(x)$ | $U_{t}^{\bmod 5}(x)\bmod{\Phi_{5}(x)}$
$0$ | $-5x+5x^{4}$ | $-5-10x-5x^{2}-5x^{3}$
$1$ | $x-x^{3}$ | $x-x^{3}$
$2$ | $-3-2x+2x^{2}+3x^{3}$ | $-3-2x+2x^{2}+3x^{3}$
$3$ | $3-3x^{2}$ | $3-3x^{2}$
$4$ | $2-2x+3x^{2}-3x^{4}$ | $5+x+6x^{2}+3x^{3}$
$t\bmod 6$ | $U_{t}^{\bmod 6}(x)$ | $U_{t}^{\bmod 6}(x)\bmod{\Phi_{6}(x)}$
$0$ | $-4x-x^{2}+x^{4}+4x^{5}$ | $5-10x$
$1$ | $1-x^{4}$ | $1+x$
$2$ | $-1+x^{2}+2x^{3}-2x^{5}$ | $-6+3x$
$3$ | $-4x-x^{2}+x^{4}+4x^{5}$ | $5-10x$
$4$ | $1-x^{4}$ | $1+x$
$5$ | $-1+x^{2}+2x^{3}-2x^{5}$ | $-6+3x$
$t\bmod 10$ | $U_{t}^{\bmod 10}(x)$ | $U_{t}^{\bmod 10}(x)\bmod{\Phi_{10}(x)}$
$0$ | $-4x+x^{4}-x^{6}+4x^{9}$ | $3-6x+3x^{2}-3x^{3}$
$1$ | $x^{6}-x^{8}$ | $-x+x^{3}$
$2$ | $-1-2x+2x^{3}-2x^{5}+2x^{7}+x^{8}$ | $1-2x-2x^{2}+x^{3}$
$3$ | $1-x^{2}+2x^{5}-2x^{7}$ | $-1+x^{2}$
$4$ | $-2x+x^{2}-x^{4}+2x^{5}+2x^{7}-2x^{9}$ | $-3-x-2x^{2}+x^{3}$
$5$ | $-4x+x^{4}-x^{6}+4x^{9}$ | $3-6x+3x^{2}-3x^{3}$
$6$ | $x^{6}-x^{8}$ | $-x+x^{3}$
$7$ | $-1-2x+2x^{3}-2x^{5}+2x^{7}+x^{8}$ | $1-2x-2x^{2}+x^{3}$
$8$ | $1-x^{2}+2x^{5}-2x^{7}$ | $-1+x^{2}$
$9$ | $-2x+x^{2}-x^{4}+2x^{5}+2x^{7}-2x^{9}$ | $-3-x-2x^{2}+x^{3}$
$t\bmod 15$ | $U_{t}^{\bmod 15}(x)$ | $U_{t}^{\bmod 15}(x)\bmod{\Phi_{15}(x)}$
$0$ | $-4x+x^{4}-x^{11}+4x^{14}$ | $4-3x-4x^{2}+4x^{3}-3x^{4}+5x^{6}-4x^{7}$
$1$ | $x^{6}-x^{13}$ | $-1+x+x^{4}-x^{5}+x^{6}+x^{7}$
$2$ | $-1-2x+2x^{3}-2x^{5}+2x^{7}+x^{8}$ | $-2-x+x^{3}+x^{4}-3x^{5}+3x^{7}$
$3$ | $-2x-x^{2}+2x^{5}-2x^{7}+x^{10}+2x^{11}$ | $-1-4x-x^{2}+x^{5}-2x^{6}-2x^{7}$
$4$ | $2-2x-x^{4}+2x^{7}-2x^{9}+x^{12}$ | $4-2x-3x^{2}+2x^{3}-x^{4}+2x^{6}-x^{7}$
$5$ | $-2x+2x^{4}-x^{6}+2x^{9}-2x^{11}+x^{14}$ | $-1+x^{2}-x^{3}+x^{4}+x^{7}$
$6$ | $-x+x^{8}+2x^{11}-2x^{13}$ | $-3-x^{3}+3x^{4}-3x^{5}-2x^{6}+3x^{7}$
$7$ | $-2-2x+x^{3}-x^{10}+2x^{12}+2x^{13}$ | $1-4x-2x^{2}+x^{3}-2x^{4}+3x^{5}-4x^{7}$
$8$ | $2-2x^{2}+x^{5}-x^{12}$ | $2-x^{2}+x^{5}+x^{7}$
$9$ | $-2x+2x^{2}-2x^{4}+2x^{5}+x^{7}-x^{14}$ | $-1-2x+3x^{2}-x^{3}-x^{4}+2x^{5}-x^{6}+2x^{7}$
$10$ | $-3x+2x^{4}-2x^{6}+3x^{9}$ | $-3-3x+3x^{2}-3x^{3}+2x^{4}-5x^{6}+3x^{7}$
$11$ | $-2x-x^{3}+2x^{6}-2x^{8}+x^{11}+2x^{13}$ | $4-7x+x^{3}-4x^{4}+4x^{5}+x^{6}-4x^{7}$
$12$ | $-2x+2x^{2}-x^{5}+2x^{8}-2x^{10}+x^{13}$ | $1-x+2x^{2}-2x^{3}+x^{4}+x^{7}$
$13$ | $1-2x+2x^{6}-x^{7}+2x^{10}-2x^{12}$ | $-1-2x+2x^{2}-2x^{5}+2x^{6}+x^{7}$
$14$ | $-2x+x^{2}-x^{9}+2x^{10}+2x^{12}-2x^{14}$ | $-3-2x-x^{3}+2x^{4}-2x^{5}-x^{6}-x^{7}$
$t\bmod 30$ | $U_{t}^{\bmod 30}(x)$ | $U_{t}^{\bmod 30}(x)\bmod{\Phi_{30}(x)}$
$0$ | $-4x+x^{4}-x^{26}+4x^{29}$ | $-4-5x+4x^{2}+4x^{3}+5x^{4}-3x^{6}-4x^{7}$
$1$ | $x^{6}-x^{28}$ | $-1-x+x^{4}+x^{5}+x^{6}-x^{7}$
$2$ | $-1-2x+2x^{3}-2x^{5}+2x^{7}+x^{8}$ | $-2-3x+3x^{3}+x^{4}-x^{5}+x^{7}$
$3$ | $-2x-x^{2}+2x^{5}-2x^{7}+x^{10}+2x^{11}$ | $-1-4x-x^{2}+3x^{5}+2x^{6}-2x^{7}$
$4$ | $-2x-x^{4}+2x^{7}-2x^{9}+x^{12}+2x^{15}$ | $-4-2x+x^{2}+2x^{3}-x^{4}-2x^{6}+x^{7}$
$5$ | $-2x-x^{6}+2x^{9}-2x^{11}+x^{14}+2x^{19}$ | $3-3x^{2}-3x^{3}-3x^{4}+3x^{7}$
$6$ | $-2x-x^{8}+2x^{11}-2x^{13}+x^{16}+2x^{23}$ | $5-3x^{3}-5x^{4}-5x^{5}+2x^{6}+5x^{7}$
$7$ | $-2x-x^{10}+2x^{13}-2x^{15}+x^{18}+2x^{27}$ | $1-4x+2x^{2}-x^{3}+2x^{4}+x^{5}-4x^{7}$
$8$ | $-x^{12}+2x^{15}-2x^{17}+x^{20}$ | $-2+3x^{2}-x^{5}-x^{7}$
$9$ | $-2x+2x^{5}-x^{14}+2x^{17}-2x^{19}+x^{22}$ | $-1-2x-x^{2}+x^{3}+3x^{4}+2x^{5}-x^{6}-2x^{7}$
$10$ | $-2x+2x^{9}-x^{16}+2x^{19}-2x^{21}+x^{24}$ | $1-x-x^{2}-x^{3}-2x^{4}+3x^{6}+x^{7}$
$11$ | $-2x+2x^{13}-x^{18}+2x^{21}-2x^{23}+x^{26}$ | $-4-5x+3x^{3}+4x^{4}+4x^{5}-3x^{6}-4x^{7}$
$12$ | $-2x+2x^{17}-x^{20}+2x^{23}-2x^{25}+x^{28}$ | $1+x-2x^{2}-2x^{3}-3x^{4}+3x^{7}$
$13$ | $1-2x+2x^{21}-x^{22}+2x^{25}-2x^{27}$ | $3-2x-2x^{2}-2x^{5}-2x^{6}+3x^{7}$
$14$ | $-2x+x^{2}-x^{24}+2x^{25}+2x^{27}-2x^{29}$ | $5-2x-3x^{3}-2x^{4}-2x^{5}+3x^{6}+x^{7}$
$15$ | $-4x+x^{4}-x^{26}+4x^{29}$ | $-4-5x+4x^{2}+4x^{3}+5x^{4}-3x^{6}-4x^{7}$
$16$ | $x^{6}-x^{28}$ | $-1-x+x^{4}+x^{5}+x^{6}-x^{7}$
$17$ | $-1-2x+2x^{3}-2x^{5}+2x^{7}+x^{8}$ | $-2-3x+3x^{3}+x^{4}-x^{5}+x^{7}$
$18$ | $-2x-x^{2}+2x^{5}-2x^{7}+x^{10}+2x^{11}$ | $-1-4x-x^{2}+3x^{5}+2x^{6}-2x^{7}$
$19$ | $-2x-x^{4}+2x^{7}-2x^{9}+x^{12}+2x^{15}$ | $-4-2x+x^{2}+2x^{3}-x^{4}-2x^{6}+x^{7}$
$20$ | $-2x-x^{6}+2x^{9}-2x^{11}+x^{14}+2x^{19}$ | $3-3x^{2}-3x^{3}-3x^{4}+3x^{7}$
$21$ | $-2x-x^{8}+2x^{11}-2x^{13}+x^{16}+2x^{23}$ | $5-3x^{3}-5x^{4}-5x^{5}+2x^{6}+5x^{7}$
$22$ | $-2x-x^{10}+2x^{13}-2x^{15}+x^{18}+2x^{27}$ | $1-4x+2x^{2}-x^{3}+2x^{4}+x^{5}-4x^{7}$
$23$ | $-x^{12}+2x^{15}-2x^{17}+x^{20}$ | $-2+3x^{2}-x^{5}-x^{7}$
$24$ | $-2x+2x^{5}-x^{14}+2x^{17}-2x^{19}+x^{22}$ | $-1-2x-x^{2}+x^{3}+3x^{4}+2x^{5}-x^{6}-2x^{7}$
$25$ | $-2x+2x^{9}-x^{16}+2x^{19}-2x^{21}+x^{24}$ | $1-x-x^{2}-x^{3}-2x^{4}+3x^{6}+x^{7}$
$26$ | $-2x+2x^{13}-x^{18}+2x^{21}-2x^{23}+x^{26}$ | $-4-5x+3x^{3}+4x^{4}+4x^{5}-3x^{6}-4x^{7}$
$27$ | $-2x+2x^{17}-x^{20}+2x^{23}-2x^{25}+x^{28}$ | $1+x-2x^{2}-2x^{3}-3x^{4}+3x^{7}$
$28$ | $1-2x+2x^{21}-x^{22}+2x^{25}-2x^{27}$ | $3-2x-2x^{2}-2x^{5}-2x^{6}+3x^{7}$
$29$ | $-2x+x^{2}-x^{24}+2x^{25}+2x^{27}-2x^{29}$ | $5-2x-3x^{3}-2x^{4}-2x^{5}+3x^{6}+x^{7}$

##  Appendix D $W_{t}^{\bmod b}(x)\bmod{\Phi_{b}(x)}$ table

$t\bmod 3$ | $U_{t}^{\bmod 3}(x)$ | $U_{t}^{\bmod 3}(x)\bmod{\Phi_{3}(x)}$
---|---|---
$0$ | $-5x+5x^{2}$ | $-5-10x$
$1$ | $-1+x$ | $-1+x$
$2$ | $3-3x^{2}$ | $6+3x$
$t\bmod 5$ | $U_{t}^{\bmod 5}(x)$ | $U_{t}^{\bmod 5}(x)\bmod{\Phi_{5}(x)}$
$0$ | $-3x+3x^{4}$ | $-3-6x-3x^{2}-3x^{3}$
$1$ | $-x+x^{3}$ | $-x+x^{3}$
$2$ | $-1-2x+2x^{2}+x^{3}$ | $-1-2x+2x^{2}+x^{3}$
$3$ | $1-x^{2}$ | $1-x^{2}$
$4$ | $2-2x+x^{2}-x^{4}$ | $3-x+2x^{2}+x^{3}$
$t\bmod 6$ | $U_{t}^{\bmod 6}(x)$ | $U_{t}^{\bmod 6}(x)\bmod{\Phi_{6}(x)}$
$0$ | $-4x+x^{2}-x^{4}+4x^{5}$ | $3-6x$
$1$ | $-1+x^{4}$ | $-1-x$
$2$ | $1-x^{2}+2x^{3}-2x^{5}$ | $-2+x$
$3$ | $-4x+x^{2}-x^{4}+4x^{5}$ | $3-6x$
$4$ | $-1+x^{4}$ | $-1-x$
$5$ | $1-x^{2}+2x^{3}-2x^{5}$ | $-2+x$
$t\bmod 10$ | $U_{t}^{\bmod 10}(x)$ | $U_{t}^{\bmod 10}(x)\bmod{\Phi_{10}(x)}$
$0$ | $-4x-x^{4}+x^{6}+4x^{9}$ | $5-10x+5x^{2}-5x^{3}$
$1$ | $-x^{6}+x^{8}$ | $x-x^{3}$
$2$ | $1-2x+2x^{3}-2x^{5}+2x^{7}-x^{8}$ | $3-2x-2x^{2}+3x^{3}$
$3$ | $-1+x^{2}+2x^{5}-2x^{7}$ | $-3+3x^{2}$
$4$ | $-2x-x^{2}+x^{4}+2x^{5}+2x^{7}-2x^{9}$ | $-5+x-6x^{2}+3x^{3}$
$5$ | $-4x-x^{4}+x^{6}+4x^{9}$ | $5-10x+5x^{2}-5x^{3}$
$6$ | $-x^{6}+x^{8}$ | $x-x^{3}$
$7$ | $1-2x+2x^{3}-2x^{5}+2x^{7}-x^{8}$ | $3-2x-2x^{2}+3x^{3}$
$8$ | $-1+x^{2}+2x^{5}-2x^{7}$ | $-3+3x^{2}$
$9$ | $-2x-x^{2}+x^{4}+2x^{5}+2x^{7}-2x^{9}$ | $-5+x-6x^{2}+3x^{3}$
$t\bmod 15$ | $U_{t}^{\bmod 15}(x)$ | $U_{t}^{\bmod 15}(x)\bmod{\Phi_{15}(x)}$
$0$ | $-4x-x^{4}+x^{11}+4x^{14}$ | $4-5x-4x^{2}+4x^{3}-5x^{4}+3x^{6}-4x^{7}$
$1$ | $-x^{6}+x^{13}$ | $1-x-x^{4}+x^{5}-x^{6}-x^{7}$
$2$ | $1-2x+2x^{3}-2x^{5}+2x^{7}-x^{8}$ | $2-3x+3x^{3}-x^{4}-x^{5}+x^{7}$
$3$ | $-2x+x^{2}+2x^{5}-2x^{7}-x^{10}+2x^{11}$ | $1-4x+x^{2}+3x^{5}-2x^{6}-2x^{7}$
$4$ | $2-2x+x^{4}+2x^{7}-2x^{9}-x^{12}$ | $4-2x-x^{2}+2x^{3}+x^{4}+2x^{6}+x^{7}$
$5$ | $-2x+2x^{4}+x^{6}+2x^{9}-2x^{11}-x^{14}$ | $-3+3x^{2}-3x^{3}+3x^{4}+3x^{7}$
$6$ | $-3x+3x^{8}+2x^{11}-2x^{13}$ | $-5-3x^{3}+5x^{4}-5x^{5}-2x^{6}+5x^{7}$
$7$ | $-2-2x-x^{3}+x^{10}+2x^{12}+2x^{13}$ | $-1-4x-2x^{2}-x^{3}-2x^{4}+x^{5}-4x^{7}$
$8$ | $2-2x^{2}-x^{5}+x^{12}$ | $2-3x^{2}-x^{5}-x^{7}$
$9$ | $-2x+2x^{2}-2x^{4}+2x^{5}-x^{7}+x^{14}$ | $1-2x+x^{2}+x^{3}-3x^{4}+2x^{5}+x^{6}-2x^{7}$
$10$ | $-x+2x^{4}-2x^{6}+x^{9}$ | $-1-x+x^{2}-x^{3}+2x^{4}-3x^{6}+x^{7}$
$11$ | $-2x+x^{3}+2x^{6}-2x^{8}-x^{11}+2x^{13}$ | $4-5x+3x^{3}-4x^{4}+4x^{5}+3x^{6}-4x^{7}$
$12$ | $-2x+2x^{2}+x^{5}+2x^{8}-2x^{10}-x^{13}$ | $-1+x+2x^{2}-2x^{3}+3x^{4}+3x^{7}$
$13$ | $-1-2x+2x^{6}+x^{7}+2x^{10}-2x^{12}$ | $-3-2x+2x^{2}-2x^{5}+2x^{6}+3x^{7}$
$14$ | $-2x-x^{2}+x^{9}+2x^{10}+2x^{12}-2x^{14}$ | $-5-2x-3x^{3}+2x^{4}-2x^{5}-3x^{6}+x^{7}$
$t\bmod 30$ | $U_{t}^{\bmod 30}(x)$ | $U_{t}^{\bmod 30}(x)\bmod{\Phi_{30}(x)}$
$0$ | $-4x-x^{4}+x^{26}+4x^{29}$ | $-4-3x+4x^{2}+4x^{3}+3x^{4}-5x^{6}-4x^{7}$
$1$ | $-x^{6}+x^{28}$ | $1+x-x^{4}-x^{5}-x^{6}+x^{7}$
$2$ | $1-2x+2x^{3}-2x^{5}+2x^{7}-x^{8}$ | $2-x+x^{3}-x^{4}-3x^{5}+3x^{7}$
$3$ | $-2x+x^{2}+2x^{5}-2x^{7}-x^{10}+2x^{11}$ | $1-4x+x^{2}+x^{5}+2x^{6}-2x^{7}$
$4$ | $-2x+x^{4}+2x^{7}-2x^{9}-x^{12}+2x^{15}$ | $-4-2x+3x^{2}+2x^{3}+x^{4}-2x^{6}-x^{7}$
$5$ | $-2x+x^{6}+2x^{9}-2x^{11}-x^{14}+2x^{19}$ | $1-x^{2}-x^{3}-x^{4}+x^{7}$
$6$ | $-2x+x^{8}+2x^{11}-2x^{13}-x^{16}+2x^{23}$ | $3-x^{3}-3x^{4}-3x^{5}+2x^{6}+3x^{7}$
$7$ | $-2x+x^{10}+2x^{13}-2x^{15}-x^{18}+2x^{27}$ | $-1-4x+2x^{2}+x^{3}+2x^{4}+3x^{5}-4x^{7}$
$8$ | $x^{12}+2x^{15}-2x^{17}-x^{20}$ | $-2+x^{2}+x^{5}+x^{7}$
$9$ | $-2x+2x^{5}+x^{14}+2x^{17}-2x^{19}-x^{22}$ | $1-2x-3x^{2}-x^{3}+x^{4}+2x^{5}+x^{6}+2x^{7}$
$10$ | $-2x+2x^{9}+x^{16}+2x^{19}-2x^{21}-x^{24}$ | $3-3x-3x^{2}-3x^{3}-2x^{4}+5x^{6}+3x^{7}$
$11$ | $-2x+2x^{13}+x^{18}+2x^{21}-2x^{23}-x^{26}$ | $-4-7x+x^{3}+4x^{4}+4x^{5}-x^{6}-4x^{7}$
$12$ | $-2x+2x^{17}+x^{20}+2x^{23}-2x^{25}-x^{28}$ | $-1-x-2x^{2}-2x^{3}-x^{4}+x^{7}$
$13$ | $-1-2x+2x^{21}+x^{22}+2x^{25}-2x^{27}$ | $1-2x-2x^{2}-2x^{5}-2x^{6}+x^{7}$
$14$ | $-2x-x^{2}+x^{24}+2x^{25}+2x^{27}-2x^{29}$ | $3-2x-x^{3}-2x^{4}-2x^{5}+x^{6}-x^{7}$
$15$ | $-4x-x^{4}+x^{26}+4x^{29}$ | $-4-3x+4x^{2}+4x^{3}+3x^{4}-5x^{6}-4x^{7}$
$16$ | $-x^{6}+x^{28}$ | $1+x-x^{4}-x^{5}-x^{6}+x^{7}$
$17$ | $1-2x+2x^{3}-2x^{5}+2x^{7}-x^{8}$ | $2-x+x^{3}-x^{4}-3x^{5}+3x^{7}$
$18$ | $-2x+x^{2}+2x^{5}-2x^{7}-x^{10}+2x^{11}$ | $1-4x+x^{2}+x^{5}+2x^{6}-2x^{7}$
$19$ | $-2x+x^{4}+2x^{7}-2x^{9}-x^{12}+2x^{15}$ | $-4-2x+3x^{2}+2x^{3}+x^{4}-2x^{6}-x^{7}$
$20$ | $-2x+x^{6}+2x^{9}-2x^{11}-x^{14}+2x^{19}$ | $1-x^{2}-x^{3}-x^{4}+x^{7}$
$21$ | $-2x+x^{8}+2x^{11}-2x^{13}-x^{16}+2x^{23}$ | $3-x^{3}-3x^{4}-3x^{5}+2x^{6}+3x^{7}$
$22$ | $-2x+x^{10}+2x^{13}-2x^{15}-x^{18}+2x^{27}$ | $-1-4x+2x^{2}+x^{3}+2x^{4}+3x^{5}-4x^{7}$
$23$ | $x^{12}+2x^{15}-2x^{17}-x^{20}$ | $-2+x^{2}+x^{5}+x^{7}$
$24$ | $-2x+2x^{5}+x^{14}+2x^{17}-2x^{19}-x^{22}$ | $1-2x-3x^{2}-x^{3}+x^{4}+2x^{5}+x^{6}+2x^{7}$
$25$ | $-2x+2x^{9}+x^{16}+2x^{19}-2x^{21}-x^{24}$ | $3-3x-3x^{2}-3x^{3}-2x^{4}+5x^{6}+3x^{7}$
$26$ | $-2x+2x^{13}+x^{18}+2x^{21}-2x^{23}-x^{26}$ | $-4-7x+x^{3}+4x^{4}+4x^{5}-x^{6}-4x^{7}$
$27$ | $-2x+2x^{17}+x^{20}+2x^{23}-2x^{25}-x^{28}$ | $-1-x-2x^{2}-2x^{3}-x^{4}+x^{7}$
$28$ | $-1-2x+2x^{21}+x^{22}+2x^{25}-2x^{27}$ | $1-2x-2x^{2}-2x^{5}-2x^{6}+x^{7}$
$29$ | $-2x-x^{2}+x^{24}+2x^{25}+2x^{27}-2x^{29}$ | $3-2x-x^{3}-2x^{4}-2x^{5}+x^{6}-x^{7}$

##  Appendix E Roots of certain polynomials

In this appendix section, we will prove that some required polynomials truly
do not possess any root that is a root of unity as well, as claimed multiple
times throughout Section 4. The polynomials of interest shall be the four
following ones:

$\displaystyle Z_{1}(x)$ $\displaystyle=2x^{10}+x^{5}+2,$ $\displaystyle
Z_{2}(x)$ $\displaystyle=2x^{10}-x^{5}+2,$ $\displaystyle Z_{3}(x)$
$\displaystyle=2x^{6}+x^{3}+2,$ $\displaystyle Z_{4}(x)$
$\displaystyle=2x^{6}-x^{3}+2.$

First and foremost, let us define the next two additional polynomials:

$\displaystyle Z^{\prime}(x)$ $\displaystyle=2x^{2}+x+2,$ $\displaystyle
Z^{\prime\prime}(x)$ $\displaystyle=2x^{2}-x+2.$

It is clear that the roots of $Z_{1}(x)$ are actually the fifth roots of the
roots of $Z^{\prime}(x)$, while the roots of $Z_{2}(x)$ are the fifth roots of
the roots of $Z^{\prime\prime}(x)$. Similarly, the roots of $Z_{3}(x)$
represent the third roots of the roots of $Z^{\prime}(x)$, while the roots of
$Z_{4}(x)$ represent the third roots of the roots of $Z^{\prime\prime}(x)$.
Thus, in order to prove that neither of the four polynomials
$Z_{1}(x),Z_{2}(x),Z_{3}(x),Z_{4}(x)$ contains a root that is a root of unity,
it is sufficient to show that neither of the two polynomials
$Z^{\prime}(x),Z^{\prime\prime}(x)$ has such a root.

Now, if the polynomial $Z^{\prime}(x)$ were to have a root that is a root of
unity, then this root would surely represent a primitive $b$-th root of unity
for some $b\in\mathbb{N}$, which would imply that $\Phi_{b}(x)\mid
Z^{\prime}(x)$ must hold. However, it is simple to show that the polynomial
$Z^{\prime}(x)$ is not divisible by any cyclotomic polynomial. The same logic
can be applied to the $Z^{\prime\prime}(x)$ polynomial.

It is clear that neither $Z^{\prime}(x)$ nor $Z^{\prime\prime}(x)$ can be
divisible by a cyclotomic polynomial whose degree is greater than two.
However, given the fact that $\deg\Phi_{b}=\varphi(b)$ for each
$b\in\mathbb{N}$, where $\varphi$ represents Euler’s totient function, it is
easy to deduct that only five cyclotomic polynomials have a degree that is not
greater than two:

$\displaystyle\Phi_{1}(x)$ $\displaystyle=x-1,$ $\displaystyle\Phi_{2}(x)$
$\displaystyle=x+1,$ $\displaystyle\Phi_{3}(x)$ $\displaystyle=x^{2}+x+1,$
$\displaystyle\Phi_{4}(x)$ $\displaystyle=x^{2}+1,$ $\displaystyle\Phi_{6}(x)$
$\displaystyle=x^{2}-x+1.$

It is trivial to check that neither $Z^{\prime}(x)$ nor $Z^{\prime\prime}(x)$
is divisible by any of these five polynomials, which completes the proof. ∎