Given this operation $\phi$ on natural number sequences, show $\phi^3=\phi$.

Question

Given a sequence of natural numbers $f:\mathbb{N}\to\mathbb{N}$ define a new sequence $\phi f$ as follows:

$$ \phi f(n):=|\{ k\in\mathbb{N} \mid k \leq n,f(k)=f(n)\}|$$

In other words $\phi f(n)$ counts up how often $f(n)=f(k)$ for $k\leq n$. Also, we can apply $\phi$ iteratively, e.g.:

$$\begin{array}{rcl} \\ f & = & (0,&1,&0,&2,&1,&3,&0,&2,&0,&1,&...) \\ \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,&...) \\ & \vdots \end{array}$$

Notice that $\phi f=\phi^3 f$. My conjecture is thus for any sequence of natural numbers $f$, we have $\phi^{n+1} f = \phi^{n+3} f$ for all $n\in\mathbb{N}$.

Answer 1

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)=|\{i\le 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=|\{i\le n:a_i=a_{n+1}\}|$ times.

---

Another approach

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

1. $\ 1\le a_n\le\max_{i<n}a_i+1$
2. In every initial segment of $a$, the number of $x$'s is at least the number of $y$'s whenever $x\le 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$.

Answer 2

Solution in progress

For a sequence $f$ define

1. the pre-image of $f$ denoted $f^{-1}(a):=\{n\in\mathbb{N}\mid f(n)=a\}$.

2. a truncation of $f$ at $t$, denoted $f_{\leq t}$, is the sequence with the domain restricted to $\{n\in\mathbb{N}\mid n\leq t\}$.

Then by $f_{\leq t}^{-1}(n)$ denote $\{k\in\mathbb{N}\mid k\leq t,f(k)=f(n)\}$. Here is a new definition for $\phi$:

Definition 1: For any sequence $f$, define $\phi f(n) := \text{card }f_{\leq n}^{-1}(n) $

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

Definition 2: A sequence $f$ with range $\mathbb{N}$ is regular if for any truncation at $t\in\mathbb{N}$, $$\text{card }f_{\leq t}^{-1}(1)\geq\text{card }f_{\leq t}^{-1}(2)\geq\text{card }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 $t\in\mathbb{N}$ 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$.