3
$\begingroup$

$\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$.

  • 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$.2012-10-05
  • 1
    What a strange notation. Why $\mathrm{Spec} \sqrt{2}$?2012-10-05
  • 0
    @Alexander: Graham, Knuth, & Patashnik, *Concrete Mathematics*, refer to this sequence as the spectrum of $\sqrt2$.2012-10-05
  • 0
    As stated, this question is obviously true. Do you mean infinitely many ***integer*** powers of 2?2012-10-05
  • 0
    @Graphth: Of course.2012-10-05
  • 0
    @BrianM.Scott I want the OP to say that :)2012-10-05
  • 0
    What mean the symbol ⌊ ⌋?2012-10-05
  • 0
    @Tomás: The floor function; $\lfloor x\rfloor$ is the unique integer $n$ such that $n\le x.2012-10-05
  • 0
    @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).2012-10-05
  • 0
    I see. Thanks..2012-10-05
  • 0
    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.2012-10-05
  • 0
    @cheepychappy: I assume that $k$ is meant to refer to natural numbers only.2012-10-05

1 Answers 1

2

Let $k=\lceil 2^n\sqrt 2\rceil$. Then $2^n\sqrt 2. In fact we have either $2^n\sqrt 2 or $2^n\sqrt 2+\frac12, 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 holds. Together with $k\sqrt 2 -1<\lfloor k\sqrt 2\rfloor 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}$.

  • 0
    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?2012-10-05