# A class of Numerical Semigroups defined by Kunz and Waldi - their Principal
Matrices and structure

Srishti Singh  and  Hema Srinivasan  Department of Mathematics, University of
Missouri, Columbia MO 65211, USA.

###### Abstract.

In this paper, we explore a class of numerical semigroups initiated by Kunz
and Waldi containing two coprime numbers $p<q$, which we call KW semigroups.
We characterize KW numerical semigroups by their principal matrices. We
present a necessary and sufficient criterion for a matrix to be the principal
matrix of a KW semigroup. An explicit description of the minimal resolutions
of numerical semigroups in the same class with small embedding dimensions $3$
and $4$ is given. We give a generalization of this notion to three dimensions
using lattice paths under a plane and present some preliminary results and
questions.

MSC Primary: 13c05, 13c70; Secondary: 13D02.

Keywords: Semigroup rings, monoids, critical binomials.

##  1\. Introduction

A numerical semigroup $\langle{\bf a}\rangle$ is a submonoid of $\mathbb{N}$
minimally generated by ${\bf a}=\\{a_{1},\ldots a_{n}\\}\subseteq\mathbb{N}$
where $\gcd(a_{1},\ldots,a_{n})=1$. Such a semigroup will contain all but
finitely many positive integers, called the gaps. The largest gap is called
the Frobenius number, $F({\bf a})$.

This paper is inspired by recent remarkable works of Kunz and Waldi in [5]
where they build numerical semigroups of the same multiplicity $p$ by filling
in gaps. Any semigroup of embedding dimension $2$ is symmetric, i.e., the
number of gaps is exactly half the number of elements less than the Frobenius
number. Thus, a semigroup generated by two relatively prime positive integers
$p<q$, is symmetric and of multiplicity $p$. Kunz and Waldi build extensions
of these semigroups by filling in gaps larger than $p$ to create semigroups of
higher embedding dimensions with the same multiplicity $p$. All the gaps of
$\langle p,q\rangle$ are of the form $pq-xp-yq$ for some positive integers
$x,y\in\mathbb{N}$, with $pq-p-q$ being the largest, the Frobenius number.

In [5], Kunz and Waldi study numerical semigroups of the form $\langle
p,q,h_{1},\ldots h_{n-2}\rangle$ where $p<q$ are relatively prime positive
integers. Further, they analyze a special class of semigroups with embedding
dimension $n$, which we denote by $KW(p,q)$, by filling in gaps where $x\leq
p/2,y\leq q/2$. In particular, they prove a structure theorem for this class:

######  Theorem 1.1.

(Corollary $3.1$, Theorem (Appendix) [5]) Let $A=\langle p,q,h_{1},\ldots
h_{n-2}\rangle$ with $h_{i}=pq-x_{i}p-y_{i}q,$ for some $0<2x_{i}\leq
q,0<2y_{i}\leq p$, $1\leq i\leq n-2$. Then the semigroup ring $k[A]$ is of
type $n-1$ and its relation ideal is generated by $\binom{n}{2}$ elements.

In this paper, we begin by studying the principal matrices of these
semigroups. A “principal matrix” is an $n\times n$ integer matrix associated
with a numerical semigroup of embedding dimension $n$. If ${\bf
a}=\\{a_{1},\ldots,a_{n}\\}$ minimally generates a numerical semigroup, then
its principal matrix $P({\bf a})=(a_{ij})$ is an $n\times n$ matrix,
$a_{ij}\geq 0,i\neq j$, where $-a_{ii}$ is the smallest positive integer such
that $a_{ii}x_{i}+\sum_{i\neq j}a_{ij}x_{j}=0$. The diagonal entries of
$P({\bf a})$ are uniquely determined for a given ${\bf a}$ but the matrix
itself need not be unique.

Indeed for a general numerical semigroup $\langle{\bf a}\rangle$, the rank of
$P({\bf a})\leq n-1$ and when it is $n-1$, one can recover ${\bf a}$ from the
$n-1$ order minors of any of the $n-1$ rows. Further, the rank of $P({\bf
a})\geq n/2$, ([2]). As such, this matrix holds vital information about the
semigroup itself.

For instance, a criterion is established for Gorenstein monomial curves using
principal matrices in [1] and [3]. Additionally, [2] presents a
characterization for principal matrices of numerical semigroups that are
gluing of numerical semigroups.

In this paper, we study the principal matrices of the semigroups in $KW(p,q)$.
We establish a necessary and sufficient criterion for a matrix to be the
principal matrix of a numerical semigroup within Kunz and Waldi’s class in
Theorem 3.1. As a consequence, we get

######  Corollary 1.2.

Let $3\leq p<q$ be prime numbers. Then the principal matrix of a numerical
semigroup $A=\langle p,q,h_{1},\ldots,h_{n-2}\rangle\in KW((p,q))$ is of the
form

$P(A)=T(\alpha,\beta)=\begin{bmatrix}-\left(\frac{q+\alpha_{n-2}}{2}\right)&\frac{p-\beta_{n-2}}{2}&0&0&\cdots&0&1\\\
\frac{q-\alpha_{1}}{2}&-\left(\frac{p+\beta_{1}}{2}\right)&1&0&\cdots&0&0\\\
\alpha_{1}&\beta_{1}&-2&0&\cdots&0&0\\\
\alpha_{2}&\beta_{2}&0&-2&\cdots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\alpha_{n-2}&\beta_{n-2}&0&0&\cdots&0&-2\end{bmatrix},$

for some odd positive integers $\alpha_{i},\beta_{i}$ satisfying
$q>\alpha_{1}\geq\ldots\geq\alpha_{n-2}\geq 0$ and
$0<\beta_{1}\leq\cdots\leq\beta_{n-2}<p$. Conversely, any $n\times n$ matrix
of the form $P(A)=T(\alpha,\beta)$ above is a principal matrix of a $KW(p,q)$
numerical semigroup.

As an interesting fact, we observe that the defining ideals of semigruop rings
$k[H]$ for $H\in KW(p,q)$ can be written as sums of $2\times 2$ minors of
$2+\binom{n-2}{2}$ matrices of size $2\times 3$.

The paper is organized as follows: In section $2$, we define the notion of
principal matrices, the class $KW(p,q)$ of numerical semigroups and some
notation. The proof of our main result (Theorem 3.1) is in section $3$. In
section $4$, various auxiliary results pertaining to the minimal resolutions
and relation ideal of semigroup rings of $KW(p,q)$ are given. We end this
paper by extending the class of KW-semigroups in section $5$, and conclude
with some open questions.

##  2\. Preliminaries

If a set of relatively prime positive integers
$\mathbf{a}=\\{a_{1},...,a_{n}\\}$ minimally generates a semigroup
$\langle\mathbf{a}\rangle$, then, there are equations

$c_{i}a_{i}=\sum_{j\neq i,1\leq j\leq n}a_{ij}a_{i},\hskip 7.22743pt1\leq
i\leq n.$

In the associated semigroup ring
$k[\mathbf{a}]=k[t^{a_{1}},\ldots,t^{a_{n}}]=k[x_{1},\ldots,x_{n}]/I_{\mathbf{a}}$,

$f_{i}=x^{c_{i}}-\prod_{j\neq i,1\leq j\leq n}x_{j}^{a_{ij}}$

are among a set of minimal generators of $I_{\mathbf{a}}$. Further,
$\sqrt{(f_{1},\ldots,f_{n})}=\sqrt{I_{\mathbf{a}}}$. These $f_{i}$ are
therefore called critical binomials of the numerical semigroup
$\langle\mathbf{a}\rangle$ or the binomial toric ideal $I_{\mathbf{a}}$. This
is also contained in the following $n\times n$ matrix, which is called the
Principal Matrix of the numerical semigroup.

######  Definition 2.1.

(Definition 1, [2]) Let $\mathbf{a}=\\{a_{1},...,a_{n}\\}$ be a set of
positive integers minimally generating a semigroup $\langle\mathbf{a}\rangle$.
$A=\begin{bmatrix}-c_{1}&a_{12}&\cdots&a_{1n}\\\
a_{21}&-c_{2}&\cdots&a_{2n}\\\ \vdots&\vdots&\ddots&a_{2n}\\\
a_{n1}&a_{n2}&\cdots&-c_{n}\end{bmatrix}$ is called a principal matrix of
$\langle\mathbf{a}\rangle$ if $A\mathbf{a}=0$, and $c_{i}$ is the smallest
positive integer such that $c_{i}a_{i}\in\langle\mathbf{a}-\\{a_{i}\\}\rangle$
for all $1\leq i\leq n$.

Although the diagonal entries $-c_{i}$ are uniquely determined, $a_{ij}$ are
not always unique. The sequence of positive integers $\mathbf{a}$ can be
recovered from a given principal matrix $A$ of rank $n-1$ by factoring out the
greatest common divisor of the entries of any nonzero column of the adjoint of
A and taking its absolute value.

######  Example 2.2.

The principal matrix of the numerical semigroup ${\bf a}=\langle
5,7,11,13\rangle$ is

$P({\bf a})=\begin{pmatrix}-4&1&0&1\\\ 2&-3&1&0\\\ 3&1&-2&0\\\ 1&3&0&-2\\\
\end{pmatrix}$

We can recover ${\bf a}$ simply from the $3\times 3$ minors of the first three
rows.

In this paper, we study the principal matrices of numerical semigroups in
$KW(p,q)$, constructed in [4] as follows:

######  Definition 2.3.

Let $p,q\in\mathbb{N}$ be relatively prime with $3\leq p<q$. The set of Kunz-
Waldi Semigroups associated to $p<q$, denoted by $KW(p,q)$, is the set of all
numerical semigroups $H$ with $\langle p,q\rangle\subset H\subset\langle
p,q,r\rangle$, where $r=\begin{cases}\frac{p}{2},&p\text{ even}\\\
\frac{q}{2},&q\text{ even}\\\ \frac{p+q}{2},&p\text{ and }q\text{
odd}.\end{cases}$

All $H\in KW(p,q)$ are in one-to-one correspondence to the lattice paths in
the rectangle $R\subseteq\mathbb{R}^{2}$ with the corners
$(0,0),(0,p^{\prime}-1),(q^{\prime}-1,p^{\prime}-1),$ and $(q^{\prime}-1,0)$,
where $p^{\prime}=\left\lfloor\frac{p}{2}\right\rfloor$ and
$q^{\prime}=\left\lfloor\frac{q}{2}\right\rfloor$. The only $H\in KW(p,q)$
with embedding dimension $e(H)=2$ are $\langle p,q\rangle,\langle
p/2,q\rangle$, and $\langle p,q/2\rangle$. For any other $H\in KW(p,q)$, the
minimal generating set is $\\{p,q,h_{1},...,h_{e(H)-2}\\}$, where $h_{i}=pq-
x_{i}p-y_{i}q$, if $(x_{i},y_{i})$ for $1\leq i\leq e(H)-2$ are the corners of
the lattice path defining $H$. This gives a sufficient condition for $H$ to be
in $KW(p,q)$ and we incorporate it in the definition:

$H\in KW(p,q)$ if

(1) $2x_{i}\leq q\quad\text{ and }\quad 2y_{i}\leq p\quad\quad\forall\;\;1\leq
i\leq e(H)-2$

######  Remark 1.

Thus, $H=\langle p,q,h_{1},\ldots,h_{n-2}\rangle\in KW(p,q)$ if and only if
$h_{i}=pq-x_{i}p-y_{i}q$ satisfying

$2x_{i}\leq q\quad\text{ and }\quad 2y_{i}\leq p\quad\quad\forall\;\;1\leq
i\leq e(H)-2,$

$0<x_{1}<\ldots<x_{n-2}$, and $y_{1}>\ldots>y_{n-2}>0$.

##  3\. Principal Matrix of KW semigroups

In this section, we prove one of our main theorems (3.1), which provides an
explicit structure of the principal matrix for any $H\in KW(p,q)$.

######  Theorem 3.1.

Let $p<q$ be two relatively prime positive integers. Choose positive integers
$q>\alpha_{1}>\alpha_{2}>...>\alpha_{n-2}\geq 0$, of the same parity and
$0\leq\beta_{1}<\beta_{2}<...<\beta_{n-2}<p$ of the same parity. Let
$h_{i}=\frac{p\alpha_{i}+q\beta_{i}}{2}$, $1\leq i\leq n-2$.

Then the matrix

(2)
$T:=T(\alpha,\beta)=\begin{bmatrix}-\left(\frac{q+\alpha_{n-2}}{2}\right)&\frac{p-\beta_{n-2}}{2}&0&0&\cdots&1\\\
\frac{q-\alpha_{1}}{2}&-\left(\frac{p+\beta_{1}}{2}\right)&1&0&\cdots&0\\\
\alpha_{1}&\beta_{1}&-2&0&\cdots&0\\\ \alpha_{2}&\beta_{2}&0&-2&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
\alpha_{n-2}&\beta_{n-2}&0&0&\cdots&-2\end{bmatrix}$

is a principal matrix for the semigroup $H=\\{p,q,h_{1},...,h_{n-2}\\}$ if and
only if $H\in KW(p,q)$ provided any of the following is true:

  1. (i)

$p$ and $q$ are both odd

  2. (ii)

$p$ is even and $2h_{1}\neq p\alpha_{1}$

  3. (iii)

$p$ is even, $2h_{1}=p\alpha_{1}$ but $q\leq 2\alpha_{1}-\alpha_{n-2}$

  4. (iv)

$q$ is even and $2h_{n-2}\neq q\beta_{n-2}$

  5. (v)

$q$ is even and $p\leq 2\beta_{n-2}-\beta_{1}$.

If none of the above conditions is true and if $p$ is even, then the principal
matrix of $H$ is

$\begin{bmatrix}-\alpha_{1}&0&2&0&\cdots&0\\\
\frac{q-\alpha_{1}}{2}&-\left(\frac{p+\beta_{1}}{2}\right)&1&0&\cdots&0\\\
\alpha_{1}&\beta_{1}&-2&0&\cdots&0\\\ \alpha_{2}&\beta_{2}&0&-2&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
\alpha_{n-2}&\beta_{n-2}&0&0&\cdots&-2\end{bmatrix}$

and if $q$ is even, it is

$\begin{bmatrix}-\left(\frac{q+\alpha_{n-2}}{2}\right)&\frac{p-\beta_{n-2}}{2}&0&0&\cdots&1\\\
0&-\beta_{n-2}&0&0&\cdots&2\\\ \alpha_{1}&\beta_{1}&-2&0&\cdots&0\\\
\alpha_{2}&\beta_{2}&0&-2&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
\alpha_{n-2}&\beta_{n-2}&0&0&\cdots&-2\end{bmatrix}.$

###### Proof.

First, suppose that one of the conditions $(i)$-$(v)$ are satisfied. Set
$\mathbf{h}=\\{p,q,h_{1},...,h_{n-2}\\}$. By construction, $h_{i}$ is a
minimal generator and $2h_{i}=p\alpha_{i}+q\beta_{i}$. Next, we note that

(3)
$p\left(\frac{q+\alpha_{n-2}}{2}\right)=\frac{pq}{2}+h_{n-2}-\frac{q\beta_{n-2}}{2}=q\left(\frac{p-\beta_{n-2}}{2}\right)+h_{n-2}\in\langle\mathbf{h}\backslash\\{q\\}\rangle$

since $p$ and $\beta_{n}$ have the same parity, and

(4)
$q\left(\frac{p+\beta_{1}}{2}\right)=\frac{pq}{2}+h_{1}-\frac{p\alpha_{1}}{2}=p\left(\frac{q-\alpha_{1}}{2}\right)+h_{1}\in\langle\mathbf{h}\backslash\\{p\\}\rangle,$

