Re: Solve or Reduce on a monstrosity of an expresssion (and a prize!)
- To: mathgroup at smc.vnet.net
- Subject: [mg57420] 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:08 -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> <4294C165.8040406@wolfram.com>
- Sender: owner-wri-mathgroup at wolfram.com
I'm taking a few parts on faith (I guess technically we all are given the
computer-assisted nature of this proof!) but it sounds like you and
Andrzej have similar ideas about establishing at most 2 roots. I don't
know what you have in mind though for how to establish "sufficiently many"
values of n. n=2,3,4,5,6, and 7 all work but for n=8, GroebnerBasis does
not include a degree 2 polynomial. (Still, FindInstance confirms no roots
in (0,(n-1)/n) for n=8, and in fact does so all the way up to 684.)
--- \/ FROM Daniel Lichtblau AT 05.05.25 13:18 (Today) \/ ---
> 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:
> > [...]
>
>
> I can point out some aspects to a probabilistic argument. Making it into
> a full fledged proof would require figuring out some bounds that offhand
> I don't know how to do, then verifying for appropriately many cases.
>
> First you need to show that there are 2 roots for each x, at least when
> n>=2. For this it suffices to show it holds for generic n. Since we
> cannot seem to do that computationally, instead do it for "random" n.
> Calling your expression fp, do, say,
>
> fp7 = Simplify[fp /. n->7]
> gb7 = GroebnerBasis[fp7,x]
>
> Now check for a quadratic polynomial (in x) in gb7. If you find one,
> that means there are at most 2 solutions when n=7. This can of course be
> repeated for other values of n. The point is that, for integers larger
> than 2, this computation appears to be feasible. Offhand I think this
> idea (of verifying at sufficiently many values of n) suffices, though
> there may be a lurking branch cut issue. Note that showing there are two
> solutions for n=7 is not quite sufficient in and of itself because 7
> might not be generic. In this setting, nongeneric points would lie on a
> variety (roots of a polynomial), hence be a set of measure zero.
>
> Verification that x->(n-1)/n and x->-(n+1)^2/(n*(n-1)) are the two
> solutions can be done by making the substitutions into fp and verifying,
> for sufficiently many n>=2, that these vanish. The reason is that
> univariate algebraic functions vanishing at sufficiently many integer
> points vanish everywhere that branches don't change (e.g. x-Sqrt[x^2]
> vanishes on positive integers and indeed on all positive reals). I think
> the branch cut issue goes away when you have the proviso that n>=2,
> because for the substitutions above all radicands are positive in that
> region. But maybe I'm missing something and there is more to it than this.
>
> I should mention that if you did not know those were the appropriate
> substitutions, they might be deduced by finding particular {x,n} pairs
> and getting more values via homotopy continuation (basically, setting up
> and solving an ODE via NDSolve). Values from this could then be used to
> interpolate an implicit relation. This was the gist of some work I
> described in a note last week:
>
> http://forums.wolfram.com/mathgroup/archive/2005/May/msg00627.html
>
> Offhand I do not know how well it would work for your particular
> algebraic expression, but it strikes me as a plausible approach. (A
> better one for this case might be to take an implicit plot of the zero
> set of fp and guess the relation).
>
>
> Daniel Lichtblau
> Wolfram Research
>
--
http://ai.eecs.umich.edu/people/dreeves - - google://"Daniel Reeves"
"To me, boxing is like a ballet, except there's no music, no
choreography, and the dancers hit each other."
-- Jack Handy, Deep Thoughts
- 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!)