Notes and papers on algebra and algebraic combinatorics

Please keep in mind that most of these texts have never been proofread. Should you find any mistakes or have any other remarks, please let me know (at A@B.com, where A = darijgrinberg and B = gmail)!
Texts:
• Darij Grinberg and Victor Reiner, [Prop] Hopf Algebras in Combinatorics.
[Prop] Sourcecode of the notes, and [Prop] a version with solutions to exercises.
The paper also appears as arXiv preprint arXiv:1409.8356, but the version on this website is updated more frequently.

These notes -- originating from a one-semester class by Victor Reiner at the University of Minnesota -- survey some of the most important Hopf algebras appearing in combinatorics. After introducing coalgebras, bialgebras and Hopf algebras in general, we study the Hopf algebra of symmetric functions, including Zelevinsky's axiomatic characterization of it as a "positive self-adjoint Hopf algebra" and its application to the representation theory of symmetric and (briefly) finite general linear groups. The notes then continue with the quasisymmetric and the noncommutative symmetric functions, some Hopf algebras formed from graphs, posets and matroids, and the Malvenuto-Reutenauer Hopf algebra of permutations. Among the results surveyed are the Littlewood-Richardson rule and other symmetric function identities, Zelevinsky's structure theorem for PSHs, the antipode formula for P-partition enumerators, the Aguiar-Bergeron-Sottile universal property of QSym, and Hazewinkel's polynomial freeness of QSym. The notes are written with a graduate student reader in mind, being mostly self-contained but requiring a good familiarity with multilinear algebra and -- for the representation-theory applications -- basic group representation theory.

Comments are welcome (on anything here, but on these notes in particular)!

• λ-rings: Definitions and basic properties.
These are notes I have made while learning this subject myself; they contain just the basics of the theory (definitions of λ-rings and special λ-rings, Adams operations, Todd homomorphisms and some more). I have started them in 2011 chiefly to improve on the sloppiness of the λ-ring literature that I knew back then; as I am now aware, there are much better and more informative references around. It should be kept in mind that the notation I use is not the one prevalent in modern literature. What Hazewinkel, in his Witt vectors. Part 1, and Yau, in his Lambda-Rings, call a "λ-ring" is my "special λ-ring", and what they call "pre-λ-ring" is my "λ-ring". Also, Hazewinkel's Λ (A) is slightly different from mine (for example, where I set Π (K~, [u1, u2, ..., un]) = product (1 + uiT) from 1 till n, he sets Π (K~, [u1, u2, ..., un]) = ∏ (1 - uiT)-1 from 1 till n).
• Darij Grinberg, Notes on the combinatorial fundamentals of algebra.
PDF file.
Sourcecode and Github repository.
A version without solutions, for spoilerless searching.

A set of notes on binomial coefficients, permutations and determinants written for a PRIMES reading project 2015. Currently covers some binomial coefficient identities (the Vandermonde convolution and some of its variations), lengths and signs of permutations, and various elementary properties of determinants (defined by the Leibniz formula).

• Darij Grinberg, Notes on linear algebra (work in progress).
PDF file.
Github repository.

An attempt at a rigorous introduction to linear algebra, currently frozen (as it has proven to be more work than I have time for). It currently covers matrix operations (multiplications etc.), various properties of matrices (triangularity, invertibility, permutation) and some basics of vector spaces. It was written to accompany my Math 4242 class at the University of Minneapolis.

Notes taken in lectures:
• Fundamentals of formal distributions (Lecture 3 of Vertex algebras by Victor Kac).
This is a mix of my own writing and scribe notes for Victor Kac's 18.276 course at MIT in Spring 2015.
We define and prove basic properties of Laurent series, differential operators, formal distributions and delta-functions over an arbitrary commutative ring. (In particular, the operator (1/n!) (∂/(∂x))n is introduced without relying on division by n!; this allows its use in arbitrary characteristic.) Presumably, most of what is in these notes is well-known, but it seems to be not so easily found in literature.

Papers (publications and preprints):
• Darij Grinberg and Alexander Postnikov, Proof of a conjecture of Bergeron, Ceballos and Labbé, preprint.
Sourcecode of the paper. The paper also appears as arXiv preprint arXiv:1603.03138, but the version on this website is updated more frequently.
Slides of a talk: AMS Sectional Meeting, University of St. Thomas (with sourcecode).

The reduced expressions for a given element w of a Coxeter group (W, S) can be regarded as the vertices of a directed graph R(w); its arcs correspond to the braid moves. Specifically, an arc goes from a reduced expression a to a reduced expression b when b is obtained from a by replacing a contiguous subword of the form stst... (for some distinct s, t ∈ S) by tsts... (where both subwords have length ms, t, the order of st ∈ W). We prove a strong bipartiteness-type result for this graph R(w): Not only does every cycle of R(w) have even length; actually, the arcs of R(w) can be colored (with colors corresponding to the type of braid moves used), and to every color c corresponds an "opposite" color cop (corresponding to the reverses of the braid moves with color c), and for any color c, the number of arcs in any given cycle of R(w) having color in {c, cop} is even. This is a generalization and strengthening of a 2014 result by Bergeron, Ceballos and Labbé.

• Pavel Galashin, Darij Grinberg and Gaku Liu, Refined dual stable Grothendieck polynomials and generalized Bender-Knuth involutions, preprint (November 25, 2015).
Sourcecode of the paper. There is also an alternative version of the paper (with a different exposition, stressing the diamond-lemma perspective). It has its sourcecode too.
The paper also appears as arXiv preprint arXiv:1509.03803, but the version on this website is updated more frequently.
Slides of talks: AMS Central Fall Sectional Meeting, October 2015 in Chicago / University of Minnesota, Combinatorics Seminar, October 2015 (with sourcecode).

The dual stable Grothendieck polynomials are a deformation of the Schur functions, originating in the study of the K-theory of the Grassmannian. We generalize these polynomials by introducing a countable family of additional parameters, and we prove that this generalization still defines symmetric functions. For this fact, we give two self-contained proofs, one of which constructs a family of involutions on the set of reverse plane partitions generalizing the Bender-Knuth involutions on semistandard tableaux, whereas the other classifies the structure of reverse plane partitions with entries 1 and 2.

• Darij Grinberg, Double posets and the antipode of QSym, preprint (version 2.5).
Sourcecode of the paper and Github repository. There is also a detailed version with some more fine-grained proofs (probably useless).
The paper also appears as arXiv preprint arXiv:1509.08355, but the version on this website is updated more frequently.
Related material: an extended abstract of this paper submitted for FPSAC 2017 (with sourcecode).
Slides of a talk: Combinatorics Seminar at Brandeis, 5 April 2006 (with sourcecode). The results of this preprint appear in Chapter 1 of the talk.

We assign a quasisymmetric function to any double poset (that is, every finite set endowed with two partial orders) and any weight function on its ground set. This generalizes well-known objects such as monomial and fundamental quasisymmetric functions, (skew) Schur functions, dual immaculate functions, and quasisymmetric (P, ω)-partition enumerators. We then prove a formula for the antipode of this function that holds under certain conditions (which are satisfied when the second order of the double poset is total, but also in some other cases); this restates (in a way that to us seems more natural) a result by Malvenuto and Reutenauer, but our proof is new and self-contained. We generalize it further to an even more comprehensive setting, where a group acts on the double poset by automorphisms.

• Darij Grinberg, The Bernstein homomorphism via Aguiar-Bergeron-Sottile universality, preprint (version 2.0).
Sourcecode of the paper.
The paper also appears as arXiv preprint arXiv:1604.02969, but the version on this website is updated more frequently.
Slides of a talk: MIT, 11 April 2006 (with sourcecode). The results of this preprint appear in Chapter 2 of the talk.

If H is a commutative connected graded Hopf algebra over a commutative ring k, then a certain canonical k-algebra homomorphism H → H ⊗ QSym is defined. This homomorphism generalizes the "internal comultiplication" on QSym, and extends what Hazewinkel (in §18.24 of his "Witt vectors") calls the Bernstein homomorphism.
We construct this homomorphism with the help of the universal property of QSym as a combinatorial Hopf algebra (a well-known result by Aguiar, Bergeron and Sottile) and extension of scalars (the commutativity of H allows us to consider, for example, H ⊗ QSym as an H-Hopf algebra, and this change of viewpoint significantly extends the reach of the universal property).

• Darij Grinberg, Dual immaculate creation operators and a dendriform algebra structure on the quasisymmetric functions, preprint (version 6.0).
Sourcecode of the paper. There is also a detailed version of the paper (with some extra steps and a proof of Proposition 5.7).
The preprint also appears as arXiv preprint arXiv:1410.0079, but the version on this website is updated more frequently.
Slides of a talk: MIT, 11 April 2006 (with sourcecode). The results of this preprint appear in Chapter 3 of the talk.

The dual immaculate functions are a basis of the ring QSym of quasisymmetric functions which form one of the most natural analogues of the Schur functions. The dual immaculate function corresponding to a partition is a weighted generating function for immaculate tableaux in the same way as a Schur function is for semistandard Young tableaux; an "immaculate tableau" is defined similarly to a semistandard Young tableau, but the shape is a composition rather than a partition, and only the first column is required to strictly increase (whereas the other columns can be arbitrary; but each row has to weakly increase). Dual immaculate functions have been introduced by Berg, Bergeron, Saliola, Serrano and Zabrocki in arXiv:1208.5191, and have since been found to possess numerous nontrivial properties.
In this note, we prove a conjecture of Mike Zabrocki which provides an alternative construction for the dual immaculate functions in terms of certain "vertex operators" (Corollary 4.3 in the note).