since $q$ and $\alpha_{1}$ are of same parity.

It remains to show the that $\frac{q+\alpha_{n-2}}{2}$ and
$\frac{p+\beta_{1}}{2}$ are the smallest integers that make (3) and (4) true,
respectively.

Suppose $\delta q=\gamma p+\mu_{1}h_{1}+...+\mu_{n-2}h_{n-2}$, for some
$\delta,\gamma,\mu_{i}(1\leq i\leq n-2)\in\mathbb{N}$. Not all $\mu_{i}$ are
zero as $p$ and $q$ are coprime. Then

$q\left(\delta-\frac{\mu_{1}\beta_{1}+...+\mu_{n-2}\beta_{n-2}}{2}\right)=p\left(\gamma+\frac{\mu_{1}\alpha_{1}+...+\mu_{n-2}\alpha_{n-2}}{2}\right)$

From the above equation, it follows that $p$ divides
$2\delta-(\mu_{1}\beta_{1}+...+\mu_{n-2}\beta_{n-2}$), so

(5) $0\leq px=2\delta-(\mu_{1}\beta_{1}+...+\mu_{n-2}\beta_{n-2})$

for some $x\in\mathbb{N}$. Now, if $q$ is odd, then none of the $\alpha_{i}$
are zero and hence $x>0$.

Observe that necessarily some $\mu_{j}\geq 1$, so in (5),

$\displaystyle\delta$ $\displaystyle=\frac{px}{2}+\frac{\sum\limits_{i\neq
j,1\leq i\leq
n}\mu_{i}\beta_{i}}{2}+\frac{p+\beta_{j}}{2}-\frac{p+\beta_{j}}{2}$
$\displaystyle=\frac{p+\beta_{j}}{2}+\frac{p}{2}\left(x-1\right)+\frac{\beta_{j}}{2}(\mu_{j}-1)+\sum_{i\neq
j}\mu_{i}\beta_{i}$ $\displaystyle\geq\frac{p+\beta_{j}}{2}$
$\displaystyle\geq\frac{p+\beta_{1}}{2}$

We have shown that $\frac{p+\beta_{1}}{2}$ is the smallest positive integer
such that
$\left(\frac{p+\beta_{1}}{2}\right)p\in\langle\mathbf{h}\backslash\\{p\\}\rangle$.

Even if $q$ is even, $x>0$ unless $\alpha_{n-2}=0$ and
$2h_{n-2}=p\beta_{n-2}$. In that case, $T$ will still be principal as long as
$p\leq 2\beta_{n-2}-\beta_{1}$.

Similarly, suppose

$\delta^{\prime}p=\gamma^{\prime}q+\nu_{1}h_{1}+...+\nu_{n-2}h_{n-2},$

for some $\delta^{\prime},\gamma^{\prime},\nu_{i}(1\leq i\leq
n-2)\in\mathbb{N}$, necessarily some $\nu_{j}\geq 1$. Isolating $p$ and $q$ as
above, we obtain that

$qy=2\delta^{\prime}-(\nu_{1}\alpha_{1}+...+\nu_{n-2}\alpha_{n-2})$

for some $y\geq 1$ if $p$ is not even so that none of the $\beta_{i}$ are
zero.

Then

$\displaystyle\delta^{\prime}$
$\displaystyle=\frac{qy}{2}+\frac{\nu_{1}\alpha_{1}+...+\nu_{n-2}\alpha_{n-2}}{2}+\frac{q+\alpha_{j}}{2}-\frac{q+\alpha_{j}}{2}$
$\displaystyle\geq\frac{q+\alpha_{j}}{2}$
$\displaystyle\geq\frac{q+\alpha_{n-2}}{2}$

Again, if $p$ happens to be even, $T$ will still be principal as long as one
of the conditions (i)-(v) is statisfied. Thus, $T$ is a principal matrix of
$H$. Moreover, each $h_{i}$, $1\leq i\leq n-2$ can expressed as follows:

(6)
$h_{i}=\frac{p\alpha_{i}+q\beta_{i}}{2}=pq-\left(\frac{q-\alpha_{i}}{2}\right)p-\left(\frac{p-\beta_{i}}{2}\right)q$

By hypotheses, $\alpha_{i}>-1$ and $\beta_{i}>-1$, so that
$2\left(\frac{q-\alpha_{i}}{2}\right)=q-\alpha_{i}<q+1$, and
$2\left(\frac{p-\beta_{i}}{2}\right)<p+1$. In view of the sufficient condition
to be a KW-semigroup (1), it now follows that $H\in KW(p,q)$.

Finally, say $p$ is even, and $2h_{1}=p\alpha_{1}$ with
$q>2\alpha_{1}-\alpha_{n-2}$. Then $q$ is odd. And the minimal relation on $p$
is $\alpha_{1}p=2h_{1}$. Hence the principal matrix is

$\begin{bmatrix}-\alpha_{1}&0&2&0&\cdots&0\\\
\frac{q-\alpha_{1}}{2}&-\left(\frac{p+\beta_{1}}{2}\right)&1&0&\cdots&0\\\
\alpha_{1}&\beta_{1}&-2&0&\cdots&0\\\ \alpha_{2}&\beta_{2}&0&-2&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
\alpha_{n-2}&\beta_{n-2}&0&0&\cdots&-2\end{bmatrix}$

The case when $q$ is even can be proved similarly. ∎

Consequently, we obtain a characterization of the principal matrix of any
$H\in KW(p,q)$ when $3<p<q$ are prime. This is Corollary 1.2. Recall from the
Introduction:

######  Corollary (1.2).

Let $p$ be odd and $q>p$ be relatively prime to $p$. Then the principal matrix
of a numerical semigroup $A=(p,q,h_{1},\ldots,h_{n-2})\in KW((p,q))$ is of the
form

$P(A)=T(\alpha,\beta)=\begin{bmatrix}-\left(\frac{q+\alpha_{n-2}}{2}\right)&\frac{p-\beta_{n-2}}{2}&0&0&\cdots&0&1\\\
\frac{q-\alpha_{1}}{2}&-\left(\frac{p+\beta_{1}}{2}\right)&1&0&\cdots&0&0\\\
\alpha_{1}&\beta_{1}&-2&0&\cdots&0&0\\\
\alpha_{2}&\beta_{2}&0&-2&\cdots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\alpha_{n-2}&\beta_{n-2}&0&0&\cdots&0&-2\end{bmatrix},$

for some odd positive integers $\alpha_{i},\beta_{i}$ satisfying
$q>\alpha_{1}\geq\ldots\geq\alpha_{n-2}\geq 0$ and
$0<\beta_{1}\leq\cdots\leq\beta_{n-2}<p$. Conversely, any $n\times n$ matrix
of the form $P(A)=T(\alpha,\beta)$ above is a principal matrix of a $KW(p,q)$
numerical semigroup.

###### Proof.

Note that $h_{i}=pq-px_{i}-qy_{i}$, for all $1\leq i\leq n-2$, with
$0<2x_{i}\leq q,0<2y_{i}\leq p$. Since $H\in KW(p,q)$, it satisfies the
hypotheses of Theorem 3.1. Next, since $p\geq 3$ is prime, it must be odd so
necessarily $y_{1}\neq p/2$. Thus, we get that the principal matrix of $H$ is
of the form $T(\alpha,\beta)$ from equation $\eqref{principalmatrix}$.

The converse is a direct consequence of Theorem 3.1. ∎

######  Remark 2.

The maximal embedding dimension for a numerical semigroup $H$ in $KW(p,q)$ is
precisely $2+\lfloor\frac{p}{2}\rfloor$. This maximum is achieved when the set
of minimal generators of $H$ is a part of an arithmetic sequence
$(p,p+d=q,\ldots,q+(p-1)d)$. However, the building of this extremal semigroup
is via the gaps $h_{i}=q+(p-1)d=pq-p\lfloor\frac{q}{2}\rfloor-q$ and continue.
For example, with $p=7,q=11$ we see that $h_{1}=77-35-11=31,h_{2}=27,h_{3}=23$
which is contained in $(7,11,15,19,23,27,31)$.

##  4\. Auxiliary Results

Let $H\in KW(p,q)$ be a numerical semigroup of embedding dimension $n\geq 3$.
Thus, $H$ is minimally generated by the set $\\{p,q,h_{1},...,h_{n-2}\\}$ for
some relatively prime positive integers $p$ and $q$, and $h_{i}=pq-
px_{i}-qy_{i}$, $1\leq i\leq n-2$. Here, $q>x_{n-2}>...>x_{1}$ and
$p>y_{1}>...>y_{n-2}$ are positive integers with the same parity with $p$ and
$q$ respectively. Let $k$ be a field. Set $S=k[u,v,u_{1},...,u_{n-2}]$ to be a
polynomial ring and $\phi:S\to k[t]$ to be the map defined by $u\mapsto
t^{p},v\mapsto t^{q},u_{i}\mapsto t^{h_{i}},1\leq i\leq n-2$. Then the
semigroup ring $k[H]=k[t^{p},t^{q},t^{h_{1}},...,t^{h_{n-2}}]$ is the image of
$\phi$ and it is isomorphic to $S/I_{H}$ where $I_{H}=\ker\phi$, called the
ideal of $H$, is the prime ideal defining the affine monomial curve whose
coordinate ring is $k[H]$.

###  4.1. A Classification of $I_{H}$

Using results from the appendix in [5], we can express the defining ideal of
the semigroup ring $k[H]$ where $H\in KW(p,q)$ for any embedding dimension
$n\geq 3$ as the sum of determinantal ideals.

######  Theorem 4.1.

Let $H=\langle p,q,h_{1},...,h_{n-2}\rangle\in KW(p,q)$, so that $h_{i}=pq-
x_{i}p-y_{i}q$, $1\leq i\leq n-2$ with positive integers
$x_{1}<x_{2}<...<x_{n-2}$, $y_{1}>y_{2}>...>y_{n-2}$, each satisfying (1):
$2x_{i}\leq q,2y_{i}\leq p$. Then the defining ideal $I_{H}$ of the semigroup
ring $k[H]$ is the ideal of the $2\times 2$ minors of the following $2\times
3$ matrices:

$A_{ij}=\begin{bmatrix}u_{i}&u^{q-2x_{j}}v^{p-y_{i}-y_{j}}&u_{j}\\\
u^{x_{j}-x_{i}}&u_{j}&v^{y_{i}-y_{j}}\end{bmatrix},\quad\quad 1\leq i<j\leq
n-2$ $\quad B=\begin{bmatrix}v^{y_{n-2}}&u^{q-x_{1}-x_{n-2}}&u_{1}\\\
u^{x_{1}}&u_{n-2}&v^{p-y_{1}-y_{n-2}}\end{bmatrix}$
$C=\begin{bmatrix}u^{q-x_{1}-x_{n-2}}v^{p-2y_{1}}&u_{1}&u_{n-2}\\\
u_{1}&u^{x_{n-2}-x_{1}}&v^{y_{1}-y_{n-2}}\end{bmatrix}$

###### Proof.

According to the theorem in Appendix A. of [5], the defining ideal of $H$
consists of the following binomials:

$\displaystyle f_{ij}$
$\displaystyle=u_{i}u_{j}-u^{q-x_{i}-x_{j}}y^{p-y_{i}-y_{j}},\quad 1\leq i\leq
j\leq n-2$ $\displaystyle g_{i}$
$\displaystyle=v^{y_{i}-y_{i+1}}u_{i}-u^{x_{i+1}-x_{i}}u_{i+1},\quad 1\leq
i\leq n-3$ $\displaystyle h_{1}$ $\displaystyle=v^{p-y_{1}}-u^{x_{1}}u_{1}$
$\displaystyle h_{2}$ $\displaystyle=v^{y_{n-2}}u_{n-2}-u^{q-x_{n-2}}$

Let $M^{l}$ denote column $l$ of a matrix $M$. Observe that

$\displaystyle f_{ij}$
$\displaystyle=\det\begin{bmatrix}A_{ij}^{1}&A_{ij}^{2}\end{bmatrix},\quad
1\leq i<j\leq n-2,$ $\displaystyle f_{jj}$
$\displaystyle=\det\begin{bmatrix}A_{ij}^{2}&A_{ij}^{3}\end{bmatrix},\quad
2\leq j\leq n-2,$ $\displaystyle f_{11}$
$\displaystyle=\det\begin{bmatrix}C^{1}&C^{2}\end{bmatrix},$ $\displaystyle
g_{i}$
$\displaystyle=\det\begin{bmatrix}A_{ij}^{1}&A_{ij}^{3}\end{bmatrix},\quad
1\leq i\leq n-3,\>\>j=i+1,$ $\displaystyle h_{1}$
$\displaystyle=\det\begin{bmatrix}B^{1}&B^{3}\end{bmatrix},$ $\displaystyle
h_{2}$ $\displaystyle=\det\begin{bmatrix}B^{1}&B^{2}\end{bmatrix}$

∎

###  4.2. Minimal Free Resolutions

In this section, we explicitly describe minimal free resolutions of the
semigroup ring $k[H]$ where $H$ is a numerical semigroup of small embedding
dimension $3$ or $4$ in the class $KW(p,q)$, and give their Betti numbers. We
express the maps in the resolution in terms of the $x_{i},y_{i}$ where
$px_{i}+qy_{i}$ are the complements of the gaps $h_{i}$ of $\langle
p,q\rangle$, i.e., $h_{i}=pq-(px_{i}+qy_{i})$ for $1\leq i\leq n-2$.

####  4.2.1. Embedding Dimension of $H$ is $3$

In this instance, we have $n=3$, so
$H=\langle p,q,h_{1}\rangle\in KW(p,q)$, $h_{1}=pq-px_{1}-qy_{1}$. Here,
$x_{1},y_{1}\in\mathbb{N}$ with $(x_{1},y_{1})\leq(q/2,p/2)$. Furthermore,
$k[H]=k[t^{p},t^{q},t^{h_{1}}]$ is the semigroup ring associated to $H$, and
$\phi:S\rightarrow R$ is the map defined by $u\mapsto t^{p},v\mapsto
t^{q},u_{1}\mapsto t^{h_{1}}$. Following is the resolution of $k[H]$:

$0\to S^{2}\xrightarrow{\begin{pmatrix}u_{1}&-u^{q-2x_{1}}\\\
-u^{x_{1}}&v^{y_{1}}\\\
v^{p-2y_{1}}&-u_{1}\end{pmatrix}}S^{3}\xrightarrow{\begin{pmatrix}v^{p-y_{1}}-u^{x_{1}}&u^{q-2x_{1}}v^{p-2y_{1}}-u_{1}^{2}&u^{q-x_{1}}-v^{y_{1}}u_{1}\end{pmatrix}}S^{1}$

####  4.2.2. Embedding Dimension of $H$ is $4$

In this setting, $H=\langle p,q,h_{1},h_{2}\rangle\in KW(p,q)$, $h_{i}=pq-
px_{i}-qy_{i},i=1,2$. Here, $x_{1}<x_{2}\leq q/2$, $y_{2}<y_{1}\leq p/2$ are
in $\mathbb{N}$. Furthermore, $k[H]=k[t^{p},t^{q},t^{h_{1}},t^{h_{2}}]$ is the
semigroup ring associated to $H$. Following is the resolution of $R/I$, where
$I$ is the relation ideal of $k[H]$:

$0\to
S^{3}\xrightarrow{A_{1}}S^{8}\xrightarrow{A_{2}}S^{6}\xrightarrow{A_{3}}S^{1}$

The maps are given by matrices below.

