In answering another MathOverflow question on Graham's number, I quoted from Harvey Friedman's Enormous Numbers in Real Life. Perhaps eventual counterexamples bear some relation to proof strength in certain systems of logic? Anyway, that example there could be rephrased to fit the current question.

Suppose I look at strings on three symbols, and given a word w of length n I look
at subwords of the form (forgive the AWK notation) `spc[i] = substr(w,i,i+1)`

, i.e.
those substrings starting at the $i$th character going for length $i+1$ characters.
So `spc[1]`

gets the first two characters of $w$, `spc[2] == w[2]w[3]w[4]`

, and so on.

I manage to find, for every $n$ that I can compute, a string $w_n$ that I use for $w$ above such that for $0 < i < j \leq \frac{n}{2}$, `spc[i]`

is not a subsequence of `spc[j]`

. Others find such examples for even larger values of $n$. It would be reasonable for me to believe I could find arbitrarily long strings with this property.

Enter Harvey Friedman:

"**Theorem 8.1**. Let $k \geq 1$. There is a longest finite sequence
$x_1, \dots ,x_n$ from $\{ 1, \dots ,k \}$ such that for no $i < j \leq \frac{n}{2}$ is $x_i, \dots ,x_{2i}$ a subsequence of $x_j , \dots ,x_{2j}$.

For $k \geq 1$, let $n(k)$ be the length of this longest finite
sequence.

Paul Sally runs a program for gifted high school students at
the University of Chicago.

He asked them to find $n(1), n(2), n(3)$. They all got $n(1) =
3$. One got $n(2) = 11$. Nobody reported much on $n(3)$.
I then started to ask several mathematicians to give an
estimate on $n(3)$, some of them very famous. I got guesses
like this:
$60, 100, 150, 200, 300$.

They were not in combinatorics. Recently I asked Lovasz,
telling him about these five guesses. He guessed $20000$.

**Theorem 8.2**. $n(3) > A(7,184)$.

Lovasz wins, as his guess is closer to $A(7,184)$ than the other guesses.

Recall the discussion about $A(5,5)$ being incomprehensibly large. With the help of computer investigations (with R. Dougherty), I got:

**Theorem 8.3**. $n(3) > A(7198, 158386)$.

A good upper bound for $n(3)$ is work in progress. Crude result:
$A(n,n)$, where $n = A(5,5).$"

Here $A(n,n)$ is defined earlier in Friedman's paper as an Ackermann-like sequence.

I suspect $n(3)$ squishes Graham's number quite unlike a galactic black hole absorbing a prion or even a quark.

EDIT: I have been corrected; in the squishing hierarchy, $n(4)$ squishes Graham's number, which squishes $n(3)$. Again, unlike any physical realization I can imagine. END EDIT

The moral here is: "Don't jump to conclusions without a sufficiently strong proof system as back up".

Gerhard "Ask Me About System Design" Paseman, 2010.02.17

12more comments