Sharp $L^1$ Inequalities for Sup-Convolution

Sharp $L^1$ Inequalities for Sup-Convolution, Discrete Analysis 2023:7, 16 pp.

Let $f$ and $g$ be two real-valued functions defined on a compact convex subset $C$ of $\mathbb R^k$. Their sup-convolution $f*g$ is given by the formula
$$f*g(x)=\sup_{(y+z)/2=x}\frac{f(y)+f(z)}2.$$
That is, it is the largest average of $f(y)$ and $f(z)$ over all pairs $y,z$ that average to $x$. The sup-convolution of more functions is defined in a similar way.

Sup-convolutions are interesting for many reasons. For instance, if a firm wishes to buy a certain amount $x$ of some resource from $n$ different suppliers and the price from each supplier is a function $p_i$ depends in a non-linear way on the quantity bought (which often happens in practice – for example, there can be bulk deals), then working out how to minimize the total cost is asking to minimize the quantity $\sum_ip_i(x_i)$ over all $(x_1,\dots,x_n)$ such that $\sum_ix_i=x$. This can easily be transformed into a problem of working out the value of a sup-convolution at $x$.

More relevant to this article is a close connection between sup-convolutions and sumsets. The strict hypograph $\text{hyp}(f)$ of a function $f:\mathbb R^k\to\mathbb R$ is the set $\{(x,y:y<f(x))\}$ of all points on or below the graph of $f$. It is not hard to show that $\text{hyp}(f*g)=\frac 12({\text{hyp}(f)+\text{hyp}(g)})$. Indeed, $y<(f*g)(x)$ if and only if there exist $u$ and $v$ with $(u+v)/2=x$ and $y<(f(u)+f(v))/2$, which is true if and only if there exist $z$ and $w$ with $(u,z)\in\text{hyp}(f)$, $(v,w)\in\text{hyp}(g)$, and $y=(z+w)/2$, which in turn is true if and only if $(x,y)\in\frac 12(\text{hyp}(f)+\text{hyp}(g))$.

If one wants to obtain bounded convex bodies, one can modify the definition above and take instead the set $\{(x,y:\lambda<y<f(x))\}$ for some sufficiently negative $\lambda$, and a similar statement holds.

In convex geometry, sumsets are referred to as Minkowski sums, about which there are many interesting problems. For instance, the following is an open problem with a surprisingly basic statement.

Problem. Let $A$ be a compact subset of $\mathbb R^2$. Must the area of $(A+A+A)/3$ be at least the area of $(A+A)/2$?

This paper contributes to a general line of enquiry concerning the relationship between Minkowski sums and convexity. One would expect that if $A$ is a (suitably nice) subset of $\mathbb R^k$, then the Minkowski sum $\frac 1n(A+\dots+A)$, where the sum is an $n$-fold sum, should converge to the convex hull of $A$, since $A$ is convex if and only if $\frac 1n(A+\dots+A)=A$. Clearly, $\frac 1n(A+\dots+A)$ is contained in the convex hull $\text{co}(A)$, so the aim has been to find upper bounds for the quantity
$$|\text{co}(A)\setminus\frac 1n(A+\dots+A)|,$$
or more naturally, for the ratio of the above quantity to the volume of $\text{co}(A)$, and thus to understand the speed of convergence. Results in this direction have been obtained by Starr, Shapley and Folkman, by Emerson and Greenleaf in 1969. Ruzsa obtained further results in a 1997 paper, the main aim of which was to show that the Brunn-Minkowski inequality (which we state below) can be significantly improved for sets that are far from convex.

This paper looks at a closely related question about sup-convolutions. If $f$ is a concave function, then the $n$-fold sup-convolution $f^{*n}$ is equal to $f$. Also, it is easy to see that if $f\leq g$ and $g$ is concave, then $f^{*n}\leq g$. So one expects the iterated sup-convolutions $f^{*n}$ to converge to $\text{co}(f)$, the smallest concave function that dominates $f$. The main result is an inequality of the form
$$\int (f^{*n}(x) -f(x)) dx$$
$$\geq c_{n,k}\int(\text{co}(f)(x)-f(x)) dx$$
where $c_{n,k}$ is a constant that tends to 1 as $n\to\infty$. That is, the authors study convergence in the $L_1$ sense, obtaining the best known estimates for $c_{n,k}$.

These questions are closely related to the important problem of the stability of the Brunn-Minkowski inequality. The Brunn-Minkowski inequality itself states that if $A$ and $B$ are two measurable subsets of $\mathbb R^k$ and $0\leq t\leq 1$, then $|tA+(1-t)B|^{1/k}\geq t|A|^{1/k}+(1-t)|B|^{1/k}$, with equality if and only if $A$ and $B$ are homothetic copies of the same convex body. The stability question is to examine the case of near equality: if it holds, then how close must $A$ and $B$ be to a pair of homothetic convex bodies?