$A_{1}=\begin{bmatrix}u_{2}&-u^{q-x_{2}}v^{y_{1}-y_{2}}&0\\\
-u_{1}&u^{q-x_{1}-x_{2}}&0\\\ u^{x_{1}}v^{p-2y_{1}}&-x_{1}&0\\\
0&v^{y_{2}}&u^{x_{2}-x_{1}}\\\ -v^{p-y_{1}-y_{2}}&u_{2}&0\\\
-u^{2x_{1}-x_{2}}&0&-v^{y_{1}-y_{2}}\\\ u^{x_{2}-x_{2}}u_{1}&0&u_{2}\\\
0&v^{2y_{2}-y_{1}}u_{2}&-u_{1}\end{bmatrix},$

$A_{2}=$
$\begin{bmatrix}-u^{x_{1}}&-u^{2x_{1}-x_{2}}v^{p-y_{1}-y_{2}}&0&0&0&-u_{2}&-v^{p-y_{1}-y_{2}}&0\\\
0&0&0&-u_{2}&0&u_{1}&u^{x_{2}-x_{1}}&-v^{\frac{y_{1}-y_{2}}{2}}\\\
0&0&v^{y_{2}}&u_{1}&u^{x_{2}-x_{1}}v^{2y_{2}-y_{1}}&0&0&u^{x_{2}-x_{1}}\\\
-v^{p+y_{2}-2y_{1}}&-u^{2x_{1}-x_{2}}u_{1}&u^{q+x_{1}-2x_{2}}&-u^{q-2x_{2}}v^{p-y_{1}-y_{2}}&-v^{2y_{2}-y_{1}}u_{2}&-u^{q-x_{1}-x_{2}}v^{p-2y_{1}}&-u_{1}&-u_{2}\\\
-u^{x_{2}-x_{1}}v^{p-2y_{1}}&-v^{p-y_{1}-y_{2}}&u_{2}&0&u_{1}&0&0&0\\\
-u_{1}&-u_{2}&u^{q-2x_{2}}v^{y_{1}-y_{2}}&0&u^{q-x_{1}-x_{2}}&0&0&0\end{bmatrix}$
$A_{3}=$
$\begin{bmatrix}u^{q-2x_{1}}v^{p-2y_{1}}-u_{1}^{2},&u^{q-x_{1}-x_{2}}v^{p-y_{1}-y_{2}}-u_{1}u_{2},&u^{q-2x_{2}}v^{p-2y_{2}}-u_{2}^{2},&v^{y_{1}-y_{2}}u_{1}-u^{x_{2}-x_{1}}u_{2},&v^{y_{2}}u_{2}-u^{q-x_{2}},&u^{x_{1}}u_{1}-v^{p-y_{1}}\end{bmatrix}$

##  5\. Generalizing KW Type Monoids to Dimension Three

In this section, we will expand this class $KW(p,q)$. Let $p$ and $q$ be two
coprime numbers with $1<p<q$. Let $w=r_{1}p+r_{2}q$ for some
$r_{1},r_{2}\in\mathbb{N}$. Then the semigroup $S=\langle
sp,sq,r_{1}p+r_{2}q\rangle$ with $\gcd(s,w)=1$, is again symmetric and with
Frobenius number $s(pq-p-q)+w(s-1)$. Consider the class $R(p,q,r_{1},r_{2},s)$
of numerical semigroups obtained by adding to $S$ gaps corresponding to points
$(a,b,c)\in\mathbb{N}^{3}$ falling on a lattice path under the plane
$G_{0}:spx+sqy+wz=s(pq+w)-sp-sq-w$.

From here on, $S$ is the numerical semigroup $\langle sp,sq,w\rangle$ where
$p<q$ are relatively prime and $s,w$ are relatively prime and
$w=r_{1}p+r_{2}q,r_{i}\geq 1$.

Figure 1. Gaps of $\langle 15,21,17\rangle$ are in 1-1 correspondence with
lattice points under the plane $15x+21y+17z=103$.

######  Proposition 5.1.

Every gap of $S$ can be written as $s(pq+w)-sp(a+1)-sp(b+1)-w(c+1)$ for some
$(a,b,c)\in\mathbb{N}^{3}$. We may always take $c\leq s-1$. In particular,
each gap of $S$ is of the form $s(pq+w)-sp(a+1)-sp(b+1)-w(c+1)$ with
$(a,b,c)<(q,p,s)$ alphabetically, and corresponds to a unique lattice point
$(a,b,c)$ below the hyperplane

$G_{0}:spx+sqy+wz=s(pq+w)-sp-sq-w.$

###### Proof.

Let $t$ be a gap of $S$. Since $S$ is symmetric, $F(S)-t\in S$ so that
$F(S)-t=spx+sqy+wz$ for some $(x,y,z)\in\mathbb{N}^{3}$. In other words,

(7) $t=s(pq+w)-sp(x+1)-sq(y+1)-w(z+1)$

Now assume $x<q,y<p,z<s$. Suppose

$t=s(pq+w)-sp(x+1)-sq(y+1)-w(z+1)\\\
=s(pq+w)-sp(x^{\prime}+1)-sq(y^{\prime}+1)-w(z^{\prime}+1)$

for some $(x,y,z),(x^{\prime},y^{\prime},z^{\prime})\in\mathbb{N}^{3}$. Then

$s(px+qy-px^{\prime}-qy^{\prime})=w(z^{\prime}-z)$

Since $(s,w)=1$, $s\mid z^{\prime}-z$, i.e., $z^{\prime}=z+ms$ for some
$m\in\mathbb{Z}$. But $0\leq z,z^{\prime}\leq s-1$ so $m=0$.

Therefore,

$p(x-x^{\prime})=q(y^{\prime}-y).$

Since $p$ and $q$ are relatively prime, we get $x=x^{\prime}+mq$ for some
$m\in\mathbb{Z}$. But $0\leq x,x^{\prime}\leq q-1$ so $m=0$.

Thus, we must have $x=x^{\prime},y=y^{\prime}$, and $z=z^{\prime}$.

∎

######  Definition 5.2.

We denote by $KW(p,q,r_{1},r_{2},s)$ the numerical semigroups $H$ in
$R(p,q,r_{1},r_{2},s)$ generated by
$\\{sp,sq,w=r_{1}p+r_{2}q,h_{1},\ldots,h_{n-3}\\}$ where
$h_{i}=s(pq+w)-(x_{i}+1)sp-(y_{i}+1)sq-(z_{i}+1)w$, where
$x_{i}\leq{\frac{q-4}{2}},y_{i}\leq{\frac{p-4}{2}}$ and $z_{i}\leq s-2$.

Figure 2. $H$ obtained by adding $55,51,63$ to $S$

Set $\Gamma(x,y,z)=F(S)-xsp-ysq-zw$ for $(x,y,z)\in\mathbb{N}^{3}$.The Apéry
set of a numerical semigroup $\mathbf{a}$ with respect to an element
$a\in\mathbf{a}$, named in honour of R. Apéry, is
$Ap(\mathbf{a},a)=\\{b\in\mathbf{a}\mid b-a\not\in\mathbf{a}\\}$. Let
$H=\langle sp,sq,w,h_{2},...,h_{n-2}\rangle\in KW(p,q,r_{1},r_{2},s)$. We give
a characterization of the elements $h_{2},...,h_{n-2}$ in terms os the Apéry
sets of $H$. To understand the motivation, we go through the following
geometric illustration.

######  Example 5.3.

Let $S=\langle sp=36,sq=44,w=29\rangle$. Obtain $H$ by adding the gaps
corresponding to a lattice point within one of the cuboids in Figure 2. Here,
$H=\langle 36,44,29,206,221,222\rangle\in KW(9,11,2,1,4)$, where
$h_{2}=221,h_{3}=222,h_{4}=206$ correspond to the lattice points
$A=(1,2,2),B=(3,1,1)$ and $E=(1,3,1)$, respectively.

First, we compute $\text{ Ap}(H,sp=36)$. Fix $z=c$, with $c\leq z_{1}$, the
maximum height of any cuboid in the image. This plane passes through at least
one of the three cuboids, say $C_{i}$ which is obtained from $h_{i}$. For each
$b\leq b_{i}$, there is a line $y=b,z=c$ on the plane $z=c$ such that each
point $(a_{j},b,c),a_{j}\leq a_{2}$ is in $H$. Moreover, whenever $i,j\leq 2$,
we have

$\Gamma(a_{i},b,c)\equiv\Gamma(a_{j},b,c)\mod sp$

Out of all these points on the line $z=c,y=b$, the one with the largest
$x-$coordinate, say $P_{l}$, corresponds to the smallest gap congruent to $sw-
sqb-wc$ modulo $sp$. The equivalence classes are distinct for each distinct
$b$ and $c$, so $\Gamma(P_{l})\in\text{ Ap}(H,sp)$. Visually,
$Ap(H,sp)\backslash S$ is contained in the set of gaps corresponding to the
lattice points seen in Figure 3.

Figure 3. $Ap(H,sp)\backslash S$

Similarly, we can find elements in $\text{ Ap}(H,sq=44)$ and $\text{
Ap}(H,w=29)$. $Ap(H,sq)\backslash S$ and $Ap(H,w)\backslash S$ can be
visualized in Figures 4 and 5 respectively. One can see that the only lattice
points common to all three figures $3,4$ and $5$ are exactly those
corresponding to $h_{2},h_{3}$ and $h_{4}$.

Figure 4. $Ap(H,sq)\backslash S$

Figure 5. $Ap(H,w)\backslash S$

This gives rise to the following result:

######  Proposition 5.4.

Let $H\in KW(p,q,r_{1},r_{2},s)$. Then $\\{\text{minimal generators of
}H\\}\backslash\\{sp,sq,w\\}=\text{ Ap}(H,sp)\cap\text{ Ap}(H,sq)\cap\text{
Ap}(H,w)$.

###### Proof.

Denote by $\mathbf{h}$ the minimal generating set of $H$. Let
$h_{i}\in\mathbf{h}$. If $h_{i}-sp\in H$, then
$h_{i}=\sum_{j}r_{j}h_{j}+asp+bsq+cw$. If $r_{i}=0$, $h_{i}$ is not a minimal
generator. If $r_{i}\geq 1$, then we have $\sum_{j\neq
i}r_{j}h_{j}+(r_{i}-1)h_{i}(a+1)sp+bsq+cw=0$ which is impossible. Hence
$h_{i}-sp\notin H$ and hence $h_{i}\in\text{ Ap}(H,sp)$. Similarly,
$h_{i}\in\text{ Ap}(H,sq)$ and $h_{i}\in\text{ Ap}(H,w)$. Thus,
$\mathbf{h}\backslash\\{p,sq,w\\}\subset\text{ Ap}(H,sp)\cap\text{
Ap}(H,sq)\cap\text{ Ap}(H,w)$ since $x\notin\text{ Ap}(H,x)$ for any $x\in H$.

If $h\in\text{ Ap}(H,sp)\cap\text{ Ap}(H,sq)\cap\text{ Ap}(H,w)$ then
$h=\sum_{i=1}^{n-2}t_{i}h_{i}$ for $h-sp,h-sq,h-w$ cannot be in $H$. Further
since $2h_{i}\in\langle sp,sq,w\rangle$ for all $i$, $t_{i}\leq 1$. If two of
the $t_{i}$ are not zero, say, $i=1,2$, then we have
$h=2h_{1}-sp(x_{2}-x_{1})-sq(y_{2}-y_{1})-w(z_{2}-z_{1})+\sum_{i=3}^{n-2}h_{i}$.
By the fact that $h_{i}\in H$ are minimal generators, we have that one of
$(x_{2}-x_{1}),(y_{2}-y_{1}),(z_{2}-z_{1})$ must be negative. So, one of
$h-sp,h-sq,h-w$ must be in $H$ which is impossible. so, only one of $t_{i}\neq
0$. Hence, $h=h_{i}$ for some $i$ and so we get the other inclusion:
$\mathbf{h}\backslash\\{sp,sq,w\\}=\text{ Ap}(H,sp)\cap\text{
Ap}(H,sq)\cap\text{ Ap}(H,w)$. ∎

The proposition above establishes a close relationship between the lattice
path of a numerical semigroup $H\in KW(p,q,r_{1},r_{2},s)$ and its Apéry set.
In fact, the lattice path of $H$ can be exclusively determined by its Apéry
sets $\text{ Ap}(H,sp)$, $\text{ Ap}(H,sq)$, and $\text{ Ap}(H,w)$.
Consequently, this observation could facilitate deriving an upper bound for
the embedding dimension of any $H\in KW(p,q,r_{1},r_{2},s)$, as in Remark 2.

Kunz and Waldi show that for $H\in KW(p,q)$, the type of the semigroup ring
$k[H]$ equals $e(H)-1$. Contrasting this with the dimension three, consider
$H\in R(5,7,2,1,3)$ obtained by adding a gap $h$ of $\langle 15,21,17\rangle$.
In the following table. the first column consists of gaps $h$ such that
$H=\langle 15,21,17,h\rangle$, with embedding dimension $4$ has the
corresponding type in column $2$.

Choice of $h$ | $t(H)$
---|---
50,56,65,67, 71,73,82,86,88,103 | 3
35, 52 | 4

However, we show that for a class of the $h\in H$ in $KW(p,q,r_{1},r_{2},s)$,
we prove that the type is always $3$.

######  Example 5.5.

Consider Figure $6$ below. Take $H=\langle 36,44,29,221\rangle\in
KW(9,11,2,1,4)$ where $221$ corresponds to the lattice point $A=(1,2,2)$. Then
$PF(H)=\\{271,316,331\\}$ where $331,271,$ and $316$ correspond to the points
$I=(2,0,0),J=(0,3,0),$ and $K=(0,0,3)$, respectively.

Figure 6. $PF(\langle 36,44,29,221\rangle)$

######  Theorem 5.6.

Let $H=\langle sp,sq,w,h\rangle\in KW(p,q,r_{1},r_{2},s)$ with $h=F(S)-spx-
sqy-wz$. If $p_{z}:=F(S)-(z+1)w\not\in H$, then $t(H)=3$.

###### Proof.

We will show that

$PF(H)=\\{p_{x}:=F(S)-(x+1)sp,p_{y}:=F(S)-(y+1)sq,p_{z}\\}.$

  * Claim 1.

$p_{x},p_{y}\not\in H$. Suppose first that $p_{x}\in H$. Then $p_{x}=\alpha
sp+\beta sq+\gamma w+\delta h$ for some $\alpha,\beta,\gamma,\delta\in N$. By
the choice of $h$ to be in Kunz-Waldi class, $2h\in S$. $pX$ is a gap of $S$.
So, $\delta=1$. So, we get $(\alpha+1)sp+(\beta-y)sq+(\gamma-z)w=0$. This
means either $\beta<y$ or $\gamma<z$. If indeed $\gamma<z$, then
$(z-\gamma)w=(\alpha+1)sp+(\beta-y)sq$. So, $s$ must divide $z-\gamma$ but
this is impossible since $z<s$. Now if $\gamma\geq z$,
$0\leq(c-z)w=((y-\beta)q-(\alpha+1)p)s$. So, there exists $u\in\mathbb{N}$
such that $(y-\beta)q-(\alpha+1)p=wu=r_{1}pu+r_{2}qu\implies(y-\beta-
r_{2}u)q=(\alpha+1+r_{1}u)p>0\implies y>p$ a contradiction. So, $p_{x}\notin
H$. The argument for $p_{y}\not\in H$ is similar.

  * Claim 2.

