# Characterizing SARS-CoV-2 Spike Sequences Based on Geographical Location

Sarwan Ali  Babatunde Bello  Zahra Tayebi and Murray Patterson
Department of Computer Science, Georgia State University
Atlanta, GA 30303, USA

###### Abstract

With the rapid spread of COVID-19 worldwide, viral genomic data is available
in the order of millions of sequences on public databases such as GISAID. This
_Big Data_ creates a unique opportunity for analysis towards the research of
effective vaccine development for current pandemics, and avoiding or
mitigating future pandemics. One piece of information that comes with every
such viral sequence is the geographical location where it was collected — the
patterns found between viral variants and geographical location surely being
an important part of this analysis. One major challenge that researchers face
is processing such huge, highly dimensional data to obtain useful insights as
quickly as possible. Most of the existing methods face scalability issues when
dealing with the magnitude of such data. In this paper, we propose an approach
that first computes a numerical representation of the spike protein sequence
of SARS-CoV-2 using $k$-mers (substrings) and then uses several machine
learning models to classify the sequences based on geographical location. We
show that our proposed model significantly outperforms the baselines. We also
show the importance of different amino acids in the spike sequences by
computing the information gain corresponding to the true class labels.

###### keywords:

Sequence Classification, SARS-CoV-2, COVID-19, $k$-mers, Geographical Location

##  1 Introduction

The adaptability of viruses like SARS-CoV-2, when coupled with a variety of
selection pressures from the various ecosystems, host immunities and
approaches to pharmaceutical intervention provide an evolutionary environment
that leads to the emergence of strains and variants in different geographical
locations. While SARS-CoV-2 has spread rather quickly to many parts of the
globe since the initial outbreak in Wuhan at the end of 2019, which led to the
COVID-19 pandemic Wu et al. (2020), it continues to raise global concerns as
the virus persistently evolves and accumulates new mutations. Consequently,
new variants of SARS-CoV-2 have emerged in different parts of the world: the
Alpha variant (B.1.1.17) emerged in the UK, Beta (B.1.351) in South Africa,
Gamma in Brazil, Epsilon in California, Iota (B.1.526) in New York, Delta
(B.1.167.2) and Kappa (B.1.167.1) in India, to name a few. All of these
variants possess some mutations that confer increased transmissibility or
higher binding affinity of their spike protein (see Figure 1) to human host
ACE2 receptors Farinholt et al. (2021); Huang et al. (2020).

Figure 1: The SARS-CoV-2 genome codes for several proteins, including the
surface, or spike protein. The spike protein is composed of 3821
($25384-21563$) nucleotides (and one “stop” character ‘*’). Therefore, the
final length of the spike protein is $3822/3=1274$ (we divide by $3$ because
each amino acid corresponds to $3$ DNA characters, or codons) Huang et al.
(2020).

It is concerning that the longer SARS-CoV-2 has to propagate, its exposure to
wider ranges of immune response attacks across diverse communities and
geographically diverse environments may be incubating the virus to evolve new
variants and strains that are dangerous and extremely immunologically evasive
both locally and globally, as the pandemic prolongs. From the point of view of
evolution, this is like giving the virus robust evolutionary room and time to
learn, to evolve adaptations, gain of function, and escapes from host immune
arsenal and attacks. Sadly, this is gradually the case already, as the
original Wuhan strain is now almost completely replaced by new variants with
different characteristic behaviors and are hence less responsive to the
currently available vaccines Korber et al. (2020); Hu et al. (2021). This is
why it is important to characterize different strains and variants of SARS-
CoV-2 based on geographical location, to understand the patterns of spread in
hopes to contain, or at least cope with this virus.

All viruses mutate with time — RNA viruses particularly do so at a faster
rate. The SARS-CoV-2 is an RNA virus, it however exhibits a moderately lower
rate compared to other RNA viruses like HIV and influenza due to the
possession of a genetic proof-reading mechanism for correcting errors. The
SARS-CoV-2 genome typically accrues 1 or 2 point mutations (SNVs) in a month.
According to a review, some 12,706 such mutations have so far been detected by
researchers since the advent of the COVID-19 pandemic. While some changes have
neutral effects, a few that occur in major proteins — be it, addition,
substitution or deletion — are critical to viral evolution, genomic stability,
transmissibility, antigenicity, virulence, adaptation and escape from host
immune response Pachetti et al. (2020); Lorenzo-Redondo et al. (2020). The
SARS-CoV-2 Spike (S) Protein is a key player in the virus life cycle. The
protein is composed of $1274$ amino acids encoded by the S gene of the virus
(see Figure 1). It is the major target of the neutralizing antibodies from
host immune response and currently available vaccines for COVID-19. The virus
uses the spike protein to bind the host ACE2 receptor on the cell surface
(found abundantly in airways, lungs, mucous lines and the intestine) which
facilitates the uptake of the virus into host cells Lamers et al. (2020);
V’kovski et al. (2021). Thus, mutations in the S gene have reportedly imparted
viral pathogenesis, binding activity of the spike protein to the host, as well
as causing conformational changes in the protein molecule. For instance,
mutation D614G — that is, a substitution of Glycine (G) for Aspartate (D) at
position 614 — was found to enhance the viral infectivity and stability of the
SARS-CoV-2 genome, which has been attributed to spike protein assembly on the
virion surface Korber et al. (2020).

Currently, quite a number of novel variants are being identified by the US
Centers for Disease Control and Prevention (CDC) and the World Health
Organization (WHO) SARS-CoV-2 Variant Classifications and Definitions . The
variants are divided into categories such as Variants of Concern (VOCs),
Variants Being Monitored (VBMs), Variants of interest (VOIs), and Variants of
High Consequence (VOHCs). At the time of this study, the VOC was the Delta
variant (B.1.617.2 and AY.1 sublineages) SARS-CoV-2 Variant Classifications
and Definitions . Since all of these variants are characterized by different
spike protein content Farinholt et al. (2021); Huang et al. (2020),
classification can help us to discover also patterns in the geographic
distribution of these variants. At the time of this study, the VBMs comprised
Alpha (B.1.1.7, Q.1-Q.8 pango lineage), Beta (B.1.351, B.1.351.2, B.1.351.3
pango lineage), Gamma (P.1, P.1.1, P.1.2 pango lineage), Epsilon (B.1.427
B.1.429 pango lineage), Eta (B.1.525 pango lineage), Iota (B.1.526 pango
lineage), Kappa (B.1.617.1 pango lineage), Zeta (P.2 pango lineage), and MU
(B.1.621, B.1.621.1 pango lineage) SARS-CoV-2 Variant Classifications and
Definitions . There are no VOIs or VOHCs at the time.

The SARS-CoV-2 still circulates among human populations in different
locations, weather conditions and epidemiological descriptions. It is
important to investigate how this regional diversity contributes to viral
evolution and emergence of new variants in these regions. Research suggests
possible selective mutations in the SARS-CoV-2 genome — specific sites which
appear more subject to selective mutation. Some mutational sites in ORF1ab,
ORF3a, ORF8 and N regions of SARS-CoV-2 reportedly exhibit different rates of
mutation Wang et al. (2020). A study involving the analysis and
characterization of samples from COVID-19 patients in different parts of the
world identify 8 novel recurrent mutational sites in the SARS-CoV-2 genome.
Interestingly, the studies also note changes at sites 2891, 3036, 14408,
23403, and 28881 to be common in Europe, while 17746, 17857, and 18060 are
common in North America Pachetti et al. (2020). A recent study also identified
the ongoing evolution of SARS-CoV-2 to involve purifying selection, and that a
small number of sites appear to be positively selected. The work also
identifies the spike protein receptor binding domain (RBD) and a region of
nucleocapsid protein to be also positively selected for substitutions. The
work also highlighted trend in virus diversity with geographic region and
adaptive diversification that may potentially make variant-specific
vaccination an issue Rochman et al. (2021).

Given all of the novel SARS-CoV-2 variants and strains that have emerged from
different geographical regions of the world, we need to investigate this
connection to the spread of the virus, _e.g._ , weather factors possibly play
a systematic role Segovia-Dominguez et al. (2021); Pezzotti et al. (2016).
There is also diversity of immune system across the human population. Genomic
variations only cause 20–40% of this immune system variation, while the rest
60–80% is accounted for by age, environmental factors, such as where we live
and our neighbors, cohabitation and chronic viral infections, etc. Immune
response is also known to show intra-species variation Liston et al. (2016).
There is an ongoing evolutionary arms-race between host and pathogens they are
exposed to which constantly changes the host anti-pathogen attack and in turn
causes the pathogen to refine or adjust its escape from host immune attack
Liston et al. (2016); Brodin et al. (2015). This is constantly taking place,
with the virus under evolutionary pressure and natural selection to propagate
the virus with the highest fitness. It may be complex to characterize how each
factor contributes to this variation. The immune system variation is possibly
an important driver on how new variants of SARS-CoV-2 are regionally emerging
with positive selections for escaping immune neutralization, increased
infectivity and transmissibility, as observed recently.

Classification of the SARS-CoV-2 Spike protein sequences based on geographical
location of emergence is therefore an important and informative exploration
for possible unique patterns, trends and distribution. The SARS-CoV-2 spike
protein must interact chemically with the host receptor molecule, ACE2 for
cellular uptake. Since millions of spike sequences are available now on public
databases such as GISAID, classifying those sequences becomes a _Big Data_
problem. When dealing with big data, scalability and robustness are two
important challenges. Some algorithms are robust while other scale well, but
give poor predictive performance on larger datasets. The author of Ali and
Patterson (2021) proposed a scalable approach, called Spike2Vec, which is
scalable to larger sized datasets. When there is some structure (natural
clustering) in the data, Spike2Vec is proven to be useful as compared to one-
hot embedding Ali and Patterson (2021). However, we show in this paper that
Spike2Vec does not always work in all types of scenarios. To further improve
the results of Spike2Vec and that of one-hot embedding, we use a neural
network (NN) model.

In this paper, we propose to use a simple sequential convolutional neural
network along with a $k$-mers based feature vector representation for
classifying the geographical locations of COVID-19 patients using spike
protein sequences only. Our contributions in this paper are the following:

  1. 1.

We show that the neural network model is scalable on a high volume of data and
significantly outperforms the baseline algorithms.

  2. 2.

We show the importance of different amino acids within the spike sequence by
computing information gain corresponding to the class label.

  3. 3.

We show that given the complexity of the data, our model is still able to
outperform the baselines while using only 10% of the training data.

  4. 4.

We show that preserving the order of amino acids using $k$-mers achieves
better predictive performance than the traditional one-hot encoding based
embedding approach.

  5. 5.

Our approach allows us to predict the geographical region of the COVID-19
infected patient while accounting for important local and global variability
in the spike sequences.

The rest of the paper is organized as follows: Section 2 contains the related
work. The proposed approach is given in Section 3. Dataset detail and
experimental setup are in Section 4. The results of our method and comparison
with baselines is shown in Section 5. Finally, we conclude our paper in
Section 6.

##  2 Related Work

Sequence classification is a widely studied problem in domains like sequence
homology (shared ancestry) detection between a pair of proteins and Phylogeny
based inference Dhar et al. (2020) of disease transmission Krishnan et al.
(2021). Knowledge of variants and mutations can also help in identifying the
transmission patterns of different variants, which will help to devise
appropriate public health interventions so that the rapid spread of viruses
can be prevented Ahmad et al. (2016, 2017); Tariq et al. (2017); Ahmad et al.
(2020). This will also help in vaccine design and efficacy. Previous studies
on working with a fixed length numerical representation of the data
successfully perform different data analytics tasks. It has applications in
different domains such as graphs Hassan et al. (2020, 2021), nodes in graphs
Ali et al. (2021a); Grover and Leskovec (2016), and electricity consumption
Ali et al. (2019, 2020b). This vector-based representation also achieves
significant success in sequence analysis, such as texts Shakeel et al. (2020b,
a, 2019), electroencephalography and electromyography sequences Atzori et al.
(2014); Ullah et al. (2020), Networks Ali et al. (2020a), and biological
sequences Ali et al. (2021c). However, most of the existing sequence
classification methods require the input sequences to be aligned. Although
sequence alignment helps to analyze the data better, it is a very costly
process.

In the evolution of the SARS-CoV-2 genome, it is well-known that a
disproportionate amount (in terms of its length) of the variation takes place
in the spike region. Kuzmin _et al._ in Kuzmin et al. (2020) show that viral-
host classification can be done efficiently using spike sequences only and
applying different machine learning (ML) models. They use one-hot encoding
(OHE) to obtain a numerical representation for the spike sequences and then
apply traditional ML classifiers after reducing the dimensions of the data
using the principal component analysis (PCA) method Wold et al. (1987).
Although OHE is proven to be efficient in terms of predictive performance, it
does not preserve the order of amino acids in the spike protein if we want to
take the pair-wise Euclidean distance Ali et al. (2021d). Another problem with
the one-hot encoding based approach is that it deals with aligned sequential
data only.

Many previous studies propose the use of $k$-mers (substrings of length $k$),
which is an alignment-free approach, instead of the traditional OHE based
embedding to obtain the numerical vector representation for the genomic data
Ali et al. (2021b, d); Ali and Patterson (2021). After computing substrings of
length $k$, a fixed-length feature vector is generated, containing the count
of each unique $k$-mer in a given sequence. This $k$-mers based method has
been used for phylogenetic applications Blaisdell (1986) and has shown success
in constructing accurate phylogenetic trees from DNA sequences. Authors in Ali
et al. (2021d) argue that better sequence classification results can be
achieved using $k$-mers instead of OHE because $k$-mers tends to preserve the
order of amino acids within a (_e.g._ , spike) sequence.

After obtaining the numerical representation, a popular approach is to compute
the kernel matrix and provide that matrix as input to traditional machine
learning classifiers like support vector machines (SVM) Leslie et al. (2003);
Farhan et al. (2017); Kuksa et al. (2012). Farhan _et al._ in Farhan et al.
(2017) propose an approximate kernel (Gram matrix) computation algorithm,
which uses the $k$-mers based feature vector representation as an input to the
kernel computation algorithm.

##  3 Proposed Approach

In this section, we present our proposed model for classifying population
regions based on spike sequences only. We start by explaining the basic
MAJORITY based model for the classification. We then show the one-hot encoding
(OHE) based feature vector generation approach. After that, we show how we
generate $k$-mers based frequency vectors. Then, we introduce our models,
which we are using for the purpose of classification. Finally, we give brief
details on the experimental setup, before reporting the results of these
experiments in the following section.

###  3.1 MAJORITY

We start with a simple baseline model called MAJORITY. In this approach, we
simply take the class with majority representation in the training data and
declare it as the class label for all data points in the test set. We then
measure the performance of this baseline model using different evaluation
metrics.

###  3.2 One-Hot Encoding Kuzmin et al. (2020)

In order to obtain a numerical representation for the sequence-based data, one
of the popular methods is using one-hot encoding (OHE) Kuzmin et al. (2020);
Ali et al. (2021b, d); Ali and Patterson (2021). Note that the length of each
spike sequence in our dataset is $1274$, which contains characters (amino
acids) from a set of $21$ unique alphabets “ACDEFGHIKLMNPQRSTVWXY”. For OHE,
since we need to have a $21$ dimensional sub-vector for each amino acid, the
length of the OHE based feature vector for each spike sequence will be
$21\times 1273=26,733$ (we take the length of spike protein as $1273$ instead
of $1274$ because we have the stopping character ‘*’ at the $1274^{th}$
position). After obtaining the OHE for the whole data, since the
dimensionality of the data will be high, authors in Kuzmin et al. (2020) use
the typical principal component analysis (PCA) approach for dimensionality
reduction. Since the size of the data is much larger in our case, we simply
cannot use PCA because of high computational cost Ali and Patterson (2021).
For this purpose, we use instead an unsupervised approach for low dimensional
feature vector representation, called random Fourier features (RFF) Rahimi et
al. (2007).

###  3.3 Random Fourier Features (RFF) Based Embedding Rahimi et al. (2007)

To compute the pair-wise similarity between two feature vectors, a popular
method is to compute the kernel (similarity) matrix (Gram matrix) and give it
as input to popular classifiers such as support vector machine (SVM) Farhan et
al. (2017). However, exact kernel methods are expensive in terms of
computation (scale poorly on training data Rahimi et al. (2007)), and they
require huge space to store an $n\times n$ matrix (where $n$ is the total
number of data points). To overcome this problem, we can use the so-called
kernel trick.

######  Definition 1 (Kernel Trick).

The kernel trick is a fast way to compute the similarity between feature
vectors using the inner product. The kernel trick’s main goal is to avoid the
explicit need to map the input data to a high-dimensional feature space.

The kernel trick relies on the assumption that any positive definite function
$f(a,b)$, where $a,b\in\mathcal{R}^{d}$, defines an inner product and a
lifting $\phi$ so that we can quickly compute the inner product between the
lifted data points Rahimi et al. (2007). It can be described in a formal way
as $\langle\phi(a),\phi(b)\rangle=f(a,b)$.

Although the kernel trick is effective in terms of computational complexity,
it is still not scalable to millions of data points. To overcome these
computational and storage problems, we use RFF Rahimi et al. (2007), an
unsupervised approach that maps the input data to a randomized low dimensional
feature space (Euclidean inner product space). It can be described in a formal
way as $z:\mathcal{R}^{d}\rightarrow\mathcal{R}^{D}$. In RFF, we approximate
the inner product between a pair of transformed points, which is almost equal
to the actual inner product between the original data points. More formally:
$f(a,b)=\langle\phi(a),\phi(b)\rangle\approx z(a)^{\prime}z(b)$. Here, $z$ is
a (transformed) low dimensional (approximate) representation of the original
feature vector (unlike the lifting $\phi$). Since $z$ is the approximate low
dimensional representation of the original feature vector, we can use $z$ as
an input for different machine learning (ML) tasks such as classification.

###  3.4 Spike2Vec Ali and Patterson (2021)

Spike2Vec is a recently proposed method that uses $k$-mers and RFF to design a
low dimensional feature vector representation of the data and then perform
typical ML tasks such as classification and clustering Ali and Patterson
(2021). The first step of Spike2Vec is to generate $k$-mers for the spike
sequences.

####  3.4.1 $k$-mers Computation

The main idea behind $k$-mers is to preserve the order of amino acids within
spike sequences. The $k$-mers is basically a set of substrings (called mers)
of length $k$. For each spike sequence, the total number of $k$-mers is
$N-k+1$, where $N$ is the length of the spike sequence ($1274$), and $k$ is a
user-defined parameter for the size of each mer. An example of $k$-mers (where
k = $3,4,$ and $5$) is given in Figure 2. In this paper, we are using $k=3$
(selected empirically).

Figure 2: Example of different length $k$-mers in spike sequence “MDPEG”.

###  3.5 Machine Learning Models

To both feature engineering based embeddings, namely OHE and Spike2Vec, we
apply three ML classifiers downstream, namely Naive Bayes (NB), Logistic
Regression (LR), and Ridge Classifier (RC). For all these classifiers, default
parameters are used for training. To measure the performance, we use average
accuracy, precision, recall, weighted and macro $F_{1}$, receiver operating
characteristic area under the curve (ROC-AUC). We also show the training
runtime (in seconds) for all methods.

###  3.6 Neural Network Model

Although the Spike2vec embedding allows the downstream ML models to scale to
datasets with millions of sequences, and is proven to outperform the typical
OHE, it is not always effective in terms of overall predictive performance in
certain scenarios. To further increase the predictive performance, we move to
a neural network (NN) architecture, which takes OHE or $k$-mers based vectors
as input. Note that no dimensionality reduction step (_e.g._ , PCA, RFF) is
applied beforehand — the NN model takes the OHE or $k$-mers based vectors
directly. Our NN architecture comprises a sequential constructor. We create a
fully connected network with one hidden layer that contains $9261$ neurons
(which is equal to the length of the feature vector _i.e._ , one neuron for
every feature at the beginning). The activation function that we are using is
“rectifier”. In the output layer, we use the “softmax” activation function. At
the end, we use the efficient Adam gradient descent optimization algorithm
Zhang (2018) with the “sparse categorical crossentropy” loss function (used
for multi-class classification problems), which computes the crossentropy loss
between the labels and predictions. The batch size that we are taking is
$100$, and we take $10$ as the number of epochs for training the model. Note
that we use OHE and $k$-mers based frequency vectors (separately) as input to
the NN.

######  Remark 3.1.

Note that we are using “sparse categorical crossentropy” rather than simple
“categorical crossentropy” because we are using integer labels rather than the
one-hot representation of labels.

##  4 Experimental Evaluation

In this section, we provide some statistics and visualization on the data that
we use, and then the precise details of the experimental setup used to produce
the results.

###  4.1 Dataset Statistics

We use a set of 2,384,646 spike amino acid sequences obtained from the GISAID
GISAID Website , along with metatdata on geographical location (continent,
country, and in the case of the USA, states). This data, organized by country,
is given in Table 1.

Region | Country | No. of sequences | Region | Country | No. of sequences
---|---|---|---|---|---
Europe | England | 568202 | North America | USA | 663527
Germany | 146730 | Canada | 91193
Denmark | 138574 |  | Mexico | 20040
Sweden | 78810 | Total | 3 | 774760
Scotland | 69387 | South America | Brazil | 26729
France | 56247 | Total | 1 | 26729
Netherlands | 49938 | Asia | Japan | 75423
Spain | 48830 | India | 37943
Switzerland | 48516 | Israel | 14361
Wales | 46851 | Total | 3 | 127727
Italy | 44728 | Australia | Australia | 20985
Belgium | 28758 | Total | 1 | 20985
Ireland | 23441 |  |  |
Poland | 16061 |  |  |
Norway | 14684 |  |  |
Lithuania | 13586 |  |  |
Luxembourg | 12713 |  |  |
Finland | 11254 |  |  |
Slovenia | 17135 |  |  |
Total | 19 | 1434445 |  |  |

Table 1: The set of 2,384,646 SARS-CoV-2 spike sequences used in this study,
labeled by country of origin.

###  4.2 Data Visualization

To evaluate any natural clustering in our data (if any exist), we use the
t-distributed stochastic neighbor embedding (t-SNE) Van der M. and Hinton
(2008). The t-SNE approach maps the data into a 2-dimensional (2D) real
vector, which can then be visualized using a scatter plot. Since applying
t-SNE on the whole data is very costly and time consuming, we randomly sampled
a subset ($\approx$80K sequences) from the data (of Table 1) and generated a
2D real vector using the t-SNE approach (see Figure 3).

######  Remark 4.1.

The reason for (randomly) selecting $\approx$80K sequences is because the
t-SNE method is computationally very expensive (runtime is $O(N^{2})$, where
$N$ is the number of data-points Pezzotti et al. (2016)) and is infeasible in
terms of runtime on 2.3 million sequences.

Figure 3: A t-SNE plot from the frequency ($k$-mers based feature) vectors
along with the country information for $\approx$80K randomly sampled sequences
from the set of 2,384,646 sequences (Table 1) used in this study.

The rate of spread of the $3$ most common variants of SARS-CoV-2 (in the USA)
from March $2020$ to July $2021$ from our data are given in Figure 4. We can
see that the Alpha variant was clearly the variant of concern when it reached
its peak in April $2021$. We can see a drop from this peak for all variants
after April $2021$. This is likely because a significant proportion of the
population were vaccinated by this point, hence the total number of cases
started decreasing Ali and Patterson (2021).

Figure 4: The rate of spread of the $3$ most common SARS-CoV-2 variants (in
the USA) from March $2020$ till July $2021$.

###  4.3 Experimental Setup

All experiments are conducted using an Intel(R) Xeon(R) CPU E7-4850 v4 @
$2.10$GHz having Ubuntu $64$ bit OS ($16.04.7$ LTS Xenial Xerus) with 3023 GB
memory. The implementation of our algorithms is done in Python and the code is
available online for reproducibility
111https://github.com/sarwanpasha/COVID-19-Country-Classification. We obtain a
set of 2,384,646 spike amino acid sequences from the GISAID GISAID Website .
The GISAID provides many different metadata for these sequences, such as
collection date, geographical location, and sometimes variant information.
which can be used after agreeing to the terms and conditions of
GISAID222Available at https://www.gisaid.org/. For the classification
algorithms, we use $10\%$ of the data for training and $90\%$ for testing. The
purpose of using a smaller training dataset is to show how much performance
gain we can achieve while using minimal training data.

##  5 Results and Discussion

In this section, we present results for three different granularities of class
labels, namely continents, countries, and finally states in a case study of
the United States of America (USA).

###  5.1 Continent Classification

In this section, we show classification results for $5$ different continents,
namely Europe, North America, South America, Asia, and Australia (see Table
1). The classification results (average $\pm$ standard deviation of 5 runs)
are given in Table 2. In terms of predictive performance, we can observe that
the NN model with the $k$-mers based embedding performs best compared to the
baselines. While comparing the two embedding methods (_i.e._ , OHE and
$k$-mers), we can see that $k$-mers is better than OHE for the NN model. Since
$k$-mers can preserve the order of amino acids better as compared to the OHE,
it is able to give richer information in the feature vector. In terms of
runtime, RC with the Spike2Vec embedding is performing best. The NN model will
take longer to train the models compared to simple ML classifiers because of
the tuning of different parameters.

