3
$\begingroup$

I am thinking a problem: given a subshift of finte type of $\{0,1\}^{\mathbb{N}}$ and $2>q>1$, where $q$ is a real number. Then how can we find the largest and smallest numbers of the projection of this subshift of finite type in base $q$. We know that the projection of the subshift of finite type in base $q$ is a graph-directed self-similar sets. Hence, the problem is that how can we find the extreme points of this set. Here, we only think one-dimensional graph-directed self-similar sets.

The largest and smallest numbers exist as SFT is closed and the projection is compact.

$\endgroup$
2
  • 2
    $\begingroup$ What you mean is $\max (\min) \{\sum_{n=1}^\infty a_nq^{-n}\mid (a_1,\dots)\in S\}$, where $S$ is your subshift, am I right? (And, I presume, $1<q<2$?) $\endgroup$ Nov 19, 2014 at 20:36
  • $\begingroup$ Yes. You can suppose that $1<q<2$. In fact we can assume $q>1$. As we all known, subshift of finte type is closed, hence the projection(as you mentioned above) is also compact. Therefore, we have the largest and the smallest numbers. I want to find these two numbers. $\endgroup$
    – Ben Ben
    Nov 20, 2014 at 9:12

2 Answers 2

2
$\begingroup$

It's a rational point for each $q$. Suppose the SFT has forbidden words of length at most $\ell$. Then given your current symbol and $\ell-1$ previous symbols, you can decide what symbol to put to maximize(minimize) your projection going forward. This means that your point is eventually periodic with period at most $2^\ell$.

$\endgroup$
4
  • $\begingroup$ Thanks. Anthony Quas. I think it is not easy to determine the maximal and minimal symbol as for some cases in the first step you pick the largest symbol in the sense of value, but for the next step, you may find the smallest. Moreover, the length of the symbol is not the same. I think this problem is not easy, even for the self-similar sets(one dimensional case), you may not find the extreme points easily, let alone the graph-directed self-similar sets. $\endgroup$
    – Ben Ben
    Nov 20, 2014 at 9:17
  • $\begingroup$ Are you sure about that, Anthony? If $q\ge2$, I agree - we are talking about just the lexicographically largest and smallest infinite 0-1 words (and these are probably periodic, indeed). But if $q\in(1,2)$, then it is not necessarily true that given $a_1\dots a_{n-1}$, choosing $a_n=1$ over $0$ will always yield the larger $q$-expansion. In particular, if $q$ is transcendental, I see no reason why the answer should be rational. $\endgroup$ Nov 20, 2014 at 12:11
  • $\begingroup$ @Nikita: Yes I am sure. Write $f(a_1,\ldots,a_{n-1})$ for the maximum value of $\sum_{k\ge n}x_kq^{-k}$ over all sequences $(x_k)_{k=n}^\infty$ that are compatible with $a_1,\ldots,a_{n-1}$. The maximum occurs somewhere (maybe with ties). Define $G(a_1,\ldots,a_{n-1})$ to be the word $a_2\ldots a_{n-1}x_n$ where $x_n$ is the first letter of one of the infinite words achieving the maximum. The point is that $f(a_1,\ldots,a_{n-1})=x_nq^{-n}+(1/q)f(G(a_1,\ldots,a_{n-1}))$. This makes use of the specific form of the `projection'. $\endgroup$ Nov 21, 2014 at 17:53
  • $\begingroup$ Thank you very much. Anthony. Motivated by your idea I have another elegant approach to find the largest points. In fact, we may find all the extreme points of the subshift of finite type, not just the maximal and minimal points. $\endgroup$
    – Ben Ben
    Nov 24, 2014 at 16:13
3
$\begingroup$

Let us look at the maximum, for instance.

If $1^k$ is admissible in your SFT for all $k\ge1$, then, clearly, $a=1^\infty$ does the trick.

Otherwise let $k$ be such that $1^k$ is admissible, but $1^{k+1}$ isn't. Then take $a=1^k d_1d_2\dots$, where $(d_n)$ is the greedy expansion of 1 base $q$. This should do it, provided $(d_n)$ is admissible in your SFT. Notice that unless $q$ is a Parry number, $(d_n)$ is not eventually periodic; in particular, it isn't if $q$ is transcendental. (Or $\sqrt2$, for example.)

If $(d_n)$ is not admissible in your SFT, then we might have a problem (and an interesting one, too, it seems).

A simple example is the SFT whose set of forbidden words is just $\{11\}$ (the ``Fibonacci compactum''). It looks like the maximum is attained at $a=(10)^\infty$ irrespective of whether $q$ is less than the golden ratio or not. But this is a very specific example.

$\endgroup$
1
  • $\begingroup$ Thank you. Nik. I think you idea follows Anthony, the sequence $1^kd_1d_2\cdots$ is a greedy expansion. That is why we can find the largest number! As you mentioned if $(d_n)$ is not admissible, then we may not find the largest sequence (in the sense of value) easily. In fact, I think for most cases, $(d_n)$ (the greedy expansion of $1$) is not in the SFT. Even for some very simple SFT, we may not find the largest number. Hence this problem cannot be addressed easily. $\endgroup$
    – Ben Ben
    Nov 21, 2014 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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