Let $\mathbf{a}$ be a sequence on a finite alphabet (i.e. set) $\mathcal{A}$. The complexity function of $\mathbf{a}$ is the number $p_{\mathbf{a}}(n)$ of distinct blocks of $n$ symbols (of $\mathcal{A}$) which appear in $\mathbf{a}$.

Now fix a finite alphabet $\mathcal{A}$ and a (real) constant $c \geq 2$. Can we always find a non-ultimately periodic sequence $\mathbf{a}$ on $\mathcal{A}$ such that $$ p_{\mathbf{a}}(n) \leq \kappa n \quad \text{for infinitely many integers} \quad n \geq 1 $$ for some constant $\kappa \geq c$ but $$ p_{\mathbf{a}}(n) \leq \tau n \quad \text{for at most finitely many integers} \quad n \geq 1 $$ for every $2 \leq \tau < c$?

  • $\begingroup$ I suppose that the answer is affirmative, but I really have no clue about tackling this problem. Also, any suggestion for better tags is welcome. $\endgroup$ – A.P. May 8 '15 at 16:47
  • $\begingroup$ Saying "non-ultimately periodic" suggests that it can be done with sequences that are periodic, or eventually periodic, but that does not seem true. A sequence that is periodic with period $d$ seems to have $p_a(n) \leq d$ for all $n$. A sequence that has transient $T$ and then becomes periodic with period $d$ has $p_a(n) \leq T+d$ for all $n$. $\endgroup$ – Michael May 8 '15 at 17:28
  • $\begingroup$ @Michael I didn't think about that. I required $\mathbf{a}$ non-ultimately periodic because an ultimately periodic sequence is not enough for my application ($\beta$-expansions of algebraic numbers not in $\Bbb{Q}(\beta)$). $\endgroup$ – A.P. May 8 '15 at 17:55
  • $\begingroup$ Dear A.P. , I'm just curious about the application (though I do not know what a "$\beta$-expansion" is, or what "$\mathbb{Q}(\beta)$" means). Would you be able to provide some more explanation of this? $\endgroup$ – Michael May 9 '15 at 0:08
  • $\begingroup$ No problem, @Michael. It is probably better if we discuss this in the chat, though. $\endgroup$ – A.P. May 9 '15 at 9:22

Yes. For simplicity, let us suppose $c$ is an integer and $\mathcal{A}$ has at least $c+1$ distinct elements. Without loss of generality assume we use elements labeled $\{0, 1, 2, 3, \ldots, c\}$.

Write the sequence in frames by listing out elements $1, ..., c$ in order, but on frame $k$ have these separated by $2^{k-1}$ zeros:

\begin{align} \mbox{frame 1: } & 010203...0c\\ \mbox{frame 2: } & 001002003...00c\\ \mbox{frame 3: } & 000010000200003...0000c \end{align} and so on. Once we fix a positive integer $n$, all but a finite number of frames will have the nonzero elements of the sequence separated by more than $n$ zeros. So for an infinite number of frames we get sequences of the form:

100000, 0100000, 0010000

200000, 0200000, 0020000


c00000, 0c00000, 00c0000

There are exactly $cn$ of these. We also get the all-zero sequence 000000. We also get some additional sequences due to the "transient" in small frames. Let $T_a(n)$ be the number due to the transient. Then: $$ p_a(n) = cn + 1 + T_a(n) $$

Then clearly $p_a(n) \geq cn$ for all $n$ (so your second condition about "at most finitely many $n$" holds). But $T_a(n)$ is at most linear in $n$, so your first condition also holds.

To show $T_a(n)$ is at most linear in $n$: Once we get to a frame where non-zero elements are separated by more than $n$ zeros, the transient is finished. Also, $T_a(n)$ is at most the total size of the transient. Let's just add up the sizes of each frame:

-Frame 1 has $(1+1)c$ symbols.

-Frame 2 has $(2+1)c$ symbols.


-Frame $k$ has $(2^{k-1}+1)c$ symbols.

So the total number of symbols in $k$ frames is $\sum_{i=1}^k c(2^{i-1}+1) = c(k-1+2^k)$. We stop once $2^k > n$. So the number of symbols in the transient is at most $\approx c(\log_2(n) + 2n)$. Overall, $T_a(n)$ is at most linear in $n$.

I think something similar can be done if $\mathcal{A}$ has just two elements by using binary to represent $c+1$ different things.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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