$p_{i}+sp,p_{i}+sq,p_{i}+w,p_{i}+h\in H$ for all $1\leq i\leq 3$.
To see that $p_{1}+sp\in H$, we have the following

$\displaystyle p_{1}+sp$ $\displaystyle=F(S)-(x+1)sp+sp$
$\displaystyle=F(S)-xsp$ $\displaystyle=h+ysq+zw\in H$

Next, to see that $p_{1}+sq\in H$, we have

$\displaystyle p_{1}+sq$ $\displaystyle=F(S)-(x+1)sp+sq$
$\displaystyle=spq+sw-sp-sq-w-(x+1)sp+sq$ $\displaystyle=sp(q-x-2)+w(s-1)\in
H$

since $x\leq\lfloor q/2\rfloor-2\implies q-x-2\geq 0$. Thirdly, for
$p_{1}+w\in H$, we see

$\displaystyle p_{1}+w$ $\displaystyle=F(S)-(x+1)sp+w$ $\displaystyle=spq+sw-
sp-sq-w-(x+1)sp+w$ $\displaystyle=sp(q-x-2)+s(r_{1}p+r_{2}q)-sq$
$\displaystyle=sp(q-x-2+r_{1})+sq(r_{2}-1)\in H$

since $r_{2}\geq 1$.

Similarly, $p_{2}+sp=sq(p-y-2)+w(s-1)\in H$ since $y\leq\lfloor
p/2\rfloor-2\implies p-y-2\geq 0$, $p_{2}+sq=h+xsp+zw\in H$, and
$p_{2}+w=sq(p-y-2+r_{2})+sp(r_{1}-1)\in H$ as $r_{1}\geq 1$.

Next, $p_{3}+sp=w(s-z-2)+sq(p-1)\in H$ as $z\leq s-2$,
$p_{3}+sq=w(s-z-2)+sp(q-1)\in H$, and $p_{3}+w=h+xsp+ysq\in H$.

It remains to show that $p_{i}+h\in H$ for all $1\leq i\leq 3$. Well, recall
that $x\leq\frac{q-4}{2},y\leq\frac{p-4}{2},$ and $z\leq s-2$ so that

$\displaystyle p_{1}+h$ $\displaystyle=sp(q-2x-3)+sq(p-y-2)+w(2s-z-2)\in H,$
$\displaystyle p_{2}+h$ $\displaystyle=sp(q-x-2)+sq(p-2y-3)+w(2s-z-2)\in H,$

and

$\displaystyle p_{3}+h$ $\displaystyle=sp(q-x-2)+sq(p-y-2)+w(2s-2z-2)\in H.$

  * Claim 3.

No other gap of $H$ is in $PF(H)$. Any gap of $H$ is of the form $g=F(S)-spa-
sqb-wc$ for some $(a,b,c)\in\mathbb{N}^{3}$. Suppose $g$ is different from
$p_{1},p_{2},p_{3}$. It is not of the form $F(S)-(x+1+i)sp$ for $i>0$ because
$F(S)-(x+1+i)sp+sp=p_{1}-(i-1)sp\in H\implies p_{1}\in H$, a contradiction to
Claim 1. Similarly, $g$ is not of the form $F(S)-(y+1+i)sq$ or $F(S)-(z+1+i)w$
for $i\geq 0$. Further, one of the following must happen: $a>x,b>y,c>w$.
Otherwise, if $a\leq x,b\leq y,c\leq z$, then $g=h+(x-a)sp+(y-b)sq+(z-c)w\in
H$.

Suppose $g=F(S)-spa-sqb-wc\in PF(H)$ with $a=x+j$ for some
$j\in\mathbb{N}\backslash\\{0\\}$, and one of $b,c$ is non-zero. Then
$p_{1}=g+sp(j-1)+sqb+wc\in H.$ If $b=y+j$ for some $j\geq 1$, then
$p_{2}=g+spa+sq(j-1)+wc\in H.$ Finally, if $c=z+j$ for some $j\geq 1$, then
$p_{3}=g+spa+sqb+w(j-1)\in H.$ Each of these cases is a contradiction since
$p_{1},p_{2},p_{3}\not\in H$. So $g$ cannot be different from $p_{1},p_{2}$ or
$p_{3}$.

Thus, $PF(H)=\\{p_{1},p_{2},p_{3}\\}$ proving that the type of $H$ is $3$.

∎

The condition $p_{3}\not\in H$ is necessary as seen in the example below.

######  Example 5.7.

Take $H=\langle 27,33,29,152\rangle\in KW(9,11,2,1,3)$. Here,
$152=s(pq+w)-(x+1)sp-(y+1)sqy-(z+1)w$ for $(x,y,z)=(3,1,1)$ but $t(H)=4$. In
this case, $p_{3}=237\in H$ and $PF(H)=\\{p_{1},p_{2},183,204\\}$.

Further, the theorem still may not hold if $H\in
R(p,q,r_{1},r_{2},s)\backslash KW(p,q,r_{1},r_{2},s)$.

######  Example 5.8.

Take $H=\langle 15,21,17,37\rangle\in R(5,7,2,1,3)$. Here,
$37=s(pq+w)-(x+1)sp-(y+1)sqy-(z+1)w$ for $(x,y,z)=(3,1,0)$, so that
$3>\frac{7-4}{2}=1.5$, and $t(H)=4$.

With this in mind, we ask the following questions:

######  Question 1.

What are the conditions on the gaps $h_{i}$ that will yield an explicit
formula for the type of $H$?

######  Question 2.

Let $h_{i}=spx+sqy+wz=s(pq+w)-spx_{i}-sqy_{i}-wz_{i}$, where
$x_{i}<{\frac{q}{2}},y_{i}<{\frac{p}{2}},z<s$. In particular, what is the type
of $H=(sp,sq,w,h_{i},1\leq i\leq n-2)\in KW(p,q,s,w)$ ?

Theorem 1.1 gives the number of generators for the relation ideal of any $H\in
KW(p,q)$. Consider the following tables, In the left one, the first column
consists of gaps $h$ such that $H=\langle 15,21,17,h\rangle$, with embedding
dimension $4$, and the second column has the corresponding number of minimal
generators for its relation ideal. In the next table, the first column
consists of $h^{\prime}$ such that $H^{\prime}=\langle
15,21,17,73,h^{\prime}\rangle$, and the second column is
$\mu(I_{H^{\prime}})$, the number of minimal generators of $I_{H^{\prime}}$.

Choice of $h$ | $\mu(I_{H})$
---|---
35, 50, 52, 56, 65, 67, 71, 73, 82, 86, 88 | 6
103 | 7
Choice of $h^{\prime}$ | $\mu(I_{H})$
---|---
67 | 9
50, 71, 82, 86 | 10
65 | 11

This prompts the question:

######  Question 3.

What is the number of minimal generators for the relation ideal of $H\in
KW(p,q,r_{1},r_{2},s)$?

Even when the embedding dimension of $H$ is $4$, we may have many different
numbers of generators for its ideal as seen in the table above.

## References

  * [1] Bresinsky, H., Monomial Gorenstein ideals, Manuscripta Math 429 (1979). 159–181. DOI: https://doi.org/10.1007/BF01303625.
  * [2] P. Dey, H. Srinivasan, Principal matrices of numerical semigroups, Women in commutative algebra Assoc. Women Math. Ser. 29 (2021), 233–256. DOI: https://doi.org/10.1007/978-3-030-91986-3_9.
  * [3] P. Gimenez, H. Srinivasan, A note on Gorenstein monomial curves, Bulletin of the Brazilian Mathematical Society, New Series Springer Science and Business Media LLC 45 (2014), 671–678. DOI: http://dx.doi.org/10.1007/s00574-014-0068-4.
  * [4] E. Kunz, R. Waldi, Geometrical illustration of numerical semigroups and of some of their invariants, Semigroup Forum 89 (2014), 664–691. DOI: http://dx.doi.org/10.1007/s00233-014-9599-7.
  * [5] E. Kunz, R. Waldi, On the deviation and the type of certain local Cohen–Macaulay rings and numerical semigroups, Journal of Algebra 478 (2017), 397–409. DOI: https://doi.org/10.1016/j.jalgebra.2017.01.041.


[1]Danchneg Lu

These authors contributed equally to this work.

1]School of Mathematical Science, Soochow University, No. 1 Shizhi Street,
Suzhou, 215021, Jiangsu, P.R.China

# Correction to: Powers of the vertex cover ideals (Collect. Math. 65 (2014)
169–181).