Approach | Embed. Method | Algo. |  Accuracy |  Precision |  Recall |  $F_{1}$ weigh. |  $F_{1}$ Macro |  ROC-AUC | Training runtime (sec.)
---|---|---|---|---|---|---|---|---|---
MAJORITY | _ | _ |  0.60 $\pm$ 0.000 |  0.36 $\pm$ 0.000 |  0.60 $\pm$ 0.000 |  0.45 $\pm$ 0.000 |  0.15 $\pm$ 0.000 |  0.50 $\pm$ 0.000 | _
Feature Engineering | OHE | NB |  0.49 $\pm$ 0.005 |  0.63 $\pm$ 0.006 |  0.49 $\pm$ 0.005 |  0.50 $\pm$ 0.007 |  0.38 $\pm$ 0.006 |  0.63 $\pm$ 0.005 | 1457.2 $\pm$ 0.023
LR |  0.67 $\pm$ 0.007 |  0.66 $\pm$ 0.008 |  0.67 $\pm$ 0.007 |  0.64 $\pm$ 0.007 |  0.33 $\pm$ 0.008 |  0.58 $\pm$ 0.005 | 1622.4 $\pm$ 0.031
RC |  0.67 $\pm$ 0.004 |  0.66 $\pm$ 0.005 |  0.67 $\pm$ 0.004 |  0.64 $\pm$ 0.006 |  0.28 $\pm$ 0.004 |  0.57 $\pm$ 0.005 | 1329.1 $\pm$ 0.029
Spike2Vec | NB |  0.48 $\pm$ 0.007 |  0.63 $\pm$ 0.006 |  0.48 $\pm$ 0.008 |  0.49 $\pm$ 0.007 |  0.36 $\pm$ 0.007 |  0.63 $\pm$ 0.006 | 970.6 $\pm$ 0.065
LR |  0.67 $\pm$ 0.005 |  0.67 $\pm$ 0.007 |  0.67 $\pm$ 0.006 |  0.64 $\pm$ 0.007 |  0.34 $\pm$ 0.006 |  0.58 $\pm$ 0.005 | 1141.9 $\pm$ 0.072
RC |  0.67 $\pm$ 0.003 |  0.66 $\pm$ 0.004 |  0.67 $\pm$ 0.003 |  0.64 $\pm$ 0.003 |  0.29 $\pm$ 0.006 |  0.57 $\pm$ 0.007 |  832.3 $\pm$ 0.057
NN | OHE | Neural Network |  0.75 $\pm$ 0.007 |  0.76 $\pm$ 0.008 |  0.75 $\pm$ 0.008 |  0.72 $\pm$ 0.009 |  0.47 $\pm$ 0.007 |  0.65 $\pm$ 0.008 | 30932.0 $\pm$ 0.105
$k$-mers | Neural Network |  0.77 $\pm$ 0.009 |  0.78 $\pm$ 0.008 |  0.77 $\pm$ 0.009 |  0.74 $\pm$ 0.007 |  0.49 $\pm$ 0.008 |  0.65 $\pm$ 0.009 | 18631.7 $\pm$ 0.235

Table 2: Continent classification results (average $\pm$ standard deviation of
5 runs) for $5$ continents comprising 2,384,646 spike sequences (10% training
set and 90% testing set). Best average values are shown in bold.

###  5.2 Country Classification

After classifying the continents, we take countries as the class label and
train all ML and NN models again with the same parameter settings. The
classification results (average $\pm$ standard deviation of 5 runs) for
countries is given in Table 3. In terms of predictive performance, we can
observe that the NN model is performing better than all baselines. In terms of
runtime, RC with the OHE is the best classifier. An important observation here
is the drop in overall performance of all classification models as compared to
the continent classification. The reason for this behavior is likely due to
any natural clustering or other information in the spike sequences
corresponding to the location of patients breaking down at this level of
granularity. This lack of knowledge in the data makes country classification a
difficult task. However, we can see that the NN model can still classify the
countries better than the baselines.

Approach | Embed. Method | Algo. |  Accuracy |  Precision |  Recall |  $F_{1}$ weigh. |  $F_{1}$ Macro |  ROC-AUC | Training runtime (sec.)
---|---|---|---|---|---|---|---|---|---
MAJORITY | _ | _ |  0.27 $\pm$ 0.000 |  0.07 $\pm$ 0.000 |  0.27 $\pm$ 0.000 |  0.12 $\pm$ 0.000 |  0.01 $\pm$ 0.000 |  0.50 $\pm$ 0.000 | _
Feature Engineering | OHE | NB |  0.11 $\pm$ 0.007 |  0.44 $\pm$ 0.008 |  0.11 $\pm$ 0.007 |  0.11 $\pm$ 0.007 |  0.10 $\pm$ 0.009 |  0.55 $\pm$ 0.008 | 1308.4 $\pm$ 0.098
LR |  0.40 $\pm$ 0.009 |  0.46 $\pm$ 0.009 |  0.40 $\pm$ 0.008 |  0.33 $\pm$ 0.007 |  0.15 $\pm$ 0.008 |  0.55 $\pm$ 0.009 | 2361.8 $\pm$ 0.074
RC |  0.40 $\pm$ 0.006 |  0.38 $\pm$ 0.007 |  0.40 $\pm$ 0.006 |  0.31 $\pm$ 0.008 |  0.11 $\pm$ 0.007 |  0.54 $\pm$ 0.006 |  746.4 $\pm$ 0.085
Spike2Vec | NB |  0.13 $\pm$ 0.004 |  0.41 $\pm$ 0.005 |  0.13 $\pm$ 0.004 |  0.151 $\pm$ 0.006 |  0.109 $\pm$ 0.005 |  0.555 $\pm$ 0.007 | 1315.3 $\pm$ 0.085
LR |  0.40 $\pm$ 0.006 |  0.45 $\pm$ 0.006 |  0.40 $\pm$ 0.007 |  0.33 $\pm$ 0.008 |  0.16 $\pm$ 0.007 |  0.55 $\pm$ 0.006 | 2736.8 $\pm$ 0.058
RC |  0.39 $\pm$ 0.006 |  0.37 $\pm$ 0.007 |  0.39 $\pm$ 0.006 |  0.31 $\pm$ 0.008 |  0.11 $\pm$ 0.006 |  0.54 $\pm$ 0.007 | 779.4 $\pm$ 0.074
NN | OHE | Neural Network |  0.49 $\pm$ 0.009 |  0.53 $\pm$ 0.008 |  0.49 $\pm$ 0.009 |  0.43 $\pm$ 0.009 |  0.24 $\pm$ 0.007 |  0.6 $\pm$ 0.006 | 28914.8 $\pm$ 0.453
$k$-mers | Neural Network |  0.51 $\pm$ 0.005 |  0.57 $\pm$ 0.004 |  0.51 $\pm$ 0.005 |  0.45 $\pm$ 0.006 |  0.28 $\pm$ 0.006 |  0.60 $\pm$ 0.007 | 10383.6 $\pm$ 0.745

Table 3: Country classification results (average $\pm$ standard deviation of 5
runs) for $27$ countries comprising 2,384,646 spike sequences (10% training
set and 90% testing set). Best average values are shown in bold.

###  5.3 A Case Study of the United States of America (USA)

After classifying continents and countries, we investigate our model with more
highly granular class labels. For this purpose, we first take the single
country with the highest number of spike sequences in the data. Since the USA
contains most of the spike sequences in our data (see Table 1), we took it as
a case study to further explore different states within the USA. The pie chart
showing the distribution of the sequences over the states of the USA is given
in Figure 5. The classification results (average $\pm$ standard deviation of 5
runs) for different states are given in Table 4. We can again observe the drop
in predictive performance for all models. This again proves that as we
increase the granularity of the class labels, it becomes difficult for any
model to classify with higher accuracy. We can also observe that the NN model
with the $k$-mers based feature embedding is performing better than all the
baselines.

Figure 5: Distribution of the 663,527 sequences over the states of the USA,
with the top 11 states specified, while the remaining fall into the “others”
category.

Approach | Embed. Method | Algo. |  Accuracy |  Precision |  Recall |  $F_{1}$ weigh. |  $F_{1}$ Macro |  ROC-AUC | Training runtime (sec.)
---|---|---|---|---|---|---|---|---|---
MAJORITY | _ | _ |  0.33 $\pm$ 0.000 |  0.11 $\pm$ 0.000 |  0.33 $\pm$ 0.000 |  0.17 $\pm$ 0.000 |  0.04 $\pm$ 0.000 |  0.50 $\pm$ 0.000 | _
Feature Engineering | OHE | NB |  0.18 $\pm$ 0.005 |  0.32 $\pm$ 0.006 |  0.18 $\pm$ 0.004 |  0.14 $\pm$ 0.005 |  0.13 $\pm$ 0.006 |  0.54 $\pm$ 0.007 | 860.2 $\pm$ 0.745
LR |  0.37 $\pm$ 0.007 |  0.45 $\pm$ 0.008 |  0.37 $\pm$ 0.007 |  0.26 $\pm$ 0.007 |  0.13 $\pm$ 0.008 |  0.53 $\pm$ 0.006 | 1036.2 $\pm$ 0.458
RC |  0.37 $\pm$ 0.008 |  0.41 $\pm$ 0.008 |  0.37 $\pm$ 0.007 |  0.25 $\pm$ 0.009 |  0.12 $\pm$ 0.005 |  0.52 $\pm$ 0.007 | 707.7 $\pm$ 0.865
Spike2Vec | NB |  0.19 $\pm$ 0.005 |  0.37 $\pm$ 0.005 |  0.19 $\pm$ 0.004 |  0.14 $\pm$ 0.006 |  0.14 $\pm$ 0.006 |  0.55 $\pm$ 0.007 | 273.7 $\pm$ 0.124
LR |  0.38 $\pm$ 0.008 |  0.44 $\pm$ 0.007 |  0.38 $\pm$ 0.007 |  0.29 $\pm$ 0.006 |  0.16 $\pm$ 0.007 |  0.54 $\pm$ 0.008 | 374.2 $\pm$ 0.865
RC |  0.37 $\pm$ 0.006 |  0.42 $\pm$ 0.006 |  0.37 $\pm$ 0.004 |  0.27 $\pm$ 0.005 |  0.14 $\pm$ 0.008 |  0.53 $\pm$ 0.007 |  197.1 $\pm$ 0.657
NN | OHE | Neural Network |  0.38 $\pm$ 0.011 |  0.44 $\pm$ 0.012 |  0.38 $\pm$ 0.011 |  0.34 $\pm$ 0.013 |  0.22 $\pm$ 0.015 |  0.57 $\pm$ 0.010 | 7881.3 $\pm$ 0.857
$k$-mers | Neural Network |  0.47 $\pm$ 0.017 |  0.50 $\pm$ 0.016 |  0.47 $\pm$ 0.014 |  0.42 $\pm$ 0.017 |  0.33 $\pm$ 0.015 |  0.61 $\pm$ 0.017 | 4908.6 $\pm$ 0.975

Table 4: Classification results (average $\pm$ standard deviation of 5 runs)
for different states of the USA (10% training set and 90% testing set). The
best average values are shown in bold.

###  5.4 Importance of Attributes

To evaluate the importance of the positions in the spike sequences, we find
the importance of each attribute with respect to class label (using the Weka
tool333Available at https://www.cs.waikato.ac.nz/ml/weka/). For this purpose,
a randomly selected a subset of spike sequences ($\approx$80K) is taken from
the original dataset. We then compute the information gain (IG) between each
attribute ($P=$ amino acid position) and the true class label ($C=$ country).
More formally, IG can be computed as

$IG(C,P)=H(C)-H(C|P),$ (1)

where $H(C)$ and $H(C|P)$ are entropy and conditional entropy, respectively.
The entropy $H$ can be calculated using

$H=\sum_{i\in C}-p_{i}\log p_{i},$ (2)

where $p_{i}$ is the probability of the class $i$. The IG values for each
attribute are given in Figure 6. The IG values for each attribute are also
available online444Available at
https://github.com/sarwanpasha/COVID-19-Country-
Classification/blob/main/attributes_correlation.csv.

Figure 6: Information gain for each amino acid position corresponding to the
class.

##  6 Conclusion

This paper employs several machine learning models using a $k$-mers based
representation as input and efficiently classifies SARS-CoV-2 spike sequences
based on geographical location. We show that our proposed approach outperforms
the baselines in terms of predictive performance. Using information gain, we
also show the importance of attributes (amino acids) in the spike sequences.
Such classification and its analysis can help researchers to study more deeply
the connection between geographical location and SARS-CoV-2 variants. In the
future, we will explore more sophisticated models like LSTM and GRU, and also
use other attributes like months information to increase the predictive
performance, and maybe give an idea of the dynamics (spread) of the virus over
time. Using other alignment-free methods such as minimizers is another
possible future direction.

## Acknowledgements

Paper was originally deposited to arXiv: https://arxiv.org/abs/2110.00809

## Author Contribution Statement

SA, MP: Conceptualization. SA: Methodology. SA: Software. SA, ZT: Validation.
SA, MP: Formal Analysis. SA, BB, ZT: Investigation. All: Resources. All: Data
Curation. All: Writing - Original Draft. All: Writing - Review & Editing. SA:
Visualization. SA, MP: Supervision. MP: Project Administration. MP: Funding
Acquisition.

## Conflict of Interest

The authors declare no conflict of interest.

## Funding Statement

Research supported by an MBD Fellowship for SA, and a Georgia State University
Computer Science start-up grant for MP.

## References

  * Ahmad et al. [2016] M. Ahmad, J. Tariq, M. Farhan, M. Shabbir, and I. Khan.  Who should receive the vaccine?  In _Australasian Data Mining Conference (AusDM)_ , pages 137–145, 2016.
  * Ahmad et al. [2017] M. Ahmad, J. Tariq, M. Shabbir, and I. Khan.  Spectral methods for immunization of large networks.  _Australasian Journal of Information Systems_ , 21, 2017.
  * Ahmad et al. [2020] M. Ahmad, S. Ali, J. Tariq, I. Khan, M. Shabbir, and A. Zaman.  Combinatorial trace method for network immunization.  _Information Sciences_ , 519:215 – 228, 2020.
  * Ali et al. [2019] S. Ali, H. Mansoor, N. Arshad, and I. Khan.  Short term load forecasting using smart meter data.  In _International Conference on Future Energy Systems (e-Energy)_ , pages 419–421, 2019.
  * Ali et al. [2020a] S. Ali, M. Alvi, S. Faizullah, M. Khan, A. Alshanqiti, and I. Khan.  Detecting DDoS attack on SDN due to vulnerabilities in OpenFlow.  In _International Conference on Advances in the Emerging Computing Technologies (AECT)_ , pages 1–6, 2020a.
  * Ali et al. [2020b] S. Ali, H. Mansoor, I. Khan, N. Arshad, M. Khan, and S. Faizullah.  Short-term load forecasting using ami data.  _CoRR_ , abs/1912.12479, 2020b.
  * Ali et al. [2021a] S. Ali, M. Shakeel, I. Khan, S. Faizullah, and M. Khan.  Predicting attributes of nodes using network structure.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ , 12(2):1–23, 2021a.
  * Ali and Patterson [2021] Sarwan Ali and Murray Patterson.  Spike2vec: An efficient and scalable embedding approach for COVID-19 spike sequences.  In _IEEE International Conference on Big Data (Big Data)_ , pages 1533–1540, 2021.
  * Ali et al. [2021b] Sarwan Ali, Tamkanat E Ali, Muhammad Asad Khan, Imdadullah Khan, and Murray Patterson.  Effective and scalable clustering of SARS-CoV-2 sequences.  In _International Conference on Big Data Research (ICBDR)_ , pages 42–49, 2021b.
  * Ali et al. [2021c] Sarwan Ali, Simone Ciccolella, Lorenzo Lucarella, Gianluca Della Vedova, and Murray Patterson.  Simpler and faster development of tumor phylogeny pipelines.  _Journal of Computational Biology_ , 28(11):1142–1155, 2021c.
  * Ali et al. [2021d] Sarwan Ali, Bikram Sahoo, Naimat Ullah, Alexander Zelikovskiy, Murray Patterson, and Imdadullah Khan.  A k-mer based approach for SARS-CoV-2 variant identification.  In _International Symposium on Bioinformatics Research and Applications_ , pages 153–164, 2021d.
  * Atzori et al. [2014] M. Atzori et al.  Electromyography data for non-invasive naturally-controlled robotic hand prostheses.  _Scientific Data_ , 1(1):1–13, 2014.
  * Blaisdell [1986] B. Blaisdell.  A measure of the similarity of sets of sequences not requiring sequence alignment.  _Proceedings of the National Academy of Sciences_ , 83:5155–5159, 1986.
  * Brodin et al. [2015] Petter Brodin, Vladimir Jojic, Tianxiang Gao, Sanchita Bhattacharya, Cesar J Lopez Angel, David Furman, Shai Shen-Orr, Cornelia L Dekker, Gary E Swan, Atul J Butte, et al.  Variation in the human immune system is largely driven by non-heritable influences.  _Cell_ , 160(1-2):37–47, 2015.
  * Dhar et al. [2020] S. Dhar et al.  Tnet: Phylogeny-based inference of disease transmission networks using within-host strain diversity.  In _International Symposium on Bioinformatics Research and Applications (ISBRA)_ , pages 203–216, 2020.
  * Farhan et al. [2017] M. Farhan, J. Tariq, A. Zaman, M. Shabbir, and I. Khan.  Efficient approximation algorithms for strings kernel based sequence classification.  In _Advances in neural information processing systems (NeurIPS)_ , pages 6935–6945. ., 2017.
  * Farinholt et al. [2021] Timothy Farinholt, Harsha Doddapaneni, Xiang Qin, Vipin Menon, Qinchang Meng, Ginger Metcalf, Hsu Chao, Marie-Claude Gingras, Paige Farinholt, Charu Agrawal, et al.  Transmission event of SARS-CoV-2 delta variant reveals multiple vaccine breakthrough infections.  _medRxiv_ , 2021.
  * [18] GISAID Website.  https://www.gisaid.org/.
  * Grover and Leskovec [2016] A. Grover and J. Leskovec.  node2vec: Scalable feature learning for networks.  In _International Conference on Knowledge Discovery & Data Mining (KDD)_, pages 855–864, 2016.
  * Hassan et al. [2020] Z. Hassan, M. Shabbir, I. Khan, and W. Abbas.  Estimating descriptors for large graphs.  In _Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)_ , pages 779–791, 2020.
  * Hassan et al. [2021] Zohair Raza Hassan, Imdadullah Khan, Mudassir Shabbir, and Waseem Abbas.  Computing graph descriptors on edge streams.  _CoRR_ , arXiv:2109.01494, 2021.
  * Hu et al. [2021] Ben Hu, Hua Guo, Peng Zhou, and Zheng-Li Shi.  Characteristics of SARS-CoV-2 and COVID-19.  _Nature Reviews Microbiology_ , 19(3):141–154, 2021.
  * Huang et al. [2020] Yuan Huang, Chan Yang, Xin-feng Xu, Wei Xu, and Shu-wen Liu.  Structural and functional properties of SARS-CoV-2 spike protein: potential antivirus drug development for COVID-19.  _Acta Pharmacologica Sinica_ , 41(9):1141–1149, 2020.
  * Korber et al. [2020] Bette Korber, Will M Fischer, Sandrasegaram Gnanakaran, Hyejin Yoon, James Theiler, Werner Abfalterer, Nick Hengartner, Elena E Giorgi, Tanmoy Bhattacharya, Brian Foley, et al.  Tracking changes in SARS-CoV-2 spike: evidence that D614G increases infectivity of the COVID-19 virus.  _Cell_ , 182(4):812–827, 2020.
  * Krishnan et al. [2021] G. Krishnan, S. Kamath, and V. Sugumaran.  Predicting vaccine hesitancy and vaccine sentiment using topic modeling and evolutionary optimization.  In _International Conference on Applications of Natural Language to Information Systems (NLDB)_ , pages 255–263, 2021.
  * Kuksa et al. [2012] P. Kuksa, I. Khan, and V. Pavlovic.  Generalized similarity kernels for efficient sequence classification.  In _SIAM International Conference on Data Mining (SDM)_ , pages 873–882, 2012.
  * Kuzmin et al. [2020] K. Kuzmin et al.  Machine learning methods accurately predict host specificity of coronaviruses based on spike sequences alone.  _Biochemical and Biophysical Research Communications_ , 533:553–558, 2020.
  * Lamers et al. [2020] Mart M Lamers, Joep Beumer, Jelte van der Vaart, Kèvin Knoops, Jens Puschhof, Tim I Breugem, Raimond BG Ravelli, J Paul Van Schayck, Anna Z Mykytyn, Hans Q Duimel, et al.  SARS-CoV-2 productively infects human gut enterocytes.  _Science_ , 369(6499):50–54, 2020.
  * Leslie et al. [2003] C. Leslie, E. Eskin, J. Weston, and W. Noble.  Mismatch string kernels for SVM protein classification.  In _Advances in neural information processing systems (NeurIPS)_ , pages 1441–1448, 2003.
  * Liston et al. [2016] Adrian Liston, Edward J Carr, and Michelle A Linterman.  Shaping variation in the human immune system.  _Trends in immunology_ , 37(10):637–646, 2016\.
  * Lorenzo-Redondo et al. [2020] Ramon Lorenzo-Redondo, Hannah H Nam, Scott C Roberts, Lacy M Simons, Lawrence J Jennings, Chao Qi, Chad J Achenbach, Alan R Hauser, Michael G Ison, Judd F Hultquist, et al.  A unique clade of SARS-CoV-2 viruses is associated with lower viral loads in patient upper airways.  _MedRxiv_ , 2020.
  * Pachetti et al. [2020] Maria Pachetti, Bruna Marini, Francesca Benedetti, Fabiola Giudici, Elisabetta Mauro, Paola Storici, Claudio Masciovecchio, Silvia Angeletti, Massimo Ciccozzi, Robert C Gallo, et al.  Emerging SARS-CoV-2 mutation hot spots include a novel RNA-dependent-RNA polymerase variant.  _Journal of translational medicine_ , 18(1):1–9, 2020.
  * Pezzotti et al. [2016] Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens Van Der Maaten, Thomas Höllt, Elmar Eisemann, and Anna Vilanova.  Approximated and user steerable tSNE for progressive visual analytics.  _IEEE transactions on visualization and computer graphics_ , 23(7):1739–1752, 2016.
  * Rahimi et al. [2007] Ali Rahimi, Benjamin Recht, et al.  Random features for large-scale kernel machines.  In _NIPS_ , volume 3, page 5, 2007.
  * Rochman et al. [2021] Nash D Rochman, Yuri I Wolf, Guilhem Faure, Pascal Mutz, Feng Zhang, and Eugene V Koonin.  Ongoing global and regional adaptive evolution of SARS-CoV-2.  _Proceedings of the National Academy of Sciences_ , 118(29), 2021.
  * [36] SARS-CoV-2 Variant Classifications and Definitions.  https://www.cdc.gov/coronavirus/2019-ncov/variants/variant-info.html.
  * Segovia-Dominguez et al. [2021] Ignacio Segovia-Dominguez, Zhiwei Zhen, Rishabh Wagh, Huikyo Lee, and Yulia R. Gel.  TLife-LSTM: Forecasting future COVID-19 progression with topological signatures of atmospheric conditions.  In _Advances in Knowledge Discovery and Data Mining_ , pages 201–212, Cham, 2021. Springer International Publishing.  ISBN 978-3-030-75762-5.
  * Shakeel et al. [2019] Muhammad Haroon Shakeel, Asim Karim, and Imdadullah Khan.  A multi-cascaded deep model for bilingual SMS classification.  In _International Conference on Neural Information Processing_ , pages 287–298, 2019.
  * Shakeel et al. [2020a] Muhammad Haroon Shakeel, Safi Faizullah, Turki Alghamidi, and Imdadullah Khan.  Language independent sentiment analysis.  In _International Conference on Advances in the Emerging Computing Technologies (AECT)_ , pages 1–5, 2020a.
  * Shakeel et al. [2020b] Muhammad Haroon Shakeel, Asim Karim, and Imdadullah Khan.  A multi-cascaded model with data augmentation for enhanced paraphrase detection in short texts.  _Information Processing & Management_, 57(3):102204, 2020b.
  * Tariq et al. [2017] J. Tariq, M. Ahmad, I. Khan, and M. Shabbir.  Scalable approximation algorithm for network immunization.  In _Pacific Asia Conference on Information Systems (PACIS)_ , page 200, 2017.
  * Ullah et al. [2020] A. Ullah, S. Ali, I. Khan, M.A. Khan, and S. Faizullah.  Effect of analysis window and feature selection on classification of hand movements using emg signal.  In _SAI Intelligent Systems Conference (IntelliSys)_ , pages 400–415, 2020.
  * Van der M. and Hinton [2008] L. Van der M. and G. Hinton.  Visualizing data using t-SNE.  _Journal of Machine Learning Research (JMLR)_ , 9(11), 2008\.
  * V’kovski et al. [2021] Philip V’kovski, Annika Kratzel, Silvio Steiner, Hanspeter Stalder, and Volker Thiel.  Coronavirus biology and replication: implications for SARS-CoV-2.  _Nature Reviews Microbiology_ , 19(3):155–170, 2021.
  * Wang et al. [2020] Changtai Wang, Zhongping Liu, Zixiang Chen, Xin Huang, Mengyuan Xu, Tengfei He, and Zhenhua Zhang.  The establishment of reference sequence for SARS-CoV-2 and variation analysis.  _Journal of medical virology_ , 92(6):667–674, 2020.
  * Wold et al. [1987] S. Wold, K. Esbensen, and P. Geladi.  Principal component analysis.  _Chemometrics and intelligent laboratory systems_ , 2(1-3):37–52, 1987.
  * Wu et al. [2020] Fan Wu, Su Zhao, Bin Yu, Yan-Mei Chen, Wen Wang, Zhi-Gang Song, Yi Hu, Zhao-Wu Tao, Jun-Hua Tian, Yuan-Yuan Pei, et al.  A new coronavirus associated with human respiratory disease in china.  _Nature_ , 579:265–269, 2020.
  * Zhang [2018] Zijun Zhang.  Improved adam optimizer for deep neural networks.  In _2018 IEEE/ACM 26th International Symposium on Quality of Service (IWQoS)_ , pages 1–2, 2018.


#  Characteristic functions for (r, n)-free and (f, g)-free elements

Himangshu Hazarika  Department of Mathematics, Behali Degree College, Borgang,
Biswanath, Assam, India<EMAIL_ADDRESS>and  Dhiren Kumar Basnet
Department of Mathematical Sciences, Tezpur University, Assam, India
<EMAIL_ADDRESS>
###### Abstract.

For a prime power $q$, $\mathbb{F}_{q}$ denotes the finite field of order $q$,
and for $m\geq 2$, $\mathbb{F}_{q^{m}}$ denotes the extension field of degree
$m$. We establish a characteristic function for the set of $(r,\,n)$-free
elements of finite cyclic $R$-module for the Euclidean domain $R$.
Furthermore, we explore $(f,\,g)$-freeness through polynomial values and
finally give an expression for the characteristic function for the set of
$(f,\,g)$-free elements.

###### Key words and phrases:

Finite field, Character sums, (r, n)-free element, (f, g)-free element

###### 2010 Mathematics Subject Classification:

11T30, 11T23, 11A07

##  1\. Introduction

For a prime power $q$, $\mathbb{F}_{q}$ denotes the finite field of order $q$
and for $m\geq 2$, $\mathbb{F}_{q^{m}}$ denotes the extended field of order
$q^{m}$. The multiplicative group $\mathbb{F}_{q^{m}}^{*}$ is a cyclic group
whose generators are called _primitive_ elements of $\mathbb{F}_{q^{m}}$. For
$e|q^{m}-1$, $\alpha\in\mathbb{F}_{q^{m}}^{*}$ is called $e$-free element if
$d|e$ and $\alpha=\beta^{d}$, for some $\beta\in\mathbb{F}_{q^{m}}^{*}$ imply
$d=1$. Furthermore $\alpha$ is primitive element if and only if it is
$(q^{n}-1)$-free elements. Further, an element $\alpha\in\mathbb{F}_{q^{m}}$
is called _normal_ element of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$, if
its Galois orbit i.e., $\\{\alpha,\alpha^{q},\ldots,\alpha^{q^{n-1}}\\}$ forms
a basis of $\mathbb{F}_{q^{m}}$ over $\mathbb{F}_{q}$.

The problem of constructing an algorithm to find a primitive element of a
finite field is one of the major open problems in finite field theory. Hence,
researchers focus on relatively unchallenging problem, i.e., to create an
algorithm to find an element of higher multiplicative order. This problem
becomes more useful as the elements of higher multiplicative order may replace
primitive elements in various applications. One of the notable work of Gao [3]
who established algorithm for elements of higher order in $\mathbb{F}_{q^{m}}$
with $m^{log_{q}m/(4log_{q}(2log_{q}m))-1/2}$ as the lower bound of the order.
Later Popovych estimated lower bounds on elements of higher multiplicative
orders of finite fields in [4]. Then Cohen, Kapetanakis and Reis defined
$(r,\,n)$-free elements for finite fields and studied various properties of
$(r,\,n)$-free elements in [2]. They provided the characteristic function for
the $(r,\,n)$-free elements, which is an extension of Vinogradov’s formula for
the characteristic function for primitive elements. From which we generalise
the notions of $(r,\,n)$-free and $(f,\,g)$-free elements of the finite cyclic
module. Next we establish the characteristic functions and prove some results
for $(r,\,n)$-free and $(f,\,g)$-free elements of the finite cyclic module.

In this article, we generalise $(r,n)$-free and $(f,g)$-free elements of the
finite cyclic module. In the Section 2, we recall the definition of
$n$-primitive elements and its characteristic function. Furthermore, we
discuss the definition of $(r,\,n)$-free elements, introduced by Cohen,
Kapetanakis and Reis [2] along with some basic properties. In Section 3, we
explore the finite cyclic $R$-module. Then we establish some results with
additive module in Section 4. In Section 5 we define $(f,g)$-free elements and
provide some properties. Finally, in Section 6, we define $(f,g)$-freeness of
elements through polynomial values and establish some additional results.

##  2\. Preparation

We begin this section with some definitions.

######  Definition 2.1.

If $n|q^{m}-1$, then an element $\alpha\in\mathbb{F}_{q^{m}}$ is called _n-
primitive_ element, if it is of order $(q^{m}-1)/n$. So primitive elements are
nothing but 1-primitive elements.

The characteristic function of $n$-free elements is given by Carlitz in [1],
as following.

######  Lemma 2.1.

If $M$ is a divisor of $q^{m}-1$, the characteristic function for the set of
elements with multiplicative order $M$ in $\mathbb{F}_{q^{m}}$ is

$\Psi_{M}(\alpha)=\frac{M}{q^{m}-1}\underset{d|M}{\sum}\frac{\mu(d)}{d}\underset{ord(\kappa)|\frac{d(q^{m}-1)}{M}}{\sum}\kappa(\alpha),$
(2.1)

where the sum runs over all the characters $\kappa$ such that
$\mathrm{ord}(\kappa)$ divides $d(q^{m}-1)/M$.

For a multiplicative cyclic group, Cohen _et al._ provided the following
result in [2, Lemma 2.5].

######  Lemma 2.2.

For positive integers $r,\,n$,

$T(r,n):=\underset{l|r}{\sum}\frac{|\mu(l_{(n)})|}{\phi(l_{(n)})}.\phi(l)=\mathrm{gcd}(r,n).W(\mathrm{gcd}(r,r_{(n)})),$

where $W(k)$ is the number of square-free divisors of $k$ and
$x_{(y)}=\frac{x}{\mathrm{gcd}(x,\,y)}.$

###  $(r,\,n)$-free elements

Following concepts are provided by Cohen, Kapetanakis and Reis in [2].

######  Definition 2.2.

Let $C_{Q}$ denote a multiplicative cyclic group of order $Q$. Let $n$ be a
divisor of $Q$ and $r$ be a divisor of $Q/n$. Then an element $\alpha\in
C_{Q}$ is called $(r,\,n)$-free if the following hold:

  * (i)

$\alpha$ is in the subgroup $C_{Q/n}$, i.e.,
$\mathrm{ord}(\alpha)|\frac{Q}{n}$;

  * (ii)

$\alpha$ is $r$-free in $C_{Q/n}$, i.e., if $\alpha=\beta^{a}$ with $\beta\in
C_{Q/n}$ and $a|r$, then $a=1$.

######  Lemma 2.3.

_[2, Lemma 3.3]_ Let $n$ be a divisor of $Q$ and $r$ be a divisor of $Q/n$. An
element $\alpha\in C_{Q}$ is $(r,\,n)$-free if and only if $\alpha=\beta^{n}$
for some $\beta\in C_{Q}$ but $\alpha$ is not of the form $\beta^{np}_{0}$
where $\beta_{0}\in C_{Q}$, for every prime divisor $p$ of $r$. In particular,
$\alpha\in C_{Q}$ is $(r,\,n)$-free if and only if
$\mathrm{gcd}\left(rn,\,\frac{Q}{\mathrm{ord}(\alpha)}\right)=n$.

In the next section, we provide some results for finite cyclic $R$-module.

##  3\. Finite cyclic $R$-module

Let $R$ be an Euclidean domain and $\mathfrak{M}$ be a finite cyclic
$R$-module, under the rule $r\,o\,\alpha$, where $r\in R$ and
$\alpha\in\mathfrak{M}$. Let $g\in\mathfrak{M}$ be a generator of
$\mathfrak{M}$. Since $\mathfrak{M}$ has similar properties as abelian group,
hence $\widehat{\mathfrak{M}}$ can be defined as an $R$-module, under the
rule, $r\,o\,\psi\,:\,\alpha\,\mapsto\,\psi(r\,o\,\alpha)$, for
$\alpha\in\mathfrak{M}$ and $\psi\in\widehat{\mathfrak{M}}$. In this article,
whenever a sum runs through the divisors of some element of $R$ or when a
condition is applicable to all the members of a conjugacy class of $R/\sim$,
we will consider just one representative, as an element of $R$ and will treat
as same with its conjugates that hold the equivalence relation $r\sim
s\Leftrightarrow r=us$, for some $u\in R^{*}$.

For $\alpha\in\mathfrak{M}$, from the properties of $R$ and $\mathfrak{M}$, we
have that the annihilator of $\alpha$ is an ideal of $R$, hence it has a
unique generator. This annihilator is called the _order_ of $\alpha$ and we
denote it with $\mathrm{ord}(\alpha)$. We set $m:=ord(g)$.

For $d\in R$, the Euler function is defined as $\phi(d)=|(R/dR)^{*}|$.

For $a,b\in R$, we denote $a_{(b)}$ as

$a_{(b)}=\frac{a}{gcd(a,b)}.$

######  Lemma 3.1.

Let $r\in R$ and $b$ is a divisor of $m$. An element $\alpha\in\mathfrak{M}$
is of the form $r\circ\beta$ with $ord(\beta)=b$ if and only if
$ord(\alpha)=b_{(n)}$, where $n=\mathrm{gcd}(r,\,m)$.

###### Proof.

$(\Rightarrow)$ Let $\alpha\in\mathfrak{M}$ be of the form $r\circ\beta$ with
$ord(\beta)=b$. Then $b$ is the generator of the ideal (ideal of annihilators
of $\beta$) in R. Then $\alpha=r\circ\beta$ has order
$\frac{b}{\mathrm{gcd}(b,\,r)}=\frac{b}{\mathrm{gcd}(b,\,n)}=b_{(n)}$.

$(\Leftarrow)$ Let $\mathrm{ord}(\alpha)=b_{(n)}$, where
$n=\mathrm{gcd}(r,\,m)$. To show $\alpha\in\mathfrak{M}$ is of the form
$r\circ\beta$ with $\mathrm{ord}(\beta)=b$.

Consider the set $A_{b}=\\{r\circ\beta|\mathrm{ord}(\beta)=b\\}.$ Then the
cardinality of the set is $\phi(b_{(n)})$. Now for any element $\delta$ of
order $b$, the elements of $A_{b}$ are $i\circ(r\circ\delta)=(ir)\circ\delta$,
where $\mathrm{gcd}(i,\,b)=1$. So we have, $(ir)\circ\delta=(jr)\circ\delta$
if and only if $i=j+yb_{(n)}$, for some $y\in R$, i.e., $i\equiv
j(\mathrm{mod}(b_{(n)}))$. (This $\mathrm{mod}$ is analogous to
$natural\,mod$.)

Therefore the cardinality of the set $A_{b}$ is the number of in-congruent
$x(\mathrm{mod}(b_{(n)}))$, as $x\in R$ such that $\mathrm{gcd}(x,\,b)=1$.
Since $b_{(n)}$ divides $b$, hence cardinality is $\phi(b_{(n)})$.

This completes the proof. ∎

######  Lemma 3.2.

For $n,\,r\in R$, we have that,

$T(r,\,n):=\underset{t|r}{\sum}\frac{|\mu(t_{(n)})|}{\phi(t_{(n)})}.\phi(t)=\left|\left(R/\alpha
R\right)\right|.W\left(\left|\left(R/\beta R\right)\right|\right),$

where $\alpha=\mathrm{gcd}(n,\,r)$, $\beta=\mathrm{gcd}(r,\,r_{(n)})$ and
$W(a)$ denotes the number of square free divisors of $a$.

