The complexity of Diophantine equations

Colloquium McMaster University Hamilton, Ontario

April 2005

The basic question

A Diophantine equation is a polynomial equation f(x_{1}, …, x_{n}) = 0 with integer coefficients, for which one seeks rational or integer solutions.

Question. Given a diophantine equation, how hard is it to find a solution?

Matijasevich. This problem of determining the existence of a solution is undecidable in general.

It is natural to try to develop theories for more restricted classes.

The size of a Diophantine equation

If a/b ∈ Q, Height (a/b) := h(a/b) = log (ab).

h((x_{1}, …, x_{n})) = h(x_{1}) + ⋯ + h(x_{n}).

If f = ∑_{J} a_{J}x^{J} is a diophantine equation,

h(f) = _{J}^{∑} h(a_{J}).

The height of an equation is, roughly speaking, the amount of paper required to write it down.

Complexity

Definition A class C of equations is said to be strictly polynomial if there is an n ≥ 1 and an algorithm which for each equation E ∈ C produces a solution to E in at most h(E)^{n} operations.

Less formally: the time required to find a solution for E is roughly equivalent to the time it takes to write E down.

Some examples

The following (not very interesting!) classes of Diophantine equations are strictly polynomial:

C = {Equations in one variable }

C = { systems of linear equations }

Question. Are there any other naturally occuring classes of non-linear Diophantine equations in more than one variable which are strictly polynomial?

Factorisation

Consider

FACT := {xy = n, x, y ≠ ±1; as n ∈ Z}. Conjecture The class FACT is not strictly polynomial. Much of modern cryptography rides on this conjecture, although it seems difficult to prove.

Conics

Consider

CONICS = {ax^{2} + by^{2} + cz^{2} = 0, as a, b, c ∈ Z}

Theorem (Hasse-Minkowski) Suppose given an oracle for extracting the square root of m modulo n in time which is polynomial in log (n). Then CONICS is strictly polynomial.

Sketch of proof

1. Find λ_{a}, λ_{b}, λ_{c} ∈ Z such that

λ_{a}^{2} = −b/c (mod a), λ_{b}^{2} = −a/c (mod b),

λ_{c}^{2} = −a/b (mod c).

2. Let Λ = set of (x, y, z) ∈ Z^{3} with z = λ_{a}y (mod a), z = λ_{b}x (mod b), y = λ_{c}x (mod c), plus parity conditions.

(x, y, z) ∈ Λ ⇒ ax^{2}+by^{2}+cz^{2} = 0 (mod 4abc).

Sketch of proof (cont’d)

3. Find a short vector (x_{0}, y_{0}, z_{0}) ∈ Λ. This is similar to a gcd calculation, and can be done very fast (in polynomial time).

4. Geometry of numbers:

4abc divides |ax_{0}^{2} + by_{0}^{2} + cz_{0}^{2}| < 4abc hence ax_{0}^{2} + by_{0}^{2} + cz_{0}^{2} = 0. This algorithm for finding (x_{0}, y_{0}, z_{0}) works in time which is polynomial in log (abc).

Applications

Theorem The classes •CONICS _{a,b} := {ax^{2}+by^{2}+pz^{2} = 0, p prime } •2SQUARES := {x^{2} + y^{2} = p, p prime }; are strictly polynomial. Question. Are there classes of Diophantine equations which can be proved to not be strictly polynomial?

Pell’s Equation

Fermat’s “favorite” Diophantine equation:

PELL := {x^{2} − dy^{2} = 1, as d ∈ Z}. Group law: (x_{1}, y_{1})⋆(x_{2}, y_{2}) := (x_{1}x_{2} +dy_{1}y_{2}, x_{1}y_{2} +y_{1}x_{2}). Fundamental solution: (±x, ±y) = (x_{∗}, y_{∗})^{⋆k}. Theorem. The class PELL is not strictly polynomial.

“Proof”

Here are some fundamental solutions.

d = 2. x = 3, y = 2.

d = 61. x = 1766319049, y = 226153980.

d = 109. x = 158070671985249, y = 15140424455100.

d = 991. x = 379516400906811930638014896080, y = 12055735790331359447442538767.

Induction (à la Fermat): h(x_{0}, y_{0}) can be as large as √d.

