Measurability of the Minkowski Sum of Two Sets

This entry has grown out of a question I answered on MathOverflow. I will try to explain the question and my answer in a more leisurely manner here.

An example that the sum of two Borel sets which is not a Borel set in n-dimensional Euclidean space

A Blog Entry on Bayesian Computation by an Applied Mathematician

$$

$$

1 Introduction

Question

For Borel sets \(A,B\in\mathcal{B}(\mathbb{R}^n)\), Minkowski sum is defined as \[ A+B:=\left\{a+b\in\mathbb{R}^n\mid a\in A,b\in B\right\}. \] We are interested in the following questions:

1. Under what conditions is \(A+B\) Borel?

2. For what \(A,B\in\mathcal{B}(\mathbb{R}^n)\) is \(A+B\) not Borel?

\(A+B\) being an image of a continuous mapping \(+:\mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}^n\), \(A+B\) is an analytic (a.k.a. Souslin) set. Therefore, \(A+B\) is Lebesgue measurable, given all Souslin sets are universally measurable.¹

A statistician or probability theorist may come across this problem when considering isoperimetric inequalities. For example, the one by (Borell, 1975) and (Sudakov and Tsirel’son, 1974) goes as follows:

Theorem² (Gaussian isoperimetric inequality)

Let \(\gamma_n:=\mathrm{N}_n(0,I_n)\) be the standard Gaussian measure on \(\mathbb{R}^n\), \(u\in\partial B^n\subset\mathbb{R}^n\) a unit vector, \(A\in\mathcal{B}(\mathbb{R}^n)\) be a Borel measurable set, and \[ H_a:=\left\{x\in\mathbb{R}^n\mid(x|u)\le a\right\},\quad a\in\mathbb{R}, \] be a affine half-space satisfying \(\gamma_n(H_a)=\gamma_n(A)\). Then, the following inequality holds for all \(\epsilon>0\): \[ \gamma_n(H_{a+\epsilon})=\gamma_n(A_\epsilon),\qquad\epsilon>0, \] where \(B^n\overset{\textrm{closed}}{\subset}\mathbb{R}^n\) is a closed unit ball centered at the origin, and \[ A_\epsilon:=\left\{x\in\mathbb{R}^n\:\middle|\:\inf_{y\in A}\|x-y\|_2\le\epsilon\right\} \] is the closed \(\epsilon\)-neighborhood of \(A\).

Here, \[ A_\epsilon=A+\epsilon B^n \] so the Borel measurability of \(A+B^n(0,\epsilon)\) matters.

Of course, \(A_\epsilon\) is \(\gamma_n\)-measurable, meaning that there exist Borel sets \(B_1,B_2\in\mathcal{B}(\mathbb{R}^n)\) such that \[ B_1\subset A_\epsilon\subset B_2, \] \[ \mu(B_2\setminus B_1)=0. \] Thus, the above theorem can be understood as implicitly assuming the Borel probability measure \(\gamma_n\) to be completed in the Lebesgue sense.

As it turns out in Section 3.2, the Borel measurability of \(A+B^n(0,\epsilon)\) is not guaranteed, despite the fact \(B^n(0,\epsilon)\) is a closed and compact subset.

2 Conditions assuring to be Borel

Proposition

Let \(A,B\in\mathcal{B}(\mathbb{R}^n)\) be Borel sets.

1. If either \(A\) or \(B\) is open, then \(A+B\) is open.
2. Even when \(A\) and \(B\) are closed, \(A+B\) may not be closed.
3. Additionally imposing either \(A\) or \(B\) to be compact, then \(A+B\) is closed.

All of the above statements remain valid when an arbitrary topological vector space is considered in place of \(\mathbb{R}^n\).

Proof

1. Given \[ A+B=\bigcup_{b\in B}(A+b), \] we see that \(A+B\) is open if either \(A\) or \(B\) is open. Note \(\bullet+b:\mathbb{R}^n\to\mathbb{R}^n\) is a homeomorphism, so \(A+b\) is open.

2. Let \(n=1\) and \[ A:=\mathbb{N}^+, \] \[ B:=\left\{-n+\frac{1}{n}\in\mathbb{R}\:\middle|\:n=2,3,\cdots\right\}. \] Both sets \(A,B\) are discrete subsets of \(\mathbb{R}\), hence closed. However, \(A+B\) is not closed. Indeed, \(\{1/n\}_{n\ge2}\subset A+B\) but its limit point \(0\notin A+B\).

3. Let us assume \(A\) to be compact and take an arbitrary sequence \(\{a_n+b_n\}\subset A+B\) converging to a limit, denoted \(x\in\overline{A+B}\). Compactnes of \(A\) implies the existence of a convergent subsequence \(\{a_{n_k}\}\subset\{a_n\}\) converging to some \(a\in A\). Then, \(\{b_{n_k}\}\subset B\) also converges and its limit is \(x-a\in B\), which belongs to \(B\) because \(B\) is closed. Hence, \(x=a+(x-a)\in A+B\), giving a sufficient condition for \(A+B\) to be closed.

3 Counterexamples

3.1 Using subgroups of \(\mathbb{R}\)

(Erdös and Stone, 1969) gives a counterexample for \(n\ge2\). Astonishingly, for the case \(n=1\), the counterexample consists of \(A\) being a Cantor, hence compact, set and \(B\) being a \(G_\delta\) set.

