# A primitive normal pair with prescribed prenorm

Kaustav Chatterjee∗ and Shailesh Kumar Tiwari  Department of Mathematics,
Indian Institute of Technology Patna, BIHAR, INDIA.
<EMAIL_ADDRESS>Department of Mathematics, Indian Institute of
Technology Patna, BIHAR, INDIA<EMAIL_ADDRESS>
###### Abstract.

For any positive integers $q$, $n$, $m$ with $q$ being a prime power and
$n\geq 5$, we establish a condition sufficient to ensure the existence of a
primitive normal pair $(\epsilon,f(\epsilon))$ in $\mathbb{F}_{q^{n}}$ over
$\mathbb{F}_{q}$ such that $\mathrm{PN}_{q^{n}/q}(\epsilon)=a$, where
$a\in\mathbb{F}_{q}$ is prescribed. Here
$f={f_{1}}/{f_{2}}\in\mathbb{F}_{q^{n}}(x)$ is a rational function subject to
some minor restrictions such that deg($f_{1}$)+deg($f_{2}$)$=m$ and
$\mathrm{PN}_{q^{n}/q}(\epsilon)=\sum_{i=0}^{n-1}\Bigg{(}\underset{j\neq
i}{\underset{0\leq j\leq n-1}{\prod}}\epsilon^{q^{j}}\Bigg{)}$. Finally, we
conclude that for $m=3$, $n\geq 6$, and $q=7^{k}$ where $k\in\mathbb{N}$, such
a pair will exist certainly for all $(q,n)$ except possibly $10$ choices at
most.

###### Key words and phrases:

Finite field; Characters; Primitive element; Normal element; Trace; Norm

###### 2020 Mathematics Subject Classification:

11T23; 12E20

<EMAIL_ADDRESS>
##  1\. Introduction

Let $\mathbb{F}_{q^{n}}$ represents a finite extension of degree $n$ of the
finite field $\mathbb{F}_{q}$, for some prime power $q$ and positive integer
$n$. There are two group structures associated to $\mathbb{F}_{q^{n}}$, one is
the additive group $\mathbb{F}_{q^{n}}$ and another one is the multiplicative
group $\mathbb{F}_{q^{n}}^{*}$. Additionally, the latter one forms a cyclic
group and any generator of the same is termed as a primitive element of
$\mathbb{F}_{q^{n}}$. Thus, there exist $\phi(q^{n}-1)$ primitive elements in
the finite field $\mathbb{F}_{q^{n}}$, where $\phi$ is the Euler’s totient
function. The least degree monic irreducible polynomial over $\mathbb{F}_{q}$
having a primitive root $\epsilon\in\mathbb{F}_{q^{n}}^{*}$, is referred as
primitive polynomial of the primitive element. For any $\epsilon$
$\in\mathbb{F}_{q^{n}}$, the elements
$\epsilon,\epsilon^{q},\ldots,\epsilon^{q^{n-1}}$ are said to be the
conjugates of $\epsilon$ with respect to $\mathbb{F}_{q}$. Clearly, the set
$\\{\epsilon,\epsilon^{q},\ldots,\epsilon^{q^{n-1}}\\}$ spans a subspace of
$\mathbb{F}_{q^{n}}$ over $\mathbb{F}_{q}$. In particular, for some
$\epsilon\in\mathbb{F}_{q^{n}}$, the set contained with the conjugates of
$\epsilon$ forms a basis of $\mathbb{F}_{q^{n}}$ over $\mathbb{F}_{q}$, then
it is said to be a normal basis, whereas the element is referred as a normal
element. A primitive normal pair
$(\epsilon,\delta)\in\mathbb{F}_{q^{n}}^{*}\times\mathbb{F}_{q^{n}}^{*}$ is
characterized by the property that both $\epsilon$ and $\delta$ are primitive
and normal with respect to the finite field $\mathbb{F}_{q}$. To obtain
further information on primitive normal elements in finite fields, we
recommend [7] to the reader. In this article, first we shall present the
following definition.

######  Definition 1.1.

For any $\epsilon\in\mathbb{F}_{q^{n}}$, the prenorm of $\epsilon$ over
$\mathbb{F}_{q}$ is denoted by $\mathrm{PN}_{q^{n}/q}(\epsilon)$ and is
defined by

$\mathrm{PN}_{q^{n}/q}(\epsilon)=\sum_{i=0}^{n-1}\Bigg{(}\underset{j\neq
i}{\prod_{j=0}^{n-1}}\epsilon^{q^{j}}\Bigg{)}.$

In other words, considering the products of the form
$\epsilon\cdot\epsilon^{q}\ldots\epsilon^{q^{j-1}}\cdot\epsilon^{q^{j+1}}\ldots\epsilon^{q^{n-1}}(0\leq
j\leq n-1)$ and then summing up these products, we get the prenorm of
$\epsilon$ over $\mathbb{F}_{q}$.

Let $\Upsilon(x)=x^{n}+a_{n-1}x^{n-1}+\ldots+a_{1}x+a_{0}\in\mathbb{F}_{q}[x]$
be the minimum polynomial of $\epsilon$. Further, the roots of $\Upsilon$ are
$\epsilon,\epsilon^{q},\ldots,\epsilon^{q^{n-1}}$. Thus

$\displaystyle\Upsilon(x)$
$\displaystyle=x^{n}+a_{n-1}x^{n-1}+\ldots+a_{1}x+a_{0}$
$\displaystyle=(x-\epsilon)(x-\epsilon^{q})\ldots(x-\epsilon^{q^{n-1}}),$

and following the comparison of the coefficients we get that
$\mathrm{PN}_{q^{n}/q}(\epsilon)=(-1)^{n-1}a_{1}$, that is,
$\mathrm{PN}_{q^{n}/q}(\epsilon)\in\mathbb{F}_{q}$. Before this article,
conditions were proved to ensure the presence of a primitive pair for a
primitive normal pair $(\epsilon,f(\epsilon))$, where $f(x)$ is a rational
function in $\mathbb{F}_{q^{n}}(x)$ with certain restrictions, along with a
specified trace or norm. In this article, our aim is to identify those pairs
$(q,n)$ for which the field $\mathbb{F}_{q^{n}}$ contains a primitive normal
pair $(\epsilon,f(\epsilon))$ over $\mathbb{F}_{q}$, satisfying
$\mathrm{PN}_{q^{n}/q}(\epsilon)=a$, for prescribed $a\in\mathbb{F}_{q}$.
Furthermore, the trace of an element $\epsilon\in\mathbb{F}_{q^{n}}$ over
$\mathbb{F}_{q}$, represented as $\mathrm{Tr}_{{q^{n}}/q}(\epsilon)$ and is
defined as
$\mathrm{Tr}_{{q^{n}}/q}(\epsilon)=\epsilon+\epsilon^{q}+\ldots+\epsilon^{q^{n-1}}$.
Similarly, the norm of an element $\epsilon\in\mathbb{F}_{q^{n}}$ over
$\mathbb{F}_{q}$, denoted by $\mathrm{N}_{{q^{n}}/q}(\epsilon)$ and is defined
as
$\mathrm{N}_{{q^{n}}/q}(\epsilon)=\epsilon\cdot\epsilon^{q}\ldots\epsilon^{q^{n-1}}$.
To proceed, we shall use of the following result.

######  Lemma 1.2.

Assume that $q$, $n$ be positive integers where $q$ is a prime power. Then
$\mathrm{PN}_{q^{n}/q}(\epsilon)=\mathrm{Tr}_{q^{n}/q}(\epsilon^{-1})\cdot\mathrm{N}_{q^{n}/q}(\epsilon)$
for any $\epsilon\in\mathbb{F}_{q^{n}}^{*}$.

###### Proof.

For any $\epsilon\in\mathbb{F}_{q^{n}}^{*}$,

$\displaystyle\mathrm{PN}_{q^{n}/q}(\epsilon)=\sum_{i=0}^{n-1}\Bigg{(}\underset{j\neq
i}{\prod_{j=0}^{n-1}}\epsilon^{q^{j}}\Bigg{)}$
$\displaystyle=\sum_{i=0}^{n-1}\Bigg{(}\epsilon^{-q^{i}}\underset{}{\prod_{j=0}^{n-1}}\epsilon^{q^{j}}\Bigg{)}$
$\displaystyle=\Bigg{(}\sum_{i=0}^{n-1}\epsilon^{-q^{i}}\Bigg{)}\cdot\Bigg{(}\underset{}{\prod_{j=0}^{n-1}}\epsilon^{q^{j}}\Bigg{)}$
$\displaystyle=\mathrm{Tr}_{q^{n}/q}(\epsilon^{-1})\cdot\mathrm{N}_{q^{n}/q}(\epsilon)$

∎

Thus, for $a\in\mathbb{F}_{q}$, to investigate the existence of a primitive
normal pair $(\epsilon,f(\epsilon))$, where $f(x)\in\mathbb{F}_{q^{n}}(x)$
with $\mathrm{PN}_{\mathbb{F}_{q^{n}}/\mathbb{F}_{q}}(\epsilon)=a$, it is
sufficient to show that for $a\in\mathbb{F}_{q}$ and primitive
$b\in\mathbb{F}_{q}^{*}$, there exists a primitive normal pair
$(\epsilon,f(\epsilon))$, where $f(x)\in\mathbb{F}_{q^{n}}(x)$ and
$\mathrm{Tr}_{q^{n}/q}(\epsilon^{-1})=ab^{-1}$ and
$\mathrm{N}_{q^{n}/q}(\epsilon)=b$. Indeed, for any
$f(x)\in\mathbb{F}_{q^{n}}(x)$, the existence of primitive normal pairs
$(\epsilon,f(\epsilon))$ together with prescribed trace or norm (or both) has
been an interesting domain of research and numerous researchers has worked in
the direction [1, 8, 11, 12, 13, 4]. In this article, we identify those pairs
$(q,n)$ such that for $f(x)\in\mathbb{F}_{q^{n}}(x)$, the field
$\mathbb{F}_{q^{n}}$ contains a primitive normal pair $(\epsilon,f(\epsilon))$
over $\mathbb{F}_{q}$ such that ${\mathrm{PN}}_{q^{n}/q}(\epsilon)=a$ for any
$a\in\mathbb{F}_{q}$.

We will define the following sets, which will have significant importance in
this article, for $m_{1},m_{2}\in\mathbb{N}\cup\\{0\\}$.

  1. 1.

