3

$\newcommand{\spec}{\operatorname{Spec}}\spec\sqrt2=\{\lfloor k\sqrt2\rfloor: k \ge 0\}$.

I have no idea of how I can prove the statement in the question.

Prove that $\spec\sqrt2$ contains infinitely many powers of $2$.

Brian M. Scott
  • 616,228
learner
  • 905
  • 2
    The most obvious place to start would be to enumerate the first few values of $\lfloor k \cdot \sqrt{2}\rfloor$ to get a feel for how it behaves. The next most obvious is to devise an algorithm for solving $\lfloor k \cdot \sqrt{2} \rfloor = 2^n$ for $k$. –  Oct 05 '12 at 21:10
  • 1
    What a strange notation. Why $\mathrm{Spec} \sqrt{2}$? – Alexander Shamov Oct 05 '12 at 21:12
  • @Alexander: Graham, Knuth, & Patashnik, Concrete Mathematics, refer to this sequence as the spectrum of $\sqrt2$. – Brian M. Scott Oct 05 '12 at 21:12
  • As stated, this question is obviously true. Do you mean infinitely many *integer* powers of 2? – GeoffDS Oct 05 '12 at 21:14
  • @Graphth: Of course. – Brian M. Scott Oct 05 '12 at 21:15
  • @BrianM.Scott I want the OP to say that :) – GeoffDS Oct 05 '12 at 21:15
  • What mean the symbol ⌊ ⌋? – Tomás Oct 05 '12 at 21:16
  • @Tomás: The floor function; $\lfloor x\rfloor$ is the unique integer $n$ such that $n\le x<n+1$. – Brian M. Scott Oct 05 '12 at 21:17
  • @Tomás: While rewriting your question in readble $\LaTeX$, I introduced this usual symbol for the floor function (yo will find the correponding symbol for ceiling in my answer below). – Hagen von Eitzen Oct 05 '12 at 21:18
  • I see. Thanks.. – Tomás Oct 05 '12 at 21:19
  • It is probably an idiotic question, but why is this more complicated to prove than proving line $y = mx+b$ contains infinitely many integer powers of two? Or to just prove the generic case that $\lfloor k\cdot a\rfloor$ would contain infinitely many integer powers of 2 for any positive real number $a$? I suppose what I mean is, why can't you just use the definition for the range of the function as your argument? The Spec function as defined seems to have a range that would include all nonnegative integers, thus infinitely many powers of 2. – cheepychappy Oct 05 '12 at 22:13
  • @cheepychappy: I assume that $k$ is meant to refer to natural numbers only. – bradhd Oct 05 '12 at 23:11

1 Answers1

2

Let $k=\lceil 2^n\sqrt 2\rceil$. Then $2^n\sqrt 2<k<2^n\sqrt 2+1$. In fact we have either $2^n\sqrt 2<k<2^n\sqrt 2+\frac12$ or $2^n\sqrt 2+\frac12<k<2^n\sqrt 2+1$, depending on the ($n+1)$st binary digit of $\sqrt 2$ (which becomes the first digit of $2^n\sqrt 2$). Since $\sqrt 2$ is irrational, there are infinitely many $n$ (and correspondingly infinitely many $k$) such that $$2^n\sqrt 2<k<2^n\sqrt 2+\frac12$$ holds. Together with $k\sqrt 2 -1<\lfloor k\sqrt 2\rfloor <k\sqrt 2$ we find $$ 2^n\cdot 2-1 <\lfloor k\sqrt 2\rfloor <2^n\cdot 2+\frac{\sqrt 2}2,$$ hence $\lfloor k\sqrt 2\rfloor=2^{n+1}$.

Hagen von Eitzen
  • 374,180
  • Thanks for the answer, but I see a lot of unexplained things, which I don't seem to be able to comprehend :( .

    (n+1)st binary digit is the one counted from the left end, right? And, how does this bit influence the range of k like you posted? Infinitely many k? But k is a natural number, right? How would k take infinitely many values in between 2 real numbers differing by 1/2?

     – learner Oct 05 '12 at 21:55