From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis Subject: Re: Number of zeros of multivariable polynomials? Date: 27 Mar 1998 23:59:16 GMT In article <35162D70.137A@ee.usyd.edu.au>, Miroslav Trajkovic wrote: >Can anyone give me a good reference to mutlivariable polynimials >solving? (Computational) algebraic geometry? That's really a much more algebraic field than is typically discussed in this newsgroup, but I didn't see any other way to handle this. Indeed, the problem turned out to be very interesting as a challenge to the techniques of which I am aware for carrying out this sort of computation. I've set follow-ups to include sci.math.symbolic, which seems more appropriate. >Let x = [x1 x2 x3] and let > >L(x) denote all liear polynomials of x >(L(x) = a0 + a1*x1 + a2*x2 + a3*x3;) and > >S(x) all square polynomials of x >(S(x) = b0 + b1*x1 + b2*x2 + b3*x3 + b4*x1*x2 + ... + b9*x3*x3). > >How many solutions exist for the system > >u^3*L1(x) = 1 >v^3*L2(x) = 1 >u*L4(x)+L5(x) = 0; >v*L6(6)+L7(x) = 0; >u*v*S1(x) + S2(x) = 0; > >where u and v are variables? My best guess is 40 in the "generic" case. Here's my reasoning. There will be many special cases, but 1. generically you can change variables so that L1 = x1, L4 = x2, L6 = x3; 2. the solutions to u and v fall out from the third and fourth equation and the remaining three variables must satisfy three simple polynomial equations Taking advantage of both ideas reduces us to this problem -L5^3 * x1 = x2^3 -L7^3 * L2 = x3^3 L5*L7*S1 + x2*x3*S2 = 0 for generic linear L2, L5, L7 and quadratic S1, S2. You could proceed to eliminate other variables here, too, and get down to one equation in one unknown x3, in principle. For generic choices of the coefficients, there is one solution (x1,x2,x3) to the original problem for each solution x3, so you only need the degree of that final equation. Sort of. Well, don't hold your breath. The computations are beyond what your local CAS can accomplish. There are a few tricks you can use to predict the answer, but I'm not willing to guarantee it. On the other hand, you could try a random set of L2, L5, L7, S1, S2, and try the elimination that way. This leaves just three variables, with numeric (say, integer) coefficients. Well, I tried that; Maple sat for 24 hours trying to eliminate two variables, and I had to kill it because it was swapping huge blocks to disk. I had better luck with Magma -- it only took a few hours to produce what I thought I wanted: K:=RationalField(); c0:=1; c1:=1; c2:=2; c3:=3; P:=PolynomialRing(K,3,"lex"); L2:=c0+c1*x1+c2*x2+c3*x3; L5:=4-x1-3*x2+5*x3; L7:=1+4*x1+9*x2+16*x3; S1:=2+x1-x2+3*x3-x1^2+2*x2^2+5*x3^2-6*x1*x2+7*x1*x3-8*x2*x3; S2:=-1-2*x1+3*x2-5*x3+7*x1^2-11*x2^2+13*x3^2-17*x1*x2+19*x1*x3-23*x2*x3; I:=ideal; I first rather lazily tried Magma's command EliminationIdeal(I,2); The result was a degree-55 polynomial in x3, which factors as x3^3*(quartic)^3*(irreducible degree-40). So we expect maybe 45 or so points in the intersection. But that's missing the "exceptional" points (where several have the same x3). So really we have to Do The Right Thing. The question here is the number of components in a variety of (we hope) dimension zero, determined by an ideal generated by three polynomials in (say) Z[x1, x2, x3]. The algebraic geometry involved can be expressed ring-theoretically: we need to know the decomposition of the radical of that ideal as an intersection of prime ideals. High-flying talk? Fear not. Magma also has a command RadicalDecomposition(I); to replace the EliminationIdeal. It computes exactly these primes, and as a bonus determines the number of points in each of the corresponding varieties. With a few more hours of machine time we find the variety has four points with x3=0, four with x2=0, and 40 in an irreducible component with neither x2=0 nor x3=0. (Actually I got this result faster first and then corroborated more slowly: Declaring instead p:=157526249; (or some other large prime) and K:=GF(p); gives the decomposition into prime ideals fairly quickly; one notices the x2=0 and x3=0 patterns quickly, and verifies them integrally, and then finds the remaining factor must be irreducible to be consistent with the data from a few such primes. Of course, it _could_ happen that I just happened to choose primes from among the set over which the number of points decreases from the integral picture, so I had to verify the whole calculation integrally, which took much longer. OK, I'm lying: I killed it after about an hour.) Since we're going more carefully here, it's worth noting that the cases x2=0 or x3=0 don't translate so nicely to the original 5-variable problem. One can re-run the program starting with a 5-variable ring, and do it all properly. Each of the 40 points indicated above does indeed lead to a (unique) point in C^5; those with x2=0 or x3=0 are not in the image of the variety in C^5. So, after many wasted machine cycles, we are led to the conclusion that there are 40 points in this solution set in C^5. Of course, this all pertains only to the _particular_ choices I made for L2 L5 L7 S1 S2, and assumes L1, L3, and L6 are linearly independent. I tried another set of choices: p:=10000000019; K:=GF(p); P:=PolynomialRing(K,5,"lex"); L1:=x1;L4:=x2;L6:=x3; c0:=1; c1:=1; c2:=2; c3:=13; L2:=c0+c1*x1+c2*x2+c3*x3; L7:=1-4*x1+10*x2+16*x3; L5:=4-x1-8*x2+6*x3; S1:=2+x1-x2+3*x3-11*x1^2+2*x2^2+5*x3^2-6*x1*x2+7*x1*x3-17*x2*x3; S2:=+1-2*x1+99*x2+0*x3+7*x1^2-111*x2^2+13*x3^2-17*x1*x2+11*x1*x3-23*x2*x3; I:=ideal; RadicalDecomposition(I); Conclusion: another set of 40 points mod p, presumably 40 points over the rationals too. Taking another leap of faith, we expect 40 points in C^5 for almost all choices of the L's and S's. (I wanted to be a little more general, so I tried replacing the first Magma ring (and leaving c0...c3 variable): L:=GF(p); K:= FunctionField(L, 4); but that took too long too, and exhausted my machine's memory as well. I'll simply _assume_ that I was not unlucky enough to choose a set of L's and S's which gave a non-generic solution set.) So what are you going to do with these equations? If you need to solve them numerically for a specific set of L's and S's, I guess I would (approximate those rationally, then) deduce the integral polynomials which define the solution set by computing them mod-p for several p and combine using the Chinese Remainder Theorem. These integral polynomials can be solved numerically to high precision, giving approximate coordinates for the points in C^5. These can then be improved iteratively using the initial equations. (Of course you can go straight for a numerical solution, but this method would provide the initial points for iteration, and also would ensure the location of all solutions.) The general tool for computing the number of points in an algebraic variety of dimension zero is Bezout's theorem, but that's hardly the silver bullet which makes this problem trivial. You need a fair amount of algebraic geometry even to know quite what the theorem intends to say. On the other hand, elimination is fairly easy; the variant known as Grobner Basis calculations would probably work well enough here. I guess this would be called (computational) commutative ring theory. The documentation for Magma contains several references. dave Algebraic geometry: index/14-XX.html Commutative rings: index/13-XX.html