[Date Index] [Thread Index] [Author Index]

Re: Solve or Reduce on a monstrosity of an expresssion (and a prize!)

• To: mathgroup at smc.vnet.net
• Subject: [mg57296] Re: [mg57278] Solve or Reduce on a monstrosity of an expresssion (and a prize!)
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Tue, 24 May 2005 05:12:33 -0400 (EDT)
• References: <200505230620.CAA04045@smc.vnet.net> <EEA0FBBD-9C31-419A-8D0B-7C73AE4DA32E@akikoz.net>
• Sender: owner-wri-mathgroup at wolfram.com

On 23 May 2005, at 21:17, Andrzej Kozlowski wrote:

> On 23 May 2005, at 15:20, Daniel Reeves wrote:
>
>
>>
>> Mathemahomies,
>>  I have a beast of a function (though continuously differentiable)  
>> that I
>> need to prove is strictly decreasing in a certain range (which I  
>> *know* it
>> is just from plotting it).  Every combination I can think of of  
>> Reduce and
>> Solve and Simplify with assumptions leaves Mathematica spinning  
>> its wheels
>> indefinitely.
>>
>> Do you have any ideas for cajoling Mathematica into crunching through
>> this?
>>
>> Here's the function:
>>
>> f[x_,n_] := 9/2/c[x,n]^2*(n+1)b[x,n]^2 (x-d[x,n])(x-x*d[x,n]+d[x,n]+
>>             d[x,n]^2+n (d[x,n]-1) (x+d[x,n]))
>>
>> where
>>
>> a[x_,n_] := 9*(n+1)^2 + Sqrt[3(n+1)^3 (x^2 (n-1) + 27(n+1))];
>>
>> b[x_,n_] := (a[x,n](n-1) x^2)^(1/3);
>>
>> c[x_,n_] := -3^(2/3) x^2 (n^2-1) + 3^(1/3)(x^2(n^2-1) (9 + 9n +
>>             Sqrt[3(n+1) (x^2(n-1) + 27(n+1))]))^(2/3);
>>
>> d[x_,n_] := c[x,n] / (3 b[x,n] (n+1));
>>
>>
>> Show that f[x,n] is strictly decreasing for x in (0,(n-1)/n) for all
>> integers n >= 2.
>>
>> Note that the limit of f[x,n] as x->0 is (n-1)/(2(n+1)) > 0
>> and f[(n-1)/n,n] == 0.  So it would suffice to show that f' has no  
>> roots
>> in (0,(n-1)/n).
>>
>>
>> PS: I have a cool prize for information leading to a solution!  
>> (whether or
>> not it actually involves Mathematica)
>>
>> -- 
>> http://ai.eecs.umich.edu/people/dreeves  - -  google://"Daniel  
>> Reeves"
>>
>> Sowmya:   Is this guy a mathematician?
>> Terence:  Worse, an economist.  At least mathematicians are honest  
>> about
>>           their disdain for the real world.
>>
>>
>>
>
> Unfortunately I can only manage the most trivial case, n=2, which I  
> do not think deserves any prize but it seems to show that if anyone  
> does get the prize it will be well deserved.
>
> We evaluate your definitions and then set
>
> n = 2;
>
> Even in this simplest of cases trying to use Solve directly
>
>
> Solve[D[f[x,2],x]==0,x]
>
> $Aborted
>
> takes for ever, so we resort to Groebner basis (actually what I  
> just called "a hack" in another discussion ;-))
>
> We first evaluate
>
> z = FullSimplify[D[f[x, 2], x] /. x^2 + 81 -> u^2, u > 0];
>
> And then use GroebnerBasis:
>
>
> GroebnerBasis[{x^2 + 81 - u^2, z}, {x}, {u}]
>
> {4*x^2 + 16*x - 9}
>
> This we can actually solve (even without Mathematica):
>
>
> r=Solve[4*x^2 + 16*x - 9 == 0, x]
>
> {{x -> -(9/2)}, {x -> 1/2}}
>
> we can check that the derivative of f[x,2] does indeed vanish at  
> these points:
>
>
> D[f[x,2],x]/.r//FullSimplify
>
> {0,0}
>
> Assuming that Groebner basis is correctly implemented this also  
> shows that f'[x,2] has no roots in the interval (0,1/2) so we are  
> done.
>
>
> Unfortunately the same method with n=3 already seems to take for  
> ever. For small n>2 it may be possible perhaps to combine in some  
> way numerical methods with Groebner basis to show similarly that D[f 
> [x,n],x] has no roots in the interval (0,(n-1)/n) but obviously  
> this won't work for a general n. At the moment the general problem  
> looks pretty intractable to me, so much that I am almost willing to  
> offer an additional prize to whoever manages to solve it (but I  
> won't make any offers before seeing other people's attempts ;-))
>
> Andrzej Kozlowski
>
>

I still have not got a proof, but thinking about the above proof for  
the case n=2 some conjectures come to my mind which might just  
possible point tothe the way to the general proof. The main idea is  
Daniel Reeves' one: to show that D[f[x,n],x] is not zero on (0,(n-1)/ 
2). If we look at the above argument for n=2  we see that it amounts  
the fact that D[f[x,n],x]==0 has just two rots, one of which is at  
(n-1)/n and the other is negative. One is tempted to conjecture that  
the same is true for any n: the derivative has just two roots, one is  
at (n-1)/n and the other is negative (I have no good guess at this  
time as to where it might be, in the n=2 example it is at -9/2).

At least for one part of the conjecture there is some confirmation:


D[f[x,3],x]/.x->2/3//FullSimplify

0


FullSimplify[D[f[x, 4], x] /. x -> (4 - 1)/4]

0

although again the general n seems to take for ever. There may also  
be a non-computational proof that the equation can only have two  
roots and that one of them must be negative. I will think about it  
more when I have a little more free time but at the moment i view  
these only as long shot conjectures.

Andrzej

• References:
  • Solve or Reduce on a monstrosity of an expresssion (and a prize!)
    • From: Daniel Reeves <dreeves@umich.edu>