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.

## 23 comments

Comments feed for this article

27 February, 2021 at 2:30 pm

John GriesmerStarting with collections , , you could use Ramsey’s theorem together with Corollary 2 to guarantee that for sufficiently large, there is a set of indices with for every pair from . Then apply Corollary 2 again to the , with .

This produces a better bound on the correlations, but I don’t know if it can get you a fraction of of the pairs of indices satisfying the bound, so maybe it’s not useful for the application you have in mind.

In any case, I’m naturally very curious about the structure of the set of pairs for which , so it’s interesting to think about how two such sets of pairs must intersect.

27 February, 2021 at 6:29 pm

Terence TaoNice – somehow I had not thought to use Ramsey’s theorem instead of the regularity lemma! Once one can guarantee one good pair with whenever exceeds some threshold then one gets a positive fraction of pairs by looking at random -element subsets of indices and averaging. So one gets a better bound on correlation but a much worse bound on density because of the iterated use of Ramsey’s theorem. (Actually now that I see this argument I think something similar is actually used in model theory when using (infinitary versions of) Ramsey’s theorem to create a huge number of indiscernibles.)

27 February, 2021 at 4:15 pm

AnonymousTerry, since I rely upon you to solve the majority of my most difficult math problems, I can only say that I enjoy attempting to figure yours out. Thanks for the opportunity! David

27 February, 2021 at 7:03 pm

AAre you adapting Walsh’s proof of Fourier Uniformity to the case of nilsequences?

27 March, 2021 at 12:29 pm

duck_masterAre you referring to https://arxiv.org/pdf/2102.05564.pdf? I think this might already be done in the case of the Liouville function, c.f. https://arxiv.org/pdf/2007.15644.pdf (even though that paper also briefly mentions the general case).

28 February, 2021 at 6:33 am

Oliver KnillThis is interesting also in the context of Lovasz umbrellas {v,u_1,…,u_n} in graph theory, where the unit vectors u_j attached to the nodes j of the graph satisfy (u_i,u_j)=0 if i,j are not adjacent. The vector v is the `stick’ of the umbrella. Lovasz noted in 1979 that max_j 1/(v,u_j)^2 is an upper bound for the Shannon capacity of the graph (a notoriously difficult number to compute and unknown even for the cyclic graph C_7). A suitable umbrella in R^3 establishes that the capacity is sqrt(5) for C_5. Corollary 2 would give then a lower bound on a fraction of all possible angles. The tensor power trick is the key why Lovasz umbrellas work for the Shannon capacity: the product of graphs produces the tensor product of umbrellas.

6 March, 2021 at 7:20 pm

Arulsaravana JeyarajIn this case I think luck was a factor. \sqrt{5} was a known lower bound. It is not clear semidefinite representations are the right way to go given all semidefinite representations are relaxations and semidefinite representations do not represent the problem exactly (there is a whole theory on it in CS based on UGC) or if these extremal problems require new insight.

6 March, 2021 at 7:27 pm

Arulsaravana JeyarajIt would be a miracle if the capacity of strong products of graphs are exactly formulated by the semidefinite relaxations. I think the truth is far lower compared to the semidefinite bounds and for the situation of certain cyclic graphs perhaps exactly portrayable (perhaps providing hints semidefinite relaxation bounds might be improvable in P (at least for certain situations)).

25 May, 2021 at 11:48 pm

Arulsaravana JeyarajI am not certain if following is right approach. The numbers coming through SDP approaches appear trigonometric. As far as I know capacity of ((2^k) +1)-cycle graphs could be bound by ((2^k)+1)^((k-1)/k). For example agrees with 5-cycle and at at 9-cycle agrees to best bounds on independence number at strong product of 9-cycle three times. k need not be integral I think and no computed independence number exceeds above. Is it possible to demonstrate the capacity of cycle graphs have different number theoretic properties compared to what arises naturally in SDP? An UGC connection is possible. Disproving optimality of SDP bound need not be necessarily explicitly computational.

28 February, 2021 at 6:40 am

dailyscreenzI echo David’s comment from above, really enjoy the blog, and reading about these topics (even if most are well above my level/pay grade).

28 February, 2021 at 7:25 am

Aditya Guha RoyReblogged this on Aditya Guha Roy's weblog.

28 February, 2021 at 7:37 am

N is a numberI have known about the fact that the tensor power trick can be used to get powerful results about bounds on sizes of sum sets. Can similar results be derived using this tool?

7 March, 2021 at 2:02 am

MarIn Corollary 3, \delta_K should be \delta_k and k=1,…K is repeated twice

[Corrected, thanks – T.]8 March, 2021 at 2:15 am

M.Typo: In the proof of corollary 3, I believe the u should be a v.

[Corrected, thanks – T.]10 March, 2021 at 4:33 pm

ZaoDear Professor,

You have carefully studied the Sendov conjecture for high degree polynomials in an older post last year.

I just have founded a preprint of T. Agama uploaded to the ArXiv on 27 august 2020 which could interest you where the author claims to have proved such a famous conjecture in the general case.

To the best of my knowledge, this paper has not been published in a journal or conference.

After reading the article, I am not convinced of the completeness and correction of the proof.

I just wanted to inform you on this contribution.

Yours sincerely

10 March, 2021 at 4:48 pm

AnonymousFollowing my previous message, you only have to take into account the version 4 of this preprint (55 pages).

Best

11 March, 2021 at 11:05 am

AnonymousIs it possible to generalize (and possibly improve) these results by using Holder’s inequality (instead of C-S inequality) in lemma 1?

16 March, 2021 at 12:14 am

Lin CuiHello, professor Tao, I’m currently a postgraduate student in a Chinese university. I consulted a study abroad company, and they told me that accord to my grades I can apply to study at UCLA further.

Professor Tao, if I’m really at the campus of UCLA, can I meet you and ask you some questions about mathematics study?

Please answer me, thank you very much!

Best wishes to you!!

28 March, 2021 at 11:02 am

AnonymousNo! You may not. COVID.

28 March, 2021 at 4:18 am

aegeanwestprofessor tao，how can i apply for your graduate student？any matieral should be prepared？and how about recommended books and tools…

have a nice day～🍭

9 April, 2021 at 7:36 pm

aquazorcarsonFirst sentence missed a square on the rewritten quantity.

[I was not able to locate the sentence referred to here. -T.]27 April, 2021 at 3:12 pm

aquazorcarsonSorry Terry, I meant the first sentence of the proof of the first result: “The left-hand side may be written as (…)^2”.

[Corrected, thanks – T.]9 April, 2021 at 8:00 pm

aquazorcarsonThe last sentence of corollary 3 seems too trivial to be what you actually meant?

[No, this is in fact the conclusion that ends up being useful in applications – T.]