7
$\begingroup$

Consider unit vectors $|v_i \rangle$ on an $n$ dimensional vector space, which obey the following relation:

$$\langle v_i|v_i \rangle =1 \quad \& \quad |\langle v_i|v_j \rangle| \leq \epsilon, \quad i \neq j.$$

Note that this implies that if $|v_i \rangle = (a_1, a_2 ... a_n)$, then each $|v_i \rangle$ lies on an $(n-1)$ dimensional sphere of unit radius,

$$a_1^2 + a_2^2 + ... + a_n^2 =1$$

If $\epsilon =0,$ the maximum number of such vectors $|v_i \rangle$ with which we can satisfy the inner product conditions is trivially $n$. However consider a finite but a small $\epsilon$.

My Question: I want to demonstrate(/or verify) using Mathematica via some explicit construction that there can be many more vectors than say, $n=700$ which obey this condition if $\epsilon \neq 0$, and if possible, approximately determine the maximum number of such vectors which can be embedded on the $(n-1)$ dimensional sphere.

One way to do this is to start iteratively. The first vector can be at some point

$$|v_1 \rangle = (1, 0 ... 0),$$

Therefore the second vector is will have $a_1^2 \leq \epsilon^2$ using the inner product relation. If we assume equality for the second condition in the inner product. Therefore the second vector will have $a_1^2 = \epsilon^2$ and

$$a_2^2 + a_3^2 ... + a_n^2 = 1-\epsilon^2.$$

Is there a way I can implement this iterative procedure and arrive at the maximum number of vectors for say, $n \sim 700$ and by assuming equality in the second condition of the inner product? I want to demonstrate(/or verify) using Mathematica via some explicit construction that there can be many more vectors than $n=700$ if $\epsilon \neq 0$.

EDIT: Also see my linked question.

$\endgroup$
4
  • 3
    $\begingroup$ Is this a question about Mathematica the software by Wolfram Research or is this a pure math question? In the latter case you should ask this on Mathematics $\endgroup$
    – b3m2a1
    Jan 13 '20 at 19:21
  • 1
    $\begingroup$ @b3m2a1 I have an approximate mathematical solution to this problem. However I want to verify my solution using Mathematica, and I am not very proficient using the same so I asked the question. That is why I repeatedly mentioned the words, "demonstrate via some explicit construction". $\endgroup$
    – Bruce Lee
    Jan 13 '20 at 19:30
  • 1
    $\begingroup$ @BruceLee it would be beneficial to edit that to “demonstrate(/or verify) using Mathematica” $\endgroup$ Jan 14 '20 at 13:44
  • 1
    $\begingroup$ @CATrevillian Done, thanks. $\endgroup$
    – Bruce Lee
    Jan 15 '20 at 18:34
4
+100
$\begingroup$

Not a solution but an extended comment with a speculative answer to a different problem. Let's look for the maximum number $m$ of unit vectors that can be arranged in $n$ dimensions such that $\vec{p}_i\cdot\vec{p}_j\le\epsilon$. Notice I removed the absolute value in the scalar product. We call this function $\hat{m}_n(\epsilon)$. Let's study all the values of $\hat{m}_n(\epsilon)$ that we know exactly.

regular polyhedra

regular polyhedra in $n$ dimensions

Looking at regular convex polytopes in $n$ dimensions, there are three kinds:

  • Simplex: the distance between any two vertices is the same. Examples: equilateral triangle ($n=2$), tetrahedron ($n=3$). An $n$-simplex has $m=n+1$ vertices, and the scalar product between the position vectors of neighboring vertices is $\vec{p}_i\cdot\vec{p}_j=-\frac{1}{n}$. So $\hat{m}_n(-\frac{1}{n})=n+1$.

  • Orthoplex: one point in each Cartesian direction: $(\pm1,0,0,\ldots,0), (0,\pm1,0,\ldots,0), (0,0,\pm1,\ldots,0), \ldots$. Examples: square ($n=2$), octahedron ($n=3$). An $n$-orthoplex has $m=2n$ vertices, and the scalar product between the position vectors of neighboring vertices is $\vec{p}_i\cdot\vec{p}_j=0$. So $\hat{m}_n(0)=2n$.

  • Hypercube: coordinates $(\pm1,\pm1,\pm1,\ldots)/\sqrt{n}$. Examples: square ($n=2$), cube ($n=3$). An $n$-hypercube has $m=2^n$ vertices, and the scalar product between the position vectors of neighboring vertices is $\vec{p}_i\cdot\vec{p}_j=1-\frac{2}{n}$. So $\hat{m}_n(1-\frac{2}{n})=2^n$.