<EMAIL_ADDRESS>Zexin Wang<EMAIL_ADDRESS>[

###### Abstract

We point out an essential gap in the proof of one of main results in [3] and
then give a corrected proof for it.

###### keywords:

Cohen-Macaulay, Cactus graph, Weakly polymatroidal, Vertex cover ideal, Power

In [3] F. Mohammadi succeeded in classifying all the Cohen- Macaulay cactus
graphs. Based on this result, he proved in [3, Theorem 4.3] that if $G$ is a
Cohen-Macaulay cactus graph then all the powers of the vertex cover ideal
$J(G)$ of $G$ are weakly polymatroidal. In this note we illustrate by an
example that there exists an essential gap in the proof of [3, Theorem 4.3]
and then present a corrected proof for this result.

We adopt the notation from the original paper [3], which the reader should
have at hand when reading this note. First of all, We explain why some parts
of the original proof of [3, Theorem 4.3] is not correct.

There were several cases to consider in the proof. In case 4, it is assumed
that $z=y_{i3}$, then one deduces that
$\\{y_{i1},y_{i2},y_{i5}\\}\subseteq\mathrm{supp}(g_{j})$ for some $1\leq
j\leq k$. Let us see the following example.

######  Example 1.

Let $G$ be a 5-cycle whose vertices are labeled
$y_{1},y_{4},y_{2},y_{3},y_{5}$ in order. Then
$f=y_{1}y_{2}y_{3}^{2}y_{4}y_{5}=(y_{1}y_{2}y_{3})(y_{3}y_{4}y_{5})$ and
$g=y_{1}y_{2}y_{3}y_{4}^{2}y_{5}=(y_{2}y_{4}y_{5})(y_{1}y_{3}y_{4})$ are
minimal monomial generators of $J(G)^{2}$. We may write
$g_{1}=y_{2}y_{4}y_{5}$ and $g_{2}=y_{1}y_{3}y_{4}$. Note that
$\deg_{y_{i}}f=\deg_{y_{i}}g$ for $i=1,2$ and $\deg_{y_{3}}f>\deg_{y_{3}}g$.
According to the proof of case 4 in [3], there exists some $g_{j}$ such that
$\\{y_{1},y_{2},y_{5}\\}\subseteq\mathrm{supp}(g_{j})$ and so $y_{3}g/y_{5}\in
J(G)^{2}$. However, it is clear that
$\\{y_{1},y_{2},y_{5}\\}\nsubseteq\mathrm{supp}(g_{j})$ for $j=1,2$ and
$y_{3}g/y_{5}\notin J(G)^{2}$. Furthermore, since $\frac{g}{y_{1}y_{2}y_{5}}$
does not belong to $J(G)$ , it follows that $g$ can not be written as
$g=g^{\prime}_{1}g^{\prime}_{2}$ such that $g^{\prime}_{i}\in J(G)$ for
$i=1,2$ and $\\{y_{1},y_{2},y_{5}\\}\subseteq\mathrm{supp}(g^{\prime}_{i})$
for some $i$.

This example shows the proof of case 4 is not correct. The proof of case 5 is
not correct in a similar way. In the sequel, we give revised proofs for cases
4 and 5.

######  Theorem 1.

([3, Theorem 4.3]) Let $G$ be a Cohen-Macaulay cactus graph. Then $J(G)^{k}$
is weakly polymatroidal for all $k\geq 1$.

###### Proof.

Recall that a cactus graph is a connected graph in which each edge belongs to
at most one cycle. As in the original proof of [3, Theorem 4.3], we may assume
that $V(G)$ is the disjoint union of

$F_{1},\ldots,F_{m},G_{1},\ldots,G_{n},L_{1},\ldots,L_{t}$

such that the induced graph of $G$ on $F_{i}$ is a clique of size 3 or 2, the
induced graph of $G$ on $G_{j}$ is a basic 5-cycle, and $L_{l}$ is an edge
which belongs to a 4-cycle of $G$ for each $i,j,l$. Here, a 5-cycle of a graph
$G$ is basic if it does not contain two adjacent vertices of degree 3 or more
in $G$, see [1].

Consider the following ordering of the variables (corresponding to the
vertices of $G$):

$x_{11}>\cdots>x_{1k_{1}}>\cdots>x_{m1}>\cdots>x_{mk_{m}}>y_{11}>\cdots>y_{15}>$
$\cdots>y_{n1}>\cdots>y_{n5}>z_{11}>z_{12}>\cdots>z_{t1}>z_{t2},$

where $F_{i}=\\{{x_{i1},\ldots,x_{ik_{i}}}\\},2\leq k_{i}\leq 3$ and
${x_{ib_{i}},\ldots,x_{ik_{i}}}$ are the free vertices of $F_{i}$ for all $i$,
and $y_{j1},y_{j4},y_{j2},y_{j3},y_{j5}$ are the vertices of $G_{j}$
successively such that the vertices $y_{j3},y_{j4},y_{j5}$ are of degree two
for all $j$, and $z_{i1},z_{i2}$ are the vertices of $L_{i}$ of degree two for
all $i$. Note that for each $i\in[n]$, each minimal vertex cover $C$ of $G$
contains exactly one of the following subsets:

$\\{y_{i1},y_{i2},y_{i5}\\},\\{y_{i2},y_{i4},y_{i5}\\},\\{y_{i1},y_{i2},y_{i3}\\},\\{y_{i1},y_{i3},y_{i4}\\},\\{y_{i2},y_{i4},y_{i5}\\}$

Now, let $f=f_{1}\cdots f_{k}$ and $g=g_{1}\cdots g_{k}$ be monomials in the
minimal generating set of $J(G)^{k}$ with $f_{s},g_{s}\in J(G)$ for $1\leq
s\leq k$. Suppose that there exists a variable $z$ such that
$\mathrm{deg}_{z^{{}^{\prime}}}f=\mathrm{deg}_{z^{{}^{\prime}}}g$ for every
variable $z^{{}^{\prime}}>z$ and $\mathrm{deg}_{z}f>\mathrm{deg}_{z}g$. We
only need to find a variable $w<z$ such that $zg/w\in J(G)^{k}$ in the cases
where $z=y_{i3}$ and where $z=y_{i4}\mbox{ or }y_{i5}$ for some $i$, which
correspond to case 4 and case 5 of the original proof, respectively. To this
end, we introduce some additional notation.

Let $i$ be the number mentioned above. First, for each triple $\\{a,b,c\\}$
such that $\\{y_{ia},y_{ib},y_{ic}\\}$ is a minimal vertex cover of $G_{i}$,
we set

$f_{abc}=|\\{1\leq s\leq
k:\\{y_{ia},y_{ib},y_{ic}\\}\subseteq\mathrm{supp}(f_{s})\\}|$

and

$g_{abc}=|\\{1\leq s\leq
k:\\{y_{ia},y_{ib},y_{ic}\\}\subseteq\mathrm{supp}(g_{s})\\}|.$

Next, we denote by $T$ the induced subgraph of $G$ on the subset
$V(G)\setminus\\{y_{i3},y_{i4},y_{i5}\\}$, and for $a=1,2,$ we set

$T_{a}=\\{z\in V(T)\setminus\\{y_{i1},y_{i2}\\}\>\;\mbox{ there exists a path
in }T\mbox{ connecting }z\mbox{ with }y_{ia}\\}.$

Since $G$ is a cactus graph, we have the subsets $T_{1},\\{y_{i1},y_{i2}\\}$
and $T_{2}$ are pairwise disjoint and $V(T)=T_{1}\cup\\{y_{i1},y_{i2}\\}\cup
T_{2}$.

Case  $z=y_{i3}$: If $g_{125}\neq 0$, there exists $s\in\\{1,\cdots,k\\}$ such
that $\\{y_{i1},y_{i2},y_{i5}\\}\subseteq\mathrm{supp}(g_{s})$. Since the
subset $(\mathrm{supp}(g_{s})\backslash\\{y_{i5}\\})\cup\\{y_{i3}\\}$ is again
a minimal vertex cover of $G$, we have $y_{i3}g/y_{i5}\in J(G)^{k}$ and so we
are done. Note that $g_{125}\neq 0$ if $k=1$, we assume now that $g_{125}=0$
and $k\geq 2$.

Since $\mathrm{deg}_{y_{ia}}f=\mathrm{deg}_{y_{ia}}g$ for $a=1,2$ and
$\mathrm{deg}_{y_{i3}}f>\mathrm{deg}_{y_{i3}}g$, we have the following
formulas:

  * •

$f_{134}+f_{123}+f_{125}=g_{134}+g_{123}+g_{125}$; ➊

  * •

$f_{245}+f_{123}+f_{125}=g_{245}+g_{123}+g_{125};$ ➋

  * •

$f_{134}+f_{123}+f_{345}>g_{134}+g_{123}+g_{345};$ ➌

  * •

$f_{134}+f_{245}+f_{123}+f_{125}+f_{345}=g_{134}+g_{245}+g_{123}+g_{125}+g_{345}=k.$
➍

Subtracting ➊ from ➍ and subtracting ➋ from ➍, we obtain

  * •

$f_{245}+f_{345}=g_{245}+g_{345}$; ➎

  * •

$f_{134}+f_{345}=g_{134}+g_{345}$. ➏

On the other hand, by combining ➌ and ➊ with the assumption $g_{125}=0$, we
have

$f_{134}+f_{123}+f_{345}>g_{134}+g_{123}+g_{345}=f_{134}+f_{123}+f_{125}+g_{345},$

and so $f_{345}>f_{125}+g_{345}\geq g_{345}$. From this together with ➎ and ➏,
it follows that $f_{134}<g_{134}$ and $f_{245}<g_{245}$. This particularly
implies $g_{134}>0$ and $g_{245}>0$, and thus, there exist
$p,q\in\\{1,\cdots,k\\}$ with $p\neq q$ such that
$\\{y_{i2},y_{i4},y_{i5}\\}\subseteq g_{p}$ and
$\\{y_{i1},y_{i3},y_{i4}\\}\subseteq g_{q}$. Say $p=1$ and $q=2$. To prove
$y_{i3}g/y_{i4}$ belongs to $J(G)^{k}$, we only need to prove that
$y_{i3}g_{1}g_{2}/y_{i4}$ belongs to $J(G)^{2}$.

We may write $g_{1},g_{2}$ as follows:

$g_{1}=y_{i2}y_{i4}y_{i5}u_{1}u_{2}\mbox{\quad
and\quad}g_{2}=y_{i1}y_{i3}y_{i4}v_{1}v_{2},$

where $\mathrm{supp}(u_{i})\cup\mathrm{supp}(v_{i})\subseteq T_{i}$ for
$i=1,2$. Then there are the following decomposition:

$y_{i3}g_{1}g_{2}/y_{i4}=(y_{i3}y_{i4}y_{i5}u_{1}u_{2})(y_{i1}y_{i2}y_{i3}v_{1}v_{2})=(y_{i3}y_{i4}y_{i5}u_{1}v_{2})(y_{i1}y_{i2}y_{i3}v_{1}u_{2}).$

We next check that both $\mathrm{supp}(y_{i3}y_{i4}y_{i5}u_{1}v_{2})$ and
$\mathrm{supp}(y_{i1}y_{i2}y_{i3}v_{1}u_{2})$ are vertex covers of $G$. To
this end, we denote $V_{1}=\mathrm{supp}(y_{i3}y_{i4}y_{i5}u_{1}v_{2})$ and
$V_{2}=\mathrm{supp}(y_{i1}y_{i2}y_{i3}v_{1}u_{2})$. Let $e=\\{z_{1},z_{2}\\}$
be an edge of $G$.

If $e\subseteq V(G_{i})$, then it is clear that $V_{1}\cap e\neq\emptyset$ and
$V_{2}\cap e\neq\emptyset$.

If $z_{1}=y_{i1}$ and $z_{2}\in T_{1}$ then $z_{2}\in\mathrm{supp}(u_{1})\cap
e$. This implies $V_{1}\cap e\neq\emptyset$ and $V_{2}\cap e\neq\emptyset$;
Similarly, we have if $z_{1}=y_{i2}$ and $z_{2}\in T_{2}$ then $V_{1}\cap
e\neq\emptyset$ and $V_{2}\cap e\neq\emptyset$.

Finally suppose that $e\cap V(G_{i})=\emptyset$. Then either $e\subseteq
E(T_{1})$ or $e\subseteq E(T_{2})$. In the case that $e\subseteq E(T_{1})$, we
have $\mathrm{supp}{(u_{1})}\cap e\neq\emptyset$ and
$\mathrm{supp}{(v_{1})}\cap e\neq\emptyset$ and so $V_{1}\cap e\neq\emptyset$
and $V_{2}\cap e\neq\emptyset$. The case that $e\subseteq E(T_{2})$ can be
proved similarly.

Thus, both $V_{1}$ and $V_{2}$ are vertex covers of $G$ indeed and so
$y_{i3}g_{1}g_{2}/y_{i4}$ belongs to $J(G)^{2}$, as required.

Case $z=y_{i4}\mbox{ or }y_{i5}$: Since the case where $z=y_{i5}$ is
impossible actually, we only need to consider the case where $z=y_{i4}$.
Moreover we may assume that $k\geq 2$ as in the case $z=y_{i3}$. Because
$\mathrm{deg}_{y_{ia}}f=\mathrm{deg}_{y_{ia}}g$ for $a=1,2,3$ and
$\mathrm{deg}_{y_{i4}}f>\mathrm{deg}_{y_{i4}}g$, we have the following
formulas:

  * •

$f_{134}+f_{123}+f_{125}=g_{134}+g_{123}+g_{125}$; ➊

  * •

$f_{245}+f_{123}+f_{125}=g_{245}+g_{123}+g_{125};$ ➋

  * •

$f_{134}+f_{123}+f_{345}=g_{134}+g_{123}+g_{345};$ ➌

  * •

$f_{134}+f_{245}+f_{345}>g_{134}+g_{245}+g_{345};$ ➍

  * •

$f_{134}+f_{245}+f_{123}+f_{125}+f_{345}=g_{134}+g_{245}+g_{123}+g_{125}+g_{345}=k.$
➎

Subtracting ➊, ➋ and ➌ from ➎ respectively, we have

  * •

$f_{245}+f_{345}=g_{245}+g_{345}$; ➏

  * •

$f_{134}+f_{345}=g_{134}+g_{345}$; ➐

  * •

$f_{245}+f_{125}=g_{245}+g_{125}$. ➑

We also obtain $f_{245}>g_{245}$ by substituting ➐ into ➍. From this together
with ➏ and ➑, it follows that $f_{345}<g_{345}$ and $f_{125}<g_{125}.$ In
particular, $g_{345}>0$ and $g_{125}>0$. Consequently, there exist
$p,q\in\\{1,\cdots,k\\}$ such that $\\{y_{i3},y_{i4},y_{i5}\\}\subseteq g_{p}$
and $\\{y_{i1},y_{i2},y_{i5}\\}\subseteq g_{q}$. Say $p=1$ and $q=2$. It
suffices to prove that the monomial $y_{i4}g_{1}g_{2}/y_{i5}$ belongs to
$J(G)^{2}$.

For this, we decompose $g_{1}$ and $g_{2}$ as follows:

$g_{1}=y_{i3}y_{i4}y_{i5}u_{1}u_{2}\mbox{\quad
and\quad}g_{2}=y_{i1}y_{i2}y_{i5}v_{1}v_{2},$

where $\mathrm{supp}(u_{i})\cup\mathrm{supp}(v_{i})\subseteq T_{i}$ for
$i=1,2$. This implies

$y_{i4}g_{1}g_{2}/y_{i5}=(y_{i3}y_{i4}y_{i5}u_{1}u_{2})(y_{i1}y_{i2}y_{i4}v_{1}v_{2})=(y_{i2}y_{i4}y_{i5}u_{1}v_{2})(y_{i1}y_{i3}y_{i4}v_{1}u_{2}).$

We can check that both $\mathrm{supp}(y_{i2}y_{i4}y_{i5}u_{1}v_{2})$ and
$\mathrm{supp}(y_{i1}y_{i3}y_{i4}v_{1}u_{2})$ are vertex covers of $G$, as in
the case where $z=y_{i3}$. Hence $y_{i4}g_{1}g_{2}/y_{i5}$ belongs to
$J(G)^{2}$. This finishes the proof. ∎

######  Remark 1.

The method used in our proof of this note depends heavily on the condition
that every edge of $G$ belongs to at most cycle of $G$. The gap of the
original proof in [3] was found when we tried to use the idea in the proof to
show that $J(G)^{k}$ is weakly polymatroidal for all $k\geq 1$ if $G$ is a
Cohen-Macaulay graph of large girth, whose structure was described explicitly
in [1]. But we failed in this regard and we can only prove in [2, Proposition
3.6] that $J(G)$ is weakly polymatroidal for such graphs.

## Declarations

  * •

Funding: This work was supported by National Natural Science Foundation of
China (Grant No. 11971338)

  * •

The authors have no competing interests to declare that are relevant to the
content of this article.

  * •

We would like to express our sincere thanks to the referee, whose comments
improved the presentation of the paper greatly.

## References

  * [1] Hoang, D.T., Minh, N.C., Trung, T.N., Cohen-Macaulay graphs with large girth. J. Algebra Appl. 14 (2015), 1550112
  * [2] Lu, D., Wang, Z., On powers of cover ideals of graphs. to appear Osaka Journal of mathematics
  * [3] Mohammadi, F., Powers of the vertex cover ideals, Collect. Math. 65, 169–181 (2014)


11institutetext: University of Zurich, Winterthurerstrasse, 8057 Zurich,
WWW home page: https://www.math.uzh.ch/aa/

# Existence and Cardinality of $k$-Normal Elements in Finite Fields

Simran Tinani  Joachim Rosenthal

###### Abstract

Normal bases in finite fields constitute a vast topic of large theoretical and
practical interest. Recently, $k$-normal elements were introduced as a natural
extension of normal elements. The existence and the number of $k$-normal
elements in a fixed extension of a finite field are both open problems in full
generality, and comprise a promising research avenue. In this paper, we first
formulate a general lower bound for the number of $k$-normal elements,
assuming that they exist. We further derive a new existence condition for
$k$-normal elements using the general factorization of the polynomial
$x^{m}-1$ into cyclotomic polynomials. Finally, we provide an existence
condition for normal elements in ${\mathbb{F}_{q^{m}}}$ with a non-maximal but
high multiplicative order in the group of units of the finite field.

###### Keywords:

Finite fields Normal bases.

##  1 Introduction

Let $q$ denote a power of a prime $p$, and ${\mathbb{F}_{q}}$ denote the
finite field of order $q$. If $\mathbb{F}$ is an extension field of the field
$\mathbb{K}$, we denote by $\mathrm{Gal}(\mathbb{F}/\mathbb{K})$ the Galois
group of the extension field $\mathbb{F}$ over $\mathbb{K}$. We are interested
in studying elements in a finite extension ${\mathbb{F}_{q^{m}}}$ of degree
$m$ over ${\mathbb{F}_{q}}$. An element $\alpha\in{\mathbb{F}_{q^{m}}}$ is
called a normal element over over ${\mathbb{F}_{q}}$ if all its Galois
conjugates, i.e. the $m$ elements
$\\{\alpha,\alpha^{q},\ldots,\alpha^{q^{m-1}}\\}$, form a basis of
${\mathbb{F}_{q^{m}}}$ as a vector space over ${\mathbb{F}_{q}}$. A basis of
this form is called a normal basis.

We let $\phi$ denote the usual Euler-phi function for integers. Let
$f\in{\mathbb{F}_{q}}[x]$ be a polynomial with positive degree $n$. Then
$\Phi_{q}(f)$ is defined to be the cardinality of the ring
$\left(\frac{{\mathbb{F}_{q}}[x]}{\langle f\rangle}\right)^{\times},$ where
$\langle f\rangle$ denotes the ideal generated by $f$ in
${\mathbb{F}_{q}}[x]$. In other words, $\Phi_{q}(f)$ is the number of
polynomials co-prime to $f$ and with degree less than $n$. It is well known
that normal elements exist in every finite extension ${\mathbb{F}_{q^{m}}}$ of
${\mathbb{F}_{q}}$ and that there are precisely $\Phi_{q}(x^{m}-1)$ normal
elements, and thus $\frac{\Phi_{q}(x^{m}-1)}{m}$ normal bases in
${\mathbb{F}_{q^{m}}}$ [14, Theorem 2.35, Theorem 3.73], [8], [17]).

Normal elements are a topic of major significance and interest because they
offer an avenue for efficient arithmetic in a finite field ${\mathbb{F}_{q}}$:
for instance, raising an element to the power $q$ is simply a cyclic shift in
normal base representation. Normal bases and related concepts such as optimal
normal bases and self-dual normal bases find several applications, both
theoretical and practical. We refer the interested reader to [1], [6], and
[15] for more on this topic.

In [9], Huczynska et al. introduced the concept of $k$-normal elements as a
natural generalization of normal elements. One of the many equivalent ways to
define a $k$-normal element $\alpha\in{\mathbb{F}_{q^{m}}}$ is as an element
whose conjugates
$\\{\alpha,\alpha^{q},\alpha^{q^{2}},\ldots\alpha^{q^{m-1}}\\}$ span a vector
space of dimension $m-k$ over ${\mathbb{F}_{q}}$. It is then of natural
interest to examine the existence and the number of $k$-normal elements. These
problems have been shown to be closely tied to the factorization of the
polynomial $x^{m}-1$ [9]. There are numerous known results on bounds on the
number of ($0$-)normal elements, several of which build on the lower bounds
proved in [5] using properties of the function $\Phi_{q}$ (see also the
improvements on these results in [7]). For arbitrary $k$, $0<k<m-1$, neither a
general rule for the existence of $k$-normal elements nor a general formula
for their number, when they exist, is known.

Huczynska et al. [9] have used the approach of Frandsen [5] to give a lower
bound on the number of $k$-normal elements which holds asymptotically, as well
as an upper bound which holds in general. However, both their upper and lower
bounds depend directly on the number of divisors of $x^{m}-1$ with degree
$m-k$, and are thus difficult to calculate. Moreover, when $x^{m}-1$ has no
divisor of degree $m-k$, the bounds equal zero, which means that the statement
about lower bounds does not yield any existence result.

In a recent paper, Saygi et al. [20] give formulas (in terms of $q$ and $m$)
for the number of $k$-normal elements for cases where $m$ is a power of a
prime or of the form $2^{v}\cdot r$ where $r\neq 2$ is a prime and $v\geq 1$,
using known results on the explicit factorization of cyclotomic polynomials.
In particular, their formulae guarantee existence for certain cases. A recent
result by Reis [19, Theorem 5.5] provides a sufficient condition on $m$ for
which $k$-normal elements exist for every $0\leq k\leq m$.

