You are currently browsing the tag archive for the ‘tensor power trick’ tag.

In this previous blog post I noted the following easy application of Cauchy-Schwarz:

Lemma 1 (Van der Corput inequality)Let be unit vectors in a Hilbert space . Then

*Proof:* The left-hand side may be written as for some unit complex numbers . By Cauchy-Schwarz we have

As a corollary, correlation becomes transitive in a statistical sense (even though it is not transitive in an absolute sense):

Corollary 2 (Statistical transitivity of correlation)Let be unit vectors in a Hilbert space such that for all and some . Then we have for at least of the pairs .

*Proof:* From the lemma, we have

One drawback with this corollary is that it does not tell us *which* pairs correlate. In particular, if the vector also correlates with a separate collection of unit vectors, the pairs for which correlate may have no intersection whatsoever with the pairs in which correlate (except of course on the diagonal where they must correlate).

While working on an ongoing research project, I recently found that there is a very simple way to get around the latter problem by exploiting the tensor power trick:

Corollary 3 (Simultaneous statistical transitivity of correlation)Let be unit vectors in a Hilbert space for and such that for all , and some . Then there are at least pairs such that . In particular (by Cauchy-Schwarz) we have for all .

*Proof:* Apply Corollary 2 to the unit vectors and , in the tensor power Hilbert space .

It is surprisingly difficult to obtain even a qualitative version of the above conclusion (namely, if correlates with all of the , then there are many pairs for which correlates with for all simultaneously) without some version of the tensor power trick. For instance, even the powerful Szemerédi regularity lemma, when applied to the set of pairs for which one has correlation of , for a single , does not seem to be sufficient. However, there is a reformulation of the argument using the Schur product theorem as a substitute for (or really, a disguised version of) the tensor power trick. For simplicity of notation let us just work with real Hilbert spaces to illustrate the argument. We start with the identity

where is the orthogonal projection to the complement of . This implies a Gram matrix inequality for each where denotes the claim that is positive semi-definite. By the Schur product theorem, we conclude that and hence for a suitable choice of signs , One now argues as in the proof of Corollary 2.A separate application of tensor powers to amplify correlations was also noted in this previous blog post giving a cheap version of the Kabatjanskii-Levenstein bound, but this seems to not be directly related to this current application.

Let be a natural number. We consider the question of how many “almost orthogonal” unit vectors one can place in the Euclidean space . Of course, if we insist on being *exactly* orthogonal, so that for all distinct , then we can only pack at most unit vectors into this space. However, if one is willing to relax the orthogonality condition a little, so that is small rather than zero, then one can pack a lot more unit vectors into , due to the important fact that pairs of vectors in high dimensions are typically almost orthogonal to each other. For instance, if one chooses uniformly and independently at random on the unit sphere, then a standard computation (based on viewing the as gaussian vectors projected onto the unit sphere) shows that each inner product concentrates around the origin with standard deviation and with gaussian tails, and a simple application of the union bound then shows that for any fixed , one can pack unit vectors into whose inner products are all of size .

One can remove the logarithm by using some number theoretic constructions. For instance, if is twice a prime , one can identify with the space of complex-valued functions , where is the field of elements, and if one then considers the different quadratic phases for , where is the standard character on , then a standard application of Gauss sum estimates reveals that these unit vectors in all have inner products of magnitude at most with each other. More generally, if we take and consider the different polynomial phases for , then an application of the Weil conjectures for curves, proven by Weil, shows that the inner products of the associated unit vectors with each other have magnitude at most .

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 with an inner product of :

Theorem 1 (Cheap Kabatjanskii-Levenstein bound)Let be unit vector in such that for some . Then we have for some absolute constant .

In particular, for fixed and large , the number of unit vectors one can pack in whose inner products all have magnitude at most will be . This doesn’t quite match the construction coming from the Weil conjectures, although it is worth noting that the upper bound of for the inner product is usually not sharp (the inner product is actually times the sum of 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 ).

Note that for , the case of the above theorem (or more precisely, Lemma 2 below) gives the bound , which is essentially optimal as the example of an orthonormal basis shows. For , the condition is trivially true from Cauchy-Schwarz, and can be arbitrariy large. Finally, in the range , we can use a volume packing argument: we have , so of we set , then the open balls of radius around each are disjoint, while all lying in a ball of radius , giving rise to the bound for some absolute constant .

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 of . 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 case of the above theorem:

Lemma 2Let be unit vectors in such that for all distinct . Then .

*Proof:* Suppose for contradiction that . We consider the Gram matrix . This matrix is real symmetric with rank at most , thus if one subtracts off the identity matrix, it has an eigenvalue of with multiplicity at least . Taking Hilbert-Schmidt norms, we conclude that

But by hypothesis, the left-hand side is at most , giving the desired contradiction.

To amplify the above lemma to cover larger values of , 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 3Let be a natural number, and let be unit vectors in such that for all distinct . Then .

*Proof:* We work in the symmetric component of the tensor power , which has dimension . Applying the previous lemma to the tensor powers , we obtain the claim.

Using the trivial bound , we can lower bound

We can thus prove Theorem 1 by setting for some sufficiently large absolute constant .

As many readers may already know, my good friend and fellow mathematical blogger Tim Gowers, having wrapped up work on the Princeton Companion to Mathematics (which I believe is now in press), has begun another mathematical initiative, namely a “Tricks Wiki” to act as a repository for mathematical tricks and techniques. Tim has already started the ball rolling with several seed articles on his own blog, and asked me to also contribute some articles. (As I understand it, these articles will be migrated to the Wiki in a few months, once it is fully set up, and then they will evolve with edits and contributions by anyone who wishes to pitch in, in the spirit of Wikipedia; in particular, articles are not intended to be permanently authored or signed by any single contributor.)

So today I’d like to start by extracting some material from an old post of mine on “Amplification, arbitrage, and the tensor power trick” (as well as from some of the comments), and converting it to the Tricks Wiki format, while also taking the opportunity to add a few more examples.

**Title: The tensor power trick
**

**Quick description: **If one wants to prove an inequality for some non-negative quantities X, Y, but can only see how to prove a quasi-inequality that loses a multiplicative constant C, then try to replace all objects involved in the problem by “tensor powers” of themselves and apply the quasi-inequality to those powers. If all goes well, one can show that for all , with a constant C which is *independent* of M, which implies that as desired by taking roots and then taking limits as .

## Recent Comments