Darij Grinberg: Algebra notes

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 and lecture notes:

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, the theory of Lyndon words, the Gessel-Reutenauer bijection, 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 written 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 called "special λ-ring" in my notes, and what they call "pre-λ-ring" is "λ-ring" in my notes. Also, Hazewinkel's Λ (A) is slightly different from mine (for example, where I set Π (K^~, [u₁, u₂, ..., u_n]) = product (1 + u_iT) from 1 till n, he sets Π (K^~, [u₁, u₂, ..., u_n]) = ∏ (1 - u_iT)^-1 from 1 till n).
Darij Grinberg, Notes on the combinatorial fundamentals of algebra.
Sourcecode and Github repository.
A version without solutions, for spoilerless searching.
The paper also appears as arXiv preprint arXiv:2008.09862, but the version on this website is updated more frequently.

A set of notes on binomial coefficients, permutations and determinants. 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).

The sourcecode of the project is also tracked on github.
Darij Grinberg, Notes on linear algebra (unfinished draft, currently frozen).
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 (multiplication 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.
Darij Grinberg, Enumerative Combinatorics (unfinished draft, currently frozen).
Ancillary content (homeworks, sourcecode).

A rigorous introduction to enumerative combinatorics at undergraduate level. Currently, the first two chapters are finished, covering binomial coefficients and basic counting strategies.
Darij Grinberg, Algebraic Combinatorics (unfinished draft, currently frozen).
Sourcecode.

An introduction to algebraic combinatorics at early graduate level. In its current stage of completion, it covers the theory of formal power series in one variable; basic properties of integer partitions up until the Jacobi Triple Product; permutations; determinant identities; symmetric polynomials up until the Littlewood-Richardson rule (proven a la Stembridge).
Darij Grinberg, Mathematical Problem Solving (unfinished draft, currently frozen).
Sourcecode.

Notes on various parts of (mostly fairly elementary) mathematics that appear in mathematical contests such as the IMO and Putnam. Includes in-depth treatments of elementary number theory, finite sums, the extremal and pigeonhole principles, invariants, basic counting and 3-term linear recurrences.
Darij Grinberg, Alternierende Summen: Aufgaben und Lösungen (unfertig) (in German).
Sourcecode.

Eine Aufgabensammlung (mit teilweisen Lösungen) über alternierende (d.h., vorzeichenbehaftete) Summen in der Kombinatorik und (elementaren) Algebra. Geschrieben für die deutsche IMO-Vorbereitung 2020.

Notes taken in lectures:

Hans-Jürgen Schneider: Hopfalgebren (German).
Sourcecode.
Mitschrift von Prof. Schneiders Vorlesungen über "Hopfalgebren und Quantengruppen" an der LMU München im WS 2008/2009 und im SS 2009. Das Skript ist gegen Ende des zweiten Semesters unvollständig, aber stellenweise von mir ergänzt.

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))ⁿ 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.
Pavel Etingof: 18.747: Infinite-dimensional Lie algebras (Spring term 2012 at MIT).
Sourcecode.
Notes I have taken in Etingof's MIT lectures. Still unfinished (and no current plans to finish).
George Lusztig: The first lecture of 18.745: Introduction to Lie algebras (Spring term 2012 at MIT).
Sourcecode.
I started scribing these lectures before I realized Lusztig would give out his own notes.

Papers (publications and preprints):

Published papers don't always appear in the same form below as they appear in the journals. In particular, editorial changes and (on occasion) some judgment calls from referees are not reflected in the preprints downloadable from this page. (However, the preprints sometimes contain more details and occasional post-publication corrections.)

Darij Grinberg, Nazar Korniichuk, Kostiantyn Molokanov, Severyn Khomych, The Pak–Postnikov and Naruse skew hook length formulas: a new proof, preprint, arXiv preprint arXiv:2310.18275.
Sourcecode of the paper.

Student project mentored via the Yulia's Dream program 2022-2023. (Proof found by the students, writing mostly by me.)

The classical hook length formula of enumerative combinatorics expresses the number of standard Young tableaux of a given partition shape as a single fraction. In recent years, two generalizations of this formula have emerged: one by Pak and Postnikov, replacing the number by a (rational) generating function, and one by Naruse, which generalizes the setting from a partition to a skew partition. Both generalizations appear to lie significantly deeper, with no simple proofs known. We combine them into a generating-function identity for skew partitions, and prove it in a fairly elementary way using recursion, determinants and simple combinatorics.
Darij Grinberg, Nazar Korniichuk, Kostiantyn Molokanov, Severyn Khomych, The diagonal derivative of a skew Schur polynomial, preprint, arXiv preprint arXiv:2402.14217.
Sourcecode of the paper.

Part of a student project mentored via the Yulia's Dream program 2022-2023.

We prove a formula for the image of a skew Schur polynomial s_λ/μ (x₁, x₂, ..., x_N) under the differential operator ∇ = ∂ / ∂x₁ + ∂ / ∂x₂ + ... + ∂ / ∂x_N. This generalizes a formula of Weigandt for ∇(s_λ).
Darij Grinberg and Richard P. Stanley, The Redei--Berge symmetric function of a directed graph, draft, arXiv preprint arXiv:2307.05569.
Sourcecode of the paper.
There is also a detailed version with some more details in some places.

Slides of talks: IPAC Seminar 2023 (with sourcecode) and SLC 90 Bad Boll 2023 (with sourcecode) and Haverford 2023 (with sourcecode) and KTH 2024 (with sourcecode).