3.2 Using a non-Borel Souslin set of \(\mathbb{R}^2\).

For every uncountable Polish space, there exists a non-Borel Souslin set,³ i.e., \(\mathcal{B}(X)\subsetneq\Sigma^1_1(X)\), where \(\Sigma^1_1(X)\) represents the class of all Souslin sets of \(X\).

Taking \(X=[-1,1]\), we can construct a non-Borel Souslin set \(A_1'\in\Sigma^1_1(X)\setminus\mathcal{B}(X)\), and using this \(A_1'\) we are going to construct a counterexample for \(n\ge3\).

Here, we are in need of the following characterization of Souslin sets:

Theorem⁴

Let \(X\) be a Souslin space, a Souslin set which is also Hausdorff, and let \(A\subset X\) its subset. The following are equivalent:

1. \(A\) is a Souslin set;
2. \(A\) can be represented as \(A=\mathrm{pr}_1(F)\), where \(F\overset{\textrm{closed}}{\subset}X\times\mathbb{N}^\infty\);
3. \(A\) can be represented as \(A=\mathrm{pr}_1(B)\), where \(B\subset X\times\mathbb{R}\) is Borel measurable.

Here we take \(X:=[-1,1]\) and \(A:=A_1'\), we can find a Borel measurable subset \(A'\subset[-1,1]^2\) such that \(A_1'=\mathrm{pr}_1(A')\).⁵

The next step is crucial, where we map the Borel subset \(A'\) to a cylinder \[ C:=\left\{(x_1,x_2,x_3)\in\mathbb{R}^3\mid x_2^2+x_3^2=1\right\}, \] using a homeomorphism \(\psi:\mathbb{R}^2\to\mathbb{R}^2\) which satisfies \[ \begin{align*} &\psi([-1,1]\times\{0\})\\ &\qquad\subset\left\{(x_1,x_2)\in\mathbb{R}^2\mid x_1^2+x_2^2=1\right\}. \end{align*} \] Such a homeomorphism \(\psi\) takes the segment \([-1,1]\) on the \(x_1\)-axis into the unit circumference \(S^1\) in the \((x_1,x_2)\)-plane.

Using \(\psi\) as a building block, we constract a homeomorphism \(\Psi:\mathbb{R}^3\to\mathbb{R}^3\) by \[ \Psi(x_1,x_2,x_3):=(x_1,\psi(x_2,x_3)). \] Such a homeomorphism \(\Psi\) pastes the set \(A'\) onto the surface of the cylinder \(C\): \(A:=\Psi(A')\subset C\). Given that \(\Psi\) is a homeomorphism, \(A\) is a Borel measurable set.⁶

Thus, \(A\subset C\subset\mathbb{R}^3\) now satisfies the following properties: \[ \biggr(A+B(0,1)\biggl)\cap\biggr(\mathbb{R}\times\{0\}^2\biggl)=A_1', \] where \(A_1'\notin\mathcal{B}(X)\) is non-Borel and \(B(0,1)\subset\mathbb{R}^3\) is a closed unit ball centered at the origin.⁷ This scenario is impossible if \(A+B(0,1)\) is Borel measurable, since \(\mathbb{R}\times\{0\}^2\) is Borel measurable.

This idea is stimulated from (Luiro et al., 2014), which has an arXiv version, Example 2.4.

References

Bogachev, V. I. (2007). Measure theory. Springer-Verlag.

Borell, C. (1975). The brunn-minkowski inequality in gauss space. Inventiones Mathematicae, 30, 207–216.

Dudley, R. M. (2002). Real analysis and probability,Vol. 74. Cambridge University Press.

Erdös, P., and Stone, A. H. (1969). On the sum of two borel sets. Notices of the American Mathematical Society, 16, 968–969.

Giné, E., and Nickl, R. (2021). Mathematical foundations of infinite-dimensional statistical models. Cambridge University Press.

Kechris, A. S. (1995). Classical descriptive set theory,Vol. 156. Springer New York.

Luiro, H., Parviainen, M., and Saksman, E. (2014). On the existence and uniqueness of p-harmonious functions. Differential Integral Equations, 27(3/4), 201–216.

Sudakov, V. N., and Tsirel’son, B. S. (1974). Extremal properties of half-spaces for spherically invariant measures. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta Im. V. A. Steklova AN SSSR, 41, 14–24.

Footnotes

1. (Dudley, 2002, p. 497) Theorem 13.2.6, (Kechris, 1995, p. 155) Theorem 21.20.

2. (Borell, 1975), (Sudakov and Tsirel’son, 1974), (Giné and Nickl, 2021, p. 31) Theorem 2.2.3.

3. (Kechris, 1995, p. 85) Theorem 14.2.

4. (Bogachev, 2007, p. 24) Theorem 6.7.2, (Kechris, 1995, p. 86) 14.3.

5. From the theorem, we can find a Borel measurable subset \(B\subset[-1,1]\times\mathbb{R}\) such that \(A_1'=\mathrm{pr}_1(B)\). Then, we define \(A':=B\cap[-1,1]^2\), which is Bore measurable and still has the property \(A_1'=\mathrm{pr}_1(A')\).

6. For a complete separable metric space \(X,Y\), an image of a Borel set via a Borel measurable injection is again Borel measurable. (Bogachev, 2007, p. 30) Theorem 6.8.6.

7. For other notations, please consult this post.