Daily Archive

You are currently browsing the daily archive for 18 July, 2013.

A cheap version of the Kabatjanskii-Levenstein bound for almost orthogonal vectors

18 July, 2013 in expository, math.MG | Tags: , | by | 26 comments

Let {n} be a natural number. We consider the question of how many “almost orthogonal” unit vectors {v_1,\ldots,v_m} one can place in the Euclidean space {{\bf R}^n}. Of course, if we insist on {v_1,\ldots,v_m} being exactly orthogonal, so that {\langle v_i,v_j \rangle = 0} for all distinct {i,j}, then we can only pack at most {n} unit vectors into this space. However, if one is willing to relax the orthogonality condition a little, so that {\langle v_i,v_j\rangle} is small rather than zero, then one can pack a lot more unit vectors into {{\bf R}^n}, due to the important fact that pairs of vectors in high dimensions are typically almost orthogonal to each other. For instance, if one chooses {v_i} uniformly and independently at random on the unit sphere, then a standard computation (based on viewing the {v_i} as gaussian vectors projected onto the unit sphere) shows that each inner product {\langle v_i,v_j \rangle} concentrates around the origin with standard deviation {O(1/\sqrt{n})} and with gaussian tails, and a simple application of the union bound then shows that for any fixed {K \geq 1}, one can pack {n^K} unit vectors into {{\bf R}^n} whose inner products are all of size {O( K^{1/2} n^{-1/2} \log^{1/2} n )}.

One can remove the logarithm by using some number theoretic constructions. For instance, if {n} is twice a prime {n=2p}, one can identify {{\bf R}^n} with the space {\ell^2({\bf F}_p)} of complex-valued functions {f: {\bf F}_p \rightarrow {\bf C}}, where {{\bf F}_p} is the field of {p} elements, and if one then considers the {p^2} different quadratic phases {x \mapsto \frac{1}{\sqrt{p}} e_p( ax^2 + bx )} for {a,b \in {\bf F}_p}, where {e_p(a) := e^{2\pi i a/p}} is the standard character on {{\bf F}_p}, then a standard application of Gauss sum estimates reveals that these {p^2} unit vectors in {{\bf R}^n} all have inner products of magnitude at most {p^{-1/2}} with each other. More generally, if we take {d \geq 1} and consider the {p^d} different polynomial phases {x \mapsto \frac{1}{\sqrt{p}} e_p( a_d x^d + \ldots + a_1 x )} for {a_1,\ldots,a_d \in {\bf F}_p}, then an application of the Weil conjectures for curves, proven by Weil, shows that the inner products of the associated {p^d} unit vectors with each other have magnitude at most {(d-1) p^{-1/2}}.

As it turns out, this construction is close to optimal, in that there is a polynomial limit to how many unit vectors one can pack into {{\bf R}^n} with an inner product of {O(1/\sqrt{n})}:

Theorem 1 (Cheap Kabatjanskii-Levenstein bound) Let {v_1,\ldots,v_m} be unit vector in {{\bf R}^n} such that {|\langle v_i, v_j \rangle| \leq A n^{-1/2}} for some {1/2 \leq A \leq \frac{1}{2} \sqrt{n}}. Then we have {m \leq (\frac{Cn}{A^2})^{C A^2}} for some absolute constant {C}.

In particular, for fixed {d} and large {p}, the number of unit vectors one can pack in {{\bf R}^{2p}} whose inner products all have magnitude at most {dp^{-1/2}} will be {O( p^{O(d^2)} )}. This doesn’t quite match the construction coming from the Weil conjectures, although it is worth noting that the upper bound of {(d-1)p^{-1/2}} for the inner product is usually not sharp (the inner product is actually {p^{-1/2}} times the sum of {d-1} unit phases which one expects (cf. the Sato-Tate conjecture) to be uniformly distributed on the unit circle, and so the typical inner product is actually closer to {(d-1)^{1/2} p^{-1/2}}).

