# Fairness in AI Systems: Mitigating gender bias from language-vision models

Lavisha Aggarwal, Shruti Bhargava

([-1600])

## 1\. Introduction

Our society is plagued by several biases, including racial biases, caste
biases, and gender bias. As a matter of fact, several years ago, most of these
notions were unheard of. These are human creations that passed through
generations, with much amplification leading to the scenario wherein several
biases have taken the role of expected norms or required laws by certain
groups in the society. One notable example is of gender bias. The notion about
the role of a man, and that of a woman have taken different forms across the
globe. Whether we talk about the corporate world, political scenarios or daily
lifestyle, some generic differences are observed regarding the involvement of
both the groups. This differential distribution, being a part of the society
at large, exhibits its presence even in the recorded data. Now, the field of
machine learning is completely dependent on the available data. The idea of
learning from data and making predictions based on that assumes that the data
defines the expected behaviour at large. This is a huge obstacle in the path
for creating a world with equality and justice. This work studies and attempts
to alleviate the gender bias issues from the task of image captioning.

## 2\. Motivation and Related Work

The motivation for this project stems from the recent paper T. et al. (2016)
highlighting the rampant gender bias severely infecting most of the present
day machine learning and natural language based models. They experimented with
word analogies and found that due to the inherent bias present in the training
data, relations were developed between certain kind of activities or objects
and gender words (’man’- ’doctor’, ’woman’-’homemaker’ etc.) leading to
incorrect inferences. It is observed that this gender bias in datasets is a
demonstration of societal behaviours, owing to the skewed data distributions
in existing datasets, and also from the human annotators’ prejudices,
responsible for labelling the datasets [Selvaraju et al. (2016)][Veit et al.
(2017)][van Miltenburg (2016)][Antol et al. (2015)]. These biased data result
in biased models (for example the Word2Vec word embeddings) which are further
used for more advanced models and tasksKafle and Kanan (2017) Zhang et al.
(2015).

### 2.1 Gender Bias via human annotation

We manually analysed the MS-COCO dataset and found some disturbing ground-
truth annotations for the captions. Several images, wherein there is a
partially visible human who can’t be distinguished as a man or woman, most
human annotators use their bias about the expected (or more common) gender
from the activity in the image. For instance, a human on a bike is labelled as
’man’, since driving a bike is considered uncommon for women. Instead of
accepting the human as a gender neutral person, annotators tend to use their
own bias. Following are selected examples where all human annotators labelled
the human as male even though the gender is not clear from the image. There
are many such instances, though we do not report it here due to space crunch.

The dataset ground truth captions for these images are mentioned below each of
them. The surprising point to note is that, for each of the images, all 4
human annotators labelled the person as ‘man’ when it can be clearly seen that
the gender is not distinguishable from the image.

### 2.2 Gender Bias in the existing datasets

In the figure below, we observe the gender bias present in some of the popular
datasets, namely MS-COCO and imSitu Verb. It reflects that words like
’braiding’, ’shopping’, ’washing’ occur much more frequently with females than
males in the data whereas words like ’repairing’ and ’coaching’ have been seen
much more with males.Zhao et al. (2017) Burns et al. (2018)

### 2.3 Gender Bias in some of the state-of-the-art models

Next we analyse how this gender bias leads to the faulty performance of our
systems relying on ML models. The figure below demonstrates Google Translate
translating a text from the gender-neutral language Turkish to English, a
gender aware language. It shows that the model assigns a male gender to a
’doctor’ and a female gender to ’nurse’ to an initially gender neutral
sentence in Turkish.

In another trained model for image captioning, we observe below that the model
labels the subject as ’man’ giving the maximum attention to the computer
screen. This again signifies the relation between a computer and man learnt
inherently by the model from the training data. The image clearly contains a
woman, but the model instead uses the prior associated with computers to make
the gender decision.[Burns et al. (2018) ]

## 3\. Our Approach

To understand the gender bias present in Image captioning tasks, we decided to
analyse the model of the paper Show, Attend and Tell [Xu et al. (2015)], it
being a popular recent work on Image captioning. We first conducted
experiments to determine how much and in what form gender bias is present in
the dataset and the model. This led us to realize that often the incorrect
captions are a result of the relations learnt between certain activity/object
words and gender words. Since the dataset has a biased distribution of gender-
activity pairs, the model learns this bias.

As an approach to mitigate the effect of biased data distribution, we thought
about techniques to make the data unbiased in order to avoid the model from
observing any unwarranted relations. We thought that this could be done by
evening out the samples for males and females for each activity. However,
owing to the innumerable activities, and sparse occurrence of most scenes and
activities, with certain rare activities having instances only with one
gender; we realized that this would not be a feasible idea. Moreover, even if
possible, this strategy of balancing the data would be very restrictive and
require manual analysis and correction for every new dataset. So we decided to
look for another direction.

Our goal was essentially to prevent the model from making strong priors about
the activity based on the gender observed or vice versa. This was equivalent
to asking the model to be gender neutral and only observe the image while
predicting the activity in the image, and to only look at the person to
predict the subject’s gender, and not just relating the two based on priors.
Though, relational priors should be helpful in strengthening a guess based on
the image, and considering that the test distribution is the same as training
distribution, should give better results. However, preventing unwarranted
conclusions from these priors (that neglect the image) would be very
challenging in this way. Also, we believe that for a given test image in real-
time, the model should not correlate such ideas, since women and men should be
considered equally capable of doing most activities, and thus be identified
irrespective of the activity. Hence, we decided to decouple these two
decisions.

So we decide to split our goal into two tasks, drawing from Misra et al.
(2016). One, a gender neutral image captioning task, and the other being just
gender identification task in the image. For the first goal, we make the Show
Attend and Tell model gender neutral by removing all instances of gender from
the training data. For this we replace gender words like man, woman, men,
lady, guy, etc. with person or people such that no gender specific relations
are learned. Thereafter, we train the Gender Agnostic Show Attend and Tell
network. For the second goal, we used an existing popular model, trained to
identify the gender of the humans present in the image. The results from both
these tasks are then combined to obtain the final captions. Our proposed
overall model is named - Show Attend and Identify - SAI, since it identifies
the gender separately after obtaining a caption for the image.

The above figure shows the top branch as the gender agnostic Show, Attend and
Tell model and the bottom branch specialised in gender identification. We
replaced the gender neutral words (person, people) with gender words (man,
woman, men, women) based on the output of the Gender Identity net.

## 4\. Datasets

Our work is primarily on the MSCOCO dataset. To correctly evaluate the
performance of our model, we split the data into subsets. The following 3
subsets are used for experiments and evaluation of our model and comparison
with the existing Show, Attend and tell modelXu et al. (2015).

  * •

MSCOCO Gender confident dataset: Because of the rampant human annotator bias
infecting the data, there was a severe need for a dataset which is accurate
and for which the labels are consistent. Since the test data is composed of
total 40K instances and we wanted to test on a reasonable sized data, manual
selection was not possible. Hence, drawing from Burns et al. (2018), we relied
on the fact that for a confident presence of a male or female in the image,
all captions for that image should have a consistent mention of the gender.
Hence, we picked up those image-caption instances for which all the captions
had the same gender word (which can be either of man, woman, men, women, lady,
ladies, guy, guys, etc.) This gave us a subset of 2036 images.

  * •

MSCOCO Human dataset: We wanted to analyse the performance of our model to
test the quality of captions generated for human-activity and human-object
pairs and how that gets affected. Hence, we filtered those images for which
any of the captions contain a human identifier word (which can be either of
person, people, player, skier, snowboarder, man, woman, men, women, lady,
ladies, guy, guys, etc.). This is done by assuming that if a human being is
present, atleast one of the captions would mention it. Also, if any of the
captions mentions a human identity word, a human being must be present in that
image. This gave us a dataset of around 19,051 images.

  * •

MSCOCO Nature dataset: We wanted to analyse the performance of our model on
images without the presence of any human beings to determine the performance
and the effects, if any. Hence, we filtered out images where no human being is
present and we relied on the fact that if none of the captions for an image
contain a human label (which can be either of person, people, player, skier,
snowboarder, man, woman, men, women, lady, ladies, guy, guys, etc.) then the
image does not contain any human being. This gave us a subset of around
instances 21,453 images

## 5\. Experiments and Results

For the gender Identificiation task, we use Levi and Hassner (2015) in our
experiments. We evaluated our model on the three datasets created and
described above separately in order to observe the performance on each of the
datasets. Since, our gender agnostic network provides predictions with person
as the output, we could compare the overall quality of the captions predicted
by the model by comparing the gender-neutral predictions. Hence, we also
report results for this. For Show Attend and Tell, the predictions were made
gender neutral (by replacing the words man, woman, girl, boy, men, etc with
person or people). Ground-truth captions were also manually made gender
neutral by replacing gender aware words with gender neutral ones.

SAT is the Show Attend and Tell model. SAT-N denotes the comparison when the
predicted captions of SAT are manually made gender neutral and compared with
gender-neutral ground truth captions. SAI- Show, Attend and Identify is our
complete model. SAI-N is the gender neutral component of our model. The
following tables represent the BLEU, METEOR, ROUGEL and CIDEr scores obtained
on the different datasets.

Table 1: Performance on confident dataset, both in gender aware and gender
neutral settings (MSCOCO Gender Confident)

| Bleu1 | Bleu2 | Bleu3 | Bleu4 | METEOR | $ROUGE_{L}$ | CIDEr
---|---|---|---|---|---|---|---
SAT | 0.59 | 0.38 | 0.25 | 0.17 | 0.20 | 0.49 | 0.44
SAI | 0.59 | 0.38 | 0.24 | 0.16 | 0.19 | 0.49 | 0.43
SAT-N | 0.62 | 0.42 | 0.28 | 0.20 | 0.22 | 0.52 | 0.44
SAI-N | 0.64 | 0.43 | 0.29 | 0.19 | 0.22 | 0.53 | 0.44

