NOTES ON EXTREMAL APPROXIMATELY CONVEX FUNCTIONS AND ESTIMATING THE SIZE OF CONVEX

HULLS

S. J. DILWORTH, RALPH HOWARD, AND JAMES W. ROBERTS

This is a set of notes that is basically and expanded version of the paper Extremal Approximately Convex Functions and Estimating the Size of Convex Hulls. The differences are a few extra pictures, Section 2.7 which is an exposition of results of Ng and Nikodem [5] about measurable approximately convex functions, and an alternate proof of Theorem 2.27 is included.

Contents

1. Introduction 2 2. Approximately Convex Functions 4 2.1. Bounds on approximately convex functions 5 2.2. Lower semi-continuity and mean value properties of extremal

approximately convex functions 7

2.3. The extremal approximately sub-affine function H(x) 12 2.4. The extremal approximately convex function E(x) on a simplex 19 2.5. Extremal approximately convex functions on convex polytopes 28 2.6. A stability theorem of Hyers-Ulam type 29 2.7. Measurable approximately convex functions 30 2.8. Examples of approximately convex functions 33 3. The Size of the Convex Hull of an Approximately Convex Set 34 3.1. General upper bounds 34 3.2. General lower bounds. 36 3.3. The sharp bounds in Euclidean Space 38 3.4. The sharp two dimensional bounds 42 References 44

Date: July, 1998.

1991 Mathematics Subject Classification. Primary: 26B25 52A27; Secondary: 39B72 41A44 51M16 52A21 52A40.

Key words and phrases. Convex hulls, convex functions, approximately convex functions, normed spaces, Hyers-Ulam Theorem.

The research of the second author was supported in part from ONR Grant N00014-90-J-1343 and ARPA-DEPSCoR Grant DAA04-96-1-0326.

1. Introduction

The problem motivating this paper is the following: given a set A in R^{n}, estimate the size of the convex hull Co(A) of A in terms of geometric properties of A. To do this we assume that R^{n} is equipped with a norm ∥ · ∥. Then a first step in constructing the convex hull of A is to add all the midpoints of segments joining points of A. The size of Co(A) can be estimated in terms of this first step.

Our main result gives the sharp constants in this estimate for n-dimensional Euclidean spaces and it provides an estimate for the constants for general n-dimensional normed spaces which is accurate to within 2/n. (Here dist(x, A) := inf{∥x − a∥ : a ∈ A} is the distance of the point x from the set A.)

Theorem 1. If (R^{n}, ∥ · ∥) is an n-dimensional normed linear space then there is a constant C_{∥·∥}, depending on the norm ∥ · ∥, so that if A ⊂ R^{n} satisfies

(1.1) a_{0}, a_{1} ∈ A implies dist (\frac{a_{0} + a_{1}}{2} , A) ≤ δ,

then

z ∈ Co(A) implies dist(z, A) ≤ C_{∥·∥}δ.

Letting [ ·] be the greatest integer function, the sharp constant C_{∥·∥} satisfies

[log_{2}(n − 1)] + 1 + (n − 1)/2^{[log_{2}(n−1)]} ≤ C_{∥·∥} ≤ [log_{2}(n)] + 1 + n/2^{[log_{2}(n)]}

(this holds for all norms) and the sharp constant when ∥ · ∥ is the Euclidean norm is C_{∥·∥} = [log_{2}(n − 1)] + 1 + (n − 1)/2^{[log_{2}(n−1)]}.

The upper bound C_{∥·∥} ≤ 2⌈log_{2}(n + 1)⌉ (where ⌈·⌉ is the ceiling function) is implicit in the paper [1, Props 3.3 and 3.4] of Casini and Papini.

For bounded sets this can be given a concise restatement in terms of the Hausdorff distance between sets. Recall that if A, B ⊂ R^{n} are bounded then the Hausdorff distance, d_{H}(A, B), between A and B is the infimum of the numbers r so that every point of A is within a distance r of a point of B and every point of B is within distance r of a point of A. Define numbers κ(n) for n ≥ 0 by κ(0) := 0 and

κ(n) := [log_{2}(n)] + 1 + n/2^{[log_{2}(n)]}

for n ≥ 1. The collection of midpoints of segments joining pairs of points of A is \frac{1}{2}(A + A) = \{(a + b)/2 : a, b ∈ A\}. Then Theorem 1 can be restated as

d_{H}(Co(A), A) ≤ C_{∥·∥}d_{H}(\frac{1}{2}(A + A), A)

where the sharp constant C_{∥·∥} satisfies

κ(n − 1) ≤ C_{∥·∥} ≤ κ(n)

APPROXIMATELY CONVEX FUNCTIONS AND THE SIZE OF CONVEX HULLS 3

and C_{∥·∥} = κ(n − 1) when ∥ · ∥ is the Euclidean norm. (Allowing +∞ for a value of d_{H}(A, B) this also holds for unbounded sets). If A is a finite set with N points, then d_{H}(A, \frac{1}{2}(A + A)) = max_{b,c∈A} min_{a∈A} ∥a − \frac{1}{2}(b + c)∥ which can be computed in O(N^{3}) operations. Thus for finite sets Theorem 1 allows estimation of d_{H}(A, Co(A)) in polynomial time.

For general norms obtaining the lower bound κ(n − 1) ≤ C_{∥·∥} is more difficult than the upper bound and involves construction of some interesting geometric objects, the extremal approximately convex functions. To describe these we first make a couple of definitions. The following is motivated by taking δ = 1 in the hypothesis of Theorem 1.

Definition 1. Let (X, ∥ · ∥) be a normed space. Then a subset A ⊂ X is an approximately convex set iff for all a, b ∈ A

dist(\frac{1}{2}(a + b), A) ≤ 1.

If A is an approximately convex set then the function h(x) = dist(x, A) (the distance of x from A) will satisfy a weak form of the inequality satisfied by a convex function. We isolate this property:

Definition 2. Let E be a convex set in the normed space (X, ∥ · ∥). Then a function h: E → R is an approximately convex function iff for all a, b ∈ E

h(\frac{a + b}{2}) ≤ \frac{h(a) + h(b)}{2} + 1.

(Strictly speaking this should be “approximately midpoint convex” or “approximately Jensen convex” but for the sake of brevity we will use “approximately convex”.) Let Δ_{n} := {(α_{0}, …, α_{n}) : α_{k} ≥ 0, ∑_{k=0}^{n} α_{k}} be the standard n-dimensional simplex. Then the result leading to the lower bounds on C_{∥·∥} is the explicit computation of the extremal approximately convex function on the simplex.

Theorem 2. There is an approximately convex E: Δ_{n} → R which vanishes on the vertices of Δ_{n} with the following properties:

1. If h is a bounded (or Borel-measurable) approximately convex function on Δ_{n} which takes non-positive values on the vertices, then h(x) ≤ E(x) for x ∈ Δ_{n}.

2. E achieves its maximum value of κ(n).

3. E is lower semi-continuous. The property 1 characterizes E uniquely. Moreover E is given concretely in terms of an elementary infinite sum (see equations (2.19) and (2.21)).

The examples showing the lower bounds on C_{∥·∥} in Theorem 1 are sharp and are constructed from the graph of E. The lower semi-continuity of E and the fact that E has κ(n) as its maximum are important in these constructions. We note the mere existence of E (which follows from abstract considerations) is less important than the fact that E is given explicitly in a relatively simple form (cf. §2.4 and Figure 3).

We now give a more detailed description of our results. In §2.1 we give upper bounds on approximately convex functions which are locally bounded from above. Motivated by Perron’s method in the theory of harmonic functions in §2.2 we show that given a compact convex set K ⊂ R^{n} with extreme points V and a uniformly continuous function φ: V → R then there is a a unique extremal bounded approximately convex function E_{K,φ} on K which agrees with φ on V; moreover, E_{K,φ} is realized (as in Perron’s method) as the pointwise supremum of all bounded approximately convex functions on K which agree with φ on V. The function E_{K,φ} is lower semi-continuous, characterized by a mean-value property, and satisfies a certain maximum principle.

§2.3 and §2.4 contain a description of the extremal approximately convex function E on the simplex and proofs of the properties of E listed in Theorem 2. In § 2.5, we determine the extremal function E_{K,φ} when K is a convex polytope. A stability theorem with sharp constants for approximately convex functions of the type first given by Hyers and Ulam [4] is given in §2.6. This states that an approximately convex function can be approximated in the uniform norm by a convex function with error only depending on the dimension of the domain. The example showing the constants are sharp is the extremal function E. The rest of Section 2 gives various other properties and examples of approximately convex functions.

Section 3 gives the proof of Theorem 1 and some of its extensions and refinements. The first two sections give the upper and lower bounds κ(n−1) ≤ C_{∥·∥} ≤ κ(n) for general norms. The upper bound follows from the general upper bounds on approximately convex functions and the lower bound uses properties of the extremal approximately convex function E on Δ_{n}. The proof that C_{∥·∥} = κ(n − 1) in the Euclidean case is given in §3.3. This requires some (hopefully interesting) geometrical arguments in addition to Theorem 2. Finally, we prove that C_{∥·∥} = 2 for all two-dimensional norms. This argument is somewhat ad hoc and does not appear to extend to higher dimensions.

2. Approximately Convex Functions

We first relate approximately convex functions to approximately convex sets.

2.1. Proposition. Let (X, ∥ · ∥) be a normed space, A ⊂ X, and define h(x) := dist(x, A). Then A is an approximately convex set if and only if h is an approximately convex function.

Proof. If h(x) = dist(x, A) is an approximately convex function it is clear that A is an approximately convex set. Conversely if A is an approximately convex set, let x_{0}, x_{1} ∈ X and ε > 0. Choose a_{0}, a_{1} ∈ A so that h(x_{0}) = dist(x_{0}, A) ≤ ∥x_{0} −a_{0}∥+ε and h(x_{1}) ≤ ∥x_{1} −a_{1}∥+ε. As A is approximately convex dist((a_{0} + a_{1})/2, A) ≤ 1. Thus

dist(\frac{x_{0} + x_{1}}{2} , A) ≤ ∥\frac{x_{0} − a_{0}}{2} ∥ + ∥\frac{x_{1} − a_{1}}{2} ∥ + dist(\frac{a_{0} + a_{1}}{2} , A)

≤ \frac{h(x_{0}) + h(x_{1})}{2} + ε + 1

As ε as arbitrary this completes the proof. (This proof is implicit in the paper of Casini and Papini [1, Prop. 3.4].)

2.1. Bounds on approximately convex functions. The first bound is an extension to approximately convex functions of a standard result about convex functions.

2.2. Proposition. Let U ⊆ R^{n} be a convex set and h: U → R be approximately convex and bounded from above by C. Then for any x_{0} ∈ U and x ∈ U ∩ (2x_{0} − U) (if x_{0} is in the interior of U this is a neighborhood of x_{0} in U) the inequality

h(x) ≥ 2h(x_{0}) − C − 2

holds, and so h is bounded from below in U ∩ (2x_{0} − U). Thus h is bounded from below on compact subsets of the interior of U.

Proof. Let y = 2x_{0} − x. Then y ∈ U as x ∈ (2x_{0} − U). Also x_{0} = (x + y)/2. Thus

h(x_{0}) = h(\frac{x + y}{2} ) ≤ \frac{h(x) + h(y)}{2} + 1 ≤ \frac{h(x) + C}{2} + 1.

Solving this for h(x) completes the proof.

The following theorem is one of our main results.

2.3. Theorem. Let A ⊂ R^{n} with convex hull E = Co(A). Let h: E → R be an approximately convex function which is bounded above and which satisfies h ≤ 0 on A. Then

sup_{x∈E} h(x) ≤ [log_{2} n] + 1 + \frac{n}{2^{[log_{2} n]}} .

Moreover this is the sharp upper bound (the sharpness follows from Theorem 2.27).

2.4. Remark. The assumption that h is bounded above can not be dropped. For the relevant example see Example 2.51 in §2.8 below.

Before giving the proof we give a name to the bounds in the Theorem and show that they satisfy a recursion which is a main ingredient of the proof. Let κ(0) = 0 and for n ≥ 1

κ(n) = [log_{2} n] + 1 + \frac{n}{2^{[log_{2} n]}} . (2.1)

This notation will be use throughout the rest of the paper.

2.5. Proposition. The sequence ⟨κ(n)⟩_{k=0}^{∞} satisfies the recursion

κ(n) = max_{\begin{matrix}n_{1}+n_{2}=n \\ n_{1},n_{2}≥0 \end{matrix}} \frac{κ(n_{1}) + κ(n_{2})}{2} + 1 (2.2)

for n ≥ 1.

2.6. Lemma. Let ⟨α(i)⟩_{i=0}^{m} be a finite sequence on {0, 1, …, m} so that ⟨α(j)−α(j −1)⟩_{j=1}^{m} is monotone decreasing (that is the sequence is concave). Then

max_{i+j=n} \frac{α(i) + α(j)}{2} + 1 = \begin{cases}α(n) + 1 = \frac{α(n) + α(n)}{2} + 1, & m = 2n; \\ \frac{α(n) + α(n + 1)}{2} + 1, & m = 2n + 1. \end{cases}

Proof. Let β(i) = (α(i) + α(n − i))/2 + 1. Then the concavity of ⟨α(i)⟩ implies the sequence ⟨β(i)⟩ is also concave. Also β(i) = β(n − i) so ⟨β(i)⟩ is symmetric. But a symmetric concave function takes on its maximum at the center of its interval of definition. Thus if m = 2n is even the maximum is β(n) = α(n) + 1 and if m = 2n + 1 the maximum is β(n) = β(n + 1) = (α(n) + α(n + 1))/2 + 1.

Proof of Proposition 2.5. A calculation shows

κ(2n) = κ(n) + 1, κ(2n + 1) = \frac{κ(n) + κ(n + 1)}{2} + 1.

(The second of these is most easily seen by writing n = 2^{m} + r where 0 ≤ r ≤ 2^{m} − 1.) But the sequence ⟨κ(n) − κ(n − 1)⟩_{k=1}^{∞} is monotone decreasing so that an application of the last lemma completes the proof.

Proof of Theorem 2.3. Recalling the definition of κ(n) we wish to show that sup_{x∈E} h(x) ≤ κ(n) We use induction on n based on the recursion (2.2) satisfied by κ. The base case of n = 0 is clear. Suppose n ≥ 1 and assume that the assertion holds for all integers less than n. If x ∈ E then by Carathéodory’s Theorem (cf. [7, p. 3]) there are x_{0}, …, x_{n} ∈ A so that x ∈ Co{x_{0}, …, x_{n}}. Thus without loss of generality we may assume that E = Co{x_{0}, …, x_{n}}. Let M := sup_{x∈E} h(x) < ∞ and let ε > 0. Suppose that x = ∑_{k=0}^{n} α_{k}x_{k} ∈ E (with ∑_{k=0}^{n} α_{k} = 1 and α_{k} ≥ 0) and h(x) ≥ M −ε. By reordering the terms if necessary we may assume α_{0} ≤ α_{1} ≤ ⋯ ≤ α_{n}. Note that α_{0} ≤ 1/(n + 1) ≤ 1/2. Let n_{1} be the least integer so that

∑_{k=0}^{n_{1}} α_{k} > \frac{1}{2}.

Then ∑_{k=0}^{n_{1}−1} α_{k} ≤ \frac{1}{2}. Set

s = \frac{1}{2} − ∑_{k=0}^{n_{1}−1} α_{k}, t = α_{n_{1}} − s,

and let

y = 2( ∑_{k=0}^{n_{1}−1} x_{k} + sx_{n_{1}}), z = 2(tx_{n_{1}} + ∑_{n_{1}+1}^{n} α_{k}x_{k}).

Then y ∈ E as ∑_{k=0}^{n_{1}−1} α_{k} + s = \frac{1}{2}. Likewise z ∈ E. In particular y ∈ Co{x_{0}, …, x_{n_{1}}} =: Δ_{1} and z ∈ Co{x_{n_{1}}, …, x_{n}} =: Δ_{2}. Then dim Δ_{1} = n_{1} and dim Δ_{2} = n − n_{1} =: n_{2}. Since α_{0} ≤ 1/2 we have n_{1} ≥ 1.

If n_{1} < n then n_{1}, n_{2} < n and therefore by the induction hypothesis and x = \frac{1}{2}(y + z), we have

M − ε ≤ h(x) ≤ \frac{h(y) + h(z)}{2} + 1 ≤ \frac{κ(n_{1}) + κ(n_{2})}{2} + 1
≤ κ(n_{1} + n_{2}) = κ(n).

Therefore M ≤ κ(n) + ε. This leaves the case n_{1} = n. Then z = x_{n} ∈ A and thus h(z) = 0. Whence

M − ε ≤ h(x) ≤ \frac{h(y) + h(z)}{2} + 1 = \frac{h(y)}{2} + 1 ≤ \frac{M}{2} + 1.

Solve this inequality for M and use 2 ≤ κ(n) to get M ≤ 2(1 + ε) ≤ κ(n)(1 + ε). Combining the inequalities from the two cases and letting ε ↘ 0 implies M ≤ κ(n) and completes the proof.

2.7. Remark. As many of our results will involve κ(n) it is worth giving some sharp bounds on κ(n). To do this extend κ to the positive reals by defining κ(x) = [log_{2} x] + 1 + x/2^{[log_{2} x]}. Then for any integer m we have κ(2^{m}) = m + 2 = log_{2}(2^{m}) + 2. On closed intervals [2^{m}, 2^{m+1}] the function κ(x) is linear. Thus κ(x) is the continuous piecewise linear function on (0, ∞) with knots at x = 2^{m} and with κ(x) = 2 + log_{2}(x) at the knots. As the function 2 + log_{2}(x) is concave this implies κ(x) ≤ 2 + log_{2}(x). On each of the intervals it is a straightforward calculus exercise to find the maximum of (2 + log_{2}(x)) − κ(x) on the interval [2^{m}, 2^{m+1}]. The result is (ln(2)−ln(ln(2))−1)/ ln(2) ≈ .08607133206 (surprisingly this is independent of which interval [2^{m}, 2^{m+1}] we are working on). This leads to the bounds

1.913928 + log_{2}(n) < κ(n) ≤ 2 + log_{2}(n).

2.2. Lower semi-continuity and mean value properties of extremal approximately convex functions. Let K ⊂ R^{n} be a compact convex set and let V be the set of extreme points of K. Let φ: V → R be a function. Then a function h: K → R^{n} has extreme values equal to φ iff h|_{V} = φ. (The terminology is a variant on that used in partial differential equations where the boundary values of a function are often prescribed.) Likewise if f, g: K → R are two functions then f and g have the same extreme values iff they agree on V. If φ: V → R, let B(K, φ) be the set of bounded approximately convex functions h so that h|_{V} ≤ φ on V. Then the extremal approximately convex function with extreme values equal to φ is

E_{K,φ}(x) = sup_{h∈B(K,φ)} h(x). (2.3)

This is the pointwise largest approximately convex function with extreme values ≤ φ on V. While in general we may have E_{K,φ}(v) < φ(v) for some v ∈ V, we will show that if φ is uniformly continuous on V (which will always be the case if V is finite) then E_{K,φ}|_{V} = φ and that E_{K,φ} is lower semi-continuous on K.

Let K ⊂ R^{n} be a compact set with extreme points V. Then for any function h: K → R which is bounded above define Sh by

Sh(x) = \begin{cases}h(x), & x ∈ V; \\ inf\{\frac{h(y) + h(z)}{2} + 1 : \frac{y + z}{2} = x\}, & x ∈ K \ V. \end{cases}

This operator is closely related to approximately convex functions as

(2.4) f ≤ Sf ⟺ f is approximately convex on K.

Despite being nonlinear S is somewhat like a mean value operator. We make this more precise by proving a maximum principle for the equation Sf = f.

2.8. Theorem. Let K ⊂ R^{n} be a compact convex set with extreme points V. Let f, F: K → R be bounded functions so that Sf ≤ f and F is approximately convex (that is SF ≥ F). Let

(2.5) L(x) = min{f(x), lim inf_{y→x} f(y)}

be the lower semi-continuous envelope of f. Then

sup_{x∈K}(F (x) − f(x)) = sup_{v∈V}(F (v) − f(v)) (2.6)

and

sup_{x∈K}(F (x) − L(x)) = sup_{v∈V}(F (v) − L(v)). (2.7)

Proof. We will prove (2.7), the proof of (2.6) being similar (and a little easier). The inequality Sf ≤ f implies that if x ∉ V then

f(x) ≥ inf\{\frac{f(y) + f(z)}{2} + 1 : \frac{y + z}{2} = x\}. (2.8)

As f and F are bounded we may assume (after possibly adding positive constants to f and F) that 0 ≤ f ≤ F ≤ M for some positive constant M. This implies 0 ≤ L ≤ F. Set ω(x) := F (x) − L(x) and δ := sup_{x∈K} ω(x). Then we wish to show sup_{v∈V} ω(v) = δ. If δ = 0 then L ≡ F and there is nothing to prove. So assume δ > 0. Choose a positive integer N so that N > M. Let 0 < ε < 1 and choose w_{0} to be a point so that ω(w_{0}) > (1 − ε2^{−N})δ. Suppose that w_{0} ∉ V for sufficiently small ε > 0 (otherwise the desired conclusion follows as ε → 0). From the definition of L there is a sequence ⟨x_{k}⟩_{k=1}^{∞} such that x_{k} → w_{0} and f(x_{k}) → L(w_{0}). By equation (2.8) there are sequences ⟨y_{k}⟩_{k=1}^{∞} and ⟨z_{k}⟩_{k=1}^{∞} such that x_{k} = (y_{k} + z_{k})/2 and a real number C ≥ 0 such that

f(x_{k}) − (\frac{f(y_{k}) + f(z_{k})}{2} + 1) → C ≥ 0 (2.9)

By passing to a subsequence we may assume that y_{k} → y, z_{k} → z, f(y_{k}) → A, and f(z_{k}) → B for some y, z ∈ K and A, B ∈ R. Clearly w_{0} = (y + z)/2 and (using the definition of L) L(y) ≤ A, L(z) ≤ B. Then (2.9) yields

L(w_{0}) = \frac{A + B}{2} + 1 + C ≥ \frac{L(y) + L(z)}{2} + 1 (2.10)

and so

F (w_{0}) = L(w_{0}) + ω(w_{0}) ≥ \frac{L(y) + L(z)}{2} + 1 + ω(w_{0}). (2.11)

But since F is approximately convex

F (w_{0}) ≤ \frac{F (y) + F (z)}{2} + 1 = \frac{L(y) + L(z)}{2} + 1 + \frac{ω(y) + ω(z)}{2}. (2.12)

Combining (2.12) and (2.11) yields

\frac{ω(y) + ω(z)}{2} ≥ ω(w_{0}). (2.13)

Since δ = sup_{x∈K} ω(x) and ω(w_{0}) ≥ (1 − ε2^{−N})δ, (2.13) implies

min{ω(y), ω(z)} ≥ 2ω(w_{0}) − δ ≥ (2(1 − ε2^{−N}) − 1)δ = (1 − ε2^{−(N−1)})δ.

From (2.10) have min{L(y), L(z)} ≤ L(w_{0}) − 1. Without loss of generality we may assume that L(y) ≤ L(w_{0})−1. Let w_{1} = y. Then L(w_{1}) ≤ L(w_{0})−1 and ω(w_{1}) ≥ (1 − ε2^{−(N−1)}).

If w_{1} ∉ V then we can repeat this argument (with N replaced by N − 1) and get a w_{2} ∈ K with L(w_{2}) ≤ L(w_{1}) − 1 and ω(w_{1}) ≥ (1 − ε2^{N−2})δ. We continue in this manner to get a finite sequence w_{0}, w_{1}, …, w_{m} with m < N so that for 1 ≤ k ≤ m − 1 we have L(w_{k}) ≤ L(w_{k−1}) − 1, ω(w_{k}) ≥ (1 − ε2^{N−k})δ, and w_{k} ∉ V. (Note this can not continue for k ≥ N as that would imply L(w_{N}) ≤ L(w_{0}) − N ≤ M − N < 0 contradicting L ≥ 0. Thus w_{m} ∈ V for some m < N.) At the last step w_{m} ∈ V and ω(w_{m}) ≥ (1 − ε2^{−(N−m)})δ. Therefore sup_{v∈V} ω(v) ≥ (1 − ε2^{−(N−m)})δ. Letting ε ↘ 0 yields sup_{v∈V} ω(v) ≥ δ. But sup_{v∈V} ω(v) ≤ δ is clear. Thus sup_{v∈V} ω(v) = δ as required.

2.9. Proposition. Let K ⊂ R^{n} be a compact convex set with extreme points V and let h: K → R^{n} be a bounded approximately convex function on K. Then h(x) ≤ Sh(x), the functions h and Sh have the same extreme values, Sh is approximately convex, and if h is lower semi-continuous as a function on K at points of V then the same is true of Sh.

Proof. If x = (y + z)/2 then as h is approximately convex h(x) ≤ (h(y) + h(z))/2 + 1 and taking the infimum yields h(x) ≤ Sh(x). That h and Sh have the same extreme values is clear. Using the definition of Sh and the inequality h ≤ Sh we have

Sh(\frac{y + z}{2} ) ≤ \frac{h(y) + h(z)}{2} + 1 ≤ \frac{Sh(y) + Sh(z)}{2} + 1,

which shows Sh is approximately convex. Finally if h is lower semi-continuous at points of V then for x ∈ V we have lim inf_{y→x} Sh(y) ≥ lim inf_{y→x} h(y) ≥ h(x) = Sh(x). This shows Sh is lower semi-continuous at x and completes the proof.

We now characterize the extremal functions E_{K,φ} as the unique bounded solutions to the equation Sf = f with extreme values φ.

2.10. Theorem. Let K be a convex set with extreme points V and f: K → R a bounded function so that Sf = f. Let φ := f|_{V} be the extreme values of f and let E_{K,φ} be the extremal approximately convex function with extreme values φ. Then f = E_{K,φ}.

Proof. The equality Sf = f implies f is approximately convex (cf. (2.4)). Then the extremal property of E_{K,φ} implies f ≤ E_{K,φ}. Let F = E_{K,φ} in Theorem 2.8 and using that f and E_{K,φ} agree on V we can use equation (2.6) to conclude f = E_{K,φ}.

The following is an elementary variant on Corollary 17.2.1 in [6]. We include a short proof for completeness.

2.11. Proposition. Assume K ⊂ R^{n} is a compact convex set and V the set of extreme points of K. Let φ: V → R be uniformly continuous. Then there exists a lower semi-continuous convex function h: K → R so that h|_{V} = φ. Moreover we can choose h so that inf_{x∈K} h(x) = inf_{v∈V} φ(v) and sup_{x∈K} h(x) = sup_{v∈V} φ(v).

Proof. Let \overline{V} be the closure of V. As φ: V → R is uniformly continuous it has a unique continuous extension \overline{φ}: \overline{V} → R. Let Let G\overline{φ} := \{(x, \overline{φ}(x)) : x ∈ \overline{V} \} ⊂ K × R be the graph of \overline{φ}. As the set \overline{V} is a compact and \overline{φ} is continuous the set G\overline{φ} is also compact. Therefore the convex hull Co(G\overline{φ}) is compact. Let A := inf_{v∈V} φ(v) = min_{x∈\overline{V}} \overline{φ}(x) and B := sup_{v∈V} φ(v) = max_{x∈\overline{V}} \overline{φ}(x). Then Co(G\overline{φ}) ⊆ K × [A, B]. Moreover, as K is the convex hull of its set of extreme points V, if x ∈ K then there is y ∈ [A, B] so that (x, y) ∈ Co(G_{φ}). Define h by

h(x) := min\{y : (x, y) ∈ Co(G\overline{φ})\}.

It is clear from this definition that h is convex and has the same supremum and infimum as φ. We now show that h is lower semi-continuous. Let a ∈ K and let A := lim inf_{x→a} f(x). Choose a sequence ⟨x_{ℓ}⟩_{ℓ=1}^{∞} so that x_{ℓ} → a and h(x_{ℓ}) → A. Then as Co(G\overline{φ}) is compact (and thus closed) the limit lim_{ℓ→∞}(x_{ℓ}, h(x_{ℓ})) = (a, A) ∈ Co(G\overline{φ}). The definition of h then implies h(a) ≤ A = lim inf_{x→a} h(x). Thus h is lower semi-continuous at a for every a ∈ A.

Finally let v ∈ V. Then as (v, h(v)) ∈ Co(G\overline{φ}) there exists (α_{0}, …, α_{n+1}) ∈ Δ_{n+1} and v_{0}, …, v_{n+1} ∈ \overline{V} so that (v, h(v)) = ∑_{k=0}^{n} α_{k}(v_{k}, \overline{φ}(v_{k})). But v is an extreme point of K, which implies that v_{k} = v for all k and therefore h(v) = \overline{φ}(v) = φ(v).

2.12. Theorem. Let K ⊆ R^{n} be a compact convex set with extreme points V. Assume that φ: V → R is uniformly continuous. Then the extremal approximately convex function E_{K,φ} satisfies E_{K,φ}|_{V} = φ and is lower semicontinuous on K.

Proof. By Proposition 2.11 there exists a lower semi-continuous convex function h: K → R with extreme values φ. As h is convex it is a fortiori approximately convex. h approximately convex (so that h ≤ E_{K,φ}) we have for v ∈ V that φ(v) = h(v) ≤ E_{K,φ}(v) ≤ φ(v), and so E_{K,φ} has φ as extreme values. As h ≤ E_{K,φ} and h is lower semi-continuous, the function E_{K,φ} will be lower semi-continuous at all points x where E_{K,φ}(x) = h(x). In particular, E_{K,φ} will be lower semi-continuous at all points of V. Finally as SE_{K,φ} ≥ E_{K,φ} (cf. 2.9) the extremal property of E_{K,φ} implies SE_{K,φ} = E_{K,φ}. Now in Theorem 2.8 let f = F = E_{K,φ} and let L be the lower semi-continuous envelope of f = E_{K,φ} as given by (2.5). Then as E_{K,φ} is lower semi-continuous at points of V we have that E_{K,φ}(v) = L(v) for all v ∈ V. Therefore (2.7) implies that E_{K,φ} = L on K, so that E_{K,φ} is lower semi-continuous as claimed.

2.13. Remark. Let K ⊂ R^{n} be a convex set with extreme points V. Let h: K → R be a bounded approximately convex function and let φ: V → R be the extreme values of h, that is φ := h|_{V}. Then there is a bounded function f: K → R such that f|_{V} = φ for which the inequality Sf ≤ f holds pointwise on K. (Such a function exists as is seen by letting f = E_{K,φ}. On the simplex Δ_{n} with φ = 0 the function f(x) = k for x in the interior of a k-dimensional face is an example of such a function.) Then define two sequences ⟨h_{k}⟩_{k=0}^{∞} and ⟨f_{k}⟩_{k=0}^{∞} of functions on K by

h_{0} = h, h_{k+1} = Sh_{k}, f_{0} = f, f_{k+1} = Sf_{k}.

Then it can be shown that f_{k+1} ≤ f_{k}, h_{k+1} ≥ h_{k}, and that each h_{k} is approximately convex. (The statements about h_{k} follow from Proposition 2.9.) Also all the h_{k}’s and f_{k}’s have φ as extreme values. Therefore both sequences have pointwise limits h_{∞} = lim_{k→∞} h_{k} and f_{∞} = lim_{k→∞} f_{k}. These both have φ as extreme values, Sh_{∞} = h_{∞}, and Sf_{∞} = f_{∞}. Therefore by Theorem 2.10 we have h_{∞} = f_{∞} = E_{K,φ}. This gives a method for finding E_{K,φ} as the limit of two more or less constructively defined sequences. Also note that for each k we have the inequalities

h_{k} ≤ E_{K,φ} ≤ f_{k}.

Thus we have explicit upper and lower bounds for E_{K,φ}.

2.3. The extremal approximately sub-affine function H(x). A function f: [0, 1] → R is approximately sub-affine iff

f(\frac{x + y}{2} ) ≤ \frac{f(x) + f(y)}{2} + \frac{x + y}{2} . (2.14)

As in example 2.49 below approximately sub-affine functions can be used to construct approximately convex functions on a simplex. As a first step in explicitly describing the extremal approximately convex function on a simplex we describe the extremal approximately convex function on the unit interval.

Let N = {0, 1, 2, … } be the natural numbers and let D be the dyadic rational numbers in [0, 1]. That is

D :=\{\frac{m}{2^{n}} : m, n ∈ N and 0 ≤ m ≤ 2^{n}\}.

