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 P(n^2+1) of primes of the form n^2+1 is infinite. Landau's conjecture implies the following unproven statement Φ: card(P(n^2+1))<ω ⇒ P(n^2+1)⊆[2,f(7)]. Let B denote the system of equations: {x_i!=x_k: i,k∈{1,...,9}} ∪ {x_i⋅x_j=x_k: i,j,k∈{1,...,9}}. We write some system U⊆B of 9 equations which has exactly two solutions in positive integers x_9,...,x_9, namely (1,...,1) and (f(1),...,f(9)). No known system S⊆B with a finite number of solutions in positive integers x_1, . . . , x_9 has a solution (x_1,. . .,x_9)∈(N\{0})^9 satisfying max(x_1,..., x_9)>f (9). We write some system A of 8 equations. Let Λ denote the statement: if the system A has at most finitely many solutions in positive integers x_1,...,x_9, then each such solution (x_1,...,x_9) satisfies x_1,...,x_9≤f(9). The statement Λ is equivalent to the statement Φ. This heuristically proves the statement Φ . This proof does not yield that card(P(n^2+1))=ω. Algorithms always terminate. We explain the distinction between existing algorithms (i.e. algorithms whose existence is provable in ZFC) and known algorithms (i.e. algorithms whose definition is constructive and currently known to us). For every set X⊆N, conditions (1)-(5) probably imply that X is naturally defined, where this term has only informal meaning. *** (1) A known algorithm with no input returns an integer n satisfying card(X)<ω ⇒ X⊆(-∞,n]. (2) A known algorithm for every k∈N decides whether or not k∈X. (3) No known algorithm with no input returns the logical value of the statement card(X)=ω. (4) There are many elements of X and it is conjectured that X is infinite. (5) X has the simplest definition among known sets Y⊆N with the same set of known elements. *** No known set X⊆N satisfies conditions (1)-(4) and is naturally defined or widely known in number theory. The set X= P(n^2+1) satisfies conditions (2)-(5). The statement Φ implies condition (1) for X=P(n^2+1). The set X={k∈N: (f(7)<k) ⇒ (f(7),f(k))∩P(n^2+1)≠∅} satisfies conditions (1)-(4) and does not satisfy condition (5) as the set of known elements of X equals {0,...,f(7)} . No set X⊆N will satisfy conditions (1)-(4) forever, if for every algorithm with no input, at some future day, a computer will be able to execute this algorithm in 1 second or less. The physical limits of computation disprove this assumption.
Keywords conjecturally infinite set X⊆N  constructively defined integer n satisfies: (X is finite) ⇒ X⊆(-∞,n]  current knowledge on a set X⊆N  distinction between existing algorithms and known algorithms  known elements of a set X⊆N  physical limits of computation  primes of the form n^2+1  X is decidable by a constructively defined algorithm
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

 PhilArchive page | Other versions
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Definability and Decision Problems in Arithmetic.Julia Robinson - 1949 - Journal of Symbolic Logic 14 (2):98-114.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Strengths and Weaknesses of LH Arithmetic.Chris Pollett & Randall Pruim - 2002 - Mathematical Logic Quarterly 48 (2):221-243.
A Fundamental Form of the Schrodinger Equation.Muhammad Adeel Ajaib - 2015 - Foundations of Physics 45 (12):1586-1598.
Prime Numbers and Factorization in IE1 and Weaker Systems.Stuart T. Smith - 1992 - Journal of Symbolic Logic 57 (3):1057 - 1085.
Bounding Prime Models.Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare - 2004 - Journal of Symbolic Logic 69 (4):1117 - 1142.


Added to PP index

Total views
924 ( #5,135 of 2,425,462 )

Recent downloads (6 months)
128 ( #4,560 of 2,425,462 )

How can I increase my downloads?


My notes