# DeepSim: Semantic similarity metrics for learned image registration

Steffen Czolbe Oswin Krause
Department of Computer Science
University of Copenhagen
{per.sc<EMAIL_ADDRESS>
&&Aasa Feragen
DTU Compute
Technical University of Denmark
<EMAIL_ADDRESS>

###### Abstract

We propose a semantic similarity metric for image registration. Existing
metrics like euclidean distance or normalized cross-correlation focus on
aligning intensity values, giving difficulties with low intensity contrast or
noise. Our semantic approach learns dataset-specific features that drive the
optimization of a learning-based registration model. Comparing to existing
unsupervised and supervised methods across multiple image modalities and
applications, we achieve consistently high registration accuracy and faster
convergence than state of the art, and the learned invariance to noise gives
smoother transformations on low-quality images.

##  1 Introduction

Deformable registration is a fundamental preprocessing tool in medical
imaging, where the goal is to find anatomical correspondences between images
and derive geometric transformations $\Phi$ to align them. Most algorithmic
and deep learning-based methods optimize alignment via a similarity measure
$D$ and a $\lambda$-weighted regularizer $R$, combined in a loss function

$L(\mathbf{I},\mathbf{J},\Phi)=D(\mathbf{I}\circ\Phi,\mathbf{J})+\lambda
R(\Phi)\enspace.$ (1)

The similarity metric $D$ assesses the alignment and strongly influences the
result. Pixel-based similarity metrics like euclidean distance
($\operatorname{MSE}$) and patch-wise normalized cross-correlation
($\operatorname{NCC}$) are commonly used in both algorithmic [4, 3, 10, 22,
23, 25] and deep learning based [1, 5, 7, 8, 26, 18, 17, 13, 14, 28, 27] image
registration. Typically, the similarity measure for a task is selected as the
best out of a small set of metrics, with no guarantee that one of the metrics
is suitable for the data.

The shortcomings of pixel-based similarity metrics have been studied
substantially in the image generation community [29], where the introduction
of deep similarity metrics approximating human visual perception has improved
the generation of photo-realistic images [6, 12]. As registration models are
generative models [7], we expect these similarity metrics to improve
registration as well. Current attempts at using learned similarity metrics for
image registration require ground truth transformations [11] or limit the
input to the registration model [17].

We propose a data-driven similarity metric for image registration based on the
alignment of semantic features. We learn semantic filters of our metric on the
dataset, use it to train a registration model, and validate our approach on
three biomedical datasets of different image modalities and applications.
Across all datasets, our method achieves consistently high registration
accuracy, outperforming even metrics utilizing supervised information. Our
models converge faster and learn to ignore noisy image patches, leading to
smoother transformations on low-quality data.

DeepSim
---
Warp
---
Feature Extractor
---
Registration Network
---
$\mathbf{I}$
---
$\mathbf{S}$
---
$\mathbf{I}$
---
$\mathbf{J}$
---
$\mathbf{J}$
---
$\mathbf{I}\circ\Phi$
---
$F^{l}(\mathbf{J})$
---
$F^{l}(\mathbf{I}\circ\Phi)$
---
$\Phi$
---
Figure 1: Two-step training: First, the Feature Extractor (yellow) is trained
on a segmentation task. Next, its weights are frozen and used in the loss
computation of the registration network (blue).

##  2 A deep similarity metric for image registration

To align areas of similar semantic value, we propose a similarity metric based
on the agreement of semantic feature representations of two images. Semantic
feature maps are obtained by a feature extractor to be tuned on a surrogate
segmentation task. To capture alignment of both localized, concrete features,
and global, abstract ones, we calculate the similarity at multiple layers of
abstraction.

Concretely, given a set of feature-extracting functions
$F^{l}\colon\mathbb{R}^{\Omega\times C}\to\mathbb{R}^{\Omega_{l}\times C_{l}}$
for $L$ layers, we define

$\displaystyle\operatorname{DeepSim}(\mathbf{I}\circ\Phi,\mathbf{J})=\frac{1}{L}\sum_{l=1}^{L}\frac{1}{|\Omega_{l}|}\sum_{{\mathbf{p}}\in\Omega_{l}}\frac{\big{<}F^{l}_{\mathbf{p}}(\mathbf{I}\circ\Phi),F^{l}_{\mathbf{p}}(\mathbf{J})\big{>}}{\|F^{l}_{\mathbf{p}}(\mathbf{I}\circ\Phi)\|\|F^{l}_{\mathbf{p}}(\mathbf{J})\|}\enspace,$
(2)

where $F^{l}_{\mathbf{p}}(\mathbf{J})$ denotes the $l^{th}$ layer feature
extractor applied to image $\mathbf{J}$, at spatial coordinate $\mathbf{p}$.
It is a vector of $C_{l}$ output channels, and the spatial size of the
$l^{th}$ feature map is denoted by $|\Omega_{l}|$. The metric is influenced by
the neighbourhood of a pixel, as $F^{l}$ composes convolutional filters with
increasing receptive area of the composition. Note that the formulation via
cosine similarity is similar to the classic $\operatorname{NCC}$ metric, which
can be interpreted as the squared cosine-similarity between two zero-mean
vectors of patch descriptions.

### Feature extraction

To aid registration, the functions $F^{l}(\cdot)$ should extract features of
semantic relevance for the registration task, while ignoring noise and
artifacts. We achieve this by training the feature extractor on a
supplementary segmentation task, as segmentation models excel at learning
relevant kernels for the data while attaining invariance towards non-
predictive features like noise. The obtained convolutional filters act as
feature extractors for $\operatorname{DeepSim}$, see also Figure 1.

##  3 Experiments

Figure 2: Quantitative comparison of similarity metrics. Stars indicate p-test
significance level. Effect size given by Cohen’s d.

We compare registration models trained with $\operatorname{DeepSim}$ to the
baselines $\operatorname{MSE}$, $\operatorname{NCC}$,
$\operatorname{NCC}_{\text{sup}}$ ($\operatorname{NCC}$ with supervised
information [5]), and $\operatorname{VGG}$ (a VGG-net based metric common in
image generation and similar to our method [12]). Figure 1 shows our model
architecture. For both registration and segmentation we use U-nets [21]. The
registration network predicts the transformation $\Phi$ based on two images
$\mathbf{I},\mathbf{J}$. A spatial transformer module [15] applies $\Phi$ to
obtain the morphed image $\mathbf{I}\circ\Phi$. The loss is given by Eq. 1; we
choose the diffusion regularizer for $R$ and tune hyperparamter $\lambda$ on
the validation sets.

To show that our approach is applicable to a large variety of registration
tasks, we validate it on three 2D and 3D datasets of different image
modalities: T1-weighted Brain-MRI scans [9, 16], human blood cells of the
Platelet-EM dataset [20], and cell-tracking of the PhC-U373 dataset [19, 24].
Each dataset is split into a train, validation, and test section.

N/A for 3D Data (a)

(b)

Figure 3: (a) Qualitative comparison, (b) Detail view of highlighted areas.
Select segmentation classes annotated color. The transformation is visualized
by morphed grid-lines.

### Registration accuracy & convergence

We measure the mean Sørensen Dice coefficient on the unseen test-set in Figure
2, and test for statistical significance of the result with the Wilcoxon
signed rank test for paired samples. Our null hypothesis for each similarity
metric is that the model trained with $\operatorname{DeepSim}$ performs
better. We test for a statistical significance levels of
${p^{*}=0.05,p^{**}=0.01,p^{***}=0.001}$. We further measure the effect size
with Cohen’s d, and label the metrics accordingly in Figure 2. Models trained
with our proposed $\operatorname{DeepSim}$ rank as the best on the Brain-MRI
and Platelet-EM datasets, with strong statistical significance. On the
PhC-U373 dataset, all models achieve high dice-overlaps of $>0.97$.
$\operatorname{DeepSim}$ converges faster than the baselines, especially in
the first epochs of training.

### Qualitative examples & transformation grids

We plot the fixed and moving images $\mathbf{I},\mathbf{J}$ and the morphed
image $\mathbf{I}\circ\Phi$ for each similarity metric model in Figure 3(a),
and a more detailed view of a noisy patch of the Platelet-EM dataset in Figure
3(b). The transformation is visualized by grid-lines, which have been
transformed from a uniformly spaced grid. On models trained with the
baselines, we find strongly distorted transformation fields in noisy areas of
the images. In particular, models trained with $\operatorname{NCC}$ and
$\operatorname{NCC}_{\text{sup}}$ produce very irregular transformations,
despite careful tuning of the regularization-hyper-parameter. The model
trained by $\operatorname{DeepSim}$ is more invariant towards the noise.

##  4 Discussion & Conclusion

Registration models trained with $\operatorname{DeepSim}$ achieve high
registration accuracy across multiple datasets, leading to improved downstream
analysis and diagnosis in medical applications. The consistency of our
proposed metric makes testing multiple traditional metrics unnecessary;
instead of empirically determining whether $\operatorname{MSE}$ or
$\operatorname{NCC}$ captures the characteristics of a data-set best, we can
use $\operatorname{DeepSim}$ to learn the relevant features from the data.

The analysis of noisy patches in Figure 3(b) highlights a learned invariance
to noise. The pixel-based similarity metrics are distracted by artifacts,
leading to overly-detailed transformation fields. $\operatorname{DeepSim}$
does not show this problem. While smoother transformation fields can be
obtained for all metrics by strengthening the regularizer, this would
negatively impact the registration accuracy of anatomically significant
regions. Accurate registration of noisy, low-quality images allows for shorter
acquisition time and reduced radiation dose in medical applications.

$\operatorname{DeepSim}$ is a general metric, applicable to image registration
tasks of all modalities and anatomies. Beyond the presented datasets, the good
results on low-quality data let us hope that $\operatorname{DeepSim}$ will
improve registration accuracy in the domains of lung CT and ultrasound, where
details are hard to identify, and image quality is often poor. We further
emphasize that the application of $\operatorname{DeepSim}$ is not limited to
deep learning. Algorithmic image registration uses a similar optimization
framework, where a similarity-based loss is minimized via gradient descent-
based methods. $\operatorname{DeepSim}$ can be applied to drive algorithmic
methods, improving their performance by aligning deep, semantic feature
embeddings.

## Broader impact

The broader impact of our work is defined by the numerous applications of
medical image registration. Common applications are in neuroscience [5], CT-
imaging of lungs and abdomen [26], as well as for fusion and combination of
multiple modalities [11].

The deep learning approach to image registration utilized in this work can
achieve impressive results across a wide variety of tasks, but this often
comes at the cost of training models on specialized hardware for extensive
periods. This energy-intensive workload may raise carbon emissions, the
primary contributor to climate change [2]. We hope that by presenting a method
for learning a semantic similarity metric from the data, we make excessive
testing of other loss functions unnecessary. This can reduce the amount of
model configurations to be tested in the development of deep learning methods,
contributing to a lower environmental impact of the image registration
community.

## References

  * [1] Jennifer Alvén, Kerstin Heurling, Ruben Smith, Olof Strandberg, Michael Schöll, Oskar Hansson and Fredrik Kahl  “A Deep Learning Approach to MR-less Spatial Normalization for Tau PET Images”  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 2019, pp. 355–363  DOI: 10.1007/978-3-030-32245-8_40
  * [2] Lasse F. Anthony, Benjamin Kanding and Raghavendra Selvan  “Carbontracker: Tracking and Predicting the Carbon Footprint of Training Deep Learning Models”  In _ICML Workshop on Challenges in Deploying and monitoring Machine Learning Systems_ , 2020  arXiv: http://arxiv.org/abs/2007.03051
  * [3] B.. Avants, C.. Epstein, M. Grossman and J.. Gee  “Symmetric diffeomorphic image registration with cross-correlation: Evaluating automated labeling of elderly and neurodegenerative brain”  In _Medical Image Analysis_ 12.1, 2008, pp. 26–41  DOI: 10.1016/j.media.2007.06.004
  * [4] Brian B. Avants, Nicholas J. Tustison, Gang Song, Philip A. Cook, Arno Klein and James C. Gee  “A reproducible evaluation of ANTs similarity metric performance in brain image registration”  In _NeuroImage_ 54.3 Academic Press, 2011, pp. 2033–2044  DOI: 10.1016/j.neuroimage.2010.09.025
  * [5] Guha Balakrishnan, Amy Zhao, Mert R. Sabuncu, John Guttag and Adrian V. Dalca  “VoxelMorph: A Learning Framework for Deformable Medical Image Registration”  In _IEEE Transactions on Medical Imaging_ 38.8 Institute of ElectricalElectronics Engineers (IEEE), 2019, pp. 1788–1800  DOI: 10.1109/tmi.2019.2897538
  * [6] Steffen Czolbe, Oswin Krause, Ingemar Cox and Christian Igel  “A Loss Function for Generative Neural Networks Based on Watson’s Perceptual Model”  In _Advances in Neural Information Processing Systems_ , 2020  arXiv: http://arxiv.org/abs/2006.15057
  * [7] Adrian V. Dalca, Guha Balakrishnan, John Guttag and Mert R. Sabuncu  “Unsupervised Learning for Fast Probabilistic Diffeomorphic Registration”  In _Medical Image Computing and Computer Assisted Intervention_ , 2018, pp. 729–738  DOI: 10.1007/978-3-030-00928-1_82
  * [8] Adrian V. Dalca, Marianne Rakic, John Guttag and Mert R. Sabuncu  “Learning Conditional Deformable Templates with Convolutional Networks”  In _Advances in neural information processing systems_ , 2019, pp. 806–818  arXiv: http://arxiv.org/abs/1908.02738
  * [9] Adriana Di Martino, Chao-Gan Yan and Qingyang Li  “The autism brain imaging data exchange: towards a large-scale evaluation of the intrinsic brain architecture in autism”  In _Molecular psychiatry_ 19.6 Nature Publishing Group, 2014, pp. 659–667
  * [10] Mirza Faisal Beg, Michael I Miller, Alain Trouvétrouv and Laurent Younes  “Computing Large Deformation Metric Mappings via Geodesic Flows of Diffeomorphisms”  In _International Journal of Computer Vision_ 61.2, 2005, pp. 139–157
  * [11] Grant Haskins, Jochen Kruecker, Uwe Kruger, Sheng Xu, Peter A. Pinto, Brad J. Wood and Pingkun Yan  “Learning deep similarity metric for 3D MR–TRUS image registration”  In _International Journal of Computer Assisted Radiology and Surgery_ 14.3 Springer Verlag, 2019, pp. 417–425  DOI: 10.1007/s11548-018-1875-7
  * [12] Xianxu Hou, Linlin Shen, Ke Sun and Guoping Qiu  “Deep feature consistent variational autoencoder”  In _Winter Conference on Applications of Computer Vision_ , 2017, pp. 1133–1141  IEEE
  * [13] Xiaojun Hu, Miao Kang, Weilin Huang, Matthew R. Scott, Roland Wiest and Mauricio Reyes  “Dual-Stream Pyramid Registration Network”  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 2019, pp. 382–390  DOI: 10.1007/978-3-030-32245-8_43
  * [14] Yipeng Hu, Eli Gibson, Dean C. Barratt, Mark Emberton, J. Noble and Tom Vercauteren  “Conditional Segmentation in Lieu of Image Registration”  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 2019, pp. 401–409  DOI: 10.1007/978-3-030-32245-8_45
  * [15] Max Jaderberg, Karen Simonyan, Andrew Zisserman and Koray Kavukcuoglu  “Spatial Transformer Networks”  In _Advances in neural information processing systems_ , 2015
  * [16] Pamela J LaMontagne, Tammie L S Benzinger and John C Morris  “OASIS-3: Longitudinal Neuroimaging, Clinical, and Cognitive Dataset for Normal Aging and Alzheimer Disease”  In _medRxiv_ Cold Spring Harbor Laboratory Press, 2019
  * [17] Matthew C.. Lee, Ozan Oktay, Andreas Schuh, Michiel Schaap and Ben Glocker  “Image-and-Spatial Transformer Networks for Structure-Guided Image Registration”  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 2019, pp. 337–345  DOI: 10.1007/978-3-030-32245-8_38
  * [18] Lihao Liu, Xiaowei Hu, Lei Zhu and Pheng-Ann Heng  “Probabilistic Multilayer Regularization Network for Unsupervised 3D Brain Image Registration”  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 2019, pp. 346–354  DOI: 10.1007/978-3-030-32245-8_39
  * [19] Martin Maška et al.  “A benchmark for comparison of cell tracking algorithms”  In _Bioinformatics_ 30.11, 2014, pp. 1609–1617  DOI: 10.1093/bioinformatics/btu080
  * [20] Matthew Quay, Zeyad Emam, Adam Anderson and Richard Leapman  “Designing deep neural networks to automate segmentation for serial block-face electron microscopy”  In _International Symposium on Biomedical Imaging_ 2018-April IEEE Computer Society, 2018, pp. 405–408  DOI: 10.1109/ISBI.2018.8363603
  * [21] Olaf Ronneberger, Philipp Fischer and Thomas Brox  “U-net: Convolutional networks for biomedical image segmentation”  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ 9351 Springer Verlag, 2015, pp. 234–241  DOI: 10.1007/978-3-319-24574-4_28
  * [22] Daniel Rueckert, Luke I Sonoda, Carmel Hayes, Derek LG Hill, Martin O Leach and David J Hawkes  “Nonrigid registration using free-form deformations: Application to breast mr images”  In _IEEE Transactions on Medical Imaging_ 18.8 Institute of ElectricalElectronics Engineers Inc., 1999, pp. 712–721  DOI: 10.1109/42.796284
  * [23] Jean-Philippe Thirion  “Image matching as a diffusion process: an analogy with Maxwell’s demons”  In _Medical Image Analysis_ 2.3 Elsevier, 1998, pp. 243–260  URL: https://hal.inria.fr/inria-00615088
  * [24] Vladimír Ulman et al.  “An objective comparison of cell-tracking algorithms”  In _Nature Methods_ 14.12 Nature Publishing Group, 2017, pp. 1141–1152  DOI: 10.1038/nmeth.4473
  * [25] Tom Vercauteren, Xavier Pennec, Aymeric Perchant and Nicholas Ayache  “Non-parametric diffeomorphic image registration with the demons algorithm”  In _Lecture Notes in Computer Science_ 4792 LNCS.PART 2, 2007, pp. 319–326  DOI: 10.1007/978-3-540-75759-7_39
  * [26] Bob D. Vos, Floris F. Berendsen, Max A. Viergever, Hessam Sokooti, Marius Staring and Ivana Išgum  “A deep learning framework for unsupervised affine and deformable image registration”  In _Medical Image Analysis_ 52 Elsevier B.V., 2019, pp. 128–143  DOI: 10.1016/j.media.2018.11.010
  * [27] Zhenlin Xu and Marc Niethammer  “DeepAtlas: Joint Semi-supervised Learning of Image Registration and Segmentation”  In _International Conference on Medical Image Computing and Computer-Assisted Intervention_ , 2019, pp. 420–429  DOI: 10.1007/978-3-030-32245-8_47
  * [28] Xiao Yang, Roland Kwitt, Martin Styner and Marc Niethammer  “Quicksilver: Fast predictive image registration - A deep learning approach”  In _NeuroImage_ 158 Academic Press Inc., 2017, pp. 378–396  DOI: 10.1016/j.neuroimage.2017.07.008
  * [29] Richard Zhang, Phillip Isola, Alexei A. Efros, Eli Shechtman and Oliver Wang  “The Unreasonable Effectiveness of Deep Features as a Perceptual Metric”  In _Conference on Computer Vision and Pattern Recognition_ IEEE Computer Society, 2018, pp. 586–595  arXiv: http://arxiv.org/abs/1801.03924


Periodic Orbits on Obtuse Edge Tessellating Polygons Benjamin R. Baer, Faheem
Gilani, Zhigang Han, and Ronald Umble Theoremequation Theorem
Propositionequation Proposition Corollaryequation Corollary Lemmaequation
Lemma

##  1 Introduction

Elementary mathematical billiards studies the motion of a massless particle
moving with unit speed along a piece-wise linear path in the interior of a
polygon $G$ subject to elastic reflections at the boundary $\partial G$, i.e.,
the angle of incidence equals the angle of reflection. We think of $G$ as a
frictionless billiard table, the edges of $G$ as its bumpers, the vertices of
$G$ as its pockets, and the particle in motion as the cue ball.

The particle’s path is its _orbit_. If the orbit reaches a vertex of $G$, it
terminates and is _singular_. A non-singular orbit that begins and ends at the
same point is _periodic_ if the particle retraces its orbit when allowed to
continue. A periodic orbit is _primitive_ if the particle traverses its orbit
exactly once. The _period_ of a periodic orbit is the number of times the
particle strikes $\partial G$ as it traverses a primitive sub-orbit.

In 2006, A. Baxter and R. Umble found and classified the periodic orbits on
equilateral triangles [3]. Five year later, A. Baxter, E. McCarthy, and J.
Eskreis-Winkler solved the analogous problem on rectangles, isosceles right
triangles, and $30^{\circ}$-right triangles [2]. In this paper we solve the
problem on $120^{\circ}$-isosceles triangles, $60^{\circ}$-rhombuses, and
$60^{\circ}$-$90^{\circ}$-$120^{\circ}$-kites, and we make a conjecture in the
case of regular hexagons.

An _edge tessellation_ of the plane is generated by reflecting a polygon $G$
and its reflected images in their edges. Each such $G$ lies in exactly one of
the eight aforementioned families [4]. The _edges_ of an edge tessellation are
the edges of its polygons and the lines containing them are its _inclines_.
For example, an equilateral triangle in standard position generates an edge
tessellation with inclines of $0^{\circ}$, $60^{\circ}$, and $120^{\circ}$.

We identify a non-singular orbit in an edge tessellating polygon $G$ with a
piece-wise linear curve $\gamma:I\rightarrow G$ defined on a finite interval
$I$. An _unfolding_ of $\gamma$ in the edge tessellation $\mathcal{T}$
generated by $G$ is a line segment produced by successively reflecting
$\gamma$ and its reflected images in the inclines of $\mathcal{T}$. Unfoldings
relate the periodicity of $\gamma$ to the geometry of $\mathcal{T}$ and are
sufficient for classifying periodic orbits in the non-obtuse cases. However,
the analysis requires us to use more sophisticated techniques involving what
we call the “fence.”

##  2 Periodic orbits on a $120^{\circ}$-isosceles triangle

###  2.1 Preliminaries

Consider a $120^{\circ}$-isosceles $\triangle ABC$ positioned and labeled so
that $\overline{AC}$ is horizontal with $A$ to the left of $C,$ the apex $B$
is positioned above $\overline{AC}$, and $\angle B$ is obtuse. The edge
tessellation $\mathcal{T}$ generated by $\triangle ABC$ has inclines of
$0^{\circ}$, $30^{\circ},$ $60^{\circ},$ $90^{\circ},$ $120^{\circ},$ and
$150^{\circ}$. Given triangles $\triangle_{1}$ and $\triangle_{2}$ in
$\mathcal{T}$ such that $\triangle_{2}=\tau(\triangle_{1})$ for some
translation $\tau$, two points $P_{1}$ on $\triangle_{1}$ and $P_{2}$ on
$\triangle_{2}$ are _(translationally) aligned (with respect to
$\triangle_{1}$ and $\triangle_{2}$)_ if $P_{2}=\tau(P_{1})$.

Let $\gamma:(0,T]\rightarrow\triangle ABC$ be an orbit in $\triangle ABC$. Let
$\upsilon:(0,T]\rightarrow\mathcal{T}$ be an unfolding of $\gamma$ with
_initial point_ $P=\lim_{t\searrow 0}\upsilon(t)$ and _terminal point_
$Q=\upsilon(T)=\sigma(\gamma(T))$, where $\sigma$ is the composition of
reflections associated with $\upsilon$. The _initial triangle_ $\triangle ABC$
and the _terminal triangle_ $\triangle
A^{\prime}B^{\prime}C^{\prime}:=\sigma\left(\triangle ABC\right)$ are
_consistently oriented_ if $\sigma$ is orientation preserving.

Unlike orientation, which is determined by comparing the labelings $(A,B,C)$
and $(A^{\prime},B^{\prime},C^{\prime})=(\sigma(A),\sigma(B),\sigma(C))$ [6],
alignment is determined by the relative positions of $P$ and $Q$ on $\triangle
ABC$ and $\triangle A^{\prime}B^{\prime}C^{\prime}$, and is independent of
labeling. The periodicity of $\gamma$ is characterized by

######  Theorem .

Let $\gamma$ be an orbit with unfolding $\upsilon$ whose initial point is on
$\overline{AC}$. Then $\gamma$ is periodic if and only if the initial and
terminal triangles are consistently oriented and the initial and terminal
points are aligned.

###### Proof.

When $\triangle A^{\prime}B^{\prime}C^{\prime}$ and $\triangle ABC$ are
consistently oriented, $\sigma$ is a rotation or a translation. Since $P$ and
$Q$ are aligned, $\sigma$ is a translation and $\sigma(P)=Q$. Hence $P$ and
$Q$ are in the same relative position in their respective triangles and the
initial and terminal angles are equal. Therefore $\gamma$ is periodic.

Conversely, given a periodic orbit $\gamma$, let $\upsilon$ be the unfolding
with initial point $P$ on $\overline{AC}$, initial angle $\Theta:=m\angle
QPC$, and generated by first reflecting in a non-horizontal incline. If
$\Theta\neq 90^{\circ}$, the reflection of $\overline{PQ}$ in the vertical
line through $P$ is another unfolding, and we may restrict our considerations
to initial angles in the range $0<\Theta\leq 90^{\circ}$.

The images of $\overleftrightarrow{AC}$ in $\mathcal{T}$ are the horizontal,
$60^{\circ}$, and $120^{\circ}$ inclines. We claim that $Q$ is on a horizontal
incline. Suppose $Q$ is on a $60^{\circ}$ incline. Then the terminal angle at
$Q$, which equals the initial angle $\Theta$ at $P$, is $60^{\circ}-\Theta$,
$\Theta+120^{\circ}$, $\Theta-60^{\circ}$, or $240^{\circ}-\Theta$. But
$0<\Theta\leq 90^{\circ}$ implies $\Theta=30^{\circ}$ (see Figure 2), and an
initial angle of $\Theta=30^{\circ}$ produces a period $8$ orbit that
terminates on a horizontal incline, which is a contradiction (see Figure 2).
Suppose $Q$ is on a $120^{\circ}$ incline. Then the terminal angle at $Q$ is
$120^{\circ}-\Theta$, $\Theta+60^{\circ}$, $\Theta-120^{\circ}$, or
$300^{\circ}-\Theta$. But $0<\Theta\leq 90^{\circ}$ implies
$\Theta=60^{\circ}$, and an initial angle of $\Theta=60^{\circ}$ produces an
orbit of period $4$ or period $10$, both of which terminate on a horizontal
incline, which is a contradiction (see Figure 3). Therefore $Q$ is on a
horizontal incline as claimed.

Unfolding${\scriptstyle 60^{\circ}}$${\scriptstyle\theta}$${\scriptstyle
60^{\circ}-\theta}$$\mathit{P}$$\mathit{Q}$Incline$\overleftrightarrow{\mathit{AC}}$

Figure 1: Equal initial and terminal angles of an unfolding.

$P$$A$$C$$B$$Q$$A^{\prime}$$C^{\prime}$$B^{\prime}$

Figure 2: An unfolding with initial angle $30^{\circ}$.

$P$$A$$C$$B$$Q$$A^{\prime}$$C^{\prime}$$B^{\prime}$

(a) An unfolding with initial angle $60^{\circ}$ and period 10.

$P$$A$$C$$B$$Q$$A^{\prime}$$C^{\prime}$$B^{\prime}$

(b) An unfolding with initial angle $60^{\circ}$ and period 4.

Figure 3:

Since $Q$ is on a horizontal incline, the base
$\overline{A^{\prime}C^{\prime}}$ is horizontal. Furthermore, since
$\overline{PQ}$ does not cross the interior of $\triangle
A^{\prime}B^{\prime}C^{\prime}$, its apex $B^{\prime}$ lies above the base.
Thus $\sigma$ is a translation or a glide reflection. If $\sigma$ is a glide
reflection, it reverses orientation. Then $180^{\circ}-\Theta=\Theta$ implies
$\Theta=90^{\circ}$. But a periodic orbit with initial angle $90^{\circ}$
coincides with the period $8$ orbit with initial angle $30^{\circ}$. Since
$\sigma$ is a composition of eight reflections, it preserves orientation,
which is a contradiction. Therefore $\sigma$ is a translation, $P$ and $Q$ are
aligned, and $\triangle A^{\prime}B^{\prime}C^{\prime}$ and $\triangle ABC$
are consistently oriented. ∎

######  Corollary .

The period of a periodic orbit is even, and an unfolding of a periodic orbit
with initial point on a horizontal terminates on a horizontal.

Corollary 2.1 does not hold for all edge tessellating polygons. For example,
Fagnano’s periodic orbit on an equilateral triangle has period $3$ and
terminates on a non-horizontal incline [3].

Note that the periodic orbit displayed in Figure 2 has initial angle
$30^{\circ}$ and period $8$, while the periodic orbits displayed in Figure 3
have initial angle $60^{\circ}$ and respective periods $4$ and $10$. A
periodic orbit $\gamma$ is _monoperiodic_ if every periodic orbit with the
same initial angle as $\gamma$ has the same period; otherwise, $\gamma$ is
_biperiodic_.

Our next proposition allows us to restrict our considerations to periodic
orbits with initial angles between 60 and 90 degrees.

######  Proposition .

Every periodic orbit can be represented by an unfolding with an initial angle
$\Theta$ in the range $60^{\circ}\leq\Theta\leq 90^{\circ}$.

###### Proof.

Let $\gamma$ be a periodic orbit with initial angle $\Theta$ in the range
$0^{\circ}<\Theta\leq 90^{\circ}$. Suppose $0^{\circ}<\Theta\leq 30^{\circ}$.
Since $Q$ is on a horizontal incline, $\overline{PQ}$ cuts a $120^{\circ}$
incline at a point $P^{\prime}$ with angle of incidence
$\Phi=60^{\circ}+\Theta.$ Thus, there is an unfolding
$\overline{P^{\prime}Q^{\prime}}$ of $\gamma$ with initial angle $\Phi$ in the
range $60^{\circ}<\Phi\leq 90^{\circ}$. On the other hand, suppose
$30^{\circ}<\Theta<60^{\circ}$, and let $\overline{PQ^{\prime}}$ be the
reflection of $\overline{PQ}$ in $\overleftrightarrow{AC}.$ Then
$\overline{PQ^{\prime}}$ cuts a $60^{\circ}$ incline at a point $P^{\prime}$
with angle of incidence $\Psi=120^{\circ}-\Theta$. Thus, there is an unfolding
$\overline{P^{\prime}R}$ with initial angle $\Psi$ in the range
$60^{\circ}<\Psi<90^{\circ}$. ∎

Since periodic orbits with initial angles $60^{\circ}$ and $90^{\circ}$ are
understood, our problem reduces to classifying periodic orbits with initial
angles in $(60^{\circ},90^{\circ})$.

###  2.2 Contact points of an unfolding and the fence

Let $AC$ denote the length of $\overline{AC}$ and let $u=\frac{1}{2}AC$.
Impose a rectangular coordinate system on $\mathcal{T}$ with horizontal axis
$\overleftrightarrow{AC}$, origin $O$ at the midpoint of $\overline{AC}$,
horizontal unit of length $u$, and vertical unit of length $\sqrt{3}u$. Then
points on vertical inclines have integer horizontal coordinates, points on
horizontal inclines have integer vertical coordinates, and adjacent vertical
and adjacent horizontal inclines lie one unit apart. If $\upsilon$ is an
unfolding of a periodic orbit with initial point $P$, terminal point $Q$, and
initial angle $\Theta$, Theorem 2.1 implies that the vector $\mathbf{PQ}$ is
parallel to a vector $\left(x,y\right)$ for some $x,y\in\mathbb{N}$; hence
$\Theta=\arctan\left(\frac{y}{x}\sqrt{3}\right)$. Furthermore,
$\Theta\in\left(60^{\circ},90^{\circ}\right)$ implies $x<y$, and we may assume
$\gcd\left(x,y\right)=1$.

Parametrize $\upsilon$ via
$\upsilon\left(t\right):=\left(t+a,\frac{y}{x}t\right),$ $0<t\leq T$, where
$a\in(-1,1)$; then $P=\lim_{t\searrow 0}\upsilon(t)=(a,0)$ and
$Q=\upsilon(T)$. Each point at which $\upsilon$ cuts a vertical incline lies
on a fundamental vertical segment of length 2 connecting the midpoints of two
horizontal edges. The function
$f:\mathbb{Z}\times\mathbb{R}\rightarrow\mathbb{R}/2\mathbb{Z}$ defined by
$f\left(\alpha,\beta\right):=\alpha+\beta+2\mathbb{Z}$ identifies each such
segment with the quotient group $\mathbb{R}/2\mathbb{Z}$, called the _fence_.
Geometrically, the projection in the $60^{\circ}$ direction onto the vertical
coordinate axis sends $(\alpha,\beta)$ into the coset $f(\alpha,\beta)$. It
will often be convenient to think of the fence as the interval
$\mathcal{F}:=\left[0,2\right)$ of coset representatives and to write
$f\left(\alpha,\beta\right)=\left(\alpha+\beta\right)\operatorname{mod}2$. The
fence $\mathcal{F}$ consists of the _barrier_
$\mathcal{B}:=\left(\frac{1}{3},\frac{5}{3}\right]$ and the _gate_
$\mathcal{B}^{c}:=\mathcal{F\smallsetminus B}$.

Between consecutive horizontal inclines, an unfolding $\upsilon$ always cuts
four non-vertical edges. But whether or not $\upsilon$ also cuts a vertical
edge is determined by its set of _contact points_

$\mathcal{C}_{T}:=\left\\{f\left(\upsilon(t)\right):0<t\leq
T\,\,\mbox{and}\,\,t+a\in\mathbb{Z}\right\\}\subset\mathcal{F}.$

Indeed, $\upsilon$ cuts a vertical edge at $\upsilon(t_{i})$ if and only if
$f(\upsilon(t_{i}))\in\mathcal{B}$. The _multiplicity_ of a contact point
$c\in\mathcal{C}_{T}$, denoted by $m_{T}\left(c\right)$, is the number of
times $\upsilon$ cuts a vertical incline at a point corresponding to $c$,
i.e.,

$m_{T}\left(c\right):=\\#\left\\{t:0<t\leq
T\,\,\mbox{and}\,\,f\left(\upsilon\left(t\right)\right)=c\right\\}.$

