[et_pb_section fb_built=”1″ admin_label=”section” _builder_version=”3.22″ custom_padding=”30px|0px|30px|0px|false|false” global_colors_info=”{}”][et_pb_row column_structure=”2_3,1_3″ admin_label=”row” _builder_version=”3.25″ background_size=”initial” background_position=”top_left” background_repeat=”repeat” custom_padding=”2px|0px|4px|0px|false|false” global_colors_info=”{}”][et_pb_column type=”2_3″ _builder_version=”3.25″ custom_padding=”|||” global_colors_info=”{}” custom_padding__hover=”|||”][et_pb_text _builder_version=”3.27.4″ header_font=”|600||on|||||” global_colors_info=”{}”]<\/p>\n
by Tomasz Tkocz<\/b><\/p>\n
This note briefly surveys several results, classical by now, which shaped high-dimensional convex geometry and describes its major open problems. We start with a closer look at Euclidean balls and then try to make a point that “in high-dimensions, all convex sets, despite their rich structure, behave a bit like Euclidean balls”.<\/p>\n
A set of points \\(A\\) in \\(R^n\\) is called convex if along with every two points \\(a_1, a_2\\) in \\(A\\), the whole segment \\([a_1,a_2]\\) joining \\(a_1\\) and \\(a_2\\) is contained in the set \\(A\\). For example balls and ellipsoids, or cubes and parallelopipeds are convex, whereas annuli are not. How is volume distributed in a convex set? Say, we have a convex set of volume \\(1\\). Where is most<\/em> of its volume concentrated<\/em>?<\/p>\n Consider the example of a centered Euclidean ball \\(B = \\{x \\in R^n, \\ x_1^2+\\ldots+x_n^2 \\leq r^2\\}\\). Choose its radius \\(r\\) such that it has unit volume, \\(r = v_n^{-1\/n}\\), where \\(v_n\\) is the volume of the $n$-dimensional ball with radius \\(1\\). Thus, \\(r = \\frac{1}{\\sqrt{\\pi}}\\Gamma(1+\\frac{n}{2})^{1\/n}\\), which is approximately \\(\\sqrt{\\frac{n}{2\\pi e}}\\) for large \\(n\\). For \\(x \\in R\\), let \\(f(x)\\) be the \\((n-1)\\)-dimensional volume of the cross-section of \\(B\\) with a hyperplane perpendicular to the \\(0x_1\\) axis passing through \\((x,0,\\ldots,0)\\). Plainly, The function \\(f\\) is the probability density of the volume distribution of the ball \\(B\\) in the direction of the vector \\((1,0,\\ldots,0)\\). What is this distribution like? That cross-section is again a ball, whose radius is \\(\\sqrt{r^2-x^2}\\) (Pythagoras’ theorem). Therefore, This means that \\(f\\), the volume distribution in the ball \\(B\\) is roughly Gaussian with variance \\(\\sigma\\) of constant order (\\(\\sigma = \\frac{1}{2\\pi e}\\))! So, where is the volume concentrated? By the \\(3\\sigma\\)-rule, \\(\\int_{-3\\sigma}^{3\\sigma} f(x) dd x > 0.99\\), so more than \\(99\\%\\) volume of \\(B\\) is within a symmetric slab \\(\\{x \\in R^n, \\ |x_1| \\leq 3\\sigma\\}\\) of width \\(6\\sigma\\). In high dimension \\(n\\), this width of constant order becomes tiny tiny in comparison with the radius \\(r\\) of \\(B\\), which is of the order \\(\\sqrt{n}\\). To challenge our high dimensional intuitions more, remark that the choice of the axis \\(0x_1\\) was arbitrary and by symmetry the above remains true for any other direction, so \\(99\\%\\) volume of \\(B\\) is within any symmetric slab of width \\(6\\sigma\\).<\/p>\n Let us have a look at how much volume there is near the surface of \\(B\\), say in an annulus of the inner radius \\(r – 1\/\\sqrt{n}\\) and the outer radius \\(r\\), for some constant \\(C\\). Plainly, this volume equals Asymptotic convex geometry is concerned with quantifying such high dimensional phenomena for arbitrary convex sets. One of the major breakthroughs was Klartag’s central limit theorem which guarantees that the same phenomenon which we observed above for the ball holds for an arbitrary convex set (properly normalised<\/em>): the distribution of volume (function \\(f\\)) is Gaussian along most<\/em> of directions. It was explained by Antilla, Ball and Peresinaki that such a central limit behavior comes from the volume being concentrated in a thin annulus, as readily observed above for the Euclidean ball. Klartag established this type of estimates, called thin-shell bounds, for an arbitrary convex set \\(K\\) in \\(R^n\\), showing that there are sequences \\(\\delta_n, \\varepsilon_n \\to 0\\) as \\(n \\to \\infty\\) such that Historically, asymptotic convex geometry grew out of Dvoretzky’s theorem, which says that \\(n\\)-dimensional symmetric convex sets admit sections with roughly \\(\\log n\\)-dimensional subspaces which are almost Euclidean balls. Interestingly, such Euclidean subspaces are not easy to find constructively, however, Milman’s probabilistic proof of Dvoretzky’s theorem shows that most subspaces yield Euclidean sections.<\/p>\n Of course, many problems remain unsolved. A central one, the slicing problem posed by Bourgain, asks whether there is a universal constant \\(c\\) such that for every dimension \\(n\\), every \\(n\\)-dimensional convex set with volume \\(1\\) admits a codimension \\(1\\) section through its barycentre of volume at least \\(c\\). (Currently the best dimension dependent bound on \\(c\\) is of the order \\(n^{-1\/4}\\)).<\/p>\n The slicing problem is equivalent to many other natural questions in convex geometry and beyond. For example, the Busemann-Petty problem asked the following: if symmetric convex sets \\(K\\) and \\(L\\) in \\(R^n\\) satisfy \\(vol(K \\cap H) \\leq vol(L \\cap H)\\) for every codimension \\(1\\) subspace, does it follow that \\(vol(K) \\leq vol(L)\\)? After a bit of dramatic history, the problem was solved completely and the answer is affirmative if and only if \\(n \\leq 4\\) (for \\(n \\geq 10\\), a cube and a ball give a counter-example). Proving that \\(vol(K) \\leq C vol(L)\\) for a universal constant \\(C\\) would also solve the slicing problem in the affirmative. Another example concerns information theory: the slicing problem is equivalent to showing that the relative entropy per coordinate of every uniform distribution on a convex set does not exceed a universal constant. The links with information theory were also fruitful to establish unexpected connections between the slicing problem and other major open problems, such as the Kannan-Lov\u00e1sz-Simonovits conjecture (which in turn has its roots in devising efficient algorithms for computing volumes of convex sets).<\/p>\n Further reading Convex Sets in High Dimensions by Tomasz Tkocz This note briefly surveys several results, classical by now, which shaped high-dimensional convex geometry and describes its major open problems. We start with a closer look at Euclidean balls and then try to make a point that “in high-dimensions, all convex sets, despite their rich structure, behave […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":34,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_et_pb_use_builder":"on","_et_pb_old_content":"This note briefly surveys several results, classical by now, which shaped high-dimensional convex geometry and describes its major open problems. We start with a closer look at Euclidean balls and then try to make a point that ``in high-dimensions, all convex sets, despite their rich structure, behave a bit like Euclidean balls''.\r\n\r\nA set of points (A) in (R^n) is called convex if along with every two points (a_1, a_2) in (A), the whole segment ([a_1,a_2]) joining (a_1) and (a_2) is contained in the set (A). For example balls and ellipsoids, or cubes and parallelopipeds are convex, whereas annuli are not. How is volume distributed in a convex set? Say, we have a convex set of volume (1). Where is most<\/em> of its volume concentrated<\/em>?\r\n\r\nConsider the example of a centered Euclidean ball (B = {x in R^n, x_1^2+ldots+x_n^2 leq r^2}). Choose its radius (r) such that it has unit volume, (r = v_n^{-1\/n}), where (v_n) is the volume of the $n$-dimensional ball with radius (1). Thus, (r = frac{1}{sqrt{pi}}Gamma(1+frac{n}{2})^{1\/n}), which is approximately (sqrt{frac{n}{2pi e}}) for large (n). For (x in R), let (f(x)) be the ((n-1))-dimensional volume of the cross-section of (B) with a hyperplane perpendicular to the (0x_1) axis passing through ((x,0,ldots,0)). Plainly,\r\n[\r\nint_{-infty}^{infty} f(x) dd x = vol(B) = 1.\r\n]\r\nThe function (f) is the probability density of the volume distribution of the ball (B) in the direction of the vector ((1,0,ldots,0)). What is this distribution like? That cross-section is again a ball, whose radius is (sqrt{r^2-x^2}) (Pythagoras' theorem). Therefore,\r\n[\r\nf(x) = sqrt{r^2-x^2}^{n-1}v_{n-1} = left(1 - frac{x^2}{r^2}right)^{frac{n-1}{2}}r^{n-1}v_{n-1}\r\n]\r\nWe check that (r^{n-1}v_{n-1} approx sqrt{e}) for large (n) and when (x) is much smaller than (r), we can write (1-(x\/r)^2 approx e^{-(x\/r)^2}) and thus conclude that, approximately,\r\n[\r\nf(x) approx sqrt{e}e^{-pi e x^2}.\r\n]\r\nThis means that (f), the volume distribution in the ball (B) is roughly Gaussian with variance (sigma) of constant order ((sigma = frac{1}{2pi e}))! So, where is the volume concentrated? By the (3sigma)-rule, (int_{-3sigma}^{3sigma} f(x) dd x > 0.99), so more than (99%) volume of (B) is within a symmetric slab ({x in R^n, |x_1| leq 3sigma}) of width (6sigma). In high dimension (n), this width of constant order becomes tiny tiny in comparison with the radius (r) of (B), which is of the order (sqrt{n}). To challenge our high dimensional intuitions more, remark that the choice of the axis (0x_1) was arbitrary and by symmetry the above remains true for any other direction, so (99%) volume of (B) is within any symmetric slab of width (6sigma).\r\n\r\nLet us have a look at how much volume there is near the surface of (B), say in an annulus of the inner radius (r - 1\/sqrt{n}) and the outer radius (r), for some constant (C). Plainly, this volume equals\r\n[\r\n1 - left(frac{r-1\/sqrt{n}}{r}right)^n = 1 - left(1 - frac{1}{rsqrt{n}}right)^n approx 1 - e^{-frac{n}{rsqrt{n}}} approx 1 - e^{-sqrt{2pi e}} approx 0.98.\r\n]\r\nThis means that on one hand, almost all the volume of (B) is within any symmetric slab of constant width (hence also in the intersection of many of those), and on the other hand, almost all the volume of (B) is concentrated near its surface (in an annulus of width $1\/sqrt{n}$). \r\n\r\n\r\nAsymptotic convex geometry is concerned with quantifying such high dimensional phenomena for arbitrary convex sets. One of the major breakthroughs was Klartag's central limit theorem which guarantees that the same phenomenon which we observed above for the ball holds for an arbitrary convex set (properly normalised<\/em>): the distribution of volume (function (f)) is Gaussian along most<\/em> of directions. It was explained by Antilla, Ball and Peresinaki that such a central limit behavior comes from the volume being concentrated in a thin annulus, as readily observed above for the Euclidean ball. Klartag established this type of estimates, called thin-shell bounds, for an arbitrary convex set (K) in (R^n), showing that there are sequences (delta_n, varepsilon_n to 0) as (n to infty) such that\r\n[\r\nfrac{1}{vol(K)}volleft{x in R^n, 1-varepsilon_n leq frac{|x|}{sqrt{n}} leq 1+varepsilon_n right} geq 1 - delta_n,\r\n]\r\nprovided that (K) is properly normalised (its inertia matrix being the identity).\r\n\r\nHistorically, asymptotic convex geometry grew out of Dvoretzky's theorem, which says that (n)-dimensional symmetric convex sets admit sections with roughly (log n)-dimensional subspaces which are almost Euclidean balls. Interestingly, such Euclidean subspaces are not easy to find constructively, however, Milman's probabilistic proof of Dvoretzky's theorem shows that most subspaces yield Euclidean sections.\r\n\r\n\r\nOf course, many problems remain unsolved. A central one, the slicing problem posed by Bourgain, asks whether there is a universal constant (c) such that for every dimension (n), every (n)-dimensional convex set with volume (1) admits a codimension (1) section through its barycentre of volume at least (c). (Currently the best dimension dependent bound on (c) is of the order (n^{-1\/4})).\r\n\r\nThe slicing problem is equivalent to many other natural questions in convex geometry and beyond. For example, the Busemann-Petty problem asked the following: if symmetric convex sets (K) and (L) in (R^n) satisfy (vol(K cap H) leq vol(L cap H)) for every codimension (1) subspace, does it follow that (vol(K) leq vol(L))? After a bit of dramatic history, the problem was solved completely and the answer is affirmative if and only if (n leq 4) (for (n geq 10), a cube and a ball give a counter-example). Proving that (vol(K) leq C vol(L)) for a universal constant (C) would also solve the slicing problem in the affirmative. Another example concerns information theory: the slicing problem is equivalent to showing that the relative entropy per coordinate of every uniform distribution on a convex set does not exceed a universal constant. The links with information theory were also fruitful to establish unexpected connections between the slicing problem and other major open problems, such as the Kannan-Lov'asz-Simonovits conjecture (which in turn has its roots in devising efficient algorithms for computing volumes of convex sets).\r\n\r\n","_et_gb_content_width":"","footnotes":""},"class_list":["post-74","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages\/74","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/comments?post=74"}],"version-history":[{"count":75,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages\/74\/revisions"}],"predecessor-version":[{"id":1972,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages\/74\/revisions\/1972"}],"up":[{"embeddable":true,"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/pages\/34"}],"wp:attachment":[{"href":"https:\/\/magazine.mcs.cmu.edu\/math\/wp-json\/wp\/v2\/media?parent=74"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\\[
\n\\int_{-\\infty}^{\\infty} f(x) dd x = vol(B) = 1.
\n\\]<\/p>\n
\n\\[
\nf(x) = \\sqrt{r^2-x^2}^{n-1}v_{n-1} = \\left(1 – \\frac{x^2}{r^2}\\right)^{\\frac{n-1}{2}}r^{n-1}v_{n-1}
\n\\]
\nWe check that \\(r^{n-1}v_{n-1} \\approx \\sqrt{e}\\) for large \\(n\\) and when \\(x\\) is much smaller than \\(r\\), we can write \\(1-(x\/r)^2 \\approx e^{-(x\/r)^2}\\) and thus conclude that, approximately,
\n\\[
\nf(x) \\approx \\sqrt{e}e^{-\\pi e x^2}.
\n\\]<\/p>\n
\n\\[
\n1 – \\left(\\frac{r-1\/\\sqrt{n}}{r}\\right)^n = 1 – \\left(1 – \\frac{1}{r\\sqrt{n}}\\right)^n \\approx 1 – e^{-\\frac{n}{r\\sqrt{n}}} \\approx 1 – e^{-\\sqrt{2\\pi e}} \\approx 0.98.
\n\\]
\nThis means that on one hand, almost all the volume of \\(B\\) is within any symmetric slab of constant width (hence also in the intersection of many of those), and on the other hand, almost all the volume of \\(B\\) is concentrated near its surface (in an annulus of width $1\/\\sqrt{n}$).<\/p>\n
\n\\[
\n\\frac{1}{vol(K)}vol\\left\\{x \\in R^n, \\ 1-\\varepsilon_n \\leq \\frac{|x|}{\\sqrt{n}} \\leq 1+\\varepsilon_n \\right\\} \\geq 1 – \\delta_n,
\n\\]
\nprovided that \\(K\\) is properly normalised (its inertia matrix being the identity).<\/p>\n
\nGiannopoulos, A., Milman, V., Asymptotic
\nconvex geometry: short overview.
\nDifferent Faces of Geometry, 87-162, Int. Math. Ser. (N. Y.), 3, 2004.<\/em>
\n[\/et_pb_text][\/et_pb_column][et_pb_column type=”1_3″ _builder_version=”3.25″ custom_padding=”|||” global_colors_info=”{}” custom_padding__hover=”|||”][et_pb_blurb image=”https:\/\/magazine.mcs.cmu.edu\/math\/wp-content\/uploads\/sites\/2\/2018\/12\/tkocz_drawing1.png” _builder_version=”4.13.0″ global_colors_info=”{}”]Figure 1: Volume distribution is Gaussian.<\/em>
\n[\/et_pb_blurb][et_pb_blurb image=”https:\/\/magazine.mcs.cmu.edu\/math\/wp-content\/uploads\/sites\/2\/2018\/12\/tkocz_drawing2.png” _builder_version=”4.13.0″ global_colors_info=”{}”]Figure 2: Most of volume is in any slab and near the surface.<\/em>
\n[\/et_pb_blurb][et_pb_blurb image=”https:\/\/magazine.mcs.cmu.edu\/math\/wp-content\/uploads\/sites\/2\/2018\/12\/tkocz_drawing3.png” _builder_version=”4.13.0″ global_colors_info=”{}”]Figure 3: In a convex set in high dimensions volume decays exponentially in almost every direction and concentrates in a thin shell<\/em>
\n[\/et_pb_blurb][\/et_pb_column][\/et_pb_row][\/et_pb_section][et_pb_section fb_built=”1″ _builder_version=”3.22″ background_color=”#e0e0e0″ custom_padding=”30px|0px|30px|0px|false|false” global_colors_info=”{}”][et_pb_row column_structure=”1_2,1_2″ _builder_version=”3.25″ custom_padding=”0|0px|0|0px|false|false” global_colors_info=”{}”][et_pb_column type=”1_2″ _builder_version=”3.25″ custom_padding=”|||” global_colors_info=”{}” custom_padding__hover=”|||”][et_pb_button button_url=”\/math\/2018-2\/new-faculty\/” button_text=”Math at CMU Welcomes Three New Faculty Members” _builder_version=”4.13.0″ custom_button=”on” button_text_color=”#00687f” button_border_width=”0px” button_font=”||||||||” button_icon=”#||divi||400″ button_icon_color=”#00687f” button_icon_placement=”left” button_on_hover=”off” global_colors_info=”{}” button_text_size__hover_enabled=”off” button_one_text_size__hover_enabled=”off” button_two_text_size__hover_enabled=”off” button_text_color__hover_enabled=”off” button_one_text_color__hover_enabled=”off” button_two_text_color__hover_enabled=”off” button_border_width__hover_enabled=”off” button_one_border_width__hover_enabled=”off” button_two_border_width__hover_enabled=”off” button_border_color__hover_enabled=”off” button_one_border_color__hover_enabled=”off” button_two_border_color__hover_enabled=”off” button_border_radius__hover_enabled=”off” button_one_border_radius__hover_enabled=”off” button_two_border_radius__hover_enabled=”off” button_letter_spacing__hover_enabled=”off” button_one_letter_spacing__hover_enabled=”off” button_two_letter_spacing__hover_enabled=”off” button_bg_color__hover_enabled=”off” button_one_bg_color__hover_enabled=”off” button_two_bg_color__hover_enabled=”off”][\/et_pb_button][\/et_pb_column][et_pb_column type=”1_2″ _builder_version=”3.25″ custom_padding=”|||” global_colors_info=”{}” custom_padding__hover=”|||”][et_pb_button button_url=”\/math\/2018-2\/jim-greenberg-memoriam\/” button_text=”In Memoriam: Jim Greenberg” button_alignment=”right” _builder_version=”4.13.0″ custom_button=”on” button_text_color=”#00687f” button_border_width=”0px” button_font=”||||||||” button_icon=”$||divi||400″ button_icon_color=”#00687f” button_on_hover=”off” global_colors_info=”{}” button_text_size__hover_enabled=”off” button_one_text_size__hover_enabled=”off” button_two_text_size__hover_enabled=”off” button_text_color__hover_enabled=”off” button_one_text_color__hover_enabled=”off” button_two_text_color__hover_enabled=”off” button_border_width__hover_enabled=”off” button_one_border_width__hover_enabled=”off” button_two_border_width__hover_enabled=”off” button_border_color__hover_enabled=”off” button_one_border_color__hover_enabled=”off” button_two_border_color__hover_enabled=”off” button_border_radius__hover_enabled=”off” button_one_border_radius__hover_enabled=”off” button_two_border_radius__hover_enabled=”off” button_letter_spacing__hover_enabled=”off” button_one_letter_spacing__hover_enabled=”off” button_two_letter_spacing__hover_enabled=”off” button_bg_color__hover_enabled=”off” button_one_bg_color__hover_enabled=”off” button_two_bg_color__hover_enabled=”off”][\/et_pb_button][\/et_pb_column][\/et_pb_row][\/et_pb_section]<\/p>\n","protected":false},"excerpt":{"rendered":"