6
$\begingroup$

For the function $$ f(x)=\sum_{k=0}^{2n}{x^k} $$ I think this function has no zeros, and if ${f(x_0)}$ is the minimum point, then ${x_0\in \left[-1,0 \right] }$.

For $1+x+x^2+x^3+x^4$ and $1+x+x^2$, I can get the minimum by calculating $f'(x)$ and then using the root fomula. But this method doesn't work for $n\geqslant 3$ since there is no root fomula for equations higher than the fifth degree.

I have no idea for the situation where $n\geqslant 3$, so any advice could be helpful

$\endgroup$
12
  • $\begingroup$ A potentially useful fact: f(x)=(2 n+1) Hypergeometric2F1[1,-2 n,2,1-x]. In this forms derivatives are easy to evaluate. $\endgroup$ Mar 13 at 20:55
  • $\begingroup$ @AaronHendrickson I am a freshman thus I know little about the Hypergeometric function. I am still learning it on wiki. Can you just show me the result or the step. $\endgroup$ Mar 13 at 23:52
  • $\begingroup$ @AaronHendrickson. Could you eleborate ? $\endgroup$ Mar 17 at 4:58
  • $\begingroup$ @AaronHendrickson Could you explain how you find derivatives because I think f(x)=(2 n+1) Hypergeometric2F1[1,-2 n,2,1-x] is same as (x^(2n+1)-1)/(x-1), thus changing the form cannot simplify it. $\endgroup$ Mar 17 at 12:38
  • 1
    $\begingroup$ More funny stuff in the update ! $\endgroup$ Mar 17 at 13:53
10
$\begingroup$

@ClaudeLeibovici and I had a lot of fun with this one. The link to the arXiv article below provides a derivation of the minimum of this polynomial for any $n\in\Bbb N$.

Exact and approximate solutions to the minimum of $1+x+\cdots+x^{2n}$


Summary of paper:

To find the minimum of this polynomial, denoted $f_{2n}(x)$, we first derived the relationship $$ \inf_x f_{2n}(x)=\frac{1+2n}{1+2n(1-x_{2n})}, $$ with $x_{2n}$ being the argument of the minimum. It was then shown that $x_{2n}$ satisfies $$ x_{2n}^{2n}\left(1-x_{2n}+\tfrac{1}{2n}\right)-\tfrac{1}{2n}=0, $$ and an exact solution of this equation was subsequently found via Lagrange inversion. For the purposes of numerical computation we also derived a faster converging perturbation series for $x_{2n}$.

$\endgroup$
11
  • $\begingroup$ Great thanks. Not offensive, so, in general, how can we judge that one problem/equation have a closed-form solution. Is there any kind of features to hint us to use numerical method? I mean that if there doesn't exist a closed-form solution, it will be wasting time to find it. $\endgroup$ Mar 18 at 0:55
  • $\begingroup$ Interesting, for sure. I thought at a time about things similar but I bumped in the problem : "where to place $\epsilon$ ?" that you solved. $\endgroup$ Mar 18 at 11:25
  • $\begingroup$ This is beautiful solution, for sure. $\endgroup$ Mar 19 at 3:48
  • $\begingroup$ More I read your answer $\implies$ more I am impressed ! $\endgroup$ Mar 19 at 10:12
  • $\begingroup$ @Claude Leibovici Wow. Seriously? That's a huge complement. Thank you Claude! I have never used perturbation series before and thought they were really fascinating. I was hoping it would reveal some sort of pattern in the coefficients. There may be one, I just couldn't see it. $\endgroup$ Mar 19 at 11:31
7
$\begingroup$

It seems possible to generate an estimate of the value of $x$ where the function $$f(x)=\sum_{k=0}^{2n}{x^k}=\frac{x^{2 n+1}-1}{x-1}$$ is minimum. As shown in other answers, the problem is to approximate the zero of function $$g(x)=2nx^{2n+1}-(2n+1)x^{2n}+1$$ This have been done using the first iteration of an high order iterative method starting with $x=-1$ as an initial guess. The result is given by $$x_0=-\frac{256 n^6+10240 n^5+75296 n^4+212560 n^3+273764 n^2+159400 n+33199}{2 (2 n+3) \left(64 n^5+2688 n^4+20224 n^3+53604 n^2+56320 n+20001\right)}$$

Now, one single interation of Newton method is supposed to sufficiently polish the solution (it would not be any problem to use Halley or Householder methods in place of Newton).

