# Arithmetic progression in a finite field with prescribed norms

Kaustav Chatterjee, Hariom Sharma, Aastha Shukla, and Shailesh Kumar Tiwari∗

###### Abstract.

Given a prime power $q$ and a positive integer $n$, let $\mathbb{F}_{q^{n}}$
represents a finite extension of degree $n$ of the finite field
${\mathbb{F}_{q}}$. In this article, we investigate the existence of $m$
elements in arithmetic progression, where every element is primitive and at
least one is normal with prescribed norms. Moreover, for $n\geq 6,q=3^{k},m=2$
we establish that there are only $10$ possible exceptions.

*email<EMAIL_ADDRESS>
First author is supported by National Board for Higher Mathematics(IN), Ref
No. 0203/6/2020- RD-11/7387.

Mathematics Subject Classification: 12E20; 11T23

Key Words and Phrases: Finite field; Primitive element; Normal element;
Characters; Norm

##  1\. Introduction

Let $\mathbb{F}_{q}$ be a finite field with $q$ elements, where $q=p^{k}$ for
some prime $p$ and positive integer $k$. With respect to multiplication, the
set $\mathbb{F}_{q}^{*}$, consisting of the non-zero elements in
$\mathbb{F}_{q}$, forms a cyclic group and a generator of this multiplicative
group is defined to be a primitive element of the finite field
$\mathbb{F}_{q}$. The finite field $\mathbb{F}_{q}$ contains $\phi(q-1)$
primitive elements, with $\phi$ representing Euler’s totient function. An
element $\alpha\in\mathbb{F}_{q^{n}}^{*}$ is primitive if and only if is a
root of an irreducible polynomial of degree $n$ over $\mathbb{F}_{q}$ and such
an irreducible polynomial is termed as primitive polynomial. Let
$\mathbb{F}_{p^{n}}$ represents a field extension of $\mathbb{F}_{q}$ of
degree of $n$, where $n$ is a positive integer. For any $\alpha$
$\in\mathbb{F}_{q^{n}}$, the elements
$\alpha,\alpha^{q},\ldots,\alpha^{q^{n-1}}$ are referred as the conjugates of
$\alpha$ with respect to $\mathbb{F}_{q}$. An element
$\alpha\in\mathbb{F}_{q^{n}}$ is said to be normal over $\mathbb{F}_{q}$ if
the set of conjugates of $\alpha$ forms a basis of $\mathbb{F}_{q^{n}}$ over
$\mathbb{F}_{q}$, while the basis itself is called normal basis. The norm of
an element $\alpha\in\mathbb{F}_{q^{n}}$ over $\mathbb{F}_{q}$, denoted by
$N_{{q^{n}}/q}(\alpha)$, is the product of the conjugates of $\alpha$ over
$\mathbb{F}_{q}$, that is,
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)=\alpha\cdot\alpha^{q}\cdot\alpha^{q^{2}}\ldots\alpha^{q^{n-1}}$.
We refer reader [10] for further informations related to the existence of
primitive normal elements.

Primitive elements play a foundational role in Random Number Generation,
Signal Processing and Elliptic Curve Cryptography. A lot of applications of
primitive elements can be found in Coding theory and Cryptography [[16], [4]],
making the study of primitive polynomials and primitive elements an important
research area. For any $\alpha,\beta\in\mathbb{F}_{q^{n}}$, a pair
$(\alpha,\beta)$ is referred as primitive normal pair if both $\alpha$ and
$\beta$ are primitive as well as normal over $\mathbb{F}_{q}$. In particular,
for any $f(x)\in\mathbb{F}_{q^{n}}(x)$, the existence of primitive normal
pairs $(\alpha,f(\alpha))$ has been a much interesting research area and many
researchers has worked in the direction [[17],[18],[19],[20]].

In $1987$, Lenstra and Schoof [7] proved the The Primitive Normal Basis
Theorem, which guarantees that every extension $\mathbb{F}_{q^{n}}$ over
$\mathbb{F}_{q}$ always contains a primitive normal element. In $2000$, Cohen
and Hachenberger [21] demonstrated the existence of primitive and normal
element $\alpha\in\mathbb{F}_{q}$ with prescribed trace and norm. Recently,
Sharma et al. [1] proved that for any polynomial
$f(x)\in\mathbb{F}_{q^{n}}[x]$ with minor restrictions, there exists a
primitive normal pair $(\alpha,f(\alpha))$ such that
$Tr_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)=b$ and
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)=a$, for any prescribed
$a,b\in\mathbb{F}_{q}$. In [2], Lemos et al. investigated the existence of an
element $\alpha\in\mathbb{F}_{q^{n}}^{*}$ such that for fixed
$\beta\in\mathbb{F}_{q^{n}}^{*}$, any element in the set
$\\{\alpha,\alpha+\beta,\ldots,\alpha+(m-1)\beta\\}$ is primitive and at least
one of them is normal. In this article, we establish the sufficient condition
for the existence of an element $\alpha\in\mathbb{F}_{q^{n}}$ such that for
fixed $\beta\in\mathbb{F}_{q^{n}}^{*}$, each element in the $m$-term
arithmetic progression $\alpha,\alpha+\beta,\ldots,\alpha+(m-1)\beta$ is
primitive, at least one of them is normal with
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha+(i-1)\beta)=c_{i}$, where
$c_{i}\in\mathbb{F}_{q}$ for $i\in\\{1,2,\ldots,m\\}$. Here we must have $m$
should be less than or equal to the characteristic of $\mathbb{F}_{q}$.

The structure of this article is as follows: In Section 2, we give basic
definitions that will be used throughout the article. Section 3 includes some
characteristic functions and lemmas providing bounds on characteristic sums.
In Section 4, we figure out the sufficient condition for the existence of the
mentioned arithmetic progressions, along with an additional condition derived
through sieve methods. Section 5 contains numerical examples for further
illustration.

##  2\. Preliminaries

Before proceeding further, we provide some essential notations and significant
definitions, which will be used consistently throughout the article. Assume
that $n$ is a positive integer, $q$ is a prime power and $\mathbb{F}_{q}$ is a
finite field with $q$ elements.

###  2.1. Definitions

  * 1.

Let $G$ be an abelain group and $T$ be the subset of complex numbers
containing elements with unit modulus. A character $\chi$ of $G$ is a
homomorphism from $G$ into $T$ i.e., $\chi(g_{1}g_{2})=\chi(g_{1})\chi(g_{2})$
for all $g_{1},g_{2}\in G$. The set of characters of ${G}$, denoted by
$\widehat{{G}}$, forms a group under multiplication. In addition, $G$ is
isomorphic to $\widehat{{G}}$. In the context of a finite field
$\mathbb{F}_{q^{n}}$, an additive character relates to the additive group of
$\mathbb{F}_{q^{n}}$, while a multiplicative character corresponds to the
multiplicative group of $\mathbb{F}_{q^{n}}^{*}$.

  * 2.

Let $e|q^{n}-1$ and $\alpha\in\mathbb{F}_{q^{n}}^{*}$. Suppose for any $d|e$
and $\beta\in\mathbb{F}_{q^{n}}$, $\alpha=\beta^{d}$ implies $d=1$. Then we
say that $\alpha$ is a $e$-free element. Thus
$\alpha\in\mathbb{F}_{q^{n}}^{*}$ is primitive $\iff$ $\alpha$ is
$(q^{n}-1)$-free.

  * 3.

Let $\alpha\in\mathbb{F}_{q^{n}}$ and $g$ be any divisor of $x^{n}-1$. We say
that $g$ is $\mathbb{F}_{q}$-order of $\alpha$ if $\alpha=h\circ\beta$, where
$\beta\in\mathbb{F}_{q^{n}}$ and $h|g$ implies $h=1$. It is easy to observe
that an element $\alpha\in\mathbb{F}_{q^{n}}$ is normal if and only if
$\alpha$ is $x^{n}-1$-free.

  * 4.

The Euler’s totient function for any polynomial $f(x)\in\mathbb{F}_{q}[x]$ is
defined as follows:

$\Phi_{q}(f)=\Bigg{|}\Bigg{(}\frac{\mathbb{F}_{q}[x]}{f\mathbb{F}_{q}[x]}\Bigg{)}^{*}\Bigg{|}=q^{deg(f)}\cdot\prod_{p\in\mathcal{I}_{f}}\Bigg{(}1-\frac{1}{p}\Bigg{)}$

where $\mathcal{I}_{f}$ represents the set of irreducible factors of $f$ and
$f\mathbb{F}_{q}[x]$ is the ideal generated by $f$.

  * 5.

The Möbius function for the set of polynomials over $\mathbb{F}_{q}$ is
defined as follows: In case when $f$ is product of $r$ distinct monic
irreducible polynomials then $\mu_{q}(f)=(-1)^{r}$ and otherwise
$\mu_{q}(f)=0$.

##  3\. Some useful results

In this section initially we present the characteristic functions of $e$-free,
$g$-free elements and the set of elements in $\mathbb{F}_{q^{n}}$ with
prescribed norm $c$.

For any $e|(q^{n}-1)$, following the work of Cohen and Huczynska [12], the
characteristic function of the $e$-free elements of $\mathbb{F}_{q^{n}}^{*}$
is given by

$\rho_{e}:\alpha\mapsto{}\frac{\phi(e)}{e}\sum_{k|e}\frac{\mu(k)}{\phi(k)}\sum_{\chi_{k}}\chi_{k}(\alpha),$

where the inner sum is taken over all multiplicative characters of order $k$,
$\mu(.)$ is the Möbius function and $\phi(.)$ is the Euler function.

Given $g(x)|x^{n}-1$, the characteristic function of the set of $g$-free
elements in $\mathbb{F}_{q^{n}}$ is given by

$\kappa_{g}:\alpha\mapsto{}\frac{\Phi_{q}(g)}{q^{deg(g)}}\sum_{h|g}\frac{\mu_{q}(h)}{\Phi_{q}(h)}\sum_{\lambda_{h}}\lambda_{h}(\alpha),$

where the inner sum is taken over any additive characters of
$\mathbb{F}_{q}$-order $h$, $\mu_{q}(.)$ is the Möbius function on
$\mathbb{F}_{q}[x]$ and $\Phi_{q}(.)$ is the Euler function on
$\mathbb{F}_{q}[x]$.

Also, for any $c\in\mathbb{F}_{q}^{*}$,

$\displaystyle\pi_{c}:\alpha\mapsto\frac{1}{q-1}\sum_{\chi\in{\widehat{{\mathbb{F}}_{q}^{*}}}}\chi(N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)c^{-1})$

is a characteristic function for the subset of $\mathbb{F}_{q^{n}}$ containing
those elements $\alpha$ such that
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)=c$. Let $\chi_{q-1}$ represents
a generator of the multiplicative group of characters
$\widehat{{\mathbb{F}}_{q}^{*}}$. Then, any
$\chi\in\widehat{{\mathbb{F}}_{q}^{*}}$ can be expressed as
$\chi(\alpha)=\chi_{q-1}(\alpha^{i})$ for some $i\in\\{1,2,\ldots,q-1\\}$.
Thus we get

$\displaystyle\pi_{c}(\alpha)$
$\displaystyle=\frac{1}{q-1}\sum_{i=1}^{q-1}\chi_{q-1}^{i}(N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)c^{-1})$
$\displaystyle=\frac{1}{q-1}\sum_{i=1}^{q-1}\bar{\chi}^{i}(\alpha)\chi_{q-1}(c^{-i}),$

where $\bar{\chi}=\chi_{q-1}\circ N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}$ is a
multiplicative character of $\mathbb{F}_{q^{n}}^{*}$. Following [1], the order
of $\bar{\chi}$ in $\widehat{{\mathbb{F}}_{q^{n}}^{*}}$ is $q-1$ and thus
there exists a multiplicative character
$\chi_{q^{n}-1}\in\widehat{{\mathbb{F}}_{q^{n}}^{*}}$ of order $q^{n}-1$ such
that $\bar{\chi}=\chi_{q^{n}-1}^{{q^{n}-1}/{q-1}}$.

Following two lemmas provide bounds on the character sums which will be useful
to prove our sufficient condition.

######  Lemma 3.1.

([8], Theorem 5.5) Let $f(x)=\prod_{j=1}^{s}f_{j}(x)^{a_{j}}$ be a rational
function over $\mathbb{F}_{q^{n}}$, where $f_{j}(x)\in\mathbb{F}_{q^{n}}[x]$
are polynomials and $a_{j}\in\mathbb{Z}\smallsetminus\\{0\\}$. Let
$\chi\in\widehat{{\mathbb{F}}_{q}^{*}}$ be a multiplicative character of order
$d$. Consider the rational function $f(x)$ that is not of the form of
$r(x)^{d}$, where $r(x)$ belongs to the field $\mathbb{F}(x)$ and $\mathbb{F}$
represents the algebraic closure of $\mathbb{F}_{q^{n}}$. Then we have