Let us define $\mathcal{Q}_{q,n}(m_{1},m_{2})$ to be the set contains with the
rational functions $f(x)=\frac{f_{1}(x)}{f_{2}(x)}$, where $f_{1}$ and $f_{2}$
co prime irreducible polynomials over $\mathbb{F}_{q^{n}}$ such that $x\nmid
f_{1},f_{2}$ with $deg(f_{1})=m_{1}$ and $deg(f_{2})=m_{2}$.

  2. 2.

Let $\mathcal{S}_{m_{1},m_{2}}$ appears to be the set containing the pairs
$(q,n)\in\mathbb{N}\times\mathbb{N}$ such that for any
$f\in\mathcal{Q}_{q,n}(m_{1},m_{2})$, $a\in\mathbb{F}_{q}$, and any primitive
$b\in\mathbb{F}_{q}^{*}$, there exists a primitive normal pair
$(\epsilon,f(\epsilon))\in\mathbb{F}_{q^{n}}^{*}\times\mathbb{F}_{q^{n}}^{*}$
for which $\mathrm{Tr}_{q^{n}/q}(\epsilon^{-1})=ab^{-1}$ and
$\mathrm{N}_{q^{n}/q}(\epsilon)=b$.

  3. 3.

Define ,
$\mathcal{Q}_{q,n}(m)=\bigcup_{m_{1}+m_{2}=m}\mathcal{Q}_{q,n}(m_{1},m_{2})$
and $\mathcal{S}_{m}=\bigcap_{m_{1}+m_{2}=m}\mathcal{S}_{m_{1},m_{2}}$.

Clearly, $(q,1)\notin\mathcal{S}_{m_{1},m_{2}}$ as in that case we get that
$\mathrm{PN}_{q^{n}/q}(\epsilon)=\epsilon$. Hence $(q,1)$ to be in
$\mathcal{S}_{m_{1},m_{2}}$, every pair $(\epsilon,f(\epsilon))$ in
$\mathbb{F}_{q}$ must be primitive normal, for any
$f\in\mathcal{Q}_{q,n}(m_{1},m_{2})$, which is possible only if $q-1$ is
prime, that is, if $p=2$. We assume that $f(x)=x+1$. Then it implies that
$(1,0)$ is a primitive normal pair. Due to complexity, we have not discussed
the cases $n=2,3,4$ in this article, while in future we shall try the
remaining cases further.

The structure of this article is as follows. Fundamental notations and
definitions that will be used all through this article are mentioned in
Section 2. In Section 3, we prove a sufficient condition for achieving our
main objective. Subsequently, in Section 4, we introduce the prime sieve
condition, which relaxes the sufficient condition. Lastly, we demonstrate the
application of the results in the preceding sections by considering finite
fields with characteristic $7$ and $m=3$. Specifically, we derive a subset of
$\mathcal{S}_{3}$.

##  2\. Preliminaries

This section presents a preliminary outline of essential concepts, symbols,
and definitions that will be used throughout this article. In this context,
$n$ signifies a positive integer, $q$ denotes any prime power, and
$\mathbb{F}_{q}$ indicates the finite field containing $q$ elements.

######  Definition 2.1.

(Character). Let $A$ be an abelain group and $U$ be the subset of complex
numbers containing elements on the circle with unit modulus. A character
$\chi$ of $A$ is a homomorphism from $A$ into $U$, i.e.,
$\chi(a_{1}a_{2})=\chi(a_{1})\chi(a_{2})$ for all $a_{1},a_{2}\in A$.

The character $\chi_{1}$ defined by $\chi_{1}(a)=1$ for all $a\in A$, is said
to be the trivial character of $A$. Moreover, the collection of all characters
of $A$, denoted as $\widehat{A}$, forms a group under multiplication and
$A\cong\widehat{A}$. Further, since
$\mathbb{F}_{q^{n}}^{*}\cong\widehat{\mathbb{F}_{q^{n}}^{*}}$, then for any
$d|q^{n}-1$, there are $\phi(d)$ multiplicative characters of order $d$.

In the context of a finite field $\mathbb{F}_{q^{n}}$, a multiplicative
character relates to the multiplicative group $\mathbb{F}_{q^{n}}^{*}$,
whereas an additive character corresponds to the additive group
$\mathbb{F}_{q^{n}}$. Any multiplicative character can $\chi$, associated to
$\mathbb{F}_{q^{n}}^{*}$, can be extended to $\mathbb{F}_{q^{n}}$ by the
following rule

$\chi(0)=\begin{cases}1,~{}\text{if}~{}\chi=\chi_{1},\\\
0,~{}\text{if}~{}\chi\neq\chi_{1}.\end{cases}\\\ $

######  Definition 2.2.

($e$-free element). Let $\epsilon\in\mathbb{F}_{q^{n}}^{*}$ and $e$ be any
divisor of $q^{n}-1$. Then, $\epsilon$ is said to be an $e$-free, if
$\epsilon=\delta^{d}$, where $\delta\in\mathbb{F}_{q^{n}}^{*}$ and $d|e$
implies that $d=1$. Clearly, $\epsilon\in\mathbb{F}_{q^{n}}^{*}$ is primitive
if and only if $\epsilon$ is $(q^{n}-1)$-free.

For any $e|(q^{n}-1)$, the characteristic function determining the subset of
$e$-free elements of $\mathbb{F}_{q^{n}}^{*}$ is given by

(1)
$\displaystyle\rho_{e}:\mathbb{F}_{q^{n}}^{*}\rightarrow\\{0,1\\};\epsilon\mapsto{}\theta(e)\sum_{d|e}\frac{\mu(d)}{\phi(d)}\sum_{\chi_{d}}\chi_{d}(\epsilon),$

where $\theta(e):=\frac{\phi(e)}{e}$, $\chi_{d}$ represents a multiplicative
character of order $d$ in $\widehat{\mathbb{F}_{q^{n}}^{*}}$ and $\mu$ is the
Möbius function.

The additive group $\mathbb{F}_{q^{n}}$ becomes an $\mathbb{F}_{q}[x]$-module
according to the following rule.

$f\circ\epsilon=\sum_{i=0}^{r}{a_{i}\epsilon^{q^{i}}};~{}\text{for}~{}\epsilon\in\mathbb{F}_{q^{n}}~{}\text{and}~{}g(x)=\sum_{i=0}^{r}{a_{i}x^{i}}\in\mathbb{F}_{q}[x].$

For $\epsilon\in\mathbb{F}_{q^{n}}$, the $\mathbb{F}_{q}$-order of $\epsilon$
is the monic $\mathbb{F}_{q}$-divisor $f$ of $x^{n}-1$ of minimal degree such
that $f\circ\epsilon=0$.

######  Definition 2.3.

($g$-free element). Let $g|x^{n}-1$ and $\epsilon\in\mathbb{F}_{q^{n}}$.
Suppose that for any $h|g$ and $\delta\in\mathbb{F}_{q^{n}}$,
$\epsilon=h\circ\delta$ implies $h=1$. Then $\epsilon\in\mathbb{F}_{q^{n}}$ is
said to be $g$-free. It is straightforward to observe that, any element
$\epsilon\in\mathbb{F}_{q^{n}}$ is normal if and only if $\epsilon$ is
$(x^{n}-1)$-free.

For any $g|x^{n}-1$, the characteristic function determining the subset of
$g$-free elements in $\mathbb{F}_{q^{n}}$ is given by

(2)
$\displaystyle\kappa_{g}:\mathbb{F}_{q^{n}}\mapsto\\{0,1\\};\epsilon\xrightarrow{}\Theta(g)\sum_{h|g}\frac{\mu_{q}(h)}{\Phi_{q}(h)}\sum_{\lambda_{h}}\lambda_{h}(\epsilon),$

where $\Theta(g):=\frac{\Phi_{q}(g)}{q^{deg(g)}}$, $\lambda_{h}$ stands for
any additive character of $\mathbb{F}_{q}$-order $h$ in
$\widehat{\mathbb{F}_{q^{n}}}$ and $\mu_{q}$ is the Möbius function for the
set of polynomials over $\mathbb{F}_{q}$ is defined as follows:

$\mu_{q}(f)=\begin{cases}(-1)^{r},~{}\text{if $f$ is product of $r$ distinct
monic irreducible polynomials},\\\
0,\;\;\;\;\;\;\;\;\;\text{otherwise}.\end{cases}\\\ $

For any $a\in\mathbb{F}_{q}$, the characteristic function for the subset of
$\mathbb{F}_{q^{n}}$ containing elements with
$\mathrm{Tr}_{{q^{n}}/q}(\epsilon)=a$ is given as follows:

$\tau_{a}:\mathbb{F}_{q^{n}}\rightarrow\\{0,1\\};\epsilon\mapsto\frac{1}{q}\sum_{\lambda\in{\widehat{{\mathbb{F}}_{q}}}}\lambda(\mathrm{Tr}_{{q^{n}}/q}(\epsilon)-a).$

Now, any additive character $\lambda$ of $\mathbb{F}_{q}$ can be represented
using the canonical additive character $\lambda_{0}$ as
$\lambda(\epsilon)=\lambda_{0}(t\epsilon)$, where $t$ is an element of
$\mathbb{F}_{q}$ that corresponds to $\lambda$. Thus

(3) $\displaystyle\tau_{a}(\epsilon)$
$\displaystyle=\frac{1}{q}\sum_{t\in\mathbb{F}_{q}}\lambda_{0}(\mathrm{Tr}_{{q^{n}}/q}(t\epsilon)-ta)$
$\displaystyle=\frac{1}{q}\sum_{t\in\mathbb{F}_{q}}{\widehat{\lambda}_{0}}(t\epsilon)\lambda_{0}(-ta),$

where $\widehat{\lambda}_{0}$ is the additive character of
$\mathbb{F}_{q^{n}}$, that is given by
$\widehat{\lambda}_{0}(\epsilon)=\lambda_{0}(\mathrm{Tr}_{{q^{n}}/q}(\epsilon))$.

Moreover, for $c\in\mathbb{F}_{q}^{*}$, the characteristic function for the
subset of $\mathbb{F}_{q^{n}}^{*}$ containing elements with
$\mathrm{N}_{{q^{n}}/q}(\epsilon)=c$ is defined as follows:

$\displaystyle\eta_{c}:\mathbb{F}_{q^{n}}^{*}\rightarrow\\{0,1\\};\epsilon\mapsto\frac{1}{q-1}\sum_{\chi\in{\widehat{{\mathbb{F}}_{q}^{*}}}}\chi(\mathrm{N}_{{q^{n}}/q}(\epsilon)c^{-1}).$

Let $\chi_{q-1}$ be a multiplicative character of order $q-1$. Thus any $\chi$
of $\widehat{{\mathbb{F}}_{q}^{*}}$ can be expressed in terms of $\chi_{q-1}$
as $\chi(\epsilon)=\chi_{q-1}(\epsilon^{i})$ for some positive integer
$i\in\\{1,2,\ldots,q-1\\}$. Thus

(4) $\displaystyle\eta_{c}(\epsilon)$
$\displaystyle=\frac{1}{q-1}\sum_{i=1}^{q-1}\chi_{q-1}^{i}(\mathrm{N}_{{q^{n}}/q}(\epsilon)c^{-1})$
$\displaystyle=\frac{1}{q-1}\sum_{i=1}^{q-1}\tilde{\chi}^{i}(\epsilon)\chi_{q-1}(a^{-i})$

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

The following lemmas has proved by Wan and Fu [5] and are crucial for proving
our main result as well as the modified prime sieve.

######  Lemma 2.4.

([5], Theorem 5.5) Consider
$f(x)=\prod_{i=1}^{r}f_{i}(x)^{a_{i}}\in\mathbb{F}_{q^{n}}(x)$ be such that
$f_{i}$’s are irreducible polynomials over $\mathbb{F}_{q^{n}}$ and $a_{i}$’s
are nonzero integers. Suppose that $\chi\in\widehat{{\mathbb{F}}_{q}^{*}}$ be
a multiplicative character having order $d$. Further, assume $f(x)$ to be a
rational function, which is not equal to $h(x)^{d}$, for
$h(x)\in\mathbb{F}_{q^{n}}(x)$, the of rational functions. Then

$\Bigg{|}\sum_{\epsilon\in\mathbb{F}_{q^{n}},f(\epsilon)\neq
0,\infty}\chi(f(\epsilon))\Bigg{|}\leq\Bigg{(}\sum_{i=1}^{r}deg(f_{i})-1\Bigg{)}q^{n/2}.$

######  Lemma 2.5.

([5], Theorem 5.6) Let $f(x)$, $g(x)$ $\in\mathbb{F}_{q^{n}}(x)$ be rational
functions over $\mathbb{F}_{q^{n}}$. Express $f(x)$ as
$\prod_{i=1}^{r}f_{i}(x)^{a_{i}}$, where each $f_{i}(x)$ is an irreducible
polynomial over the field $\mathbb{F}_{q^{n}}$, and $a_{i}$’s are nonzero
integers $(i=1,2,\ldots,r)$. Let $D_{1}=\sum_{i=1}^{r}deg(f_{i})$,
$D_{2}=max(deg(g(x)),0)$, $D_{3}$ represents the degree of the denominator of
$g(x)$ and $D_{4}$ denotes the sum of the degrees of irreducible polynomials
dividing the denominator of $g(x)$ (excluding those equal to $f_{i}(x)$, for
$i=1,2,\ldots,r$). Consider $\chi$ as a multiplicative character of
$\mathbb{F}_{q^{n}}^{*}$ and $\lambda$ as a nontrivial additive character of
$\mathbb{F}_{q^{n}}$. Further, assume that $g(x)\neq h(x)^{q^{n}}-h(x)$, where
$h(x)\in\mathbb{F}_{q^{n}}(x)$. Then we have

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

For $l$, a positive integer (or a monic polynomial over $\mathbb{F}_{q}$), we
use $\omega(l)$ to represent the cardinality of the set which contains
distinct prime divisors (irreducible factors ) of $l$ and $W(l)$ to represent
the cardinality of the set which contains square-free divisors (square-free
factors) of $l$, that is $W(l)=2^{\omega(l)}$.

######  Lemma 2.6.

([9], Lemma 3.7) Let $r>0$ be a real number and $m$ be a positive integer.
Then $W(m)<\mathcal{C}\cdot m^{\frac{1}{r}}$, where
$\mathcal{C}=\frac{2^{w}}{{({p_{1}p_{2}\ldots p_{w})}}^{\frac{1}{r}}}$ and
$p_{1},p_{2},\ldots,p_{w}$ are primes $\leq 2^{r}$ that divide $m$.

######  Lemma 2.7.

([3], Lemma 2.9) Suppose that $q$ be a prime power, $n$ be a natural number
and $n^{\prime}$=gcd$(n,q-1)$. Then we have $W(x^{n}-1)\leq
2^{\frac{1}{2}\\{n+n^{\prime}\\}}$, which gives $W(x^{n}-1)\leq 2^{n}$.
Further, $W(x^{n}-1)=2^{n}$ if and only if $n|q-1$. In addition, if $n\nmid
q-1$, then $W(x^{n}-1)\leq 2^{\frac{3}{4}n}$.

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 2.8.

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

##  3\. Main Result

Let $e_{1},e_{2}|q^{n}-1$ and $g_{1},g_{2}|x^{n}-1$. Let
$\delta=$gcd($e_{1},q-1$) and $Q_{e_{1}}$ be the largest divisor of $e_{1}$
such that gcd($Q_{e_{1}},\delta$)$=1$. Let
$m_{1},m_{2}\in\mathbb{N}\cup\\{0\\}$ be such that $1\leq m_{1}+m_{2}<q^{n}$.
Also, let $f(x)\in\mathcal{Q}_{q,n}(m)$, $a\in\mathbb{F}_{q}$ and
$b\in\mathbb{F}_{q}^{*}$ be $\delta$-free element. We denote
$\mathfrak{M}_{f,a,b}(Q_{e_{1}},e_{2},g_{1},g_{2})$ as the number of
$\epsilon\in\mathbb{F}_{q^{n}}^{*}$ such that $\epsilon$ is $Q_{e_{1}}$-free,
$g_{1}$-free and $f(\epsilon)$ is $e_{2}$-free, $g_{2}$-free with
$\mathrm{Tr}_{q^{n}/q}(\epsilon^{-1})=ab^{-1}$ and
$\mathrm{N}_{q^{n}/q}(\epsilon)=b$. Let us abbreviate, $Q:=Q_{q^{n}-1}$.

We hereby prove the following inequality like sufficient condition.

######  Theorem 3.1.

Let $n,m,q\in\mathbb{N}$ be such that $q$ is a prime power and $n\geq 5$.
Assume that

$q^{\frac{n}{2}-2}>(2m+2)W(Q){W(q^{n}-1)}{W(x^{n}-1)}^{2}.$

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

###### Proof.

Suppose that $\mathcal{U}$ be the set containing zeros and poles of $f$ and
$\mathcal{U}_{1}=\mathcal{U}\cup\\{0\\}$. Then by the definition
$\mathfrak{M}_{f,a,b}(Q_{e_{1}},e_{2},g_{1},g_{2})$ is given by

$\displaystyle\sum_{\epsilon\in\mathbb{F}_{q^{n}}\smallsetminus\mathcal{U}_{1}}\rho_{Q_{e_{1}}}(\epsilon)\rho_{e_{2}}(f(\epsilon))\kappa_{g_{1}}(\epsilon)\kappa_{g_{2}}(f(\epsilon))\tau_{ab^{-1}}(\epsilon^{-1})\eta_{b}(\epsilon).$

Using (1), (2), (3) and (4) we have

(5)
$\displaystyle\mathfrak{M}_{f,a,b}(Q_{e_{1}},e_{2},g_{1},g_{2})=\mathcal{H}\underset{\underset{h_{1}|g_{1},h_{2}|g_{2}}{d_{1}|Q_{e_{1}},d_{2}|e_{2}}}{\sum}\frac{\mu}{\phi}(d_{1},d_{2},h_{1},h_{2})\underset{\underset{\lambda_{h_{1},\lambda_{h_{2}}}}{\chi_{d_{1}},\chi_{d_{2}}}}{\sum}\boldsymbol{\chi}_{f,a,b}(d_{1},d_{2},h_{1},h_{2})$

where
$\mathcal{H}=\frac{\theta(Q_{e_{1}})\theta(e_{2})\Theta(g_{1})\Theta(g_{2})}{q(q-1)}$,
$\frac{\mu}{\phi}(d_{1},d_{2},h_{1},h_{2})=\frac{\mu(d_{1})\mu(d_{2})\mu_{q}(h_{1})\mu_{q}(h_{2})}{\phi(d_{1})\phi(d_{2})\Phi_{q}(h_{1})\Phi_{q}(h_{2})}$
and

$\displaystyle\boldsymbol{\chi}_{f,a,b}(d_{1},d_{2},h_{1},h_{2})$
$\displaystyle=\sum_{i=1}^{q-1}\sum_{t\in\mathbb{F}_{q}}\chi_{q-1}(b^{-i})\lambda_{0}(-ab^{-1}t)\sum_{\epsilon\in\mathbb{F}_{q^{n}}\smallsetminus\mathcal{U}_{1}}\chi_{d_{1}}(\epsilon)\chi_{d_{2}}(f(\epsilon))\lambda_{h_{1}}(\epsilon)$
$\displaystyle\times\lambda_{h_{2}}(f(\epsilon))\tilde{\chi}^{i}(\epsilon)\widehat{\lambda_{0}}(t\epsilon^{-1}).$

Since $\chi_{q^{n}-1}$ is a multiplicative character of order $q^{n}-1$ in the
cyclic group $\widehat{\mathbb{F}_{q^{n}}^{*}}$, there exist
$c_{i}\in\\{0,1,2,\ldots,q^{n}-2\\}$ such that
$\chi_{d_{i}}(\epsilon)=\chi_{q^{n}-1}(\epsilon^{c_{i}})$ for $i=1,2$.
Furthermore, there exist $y_{1},y_{2}\in\mathbb{F}_{q^{n}}$ such that
$\lambda_{h_{i}}(\epsilon)=\widehat{\lambda_{0}}(y_{i}\epsilon)$, for $i=1,2$.
Thus

