MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 clarified/corrected squishing

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 ith 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 < = 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 >= 1. There is a longest finite sequence x1,...,xn from {1,...,k} such that for no i < j <= n/2 is xi,...,x2i a subsequence of xj,...,x2j.

For k >= 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 20,000.

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

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 ith 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 < = 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 >= 1. There is a longest finite sequence x1,...,xn from {1,...,k} such that for no i < j <= n/2 is xi,...,x2i a subsequence of xj,...,x2j.

For k >= 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 20,000.

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.

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