These ideas are illustrated in Figure 4.

$A$$C$$B$$C^{\prime}$$A^{\prime}$$B^{\prime}$$P$$Q$$\mathcal{O}$

(a) Geometric motivation for the fence.

$c_{0}$$c_{1}$$c_{2}$

(b) The fence for the unfolding in (a); contact points along the unfolding are
indexed sequentially.

Figure 4:

Define $t_{i}:=i-a$, where $i\in\mathbb{Z}$; then
$c_{i}:=f(\upsilon\left(t_{i}\right))=f(i,\frac{y}{x}(i-a))$. Extending the
domain of $\upsilon$ to all real numbers allows us to define $c_{i}$ for all
integers $i$, in which case the equality still holds. The following lemma
characterizes the purely geometric notion of alignment in terms of analytic
conditions on the set of contact points.

######  Lemma .

The initial and terminal points of an unfolding
$\upsilon\left(t\right),\,0<t\leq T$, are aligned if and only if
$c_{i}=c_{i+T}$ for all $i\in\mathbb{Z}$.

###### Proof.

By inspection, the initial point $\left(a,0\right)$ and the terminal point
$\left(T+a,\frac{y}{x}T\right)$ are aligned in the tessellation $\mathcal{T}$
if and only if the horizontal change $T$ and the vertical change
$\frac{y}{x}T$ are both integers, and $2\mid\left(T+\frac{y}{x}T\right)$. By
definition, $c_{i}=c_{i+T}$ if and only if $T\in\mathbb{Z}$ and
$i+\frac{y}{x}(i-a)+2\mathbb{Z}=i+T+\frac{y}{x}(i+T-a)+2\mathbb{Z}$, where the
latter condition is equivalent to $2\mid\left(T+\frac{y}{x}T\right)$. The fact
that $T\in\mathbb{Z}$ and $2\mid\left(T+\frac{y}{x}T\right)$ implies
$\frac{y}{x}T\in\mathbb{Z}$ completes the proof. ∎

