MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $J$ be an arc in $\mathbb{S}^{1}\subset\mathbb{C}$ (no matter open or closed) and $\alpha\in(0,2\pi)$ be an angle such that $\alpha/\pi$ is irrational. Consider in $\mathbb{S}^{1}$ the sequence $z_{n}=e^{in\alpha}$. Then this sequence is dense in $\mathbb{S}^{1}$ by Kronecker's Theorem or by ergodicity. Let's associate with the arc $J$ its "indicator sequence" $s(J)={s_{n}\}$ of zeroes and ones defined as follows:

$s_{n}=1$ if $z_{n}\in J$ and $s_{n}=0$ if $z_{n}\notin J$.

So, we get something like 0 0 1 1 1 0 0 0 1 1 0 0 1. . . Suppose that we are given such a sequence $s(J)$ for some $J$ and some $\alpha$. By the Ergodic Theorem one gets the measure of arc $J$ as the limit

$\mathtt{meas}(J)=2\pi\underset{n\rightarrow\infty}{\lim}\frac{\sigma_{n}}{n}$ where $\sigma_{n}$ is the number of 1's in ${s_{1},s_{2},...,s_{n}}$.

OK, but is it possible to detect the "frequency" $\alpha$ only by the 0-1 data contained in the sequence $s_{n}$? More precisely, my question is:

Let $\{s_{n}\}$ be a sequence of 0's and 1's and we know that it is an "indicator sequence" for some arc $J\subset\mathbb{S}^{1}$ and some angle $\alpha$. Is it then possible to get $\alpha$ by some formula similar to the above one for the measure of $J$? This would be something like a "rotation number" of sequence $\{s_{n}\}$.

Similar question may be posed for the torus $\mathbb{T}^{n\text{ }}$and an open set $J\subset\mathbb{T}^{n\text{ }}$. Then we should detect not only the frequencies $\alpha_{1},\alpha_{2},...$ but also the "dimension" $n$ of the sequence. Here $\alpha_{1},...,\alpha_{n},\pi$ have to be independent over $\mathbb{Z}$.

[I know that the "indicator sequence" is a standard construction in symbolic dynamics, but I am not very involved in the topic, so references are welcome.]

P.S. Curly brackets {} are not displayed in math mode. How to fix the problem?

share|cite|improve this question
Curly brackets can be obtained via \lbrace and \rbrace. – Andrew Sep 11 '11 at 10:20
@Andrew @Symbo'leon Or via \{ and \}. – Quinn Culver Sep 11 '11 at 15:27
$S((0,\alpha))$ forms what is called a Sturmian sequence, a special case of a subshift of finite type. If $J$ is a general interval, than one gets a more general subshift. I still believe, one always has uniqueness. – Helge Sep 11 '11 at 17:23
@Helge: Sturmian sequences - or, strictly speaking, their orbit closures - are subshifts of infinite type. Subshifts of finite type are those subshifts which can be obtained from the full shift by "forbidding" finitely many words, and have special properties not enjoyed by Sturmian shifts. (These days it is usually assumed that the forbidden words are all of length two, which can be achieved by re-coding the alphabet.) – Ian Morris Sep 11 '11 at 21:00
up vote 5 down vote accepted

It seems likely to me that $\alpha$ can be computed by calculating the frequencies of subwords of the coding sequence, but in a manner which depends on certain parameters. For example, if $\alpha<\min\{|J|,2\pi-|J|\}$ then the interval $J \setminus J +\alpha$ has length precisely $\alpha$, and it follows easily that $\alpha$ equals the frequency of the subword 01. On the other hand if $|J|$ is very small and $\alpha, 2\pi-\alpha$ are both larger than $|J|$, then the frequency of the subwords 01 and 10 are both $|J|$, while the subword 00 has frequency $1-2|J|$, and we cannot gain anything by considering words of length 1 or 2. So the frequencies of words of arbitrary length probably need to be considered.

The articles "Coding rotations on intervals" by Berstel and Vuillon, and "Three-distance theorems and combinatorics on words" by Alessandri and Berthé appear to be relevant (especially Lemma 1 in the latter) but do not seem to yield a complete answer.

share|cite|improve this answer

Unless I am missing something you can just compute $\lim_{N\rightarrow \infty} \frac{1}{N}\sum a_k \exp(2 \pi i k s)$ to find the Fourier transform of the characteristic function of the interval J, and then do an inverse transform to find J. This is more-or-less what you suggest about computing a rotation number.

share|cite|improve this answer
What I said above was not quite what you asked - let me try again. The above should give you the Fourier transform with argument $\frac{s}{\alpha}$. From this and knowledge of the Fourier transform of an interval you can recover $\alpha$. – Jared Bronski Sep 11 '11 at 23:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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