33
$\begingroup$

Let $C$ be the standard Cantor middle-third set. As a consequence of the Baire category theorem, there are numbers $r$ such that $C+r$ consists solely of irrational numbers, see here.

What would be an explicit example of a number $r$ with this property?

Short of an explicit example, are there any references addressing this question?

A natural approach would be to see that all irrationals in $C$ are transcendental, so it would suffice to take $r=\sqrt2$. But this is open, see here.


Many thanks for the answers. (It would be interesting to know whether $\sqrt2$ works.)

$\endgroup$
  • 1
    $\begingroup$ Alternately, you can use "measure zero". More generally, given any any measure zero set $Z$ and any countable set $Q$, there is $r$ so that $Z+r$ misses $Q$. $\endgroup$ – Gerald Edgar Feb 22 '14 at 21:05
  • $\begingroup$ @GeraldEdgar Yes. Conversely, Bjørn's measure-theoretic answer can be restated in terms of category and (Cohen) 1-generic reals. $\endgroup$ – Andrés E. Caicedo Feb 23 '14 at 23:00
31
$\begingroup$

One way to obtain explicit examples, which combines the ideas of (weak forms of) randomness and base 3 expansions, is to use the fact that normality in a given base is preserved under rational addition, which was proved by D. D. Wall in his 1949 Berkeley PhD Dissertation. (I'm relying on D. Doty, J. H. Lutz, and S.Nandakumar [Finite-state dimension and real arithmetic, Information and Computation 205(11):1640-1651, 2007] for this reference.) Here a number $r$ is normal in base $b$ if for any finite nonempty string $\sigma$ drawn from the alphabet $\{0,...,b-1\}$, the limiting frequency of the appearances of $\sigma$ as a substring of the base $b$ expansion of $r$ is $b^{-|\sigma|}$. Since elements of $C$ are not normal in base $3$, any number $r$ that is normal in base $3$ has the desired property. Examples of such numbers can be found at http://en.wikipedia.org/wiki/Normal_number, for instance.

In fact, normality is overkill. Let $r$ be disjunctive in base $3$, i.e., every finite ternary string appears as a substring of the ternary expansion of $r$ (which is both a comeager and a conull property). We need to show is that if $q$ is a positive rational then $r+q \notin C$. (Here addition is mod $1$.) If the ternary expansion of $q$ has infinitely many $1$'s then the fact that the ternary expansion of $r$ contains $0^n$ for all $n$ means that $q+r \notin C$. Otherwise, the fact that this expansion contains $0^m10^n$ for all $m,n$ does the trick.

$\endgroup$
  • 3
    $\begingroup$ Great answer, also welcome Denis! $\endgroup$ – Bjørn Kjos-Hanssen Feb 22 '14 at 22:12
  • $\begingroup$ very nice answer... $\endgroup$ – Anthony Quas Feb 22 '14 at 22:24
  • $\begingroup$ The normals former a meager set, can we make a comeager answer? $\endgroup$ – Bjørn Kjos-Hanssen Feb 22 '14 at 22:53
  • $\begingroup$ Great, thank you! Much nicer and general than I had hoped for. You may want to add your latest comment to the answer, to increase its visibility, since it is a stronger result. $\endgroup$ – Andrés E. Caicedo Feb 23 '14 at 23:08
  • $\begingroup$ Thanks for the suggestion. I've incorporated my comment (which addressed Bjørn's question) into my answer. $\endgroup$ – Denis Hirschfeldt Feb 23 '14 at 23:23
29
$\begingroup$

EDIT: This is modified from the original version which was incorrect, as pointed out by @KajetanJaniak.

I don't think this should be hard. Think base 3. Something is irrational if and only if it does not have a ultimately periodic base 3 expansion. Something's in $C$ if and only if it has no 1's in its base 3 expansion.

Here's an explicit $t$ that I think does the job: $$ t=\sum_{n=0}^\infty \sum_{j=2^{2n}}^{2^{2n+1}-1}3^{-j}\mathbf 1_{j\text{ odd}}. $$ In base 3 it's $$ t=0.1|00|0101|00000000|0101010101010101|00000000000000000000000000000000|01\ldots $$ (the $|$ are not part of the number, but just make it easier to read). Since $t$ does not have an ultimately periodic base 3 expansion, it's irrational.

Let's call the coordinate ranges where $t$ has 0's "0-blocks" (i.e. from $2^k$ to $2^{k+1}-1$ for $k$ odd) and the coordinate ranges where $t$ has 01's "01-blocks". Now if you form $x+t$ for any $x\in C$, $x+t$ has arbitrarily long blocks with no 1's in the base 3 expansion (corresponding to the blocks of 0's in $t$) - if you're unlucky, the last digit of $x+t$ in a 0-block might be a 1, but there are no others.

Hence if assume for a contradiction that $x+t$ is rational (and so has ultimately periodic base 3 expansion), the repeating block must contain only 0's and 2's.

Now consider the expansion of $x+t$ on the 01-blocks. A calculation shows that the only way to avoid having 1's in the sum in the interior of the 01-blocks is for $x$ to consist of a concatenation of 0022's and 2022's in those blocks and $x+t$ to consist of 0200's and 2200's there. Since the blocks occurring in $x+t$ have one less two than the corresponding blocks in $x$, we see that $x+t$ "looks different" on the 0-blocks than it does on the 01-blocks. Hence $x+t$ cannot have a periodic base 3 expansion, and must be irrational.

$\endgroup$
  • $\begingroup$ Thank you. This is the kind of answer I was expecting, and it is nice that the calculations end up not being as messy as I feared. I myself lost patience trying to keep track of what you call the 1-blocks of $x+t$ (for the $t$ I used myself, which I see is different from yours) when I first thought about this. $\endgroup$ – Andrés E. Caicedo Feb 23 '14 at 23:05
  • 3
    $\begingroup$ Anthony, I have some doubts about your explicit example of $t$. Let's write it like that: $$ t = 0.1(00)^{2^0}(11)^{2^1}(00)^{2^2}(11)^{2^3}\ldots (00)^{2^{2n}}(11)^{2^{2n+1}}\ldots $$ Then take $x \in C$: $$ x = 0.0(20)^{2^0}(02)^{2^1}(20)^{2^2}(02)^{2^3}\ldots (20)^{2^{2n}}(02)^{2^{2n+1}}\ldots $$ As a result we get $$ x + t = 0.1(20)^\infty \in \mathbb Q, $$ because within each block of length $2^n$ we can calculate the sum separately. (continued) $\endgroup$ – Kajetan Janiak Jan 19 '16 at 18:44
  • 3
    $\begingroup$ More precisely, for each subsequent pair of digits we use the following two formulas: $$ 0.(0)^n00 + 0.(0)^n20 = 0.(0)^n20 $$ and $$ 0.(0)^n11 + 0.(0)^n02 = 0.(0)^n20. $$ $\endgroup$ – Kajetan Janiak Jan 19 '16 at 18:44
  • $\begingroup$ @KajetanJaniak: Thanks for the comment. It seems I was too hasty in my last but 2 paragraph. I feel hopeful there is some way to modify the example and make it work. $\endgroup$ – Anthony Quas Oct 16 '17 at 17:47
  • 1
    $\begingroup$ Anthony: Add a mention to that effect at the beginning of the post? $\endgroup$ – Did Oct 16 '17 at 21:12
10
$\begingroup$

If $q\in x+C$, i.e., $q=x+c$ for some $c\in C$, then $x=q-c$, i.e., $x\in q-C$. Now $q-C$ is a closed set of measure zero and moreover it is a $\Pi^0_1$ class if $q\in\mathbb Q$. Thus each weakly 1-random real avoids $q-C$. In particular Chaitin's $\Omega$ does not belong to $q-C$.

There are infinitely many versions of Chaitin's number, so to get an explicit example we must choose one, coming from a canonical construction of a prefix-free universal Turing machine.

$\endgroup$
  • $\begingroup$ Is it clear that there is a computable example? The Baire category argument just says that there are comeager-many examples. $\endgroup$ – Noah Schweber Feb 22 '14 at 20:25
  • $\begingroup$ I guess the set $q-C$ is fairly simple, so a resource-bounded random real (like a polynomial time random one) should suffice. Perhaps one of those is even sort of explicitly definable, like a "polynomial time $\Omega$"... $\endgroup$ – Bjørn Kjos-Hanssen Feb 22 '14 at 20:40
0
$\begingroup$

Here is a simple example. Let $(f(n),g(n))$ enumerate all pairs of positive naturals over natural $n$. Let $x$ be the value of the ternary expansion starting with .1 where the $n$-th block of $0$s (between $1$s) has minimum length that is greater than the previous block length and is such that the $1$ immediately after that is at a position of the form $f(n)·k+g(n)$ for natural $k$. This is always possible because $f(n)$ is positive. Then $C−x$ does not contain any rational $r$.

Proof: Take any rational $r$. Then $r$ has ternary expansion that eventually regularly repeats some block $B$ of size $b$. If $B$ has a $0$, then it will repeat at positions of the form $f(n)·k+g(n)$ for some natural $n$ such that $f(n) = b$, and so at a position large enough adding $x$ to $r$ will add a $1$ to some repeat of that $0$ such that the next $1$ is beyond the next block, and so the result will have a $1$, and hence $x+r$ is not in $C$. If $B$ has a $1$, then at a position large enough adding $x$ to $r$ will add only $0$s to two adjacent repeats of $B$, since $x$ has increasingly longer blocks of $0$s, and the next $1$ after that will not affect the first repeat block, and hence $x+r$ is not in $C$. Since we can assume that $B$ has either a $0$ or a $1$, we are done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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