147
$\begingroup$

Conor McBride asks for a fast proof that $$x = {\left(\pi^\pi\right)}^{\pi^\pi}$$ is not an integer. It would be sufficient to calculate a very rough approximation, to a precision of less than 1, and show that $n < x < n+1$ for some integer $n$. But $x$ is large enough (56 digits) that that method is not obviously practical without electronic computation tools.

Is there a purely theoretic proof that works with no calculation at all, or is there a calculational argument that would be practical prior to 1950?

Edit: Let me phrase the question a little differently, as a spur to your mathematical imagination. I go back in time to 1847 and have lunch with Carl Friedrich Gauss. We are chatting about the developments in 20th and 21st-century mathematics, and because I am a horrible person, I mention that $(\pi^\pi)^{\pi^\pi}$ has been proven to be an integer. Gauss is incredulous, but I insist. After I leave, can Gauss convince himself that I am nothing but a troll?

Edit: After I looked back at McBride's original question, I saw to my dismay that he had not asked about $x= (\pi^\pi)^{\pi^\pi}$, but $$y=\pi^{\left(\pi^{\pi^\pi}\right)}$$ which is a rather different animal. The value of $x$ has 57 decimal digits; the value of $y$ has $10^{57}$ digits. So Alexander Walker's impressive display of direct numerical calculation will avail nothing for deciding that $y$ is not an integer, neither in 1873 nor in 2013, and perhaps not in 2153 either. ("We should attempt to destroy the aliens.") More powerful theoretical methods will be required. I am posting an additional bounty to see if anyone can suggest anything of that sort; it need not be theory that was available in the 19th century.

$\endgroup$
  • 25
    $\begingroup$ You do not know what a messy office looks like. $\endgroup$ – MJD May 13 '13 at 19:56
  • 8
    $\begingroup$ I do know that trick, and I also know the Gel'fond–Schneider theorem, but I don't see how to apply either technique to this problem. $\endgroup$ – MJD May 13 '13 at 20:49
  • 4
    $\begingroup$ Yes, it's quite straightforward to calculate a sufficiently precise value to show that it is a noninteger, but unless you have a version of Wolfram Alpha that runs on a slide rule, that's not what the question is about. $\endgroup$ – MJD May 22 '13 at 18:04
  • 7
    $\begingroup$ @GitGud: A challenger appears. $\endgroup$ – Nikolaj-K May 28 '13 at 14:55
  • 4
    $\begingroup$ The only answer at question 13054 appeals to Schanuel's Conjecture (SC)---which if true would imply immediately that \em{any} term written in integers, the algebraic operations and the exponential function (as $e^{e^{e^e}}$ is) was transcendental unless there's an obvious reason why not, giving a positive answer to this question---but is unfortunately intractable. Model theorists, following Zilber, have recently made real progress in studying the consequences of (SC). In particular, there is exactly one algebraically closed field of cardinality $2^{\aleph_0}$ satisfying (SC) and ... [cont] $\endgroup$ – HTFB Jun 3 '13 at 10:06
114
+400
$\begingroup$

I think this calculation would have been doable in 1873, as follows:

(1) Compute $\log \pi$ to $60$ digits. For this, we begin with the expansion

$$\log \pi = \log \left(\frac{\pi}{22/7}\right)+\log 2 + \log 11-\log 7$$

and take full advantage of the fact that the logarithm tables of small integers were known to great precision. As for the logarithm of $\pi/(22/7) \approx 1.00041$, the Taylor series for the logarithm spits out $60$ digits after only $17$ terms. (Surprisingly, this exact analysis has been done on MSE before.)

(2) Compute $(\pi+1)\log \pi$ to $60$ digits. This is no big deal, given our value for $\log \pi$ from (1), since $\pi$ was known (to Gauss, no less!) to at least $100$ digits back in 1844. For reference, this value is

$$ \approx 4.7410048855785583722294291029994190930164741026691888020108672.$$

