DIOPHANTINE EQUATION FLOWCHART [These are working notes! -- how did you find them?] Do you want to know if there are numbers which satisfy some particular pattern or relationship? If so, you may be looking for the solution of a DIOPHANTINE EQUATION. Please read http://www.math.niu.edu/~rusin/known-math/index/11DXX.html for an overview of the field to see if that is indeed what you are doing. The purpose of this document is to help you discover whether the situation you are considering has been looked at before, so that you can tell whether or not solutions exist, how many there are, and how to find them. OUTLINE I. Reducing to an ideal in Z[x_1, ..., x_n] 1. References to special numbers, geometrical patterns, etc. 2. References to prime numbers 3. Restrictions to positivity 4. Problems about sets of integers 5. Use of special functions 6. Exponential problems II. Terminology and basic theory 1. Types of "solutions" 2. Algebraic varieties and dimension 3. (Embedding) Dimension reduction 4. Subvarieties and quotient varieties; parameterizations 5. Genus of curves III. Particular cases with "solutions" 1. Zero-dimensional varieties (finite solution sets) 2. Linear equations - Euclidean algorithm 3. Linear equations - Smith normal form 4. Single quadratic equations: rational solutions 5. Single integral quadratic equations: factoring, modular square roots 6. Single integral quadratic equations: Pell's equation 7. Elliptic curves 8. Thue equations 9. Other curves of higher genus 10. Surfaces 11. High-dimensional varieties: sums of powers 12. High-dimensional varieties: lattice problems 13. Other types of Diophantine problems with (partial) solutions The basic setting for Diophantine problems is a set of equations which are to be solved in whole numbers (or in some cases rational numbers or numbers of a certain form). For example, you might want to know about solutions to the equation X^N + Y^N = Z^N among whole numbers X, Y, Z, and N. In section I, we consider the most general Diophantine problems; the goal is to see whether they can be put into this more restrictive framework. When not, some alternatives suggesting possible solutions are discussed. In section II we outline the terminology and general rules for analyzing Diophantine problems which are in this general form. It is usually necessary to be familiar with this section in order to know where in section III to look for solutions to a particular problem. In section III we consider separately the general families of Diophantine problems which have solutions or which are amenable to attack by some established procedures. An outline of what is known and some pointers to examples are provided; detailed algorithms are not. With luck you will be able to find solutions to your problems with this guide. It's easy to check that any solutions you find are correct. Proving the list complete, and in particular proving that no solutions exist, may be a little trickier than is suggested here, since it is not our intention to provide for all the technical details -- the goal here is to discuss what "usually" happens in various types of problems. ============================================================================== SECTION I: PROBLEM REDUCTION Some Diophantine problems are a little too exotic for treatment in this document. We'll take a look at a such a problem and ask a few questions to see if we can force it into the more restrictive format discussed in Section II and Section III. Q1. Does your problem refer to anything besides ordinary NUMBERS? Many Diophantine questions appear to ask about special kinds of numbers: squares, triangular numbers, Mersenne numbers, Bell numbers, Catalan numbers, and so on. Frequently, these numbers can be expressed as functions of some parameters, so that the problem can be expressed in terms of a search for the parameters rather than the numbers themselves. For example, "Are there triangular numbers which are also squares?" asks, "Are there integers m, n with (m^2+m)/2 = n^2?". We will thus assume in the sequel that "numbers" are simply "integers" (or in some cases "rational numbers"). One common source of Diophantine problems is metric Euclidean geometry. That is, one asks for arrangements of points, line segments, triangles, and so on for which various lengths, areas, and volumes are expressed in terms of integers or rational numbers. These can usually be converted to problems involving numbers by the introduction of coordinates, or with the Pythagorean theorem (binding lengths), Heron's formula (binding lengths to areas), or the related formula for volume of a tetrahedron. We shall in the sequel assume the problem now asks simply about "numbers" satisfying certain conditions, although a couple of special cases warrant separate mention: Q2. Does your problem refer in some way to PRIME numbers? Many problems ask for sets of integers satisfying a number of equations or inequalities, with the additional constraint that one or more of the variables be prime. For example one might ask for the number of solutions to p = 4 n + 1, p=prime , or more generally p = a n + b, p=prime (a and b given) see Dirichlet's theorem p = n! + 1, p=prime p = n^2 + 1, p=prime p = 2^n + 1, p=prime (Fermat numbers) p = 2^n - 1, p=prime (Mersenne numbers) p - q = 2, p, q both prime (Twin primes conjecture) p + q = N, p, q both prime (N given) Goldbach conjecture N^2 < p < (N+1)^2 p prime (N given) Apart from Dirichlet's theorem and its special cases, these are all open problems and expected to be hard. Dirichlet's result is proven with tools in analytic number theory; most of the others are usually approached with sieve methods. Remark: Matiyasevich's work shows we may express the statement "p is prime" as a statements "there exist integers a_1, ..., a_25 such that F_1(a_1, ..., a_25, p) = F_2(a_1, ..., a_25, p) = ... = 0" for some collection of polynomials F_1, F_2, ... Thus in principle, we may transform a Diophantine problem of this type to one in which primality is not mentioned. But this is not at all effective. (Similar remarks may be made in several of the other sections; for example exponential Diophantine problems such as the Fermat equation can be expressed as a larger set of _polynomial_ Diophantine problems -- no unknowns are used as exponents. See e.g. Baxa, Christoph: "A note on Diophantine representations", Amer. Math. Monthly 100 (1993), no. 2, 138--143. MR94a:11035.) In the sequel, we will assume that no such conditions of primality are set. Q3. Does your problem refer in an essential way to POSITIVE numbers? It is common to prefer positive (integer) solutions to a problem but to accept negative solutions as a matter of some interest; certainly a good description of the set of all solutions would allow the retrieval of the positive solutions among them. However, there are cases in which the positivity of the variables plays an essential role. For example, the "postage stamp problem" asks us to solve d_1 x + d_2 y = N, x and y both nonnegative (d_1, d_2, N given) (or more generally to solve Sum( d_i x_i ) = N with given {d_i} and N). This is easy to solve integrally -- it is necessary and sufficient that gcd(d_1, d_2) divide N, in which case solutions arise from the Euclidean algorithm. But when x and y are required to be positive it is not as easy to describe those N for which a solution exists. Problems of this type arise in optimization problems; in some cases techniques of linear programming apply. Note that in principle the condition "x is positive" may be replaced by the condition "there exist integers a,b,c,d with x=a^2+b^2+c^2+d^2" by Lagrange's theorem, so that one may apply the techniques described below. As in the previous section Q2, this introduction of many variables makes the translation useless in practice. (Also note that "x is positive" may be replaced by the somewhat more efficient statement "x=a^2+b^2+c^2+c+1 for some a,b,c".) Some Diophantine problems can be expressed in terms of inequalities; since every inequality simply describes the positivity of some quantity, here again in principle these may be reduced to a simpler situation. For example the condition "n is abundant" may be expressed "sigma(n) > 2n", but of course this is equivalent to the pair of conditions, "m=sigma(n)-2n, m>0". Naturally, it is unclear whether or not any of the previous approaches is helpful in this situation! We will assume in the sequel that negative values of the variables are acceptable, and that the problem is stated using equations, not inequalities. Q4. Does your problem refer to SETS of integers in an essential way? An example of such a problem is the knapsack problem: given a finite set of integers S and an integer N is there a subset T of S such that the sum of the elements of S equals N? Such problems are more appropriately thought of as combinatorial number theory. Some tools from computer science or mathematical logic may be applied, although the brief answer is that it is hard to solve such problems efficiently. Another example arises with Egyptian fractions -- we ask for ways to express a given rational number as a sum of distinct unit fractions 1/n. Stated in this form, the problem is not quite accessible with the tools of this document; however a question of Erdos (can we write 4/n=1/x+1/y+1/z for each n?) _is_ a Diophantine problem in the narrower sense since the number of variables (3) is fixed. In the same way, Waring's problem (e.g. can we write every integer as a sum of fifth powers?) could be analyzed differently if we state it as a problem with a fixed set of variables (can we write every integer as a sum of 37 fifth powers?) Note that in some cases, problems with sets of integers may be reduced to problems with just a few variables; the key there is the ability to express the set in terms of some parameters. For example, Selfridge and Erdos asked when a product of a set of consecutive integers could be a power. Since sets of _consecutive_ integers are parameterized by their length and least element, this asks for solutions to the equation (n+k)!/n! = x^m. In the rest of this document we will assume we seek only sets of a known, fixed, (and usually small) cardinality, whose elements are integers drawn from among a set which is (essentially) unconstrained. Q5. What FUNCTIONS are used in the description of your problem? Many important arithmetical questions can be expressed as Diophantine equations using various number-theoretic functions. We have already mentioned an example using the factorial function. Related functions include the binomial coefficient functions C(n,k); if k is fixed, these are simply polynomial functions of n, but for example a number of well-known questions ask for divisors of the Catalan numbers, that is, solutions of the equation C(2n,n) = pq. Others important Diophantine questions involve the sum-of-divisors function sigma --- for example, solutions to the equation sigma(n)=2n are the perfect numbers; solutions to the pair of equations sigma(n)=2m, sigma(m)=2n are the amicable numbers. Of a similar nature are the Euler phi-function, the Mobius function mu, the partition function p(n) and so on. In some cases general results can be obtained using the relationship with the Riemann zeta function, but specific Diophantine problems involving these functions are mostly unsolved. Many Diophantine questions appear to involve the "mod" function. The condition "x = y mod z" in most cases may be replaced by the simple equation "there is an integer q with x=y+zq", but some questions require that 0 <= x < z, for example. Some of these questions can be resolved with trigonometric sums, but in general the function "y mod z" (and the related "floor", "ceiling", "round", "frac" etc.) are difficult. Some results in transcendental number theory can be applied; for example, for fixed real alpha and beta , one may ask for integers m and n with frac(m*alpha)=frac(n*beta), which is a question about linear independence over Q. There are a number of questions which involve the digits of an integers when expressed base-10 or in some other base. These too may be expressed in terms of the floor function. (Note however that there are really no nontrivial results known about solutions to problems which are base-dependent.) In the problems which follow, we will assume the conditions which describe the integers sought are expressed in terms of the five fundamental operations +, -, *, /, ^. Q6. Does your problem include variables in EXPONENTS in an essential way? An example is the Catalan problem: what are the integer solutions to x^y - z^w = 1 that is, what are the consecutive powers? Problems involving variables in exponents tend to be hard, and for good reason: it is a consequence of work in mathematical logic (e.g. Matijasevic's theorem) that the solution sets to such problems can be essentially any subset of the integers. In some cases progress has been made using linear independence results involving logarithms of integers. Other problems involve variable exponents only as parameters. For example, the Fermat equation x^n + y^n = z^n is a Diophantine equation to be solved for four variables x,y,z,n. But clearly one may hold n fixed and investigate the solvability of first x^3+y^3=z^3, then x^4+y^4=z^4, and so on. The resolution of a finite number of specific cases is insufficient, of course, for the general result, but as it turned out, an analysis is possible which holds n fixed but arbitrary, so that one may view x,y,and z as the only variables. We now assume in Sections II and III that the variables we are to solve for are INTEGERS (or RATIONAL NUMBERS) which are to satisfy a finite number of EQUATIONS relating (multivariate) POLYNOMIALS. Note that we may multiply through by any common denominators and assume the polynomials have integral coefficients. ============================================================================== SECTION II: PROBLEM ANALYSIS Our goal in this section is to introduce the notation and basic concepts necessary for the classification and analysis (in Section III) of the types of problems defined in Section I. We assume that we are given a collection of M polynomial equations in N variables, which we want to solve in integers or rational numbers. We may write these equations as P_1 ( x_1, ...., x_N ) = 0 ... P_M ( x_1, ...., x_N ) = 0. 1. What is a "solution"? There are several interpretations of "solve" which apply. In some cases, "solutions" can be given in one sense but perhaps no "solution" exists in a stronger sense. Here are possible interpretations: Can one 1) determine whether any solutions exist? 2) determine whether infinitely many solutions exist, or 3) determine the number of solutions (if finite)? 4) find a solution? 5) find infinitely many solutions? 6) find all solutions (if finite)? 7) give a good description of the solution set (if infinite)? ("good" may mean: "connected to another mathematical topic", or "given parametrically", or "sufficient for computing all solutions in turn", or "sufficient for counting the solutions in a certain region", etc.) In some cases we will give tests for the existence of solutions which are necessary but not sufficient; we can give algorithms which might produce solutions but might not terminate; we can give theorems whose truth rests upon some unproven conjectures. For each interpretation of "solution", we may ask for the solutions among the rational numbers as well as among the integers. We may ask about solutions in other number fields. We may ask about the computation of solutions "efficiently" (relative to some measurement of "size" of the initial polynomials P_1...P_M). If the problem involves a parameter, we may ask for information about the relationship between the parameter and the existence/number/magnitude of solutions. The situation for general Diophantine equations is disappointing: in general, we have no way even to know whether or not solutions exist to a general Diophantine equation. This was the 10th of Hilbert's problems http://www.math.niu.edu/~rusin/known-math/95/hilb.list and was proved to have a negative answer. Among the special families for which a general framework exists to study the solutions, we find some families in which (1) may be answered but not (4), and so on. In this document we will try to cover as many aspects of "solving" the problem as possible for each class of problems. 2. Algebraic Geometry; dimension The set of points (x_1, ..., x_N) which satisfies the initial equations is an example of a _variety_, the object of study in algebraic geometry. (The study of integral and rational points on varieties is sometimes known as "arithmetic algebraic geometry".) It is most useful to use the terminology and tools of algebraic geometry to study some Diophantine sets of equations. The principal determinant of the size of the solution set is the _dimension_ of the variety, which in most cases is the difference N-M. This calculation may be misleading in some contexts; for example, the single equation (a-b)^2 + (b-c)^2 = 0 is clearly equivalent to the pair of equations a-b=b-c=0 whose solution set is a line, not a surface, in space. This type of situation may also occur more subtly in larger sets of equations; the necessary condition is the nondegeneracy of the Jacobian matrix. Our interest is in the generic cases of problems; hence we will ignore this difficulty in most of the examples we consider. When the number of equations exceeds the number of variables, it is frequently true (in some sense "likely true") that the solution set is empty. One need only compute the solution set to any collection of N equations in the N unknowns -- this solution set should be "zero-dimensional": finite -- and then for each of those solutions verify whether or not the remaining M-N equations are satisfied. In some cases there may be an advantage to permuting the collections of polynomials used at various points during the computations, but as far as I am aware no one has seriously investigated the consequences of simply working with the N polynomials of lowest degree, then checking against the other M-N. There is a common special case in which "dimension" should be treated carefully. Suppose each of the polynomials P_i is homogeneous. Then it is clear that for any nonzero constant c, (X_1, ..., X_N) is a solution iff (cX_1, ..., cX_N) is. In this case there is no distinction between integral solutions and rational solutions. Moreover, we may consider two simpler problems: we may look for solutions with X_N=0 and with X_N=1, in each case getting a problem of fewer variables, that is, of smaller dimension. All other solutions can be recovered by scaling by X_N. (Conversely, we may render any problem homogeneous at the expense of increasing the (affine) dimension by 1.) This situation occurs very commonly in "natural" questions (whatever that means) and in many geometric questions (in which any dimensionally-consistent formula would for example raise all lengths to the same power). In the attempt to keep the discussion elementary rather than elegant, we will in this document usually opt to destroy symmetry and discuss the affine problems rather than the projective problems. Thus for our purposes the analysis of Fermat's Last Theorem would ask, Are there rational solutions to x^n + y^n = 1 ? rather than Are there integral solutions to x^n + y^n = z^n ? It is not immediately clear under what circumstances two Diophantine problems should be considered "the same". Usually we accept transformations which give us correspondences between two varieties which are not quite one-to-one or onto but whose deviation from that ideal state are easily accounted for. For example, this transformation of the Fermat equation isn't quite perfect: the solutions with z=0 to the integral problem have no corresponding rational solution (x,y) to the other problem; and each solution of the rational problem corresponds to several solutions of the integral equation even if we add the condition that the integers x,y,z be relatively prime. This kind of a correpondence is a "birational equivalence", and it occurs whenever we try to "solve" equations by making reversible substitutions and manipulating equations in the simple-minded ways. The reader is cautioned to watch carefully for solutions lost in such a transformation, as well as for spurious solutions introduced. The main point is that the manipulations we perform will not change the dimension of the variety: although they could easily change the number of equations M or the number of variables N needed to describe the problem, the difference N-M should stay fixed. Thus it is the dimension, rather than M or N individually, which is most useful for classifying Diophantine problems. For further reading in Algebraic Geometry turn to http://www.math.niu.edu/~rusin/known-math/index/14-XX.html 3. Reducing the embedding dimension It is frequently easier to discuss a variety and find its rational points if we can reduce the number of variables N and equations M. If some variable shows up simply in an equation, we solve for that variable, then substitute our solution into the remaining equations. If we view the defining equations as carving out a portion of N-dimensional space, it follows that the effect of eliminating a variable is to reduce the dimension of the space in which our variety lives. For example, the equations x^2+y^2+z^2=1, x+y+z=0 describe a curve in 3-space (the intersection of a plane and a sphere is in fact a circle); eliminating z gives one equation in two unknowns: x^2 + y^2 + (-x-y)^2 = 1. This is still a (1-dimensional) curve, but now it's a curve in the plane rather than in space, so it seems reasonable that the curve is now easier to analyze. (It happens to have no rational or integral points). Can we always eliminate variables, leading to just one equation in several unknowns? (Even better: can we eliminate one more variable, leaving no equations in several unknowns, that is, leaving us with a few of the variables unconstrained, and the rest given as simple rational functions of them?) The answer is "no", although just what goes wrong is a little hard to describe at this point. Still, we often would like to eliminate as many variables as possible. Possible techniques for doing this include elimination theory and the use of resultants, as well as Groebner basis techniques. Each is known to be wildly inefficient for some problems, but they can be used effectively in many cases of interest. We will discuss these techniques briefly here; these are topics in Commutative Algebra, http://www.math.niu.edu/~rusin/known-math/index/13-XX.html If f and g are polynomials in one variable X_1, the the resultant Res(f,g) of f and g is (up to a constant) the product Prod f(r_i) where r_i ranges over the roots of g. In particular, f and g have a common root iff Res(f,g)=0. Now, as it turns out, the resultant may be computed as a polynomial in the coefficients of f and g. In particular, if these coefficients involve a second variable X_2, then Res(f,g) is a polynomial in X_2 which vanishes precisely at those values of X_2 for which the equations f(X_1,X_2)=g(X_1,X_2)=0 have a common solution (X_1, X_2). So we may find integer points defined by f=g=0 by first computing any integer roots of Res(f,g)=0 and then for each such X_2 computing any integer roots of f=0, checking to see whether these are also the common roots with g=0. Likewise, we may in this way replace a set of equations P_1=...=P_M=0 involving variables X_1, ..., X_M with a smaller set of equations Res(P_1, P_2)=Res(P_1,P_3)=...=Res(P_1,P_M)=0 in fewer variables X_2,..., X_M. Proceeding by induction we may reduce to the case of one equation in one unknown X_M (and any other variables not yet mentioned). One drawback here is that the resultant is computed as a determinant of usually large symbolic matrix, and hence is costly to evaluate. Moreover, repeated use of resultants can easily produce polynomials of very large degree with large coefficients. Finally, the process of elimination may introduce many spurious solutions. Elimination theory also replaces a set of polynomials in N variables with a smaller set of polynomials in N-1 variables --- as above, usually more cumbersome polynomials, computed only slowly, and with a solution set larger than the solution set of the original problem. Here we begin with the observation that any common root of f and g is also a root of all linear combinations uf+vg (u and v arbitrary polynomials of the same variable(s) as f and g). Now, we may apply the Euclidean algorithm to discover the greatest common divisor h of f and g, and indeed to discover u and v making h = u f + v g. Applied to polynomials of say X_1 and X_2, we can compute such u and v in the ring Q(X_2)[X_1] of polynomials in X_1 whose coefficients are rational functions of X_2. Now, if indeed the dimension of the solution set is 0, there should be no common denominator of f and g, so that we can write u f + v g = 1; clearing denominators gives an equation u' f + v' g = h' where h' is a polynomial in X_2. (Actually the computations can be organized to avoid denominators altogether and compute u', v', and h' directly.) Then a common solution to f=g=0 also makes h'=0, so that our search for solutions (X_1,X_2) has been reduced to a search for solutions X_2 to a single polynomial in one variable. More variables may be treated as in the previous paragraph. A popular method of organizing several polynomial equations in several unknowns uses Groebner bases. Here is the basic idea. The theory of elimination proceeds very nicely given equations in just one variable, so that the Euclidean algorithm among polynomials can be used directly. At another extreme, a set of equations in many variables may be reduced easily to an equation in one variable if all the equations are linear, using Gaussian elimination. There are a number of related approaches, collectively called Groebner basis techniques, which combine these two ideas to consider equations in more than one variable, of degrees greater than one. These are implemented in many of the popular symbolic algebra programs. Like the methods of resultants and elimination, the goal is the creation of a sequence of polynomials Q_1(X_M, ...,X_N), Q_2(X_{M-1}, X_M, ...X_N), ..., Q_M(X_1, ..., X_N) whose solution set roughly conincides with the solution set of the P_i, but which is clearly easier to address: we find all solutions to Q_1 first, then for each use Q_2 as an equation which defines X_{M-1}, and so on by induction until we use Q_M to define X_1. For example, this process works very well if M=N (the variety is zero-dimensional) as we shall see in Section III. All these approaches may be interpreted geometrically as projecting the solutions (X_1, ..., X_N) of the original equations to the subspaces R^i of R^N. In every case they suffer the defect that it is possible for the solution set of the polynomials in X_N alone, say, to include points which are not in the image of the solution set of the polynomials in X_{N-1} and X_N. For example, there are no integral solutions to the pair of equations X_1^2+X_2 = X_2-1 = 0, even though the first equation alone does have solutions. In addition, these approaches produce polynomials of an unnecessarily large degree, making computation difficult. Consider the equations X_2 - X_1^2 = X_2 - c = 0. For nonzero c, we eliminate X_2 to get the equation X_1^2 - c = 0, necessarily of degree 2 since for some c there are two points in the solution set; however, when c=0, this elimination has led to the equation X_1^2=0, which naturally has the same solution set as the simpler X_1 = 0. The phenomenon here is best described using commutative algebra: we seek the ideal I of polynomials which vanish on the solution set of our initial problem; within this ideal are smaller ideals which describe the same solution set, namely those containing I^m for any integer m. These are the ideals produced by the techniques described so far. What is preferable is an algorithm which can produce an ideal with generators of minimal degree -- equivalently, an algorithm producing the largest possible ideal, namely I itself (this is the radical of the ideal defined by the initial P_i). Such an algorithm has been incorporated into Magma; they cite "Becker & Weispfenning, chapter 8" as a source for their ideas. Application of these ideas tends to create problems requiring huge memory outlays and long execution times when for example given a dozen quadratic equations in as many variables. Considerable research is being done to investigate and improve the competing algorithms. Finally, we should observe that the process of eliminating one variable at at time can easily mask some underlying structure or symmetry of the variety, making analysis harder instead of easier. In short: dimension reduction can be done -- usually, approximately, with difficulty, and with uncertain value! 4. Subvarieties and quotient varieties If you can think about Diophantine problems geometrically (as varieties) then it makes sense to ask about maps from one to the other; as in other contexts in mathematics, we can ask when these maps are one-to-one or onto, although those aren't quite the right questions to ask for technical reasons. Roughly speaking, maps between varieties are composites of the two important types: inclusions and projections. We won't really be concerned with more general maps in this document, except to note that the process of making _noninvertible_ substitutions of variables, adding or deleting equations from the defining set, correspond to defining maps between varieties. A subvariety of a variety V is a subset of V defined by some additional equations; for example, we mentioned above that the circle is a subvariety of the sphere. Subvarieties are useful for producing solutions to a Diophantine problem: obviously if the points of W are determined by specifying all the equations of V and others in addition, then integer (or rational) points on W are give integer solutions to the equations defining V; whether or not there are other rational points in V is a much harder question. A well-known example to this is Elkies' discovery of an integer solution to the equation X^4+Y^4+Z^4=W^4; he found a curve having infinitely many rational points as a subvariety in the surface X^4+Y^4+Z^4=1 by adding another equation relating X, Y, and Z. A _parametric solution_ to a Diophantine problem involving variables X_1, ..., X_N is a set of N rational functions f_i of one or more parameters, with the property that all the equations of the problem are satisfied identically upon substituting X_1=f_1, etc. For example, a parametric solution to the equation x^2 + y^2 = 1 is x=2t/(1+t^2), y=(1-t^2)/(1+t^2). In this particular case, the points (x,y) obtained from rational values of t are all the rational points on this variety. In a more general situation, a parametric solution to a Diophantine problem is a (very special type of) subvariety of the variety determined by the equations. Quotient varieties are a little harder to describe in any generality but they enter our discussion in an important way. Suppose we define a variety V with a set of equations involving several variables X_i; suppose X_N is present only in the last equation. If we drop that equation we then have M-1 equations in N-1 variables, defining another variety of (usually) the same dimension. Each point (x_1, ..., x_N) of the original variety gives a solution (x_1, ..., x_{N-1}) to the new set of equations; the converse is (almost everywhere) true too, if you accept solutions with complex coordinates. What is significant, though, is that the correspondence is _not_ one to one; indeed, if the one equation involving X_N is of degree d in that variable, then there are generically d points in the inverse image. In practice, this means that the quotient variety is "simpler", or "less twisty" and, significantly, often has more rational or integral points than the first. In practice, this makes it difficult to find points on the original variety by finding some on the quotient variety and then hoping to solve for X_N from the one remaining equation. On the other hand, this gives a tool for showing that the original variety _has no points_, if the quotient variety has none either. Another example of quotient varieties arises from a change of perspective. It is often appealing to think of one of more of the variables in a Diophantine problem as being a "parameter". For example the equation x^2+y^2=r^2 describes a 2-dimensional variety in 3 variables; but for any individual r, we think of this as describing a 1-dimensional variety in the other two variables. Geometrically, we are mapping points (x,y,r) in the surface to points r in the line. This makes the line into a quotient of the surface. The individual circles are called the "fibres"; one pictures them on separate parallel planes all perpendicular to the "r-axis". 5. Genus of curves In Section III we will analyze a number of Diophantine problems which consider varieties of dimension 1 -- curves. This (usually) occurs whenever there is just one more unknown than equation. As it turns out, the analysis depends on a characteristic number associated with the curve, known as the genus. There is a geometric picture which is extremely important when attempting to solve 1-dimensional Diophantine problems. The defining equations of our variety may be interpreted as equations over the complex numbers; then the solution set is a set of N-dimensional complex space. In general, N-1 equations will define a 1-dimensional subspace of C^N, but that will be a _complex 1-dimensional set_: locally, each point on the set appears to be surrounded not by a piece of the _real_ line R^1 (that is, it doesn't look like a curve) but rather by a piece of the _complex_ "line" C^1, which we usually think of as a (real) plane. Thus, the solution will tend to look like a _surface_, and in the absence of any singular points will be a fairly nice surface: a sphere, perhaps, or a torus with a certain number g of holes. This number g is the genus of the curve; it's invariant under birational equivalence. When plotted as a subset of R^2, the equation x^2+y^2-1=0 describes a circle; but this is only the "real slice" of the solution in complex space, which is topologically a sphere. Likewise, the curve y^2=x(x-1)(x-2)(x-3) is merely a slice through a torus; we say that this equation describes a curve of genus 1. Unfortunately the curve y^2=x(x-1)(x^2+1) also describes a curve of genus 1 although its real locus more resembles the circle than the other curve; the real locus doesn't accurately suggest the genus. There are algorithms to compute the genus of a curve, but they are complicated in general. Some special cases are easier: a nonsingular plane curve defined by a polynomial of degree d has genus (d-1)(d-2)/2 (Hurwitz's formula), so that a single quadratic has genus zero, and a single nonsingular cubic equation in two variables defines a curve of genus 1. (Curves of genus zero are often called "conics"; curves of genus one are called "elliptic curves". As it turns out, the only 1-dimensional varieties which may be parameterized are those of genus zero.) I will not try in this document to cover all the details and nuances here; one must carefully consider singular points, projectivizations, cover maps, and the whole nine yards to get a good understanding of the concepts. I wish only to stress the importance of this particular parameter, the genus, in the study of algebraic curves. In particular, when using elimination theory, say, to pass from a curve described by M equations in M+1 variables, to a curve described by M-1 equations in M variables, we project from a variety V to a variety V'; it happens to be true that the genus of V' is never more than the genus of V, but it may well be less, and that drop in genus will fundamentally change the nature of the solution set over the rationals or the integers. For algebraic curves see http://www.math.niu.edu/~rusin/known-math/index/14HXX.html ============================================================================== SECTION III: SOLVABLE FAMILIES OF EQUATIONS In the terminology of Section 2, we describe this flowchart to analyze a Diophantine problem. (We don't pretend this has the precision of an algorithm): Q1 Is the variety zero-dimensional? If so, go to section 1 Otherwise, the variety is positive-dimensional Q2 Are there equations which are linear? If so, we may eliminate these equations and some variables easily if we are solving rationally; if solving integrally, consider whether: Q2a There is just one equation and it is linear: use section 2 Q2b There are several equations, all linear: use section 3 Q2c There are linear and nonlinear equations: use section 2 or section 3 as appropriate to solve for the variables in the linear equations; substitute into the others. So we assume all equations are of degree two or more. Q3 Is there just one, quadratic equation? If so go to section 4 if solving rationally; if solving integrally, see sections 5-6 for two-variable problems, 6-7 for more variables. Now there is either more than one (nonlinear) equation, or a single equation of degree 3 or more Q4 Are there just two, quadratic equations in 3 variables, or one cubic in two variables? If so (elliptic curve) see section 8. Q5 Is there just one equation in two variables (now of degree at least four)? If so, see section 9-10. Q6 Is this some other curve? see section 10. Q7 Is this a surface of a type not yet treated? see section 11-12 Q8 Is the variety of dimension 3 or more? see section 12 If none of these sections match your problem, you may try to perform simple substitutions to get a birationally equivalent variety which perhaps is covered in one of these sections. If this fails, Q9 Do you think there are solutions? If so, consider adding additional equations to describe a subvariety which can be shown, using one of the sections above, to have solutions. Or if you think there are no solutions, consider finding a quotient variety which can be shown, using one of the sections above, not to have any solutions. Q10 Were none of the above very helpful? Sorry! It may be that no one knows whether your problem has solutions or not! ============================================================================== Everything below this line still needs to be edited following a reorganization of everything above the line! ============================================================================== 1. Zero-dimensional varieties (finite solution sets) 2. Linear equations - Euclidean algorithm 3. Linear equations - Smith normal form 4. Single quadratic equations: rational solutions 5. Single integral quadratic equations: factoring, modular square roots 6. Single integral quadratic equations: Pell's equation 7. Single integral quadratic equations, three or more variables. 8. Elliptic curves 9. Thue equations 10. Other curves of higher genus 11. Surfaces 12. High-dimensional varieties: sums of powers 13. High-dimensional varieties: lattice problems 14. Other types of Diophantine problems with (partial) solutions 1. Zero-dimensional varieties (finite solution sets) Here we consider the case that the number of equations equals the number of unknowns. ONE EQUATION, ONE UNKNOWN: The simplest case involves just one unknown. Here it is simplest to use the rational root test: if P(x)=0 has an integer solution x, that x is a (positive or negative) divisor of the constant term P(0) of the polynomial; if P has a rational solution, its numerator divides P(0) and its denominator divides the leading coefficient of P. This gives a finite number of candidates x to check, so we may list all solutions effectively In practice, this may not be the most efficient method of solution: this requires we know all the factors of P(0), and assumes that number to be small. If we don't know those factors, or if they are numerous relative to the degree of the polynomial, it is more efficient to find the real roots of P and see if they are integral or rational. Since the coefficients of P are assumed to be integral, it is efficient to determine rational intervals each containing precisely one of the roots of P, using Sturm sequences. By bisection one may assume these intervals to have length at most 1, so that the candidate integral solutions are all known. One may continue to refine the intervals until they are of length at most 1/|P_0| (here P_0 is the lead coefficient) to discover whether there is a candidate rational number which is a root of P. (This procedure is essentially equivalent to computing the root e.g. with Newton's method and then using the continued-fractions algorithm to find rational approximations to the root; once the denominators of the approximations exceed |P_0| we conclude the root is not rational.) General topics concerning the solving a single polynomial equations in one variable may be found in http://www.math.niu.edu/~rusin/known-math/index/26CXX.html but for Diophantine analysis it's more relevant to think about polynomials from the perspective of Field Theory and Galois theory; see http://www.math.niu.edu/~rusin/known-math/index/12FXX.html DIMENSION REDUCTION Now suppose we have N integral polynomials in N variables. If we assume the N x N Jacobian matrix to be nonsingular on the solution set, then this solution set will be finite. One may mimic the case N=1 to some extent: using a multivariate Newton's method approach, one may compute the solutions to any desired degree of accuracy; it will be plain to see whether any solution are integral, and if they are rational this can be discerned by the continued-fraction algorithm. Unfortunately this method fails to give global estimates on the locations of the solutions (Newton's method is a local technique) and on the potential denominators of rational points. Possible techniques for resolving this problem include elimination theory and the use of resultants, as well as Groebner basis techniques. Each is known to be inefficient for some problems, but they can be used effectively in many cases of interest. We will discuss these techniques briefly here; these are topics in Commutative Algebra, http://www.math.niu.edu/~rusin/known-math/index/13-XX.html If f and g are polynomials in one variable X_1, the the resultant Res(f,g) of f and g is (up to a constant) the product Prod f(r_i) where r_i ranges over the roots of g. In particular, f and g have a common root iff Res(f,g)=0. Now, the resultant may be computed as a polynomial in the coefficients of f and g. In particular, if these coefficients involve a second variable X_2, then Res(f,g) is a polynomial in X_2 which vanishes precisely at those values of X_2 for which the equations f(X_1,X_2)=g(X_1,X_2)=0 have a common solution (X_1, X_2). So we may find integer points defined by f=g=0 by first computing any integer roots of Res(f,g)=0 and then for each such X_2 computing any integer roots of f=0, checking to see whether these are also the common roots with g=0. Likewise, we may in this way replace a set of equations P_1=...=P_N=0 in variables X_1, ..., X_N with a smaller set of equations Res(P_1, P_2)=Res(P_1,P_3)=...=Res(P_1,P_N)=0 in fewer variables X_2,..., X_N. Proceeding by induction we may reduce to the case of one equation in one unknown and solve as before. The drawback here is that the resultant is computed as a determinant of usually large symbolic matrix, and hence is costly to evaluate. Moreover, repeated use of resultants can easily produce polynomials of very large degree with large coefficients. Elimination theory also replaces a set of polynomials in N variables with a smaller set of polynomials in N-1 variables --- as above, usually more cumbersome polynomials, computed only slowly. Here we begin with the observation that any common root of f and g is also a root of all linear combinations uf+vg (u and v arbitrary polynomials of the same variable(s) as f and g). Now, we may apply the Euclidean algorithm to discover the greatest common divisor h of f and g, and indeed to discover u and v making h = u f + v g. Applied to polynomials of say X_1 and X_2, we can compute such u and v in the ring Q(X_2)[X_1] of polynomials in X_1 whose coefficients are rational functions of X_2. Now, if indeed the dimension of the solution set is 0, there should be no common denominator of f and g, so that we can write u f + v g = 1; clearing denominators gives an equation u' f + v' g = h' where h' is a polynomial in X_2. (Actually the computations can be organized to avoid denominators altogether and compute u', v', and h' directly.) Then a common solution to f=g=0 also makes h'=0, so that our search for solutions (X_1,X_2) has been reduced to a search for solutions X_2 to a single polynomial in one variable. More variables may be treated as in the previous paragraph. GROEBNER BASES The theory of elimination proceeds very nicely given equations in just one variable, so the Euclidean algorithm can be used directly. At another extreme, a set of equations in many variables may be reduced easily to an equation in one variable if all the equations are linear, using Gaussian elimination. There are a number of related approaches, collectively called Groebner basis techniques, which combine these two ideas to consider equations in more than one variable, of degrees greater than one. These are implemented in many of the popular symbolic algebra programs. Like the methods of resultants and elimination, the goal is the creation of a sequence of polynomials Q_1(X_1), Q_2(X_1, X_2), ..., Q_N(X_1, ..., X_N) whose solution set conincides with the solution set of the P_i, but which is clearly easier to address, since we may discover all integral or rational solutions X_1 to Q_1 using the techniques at the beginning of the section; then for each discover the possible solutions (X_1, X_2) by treating the equation Q_2(X_1,X_2) as a polynomial in one variable X_2, and so on. All these approaches may be interpreted geometrically as projecting the solutions (X_1, ..., X_N) of the original equations to the subspaces R^i of R^N. In every case they suffer the defect that it is possible for the solution set of the polynomials in X_1 alone, say, to include points which are not in the image of the solution set of the polynomials in X_1 and X_2. For example, there are no integral solutions to the equations X_1-1=X_2^2+X_1=0, even though the first equation alone does have solutions. In addition, these approaches produce polynomials of an unnecessarily large degree, making computation difficult. Consider the equations X_2 - X_1^2 = X_2 - c = 0. For nonzero c, we eliminate c to get the equation X_1^2 - c = 0, necessarily of degree 2 since for some c there are two points in the solution set; however, when c=0, this elimination has led to the equation X_1^2=0, which naturally has the same solution set as the simpler X_1 = 0. The phenomenon here is best described using commutative algebra: we seek the ideal I of polynomials which vanish on the solution set of our initial problem; within this ideal are smaller ideals which describe the same solution set, namely those containing I^m for any integer m. These are the ideals produced by the techniques described so far. What is preferable is an algorithm which can produce an ideal with generators of minimal degree -- equivalently, an algorithm producing the largest possible ideal, namely I itself (this is the radical of the ideal defined by the initial P_i). Such an algorithm has been incorporated into Magma; they cite "Becker & Weispfenning, chapter 8" as a source for their ideas. Application of these ideas tends to create problems requiring huge memory outlays and long execution times when for example given a dozen quadratic equations in as many variables. Considerable research is being done to investigate and improve the competing algorithms. MORE EQUATIONS THAN UNKNOWNS We conclude this section by observing that when the number of equations exceeds the number of variables, it is easy (in some sense likely) that the solution set is empty. One need only compute the solution set to any collection of N equations in the N unknowns, and then for each of those solutions verify whether or not the remaining M-N equations are satisfied. In some cases there may be an advantage to permuting the collections of polynomials used at various points during the computations, but as far as I am aware no one has seriously investigated the consequences of simply working with the N polynomials of lowest degree, then checking against the other M-N. SECTION 2b: DIMENSION ONE. Here we consider systems of N-1 integral equations in N unknowns. The solution set will be "one-dimensional" in general; for example, 0 equations in 1 unknown has as solution set the (real/complex/rational) line. We think of the solution set as a curve through the appropriate N-dimensional space. Unlike the situation in dimension zero, There is no known algorithm which can "solve" all Diophantine problems which lead to varieties of dimension one (or higher) except in the very weakest sense of the word "solve". For example, we have no real hint of an algorithm to determine whether or not the equation y^2=Q(x) has any rational solutions, which will can return an answer in finite time for every integral polynomial Q of degree 5. It is not known whether this sad state of affairs is irremediable; that is, it is not yet known whether or not our failure to produce an algorithm is a consequence of an inherent restriction from mathematical logic (akin to Matijasevic's resolution of Hilbert's 10th problem) or simply represents a poor understanding of the underlying situation on our part. Nonetheless, we have an excellent understanding of the general situation, many theorems concerning curves of low degree (genus), and a number of useful and efficient algorithms for some of the important special cases. This topic is http://www.math.niu.edu/~rusin/known-math/index/14HXX.html GEOMETRY OF ALGEBRAIC CURVES: EMBEDDING DIMENSION Using the ideas from the previous section 2a, we see that it is more or less true that we can reduce the number of variables and equations without changing the underlying nature of the solution set. Thus we focus on the special case of single equations (M=1); in order to have a one-dimensional solution set, this will assume the equation involves N=2 variables. The reader is warned however that this perspective can greatly obscure the true nature of the problem at hand. The difficulty here is related to the one already noticed in section 2a: when projecting from R^N to R^(N-1), we find a variety V' in R^(N-1) which contains the image of our variety V in R^N, and has the same dimension; but the projection from V to V' is neither one-to-one nor onto in general. Now, when V was finite-dimensional, this was not a serious problem: for each point P in V we check among the finitely-many points in V' which project to P, to see which are rational or integral; the entire process involves only finitely many steps. When V (and V' as well) is of greater dimension, there may well be infinitely many points in V', only some of which will in general be in the image of V. GEOMETRY OF ALGEBRAIC CURVES: GENUS There is a geometric picture which is extremely important when attempting to solve 1-dimensional Diophantine problems. The defining equations of our variety may be interpreted as equations over the complex numbers; then the solution set is a set of N-dimensional complex space. In general, N-1 equations will define a 1-dimensional subspace of C^N, but that will be a _complex 1-dimensional set_: locally, each point on the set appears to be surrounded not by a piece of the _real_ line R^1 (that is, it doesn't look like a curve) but rather by a piece of the _complex_ "line" C^1, which we usually think of as a (real) plane. Thus, the solution will tend to look like a _surface_, and in the absence of any degenerate points will be a fairly nice surface: a ball, perhaps, or a torus with a certain number g of holes. When plotted as a subset of R^2, the equation x^2+y^2-1=0 describes a circle; but this is only the "real slice" of the solution in complex space, which is topologically a sphere. Likewise, the curve y^2=x(x-1)(x-2)(x-3) is merely a slice through a torus; we say that this equation describes a curve of genus 1. I will not try in this document to cover all the details and nuances here; one must carefully consider singular points, projectivizations, cover maps, and the whole nine yards to get a good understanding of the concepts. I wish only to stress the importance of this particular parameter, the genus, in the study of algebraic curves. In particular, when using elimination theory, say, to pass from a curve described by M equations in M+1 variables, to a curve described by M-1 equations in M variables, we project from a variety V to a variety V'; it happens to be true that the genus of V' is never more than the genus of V, but it may well be less, and that drop in genus will fundamentally change the nature of the solution set over the rationals or the integers. Very well, then; we will consider algebraic curves defined by N-1 equations in N unknowns, with a focus on the case N=2 but a nod toward other combinations when appropriate. LINEAR EQUATIONS: EUCLIDEAN ALGORITHM Let us begin with one _linear_ equation in two unknowns. How do we compute solutions to ax + by = c ? Computing rational solutions is easy: we may take x arbitrary and let y=(c-ax)/b, with the obvious proviso about b=0. Integral solutions need not exist, as is clear from the case a=b=2,c=1. However, a necessary and sufficient condition that a solution exist is that d=gcd(a,b) divide c. Better: this condition can be checked rapidly from a and b -- no factorization is needed; this is the Euclidean algorithm. Better yet: application of the Euclidean algorithm will solve the equation ax+by=d; one need only apply Gaussian elimination to the matrix [ 1 0 a ] [ 0 1 b ] using the division algorithm (writing e.g. a=bq+r with 0 <= r < |b|) but not division per se. Of course if we can solve ax+by=d and it is known that d | c, we simply scale through to get a solution to our initial problem. Once one solution is known, all the others are easy to obtain; for if ax+by=c, then ax'+by'=c as well iff a(x'-x) = -b(y'-y); if we have computed d=gcd(a,b) then this condition is equivalent to x'= x+(-b/d)k and y'=y+(a/d)k for some integer k. So we have an infinite collection of solutions, all parameterized by one parameter k. This is a very satisfactory form of "solution" to our original problem; the only real deficiency is that it is difficult to estimate the sizes of the "smallest" solution (x,y). Thus for example if a and b are positive and relatively prime, we know ax+by=c is solvable in integers for every integer c; yet it is clearly not solvable in _positive_ integers (x,y) for all positive c, so although it is easy to see all _sufficiently large_ integers c admit a representation of this form, it is a bit difficult to determine the largest positive c not admitting a representation of the form c= ax+by. (This is the "postage stamp" problem mentioned earlier.) One interpretation of the problem solved is that we have determined a coset of the free abelian group Z^2, namely, the preimage of the integer c under the homomorphism Z^2 -> Z defined by f(x,y) = ax+by. It is sufficient to know whether or not c is actually in the image of f, and if so to compute an element (x,y) in the preimage; then all other solutions are obtained by adding to this one solution an arbitrary element of the kernel. Since we have a nonzero map Z^2->Z, the kernel is necessarily a free abelian group of rank 1. LINEAR SYSTEMS; SMITH NORMAL FORM This interpretation generalizes to other similar Diophantine problems. Suppose we are given M _linear_ integral equations in N unknowns. We may view this in precisely the same fashion as the study of the preimage of a certain element v in the abelian group Z^M, under a certain linear map f: Z^N -> Z^M. (It is the case M=N-1 which is of interest in this section, but we may handle the general case now.) As in the case N=2 the situation is fairly clear: if rational solutions are sought, we need only treat this as an ordinary linear system and solve e.g. by Gaussian elimination (although from the perspective of numerical linear algebra this is perhaps not the most efficient or stable approach). If integral solutions are sought, we need only establish what the image of f is and determine generators w_i for the kernel (necessarily a free abelian group of rank N-rank(image(f)) ). Then if w is any one solution to the Diophantine equation, we form the general solution as w + k_1 w_1 + k_2 w_2 + ..., where the k_i are arbitrary, independent, integral parameters. (If as in this section the variety really is one-dimensional, there will be a single w_1 and a single parameter k_1.) With a specific Diophantine system in mind, that is, a specific f and v, the process may be carried out efficiently; using ordinary row- and column-operations, the matrix representing f may be reduced to Smith Normal Form -- a diagonal matrix with each diagonal entry nonnegative and dividing the next. Applied the the augmented matrix with v in an additional column, this reduces the question of the _existence_ of solutions to the divisibility of various linear combinations of the entries of v by the diagonal entries of the Smith normal form. Moreover, the _computation_ of a solution then amounts to a linear transformation, a division, and then the inverse transformation -- all done easily and quickly. Finally, the kernel of f is also easily found from the Smith form; we simply set the last few transformed coordinates to zero. One example of a linear system of Diophantine equations merits special mention: given integers a,b,c,d we seek an integer x with x = a mod b and x = c mod d. Equivalently, we seek three integers x,y,z with x + by + 0 z = a and x + 0 y + d z = c; two equations in three variables, so the solution set, if nonempty, should be a coset of a rank-1 subgroup of Z^3. In fact, the Chinese Remainder Theorem asserts that a solution exists iff a = c mod gcd(b,d), and that when one solution exists, all others are found by adding and subtracting multiples of bd/gcd(b,d). Moreover, it is easy to give constructive proofs of this result and efficient algorithms to compute x,y,z. But this is really no different from the general linear problem considered in previous paragraphs. Whenever some of the equations defining a variety are linear, we may usually take these to define some of the variables in terms of the other; that is, we perform a projection from a space of higher dimension to a space of lower dimension using a projection which is almost everywhere a one-to-one correspondence. When seeking rational solutions this is a perfect correspondence. When seeking integral solutions, we see as in the discussion of sets of linear equations only, above, that additional linear equations in the general case serve only to restrict the solution set to a collection of congruence classes (modulo the determinant of the linear system defining the eliminated variables). In the sequel we will not typically consider sets of equations including linear equations. QUADRATIC EQUATIONS The next level of complexity arises when there are some quadratic equations defining a variety. The simplest 1-dimensional case is a single quadratic equation in two variables, but we may make some comments common to other situations too. We observed that the addition of linear equations to a collection of equations defining a variety has little consequence. On the other hand, every quadratic equation can significantly increase the complexity of a variety. Indeed, EVERY variety can be described using only quadratic equations! For example, the variety described by the equation x^4+x^3y+y^5=0 may equally well be described by this set of equations, quadratic and linear: a+b+c=0; a-d^2=0; d-x^2=0; b-de=0; e-xy=0; c-yf=0; f-g^2=0; g-y^2=0 (There is little to be gained by this, perhaps, but it shows that quadratic equations are sufficient to generate all types of Diophantine problems.) One indication of the difficulties associated with quadratic equations is illustrated by the single quadratic equation x^2 - y^2 = N for N a fixed integer. It is easily seen that the solution of this equation in integers is equivalent to the factorization of N. This is a succint "solution" of the problem, but computationally is very hard; indeed, it is currently impossible to factor integers of more than a couple hundred digits. In general, this means that the process of actually finding integer solutions to quadratic equations may involve factorization and thus be computationally impossible for very large problems. One novel feature which arises with quadratic equations is the presence of singularites. This is already clear with single 2-variable quadratics: consider the equation x^2 - y^2 = 0. Of course the solution set is the pair of lines y = +- x, from which it is easy to obtain both the set of integral solutions and the rational ones. This solution set is significantly different from the solutions to the similar equations x^2 - y^2 - c = 0 for nonzero c. Algebraically, we observe that the solution more closely resembles the linear case than the quadratic case. Geometrically, we see the pair of lines looks different at the origin: unlike every other point on every one of the lines or hyperbolas, the region around the origin looks like a small X (with two tangent lines) rather than looking like the real line (with a single tangent). We say the origin is a _singular point_. One can test for these by finding points on the variety where the Jacobian has less than full rank. When singular points are present, the geometry of the variety is more complex; however, we need not be too concerned with this. Indeed, the rule of thumb is that, as in the one example above, singular points tend to make the arithmetic _easier_, or perhaps more accurately, varieties with singular points tend to resemble nonsingular varieties defined by equations of lower degree. We will see examples of this later. SINGLE QUADRATICS, RATIONAL SOLUTIONS Let us return to the case of a variety determined by a single quadratic equation. We look for solutions in rational numbers first; integral solutions are trickier. We first observe that a quadratic equation may be put in "polar form" a_1 X_1^2 + a_2 X_2^2 + ... = c for some constants a_i. Indeed, if the quadratic equation is written Q + L - c = 0, where Q is a homogeneous quadratic form, L is linear in the X_i, and c is a constant, then the construction of a linear transformation to render Q diagonal is the usual Gram-Schmidt process, without the extraction of square roots. If after diagonalizing Q, we find L involves variables not present in Q, we may use this defining equation to solve for one of the variables in L in terms of the other variables; in this case we have infinitely many solutions, all parameterized by a number of parameters equal to the dimension of the variety. Otherwise we may assume all the variables present in L are present in Q, and so with a simple translation we may complete the squares and assume L=0. Then the desired form of the quadratic equation results. We assume this has been accomplished in what follows. We will focus first on the equation a x^2 + b y^2 = c in just two variables. We would like to know when such an equation has any rational solutions at all. Consider the equation x^2 - 3 y^2 = 2. If there were a rational solution (x,y), then we could express x and y in lowest terms and clear denominators to get an integral solution to the equation x^2 - 3 y^2 = 2 z^2. Now, when reduced mod 3, this would require x^2 = 2 z^2 mod 3; now, all integers have squares congruent either to 0 or 1 mod 3, and the only combinations consistent with this congruence are to have x and z congruent to 0 mod 3. But then x^2 and 2z^2 are multiples of 9, so if x^2-3y^2=2z^2, then y is also divisible by 3. This would contradict the assumption that x/z and y/z were reduced to lowest terms. So there is a mod-3 obstruction to solving this equation rationally (and integrally too, of course). The equation 3x^2 - y^2 = 6 is just a little different: there is no difficulty finding a solution mod 3, but this requires y = 0 mod 3; if, say, y=3y', then we see need x^2 - 3 y'^2 = 2, which we have just found to be impossible. Thus the difficulty is not in solving modulo 3 but rather modulo a power of 3; we refer to this as a 3-adic restriction. A quadratic equation x^2 + y^2 = -1 is also clearly insoluble rationally, since there aren't even any real solutions. There is a wonderful theorem which uses this idea to "solve" quadratic equations: Theorem: a single quadratic equation a_1 X^2 + a_2 X_2^2 + ... = a_0 admits rational solutions iff there are no real restrictions nor any p-adic restrictions for any prime p dividing some a_i. (This is due to Legendre, Gauss, Hasse, or Minkowski, depending on interpretation. It is referred to as the "local-to-global principle".) Once one rational solution to a quadratic equation is known, all others may be obtained with a rational parameterization: if (X_1, ..., X_N)=(x_1, ..., x_N) is one solution, all others are obtained by taking (X_1, ..., X_N)=(x_1 + t, x_2 + r_2 t, ..., x_N + r_N t) for arbitrary parameter values r_i and suitable t (computed by substituting X_i = x_i + r_i t into the quadratic equation and solving for t). So there are infinitely many solutions when there are any at all, and they may be easily computed from the first one. Even better, the proofs may be made effective: that is, one may actually compute a solution if there are no p-adic or real restrictions, subject only to one impediment: one must know the primes dividing the a_i. We will see in a moment that this is a fundamental restriction, that is, one cannot expect to be able to solve a single quadratic Diophantine equation and more easily than one can factor. This analysis applies more generally to varieties of all dimensions determines by a single quadratic equation. However, once the number of variables exceeds three, one may show that there are never any p-adic solutions: a quadratic equation in four or more variables always admits a rational solution if it has any real solutions. SINGLE QUADRATICS, INTEGRAL SOLUTIONS: FACTORING, MODULAR SQUARE ROOTS. We restrict our attention to curves again, that is, we consider solving a single quadratic equation in two variables. An important example of this is the equation X_1 X_2 = N for fixed N (equivalently, Y_1^2 - Y_2^2 = N). Of course it's easy to give trivial solutions with some X_i = +- 1, but to give all solutions (X_1, X_2) is equivalent to factoring N. Unfortunately, unlike most of the other algorithms we have mentioned so far, the known algorithms for factoring N are _not_ known to be very efficient. (They are certainly amazingly fast when N has less than about 150 decimal digints, but the computation time required grows very quickly with N.) Thus we see that it is reasonable to expect most problems in the class to be as hard as factoring. When describing methods of resolving Diophantine equations we shall thus freely assume that numbers can be factored whenever necessary. (In practice, algorithms should be designed to minimize this.) For example, suppose we wish to solve one quadratic equation in two variables for which the quadratic part is degenerate. After a linear change of variables, the equation may be written a X_1^2 + b X_2 = c, that is, the Diophantine equation is simply a X^2 = c mod b. One can show that b may be factored as quickly as this equation can solved for randomly-selected a and c (mod b). Conversely, if b can be factored as a product of prime powers, we need only solve modulo each prime and combine solutions with the Chinese Remainder Theorem; and finding solutions modulo a prime power is easily accomplished after solutions are found modulo the corresponding prime itself (p=2 is a bit different). This last, finally, is accomplished directly using e.g. an algorithm due to Shanks. Unlike other algorithms given so far, it involves a randomizing component; the proof that the algorithm succeeds quickly requires the Generalized Riemann Hypothesis. SINGLE QUADRATICS, INTEGRAL SOLUTIONS: PELL's EQUATIONS. Given a quadratic equation in two variables with _nondegenerate_ quadratic part, we may as in the previous section complete the squares and apply a linear transformation to express the problem in diagonal form a X_1^2 + b X_2^2 = c. Multiplying through by a and changing notation slightly, we see it is then necessary, and nearly sufficient, to be able to solve _Pell's equation_, X^2 - D Y^2 = N. Here it is most productive to view the equation as a statement about norms. Let R be the ring Z[sqrt(D)] (in) the ring of integers of the corresponding quadratic extension field of Q. Then for any alpha = X + Y sqrt(D) we have the norm(alpha) = (X+Y sqrt(D))(X - Y sqrt(D)), an integer. The key property of the norm map is multiplicativity: norm(alpha beta) = norm(alpha) norm(beta). Thus, roughly speaking, one solves Pell's equations by factoring N, solving x^2 - D y^2 = N_i for each factor N_i of N, then multiplying the various elements of R together to get one of the right norm. Unfortunately, this pattern cannot succeed as is; a proper investigation of Pell's equation parallels the study of factorization in quadratic extensions of Q, which is not trivial. First, the equation need not even be solvable rationally, as noted in the previous section, if there are primes dividing N_i to an odd power, modulo which D is not a square. But even if D is a square modulo p | N, that shows the ideal (p) splits into a product of two prime ideals in R; each has norm p, but unless they are principal, there is not an element of R with norm exactly p. Thus the _existence_ of a solution to Pell's equation requires the triviality of a certain product of prime ideals in the ideal class group of R. Moreover, the solutions are clearly unlikely to be unique when they do exist; we may replace any of the divisors of the primes (p) by their Galois conjugates to obtain more, distinct solutions. In addition, we may obtain infinitely many solutions from any one if D > 0, since in that case R is a totally real field with an infinite cyclic group of units (at least half of which have norm=1). (If D < 0, there will be only finitely many solutions for any N and D of course.) Fortunately, it is not necessary to trace all these factors about divisibility in order to compute solutions to Pell's equations in general. The key calculation is the minimal solution to the equation norm(alpha) = +-1, that is, the solution of the particular quadratic equation X^2 - D Y^2 = +- 1. Note that this requires X/Y to be very nearly sqrt(D), so one may apply the continued fraction algorithm to find good rational approximations to sqrt(D); we will eventually find a rational X/Y with X^2 - D Y^2 = +- 1. (Unfortunately, this process may be very slow for large D.) It is also true that along the way, we will obtain integer solutions to every equation of the form X^2 - D Y^2 = N for which a solution exists, with N < O(sqrt(D)). A method of reduction allows us to then extend these solutions to all solvable problems X^2 - D Y^2 = N. This completes the consideration of curves defined by a single quadratic equation. ELLIPTIC CURVES. The next level of difficulty would logically be either surves described by two quadratic equations (in three variables). Fortunately, these turn out to describe essentially the same class of curves. Moreover, the same family of curves also arises from consideration of quartic equations of the special form y^2 = P(x) where P is a polynomial of degree 4. These are the curves of genus 1, known as elliptic curves. We begin with the rational solutions, then discuss the integral solutions among them. First we observe that, as noted earlier, singularities can simplify the situation. For example, the solutions to y^2=x^3 can be parameterized a the set of pairs (t^3, t^2) for all rational t. We assume in the sequel that there are no singularities. Next we must concede an important fact: the local-to-global principle no longer applies. Indeed, there does not yet exist a completely proven procedure which will decide whether or not a particular integral cubic polynomial in two variables admits any rational solutions at all. (Conjecturally effective procedures exist and are very useful.) However, in each of the three classes of varieties mentioned, if one can find any one point on the variety, one may with simple algebra reduce the curve to Weierstass normal form: y^2 = x^3 + a x + b for some integers a and b. (Indeed, there is an easily calculated canonical form for the curve which is nearly of this type, with coefficients which are minimal in an appropriate sense.) Here we allow for the possibility that the only "point" on the variety is the "point at infinity" (introduce another variable z using which the defining equations become homogeneous, then set z=0 and see if there are rational solutions to the remaining equation(s).) At this point, we once again have a sort of structure to our solution set: We may define a group operation by noting that every straight line must intersect the curve in exactly three (possibly complex) points; given P and Q in the solution set, let the third point of intersection of the solution set and the line PQ be R; then the group operation is defined by P + Q + R = O. (Here O is the identity element of the group, the point at infinity.) This group may be shown to be finitely-generated, and a celebrated theorem of Mazur limits the torsion subgroup to a certain collection of abelian groups of order up to 16. Unfortunately, the other component of the set of rational solutions -- the computation of the (free-) rank of this abelian group, and the discovery of a set of generators of it -- is still only incompletely understood. We do not know if the rank may be arbitrarily large (we expect so); we do not know an upper bound on the numerators and denominators of x and y in a set of generators (if a bound exists, it is uselessly large). Nonetheless, quite a bit is known and in almost every example of reasonable size, the entire group structure of the solution set may be computed in a short time. Thus we can say with some precision whether or not any rational solutions exist, and when they do, we can describe an algorithm which will generate the solutions quickly. In practice, the computations necessary to perform these computations are delicate and tedious. Finally we may consider the integral solutions to the equations defining an elliptic curve. A theorem of Siegel shows that there are only finitely many such points. However, the proof is not effective, so we have no upper bound on the sizes of the integers x and y over which to check for solutions. It is possible to reason ad-hoc in many examples that the set of integer solutions found among small combinations of generators (and torsion elements) of the set of rational solutions is in fact a complete set of integer solutions. But the general determination of what the (finitely-many) integral points on a particular elliptic curve really are is still beyond our abilities. THUE EQUATIONS FALTINGS RESULT SECTION 2b: DIMENSION TWO. Previously-considered types Uses of subvarities and quotients ELLIPTIC SURFACES SECTION 2c: DIMENSION THREE or greater Previously-considered types ============================================================================== A few examples to mention ============================================================================== rational varieties / paramterizations pythag triples with pells LLL rational box congruent #s fermat soln to flt4 spider 4 5s, 4 4,s etc sum of consec. squares a cube ============================================================================== Some excised paragraphs I need to re-incorporate ============================================================================== Our goal in this document is to organize the set of problems of this type into families which admit a similar analysis. The families of problems for which a solution is available is fairly small but important. Examples in many of the families are provided. Our presentation divides into a number of smaller topics. We organize the rest of this document into cases, according to the dimension. Note that in some cases it may be easier to shift dimension to answer the question at hand. For example, if you think there are no solutions to your problem of dimension 1, it may be possible to prove this by dropping one of the defining equations to get a problem of dimension 2 and showing that this surface has no rational/integral points. Conversely, one may find points on a variety of dimension 2 by adding an additional constraint to obtain a variety of dimension 1 within it; this smaller variety may more easily be shown to have points on it. As we consider problems of increasing complexity, we will address ideas which apply to varieties of different dimensions when it is possible to do so without a great deal of added notation.