Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Find the lowest degree polynomial that satisfies the following constraints:

i) $F(0)=0$

ii) $F(1)=0$

iii)The maximum of $F$ on the interval $(0,1)$ occurs at point $c$

iv) $F(x)$ is positive on the interval $(0,1)$

The answer seems to depend pretty strongly on $c$. It's not difficult to find solutions for all $c$, but the solutions are not minimal. It seems like the solution involves Chebyshev polynomials, but I'm not familiar with them. Can anyone recommended a link?

share|improve this question
13  
Can you give reasons of asking the question? Your $F(x)=x(1-x)G(x)$, where $G(x)>0$ for $0<x<1$ and $F'(c)=0$. By symmetry we can consider $c\ge1/2$ only. $c=1/2$ corresponds to $G(x)=1$. For $1/2<c<2/3$ you simply take $G(x)=x-c(2-3c)/(1-2c)$, otherwise you have to try $G(x)$ a 2nd degree polynomial... I don't see any obvious appearance of Tschebyscheff. –  Wadim Zudilin Dec 28 '10 at 3:45

2 Answers 2

I'll plunge in here.
Edit: I've now added a proof, using Brownian motion. (Earlier this was only justified heuristically) Further revised Jan 5, 2011, to correct typos/formatting and to promote material from comments.

The $n$th Chebyshev $T$-polynomials $T_n(x) = \cos(n \arccos( x))$ are the unique degree n polynomials that fold the interval $[-1,1]$ exactly over itself $n$ times, taking $1$ to $1$.

When $n$ is even, $T_n(-1) = 1$ as well, so by an affine transformation you can make it satisfy the inequalities of the question: $$f_n(x) = 1 - T(2 x - 1) . $$

Here for example is the plot of $f_{10}$:

alt text

This has a maximum at $c = \cos(\pi/10) / 2 = .975528...$, pretty close to 1. (If a strict maximum is desired, modify the polynomial by adding $\epsilon x$, and change by a linear transformation of the domain so that $f(1)=0$.)

For odd degrees, you can restrict the Chebyshev polynomials to an interval from the first local maximum to 1, and renormalize in a similar way, to get the unique degree $n$ polynomial $V_n(x)$ that folds the unit interval exactly $n-1$ times over itself and has a double root at 0.