(The multiplication will of course be a pain, as it requires around $1800$ flops. Nevertheless, this computation would likely be delegated to a lesser mathematician. The Wikipedia article on Zacharias Dase (a temporary assistant to Gauss) puts these computations into perspective:

At age 15 [Zacharias Dase] began to travel extensively, giving exhibitions in Germany, Austria and England. Among his most impressive feats, he multiplied 79532853 × 93758479 in 54 seconds. He multiplied two 20-digit numbers in 6 minutes; two 40-digit numbers in 40 minutes; and two 100-digit numbers in 8 hours 45 minutes. The famous mathematician Carl Friedrich Gauss commented that someone skilled in calculation could have done the 100-digit calculation in about half that time with pencil and paper.

(3) Exponentiate the product, again to $60$ places. Using just the series $$e^z = \sum_{k=0}^\infty \frac{z^k}{k!}$$ such a calculation would require $77$ terms. For this reason, we instead calculate $$e^{4.741} \approx 114.54869311801681310751748724665811195370661075419665168411647;$$ $$e^{0.0000048\cdots} \approx 1.0000048855904928305900123833767696556988185632721564706179420.$$ The latter approximation requires a mere $10$ terms of the exponential Taylor series to achieve $60$ digits, a commitment of around 18000 flops. By Gauss's metric, we might expect a skilled mathematician to complete this task in just over seven hours.

The prior calculation could be done in one of two ways: directly, at a cost of another $18000$ flops (e.g. $77$ consecutive multiplications of a $4$-digit and a $60$-digit number); or by calculating $\mathrm{exp}(4)$ and $\mathrm{exp}(.741)$ independently (a slight time savings, I believe, even after the final multiplication). Of course, now it just takes another $1800$ flops to multiply these numbers to $60$ places.

Note: In hindsight, it appears that calculating the triple product $$e^4 e^{3/4}e^{-9/1000}$$ may expedite this most recent step.

In case you've lost track, we now know the value of $$e^{(\pi +1)\log \pi}=\pi^{\pi+1}$$ to $60$ digits, all within a day or two of starting our calculations.

(4) Multiply $\log \pi$ and $\pi^{\pi+1}$ to $60$ digits. This step is easy, given steps (1) and (3). This value is $$\approx 131.12795303153615589452803943707399841542170349230159549341360.$$ Of course, this value is also the logarithm of $(\pi^\pi)^{\pi^\pi}$, so it remains to:

(5) Exponentiate the term from (4). Since it worked out so well in (3), we'll again split our exponential into a product of simpler terms. Here, we luck out - since the binary expansion of $131.127953\ldots$ begins as $$10000011.001000001100000\cdots_2,$$ the partial approximation $131+1/8$ is surprisingly accurate: to within $\approx 0.002953$. The exponential of this remainder can be made accurate to over $60$ digits with a mere $18$ terms (i.e. $32000$ flops).

Secondly, we compute $e^{131}$ to $60$ digits, using iterated multiplication and an approximation of $e$ to $62$ digits ($205$ digits were known to William Shanks in 1871). Since it suffices here to successively compute $$e^2,e^4,e^8,e^{16},e^{32},e^{64},e^{128},$$ this step can be done in less than $15000$ flops. Thirdly, we compute $e^{1/8}$ to $60$ digits using three applications of Newton's method for the square root (another $6000$ flops). We find a value of $$ \approx 887455172183124295874631455225434602688412866765466125005\color{red}{.16},$$ a non-integer.

All said and done, I would be surprised if this calculation took much longer than a week. At the same time, I stress that this problem would have been barely doable in that era. If twice the number of digits were required, for example, this work may very well have taken the better part of a year.

$\endgroup$
  • 50
    $\begingroup$ I think I must feel a little bit the way Feynman did when he offered a prize for an electric motor that would fit in a 1mm cube, expecting to spur the development of a new design for electric motors, and instead got a very tiny, very carefully constructed, but completely conventional electric motor. But your answer is a tour de force, and makes me say "Oh, is that all there is to it?" when previously I could not think of how to do it at all—which is a good thing. So thank you very much for this reply! $\endgroup$ – MJD May 25 '13 at 4:28
  • 9
    $\begingroup$ It's amazing what 1800s mathematicians had to work with before the dawn of computers. Their numerical skills far outpace mine own! $\endgroup$ – awwalker May 25 '13 at 5:23
1
$\begingroup$

The idea is to try to use this theorem, but in essence it will be just a leading force into simplifying it all considerably.

Theorem

$e^x$ is an integer iff for every $n>ex$

$$1-\{\sum_{k=0}^{n}\{\frac{x^k}{k!}\}\} \leq \frac{2x^{n+1}}{(n+1)!}$$

This is easy to derive and 19th century mathematicians had tools to find that it is sufficient to take $ex$ terms in order to achieve the precision less than $1$ and the right part is a crude estimation of the error term.

However in order to make this more precise, we find an integer as close to $(\pi^\pi)^{\pi^\pi}$ as we can. Since we know $\pi^3 \approx 31$, the candidate is simply $31^{31}$ which is not that difficult to calculate after all:

$$31^{31}=\frac{(((((31)^2)^2)^2)^2)^2}{31}$$

Using that we are reducing the calculation from $300$ terms to about $80$ terms of working with smaller numbers. Yet we can do better:

$$\pi^{\pi+1}\ln(\pi)-31\ln(31) \approx 25$$

Going into this direction we can try to find max integer solution of

$$x^x < e^{24}$$ $$x = 10$$

That leaves

$$\pi^{\pi+1}\ln(\pi)-31\ln(31)-10\ln(10) \approx 1.64$$

making

$$(\pi^\pi)^{\pi^\pi}=31^{31}10^{10}e^{\pi^{\pi+1}\ln(\pi)-31\ln(31)-10\ln(10)}$$

Further

$$(\pi^\pi)^{\pi^\pi}=31^{31} 10^{10} 2^{2} e^{{\pi^{\pi+1}}\ln(\pi)-31\ln(31)-10\ln(10)-2\ln(2)}$$

And finally

$$1<e^{\pi^{\pi+1}\ln(\pi)-31\ln(31)-10\ln(10)-2\ln(2)} <2$$

As we are dealing with small numbers the idea is very obvious. Express

$$\pi^{\pi+1}\ln(\pi) = r+\sum_{k=1}^{m}a_k\ln(b_k), a_k \in \mathbb{N},b_k \in \mathbb{N}, 0 \leq r < \ln(2)$$

Once this is done it is only $\{e^r\}$ that decides if the expression is an integer or not which we can calculate to almost any desirable precision or limited but sufficient one manually. Still we need to do the final multiplication.

Notice that even without the final multiplication, just by calculating $\{e^r\}$ we may confirm beyond doubt that the number cannot be rational number (which is the only way of making the above expression an integer), or that it is not a correct rational number if it happens to be rational, for which we would not have to multiply with the large number $31^{31} 2^{2}$ at all. A nice thing to have is $10^{10}$ if we work in decimal notation, but any integer pair $p\ln(q)$ would do equally well.

Simplifications can be revolving around these two ideas, of course, starting from instantly trying to find the best matching $10^d$ to still using the series with a couple of terms, or trying out only small primes in order to get the simplest possible proof that $e^r$ is not rational and so on.

For example

$$\pi^{\pi+1}\ln(\pi) = 189\ln(2)+r$$

Now you calculate $e^r$ to about 60-digit precision. The worst case scenario is that it is of the form $\frac{p}{2^{189}}$ which would be obvious that it is not from its form. (Not that mathematicians were not capable of using binary form I doubt dealing constantly just with $0$ and $1$ would be beneficial. Still it is a very nice feature to have that $r$ has to stop in binary representation.)

Finally we pick

$e^{\pi^{\pi+1}\ln(\pi)- 56\ln(10)} = 8.874551721831242958746314552254346026884128667654661250051588548428...$

proving it is not an integer. The precision is about 65 digits and it does not end with the stream of $0$'s or possibly $9$'s.

19th century mathematicians were much smarter than this sample of ideas for sure.

Not to forget then about the "and now" part.

All we need is to prove that

$$e^{\pi^{\pi^\pi}\ln(\pi)-2213275961092431622\ln(2)}$$

is irrational. Piece of cake for 22nd century mathematician. :)

The most likely future proof is going to claim that

$$ \{ 1,^{n}\pi | n \in \mathbb{N} \} $$

are all linearly independent over $\mathbb{Q}$, where $^{n}x$ is tetration. Meaning none of exponents is an integer.

$\endgroup$

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.