Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In their paper , Marker and Slaman, proved the decidability of the the theory of the natural numbers with the quantifier "for all but finitely many", One can obviously encode the question of whether any diophantine equation has an infinite number of solution as the question of whether a statement belonging to this language is satisfied by the Naturals or not. Since they proved the theory is decidable we know that such algorithm exists. My question is: Has any one tried to come up with an efficient algorithm for that ?

Link to the paper:

share|cite|improve this question
The proof of decidability shows that the theory is the same as the corresponding theory of the reals. So the algorithms for deciding sentences about the field of real numbers will also work for the naturals in this language. That gives an upper bound, at least. – Carl Mummert Jul 10 '11 at 11:43
That sounds like an answer to me, Carl (or at any rate, more than just a comment). – Gerry Myerson Jul 10 '11 at 12:29
up vote 7 down vote accepted

There is a fundamental error in this question.

For a one-variable diophantine equation, the question whether it has infinitely many solutions is rather trivial to answer (and the answer is the same over $\mathbb{Z}$ and over $\mathbb{R}$, as Carl pointed out).

The situation is different with more than one variables. The basic reason for this is that $$\exists^\infty x \exists^\infty y \cdots$$ does not mean

There are infinitely many pairs $x, y$ such that $\cdots$

It rather means,

There are infinitely many $x$ for each of which there are infinitely many $y$ such that $\cdots$

In fact, it is not possible to say there are infinitely many pairs (triples, quadruples, etc.) in the fragment of first-order logic that Marker and Slaman consider in their paper (for the reason that David pointed out).

share|cite|improve this answer
What about Goedel coding? "There are infinitely many w such that $w=2^x3^y$ and..." – Charles Jul 11 '11 at 1:01
@Charles: The paper does mention that the same result holds when adding exponentials provided Schanuel's Conjecture is true. However, even then, how do you define the corresponding logarithms without $\exists$ and $\forall$? – François G. Dorais Jul 11 '11 at 2:15
Hmm. Is there no total recursive function we can use? I wasn't able to get one, but the requirements for a Goedel numbering are pretty low. To put it another way: if I had an odd() predicate I could make a coding 2^a * (2b+1) recursively, so we can't even test the parity of a number if pairing is impossible. Right? – Charles Jul 11 '11 at 2:43
@Charles: Without $\exists$ and $\forall$ you don't even have bounded quantifiers, so it would take some serious effort to get most primitive recursive functions in this context. – François G. Dorais Jul 11 '11 at 2:48
Exponentials are a distraction, you can encode ordered pairs as "$x$ and $y$ are positive and $w = x + (x+y)(x+y+1)/2$." The trouble is that you don't have $\exists$. So you want to say "$\exists^{\infty} w \exists x \exists y : w = x + (x+y)(x+y+1)/2$ and ...", but you can't ask for $x$ and $y$ to exist. – David Speyer Jul 11 '11 at 15:28

The question of whether a diophantine equation has infinitely many solutions is at least hard as the question of whether a diophantine equation has any solutions, and is therefore undecidable. (As JDH comments below, in a certain technical sense, the question of whether there are infinitely many solutions may be harder.)

Proof: Let $F(x_1, x_2, \ldots, x_m)=0$ be any diophantine equation. Then $F=0$ has a solution if and only if $F(x_1, x_2, \ldots, x_{m-1}, y-z)=0$ has infinitely many solutions.

Your error is equating "infinitely many" with the much larger "all but finitely many".

UPDATE: As Mohammed points out "It is false that all but finitely many bagels are delicious" is equivalent to "infinitely many bagels are not delicious". And the theorem of Marker and Slaman is for all first order statements, not just for diophantine equations, so we should be able to use this rewording.

On skimming their paper, the first thing that I notice is that they have the quantifier $\forall^{\infty}$ ranging over a single integer variable, not over a $k$-tuple of integers, so you can say "For all but finitely many $x$, the following holds for all but finitely many $y$..." but can't directly say the stronger "For all but finitely many ordered pairs $(x,y)$..." But I'm not sure whether this is the heart of the difference, or just a minor technical issue.

share|cite|improve this answer
But aren't both quantifiers dual? For example consider the statement $\neg \forall^{\infty} \neg F = 0$, where $\forall^{\infty}$ is the quantifier "for all but finitely many", doesnt this statement mean there is an infinite number of solutions? – Mohamed Alaa El Behairy Jul 10 '11 at 17:25
(I removed my comment and posted it as an answer.) – François G. Dorais Jul 10 '11 at 21:59
David, you claim that the infinite-solution problem is "as hard as" the solution problem for diophantine equations, and this suffices to answer the question, but it would be more correct to say that it is "at least as hard as," since in fact it is strictly harder. The problem of determining whether a diophantine equation has a integer solution has complexity $\Sigma^0_1$---it is computably enumerable---but the problem of determining in general whether a diophantine equation has infinitely many solutions has complexity $\Pi^0_2$; indeed, it is $\Pi^0_2$-complete, hence strictly harder. – JDH Jul 10 '11 at 23:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.