#  Contrastive Learning for Object Detection

Rishab Balasubramanian Kunal Rathore
Oregon State University
{balasuri<EMAIL_ADDRESS>
##  1 Introduction

###  1.1 Problem Statement

In this project we will be working on Object Detection using Contrastive
Learning. The goal of the project is to implement and evaluate the success of
contrastive learning paradigm for learning better feature representations, and
use these for object detection.

Contrastive Learning follows from traditional triplet-loss, where similarity
between an “anchor” and “positive” is maximized, and the similarity between
“anchor” and “negative” is minimized. Contrastive learning is commonly used as
a method of self-supervised learning with the “anchor” and “positive” being
two random augmentations of a given input image, and the “negative” is the set
of all other images. This has been shown to outperform traditional approaches
such as the triplet loss and N-pair loss in [1]. However, the requirement of
large batch sizes and memory banks has made it difficult and slow to train
([1], [3], [2]). This motivated the rise of Supervised Contrasative approaches
that overcome these problems by using annotated data [5]. However there is no
explicit emphasis on learning good representation, but rather the idea is to
cluster points into regions such that they are separable in the higher
dimensional parameter space. The authors in [4] make an attempt at enforcing
better representation learning into the contrastive learning framework by
clustering classes together based on their similarity to each other.

Inspired by this approach, we look to rank classes based on their similarity,
and observe the impact of human bias (in the form of ranking) on the learned
representations. We feel this is an important question to address, as learning
good feature embeddings has been a long sought after problem in computer
vision. This would also be important for similar domains such as OOD
detection, image matching/retrieval, and other tasks which require a good
representation of the images. Code available at
https://github.com/rishabbala/Contrastive_Learning_For_Object_Detection

###  1.2 Scope and Challenges

We work in a supervised setting with labels for the bounding boxes of objects
and their corresponding class. We work with VOC 2007, a sufficiently large
dataset of annotated images belonging to 20 different classes. The main
challenge in our work would be the training time for multiple experiments. Due
to the longer training time, and batch size of contrastive learning, we would
need access to GPUs for our experiments. The class similarity rankings, which
are a user input are also a challenge as they would require manual tuning and
multiple experiments to identify useful ranking order.

##  2 Approach

(a)
Figure 1: Our Approach

Fig 1 shows the approach we follow for training our model. Given an input
image, we pass it through the Object Detection module to predict bounding
boxes (Sec 2.1). Once the bounding boxes are predicted, we perform a Two-Crop
transformation on each object in the image (Sec 2.2), and pass it through our
Contrastive Learning framework (Sec 2.3). We divide the process into three
main stages

  * •

Object Detection

  * •

Two Crop Augmentations

  * •

Object Classification

###  2.1 Object Detection

(a)
Figure 2: Faster RCNN

In this work we use Faster RCNN [6] for object detection. Faster RCNN has two
main components, a region proposal network (RPN), and a classification
network. We remove the classification network and retain only the proposed
bounding boxes by the RPN. Fig 2 (adapted from d2l) shows the Faster RCNN
pipeline used in our work. Given the location of the bounding boxes, the image
is cropped at these locations and a two-crop transformation is performed.

###  2.2 Two Crop Transformation

(a)
Figure 3: Proposed transformations

The cropped images at the location of the bounding boxes are stacked together
into a batch of images. We first normalize the images using the mean and
standard deviation of the dataset. Then we follow the standard transformations
for Contrastive Learning proposed in [5], as shown in Fig 3. Of these we do
not use the cutout, blur, and sobel filter augmentations proposed. We perform
two random combination using a subset of these methods to produce two
augmentations of the image. The first is the “anchor”, and the second falls in
the “positive” class.

###  2.3 Object Classification

(a)
Figure 4: Traditional Contrastive Learning approaches are binary (left), where
there is a single “anchor”, and a single “positive” image/class. We use a
ranking system to improve learned features (right)

Fig 4 (adapted from [4]) shows the Contrastive Learning approach we use. We
follow [4], and use a ranked supervised contrastive learning method, where the
ranking is user defined. This is different from traditional approaches which
use a single “positive” image/class.

For each anchor (query) image $q$, we rank a number of similar classes as
$\mathcal{P}_{1}\cdots\mathcal{P}_{r}$, where $r$ denotes the number of
positive classes in our ranking. We also define a negative class as
$\mathcal{N}$. Let $h(q,x)$ be the cosine similarity between the query and any
other image $x$. Then, we can define our objective as enforcing :

$h(q,\mathcal{P}_{1})>h(q,\mathcal{P}_{2})>\cdots
h(q,\mathcal{P}_{r})>h(q,\mathcal{N})$ (1)

We do this by defining a loss $L=\sum_{i=1}^{r}l_{i}$ where

$\mathit{l_{i}}=-\log\frac{\sum_{p\in\mathcal{P}_{i}}\exp(\frac{h(q,p)}{\tau_{i}})}{\sum_{p\in\cup_{j\geq
i}\mathcal{P}_{i}}\exp(\frac{h(q,p)}{\tau_{i}})+\sum_{n\in\mathcal{N}\exp(\frac{h(q,n)}{\tau_{i}})}}$
(2)

This can be thought of as recursively computing the loss ($L$), when
considering the current highest ranked class ($i$) as “positive” and all other
classes as negative. After computing the loss, the current highest ranked
class ($i$) is removed, and the loss is computed again for class $i+1$. To
ensure good separation, we set $\tau_{i+1}>\tau_{i}$, following the empirical
studies provided in [4].

Opposed to [4], we rank classes instead of clustering them into groups. The
difference between them is that in our ranking, any class could be ranked
similar to any other class, with a user defined score. However, in clustering
as done in [4], only the classes within the same cluster are considered
similar. For example, [4] puts the classes “aeroplane” and “ship” together as
“vehicles”. However, from human knowledge, we know that an “aeroplane” is also
(probably more) similar to a “bird” than a “ship”. Hence in our method, we
create the ranking for the class “aeroplane” as {“bird”, “ship”, … } with
decreasing order of similarity from left to right.

##  3 Evaluation

###  3.1 Implementation Details

  * •

We use the detectron2 library [7] open sourced by Facebook for the bounding
box predictions. We use a ResNet 50 FPN backbone for object detection

  * •

We build upon the code provided in [4] to incorporate our ranking and
experiments.

  * •

We used ResNet backbone 50 for all our Contrastive Learning experiments

  * •

We run our experiments with a batch size of 32 with the VOC2007 dataset

  * •

We trained our model for 500 epochs

  * •

We use cosine similarity, with a learning rate of 0.5, and a learning decay
rate of 0.1.

  * •

We set the temperature in the loss $\tau\in[0.1,0.6]$

  * •

The experiments are conducted with the number of positively ranked classes
$r\in\\{1,3,5\\}$

###  3.2 Dataset

We evaluate on the VOC2007 dataset, which has 20 classes, 9963 images and
24640 objects (bounding boxes). This is split into 5011 images in the
training/val set and 4952 images in the test set, with similar number of
objects between the two. The dataset provides the images, ground truth
bounding box annotations, and the corresponding class for each bounding box.

###  3.3 Metrics And Comparison

We evaluate the mAP for the object detection stage and evaluate classification
accuracy for the Contrastive Learning model. We compare the accuracy with
SupCL ([5] where there is no ranking), RINCE ([4], where similar classes are
clustered together), and SoftMax (common discriminative approach of training a
ResNet 50 with a SoftMax loss). Extra Credit: We also test our model for
detecting OOD classes. In this case we plot the ROC curve of True positive
Rate vs False Positive Rate and compare the Area Under the Curve.

Model |  AP |  AP50 |  AP75
---|---|---|---
Faster RCNN (trained on VOC2007 train+val) ResNet50 FPN |  45.254 |  72.746 |  49.338

Table 1: Object Detection scores

###  3.4 Results & Evaluations

(a)

(b)

(c)

(d)

(e)

(f)

Figure 5: Results

We first evaluate the efficiency of the Faster-RCNN model in predicting
bounding boxes. To do so, we compute the AP scores using a pre-trained model.
Table 1 shows the AP, AP50, and AP75 scores of the Object detection module we
used. This is lower than the values reported in the Faster RCNN paper, and
also lower than more modern approaches. Since the objective was not only
object detection, we did not try different detection models.

Table 2 shows the classification accuracy on the VOC2007 dataset, and Fig 5
shows the results from our model. We observe that again our accuracy is
comparable to RINCE ([4]) and SupCL ([5]), while the discriminative
classification receives a much lower score. However, we observed that our
scores are slightly lesser than SupCL and RINCE. Since, all other parameters
were similar during testing, the two factors that affects these results the
most is ranking, and the user-tuned class-similarity scores. Due to the
diverse nature of classes in the dataset, it resulted in sparser ranking which
affects the performance of this approach.

Method | Classification Accuracy
---|---
SupCL ($r$=1) | 0.6499
Ours($r$=3) | 0.6068
RINCE($r$=5) | 0.6368
SoftMax | 0.5829
Table 2: Classification Accuracy on VOC2007

(a)

(b)

(c)

Figure 6: ROC plots for VOC

###  3.5 Extra Credit: Out of Distribution Detection

We finally evaluate our model’s performance for OOD object detection. We
evaluate on the VOC2007 dataset, with 2 classes withheld and show the ROC
curve in Fig 6 and the AUROC in Table 3. We see that our model does not
perform better than the baselines. This shows that our method enforces good
representation learning when human input is given, but the representations for
new classes are poor. We can conclude that given an unobserved object class,
our model pushes it close to one of the known classes thus resulting in poor
results.

Method | AUROC
---|---
SupCL ($r$=1) | 0.6679
Ours($r$=5) | 0.5532
SoftMax | 0.5621
Table 3: AUROC on VOC2007 with 2 classes withheld

###  3.6 Runtimes & Hardware

We train all our models on the HPC cluster using a Tesla V100 GPU. For
training we use a batch size of 32, and observe that it takes around 1.5-2
minutes per epoch During testing we observe that we take 2 minutes to to
generate results over the validation set. Evaluation of the Average Precision
scores for Faster RCNN takes about 5 minutes.

###  3.7 Individual Contributions

Kunal worked on the object detection pipeline, and its evaluation. Rishab
worked on setting up the Contrastive Learning experiments and training them.
We worked together for OOD Detection. We filled up our respective portions in
the report, and made changes together.

## References

  * [1] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [2] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  arXiv preprint arXiv:2003.04297, 2020.
  * [3] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729–9738, 2020.
  * [4] David T Hoffmann, Nadine Behrmann, Juergen Gall, Thomas Brox, and Mehdi Noroozi.  Ranking info noise contrastive estimation: Boosting contrastive learning via ranked positives.  arXiv preprint arXiv:2201.11736, 2022.
  * [5] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan.  Supervised contrastive learning.  Advances in Neural Information Processing Systems, 33:18661–18673, 2020.
  * [6] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  Advances in neural information processing systems, 28, 2015.
  * [7] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick.  Detectron2.  https://github.com/facebookresearch/detectron2, 2019.


# Connecting two types of representations of a permutation of $\mathbb{F}_{q}$

Zhiguo Ding  Hunan Institute of Traffic Engineering, Changsha, Hunan 410005
China<EMAIL_ADDRESS>
###### Abstract.

In this paper, we connect two types of representations of a permutation
$\sigma$ of the finite field $\mathbb{F}_{q}$. One type is algebraic, in which
the permutation is represented as the composition of degree-one polynomials
and $k$ copies of $x^{q-2}$, for some prescribed value of $k$. The other type
is combinatorial, in which the permutation is represented as the composition
of a degree-one rational function followed by the product of $k$ $2$-cycles on
$\mathbb{P}^{1}(\mathbb{F}_{q}):=\mathbb{F}_{q}\cup\\{\infty\\}$, where each
$2$-cycle moves $\infty$. We show that, after modding out by obvious
equivalences amongst the algebraic representations, then for each $k$ there is
a bijection between the algebraic representations of $\sigma$ and the
combinatorial representations of $\sigma$. We also prove analogous results for
permutations of $\mathbb{P}^{1}(\mathbb{F}_{q})$. One consequence is a new
characterization of the notion of Carlitz rank of a permutation on
$\mathbb{F}_{q}$, which we use elsewhere to provide an explicit formula for
the Carlitz rank. Another consequence involves a classical theorem of Carlitz,
which says that if $q>2$ then the group of permutations of $\mathbb{F}_{q}$ is
generated by the permutations induced by degree-one polynomials and $x^{q-2}$.
Our bijection provides a new perspective from which the two proofs of this
result in the literature can be seen to arise naturally, without requiring the
clever tricks that previously appeared to be needed in order to discover those
proofs.

A version of Theorem 1 of the present paper was originally proved as part of a
joint project with Michael Zieve which resulted in the paper [11]. The author
thanks Michael Zieve for encouraging him to publish Theorem 1 separately in
the present paper. The author thanks the referees and Michael Zieve for
suggesting improvements to the statement and proof of Theorem 1, which yielded
a stronger result than appeared in the original version of this paper.

##  1\. Introduction

Throughout, we assume that $q>2$ is a prime power and $\mathbb{F}_{q}$ is the
finite field with $q$ elements. Note that permutations of $\mathbb{F}_{q}$ can
be viewed as permutations of
$\mathbb{P}^{1}(\mathbb{F}_{q}):=\mathbb{F}_{q}\cup\\{\infty\\}$ which fixes
$\infty$. We will study two completely different types of representations of
permutations on $\mathbb{P}^{1}(\mathbb{F}_{q})$. The first type of
representations is essentially algebraical, and the second type of
representations is essentially combinatorial.

More precisely, fixing a positive integer $k$ and a permutation $\sigma$ of
$\mathbb{P}^{1}(\mathbb{F}_{q})$, we denote by $\mathcal{A}_{\sigma,k}$ the
set of all representations of $\sigma$ of the form

$\sigma=\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$

with $a_{1},a_{2},\dots,a_{k}\in\mathbb{F}_{q}$ and
$\mu(x)\in\mathbb{F}_{q}(x)$ of degree one, and similarly we denote by
$\mathcal{C}_{\sigma,k}$ the set of all representations of $\sigma$ of the
form

$\sigma=\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty)$