Computing the period of a periodic orbit will be significantly simplified by

######  Proposition .

If the initial and terminal points of an unfolding are aligned, all contact
points are equally spaced on the fence and have the same multiplicity.

###### Proof.

If the initial and terminal points of $\upsilon\left(t\right),\,0<t\leq T$,
are aligned, then $c_{i}=c_{i+T}$ for all $i\in\mathbb{Z}$ by Lemma 2.2. Hence
$\mathcal{G}:=\\{(1+\frac{y}{x})i+2\mathbb{Z}:i\in\mathbb{Z}\\}$ is a finite
subgroup of $\mathbb{R}/2\mathbb{Z}$, and the set of contact points
$\\{c_{i}\\}=(-\frac{y}{x}a+2\mathbb{Z})+\mathcal{G}$ is a coset of
$\mathcal{G}$ in $\mathbb{R}/2\mathbb{Z}$. Therefore contact points are
equally spaced in $\mathbb{R}/2\mathbb{Z}$. Furthermore, if $|\mathcal{G}|=m$,
then $m\mid T$ and $m_{T}\left(c_{i}\right)=\frac{T}{m}$ for all $i$. ∎

###  2.3 Counting the number of edges cut by an unfolding

Since the initial and terminal points of $\upsilon\left(t\right),\,0<t\leq T$,
are aligned if and only if both $T$ and $\frac{y}{x}T$ are integers and
$2\mid\left(T+\frac{y}{x}T\right)$, it follows that $x\mid T$ since
$\mathrm{gcd}(x,y)=1$. The _first alignment of_ $\upsilon$, denoted by
$T_{1}$, is the smallest value of $T$ for which the three conditions above
hold. With the parities of $x$ and $y$ in mind, it is easy to check that these
three conditions imply

