# Primitive normal Values of rational functions with one prescribed norm and
trace over finite fields

Arpan Chandra Mazumder  Department of Mathematical Sciences, Tezpur
University, Tezpur, Assam, 784028, India<EMAIL_ADDRESS>and  Dhiren
Kumar Basnet  Department of Mathematical Sciences, Tezpur University, Tezpur,
Assam, 784028, India<EMAIL_ADDRESS>
###### Abstract.

Let $q,n,m\in\mathbb{N}$ be such that $q$ is a prime power and
$a,b\in\mathbb{F}_{q}$. In this article we establish a sufficient condition
for the existence of a primitive normal pair
$(\alpha,f(\alpha))\in\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$ with a
prescribed primitive norm $a$ and a non-zero trace $b$ over $\mathbb{F}_{q}$
of $\alpha$, where $f(x)\in\mathbb{F}_{q^{m}}(x)$ is a rational function of
degree sum $n$ with some minor restrictions. Furthermore, for $q=7^{k}$,
$m\geq 7$ and rational functions with numerator and denominator being linear,
we explicitly find at most 6 fields in which the desired pair may not exist.

###### Key words and phrases:

Finite fields; Primitive elements; Normal elements; Additive and
multiplicative characters; Trace

###### 2020 Mathematics Subject Classification:

12E20, 11T23

The first author is supported by DST INSPIRE Fellowship, under grant no.
DST/INSPIRE Fellowship/2021/IF210206.

##  1\. Introduction

Throughout the article, let $q$ be a prime power and $m$ be a positive
integer. Denote by $\mathbb{F}_{q}$ the finite field of order $q$ and by
$\mathbb{F}_{q^{m}}$ the extension field of $\mathbb{F}_{q}$ of degree $m$.
The multiplicative group $\mathbb{F}_{q^{m}}^{*}$ is cyclic and a generator of
this group is called a primitive element of $\mathbb{F}_{q^{m}}^{*}$. An
element $\alpha\in\mathbb{F}_{q^{m}}$ is said to be normal over
$\mathbb{F}_{q}$ if the set of all its conjugates with respect to
$\mathbb{F}_{q}$, that is, the set
$\\{\alpha,\alpha^{q},\ldots,\alpha^{q^{m-1}}\\}$ forms a basis of
$\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$. An element
$\alpha\in\mathbb{F}_{q^{m}}$ is said to be a primitive normal if it is both
primitive and normal over $\mathbb{F}_{q}$.

Let $\alpha\in\mathbb{F}_{q^{m}}$, then
$\alpha,\alpha^{q},\ldots,\alpha^{q^{m-1}}$ are called the conjugates of
$\alpha$ over $\mathbb{F}_{q}$.The trace of an element
$\alpha\in\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, denoted by
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)$, is the sum of
all conjugates of $\alpha$ with respect to $\mathbb{F}_{q}$, that is,
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=\alpha+\alpha^{q}+\ldots+\alpha^{q^{m-1}}$.
The norm of an element $\alpha\in\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$,
denoted by $\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)$, is
the product of all the conjugates of $\alpha$ with respect to
$\mathbb{F}_{q}$, that is,
$\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=\alpha.\alpha^{q}\ldots\alpha^{q^{m-1}}=\alpha^{\frac{{q^{m}-1}}{q-1}}$.
We note that the trace of a normal element is a non-zero element and the norm
of a primitive element is a primitive element.

Primitive elements, besides their theoretical interest, have various
applications, including cryptographic schemes[11] such as Diffie-Hellmen key
exchange and Elgamel encryption schemes and the construction of Costas
arrays[7], which are used in sonar and radar technology. Normal elements hold
computational advantages for finite field arithmetic and are therefore used in
many software and hardware implementations in coding theory and cryptography.

For any $\alpha,\beta\in\mathbb{F}_{q^{m}}$, we call a pair $(\alpha,\beta)$
to be a primitive normal pair if both $\alpha$ and $\beta$ are primitive and
normal elements over $\mathbb{F}_{q}$. The existence of primitive normal pairs
$(\alpha,f(\alpha))$, where $f(x)$ is a function over $\mathbb{F}_{q^{m}}$
have been studied extensively and is a topic of great research interest. A
natural question is to ask whether there exists a primitive normal pair of
elements with prescribed trace and norm.

In 1999 and 2000, in a series of two papers [3, 4] Cohen and Hachenberger
proved the existence of primitive and normal elements of prescribed trace and
norm over finite fields. In 2001, Chou and Cohen [1] proved the existence of
an element $\alpha$ such that both $\alpha$ and $\alpha^{-1}$ have zero traces
over $\mathbb{F}_{q}$. In 2018, Gupta, Sharma and Cohen [8], proved the
existence of a primitive pair $(\alpha,\alpha+\alpha^{-1})$ with
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=a$, for any
prescribed $a\in\mathbb{F}_{q}$ and for all $q$ and $m\geq 5$. Recently,
Sharma, Rani and Tiwari [14] proved the existence of a primitive normal pair
$(\alpha,f(\alpha))$ where $f(x)\in\mathbb{F}_{q^{m}}[x]$ is a polynomial with
minor restrictions such that
$\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=a$ and
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=b$.

We impose a minor constraint on the form of the rational function
$f\in\mathbb{F}_{q^{m}}(x)$ so as to avoid some exceptional cases. We consider
rational functions $f\in\mathbb{F}_{q^{m}}(x)$ which belong to the set
$\mathfrak{R}_{n}$ as defined below.

######  Definition 1.1.

The set $\mathfrak{R}_{n}$ is the collection of rational functions
$f\in\mathbb{F}_{q^{m}}(x)$ with simplest form $f_{1}/f_{2}$, where
$n_{1},n_{2}$ are the degrees of $f_{1},f_{2}$ respectively, with
$n_{1}+n_{2}=n$ i.e. degree sum of $f$ is $n$, such that

  1. (i)

$f\neq cx^{i}g^{d}$ for some $c\in\mathbb{F}_{q^{m}}$, $i\in\mathbb{Z}$,
$g\in\mathbb{F}_{q^{m}}(x)$ and $d(>1)$ divides $q^{m}-1$.

  2. (ii)

$f_{2}$ is monic such that $f_{2}\neq g^{q^{m}}$ for any
$g\in\mathbb{F}_{q^{m}}[x]$.

We note that if $f(x)=g(x)^{t}$ for some $g\in\mathbb{F}_{q^{m}}(x)$ and $t>1$
which divides $q^{m}-1$, then $f(\alpha)$ (for any primitive element $\alpha$)
is necessarily a $t^{\text{th}}$ power and hence it cannot be primitive.
Furthermore, if $f(x)=cxg(x)^{2}$ where $c$ a non-square in $\mathbb{F}_{q}$.
Then, if $\alpha$ is primitive, $f(\alpha)$ is a square and so not necessarily
primitive. Also, part (ii) of the above definition forces that $n_{2}\geq 1$.
For the case $n_{2}=0$, i.e. for polynomials $f\in\mathbb{F}_{q^{m}}[x]$, the
existence of a primitive normal element $\alpha\in\mathbb{F}_{q^{m}}$ over
$\mathbb{F}_{q}$ such that $f(\alpha)$ is also a primitive normal element in
$\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$ with prescribed
$a\in\mathbb{F}_{q}$ has been studied in [14].

In this article we aim to classify finite fields $\mathbb{F}_{q^{m}}$ for
which there exists a primitive normal pair $(\alpha,f(\alpha))$ in
$\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$ such that
$\operatorname{N}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=a$ and
$\operatorname{Tr}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=b$ for any
prescribed primitive norm $a$ and a non-zero trace $b$ over $\mathbb{F}_{q}$,
where $f(x)\in\mathfrak{R}_{n}$. To be precise, in Section 3, we obtain a
sufficient condition for the existence of desired primitive normal pairs. In
Section 4, we use an "additive-multiplicative" sieve to weaken the sufficient
condition for more efficient results. In Section 5, we study the application
of our results over fields of chracteristic $7$ and for rational functions
whose degrees of numerator and denominator are $1$ and proved the following:

######  Theorem 1.1.

Let $q=7^{k}$, $m\geq 7$ and $f\in\mathfrak{R}_{n}$ such that
$(n_{1},n_{2})=(1,1)$. Then we have that, for any prescribed primitive norm
$a$ and a non-zero trace $b$ over $\mathbb{F}_{q}$, there exists an element
$\alpha\in\mathbb{F}_{q^{m}}$ with
$\operatorname{N}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=a$ and
$\operatorname{Tr}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=b$, for
which $(\alpha,f(\alpha))$ is a primitive normal pair in $\mathbb{F}_{q^{m}}$
over $\mathbb{F}_{q}$, except possibly the pairs $(7,7)$, $(7,8)$, $(7,9)$,
$(7,10)$, $(7,12)$ and $(7,18)$.

We introduce some notations and conventions which play an important role in
this article. For $q=p^{k}$, we denote by $\mathbb{F}$ the algebraic closure
of $\mathbb{F}_{p}$. Let $\mathfrak{Q}(n_{1},n_{2})$ denote the set of pairs
$(q,m)$ such that, for any prescribed primitive norm $a$ and a non-zero trace
$b$ over $\mathbb{F}_{q}$ and $f\in\mathfrak{R}_{n}$, there exists an element
$\alpha\in\mathbb{F}_{q^{m}}$ with
$\operatorname{N}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=a$ and
$\operatorname{Tr}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=b$, for
which $(\alpha,f(\alpha))$ is a primitive normal pair in $\mathbb{F}_{q^{m}}$
over $\mathbb{F}_{q}$. For each $n\in\mathbb{N}$, we denote by $\omega(n)$ and
$W(n)$, the number prime divisors of $n$ and the number of square-free
divisors of $n$ respectively. Also for $f(x)\in\mathbb{F}_{q}[x]$, we denote
by $\omega(f)$ and $W(f)$, the number of monic irreducible
$\mathbb{F}_{q}$-divisors of $f$ and the number of square-free
$\mathbb{F}_{q}$-divisors of $f$ respectively.

All non-trivial computations wherever needed in this article are carried out
using SageMath [13].

##  2\. Preliminaries

In this section, we recall some definitions and results and provide some
preliminary notations which are used to prove the main results of this
article.

In our work, the characteristic functions of primitive and normal elements
play an important role. To represent those functions, the idea of character of
finite abelian group is necessary.

Let $\mathbb{G}$ be a finite abelian group. A character $\chi$ of the group
$\mathbb{G}$ is a homomorphism from $\mathbb{G}$ to $\mathbb{S}^{1}$, where
$\mathbb{S}^{1}:=\\{z\in\mathbb{C}:|z|=1\\}$ is the multiplicative group of
complex numbers of unit modulus, i.e.
$\chi(a_{1}a_{2})=\chi(a_{1})\chi(a_{2})$, for all $a_{1},a_{2}\in\mathbb{G}$.

The characters of $\mathbb{G}$ form a group under multiplication defined by
$(\chi_{\alpha}\chi_{\beta})(a)=\chi_{\alpha}(a)\chi_{\beta}(a)$, called the
dual group or character group of $\mathbb{G}$ denoted by
$\widehat{\mathbb{G}}$, which in fact is isomorphic to the group $\mathbb{G}$.
If the order of an element (i.e. a character) of the group
$\widehat{\mathbb{G}}$ is $d$, then characters of order $d$ is denoted by
$(d)$. Further, since
$\widehat{\mathbb{F}^{*}_{q^{m}}}\cong\mathbb{F}^{*}_{q^{m}}$,
$\widehat{\mathbb{F}^{*}_{q^{m}}}$ is cyclic and for any divisor $d$ of
$q^{m}-1$ there are exactly $\phi(d)$ characters of order $d$ in
$\widehat{\mathbb{F}^{*}_{q^{m}}}$. The special character
$\chi_{0}:\mathbb{G}\rightarrow\mathbb{S}^{1}$ defined as $\chi_{0}(a)=1$, for
all $a\in\mathbb{G}$ is called the trivial character of $\mathbb{G}$.

In a finite field $\mathbb{F}_{q^{m}}$ there are two group structures, one is
the additive group $\mathbb{F}_{q^{m}}$ and the other is the multiplicative
group $\mathbb{F}^{*}_{q^{m}}$. Therefore we have two types of characters
pertaining to these two group structures, one is the additive character for
$\mathbb{F}_{q^{m}}$ denoted by $\psi$ and the other one is the multiplicative
character for $\mathbb{F}^{*}_{q^{m}}$ denoted by $\chi$. The multiplicative
characters associated with $\mathbb{F}^{*}_{q^{m}}$ are extended from
$\mathbb{F}^{*}_{q^{m}}$ to $\mathbb{F}_{q^{m}}$ by the rule

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