Note that for {0 \leq A < 1/2}, the {A=1/2} case of the above theorem (or more precisely, Lemma 2 below) gives the bound {m=O(n)}, which is essentially optimal as the example of an orthonormal basis shows. For {A \geq \sqrt{n}}, the condition {|\langle v_i, v_j \rangle| \leq A n^{-1/2}} is trivially true from Cauchy-Schwarz, and {m} can be arbitrariy large. Finally, in the range {\frac{1}{2} \sqrt{n} \leq A \leq \sqrt{n}}, we can use a volume packing argument: we have {\|v_i-v_j\|^2 \geq 2 (1 - A n^{-1/2})}, so of we set {r := 2^{-1/2} (1-A n^{-1/2})^{1/2}}, then the open balls of radius {r} around each {v_i} are disjoint, while all lying in a ball of radius {O(1)}, giving rise to the bound {m \leq C^n (1-A n^{-1/2})^{-n/2}} for some absolute constant {C}.

As I learned recently from Philippe Michel, a more precise version of this theorem is due to Kabatjanskii and Levenstein, who studied the closely related problem of sphere packing (or more precisely, cap packing) in the unit sphere {S^{n-1}} of {{\bf R}^n}. However, I found a short proof of the above theorem which relies on one of my favorite tricks – the tensor power trick – so I thought I would give it here.

We begin with an easy case, basically the {A=1/2} case of the above theorem:

Lemma 2 Let {v_1,\ldots,v_m} be unit vectors in {{\bf R}^n} such that {|\langle v_i, v_j \rangle| \leq \frac{1}{2n^{1/2}}} for all distinct {i,j}. Then {m < 2n}.

Proof: Suppose for contradiction that {m \geq 2n}. We consider the {2n \times 2n} Gram matrix {( \langle v_i,v_j \rangle )_{1 \leq i,j \leq 2n}}. This matrix is real symmetric with rank at most {n}, thus if one subtracts off the identity matrix, it has an eigenvalue of {-1} with multiplicity at least {n}. Taking Hilbert-Schmidt norms, we conclude that

\displaystyle \sum_{1 \leq i,j \leq 2n: i \neq j} |\langle v_i, v_j \rangle|^2 \geq n.

But by hypothesis, the left-hand side is at most {2n(2n-1) \frac{1}{4n} = n-\frac{1}{2}}, giving the desired contradiction. \Box

To amplify the above lemma to cover larger values of {A}, we apply the tensor power trick. A direct application of the tensor power trick does not gain very much; however one can do a lot better by using the symmetric tensor power rather than the raw tensor power. This gives

Corollary 3 Let {k} be a natural number, and let {v_1,\ldots,v_m} be unit vectors in {{\bf R}^n} such that {|\langle v_i, v_j \rangle| \leq 2^{-1/k} (\binom{n+k-1}{k})^{-1/2k}} for all distinct {i,j}. Then {m < 2\binom{n+k-1}{k}}.

Proof: We work in the symmetric component {\hbox{Sym}^k {\bf R}^n} of the tensor power {({\bf R}^n)^{\otimes k} \equiv {\bf R}^{n^k}}, which has dimension {\binom{n+k-1}{k}}. Applying the previous lemma to the tensor powers {v_1^{\otimes k},\ldots,v_m^{\otimes k}}, we obtain the claim. \Box

Using the trivial bound {e^k \geq \frac{k^k}{k!}}, we can lower bound

\displaystyle 2^{-1/k} (\binom{n+k-1}{k})^{-1/2k} \geq 2^{-1/k} (n+k-1)^{-1/2} (k!)^{1/2k}

\displaystyle \geq 2^{-1/k} e^{-1/2} k^{1/2} (n+k-1)^{-1/2} .

We can thus prove Theorem 1 by setting {k := \lfloor C A^2 \rfloor} for some sufficiently large absolute constant {C}.

Archives