Maximal entries of elements in certain matrix monoids

Abstract

Let $L_u=\left[\begin{array}{cc}1& 0\\ u& 1\end{array}\right]$ and $R_v=\left[\begin{array}{cc}1& v\\ 0& 1\end{array}\right]$ be matrices in $S{L}_2(\mathbb{Z})$ with $u,v\ge 1$. Since the monoid generated by $L_u$ and $R_v$ is free, we can associate a depth to each element based on its product representation. In the cases where $u=v=2$ and $u=v=3$, Bromberg, Shpilrain, and Vdovina determined the depth $n$ matrices containing the maximal entry for each $n\ge 1$. By using ideas from our previous work on $(u,v)$-Calkin-Wilf trees, we extend their results for any $u,v\ge 1$ and in the process we recover the Fibonacci and some Lucas sequences. As a consequence we obtain bounds which guarantee collision resistance on a family of hashing functions based on $L_u$ and $R_v$.

Fixed typos and added comment related to BSV, 31 pages

References in corpus (1)

• The (u,v)-Calkin-Wilf Forest