2
$\begingroup$

Is it possible to find the smallest positive real number $c$ (or at least the smallest positive integer $c$) such that the following result holds for all functions $f$ satisfying some conditions?

Let $f:[0,a] \rightarrow [0,b]$ be a decreasing convex function, such that $f(0)=b$ and $f(a)=0$.
Let the area of the set $S=\{0 \leq x \leq a, 0 \leq y \leq f(x)\}$ be equal to $1$.
There exist $k \ge 1$ rectangles $R_1, ..., R_k$ such that the point $(0,0)$ is a vertice of all these rectangles, their sides are parallel to the $x$-axis and $y$-axis, together they cover $S$ and the sum of their areas is less than or equal to $c$.
(the variables $a,b,k$ and theses rectangles depend on $f$).

$\endgroup$

1 Answer 1

1
$\begingroup$

The following is obviously not optimal, but at least it shows that the optimal $c$ satisfies $c \leqslant 4$. On the other hand, $c \geqslant 2 / \log 2 \approx 2.885$, so if $c$ is to be integer, it remains to show that in fact $c < 4$ and hence necessarily $c = 3$.

Edit: As remarked in the comments, the following argument works for continuous decreasing functions, not necessarily convex.


Notation: Write $|A|$ for the area of $A$.


By approximation, it is sufficient to consider the case when $f'(0^+)$ and $f'(b^-)$ are finite and non-zero, and $f$ is strictly convex (edit: this is not really needed). Denote by $F$ the region under the graph of $f$: $$ F = \{(x, y) \in [0, \infty)^2 : y \leqslant f(x)\} .$$ Rather than assuming that $|F| = 1$, we allow for arbitrary $|F|$ and study the inequality $$ \inf \sum_{j = 1}^k |R_j| \leqslant c |F| , \tag{$\spadesuit$} $$ where the infimum is taken over all possible families of "proper" rectangles $R_j$ that cover $F$.


We construct rectangles $R_j = [0, a_j] \times [0, b_j]$ in an iterative way. By $D_j$ we denote the "decreasing" diagonal of $R_j$: the line segment connecting $(0, a_j)$ with $(b_j, 0)$.

First, we choose $b_1 = b$ and $a_1 = b / |f'(0^+)|$, so that the diagonal $D_1$ is tangent to the graph of $f$ at $(0, b)$.

Once $a_j$ and $b_j$ are chosen, we set $b_{j+1} = f(a_j)$ and we choose $a_{j+1}$ in such a way that the diagonal $D_{j+1}$ is tangent to the graph of $f$. More precisely, $a_{j+1}$ is the largest number such that $D_j$ is contained in $F$. If $a_{j+1} = a$, we set $k = j + 1$, and we stop.

two rectangles

Step 1. Consider two adjacent rectangles $R_j = [0, a_j] \times [0, b_j]$ and $R_{j+1} = [0, a_{j+1}] \times [0, b_{j+1}]$ (see figure above). The diagonal $D_j$ is tangent to the graph of $f$ at a certain point $(\alpha, \beta)$. This point lies below the segment with endpoints $(0, b_j)$ and $(a_j, b_{j+1})$ (the "decreasing" diagonal of $[0, a_j] \times [b_j, b_{j+1}]$). Thus, this segment necessarily lies above the secant line of $f$ passing through $(\alpha, \beta)$ and $(a_j, b_{j+1})$, and this, in turn, lies above the tangent line to the graph of $f$ at $(a_j, b_{j+1})$. It follows that, $$ \frac{b_j - b_{j+1}}{a_j} \geqslant |f'(a_j)| . $$ Similarly, $$ |f'(a_j)| \geqslant \frac{b_{j+1}}{a_{j+1} - a_j} \, , $$ and hence $$ \frac{b_j - b_{j+1}}{a_j} \times \frac{a_{j+1} - a_j}{b_{j+1}} \geqslant 1 . $$ We write $a_j = p a_{j+1}$ and $b_{j+1} = q a_{j+1}$. The above inequality reads $$ \frac{1 - q}{p} \times \frac{1 - p}{q} \geqslant 1 . $$ Equivalently, $(1 - p) (1 - q) \geqslant p q$, or $$ p + q \leqslant 1 . $$ Geometrically speaking: the "decreasing" diagonal of a larger rectangle $[0, a_{j+1}] \times [0, b_j]$ passes above the point $(a_j, b_j)$.

