Maximal entries of elements in certain matrix monoids
| Autor: | Han, Sandie, Masuda, Ariane M., Singh, Satyanand, Thiel, Johann |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Integers 20 (2020), Paper No. A31, 35 pp |
| Druh dokumentu: | Working Paper |
| Popis: | Let $L_u=\begin{bmatrix}1 & 0\\u & 1\end{bmatrix}$ and $R_v=\begin{bmatrix}1 & v\\0 & 1\end{bmatrix}$ be matrices in $SL_2(\mathbb Z)$ with $u, v\geq 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\geq 1$. By using ideas from our previous work on $(u,v)$-Calkin-Wilf trees, we extend their results for any $u, v\geq 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$. Comment: Fixed typos and added comment related to BSV, 31 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|