Below are reported some results ($x_1$ by Newton). $$\left( \begin{array}{cccc} n & x_0 & x_1 & \text{solution} \\ 1 & -0.500137 & -0.500000 & -0.500000 \\ 2 & -0.605614 & -0.605830 & -0.605830 \\ 3 & -0.669716 & -0.670334 & -0.670332 \\ 4 & -0.713566 & -0.714543 & -0.714538 \\ 5 & -0.745773 & -0.747064 & -0.747054 \\ 6 & -0.770592 & -0.772160 & -0.772142 \\ 7 & -0.790396 & -0.792205 & -0.792178 \\ 8 & -0.806624 & -0.808643 & -0.808605 \\ 9 & -0.820203 & -0.822403 & -0.822353 \\ 10 & -0.831760 & -0.834116 & -0.834053 \\ 11 & -0.841736 & -0.844223 & -0.844148 \\ 12 & -0.850449 & -0.853047 & -0.852958 \\ 13 & -0.858136 & -0.860826 & -0.860724 \\ 14 & -0.864977 & -0.867742 & -0.867627 \\ 15 & -0.871111 & -0.873936 & -0.873809 \\ 16 & -0.876648 & -0.879520 & -0.879381 \\ 17 & -0.881675 & -0.884583 & -0.884433 \\ 18 & -0.886264 & -0.889197 & -0.889037 \\ 19 & -0.890473 & -0.893421 & -0.893252 \\ 20 & -0.894349 & -0.897304 & -0.897127 \\ 21 & -0.897932 & -0.900888 & -0.900703 \\ 22 & -0.901257 & -0.904206 & -0.904015 \\ 23 & -0.904351 & -0.907289 & -0.907091 \\ 24 & -0.907239 & -0.910161 & -0.909958 \\ 25 & -0.909942 & -0.912843 & -0.912636 \end{array} \right)$$

It is possible to do better for $x_0$ at the price of an higher order method.

Edit

For the fun of it, I used the same procedure with two more orders. The result write, just as before, $$x_0=-\frac{\sum_{k=0}^8 a_k\,n^k}{\sum_{k=0}^8 b_k\,n^k}$$ and the coefficients are $$\left( \begin{array}{ccc} k & a_k & b_k \\ 0 & 2300106 & 8278851 \\ 1 & 13284828 & 37098288 \\ 2 & 30007592 & 67149620 \\ 3 & 34417264 & 63318640 \\ 4 & 21546112 & 33284272 \\ 5 & 7272832 & 9611392 \\ 6 & 1199488 & 1382080 \\ 7 & 73216 & 75520 \\ 8 & 512 & 512 \end{array} \right)$$

Just to give an idea, for $n=25$ this produces for $x_0$ a value of $-0.912088$.

Update

Up to now, we just focused on the value of $x$ for which $f(x)$ is minimum. What is interesting if that when $f'(x_0)=0$ by elimination we have the simple $$f(x_0)=\frac{2 n+1}{1+2 n(1-x_0)}$$

Using the last set of coefficients given in the edit, we have $$\left( \begin{array}{ccccc} n & f_{\text{min}}^{\text{est}} & f_{\text{min}}^{\text{calc}} & x_0^{\text{calc}}& x_0^{\text{est}}\\ 1 & 0.749996 & 0.750000& -0.500000 & -0.500011 \\ 2 & 0.673570 & 0.673553& -0.605830 & -0.605782 \\ 3 & 0.635115 & 0.635094& -0.670332 & -0.670271 \\ 4 & 0.611584 & 0.611567& -0.714538 & -0.714486 \\ 5 & 0.595555 & 0.595543& -0.747054 & -0.747017 \\ 6 & 0.583866 & 0.583858& -0.772142 & -0.772117 \\ 7 & 0.574928 & 0.574922& -0.792178 & -0.792159 \\ 8 & 0.567852 & 0.567846& -0.808605 & -0.808586 \\ 9 & 0.562099 & 0.562091& -0.822353 & -0.822327 \\ 10 & 0.557321 & 0.557309& -0.834053 & -0.834013 \\ 11 & 0.553284 & 0.553267& -0.844148 & -0.844089 \\ 12 & 0.549825 & 0.549801& -0.852958 & -0.852876 \\ 13 & 0.546825 & 0.546793& -0.860724 & -0.860614 \\ 14 & 0.544196 & 0.544156& -0.867627 & -0.867487 \\ 15 & 0.541872 & 0.541823& -0.873809 & -0.873636 \\ 16 & 0.539802 & 0.539743& -0.879381 & -0.879173 \\ 17 & 0.537945 & 0.537876& -0.884433 & -0.884189 \\ 18 & 0.536269 & 0.536190& -0.889037 & -0.888755 \\ 19 & 0.534749 & 0.534660& -0.893252 & -0.892932 \\ 20 & 0.533363 & 0.533263& -0.897127 & -0.896769 \\ 21 & 0.532094 & 0.531984& -0.900703 & -0.900306 \\ 22 & 0.530926 & 0.530807& -0.904015 & -0.903580 \\ 23 & 0.529850 & 0.529719& -0.907091 & -0.906618 \\ 24 & 0.528852 & 0.528712& -0.909958 & -0.909447 \\ 25 & 0.527926 & 0.527777& -0.912636 & -0.912088 \end{array} \right)$$