###### Proof.

We have $f_{n}(r):=\frac{|\mu(t_{(n)})|}{\phi(t_{(n)})}.\phi(t)$ and
$g_{n}(r):=\left|\left(R/\alpha R\right)\right|.W\left(\left|\left(R/\beta
R\right)\right|\right)$, which are multiplicative functions in $R$. Hence the
same holds for $T(n,\,r)$ and hence it suffices to prove the equality
$T(n,\,r)=g_{n}(r)$ in the case, where $r$ is a prime power in $R$. We use
$r=p^{a}$, where $p$ is a prime in $R$ and $a$ is the exponent of $p$ such
that $a\in\mathbb{N}$. We write $n=p^{b}n_{0}$, where $b$ is an integer with
$b\geq 0$ and $\mathrm{gcd}(p,\,n_{0})=1$. Now we have the following cases.

  * (i)

If $b=0$, we have $\mathrm{gcd}(r,\,n)=1$, $r_{(n)}=r$ i.e.,
$\alpha=1,\,\beta=r.$

$T(n,\,r)=\underset{t|r}{\sum}\frac{|\mu(t_{(n)})|}{\phi(t_{(n)})}.\phi(t)=\phi(1)+\frac{|\mu(p)|}{\phi(p)}\phi(p)=2,$

and
$g_{n}(r)=\left|\left(R/R\right)\right|.W\left(\left|\left(R/p^{a}R\right)\right|\right)=W\left(\left|\left(R/pR\right)\right|^{a}\right)=W\left(\left|\left(R/pR\right)\right|\right)=2.$

  * (ii)

If $0<b\leq a$, then we have $\mathrm{gcd}(n,\,r)=p^{b}$ and
$r_{(n)}=p^{a-b}$, i.e. $\alpha=p^{b}$ and $\beta=p^{a-b}$ if $b<a$, $\beta=1$
if $b=a$.

Then for $b<a$,
$T(n,\,r)=\underset{i=0}{\overset{b}{\sum}}\phi(p^{i})+\underset{i=b+1}{\overset{a}{\sum}}\frac{|\mu(p^{i-b})|}{\phi(p^{i-b})}\phi(p^{i})=\underset{i=0}{\overset{b}{\sum}}\phi(p^{i})+\frac{1}{\phi(p)}\phi(p^{b+1})=2|(R/p^{b}R)|.$

If $b=a$, then $T(n,\,r)=|(R/p^{b}R)|.$

When $b<a$, $\alpha=p^{b}$ and $\beta=p^{a-b}$ and hence
$g_{n}(r)=\left|\left(R/p^{b}R\right)\right|.W\left(\left|\left(R/p^{a-b}R\right)\right|\right)=\left|\left(R/p^{b}R\right)\right|.W\left(\left|\left(R/pR\right)\right|^{a-b}\right)=\left|\left(R/p^{b}R\right)\right|.W\left(\left|\left(R/pR\right)\right|\right)=2\left|\left(R/p^{b}R\right)\right|.$

Similarly, when $b=a$, then $\alpha=p^{b}$ and $\beta=1$. In this case
$g_{n}(r)=|(R/p^{b}R)|.$

  * (iii)

If $b>a$, then $\mathrm{gcd}(n,\,r)=p^{a}$ and $r_{(n)}=1$, i.e.
$\alpha=p^{a}$, $\beta=1.$ Then
$T(n,\,r)=\underset{i=0}{\overset{a}{\sum}}\frac{|\mu(1)|}{\phi(1)}\phi(p^{i})=|(R/p^{a}R)|.$
For $\alpha=p^{a}$, $\beta=1$, $g_{n}(r)=|(R/p^{a}R)|$.

∎

Next we have the characteristic function for the set of elements in
$\mathfrak{M}$ with order $n$.

######  Lemma 3.3.

_[2, Lemma 3.4]_ If $n$ is a divisor of $m$, then the characteristic function
for the set of elements in $\mathfrak{M}$ with order $n$ can be expressed as

$\Lambda_{n}(\omega)=\frac{|(R/nR)|}{|\mathfrak{M}|}\underset{d|n}{\sum}\frac{\mu(n)}{|(R/dR)|}\underset{ord(\chi)=d}{\sum}\chi(\omega).$

######  Lemma 3.4.

For $r=m/n$ with $n$ is a divisor of $m$, the above function can be rewritten
as

$\Lambda_{n}(\omega)=\frac{\phi(m/n)}{|\mathfrak{M}|}\underset{t|m}{\sum}\frac{\mu(t_{(n)})}{\phi(t_{(n)})}\underset{ord(\chi)=t}{\sum}\chi(\omega).$

###  3.1. Generalised $(r,\,n)$-free elements

Following is the definition of Generalised $(r,\,n)$-free elements.

######  Definition 3.1.

Let $r$ and $n$ be two divisors of $m$. An element $x\in\mathfrak{M}$ is
called $(r,\,n)$-free if $ord(a)|\frac{m}{\mathrm{gcd}(r,\,n)}$ and if
$x=d\circ y$ for some $y\in\mathfrak{M}$ with
$ord(y)|\frac{m}{\mathrm{gcd}(r,\,n)}$ and $d|r_{(n)}$, implies $d=1$.

######  Lemma 3.5.

Let $r,\,n$ be two divisors of $m$. Let $a\in\mathfrak{M}$ be such that
$ord(a)|\frac{m}{\mathrm{gcd}(r,\,n)}$. Then $a$ is $(r,\,n)$-free if and only
if $\mathrm{gcd}(r,\,n)=\mathrm{gcd}(r,\,\frac{m}{ord(a)})$.

###### Proof.

Clearly it suffices to prove that
$\mathrm{gcd}\left(r_{(n)},\frac{m}{\mathrm{gcd}(r,\,n)ord(a)}\right)=1$. We
take $b\in\mathfrak{M}$ of order $\frac{m}{\mathrm{gcd}(r,\,m)}$. Then
$a=k\circ b$ for some $k\in R$, while
$ord(a)=\left(\frac{m}{\mathrm{gcd}(r,\,n)\mathrm{gcd}\left(k,\frac{m}{\mathrm{gcd}(r,\,n)}\right)}\right).$

($\Rightarrow$) Let $a$ be $(r,\,n)$-free such that
$\mathrm{gcd}\left(r_{(n)},\frac{m}{\mathrm{gcd}(r,\,n)ord(a)}\right)\neq 1$.

Then
$\mathrm{gcd}\left(r_{(n)},\mathrm{gcd}\left(k,\frac{m}{\mathrm{gcd}(r,\,n)}\right)\right)\neq
1$ i.e., $\mathrm{gcd}\left(r_{(n)},k,\frac{m}{\mathrm{gcd}(r,\,n)}\right)\neq
1,$ i.e. $k=k_{0}k_{1},$ for some $k_{0}\in R$ such that $k_{0}\neq 1$ and
$k_{0}\,|\,\mathrm{gcd}\left(r_{(n)},\frac{m}{\mathrm{gcd}(r,\,n)}\right).$

Thus $a=k\circ b=(k_{0}k_{1})\circ b=k_{0}\circ(k_{1}\circ b).$ Since $a$ is
$(r,\,n)$-free, this implies $k_{0}=1,$ a contradiction.

($\Leftarrow$) Let
$\mathrm{gcd}\left(r_{(n)},\frac{m}{\mathrm{gcd}(r,\,n)ord(a)}\right)=1$. Take
some $\beta\in\mathfrak{M}$ such that
$ord(\beta)|\frac{m}{\mathrm{gcd}(r,\,n)},$ $a=d\circ\beta$ and $d|r_{(n)}.$
It suffices to show that $d=1$.

First we have $\beta=i\circ b$, for some $i\in R$. It follows that $a=k\circ
b=d\circ(i\circ b)=(di)\circ b$. Now $ord(b)=\frac{m}{\mathrm{gcd}(r,\,n)}$
and $k\circ b=(di)\circ b$, where $b\in\mathfrak{M}$ and $k,di\in R.$ Since
$R$ is ED, there exists $t\in R$ such that
$k=di+t\frac{m}{\mathrm{gcd}(r,n)}$. Since $d|di$ and
$d|\frac{m}{\mathrm{gcd}(r,\,n)}$, hence $d|k$. We have
$\mathrm{gcd}\left(r_{(n)},\frac{m}{\mathrm{gcd}(r,\,n)ord(a)}\right)=1$ i.e.
$\mathrm{gcd}\left(r_{(n)},k,\frac{m}{\mathrm{gcd}(r,\,n)}\right)=1$ and
combining the facts that $d|k$ and $d|\frac{m}{\mathrm{gcd}(r,\,n)}$ we get
$d=1$.

∎

######  Lemma 3.6.

Let $t|m$ and $x\in\mathfrak{M}$. Then

$\underset{ord(\chi)|t}{\sum}\chi(x)=\begin{cases}|(R/tR)|,\,\mbox{ if
}\,t|\frac{m}{ord(x)},\\\ 0,\,\mbox{ otherwise}.\end{cases}$

This can be proved from orthogonality relations. Finally, we define the
characteristic function for the set of $(r,\,n)$-free elements in
$\mathfrak{M}$ by

$\Lambda_{r,n}(x)=\frac{\phi(r_{(n)})}{|(R/rR)|}\underset{t|r}{\sum}\frac{\mu(t_{(n)})}{\phi(t_{(n)})}\underset{ord(\chi)=t}{\sum}\chi(x),x\in\mathfrak{M},$

as character sum expression.

We prove the following lemma to support our claim.

######  Lemma 3.7.

Let $x\in\mathfrak{M}$, then

$\Lambda_{r,n}(x)=\begin{cases}1,\,\mbox{ if }x\mbox{ is
}(r,\,n)\mbox{-free},\\\ 0,\,\mbox{ otherwise}.\end{cases}$

###### Proof.

Let $r=p_{1}^{e_{1}}p_{2}^{e_{2}}\ldots p_{k}^{e_{k}}$ be a prime
factorisation of $r$ in $R$ and exponents $e_{i}\neq 0$. It follows from the
definition that $\omega$ is $(r,\,n)$-free if and only if it is
$(p_{i}^{e_{i}},\,n)$-free for each $i=1,2,\ldots,k$. Moreover we have
$\Lambda_{e_{1}e_{2},n}(\omega)=\Lambda_{e_{1},n}(\omega)\Lambda_{e_{2},n}(\omega).$
It follows that, it suffices to restrict our case to $r=p^{s}$, where $p$ is
irreducible over $R$ and $s\neq 0$.

Consider the case $p^{s}\nmid n$, then $\mathrm{gcd}(p^{s},n)=p^{t}$, for some
$0\leq t<s.$ So $p^{s}_{(n)}=p^{s-t}$.

$\Lambda_{p^{s},n}(\omega)=\frac{\phi(p^{s}_{(n)})}{|(R/p^{s}R)|}\underset{i=0}{\overset{s}{\sum}}\frac{\mu(p^{i}_{(n)})}{\phi(p^{i}_{(n)})}\underset{ord(\psi)=p^{i}}{\sum}\psi(\omega).$

Now

$\displaystyle\underset{i=0}{\overset{s}{\sum}}\frac{\mu(p^{i}_{(n)})}{\phi(p^{i}_{(n)})}\underset{ord(\psi)=p^{i}}{\sum}\psi(\omega)=$
$\displaystyle\underset{i=0}{\overset{t}{\sum}}\frac{\mu(p^{i}_{(n)})}{\phi(p^{i}_{(n)})}\underset{ord(\psi)=p^{i}}{\sum}\psi(\omega)+\frac{\mu(p^{t+1}_{(n)})}{\phi(p^{t+1}_{(n)})}\underset{ord(\psi)=p^{t+1}}{\sum}\psi(\omega)$
$\displaystyle=$
$\displaystyle\underset{i=0}{\overset{t}{\sum}}\underset{ord(\psi)=p^{i}}{\sum}\psi(\omega)-\frac{1}{\phi(p)}\underset{ord(\phi)=p^{t+1}}{\sum}\psi(\omega)$
$\displaystyle=$
$\displaystyle\underset{ord(\psi)|p^{t}}{\sum}\psi(\omega)-\frac{1}{\phi(p)}\underset{ord(\psi)=p^{t+1}}{\sum}\psi(\omega).$

Hence

$\Lambda_{p^{s},n}(\omega)=\frac{\phi(p^{s}_{(n)})}{|(R/p^{s}R)|}\left(\underset{ord(\psi)|p^{t}}{\sum}\psi(\omega)-\frac{1}{\phi(p)}\underset{ord(\psi)=p^{t+1}}{\sum}\psi(\omega)\right).$
(3.1)