######  Proposition .

The first alignment of an unfolding $\upsilon$ is given by

$\displaystyle T_{1}=\begin{cases}x&\textnormal{if }x\equiv
y\operatorname{mod}2\\\ 2x&\textnormal{if }x\not\equiv
y\operatorname{mod}2.\end{cases}$

Let $N_{T}$ be the number of edges of $\mathcal{T}$ cut by
$\upsilon(t),\,0<t\leq T$. Proposition 2.3 implies that the initial and
terminal points of $\upsilon\left(t\right),$ $0<t\leq 2x$, are always aligned.
Consequently, we can compute $N_{2x}$ by appealing to the regularity of the
contact points given by Proposition 2.2.

######  Lemma .

Let $b_{2x}$ denote the number of contact points of $\upsilon(t),\,0<t\leq
2x$, on the barrier. Then

$N_{2x}=8y+m_{2x}b_{2x}.$

###### Proof.

Since $0<t\leq 2x$, the unfolding $\upsilon$ cuts $\frac{y}{x}\cdot 2x=2y$
horizontal inclines. Between consecutive horizontal inclines, $\upsilon$ cuts
four non-vertical edges. Recall that the points at which $\upsilon$ cuts
vertical edges correspond to the contact points on the barrier. Since the
initial and terminal points of $\upsilon$ are aligned, all contact points have
the same multiplicity $m_{2x}$ by Proposition 2.2. Thus the total number of
contact points on the barrier is $m_{2x}b_{2x}$, which is also the total
number of vertical edges cut by $\upsilon$. Consequently, the total number of
edges cut by $\upsilon$ is $4\cdot 2y+m_{2x}b_{2x}=8y+m_{2x}b_{2x}.$ ∎

An explicit formula for $N_{2x}$ follows from explicit formulas for $m_{2x}$
and $b_{2x}$.

######  Lemma .

The multiplicity $m_{2x}$ and the spacing $s$ between consecutive contact
points are given by

