58
$\begingroup$

As an arithmetic algebraic geometer of the highest moral fiber, I am trained to look at Diophantine equations in terms of the geometry of the corresponding scheme. For instance, if the Diophantine equation comes from a curve, I know that I should compute the genus, and do various things depending on if the genus is $0$, $1$, or $\geq 2$.

But I know very little about what the limits of this geometric approach are. I only know that there exist undecidable Diophantine equations, or families of Diophantine equations. I do not know what their geometry is like!

Do undecidable Diophantine equations, or families of equations, have interesting geometric properties? Can we compute basic geometric invariants like the Hodge diamond, Kodaira dimension, etc.? Are they pathological in every way, or do some of them have properties that might give a naive geometer hope about finding solutions? What would Noam Elkies try to do if he were asked to solve them and did not know they were undecidable, and why would he be stymied?

Improve this question
$\endgroup$
11
  • 14
    $\begingroup$ Title should be "The geometry of undecidable diophantine equations: WWNED?" $\endgroup$
    – R Hahn
    Commented Dec 4, 2012 at 18:32
  • 12
    $\begingroup$ Maybe we need a Noam Elkies tag as well? :-) $\endgroup$
    – Todd Trimble
    Commented Dec 4, 2012 at 19:27
  • 4
    $\begingroup$ If I go add ask-noam to 50 questions where it would be appropriate, do I get the taxonomist badge? $\endgroup$
    – Will Sawin
    Commented Dec 4, 2012 at 22:39
  • 3
    $\begingroup$ I never checked this myself, but Mazur told a number of us many years ago that he had looked at Matiyasevich's equations, and found that they all had plenty of rational solutions. Someone should ask him about this. Alternatively, you could look at the equations yourself. This doesn't answer your question, but it's a start. $\endgroup$
    – Minhyong Kim
    Commented Dec 5, 2012 at 0:17
  • 2
    $\begingroup$ And Minhyong, while you're here, I remember reading in one of your survey something that I liked, and that seems related to the question: the hope that the question of which algebraic curves over $\mathbb Q$ has a rational solution might be decidable -- even if for general variety, it is probably not (though we don't know it for sure yet). $\endgroup$
    – Joël
    Commented Dec 5, 2012 at 2:13

3 Answers 3

Reset to default
25
$\begingroup$

Though I don't have a full answer to your question, the following remarks may help.

Let's distinguish between (1) explicit examples of systems of Diophantine equations that are known to be undecidable, and (2) a system of Diophantine equations that has the property of being undecidable, whether we know it or not.

Regarding number (1), Jones has written down some explicit examples. The main practical difficulty with computing any invariants of these examples is their size. The basic example in the paper has 28 variables and degree $5^{60}$, which can be rewritten as a system in 58 variables and degree 2. My guess is that any Groebner basis algorithm would crash on this example, not because of any particular pathology, but because of its size. However, maybe I'm wrong. The example is written out explicitly so you could try playing with it yourself.

Regarding number (2), although I'm not aware of any precise theorems to this effect, I think that the intuition of most logicians and computability theorists is that "most" systems of Diophantine equations are undecidable. (This is related to the intuition that "most" computably enumerable sets are not computable.) If this intuition is correct, then undecidable Diophantine equations aren't "special"; it's just the reverse—the decidable ones are the ones that are special. Then your question is not very different from the question, what is the geometry of a "random" set of Diophantine equations? So it becomes more of a question in computational commutative algebra than a question in computability theory.

Improve this answer
$\endgroup$
11
  • $\begingroup$ This reminds me of the tone of Weinberger's book "Computers, Rigidity, and Moduli": books.google.com/books?id=CtvmQiuOKSEC $\endgroup$
    – Steve Huntsman
    Commented Dec 4, 2012 at 20:46
  • $\begingroup$ Number of variables and degree is a clumsy way of describing geometry. I know that people in this field like to write systems $f_1=f_2=\cdots=f_N=0$ as a single system $f_1^2+f_2^2+\cdots + f_N^2$. If we undo all such obvious tricks to get back to a system of equations, then what is the dimension of the complex solution space? $\endgroup$
    – David E Speyer
    Commented Dec 4, 2012 at 21:30
  • 1
    $\begingroup$ @David: Jones's system has 28 variables and 18 equations in its original formulation. Of course this doesn't necessarily mean that the dimension is 10. I don't know how to determine the dimension without first computing a Groebner basis. $\endgroup$
    – Timothy Chow
    Commented Dec 4, 2012 at 22:35
  • $\begingroup$ I don't think this accurately reflects my question. There are many ways in which an algebraic variety can be special: low dimension, low kodaira dimension, etc. I would like to know about algebraic varieties which are "general" in that there diophantine problems are undecidable, but "special" in that they have some other nice property. There are two ways at getting at the existence of these things: showing that varieties with a certain set of nice properties have decidable Dipohantine problems (I'm aware of some conjectures to this effect), and the reverse: finding varieties with certain $\endgroup$
    – Will Sawin
    Commented Dec 4, 2012 at 22:44
  • 1
    $\begingroup$ By the way, I think in many reasonable measures a positive proportion of algebraic varieties have no solutions mod $p$, for any fixed $p$. So I don't think undecidable is quite the same as random. $\endgroup$
    – Will Sawin
    Commented Dec 5, 2012 at 6:42