(These play a considerable rôle in what follows.) The numbers in [0, 1]\D will be called the dyadic irrationals. Every dyadic irrational x has a unique binary expansion x = ∑_{i=0}^{∞} x_{i}/2^{i} with x_{i} ∈ {0, 1}. If x ∈ D then there are two binary expansions: the finite expansion x = ∑_{i=0}^{N} x_{i}/2^{i} and, if x_{N} = 1, there is also the infinite expansion x = ∑_{i=0}^{N−1} x_{i}/2^{i} + ∑_{i=N+1}^{∞} 1/2^{i}. Unless stated otherwise we will always use the finite expansion for an element of D, even when we write x = ∑_{i=0}^{∞} x_{i}/2^{i} for notational uniformity. With this understood, define H: [0, 1] → R by

H(x) := ∑_{i=0}^{∞} i\frac{x_{i}}{2^{i}} where x = ∑_{i=0}^{∞} \frac{x_{i}}{2^{i}} . (2.15)

For motivation see Remark 2.20. A graph of H is shown in Figure 1. We now derive another representation of H. Let r: R → R be defined by

r(x) := \begin{cases}0, & 0 ≤ x < 1; \\ 1, & 1 ≤ x < 2, \end{cases}

and extend to R by periodicity: r(x + 2) = r(x). If 0 ≤ x < 1 and x has binary expansion x = ∑_{i=1}^{∞} x_{i}/2^{i}, where x_{i} ∈ {0, 1}, then it is not hard to see that x_{i} = r(2^{i}x) (if x is a dyadic rational we check to see this does give the finite expansion). It follows for 0 ≤ x < 1 that x = ∑_{i=1}^{∞} r(2^{i}x)/2^{i}. More generally if we let {x} = x − [x] be the fractional part of x then as both {x} and ∑_{i=1}^{∞} r(2^{i}x)/2^{i} are periodic with period 1 and {x} = x for 0 ≤ x < 1 we have

\{x\} = ∑_{i=1}^{∞} \frac{r(2^{i}x)}{2^{i}}. (2.16)

If H is extended to R to be periodic, H(x + 1) = H(x), (this is possible as H(0) = H(1) = 0) then the definition of H becomes

H(x) = ∑_{i=1}^{∞} i\frac{r(2^{i}x)}{2^{i}}. (2.17)

Figure 1. Graphs of y = H(x), y = x log_{2}(x), and y = 2x + log_{2}(x) for 0 ≤ x ≤ 1.

2.14. Proposition. Let the function H be extended from [0, 1) to R so that H is periodic: H(x + 1) = H(x). Then H satisfies the functional equation

H(x) = \{x\} + \frac{1}{2}H(2x) (2.18)

and thus H has the series representation

H(x) = ∑_{k=0}^{∞} \frac{\{2^{k}x\}}{2^{k}}. (2.19)

This implies H is lower semi-continuous, continuous at all points of [0, 1]\D and right continuous at all points.

Proof. This is a calculation based on the two series (2.17) and (2.16).

H(x) = ∑_{i=1}^{∞} i\frac{r(2^{i}x)}{2^{i}} = \{x\} + ∑_{i=1}^{∞}(i − 1)\frac{r(2^{i}x)}{2^{i}}

= \{x\} + \frac{1}{2} ∑_{i=2}^{∞}(i − 1)\frac{r(2^{i−1}2x)}{2^{i−1}}

= \{x\} + \frac{1}{2} ∑_{j=1}^{∞} j \frac{r(2^{j}2x)}{2^{j}} = \{x\} + \frac{1}{2}H(2x).

To prove the series representation (2.19) for H(x) observe that an induction using the functional equation (2.18) yields

H(x) = ∑_{k=0}^{m} \frac{\{2^{k}x\}}{2^{k}} + \frac{1}{2^{m+1}} H(2^{m+1}x)

and as 0 ≤ H(x) ≤ ∑_{i=1}^{∞} i/2^{i} = 2 the series converges uniformly to H(x). The functions x ↦ {2^{k}x}/2^{k} are lower semi-continuous and right continuous and hence so are the partial sums S_{n}(x) = ∑_{k=0}^{n} {2^{k}x}/2^{k}. Thus H is the uniform limit of lower semi-continuous and right continuous functions and therefore is lower semi-continuous and right continuous. Finally the functions {2^{k}x}/2^{k} are continuous at all points of [0, 1] \ D. As the series converges uniformly this implies that the sum H is also continuous at these points.

2.15. Remark. The graph of H(x) has an interesting “self-congruence” property. The series (2.19) for H(x) implies for m a positive integer that

H(x + \frac{1}{2^{m}} ) = ∑_{k=0}^{m−1} \frac{1}{2^{k}} (\{2^{k}x + 2^{k−m}\} − \{2^{k}x\}) + H(x) = P_{m}(x) + H(x)

where this defines P_{m}(x). It is not hard to check that the functions ({2^{k}x + 2^{k−m}} − {2^{k}x})/2^{k} are all constant on intervals [i/2^{m}, (i + 1)/2^{m}) and so the same will be true for P_{m}(x). This implies for any i and j that the graph of the restriction H|_{[i/2^{m},(i+1)/2^{m})} is a translation of the graph of H|_{[j/2^{m},(j+1)/2^{m})}. So informally and somewhat imprecisely “the graph of H is locally self congruent at all the scales 1/2^{m}”. If F is the closure of the graph of H|_{[0,1)} then this, and some calculation, can be used to show F can be covered by 2^{m} closed sets of diameter ≤ 4m2^{−m}. Thus for any δ > 0 the Hausdorff δ-dimensional measure of F is ≤ 2^{m}(4m2^{−m})^{δ} and when δ > 1 we have 2^{m}(4m2^{−m})^{δ} → 0 as m → ∞. Therefore the Hausdorff dimension of F is ≤ 1. But as F projects onto the interval [0, 1] its Hausdorff dimension is ≥ 1. Thus F has Hausdorff dimension one. (With a little more work it can be shown the one dimensional Hausdorff measure of F is infinite.) However F is compact, separable, totally disconnected and has no isolated points. Thus F is homeomorphic to the Cantor set and therefore of topological dimension zero. Whence the closure of the graph of F is a “fractal” in the sense that its geometric dimension is greater than its topological dimension.

2.16. Proposition. The function H is approximately sub-affine:

H(\frac{x + y}{2} ) ≤ \frac{H(x) + H(y)}{2} + \frac{x + y}{2} for x, y ∈ [0, 1].

2.17. Lemma. If x = ∑_{i=0}^{N} l_{i}/2^{i} ∈ D with each l_{i} a nonnegative integer, then

H(x) ≤ ∑_{i=0}^{N} i\frac{l_{i}}{2^{i}}

with equality if and only if each l_{i} ∈ {0, 1}.

Proof. If (l_{0}, l_{1}, …, l_{N}) is a finite sequence with ∑_{i=0}^{N} l_{i}/2^{i} ≤ 1 we let λ(l_{0}, …, l_{N}) := ∑_{i=0}^{N} l_{i}. The proof is by induction on m = λ(l_{0}, …, l_{N}). If m = 0 then each l_{i} = 0 and x = H(x) = 0 and the result is trivial. Now assume the inequality holds for all (l_{0}, l_{1}, …, l_{N}) with λ(l_{0}, …, l_{N}) < m. Let k be the least integer such that l_{k} ≥ 2 (if all l_{k} ∈ {0, 1} there is nothing to prove). Note k ≠ 0 as 2/2^{0} = 2. Then

x = ∑_{i=0}^{k−2} \frac{l_{i}}{2^{i}} + \frac{l_{k−1}}{2^{k−1}} + \frac{l_{k}}{2^{k}} + ∑_{i=k+1}^{N} \frac{l_{i}}{2^{i}}

= ∑_{i=0}^{k−2} \frac{l_{i}}{2^{i}} + \frac{l_{k−1} + 1}{2^{k−1}} + \frac{l_{k} − 2}{2^{k}} + ∑_{i=k+1}^{N} \frac{l_{i}}{2^{i}} = ∑_{i=0}^{N} \frac{r_{i}}{2^{i}}

where the last line defines the r_{i} implicitly. Then

λ(r_{0}, …, r_{N}) = λ(l_{0}, …, l_{k−1} + 1, l_{k} − 2, …, l_{N}) = λ(l_{0}, …, l_{N}) − 1 = m − 1.

Thus the induction hypothesis gives

∑_{i=0}^{N} i\frac{l_{i}}{2^{i}} = ∑_{i=0}^{N} i\frac{r_{i}}{2^{i}} + k \frac{2}{2^{k}} − (k − 1)\frac{1}{2^{k−1}}

= ∑_{i=0}^{N} i\frac{r_{i}}{2^{i}} + \frac{k − (k − 1)}{2^{k−1}} > ∑_{i=0}^{N} i\frac{r_{i}}{2^{i}} ≥ H(x).

This gives H(x) < ∑_{i=0}^{N} l_{i}/2^{i} unless l_{i} ∈ {0, 1} for all i. This completes the proof.

Proof of Proposition 2.16. First consider the case x, y ∈ D so that x = ∑_{i=0}^{N} x_{i}/2^{i}, y = ∑_{i=0}^{N} y_{i}/2^{i}. Then by Lemma 2.17

H(\frac{x + y}{2} ) = H( ∑_{i=0}^{N} \frac{x_{i} + y_{i}}{2^{i+1}} ) ≤ ∑_{i=0}^{N}(i + 1)\frac{x_{i} + y_{i}}{2^{i+1}}

= \frac{1}{2}(∑_{i=0}^{N} i\frac{x_{i}}{2^{i}} + ∑_{i=1}^{N} i\frac{y_{i}}{2^{i}} ) + \frac{1}{2}(∑_{i=0}^{N} \frac{x_{i}}{2^{i}} + ∑_{i=1}^{N} \frac{y_{i}}{2^{i}} )

= \frac{H(x) + H(y)}{2} + \frac{x + y}{2}

If x is a dyadic irrational and y ∈ D then we use that by Proposition 2.14 the function H is lower semi-continuous on R and continuous at x. Let x(r) ∈ D so that lim_{r→∞} x(r) = x and so by continuity lim_{r→∞} H(x(r)) = H(x). Thus

H(\frac{x + y}{2} ) ≤ lim inf_{r→∞} H(\frac{x(r) + y}{2} ) ≤ lim_{r→∞} (\frac{H(x(r)) + H(y)}{2} + \frac{x(r) + y}{2} )

= \frac{H(x) + H(y)}{2} + \frac{x + y}{2}

The case where both x and y are dyadic irrationals is handled similarly.

2.18. Proposition. Suppose f is a lower semi-continuous approximately sub-affine function defined on [0, 1] such that f(0) = 0. Then f(x) ≤ H(x)+ f(1)x for all x ∈ [0, 1].

First some preliminaries. If x = ∑_{j=1}^{N} x_{j}/2^{j} ∈ D define the dyadic support of x to be {j ∈ N : x_{j} = 1} and denote it by supp x.

2.19. Lemma. If x, y ∈ D and (supp x) ∩ (supp y) = ∅ then

H(\frac{x + y}{2} ) = \frac{H(x) + H(y)}{2} + \frac{x + y}{2} .

2.20. Remark. This lemma motivated the definition of H. As the proof of Proposition 2.18 makes clear this is the property which implies H is the largest lower semi-continuous approximately sub-affine function on [0, 1]. It also allows one to compute the values of H on D leading to the formula (2.15).

Proof. The condition on the dyadic supports implies that the binary expansion of x + y can be computed by just adding the digits without “carrying”.

Thus for sufficiently large N

H(\frac{x + y}{2} ) = ∑_{j=0}^{N}(j + 1)\frac{x_{j} + y_{y}}{2^{j+1}}

= \frac{1}{2}(∑_{j=0}^{N}(j + 1)\frac{x_{j}}{2^{j}} + ∑_{j=0}^{N}(j + 1)\frac{y_{j}}{2^{j}} ) + \frac{x + y}{2}

= \frac{H(x) + H(y)}{2} + \frac{x + y}{2} .

Proof of Proposition 2.18. If f(x) is replaced by φ(x) := f(x)−f(1)x then φ will also be approximately sub-affine and φ(0) = φ(1) = 0 = H(0) = H(1). We now show by induction on k that if x = m/2^{k} ∈ D then φ(x) ≤ H(x). The base case of k = 0 holds. Now assume that x = m/2^{k} and that the result is true when the denominator of the fraction is a smaller power of 2. We may assume that m is odd. If x ≤ 1/2 let y = 2x = m/2^{k−1}. Then x = (0 + y)/2, φ(y) ≤ H(y) and supp(0) ∩ supp(y) = ∅. Therefore

φ(x) = φ(\frac{0 + y}{2} ) ≤ \frac{φ(0) + φ(y)}{2} + \frac{0 + y}{2}

≤ \frac{H(0) + H(y)}{2} + \frac{0 + y}{2} = H(\frac{0 + y}{2} ) = H(x).

If 1/2 < x < 1 then let y = 2x−1 so that x = (y +1)/2. Then as the dyadic supports of y and 1 are disjoint, a calculation like the one just done shows φ(x) ≤ H(x). Thus φ(x) ≤ H(x) for all x ∈ D. For any other x ∈ [0, 1] \ D choose x_{k} ∈ D with x_{k} → x. By Proposition 2.14 H is continuous at x. Therefore the lower semi-continuity of φ implies

φ(x) ≤ lim inf_{k→∞} φ(x_{k}) ≤ lim_{k→∞} H(x_{k}) = H(x).

Finally φ(x) ≤ H(x) is equivalent to the required inequality for f.

2.21. Proposition. The inequalities

x log_{2}(1/x) ≤ H(x) ≤ 2x + log_{2}(1/x) (2.20)

hold for 0 ≤ x ≤ 1 (cf. Figure 1). See Figure 2

2.22. Lemma. Let φ(x) := x log_{2}(1/x) = −x ln(x)/ ln(2). Then for 0 ≤ t ≤ 1 and x, y ∈ [0, 1]

0 ≤ φ((1 − t)x + tx) − tφ(x) − (1 − t)φ(x) ≤ φ(t)x + φ(1 − t)y.

As φ(1/2) = 1/2 this implies φ is approximately sub-affine on [0, 1].

Proof. The left hand inequality follows from the concavity of φ. To prove the right hand inequality we first assume 0 < x ≤ y ≤ 1. For fixed t and y let

F (x) := φ((1 − t)x + ty) − (1 − t)φ(x) − tφ(y).

Figure 2. Graphs of y = H(x), y = x log_{2}(x), and y = 2x + log_{2}(x) for 0 ≤ x ≤ 1.

Then

F′(x) = \frac{(1 − t)}{ln(2)}(ln(x) − ln((1 − t)x + ty)) ≤ 0.

Therefore F is monotone decreasing and so the maximum of F (x) on [0, y] occurs when x = 0. But

F (0) = φ(ty) − tφ(y) = \frac{−(ty ln(ty) − ty ln(y))}{ln(2)} = \frac{−t ln(t)}{ln(2)} y = φ(t)y.

So for all 0 ≤ x ≤ y and 0 ≤ t ≤ 1

φ((1 − t)x + ty) − tφ(x) − (1 − t)φ(y) ≤ φ(t)y ≤ φ(t)y + φ(1 − t)x

(for the last step note that φ(1 − t)x ≥ 0). A similar argument works in the case y ≤ x (or replace t by (1 − t) in what has been shown).

Proof of Proposition 2.21. As the function φ(x) = x log_{2}(1/x) is approximately sub-affine, vanishes at the endpoints of [0, 1] and is continuous the lower bound of (2.20) follows from Proposition 2.18. To prove the upper bound we use the series (2.19). Let 0 < x < 1. There exists a unique nonnegative integer m so that 2^{m}x < 1 ≤ 2^{m+1}x (i.e. 1/2^{m+1} ≤ x < 1/2^{m}).

Then for 0 ≤ k ≤ m we have {2^{k}x} = 2^{k}x, and thus

H(x) = ∑_{k=0}^{∞} \frac{1}{2^{k}} \{2^{k}x\} ≤ (m + 1)x + ∑_{k=m+1}^{∞} \frac{1}{2^{k}} = (m + 1)x + \frac{1}{2^{m}} .

So to complete the proof it is enough to show

ψ(x) := 2x + x log_{2}(1/x) − ((m + 1)x + \frac{1}{2^{m}} ) = \frac{−x ln(x)}{ln(2)} − (m − 1)x + \frac{1}{2^{m}}

satisfies ψ(x) ≥ 0 for x ∈ [1/2^{m+1}, 1/2^{m}]. But ψ(1/2^{m+1}) = ψ(1/2^{m}) = 0 and ψ′′(x) = −1/(x ln(2)) < 0. So ψ is concave on [1/2^{m+1}, 1/2^{m}] and vanishes at the endpoints which implies ψ ≥ 0 on the interval.