Table 2: Performance on images with no humans (MSCOCO Nature)

| Bleu1 | Bleu2 | Bleu3 | Bleu4 | METEOR | $ROUGE_{L}$ | CIDEr
---|---|---|---|---|---|---|---
SAT | 0.62 | 0.41 | 0.27 | 0.18 | 0.20 | 0.49 | 0.55
SAI | 0.62 | 0.40 | 0.26 | 0.17 | 0.20 | 0.49 | 0.54

Table 3: Performance on images with humans (MSCOCO Human)

| Bleu1 | Bleu2 | Bleu3 | Bleu4 | METEOR | $ROUGE_{L}$ | CIDEr
---|---|---|---|---|---|---|---
SAT-N | 0.60 | 0.38 | 0.25 | 0.17 | 0.20 | 0.48 | 0.47
SAI-N | 0.61 | 0.38 | 0.24 | 0.16 | 0.20 | 0.47 | 0.47

A major limiting factor for the performance of our model is the accuracy of
the gender identity CNN. It is a popular model with one of the best results
reported. However surprisingly the model had a significantly low accuracy of
around 50% on the MSCOCO Confident dataset. This poses as a major roadblock.

The above example shows qualitative results of our model and the show attend
and tell model.

## 6\. Conclusion and Discussion

This project has demonstrated that gender bias is clearly prevalent in
existing datasets and models. We propose a technique to do away with the bias
in image captioning. Though our work is limited to images where all humans
need to belong to the same gender, however it demonstrates that developing a
gender neutral model allows us to get rid of the gender biased relations. The
results depict that this leads to an improvement in the overall caption
quality, while the performance for non-human images is not affected. Also, we
noticed that on removing man/woman from training data, our gender neutral
model predictions saw a sudden emergence of the words ’male’ and ’female’.
This depicts the close relation between the word embeddings for these.
Overall, we believe that the approach to get unbiased models involves having
the decoupling procedure to avoid any gender specifications and thus
unwarranted relations from entering the model.

## 7\. Problems and Future Work

We started this project with the task of removing gender bias from VQA models,
however VQA at present remains one of the most challenging problems, having
been called the ’visual turing test’ by some. Hence, most VQA models at
present are too naive making the task all the more challenging. Hence, we
worked on the removal of gender bias from Image captioning tasks in which
decent results have been obtained by some of the state-of-the-art methods
including Show, Attend and Tell which we use as our basenet. One could
experiment with the use of debiased word embeddings to further remove gender
bias from the model. One could learn a gender identification network which not
only identifies male/female but also has a third category of person, which
should be chosen in cases when the discrimination is not possible. More work
on the gender network could lead to improvements for our overall model.

##

## References

  * Antol et al. (2015) Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C. Lawrence Zitnick, and Devi Parikh.  Vqa: Visual question answering.  In _The IEEE International Conference on Computer Vision (ICCV)_ , December 2015.
  * Burns et al. (2018) Kaylee Burns, Lisa Anne Hendricks, Trevor Darrell, and Anna Rohrbach.  Women also snowboard: Overcoming bias in captioning models.  _arXiv preprint arXiv:1803.09797_ , 2018.
  * Kafle and Kanan (2017) Kushal Kafle and Christopher Kanan.  Visual question answering: Datasets, algorithms, and future challenges.  _Computer Vision and Image Understanding Journal (CVIU)_ , 2017.
  * Levi and Hassner (2015) Gil Levi and Tal Hassner.  Age and gender classification using convolutional neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops_ , pages 34–42, 2015.
  * Misra et al. (2016) Ishan Misra, C Lawrence Zitnick, Margaret Mitchell, and Ross Girshick.  Seeing through the human reporting bias: Visual classifiers from noisy human-centric labels.  In _Computer Vision and Pattern Recognition (CVPR), 2016 IEEE Conference on_ , pages 2930–2939. IEEE, 2016.
  * Selvaraju et al. (2016) Ramprasaath R Selvaraju, Abhishek Das, Ramakrishna Vedantam, Michael Cogswell, Devi Parikh, and Dhruv Batra.  Grad-cam: Why did you say that?  _arXiv preprint arXiv:1611.07450_ , 2016.
  * T. et al. (2016) Bolukbasi T., Chang K.-W, Zou J., Saligrama V., and Kalai A.  _Man is to computer programmer as woman is to homemaker? Debiasing word embeddings_.  In Advances in Neural Information Processing Systems, pp. 4349-4357, 2016\.
  * van Miltenburg (2016) E. van Miltenburg.  Stereotyping and bias in the flickr30k dataset. in: Workshop on multimodal corpora.  _Computer vision and language processing_ , 2016.
  * Veit et al. (2017) Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, and Serge Belongie.  Learning from noisy large-scale datasets with minimal supervision.  _In Computer Vision and Pattern Recognition, (CVPR)_ , 2017.
  * Xu et al. (2015) Kelvin Xu, Jimmy Ba, Kyunghyun Cho Ryan Kiros, Aaron C. Cou rville, Ruslan Salakhutdinov, Richard S. Zemel, and Yoshua Bengio.  Show, attend and tell: Neural image caption generation with visual attention.  _In ICML International Conference on Machine Learning_ , 2015.
  * Zhang et al. (2015) Peng Zhang, Yash Goyal, Douglas Summers-Stay, Dhruv Batra, and Devi Parikh.  Yin and yang: Balancing and answering binary visual questions.  _arXiv preprint arXiv:1511.05099_ , 2015.
  * Zhao et al. (2017) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang.  Men also like shopping: Reducing gender bias amplification using corpus-level constraints.  _arXiv preprint arXiv:1707.09457_ , 2017.


# Bad witnesses for a composite number

Johnathan Djella Legnongo  Johnathan Djella, UFR of Science and Technology,
Assane Seck University of Ziguinchor, BP 523, Senegal<EMAIL_ADDRESS>,
Tony Ezome  Tony Ezome, Laboratoire de Recherche en Mathématiques et
Applications (LAREMA), École Normale Supérieure (ENS), BP 17 009 Libreville,
Gabon<EMAIL_ADDRESS>and  Florian Luca  Florian Luca, School of
Mathematics, University of the Witwatersrand, Private Bag 3, Wits 2050, South
Africa<EMAIL_ADDRESS>
###### Abstract.

We describe the average sizes of the set of bad witnesses for a pseudo-
primality test which is the product of a multiple-rounds Miller-Rabin test by
the Galois test.

Keywords: Fermat test, Miller-Rabin test, Galois test, probable prime.
2020 Mathematics Subject Classification: 11Y11 (primary); 11A51

##  1\. Introduction

One of the simplest questions we have in mind, when handling a large number,
is to know whether this number is prime or composite. There are of course
several methods allowing to decide primality. The most important algorithms
are divided into two subfamilies: primality tests and pseudo-primality tests.
We refer to [4, Chapters 8 and 9], [8] and [13]] for surveys on known
algorithms, from oldest to most recent. Actually, we are talking about a very
long-standing mathematical problem which was already addressed by Euclid’s
Elements. Closer to our time, the Fermat’s little theorem gives rise to a
pseudo-primality test which studies the primality of an odd integer $n$ by
checking the congruence $x^{n-1}\equiv 1\pmod{n}$ whenever an integer $x$
relatively prime to $n$ is randomly chosen. If the congruence is false, then
$n$ is obviously composite. When the congruence is true, one can only conclude
that $n$ is probably prime. Indeed, Carmichael numbers are composite numbers
for which the previous congruence is true for any $x$. However, Alford,
Granville and Pomerance proved in [1] that there are infinitely many
Carmichael numbers. This compromises the reliability of the Fermat test. The
most commonly used algorithm in practice for prime detection is the Miller-
Rabin pseudo-primality test. This algorithm is an improvement of the Fermat
test resulting from the work by Artjuhov [2], Miller [10] and Rabin [12].
Setting $n-1=2^{k}m$ with $m$ odd, we say that $n$ passes a Miller-Rabin test
if one of the congruences

(1) $x^{m}\equiv 1\pmod{n},\ \text{ or }\ x^{2^{i}m}\equiv-1\pmod{n}\ \text{
for some }\ i<k$

holds with an integer $x$ relatively prime to $n$ chosen randomly. Such an $x$
is a witness of the pseudo-primality of $n$ with respect to the Miller-Rabin
test. One says that $x$ is a  bad witness if it satisfies one of the above
congruences while $n$ is in fact composite. The density of bad witnesses is an
important characteristic for a pseudo-primality test as it measures the
reliability of this test. It is proved [13, Proof of theorem 2.1] that the
Miller-Rabin test is very effective in the case when $n$ has many prime
divisors. A pseudo-primality test called the Galois test which is efficient
when the integer to be tested has only very few prime divisors has been
constructed in [5]. At the end of that paper, the authors deduced a stronger
pseudo-primality test which is the product of a multiple-rounds Miller-Rabin
test ($i.e$ running several Miller-Rabin tests at the same time) by a Galois
test. This product test takes advantages of strengths of each of its
components, especially in the extreme cases when the integer to be tested has
either many or very few prime divisors. However, nothing is known yet about
the average case analysis. A first step in this direction has been made by
Erdös and Pomerance in [7], they focused on the special case of a one-round
Miller-Rabin test.

