[FOM] 788: Revolutionary Possibilities/7
Harvey Friedman
hmflogic at gmail.com
Thu Feb 1 00:02:18 EST 2018
More cleaning, fine tuning, clearer strategy, error correction, etcetera.
1. INTRODUCTION.
2. RAMSEY FACTOR THEORY.
2.1. FINITE RANGE.
2.2. ARBITRARY.
3. APPLICATIONS - QUADRATIC RESIDUES.
4. FUTURE POSSIBILITIES.
1. INTRODUCTION
There is a new or "new" form of Ramsey theory which we call
RAMSEY FACTOR THEORY
This is a one dimensional theory where the input object is an f:Z+
into Z+ and the output object is a positive integer t.
Ramsey Factor Theory is a hybrid in the sense that the input object is
not number theoretic but the output object is simply a positive
integer and we only look at its set of FACTORS.
Because it is hybrid, we can still prove results with adaptations of
known techniques from ordinary Ramsey theory - including both the
classical finite and infinite 1930 Ramsey theorems.
Also Ramsey Factor Theory breaks new very thematic ground in PA Incompleteness.
The REVOLUTIONARY POSSIBILITIES might come about when we specialize to
NUMBER THEORETIC f:Z+ into Z+. Perhaps the most basic deep case is the
quadratic residue functions
t^2 mod n
where n is a fixed positive integer.
The use of such number theoretic and other specially interesting
functions for the f:N into N does a number of things.
1. The theorems are still true, because they are true for ANY f:Z+ into Z+.
2. We now have a purely number theoretic theorem - and maybe the
beginning of a long process of generating many more yet more
interesting purely number theoretic theorems.
3. We can run computer studies trying to actually find the output number t.
4. In fact, the theorems tell us that there exists t with a certain
property, a property which can be scaled back and made weaker. I.e.,
the property can be SCORED. We can run the computer in order to look
for t with a good but not perfect score, knowing that there exists t
with a perfect score.
5. REVOLUTIONARY - we know that Ramsey Factor Theory is exotic with
monstrous lower bounds, and even exhibits PA Incompleteness. Could
this ALSO be true for these purely number theoretic consequences?
Unless otherwise indicated, all integers are positive. The factors of
an integer are required to be positive. It is convenient to define a
FACTOR SET as the set of all positive factors of some positive
integers.
2. RAMSEY FACTOR THEORY
Here is the main Thematic Template.
TEMPLATE A. Every f:Z+ into Z+ has relatively few values on some large
factor sets.
We naturally separate into the case where f has finite range, and the
arbitrary case.
2.1. FINITE RANGE
Here we focus on
TEMPLATE B. Every f:Z+ into Z+ with finite range has relatively few
values on arbitrarily large factor sets.
THEOREM 2.1.1. For all k, every f:Z+ into Z+ with finite range has at
most ceiling(log(k))+1 values on some >= k element factor set. For all
k, ceiling(log(k))+1 is best possible.
If we eliminate >= from Theorem 2.1.1, then matters are much more delicate.
DEFINITION 2.1.1. alpha:Z+ into Z+ is defined as follows. alpha(k) is
least such that every f:Z+ into Z+ with finite range has at most
alpha(k) values on some k element factor set.
We have an algorithm for computing alpha(k) that is rather technical,
involving the various factorizations of k. We computed the first 16
values of alpha:
alpha(1) = 1
alpha(2) = 2
alpha(3) = 3
alpha(4) = 3
alpha(5) = 5
alpha(6) = 5
alpha(7) = 7
alpha(8) = 4
alpha(9) = 7
alpha(10) = 9
alpha(11) = 11
alpha(12) = 7
alpha(13) = 13
alpha(14) = 13
alpha(15) = 15
alpha(16) = 5
NOTE: In https://cs.nyu.edu/pipermail/fom/2018-January/020829.html I
miscalculated alpha(9).
We now make some general computations.
THEOREM 2.1.2. alpha(2^k) = k+1. alpha(3(2^k)) = 2k+1. alpha(9(2^k)) =
5k-3. alpha(k) = k if k is prime.
A nice closed formula for alpha(3^k) is probably not possible.
However, some reasonable kind of multiple recurrence should work.
Very large numbers come into this picture as follows. A factor set is
<= s if and only if its greatest element is <= s.
DEFINITION 2.1.2. Define beta(k,n) to be least such that every f:Z+
into {1,...,n} has at most beta(k,n) values on some k element factor
set that is <= beta(k,n). Define gamma(k,n) to be least such that
every f:Z+ into {1,...,n} has at most gamma(k,n) values on some >= k
element factor set. that is <= gamma(k,n).
THEOREM 2.1.3. beta(k,2) is not dominated by any fixed length
exponential stack. gamma(k,2) eventually dominates every fixed length
exponential stack.
2.2. LOW VALUES
We now put no restriction on f:N into N. We count the number of LOW
values of f on factor sets.
DEFINITION 2.2.1. Let f:Z+ into Z+ and S containedin Z+. A low value
of f on S is a value of f that is at most min(S\{1}) or |S|.
THEOREM 2.2.1. For all k, every f:Z+ into Z+ has at most
ceiling(log(k))+1 low values on some >= k element factor set. For all
k, ceiling(log(k))+1 is best possible.
NOTE: Remarkably, Theorem 2.2.1 has the same best possible quantity
that Theorem 2.1.1 has!
Theorem 2.2.1 requires an infinite argument to prove. It is provably
equivalent to 1-Con(PA) over RCA_0.
There is a strong uniformity in Theorem 2.2.1.
THEOREM 2.2.2. In Theorem 2.2.1, there is an upper bound on the
(maximum element of the) factor set that depends only on k and not on
f. The resulting Pi02 sentence is equivalent to 1-Con(PA) over EFA,
with associated growth rate just beyond the <epsilon recursive
functions.
3. APPLICATIONS - QUADRATIC RESIDUES
We now apply Theorems 2.1.1 and 2.2.1 to particular f:Z+ into Z+ from
number theory.
THEOREM 3.1. For all k,n, some >=k element factor set has at most
ceiling(log(k))+1 quadratic residues mod n.
This explicitly Pi02 sentence immediately follows from Theorem 2.1.1.
We can run computer investigations for small k,n. I suspect that even
for very small k,n, we will not be able to verify Theorem 3.1 as the
least factor set will have too high a max. HOWEVER, we can grade what
we find, by counting the number of quadratic residues mod n, and
seeing how much bigger the count is than ceiling(log(k))+1.
We can ask whether we really get iterated exponential behavior in
Theorem 3.1 as we know we do with Theorem 2.1.1, even with n = 2. With
Theorem 3.1, for extremely small n like 2, presumably we can fully
take the mystery out of Theorem 3.1.
THEOREM 3.2. For all k,n, some >=k element factor set has at most
ceiling(log(k))+1 quadratic residues mod the first prime after
min(S\{1}) and k.
We can run the same kind of computer investigations here with the same
grading scheme. We can ask whether Theorem 3.2 is still independent of
PA, and has the associated growth rate greater than that of all
<epsilon_0 recursive functions.
4. FUTURE POSSIBILITIES
Presumably, there is a good statistical form of these theorems with
ceiling(log(k))+1 raised considerably - assuming f is random from
{1,...,m} into {1,..,n}, m >> n, or f is random from {1,...,n} into
{1,...,n}, n sufficiently large. BUT even so, this doesn't mean that
the residue functions behave randomly in the appropriate sense even if
they appear to satisfy statistical tests in computer runs. And even if
they do behave randomly, we may or may not be able to apply a
randomness form of the theorems. So these situation needs to be
clarified on several fronts, including of course, some actual computer
investigations.
These are already pretty simple and satisfying. However, we have no
doubt that they can be improved on considerably in the arena of
elementary number theory.
Furthermore, there is the matter of giving number theoretic
interpretations of our Emulation Function Theory, which goes well
beyond ZFC. Emulation Function Theory has now taken the form of a
related kind of Ramsey Theory, with the added ingredient of support
maximality. If successful, we would have a series of applications of
large cardinals to number theory and perhaps other finite mathematics,
although as it is the case here, we would not know if the large
cardinals can be removed.
************************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 788th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-699 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
711: Large Cardinals and Continuations/21 9/18/16 10:42AM
712: PA Incompleteness/1 9/23/16 1:20AM
713: Foundations of Geometry/1 9/24/16 2:09PM
714: Foundations of Geometry/2 9/25/16 10:26PM
715: Foundations of Geometry/3 9/27/16 1:08AM
716: Foundations of Geometry/4 9/27/16 10:25PM
717: Foundations of Geometry/5 9/30/16 12:16AM
718: Foundations of Geometry/6 101/16 12:19PM
719: Large Cardinals and Emulations/22
720: Foundations of Geometry/7 10/2/16 1:59PM
721: Large Cardinals and Emulations//23 10/4/16 2:35AM
722: Large Cardinals and Emulations/24 10/616 1:59AM
723: Philosophical Geometry/8 10/816 1:47AM
724: Philosophical Geometry/9 10/10/16 9:36AM
725: Philosophical Geometry/10 10/14/16 10:16PM
726: Philosophical Geometry/11 Oct 17 16:04:26 EDT 2016
727: Large Cardinals and Emulations/25 10/20/16 1:37PM
728: Philosophical Geometry/12 10/24/16 3:35PM
729: Consistency of Mathematics/1 10/25/16 1:25PM
730: Consistency of Mathematics/2 11/17/16 9:50PM
731: Large Cardinals and Emulations/26 11/21/16 5:40PM
732: Large Cardinals and Emulations/27 11/28/16 1:31AM
733: Large Cardinals and Emulations/28 12/6/16 1AM
734: Large Cardinals and Emulations/29 12/8/16 2:53PM
735: Philosophical Geometry/13 12/19/16 4:24PM
736: Philosophical Geometry/14 12/20/16 12:43PM
737: Philosophical Geometry/15 12/22/16 3:24PM
738: Philosophical Geometry/16 12/27/16 6:54PM
739: Philosophical Geometry/17 1/2/17 11:50PM
740: Philosophy of Incompleteness/2 1/7/16 8:33AM
741: Philosophy of Incompleteness/3 1/7/16 1:18PM
742: Philosophy of Incompleteness/4 1/8/16 3:45AM
743: Philosophy of Incompleteness/5 1/9/16 2:32PM
744: Philosophy of Incompleteness/6 1/10/16 1/10/16 12:15AM
745: Philosophy of Incompleteness/7 1/11/16 12:40AM
746: Philosophy of Incompleteness/8 1/12/17 3:54PM
747: PA Incompleteness/2 2/3/17 12:07PM
748: Large Cardinals and Emulations/30 2/15/17 2:19AM
749: Large Cardinals and Emulations/31 2/15/17 2:19AM
750: Large Cardinals and Emulations/32 2/15/17 2:20AM
751: Large Cardinals and Emulations/33 2/17/17 12:52AM
752: Emulation Theory for Pure Math/1 3/14/17 12:57AM
753: Emulation Theory for Math Logic 3/10/17 2:17AM
754: Large Cardinals and Emulations/34 3/12/17 12:34AM
755: Large Cardinals and Emulations/35 3/12/17 12:33AM
756: Large Cardinals and Emulations/36 3/24/17 8:03AM
757: Large Cardinals and Emulations/37 3/27/17 2:39AM
758: Large Cardinals and Emulations/38 4/10/17 1:11AM
759: Large Cardinals and Emulations/39 4/10/17 1:11AM
760: Large Cardinals and Emulations/40 4/13/17 11:53PM
761: Large Cardinals and Emulations/41 4/15/17 4:54PM
762: Baby Emulation Theory/Expositional 4/17/17 1:23AM
763: Large Cardinals and Emulations/42 5/817 2:18AM
764: Large Cardinals and Emulations/43 5/11/17 12:26AM
765: Large Cardinals and Emulations/44 5/14/17 6:03PM
766: Large Cardinals and Emulations/45 7/2/17 1:22PM
767: Impossible Counting 1 9/2/17 8:28AM
768: Theory Completions 9/4/17 9:13PM
769: Complexity of Integers 1 9/7/17 12:30AM
770: Algorithmic Unsolvability 1 10/13/17 1:55PM
771: Algorithmic Unsolvability 2 10/18/17 10/15/17 10:14PM
772: Algorithmic Unsolvability 3 Oct 19 02:41:32 EDT 2017
773: Goedel's Second: Proofs/1 Dec 18 20:31:25 EST 2017
774: Goedel's Second: Proofs/2 Dec 18 20:36:04 EST 2017
775: Goedel's Second: Proofs/3 Dec 19 00:48:45 EST 2017
776: Logically Natural Examples 1 12/21 01:00:40 EST 2017
777: Goedel's Second: Proofs/4 12/28/17 8:02PM
778: Goedel's Second: Proofs/5 12/30/17 2:40AM
779: End of Year Claims 12/31/17 8:03PM
780: One Dimensional Incompleteness/1 1/4/18 1:14AM
781: One Dimensional Incompleteness/2 1/6/18 11:25PM
782: Revolutionary Possibilities/1 1/12/18 11:26AM
783: Revolutionary Possibilities/2 1/20/18 9:43PM
784: Revolutionary Possibilities/3 1/21/18 2:59PM
785: Revolutionary Possibilities/4 1/22/18 12:38AM
786: Revolutionary Possibilities/5 1/24/18 12:15AM
787: Revolutionary Possibilities/6 1/25/18 4:09AM
Harvey Friedman
More information about the FOM
mailing list