The physical limits of computation inspire an open problem that concerns abstract computable sets X ⊆ N and cannot be formalized in the set theory ZFC as it refers to our current knowledge on X Sławomir Kurpaska, Apoloniusz Tyszka Abstract. Let f (1) = 2, f (2) = 4, and let f (n + 1) = f (n)! for every integer n > 2. Edmund Landau's conjecture states that the set Pn2+1 of primes of the form n2 + 1 is infinite. Landau's conjecture implies the following unproven statement Φ: card(Pn2+1) < ω⇒ Pn2+1 ⊆ [2, f (7)]. Let B denote the system of equations: { xi! = xk : i, k ∈ {1, . . . , 9} } ∪ { xi * x j = xk : i, j, k ∈ {1, . . . , 9} } . We write down a systemU ⊆ B of 9 equations which has exactly two solutions in positive integers, namely (1, . . . , 1) and ( f (1), . . . , f (9)). Let Ψ denote the statement: if a system S ⊆ B has at most finitely many solutions in positive integers x1, . . . , x9, then each such solution (x1, . . . , x9) satisfies x1, . . . , x9 6 f (9). We write down a system A ⊆ B of 8 equations. Theorem 1. The statement Ψ restricted to the system A is equivalent to the statement Φ. Open Problem. Is there a set X ⊆ N that satisfies conditions (1)(5)? (1) There are many elements of X and it is conjectured that X is infinite. (2) No known algorithm decides the finiteness/infiniteness of X. (3) There is a known algorithm that for every k ∈ N decides whether or not k ∈ X. (4) There is a known algorithm that computes an integer n satisfying card(X) < ω⇒ X ⊆ (−∞, n]. (5) There is a naturally defined condition C, which can be formalized in ZFC, such that for almost all k ∈ N, k satisfies the condition C if and only if k ∈ X. The simplest known such condition C defines in N the set X. Condition (5) excludes artificially defined set X from the statement (i). We prove: (i) the set X = { k ∈ N : ( f (7) < k)⇒ ( f (7), k) ∩ Pn2+1 , ∅ } satisfies conditions (1)(4); (ii) the statement Φ implies that the set X = {1} ∪ Pn2+1 satisfies conditions (1)(5). Proving Landau's conjecture will disprove the statements (i) and (ii). Theorem 2. No set X ⊆ N will satisfy conditions (1)(4) forever, if for every algorithm with no inputs that operates on integers, at some future day, a computer will be able to execute this algorithm in 1 second or less. Physics disproves the assumption of Theorem 2. 2020 Mathematics Subject Classification: 03D20. Key words and phrases: algorithm with no inputs that operates on integers, argument against logicism, artificially defined set X ⊆ N, computable set X ⊆ N, conjecturally infinite set X ⊆ N, current knowledge on X, naturally defined set X ⊆ N, physical limits of computation, primes of the form n2 + 1. 2 1. Basic definitions and the philosophical goal of the article Logicism is a programme in the philosophy of mathematics. It is mainly characterized by the contention that mathematics can be reduced to logic, provided that the latter includes set theory, see [3, p. 199]. Definition 1. Conditions (1)(5) concern sets X ⊆ N. (1) There are many elements of X and it is conjectured that X is infinite. (2) No known algorithm decides the finiteness/infiniteness of X. (3) There is a known algorithm that for every k ∈ N decides whether or not k ∈ X. (4) There is a known algorithm that computes an integer n satisfying card(X) < ω⇒ X ⊆ (−∞, n]. (5) There is a naturally defined condition C, which can be formalized in ZFC, such that for almost all k ∈ N, k satisfies the condition C if and only if k ∈ X. The simplest known such condition C defines in N the set X. Condition (5) excludes artificially defined set X from Statement 2. Definition 2. We say that an integer n is a threshold number of a set X ⊆ N, if card(X) < ω⇒ X ⊆ (−∞, n], cf. [7] and [8]. If a set X ⊆ N is empty or infinite, then any integer n is a threshold number of X. If a set X ⊆ N is non-empty and finite, then the all threshold numbers of X form the set [max(X),∞) ∩ N. Edmund Landau's conjecture states that the set Pn2+1 of primes of the form n2 + 1 is infinite, see [4]–[6]. Definition 3. Let Φ denote the following unproven statement: card(Pn2+1) < ω⇒ Pn2+1 ⊆ (−∞, (((24!)!)!)!] Landau's conjecture implies the statement Φ. In Section 4, we heuristically justify the statement Φ without invoking Landau's conjecture. Statement 1. No known algorithm computes an integer k such that card(Pn2+1) < ω⇒ Pn2+1 ⊆ (−∞, k] Proving the statement Φ will disprove Statement 1. Statement 1 cannot be formalized in ZFC because it refers to the current mathematical knowledge. The same is true for Statements 2–3 and Open Problem 1 in the next sections. It argues against logicism as Open Problem 1 concerns abstract computable sets X ⊆ N. 2. The physical limits of computation inspire Open Problem 1 Definition 4. Let β = (((24!)!)!)!. Lemma 1. log2(log2(log2(log2(log2(log2(log2(β))))))) ≈ 1.42298. Proof. We ask Wolfram Alpha at http://wolframalpha.com.  3 Statement 2. The setX = {k ∈ N : (β < k)⇒ (β, k)∩Pn2+1 , ∅} satisfies conditions (1)(4). Proof. Condition (1) holds as X ⊇ {0, . . . , β} and the set Pn2+1 is conjecturally infinite. By Lemma 1, due to known physics we are not able to confirm by a direct computation that some element of Pn2+1 is greater than β, see [2]. Thus condition (2) holds. Condition (3) holds trivially. Since the set {k ∈ N : (β < k) ∧ (β, k) ∩ Pn2+1 , ∅} is empty or infinite, the integer β is a threshold number of X. Thus condition (4) holds.  Proving Landau's conjecture will disprove Statement 2. Open Problem 1. Is there a set X ⊆ N that satisfies conditions (1)(5)? Theorem 1. No set X ⊆ N will satisfy conditions (1)-(4) forever, if for every algorithm with no inputs that operates on integers, at some future day, a computer will be able to execute this algorithm in 1 second or less. Proof. The proof goes by contradiction. Since conditons (2)(4) will hold forever, the algorithm in Figure 1 never terminates and sequentially prints the following sentences: n + 1 < X, n + 2 < X, n + 3 < X, . . . (T) Yes No Start k := 1 Is n+k ∈ X? Print "n + k < X" Print "The set X is infinite" k := k + 1Stop Fig. 1 An algorithm whose execution never terminates if the set X is finite The sentences from the sequence (T) and our assumption imply that for every integer m > n computed by a known algorithm, at some future day, a computer will be able to confirm in 1 second or less that (n,m] ∩ X = ∅. Thus, at some future day, numerical evidence will support the conjecture that the set X is finite, contrary to the conjecture in condition (1).  Physics disproves the assumption of Theorem 1. 4 3. Number-theoretic statements Ψn Let f (1) = 2, f (2) = 4, and let f (n + 1) = f (n)! for every integer n > 2. LetU1 denote the system of equations which consists of the equation x1! = x1. For an integer n > 2, letUn denote the following system of equations: x1! = x1 x1 * x1 = x2 ∀i ∈ {2, . . . , n − 1} xi! = xi+1 The diagram in Figure 2 illustrates the construction of the systemUn. ! x1 squaring x2 ! x3 . . . xn−1 ! xn Fig. 2 Construction of the systemUn Lemma 2. For every positive integer n, the systemUn has exactly two solutions in positive integers, namely (1, . . . , 1) and ( f (1), . . . , f (n)). Let Bn denote the following system of equations:{ xi! = xk : i, k ∈ {1, . . . , n} } ∪ { xi * x j = xk : i, j, k ∈ {1, . . . , n} } For a positive integer n, let Ψn denote the following statement: if a system of equations S ⊆ Bn has at most finitely many solutions in positive integers x1, . . . , xn, then each such solution (x1, . . . , xn) satisfies x1, . . . , xn 6 f (n). The statement Ψn says that for subsystems of Bn with a finite number of solutions, the largest known solution is indeed the largest possible. The statements Ψ1 and Ψ2 hold trivially. There is no reason to assume the validity of the statement ∀n ∈ N \ {0} Ψn. Theorem 2. For every statement Ψn, the bound f (n) cannot be decreased. Proof. It follows from Lemma 2 becauseUn ⊆ Bn.  Theorem 3. For every integer n > 2, the statement Ψn+1 implies the statement Ψn. Proof. If a system S ⊆ Bn has at most finitely many solutions in positive integers x1, . . . , xn, then for every integer i ∈ {1, . . . , n} the system S ∪ {xi! = xn+1} has at most finitely many solutions in positive integers x1, . . . , xn+1. The statement Ψn+1 implies that xi! = xn+1 6 f (n + 1) = f (n)!. Hence, xi 6 f (n).  Theorem 4. Every statement Ψn is true with an unknown integer bound that depends on n. Proof. For every positive integer n, the system Bn has a finite number of subsystems.  5 4. A conjectural solution to Open Problem 1 Lemma 3. For every positive integers x and y, x! * y = y! if and only if (x + 1 = y) ∨ (x = y = 1) Lemma 4. (Wilson's theorem, [1, p. 89]). For every integer x > 2, x is prime if and only if x divides (x − 1)! + 1. LetA denote the following system of equations: x2! = x3 x3! = x4 x5! = x6 x8! = x9 x1 * x1 = x2 x3 * x5 = x6 x4 * x8 = x9 x5 * x7 = x8 Lemma 3 and the diagram in Figure 3 explain the construction of the systemA. x1 squaring x2 +1 or x2 = x5 = 1 x5 ! x6 ! x3 ! x4 +1 or x3 = x8 = 1 x8 ! x9 x5 * x7 = x8x3 * x5 = x6 x4 * x8 = x9 Fig. 3 Construction of the systemA 6 Lemma 5. For every integer x1 > 2, the system A is solvable in positive integers x2, . . . , x9 if and only if x21 + 1 is prime. In this case, the integers x2, . . . , x9 are uniquely determined by the following equalities: x2 = x21 x3 = (x21)! x4 = ((x21)!)! x5 = x21 + 1 x6 = (x21 + 1)! x7 = (x21)! + 1 x21 + 1 x8 = (x21)! + 1 x9 = ((x21)! + 1)! Proof. By Lemma 3, for every integer x1 > 2, the system A is solvable in positive integers x2, . . . , x9 if and only if x21 + 1 divides (x 2 1)! + 1. Hence, the claim of Lemma 5 follows from Lemma 4.  Lemma 6. There are only finitely many tuples (x1, . . . , x9) ∈ (N \ {0})9, which solve the systemA and satisfy x1 = 1. This is true as every such tuple (x1, . . . , x9) satisfies x1, . . . , x9 ∈ {1, 2}. Proof. The equality x1 = 1 implies that x2 = x1 * x1 = 1. Hence, x3 = x2! = 1. Therefore, x4 = x3! = 1. The equalities x5! = x6 and x5 = 1 * x5 = x3 * x5 = x6 imply that x5, x6 ∈ {1, 2}. The equalities x8! = x9 and x8 = 1 * x8 = x4 * x8 = x9 imply that x8, x9 ∈ {1, 2}. The equality x5 * x7 = x8 implies that x7 = x8 x5 ∈ { 1 1 , 1 2 , 2 1 , 2 2 } ∩ N = {1, 2}.  Conjecture 1. The statement Ψ9 is true when is restricted to the systemA. Theorem 5. Conjecture 1 proves the following implication: if there exists an integer x1 > 2 such that x21 + 1 is prime and greater than f (7), then the set Pn2+1 is infinite. Proof. Suppose that the antecedent holds. By Lemma 5, there exists a unique tuple (x2, . . . , x9) ∈ (N\{0})8 such that the tuple (x1, x2, . . . , x9) solves the systemA. Since x21 + 1 > f (7), we obtain that x 2 1 > f (7). Hence, (x 2 1)! > f (7)! = f (8). Consequently, x9 = ((x21)! + 1)! > ( f (8) + 1)! > f (8)! = f (9) Conjecture 1 and the inequality x9 > f (9) imply that the system A has infinitely many solutions (x1, . . . , x9) ∈ (N \ {0})9. According to Lemmas 5 and 6, the set Pn2+1 is infinite.  Theorem 6. Conjecture 1 implies the statement Φ. Proof. It follows from Theorem 5 and the equality f (7) = (((24!)!)!)!.  7 Theorem 7. The statement Φ implies Conjecture 1. Proof. By Lemmas 5 and 6, if positive integers x1, . . . , x9 solve the systemA, then (x1 > 2) ∧ (x5 = x21 + 1) ∧ (x5 is prime) or x1, . . . , x9 ∈ {1, 2}. In the first case, Lemma 5 and the statement Φ imply that the inequality x5 6 (((24!)!)!)! = f (7) holds when the system A has at most finitely many solutions in positive integers x1, . . . , x9. Hence, x2 = x5 − 1 < f (7) and x3 = x2! < f (7)! = f (8). Continuing this reasoning in the same manner, we can show that every xi does not exceed f (9).  Statement 3. The statement Φ implies that the set X = {1} ∪ Pn2+1 satisfies conditions (1)(5). Proof. The set Pn2+1 is conjecturally infinite. There are 2199894223892 primes of the form n2 + 1 in the interval [2, 1028), see [5]. These two facts imply condition (1). By Lemma 1, due to known physics we are not able to confirm by a direct computation that some element of {1} ∪ Pn2+1 is greater than f (7) = (((24!)!)!)! = β, see [2]. Thus condition (2) holds. Condition (3) holds trivially. The statement Φ implies that β is a threshold number of X = {1} ∪ Pn2+1. Thus condition (4) holds. The following condition: k − 1 is a square and k has no divisors greater than 1 and smaller than k defines in N the set {1} ∪ Pn2+1. This proves condition (5).  Proving Landau's conjecture will disprove Statement 3. Acknowledgment. Sławomir Kurpaska prepared three diagrams in TikZ. Apoloniusz Tyszka wrote the article. References [1] M. Erickson, A. Vazzana, D. Garth, Introduction to number theory, 2nd ed., CRC Press, Boca Raton, FL, 2016. [2] S. Lloyd, Ultimate physical limits to computation, Nature 406 (2000), 1047–1054, http: //doi.org/10.1038/35023282. [3] W. Marciszewski, Logic, modern, history of, in: Dictionary of logic as applied in the study of language (ed. W. Marciszewski), pp. 183–200, Springer, Dordrecht, 1981. [4] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, A002496, Primes of the form n2 + 1, http://oeis.org/A002496. [5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, A083844, Number of primes of the form x2 + 1 < 10n, http://oeis.org/A083844. [6] Wolfram MathWorld, Landau's Problems, http://mathworld.wolfram.com/ LandausProblems.html. [7] A. A. Zenkin, Super-induction method: logical acupuncture of mathematical infinity, Twentieth World Congress of Philosophy, Boston, MA, August 10–15, 1998, http: //www.bu.edu/wcp/Papers/Logi/LogiZenk.htm. 8 [8] A. A. Zenkin, Superinduction: new logical method for mathematical proofs with a computer, in: J. Cachro and K. Kijania-Placek (eds.), Volume of Abstracts, 11th International Congress of Logic, Methodology and Philosophy of Science, August 20–26, 1999, Cracow, Poland, p. 94, The Faculty of Philosophy, Jagiellonian University, Cracow, 1999. Sławomir Kurpaska Technical Faculty Hugo Kołłataj University Balicka 116B, 30-149 Kraków, Poland E-mail: rtkurpas@cyf-kr.edu.pl Apoloniusz Tyszka Technical Faculty Hugo Kołłataj University Balicka 116B, 30-149 Kraków, Poland E-mail: rttyszka@cyf-kr.edu.pl