2.4. The extremal approximately convex function E(x) on a simplex. Let e_{0}, …, e_{n} be the standard basis of R^{n+1}. Then the standard simplex is, as usual, Δ_{n} = Co{e_{0}, …, e_{n}}. We will often write points of Δ_{n} in terms of their affine coordinates (x_{0}, …, x_{n}) where x_{k} ≥ 0 and ∑_{k=0}^{n} x_{k} = 1. This corresponds to ∑_{k=0}^{n} x_{k}e_{k}. Define a function E on Δ_{n} as follows:

E(∑_{k=0}^{n} x_{k}e_{k}) = E(x_{0}, …, x_{n}) := ∑_{k=0}^{n} H(x_{k}). (2.21)

2.23. Remark. If μ is a finite measure space and A is a finite algebra of measurable sets with atoms A_{0}, A_{1}, …, A_{n} the entropy of A is − ∑_{k=0}^{n} μ(A_{k}) ln μ(A_{k}). If x ∈ Δ_{n} we can think of x as a measure on {0, 1, , …, n}. If A is the algebra of subsets of {0, 1, , …, n} then its entropy with respect to the measure determined by x is − ∑_{x_{k}}^{n} x_{k} ln x_{k}. By Lemma 2.22 the function x log_{2}(1/x) is approximately sub-affine and so H can be viewed as an extremal version of x log_{2}(1/x). To the extent that H(x) and −x ln(x) can be thought of as analogous functions, E(x) = ∑_{k=0}^{n} H(x_{k}) can be viewed as a “poor man’s” version of the entropy. The inequalities 2.20 make this analogy somewhat precise.

The standard dyadic simplex is

D_{n} := {∑_{k=0}^{n} x_{k}e_{k} : x_{k} ∈ D, ∑_{k=0}^{n} x_{k} = 1}.

Like D ⊂ [0, 1] the set D_{n} will play a large rôle.

2.24. Proposition. The function E is approximately convex and lower semi-continuous on Δ_{n} with E(e_{k}) = 0 for 0 ≤ k ≤ n. The points of continuity of E are the points x = (x_{0}, …, x_{n}) such that all the coordinates x_{k} are dyadic irrationals. Moreover E satisfies the inequalities

∑_{k=0}^{n} x_{k} log_{2}(1/x_{k}) ≤ E(x_{0}e_{0} + ⋯ + x_{n}e_{n}) ≤ 2 + ∑_{k=0}^{n} x_{k} log_{2}(1/x_{k}).

Proof. For x ∈ Δ_{n} the functions x ↦ H(x_{k}) are lower semi-continuous by Proposition 2.14. Thus E will also be lower semi-continuous. Also from Proposition the points of continuity of H are the dyadic irrationals in [0, 1]. This implies the statement about the points of continuity of E. As H is approximately sub-affine we have

E(\frac{x + y}{2} ) = ∑_{k=0}^{n} H(\frac{x_{k} + y_{k}}{2} )

≤ ∑_{k=0}^{n} \frac{H(x_{k}) + H(y_{k})}{2} + ∑_{k=0}^{n} \frac{x_{k} + y_{k}}{2}

= \frac{E(x) + E(y)}{2} + 1

as ∑_{k=0}^{n} x_{k} = ∑_{k=0}^{n} y_{k} = 1. So E is approximately convex as claimed. That E(e_{k}) = 0 follows from H(0) = H(1) = 0. The bounds for E follow from the inequalities (2.20).

It is possible to give an explicit formula for E on the one dimensional simplex.

2.25. Proposition. Let the one dimensional simplex Δ_{1} be identified with [0, 1] in the usual manner (t corresponds to (1 − t)e_{0} + te_{1}). Then

E(t) = \begin{cases}2, & t ∉ D; \\ 2 − \frac{1}{2^{l−1}} , & \frac{m}{2^{l}} ∈ D with m odd. \end{cases} (2.22)

Proof. Set ψ(t) = {t} + {1 − t} = {t} + { − t}. Then by (2.19)

E(t) = H(t) + H(1 − t) = ∑_{k=0}^{∞} \frac{ψ(2^{k}t)}{2^{k}}. (2.23)

But then ψ(t) = 0 for t ∈ Z and ψ(t) = 1 for t ∉ Z. So if t ∉ D we have ψ(2^{k}t) = 1 for all k. If t = m/2^{l} with m odd then ψ(2^{k}t) = 1 for k < l and ψ(2^{k}t) = 0 for k ≥ l. Now the required formula for E(t) follows from the series (2.23).

Unfortunately, in higher dimensions E is not as easy to understand. The graph of E on the two dimensional simplex is shown in Figures 3, 5 and 4.

2.26. Remark. The graph (Figure 3) of E suggests that E has some self similarities. This is indeed the case as we now briefly indicate. For each k ∈ {0, …, n} define a map θ_{k}: Δ_{n} → Δ_{n} by

θ_{k}(x) := \frac{e_{k} + x}{2}

This is the dilation by a factor of 1/2 centered at e_{k} and it maps Δ_{n} onto its subset defined by 1/2 ≤ x_{k} ≤ 1. The functional equation (2.18) for H can be rewritten in the from H(t/2) = \{t/2\} + \frac{1}{2}H(t/2). We leave it as

Figure 3. Graph of z = E(x, y, 1 − x − y) for 0 ≤ x ≤ 1 − y ≤ 1

an exercise for the reader to show this (and H(t + 1/2) = H(t) + 1/2 for 0 < t < 1/2) can be used in the definition of E so show that for any x ∈ Δ_{n} which is not a vertex that

E(θ_{k}(x)) = 1 + \frac{1}{2}E(x).

Thus if on the space Δ_{n}×[0, ∞) a map Θ_{k} is defined by Θ_{k}(x, z) = (θ_{k}(x), 1+ z/2) then the graph of E (with the points over the vertices deleted) is invariant under Θ_{k}. Each Θ_{k} is the dilation by a factor of 1/2 with center (e_{k}, 2). This explains the self similarities of the graph of E.

Our next result implies that the upper bound of Theorem 2.3 is sharp. Recall that a subset of a metric space is a G_{δ} iff it is a countable intersection of open sets.

2.27. Theorem. The function E achieves its maximum value of κ(n) on an uncountable G_{δ} subset of Δ_{n}.

2.28. Remark. The maximum of E does not occur at the center (1/(n + 1), …, 1/(n + 1)) of Δ_{n}. Given the symmetry of the problem this is a little surprising.

Proof. That sup E[Δ_{n}] ≤ κ(n) follows from 2.3. To show the maximum is obtained, let m = [log_{2}(n)] so that n = 2^{m} + r with 0 ≤ r < 2^{m}. Suppose x = (x_{0}, …, x_{n}) ∈ Δ_{n} with each coordinate x_{k} a dyadic irrational. In particular, if x_{k} = ∑_{j=0}^{n} x_{kj}/2^{j} then x_{kj} is zero for infinitely many j and one for infinitely many j. Let M_{j}(x) := #{k : x_{kj} = 1}. We claim that

22 S. J. DILWORTH, RALPH HOWARD, AND JAMES W. ROBERTS

Figure 4. Graph of z = E(x, y, 1 − x − y) for 0 ≤ x ≤ 1 − y ≤ 1 seen from along the x-axis.

E(x) = κ(n) provided each coordinate x_{k} is a dyadic irrational and

M_{j}(x) = \begin{cases}0, & j ≤ m; \\ n − 2r, & j = m + 1; \\ n, & j ≥ m + 2. \end{cases} (2.24)

Let K be the set of all x = (x_{0}, …, x_{n}) that satisfy these two conditions. If x ∈ K, then

∑_{k=0}^{n} x_{k} = ∑_{j=0}^{∞} ∑_{k=0}^{n} \frac{x_{kj}}{2^{j}} = \frac{M_{m+1}}{2^{m+1}} + n ∑_{j=m+2}^{∞} \frac{1}{2^{j}} = \frac{n − 2r}{2^{m+1}} + \frac{n}{2^{m+1}} = \frac{n − r}{2^{m}} = 1

Thus x ∈ Δ_{n} and so K ⊂ Δ_{n}.

To see that K is uncountable (and thus nonempty) let ⟨a_{m+2}, a_{m+3}, …⟩ be a sequence in {0, 1, …, n} such that for every k ∈ {0, 1, …, n}, a_{j} = k for infinitely many j. We let x_{kj} = 0 if j ≤ m and we let x_{k m+1} = 1 for exactly n − r many k. For j ≥ m + 2, let

x_{kj} := \begin{cases}1, & a_{j} ≠ j; \\ 0, & a_{j} = k. \end{cases}

Figure 5. Graph of z = E(x, y, 1 − x − y) for 0 ≤ x ≤ 1 − y ≤ 1 seen from a different view.

Since each sequence ⟨x_{kj}⟩_{j=0}^{∞} has infinitely many zeros and ones, each x_{k} is a dyadic irrational. Thus x = (x_{0}, …, x_{n}) ∈ K. As there are uncountably many such sequences ⟨a_{m+2}, a_{m+3}, …⟩ the set K is uncountable.

If x = (x_{0}, …, x_{n}) ∈ K then, using the definition (2.15) of H and the identity ∑_{j=m+2}^{∞} j/2^{j} = (m + 3)/2^{m+1}, we have

E(x) = ∑_{k=0}^{n} H(x_{k}) = ∑_{j=0}^{∞} \frac{jM_{j}}{2^{j}} = \frac{M_{m+1}(m + 1)}{2^{m+1}} + n ∑_{j=m+2}^{∞} \frac{j}{2^{j}}

= \frac{(n − 2r)(m + 1)}{2^{m+1}} + \frac{n(m + 3)}{2^{m+1}} = \frac{(2n − 2r)(m + 1) + 2n}{2^{m+1}}

= m + 1 + \frac{n}{2^{m}} = κ(n).

This shows that E achieves its maximum at all points of K. Finally {x ∈ Δ_{n} : E(x) = κ(n)} = ⋂_{ℓ=1}^{∞} E^{−1}[(κ(n) − 1/ℓ, ∞)] and each of the sets E^{−1}[(κ(n) − 1/ℓ, ∞)] is open as E is lower semi-continuous. Thus {x ∈ Δ_{n} : E(x) = κ(n)} is a G_{δ}.

2.29. Remark. With a little more work it can be shown that E(x) = κ(n) if and only if x ∈ K with K as above.

Alternate proof of Theorem 2.27. That sup E[Δ_{n}] ≤ κ(n) follows from 2.3. We will now show by induction on the dimension n that there are infinitely many x ∈ Δ_{n} with E(x) = κ(n). As inductive hypothesis we assume that if A ⊂ N is infinite then there exists x = ∑_{k=0}^{n} x_{k}e_{k} ∈ Δ_{n} with E(x) = κ(n) and such that one barycentric coordinate of x, say x_{n}, is a dyadic irrational with supp(x_{n}) ⊆ A. By Proposition 2.25 this is true when n = 1. Suppose that n > 1 and that the inductive hypothesis holds for all positive integers less than n. Then from the recursion (2.2) satisfied by κ there exists an m with 1 ≤ m < n so that κ(n) = (κ(m) + κ(n − m))/2 + 1. Let A ⊂ N be infinite. Without loss of generality we can assume that N \ A is also infinite. Let B := {n − 1 : n ∈ A} and partition B into a disjoint union B = B_{1} ∪ B_{2} of two infinite subsets. As m < n by the induction hypothesis there exists y = ∑_{k=0}^{m} y_{k}e_{k} such that E(y) = κ(m) and such that the coordinate y_{m} is a dyadic irrational with supp y_{m} ⊆ B_{1}. Likewise as n − m < n there exists z = ∑_{k=m}^{n} z_{k}e_{k} such that z_{m} is a dyadic irrational with supp z_{m} ⊆ B_{2}. As the supports of y_{m} and z_{m} are disjoint we have supp(y_{m} +z_{m}) = supp y_{m} ∪supp z_{m} unless y_{m} +z_{m} is a dyadic rational, that is if the binary expansion of y_{m} + z_{m} is all 1’s from some point on. But this is impossible as N \ A is infinite. Thus (y_{m} + z_{m})/2 is a dyadic irrational and that the dyadic supports of y_{m}/2 and z_{m}/2 are disjoint. It then follows from the definition of H that

H(\frac{y_{m} + z_{m}}{2} ) = H(\frac{y_{m}}{2} ) + H(\frac{z_{m}}{2} ).

Let x = (y+z)/2. Then using the functional equation H(t/2) = (H(t)+t)/2 which holds for t ∈ [0, 1) (cf. (2.18)) we have

E(x) = ∑_{k=0}^{m−1} H(\frac{y_{k}}{2} ) + H(\frac{y_{m} + z_{m}}{2} ) + ∑_{k=m+1}^{m} H(\frac{y_{k}}{2} )

= ∑_{k=0}^{m} H(\frac{y_{k}}{2} ) + ∑_{k=m}^{n} H(\frac{z_{k}}{2} )

= \frac{1}{2} ∑_{k=0}^{m}(H(y_{k}) + y_{k}) + \frac{1}{2} ∑_{k=m}^{n}(H(z_{k}) + z_{k})

= \frac{1}{2}(∑_{k=0}^{m} H(y_{k}) + ∑_{k=m}^{n} H(z_{k})) + 1

= \frac{E(y) + E(z)}{2} + 1 = \frac{κ(m) + κ(n − m)}{2} + 1 = κ(n).

Finally note that (z_{m}+y_{m})/2 is a dyadic irrational with supp((z_{m}+y_{m})/2) = supp(y_{m}/2) ∪ supp(z_{m}/2) ⊆ A . This closes the induction and completes the proof.

2.30. Theorem. The function E is the largest bounded approximately convex function on Δ_{n} that vanishes on the vertices. More precisely, if h is any bounded approximately convex function on Δ_{n} with h(e_{k}) ≤ 0 for k = 0, 1, …, n, then h ≤ E on Δ_{n}.

2.31. Corollary. Let h: Δ_{n} → R be an approximately convex function that is Borel measurable. Then for any x = ∑_{k=0}^{n} x_{k}e_{k} the inequality

h(x) ≤ κ(n) + ∑_{k=0}^{n} x_{k}h(e_{k})

holds. In particular, if h(e_{k}) ≤ 0 for all k, then h ≤ κ(n).

Proof of Corollary 2.31. Define l on Δ_{n} by l(x) = ∑_{k=0}^{n} x_{k}h(e_{k}). Then the function h(x)−l(x) is approximately convex, Borel measurable, and vanishes on the vertices of Δ_{n}. So by replacing h by h − l we may assume h vanishes on the vertices of Δ_{n} it will be enough to show h ≤ κ(n) on Δ_{n}. We do this by induction on n. For n = 1 it follows from results of Ng and Nikodem [5, Cor. 1 and Thm 2] that h is bounded above. (Or use Lemma 2.46 below.) But then h ≤ κ(1) = 2 by Theorem 2.3. Now let n ≥ 2 and assume the result holds for all simplices with dimension < n. Consider Δ_{n−1} as a face of Δ_{n} in the natural way (Δ_{n−1} = Co{e_{0}, …, e_{n−1}} ⊂ Co{e_{0}, …, e_{n}}). Then by the induction hypothesis h|_{Δ_{n−1}} ≤ κ(n − 1). Now any point x ∈ Δ_{n} has a representation as x = (1 − t)e_{n} + ty where y ∈ Δ_{n−1} and t ∈ [0, 1]. But then the one dimensional result (applied to the restriction of h to the segment between e_{0} and y where we note that this restriction is Borel and thus Lebesgue measurable) implies

h(x) = h((1 − t)e_{n} + ty) ≤ 2 + (1 − 2)h(e_{n}) + th(y)
≤ 2 + 0 + tκ(n − 1) ≤ 2 + κ(n − 1).

Thus h is bounded above on Δ_{n}. But then we can use Theorem 2.3 and reduce the bound to κ(n). This completes the proof.

2.32. Corollary. Let U ⊆ R^{n} be a convex set and let h: U → R be either Borel measurable or bounded above on compact subsets of U. Then for any m ≤ n, points x_{0}, …, x_{m} ∈ U and (α_{0}, …, α_{m}) ∈ Δ_{m}, we have

h(α_{0}x_{0} + ⋯ + α_{m}x_{m}) ≤ E(α_{0}, …, α_{m}) + α_{0}h(x_{0}) + ⋯ + α_{m}h(x_{m})
≤ κ(m) + α_{0}h(x_{0}) + ⋯ + α_{m}h(x_{m}).