Let $e\mid q^{m}-1$, then an element $\alpha\in\mathbb{F}^{*}_{q^{m}}$ is
called $e$-free, if $d\mid e$ and $\alpha=y^{d}$, for some
$y\in\mathbb{F}^{*}_{q^{m}}$ imply $d=1$. It is clear from the definition that
an element $\alpha\in\mathbb{F}^{*}_{q^{m}}$ is primitive if and only if it is
a $(q^{m}-1)$-free element. The $p$-free part of a natural number $r$ is
denoted by $r_{0}$, where $r=r_{0}p^{k}$ such that $\mathrm{gcd}(r_{0},p)=1$.
It is clear from the definition that $q^{m}-1$ can be freely replaced by its
$p$-free part.

For any $e\mid q^{m}-1$, the characteristic function of $e$-free elements of
$\mathbb{F}^{*}_{q^{m}}$ is defined as follows:

(2.1)
$\rho_{e}:\mathbb{F}^{*}_{q^{m}}\rightarrow\\{0,1\\};\alpha\mapsto\theta(e)\sum_{d\mid
e}\left(\frac{\mu(d)}{\phi(d)}\sum_{(d)}\chi_{d}(\alpha)\right),$

where $\theta(e):=\phi(e)/e$, $\mu$ is the Möbius function and $\chi_{d}$
stands for any character of $\widehat{\mathbb{F}_{q^{m}}^{*}}$ of order $d$.

The additive group of $\mathbb{F}_{q^{m}}$ is an $\mathbb{F}_{q}[x]$-module
under the rule

$f\circ\alpha=\sum_{i=0}^{n}a_{i}\alpha^{q^{i}},$

for $\alpha\in\mathbb{F}_{q^{m}}$, where

$f(x)=\sum_{i=0}^{n}a_{i}x^{i}\thinspace\in\mathbb{F}_{q}[x]$

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

The _$\mathbb{F}_{q}$ -order_ of an additive character
$\chi_{g}\in\widehat{\mathbb{F}_{q^{m}}}$ is the monic
$\mathbb{F}_{q}$-divisor $g$ of $x^{m}-1$ of minimal degree such that
$\chi_{g}\circ g$ is the trivial character of $\widehat{\mathbb{F}_{q^{m}}}$,
where ($\chi_{g}\circ g)(\alpha)=\chi_{g}(g\circ\alpha)$ for any
$\alpha\in\mathbb{F}_{q^{m}}$.

For $g\mid x^{m}-1$, an element $\alpha\in\mathbb{F}_{q^{m}}$ is called
$g$-free element if $\alpha=h\circ\beta$ for some $\beta\in\mathbb{F}_{q^{m}}$
and $h\mid g$ imply $h=1$. From the definition, it is obvious that an element
$\alpha\in\mathbb{F}_{q^{m}}$ is normal if and only if it is $(x^{m}-1)$-free.
It is clear that $x^{m}-1$ can be freely replaced by its $p$-radical
$g_{0}:=x^{m_{0}}-1$, where $m_{0}$ is such that $m=m_{0}p^{a}$, here $a$ is a
non-negative integer and $\mathrm{gcd}(m_{0},p)=1$.

For any $g\mid x^{m}-1$, the characteristic function of $g$-free elements of
$\mathbb{F}_{q^{m}}$ is defined as follows:

(2.2)
$\kappa_{g}:\mathbb{F}_{q^{m}}\rightarrow\\{0,1\\};\alpha\mapsto\Theta(g)\sum_{f\mid
g}\left(\frac{\mu^{\prime}(f)}{\Phi(f)}\sum_{(f)}\psi_{f}(\alpha)\right),$

where $\Theta(g):=\Phi(g)/{q^{deg(g)}}$, $\psi_{f}$ stands for any character
of $\widehat{\mathbb{F}_{q^{m}}}$ of $\mathbb{F}_{q}$-order $f$ and
$\mu^{\prime}$ is the analogue of the Möbius function defined as follows:

$\mu^{\prime}(g)=\begin{cases}(-1)^{s},&\text{if $g$ is the product of $s$
distinct irreducible monic polynomials},\\\ 0,&\text{otherwise.}\\\
\end{cases}$

For each $b\in\mathbb{F}_{q}$, the characteristic function of the subset of
$\mathbb{F}_{q^{m}}$ consisting of elements $\alpha$ with
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=b$ is defined
as follows:

(2.3)
$\tau_{b}:\mathbb{F}_{q^{m}}\rightarrow\\{0,1\\};\alpha\mapsto\frac{1}{q}\sum_{\psi\in\widehat{\mathbb{F}_{q}}}\psi\left(\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)-b\right).$

The additive character $\psi_{1}$ defined by
$\psi_{1}(\beta)=e^{{2{\pi}i\text{Tr}(\beta)}/p}$, for all
$\beta\in\mathbb{F}_{q}$, where Tr is the absolute trace function from
$\mathbb{F}_{q}$ to $\mathbb{F}_{p}$, is called the _canonical additive
character_ of $\mathbb{F}_{q}$ and every additive character $\psi_{\beta}$ for
$\beta\in\mathbb{F}_{q}$ can be expressed in terms of the canonical additive
character $\psi_{1}$ as $\psi_{\beta}(\gamma)=\psi_{1}(\beta\gamma)$, for all
$\gamma\in\mathbb{F}_{q}$.

Thus we have that

$\displaystyle\tau_{b}(\alpha)$
$\displaystyle=\frac{1}{q}\sum_{u\in\mathbb{F}_{q}}\psi_{1}\left(\text{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(u\alpha)-ub\right)$
$\displaystyle=\frac{1}{q}\sum_{u\in\mathbb{F}_{q}}\widehat{\psi_{1}}(u\alpha)\psi_{1}(-ub),$

where $\widehat{\psi_{1}}$ is the lift of $\psi_{1}$, that is, the additive
character of $\mathbb{F}_{q^{m}}$ defined by
$\widehat{\psi_{1}}(\alpha)=\psi_{1}(\text{Tr}_{{\mathbb{F}_{q^{m}}}/\mathbb{F}_{q}}(\alpha))$.
In particular, $\widehat{\psi_{1}}$ is the canonical additive character of
$\mathbb{F}_{q^{m}}$.

For each $a\in\mathbb{F}_{q}^{*}$ the characteristic function of the subset of
$\mathbb{F}_{q^{m}}$ consisting of elements $\alpha$ with
$\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=a$ is defined as
follows:

(2.4)
$\eta_{a}:\mathbb{F}_{q^{m}}\rightarrow\\{0,1\\};\alpha\mapsto\frac{1}{q-1}\sum_{\chi\in\widehat{\mathbb{F}_{q}^{*}}}\chi\left(\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha).{a}^{-1}\right).$

The multiplicative group $\mathbb{F}_{q}^{*}$ is cyclic, so for any character
$\chi$ of $\mathbb{F}_{q}^{*}$ we can write
$\chi(\alpha)=\chi_{q-1}^{i}(\alpha)$ where $i\in\\{1,2,\ldots,q-1\\}$ and
$\chi_{q-1}$ is the multiplicative character of order $q-1$ in
$\widehat{\mathbb{F}_{q}^{*}}$. In particular we have that,

$\displaystyle\eta_{b}(\alpha)$
$\displaystyle=~{}\frac{1}{q-1}\sum_{\chi\in\widehat{\mathbb{F}_{q}^{*}}}\chi\left(\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha).{a}^{-1}\right)$
$\displaystyle=~{}\frac{1}{q-1}\sum_{i=1}^{q-1}\chi_{q-1}(a^{-i})\chi_{q-1}^{i}(\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha))$
$\displaystyle=~{}\frac{1}{q-1}\sum_{i=1}^{q-1}\chi_{q-1}(a^{-i})\widehat{\chi^{i}}(\alpha)$

where $\widehat{\chi}$ is the lift of $\chi_{q-1}$, that is, the
multiplicative character of $\mathbb{F}_{q^{m}}^{*}$ defined by
$\widehat{\chi}(\alpha)=\chi_{q-1}(\operatorname{N}_{{\mathbb{F}_{q^{m}}}/\mathbb{F}_{q}}(\alpha))$.
We observe that $\widehat{\chi}^{q-1}(\alpha)=1$. In fact, the order of
$\widehat{\chi}$ is $q-1$. To show this, let the order of $\widehat{\chi}$ be
$j<q-1$. Then for any $\alpha\in\mathbb{F}_{q^{m}}^{*}$, we have that
$\widehat{\chi}^{j}(\alpha)=1$ which implies
$\chi^{j}_{q-1}(\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha))=1$
which further implies $\chi^{j}_{q-1}(\gamma)=1$ for all
$\gamma\in\mathbb{F}_{q}^{*}$, since norm is an onto function. That is,
$(q-1)|j$, which is a contradiction.

The following results are due to Wan and Fu [6] and are crucial for proving
our sufficient condition.

######  Lemma 2.1.

[6, Theorem 5.5] Let $f(x)\in\mathbb{F}_{q^{m}}(x)$ be a rational function.
Write $f(x)=\prod_{j=1}^{k}f_{j}(x)^{r_{j}}$, where
$f_{j}(x)\in\mathbb{F}_{q^{m}}[x]$ are irreducible polynomials and $r_{j}$ are
non zero integers. Let $\chi$ be a non-trivial multiplicative character of
$\mathbb{F}_{q^{m}}$ of square-free order $d$ (a divisor of $q^{m}-1$).
Suppose that $f(x)$ is not of the form $cg(x)^{d}$ for any rational function
$g(x)\in\mathbb{F}_{q^{m}}(x)$ and $c\in\mathbb{F}^{*}_{q^{m}}$. Then we have

$\left|\sum_{\alpha\in\mathbb{F}_{q^{m}},f(\alpha)\neq
0,\infty}\chi(f(\alpha))\right|\leq\left({\sum_{j=1}^{k}deg(f_{j})}-1\right)q^{\frac{m}{2}}.$

######  Lemma 2.2.

[6, Theorem 5.6] Let $f(x),g(x)\in\mathbb{F}_{q^{m}}(x)$ be a rational
functions. Write $f(x)=\prod_{j=1}^{k}f_{j}(x)^{n_{j}}$, where
$f_{j}(x)\in\mathbb{F}_{q^{m}}[x]$ are irreducible polynomials and $n_{j}$ are
non zero integers. Let $D_{1}=\sum_{j=1}^{k}deg(f_{j})$,
$D_{2}=max(deg(g),0)$, $D_{3}$ be the degree of the denominator of $g(x)$, and
$D_{4}$ be the sum of degrees of those irreducible polynomials dividing the
denominator of $g$ but distinct from $f_{j}(x)(j=1,2,\ldots,k)$. Let $\chi$ be
a multiplicative character of $\mathbb{F}_{q^{m}}$, and let $\psi$ be a non
trivial additive character of $\mathbb{F}_{q^{m}}$. Suppose $g(x)$ is not of
the form $r(x)^{q^{m}}-r(x)$ in $\mathbb{F}_{q^{m}}(x)$. Then we have the
estimate

$\left|\sum_{\alpha\in\mathbb{F}_{q^{m}},f(\alpha)\neq 0,\infty;g(\alpha)\neq
0,\infty}\chi(f(\alpha))\psi(g(\alpha))\right|\leq(D_{1}+D_{2}+D_{3}+D_{4}-1)q^{\frac{m}{2}}.$

The following result provides an upper bound on the square-free divisors of
$x^{m}-1$.

######  Lemma 2.3.

[10, Lemma 2.9] Let $q$ be a prime power and $m$ a positive integer. Then, we
have $W(x^{m}-1)\leq 2^{\frac{1}{2}(m+\gcd(m,q-1))}$. In particular,
$W(x^{m}-1)\leq 2^{m}$ and $W(x^{m}-1)=2^{m}$ if and only if $m\mid(q-1)$.
Furthermore, $W(x^{m}-1)\leq 2^{3m/4}$ if $m\nmid(q-1)$, since in this case,
$\gcd(m,q-1)\leq\frac{m}{2}$.

##  3\. The Main Result

It is known to us that norm of a primitive element is also a primitive
element. In particular, for any $\alpha\in\mathbb{F}_{q^{m}}$ which is
$(q^{m}-1)$-free, its norm over $\mathbb{F}_{q}$ is $(q-1)$-free. The
following lemma is a generalization of the above fact done by Sharma et al. in
Lemma 3.1 of [14].

######  Lemma 3.1.

Let $l\mid(q^{m}-1),\sigma=\gcd(l,q-1)$, and $Q_{l}$ be the largest divisor of
$l$ such that $\gcd(Q_{l},\sigma)=1$. Then an element
$\alpha\in\mathbb{F}_{q^{m}}^{*}$ is $l$-free if and only if
$\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)$ is
$\sigma$-free in $\mathbb{F}_{q}^{*}$ and $\alpha$ is $Q_{l}$-free.

