Sharp L1 Inequalities for Sup-Convolution

- Mathematics, Stanford University (CA)
- More about Hunter Spink

- Mathematical Institute, University of Oxford
- More about Marius Tiba

- Math, University of Cambridge
**ORCID iD:**0000-0002-2323-2897- More about Peter van Hintum

*Discrete Analysis*, July. https://doi.org/10.19086/da.81314.

### Editorial introduction

Sharp L1 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 Rk. Their *sup-convolution* f∗g is given by the formula

f∗g(x)=sup(y+z)/2=xf(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 pi 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 ∑ipi(xi) over all (x1,…,xn) such that ∑ixi=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* hyp(f) of a function f:Rk→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 hyp(f∗g)=12(hyp(f)+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)∈hyp(f), (v,w)∈hyp(g), and y=(z+w)/2, which in turn is true if and only if (x,y)∈12(hyp(f)+hyp(g)).

If one wants to obtain bounded convex bodies, one can modify the definition above and take instead the set {(x,y:λ<y<f(x))} for some sufficiently negative λ, 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 R2. 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 Rk, then the Minkowski sum 1n(A+⋯+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 1n(A+⋯+A)=A. Clearly, 1n(A+⋯+A) is *contained* in the convex hull co(A), so the aim has been to find upper bounds for the quantity

|co(A)∖1n(A+⋯+A)|,

or more naturally, for the ratio of the above quantity to the volume of 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≤g and g is concave, then f∗n≤g. So one expects the iterated sup-convolutions f∗n to converge to co(f), the smallest concave function that dominates f. The main result is an inequality of the form

∫(f∗n(x)−f(x))dx

≥cn,k∫(co(f)(x)−f(x))dx

where cn,k is a constant that tends to 1 as n→∞. That is, the authors study convergence in the L1 sense, obtaining the best known estimates for cn,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 Rk and 0≤t≤1, then |tA+(1−t)B|1/k≥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?