In 1987, Lenstra and Schoof [13] proved (also see partial proofs by Carlitz
[2] and Davenport [4]) what is known as the Primitive Normal Basis theorem,
which states the existence of an element that is simultaneously normal and
primitive (i.e. has multiplicative order $q^{m}-1$ in
$\mathbb{F}_{q^{m}}^{*}$). By extension, elements that have high
multiplicative orders and also span large subspaces along with their
conjugates are of interest. In particular, problems along this line have found
mention in [9], [11], [12] and [16]. The question of the existence of elements
in ${\mathbb{F}_{q^{m}}}$ that are both $1$-normal over ${\mathbb{F}_{q}}$ and
primitive has been answered in entirety in [19], after a partial proof and
formulation of the problem in [9].

In this paper, we first present an existence condition for $k$-normal elements
(over ${\mathbb{F}_{q}}$) in ${\mathbb{F}_{q^{m}}}$ based on inequalities
involving $m$ and $k$. It turns out that under certain constraints on $m$
(loosely put, $m$ must have a sufficiently large common divisor with
$q^{m}-1$), $k$-normal elements exist for $k$ above a minimum lower bound.
This result is independent of the factorization of $x^{m}-1$. Moreover, the
conditions on $m$ and $q$ required are weaker than the special forms required
in [20], and also cannot be derived from the conditions in [18, Theorem 5.5].
Thus, this result extends to cases not previously covered.

We further present a result that guarantees a general lower bound on the
number of $k$-normal elements (for arbitrary $0\leq k\leq m-1$), provided that
they exist. This proves a link between the number of normal elements and the
number of $k$-normal elements for $k>0$. Since this result does not make any
additional assumption about $k$, $q$ or $m$, it is not derivable from any of
the known formulas on the number of $k$-normal elements.

Our final contribution is an existence condition for ($0$-)normal elements of
multiplicative order $\frac{q^{m}-1}{q-1}$ in ${\mathbb{F}_{q^{m}}}$ when $m$
and $q-1$ are co-prime. Using the terminology of [16], this is the same as
talking about $0$-normal, $(q-1)$-primitive elements. With this result, we
answer a special case of Problem 6.4 posed in [9], which deals with
high-(multiplicative) order $k$-normal elements in ${\mathbb{F}_{q^{m}}}$ over
${\mathbb{F}_{q}}$. Our proof follows the method used by Lenstra and Schoof in
in proving the Primitive Normal Basis Theorem [13].

##  2 Preliminaries

###### Definition 1

An element $\alpha\in{\mathbb{F}_{q^{m}}}$ is called $k$-normal if

$\dim_{\mathbb{F}_{q}}\left(\mathrm{span}_{\mathbb{F}_{q}}\left\\{\alpha,\alpha^{q},\ldots,\alpha^{q^{m-1}}\right\\}\right)=m-k$

###### Remark 1

It is clear form the definition that an element $\alpha$ is $0$-normal if and
only if it is normal by the usual definition. Also, the only $m$-normal
element in ${\mathbb{F}_{q^{m}}}$ is 0.

Given $\alpha\in{\mathbb{F}_{q^{m}}}$, we denote by $\mathrm{ord}(\alpha)$ the
usual multiplicative order of $\alpha$ in the group $\mathbb{F}_{q^{m}}^{*}$.
${\mathbb{F}_{q^{m}}}$ may be seen as a module over the ring
${\mathbb{F}_{q}}[x]$, under the action

$\displaystyle\sum_{i=0}^{n}a_{i}x^{i}\cdot\alpha=\sum_{i=0}^{n}a_{i}\alpha^{q^{i}},\;\alpha\in{\mathbb{F}_{q^{m}}}$
(1)

In other words, the value of the image of $\alpha$ under the action of a
polynomial $f(x)=\sum_{i=0}^{n}a_{i}x^{i}$ is the evaluation of $\alpha$ at
the $q$-associate [14, Definition 3.58] of $f(x)$. Note that this is the same
as the action of ${\mathbb{F}_{q}}$-linear maps on ${\mathbb{F}_{q^{m}}}$.
Through this module structure, we also have another concept of order, as
defined in [13] as an additive analogue of the multiplicative order.

###### Definition 2

Define the function

$\mathrm{Ord}:{\mathbb{F}_{q^{m}}}\rightarrow{\mathbb{F}_{q}}[x]$

as follows. For any $\alpha\in{\mathbb{F}_{q^{m}}}$, $\mathrm{Ord}(\alpha)$ is
the unique monic polynomial generating the annihilator of $\alpha$ under the
action defined by Equation (1), i.e.

$\mathrm{Ann}(\alpha)=\langle\mathrm{Ord}(\alpha)\rangle\text{ in
}{\mathbb{F}_{q}}[x]$

We now state an important result which provides several equivalent
characterizations of $k$-normal elements.

###### Theorem 2.1

[9, Theorem 3.2] Let $\alpha$ be an element of ${\mathbb{F}_{q^{m}}}$ and

$g_{\alpha}(x):=\sum_{i=0}^{m-1}\alpha^{q^{i}}\cdot
x^{m-1-i}\in{\mathbb{F}_{q^{m}}}[x]$

Then the following conditions are equivalent:

  1. 1.

$\alpha$ is $k$-normal.

  2. 2.

$\gcd(x^{m}-1,\;g_{\alpha}(x))$ over ${\mathbb{F}_{q^{m}}}$ has degree $k$

  3. 3.

$\deg(\mathrm{Ord}(\alpha))=m-k$.

  4. 4.

The matrix $A_{\alpha}$ defined below has rank $m-k$.

$A_{\alpha}=\begin{bmatrix}\alpha&\alpha^{q}&\alpha^{q^{2}}&\cdots&\alpha^{q^{m-1}}\\\
\alpha^{q^{m-1}}&\alpha&\alpha^{q}&\cdots&\alpha^{q^{m-2}}\\\
\vdots&\vdots&\cdots&\vdots&\vdots\\\
\alpha^{q}&\alpha^{q^{2}}&\alpha^{q^{3}}&\cdots&\alpha\\\ \end{bmatrix}$

The following result on the number of $k$-normal elements will also prove
useful.

###### Theorem 2.2

[9, Theorem 3.5] The number of $k$-normal elements of ${\mathbb{F}_{q^{m}}}$
over ${\mathbb{F}_{q}}$ equals 0 if there is no $h\in{\mathbb{F}_{q}}[x]$ of
degree $m-k$ dividing $x^{m}-1$; otherwise it is given by

$\sum_{\begin{subarray}{c}h\mid x^{m}-1\\\
\deg(h)=m-k\end{subarray}}\Phi_{q}(h),$ (2)

where divisors are monic and polynomial division is over ${\mathbb{F}_{q}}$.

It is known that $x^{m}-1$ factorizes over ${\mathbb{F}_{q}}$ into the set of
cyclotomic polynomials of degrees dividing $m$ [14, Theorem 2.45]. Moreover,
for $p\nmid d$ (recall that $p$ is defined as
$p=\mathrm{char}({\mathbb{F}_{q}})$), the irreducible factors of the
cyclotomic polynomial $Q_{d}(x)$ each has degree $\frac{\phi(d)}{r}$, where
$r$ is the multiplicative order of $d\mod q$ [14, Theorem 2.47]. Since there
is also no known closed formula for this number, there is no closed-form
complete factorization (i.e. factorization into irreducibles) of $x^{m}-1$
over ${\mathbb{F}_{q}}$. Thus, the above theorem does not give direct answers
about the existence of $k$-normal elements for $k>0$. However, it may be used
to ascertain the existence of $k$-normal elements for certain values of $k$.
In the next two sections, we look at some interesting results on $k$-normal
elements which can be derived in certain special cases using Thereom 2.

##  3 Cardinality of $k$-Normal Elements

For $k=0$, the formula in Thereom 2 yields the well-known value $\Phi_{q}(m)$
for the number of normal elements over ${\mathbb{F}_{q}}$ in
${\mathbb{F}_{q^{m}}}$ [14, Theorem 3.37]. Since $x^{m}-1$ always has the
divisor $x-1$ of degree 1 and hence also a divisor of degree $m-1$ (and since
$\Phi_{q}(f(x))\neq 0$ for any nonzero polynomial $f(x)$), we always have
1-normal and $(m-1)$-normal elements in ${\mathbb{F}_{q^{m}}}$. It has been
observed in [9] that the only values of $k$ for which $k$-normal elements are
guaranteed to exist for every pair $(q,\;m)$ are 0, 1 and $m-1$. In fact, as
noted in [19], if $q$ is a primitive root modulo $m$, $\frac{x^{m}-1}{x-1}$ is
irreducible and so for $1<k<m-1$, $k$-normal elements do not exist.

In certain other cases, it is possible to use information about the
factorization of $x^{m}-1$ along with Theorem 2 to gain insights into the
number of $k$-normal elements for different values of $k$. In [20], the
authors provide explicit formulas for $k$-normal elements for degrees $m$ that
are either prime powers or numbers of the form $2^{v}\cdot r$, for a prime
$r\neq 2$, under certain other constraints $q$ and $m$. Below we state one of
their noteworthy results.

######  Proposition 1 ([20, Proposition 1])

Let $\mathrm{char}({\mathbb{F}_{q}})=p$ and $n=p^{r}$ for some positive
integer $r$. Then the number of $k$-normal elements of ${\mathbb{F}_{q^{m}}}$
over ${\mathbb{F}_{q}}$ is given by

$(q-1)\cdot q^{m-k-1},$

where $k=0,1,\ldots,m-1$.

The following result by Huczynska et. al [9] formulates a lower bound for the
number of $k$-normal elements when the extension degree $m$ is large enough.

######  Theorem 3.1 ([9, Theorem 4.6])

Let $c_{m-k}$ denote the number of divisors of $x^{m}-1$ with degree $m-k$.
There is a constant $c$ such that for all $q\geq 2$ and $m>q^{c}$, the number
of $k$-normal elements of ${\mathbb{F}_{q^{m}}}$ over ${\mathbb{F}_{q}}$ is at
least

$0.28477\cdot q^{m-k}\cdot c_{m-k}\cdot\sqrt{\log_{q}(m)}$

Note that there is no simple rule or formula for the value $c_{m-k}$ in terms
of $m$, $k$ and $q$, and it may equal zero. So, the above result does not
yield an existence condition.

We now proceed to build a general result on the number of $k$-normal elements,
assuming that they exist. For this purpose, we consider the structure of
${\mathbb{F}_{q^{m}}}$ as an ${\mathbb{F}_{q}}[x]$-module under the action
defined by Equation (1). We follow the approach in [10], which is based on the
observation that for $\mathbb{K}={\mathbb{F}_{q^{m}}}$ and
$G=\mathrm{Gal}(\mathbb{K}/{\mathbb{F}_{q}})$, the group of invertible
elements $\mathbb{K}[G]^{\times}$ of the group algebra $\mathbb{K}[G]$ acts on
the set of normal elements of ${\mathbb{F}_{q^{m}}}$. Using this group action,
the author of [10] formulates an alternate method to count normal elements. We
adapt the same argument to find a lower bound on the number of $k$-normal
elements in ${\mathbb{F}_{q^{m}}}$ when they exist.

###### Lemma 1

Let $k\in\\{0,1,\ldots,m\\}$. Denote
$G:=\mathrm{Gal}({\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}})$ and
$\mathbb{K}:={\mathbb{F}_{q}}$. Let $S_{k}$ be the set of $k$-normal elements
over ${\mathbb{F}_{q}}$ in ${\mathbb{F}_{q^{m}}},$ and assume that
$S_{k}\neq\emptyset$. Let $\mathbb{K}[G]^{\times}$ be the group of invertible
elements of the group algebra $\mathbb{K}[G]$. The map

$\displaystyle\mathbb{K}[G]^{\times}\times S_{k}$ $\displaystyle\rightarrow
S_{k},\text{ given by}$ $\displaystyle\left(\sum_{h\in G}a_{h}\cdot
h\right)\cdot\alpha$ $\displaystyle=\sum_{h\in G}a_{h}\cdot(h\cdot\alpha)$ (3)

for $\alpha\in{\mathbb{F}_{q^{m}}}$ and coefficients $a_{h}\in\mathbb{K}$
defines a group action on the set $S_{k}$.

###### Proof

Let $\alpha$ be an arbitrary element of ${\mathbb{F}_{q^{m}}}$ and let

$V:=\mathrm{span}_{\mathbb{F}_{q}}\\{\sigma\alpha:\sigma\in G\\}$

We know that $G$ is a cyclic group of order $m$, $V$ is a subspace of
${\mathbb{F}_{q^{m}}}$, and that $\alpha$ is $k$-normal if and only if
$\dim_{\mathbb{F}_{q}}V=m-k$. It is clear that the map

$\displaystyle\mathbb{K}[G]^{\times}\times{\mathbb{F}_{q^{m}}}$
$\displaystyle\rightarrow{\mathbb{F}_{q^{m}}},\text{ given by}$
$\displaystyle\left(\sum_{h\in G}a_{h}\cdot h\right)\cdot\alpha$
$\displaystyle=\sum_{h\in
G}a_{h}\cdot(h\cdot\alpha),\;\alpha\in{\mathbb{F}_{q^{m}}}$ (4)

defines a group action.

Now, assume that $\alpha\in S_{k}$. Then, $\dim_{\mathbb{F}_{q}}V=m-k$. Let

$\\{\sigma_{1}\cdot\alpha,\ldots,\sigma_{m-k}\cdot\alpha\\}$

be a basis of $V$. We show that the image of $\alpha$ under any element of the
group $\mathbb{K}[G]^{\times}$ is again $k$-normal. For this, pick
$u\in\mathbb{K}[G]^{\times}$ and write

$u=\sum_{h\in G}a_{h}\cdot h$

for coefficients $a_{h}\in\mathbb{K}$. Let $\beta=u\cdot\alpha$. We have

$\displaystyle\beta=u\cdot\alpha$ $\displaystyle=\sum_{h\in
G}a_{h}\cdot(h\alpha)$ $\displaystyle=\sum_{h\in
G}a_{h}\cdot\sum_{j=1}^{m-k}b_{hj}\cdot\left(\sigma_{j}\alpha\right)$
$\displaystyle\left[\text{ Writing
}h\cdot\alpha=\sum_{j=1}^{m-k}b_{hj}\left(\sigma_{j}\alpha\right),\text{
}b_{hj}\in\mathbb{K}\right]$
$\displaystyle=\sum_{j=1}^{m-k}b_{hj}\cdot\sum_{h\in
G}a_{h}\cdot(\sigma_{j}\alpha)$ $\displaystyle\in V$

where the second step is possible because
$\\{\sigma_{i}(\alpha)_{i\in\\{1,\ldots,m-k\\}}\\}$ is a basis for $V$.

Similarly, for any $\sigma\in G$, $\sigma\cdot\beta\in V$, so

$\mathrm{span}_{\mathbb{F}_{q}}\\{\sigma\beta:\sigma\in
G\\}\subseteq_{subspace}V$

But since $u$ is invertible, we have $\alpha=u^{-1}\cdot\beta$. By an
identical argument as above,

$V=\mathrm{span}_{\mathbb{F}_{q}}\\{\sigma\alpha:\sigma\in
G\\}\subseteq_{subspace}\mathrm{span}_{\mathbb{F}_{q}}\\{\sigma\beta:\sigma\in
G\\}$

So, $\mathrm{span}_{\mathbb{F}_{q}}\\{\sigma\beta:\sigma\in G\\}=V$, and we
conclude that $\beta$ is also $k$-normal. Therefore, we have shown that the
action (4) sends $k$-normal elements to $k$-normal elements, and thus
naturally induces the action (1). This completes the proof. ∎