regular polyhedra in $n=2$ dimensions

Looking at $n=2$, we further have all regular polygons with any number $m$ of vertices, and the scalar product between the position vectors of neighboring vertices is $\vec{p}_i\cdot\vec{p}_j=\cos(\frac{2\pi}{m})$. So $\hat{m}_2(\cos(\frac{2\pi}{m}))=m$, or $\hat{m}_2(\epsilon)=\frac{2\pi}{\cos^{-1}(\epsilon)}$.

regular polyhedra in $n=3$ dimensions

Looking at $n=3$, we further have $\hat{m}_3(\frac{1}{\sqrt{5}})=12$ (icosahedron), $\hat{m}_3(\frac{\sqrt{5}}{3})=20$ (dodecahedron).

regular polyhedra in $n=4$ dimensions

Looking at $n=4$, we further have $\hat{m}_4(\frac12)=24$ (24-cell), $\hat{m}_4(\frac{1+\sqrt{5}}{4})=120$ (600-cell), $\hat{m}_4(\frac{1+3\sqrt{5}}{8})=600$ (120-cell).

limit $m\to\infty$

Further, for $m\to\infty$ we can make a geometric approximation. Assume the $m$ unit vectors will be distributed homogeneously over the surface of the unit $n$-sphere, which has a surface area of $2\pi^{n/2}/\Gamma(\frac{n}{2})$. So each unit vector's tip has an associated Voronoi volume (environment bubble) of $\frac{2\pi^{n/2}}{m\Gamma(\frac{n}{2})}$. If we assume that these environment bubbles are roughly hyperspherical with radius $r$, they have a volume (in $n-1$ dimensions) of $\frac{\pi^{\frac{n-1}{2}}}{\Gamma(\frac{n+1}{2})}r^{n-1}$, which gives $r\approx\left(\frac{2\sqrt{\pi}\Gamma(\frac{n+1}{2})}{m\Gamma(\frac{n}{2})}\right)^{\frac{1}{n-1}}$ and a mean distance between nearest neighbors of $d\approx2r$. This means that the scalar product between nearest neighbors is approximately $\vec{p}_i\cdot\vec{p}_j\approx1-\frac12d^2=1-2\left(\frac{2\sqrt{\pi}\Gamma(\frac{n+1}{2})}{m\Gamma(\frac{n}{2})}\right)^{\frac{2}{n-1}}$. Solving this formula for $m$, we get the limiting behavior $\hat{m}_n(\epsilon)\approx 2^{n/2}\frac{\sqrt{2\pi}\Gamma(\frac{n+1}{2})}{\Gamma(\frac{n}{2})}(1-\epsilon)^{-\frac{n-1}{2}}$ for $\epsilon\to1$ (i.e., for $0<1-\epsilon\ll1$).

assemble everything

Let's put all of these points on a log-plot (omitting the $m\to\infty$ data):

enter image description here

It looks like for small $n$ the number of fittable vectors scales exponentially with $\epsilon$: for $\lvert\epsilon\rvert\ll1$ I would guesstimate something like

$$ \hat{m}_n(\epsilon)\approx2n\left(\frac{2n}{n+1}\right)^{n\epsilon} $$

which fits the simplex and orthoplex formulas exactly and extrapolates exponentially to small values of $0<\epsilon\ll1$, finally getting the hypercube formula almost right (overestimating it by a small factor of $\frac{n}{2e}$):

(* approximation of the maximum number of vectors *)
M[n_, ε_] = 2n*((2n)/(n+1))^(n*ε);

(* validate simplex formula *)
M[n, -1/n]
(*    1 + n    *)

(* validate orthoplex formula *)
M[n, 0]
(*    2 n    *)