$\Bigg{|}\sum_{\alpha\in\mathbb{F}_{q^{n}}}\chi(f(\alpha))\Bigg{|}\leq\Bigg{(}\sum_{i=1}^{s}deg(f_{i})-1\Bigg{)}q^{n/2}.$

######  Lemma 3.2.

([8], Theorem 5.6) Let us Consider two rational functions, $f(x)$ and $g(x)$,
both belonging to the field $\mathbb{F}_{q^{n}}(x)$. Express $f(x)$ as
$\prod_{j=1}^{s}f_{j}(x)^{a_{j}}$, where each $f_{j}(x)$ are irreducible
polynomials over the field $\mathbb{F}_{q^{n}}$ and
$a_{j}\in\mathbb{Z}\smallsetminus\\{0\\}$. Let
$D_{1}=\sum_{j=1}^{s}deg(f_{j})$, $D_{2}=max(deg(g(x)),0)$, $D_{3}$ is the
degree of the denominator of $g(x)$ and the sum of the degrees of the
irreducible polynomials dividing the denominator of $g(x)$ (excluding those
that are equal to $f_{j}(x)$, for some $j=1,2,\ldots,s$) is equal to $D_{4}$.
Let $\chi$ be a multiplicative character of $\mathbb{F}_{q^{n}}^{*}$ and
$\lambda$ is nontrivial additive character of $\mathbb{F}_{q^{n}}$. Also,
suppose that $g(x)$ is not of the form $H(x)^{q^{n}}-H(x)$,
$H(x)\in\mathbb{F}_{q^{n}}(x)$. Then

$\displaystyle\Bigg{|}\sum_{\alpha\in\mathbb{F}_{q^{n}},f(\alpha)\neq
0,\infty,g(\alpha)\neq\infty}\chi(f(\alpha))\lambda(g(\alpha))\Bigg{|}\leq(D_{1}+D_{2}+D_{3}+D_{4}-1)q^{n/2}.$

Let $r(>1)$ be a positive integer and $g\in\mathbb{F}_{q}[x]$. We use $W(r)$
to represent the number of square-free divisors of $r$ and $W(g)$ indicates
the number of square-free factors of $g$.

######  Lemma 3.3.

([12], Lemma 3.7) Let $\nu$ be a positive real number and $r\in\mathbb{N}$.
Then we have $W(r)<\mathcal{C}\cdot r^{\frac{1}{\nu}}$, where $\mathcal{C}$ is
defined as $\frac{2^{u}}{{({p_{1}p_{2}\ldots p_{u})}}^{\frac{1}{\nu}}}$ and
$p_{1},p_{2},\ldots,p_{u}$ are primes $\leq 2^{\nu}$ that divide $r$.

######  Lemma 3.4.

([7], Lemma 2.9) Let $q$ be a prime power and $n$ be a positive integer. Then
we have $W(x^{n}-1)\leq 2^{\frac{1}{2}\\{n+gcd(n,q-1)\\}}$. Moreover,
$W(x^{n}-1)\leq 2^{n}$ and $W(x^{n}-1)=2^{n}$ if and only if $n$ divides
$q-1$. Additionally, we have $W(x^{n}-1)\leq 2^{\frac{3}{4}n}$ if $n\nmid
q-1$.

We know that norm of a primitive element is also primitive. Moreover, Sharma
et al. [1] has proved the following lemma in a more general context.

######  Lemma 3.5.

([1], Lemma 3.1) Let $e$ be a positive divisor of $q^{n}-1$ and
$\delta=$gcd($e,q-1$). Additionally, let $L_{e}$ represents the largest
divisor of $e$ for which gcd($L_{e},\delta$)=1. Then an element
$\alpha\in\mathbb{F}_{q^{n}}^{*}$ is $l$-free $\iff$ $\alpha$ is $L_{e}$-free
and $N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)$ is $\delta$-free.

Since $L_{q^{n}-1}$ is the largest divisor of $q^{n}-1$ with
$gcd(L_{q^{n}-1},q-1)=1$, we can express $L_{q^{n}-1}$ as
$\frac{q^{n}-1}{(q-1)gcd(n,q-1)}$ and this further implies $W(L_{q^{n}-1})\leq
W(q^{n}-1)$.

##  4\. Main Results

Let $\beta\in\mathbb{F}_{q^{n}}^{*}$ and
$c_{1},c_{2},\ldots,c_{m}\in\mathbb{F}_{q}^{*}$. We shall establish a
sufficient condition which ensures the existence of an element
$\alpha\in\mathbb{F}_{q^{n}}^{*}$ such that the elements
$\alpha,\alpha+\beta,\ldots,\alpha+(m-1)\beta$ are all primitive and at least
one of them is normal together with
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)=c_{1}$,
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha+\beta)=c_{2}$,…,
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha+(m-1)\beta)=c_{m}$. Let
$e_{1},e_{2},\ldots,e_{m}$ be positive divisors of $q^{n}-1$,
$g\in\mathbb{F}_{q}[x]$ be a divisor of $x^{n}-1$ and
$\delta_{i}=$gcd($e_{i},q-1)$ for $i=1,2,\ldots,m$. Further, let ${L}_{e_{i}}$
be the largest divisor of $e_{i}$ such that $gcd(L_{e_{i}},\delta_{i})=1$ for
$i=1,2,\ldots,m$. To proceed further, let us consider the following
definitions.

###  4.1. Definitions.

  * 1.

For $m\geq 3$, let $\mathcal{S}_{m}$ be the set containing the pairs
$(q,n)\in\mathbb{N}\times\mathbb{N}$ such that for any
$\beta\in\mathbb{F}_{q^{n}}^{*}$ and a subset $\\{c_{i}\in\mathbb{F}_{q}:1\leq
i\leq m\\}\subset\mathbb{F}_{q}^{*}$, there exists an element
$\alpha\in\mathbb{F}_{q^{n}}^{*}$ such that the elements in the set
$\\{\alpha+(i-1)\beta:1\leq i\leq m\\}$ are all primitive, at least one is
normal and $N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha+(i-1)\beta)=c_{i}$
for $i=1,2,\dots,m$.

  * 2.

For $m\in\mathbb{N}$, we define $\mathcal{C}_{m}$ to be the set containing the
$m$-tuples $(c_{1},c_{2},\ldots,c_{m}),$ where $c_{i}\in\mathbb{F}_{q}^{*}$ be
such that $c_{i}$ is $\delta_{i}$-free for $i=1,2,\dots,m$.

  * 3.

For any $(c_{1},c_{2},\ldots,c_{m})\in\mathcal{C}_{m}$,
$\Psi_{c_{1},c_{2},\ldots,c_{m}}({e_{1}},{e_{2}},\ldots,{e_{m}},g)$ denotes
the cardinality of the set containing the elements
$\alpha\in\mathbb{F}_{q^{n}}^{*}$ that satisfy the following conditions:

    1. a.

$\alpha+(i-1)\beta$ is ${e_{i}}$-free for $i=1,2,\ldots,m$,

    2. b.

$\alpha+(j-1)\beta$ is $g$-free for some $j\in\\{1,2,\ldots,m\\}$,

    3. c.

$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha+(i-1)\beta)=c_{i}$.

  * 4.

For any $(c_{1},c_{2},\ldots,c_{m})\in\mathcal{C}_{m}$ and
$j\in\\{1,2,\ldots,m\\}$, we define the set
$\Psi_{c_{1},c_{2},\ldots,c_{m}}({e_{1}},{e_{2}},\ldots,{e_{m}},g,j)$ as the
number of the elements $\alpha\in\mathbb{F}_{q^{n}}^{*}$ that satisfy the
following conditions:

    1. a.

$\alpha+(i-1)\beta$ is ${e_{i}}$-free for $i=1,2,\ldots,m$,

    2. b.

$\alpha+(j-1)\beta$ is $g$-free,

    3. c.

$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha+(i-1)\beta)=c_{i}$.

We shall use the following abbreviations consistently throughout this article:

$\displaystyle\bar{c}=$
$\displaystyle(c_{1},c_{2},\ldots,c_{m}),~{}\overline{L_{{e}}}=(L_{e_{1}},L_{e_{2}},\ldots,L_{e_{m}}),W(\overline{L_{{e}}})=\prod_{i=1}^{m}W({L_{{e_{i}}}})$
$\displaystyle\text{and}~{}\bar{e}=\overline{q^{n}-1}~{}\text{when
}~{}e_{i}=q^{n}-1~{}\text{for}~{}i=1,2,\ldots,m.$

Thus we have

(1)
$\displaystyle\Psi_{\bar{c}}(\overline{L_{{e}}},g)\geq\frac{1}{m}\sum_{j=1}^{m}\Psi_{\bar{c}}(\overline{L_{{e}}},g,j).$

We now prove our principal result, as given in the following.

######  Theorem 4.1.

Let $q,n,m$ be positive integers such that $q$ is a prime power and $n>2m$.
Suppose that

$\displaystyle q^{\frac{n}{2}-m}\geq mW(\overline{L_{{q^{n}-1}}})W(x^{n}-1).$

Then $(q,n)\in\mathcal{S}_{m}$.

###### Proof.

Let $e_{1},e_{2},\ldots,e_{m}$ be positive divisors of $q^{n}-1$,
$g\in\mathbb{F}_{q}[x]$ be a divisor of $x^{n}-1$ and
$\beta\in\mathbb{F}_{q^{n}}^{*}$. Let $Z=\\{-(i-1)\beta:1\leq i\leq m\\}$.
From 1, using the definitions of the characteristic functions $\rho_{e}$,
$\kappa_{g}$ and $\pi_{c}$, we have

(2) $\displaystyle\Psi_{\bar{c}}(\overline{L_{{e}}},g)$
$\displaystyle\geq\frac{1}{m}\sum_{\alpha\in\mathbb{F}_{q^{n}}\smallsetminus
Z}\bigg{[}\prod_{i=1}^{m}\rho_{L_{e_{i}}}(\alpha+(i-1)\beta)\pi_{c_{i}}(\alpha+(i-1)\beta)\sum_{j=1}^{m}\kappa_{g}(\alpha+(j-1)\beta)\bigg{]}$
$\displaystyle=\frac{{\mathfrak{C}}}{m}\underset{1\leq i\leq
m}{\sum_{d_{i}|L_{e_{i}}}}\underset{}{\underset{h|g}{\sum}}\frac{\mu}{\phi}(d_{1},d_{2},\ldots,d_{m},h)\underset{1\leq
i\leq
m}{\sum_{\chi_{d_{i}}}}\sum_{{\lambda_{h}}}\boldsymbol{\chi}_{\bar{d},h,\bar{c}},$

where
$\mathfrak{C}=\frac{\phi(L_{e_{1}})\phi(L_{e_{2}})\ldots\phi(L_{e_{m}})\Phi_{q}(g)}{L_{e_{1}}L_{e_{2}}\ldots
L_{e_{m}}q^{deg(g)}(q-1)^{m}}$,
$\frac{\mu}{\phi}(d_{1},d_{2},\ldots,d_{m},h)=\frac{\mu(d_{1})\mu(d_{2})\ldots\mu(d_{m})\mu_{q}(h)}{\phi(d_{1})\phi(d_{2})\ldots\phi(d_{m})\Phi_{q}(h)}$
and

$\displaystyle\boldsymbol{\chi}_{\bar{d},h,\bar{c}}=\underset{\underset{}{}}{\sum_{k_{1},k_{2},\ldots,k_{m}=1}^{q-1}}\chi_{q-1}(c_{1}^{-k_{1}}c_{2}^{-k_{2}}\ldots$
$\displaystyle c_{m}^{-k_{m}})\sum_{\alpha\in\mathbb{F}_{q^{n}}\smallsetminus
Z}\prod_{i=1}^{m}\chi_{d_{i}}(\alpha+(i-1)\beta)$
$\displaystyle\times{\bar{\chi}}^{k_{i}}(\alpha+(i-1)\beta)\sum_{j=1}^{m}\lambda_{h}(\alpha+(j-1)\beta).$

Consider $\chi_{q^{n}-1}$ a generator of the multiplicative cyclic group
$\mathbb{F}_{q^{n}}^{*}$. Thus, for $i\in\\{1,2,\ldots,m\\}$ there exist
$t_{i}\in\\{0,1,2,\ldots,q^{n}-2\\}$ such that
$\chi_{d_{i}}(\alpha)=\chi_{q^{n}-1}^{t_{i}}(\alpha)$. Further, there exists
$y\in\mathbb{F}_{q^{n}}$ such that
$\lambda_{h}(\alpha)=\widehat{\lambda_{0}}(y\alpha)$. Here
$\widehat{\lambda}_{0}$ is the additive character of $\mathbb{F}_{q^{n}}$
defined by
$\widehat{\lambda}_{0}(\alpha)=\lambda_{0}(Tr_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha))$,
where $\lambda_{0}$ is the canonical additive character of $\mathbb{F}_{q}$.
Hence

