# Finding a non-periodic sequence with prescribed complexity.

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

• 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. – A.P. May 8 '15 at 16:47
• 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$. – Michael May 8 '15 at 17:28
• @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)$). – A.P. May 8 '15 at 17:55
• 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? – Michael May 9 '15 at 0:08
• No problem, @Michael. It is probably better if we discuss this in the chat, though. – 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.