58

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?

Matthieu FG
  • 55
  • 6
Will Sawin
  • 135,926
  • 14
    Title should be "The geometry of undecidable diophantine equations: WWNED?" – R Hahn Dec 04 '12 at 18:32
  • 11
    Maybe we need a Noam Elkies tag as well? :-) – Todd Trimble Dec 04 '12 at 19:27
  • 4
    If I go add ask-noam to 50 questions where it would be appropriate, do I get the taxonomist badge? – Will Sawin Dec 04 '12 at 22:39
  • 3
    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. – Minhyong Kim Dec 05 '12 at 00:17
  • 2
    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). – Joël Dec 05 '12 at 02:13
  • @Joël See http://mathoverflow.net/questions/60617/the-arithmetic-of-higher-genus-curves/60626#60626 – Felipe Voloch Dec 05 '12 at 15:52
  • 2
    I consider personalized tags as against the spirit of the site. Thus I would like to ask you to remove it. –  Dec 09 '12 at 12:18
  • Is there a meta thread or other discussion about this? I would like to hear the view of the wider MO community. – Will Sawin Dec 09 '12 at 18:02
  • Thanks for the reply. I do not know about a meta thread, for 'other discussion' see http://mathoverflow.net/questions/104889/what-numbers-are-integrally-represented-by-4-x2-2-x-y-7-y2-z3 (check the edit history to see the 'problematic' tags as they are gone now). As I said there while I prefer if it does not happen at all it is not a 'big problem' for me if it stays very rare. So, if you really want to keep it on this one occassion, well, then please keep it. If you however intend to make this a habit then yes likely you or I should start a meta thread. –  Dec 09 '12 at 22:16
  • I wasn't planning to make it a habit. – Will Sawin Dec 09 '12 at 23:10
  • 1
    @WillSawin: the set of undecidable Diophantine equations is very large and there is an easy procedure to get many of those once you have one. So geometrically these equations vary a lot. A more interesting question would be, given some geometric property, find out if there exists an undecidable equation or a system of equations satisfying that property. As far as I know nobody studied that problem seriously which is a pity. –  Jun 29 '17 at 01:16

3 Answers3

26

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.

Timothy Chow
  • 78,129
  • This reminds me of the tone of Weinberger's book "Computers, Rigidity, and Moduli": http://books.google.com/books?id=CtvmQiuOKSEC – Steve Huntsman Dec 04 '12 at 20:46
  • 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? – David E Speyer Dec 04 '12 at 21:30
  • 1
    @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. – Timothy Chow Dec 04 '12 at 22:35
  • 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 – Will Sawin Dec 04 '12 at 22:44
  • sets of nice properties that do not have decidable Diophantine problems. I am interested in the second approach. I am disheartened by the dimension difficulty. That might entirely kill this question, but hopefully there is something interesting that can still be said. – Will Sawin Dec 04 '12 at 22:46
  • @Will: For what you're looking for, I think you need (1) explicit examples that are known to be undecidable, right? The trouble is that the only known way to construct such things is to encode the axioms that your system's lack of solutions can't be proven from. Though I don't know the state of the art, I suspect that it's very difficult to enforce some nice geometric property at the same time that you're encoding the axioms of ZFC (or whatever) in your equations. – Timothy Chow Dec 05 '12 at 01:29
  • One small correction: If you're allowing families of systems then you don't have to encode a particular axiomatic system, but the members of the family still need to encode an undecidable problem, so I think it's still very difficult to ensure some nice geometric property at the same time. – Timothy Chow Dec 05 '12 at 01:46
  • That seems very reasonable to me. But perhaps it is very difficult but not impossible? I suppose there is only one way to find out. – Will Sawin Dec 05 '12 at 06:34
  • 1
    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. – Will Sawin Dec 05 '12 at 06:42
  • What do you you mean by " "most" computably enumerable sets are not computable.", especially "most"? recursive sets are computablly enumerable, and so do c.e. sets that are not recursive. How to define your "most"? discrete measure? – XL _At_Here_There Jan 26 '18 at 01:22
  • @XL_at_China : I don't know exactly what I mean by "most" which is why I used scare quotes. This is just an informal intuition, that there ought to be some definition of "most" according to which such a statement is true. – Timothy Chow Jan 26 '18 at 15:53
16

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.

Misha
  • 30,995
  • 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. – Will Sawin Dec 05 '12 at 04:15
  • 1
    @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. – Misha Dec 05 '12 at 04:55
  • 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/ – Will Sawin Dec 05 '12 at 06:35
  • I think the Hasse principle is very strongly related to decidability, but I'm not sure if it always implies decidability. – Will Sawin Dec 05 '12 at 06:38
  • @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. – Timothy Chow Dec 05 '12 at 16:44
9

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.)

Charles Matthews
  • 12,415
  • 34
  • 63
  • 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. – Will Sawin Dec 05 '12 at 06:42