Re: multivariate polynomial inequalities

On Sat, 07 Apr 2007 21:54:48 -0500, quasi <quasi@xxxxxxxx> wrote:

On Sat, 07 Apr 2007 21:37:42 -0500, quasi <quasi@xxxxxxxx> wrote:

On Sun, 08 Apr 2007 02:13:08 +0100, Jake <foontala@xxxxxxxxx> wrote:

quasi wrote:

On Sat, 07 Apr 2007 00:55:00 +0100, Jake <foontala@xxxxxxxxx> wrote:

quasi wrote:

On Fri, 06 Apr 2007 22:35:07 +0100, Jake <foontala@xxxxxxxxx> wrote:

Hello,

I'm trying to solve the below problem.

Find k,l,m such that

k^2+(4*l*m-4*l^2)*k+4*l^2*m^2-8*l^3*m-4*m^2+4*l^4-8*l^2+4*m+8*l*m <0

if and only if l=0 or l=m

Something is wrong with the statement of the problem.

The word "Find" and the phrase "if and only if" don't make sense
together in the way that you used them.

Sorry, I'll do my best to be more clear...

Given an m >= 2, find an inequality for k (based on m) such that BOTH

1) When l=0 and l=m

k^2+(4*l*m-4*l^2)*k+4*l^2*m^2-8*l^3*m-4*m^2+4*l^4-8*l^2+4*m+8*l*m <0

AND

2) When 0 < l < m

k^2+(4*l*m-4*l^2)*k+4*l^2*m^2-8*l^3*m-4*m^2+4*l^4-8*l^2+4*m+8*l*m >= 0


Here k,l,m can be restricted to nonnegative integers with

0 <= k <= m^2
0 <= l <= m
m >= 2



In effect, I want to be able to find inequalities concerning k and m so
that both of the above properties are simultaneously satisfied.

Maybe you meant to solve the inequality subject to the restriction
that l is not zero and l is not equal to m. If that's the problem,
there are lots of solutions, for example, k=1, l=1, m=2.
If you want the complete solution set, I recommend a graphical
approach, namely let f be the polynomial on the LHS of your inequality
and then use a program such as Maple or Mathematica to graph the
implicit equation f=0 as a 3D surface so as to determine the regions
of R^3 where f is negative.

I am looking for the complete solution set, and my first attempt was to
try
the graphical approach you suggest. One problem is that it is very hard
for me to determine by eye the exact inequalities where both properties
are true from a 3d graphic.

Another more significant problem is that if I have more than 3 variables,
I
won't be able to use the graphical method right? The next stage of my
problem uses 5 variables. So, I'm looking for a general method for
solving this type of problem.

Although just getting the answer to the 3 variable problem above would be
an accomplishment I'd be very happy with.

:)

However the first thing to do is make sure the problem is stated
correctly.

Hopefully I have done this now. Sorry for any confusion!

quasi

Many thanks for your help!

Sincerely,
Jake

I think the following constraints on k are both necessary and
sufficient:

0 <= k <= 2*(m-1)

That is something similar to what I had as well. I got my answer after
solving for k when l=0. I had :

0 <= k <= 2*sqrt(m^2-m)

It just seems like it won't always be the case that choosing l=0 and solving
for k will "work." In effect, it seems like it might be possible that
there are some values of k in the constraints found in this way that might
make the second equation negative for some 0 < l < m

Questions:
1. Did you use a procedure/algorithm to find this answer?

I did the same as what you did to start. I set l=0 and solved for k in
terms of m.

Then I did the same for l=m and got the same result.

Thus we get a necessary condition

k<2*sqrt(m^2-m).

Since all the variables were specified as nonnegative integers, and
given that we know m>=2, the inequality can be re-expressed as

k<=2*(m-1).

Let f(k,l,m) represent the expression on the LHS of your inequality.

Symmetry was suggested by the fact that setting l=0 and l=m gave the
same solution for k, so I tested for symmetry. The equation
f(k,l,m)=f(k,m-l,m) reduces to an identity, proving the suspected
symmetry. Thus, we only need to consider values of l in the range
0<=l<=m/2.

At that point, I wrote a short Maple program to evaluate f numerically
for the domain:

2<=m<=1000
0<=l<=m/2
0<=k<=2*(m-1)

The requirements were always satisfied. Thus, from the earlier
algebra, we know 0<=k<=2*(m-1) is a necessary condition, and from the
numerical evidence, it appears likely that it's also a sufficient
condition.

2. Is there a corresponding proof that the constraints on k are both
necessary and sufficient?

Necessity is already proved, so we only need to prove sufficiency. The
intuition is that, for fixed values of m and l with 0<=l<=m/2, f is
monotone increasing as a function of k. To prove that, I would try to
show that the partial derivative of f with respect to k is always
positive on the domain 0<m, 0<l<m/2. That should be straightforward
but I haven't tried it, and I'm a little low on time for the next few
days. If not resolved by late next week, I'll look at it, but I don't
think it will be difficult to prove. No integer restrictions are
needed -- allow all real l,m subject to the above constraints.

3. If yes to 1 and 2, will the strategy work for larger dimensionalities
and higher powers on variables?

In the current stage of mathematical knowledge, proving polynomial
inequalities is an art form. There are lots of standard tricks and
strategies. In principle, the problem is algorithmically decidable,
but whether in polynomial time, I'm not sure. I don't know of any
easily available program which allows you to input a set of polynomial
inequalities and returns a yes or no answer (with a certificate) as to
whether or not they are simultaneously satisfiable.

A general method for finding these constraints would be great.

Yes it would, but in practice, these things get solved one class at a
time.

quasi

2 corrections ...

First, I meant to say that, with the restrictions

2<m
0<l<m/2
0<=k<=2*(m-1)

it's intuitive that f is monotone as a function of l with k,m fixed.
So the partial derivative of f with respect to l is the function that
needs to be proved positive on the above domain.

Second, with the same domain restrictions, one would need to show that
f is always positive at l=1.

So there are 2 inequalities that need to be proved. The numerical
evidence suggests that the inequalities are always satisfied, but I
haven't really looked at either of them.

quasi

Ok, I took a quick look. My suggested strategy works, so yes, it's
possible to prove sufficiency without too much difficulty. I don't
have time now to post the details, but try it -- it works exactly as
outlined.

quasi
.

Relevant Pages

  • Re: multivariate polynomial inequalities
    ... I want to be able to find inequalities concerning k and m so ... I am looking for the complete solution set, and my first attempt was to ... so I tested for symmetry. ... Necessity is already proved, so we only need to prove sufficiency. ...
    (sci.math)
  • Re: multivariate polynomial inequalities
    ... find an inequality for k such that BOTH ... I am looking for the complete solution set, and my first attempt was to ... so I tested for symmetry. ... Necessity is already proved, so we only need to prove sufficiency. ...
    (sci.math)
  • Re: Systems of inequalities: methods.
    ... >non-linear) inequalities. ... I am a bit overwhelmed with the amount of information ... >that verify the conditions for a set of non-linear equations). ... For the nonlinear case the boundary of the solution set will consist of ...
    (sci.math)