# Levenshtein bound for spherical codes

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}))$?

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

• 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? – Andrew S May 8 '18 at 23:23
• 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$. – kodlu May 8 '18 at 23:45
• 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$. – Andrew S May 8 '18 at 23:59
• OK, I see it more clearly now. By the way, regarding your question on the Levenshtein bounds, they do assume a constant $\theta.$ – kodlu May 9 '18 at 0:28
• Nice chatting with you, @AndrewS. If you found my incomplete answer helpful, shedding some light on the problem, feel free to upvote :-). – kodlu May 9 '18 at 0:29