$\displaystyle\boldsymbol{\chi}_{f,a,b}(d_{1},d_{2},h_{1},h_{2})=$
$\displaystyle\sum_{i=1}^{q-1}\sum_{t\in\mathbb{F}_{q}}\chi_{q-1}(b^{-i})\lambda_{0}(-ab^{-1}t)\sum_{\epsilon\in\mathbb{F}_{q^{n}}\smallsetminus\mathcal{U}_{1}}\chi_{q^{n}-1}(\epsilon^{c_{1}+\frac{q^{n}-1}{q-1}i}f(\epsilon)^{c_{2}})$
$\displaystyle\times\widehat{\lambda_{0}}(y_{1}\epsilon+t\epsilon^{-1}+y_{2}f(\epsilon))$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{q-1}\sum_{t\in\mathbb{F}_{q}}\chi_{q-1}(b^{-i})\lambda_{0}(-ab^{-1}t)\sum_{\epsilon\in\mathbb{F}_{q^{n}}\smallsetminus\mathcal{U}_{1}}\chi_{q^{n}-1}(F(\epsilon))\widehat{\lambda_{0}}(G(\epsilon)),$

where
$F(x)=x^{c_{1}+\frac{q^{n}-1}{q-1}i}{f(x)}^{c_{2}}\in\mathbb{F}_{q^{n}}(x)$
and $G(x)=y_{1}x+tx^{-1}+y_{2}f(x)\in\mathbb{F}_{q^{n}}(x)$. Firstly, let us
consider the situation $G(x)\neq{\mathcal{L}(x)}^{q^{n}}-{\mathcal{L}(x)}$ for
any $\mathcal{L}(x)\in\mathbb{F}_{q^{n}}(x)$. Here we arrive at the following
possibilities.
Case 1: If $m_{2}+1\geq m_{1}$, then as mentioned in Lemma 2.5 we have
$D_{2}=1$, and

$\displaystyle|\boldsymbol{\chi}_{f,a}(d_{1},d_{2},h_{1},h_{2})|\leq(2m+2)(q-1)q^{\frac{n}{2}+1}.$

Case 2: If $m_{2}+1<m_{1}$, then we have $D_{2}=m_{1}-m_{2}$ and

$\displaystyle|\boldsymbol{\chi}_{f,a}(d_{1},d_{2},h_{1},h_{2})|\leq(2m+1)(q-1)q^{\frac{n}{2}+1}.$

Next, we assume that $G(x)={\mathcal{L}(x)}^{q^{n}}-{\mathcal{L}(x)}$ for some
$\mathcal{L}(x)\in\mathbb{F}_{q^{n}}(x)$. Then we have

(6) $\displaystyle
y_{1}x+tx^{-1}+y_{2}f(x)={\mathcal{L}(x)}^{q^{n}}-{\mathcal{L}(x)}.$

We claim that the above equation is feasible only if $y_{1}=y_{2}=t=0$. Let us
write $\mathcal{L}(x)=\frac{l_{1}(x)}{l_{2}(x)}$ with gcd$(l_{1},l_{2})=1$,
which gives that

(7) $\displaystyle
xf_{2}(x)({l_{1}(x)}^{q^{n}}-l_{1}(x){l_{2}(x)}^{q^{n}-1})={l_{2}(x)}^{q^{n}}(y_{1}x^{2}f_{2}(x)+tf_{2}(x)+y_{2}xf_{1}(x)).$

Since
$({l_{1}(x)}^{q^{n}}-l_{1}(x){l_{2}(x)}^{q^{n}-1},{l_{2}(x)}^{q^{n}})=1$, it
implies that ${l_{2}(x)}^{q^{n}}|xf_{2}(x)$. Further, since
$f\in\mathcal{Q}_{q,n}(m)$, we have
$f_{2}(x)|{l_{2}(x)}^{q^{n}}\implies{l_{2}(x)}^{q^{n}}=k{f_{2}}(x)$ for some
$k\in\mathbb{F}_{q^{n}}[x]$, which further implies
${l_{2}(x)}^{q^{n}}=f_{2}(x)$ or ${l_{2}(x)}^{q^{n}}=xf_{2}(x)$. The earlier
is possible only if $l_{2}(x)=w$, where $w\in\mathbb{F}_{q^{n}}^{*}$. Then (7)
becomes

$x({l_{1}(x)}^{q^{n}}-l_{1}(x))=(y_{1}x^{2}w+tw+y_{2}xf_{1}(x)),$

and this forces that $t=0$. Substituting it to the above yields,
${l_{1}(x)}^{q^{n}}-l_{1}(x)=y_{1}xw+y_{2}f_{1}(x)$, which happens only if
$l_{1}$ is nonzero constant and $y_{1}=y_{2}=0$. Now, let us consider the
latter possibility, that is, ${l_{2}(x)}^{q^{n}}=xf_{2}(x)$. This gives
$x|l_{2}(x)$, which further gives $x|f_{2}(x)$, a contradiction. Hence we have
$t=y_{1}=y_{2}=0$, that is, $h_{1}=h_{2}=1,t=0$. In addition to this, let us
consider the following possibilities.
Case 1: If $F(x)\neq{\mathcal{R}(x)}^{q^{n}-1}$ for any
$\mathcal{R}(x)\in\mathbb{F}_{q^{n}}(x)$, then it follows from Lemma 2.4, that

$\displaystyle|\boldsymbol{\chi}_{f,a}(d_{1},d_{2},h_{1},h_{2})|\leq
m(q-1)q^{\frac{n}{2}+1}.$

Case 2: Here, we consider the case when $F(x)=\mathcal{R}(x)^{q^{n}-1}$ for
some $\mathcal{R}(x)\in\mathbb{F}_{q^{n}}(x)$, where
$\mathcal{R}(x)=\frac{r_{1}(x)}{r_{2}(x)}$ with gcd$(r_{1},r_{2})=1$. Then we
have
$x^{c_{1}+\frac{q^{n}-1}{q-1}i}\bigg{(}{\frac{f_{1}(x)}{f_{2}(x)}}\bigg{)}^{c_{2}}=\bigg{(}{\frac{r_{1}(x)}{r_{2}(x)}}\bigg{)}^{q^{n}-1}$,
that is,

(8) $\displaystyle
x^{c_{1}+\frac{q^{n}-1}{q-1}i}{f_{1}(x)}^{c_{2}}{r_{2}(x)}^{q^{n}-1}={f_{2}(x)}^{c_{2}}{r_{1}(x)}^{q^{n}-1}.$

We now show that equation (8) is feasible only if $c_{1}=c_{2}=0$. For this,
first we show that if $c_{2}$ is $0$, then $c_{1}$ must be $0$. Suppose that
$c_{2}=0$. From equation (8), it follows that
$c_{1}+\frac{q^{n}-1}{q-1}i=k_{1}(q^{n}-1)$ for some positive integer $k_{1}$.
Following [1], it happens only if $c_{1}=0$. Next if possible, let $c_{2}\neq
0$. Again, $c_{1}+\frac{q^{n}-1}{q-1}i>0$ forces that either $x|f_{2}(x)$ or
$x|r_{1}(x)$. We may assume that $x|r_{1}(x)$, as $x\nmid f_{2}(x)$. Rewrite
equation (8) as

$\displaystyle{f_{1}(x)}^{c_{2}}{r_{2}(x)}^{q^{n}-1}={r_{1}^{\prime}(x)}^{q^{n}-1}{f_{2}(x)}^{c_{2}}x^{q^{n}-1-\frac{q^{n}-1}{q-1}i-c_{1}},$

where $r_{1}^{\prime}(x)=\frac{r_{1}(x)}{x}$. Let us discuss the following
possible cases.
Case 2.1. $q^{n}-1-\frac{q^{n}-1}{q-1}i-c_{1}>0$. Since
gcd$(r_{1}(x),r_{2}(x))=1$, we must have $x|f_{1}(x)$, a contradiction.
Case 2.2. $q^{n}-1-\frac{q^{n}-1}{q-1}i-c_{1}=0$. In this case, we have
${f_{1}(x)}^{c_{2}}{r_{2}(x)}^{q^{n}-1}={r_{1}^{\prime}(x)}^{q^{n}-1}{f_{2}(x)}^{c_{2}}$.
Since gcd$(f_{1}(x),f_{2}(x))=1$, the latter gives $f_{2}(x)|r_{2}(x)$, which
further implies that
${f_{1}(x)}^{c_{2}}{r_{2}^{\prime}(x)}^{q^{n}-1}{f_{2}(x)}^{q^{n}-1-c_{2}}={r_{1}^{\prime}(x)}^{q^{n}-1}$,
where $r_{2}^{\prime}(x)=\frac{r_{2}(x)}{f_{2}(x)}$. Since $q^{n}-1-c_{2}>0$,
we must have $f_{2}(x)|r_{1}^{\prime}(x)$, a contradiction.
Case 2.3. $q^{n}-1-\frac{q^{n}-1}{q-1}i-c_{1}<0$. As $x\nmid f_{2}(x)$, so we
have $x|r_{1}^{\prime}(x)$, which gives
${f_{1}(x)}^{c_{2}}{r_{2}(x)}^{q^{n}-1}={r_{1}^{\prime\prime}(x)}^{q^{n}-1}{f_{2}(x)}^{c_{2}}x^{2(q^{n}-1)-\frac{q^{n}-1}{q-1}i-c_{1}}$,
where $r_{1}^{\prime\prime}(x)=\frac{r_{1}^{\prime}(x)}{x}$. Here
$2(q^{n}-1)-\frac{q^{n}-1}{q-1}i-c_{1}>0$ implies that $x|f_{1}(x)$, a
contradiction. Thus, it follows that $F(x)\neq{\mathcal{R}(x)}^{q^{n}-1}$ for
any $\mathcal{R}(x)\in\mathbb{F}_{q^{n}}(x)$. Hence, $c_{1}=c_{2}=0$, that is,
$d_{1}=d_{2}=1$.

Thus, if $(d_{1},d_{2},h_{1},h_{2})\neq(1,1,1,1)$, then based one the above
discussions, we get that

$|\boldsymbol{\chi}_{f,a,b}(d_{1},d_{2},h_{1},h_{2})|\leq(2m+2)(q-1)q^{\frac{n}{2}+1}.\\\
$

Further, we have

$\displaystyle\boldsymbol{\chi}_{f,a,b}(1,1,1,1)$
$\displaystyle=\sum_{i=1}^{q-1}\sum_{t\in\mathbb{F}_{q}}\chi_{q-1}(b^{-i})\lambda_{0}(-ab^{-1}t)\sum_{\epsilon\in\mathbb{F}_{q^{n}}\smallsetminus\mathcal{U}_{1}}{\chi}_{q^{n}-1}(\epsilon^{\frac{q^{n}-1}{q-1}i})\widehat{\lambda_{0}}(t\epsilon^{-1})$
$\displaystyle=(q^{n}-|\mathcal{U}_{1}|)+V_{1}+V_{2},$

