Q is for quantum?

The letter q has three, or maybe four, standard uses in mathematics.

It stands for “quantum”, and it is fashionable now to produce quantum versions of everything from chromatic number of a graph to the symmetric group.

Related to this, q occurs as a “deformation parameter” in quantised versions of standard algebraic structures. That is, there is an algebra depending on a parameter q, and as q tends to 1, the algebra becomes a “classical algebra”. There can be real advantages to doing this. It may be that the representation theory of the classical algebra is difficult, but that of the deformed algebra is easier, and we can get some information about the classical case by taking a limit.

It is also quite common to use q as a formal parameter in certain power series counting objects of interest. For example, consider the problem of counting lattice paths from the origin to the point (m,n), where m and n are non-negative integers. Each step in the path must be a unit step in either the easterly or the northerly direction. We have to take altogether m+n steps, of which m must be easterly and n northerly; these steps can be taken in any order, so the number of paths is the binomial coefficient, which I shall write as Bin(m+n,m). But now let us refine the count. Each such path, together with the X-axis and the line x = m, encloses a certain area A (between 0 and mn inclusive). Now if, instead of counting 1 for each path, we count qA to a path enclosing an area A, the sum we get is the Gaussian coefficient Gauss(m+n,m)q. This is calculated by replacing each integer k in the expression for the binomial coefficient by the “q-integer” qk−1. Since the number of factors in numerator and denominator is the same, an application of l’Hôpital’s rule shows that the Gaussian coefficient tends to the binomial as q→1.

Finally, the number of elements in a finite field (which is a prime power) is universally referred to as q. This is so ingrained that the finite fields community call their annual conferences Fq, a standard notation for a field of q elements.

Now something unexpected and wonderful holds. The binomial coefficient Binom(n,k) counts the number of k-element subsets of a set of size n; and the Gaussian coefficient Gauss(n,k)q counts the number of k-dimensional subspaces of an n-dimensional subspace over the field Fq.

There are many analogies and parallels between the combinatorics of subsets of a set and the combinatorics (or projective geometry) of subspaces of a vector space, especially over a finite field. This leads us to sometimes describe the former as “geometry over the field with one element”, as I have discussed on another occasion.

This long introduction finally brings me to my topic, a paper entitled “Defining the q-analogue of a matroid” by Relinde Jurrius and Ruud Pellikaan, which appeared in the Electronic Journal of Combinatorics last month.

Matroids are combinatorial structures which describe many kinds of “independence”: linear independence in a vector space; algebraic independence over a ground field in an algebraically closed field; forests in a graph; partial transversals of a set system; affine independence in an affine space; and so on. They were introduced by Whitney, and their theory was developed by Tutte, Rota, welsh, and many other mathematicians. Take a look at the Matroid Union blog to learn more.

Jurrius and Pellikaan are not producing a quantum version of matroid theory. Rather, as in the last case above, they are defining a structure over a field with q elements to be the analogue of a matroid in the usual sense over the “field with one element”. More precisely, they define a q-matroid to be a finite-dimensional vector space E over Fq, together with a rank function r from the set of subspaces of E, satisfying exactly the same conditions as for a matroid, namely, for all subspaces A and B of E,

  • 0 ≤ r(A) ≤ dim(A);
  • if A ⊆ B, then r(A) ≤ r(B);
  • r(A+B)+r(AB) ≤ r(A)+r(B).

Of course, matroids can be defined in many other ways: in terms of their independent sets, bases, circuits, and so on. Something a little unexpected emerges. For the analogue of independent sets, for example, we have a collection of subspaces called independent spaces, satisfying exact analogues of the independent-sets axiom for matroids, but with an extra axiom, which cannot be dispensed with. It states that if A,B are subspaces, and I,J are maximal independent subspaces of A,B respectively, then there is a maximal subspace of A+B which is contained in I+J.

About halfway through the paper comes the motivation for studying q-matroids. Just as ordinary (representable) matroids arise from (linear) codes, it turns out that q-matroids arise from “rank metric codes”, structures using the rank of the difference between matrices as a measure of how far apart they are.

Right at the end of the paper, they mention that the notion of a quantum matroid has been defined by Paul Terwilliger; it is closely related to that of q-matroid. There is also related work by Henry Crapo.

The paper contains many research topics. One of these concerns the Tutte polynomial. How should it be defined in such a way that Greene’s link between Tutte pollynomial of a matroid and weight enumerator of the corresponding linear code has an analogue for q-matroids and rank metric codes?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

2 Responses to Q is for quantum?

  1. Jon Awbrey says:

    I remember working out the q-analogue of integration-by-parts one time. All sorts of pretty partition identities fell out.

  2. Thanks a lot for featuring our paper! I would like to add some more information on recent developments in q-matroids, since some of the questions above have a (partial) answer.

    Shiromoto wrote about the relation between the rank weight enumerator fo a code and the rank genetisch function of a q-polymatroidd, see https://arxiv.org/abs/1803.06041. More on q-polymatroids and coding theory can be found in a paper with Gorla, Ravagnani and Lopez, see https://arxiv.org/abs/1803.10844.

    The question about a sensible definition of the Tutte polynomial of a q-matroid is still open. There is some preliminary work on ti with Bollen and Crapo (https://arxiv.org/abs/1707.03459), but it is far from finished.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.