$m_{2x}=\left\\{\begin{array}[c]{cc}2,&\textnormal{if }x\equiv
y\operatorname{mod}2\\\ 1,&\textnormal{if }x\not\equiv
y\operatorname{mod}2\end{array}\right.\text{ and \
}s=\left\\{\begin{array}[c]{cc}2/x,&\textnormal{if }x\equiv
y\operatorname{mod}2\\\ 1/x,&\,\textnormal{if }x\not\equiv
y\operatorname{mod}2.\end{array}\right.$

###### Proof.

At the first alignment, $\mathcal{C}_{T_{1}}$ consists of $T_{1}$ distinct
contact points each with multiplicity $1$. If $x\equiv y\bmod 2$, then
$T_{1}=x$ by Proposition 2.2, so that each contact point of $\mathcal{C}_{2x}$
has multiplicity $2$. Since there are $x$ distinct contact points on the fence
$\mathcal{F}$ of length $2$, the spacing $s=\frac{2}{x}$. If $x\not\equiv
y\bmod 2$, then $T_{1}=2x$ so that each contact point in $\mathcal{C}_{2x}$
has multiplicity $1$. Consequently, there are $2x$ distinct contact points and
the spacing $s=\frac{2}{2x}=\frac{1}{x}$. ∎

Having established the spacing $s$, let us derive a formula for the number
$b_{2x}$ of contact points on the barrier. Let $\left[x\right]$ denote the
integer part of $x$.

######  Lemma .

The number of contact points on the barrier is

$\displaystyle b_{2x}=\begin{cases}\frac{4}{3s}&\textnormal{if }3\mid x\vskip
3.0pt plus 1.0pt minus 1.0pt\\\
\left[\frac{4}{3s}\right]\,\,\textnormal{or}\,\,\left[\frac{4}{3s}\right]+1&\textnormal{if
}3\nmid x.\end{cases}$

###### Proof.

Horizontally translating the initial point $P$ uniformly shifts the contact
points and preserves the spacing $s$. Since
$s\in\\{\frac{1}{x},\frac{2}{x}\\}$, the length of barrier $\frac{4}{3}$ is an
integer multiple of $s$ if and only if $3\mid x$.

Suppose $3\mid x$. Since contact points are equally spaced and the barrier
$\left(\frac{1}{3},\frac{5}{3}\right]$ is half open, uniformly shifting the
contact points preserves the number of contact points on the barrier. Thus
$b_{2x}=\frac{4}{3s}$. Suppose $3\nmid x$. Uniformly shifting the contact
points alternately increases or decreases $b_{2x}$ by $1$ as contact points
enter or leave the barrier. Therefore
$b_{2x}\in\\{\left[\frac{4}{3s}\right],\left[\frac{4}{3s}\right]+1\\}$. ∎

The facts we need to derive an explicit formula for $N_{2x}$ are now in place.

######  Proposition .

The number $N:=N_{2x}$ is given by the following table:

$N\equiv 1,3\bmod 4$ | $N\equiv 2\bmod 4$ | $N\equiv 0\bmod 4$ |
---|---|---|---
|  | $8y+\frac{4x}{3}$ | $x\equiv 0\bmod 3\textnormal{ and }x\equiv y\bmod 2$
|  | $8y+\frac{4x}{3}$ | $x\equiv 0\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$
| $8y+\frac{4x+2}{3}$ | $8y+\frac{4x-4}{3}$ | $x\equiv 1\bmod 3\textnormal{ and }x\equiv y\bmod 2$
$8y+\frac{4x-1}{3}$ | $8y+\frac{4x+2}{3}$ |  | $x\equiv 1\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$
| $8y+\frac{4x-2}{3}$ | $8y+\frac{4x+4}{3}$ | $x\equiv 2\bmod 3\textnormal{ and }x\equiv y\bmod 2$
$8y+\frac{4x+1}{3}$ | $8y+\frac{4x-2}{3}$ |  | $x\equiv 2\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$

######  Remark.

The columns are arranged to accommodate Proposition 2.4.

###### Proof.

The formula for $N_{2x}$ follows immediately from Lemmas 2.3, 2.3, and 2.3.

Case 1. If $x\equiv 0\bmod 3$ and $x\equiv y\bmod 2$, then $m_{2x}=2$,
$s=\frac{2}{x}$, and $b_{2x}=\frac{4}{3s}$. Thus
$N_{2x}=8y+m_{2x}b_{2x}=8y+2\cdot\frac{4}{3}\cdot\frac{x}{2}=8y+\frac{4x}{3}$.

Case 4. If $x\equiv 1\bmod 3$ and $x\not\equiv y\bmod 2$, then $m_{2x}=1$,
$s=\frac{1}{x}$, and either $b_{2x}=\left[\frac{4}{3s}\right]$ or
$\left[\frac{4}{3s}\right]+1$. If $b_{2x}=\left[\frac{4}{3s}\right]$, then
$N_{2x}=8y+m_{2x}b_{2x}=8y+1\cdot\left[\frac{4}{3}\cdot\frac{x}{1}\right]=8y+\frac{4x-1}{3}$.
If $b_{2x}=\left[\frac{4}{3s}\right]+1$, then
$N_{2x}=8y+1\cdot\left(\left[\frac{4}{3}\cdot\frac{x}{1}\right]+1\right)=8y+\frac{4x+2}{3}$.

Proofs of the other cases are similar and left to the reader. ∎

###  2.4 Computing the period of a periodic orbit

Since the period of a periodic orbit is the period of its primitive sub-
orbits, let us determine the values of $T$ for which $\upsilon(t),0<t\leq T$,
is an unfolding of a primitive periodic orbit.

######  Proposition .

Let $x,y\in\mathbb{N}$ such that $x<y$ and $\mathrm{gcd}(x,y)=1$. A primitive
periodic orbit $\gamma$ with initial angle
$\Theta=\arctan(\frac{y}{x}\sqrt{3})$ has an unfolding $\upsilon(t)$, $0<t\leq
T$, for some $T\in\\{x,2x,4x\\}$, and period $p(x,y)$ determined as follows:

  1. 1.

If $x\equiv y\bmod 2$ and $N_{2x}\equiv 0\bmod 4$, then $T=x$ and
$p(x,y)=\frac{1}{2}N_{2x}$.

  2. 2.

If $x\equiv y\bmod 2$ and $N_{2x}\equiv 2\bmod 4$, then $T=2x$ and
$p(x,y)=N_{2x}$.

  3. 3.

If $x\not\equiv y\bmod 2$ and $N_{2x}$ is even, then $T=2x$ and
$p(x,y)=N_{2x}$.

  4. 4.

If $x\not\equiv y\bmod 2$ and $N_{2x}$ is odd, then $T=4x$ and
$p(x,y)=2N_{2x}$.

###### Proof.

A primitive periodic orbit has an unfolding $\upsilon(t)$, $0<t\leq T$, if and
only if $T$ is the smallest positive integer such that the initial and
terminal points are aligned and $N_{T}$ is even. Recall that the alignment
condition implies $x\mid T$, and the first alignment $T_{1}=x$ when $x\equiv
y\bmod 2$ and $T_{1}=2x$ otherwise.

Case 1. If $x\equiv y\bmod 2$, then $T_{1}=x$. If $N_{2x}\equiv 0\bmod 4$,
then $N_{x}=\frac{1}{2}N_{2x}$ is even so that $T=x$ and
$p(x,y)=N_{x}=\frac{1}{2}N_{2x}$. If $N_{2x}\equiv 2\bmod 4$, then
$N_{x}=\frac{1}{2}N_{2x}$ is odd so that $T=2x$ and $p(x,y)=N_{2x}$.

Case 2. If $x\not\equiv y\bmod 2$, then $T_{1}=2x$. If $N_{2x}$ is even, then
$T=2x$ and $p(x,y)=N_{2x}$. If $N_{2x}$ is odd, then $N_{4x}=2N_{2x}$ is even
so that $T=4x$ and $p(x,y)=N_{4x}=2N_{2x}$. ∎

The period of every periodic orbit is now determined.

######  Theorem .

Let $x,y\in\mathbb{N}$ such that $x<y$ and $\mathrm{gcd}(x,y)=1$. Then the
period $p(x,y)$ of a periodic orbit with initial angle
$\Theta=\arctan(\frac{y}{x}\sqrt{3})$ is

$p(x,y)=\begin{cases}4y+\frac{2x}{3}&{\rm if}\,\,x\equiv 0\textnormal{ mod
3}\textnormal{ and }x\equiv y\textnormal{ mod 2}\\\ 8y+\frac{4x}{3}&{\rm
if}\,\,x\equiv 0\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{
mod 2}\\\ 4y+\frac{2x-2}{3}\textnormal{ or
}\textnormal{8}y+\frac{4x+2}{3}&{\rm if}\,\,x\equiv 1\textnormal{ mod
3}\textnormal{ and }x\equiv y\textnormal{ mod 2}\\\
16y+\frac{8x-2}{3}\textnormal{ or }8y+\frac{4x+2}{3}&{\rm if}\,\,x\equiv
1\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{ mod 2}\\\
4y+\frac{2x+2}{3}\textnormal{ or }8y+\frac{4x-2}{3}&{\rm if}\,\,x\equiv
2\textnormal{ mod 3}\textnormal{ and }x\equiv y\textnormal{ mod 2}\\\
16y+\frac{8x+2}{3}\textnormal{ or }8y+\frac{4x-2}{3}&{\rm if}\,\,x\equiv
2\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{ mod 2}.\\\
\end{cases}$

###### Proof.

Propositions 2.3 and 2.4 immediately lead to the formula for $p(x,y)$.

Case 1. If $x\equiv 0\bmod 3$ and $x\equiv y\bmod 2$, then
$N_{2x}=8y+\frac{4x}{3}\equiv 0\bmod 4$ so that
$p(x,y)=\frac{1}{2}N_{2x}=4y+\frac{2x}{3}$.

Case 4. If $x\equiv 1\bmod 3$ and $x\not\equiv y\bmod 2$, then
$N_{2x}=8y+\frac{4x-1}{3}$ or $N_{2x}=8y+\frac{4x+2}{3}$. In the first case,
$N_{2x}$ is odd so that $p(x,y)=2N_{2x}=16y+\frac{8x-2}{3}$; in the second
case, $N_{2x}$ is even so that $p(x,y)=N_{2x}=8y+\frac{4x+2}{3}$.

Proofs of the other cases are similar and left to the reader. ∎

When $\Theta=60^{\circ}$, periods $4$ and $10$ are consistent with the formula
in Theorem 2.4 with $(x,y)=(1,1)$; when $\Theta=90^{\circ}$, period $8$ is
consistent with $(x,y)=(0,1)$.

######  Corollary .

A biperiodic periodic orbit with initial angle
$\Theta=\arctan\big{(}\frac{y}{x}\sqrt{3}\big{)}$ has one of two possible
periods $p_{1}<p_{2}$, where $p_{2}=2p_{1}+2$ or $p_{2}=2p_{1}-2$.

While our understanding of unfoldings follows by considering the fence, the
simple statement in Thoerem 12 makes no mention of the initial point. However,
the framework developed here allows us to determine a more precise period
formula in terms of the initial and terminal points $P=(a,0)$ and $Q=(a+x,y)$,
and doing so required us to compute the number of contact points on the
barrier as a function of $a$:

$b_{a}(x,y)=\left[\frac{5/3+ay/x}{s_{a}(x,y)}\right]-\left[\frac{1/3+ay/x}{s_{a}(x,y)}\right],$

where $s_{a}(x,y)$ is the spacing function.

##  3 Periodic orbits on other obtuse polygons

The methods developed in Section 2 can be applied to a $60^{\circ}$-rhombus
and a $60^{\circ}$-$90^{\circ}$-$120^{\circ}$-kite. Let $\mathcal{T}_{1}$ and
$\mathcal{T}_{2}$ be the respective edge tessellations generated by a
$60^{\circ}$-rhombus and a $60^{\circ}$-$90^{\circ}$-$120^{\circ}$-kite. Note
that an analogue of Theorem 2.1 holds in both of these cases. In either case,
periodic orbits can be represented by unfoldings with an initial angle
$\Theta\in[60^{\circ},90^{\circ}]$, and $\Theta\in(60^{\circ},90^{\circ})$ can
be expressed in the form $\Theta=\arctan(\frac{y}{x}\sqrt{3})$ with $x<y$ and
$\gcd(x,y)=1$. When $\Theta=60^{\circ}$ or $\Theta=90^{\circ}$, the period can
be determined by inspection and fits the general formula to be derived.

###  3.1 The $60^{\circ}$-rhombus

Note that $\mathcal{T}_{1}$ can be obtained from $\mathcal{T}$ by removing its
$0^{\circ}$, $60^{\circ}$, and $120^{\circ}$ inclines (see Figure 5(a)).
Impose the same coordinate system on $\mathcal{T}_{1}$ we imposed on
$\mathcal{T}$. The barrier and gate for $\mathcal{T}_{1}$ are identical to the
barrier and gate for $\mathcal{T}$, and all definitions and techniques in the
previous sections apply. Although $\mathcal{T}_{1}$ has no horizontal
inclines, we can position the initial point of an unfolding $\upsilon$ on a
horizontal incline of $\mathcal{T}$ (the dotted line on Figure 5(a)). Although
a $60^{\circ}$-rhombus exhibits both line and rotational symmetry, a quick
check shows that the initial and terminal rhombuses determined by an unfolding
with aligned initial and terminal points, may differ by a reflection but not
by a rotation.

The formula $N_{2x}=4y+m_{2x}b_{2x}$ (as in Lemma 2.3) leads to the following
table (as in Proposition 2.3):

$N\equiv 1,3\bmod 4$ | $N\equiv 2\bmod 4$ | $N\equiv 0\bmod 4$ |
---|---|---|---
|  | $4y+\frac{4x}{3}$ | $x\equiv 0\bmod 3\textnormal{ and }x\equiv y\bmod 2$
|  | $4y+\frac{4x}{3}$ | $x\equiv 0\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$
| $4y+\frac{4x+2}{3}$ | $4y+\frac{4x-4}{3}$ | $x\equiv 1\bmod 3\textnormal{ and }x\equiv y\bmod 2$
$4y+\frac{4x-1}{3}$ | $4y+\frac{4x+2}{3}$ |  | $x\equiv 1\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$
| $4y+\frac{4x-2}{3}$ | $4y+\frac{4x+4}{3}$ | $x\equiv 2\bmod 3\textnormal{ and }x\equiv y\bmod 2$
$4y+\frac{4x+1}{3}$ | $4y+\frac{4x-2}{3}$ |  | $x\equiv 2\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$

Proposition 2.4 applies, and when combined with the table above, produces the
following formula for the period (as in Theorem 2.4):

$p(x,y)=\begin{cases}2y+\frac{2x}{3}&{\rm if}\,\,x\equiv 0\textnormal{ mod
3}\textnormal{ and }x\equiv y\textnormal{ mod 2}\\\ 4y+\frac{4x}{3}&{\rm
if}\,\,x\equiv 0\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{
mod 2}\\\ 2y+\frac{2x-2}{3}\textnormal{ or
}\textnormal{4}y+\frac{4x+2}{3}&{\rm if}\,\,x\equiv 1\textnormal{ mod
3}\textnormal{ and }x\equiv y\textnormal{ mod 2}\\\
4y+\frac{4x+2}{3}\textnormal{ or }8y+\frac{8x-2}{3}&{\rm if}\,\,x\equiv
1\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{ mod 2}\\\
2y+\frac{2x+2}{3}\textnormal{ or }4y+\frac{4x-2}{3}&{\rm if}\,\,x\equiv
2\textnormal{ mod 3}\textnormal{ and }x\equiv y\textnormal{ mod 2}\\\
4y+\frac{4x-2}{3}\textnormal{ or }8y+\frac{8x+2}{3}&{\rm if}\,\,x\equiv
2\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{ mod 2}.\\\
\end{cases}$

(a) The tessellation $\mathcal{T}_{1}$ generated by a $60^{\circ}$-rhombus.

$A$$O$$B$$D$ (b) The tessellation $\mathcal{T}_{2}$ generated by a
$60^{\circ}$-$90^{\circ}$-$120^{\circ}$-kite.

Figure 5:

###  3.2 The $60^{\circ}$-$90^{\circ}$-$120^{\circ}$-kite

The edge tessellation $\mathcal{T}_{2}$ is also related to $\mathcal{T}$.
Consider the $60^{\circ}$-$90^{\circ}$-$120^{\circ}$-kite positioned as $\Box
AOBD$, where $A$ and $B$ coincide with the two vertices of the
$120^{\circ}$-isosceles $\triangle ABC$ and $O$ is the midpoint of
$\overline{AC}$ (see Figure 5(b)). Impose the same coordinate system on
$\mathcal{T}_{2}$ we imposed on $\mathcal{T}$ and position the initial point
of an unfolding $\upsilon$ on a horizontal incline. While the fence is the
same as before, the barrier and gate are interchanged, i.e.,
$(\frac{1}{3},\frac{5}{3}]$ is the gate.

The formula $N_{2x}=6y+m_{2x}b_{2x}$ (as in Lemma 2.3) leads to the following
table (as in Proposition 2.3):

$N\equiv 1,3\bmod 4$ | $N\equiv 2\bmod 4$ | $N\equiv 0\bmod 4$ |
---|---|---|---
|  | $6y+\frac{2x}{3}$ | $x\equiv 0\bmod 3\textnormal{ and }x\equiv y\bmod 2$
| $6y+\frac{2x}{3}$ |  | $x\equiv 0\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$
| $6y+\frac{2x-2}{3}$ | $6y+\frac{2x+4}{3}$ | $x\equiv 1\bmod 3\textnormal{ and }x\equiv y\bmod 2$
$6y+\frac{2x+1}{3}$ |  | $6y+\frac{2x-2}{3}$ | $x\equiv 1\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$
| $6y+\frac{2x+2}{3}$ | $6y+\frac{2x-4}{3}$ | $x\equiv 2\bmod 3\textnormal{ and }x\equiv y\bmod 2$
$6y+\frac{2x-1}{3}$ |  | $6y+\frac{2x+2}{3}$ | $x\equiv 2\bmod 3\textnormal{ and }x\not\equiv y\bmod 2$

Proposition 2.4 applies, and when combined with the table above, produces the
following formula for the period (as in Theorem 2.4):

$p(x,y)=\begin{cases}3y+\frac{x}{3}&{\rm if}\,\,x\equiv 0\textnormal{ mod
3}\textnormal{ and }x\equiv y\textnormal{ mod 2}\\\ 6y+\frac{2x}{3}&{\rm
if}\,\,x\equiv 0\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{
mod 2}\\\ 3y+\frac{x+2}{3}\textnormal{ or }\textnormal{6}y+\frac{2x-2}{3}&{\rm
if}\,\,x\equiv 1\textnormal{ mod 3}\textnormal{ and }x\equiv y\textnormal{ mod
2}\\\ 6y+\frac{2x-2}{3}\textnormal{ or }12y+\frac{4x+2}{3}&{\rm if}\,\,x\equiv
1\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{ mod 2}\\\
3y+\frac{x-2}{3}\textnormal{ or }6y+\frac{2x+2}{3}&{\rm if}\,\,x\equiv
2\textnormal{ mod 3}\textnormal{ and }x\equiv y\textnormal{ mod 2}\\\
6y+\frac{2x+2}{3}\textnormal{ or }12y+\frac{4x-2}{3}&{\rm if}\,\,x\equiv
2\textnormal{ mod 3}\textnormal{ and }x\not\equiv y\textnormal{ mod 2}.\\\
\end{cases}$

###  3.3 The Regular Hexagon

While the techniques in Section 2 can be applied to determine the number of
edges cut by an unfolding of a periodic orbit on a regular hexagon, the
presence of rotational symmetries renders this information insufficient to
determine exactly where an unfolding terminates. Position the hexagon so that
a subdivision of its edge tessellation is the edge tessellation generated by a
$120^{\circ}$-isosceles triangle, and restrict considerations to initial
angles $\Theta\in(30^{\circ},60^{\circ})$.

Although we are unable to rigorously solve the problem, we pose a conjecture
based on extensive numerical evidence. We computed the period for 3814 pairs
$(x,y)$ and partitioned these pairs into planar groups using a mixture
algorithm [1]. We conjecture that the period $p(x,y)$ is

$\begin{cases}3y+x&{\rm if}\,\,x\equiv 0\textnormal{ mod 3},x\equiv
y\textnormal{ mod 2},\textnormal{and }(x,y)\in A_{0,0}\\\ y+\frac{x}{3}&{\rm
if}\,\,x\equiv 0\textnormal{ mod 3},x\equiv y\textnormal{ mod
2},\textnormal{and }(x,y)\in A^{c}_{0,0}\\\ 6y+2x&{\rm if}\,\,x\equiv
0\textnormal{ mod 3},x\not\equiv y\textnormal{ mod 2},\textnormal{and
}(x,y)\in A_{0,1}\\\ 2y+\frac{2x}{3}&{\rm if}\,\,x\equiv 0\textnormal{ mod
3},x\not\equiv y\textnormal{ mod 2},\textnormal{and }(x,y)\in A^{c}_{0,1}\\\
2y+\frac{2x-2}{3}\textnormal{ or }\textnormal{3}y+x+2&{\rm if}\,\,x\equiv
1\textnormal{ mod 3},x\equiv y\textnormal{ mod 2},\textnormal{and }(x,y)\in
A_{1,0}\\\ y+\frac{x+2}{3}\textnormal{ or }\textnormal{2}y+\frac{2x-2}{3}&{\rm
if}\,\,x\equiv 1\textnormal{ mod 3},x\equiv y\textnormal{ mod
2},\textnormal{and }(x,y)\in A^{c}_{1,0}\\\ 4y+\frac{4x+2}{3}\textnormal{ or
}6y+2x-2&{\rm if}\,\,x\equiv 1\textnormal{ mod 3},x\not\equiv y\textnormal{
mod 2},\textnormal{and }(x,y)\in A_{1,1}\\\ 2y+\frac{2x-2}{3}\textnormal{ or
}4y+\frac{4x+2}{3}&{\rm if}\,\,x\equiv 1\textnormal{ mod 3},x\not\equiv
y\textnormal{ mod 2},\textnormal{and }(x,y)\in A^{c}_{1,1}\\\
2y+\frac{2x+2}{3}\textnormal{ or }3y+x-2&{\rm if}\,\,x\equiv 2\textnormal{ mod
3},x\equiv y\textnormal{ mod 2},\textnormal{and }(x,y)\in A_{2,0}\\\
y+\frac{x-2}{3}\textnormal{ or }2y+\frac{2x+2}{3}&{\rm if}\,\,x\equiv
2\textnormal{ mod 3},x\equiv y\textnormal{ mod 2},\textnormal{and }(x,y)\in
A^{c}_{2,0}\\\ 4y+\frac{4x-2}{3}\textnormal{ or }6y+2x+2&{\rm if}\,\,x\equiv
2\textnormal{ mod 3},x\not\equiv y\textnormal{ mod 2},\textnormal{and
}(x,y)\in A_{2,1}\\\ 2y+\frac{2x+2}{3}\textnormal{ or }4y+\frac{4x-2}{3}&{\rm
if}\,\,x\equiv 2\textnormal{ mod 3},x\not\equiv y\textnormal{ mod
2},\textnormal{and }(x,y)\in A^{c}_{2,1},\end{cases}$

where the sets $A_{i,j}$ have yet to be determined. A numerical grid search
appeared to indicate that the sets $A_{i,j}$ cannot be described by a linear
modulus condition $c_{1}x+c_{2}y\bmod c_{3}$ for any
$c_{1},c_{2}=-36,-35,...,35,36$ and $c_{3}=2,...,36$. However, when $3\mid x$,
we conjecture that whenever $(x,y)\in A_{i,j}$ for any $i,j$, then
$(27y-7x,11y-3x)\in A_{i^{\prime},j^{\prime}}$ for some possibly different
$i^{\prime},j^{\prime}$. Under this assumption, we can state our conjecture
for the period formula more precisely for a given $x$.

## Acknowledgments

We wish to thank David Brown for his participation in an undergraduate
research seminar during the 2011-2012 academic year in which this problem was
first considered, and Joshua Pavoncello for writing a computer program [5]
that visualizes the orbits on an edge tessellating polygon and collects
related experimental data. And we wish to thank the referees whose numerous
helpful suggestions improved the exposition.

## References

  * [1] Baer, B., Gilani, F. Billiard simulations. Retrieved from: https://github.com/FaheemGilani/Billiards.
  * [2] Baxter, A., Eskreis-Winkler, J., McCarthy, E. (2011). Periodic Billiard Paths in Edge Tessellating Polygons. Unpublished Manuscript.
  * [3] Baxter, A., Umble, R. (2008). Periodic Orbits for Billiards on an Equilateral Triangle. American Mathematical Monthly, 115 (6) 479-491.
  * [4] Kirby, M., Umble, R. (2011). Edge Tessellations and Stamp Folding Puzzles. Mathematics Magazine. 84 (4) 283-289.
  * [5] Pavoncello, J. (2013). Orbit Mapper. Retrieved from: https://github.com/jrpavoncello/OrbitMapper.
  * [6] Umble, R., Han, Z. (2015). Transformational Plane Geometry. Chapman and Hall/CRC.

## About the authors

### Benjamin R. Baer

Department of Statistics and Data Science, Cornell University, Ithaca, NY
14853<EMAIL_ADDRESS>
Mr. Baer is a sixth year statistics PhD student at Cornell University studying
statistical methodology.

### Faheem Gilani

Department of Mathematics, The Pennsylvania State University, State College,
PA 16801<EMAIL_ADDRESS>
Mr. Gilani is a fifth year mathematics PhD student at Penn State studying
machine learning.

### Zhigang Han

Department of Mathematics, Millersville University of Pennsylvania,
Millersville, PA 17551<EMAIL_ADDRESS>
Dr. Han is an Associate Professor of Mathematics at Millersville University.
His primary research areas are symplectic geometry and topology.

### Ronald Umble

Department of Mathematics, Millersville University of Pennsylvania,
Millersville, PA 17551<EMAIL_ADDRESS>
Dr. Umble retired from teaching in August of 2020. He is a Professor of
Mathematics Emeritus at Millersville University and a member of Pi Mu
Epsilon–Pennsylvania Zeta Chapter. His primary research area is algebraic
topology. He has directed or codirected 19 undergraduate research projects,
nine of which led to publications.


]  Further improvement on index bounds
Y. Wu]Yansheng Wu
School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, P. R. China;  Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai 200062, P. R. China