Let $e_{1},e_{2}$ be divisors of $q^{m}-1$, $\sigma=\gcd(e_{1},q-1)$ and
$Q_{e_{1}}$ be the largest divisor of $e_{1}$ such that
$\gcd(Q_{e_{1}},\sigma)=1$. From Lemma 3.1, if the norm of an element $\alpha$
is $\sigma$-free, then for $\alpha$ to be $e_{1}$-free, it suffices to show
that it is $Q_{e_{1}}$-free.

Furthermore, we know that trace of a normal element is non-zero. In fact, if
the trace of $\alpha$ is non-zero, then $\alpha$ is $(x-1)$-free. Let
$g_{1}(x),g_{2}(x)$ be divisors of $x^{m}-1$. Thus, for $\alpha$ to be
$g_{1}$-free, it suffices to show that it is $R_{g_{1}}$-free, where
$R_{g_{1}}$ is the largest divisor of $g_{1}$ co-prime to $(x-1)$.

For any rational function $f(x)\in\mathfrak{R}_{n}$, any $\sigma$-free element
$a\in\mathbb{F}_{q}^{*}$ and any non-zero element $b\in\mathbb{F}_{q}$, let
$\mathfrak{N}_{f,a,b}(Q_{e_{1}},e_{2},R_{g_{1}},g_{2})$ denote the number of
elements $\alpha\in\mathbb{F}_{q^{m}}$ such that $\alpha$ is $Q_{e_{1}}$ and
$R_{g_{1}}$-free, $f(\alpha)$ is $e_{2}$ and $g_{2}$-free, and
$\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=a$ and
$\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)=b$.

In this section we present a sufficient condition for the existence of a
primitive normal pair $(\alpha,f(\alpha))$ in $\mathbb{F}_{q^{m}}$ over
$\mathbb{F}_{q}$ such that
$\operatorname{N}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=a$ and
$\operatorname{Tr}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=b$ for any
prescribed primitive norm $a$ and a non-zero trace $b$ over $\mathbb{F}_{q}$,
where $f(x)\in\mathfrak{R}_{n}$. From the discussion above, it is equivalent
to determining when $\mathfrak{N}_{f,a,b}(Q_{e_{1}},e_{2},R_{g_{1}},g_{2})>0$.

Let $P$ be the set containing $0$, and the zeros and poles of $f$. From the
definition we have,

$\mathfrak{N}_{f,a,b}(Q_{e_{1}},e_{2},R_{g_{1}},g_{2})=\sum_{\alpha\in\mathbb{F}_{q^{m}}\setminus
P}\rho_{Q_{e_{1}}}(\alpha)\rho_{e_{2}}(f(\alpha))\kappa_{R_{g_{1}}}(\alpha)\kappa_{g_{2}}(f(\alpha))\eta_{a}(\alpha)\tau_{b}(\alpha)$

Then using the characteristic functions 2.1, 2.2, 2.3 and 2.4 we have the
following expression,

$\displaystyle\mathfrak{N}_{f,a,b}(Q_{e_{1}},e_{2},R_{g_{1}},g_{2})=$
$\displaystyle~{}\frac{\theta(Q_{e_{1}})\theta(e_{2})\Theta(R_{g_{1}})\Theta(g_{2})}{q(q-1)}\sum_{\begin{subarray}{c}d_{1}\mid
Q_{e_{1}},d_{2}\mid e_{2}\\\ h_{1}\mid R_{g_{1}},h_{2}\mid
g_{2}\end{subarray}}\frac{\mu(d_{1})\mu(d_{2})\mu^{\prime}(h_{1})\mu^{\prime}(h_{2})}{\phi(d_{1})\phi(d_{2})\Phi(h_{1})\Phi(h_{2})}$
$\displaystyle~{}\sum_{\begin{subarray}{c}\chi_{d_{1}},\chi_{d_{2}}\\\
\psi_{h_{1}},\psi_{h_{2}}\end{subarray}}\chi_{f,a,b}(d_{1},d_{2},h_{1},h_{2})$
(3.1) $\displaystyle=$
$\displaystyle~{}\vartheta\sum_{\begin{subarray}{c}d_{1}\mid e_{1},d_{2}\mid
e_{2}\\\ h_{1}\mid g_{1},h_{2}\mid
g_{2}\end{subarray}}\frac{\mu(d_{1})\mu(d_{2})\mu^{\prime}(h_{1})\mu^{\prime}(h_{2})}{\phi(d_{1})\phi(d_{2})\Phi(h_{1})\Phi(h_{2})}\sum_{\begin{subarray}{c}\chi_{d_{1}},\chi_{d_{2}}\\\
\psi_{h_{1}},\psi_{h_{2}}\end{subarray}}\chi_{f,a,b}(d_{1},d_{2},h_{1},h_{2}),$

where

$\vartheta=\frac{\theta(Q_{e_{1}})\theta(e_{2})\Theta(R_{g_{1}})\Theta(g_{2})}{q(q-1)}$

and

$\displaystyle\chi_{f,a,b}(d_{1},d_{2},h_{1},h_{2})=$
$\displaystyle~{}\sum_{\chi\in\widehat{\mathbb{F}_{q}^{*}}}\sum_{\psi\in\widehat{\mathbb{F}_{q}}}\sum_{\alpha\in\mathbb{F}_{q^{m}}\setminus
P}\chi_{d_{1}}(\alpha).\chi_{d_{2}}(f(\alpha)).\psi_{g_{1}}(\alpha).\psi_{g_{2}}(f(\alpha)).$
$\displaystyle~{}\chi(\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha).{a^{-1}}).\psi(\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)-b)$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{q-1}\sum_{c\in\mathbb{F}_{q}}\chi_{q-1}(a^{-i})\psi_{1}(-cb)\sum_{\alpha\in\mathbb{F}_{q^{m}}\setminus
P}\chi_{d_{1}}(\alpha).\chi_{d_{2}}(f(\alpha)).\psi_{g_{1}}(\alpha).\psi_{g_{2}}(f(\alpha)).$
$\displaystyle~{}\chi_{q-1}^{i}(\operatorname{N}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha)).\psi_{1}(c\operatorname{Tr}_{\mathbb{F}_{q^{m}}/\mathbb{F}_{q}}(\alpha))$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{q-1}\sum_{c\in\mathbb{F}_{q}}\chi_{q-1}(a^{-i})\psi_{1}(-cb)\sum_{\alpha\in\mathbb{F}_{q^{m}}\setminus
P}\chi_{d_{1}}(\alpha).\chi_{d_{2}}(f(\alpha)).\psi_{g_{1}}(\alpha).\psi_{g_{2}}(f(\alpha)).$
$\displaystyle~{}\widehat{\chi^{i}}(\alpha).\widehat{\psi_{1}}(c\alpha).$

where, as seen earlier, $\widehat{\chi}$ and $\widehat{\psi_{1}}$ are lifts of
$\chi_{q-1}$ and $\psi_{1}$ to $\mathbb{F}_{q^{m}}^{*}$ and
$\mathbb{F}_{q^{m}}$ respectively.

Since, $\widehat{\mathbb{F}}^{*}_{q^{m}}$ is a cyclic group, we can write
$\widehat{\chi}=\chi_{q^{m}-1}^{(q^{m}-1)/(q-1)}$ as the order of
$\widehat{\chi}$ is ${q-1}$ as seen earlier. Also, we can write
$\chi_{d_{i}}(\alpha)=\chi_{q^{m}-1}(\alpha^{n_{i}})$ for some
$n_{i}\in\\{0,1,2,\ldots,q^{m}-2\\};i=1,2$. Furthermore, there exist
$u_{1},u_{2}\in\mathbb{F}_{q^{m}}$ such that
$\psi_{g_{i}}(\alpha)=\widehat{\psi}_{1}(u_{i}\alpha)$, for $i=1,2$, where
$\widehat{\psi}_{1}$ is the canonical additive character of
$\mathbb{F}_{q^{m}}$. Then we have the following expression,

$\displaystyle\chi_{f,a,b}(d_{1},d_{2},h_{1},h_{2})=$
$\displaystyle~{}\sum_{i=1}^{q-1}\sum_{c\in\mathbb{F}_{q}}\chi_{q-1}(a^{-i})\psi_{1}(-cb)\sum_{\alpha\in\mathbb{F}_{q^{m}}\setminus
P}\chi_{q^{m}-1}(\alpha^{n_{1}+\frac{(q^{m}-1)i}{q-1}}f(\alpha)^{n_{2}})$
(3.2) $\displaystyle~{}\widehat{\psi_{1}}((u_{1}+c)\alpha+u_{2}f(\alpha))$
$\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{q-1}\sum_{c\in\mathbb{F}_{q}}\chi_{q-1}(a^{-i})\psi_{1}(-cb)\sum_{\alpha\in\mathbb{F}_{q^{m}}\setminus
P}\chi_{q^{m}-1}(H_{i}(\alpha))\widehat{\psi_{1}}(T_{c}(\alpha)),$

where $H_{i}(x)=x^{n_{1}+\frac{(q^{m}-1)i}{q-1}}f(x)^{n_{2}}$; for
$i=1,\ldots,q-1$ and $T_{c}(x)=(u_{1}+c)x+u_{2}f(x);c\in\mathbb{F}_{q}$.

Next, suppose that $H_{i}(x)\neq y.R(x)^{q^{m}-1}$ or $T_{c}(x)\neq
R^{q^{m}}-R(x)$ for any $y\in\mathbb{F}_{q^{m}}^{*}$ and any
$R(x)\in\mathbb{F}(x)$, where $\mathbb{F}$ is the algebraic closure of
$\mathbb{F}_{q^{m}}$, then from Lemma 2.1 and 2.2 we have the following,

(3.3)
$|\chi_{f,a,b}(d_{1},d_{2},h_{1},h_{2})|\leq\mathfrak{M}.(q-1).q^{\frac{m}{2}+1},$

where

$\mathfrak{M}=\begin{cases}2n_{1}+n_{2},&\text{if }n_{1}>n_{2},\\\
n_{1}+2n_{2}+1,&\text{if }n_{1}\leq n_{2}.\end{cases}$

Claim: If $H_{i}(x)=y.R(x)^{q^{m}-1}$ and $T_{c}(x)=R(x)^{q^{m}}-R(x)$ for
some $y\in\mathbb{F}_{q^{m}}^{*}$ and some $R(x)\in\mathbb{F}(x)$, then we
have $(d_{1},d_{2},h_{1},h_{2})=(0,0,0,0)$.

Proof of the claim: Suppose that $H_{i}(x)=y.R(x)^{q^{m}-1}$ for some
$y\in\mathbb{F}_{q^{m}}^{*}$ and some $R(x)\in\mathbb{F}(x)$. Write
$f=\frac{f_{1}}{f_{2}}$ and $R(x)=\frac{r_{1}}{r_{2}}$ where $f_{1},f_{2}$ are
co-prime polynomials over $\mathbb{F}_{q^{m}}$, $r_{1},r_{2}$ are co-prime
polynomials over $\mathbb{F}$ and $f_{2},r_{2}$ are both monic. Then we have
the following expression,

(3.4)
$x^{n_{1}+\frac{(q^{m}-1)i}{q-1}}.f_{1}^{n_{2}}.r_{2}^{q^{m}-1}=y.r_{1}^{q^{m}-1}.f_{2}^{n_{2}}$

Next write $f_{1}=\prod_{i=1}^{t}f_{1i}^{s_{i}}$ be the decomposition of
$f_{1}$ into irreducible polynomials over $\mathbb{F}_{q^{m}}$, where
$s_{i}$’s are positive integers. Since $\mathbb{F}$ is the algebraic closure
of $\mathbb{F}_{q^{m}}$, $f_{1i}$ completely reduces into distinct linear
factors over $\mathbb{F}$. From Equation 3.4, we have that, each $f_{1i}$
divides $r_{1}$ over $\mathbb{F}$, since $\gcd(f_{1},f_{2})=1$. Thus, $f_{1i}$
divides $r_{1}$ over $\mathbb{F}$ for all $i=1,2,\ldots,t$. By comparing the
degrees of the factors $f_{1i}^{s_{i}n_{2}}$ on both sides of the Equation 3.4
over $\mathbb{F}$, we get $s_{i}.n_{2}=k_{i}.(q^{m}-1)$, where $k_{i}$ is the
multiplicity of $f_{1i}$ in the factorization of $R(x)$. This implies that
$s\mid s_{i}$, where $s=\frac{q^{m}-1}{\gcd(q^{m}-1,n_{2})}$. Therefore,
$f_{1}=(f^{\prime}_{1})^{s}$ for some polynomial
$f^{\prime}_{1}(x)\in\mathbb{F}_{q^{m}}[x]$. In a similar manner,
$f_{2}=(f^{\prime}_{2})^{s}$ for some polynomial
$f^{\prime}_{2}(x)\in\mathbb{F}_{q^{m}}[x]$. Thus, we have that
$f=\frac{f_{1}}{f_{2}}=(\frac{f^{\prime}_{1}}{f^{\prime}_{2}})^{s}$, where
$s\mid(q^{m}-1)$ and $f\in\mathfrak{R}_{n}$. This further implies that $s=1$,
i.e., $\gcd(q^{m}-1,n_{2})=q^{m}-1$, i.e., $(q^{m}-1)\mid n_{2}$, which
implies $n_{2}=0$.

