How to detect frequency? - MathOverflow

How to detect frequency?

2011-09-11T07:56:53Z

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?

Answer by Ian Morris for How to detect frequency?

2011-09-11T11:41:07Z

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.

Answer by Jared Bronski for How to detect frequency?

2011-09-11T23:12:13Z

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.