Hence merely writing down the fundamental solution can take as many as √d >> log (d)^{n} operations.

Polynomial complexity

Problem P(E,h). Given E ∈ C and h >> h(E), (more precisely: h > exp (h(E))) find a solution x of E with h(x) < h, if it exists, or terminate with an appropriate message, otherwise.

Obvious algorithm: run over all solutions with height ≤ h until a solution is found (or not).

This requires a number of operations which is exponential in h.

Definition. A class C of Diophantine equations is said to be solvable in polynomial time if there is n ∈ N and an algorithm that solves P (E, h) in at most h^{n} operations.

Less formally: the time required to find a large solution for E is roughly equivalent to the time it takes to write the solution down.

Caveat: FACT is trivially solvable in polynomial time according to this definition.

Pell’s equation

Theorem The class PELL is solvable in polynomial time. Algorithm for computing (x_{∗}, y_{∗}): the continued fraction method.

√d = a_{0} + _{\frac{1}{a_{1}+\frac{1}{a2+···}}}

\frac{x_{n}}{y_{n}} = a_{0} + _{\frac{1}{a_{1}+_{\frac{1}{a2+···+\frac{1}{an}}}}} .

For n >> 0, (x_{n}, y_{n}) = (x_{∗}, y_{∗}). This approach requires O(log (x_{∗})) operations.

Elliptic curves

The class ELL := {y^{2} = x^{3} + ax + b, a, b ∈ Q}.

The addition law on an elliptic curve

The Mordell-Weil theorem

Theorem. The set E(Q) is a finitely generated abelian group.

E(Q) = T ⊕ Z^{r}, r ≥ 0.

Question. Is there an algorithm to compute E(Q) given E?

The answer is not known! (It is related to the Shafarevich-Tate conejcture, and the Birch and Swinnerton-Dyer conjecture.)

Related Question Is ELL solvable in polynomial time?

This question might seem more approachable to the uninitiated.

A conjecture/provocation

Conjecture The class ELL of elliptic curve equations is solvable in polynomial time.

This conjecture asserts that it should be possible to “zero in” on solutions to elliptic curve equations much more rapidly than by performing an exhaustive search.

It appears to be intimately connected to the Birch and Swinnerton-Dyer conjecture.

An example of Bremner and Cassels

The elliptic curve

E : y^{2} = x^{3} + 877x

has rank one and generator given by:

x = \frac{612776083187947368101^{2}}{78841535860683900210^{2}}

y = 25625626798892680938877 68340455130896486691 53204356603464786949 78841535860683900210^{3}

Another example

Consider the equation

101y^{2} = x^{3} − x^{2} − 10x − 19/4.

The smallest solution has

x = \frac{1081624136644692539667084685116849}{246846541822770321447579971520100}

This solution was found on a computer in a few seconds.

The Hasse-Weil L-series

Let N :=Conductor(E), and define

