Well approximating sets

Question

Given a real number $x \in (0, 1)$, we denote by $0.x_1x_2\ldots$ its binary expansion, where we always choose the expansion that ends in an infinite number of $1$’s whenever a choice has to be made.

Given two real numbers $a = 0.a_1a_2\ldots$ and $b = 0.b_1b_2...$ in $(0, 1)$, denote by $S(a, b)$ the set of indices $i$ for which $a_i \neq b_i$. We label the elements of $S(a, b)$ by $s_0, s_1,\ldots$, where the values of the sequence are chosen to be in increasing order. We suppress the dependence on $a, b$ when writing the sequence for clarity.

We say an increasing sequence $c_n$ of positive real numbers is anti-syndetic if for any polynomial $P$ with positive coefficients, there exists some $N \in \mathbb N$ such that $c_{n + N} > P(n)$ for all $n \in \mathbb N$.

A subset $D$ of $(0, 1)$ is said to be well approximating if for every $x \in (0, 1)$, there is a $d \in D$ such that the sequence $s_n$ associated with $S(x, d)$ is anti-syndetic.

Question: Does there exist a well approximating subset of $(0, 1)$ with Lebesgue measure zero?

Answer 1

Let $D$ consist of all numbers $d$ in $[0,1]$ such that in their binary expansion for every $k$ the digit at location $2^k$ vanishes, i.e., $d_{2^k}=0$. Then it is easy to check that $D$ has Lebesgue measure zero (Indeed it can be covered by $2^{2^k-k}$ intervals of length $2^{-2^k}$ for each $k$). For every $x \in (0,1)$ there is $d \in D$ that agrees with it in all digits except those that our powers of 2, so the elements of $S(x,d)$ satisfy $s_n \ge 2^n$ for all $n$.

(Answer first provided on another site yesterday; it is the same as Fedor Petrov's comment.)