25
$\begingroup$

My question is inspired by another question that was asked here.

Question

How many points $x_1,x_2,\dots,x_m \in \mathbb{R}^n$ can I find such that $\|x_i-x_j\|_p = 1$ for all $i\neq j$.

For $p=2$ the answer is $n+1$. you can find the prove in the thread of my inspiration. However I though that the result holds for an arbitrary $p\in[1,+\infty]$. Then I found a counterexample for $p=1$ and $p=\infty$:

you can choose the points \begin{align*} x_1 = \left(\begin{matrix} 0 \\ 0\end{matrix}\right),\; x_2 = \left(\begin{matrix} 1 \\ 0\end{matrix}\right),\; x_3 = \left(\begin{matrix} 0 \\ 1\end{matrix}\right)\;\text{and}\; x_4 = \left(\begin{matrix} 1 \\ 1\end{matrix}\right) \end{align*} then you have four points in $\mathbb{R}^2$ which fulfill $\|x_i-x_j\|_\infty = 1$ for $i\neq j$.

There is a very similar example for $p=1$. I think that this follows from the special geometry of the balls in these norms. So I think there are three cases

  1. $p = 1$
  2. $p = \infty$
  3. $p \in (1,+\infty)$

In the first case I think the solution is $m\leq 2n$ in the second it is $m\leq 2^n$ and in the third $m\leq n+1$. Unfortunately I couldn't prove it maybe someone has a tipp.

Update

I found out that the cases $p=1$ and $p=\infty$ have different solutions as I already have edited. I can also prove that my guesses are lower bounds for the maximum of points that can exist. One has just to regard the corners of a ball $B_r(x)$ with radius $r=\frac{1}{2}$ in the desired norm.

$\endgroup$
4
  • $\begingroup$ For $p=\infty$: any set of diameter $1$ is contained in a ball of radius $\tfrac12$ (project on the coordinate axes ad take the midpoints of the projections); wlog the center is $0$. By assumption $B(x_i,\tfrac12)$ are disjoint, and their union is contained in $B(0,1)$. The related volume estimate gives $m\leq 2^n$. $\endgroup$
    – Del
    Commented Jan 4, 2018 at 21:09
  • $\begingroup$ Related: the same question just for $p=1$ math.stackexchange.com/questions/1341076/… $\endgroup$
    – Del
    Commented Jan 4, 2018 at 21:51
  • $\begingroup$ @Del I guess I understand your argument. Therefore, the problem is solved for $p=\infty$. Thanks :) $\endgroup$ Commented Jan 5, 2018 at 10:53
  • $\begingroup$ It looks like there could be something useful here, though I couldn't see a direct answer to your question: doi.org/10.1016/S0195-6698(13)80131-X $\endgroup$
    – stewbasic
    Commented Jan 12, 2018 at 3:04

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ Why does following the gradient of $f_2$ ensure $\|a-y_1\|$ decreases? Also it seems you make several arguments for $\|\,\|_2$ and then remark that they carry over to other values of $p$; I think it would be clearer to make the argument in the generality you need from the start. $\endgroup$
    – stewbasic
    Commented Jul 13, 2018 at 3:16
  • $\begingroup$ For the gradient of $f_2$, I modified. $\endgroup$
    – HK Lee
    Commented Jul 15, 2018 at 13:01
  • 1
    $\begingroup$ @HKLee: It looks like this also answers my earlier question: math.stackexchange.com/q/1341076/16420. Can you please confirm? $\endgroup$
    – krlmlr
    Commented May 23, 2020 at 2:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .