Notes and papers on algebra and algebraic combinatorics

Comments and corrections are welcome on all of these writings! (This includes "trivial" typos. 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.

• λ-rings: Definitions and basic properties.
Sourcecode and Github repository.
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 (originally written for a PRIMES reading project 2015, but massively extended since). It covers some binomial coefficient identities (such as Vandermonde convolution), lengths and signs of permutations, and various elementary properties of determinants (defined by the Leibniz formula).

• Darij Grinberg, Notes on linear algebra (unfinished draft, currently frozen).
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 Minnesota.

Notes taken in lectures:

Papers (publications and preprints):
• Darij Grinberg, A double Sylvester determinant, preprint.
PDF file.
Sourcecode of the paper.

We prove the vanishing of a determinant whose entries themselves are products of minors of two matrices. This generalizes one of the main results in Peter Olver's and my The n body matrix and its determinant.

• Darij Grinberg, Peter Olver, [Prop] The n body matrix and its determinant, arXiv:1802.02900.

The primary purpose of this note is to prove two recent conjectures concerning the n body matrix that arises in recent papers of Escobar--Ruiz, Miller, and Turbiner on the classical and quantum n body problem in d-dimensional space. First, whenever the masses are in a nonsingular configuration, meaning that they do not lie on an affine subspace of dimension ≤ n-2, the n body matrix is positive definite, and hence defines a Riemannian metric on the space coordinatized by their interpoint distances. Second, its determinant can be factored into the product of the order n Cayley--Menger determinant and a mass-dependent factor that is also of one sign on all nonsingular mass configurations. The factorization of the n body determinant is shown to be a special case of an intriguing general result proving the factorization of determinants of a certain form.

• Darij Grinberg, A basis for a quotient of symmetric polynomials (draft), draft of a preprint.
Sourcecode of the paper.
Slides of a talk: University of Connecticut (with sourcecode) and Massachusetts Institute of Technology (with sourcecode) and Drexel University (with sourcecode) and University of Minnesota (with sourcecode). (The last talk is the most complete and up-to-date.)
Related material: an extended abstract of this paper submitted for FPSAC 2019 (with sourcecode).

Consider the ring S of symmetric polynomials in k variables over an arbitrary base ring k. Fix k scalars a1, a2, ..., akk.
Let I be the ideal of S generated by hn-k+1 - a1, hn-k+2 - a2, ..., hn - ak (where hi stands for the i-th complete homogeneous symmetric polynomial).
The quotient ring S/I generalizes both the usual and the quantum cohomology of the Grassmannian.
We show that S/I has a k-module basis consisting of (residue classes of) Schur polynomials fitting into an k × (n-k)-rectangle; and that its multiplicative structure constants satisfy the same S3-symmetry as those of the Grassmannian cohomology. We furthermore find an analogue of the Pieri rule for complete homogeneous symmetric polynomials and a few other formulas.
We also study the quotient of the whole polynomial ring (not just the symmetric polynomials) by the ideal generated by the same k polynomials as I.

• Darij Grinberg, Jia Huang, Victor Reiner, [Prop] Critical groups for Hopf algebra modules, preprint.
[Prop] Sourcecode of the paper.
There is also a [Prop] detailed version with some more details in some places and a few alternative proofs.
Published in: Mathematical Proceedings of the Cambridge Philosophical Society, forthcoming.
The paper also appears as arXiv preprint arXiv:1704.03778, but the version on this website is updated more frequently.
Slides of a talk: University of Wisconsin, Madison (with sourcecode).

This paper considers an invariant of modules over a finite-dimensional Hopf algebra, called the critical group. This generalizes the critical groups of complex finite group representations studied by Benkart, Klivans, Reiner and Gaetz. A formula is given for the cardinality of the critical group generally, and the critical group for the regular representation is described completely. A key role in the formulas is played by the greatest common divisor of the dimensions of the indecomposable projective representations.

• Darij Grinberg, t-unique reductions for Mészáros's subdivision algebra, preprint.
Sourcecode of the paper. The paper also appears as arXiv preprint arXiv:1704.00839, but the version on this website is updated more frequently.
There is also a detailed version with some more details in some places and some background on Gröbner bases.

There is also an old version (corresponding to arXiv:1704.00839v2) (and its sourcecode), which proves a less general result through a somewhat different construction (which might be of independent interest).
Related material: an extended abstract of this paper submitted for FPSAC 2018 (with sourcecode).

Fix a commutative ring k, two elements β ∈ k and α ∈ k and a positive integer n. Let X be the polynomial ring over k in the n(n-1)/2 indeterminates xi,j for all 1 ≤ i < j ≤ n. Consider the ideal J of X generated by all polynomials of the form xi,j xj,k - xi,k (xi,j + xj,k + β) - α for 1 ≤ i < j < k ≤ n. The quotient algebra X / J (in some specific cases) has been introduced by Karola Mészáros as a commutative analogue of Anatol Kirillov's quasi-classical Yang-Baxter algebra. A natural question is to find a combinatorial basis of this quotient algebra. One can define the pathless monomials, i.e., the monomials in X that have no divisors of the form xi,j xj,k with 1 ≤ i < j < k ≤ n. The residue classes of these pathless monomials indeed span the k-module X / J; however, they turn out (in general) to be k-linearly dependent. More combinatorially: Reducing a given monomial in X modulo the ideal J by applying replacements of the form xi,j xj,k ↦ xi,k (xi,j + xj,k + β) + α always eventually leads to a k-linear combination of pathless monomials, but the result may depend on the choices made in the process.

More recently, the study of Grothendieck polynomials has led Laura Escobar and Karola Mészáros to defining a k-algebra homomorphism D from X into the polynomial ring k[t1, t2, ..., tn-1] that sends each xi,j to ti. For a certain class of monomials (those corresponding to "noncrossing trees"), they have shown that whatever result one gets by reducing the monomial modulo J, the image of this result under D is independent on the choices made in the reduction process. Mészáros has conjectured that this property holds not only for this class of monomials, but for any polynomial p ∈ X. We prove this result, in the following slightly stronger form: If p ∈ X, and if q ∈ X is a k-linear combination of pathless monomials satisfying p ≡ q mod J, then D(q) does not depend on q (as long as β, α and p are fixed).

We also find an actual basis of the k-module X / J, using what we call forkless monomials.

• Erik Aas, Darij Grinberg, Travis Scrimshaw, [Prop] Multiline queues with spectral parameters, draft of a preprint.
[Prop] Sourcecode of the paper.
There is also a [Prop] detailed version with some more details in some places.
Slides of a talk: Leibniz Universität Hannover (with sourcecode).
Slides of another talk: North Carolina State University (with sourcecode).

Using the description of multiline queues as functions on words, we introduce the notion of a spectral weight of a word by defining a new weighting on multiline queues. We show that the spectral weight of a word is invariant under a natural action of the symmetric group, giving a proof of the commutativity conjecture of Arita, Ayyer, Mallick, and Prolhac. We give a determinant formula for the spectral weight of a word, which gives a proof of a conjecture of the first author and Linusson.

• Darij Grinberg, Noncommutative Abel-like identities, preprint.
Sourcecode of the paper.
There is also a detailed version with expanded proofs.

Let L be a noncommutative ring. Let V be a finite set. For each s ∈ V, let xs be an element of L. Let X and Y be elements of L such that X + Y lies in the center of L.
We prove the following three identities, which generalize the classical Abel-Hurwitz identities:
• The sum of (X + ∑s ∈ S xs)|S| (Y - ∑s ∈ S xs)n-|S| over all subsets S of V equals the sum of (X + Y)n-k xi1 xi2 ... xik over all integers k and all k-tuples (i1, i2, ..., ik) of distinct elements of V.
• The sum of X (X + ∑s ∈ S xs)|S|-1 (Y - ∑s ∈ S xs)n-|S| over all subsets S of V equals (X + Y)n. (Here, the product X (X + ∑s ∈ S xs)|S|-1 has to be understood as 1 if S is empty.)
• The sum of X (X + ∑s ∈ S xs)|S|-1 (Y - ∑s ∈ S xs)n-|S|-1 (Y - ∑s ∈ V xs) over all subsets S of V equals (X + Y - ∑s ∈ V xs) (X + Y)n-1. (Here, again, denominators are meant to be cancelled before evaluation when S is empty or the whole set V or when V is empty.)

• Darij Grinberg and Alexander Postnikov, Proof of a conjecture of Bergeron, Ceballos and Labbé, to appear in the New York Journal of Mathematics.
Sourcecode of the paper. The paper also appears as arXiv preprint arXiv:1603.03138, but the version on this website is updated more frequently.
Published in: New York Journal of Mathematics, Volume 23 (2017), 1581--1610.
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é.

• Darij Grinberg, Shuffle-compatible permutation statistics II: the exterior peak set, preprint.
Sourcecode of the paper.
There is also a detailed version of the paper.
Slides of a talk: University of Washington, Seattle (with sourcecode).
Slides of a talk: University of Illinois at Urbana-Champaign (with sourcecode).
Slides of a related expository talk: University of Illinois at Urbana-Champaign (with sourcecode).
Slides of a talk: Dartmouth College, Hanover (with sourcecode).

This is a continuation of the paper Shuffle-compatible permutation statistics" by Ira M. Gessel and Yan Zhuang. We show that the exterior peak set is a shuffle-compatible permutation statistic (as conjectured by Gessel and Zhuang), using a notion of "Z-enriched (P, γ)-partitions" that generalizes the concepts of "P-partitions", "enriched P-partitions" and "left enriched P-partitions". Furthermore, we introduce the notion of "LR-shuffle-compatibility", which is a property stronger than shuffle-compatibility, and which we also verify for the permutation statistics Des, des, Lpk and Epk (but not maj, Rpk and Pk). Furthermore, we describe the kernel of the homomorphism from QSym to the shuffle algebra of the exterior peak set statistic (by finding two generating sets for this kernel), and we relate LR-shuffle-compatibility to dendriform algebra quotients of QSym in the same way as shuffle-compatibility itself relates to algebra quotients of QSym. We pose various questions about these concepts.

• Pavel Galashin, Darij Grinberg and Gaku Liu, Refined dual stable Grothendieck polynomials and generalized Bender-Knuth involutions, preprint (2016).
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.
Published in: The Electronic Journal of Combinatorics 23, Issue 3 (2016), Paper #P3.14.
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 3.0).
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.
Published in: The Electronic Journal of Combinatorics 24, Issue 2 (2017), Paper #P2.22.
Related material: an extended abstract of this paper submitted for FPSAC 2017 (with sourcecode).
Slides of a talk: Combinatorics Seminar at Brandeis, 5 April 2016 (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 2016 (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.
Published in: Canad. J. Math. 69 (2017), pp. 21--53.
Slides of a talk: MIT, 11 April 2016 (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?, unfinished draft.
PDF file.
Sourcecode of the paper and Github repository.
Slides of a talk: Combinatorial Algebra meets Algebraic Combinatorics, UQAM 2017 (with sourcecode), and, in a somewhat extended version, Cornell 2017 (with sourcecode).

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 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 7 October 2017).
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.
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.4, 20 November 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, An exercise on determinant-like sums.
PDF file.
Sourcecode of the paper.

Let n and r be integers with n ≥ 0 and r > 0. Let K be a field of characteristic 0. Let Sn denote the set of all permutations of {1, 2, ..., n}. If σ ∈ Sn is a permutation, then (-1)σ shall denote the sign of σ.
Find the smallest integer k ≥ 0 such that there exists an n × n-matrix (Ai, j)1 ≤ i ≤ n, 1 ≤ j ≤ n of rank ≤ r satisfying
sum( (-1)σ (A1, σ(1) + A2, σ(2) + ... + An, σ(n))k over all σ in Sn ) ≠ 0 .

• Darij Grinberg, Why quaternion algebras have rank 4 (version 0.1, 13 June 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 a slightly weaker Theorem 1. Sourcecode of all the files.

This is a five-part note about commutative algebra. Rings mean commutative rings with unity.

Part 1 (Integrality over rings) is an (over-formalized) writeup of proofs to some known and less known results about integrality over rings. If A is a subring of a ring B, and n is an integer, then an element u of B is said to be n-integral over A if there exists a monic polynomial P of degree n with coefficients in A such that P(u) = 0. We show that:
- (Theorem 1) An element u of B is n-integral over A if and only if there exists an n-generated (= generated by n elements) A-submodule U of B such that uU is a subset of U and such that v = 0 for every v in B satisfying vU = 0.
- (Theorem 1 as well) An element u of B is n-integral over A if and only if there exists an n-generated (= generated by n elements) A-submodule U of B such that 1 lies in U and uU is a subset of U.
- (Theorem 1 in the old version) An element u of B is n-integral over A if and only if there exists a faithful n-generated (= generated by n elements) A-submodule U of some B-module such that uU is a subset of U.
- (Theorem 2) If a0, a1, ..., an are elements of A and v is an element of B such that SUM_{i=0}^{n} aivi = 0, then SUM_{i=0}^{n-k} ai+kvi is n-integral over A for every 0 ≤ k ≤ n. (This result, and its Corollary 3, generalize exercise 2-5 in J. S. Milne's Algebraic Number Theory.)
- (Theorem 4) If some element v of B is m-integral over A, and some element u of B is n-integral over A[v], then u is nm-integral over A. (This is a known fact. I derive it from Theorem 1, just as most people do. Maybe I will also write up a different proof using resultants.)
- (Theorem 5) Any element of A is 1-integral over A. If some element x of B is m-integral over A, and some element y of B is n-integral over A, then x+y and xy are nm-integral over A. (This is known again. I use Theorem 4 to prove this.)
- (Corollary 6) Let v be an element of B, and n and m two positive integers. Let P be a polynomial of degree n-1 with coefficients in A, and let u = P(v). If vu is m-integral over A, then u is nm-integral over A. (This follows from Theorems 2 and 5 but may turn out useful, though I don't expect much.)

Part 2 (Integrality over ideal semifiltrations) gives a common generalization to integrality over rings (as considered in Part 1) and integrality over ideals (a less known, but still important notion).
We define an ideal semifiltration of a ring A as a sequence (Ii)i≥0. of ideals of A such that I0 = A and IaIb is a subset of Ia+b for any a ≥ 0 and b ≥ 0. (This notion is weaker than that of an ideal filtration, since we do not require that In+1 is a subset of In for every n ≥ 0.)
If A is a subring of a ring B, if (Ii)i≥0 is an ideal semifiltration of A, and if n is an integer, then an element u of B is said to be n-integral over (A,(Ii)i≥0) if there exists a monic polynomial P of degree n with coefficients in A such that P(u) = 0 and the i-th coefficient of P lies in Ideg P - i for every i in {0, 1, ..., deg P}.
While this notion is much more general than integrality over rings (which is its particular case when (Ii)i≥0 = (A)i≥0) and integrality over ideals (which is its particular case when B = A and (Ii)i≥0 = (Ii)i≥0 for some fixed ideal I), it still can be reduced to basic integrality over rings by a base change. Namely:
- (Theorem 7) The element u of B is n-integral over (A,(Ii)i≥0) if and only if the element uY of the polynomial ring B[Y] is n-integral over the Rees algebra A[(Ii)i≥0*Y]. (This Rees algebra A[(Ii)i≥0*Y] is defined as the subring I0Y0 + I1Y1 + I2Y2 + ... of the polynomial ring A[Y]. Not that I would particularly like the notation A[(Ii)≥0*Y], but I have not seen a better one.)
(The idea underlying this theorem is not new, but I haven't seen it stated in standard texts on integrality.)
Using this reduction, we can generalize Theorems 4 and 5:
- (Theorem 8, generalizing Theorem 5) An element of A is 1-integral over (A,(Ii)i≥0) if and only if it lies in I1. If some element x of B is m-integral over (A,(Ii)i≥0), and some element y of B is n-integral over (A,(Ii)i≥0), then x+y is nm-integral over (A,(Ii)i≥0). If some element x of B is m-integral over (A,(Ii)i≥0), and some element y of B is n-integral over A (not necessarily over (A,(Ii)i≥0) !), then xy is nm-integral over (A,(Ii)i≥0).
- (Theorem 9, generalizing Theorem 4) If some element v of B is m-integral over A, and some element u of B is n-integral over (A[v], (IiA[v])i≥0), then u is nm-integral over (A,(Ii)i≥0).
Note that Theorem 9 doesn't seem to yield Theorem 8 as easily as Theorem 5 could be derived from Theorem 4 !

Part 3 (Generalizing to two ideal semifiltrations) continues Part 2, generalizing a part of it even further:
Let A be a subring of a ring B. Let (Ii)i≥0 and (Ji)i≥0 be two ideal semifiltrations of A. Then, (IiJi)i≥0 is an ideal semifiltration of A, as well. Now, we can give a "relative" version of Theorem 7:
- (Theorem 11) An element u of B is n-integral over (A,(IiJi)i≥0) if and only if the element uY of the polynomial ring B[Y] is n-integral over the (A[I], (JiA[I])i≥0), where A[I] is a shorthand for the Rees algebra A[(Ii)i≥0*Y].
Using this, we can generalize the xy part of Theorem 8 even further:
- (Theorem 13) If some element x of B is m-integral over (A,(Ii)i≥0), and some element y of B is n-integral over (A,(Ji)i≥0), then xy is nm-integral over (A,(IiJi)i≥0).

Part 4 (Accelerating ideal semifiltrations) extends Theorem 7:
- (Theorem 16, a generalization of Theorem 7) Let s ≥ 0 be an integer. An element u of B is n-integral over (A,(Isi)i≥0) if and only if the element uYs of the polynomial ring B[Y] is n-integral over the Rees algebra A[(Ii)i≥0*Y].
Actually, this can be further generalized in the vein of Theorem 11 (to Theorem 15).
As a consequence, Theorem 2 is generalized as well.

Part 5 (Generalizing a lemma by Lombardi) is mostly about the following fact:
- (Theorem 22) Let x, y and u be three elements of B. If u is integral over A[x] and over A[y], then u is also integral over A[xy].
This generalizes Theorem 2 from Lombardi's Hidden Constructions (1). We also show a relative version (Theorem 23) and reprove Corollary 3.

• 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.3, 26 May 2014).
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.
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.

After proving the trace Cayley-Hamilton theorem, the note proceeds to derive a nilpotency criterion from it, as well as show some classical properties of adjugates:
where A and B are n×n-matrices.

• Darij Grinberg, Regular elements of a ring, monic polynomials and "lcm-coprimality".
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, 13 June 2017).
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, The 4-periodic spiral determinant (rough draft).
PDF file.
Sourcecode.

This note outlines an (ugly computer-assisted) proof of an explicit formula for the determinant of an n × n-matrix whose cells are filled in with four numbers a, b, c, d (looping periodically) in a spiral pattern (starting in cell (1, 1), then moving eastwards, then southwards, then westwards etc.). This answers and generalizes MathOverflow question #270539.

• Darij Grinberg, Elementary derivations of some results of linear optimization.
PDF file.
Sourcecode.

Various basic facts from linear optimization theory (separation theorems for convex hulls and conic hulls, Farkas's lemma, Gordan's and Stiemke's theorems, and the duality theorem in a few forms) are presented here with constructive proofs.

This has been mostly written in 2012, when I was learning combinatorial optimization from Alexander Schrijver's notes and was annoyed by the use of analysis in the proofs. I provide constructive and elementary proofs instead. The proofs are my own (except for the first proof of the separation theorem for cones, which follows David Bartl's 2011 paper); as a consequence, they are likely to be much longer than necessary. See Niels Lauritzen's Undergraduate Convexity and Alexander Schrijver's Theory of Linear and Integer Programming for textbooks which also give constructive proofs of the main results (most likely, better ones than mine).

• 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, PRIMES 2015 reading project: Problem set #3.
PDF file.
Sourcecode.

This gives a do-it-yourself proof (as a sequence of exercises) for the following fact:
Let (v1, v2, ..., vn) and (w1, w2, ..., wn) be two vectors with integer entries. If the Laurent polynomials x1v1 x2v2 ... xnvn + 1 and x1w1 x2w2 ... xnwn + 1 are not coprime in the ring of Laurent polynomials over the integers, then the vectors (v1, v2, ..., vn) and (w1, w2, ..., wn) are proportional (i.e., linearly dependent).
This fact is used in the famous Cluster Algebras III paper by Berenstein, Fomin and Zelevinsky, where it is proven using Newton polytopes. My proof avoids Newton polytopes (it was written for a project with high-school students).

• Darij Grinberg, On the logarithm of the identity on connected filtered bialgebras.
PDF file.
Sourcecode.
Related: Counterexample for MathOverflow #84345 (Sourcecode.)

This is a long (> 500 pages) "lab notebook" in which I have been recording various properties of Hopf algebras with detailed proofs back in the early 2010s. (It includes properties of the Eulerian and Dynkin idempotents; some variants of the Cartier-Milnor-Moore and Leray theorems; various basic facts facts like the invertibility of the antipode in a connected filtered Hopf algebra.)

I'm afraid that the document is neither well-organized nor particularly readable; most of the interesting results are probably found elsewhere. But in case it happens to be of use, here it is.

• 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.

Talk slides not corresponding to papers (mostly expository):
• The diamond lemma and its applications (May 2018, Student Combinatorics Seminar, UMN Minneapolis).
Sourcecode.
This is an exposition of Newman's diamond lemma, with (an outline of a) constructive proof and a few applications (including a glimpse at Gröbner bases). The target audience are students somewhat familiar with combinatorics.
• Integral-valued polynomials (October 2013, UConn Math Club).
Sourcecode.
This talk surveys some basic results about integral-valued (a.k.a. integer-valued) polynomials (such as the one that they can be written as Z-linear combinations of binomial coefficients). It is meant for interested undergraduates.

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 algebraic 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 (rather ugly) proof of a lemma for Rep#2.

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 have a proof now.

Algebra notes

Back to the main site

Darij Grinberg