with $b_{1},b_{2},\dots,b_{k}\in\mathbb{F}_{q}$ and
$\nu(x)\in\mathbb{F}_{q}(x)$ of degree one.

The presentations in the set $\mathcal{A}_{\sigma,k}$ are algebraically nice,
since they are compositions of a degree-one rational function $\mu(x)$ with
the monomial $x^{q-2}$ and monic degree-one polynomials $x-a_{i}$ with $1\leq
i\leq k$. The presentations in the set $\mathcal{C}_{\sigma,k}$ are
combinatorially nice, since they are compositions of a degree-one rational
function $\nu(x)$ with $2$-cycles on $\mathbb{P}^{1}(\mathbb{F}_{q})$ of the
form $(b_{i},\infty)$ with $1\leq i\leq k$.

Although $\mathcal{A}_{\sigma,k}$ and $\mathcal{C}_{\sigma,k}$ are completely
different in nature, Theorem 7 gives a recipe to turn any representation in
$\mathcal{A}_{\sigma,k}$ into a representation in $\mathcal{C}_{\sigma,k}$,
and Theorem 8 gives a recipe to turn any representation in
$\mathcal{C}_{\sigma,k}$ into a representation in $\mathcal{A}_{\sigma,k}$.
Moreover, due to Theorem 6 the maps
$\mathcal{F}:\mathcal{A}_{\sigma,k}\to\mathcal{C}_{\sigma,k}$ and
$\mathcal{G}:\mathcal{C}_{\sigma,k}\to\mathcal{A}_{\sigma,k}$ induced by the
above two recipes respectively are inverses to one another. In other words,
there exist naturally two inverse bijections between $\mathcal{A}_{\sigma,k}$
and $\mathcal{C}_{\sigma,k}$, which are induced by the recipes as illustrated
in Theorem 7 and Theorem 8 respectively, as stated in the following:

