The problem of finding the first digit in Graham's number

Question

Motivation

In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could it be possible to show that (under some assumptions about the speed of our computers) we can never determine the first digit?

In logic you have independence results like "We cannot decide if AC is true in ZF". But we cannot hope for this kind of result in this case, since we can easily program a computer to give us the answer. The problem is, that we don't have enough time to wait for the answer!

In complexity theory you prove things like "no program can solve all problems in this infinite set of problems, fast". But in this case you only have one problem, and it is easy to write a program, that gives you the answer. Just write a program that prints "1" another that prints "2" ... and a program that prints "9". Now you have a program that gives you the answer! The problem is, that you don't know which of the 9 programs that are correct.

Questions

Edit: I have now stated the questions differently. Before I asked about computer programs instead proofs.

1. Could it be possible to show that any proof of what the first digit in Grahams numbers is, would have length at least $10^{100}$?
2. Do there exist similar results? That is, do we know a decidable statement P and a proof that any proof or disproof of P must have length $10^{100}$.
3. Or can we prove, that any proof that a proof or disproof of P must have length at least $n$, must itself have length at least $n$?

I think the answer to 3) is no, at least if all proofs are in the same system. Such a proof would prove that it should have length all least n for any n.

(Old Questions:

1. Could it be possible to show that it would take a computer at least say $10^{100}$ steps to determine the first digit in Grahams number?
2. Do there exist similar results? That is, do we know a decidable statement P and a proof that P cannot be decided in less that say $10^{100}$ steps.
3. Or can we prove that we need at least $n$ steps to show that a decidable statement cannot be decided in less than $n$ steps?)

(I'm not sure I tagged correctly. Fell free to retag, or suggest better tags.)

Answer 1

Easy: 1. But you probably meant base 10, not base 3, right ? That's a touch harder...

[Hopefully I don't run afoul of some MO rule by injecting a little humour in an answer?]

Answer 2

It seems to me that the question is really about the shortest proof that the first digit of Graham's number is what it is, rather than the shortest program that calculates it. Indeed, if you have an efficient program plus a proof that the program is correct (which rules out your nine programs, one of which is correct), then you have a short proof, and if you have a short proof then you have an efficient program that you know is correct (it just prints out the answer).

There are certainly results that are known to be true in PA but only to have very long proofs in PA. For example, the proof that every Goodstein sequence eventually hits zero needs the axiom of infinity. But any particular instance can in principle be shown to hit zero -- it's just that the proof would take an inordinately long time. So the answer to your question 2 is yes if you restrict to PA. I imagine that similar results are known for other axiom systems. As Gerhard says, Harvey Friedman knows a lot about this sort of thing.

Answer 3

Harvey Friedman has dealt with many large numbers, as well as issues regarding their computability. (Cf. his Enormous Numbers in Real Life.) I suggest emailing him your question. (You can also check other Math Overflow posts on Graham's number.)

Gerhard "Ask Me About System Design" Paseman, 2010.04.08

Answer 4

In general, the first digit of a number $A$ can be determined from the fractional part of $\log_{10} A$. Specifically, if $\log_{10} A = n + \gamma$ where $n = \lfloor \log_{10} A \rfloor$ and $\gamma = \{ \log_{10} A \}$ then $A = 10^\gamma 10^n$ and $1 \leq 10^\gamma < 10$. Therefore the first decimal digit of $A$ is $k$ iff $k \leq 10^\gamma < k+1$, or, equivalently, iff $\log_{10} k \leq \gamma < \log_{10} (k+1)$.

Taking the special case where $A = G$ is Graham's number, we have $G = 3^{3^x}$ for some natural number $x$. Then $\log_{10} G = 3^x \log_{10} 3$. Observe that multiplication by $3^x$ is the same as shifting the base 3 digits of a number $x$ places to the left. Setting $\alpha = \log_{10} 3$ the problem reduces to finding the base 3 digits of $\alpha$ starting $x$ places after the decimal point.

Then the following conjecture would imply that it is impossible to prove anything about the first digit of $G$ in time $o (x)$:

Conjecture: Given a natural number $x$ and a sequence of base 3 digits $z_0, \dots, z_{k-1}$, any proof in ZFC of the statement "The first $k$ base 3 digits of $\alpha$ starting $x$ places after the decimal point are not $z_0 \dots z_{k-1}$" must have length $\Omega\:(n)$.

Analogous conjectures can be asked for any other $b \geq 2$ and replacing $\alpha = \log_{10} 3$ with any other well-known irrational numbers. The reason to expect such a conjecture to hold is that I don't think there is any way to prove anything about $x$th digit of $\alpha$ that is essentially different from calculating the $x$th digit with a general-purpose algorithm, and I don't think there are any such sublinear general-purpose algorithms. Given that there does exist a quasilinear time algorithm for computing the digits of $\alpha$ (see Modern Computer Arithmetic for details), this conjecture would give a fairly sharp estimates $\tilde {\Theta}\:(\log \log G)$ steps for the shortest proof determining the first digit of $G$.

Showing that there are no sublinear-time algorithms for computing the $x$th digits of any natural irrational number seems more difficult than the P vs. NP problem, which is already far beyond what current theoretic computer science can achieve, and the conjecture I stated above is probably more difficult still. However, if we ever get to the point where it is possible to give sharp lower bounds on the most efficient possible algorithms for most problems, then this problem would be potentially solvable.

Answer 5

In base nine it's 3.

Answer 6

Similarly, it is 1 if the base is of the shape $3^n$, with $n$ a power of 3 (less than $\ln G$) ; other cases are easy for small powers of 3. On the other hand, Graham's number is much too large for the question to be really interesting ; the determination of the first digit in base 10 of $A(9,9)$ (where $A$ is the Ackermann function) should already be inaccessible.