Now, Equation 3.4 becomes,

$x^{n_{1}+\frac{(q^{m}-1)i}{q-1}}=y.R(x)^{q^{m}-1}$

From the above expression, it can be clearly seen that $R(x)=x^{k}$ for some
positive integer $k$ and comparing the degrees on both sides we get

$n_{1}+\frac{(q^{m}-1)i}{q-1}=k(q^{m}-1)$

This implies that,

$n_{1}=(k-\frac{i}{q-1})(q^{m}-1)\geq(k-1)(q^{m}-1)$

which is impossible unless $k=1$, as $0\leq n_{1}\leq q^{m}-2$. Thus,
$n_{1}=(1-\frac{i}{q-1})(q^{m}-1)$. Since,
$\chi_{d_{1}}=\chi_{q^{m}-1}^{n_{1}}$, there exists some positive integer $u$
such that $n_{1}=\frac{(q^{m}-1)u}{d_{1}}$. Substituting the value of $n_{1}$
we get

$\frac{(q^{m}-1)u}{d_{1}}=(1-\frac{i}{q-1})(q^{m}-1)$

This implies $u(q-1)=(q-1-i)d_{1}$ which further implies $d_{1}|u$, since
$\gcd(d_{1},q-1)=1$. Therefore, $q^{m}-1\mid n_{1}$, which is possible only if
$n_{1}=0$. Hence, $n_{1}=n_{2}=0$, that is $d_{1}=d_{2}=0$.

Secondly, for $c\in\mathbb{F}_{q}$, suppose $T_{c}(x)=R(x)^{q^{m}}-R(x)$ for
some $R(x)\in\mathbb{F}(x)$. Write $f=\frac{f_{1}}{f_{2}}$ and
$R=\frac{r_{1}}{r_{2}}$, where $f_{1},f_{2}\in\mathbb{F}_{q^{m}}[x]$ and
$r_{1},r_{2}\in\mathbb{F}[x]$ , such that $\gcd(f_{1},f_{2})=1$ and
$\gcd(r_{1},r_{2})=1$, then we have

(3.5)
$r_{2}^{q^{m}}[f_{2}(u_{1}+c)+u_{2}f_{1}]=f_{2}[r_{1}^{q^{m}}-r_{1}.r_{2}^{q^{m}-1}]$

Suppose at least one of $u_{1}$ or $u_{2}$ is non-zero. If $u_{2}\neq 0$, then
$f_{2}=r_{2}^{q^{m}}$, since $\gcd(f_{1},f_{2})=1$ and $\gcd(r_{1},r_{2})=1$.
From the second part of the definition of the set $\mathfrak{R}_{n}$, we know
that there exists a monic irreducible factor $h\in\mathbb{F}_{q^{m}}[x]$ of
$f_{2}$ with multiplicity $t$ such that $q^{m}\nmid t$. By comparing degrees
of $h$ on both sides of the expression $f_{2}=r_{2}^{q^{m}}$ over
$\mathbb{F}$, we get that $t=s.q^{m}$, where $s$ is such that $g^{s}\mid\mid
r_{2}$, that is, $s$ is the highest power of $g$ that divides $r_{2}$. This is
clearly not possible since $q^{m}\nmid t$. Therefore $u_{2}=0$, and Equation
3.5 becomes,

$(u_{1}+c)x.r_{2}^{q^{m}}=r_{1}^{q^{m}}-r_{1}.r_{2}^{q^{m}-1}$

Since $\gcd(r_{1},r_{2})=1$, the above expression implies that $r_{2}$ is a
non-zero constant polynomial and the above Equation becomes
$Cx=r_{1}^{q^{m}}-r_{1}.r_{2}^{q^{m}-1}$, where
$C=(u_{1}+c).r_{2}^{q^{m}}\in\mathbb{F}$. Therefore, this implies that
$(u_{1}+c)=0$, since else $\deg(r_{1}).q^{m}=1$. We observe that
$\psi_{g_{1}}(g_{1}(\alpha))=1$ which implies
$\widehat{\psi_{1}}(u_{1}.g_{1}(\alpha))=1$. Thus, if $u_{1}+c=0$, then
$\widehat{\psi_{1}}(u_{1}.g_{1}(\alpha))=1$, which implies
$\widehat{\psi_{1}}((-c).g_{1}(\alpha))=1$. Since $c\in\mathbb{F}_{q}$ and
$x^{m}-1$ is the $\mathbb{F}_{q}$-order of $\widehat{\psi_{1}}$, we have
$(x^{m}-1)\mid c.g_{1}$, which further implies $c=0$, that is $u_{1}=0$.
Hence, $u_{1}=u_{2}=0$ that is $h_{1}=h_{2}=0$.

The following lemma deals with the case when
$(d_{1},d_{2},h_{1},h_{2})=(0,0,0,0)$.

######  Lemma 3.2.

If $(d_{1},d_{2},h_{1},h_{2})=(0,0,0,0)$, then

$|\chi_{f,a,b}(0,0,0,0)-(q^{m}-|P|)|\leq(q-2)(|P|-1)+(q-1)^{2}.q^{\frac{m}{2}}$

###### Proof.

The proof is similar to Lemma 3.3 of [14], hence omitted. ∎

Now, from Equation 3.3 and the claim above we have that,

$|\chi_{f,a,b}(d_{1},d_{2},h_{1},h_{2})|\leq\mathfrak{M}.(q-1).q^{\frac{m}{2}+1}$

unless $(d_{1},d_{2},h_{1},h_{2})=(0,0,0,0)$. Furthermore, from Lemma 3.2 we
have

$\displaystyle|\chi_{f,a,b}(0,0,0,0)-(q^{m}-|P|)|\leq$
$\displaystyle~{}(q-2)(|P|-1)+(q-1)^{2}.q^{\frac{m}{2}}$ $\displaystyle\geq$
$\displaystyle~{}(q^{m}-|P|)-(q-2)(|P|-1)-(q-1)^{2}.q^{\frac{m}{2}}$
$\displaystyle\geq$
$\displaystyle~{}q^{m}-(q-1)(|P|-1)-(q-1)^{2}.q^{\frac{m}{2}}$
$\displaystyle\geq$ $\displaystyle~{}q^{m}-(q-1).n-(q-1)^{2}.q^{\frac{m}{2}}.$

Therefore, from Equation 3, we get

$\displaystyle\mathfrak{N}_{f,a,b}(Q_{e_{1}},e_{2},R_{g_{1}},g_{2})>$
$\displaystyle\vartheta\\{q^{m}-(q-1)\\{n+(q-1)q^{\frac{m}{2}}+\mathfrak{M}.q^{\frac{m}{2}+1}(W(Q_{e_{1}}).W(e_{2}).W(R_{g_{1}})W(g_{2})-1))\\}\\}$
$\displaystyle>$
$\displaystyle\vartheta\\{q^{m}-\mathfrak{M}.q^{\frac{m}{2}+1}(q-1)W(Q_{e_{1}}).W(e_{2}).W(R_{g_{1}})W(g_{2})\\}$
$\displaystyle>$
$\displaystyle\vartheta\\{q^{m}-\mathfrak{M}.q^{\frac{m}{2}+2}W(Q_{e_{1}}).W(e_{2}).W(R_{g_{1}})W(g_{2})\\}$

Hence $\mathfrak{N}_{f,a,b}(Q_{e_{1}},e_{2},R_{g_{1}},g_{2})>0$ provided
$q^{\frac{m}{2}-2}>\mathfrak{M}.W(Q_{e_{1}}).W(e_{2}).W(R_{g_{1}})W(g_{2})$,
where

$\mathfrak{M}=\begin{cases}2n_{1}+n_{2},&\text{if }n_{1}>n_{2},\\\
n_{1}+2n_{2}+1,&\text{if }n_{1}\leq n_{2}.\end{cases}$

Summarizing the discussion above we arrive at the following result.

######  Theorem 3.3.

Let $q$ be a prime power and $m,n\in\mathbb{N}$ such that $m\geq 5$. Suppose
$e_{1},e_{2}$ divide $q^{m}-1$ and $g_{1},g_{2}$ divide $x^{m}-1$. Then we
have

