Feeds:
Posts

## Estimating roots

In lieu of a real blog post, which will have to wait for at least another two weeks, let me offer an estimation exercise: bound, as best you can, the unique positive real root of the polynomial $\displaystyle x^{10000} + x^{100} - 1$.

The intermediate value theorem shows that $x \in (0, 1)$, which was the subject of a recent math.SE question that provided the inspiration for this question. I provide a stronger lower bound on $x$ using elementary inequalities and entirely by hand in an answer to the linked question, although I don’t try to improve the upper bound.

### 9 Responses

1. on February 16, 2012 at 12:57 am | Reply truyen sex

Upper bound comes from derivative: 10000x^9999+100x^99. It is increasing with x, so tangent line at x=1 would be lower then our polynomial. ??

2. on January 19, 2012 at 11:29 pm | Reply Luke G

Another alternative… (I’m not on mathSE so feel free to repost this there)

We have 1 = x^100+x^10000. By AM-GM, x^100+x^10000 >= 2x^5050. So x <= (1/2)^(1/5050) < .99987. You can bound it even better using weighted AM-GM; something like .99972 using 100:1 weighting for x^100 to x^10000. (In fact, with the right weights, you can recover the answer exactly, but to choose the weights you'd have to already know the answer.)

A reasonable lower bound comes from 1=x^100(1+x^9900) = .99939.

• on January 20, 2012 at 8:01 am | Reply Qiaochu Yuan

Nice. I suppose you could alter the weights based on your previous estimates and get an iterative scheme for getting better upper bounds.

3. on January 19, 2012 at 11:55 am | Reply Christian Blatter

I have posted not so bad bounds at the stock exchange site where the problem originally appeared:

http://math.stackexchange.com/questions/88567/prove-that-the-equation-x10000-x100-1-0-has-a-solution-with-0-x/100552#100552

4. on January 3, 2012 at 2:30 pm | Reply Rasmus

5. on December 6, 2011 at 1:22 am | Reply mortid0

Upper bound comes from derivative: 10000x^9999+100x^99. It is increasing with x, so tangent line at x=1 would be lower then our polynomial.
Line equation is y = 10100x + b, where 10100 is value of derivative at 1. As line must go throw point (1,1) then b = -10099. And our tangent line intersects x-axis at 10099/10100.(This is just first iteration of Newton’s method).

Lower bound comes from observation that x^10000+x^100-1 looks like symmetric parabola. So we can find simple function g(x) = ax^100+b that is always greater than our polynomial on (0; 1). Let it go throw points (0; -1) and (1; 1). Than a = 2 and b = -1.
2*x^100 – 1 > x^10000+x^100-1 on (0; 1).

And g(x) crosses x-axis at (1/2)^(1/100).

So root is inside ((1/2)^(1/100); 10099/10100) or (0.993; 0.99991)

Drawing graphics can explain better 🙂

6. on December 5, 2011 at 10:30 pm | Reply bartogian

What counts as elementary? The function at hand is visibly convex, so its graph lies above the graph of any tangent. Taking the tangent at (1,1) gives a start on improving the upper bound. (this is of course just the first approximation in an application of Newton’s algorithm).

• on December 6, 2011 at 4:08 am | Reply Qiaochu Yuan

Elementary is in the eye of the beholder, I suppose. It’s up to you.