One way to know the existence of such a polynomial is this: extend the map of the interval to itself to all of $\mathbb C$ in a way that it is an $n+1$-fold branched cover of $\mathbb C$ (not yet analytic) with the branching pattern corresponds to the desired critical points and critical values. Pull back the complex structure in the range via this map. Using the Riemann mapping theorem, it can be seen that the resulting complex 1-manifold is $\mathbb C$, so you get a polynomial map. By symmetry, the critical points all lie on a straight line, so it can be renormalized as a map from the interval to itself. (This is a special case of more general theories, including Shabat polynomials and dessins d'enfants, as well as the theory of postcritically finite rational maps).

For odd degree $n$, I think $V_n$ probably gives the maximal $c$.

Here's a heuristic argument: One can ask, where are the critical points in $\mathbb C$ for a polynomial that satisfies the given constraints and maximizes $c$. Given the $n-1$ critical points $\{c_i\}$, the derivative of $f$ is up to a constant $\prod x-c_i$. To make the ratio large, we need the ratio of the mean value of the integrand in $[0,c]$ to be small compared to the mean value of - integrand in $[c,1]$: since the integrals add to 0, this ratio is the same as the ratio of arc length. This seems to say that the $c_i$'s want to be close to --- actually, inside--- the interval $[0,c]$. The best way to squeeze them in seems to be to make the interval fold as described.

It's easy to relax from the extreme case. For example, in even degrees, just make an affine change to a larger interval $f_n^{-1}( [1-t, \infty], t \ge 0$; as $t \rightarrow \infty$, $c \rightarrow .5$. For the odd degree examples, add a linear function and renormalize in a similar way.

This is reminiscent of the phenomenon of monotonicity in the theory of iterated real polynomials, but simpler to establish.

Added: a proof, using Brownian Motion

Proof that Chebyshev polynomials are optimal for even degrees

There's a way to formulate the problem as a probability question. If you start a Brownian path from a point near infinity in the plane, it almost surely eventually hits the line segment $J = [0,1]$. The position of $c$ in this line segment is determined by the ratio of the probability that the path first hits $[0,c]$ vs $[c,1]$. (To get the exact function, you can map the complement of the line segment coformally to the complement of a circle; on a circle, hitting measure is proportional to arc length).

Now suppose we have a degree $n$ polymomial $g$, as in the question, scaled so that $g(x)$ with $g([0,1]) = [0,1]$ and $g(0)=g(1) = 0$. As a complex polynomial, it defines a branched cover of $\mathbb C$ over $\mathbb C$. In 2 dimensions, conformal maps preserve the trajectories of Brownian motion: only the time parameter changes. Therefore, Brownian motion on the branched cover of the plane looks exactly like Brownian motion on the plane, but with the extra information of which of the $n$ sheets the trajectory is on at any given time. As the trajectory goes around the various critical values, the sheets are permuted. At any given time, if we just know the position of a Brownian path, the distribution on the sheets is uniform.

Let's denote by $J$ the unit interval $[0,1]$ in the domain (upstairs in the branched cover) and $K$ the same interval $[0,1]$ in the range (downstairs). Thus, $J$ is a union of line segments on sheets above $K$, and furthermore, the two subintervals of $J$, $[0,c]$ and $[c,1]$, both map surjectively to $[0,1]$.

Therefore, the first time the Brownian path downstairs crosses $[0,1]$, it has at least a $1/n$ probability of crossing the $[c,1]$ segment in the branched cover. For the even degree Chebyshev polynomial, as soon as it hits the segment $K$ downstairs it also hits $J$ upstairs, so the probability is exactly $1/n$: therefore, this is optimal. It is the unique optimal example for even degree, since if $g^{-1}(K) \ne J$, there would be a nonzero second chance for paths that hit $g^{-1}(K) \setminus J$ to continue on and still hit $[c,1]$.

The figures below illustrate this. The top figure shows the 6th Chebyshev polynomial, renormalized as above to take $[0,1] \rightarrow [0,1]$. The red interval is $J$, the caterpillar's skin is the inverse image of the circumscribed circle about $K$; also depicted is the inverse image of $\mathbb R$. Brownian motion starting at infinity has an equal probability of arriving in any of the 12 sectors (which each opens out under the map to a halfplane), so the probability of arriving in the leftmost segment is exactly 1/6, with length $(1-\cos(\pi/6))/2 = .0669873\dots$.

alt text

The next figure (below) shows a comparison polynomial (also graphed, futher down) with an order 5 zero at 0 and one other critical point at $c$, mapping with critical value $1$. The same data is shown. When a Brownian path starting from infinity first hits $K$ (downstairs), it has equal probability of hitting any of the 6 segments inside the various curves: one of the two red segments (in $J$), or the vein in one of the four leaves. In the 4/6 probability event that it does not hit $J$, when the Brownian path continues on it has some chance of hitting the top interval, so this probability is strictly greater than $1/6$.

alt text

Proof that Chebyshev polynomials are optimal for odd degree

For the odd degree case, a little more is needed. Since the requirement of the question is that $g(0)=g(1)=0$, there are an even number of sheets above any point of $K$, so at least one sheet is absent in $J \setminus g^{-1}(K)$. Let's suppose first that $g^{-1}(K)$ is connected. In that case, we can use the Riemann mapping theorem to map its complement conformally to the exterior of a unit disk; there is a set of measure at least $2\pi/n$ that does not map to $J$. We can follow Brownian motion by letting it "reflect" whenever it hits this portion of the boundary of the unit disk, and continue on until it hits a part that corresponds to $J$. With this formulation, it's obvious that to minimize the probability that the continuing trajectory hits the sensitive area corresponding to $[c,1]$, we need to minimize its length and put it as far away from the sensitive area as possible. That's exactly what happens for $V_n$: on the circle the extra sheet is antipodal to the sensitive sheet.

A similar argument applies to the disconnected case, although without quite as simple a visual representation. It's easy to establish that any optimal polynomial must have the maximal number of sheets above each point in $K$. The hitting probability for the senstive area for random walks starting at points $z$ is a harmonic function on $\mathbb C \setminus J$, with limit 1 along $[c,1]$ and 0 along $[0,c]$. This harmonic function has no critical points, so if there is a component of $g^{-1}(K)$ not attached to $J$, its mean on this component can be reduced by moving it toward 0, by moving the critical values not on the $K$ toward $0$. Below is a picture for the optimal solution for degree 5. There's a short tail to the caterpillar where the Brownian path gets a second chance, but its far away from the sensitive portion so it has only a small chance to next hit there rather than in $[0,c]$. The interval $[c,1]$ is comparatively short because it is exposed out at the end of the interval, but not as exposed so not as short as in the Chebyshev case.

alt text

The Constants

When $n$ is even, there is a solution for $c$ between $(1−\cos(\pi/n))/2$ and $(1+\cos(\pi/n)/2$. If $n$ is odd, there is a solution for $c$ between $(1−\cos(\pi/n))/(1+\cos(\pi/n))$ and $2 \cos(\pi/n)/(1+\cos(\pi/n))$. Numerically, the low values for $c$ are {2, 0.5}, {3, 0.333333}, {4, 0.146447}, {5, 0.105573}, {6,0.0669873}, {7, 0.0520951}, {8, 0.0380602}, {9, 0.0310912}, {10, 0.0244717}

*End of added proof *

Polynomials with a unique local maximum

For comparison, here are plots of degree $n$ polynomials functions (unique up to a constant) that have an $n-1$-fold root at 0, a critical point at $c$, and take value $0$ at 1. At first I guessed that these might give the optimal $c$, but for them, $c = 1-1/n$, much smaller than for the Chebyshev polynomials. The plots are for $n = 2, 3, \dots, 10$.

alt text

However, these polynomials answer a different question: given c, what is the minimum degree of a polynomial that is 0 at 0 and 1 and has a unique local maximum at c. These polynomials, also discussed by Wadim Zudilin, have that property. For such a polynomial, the same technique as above can be used. For any candidate polynomial f, a Brownian path starting at infinity has a probability of a probability of 1/n to hit the interval [0,c], 1/n probability to hit [1,c], and (n−2)/n to first hit elsewhere on f−1([0,1]). The same proof shows these examples are optimal

share|improve this answer
    
+1. You give sufficiet details for doing the case of $n$ even, and the oddies should need a slight modification of the argument. Without seeing a reason for the OP, there is no motivation to elaborate on the technicalities. This could be done by the author. –  Wadim Zudilin Dec 29 '10 at 3:19
    
That's wonderful! Is there a guess for $c$ in the odd case? –  Wadim Zudilin Dec 29 '10 at 23:06
2  
@Wadim Zudilin: Yes, thanks for asking, I should have put in the values for c. When $n$ is even, there is a solution for $c$ between $(1 - \cos(\pi/n))/2$ and $(1 + \cos(\pi/n)/2$. If $n$ is odd, there is a solution for $c$ between $(1-\cos(\pi/n))/(1+\cos(\pi/n))$. Numerically, the low values for $c$ are {2, 0.5}, {3, 0.333333}, {4, 0.146447}, {5, 0.105573}, {6,0.0669873}, {7, 0.0520951}, {8, 0.0380602}, {9, 0.0310912}, {10, 0.0244717} –  Bill Thurston Dec 29 '10 at 23:57
    
One can also ask, given $c$, what is the minimum degree of a polynomial that is 0 at ${0,1}$ and has a unique local maximum at $c$. The polynomials that appear in the last figure of my answer and were also discussed by Wadim Zudilin have that property. For such a polynomial, the same technique as above can be used. For any candidate polynomial $f$, a Brownian path starting at infinity has a probability of a probability of 1/n to hit the interval $[0,c]$, 1/n probability to hit $[1,c]$, and $(n-2)/n$ to first hit elsewhere on $f^{-1}([0,1])$. The same proof shows these examples are optimal. –  Bill Thurston Jan 1 '11 at 16:51

By replacing $F(x)$ by $F(1-x)$ we may assume that $c\ge1/2$. The problem is to determine a polynomial $G(x)=G_c(x)$ of minimal possible degree, say $n$, such that $G(x)>0$ for $0 < x < 1$ and the derivative of $F(x)=x(1-x)G(x)$ changes sign at $x=c$ and $F(x)\le F(c)$ for $0 \le x \le1$. Clearly, $G_{1/2}(x)\equiv1$ and with a very little work $G_c(x)=x+c(2-3c)/(2c-1)$ for $1/2 < c\le2/3$, so $n=1$. The case $n=2$ produces $$G(x)=x^2+a\biggl(x-\frac{c(3c-2)}{2c-1}\biggr)-\frac{c^2(4c-3)}{2c-1},$$ so for $a \ge 0$ we have $G(x) > G(0)=c^2(3-4c)/(2c-1)$ on $x\in(0,1)$, while the latter expression is non-negative for $2/3 < c\le3/4$. If $a <0$, then either $G(x)$ is not positive for $0 < x < 1$ or $F(x)$ attains its maximum at a different point of the interval $0 < x < 1$. This is however a little bit technical to show. (For example, if we take $a=1-3c$, then for the corresponding polynomial $G(x)$ we indeed have $G(x) > 0$, since $$ G(x)\ge G\biggl(\frac{3c-1}2\biggr)=\frac{(2c+1)(c-1)^2}{4(2c-1)}. $$ But $x=c$ is not the maximum of $F(x)=x(1-x)G(x)$ on the interval.)

If the above pattern remains, then for $n/(n+1) < c \le (n+1)/(n+2)$ the minimal possible degree of the polynomial $G(x)$ seems to be $n$ (so that $\deg F=n+2$), with the corresponding choice $$ G_c(x)=x^n-\frac{c^n((n+2)c-(n+1))}{2c-1}. $$ The limiting case $c=1$ is in favor of this observation: there is no polynomial $F(x)\not\equiv0$ of the assumed form which attains its maximum at $x=1$. So, the expected answer to the original question would be $\deg F=\lceil 1/\min(c,1-c)\rceil$, where $\lceil x\rceil=n$ when $n-1 < x \le n$.

Edit. With the above choice of $G_c(x)$, $F'(x)=0$ on the interval $0 < x < 1$ only at $x=c$. Therefore, this choice results in the estimate $\deg F \le \lceil 1/\min(c,1-c)\rceil$, which is sharp at least for $1/3 \le c \le 2/3$.

Edit 2. Bill's answer gives pretty much evidence for the fact that $1/2 < c < (1+\cos(\pi/n))/2$ gives the estimate $\deg F\le n$ for $n$ even. More remarkably, this is indeed related to the Chebyshev polynomials. The most unpleasant thing is a necessary amount of technical work to be done (but Bill's answer contains all details for such calculations).

share|improve this answer
    
But ... for your n = 2, the polynomial $f_{n+2}$ in my answer below achieves $c = (2 + \sqrt 2)/4 = .853553 > 3/4 $. I'll attempt to put the comparison of the plots in this comment: !Degree 4 renormalized Chebyshev –  Bill Thurston Dec 29 '10 at 1:57
    
I played with choosing $a<0$ (experimentally only) and discovered that $F(x)$ has its maximum at a different point. Your plot suggests that there are 2 maximums, so $F(x)=F(c)$ for some $x\ne c$. Otherwise, please give an explicit example... –  Wadim Zudilin Dec 29 '10 at 2:13
    
The statement of the problem doesn't specifically require that F attain a unique maximum at $c$. But (this is mentioned in my answer) if you do insist that the maximum should be unique, just modify it by a small linear pertubation, i.e. $g_{n, \epsilon}(x) = \epsilon x + f_n((1-\epsilon') x)$, where $\epsilon'$ is chosen to solve $g_{n,\epsilon}(1)=0$. The limit of the $c$'s as $\epsilon \rightarrow 0$ is that for $f_n(x)$, namely $(1 + \cos(\pi/n))/2$. –  Bill Thurston Dec 29 '10 at 4:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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