where

$\displaystyle
V_{1}=\sum_{i=1}^{q-2}\chi_{q-1}(b^{-i})\sum_{\epsilon\in\mathbb{F}_{q^{n}}\smallsetminus\mathcal{U}_{1}}{\chi}_{q^{n}-1}(\epsilon^{\frac{q^{n}-1}{q-1}i})$
and $\displaystyle
V_{2}=\sum_{i=1}^{q-1}\sum_{t\in\mathbb{F}_{q}^{*}}\chi_{q-1}(b^{-i})\lambda_{0}(-ab^{-1}t)\sum_{\epsilon\in\mathbb{F}_{q^{n}}\smallsetminus\mathcal{U}_{1}}{\chi}_{q^{n}-1}(\epsilon^{\frac{q^{n}-1}{q-1}i})\widehat{\lambda_{0}}(t\epsilon^{-1}).$

Now, let us find upper bounds of $|V_{1}|$ and $|V_{2}|$. Note that for
$i\in\\{1,2,\ldots,q-2\\}$, ${\chi}_{q^{n}-1}^{\frac{q^{n}-1}{q-1}i}$ is a
nontrivial character and thus
$\sum_{\epsilon\in\mathbb{F}_{q^{n}}^{*}}{\chi}_{q^{n}-1}^{\frac{q^{n}-1}{q-1}i}(\epsilon)=0$.
Hence, we get $|V_{1}|\leq m(q-2)$. Moreover, for any
$t\in\mathbb{F}_{q}^{*}$, $tx^{-1}$ is not of the form $H(x)^{q^{n}}-H(x)$,
for any $H(x)\in\mathbb{F}_{q^{n}}(x)$. Then, we have
$|V_{2}|\leq(q^{n/2}+m)(q-1)^{2}$.

Therefore from (5), we get

(9) $\displaystyle\mathfrak{M}_{f,a,b}(Q_{e_{1}},e_{2},g_{1},g_{2})$
$\displaystyle\geq\mathcal{H}\\{q^{n}-(m+1)-m(q-2)-(q-1)^{2}(q^{n/2}+m)$
$\displaystyle-(2m+2)q^{\frac{n}{2}+2}(W(Q_{e_{1}})W(e_{2})W(g_{1})W(g_{2})-1)\\}$
$\displaystyle\geq\mathcal{H}\\{(q^{n}-(2m+2)q^{\frac{n}{2}+2}W(Q_{e_{1}})W(e_{2})W(g_{1})W(g_{2})\\}.$

Hence $\mathfrak{M}_{f,a.b}(Q_{e_{1}},e_{2},g_{1},g_{2})>0$, if we have
$q^{\frac{n}{2}-2}>(2m+2)W(Q_{e_{1}})W(e_{2})W(g_{1})W(g_{2})$. Consequently,
we have $(q,n)\in\mathcal{S}_{m}$ by choosing $e_{1}=e_{2}=q^{n}-1$ and
$g_{1}=g_{2}=x^{n}-1$, that is provided

$q^{\frac{n}{2}-2}>(2m+2)W(Q){W(q^{n}-1)}{W(x^{n}-1)}^{2}.$

∎

##  4\. Prime Sieve

In this section, we provide the prime sieve inequality initially instigated by
Kapetanakis in [2], and subsequently employ it following certain
modifications.

######  Lemma 4.1.

Let $e^{\prime}|Q$ and $p_{1}^{\prime},p_{2}^{\prime},\ldots,p_{u}^{\prime}$
be the remaining distinct prime divisors of $Q$, let $e|q^{n}-1$ and
$p_{1},p_{2},\ldots,p_{r}$ be the remaining distinct primes dividing
$q^{n}-1$. Moreover, let $g$ be a divisor of $x^{n}-1$ and
$g_{1},g_{2},\ldots,g_{s}$ be the remaining distinct irreducible factors of
$x^{n}-1$. Abbreviate $\mathfrak{M}_{f,a,b}(Q,q^{n}-1,x^{n}-1,x^{n}-1)$ to
$\mathfrak{M}_{f,a,b}$. Then

(10)
$\displaystyle\mathfrak{M}_{f,a,b}\geq\sum_{i=1}^{u}\mathfrak{M}_{f,a.b}(p_{i}$
$\displaystyle{}^{\prime}e^{\prime},e,g,g)+\sum_{i=1}^{r}\mathfrak{M}_{f,a,b}(e^{\prime},p_{i}e,g,g)+\sum_{j=1}^{s}\mathfrak{M}_{f,a,b}(e^{\prime},e,gg_{j},g)$
$\displaystyle+\sum_{j=1}^{s}\mathfrak{M}_{f,a,b}(e^{\prime},e,g,gg_{j})-(u+r+2s-1)\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g).$

Upper bounds of certain differences are given in the following result, which
will be needed further.

######  Lemma 4.2.

Let $e^{\prime},e,n,q\in\mathbb{N}$, $g\in\mathbb{F}_{q}[x]$ be such that $q$
is a prime power, $n\geq 5$, $e^{\prime}|Q$, $e|q^{n}-1$, and $g|x^{n}-1$. Let
$P^{\prime}$ be a prime number which divides $Q$ but not $e^{\prime}$, let $P$
be a prime number which divides $q^{n}-1$ but not $e$, and also $I$ be an
irreducible polynomial which divides $x^{n}-1$ but not $g$. Then we get the
following bounds:

$\displaystyle|\mathfrak{M}_{f,a,b}(P^{\prime}e^{\prime},e,g,g)-\theta(P^{\prime})$
$\displaystyle\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g)|$
$\displaystyle\leq(2m+2)\theta(P^{\prime}){\theta(e)}\theta(e^{\prime}){\Theta(g)}^{2}{W(e)}W(e^{\prime}){W(g)}^{2}q^{n/2},$
$\displaystyle|\mathfrak{M}_{f,a,b}(e^{\prime},Pe,g,g)-\theta(P)$
$\displaystyle\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g)|$
$\displaystyle\leq(2m+2)\theta(P)\theta(e)\theta(e^{\prime}){\Theta(g)}^{2}W(e)W(e^{\prime}){W(g)}^{2}q^{n/2},$
$\displaystyle|\mathfrak{M}_{f,a,b}(e^{\prime},e,Ig,g)-\Theta(I)$
$\displaystyle\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g)|$
$\displaystyle\leq(2m+2)\Theta(I)\theta(e)\theta(e^{\prime}){\Theta(g)}^{2}W(e)W(e^{\prime}){W(g)}^{2}q^{n/2},$
$\displaystyle|\mathfrak{M}_{f,a,b}(e^{\prime},e,g,Ig)-\Theta(I)$
$\displaystyle\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g)|$
$\displaystyle\leq(2m+2)\Theta(I)\theta(e)\theta(e^{\prime}){\Theta(g)}^{2}W(e)W(e^{\prime}){W(g)}^{2}q^{n/2}.$

###### Proof.

From the definition, we have

$\displaystyle\mathfrak{M}_{f,a,b}(P^{\prime}e^{\prime},e,g,g)-$
$\displaystyle\theta(P^{\prime})\mathfrak{M}_{f,a}(e^{\prime},e,g,g)$
$\displaystyle=\mathcal{H}\underset{\underset{h_{1}|g,h_{2}|g}{P^{\prime}|d_{1}|P^{\prime}e^{\prime},d_{2}|e}}{\sum}\frac{\mu}{\phi}(d_{1},d_{2},h_{1},h_{2})\underset{\underset{\lambda_{h_{1},\lambda_{h_{2}}}}{\chi_{d_{1}},\chi_{d_{2}}}}{\sum}\boldsymbol{\chi}_{f,a}(d_{1},d_{2},h_{1},h_{2}).$

By using
$|\boldsymbol{\chi}_{f,a}(d_{1},d_{2},h_{1},h_{2})|\leq(2m+2)(q-1)q^{\frac{n}{2}+1}$,
we get

$\displaystyle|\mathfrak{M}_{f,a}($ $\displaystyle
P^{\prime}e^{\prime},e,g,g)-\theta(P^{\prime})\mathfrak{M}_{f,a}(e^{\prime},e,g,g)|$
$\displaystyle\leq\frac{\theta(P^{\prime})\theta(e)\theta(e^{\prime})\Theta(g)^{2}}{q(q-1)}(2m+2)(q-1)q^{\frac{n}{2}+1}W(e){W(g)}^{2}(W(P^{\prime}e^{\prime})-W(e^{\prime})).$

Since $W(P^{\prime}e^{\prime})=W(P^{\prime})W(e^{\prime})=2W(e^{\prime})$, we
have

$\displaystyle|\mathfrak{M}_{f,a}(P^{\prime}e^{\prime},e,g,g)-\theta(P^{\prime})$
$\displaystyle\mathfrak{M}_{f,a}(e^{\prime},e,g,g)|$
$\displaystyle\leq(2m+2)\theta(P^{\prime}){\theta(e)}\theta(e^{\prime}){\Theta(g)}^{2}{W(e)}W(e^{\prime}){W(g)}^{2}q^{n/2},$

The other bounds can also be derived in a similar manner. ∎

######  Theorem 4.3.

Let $e^{\prime},e,n,q\in\mathbb{N}$, $g\in\mathbb{F}_{q}[x]$ be such that $q$
is a prime power, $n\geq 5$, $e^{\prime}|Q$, $e|q^{n}-1$ and $g|x^{n}-1$. Let
$p_{1}^{\prime},p_{2}^{\prime},\ldots,p_{u}^{\prime}$ be the distinct primes
dividing $Q$ but not $e^{\prime}$, let $p_{1},p_{2},\ldots,p_{r}$ be the
distinct primes dividing $e$ but not $q^{n}-1$, and $g_{1},g_{2},\ldots,g_{s}$
be the distinct irreducible factor of $g$ but not $x^{n}-1$. Let us define

$\mathcal{S}:=1-\sum_{i=1}^{u}\frac{1}{p_{i}^{\prime}}-\sum_{i=1}^{r}\frac{1}{p_{i}}-2\sum_{j=1}^{s}\frac{1}{q^{deg(g_{j})}},\mathcal{S}>0$

and

$\mathcal{M}:=\frac{r+u+2s-1}{\mathcal{S}}+2.$

Then $\mathfrak{M}_{f,a,b}>0$, if we have

(11) $q^{\frac{n}{2}-2}>(2m+2)W(e^{\prime})W(e){W(g)}^{2}\mathcal{M}.$

###### Proof.

