# Largest rectangle bounded under a function

Let $f$ be a positive monotonically increasing real function in $[0,1]$. Let $F$ be the area under the curve of $f$ ($F=\int_0^1{f(x)dx}$)

For every $x\in[0,1]$, let $G(x)=f(x)\cdot (1-x)$ = the area of a rectangle bounded below the curve of $f$ and the $x$ axis:

Let $L=\left\lceil\log_2{\frac{f(1)}{f(0)}}\right\rceil$. Prove that there exists an $x$ such that:

$$G(x)\geq F/(2L)$$

Here is a possible proof:

Partition the interval $[0,1]$ to bins such that, in each bins $[a,b]$, $f(b)\leq 2f(a)$ (i.e. the value of $f$ grows by at most a factor of 2). The number of such bins is at most $L$. Hence, by the pigeonhole principle, there is a bin $[a,b]$ in which the area under the curve ($= \int_a^b{f(x)dx}$) is at least $F/L$. Now, this area is bounded below the rectangle $(b-a)f(b)$. By definition of a bin, $f(a)\geq f(b)/2$. Hence:\begin{align}G(a) &= (1-a)f(a) \\&\geq (b-a)f(a) \\&\geq (b-a)f(b)/2 \\&\geq F/2L\end{align}

MY QUESTIONS ARE:

1. Is there a simpler proof?

2. Is there a better bound for the area of the maximal rectangle?

• The result you want to prove (and hence also the proof) is false. The key observation is that $L = 0$ if $f(1) = f(0)$, hence, you are "dividing by $0$" in your bound $F/2L$ (which I read as $F/(2L)$. If you actually mean $FL/2$, things are of course different). More precisely, if we let $f(x) = 1+\epsilon x$, then your estimate yields $2 \geq 1+\epsilon \geq (1-x_\epsilon) \cdot (1 + \epsilon x_\epsilon) \geq \frac{1 + \epsilon/2}{2 \cdot \log_2 (1+\epsilon)} \xrightarrow[\epsilon \downarrow 0]{} \infty$, a contradiction. – PhoemueX Dec 31 '14 at 13:52
• You are right. I should put the log in $\lceil ... \rceil$ and note that $f(1)>f(0)$ since $f$ is monotonically increasing. – Erel Segal-Halevi Dec 31 '14 at 14:23

Let

• $f_0 = f(0)$ and $f_1 = f(1)$.
• $x_*$ be the point which maximizes $G(x) = f(x)(1-x)$ over $[0,1]$.
• $z_* = G(x_*) = f(x_*)(1-x_*)$.

It is clear $f_0 \le z_* \le f_1$ and by definition of $x_*$, we have

$$f_0 \le f(x) \le \min\left(\frac{z_*}{1-x}, f_1\right)\quad\text{ for } x \in [0,1]$$ This leads to $$F = \int_0^1 f(x) dx \le \int_0^{1-\frac{z_*}{f_1}} \frac{z_*}{1-x} dx + \int_{1-\frac{z_*}{f_1}}^1 f_1 dx = z_*\left(\log\frac{f_1}{z_*} + 1\right) \le z_*\left(\log\frac{f_1}{f_0} + 1\right)$$ As a result,

$$\max_{x\in [0,1]} G(x) = G(x_*) = z_* \ge \lambda_* F \quad\text{ where }\quad \lambda_* = \frac{1}{\log\frac{f_1}{f_0} + 1}\tag{*1}$$

This ratio $\lambda_*$ is the best we can have.

Let us first consider the case where "monotonic increasing" means "non-decreasing" instead of "strictly increasing". Fixing $f_0$ and $f_1$, the function $\tilde{f} : [0,1] \to [ f_0, f_1 ]$ defined by

$$\tilde{f}(x) = \min\left( \frac{f_0}{1-x}, f_1 \right)\tag{*2}$$

is non-decreasing, satisfying $\tilde{f}(0) = f_0, \tilde{f}(1) = f_1$. At the same time, we have

$$\max_{x\in[0,1]}\left\{ \tilde{f}(x)(1-x)\right\} = f_0 = \frac{1}{\log\frac{f_1}{f_0} + 1}\int_0^1 \tilde{f}(x) dx$$

which make the inequality in $(*1)$ becomes an equality.

If "monotonic increasing" means "strictly increasing", we can replace the $\tilde{f}$ in $(*2)$ by something like

$$\tilde{f}_\epsilon(x) = \min\left(\frac{f_0}{1-x}, f_1 - \epsilon(1-x)\right)$$

where $\epsilon$ is any sufficiently small positive number. Repeat the algebra, it is not hard to show

$$\max_{x\in[0,1]}\left\{ \tilde{f}_\epsilon(x)(1-x)\right\} = f_0 \quad\text{ and }\quad \frac{f_0}{\int_0^1 \tilde{f}_\epsilon(x) dx} \searrow \frac{1}{\log\frac{f_1}{f_0} + 1}\quad\text{ as }\quad\epsilon \searrow 0^{+}$$