Let D = (V, A) be a digraph with n vertices, where each arc a ∈ A is a pair (u, v) of two vertices. We study the Redei--Berge symmetric function U_D, defined as the quasisymmetric function ∑ L_{Des(w, D), n} ∈ QSym. Here, the sum ranges over all lists w = (w₁, w₂, ..., w_n) that contain each vertex of D exactly once, and the corresponding addend is L_{Des(w, D), n} := ∑ x_i₁ x_i₂ ... x_{i_n} summed over all n-tuples (i₁ ≤ i₂ ≤ ... ≤ i_n) of positive integers that satisfy i_p ≤ i_p+1 for each p satisfying (w_p, w_p+1) ∈ A (an instance of Gessel's fundamental quasisymmetric functions).

While U_D is a specialization of Chow's path-cycle symmetric function, which has been studied before, we prove some new formulas that express U_D in terms of the power-sum symmetric functions. We show that U_D is always p-integral, and furthermore is p-positive whenever D has no 2-cycles. When D is a tournament, U_D can be written as a polynomial in p₁, 2p₃, 2p₅, 2p₇, ... with nonnegative integer coefficients. By specializing these results, we obtain the famous theorems of Redei and Berge on the number of Hamiltonian paths in digraphs and tournaments, as well as a modulo-4 refinement of Redei's theorem.
Darij Grinberg and Ekaterina A. Vassilieva, The enriched q-monomial basis of the quasisymmetric functions, preprint (version 2.0).
Sourcecode of the paper.
The paper also appears as arXiv preprint arXiv:2309.01118, but the version on this website is updated more frequently.

Ancillary file: Some basic properties of compositions (and its sourcecode), which proves some elementary combinatorial lemmas.
Related material: three extended abstracts (FPSAC 2021, FPSAC 2022, FPSAC 2023) surveying parts of this paper and various other results. Also, an obsolete draft (sourcecode) preserved only for historical reasons.

We construct a new family (η_α^(q))_{α ∈ Comp} of quasisymmetric functions for each element q of the base ring. We call them the "enriched q-monomial quasisymmetric functions". When r : = q + 1 is invertible, this family is a basis of QSym. It generalizes Hoffman's "essential quasi-symmetric functions" (obtained for q = 0) and Hsiao's "monomial peak functions" (obtained for q = 1), but also includes the monomial quasisymmetric functions as a limiting case.

We describe these functions η_α^(q) by several formulas, and compute their products, coproducts and antipodes. The product expansion is given by an exotic variant of the shuffle product which we call the "stufufuffle product" due to its ability to pick several consecutive entries from each composition. This "stufufuffle product" has previously appeared in recent work by Bouillot, Novelli and Thibon, generalizing the "block shuffle product" from the theory of multizeta values.
Darij Grinberg and Nadia Lafrenière, [Prop] The one-sided cycle shuffles in the symmetric group algebra, preprint (version 3.0).
Sourcecode of the paper.
The paper also appears as arXiv preprint arXiv:2212.06274, but the version on this website is updated more frequently.

Related material: an extended abstract of this paper submitted for FPSAC 2024 (with sourcecode).
Slides of talks: Waterloo Algebraic Combinatorics Seminar (with sourcecode) and April 2023 at George Washington University (with sourcecode).

Related drafts: Rook sums in the symmetric group algebra (sourcecode) on yet another family of well-behaved elements of the group algebra. Slides of a talk about it: April 2024 at Howard University (with sourcecode).

We study an infinite family of shuffling operators on the symmetric group S_n, which includes the well-studied top-to-random shuffle. The general shuffling scheme consists of removing one card at a time from the deck (according to some probability distribution) and re-inserting it at a position chosen uniformly at random among the positions below. Rewritten in terms of the group algebra R[S_n], our shuffle corresponds to right multiplication by a linear combination of the elements
t_ℓ := cyc_ℓ + cyc_ℓ,ℓ+1 + cyc_{ℓ,ℓ+1,ℓ+2} + ... + cyc_{ℓ,ℓ+1,...,n} ∈ R[S_n]
for all ℓ ∈ {1, 2, ..., n} (where cyc_{i₁, i₂, ..., i_p} denotes the permutation in S_n that cycles through i₁, i₂, ..., i_p).
We compute the eigenvalues of these shuffling operators and of all their linear combinations. In particular, we show that the eigenvalues of right multiplication by a linear combination λ₁t₁ + λ₂t₂ + ... + λ_nt_n (with λ₁, λ₂, ..., λ_n being reals) are the numbers λ₁m_I,1 + λ₂m_I,2 + ... + λ_nm_I,n, where I ranges over the lacunar subsets of {1, 2, ..., n-1} (i.e., over the subsets that contain no two consecutive integers), and where m_I,ℓ denotes the distance from ℓ to the next-higher element of I (which element is understood to be ℓ itself if ℓ ∈ I, and to be n+1 if ℓ > max I). We compute the multiplicities of these eigenvalues and show that if they are all distinct, the shuffling operator is diagonalizable. To this purpose, we show that the operators of right multiplication by t₁, t₂, ..., t_n on R[S_n] are simultaneously triangularizable, and in fact there is a combinatorially defined basis (the "descent-destroying basis", as we call it) of R[S_n] in which they are represented by upper-triangular matrices. The results stated here over R for convenience are actually stated and proved over an arbitrary commutative ring. We finish by describing a strong stationary time for the random-to-below shuffle, which is the shuffle in which the card that moves below is selected uniformly at random, and we give the waiting time for this event to happen.
Darij Grinberg, Commutator nilpotency for somewhere-to-below shuffles, preprint (version 2.0).
Sourcecode of the paper.
The paper also appears as arXiv preprint arXiv:2309.05340, but the version on this website is updated more frequently.

Given a positive integer n, we consider the group algebra of the symmetric group S_n. In this algebra, we define n elements t₁, t₂, ..., t_n by the formula
t_ℓ := cyc_ℓ + cyc_ℓ,ℓ+1 + cyc_{ℓ,ℓ+1,ℓ+2} + ... + cyc_{ℓ,ℓ+1,...,n} ,
where cyc_{ℓ, ℓ+1, ..., k} denotes the cycle that sends ℓ, ℓ+1, ..., k-1, k to ℓ+1, ℓ+2, ..., k, ℓ (respectively). These n elements are called the somewhere-to-below shuffles due to an interpretation as card-shuffling operators. In this paper, we show that their commutators [t_i, t_j] are nilpotent, and specifically satisfy the equalities
[t_i, t_j]^{ceiling((n-j)/2) + 1} = 0 for any i, j ∈ [n]
and
[t_i, t_j]^{j - i + 1} = 0 for i < j.
We discuss some further identities and possible generalizations.
Darij Grinberg and Tom Roby, Birational rowmotion on a rectangle over a noncommutative ring, preprint (version 3.0).
Sourcecode of the paper.
There is also a detailed version with some more details in some places.
The paper also appears as arXiv preprint arXiv:2208.11156, but the version on this website is updated more frequently.

Related material: an extended abstract of this paper submitted for FPSAC 2023 (with sourcecode).
Slides of talks: November 2021 in Kelowna (with sourcecode) and November 2021 at CAP (with sourcecode) and December 2022 at MIT (with sourcecode) and March 2023 at KTH (with sourcecode).

We extend the periodicity of birational rowmotion for rectangular posets to the case when the base field is replaced by a noncommutative ring (under appropriate conditions). This resolves a conjecture from 2014. The proof uses a novel approach and is fully self-contained.

Consider labellings of a finite poset P by |P| + 2 elements of a ring K: one label associated with each poset element and two constant labels for the added top and bottom elements. Birational rowmotion is a partial map on such labellings. It was originally defined by Einstein and Propp for K = R as a lifting (via detropicalization) of piecewise-linear rowmotion, a map on the order polytope O(P) := {order-preserving f : P → [0,1]}. The latter, in turn, extends the well-studied rowmotion map on the set of order ideals (or more properly, the set of order filters) of P, which correspond to the vertices of O(P). Dynamical properties of these combinatorial maps sometimes (but not always) extend to the birational level, while results proven at the birational level always imply their combinatorial counterparts. Allowing K to be noncommutative, we generalize the birational level even further, and some properties are in fact lost at this step.

In 2014, the authors gave the first proof of periodicity for birational rowmotion on rectangular posets (when P is a product of two chains) for K a field, and conjectured that it survives (in an appropriately twisted form) in the noncommutative case. In this paper, we prove this noncommutative periodicity and a concomitant antipodal reciprocity formula. We end with some conjectures about periodicity for other posets, and the question of whether our results can be extended to (noncommutative) semirings.
Darij Grinberg, The pre-Pieri rules, arXiv preprint arXiv:2110.03108.
Sourcecode of the paper.

We prove two determinantal identities and some of their corollaries, which include some variant Pieri rules that have appeared in the literature.
Jonah Blasiak, Omesh Dhar Dwivedi, Darij Grinberg, Multislant matrices and Jacobi--Trudi determinants over finite fields, arXiv preprint arXiv:2302.07239.
Published in: Finite Fields and Their Applications 91, 2023, 102262.

The problem of counting the F_q-valued points of a variety has been well-studied from algebro-geometric, topological, and combinatorial perspectives. We explore a combinatorially flavored version of this problem studied by Anzis et al. (2018), which is similar to work of Kontsevich, Elkies, and Haglund.
Anzis et al. considered the question: what is the probability that the determinant of a Jacobi-Trudi matrix vanishes if the variables are chosen uniformly at random from a finite field? They gave a formula for various partitions such as hooks, staircases, and rectangles. We give a formula for partitions whose parts form an arithmetic progression, verifying and generalizing one of their conjectures. More generally, we compute the probability of the determinant vanishing for a class of matrices ("multislant matrices") made of Toeplitz blocks with certain properties.
We furthermore show that the determinant of a skew Jacobi-Trudi matrix is equidistributed across the finite field if the skew partition is a ribbon.
Omesh Dhar Dwivedi, Darij Grinberg, On the rank of Hankel matrices over finite fields, arXiv preprint arXiv:2109.05415.
Published in: Linear Algebra and its Applications 641, 15 May 2022, pp. 156--181.

Given three nonnegative integers p, q, r and a finite field F, how many Hankel matrices (x_i+j)_{0 ≤ i ≤ q, 0 ≤ j ≤ q} over F have rank ≤ r ? This question is classical, and the answer (q^2r when r ≤ min {p, q}) has been obtained independently by various authors using different tools (Daykin, Elkies, Garcia Armas, Ghorpade and Ram). In this note, we study a refinement of this result: We show that if we fix the first k entries x₀, x₁, ..., x_k-1 for some k ≤ r ≤ min {p, q}, then the number of ways to choose the remaining p + q - k + 1 entries x_k, x_k+1, ..., x_p+q such that the resulting Hankel matrix (x_i+j)_{0 ≤ i ≤ q, 0 ≤ j ≤ q} has rank ≤ r is q^2r-k. This is exactly the answer that one would expect if the first k entries had no effect on the rank, but of course the situation is not this simple. The refined result generalizes (and provides an alternative proof of) a result by Anzis, Chen, Gao, Kim, Li and Patrias on evaluations of Jacobi-Trudi determinants over finite fields.
Darij Grinberg, On the square of the antipode in a connected filtered Hopf algebra.
Sourcecode of the paper.
There is also a detailed version with some more details in some places. It has its own sourcecode.
The paper also appears as arXiv preprint arXiv:2109.02101v2, but the version on this website is updated more frequently.
Published in: Communications in Mathematics 31 (2023), issue 1.

Marcelo Aguiar and Aaron Lauve have shown that if H is a connected graded Hopf algebra over a field, then its antipode S satisfies (id - S²)ⁿ (H_n) = 0 for any positive integer n, where H_n denotes the n-th graded component of H. In later work, Aguiar improved this to (id + S) (id - S²)^n-1 (H_n) = 0. For the Malvenuto-Reutenauer Hopf algebra, Aguiar and Lauve have furthermore shown the stronger claim (id - S²)^n-1 (H_n) = 0 for n > 1.
In this note, we generalize these results in several directions and reprove them using elementary manipulations of tensors. In particular, the connected graded Hopf algebra is replaced by a connected filtered coalgebra (with S² becoming a coalgebra homomorphism satisfying certain conditions).
Darij Grinberg, The Elser nuclei sum revisited.
Sourcecode of the paper.
There is also a detailed version with some more details in some places.
The paper also appears as arXiv preprint arXiv:2009.11527, but the version on this website is updated more frequently.
Published in: Discrete Mathematics & Theoretical Computer Science 23 (1), 2021, article 7012.

There is also an old version (corresponding to arXiv:2009.11527v1 with a correction) (and its sourcecode), which gives a different (less combinatorial, more computational) proof of the main theorem.
Slides of talks: Algebra Seminar, University of Connecticut 2021 (with sourcecode).

Fix a finite undirected graph G and a vertex v of G. Let E be the set of edges of G; assume that E ≠ ∅. We call a subset F of E pandemic if each of edge G has at least one endpoint that can be connected to v by an F-path (i.e., a path using edges from F only). In 1984, Elser showed that the sum of (-1)^|F| over all pandemic subsets F of E is 0. We give a simpler proof and discuss variants and generalizations.
Darij Grinberg, The Pelletier--Ressayre hidden symmetry for Littlewood--Richardson coefficients, preprint.
Sourcecode of the paper.
There is also a detailed version with some more details in some places.
The paper also appears as arXiv preprint arXiv:2008.06128, but the version on this website is updated more frequently.
Published in: Combinatorial Theory 1, 2021 (abridged version).

Slides of talks: Algebraic and Combinatorial Perspectives in the Mathematical Sciences 2020 (with sourcecode) and Drexel University Mathematics Colloquium 2020 (with sourcecode).

We prove an identity for Littlewood--Richardson coefficients conjectured by Pelletier and Ressayre. The proof relies on an (apparently novel) birational involution defined over any semiring.
Darij Grinberg, Petrie symmetric functions.
Sourcecode of the paper.
There is also a detailed version with some more details in some places.
The paper also appears as arXiv preprint arXiv:2004.11194, but the version on this website is updated more frequently.
Published in: Algebraic Combinatorics 5 (2022), no. 5, pp. 947--1013.

Related material: an extended abstract of this paper submitted for FPSAC 2020 (with sourcecode).
Slides of a talk: Institut Mittag-Leffler, Djursholm 2020 (with sourcecode) and poster at FPSAC 2020 (with sourcecode).

For any positive integer k and nonnegative integer m, we consider the symmetric function G(k, m) defined as the sum of all monomials of degree m that involve only exponents smaller than k. We call G(k, m) a Petrie symmetric function in honor of Flinders Petrie, as the coefficients in its expansion in the Schur basis are determinants of Petrie matrices (and thus belong to {0, 1, -1} by a classical result of Gordon and Wilkinson). More generally, we prove a Pieri-like rule for expanding a product of the form G(k, m) · s_μ in the Schur basis whenever μ is a partition; all coefficients in this expansion belong to {0, 1, -1}. We also show that G(k, 1), G(k, 2), G(k, 3), ... form an algebraically independent generating set for the symmetric functions when 1 - k is invertible in the base ring, and we prove a conjecture of Liu and Polo about the expansion of G(k, 2k-1) in the Schur basis.
Darij Grinberg and Fedor Petrov, A greedoid and a matroid inspired by Bhargava's p-orderings, arXiv:1909.01965.
Published in: The Electronic Journal of Combinatorics 28(3) (2021), #P3.6.

Related material: an extended abstract of a related preprint submitted for FPSAC 2020 (with sourcecode).
Slides of talks: Institut Mittag-Leffler, Djursholm (with sourcecode) and a more expository talk at the Rutgers Experimental Mathematics Seminar (with sourcecode and video) and an updated version of the Rutgers talk at the New York Number Theory Zoom Seminar (with sourcecode).

Consider a finite set E. Assume that each e ∈ E has a "weight" w(e) ∈ R assigned to it, and any two distinct e, f ∈ E have a "distance" d(e,f) = d(f,e) ∈ R assigned to them, such that the distances satisfy the ultrametric triangle inequality d(a,b) ≤ max{d(a,c), d(b,c)}. We look for a subset of E of given size with maximum perimeter (where the perimeter is defined by summing the weights of all elements and their pairwise distances). We show that any such subset can be found by a greedy algorithm (which starts with the empty set, and then adds new elements one by one, maximizing the perimeter at each step). We use this to define numerical invariants, and also to show that the maximum-perimeter subsets of all sizes form a strong greedoid (a type of set system similar to a matroid), and the maximum-perimeter subsets of any given size are the bases of a matroid. This essentially generalizes the "P-orderings" constructed by Bhargava in order to define his generalized factorials, and is also similar to the strong greedoid of maximum diversity subsets in phylogenetic trees studied by Moulton, Semple and Steel.

We further discuss some numerical invariants of (E, w, d) stemming from this construction, as well as an analogue where maximum-perimeter subsets are replaced by maximum-perimeter tuples (i.e., elements can appear multiple times).
Darij Grinberg, The Bhargava greedoid as a Gaussian elimination greedoid, preprint.
Sourcecode of the paper.
The paper also appears as arXiv preprint arXiv:2001.05535, but the version on this website is updated more frequently.

Related material: an extended abstract of this paper submitted for FPSAC 2020 (with sourcecode).
Slides of talks: Institut Mittag-Leffler, Djursholm (with sourcecode) and a more expository talk at the Rutgers Experimental Mathematics Seminar (with sourcecode and video) and an updated version of the Rutgers talk at the New York Number Theory Zoom Seminar (with sourcecode).

This is an algebraic approach to the Bhargava greedoid introduced previously in a joint paper with Fedor Petrov. Here I show that any Bhargava greedoid is a Gaussian elimination greedoid (a greedoidal analogue of a representable matroid).
Alberto Dennunzio, Enrico Formenti, Darij Grinberg, Luciano Margara, Integrality of matrices, finiteness of matrix semigroups, and dynamics of linear cellular automata, arXiv:1907.08565.
Parts of this preprint have been incorporated into An efficiently computable characterization of stability and instability for linear cellular automata (by the same authors), which has been published in Journal of Computer and System Sciences 122 (2021), pp. 63--71.

Let K be a finite commutative ring, and let L be a commutative K-algebra. Let A and B be two n × n-matrices over L that have the same characteristic polynomial. The main result of this paper states that the set {A⁰, A¹, A², ...} is finite if and only if the set {B⁰, B¹, B², ...} is finite. We apply this result to the theory of discrete time dynamical systems. Indeed, it gives a complete and easy-to-check characterization of sensitivity to initial conditions and equicontinuity for linear cellular automata over the alphabet Kⁿ for K = Z/mZ, i.e. cellular automata in which the local rule is defined by n × n-matrices with elements in Z/mZ.

To prove our main result, we derive an integrality criterion for matrices that is likely of independent interest. Namely, let K be any commutative ring (not necessarily finite), and let L be a commutative K-algebra. Consider any n × n-matrix A over L. Then, A ∈ L^{n × n} is integral over K (that is, there exists a monic polynomial f ∈ K[t] satisfying f(A) = 0) if and only if all coefficients of the characteristic polynomial of A are integral over K. The proof of this fact relies on a strategic use of exterior powers (a trick pioneered by Gert Almkvist).
Alberto Dennunzio, Enrico Formenti, Darij Grinberg, Luciano Margara, Chaos and ergodicity are decidable for linear cellular automata over (Z/mZ)ⁿ, Information Sciences 539 (2020), pp. 136--144.

The following fragment of this paper is likely to have some independent value to algebraists: [Prop] On coprime characteristic polynomials over finite fields ([Prop] sourcecode).
Darij Grinberg, A double Sylvester determinant, preprint.
Sourcecode of the paper.
There is also a detailed version with some more details in some places.
The paper also appears as arXiv preprint arXiv:1901.11109, but the version on this website is updated more frequently.
Published in: Ars Mathematica Contemporanea 20 (2021), no. 2.

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.
Published in: SIAM Journal on Applied Algebra and Geometry 3(1), 2019, pp. 67--86.

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.
The paper also appears as arXiv preprint arXiv:1910.00207, but the version on this website is updated more frequently.

Slides of talks: University of Connecticut (with sourcecode) and Massachusetts Institute of Technology (with sourcecode) and Drexel University (with sourcecode) and University of Minnesota (with sourcecode) and University of Pennsylvania (with sourcecode) and CAP conference (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 a₁, a₂, ..., a_k ∈ k.
Let I be the ideal of S generated by h_n-k+1 - a₁, h_n-k+2 - a₂, ..., h_n - a_k (where h_i 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 S₃-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 168 (2020), pp. 473--503.
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).

Here we consider an invariant of a module 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.
Published in: SIGMA 14 (2018), 078. The preprint is more up-to-date (correcting mistakes and adding references).
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 x_i,j for all 1 ≤ i < j ≤ n. Consider the ideal J of X generated by all polynomials of the form x_i,j x_j,k - x_i,k (x_i,j + x_j,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 x_i,j x_j,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 x_i,j x_j,k ↦ x_i,k (x_i,j + x_j,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[t₁, t₂, ..., t_n-1] that sends each x_i,j to t_i. 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, preprint.
[Prop] Sourcecode of the paper.
There is also a [Prop] detailed version with some more details in some places.
The paper also appears as arXiv preprint arXiv:1810.08157, but the version on this website is updated more frequently.
Published in: Communications in Mathematical Physics 374 (2020), pp. 1743--1786.

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 x_s 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} x_s)^|S| (Y - ∑_{s ∈ S} x_s)^n-|S| over all subsets S of V equals the sum of (X + Y)^n-k x_i₁ x_i₂ ... x_{i_k} over all integers k and all k-tuples (i₁, i₂, ..., i_k) of distinct elements of V.
- The sum of X (X + ∑_{s ∈ S} x_s)^|S|-1 (Y - ∑_{s ∈ S} x_s)^n-|S| over all subsets S of V equals (X + Y)ⁿ. (Here, the product X (X + ∑_{s ∈ S} x_s)^|S|-1 has to be understood as 1 if S is empty.)
- The sum of X (X + ∑_{s ∈ S} x_s)^|S|-1 (Y - ∑_{s ∈ S} x_s)^n-|S|-1 (Y - ∑_{s ∈ V} x_s) over all subsets S of V equals (X + Y - ∑_{s ∈ V} x_s) (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é, 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.
Published in: New York Journal of Mathematics 23 (2017), pp. 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 m_{s, 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 c^op (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, c^op} 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.
The paper also appears as arXiv preprint arXiv:1806.04114, but the version on this website is updated more frequently.
Published in: Electronic Journal of Combinatorics 25 (2018), Paper #P4.17.

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.1).
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.

Related drafts: A Solomon Mackey formula for graded bialgebras (sourcecode) and Annihilating polynomials of Hopf algebra endomorphisms (sourcecode), about descent operators on arbitrary connected graded bialgebras. Also, slides of a talk (Bergen 2023) on these drafts.

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 Section 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 7.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: Canadian Journal of Mathematics 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, and form one of the most natural analogues of the Schur functions. The dual immaculate function corresponding to a composition 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.7 in the paper). The proof uses a dendriform structure on the ring QSym; we discuss the relation of this structure to known dendriform structures on the combinatorial Hopf algebras FQSym and WQSym.
Darij Grinberg, Generalized Whitney formulas for broken circuits in ambigraphs and matroids, 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.

Slides of talks: Algebraic and Combinatorial Perspectives in the Mathematical Sciences 2023 (with sourcecode).

This paper was formerly known as "A note on non-broken-circuit sets and the chromatic polynomial".

We explore several generalizations of Whitney's theorem -- a classical formula for the chromatic polynomial of a graph. Following Stanley, we replace the chromatic polynomial by the chromatic symmetric function. Following Dohmen and Trinks, we exclude not all but only an (arbitrarily selected) set of broken circuits, or even weigh these broken circuits with weight monomials instead of excluding them. Following Crew and Spirkl, we put weights on the vertices of the graph. Following Gebhard and Sagan, we lift the chromatic symmetric function to noncommuting variables. In addition, we replace the graph by an "ambigraph", an apparently new concept that includes both hypergraphs and multigraphs as particular cases. We show that Whitney's formula endures all these generalizations, and a fairly simple sign-reversing involution can be used to prove it in each setting. Furthermore, if we restrict ourselves to the chromatic polynomial, then the graph can be replaced by a matroid. We discuss an application to transitive digraphs (i.e., posets), and reprove an alternating-sum identity by Dahlberg and van Willigenburg.
Darij Grinberg and Tom Roby, Iterative properties of birational rowmotion, preprint (version 7.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.
Published in: (part 1) Electronic Journal of Combinatorics 23 (2016), Paper #P1.33 and (part 2) Electronic Journal of Combinatorics 22 (2015), Paper #P3.40 (both abridged).

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 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.5031v4.
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.
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 F_q[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 GL_n(F_q)).

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) F_q[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 F_p-vector subspaces of fields.
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 Øystein 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 X^p⁰, X^p¹, X^p², ...).
- 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 some of the proofs!
Darij Grinberg, Karthik Karnik, Anya Zhang, A generalization of Chio Pivotal Condensation (version 27 June 2016).
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 = (a_i,j)_{1 ≤ i ≤ n, 1 ≤ j ≤ n} with n ≥ 2 satisfies
det ( (a_i,j a_n,n - a_i,n a_n,j)_{1 ≤ i ≤ n-1, 1 ≤ j ≤ n-1} ) = a_n,n^n-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 ( (a_i,j a_f(i),n - a_i,n a_f(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).
Sourcecode of the paper.
The paper also appears as arXiv preprint arXiv:1505.01201, but the version on this website is updated more frequently.

This note answers 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, preprint.
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), preprint.
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, [Prop] The entry sum of the inverse Cauchy matrix.
[Prop] Sourcecode of the paper.
Published (with editorial changes) in: The Mathematical Intelligencer (2023).
The paper also appears as arXiv preprint arXiv:2301.09777.

The Cauchy matrix is the n×n-matrix whose (i, j)-th entry is 1 / (x_i + y_j), where x₁, x₂, ..., x_n, y₁, y₂, ..., y_n are 2n given numbers. A folklore theorem claims that if this matrix is invertible, then the sum of all entries of its inverse is x₁ + x₂ + ... + x_n + y₁ + y₂ + ... + y_n. In this brief expository note, we give a short and simple proof of this fact (using nothing but the definition of inverse matrices). We also discuss some properties of the matrix with entries min{x_i, y_j} (proofs left to the reader).
Darij Grinberg, An exercise on determinant-like sums, preprint.
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 S_n denote the set of all permutations of {1, 2, ..., n}. If σ ∈ S_n is a permutation, then (-1)^σ shall denote the sign of σ.
Find the smallest integer k ≥ 0 such that there exists an n × n-matrix (A_{i, j})_{1 ≤ i ≤ n, 1 ≤ j ≤ n} of rank ≤ r satisfying
sum( (-1)^σ (A_{1, σ(1)} + A_{2, σ(2)} + ... + A_{n, σ(n)})^k over all σ in S_n ) ≠ 0 .
Darij Grinberg, Why quaternion algebras have rank 4 (version 0.1, 13 June 2016), draft of a preprint.
Sourcecode of the paper.

If k is a commutative ring and a and b are two elements of k, then the quaternion algebra H_{a, b} is defined as the k-algebra with generators i and j and relations i² = a, j² = 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 H_{a, 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, Integrality over ideal semifiltrations, preprint. Detailed version with expanded proofs.
Sourcecode of the paper.
Also available:
- an old version of this paper (named "A few facts on integrality");
- a detailed version of this old version;
- an even older version with a slightly weaker Theorem 1;
- the sourcecodes of these old versions.
The paper also appears as arXiv preprint arXiv:1907.06125, but the version on this website is updated more frequently.

This is a paper on commutative algebra that I wrote as an undergraduate in 2010 when exploring integrality over rings. I have edited it in 2019 to improve readability and generality.
In the following, "ring" means "commutative ring with unity"; the same applies to algebras. We fix a ring A and an A-algebra B.

Section 1 (Integrality over rings) is an exposition of proofs to some known and less known results about integrality over rings. If 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.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 ⊆ U and such that v = 0 for every v ∈ B satisfying vU = 0.
- (Theorem 1.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 ∈ U and uU ⊆ U.
- (Theorem 1.11) If a₀, a₁, ..., a_n are elements of A (where n > 0) and v is an element of B such that SUM_{i=0}^{n} a_ivⁱ = 0, then SUM_{i=0}^{n-k} a_i+kvⁱ is n-integral over A for every 0 ≤ k ≤ n. (This result, and its Corollary 1.12, generalize exercise 2-5 in J. S. Milne's Algebraic Number Theory.)
- (Theorem 1.5) 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, standardly proven either using resulants or using Theorem 1.1. I give the latter proof.)
- (Theorem 1.7) 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 1.5 to prove this.)
- (Corollary 1.13) Let v ∈ B, and let n and m be 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.

Section 2 (Integrality over ideal semifiltrations) defines a common generalization to integrality over rings (as considered in Section 1) and integrality over ideals (a less popular, but still important notion).
We define an ideal semifiltration of a ring A as a sequence (I_i)_i≥0. of ideals of A such that I₀ = A and I_aI_b ⊆ I_a+b for any a ≥ 0 and b ≥ 0. (This notion is weaker than that of an ideal filtration, since we do not require that I_n+1 ⊆ I_n for every n ≥ 0.)
If (I_i)_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,(I_i)_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 I_{n - i} for every i in {0, 1, ..., n}.
While this notion is much more general than integrality over rings (which is its particular case when (I_i)_i≥0 = (A)_i≥0) and integrality over ideals (which is its particular case when B = A and (I_i)_i≥0 = (Iⁱ)_i≥0 for some fixed ideal I), it still can be reduced to basic integrality over rings by a Rees algebra trick. Namely:
- (Theorem 2.11) The element u of B is n-integral over (A,(I_i)_i≥0) if and only if the element uY of the polynomial ring B[Y] is n-integral over the Rees algebra A[(I_i)_i≥0*Y]. (This Rees algebra A[(I_i)_i≥0*Y] is defined as the subring I₀Y⁰ + I₁Y¹ + I₂Y² + ... of the polynomial ring A[Y].)
(The idea underlying this theorem is not new, but I have not seen it stated in standard texts on integrality.)
Using this reduction, we can generalize Theorems 1.5 and 1.7:
- (Theorem 2.13, generalizing Theorem 1.7 (a)) If some element x of B is m-integral over (A,(I_i)_i≥0), and some element y of B is n-integral over (A,(I_i)_i≥0), then x+y is nm-integral over (A,(I_i)_i≥0).
- (Theorem 2.14, generalizing Theorem 1.7 (b)) If some element x of B is m-integral over (A,(I_i)_i≥0), and some element y of B is n-integral over A (not necessarily over (A,(I_i)_i≥0) !), then xy is nm-integral over (A,(I_i)_i≥0).
- (Theorem 2.16, generalizing Theorem 1.5) If some element v of B is m-integral over A, and some element u of B is n-integral over (A[v], (I_iA[v])_i≥0), then u is nm-integral over (A,(I_i)_i≥0).

Section 3 (Generalizing to two ideal semifiltrations) continues Section 2, extending parts of it even further:
Let (I_i)_i≥0 and (J_i)_i≥0 be two ideal semifiltrations of A. Then, (I_iJ_i)_i≥0 is an ideal semifiltration of A, as well. Now, we can give a "relative" version of Theorem 2.11:
- (Theorem 3.2) An element u of B is n-integral over (A,(I_iJ_i)_i≥0) if and only if the element uY of the polynomial ring B[Y] is n-integral over the (A_[I], (J_iA_[I])_i≥0), where A_[I] is a shorthand for the Rees algebra A[(I_i)_i≥0*Y].
Using this, we can generalize Theorem 2.14 even further:
- (Theorem 3.4) If some element x of B is m-integral over (A,(I_i)_i≥0), and some element y of B is n-integral over (A,(J_i)_i≥0), then xy is nm-integral over (A,(I_iJ_i)_i≥0).

Section 4 (Accelerating ideal semifiltrations) extends Theorem 2.11:
- (Theorem 4.3, a generalization of Theorem 2.11) Let λ ≥ 0 be an integer. An element u of B is n-integral over (A,(I_λi)_i≥0) if and only if the element uY^λ of the polynomial ring B[Y] is n-integral over the Rees algebra A[(I_i)_i≥0*Y].
This can be further generalized in the vein of Theorem 3.2 (to Theorem 4.2).
As a consequence, Theorem 1.11 is generalized as well.

Section 5 (On a lemma by Lombardi) is mostly about the following fact:
- (Theorem 5.5) 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 is connected to Theorem 2 from Lombardi's Hidden Constructions (1). We also show a relative version (Theorem 5.6) and reprove Corollary 1.12.
Darij Grinberg, Poincaré-Birkhoff-Witt type results for inclusions of Lie algebras (version 1.5, 22 October 2013).
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.
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).
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).
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).
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 A₁ and A₂ two R-linear maps from M to M. Then, A₁(M) = A₂(M) if and only if there exists an R-module automorphism U of M such that A₁ = A₂U. 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.
Sourcecode.

Let K be a commutative ring. The famous Cayley-Hamilton theorem says that if χ_A = det (t I_n - 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( c_n-i tⁱ over i = 0, 1, ..., n ) (with c_n-i ∈ K), then sum( c_n-i Aⁱ over i = 0, 1, ..., n ) = 0. A less well-known fact, which I call the trace Cayley-Hamilton theorem, states that
kc_k + sum( Tr(Aⁱ) c_k-i over i = 1, 2, ..., k ) = 0
for every nonnegative integer k (where χ_A is written as sum( c_n-i tⁱ over i = 0, 1, ..., n ) as before, and where we set c_n-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 I_n - 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:
adj(AB) = adj B · adj A;
det(adj A) = (det A)^n-1;
adj(adj A) = (det A)^n-2 adj A,
where A and B are n×n-matrices.
Darij Grinberg, Regular elements of a ring, monic polynomials and "lcm-coprimality".
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 X₁, X₂, ..., X_n over a commutative ring.
Let G be a subset of { (i, j) ∈ {1, 2, ..., n}² | i < j } .
If f is divisible by X_i - X_j for all (i, j) ∈ G, then f is divisible by the product of X_i - X_j over all (i, j) ∈ G.

Thereafter, further properties of polynomials and power series are studied, and in particular an analogue of this theorem for power series is proven.
Darij Grinberg, Commutators, matrices and an identity of Copeland.
Sourcecode.

I prove an identity for matrices over noncommutative rings, generalizing a MathOverflow question by Tom Copeland.
Darij Grinberg, A few classical results on tensor, symmetric and exterior powers (version 0.3, 13 June 2017).
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 tensors of this form v₁ ⊗ v₂ ⊗ ... ⊗ v_n - (-1)^σ v_σ(1) ⊗ v_σ(2) ⊗ ... ⊗ v_σ(n) (where σ is a permutation of {1, 2, ..., n}, and where (-1)^σ denotes its sign). 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).
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, Why Ring(A, k) / G injects into Ring(A^G, k).
Sourcecode.

This gives an elementary proof of the following neat fact (Lemma 4.9 in Kucharczyk and Scholze, arXiv:1609.04717v2): Let a finite group G act on a commutative ring A, and let k be an integral domain. If two ring homomorphisms from A to k are equal on the invariant ring A^G, then there exists a g ∈ G such that each a ∈ A satisfies x(a) = y(ga).
Darij Grinberg, Comments on arXiv:2105.00538v3.
Sourcecode.

This gives new proofs of two isomorphisms of GL_n-modules found by Eoghan McDowell and Mark Wildon: the modular Wronskian isomorphism (an isomorphism of GL₂-modules, generalizing Hermite reciprocity to arbitrary base rings and to the full GL₂) and the complementary partition isomorphism (a categorification of the relation between the Schur polynomials corresponding to a partition and its box-complement, again stated over an arbitrary base ring as an isomorphism between Schur modules).

My note is rather terse and not very self-contained; I use the notations from McDowell and Wildon and rely on results from Fulton's Young tableaux book ([Ful97]).
Darij Grinberg, Similar matrices and equivalent polynomial matrices.
Sourcecode.

This expository note gives an elementary proof of the following fact: Two elements a and b of a ring R (not necessarily commutative) are conjugate in R if and only if the polynomials t - a and t - b in the polynomial ring R[t] are equivalent (i.e., there exist invertible polynomials p and q in R[t] such that (t - a) p = q (t - b)). When R is a matrix ring, this specializes to a classical result in linear algebra.
The proof is an elementary restatement of a module-theoretic argument suggested on MathOverflow.
Darij Grinberg, Elementary derivations of some results of linear optimization.
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).
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) = x² h(a, b) for every x ∈ L, a ∈ V and b ∈ W.
Prove that h is L-bilinear.