$\mathfrak{N}_{f,a,b}(Q_{e_{1}},e_{2},R_{g_{1}},g_{2})>\vartheta\\{q^{m}-\mathfrak{M}.q^{\frac{m}{2}+2}W(Q_{e_{1}}).W(e_{2}).W(R_{g_{1}})W(g_{2}).$

In particular, we have $(q,m)\in\mathfrak{Q}(n_{1},n_{2})$ provided that

(3.6)
$q^{\frac{m}{2}-2}>\mathfrak{M}.W(Q_{e_{1}}).W(e_{2}).W(R_{g_{1}})W(g_{2}),$

where

$\mathfrak{M}=\begin{cases}2n_{1}+n_{2},&\text{if }n_{1}>n_{2},\\\
n_{1}+2n_{2}+1,&\text{if }n_{1}\leq n_{2}.\end{cases}$

It is clear from the above discussion that
$(q,m)\in\mathfrak{Q}(n_{1},n_{2})$, when $e_{1}=e_{2}=q^{m}-1$ and
$g_{1}=g_{2}=x^{m}-1$, that is provided

(3.7)
$q^{\frac{m}{2}-2}>\mathfrak{M}.W(Q_{q^{m}-1}).W(q^{m}-1)W(R_{x^{m}-1}).W(x^{m}-1),$

where

$\mathfrak{M}=\begin{cases}2n_{1}+n_{2},&\text{if }n_{1}>n_{2},\\\
n_{1}+2n_{2}+1,&\text{if }n_{1}\leq n_{2}.\end{cases}$

Here $Q_{q^{m}-1}$ is the largest divisor of $q^{m}-1$ such that
$\gcd(Q_{q^{m}-1},q-1)=1$. In particular,
$Q_{q^{m}-1}=\frac{q^{m}-1}{(q-1)\gcd(m,q-1)}$ and $W(Q_{q^{m}-1})\leq
W(q^{m}-1)$. Similarly, $R_{x^{m}-1}$ is the largest divisor of $x^{m}-1$ such
that $\gcd(R_{x^{m}-1},x-1)=1$. Furthermore, $W(R_{x^{m}-1})=W(x^{m}-1)/2$.

##  4\. Sieving Inequality

For our problem we use the "additive-multiplicative" sieve that involves
sieving with respect to the primes in $q^{m}-1$ as well as the irreducible
factors in $x^{m}-1$. We apply the sieving inequality established by
Kapetanakis in [9] to give a modified form of (3.6), in order to study the
pairs $(q,m)$ which do not satisfy the condition (3.6).

######  Lemma 4.1 (Sieving Inequality).

Let $d^{\prime}$ be a divisor of $Q_{q^{m}-1}$ and
$p^{\prime}_{1},p^{\prime}_{2},\dots,p^{\prime}_{r}$ be the remaining distinct
primes dividing $Q_{q^{m}-1}$; let $d$ be a divisor of $q^{m}-1$ and
$p_{1},p_{2},\dots,p_{s}$ be the remaining distinct primes dividing $q^{m}-1$.
Furthermore, let $g^{\prime}$ be a divisor of $R_{x^{m}-1}$ and
$g^{\prime}_{1},g^{\prime}_{2},\dots,g^{\prime}_{t}$ be the remaining distinct
irreducible factors of $R_{x^{m}-1}$; let $g$ be a divisor of $x^{m}-1$ and
$g_{1},g_{2},\dots,g_{u}$ be the remaining distinct irreducible factors of
$x^{m}-1$. Abbreviate
$\mathfrak{N}_{f,a,b}(Q_{q^{m}-1},q^{m}-1,R_{x^{m}-1},x^{m}-1)$ to
$\mathfrak{N}_{f,a,b}$. Then

(4.1)
$\mathfrak{N}_{f,a,b}\geq\sum_{i=1}^{r}\mathfrak{N}_{f,a,b}(p^{\prime}_{i}d^{\prime},d,g^{\prime},g)+\sum_{i=1}^{s}\mathfrak{N}_{f,a,b}(d^{\prime},p_{i}d,g^{\prime},g)+\sum_{i=1}^{t}\mathfrak{N}_{f,a,b}(d^{\prime},d,g^{\prime}_{i}g^{\prime},g)\\\
+\sum_{i=1}^{u}\mathfrak{N}_{f,a,b}(d^{\prime},d,g^{\prime},g_{i}g)-(r+s+t+u-1)\mathfrak{N}_{f,a,b}(d^{\prime},d,g^{\prime},g).$

######  Theorem 4.2.

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

$\lambda:=1-\sum_{i=1}^{r}\frac{1}{p^{\prime}_{i}}-\sum_{i=1}^{s}\frac{1}{p_{i}}-\sum_{i=1}^{t}\frac{1}{q^{{\mathrm{d}eg}(g^{\prime}_{i})}}-\sum_{i=1}^{u}\frac{1}{q^{{\mathrm{d}eg}(g_{i})}},\
$

and

$\Lambda:=\frac{r+s+t+u-1}{\lambda}+2.$

Suppose $\lambda>0$, then $\mathfrak{N}_{f,a,b}>0$ if

(4.2)
$q^{\frac{m}{2}-2}>\mathfrak{M}.W(d^{\prime})W(d)W(g^{\prime})W(g)\Lambda,$

where

$\mathfrak{M}=\begin{cases}2n_{1}+n_{2},&\text{if }n_{1}>n_{2},\\\
n_{1}+2n_{2}+1,&\text{if }n_{1}\leq n_{2}.\end{cases}$

###### Proof.

The proof is similar to Proposition 5.3 of [9], hence omitted. ∎

##  5\. Computational Results

The above discussed results hold for any finite field $\mathbb{F}_{q^{m}}$ of
any prime characteristic and for any arbitrary natural number $n$. In order to
make computations less tedious and illustrate how the aforementioned results
can be applied, we assume that $q=7^{k}$ where $k$ is a positive integer and
$(n_{1},n_{2})=(1,1)$, that is, $n=n_{1}+n_{2}=2$.

We use the concept of the $7$-free part of $m$ i.e. $m^{\prime}$, where
$m^{\prime}$ is such that $m=7^{k}m^{\prime}$, such that
$\gcd(7,m^{\prime})=1$ and $k$ is a non-negative integer. We then have that
$\omega(x^{m}-1)=\omega(x^{m^{\prime}}-1)$ which implies
$W(x^{m}-1)=W(x^{m^{\prime}}-1)$.

We shall need the following lemma which can be derived from Lemma 6.2 of
Cohen’s work [2].

######  Lemma 5.1.

Let $M$ be a positive integer, then

  1. (i)

$W(M)<244.66\times M^{1/7}$.

  2. (ii)

$W(M)<1.11\times 10^{9}\times M^{1/10}$.

  3. (iii)

$W(M)<5.09811\times 10^{67}\times M^{1/14}$.

When $q=7^{k}$ and $m=6$, we observe that $x^{6}-1$ factors into a product of
six linear factors. Then using Lemma 5.1, $(q,m)$ $\in$ $Q(1,1)$ if
$q^{1/7}>4\cdot 2^{11}\cdot(5.09811\times 10^{67})^{2}$, which implies
$q>1.984\times 10^{975}$, that is the case $k\geq 1155$ is settled. Similarly,
when $m=5$, we get that $(q,m)$ $\in$ $Q(1,1)$ if $q>1.026\times 10^{269771}$
which implies $k\geq 319219$, is hence settled. To treat the remaining cases
it requires huge computational resources. Thus, moving forward, we shall
assume that $m\geq 7$.

Next we divide our discussion into cases depending on the nature of factors of
$x^{m^{\prime}}-1$.

###  5.1. Values of $m$ such that $m^{\prime}$ divides $q-1$.

When $m^{\prime}\mid q-1$, then $x^{m^{\prime}}-1$ splits into a product of
$m^{\prime}$ linear factors over $\mathbb{F}_{q}$. Let
$d^{\prime}=Q_{q^{m}-1}$, $d=q^{m}-1$, $g^{\prime}=1$ and $g=1$ in Theorem
4.2, then $\Lambda=\frac{2q^{2}+2a-6q+4}{(a-2)q+a+2}$, where
$a=\frac{q-1}{m^{\prime}}$. In particular, $\Lambda<2q^{2}$. Thus,
$(q,m)\in\mathfrak{Q}(1,1)$ if $q^{\frac{m}{2}-4}>8.W(q^{m}-1)^{2}$. Applying
Lemma 5.1, it is sufficient if $q^{\frac{3m}{14}-4}>8.(244.66)^{2}$. This
inequality holds for $q\geq 49$ and for all $m\geq 35$. In particular, for
$q\geq 49$ and $m^{\prime}\geq 35$.

Next, we investigate all cases with $m^{\prime}\leq 34$. For this, we set
$d^{\prime}=Q_{q^{m}-1}$, $d=q^{m}-1$, $g^{\prime}=1$ and $g=1$ in Theorem 4.2
unless otherwise mentioned. Here $\lambda=1-\frac{2m^{\prime}-1}{q}$ and
$\Lambda=2+\frac{2q(m^{\prime}-1)}{q-2m^{\prime}+1}$.

####  5.1.1. $m^{\prime}=1$

In this case $m=7^{j}$ for some positive integer $j$ and $\Lambda=2$. Then by
Theorem 4.2, it is sufficient if $q^{\frac{m}{2}-2}>8\cdot W(q^{m}-1)^{2}$.
Using Lemma 5.1, the above becomes $q^{3\cdot 7^{j}/10-2}>8\cdot(1.11\times
10^{9})^{2}$. This holds for $q=7$ for all $j\geq 3$. For $7^{2}\leq q\leq
7^{224}$ for all $j\geq 2$ and for $q\geq 7^{225}$ for all $j\geq 1$. For the
above $225$ pairs we checked $q^{\frac{m}{2}-2}>8\cdot W(q^{m}-1)^{2}$ by
factoring $q^{m}-1$ directly and get that all except the pairs
$(7,7),(7^{2},7),(7^{3},7)$ and $(7^{4},7)$ satisfy the condition.

####  5.1.2. $m^{\prime}=2$

Here $m=2\cdot 7^{j}$ for some positive integer $j$ and
$\Lambda=2+\frac{2q}{q-3}<6$. Now by Theorem 4.2 and Lemma 5.1, it suffices to
see that $q^{3\cdot(2\cdot 7^{j})/14-2}>24\cdot(244.66)^{2}$. The above
inequality holds for $7\geq q\geq 7^{8}$ for all $j\geq 2$ and for $q\geq
7^{8}$; this holds for all $j\geq 1$. Proceeding in a similar way and
verifying the condition $q^{\frac{m}{2}-2}>24\cdot W(q^{m}-1)^{2}$ for the
above seven pairs, we get that $(7,14)$ fails to satisfy the condition.

####  5.1.3. $3\leq m^{\prime}\leq 34$

Proceeding in a similar fashion for the cases $3\leq m^{\prime}\leq 34$, we
find that there is no exceptional pair for the aforementioned cases.

Now, for the above possible exceptional pairs we choose suitable values of
$d^{\prime}$, $d$, $g^{\prime}$ and $g$ such that all the pairs satisfy
Theorem 4.2 (see Table 1) except the pair $(7,7)$. Therefore, there is one
exceptional pair for the case $m^{\prime}\mid q-1$.

# | $(q,m)$ | $d^{\prime}$ | $d$ | $g^{\prime}$ | $g$ | $\lambda>$ | $\Lambda<$
---|---|---|---|---|---|---|---
1 | $(7^{2},7)$ | 29 | 2 | 1 | 1 | 0.591458675085391 | 15.5258815822509
2 | $(7^{3},7)$ | 1 | 2 | 1 | 1 | 0.541731553445425 | 16.7674617605709
3 | $(7^{4},7)$ | 1 | 2 | 1 | 1 | 0.376967586454699 | 33.8329756488017
4 | $(7,14)$ | 2 | 2 | $(x+1)$ | $(x-1)$ | 0.434526936872864 | 22.7121796976956
Table 1. Pairs $(q,m)$ with $m^{\prime}\mid q-1$ for which Theorem 4.2 holds
for the above choices of $d^{\prime}$, $d$, $g^{\prime}$ and $g$.

###  5.2. Values of $m$ such that $m^{\prime}$ does not divide $q-1$.

Given $q$ and $m$, let $u$ be the order of $q$ mod $m^{\prime}$. Then
$x^{m^{\prime}}-1$ is a product of irreducible polynomial factors of degree
less than or equal to $u$ in $\mathbb{F}_{q}[x]$; in particular, $u\geq 2$ if
$m^{\prime}\nmid q-1$. Let $M$ be the number of distinct irreducible factors
of $x^{m}-1$ over $\mathbb{F}_{q}$ of degree less than $u$. Let $\sigma(q,m)$
denotes the ratio

$\sigma(q,m):=\frac{M}{m},$

where $m\sigma(q,m)=m^{\prime}\sigma(q,m^{\prime})$.

We need the following bounds which can be deduced from Proposition 5.3 of [5].

######  Lemma 5.2.

Suppose $q=7^{k}$, $m^{\prime}>4$ and $m_{1}=\gcd(q-1,m^{\prime})$

  1. (i)

If $m^{\prime}=2m_{1}$ and $q$ odd, then $u=2$ and $\sigma(q,m^{\prime})=1/2$.

  2. (ii)

If $m^{\prime}=4m_{1}$ and $q\equiv 1\pmod{4}$, then $u=4$ and
$\sigma(q,m^{\prime})=3/8$.

  3. (iii)

If $m^{\prime}=6m_{1}$ and $q\equiv 1\pmod{6}$, then $u=6$ and
$\sigma(q,m^{\prime})=13/36$.

  4. (iv)

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

We need the following Lemma 5.3 [12] which we adjusted properly. It provides a
bound on $\Lambda$, for suitable development of the sufficient condition.

######  Lemma 5.3.

Assume that $q=p^{k}$ and $m$ is a positive integer such that $m^{\prime}\nmid
q-1$. Let $u(>2)$ denote the order of $q\mod m^{\prime}$. Let $g$ be the
product of the irreducible factors of $x^{m^{\prime}}-1$ of degree less than
$eu$. Then, in the notation of Theorem 4.2 with $d^{\prime}=Q_{q^{m}-1}$,
$d=q^{m}-1$ and $g^{\prime}=g/(x-1)$, we have $\Lambda\leq 2m^{\prime}$.

We now observe that $q=1,2,3$ and $6$ divide $q-1$ for any $q=7^{k}$ and it
has been discussed earlier, whereas $m^{\prime}=7$ is not possible. Therefore,
it suffices to discuss $m^{\prime}=4,5$ and $m^{\prime}\geq 8$ for which
$m^{\prime}\nmid q-1$.

We first deal with the case $m^{\prime}=4$. Then $m=4\cdot 7^{j}$ for some
positive integer $j$. When $q=7^{k}$ and $m^{\prime}\nmid q-1$, we note that
$k$ is odd and in this case $x^{m^{\prime}}-1$ is the product of two linear
factors and a quadratic factor. This implies that
$W(x^{m}-1)=W(x^{m^{\prime}}-1)=2^{3}=8$ and $W(R_{x^{m}-1})=2^{2}=4$. Thus,
$(q,m)\in\mathfrak{Q}(1,1)$ if $q^{\frac{m}{2}-2}>128\cdot W(q^{m}-1)^{2}$.
Using Lemma 5.1 it is sufficient that
$q^{\frac{3m}{14}-2}>128\cdot(244.66)^{2}$. The above inequality holds for
$q=7$, $m\geq 48$ and for $q\geq 7^{3}$, $m\geq 23$. Now for the only possible
exceptional pair $(7,28)$, we check the condition $q^{\frac{m}{2}-2}>128\cdot
W(q^{m}-1)^{2}$ and found that it satisfies the condition.

We treat the case $m^{\prime}=5$ in two sub-cases. When $q=7^{k}$ with $k$
odd, then $x^{m^{\prime}}-1$ is a product of a linear factor and a factor of
degree four, which implies that $W(x^{m}-1)=W(x^{m^{\prime}}-1)=2^{2}=4$ and
$W(R_{x^{m}-1})=2$. Hence from Theorem 3.3 and Lemma 5.1 it is sufficient that
$q^{\frac{3m}{14}-2}>32\cdot(244.66)^{2}$. The above holds for $q=7$, $m\geq
45$ and for $q\geq 7^{3}$, $m\geq 21$. For the possible exceptional pair
$(7,35)$, we check $q^{\frac{m}{2}-2}>32\cdot W(q^{m}-1)^{2}$ and got it
verified to be true. Again when $q=7^{k}$, where $k$ is even and $k\not\equiv
0\pmod{4}$, $x^{m^{\prime}}-1$ is a product of a linear factor and two
quadratic factors. In this case, $W(x^{m}-1)=W(x^{m^{\prime}}-1)=2^{3}=8$ and
$W(R_{x^{m}-1})=2^{2}=4$. Again applying Theorem 3.3 and Lemma 5.1, it is
sufficient that $q^{\frac{3m}{14}-2}>128\cdot(244.66)^{2}$, which holds for
$q\geq 7^{2}$ and $m\geq 29$. Thus there is no exceptional pair in this case.

Next suppose $m^{\prime}\geq 7$. Let $d^{\prime}=Q_{q^{m}-1}$, $d=q^{m}-1$,
$g^{\prime}=g/(x-1)$ and $g$ be the product of the irreducible factors of
$x^{m^{\prime}}-1$ of degree less than $u$. Thus, Theorem 4.2 along with Lemma
5.3 give us the following sufficient condition

$q^{\frac{m}{2}-2}>8\cdot m^{\prime}\cdot W(q^{m}-1)^{2}\cdot
2^{2m^{\prime}\sigma(q,m^{\prime})},$

that is, it suffices that,

(5.1) $q^{\frac{m}{2}-2}>8\cdot m\cdot W(q^{m}-1)^{2}\cdot
2^{2m\sigma(q,m^{\prime})}.$

######  Lemma 5.4.

Let $q=7$ and $m$ be a positive integer such that $m^{\prime}\nmid q-1$. Then
for $m^{\prime}\geq 8$ we have that, for any prescribed primitive norm $a$ and
a non-zero trace $b$ over $\mathbb{F}_{q}$, there exists an element
$\alpha\in\mathbb{F}_{q^{m}}$ with
$\operatorname{N}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=a$ and
$\operatorname{Tr}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=b$, for
which $(\alpha,f(\alpha))$ is a primitive normal pair in $\mathbb{F}_{q^{m}}$
over $\mathbb{F}_{q}$ except, possibly the pairs $(7,8)$, $(7,9)$, $(7,10)$,
$(7,12)$ and $(7,18)$.

###### Proof.

We divide our discussion into the following two cases.

Case 1. When $m^{\prime}\neq 2m_{1},4m_{1},6m_{1}$, we have from Lemma 5.2
that $\sigma(q,m^{\prime})\leq 1/3$. Substituting this in (5.1) and also using
Lemma 5.1, we have the sufficient condition

$q^{\frac{3m}{10}-2}>8\cdot m\cdot(1.11\times 10^{9})^{2}\cdot
2^{\frac{2m}{3}-1}$

The above inequality holds for $m\geq 436$. Next for $m\leq 435$, we verify
the condition (3.7) and found that $(7,m)\in\mathfrak{Q}(1,1)$ except when
$m$= $8$, $9$, $10$, $11$, $12$, $15$, $16$, $18$, $19$, $20$, $24$, $27$,
$30$, $32$ and $48$. We next choose appropriate values of $d^{\prime}$, $d$,
$g^{\prime}$ and $g$ and get that the pairs $(7,m)$ where $m$= $11$, $15$,
$16$, $19$, $20$, $24$, $27$, $30$, $32$ and $48$ satisfy Theorem 4.2 (see
Table 2). Therefore, in this case the possible exceptional pairs are $(7,8)$,
$(7,9)$, $(7,10)$, $(7,12)$ and $(7,18)$.

Case 2. When $m^{\prime}=6m_{1}$, the only possible value of $m^{\prime}$ is
$36$ and in this case $x^{m^{\prime}}-1$ is a product of $15$ irreducible
factors. Proceeding in a similar way we find that it is sufficient that
$q^{\frac{3m}{14}-2}>2^{31}\cdot(244.66)^{2}$, which holds for $m\geq 88$.
Again for the only possible exceptional pair $(7,36)$, we checked the
sufficient condition (3.7) and get that it fails to satisfy it but it
satisfies Theorem 4.2 for appropriate values of $d^{\prime}$, $d$,
$g^{\prime}$ and $g$(see Table 2). Hence in this case there is no exceptional
pair.

The proof is now complete. ∎

# | $(q,m)$ | $d^{\prime}$ | $d$ | $g^{\prime}$ | $g$ | $\lambda>$ | $\Lambda<$
---|---|---|---|---|---|---|---
1 | $(7,11)$ | 1 | 2 | $\frac{x^{11}-1}{x+6}$ | $x+6$ | 0.664878903964168 | 9.52016640953532
2 | $(7,15)$ | 1 | 2 | $x+3$ | $x+5$ | 0.0650904516114856 | 263.175019977896
3 | $(7,16)$ | 2 | 6 | $x+1$ | $x+6$ | 0.0521044379491288 | 424.228909204995
4 | $(7,19)$ | 1 | 2 | $\frac{x^{19}-1}{x-1}$ | $x+6$ | 0.644400685606226 | 17.5182950970830
5 | $(7,20)$ | 2 | 2 | $x+1$ | $x^{2}+6$ | 0.0219001519714673 | 1006.55923907116
6 | $(7,24)$ | 10 | 6 | $\frac{x^{6}-1}{x-1}$ | $x^{6}+6$ | 0.0716671887608818 | 476.415148519935
7 | $(7,27)$ | 3 | 2 | $x+3$ | $x+6$ | 0.0435777658630945 | 575.687051294481
8 | $(7,30)$ | 22 | 66 | $x^{3}+1$ | $x^{3}+1$ | 0.0532274038983268 | 565.619447931464
9 | $(7,32)$ | 2 | 6 | $x+1$ | $x+6$ | 0.0431067705041303 | 790.739207376768
10 | $(7,48)$ | 131806610 | 30 | $\frac{x^{12}-1}{x-1}$ | $x^{12}+6$ | 0.0431067705041303 | 790.739207376768
11 | $(7,36)$ | 30 | 30 | $x^{4}+x^{2}+1$ | $x^{4}+x^{2}+1$ | 0.0529987428084201 | 681.261395503905
12 | $(7^{2},9)$ | 3 | 6 | $1$ | $x+6$ | 0.710605990818367 | 25.9232432876368
13 | $(7^{2},10)$ | 1 | 6 | $x+1$ | $x+6$ | 0.375641648570107 | 55.2422325270126
14 | $(7^{2},15)$ | 1 | 6 | $\frac{x^{15}-1}{x-1}$ | $x+6$ | 0.547377568602427 | 44.0185285610515
15 | $(7^{2},16)$ | 5 | 6 | $x+1$ | $x+6$ | 0.0831734094045884 | 470.899859693000
16 | $(7^{2},18)$ | 15 | 30 | $\frac{x^{18}-1}{x-1}$ | $x^{3}+x^{2}+4x+1$ | 0.566118276336117 | 40.8611371856472
17 | $(7^{2},20)$ | 5 | 2 | $x+1$ | $x+6$ | 0.106897950411074 | 357.479219703201
18 | $(7^{3},8)$ | 2 | 6 | $x+1$ | $x+6$ | 0.288679255430203 | 81.6731998138361
19 | $(7^{3},10)$ | 2 | 6 | $x+1$ | $x+6$ | 0.693040559610923 | 29.4154228587526
20 | $(7^{3},18)$ | 2 | 2 | $x+1$ | $x+6$ | 0.393704090361428 | 134.078891921755
21 | $(7^{4},9)$ | 3 | 6 | $x+3$ | $x+6$ | 0.426127285898464 | 55.9744831207086
22 | $(7^{5},8)$ | 2 | 2 | $x+1$ | $x+6$ | 0.0159001518760136 | 1511.41954436332
23 | $(7^{6},8)$ | 5 | 2 | $x+1$ | $x+6$ | 0.0637988343818541 | 534.925096977484
24 | $(7^{3},12)$ | 10 | 2 | $x+1$ | $x+6$ | 0.120384944971172 | 259.507282222236
Table 2. Pairs $(q,m)$ with $m^{\prime}\nmid q-1$ for which Theorem 4.2 holds
for the above choices of $d^{\prime}$, $d$, $g^{\prime}$ and $g$.

######  Lemma 5.5.

Let $q\geq 7^{2}$ and $m$ be a positive integer such that $m^{\prime}\nmid
q-1$. Then for $m^{\prime}\geq 8$ we have that, for any prescribed primitive
norm $a$ and a non-zero trace $b$ over $\mathbb{F}_{q}$, there exists an
element $\alpha\in\mathbb{F}_{q^{m}}$ with
$\operatorname{N}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=a$ and
$\operatorname{Tr}_{{\mathbb{F}_{q^{m}}}/{\mathbb{F}_{q}}}(\alpha)=b$, for
which $(\alpha,f(\alpha))$ is a primitive normal pair in $\mathbb{F}_{q^{m}}$
over $\mathbb{F}_{q}$.

###### Proof.

We shall consider the following four cases.

Case 1. $m^{\prime}\neq 2m_{1},4m_{1},6m_{1}$. In this case Lemma 5.2 implies
$\sigma(q,m^{\prime})\leq 1/3$. Applying Lemma 5.1, we get
$(q,m)\in\mathfrak{Q}(1,1)$ whenever $q^{\frac{3m}{14}-2}>8\cdot
m\cdot(244.66)^{2}\cdot 2^{\frac{2m}{3}-1}$. This holds for $q=7^{2}$ for all
$m\geq 55$. Next for $q\geq 7^{2}$ and $q^{m}<(7^{2})^{55}$, we checked the
condition (3.7) and get that all pairs except $(7^{2},9)$, $(7^{2},10)$,
$(7^{2},15)$, $(7^{2},16)$, $(7^{2},18)$, $(7^{2},20)$, $(7^{3},8)$,
$(7^{3},10)$, $(7^{3},18)$, $(7^{4},9)$, $(7^{5},8)$ and $(7^{6},8)$ satisfy
the condition.

Case 2. $m^{\prime}=2m_{1}$. From Lemma 5.2, $\sigma(q,m^{\prime})\leq 1/2$.
Thus, using Lemma 5.1 condition (5.1) becomes, $q^{\frac{3m}{14}-2}>8\cdot
m\cdot(244.66)^{2}\cdot 2^{m-1}$. For $q=7^{2}$ this holds for all $m\geq
152$. Next for the remaining pairs, we verified the sufficient condition (3.7)
and found that the pair $(7^{3},12)$ fails to satisfy it.

Case 3. $m^{\prime}=4m_{1}$. Here, $\sigma(q,m^{\prime})\leq 3/8$. Similarly,
the condition (5.1) becomes $q^{\frac{3m}{14}-2}>8\cdot
m\cdot(244.66)^{2}\cdot 2^{\frac{3m}{4}-1}$ which holds for $q=7^{2}$ for all
$m\geq 66$. For $q\geq 7^{2}$ and $q^{m}\leq 49^{66}$, upon verification we
get that condition (3.7) holds for all pairs. Thus, in this case there is no
exceptional pair.

Case 4. $m^{\prime}=6m_{1}$. In this case $\sigma(q,m^{\prime})\leq 13/36$.
Then the condition (5.1) becomes $q^{\frac{3m}{14}-2}>8\cdot
m\cdot(244.66)^{2}\cdot 2^{\frac{13m}{18}-1}$, which holds for $q=7^{2}$ for
all $m\geq 62$. For $q\geq 7^{2}$ and $q^{m}\leq 49^{62}$ and upon further
verification we get that there is no exceptional pairs.

Finally, we refer to Table 2, to note that Theorem 4.2 holds for all the
possible exceptional pairs in the above discussion for the suitable choices of
$d^{\prime}$, $d$, $g^{\prime}$ and $g$. Thus, there is no possible exception
in this case.

This completes our proof. ∎

As an immediate consequence the discussion in Subsections 5.1 and 5.2 we
obtain the Theorem 1.1.

##  6\. Declarations

Conflict of interest The authors declare no competing interests.

Ethical Approval Not applicable.

Funding The first author is supported by DST INSPIRE Fellowship(IF210206).

Data availability Not applicable.

## References

  * [1] Wun-Seng Chou and Stephen D Cohen.  Primitive elements with zero traces.  Finite Fields and Their Applications, 7(1):125–141, 2001.
  * [2] Stephen D Cohen.  Pairs of primitive elements in fields of even order.  Finite Fields and Their Applications, 28:22–42, 2014.
  * [3] Stephen D Cohen and Dirk Hachenberger.  Primitive normal bases with prescribed trace.  Applicable Algebra in Engineering, Communication and Computing, 9:383–403, 1999.
  * [4] Stephen D Cohen and Dirk Hachenberger.  Primitivity, freeness, norm and trace.  Discrete Mathematics, 214(1-3):135–144, 2000.
  * [5] Stephen D Cohen and Sophie Huczynska.  The primitive normal basis theorem–without a computer.  Journal of the London Mathematical Society, 67(1):41–56, 2003.
  * [6] Lei Fu and Daqing Wan.  A class of incomplete character sums.  arXiv preprint arXiv:1303.3650, 2013.
  * [7] Solomon W Golomb.  Algebraic constructions for costas arrays.  Journal of Combinatorial Theory, Series A, 37(1):13–21, 1984.
  * [8] Anju Gupta, Rajendra K Sharma, and Stephen D Cohen.  Primitive element pairs with one prescribed trace over a finite field.  Finite Fields and Their Applications, 54:1–14, 2018.
  * [9] Giorgos Kapetanakis.  Normal bases and primitive elements over finite fields.  Finite Fields and Their Applications, 26:123–143, 2014.
  * [10] Hendrik Willem Lenstra and RJ Schoof.  Primitive normal bases for finite fields.  Mathematics of Computation, 48(177):217–231, 1987.
  * [11] Christof Paar, Jan Pelzl, Christof Paar, and Jan Pelzl.  Public-key cryptosystems based on the discrete logarithm problem.  Understanding Cryptography: A Textbook for Students and Practitioners, pages 205–238, 2010.
  * [12] Mamta Rani, Avnish K Sharma, Sharwan K Tiwari, and Indivar Gupta.  On the existence of pairs of primitive normal elements over finite fields.  Sao Paulo Journal of Mathematical Sciences, 16(2):1032–1049, 2022\.
  * [13] SageMath Sage Developers.  the sage mathematics software system (version 9.0), 2020.
  * [14] Avnish K Sharma, Mamta Rani, and Sharwan K Tiwari.  Primitive normal pairs with prescribed norm and trace.  Finite Fields and Their Applications, 78:101976, 2022.


1/4})^{\delta^{\prime}n/10}=2^{-\Omega(\delta^{\prime}\log(1/\delta^{\prime})n)},$

