What location on a hypersphere maximizes the Manhattan distance of the radius?

Question

In two dimension picture a unit circle. While the distance of the radius is constantly one, the Manhattan distance of the radius at zero degrees is equal to 1 while the Manhattan distance at 45 degrees is $\frac{\sqrt{2}}{2}+\frac{\sqrt{2}}{2}\approx1.41$. Thus for a circle the difference between the minimum and maximum Manhattan distance is about 0.41. I am curious how this difference changes for higher dimensions. I know the minimum Manhattan distance will remain one, however, I am stumped how to find the maximum even for the sphere...I feel like it should just be a simple calculus exercise. I would appreciate any helping in setting up the solution for the sphere, and even better a general solution for a hypersphere!

I'm guessing that the difference continues to increase with dimension but asymptotically approaches some limit. Happy New Years!

Answer 1

Do you know minimisation of multi-variable functions over given sets?

Your problem is essentially asking to maximise and minimise $f(x) = \sum_j x_j$ (the Manhattan distance, $x_j$ are the components of the vector $x$) on the set $$ M := \{x\in\mathbb{R}^n : x_j\geq 0 \text{ for all $j$ and } ||x||=1\} $$ It is enough to consider $M$ instead of the entire hypersphere by, well, spherical symmetry (pun intended).

This can happen either on the boundary (where, in this case, you will have the minimum) of the set or wherever $\nabla f(x) = \left(\frac{\partial f(x)}{\partial x_1},\ldots,\frac{\partial f(x)}{\partial x_n}\right)$ is orthogonal to $M$. Since $M$ is part of a sphere, this is equivalent to $$\nabla f(x) = \lambda x$$ for some $\lambda\in\mathbb{R}$ (why?). This you can transform to a system of linear equations which you can solve. Do you think you can take it from here?

Answer 2

While my solution is not as general or robust as whats outlined above; I used Tobius's answer as a blueprint for my solutions, and the results are kind of neat!

I implemented Tobius's approach in 3-dimensions because it helped me wrap my head around what the solution process looked like:

$f(x_1,x_2,x_3)=x_1+x_2+x_3$ subject to the constraint on set M that $g(x_1,x_2,x_3) = 1-x_1^2-x_2^2-x_3^2=0$. So then if we have a solution of the form above it looks like $\nabla(f-\lambda g)=0$ Which gives us the following sets of equations $$ 1-2\lambda x_1 = 0 $$ $$ 1-2\lambda x_2 = 0 $$ $$ 1-2\lambda x_3 = 0 $$ $$ 1-x_1^2-x_2^2-x_3^2 = 0 $$

Solving gives us $\lambda =\sqrt{3}/2$, and $x_1,x_2,x_3,=\sqrt{3}/3$ and thus the total manhatten distance is $\sqrt{3}$. In general this tells us that the maximal manhatten distance for the radius of a hypersphere of dimension n is just $\sqrt{n}$.

Thus the difference between the maximum and minimal manhatten distance of the radius of a hypersphere actually increase to infinity like $\sqrt{n}$ as dimensions increase to inifnity! Which I suppose isn't too surprising because with infinite dimensions the manhatten distance should be infinite for any non_zero radius...