Venn and Euler type diagrams for vector spaces and abelian groups

A popular way to visualise relationships between some finite number of sets is via Venn diagrams, or more generally Euler diagrams. In these diagrams, a set is depicted as a two-dimensional shape such as a disk or a rectangle, and the various Boolean relationships between these sets (e.g., that one set is contained in another, or that the intersection of two of the sets is equal to a third) is represented by the Boolean algebra of these shapes; Venn diagrams correspond to the case where the sets are in “general position” in the sense that all non-trivial Boolean combinations of the sets are non-empty. For instance to depict the general situation of two sets together with their intersection and one might use a Venn diagram such as

(where we have given each region depicted a different color, and moved the edges of each region a little away from each other in order to make them all visible separately), but if one wanted to instead depict a situation in which the intersection was empty, one could use an Euler diagram such as

One can use the area of various regions in a Venn or Euler diagram as a heuristic proxy for the cardinality (or measure ) of the set corresponding to such a region. For instance, the above Venn diagram can be used to intuitively justify the inclusion-exclusion formula

for finite sets , while the above Euler diagram similarly justifies the special case

for finite disjoint sets .

While Venn and Euler diagrams are traditionally two-dimensional in nature, there is nothing preventing one from using one-dimensional diagrams such as

or even three-dimensional diagrams such as this one from Wikipedia:

Of course, in such cases one would use length or volume as a heuristic proxy for cardinality or measure, rather than area.

With the addition of arrows, Venn and Euler diagrams can also accommodate (to some extent) functions between sets. Here for instance is a depiction of a function , the image of that function, and the image of some subset of :

Here one can illustrate surjectivity of by having fill out all of ; one can similarly illustrate injectivity of by giving exactly the same shape (or at least the same area) as . So here for instance might be how one would illustrate an injective function :

Cartesian product operations can be incorporated into these diagrams by appropriate combinations of one-dimensional and two-dimensional diagrams. Here for instance is a diagram that illustrates the identity :

In this blog post I would like to propose a similar family of diagrams to illustrate relationships between vector spaces (over a fixed base field , such as the reals) or abelian groups, rather than sets. The categories of (-)vector spaces and abelian groups are quite similar in many ways; the former consists of modules over a base field , while the latter consists of modules over the integers ; also, both categories are basic examples of abelian categories. The notion of a dimension in a vector space is analogous in many ways to that of cardinality of a set; see this previous post for an instance of this analogy (in the context of Shannon entropy). (UPDATE: I have learned that an essentially identical notation has also been proposed in an unpublished manuscript of Ravi Vakil.)

IPAM program in quantitative linear algebra, Mar 19-Jun 15 2018

Alice Guionnet, Assaf Naor, Gilles Pisier, Sorin Popa, Dimitri Shylakhtenko, and I are organising a three month program here at the Institute for Pure and Applied Mathematics (IPAM) on the topic of Quantitative Linear Algebra.  The purpose of this program is to bring together mathematicians and computer scientists (both junior and senior) working in various quantitative aspects of linear operators, particularly in large finite dimension.  Such aspects include, but are not restricted to discrepancy theory, spectral graph theory, random matrices, geometric group theory, ergodic theory, von Neumann algebras, as well as specific research directions such as the Kadison-Singer problem, the Connes embedding conjecture and the Grothendieck inequality.  There will be several workshops and tutorials during the program (for instance I will be giving a series of introductory lectures on random matrix theory).

While we already have several confirmed participants, we are still accepting applications for this program until Dec 4; details of the application process may be found at this page.

AMS open math notes

I just learned (from Emmanuel Kowalski’s blog) that the AMS has just started a repository of open-access mathematics lecture notes.  There are only a few such sets of notes there at present, but hopefully it will grow in the future; I just submitted some old lecture notes of mine from an undergraduate linear algebra course I taught in 2002 (with some updating of format and fixing of various typos).

 

[Update, Dec 22: my own notes are now on the repository.]

Approximate bases, sunflowers, and nonstandard analysis

One of the most basic theorems in linear algebra is that every finite-dimensional vector space has a finite basis. Let us give a statement of this theorem in the case when the underlying field is the rationals:

Theorem 1 (Finite generation implies finite basis, infinitary version) Let be a vector space over the rationals , and let be a finite collection of vectors in . Then there exists a collection of vectors in , with , such that

• ( generates ) Every can be expressed as a rational linear combination of the .
• ( independent) There is no non-trivial linear relation , among the (where non-trivial means that the are not all zero).

In fact, one can take to be a subset of the .

Proof: We perform the following “rank reduction argument”. Start with initialised to (so initially we have ). Clearly generates . If the are linearly independent then we are done. Otherwise, there is a non-trivial linear relation between them; after shuffling things around, we see that one of the , say , is a rational linear combination of the . In such a case, becomes redundant, and we may delete it (reducing the rank by one). We repeat this procedure; it can only run for at most steps and so terminates with obeying both of the desired properties.

In additive combinatorics, one often wants to use results like this in finitary settings, such as that of a cyclic group where is a large prime. Now, technically speaking, is not a vector space over , because one only multiply an element of by a rational number if the denominator of that rational does not divide . But for very large, “behaves” like a vector space over , at least if one restricts attention to the rationals of “bounded height” – where the numerator and denominator of the rationals are bounded. Thus we shall refer to elements of as “vectors” over , even though strictly speaking this is not quite the case.

On the other hand, saying that one element of is a rational linear combination of another set of elements is not a very interesting statement: any non-zero element of already generates the entire space! However, if one again restricts attention to rational linear combinations of bounded height, then things become interesting again. For instance, the vector can generate elements such as or using rational linear combinations of bounded height, but will not be able to generate such elements of as without using rational numbers of unbounded height.

For similar reasons, the notion of linear independence over the rationals doesn’t initially look very interesting over : any two non-zero elements of are of course rationally dependent. But again, if one restricts attention to rational numbers of bounded height, then independence begins to emerge: for instance, and are independent in this sense.

Thus, it becomes natural to ask whether there is a “quantitative” analogue of Theorem 1, with non-trivial content in the case of “vector spaces over the bounded height rationals” such as , which asserts that given any bounded collection of elements, one can find another set which is linearly independent “over the rationals up to some height”, such that the can be generated by the “over the rationals up to some height”. Of course to make this rigorous, one needs to quantify the two heights here, the one giving the independence, and the one giving the generation. In order to be useful for applications, it turns out that one often needs the former height to be much larger than the latter; exponentially larger, for instance, is not an uncommon request. Fortunately, one can accomplish this, at the cost of making the height somewhat large:

Theorem 2 (Finite generation implies finite basis, finitary version) Let be an integer, and let be a function. Let be an abelian group which admits a well-defined division operation by any natural number of size at most for some constant depending only on ; for instance one can take for a prime larger than . Let be a finite collection of “vectors” in . Then there exists a collection of vectors in , with , as well an integer , such that

• (Complexity bound) for some depending only on .
• ( generates ) Every can be expressed as a rational linear combination of the of height at most (i.e. the numerator and denominator of the coefficients are at most ).
• ( independent) There is no non-trivial linear relation among the in which the are rational numbers of height at most .

In fact, one can take to be a subset of the .

Proof: We perform the same “rank reduction argument” as before, but translated to the finitary setting. Start with initialised to (so initially we have ), and initialise . Clearly generates at this height. If the are linearly independent up to rationals of height then we are done. Otherwise, there is a non-trivial linear relation between them; after shuffling things around, we see that one of the , say , is a rational linear combination of the , whose height is bounded by some function depending on and . In such a case, becomes redundant, and we may delete it (reducing the rank by one), but note that in order for the remaining to generate we need to raise the height upper bound for the rationals involved from to some quantity depending on . We then replace by and continue the process. We repeat this procedure; it can only run for at most steps and so terminates with and obeying all of the desired properties. (Note that the bound on is quite poor, being essentially an -fold iteration of ! Thus, for instance, if is exponential, then the bound on is tower-exponential in nature.)

(A variant of this type of approximate basis lemma was used in my paper with Van Vu on the singularity probability of random Bernoulli matrices.)

