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.

  • 24
    $\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

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.

  • 46
    $\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
  • 7
    $\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

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.