Skip to main content
5 of 6
Typo
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Distribution of traces and max entries of words of fixed length in $\operatorname{SL}_2(\mathbb{N})$

$\DeclareMathOperator\SL{SL}\DeclareMathOperator\tr{\mathsf{tr}}$$\SL_2(\mathbb{N})$ is a free monoid on the generators $$ L=\begin{pmatrix}1&0\\1&1\end{pmatrix},\quad R=\begin{pmatrix}1&1\\0&1\\\end{pmatrix}. $$ Let $\SL_2^{(n)}(\mathbb{N})$ designate the set of words of length $n$ in these generators. I have a couple of questions about this family that seem within reach (i.e. are already known or could be determined by the good folks of mathoverflow).

  1. What is the distribution of $\{\tr(M) : M\in \SL_2^{(n)}(\mathbb{N})\}$?
  2. What is the distribution of $\{\|M\|_{\infty} : M\in \SL_2^{(n)}(\mathbb{N})\}$?
  3. What is the joint distribution of the two quantities above?

I'd prefer to know the limiting distribution $n\to\infty$ and some useful error term (if they exist), but any non-trivial bounds are welcome, or approximations to relevant functions of the matrices as functions of the $\{L,R\}$ decomposition $$ M(w)=\prod_{i=0}^{n-1}G_{w_i}, \quad w\in\{0,1\}^n, \quad G_0=L, \quad G_1=R. $$

Here are a few pictures (of dubious quality); scatterplot on top of bar plot (could've just done a histogram but was more curious about some of the exact values).

Traces, $n=15,20,25$: trace counts for length 15 words trace counts for length 20 words trace counts for length 25 words

$L^{\infty}$, $n=15,20,25$: sup norm counts for length 15 words sup norm counts for length 20 words sup norm counts for length 25 words

Joint $n=15$ (the linear relationship seems to be $\tr(M)\approx \frac{9}{8}\|M\|_{\infty}$): Joint n = 15

yoyo
  • 609
  • 3
  • 10