#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

Date: Nov 25, 2024. Time: 18:30 (MSK), 16:30 (CET)
Title: Word combinatorics and approximations of reals
(Following Matthieu Rosenfeld, LIRMM)

Let $\alpha$ be a real number that we try to approximate by rational numbers $m/n$. It can be done with arbitrary precision, but there is a tradeoff between the precision and the denominator. For given denominator $n$ we can obviously make the error smaller than $0.5/n$ (by rounding $\alpha n$); Dirichlet theorem says that for _some_ n the precision could be much better. Let us an approximation $\eps$-good if $|\alpha n -m|\le\eps$. So for every $n$ there is $1/2$-good approximation with denominator $n$ (obvious), and for every $\eps0$ there are infinitely many denominators that allow $\eps$-good approximations (Dirichlet)

What if we allow only some denominators? Then Dirichlet theorem is no more true. For example, if we allow only denominators $1,2,4,8,16,\ldots$, then $1/3$ = $0.0101010101\ldots$ in binary, has no $1/4$-good approximations ($n\alpha$ has fractional part $1/3$ or $2/3$).

Question: assume that we have some other sequence of denominators $n_1,n_2,\ldots$ that is sparse: $n_i2n_{i-1}$, and some $\eps0$. Is it always possible to find some $\alpha$ that has no $\eps$-good approximations, for some $\eps$ and for all the denominators in the sequence? (Note that we cannot take $\alpha$ randomly, since for every $\eps$ the probability of success in $2\eps$ and the union bound does not work for infinitely many denominators.)

People in number theory were interested in this question (and finally proved that the statement is true). Matthieu Rosenfeld noted that we can get a simple proof of this result if we use tools from word combinatorics (e.g., Joe Miller's potential argument for avoiding forbidden strings). This proof will be explained.

➰ ВК