Update

After this question (which looks quite similar), I thought that it could be interesting to look for the zero of function $$h(x)=\log \left((2 n+1) x^{2 n}-2 n x^{2 n+1}\right)$$ Expanding it as a series around $x=-1$ and using series reversion, we end with $$x=-1+z+\sum_{k=2}^\infty (-1)^{k+1}\frac {P_k(n) } { 2^{k-1}\, k! \,(4 n+1)^{k-1} }\,z^k$$ with $$z=\frac{(4 n+1) \log (4 n+1)}{4 n (2 n+1)}$$ The first $P_k(n)$ are $$\left( \begin{array}{cc} 2 & 8 n+1 \\ 3 & 64 n^2+8 n-1 \\ 4 & 512 n^3+32 n^2-24 n-1 \\ 5 & 4096 n^4+256 n^3+32 n^2+104 n+13 \end{array} \right)$$

$\endgroup$
8
  • $\begingroup$ Thank you for your efforts on numerical methods. I used computer program to calculate in your way and find out the zeros. Furthermore, I am interested in whether there exists a closed-form expression of an analytic expression. One commenter recommended me to use f(x)=(2 n+1) Hypergeometric2F1[1,-2 n,2,1-x], but it seems difficult. $\endgroup$ Mar 16 at 20:40
  • 2
    $\begingroup$ @SaltedFishKing. I do not see how rewrite $f(x)$ as the hypergeometric function could be of any help for the computation of any derivative. Do not dream too much about a closed form solution. $\endgroup$ Mar 17 at 5:52
  • $\begingroup$ Anyway, thanks. I think that f(x)=(2 n+1) Hypergeometric2F1[1,-2 n,2,1-x] is just same as (x^(2n+1)-1)/(x-1). $\endgroup$ Mar 17 at 12:37
  • 1
    $\begingroup$ @SaltedFishKing. For sure, it is ! This is why I asked AaronHendrickson to elaborate. $\endgroup$ Mar 17 at 12:41
  • $\begingroup$ It is true that $f(x)=\sum_{k=0}^{2n}x^k=(2n+1) {_2F}_1(1,-2n,2,1-x)$ which can be derived by expanding $1-x^{2n+1}=1-(1-(1-x))^{2n+1}$ with binomial theorem and then using hypergeometric series to compare. As per my comment above, I thought it was going to be helpful but it didn't accomplish much. $\endgroup$ Mar 17 at 17:28
6
$\begingroup$

Yes, it has no zeros, because $f(1)=2n+1\ne0$ and because, if $x\ne1$, $f(x)=\frac{x^{2n+1}-1}{x-1}$, which is never equal to $0$.

However, it is not true that the minimum is attained at some of $[0,1]$. For instance, of $n=2$, the the minimum is attained at about $-0.606$.

$\endgroup$
1
  • $\begingroup$ Thanks, I made a mistake when determining the interval of x, it should be -1 to 0, and I will change it. $\endgroup$ Mar 13 at 23:40
3
$\begingroup$

We can establish the minimum $x_0\in(-1,0)$ without explicitly finding it. This can be done by first re-writing, $$f(x)=\frac{x^{2n+1}-1}{x-1}$$ and then differentiating, $$f'(x)=\frac{2nx^{2n+1}-(2n+1)x^{2n}+1}{(x-1)^2}$$ Descarte's Rule of Signs reveals that $f'(x)$ has only one negative real root, call it $\alpha$. In particular, we see that $f'(-1)=-n$ and $f'(0)=1$, so we know $\alpha\in(-1,0)$, thus we know that $f(x)$ is decreasing (negative derivative) from $(-\infty,\alpha)$ and is increasing (positive derivative) from $(\alpha,0)$. Thus, since $f(x)>1$ for $x>0$ and $f(0)=1$ and $f(-1)=0$, then we are assured that $f(\alpha)<0$ and will be the absolute minimum of the whole function $f(x)$.


Finding $\alpha$ will most likely be done with an approximation (instead of closed form). There are a number of ways to approximate $\alpha$. One particularly straight forward approach, is to half the intervals testing if you are positive or negative at each step using the derivative. Since you know $\alpha\in[-1,0]$ this method will reach a really good approximation very quickly.

$\endgroup$
2
  • $\begingroup$ It seems that we could have almost the solution. Cheers :-) $\endgroup$ Mar 16 at 10:12
  • $\begingroup$ @Claude Leibovici The OP indicated that they believed the minimum was a root of the derivative found in $[-1,0]$. I guess I was under the impression that the OP wanted to know if that statement is true and how we know that this statement is true for $n\ge 3$. $\endgroup$ Mar 17 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.