(* validate hypercube formula (approximately *)
Limit[M[n, 1 - 2/n]/(n/(2E)*2^n), n -> ∞]
(*    1    *)

For $n=700$ this formula would mean approximately the following very steep dependency on $\epsilon$:

enter image description here

$\endgroup$
5
  • $\begingroup$ Hi, Thanks for your answer. I am looking for the $ \epsilon >0, \epsilon \ll 1$ case in your problem, and my derived estimation is similar to what you have found out, with an exponential behaviour. My question is this: Just like you pointed out that there are explicit regular polyhedra solutions for the $\epsilon \sim 1$ case (the hypercube ones), can one construct explicitly solutions for $ \epsilon >0, \epsilon \ll 1$ case which would have a very large number of vectors? $\endgroup$
    – Bruce Lee
    Jan 18 '20 at 11:41
  • $\begingroup$ I want a demonstration in which this is actually true for say $n \sim 10^3$ so that I can actually trust my (as well as your) results. Say with a particular choice of $\epsilon$ close to zero we can actually fit in some $n\sim 10^4/10^5$ vectors. $\endgroup$
    – Bruce Lee
    Jan 18 '20 at 11:48
  • $\begingroup$ Let's say that my first vector is placed at (1,0,0....). Therefore I need to place my second vector $(a_1, a_2, a_3....a_n) $ outside the hypersphere $a_2^2 + a_3^2 ... + a_n^2 = 1-\epsilon^2.$ Can you use this to construct up the solution by iteratively putting the vectors up, just like for the case of the regular polyhedra? Can one fit $m \sim 10^4/10^5$ number of vectors if the dimensionality of the space is $n \sim 10^3$? $\endgroup$
    – Bruce Lee
    Jan 18 '20 at 12:02
  • $\begingroup$ @BruceLee note that I wrote this as "a speculative answer to a different problem" because I left out the absolute values around the scalar product. $\endgroup$
    – Roman
    Jan 18 '20 at 14:02
  • $\begingroup$ Thanks for your nice answer Roman. :) $\endgroup$
    – Bruce Lee
    Jan 21 '20 at 13:20
4
$\begingroup$

Complete rewrite of my answer...a counter-example.

Consider an hypersphere with unit radius embedded in an $n$- dimensional space, and consider a regular simplex inside the sphere with vertices on the sphere. The simplex will have the following properties:

  1. the simplex will have $n+1$ vertices (and vectors to those vertices from the origin)
  2. the angles (and dot products) between each of the vectors will be the same
  3. the absolute value of the dot product between the vectors will simply be $1/n$

So in order to have even just n+1 vectors satisfying your relationship, you have to have $\epsilon > 1/n$.

** EDIT **

As an experiment, here is code to treat positioning the points around the hypersphere as an energy minimizing problem.

Define a function that models a repelling force on a point from another point, with no force of the point from itself. Note the parameters α, β, which will impact the algorithm's performance. The potential energy is minimized when the points are evenly distributed.

α = 100;
β = 4;
push[p1_, p2_] := If[p1 != p2, p1 + α (p1 - p2)/((p1 - p2).(p1 - p2))^β, p1];

A function which moves the points, hopefully spreading them around the sphere. It first pushes them to a new position that is not on the sphere, then normalizes them to the sphere.

spread[pts_] := Map[Normalize, (Outer[push[#1, #2] &, pts, pts, 1]//Transpose//Total)];

To check the results, define a function to find the maximum dot product between all the vectors.

maxDot[pts_] := Map[Dot[#[[1]], #[[2]]] &, Permutations[pts, {2}]] // Max;

Now create an initial spread of points and run it...it rapidly converges to the ideal of -0.02 for a simplex.

Set the dimension n and the number of points m

n = 50;
m = 51;
pts = RandomPoint[Sphere[n], m];

res = NestList[spread[#] &, pts, 200];
dots = Map[maxDot, res];
ListPlot[dots, Frame -> True, GridLines -> Automatic]

enter image description here

Try it with the orthoplex. We expect a max dot product of zero.

n = 20;
m = 40; (* = 2 n *)
pts = RandomPoint[Sphere[n], m];
res = NestList[spread[#] &, pts, 200];
dots = Map[maxDot, res];
ListPlot[dots, Frame -> True, GridLines -> Automatic]

enter image description here

One more, for the hypercube. We expect the max dot to be <=(1-2/n). Had to reduce α and β to get it to work.

α = 1;
β = 1;
n = 6;
m = 2^n;
pts = RandomPoint[Sphere[n], m];
res = NestList[spread[#] &, pts, 300];
ListPlot[dots, Frame -> True, GridLines -> Automatic]

enter image description here

The code could definitely be optimized.

One more graphic, watching the points disperse. Started them all in the positive quadrant, greatly reduced α to slow convergence.

α = .1;
β = 1;
n = 3;
m = 100;
pts = Abs@RandomPoint[Sphere[n], m];
res = NestList[spread[#] &, pts, 50];
anim = ListAnimate[ListPointPlot3D[#, AspectRatio -> Full, 
 PlotRange -> {{-1, 1}, {-1, 1},{-1,1}}] & /@ res]

enter image description here

$\endgroup$
1
  • $\begingroup$ Yes precisely. Now let's take $n$ to be very large. Is there a demonstration where you can get the maximum number of vectors to be very large with some non zero $\epsilon$? $\endgroup$
    – Bruce Lee
    Jan 18 '20 at 11:55
3
$\begingroup$

Not sure if I'm missing something here, but assuming your vector space is Euclidean it seems to me that for small $\epsilon$ the number of such vectors is still $n$. Here my thoughts:

For $\epsilon=0$, we can pick a particular basis of $n$ such vectors, say $$|v_i\rangle=\vec{e}_i=\delta_{i,j}~~~,~~~i,j=1,2,...,n$$

If we relax $0<\epsilon\ll1$, the possibly slightly deformed vectors $\vec{e}_i+\mathcal{O}(\epsilon)$ are still in the set of admissible vectors and one representative of such slight deformation must be included in this case as well (alternatively, any orthogonal transformation of the original set $\vec{e}_i$ can be used of course, but a redefinition of the coordinate system orientation can always be used to recover the original simple system $\vec{e}_i$ above). Looking for a new vector $|w\rangle$ such that $$|\langle w|v_i\rangle|<\epsilon~~~\text{and}~~~\langle w|w\rangle=1$$ we encounter the problem that the $n$ vectors $|v_i\rangle=\vec{e}_i +\mathcal{O}(\epsilon)$ also are approximate projectors onto the respective specific axes in the $n$ dimensional vector space. This creates a contradiction, since to have $$\langle w|w\rangle=1$$ at least one vector component of $|w\rangle$ must be $\mathcal{O}(1)$, but to have $$|\langle w|v_i\rangle| < \epsilon$$ for all $i=1,2,...,n$ we see that each vector component of $|w\rangle$ must be $\mathcal{O}(\epsilon)$.

Since all the components of $|w\rangle$ cannot simultaneously be of order $\mathcal{O}(\epsilon)$ while still producing the $\mathcal{O}(1)$ result $\langle w|w\rangle=1$, we see that no such vector $|w\rangle$ exists.

What do you think?

PS:

Of course, there is a possibility of setting $\epsilon$ to not be much smaller than $1$, so that a finite sum of order $\mathcal{O}(\epsilon)$ quantities can produce an order $\mathcal{O}(1)$ quantity. However, that would not have an $\epsilon\to 0$ limit as long as the overall number of vectors in the set is finite.

$\endgroup$
3
  • $\begingroup$ I think your statement " the vectors $e⃗_{i}$...must be included in this case as well." is not true, although I agree that the number of vectors is still $n$. $\endgroup$
    – MikeY
    Jan 16 '20 at 16:57
  • 1
    $\begingroup$ @MikeY Oh, I see what you mean, one can start with a slightly $\mathcal{O}(\epsilon)$ deformed version of $\vec{e}_i$ vectors, but it does not change the argument. I made some edits to accommodate this. $\endgroup$
    – Kagaratsch
    Jan 16 '20 at 17:38
  • $\begingroup$ In the limit $\epsilon \to 0$, yes there won't be any more vectors. However if the dimensionality of the vector space is quite large, then a sufficiently small $\epsilon$ would give rise to many vectors. See the answer by @Roman in which he has demonstrated that the number of such vectors actually grows like an exponential of $\epsilon$. I also have a similar result to that, but I want an explicit demonstration of the same. $\endgroup$
    – Bruce Lee
    Jan 18 '20 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.