# Easy but hard question regarding concave functions!

I have a question about concave functions. Let $f:[0,T]\rightarrow R^+$ is a concave function. Let $S=\int_0 ^ T f(x)dx$ and $R=\frac S T$. Show that there is an interval $[a,b]$, where $0\leq a \leq b \leq T$ and $b-a\geq \frac T 2$ such that for every $x\in [a,b]$ we have: $f(x) \geq R$.

If $f$ is non-decreasing function it is quite simple since by use of Jensen's inequality one can argue that $\frac 1 T \int_0 ^T f(x)dx \leq f(\frac T 2)$. Also I could prove this for piecewise linear concave functions. My proof is by induction on the number of line segments in the piecewise linear concave function. It is messy and use lots of geometric stuff. I wonder if there are any nice and tidy proofs for general concave functions.

-
I wonder how the piecewise linear case could be much easier than general... Did you try to approximate a general concave function by piecewise linear ones? (Welcome to Math.SE, by the way). – user53153 Dec 29 '12 at 20:04
Pavel, Thanks for your comment. Yes, we can approximate general concave functions by piecewise linear ones but my main problem is my proof for linear concave function is very messy and I believe there should be easy proofs for general concave functions with different approach. – user54626 Dec 29 '12 at 20:45
To me, the right idea should be to contruct a tent-shaped function $g$ that majorizes $f$. (If $[a,b]$ is the interval on which $f$ exceeds its average value $R$, then make the tent out of the tangent lines at $a$ and $b$, essentially.) Then one should be able to derive the statement for $f$ from the statement for $g$, which you've already established. – Greg Martin Dec 29 '12 at 22:01
Off topic: how can a question be "easy but hard"? :-) – Jesse Madnick Dec 29 '12 at 22:12
To a postmodern philosopher, that would be the default assumption for any hypothesis. – gnometorule Dec 29 '12 at 22:38

I liked this problem, it takes me way back! Here's my approach. It does rely on a few geometric notions but I like to think it is reasonably elementary and not too ugly (and that there are no mistakes).

Set

$$a := \inf \left\{ x \in [0,T] \; : \; f(x) \geq R \right\}$$

$$b := \sup\left\{ x \in [0,T] \; : \; f(x) \geq R \right\}$$

Let us focus on the general case in which $f(a) = f(b) = R$ (this will always happen if, say, $a$ and $b$ fall in the interior of $[0,T]$). In view of the concativity, there are constants $T_a, T_b > 0$ ($T$ for "tangent") such that

$$f(x) \leq T_a(x-a) + R$$

and

$$f(x) \leq T_b(b-x) + R$$

for all $x \in [0,T]$.

Do draw a diagram and then consider the (measurable) curvilinear sets:

$$X := \left\{ (x,y) \in \mathbb{R}^2 \; : \; 0 \leq x \leq a, \; f(x) \leq y \leq R \right\}$$

$$Y := \left\{ (x,y) \in \mathbb{R}^2 \; : \; a \leq x \leq b, \; R \leq y \leq f(x) \right\}$$

$$Z := \left\{ (x,y) \in \mathbb{R}^2 \; : \; b \leq x \leq T, \; f(x) \leq y \leq R \right\}$$

Note that the constant $R$ is the mean value of $f$ and is such that $\mathscr{L}^2(Y) = \mathscr{L}^2(X) + \mathscr{L}^2(Z)$, with $\mathscr{L}^2$ denoting Lebesgue measure.

Our linear concativity estimates above allow us to further estimate these measures from above and below by the measures of certain triangles (looking at your diagram is going to help here).

In particular, we may estimate $\mathscr{L}^2(Y)$ from above by the area of the triangle determined by the lines $y = T_a(x-a)+R$, $y = T_b(b-x)+R$, and $y = R$. Some basic Euclidean geometry then gives

$$\mathscr{L}^2(Y) \leq \frac{1}{2} \frac{(b-a)^2 T_a T_b}{T_a+T_b}$$

(The right hand side is simply the area of the triangle.) Similarly bound $\mathscr{L}^2(X)$ from below by the area of the orthogonal triangle $x = 0$, $y = R$, $y = T_a(x-a)+R$, and $\mathscr{L}^2(Z)$ from below by the area of the corresponding triangle on the right determined by $x = T$, $y = R$, $y = T_b(b-x)+R$.

$$\mathscr{L}^2(X) + \mathscr{L}^2(Z) \geq \frac{1}{2} a^2 T_a + \frac{1}{2} (T-b)^2 T_b$$

Since $\mathscr{L}^2(Y) = \mathscr{L}^2(X) + \mathscr{L}^2(Z)$, we need have

$$\frac{1}{2} \frac{(b-a)^2 T_a T_b}{T_a + T_b} \geq \frac{1}{2} a^2 T_a + \frac{1}{2} (T-b)^2 T_b$$

Things start to look a little hopeful around here; indeed we are close. Canceling the $\frac{1}{2}$ factor and multiplying through by $\frac{T_a+T_b}{T_a T_b}$ we get

$$(b-a)^2 \geq a^2 \frac{T_a + T_b}{T_b} + (T-b)^2 \frac{T_a + T_b}{T_a} = a^2 + (T-b)^2 + a^2 \frac{T_a}{T_b} + (T-b)^2 \frac{T_b}{T_a}$$

We may of course estimate the last two terms by AM-GM (or $x^2 + y^2 \geq 2xy$) and get

$$(b-a)^2 \geq a^2 + (T-b)^2 + 2a(T-b) = (T-b+a)^2$$

from where it follows that $b-a \geq \frac{1}{2} T$. This settles the "general case" where $f(a) = f(b) = R$.