The present paper describes the average sizes of the set $\mathbf{Str}(n)$ of
bad witnesses of an odd number $n$ with respect to the stronger test proposed
in [5]. We start by studying the set $\mathbf{Gal}(n)$ of bad witnesses for
the Galois test in Section 2. We recall some well known results concerning
$\mathbf{Gal}(n)$ in 2.1. Then, we focus on the arithmetic and geometric mean
values of its cardinality denoted by $Gal(n)$ in Subsections 2.2 and 2.3.
Section 3 is devoted to the stronger test. We first describe the average
numbers of bad witnesses for a multiple-rounds Miller-Rabin test. And then, we
specify the case of the stronger test.

### Acknowledgments

This study has been carried out with financial support from the French State,
managed by CNRS in the frame of the Dispositif de Soutien aux Collaborations
avec l’Afrique subsaharienne (via the REDGATE Project and the IRN AFRIMath).
The first two authors were supported by Simons Foundation via the PREMA
project. The first author is grateful to EMS-Simons for Africa for their
support to his PhD education.

##  2\. Bad witnesses of the Galois test

In this section, we compute functions that bound from above and from below the
arithmetic mean of the number of bad witnesses for the Galois test, we also
specify its geometric mean. We start by recalling some known results.

###  2.1. Preliminaries

Let $n\geq 3$ be an odd integer to be tested, and
$n=\prod_{p^{v_{p}}\|n}p^{v_{p}}$ its prime factorization. Let $S$ be a
$d$-dimensional cyclic extension of $R:={\mathbb{Z}}/n{\mathbb{Z}}$ with
Galois group generated by $\sigma$. As a ring $S$ is isomorphic to

$\prod_{p\mid n}S_{p},$

where $S_{p}:=S/p^{v_{p}}S$. Fixing a prime factor $p$ of $n$, we set ${\bf
L}_{p}:=S_{p}/pS_{p}$ and $\mathbf{K}:=R/pR$. It is known [5, Section 2] that
$S$ is a free $R[\sigma]$-module of rank $1$. We denote by
$(\sigma^{i}(\omega))_{0\leq i\leq d-1}$ a normal basis of $S$ over $R$. The
ring ${\bf L}_{p}$ has only a finite number of prime ideals, say ${\bf
p}_{1},\ldots,{\bf p}_{m}$. The residue fields ${\bf L}_{p}/{\bf p}_{i}$ for
$i=1,\ldots,m$ are all isomorphic to ${\mathbb{F}}_{p^{f}}$, the finite field
with $f$ elements, where of course $d=fm$. In particular, the ring ${\bf
L}_{p}$ is isomorphic to

$\prod_{p\mid n}{\mathbb{F}}_{p^{f}}.$

So, the more composite $d$ is the more possibilities for the pair
$(m,f)=(m,d/m)$. The $R$-automorphism $\sigma:S\longrightarrow S$ induces a
$\mathbf{K}$-automorphism of ${\bf L}_{p}$. There is an integer $z$ coprime to
$m$ such that

$x^{p}=\sigma^{zm}(x),\ \ \text{ for all }x\in{\bf L}_{p}.$

We denote by $t\in\llbracket 1,f-1\rrbracket$ the inverse of $z$ modulo $f$
(if $f=1$, we have $z=t=0$). Note that the integers $f,m$ and $t$ depend on
the prime $p$. For a fixed dimension $d$, there are only finitely many
possibilities for $(m,f,t)$, and every prime gets some such possibility
assigned to it (these possibilities might not all be the same they may vary
with the primes).

Assume that $\sigma(\omega)=\omega^{n}$. Then $n$ passes successfully a Galois
test of dimension $d$ if by choosing randomly a nonzero element $x$ in $S$, we
have that $x$ is invertible and

(2) $\sigma(x)=x^{n}.$

Let $\mathbf{Gal}(n)$ be the set of invertible elements in $S^{\times}$ which
are solutions of Equation $(\ref{eq:16})$. We denote by $\mathrm{Gal}(n)$ its
cardinality. It is proved [5, Section 1 and Section 2] that

(3) $Gal(n)=\prod_{p\mid n}\gcd(n^{m}-p^{t},p^{f}-1).$

Since $n^{m}-p^{t}$ divides $n^{mf}-p^{tf}=(n^{d}-1)-((p^{f})^{t}-1)$, we
deduce that ${Gal}(n)$ divides

$D(n):=\prod_{p\mid n}\gcd(p^{f}-1,n^{d}-1).$

Note that the latter quantity counts the number of elements $x$ in the group
of invertible elements of the ring

$\prod_{p\mid n}{\mathbb{F}}_{p^{f}}$

satisfying $x^{n^{d}-1}=1$. Since these elements form a subgroup, there exists
some positive integer $k$ such that

(4) $D(n)=\frac{1}{k}\prod_{p\mid n}(p^{f}-1).$

Set $L(x)=\exp\left(\frac{\log x\log\log\log x}{\log\log x}\right)\text{ for
all large }x$. The lemma below is very useful.

######  Lemma 1.

Given a positive integer $k$, the number of composite numbers $n\leq x$ having
a prime divisor $p>kL(x)$ and such that $D(n)=\frac{1}{k}\prod_{p\mid
n}(p^{f}-1)$ is bounded from above by $xL(x)^{-1+o(1)}$.

###### Proof.

Indeed, equation $(\ref{eq:17})$ implies that $\prod_{p\mid n}(p^{f}-1)$
divides $k(n^{d}-1)$. So,

$p-1\mid k(n^{d}-1).$

Set $D:=(p-1)/\gcd(k,p-1)$. Since $p$ is fixed and so is $k$, the number $D$
is fixed. We need to count the $n\leq x$ divisible by $p$ such that $n^{d}-1$
is divisible by $D$. Write $D=\prod_{q^{u}\|D}q^{u}$. Then the number of
solutions $y$ to the congruence

$y^{d}-1\equiv 0\pmod{D}$

is equal modulo $D$ to

$\prod_{q^{u}\|D}\rho(q^{u}),$

where for a prime power $q^{j}$, $\rho(q^{j})$ denotes the number of solutions
$y$ modulo $q^{j}$ of the congruence $y^{d}-1\equiv 0\pmod{q}^{j}$. Therefore,
the number of $n\leq x$ divisible by $p$ such that $n^{d}-1$ is divisible by
$D$ is bounded from above by $C_{d}d^{\omega(D)}$, where $C_{d}$ depends only
on $d$. This upper bound is obvious for $q>d$, since $y^{d}-1\equiv 0\pmod{q}$
has then at most $d$ solutions modulo $q$ which by Hensel’s lemma are each
extendible in a unique way to a solution $x$ modulo $q^{j}$ for every $j\geq
1$. The constant term $C_{d}$ obviously equals $1$ in this case. A nontrivial
$C_{d}$ appears when dealing with moduli which are small prime powers of
primes dividing $d$. Since

$\displaystyle C_{d}d^{\omega(D)}$ $\displaystyle\leq$ $\displaystyle
C_{d}d^{O(\log(p-1)/\log\log(p-1))}$ $\displaystyle=$
$\displaystyle\exp\left(\log C_{d}+O\left(\frac{\log x}{\log\log
x}\right)\right)$ $\displaystyle=$ $\displaystyle L(x)^{o(1)},$

the number of such progressions is $L(x)^{o(1)}$. Let us count the $n\leq x$
in a fixed progression. We take $x_{0}\in[1,D-1]$ such that $x_{0}^{d}\equiv
1\pmod{D}$ and we count the number of $n\leq x$ such that $n\equiv
x_{0}\pmod{D}$. Since $n\equiv 0\pmod{p}$ and $(p,D)=1$ (since $D\mid p-1)$,
we get that this puts $n$ into some progression $n\equiv
x_{0}^{\prime}\pmod{pD}$. The number of such $n\leq x$ is

(5) $1+\left\lfloor\frac{x}{pD}\right\rfloor.$

Since

$\frac{x}{pD}=\frac{x}{p(p-1)/\gcd(k,p-1)}\leq\frac{kx}{p(p-1)},$

we have

$\sum_{p>kL(x)}\left\lfloor\frac{x}{pD}\right\rfloor\leq
2kx\sum_{p>kL(x)}\frac{1}{p^{2}}\ll\frac{x}{L(x)}.$

It remains to count the $1$’s in equation $(\ref{eq:19})$. These are the
initial terms $x_{0}^{\prime}$ of the solutions modulo $Dp$, namely the
smallest positive integer $n\leq x$ such that $n\equiv x_{0}\pmod{D}$ and
$n\equiv 0\pmod{p}$. Write $n=pm$. Then $n^{d}\equiv p^{d}m^{d}\equiv
1\pmod{D}$. Since $D\mid p-1$, we get that $m^{d}\equiv 1\pmod{D}$. This means
$D\mid m^{d}-1$. We know that $m>1$ since $n$ is not prime. Thus, $m>D^{1/d}$.
Since $pm\leq x$, it follows that $pD^{1/d}\leq x$.

Let us make a parenthesis and take a closer look at $\gcd(p-1,k)$. Let
$k_{1}=\gcd(p-1,k)$. We first treat the case $k_{1}\geq L(x)$. Note that
$k\mid\prod_{p\mid n}(p^{f}-1)<n^{f}\leq x^{d}$. Thus, $k_{1}$ is a divisor of
a number of size $x^{d}$. The number of divisors of $k$ is therefore at most