Y. Lee] Yoonjin Lee
Department of Mathematics, Ewha Womans
University, Seoul, 03760, Republic of Korea

Q. Wang]Qiang Wang
School of Mathematics and Statistics, Carleton University, Ottawa, ON K1S 5B6, Canada

Y. Wu was supported by the National Natural Science Foundation of China (Grant No. 12101326), the Natural Science Foundation of Jiangsu Province (Grant No. BK20210575 ).
Y. Lee is a corresponding author and supported by
the National Research Foundation of Korea (NRF) grant funded by the Korea government (MEST)(NRF-2017R1A2B2004574) and also by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (Grant No. 2019R1A6A1A11051177). The research of Qiang Wang is partially supported by NSERC of Canada (RGPIN-2017-06410).

In this paper we obtain further improvement of index bounds for character sums of polynomials over finite fields. We present some examples, which show that our new bound is  an improved bound compared to both the Weil bound and the index bound given by Wan and Wang.
As an application, we count the number of all the solutions of some algebraic curves by using our result.

§ INTRODUCTION

Let  $p$  be  a prime number and  $ \Bbb F_q$ be a finite field, where $q=p^m$ for some positive integer $m$.  Let  $\psi: \Bbb F_q \to \mathbb{C} ^*$ be a nontrivial additive character and  $f(x)\in \Bbb F_q[x]$. The following sums

$$\sum_{x\in \Bbb F_q}\psi(f(x))$$

are referred to as the Weil sums [9]. Throughout this paper,  we always view a polynomial $f(x)\in\Bbb F_q[x] $ as a mapping over $\Bbb F_q$.  In this sense the degree of a polynomial in $\Bbb F_q[x]$ should be controlled  by $q-1$ when we consider  Weil sums.

Given a polynomial $f(x)\in\Bbb F_q[x] $ of positive degree $n$ with  $\gcd(n,q)=1$, we have

\begin{equation}\bigg|\sum_{x\in \Bbb F_q}\psi(f(x))\bigg|\le (n-1)\sqrt{q}.\end{equation}

The upper bound in  (1.1) is well known as the Weil bound.

The Weil bound for character sums has many applications  in mathematics, theoretical computer science, and information theory etc.
The Weil bound is trivial when the degree of the polynomial  is bigger than $\sqrt{q}$.
Some progress on improvement to the Weil bound has been made as follows.

(1) Using Deligne's bound for exponential sums in several variables, Gillot et al. [6, 7] provided a new bound for $|\sum_{x\in \Bbb F_{q^m}}\psi(f(x))|$ such that for any $b\in \Bbb F_{q^m}^*$ the $q$-degree of  $f(x)=bx^d+g(x)\in \Bbb F_{q^m}[x]$ only depends on the leading term $bx^d$ ;  the $q$-degree of a nonzero polynomial $f$ over $\Bbb F_{q^m}$ is defined by
\begin{equation*}\mbox{deg}_{q}(f)=\underset{}{\mbox{max}}\{d_{0}+d_{1}+\cdots+d_{m-1}:  d\in \mbox{supp}(f)\}, \end{equation*}
where  $d=d_{0}+d_{1}q+\cdots+d_{m-1}q^{m-1}$ denotes the $q$-ary expansion of $d$.

(2) Wan and Wang [10] obtained an index bound for character sums over finite fields; they used the the concept of index of a polynomial over a finite field, which was first introduced in the research of permutation polynomials [1]. This bound improved the Weil bound for high degree polynomials with small indices as well as polynomials with large indices that are generated by cyclotomic mapping of small indices.

(3) Recently, there is an improvement on the Hasse-Weil bound in the characteristic two case by Cramer and Xing [3].
They used the algebraic geometry and the algebraic number theory.
As an application, they also improved the Weil bound for character sums.

§.§ Main result and  comparison with previous results

The concept of the index of a polynomial over a finite field was first introduced in [1].

A polynomial $f(x)\in  \Bbb F_{q}[x] $ of degree $n\le q-1$ can be written as the following form:

where $a, a_{n-i_j}\neq 0, j=1,\ldots,k$. Let $r$ be the lowest degree of $x$ in $f(x)-b$. The index $ l$ of the polynomial $f(x)$ is defined by