(3)
$\displaystyle\boldsymbol{\chi}_{\tilde{d},h,\tilde{c}}=\underset{\underset{}{}}{\sum_{k_{1},k_{2},\ldots,k_{m}=1}^{q-1}}\chi_{q-1}(c_{1}^{-k_{1}}c_{2}^{-k_{2}}\ldots$
$\displaystyle
c_{m}^{-k_{m}})\sum_{j=1}^{m}\widehat{\lambda_{0}}((j-1)y\beta)$
$\displaystyle\times\sum_{\alpha\in\mathbb{F}_{q^{n}}\smallsetminus{Z}}\chi_{q^{n}-1}(F(\alpha))\widehat{\lambda_{0}}(y\alpha).$

where
$F(x)=\prod_{i=1}^{m}\\{x+(i-1)\beta\\}^{{\frac{q^{n}-1}{q-1}k_{i}+t_{i}}}$.
If we have $F(x)=H(x)^{q^{n}-1}$ for some $H(x)\in\mathbb{F}_{q^{n}}(x)$, then
comparing the powers of $x+(i-1)\beta$ we get
$\frac{q^{n}-1}{q-1}k_{i}+t_{i}=(q^{n}-1)r_{i}$, for some non negative integer
$r_{i}$. From this equation it follows that
$t_{i}=(q^{n}-1)(r_{i}-\frac{k_{i}}{q-1})\geq(q^{n}-1)(r_{i}-1)$. Since
$t_{i}\in\\{0,1,\ldots,q^{n}-2\\}$, the latter one implies that $r_{i}=1$.
Thus we have $t_{i}=(q^{n}-1)(1-\frac{k_{i}}{q-1})$ for $i=1,2,\ldots,m$. As
$\chi_{d_{i}}=\chi_{q^{n}-1}^{t_{i}}$, there is a positive integer
$k_{i}^{{}^{\prime}}$ such that $t_{i}d_{i}=(q^{n}-1)k_{i}^{{}^{\prime}}$,
which further implies $k_{i}^{{}^{\prime}}(q-1)=d_{i}(q-1-k_{i})$. Since
$gcd(q-1,d_{i})=1$, it follows that $d_{i}|k_{i}^{{}^{\prime}}$. Thus we have
$q^{n}-1|t_{i}$, which is possible only if $t_{i}=0$. Hence $\bar{t}=\bar{0}$,
that is, $\bar{d}=\bar{1}$.

Moreover, we have $yx\neq H(x)^{q^{n}}-H(x)$ for any
$H(x)\in\mathbb{F}_{q^{n}}(x)$ unless we have $H(x)$ is constant and $y=0$,
that is $h=1$. Consequently, if $\bar{d}\neq\bar{1}$ or $h\neq 1$ then from
the Lemma 3.2 we have

(4) $\displaystyle|\boldsymbol{\chi}_{\tilde{d},h,\tilde{c}}|$
$\displaystyle\leq m^{2}q^{\frac{n}{2}+m}.$

From (3), we have

(5)
$\displaystyle\boldsymbol{\chi}_{\tilde{1},1,\tilde{c}}=m\underset{\underset{}{}}{\sum_{k_{1},k_{2},\ldots,k_{m}=1}^{q-1}}\chi_{q-1}(c_{1}^{-k_{1}}c_{2}^{-k_{2}}\ldots
c_{m}^{-k_{m}})\sum_{\alpha\in\mathbb{F}_{q^{n}}\smallsetminus{Z}}\chi_{q^{n}-1}(\bar{F}(\alpha)),$

where
$\bar{F}(x)=\prod_{i=1}^{m}\\{x+(i-1)\beta\\}^{{\frac{q^{n}-1}{q-1}k_{i}}}$.
Suppose that $F_{i}(x)=x+(i-1)\beta$ for $i=1,2,\ldots,m$. We consider the
following cases based on possible values of $d_{i}$’s.

Case(1): Let $S_{1}$ be the case when $k_{i}=q-1$ for $i=1,2,\ldots,m$.
Clearly, we have $S_{1}=m(q^{n}-m)$.

Case(2): Let $S_{2}$ be the case when for fixed $i\in\\{1,2,\ldots,m\\}$,
$k_{i}$ takes value in $\\{1,2,\ldots,q-2\\}$ and rest others are equal to
$(q-1)$. There are total ‘$m$’ such possibilities. Thus

$\displaystyle|S_{2}|$ $\displaystyle\leq
m^{2}\Bigg{|}\sum_{k_{i}=1}^{q-2}\chi_{q-1}(c_{i}^{-k_{i}})\sum_{\alpha\in\mathbb{F}_{q^{n}}\smallsetminus
Z}\chi_{q^{n}-1}^{{\frac{q^{n}-1}{q-1}k_{i}}}(F_{i}(\alpha))\Bigg{|}.$

Since $\chi_{q^{n}-1}^{{\frac{q^{n}-1}{q-1}k_{i}}}$ is a nontrivial
multiplicative character in $\widehat{\mathbb{F}_{q^{n}}^{*}}$, we must have

$\displaystyle\sum_{\alpha\in\mathbb{F}_{q^{n}}\smallsetminus\\{-(i-1)\beta\\}}\chi_{q^{n}-1}^{{\frac{q^{n}-1}{q-1}k_{i}}}(F_{i}(\alpha))=0,$

which gives

$|S_{2}|\leq m^{2}(m-1)(q-2).$

Case(3): Let $S_{3}$ be the case when for a given pair $(i,j)$ of distinct
integers belonging to the set $\\{1,2,\ldots,m\\}$, the variables $k_{i}$ and
$k_{j}$ take values in the range ${1,2,\ldots,q-2}$, while all other $k_{p}$’s
are set to $(q-1)$. There are a total of ‘$\binom{m}{2}$’ possibilities in
this case. Hence we have

$\displaystyle|S_{3}|$ $\displaystyle\leq
m\binom{m}{2}\Bigg{|}\sum_{k_{i},k_{j}=1}^{q-2}\chi_{q-1}(c_{i}^{-k_{i}}c_{j}^{-k_{j}})\sum_{\alpha\in\mathbb{F}_{q^{n}}\smallsetminus{Z}}\chi_{q^{n}-1}\Bigg{(}F_{i}(\alpha)^{{\frac{q^{n}-1}{q-1}k_{i}}}F_{j}(\alpha)^{{\frac{q^{n}-1}{q-1}k_{j}}}\Bigg{)}\Bigg{|}.$

Clearly we have
$F_{i}(x)^{{\frac{q^{n}-1}{q-1}k_{i}}}F_{j}(x)^{{\frac{q^{n}-1}{q-1}k_{j}}}\neq
H(x)^{q^{n-1}}$ for any $H(x)\in\mathbb{F}_{q^{n}}(x)$. Thus by Lemma 3.1, we
get

$|S_{3}|\leq m\binom{m}{2}(q-2)^{2}\\{q^{\frac{n}{2}}+(m-2)\\}.$

Case(4): Let $S_{4}$ be the case when for a given triple $(i,j,l)$ of distinct
integers belonging to the set $\\{1,2,\ldots,m\\}$, the variables $k_{i}$,
$k_{j}$ and $k_{l}$ each taking values in the range ${1,2,\ldots,q-2}$, while
all other $k_{p}$’s are set to $(q-1)$. There are a total of ‘$\binom{m}{3}$’
possibilities in this case. Proceeding in a similar manner as done in the
previous case, we have

$|S_{4}|\leq m\binom{m}{3}(q-2)^{3}\\{2q^{\frac{n}{2}}+(m-3)\\}.$ $\vdots$

Case(m+1): Let $S_{m+1}$ be the case when for each $i\in\\{1,2,\ldots,m\\}$,
$k_{i}$ take values in the range $1,2,\ldots,q-2$. Here we have

$\displaystyle
S_{m+1}=m\underset{\underset{}{}}{\sum_{k_{1},k_{2},\ldots,k_{m}=1}^{q-2}}\chi_{q-1}(c_{1}^{-k_{1}}c_{2}^{-k_{2}}\ldots
c_{m}^{-k_{m}})\sum_{\alpha\in\mathbb{F}_{q^{n}}\smallsetminus{Z}}\chi_{q^{n}-1}(\bar{F}(\alpha)),$

which implies

$|S_{m+1}|\leq m(q-2)^{m}(m-1)q^{\frac{n}{2}}.$

Taking into the consideration of all the above possibilities and using the
equation (5), we get

$\displaystyle|\boldsymbol{\chi}_{\tilde{1},1,\tilde{c}}-m(q^{n}-m)|$
$\displaystyle\leq
m\Bigg{[}m(q-2)(m-1)+\binom{m}{2}(q-2)^{2}\\{q^{\frac{n}{2}}+(m-2)\\}$
$\displaystyle+\binom{m}{3}(q-2)^{3}\\{2q^{\frac{n}{2}}+(m-3)\\}+\ldots+(q-2)^{m}(m-1)q^{\frac{n}{2}}\Bigg{]}$
$\displaystyle=m\sum_{i=1}^{m}\binom{m}{i}(q-2)^{i}\\{(m-i)+q^{\frac{n}{2}}(i-1)\\}.$

If $m$ is a positive integer, then we have

(6) $(x+1)^{m}-1=\sum_{i=1}^{m}\binom{m}{i}x^{i}.$

Division by ‘$x$’ in both sides, followed by differentiation, the latter
equation transforms into

(7)
$\displaystyle\sum_{i=1}^{m}\binom{m}{i}(i-1)x^{i}=mx(x+1)^{m-1}-(x+1)^{m}+1.$

We rewrite (6) as,

$\displaystyle\sum_{i=1}^{m-1}\binom{m}{i+1}x^{i+1}=(x+1)^{m}-mx-1.$

Taking the derivative with respect to ‘$x$’ on both sides of the above
equation we get,

$\displaystyle\sum_{i=1}^{m-1}\binom{m}{i+1}(i+1)x^{i}=m(x+1)^{m-1}-m.$

Let us apply the binomial identity $\binom{m}{i}(m-i)=\binom{m}{i+1}(i+1)$ in
the previous equation. Thus

(8) $\sum_{i=1}^{m}\binom{m}{i}(m-i)x^{i}=m(x+1)^{m-1}-m.$

Substituting ‘$x$’ with ‘$(q-2)$’ in (7) and (8), we obtain the following
summations

$\sum_{i=1}^{m}\binom{m}{i}(i-1)(q-2)^{i}=m(q-2)(q-1)^{m-1}-(q-1)^{m}+1$ and
$\sum_{i=1}^{m}\binom{m}{i}(m-i)(q-2)^{i}=m(q-1)^{m-1}-m.$

Hence we have

$\displaystyle\boldsymbol{\chi}_{\tilde{1},1,\tilde{c}}$ $\displaystyle\geq
m[(q^{n}-m)-q^{\frac{n}{2}}\\{m(q-2)(q-1)^{m-1}-(q-1)^{m}+1\\}-m\\{(q-1)^{m-1}-1\\}]$
$\displaystyle=m[q^{n}-q^{\frac{n}{2}}\\{m(q-2)(q-1)^{m-1}-(q-1)^{m}+1\\}-m(q-1)^{m-1}].$

Using the above lower bound, it can be deduced from equations (3) and (4) that

$\displaystyle\Psi_{\bar{c}}(\overline{L_{{e}}},g)$
$\displaystyle\geq\mathcal{C}[q^{n}-q^{\frac{n}{2}}\\{m(q-2)(q-1)^{m-1}-(q-1)^{m}+1\\}-m(q-1)^{m-1}$
$\displaystyle-mq^{\frac{n}{2}+m}(W(\overline{L_{{e}}})W(g)-1)]$
$\displaystyle>\mathcal{C}\\{q^{n}-mq^{\frac{n}{2}+m}W(\overline{L_{{e}}})W(g)+q^{\frac{n}{2}}(q-1)^{m}-m(q-1)^{m-1}\\},$

which is positive if we have $q^{\frac{n}{2}-m}>mW(\overline{L_{{e}}})W(g)$.
Clearly, the result follows by letting $e=e_{1}=e_{2}=\ldots=e_{m}=q^{n}-1$
and $g=x^{n}-1$. ∎

In the following lemma, we refer the sieving inequality, originally introduced
by Kapetanakis in [5] and subsequently apply the modified form of this
inequality.

######  Lemma 4.2.

Let $q,n,m$ be positive integers such that $q$ is a prime power and $n>2m$.
Let $e=e_{1}=e_{2}=\ldots=e_{m}$ be a divisor of $L_{q^{n}-1}$ and
$p_{1},p_{2},\ldots,p_{r}$ be the distinct primes dividing $L_{q^{n}-1}$ but
not $e$. Moreover, let $g$ be a divisor of $x^{n}-1$ and
$g_{1},g_{2},\ldots,g_{s}$ be the distinct irreducible polynomials dividing
$x^{n}-1$ but not $g$. Then for $j\in\\{1,2,\ldots,m\\}$, we have

