# Multivariable function analysis

Sorry if the terms I'm going to use is not professional enough:) This is about the complexity analysis of an algorithm.

Let $\alpha$ be the greatest real root of the polynomial $f(x)=x^n-2x^{n-1}-x^{n-k}-2^k$, in which $k$ is a parameter.

The question is how to choose $k$, $(k=\beta n, 0<\beta<1)$ in order to minimize $\alpha$?

We believe that $g$ exists because to minimize $\alpha$, the term $2^k$ requires a small $k$ while the rest needs a big $k$.

Thank you in advance for any idea.

UPDATE:
We've just updated the recurrence relation, the idea is still the same. $k$ is still a relative value to $n$. Let $k=\beta n$. Then the new recurrence is
$f(x)=x^n-3x^{n-1}+x^{n-2}-x^{n-\beta n}-3^{\beta n}+3^{\beta (n-1)}$ Perhaps we can get more information from this one?

• If you differentiate with respect to $k$ the relation $f(\alpha(k))=0$ and require $\alpha'(k)=0$, you obtain $k=\frac{\ln\frac{\ln\alpha(k)}{\ln2}+n\ln\alpha(k)}{\ln\alpha(k)-\ln 2}$. Don't know if that helps, though, but it may if you have some kind of control on $\alpha$ as the largest root. – Loïc Teyssier Apr 24 '15 at 9:36
• Since you say "polynomial", is $k$ to be an integer $\le n$? By "largest" do you mean largest in absolute value, or greatest real root, or what? – Robert Israel Apr 24 '15 at 22:16
• @RobertIsrael Sorry for the inaccuracy:) $k$ is an integer less than $n$, we may suppose $k=\beta n$ with $0<\beta<1$. By "largest", I mean greatest real root. – Leo Apr 28 '15 at 7:46

Let's write the function as $f(x,k)$.
For $k = 0$, the polynomial $f(x,0) = - 2 x^{n-1} - 1$ has no positive roots. For $k = 1$, $f(x,1) = x^n - 3 x^{n-1} - 2$ has a real root greater than $3$. For $k = 2$, $f(x,2) = x^{n-2} (x^2 - 2 x - 1) - 4 > 0$ if $x \ge 3$ and $n \ge 3$. For $k = n$, $f(x,n) = x^{n-1}(x - 2) - 1 - 2^n > 0$ if $x \ge 3$ and $n \ge 3$. Now $f(x,k)$ is a concave function of $\log_2(k)$ for fixed $x > 1$, so $f(x,k) > 0$ if $x \ge 3$, $n \ge 3$ and $2 \le k \le n$. Thus if $n \ge 3$, the greatest real root of $f(x,k)$ for integers $0 \le k \le n$ occurs at $k=1$.
Since the companion matrix of the polynomial $f(x,k)$ has nonnegative entries, the Perron-Frobenius theorem shows that the greatest real root is also the greatest in absolute value.
If we plot the roots, the picture is rather striking. Here is an animation showing the case $n=100$. For each $k\ge 1$ it appears that we have one positive root (near $x=3$ for $k=1$, decreasing rapidly to near $2$, and finally increasing slightly for $90 < k \le 100$), the other roots almost in a circle centred at $0$, of radius less than the real root, that expands as $k$ increases.