# Rolle's theorem in n dimensions

This looks like a statement from a calculus textbook, which perhaps it should be.

"Rolle's theorem". Let $F\colon [a,b]\to\mathbb R^n$ be a continuous function such that F(a)=F(b) and F'(t) exists for all $a<t<b$. Then there exist numbers $a < t_1 < t_2 < \dots < t_n < b$ such that the vectors $F'(t_1),\dots,F'(t_{n})$ are linearly dependent.

We are all familiar with the case n=1. The case n=2 is not hard either: pick any $a<t^\ast<b$ and find, using the mean value theorem, numbers $a<t_1<t^\ast$ and $t^*<t_2<b$ such that $F'(t_j)$ is collinear with $F(t^\ast)-F(a)$. Note that we avoided using the parameter value $t^\ast$, which will be important in a moment. When n=3, we pick $a<t^\ast<b$ and project F onto the orthogonal complement of $F'(t^\ast)$, then apply the case n=2 to the projection ($t^\ast$ will become the third chosen parameter value). So far so good.

But I get stuck at n=4. If the above process is followed, then after F is projected down to two dimensions, we must avoid two particular parameter values. Which is not possible in general: if in two dimensions F parametrizes a triangle and F(a) is a vertex, then one of points $F(t_j)$ must be one of two other vertices. Presumably this problem can avoided by a generic choice of points of projection, but how?

-
Harry, your link is to the case when the domain is R^n, not the range. They mention an inequality that does extend to higher dimensional ranges, but they don't appear to address Leonid's question. –  Jonas Meyer Jan 1 '10 at 22:32
@Harry: so you are using the method of proof by irrelevance? :P –  Mariano Suárez-Alvarez Jan 1 '10 at 22:42
Mariano, isn't that the best kind of proof? ;) I deleted my comments to make room for the other comments, but in summary, I posted a link to a proof of the MVT for R^n, but it was irrelevant. –  Harry Gindi Jan 1 '10 at 23:43
I think I can solve the original problem for even $n$. Interested? –  darij grinberg Jan 1 '10 at 23:46
Okay, as long as my solution below stays incomplete, I'm giving the fix for even $n$: Read my reply until (4), and notice that, whenever $\left(t_1,t_2,...,t_n\right)$ is an $n$-tuple of points in counterclockwise position, then so is $\left(t_n,t_1,t_2,...,t_{n-1}\right)$, so (4) yields that the reals $\det\left(F^{\prime}\left(t_1\right),F^{\prime}\left(t_2\right),...,F^{\prime}\‌​left(t_n\right)\right)$ and $\det\left(F^{\prime}\left(t_n\right),F^{\prime}\left(t_1\right),F^{\prime}\left‌​(t_2\right),...,F^{\prime}\left(t_{n-1}\right)\right)$ have the same sign, which is absurd. –  darij grinberg Jan 2 '10 at 0:43

Here is a solution in the $C^1$ case [but see upd]. Suppose the vectors $F'(t_1),\ldots, F'(t_n)$ are linearly independent for all $0\leq t_1< \cdots < t_n\leq 1$. Let $L(t_1,\ldots,t_{n-1})$ be vector space spanned by the first $n-1$ of these. Let $$t^i=(t_1^i,\ldots,t_{n-1}^i),0\leq t^i_1< \cdots < t^i_{n-1}\leq 1$$ be a sequence such that $t^i_{n-1}\to 0$ as $i\to \infty$. Since the space of all vector hyperplanes in $\mathbf{R}^n$ is compact, we can assume the sequence $L(t^i)$ has a limit $L$.

Claim: for any $s,t$ such that $0< s < t\leq 1$ the hyperplane $L$ does not separate $F'(s)$ and $F'(t)$.

Proof of the claim: if $L$ does, then for all sufficiently large $i$ the hyperplane $L(t^i)$ also separates $F'(s)$ and $F'(t)$. Choose $i$ so that moreover $t^i_{n-1} < s$. Then the determinants of the matrices $(F'(t^i_1),\ldots, F'(t^i_{n-1}),F'(s))$ and $(F'(t^i_1),\ldots, F'(t^i_{n-1}),F'(t))$ have different signs. This is impossible, since $F'$ is continuous and the determinant is never zero. Claim is proven.

Now one of the two things can happen: either all $F'(t),0 \leq t\leq 1$ are in $L$, in which case $F'(t_1),\ldots, F'(t_n)$ are linearly dependent for all $t_1,\ldots, t_n$, or there is a $t$ such that for $l(F'(t))\neq 0$ where $l$ is a linear equation defining $L$. Say, $l(F'(t)) > 0$. Then $l(F(0)) < l(F(1))$, so we can't have $F(0)=F(1)$.

upd: here is how one can take care of the case when $F'$ is not assumed continuous. Basically, the only thing that changes is the proof of the claim; the claim itself remains the same except that we assume $t < 1$. Choose $i$ as above and set $g(x),s\leq x\leq t$ to be the determinant of $(F'(t^i_1),\ldots,F'(t^i_{n-1}),F(x))$. This function is differentiable and we have $g'(x)=det(F'(t^i_1),\ldots,F'(t^i_{n-1}),F'(x))$. So $g'(s)$ and $g'(t)$ have different signs. The claim follows now from the following statement, which is a consequence of the classical Rolle's theorem: if $f:[a,b]\to\mathbf{R}$ is differentiable at each point of $[a,b]$ and $f'(a)$ and $f'(b)$ have different signs, then there is an $x\in (a,b)$ such that $f'(x)=0$.

Then we deduce from the claim that all $F'(t),0 < t < 1$ are in the same half-space with respect to $L$. This suffices.

-
This is a nice proof. Does L agree with something like an osculating hyperplane (from the right, perhaps?) to the curve at t=0? –  j.c. Jan 2 '10 at 2:22
jc -- $L$ is the osculating plane, that is, if enough derivatives exist and are linearly independent. –  algori Jan 2 '10 at 2:49

It is more natural to ask $0\in\mathop{Conv}\{f'(t_i)\}$.

Clearly $0\in\mathop{Conv}f'([a,b])$, thus from Carathéodory's theorem we get $n+1$ points. Further, we can remove two points and exchange them to one. The later follows easeely if $f'$ is continuous, otherwise it is a bit of work...

-
Your wonderful 1-paragraph explanation is equivalent to, but so much cleaner and concise than our effort, I must say wow! –  Ilya Nikokoshev Jan 2 '10 at 2:07
That's really slick! –  David Speyer Jan 2 '10 at 2:32
I don´t understand why $0$ is in the convex hull of $f'([a,b])$. The function could very well be linear and non-constant... –  Mariano Suárez-Alvarez Jan 2 '10 at 13:09
@Mariano: The function was assumed to have the same value at both end points. –  Harald Hanche-Olsen Jan 2 '10 at 14:27

Let's add a bit of Anton Petrunin's answer into algori's: namely, I'm going to spell out the 'little bit of work' from Anton's answer, which is a version of algori's Claim. I am not proving the stronger statement made by Anton though, only the original statement. (This was supposed to be a comment: my attempt to write algori's proof without taking limits, but it turned out to be too long for comments.)

Claim 1 (Petrunin): $0\in Conv(f'(a,b))$.

Proof: Otherwise there is a hyperplane separating $0$ from the convex hull.

By Caratheodory's Theorem, we get $$a < t_1 < \dots < t_{n+1} < b$$ such that $$0\in Conv(f'(t_1),\dots,f'(t_{n+1}).$$

Claim 2 (algori): There is $s\in[t_n,t_{n+1}]$ such that $$0\in Span(f'(t_1),\dots,f'(t_{n-1}),f'(s)).$$

Proof: Set $$l(x)=\det(f'(t_1),\dots,f'(t_n),f(x)).$$ The condition on $s$ is that $l'(s)=0$. By Claim 1, either $$0\in Conv(f'(t_1),\dots,f'(t_{n-1}))$$ (in which case the claim is obvious) or $0$ lies between $l'(t_n)$ and $l'(t_{n-1})$. In the latter case, such $s$ exists by the usual Rolle's theorem.

-

This is the corrected proof of the satement in the case when $F'$ is supposed to be continuous. We also assume that $F'$ never vanishes, othevise the statement is obviuous. The first four comments below are about previous versions of my proof, which were not correct. So first 4 comments are not relevant anymore to this answer (really sorry for that).

I will use slightly modified reasoning of Ilya (please read his answer. His idea is that we conisder the curve $\frac{F'}{|F'|}$ in the unit $S^{n-1}$). Then we need to prove a little lemma.

Lemma. Consider a continous curve $C$ on a sphere $S^{n-1}$ that doesn't lie inside any half-sphere parametrised by an inteval $[0,1]$. Prove that there exists an equator that intersects the curve for at least $n$ different values of the parameter.

Proof. The center of the sphere belongs to the convex hull of $C$ by the assumption of the lemma. This means that there are $n+1$ or less points on $C$ such that the simplex with vertices in these points contains the centre $0$ of the sphere. If the number of points is less than $n+1$, we are done. Suppose that the number of points is in fact $n+1$ and they are linearly inependent. We call the points $x(t_1),...,x(t_{n+1})$ where $t_i$ are odered for. Consider now the hyperplane $H$ generated by points $x(t_1),...,x(t_{n-1})$ and the center of the sphere. $H$ cuts $S^{n-1}$ in two halves. Since by constructions the convex hull of $x(t_i)$ contains $0$, the points $x(t_n), x(t_{n+1})$ are in different half spaces with respect to the plane. So this plane intersects the part of curve C contained between $t_n$, $t_{n+1}$ in some point $x(t_n')$. The lemma is proved.

-
@Dmitri, The simplex you're talking about will have $n+1$ vertices, while the problem is to show that there is a simplex with $n$ vertices. –  Ilya Nikokoshev Jan 1 '10 at 23:47
I don't understand what you are proving here. Can you explain say in the case n=2? Also where are you using the derivative of F? –  Reid Barton Jan 1 '10 at 23:48
Please, before it's too late, just return back your old text and post a new answer with the new text! Otherwise, people will not understand what the comments refer to! –  Ilya Nikokoshev Jan 2 '10 at 1:39
No - he is considering the arc of $C$ which doesn't contain these points. I think this is why he says that the $t_i$ should be ordered. –  darij grinberg Jan 2 '10 at 1:46
The same argument works without continuity, instead you use that $f'(x)$ belongs to closure of $Conv f'([x,y]$. –  Anton Petrunin Jan 2 '10 at 2:08

I've never seen such an interesting analysis problem :) Here is my current state, which I post because I like this form in itself and because I hope somebody finishes it.

We can reformulate what we want to prove as follows, by taking the direction of $F'(t)$:

Consider a smooth curve on a sphere $S^{n-1}$ that doesn't lie inside any half-sphere. Prove that there exists an equator that intersects the curve in at least $n$ points.

(Note that an there is $n-1$-dimensional family of equators.)

Now suppose there were a contradictory curve. I'm currently thinking about shrinking it: if we can do it keeping the offending properties (using that there are no $n$-intersecting equators) then we'll arrive to contradiction since once the curve is small it's definitely inside half-circle.

-
Ilya, I corrected my previous post. This is uses the same idea as yours. I think, this time I prove your lemma. So it gives the proof of the statement if we suppose $F'$ is continuous. –  Dmitri Jan 2 '10 at 1:37

EDIT: The following solution is incomplete. We need to make sure that if $F^{\prime}\left(t\right)$, $F^{\prime\prime}\left(t\right)$, ..., $F^{\left(n-1\right)}\left(t\right)$ are linearly dependent vectors for every $t$, then the coordinate functions of $F^{\prime}$ are linearly dependent on a sufficiently small interval. This follows from Wronskian considerations if the coordinate functions of $F^{\prime}$ are sufficiently nice (i. e., locally real-analytic), so this solves the problem for this nice class of functions, but I can't use this ansatz further.

"SOLUTION".

IMPORTANT: I consider $F$ to be a map from $S^1$ to $\mathbb R^n$, because a map from an interval with equal values at the ends is the same as a map from the circle. I will assume continuity of $F^{\prime}$ (yes, this includes the two endpoints of the interval which I have glued together). So I don't claim I have 100% solved the original problem.

I will say that an $n$-tuple of distinct points $\left(t_1,t_2,...,t_n\right)\in \left(S^1\right)^n$ is in counterclockwise position if there is an orientation-preserving map $\Phi:S^1\to \left[0,1\right]$, continuous except at one point, such that $\Phi\left(t_1\right)<\Phi\left(t_2\right)<...<\Phi\left(t_n\right)$. I need the following intuitively obvious fact:

(1) If an $n$-tuple of distinct points $\left(t_1,t_2,...,t_n\right)\in \left(S^1\right)^n$ is in counterclockwise position, and an $n$-tuple of distinct points $\left(s_1,s_2,...,s_n\right)\in \left(S^1\right)^n$ is in counterclockwise position as well, then there exists a smooth way to move the points $t_1$, $t_2$, ..., $t_n$ along $S^1$ such that they occupy the places of $s_1$, $s_2$, ..., $s_n$ at the end, and such that they stay distinct at any time during the process.

I could formalize this if anyone asks me to.

As a consequence of (1) and the intermediate value theorem (the usual one, for functions $\mathbb R\to \mathbb R$), we have:

(2) If an $n$-tuple of distinct points $\left(t_1,t_2,...,t_n\right)\in \left(S^1\right)^n$ is in counterclockwise position, and an $n$-tuple of distinct points $\left(s_1,s_2,...,s_n\right)\in \left(S^1\right)^n$ is in counterclockwise position as well, and $R:\left(S^1\right)^n\to \mathbb R$ is a continuous map that never takes the value $0$ on $n$-tuples of distinct points, then the reals $R\left(t_1,t_2,...,t_n\right)$ and $R\left(s_1,s_2,...,s_n\right)$ have the same sign.

In other words,

(3) If $R:\left(S^1\right)^n\to \mathbb R$ is a continuous map that never takes the value $0$ on $n$-tuples of distinct points, then for any $n$-tuple of distinct points $\left(t_1,t_2,...,t_n\right)\in \left(S^1\right)^n$ in counterclockwise position, the real $R\left(t_1,t_2,...,t_n\right)$ has the same sign.

Now, let's solve the problem: Assume that the assertion is wrong, and thus $F^{\prime}\left(t_1\right)$, $F^{\prime}\left(t_2\right)$, ..., $F^{\prime}\left(t_n\right)$ are linearly independent for any $n$-tuple of distinct points $\left(t_1,t_2,...,t_n\right)\in \left(S^1\right)^n$. Then, applying (3) to the continuous map

$R:\left(S^1\right)^n\to \mathbb R,$ $\left(t_1,t_2,...,t_n\right)\mapsto \det\left(F^{\prime}\left(t_1\right),F^{\prime}\left(t_2\right),...,F^{\prime}\left(t_n\right)\right)$,

we obtain that:

(4) For any $n$-tuple of distinct points $\left(t_1,t_2,...,t_n\right)\in \left(S^1\right)^n$ in counterclockwise position, the real $\det\left(F^{\prime}\left(t_1\right),F^{\prime}\left(t_2\right),...,F^{\prime}\left(t_n\right)\right)$ has the same sign.

Let's WLOG say that it is positive all the time (if its negative, just rewrite the proof with negative instead of positive...), i. e. we have:

(5) For any $n$-tuple of distinct points $\left(t_1,t_2,...,t_n\right)\in \left(S^1\right)^n$ in counterclockwise position, the real $\det\left(F^{\prime}\left(t_1\right),F^{\prime}\left(t_2\right),...,F^{\prime}\left(t_n\right)\right)$ is positive.

Now, move $t_2$, $t_3$, ..., $t_{n-1}$ (not $t_n$) closer and closer to $t_1$ (while keeping the counterclockwise position, of course), while keeping $t_1$ and $t_n$ fixed. Then, $\det\left(F^{\prime}\left(t_1\right),F^{\prime}\left(t_2\right),...,F^{\prime}\left(t_n\right)\right)$ tends to $\det\left(F^{\prime}\left(t_1\right),F^{\prime\prime}\left(t_1\right),...,F^{\left(n-1\right)}\left(t_1\right),F^{\prime}\left(t_n\right)\right)$. So, we get:

(5) For any pair of distinct points $\left(t_1,t_n\right)\in \left(S^1\right)^2$ in counterclockwise position, the real $\det\left(F^{\prime}\left(t_1\right),F^{\prime\prime}\left(t_1\right),...,F^{\left(n-1\right)}\left(t_1\right),F^{\prime}\left(t_n\right)\right)$ is nonnegative.

Notice how "positive" became "nonnegative" due to the limiting process (the limit of positive reals needs not be positive, but is always nonnegative).

Now, any pair of distinct points on $S^1$ is in counterclockwise position (and in clockwise position, too), so (5) can be simply rewritten as follows:

(6) For any pair of distinct points $\left(t,s\right)\in \left(S^1\right)^2$, the real $\det\left(F^{\prime}\left(t\right),F^{\prime\prime}\left(t\right),...,F^{\left(n-1\right)}\left(t\right),F^{\prime}\left(s\right)\right)$ is nonnegative.

We can drop the "distinct" in (6), as well, because for $s=t$, the real is simply $0$. So we have:

(7) For any pair of points $\left(t,s\right)\in \left(S^1\right)^2$, the real $\det\left(F^{\prime}\left(t\right),F^{\prime\prime}\left(t\right),...,F^{\left(n-1\right)}\left(t\right),F^{\prime}\left(s\right)\right)$ is nonnegative.

But if we fix $t$ and integrate $\det\left(F^{\prime}\left(t\right),F^{\prime\prime}\left(t\right),...,F^{\left(n-1\right)}\left(t\right),F^{\prime}\left(s\right)\right)$ over $s\in S^1$, we must get zero (because $\det\left(F^{\prime}\left(t\right),F^{\prime\prime}\left(t\right),...,F^{\left(n-1\right)}\left(t\right),F^{\prime}\left(s\right)\right)$ is linear in $F^{\prime}\left(s\right)$, and the integral of $F^{\prime}\left(s\right)$ over $S^1$ is zero). The integral of a continuous nonnegative function is zero only if the function itself is identically zero. Thus, $\det\left(F^{\prime}\left(t\right),F^{\prime\prime}\left(t\right),...,F^{\left(n-1\right)}\left(t\right),F^{\prime}\left(s\right)\right)$ for all $s\in S^1$. This means that $F^{\prime}\left(s\right)$ lies in a fixed hyperplane for all $s\in S^1$. Now, taking ANY $n$ points $t_1$, $t_2$, ..., $t_n$ on $S^1$, we get linearly dependent vectors $F^{\prime}\left(t_1\right)$, $F^{\prime}\left(t_2\right)$, ..., $F^{\prime}\left(t_n\right)$, and this is of course a contradiction!

Or do we?

-

What is missing in the original solution is the following observation: If $F([a,t^\ast])$ does not lie a hyperplane, then we can find $\epsilon>0$ such that the extremum of $|P\circ F|$ on any one-dimensional projection $P$ orthogonal to $F(t^\ast)-F(a)$ does not occur on $(t^\ast-\epsilon,t^\ast]$. Similarly for $[t^\ast,a]$.

With this, you just pick $n-2$ points on $(t^\ast-\epsilon,t^\ast+\epsilon)$. We may assume that the space spanned by $F'$ at each of these points is $n-1$-dimensional and does not contain the vector $F(t^\ast)-F(a)$ (if it necessarily does, then adding one additional point makes the collection linearly dependent). Now throw in $F(t^\ast)-F(a)$ to obtain a hyperplane $L$ and take an orthogonal projection to obtain an extreme point on each side of $t^\ast$. Its derivative is zero, and it doesn't lie in the original collection by the remark.

-