$\max_{k<x^{d}}\tau(k)=\exp((O(\log x^{d}/\log\log x^{d}))=\exp(O(d\log
x/\log\log x))=L(x)^{o(1)}$

as $x\to\infty$. Assume now that $k_{1}\mid k$ is fixed and let us count
primes $p\leq x$ such that $\gcd(p-1,k)=k_{1}$. Then $p\equiv 1\pmod{k_{1}}$.
We bound the number of such primes $p\leq x$ trivially $\leq x/k_{1}\leq
x/L(x)$. Given $p$, $D$ is a divisor of $p-1$, so $D$ can have at most
$\tau(p-1)=L(x)^{o(1)}$ possibilities. Thus, for fixed $k_{1}$, there are
$x/L(x)^{1+o(1)}$ possibilities for the pair $(p,D)$. Summing up over the
$L(x)^{o(1)}$ possible values of $k_{1}$ (divisors of $k$ larger than $L(x)$),
we get a count of $x/L(x)^{1+o(1)}$ for the number of such pairs $(p,D)$.

Next, we assume that $k_{1}<L(x)$. Then

$D=\frac{p-1}{\gcd(p-1,k)}=\frac{p-1}{k_{1}}>\frac{p-1}{L(x)},$

so

$D^{1/d}\geq(p-1)^{1/d}/L(x)^{1/d}.$

Thus, $p(p-1)^{1/d}\leq pD^{1/d}\leq xL(x)^{1/d}=x^{1+o(1)}$, showing that
$p\leq x^{d/(d+1)+o(1)}$. Given $p$, $D$ is determined in at most
$\tau(p-1)=L(x)^{o(1)}$ ways, so the modulus $Dp$ is determined in at most
$x^{d/(d+1)+o(1)}$ ways. Thus, the number of starting points $x_{0}\pmod{D}$
is also determined in at most $L(x)^{o(1)}$ ways. So, the number of $1$’s in
this last case is in fact much smaller namely at most

$x^{d/(d+1)+o(1)}<\frac{x}{L(x)}$

for large $x$. This concludes the proof of the lemma. ∎

###  2.2. Average order of $\mathrm{Gal}(n)$

Here, we study the arithmetic mean of the number of bad witnesses of the
Galois test. We first compute a function which bounds it from below. In what
follows ${\mathop{\sum\\!^{\prime}}\nolimits}$ denotes a sum over composite
numbers.

######  Theorem 1.

For all large $x$,

$\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}Gal(n)>x^{\frac{15}{23}}.$

###### Proof.

Let $M(x)$ denote the least common multiple of the integers up to $x$. For any
$y$, let

$\mathbf{P}(y,x)=\\{p\leq y:p-1|M(x)\\}$

It is shown ([6] or [11]) that there is a real number $\alpha>1$ such that

$\\#\mathbf{P}(x^{\alpha^{\prime}},x)=O(x^{\alpha^{\prime}}/\log
x)\quad\text{for all }0<\alpha^{\prime}<\alpha.$

We let

$\beta=\sup\\{\alpha:\\#\mathbf{P}(x^{\alpha^{\prime}},x)=x^{\alpha^{\prime}+o(1)}\text{
for all }0<\alpha^{\prime}<\alpha\\}.$

From [3], we have

$\beta>23/8.$

Let $L$ denote an upper bound for Linnik’s constant, so that given positive
integers $a,m$ with $\gcd(a,m)=1$ and $m>1$, then there is a prime $p\equiv
a\pmod{m}$ with $p<m^{L}$. Let $\alpha$ be such that $1<\alpha<\beta$ and
$0<\epsilon<\alpha-1$ arbitrarily small. We set

$\begin{array}[]{c}M=M(\log x/\log\log x),\\\
\mathbf{P}=\mathbf{P}(\log^{\alpha}x,\log x/\log\log
x)-\\{p:p\leq\log^{\alpha-\epsilon}x\\}.\end{array}$

Let $\mathbf{S}$ denote the set of integers composed of exactly

$k=[\log(x/M^{L})/\log(\log^{\alpha}x)]$

distinct primes in $\mathbf{P}$. Thus, if $s\in\mathbf{S}$, then

(6) $x^{1-\epsilon}<s<x/M^{L}.$

Let $\mathbf{S}^{\prime}$ be the set of products $sq$, where $s\in\mathbf{S}$
and $q$ is the least prime such that

$sq\equiv 1\pmod{M}.$

It is shown ([7], Proof of Theorem 2.1) that

(7) $sq\leq x,\quad\text{ and }\quad\\#\mathbf{S}^{\prime}\geq
x^{(\alpha-1)\alpha^{-1}+o(1)}.$

So if $n=sq\in\mathbf{S}^{\prime}$, then

$\mathrm{Gal}(n)=\prod_{p|n}\gcd(n^{m}-p^{t},p^{f}-1)\geq\prod_{p|s}\gcd(n^{m}-p^{t},p^{f}-1)\geq\prod_{p|s}\gcd(n-1,p-1)$
$=\prod_{p|s}\gcd(M,p-1)=\varphi(s).$

Theorem $328$ in [9] implies that

$s/\log\log s=O(\varphi(s)).$

Besides, $(\ref{eq:14})$ and $(\ref{eq:15})$ give

$s/\log\log s\geq x^{1-\epsilon}/\log\log x.$

So

$\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}Gal(n)\geq\frac{1}{x}\sum_{n\in\mathbf{S}^{\prime}}Gal(n)\geq
x^{-\epsilon+o(1)}\cdot\\#\mathbf{S}^{\prime}\geq
x^{1-\varepsilon-\alpha^{-1}+o(1)}.$

Since $\varepsilon>0$ is arbitrarily small and $\alpha$ is arbitrarily close
to $\beta$, we have

$\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq x}Gal(n)\geq
x^{1-\beta^{-1}+o(1)}.$

Hence,

$\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}Gal(n)>x^{\frac{15}{23}+o(1)},$

since $\beta>23/8$.

∎

We now compute a function which bounds from above the number of bad witnesses
of the Galois test.

######  Theorem 2.

As $x\to\infty$,

(8) $\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq x}Gal(n)\leq
x^{d}L(x)^{-1+o(1)}.$

###### Proof.

We saw in Subsection 2.1 that $Gal(n)$ divides $D(n)$. Therefore, it suffices
to show that

$\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq x}D(n)\leq
x^{d}L(x)^{-1+o(1)}.$

For every integer $k\geq 1$, we let $\mathbf{C}_{k}(x)$ be the set of
composite numbers $n\leq x$ such that $D(n)=\frac{1}{k}\prod_{p\mid
n}(p^{f}-1)$, and we set $C_{k}(x)=\\#\mathbf{C}_{k}(x)$. Then

${\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}D(n)=\sum_{k}\sum_{n\in\mathbf{C}_{k}(x)}\frac{1}{k}\prod_{p\mid
n}(p^{f}-1)\leq\sum_{n\leq x}\frac{n^{d}}{L(x)}+\sum_{k\leq
L(x)}\frac{1}{k}\sum_{n\in\mathbf{C}_{k}(x)}n^{d}.$

So,

${\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}D(n)\leq\frac{x^{d+1}}{L(x)}+x^{d}\sum_{k\leq L(x)}\frac{C_{k}(x)}{k}.$

Therefore, we have to show that

$C_{k}(x)\leq xL(x)^{-1+o(1)}\text{ for }k\leq L(x).$

There are three cases to be considered:

  * (i)

$n<x/L(x)$,

  * (ii)

$n$ is divisible by some prime $p>kL(x)$,

  * (iii)

$n\geq x/L(x)$ and every prime divisor of $n$ is at most $kL(x)$.

Situation $(i)$ is trivial. Situation $(ii)$ is taken care of by Lemma 1.
Situation $(iii)$ implies that $n$ has a divisor $n_{1}$ satisfying

(9) $\frac{x}{kL(x)^{2}}<n_{1}<\frac{x}{L(x)}.$

By $(\ref{eq:17})$, we know that the exponent $\lambda_{S}(n)$ of the group
$\prod_{p\mid n}{\mathbb{F}}_{p^{f}}^{*}$ divides $k(n^{d}-1)$. We would like
to follow the proof of case (iii) of Theorem 2.2 in [7], but there are
additional complications due to the possible prime factors of $n$ which might
appear to powers larger than $1$ in the factorization of $n$. So, we write
$n_{1}=ab$, where $a$ is squarefree and $b$ is squarefull. We may assume that
$b\leq L(x)^{2}$, since if not, $b>L(x)^{2}$ and the number of $n\leq x$ such
that $b\mid n$ is $\leq x/b$. Since

$\sum_{\begin{subarray}{c}m>y\\\ m\leavevmode\nobreak\ {\text{\rm
squarefull}}\end{subarray}}\frac{1}{m}=O\left(\frac{1}{\sqrt{t}}\right),$

we get that the set of such $n$ is of cardinality

$O\left(\frac{x}{L(x)}\right)=\frac{x}{L(x)^{1+o(1)}}$

irregardless of the value of $k$. So, assuming $b\leq L(x)^{2}$, we get that

(10) $\frac{x}{kL(x)^{4}}\leq\frac{x}{kL(x)^{2}b}\leq a\leq\frac{x}{L(x)b}.$

We fix a squarefree $a$, a squarefull $b$ coprime to $a$ and smaller than
$L(x)^{2}$ and we look for $n=b\lambda$. Clearly, $\lambda\leq x/b$. Further,
$a\mid\lambda$ and additionally $\lambda(a)\mid k(n^{d}-1)$, which shows that
$\lambda^{d}\equiv(b^{*})^{d}\pmod{\lambda(a)/(\lambda(a),k)}$. Here, $b^{*}$
is the inverse of $b$ modulo $\lambda(a)/(k,\lambda(a))$. Since $b$ is fixed,
this puts $\lambda\leq x/b$ in at most
$C_{d}d^{\omega(\lambda(a)/(k,\lambda(a)))}$ arithmetic progressions modulo
$\lambda(a)/(k,\lambda(a))$. By the Chinese Remainder Theorem, this puts
$\lambda\leq x/b$ in

$C_{d}d^{\omega(\lambda(a)/(k,\lambda(a)))}$

progressions modulo $a\lambda(a)/(k,\lambda(a))$. The number of such numbers
$\lambda\leq x/b$ is

$\leq
C_{d}d^{\omega(\lambda(a)/(k,\lambda(a)))}\left(\frac{x}{ba\lambda(a)/(k,\lambda(a))}+1\right).$

Since $\lambda(a)\leq x$ has $O(\log x/\log\log x)$ prime factors, the factor
multiplying the parenthesis is of size $\exp(O(\log x/\log_{2}x))=L(x)^{o(1)}$
as $x\to\infty$. Factoring out such factor and summing up the remaining
parenthesis over all numbers of the form $n_{1}=ab$ we get a count of

$\sum_{b\leq
L(x)^{2}}\sum_{a}^{*}\frac{x(k,\lambda(a))}{ab\lambda(a)}+\sum_{ab\leq
x/L(x)}1.$

Here, for a fixed $b$, the star on the inner summation indicates that the
summation is over the squarefree $a$’s satisfying (10). The second sum is the
number of positive integers up to $x/L(x)$ so it is $O(x/L(x))$. The first
inner sum is for fixed $b$ estimated as on the bottom of page 283 and top of
page 284 in [7]. For a fixed $b$ it ends up being