######  Theorem 1.

For any positive integer $k$ and any permutation $\sigma$ of
$\mathbb{P}^{1}(\mathbb{F}_{q}):=\mathbb{F}_{q}\cup\\{\infty\\}$ with $q>2$,
there are two natural inverse bijections between the set
$\mathcal{A}_{\sigma,k}$ of all representations of $\sigma$ of the form

$\sigma=\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$

with $a_{1},a_{2},\dots,a_{k}\in\mathbb{F}_{q}$ and
$\mu(x)\in\mathbb{F}_{q}(x)$ of degree one and the set
$\mathcal{C}_{\sigma,k}$ of all representations of $\sigma$ of the form

$\sigma=\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty)$

with $b_{1},b_{2},\dots,b_{k}\in\mathbb{F}_{q}$ and
$\nu(x)\in\mathbb{F}_{q}(x)$ of degree one. In particular, the finite sets
$\mathcal{A}_{\sigma,k}$ and $\mathcal{C}_{\sigma,k}$ have the same
cardinality.

There are two easy consequences of our results. The first consequence is a new
characterization of the notion of Carlitz rank of a permutation on
$\mathbb{F}_{q}$, based on which an explicit formula about Carlitz rank has
been obtained in [11]. The second consequence involves a classical theorem of
Carlitz, which says that if $q>2$ then the group of permutations of
$\mathbb{F}_{q}$ is generated by the permutations induced by degree-one
polynomials and $x^{q-2}$. Our bijection in Theorem 1 provides a new
perspective from which the two proofs of this result in the literature can be
seen to arise naturally, without requiring the clever tricks that previously
appeared to be needed in order to discover those proofs.

This paper is organized as follows. In the next section, we prove some results
about permutations on $\mathbb{P}^{1}(\mathbb{F}_{q})$ which will be used in
our treatment. In section 3 we give a proof for Theorem 1 together with the
explicit recipe, which turns an algebraically nice representation of a
permutation of $\mathbb{P}^{1}(\mathbb{F}_{q})$ into a combinatorially nice
representation of the same permutation and vice versa. We conclude in section
4 by illustrating the above mentioned two consequences of our results.

##  2\. Basic facts

Let us begin with the following basic observation:

######  Lemma 2.

We have $(0,\infty)=x^{-1}\circ x^{q-2}$ as permutations of
$\mathbb{P}^{1}(\mathbb{F}_{q})$.

###### Proof.

Note that $x^{q-2}=x^{-1}$ for any nonzero element $x\in\mathbb{F}_{q}$, so
the map $x^{-1}\circ x^{q-2}$ fixes each element in $\mathbb{F}_{q}^{*}$. It
is not hard to verify directly that $x^{-1}\circ x^{q-2}$ exchanges the
remaining two points $0$ and $\infty$. ∎

Next, we need to know the conjugations of a given $2$-cycle $(b,\infty)$ with
$b\in\mathbb{F}_{q}$ by a degree-one polynomial $x-a$ and by the monomial
$x^{q-2}$ respectively. For this purpose let us give first the following fact:

######  Lemma 3.

The relation $f\circ(u,v)=(f(u),f(v))\circ f$ holds for any injective map $f$
of sets from $X$ to $Y$ and any two distinct $u,v\in X$.

###### Proof.

Both $f\circ(u,v)$ and $(f(u),f(v))\circ f$ send $x$ to $f(x)$ for any element
$x\in X\setminus\\{u,v\\}$, while both of them send $u$ to $f(v)$ and send $v$
to $f(u)$. ∎

######  Corollary 4.

The following identities hold as permutations of
$\mathbb{P}^{1}(\mathbb{F}_{q})$:

  * •

$(x-a)\circ(b,\infty)=(b-a,\infty)\circ(x-a)$ for any $a,b\in\mathbb{F}_{q}$,

  * •

$x^{q-2}\circ(b,\infty)=(b^{q-2},\infty)\circ x^{q-2}$ for any
$b\in\mathbb{F}_{q}$.

###### Proof.

The results follows from Lemma 3 by taking
$X=Y:=\mathbb{P}^{1}(\mathbb{F}_{q})$, $u:=b$, $v:=\infty$, letting
$f(x):=x-a$ and $f(x):=x^{q-2}$ respectively. ∎

Corollary 4 implies particularly that $x^{q-2}\circ(0,\infty)=(0,\infty)\circ
x^{q-2}$, which is just equal to $x^{-1}$ by Lemma 2. Moreover, it is
interesting to note that the composition of any two of the three permutations
$x^{-1},x^{q-2},(0,\infty)$ of $\mathbb{P}^{1}(\mathbb{F}_{q})$ is equal to
the third one. In other words, the subgroup of permutations of
$\mathbb{P}^{1}(\mathbb{F}_{q})$ with $q>2$ generated by $x^{-1}$, $x^{q-2}$,
and $(0,\infty)$ is exactly the Klein four-group.

After conjugating $(0,\infty)$ by the translation $x+a$, we can obtain the
following expression of a $2$-cycle of the form $(a,\infty)$ with
$a\in\mathbb{F}_{q}$:

######  Corollary 5.

$(a,\infty)=(x^{-1}+a)\circ x^{q-2}\circ(x-a)$ holds for any
$a\in\mathbb{F}_{q}$.

###### Proof.

By applications of Corollary 4 and Lemma 2, we have

$(a,\infty)=(x+a)\circ(0,\infty)\circ(x-a)=(x+a)\circ x^{-1}\circ
x^{q-2}\circ(x-a),$

which is equal to $(x^{-1}+a)\circ x^{q-2}\circ(x-a)$ obviously. ∎

##  3\. Proof of Theorem 1

For a fixed positive integer $k$, let us define maps
$F:\mathbb{F}_{q}^{k}\to\mathbb{F}_{q}^{k}$ and
$G:\mathbb{F}_{q}^{k}\to\mathbb{F}_{q}^{k}$ as follows, which will be used to
illustrate the recipes in Theorem 7 and Theorem 8 respectively.

Define $F:\mathbb{F}_{q}^{k}\to\mathbb{F}_{q}^{k}$ by sending
$(a_{1},a_{2},\cdots,a_{k})$ to $(b_{1},b_{2},\cdots,b_{k})$, where
$b_{i}:=c_{i,i}$ for $1\leq i\leq k$, and for any fixed $1\leq i\leq k$ we
define $c_{i,j}$ with $0\leq j\leq i$ inductively by $c_{i,0}:=0$ and
$c_{i,j}:=c_{i,j-1}^{q-2}+a_{i-j+1}$.

