[FOM] 790: Revolutionary Possibilities/9
Harvey Friedman
hmflogic at gmail.com
Fri Feb 2 03:07:24 EST 2018
We continue to make simplifications and improvements. Now they have
become much simpler again, we systemically restate the most relevant
part of the entire current situation. We don't need as elaborate an
explanation as in
https://cs.nyu.edu/pipermail/fom/2018-January/020829.html because of
these new simplifications and improvements.
1. Factor Counting Theory.
2. Residue Factor Counting Theory.
3. Computer Experiments.
4. The Future.
COUNTING, FACTORS, AND RESIDUES
1. FACTOR COUNTING THEORY
DEFINITION 1.1. All integers, unless indicated otherwise, are
positive. Z+ is the set of all positive integers. The factors of n are
the positive m|n, which always includes 1,n. A factor set is the set
of factors of some positive integer.
Factor sets played a significant role in early number theory. E.g.,
they proved theorems about what we can call perfect factor sets, which
are factor sets whose sum is twice its greatest element. It is of
course still open if there are infinitely many perfect factor sets, or
any perfect factor sets whose elements are all odd.
THEOREM 1.1. For all k,n and f:Z+ into Z+, there is a factor set with
exactly k prime elements, and at most k+1 values <=n. There is an
upper bound on the largest element of the required factor set that
depends only on k,n, and not on f. The best upper bound eventually
dominates every fixed exponential stack, even for fixed n = 2. The
corresponding Pi02 form, the statement is equivalent to SEFA (super
exponential function arithmetic) over EFA (exponential function
arithmetic).
THEOREM 1.2. for all k and f:Z+ into Z+, there is a factor set with
exactly k primes, and at most k+1 values less than its least prime
element > k. There is an upper bound on the largest element of the
required factor set that depends only on k, and not on f. The best
upper bound eventually dominates every < epsilon_0 recursive function.
In the corresponding Pi02 form, the statement is equivalent to
1-Con(PA) over EFA.
We also have this variant with an extra parameter.
THEOREM 1.3. for all n > k and f:Z+ into N, there is a factor set
with exactly k primes, and at most k+1 values less than its least
prime element > n. There is an upper
bound on the largest element of the required factor set that depends
only on k,n, and not on f. The best upper bound eventually dominates
every < epsilon_0 recursive function. In the corresponding Pi02 form,
the statement is equivalent to 1-Con(PA) over EFA.
In Theorems 1.1-1.3, we use the simplest factor sets with exactly k
primes, namely the product of primes p_1 < ... < p_k, where these
primes need to be chosen with care, and generally we need each p_i is
greater than the product of all p_j, j < i.
Theorems 1.1 - 1.3 become much more delicate combinatorially if we
impose a condition on the number of elements of the factor set, or a
condition on both the number of elements of the factor set and the
number of prime elements of the factor set.
A. Impose a condition, like we have done above, on the number of
primes in the factor set, and not on the number of elements of the
factor set.
B. Impose a condition on the number of elements of the factor set
only, and not on the number of primes in the factor set. The condition
can be either exact or a lower bound.
C. Impose a condition on the number of elements of the factor set and
a condition on the number of primes in the factor set. These can be
either exact or a lower bound.
Note that in Theorems 1.1-1.3, we have been using A and k+1. For B,C
we have to adjust k+1. We will not pursue these more delicate versions
in this posting. But for a modest beginning, see the alpha function of
https://cs.nyu.edu/pipermail/fom/2018-February/020836.html
2. RESIDUE FACTOR COUNTING THEORY
DEFINITION 2.1. The quadratic residues mod n of a factor set are the
quadratic residues mod n of its elements. Thus quadratic residues mod
n are among 0,1,...,n-1.
THEOREM 2.1. For all k,n, some factor set with exactly k primes has at
most k+1 quadratic residues mod n.
THEOREM 2.2. For all k, some factor set with exactly k primes has at
most k+1 quadratic residues modulo its least prime element > k.
THEOREM 2.3. For all k,n, some factor set with exactly k primes has at
most k+1 quadratic residues modulo its least prime element > n.
We prove Theorem 2.1 in SEFA (super exponential function arithmetic)
with an iterated exponential upper bound. Can Theorem 2.1 be proved in
EFA?
We prove Theorems 2.2, 2.3 in EFA + 1-Con(PA) - i.e., somewhat more
than Peano Arithmetic - with an epsilon_0 recursive upper bound. Can
Theorem 2.1 or 2.2 be proved in PA?
I am not competent to judge if there is enough known number theory
that controls quadratic residues as used here in order to give normal
proofs of Theorems 2.1 - 2.3. Maybe ERH is relevant here.
If there is enough number theory, or the relevant number theory gets
established, then there should be no difficulties in increasing the
number theoretic difficulties here substantially, in various natural
ways - while still making these Theorems trivial consequences of the
more general combinatorial theorems in Factor Counting Theory (section
1).
3. COMPUTER EXPERIMENTS
Theorem 2.1: Starting with very small k,n, run through numbers t with
exactly k prime factors, and count the number of quadratic residues of
its elements mod n. You try to achieve as few as k+1, which is
achievable according to Theorem 2.1. See how close you get.
Theorem 2.2: Same, except use the modulus "the least prime element > k".
Theorem 2.3: Same, except use the modulus "the least prime element > n".
4. THE FUTURE
I wouldn't rule out the possibility of some versions of Residue Factor
Counting Theory where we can get rigorous lower bounds.
AMBITIOUS: Do this sort of thing for my Emulation Theory, which has
recently taken the form: every finite support limited f:Q[0,k+1] into
Q[0,k+1] has a
support maximal emulation with f(1,...,k) = f(2,...,k+1).
I.e., applications of large cardinals to number theory, with a long
series of simplifications and improvements.
************************************************************************
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 790th 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
788: Revolutionary Possibilities/7 2/1/18 2:18AM
789: Revolutionary Possibilities/8 2/1/18 9:02AM
Harvey Friedman
More information about the FOM
mailing list