(9) $\displaystyle\Psi_{\bar{c}}(\overline{L_{{q^{n}-1}}},x^{n}-1,j)$
$\displaystyle\geq\sum_{i=1}^{r}\Psi_{\bar{c}}(p_{i}e_{1},e_{2},\ldots,e_{m},g,j)+\sum_{i=1}^{r}\Psi_{\bar{c}}(e_{1},p_{i}e_{2},\ldots,e_{m},g,j)$
$\displaystyle+\ldots+\sum_{i=1}^{r}\Psi_{\bar{c}}(e_{1},e_{2},\ldots,p_{i}e_{m},g,j)+\sum_{i=1}^{s}\Psi_{\bar{c}}(\bar{e},g_{i}g,j)$
$\displaystyle-(mr+s-1)\Psi_{\bar{c}}(\bar{e},g,j).$

######  Lemma 4.3.

Let $q,n,m$ be positive integers such that $q$ is a prime power and $n>2m$.
Let $e=e_{1}=e_{2}=\ldots=e_{m}$ be a divisor of $L_{q^{n}-1}$ and $p$ be a
prime dividing $L_{q^{n}-1}$ but not $e$. Moreover, let $g$ be a divisor of
$x^{n}-1$ and $g^{\prime}$ be an irreducible factors of $x^{n}-1$ but not $g$.
Denote $\prod_{i=1}^{m}W(e_{i})$ and $\prod_{i=1}^{m}\theta(e_{i})$ by
$W(\bar{e})$ and $\theta(\bar{e})$ respectively. Then for
$j\in\\{1,2,\ldots,m\\}$, we have

$\displaystyle|\Psi_{\bar{c}}(p_{i}e_{1},e_{2},\ldots,e_{m},g,j)-\theta(p)\Psi_{\bar{c}}(\bar{e},g,j)|$
$\displaystyle\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\theta(p)}W(\bar{e})W(g),$
$\displaystyle|\Psi_{\bar{c}}(e_{1},pe_{2},\ldots,e_{m},g,j)-\theta(p)\Psi_{\bar{c}}(\bar{e},g,j)|$
$\displaystyle\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\theta(p)}W(\bar{e})W(g),$
$\displaystyle\vdots$
$\displaystyle|\Psi_{\bar{c}}(e_{1},e_{2},\ldots,pe_{m},g,j)-\theta(p)\Psi_{\bar{c}}(\bar{e},g,j)|$
$\displaystyle\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\theta(p)}W(\bar{e})W(g),$ and
$\displaystyle|\Psi_{\bar{c}}(e_{1},e_{2},\ldots,e_{m},gg^{\prime},j)-\Theta(g^{\prime})\Psi_{\bar{c}}(\bar{e},g,j)|$
$\displaystyle\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\Theta(g^{\prime})}W(\bar{e})W(g).$

###### Proof.

From the definition, we have

$\Psi_{\bar{c}}(pe_{1},e_{2},\ldots,e_{m},g,j)-\theta(p)\Psi_{\bar{c}}(\bar{e},g,j)=\theta(\bar{e})\Theta(g)\theta(p)\underset{t\in\\{2,3,\ldots,m\\}}{\underset{d_{t}|e_{t}}{\underset{p|{d_{1}}|pe_{1},h|g}{\sum}}}\frac{\mu}{\phi}(\bar{d},h)\underset{1\leq
i\leq
m}{\sum_{\chi_{d_{i}},\lambda_{h}}}\boldsymbol{\chi}_{\bar{d},h,\bar{c}}$

Now, using the inequality $|\boldsymbol{\chi}_{\bar{d},h,\bar{c}}|\leq
m^{2}q^{\frac{n}{2}+m}$, we get

$|\Psi_{\bar{c}}(pe_{1},e_{2},\ldots,e_{m},g,j)-\theta(p)\Psi_{\bar{c}}(\bar{e},g,j)|\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\theta(p)}W(\bar{e})W(g).$

Similarly we have,

$\displaystyle|\Psi_{\bar{c}}(e_{1},pe_{2},\ldots,e_{m},g,j)-\theta(p)\Psi_{\bar{c}}(\bar{e},g,j)|$
$\displaystyle\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\theta(p)}W(\bar{e})W(g),$
$\displaystyle|\Psi_{\bar{c}}(e_{1},pe_{2},\ldots,e_{m},g,j)-\theta(p)\Psi_{\bar{c}}(\bar{e},g,j)|$
$\displaystyle\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\theta(p)}W(\bar{e})W(g),$
$\displaystyle\vdots$
$\displaystyle|\Psi_{\bar{c}}(e_{1},e_{2},\ldots,pe_{m},g,j)-\theta(p)\Psi_{\bar{c}}(\bar{e},g,j)|$
$\displaystyle\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\theta(p)}W(\bar{e})W(g).$

Further,

$\Psi_{\bar{c}}(e_{1},e_{2},\ldots,e_{m},gg^{\prime},j)-\Theta(g^{\prime})\Psi_{\bar{c}}(\bar{e},g,j)=\theta(\bar{e})\Theta(g)\Theta(g^{\prime})\underset{}{\underset{g^{\prime}|h}{\underset{\bar{d}|\bar{e},h|gg^{\prime}}{\sum}}}\frac{\mu}{\phi}(\bar{d},h)\underset{1\leq
i\leq
m}{\sum_{\chi_{d_{i}},\lambda_{h}}}\boldsymbol{\chi}_{\bar{d},h,\bar{c}}.$

Hence

$|\Psi_{\bar{c}}(e_{1},e_{2},\ldots,e_{m},gg^{\prime},j)-\Theta(g^{\prime})\Psi_{\bar{c}}(\bar{e},g,j)|\leq
m^{2}q^{\frac{n}{2}+m}{\theta(\bar{e})\Theta(g)\Theta(g^{\prime})}W(\bar{e})W(g).$

∎

######  Proposition 4.4.

Assuming all the notations and conditions in the Lemma 4.2, we define

$\displaystyle\delta:=1-m\sum_{i=1}^{r}\frac{1}{p_{i}}-\sum_{i=1}^{s}\frac{1}{q^{deg(g_{j})}}$

and

$\displaystyle\Delta:=\frac{mr+s-1}{\delta}+2.$

If $\delta>0$ and

$q^{\frac{n}{2}-m}>m{W(\bar{e})}W(g)\Delta$

then $(q,n)\in\mathcal{S}_{m}$.

###### Proof.

For fix $j\in\\{1,2,\ldots,m\\}$, let us rewrite the equation (9) as

$\displaystyle\Psi_{\bar{c}}(\overline{L_{{q^{n}-1}}},x^{n}-1,j)$
$\displaystyle\geq\sum_{i=1}^{r}[\Psi_{\bar{c}}(p_{i}e_{1},e_{2},\ldots,e_{m},g,j)-\theta(p_{i})\Psi_{\bar{c}}(\bar{e},g,j)]$
$\displaystyle+\sum_{i=1}^{r}[\Psi_{\bar{c}}(e_{1},p_{i}e_{2},\ldots,e_{m},g,j)-\theta(p_{i})\Psi_{\bar{c}}(\bar{e},g,j)]+\ldots$
$\displaystyle+\sum_{i=1}^{r}[\Psi_{\bar{c}}(e_{1},e_{2},\ldots,p_{i}e_{m},g,j)-\theta(p_{i})\Psi_{\bar{c}}(\bar{e},g,j)]$
$\displaystyle+\sum_{i=1}^{s}[\Psi_{\bar{c}}(e_{1},e_{2},\ldots,p_{i}e_{m},gg_{i},j)-\Theta(g_{i})\Psi_{\bar{c}}(\bar{e},g,j)]+\delta\Psi_{\bar{c}}(\bar{e},g,j).$

We obtain the subsequent expression by applying the Lemma 4.3, as

$\displaystyle\Psi_{\bar{c}}(\overline{L_{{q^{n}-1}}},x^{n}-1,j)\geq\frac{\phi(e)\cdot\Phi_{q}(g)}{e\cdot
q^{deg(g)}}\Bigg{[}\Bigg{(}m$
$\displaystyle\sum_{i=1}^{r}\theta(p_{i})+\sum_{i=1}^{s}\Theta(g_{i})\Bigg{)}(-m^{2}W(\bar{e})W(g)q^{\frac{n}{2}+m})$
$\displaystyle+\delta\\{m(q^{n}-m)-m^{2}q^{\frac{n}{2}+m}(W(\bar{e})W(g)-1)\\}\Bigg{]},$

which implies

$\displaystyle\Psi_{\bar{c}}(\overline{L_{{q^{n}-1}}},x^{n}-1,j)\geq\frac{\phi(e)\cdot\Phi_{q}(g)}{e\cdot
q^{deg(g)}}$
$\displaystyle\delta\Bigg{[}\Bigg{(}\frac{m\sum_{i=1}^{r}\theta(p_{i})+\sum_{i=1}^{s}\Theta(g_{i})}{\delta}+1\Bigg{)}\times$
$\displaystyle(-m^{2}W(\bar{e})W(g)q^{\frac{n}{2}+m})+\\{m(q^{n}-m)+m^{2}q^{\frac{n}{2}+m}\\}\Bigg{]}.$

Here we note that
$\delta=m\sum_{i=1}^{r}\theta(p_{i})+\sum_{i=1}^{s}\Theta(g_{i})-(mr+s-1)$.
Then the above inequality becomes

$\displaystyle\Psi_{\bar{c}}(\overline{L_{{q^{n}-1}}},x^{n}-1,j)$
$\displaystyle\geq\frac{\phi(e)\cdot\Phi_{q}(g)}{e\cdot q^{deg(g)}}\delta
m\Bigg{[}-m\Delta
W(\bar{e})W(g)q^{\frac{n}{2}+m}+\\{(q^{n}-m)+mq^{\frac{n}{2}+m}\\}\Bigg{]},$

where $\Delta=\frac{mr+s-1}{\delta}+2$. Then using the equation (1), it
follows that given $\delta>0$,
$\Psi_{\bar{c}}(\overline{L_{{q^{n}-1}}},x^{n}-1)>0$ if we have

(10) $q^{\frac{n}{2}-m}>m{W(\bar{e})}W(g)\Delta.$

∎

######  Corollary 4.5.

Let $q,n\in\mathbb{N}$ such that $q$ is a prime power, $n>4$ and let
$\beta\in\mathbb{F}_{q^{n}}^{*}$. Then for any
$c_{1},c_{2}\in\mathbb{F}_{q}^{*}$, there exists an element
$\alpha\in\mathbb{F}_{q^{n}}$ such that both $\alpha$, $\alpha+\beta$ are
primitive and at least one of them is normal together with
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha)=c_{1}$ and
$N_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\alpha+\beta)=c_{2}$ if we have

(11) $q^{\frac{n}{2}-2}\geq 2W({L_{{q^{n}-1}}})^{2}W(x^{n}-1).$

##  5\. Working example

In this part, we will identify those $(q,n)$ that might not belong to
$\mathcal{S}_{2}$ for $p=3$, $q=3^{k}$. For $n=5$, we have to go through an
exhaustive computation and thus a different approach is required in this case.
In this article, we consider the cases $n\geq 6$. Further, we divide our
computations into two parts. In the first part, we determine the exceptions
$(q,n)$ when $n\geq 9$, and in the next part, we carry out computations for
$n=6,7,~{}\text{and}~{}8$. We use SageMath [14] as the computational tool for
all nontrivial computations needed in this article.

###  5.1. Part I

In this part, we assume that $n\geq 9$. Then the equation 11 and Lemmas 3.3,
3.4 together implies that $(q,n)\in\mathcal{S}_{2}$ if

(12) $\displaystyle q^{\frac{n}{2}-2}$
$\displaystyle>2~{}\mathcal{C}^{2}q^{\frac{2n}{\nu}}2^{n}.$

Moreover, from the proposition (4.4),
$\Psi_{\bar{c}}(\overline{L_{{q^{n}-1}}},x^{n}-1)>0$ if

(13) $\displaystyle q^{\frac{n}{2}-2}>2{W(e)}^{2}W(g)\Delta.$

Choosing $\nu=11.2$, the inequality (12) is satisfied for $k\geq 291$ and for
$n\geq 7$. Further, if $3\leq k\leq 290$, Table 1 gives the values of $n_{k}$,
such that the inequality (12) satisfies for $n\geq n_{k}$ and appropriate
choices of $\nu$.

######  Lemma 5.1.

Let $q$ and $n$ be positive integers where $q=3^{k}$ with $k\geq 3$ and $n\geq
9$. Then we have $(q,n)\in\mathcal{S}_{2}$.

###### Proof.

From the Table 1, it is clear that $(q,n)\in\mathcal{S}_{2}$ for all $k\geq
61$ and $n\geq 9$. For the remaining pairs, we first verify the inequality
$q^{\frac{n}{2}-2}\geq 2\mathcal{C}^{2}q^{\frac{2n}{\nu}}W(x^{n}-1)$ and then,
the pairs do not satisfy this, we test the inequality (11). Consequently, we
get $(q,n)\in\mathcal{S}_{2}$ unless $(3^{3},10),(3^{3},13),(3^{4},9)$ and
$(3^{4},10)$. For these pairs, choose $e,g$ as given in the Table 4 and after
verifying (13), we find that all of the pairs $(q,n)\in\mathcal{S}_{2}$. ∎