In order to define the map $G:\mathbb{F}_{q}^{k}\to\mathbb{F}_{q}^{k}$, we
need to use the map
$\Phi_{\ell}:\mathbb{F}_{q}^{\ell}\to\mathbb{F}_{q}^{\ell-1}$ for each $\ell$
with $2\leq\ell\leq k$, which is defined to send
$(e_{1},e_{2},\dots,e_{\ell})$ to
$((e_{2}-e_{1})^{q-2},(e_{3}-e_{1})^{q-2},\dots,(e_{\ell}-e_{1})^{q-2})$. For
ease of notation, we will drop the subscript $\ell$ and write $\Phi$ for
$\Phi_{\ell}$ when the value of $\ell$ is clear from context.

Define $G:\mathbb{F}_{q}^{k}\to\mathbb{F}_{q}^{k}$ by sending
$(b_{1},b_{2},\dots,b_{k})$ to $(a_{1},a_{2},\dots,a_{k})$, where for $1\leq
i\leq k$ we denote by $a_{i}$ the first entry of
$\Phi^{i-1}(b_{1},b_{2},\dots,b_{k})$, in which the map
$\Phi^{i-1}:\mathbb{F}_{q}^{k}\to\mathbb{F}_{q}^{k-i+1}$ is really the
composition $\Phi_{k-i+2}\circ\Phi_{k-i+3}\circ\cdots\circ\Phi_{k}$ with the
convention that $\Phi^{0}$ is the identity map on $\mathbb{F}_{q}^{k}$. More
precisely, if we write

$\Phi^{i-1}(b_{1},b_{2},\dots,b_{k})=(d_{1,i-1},d_{2,i-1},\dots,d_{k-i+1,i-1})$

for $1\leq i\leq k$, then by definition we have

$(a_{1},a_{2},\dots,a_{k}):=(d_{1,0},d_{1,1},\dots,d_{1,k-1}).$

######  Theorem 6.

The maps $F:\mathbb{F}_{q}^{k}\to\mathbb{F}_{q}^{k}$ and
$G:\mathbb{F}_{q}^{k}\to\mathbb{F}_{q}^{k}$ are inverses of one another. In
particular, both $F$ and $G$ are bijections on $\mathbb{F}_{q}^{k}$.

###### Proof.

It suffices to show that $G\circ F$ is the identity map on
$\mathbb{F}_{q}^{k}$, since then $F$ is injective and $G$ is surjective, but
since each of $F$ and $G$ is a map on $\mathbb{F}_{q}^{k}$, it follows that
$F$ and $G$ are bijective, whence $F$ and $G$ are inverse bijections since
$G\circ F$ is the identity map on $\mathbb{F}_{q}^{k}$ again.

Now, let us show that $G\circ F$ is the identity map on $\mathbb{F}_{q}^{k}$.
Given $a_{1},a_{2},\dots,a_{k}$ in $\mathbb{F}_{q}$, recall that for $1\leq
i\leq k$ the elements $c_{i,j}$ with $0\leq j\leq i$ are defined inductively
by $c_{i,0}=0$ and $c_{i,j}=c_{i,j-1}^{q-2}+a_{i-j+1}$. Put $b_{j}=c_{j,j}$
for $1\leq j\leq k$, so that by the definition of $F$ we get

$F(a_{1},a_{2},\dots,a_{k})=(b_{1},b_{2},\dots,b_{k}).$

For $1\leq i\leq k$ let us write

$\Phi^{i-1}(b_{1},b_{2},\dots,b_{k})=(d_{1,i-1},d_{2,i-1},\dots,d_{k-i+1,i-1}),$

then by the definition of $G$ we have

$G(b_{1},b_{2},\dots,b_{k})=(d_{1,0},d_{1,1},\dots,d_{1,k-1}).$

We will show by induction on $j$ that $d_{i,j}=c_{i+j,i}$ holds for all $i,j$
with $0\leq j\leq k-1$ and $1\leq i\leq k-j$. The base case $j=0$ says that
$d_{i,0}=c_{i,i}$ for $1\leq i\leq k$, which is true since both sides equal
$b_{i}$. Inductively, if $1\leq j\leq k-1$, then for each $1\leq i\leq k-j$ we
have

$\displaystyle
d_{i,j}=(d_{i+1,j-1}-d_{1,j-1})^{q-2}=(c_{i+j,i+1}-c_{j,1})^{q-2}$
$\displaystyle=$
$\displaystyle(c_{i+j,i+1}-a_{j})^{q-2}=(c_{i+j,i}^{q-2})^{q-2}=c_{i+j,i},$

which concludes the induction. Thus

$\displaystyle G\circ F(a_{1},a_{2},\dots,a_{k})=G(b_{1},b_{2},\dots,b_{k})$
$\displaystyle=$
$\displaystyle(d_{1,0},d_{1,1},\dots,d_{1,k-1})=(c_{1,1},c_{2,1},\dots,c_{k,1})=(a_{1},a_{2},\dots,a_{k}).$

So $G\circ F$ is the identity map on $\mathbb{F}_{q}^{k}$, whence as explained
above it follows that $F$ and $G$ are inverse bijections on
$\mathbb{F}_{q}^{k}$. ∎

######  Theorem 7.

For any $a_{1},a_{2},\dots,a_{k}$ in $\mathbb{F}_{q}$, denote

$(b_{1},b_{2},\cdots,b_{k}):=F(a_{1},a_{2},\cdots,a_{k}),$

then

$\displaystyle x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$
$\displaystyle=$
$\displaystyle\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty),$

where

$\nu(x):=x^{-1}\circ(x-a_{k})\circ x^{-1}\circ(x-a_{k-1})\circ\cdots\circ
x^{-1}\circ(x-a_{1})$

is a degree-one rational function in $\mathbb{F}_{q}(x)$.

###### Proof.

We prove it by induction on $k$. The base case $k=1$ says

$x^{q-2}\circ(x-a_{1})=x^{-1}\circ(x-a_{1})\circ(b_{1},\infty)$

where $b_{1}=F(a_{1})=a_{1}$. This identity follows directly from Corollary 5.
Inductively, suppose $k>1$ and $a_{1},a_{2},\dots,a_{k}$ are in
$\mathbb{F}_{q}$. By definition, for $1\leq i\leq k$ we have $c_{i,0}=0$ and
$c_{i,j}=c_{i,j-1}^{q-2}+a_{i-j+1}$ with $1\leq j\leq i$. Write
$b_{i}=c_{i,i}$ for $1\leq i\leq k$, so that

$(b_{1},b_{2},\dots,b_{k})=F(a_{1},a_{2},\dots,a_{k}).$

For ease of expression, let us denote

$\lambda_{i}:=x^{-1}\circ(x-a_{k})\circ x^{q-2}\circ(x-a_{k-1})\circ
x^{q-2}\circ\cdots\circ x^{q-2}\circ(x-a_{i})$

for $1\leq i\leq k$, and denote

$\rho_{i}:=x^{q-2}\circ(x-a_{i})\circ x^{q-2}\circ(x-a_{i-1})\circ\cdots\circ
x^{q-2}\circ(x-a_{1})$

for $0\leq i\leq k$ where by convention $\rho_{0}=x$. Write

$\sigma:=x^{q-2}\circ(x-a_{k})\circ x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ
x^{q-2}\circ(x-a_{1}).$

Hence we have

$\displaystyle\sigma=\rho_{k}=$ $\displaystyle
x^{q-2}\circ(x-a_{k})\circ\rho_{k-1}$ $\displaystyle=$ $\displaystyle
x^{-1}\circ(0,\infty)\circ(x-a_{k})\circ\rho_{k-1}$ $\displaystyle=$
$\displaystyle x^{-1}\circ(x-a_{k})\circ(a_{k},\infty)\circ\rho_{k-1}$
$\displaystyle=$
$\displaystyle\lambda_{k}\circ(c_{k,1},\infty)\circ\rho_{k-1}.$

