# Fast checking that overdetermined polynomial system does not have a solution

As a result of some inductive procedure for each $n$ I have a system of about $n^2$ polynomial equations with $n$ variables with integer coefficients, which can be precisely computed. As the system is quite seriously overdetermined I suspect that it has no complex solutions, which is what I need to numerically verify.

I am not an expert in the area, but I have seen somewhere that while in general case the complexity of finding Groebner basis grows very fast, for overdetermined systems there are faster aglorithms not even using Groebner bases that in some cases can even produce polynomial growth of complexity.

Also as I have a particular system, are there some probabilistic algorithms that can give lower complexity as I am not interested in theoretically worst possible cases, but rather have a concrete example.

P.S.Question corrected, thanks to Lev Borisov.

P.P.S. The main thing which I have in mind is to check that the generated ideal contains $1$ either with Groebner bases or without them. However I do not insist on this method of course.

• Are your coefficients exact or is everything approximate? What sort of equations are they? Apr 8 '14 at 21:21
• The coefficients are integers. For each $n$ I have about $n^2$ polynomial equations of $n$ variables with integer coefficients, which can be precisely computed. I can not say more as I get these equations as a result of some inductive procedure. Apr 8 '14 at 22:58
• Since you are talking about numerical verification, the value of $n$ will likely determine the best suited method. What is your typical $n$? Apr 8 '14 at 23:19
• That is a wonderful question. Short answer - the bigger the better. More precisely, let us first assume that $n$ is about 15-20. If everything goes OK, I would increase $n$ to say 1000. If still can verify, I would again increase $n$ by order of 10. In the other words, ideally, would be good to be able to verify it for ranges of $n$ say up to $10^6$ but even $n=20$ would be not bad too! Apr 8 '14 at 23:20
• Mathematica has a method for this based on cylindrical decomposition. It will probably be much too slow even for $n=10$, though. Sep 20 '14 at 12:40

## 1 Answer

I know of two methods that work well for problems with low dimensionality; i.e. $n \leq 50$. The first method, due to Lasserre, works by transforming the problem into a series of SDP's. You can find an introduction to that method in [1]. There is a software package, called GloptiPoly, that uses this method.

The second method is to apply the branch-and-bound algorithm. Note that this method requires you to somehow reduce your search space to some bounded subset of $\mathbb{R}^n$. This shouldn't be too hard, since you are concerned with polynomials. Anyway, given a bounded space, you use some range computation method (e.g. Interval Arithmetic (IA), Affine Arithmetic (AA), ...) to bound your polynomial. If the bounds rule out a root, you are done. If not, you subdivide the search space and recurse. The basic logic being simple, sophisticated algorithms of this kind employ a lot of accelerating techniques. Some keywords to look for include: Constraint Propagation, Interval Newton Method, Affine Relaxations. See [2] for a detailed explanation of a method employing several of these accelerating techniques.

I don't have a lot of experience with using the first method, so I'm not sure how it will work for your problem. However, I've solved lots of tightly coupled equations with a method of the second kind, and I think it might serve you well for $n \leq 50$.

[1] Chapter 3: Polynomial Optimization, R. Cominetti, F. Facchinei, J.B. Lasserre, Modern Optimization Modelling Techniques.

[2] A Reliable Affine Relaxation Method for Global Optimization, J. Ninin, F. Messine, P. Hansen, Technical Report, IRIT and Cahiers du GERAD.

• Thank you very much for the answer! I will try to take a look for what you have written. However couple of things, which I have in mind: 1) As far as I understand you are suggesting just to check that there are no roots by the "brute force" by showing that the attempt to find the root would fail ( or am I wrong?) . In this case I have no idea how to reduce the problem to the bounded subset of ${\mathbb{R}}^n$ as there are polynomials which can have unbounded zero sets ( say take the equation $xy=0$). 2) What I had in mind is to check algebraically that the generated ideal contains 1. continue Apr 9 '14 at 0:17
• continue here .. which is what is usually done with Groebner bases, but I have seen somewhere ( if needed I can try to find out ) that in case of overdetermined systems the faster methods then Groebner bases exist. But thank you for the answer! Apr 9 '14 at 0:19
• You're welcome. The second method indeed requires an auxiliary procedure to bound the feasible set. The first method does not require that assumption, so it might be useful to you if you can't find a fast algebraical method. Apr 9 '14 at 0:42
• The main difficulty with the bound here is that the system is defined inductively, I do not have it "at hands". So except that the coefficients are integers I do not have any idea how it will look like. And so imagine that for, say, $n=10$ I will get about $100$ polynomial equations of $10$ variables for which I will have to "manually" bound the solution set. Doesn't sound like an easy task huh?:) Not even to mention what would happen for $n=20$ :) That is why I would prefer not to look " inside the system" at all. Apr 9 '14 at 0:48
• Note that the 1st method is not exact, and the software mentioned does its work with the usual floating point numbers. Particularly if your integer coefficients will get long, this won't be very reliable. That is to say, that you will have to look inside your systems just to make sure the coefficients don't blow up. Apr 13 '14 at 20:01