2
$\begingroup$

I was trying to figure out what is the asymptotic expression for the maximum number of $n$-dimensional unit vectors in $\mathbb{R}^n$ we can have such that $v \cdot u \leq 1/\sqrt{n}$ for all pairs of vectors.

I found a Terence Tao blog post here where he gives a bound if we require that $| u \cdot v| \leq 1/\sqrt{n}$. This is almost what I want, but not quite. I dug into some coding theory books because I realize this is just $A(n, \arccos (1/\sqrt{n}))$, where $A(n, \theta)$ is the maximum size of an $n$-dimensional spherical code with minimum angle $\theta$.

The bound I found in a couple books is $$\frac{1}{n}\log_2 A(n, \theta) \leq \frac{1 + \sin \theta}{2sin\theta}\log_2\left( \frac{1 + \sin \theta}{2sin\theta}\right) - \frac{1 - \sin \theta}{2sin\theta}\log_2\left( \frac{1 - \sin \theta}{2sin\theta}\right)$$ which is given as due to Levenshtein. I first plugged this into a graphing utility with $\theta = \arccos(1/\sqrt{n})$ to see roughly how quickly it grows and what kinds of bounds I should try guessing to get an expression in terms of $n$. I was surprised to see that it grew really slowly. I thought maybe it was because of some sensitivity to rounding that the computer was doing, and so I did some rough calculation that seemed to indicate that $A(n, \arccos(1/\sqrt{n}))$ was bounded above by $e$. The graphing calculator seemed to confirm that. Clearly this bound makes no sense because I can easily pick a set of $2n$ vectors which all have dot products at most $0$.

My guess is that the Levenshtein bound holds for a fixed value of $\theta$ and the fact that I let $\theta$ vary with $n$ broke it somehow. Does anybody know if this is the case? And what bounds are known for $A(n, \arccos(1/\sqrt{n}))$?

$\endgroup$
1
$\begingroup$

You can model this by means of characteristic vectors of set families (vectors $v$ in $\{0,1\}^n$) where $$i\in A_v \leftrightarrow v_i=1,$$ with $A_v \subset \{1,2,\ldots,n\}$) and $v=(v_1,\ldots,v_n).$

The vector $v$ can then be converted to a vector $w\in \{\pm 1\},$ via $$ w:=w(v)=(w_1,\ldots,w_n)=((-1)^{v_1},\ldots,(-1)^{v_n}). $$ Clearly $w$ is on the surface of the sphere $S^{n-1}\subset \mathbb{R}^n.$

If we define the symmetric distance metric on the set system, via, $$ d(A,B)= A\triangle B=(A\setminus B)\cup (B\setminus A). $$ Fix $\alpha\in (0,1).$ Define $$ f(n;\alpha)=\max\{ |\cal F|: \cal F \subset \cal P(\{1,\ldots,n\}), d(A,B)\geq \alpha n,~\forall A,B \in \cal F, A\neq B\}. $$

Then the case of a small positive inner product upper bound, i.e., $$ u\cdot v\leq \frac{1}{\sqrt{n}} $$ after appropriate normalisation, corresponds to the case that $\alpha<1/2,$ for any finite $n.$ Theorem 6 in Chapter 10 of Bollobas' little white book Combinatorics states that $$ f(n;\alpha)\geq 2^{\epsilon n} $$ for some $\epsilon=\epsilon(\alpha)>0,$ while $$ f(n;1/2)\leq 2n, $$ with equality for infinitely many values of $n$. A greedy construction gives the first case (see exercise 4).

Edit: Bollobas, Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial probability. See here

$\endgroup$
  • $\begingroup$ Thank you for pointing out Bollobas' resource. Unfortunately, the bound he gives is for a fixed $\alpha$. What happens if we let $\alpha$ tend to 0 as $n$ increases? $\endgroup$ – Andrew S May 8 '18 at 23:23
  • $\begingroup$ Be careful, I think your $\alpha$ is not the same as his. For the $\pm 1$ formulation, I think, your bound corresponds to his $\alpha \rightarrow 0,$ which then gives an upper bound of $2n$. $\endgroup$ – kodlu May 8 '18 at 23:45
  • $\begingroup$ You're right, I meant the dot products tend to 0, not $\alpha$. Bollobas' $\alpha$ corresponds to a dot product of $(1 - 2\alpha)/\sqrt{n}$. So I'm looking at $\alpha \leq \frac{1}{2} -\frac{1}{n}$ which tends to $1/2$ as n increases. Still, I don't think the statement in the book deals with such an $\alpha$. $\endgroup$ – Andrew S May 8 '18 at 23:59
  • $\begingroup$ OK, I see it more clearly now. By the way, regarding your question on the Levenshtein bounds, they do assume a constant $\theta.$ $\endgroup$ – kodlu May 9 '18 at 0:28
  • $\begingroup$ Nice chatting with you, @AndrewS. If you found my incomplete answer helpful, shedding some light on the problem, feel free to upvote :-). $\endgroup$ – kodlu May 9 '18 at 0:29

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.