$\frac{x(\log x)^{2}}{bL(x/(kL(x)^{2}b)}2^{(1+o(1))\log x/\log_{2}x}.$

Since $b\leq L(x)^{2}$ and $k\leq L(x)$, we get that
$L(x/(kL(x)^{2}b))=L(x)^{1+o(1)}$, while $2^{(1+o(1))\log
x/\log_{2}x}=L(x)^{o(1)}$ as $x\to\infty$. Hence, the first sum simply becomes

$\frac{x}{L(x)^{1+o(1)}}\sum_{b\leq
L(x)^{2}}\frac{1}{b}\ll\frac{x}{L(x)^{1+o(1)}},$

which is what we wanted. ∎

###  2.3. Geometric mean value of $\mathrm{Gal}(n)$

Theorem 3.1 in [7] studied the geometric mean value of

(11) $F(n)=\prod_{p\mid n}\gcd(p-1,n-1).$

The result there is that

$\left(\prod_{n\leq x}F(n)\right)^{1/x}=(c_{2}+o(1))(\log x)^{c_{1}}$

with

(12) $c_{1}=\sum_{d}\frac{\Lambda(d)}{d\varphi(d)},\qquad
c_{2}=\exp\left(1+\sum_{d}\frac{\Lambda(d)C(d)}{d}\right),$

where $\Lambda(n)$ denotes the von Mangoldt’s function and $\varphi(n)$
denotes the Euler’s $\varphi$-function. Since

${\text{\rm Gal}}(n)=\prod_{p\mid n}\gcd(n^{m}-p^{t},p-1)\geq F(n),$

it follows that the geometric mean value of ${\text{\rm Gal}}(n)$ is at least
as large as the geometric mean value of $F(n)$. Since $m,t$ depend on the
prime $p$, it seems hard to find an asymptotic for the geometric mean of
${\text{\rm Gal}}(n)$. However, since ${\text{\rm Gal}}(n)$ divides

$H(n)=\prod_{p[\mid n}\gcd(p^{d}-1,n^{d}-1),$

it follows that the geometric mean of ${\text{\rm Gal}}(n)$ is at most as
large as the geometric mean of $H(n)$. Concerning this last one we have the
following result.

######  Theorem 3.

The estimate

$\frac{1}{x}\sum_{n\leq x}\log H(n)=c_{3}\log\log x+O(d^{4}),$

holds with

$c_{3}=c_{3}(d):=\sum_{d_{1}\mid
d}\sum_{(\lambda(s),d)=d_{1}}f(s,d_{1})^{2}\frac{\Lambda(s)}{s\phi(s)}.$

In the above, $\lambda(s)$ is the Carmichael function of $s$, and a for a
prime power $s$ and $d_{1}\mid\lambda(s)$, $f(s,d_{1})$ denotes the number of
elements in $({\mathbb{Z}}/s{\mathbb{Z}})^{*}$ of order exactly $d_{1}$. Note
that when $s$ is a prime power we have $f(s,d_{1})=d_{1}$ except if $s=2^{a}$
with $a\geq 3$ and $d_{1}\geq 2$ in which case $f(s,d_{1})=2d_{1}$.

One may ask how big is $c_{3}(d)$? Well since $s\asymp\phi(s)\asymp\lambda(s)$
and $f(s,d_{1})\asymp d_{1}$ when $s$ is a prime power, it follows that for a
fixed $d_{1}$,

$\sum_{(\lambda(s),d)=d_{1}}\frac{\Lambda(s)}{s\phi(s)}\ll\sum_{t\geq
1}\frac{\log(d_{1}t)}{(d_{1}t)^{2}}\ll\frac{\log d_{1}}{d_{1}^{2}},$

showing that

$c_{3}\ll\sum_{d_{1}\mid d}\log d_{1}=\log\left(\prod_{d_{1}\mid
d}d_{1}\right)=\log(d)^{\tau(d)/2}=(\tau(d)/2)\log d,$

so

$c_{3}=O(\tau(d)\log d).$

In particular, $c_{3}=d^{o(1)}$ as $d\to\infty$.

###### Proof.

We have

$\displaystyle\sum_{n\leq x}\log H(n)$ $\displaystyle=$
$\displaystyle\sum_{n\leq x}\log\prod_{p\mid n}\gcd(n^{d}-1,p^{d}-1)$
$\displaystyle=$ $\displaystyle\sum_{n\leq x}\ \sum_{p\mid n}\
\sum_{s\mid\gcd(n^{d}-1,p^{d}-1)}\Lambda(s)$ $\displaystyle=$
$\displaystyle\sum_{s\leq x^{d}}\Lambda(s)\sum_{\begin{subarray}{c}p\leq x\\\
s\mid p^{d}-1\end{subarray}}\sum_{\begin{subarray}{c}n=p\ell\leq x\\\
s\mid(p\ell)^{d}-1\end{subarray}}1$ $\displaystyle=$ $\displaystyle\sum_{s\leq
x^{d}}\Lambda(s)\sum_{\begin{subarray}{c}p\leq x\\\ p^{d}\equiv
1\pmod{s}\end{subarray}}\sum_{\begin{subarray}{c}\ell\leq x/p\\\
\ell^{d}\equiv 1\pmod{s}\end{subarray}}1.$

In the above, we wrote the condition $p\mid n,\leavevmode\nobreak\ n\leq x$ as
$n=p\ell\leq x$, so $\ell\leq x/p$. We first deal with large values of $s$.
Let $S_{1}$ be the sum corresponding to $s=q^{\lambda}$, where $q\geq x$.
Firstly, $\lambda\leq d$. Secondly, if such $q$ appears then $q\mid p^{d}-1$
for some $p\leq x$. Further, since $p\leq x$ and $q>x$, it follows that the
above congruence has only at most $d$ solutions $p$ altogether. Thus, for each
such $s$, there are at most $d$ occurrences of $p$ such that $p^{d}\equiv
1\pmod{s}$, and the same goes for the $\ell$’s. For each such $q$ let $s_{q}$
be the maximal power of $q$ for which $s_{q}$ appears in $S_{1}$. Then the
product of $s_{q}$’s divides

$\prod_{p\leq x}(p^{d}-1)\leq\left(\prod_{p\leq
x}p\right)^{d}=\exp((1+o(1))x),$

where the last equality follows from the Prime Number Theorem. Thus,

$\sum_{q}^{\prime}\log s_{q}=O(dx),$

where $\sum^{\prime}$ means that we are only summing over the $q$’s that
appear in $S_{1}$. Since the exponents of such $q$ in $s_{q}$ is at most $d$
(so there are at most $d$ values of $s$ dividing $s_{q}$ appearing in $S_{1}$)
and since for each such $s$ there are at most $d^{2}$ pairs $(p,\ell)$ such
that $p^{d}\equiv\ell^{d}\equiv 1\pmod{s}$, we get that

$S_{1}=O(d^{4}x).$

From now on, we look at $s=q^{\lambda}$ but $q<x$. Let $S_{2}$ be the sum
corresponding to $s=q^{\lambda}\geq x$. The equation $p^{d}\equiv 1\pmod{s}$
has $O(d)$ solutions and the same is true for the equation $\ell^{d}\equiv
1\pmod{s}$. Thus, given $s$, there are at most $O(d^{2})$ pairs $(p,\ell)$
with $p\leq x,\leavevmode\nobreak\ \ell\leq x$ such that
$p^{d}\equiv\ell^{d}\equiv 1\pmod{s}$. Since $s=q^{\lambda}\in(x,x^{d}]$, we
have $\lambda\in(\log x/\log q,d\log x/\log q]$. Thus, there are $O(d\log
x/\log q)$ possibilities for the exponent $\lambda$ in $s$ once $q$ is fixed.
Hence,

$S_{2}=O\left(d^{3}\sum_{q\leq x}\log q\left(\frac{\log x}{\log
q}\right)\right)=O(d^{3}\pi(x)\log x)=O(d^{3}x).$

From now on, we may assume that $s\leq x$. We now look at the condition
$p^{d}\equiv 1\pmod{s}$. But we also have $p^{\lambda(s)}\equiv 1\pmod{s}$,
where $\lambda(s)$ is the Carmichael function of $s$. Thus,
$p^{\gcd(d,\lambda(s))}\equiv 1\pmod{s}$. This suggests putting
$d_{1}=\gcd(d,\lambda(s))$ and studying $p^{d_{1}}\equiv 1\pmod{s}$. The unit
group modulo $s$ is cyclic for primes powers $s$ except when $s=2^{a}$ with
$a\geq 3$, in which case it is isomorphic
${\mathbb{Z}}/2{\mathbb{Z}}\times{\mathbb{Z}}/2^{a-2}{\mathbb{Z}}$. It thus
follows that the number of residue classes modulo $s$ say $y$ such that
$y^{d_{1}}\equiv 1\pmod{s}$ is exactly $d_{1}$ except if $s=2^{a}$ for $a\geq
3$ and $d_{1}>1$ in which case it is $2d_{1}$. Let this number be $f(s,d_{1})$
like in the statement of the theorem and let these residues be
$y_{i}(s,d_{1})$ for $i=1,\ldots,f(s,d_{1})$. We then have that $p^{d}\equiv
1\pmod{s}$ forces $p\equiv y_{i}(s,d_{1})\pmod{s}$ for some
$i=1,\ldots,f(s,d_{1})$. For each such $p\leq x$, the equation $\ell^{d}\equiv
1\pmod{s}$ also has exactly $f(s,d_{1})$ solutions $\ell$ modulo $s$ and since
$\ell\leq x/p$, the number of such solutions is

$f(s,d_{1})\left(\left\lfloor\frac{x}{ps}\right\rfloor+O(1)\right).$

When $ps>x$, the first term in integer part is not present. We remove integer
parts and include the fractional parts into the $O(1)$ terms so the remaining
sum is now

$\sum_{d_{1}\mid d}\sum_{\begin{subarray}{c}s\leq x\\\
\gcd(\lambda(s),d)=d_{1}\end{subarray}}\Lambda(s)f(d_{1},s)\sum_{i=1}^{f(s,d_{1})}\sum_{\begin{subarray}{c}p\leq
x\\\ p\equiv
y_{i}(s,d_{1})\pmod{s}\end{subarray}}\left(\frac{x}{ps}+O(1)\right)=S_{3}+O(S_{4}),$

where $S_{3}$ is the sum involving the terms $x/ps$ and $S_{4}$ is the sum
involving the $1$’s. For $S_{4}$, since $ps>x$, each class $y_{i}(s,d_{1})$
contains at most one such prime $p$. So,

$S_{4}\leq\sum_{d_{1}\mid d}\sum_{\begin{subarray}{c}s\leq x\\\
\gcd(\lambda(s),d_{1})=d_{1}\end{subarray}}\Lambda(s)f(s,d_{1})^{2}=O\left(d^{2}\sum_{s\leq
x}\Lambda(s)\right)=O(d^{2}x).$

It remains to deal with $S_{3}$. For this we proceed as in [7] and split into
$S_{3,1}$ and $S_{3,2}$ with $S_{3,1}$ being the sum over small $s$ (say
$s\leq(\log x)^{2}$) and $S_{3,2}$ being the sum over large $s$ (say $s>(\log
x)^{2}$). As in that proof, using results of Norton and Pomerance, we get that
for

(13) $\sum_{\begin{subarray}{c}p\leq x\\\ p\equiv
y_{i}(s,d_{1})\pmod{s}\end{subarray}}\frac{1}{p}=\frac{\log_{2}x}{s\phi(s)}+O\left(\frac{\log
s}{\phi(s)}\right)$

uniformly in $s,d_{1}$ and $i=1,\ldots,f(s,d_{1})$. Thus,

$\displaystyle S_{3,2}$ $\displaystyle\leq$ $\displaystyle\sum_{d_{1}\mid
d}\sum_{\begin{subarray}{c}(\log x)^{2}<s\leq x\\\
\gcd(\lambda(s),d)=d_{1}\end{subarray}}f(s,d_{1})\Lambda(s)\sum_{i=1}^{f(s,d_{1})}\sum_{\begin{subarray}{c}p\leq
x\\\ p\equiv y_{i}(s,d_{1})\pmod{s}\end{subarray}}\frac{x}{ps}$
$\displaystyle\ll$ $\displaystyle x\sum_{d_{1}\mid
d}\sum_{\begin{subarray}{c}(\log x)^{2}<s\leq x\\\
\gcd(\lambda(s),d)=d_{1}\end{subarray}}\left(\frac{f(s,d_{1})^{2}\Lambda(s)\log_{2}x}{s\phi(s)}+\frac{f(s,d_{1})^{2}\Lambda(s)\log
s}{s\phi(s)}\right)$ $\displaystyle\ll$ $\displaystyle\sum_{d_{1}\mid
d}\frac{xd_{1}^{2}(\log_{2}x)^{2}}{(\log x)^{2}}=o(d^{2}x),$

as $x\to\infty$. So, it remains to deal with $S_{3,1}$. Using again (13), we
get

$\displaystyle S_{4,1}$ $\displaystyle=$ $\displaystyle\sum_{d_{1}\mid
d}\sum_{\begin{subarray}{c}s\leq(\log x)^{2}\\\
\gcd(\lambda(s),d)=d_{1}\end{subarray}}f(s,d_{1})\Lambda(s)\sum_{i=1}^{f(s,d_{1})}\sum_{\begin{subarray}{c}p\leq
x/s\\\ p\equiv y_{i}(s,d_{1})\pmod{s}\end{subarray}}\frac{x}{ps}$
$\displaystyle=$ $\displaystyle\sum_{d_{1}\mid
d}\sum_{\begin{subarray}{c}s\leq(\log x)^{2}\\\
\gcd(\lambda(s),d)=d_{1}\end{subarray}}f(s,d_{1})^{2}\Lambda(s)\left(\frac{\log\log(x/s)}{\phi(s)}+O\left(\frac{\log
s}{\phi(s)}\right)\right)$ $\displaystyle=$ $\displaystyle
x\left(\sum_{d_{1}\mid d}\sum_{\begin{subarray}{c}s\leq(\log x)^{2}\\\
\gcd(\lambda(s),d)=d_{1}\end{subarray}}\frac{f(s,d_{1})^{2}\Lambda(s)\log\log(x/s)}{s\phi(s)}+O\left(\sum_{d_{1}\mid
d}\sum_{\begin{subarray}{c}s\leq(\log x)^{2}\\\
\gcd(\lambda(s),d)=d_{1}\end{subarray}}\frac{f(s,d_{1})^{2}\Lambda(s)\log
s}{s\phi(s)}\right)\right).$

The inner sum inside the $O$ over the $s$ is convergent so that sum is
$O(d^{2}x)$. The remaining sum is

$\displaystyle x\log_{2}x\sum_{d_{1}\mid
d}\sum_{\gcd(\lambda(s),d)=d_{1}}\frac{f(s,d_{1})^{2}\Lambda(s)}{s\phi(s)}$
$\displaystyle+$ $\displaystyle O\left(x\sum_{d_{1}\mid d}\sum_{s\leq(\log
x)^{2}}\frac{f(s,d_{1})^{2}\Lambda(s)\log s}{s\phi(s)\log x}\right)$
$\displaystyle+$ $\displaystyle O\left(x\sum_{d_{1}\mid
d}\sum_{\begin{subarray}{c}s>(\log x)^{2}\\\
\gcd(\lambda(s),d)=d_{1}\end{subarray}}\frac{f(s,d_{1})^{2}\Lambda(s)}{s\phi(s)}\right).$

In the error terms, the first one is $O(d^{2}x/\log x)=o(d^{2}x)$ as
$x\to\infty$ and the second one is $O(d^{2}\log_{2}x/(\log x)^{2})=o(d^{2}x)$.
Finally, note that the first term above is just $c_{3}x\log_{2}x$. This
finishes the proof. ∎

##  3\. Bad witnesses of the stronger test

The authors of [5] described the needed formalism concerning the product of
pseudo-primality tests. In this section, we study the average sizes of the set
of bad witnesses for a pseudo-primality test which is the product of several
Miller-Rabin tests by the Galois test.

###  3.1. Preliminaries

Let $n>2$ be an odd composite integer such that $n-1=2^{k}m$ with $m$ odd. Let

$\mathbf{F}(n)=\\{a\pmod{n}:a^{n-1}-1\equiv 0\pmod{n}\\},$

and

$\mathbf{MR}(n)=\\{a\pmod{n}:a^{m}\equiv 1\pmod{n},\ \text{ or }\
a^{2^{i}m}\equiv-1\pmod{n}\ \text{ for some }\ i<k\\}$

be the sets of bad witnesses for the Fermat test and the Miller-Rabin test
respectively. Then $\mathbf{MR}(n)$ is a subset of $\mathbf{F}(n)$, and the
later is a subgroup of the group of units in ${\mathbb{Z}}/n{\mathbb{Z}}$.
Note that $\\#\mathbf{F}(n)=F(n)$, where $F(n)$ is given in equation
$(\ref{eq:21})$. Set $\\#\mathbf{MR}(n)=M\\!R(n)$. Let $v_{p}(n)$ be the
exponent on $p$ in the prime factorization of $n$. For a positive integer $k$
we let $k^{\prime}:=(k-1)/2^{\nu_{2}(k-1)}$ denote $\text{the largest odd
divisor of }k-1.$ For example, $n^{\prime}=m$. We set

(14) $v(n)=\text{min}_{p|n}\\{v_{2}(p-1)\\},\quad w(n)=\sum_{p|n}1,\quad
s(n)=\prod_{p|n}(n^{\prime},p^{\prime}).$

Then

(15) $M\\!R(n)=\left(1+\frac{2^{v(n)w(n)}-1}{2^{w(n)}-1}\right)s(n).$

It is shown ([7], proof of Theorem 5.2) that

$\displaystyle\frac{2}{x}\sum_{\begin{subarray}{c}1\leq n\leq c\\\ n\equiv
1\pmod{2}\end{subarray}}\log M\\!R(n)$ $\displaystyle=$
$\displaystyle\left(c_{1}-\frac{2\log 2}{3}\right)\log\log x+\log c_{2}+1+\log
2$ $\displaystyle-\sum_{i\geq 1}\frac{C(2^{i})}{2^{i}}\log
2+O\left(\frac{\log\log x}{\sqrt{\log x}}\right),$

where

(17) $C(d)=O\left(\frac{\log d}{\varphi(d)}\right)\text{ for any integer
}d\geq 2,$

and $c_{1},c_{2}$ are explicit constants defined in equation $(\ref{eq:5})$.

###  3.2. Arithmetic mean of the bad witnesses of the stronger test

Let $x$ be a large real number. It is shown ([7], proof of Theorem 5.1) that
there exist real numbers $\alpha,\beta,\varepsilon$ with

$\beta>23/8,\ 1<\alpha<\beta,\ 0<\varepsilon<\alpha-1\quad(\varepsilon\text{
arbitrarily small })\ \text{such that }\ M\\!R(n)>x^{1-\varepsilon}/\log\log
x,$

and a certain set $\mathbf{S}^{\prime}$ of positive integers $n\leq x$ such
that

$\\#\mathbf{S}^{\prime}\geq x^{(\alpha-1)\alpha^{-1}+o(1)}.$

Given a positive integer $r\geq 2$, we denote by $F^{r}(n)$ and $M\\!R^{r}(n)$
the number of bad witnesses of the product of $r$ Fermat tests and the product
of $r$ Miller-Rabin tests respectively. So

$M\\!R^{r}(n)>\left(\frac{x^{1-\varepsilon}}{\log\log x}\right)^{r},$

and

$\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}M\\!R^{r}(n)\geq\frac{1}{x}\sum_{n\in\mathbf{S}^{\prime}}x^{r-r\varepsilon+o(1)}\geq
x^{-1+r-r\varepsilon+o(1)}\cdot\\#\mathbf{S}^{\prime}=x^{r-r\varepsilon-\alpha^{-1}+o(1)}.$

Since $\varepsilon>0$ is arbitrarily small and $\alpha$ is arbitrarily close
to $\beta$, we have

$\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq x}M\\!R^{r}(n)\geq
x^{r-\beta^{-1}+o(1)}.$

