Welcome to MathOverflow

Question

13

3

Suppose I have a bunch of polynomial equations with coefficients in a number field, and suppose further that I'm guaranteed a priori that they have a solution in that number field. Can I leverage that knowledge into a technique for solving the equations more easily? The cases we care about are massively overdetermined systems of linear and quadratic equations.

edited Nov 15 2009 at 19:25

Lavender Honey
6,024●30●69

asked Oct 25 2009 at 0:03

Noah Snyder
11.3k●1●26●71

I am curious about the origin of the equations you are interested in. Could you say a few words about it ? – jvp Oct 25 2009 at 2:12

2

Over R, systems of quadratic equations (especially massively overdetermined ones) are no easier to solve than general systems of equations, by Kempe's Universality Theorem for linkages. (Tim Abbott and I have an unpublished paper on this.) I'm not sure whether the proof works rationally, though. – Reid Barton Oct 25 2009 at 4:31

The origin of the equations is trying to construct fusion categories and subfactors by hand. The equations come from relations that we know to be satisfied. – Noah Snyder Oct 25 2009 at 17:10

moonface · Answer 1 · 2009-10-25 03:41:24Z UTC

3

Practically speaking: I would try to reduce the equations modulo several small primes (or prime powers), solve them by brute force, and then try to lift to solutions in your number field using the chinese remainder theorem. It might be helpful to combine this with solving them to high precision over the real (or complex) numbers.

answered Oct 25 2009 at 3:41

moonface
486●3●3

Somewhat better? Find a local solution with invertible Jacobian, on a subset of equations maybe, and use a Newton technique to lift it high, so that LLL (p-adic) will find it in the number field. I don't think that $R$ or $C$ will help as well as p-adic for converging. What is the expected field degree, and size of the solutions? The largest I have seen with this is 8-10 variables and field degree 50-100. The work should be for finding the local solution. – Junkie Apr 30 2010 at 8:14

David Lehavi · Answer 2 · 2009-10-25 11:28:13Z UTC

I have to say that this sounds suspiciously close to Matiyasevich's proof of Hilbert's 10th problem (Yuri V. Matiyasevich, Hilbert's Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993). The "yoga" of his proof is that you can have some "Godel coding" on systems of quadratic and linear forms, which shows that solving a system of such equations is hard from a logic/TCS point of view.

Charles Siegel · Answer 3 · 2009-10-25 00:16:50Z UTC

2

Should be able to use Groebner bases and elimination theory to do it, I think. Though in the case of linear and quadratic equations, I'm not sure how much help it will be.

answered Oct 25 2009 at 0:16

Charles Siegel
10.8k●2●31●81

No no, these are massively overdetermined. In typical examples, we're looking at >10^5 quadratics in 20 variables. Our experience so far with Groebner bases has been unhappy -- you can't just hand off the entire list of equations to a Groebner basis implementation and expect it to cope with modern RAM constraints. If this sounds wrong, please tell us! – Scott Morrison♦ Oct 25 2009 at 6:46

Ahh, if they're THAT overdetermined, I can't really offer much help to you. I don't really have anything that can handle those numbers. – Charles Siegel Oct 25 2009 at 14:58

3

Generally Groebner basis algorithms are doubly exponential, never let them NEAR anything of that magnitude – Michael Hoffman Oct 29 2009 at 14:59

David Speyer · Answer 4 · 2009-10-26 10:46:57Z UTC

One minor comment: if you can ever reduce to solving equations in a single variable, and looking for rational roots, then you can use the rational root theorem. You can reduce to the case where your number field is the rationals easily enough. (For example, if you started out looking for roots in Q(i), write everything as a+bi.) But I don't know that there is any good way to reduce to equations in a single variable.

Ilya Nikokoshev · Answer 5 · 2009-10-25 00:39:20Z UTC

0

Well, it's certainly easier to intersect lines and quadrics. I would simply go on intersecting all lines, and then select some nicer quadrics to intersect until I'm having a finite set of points, from which I would eliminate the wrong points by using more quadrics until one is left, the answer.

answered Oct 25 2009 at 0:39

Ilya Nikokoshev
8,989●5●30●73

Typically, by the time we get down to a finite set of points, that finite set would have size 2^20 or so. Not fun in practice. – Scott Morrison♦ Oct 25 2009 at 6:48

Solving polynomial equations when you know in which number field the solutions live

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

5 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.