We claim that

$\lambda_{i+1}\circ(c_{k,k-i},\infty)\circ\rho_{i}=\lambda_{i}\circ(c_{k,k-i+1},\infty)\circ\rho_{i-1}$

for $1\leq i\leq k-1$. Indeed, for each $i$ with $1\leq i\leq k-1$, we have

$\displaystyle(c_{k,k-i},\infty)\circ\rho_{i}$ $\displaystyle=$
$\displaystyle(c_{k,k-i},\infty)\circ x^{q-2}\circ(x-a_{i})\circ\rho_{i-1}$
$\displaystyle=$ $\displaystyle
x^{q-2}\circ(c_{k,k-i}^{q-2},\infty)\circ(x-a_{i})\circ\rho_{i-1}$
$\displaystyle=$ $\displaystyle
x^{q-2}\circ(x-a_{i})\circ(c_{k,k-i+1},\infty)\circ\rho_{i-1}.$

Thus by prepending $\lambda_{i+1}$ to these permutations we get

$\displaystyle\lambda_{i+1}\circ(c_{k,k-i},\infty)\circ\rho_{i}$
$\displaystyle=$ $\displaystyle\lambda_{i+1}\circ
x^{q-2}\circ(x-a_{i})\circ(c_{k,k-i+1},\infty)\circ\rho_{i-1}$
$\displaystyle=$
$\displaystyle\lambda_{i}\circ(c_{k,k-i+1},\infty)\circ\rho_{i-1},$

which concludes the proof of the claim. So we have

$\sigma=\lambda_{k}\circ(c_{k,1},\infty)\circ\rho_{k-1}=\lambda_{k-1}\circ(c_{k,2},\infty)\circ\rho_{k-2}=\cdots=\lambda_{1}\circ(c_{k,k},\infty)\circ\rho_{0},$

which by definition is equal to

$x^{-1}\circ(x-a_{k})\circ x^{q-2}\circ(x-a_{k-1})\circ
x^{q-2}\circ\cdots\circ x^{q-2}\circ(x-a_{1})\circ(b_{k},\infty).$

By inductive hypothesis, we have

$\displaystyle x^{q-2}\circ(x-a_{k-1})\circ
x^{q-2}\circ(x-a_{k-2})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$
$\displaystyle=$ $\displaystyle x^{-1}\circ(x-a_{k-1})\circ
x^{-1}\circ(x-a_{k-2})\circ\cdots\circ x^{-1}\circ(x-a_{1})\circ$
$\displaystyle\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k-1},\infty).$

Therefore, we get

$\displaystyle\sigma=$ $\displaystyle x^{-1}\circ(x-a_{k})\circ
x^{-1}\circ(x-a_{k-1})\circ\cdots\circ x^{-1}\circ(x-a_{1})\circ$
$\displaystyle\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty),$

which concludes the induction and hence concludes the proof. ∎

######  Theorem 8.

For any $b_{1},b_{2},\dots,b_{k}$ in $\mathbb{F}_{q}$, denote

$(a_{1},a_{2},\dots,a_{k}):=G(b_{1},b_{2},\dots,b_{k}),$

then

$\displaystyle(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty)$
$\displaystyle=$ $\displaystyle\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1}),$

where

$\mu(x):=(x+a_{1})\circ x^{-1}\circ(x+a_{2})\circ
x^{-1}\circ\cdots\circ(x+a_{k})\circ x^{-1}$

is a degree-one rational function in $\mathbb{F}_{q}(x)$.

###### Proof.

Let us prove it by induction on $k$. The base case $k=1$ says

$(b_{1},\infty)=(x+a_{1})\circ x^{-1}\circ x^{q-2}\circ(x-a_{1})$

where $a_{1}=G(b_{1})=b_{1}$, which is true by Corollary 5. For the inductive
step, assume that $k>1$ and $b_{1},b_{2},\dots,b_{k}$ are in $\mathbb{F}_{q}$.
Write

$\Phi^{i-1}(b_{1},b_{2},\dots,b_{k})=(d_{1,i-1},d_{2,i-1},\dots,d_{k-i+1,i-1})$

for $1\leq i\leq k$, so that

$(a_{1},a_{2},\dots,a_{k})=G(b_{1},b_{2},\dots,b_{k})=(d_{1,0},d_{1,1},\dots,d_{1,k-1}).$

For ease of expression, let us define

$\gamma_{i}:=(x+b_{1})\circ
x^{-1}\circ(d_{1,1},\infty)\circ(d_{2,1},\infty)\circ\cdots\circ(d_{i-1,1},\infty)\circ
x^{q-2}\circ(x-b_{1})$

for $1\leq i\leq k$, and define

$\theta_{i}:=(b_{i+1},\infty)\circ(b_{i+2},\infty)\circ\dots\circ(b_{k},\infty)$

for $0\leq i\leq k$, where by convention $\gamma_{1}=(x+b_{1})\circ
x^{-1}\circ x^{q-2}\circ(x-b_{1})$ and $\theta_{k}=x$. Denote

$\tau:=(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty).$

Hence by Corollary 5 we have

$\tau=\theta_{0}=(b_{1},\infty)\circ\theta_{1}=(x+b_{1})\circ x^{-1}\circ
x^{q-2}\circ(x-b_{1})\circ\theta_{1}=\gamma_{1}\circ\theta_{1}.$

We claim that $\gamma_{i}\circ\theta_{i}=\gamma_{i+1}\circ\theta_{i+1}$ for
$1\leq i\leq k-1$. Indeed, for each $i$ with $1\leq i\leq k-1$, we have

$\displaystyle x^{q-2}\circ(x-b_{1})\circ\theta_{i}$ $\displaystyle=$
$\displaystyle x^{q-2}\circ(x-b_{1})\circ(b_{i+1},\infty)\circ\theta_{i+1}$
$\displaystyle=$ $\displaystyle
x^{q-2}\circ(b_{i+1}-b_{1},\infty)\circ(x-b_{1})\circ\theta_{i+1}$
$\displaystyle=$ $\displaystyle(d_{i,1},\infty)\circ
x^{q-2}\circ(x-b_{1})\circ\theta_{i+1}.$

Thus by prepending

$(x+b_{1})\circ
x^{-1}\circ(d_{1,1},\infty)\circ(d_{2,1},\infty)\circ\cdots\circ(d_{i-1,1},\infty)$

to these permutations, we get

$\displaystyle\gamma_{i}\circ\theta_{i}=$ $\displaystyle(x+b_{1})\circ
x^{-1}\circ(d_{1,1},\infty)\circ(d_{2,1},\infty)\circ\cdots$
$\displaystyle\circ(d_{i-1,1},\infty)\circ
x^{q-2}\circ(x-b_{1})\circ\theta_{i}$ $\displaystyle=$
$\displaystyle(x+b_{1})\circ
x^{-1}\circ(d_{1,1},\infty)\circ(d_{2,1},\infty)\circ\cdots$
$\displaystyle\circ(d_{i-1,1},\infty)\circ(d_{i,1},\infty)\circ
x^{q-2}\circ(x-b_{1})\circ\theta_{i+1}$ $\displaystyle=$
$\displaystyle\gamma_{i+1}\circ\theta_{i+1},$

which concludes the proof of the claim. So we have

$\tau=\gamma_{1}\circ\theta_{1}=\gamma_{2}\circ\theta_{2}=\cdots=\gamma_{k}\circ\theta_{k}$

which by definition is equal to

$(x+b_{1})\circ
x^{-1}\circ(d_{1,1},\infty)\circ(d_{2,1},\infty)\circ\cdots\circ(d_{k-1,1},\infty)\circ
x^{q-2}\circ(x-b_{1}).$