Hence,

(18) $\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}M\\!R^{r}(n)\geq x^{r-\frac{8}{23}+o(1)}.$

On the other hand, let $\mathbf{C}_{k}(x)$ denote the set of composite number
$n\leq x$ such that

$F(n)=\varphi(n)/k\text{ for each integer }k.$

Set $C_{k}(x)=\\#\mathbf{C}_{k}(x)$. Since $M\\!R(n)\leq F(n)$, we have

${\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}M\\!R^{r}(n)\leq{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}F^{r}(n)=\sum_{k}\sum_{n\in\mathbf{C}_{k}(x)}F^{r}(n)$
$\leq\sum_{k}\sum_{n\in\mathbf{C}_{k}(x)}\frac{n^{r}}{k^{r}}$ $\leq\sum_{n\leq
x}\frac{n^{r}}{L^{r}(x)}+\sum_{k\leq
L(x)}\sum_{n\in\mathbf{C}_{k}(x)}\frac{n^{r}}{k^{r}}$
$\leq\frac{x^{r+1}}{L^{r}(x)}+x^{r}\sum_{k\leq L(x)}\frac{C_{k}(x)}{k^{r}}.$

It is shown ([7], proof of Theorem 2.2) that

$C_{k}(x)\leq xL(x)^{-1+o(1)}\quad\text{uniformly for }k\leq L(x),$

as $x\to\infty$. Further,

$\sum_{k\leq x}\frac{1}{k^{r}}<\zeta(r)<2,\quad\text{where }\zeta(r)\text{
denotes the Riemann zeta function,}$

since $r\geq 2$. So,

$\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq x}M\\!R^{r}(n)\leq
x^{r}L(x)^{-1+o(1)},$

and we have proved the following theorem.

######  Theorem 4.

For every integer $r\geq 2$, we have

$x^{r-\frac{8}{23}}<\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}M\\!R^{r}(n)\leq x^{r}L(x)^{-1+o(1)}\ \text{ as }x\to\infty.$

Denoting by $\mathbf{Str}(u)$ the sets of bad witnesses for the stronger test
and $Str(n)$ its cardinality, we deduce from Theorem 1, Theorem 2 and Theorem
4 the lower and upper bounds below.

######  Corollary 1.

As $x\to\infty$,

$x^{r+\frac{7}{23}}<\frac{1}{x}{\mathop{\sum\\!^{\prime}}\nolimits}_{n\leq
x}Str(n)\leq x^{r+d}\zeta(r)L(x)^{-2+o(1)}.$

###  3.3. Geometric mean of the bad witnesses of the stronger test

We start by studying the geometric mean of the number of bad witnesses of a
multiple-rounds Miller-Rabin test.

######  Theorem 5.

For $c_{1}$ given by $(\ref{eq:5})$ and $c_{4}$ defined in $(\ref{eq:7})$
below, we have

$\left(\prod_{1<n\leq x}M\\!R^{r}(n)\right)^{2/x}=c_{4}(\log
x)^{r(c_{1}-\frac{2\log 2)}{3})}+O\left(\frac{\log\log x}{\sqrt{\log
x}}\right)$

as $x\to\infty$.

###### Proof.

From Equation $(\ref{eq:23})$, we have

$\frac{2}{x}\sum_{\begin{subarray}{c}1\leq n\leq x\\\ n\equiv
1\pmod{2}\end{subarray}}\log(M\\!R^{r}(n))=r\left(c_{1}-\frac{2\log
2}{3}\right)\log\log x+\log(c_{2}^{r})+r+\log 2^{r}$ $-r\sum_{i\geq
1}\frac{C(2^{i})}{2^{i}}\log 2+O\left(\frac{\log\log x}{\sqrt{\log
x}}\right).$

The desired asymptotic formula follows by setting

(19) $c_{4}=\left(\frac{2ec_{2}}{2^{\sum_{i\geq
1}{C(2^{i})}{2^{i}}}}\right)^{r}.$

∎

Since $Gal(n)\geq F(n)$, it follows that the geometric mean value of $Str(n)$
is at least as large as the geometric mean value of $M\\!R^{r}(n)\times F(n)$.
By [7, Theorem 3.1] and Theorem 5, we know that $\Big{(}\prod_{1<n\leq
x}M\\!R^{r}(n)\times F(n)\Big{)}^{2/x}$ equals

$\Bigg{(}c_{4}(\log x)^{r(c_{1}-\frac{2\log 2}{3})}+O\left(\frac{\log\log
x}{\sqrt{\log x}}\right)\Bigg{)}\times\Bigg{(}c_{2}^{2}(\log
x)^{2c_{1}}+O\Big{(}(\log x)^{2c_{1}-1}\Big{)}\Bigg{)}.$

This means that

$\Big{(}\prod_{1<n\leq x}M\\!R^{r}(n)\times
F(n)\Big{)}^{2/x}=c_{4}c_{2}^{2}(\log x)^{(r+2)c_{1}-\frac{2r\log
2}{3}}+O\Big{(}(\log x)^{(r+2)c_{1}-(\frac{2r\log 2}{3}+1)}\Big{)}.$

On the other hand, the geometric mean of $Str(n)$ is at most as large as the
geometric mean of $\Big{(}M\\!R^{r}(n)\times H(n)\Big{)}^{2/x}$ because
$Gal(n)$ divides $H(n)$. By Theorem 3 and Theorem 5, we have that
$\Big{(}\prod_{1<n\leq x}M\\!R^{r}(n)\times H(n)\Big{)}^{2/x}$ is of order

$\asymp_{d}(\log x)^{r\left(c_{1}-\frac{2\log 2}{3}\right)+2c_{3}},$

where the constant implied by the above sign are of size $e^{O(d^{4})}$.

##  4\. Conclusion and Perspectives

This work describes the arithmetic and geometric mean values of the number of
bad witnesses $Str(n)$ when testing the primality of $n$ by using a pseudo-
primality test which is the product of a multiple-rounds Miller-Rabin test by
the Galois test. We actually compute functions which squeeze these mean
values. These bounds can still be improved. On the other hand, one could also
study the normal order of $Str(n)$, that is its behaviour on a set of natural
numbers of asymptotic density $1$. We thus have at least two alternatives for
future work.

## References

  * [1] W. R. Alford, Andrew Granville, and Carl Pomerance.  There are infinitely many Carmichael numbers.  Ann. Math. (2), 139(3):703–722, 1994.
  * [2] M. M. Artjuhov.  Certain criteria for primality of numbers connected with the little fermat theorem.  Acta Arith., 12:355–364, 1966/1967.
  * [3] A. Balog.  "$p+1$ without large prime factors".  Séminaire de Théorie des Nombres de Bordeaux, (1983)-(1984), no. 31.
  * [4] Henri Cohen.  A course in computational algebraic number theory, volume 138 of Grad. Texts Math. Berlin: Springer-Verlag, 1993.
  * [5] Jean-Marc Couveignes, Tony Ezome, and Reynald Lercier.  A faster pseudo-primality test.  Rend. Circ. Mat. Palermo (2), 61(2):261–278, 2012.
  * [6] Paul Erdös.  On the normal number of prime factors of $p-1$ and some related questions concerning $\mathrm{E}$uler’s $\phi$-function.  Quart. J. Math. Oxford Ser., 6:205–213, 1935.
  * [7] Paul Erdös and Carl Pomerance.  On the number of false witnesses for a composite number.  Math. Comp., 46(173):259–279, 1986.
  * [8] Tony Ezome.  Tests de primalité et de pseudo-primalité.  Publications Mathématiques de Besançon, pages 89–106, 2013\.
  * [9] G. H. Hardy and E. M. Wright.  Introduction to the Theory of Numbers.  Actualités Scientifiques et Industrielles, No. 1308. Oxford Univ. Press, London, 1965.
  * [10] Gary L. Miller.  Riemann’s hypothesis and tests for primality.  Kibern. Sb., Nov. Ser., 23:31–50, 1986.
  * [11] Carl Pomerance.  Popular values of euler’s function.  Mathematika, 27:84–89, 1980.
  * [12] Michael O. Rabin.  Probabilistic algorithm for testing primality.  J. Number Theory, 12:128–138, 1980.
  * [13] René Schoof.  Four primality testing algorithms.  In Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., pages 101–126. Cambridge Univ. Press, Cambridge, 2008.


