Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Trace of sequence

Denote by $\mathbb{N}=\{0,1,2,...\},~$ the set of natural numbers, and by $I_{m}=\{0,1,...,m-1\}\,$ the set of natural numbers lesser than given natural number $m$. Let $c=(c_0,c_1,...,c_{m-1})\,$ a $m$-sequence of natural numbers, and $p=max\{c_0,c_1,...,c_{m-1}\},\,$ the greatest term of sequence $c$

Then the sequence

$t(c)=(t_0,t_1,...,t_p)\,$

where $t_j,j\in I_{p+1}\,$ denote number of terms of sequence $ c$ thats are equal at $j$, is called trace of $c$. It is clear that terms of trace fulfills the conditions

$t_0+t_1+...+t_p=m\,$

$t_1+2t_2+...+pt_p=c_0+c_1+...+c_{m-1}\,$

Denote by

$t^{0}(c)=c\,$

$t^{n}(c)=t(t^{n-1}(c))\,$

1.The set of sequences

$B=\{(1,0,0,1),(2,2),(0,0,2),(2,0,1),(1,1,1),(0,3)\}\,$

that is cycle of length 6 is called '''bracelet of sequences''' because for each sequence $c$ from $B$ holds

$t^6 (c)=c\,$

2.The set of sequences

$R=\{(0,1,1),(1,2)\}\,$

that is cycle of length 2 is called '''ring of sequences''' because for each sequence $c $ from $R$ holds

$t^2 (c)=c\,$

The set

$ H=B\cup R\,$ is called ''' black hole of sequences'''

Reasons for that name are because I suppose that:

Claim: For each finite sequence $a$ of natural numbers exists natural number $n$ such that $t^n(a)\in H\,$ in other words each sequence converges to $H$.

Sequence $a$ is of type $B$ if its converge to $H$ from $B$ for example sequence $(2,3)$ is of type $B$ because

$t^3((2,3))=(0,0,2)\in B\,$

And sequences that converges to $H$ from $R$ are of type $R$ for example the sequence $(0)$ is of type $R$ because

$t^6((0))=(1,2)\in R\,$

My questions are.

  1. Is my assumption true
  2. If it is true how to decide of which type is any given finite sequence of natural numbers
  3. Can be done any programme or algorithme to determine of which type is certain sequence. Thanks
share|improve this question
    
Just checking if I understand: $(6,2,1,0,0,0,1,0,0,0)$ is a fixed point, right? –  Gerry Myerson Jul 16 '11 at 5:01
    
@Gerry: No, because $p=\max\{c_0,\dots,c_{m-1}\}$, so $t((6,2,1,0,0,0,1,0,0,0))=(6,2,1,0,0,0,1)$, which is taken to $(3,2,1,0,0,0,1)$ by $t$. The orbit continues with $(3,2,1,1),(0,2,1,1),(1,2,1),$ $(0,2,1),(1,1,1)$, and we’re in $B$. –  Brian M. Scott Jul 16 '11 at 6:27
    
Ah, yes, I missed that. Thanks, Brian. –  Gerry Myerson Jul 16 '11 at 12:24
    