By inductive hypothesis, if we denote

$(\widehat{a_{1}},\widehat{a_{2}},\dots,\widehat{a_{k-1}}):=G(d_{1,1},d_{2,1},\dots,d_{k-1,1}),$

then

$\displaystyle(d_{1,1},\infty)\circ(d_{2,1},\infty)\circ\cdots\circ(d_{k-1,1},\infty)$
$\displaystyle=$ $\displaystyle(x+\widehat{a_{1}})\circ
x^{-1}\circ(x+\widehat{a_{2}})\circ
x^{-1}\circ\cdots\circ(x+\widehat{a_{k-1}})\circ x^{-1}\circ$
$\displaystyle\circ x^{q-2}\circ(x-\widehat{a_{k-1}})\circ
x^{q-2}\circ(x-\widehat{a_{k-2}})\circ\cdots\circ
x^{q-2}\circ(x-\widehat{a_{1}}).$

Note that for $1\leq i\leq k-1$ we have $\widehat{a_{i}}=a_{i+1}$ since

$\Phi^{i-1}(d_{1,1},d_{2,1},\dots,d_{k-1,1})=\Phi^{i}(b_{1},b_{2},\dots,b_{k}).$

Therefore, we have

$\displaystyle\tau=$ $\displaystyle(x+b_{1})\circ x^{-1}\circ(x+a_{2})\circ
x^{-1}\circ(x+a_{3})\circ x^{-1}\circ\cdots$ $\displaystyle\circ(x+a_{k})\circ
x^{-1}\circ x^{q-2}\circ(x-a_{k})\circ x^{q-2}\circ(x-a_{k-1})\circ\cdots$
$\displaystyle\circ x^{q-2}\circ(x-a_{2})\circ x^{q-2}\circ(x-b_{1}),$

which concludes the induction and the proof since $b_{1}=a_{1}$. ∎

We remark that Theorem 7 gives a recipe for turning an algebraical
presentation of a permutation on $\mathbb{P}^{1}(\mathbb{F}_{q})$ of the form

$\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$

into a combinatorial presentation of the same permutation of the form

$\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty),$

and conversely Theorem 8 gives a recipe for turning a combinatorial
presentation of a permutation on $\mathbb{P}^{1}(\mathbb{F}_{q})$ of the form

$\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty)$

into an algebraical presentation of the same permutation of the form

$\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1}),$

where $a_{1},a_{2}\dots,a_{k},b_{1},b_{2}\dots,b_{k}$ are elements in
$\mathbb{F}_{q}$ and $\mu(x),\nu(x)$ are degree-one rational functions in
$\mathbb{F}_{q}(x)$.

In other words, for any fixed permutation $\sigma$ of
$\mathbb{P}^{1}(\mathbb{F}_{q})$, there are two natural maps
$\mathcal{F}:\mathcal{A}_{\sigma,k}\to\mathcal{C}_{\sigma,k}$ and
$\mathcal{G}:\mathcal{C}_{\sigma,k}\to\mathcal{A}_{\sigma,k}$ induced by the
recipes illustrated in Theorem 7 and Theorem 8 respectively, where
$\mathcal{A}_{\sigma,k}$ is the set of all representations of $\sigma$ of the
form

$\sigma=\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$

with $a_{1},a_{2},\dots,a_{k}\in\mathbb{F}_{q}$ and
$\mu(x)\in\mathbb{F}_{q}(x)$ of degree one, and $\mathcal{C}_{\sigma,k}$ is
the set of all representations of $\sigma$ of the form

$\sigma=\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty)$

with $b_{1},b_{2},\dots,b_{k}\in\mathbb{F}_{q}$ and
$\nu(x)\in\mathbb{F}_{q}(x)$ of degree one.

Now we are ready to prove Theorem 1, which asserts the natural maps
$\mathcal{F}:\mathcal{A}_{\sigma,k}\to\mathcal{C}_{\sigma,k}$ and
$\mathcal{G}:\mathcal{C}_{\sigma,k}\to\mathcal{A}_{\sigma,k}$ induced by the
recipes in Theorem 7 and Theorem 8 respectively are inverses to one another.

###### Proof of Theorem 1.

It suffices to show that both $\mathcal{G}\circ\mathcal{F}$ and
$\mathcal{F}\circ\mathcal{G}$ are the identity maps, where
$\mathcal{F}:\mathcal{A}_{\sigma,k}\to\mathcal{C}_{\sigma,k}$ and
$\mathcal{G}:\mathcal{C}_{\sigma,k}\to\mathcal{A}_{\sigma,k}$ are the natural
maps induced by Theorem 7 and Theorem 8 respectively.

Given any algebraic representation of $\sigma$ in the set
$\mathcal{A}_{\sigma,k}$ of the form

$\sigma=\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$

with $a_{1},a_{2},\dots,a_{k}\in\mathbb{F}_{q}$ and
$\mu(x)\in\mathbb{F}_{q}(x)$ of degree one, by definition $\mathcal{F}$ sends
it to a combinatorial representation of $\sigma$ in $\mathcal{C}_{\sigma,k}$
of the form

$\sigma=\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty)$

with $b_{1},b_{2},\dots,b_{k}\in\mathbb{F}_{q}$ and
$\nu(x)\in\mathbb{F}_{q}(x)$ of degree one, in which

$(b_{1},b_{2},\cdots,b_{k}):=F(a_{1},a_{2},\cdots,a_{k}),$
$\nu_{0}(x):=x^{-1}\circ(x-a_{k})\circ x^{-1}\circ(x-a_{k-1})\circ\cdots\circ
x^{-1}\circ(x-a_{1}),$

and $\nu(x):=\mu(x)\circ\nu_{0}(x)$. This combinatorial representation is sent
by $\mathcal{G}$ to another algebraic representation of $\sigma$ in
$\mathcal{A}_{\sigma,k}$ of the form

$\sigma=\mu^{*}(x)\circ x^{q-2}\circ(x-a_{k}^{*})\circ
x^{q-2}\circ(x-a_{k-1}^{*})\circ\cdots\circ x^{q-2}\circ(x-a_{1}^{*})$

with $a_{1}^{*},a_{2}^{*},\dots,a_{k}^{*}\in\mathbb{F}_{q}$ and
$\mu^{*}(x)\in\mathbb{F}_{q}(x)$ of degree one, in which

$(a_{1}^{*},a_{2}^{*},\dots,a_{k}^{*}):=G(b_{1},b_{2},\dots,b_{k}),$
$\mu_{0}(x):=(x+a_{1}^{*})\circ x^{-1}\circ(x+a_{2}^{*})\circ
x^{-1}\circ\cdots\circ(x+a_{k}^{*})\circ x^{-1},$

and $\mu^{*}(x):=\nu(x)\circ\mu_{0}(x)$. By Theorem 6, the $k$-tuple

$(a_{1}^{*},a_{2}^{*},\dots,a_{k}^{*})=G(b_{1},b_{2},\dots,b_{k})=G\circ
F(a_{1},a_{2},\dots,a_{k})$

equals $(a_{1},a_{2},\dots,a_{k})$, i.e., we have $a_{i}^{*}=a_{i}$ for any
$1\leq i\leq k$. Thus $\mu_{0}(x)$ and $\nu_{0}(x)$ are inverse to one
another, which implies that

$\mu^{*}(x)=\nu(x)\circ\mu_{0}(x)=\mu(x)\circ\nu_{0}(x)\circ\mu_{0}(x)=\mu(x).$

