Vtyjkyuk

Given a sequence $f$ define a new sequence $phi f$ as follows:

$$ phi f(n):=textcard kinmathbbN_leqnmid f(k)=f(n)$$

where $textcard$ is the set cardinality function. In other words $phi f(n)$ counts up how often $f(n)=f(k)$ for $kleq n$. Also, we can iteratively apply $phi$ to $f$. Here is an example:

$$beginarray \
f & = & (a,&b,&a,&c,&b,&d,&a,&c,&a,&b,&...) \
phi f & = & (1,&1,&2,&1,&2,&1,&3,&2,&4,&3,&...) \
phi^2 f & = & (1,&2,&1,&3,&2,&4,&1,&3,&1,&2,&...) \
phi^3 f & = & (1,&1,&2,&1,&2,&1,&3,&2,&4,&3,&...) \
endarray$$

Notice that $phi f=phi^3 f$, which via induction implies $phi^nf=phi^n+2f$ for all $ninmathbbN$

Conjecture : If $f$ is any sequence then $phi^n f = phi^n+2 f$ for all $ninmathbbN$.

Very nice observation.

As you note, for the conjecture it suffices to prove $phi^3=phi$.

Call sequences $a=(a_1,a_2,dots)$ and $b=(b_1,b_2,dots)$ similar, if $phi a=phi b$, i.e. for each index $n$, $ a_n$ occurs the same times among $a_1,dots,a_n $ as $ b_n$ among $b_1,dots,b_n$.

For example, the sequences $(1,1,2,2,3,3,1), (1,1,2,2,3,3,2), (1,1,2,2,3,3,3)$ are similar.

We have to show that $phi^2 a$ is similar to $a$ for an arbitrary sequence $a$.

Assume it holds for $n$ long sequences, and take $a_n+1$ in $a=(a_1,dots,a_n+1)$.

• It is either a 'new element' ($phi a(n+1)=1$), in which case the number of $1$'s that denotes the new elements, is increased by one in $phi a$, implying $phi^2 a(n+1)=|a_1,dots,a_n+1|$ which is a new element in the sequence $phi^2a$.


• Or, it is a repeating element, and $s:=phi a(n+1)=|ile n+1:a_i=a_n+1|$.
  
  This $s$ occurs in $phi a$ for exactly $q$ times, where $q$ is the number of $a_i$'s occuring exactly $s$ times in $a$. (If $s$ is new, then $q=1$, and $a_n+1$ can be replaced by any of these $a_i$'s to get a similar sequence.)
  
  On one hand, it means $phi^2 a(n+1)=q$.
  
  On the other hand, $q$ already occured in $phi^2 a(1,dots,n)$ exactly $s-1=|ile n:a_i=a_n+1|$ times.

Another approach

Call a sequence $a$ of positive integers a regular sequence, if for all $n$,

1. $ 1le a_nlemax_i<na_i+1$


2. In every initial segment of $a$, the number of $x$'s is at least the number of $y$'s whenever $xle y$.

Note that 2. can be rephrased as: if $a_n=a_i$ for some $i<n$, then $a_n$ is minimal among those sequence elements which occur exactly $(phi a)_n-1$ times in $(a_1,dots,a_n-1)$

[because $a_n$ in $(a_1,dots,a_n)$
has one more occurances than any of them].

For example, $(1,2,2)$ and $(1,2,3,2)$ are not regular, while $(1,2,1)$ and $(1,2,3,1)$ are regular.

Proposition.

$ $ a) $ phi a$ is regular for any sequence $a$.

$ $ b) $ $If $a$ is a regular sequence, then $phi^2 a=a$.

Solution in progress

For a sequence $f$ define

1. the pre-image of $f$ denoted $f^-1(a):=ninmathbbNmid f(n)=a$.




2. a truncation of $f$ at $t$, denoted $f_leq t$, is the sequence with the domain restricted to $ninmathbbNmid nleq t$.

Then by $f_leq t^-1(n)$ denote $kinmathbbNmid kleq t,f(k)=f(n)$. Here is a new definition for $phi$:

Definition 1: For any sequence $f$, define $phi f(n) := textcard f_leq n^-1(n) $

The following definition and conjecture describes the sequences that $phi$ will produce:

Definition 2: A sequence $f$ with range $mathbbN$ is regular if for any truncation at $tinmathbbN$, $$textcard f_leq
t^-1(1)geqtextcard f_leq t^-1(2)geqtextcard f_leq
t^-1(3)geq...$$

That is, for any truncation of the sequence $f$, the number of $1$s is $geq$ the number of $2$s, which is $geq$ the number of $3$s and so on, which ensures the sequence is counting properly. I am nearly certain this definition is equivalent to those in comments.

Conjecture: If $f$ is any sequence then $phi f$ is regular, and if $f$ is regular then $phi^2 f = f$.

Prove $phi f$ is regular via induction on the size of truncations and using the following lemma:

Lemma 1: A sequence $f$ is regular iff for each $tinmathbbN$ the truncated sequence $f_leq t$ is regular.

Proposition: For any sequence $f$, $phi f$ is regular.

Proof: If $t=1$, $phi f_leq 1$ is the singleton sequence, $phi f_leq 1=(1)$, so it is trivially regular.

Inductive step: Assume for any $s<t$, the truncated sequence $phi f_leq s$ is regular. Now show $phi f_leq t$ is regular by showing that for any truncation the defining inequality holds. In fact, it is sufficient to demonstrate the inequality for truncation up to length $t$.