FOM: 123:Divisibility

[Harvey Friedman]

In posting 121:Discrepancy Theory/4-revised, 11:34AM  1/31/02, I wrote:

>A1 containedin Ai delta fjAk containedin Ar delta f1Ak+1.

I should have written

A1 containedin Ai delta fjAk containedin Am delta f1Ak+1.

#######################################

Now for some very elementary looking number theory that explodes.

THEOREM 1. There are only finitely many sets of positive integers, where
each element exceeding 13 divides the product of all smaller elements, but
does not divide any larger elements.

THEOREM 2. For each k >= 0 there are only finitely many sets of postiive
integers, where each element exceeding k divides the product of all smaller
elements, but does not divide any larger elements.

For each k >= 0 let #(k) be the largest number of elements in such a set of
positive integers.

k = 0. {1}. #(0) = 1.
k = 1. {1]. #(1) = 1.
k = 2. {1,2}, #(2) = 2.
k = 3. {1,2,3,6,9}. #(3) = 5.
k = 4. {1,2,3,4,24,36,162,891}. #(4) = 8.
k = 5. #(5) >= 37.
k = 6. #(6) >= 26,948.
k = 7. #(7) >= 2^2^2^60.
k = 11. #(11) > E*(1000) = A3(1000) = the 3rd level of the Ackermann
hierarchy of functions at 1000 = an exponential stack of 1000 2's.
k = 13. #(13) > A4(5000).

THEOREM 3. The function #(k) grows like the Ackermann function.

**********************************************

I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.

This is the 123rd in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones counting from #100 are:

100:Boolean Relation Theory IV corrected  3/21/01  11:29AM
101:Turing Degrees/1  4/2/01  3:32AM
102: Turing Degrees/2  4/8/01  5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01  11:10AM
104:Turing Degrees/3   4/12/01  3:19PM
105:Turing Degrees/4   4/26/01  7:44PM
106.Degenerative Cloning  5/4/01  10:57AM
107:Automated Proof Checking  5/25/01  4:32AM
108:Finite Boolean Relation Theory   9/18/01  12:20PM
109:Natural Nonrecursive Sets  9/26/01  4:41PM
110:Communicating Minds I  12/19/01  1:27PM
111:Communicating Minds II  12/22/01  8:28AM
112:Communicating MInds III   12/23/01  8:11PM
113:Coloring Integers  12/31/01  12:42PM
114:Borel Functions on HC  1/1/02  1:38PM
115:Aspects of Coloring Integers  1/3/02  10:02PM
116:Communicating Minds IV  1/4/02  2:02AM
117:Discrepancy Theory   1/6/02  12:53AM
118:Discrepancy Theory/2   1/20/02  1:31PM
119:Discrepancy Theory/3  1/22.02  5:27PM
120:Discrepancy Theory/4  1/26/02  1:33PM
121:Discrepancy Theory/4-revised  1/31/02  11:34AM
122:Communicating Minds IV-revised  1/31/02  2:48PM