I would conjecture that the sequences of type $R$ are the following, and all the others are type $B$: $(0),(1),(2),(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(0,0,1),(0,1,0),(0,‌​1,1),(1,0,0),(1,0,1),(1,1,0)$. –  mac Jul 17 '11 at 8:51
1  
The conjecture I made above is correct, as can be seen by considering the tree of preimages of $(1,2)$ under $t$ (the children of a node form the set of preimages of that node, which is the set of permutations of any one preimage). There is one infinite path given by cycling through $R$, but every other path in the tree is finite since it ends in a node of the form $(c_0,\dots,c_{m-1})$ where $c_{m-1}=0$, and these have no children. The nodes of the tree are the sequences I conjectured. –  mac Jul 17 '11 at 11:29

2 Answers 2

up vote 4 down vote accepted

This is not a complete solution, but it seems to reduce the problem to an analysis of the cases $m\le2$.

I'll write $t^k$ for the $k$-fold composition of $t$ with itself, so that $t^1=t$, $t^2=t\circ t$, etc.

I'll also write $|\{c\}|$ for the number of distinct elements of the $m$-tuple $c=(c_0,c_1,\dots,c_{m-1})\in\mathbb{N}^m$.

And I'll write things like $(n,m^k,p)$ as shorthand for $(n,m,m,\dots,m,p)$ where $m$ is repeated $k$ times.

A first observation is that $t(c)=t(c')$ for any permutation $c'$ of $c$.

Lemma: $|t^2(c)|\geq |c|$ if and only if either $|\{c\}|=1$, or $|\{c\}|=2$ and $c=(a,b^{|c|-1})$ (up to permutation) where $a\ne b$.

Proof: We have $|t^2(c)|=\max\{t_0,\dots,t_p\}+1$, so $|t^2(c)|\ge |c|$ if and only if $|t^2(c)|\in \{|c|,|c|+1\}\iff \{|c|-1,|c|\}\cap \{t_0,\dots,t_p\}\ne \emptyset$, which is equivalent to the conditions above.

Claim: If $m=|c|\ge 3$ then $|t^n(c)|<|c|$ for some $n\ge1$.

Remark: This allows us to reduce to the case $m\in \{1,2\}$ to establish the claim in the question, if it's true.

Proof of the claim: this is a case-by-case analysis.

  1. If $|\{c\}|>2$ then $n=2$ will do by the lemma.

  2. If $|\{c\}|=1$, either $c=(0^m)\implies t(c)=(m)$, or $c=(1^m)\implies t(c)=(0,m)$, or $c=(2^3)\implies t^6(c)=(0,3)$, or $c=(2^m)$ where $m\ge4$, so that $t(c)=(0,0,m)$, or $c=(x^m)$ where $x\ge3$. In this case, $t(c)=(0^x,m)$, $t^2(c)=x,0^{m-1},1), t^3(c)=(m-1,1,0^{x-2},1)$, $t^4(c)=(x-2,2,0^{m-3},1)$. If $m\ge4$ or $x\ge5$ then $|\{t^4(c)\}|>2$, so $|t^4(c)|=m$ and $|t^6(c)|<m$ by the lemma. If $m=3$ and $x\in \{3,4\}$ then $t^7(c)=(0,3)$.

  3. If $|\{c\}|=2$ and $c$ is not of the form $(x,y^{m-1})$ (up to permutation) then $|t^2(c)|<|c|$ by the lemma.

  4. If $|\{c\}|=2$ and $c=(x,y^{m-1})$, suppose first that $x<y$. We have $t(c)=(0^x,1,0^{y-x-1},m-1)$ so $t^2(c)=(y-1,1,0^{m-3},1)$ and if $y\ge3$ then $t^3(c)=(m-3,2,0^{y-3},1)$, so if $m>3$ then $|t^4(c)|=\max\{m-3,2\}+1=\max\{m-2,3\}<m$, whereas if $m=3=y$ then checking the three possibilities $c=(x,3,3)$ for $x\in \{0,1,2\}$ gives $t^{11}(c)=(0,3)$, and if $m=3<y$ then $t^4(c)=t(0,2,0^{y-3},1)=(y-2,1,1)$ so $t^5(c)=(0,1,0^{y-4},1), t^6(c)=(y-3,1,1),\dots, t^{2(y-1)}(c)=(1,1,1), t^{2y-1}(c)=(0,3)$. If $y\in \{1,2\}$ then $|t^3(c)|=2$. If $c=(x,y^{m-1})$ where $x>y$ then $t(c)$ is a permutation of $t(y,x^{m-1})$, so the previous argument applies.

share|improve this answer
    
There’s a small error in (4): if $c=(1,3,3)$, $m=y=3$, but $|t^4(c)|=|(1,1,1)|=3\not <m$. In the subcase $y\ge 3$ you should have $|t^4(c)|=\max\{m-2,3\}$. You’re fine if $m>3$ or if $m=y=3$ (when $t^5(c)=(0,3)$). If $m=3<y$, $t^4(c)=(y-2,1,1)$, and you can use the fact that $t^2((n,1,1))=$ $(n-1,1,1)$ for $n\ge 2$ to reduce it eventually to $(0,3)$. –  Brian M. Scott Jul 16 '11 at 17:38
    
In the section 4. If $|\{c\}=2$ you obviously mean $|\{c\}|=2 $. Nice attempt to complete proof –  Adi Dani Jul 16 '11 at 19:30
    
@Brian: thanks! I've tried to fix things up as you suggested. –  mac Jul 17 '11 at 1:10

Following on from mac’s partial answer, the assumption is true for $m \in \{1,2\}$, so it appears to be true in general.

If $m=1$, $c=(x)$ for some $x \in \mathbb{N}$. If $x>0$, $t(c) = (0^x,1)$, and either $x=1$, in which case $t^2(c) = (0,2), t^3(c) = (1,0,1)$, and $t^4(c) = (1,2) \in R$. If $x=0$, $t(c) = (1)$, and we’re in the first case.

Now let $m=2$ and $c = (x,y)$. Observation: If $n>2$, $t^2((n,2)) = (n-1,2)$, while $t((2,2)) = (0,0,2) \in B$, so $t^{1+2(n-2)}((n,2)) = t^{2n-3}((n,2)) \in B$ whenever $n \ge 2$.

If $x=y \in \{0,1\}$, $t(c) = (0^x,2),t^2(c) = (x,0,1)$, and $t^4(c) = (0,1,1) \in R$.

If $x=y>1$, $t(c) = (0^x,2),t^2(c) = (x,0,1),t^3(c) = (1,1,0^{x-2},1)$, and $t^4(c) = (x-2,3)$.

If $x=y=2$, $t^4(c) \in B$; if $x=y \in \{3,4\}$, $t^6(c) = (2,2) \in B$; and if $x=y=5$, $t^{10}(c) = (2,2) \in B$.

If $x=y>5$, $t^5(c) = (0,0,0,1,0^{x-6},1)$, and $t^6(c) = (x-3,2)$, where $x-3>2$, whence $t^{6+2(x-3)-3}(c) = t^{2x-3}(c) \in B$ by the Observation.

Now assume without loss of generality that $x<y$; then $t(c) = (0^x,1,0^{y-x-1},1)$, and $t^2(c) = (y-1,2)$, which is in $R$ if $y=2$. If $y=1$, $t^4(c) = (1,2) \in R$. And if $y \ge 3$, the Observation ensures that $t^{2+2(y-1)-3}(c) = t^{2y-3}(c) \in B$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.