By using Lemma 4.1, we get the following expression

$\displaystyle\mathfrak{M}_{f,a,b}$
$\displaystyle\geq\sum_{i=1}^{u}\\{\mathfrak{M}_{f,a,b}(p_{i}^{\prime}e^{\prime},e,g,g)-\theta(p_{i}^{\prime})\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g)\\}$
$\displaystyle+\sum_{i=1}^{r}\\{\mathfrak{M}_{f,a,b}(e^{\prime},p_{i}e,g,g)-\theta(p_{i})\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g)\\}$
$\displaystyle+\sum_{j=1}^{s}\\{\mathfrak{M}_{f,a,b}(e^{\prime},e,g_{j}g,g)-\Theta(g_{j})\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g)\\}$
$\displaystyle+\sum_{j=1}^{s}\\{\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g_{j}g)-\Theta(g_{j})\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g)\\}+\mathcal{S}\mathfrak{M}_{f,a,b}(e^{\prime},e,g,g).$

From (9) and using Lemma 4.2, we obtain the following expression

$\displaystyle\mathfrak{M}_{f,a,b}$
$\displaystyle\geq({\theta(e^{\prime})\theta(e){\Theta(g)}^{2}}/q(q-1))\Bigg{[}\Bigg{(}\sum_{i=1}^{u}\theta(p_{i}^{\prime})+\sum_{i=1}^{r}\theta(p_{i})+2\sum_{j=1}^{s}\Theta(g_{j})\Bigg{)}\\{-(2m+2)$
$\displaystyle\times(q-1)W(e)W(e^{\prime}){W(g)}^{2}q^{n/2+1}\\}+\mathcal{S}\\{q^{n}-(2m+2)q^{n/2+2}W(e)W(e^{\prime}){W(g)}^{2}\\}\Bigg{]},$

which implies,

$\displaystyle\mathfrak{M}_{f,a,b}\geq(\mathcal{S}{\theta(e)\theta(e^{\prime}){\Theta(g)}^{2}}/q$
$\displaystyle(q-1))\Bigg{[}q^{n}-(2m+2)W(e)W(e^{\prime}){W(g)}^{2}q^{n/2+2}$
$\displaystyle\times\Bigg{\\{}\Bigg{(}{\sum_{i=1}^{u}\theta(p_{i}^{\prime})+\sum_{i=1}^{r}\theta(p_{i})+2\sum_{j=1}^{s}\Theta(g_{j})}\Bigg{)}\Bigg{/}{\mathcal{S}}+1\Bigg{\\}}\Bigg{]}.$

We note that
$\mathcal{S}=\sum_{i=1}^{u}\theta(p_{i}^{\prime})+\sum_{i=1}^{r}\theta(p_{i})+2\sum_{j=1}^{s}\Theta(g_{j})-(u+r+2s-1)$.
Then the above turns into

$\displaystyle\mathfrak{M}_{f,a,b}\geq(\mathcal{S}{\theta(e)\theta(e^{\prime}){\Theta(g)}^{2}}/q(q-1))\\{q^{n}-(2m+2)q^{n/2+2}W(e)W(e^{\prime}){W(g)}^{2}\mathcal{M}\\},$

where $\mathcal{M}=\frac{u+r+2s-1}{\mathcal{S}}+2$. In fact, if inequality
$(\ref{E11})$ holds, $\mathfrak{M}_{f,a,b}>0$ and so
$(q,n)\in\mathcal{S}_{m}$. ∎

##  5\. Evaluations

In this section we utilize our results to find out the presence of elements
having desired properties. The results that are mentioned earlier apply to the
arbitrary finite field $\mathbb{F}_{q^{n}}$ of arbitrary characteristic. For
illustration, we explicitly determine each pair $(q,n)$ belonging to
$\mathcal{S}_{3}$, where $q=7^{k}$ and $n\geq 6$. Here let us split our
calculations into two parts. Initially, we identify the exceptions $(q,n)$ for
$n\geq 8$, and subsequently, we execute the possible exceptions for $n=6,7$.
In this article, SageMath [10] serves as the computational tool for all
significant calculations. From Theorem 4.3, it follows that
$(q,n)\in\mathcal{S}_{3}$ if we have

(12) $q^{\frac{n}{2}-2}>8~{}W(e^{\prime}){W(e)}{W(g)}^{2}\mathcal{M}.$

Also, by Theorem 3.1, $(q,n)\in\mathcal{S}_{3}$ if we have

(13) $q^{\frac{n}{2}-2}>8W(Q)W(q^{n}-1){W(x^{n}-1)}^{2}.$

Recall that $Q$ is the largest divisor of $q^{n}-1$ such that
gcd($Q,q-1$)$=1$. Clearly, we have $W(Q)\leq W(q^{n}-1)$.
Part I: Rewrite $n$ as $n=n^{\prime}\cdot q^{i}$; $i\geq 0$, where
$q,n^{\prime}\in\mathbb{N}$ be such that $q$ is a prime power, being co prime
to $n^{\prime}$. Furthermore, assume that $d$ be the order of $q$ modulo
$n^{\prime}$, where gcd$(n^{\prime},q)=1$. Following [[7], Theorems $2.45$ and
$2.47$], $x^{n^{\prime}}-1$ can be factorized into the product of irreducible
polynomials over $\mathbb{F}_{q}$ in such a way that degree of each factor
must be less than or equal to $d$.

Denote $I_{n^{\prime}}$ as the cardinality of the set containing the
irreducible factors of $x^{n^{\prime}}-1$ over $\mathbb{F}_{q}$ such that
degree of each factor is less than $d$, and let the ratio
$\frac{N_{0}}{n^{\prime}}$ be denoted by $\pi(q,n^{\prime})$. Observe that the
set containing the irreducible factors of $x^{n}-1$ over $\mathbb{F}_{q}$ and
the set containing irreducible factors of $x^{n^{\prime}}-1$ over
$\mathbb{F}_{q}$ are of equal cardinality, and this results in
$n\pi(q,n)=n^{\prime}\pi(q,n^{\prime})$. For further computations, we shall
use bounds for $\pi(q,n)$, that is provided in the following lemma.

######  Lemma 5.1.

([9], Lemma 6.1, Lemma 7.1) Let $q=7^{k}$ and $n^{\prime}>4$ be such that
$7\nmid n^{\prime}$. Let $n_{1}^{\prime}=gcd(n^{\prime},q-1)$. Then the
following hold:

  * (i)

If $n^{\prime}=2n_{1}^{\prime}$, then we have $d=2$ and
$\pi(q,n^{\prime})=1/2$.

  * (ii)

If $n^{\prime}=4n_{1}^{\prime}$ and $q\equiv 1(mod~{}4)$, then we have $d=4$
and $\pi(q,n^{\prime})=3/8$.

  * (iii)

If $n^{\prime}=6n_{1}^{\prime}$ and $q\equiv 1(mod~{}6)$, then $d=6$ and
$\pi(q,n^{\prime})=13/36$.

  * (iv)

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

######  Lemma 5.2.

Suppose that $q=p^{k}$; $k\in\mathbb{N}$ and $n=n^{\prime}\cdot q^{i}$;
$i\in\mathbb{N}\cup\\{0\\}$, where gcd($n^{\prime},q)=1$ in addition with
$n^{\prime}\nmid q-1$. Assume that $d(>2)$ be the order of $q$ (mod
$n^{\prime}$). Moreover, let $e^{\prime}=Q$, $e=q^{n}-1$ and $g$ is assumed to
be the product of all irreducible factors of $x^{n^{\prime}}-1$ along with
each one have degree less than $d$. Then, following Theorem 4.3, we get that
$\mathcal{M}<2n^{\prime}$.

###### Proof.

The proof is omitted here, as it can be derived from [[6], Lemma 10]. ∎

Let us find the pairs $(q,n)\in\mathcal{S}_{3}$ for $q=7^{k}$; $n\geq 8$. From
now on, we assume that $n\geq 8$ and $n=n^{\prime}\cdot 7^{i}$, where
gcd$(7,n^{\prime})=1$. Then we have $W(x^{n}-1)=W(x^{n^{\prime}}-1)$.

######  Lemma 5.3.

Let $q=7$ and $n=n^{\prime}\cdot 7^{i}$, where gcd$(7,n^{\prime})=1$. Then
$(7,n)\in\mathcal{S}_{3}$ for all $n\geq 8$ except for $n=8,9,10,12$ and $18$.

###### Proof.

Firstly, assume that $n^{\prime}\nmid q^{2}-1$. Then we must have
$n^{\prime}\geq 5$ and by Lemma 5.1, we have $\pi(7,n^{\prime})\leq 1/3$
unless $n^{\prime}=36$, because then $n^{\prime}=6n_{1}^{\prime}$ and
$\pi(q,n^{\prime})=13/36$. Let $e^{\prime}=Q$, $e=7^{n}-1$ and $g$ is the
product of all irreducible factors of $x^{n^{\prime}}-1$ of degree less than
$d$. Then by Lemmas 2.6, 5.2 and inequality (13), $(7,n)\in\mathcal{S}_{3}$ if
we have

$7^{n/2-2}>8~{}{\mathcal{C}}^{2}~{}7^{2n/r}~{}2^{2n/3}~{}2n.$

Observe that the above inequality holds for $r=9.8$ and $n\geq 446$. For
$n\leq 445$, we test inequality (13), and get that $(7,n)\in\mathcal{S}_{3}$
except for $n=9,10,11,15,18,19,20,\\\ 27,30,32$. However, for the remaining
pairs, we choose the values of $e^{\prime}$, $e$, $g$, $\mathcal{S}$ and
$\mathcal{M}$ (see Table 1) such that inequality (12) is satisfied and get
that $(7,n)\in\mathcal{S}_{3}$ unless $n=9,10$ and $18$. We now consider
$n^{\prime}=36$ and by testing inequality $7^{36\cdot
7^{i}/2-2}>576\cdot\mathcal{C}^{2}\cdot 7^{72\cdot 7^{i}/r}\cdot 2^{13/18}$,
we get $(7,36\cdot 7^{i})\in\mathcal{S}_{3}$ for $i\geq 1$ and $r=10$. For the
sole remaining pair $(7,36)$, we observe that inequality (12) is verified for
certain values of $e^{\prime}$, $e$, $g$, $\mathcal{S}$ and $\mathcal{M}$ (see
Table 1).

Secondly, assume that $n^{\prime}|q^{2}-1$. By Lemmas 2.6, 2.7 and inequality
(13), $(7,n)\in\mathcal{S}_{3}$ if we have

