Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

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

Search the Archive

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."


  • Prev by Date: Re: Solve or Reduce on a monstrosity of an expresssion (and a prize!)
  • Next by Date: Limit of list
  • Previous by thread: Re: Solve or Reduce on a monstrosity of an expresssion (and a prize!)
  • Next by thread: Re: Solve or Reduce on a monstrosity of an expresssion (and a prize!)