Looking at the statements and proofs of these two theorems it is clear that the two results are in some sense the “same” result, except that the latter has been made sufficiently quantitative that it is meaningful in such finitary settings as . In this note I will show how this equivalence can be made formal using the language of non-standard analysis. This is not a particularly deep (or new) observation, but it is perhaps the simplest example I know of that illustrates how nonstandard analysis can be used to transfer a quantifier-heavy finitary statement, such as Theorem 2, into a quantifier-light infinitary statement, such as Theorem 1, thus lessening the need to perform “epsilon management” duties, such as keeping track of unspecified growth functions such as . This type of transference is discussed at length in this previous blog post of mine.

In this particular case, the amount of effort needed to set up the nonstandard machinery in order to reduce Theorem 2 from Theorem 1 is too great for this transference to be particularly worthwhile, especially given that Theorem 2 has such a short proof. However, when performing a particularly intricate argument in additive combinatorics, in which one is performing a number of “rank reduction arguments”, “energy increment arguments”, “regularity lemmas”, “structure theorems”, and so forth, the purely finitary approach can become bogged down with all the epsilon management one needs to do to organise all the parameters that are flying around. The nonstandard approach can efficiently hide a large number of these parameters from view, and it can then become worthwhile to invest in the nonstandard framework in order to clean up the rest of a lengthy argument. Furthermore, an advantage of moving up to the infinitary setting is that one can then deploy all the firepower of an existing well-developed infinitary theory of mathematics (in this particular case, this would be the theory of linear algebra) out of the box, whereas in the finitary setting one would have to painstakingly finitise each aspect of such a theory that one wished to use (imagine for instance trying to finitise the rank-nullity theorem for rationals of bounded height).

The nonstandard approach is very closely related to use of compactness arguments, or of the technique of taking ultralimits and ultraproducts; indeed we will use an ultrafilter in order to create the nonstandard model in the first place.

I will also discuss a two variants of both Theorem 1 and Theorem 2 which have actually shown up in my research. The first is that of the regularity lemma for polynomials over finite fields, which came up when studying the equidistribution of such polynomials (in this paper with Ben Green). The second comes up when is dealing not with a single finite collection of vectors, but rather with a family of such vectors, where ranges over a large set; this gives rise to what we call the sunflower lemma, and came up in this recent paper of myself, Ben Green, and Tamar Ziegler.

This post is mostly concerned with nonstandard translations of the “rank reduction argument”. Nonstandard translations of the “energy increment argument” and “density increment argument” were briefly discussed in this recent post; I may return to this topic in more detail in a future post.

Unipotent elements of the Lorentz group, and conic sections

In my discussion of the Oppenheim conjecture in my recent post on Ratner’s theorems, I mentioned in passing the simple but crucial fact that the (orthochronous) special orthogonal group of an indefinite quadratic form on can be generated by unipotent elements. This is not a difficult fact to prove, as one can simply diagonalise Q and then explicitly write down some unipotent elements (the magic words here are “null rotations“). But this is a purely algebraic approach; I thought it would also be instructive to show the geometric (or dynamic) reason for why unipotent elements appear in the orthogonal group of indefinite quadratic forms in three dimensions. (I’ll give away the punch line right away: it’s because the parabola is a conic section.) This is not a particularly deep or significant observation, and will not be surprising to the experts, but I would like to record it anyway, as it allows me to review some useful bits and pieces of elementary linear algebra.

Compressed sensing and single-pixel cameras

I’ve had a number of people ask me (especially in light of some recent publicity) exactly what “compressed sensing” means, and how a “single pixel camera” could possibly work (and how it might be advantageous over traditional cameras in certain circumstances). There is a large literature on the subject, but as the field is relatively recent, there does not yet appear to be a good non-technical introduction to the subject. So here’s my stab at the topic, which should hopefully be accessible to a non-mathematical audience.

For sake of concreteness I’ll primarily discuss the camera application, although compressed sensing is a more general measurement paradigm which is applicable to other contexts than imaging (e.g. astronomy, MRI, statistical selection, etc.), as I’ll briefly remark upon at the end of this post.