###### Theorem 3.2

Let $n_{k}$ denote the number of $k$-normal elements in
${\mathbb{F}_{q^{m}}}$. If $n_{k}>0$, i.e. if $k$-normal elements exist in
${\mathbb{F}_{q^{m}}}$, then

$n_{k}\geq\frac{\Phi_{q}(x^{m}-1)}{q^{k}}$

###### Proof

We use the same notation as in Lemma 1. Note that for a generator $\sigma$ of
$G$ we have a ring isomorphism

$\displaystyle\left(\frac{{\mathbb{F}_{q}}[x]}{\langle x^{m}-1\rangle}\right)$
$\displaystyle\mapsto\mathbb{K}[G]$ $\displaystyle x$
$\displaystyle\mapsto\sigma$ (5)

Therefore,

$\mathbb{K}[G]^{\times}\cong\left(\frac{{\mathbb{F}_{q}}[x]}{\langle
x^{m}-1\rangle}\right)^{\times}\hskip 11.38109pt\text{ (as groups)}.$ (6)

We conclude that through the isomorphism (5) the group action (1) induces a
group action

$\displaystyle\left(\frac{{\mathbb{F}_{q}}[x]}{\langle
x^{m}-1\rangle}\right)^{\times}\times\;S_{k}\mapsto S_{k}$ given by
$\displaystyle\left(\sum_{i=0}^{m-1}f_{i}\cdot
x^{i}\right)\cdot\alpha=\sum_{i=0}^{m-1}f_{i}\cdot\sigma^{i}(\alpha)=\sum_{i=0}^{m-1}f_{i}\cdot\alpha^{q^{i}}$
(7)

Denote
$H:=\left(\frac{{\mathbb{F}_{q}}[x]}{\left(x^{m}-1\right)}\right)^{\times}$.
For any $k$-normal element $\alpha$, we have

$\displaystyle\mathrm{Stab}(\alpha)$ $\displaystyle=\\{p(x)\in
H:p(x)\cdot\alpha=\alpha\\}$ $\displaystyle=\\{p(x)\in
H:(p(x)-1)\cdot\alpha=0\\}$ $\displaystyle=\\{p(x)\in
H:\mathrm{Ord}(\alpha)\text{ divides }(p(x)-1)\\}$ (8)

We know that from Theorem 2.1 that $\mathrm{Ord}(\alpha)$ is a polynomial of
degree $m-k$. Equation (8) implies that for $p(x)\in H$,

$p(x)\in\mathrm{Stab}(\alpha)\Leftrightarrow p(x)=\mathrm{Ord}(\alpha)\cdot
r(x)+1,\text{ with }\deg(r(x))\leq k-1$ (9)

Hence, the number of possible distinct values for
$p(x)\in\mathrm{Stab}(\alpha)$ cannot exceed the number of polynomials with
degree less than $k$. More precisely,

$\left|\mathrm{Stab}(\alpha)\right|\leq\min(|H|,\;q^{k})=\min\left(\Phi_{q}(x^{m}-1),\;q^{k}\right)\leq
q^{k}$ (10)

Finally, Equation (10) and the Orbit-Stabilizer Theorem together give

$\left|\mathrm{Orb}(\alpha)\right|=\left|\frac{H}{\mathrm{Stab}(\alpha)}\right|\geq\frac{\Phi_{q}(x^{m}-1)}{q^{k}}$

Since the action (7) is on $k$-normal elements, it is now clear that the
number $n_{k}$ of $k$-normal elements satisfies
$n_{k}\geq\frac{\Phi_{q}(x^{m}-1)}{q^{k}}$, thus completing the proof. ∎

###### Remark 2

In [10], it is shown that for the case of normal elements (i.e. $k=0$), the
action (7) is both free (i.e. $u\cdot\alpha=\alpha\Rightarrow u=1$) and
transitive, and it thereby yields an alternate proof of the well-known result
that the number of normal elements in ${\mathbb{F}_{q^{m}}}$ is equal to
$\Phi_{q}(x^{m}-1)$. However, for $k>0$ the action is clearly not free (in
fact, for every $k$-normal $\alpha$, there exists $u\in\mathbb{K}[G]^{\times}$
such that $u\cdot\alpha=\alpha$). So, we cannot directly adapt the argument as
in [10] to count the exact number of $k$-normal elements. However, as shown by
the above theorem, the action may nevertheless be used to obtain a lower
bound.

##  4 Existence of $k$-Normal Elements

From the previous section, it is clear that some results on the number of
$k$-normal elements automatically imply their existence. For instance, the
existence of $k$-normal in ${\mathbb{F}_{q^{m}}}$ for $m$ a power of the
characteristic $p$ is established as an immediate corollary of Proposition 1.
On the other hand, the cardinality formula in Theorem 3.1 gives the value zero
when $x^{m}-1$ has no divisor with degree $m-k$, and thus yields no condition
for the existence of $k$-normal elements. Similarly, the statement on
cardinalities in Theorem 3.2 holds only under the assumption that $k$-normal
elements exist in ${\mathbb{F}_{q^{m}}}$. We now shift our focus to finding
existence conditions for $k$-normal elements over ${\mathbb{F}_{q}}$. We begin
by presenting (a slight rewording of) a result by Reis, which is closely
related to our existence result.

######  Theorem 4.1 ([18])

Let $q$ be a power of a prime $p$ and let $m\geq 2$ be a positive integer such
that every prime divisor of $m$ divides $p\cdot(q-1)$. Then $k$-normal
elements exist for all $k=0,1,2,\ldots,m$.

Clearly, we get Proposition 1 as a corollary of the above theorem. Although
this theorem significantly extends Proposition 1, it still restricts the prime
factorization of $m$ to be of a particular form, and thus limits the allowed
values of $m$. it is easy to see that it does not apply to simple examples
like $q=5$, $m=6$, and $q=8$, $m=6$, where $k$-normal elements are known to
exist for every $k=0,1,2,\ldots,m$. We now state the main result of this
section, a sufficiency condition for the existence of $k$-normal elements,
which does not, unlike Proposition 1 and Theorem 4.1, require $m$ or its prime
factors to be of a fixed type. This result is also independent of the
factorization of $x^{m}-1$ into irreducibles over ${\mathbb{F}_{q}}$, and is
derived using only the general factorization into cyclotomic polynomials.

###### Theorem 4.2

If $m\mid(q^{m}-1)$, then $k$-normal elements exist in ${\mathbb{F}_{q^{m}}}$
for every integer $k$ in the interval $0\leq k\leq m-1$. If $m\nmid q^{m}-1$,
let $d=\gcd(q^{m}-1,\;m)$. Assume that $\sqrt{m}<d$. Let $b$ denote the
largest prime divisor of $m$ that is a non-divisor of $q^{m}-1$. Then, for
$k\geq m-d-b+1$, $k$-normal elements exist in ${\mathbb{F}_{q^{m}}}$. In
particular, if $m\leq d+b-1$, then $k$-normal elements exist for every $k$ in
the interval $0\leq k\leq m-1$.

###### Proof

We know from Equation (2) that the number of $k$-normal elements in
${\mathbb{F}_{q^{m}}}$ is given by

$\sum_{\begin{subarray}{c}h\mid x^{m}-1\\\ \deg
h=m-k\end{subarray}}\Phi_{q}(h(x))$

Thus, normal elements exist in ${\mathbb{F}_{q^{m}}}$ if and only if $x^{m}-1$
has a divisor of degree $m-k$. First note that for $d=\gcd(q^{m}-1,m)$, we
have $d\mid q^{m}-1$, the order of $\mathbb{F}_{q^{m}}^{*}$, so by the general
properties of a finite cyclic group, there are precisely $d$ elements $\alpha$
in the group $\mathbb{F}_{q^{m}}^{*}$ satisfying $\alpha^{d}=1$, and so $d$
elements must also satisfy $\alpha^{m}=1$. Thus, $x^{m}-1$ has precisely $d$
linear factors over ${\mathbb{F}_{q^{m}}}$. Let its roots in
${\mathbb{F}_{q^{m}}}$ be $\alpha_{1},\alpha_{2},\ldots,\alpha_{d}$.

If $m\mid q^{m}-1$, then $d=m$, and $x^{m}-1$ splits into linear factors over
${\mathbb{F}_{q^{m}}}$. Thus, in this case, for any
$k\in\\{0,1,2,\ldots,m-1\\}$, one may always combine $m-k$ of the $m$ linear
factors to obtain a factor of degree $m-k$ of $x^{m}-1$. Hence, we are done
for this case.

If $m\nmid q^{m}-1$, then $d<m$. Assume that for some
$k\in\\{0,1,2,\ldots,m-1\\}$, no $k$-normal element exists in
${\mathbb{F}_{q^{m}}}$. It is known that $x^{m}-1$ has the following
factorization over ${\mathbb{F}_{q}}$:

$x^{m}-1=\prod_{t\mid m}Q_{t}(x)$

where $Q_{t}(x)$ denotes the $t^{th}$ cyclotomic polynomial, and is known to
have coefficients in ${\mathbb{F}_{q}}$ [14, Theorem 2.45]. Write

$\displaystyle x^{m}-1$ $\displaystyle=\prod_{t\hskip 2.84526pt\mid\hskip
2.84526ptd}Q_{t}(x)\cdot\prod_{\begin{subarray}{c}t\hskip 2.84526pt\mid\hskip
2.84526ptm\\\ t\hskip 2.84526pt\nmid\hskip
2.84526ptq^{m}-1\end{subarray}}Q_{t}(x)$
$\displaystyle=(x^{d}-1)\cdot\prod_{\begin{subarray}{c}t\hskip
2.84526pt\mid\hskip 2.84526ptm\\\ t\hskip 2.84526pt\nmid\hskip
2.84526ptq^{m}-1\end{subarray}}Q_{t}(x)$
$\displaystyle=(x-\alpha_{1})\cdot(x-\alpha_{2})\cdot\ldots\cdot(x-\alpha_{d})\cdot\prod_{\begin{subarray}{c}t\hskip
2.84526pt\mid\hskip 2.84526ptm\\\ t\hskip 2.84526pt\nmid\hskip
2.84526ptq^{m}-1\end{subarray}}Q_{t}(x)$

where the last step follows from the fact that $d\mid q^{m}-1$, so as in the
first case, $x^{d}-1$ splits in ${\mathbb{F}_{q^{m}}}$. Now, let $b$ be the
largest prime dividing $m$ but not $q^{m}-1$ (such a $b$ exists because we
have assumed that $m\nmid q^{m}-1$). Then $Q_{b}(x)$ figures in the latter
product of the above equation. Since no $k$-normal elements exist in
${\mathbb{F}_{q^{m}}}$, $m-k$ must be greater than the number $d$ of linear
factors, and it must be impossible to combine the factors of degree greater
than 1, in particular, $Q_{b}(x)$, with the linear factors to obtain a factor
of degree $m-k$. Mathematically,

$\displaystyle m-k>d,$ and $\displaystyle\text{either }\phi(b)>m-k\text{ or
}\phi(b)+d<m-k$

Rearranging, we get

$\displaystyle k<m-d,$ (11) and $\displaystyle\text{either }k>m-\phi(b)\text{
or }k<m-d-\phi(b)$ (12)

Now, since $b$ is a prime dividing $m$ but not $q-1$, $b$ must divide
$\frac{m}{d}$. In particular, $b\leq\frac{m}{d}$. From the hypothesis
$\sqrt{m}<d$, we get $b\leq\frac{m}{d}<d$, and so

$\displaystyle m-\phi(b)$ $\displaystyle=m-b+1$ $\displaystyle>m-d+1>m-d$
$\displaystyle>k$ (13)

where the last step follows from Eq. (11). We now immediately note that the
former condition in Eq. (12) is incompatible with Eq. (13), and so it cannot
hold. Therefore, the latter condition of Eq. (12) must be satisfied, i.e. we
must have

$k<m-d-\phi(b)=m-d-b+1$

for $k$ such that $k$-normal elements do not exist. Hence, we conclude that
for all $k\geq m-d-b+1$, $k$-normal elements exist in ${\mathbb{F}_{q^{m}}}$,
as required. ∎

###### Remark 3

Note that the fact that $b$ is a prime plays a key role in the above proof. If
$b$ is, instead, an arbitrary divisor of $m$ that does not divide $q-1$, then
it is not guaranteed that $b$ divides $\frac{m}{d}$ (E.g. consider
$q=25,m=20,b=10$). So the argument may not hold true even though the
inequality $\frac{m}{d}<d$ may hold.

We now reconsider the two examples considered before. For $q=5$, $m=6$, we
have $q^{m}-1=15624$, which is divisible by 6. So, Theorem 4.2 shows that
$k$-normal elements exist in ${\mathbb{F}_{q^{m}}}$ for every
$k\in\\{0,1,\ldots,m\\}$. For $q=8$, $m=6$, we have $q^{m}-1=262143$, and so
$d=\gcd(q^{m}-1,\;m)=3>\sqrt{6}$. The largest prime $b$ that divides $6$ and
not $262143$ is clearly 2. So, Theorem 4.2 shows that $k$-normal elements
exist in ${\mathbb{F}_{q^{m}}}$ for every $k\geq m-d-b+1$, i.e. for every
$k\geq 2$. Since we know that $0$\- and $1$-normal elements always exist in
${\mathbb{F}_{q^{m}}}$, we conclude that in this case $k$-normal elements
exist for every $k\in\\{0,1,\ldots,m\\}$. The exact numbers for these two
examples are listed in Tables 4 and 2, respectively, in Section 6.

##  5 Normal Elements with Large Multiplicative Order

So far, we have studied the “additive” structure of ${\mathbb{F}_{q^{m}}}$ as
a vector space over ${\mathbb{F}_{q^{m}}}$. It is also of interest to study
the relation between this aditive structure and the natural multiplicative
structure of $\mathbb{F}_{q^{m}}^{*}$. One of the most noteworthy results in
this direction is the Primitive Normal Basis Theorem ([13], [2], [4]). Several
generalizations to this result have been proposed and are still unsolved. We
state some of these in Section 6. Below, we state and prove an existence
result for normal elements (i.e. $k=0$) with multiplicative order
$\frac{q^{m}-1}{q-1}$ in ${\mathbb{F}_{q^{m}}}$. It turns out that such
elements always exist if $m$ and $q-1$ are co-prime, and that this may be
derived using the same methods as Lenstra and Schoof [13] in the proof of the
Primitive Normal Basis Theorem.

###### Theorem 5.1

Suppose that $(m,q-1)=1$. Then ${\mathbb{F}_{q^{m}}}$ has a normal element
with multiplicative order $\frac{q^{m}-1}{q-1}$.

###### Proof

Let $k:=\frac{q^{m}-1}{q-1}$. Define

$\displaystyle A=$
$\displaystyle\\{\alpha\in{\mathbb{F}_{q^{m}}}:\mathrm{Ord}(\alpha)=x^{m}-1\\}$
$\displaystyle B=$
$\displaystyle\\{\alpha\in\mathbb{F}_{q^{m}}^{*}:\mathrm{ord}(\alpha)=k\\}$
$\displaystyle C=$
$\displaystyle\\{\alpha\in{\mathbb{F}_{q^{m}}}:\alpha^{(q-1)^{2}}=1\\}$

