Def : We will use the terminology set in
equidistance $\{y_i\}_{i=1}^l$ if
$$\| y_i-y_j\| =\|y_1-y_2\|$$ for all $i\neq j$ and we can not add
more point. Here if $l$ is largest, then we call it maximal and if $l$ is smallest, then we use minimal.
Question : What is the size $h_{n,p}$ of maximal
set in equidistance in
$$(\mathbb{R}^n,\|\ \|_p),\ 1\leq p\leq \infty\ ?$$ And
$l_{n,p}$ for minimal set ?
EXE1 : i) $$ h_{2,p}=l_{2,p}=3,\ 1<p<\infty $$
$$ l_{2,1}=l_{2,\infty}=3,\ h_{2,1}=h_{2,\infty }=4$$
ii) In further, $h_{n,\infty}=2^n$.
Def : A center of Voronoi domains is a point $c$ if
$$ \| y_i-c\| =\| y_1-c\| $$
EXE2 : i) If $\{y_i\}$ is a set of equidistance $2$, then
Voronoi domains contains a unit ball.
ii) Voronoi domain has a center.
Proof of ii) : Assume that $$ \bigcap_{i=1}^k\ V_i \ni z,\
V_1\bigcap V_j=\emptyset,\ j>k $$
If $c(t)=ty_1+(1-t)y_{k+1}$, then $$ c|(\epsilon, \varepsilon
)\subset \bigcup_{i=2}^k\ V_i $$
Since $V_i$ contains unit ball, $$ 2\leq \| y_{k+1}
-c(\epsilon ) \| +\| c( \varepsilon )-y_1\| < \| y_1-y_{k+1} \| $$
EXE3 : Prove that $$l_{n,p}\geq n+1$$ for any $1\leq p\leq \infty$
Proof : Assume that $H$ is $n-1$ dimensional hyperplane
for $\mathbb{R}^n$ and any two points in $ \{y_i\}_{i=1}^n$ in $H$
has distance $2$. Then we have a claim that there is $y_{n+1}\in
\mathbb{R}^n$ s.t. any two points in $\{y_i\}_{i=1}^{n+1}$ has a
distance 2. We will prove by an induction.
Step 1 : Define $$ F: H\rightarrow \mathbb{R}^n,\
F(x)=(\|x-y_1\|,\cdots,\|x-y_n\|) $$
Consider Theorem 19.1.3 in [1] :
$$ U =\{ y| y\succeq q,\ {\rm some}\ q\in F(H)\} $$ where $y\succeq
q$ iff
$y_i\geq q_i,\ \forall i$.
If $p,\ q\in U$, then there is $p',\ q'\in F(H)$ s.t. $p\succeq p',\
q\succeq q'$. Hence $$ tp+(1-t)q\succeq tp' +(1-t)q'
$$
Then $U$ is convex and $\partial U$ is convex hypersurface.
Step 2 : By definition of $F$, $F(H)$ is closed so that $U$ is closed.
Step 3 : Note
that there is a
center $x_0 \in H$ s.t. $$
\| x_0-y_i\|=\|x_0-y_1\|:=\varepsilon$$ for all $i$.
Then $U$ contains $$
\{ t(\varepsilon,\cdots,\varepsilon)|t\geq 1\}$$
If $c(T)=x_0 + T \frac{y_1-x_0}{\| y_1-x_0\|}$, then triangle
inequality implies $$ T-\varepsilon\leq \| c(T)-y_i \| \leq
T+\varepsilon $$ for all $i$.
EXE4 : i) $ l_{n,1} =n+1,\ n\geq 3$ : $e_i$ and
$\frac{1}{n-2} \sum_{i=1}^n\ e_i $.
ii) $l_{n,\infty}=n+1$ :
$$x_0=(0,0,\cdots,0),\ x_1=(2,0,\cdots,0),\ x_2=(1,2,0,\cdots,0), $$ $$
x_i=(1,\cdots,1,\underbrace{2}_{i-{\rm th\ coordinate}},0,\cdots ,0)
$$
EXE5 : If $\{y_i\}_{i=1}^{l}$ is a set of equidistance $2$
in $(\mathbb{R}^n,\|\ \|)$ and if $ {\rm dim}\ {\rm conv}\
\{y_i\}=n$, then $y_i$ is a vertex in ${\rm conv}\ \{y_i\}$.
Proof : If $y_1$ is an \textit{interior} point in ${\rm
conv}\ \{y_i\}_{i=2}^l$, then define $$ f(x)=\sum_{i=2}^l \
\|x-y_i\|_2^2$$
Here $ f(y_1)=4(l-1)$. If $x$ is a point of $[y_1y_2]$ with $\|
x-y_1\|=\epsilon$, then convexity of distance function implies $$ \| y_i-x\|\leq 2$$ for
$i>2$.
That is, $$ f(x) \leq 4(l-2)+(2-\epsilon)^2 < f(y_1) $$
for a small $\epsilon >0$. We can do the same for direction
$\overrightarrow{y_1y_i}$ for $i>2$.
Hence $y_1$ is a strict local maximum, since $f$ is convex.
EXE6 : Fix a set of equidistance $2\ \{y_i\}_{i=1}^l,\
l\geq n+2$ in $\mathbb{R}^n$.
Then there is $4\leq k\leq l$ s.t. $$ [y_1y_2] \subset {\rm int\ conv}
\ \{ y_i\}_{i=1}^k ,\ {\rm dim\ conv}
\ \{ y_i\}_{i=1}^k =k-1 $$
Proof : We will prove by an induction. Hence by EXE5, we can assume that
$$S:=
\partial\ C,\ C:=
{\rm conv}\ \{y_1,\cdots, y_{n+1} \} $$
Here ${\rm dim}\ C=n$ and $y_{n+2}$ is not in $C$.
By $
y_{ n+2}$, $S$ is divided into two regions, bright and dark (cf. Similar notions are used
in [2], [3]) :
If a segment $[y_{n+2} x]$ for $x\in S$ does not contain an interior point of $
C$, then $x$ is in the bright.
If the bright region is exactly one $n-1$
dimensional face of $C$, then there exists a vertex $y_i$ in the
dart s.t. $[y_{n+2}y_i]$ is
desired.
If $f,\ g$ are $n-1$ dimensional face of $C$ and
${\rm int}\ f,\ {\rm int}\ g$ intersect the bright s.t. $f\bigcap
g\neq \emptyset$,
then the bright contains an edge. Then we are done.
EXE7 : Prove that $$ h_{n,p}\leq n+1,\
1<p<\infty$$
Proof : By previous, $[y_1y_2]$ penetrates $n-1$
dimensional ${\rm conv}\ \{y_i\}_{i=3}^{n+2}$.
If $V_i$ is Voronoi domain for $y_i$, then clearly $$
[y_1y_{2}]\subset V_1\bigcup V_{2} $$
If $c$ is a center for $\{y_i\}_{i=1}^{n+2}$, then it must be a
midpoint of $[y_1y_{2}]$ so that $\| y_i-c\|=1$. It is a contradiction.
EXE8 : $h_{n,1}=2n$.
Proof : If $\{y_i\}_{i=1}^l,\ l\geq n+2$ is a set of
distance 2 in
$(\mathbb{R}^n,\|\ \|_1)$, then there is a point $o$ s.t.
$\|y_i-o\|_1=1$ by a proof of the previous exercise. Hence we complete the proof by some argument.
Reference :
[1] S. Alexander, V. Kapovitch and A. Petrunin, Alexandrov
geometry, July 30, 2016.
[2] N. Lebedeva and A. Petrunin, On
the total curvature of minimizing geodesics on convex surfaces,
arXiv:1511.07911v2 [math.DG] 26 Jun 2016
[3] M. Ghomi, Shadows and convexity of surfaces, Annals of
Mathematics, 155 (2002),
281--293