Hence, $\mathcal{G}\circ\mathcal{F}$ is the identity map on the set
$\mathcal{A}_{\sigma,k}$. Similarly, we can show that
$\mathcal{F}\circ\mathcal{G}$ is the identity map on $\mathcal{C}_{\sigma,k}$.
Therefore, the natural maps
$\mathcal{F}:\mathcal{A}_{\sigma,k}\to\mathcal{C}_{\sigma,k}$ and
$\mathcal{G}:\mathcal{C}_{\sigma,k}\to\mathcal{A}_{\sigma,k}$ induced by
Theorem 7 and Theorem 8 respectively are inverse bijections. ∎

##  4\. Consequences

Note that any permutation of $\mathbb{F}_{q}$ can be extended uniquely to a
permutation of $\mathbb{P}^{1}(\mathbb{F}_{q})$. Hence permutations of
$\mathbb{F}_{q}$ can be regarded as permutations of
$\mathbb{P}^{1}(\mathbb{F}_{q})$ in this sense. By application of Theorem 1 to
permutations of $\mathbb{F}_{q}$, we get the following result:

######  Corollary 9.

Suppose $f$ is a permutation of $\mathbb{F}_{q}$, and then extends $f$ to a
permutation of $\mathbb{P}^{1}(\mathbb{F}_{q})$ which fixes $\infty$. Then in
any representation

$f=\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$

with $a_{1},a_{2},\dots,a_{k}\in\mathbb{F}_{q}$ and
$\mu(x)\in\mathbb{F}_{q}(x)$ of degree one, the rational function $\mu(x)$
must be a degree-one polynomial in $\mathbb{F}_{q}[x]$. Therefore, the set of
all representations of $f$ in the form of

$\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$

with $a_{1},a_{2},\dots,a_{k}\in\mathbb{F}_{q}$ and
$\mu(x)\in\mathbb{F}_{q}[x]$ of degree one is naturally bijective to the set
of all representations of $f$ in the form of

$\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty)$

with $b_{1},b_{2},\dots,b_{k}\in\mathbb{F}_{q}$ and
$\nu(x)\in\mathbb{F}_{q}(x)$ of degree one.

###### Proof.

Note that the degree-one rational function $\mu(x)\in\mathbb{F}_{q}(x)$ in any
representation of the extended permutation $f$ on
$\mathbb{P}^{1}(\mathbb{F}_{q})$ in the form of

$f=\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1})$

fixes the point $\infty$, since all of $f$, $x^{q-2}$, and $(x-a_{i})$ fix
$\infty$. Hence the first assertion follows from the fact that the degree-one
rational functions which fix $\infty$ are precisely the degree-one
polynomials. The second assertion is then a direct consequence of Theorem 1. ∎

The following is a classical result on permutations of $\mathbb{F}_{q}$, which
was posed as a question by Straus, and was first proved by Carlitz [3] and
then proved again by Zieve [22]:

######  Theorem 10.

If $q>2$ is a prime power, then every permutation of $\mathbb{F}_{q}$ is a
composition of $x^{q-2}$ and degree-one polynomials over $\mathbb{F}_{q}$.

Inspired by Theorem 10, Aksoy et al. [1] introduced the notion of the _Carlitz
rank_ of a permutation $f$ of $\mathbb{F}_{q}$, which means the smallest value
of $n\geq 0$ in any representation of $f$ of the form

$f=\theta_{0}\circ x^{q-2}\circ\theta_{1}\circ x^{q-2}\circ\dots\circ
x^{q-2}\circ\theta_{n}$

in which each $\theta_{i}$ is a degree-one polynomial in $\mathbb{F}_{q}[x]$.
For a systematic study of the general theory of Carlitz ranks and their
generalizations, see [11]. Carlitz ranks have been extensively studied in the
literature, see for example the papers [1, 6, 7, 8, 9, 14, 15, 16, 17, 19,
20]. For the history of permutation polynomials over a finite field, see the
papers [2, 3, 4, 5, 10, 12, 13, 18, 21].

As the first consequence, our results provide a new perspective on the theory
of Carlitz ranks from the point of view of combinatorics, instead of from the
point of view of algebra as in the literature previously.

More precisely, by Corollary 9 the Carlitz rank of a permutation $f$ of
$\mathbb{F}_{q}$ is exactly the smallest integer $n\geq 0$ for which the
uniquely extended permutation of $\mathbb{P}^{1}(\mathbb{F}_{q})$, which is
also denoted by $f$ by abuse of language, admits a combinatorial
representation of the form

$f=\nu(x)\circ(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{n},\infty)$

for some $b_{1},b_{2},\dots,b_{n}\in\mathbb{F}_{q}$ and some
$\nu(x)\in\mathbb{F}_{q}(x)$ of degree one.

Based on this new characterization of Carlitz rank, the following result on
the computation of Carlitz rank has be obtained in [11]:

######  Theorem 11.

Let $f=\mu\circ\sigma$ be a permutation of $\mathbb{F}_{q}$, where $\mu$ is a
degree-one rational function, and $\sigma$ is a permutation of
$\mathbb{P}^{1}(\mathbb{F}_{q})$ which moves $s$ points in $\mathbb{F}_{q}$
and has $t$ nontrivial orbits. Define $n:=s+t$ if $\sigma(\infty)=\infty$ and
$n:=s+t-1$ if $\sigma(\infty)\neq\infty$. Then the Carlitz rank of $f$ is at
most $n$, and it equals $n$ if in addition $q\geq n+s+2$.

As the second consequence, our results provide new perspective to Theorem 10.
Indeed, Theorem 10 follows easily from Corollary 9 in various ways, since any
permutation $f$ of $\mathbb{F}_{q}$ has many different ways to be represented
as

$f=(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{k},\infty)$

for some $k\geq 1$ and some $b_{1},b_{2},\dots,b_{k}\in\mathbb{F}_{q}$, and by
Corollary 9 any such combinatorial representation of $f$ gives rise to an
algebraic representation of $f$ as a composition of $k$ copies of $x^{q-2}$
and degree-one polynomials over $\mathbb{F}_{q}$, which concludes our proof
for Theorem 10.

More precisely, given any nontrivial permutation $f$ of $\mathbb{F}_{q}$, we
can write $f$ as the product of disjoint cycles of length at least two as
follows:

$f=(b_{11},b_{12},\dots,b_{1s_{1}})(b_{21},b_{22},\dots,b_{2s_{2}})\cdots(b_{t1},b_{t2},\dots,b_{ts_{t}}),$

where $t\geq 1$ and each $s_{i}\geq 2$ with $1\leq i\leq t$. Note that

$(b_{i1},b_{i2},\dots,b_{is_{i}})=(b_{i1},\infty)\circ[(b_{is_{i}},\infty)\circ\cdots\circ(b_{i2},\infty)\circ(b_{i1},\infty)],$

for any $1\leq i\leq t$. Hence we get a representation of $f$ of the form

$f=(b_{1},\infty)\circ(b_{2},\infty)\circ\cdots\circ(b_{n},\infty),$

where $s:=\Sigma_{i=1}^{t}s_{i}$, $k:=s+t$, and denote by
$(b_{1},b_{2},\dots,b_{k})$ the tuple

$((b_{11},b_{1s_{1}},\dots,b_{11}),(b_{21},b_{2s_{2}},\dots,b_{21}),\dots,(b_{t1},b_{ts_{t}},\dots,b_{t1})).$

By Theorem 8, if we denote

$(a_{1},a_{2},\dots,a_{k}):=G(b_{1},b_{2},\dots,b_{k}),$

then we obtain a representation of $f$ of the form

$f=\mu(x)\circ x^{q-2}\circ(x-a_{k})\circ
x^{q-2}\circ(x-a_{k-1})\circ\cdots\circ x^{q-2}\circ(x-a_{1}),$

where

$\mu(x):=(x+a_{1})\circ x^{-1}\circ(x+a_{2})\circ
x^{-1}\circ\cdots\circ(x+a_{k})\circ x^{-1}\in\mathbb{F}_{q}(x)$

is a rational function of degree one. Furthermore, $\mu(x)$ is a degree-one
polynomial over $\mathbb{F}_{q}$ by Corollary 9. Therefore, we obtain an
algebraic representation of the given permutation $f$ of $\mathbb{F}_{q}$ as a
composition of $k$ copies of $x^{q-2}$ and $k+1$ degree-one polynomials over
$\mathbb{F}_{q}$ as above. Moreover, if in addition $q\geq 2s+t+2$, then this
representation of $f$ is optimal in the sense that it has the least possible
copies of $x^{q-2}$, since in this case the Carlitz rank of $f$ is exactly $k$
by Theorem 11.

In particular, by application of the above procedure to $2$-cycles of the form
$(0,a)$ with $a\in\mathbb{F}_{q}^{*}$, we can recover uniformly both proofs
for Theorem 10 in Carlitz [3] and Zieve [22], which involve some clever tricks
and have not been related to each other previously.

First, let us review briefly the proofs for Theorem 10 in Carlitz [3] and
Zieve [22]. The starting point for both proofs is the same, i.e., it is enough
to show the result in the special case that the permutation is a $2$-cycle of
the form $(0,a)$ with $a\in\mathbb{F}_{q}^{*}$, since any permutation of
$\mathbb{F}_{q}$ can be written as a product of such $2$-cycles. But Carlitz
[3] and Zieve [22] give different expressions of the $2$-cycle $(0,a)$ as
compositions of $x^{q-2}$ and degree-one polynomials. More precisely, Carlitz
[3] relies on the mysterious observation that

$(0,a)=(-a^{2}x)\circ x^{q-2}\circ(x-a)\circ x^{q-2}\circ(x+1/a)\circ
x^{q-2}\circ(x-a),$

but does not explain how it could be found; Zieve [22] observes that

$(0,a)=(-ax+a)\circ x^{q-2}\circ(-x+1)\circ x^{q-2}\circ(-x+1)\circ
x^{q-2}\circ(x/a),$

which follows from the clever combination of Lemma 2 and the fact that the
degree-one rational function $1-x^{-1}$ induces an order-three permutation of
$\mathbb{P}^{1}(\mathbb{F}_{q})$ with a $3$-cycle $(\infty,1,0)$.

Now, we apply our procedure illustrated above to $2$-cycles $(0,a)$ with
$a\in\mathbb{F}_{q}^{*}$ to recover uniformly both of the above two
observations in Carlitz [3] and Zieve [22] respectively. Indeed, for any
$a\in\mathbb{F}_{q}^{*}$, there are two equally natural ways to express the
$2$-cycle $(0,a)$ as a product of some $2$-cycles of the form $(b,\infty)$
with $b\in\mathbb{F}_{q}$. More precisely, by our procedure the $2$-cycle
$(0,a)$ can be expressed naturally as either
$(0,a)=(a,\infty)\circ(0,\infty)\circ(a,\infty)$ or
$(0,a)=(0,\infty)\circ(a,\infty)\circ(0,\infty)$. By some computation as
explained above, the first identity leads exactly to the mysterious
observation in Carlitz [3], and the second one gives

$(0,a)=(-a^{2}x+a)\circ x^{q-2}\circ(x+a)\circ x^{q-2}\circ(x-1/a)\circ
x^{q-2}\circ x,$

which is the same as the observation in Zieve [22] as polynomials. To see this
it is enough to normalize all except the first degree-one polynomials to be
monic in the observation discovered by Zieve [22].

Finally, we emphasize that it is of essential importance to introduce the
extra point $\infty$ and to work over $\mathbb{P}^{1}(\mathbb{F}_{q})$ instead
of $\mathbb{F}_{q}$, although both Carlitz’s original Theorem 10 and the
notion of Carlitz rank are only about permutations of $\mathbb{F}_{q}$ and
appear to have nothing to do with $\infty$. It is clear that neither of the
above two consequences can be possibly obtained by working over
$\mathbb{F}_{q}$ without introducing $\infty$.

## References

  * [1] E. Aksoy, A. Çeşmelioğlu, W. Meidl and A. Topuzoğlu, On the Carlitz rank of permutation polynomials, Finite Fields Appl. 15 (2009), 428–440.
  * [2] E. Betti, Sopra la risolubilità per radicali delle equazioni algebriche irriduttibili di grado primo, Annali di Scienze Matematiche e Fisiche 2 (1851), 5–19 (=Opere Matematiche, v. 1, 17–27).
  * [3] L. Carlitz, Permutations in a finite field, Proc. Amer. Math. Soc. 4 (1953), 538\.
  * [4] by same author, Permutations in finite fields, Acta Sci. Math. (Szeged) 24 (1963), 196–203.
  * [5] by same author, A note on permutations in an arbitray field, Proc. Amer. Math. Soc. 14 (1963), 101\.
  * [6] A. Çeşmelioğlu, A representation of permutations with full cycle, arXiv:1005.2019v1.
  * [7] A. Çeşmelioğlu, W. Meidl and A. Topuzoğlu, On the cycle structure of permutation polynomials, Finite Fields Appl. 14 (2008), 593–614.
  * [8] by same author, Enumeration of a class of sequences generated by inversions, in: Coding and Cryptology, World Sci. Publ., Hackensack, NJ (2008), 44–57.
  * [9] by same author, Permutations of finite fields with prescribed properties, J. Comput. Appl. Math. 259 (2014), part B, 536–545.
  * [10] L. E. Dickson, The analytic representation of substitutions on a power of a prime number of letters, with a discussion of the linear group, Annals Math. 11 (1896–1897), 65–120 and 161–183.
  * [11] Z. Ding and M. E. Zieve, Carlitz ranks and approximate rational functions, to submit.
  * [12] K. D. Fryer, A class of permutation groups of prime degree, Canad. J. Math. 7 (1955), 24–34.
  * [13] by same author, Note on permutations in a finite field, Proc. Amer. Math. Soc. 6 (1955), 1–2.
  * [14] D. Gomez-Perez, A. Ostafe and A. Topuzoğlu, On the Carlitz rank of permutations of $\mathbb{F}_{q}$ and pseudorandom sequences, J. Complexity 30 (2014), 279–289.
  * [15] L. Işik, On complete mappings and value sets of polynomials over finite fields, Ph. D. thesis, Sabanci University, 2015.
  * [16] L. Işik and A. Topuzoğlu, A note on value sets of polynomials over finite fields, arXiv:1701.06158v1.
  * [17] L. Işik, A. Topuzoğlu and A. Winterhof, Complete mappings and Carlitz rank, Des. Codes Cryptogr. 85 (2017), 121–128.
  * [18] R. Lidl and H. Niederreiter, Finite Fields, second ed., Encyclopedia Math. Appl. 20, Cambridge Univ. Press, New York, 1997.
  * [19] W. Meidl and A. Topuzoğlu, On the inversive pseudorandom number generator, in: Recent developments in applied probability and statistics, Physica, Heidelberg (2010), 103–125.
  * [20] A. Topuzoğlu, The Carlitz rank of permutations of finite fields: A survey, J. Symbolic Comput. 64 (2014), 53–66.
  * [21] C. Wells, Generators for groups of permutation polynomials over finite fields, Acta Sci. Math. Szeged. 29 (1968), 167–176.
  * [22] M. E. Zieve, On a theorem of Carlitz, J. Group Theory 17 (2014), 667–669.