$$l:=\frac{q-1}{\gcd(n-r,n-r-i_1, \ldots, n-r-i_{k-1},q-1)}.$$
In fact, any non-constant polynomial $f(x)\in  \Bbb F_{q}[x] $ of degree $n \le q-1$ can be written uniquely as $f(x)=a(x^r h(x^{(q-1)/l}))+b$.

By using the index of polynomials, Wan and Wang [10] found a new bound, which is called an index bound, for character sums of polynomials over finite fields as follows:

<cit.> Let $f(x)=x^r h(x^{(q-1)/l})+b\in \Bbb F_q[x]$ be any polynomial with index $l$.
Let $\xi$ be a primitive $l$-th root of unity in $\Bbb F_q$ and $n_0=\sharp\{0\le i\le l-1 \mid h(\xi^i)=0\}$.
Let $\psi: \Bbb F_q \to \mathbb{C} ^*$ be a nontrivial additive character.

\begin{equation}\bigg|\sum_{x\in \Bbb F_q}\psi(f(x))-\frac{q}{l}n_0\bigg|\le (l-n_0)\gcd\bigg(r, \; \frac{q-1}{l}\bigg)\sqrt{q}.\end{equation}

This theorem is sensitive to the form of $f(x)$. Replacing $f(x)$ with $f^{*} (x) = f(x) + d(x)$
such that  $\sum_{x\in \Bbb F_q}  \psi(d(x)) = 0$, and in particular, for $d(x)$ of the form $y^p -y$, leaves the
left hand side  unchanged but may lower the upper bound in the right hand side.

As mentioned before, we can view  a polynomial as a mapping over $\Bbb F_{q} $ when we just consider the Weil sums. Then it is easy to extend the Frobenius mapping $\pi$ over $\Bbb F_q$ to $\Bbb F_{q}[x]$ as follows:

$$\pi : \Bbb F_{q}[x] \to \Bbb F_{q}[x], \pi(a) = a^p, \pi(x)=x^p.$$

There is an equivalence relation between polynomials  in $\Bbb F_{q}[x]$. Given two polynomials $f(x)=\sum_ia_ix^i$ and $g(x)$ in $\Bbb F_{q}[x]$, we write $f\sim g$ if there exists a vector $v=(v_0, v_1,\ldots, v_n)\in \mathbb{Z}_m^{n+1}$ such that
The equivalence class of $f(x) \in \mathbb{F}_q[x]$ is denoted by $[f]$.
For each polynomial $g(x)$ in the equivalence class $[f]$, we  use $l_g$ for  the index of $g(x)$ and $n_g$ for the degree of $g(x)$. For each equivalence class $[f]$, let $l^*$ be defined by
$$l^*=\mbox{min}\{l_g: g\in [f]\}.$$
Then there exists a polynomial $f^*(x)\in [f]$ such that
$f^*(x)=x^{r^*} h^*(x^{(q-1)/l^*})+b\in \Bbb F_q[x]$ and
the index of  $f^*(x)$ is exactly $l^*.$    We call  $f^*(x)$ the equivalent polynomial of $f(x)$ with the smallest index and $h^*(x)$ the associated polynomial of $f^*(x)$.

The following theorem is our main result, which provides a new formulation of index bounds in Theorem 1.1 for character sums of polynomials over finite fields.

Let $f(x)\in \Bbb F_q[x]$ be a polynomial of positive degree $n$ with $\gcd(n,q)=1$. Let $f^*(x)$ be  the equivalent polynomial of $f(x)$ with the smallest index $l^*$ and $h^*(x)$ the associated polynomial of $f^*(x)$.  Let $\xi$ be a primitive $l^*$-th root of unity in $\Bbb F_q$ and $n_0=\sharp\{0\le i\le l^*-1 \mid  h^*(\xi^i)=0\}$. Let $\psi: \Bbb F_q \to \mathbb{C} ^*$ be a nontrivial additive character.  Then

\begin{equation}\label{indexbound}
\bigg|\sum_{x\in \Bbb F_q}\psi(f(x))-\frac{q}{l^*}n_0\bigg|\le (l^*-n_0)\gcd\bigg(r^*, \; \frac{q-1}{l^*}\bigg)\sqrt{q}.\end{equation}

The following examples show that the upper bound in (<ref>)  is indeed  an improved bound compared to both the Weil bound in (1.1) and the index bound in Theorem 1.1.

Let $f(x)=x^{25}+ax^4\in \Bbb F_{27}[x]$, where $a\in \Bbb F_{27}^*$.   Obviously, the Weil bound is trivial because of the high degree. Since the index of $f$ is $26$, the index bound is also trivial.

However, by Theorem <ref>, $l^*=\frac{26}{\gcd(25-12,26)}=2$.

If $a^3  = \pm 1$,
$\bigg|\sum_{x\in \Bbb F_{27}}\psi(x^{25}+ax^4)-\frac{27}{2}\bigg|\le \sqrt{27}$;
otherwise, we have $\bigg|\sum_{x\in \Bbb F_{27}}\psi(x^{25}+ax^4) \bigg|\le2\sqrt{27}.$

Let $f(x)=x^{19}+ax^2\in \Bbb F_{27}[x]$, where $a\in \Bbb F_{27}^*$.   Obviously, the Weil bound and the index bound are both  trivial.
By Theorem <ref>, $l^*=2$.  If  $a^3  = \pm 1$,
$\bigg|\sum_{x\in \Bbb F_{27}}\psi(x^{19}+ax^2)-\frac{27}{2}\bigg|\le \sqrt{27}$;
otherwise, we have $\bigg|\sum_{x\in \Bbb F_{27}}\psi(x^{19}+ax^2) \bigg|\le2\sqrt{27}.$

Similarly, we define

\begin{equation}\label{eqn:n*}
n^* = \mbox{min}\{n_g: g\in [f]\}.
\end{equation}

Then using the Weil bound,  the same arguments derives

\begin{equation}\label{eqn:reducedweil}
\bigg|\sum_{x\in \Bbb F_q}\psi(f(x)) \bigg| \le (n^*-1)\sqrt{q}.
\end{equation}

The following examples show that the upper bound in (<ref>)  is also an improved  bound  when it is  compared to  the Weil bound in (1.1),  the index bound in Theorem 1.1, and the upper bound in (<ref>).

Let $f(x)=x^{19}+ax^4\in \Bbb F_{27}[x]$, where $a\in \Bbb F_{27}^*$.   Obviously, the Weil bound, the index bound, and the upper bound in (<ref>) are all trivial.  However, by (<ref>) and (<ref>), we have  $n^*=5$ and
$\bigg|\sum_{x\in \Bbb F_{27}}\psi(x^{19}+ax^4) \bigg|\le4\sqrt{27}.$

Let $f(x)=x^{10}+ax^5\in \Bbb F_{27}[x]$, where $a\in \Bbb F_{27}^*$.   Obviously, the Weil bound,   the index bound, and  the upper bound in (<ref>) are all  trivial.  However, by (<ref>) and (<ref>), we have  $n^*=5$ and
$\bigg|\sum_{x\in \Bbb F_{27}}\psi(x^{10}+ax^5) \bigg|\le4\sqrt{27}.$

The $p$-cyclotomic coset modulo $q-1$ containing $i$ is defined by
$$C_i =\{ip^j \pmod {q-1}: 0\le j <l_i\},$$

where $l_i$ is the smallest positive integer such that $p^{l_i} i\equiv i \pmod {q-1}$, and is the cardinality of $C_i$. The smallest integer in $C_i$ is called the coset leader of $C_i$. By <cit.>, we also find an infinite family of polynomials, which shows that the upper bound  in (<ref>) is  an improved bound.

Let $q=p^m$,  $s$ be an integer with $p<s<\sqrt q$,  and $\gcd(s,p)=1$.  Let $f(x)=x^{sp^{m-1}}+ax^r\in \Bbb F_q[x]$, where $a\in \Bbb F_q^*$ and $r<s$. Then $\gcd(sp^{m-1}-q+1,q)=1$, $n^*=s$, and  $\bigg|\sum_{x\in \Bbb F_q}\psi(f(x)) \bigg| \le (s-1)\sqrt{q}$.

The rest of this paper is organized as follows.
In Section 2, we prove Theorem  <ref>.
Our main idea of improving the index bound in [10] is to replace the polynomial over finite fields by using
the equivalent polynomial with the smallest index. Those equivalent polynomials are obtained  by applying Frobenius automorphisms on individual monomials.   In Section 3, as an application, we count the number of solutions of some algebraic curves by using our main result.

§ PROOF OF THEOREM 1.2 AND COROLLARIES

Let $q=p^m$ as before and  $\Bbb F_p$ be a subfield of $\Bbb F_{q}$.
Let $\pi$ be the Frobenius automorphism of $\Bbb F_{q}$ over $\Bbb F_p$, which is defined by $\pi : \Bbb F_{q} \to \Bbb F_{q} , \pi(a) = a^p$.
We note that $\pi(a) = a$ if and only if $a \in \Bbb F_p$.

Now, we are ready to give the proof of Theorem 1.2.

Proof of Theorem 1.2. We write $f(x)=a_0+a_1x+\cdots+c_nx^n$ and $\psi=\psi_1(c)$ for some nonzero $c\in \Bbb F_q$, where $\psi_1$ is the canonical additive character of $\Bbb F_q$.
Let $\Tr_{q/p}$ be the trace function from $\Bbb{F}_q$ to $\Bbb{F}_p$.
For each $v=(v_0, v_1, \ldots, v_n)\in \mathbb{Z}_m^{n+1}$,

\begin{eqnarray*} && \sum_{x\in \Bbb F_q}\psi_1(\pi^v(cf(x)))\\
&=& \sum_{x\in \Bbb F_q}\psi_1 (\pi^{v_0}(ca_0)+\pi^{v_1}(ca_1x)+\cdots+\pi^{v_n}(ca_nx^n))\\
&=& \sum_{x\in \Bbb F_q}\psi_1 ((ca_0)^{p^{v_0}}+(ca_1x)^{p^{v_1}}+\cdots+(ca_nx^n)^{p^{v_n}})\\
&=& \sum_{x\in \Bbb F_q}\zeta_p^{\Tr_{q/p}( (ca_0)^{p^{v_0}}+(ca_1x)^{p^{v_1}}+\cdots+(ca_nx^n)^{p^{v_n}})}\\
&=& \sum_{x\in \Bbb F_q}\zeta_p^{\Tr_{q/p}( ca_0+ca_1x+\cdots+ca_nx^n)}\\
&=&\sum_{x\in \Bbb F_q}\psi(f(x)).
\end{eqnarray*}

Note that $f(x)$ and $cf(x)$ have the same indices.
Taking a vector $v\in  \mathbb{Z}_m^{n+1}$ such that $f^*(x)=\pi^v(cf(x))$, the result follows from Theorem 1.1. $\square$

Using the concept of the $p$-cyclotomic cosets, for binomial polynomials, we obtain the following corollary, which is a simple version of Theorem 1.2. This also improves and corrects an error in Corollary 1.2 in [10].

Let   $f(x)=x^{n}+ax^{r}\in \Bbb F_{q}[x]$, where $a\in \Bbb F_{q}^*$ and $1\le r<n\le q-1$.  Let $C_r$ be  the $p$-cyclotomic coset modulo $q-1$ containing $r$.
Suppose that $r^*=rp^k$ for some integer $k$ with $0\le k\le m-1$ such that
\frac{q-1}{\gcd(n-r^*,q-1)} =
\mbox{min}\bigg\{\frac{q-1}{\gcd(n-j,q-1)}: j\in C_r\bigg\}.$$

Let $t=\gcd(n,r,q-1)$.  Let $\psi: \Bbb F_q \to \mathbb{C} ^*$ be a nontrivial additive character. If $x^{n-r^*}+a^{p^k}$ has a solution in  $\Bbb F_q^*$, then

\begin{equation}\bigg|\sum_{x\in \Bbb F_q}\psi(x^{n}+ax^{r})-\frac{q}{l^*}\bigg|\le (l^*-1)t\sqrt{q};\end{equation}

otherwise, we have

