Re: Solve or Reduce on a monstrosity of an expresssion (and a prize!)
- To: mathgroup at smc.vnet.net
- Subject: [mg57421] Re: Solve or Reduce on a monstrosity of an expresssion (and a prize!)
- From: Daniel Reeves <dreeves at umich.edu>
- Date: Fri, 27 May 2005 04:57:12 -0400 (EDT)
- References: <200505230620.CAA04045@smc.vnet.net> <EEA0FBBD-9C31-419A-8D0B-7C73AE4DA32E@akikoz.net> <Pine.LNX.4.58.0505231817420.9452@boston.eecs.umich.edu> <458D701E-37FA-425F-89C4-52A5628E22CF@akikoz.net> <Pine.LNX.4.58.0505241736010.24188@boston.eecs.umich.edu> <1D91709F-1E4D-4B98-95F5-695F7BD65577@akikoz.net> <Pine.LNX.4.58.0505242049410.3527@boston.eecs.umich.edu> <F016112F-BF6B-4D4E-8A3C-1F38AB3DDC5F@akikoz.net> <Pine.LNX.4.58.0505251303210.3527@boston.eecs.umich.edu> <D20ACE19-9F36-432F-9C52-9D059659BEAA@akikoz.net>
- Sender: owner-wri-mathgroup at wolfram.com
Well, it's for a theorem in my phd thesis about the efficacy of a game theory approximation technique in a class of simple auction games. To open this up to non-Mathematica folks, here's the function (the derivative of the original function I posted) in a platform-neutral format: http://ai.eecs.umich.edu/people/dreeves/f.txt Again, the goal is to show that that expression is negative in (0,(n-1)/n) for all integers n>=2. One way to show that is to show that the expression has at most 2 roots and show that it is zero at x = (n-1)/n and at x = -(n+1)^2/(n*(n-1)). (It is.) I'm looking at Faugere's Fgb program now. Really appreciate that tip, Andrzej! Pre-prizes are on the way for you and DanL... --- \/ FROM Andrzej Kozlowski AT 05.05.26 14:36 (Today) \/ --- > It seems to me that if you really want to maximize the chances of > this problem being solved you should do two things. First, you should > let everyone know why you want it solved: if people think it is > something sufficiently important they will be more keen to spend time > trying to solve it. Second, you should try to popularize it outside > the Mathematica community. There are free equation solvers used for > research purposes much more powerful than Mathematica and there are > researchers who develop them, like Jean-Charles Faugere, who can > solve anything that can be solved by human being or machine. > Even then I doubt this will ever get solved, but you will have a > fighting chance. > > Andrzej > > > On 26 May 2005, at 02:20, Daniel Reeves wrote: > > > > > yikes. ok, let's assume that all works. So it remains to show > > that both > > of the following expressions of n are zero for all n >= 2. Strangely, > > FullSimplify can do this for all specific n up to 113 but 114 seems to > > stump it. > > > > here are the expressions: > > [...] > > > > --- \/ FROM Andrzej Kozlowski AT 05.05.25 12:42 (Today) \/ --- > > > > > >> On 25 May 2005, at 10:00, Daniel Reeves wrote: > >> > >> > >>> wow, this is huge progress. medium prize, at the least, is > >>> cinched :) > >>> > >>> eager to hear how you establish that the derivative has <= 2 > >>> roots... > >>> > >> > >> First, I only think I could probably prove this, but that does not > >> mean I actually have a rigorous proof. I have a sketch of a possible > >> proof that I will describe, but it may not work. What is worse, even > >> if it is essentially correct, it is probably the easy part of the > >> problem. Checking the two "simple identities" for every integer may > >> turn out to be awfully hard, perhaps as hard as Fermat's Last > >> Theorem? > >> So I don't think that my contribution so far deserves any prize :-( > >> > >> Anyway, this is my idea for a argument proving that D[f[x,n]]==0 has > >> only two roots, for every n. For each complex number n, think of the > >> expression D[f[x,n]] as an element of the field Al of "algebraics" > >> over the complex numbers, that is the algebraic closure of the > >> field C > >> [x] of rational functions in one variable with coefficients in the > >> complex numbers C. This is not just an algebraic object but also a > >> topological space. Each element f[x] of Al can be thought as a > >> function on C given by a radical expression like the one in your > >> problem. We know that for each f[x] there is a polynomial p[x] such > >> that all the roots of f[x]==0 are also roots of p[x]==0. As Daniel > >> Lichtblau pointed out in a recent posting the function > >> First[GroebnerBasis[f[x],x]] gives such a polynomial. I think one > >> can probably make sure that the polynomial is monic, that is, its > >> highest degree term is 1. So consider the mapping f[x]->First > >> [GroebnerBasis[f[x],x]] from the topological space Al to the space of > >> all polynomials in one variable. Now, here comes the point I am most > >> uncertain about: I think this mapping can be made continuous. In > >> other words, if we change our radical expression f[x] only slightly > >> than the corresponding polynomial will only change slightly. In > >> particular, it's degree will not jump. If that is so we are nearly > >> done. We need only to check only one more thing, which is that any > >> expression D[f[x,n],x] can be connected to D[f[x,m],x] by a > >> continuous path. Looking at the monstrous expression it seems to me > >> that it is so, anyway, as long as we keep n>1 . But since we can > >> compute the polynomial for a number of integers n and we know that it > >> has degree 2, it would seem to follow that it must always have > >> degree 2. > >> > >> To really be sure the argument is correct would require very good > >> understanding of what the GrobenerBasis algorithm really does in such > >> situations and I have only a vague understanding. In particular I > >> have never seen anywhere the issue of continuity being discussed, but > >> then I have not looked for it. > >> But one must remember even if we could prove this we could still be > >> almost as far from proving the full statement as we were at the > >> start. > >> > >> Andrzej Kozlowski > >> > >> > >> > >> > >> > >> > >>> > >>> > >>> --- \/ FROM Andrzej Kozlowski AT 05.05.25 09:16 (Tomorrow) \/ > >>> --- > >>> > >>> > >>> > >>>> I am now pretty sure that I could now prove the general result > >>>> provided that I could establish two "simple" facts, which are that: > >>>> > >>>> > >>>> FullSimplify[D[f[x, n], x] /. x -> (n - 1)/n, > >>>> Element[n,Integers] && n > 2] > >>>> > >>>> FullSimplify[D[f[x, n], x] /. > >>>> x -> (-n^2 - 2*n - 1)/((n - 1)*n), > >>>> Element[n,Integers] && n > 2] > >>>> > >>>> are both zero. In other words, I think I can prove (there are some > >>>> details that I would have to check but I am pretty sure they are > >>>> fine) that the derivative can have no more than two roots, so if > >>>> the above are the roots everything is done. But unfortunately after > >>>> 24 hours Matheamtica has not returned any answer to the first of > >>>> the > >>>> above. I have not even tried the second. > >>>> Perhaps a more specialized algebra program for this sort of thing > >>>> might do better? > >>>> > >>>> Andrzej Kozlowski > >>>> > >>>> > >>> > >>> -- > >>> http://ai.eecs.umich.edu/people/dreeves - - google://"Daniel > >>> Reeves" > >>> > >>> "I have enough money to last me the rest of my life, unless I > >>> buy something." -- Jackie Mason > >>> > >>> > >>> > >> > >> > > > > -- > > http://ai.eecs.umich.edu/people/dreeves - - google://"Daniel Reeves" > > > > "Engineers think of their equations as approximating reality. > > Scientists think of reality as approximating their equations. > > Mathematicians don't care." > > > > > -- http://ai.eecs.umich.edu/people/dreeves - - google://"Daniel Reeves" "This case -- and I must be careful not to fall into Spooner's trap here -- concerns a group of warring bankers."
- References:
- Solve or Reduce on a monstrosity of an expresssion (and a prize!)
- From: Daniel Reeves <dreeves@umich.edu>
- Solve or Reduce on a monstrosity of an expresssion (and a prize!)