Now, let $\nu_{p}(g)$ stands for the exponent of the prime $p$ in the prime
factorisation of $g$. Now $\omega$ is $(p^{s},\,n)$-free if and only if
$t=\nu_{p}(m)-\nu_{p}(ord(\omega))$.

If $\omega$ is $(p^{s},\,n)$-free, then the above equality and Lemma 3.6 imply
that

$\underset{ord(\chi)|p^{t}}{\sum}\chi(\omega)=\left|\left(R/p^{s}R\right)\right|$
and $\underset{ord(\chi)|p^{t+1}}{\sum}\chi(\omega)=0$, which yields
$\underset{ord(\chi)=p^{t+1}}{\sum}\chi(\omega)=-\left|\left(R/p^{s}R\right)\right|$.

Now, from the Equation (3.1), we have $\Lambda_{p^{s},n}(\omega)=1$.

Next assume that $\omega$ is not $(p^{s},\,n)$-free. This means
$t>\nu_{p}(m)-\nu_{p}(ord(\omega))$ or $t<\nu_{p}(m)-\nu_{p}(ord(\omega))$.

Now, for the case $t>\nu_{p}(m)-\nu_{p}(ord(\omega))$, we have
$p^{t}\nmid\frac{m}{ord(\omega)}$. By Lemma 3.6, we have
$\underset{ord(\chi)|p^{t}}{\sum}\chi(\omega)=\underset{ord(\chi)=p^{t+1}}{\sum}\chi(\omega)=0.$
Hence from Equation (3.1), $\Lambda_{p^{s},n}=0.$

Finally if $t<\nu_{p}(m)-\nu_{p}(ord(\omega))$, by Lemma 3.6, we have
$\underset{ord(\chi)|p^{t}}{\sum}\chi(\omega)=\left|\left(R/p^{t}R\right)\right|$
and
$\underset{ord(\chi)=p^{t+1}}{\sum}\chi(\omega)=\phi(p^{t+1})=\left|\left(R/p^{t}R\right)\right|\left(1-\frac{1}{\left|\left(R/pR\right)\right|}\right)$.

Now, we discuss the case $p^{s}|n$. In this case $\mathrm{gcd}(p^{s},n)=p^{s}$
and $p^{s}_{(n)}=1$. Therefore

$\Lambda_{p^{s},n}(\omega)=\frac{\phi(p^{s}_{(n)})}{\left|\left(R/p^{t}R\right)\right|}\underset{i=0}{\overset{s}{\sum}}\frac{\mu(p^{i}_{(n)})}{\phi(p^{i}_{(n)})}\underset{ord(\chi)=p^{i}}{\sum}\chi(\omega)=\frac{1}{\left|\left(R/p^{t}R\right)\right|}\underset{ord(\chi)|p^{s}}{\sum}\chi(\omega).$
(3.2)

In this case $\omega$ is $(p^{s},\,n)$-free if and only if
$p^{s}|\frac{m}{ord(\omega)}$. Along with this and from Lemma 3.6, we have
that $\Lambda_{p^{s},n}(\omega)=1$ if $\omega$ is $(p^{s},n)$-free and
$\Lambda_{p^{s},n}(\omega)=0$, otherwise.

∎

##  4\. Additive module

The additive group of $\mathbb{F}_{q^{m}}$ can be viewed as an
$\mathbb{F}_{q}[x]$-module
$\mathfrak{F}\,o\,x\,:=\,\underset{i=0}{\overset{n}{\sum}}F_{i}x^{q^{i}}$,
where
$\mathfrak{F}(X)=\underset{i=0}{\overset{n}{\sum}}F_{i}X^{i}\in\mathbb{F}_{q}[X]$.
From the normal basis theorem, it is clear that the $\mathbb{F}_{q}[x]$-module
is cyclic, and normal elements or free elements are generators of the module.

For $\alpha\in\mathbb{F}_{q^{m}}$, the unique monic polynomial polynomial $g$
of the least degree dividing $x^{m}-1$ is said to be $\mathbb{F}_{q}$-order of
$\alpha$ if $g\circ\alpha=0$. Throughout this section, we denote $Ord(\alpha)$
as the $\mathbb{F}_{q}$-order of $\alpha\in\mathbb{F}_{q^{m}}$. For any
element $\alpha$ in some extension of $\mathbb{F}_{q}$,
$(x^{m}-1)\circ\alpha=\alpha^{q^{m}}-\alpha=0$ if and only if
$\alpha\in\mathbb{F}_{q^{m}}$. If we set
$I_{\alpha}=\\{g(x)\in\mathbb{F}_{q}[x]\mid g\circ\alpha=0\\}$, then
$I_{\alpha}$ is an ideal of $\mathbb{F}_{q}[x]$ and hence generated by a
polynomial, say $h_{\alpha}(x)$ (we require $h_{\alpha}(x)$ to be monic). Then
$h_{\alpha}(x)$ is the $\mathbb{F}_{q}$-order of $\alpha$. It is clear that
$Ord(\alpha)\in\mathbb{F}_{q}[x]$ and $Ord(\alpha)|x^{m}-1$.

For $f,g\in\mathbb{F}_{q}[x]$, we denote $f_{(g)}$ as

$f_{(g)}=\frac{f}{\mathrm{gcd}(f,\,g)}.$

If $f\in\mathbb{F}_{q}[x]$, $f=\underset{i=0}{\overset{s}{\sum}}a_{i}x^{i}$,
we define $L_{f}(x)=\underset{i=0}{\overset{s}{\sum}}a_{i}x^{q^{i}}$ as
$q$-associate of $f$. Also for $\alpha\in\mathbb{F}_{q^{m}}$, let
$f\circ\alpha=L_{f}(\alpha)=\underset{i=0}{\overset{s}{\sum}}a_{i}\alpha^{q^{i}}$.
For $f,g\in\mathbb{F}_{q}[x]$, the following hold.

  * (i)

$L_{f}(L_{g}(x))=L_{fg}(x).$

  * (ii)

$L_{f}(x)+L_{g}(x)=L_{f+g}(x).$

######  Lemma 4.1.

Let $f\in\mathbb{F}_{q}[x]$ and $g\in\mathbb{F}_{q}[x]$ be a divisor of
$x^{m}-1$. An element $\alpha\in\mathbb{F}_{q^{m}}$ is of the form
$f\circ\beta$ with $Ord(\beta)=g$ if and only if $Ord(\alpha)=g_{(h)}$, where
$h=\mathrm{gcd}(f,x^{m}-1)$.

Proof of this lemma is similar to that of Lemma 3.1.

######  Lemma 4.2.

Let $f,g\in\mathbb{F}_{q^{m}}[x]$, then we have

$T(f,g):=\underset{t|f}{\sum}\frac{|\mu(t_{(g)})|}{\Phi(t_{(g)})}.\Phi(t)=\left|\frac{\mathbb{F}_{q}[x]}{l\mathbb{F}_{q}[x]}\right|.W\left(\left|\frac{\mathbb{F}_{q}[x]}{h\mathbb{F}_{q}[x]}\right|\right)=\left(q^{deg(l)}\right).W\left(q^{deg(h)}\right),$

where $l=\mathrm{gcd}(f,g)$ and $h=\mathrm{gcd}(f,f_{(g)})$, $W(n)$ denotes
the number of square free divisors of $n$.

Proof of this lemma is similar to that of Lemma 3.2.

##  5\.  $(f,\,g)$-free element

######  Definition 5.1.

Let $f,g\in\mathbb{F}_{q}[x]$ be divisors of $x^{m}-1$. An element
$\alpha\in\mathbb{F}_{q^{m}}$ is called $(f,\,g)$-free if
$Ord(\alpha)\mid\frac{x^{m}-1}{\mathrm{gcd}(f,\,g)}$ and $\alpha=h\circ\beta$,
for some $\beta\in\mathbb{F}_{q^{m}}$ with
$Ord(\beta)\mid\frac{x^{m}-1}{\mathrm{gcd}(f,\,g)}$ and $h|f_{(g)}$, imply
$h=1$.

Then we have the following.

######  Lemma 5.1.

Let $f,\,g\in\mathbb{F}_{q}[x]$ be divisors of $x^{m}-1$. Let
$\alpha\in\mathbb{F}_{q^{m}}$ be such that
$Ord(\alpha)\mid\frac{x^{m}-1}{\mathrm{gcd}(f,\,g)}$. Then $\alpha$ is
$(f,\,g)$-free if and only if
$\mathrm{gcd}(f,\,g)=\mathrm{gcd}(f,\,\frac{x^{m}-1}{Ord(\alpha)})$.

The proof is similar to Lemma 3.5.

######  Lemma 5.2.

Let $t|x^{m}-1$ and we take some $\omega\in\mathbb{F}_{q^{m}}$. Then

$\underset{Ord(\psi)|t}{\sum}\psi(\omega)=\begin{cases}\left|\frac{\mathbb{F}_{q}[x]}{<t>}\right|\,\mbox{or
}\,q^{deg(t)},\,\mbox{ if }\,t\mid\frac{x^{m}-1}{Ord(\omega)},\\\ 0,\,\mbox{
otherwise}.\end{cases}$

######  Definition 5.2.

Now we define the function

$\Omega_{f,g}(\omega)=\frac{\Phi(f_{(g)})}{q^{deg(f)}}\underset{h|f}{\sum}\frac{\mu(h_{(g)})}{\Phi(h_{(g)})}\underset{Ord(\psi)=h}{\sum}\psi(\omega),\,\omega\in\mathbb{F}_{q^{m}}$

and prove it to be characteristic function for $(f,\,g)$-free elements of
$\mathbb{F}_{q^{m}}$.

######  Lemma 5.3.

Let $\omega\in\mathbb{F}_{q^{m}}$, then

$\Omega_{f,g}(\omega)=\begin{cases}1,\,\mbox{ if }\omega\mbox{ is
}(f,\,g)\mbox{-free},\\\ 0,\,\mbox{ otherwise}.\end{cases}$

The proof is similar as Lemma 3.7.

##  6\.  $(f,\,g)$-freeness through polynomial values

For divisors $f,\,F,\,g,\,G$ of $x^{m}-1$ and polynomials
$h,\,H\in\mathbb{F}_{q^{m}}[x]$, we study the number of pairs $(h(y),\,H(y))$
such that $h(y)$ is $(f,\,g)$-free and $H(y)$ is $(F,\,G)$-free with
$y\in\mathbb{F}_{q^{m}}$. This number can be zero if $h(x)$ and $H(x)$ have
certain additive dependence with respect to the polynomials $h,\,H$.

Following is the definition of dependence for polynomials in
$\mathbb{F}_{q^{m}}[x].$

######  Definition 6.1.

Let $f,\,F\in\mathbb{F}_{q^{m}}[x]$ be divisors of $x^{m}-1$ and let
$h,\,H\in\mathbb{F}_{q^{m}}[x]$ be non constant polynomials. The pair
$(h,\,H)$ is $(f,\,F)$-independent if for every $t|f$ and $T|F$ with
$l=\mathrm{lcm}(t,\,T)\neq 1$ (we choose $t,\,T$ to be monic) and $1\leq
deg(c)\leq deg(t)$ and $1\leq deg(C)\leq deg(T)$ with
$\mathrm{gcd}(t,\,c)=\mathrm{gcd}(T,\,C)=1$, the polynomial
$L_{\frac{lc}{t}}(h(x))+L_{\frac{lC}{T}}(H(x))$ is not of the form
$L_{l}(g(x))+k$, for some $g\in\mathbb{F}_{q}[x]$ and
$k\in\mathbb{F}_{q^{m}}$.

We continue with the following proposition.

######  Proposition 6.1.

With the terms and conditions as above, if
$\mathfrak{G}(x)=L_{\frac{lc}{t}}(h(x))+L_{\frac{lC}{T}}(H(x))$ is not of the
form $L_{l}(g(x))+k$ for any $g(x)\in\mathbb{F}_{q}[x]$ and for any
$k\in\mathbb{F}_{q^{m}}$, then $\mathfrak{G}(x)$ is definitely not of the form
$a(x)^{p}-a(x)+b$, for any $a(x)\in\mathbb{F}_{q}[x]$ and
$b\in\mathbb{F}_{q^{m}}$, where $q=p^{n}$ for some positive integer $n$.

######  Lemma 6.2.

Let $f,\,F\in\mathbb{F}_{q^{m}}[x]$ be divisors of $x^{m}-1$. If the pair
$(h,\,H)$ is not $(f,\,F)$-independent, then there exist divisors
$r,\,R\in\mathbb{F}_{q^{m}}[x]$ of $x^{m}-1$ in a way that there is no element
$\theta\in\mathbb{F}_{q^{m}}$ such that $h(\theta)$ is $(f,\,r)$-free and
$H(\theta)$ is $(F,\,R)$-free.