where the sets $A$ and $C$ are defined identically as in the proof of Lenstra
and Schoof, and $B$ is defined as the set of elements with order $k$, rather
than primitive elements. Note that $C$ is a subgroup of
$\mathbb{F}_{q^{m}}^{*}$. Also note that since the definitions of $A$ and $C$
are unchanged, we may use directly the result (1.12) of the original proof in
[13]. We state this as follows. For the set $CA$ defined as

$CA=\\{\gamma\cdot\alpha:\gamma\in C,\alpha\in A\\},$

we have

$CA=A$ (14)

Let $BC$ denote the set $BC=\\{\beta\cdot\gamma:\beta\in B,\gamma\in C\\}$.
Now, since Equation (14) holds, the exact same argument as in the original
proof also yields the result indexed (1.13) in [13]. Since we have a different
$B$, we prove it below. The proof is identical for $B$ defined as the set of
elements of any multiplicative order.

If $\alpha\in A$, $\beta\in B$, $\gamma\in C$ are such that
$\alpha=\beta\cdot\gamma\in B\cdot C$, then $\beta=\alpha\cdot\gamma^{-1}\in
CA\cap B=A\cap B$, and so we have

$A\cap B=\emptyset\Leftrightarrow A\cap BC=\emptyset$ (15)

As in the original paper, we use Equation (15) and prove that $A\cap B\cdot
C\neq\emptyset$ to conclude that $A\cap B\neq\emptyset$.

Let $H$ denote the unique subgroup of order $k$ in $\mathbb{F}_{q^{m}}^{*}$.
Here,

$\displaystyle BC$ $\displaystyle=\left\\{\beta\cdot\gamma:\beta\in
B,\>\gamma\in C\right\\}$ $\displaystyle=\left\\{\beta\cdot\gamma:\beta\text{
generates }H,\>\gamma\in C\right\\}$
$\displaystyle=\left\\{\beta\cdot\gamma:\beta\cdot C\text{ generates
}\frac{H}{C},\>\gamma\in C\right\\}$
$\displaystyle=\left\\{\beta\cdot\gamma:\beta\cdot C\cap H\text{ generates
}\frac{H}{H\cap C},\>\gamma\in C\right\\}$

Now note that

$\displaystyle\gcd(k,(q-1))$
$\displaystyle=\gcd\left(\frac{q^{m}-1}{q-1},\;q-1\right)$
$\displaystyle=\gcd\left(1+q+q^{2}+\ldots+q^{m}-1,\;q\right)$
$\displaystyle=\gcd(m,\;q-1)$ $\displaystyle=1,$

where the second last equality can be checked by direct computation for
general values of $m$ and $q$, and the last equality follows by the hypothesis
of the theorem. Thus, $|C|=(q-1)\cdot\gcd(q-1,\;m)=(q-1)$. So, in this case,
$C$ is the unique subgroup of $\mathbb{F}_{q^{m}}^{*}$ with order $q-1$. Thus,
$C$ and $H$ are subgroups with co-prime orders, and therefore intersect
trivially. Now let

$D=\\{\alpha\in\mathbb{F}_{q^{m}}^{*}:ord(\alpha)=q^{m}-1\\}$

denote the set of generators of $\mathbb{F}_{q^{m}}^{*}$. We claim that

$D\subseteq BC$

To see this, pick $\alpha\in D$. Since $\gcd(k,\;q-1)=1$, there exist integers
$a$ and $b$ such that

$a\cdot k+b\cdot(q-1)=1$

This implies that $(a,q-1)=1$ and $(b,k)=1$. Thus, $\alpha^{ka}$ has order
$q-1$ and $\alpha^{b(q-1)}$ has order $k$.

Thus, $\alpha=\alpha^{b(q-1)}\cdot\alpha^{ka}$, with $\alpha^{b(q-1)}\in B$
and $\alpha^{ka}\in C$. We have hereby proved that $D\subseteq BC$. We now
have $A\cap D\subseteq A\cap BC$. But, by [13, result (1.10)], we have $A\cap
D\neq\emptyset$, and so we must also have $A\cap BC\neq\emptyset$. By Equation
(15), we conclude that $A\cap B\neq\emptyset$.

Hence, ${\mathbb{F}_{q^{m}}}$ contains a normal element with multiplicative
order $k=\frac{q^{m}-1}{q-1}$, as required. ∎

##  6 Examples

We now demonstrate the validity of Theorems 3.2, 4.2, and 5.1 with the help of
concrete examples. The following cardinalities were derived by an exhaustive
search using the algebra software package SageMath [21]. Each table below
corresponds to the extension ${\mathbb{F}_{q^{m}}}$ of ${\mathbb{F}_{q}}$, and
shows that the number of $k$-normal elements, whenever nonzero, is greater
than or equal to the number $\frac{\Phi_{q}(x^{m}-1)}{q^{k}}$, as stated in
Theorem 3.2. Note that these latter values, which appear in the second column,
have been rounded off to two decimal places. Below each table, we give the
number of normal elements with multiplicative order $\frac{q^{m}-1}{q-1}$. In
the terminology of [16], we call these $(q-1)$-primitive normal elements.
Clearly, Theorem 5.1 is validated by the fact that all these numbers are non-
zero.

We have already discussed Tables 4 and 6 in the light of Theorems 4.1 and 4.2.
On the other hand, note that for the example in Table 5, Theorem 4.1 is
applicable, while Theorem 4.2 is not. This shows that neither of these two
results is stronger than the other. In the case of Table 8, the assumptions of
both theorems hold and both guarantee the existence of $k$-normal elements for
every value of $k$ less than $m$. For Tables 1, 2, 3, and 7, neither Theorem
4.1 nor Theorem 4.2 applies. In fact, Table 3 shows that 3-normal elements and
7-normal elements over $\mathbb{F}_{2}$ do not exist in $\mathbb{F}_{1024}$.

Table 1: $\mathbb{F}_{8}/\mathbb{F}_{2}$ ($q=2$, $m=3$) k # of $k$-normal elements $\displaystyle\dfrac{\Phi_{q}(x^{m}-1)}{q^{k}}$ 0 4 4 1 4 4 2 2 2 3 1 1 # of $(q-1)$-primitive normal elements = 4 |  Table 2: $\mathbb{F}_{59049}/\mathbb{F}_{9}$ ($q=9$, $m=5$) k # of $k$-normal elements $\displaystyle\dfrac{\Phi_{q}(x^{m}-1)}{q^{k}}$ 0 51200 51200 1 6400 5688.89 2 1280 632.10 3 160 70.23 4 8 7.80 # of $(q-1)$-primitive normal elements = 5750
---|---
Table 3: $\mathbb{F}_{1024}/\mathbb{F}_{2}$ ($q=2$, $m=10$) k # of $k$-normal elements $\displaystyle\dfrac{\Phi_{q}(x^{m}-1)}{q^{k}}$ 0 480 480 1 240 240 2 240 120 3 0 60 4 35 30 5 15 15 6 15 7.5 7 0 3.75 8 2 1.875 9 1 0.94 # of $(q-1)$-primitive normal elements = 290 |  Table 4: $\mathbb{F}_{262144}/\mathbb{F}_{8}$ ($q=8$, $m=6$) k # of $k$-normal elements $\displaystyle\dfrac{\Phi_{q}(x^{m}-1)}{q^{k}}$ 0 225792 225792 1 28224 28224 2 7560 3528 3 441 441 4 119 55.13 5 7 6.89 # of $(q-1)$-primitive normal elements = 20124
Table 5: $\mathbb{F}_{729}/\mathbb{F}_{3}$ ($q=3$, $m=6$) k # of $k$-normal elements $\displaystyle\dfrac{\Phi_{q}(x^{m}-1)}{q^{k}}$ 0 324 324 1 216 108 2 108 36 3 60 12 4 16 4 5 4 1.33 # of $(q-1)$-primitive normal elements = 290 |  Table 6: $\mathbb{F}_{15625}/\mathbb{F}_{5}$ ($q=5$, $m=6$) k # of $k$-normal elements $\displaystyle\dfrac{\Phi_{q}(x^{m}-1)}{q^{k}}$ 0 9216 9216 1 4608 1843.20 2 1344 368.64 3 384 73.73 4 64 14.75 5 8 2.95 # of $(q-1)$-primitive normal elements = 642
Table 7: $\mathbb{F}_{4913}/\mathbb{F}_{17}$ ($q=17$, $m=3$) k # of $k$-normal elements $\displaystyle\dfrac{\Phi_{q}(x^{m}-1)}{q^{k}}$ 0 4608 4608 1 288 271.06 2 16 15.94 # of $(q-1)$-primitive normal elements = 288 |  Table 8: $\mathbb{F}_{2401}/\mathbb{F}_{7}$ ($q=7$, $m=4$) k # of $k$-normal elements $\displaystyle\dfrac{\Phi_{q}(x^{m}-1)}{q^{k}}$ 0 1728 1728 1 576 246.86 2 84 35.26 3 16 5.04 # of $(q-1)$-primitive normal elements = 112

##  7 Conclusions

In this paper, we dealt with the recently introduced concept of $k$-normal
elements in finite fields [9]. The existence and cardinalities of $k$-normal
elements in ${\mathbb{F}_{q^{m}}}$ are both strongly tied to the factorization
of the polynomial $x^{m}-1$ over ${\mathbb{F}_{q}}$, which, in turn, depends
on the factorization of cyclotomic polynomials. One does not have an explicit
formula for the irreducible factors of cyclotomic polynomials, or of their
degrees, and so it is not possible to directly infer the existence or numbers
of $k$-normal elements. However, one may deduce several key results by forcing
certain conditions on $m$, $k$, and $q$. In Theorem 4.2, we used the general
factorization of $x^{m}-1$ into cyclotomic polynomials to obtain a new
existence condition for $k$-normal elements.

The structure of ${\mathbb{F}_{q^{m}}}$ as an additive module over
${\mathbb{F}_{q}}[x]$ plays a key role in proofs related to normal and
$k$-normal bases. In Theorem 3.2, we furnished a lower bound for the number of
$k$-normal elements in ${\mathbb{F}_{q^{m}}}$ under the sole assumption that
at least one of them exists. The proof is inspired by the observation in [10]
that the additive module structure of ${\mathbb{F}_{q^{m}}}$ in fact gives
rise to a group action on all the normal elements. Our bound does not require
a specific form for $m$ or $q$, and therefore extends beyond the formulas
provided in [20].

After the proof of the well-known Primitive Normal Basis Theorem by Lenstra
and Schoof [13], several interesting generalizations have been proposed. The
existence and numbers of elements with different pairs of additive orders (as
in Definition 2) and multiplicative group orders have been investigated by
several authors. Some solved and unsolved problems in this domain may be found
in [9], [3], [16], and [12]. We state one such relevant open problem below.

######  Problem 1 ([9, Problem 6.4])

Determine the existence of high-order $k$-normal elements
$\alpha\in{\mathbb{F}_{q^{m}}}$ over ${\mathbb{F}_{q}}$, where “high order”
means $ord(\alpha)=N$, with $N$ a large positive divisor of $q^{m}-1$.

With Theorem, 5.1 we answered a special case of Problem 1. Following the
method of Lenstra and Schoof [13], we provided an existence condition for
elements in ${\mathbb{F}_{q^{m}}}$ with maximal additive order (i.e. normal
elements) that simultaneously have a non-maximal but high multiplicative
order, namely $\frac{q^{m}-1}{q-1}$.

## Acknowledgement

This work was partially supported by Swiss National Science Foundation grant
n. 188430. The authors are also greatly thankful to Gianira Alfarano for her
thorough proofreading and constructive feedback on this manuscript.

## References

  * [1] Ash, D.W., Blake, I.F., Vanstone, S.A.: Low complexity normal bases. Discrete Appl. Math. 25(3), 191–210 (1989). https://doi.org/10.1016/0166-218X(89)90001-2
  * [2] Carlitz, L.: Primitive roots in a finite field. Trans. Amer. Math. Soc. 73, 373–382 (1952). https://doi.org/10.2307/1990797
  * [3] Cohen, S.D., Huczynska, S.: The strong primitive normal basis theorem. Acta Arith. 143(4), 299–332 (2010). https://doi.org/10.4064/aa143-4-1, https://doi.org/10.4064/aa143-4-1
  * [4] Davenport, H.: Bases for finite fields. J. London Math. Soc. 43, 21–39 (1968). https://doi.org/10.1112/jlms/s1-43.1.21
  * [5] Frandsen, G.S.: On the density of normal bases in finite fields. Finite Fields Appl. 6(1), 23–38 (2000). https://doi.org/10.1006/ffta.1999.0263
  * [6] Gao, S.: Normal bases over finite fields. ProQuest LLC, Ann Arbor, MI (1993), thesis (Ph.D.)–University of Waterloo (Canada)
  * [7] Gao, S., Panario, D.: Density of normal elements. Finite Fields Appl. 3(2), 141–150 (1997). https://doi.org/10.1006/ffta.1996.0177
  * [8] Hensel, K.: Ueber die Darstellung der Zahlen eines Gattungsbereiches für einen beliebigen Primdivisor. J. Reine Angew. Math. 103, 230–237 (1888). https://doi.org/10.1515/crll.1888.103.230
  * [9] Huczynska, S., Mullen, G.L., Panario, D., Thomson, D.: Existence and properties of $k$-normal elements over finite fields. Finite Fields Appl. 24, 170–183 (2013). https://doi.org/10.1016/j.ffa.2013.07.004
  * [10] Hyde, T.: Normal elements in finite fields. arXiv preprint arXiv:1809.02155 (2018)
  * [11] Kapetanakis, G.: Normal bases and primitive elements over finite fields. Finite Fields Appl. 26, 123–143 (2014). https://doi.org/10.1016/j.ffa.2013.12.002
  * [12] Kapetanakis, G., Reis, L.: Variations of the primitive normal basis theorem. Des. Codes Cryptogr. 87(7), 1459–1480 (2019). https://doi.org/10.1007/s10623-018-0543-9
  * [13] Lenstra, Jr., H.W., Schoof, R.J.: Primitive normal bases for finite fields. Math. Comp. 48(177), 217–231 (1987). https://doi.org/10.2307/2007886
  * [14] Lidl, R., Niederreiter, H.: Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20. Cambridge University Press, Cambridge, second edn. (1997), with a foreword by P. M. Cohn
  * [15] Menezes, A.J., Blake, I.F., Gao, X., Mullin, R.C., Vanstone, S.A., Yaghoobian, T.: Applications of finite fields, The Kluwer International Series in Engineering and Computer Science, vol. 199. Kluwer Academic Publishers, Boston, MA (1993). https://doi.org/10.1007/978-1-4757-2226-0
  * [16] Mullen, G.L.: Some open problems arising from my recent finite research. In: Contemporary developments in finite fields and applications, pp. 254–269. World Sci. Publ., Hackensack, NJ (2016)
  * [17] Ore, O.: Contributions to the theory of finite fields. Trans. Amer. Math. Soc. 36(2), 243–274 (1934). https://doi.org/10.2307/1989836
  * [18] Reis, L.: Existence results on $k$-normal elements over finite fields. Rev. Mat. Iberoam. 35(3), 805–822 (2019). https://doi.org/10.4171/rmi/1070
  * [19] Reis, L., Thomson, D.: Existence of primitive 1-normal elements in finite fields. Finite Fields Appl. 51, 238–269 (2018). https://doi.org/10.1016/j.ffa.2018.02.002
  * [20] Saygı, Z., Tilenbaev, E., Ürtiş, c.: On the number of $k$-normal elements over finite fields. Turkish J. Math. 43(2), 795–812 (2019). https://doi.org/10.3906/mat-1805-113
  * [21] The Sage Developers: SageMath, the Sage Mathematics Software System (Version 8.6) (2020), https://www.sagemath.org