Proof. Define f: Δ_{m} → R by f(α_{0}, …, α_{m}) := h(α_{0}x_{0} + ⋯ + α_{m}x_{m}) − (α_{0}h(x_{0}) + ⋯ + α_{m}h(x_{m})). Then f is approximately convex and bounded above on Δ_{m} or is Borel measurable on Δ_{m}. As f vanishes on the vertices of Δ_{m} either Theorem 2.30 or Corollary 2.41 implies f ≤ E ≤ κ(m) on Δ_{m}. This is equivalent to the conclusion of the corollary.

We start the proof of Theorem 2.30 by extending the idea of the dyadic support from D to D_{n}. If x = ∑_{k=0}^{n} (∑_{j=0}^{N} x(j, k)/2^{j}) e_{k} ∈ D_{n} (here x(j, k) ∈ {0, 1}) then set

supp x := {(j, k) : x(j, k) = 1}. (2.25)

The following is trivial to prove using Lemma 2.19 and the definition of E in terms of H.

2.33. Lemma. If x, y ∈ D_{n} and (supp x) ∩ (supp y) = ∅ then

E(\frac{x + y}{2} ) = \frac{E(x) + E(y)}{2} + 1.

2.34. Lemma. If x ∈ D_{n} and x ∉ {e_{0}, …, e_{n}}, then there are y, z ∈ D_{n} so that x = (y + z)/2 and (supp y) ∩ (supp z) = ∅.

Proof. Letting x = ∑_{k=0}^{n} (∑_{j=0}^{N} x(j, k)/2^{k}) e_{k} It suffices to show that there are nonempty sets A, B so that A ∩ B = ∅ and

∑_{(j,k)∈A} \frac{x(k, j)}{2^{j}} = \frac{1}{2} = ∑_{(j,k)∈B} \frac{x(k, j)}{2^{j}}.

For then if a = ∑_{(j,k)∈A} x(k, j)/2^{j−1}e_{k} and b = ∑_{(j,k)∈B} x(k, j)/2^{j−1}e_{k} we have a, b ∈ D_{n}, (supp a) ∩ (supp b) = ∅ and x = (a + b)/2.

We first prove by induction on ∑_{j=1}^{N} a_{j} that if a_{1}, …, a_{N} are positive integers so that ∑_{j=1}^{N} a_{j}/2^{j} = 1 then there are b_{j}, c_{j} ∈ N such that ∑_{j=1}^{N} b_{j}/2^{j} = ∑_{j=1}^{N} c_{j}/2^{j} = 1/2. Note that a_{N} is even (otherwise 2^{−N} ∑_{j=1}^{N} 2^{N−j}a_{j} would not sum to 1) and so a_{N} − 2 ≥ 0. Therefore

∑_{j=1}^{N−2} \frac{a_{j}}{2^{j}} + \frac{a_{N−1} + 1}{2^{N−1}} + \frac{a_{N} − 2}{2^{N}} = 1.

Since ∑_{j=1}^{N−2} +(a_{N−1} + 1) + (a_{N} − 2) = ∑_{j=1}^{N} a_{j} − 1 we may apply the induction hypothesis, which yields the claim.

Now let x ∈ D_{n} be as above. Let a_{j} := #{k : x(j, k) = 1}. Then ∑_{j=1}^{N} a_{j}/2^{j} = 1. Therefore we have a_{j} = b_{j} + c_{j} as above. Then splitting each of the sets {k : x(j, k) = 1} into two disjoint sets A_{j} and B_{j} with #(A_{j}) = b_{j} and #(B_{j}) = c_{j} we let A := ∪_{j=1}^{N}A_{j} and B := ∪_{j=1}^{N}B_{j}. This completes the proof.

2.35. Proposition. Let h be any approximately convex function on Δ_{n} (not necessarily bounded above) such that h(e_{k}) ≤ 0 for 0 ≤ k ≤ n. Then h(x) ≤ E(x) for all x ∈ D_{n}.

Proof. The proof is by induction on m = #(supp x). If m = 1 then x = e_{k} for some k and h(e_{k}) ≤ 0 = E(e_{k}). Now assume that h(x) ≤ E(x) for all x with #(supp x) ≤ m − 1 and let supp x = m. By Lemma 2.34 we can write x = (y +z)/2 with #(supp y), #(supp z) ≤ m−1. Using the induction hypothesis and Lemma 2.33

h(x) = h(\frac{y + z}{2} ) ≤ \frac{h(y) + h(z)}{2} + 1 ≤ \frac{E(y) + E(z)}{2} + 1 = E(x).

The following lets us pass from knowing inequalities for E on D_{n} to proving them on Δ_{n}.

2.36. Lemma. If x ∈ Δ_{n} then there is a sequence ⟨x(r)⟩_{r=1}^{∞} from D_{n} so that lim_{r→∞} x(r) = x and lim_{r→∞} E(x(r)) = E(x).

Proof. Write x = ∑_{k=0}^{n} x_{k}e_{k}. By reordering we can assume for some ℓ ∈ {0, …, n} that x_{k} ∈ D for 0 ≤ k ≤ ℓ and x_{k} ∉ D for ℓ + 1 ≤ k ≤ n. For 0 ≤ k ≤ ℓ set x_{k}(r) = x_{k} for all r. As ∑_{k=0}^{n} x_{k} = 1 and ∑_{k=0}^{ℓ} x_{k} ∈ D (as x_{k} ∈ D for each x_{k} in this sum) the sum δ := ∑_{k=ℓ+1}^{n} x_{k} = 1−∑_{k=0}^{ℓ} x_{k} will also be a dyadic rational. Let Δ_{n−ℓ−1}(δ) = {∑_{k=ℓ+1}^{n} α_{k}e_{k} : α_{k} ≥ 0, ∑_{k=ℓ+1}^{n} α_{k} = δ} and D_{n−ℓ−1}(δ) = {∑_{k=ℓ+1}^{n} α_{k}e_{k} : α_{k} ∈ D, ∑_{k=ℓ+1}^{n} α_{k} = δ}. Then D_{n−ℓ−1}(δ) will be dense in Δ_{n−ℓ−1}(δ) so there is a sequence y(r) = ∑_{k=ℓ+1}^{n} y_{k}(r)e_{k} with lim_{r→∞} y(r) = y. Set x_{k}(r) = y_{k}(r) for ℓ+1 ≤ k ≤ n. Then x_{k}(r) = x_{k} ∈ D for 0 ≤ k ≤ ℓ and lim_{r→∞} x_{k}(r) = x_{k} ∉ D for ℓ + 1 ≤ k ≤ n. Set x(r) = ∑_{k=0}^{n} x_{k}(r)e_{k}. Then x(r) ∈ D_{n} and lim_{r→∞} x(r) = x. We now use the definition of E in terms of H and the fact that H is continuous at all dyadic irrationals (Proposition 2.14) to obtain

lim_{r→∞} E(x(r)) = ∑_{k=0}^{ℓ} H(x_{k}) + lim_{r→∞} ∑_{k=ℓ+1}^{n} H(x_{k}(r)) = ∑_{k=0}^{n} H(x_{k}) = E(x).

Proof of Theorem 2.30. Let E_{Δ_{n},0} extremal approximately convex function on Δ_{n} that takes the values 0 on the vertices (cf. (2.3)). We wish to show E = E_{Δ_{n},0}. The inequality E ≤ E_{Δ_{n},0} follows from the definition of E_{Δ_{n},0}, so it is enough to prove E_{Δ_{n},0} ≤ E. By Lemma 2.36 there is a sequence x(r) ∈ D_{n} such that lim_{r→∞} x(r) = x and lim_{r→∞} E(x(r)) = E(x). By Lemma 2.35 E_{Δ_{n},0}(x(r)) ≤ E(x(r)). By Theorem 2.12 the function E_{Δ_{n},0} is lower semi-continuous. Therefore

E_{Δ_{n},0}(x) ≤ lim inf_{r→∞} E_{Δ_{n},0}(x(r)) ≤ lim_{r→∞} E(x(r)) = E(x).

2.5. Extremal approximately convex functions on convex polytopes. Let K ⊂ R^{n} be a compact convex set with extreme points V and let φ: V → R be bounded. In §2.2 we defined the extremal approximately convex function E_{K,φ} with extreme values φ but without being explicit about how to compute it. In §2.4 we gave a very explicit description of E = E_{Δ_{n},0}, the extremal approximately convex function on the simplex. Here we show that when K is a polytope (that is the convex hull of a finite number of points) then E_{K,φ} can be expressed directly in terms of E_{Δ_{m},0} for some m. We first establish some elementary properties of approximately convex functions under affine maps.

2.37. Proposition. Let A ⊂ R^{m} and B ⊂ R^{n} be convex sets and T: R^{m} → R^{n} an affine map.

1. If T [A] ⊆ B and f is an approximately convex function on B then T^{∗}f(x) := f(T (x)) is an approximately convex function on A.

2. If T [A] ⊇ B and h is an approximately convex function on A which is bounded from below then T_{∗}h(y) := inf_{T (x)=y} h(x) is approximately convex on B.

3. Both T^{∗} and T_{∗} are order preserving. That is f_{1} ≤ f_{2} and h_{1} ≤ h_{2} pointwise implies T^{∗}f_{1} ≤ T^{∗}f_{2} and T_{∗}h_{1} ≤ T_{∗}h_{2} pointwise.

4. If T [A] = B, h is approximately convex and bounded below on A and f is approximately convex and bounded below on B, then T^{∗}T_{∗}h ≤ h and T_{∗}T^{∗}f = f.

Proof. This is just a chase through the definitions of T^{∗} and T_{∗}.

Let K be a convex polytope in R^{n} with extreme points V = {v_{0}, …, v_{m}} and extreme values given by φ: V → R. and let a_{0}, …, a_{m} be real numbers. We wish to find the largest approximately convex function F on K so that F (v_{k}) = φ(v_{k}) for 0 ≤ k ≤ m. Toward this end let E = E_{Δ_{m},0} be the extremal approximately convex function on the simplex Δ_{m} and define E_{Δ_{m},φ} on Δ_{M} by

E_{Δ_{m},φ}(x) = E_{Δ_{m},φ}(x_{0}, …, x_{m}) := E_{Δ_{m},0}(x_{0}, …, x_{m}) + ∑_{k=0}^{m} x_{k}φ(a_{k}).

(This is a slight misuse of notation as φ is a function on the extreme points V of K rather than the set of extreme points {e_{0}, …, e_{m}} of Δ_{m}.) Then, as x ↦ ∑_{k=0}^{m} x_{k}a_{k} is affine, the function E_{Δ_{m},φ} is approximately convex on Δ_{m} and satisfies E_{Δ_{m},φ}(e_{k}) = φ(v_{k}). Moreover E_{Δ_{m},φ} is the extremal approximately convex function on Δ_{m} taking on these values on the vertices in the sense that if f: Δ_{m} → R is approximately convex and bounded above, lower semi-continuous, and f(e_{k}) ≤ φ(v_{k}) then f(x) ≤ E_{Δ_{m},φ}(x) for all x ∈ Δ_{m}.

Returning to our extremal problem there is a unique affine map T: Δ_{m} → K such that T (e_{k}) = v_{k} for 0 ≤ k ≤ m. Then T [Δ_{m}] = K. Define F_{K,}: K → R by

F_{K,φ} := T_{∗}E_{Δ_{m},φ}.

Then another definition chase shows F_{K,φ}(v_{k}) = a_{k}.

2.38. Theorem. Using the notation above, the extremal approximately continuous function on the polytope K with extreme values φ is

E_{K,φ} := T_{∗}E_{Δ_{0},φ}.

The function E_{K,φ} is lower semi-continuous.

Proof. Let f: K → R be approximately convex, bounded, and and satisfy f(v_{k}) ≤ φ(v_{k}). Then the function T^{∗}f on Δ_{m} is approximately convex, bounded, and T^{∗}f(e_{k}) = f(v_{k}) ≤ φ(v_{k}). Therefore T^{∗}f ≤ E_{Δ_{m},φ}. But then f = T_{∗}T^{∗}f ≤ T_{∗}E_{Δ_{m},φ} which proves T_{∗}E_{Δ_{m},φ} = E_{K,φ}. The lower semi-continuity of E_{K,φ} follows from Theorem 2.12.

2.6. A stability theorem of Hyers-Ulam type. Here we give a stability result for approximately convex functions related to and motivated by a theorem of Hyers and Ulam [4]. The idea is that an approximately convex function is close (in the uniform norm) to some convex function.

2.39. Theorem. Assume that U ⫅ R^{n} is convex, ε > 0, and that f: U → R is bounded above on compact sets and satisfies

f(\frac{x + y}{2} ) ≤ \frac{f(x) + f(y)}{2} + ε. (2.26)

Then there exist convex functions g, g_{0} : U → R such that

f(x) ≤ g(x) ≤ f(x) + κ(n)ε and |f(x) − g_{0}(x)| ≤ \frac{κ(n)}{2}ε (2.27)

for all x ∈ U. The constant κ(n) is the best possible constant in these inequalities.

Proof. By replacing f by ε^{−1}f we may assume ε = 1 so that f is approximately convex. Following Hyers and Ulam [4, p. 823] or Cholewa [2, pp. 81– 82] set W := {(x, y) ∈ R^{n} × R : y ≥ f(x)} and define g by

g(x) := inf{y : (x, y) ∈ Co(W)}.

We now show that g does not take on the value −∞. If (x, y) ∈ Co(W) then by Carathéodory’s Theorem there exist n+2 points (x_{0}, y_{0}), …, (x_{n+1}, y_{n+1}) ∈ W and (α_{0}, …, α_{n}) ∈ Δ_{n+1} such that (x, y) = ∑_{k=0}^{n+1} α_{k}(x_{k}, y_{k}). Therefore by Corollary 2.32

f(x) = f(∑_{k=0}^{n+1} α_{k}x_{k}) ≤ κ(n + 1) + ∑_{k=0}^{n+1} α_{k}f(x_{k})

≤ κ(n + 1) + ∑_{k=0}^{n+1} α_{k}y_{k} = κ(n + 1) + y.

Thus y ≥ f(x) − κ(n + 1) which implies g(x) ≥ f(x) − κ(n + 1) > −∞.

¿From the definition it is clear that g(x) ≤ f(x) and that g(x) is convex. To see that f(x) ≤ g(x) + κ(n) let δ > 0 and choose y so that (x, y) ∈ Co(W) and y < g(x) + δ. Then as above there are n + 2 points (x_{0}, y_{0}), …, (x_{n+1}, y_{n+1}) ∈ W with (x, y) ∈ W and such that (x, y) ∈ Δ := Co(\{(x_{0}, y_{0}), …, (x_{n+1}, y_{n+1})\}). Let \overline{y} := min\{η : (x, η) ∈ Δ\}. Then (x, \overline{y}) is on the boundary of Δ and so it is a convex combination of n + 1 of the points (x_{0}, y_{0}), …, (x_{n+1}, y_{n+1}), say (x, \overline{y}) = ∑_{k=0}^{n} α_{k}(x_{k}, y_{k}) with (α_{0}, …, α_{n}) ∈ Δ_{n}. Then a calculation like one showing that g(x) > −∞ (but with n+1 replacing n+2) yields that f(x) ≤ \overline{y}+κ(n) ≤ g(x)+δ+κ(n). As δ > 0 was arbitrary this implies f(x) ≤ g(x) + κ(n).

Letting g_{0}(x) = g(x) + κ(n)/2 we have |f(x) − g_{0}(x)| ≤ κ(n)/2.

Finally to see that the constants in question are sharp consider the almost convex function E: Δ_{n} → R which has max E = κ(n). Then the largest convex function g on Δ_{n} with g ≤ E is g(x) ≡ 0. Likewise g_{0}(x) ≡ κ(n)/2 has |E(x) − g_{0}(x)| ≤ κ(n)/2 and no other convex function on Δ_{n} gives a better estimate.

2.7. Measurable approximately convex functions. In this section we show the boundedness assumption on the approximately convex function h can be relaxed if we assume even minimal regularity on h. Basicly all the results in this section are in the paper [5] of Ng and Nikodem. We will denote by L^{n} the Lebesgue measure on R^{n}. A function f: R^{n} → R is Borel measurable iff for any open set V ⊂ R the preimage f^{−1}[V] is a Borel set in R^{n}.

2.40. Theorem. Let U be an open convex set and let h: U → R be an approximately convex function that is Lebesgue measurable. Then h is bounded from above and below on any compact subset of U.

