[FOM] 786: Revolutionary Possibilities/5
Harvey Friedman
hmflogic at gmail.com
Wed Jan 24 12:15:52 EST 2018
RAMSEY THEORY AND RESIDUES
1. COLORINGS AND FACTORS
Thematic goal:
MINIMIZE THE NUMBER OF COLORS THAT THE POSITIVE FACTORS OF A POSITIVE
NUMBER CAN BE REQUIRED TO HAVE, GIVEN ONLY THE NUMBER OF ITS POSITIVE
FACTORS. THIS IS TO BE DONE INDEPENDENTLY OF THE COLORING.
DEFINITION 1.1. alpha(k) is the least r such that for all f:N into N
there exists positive t where the number of values of f on the exactly
k factors of t is at most r.
Obviously, alpha(k) <= k.
THEOREM 1.1. For positive k, alpha(2^k) = k+1, alpha(2^k + 1) = 2^k +
1, alpha(2^k - 1) = 2^k - 1. If positive k is not a power of 2 then
alpha(k) > log(k)+1.
It is interesting to investigate alpha(k) further. We do a certain
amount of calculations.
FIRST 16 VALUES OF alpha(n)
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) = 9
alpha(10) = 9
alpha(11) = 11
alpha(12) = 7
alpha(13) = 13
alpha(14) = 13
alpha(15) = 15
alpha(16) = 5
There are a number of numerical functions associated with alpha that
have exotic growth properties - beyond any fixed exponential stack.
2. RESIDUES AND FACTORS
GENERAL THEME. Let p be fixed (not necessary prime). Given a positive
integer, what can be say about the number of different quadratic
residues mod p of its positive factors?
DEFINITION 2.1. Let k,p be positive. gamma(k,p) is the least r such
that there exists positive t, not divisible by p, whose exactly k
factors have at most r quadratic residues mod p.
THEOREM 2.1. For all positive k,p, gamma(k,p) exists. In fact, for all
positive k, the gamma(k,p), p positive, achieves a maximum value.
There are plenty of candidates here for functions that are not bounded
by any finite stack of 2's, as in section 1. For instance, we can fix
a prime p, say, 23, and for each k look for the least t not divisible
by 23, with at least k+1 of its exactly 2^k positive factors having
the same quadratic residue mod 23. The corresponding situation in
section 1 with arbitrary 23 color colorings we know involves
indefinitely iterated exponentiation. But what about here, in this
quadratic residue situation?
Perhaps a case can be made that quadratic residues have a certain kind
of opaque randomness that proving specific facts about them like the
ones we are concerned with is as "hard" as proving them for
arbitrarily functions (with of course 0 <= f(k,p) < p). But of course
if they are "random" then Ramsey numbers are comparatively small (you
get big monochromatic sets rather easily), like, e.g.,
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r133/pdf
Another way of looking at this: It is probably known or could easily
be known that statistically the relevant higher Ramsey numbers are
low. So according to the way number theorists often talk, low numbers
in the previous paragraph would be "statistically true". However, is
it really true here?
If this is not hard enough, we can of course go to r-th power residues
instead of just quadratic residues.
There is a long history of statistical studies of quadratic and power
residues. See, e.g.,
On the Distribution of Quadratic Residues and Nonresidues Modulo a
Prime Number Author(s): René Peralta
and references therein.
3. COLORINGS AND FACTORS - AT THE PA LEVEL
THEOREM 3.1. Let f:N into N and k be a positive integer. There is an
odd positive integer t such that f has at most k+1 values below the
factorial of the second least of the exactly 2^k positive factors of
t. There is an upper bound on t that depends only on k
The above is not provable in PA but can be proved with 1-Con(PA). The
upper bound grows faster than any < epsilon_0 recursive function.
4. RESIDUES AND FACTORS - AT THE PA LEVEL
THEOREM 4.1. For all positive integers k there is an odd positive
integer t such that the number of quadratic residues modulo the
factorial of the second least of the exactly 2^k positive factors of t
is at most k+1.
We prove Theorem 4.1 in PA + 1-Con(PA) using Theorem 3.1. But is
Theorem 4.1 itself provable in PA? How does this relate to a kind of
"randomness" of quadratic residues come into play here as in the
remarks in section 2 above?
If this is not hard enough, we can of course go to r-th power residues
instead of just quadratic residues.
************************************************************************
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 786th 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
Harvey Friedman
More information about the FOM
mailing list