Step 2. The above implies that our procedure ends after a finite number of steps. Indeed: $$ \frac{b_{j+1} / a_{j+1}}{b_j / a_j} = p q \leqslant \frac{1}{4} , $$ and so $b_j / a_j$ eventually becomes less than or equal to $|f'(a^-)|$. This, however, means that $b_j \leqslant a |f'(a^-)|$ and consequently $a_j = a$ and $k = j$. (This shows that in fact $k \leqslant \log_4 |f'(0^+) / f'(a^-)|$.)

enter image description here

Step 3. We divide $F$ with line segments that connect $(a_j, b_{j+1})$ with the origin. Let $F_j$ be the curvilinear triangle with vertices $(0, 0)$, $(a_{j-1}, b_j)$ and $(a_j, b_{j+1})$ (the blue region in the figure above). We claim that $$|F_j| \geqslant \tfrac{1}{4} (|R_j| + |R_{j+1}|) . \tag{$\clubsuit$}$$ In order to prove this claim, observe that $|F_j|$ is clearly greater than the area of the blue region $F_j'$ in the following picture.

enter image description here

Denote $p = a_{j-1} / a_j$ and $q = b_{j+1} / b_j$, and let $(\alpha, \beta)$ be the point at which the diagonal $D_j$ is tangent to the graph of $f$. Since $p a_j = a_{j-1} \leqslant \alpha$ and $q b_j = b_{j+1} \leqslant \beta$, and $\tfrac{\alpha}{a_j} + \tfrac{\beta}{b_j} = 1$ (the point $(\alpha, \beta)$ lies on the diagonal $D_j$), we have $p + q \leqslant 1$. The area of the blue region on the last picture is equal to $$ \tfrac{1}{2} (1 - p - q + p^2 + q^2) a_j b_j , $$ and this is minimised at $p = q = \tfrac12$. Thus, $$ |F_j| \geqslant |F_j'| \geqslant \tfrac{1}{4} a_j b_j = \tfrac{1}{4} |R_j| , $$ as claimed. Our claim is proved.

Step 4. By summing up over all $j$, we see that $$ |F| \geqslant \sum_j |F_j| \geqslant \frac{1}{4} \sum_j |R_j| . $$ In other words, the inequality ($\spadesuit$) holds with $c = 4$.


The constant $c = 4$ in ($\spadesuit$) does not seem optimal, but it cannot be improved much. If $f(x) = \tfrac{1}{x}$ for $x \in [1, 2^n]$, and $f$ is otherwise linear, then the optimal choice seems to be $R_0 = [0,1]\times[0,2]$, $R_j = [0, 2^j] \times [0, 2^{1-j}]$ for $j = 1,2, \ldots, n$ and $R_{n+1} = [0, 2^{n+1}] \times [0, 2^{-n}]$. The area under $f$ is $3 + n \log 2$, while the sum of the areas of $R_j$ is $4 + 2 n$, and so $c \geqslant 2 / \log 2 \approx 2.885$.

$\endgroup$
7
  • $\begingroup$ Thank you! I have some doubts, doesn't the diagonal of the leftmost rectangle always intersect $F$? Also could you please provide more details why the procedure stops after a finite number of steps? $\endgroup$
    – jack
    Commented Oct 17, 2021 at 3:10
  • $\begingroup$ I'll try to add additional details soon. $\endgroup$ Commented Oct 17, 2021 at 8:46
  • $\begingroup$ Looks like I got a bunch of inequalities wrong. It should be fixed now (with a significantly different approach). Let me know if there's any mistake in the revised answer. $\endgroup$ Commented Oct 17, 2021 at 14:22
  • $\begingroup$ (+1) Maybe the area of the rectangle $[0, a_j] \times [b_{j+2}, b_{j+1}]$ can be considered to improve your method. $\endgroup$
    – jack
    Commented Oct 18, 2021 at 2:18
  • $\begingroup$ I think I managed to improve the bound to $c = 4$; see the edited answer. $\endgroup$ Commented Oct 18, 2021 at 14:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .