How to detect frequency? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T05:13:24Z http://mathoverflow.net/feeds/question/75131 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75131/how-to-detect-frequency How to detect frequency? symboleon 2011-09-11T07:56:53Z 2011-09-11T23:12:13Z <p>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:</p> <p>$s_{n}=1$ if $z_{n}\in J$ and $s_{n}=0$ if $z_{n}\notin J$.</p> <p>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</p> <p>$\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}}$.</p> <p>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:</p> <p>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}}$.</p> <p>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}$.</p> <p>[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> <p>P.S. Curly brackets {} are not displayed in math mode. How to fix the problem?</p> http://mathoverflow.net/questions/75131/how-to-detect-frequency/75139#75139 Answer by Ian Morris for How to detect frequency? Ian Morris 2011-09-11T11:41:07Z 2011-09-11T11:41:07Z <p>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&lt;\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.</p> <p>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.</p> http://mathoverflow.net/questions/75131/how-to-detect-frequency/75173#75173 Answer by Jared Bronski for How to detect frequency? Jared Bronski 2011-09-11T23:12:13Z 2011-09-11T23:12:13Z <p>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. </p>