Skip to content Mastodon

Notes and Tones

Oranges in Many Dimensions

Peeling oranges in high dimensionality k 3 is hard. This post discusses a fundamental phenomenon in asymptotic geometry and explains at which rate you should peel an orange.

Suppose we have a special branch of hyper-orange existing in d 1 and we would like to peel such that 95% of pulp is preserved. We will denote the volume of an Lp norm in d dimensions, that is C = {x d xp r}, as VC = Vp,d. Because we first deal with balls we have p = 2 and set by default V2,d = Vd.

We first look at ratios of volume of balls radii scaled by φ such that Vd(φr)Vd(r) = 0.95. For d {1,2,3} we know from middle school that V1(r) = 2r, V2(r) = πr2 and V3(r) = 4 3πr3, and hence φ1,2,3 = 0.951,2,3. For d > 3 we need some material from real analysis to work out the volume.

Volume of n-ball Exponential Function

One proof works with two observations: first scaling area identity An1(r) = rn1An1(1) and evaluates the integral for rotational invariant function f(x1,,xd) = exp(x12 xd2).

On the one side, we have

df(x1,,xd)dx1dxd = exp(x12)dx 1 exp(xd2)dx d = πd2

On the other side, isolating one variable and applying the area identity

df(x1,,xd)dx1dxd =0Sn1(r) exp(r2)dAdr =0A n1(1)rd1 exp(r2)dr = An1(1)0exp(r2)rd1dr = 1 2An1(r)Γ(d 2).

Solving for the d 1 dimensional area we get Ad1(1) = 2πd2 Γ(d2) and substituting into the volume formula, we get the desired Vd(R) = πd2Rd d 2 Γ(d2).

Consequence for Peeling Oranges

Now consider the volume of two balls Vd(1), Vd(1 𝜀) and compare their volume

Vd(1 𝜀) Vd(1) = (1 𝜀)d.

Then, for every constant 𝜀 the ratio tends to zero, and we are left with no pulp at all! Realizing that for 𝜀 d1, the limit yields exponential function

Vd(1 𝜀) Vd(1) = (1 M d )d exp(M) for d ,

we should peel (log0.95)d of the skin to get a fair share of pulp for high dimensions.

Consequence for Approximating Norms

Let’s pack the orange into a box. For simplicity we assume that the box has side length 1 and recognize that an d-cube is described with the maximum norm. The volume of such a box is V,d = 1d = 1, and comparing that to the volume of our orange

V2,d V,d = πd2 d 2Γ(d2)1

Express this in log-space and use log-gamma approximation logΓ(z) (z 1 2)logz z + 1 2 log(2π)

log V2,d V,d = d 2logπ log d 2 logΓ(d 2) d 2log 2πe d 1 2log2πd d 2log 2πe d

which turns negative once d > 2πe and grows linear in the dimensionality. Hence, the fraction diminishes exponentially fast. That means for large d we can pack exponential many oranges into a single box!