In some situations $f(a)$ or $f(b)$ (but not both) may fail to equal $R$. This boundary situation is easily amenable. In that case we have $f(a) = R$, $f(b) > R$, $b = T$ (or with $a$ and $0$ in place of $b$ and $T$). Then instead of comparing the areas of three triangles (one scalene, two orthogonal), we just compare the areas of two orthogonal triangles (one defined by $x = 0$, $y = R$, $y = T_a(x-a)+R$, and the other one defined by $x = T$, $y = R$, $y = T_a(x-a)+R$). This is much easier and immediately gives $a \leq \frac{1}{2} T$, $b = T$.

-
Hi Christos. Thanks for this nice and neat proof! It was AWESOME! – user54626 Jan 1 '13 at 21:19
Sure my friend, glad you liked it. – Christos Jan 2 '13 at 2:58

Here is an idea, too long for a comment:

I assume your function is continuous.

As you said, by Jensen

$$\frac 1 T \int_0 ^T f(x)dx \leq f(\frac T 2)$$

Now, all you need is to observe that any concave function has at most one local maximum on $(0,T)$ and no local minimum. Because of this, there are only few possibilities:

-f is non-decreasing

-f is non-increasing

-f is increasing up to $x_0$ and decreasing from $x_0$.

In the first case $[\frac{T}{2},T]$ works while in the second $[0, \frac{T}{2}]$ works.

In the last case, it is easy to prove that the equation $f(x)=R$ has exactly two solutions $[a,b]$. All you need is to show that $b-a \geq \frac{T}{2}$.

I would look to the problem on $[0,x_0]$ and $[x_0,T]$. Maybe a similar idea can Yield $a \leq \frac{x_0}{2}$ and $b \geq \frac{x_0+T}{2}$...

-
I was pretty much at this point, but working as usual with phone and such isn't that great. The last step you mentionis geometrically obvious by contradiction, because of the curvature of f and f positive. I'm not saying I can throw a solution down, but it should follow more or less from curvature (if you say this above, and I'm parroting you, apologies: as said, on phone and a bit handicapped by it). – gnometorule Dec 29 '12 at 22:35
As in: the 'derivative' is larger before $a$ and after $b$ compared to between the two (note $f$ positive); as these points are two points whose $f$ value satisfies the MVT for integrals, you need to compensate by making $b - a$ larger than its complement to average out fine. – gnometorule Dec 29 '12 at 22:48

We may restrict attention to the case where $T=S=1$, $f$ is continuous non-negative and $f(0)=0$.

The details of how this is done are given at the end of this post, and aren't all too important. It's just a matter of making $f$ continuous, rescaling it and possibly switching left and right.

Define $0< a<b\leq 1$ by $$a=\inf\lbrace x\in [0,1] \text{ such that }f(x)\geq\frac{1}{2}\rbrace$$ $$b=\sup\lbrace x\in [0,1] \text{ such that }f(x)\geq\frac{1}{2}\rbrace$$ By concavity, $f\geq\frac12$ on all of $[a,b]$, and so it suffices to show $b-a\geq\frac12$.

• $a\leq\frac14$: Since $f$ is concave, its graph lies below its tangent lines. Let $L$ be a line that passes through $(a,\frac12)$ and lies over the graph of $f$. Because $f(0)=0$ and $f(1)\geq 0$, $L$ obeys an equation $y=\alpha x+\beta$ where $$\beta\geq 0,~\alpha+\beta\geq 0\text{ and }a\alpha+\beta=\frac12.$$ Also, since $a$ is by definition the smallest $t$ for which $f(t)\geq\frac12$ and $f$ has area $1$, $L$ may not be decreasing; for otherwise $f$ would be constantly $\leq\frac12$ which would imply $S\leq\frac12$. Therefore $$\alpha>0.$$ The area enclosed by $L$ and the horizontal axis between the endpoints $x=0$ and $x=1$ equals $\beta+\frac12\alpha$ and must exceed the area enclosed under $f$ in that same interval, that is, it must exceed $1$. Thus $$1\leq \beta+\frac12\alpha\text{ i.e. }\frac12\leq(\frac12-a)\alpha.$$ Therefore, $a<\frac12$. Now suppose we had $\frac14<a<\frac12$, then by the above equation, we'd get $2<\alpha$ and $\frac12= a\alpha+\beta\geq a\alpha>\frac14\cdot 2=\frac12$ which is absurd, so $0<a\leq\frac14$.
• $b\geq \frac34$: The exact same proof will produce a contradiction from $b<\frac34$.

Therefore $$b-a\geq \frac12$$ and we are done.

## The reduction

Let us replace $f\neq0$ by an auxiliary function. The two bullet points below are the details of how we define this auxiliary function, they are unimportant.

• Let us redefine $f(0)$ and $f(T)$ by $\lim_{0^+}f$ and $\lim_{T^-}f$ respectively (they are finite nonnegative and exist by concavity). This allows us to suppose $f$ continuous over $[0,T]$.
• We rescale $f$ by defining for all $x\in[0,1]$ $$g(x)=\frac{f(\frac{x}{T})-f(0)}{S-Tf(0)}$$ if $f(0)\leq f(T)$, and $$g(x)=\frac{f(\frac{T-x}{T})-f(T)}{S-Tf(T)}$$ if $f(T)\leq f(0)$
-
I just noticed I misread the question ^^, I'll correct my answer accordingly tomorow, but I think a variation on this idea will work. – Olivier Bégassat Dec 30 '12 at 2:53
Also, Greg Martin actually proposed the right idea several hours ago... – Olivier Bégassat Dec 30 '12 at 3:04
A solution was posted here based on that idea (tent-shaped function) but it wasn't correct. Still there might be some chance that it works, but the connection seems to be non-trivial. – afshi7n Dec 30 '12 at 3:44