Table 1. Values of $n_{k}$ such that $3\leq k\leq 290$ $\nu$ | $k$ | $n_{k}$
---|---|---
9.0 | {3} | 151
8.5 | {4} | 65
8 | {5} | 42
8 | {6} | 33
8 | {7} | 27
8 | {8} | 24
8 | {9} | 21
7.5 | {10} | 20
7.9 | {11,12} | 18
7.5 | {13} | 17
7.5 | {14} | 16
7.9 | {15,16} | 15
7.9 | {17,18,19} | 14
7.9 | {20,21,22,23} | 13
7.9 | {24,25,…,29} | 12
8.7 | {30,31,…,39} | 11
8.7 | {40,41,…,60} | 10
9.5 | {61,62,…,109} | 9
10.2 | {110,111,…,290} | 8

Next we consider the cases $k=1,2$. Let us express $n=n^{\prime}\cdot 3^{i}$;
$i\geq 0$, where $gcd(n{{}^{\prime}},3)=1$. As a consequence, we have
$W(x^{n}-1)=W(x^{n^{\prime}}-1)$. We now divide our discussion in two parts:

  * •

$n^{\prime}|q^{2}-1$

  * •

$n^{\prime}\nmid q^{2}-1$.

Initially, we suppose that $n{{}^{\prime}}|q^{2}-1$ and establish the
following lemma:

######  Lemma 5.2.

Let $q=3^{k};k=1,2,n\geq 9$ and $n{{}^{\prime}}|q^{2}-1$. Then
$(q,n)\in\mathcal{S}_{2}$ with possible exceptions $(3,9)$ and $(3,12)$.

###### Proof.

Rewrite the inequality (12) as follows

(14) $\displaystyle q^{{n^{\prime}\cdot 3^{i}}/{2}-2}$
$\displaystyle>2~{}\mathcal{C}^{2}~{}q^{{2n^{\prime}\cdot
3^{i}}/{\nu}}~{}2^{n^{\prime}}$

Case $(i)$: Let $k=1$. Taking $\nu=7$, the inequality (14) is satisfied for
$i\geq 3$, when $n^{\prime}=4,8$ and for $i\geq 4$, when $n^{\prime}=1,2$.
Thus for $n\geq 9$, $(3,n)\in\mathcal{S}_{2}$ unless
$n=9,12,18,24,27,36,54,72$. While testing the inequality (11) with these
values, we find that $(3,n)\in\mathcal{S}_{2}$ unless $n=9,12,18,24$. For
these specific values of $n$, choose $e$, $g$ as provided in Table 4 to
satisfy the inequality (13), resulting in $(q,n)\in\mathcal{S}_{2}$ except
when $n=9,12$.
Case $(ii)$: Let $k=2$. Taking $\nu=7$, the inequality (11) is satisfied for
$i\geq 1$, when $n^{\prime}=40,80$; for $i\geq 2$, when
$n^{\prime}=5,8,10,16,20$; for $i\geq 3$, when $n^{\prime}=2,4$ and $i\geq 4$,
when $n{{}^{\prime}}=1$. Thus for $n\geq 9$, $(9,n)\in\mathcal{S}_{2}$ unless
$n=9,10,12,15,16,18,20,24,27,30,36,40,48,60,80$. While testing the inequality
(11) with these values, we find that $(9,n)\in\mathcal{S}_{2}$ except when
$n=9,10,12,15,16$. For these specific values of $n$, choose $l,g$ as provided
in Table 4 to satisfy the inequality (14), resulting in
$(q,n)\in\mathcal{S}_{2}$ for all $n$. ∎

Let $n$ be represented as $n=n^{\prime}\cdot q^{i}$; $i\geq 0$, where $q$ is a
prime power such that $gcd(n^{\prime},q)=1$. Additionally, let $d$ denote the
order of $q$ modulo $n^{\prime}$, with $q$ and $n^{\prime}$ being co-prime.
According to [[10], Theorems $2.45$ and $2.47$], $x^{n^{\prime}}-1$ can be
expressed as the product of irreducible polynomials in $\mathbb{F}_{q}[x]$,
each having a degree less than or equal to $d$.

Let $N_{0}$ denote the number of irreducible factors of $x^{n^{\prime}}-1$
over $\mathbb{F}_{q}$, each having a degree less than $d$, and let
$\rho(q,n^{\prime})$ represent the ratio $\frac{N_{0}}{n^{\prime}}$. Note that
the number of irreducible factors of $x^{n}-1$ over $\mathbb{F}_{q}$ is
identical to the number of irreducible factors of $x^{n^{\prime}}-1$ over
$\mathbb{F}_{q}$, which implies $n\rho(q,n)=n^{\prime}\rho(q,n^{\prime})$.

In fact, when $p=3$ and $n=n{{}^{\prime}}\cdot 3^{i}$, where $3\nmid
n{{}^{\prime}}$, the subsequent lemma provides bounds for $\rho(q,n)$, which
will be used in further discourse.

######  Lemma 5.3.

([12], Lemmas 6.1, 7.1) Let $q=3^{k}$ and $n{{}^{\prime}}>4$ be such that
$3\nmid n{{}^{\prime}}$. Then the following hold:

  * (i)

If $n{{}^{\prime}}=2\cdot gcd(q-1,n{{}^{\prime}})$, then $d=2$ and
$\rho(q,n{{}^{\prime}})=1/2$.

  * (ii)

If $n{{}^{\prime}}=4\cdot gcd(q-1,n{{}^{\prime}})$ and $q\equiv 1(mod~{}4)$,
then $d=4$ and $\rho(q,n{{}^{\prime}})=3/8$.

  * (iii)

$\rho(3,16)=5/16$, otherwise $\rho(3,n{{}^{\prime}})\leq 1/4$.

  * (iv)

Elsewhere, $\rho(q,n{{}^{\prime}})\leq 1/3$.

######  Lemma 5.4.

Let $q=p^{k}$; $k\in\mathbb{N}$ and $n=n^{\prime}\cdot q^{i}$; $i\geq 0$,
where $n^{\prime}$ and $q$ are co-prime with $n^{\prime}\nmid q-1$. Suppose
$d(>2)$ be the order of $q$ modulo $n^{\prime}$. Moreover, let $e$ be equal to
$L_{q^{n}-1}$ and $g$ be the product of all irreducible factors of
$x^{n^{\prime}}-1$ having degrees less than $d$. Then, in accordance with the
proposition (4.4), we have $\Delta<2n^{\prime}$.

###### Proof.

We omit the proof of the lemma, as it follows from [[9], Lemma 10]. ∎

######  Lemma 5.5.

Let $q=3^{k};k=1,2,n\geq 9$ and $n{{}^{\prime}}\nmid q^{2}-1$. Then
$(q,n)\in\mathcal{S}_{2}$ with possible exceptions $(3,10)$ and $(3,16)$.

###### Proof.

Case $(i)$: Let $k=1$. It is clear that $n^{\prime}\geq 3$ and from Lemma 5.3,
it follows that $\rho(3,n^{\prime})\leq 1/4$ except $n^{\prime}=16$. We
consider $e$ as $L_{q^{n}-1}$ and $g$ as the product of all irreducible
factors of $x^{n^{\prime}}-1$ with degrees less than $d$. Then by Lemma 5.4
and the inequality (14), the pairs $(q,n)\in\mathcal{S}_{2}$, if the
inequality
$3^{\frac{n}{2}-2}>2~{}\mathcal{C}^{2}3^{\frac{2n}{\nu}}2^{\frac{n}{4}}2n$ is
true. This inequality is valid for $n\geq 277$ and $\nu=9.2$. For $n\leq 276$,
we verify the inequality (11) and find that $(3,n)\in\mathcal{S}_{2}$ except
for $n=10,11,13,14,15,20,22$. For these exceptions, we choose the values of
$e$ and $g$ as mentioned in Table 4, and test the inequality 13. Hence we
have, $(3,n)\in\mathcal{S}_{2}$ except for $n=10$.

Now we consider the case $n^{\prime}=16$. Here we test the inequality
$3^{\frac{16\cdot 3^{i}}{2}-2}>64~{}\mathcal{C}^{2}~{}3^{\frac{32\cdot
3^{i}}{\nu}}~{}2^{5/16}$ and get that $(3,16\cdot 3^{i})\in\mathcal{S}_{2}$
for all $i\geq 2$ and $\nu=9.2$. Among the exceptionas $(3,16),(3,48)$, the
last one satisfies the inequality (11), however for the remaining one , the
inequality (14) does not hold for any choice of $e$ and $g$.

Case $(ii)$: Let $k=2$. If $n^{{}^{\prime}}\nmid q^{2}-1$, then
$n^{\prime}\nmid q-1$ and by Lemma 3.4 $W(x^{n^{\prime}}-1)\leq
2^{3n^{\prime}/4}$. Then the inequality (11) is true if
$9^{{n}/{2}-2}>2~{}\mathcal{C}^{2}9^{{2n}/{\nu}}2^{{3n}/{4}}$ is true and the
latter is true for $n\geq 335$ and $\nu=9.2$. For $9\leq n\leq 334$, we verify
the inequality (11) and find that $(9,n)\in\mathcal{S}_{2}$ except for
$n=11,14$. For these exceptional cases, we choose values for $e$ and $g$ as
listed in Table 4 for which the inequality (14) is true and get that
$(9,n)\in\mathcal{S}_{2}$. ∎

###  5.2. Part II

In this section, we shall verify the cases where $n$ takes values of
$6,7,~{}\text{or}~{}8$. We shall also utilize the following result for further
calculations.

######  Lemma 5.6.

([22], Lemma 5.4) For any $M\in\mathbb{N}$ satisfying $\omega(M)\geq 2828$, we
have $W(M)<M^{\frac{1}{13}}$.

First, let us suppose that $\omega(q^{n}-1)\geq 2828$. Clearly, in this part
we have $W(x^{n}-1)\leq 2^{8}$. Then (11) and the Lemma 5.6 together implies
that $(q,n)\in\mathcal{S}_{2}$ if we have $q^{\frac{n}{2}-2}>2^{9}\cdot
q^{\frac{2n}{13}}$ or equivalently if $q^{\frac{9n}{26}-2}>2^{9}$, that is if
we have $q^{n}>512^{\frac{26n}{9n-52}}$. This holds for $q^{n}>512^{78}$,
which is true for $\omega(q^{n}-1)\geq 2828$. For further progress we follow
[22]. We now assume that $88\leq\omega(q^{n}-1)\leq 2827$. Choosing
$g={x^{n}-1}$ and $e$ to be the product of least $88$ primes dividing
$L_{q^{n}-1}$ i.e., $W(e)=2^{88}$. Then $r\leq 2739$ and $\delta$ will be
least when $\\{p_{1},p_{2},\ldots,p_{2739}\\}=\\{461,463,\ldots,25667\\}$.
This gives $\delta>0.0044306$ and $\Delta<1.2362\times 10^{6}$, hence $2\Delta
W(e)^{2}W(g)<6.07\times 10^{61}=T$(say). By Proposition 4.4,
$(q,n)\in\mathcal{S}_{2}$ if we have $q^{\frac{n}{2}-2}>T$ or
$q^{n}>T^{\frac{2n}{n-4}}$. But $n\geq 6$ implies $\frac{2n}{n-4}\leq 6$.
Therefore, whenever $q^{n}>T^{6}$ or $q^{n}>5.00187\times 10^{370}$ then
$(q,n)\in\mathcal{S}_{2}$. Hence, $\omega(q^{n}-1)\geq 154$ gives
$(q,n)\in\mathcal{S}_{2}$. Iterating the process (of Proposition 4.4) for the
values in Table 2, we get that $(q,n)\in\mathcal{S}_{2}$, if we have
$q^{\frac{n}{2}-2}>2.7829\times 10^{10}$. This determines the cases
$n=6,q>2.7829\times 10^{10}$; $n=7,q>(2.7829\times 10^{10})^{{2}/{3}}$ and
$n=8,q>(2.7829\times 10^{10})^{1/2}$. Thus, the only possible exceptions are
$(3,6),(3^{2},6),\ldots,(3^{21},6)$; $(3,7),(3^{2},7),\ldots,(3^{14},7)$ and
$(3,8),(3^{2},8),\ldots,(3^{10},8)$. For these pairs, first we verify the
inequality (11) and then for the remaining pairs, choose $e,g$ as mentioned in
the Table 3 and verify (13). Hence, only possible exceptions are
$(3,6),(3^{2},6),(3^{3},6),(3,7),(3,8)~{}\text{and}~{}(3^{2},8)$.

