10

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}$.

2 Answers2

3

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$.

Berci
  • 90,745
  • Currently considering "level sets" of the sequence. If the original sequence $f$ has domain $D$ then for $x\in D$ I let $E_x={n\in\mathbb{N}\mid f(n)=x}$. If you list those elements like $E_x={e_1,e_2,...}$ then $f(e_n)=n$, and $\phi f(e_n)$ is a constant, and furthermore $E_x$ is the only set which is mapped to this constant. Thus, $\phi^2 f(e_n)=f(e_n)=n$ for all $n$. –  Aug 26 '18 at 23:42
  • Yes, level sets definitely play some role here around. – Berci Aug 26 '18 at 23:46
  • Hmm.. You still have to finish the proof (of the last sentence). – Berci Aug 27 '18 at 00:32
  • I think I can prove the case for the level sets, essentially that $(1,2,3,...)\mapsto(1,1,1,...)\mapsto(1,2,3,...)$, and then a larger argument piecing them together for an arbitrary sequence. –  Aug 27 '18 at 00:52
  • You're allowed to post your own answer. What is that argument? – Berci Aug 27 '18 at 06:11
  • I think I also found another approach, updated my answer. Please verify. – Berci Aug 27 '18 at 22:02
  • I'm having a hard time understanding part 2 of definition though it seems correct. –  Aug 27 '18 at 22:42
  • In a regular sequence, a number can't repeat ($k$ times) until all smaller numbers are not repeated (at least $k$ times).. – Berci Aug 27 '18 at 22:47
  • Another reformulation of condition 2 is: if $x<y$ then $x$ occurs at least as many times as $y$ in any initial segment of the sequence. – Berci Aug 28 '18 at 07:16
  • Might this have something to do with binomial transforms? – it's a hire car baby Sep 06 '18 at 08:35
1

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$.

  • Yes, your definition 2 matches up to condition 2 in my second approach, see my last comment there. – Berci Aug 29 '18 at 07:58