Erdős' similarity conjecture states that for each infinite set $A\subset \mathbb R$ there is a set $P\subset [0,1]$ of positive measure such that for all $t\in \mathbb R$, $\delta\neq 0$ there is some $a\in A$ with $t+\delta a\notin P$. In particular, it is unknown if the sequence $A=\{2^{-n}:n\geq 1\}$ has the property above.

I am considering the following related proposition (not sure if this has been answered in previous literature):

If $E\subset [0,1]$ has full measure then there is $t\in \mathbb R$ and $\delta\neq 0$ such that $t+\delta 2^{-n}\in E$ for all $n\geq 1$.

Is this correct?

  • 1
    $\begingroup$ Your conjecture is correct. Actually $t$ can be 0. $\endgroup$ – 喻 良 Sep 18 at 0:45
  • $\begingroup$ @喻良 Thanks! Do you have a reference for that? $\endgroup$ – Thomas Yang Sep 18 at 0:49
  • $\begingroup$ Here is the most recent survey: jstor.org/stable/44153069. Question 1 was answered. I have a positive answer to Question 2 under certain set theoretical assumptions. $\endgroup$ – 喻 良 Sep 18 at 0:55
  • $\begingroup$ FYI LaTeX-style accenting like \H{o} doesn't work in text on this site, only in math. If you want ő you have to actually type it (if you don't know how to type it on your keyboard, your OS may have a character map tool). $\endgroup$ – Nate Eldredge Sep 18 at 1:21
  • $\begingroup$ For $t=0$ almost any $\delta\in (0,1)$ works: not appropriate values are covered by countably many null sets. Well, I guess this may be what 喻 良 essentially says, but without special terminology which I am sorry to be not familiar with. $\endgroup$ – Fedor Petrov Sep 18 at 7:47

I want to take this opportunity to give an application of algorithmic randomness theory to this area. Accidentally I am working on the similarity problem recently and found some interesting applications of algorithmic randomness theory to the area.

For the notation of randomness you may refer to the book by Downey-Hirschfeldt or Nies.

Proof: It is simple to see that if $\delta$ is $x$-random, then so is $\delta2^{-n}$ for any $n\geq 1$. But $E$ is conull and so there must be a real $x$ so that every $x$-random belongs to $E$. Then it is clear that every $x$-random real $\delta$ meets your requirement. QED

Actually this method can be used to prove that for any countable set $A\subset (0,1)$ , there is a real $\delta$ so that $\delta y\in E$ for any $y\in A$ (The result was proved by Kolountzakis first).


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.