One of the solutions 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.
Sourcecode.

This gives a do-it-yourself proof (as a sequence of exercises) for the following fact:
Let (v₁, v₂, ..., v_n) and (w₁, w₂, ..., w_n) be two vectors with integer entries. If the Laurent polynomials x₁^v₁ x₂^v₂ ... x_n^v_n + 1 and x₁^w₁ x₂^w₂ ... x_n^w_n + 1 are not coprime in the ring of Laurent polynomials over the integers, then the vectors (v₁, v₂, ..., v_n) and (w₁, w₂, ..., w_n) 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.
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.
Sourcecode.

Some elementary properties of bilinear forms over a field are proven. Everything in Sections 1--5 is standard linear-algebra material. In Section 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 ∩ L_f(W))) = dim(W / (W ∩ R_f(V))). Here, L_f(B) (for any subset B of W) denotes the set of all v ∈ V such that f(v, B) = 0, whereas R_f(A) (for any subset A of V) denotes the set of all w ∈ W such that f(A, w) = 0. In Section 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 L_f(R_f(A)) = A + L_f(W).

This note is written in more detail than anyone except maybe an undergraduate will likely need. All results can be treated 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:

William Kuszmaul, Counting Permutations Modulo Pattern-Replacement Equivalences for Three-Letter Patterns, Electron. J. Comb., Volume 20, Issue 4 (2013), #P10.
A preprint of this paper is available as arXiv:1304.5667.
This paper won William the Davidson Fellows Scholarship in 2013.
William Kuszmaul and Ziling Zhou, Equivalence Classes in S_n for Three Families of Pattern-Replacement Relations, arXiv:1304.5669 (co-supervised with Sergei Bernstein).
William Kuszmaul, A New Approach to Enumerating Statistics Modulo n, arXiv:1402.3839.
William has earned the third place in the 2014 Intel Science Talent Search for this paper.
Eric Neyman, Cylindric Young Tableaux and their Properties, arXiv:1410.5039.
[Prop] Karthik Karnik, Anya Zhang, Combinatorial proof of Chio Pivotal Condensation.
This is an expository note (new proof of an old result) resulting from a PRIMES reading project. See also A generalization of Chio Pivotal Condensation.

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 w_n: This proves a simple assertion: A polynomial τ (in one or several variables) over the integers has the form w_n(τ₀,τ₁,...,τ_n) (for some polynomials τ_i over the integers) if and only if its derivative with respect to every indeterminate is divisible by pⁿ. (Here, w_n 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 σ · k^{cycle σ} 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 w_n: We prove that a polynomial τ (in one or several variables) over the integers has the form w_m(τ₀,τ₁,...,τ_m) (for some polynomials τ_i over the integers) if and only if its derivative with respect to every indeterminate is divisible by m. Here, w_m 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 w_n. For example (Theorem 7 (c)), for any positive integer n, the sum of w_nk/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 G_bin and I_bin, formulated for the nest {1,2,3,...} for the sake of simplicity): A sequence (b₁, b₂, b₃, ...) of elements of a binomial ring A (for instance, of the ring ℤ) satisfies
n | ∑_d|n φ(d) b_n/d for every positive integer n
(where φ stands for Euler's totient function) if and only if there exists a sequence (q₁, q₂, q₃, ...) of elements of A such that every positive integer n satisfies
b_n = ∑_d|n d binom(q_d 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 p^aq^b 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 (if rather long and complicated) proof of the lemma.
Rep#2a: Finite subgroups of multiplicative groups of fields: A (rather ugly) proof of a lemma for Rep#2.

See also my errata and marginalia to various papers, textbooks and notes.

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 { (a₁x₁ + a₂x₂ + ... + a_nx_n)^m | a₁, a₂, ..., a_n are nonnegative integers with sum m } is a basis for the vector space of all m-th degree homogeneous polynomials in n variables x₁, x₂, ..., x_n over a field of characteristic 0. This was conjectured by t0rajir0u on AoPS.

Algebra notes

Back to the main site

Darij Grinberg