ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P4.03
https://doi.org/10.26493/1855-3974.3009.6df
(Also available at http://amc-journal.eu)
Complete resolution of the circulant nut graph
order–degree existence problem
Ivan Damnjanović *
University of Niš, Faculty of Electronic Engineering,
Aleksandra Medvedeva 14, 18106 Niš, Serbia and
Diffine LLC, 3681 Villa Terrace, San Diego, CA 92104, USA
Received 20 November 2022, accepted 28 September 2023, published online 23 September 2024
Abstract
A circulant nut graph is a non-trivial simple graph such that its adjacency matrix is
a circulant matrix whose null space is spanned by a single vector without zero elements.
Regarding these graphs, the order–degree existence problem can be thought of as the math-
ematical problem of determining all the possible pairs (n, d) for which there exists a d-
regular circulant nut graph of order n. This problem was initiated by Bašić et al. and the
first major results were obtained by Damnjanović and Stevanović, who proved that for each
odd t ≥ 3 such that t 6≡10 1 and t 6≡18 15, there exists a 4t-regular circulant nut graph
of order n for each even n ≥ 4t + 4. Afterwards, Damnjanović improved these results by
showing that there necessarily exists a 4t-regular circulant nut graph of order n whenever
t is odd, n is even, and n ≥ 4t + 4 holds, or whenever t is even, n is such that n ≡4 2,
and n ≥ 4t + 6 holds. In this paper, we extend the aforementioned results by completely
resolving the circulant nut graph order–degree existence problem. In other words, we fully
determine all the possible pairs (n, d) for which there exists a d-regular circulant nut graph
of order n.
Keywords: Circulant graph, nut graph, graph spectrum, graph eigenvalue, cyclotomic polynomial.
Math. Subj. Class. (2020): 05C50, 11C08, 12D05, 13P05
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
*The author is supported by Diffine LLC.
E-mail addresses: ivan.damnjanovic@elfak.ni.ac.rs (Ivan Damnjanović)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P4.03
edges. Also, for convenience, we will take that each graph of order n has the vertex set
{0, 1, 2, . . . , n− 1}.
A graph G is considered to be a circulant graph if its adjacency matrix A has the form
A =

a0 a1 a2 · · · an−1
an−1 a0 a1 · · · an−2
an−2 an−1 a0 · · · an−3
...
...
...
. . .
...
a1 a2 a3 . . . a0
 .
Here, we clearly have a0 = 0, as well as aj = an−j for all j = 1, n− 1. A concise
way of describing a circulant graph is by taking into consideration the set of all the values
1 ≤ j ≤ n2 such that aj = an−j = 1. We shall refer to this set as the generator set of a
circulant graph and we will use 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
[10]. Bearing this in mind, a circulant nut graph is simply a nut graph whose adjacency
matrix additionally represents a circulant matrix. The study of regular nut graphs was
initiated by Gauci et al. [7], who proved that there exists a cubic nut graph of order n if
and only if n = 12 or 2 | n, n ≥ 18 and that there exists a quartic nut graph of order n if
and only if n ∈ {8, 10, 12} or n ≥ 14. These results were later extended by Fowler et al.
[6, Theorem 7], who determined all the orders that a d-regular nut graph can have for any
5 ≤ d ≤ 11. In the aforementioned paper, the following question was also asked regarding
the existence of vertex-transitive nut graphs.
Problem 1.1 (Fowler et al. [6, Question 9]). For what pairs (n, d) does a vertex-transitive
nut graph of order n and degree d exist?
The necessary conditions for the existence of a d-regular vertex-transitive nut graph of
order n were further derived in the form of the next theorem.
Theorem 1.2 (Fowler et al. [6, Theorem 10]). Let G be a vertex-transitive nut graph on n
vertices, of degree d. Then n and d satisfy the following conditions. Either d ≡4 0, and
n ≡2 0 and n ≥ d+ 4; or d ≡4 2, and n ≡4 0 and n ≥ d+ 6.
Afterwards, Bašić et al. [2] demonstrated that there exists a 12-regular nut graph of
order n if and only if n ≥ 16. While doing so, the study of circulant nut graphs was ini-
tiated and several results concerning these graphs were disclosed, alongside the following
conjecture.
Conjecture 1.3 (Bašić et al. [2]). For every d, where d ≡4 0, and for every even n, n ≥
d+ 4, there exists a circulant nut graph Circ(n, {s1, s2, s3, . . . , s d
2
}) of degree d.
Damnjanović and Stevanović [4, Lemma 18] quickly disproved Conjecture 1.3 by
showing that for each d such that 8 | d, a d-regular circulant nut graph cannot have an
order that is below d + 6. However, Conjecture 1.3 did indirectly bring up an interesting
question which represents a natural follow-up of Question 1.1 and of an earlier question
regarding the existence of regular nut graphs [7, Problem 13]:
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 3
Problem 1.4. What are all the pairs (n, d) for which there exists a d-regular circulant nut
graph of order n?
Henceforth, we shall refer to Question 1.4 as the circulant nut graph order–degree ex-
istence problem, and we will use Nd to denote the set of all the orders that a d-regular
circulant nut graph can have, for each d ∈ N0. Regarding the aforementioned problem,
there are several basic facts that can quickly be noticed, as demonstrated by Damnjanović
and Stevanović [4]. First of all, it is easy to show that every d-regular circulant nut graph
of order n must satisfy 4 | d and 2 | n. Moreover, for any odd t ∈ N, a 4t-regular circulant
nut graph cannot have an order below 4t+4, while for any even t ∈ N, such a graph cannot
have an order smaller than 4t+ 6, as already discussed.
Furthermore, Damnjanović and Stevanović [4] have managed to construct a 4t-regular
circulant nut graph of order n for each even n ≥ 4t + 4, provided t is odd, t 6≡10 1 and
t 6≡18 15. This result is disclosed in the following theorem.
Theorem 1.5 (Damnjanović and Stevanović [4]). For each odd t ≥ 3 such that t 6≡10 1
and t 6≡18 15, the circulant graph Circ(n, {1, 2, 3, . . . , 2t + 1} \ {t}) is a nut graph for
each even n ≥ 4t+ 4.
Thus, Theorem 1.5 fully determines N4t for infinitely many odd values of t. On top of
that, Damnjanović and Stevanović [4, Proposition 19] have also found the set
N8 = {14} ∪ {n ∈ N : 2 | n ∧ n ≥ 18}. (1.1)
In this scenario, it is interesting to notice that a surprising “irregularity” exists due to the
absence of an 8-regular circulant nut graph of order 16.
Afterwards, Damnjanović [3] succeeded in improving the previously disclosed results
by finding the set N4t for each odd t ∈ N:
N4t = {n ∈ N : 2 | n ∧ n ≥ 4t+ 4} (∀t ∈ N, 2 - t).
This result is an immediate corollary of the next two theorems.
Theorem 1.6 (Damnjanović [3]). For each odd t ∈ N and n ≥ 4t+ 4 such that 4 | n, the
circulant graph
Circ
(
n, {1, 2, . . . , t− 1} ∪
{n
4
,
n
4
+ 1
}
∪
{n
2
− (t− 1), . . . , n
2
− 2, n
2
− 1
})
must be a 4t-regular nut graph of order n.
Theorem 1.7 (Damnjanović [3]). For each t ∈ N and n ≥ 4t + 6 such that n ≡4 2, the
circulant graph
Circ
(
n, {1, 2, . . . , t− 1} ∪
{
n+ 2
4
,
n+ 6
4
}
∪
{n
2
− (t− 1), . . . , n
2
− 2, n
2
− 1
})
must be a 4t-regular nut graph of order n.
In this paper, we fully resolve the circulant nut graph order–degree existence problem
by finding Nd for each d ∈ N0. The main result is given in the following theorem.
4 Ars Math. Contemp. 24 (2024) #P4.03
Theorem 1.8 (Circulant nut graph order–degree existence theorem). For each
d ∈ N0, the set Nd can be determined via the following expression:
Nd =

∅, d = 0 ∨ 4 - d,
{n ∈ N : 2 | n ∧ n ≥ d+ 4}, d ≡8 4,
{14} ∪ {n ∈ N : 2 | n ∧ n ≥ 18}, d = 8,
{n ∈ N : 2 | n ∧ n ≥ d+ 6}, 8 | d ∧ d ≥ 16.
(1.2)
The result given in the case d = 0 ∨ 4 - d of Equation (1.2) is straightforward to see,
while the expression corresponding to the case d = 8 follows directly from Equation (1.1).
Given the fact that the case d ≡8 4 represents an immediate corollary of Theorems 1.6
and 1.7, as we have already mentioned, the only remaining case left to be proved is when
8 | d ∧ d ≥ 16. However, Theorem 1.7 tells us that for each such d, there does exist a
circulant nut graph of every order n such that n ≡4 2 and n ≥ d + 6. Thus, taking every-
thing into consideration, in order to complete the proof of Theorem 1.8, it only remains to
be shown that for each even t ≥ 4, there must exist a 4t-regular circulant nut graph of each
order n such that 4 | n and n ≥ 4t+ 8. This is precisely the task that the remainder of the
paper will solve.
The structure of the paper shall be organized in the following manner. After Section 1,
which is the introduction, Section 2 will serve to preview certain theoretical facts regarding
the circulant matrices, circulant nut graphs and cyclotomic polynomials which are required
to successfully finalize the proof of Theorem 1.8. Afterwards, we shall use three separate
constructions in order to show the existence of all the required circulant nut graphs. In
Section 3 we will construct a 4t-regular circulant nut graph of order 4t + 8, for each even
t ≥ 4, thereby showing that such a graph necessarily exists. After that, Section 4 will be
used to show that, for any even t ≥ 4, there exists a 4t-regular circulant nut graph of order
n for each n ≥ 4t + 16 such that 8 | n. Subsequently, Section 5 will demonstrate the
existence of a 4t-regular circulant nut graph of order n for each n ≥ 4t + 12 such that
n ≡8 4, where t ≥ 4 is an arbitrarily chosen even integer. Finally, Section 6 shall provide
a brief conclusion regarding all the obtained results and give two additional problems to be
examined in the future.
2 Preliminaries
It is known from elementary linear algebra theory (see, for example, [8, Section 3.1]) that
the circulant matrix
A =

a0 a1 a2 · · · an−1
an−1 a0 a1 · · · an−2
an−2 an−1 a0 · · · an−3
...
...
...
. . .
...
a1 a2 a3 . . . a0

must have the eigenvalues
P (1), P (ω), P (ω2), . . . , P (ωn−1),
where ω = ei
2π
n is an n-th root of unity, and
P (x) = a0 + a1x+ a2x
2 + · · ·+ an−1xn−1.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 5
Starting from the aforementioned result, Damnjanović and Stevanović [4] have man-
aged to give the necessary and sufficient conditions for a circulant graph to be a nut graph
in the form of the following lemma.
Lemma 2.1 (Damnjanović and Stevanović [4]). Let G = Circ(n, S) where n ≥ 2. The
graph G is a nut graph if and only if all of the following conditions hold:
• 2 | n;
• S consists of t odd and t even integers from
{
1, 2, 3, . . . , n2 − 1
}
, for some t ≥ 1;
• P (ωj) 6= 0 for each j ∈
{
1, 2, 3, . . . , n2 − 1
}
.
Suppose that we are given an arbitrary circulant graph of even order n whose generator
set is non-empty and contains equally many odd and even integers, all of which are positive
integers smaller than n2 . Taking into consideration Lemma 2.1, it becomes apparent that in
order to show that such a graph 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
this graph, the polynomial P (x) ∈ Z[x] has no n-th roots of unity among its roots, except
potentially −1 or 1.
Furthermore, it is clear that ζn−j = 1ζj for each j = 1, n− 1 and each n-th root of
unity ζ ∈ C. Bearing this in mind, we quickly obtain that
P (ζ) =
(
ζs0 +
1
ζs0
)
+
(
ζs1 +
1
ζs1
)
+ · · ·+
(
ζsk−1 +
1
ζsk−1
)
(2.1)
for an arbitrary n-th root of unity ζ and circulant graph G = Circ(n, S), where S =
{s0, s1, s2, . . . , sk−1}, provided all the generator set elements are lower than n2 . Sections 3,
4 and 5 will all heavily rely on Equation (2.1), as well as Lemma 2.1, whilst proving that
the soon-to-be constructed circulant graphs are indeed nut graphs.
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 Φb(x) can be defined for each
b ∈ N via
Φb(x) =
∏
ξ
(x− ξ),
where ξ 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 Q[x] (see, for example, [1]).
Hence, an arbitrary polynomial in Q[x] has a primitive b-th root of unity among its roots if
and only if it is divisible by Φb(x).
While inspecting whether certain integer polynomials are divisible by cyclotomic poly-
nomials, we will strongly rely on the following theorem on the divisibility of lacunary
polynomials by cyclotomic polynomials.
Theorem 2.2 (Filaseta and Schinzel [5]). Let P (x) ∈ Z[x] have N nonzero terms and let
Φb(x) | P (x). Suppose that p1, p2, . . . , pk are distinct primes such that
k∑
j=1
(pj − 2) > N − 2.
Let ej be the largest exponent such that p
ej
j | b. Then for at least one j, 1 ≤ j ≤ k, we
have that Φb′(x) | P (x), where b′ = b
p
ej
j
.
6 Ars Math. Contemp. 24 (2024) #P4.03
3 Construction for n = 4t + 8
In this section, we will demonstrate that for each even t ≥ 4 there does exist a 4t-regular
circulant nut graph of order 4t + 8. In order to achieve this, we shall provide a concrete
example of such a graph, for each even t ≥ 4, and then prove that the given graph is
indeed a circulant nut graph. While constructing these graphs, we will rely on two different
construction patterns. One pattern will be used for the scenario when 4 | t, while the second
will give us our desired result provided t ≡4 2. In the rest of the section we present the two
according lemmas.
Lemma 3.1. For each t ≥ 4 such that 4 | t, the circulant graph
Circ(4t+ 8, {1, 2, 3, . . . , 2t+ 3} \ {t+ 1, t+ 3, t+ 4})
must be a 4t-regular circulant nut graph of order 4t+ 8.
Proof. Let n = 4t+8. First of all, we know that t+1 and t+3 are odd, while t+4 is even,
which directly tells us that the given circulant graph does have a non-empty generator set
that contains equally many odd and even integers, all of which are positive, but smaller than
n
2 . Thus, by virtue of Lemma 2.1, in order to prove the given lemma, it is sufficient to show
that the polynomial P (x) has no n-th roots of unity among its roots, except potentially 1
or −1.
Let ζ ∈ C be an arbitrary n-th root of unity that is different from both 1 and −1. By
implementing Equation (2.1), we swiftly obtain
P (ζ) =
2t+3∑
j=1
(
ζj + ζ−j
)
−
(
ζt+1 + ζ−t−1
)
−
(
ζt+3 + ζ−t−3
)
−
(
ζt+4 + ζ−t−4
)
.
However, since ζ 6= 1, we know that
n−1∑
j=0
ζj = 0
=⇒ ζ−2t−3
4t+7∑
j=0
ζj = 0
=⇒
2t+4∑
j=−2t−3
ζj = 0
=⇒ ζ2t+4 + 1 +
2t+3∑
j=1
(
ζj + ζ−j
)
= 0
=⇒
2t+3∑
j=1
(
ζj + ζ−j
)
= −1− ζ2t+4.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 7
Thus, the condition P (ζ) = 0 quickly becomes equivalent to
P (ζ) = 0
⇐⇒ −1− ζ2t+4 − ζt+1 − ζ−t−1 − ζt+3 − ζ−t−3 − ζt+4 − ζ−t−4 = 0
⇐⇒ −ζt+4(−1− ζ2t+4 − ζt+1 − ζ−t−1 − ζt+3 − ζ−t−3 − ζt+4 − ζ−t−4) = 0
⇐⇒ ζ3t+8 + ζ2t+8 + ζ2t+7 + ζ2t+5 + ζt+4 + ζ3 + ζ + 1 = 0.
(3.1)
We will finish the proof of the lemma by dividing the problem into two cases depending on
the value of ζ
n
2 .
Case ζ
n
2 = −1. In this case, we have ζ2t+4 = −1, hence ζ3t+8 = −ζt+4, which means
that Equation (3.1) leads us to
P (ζ) = 0
⇐⇒ ζ2t+8 + ζ2t+7 + ζ2t+5 + ζ3 + ζ + 1 = 0
⇐⇒ −ζ4 − ζ3 − ζ + ζ3 + ζ + 1 = 0
⇐⇒ 1− ζ4 = 0
⇐⇒ ζ4 = 1.
However, ζ4 = 1 cannot possibly hold. Moreover, ζ 6= 1,−1 by definition, while i and −i
do not satisfy the conditions i
n
2 = −1 and (−i)n2 = −1 due to the fact that 4 | 2t + 4.
Thus, P (ζ) = 0 does not hold for any n-th root of unity ζ that is different from both 1 and
−1 and such that ζ n2 = −1.
Case ζ
n
2 = 1. In this scenario, we immediately see that ζ3t+8 = ζt+4, which further helps
us obtain from Equation (3.1)
P (ζ) = 0
⇐⇒ ζ2t+8 + ζ2t+7 + ζ2t+5 + 2ζt+4 + ζ3 + ζ + 1 = 0
⇐⇒ ζ4 + ζ3 + ζ + 2ζt+4 + ζ3 + ζ + 1 = 0
⇐⇒ 2ζt+4 + ζ4 + 2ζ3 + 2ζ + 1 = 0. (3.2)
We now divide the problem into two subcases depending on the value of ζ
n
4 .
Subcase ζ
n
4 = −1. Here, it is clear that ζt+4 = −ζ2, which means that Equation (3.2)
directly transforms to
P (ζ) = 0 ⇐⇒ ζ4 + 2ζ3 − 2ζ2 + 2ζ + 1 = 0.
However, the polynomial x4 + 2x3− 2x2 + 2x+ 1 ∈ Q[x] has no roots of unity among its
roots, as demonstrated in Appendix D. This means that P (ζ) = 0 cannot possibly hold for
any ζ that is an n-th root of unity, as desired.
Subcase ζ
n
4 = 1. In this subcase, we obtain ζt+4 = ζ2. Thus, Equation (3.2) gives us
P (ζ) = 0
⇐⇒ ζ4 + 2ζ3 + 2ζ2 + 2ζ + 1 = 0
⇐⇒ (ζ2 + 1)(ζ + 1)2 = 0
⇐⇒ ζ2 + 1 = 0.
8 Ars Math. Contemp. 24 (2024) #P4.03
Now, by taking into consideration that i
n
4 = (−i)n4 = −1 due to the fact that n4 = t+2 ≡4
2, we clearly see that for any n-th root of unity ζ ∈ C different from 1 and −1 and such
that ζ
n
4 = 1, the equality ζ2 + 1 = 0 truly cannot hold. Hence, we reach P (ζ) 6= 0 once
again.
Lemma 3.2. For each t ≥ 6 such that t ≡4 2, the circulant graph
Circ(4t+ 8, {1, 2, 3 . . . , 2t+ 3} \ {t− 2, t+ 1, t+ 3})
must be a 4t-regular circulant nut graph of order 4t+ 8.
Proof. Let n = 4t + 8. It is clear that t − 2 is even, while t + 1 and t + 3 are odd,
which implies that the given circulant graph has a non-empty generator set that contains
equally many odd and even integers, all of which are positive and lower than n2 . By relying
on Lemma 2.1, we know that in order to finalize the proof of the lemma, it is enough to
demonstrate that the polynomial P (x) has no n-th roots of unity among its roots, except
potentially 1 or −1.
We will use a very similar strategy to complete the proof as it was done in Lemma 3.1.
Let ζ ∈ C be an arbitrary n-th root of unity such that ζ 6= 1,−1. By using Equation (2.1),
we immediately get
P (ζ) =
2t+3∑
j=1
(
ζj + ζ−j
)
−
(
ζt−2 + ζ−t+2
)
−
(
ζt+1 + ζ−t−1
)
−
(
ζt+3 + ζ−t−3
)
.
Now, we can use the same equality
∑2t+3
j=0
(
ζj + ζ−j
)
= −1 − ζ2t+4 that was proved in
Lemma 3.1 in order to conclude that
P (ζ) = 0
⇐⇒ −1− ζ2t+4 − ζt−2 − ζ−t+2 − ζt+1 − ζ−t−1 − ζt+3 − ζ−t−3 = 0
⇐⇒ −ζt+3(−1− ζ2t+4 − ζt−2 − ζ−t+2 − ζt+1 − ζ−t−1 − ζt+3 − ζ−t−3) = 0
⇐⇒ ζ3t+7 + ζ2t+6 + ζ2t+4 + ζ2t+1 + ζt+3 + ζ5 + ζ2 + 1 = 0.
(3.3)
We shall finish the proof by dividing the problem into two cases depending on the value of
ζ
n
2 .
Case ζ
n
2 = −1. Here, we see that ζ2t+4 = −1, hence ζ3t+7 = −ζt+3. On behalf of
Equation (3.3), P (ζ) = 0 becomes further equivalent to
P (ζ) = 0
⇐⇒ ζ2t+6 + ζ2t+4 + ζ2t+1 + ζ5 + ζ2 + 1 = 0
⇐⇒ −ζ2 − 1− 1
ζ3
+ ζ5 + ζ2 + 1 = 0
⇐⇒ ζ5 − 1
ζ3
= 0
⇐⇒ ζ8 = 1.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 9
However, n2 = 2t + 4, where t ≡4 2, which means that 8 |
n
2 . This implies that whenever
some eighth root of unity is raised to the power of n2 , it yields 1, not−1. Hence, the equality
ζ8 = 1 cannot possibly hold for any n-th root of unity ζ ∈ C such that ζ n2 = −1. Thus,
we obtain P (ζ) 6= 0, as desired.
Case ζ
n
2 = 1. In this case, it is clear that ζ3t+7 = ζt+3, which allows us to implement
Equation (3.3) in order to reach
P (ζ) = 0
⇐⇒ ζ2t+6 + ζ2t+4 + ζ2t+1 + 2ζt+3 + ζ5 + ζ2 + 1 = 0
⇐⇒ ζ2 + 1 + 1
ζ3
+ 2ζt+3 + ζ5 + ζ2 + 1 = 0
⇐⇒ ζ3
(
2ζt+3 + ζ5 + 2ζ2 + 2 +
1
ζ3
)
= 0
⇐⇒ 2ζt+6 + ζ8 + 2ζ5 + 2ζ3 + 1 = 0. (3.4)
We now divide the problem into two subcases depending on the value of ζ
n
4 .
Subcase ζ
n
4 = −1. In this subcase, we know that ζt+6 = −ζ4, hence Equation (3.4)
quickly implies
P (ζ) = 0
⇐⇒ ζ8 + 2ζ5 − 2ζ4 + 2ζ3 + 1 = 0
⇐⇒ (ζ2 + 1)(ζ6 − ζ4 + 2ζ3 − ζ2 + 1) = 0.
Furthermore, we have i
n
4 = (−i)n4 = 1 due to the fact that n4 = t+ 2 ≡4 0, which means
that ζ2 + 1 6= 0. This leads us to
P (ζ) = 0 ⇐⇒ ζ6 − ζ4 + 2ζ3 − ζ2 + 1 = 0.
However, the polynomial x6 − x4 + 2x3 − x2 + 1 ∈ Q[x] has no roots of unity among its
roots, as shown in Appendix D. This implies that P (ζ) 6= 0 for any n-th root of unity ζ
such that ζ 6= 1,−1 and ζ n4 = −1.
Subcase ζ
n
4 = 1. Here, we get ζt+6 = ζ4, which enables us to use Equation (3.4) to swiftly
obtain
P (ζ) = 0
⇐⇒ ζ8 + 2ζ5 + 2ζ4 + 2ζ3 + 1 = 0
⇐⇒ (ζ + 1)2(ζ6 − 2ζ5 + 3ζ4 − 2ζ3 + 3ζ2 − 2ζ + 1) = 0
⇐⇒ ζ6 − 2ζ5 + 3ζ4 − 2ζ3 + 3ζ2 − 2ζ + 1 = 0.
The polynomial x6−2x5 + 3x4−2x3 + 3x2−2x+ 1 ∈ Q[x] has no roots of unity among
its roots, as demonstrated in Appendix D. This clearly shows that P (ζ) = 0 cannot hold,
as desired.
4 Construction for 8 | n ∧ n ≥ 4t + 16
In this section we will give a constructive proof of the existence of a 4t-regular circulant
nut graph of any order n ∈ N such that n ≥ 4t+ 16 and 8 | n, for any even t ≥ 4. In order
to achieve this, we will prove the following theorem.
10 Ars Math. Contemp. 24 (2024) #P4.03
Theorem 4.1. For any even t ≥ 4 and any n ≥ 4t+16 such that 8 | n, the circulant graph
Circ(n, S′t,n) where
S′t,n = {1, 2, . . . , t− 3} ∪ {t− 1, t} ∪
{n
4
,
n
4
+ 2
}
∪
{n
2
− t, n
2
− (t− 1)
}
∪
{n
2
− (t− 3), . . . , n
2
− 2, n
2
− 1
}
must be a 4t-regular circulant nut graph of order n.
For starters, it is clear that the set S′t,n is well defined, given the fact that t <
n
4 and
n
4 + 2 <
n
2 − t for each even t ≥ 4 and each n ≥ 4t + 16 such that 8 | n. Moreover, it
is not difficult to see that this set necessarily contains equally many odd and even integers,
all of which are positive and smaller than n2 . By virtue of Lemma 2.1, in order to prove
Theorem 4.1, it is sufficient to show that P (x) has no n-th roots of unity among its roots,
except potentially 1 or −1.
The proof of Theorem 4.1 will be carried out in a fashion that is very similar to the
strategy used by Damnjanović [3]. Thus, we will rely on a few auxiliary lemmas which will
be used in order to finalize the proof in a more concise manner. We start off by defining the
following two polynomials
Qt(x) = 2x
2t+1 − 2x2t−1 + 2x2t−2 + xt+3 − xt+2 + xt−1 − xt−2 − 2x3 + 2x2 − 2,
Rt(x) = 2x
2t+1 − 2x2t−1 + 2x2t−2 − xt+3 + xt+2 − 4xt+1
+ 4xt − xt−1 + xt−2 − 2x3 + 2x2 − 2,
for each even t ≥ 6. Now, since it is clear that 3 < t− 2 and t + 3 < 2t− 2 hold for any
even t ≥ 6, we see that Qt(x) must have exactly 10 non-zero terms, while Rt(x) surely
has exactly 12 non-zero terms. Let L′t and L
′′
t be the sets containing the powers of these
terms, respectively, i.e.
L′t = {0, 2, 3, t− 2, t− 1, t+ 2, t+ 3, 2t− 2, 2t− 1, 2t+ 1},
L′′t = {0, 2, 3, t− 2, t− 1, t, t+ 1, t+ 2, t+ 3, 2t− 2, 2t− 1, 2t+ 1},
for each even t ≥ 6. In the next lemma we will show one valuable property regarding these
two sets.
Lemma 4.2. For each even t ≥ 6 and each β ∈ N, β ≥ 10, L′t must contain an element
whose remainder modulo β is unique within the set. Also, for each even t ≥ 6 and each
β ∈ N, β ≥ 7 such that β - t, L′′t necessarily contains an element whose remainder modulo
β is unique within the set.
Proof. It is clear that, for any β ≥ 7, the elements t− 2, t− 1, t, t+ 1, t+ 2, t+ 3 must all
have mutually distinct remainders modulo β. If the element t − 1 were to have a distinct
remainder modulo β from all the remainders of the elements 0, 2, 3, 2t− 2, 2t− 1, 2t+ 1,
then this value would represent an element of the set L′t, as well as the set L
′′
t , which
has a unique remainder modulo β inside the said set. The lemma statement would swiftly
follow from here. Now, suppose otherwise, i.e. that the value t − 1 does have the same
remainder modulo β as some number from the set {0, 2, 3, 2t− 2, 2t− 1, 2t+ 1}. We will
finish the proof off by showing that the lemma statement holds in this scenario as well. For
convenience, we will divide the problem into six corresponding cases.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 11
t ≡β −2 t ≡β 0 t ≡β 1 t ≡β 3 t ≡β 4
0 ≡β 0 0 0 0 0
2 ≡β 2 2 2 2 2
3 ≡β 3 3 3 3 3
t− 2 ≡β −4 −2 −1 1 2
t− 1 ≡β −3 −1 0 2 3
t ≡β −2 0 1 3 4
t+ 1 ≡β −1 1 2 4 5
t+ 2 ≡β 0 2 3 5 6
t+ 3 ≡β 1 3 4 6 7
2t− 2 ≡β −6 −2 0 4 6
2t− 1 ≡β −5 −1 1 5 7
2t+ 1 ≡β −3 1 3 7 9
Table 1: The elements of the sets L′t and L
′′
t modulo β, for certain values of t mod β.
Case t − 1 ≡β 0. In this case we obtain t ≡β 1. From Table 1 it is now clear that the
element t− 2 must have a unique remainder modulo β in both L′t and L′′t .
Case t− 1 ≡β 2. In this case we get t ≡β 3. Once again, Table 1 tells us that the element
t− 2 must have a unique remainder modulo β in both L′t and L′′t .
Case t − 1 ≡β 3. Here, we conclude that t ≡β 4. According to Table 1, we see that the
element t necessarily has a unique remainder modulo β in L′′t , whenever β ≥ 7. On the
other hand, if β ≥ 10, then the element 0 certainly has a unique remainder modulo β within
the set L′t.
Case t−1 ≡β 2t−2. In this scenario we get t ≡β 1, hence this case is solved in absolutely
the same way as the previous case t− 1 ≡β 0.
Case t − 1 ≡β 2t − 1. Here, we immediately get t ≡β 0. By virtue of Table 1, we see
that the element 0 has a unique remainder modulo β in the set L′t. On the other hand, the
set L′′t contains no element with a unique remainder modulo β. In fact, we can group the
elements of L′′t into six equivalence pairs according to their remainders modulo β. We will
rely on this fact later on.
Case t− 1 ≡β 2t+ 1. In this case, we obtain t ≡β −2. It is easy to see from Table 1 that
whenever β ≥ 10, the element t − 2 must have a unique remainder modulo β within the
set L′t. Similarly, if β ≥ 7, then the element t+ 1 surely has a unique remainder modulo β
inside the set L′′t .
Now, by implementing Lemma 4.2, we are able to prove the following lemma regarding
the divisibility ofQt(x) andRt(x) polynomials by certain polynomials that shall be of later
use to us.
Lemma 4.3. For any even t ≥ 6 and each β ≥ 10, the polynomial Qt(x) cannot be
divisible by a polynomial V (x) ∈ Q[x] with at least two non-zero terms such that all of
its terms have powers divisible by β. Similarly, for any even t ≥ 6 and each β ≥ 7, the
polynomial Rt(x) also cannot be divisible by any such V (x).
Proof. Let t ≥ 6 be an arbitrarily chosen even integer and let β ≥ 10 be any positive
integer. Suppose that the polynomial Qt(x) is divisible by a V (x) with at least two non-
zero terms such that all of its terms have powers divisible by β. Now, we will useQ(β,j)t (x)
12 Ars Math. Contemp. 24 (2024) #P4.03
to denote the polynomial composed of all the terms of Qt(x) whose powers are congruent
to j modulo β, for each j = 0, β − 1. If we write
Qt(x) = V (x)V1(x)
and use the notation V (β,j)1 (x) in a manner analogous to the previously stated Q
(β,j)
t (x), it
becomes easy to notice that
Q
(β,j)
t (x) = V (x)V
(β,j)
1 (x)
must hold for each j = 0, β − 1. Hence, we obtain that V (x) | Q(β,j)t (x) is true for each
j = 0, β − 1. However, by virtue of Lemma 4.2, we know that there exists an element of
L′t that has a unique remainder modulo β within the set. This implies that there exists a j
such that Q(β,j)t (x) has the form c x
a for some c ∈ Z \ {0} and a ∈ N0. By taking this into
consideration, we get that V (x) | c xa, which further implies that V (x) cannot have more
than one non-zero term, thus yielding a contradiction.
Now, let t ≥ 6 be any even integer and let β ≥ 7 be some positive integer. Suppose that
Rt(x) is divisible by a V (x) with at least two non-zero terms such that all of its terms have
powers divisible by β. If β - t, then we can obtain a contradiction by applying Lemma 4.2
in a manner that is entirely analogous to the technique previously used while dealing with
the Qt(x) polynomial. Thus, we choose to omit the proof details of this case and focus
solely on the remaining scenario when β | t holds.
By taking into consideration the remainders given in Table 1, we see that for β ≥ 7 and
β | t, the divisibility V (x) | Rt(x) further implies
V (x) | 4xt − 2,
V (x) | xt+2 + 2x2,
from which we swiftly obtain
V (x) | x2 (4xt − 2) + (xt+2 + 2x2)
=⇒ V (x) | 5xt+2,
thus yielding a contradiction once more, as desired.
We now turn our attention to the cyclotomic polynomials and investigate the divisibility
of Qt(x) and Rt(x) by these polynomials, for all possible even values t ≥ 6. By taking
into consideration that each cyclotomic polynomial Φb(x) must have at least two non-zero
terms, it becomes apparent that Lemma 4.3 will play a big role in our analysis to come. In
fact, its usage is immediately demonstrated within the next lemma.
Lemma 4.4. For each even t ≥ 6, the divisibility Φb(x) | Qt(x) for some b ∈ N implies
• p2 - b for any prime number p ≥ 11;
• 73 - b, 53 - b, 34 - b, 22 - b.
Also, for each even t ≥ 6, the divisibility Φb(x) | Rt(x) for some b ∈ N implies
• p2 - b for any prime number p ≥ 7;
• 53 - b, 33 - b, 22 - b.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 13
Proof. Let b ∈ N be such that p2 | b for some prime number p. In this case, bp is a positive
integer divisible by p, hence we get that Φb(x) = Φ b
p
(xp) (see, for example, [9, page 160]).
Similarly, if pk | b for some k ≥ 2, we inductively obtain that Φb(x) = Φ b
pk−1
(xp
k−1
).
We will now implement this observation in order to complete the proof of the lemma by
dividing it into two separate cases for Qt(x) and Rt(x).
Case Qt(x). Suppose that Φb(x) | Qt(x) for some even t ≥ 6 and some b ∈ N. If p2 | b
for some prime number p ≥ 11, we then get that Φb(x) = Φ b
p
(xp), hence all the terms
of Φb(x) must have powers divisible by p ≥ 11. By virtue of Lemma 4.3, the divisibility
Φb(x) | Qt(x) cannot hold, hence we obtain a contradiction.
If we suppose that 73 | b or 53 | b or 34 | b, we get that all the terms of Φb(x) must have
powers divisible by 49 or 25 or 27, respectively. In each of these cases, Lemma 4.3 tells us
that the divisibility Φb(x) | Qt(x) does not hold, thus yielding a contradiction. In order to
prove the part of the lemma regarding the Qt(x) polynomial, it becomes sufficient to show
that 4 | b cannot be true.
Now, suppose that 4 | b holds. In this case, we immediately get that Φb(x) contains
only terms whose powers are even. By taking into consideration that the numbers 0, 2,
t− 2, t+ 2, 2t− 2 are even, while 3, t− 1, t+ 3, 2t− 1, 2t+ 1 are odd, we conclude that
Φb(x) | 2x2t−2 − xt+2 − xt−2 + 2x2 − 2,
Φb(x) | 2x2t+1 − 2x2t−1 + xt+3 + xt−1 − 2x3.
If we denote
A(x) = 2x2t−2 − xt+2 − xt−2 + 2x2 − 2,
B(x) = 2x2t+1 − 2x2t−1 + xt+3 + xt−1 − 2x3,
C(x) = xt+7 − xt+5 + xt+3 − xt+1 + 1
2
x9 + 2x7 − 3x5 + 4x3 − 3
2
x,
D(x) = −xt+4 − xt + 1
2
x8 − x4 + 2x2 − 3
2
,
then it can be further obtained that
Φb(x) | A(x)C(x) +B(x)D(x)
=⇒ Φb(x) | 3x9 − 8x7 + 10x5 − 8x3 + 3x
=⇒ Φb(x) | x(x− 1)2(x+ 1)2(3x4 − 2x2 + 3)
=⇒ Φb(x) | 3x4 − 2x2 + 3.
However, the polynomial 3x4 − 2x2 + 3 ∈ Q[x] has no roots of unity among its roots, as
demonstrated in Appendix D, thus yielding a contradiction. This means that 4 | b cannot
possibly be true, as desired.
Case Rt(x). Suppose that Φb(x) | Rt(x) for some even t ≥ 6 and some b ∈ N. It can
be shown that p2 - b for any prime p ≥ 7, as well as 53 - b and 33 - b, by implementing
Lemma 4.3 in a completely analogous manner as done in the proof of the previous case.
For this reason, we choose to leave out the according details. Thus, in order to finalize the
proof, it is enough to show that 4 - b.
14 Ars Math. Contemp. 24 (2024) #P4.03
Suppose that 4 | b does hold. Similarly as in the previous case, we conclude that Φb(x)
contains only terms whose powers are even. Besides that, the numbers 0, 2, t − 2, t, t +
2, 2t− 2 are even, while 3, t− 1, t+ 1, t+ 3, 2t− 1, 2t+ 1 are odd. Bearing this in mind,
we get
Φ(b) | 2x2t−2 + xt+2 + 4xt + xt−2 + 2x2 − 2,
Φ(b) | 2x2t+1 − 2x2t−1 − xt+3 − 4xt+1 − xt−1 − 2x3.
Now, if we denote
A(x) = 2x2t−2 + xt+2 + 4xt + xt−2 + 2x2 − 2,
B(x) = 2x2t+1 − 2x2t−1 − xt+3 − 4xt+1 − xt−1 − 2x3,
C(x) = −xt+7 − 3xt+5 + 3xt+3 + xt+1 + 1
2
x9 + 6x7 + 5x5 + 8x3 − 3
2
x,
D(x) = xt+4 + 4xt+2 + xt +
1
2
x8 + 4x6 + 7x4 + 6x2 − 3
2
,
it is clear that
Φb(x) | A(x)C(x) +B(x)D(x)
=⇒ Φb(x) | 3x9 − 16x7 − 6x5 − 16x3 + 3x
=⇒ Φb(x) | x(x2 − 2x− 1)(x2 + 2x− 1)(3x4 + 2x2 + 3)
=⇒ Φb(x) | (x2 − 2x− 1)(x2 + 2x− 1)(3x4 + 2x2 + 3).
However, neither of the polynomials x2 − 2x − 1, x2 + 2x − 1, 3x4 + 2x2 + 3 contains
a root that represents a root of unity, which immediately leads us to a contradiction. Thus,
we reach 4 - b.
Lemma 4.4 indicates that the cyclotomic polynomials which divide Qt(x) and Rt(x)
are very specific. Moreover, it can be shown that for any b ≥ 3, the cyclotomic polynomial
Φb(x) can divide neitherQt(x) norRt(x). In fact, our next step shall be to prove this exact
statement. In order to do this, we will need the following two short auxiliary lemmas.
Lemma 4.5. For each even t ≥ 6 and each prime number p ≥ 11, Qt(x) cannot be
divisible by Φp(x) or Φ2p(x). Similarly, for any even t ≥ 6 and any prime number p ≥ 13,
Rt(x) cannot be divisible by Φp(x) or Φ2p(x).
Proof. The lemma statement about the Qt(x) polynomial can be proved in a fairly anal-
ogous manner as the part regarding Rt(x). In fact, the proof of Φp(x) - Rt(x) and
Φ2p(x) - Rt(x) is slightly more difficult to perform due to the existence of one addi-
tional edge case which does not exist when we are dealing with Qt(x). For this reason,
we choose to leave out the proof details for Φp(x) - Qt(x) and Φ2p(x) - Qt(x) and focus
solely on the Rt(x) polynomial.
Now, let t ≥ 6 be an arbitrary even integer and let p ≥ 11 be some prime number. By
noticing that
Φp(x) =
p−1∑
j=0
xj , Φ2p(x) =
p−1∑
j=0
(−1)jxj ,
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 15
we immediately see that deg Φp = deg Φ2p = p−1. We will finalize the proof by splitting
the problem into two cases depending on whether we are dealing with Φp(x) or Φ2p(x).
Case Φp(x). Let R
mod p
t (x) be the following polynomial:
R mod pt (x) = 2x
(2t+1) mod p − 2x(2t−1) mod p + 2x(2t−2) mod p − x(t+3) mod p
+ x(t+2) mod p − 4x(t+1) mod p + 4xt mod p
− x(t−1) mod p + x(t−2) mod p − 2x3 + 2x2 − 2.
It is clear that Φp(x) | Rt(x) holds if and only if Φp(x) | R mod pt (x) does, too. If we
suppose that Φp(x) | Rt(x) is true and take into consideration that
degR mod pt ≤ p− 1 = deg Φp,
we quickly obtain two possibilities:
• R mod pt (x) ≡ 0;
• R mod pt (x) = cΦp(x) for some c ∈ Q \ {0}.
It is not difficult to see that R mod pt (x) ≡ 0 cannot hold. If p - t, then Lemma 4.2
dictates that there exists an element of L′′t that has a unique remainder modulo p within
that set. Hence, R mod pt (x) must have at least one term corresponding to that element. On
the other hand, if p | t, then according to Table 1, in order for R mod pt (x) ≡ 0 to be true,
we would need 4xt mod p − 2 = 0 to hold, which clearly does not. It is worth pointing out
that while performing the analogous proof for Qt(x), the edge case p | t does not exist,
which can immediately be noticed in the formulation itself of Lemma 4.2.
Now, suppose that R mod pt (x) = cΦp(x) holds for some c ∈ Q \ {0}. The polynomial
Φp(x) has p non-zero terms, which means that R
mod p
t (x) needs to have exactly p non-
zero terms as well. This is obviously not possible whenever p ≥ 13, since R mod pt (x) can
have at most 12 non-zero terms.
Case Φ2p(x). Let R̂
mod p
t (x) be the following polynomial:
R̂ mod pt (x) = 2(−1)
b 2t+1p cx(2t+1) mod p − 2(−1)b
2t−1
p cx(2t−1) mod p
+ 2(−1)b
2t−2
p cx(2t−2) mod p − (−1)b
t+3
p cx(t+3) mod p
+ (−1)b
t+2
p cx(t+2) mod p − 4(−1)b
t+1
p cx(t+1) mod p
+ 4(−1)b
t
p cxt mod p − (−1)b
t−1
p cx(t−1) mod p
+ (−1)b
t−2
p cx(t−2) mod p − 2x3 + 2x2 − 2.
We know that each primitive 2p-th root of unity gives −1 when raised to the power of
p. For this reason, it is not difficult to conclude that Φ2p(x) | Rt(x) is equivalent to
Φ2p(x) | R̂ mod pt (x). Now, if we suppose that Φ2p(x) | Rt(x) holds and bear in mind that
deg R̂ mod pt ≤ p− 1 = deg Φ2p,
we reach the same two possibilities as in the previous case:
16 Ars Math. Contemp. 24 (2024) #P4.03
• R̂ mod pt (x) ≡ 0;
• R̂ mod pt (x) = cΦp(x) for some c ∈ Q \ {0}.
The rest of the proof can be carried out in a manner analogous to the previous case. Thus,
we choose to omit it.
Lemma 4.6. For each even t ≥ 6, Qt(x) cannot be divisible by a cyclotomic polynomial
Φb(x) where b ≥ 3 is a positive integer such that
• it does not have any prime factors outside of the set {2, 3, 5, 7};
• it does not contain all the prime factors from the set {3, 5, 7};
• 22 - b, 34 - b, 53 - b, 73 - b.
Also, for any even t ≥ 6, Rt(x) cannot be divisible by a cyclotomic polynomial Φb(x)
where b ≥ 3 is a positive integer such that
• it does not have any prime factors outside of the set {2, 3, 5, 7, 11};
• it does not contain both prime factors from the set {7, 11} or from the set {5, 11};
• 22 - b, 33 - b, 53 - b, 72 - b, 112 - b.
Proof. Let Q mod bt (x) and R
mod b
t (x) be the next two polynomials:
Q mod bt (x) = 2x
(2t+1) mod b − 2x(2t−1) mod b + 2x(2t−2) mod b + x(t+3) mod b
− x(t+2) mod b + x(t−1) mod b − x(t−2) mod b
− 2x3 mod b + 2x2 mod b − 2,
R mod bt (x) = 2x
(2t+1) mod b − 2x(2t−1) mod b + 2x(2t−2) mod b − x(t+3) mod b
+ x(t+2) mod b − 4x(t+1) mod b + 4xt mod b − x(t−1) mod b
+ x(t−2) mod b − 2x3 mod b + 2x2 mod b − 2.
Here, it is crucial to point out that Φb(x) | Qt(x) ⇐⇒ Φb(x) | Q mod bt (x) and
Φb(x) | Rt(x) ⇐⇒ Φb(x) | R mod bt (x). However, for a fixed value of b ∈ N, it
is clear that there exist only finitely many polynomials Q mod bt (x) and R
mod b
t (x) as t
ranges over the even integers greater than or equal to 6. Thus, if we show that Φb(x) di-
vides none of these concrete Q mod bt (x) polynomials, this is sufficient to prove that Φb(x)
does not divide Qt(x). The same can be said regarding Rt(x).
In order to prove the lemma, it is enough to demonstrate that Φb(x) - Q mod bt (x) and
Φb(x) - R mod bt (x) for all the required values of b and for all the possible remainders t mod
b. However, the lemma formulation specifies only a finite set of b values corresponding to
Qt(x) and to Rt(x). For this reason, it is trivial to perform the proof of the lemma via
computer. The required computational results are disclosed in Appendices A and B.
We now proceed to prove the aforementioned statement regarding the divisibility of
Qt(x) and Rt(x) polynomials by cyclotomic polynomials. In order to do this, we shall
heavily rely on Theorem 2.2. The reason why this theorem is so convenient to use is clear
— it is due to the sheer fact that the Qt(x) and Rt(x) polynomials have very few non-zero
terms.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 17
Lemma 4.7. For each even t ≥ 6, Qt(x) is not divisible by any cyclotomic polynomial
Φb(x) where b ≥ 3.
Proof. Suppose that Φb(x) | Qt(x) for some even t ≥ 6 and some b ≥ 3. We now divide
the problem into two cases depending on whether b is divisible by some prime number
from the set {3, 5, 7}.
Case 3 - b ∧ 5 - b ∧ 7 - b. In this case, it is clear that b has at least one prime factor greater
than 7, since b /∈ {1, 2} and 22 - b, according to Lemma 4.4. Now, since Qt(x) has exactly
10 non-zero terms, and p − 2 ≥ 10 − 2 for any prime p ≥ 11, we are able to repeatedly
apply Theorem 2.2 in order to cancel out any additional prime divisor of b greater than 7,
until exactly one is left. This leads us to
Φb′(x) | Qt(x),
where b′ has a single prime divisor greater than 7, and is potentially divisible by two as
well. Taking into consideration Lemma 4.4, we conclude that b′ must either be equal to
some prime p ≥ 11 or have the form 2p, where p ≥ 11 is a prime number. Either way,
Lemma 4.5 tells us that such a Φb′(x) cannot possibly divide Qt(x), hence we obtain a
contradiction.
Case 3 | b ∨ 5 | b ∨ 7 | b. In this scenario, we can apply Theorem 2.2 in a similar fashion
in order to cancel out any potential prime divisor of b greater than 7 until we reach
Φb′(x) | Qt(x),
where b′ ≥ 3 is such that all of its prime factors belong to the set {2, 3, 5, 7}, and 22 - b′,
34 - b′, 53 - b′, 73 - b′, by virtue of Lemma 4.4. Furthermore, we know that (3 − 2) +
(5 − 2) + (7 − 2) > 10 − 2, hence we can suppose without loss of generality that b′ is
not divisible by at least one prime number from the set {3, 5, 7}, in accordance with Theo-
rem 2.2. However, Lemma 4.6 dictates that such a Φb′(x) cannot divide Qt(x), yielding a
contradiction.
Lemma 4.8. For each even t ≥ 6, Rt(x) is not divisible by any cyclotomic polynomial
Φb(x) where b ≥ 3.
Proof. Suppose that Φb(x) | Rt(x) for some even t ≥ 6 and some b ≥ 3. We proceed
by dividing the problem into two cases depending on whether b is divisible by some prime
number from {3, 5, 7, 11}.
Case 3 - b ∧ 5 - b ∧ 7 - b ∧ 11 - b. Due to the fact that b 6∈ {1, 2} and 22 - b, by virtue of
Lemma 4.4, we deduce that b has at least one prime factor greater than 11. SinceRt(x) has
exactly 12 non-zero terms and p − 2 > 12 − 2 for any prime p ≥ 13, we can implement
Theorem 2.2 and Lemma 4.4 in an analogous fashion as in Lemma 4.7 in order to reach
Φb′(x) | Rt(x),
for some b′ that is either equal to a prime p ≥ 13 or has the form 2p, for some prime number
p ≥ 13. Once again, Lemma 4.5 tells us that such a divisibility cannot hold, leading to a
contradiction.
18 Ars Math. Contemp. 24 (2024) #P4.03
Case 3 | b ∨ 5 | b ∨ 7 | b ∨ 11 | b. In this case, we apply Theorem 2.2 once more in order
to cancel out any potential prime divisor of b greater than 11 until we get
Φb′(x) | Rt(x),
where b′ ≥ 3 is such that all of its prime factors belong to the set {2, 3, 5, 7, 11}, and
22 - b′, 33 - b′, 53 - b′, 72 - b′, 112 - b′ due to Lemma 4.4. Besides that, it is clear that
(7−2) + (11−2) > 12−2 and (5−2) + (11−2) > 12−2, which means that it is safe to
suppose that b′ is not divisible by both elements from {7, 11} or from {5, 11}. Bearing this
in mind, it is easy to reach a contradiction by taking into consideration Lemma 4.6.
Finally, we are able to put all the pieces of the puzzle together and complete the proof
of Theorem 4.1.
Proof of Theorem 4.1. From Equation (2.1) we immediately obtain
P (ζ) =
(
ζ
n
4 +
1
ζ
n
4
)
+
(
ζ
n
4 +2 +
1
ζ
n
4 +2
)
+
t∑
j=1,
j 6=t−2
(
ζj +
1
ζj
)
+
n
2−1∑
j=n2−t,
j 6=n2−t+2
(
ζj +
1
ζj
)
,
where ζ is an arbitrarily chosen n-th root of unity different from 1 and −1. It is easy to
further conclude that
P (ζ) =
(
ζ
n
4 +
1
ζ
n
4
)
+
(
ζ
n
4 +2 +
1
ζ
n
4 +2
)
+
t∑
j=1,
j 6=t−2
(
ζj +
1
ζj
+ ζ
n
2−j +
1
ζ
n
2−j
)
. (4.1)
We will finish the proof by showing that P (ζ) 6= 0 must necessarily hold. For the purpose
of making the proof easier to follow, we shall divide it into two cases depending on whether
ζ
n
2 is equal to 1 or −1.
Case ζ
n
2 = −1. It is straightforward to see that ζ n2−j = − 1ζj and
1
ζ
n
2
−j = −ζj , which
swiftly gives
ζj +
1
ζj
+ ζ
n
2−j +
1
ζ
n
2−j
= 0
for any j = 1, t. Thus, Equation (4.1) simplifies to
P (ζ) = ζ
n
4 +2 + ζ
n
4 +
1
ζ
n
4
+
1
ζ
n
4 +2
.
The condition P (ζ) = 0 now becomes equivalent to
P (ζ) = 0
⇐⇒ ζ n4 +2
(
ζ
n
4 +2 + ζ
n
4 +
1
ζ
n
4
+
1
ζ
n
4 +2
)
= 0
⇐⇒ ζ n2 +4 + ζ n2 +2 + ζ2 + 1 = 0
⇐⇒ −ζ4 − ζ2 + ζ2 + 1 = 0
⇐⇒ ζ4 = 1.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 19
However, due to the fact that 4 | n2 , it is evident that each fourth root of unity among ζ
cannot satisfy ζ
n
2 = −1. Thus, provided ζ n2 = −1, ζ4 6= 1 cannot be true, from which we
immediately obtain P (ζ) 6= 0, as desired.
Case ζ
n
2 = 1. Here, we swiftly obtain ζ
n
2−j = 1ζj and
1
ζ
n
2
−j = ζ
j . This immediately
implies
ζj +
1
ζj
+ ζ
n
2−j +
1
ζ
n
2−j
= 2
(
ζj +
1
ζj
)
for any j = 1, t. By applying Equation (4.1), it is now clear that P (ζ) = 0 is equivalent to
P (ζ) = 0
⇐⇒
(
ζ
n
4 +2 + ζ
n
4 +
1
ζ
n
4
+
1
ζ
n
4 +2
)
+ 2
t∑
j=1,
j 6=t−2
(
ζj +
1
ζj
)
= 0
⇐⇒
(
ζ
n
4 +2 + ζ
n
4 +
1
ζ
n
4
+
1
ζ
n
4 +2
)
− 2− 2ζt−2 − 2
ζt−2
+ 2
t∑
j=−t
ζj = 0
⇐⇒ ζt
ζ n4 +2 + ζ n4 + 1
ζ
n
4
+
1
ζ
n
4 +2
− 2− 2ζt−2 − 2
ζt−2
+ 2
t∑
j=−t
ζj
 = 0
⇐⇒ ζt+n4 +2 + ζt+n4 + ζt−n4 + ζt−n4−2 − 2ζt − 2ζ2t−2 − 2ζ2 + 2
2t∑
j=0
ζj = 0.
Given the fact that
(ζ − 1)
ζt+n4 +2 + ζt+n4 + ζt−n4 + ζt−n4−2 − 2ζt − 2ζ2t−2 − 2ζ2 + 2 2t∑
j=0
ζj
 =
= ζt+
n
4 +3 − ζt+n4 +2 + ζt+n4 +1 − ζt+n4 + ζt−n4 +1 − ζt−n4 + ζt−n4−1 − ζt−n4−2
− 2ζt+1 + 2ζt − 2ζ2t−1 + 2ζ2t−2 − 2ζ3 + 2ζ2 + 2ζ2t+1 − 2
= ζt+
n
4 +3 − ζt+n4 +2 + 2ζt+n4 +1 − 2ζt+n4 + ζt+n4−1 − ζt+n4−2
+ 2ζ2t+1 − 2ζ2t−1 + 2ζ2t−2 − 2ζt+1 + 2ζt − 2ζ3 + 2ζ2 − 2,
it is straightforward to see that P (ζ) = 0 is further equivalent to
ζt+
n
4 +3 − ζt+n4 +2 + 2ζt+n4 +1 − 2ζt+n4 + ζt+n4−1 − ζt+n4−2
+ 2ζ2t+1 − 2ζ2t−1 + 2ζ2t−2 − 2ζt+1 + 2ζt − 2ζ3 + 2ζ2 − 2 = 0.
(4.2)
We now divide the problem into two separate subcases depending on whether ζ
n
4 is equal
to 1 or −1.
Subcase ζ
n
4 = 1. In this subcase, it can be easily noticed from Equation (4.2) that P (ζ) = 0
is equivalent to
ζt+3 − ζt+2 + 2ζt+1 − 2ζt + ζt−1 − ζt−2
+ 2ζ2t+1 − 2ζ2t−1 + 2ζ2t−2 − 2ζt+1 + 2ζt − 2ζ3 + 2ζ2 − 2 = 0,
20 Ars Math. Contemp. 24 (2024) #P4.03
that is
2ζ2t+1 − 2ζ2t−1 + 2ζ2t−2 + ζt+3 − ζt+2 + ζt−1 − ζt−2 − 2ζ3 + 2ζ2 − 2 = 0. (4.3)
Suppose that P (ζ) = 0 does hold for some n-th root of unity ζ different from 1 and −1.
For t = 4, Equation (4.3) simplifies to
2ζ9 − ζ7 + ζ6 − ζ3 + ζ2 − 2 = 0
⇐⇒ (ζ − 1)(ζ + 1)2(2ζ6 − 2ζ5 + 3ζ4 − 2ζ3 + 3ζ2 − 2ζ + 2) = 0
⇐⇒ 2ζ6 − 2ζ5 + 3ζ4 − 2ζ3 + 3ζ2 − 2ζ + 2 = 0.
However, the polynomial 2x6−2x5+3x4−2x3+3x2−2x+2 ∈ Q[x] has no roots of unity
among its roots, as shown in Appendix D. Thus, we reach a contradiction. On the other
hand, if t ≥ 6, then Equation (4.3) is equivalent to Qt(ζ) = 0, which immediately implies
that the polynomial Qt(x) must be divisible by a cyclotomic polynomial Φb(x) where
b ≥ 3. However, by virtue of Lemma 4.7, this is not possible, yielding a contradiction once
more.
Subcase ζ
n
4 = −1. Here, implementing Equation (4.2) means that P (ζ) = 0 is equivalent
to
− ζt+3 + ζt+2 − 2ζt+1 + 2ζt − ζt−1 + ζt−2
+ 2ζ2t+1 − 2ζ2t−1 + 2ζ2t−2 − 2ζt+1 + 2ζt − 2ζ3 + 2ζ2 − 2 = 0,
that is
2ζ2t+1 − 2ζ2t−1 + 2ζ2t−2 − ζt+3 + ζt+2
− 4ζt+1 + 4ζt − ζt−1 + ζt−2 − 2ζ3 + 2ζ2 − 2 = 0.
(4.4)
Now, suppose that P (ζ) = 0 is true for some n-th root of unity ζ 6= 1,−1. If t = 4, then
Equation (4.4) transforms to
2ζ9 − 3ζ7 + 3ζ6 − 4ζ5 + 4ζ4 − 3ζ3 + 3ζ2 − 2 = 0
⇐⇒ (ζ − 1)(2ζ8 + 2ζ7 − ζ6 + 2ζ5 − 2ζ4 + 2ζ3 − ζ2 + 2ζ + 2) = 0
⇐⇒ 2ζ8 + 2ζ7 − ζ6 + 2ζ5 − 2ζ4 + 2ζ3 − ζ2 + 2ζ + 2 = 0.
However, the polynomial 2x8 + 2x7 − x6 + 2x5 − 2x4 + 2x3 − x2 + 2x+ 2 ∈ Q[x] has
no roots of unity among its roots, as demonstrated in Appendix D, hence P (ζ) = 0 leads
to a contradiction, as desired. On the other hand, whenever t ≥ 6, Equation (4.4) becomes
equivalent to Rt(ζ) = 0, which further implies that Rt(x) is divisible by some cyclotomic
polynomial Φb(x) where b ≥ 3. However, Lemma 4.8 dictates that this is impossible,
hence we reach a contradiction yet again.
5 Construction for n ≡8 4 ∧ n ≥ 4t + 12
In this section we shall give a constructive proof of the existence of a 4t-regular circulant
nut graph of any order n ∈ N such that n ≥ 4t + 12 and n ≡8 4, for any even t ≥ 4. The
proof will be given in the form of the next theorem.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 21
Theorem 5.1. For any even t ≥ 4 and any n ≥ 4t + 12 such that n ≡8 4, the circulant
graph Circ(n, S′′t,n) where
S′′t,n = {1, 2, . . . , t− 1} ∪
{n
4
− 1, n
4
+ 3
}
∪
{n
2
− (t− 1), . . . , n
2
− 2, n
2
− 1
}
must be a 4t-regular circulant nut graph of order n.
We will show that Theorem 5.1 holds by using a similar strategy as with Theorem 4.1.
To begin with, it can be easily deduced that the set S′′t,n is well defined, since t−1 < n4 −1
and n4 + 3 <
n
2 − (t − 1) for each even t ≥ 4 and each n ≥ 4t + 12 such that n ≡8 4.
Besides that, the set S′′t,n certainly contains equally many odd and even integers, all of
which are positive and smaller than n2 . This means that, by implementing Lemma 2.1, we
can prove Theorem 5.1 if we simply show that P (x) has no n-th roots of unity among its
roots, except potentially 1 or −1.
To begin with, we shall define the following two polynomials
Ut(x) = 2x
2t−1 + xt+3 − xt+2 + xt+1 − 3xt + 3xt−1 − xt−2 + xt−3 − xt−4 − 2,
Wt(x) = 2x
2t−1 − xt+3 + xt+2 − xt+1 − xt + xt−1 + xt−2 − xt−3 + xt−4 − 2,
for each even t ≥ 4. Now, for t ≥ 6 we have 2t − 1 > t + 3 and t − 4 > 0, while the
equalities 2t − 1 = t + 3 and t − 4 = 0 hold for t = 4. This means that the polynomials
Ut(x) and Wt(x) have exactly 10 non-zero terms for any even t ≥ 6, and 8 non-zero terms
in case t = 4. We will use Mt to denote the set containing the powers of these terms, i.e.
Mt = {0, t− 4, t− 3, t− 2, t− 1, t, t+ 1, t+ 2, t+ 3, 2t− 1},
for each even t ≥ 4. We are now able to present the following lemma that demonstrates a
property of Mt similar to the one displayed in Lemma 4.2 regarding the sets L′t and L
′′
t .
Lemma 5.2. For each even t ≥ 4 and each β ∈ N, β ≥ 6, Mt must contain an element
whose remainder modulo β is unique within the set.
Proof. It is clear that the six consecutive integers t − 3, t − 2, t − 1, t, t + 1, t + 2 must
all have mutually distinct remainders modulo β for any β ≥ 6. Regardless of whether
t = 4 or t ≥ 6, it is easy to establish that at least two of these integers must have a distinct
remainder modulo β from all the elements of the set {0, t − 4, t + 3, 2t − 1}. Hence,
these integers must have a unique remainder modulo β withinMt and the lemma statement
follows swiftly from here.
By relying on Lemma 5.2, we can now prove another lemma regarding the divisibility
of Ut(x) and Wt(x) polynomials that is analogous to Lemma 4.3.
Lemma 5.3. For any even t ≥ 4 and each β ≥ 6, neither Ut(x) norWt(x) can be divisible
by a polynomial V (x) ∈ Q[x] with at least two non-zero terms such that all of its terms
have powers divisible by β.
Proof. This lemma can be proved in an absolutely analogous manner as Lemma 4.3. The
only difference is that Lemma 5.2 is implemented in place of Lemma 4.2. For this reason,
we choose to omit the proof details.
22 Ars Math. Contemp. 24 (2024) #P4.03
In a similar manner as done so in Section 4, we now investigate the divisibility of Ut(x)
andWt(x) polynomials by cyclotomic polynomials. By directly implementing Lemma 5.3,
we are able to prove the following result.
Lemma 5.4. For each even t ≥ 4, if Φb(x) | Ut(x) or Φb(x) |Wt(x) hold for some b ≥ 3,
we then necessarily have
• p2 - b for any prime number p ≥ 7;
• 53 - b, 33 - b;
• if 22 | b, then b ∈ {4, 8}.
Proof. The proof of this lemma can be carried out in a manner that is almost entirely
analogous to the proof of Lemma 4.4. To be more precise, the results p2 - b for any prime
p ≥ 7, 53 - b and 33 - b can all be shown by simply implementing Lemma 5.3 together with
the same idea used in the aforementioned proof of Lemma 4.4. Thus, we decide to leave
out this part of the proof and focus solely on demonstrating 4 | b =⇒ b ∈ {4, 8}. We will
do this separately for Ut(x) and Wt(x) by splitting the remaining piece of the problem into
two corresponding cases.
Case Ut(x). For a given even t ≥ 4, suppose that Φb(x) | Ut(x) for some b ∈ N such that
4 | b. Since the integers 2t−1, t+ 3, t+ 1, t−1, t−3 are odd, while t+ 2, t, t−2, t−4, 0
are even, it is easy to use the same logic displayed in the proof of Lemma 4.4 in order to
deduce that
Φb(x) | 2x2t−1 + xt+3 + xt+1 + 3xt−1 + xt−3,
Φb(x) | −xt+2 − 3xt − xt−2 − xt−4 − 2.
If we denote
A(x) = 2x2t−1 + xt+3 + xt+1 + 3xt−1 + xt−3,
B(x) = −xt+2 − 3xt − xt−2 − xt−4 − 2,
we immediately obtain
Φb(x) | (x6 + 3x4 + x2 + 1)A(x) + 2xt+3B(x)
=⇒ Φb(x) | xt+9 + 4xt+7 + 7xt+5 + 8xt+3 + 7xt+1 + 4xt−1 + xt−3
=⇒ Φb(x) | xt−3 (x2 + 1)4(x4 + 1)
=⇒ Φb(x) | (x2 + 1)4(x4 + 1).
From here, it follows that any b-th primitive root of unity must also be a root of at least one
of the two polynomials x2 + 1, x4 + 1 ∈ Q[x]. Hence, b ∈ {4, 8}.
Case Wt(x). In this case, let t ≥ 4 be some even integer and let Φb(x) | Wt(x) be true
for some b ∈ N such that 4 | b. In an absolutely analogous way as in the previous case, we
conclude that
Φb(x) | 2x2t−1 − xt+3 − xt+1 + xt−1 − xt−3,
Φb(x) | xt+2 − xt + xt−2 + xt−4 − 2.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 23
By denoting
A(x) = 2x2t−1 − xt+3 − xt+1 + xt−1 − xt−3,
B(x) = xt+2 − xt + xt−2 + xt−4 − 2,
we swiftly get
Φb(x) | (−x6 + x4 − x2 − 1)A(x) + 2xt+3B(x)
=⇒ Φb(x) | xt+9 − xt+5 − xt+1 + xt−3
=⇒ Φb(x) | xt−3 (x− 1)2(x+ 1)2(x2 + 1)2(x4 + 1)
=⇒ Φb(x) | (x2 + 1)2(x4 + 1).
Thus, once again we see that any b-th primitive root of unity must also be a root of at
least one of the two polynomials x2 + 1, x4 + 1 ∈ Q[x], from which we quickly obtain
b ∈ {4, 8}, as desired.
Lemma 5.4 tells us that only certain cyclotomic polynomials could divide theUt(x) and
Wt(x) polynomials. In fact, except potentially the four polynomials Φ1(x),Φ2(x),Φ4(x),
Φ8(x), no other cyclotomic polynomial can divide Ut(x) or Wt(x), for each even t ≥ 4.
We shall now prove this claim by strongly relying on the next two auxiliary lemmas that
greatly resemble the previously disclosed Lemmas 4.5 and 4.6.
Lemma 5.5. For each even t ≥ 4 and each prime number p ≥ 11, neither Ut(x) nor
Wt(x) can be divisible by Φp(x) or Φ2p(x).
Proof. This lemma can be proved in an absolutely analogous manner as Lemma 4.5, the
only difference being that Lemma 5.2 is used in place of Lemma 4.2. For this reason, we
choose to omit the proof details.
Lemma 5.6. For each even t ≥ 4, neither Ut(x) nor Wt(x) can be divisible by a cyclo-
tomic polynomial Φb(x) where b ≥ 3 is a positive integer such that
• it does not have any prime factors outside of the set {2, 3, 5, 7};
• it does not contain all the prime factors from the set {3, 5, 7};
• 22 - b, 33 - b, 53 - b, 72 - b.
Proof. This lemma can be proved in an absolutely analogous manner as Lemma 4.6, hence
we choose the leave out the proof details. The corresponding computational results can be
found in Appendix C.
We will now prove the previously mentioned statement regarding the divisibility of
Ut(x) and Wt(x) polynomials by cyclotomic polynomials. In order to accomplish this,
we shall strongly rely on Theorem 2.2 in a similar way as we have already done so while
proving Lemmas 4.7 and 4.8.
Lemma 5.7. For each even t ≥ 4 and each positive integer b ∈ N such that b /∈ {1, 2, 4, 8},
neither Ut(x) nor Wt(x) are divisible by Φb(x).
24 Ars Math. Contemp. 24 (2024) #P4.03
Proof. Suppose that Φb(x) | Ut(x) or Φb(x) | Wt(x) for some even t ≥ 4 and some
b /∈ {1, 2, 4, 8}. We will now finalize the proof via contradiction by splitting the problem
into two separate cases depending on whether b is divisible by a prime number from the set
{3, 5, 7}.
Case 3 - b ∧ 5 - b ∧ 7 - b. By implementing Lemma 5.4, it becomes evident that b has at
least one prime factor greater than 7, given the fact that b /∈ {1, 2, 4, 8}. Further on, we see
that both Ut(x) and Wt(x) have at most 10 non-zero terms, which means that Theorem 2.2
can be applied to any prime p ≥ 11 in an analogous manner as it was done in the proof of
Lemma 4.7. By cancelling out every single prime divisor of b greater than 7 until exactly
one is left, we conclude that
Φb′(x) | Ut(x) ∨ Φb′(x) |Wt(x)
where b′ has a single prime divisor greater than 7, and is potentially divisible by two as
well, but not by four. By virtue of Lemma 5.4, it is not difficult to deduce that b′ must
either represent a prime number p ≥ 11 or have the form 2p for some prime p ≥ 11. Either
way, Lemma 5.5 swiftly leads us to a contradiction.
Case 3 | b ∨ 5 | b ∨ 7 | b. In this case, Theorem 2.2 can be applied in an analogous manner
in order to cancel out any potential prime divisor of b greater than 7 until we obtain
Φb′(x) | Ut(x) ∨ Φb′(x) |Wt(x)
for some b′ ∈ N such that all of its prime factors belong to the set {2, 3, 5, 7} and 3 | b′ ∨
5 | b′ ∨ 7 | b′. It is clear that b′ ≥ 3. By using Lemma 5.4, we now see that 72 - b′,
53 - b′, 33 - b′, as well as 22 - b′. By virtue of Theorem 2.2, we can suppose without loss
of generality that b′ is not divisible by all the elements from the set {3, 5, 7}, due to the
fact that (3− 2) + (5− 2) + (7− 2) > 10− 2. Taking everything into consideration, we
conclude that b′ must satisfy the criteria given in Lemma 5.6, which immediately yields a
contradiction once more.
We shall now implement Lemma 5.7 in order to finalize the proof of Theorem 5.1 in a
similar manner as we have done so with Theorem 4.1.
Proof of Theorem 5.1. Equation (2.1) directly gives us
P (ζ) =
(
ζ
n
4−1 +
1
ζ
n
4−1
)
+
(
ζ
n
4 +3 +
1
ζ
n
4 +3
)
+
t−1∑
j=1
(
ζj +
1
ζj
)
+
n
2−1∑
j=n2−t+1
(
ζj +
1
ζj
)
,
where ζ is an arbitrarily chosen n-th root of unity different from 1 and −1. From here, we
immediately get
P (ζ) =
(
ζ
n
4−1 +
1
ζ
n
4−1
)
+
(
ζ
n
4 +3 +
1
ζ
n
4 +3
)
+
t−1∑
j=1
(
ζj +
1
ζj
+ ζ
n
2−j +
1
ζ
n
2−j
)
.
(5.1)
We now divide the problem into two cases depending on whether ζ
n
2 is equal to 1 or −1.
We shall finalize the proof by showing that P (ζ) 6= 0 is certainly true in both cases.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 25
Case ζ
n
2 = −1. It is obvious that ζ n2−j = − 1ζj and
1
ζ
n
2
−j = −ζj , from which we get
ζj +
1
ζj
+ ζ
n
2−j +
1
ζ
n
2−j
= 0
for any j = 1, t− 1. For this reason, Equation (5.1) simplifies to
P (ζ) = ζ
n
4 +3 + ζ
n
4−1 +
1
ζ
n
4−1
+
1
ζ
n
4 +3
.
The condition P (ζ) = 0 now becomes equivalent to
P (ζ) = 0
⇐⇒ ζ n4 +3
(
ζ
n
4 +3 + ζ
n
4−1 +
1
ζ
n
4−1
+
1
ζ
n
4 +3
)
= 0
⇐⇒ ζ n2 +6 + ζ n2 +2 + ζ4 + 1 = 0
⇐⇒ −ζ6 − ζ2 + ζ4 + 1 = 0
⇐⇒ −(ζ − 1)(ζ + 1)(ζ4 + 1) = 0
⇐⇒ ζ4 = −1.
Thus, P (ζ) = 0 holds if and only if ζ is a primitive eighth root of unity. However, 8 - n,
hence no n-th root of unity can be a primitive eighth root of unity. Thus, P (ζ) 6= 0, as
desired.
Case ζ
n
2 = 1. In this case, it is clear that ζ
n
2−j = 1ζj and
1
ζ
n
2
−j = ζ
j , which immediately
leads us to
ζj +
1
ζj
+ ζ
n
2−j +
1
ζ
n
2−j
= 2
(
ζj +
1
ζj
)
for any j = 1, t− 1. Bearing this in mind, it is straightforward to see that
P (ζ) = 0
⇐⇒
(
ζ
n
4 +3 + ζ
n
4−1 +
1
ζ
n
4−1
+
1
ζ
n
4 +3
)
+ 2
t−1∑
j=1
(
ζj +
1
ζj
)
= 0
⇐⇒
(
ζ
n
4 +3 + ζ
n
4−1 +
1
ζ
n
4−1
+
1
ζ
n
4 +3
)
− 2 + 2
t−1∑
j=−t+1
ζj = 0
⇐⇒ ζt−1
ζ n4 +3 + ζ n4−1 + 1
ζ
n
4−1
+
1
ζ
n
4 +3
− 2 + 2
t−1∑
j=−t+1
ζj
 = 0
⇐⇒ ζt+n4 +2 + ζt+n4−2 + ζt−n4 + ζt−n4−4 − 2ζt−1 + 2
2t−2∑
j=0
ζj = 0
⇐⇒ (ζ − 1)
ζt+n4 +2 + ζt+n4−2 + ζt−n4 + ζt−n4−4 − 2ζt−1 + 2 2t−2∑
j=0
ζj
 = 0,
26 Ars Math. Contemp. 24 (2024) #P4.03
which finally means that P (ζ) = 0 must be equivalent to
ζt+
n
4 +3 − ζt+n4 +2 + ζt+n4−1 − ζt+n4−2 + ζt−n4 +1 − ζt−n4 + ζt−n4−3 − ζt−n4−4
+ 2ζ2t−1 − 2ζt + 2ζt−1 − 2 = 0.
(5.2)
We now split the problem into two separate subcases depending on whether ζ
n
4 is equal to
1 or −1.
Subcase ζ
n
4 = 1. In this subcase, the implementation of Equation (5.2) directly gives that
P (ζ) = 0 is further equivalent to
ζt+3 − ζt+2 + ζt−1 − ζt−2 + ζt+1 − ζt + ζt−3 − ζt−4
+ 2ζ2t−1 − 2ζt + 2ζt−1 − 2 = 0,
that is
2ζ2t−1 + ζt+3 − ζt+2 + ζt+1 − 3ζt + 3ζt−1 − ζt−2 + ζt−3 − ζt−4 − 2 = 0.
In other words, P (ζ) = 0 is equivalent to ζ being a root of Ut(x). Now, we know that
ζ 6= 1,−1 and that ζ cannot be a primitive eighth root of unity, as discussed earlier. On
top of that, ζ 6= i,−i given the fact that n2 ≡4 2, hence i
n
2 = (−i)n2 = −1. Bearing this
in mind, it is clear that if were P (ζ) = 0 were to hold, then Ut(x) would be divisible by
some cyclotomic polynomial Φb(x) where b /∈ {1, 2, 4, 8}. However, this is not possible
according to Lemma 5.7. For this reason, P (ζ) 6= 0 must hold.
Subcase ζ
n
4 = −1. In this scenario, Equation (5.2) can be quickly simplified to
− ζt+3 + ζt+2 − ζt−1 + ζt−2 − ζt+1 + ζt − ζt−3 + ζt−4
+ 2ζ2t−1 − 2ζt + 2ζt−1 − 2 = 0,
that is
2ζ2t−1 − ζt+3 + ζt+2 − ζt+1 − ζt + ζt−1 + ζt−2 − ζt−3 + ζt−4 − 2 = 0.
Thus, we get that P (ζ) = 0 is equivalent to ζ being a root ofWt(x). By using the analogous
logic as in the previous subcase, it is easy to establish that P (ζ) = 0 would imply that
Wt(x) is divisible by some cyclotomic polynomial Φb(x) where b /∈ {1, 2, 4, 8}, which is
again impossible due to Lemma 5.7. Hence, P (ζ) = 0 cannot be true, which completes the
proof.
6 Conclusion
Theorem 1.8 provides the full answer to Question 1.4 posed by the circulant nut graph
order–degree existence problem. It is evident that there exists a clear and rich pattern that
the orders and degrees of circulant nut graphs must follow, with the sole exception being
the case (n, d) = (16, 8). Bearing this in mind, it now becomes possible to explore other
types of nut graphs more easily.
For example, it is clear that each circulant graph is necessarily a Cayley graph, which
is, in turn, surely a vertex-transitive graph. For this reason, if we are trying to investigate
the existence of Cayley nut graphs or vertex-transitive nut graphs, Theorem 1.8 provides a
solid starting point. Taking all the aforementioned facts into consideration, we are able to
disclose the following corollary.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 27
Corollary 6.1. Let d ∈ N be such that 4 | d, and let n ∈ N be such that 2 | n and
• n ≥ d+ 4 if 8 - d;
• n ≥ d+ 6 if 8 | d;
• (n, d) 6= (16, 8).
There necessarily exists a d-regular Cayley nut graph of order n, as well as a d-regular
vertex-transitive nut graph of order n.
It becomes clear that Corollary 6.1 gives a partial answer to Question 1.1. One of the
possible ways of extending the research concerning the vertex-transitive nut graphs is by
providing a full answer to the aforementioned question. Another possibility is to consider
the order–degree existence problem regarding the Cayley nut graphs, whose conditions are
also less restrictive than those corresponding to the circulant nut graphs. Bearing this in
mind, we end the paper with the following open problem.
Problem 6.2. What are all the pairs (n, d) for which there exists a d-regular Cayley nut
graph of order n?
ORCID iDs
Ivan Damnjanović https://orcid.org/0000-0001-7329-1759
References
[1] Cyclotomic polynomials, Encyclopedia of Mathematics, https://
encyclopediaofmath.org/index.php?title=Cyclotomic_polynomials.
[2] N. Bašić, M. Knor and R. Škrekovski, On 12-regular nut graphs, Art Discrete Appl. Math.
5 (2022), #P2.01, doi:10.26493/2590-9770.1403.1b1, https://doi.org/10.26493/
2590-9770.1403.1b1.
[3] I. Damnjanović, Two families of circulant nut graphs, Filomat 37 (2023), 8331–8360, doi:
10.2298/FIL2324331D, https://www.pmf.ni.ac.rs/filomat-content/2023/
37-24/FILOMAT%2037-24.html.
[4] I. Damnjanović and D. Stevanović, On circulant nut graphs, Linear Algebra Appl. 633 (2022),
127–151, doi:10.1016/j.laa.2021.10.006, https://doi.org/10.1016/j.laa.2021.
10.006.
[5] M. Filaseta and A. Schinzel, On testing the divisibility of lacunary polynomials by cyclo-
tomic polynomials, Math. Comput. 73 (2004), 957–965, doi:10.1090/S0025-5718-03-01589-8,
https://doi.org/10.1090/S0025-5718-03-01589-8.
[6] P. W. Fowler, J. B. Gauci, J. Goedgebeur, T. Pisanski and I. Sciriha, Existence of regular nut
graphs for degree at most 11, Discuss. Math. Graph Theory 40 (2020), 533–557, doi:10.7151/
dmgt.2283, https://doi.org/10.7151/dmgt.2283.
[7] J. B. Gauci, T. Pisanski and I. Sciriha, Existence of regular nut graphs and the Fowler con-
struction, Appl. Anal. Discrete Math. 17 (2023), 321–333, doi:10.2298/aadm190517028g,
https://doi.org/10.2298/aadm190517028g.
[8] R. M. Gray, Toeplitz and circulant matrices: a review., Found. Trends Commun. Inf.
Theory 2 (2006), 155–239, doi:10.1561/0100000006, https://doi.org/10.1561/
0100000006.
28 Ars Math. Contemp. 24 (2024) #P4.03
[9] T. Nagell, Introduction to Number Theory, John Wiley & Sons, Inc., New York, 1951.
[10] I. Sciriha, On the construction of graphs of nullity one, Discrete Math. 181
(1998), 193–211, doi:10.1016/S0012-365X(97)00036-8, https://doi.org/10.1016/
S0012-365X(97)00036-8.
Appendices
A Inspection for Φb(x) - Qt(x)
In this appendix section, we will disclose the computational results that demonstrate
Φb(x) - Qt(x) for all the required values of b ≥ 3, as stated in Lemma 4.6. First of
all, the set of all such values of b can be obtained in a plethora of ways. For example, the
following short Python script can be used.
1 import numpy as np
2
3
4 def main():
5 part_1 = np.multiply.outer([1, 2], [1, 3, 9, 27]).reshape(-1)
6 part_2 = np.multiply.outer([1, 5, 25], [1, 7, 49]).reshape(-1)
7
8 all_of_them = np.multiply.outer(part_1, part_2).reshape(-1)
9 all_of_them.sort()
10 all_of_them = all_of_them.tolist()
11
12 result = list(filter(lambda item: item % 105 != 0, all_of_them))
13 result = list(filter(lambda item: item >= 3, result))
14
15 print(len(result))
16 print(result)
17
18
19 if __name__ == "__main__":
20 main()
The said script quickly finds that there exist exactly 46 values of b that satisfy the given
criteria:
{3, 5, 6, 7, 9, 10, 14, 15, 18, 21, 25, 27, 30, 35, 42, 45, 49, 50, 54, 63,
70, 75, 90, 98, 126, 135, 147, 150, 175, 189, 225, 245, 270, 294,
350, 378, 441, 450, 490, 675, 882, 1225, 1323, 1350, 2450, 2646}.
For each of these values, it can be determined that Φb(x) - Q mod bt (x) for any possible
remainder t mod b. In order to achieve this, we can use, for example, the following Math-
ematica command.
1 Min[Table[
2 Min[Table[
3 Length[CoefficientRules[
4 PolynomialRemainder[
5 2 xˆMod[2 t + 1, b] - 2 xˆMod[2 t - 1, b] +
6 2 xˆMod[2 t - 2, b] + xˆMod[t + 3, b] - xˆMod[t + 2, b] +
7 xˆMod[t - 1, b] - xˆMod[t - 2, b] - 2 xˆ3 + 2 xˆ2 - 2,
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 29
8 Cyclotomic[b, x], x]]], {t, 0, b - 1}]], {b, {3, 5, 6, 7, 9,
9 10, 14, 15, 18, 21, 25, 27, 30, 35, 42, 45, 49, 50, 54, 63, 70,
10 75, 90, 98, 126, 135, 147, 150, 175, 189, 225, 245, 270, 294, 350,
11 378, 441, 450, 490, 675, 882, 1225, 1323, 1350, 2450, 2646}}]]
This command yields the minimum possible number of non-zero terms that the polynomial
Q mod bt (x) mod Φb(x) can have, as b ranges through all the necessary values and t mod b
varies through all the possible remainders. It can be promptly checked that this number is
equal to one, which immediately means that the remainderQ mod bt (x) mod Φb(x) is never
equal to the zero polynomial. From here, we quickly obtain our desired result.
B Inspection for Φb(x) - Rt(x)
Here, we elaborate the computational results showing that Φb(x) - Rt(x) for all the values
of b ≥ 3 given in Lemma 4.6. For starters, the set of all such values of b can be computed,
for example, by using the following Python script.
1 import numpy as np
2
3
4 def main():
5 part_1 = np.multiply.outer([1, 2], [1, 7, 11, 77]).reshape(-1)
6 part_2 = np.multiply.outer([1, 3, 9], [1, 5, 25]).reshape(-1)
7
8 all_of_them = np.multiply.outer(part_1, part_2).reshape(-1)
9 all_of_them.sort()
10 all_of_them = all_of_them.tolist()
11
12 result = list(filter(lambda item: item % 77 != 0, all_of_them))
13 result = list(filter(lambda item: item % 55 != 0, result))
14 result = list(filter(lambda item: item >= 3, result))
15
16 print(len(result))
17 print(result)
18
19
20 if __name__ == "__main__":
21 main()
The Python script easily concludes that there exist exactly 40 values of b that satisfy the
given criteria:
{3, 5, 6, 7, 9, 10, 11, 14, 15, 18, 21, 22, 25, 30, 33, 35, 42,
45, 50, 63, 66, 70, 75, 90, 99, 105, 126, 150, 175, 198,
210, 225, 315, 350, 450, 525, 630, 1050, 1575, 3150}.
For each of these values, it can be determined that Φb(x) - R mod bt (x) regardless of what
the remainder t mod b is. This can be done, for example, by using the next Mathematica
command.
1 Min[Table[
2 Min[Table[
3 Length[CoefficientRules[
30 Ars Math. Contemp. 24 (2024) #P4.03
4 PolynomialRemainder[
5 2 xˆMod[2 t + 1, b] - 2 xˆMod[2 t - 1, b] +
6 2 xˆMod[2 t - 2, b] - xˆMod[t + 3, b] + xˆMod[t + 2, b] -
7 4 xˆMod[t + 1, b] + 4 xˆMod[t, b] - xˆMod[t - 1, b] +
8 xˆMod[t - 2, b] - 2 xˆ3 + 2 xˆ2 - 2, Cyclotomic[b, x],
9 x]]], {t, 0, b - 1}]], {b, {3, 5, 6, 7, 9, 10, 11, 14, 15, 18,
10 21, 22, 25, 30, 33, 35, 42, 45, 50, 63, 66, 70, 75, 90, 99, 105,
11 126, 150, 175, 198, 210, 225, 315, 350, 450, 525, 630, 1050, 1575,
12 3150}}]]
The said command computes the minimum possible number of non-zero terms that the
polynomial R mod bt (x) mod Φb(x) can have, as b ranges through all the required values
and t mod b varies through all the possible remainders. The computation output is equal to
one, hence we obtain our desired result in the same way as in Appendix A.
C Inspection for Φb(x) - Ut(x) and Φb(x) - Wt(x)
We can use an analogous mechanism to disclose the computational results that demonstrate
Φb(x) - Ut(x), as well as Φb(x) - Wt(x), for all the values of b ≥ 3 stated in Lemma 5.6.
The set of all the required values of b can be determined, for example, by using the follow-
ing Python script.
1 import numpy as np
2
3
4 def main():
5 part_1 = np.multiply.outer([1, 2], [1, 3, 9]).reshape(-1)
6 part_2 = np.multiply.outer([1, 5, 25], [1, 7]).reshape(-1)
7
8 all_of_them = np.multiply.outer(part_1, part_2).reshape(-1)
9 all_of_them.sort()
10 all_of_them = all_of_them.tolist()
11
12 result = list(filter(lambda item: item % 105 != 0, all_of_them))
13 result = list(filter(lambda item: item >= 3, result))
14
15 print(len(result))
16 print(result)
17
18
19 if __name__ == "__main__":
20 main()
The given Python script finds that there exist exactly 26 values of b that satisfy the given
criteria:
{3, 5, 6, 7, 9, 10, 14, 15, 18, 21, 25, 30, 35, 42, 45,
50, 63, 70, 75, 90, 126, 150, 175, 225, 350, 450}.
For each of these values, it can be promptly shown that Φb(x) - U mod bt (x) and
Φb(x) - W mod bt (x) for any possible remainder t mod b. This can be accomplished, for
example, by using the following two Mathematica commands.
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 31
1 Min[Table[
2 Min[Table[
3 Length[CoefficientRules[
4 PolynomialRemainder[
5 2 xˆMod[2 t - 1, b] + xˆMod[t + 3, b] - xˆMod[t + 2, b] +
6 xˆMod[t + 1, b] - 3 xˆMod[t, b] + 3 xˆMod[t - 1, b] -
7 xˆMod[t - 2, b] + xˆMod[t - 3, b] - xˆMod[t - 4, b] - 2,
8 Cyclotomic[b, x], x]]], {t, 0, b - 1}]], {b, {3, 5, 6, 7, 9,
9 10, 14, 15, 18, 21, 25, 30, 35, 42, 45, 50, 63, 70, 75, 90, 126,
10 150, 175, 225, 350, 450}}]]
1 Min[Table[
2 Min[Table[
3 Length[CoefficientRules[
4 PolynomialRemainder[
5 2 xˆMod[2 t - 1, b] - xˆMod[t + 3, b] + xˆMod[t + 2, b] -
6 xˆMod[t + 1, b] - xˆMod[t, b] + xˆMod[t - 1, b] +
7 xˆMod[t - 2, b] - xˆMod[t - 3, b] + xˆMod[t - 4, b] - 2,
8 Cyclotomic[b, x], x]]], {t, 0, b - 1}]], {b, {3, 5, 6, 7, 9,
9 10, 14, 15, 18, 21, 25, 30, 35, 42, 45, 50, 63, 70, 75, 90, 126,
10 150, 175, 225, 350, 450}}]]
The given two commands yield the minimum possible number of non-zero terms that the
polynomials U mod bt (x) and W
mod b
t (x) can have, respectively, as b ranges through all the
required values and t mod b takes on any possible value. Both computation outputs are
equal to one, which means that none of the aforementioned remainders are equal to the
zero polynomial, as desired.
D Roots of certain polynomials
In this appendix section, we will demonstrate that none of the following polynomials
Z1(x) = x
4 + 2x3 − 2x2 + 2x+ 1,
Z2(x) = x
6 − x4 + 2x3 − x2 + 1,
Z3(x) = x
6 − 2x5 + 3x4 − 2x3 + 3x2 − 2x+ 1,
Z4(x) = 3x
4 − 2x2 + 3,
Z5(x) = x
2 − 2x− 1,
Z6(x) = x
2 + 2x− 1,
Z7(x) = 3x
4 + 2x2 + 3,
Z8(x) = 2x
6 − 2x5 + 3x4 − 2x3 + 3x2 − 2x+ 2,
Z9(x) = 2x
8 + 2x7 − x6 + 2x5 − 2x4 + 2x3 − x2 + 2x+ 2,
contain a root of unity among its roots. This can be swiftly achieved by simply showing
that none of them are divisible by any cyclotomic polynomial Φb(x). In fact, it is clear
that, for each j = 1, 9, the polynomial Zj(x) cannot be divisible by a Φb(x) such that
deg Φb > degZj . Thus, in order to prove the desired result, it is sufficient to show that
each given polynomial is not divisible by the corresponding cyclotomic polynomials whose
degrees do not exceed its own. This is trivial to accomplish via computer.
32 Ars Math. Contemp. 24 (2024) #P4.03
For starters, it is not difficult to determine all 18 cyclotomic polynomials whose degree
is not above 8:
Φ1(x) = x− 1, Φ7(x) = x6 + x5 + x4 + x3 + x2 + x+ 1,
Φ2(x) = x+ 1, Φ9(x) = x
6 + x3 + 1,
Φ3(x) = x
2 + x+ 1, Φ14(x) = x
6 − x5 + x4 − x3 + x2 − x+ 1,
Φ4(x) = x
2 + 1, Φ18(x) = x
6 − x3 + 1,
Φ6(x) = x
2 − x+ 1, Φ15(x) = x8 − x7 + x5 − x4 + x3 − x+ 1,
Φ5(x) = x
4 + x3 + x2 + x+ 1, Φ16(x) = x
8 + 1,
Φ8(x) = x
4 + 1, Φ20(x) = x
8 − x6 + x4 − x2 + 1,
Φ10(x) = x
4 − x3 + x2 − x+ 1, Φ24(x) = x8 − x4 + 1,
Φ12(x) = x
4 − x2 + 1, Φ30(x) = x8 + x7 − x5 − x4 − x3 + x+ 1.
The necessary computational results can be found on Tables 2, 3, 4 and 5. The disclosed
remainders clearly indicate that no given polynomial can be divisible by any cyclotomic
polynomial of interest, as desired.
b Z5(x) mod Φb(x) Z6(x) mod Φb(x)
1 −2 2
2 2 −2
3 −2− 3x −2 + x
4 −2− 2x −2 + 2x
6 −2− x −2 + 3x
Table 2: The required remainders of Z5(x) and Z6(x).
b Z1(x) mod Φb(x) Z4(x) mod Φb(x) Z7(x) mod Φb(x)
1 4 4 8
2 −4 4 8
3 5 + 5x 5 + 5x 1 + x
4 4 8 4
6 1− x 5− 5x 1− x
5 x− 3x2 + x3 −3x− 5x2 − 3x3 −3x− x2 − 3x3
8 2x− 2x2 + 2x3 −2x2 2x2
10 3x− 3x2 + 3x3 3x− 5x2 + 3x3 3x− x2 + 3x3
12 2x− x2 + 2x3 x2 5x2
Table 3: The required remainders of Z1(x), Z4(x) and Z7(x).
I. Damnjanović: Complete resolution of the circulant nut graph order–degree existence . . . 33
b Z2(x) mod Φb(x) Z3(x) mod Φb(x) Z8(x) mod Φb(x)
1 2 2 4
2 −2 14 16
3 5 −1 1
4 −2x −2x −2x
6 1 −1 1
5 2 + 2x+ 3x3 −4− 4x− 5x3 −3− 3x− 5x3
8 2− 2x2 + 2x3 −2 + 2x2 − 2x3 −1 + x2 − 2x3
10 2− 2x+ x3 x3 1− x+ x3
12 1− 2x2 + 2x3 −3 + 6x2 − 4x3 −3 + 6x2 − 4x3
7 −x− 2x2 + x3 − 2x4 − x5 −3x+ 2x2 − 3x3 + 2x4 − 3x5 −4x+ x2 − 4x3 + x4 − 4x5
9 −x2 + x3 − x4 −2x+ 3x2 − 3x3 + 3x4 − 2x5 −2x+ 3x2 − 4x3 + 3x4 − 2x5
14 x− 2x2 + 3x3 − 2x4 + x5 −x+ 2x2 − x3 + 2x4 − x5 x2 + x4
18 −x2 + 3x3 − x4 −2x+ 3x2 − x3 + 3x4 − 2x5 −2x+ 3x2 + 3x4 − 2x5
Table 4: The required remainders of Z2(x), Z3(x) and Z8(x).
b Z9(x) mod Φb(x)
1 8
2 −8
3 −x
4 4
6 5x
5 6 + 3x+ 3x2 + 6x3
8 6
10 2 + x− x2 − 2x3
12 5− 2x− 5x2 + 4x3
7 5 + 5x+ 3x3 − x4 + 3x5
9 3− 3x2 + 3x3 − 4x4
14 1− x+ x3 − x4 + x5
18 3− 3x2 + x3 + 4x5
15 4x− x2 − x6 + 4x7
16 2x− x2 + 2x3 − 2x4 + 2x5 − x6 + 2x7
20 2x+ x2 + 2x3 − 4x4 + 2x5 + x6 + 2x7
24 2x− x2 + 2x3 + 2x5 − x6 + 2x7
30 −x2 + 4x3 + 4x5 − x6
Table 5: The required remainders of Z9(x).