when $\delta^{\prime}$ is sufficiently small. If this does not happen, then
$\mathbf{X}_{a}$ at the end is at least

$a-(\delta^{\prime}n/10)-2\cdot(\delta^{\prime}n/10)\geq\delta^{\prime}n/2$

using $a\geq 0.99\delta^{\prime}n$, so the claim is proved. ∎

###### Proof of Claim 42.

Let $S$ be a well-spaced set in $\\{0,1\\}^{n}_{m}$, and
$I_{1},\ldots,I_{\delta^{\prime}n/2}$ be the $\delta^{\prime}n/2$ intervals in
$[n]$ of length $2\beta+1$ each that satisfy the conditions of Definition 40.
For each $I_{j}$, we let $i_{j}\in[t]$ be such that
$I_{j}=\\{v_{i_{j}-\beta},\ldots,v_{i_{j}+\beta}\\}$ (so $v_{i_{j}}$ is the
center of $I_{j}$). Let

$I_{j}^{\prime}=\left\\{v^{\prime}_{i_{j}-4/\sqrt{\delta^{\prime}}},\ldots,v^{\prime}_{i_{j}+4/\sqrt{\delta^{\prime}}}\right\\}$

for each $j$. Note that since $\delta^{\prime}$ is at most some sufficiently
small constant, we have $4/\sqrt{\delta^{\prime}}<\beta$ and thus,
$I_{j}^{\prime}$’s are mutually disjoint intervals in $[n]$ because $I_{j}$’s
satisfy conditions of Definition 40.

Let $\mathbf{S}^{\prime}\sim\\{0,1\\}^{n}_{m}$. We claim that, in order to
have
$\smash{\mathsf{score}_{M}(S,\mathbf{S}^{\prime})\geq(1-\sqrt{\delta^{\prime}})n}$,
it must be the case that $\mathbf{S}^{\prime}$ has at least
$\delta^{\prime}n/4$ many zero entries in the union of $I_{j}^{\prime}$. To
see this, suppose that $\mathbf{S}^{\prime}$ has no more than
$\delta^{\prime}n/4$ many zeros in the union of $I_{j}^{\prime}$. Then at
least $\delta^{\prime}n/4$ many $I_{j}^{\prime}$’s have all ones in
$\mathbf{S}^{\prime}$. For each such $j$, given that
$S_{I_{j}}=1^{\beta}01^{\beta}$, we have that either

$\left(v_{i_{j}-4/\sqrt{\delta^{\prime}}},v^{\prime}_{i_{j}-4/\sqrt{\delta^{\prime}}}\right),\ldots,\left(v_{i_{j}-1},v^{\prime}_{i_{j}-1}\right)\quad\text{or}\quad\left(v_{i_{j}+1},v^{\prime}_{i_{j}+1}\right),\ldots,\left(v_{i_{j}+4/\sqrt{\delta^{\prime}}},v^{\prime}_{i_{j}+4/\sqrt{\delta^{\prime}}}\right)$

are not synched. As a result, the number of pairs in $M$ that are not synched
in $(S,\mathbf{S}^{\prime})$ is at least
$(\delta^{\prime}n/4)\cdot(4/\sqrt{\delta^{\prime}})\geq\sqrt{\delta^{\prime}}n$
and thus, the score is at most $(1-\sqrt{\delta^{\prime}})n$.

Finally we bound the probability of $\mathbf{S}^{\prime}\sim\\{0,1\\}^{n}_{m}$
having at least $\delta^{\prime}n/4$ many zeros in the union of
$I_{j}^{\prime}$. Given that the union has size

$\frac{\delta^{\prime}n}{2}\cdot\left(\frac{8}{\sqrt{\delta^{\prime}}}+1\right)<5\sqrt{\delta^{\prime}}n,$

the probability is at most (where the summand $r$ is the number of zeros in
the union of $I_{j}^{\prime}$)

$\sum_{r=\delta^{\prime}n/4}^{\delta^{\prime}n}{\frac{{5\sqrt{\delta^{\prime}}n\choose
r}\cdot{n-5\sqrt{\delta^{\prime}}n\choose\delta^{\prime}n-r}}{{n\choose\delta^{\prime}n}}}\leq\left(\frac{3\delta^{\prime}n}{4}+1\right)\cdot{5\sqrt{\delta^{\prime}}n\choose\delta^{\prime}n/4}\cdot{\frac{{n-5\sqrt{\delta^{\prime}}n\choose
3\delta^{\prime}n/4}}{{n\choose\delta^{\prime}n}}}$

given that the terms are maximized at $r=\delta^{\prime}n/4$. Using ${n\choose
k}\leq(en/k)^{k}$, we have

${5\sqrt{\delta^{\prime}}n\choose\delta^{\prime}n/4}\leq\left(\frac{60}{\sqrt{\delta^{\prime}}}\right)^{\delta^{\prime}n/4}.$

On the other hand, we have

${\frac{{n-5\sqrt{\delta^{\prime}}n\choose
3\delta^{\prime}n/4}}{{n\choose\delta^{\prime}n}}}\leq{\frac{{n\choose
3\delta^{\prime}n/4}}{{n\choose\delta^{\prime}n}}}=\frac{(n-\delta^{\prime}n)!\cdot(\delta^{\prime}n)!}{(n-3\delta^{\prime}n/4)!\cdot(3\delta^{\prime}n/4)!}\leq\left(\frac{\delta^{\prime}n}{n-\delta^{\prime}n}\right)^{\delta^{\prime}n/4}\leq(2\delta^{\prime})^{\delta^{\prime}n/4}.$

As a result, the probability is at most

$\left(\frac{3\delta^{\prime}n}{4}+1\right)\cdot\left(120\sqrt{\delta^{\prime}}\right)^{\delta^{\prime}n/4}=2^{-\Omega(\delta^{\prime}\log(1/\delta^{\prime})n)}$

since $\delta^{\prime}$ is at most some sufficiently small constant. This
finishes the proof of Claim 42. ∎

## References

  * [BC22] Boris Bukh and Christopher Cox.  Periodic words, common subsequences and frogs.  The Annals of Applied Probability, 32(2):1295 – 1332, 2022.
  * [BCF+19] Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, and Sandip Sinha.  Beyond trace reconstruction: Population recovery from the deletion channel.  In 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 745–768. IEEE Computer Society, 2019.
  * [BCSS19] Frank Ban, Xi Chen, Rocco A. Servedio, and Sandip Sinha.  Efficient average-case population recovery in the presence of insertions and deletions.  In APPROX/RANDOM 2019, volume 145 of LIPIcs, pages 44:1–44:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [BKKM04] Tuǧkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor.  Reconstructing strings from random traces.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pages 910–918, 2004.
  * [BM14] Boris Bukh and Jie Ma.  Longest common subsequences in sets of words.  SIAM J. Discret. Math., 28(4):2042–2049, 2014.
  * [Buk22] B. Bukh.  Personal communication, 2022.
  * [CDK21] Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer.  Approximate trace reconstruction via median string (in average-case).  In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 213 of LIPIcs, pages 11:1–11:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [CDL+21a] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Polynomial-time trace reconstruction in the low deletion rate regime.  In 12th Innovations in Theoretical Computer Science Conference, volume 185 of LIPIcs, pages 20:1–20:20, 2021.
  * [CDL+21b] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Polynomial-time trace reconstruction in the smoothed complexity model.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 54–73, 2021.
  * [CDL+22] Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha.  Near-optimal average-case approximate trace reconstruction from few traces.  In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pages 779–821, 2022.
  * [Cha21a] Zachary Chase.  New lower bounds for trace reconstruction.  Ann. Inst. H. Poincaré Probab. Statist., 57(2):627–643, 2021\.
  * [Cha21b] Zachary Chase.  Separating words and trace reconstruction.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 21–31. ACM, 2021\.
  * [CP21] Z. Chase and Y. Peres.  Approximate trace reconstruction of random strings from a constant number of traces.  Available at https://arxiv.org/abs/2107.06454, 2021.
  * [CS75] Václáv Chvatal and David Sankoff.  Longest common subsequences of two random sequences.  J. Appl. Probability, 12:306–315, 1975.
  * [DOS17] Anindya De, Ryan O’Donnell, and Rocco A. Servedio.  Optimal mean-based algorithms for trace reconstruction.  In Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), pages 1047–1056, 2017.
  * [DRRS21] Sami Davies, Miklos Z. Rácz, Cyrus Rashtchian, and Benjamin G. Schiffer.  Approximate trace reconstruction: Algorithms.  In IEEE International Symposium on Information Theory, 2021.
  * [GHS20] Venkatesan Guruswami, Bernhard Haeupler, and Amirbehshad Shahrasbi.  Optimally resilient codes for list-decoding from insertions and deletions.  In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 524–537. ACM, 2020.
  * [GSZ21] Elena Grigorescu, Madhu Sudan, and Minshen Zhu.  Limitations of mean-based algorithms for trace reconstruction at small distance.  In IEEE International Symposium on Information Theory, 2021.
  * [HHP18] Lisa Hartung, Nina Holden, and Yuval Peres.  Trace reconstruction with varying deletion probabilities.  In Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018, New Orleans, LA, USA, January 8-9, 2018., pages 54–61, 2018.
  * [HMPW08] Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder.  Trace reconstruction with constant deletion probability and related results.  In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pages 389–398, 2008.
  * [HPP18] Nina Holden, Robin Pemantle, and Yuval Peres.  Subpolynomial trace reconstruction for random strings and arbitrary deletion probability.  In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 1799–1840. PMLR, 2018.
  * [HPPZ19] Nina Holden, Robin Pemantle, Yuval Peres, and Alex Zhai.  Subpolynomial trace reconstruction for random strings and arbitrary deletion probability.  Mathematical Statistics and Learning, 2(3/4):275–309, 2019.
  * [Kal73] V. V. Kalashnik.  Reconstruction of a word from its fragments.  Computational Mathematics and Computer Science (Vychislitel’naya matematika i vychislitel’naya tekhnika), Kharkov, 4:56–57, 1973.
  * [KB80] R. Kaas and J.M. Buhrman.  Mean, Median and Mode in Binomial Distributions.  statistica neerlandica, 34(1):13–18, 1980.
  * [KLM05] Marcos Kiwi, Martin Loebl, and Jiří Matoušek.  Expected length of the longest common subsequence for large alphabets.  Advances in Mathematics, 197(2):480–498, 2005.
  * [KMMP19] Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal.  Trace reconstruction: Generalized and parameterized.  In 27th Annual European Symposium on Algorithms, ESA 2019, volume 144 of LIPIcs, pages 68:1–68:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [Lev01a] Vladimir Levenshtein.  Efficient reconstruction of sequences.  IEEE Transactions on Information Theory, 47(1):2–22, 2001.
  * [Lev01b] Vladimir Levenshtein.  Efficient reconstruction of sequences from their subsequences or supersequences.  Journal of Combinatorial Theory Series A, 93(2):310–332, 2001.
  * [Lue09] George S. Lueker.  Improved bounds on the average length of longest common subsequences.  J. ACM, 56(3):17:1–17:38, 2009.
  * [MPV14] Andrew McGregor, Eric Price, and Sofya Vorotnikova.  Trace reconstruction revisited.  In Proceedings of the 22nd Annual European Symposium on Algorithms, pages 689–700, 2014.
  * [NP17] Fedor Nazarov and Yuval Peres.  Trace reconstruction with $\exp(O(n^{1/3}))$ samples.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1042–1046, 2017.
  * [NR21] Shyam Narayanan and Michael Ren.  Circular Trace Reconstruction.  In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 18:1–18:18, 2021.
  * [PZ17] Yuval Peres and Alex Zhai.  Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 228–239. IEEE Computer Society, 2017.
  * [SB21] Jin Sima and Jehoshua Bruck.  Trace reconstruction with bounded edit distance.  In IEEE International Symposium on Information Theory, 2021.  Manuscript, available at https://arxiv.org/abs/2102.05372.
  * [SDDF18] Sundara Rajan Srinivasavaradhan, Michelle Du, Suhas Diggavi, and Christina Fragouli.  On maximum likelihood reconstruction over multiple deletion channels.  In IEEE International Symposium on Information Theory, ISIT 2018, pages 436–440, 2018.
  * [Tur66] L. Richard Turner.  Inverse of the vandermonde matrix with applications.  NASA technical note D-3547 available at available at http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19660023042.pdf., 1966\.
  * [vL82] J. H. van Lint.  Introduction to Coding Theory.  Springer Science+Business Media, 1982.
  * [Wik22a] Wikipedia contributors.  Chvátal-Sankoff constants.  Wikipedia, The Free Encyclopedia, accessed June 23, 2022.  https://en.wikipedia.org/wiki/Chvátal-Sankoff$\\_$constants.
  * [Wik22b] Wikipedia contributors.  Subadditivity.  Wikipedia, The Free Encyclopedia, accessed June 23, 2022.  https://en.wikipedia.org/wiki/Subadditivity.

##  Appendix A An upper bound on average-case zero-trace reconstruction

We recall from Section 1.1.2 that in the asymptotic limit, the best possible
performance of any zero-trace average-case reconstruction algorithm is given
by

$c_{2}=\lim_{n\to\infty}\max_{z\in\\{0,1\\}^{n}}{\frac{\operatorname{{\bf
E}}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}[|\mathsf{LCS}(\boldsymbol{x},\boldsymbol{z})|]}{n}},$

and from Section 5 that this quantity equals
$\lim_{n\to\infty}{\frac{L_{0,\mathop{\mathrm{avg}}}(n)}{n}}.$

Via an involved analysis, Bukh and Cox show that $\operatorname{{\bf
E}}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}[|\mathsf{LCS}(\boldsymbol{x},w)|]\geq
0.82118$ where $w$ is the $n$-bit string
$(0110111010010110010001011010)^{n/28},$ and hence $c_{2}\geq 0.82118.$ We
give an upper bound on $c_{2}$:

######  Claim 43.

$c_{2}\leq 0.88999.$

###### Proof.

Fix $z\in\\{0,1\\}^{n}$ to be the optimal string that maximizes
$\operatorname{{\bf
E}}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}[|\mathsf{LCS}(\boldsymbol{x},\boldsymbol{z})|]$.
The claimed bound on $c_{2}$ follows from

$\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}[z\text{~{}has a
matching of size $0.88999n$ with $\boldsymbol{x}$}]\leq o(1),$ (34)

which we establish below by showing that

$\sum_{S\subseteq[n],|S|=0.88999n}\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}[z_{S}\text{~{}matches entirely into
$\boldsymbol{x}$}]\leq o(1).$ (35)

Via a union bound, Equation 35 in turn follows from showing that for any
$t$-bit string $y$, where $t:=0.88999n$, we have

$\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}[y\text{~{}matches
entirely into $\boldsymbol{x}$}]={\frac{o(1)}{{n\choose 0.88999n}}}.$ (36)

Fix any $t$-bit string $y$ and any $n$-bit string $x$. The “greedy strategy”
for (attempting to) entirely match $y$ into $x$ is the approach which
maintains two pointers $p_{y}$ (into the coordinates of $y$) and $p_{x}$ and
scans across $x$ by successively incrementing $p_{x}$, matching each
coordinate of $y$ and incrementing $p_{y}$ whenever it is possible to do so.
We recall the following well-known fact:

######  Claim 44 (Greedy matching is optimal for entirely matching one string
into another).

There is some matching that entirely matches $y$ into $x$ if and only if the
greedy strategy succeeds in entirely matching $y$ into $x$.

We return to establishing Equation 36. By Claim 44, $y$ matches entirely into
$\boldsymbol{x}$ if and only if the greedy strategy matches $y$ entirely into
$\boldsymbol{x}$. We may view a uniform $\boldsymbol{x}\sim\\{0,1\\}^{n}$ as
being generated by successively tossing coins for the successive bits of
$\boldsymbol{x}$; from this perspective it is clear that $\operatorname{{\bf
Pr}}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}[$the greedy strategy successfully
matches $y$ entirely into $\boldsymbol{x}]$ is precisely the probability that
a sequence of $n$ fair coin tosses has at least $t$ “heads” (the $i$-th coin
toss coming up “heads” corresponds to the $i$-th bit $\boldsymbol{x}_{i}$
matching the bit of $y$ currently pointed to by $p_{y}$). By 8, this
probability is at most

${\frac{2^{H(0.11001)n}}{2^{n}}},$ (37)

so again using 8 and $2H(0.11001)<1$ we get that
$(\ref{eq:plum})={\frac{o(1)}{{n\choose 0.88999n}}}$ as required. ∎

##  Appendix B A simple upper bound on average-case one-trace reconstruction
in the small deletion rate regime

In this section we give a simple upper bound on the best possible expected LCS
that any one-trace algorithm can achieve in the average-case small-deletion-
rate regime. The argument, which is based on a union bound over all possible
matchings of a given size, is significantly simpler than the proof of Theorem
35, but it yields a result that is quantitatively weaker by a
$\Theta(\log(1/\delta))$ factor.

######  Theorem 45 (Weak average-case upper bound on any algorithm, small
deletion rate).

Let $\delta=\delta(n)$ be any $\omega(1/n)$ deletion rate. There is an
absolute constant $c>0$ such that for sufficiently large $n$ we have
$L_{1,\mathop{\mathrm{avg}}}(\delta,n)\leq(1-c\delta/\log(1/\delta))n.$

###### Proof.

As in the beginning of the proof of Theorem 35, by recalling the well-known
fact [KB80] that the median of the $\mathrm{Bin}(n,\delta)$ distribution
belongs to $\\{\lfloor n\delta\rfloor,\lceil n\delta\rceil\\}$, since
$\delta=\omega(1/n)$ we have that with probability $\Omega(1)$ the length
$|\boldsymbol{y}|$ of a random trace $\boldsymbol{y}$ drawn from the
$\delta$-deletion channel is at least
$(1-\Omega(\delta))n=:(1-\delta^{\prime})n$. Hence to upper bound
$L_{1,\mathop{\mathrm{avg}}}(\delta,n)$ as claimed, it suffices to show the
following: for any one-trace algorithm $A$ that is given as input a uniform
random trace $\boldsymbol{y}$, of length exactly $(1-\delta^{\prime})n$, from
a uniform random source string $\boldsymbol{x}\sim\\{0,1\\}^{n}$, we have

$\mathop{{\bf Pr}\/}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}\left[A\text{~{}outputs
a hypothesis string $z$
with~{}}|\mathsf{LCS}(\boldsymbol{x},z)|\geq\left(1-{\frac{c\delta^{\prime}}{\log(1/\delta^{\prime}}}\right)n\right]\leq
0.9.$ (38)

We first recall from Corollary 10 that given a trace $\boldsymbol{y}$ of
length $(1-\delta^{\prime})n$ from a uniform
$\boldsymbol{x}\sim\\{0,1\\}^{n}$, the $\delta^{\prime}n$ bits of
$\boldsymbol{x}_{\mathbf{D}}$ that are missing from $\boldsymbol{y}$ are
independent and uniform random. Next, we note that any candidate matching
$\mu$ of size $(1-\tau)n$ between a source string $x\in\\{0,1\\}^{n}$ and a
hypothesis string $z\in\\{0,1\\}^{n}$ is completely specified by two subsets
$S=\\{i_{1}<\cdots<i_{\tau n}\\}\subset[n]$ and
$S^{\prime}=\\{j_{1}<\cdots<j_{\tau n}\\}\subset[n]$ of size $\tau n$, where
$S$ ($S^{\prime}$, respectively) is the set of positions in $x$ (positions in
$z$, respectively) that do not participate in the matching.

Fix any hypothesis string $z\in\\{0,1\\}^{n}$ (here $z$ may depend on the
trace $\boldsymbol{y}\sim\\{0,1\\}^{(1-\delta^{\prime})n}$ that algorithm $A$
receives as input). Consider a fixed candidate matching $\mu$ of size
$(1-\tau)n$ between $z$ and $\boldsymbol{x}$, defined by two fixed sets
$S,S^{\prime}$ as described above. For $\tau<\delta^{\prime}/2$ (which will be
the case given our final parameter setting for $\tau$), even if all $\tau n$
positions in $S$ are contained in the deleted locations $\mathbf{D}$, there
are at least $(\delta-\tau)n\geq(\delta^{\prime}/2)n$ bits in
$\boldsymbol{x}_{\mathbf{D}}$ that are not present in $\boldsymbol{y}$ but are
matched to some bits of $z$ by the candidate matching $\mu$. As mentioned
above, these bits are independently uniform random, and so the probability
that $\mu$ successfully matches all of those (at least) $(\delta^{\prime}/2)n$
bits with the right outcomes of their partners in $z$ is at most
$2^{-(\delta^{\prime}/2)n}.$ It follows that $\operatorname{{\bf
Pr}}_{\boldsymbol{x}}[$the candidate matching $\mu$ is a valid matching
between $z$ and $\boldsymbol{x}]\leq 2^{-(\delta^{\prime}/2)n}$. Hence we have

$\displaystyle\mathop{{\bf
Pr}\/}_{\boldsymbol{x}\sim\\{0,1\\}^{n}}[\text{there exists some matching of
size $(1-\tau)n$ between $\boldsymbol{x}$ and $z$}]$
$\displaystyle\leq{n\choose\tau n}^{2}\cdot 2^{-(\delta^{\prime}/2)n}\leq
2^{(2H(\tau)-\delta^{\prime}/2)n}\leq 2^{-(\delta^{\prime}/4)n}\leq 0.9,$

where the first inequality is by a union bound over all ${n\choose\tau n}^{2}$
many candidate matchings of size $(1-\tau)n$, the second is 8, the third holds
by choosing $\tau=c\delta^{\prime}/\log(1/\delta^{\prime})$ for a suitable
absolute constant $c$, and the fourth (with room to spare) is because
$\delta^{\prime}$, like $\delta$, is $\omega(1/n).$ ∎

##  Appendix C No constant-size $(2/3+\varepsilon)n$-LCS cover for any
constant $\varepsilon>0$

######  Claim 46.

For any positive constant $\varepsilon$, any $(2/3+\varepsilon)n$-LCS cover
$S\subseteq\\{0,1\\}^{n}$ must have size $\Omega(\log n)$.

###### Proof.

Let $\varepsilon$ be a positive constant and let
$\varepsilon^{\prime}=6\varepsilon$. Let $S\subseteq\\{0,1\\}^{n}$ be a
$(2/3+\varepsilon)n$-LCS cover for strings of length $n$. As explained in
Section 3.2.2, by arguments given in the proof of Theorem 1.4 of [GHS20], for
any $x\in\\{0,1\\}^{n}$ (and hence in particular for each string $x\in S$),
there can be at most ${1200}/{\varepsilon^{\prime 3}}$ many strings $a\in
C_{n,\varepsilon^{\prime}}$ that have
$\lvert\mathsf{LCS}(x,a)\rvert\geq(2/3+\varepsilon^{\prime}/6)n=(2/3+\varepsilon)n.$
Say a string $a\in C_{n,\varepsilon^{\prime}}$ is _covered_ if there is some
string $x\in S$ such that
$\lvert\mathsf{LCS}(x,a)\rvert\geq(2/3+\varepsilon)n$; it follows that at most
$|S|\cdot{({1200}/{\varepsilon^{\prime 3}}})$ strings in
$C_{n,\varepsilon^{\prime}}$ are covered. Given that every string in
$C_{n,\varepsilon^{\prime}}$ is covered (by the assumption that $S$ is a
$(2/3+\varepsilon)n$-LCS cover), we have

$|S|\cdot\frac{1200}{\varepsilon^{\prime
3}}\geq\big{|}C_{n,\varepsilon^{\prime}}\big{|}=\frac{\log
n}{\log(1/\varepsilon^{\prime 4})},$

from which the $\Omega(\log n)$ lower bound on $|S|$ follows. ∎