Hecke groups, linear recurrences and Kepler limits (update 2)
Author
Barry Brent
License
Creative Commons CC BY 4.0
Abstract
Computations with the the objects mentioned in the title.
Computations with the the objects mentioned in the title.
\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}