Turán and Ramsey problems for alternating multilinear maps
- School of Computer Science, University of Technology Sydney
- ORCID iD: 0000-0003-4334-1449
Editorial introduction
Turán and Ramsey problems for alternating multilinear maps, Discrete Analysis 2023:12, 22 pp.
Ramsey’s theorem (in its finite version) states that for every positive integer k there exists a positive integer n such that every graph with n vertices contains a clique or an independent set with k vertices. This result is just the beginning of what has become a huge field. Typically, a result in Ramsey theory takes the following form: one is given a structure S and a family S of structured subsets of S, and the result says that however one colours the elements of S with at most r colours, there must be a substructure S′∈S with all its elements of the same colour. For example, it follows from the Hales-Jewett theorem that for every prime p and every pair of positive integers r and k there exists a positive integer n such that however the points of Fnp are coloured with r colours, there must be an affine subspace of Fnp of dimension at least k with all its points of the same colour.
Ramsey theory is not just a collection of attractive theorems, since Ramsey-theoretic results often have surprising applications. Typically, these will tell us that a set must have a subset with one of two very different properties. A simple example of this is the statement that every sequence of real numbers has a subsequence that is either increasing or decreasing (though that can be proved directly with a simpler argument). There are also more complicated examples where one obtains either a highly structured subset or a subset that is “maximally unstructured” in some suitable sense.
Some results that follow this general pattern are not directly deduced from classic results of Ramsey theory; they can therefore be regarded as a kind of extension of Ramsey theory. One such result, a “quantum Ramsey theorem” relevant to this paper, was proved by Nik Weaver in 2016. Define a quantum system to be a linear subspace of Mn(C) that contains the identity and is closed under taking adjoints. Given a quantum system Λ and a subspace V⊂Cn, define the restriction of Λ to V to be the family {PAP:A∈Λ}, where P is the orthogonal projection from C to V. Weaver proved that for every s there exists n (the bound obtained is s3−s+1) such that for every quantum family Λ⊂Mn(C) there is a subspace V of dimension s such that the restriction of Λ to V is either as large as possible – that is, it is isomorphic to Ms(V) – or as small as possible – that is, it consists of multiples of P (which from V’s perspective look like multiples of the identity).
An interesting example of Weaver’s theorem is where Λ consists of all diagonal matrices. It is not hard to show that the restriction of Λ even to a 2-dimensional subspace must have dimension greater than 1, so, somewhat surprisingly, the theorem yields a subspace V where the restriction is isomorphic to Mn(V). (This becomes less surprising when one notes that if D and D′ are diagonal matrices and P is an orthogonal projection, it does not necessarily follow that PDP and PD′P commute.)
The main result of this paper sounds quite similar to Weaver’s theorem, but there are important differences that cause it to need a significantly different proof. It concerns alternating bilinear forms. If U is a vector space over a field F, then an alternating form on U is a bilinear map f:U×U→F such that f(u,u)=0 for every u∈U (which implies that f(u,v)=−f(u,v) for every u,v∈U, and conversely if F does not have characteristic 2). Write Λ(U) for the space of all alternating bilinear forms on U. Then the main theorem of this paper states that if U is of high enough dimension, then for every subspace A of Λ(U), either there is an s-dimensional subspace V of U such that the restriction of A to V contains just the zero map, or there is a t-dimensional subspace W such that the restriction of A to W is Λ(W).
The bound obtained for the dimension of U is st4. Since this is a power-type bound, it is immediately clear that this result is not a simple consequence of Ramsey’s theorem. The important differences between this and Weaver’s result are that it works for arbitrary fields, and that diagonal matrices, which play a key role in Weaver’s arguments, are absent here.
An indication that this is a natural direction to pursue, and not just a problem formulated for the sake of it, is that it can be reformulated as a statement about p-groups. It says that among p-groups that are nilpotent of class 2 (that is, the commutators xyx−1y−1 commute with all other elements) every sufficiently large group G has a subgroup S with one of the following two properties.
- S[G,G]/[G,G] is isomorphic to Fsp.
- S is isomorphic to the free nilpotent p-group of class 2 with t generators.
The free nilpotent p-group of class 2 on t generators x1,…,xt is the group with all relations of the form ut=e and u[v,w]=[v,w]u, where u,v,w are arbitrary words.
Very roughly, this says that G has a subgroup that is either as structured as possible (modulo the commutator subgroup [G,G] it is Abelian) or as unstructured as possible (it is free, up to the constraints that it is contained in a p-group that is nilpotent of class 2).
The paper contains a discussion of several other interesting connections with different parts of mathematics, as well as some natural conjectures, which include in particular a conjecture that would extend the main result of this paper from bilinear to multilinear forms. Thus, as well as proving Ramsey-theoretic results with attractive and non-obvious statements, it is potentially opening up a new subfield of Ramsey theory.
This talk by the author contains more information about the background to these results.