Table 2. Values of $W(e)$, $\delta$ and $\Delta$ such that Proposition 4.4 holds $Sr.no$ | $c\leq\omega(q^{n}-1)\leq d$ | $W(e)$ | $\delta>$ | $\Delta<$ | $2\Delta W(e)^{2}W(g)<$
---|---|---|---|---|---
$1$ | $a=17,b=153$ | $2^{17}$ | $0.0304555$ | $8900.2013271$ | $7.8287\times 10^{16}$
$2$ | $a=9,b=54$ | $2^{9}$ | $0.03063362$ | $2907.3044905$ | $3.9022\times 10^{11}$
$3$ | $a=8,b=40$ | $2^{8}$ | $0.0761466$ | $829.3503968$ | $2.7829\times 10^{10}$

The above discussions leads us to conclude the following.

######  Theorem 5.7.

Let $q,k,n\in\mathbb{N}$ such that $q=3^{k}$ and $n\geq 6$. The
$(q,n)\in\mathcal{S}_{2}$ unless the following possible exceptions:

  * 1.

$q=3,3^{2},3^{3}~{}\text{and}~{}n=6$;

  * 2.

$q=3,3^{2}~{}\text{and}~{}n=8$;

  * 3.

$q=3~{}\text{and}~{}n=7,9,10,12,16$.

## References

  * [1] Sharma, A. K., Rani, M., Tiwari, S. K. (2022). Primitive normal pairs with prescribed norm and trace. Finite Fields and Their Applications, 78, 101976.
  * [2] Lemos, A., Neumann, V. G., Ribas, S. (2023). On arithmetic progressions in finite fields. Designs, Codes and Cryptography, 91(6), 2323-2346.
  * [3] Wan, D. (1997). Generators and irreducible polynomials over finite fields. Mathematics of Computation, 66(219), 1195-1212.
  * [4] Agnew, G. B., Mullin, R. C., Onyszchuk, I. M., Vanstone, S. A. (1991). An implementation for a fast public-key cryptosystem. Journal of CRYPTOLOGY, 3, 63-79.
  * [5] Kapetanakis, G. (2014). Normal bases and primitive elements over finite fields. Finite Fields and Their Applications, 26, 123-143.
  * [6] Sharma, H., Sharma, R. K. (2021). Existence of primitive pairs with prescribed traces over finite fields. Communications in Algebra, 49(4), 1773-1780.
  * [7] Lenstra, H. W., Schoof, R. J. (1987). Primitive normal bases for finite fields. Mathematics of Computation, 48(177), 217-231.
  * [8] Fu, L., Wan, D. (2014). A class of incomplete character sums. The Quarterly Journal of Mathematics, 65(4), 1195–1211.
  * [9] Rani, M., Sharma, A. K., Tiwari, S. K., Gupta, I. (2022). On the existence of pairs of primitive normal elements over finite fields. São Paulo Journal of Mathematical Sciences, 16(2), 1032-1049.
  * [10] Lidl, R., Niederreiter, H. (1997). Finite fields (No. 20). Cambridge university press.
  * [11] Cohen, S. D., Gupta, A. (2021). Primitive element pairs with a prescribed trace in the quartic extension of a finite field. Journal of Algebra and Its Applications, 20(09), 2150168.
  * [12] Cohen, S. D., Huczynska, S. (2010). The strong primitive normal basis theorem. Acta Arithmetica, 143(4), 299–332.
  * [13] Cohen, S. D. (1985). Consecutive primitive roots in a finite field. Proceedings of the American Mathematical Society, 93(2), 189-197.
  * [14] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.1), (2020) https://www.sagemath.org.
  * [15] Chou, W. S., Cohen, S. D. (2001). Primitive elements with zero traces. Finite Fields and Their Applications, 7(1), 125-141.
  * [16] Paar, C., Pelzl, J., Paar, C., Pelzl, J. (2010). Public-key cryptosystems based on the discrete logarithm problem. Understanding Cryptography: A Textbook for Students and Practitioners, 205-238.
  * [17] Sharma, R. K. (2017). Existence of some special primitive normal elements over finite fields. Finite Fields and Their Applications, 46, 280-303.
  * [18] Sharma, R. K., Awasthi, A., Gupta, A. (2018). Existence of pair of primitive elements over finite fields of characteristic 2. Journal of Number Theory, 193, 386-394.
  * [19] Sharma, A. K., Rani, M., Tiwari, S. K. (2023). Primitive normal values of rational functions over finite fields. Journal of Algebra and Its Applications, 22(07), 2350152.
  * [20] Hazarika, H., Basnet, D. K., Kapetanakis, G. (2022). On the existence of primitive normal elements of rational form over finite fields of even characteristic. International Journal of Algebra and Computation, 32(02), 357-382.
  * [21] Cohen, S. D., Hachenberger, D. (2000). Primitivity, freeness, norm and trace. Discrete Mathematics, 214(1-3), 135-144.
  * [22] Sharma, H., Sharma, R. K. (2021). Existence of primitive normal pairs with one prescribed trace over finite fields. Designs, Codes and Cryptography, 89, 2841-2855.

Table 3. Pairs $(q,n)\in\mathcal{S}_{2}(6\leq n\leq 8)$ by Sieve Technique $Sr.no$ | $(q,n)$ | $e$ | $g$ | $\delta$ | $\Delta$ |
---|---|---|---|---|---|---
$1$ | $(3^{4},6)$ | $1$ | $1$ | $0.459261859983295$ | $25.9514772691991$ |
$2$ | $(3^{5},6)$ | $1$ | $x+2$ | $0.447087519356890$ | $31.0770809677259$ |
$3$ | $(3^{6},6)$ | $1$ | $x+2$ | $0.407896267111061$ | $33.8708481743972$ |
$4$ | $(3^{7},6)$ | $1$ | $x+2$ | $0.508470251621857$ | $27.5668841166895$ |
$5$ | $(3^{8},6)$ | $1$ | $x+2$ | $0.377733579667098$ | $52.3000024957934$ |
$6$ | $(3^{9},6)$ | $1$ | $x+2$ | $0.531452453574178$ | $33.9878097949682$ |
$7$ | $(3^{10},6)$ | $1$ | $x+2$ | $0.0589802048533907$ | $324.141980470041$ |
$8$ | $(3^{11},6)$ | $1$ | $x+2$ | $0.527461761956088$ | $30.4380804105545$ |
$9$ | $(3^{12},6)$ | $1$ | $x+2$ | $0.788944166092470$ | $21.0127522892943$ |
$10$ | $(3^{13},6)$ | $1$ | $x+2$ | $0.514520279376933$ | $42.8147177899972$ |
$11$ | $(3^{14},6)$ | $1$ | $x+2$ | $0.0158565410261152$ | $1452.50550193259$ |
$12$ | $(3^{15},6)$ | $1$ | $x+2$ | $0.435349772783422$ | $59.4250902674457$ |
$13$ | $(3^{16},6)$ | $1$ | $x+1$ | $0.506021983577781$ | $43.5001732761123$ |
$14$ | $(3^{17},6)$ | $1$ | $x+1$ | $0.529063818388427$ | $41.6927540121110$ |
$15$ | $(3^{18},6)$ | $1$ | $x+1$ | $0.549184527812597$ | $36.5967503412324$ |
$16$ | $(3^{19},6)$ | $1$ | $x+1$ | $0.550290107689489$ | $40.1616890919101$ |
$17$ | $(3^{20},6)$ | $1$ | $x+1$ | $0.403312899984737$ | $68.9455403013932$ |
$18$ | $(3^{21},6)$ | $1$ | $x+1$ | $0.482470736843123$ | $53.8166141299650$ |
$19$ | $(3^{2},7)$ | $1$ | $1$ | $0.880659271367610$ | $8.81307765111286$ |
$20$ | $(3^{3},7)$ | $1$ | $x+2$ | $0.994049514027501$ | $8.03591663728131$ |
$21$ | $(3^{4},7)$ | $1$ | $x+2$ | $0.925423322543100$ | $11.7252789947714$ |
$22$ | $(3^{5},7)$ | $1$ | $x+2$ | $0.970001158998250$ | $8.18555961953322$ |
$23$ | $(3^{6},7)$ | $1$ | $x+2$ | $0.938884907082541$ | $17.9763991164907$ |
$24$ | $(3^{7},7)$ | $1$ | $x+2$ | $0.995131839337739$ | $12.0489197558537$ |
$25$ | $(3^{8},7)$ | $1$ | $x+2$ | $0.925419354656423$ | $16.0476854461580$ |
$26$ | $(3^{9},7)$ | $1$ | $x+2$ | $0.998164732621425$ | $10.0147091342228$ |
$27$ | $(3^{10},7)$ | $1$ | $x+2$ | $0.966344851863111$ | $13.3830999138579$ |
$28$ | $(3^{11},7)$ | $1$ | $x+2$ | $0.998170134660812$ | $10.0146657590777$ |
$29$ | $(3^{12},7)$ | $1$ | $x+2$ | $0.877317235655992$ | $28.2162864984664$ |
$30$ | $(3^{13},7)$ | $1$ | $x+2$ | $0.998170173334930$ | $8.01099908641203$ |
$31$ | $(3^{14},7)$ | $1$ | $x+2$ | $0.995131836990084$ | $17.0733796693407$ |
$32$ | $(3^{3},8)$ | $1$ | $x+2$ | $0.196647108479655$ | $68.1082692774249$ |
$33$ | $(3^{4},8)$ | $1$ | $x+2$ | $0.736789913062364$ | $21.0013459085114$ |
$34$ | $(3^{5},8)$ | $1$ | $x+2$ | $0.512573068211997$ | $27.3622377105137$ |
$35$ | $(3^{6},8)$ | $1$ | $x+2$ | $0.359216168215832$ | $68.8121374358067$ |
$36$ | $(3^{7},8)$ | $1$ | $x+1$ | $0.478010818428838$ | $37.5640486461727$ |
$37$ | $(3^{8},8)$ | $1$ | $x+1$ | $0.870923243421729$ | $18.0748953547227$ |
$38$ | $(3^{9},8)$ | $1$ | $x+1$ | $0.0784275783761321$ | $269.762953221452$ |
$39$ | $(3^{10},8)$ | $1$ | $x+1$ | $0.421258807060023$ | $54.2244274334312$ |
Table 4. Pairs $(q,n)\in\mathcal{S}_{2}(n\geq 9)$ by Sieve Technique $Sr.no$ | $(q,n)$ | $e$ | $g$ | $\delta$ | $\Delta$ |
---|---|---|---|---|---|---
$1$ | $(3^{2},9)$ | $1$ | $x+2$ | $0.287369229453635$ | $36.7984369064588$ |
$2$ | $(3^{4},9)$ | $1$ | $x+2$ | $0.358733632763241$ | $41.0261707333134$ |
$3$ | $(3^{2},10)$ | $1$ | $x+2$ | $0.223207625673814$ | $55.7616040839764$ |
$4$ | $(3^{3},10)$ | $1$ | $x+1$ | $0.390305143669876$ | $37.8693709961489$ |
$5$ | $(3^{4},10)$ | $1$ | $x+1$ | $0.623809806883578$ | $30.8549487381806$ |
$6$ | $(3,11)$ | $1$ | $1$ | $0.570960346628126$ | $12.5086106862477$ |
$7$ | $(3^{2},11)$ | $1$ | $x+2$ | $0.879613797583913$ | $12.2317631041269$ |
$8$ | $(3^{2},12)$ | $5$ | $x+2$ | $0.0395087735635420$ | $331.040838969402$ |
$9$ | $(3,13)$ | $1$ | $x+2$ | $0.851849342948381$ | $7.86958250468825$ |
$10$ | $(3^{3},13)$ | $1$ | $x+2$ | $0.548585326900787$ | $36.6345391834299$ |
$11$ | $(3,14)$ | $1$ | $x^{2}+2$ | $0.991770382478721$ | $7.04148953057416$ |
$12$ | $(3^{2},14)$ | $1$ | $x+2$ | $0.408829006334904$ | $36.2441455549059$ |
$13$ | $(3,15)$ | $1$ | $x+2$ | $0.318218151661110$ | $23.9974880862696$ |
$14$ | $(3^{2},15)$ | $1$ | $x+2$ | $0.137697321077803$ | $118.196886582561$ |
$15$ | $(3^{2},16)$ | $5$ | $x^{2}+2$ | $0.107160283432735$ | $160.640864464221$ |
$16$ | $(3,18)$ | $1$ | $x+1$ | $0.0651470072314125$ | $155.498992892773$ |
$17$ | $(3,20)$ | $5$ | $x^{4}+2$ | $0.734318736784925$ | $14.2562581467072$ |
$18$ | $(3,22)$ | $23$ | $x^{2}+2$ | $0.950143284148867$ | $11.4722555536054$ |
$19$ | $(3,24)$ | $1435$ | $x+1$ | $0.151781324860484$ | $61.2958323975149$ |


# Speeding up charge exchange recombination spectroscopy analysis in support
of NERSC/DIII-D realtime workflow ††thanks: Citation: arXiv:2309.08687