• Darij Grinberg, A note on non-broken-circuit sets and the chromatic polynomial, preprint.
Sourcecode of the paper. The preprint also appears as arXiv preprint arXiv:1604.03063, but the version on this website is updated more frequently.

The purpose of this note is to demonstrate several generalizations of a classical formula for the chromatic polynomial of a graph -- namely, of Whitney's theorem. One generalization allows the exclusion of only some broken circuits, whereas another weighs these broken circuits with weight monomials instead of excluding them; yet another extends the theorem to the chromatic symmetric functions, and yet another replaces the graph by a matroid. Most of these generalizations can be combined (albeit not all of them: matroids do not seem to have chromatic symmetric functions).

• Darij Grinberg and Tom Roby, Iterative properties of birational rowmotion, preprint (version 6.0).
Sourcecode of the paper. The paper also appears as arXiv preprint arXiv:1402.6178, but the version on this website is updated more frequently.

Related material: [Prop] an extended abstract of this paper submitted for FPSAC 2014 (with [Prop] sourcecode).
Slides of talks: [Prop] March 2014 in Toronto and [Prop] June 2014 in Vienna.

A number of authors have studied a natural operation (under various names) on the order ideals (equivalently, antichains) of a finite poset, here called rowmotion. For certain posets of interest, the order of this map is much smaller than one would naively expect, and the orbits exhibit unexpected properties. In very recent work (inspired by discussions with Berenstein) Einstein and Propp describe how rowmotion can be generalized: first to the piecewise-linear setting of order polytopes (instead of acting on order ideals, the operation here acts on points inside the order polytope of the poset), then via detropicalization to the birational setting (here, the operation acts -- more or less -- on maps from the poset to an arbitrary field).

In the latter setting, it is no longer a priori clear even that birational rowmotion has finite order, and for many posets the order is indeed infinite. However, we show that, for the poset P = [p] × [q] (product of two chains), birational rowmotion has the same order, p+q, as ordinary rowmotion. We also show that birational (hence also ordinary) rowmotion has finite order for some other classes of posets, e.g., the upper, lower, right and left halves of the poset above, and trees having all leaves on the same level. Our methods are based on those used by Volkov to resolve the type AA (rectangular) Zamolodchikov Periodicity Conjecture, of which our result can be considered an analogue.

The proofs are at most sketched in the above abstract, while the main paper offers more detail.

• James Borger and Darij Grinberg, [Prop] Boolean Witt vectors and an integral Edrei-Thoma theorem (arXiv:1311.5031v3).
Published version: Selecta Mathematica, 22(2), pp. 595--629.

This is a spin-off from James Borger, Witt vectors, semirings, and total positivity.
We give explicit descriptions of the Witt vectors of the Boolean semiring. This includes the big Witt vectors, the Schur Witt vectors, and the p-typical Witt vectors. We use this to determine the Schur Witt vectors of the natural numbers. This can be viewed as an integral variant of the Edrei-Thoma theorem on totally positive power series. We also determine the cardinality of the Witt vectors of the semiring quotient of the natural numbers by a single relation of the form n = n + 1. It is countable for n = 0, 1, 2 but uncountable after that.

Other writings:
• Darij Grinberg, Do the symmetric functions have a function-field analogue? (draft).
PDF file.
Sourcecode of the paper and Github repository.

This is an attempt to construct an object which relates to the ring of symmetric functions in the same way as the polynomial ring Fq[T] (over a finite field) relates to the ring of integers. So, for example, while the ring of symmetric functions has bases indexed by partitions (~ conjugacy classes of permutations), this mythical object would have bases indexed by "function-field partitions" (~ conjugacy classes of matrices in GLn(Fq)).

I have not been able to say much about this object so far; the construction I have is rather indirect and the combinatorial meaning is yet to be found. But along the way, I found a nice (I believe) Fq[T]-analogue of Witt vectors in which the Carlitz action replaces exponentiation.

This is far from finished, and so far most proofs have yet to be written up.

• Darij Grinberg, On p-polynomials and Fp-vector subspaces of fields.
PDF file.
Sourcecode of the paper.

This expository note collects various proofs (some contributed by students at the PRIMES 2015 entrance competition) of the following facts (the first of which is classical, dating back at least to Oystein Ore in 1933):
• Let V be a finite additive subgroup of a field L, and let p be the characteristic of L. Then, the product of (X + v) over all v ∈ V (where X is an indeterminate) is a p-polynomial in X (that is, an L-linear combination of Xp0, Xp1, Xp2, ...).
• Let V be a finite additive subgroup of a field L. Let t be an element of L not lying in V. Then, the sum of 1 / (t + v) over all v ∈ V equals the product of all 1 / (t + v) over all v ∈ V multiplied by the product of all nonzero elements of V.
Three proofs are given for the first fact, and two proofs for the second. Generalizations are also discussed and proven.