2.41. Theorem. Let h: Δ_{n} → R be an approximately convex function that is Borel measurable. Then for any x = ∑_{k=0}^{n} x_{k}e_{k} the inequality

h(x) ≤ κ(n) + ∑_{k=0}^{n} x_{k}h(e_{k})

In particular, if h(e_{k}) ≤ 0 for all k, then h ≤ κ(n).

2.42. Remark. In Theorem 2.40 it is not possible to conclude that h is bounded on U. As a one dimensional example let h(x) = 1/(1 − x^{2}) which is approximately convex (in fact convex) on (−1, 1), but which becomes unbounded near the boundary. More generally given a nonempty convex open set U in R^{n} there is a smooth convex function defined on U that becomes unbounded near every boundary points of U.

2.43. Remark. Theorem 2.41 becomes false if “Borel measurable” is weakened to “Lebesgue measurable”. See Example 2.52

2.44. Remark. Let h: R^{n} → R satisfy Cauchy’s functional equation h(x + y) = h(x) + h(y). Then h is approximately convex. If h is also Lebesgue measurable Theorem 2.40 implies that if \overline{B} is the Euclidean closed unit ball above the origin of R^{n} then h is bounded above on \overline{B} and below. Thus there is a constant C such that ∥x∥ ≤ 1 implies |h(x)| ≤ C. Cauchy’s equation implies h is linear over the rationals. Therefore for any rational number r > 0 we have |h(x) − h(y)| = r|h((x − y)/r)|. Let ε > and assume ∥x − y∥ < ε/C. Then there is a rational number r so that ∥x − y∥ < r < ε/C. This implies ∥(x − y)/r∥ < 1, and so |h(x) − h(y)| = r|h((x − y)/r)| ≤ rC < (ε/C)C = ε. Therefore h is uniformly continuous on R^{n}. But then standard arguments show h is a linear (over R) map. Thus Theorem 2.40 gives a short proof of the well known theorem of Banach that a measurable solution to Cauchy’s equation is linear.

As a generalization if f: R^{n} → X with X a normed linear space (and by replacing X by its completion we can assume X is complete) f(x + y) = f(x) + f(y) and is measurable then for any linear functional λ in the dual space X^{∗} of X the function h: R^{n} → R given by h(x) = λf(x) will be a linear function on R^{n}. From this (and the uniform boundedness principle) it follows f is a linear map.

For any a ∈ R^{n} let

θ_{a}(x) = 2a − x

be the symmetry at a. Note θ_{a}(a) = a, θ_{a} ∘ θ_{a} = Id_{R^{n}} and θ_{a} is an isometry of R^{n}. The latter implies θ_{a} preserves the Lebesgue measure of sets: L^{n}(θ_{a}[A]) = L^{n}(A).

2.45. Lemma. Let B_{r}(a) be the ball of radius r about a. Suppose that A is a measurable set so that if x ∈ B_{r}(a) then A does not contain both x and θ_{a}(x). Then L^{n}(A ∩ B_{r}(a)) ≤ \frac{1}{2}L^{n}(B_{r}(a))

Proof. Be replacing A by A ∩ B_{r}(a) we can assume that A ⊂ B_{r}(a). The condition that A not contain both x and θ_{a}(x) implies that A ∩ θ_{a}[A] = ∅. As A ∪ θ_{a}[A] ⊂ B_{r}(a) this implies L^{n}(B_{r}(a)) ≥ L^{n}(A ∪ θ_{a}[A]) = L^{n}(A) + L^{n}(θ_{a}[A]) = 2L^{n}(A). This completes the proof.

Proof of Theorem 2.40. Let K ⊂ U be compact. We may assume that U has finite measure, for if it does not then replace U by B_{R}(0) ∩ U where R is chosen large enough that K ⊂ B_{R}(0). As K is compact the distance of K to the boundary of U is positive so choose r so that r < dist(K, ∂U). For each k let A_{k} := {x ∈ U : h(x) ≤ k}. Then A_{k} ⊆ A_{k+1} and ⋃_{k=1}^{∞} A_{k} = U. Therefore there is a k so that L^{n}(U \ A_{k}) < \frac{1}{2}L^{n}(B_{r}(0)). Now let a ∈ K. Then B_{r}(a) ⊂ U. And as L^{n}(U \ A_{k}) < \frac{1}{2}L^{n}(B_{r}(0)) we have L^{n}(A_{k} ∩ B_{r}(a)) > \frac{1}{2}L^{n}(B_{r}(a)). By Lemma 2.45 this implies there is an x ∈ B_{r}(a) so that both x and θ_{a}(x) ∈ A_{k}. As x, θ_{a}(x) ∈ A_{k} we have h(x), h(θ_{a}(x)) ≤ k. Also \frac{1}{2}(x + θ_{a}(x)) = \frac{1}{2}(x + (2a − x)) = a. Therefore

h(x) = h(\frac{x + θ_{a}(x)}{2})≤ \frac{h(x) + h(θ_{a}(x))}{2} + 1 ≤ k + 1.

Thus h(x) ≤ k + 1 for all x ∈ K. Therefore h is bounded above all compact subsets of U

Again letting K ⊂ U be compact choose an open set V so that the closure \overline{V} is compact and K ⊂ V ⊂ \overline{V} ⊂ U. Then h is bounded above on \overline{V} and therefore by Proposition 2.2 h is bounded below on K. This completes the proof.

2.46. Lemma. Let h be any approximately convex function on [a, b] then the estimate

h((1 − t)a + tb) ≤ 2 + (1 − t)h(a) + th(b)

holds for all t ∈ D.

Proof. The function f(t) := h((1 − t)a + tb) − (1 − t)h(a) − th(b) is approximately convex and f(a) = f(b) = 0. Then by Proposition 2.35 f((1 − t)a + tb) ≤ E((1 − t)e_{0} + te_{1}) for all t ∈ D. But by Proposition 2.25 E(t) ≤ 2.

2.47. Lemma. Let h: [a, b] → R be an approximately convex function which is also Lebesgue measurable. Then h is bounded from above on [a, b].

Proof. By a change of variable we may assume [a, b] = [0, 1]. By Theorem 2.40 there is a constant C_{1} so that h(x) ≤ C_{1} for all x ∈ [1/4, 3/4]. Let C_{2} := max{C_{1}, h(0), h(1)}. We claim that h(x) ≤ C_{2} + 2 for all x ∈ [0, 1]. When x ∈ [1/4, 3/4] this is clear. If x ∈ [0, 1/4] then either x = 0, when h(x) = h(0) ≤ C_{2}, or there is an integer m ≥ 1 so that y := 2^{m}x ∈ [1/4, 3/4]. Then x = ((1−1/2^{m})0+(1/2^{m})y). Letting t = 1/2^{m} ∈ D we use Lemma 2.46

h(x) = h((1−t)0+ty) ≤ 2+(1−t)h(0)+th(y) ≤ 2+(1−t)C_{2}+tC_{2} = 2+C_{2}.

The same argument shows if x ∈ [3/4, 1] then h(x) ≤ C_{2} + 2. Thus h is bounded above by C_{2} + 2 on all of [0, 1].

2.48. Proposition. Let h: [a, b] → R be an approximately convex function which is also Lebesgue measurable. Then

h(x) ≤ 2 + \frac{(b − x)h(a) + (x − a)h(b)}{b − a}

for all a ∈ [a, b]. (Here 2 is the sharp constant.)

Proof. By Lemma 2.47 h is bounded from above on [a, b]. Let l(x) be the linear function l(x) = ((b − x)h(a) + (x − a)h(b))/(b − a). Let ψ(x) = h(x) − l(x) Then ψ(a) = ψ(b) = 0, ψ is bounded above, and ψ is approximately convex. Thus by Theorem 2.3 we have that ψ(x) ≤ κ(1) = 2. But ψ ≤ 2 is equivalent to the statement of the proposition.

Proof of Theorem 2.41. Define l on Δ_{n} by l(x) = ∑_{k=0}^{n} x_{k}h(e_{k}). Then the function h(x) − l(x) is approximately convex, Borel measurable, and vanish on the vertices of Δ_{n}. So by replacing h by h − l we may assume h vanishes on the vertices of Δ_{n} and it will be enough to show h ≤ κ(n) on Δ_{n}. We do this by induction on n. For n = 1 this follows from Proposition 2.48. Now let n ≥ 2 and assume the result holds for all simplices with dimension < n. Consider Δ_{n−1} as a face of Δ_{n} in the natural way (Δ_{n−1} = Co{e_{0}, …, e_{n−1}} ⊂ Co{e_{0}, …, e_{n}}). Then by the induction hypothesis h|_{Δ_{n−1}} ≤ κ(n − 1). (This is where the hypothesis that h is Borel measurable is used. The restriction h|_{Δ_{n−1}} will also be Borel measurable, but if h were only assumed to be Lebesgue measurable there is no reason h|_{Δ_{n−1}} should be Lebesgue measurable on Δ_{n−1}.) Now any point x ∈ Δ_{n} has a representation as x = (1 − t)e_{n} + ty where y ∈ Δ_{n−1} and t ∈ [0, 1]. But then the one dimensional result 2.48 (applied to the restriction of h to the segment between e_{0} and y where we note that this restriction is Borel and thus Lebesgue measurable) implies

h(x) = h((1 − t)e_{n} + ty) ≤ 2 + (1 − 2)h(e_{n}) + th(y)
≤ 2 + 0 + tκ(n − 1) ≤ 2 + κ(n − 1).

Thus h is bounded above on Δ_{n}. But then we can use Theorem 2.3 and reduce the bound to κ(n). This completes the proof.

2.8. Examples of approximately convex functions. Here we give examples showing that the hypothesis of our results are necessary.

2.49. Example. Let f(t) be any approximately sub-affine function on [0, 1]. Then (as in the proof of Proposition 2.24) the function F (x) := f(x_{0}) + f(x_{1}) + ⋯ + f(x_{n}) defined on the simplex Δ_{n} will be approximately convex. Using the function f(t) = t log_{2}(1/t) shows that for example F (x) := ∑_{k=0}^{n} x_{k} log_{2}(1/x_{k}) is approximately convex (cf. Lemma 2.22). As a slight generalization of this if f_{0}, …, f_{n} are all approximately sub-affine then F_{1}(x) = f_{0}(x_{0}) + f_{1}(x_{1}) + ⋯ + f_{n}(x_{n}) is approximately convex.

2.50. Example. Let C be any convex subset of any normed vector space and let φ: C → [0, 1]. Then φ((x + y)/2) ≤ 1 ≤ (φ(x) + φ(y))/2 + 1 so φ is approximately convex. There is no assumption on φ other than the bounds 0 ≤ φ ≤ 1. Thus φ need not be continuous or measurable. So approximate convexity by itself does not imply any type of regularity of the function.

2.51. Example. View R^{n+1} as a vector space over the rational numbers Q and let B be a Hamel basis for R^{n+1} over Q. Let h: R^{n+1} → R obtained by first mapping B to R and then extending to R^{n+1} by linearity. We can choose B ⊂ Δ_{n} = Co{e_{0}, …, e_{n}} (with e_{0}, …, e_{n} the standard basis of R^{n+1}) and h so that h[B] is dense in R. Therefore h is unbounded on Δ_{n}.

To get an example more closely related to Theorem 2.3 let h be as just defined but chosen in such a way that h(e_{i}) = 0 for 0 ≤ i ≤ n and set h_{0}(x) := max{h(x), 0}. Then for A := {e_{0}, …, e_{n}} we have Δ_{n} = Co(A), h_{0} is bounded from below, and h_{0} ≡ 0 on A. But h_{0} is not bounded from above on Δ. This shows the assumption that h be bounded from above in Theorem 2.3 is necessary. A similar example appears in the paper of Cholewa [2, §3].

2.52. Example. As an extension of the last example let Δ_{n−1}^{k} for 0 ≤ k ≤ n be the ((n − 1)-dimensional) faces of Δ_{n}. For each k choose an unbounded approximately convex function h_{k} : Δ_{n−1}^{k} → [0, ∞) that vanishes on the vertices of Δ_{n−1}^{k} (possible by the last example). Let h: Δ_{n} → [0, ∞) be h(x) = 0 on the interior of Δ_{n} and for each face h|_{Δ_{n−1}^{k}} = h_{k}. (A little care must be taken in the choice of the h_{k}’s to ensure that these restrictions agree on the intersections of the faces. This is not hard to arrange and we leave the details to the reader.) Then as the boundary of Δ_{n} (which is ⋃_{k=0}^{n} Δ_{n−1}^{k}) is a set of measure zero the function h is Lebesgue measurable on Δ_{n}, but is not Borel measurable. This shows that the hypothesis of Theorem 2.41 can not be weakened from Borel measurable to Lebesgue measurable.

3. The Size of the Convex Hull of an Approximately Convex Set

In this section we apply our results on approximately convex functions to the problem of giving a priori bounds on the size of convex hull of an approximately convex set.

3.1. General upper bounds. We now apply our results to the geometric problem of computing the size of the convex hull.

3.1. Theorem. Let ∥ · ∥ be any norm on R^{n} and let A ⊂ R^{n} be a set that is approximately convex in this norm. Let b ∈ Co(A) so that for some a_{0}, …, a_{m} ∈ A with m ≤ n we have b = ∑_{k=0}^{m} α_{k}a_{k} where (α_{0}, …, α_{n}) ∈ Δ_{m}, then

dist(b, A) ≤ E(α_{0}, …, α_{m}) ≤ κ(m) ≤ κ(n). (3.1)

(In the terminology of Theorem 1 this implies that C_{∥·∥} ≤ κ(n).)

3.2. Remark. For bounded sets this result can be restated in a dilation invariant fashion that does not involve approximately convex sets in its statement: If A ⊂ R^{n} is bounded set and b ∈ Co(A) so that b = ∑_{k=0}^{m} α_{k}a_{k} as in the statement of the theorem, then

dist(b, A) ≤ E(α_{0}, …, α_{m})d_{H}(\frac{1}{2}(A + A), A) ≤ κ(m)d_{H}(\frac{1}{2}(A + A), A).

The results below have similar dilation invariant versions.

Proof. Define a function f: Δ_{m} → [0, ∞) by

f(β_{0}, …, β_{m}) := dist ( ∑_{k=0}^{m} β_{m}a_{k}, A).

Then as the function function x ↦ dist(x, A) on R^{n} is an approximately convex function and the map (β_{0}, …, β_{m}) ↦ ∑_{k=0}^{n} β_{k}a_{k} is affine the function f is approximately convex and it is clearly continuous. Also f vanishes on the vertices of Δ_{m}. Therefore by Theorem 2.30 the bound f(β_{0}, …, β_{n}) ≤ E(β_{0}, …, β_{n}) holds. But this implies (3.1).

Recall that a subset A ⊂ R^{n} is convexly connected iff there is no hyperplane H of R^{n} so that A meets both half spaces determined by H but does not meet H. Each subset A decomposes uniquely into convexly connected components.

3.3. Theorem. Let ∥·∥ be a norm on R^{n} and let A ⊂ R^{n} which is approximately convex in this norm. Assume that either A has at most n connected components or A is compact and has at most n convexly connected components. Then any b ∈ Co(A) satisfies dist(b, A) ≤ κ(n − 1).

Proof. In either of the two cases there is a refinement of Carathéodory’s Theorem (cf. [3]) which implies that b is a convex combination of n points a_{0}, …, a_{n−1} points of A. Then Theorem 3.1 with m = n − 1 implies dist(b, A) ≤ κ(n − 1).

In a normed space we will use the notation B_{R}(x_{0}) for the closed ball of radius R about x_{0}.

3.4. Proposition. Let ∥·∥ be a norm on R^{n} and A ⊂ R^{n} a closed subset of R^{n}. Assume that x_{0} ∈ R^{n} \ A is a point where the function x ↦ dist(x, A) has a local maximum. Set R := dist(x_{0}, A) and let A_{1} := B_{R}(x_{0}) ∩ A be the points of A at a distance R from x_{0}. Then there are points a_{0}, …, a_{k} ∈ A_{1} with k ≤ n and norm one linear functionals λ_{0}, …, λ_{k} ∈ R^{n∗} so that λ_{i}(a_{i} − x_{0}) = R (i.e. λ_{i} norms a_{i} − x_{0}) and with 0 ∈ Co{λ_{0}, …, λ_{k}}.