a_{p} := \{ \begin{matrix}p + 1 − #E(Z/pZ) & if p |̸N; \\ 0, 1, or − 1 & if p|N. \end{matrix}

a_{p^{n}} = a_{p}a_{p^{n−1}} − pa_{p^{n−2}},
a_{rs} := a_{r}a_{s}, (r, s) = 1.

Hasse-Weil L-function attached to E:

L(E, s) = _{n}^{∑} a_{n}n^{−s} = _{p}^{∏}(1 − a_{p}p^{−s} + p^{1−2s})^{−1}

L(E, 1)“ = ” _{p}^{∏} \frac{p}{#E(Z/pZ)} .

The Hasse-Weil L-series is expected to encode arithmetic information about E, notably its rank.

The Birch and Swinnerton-Dyer conjecture

Conjecture. The L-function L(E, s) extends to an analytic function of s ∈ C, and

rank (E(Q)) = ord_{s=1} L(E, s).

The leading term of L(E, s) is also expected to be expressible in terms of the heights of the generators of E(Q), and of the conjecturally finite Shafarevich-Tate group.

Tate (1974) “... this remarkable conjecture relates the behaviour of a function L at a point where it is at present not known to be defined to the order of a group LLI which is not known to be finite.”

Modularity

Problem: Give a “closed formula” for the a_{n}? Consider the generating series:

f_{E}(q) := ∞ ; ∑ ; n=1 a_{n}q^{n}, q := e^{2πiτ} .

Hecke’s congruence group:

Γ_{0}(N) := \{( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ SL_{2}(Z) s.t. N|c\} .

Definition. A modular form of weight k and level N is a function

f(z) = ∞ ; ∑ ; n=0 b_{n}e^{2πinz}

such that

f (\frac{az + b}{cz + d} ) = (cz + d)^{k}f(z),

for all ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ_{0}(N).

Wiles’ Theorem

Theorem (Wiles) The generating function f_{E}(z) is a modular form of weight 2 and level N. First consequence: The Hasse-WeilL-series

L(E, s) = (2π)^{s}Γ(s)^{−1} ∫_{0}^{∞} f(it)t^{s}\frac{dt}{t}

extends to an analytic function of s ∈ C. Hence the left-hand side of the BSD conjecture makes sense!

Modular parametrisations

Second consequence: Let

exp_{E} : C ⟶ E(C)

be the Lie exponential. There exists λ ∈ C^{×} such that

Φ(τ) := exp_{E} (λ ∫_{i∞}^{τ} f(z)dz)

descends to a well-defined analytic map

Φ : H/Γ_{0}(N) ⟶ E(C),

called the modular parametrisation. H := {z ∈ C s.t. ℑ(z) > 0} (the Poincaré upper half-plane.) Key remark. The map Φ can be calculated in polynomial time, in the sense that d digits of accuracy can be obtained in O(d^{n}) operations.

The Heegner point construction

Let H′ be a the set of τ ∈ H which generate a quadratic imaginary field K: τ = a + b√d, with a, b, d ∈ Q. Theorem. If τ belongs to H ∩ K, then Φ(τ) belongs to E(K^{ab}). K^{ab} = maximal abelian extension of K. In fact, the smallest abelian extension H_{τ} over which Φ(τ) is defined can be specified explicitly. For τ ∈ H′, define P_{τ} := trace _{H_{τ}/Q}(Φ(τ)) The point P_{τ} is called the Heegner point attached to τ. Theorem. If h(P_{τ}) < h, then P_{τ} can be computed in poly(log (h)) operations.

Main Properties

Theorem (Kolyvagin) If r = rank (E(Q)) ≠ 1, then P_{τ} is torsion for all τ. Theorem (Gross-Zagier). If ord_{s=1} L(E, s) = 1, then P_{τ} is of infinite order for infinitely many τ. Corollary Let ELL _{1} := {E ∈ ELL s.t. ord_{s=1} L(E, s) ≤ 1}. The class ELL _{1} is solvable in polynomial time.

The number field case

In contrast with ELL _{1}, the complexity of ELL seems very hard to study, and we find ourselves with little of interest to say about it. We seek refuge in the number field case. Let F =finite extension of Q. •ELL (F) := {Elliptic curves over F }; •E ∈ ELL _{1}(F) ⇔ ord_{s=1} L(E/F, s) ≤ 1. Hard conjecture The class ELL (F) is solvable in polynomial time. Easier conjecture The class ELL _{1}(F) is solvable in polynomial time. Thesis. This last conjecture, while seemingly not out of reach, is worthwhile and presents many interesting challenges.

Real quadratic fields

Let F =real quadratic field. Assume all elliptic curves over F are modular. ELL ′_{1}(F) = set of elliptic curves E ∈ ELL _{1}(F) such that there is a prime p of O_{F} which divides N(E) exactly. Theorem (Matt Greenberg, 2005) The class ELL ′_{1}(F) is solvable in polynomial time. The proof uses ideas arising from the theory of p-adic integration and the theory of overconvergent p-adic modular forms (attached to definite quaternion algebras). What about ELL _{1}(F)?

The class ELL _{1}(F)

There is a conjectural algorithm for solving any equation in ELL _{1}(F) in polynomial time, which works reasonably well in practice.

Darmon, Logan. Periods of Hilbert modular forms and rational points on elliptic curves. IMRN (2003) no. 40, 2153-2180.

Useful theoretical insights about elliptic curves are to be gained by carefully considering ELL _{1}(F) for other fields F, such as the imaginary quadratic fields.