Thanks to Meghal Gupta for devising some of the proofs!

• Darij Grinberg, Karthik Karnik, Anya Zhang, A generalization of Chio Pivotal Condensation (version 27 June 2016).
PDF file.
Sourcecode of the paper. The paper also appears as arXiv preprint arXiv:1606.08193, but the version on this website is updated more frequently.

The Chio pivotal condensation theorem is the fact that every n × n matrix A = (ai,j)1 ≤ i ≤ n, 1 ≤ j ≤ n with n ≥ 2 satisfies
det ( (ai,j an,n - ai,n an,j)1 ≤ i ≤ n-1, 1 ≤ j ≤ n-1 ) = an,nn-2 det A.
On the other hand, the Matrix-Tree theorem expresses the number (and, more generally, a weighted sum) of spanning trees of a graph as a determinant. In this note, we show that these two results have a common generalization. In its simplest form, the generalization computes det ( (ai,j af(i),n - ai,n af(i),j)1 ≤ i ≤ n-1, 1 ≤ j ≤ n-1 ), where f : {1, 2, ..., n} → {1, 2, ..., n} is a map satisfying f(n) = n. The result depends on whether the map f is "n-potent" (i.e., every element gets sent to n by a sufficiently high power of f) or not; the n-potent maps are in bijection with the trees on {1, 2, ..., n}.

• Darij Grinberg, The signed random-to-top operator on tensor space (draft) (version 27 August 2016).
PDF file.
Sourcecode of the paper. The paper also appears as arXiv preprint arXiv:1505.01201, but the version on this website is updated more frequently.

The purpose of this note is to answer a question I asked in 2010 on MathOverflow. It concerns the kernel of a certain operator on the tensor algebra T(L) of a free module L over a commutative ring k (an operator that picks out a factor from a tensor and moves it to the front, and takes an alternating sum of the results ranging over all factors – an algebraic version of what probabilists call the "random-to-top shuffle", albeit with signs). Originating in pure curiosity, this question has been tempting me with its apparent connections to the random- to-top and random-to-random shuffling operators as studied in Reiner-Saliola-Welker and Schocker. I have not (yet?) grown any wiser from these connections, but I was able to answer the question, and the answer seems (to me) to be interesting enough to warrant some publicity.

• Darij Grinberg, On the PBW theorem for pre-Lie algebras (version 16 July 2016).
PDF file.
Sourcecode of the paper.

Guin and Oudom have constructed a coalgebra isomorphism U(A-) → Sym(A) for any pre-Lie algebra A (over any commutative ring), where U(A-) denotes the universal enveloping algebra of the Lie algebra A- canonically constructed from A. Here we reprove this isomorphism (using a more general construction), and explore its properties; we furthermore apply the results to MathOverflow question #102874.

• Darij Grinberg, A constructive proof of Orzech's theorem (version 1.3, 26 June 2016).
PDF file.
Sourcecode of the paper.

Let A be a commutative ring, and M a finitely generated A-module. A known fact in commutative algebra (due to Vasconcelos) states that any surjective A-module endomorphism of M is an isomorphism. In 1971, Morris Orzech found a generalization of this: If N is an A-submodule of a finitely generated A-module M, then any surjective A-module homomorphism N -> M is an isomorphism.

Orzech's proof was non-constructive, and it is not clear how to transform it into a constructive one (it reduces to a Noetherian case using the Hilbert basis theorem). In this note, I give a constructive proof based on the Cayley-Hamilton theorem.

• Darij Grinberg, Why quaternion algebras have rank 4 (version 0.1, 25 March 2016).
PDF file.
Sourcecode of the paper.

If k is a commutative ring and a and b are two elements of k, then the quaternion algebra Ha, b is defined as the k-algebra with generators i and j and relations i2 = a, j2 = b and ij = -ji. (This is a generalization of Hamilton's quaternions.)

A classical fact states that (1, i, j, ij) is a basis of Ha, b (as a k-module). In this expository note (written for a class), we show two proofs of this fact, and try to convey the ideas behind them. We also explain why the fact is nontrivial (although the proofs are not hard), and what pitfalls one might encounter when proving it.

The note will eventually be extended with additional sections, e.g., about the generalization to Clifford algebras.

• Darij Grinberg, A few facts on integrality (version 30 November 2010).
PDF file.
Detailed version with all the proofs much more formalized. Old version (version 20 August 2009) with slightly weaker Theorem 1. Sourcecode of all the files.

See main page for an abstract.

• Darij Grinberg, Poincaré-Birkhoff-Witt type results for inclusions of Lie algebras (version 1.5, 22 October 2013).
PDF file.
Detailed version with all the proofs (warning: extremely long and hard to read; warning 2: only chapters 1-4 are detailed). This was written in order to make sure the calculations really work out as they should. No reader should seriously need to read it.
Sourcecode of both files. It uses the LaTeX packages framed and comment. Toggle the "in" and "ex" parts of "\excludecomment{verlong}" and "\includecomment{vershort}" to switch between detailed (long) and normal (short) version.

This is (a slightly updated version of) my diploma thesis.

This paper provides detailed proofs of the main results of PBW for an inclusion of Lie algebras (arXiv:1010.0985) by Damien Calaque, Andrei Caldararu, and Junwu Tu. In particular, the fundamental lemma (Lemma 3.4) is proven in a new and significantly more elementary way, and the results are shown to hold over commutative rings (under appropriate splitting or flatness conditions) rather than over fields only.

The leading question of the paper is in how far the classical PBW (Poincaré-Birkhoff-Witt) theorem, stating that the associated graded algebra gr(U(g)) of the universal enveloping algebra U(g) of a Lie algebra g (over a field k) is isomorphic to the symmetric algebra Sym(g) of g, can be extended to the situation of a Lie algebra g with a Lie subalgebra h. The most logical guess for such an extension would be that the associated graded space of the vector space U(g) / (U(g)h) is isomorphic to Sym(g/h). In the Calaque-Caldararu-Tu paper, this was proven, along with some strengthenings (for example, we even get an isomorphism of h-modules, and with an additional condition on g and h, it turns out that the filtered h-module U(g) / (U(g)h) itself is isomorphic to Sym(g/h)) and generalizations. Here we reprove the main results of that paper by elementary means (nothing more advanced than the classical PBW theorem is used) and extend them to the case of k-modules (for k a commutative rings) rather than k-vector spaces (for k a field). We need additional assumptions for the results to hold in this generality, but flatness of g and g/h and splitting of the injection h → g are enough for almost everything (and for some results, the splitting of h → g alone suffices).

• Darij Grinberg, Collected trivialities on algebra derivations.
PDF file.
Sourcecode.

This note proves (in some detail) various basic properties of derivations of algebras that are commonly left to the reader. In particular, it shows that the commutator of derivations is a derivation; that derivations from a k-algebra A to an (A, A)-bimodule M are in a 1-to-1 correspondence with a certain class of A-algebra homomorphisms; that derivations from the tensor and symmetric algebras of a k-module can be built up from linear maps from this k-module.

• Darij Grinberg, The Clifford algebra and the Chevalley map - a computational approach (version 0.6, 3 June 2016).
PDF file.
Detailed version with all the proofs (warning: extremely long and hard to read). Sourcecode of all the files.

Let k be a commutative ring (with 1), L some k-module, and f : L × L → k be a bilinear form (not necessarily symmetric). We define the Clifford algebra Cl(L, f) as the tensor algebra ⊗ L of L, divided by the two-sided ideal generated by all terms of the form u ⊗ u - f(u, u) with u being a vector in L.

This note shows that, as a k-module, Cl(L, f) is isomorphic to the exterior algebra /\ L of L. This is a standard result in case of k being a field of characteristic 0 and f being symmetric, but we establish it independently of these assumptions. Moreover, the isomorphism /\ L → Cl(L, f) that we construct (inductively) is a projection of a k-module automorphism αf : ⊗ L → ⊗ L. Considering this αf for different f, we notice the surprising fact that the composition αf αg equals αf+g for any two bilinear forms f and g on L. We show that our isomorphism /\ L → Cl(L, f) is indeed the antisymmetrization map that is usually constructed in textbooks on Clifford algebras, if k is a field of characteristic 0 (or, at least, (dim L)! is invertible in k). We also show that the k-module Cl(L, f) has a basis similar to the standard basis of /\ L if L itself is a free k-module.

Update (2013): The results just listed are wellknown. They appear in Bourbaki's Algèbre IX, §9, no. 2-3, and in Chapter 2 of Ricardo Baeza's Quadratic Forms over Semilocal Rings, Lecture Notes in Mathematics 655, Springer 1978. The results listed below have a better chance to be new.

A further section describes some elements of Fix αsymm, which is the space of all tensors in ⊗ L that are fixed under αf for all symmetric bilinear forms f. Finally it is shown that if L is a direct sum of two k-submodules M and N and h is a bilinear form on L such that h (M × M) = 0, then there exists an isomorphism of k-modules /\ L → Cl(L, h) which sends (/\ L) M to (Cl(L, h)) M.

• Darij Grinberg, A representation-theoretical solution to MathOverflow question #88399 (version 2, 4 December 2013).
PDF file.
Sourcecode.

An answer to MathOverflow question #88399. (A combinatorial determinant evaluated using the representation theory of symmetric groups.)

• Darij Grinberg, A note on lifting isomorphisms of modules over PIDs (version 0.2, 2 March 2013).
PDF file.
Sourcecode.

This proves a few properties of finite free modules over principal ideal domains. The main result is: Let R be a PID. Let M be a finite free R-module, and A1 and A2 two R-linear maps from M to M. Then, A1(M) = A2(M) if and only if there exists an R-module automorphism U of M such that A1 = A2U. This result is then used to extend the claims from Keith Conrad's note Simultaneously aligned bases to a less restrictive case.

• Darij Grinberg, The trace Cayley-Hamilton theorem (version 16 September 2016).
PDF file.
Sourcecode.

Let K be a commutative ring. The famous Cayley-Hamilton theorem says that if χA = det (t In - A) ∈ K[t] is the characteristic polynomial of an n×n-matrix A over K, then χA(A) = 0. Speaking more explicitly, it means that if we write this polynomial χA in the form χA = sum( cn-i ti over i = 0, 1, ..., n ) (with cn-i ∈ K), then sum( cn-i Ai over i = 0, 1, ..., n) = 0. A less well-known fact, which I call the trace Cayley-Hamilton theorem, states that
kck + sum( Tr(Ai) ck-i over i = 1, 2, ..., k ) = 0
for every nonnegative integer k (where χA is written as sum( cn-i ti over i = 0, 1, ..., n ) as before, and where we set cn-i = 0 for every negative i).

The trace Cayley-Hamilton theorem is a folklore result, and sketches of proofs appear in the literature, but I have never seen a detailed proof that works for arbitrary commutative rings K written up. This note gives self-contained proofs for both the Cayley-Hamilton and the trace Cayley-Hamilton theorem. (The proof of Cayley-Hamilton is not new; it is merely written as a natural stepping stone.) As an intermediate result, we show that the derivative of the characteristic polynomial χA is the trace of the adjugate matrix of t In - A.

• Darij Grinberg, Regular elements of a ring, monic polynomials and "lcm-coprimality" (version 19 August 2016).
PDF file.
Sourcecode.

After proving some basic properties of monic polynomials over commutative rings (most importantly, that every polynomial can be divided with remainder by a monic polynomial), this note shows the following theorem:

Let f be a polynomial in n variables X1, X2, ..., Xn over a commutative ring.
Let G be a subset of { (i, j) ∈ {1, 2, ..., n}2 | i < j } .
If f is divisible by Xi - Xj for all (i, j) ∈ G, then f is divisible by the product of Xi - Xj over all (i, j) ∈ G.

• Darij Grinberg, A few classical results on tensor, symmetric and exterior powers (version 0.3, 25 March 2016).
PDF file.
Sourcecode.

Some basic facts about tensor products over commutative rings that I have written down with detailed proofs. "Detailed", as usual, means "a pain to read".

Let k be a commutative ring.
In 0.9, it is shown that if f : V -> V' and g : W -> W' are two surjective maps of k-modules, then Ker (f ⊗ g) = (the image of (Ker f) ⊗ W -> V ⊗ W) + (the image of V ⊗ (Ker g) -> V ⊗ W). This is extended to non-surjective maps under appropriate flatness conditions, and counterexamples are given for the general case.
In 0.11, the surjective case is extended to n modules.
In 0.12, the "pseudoexterior algebra" of a k-module is defined; this is the tensor algebra modulo identifying each tensor with each permutation of its tensorand times the sign of the permutation. This is almost the exterior algebra, but not the same if 2 is not invertible in k. In 0.13, the kernel of the map between pseudoexterior algebras induced by a surjective k-module map is computed.
In 0.14, the same is done for the symmetric algebra.
In 0.15, the same is done for the exterior algebra.

Back when I wrote this note, I hadn't realized that the claim about Ker (f ⊗ g) for surjective f and g (as well as its n-modules generalization) are in Keith Conrad's Tensor Products, II. They are a lot better explained there, so go there if you want to see them proven in a human-readable form.

• Darij Grinberg, A problem on bilinear maps (problem U228 in Mathematical Reflections) (version 0.7, 30 October 2012).
PDF file.
Sourcecode.

This note provides three solutions to the following problem:

Let L/K be a separable algebraic extension of fields and let V, W and U be L-vector spaces.
Let h : V × W → U be a K-bilinear map satisfying
h(xa, xb) = x2 h(a, b) for every x ∈ L, a ∈ V and b ∈ W.
Prove that h is L-bilinear.

One of the solution generalizes the problem from separable algebraic field extensions to commutative separable algebras over commutative rings. Along the way, some basic properties of separable field extensions are shown.

• Darij Grinberg, A note on bilinear forms.
PDF file.
Sourcecode.

Some elementary properties of bilinear forms over a field are proven. Everything in §1--§5 is standard linear-algebra material. In §6, the following fact is proven (Theorem 6.5 (c)): If V and W are two finite-dimensional vector spaces, and f is a bilinear form on V × W, then dim(V / (V ∩ Lf(W))) = dim(W / (W ∩ Rf(V))). Here, Lf(B) (for any subset B of W) denotes the set of all v ∈ V such that f(v, B) = 0, whereas Rf(A) (for any subset A of V) denotes the set of all w ∈ W such that f(A, w) = 0. In §7, some consequences of this fact are studied, such as the following (Proposition 7.3 (a)): If V and W are two finite-dimensional vector spaces, and f is a bilinear form on V × W, and if A is a vector subspace of V, then Lf(Rf(A)) = A + Lf(W).

This note is written in more detail than anyone except maybe an undergraduate will likely need. I suggest treating all statements as (relatively simple) exercises.

Work supervised:

I have been a mentor in the
PRIMES program at MIT from 2012 to 2015. In this function, I have supervised college students doing mathematical research projects; these projects led to the following writings by the students:

Sidenotes to Michiel Hazewinkel: Witt vectors. Part 1:

Witt vectors reside somewhere on the crossroads between algebra, combinatorics and number theory. Hazewinkel's text is, in my opinion, a must-read for everyone interested in at least two of these fields. It also sheds light on the representation theory of symmetric groups, the theory of symmetric polynomials, Hopf algebras and λ-rings.

I tend to advise Hazewinkel's text to anyone interested in any of the subjects mentioned, due to its very vivid and explanatory writing style. (It was the main thing that made me study combinatorial algebra!) Unfortunately, a multitude of typos makes reading it harder than it should be. If you have troubles with understanding something in the text, the reason may be in this list of errata (plus a few remarks). (Here is a more complete collection of errata which I sent to the author; these include obvious spelling mistakes which won't hinder anyone at understanding the text.)
Warning: Don't take my list of errata at face value. They can contain false positives and wrong corrections.

Here are some sidenotes I have made. Usually, these contain proofs of assertions which are mentioned without proof in Hazewinkel's work. Some contain generalizations/extensions (however, it's mostly the cheap kind of generalization, that barely adds any new content). I have written them for myself to keep track of what's true and what isn't; unfortunately they aren't very readable...
• Witt#0: Teichmüller representatives: This gives detailed proofs of the results in Section 4 of Hazewinkel's paper.

• Witt#1: The Burnside Theorem: Proof of the Burnside theorem, stating that a G-set (for a finite group G) is uniquely characterized (up to isomorphism) by specifying its number of H-invariant elements for each subgroup H of G. (This is Theorem 19.10 in Hazewinkel's paper.) This is easy and old, but I haven't seen a proof of this in freely accessible online sources, so I wrote it up myself.

• Witt#2: Polynomials that can be written as wn: This proves a simple assertion: A polynomial τ (in one or several variables) over the integers has the form wn01,...,τn) (for some polynomials τi over the integers) if and only if its derivative with respect to every indeterminate is divisible by pn. (Here, wn is the n-th p-adic Witt polynomial.) Generalized in Witt#5a below.

• Witt#3: Ghost component computations: This formalizes the principle of "working with ghost components" in Section 5 of Hazewinkel's article. In particular, Theorem 5.2 and some assertions on Frobenius and Verschiebung for p-adic Witt vectors are proven en detail.

• Witt#4: Some computations with symmetric functions: Caution, very boring / close to unreadable. I wanted to give proofs for some of the formulas in Section 9, but ended up proving the easy stuff ((9.37), (9.44), (9.57), (9.62), (9.70)) and leaving the hard stuff (particularly, the Schur polynomial identities) untouched. The only things of interest in this sidenote are Theorem 5 (b) (which generalizes (9.62) and can be used in combinatorics) and Theorem 9 (which yields an analogue to (9.70)).

• Witt#4a: Equigraded power series: Lemma for Witt#4. Can be used as an exercise in commutative algebra.

• Witt#4b: A combinatorial identity proven using symmetric functions identities: Theorem 5 (b) is used to prove the following combinatorial identity: For any natural n and real k, the sum of sign σ · kcycle σ over all permutations σ of {1, 2, ..., n} is equal to n! binom(k,n). Here, cycle σ means the number of cycles (including those of length 1) in the cycle decomposition of σ. This comes from an AoPS thread. Warning: sloppy writing.

• Witt#5: Around the integrality criterion 9.93: The integrality criterion 9.93 is proven and generalized. Some more criteria for ghost-Witt vectors are added. The result is applied to different circumstances. For instance (part of Theorem 20), we get that if n and r are positive integers, and q is an integer, then the sum of binom (q gcd(i, n), r gcd(i, n)) over all i from 1 till n is divisible by qn/r (in other words, if we divide it by qn/r, we get an integer). This generalizes a wellknown combinatorics exercise and many others.

• Witt#5a: Polynomials that can be written as big wn: We prove that a polynomial τ (in one or several variables) over the integers has the form wm01,...,τm) (for some polynomials τi over the integers) if and only if its derivative with respect to every indeterminate is divisible by m. Here, wm is the m-th big (a. k. a. universal) Witt polynomial. This is more general than Witt#2, but harder to prove (in particular, I need a result from Witt#5). Still it's rather simple and I doubt that it is new.

• Witt#5b: Some divisibilities for big Witt polynomials: We show some divisibility relations for the (big a. k. a. universal) Witt polynomials wn. For example (Theorem 7 (c)), for any positive integer n, the sum of wnk/gcd(i,n)gcd(i,n) over all i = 1, 2, ..., n is divisible by n as a polynomial (i. e., every coefficient is divisible by n).

• Witt#5c: The Chinese Remainder Theorem for Modules: Proof of the Chinese Remainder Theorem for modules (only a part of it; the rest was proven in Witt#5). Was written for use in Witt#5b. Now that I know that the Chinese Remainder Theorem for modules follows from the ring version by tensoring, and the ring version is known, this note is not of much use.

• Witt#5d: Analoga of integrality criteria for radical Witt polynomials and Witt#5e: Generalizing integrality theorems for ghost-Witt vectors: A rather esoteric generalization of Witt#5. Almost all proofs are exactly the same as in Witt#5 (and often are copypasted from Witt#5).

• Witt#5f: Ghost-Witt integrality for binomial rings: This generalizes some of the statements made in Witt#5 about the ring of integers to general binomial rings, and adds a couple more. Here is the only novel result (the equivalence of Gbin and Ibin, formulated for the nest {1,2,3,...} for the sake of simplicity): A sequence (b1, b2, b3, ...) of elements of a binomial ring A (for instance, of the ring ℤ) satisfies
n | ∑d|n φ(d) bn/d for every positive integer n
(where φ stands for Euler's totient function) if and only if there exists a sequence (q1, q2, q3, ...) of elements of A such that every positive integer n satisfies
bn = ∑d|n d binom(qd n/d, n/d),
with binom(x, y) denoting the binomial coefficient "x choose y". This is part of a long list of equivalent assertions, most of which are classical (and characterize the so-called "ghost-Witt vectors".
LaTeX sourcecode of the above.

Sidenotes to Pavel Etingof, Oleg Golberg, Sebastian Hensel, Tiankai Liu, Alex Schwendner, Dmitry Vaintrob, and Elena Yudovina: Introduction to representation theory:
• Rep#1: Deformations of a bimodule algebra: An exercise in Introduction to representation theory on deformations of algebras is generalized and solved.

• Rep#2: An algebraic proof of an analytic lemma: The famous representation-theoretical proof of Burnside's paqb theorem requires a lemma about roots of unity (stating that the arithmetic mean of finitely many roots of unity is never an algebraic integer unless it is = 0 or all the roots are equal). This is trivial using the triangle inequality in the complex numbers, but in contrast to many other uses of complex numbers, here we actually need to work in complex numbers and not just in any field extension of the rationals (in particular, we need to know that complex numbers have absolute values, and these absolute values are reals). This note was written as a remedy, giving a purely algebraical proof of the lemma. However, the proof grew longer and longer in writing, and is now probably ugly enough to serve as an example why algebraic proofs are not always better than analytical ones...

• Rep#2a: Finite subgroups of multiplicative groups of fields: A proof of a lemma for Rep#2. Rather ugly.

Errata to various books and papers:

When reading mathematics, I tend to keep track of errors and places that I don't understand by taking notes on the sides. In some cases, when I suspect that my notes might possibly be of some use to others, I put them online here.

Caveat lector: Do not take my lists of errata at face value. There is no guarantee that what I claim to be errors are actually errors, nor that what I believe to be corrections is more correct than the originals.

Further plans (outdated):
• Quadratic reciprocity for function fields, through determinant identities. This will take some time, I fear, if I'll write it up at all (there are much simpler proofs known).
• Any nilpotent matrix over a commutative ring has a nilpotent trace. But which is the lowest power of the trace to be identically 0? See here for an answer with a beautiful proof by Gert Almkvist. I have a different proof and if I succeed to write it up in a readable way, it will land here.
• If two polynomials over a commutative a ring have product 1, then both of them have the form (constant coefficient) + (nilpotent polynomial). This is known (one of the very first exercises in Atiyah/Macdonald) and easy, but a good example for how a proof using the axiom of choice (prime ideals etc.) can be turned into a constructive one using the method of trees. Another proof illustrates the usefulness of root adjunction to commutative rings.
• The set { (a1x1 + a2x2 + ... + anxn)m | a1, a2, ..., an are nonnegative integers with sum m } is a basis for the vector space of all m-th degree homogeneous polynomials in n variables x1, x2, ..., xn over a field of characteristic 0. This was conjectured by t0rajir0u on AoPS. I believe I have a proof now.

Algebra notes

Back to the main site

Darij Grinberg