# Energy Consumption and Performance of
Heapsort in Hardware and Software*
††thanks: This work is supported by the Innovation Fund Denmark for the
project DIREC (9142-00001B) and by CERCIRAS Cost Action CA19135.

Maja H. Kirkeby, Thomas Krabben, Mathias Larsen,
Maria B. Mikkelsen, Mads Rosendahl, Martin Sundman  Department of People and
Technology
Roskilde University
Roskilde, Denmark
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Tjark Petersen, Martin Schoeberl
DTU Compute
Technical University of Denmark
Lyngby, Denmark
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this poster abstract we will report on a case study on implementing the
Heapsort algorithm in hardware and software and comparing their time and
energy consumption. Our experiment shows that the Hardware implementation is
more energy efficient, but slower than the Software implementation due to a
low clock frequency. It also indicate that the optimal degree of
parallelization differs when optimizing for time compared to optimizing for
time.

###### Index Terms:

Heapsort, Energy Consumption, Performance, Hardware & Software implementation

##  I Background

Programs running on a general purpose computer consume a considerable amount
of energy. Some programs can be translated into hardware and executed on an
field-programmable gate array (FPGA). The study presented here is a first step
in studying whether and how it is possible to reduce energy consumption of IT
systems by moving algorithms from software into hardware (FPGAs). In this
first study, the focus is on implementations of a sorting algorithm: In later
works the framework will be extended to path finding algorithms

##  II Aims/purpose

We will do this by investigating the classic sorting algorithm Heapsort, e.g.,
see [2, Chp.6], implementing it in software and hardware and comparing their
performance and energy-efficiency. Such results are essential for reducing
energy and time consumption in both data centers as well as embedded systems.
The choice of Heapsort for this analysis is based on a number of factors.
Heapsort has a known worst and best case complexity of $O(n\log_{2}(n))$ with
limited data dependency on execution time; when generalizing the binary heap
to a $k$-heap the complexity is $O(n\log_{k}(n))$. Sorting can be done in
memory without using extra dynamic data. The algorithm also allows us to
parallelize certain elements of the algorithm and thus facilitating an
investigation of the effects parallel evaluation can have on resource and
energy consumption.

##  III Methods

Figure 1: Measured and Estimated Energy Consumption (in mJ) for Raspberry Pi
and FPGA, respectively. The third subfigure shows Estimated Energy Consumption
of sorting the randomly ordered list for different values of $k$.

### Software Implementation

The software implementation of Heapsort is written in C and is based on the
standard solution from Rosetta
Code111http://www.rosettacode.org/wiki/Sorting_algorithms/Heapsort which
follows the description in [2, Chp.6]. The solution implements a max-heap. For
easy comparison with the hardware implementation, the solution is altered so
that the input list is a variable in the compiled program and when the program
is executed the list elements are inserted into a heap structure. To ensure
the max-heap property when inserting or removing a new element, all the
nodes/elements violating the heap order are swapped while traversing the heap
until each node is larger than its children.

### Hardware Implementation

The hardware implementation consists of a heap module and a state machine. The
latter first inserts all input elements from an on-chip memory into the heap
and afterwards writes them in sorted order from the heap back into the on-chip
memory. The heap module has a variable tree order $k$. It maintains the max-
heap property the same way the software implementation does.

In the hardware solution, we can exploit parallelism in two cases: when
considering the memory layout, and when finding the maximum between a node and
its children. In both cases, more parallelism can be exploited by increasing
the tree order $k$. The heap module uses its own memory to store values while
they reside in the heap. All sibling nodes are spread over $k$ memory banks.
This gives us single cycle access to all children of a given node at the same
time. Finding the maximum between a node and its children can be parallelized
using a reduction tree. Like in a tournament, we find the maximum between
pairs, halving the candidates in each cycle until only one winner is left.
This reduces the number of cycles from $k$ to $\log_{2}(k)$ for this
operation.

### Measuring and Estimating Time, Power, and Energy

Because the runtime depends on (i) the number of elements of Heapsort’s input
lists, we have varied the number of elements in the input lists, i.e., the
size, from 4096 up to 16384 elements; and (ii) the order of these elements, we
have (for each size) generated three different versions of each input list:
one with random order, one with sorted elements and one with reverse sorted
elements. We have used the same lists as input to both the software and
hardware implementations.

The software Heapsort implementation in C is executed on a standard _Raspberry
Pi 4 computer Model B 4GB RAM and a 1.5 GHz 64-bit quad-core ARM Cortex-A72
processor_ using the `gcc` compiler222Version: gcc (Raspbian 8.3.0-6+rpi1)
8.3.0 with flag `-O2`. We have created one program per input list.We measure
the energy consumption for the entire Raspberry Pi using a programmable power
supply _Siglent SPD3303X-E Linear DC 3CH_. To obtain average power dissipation
and average execution times, we executed each program 2000 times with 20
seconds sleep in between. This approach allowed us to measure the execution
time 2000 times for each program and at the same time sampling the power
dissipation externally.

The execution time of the hardware Heapsort implementation is deterministic
for a given data set. We can therefore identify the exact number of cycles for
each test case by running a simulation. For this purpose, we have used the
Chiseltest framework [1]. We have synthesized the design to the Digilent Basys
3 Artix-7 FPGA board for all configurations. The number of clock cycles
together with the 100MHz clock frequency of the Basys 3 board give us exact
run time results, which are provided in Table I. To obtain energy estimates,
we have used Xilinx Vivado’s built-in power reporting tool; this provides
rough power dissipation estimates for the hardware implementations.

##  IV Results

The execution time increases steadily relative to the number of inputs for
both implementations, see Table I with the results for a standard binary heap,
i.e., $k=2$. The hardware implementation runs slightly faster for input sizes
$4096$ and $6144$, whereas the software implementation runs faster for larger
input sizes, see “Time” column in Table I. This is expected since Raspberry
processor runs 15 times faster, when they both execute the same operations
(sequentially).

Figure 1 show that the energy consumption of the implementations increase with
the number of elements to be sorted. For the software implementation, the
measured power dissipation had only minor variations and the execution is an
accurate proxy of the energy consumption I; this aligns with the findings for
sequential Haskell programs [3]. While the execution time for the hardware
implementations is predictable, its estimated energy consumption is less
predictable; this could be due to the uncertainty introduced by the rough
estimates of the power dissipation.

When considering $k$-heaps, our experiments showed an increase of performance
of the hardware implementation when $k$ increased. This aligns with the
complexity of the algorithm and especially for hardware this is expected,
since a higher $k$ facilitates a higher degree of parallelism. While $k=128$
is the better choice when optimizing the hardware implementation for time,
Figure 1 demonstrates that $k=16$ is optimal when optimizing for energy
(assuming at least relative precision of the power dissipation estimates).

TABLE I: The avg. execution time and energy consumption of hardware with $k=2$ (FPGA) over software (Raspberry Pi) executions for random input, together with the FPGA’s (non)-improvements over the Raspberry Pi. | Time (ms) | Energy Cons. (mJ) | FPGA Improvement
---|---|---|---
Size | Rasp. Pi | FPGA | Rasp. Pi | FPGA | Time | Energy
4096 | 8.001 | 5.386 | 27.27 | 0.522 | 1.486 | 52.241
6144 | 9.263 | 8.479 | 31.824 | 1.085 | 1.092 | 29.331
8192 | 10.696 | 11.665 | 37.015 | 1.271 | 0.917 | 29.123
10240 | 12.023 | 14.963 | 41.17 | 2.574 | 0.804 | 15.995
12288 | 13.137 | 18.322 | 45.148 | 3.023 | 0.717 | 14.935
14336 | 14.604 | 21.737 | 49.678 | 3.521 | 0.672 | 14.109
16384 | 15.749 | 25.138 | 53.39 | 3.343 | 0.627 | 15.971

##  V Conclusion

In this poster abstract, we have compared performance and energy efficiency of
software and hardware implementations of Heapsort. We find that while the
hardware implementation runs slower on an FPGA board compared to running the
software implementation on a Rasperry Pi; the hardware implementation is more
energy efficient. We also note that the optimal degree of parallelization of
the hardware implementation differs when optimizing for energy versus
optimizing for time.

## References

  * [1] Chiseltest github repository.  https://github.com/ucb-bar/chiseltest.  Accessed: 31-03-2022.
  * [2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  Introduction to Algrithms, 3rd Edition (The MIT Press).  2009\.
  * [3] Luís Gabriel Lima, Francisco Soares-Neto, Paulo Lieuthier, Fernando Castor, Gilberto Melfe, and João Paulo Fernandes.  Haskell in green Land: Analyzing the energy behavior of a purely functional language.  2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering, SANER 2016, 1:517–528, 2016.