$7^{n^{\prime}\cdot 7^{i}/2-2}>8~{}{\mathcal{C}}^{2}~{}7^{2n^{\prime}\cdot
7^{i}/r}~{}2^{2n^{\prime}}.$

Taking $r=9$, the above inequality holds for $i\geq 3$, when $n^{\prime}=1$,
for $i\geq 2$, when $n^{\prime}=2,3,4,6,8,12$ and for $i\geq 1$, when
$n^{\prime}=16,24,48$. Hence, for $n\geq 8$, $(7,n)\in\mathcal{S}_{3}$ except
when $n=8,12,14,16,21,24,28,42,48,49,56,84$. For this exceptions, we test
inequality (13) and get $(7,n)\in\mathcal{S}_{3}$ except when
$n=8,12,14,16,24,48$. However, for the remaining pairs, we choose the values
of $e^{\prime}$, $e$, $g$, $\mathcal{S}$ and $\mathcal{M}$ (see Table 1) such
that inequality (12) is satisfied and get that $(7,n)\in\mathcal{S}_{3}$
unless $n=8$ and $12$. ∎

######  Lemma 5.4.

Let $q=49$ and $n=n^{\prime}\cdot 7^{i}$, where gcd$(7,n^{\prime})=1$. Then
$(49,n)\in\mathcal{D}_{2}$ for all $n\geq 9$.

###### Proof.

Firstly, assume that $n^{\prime}\nmid q^{2}-1$. Then $n^{\prime}\nmid q-1$ and
thus by Lemma 2.7, we have $W(x^{n^{\prime}}-1)\leq
2^{\frac{3}{4}n^{\prime}}$. Then inequality (13) is true, if
$q^{n/2-2}>8~{}\mathcal{C}^{2}q^{2n/r}~{}2^{3n/2}$ is true. Choosing $r=10.5$,
the latter inequality holds for all $n\geq 381$. For $n\leq 380$, we verify
inequality (13) and get that $(49,n)\in\mathcal{S}_{3}$ unless $n=9$ and $18$.
However, for the remaining pairs, we choose the values of $e^{\prime}$, $e$,
$g$, $\mathcal{S}$ and $\mathcal{M}$ (see Table 1) such that inequality (12)
is satisfied and get that $(49,n)\in\mathcal{S}_{3}$ for all $n$.

Table 1.  $(q,n)$ | $e^{\prime}$ | $e$ | $g$ | $\mathcal{S}$ | $\mathcal{M}$
---|---|---|---|---|---
$(7,11)$ | $1$ | $2$ | $1$ | $0.379164614709749$ | $23.0990152815921$
$(7,14)$ | $1$ | $2$ | $x+1$ | $0.291669794015721$ | $36.2853466665835$
$(7,15)$ | $1$ | $2$ | $x^{2}+x+1$ | $0.207947594468628$ | $78.9424625511299$
$(7,16)$ | $1$ | $6$ | $x^{2}+6$ | $0.194961580806272$ | $109.713529574153$
$(7,19)$ | $1$ | $1$ | $x+6$ | $0.126907974235963$ | $135.955333400811$
$(7,20)$ | $1$ | $2$ | $x^{2}+6$ | $0.0219001519714673$ | $1006.55923907116$
$(7,24)$ | $5$ | $30$ | $x^{6}+6$ | $0.271667188760882$ | $123.472159190509$
$(7,27)$ | $1$ | $2$ | $x^{2}+x+1$ | $0.186434908720237$ | $130.731256204889$
$(7,30)$ | $1$ | $2$ | $x^{6}+6$ | $0.252361603032526$ | $112.951902601408$
$(7,32)$ | $1$ | $2$ | $x^{16}+6$ | $0.138344865742225$ | $146.566261224797$
$(7,36)$ | $1$ | $6$ | $x^{6}+6$ | $0.0815701713798487$ | $431.078416876374$
$(7,48)$ | $5$ | $30$ | $x^{24}+6$ | $0.0315593546237637$ | $1427.88467148551$
$(7^{2},9)$ | $1$ | $2$ | $1$ | $0.336456330954422$ | $61.4430782243456$
$(7^{2},10)$ | $1$ | $2$ | $x+1$ | $0.0219001519714673$ | $1006.55923907116$
$(7^{2},12)$ | $5$ | $30$ | $x+1$ | $0.190034535699657$ | $196.701451837560$
$(7^{2},15)$ | $1$ | $2$ | $1$ | $0.129912623440689$ | $263.714366930035$
$(7^{2},16)$ | $5$ | $30$ | $x+1$ | $0.262765246139282$ | $150.421454408501$
$(7^{2},18)$ | $1$ | $6$ | $x+1$ | $0.0232271340399648$ | $1508.85831234188$
$(7^{2},20)$ | $1$ | $2$ | $x^{4}+6$ | $0.00893876673760447$ | $3805.65670098153$
$(7^{2},24)$ | $902785$ | $5416710$ | $x+1$ | $0.0058477612584259$ | $10091.3311803707$
$(7^{2},30)$ | $55$ | $330$ | $x+1$ | $0.353135978712364$ | $169.074451646448$
$(7^{2},48)$ | $5$ | $30$ | $\frac{x^{48}-1}{x^{12}-1}$ | $0.00527505642356318$ | $10428.4287590025$
$(7^{3},8)$ | $1$ | $6$ | $1$ | $0.279932899745072$ | $94.8794008266895$
$(7^{3},9)$ | $1$ | $2$ | $1$ | $0.483964545975008$ | $66.0542788884391$
$(7^{3},10)$ | $1$ | $2$ | $1$ | $0.298329291645090$ | $79.0960165298223$
$(7^{3},12)$ | $1$ | $6$ | $1$ | $0.244971922619374$ | $140.791415915968$
$(7^{3},18)$ | $1$ | $114$ | $x+1$ | $0.776753550747086$ | $67.6578910401477$
$(7^{4},8)$ | $1$ | $2$ | $1$ | $0.335012920719318$ | $82.5939064738975$
$(7^{4},9)$ | $1$ | $2$ | $1$ | $0.0915444731815404$ | $296.938613568257$
$(7^{4},10)$ | $1$ | $2$ | $1$ | $0.207272794226151$ | $180.508714267778$
$(7^{4},12)$ | $1$ | $30$ | $x+1$ | $0.512192424178116$ | $85.9528231386856$
$(7^{4},15)$ | $1$ | $30$ | $x+3$ | $0.373733457035790$ | $149.163704411760$
$(7^{5},8)$ | $1$ | $2$ | $1$ | $0.0157216548212150$ | $1719.37646622071$
$(7^{6},8)$ | $1$ | $6$ | $1$ | $0.197106668135930$ | $189.715617893169$

Secondly, assume that $n^{\prime}|q^{2}-1$. By Lemmas 2.6, 2.7 and inequality
(13), $(49,n)\in\mathcal{S}_{3}$ if we have

$49^{n^{\prime}\cdot 7^{i}/2-2}>8~{}{\mathcal{C}}^{2}~{}49^{2n^{\prime}\cdot
7^{i}/r}~{}2^{2n^{\prime}}.$

Taking $r=9$, the above inequality holds for $i\geq 2$, when
$n^{\prime}=1,2,3,4,5$ and for $i\geq 1$, otherwise. Thus for $n\geq 8$,
$(49,n)\in\mathcal{S}_{3}$ except when $n^{\prime}=$ 8, 10, 12, 14, 15, 16,
20, 21, 24, 25, 28, 30, 32, 35, 40, 48, 50, 60, 75, 80, 96, 100, 120, 150,
160, 200, 240, 300, 400, 480, 600, 800, 1200, 2400. For each of the values of
$n$, we test inequality (13) and get that $(49,n)\in\mathcal{S}_{3}$ unless
$n=8,10,12,15,16,20,24,30,48$. However, for the remaining pairs, we verify
inequality (12) and find the values of $e^{\prime}$, $e$, $g$, $\mathcal{S}$
and $\mathcal{M}$ (listed in Table 1). Thus we get $(49,n)\in\mathcal{S}_{3}$
unless $n=8$. ∎

######  Lemma 5.5.

Let $k\in\mathbb{N}$ and $q=7^{k}$. Then $(q,n)\in\mathcal{S}_{3}$ for $n\geq
8$ and $k\geq 3$.

###### Proof.

From Lemma 2.6, $W(q^{n}-1)<C\cdot(q^{n}-1)^{1/r}$ for some positive real
number $r$ and also we have $W(x^{n}-1)\leq 2^{n}$. Therefore, by inequality
(13), $(q,n)\in\mathcal{S}_{3}$ if

(14) $q^{n/2-2}>8\cdot\mathcal{C}^{2}\cdot q^{2n/r}\cdot 2^{2n}.$

For $r=9.5$, Lemma 2.6 gives $\mathcal{C}<1.46\times 10^{7}$ and thus
inequality (14) holds for $n\geq 8$ and $k\geq 76$. For each $3\leq k\leq 75$
and for proper choice of ‘$r$’, we get $n_{k}$’s such that for all $n\geq
n_{k}$, inequality (14) is satisfied, that are listed in Table 2.

Table 2.  $r$ | $k$ | $n_{k}$
---|---|---
10 | {3} | 152
9.0 | {4} | 57
8.5 | {5} | 36
8.5 | {6} | 28
8.5 | {7} | 23
8.5 | {8} | 20
8.5 | {9} | 18
9 | {10} | 17
9 | {11} | 16
9 | {12} | 15
9 | {13,14} | 14
9 | {15,16,17} | 13
9 | {18,19,20,21} | 12
9 | {22,23,…,27} | 11
9 | {28,29,…,40} | 10
9.5 | {41,42,…,75} | 9

We calculate the values of $W(Q)$, $W(q^{n}-1)$ and $W(x^{n}-1)$ precisely for
each of the above values of $k$ and $n$ (mentioned in Table 2) and verify
inequality

$q^{\frac{n}{2}-2}>8\cdot W(Q){W(q^{n}-1)}{W(x^{n}-1)}^{2}.$

