22
$\begingroup$

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.)

$\endgroup$
  • 6
    $\begingroup$ You need to be careful when you talk about complexity of a single problem. Perhaps it is not running time of a program but something like the length of a shortest formal proof (e.g. from ZFC). So if you write a program that just prints the answer, you must accompany it with a proof that the answer is correct, and the length of the proof counts in. $\endgroup$ – Sergei Ivanov Apr 8 '10 at 18:40
  • 4
    $\begingroup$ Most likely, the answer is 1: wikiwand.com/en/Benford's_law. $\endgroup$ – stanm Jul 2 '15 at 11:38
  • 1
    $\begingroup$ There's a 70% chance it's not $1$. $\endgroup$ – Todd Trimble Jul 2 '15 at 11:46
  • 3
    $\begingroup$ There is either a 100% chance it's 1 or a 100% chance it's not 1, plus or minus 0%. $\endgroup$ – PrimeRibeyeDeal Jul 2 '15 at 13:49
  • $\begingroup$ @stanm That is the strangest thing I have ever seen... $\endgroup$ – Simply Beautiful Art Aug 10 '16 at 0:27
16
$\begingroup$

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?]

$\endgroup$
  • 4
    $\begingroup$ It is also 1 in base 2 and in base b with $Graham/2<b\leq Graham$. Yes, I was mostly interested in the case with 10 ;), but I think the answer would be interesting for any b, $3<b<\log(graham)$ not a power of 3. (I just choose $\log(graham)$ because it is a huge number much smaller than grahams numbers. You could probably have chosen a larger number) $\endgroup$ – Sune Jakobsen Apr 8 '10 at 20:01
10
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ I go to OSU, so if I see him around I will run it by him. $\endgroup$ – Steven Gubkin Apr 8 '10 at 18:33
  • $\begingroup$ @Steven: I just sent him an email. It seems that OSUs math homepage is down. Do you know if the math.ohio-state.edu mails work? $\endgroup$ – Sune Jakobsen Apr 11 '10 at 17:07
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this conjecture. Can you comment on the situation for $\alpha = \pi$ in light of the Bailey-Borwein-Plouffe formula? en.wikipedia.org/wiki/…? $\endgroup$ – Vincent Mar 18 at 12:10
  • $\begingroup$ In general, if the most efficient algorithm for computing a few digits after the n'th digit requires $\Theta (f (n))$ "computational resources" then I expect a proof which constrains those digits should have length $\Theta (f (n))$, where the exact encoding method for proofs affects how the cost of a computation is calculated. A more efficient algorithm should lead us to expect weaker lower bounds for the proof length. Considering specifically $\alpha = \pi$ and $b = 2$, I believe the BPP algorithm requires $O (n \log n)$ time and $O (\log n)$ space, so I expect my conjecture to still be true. $\endgroup$ – Itai Bar-Natan Mar 18 at 14:29
  • $\begingroup$ Yes, I expected the BPP to have $O(log n)$ time also since you don't need all previous digits, but somehow ruling out possible problems with 'carrying' takes up a LOT of time if I understand Wikipedia correctly. I still find it quite counterintuitive $\endgroup$ – Vincent Mar 18 at 21:03
1
$\begingroup$

In base nine it's 3.

$\endgroup$
  • 2
    $\begingroup$ Citation, or details? $\endgroup$ – David Roberts Jun 26 '13 at 22:09
  • 3
    $\begingroup$ @DavidRoberts Not the OP, but: since Graham's number is a power of 3, the first digit (mod 9) must be either 1 or 3. Since Graham's number is an odd power of 3 (it's 3 raised to another power of 3, all of which are odd), it has to be 3. $\endgroup$ – Steven Stadnicki Nov 27 '17 at 20:45
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Less than $\log_3 G,$ surely? $\endgroup$ – Charles May 8 '12 at 14:21

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.