5
$\begingroup$

If $F(v_1,\dots,v_k)$ is a $k$-linear form on $\mathbb R^n$, the norm I want to consider is

$$ ||F|| = \sup \frac{ F(v_1,\dots, v_k)}{\prod_{i=1}^k \left|\left|v_i\right|\right|} $$

where the vector norm is the $2$-norm.

A random $k$-linear form is one given by a $k$-tensor with i.i.d. mean 0 entries.

Known result 1: A random $2$-linear form has norm $O( \sqrt{n})$ with probability approaching $1$. (This is the same as the largest singular value of a randommatrix, so it's the square root of the largest eigenvalue of a Wishart random matrix, which is close to $2\sqrt{n}$ with high probability.)

Known result 2: A random $3$-linear form has norm $O(n^{1/2+\epsilon})$ with probability approaching 1. (On an inequality of von Neumann and an application to the metric theory of tensor products)

Known result 3: Suppose there is a sequence of distributions of $2$-linear forms on $\mathbb R^n$ such that for each degree $d$, for sufficiently large $n$, the expectation of all degree $d$ polynomials of the entries is the same as for a random $2$-linear form. Then an element of that distribution has norm $O(n^{1/2+\epsilon})$ with probability approaching one. (The expected value of $tr (M M^T)^{d/2})$ for a random matrix $M$ is proportional to $n^{1+d/2}$ and it is an upper bound on the $d$th power of the norm, so we get an upper bound of the form $n^{1/2 + 1/d}$ from the $d$th moments.)

Question:

Suppose there is a sequence of distributions of $3$-linear forms on $\mathbb R^n$ such that for each degree $d$, for sufficiently large $n$, the expectation of all degree $d$ polynomials of the entries is the same as for a random $3$-linear form. Does an element of that distribution have norm $O(n^{1/2+\epsilon})$ with probability approaching one?

Observe that the proof of known result 2 relies on computing

$$ \mathbb E \left [e^{ \lambda F(v_1,v_2,v_3)} \right]$$

for random $v_1$, $v_2$, $v_3$ on the unit ball. This can be expressed in terms of moments of $F$, but it involves polynomials of arbitrarily high degree. Is this necessary?

The motivation for this question that a small moment result would allow us to prove the same inequality for a much larger class of distributions, such as those arising from algebraic geometry.

$\endgroup$
2
  • $\begingroup$ Looks plausible to me. One can view a trilinear form $F(v_1,v_2,v_3)$ as a bilinear form $F_{v_3}(v_1,v_2)$ whose coefficients are various sums of $v_3$. From the bilinear theory one needs to control various moments of these coefficients, but it looks like one should be doable in terms of expectation of bounded degree polynomials. In particular the moments should match those of the gaussian iid case in which everything behaves as expected. I haven't done the computations though. $\endgroup$
    – Terry Tao
    Jan 8, 2015 at 18:50
  • $\begingroup$ Oh, wait, the argument I sketched out will bound things for almost all $v_3$, but you want something that will work for all $v_3$. This could be significantly trickier. In the genuinely random case one can use epsilon-net arguments, but these are not accessible just from bounded moment hypotheses. I'll have to think about this some more. $\endgroup$
    – Terry Tao
    Jan 8, 2015 at 19:13

1 Answer 1

3
$\begingroup$

No. One cannot prove any bound better than $n^{3/4-\epsilon}$. In case anyone else is interested I am posting my argument here.

My argument for this is slightly unusual - it relies on algebraic geometry to produce a counterexample. I am sure there is an elementary argument that uses a purely combinatorial construction of a counterexample, but this one was easier for me to come up with.

First note that if one has a bound $n^{3/4-\epsilon}$ for $d$ growing arbitrarily slowly as a function of $n$, one has a bound $n^{3/4-\epsilon}$ for some specific $d$.

Also note that any bound based on moments must only depend on the $O(n)^3$-invariant moments, because you could just multiply by a random element of $O(n)$. There are only finitely many linearly independent $O(n)$-invariant polynomials of degree $d$, so we only need to track finitely many moments.

Assume $n=q$ is a prime power, and fix an additive character $\psi: \mathbb F_q \to \mathbb C^\times$. Also assume $d$ is less than the characteristic of $\mathbb F_q$.

Consider the distribution consisting of $3$-tensors whose entries are $M_{xyz}=\psi (f(x,y,z))$ for random polynomials $f$ of degree $d$ in $\mathbb F_q[x,y,z]$. The moments of these $3$-tensors are exactly the same as the moments of random $3$-tensors whose entries are independent random complex numbers of unit norm.

If $q$ is a perfect square, $f$ is a polynomial whose coefficients happen to be in $\mathbb F_{q^{1/2}}$, and $\psi$ is trivial on $\mathbb F_{q^{1/2}}$, then the associated trilinear form has norm at least $q^{3/4}$. We can see this by taking $v_1=v_2=v_3$ to be the vector that is $1$ on $\mathbb F_{q^{1/2}}$ and $0$ elsewhere. Then $F(v_1,v_2,v_3) = q^{3/2}$ because $\psi(f(x,y,z))=1$ for $x,y,z\in \mathbb F_{q^{1/2}}$. $||v_i||=q^{1/4}$, so we get a norm of at least $q^{3/2}$.

The probability that all the coefficients will just randomly lie in $\mathbb F_{q^{1/2}}$ is very small. Even worse, the moments for a random polynomial in $\mathbb F_{q^{1/2}}[x,y,z]$ are not exactly the same as the moments for a random polynomial in $\mathbb F_q[x,y,z]$. But we can "glue" the two distributions to obtain a distribution with the correct moments but that has operator norms very large with positive probability, as follows:

Take the finitely many O(n)-invariant polynomials and consider the finite set of points in $\mathbb C^n$ induced by evaluating these polynomials on the two distributions. If the average of the first set of points is contained in the convex hull of the second set of points, then by choosing an appropriate distribution of the second set of points, we get a distribution whose moments are the same as for a random distribution, but with operator norm at least $n^{3/4}$.

To check this condition, note that the moments are complete exponential sums, so we can compute their distribution by Deligne's equidistribution theorem, as sums of powers of $q$ times traces of random elements of groups acting on some fixed group representations. So it is sufficient to chech the convex hull conditions for the traces of group representations. The group elements associated to polynomials of $\mathbb F_q[x,y,z]$ have distribution approaching the distribution of random elements in the group, while for polynomials in $\mathbb F_{q^{1/2}}[x,y,z]$ the distribution is the distribution of random squares of elements of the group.

As long as the group is connected these distributions are pretty similar: one assigns positive measure to a set if and only if the other does. We can make sure that the convex hull of a set of points contains the average of a distribution by checking that it has a point in each of finitely many sets to which the distribution assigns positive measure - e.g. small neighborhoods of the corners of a polyhedron containing the average. So because the distributions are so similar, as long as we sample enough points we can get the desired counterexample. This happens for $q$ sufficiently large.

To deal with non-connected groups, first sample a connected component and then, if the connected component does not contain squares, sample from the full distribution restricted to that component, and if it does, use the convex hull trick. This gives $n^{3/4}$ a positive proportion of the time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.