A condition Γ(X) (which conjecturally holds for X={1}∪P(n^2+1)) expresses the current knowledge on a set X⊆N and strengthens the implication (the infiniteness of X is conjectured and unproven) ∧ (card(X)<ω ⇒ X⊆[0,(((24!)!)!)!]), whereas the statement ∃ X⊆N Γ(X) (which is proven) fails for everyone who for every terminating algorithm with no input knows its output

Download Edit this record How to cite View on PhilPapers
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)⊆(-∞,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 down a system U⊆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 x_1,...,x_9, then each such solution (x_1,...,x_9) satisfies x_1,...,x_9≤f(9). We write down a system A⊆B of 8 equations. The statement Ψ restricted to the system A 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 existence is constructive and currently known to us). 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 with no inputs returns the logical value of the statement card(X)=ω. (3) There is a known algorithm that for every k∈N decides whether or not k∈X. (4) There is a known algorithm with no inputs that computes an integer n satisfying card(X)<ω ⇒ X⊆(-∞,n]. (5) There is a known condition C, which can be formalized in ZFC, such that for all except at most finitely many 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. *** The set X={k∈N: (f(7)<k) ⇒ (f(7),k)∩P(n^2+1)≠∅} satisfies conditions (1)-(4). A more complicated set X⊆N satisfies conditions (1)-(5). No set X⊆N will satisfy conditions (1)-(4) forever, if for every algorithm with no inputs, 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. The statement Φ implies that conditions (1)-(5) hold for X={1}∪P(n^2+1). To define the condition Γ(X) from the title, we formulate condition (4) for n=(((24!)!)!)! and take the conjunction of conditions (1)-(4) or the conjunction of conditions (1)-(5).
PhilPapers/Archive ID
Upload history
First archival date: 2017-10-17
Latest version: 169 (2021-01-15)
View other versions
Added to PP index

Total views
853 ( #4,592 of 55,822 )

Recent downloads (6 months)
126 ( #4,353 of 55,822 )

How can I increase my downloads?

Downloads since first upload
This graph includes both downloads from PhilArchive and clicks on external links on PhilPapers.