Proof. By translation and rescaling we may assume x_{0} = 0 and R = 1. Let S := {u ∈ R^{n} : ∥u∥ = 1} be the unit sphere of the norm ∥ · ∥. Let ∥ · ∥^{∗} be the dual norm on R^{n∗} and S^{∗} the unit sphere of ∥ · ∥^{∗}. For any subset C ⊂ R^{n} let N^{∗}(C) be the set of linear functionals that norm some member of C. Explicitly N^{∗}(C) := {λ ∈ S^{∗} : λ(c) = ∥c∥ for some c ∈ C}. If C is compact then N^{∗}(C) is also compact. (For if ⟨λ_{ℓ}⟩_{ℓ=1}^{∞} is a sequence from N^{∗}(C) then (as S^{∗} is compact) by going to a subsequence we can assume that λ_{ℓ} → λ for some λ ∈ S^{∗}. For each ℓ there is a c_{ℓ} ∈ C with λ_{ℓ}(c_{ℓ}) = ∥c_{ℓ}∥. By compactness of C and again going to a subsequence we assume c_{ℓ} → c for some c ∈ C. But then λ(c) = lim_{ℓ→0} λ_{ℓ}(c_{ℓ}) = lim_{ℓ→0} ∥c_{ℓ}∥ = ∥c∥ which shows λ ∈ N^{∗}(C). Thus any sequence from N^{∗}(C) contains a subsequence that converges to a point of N^{∗}(C) and therefore N^{∗}(C) is is compact.)

Let d_{H}(·, ·) be the Hausdorff distance defined on the compact subsets of R^{n}. View the map C ↦ N^{∗}(C) as a map from the set of compact subsets of R^{n} to the set of compact subsets of S^{∗}. Then we claim this map is subcontinuous in the sense that if d_{H}(C_{ℓ}, C) → 0 and K ⊆ S^{∗} is a cluster point of the sequence ⟨N^{∗}(C_{ℓ})⟩_{ℓ=1}^{∞} then K ⊆ N^{∗}(C). To see this note as K is a cluster point of ⟨N^{∗}(C_{ℓ})⟩_{ℓ=1}^{∞} by going to a subsequence we can assume N^{∗}(C_{ℓ}) → K. Choose λ ∈ K. Then we can choose λ_{ℓ} ∈ N^{∗}(C_{ℓ}) in such a way that λ_{ℓ} → λ. From the definition of N^{∗}(C_{ℓ}) there is a c_{ℓ} ∈ C_{ℓ} so that λ_{ℓ}(e_{ℓ}) = ∥c_{ℓ}∥. By yet again going to a subsequence it can be assumed c_{ℓ} → c for some c ∈ C. But then a calculation like the one showing N^{∗}(C) is compact yields λ(c) = ∥c∥. Thus λ ∈ N^{∗}(C). As λ was any element of K this shows K ⊂ N^{∗}(C) as claimed.

Returning to the proof of Proposition 3.4. For r ≥ 1 let A_{r} := {a ∈ A : ∥a∥ ≤ r}. Then, as in the statement of the proposition, A_{1} is the set of points of A at a distance exactly 1 from 0 and so the conclusion of the proposition is equivalent to 0 ∈ Co(N^{∗}(A_{1})) (for if 0 is a convex combination of elements of N^{∗}(A_{1}) then the number of elements can be reduced to n + 1 by Carathéodory’s Theorem). Assume, toward a contradiction, that 0 ∉ Co(N^{∗}(A_{1})). Then N^{∗}(A_{1}) is compact and thus Co(N^{∗}(A_{1})) is also compact. Therefore the distance from Co(N^{∗}(A_{1})) to 0 is positive, say 2δ. As 1 ≤ r ≤ s implies A_{1} ⊆ A_{r} ⊆ A_{s} and ⋂_{r≥1} A_{r} = A_{1} it is not hard to see that lim_{r↘1} d_{H}(A_{r}, A_{1}) = 0. Thus by the sub-continuity of N^{∗} there is an r_{0} > 1 so that the set N^{∗}(A_{r_{0}}) has Hausdorff distance < δ from some subset K of N^{∗}(A_{1}). This implies the Hausdorff distance between Co(N^{∗}(A_{r_{0}})) and Co(K) is < δ and as K ⊂ N^{∗}(A_{1}) this implies dist(0, N^{∗}(A_{r_{0}})) ≥ δ. Thus there is a a linear functional on R^{n∗} that separates N^{∗}(A_{r_{0}}) from 0. As the linear functionals on R^{n∗} are the point evaluations there is a unit vector u_{0} ∈ S and ε > 0 so that for all λ ∈ N^{∗}(A_{r_{0}}) the inequality λ(u_{0}) ≤ −ε holds. Therefore for any b ∈ A_{r_{0}} we have a λ ∈ N^{∗}(A_{r_{0}}) that norms b and so for all t > 0

∥b − tu_{0}∥ ≥ λ(b − tu_{0}) = ∥b∥ − tλ(u_{0}) ≥ 1 + εt

and so dist(tu_{0}, A_{r_{0}}) ≥ 1 + εt for all t ≥ 0. Suppose that ∥x∥ < (r_{0} − 1)/2. Then dist(x, A) ≤ dist(0, A) + ∥x∥ < 1 + (r_{0} − 1)/2 = (r_{0} + 1)/2. Suppose that a ∈ A and that ∥a∥ > r_{0}. Then ∥a − x∥ > r_{0} − ∥x∥ > (1 + r_{0})/2 > dist(x, A). Thus, dist(x, A) = dist(x, A_{r_{0}}). In particular this implies that for 0 < t < (r_{0} − 1)/2 that dist(tu_{0}, A) = dist(tu_{0}, A_{r_{0}}) ≥ 1 + εt > 1. This contradicts that dist(·, A) has a local maximum at x = 0 and completes the proof.

3.2. General lower bounds. The following result shows that the estimate of Theorem 3.1 is sharp for all m ≤ n−1 and that Theorem 3.3, Theorem 3.7 and Theorem 3.14 are all sharp.

3.5. Theorem. Let ∥ · ∥ be any norm on R^{n} with n ≥ 2 and let α = (α_{0}, …, α_{n−1}) ∈ Δ_{n−1}. Then, for any ε > 0, there is a compact connected approximately convex set A ⊂ R^{n} and a point b ∈ Co(A) so that b = ∑_{k=0}^{n−1} α_{k}a_{k}, with a_{k} ∈ A, so that dist(b, A) ≥ E(α_{0}, …, α_{n−1}) − ε. In particular, since sup_{x∈Δ_{n−1}} E(x) = κ(n − 1) (cf. 2.27), for the proper choice of α it follows that there is a compact connected approximately convex set A ⊂ R^{n} and a point b ∈ A so that dist(b, A) ≥ κ(n−1). (In the terminology of Theorem 1 this implies that C_{∥·∥} ≥ κ(n − 1).)

Proof. Let ∥ · ∥ be any norm on R^{n} and let λ ∈ R^{n∗} be a linear functional on R^{n} with ∥λ∥ = 1. Let u ∈ R^{n} be a vector with ∥u∥ = 1λ(u). Let S := {x ∈ R^{n} : λ(x) = 0} be the null space of R^{n}. Choose n points a_{0}, …, a_{n} in S that are affinely independent. For each M > 0 define

V_{M} := Co{Ma_{0}, …, Ma_{n−1}}.

Any point of V_{M} is uniquely of the form ∑_{k=0}^{n−1} x_{k}Ma_{k} for some ∑_{k=0}^{n−1} x_{k}e_{k} ∈ Δ_{n−1}. Define F_{M} on V_{M} by

F_{M}( ∑_{k=0}^{n−1} x_{k}Ma_{k}) = E( ∑_{k=0}^{n−1} x_{k}e_{k}).

Finally set

A_{M} := {x + yu : x ∈ V_{M}, F_{M}(x) ≤ y ≤ κ(n − 1) + 1}.

Since E is lower semi-continuous F_{M} is also lower semi-continuous. This implies A_{M} is closed and bounded. (To see A_{M} is closed: x_{ℓ} + y_{ℓ}u ∈ A_{M} and x_{ℓ} + y_{ℓ}u → x + yu implies x_{ℓ} → x and F_{M}(x) ≤ lim inf_{ℓ→∞} F_{M}(x_{ℓ}) ≤ lim_{ℓ→∞} y_{ℓ} = y and so x+yu ∈ A_{M}.) It is also easy to check A_{M} is connected (and in fact contractible). That A_{M} is an approximately convex sets follows from E being an approximately convex function.

Let ε > 0 and define φ_{M}: Δ_{n−1} → V_{M} by

φ_{M}(x) = φ_{M}( ∑_{k=0}^{n−1} x_{k}e_{k}) = ∑_{k=0}^{n−1} x_{k}Ma_{k}.

Then F_{M} ∘ φ_{M} = E. Fix a norm ∥ · ∥_{0} on R^{n}. Then there is a constant C > 0 so that

∥φ_{M}(x) − φ_{M}(y)∥ ≥ CM∥x − y∥_{0} for all x, y ∈ Δ_{n−1}.

(C will depend on ∥ · ∥_{0}.) Since E is lower semi-continuous U := {x ∈ Δ_{n−1} : E(x) > E(α) − ε} is open in Δ_{n−1} and thus there is an R > 0 so that B_{R}(α) ∩ Δ_{n−1} ⊂ U. Let a_{k} := φ_{M}(e_{k}). Then as E(e_{k}) = 0 we have a_{k} ∈ A_{M} for 0 ≤ k ≤ n − 1. Let b := φ_{M}(α) = ∑_{k=0}^{n−1} α_{k}a_{k}. If w ∈ A_{M} then w = z +βu where z ∈ V_{M} and F_{M}(z) ≤ β ≤ κ(n−1)+1. If ∥z −b∥ < MCR, then F_{M}(z) > E(α) − ε so that ∥z + βu − b∥ ≥ λ(βu) = β ≥ E(α) − ε. If ∥z − y∥ ≥ MCR, then

∥z + βu − b∥ ≥ ∥z − b∥ − β ≥ MCR − κ(n − 1) − 1.

Now choose M so that MCR > 2κ(n − 1) + 1 so that MCR − κ(n − 1) − 1 ≥ κ(n − 1) ≥ E(α) − ε. Then ∥z + βu − b∥ ≥ κ(n − 1) − ε for all z + βu ∈ A_{M} and so dist(b, A_{M}) ≥ E(α) − ε. This completes the proof.

In the terminology of the last proof define a function h_{M}: Δ_{n−1} → [0, ∞) by h_{M} := dist(φ_{M}(x), A_{M}). Then h_{M} is approximately convex and h_{M} vanishes on the vertices of Δ_{n−1}. Also h_{M} is continuous and in fact Lipschitz continuous. The proof shows that for each fixed α ∈ Δ_{n−1} that lim_{M→∞} h_{M}(α) = E(α). Replacing n − 1 by n we thus have:

3.6. Proposition. There is a sequence of Lipschitz continuous approximately convex functions ⟨h_{ℓ}⟩_{ℓ=0}^{∞} on Δ_{n} vanishing on the vertices of Δ_{n} such that lim_{ℓ→∞} h_{ℓ}(x) = sup_{ℓ≥1} h_{ℓ}(x) = E(x) for all x ∈ Δ_{n}.

3.3. The sharp bounds in Euclidean Space. Theorem 3.1 can be improved in Euclidean spaces.

3.7. Theorem. Let R^{n} have its usual inner product norm and let A ⊂ R^{n} be approximately convex. Then any point b ∈ Co(A) has dist(b, A) ≤ κ(n − 1). (When combined with Theorem 3.5 and using the terminology of Theorem 1 this implies C_{∥·∥} = κ(n − 1) in Euclidean spaces of all dimensions.)

We will denote the usual inner product on R^{n} by ⟨·, ·⟩. Let S^{n−1} be the unit sphere in R^{n} with the Euclidean norm. Set