###### Proof.

Since $(h,\,H)$ is not $(f,\,F$)-independent, there exist some $t|f$ and $T|F$
with $l=\mathrm{lcm}(t,\,T)\neq 1$ and $1\leq deg(c)\leq deg(t)$ and $1\leq
deg(C)\leq deg(T)$ with $\mathrm{gcd}(t,\,c)=\mathrm{gcd}(T,\,C)=1$, such that
for some $g\in\mathbb{F}_{q^{m}}[x]$ and $k\in\mathbb{F}_{q^{m}}[x]$

$L_{\frac{lc}{t}}(h(x))+L_{\frac{lC}{T}}(H(x))=L_{l}(g(x))+k.$

Then for every $\theta\in\mathbb{F}_{q^{m}}$ we have

$\left(\frac{lc}{t}\right)\circ h(\theta)+\left(\frac{lC}{T}\right)\circ
H(\theta)=l\circ g(\theta)+k.$

Then multiplying by $\frac{x^{m}-1}{l}$ we have

$\frac{(x^{m}-1)c}{t}\circ h(\theta)+\frac{(x^{m}-1)C}{T}\circ
H(\theta)=\left(\frac{x^{m}-1}{l}\right)\circ k.$ (6.1)

First we consider the case $t\neq T$ (we have already chosen $t,T$ as monic).
From the Equation (6.1), we have

$\frac{T(x^{m}-1)c}{t}\circ h(\theta)=\frac{T(x^{m}-1)}{l}\circ k$ and
$\frac{t(x^{m}-1)C}{T}\circ H(\theta)=\frac{t(x^{m}-1)}{l}\circ k$

Since right hand sides are inverses of one another, hence we have

$\displaystyle\frac{Ord(h(\theta))}{\mathrm{gcd}\left(Ord(h(\theta)),\frac{x^{m}-1}{t}.T.c\right)}=\frac{Ord(H(\theta))}{\mathrm{gcd}\left(Ord(H(\theta)),\frac{x^{m}-1}{T}.t.C\right)}$
$\displaystyle\Leftrightarrow
t.\mathrm{gcd}\left(T,\frac{x^{m}-1}{Ord(H(\theta))}.t.C\right)=T.\mathrm{gcd}\left(t,\frac{x^{m}-1}{Ord(h(\theta))}.T.c\right).$

We divide both the parts of above by $\mathrm{gcd}(t,\,T)$ and get

$t.\mathrm{gcd}\left(T_{(t)},\frac{x^{m}-1}{Ord(H(\theta))}.t_{(T)}.C\right)=T.\mathrm{gcd}\left(t_{(T)},\frac{x^{m}-1}{Ord(h(\theta))}.T_{(t)}.c\right).$

Since $\mathrm{gcd}(t_{(T)},T_{(t)}.c)=\mathrm{gcd}(T_{(t)},t_{(T)}.C)=1$, the
above equation becomes

$t.\mathrm{gcd}\left(T_{(t)},\frac{x^{m}-1}{Ord(H(\theta))}\right)=T.\mathrm{gcd}\left(t_{(T)},\frac{x^{m}-1}{Ord(h(\theta))}\right).$
(6.2)

If possible, let there be some $\theta\in\mathbb{F}_{q^{m}}$, such that
$h(\theta)$ is $(f,r)$-free and $H(\theta)$ is $(F,R)$-free, for some divisors
$r,R\in\mathbb{F}_{q^{m}}[x]$ of $x^{m}-1$. Using Lemma 5.1, we have
$\mathrm{gcd}\left(f,\frac{x^{m}-1}{Ord(h(\theta))}\right)=\mathrm{gcd}(f,r)$.
Then combining this with the fact that $t_{(T)}|f$, we have that
$\mathrm{gcd}\left(t_{(T)},\frac{x^{m}-1}{Ord(h(\theta))}\right)=\mathrm{gcd}(t_{(T)},r).$
Similarly we have
$\mathrm{gcd}\left(T_{(t)},\frac{x^{m}-1}{Ord(H(\theta))}\right)=\mathrm{gcd}(T_{(t)},R).$
Then Equation (6.2) gives

$t.\mathrm{gcd}(T_{(t)},R)=T.\mathrm{gcd}(t_{(T)},r).$ (6.3)

Since $t\neq T$, without loss of generality we assume that there is some non
constant monic polynomial $d\in\mathbb{F}_{q^{m}}[x]$ such that $d|t_{(T)}$.
Now we choose $R=T_{(t)}$ and $r=\frac{t_{(T)}}{d}$, then Equation (6.3)
yields $\frac{tT}{\mathrm{gcd}(t,T)}=\frac{tT}{d\,\mathrm{gcd}(t,T)}$, a
contradiction.

Now we have the case $t=T$. In this case, Equation (6.1) becomes

$\frac{(x^{m}-1)c}{l}\circ h(\theta)+\frac{(x^{m}-1)C}{l}\circ
H(\theta)=\frac{(x^{m}-1)}{l}\circ k$.

Let us set $r=R=l$. In this case if $h(\theta)$ is $(f,\,l)$-free, then its
$\mathbb{F}_{q}$-order divides $\frac{x^{m}-1}{l}$, hence
$\frac{(x^{m}-1)c}{l}\circ h(\theta)=0$. Similarly $\frac{(x^{m}-1)C}{l}\circ
H(\theta)=0$ and hence their sum must be zero i.e., $\frac{x^{m}-1}{l}\circ
k=0$. Then identical arguments lead us to Equation (6.3), i.e.,

$t.\mathrm{gcd}(T,\,R)=T.\mathrm{gcd}(t,\,r).$

Since $\mathrm{lcm}(t,\,T)$ is non constant monic polynomial in
$\mathbb{F}_{q^{m}}[x]$, hence without loss of generality we may assume that
there exists some non constant $e\in\mathbb{F}_{q^{m}}[x]$ such that $e|t$.
Now we choose $R=T$ and $r=\frac{t}{e}$, then above yields $tT=\frac{tT}{e}$,
a contradiction.

This completes the proof.

∎

######  Theorem 6.3.

Let $f,\,F,\,r,\,R\in\mathbb{F}_{q^{m}}[x]$ be divisors of $x^{m}-1$ and for
$h,\,H\in\mathbb{F}_{q^{m}}[x]$, the pair $(h,\,H)$ is $(f,\,F)$-independent.
Let $D+1\geq 1$ be the number of distinct roots of $h(x)+H(x)$ in its
splitting field over $\mathbb{F}_{q}$. The number
$\mathfrak{N}_{h,\,H}=\mathfrak{N}_{h,\,H}(f,F,r,R)$ of elements
$\theta\in\mathbb{F}_{q^{m}}$ such that $h(\theta)$ is $(f,\,r)$-free and
$H(\theta)$ is $(F,\,R)$-free satisfies

$\mathfrak{N}_{h,H}=\frac{\Phi(f_{(r)})\Phi(F_{(R)})}{q^{deg(f)}q^{deg(F)}}\left(q+M(f,r,F,R)\right),$

with $|M(f,r,F,R)|\leq Dq^{m/2}Q_{f,r}Q_{F,R}$, where
$Q_{g,h}:=\left|\frac{\mathbb{F}_{q}[x]}{<k>}\right|.W\left(\left|\frac{\mathbb{F}_{q}[x]}{<y>}\right|\right)$
with $k=gcd(g,h)$, $y=\mathrm{gcd}(g,g_{(h)})$.

###### Proof.

By definition we have,
$\mathfrak{N}_{h,H}=\underset{\omega\in\mathbb{F}_{q^{m}}}{\sum}\Omega_{f,r}(h(\omega))\Omega_{F,R}(H(\omega))$.
From the characteristic function $\Omega$, for
$A=\frac{\Phi(f_{(r)})\Phi(F_{(R)})}{q^{deg(f)}q^{deg(F)}}$ , we have that

$\displaystyle\mathfrak{N}_{h,H}/A$
$\displaystyle=\underset{\omega\in\mathbb{F}_{q^{m}}}{\sum}\left(\underset{t|f}{\sum}\frac{\mu(t_{(r)})}{\Phi(t_{(r)})}\underset{Ord(\psi)}{\sum}\psi(h(\omega))\right)\left(\underset{T|F}{\sum}\frac{\mu(T_{(R)})}{\Phi(T_{(R)})}\underset{Ord(\kappa)}{\sum}\kappa(H(\omega))\right)$
$\displaystyle=\underset{\underset{T|F}{t|f}}{\sum}\frac{\mu(t_{(r)})\mu(T_{(R)})}{\Phi(t_{(r)})\Phi(T_{(R)})}\underset{Ord(\kappa)=T,Ord(\psi)=t}{\sum}G_{h,H}(\psi,\kappa),$

where
$G_{h,H}=\underset{\omega\in\mathbb{F}_{q^{m}}}{\sum}\psi(h(\omega))\kappa(H(\omega))$.

Fix $t|f$ and $T|F$ (we choose $t,T$ to be monic), let $\psi,\kappa$ be
additive characters of $\mathbb{F}_{q}$-orders $t$ and $T$ respectively, and
set $l=\mathrm{lcm}(t,\,T)$. Then

$\psi(h(\omega))\kappa(H(\omega))=\widetilde{\psi}\left(\left(\frac{cl}{t}\right)\circ
h(\omega)+\left(\frac{Cl}{T}\right)\circ H(\omega)\right),$

for some additive character $\widetilde{\psi}$ of $\mathbb{F}_{q}$-order $l$
and some polynomials $c,C$ such that $1\leq deg(c)\leq deg(t)$ and $1\leq
deg(C)\leq deg(T)$ with $\mathrm{gcd}(t,\,c)=\mathrm{gcd}(T,\,C)=1$.

Since the pair $(h,\,H)$ is $(f,\,F)$-independent, the polynomial
$\mathfrak{G}(x)=L_{\frac{cl}{t}}(h(x))+L_{\frac{Cl}{T}}(H(x))$ is of the form
$L_{l}(g(x))+k$ if and only if $l=1$ i.e. $t=T=1$. Therefore from Weil’s
theorem we have $|G_{h,H}(\psi,\kappa)|\leq Dq^{m/2}$ whenever
$(t,\,T)=(1,\,1)$.

For $t=T=1$, we observe that $\psi$ and $\kappa$ are just the trivial additive
characters and so $G_{h,H}(\psi,\kappa)=q^{m}-\varepsilon$, where
$\varepsilon$ is the number of the roots of $h(x)+H(x)$ defined over
$\mathbb{F}_{q^{m}}$. Since $\varepsilon\leq D+1$, we have

$\left|\mathfrak{N}_{h,H}/A-q^{m}\right|\leq D+1+Dq^{m/2}E,$

where
$E=\underset{\underset{(t,T)\neq(1,1)}{t|f,T|F}}{\sum}\frac{\mu(t_{(r)})\mu(T_{(R)})}{\Phi(t_{(r)})\Phi(T_{(R)})}\underset{Ord(\kappa)=T}{\underset{Ord(\psi)=t}{\sum}}1=T(f,\,r)T(F,\,R)-1$.

Where $T(f,\,g)$ is as in Lemma 4.2 and according to the Lemma 6.2, we have
the equality $T(f,\,g)=Q_{f,\,g}$ and so

$\left|\mathfrak{N}_{h,H}/A-q^{m}\right|\leq
D+1+Dq^{m/2}(Q_{f,r}Q_{F,R}-1)<Dq^{m/2}Q_{f,r}Q_{F,R}$

from where the result follows.

∎

######  Corollary 6.3.1.

Let $f,\,F,\,r,\,R,\,h,\,H$ as in the above theorem.

If $q^{m/2}\geq DQ_{f,r}Q_{F,R}$, then $\mathfrak{N}_{h,H}>0.$

## References

  * [1] Carlitz, L. Primitive roots in a finite fields. _Transactions of the American Mathematical Society_ , 73(3):314-318, 1952.
  * [2] Cohen, S. D., Kapetanakis, G. and Reis, L. The existence of $\mathbb{F}_{q}$-primitive points on curves using freeness. _Comptes Rendus. Mathématique_ , 360, 641-652, 2022.
  * [3] Gao, S. Elements of provable high orders in finite fields. _Proceedings of the American Mathematical Society_ , 127(6), 1615–1623, 1999.
  * [4] Popovych, R. Elements of high order in finite fields of the form $\mathbb{F}_{q}[x]/\Phi_{r}(x)$. _Finite Fields and Their Applications_ , 18(4), 700–710, 2012.
  * [5] Lidl, R. and Niederreiter, H. _Finite Fields_. Cambridge University Press,Cambridge, 2nd edition, 1997.