Consequently, we get $(q,n)\in\mathcal{S}_{3}$ unless $(q,n)$ equals
$(7^{3},8)$, $(7^{3},9)$, $(7^{3},10)$, $(7^{3},12)$, $(7^{3},18)$,
$(7^{4},8)$, $(7^{4},9)$, $(7^{4},10)$, $(7^{4},12)$, $(7^{4},15)$,
$(7^{5},8)$, $(7^{6},8)$. For these exceptions, we find the values of
$e^{\prime}$, $e$, $g$, $\mathcal{S}$ and $\mathcal{M}$ for all $(q,n)$
(listed in Table 1) such that inequality (12) is satisfied. Thus,
$(7^{k},n)\in\mathcal{S}_{3}$ for all $n\geq 8$ and $k\geq 3$. ∎

Part II: In this part, we execute computations for $n=6,7$. The following
lemma will be utilized in this part for computation.

######  Lemma 5.6.

Let $M\in\mathbb{N}$ such that $\omega(M)\geq 2828$. Then we have
$W(M)<M^{1/13}$.

###### Proof.

Let $S=\\{2,3,\ldots,25673\\}$ be the set containing first $2828$ primes.
Clearly the product of all elements in $S$ surpasses $2.24\times 10^{11067}$.
Let us decompose $M$ as the product of two co prime positive integers $M_{1}$
and $M_{2}$ such that prime divisors of $M_{1}$ come from the least $2828$
prime divisors of $M$ and remaining prime divisors are divisors of $M_{2}$.
Therefore, $M_{1}^{1/13}>2.16\times 10^{851}$ , on the other hand
$W(M_{1})<2.06\times 10^{851}$. Hence we draw the conclusion, as $p^{1/13}>2$
for any prime $p>25673$. ∎

First we assume that $\omega(q^{n}-1)\geq 2828$. Note that $W(x^{n}-1)\leq
2^{7}$ and thus by the 5.6, $(q,n)\in\mathcal{S}_{3}$ if we have
$q^{\frac{n}{2}-2}>8\cdot q^{\frac{2n}{13}}\cdot 2^{14}$, that is, if
$q^{n}>2^{\frac{442n}{9n-52}}$ then $(q,n)\in\mathcal{S}_{3}$. But $n\geq 6$
gives $\frac{442n}{9n-52}\leq 1326$. Hence, if $q^{n}>2^{1326}$ then
$(q,n)\in\mathcal{S}_{3}$, which is valid when $\omega(q^{n}-1)\geq 2828$. Let
us suppose that $88\leq\omega(q^{n}-1)\leq 2827$. In Theorem 4.3, choose
$g=x^{n}-1$ and $e$ (or $e^{\prime}$) is assumed to be the product of least
$88$ prime divisors of $q^{n}-1$ ( or $Q$), that is,
$W(e)=W(e^{\prime})=2^{88}$, then $r\leq 2739$ and $\mathcal{S}$ assumes its
minimum positive value when
$\\{p_{1},p_{2},\ldots,p_{2739}\\}=\\{461,463,\ldots,25667\\}$. This gives
$\mathcal{S}>0.0044306$ and $\mathcal{M}<1.24\times 10^{6}$. Thus
$8\mathcal{M}W(e^{\prime})W(e){W(g)}^{2}<1.5518994\times 10^{64}=R$(say). By
Sieve variation, we get $(q,n)\in\mathcal{S}_{3}$ if we have
$q^{\frac{n}{2}-2}>R$, that is, if $q^{n}>R^{\frac{2n}{n-4}}$. Since $n\geq 6$
implies $\frac{2n}{n-4}\leq 6$, we have $(q,n)\in\mathcal{S}_{3}$ if
$q^{n}>1.396951\times 10^{385}$. Hence, $\omega(q^{n}-1)\geq 158$ gives
$(q,n)\in\mathcal{S}_{3}$.

Table 3.  $a\leq\omega(q^{n}-1)\leq b$ | $W(e)/W(e^{\prime})$ | $\mathcal{S}>$ | $\mathcal{M}<$ | $8\mathcal{M}W(e^{\prime}){W(e)}{W(g)}^{2}<$
---|---|---|---|---
$a=17,b=157$ | $2^{17}$ | $0.02162406$ | $12904.293824$ | $2.90579\times 10^{19}$
$a=10,b=60$ | $2^{10}$ | $0.0550598$ | $1800.044933$ | $2.47397\times 10^{14}$
$a=8,b=47$ | $2^{8}$ | $0.00340868$ | $22591.376714$ | $1.94059\times 10^{14}$

We repeat the steps given in Theorem 4.3 by using the data given in the second
column of Table 3. Therefore we get, $(q,n)\in\mathcal{S}_{3}$ if we have
$q^{\frac{n}{2}-2}>1.94059\times 10^{14}$. This gives the scenarios that
$n=6,q>1.94059\times 10^{14}$; $n=7,q>(1.94059\times 10^{14})^{{2}/{3}}$.
Thus, the only possible exceptions are $(7,6),(7^{2},6),\ldots,(7^{16},6)$;
$(7,7),(7^{2},7),\ldots,(7^{11},7)$. However Table 4 implies that Theorem 4.3
holds for
$(7^{5},6),(7^{6},6),\ldots,(7^{16},6)$;$(7^{3},7),(7^{,}7),\ldots,(7^{11},7)$.
Thus the only possible exceptions are $(7,6),(7^{2},6),(7^{3},6)$ and $(7,7)$.

Table 4.  $(q,n)$ | $e^{\prime}$ | $e$ | $g$ | $\mathcal{S}$ | $\mathcal{M}$
---|---|---|---|---|---
$(7^{4},6)$ | $1$ | $6$ | $1$ | $0.434016210002031$ | $66.5137194296705$
$(7^{5},6)$ | $1$ | $2$ | $1$ | $0.257002547699352$ | $107.057324301646$
$(7^{6},6)$ | $1$ | $6$ | $1$ | $0.303162160154874$ | $91.0612469122359$
$(7^{7},6)$ | $1$ | $2$ | $1$ | $0.460243100976110$ | $62.8374138376349$
$(7^{8},6)$ | $1$ | $6$ | $1$ | $0.322185830859915$ | $104.425360891641$
$(7^{9},6)$ | $1$ | $1$ | $1$ | $0.0178814663260537$ | $1679.71476080177$
$(7^{10},6)$ | $1$ | $6$ | $1$ | $0.0818969304893583$ | $465.997854045796$
$(7^{11},6)$ | $1$ | $2$ | $1$ | $0.396638261656470$ | $82.6780462035085$
$(7^{12},6)$ | $1$ | $2$ | $1$ | $0.208001805090034$ | $189.498372829595$
$(7^{13},6)$ | $1$ | $2$ | $1$ | $0.451835063251708$ | $75.0355005264751$
$(7^{14},6)$ | $1$ | $6$ | $1$ | $0.238642380092351$ | $148.662969026941$
$(7^{15},6)$ | $1$ | $2$ | $1$ | $0.282943029313370$ | $150.439776381568$
$(7^{16},6)$ | $1$ | $2$ | $1$ | $0.0213997081969370$ | $1964.64358436493$
$(7^{2},7)$ | $1$ | $2$ | $1$ | $0.536567753199395$ | $20.6369753686705$
$(7^{3},7)$ | $1$ | $1$ | $1$ | $0.0388161015503813$ | $259.625047353622$
$(7^{4},7)$ | $1$ | $2$ | $1$ | $0.376551093326836$ | $36.5238673592599$
$(7^{5},7)$ | $1$ | $1$ | $1$ | $0.0968025701017207$ | $125.963650834790$
$(7^{6},7)$ | $1$ | $1$ | $1$ | $0.00143402424023756$ | $13251.4273575547$
$(7^{7},7)$ | $1$ | $1$ | $1$ | $0.131401454426554$ | $100.933455925073$
$(7^{8},7)$ | $1$ | $2$ | $1$ | $0.369673098692035$ | $61.5120393608290$
$(7^{9},7)$ | $1$ | $1$ | $1$ | $0.0166791949792349$ | $841.369047332896$
$(7^{10},7)$ | $1$ | $2$ | $1$ | $0.447962587202473$ | $57.8082320135819$
$(7^{11},7)$ | $1$ | $1$ | $1$ | $0.0963847008090025$ | $157.626358479073$

The above discussions leads us to conclude the following.

######  Theorem 5.7.

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

  * 1.

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

  * 2.

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

  * 3.

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

##  6\. Acknowledgments

We sincerely appreciate and acknowledge the reviewers for their helpful
comments and suggestions. First author is supported by the National Board for
Higher Mathematics (NBHM), Department of Atomic Energy (DAE), Government of
India, Ref No. 0203/6/2020-R&D-II/7387.

##  7\. Statements and Declarations

There are no known competing financial interests or personal relationships
that could have influenced this paper’s findings. All authors are equally
contributed.

## References

  * [1] A. K. Sharma, M. Rani, S. K. Tiwari, Primitive normal pairs with prescribed norm and trace, Finite Fields Appl. 78 101976 (2022).
  * [2] G. Kapetanakis, Normal bases and primitive elements over finite fields, Finite Fields Appl. 26 123-143 (2014).
  * [3] H. W. Lenstra, R. J. Schoof, Primitive normal bases for finite fields, Math. Comp. 48 217-231 (1987).
  * [4] K. Chatterjee, H. Sharma, A. Shukla, S. K. Tiwari, Arithmetic progression in a finite field with prescribed norms, Forum Math. (2024).
  * [5] L. Fu, D. Q. Wan, A class of incomplete character sums, Q.J. Math. 65 1195-1211 (2014).
  * [6] M. Rani, A. K. Sharma, S. K. Tiwari, I. Gupta, On the existence of pairs of primitive normal elements over finite fields, São Paulo J. Math. Sci. 16(2) 1032-1049 (2022).
  * [7] R. Lidl, H. Niederreiter, Finite Fields, 2nd edition, Cambridge University Press (1997).
  * [8] S. D. Cohen, A. Gupta, Primitive element pairs with a prescribed trace in the quartic extension of a finite field, J. Algebra Appl. 20(09) 2150168 (2021).
  * [9] S. D. Cohen, S. Huczynska, The strong primitive normal basis theorem, Acta Arith. 143(4) 299-332 (2010).
  * [10] The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.1), https://www.sagemath.org, (2020).
  * [11] W. S. Chou, S. D. Cohen, Primitive elements with zero traces, Finite Fields Appl. 7 125–141 (2001).
  * [12] S. D. Cohen, D. Hachenberger, Primitivity, freeness, norm and trace, Discrete Math. 214(1-3) 135-144 (2000).
  * [13] X. Cao, P. Wang, Primitive elements with prescribed trace, Appl. Algebra Engrg. Comm. Comput. 25(5) 339–345 (2014).