Aarushi Jain
University of Texas- Arlington
Arlington, Texas
<EMAIL_ADDRESS>
Laurie Stephey
Lawrence Berkeley National Lab
Berkeley, California
<EMAIL_ADDRESS>
0000-0003-3868-6178
Erik Linsenmayer
General Atomics
San Diego, California
<EMAIL_ADDRESS>
Colin Chrystal
General Atomics
San Diego, California
<EMAIL_ADDRESS>
0000-0003-3049-8658
Jonathan Dursi
NVIDIA
<EMAIL_ADDRESS>
Hannah Ross
Lawrence Berkeley National Lab
Berkeley, California
<EMAIL_ADDRESS>
###### Abstract

We report optimization work made in support of the development of a realtime
Superfacility workflow between DIII-D and NERSC. At DIII-D, the ion properties
measured by charge exchange recombination (CER) spectroscopy are required
inputs for a Superfacility realtime workflow that computes the full plasma
kinetic equilibrium. In this workflow, minutes matter since the results must
be ready during the brief 10-15 minute pause between plasma discharges. Prior
to this work, a sample CERFIT analysis took approximately 15 minutes. Because
the problem consists of many calculations that can be done independently, we
were able to restructure the CERFIT code to leverage this parallelism with
Slurm job arrays. We reduced the runtime to approximately 51 seconds- a
speedup of roughly 20x, saving valuable time for both the scientists
interested in the CER results and also for the larger equilibrium
reconstruction workflow.

_Keywords_ HPC $\cdot$ Optimization $\cdot$ Realtime $\cdot$ Superfacility
$\cdot$ Parallelism $\cdot$ Slurm Job Arrays $\cdot$ NERSC $\cdot$ Fusion
$\cdot$ Plasma $\cdot$ DIII-D $\cdot$ Charge Exchange

##  1 Introduction

DIII-D is currently the largest operating magnetic confinement fusion
experiment in the United States. It operates over campaigns several months
long, with 30-40 plasma discharges per experimental runday, with experimental
discharges occurring approximately every 15 minutes. DIII-D has over 50
diagnostics [1], many of which require moderate to substantial computational
resources to convert from raw signals to usable physical measurement
quantities. [2]

The major goal of the DIII-D/NERSC Superfacility effort [3, 4] is to optimize
an equilibrium reconstruction workflow at NERSC so that the walltime is fast
enough to enable between-discharge analysis. This Superfacility work builds on
previous efforts to couple magnetic confinement fusion experiments with
realtime HPC resources [5, 6]. CAKE is Consistent Automatic Kinetic
Equilibrium [7]\- it is a module within the larger OMFIT framework [8]. The
ion properties measured by the CER (charge exchange recombination
spectroscopy) diagnostic are required inputs for the CAKE workflow, so the
reconstruction portion of CAKE cannot start running until CERFIT, the analysis
suite for the CER diagnostic, completes.

CAKE provides fully kinetic plasma equilibrium reconstructions, yielding a
higher accuracy magnetic topology of the plasma. Although the plasma topology
is important to both operators and researchers, it is computationally
expensive to obtain and the current CAKE walltime is too long to be run
between discharges. As a result, CAKE is often run after the experimental
runday has completed; at this time any insights about plasma equilibrium are
no longer actionable.

The DIII-D CER diagnostic system (see [9] and the references therein) is
comprised of approximately 76 channels, each of which has a different viewing
position, or chord, into the DIII-D vacuum vessel. A diagram of the CER system
is shown in Figure 1. Visible light from these chords is analyzed by
spectrometers, and particular spectral lines emitted by the plasma are used to
determine ion velocity, temperature, and density via the measured Doppler
shift, Doppler broadening, and radiance. These quantities are derived from
fits to the spectra, and the code used to perform these fits is called CERFIT
[10, 9]. For standard analysis, CERFIT processes 64 chords.

The duration of a typical DIII-D discharge is between 4 and 10 seconds, and
the CER system normally acquires data at 200 Hz. While any one spectral fit is
not computationally difficult, complete analysis for a typical discharge
requires more than 10,000 fits, and executing the highest quality automatic
version of these fits in series previously required approximately 15 minutes
running on a node of the DIII-D Omega cluster (node details are discussed in
detail in Section 2). Since information from a previous discharge is needed as
quickly as possible to inform the setup of the next discharge, automatic CER
fits done between discharges are less complex (and correspondingly less
accurate) and take approximately 4 minutes to complete. For this work, the
goal was to speed up the highest quality fitting (which is required for CAKE)
by at least a factor of 10 so that those results could be used between
discharges and also be inputs to further computations that also aim to
complete significantly before the next discharge.

Figure 1: A diagram of the DIII-D Charge Exchange Recombination Spectroscopy
diagnostic system (CER). There are approximately 76 total channels in the
system; vertical viewing channels (chords) are shown in blue, and tangential
viewing channels (chords) are shown in red. 64 chords are analyzed in standard
CERFIT processing [9].

##  2 Experimental setup

We performed this study using the local DIII-D cluster, Omega. Owing to its
nature as a data-analysis code, CERFIT is substantially less portable than a
simulation code. CERFIT has complex dependencies that are not easily satisfied
on NERSC systems. One of these dependencies is a custom DIII-D data access
library PTDATA [11], which to our knowledge has not yet been installed on a
system outside of DIII-D. In addition to the PTDATA library, the DIII-D raw
data itself much also be accessible as an input to CERFIT, including the
timing and profile of neutral beams, which requires access to the DIII-D data
system. CERFIT has several sub-modules which are tracked via a set of
environment variables, which in turn can be set by custom system modules. The
CERFIT test suite requires known-good datasets in an expected directory
structure. All of these factors make it a challenge to move CERFIT to another
system; however, we would like to study the feasibility of running this
workflow at NERSC to leverage the additional computational resources available
on Perlmutter as future work [12].

The Omega cluster is a heterogeneous Linux cluster situated at DIII-D. It
contains two login nodes with 2x Intel Xeon Gold 6252 CPUs and 34 total
compute nodes including: 2 nodes of 2x Intel Xeon Gold 6252 CPUs, each with 1
NVIDIA V100, 1 node of 2x Intel Xeon Gold 6252, 2 nodes of 2x Intel Xeon
Platinum 8260, 16 nodes of 2x AMD EPYC 7513, 12 nodes of 2X AMD EPYC 7502, and
1 node of 2x AMD EPYC 7343. Job submission is managed by the Slurm scheduler.
For queue permission reasons, we have targeted the two Intel Xeon Gold 6252
CPUs nodes during our study, as the CERFIT code currently must be compiled and
run on Intel nodes due to an apparent outstanding nvfortran compiler issue on
AMD nodes. Work is ongoing to address this nvfortran issue. To work around
this, the CER team is actively switching to the gfortran compiler. Early
results have shown that there are no issues using the AMD hardware with
gfortran.

##  3 Determining Optimization Strategy

FITCER, the outer wrapper for CERFIT, performs complete CERFIT analysis of all
CER chord data from a discharge. The CERFIT analysis code is comprised both of
Fortran and C code- the main analysis algorithms are written in Fortran, and
the main data access components are written in C. CERFIT performs spectral
fitting by adding Gaussian functions to produce a synthetic spectra (Sum of
Gauss), and then using the Levenberg-Marquardt minimization algorithm, CERFIT
iteratively fine-tunes the model to minimize the $\chi^{2}$ value of the fit,
ultimately obtaining the best fit ion properties based on the fit line’s
location, width, and amplitude (Chi-squared minimization). There are several
additional data acquisition and pre-processing steps.

We began this optimization study with application profiling. Understanding the
structure of the CERFIT application and where the time was spent was crucial
to identifying a strategy to achieve speedup. We used the NVIDIA Nsight system
profiler nsys for our CPU code since that was available on the system. We
profiled the application running on a single process/single CPU since that was
how CERFIT was typically run. Our main interest was how much speedup can be
practically achieved for the team given the conditions under which they
typically run.

Figure 2: NVIDIA nsys profiling results illustrating the runtime distribution
of the CERFIT code in “Bottom-up view”. Note that nsys is displaying the
symbol names rather than the function names. The Chi-squared minimization,
symbol holger_eval_model, occupies approximately 16% of the total runtime,
while the Sum of Gauss operations, symbol sum_of_gauss_model_csigma, used for
preparing synthetic spectra, accounts for around 10%. The absence of a single
hotspot suggests that GPU porting of these algorithms may not yield
significant overall speedup without a major redesign of the CERFIT code.

Sample NVIDIA nsys profiling data are shown in Figure 2. Displaying the nsys
profiling data in “Bottom-up” view [13] provided useful information for our
CPU-only application. It provided information about the structure of the
application and the major hotspots in the code. The Chi-squared minimization,
symbol holger_eval_model, took about 16 percent of total runtime, and the Sum
of Gauss function, symbol sum_of_gauss_model_csigma, that constructed
synthetic spectra for fitting took about 10 percent of total runtime. Many
individual functions performing adjacent tasks accounted for the remainder of
the application runtime, which we believe is a result of application
branching.

These profiling data indicated that no single function was doing a lot of the
heavy lifting in CERFIT. In a best-case scenario in which we ported both Chi-
squared minimization and Sum of Gauss to GPU and achieved speedup, we would
still be speeding up only about a quarter of the application runtime. Although
our initial goal in this study was to try to adapt CERFIT to leverage GPUs,
the profiling data made it clear that CERFIT in its present state was not a
good candidate for GPU optimization.

Recognizing the limited potential from GPU porting, we redirected our focus
towards obtaining CPU speedup through adding parallelism. Both from
discussions with the CER team and from our profiling data, we were aware that
CERFIT was performing fully independent calculations for each CER chord and
could be reconfigured to run in an embarrassingly parallel manner. The
independent nature of the calculations made the algorithm an excellent
candidate for parallelization, so we decided to pursue this approach.

##  4 Implementing chord-level CPU parallelism

Given the complex nature of the CERFIT code (see Section 3), which involves
multiple branching points, our goal was to validate our understanding of
chord-level parallelism. We first needed to locate the right place in the code
where the chord-splitting takes place. Once located, as a test, we used the
Linux utility xargs to divide the CERFIT input file in two pieces and launch
two independent CERFIT jobs, each running on a subset of the input file. We
observed that CERFIT ran as expected in this mode of operation and determined
it was safe to move forward with this strategy depicted in Figure 3.

Figure 3: Illustration of serial and parallel execution of CERFIT. In the
serial execution, a single input file contains data for all chords, and CERFIT
processes each chord sequentially. In contrast, the parallel execution divides
the input data into separate files, one for each chord. Multiple instances of
CERFIT run in parallel in this embarrassingly parallel model.

To obtain results quickly, we began by writing a prototype Python script to
break the CERFIT input file into 64 individual input files- one for each
viewing chord. This prototype script enabled us to explore large-scale
parallelization via Slurm job arrays. Slurm job arrays [14] are a feature in
the Slurm workload manager that enables many similar jobs to be launched from
a single batch script. We decided to start with Slurm job arrays instead of a
solution like MPI largely due to the lower barrier to entry and faster path to
implementation. Incorporating MPI into CERFIT, a complex C and Fortran code,
would likely be time-consuming and can be considered for future work. One
benefit of relying on Slurm to provide parallelism is that the distribution of
work is extremely flexible and the size of the job can be quickly adjusted
(i.e. using one node instead of two). This is one major advantage compared to
a similar MPI implementation.

To enable FITCER to launch its own Slurm jobs, we wrote a Slurm job array
script designed to launch 64 nearly identical CERFIT jobs, one for each CER
chord. The variable SLURM_ARRAY_TASK_ID was used to access the corresponding
CERFIT chord input file. The script launched one job per physical CPU core
with 24 total jobs per node. Additionally, it was necessary to allocate the
memory per CPU correctly so that the resources requested for each job would
not exceed the total resources on the node and cause the jobs to block. With
this configuration, we observed that our jobs ran in parallel as expected. Our
Slurm job array batch script is shown below:

    #!/bin/bash
    #SBATCH -p gpus
    #SBATCH --array=1-64
    #SBATCH --cpus-per-task=1
    #SBATCH -n 1
    #SBATCH --ntasks-per-node=24
    #SBATCH --mem-per-cpu=1G

    srun time cerfit < chord $SLURM_ARRAY_TASK_ID.in \
    >& fit_$SLURM_ARRAY_TASK_ID.out

Once we confirmed that this new chord-parallel structure was suitable, our
objective was to implement our changes back into the production version of
FITCER, with the goal of making the parallel version of the code look and feel
like the original version. The key feature was to re-implement the chord-
splitting function that had been tested via a Python script into FITCER in
Fortran. A specialized Fortran subroutine was developed to effectively
partition individual chords from the primary input file called
fit_<chord_number>.in. One challenge in translating from a Python prototype to
a Fortran subroutine is that handling multi-file I/O requires more care and
certainly more lines of code. Another challenge was handling the splitting in
a robust manner. During the process, we observed that the structure of the
CERFIT input file differs between production runs and running within the test
suite. As a result, this meant that we needed to split the file on a certain
word rather than after a certain number of lines. This resulting subroutine
seamlessly integrates within the existing fitcer_input_file.f90 code.

##  5 CER Regression Testing

