Schmidt and analytic ranks, the Kronecker lemma and Hadamard lectures

Just a short post: David Kazhdan, Tammy Ziegler and I have recently (and finally) posted our proof that the analytic rank of a cubic, the logarithm of its bias, and its Schmidt rank (how hard it is to write it as products of lower degree polynomials), are linearly related.

This came out of our discussion of Kronecker’s lemma. One version can be stated as follows:

Lemma (Kronecker) Consider A, B linear maps from a vectorspace X to another one Y over any infinite field. Assume that

B ker(A) is not a subspace of im A

then the generic linear combination of A and B has larger rank than A and B

Leopold Kronecker

I had used this lemma in a previous work to construct Lefschetz elements, without knowing at first it was due to Kronecker. More about that Lefschetz aspect later, when some exciting news will come online. Suffices to say, that Kronecker’s lemma gives a rather cool restriction on spaces of linear maps, and strongly restricts them when they are of low rank.

Corollary Consider a space of bilinear forms L over X times Y, such that every element is of rank at most r. Then there are subspaces X’ and Y’, each of codimension r in X resp. Y, so that L vanishes identically on X’ times Y’.

It isn’t much, really, but at first this corollary was quite counterintuitive to me, since after knowing that a space of matrices of rank r cannot be restricted to r rows or r columns (consider \mathfrak{so}_3) I did not believe anything of the sort could be true.

Anyway, for the application to tensor ranks, see our paper. Let me advertize also the upcoming Hadamard lectures, where I will explain how Kronecker’s lemma can be used to construct Lefschetz isomorphisms.

(including a picture of myself where I look like a Russian mobster)

Kronecker, L. Algebraische Reduction der Scharen bilinearer Formen, Sitzungsber. Akad.Berlin, Jbuch. 22 (169) (1890) 1225-1237.

Minkowski sums (and how big they must be)

So, this is the promised actual first post, motivated by and answering a question recently posed to me by Yue Ren (and several before him that I apologize for forgetting). It comes with a problem, and that is, to prove the result in a simpler, more elementary way.

I had written a longer paper (with Raman Sanyal) on a problem concerning Upper Bounds on the complexity of Minkowski sums that dealt with the problem quite thoroughly.

But after we submitted the paper, and it was accepted and published in Publications IHES, someone asked me a question. I thought for a while, and answered that it follows from that and that lemma in the paper. But the question came up again and again, seemingly being quite relevant. On the other hand, writing a new paper on the matter was tedious, as it promised to be 90% repetition of paper number one. Which was an annoying prospect at best.

The problem is this: Consider a bunch (say m of polytopes (P_i) in a euclidean vector space of dimension d. For simplicity, and to be interesting, let us assume that all these polytopes are of positive dimension. Also, let us assume that all these polytopes are in general position with respect to each other.

Question: How many vertices must the Minkowski sum of the family (P_i) have? Surely, it has to be at least the number of vertices as the Minkowski sum of m segments in general position.

Turns out, the naive guess is correct. Also turns out that the proof seems to be quite a bit harder than I initially thought it would be. Indeed, the naive idea, that the Minkowski sum of two polytopes of positive dimension P and Q, P fixed, is minimized if and only if Q is a line segments, is not true. The real proof, unfortunately, seems to need a considerable detour. Let me sketch it here.

The first idea here is to consider the Cayley polytope of the family (P_i). This is a polytope in \mathbb{R}^{d+m-1}= \mathbb{R}^{d} \otimes \mathbb{R}^{m-1} obtained by translating each of the P_i independently into general positon, for instance by translating each of them along a choice of m vectors v_i in general position in \mathbb{R}^{m-1} that sum to zero. And then passing to the convex hull.

That is a rather powerful trick, as we now have a new polytope C(P_i) that encodes the Minkowski sum: we obtain it back by slicing the polytope with the subspace \mathbb{R}^{d}. The collection of faces of C(P_i) that intersects \mathbb{R}^{d} is called the “open Cayley complex” T^\circ(P_i), its closure is the Cayley complex T(P_i).

Now we count the number of faces f_j of the Minkowski sum, or equivaently, the face numbers of the open Cayley complex (shifted by m-1). That is best done by first transforming to the h-vector,

h_k := \sum_{i=0}^k (-1)^{k-j}\binom{d-j}{k-j}f_{j-1}.

and estimating this. There are now two essential facts: We have the Dehn-Sommerville relations

h_k(T(P_i)) \ =\ h_{d+m-j}(T^\circ(P_i)) + E

where the error E only depends on number of summands, and the important inequality

h_1(T(P_i)) \ \le\ h_{d-j}(T^\circ(P_i))

for all j\ge 1. That last inequality is key, and seems to only really follow from that Lefschetz theorem for polytopes (or the associate toric variety) where the first, the Dehn-Sommerville relations, follow from “only” a version of Poincar\’e duality.

Now the path is clear: if we want to estimate the number of k-faces of the Minkowski sum, then we can equally estimate the number of k+m-1-faces of the open Cayley complexes, which amounts to estimating h_{k+m}(T^\circ(P_i)), or equivalently, h_{d-k+1}(T^\circ(P_i)).

Which of course is bounded below by h_1(T(P_i)), which is quickly computed to be the total number of vertices of summands, minus d+m-1, and gives the desired lower bound.

The details can be found here and in its appendix here.

First post (the why and what)

The idea of this blog, that I was long too lazy to put into action, was as a collection of smaller observations that are not exactly paper worthy. That, and the obvious procrastination from doing actual work.

The final kick was the pandemic, and a question that Yue Ren asked me recently. It occured to me that I had answered the question before, several times, to several people, but had not really recorded the answer. That will be the topic of the actual first post.

So if you look for smaller musings and nonsense, between combinatorics, algebra and geometry. Then that somewhere is here, for this result and others like it. Sometimes also other things, who knows.