\begin{equation}\bigg|\sum_{x\in \Bbb F_q}\psi(x^{n}+ax^{r}) \bigg|\le l^*t\sqrt{q}.\end{equation}

By Theorem 1.2, we have
$$l^*=\mbox{min}\bigg\{\frac{q-1}{\gcd(i-j,q-1)}: i\in C_n, j\in C_r\bigg\}.$$
Suppose that $i=np^{\alpha}$ and $j=rp^{\beta}$ such that $l^*=\frac{q-1}{\gcd(i-j,q-1)}.$ Then $i-j=p^{\alpha}(n-rp^{\beta-\alpha})$; hence, using Theorem 1.2, the result follows immediately since $\gcd(p,q-1)=1$. In particular, $n_0 =1$ if there exists a solution for $x^{n-r^*} + a^{p^k}$.

In the following corollary, we present some special classes of polynomials for illustration of our main result.

Let $Q$ be the least prime factor of $q-1$,  $n=\frac{q-1}{Q}$, and $\alpha$ be a positive integer.
Let $f(x)=x^{n+p^{\alpha}}+ax\in \Bbb F_{q}[x]$, where $a\in \Bbb F_{q}^*$  and $1< n+p^{\alpha}\le q-1$.
If $x^{n}+a^{p^{\alpha}}$ has a solution  in $\Bbb F_q^*$, then

\begin{equation*}\bigg|\sum_{x\in \Bbb F_q}\psi(x^{n+p^{\alpha}}+ax)-\frac{q}{Q}\bigg|\le (Q-1)\sqrt{q};\end{equation*}

otherwise, we have

\begin{equation*}\bigg|\sum_{x\in \Bbb F_q}\psi(x^{n+p^{\alpha}}+ax) \bigg|\le Q\sqrt{q}.\end{equation*}

For each integer $i$ with $0\le i\le m-1$, $\gcd(n+p^{\alpha}-p^i,q-1)$ is a divisor of $q-1$.
Since $Q$ is the least prime factor of $q-1$, $\gcd(n,q-1)$ is the largest integer in the set $\big\{\gcd(n+p^{\alpha}-p^i,q-1):i=0,1,\ldots,m-1\big\}$. Hence, we have $l^*=Q$; thus, the result follows  from Corollary 2.1.

Let  $n = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}} \cdots p_{h}^{\alpha_{h}}$ be the prime factorization, where $p_1,\ldots, p_h$ are distinct primes and  $\alpha_i$ are positive integers for $1\le i\le h$.
We denote $\mbox{rad}(n) = p_{1} p_{2} \cdots p_{h}$ and  $v_{p_i}(n)=\alpha_i$ for $1\le i\le h$,  where $v_T$ denotes the $T$-adic valuation.

Let $p$ be an odd prime number and $n$ be  an odd positive integer such that $\gcd(n,p-1)=1$ and $2\mbox{rad}(n)=\mbox{rad}(p+1)$.
Let    $f(x)=x^{n+p}+a^{}x^{}\in \Bbb F_{p^2}[x]$, where $a\in \Bbb F_{p^2}^*$  and $1< n+p \le p^2-1$.
Let $s=\frac{p^2-1}{\gcd(n,p+1)}$.  If $x^{n}+a^{p}$ has a solution in $\Bbb F_{p^2}$, then

\begin{equation*}\bigg|\sum_{x\in \Bbb F_{p^2}}\psi(x^{n+p}+ax)-\frac{p^2}{s}\bigg|\le (s-1)p;
\end{equation*}

otherwise, we have

\begin{equation*}\bigg|\sum_{x\in \Bbb F_{p^2}}\psi(x^{n+p}+ax) \bigg|\le sp.\end{equation*}

We note that $\gcd(n+p-1,p^2-1)=1$ and $\gcd(n,p^2-1)=\gcd(n,p+1)>1$.
Hence, we have $l^*=s<l=p^2-1$.
The result thus follows immediately from Corollary 2.1.

We present more polynomials $x^n+ax^r\in \Bbb F_{p^m}[x]$ where $a\in \Bbb F_{p^m}^*$ to illustrate our main result for  small primes $p\le 5$ as listed in Tables 1-3.
In the tables, $\ast$ indicates that the bound is trivial.

to 1X[1,c]|X[1,c]|X[1,c]|X[1.5,c]|X[1.6,c]|X[1.5,c]
$m$   $n$   $r$   Weil bound    Index bound   Our bound

$4$   $13$   $4$   ${\ast}$    ${\ast}$   12

$6$   $41$   $5$   ${\ast}$    56   24

$6$   $43$   $25$   ${\ast}$    56   24

$6$   $53$   $25$   ${\ast}$    ${\ast}$   24

$8$   $57$   $12$   ${\ast}$   $ {\ast}$   80

$8$   $63$   $3$   ${\ast}$   $ {\ast}$   80

to 1X[1,c]|X[1,c]|X[1,c]|X[1.5,c]|X[1.6,c]|X[1.5,c]
$m$   $n$   $r$   Weil bound    Index bound   Our bound

$2$   $7$   $1$   ${\ast}$    ${\ast}$   6

$3$   $19$   $2$   $ {\ast}$    ${\ast}$   6$\sqrt 3$

$4$   $44$   $28$   ${\ast}$    45   18

$4$   $46$   $18$   ${\ast}$   ${\ast}$   36

$5$   $154$   $11$    ${\ast}$    ${\ast}$   18$\sqrt 3$

$6$   $107$   $9$    ${\ast}$   ${\ast}$   189

$6$   $122$   $18$    ${\ast}$     378   108

to 1X[1,c]|X[1,c]|X[1,c]|X[1.5,c]|X[1.6,c]|X[1.5,c]
$m$   $n$   $r$   Weil bound    Index bound   Our bound

$2$   $14$   $10$   ${\ast}$    ${\ast}$   20

$2$   $19$   $11$   ${\ast}$    15   10

$3$   $33$   $10$    ${\ast}$    ${\ast}$   20$\sqrt5$

$3$   $77$   $3$    ${\ast}$    ${\ast}$   10$\sqrt5$

$4$   $42$   $10$   ${\ast}$   ${\ast}$   150

$4$   $314$   $50$   ${\ast}$   ${\ast}$   100

§ AN APPLICATION

In this section, as an application of Theorem 1.2,  we give an estimation of the number of solutions  for  some algebraic curves.

Let $f(x)\in \Bbb F_{q^m}[x]$ be a polynomial and $N_{f,q^m}$ be the number of solutions $(x,y)\in \Bbb F_{q^m}^2$ of an Artin-Schreier equation $y^q-y=f(x)$. Then
$$N_{f,q^m}=\sum_{\psi_m}\sum_{x\in \Bbb F_{q^m}}\psi_m(f(x)),$$

where the outer sum runs over all additive characters $\psi$ of $\Bbb F_q$ and $\psi_m(x)=\psi(\Tr _{q^m/q}(x))$.

If $f(x)$ has degree $n$ and $\gcd(n,q)=1$, then we have the well known Weil bound:

\begin{equation} \label{WeilCurveBound}
\bigg|N_{f,q^m}-q^m\bigg|\le (q-1)(n-1)\sqrt{q^m}.
\end{equation}

By Theorem 1.2, we have the following corollary.

Let $f(x)\in \Bbb F_{q^m}[x]$ be a polynomial of degree $n$ with $\gcd(n,q)=1$. Let $N_{f,q^m}$ be the number of solutions $(x,y)\in \Bbb F_{q^m}^2$ of an Artin-Schreier equation $y^q-y=f(x)$.  Then we get

\begin{equation*}
\bigg|N_{f,q^m}-q^m-\frac{(q-1)q^mn_0}{l^*}\bigg|\le  (q-1)(l^*-n_0)\gcd\bigg(r^*,\frac{q^m-1}{l^*}\bigg)\sqrt{q^m}.
\end{equation*}

Let $f(x)=x^{13}+ax\in \Bbb F_{16^2}[x]$ with $a\in \Bbb F_{16^2}^*$. Let $N_{f,16^2}$ be the number of solutions $(x,y)\in \Bbb F_{16^2}^2$ of an Artin-Schreier equation $y^{16}-y=f(x)$.

Note that the $2$-cyclotomic coset $C_{13}$ modulo 255 is given by $C_{13}=\{13, 26, 52, 67, 104,134\}$.
By Corollary 3.1,  $l^*=\frac{255}{\gcd(52-1,255)}=5. $ Then we get

\begin{equation*}
\bigg|N_{f,16^2}-16^2\bigg|\le  15\cdot 5\cdot 16,
\end{equation*}
except  the case when $x^{51}+a$ has a solution in  $\Bbb F_{16^2}$, in which
case, we have

\begin{equation*}
\bigg|N_{f,16^2}-16^2-\frac{15\cdot16}{5}\bigg|\le  15\cdot 4\cdot 16.
\end{equation*}

By Magma program, $N_{f,16^2}=1024$ if $a^5=1$ and $N_{f,16^2}=256$  otherwise.
Despite that the above bounds are not close to the reality for $a^5 \neq 1$,   our bounds are still an improvement of  (<ref>) and the above second bound is pretty good when $a^5=1$.

The following corollary is obtained from Corollary 2.2.

Let $Q$ be the least prime factor of $q^m-1$ and $n=\frac{q^m-1}{Q}$.
Let $\alpha$ and $r$ be two positive integers, and  $f(x)=x^{n+p^{\alpha}}+ax\in \Bbb F_{q^m}[x]$, where $a\in \Bbb F_{q^m}^*$ and $1< n+p^{\alpha}\le q^m-1$.
Let $N_{f,q^m}$ be the number of solutions $(x,y)\in \Bbb F_{q^m}^2$ of an Artin-Schreier equation $y^q-y=f(x)$.  If $x^{n}+a^{p^{\alpha}}$ has a solution  in $\Bbb F_{q^m}$, then we get

\begin{equation*}\bigg|N_{f,q^m}-q^m-\frac{(q-1)q^m}{Q}\bigg|\le (q-1)(Q-1)\sqrt{q^m};\end{equation*}

otherwise, we have

\begin{equation*}\bigg|N_{f,q^m}-{q^m}\bigg|\le (q-1)Q\sqrt{q^m}.\end{equation*}

The following corollary is obtained from Proposition  1.7.

Let $s$ be an integer with $p<s<\sqrt {q^m}$ and $\gcd(s,p)=1$.  Let $f(x)=x^{sq^m/p}+ax^r\in \Bbb F_{q^m}[x]$, where $a\in \Bbb F_{q^m}^*$ and $r<s$.  Let $N_{f,q^m}$ be the number of solutions $(x,y)\in \Bbb F_{q^m}^2$ of an Artin-Schreier equation $y^q-y=f(x)$. Then

\begin{equation*}\bigg|N_{f,q^m}-{q^m}\bigg|\le (q-1)(s-1)\sqrt{q^m}.\end{equation*}

§.§ Acknowledgements

The authors thank the anonymous  reviewers for their  helpful suggestions.

[1]  Akbary, A., Ghioca, D., Wang, Q.: On permutation polynomials of prescribed shape, Finite Fields Appl. 15(2), 195-206 (2009)

[3]  Cramer, R., Xing, C.: An improvement to the Hasse-Weil bound and applications to character sums, cryptography and coding, Adv. Math. 309, 238-253 (2017)

[6]  Gillot, V.: Bounds for exponential sums over finite fields, Finite Fields Appl. 1(4), 421-436 (1995)

[7] Gillot, V., Langevin, P.:  Estimation of some exponential sum by means of $q$-degree, Glasg. Math. J. 52(2), 315-324 (2010)

[8] Li, C.: Hermitian LCD codes from cyclic codes, Des. Codes Cryptogr. 86(10), 2261-2278  (2018)

[9] Lidl, R., Niederreiter, H.: Finite Fields, Cambridge University Press, England (2008)

[10]  Wan, D.,  Wang, Q.: Index bounds for character sums of polynomials over finite fields, Des. Codes Cryptogr. 81(3), 459-468 (2016)