Verifying that our modifications to CERFIT did not meaningfully alter the
outputs of the code was essential. We used the established CERTEST test script
developed at DIII-D to check for correctness of our CERFIT outputs.

CERTEST can be run in two modes- in the first mode, it generates a set of
known-good reference files stored in a bespoke directory. In test mode,
CERTEST runs CERFIT and generates standard output files, which are then
compared to the reference files. We generated the reference files using the
original serial code, and we generated the test files using our parallel
version of CERFIT. CERTEST needed some modifications to be able to handle the
paradigm in which output files are written from Slurm jobs. Once we ran the
updated CERTEST, the CER team determined that the differences that were
present between the two versions were negligible.

##  6 Results

In this section we discuss the measurements to assess the overall improvements
in runtime from our implementation of chord-level parallelism via Slurm job
arrays.

We used the following procedure to perform our benchmarking on the Omega
cluster and achieve our speedup results shown in Figure 4:

  1. 1.

We ran CERFIT via FITCER using a standard sample discharge 163100 for
analysis. This run was performed on an Omega Intel Xeon Gold 6252 CPU login
node since this is the standard procedure for the CER team. We ran 3 trials of
the original serial implementation, shown in blue, using the Linux time
command to obtain the measurement. The mean runtime of these 3 trials was 1010
seconds.

  2. 2.

We ran our parallelized version of FITCER using the same standard sample
discharge. For this benchmark we ran on two Omega Intel Xeon Gold 6252 compute
nodes, each with 24 physical cores, for a total of 48 physical cores. We ran 3
trials of the parallel implementation, shown in orange, using a special bash
wrapper script to obtain the full FITCER runtime. It was not adequate to time
FITCER using Linux time since FITCER currently finishes executing as soon as
the job array is submitted via SBATCH. In the wrapper script, we included a
while loop to query Slurm every 2 seconds to determine if the job array jobs
were still running. When the query returned no results, the timer ended and
the runtime duration was calculated. Future work could include adding such
timing capabilities into FITCER itself. The mean runtime of these 3 trials was
51 seconds. Dividing the original 1016 seconds by 51 seconds, we arrive at a
speedup of 19.9, or approximately 20x.

Figure 4: Benchmarking results of sequential vs. parallel CERFIT Execution.
This plot presents a comparison of execution times for 3 trials of each case.
Sequential execution of FITCER, indicated by the blue bars, completes in
approximately 15 minutes. In contrast, parallel execution, indicated by the
orange bars, completes in approximately 50 seconds. On average, the parallel
version yields a 20x speedup relative to the sequential version.

We performed a separate study to examine the individual chord processing
times. The execution times for each chord are shown in Figure 5. We ran 3
trials of this CERFIT per-chord test and found that some chords are
consistently processed more quickly than others. Given this behavior, using a
flexible framework like Slurm job arrays affords some load-balancing by
allowing any cores that many have finished early the opportunity to process
another channel.

It is additionally useful to discuss the speedup in terms of a per-core
analysis. The initial benchmark (roughly 1016 seconds) was run in serial on a
single core. The final benchmark (roughly 51 seconds) was run on 48 physical
cores. With perfect strong scaling one might expect a 48x speedup (roughly 19
seconds)- what accounts for this difference? First, there are 64 total chords
being processed, so 16 CPUs processed more than one chord, which reduces the
potential strong-scaling speedup. Next, Figure 5 demonstrates that the time to
process each chord varies from a few seconds to nearly 30 seconds. In an ideal
situation, a CPU that finishes early with an “fast” chord would be available
to process another chord. Using Slurm Job Arrays does inherently provide some
load balancing in this regard, although it is not optimized. Finally, there is
some overhead of submitting each CERFIT task as a Slurm job. We should note
that the target CPU compute nodes were unoccupied, so we expect that there is
some overhead to submit and start the job, but there was no queue wait-time
(except from the application itself). If the test could have been performed on
3 nodes with more than 64 available CPU cores, we might expect to achieve
closer to the ideal strong-scaling speedup, although the speedup will be
determined by the “long pole in the tent”, which in this case is the chord
that takes approximately 30 seconds to be processed. Since there is so much
variation in the per-chord processing time, achieving the ideal strong-scaling
speedup of 19s is not possible with this application.

Figure 5: Examination of the individual chord runtimes in CERFIT. We performed
3 trials of this test. The plot shows chord number vs execution time, with
each trial shown in a different color. We observed that the differences in
processing time between chords is robust.

##  7 Future Work

The work we have reported here is an initial effort towards speeding up the
walltime of CERFIT analysis at DIII-D. However, there are many additional
avenues for this work.

First and foremost, the objective of this work is to develop a production
quality parallel version of CERFIT that the CER and CAKE teams can use in
routine analysis. Work is ongoing to finalize changes, including switching
from nvfortran to gfortran and adjusting the Slurm job array configuration to
fit Omega queue policies, to enable CERFIT to run routinely between discharges
on the AMD compute nodes in the Omega cluster.

One potential next step would be to study replacing the Slurm job array based
parallelism with MPI. This would provide a scheduler-independent framework for
parallelism. It would also be instructive to evaluate the differences in
overhead between starting an independent Slurm job for each chord as compared
to MPI process startup within a single job.

The whole of this work was performed on the Omega cluster at DIII-D. However,
another major area of study would be to try running this analysis on NERSC’s
Perlmutter. This would require some additional libraries (like PTDATA, a
DIII-D internal data system library) to be locally installed at NERSC. It may
also require some examination of the efficiency of external data transfer via
PTDATA. The goal would be to determine if the realtime resources NERSC could
offer would benefit the overall workflow and overcome the additional overheads
of raw data transfer (estimated to be a relatively modest 1 GB per discharge).
Running CERFIT locally at NERSC would mean that the ion physics outputs from
CERFIT would be located at NERSC and could be used directly in CAKE and other
workflows, which could be beneficial. Questions about how to locally store
these data for efficient access and for what duration would need to be
explored.

##  8 Summary

To summarize, this work describes our efforts to achieve 20x speedup for the
high-quality CERFIT CER diagnostic analysis code used at DIII-D which yields
plasma ion properties. This speedup is expected to benefit DIII-D scientists
and operators working with CER results in the control room since it will
provide them this high-quality information substantially faster. We believe
this CERFIT speedup will additionally translate into speedup for the CAKE
Superfacility workflow project that connects DIII-D to NERSC with the goal of
enabling routine between-discharge plasma equilibrium reconstruction.

## Acknowledgments

This research used resources of the National Energy Research Scientific
Computing Center (NERSC), a U.S. Department of Energy Office of Science User
Facility located at Lawrence Berkeley National Laboratory, operated under
Contract No. DE-AC02-05CH11231 using NERSC award ASCR-ERCAP0019913.

This material is based upon work supported by the U.S. Department of Energy,
Office of Science, Office of Fusion Energy Sciences, using the DIII-D National
Fusion Facility, a DOE Office of Science user facility, under Award(s) DE-
FC02-04ER54698.

Disclaimer: This report was prepared as an account of work sponsored by an
agency of the United States Government. Neither the United States Government
nor any agency thereof, nor any of their employees, makes any warranty,
express or implied, or assumes any legal liability or responsibility for the
accuracy, completeness, or usefulness of any information, apparatus, product,
or process disclosed, or represents that its use would not infringe privately
owned rights. Reference herein to any specific commercial product, process, or
service by trade name, trademark, manufacturer, or otherwise does not
necessarily constitute or imply its endorsement, recommendation, or favoring
by the United States Government or any agency thereof. The views and opinions
of authors expressed herein do not necessarily state or reflect those of the
United States Government or any agency thereof.

This work was completed in part at the July 2023 NERSC Open Hackathon, part of
the Open Hackathons program. The authors would like to acknowledge OpenACC-
Standard.org for their support.

The authors would like to thank David Schissel and 3 anonymous reviewers from
the SC23 XLOOP workshop for their suggestions to improve this paper.

Finally, the authors would like to thank the CAKE Superfacility team for
useful discussions that contributed to this work.

## References

  * noa [2023a] DIII-D research program, August 2023a.  URL https://fusion.gat.com/global/diii-d/home.
  * noa [2023b] DIII-D National Fusion Facility, August 2023b.  URL https://www.ga.com/magnetic-fusion/diii-d.
  * Smith et al. [2023] Sterling Smith, Emily Belli, Orso Meneghini, Reuben Budiardja, David Schissel, Jeff Candy, Tom Neiser, and Adam Eubanks.  A Vision for Coupling Operation of US Fusion Facilities with HPC Systems and the Implications for Workflows and Data Management.  pages 87–100. Springer, 2023.  URL https://doi.org/10.1007/978-3-031-23606-8_6.
  * Bard et al. [2022] Deborah Bard, Cory Snavely, Lisa Gerhardt, Jason Lee, Becci Totzke, Katie Antypas, William Arndt, Johannes Blaschke, Suren Byna, Ravi Cheema, Shreyas Cholia, Mark Day, Bjoern Enders, Aditi Gaur, Annette Greiner, Taylor Groves, Mariam Kiran, Quincey Koziol, Tom Lehman, Kelly Rowland, Chris Samuel, Ashwin Selvarajan, Alex Sim, David Skinner, Laurie Stephey, Rollin Thomas, and Gabor Torok.  The LBNL Superfacility Project Report, 2022, 2206.11992.  URL https://doi.org/10.48550/arXiv.2206.11992.
  * Kostuk et al. [2018] M. Kostuk, T. D. Uram, T. Evans, D. M. Orlov, M. E. Papka, and D. Schissel.  Automatic Between-Pulse Analysis of DIII-D Experimental Data Performed Remotely on a Supercomputer at Argonne Leadership Computing Facility.  Fusion Science and Technology, 74(1-2):135–143, August 2018.  ISSN 1536-1055.  URL https://doi.org/10.1080/15361055.2017.1390388.  Publisher: Taylor & Francis.
  * Kube et al. [2022] R Kube, R M Churchill, C S Chang, J Choi, R Wang, S Klasky, L Stephey, E Dart, and M J Choi.  Near real-time streaming analysis of big fusion data.  Plasma Physics and Controlled Fusion, 64(3):035015, February 2022.  ISSN 0741-3335.  URL http://dx.doi.org/10.1088/1361-6587/ac3f42.  Publisher: IOP Publishing.
  * Xing et al. [2021] Z.A. Xing, D. Eldon, A.O. Nelson, M.A. Roelofs, W.J. Eggert, O. Izacard, A.S. Glasser, N.C. Logan, O. Meneghini, S.P. Smith, R. Nazikian, and E. Kolemen.  CAKE: Consistent Automatic Kinetic Equilibrium reconstruction.  Fusion Engineering and Design, 163:112163, February 2021.  ISSN 0920-3796.  URL https://doi.org/10.101/j.fusengdes.2020.112163.
  * Meneghini et al. [2015] O. Meneghini, S.P. Smith, L.L. Lao, O. Izacard, Q. Ren, J.M. Park, J. Candy, Z. Wang, C.J. Luna, V.A. Izzo, B.A. Grierson, P.B. Snyder, C. Holland, J. Penna, G. Lu, P. Raum, A. McCubbin, D.M. Orlov, E.A. Belli, N.M. Ferraro, R. Prater, T.H. Osborne, A.D. Turnbull, G.M. Staebler, and The AToM Team.  Integrated modeling applications for tokamak experiments with OMFIT.  Nuclear Fusion, 55(8):083008, July 2015.  ISSN 0029-5515.  URL https://dx.doi.org/10.1088/0029-5515/55/8/083008.  Publisher: IOP Publishing.
  * Chrystal et al. [2016] C. Chrystal, K. H. Burrell, B. A. Grierson, S. R. Haskey, R. J. Groebner, D. H. Kaplan, and A. Briesemeister.  Improved edge charge exchange recombination spectroscopy in DIII-D.  Review of Scientific Instruments, 87(11):11E512, August 2016.  ISSN 0034-6748.  URL https://doi.org/10.1063/1.4958915.
  * Seraydarian and Burrell [1986] Raymond P. Seraydarian and Keith H. Burrell.  Multichordal charge-exchange recombination spectroscopy on the DIII-D tokamak.  Review of Scientific Instruments, 57(8):2012–2014, August 1986.  ISSN 0034-6748.  URL https://doi.org/10.1063/1.1138774.
  * McHarg Jr et al. [2002] BB McHarg Jr, JR Burruss, J Freeman, CT Parker, J Schachter, and DP Schissel.  DIII-D data management.  Fusion engineering and design, 60(3):305–309, 2002.  ISSN 0920-3796.  URL https://doi.org/10.1016/S0920-3796(02)00025-X.  Publisher: Elsevier.
  * NER [2023] NERSC Perlmutter, August 2023.  URL https://docs.nersc.gov/systems/perlmutter/.
  * nsy [2023] NVIDIA nsys Function Table Modes, August 2023.  URL https://docs.nvidia.com/nsight-systems/2020.3/additional-info/index.html#function-table-modes.
  * slu [2023] Slurm Job Array Support, August 2023.  URL https://slurm.schedmd.com/job_array.html.