Skip to main content
8 events
when toggle format what by license comment
Feb 5 at 6:02 comment added Sean it has been a long time, but could I contact you individually and talk about some related research? Thank you very much!
Mar 6, 2020 at 20:08 vote accept Sean
Mar 6, 2020 at 20:08 comment added Sean Thank you a lot!
Nov 26, 2019 at 4:56 comment added Sam Zbarsky @Sean this means that $a$ from my answer can be taken to be $\theta(\log N)$. Thus is takes $\Omega(N\log N)$ time to get to $N$. Letting $s=cN\log N$ for some small $c$, we have $\eta(s)<N$, so $\eta(s)/s<1/(c\log N)<\frac{2}{c}(1/\log s)$
Nov 26, 2019 at 3:10 comment added Sean Why does that estimate relate to the limit?
Nov 25, 2019 at 22:24 comment added Sam Zbarsky @Sean The idea is that the argument about the size of $A_\epsilon$ should work for any $\epsilon\in [1/N^{1/4},1/10]$ (not trying to optimize the bounds here). We use well-known facts about the approximability/continued fraction expansion of $\sqrt{2}$ to get that there are some natural numbers $a=\theta(N^{1/3})$ with $a\sqrt{2}-b=\theta(N^{-1/3})$. This gives that taking integers up to size $\theta(N)$, they are equidistributed on scale $N^{-1/3}\ll\epsilon$. So we can take $\epsilon$ in the stated interval.
Nov 25, 2019 at 22:11 comment added Sean Can you explain how to bound that $a = \theta(\log N)$?
Nov 25, 2019 at 7:09 history answered Sam Zbarsky CC BY-SA 4.0