16
$\begingroup$

This is just a long comment, rather than an answer to Will's question. There are "standard" algorithmically unsolvable problems in combinatorial group theory: Word problem, conjugacy problem, triviality problem for the group, isomorphism problem for a pair of groups, etc. The most fruitful line of arguments relating logic to geometry in group theory is to find geometric conditions on finitely-presented group(s) which are sufficient for solvability of these problems. It turned out that, appropriately defined hyperbolicity is a geometric condition implying algorithmic solvability of all the "standard" problems. Furthermore, it turned out that hyperbolicity is, probabilistically speaking, "generic". Moreover, one of the oldest algorithms for solving word problem (Dehn's algorithm/linear isoperimetric inequality) is one of many equivalent definitions of hyperbolicity. In view of this, I would be looking for algebro-geometric features which are sufficient for algorithmic solvability of Diophantine equations, rather than the other way around. However, since I am neither a number-theorist nor a logician, I do not know what they could be.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I think you're right that the other way makes more sense, but I think there is a lot of work of this nature, even if it doesn't make explicit references to computation. Methods for solving Diophantine equations are a huge, huge field, and I already know many key ideas. That's why I'm interested in the reverse. $\endgroup$
    – Will Sawin
    Commented Dec 5, 2012 at 4:15
  • 1
    $\begingroup$ @Will: Could you add some (interesting) examples of geometric conditions implying solvability of Diophantine equations to your question? I think, it would be quite valuable (for people like me). One thing I find surprising is Timothy Chow's comment that unsolvability is expected to be generic: This contradicts my intuition coming from group theory. $\endgroup$
    – Misha
    Commented Dec 5, 2012 at 4:55
  • $\begingroup$ I don't know much about explicit decidability results. Here is an interesting discussion of a conjectural one: http://terrytao.wordpress.com/2007/05/04/distinguished-lecture-series-iii-shou-wu-zhang-%E2%80%9Ctriple-l-series-and-effective-mordell-conjecture%E2%80%9D/ $\endgroup$
    – Will Sawin
    Commented Dec 5, 2012 at 6:35
  • $\begingroup$ I think the Hasse principle is very strongly related to decidability, but I'm not sure if it always implies decidability. $\endgroup$
    – Will Sawin
    Commented Dec 5, 2012 at 6:38
  • $\begingroup$ @Misha: The content of the MRDP theorem is that every computably enumerable set is Diophantine. This is a lot stronger than the "mere" statement that it's undecidable whether a Diophantine system has a solution. Now, it's true that converting a computably enumerable set to a Diophantine set is a somewhat delicate process, so it's not ruled out that there still some sense in which "generic" Diophantine sets are decidable. I think it would be pretty surprising, though. $\endgroup$
    – Timothy Chow
    Commented Dec 5, 2012 at 16:44
9
$\begingroup$

You have a typical recursively enumerable set S of integers, and a set X of lattice points cut out by a multivariate polynomial. We are talking about S being the projection (onto one axis) of X. Given that S can be "pretty bad", can one say anything except that X is "presumably worse"? None of the interest lies in any finite segment of S.

To put it another way, possibly more interesting to geometers, the analogy with constructible sets fails here. There is some hint in the history that Hilbert was misled by elimination theory into thinking that Godel's incompleteness theorem (or suchlike) couldn't be the case. (I'm not putting this very well, and it is disrespectful in a way to Hilbert.) Anyway algebraic geometers "know" that projection doesn't really innovate that much in the way of geometry, and logicians "know" the precise opposite in terms of logic. So at the very least the intuitions are in tension.

(Maybe the mistake of thinking that "geometry of undecidable diophantine systems" was a kind of impossible object, and therefore all r.e. sets would turn out to be recursive, is a mistake intelligent enough to attribute to Hilbert. As a kind of Fundamental Theorem of Proof Theory.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm not interested in the set $X$ of lattice points, but in the whole set of complex points. This should hopefully be a more manageable object, due to the first-order decidability of complex stuff. $\endgroup$
    – Will Sawin
    Commented Dec 5, 2012 at 6:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .