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

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

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

• I suppose that’s not ideal. Fixed.

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

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

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

6. 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. ??