Computations with the the objects mentioned in the title.
\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
\documentclass{article}
\usepackage[normalem]{ulem}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{thmtools}
\declaretheoremstyle[headfont=\normalfont]{normalhead}
\usepackage{color}
\usepackage{graphicx}
\usepackage{morefloats}
\usepackage{hyperref}
\usepackage{ amssymb }
\usepackage{textcomp}
% * <barry314159@gmail.com> 2018-12-11T05:24:58.850Z:
%
% ^.
\usepackage{url}
\usepackage{float}
\usepackage{biblatex}
\addbibresource{hecke.bib}
\newtheoremstyle{mydef}
{\topsep}{\topsep}%
{}{}%
{\itshape}{}
{\newline}
{%
\rule{\textwidth}{0.0pt}\\*%
\thmname{#1}~\thmnumber{#2}\thmnote{\-\ #3}.\\*[-1.5ex]%
\rule{\textwidth}{0.0pt}}%
\begin{document}
\theoremstyle{mydef}
\newtheorem{conjecture}{Conjecture}
\newtheorem{theorem}{Theorem}
\newtheorem{question}{Question}
\newtheorem{remark}{Remark}
\newtheorem{proposal}{Proposal}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{observation}{Observation}
\author{Barry Brent}
\date{24m 9h 22 February 2019}
\title{Hecke groups, linear recurrences, and Kepler limits}
\maketitle
\begin{abstract}
\hskip -.2in
\noindent
We study the linear fractional
transformations in
the Hecke group $G(\Phi)$
where $\Phi$ is either root
of $x^2 - x -1$
(the larger root being
the ``golden ratio''
$\phi = 2 \cos \frac {\pi}5$.)
Let $g \in G(\Phi)$ and let $z$ be
a generic element of the upper half-plane.
Exploiting the fact that
$\Phi^2 = \Phi -1$,
we find that
$g(z)$ is a quotient of linear
polynomials in $z$
such that
the coefficients
of $z^1$ and $z^0$
in the numerator and denominator of
$g(z)$
appear themselves to be linear polynomials
in $\Phi$ with coefficients
that are certain multiples of Fibonacci numbers.
We make somewhat less
detailed observations
along similar lines
about the functions
in $G(2 \cos \frac {\pi}k)$
for $k \geq 5$.
\end{abstract}
\section{Introduction}
Let $G(\lambda)$ be the
Hecke group
generated by
the linear fractional transformations
$S \colon z \mapsto -1/z$ and
$T_{\lambda} \colon z \mapsto z + \lambda$
and let $G_k = G(2 \cos \frac {\pi}k)$.
This article describes numerical experiments
carried out
to study Hecke groups,
mainly
$G_k$ for $k \geq 5$.
In this article, an $n$-tuple of symbols
$$\overrightarrow{w} = \{w_1, w_2, w_3, ..., w_n\}$$
representing an ordered set of integers
is called a \it word \rm on $\bf{Z}$
and we write $n = |\overrightarrow{w}|$.
A typical
element of $G(\lambda)$
takes the form
$$T_{\lambda}^{w_1}ST_{\lambda}^{w_2}S ... S
T_{\lambda}^{w_n} =
\text{(say) } g_{_{\small{\lambda}};
_{\small{\overrightarrow{w}}}}.$$
\noindent
This representation is not unique.
For example,
a function
$g \in G(\lambda)$
can be described by a word
of length $n$ for
arbitrarily large $n$,
because
any word representing $g$
can be padded with
zeros and the resulting word will
also represent $g$. Consequently, when
studying all $g$ represented by words
$\overrightarrow{w}$
with $|\overrightarrow{w}| \leq N$,
we can restrict attention to
the words satisfying
$|\overrightarrow{w}| = N$.
\newline \newline
\noindent
Let $\phi, \phi^* $,
represent the larger and smaller roots of $x^2 - x - 1$,
respectively.
The problem of expressing
(for $g \in G_5)$
$g = g_{_{\small{\phi}};_{\small{\overrightarrow{w}}}}$
in terms of the $w_i$
was raised by Leo in \cite{leo2008fourier}
and discussed by his student Sherkat in
\cite{sherkat2007investigation};
the first purpose of this article is to
write down conjectures addressing this question.
Our calculations indicate that,
for arbitrary $\lambda, z \in \bf{C}$,
$g_{_{\small{\lambda}};_{\small{\overrightarrow{w}}}}(z)$
is a rational function of $z$ and $\lambda$ in
polynomials of
$\lambda$-degree
$\leq k$. Here are the first few:
$$g_{\small{\lambda};\{w_1\}}(z) =
\frac{1\cdot z + w_1 \lambda}{0 \cdot z + 1},
$$
$$
g_{\small{\lambda};\{w_1,w_2\}}(z) =
\frac{w_1 \lambda \cdot z + w_1 w_2 \lambda^2 - 1}
{1 \cdot z +w_2 \lambda},
$$
and
$$
g_{\small{\lambda};\{w_1,w_2,w_3\}}(z) =
\frac{(w_1 w_2\lambda^2 - 1) \cdot z +
w_1 w_2 w_3 \lambda^3 - (w_1 + w_3)\lambda}
{w_2 \lambda \cdot z + w_2 w_3 \lambda^2 -1}.
$$
\noindent
Following \cite{sherkat2007investigation},
we simplify the above expressions for
$g_{_{\small{\lambda}};_{\small{\overrightarrow{w}}}}$
when
$\lambda = \phi$ or $\phi^*$
by repeatedly making the substitution
$\Phi^2 = \Phi + 1 (\Phi = \phi$ or $\phi^*$.)
The coefficients in
$g_{_{\small{\Phi};_{\small{\overrightarrow{w}}}}}$
become linear polynomials
in $\Phi$:
\newline \newline
$$g_{\small{\Phi};\{w_1\}}(z) =\frac{1 \cdot z
+ w_1 \Phi}{0 \cdot z + 1},
$$
$$g_{\small{\Phi};\{w_1,w_2\}}(z) =
\frac{w_1 \Phi \cdot z + w_1 w_2 \Phi + w_1 w_2 - 1}
{1\cdot z +w_2 \Phi},
$$
and
$$g_{\small{\Phi};\{w_1,w_2,w_3\}}(z) = $$
$$\frac{(w_1 w_2\Phi + w_1 w_2 - 1) \cdot z
+ (2w_1 w_2 w_3 -w_1 - w_3) \Phi +
w_1 w_2 w_3}
{w_2 \Phi \cdot z + w_2 w_3 \Phi + w_2 w_3 -1}.
$$
\noindent
Further calculations suggest that
the coefficients of $\Phi^1$ and $\Phi^0$ in
these expressions are always
a linear combinations of first-degree monomials
$h$
in the $w_i$ such that
the numerical coefficient
of $h$ is $\pm 1$ times a Fibonacci number
determined by the total degree of $h$;
details are in the next section.
\newline \newline\noindent
It is well known, of course, that the
consecutive ratios $F_n/F_{n-1}$
of Fibonacci numbers
converge to $\phi$.
More generally,
the limit of the ratios of
consecutive elements of a linear recurrence $L$,
when it exists, is called by Fiorenza and Vincenzi
the \it Kepler limit \rm of $L$.
Certain roots of other
polynomials than $x^2 - x -1$ are also Kepler limits
\cite{fiorenza2013fibonacci,fiorenza2011limit},
so we are led to consider
the possibility that the $G_5$ phenomenon generalizes;
our observations tend to confirm this guess.
Section 2 describes what we found
out about $G_5$,
section 3 describes less detailed observations for
$G_k, 5 \leq k \leq 33$,
and the final section provides some detail about
our numerical experiments;
documentation in the form of \it Mathematica \rm
notebooks is here \cite{Br}.
\newline \newline \noindent
We
state merely
empirical claims in
this article.
When we say we have observed convergence
of a sequence $s_n$ (say)
to a limit $S$, we mean that
our plots of $1000$
values of $\log |S-s_n|$ are
apparently linear, with negative slope.
We relied on our eyesight in this matter:
we did not fit our data to curves with
a statistical package. Interested readers are
invited to inspect the plots
on our ResearchGate pages \cite{Br}.
\newline \newline \noindent
In the following section our observations
were made on words
in $W$ of length $20$,
and those in the last secton
tested words of length $25$.
This means that we have in fact
tested the claims
on all shorter words as well.
\newline \newline \noindent
In our tests, we identified
functions in the $G_k$ with
their matrix representations:
A function
$$T_{\lambda}^{w_1}ST_{\lambda}^{w_2}S ... S
T_{\lambda}^{w_n}$$
was identified
with the corresponding matrix product.
\newline \newline \noindent
More information about the
Hecke groups is available,
for example,
in \cite{berndt2008hecke}.
\begin{remark} \rm
The book \cite{khovanskii1963application}
by Khovanskii
apparently describes another method for
approximating roots
of polynomials
using convergent sequences
of ratios of elements
of numerical sequences; but these
sequences are not linear recurrences.
(We have
not seen \cite{khovanskii1963application},
but Khovanskii's's method
is described in \cite{mc2005some}, where
the book is cited.)
\end{remark}
\section{The group \texorpdfstring{$G_5$}{TEXT}}
We make the following definitions.
\newline\newline\noindent
1. The Fibonacci numbers are defined with the convention that
$F_0 = 0, F_1 = F_2 = 1$, \it etc. \rm It will be convenient
to write $F_{-1} = 1$ as well in contexts where (see below)
$\overrightarrow{s} = \emptyset$.
\newline\newline\noindent
2. $\chi$ is the following Dirichlet character:
\[
\chi(n) =
\left\{
\begin{array}{cl}
0 & \mbox{if $n \equiv 0 \pmod{4}$,}\\
1 & \mbox{if $n \equiv 1 \pmod{4}$,}\\
0 & \mbox{if $n \equiv 2 \pmod{4}$,}\\
-1 & \mbox{if $n \equiv 3 \pmod{4}.$}\\
\end{array}
\right.
\]
Alternatively, with $(a|b)$ representing
the Kronecker symbol,
$\chi(n) = (n|2)$ if
$n \equiv 0, 1, 2, 3, 4$ or $6$ $\pmod{8}$,
and $\chi(n) = -(n|2)$ otherwise.
\newline\newline\noindent
3. $W$ is the set of words $\overrightarrow{w}$ on $\bf{Z}$.
The empty word $\overrightarrow{\emptyset}$
verifies
$\overrightarrow{\emptyset} \in W$
and $\overrightarrow{\emptyset} \subset \overrightarrow{w}$
for any $\overrightarrow{w} \in W$.
\newline\newline\noindent
4. We write the
cardinal number of a set $\sigma$
as $|\sigma|$.
We apply the same notation to words $\overrightarrow{w} \in W$.
We write $|\overrightarrow{\emptyset}| = 0$.
\newline\newline\noindent
5. (a) For
$\overrightarrow{w} \in W, \overrightarrow{w}
\neq \overrightarrow{\emptyset}$,
let
$\overrightarrow{s} = \{w_{j_1}, w_{j_2}, ..., w_{j_m}\}
\subset \overrightarrow{w} = \{w_1, ..., w_n \}$.
If all of the $j_m \equiv m \pmod{2}$,
\newline\newline\noindent
then we write
$$\overrightarrow{s} \ll _1 \overrightarrow{w}.$$
We also write
$\overrightarrow{\emptyset} \ll _1 \overrightarrow{w}$.
\newline\newline\noindent
(b) If
$\overrightarrow{s} \ll _1 \overrightarrow{w}$
and
$|\overrightarrow{s}| > 1$,
we write $$\overrightarrow{s} \ll _2 \overrightarrow{w}.$$
\noindent
(c) Let $\overrightarrow{s}, \overrightarrow{w}$ be as
in definition 5a,
except that all of the $j_m$ satisfy
$j_m \equiv m - 1 \pmod{2}$.
Then we write $$\overrightarrow{s} \ll _3 \overrightarrow{w}.$$
We also write
$\overrightarrow{\emptyset} \ll _3 \overrightarrow{w}$.
\newline\newline\noindent
(d) If
$\overrightarrow{s} \ll _3 \overrightarrow{w}$
and $|\overrightarrow{s}| > 1$,
we write $\overrightarrow{s} \ll _4 \overrightarrow{w}$.
\newline\newline\noindent
6. (a) For
$\overrightarrow{w} \in W$, the formal product
$$m_{\small{\overrightarrow{w}}} =
\prod_{w_i \in \small{\overrightarrow{w}}} w_i .$$
We also write
$$m_{\small{\overrightarrow{\emptyset}}} = 1.$$
\newline\newline\noindent
(b) $M_{\overrightarrow{w}}$ is the set of all
linear combinations with coefficients in the integers
of monomials $m_{\small{\overrightarrow{s}}}$
such that $\overrightarrow{s} \subset \overrightarrow{w}$.
\newline\newline\noindent
(c) $M$ is the union of the $M_{\overrightarrow{w}}$
as $\overrightarrow{w}$ ranges over $W$.
\begin{remark} \rm
In view of the identities $\Phi^2 = \Phi + 1$
for $\Phi = \phi$ or $\phi^*$,
it is clear that
\newline\newline\noindent
(i) For each $1 \leq j \leq 8$, there is a function
$f_j \colon W \rightarrow M$ such that
$f_j(\overrightarrow{w}) \in M_{\small{\overrightarrow{w}}}$
and,
for all $g_{_{\small{\Phi};
_{\small{\overrightarrow{w}}}}} \in G(\Phi)$ and
$\Im z > 0$,
$$g_{_{\small{\Phi};_{\small{\overrightarrow{w}}}}} (z) =
\frac{(f_1(\small{\overrightarrow{w}})
\Phi + f_2(\small{\overrightarrow{w}})) z
+
f_3(\small{\overrightarrow{w}})\Phi +f_4(\small{\overrightarrow{w}})
}{(f_5(\small{\overrightarrow{w}})
\Phi + f_6(\small{\overrightarrow{w}})) z
+
f_7(\small{\overrightarrow{w}})\Phi +
f_8(\small{\overrightarrow{w}})}.
$$
Referring to the introduction, for example:
$$
f_3(w_1, w_2, w_3) =
2w_1 w_2 w_3 -w_1 - w_3
$$
and
$$f_6(w_1, w_2, w_3) = 0.$$
\noindent
(ii) For each $1 \leq j \leq 8$,
there is a function
$\nu_j \colon W \times W \mapsto \bf{Z}$
determined by the condition
$$f_j(\small{\overrightarrow{w}}) =
\sum_{\overrightarrow{s} \subset \overrightarrow{w}}
\nu_j(\small{\overrightarrow{s}},\overrightarrow{w})
m_{\small{\overrightarrow{s}}}.$$
\end{remark}
\noindent
The following observations
describe the
functions represented by words of length $\leq 20$
in $G_k, 5 \leq k \leq 50$.
\begin{observation}
(i)
\[
\nu_1(\small{\overrightarrow{s}},\overrightarrow{w}) =
\left\{
\begin{array}{cl}
\chi(|\overrightarrow{w}| - |\overrightarrow{s}|)
F_{|\overrightarrow{s}| }
& \mbox{if $\overrightarrow{s} \ll_1 \overrightarrow{w}$,}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]
(ii)
\[
\nu_2(\small{\overrightarrow{s}},\overrightarrow{w}) =
\left\{
\begin{array}{cl}
\chi(|\overrightarrow{w}| - |\overrightarrow{s}|)
F_{|\overrightarrow{s}| -1}
& \mbox{if $\overrightarrow{s} \ll_1 \overrightarrow{w}$,}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]
(iii)
\[
\nu_3(\small{\overrightarrow{s}},\overrightarrow{w}) =
\left\{
\begin{array}{cl}
-\chi(|\overrightarrow{w}| - |\overrightarrow{s}|-1)
F_{|\overrightarrow{s}|}
& \mbox{if $\overrightarrow{s} \ll_1 \overrightarrow{w}$,}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]
(iv)
\[
\nu_4(\small{\overrightarrow{s}},\overrightarrow{w}) =
\left\{
\begin{array}{cl}
-\chi(|\overrightarrow{w}| - |\overrightarrow{s}|-1)
F_{|\overrightarrow{s}|-1 }
& \mbox{if $\overrightarrow{s} \ll_2 \overrightarrow{w}$,}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]
(v)
\[
\nu_5(\small{\overrightarrow{s}},\overrightarrow{w}) =
\left\{
\begin{array}{cl}
\chi(|\overrightarrow{w}| - |\overrightarrow{s}| - 1)
F_{|\overrightarrow{s}|-1 }
& \mbox{if $\overrightarrow{s} \ll_3 \overrightarrow{w}$,}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]
(vi)
\[
\nu_6(\small{\overrightarrow{s}},\overrightarrow{w}) =
\left\{
\begin{array}{cl}
\chi(|\overrightarrow{w}| - |\overrightarrow{s}| - 1)
F_{|\overrightarrow{s}|-1 }
& \mbox{if $\overrightarrow{s} \ll_4 \overrightarrow{w}$,}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]
(vii)
\[
\nu_7(\small{\overrightarrow{s}},\overrightarrow{w}) =
\left\{
\begin{array}{cl}
\chi(|\overrightarrow{w}| - |\overrightarrow{s}|)
F_{|\overrightarrow{s}|}
& \mbox{if $\overrightarrow{s} \ll_3 \overrightarrow{w}$,}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]
(viii)
\[
\nu_8(\small{\overrightarrow{s}},\overrightarrow{w}) =
\left\{
\begin{array}{cl}
\chi(|\overrightarrow{w}| - |\overrightarrow{s}|)
F_{|\overrightarrow{s} | - 1}
& \mbox{if $\overrightarrow{s} \ll_3 \overrightarrow{w}$,}\\
0 & \mbox{otherwise.}
\end{array}
\right.
\]
\end{observation}
\section{Higher-order Hecke groups}
Definition:
let $t(x)$ be a polynomial
$ \sum_{j=0}^d a_j x^j$
and
$\gamma(t) : = \gcd \{j $ s.t. $a_j \neq 0\} $.
If $\gamma(t) = 1$,
we say that $t$ is \it stable \rm.
Whether or not $t$
is stable, we associate to it
the family of $d^{th}$-order linear recurrences
$\Lambda_{t}$
with kernel
$\{-a_{d-1}, -a_{d-2}, ..., -a_0 \}$.
Let $\lambda = 2 \cos \frac{\pi}k$
with
minimal polynomial
$p_{\lambda}$.
Under certain conditions
\cite{fiorenza2013fibonacci,fiorenza2011limit},
a
root $x = \kappa_{\lambda}$ of $p_{\lambda}(x)$
is the Kepler limit of one of the
$L_{\lambda} \in \Lambda_{p_{\lambda} }$.
The elements
of $G(\lambda) = G_k$
have the form
\begin{equation}
g_{_{\small{\lambda};_{\small{\overrightarrow{w}}}}} (z)
= \frac{(\sum_{j=0}^{d-1} f_{\lambda,1,j}
(\small{\overrightarrow{w}})\lambda^j)\cdot z
+ \sum_{j=0}^{d-1}
f_{\lambda,2,j}(\small{\overrightarrow{w}})\lambda^j
}{(\sum_{j=0}^{d-1} f_{\lambda,3,j}(\small{\overrightarrow{w}})\lambda^j)\cdot z
+ \sum_{j=0}^{d-1} f_{\lambda,4,j}(\small{\overrightarrow{w}})\lambda^j}
\end{equation}
(Equation (1)
is clear, as in the $G_5$ case, by substitution.)
\newline \newline \noindent
For pragmatic reasons, we restricted
our attention to
$f = f_{\lambda,1,0}$ in the
following observations.
\begin{observation}
For $5 \leq k \leq 500,
\gamma(p_{\lambda}) = 1$ if $k$ is odd,
$\gamma(p_{\lambda}) = 2$ if $k$ is even.
\end{observation}
\begin{observation}
Let $5 \leq k \leq 33$.
\newline \newline \noindent
(a) There is a function
$\nu^{(k)} \colon W \times W \mapsto \bf{Z}$
such that
\begin{equation}
f(\small{\overrightarrow{w}}) =
\sum_{\overrightarrow{s} \subset \overrightarrow{w}}
\nu^{(k)}(\small{\overrightarrow{s}},\overrightarrow{w})
m_{\small{\overrightarrow{s}}}.
\end{equation}
and
\begin{equation}
\overrightarrow{s_1}, \overrightarrow{s_2} \subset \overrightarrow{w} \text{ and }
|\overrightarrow{s_1}| = |\overrightarrow{s_2}| \Rightarrow
|\nu^{(k)}(\small{\overrightarrow{s_1}},\overrightarrow{w})| =
|\nu^{(k)}(\small{\overrightarrow{s_2}},\overrightarrow{w})|
\end{equation}
for all $\overrightarrow{w} \in W$
s.t. $|\overrightarrow{w}| = 25$.
\newline \newline \noindent
(b) If $k$ is odd, then for some particular
$L_{\lambda} \in \Lambda_{\lambda}$
and all
$\small{\overrightarrow{s}} \subset \overrightarrow{w}$
s.t. $|\overrightarrow{w}| = 25$:
\newline \newline \noindent
(b1) $|\nu^{(k)}(\small{\overrightarrow{s}},
\overrightarrow{w})| \in L_{\lambda}$ and
(b2) $\kappa_{\lambda} = \lambda$.
\newline \newline \noindent
(In our experiments the sum on the r.h.s. of
equation (2) typically contains over $6 \times 10^4$
terms, but twelve or fewer distinct values
of $|\nu^{(k)}(\small{\overrightarrow{s}},\overrightarrow{w})|$.)
\newline \newline \noindent
(c) Suppose $6 \leq k \leq 32$ is even but $k \neq 14, 22$ or $26$.
Then
\newline \newline \noindent
(c1) clause (b1) still holds,
but (b2) does not; in this situation,
we found no $L_{\lambda}$ for
which $\kappa_{\lambda}$ exists.
(By design, our searches stopped with the
first instance of $L_{\lambda}$
satisfying (a), so this is
far from decisive.)
\newline \newline \noindent
(c2) For $k = 8, 10, 16, 18$, and $32$,
the ratios of
odd- and even-index members
of the $L_{\lambda}$ we found
form convergent sub-sequences with different limits.
\newline \newline \noindent
(c3) For $k = 6, 12, 20, 24, 28$, and $30$, the
$L_{\lambda}$ terminate in a sequence in which
alternate members are zero, so that the
requisite ratios are alternately zero or
undefined.
\newline \newline \noindent
(d) Suppose $k =
12, 20, 24, 28$, or $30$.
After a substitution
$y = x^2$, $p_{\lambda}(x)$ is
transformed to a stable polynomial
$q_{\lambda^2}(y)$ (say),
and then
$\lambda^2$
is the Kepler limit of
a linear recurrence in
$\Lambda_{q_{\lambda^2}}$.
\newline \newline \noindent
(e) For $k = 14, 22$, or $26$, we did not find
$L_{\lambda}$
satisfying clause (a).
Again (because
we do not have
a theoretical reason to rule out
the
existence of such linear recurrences)
this is not decisive.
\end{observation}
\noindent
The conditions on polynomials $p$
under which a linear recurrence
can be attached to $p$
with a Kepler limit that is killed by $p$
were established in
\cite{poincare1885equations}
(cited in \cite{fiorenza2013fibonacci}).
\newline \newline \noindent
A procedure (which can be invoked
from computer algebra systems)
for computing
$p_{\lambda}$
for $\lambda = 2 \cos \frac{\pi}k$
one at a time
for individual $k$
has appeared in
\cite{bayad2012minimal};
some information about the constant terms,
in
\cite{adiga2016constant}; and,
about the
degree, in \cite{lehmer1933note}.
\printbibliography
\end{document}