S(n) := {A ⊂ S^{n−1} : #(A) = n + 1 and 0 ∈ Co(A)^{∘}}, (3.2)

so that S(n) can be thought of as the set of simplexes inscribed in the sphere that have the origin 0 in their interior. An n-dimensional simplex that has all its edge lengths equal is a regular simplex. Recall that any two regular simplices with the same edge lengths are congruent. We leave following calculations to the reader.

3.8. Proposition. Let A ⊂ S^{n−1} be the set of vertices of a regular ndimensional simplex (so that #(A) = n + 1) inscribed in the sphere. Then A ∈ S(n) and the edge length of A is given by

∥a − b∥ = \sqrt{\frac{2(n + 1)}{n}}.

(a, b ∈ A and a ≠ b). Moreover the distance of the midpoint of the segment between a and b to the origin is

∥\frac{a + b}{2}∥ = \sqrt{\frac{n − 1}{2n}}.

Define M: S(n) → [0, 2] by

M(A) = max_{a,b∈A} ∥a − b∥.

Then M(A) is the length of the longest edge of the simplex with vertices A. The following characterizes the regular simplexes in terms of minimizing M on S(n).

3.9. Theorem. Let A ∈ S(n). Then

M(A) ≥ \sqrt{\frac{2(n + 1)}{n}}

with equality if and only if A is the set of vertices of a regular simplex.

3.10. Lemma. Let A = {x_{0}, …, x_{n}} ∈ S(n) and assume that

∥x_{0} − x_{n−1}∥ < ∥x_{0} − x_{n}∥. (3.3)

Then there is a point x_{0}^{∗} ∈ S^{n−1} so that

{x_{0}^{∗}, x_{1}, x_{2}, …, x_{n}} ∈ S(n), (3.4)

∥x_{0}^{∗} − x_{n}∥ < ∥x_{0} − x_{n}∥, (3.5)

∥x_{0}^{∗} − x_{n−1}∥ < ∥x_{0} − x_{n}∥, (3.6)

∥x_{0}^{∗} − x_{i}∥ = ∥x_{0} − x_{i}∥, 1 ≤ i ≤ n − 2. (3.7)

Proof. Since 0 is in the interior of Co(A) any subset of A of size n will be linearly independent. For 1 ≤ i ≤ n define f_{i}: R^{n} → [0, ∞) and ρ_{i}: S^{n} → R^{n} by

f_{i}(x) := ∥x − x_{i}∥, ρ_{i}(x) := ∥x − x_{i}∥.

(ρ_{i} is the restriction of f_{i} to S^{n−1}.) Let ∇f_{i} be the usual gradient of f_{i} and ∇ρ_{i} the gradient of ρ_{i} as a function on S^{n−1}. (That is ∇ρ_{i} is the vector field tangent to S^{n−1} so that for smooth curves c(t) in S^{n−1} the equality \frac{d}{dt}ρ_{i}(c(t)) = ⟨c′(t), ∇ρ_{i}(c(t))⟩ holds.) Then a standard calculation gives

∇f_{i}(x) = \frac{x − x_{i}}{∥x − x_{i}∥}.

As ρ_{i} is the restriction of f_{i} to S^{n−1} the vector field ∇ρ_{i}(x) is the orthogonal projection of ∇f_{i}(x) onto the tangent space T (S^{n−1})_{x} to S^{n−1} at x. Therefore

∇ρ_{i}(x_{0}) = \frac{x_{0} − x_{i}}{∥x_{0} − x_{i}∥} − ⟨\frac{x_{0} − x_{i}}{∥x_{0} − x_{i}∥}, x_{0}⟩x_{0}.

But then the n − 1 vectors ∇ρ_{1}(x_{0}), …, ∇ρ_{n−2}(x_{0}), ∇ρ_{n}(x_{0}) are linearly independent as any nontrivial linear relationship between them would lead to a nontrivial linear relationship between x_{0}, …, x_{n−2}, x_{n} which are linearly independent. The implicit function theorem implies that the n−1 functions ρ_{1}, …, ρ_{n−2}, ρ_{n} are local coordinates on S^{n−1} near x_{0} (that is the map x ↦ (ρ_{1}(x), …, ρ_{n−1}(x), ρ_{n}(x) is a diffeomorphism onto an open set in R^{n−1} when restricted to a small enough open neighborhood of x_{0}). Let δ_{i} = ρ_{i}(x_{0}) = ∥x_{0} − x_{i}∥ and set

N :={x ∈ S^{n−1} : ρ_{i}(x) = δ_{i}, 1 ≤ i ≤ n − 2}
={x ∈ S^{n−1} : ∥x − x_{i}∥ = δ_{i}, i ≤ i ≤ n − 2}.

As ρ_{1}, …, ρ_{n−2}, ρ_{n} are local coordinates near x_{0} this will be a smooth curve in S^{n−1} near x_{0} and, moreover, any point x_{0}^{∗} ∈ N will satisfy all the conditions (3.7). Choose a parameterization c: (−ε, ε) → N of N near x_{0} with c(0) = x_{0}. As ρ_{1}, …, ρ_{n−2}, ρ_{n} is a local coordinate system near x_{0} and the first n − 2 for these functions are constant on c(t) we have that \frac{d}{dt}ρ_{n}(c(t))|_{t=0} = ⟨∇ρ_{n}(x_{0}), c′(t)⟩ ≠ 0. Without loss of generality we can assume that \frac{d}{dt}ρ_{i}(c(t))|_{t=0} < 0 (otherwise replace c(t) by c(−t)). Then for small t > 0 we have ρ_{n}(c(t)) < ρ_{n}(c(0)) = ρ_{n}(x_{0}). Also the conditions (3.4 and (3.6) are open conditions in x_{0}^{∗} and so for any t sufficiently close to 0 they will hold for x_{0}^{∗} = c(t). Therefore x_{0}^{∗} = c(t) for small positive t satisfies the conclusion of the lemma. This completes the proof.

Proof of Theorem 3.9. We prove the theorem by induction on n. The base case of n = 1 is trivial. Let \overline{S}(n) be the closure of S(n), that is

\overline{S}(n) = \{A ⊂ S^{n−1} : #(A) ≤ n + 1, 0 ∈ Co(A)\}.

Then the function M(A) = max_{a,b∈A} ∥a−b∥ is continuous on \overline{S}(n) and \overline{S}(n) is compact, so M obtains its minimum at some A_{0} ∈ \overline{S}(n). If this minimum occurs at a boundary point of \overline{S}(n) then 0 ∈ Co(A_{0}), but 0 ∉ Co(A_{0})^{∘}. Let a, b ∈ A_{0} be the points of A_{0} so that ∥a − b∥ = M(A_{0}). Then there exists a subset {a, b} ⊆ A_{1} ⊆ A_{0} so that #(A_{1}) =: m + 1 < n + 1 with A_{1} affinely independent and so that 0 is in the relative interior of Co(A_{1}). Thus, with obvious notation, A_{1} ∈ S(m) and therefore by the induction hypothesis M(A_{1}) ≥ \sqrt{2(m + 1)/m}. But for the regular simplex in S(n) that M has the value \sqrt{2(n + 1)/n}, which is less than \sqrt{2(m + 1)/m}. Therefore the minimum of M on \overline{S}(n) occurs in S(n).

Again, let A_{0} ∈ S(n) be where M obtains its minimum, and let c = M(A_{0}). If every edge of A_{0} has length c then A_{0} is a regular simplex and we are done. The number of edges of A_{0} is \binom{n+1}{2}. So assume that there are k < \binom{n+1}{2} edges that have length c. Then there will be a side \{x_{0}, x_{n}\} of length c that has a vertex in common with a side {x_{0}, x_{n−1}} that was a length less than c. With this notation let A_{0} = {x_{0}, …, x_{n}}. Then by Lemma 3.10 we can replace x_{0} be some x_{0}^{∗} so that if A_{1} := {x_{0}^{∗}, x_{1}, …, x_{n}} then both the edges {x_{0}^{∗}, x_{n}} and {x_{0}^{∗}, x_{n−1}} have length < c and all of the other \binom{n+1}{2} − 2 edge lengths stay the same. Therefore A_{1} has only k − 1 edges of length c (and if k = 1 then all edges of A_{1} have length less than c). By repeating this procedure k times we end up with A_{k} ∈ S(n) so that M(A_{k}) < M(A_{0}), contrary to the assumption that A_{0} was the minimizer. Thus the minimizer must be regular. This completes the proof.

If x, y ∈ S^{n−1} then ∥x + y∥^{2} + ∥x − y∥^{2} = 4. Whence the distance ∥\frac{1}{2}(x + y)∥ of the midpoint of the segment \overline{xy} from the origin is determined by its length. Therefore Theorem 3.9 implies the following:

3.11. Corollary. Let S(n) be defined by (3.2) above and let D: S(n) → [0, 2] be given by

D(A) = min_{a,b∈A}∥\frac{a + b}{2}∥.

Then for all A ∈ S(n) the inequality

D(A) ≤ \sqrt{\frac{n − 1}{2n}}

holds. Equality holds if and only if A is the set of vertices of a regular simplex.

The following is what is needed in the proof of our main results.

3.12. Proposition. Let B_{r}(x_{0}) be a ball of radius r in R^{n} with the Euclidean norm and assume that there are n+1 points {a_{0}, …, a_{n}} ⊆ ∂B_{r}(x_{0}) such that x_{0} is in the interior of the simplex Co{a_{0}, …, a_{n}}. Assume that for each pair {a_{i}, a_{j}} that the distance of the midpoint (a_{i}+a_{j})/2 to ∂B_{r}(x_{0}) is ≤ 1. Then

r ≤ \frac{\sqrt{2n}(\sqrt{2n} + \sqrt{n − 1})}{n + 1} ≤ κ(n − 1)

Proof. By Corollary 3.11 there exists a pair {a_{i}, a_{j}} such that ∥a_{i} + a_{j}∥/2 ≤ r\sqrt{(n − 1)/(2n)}. So

1 ≥ dist (\frac{a_{i} + a_{j}}{2} , ∂B_{r}(x_{0})) ≥ r − \frac{∥a_{i} + a_{j}∥}{2} ≥ r (1 − \sqrt{\frac{n − 1}{2n}} )

Solving for r gives r ≤ \sqrt{2m}(\sqrt{2n}−\sqrt{n − 1})/(n+1). To see that r = r(n) ≤ κ(n − 1) first note r(n) < 2 + \sqrt{(}2) < 3.42 for n ≥ 1. If n ≥ 4 we then have r(n) < 3.5 = κ(4 − 1) ≤ κ(n − 1). This only leaves r(2) = 2 = κ(2 − 1) and r(3) = \sqrt{3}(\sqrt{3} + 1)/2 < 3 = κ(3 − 1).

Proof of Theorem 3.7. By replacing A by its closure we can assume that A is closed. Define f: R^{n} → R by f(x) := dist(x, A). By Carathéodory’s Theorem, it suffices to prove that if {a_{0}, …, a_{n}} ⊆ A then f(x) ≤ κ(n − 1) for all x ∈ Co({a_{0}, …, a_{n}}). To simplify notation set Δ := Co({a_{0}, …, a_{n}}) and let x_{0} be the point where f|_{Δ} achieves its maximum. Then we wish to show f(x_{0}) ≤ κ(n − 1). If x_{0} is on the boundary (or if {a_{0}, …, a_{n}} is not affinely dependent) then x_{0} is a convex combination of ≤ n points of {a_{0}, …, a_{n}} and so f(x_{0}) ≤ κ(n − 1) by Theorem 2.3.

This leaves the case where x_{0} is in the interior of Δ. Then f(·) = dist(·, A) has a local maximum at the interior point x_{0} of Co(A). Let R := f(x_{0}). Then, by Proposition 3.4, there are points a_{0}, …, a_{k} ∈ A ∩ B_{R}(x_{0}) so that {a_{0}, …, a_{k}} is an affinely independent set and there are unit vectors u_{0}, …, u_{k} so that the functional λ_{i} := ⟨·, u_{i}⟩ norms a_{i} − x_{0} and 0 ∈ Co{u_{0}, …, u_{k}}. But if λ_{i} norms a_{i} − x_{0} then u_{i} = (a_{i} − x_{i})/∥a_{i} − x_{i}∥. Therefore 0 ∈ Co{u_{0}, …, u_{k}} implies x_{0} ∈ Co{a_{0}, …, a_{k}}. Now Proposition 3.12 implies f(x_{0}) = R ≤ κ(n − 1). This completes the proof.

3.13. Remark. Let A be the seven point subset of the Euclidean plane shown in Figure 6. Then A is approximately convex and satisfies d_{H}(Co(A), A) = 2 = κ(1). In higher dimensions we do not know if there exist such examples of A ⊂ R^{n} with d_{H}(Co(A), A) = κ(n − 1).

.  . .  . .  . .  ^{(2\sqrt{3}, 1)}^{(−2\sqrt{3}, 1)}  ^{(\sqrt{3}, 2)}^{(−\sqrt{3}, 2)}  ^{(0, 1)}^{(−3\sqrt{3}, 0)}  ^{(3\sqrt{3}, 0)}

Figure 6. A two-dimensional Euclidean example.

3.4. The sharp two dimensional bounds. We now give the sharp estimate for the size of a convex hull in all two dimensional normed spaces.

3.14. Theorem. Suppose ∥ · ∥ is a norm on R^{2} and that A ⊆ X has is approximately convex in this norm. Then any point b ∈ Co(A) has dist(b, A) ≤ 2. (By Theorem 3.5 given ε > 0, there exists an approximately convex A_{ε} ⊆ R^{2} and a b ∈ Co(A) so that dist(b, A) ≥ 2 − ε and thus thus in the notation of Theorem 1 C_{∥·∥} = 2 for all two dimensional norms.)

3.15. Lemma. Let V = {a, b, c, −a, −b, −c} be the vertices of a symmetric convex hexagon. Then

{a + b, b + c, c + a} ∩ Co(V) ≠ ∅.

Proof. By applying a linear transformation we may assume a = (−1, 1) and b = (−1, −1). Without loss of generality we also assume c = (x_{0}, y_{0}), where −1 ≤ y_{0} ≤ 0 and x_{0} ≥ 1. If y_{0} > 2 − x_{0}, then a + b = (−2, 0) ∈ Co(V), and we are done. So we may assume that c ∈ Co({(1, 0), (1, −1), (2, 0), (3, −1)}). (Co({(1, 0), (1, −1), (2, 0), (3, −1)}) is shaped region in Figure 7.) This forces

(1, 0)  (2, 0) −c  c b = (−1, −1) a = (−1, 1)  −b = (1, 1) −a = (1, −1)  (3, −1) a + c Figure 7

the quadrilateral Co({0, a, c, −b}) to contain the parallelogram Co({0, a, c, a+ c}), and so

a + c ∈ Co({0, a, c, a + c}) ⊆ Co({0, a, c, −b}) ⊆ Co(V).

For the rest of this section we will call a norm on a finite dimensional space ∥ · ∥ smooth if it is a C^{∞} function away from the origin and the unit ball is strictly convex. A finite dimensional space is smooth iff its norm is smooth. This implies that norming linear functionals are unique.

3.16. Lemma. Let X be a smooth two-dimensional normed space. Suppose that K ⊆ S_{1}(0) is a closed set and that 0 ∉ Co(K). Then f(x) = dist(x, K) does not attain a local maximum at x = 0.

Proof. As (X, ∥·∥) is smooth for each u ∈ S_{1}(0) there is a unique norm linear functional λ_{u} that norms u, the map u ↦ λ_{u} is a homeomorphism of S_{1}(0) onto the unit sphere S_{1}^{∗}(0) in the dual space (X^{∗}, ∥ · ∥^{∗}), and λ_{−u} = −λ_{u}. If u ∈ S_{1}(0) then S_{1}(0) \ {u, −u} has exactly two connected components. A closed subset K ⊆ S_{1}(0) satisfies 0 ∉ Co(K) if and only if there is a u ∈ S_{1}(0) so that K is contained in one of the connected components of S_{1}(0) \ {u, −u} (for this is equivalent to being able to separate K from the origin by a linear functional). But the properties of the map u ↦ λ_{u} imply K is contained in a connected component of S_{1}(0) \ {−u, u} if and only if N^{∗}(K) := {λ_{u} : u ∈ K} is contained in a connected component of S_{1}^{∗}(0) \ {λ_{u}, −λ_{u}}. Therefore 0 ∉ Co(K) if and only if 0 ∉ Co(N^{∗}(K)). But by Proposition 3.4 0 ∉ Co(N^{∗}(K)) implies that f does not have a local maximum at 0.

Let ε > 0. A set A ⊆ X will be said to be ε-separated if ∥a − b∥ ≥ ε whenever a, b are distinct elements of A.

3.17. Lemma. Suppose that X is a smooth two-dimensional normed space and that A ⊆ X is ε-separated and approximately convex. Then d_{H}(A, Co(A)) ≤ 2.

Proof. Let f(x) = dist(x, A) (x ∈ X). By Carathéodory’s Theorem, it suffices to prove that if {d, e, f} ⊆ A, then f(x) ≤ 2 for all x ∈ Δ, where Δ = Co({d, e, f}). By continuity of f, there exists x_{0} ∈ Δ at which f attains its maximum. By translation we may assume without loss of generality that x_{0} = 0. If 0 ∈ ∂(Δ) then 0 is on a segment between two elements of A and so by restriction f to this segment see by Theorem 2.3 f(0) ≤ 2. So we may assume that 0 lies in the interior of Δ. Let R = f(0) and let K = A ∩ B_{R}(0). If 0 ∉ Co(K), then by Lemma 3.16 g(x) = dist(x, K) does not attain a local maximum at x = 0. But since A is ε-separated an easy compactness argument yields dist(0, A \ K) > R, and so f(x) = g(x) for all x sufficiently close to x = 0. Thus, f(x) does not attain a local maximum at x = 0, which contradicts the fact that 0 lies in the interior of Δ.

So we may assume that 0 ∈ Co(K). By Carathéodory’s Theorem there exists {a, b, c} ⊆ K with 0 ∈ Co({a, b, c}) Once again, we may assume that 0 lies in the interior of Co({a, b, c}). Now B_{R}(0) contains the convex hexagon with vertices V = {a, b, c, −a, −b, −c}. By Lemma 3.16,

{a + b, b + c, c + a} ∩ Co(V) ≠ ∅.

Thus

min{∥a + b∥, ∥b + c∥, ∥c + a∥} ≤ R.

We may assume without loss of generality that ∥a + b∥ ≤ R. Since A is approximately convex there exists x ∈ A with ∥x − (1/2)(a + b)∥ ≤ 1. Thus

R = dist(0, A) ≤ ∥x∥ ≤ 1 + \frac{1}{2}∥a + b∥ ≤ 1 + \frac{R}{2},

and so R ≤ 2 as required.

Proof of Theorem 3.14. Assume A ⊆ X is approximately convex Let ε > 0. There exists an equivalent smooth norm ∥ · ∥′ on X such that

∥x∥′ ≤ ∥x∥ ≤ (1 + ε)∥x∥′ (x ∈ X).

Let B ⊆ A be a maximal ε-separated subset of A. Then d′_{H}(A, B) ≤ d_{H}(A, B) ≤ ε (here d′_{H}(·, ·) denotes Hausdorff distance with respect to ∥·∥′). Thus,

d′_{H} (B, \frac{B + B}{2} ) ≤ d′_{H}(B, A) + d′_{H} (A, \frac{A + A}{2}) + d′_{H} (\frac{A + A}{2}, \frac{B + B}{2} )
≤ ε + 1 + ε = 1 + 2ε

Lemma 3.17 applied to ∥ · ∥′ and B yields d′_{H}(B, Co(B)) ≤ 2(1 + 2ε). Thus,

d_{H}(A, Co(A)) ≤ (1 + ε)d_{H}(A, Co(A))
≤ (1 + ε)((d′_{H}(B, Co(B)) + 2d′_{H}(A, B))
≤ (1 + ε)(2(1 + 2ε) + 2ε)

Since ε > 0 is arbitrary, we obtain d_{H}(A, Co(A)) ≤ 2 as desired.

Acknowledgments: We would like to thank Maria Girardi for realizing a blackboard on the North end of the third floor of the Mathematics building would lead to the type of results given here. During all stages of this work we profited from conversations with Anton Schep.

References

[1] E. Casini and P. L. Papini, Almost convex sets and best approximation, Ricerche Mat. 40 (1991), no. 2, 299–310 (1992).

[2] P. W. Cholewa, Remarks on the stability of functional equations, Aequationes Math. 27 (1984), no. 1-2, 76–86.

[3] O. Hanner and H. Rådström, A generalization of a theorem of Fenchel, Proc. Amer. Math. Soc. 2 (1951), 589–593.

[4] D. H. Hyers and S. M. Ulam, Approximately convex functions, Proc. Amer. Math. Soc. 3 (1952), 821–828.

[5] C. T. Ng and K. Nikodem, On approximately convex functions, Proc. Amer. Math. Soc. 118 (1993), no. 1, 103–108.

[6] R. T. Rockafellar, Convex analysis, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997, Reprint of the 1970 original, Princeton Paperbacks.

[7] R. Schneider, Convex bodies: The Brunn-Minkowski theory, Encyclopedia of Mathematics and its Applications, vol. 44, Cambridge University Press, 1993.

Department of Mathematics University of South Carolina Columbia, S.C. 29208, USA

dilworth@math.sc.edu
howard@math.sc.edu
roberts@math.sc.edu