5
$\begingroup$

Very poorly chosen words on my part...what I am getting at is that instead of using proof by contradiction is it possible to build an algorithm that returns the digits of the square root of 2 or some other irrational number in such a way as to demonstrate the digits will never be repeating themselves?

I realize that proof by contradiction may well be the only way but in that case must one also show the law of excluded middle will apply in order to use the contradiction? And I was trying to avoid this possibility because I did not know how to do it. Thank you

$\endgroup$
  • 1
    $\begingroup$ Surely if we could determine irrationality though digit analysis, then we could determine the (ir)rationality of $\pi + e$. But that's still an open problem, so I'm doubtful of such an approach. $\endgroup$ – Tiwa Aina Nov 20 '17 at 15:54
  • 4
    $\begingroup$ Interesting question! If you're willing to accept representations besides expansions in base $n$ (where $n \geq 2),$ then maybe a continued fraction expansion will work? $\endgroup$ – Dave L. Renfro Nov 20 '17 at 15:55
  • $\begingroup$ @DaveL.Renfro How would you prove that it never repeats through continued fraction expansion? $\endgroup$ – Tiwa Aina Nov 20 '17 at 15:56
  • 5
    $\begingroup$ @Tiwa Aina: This is what I meant. Thus, instead of a base $n$ expansion and showing non-periodicity by some argument relying on the expansion being recursively given in some explicit way, the answer is very easy if we instead are allowed use a continued fraction expansion and show the expansion is not finite. As for the question as asked, I suspect the answer is NO, because (for example) no one even knows whether the decimal expansion of $\sqrt{2}$ contains infinitely many digits equal to $2.$ $\endgroup$ – Dave L. Renfro Nov 20 '17 at 16:02
  • 3
    $\begingroup$ I can imagine the following happening: (i) Give a rule generating a sequence of numbers which happens to be the decimal expansion of $\sqrt{2}$. (ii) Show that this rule does not generate an eventually-repeating sequence, without reference to $\sqrt{2}$. (iii) Prove that in fact it gives the decimal expansion of $\sqrt{2}$. Would this be the sort of thing you're looking for? (Note that we would still need to prove a "global" fact - step (ii) - and there's no way around this; some kind of broad reasoning is going to be necessary.) $\endgroup$ – Noah Schweber Nov 20 '17 at 16:35
2
$\begingroup$

This may not be the kind of proof the OP is looking for, but it might be of interest anyway.

Let's show that $\sqrt2$ cannot have an eventually repeating binary expansion. (I'm taking for granted the theorem that rational numbers are eventually repeating in any base and irrational numbers are not.) That is, $\sqrt2=1.0110101\ldots$ does not settle into any $n$-bit repetition after any finite number of binary bits, say $m$.

Suppose it did. Then, since ${1\over2^n}+{1\over2^{2n}}+\cdots={1\over2^n-1}$, we would have $2^m\sqrt2=M+{N\over2^n-1}$ for some (positive) integers $M$ and $N$ (with $N\lt2^n$). We can assume we've taken $m$ to be minimal. We'll first show that $m=0$ (and hence $M=1$, since $1\lt\sqrt2\lt2$). This is because squaring both sides of $(2^n-1)2^m\sqrt2=2^nM+(N-M)$ gives an even number of the left hand side, which implies $M$ and $N$ must have the same parity. This means they end in the same bit, either $0$ or $1$. So if $m$ were greater than $0$, we could move the (binary) decimal point to the left and still have an $n$-bit repeating string.

So now we need only consider the possibility $(2^n-1)\sqrt2=2^n+(N-1)$ for some positive integers $n$ and $N$ -- i.e., that the binary string $.0110101\ldots$ is periodic with some period $n$, which must clearly be at least $5$. As before, $N$ must be odd, so the right hand side is even, which means its square is congruent to either $0$ or $4$ mod $8$, since $n\gt3$. But the square of the left hand side is congruent to $2$ mod $8$, which gives a contradiction.

Surely this proof is already in the literature somewhere. Can anyone supply a reference?

$\endgroup$
  • $\begingroup$ Where did $M$ go? You showed $m=0$, but as far as I can see, you didn't show $M=1$. $\endgroup$ – celtschk Nov 20 '17 at 19:46
  • $\begingroup$ @celtschk, $M$ is the integer part of $2^m\sqrt2$. So if $m=0$, $M$ is the integer part of $\sqrt2$. $\endgroup$ – Barry Cipra Nov 20 '17 at 19:57
  • $\begingroup$ I see; explicitly stating that at that point wouldn't have hurt, though. $\endgroup$ – celtschk Nov 20 '17 at 20:07
  • $\begingroup$ @celtschk, good point. Done. $\endgroup$ – Barry Cipra Nov 20 '17 at 20:14

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.