2

It's quite easy to prove that given an application: $\sigma:[1,n]\to [1,n]$ we know that the sequence: $$Id_n,\sigma,\sigma^2,\sigma^3,\cdots,\sigma^m,\cdots $$ Is periodic after some index $k\leq n^n$

Now my question is Given two applications $\sigma_1,\sigma_2:[1,n]\to [1,n]$ can we prove a similar result for: $$Id_n,\sigma_1,\sigma_2,\sigma_1^2,\sigma_1\sigma_2,\sigma_2\sigma_1,\sigma_2^2,\cdots $$

?

The sequence is defined using the following order of indexes to multiply: $$\begin{align}0 , \color{#00a}1,\color{#00a}2, \color{#0a0}{(1,\color{#00a}1)},\color{#0a0}{(1,\color{#00a}2)},\color{#0a0}{(2,\color{#00a}1)},\color{#0a0}{(2,\color{#00a}2)},(\color{#c00}1,\color{#0a0}{1,1}),(\color{#c00}1,\color{#0a0}{1,2}),(\color{#c00}1,\color{#0a0}{2,1}),(\color{#c00}1,\color{#0a0}{2,2}),\\(\color{#c00}2,\color{#0a0}{1,1}),(\color{#c00}2,\color{#0a0}{1,2}),(\color{#c00}2,\color{#0a0}{2,1}),(\color{#c00}2,\color{#0a0}{2,2}),\cdots \end{align}$$

Elaqqad
  • 13,725
  • ...how is the second sequence defined??? It seems ambiguous to me. – JP McCarthy Apr 20 '15 at 10:59
  • Does $\sigma_1\sigma_2=\sigma_2\sigma_1$ hold? –  Apr 20 '15 at 11:10
  • I am still not seeing how to continue that sequence in an unambiguous way. – Tobias Kildetoft Apr 20 '15 at 13:24
  • This is encountered in a computer science problem, actually I want the sequence to be periodic but I don't see any reason for that to hold in general so if there are some assumptions about $\sigma_1,\sigma_2$ this would be interesting two – Elaqqad Apr 20 '15 at 13:26
  • I am still not seeing an unambiguous pattern here. – Tobias Kildetoft Apr 20 '15 at 13:30
  • What you have written is not lexicographic unless you cap the exponents at $2$. – Tobias Kildetoft Apr 20 '15 at 13:32
  • 1
    we pick first $1$-tuples we order them in lexicographic order, then $2$-tuples we order them in lexicographic order, then $3$-tuples we order them in lexicographic order, $4$-tuples we order them in lexicographic order \cdots – Elaqqad Apr 20 '15 at 13:44
  • Ahh, I see what you mean now. My guess is that it will be periodic, simply because it is systematically defined and there are only a finite number of possible elements to pick from, but I need to think a bit more for a formal argument. – Tobias Kildetoft Apr 20 '15 at 13:46

0 Answers0