All writings except for talks

Burman and Kulishov defined Lie elements in the group algebra k[S_n] by comparing, on every exterior power of the reflection representation V, the usual action of k[S_n] with the infinitesimal action induced by its action on V. They conjectured that the Lie algebra of all Lie elements is generated by the Kirchhoff differences 1 - (i j). We disprove this conjecture for n = 4 by exhibiting an explicit counterexample arising from the (2,2)-block of k[S₄]. More generally, we describe this Lie algebra in terms of the Artin--Wedderburn decomposition of k[S_n]: its hook blocks are determined by the action on V, whereas its non-hook blocks are arbitrary. Consequently, the primitive central idempotents of the non-hook blocks yield linearly independent obstructions to the conjecture. We also identify the Lie algebra generated by the Kirchhoff differences in terms of the derived algebra of the Lie algebra generated by transpositions. Along the way, we give an integral, and hence characteristic-free, proof that the exterior powers of V are the hook-shaped Specht modules.

We give a simple proof of a determinantal identity found by Procesi. The identity connects different minors of a symmetric (or partially symmetric) matrix, and originates in the invariant theory of the orthogonal group.

Consider the group algebra k[S_n] of the symmetric group S_n over a field k of characteristic 0. In this algebra, we define the dyadic shuffles S_n,k by

S_n,k = sum of incmat_k (w) w over all w ∈ S_n,

where incmat_k (w) is the number of k-tuples of disjoint 2-element subsets of [n] on which w increases (i.e., of all 2k-tuples (i₁, i₂, ..., i_k, j₁, j₂, ..., j_k) of distinct elements of [n] such that each p satisfies i_p < j_p and w(i_p) < w(j_p)).

These shuffles were already defined by Reiner, Saliola and Welker in 2011, who showed that these shuffles commute and have integer eigenvalues (acting on any representation of S_n).

We recover these results by showing that all these shuffles lie in a left ideal of k[S_n] that is a Gelfand model of S_n (that is, a representation that contains each irreducible representation exactly once). This Gelfand model is equipped with a natural filtration, and its associated graded module is the involution-based Gelfand model studied by Kodiyalam and Verma (2004) and by Adin, Postnikov and Roichman (2008).

We furthermore prove a number of general properties of multiplicity-free left ideals of k[S_n], as well as a few specific properties of our Gelfand model.

Let R be a commutative ring. We show that every homogeneous multivariate polynomial f over R of degree n splits into a product of n homogeneous linear forms over a suitable noncommutative ring extension of R.

The proof uses Bergman's Diamond Lemma: we define S by generators and relations, and the relations form a terminating reduction system that has no ambiguities and thus is confluent. An analogous result is also shown for inhomogeneous polynomials (with inhomogeneous factors). This easily follows from the homogeneous case by homogenizing and then setting the homogenizing variable equal to 1.

Consider a directed multigraph D that is balanced (i.e., at each vertex, the indegree equals the outdegree). Let A be its set of arcs. Fix an integer k. Let s be a vertex of D. We show that the number of k-element subsets B of A that contain no cycles but contain a path from each vertex to s (we call them "s-convergences") is independent of s. This generalizes known facts about spanning arborescences, acyclic orientations and maximal acyclic subdigraphs. Moreover, this result can be generalized even further, replacing "contain no cycles" with "have a given set of cycles".

In his 1951 thesis, P. M. Cohn described the kernel of the Dynkin operator on the tensor algebra. This note gives a modern exposition of this result with its proof, both in the case of a free module and in the case of an arbitrary module over a Q-algebra. (In the fully general case, a counterexample is given.) No novelty is claimed.

Let E be a nonempty finite set. A shade map on E is a map T : P(E) → P(E) such that toggling an element u ∉ T(F) in the input F does not change T(F). We prove that, if T is an inclusion-reversing shade map and G ⊆ E, then the simplicial complex

{F ⊆ E ∣ G ⊆ T(F)}

is collapsible. Equivalently, if S is an inclusion-preserving shade map, then the Alexander dual of

{F ⊆ E ∣ G ⊈ S(F)}

is collapsible. This is an Alexander-dual companion to the shade-map collapsibility theorem in The Elser nuclei sum revisited.

We study n-homomorphisms in the sense of Khudaverdian--Voronov, but generalized to maps from arbitrary rings to arbitrary commutative rings. We show that the sum of an n-homomorphism and an m-homomorphism is an n+m-homomorphism, and that the composition of an n-homomorphism and an m-homomorphism is an nm-homomorphism. The proofs are entirely combinatorial.

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

We address two variants of the classical necklace counting problem from enumerative combinatorics. In both cases, we fix a finite group G and a positive integer n. In the first variant, we count the “identity-product n-necklaces” — that is, the orbits of n-tuples (a₁, a₂, ..., a_n) ∈ Gⁿ that satisfy a₁a₂...a_n = 1 under cyclic rotation.

In the second, we count the orbits of all n-tuples (a₁, a₂, ..., a_n) ∈ Gⁿ under cyclic rotation and left multiplication (i.e., the operation of G on Gⁿ given by h · (a₁, a₂, ..., a_n) = (ha₁, ha₂, ..., ha_n)). We prove bijectively that both answers are the same, and express them as a sum over divisors of n.

Consequently, we generalize the first problem to n-necklaces whose product of entries lies in a given subset of G (closed under conjugation), and we connect a particular case to the enumeration of irreducible polynomials over a finite field with given degree and second-highest coefficient 0.

Let L be a noncommutative ring. Let V be a finite set of size n. 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 give a new proof that the k-th Young–Jucys–Murphy element J_k in the group algebra of S_n is annihilated by the polynomial ∏_{i = −k + 1}^{k − 1} (t − i). The proof is inspired by Igor Makhlin’s MathOverflow proof, but uses no linear algebra; its core is an algebraic computation found with the help of LLMs.

We then show that ∏_{i = −n + 2}^{n − 2} (J_n − i), for n ≥ 2, is 2(2n − 3)! / n! times the sum of all odd permutations in S_n.

We construct a surjective filtered morphism of connected graded coalgebras over Z that is injective on primitive elements but is not injective. As a consequence, we construct a nonzero coideal containing no nonzero primitive element. All tensor factors occurring in the coproduct of the source are direct summands, so the construction does not rely on any ambiguity in the notion of a subcoalgebra in the absence of flatness.

Given a finite Coxeter group W and a scalar q, we define the element L_q to be the sum of q^ℓ(w) w over all w ∈ W in the group algebra of W. We say that an element w ∈ W is W-length-symmetric if its coefficient in the commutator [L_a, L_b] is 0 for all scalars a, b in any commutative ring. We prove several sufficient criteria for elements to be W-length-symmetric. In particular, we show that any separable permutation (i.e., permutation avoiding the patterns 2413 and 3142) in the symmetric group S_n is S_n-length-symmetric. This is only a sufficient condition; other W-length-symmetric elements include (twisted) involutions and elements of dihedral parabolic subgroups.

Let k be a commutative ring, and let the symmetric group S_n act on the polynomial ring P = k[x₁, x₂, ..., x_n] by permuting the variables. We prove four classical results. First, the coinvariant algebra (the quotient of P by the ideal generated by the symmetric polynomials with constant term 0) is a free k-module of rank n!, with the residue classes of the Artin monomials as a basis. Second, P is a free module of rank n! over the ring P^S_n of symmetric polynomials, again with the Artin monomials as a basis. Third, if n! is invertible in k, the coinvariant algebra is the regular k[S_n]-module. Fourth, under the same hypothesis, P is a free left P^S_n[S_n]-module of rank 1. The first result follows from an elementary normal-form lemma for monic polynomials with pairwise relatively prime leading monomials. The second is proved by lifting the Artin basis. For the third, we use orbit harmonics with a strongly discrete point orbit, and the fourth follows by equivariantly lifting a regular basis of the coinvariant algebra.

Consider a square matrix A whose all principal minors are equal to 1. Over a field, this property is inherited by any integer power of A, but this is not the case over an arbitrary commutative ring. We show that it is the case over any well-behaved ring, including all reduced rings and quotients of commutative rings modulo integrally closed ideals. This generalizes Problem B5 of the 2021 Putnam contest.

Over arbitrary commutative rings, we identify a stronger property that is always inherited by powers: We say that a matrix A with entries a_i,j is 1-nullcyclic if all its diagonal entries are 1 and if all the cyclic products a_i1,i2 a_i2,i3 ... a_ik,i1 with k > 1 vanish. We show that the latter products are always integral over the ideal generated by the principal minors of A minus 1.

We also prove variants of the above results for matrices A whose diagonal entries can be arbitrary, and whose principal minors are equal to the corresponding products of principal minors.

We show that every polynomial of degree ≤ m over a commutative ring R can be split into a product of m factors of degree ≤ 1 over an extension S of R. This answers MathOverflow question #429134.

The proof involves diagonal symmetric polynomials in 2m variables and a variant of Garsia-Stanton descent monomials, but nothing beyond basic algebra is used without proof.

The above note has been edited for clarity, but I plan to write up my own version of this proof.

We introduce a new basis of the group algebra of the symmetric group, built using the left-to-right minima sets of permutations. We show that on this basis, the descent algebra acts by triangular operators, thus making it an analogue of a cellular basis. The proof involves Dynkin elements (nested commutators) of the free algebra and their interactions with the B-basis.

The somewhere-to-below shuffles are the elements

t_ℓ := cyc_ℓ + cyc_ℓ,ℓ+1 + cyc_{ℓ,ℓ+1,ℓ+2} + ... + cyc_{ℓ,ℓ+1,...,n}

(for ℓ ∈ {1, 2, ..., n}) in the group algebra k[S_n] of the symmetric group S_n. Their linear combinations are called the one-sided cycle shuffles. We determine the eigenvalues of the action of any one-sided cycle shuffle on any Specht module S^λ of S_n.

We generalize and prove a recursive relation conjectured by I. G. Macdonald for his "7th variation" of the Schur functions. This variation is a family of polynomials over a finite field that mimic the (straight and skew) Schur polynomials using powers of the Frobenius.

An introduction to algebraic combinatorics at early graduate level. Currently, 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).

Graduate-level introduction to rings and fields, assuming familiarity with groups. Contains some new results on strong gcd-sequences.

Graduate-level (but fairly detailed) introduction to the group algebra and the representation theory of the symmetric group. Covers Young symmetrizers, Specht modules, Garnir relations, Murphy bases, the Young natural basis and the Artin-Wedderburn theorem, among other topics (much more to be added one day).

Undergraduate-level but rigorous introduction to induction proofs, elementary number theory and counting. Assumes familiarity with logic, sets and proofs.

Let 𝒜 be the group algebra k[S_n] of the n-th symmetric group S_n over a commutative ring k. For any two subsets A and B of [n] = {1, 2, ..., n}, we define the elements

∇_B,A := sum of all permutations w ∈ S_n satisfying w(A) = B

and

˜∇_B,A := sum of all permutations w ∈ S_n satisfying w(A) ⊆ B

of 𝒜. We study these elements, showing in particular that their minimal polynomials factor into linear factors (with integer coefficients). We express the product ∇_D,C ∇_B,A as a Z-linear combination of ∇_U,V's.

More generally, for any two set compositions (i.e., ordered set partitions) A and B of [n], we define ∇_B,A to be the sum of all permutations w ∈ S_n that send each block of A to the corresponding block of B. This generalizes ∇_B,A. The factorization property of minimal polynomials does not extend to the ∇_B,A, but we describe the ideal spanned by the ∇_B,A and a further ideal complementary to it. These two ideals have a "mutually annihilative" relationship, are free as k-modules, and appear as annihilators of tensor product S_n-representations; they are also closely related to Murphy's cellular bases, Specht modules, pattern-avoiding permutations and even some algebras appearing in quantum information theory.

This mostly expository note gives a conceptual proof of Peel's hook exact sequence, one of the first nontrivial results in the modular representation theory of symmetric groups. It works over arbitrary commutative rings satisfying n = 0 when necessary, rather than only over finite fields.

The proof uses basic homological algebra and exterior algebra instead of ad-hoc computations with Young tableaux, and establishes the exactness of the sequence together with a k-linear chain contraction.

We generalize Reiner-Saliola-Welker's well-known but mysterious family of k-random-to-random shuffles from Markov chains on symmetric groups to Markov chains on the Type-A Iwahori–Hecke algebras. We prove that the family of operators pairwise commutes and has eigenvalues that are polynomials in q with non-negative integer coefficients. Our work generalizes work of Reiner–Saliola–Welker and Lafrenière for the symmetric group, and simplifies all known proofs in this case.

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. More explicitly, if χ_A = ∑_{i = 0}ⁿ c_n-i tⁱ, then ∑_{i = 0}ⁿ c_n-i Aⁱ = 0.

A less well-known fact, which I call the trace Cayley-Hamilton theorem, states that

kc_k + ∑_{i = 1}^k Tr(Aⁱ) c_k-i = 0

for every nonnegative integer k, where 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 trace Cayley-Hamilton theorems. As an intermediate result, we show that the derivative of χ_A is the trace of the adjugate matrix of t I_n - A.

After proving the trace Cayley-Hamilton theorem, the note derives a nilpotency criterion and proves 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.

We study the "top-to-random-and-reverse shuffle", defined as the top-to-random shuffle in the symmetric group algebra composed with the permutation w₀ (which sends each i to n + 1 - i). More generally, we analyze the composition of any B-basis element of the descent algebra with w₀. We show that the minimal polynomial of any such composition (over Q) factors into distinct linear factors, which correspond to the "signed knapsack numbers" of set compositions.

This is a counterpart to an analogous property of the B-basis elements themselves, which was proved by Brown using Bidigare's face monoid. In the case of the top-to-random-and-reverse shuffle, the minimal polynomial turns out to be ∏_{k ∈ {-n + 2} ∪ [-n + 4, n - 3] ∪ {0} ∪ {n}} (x - k).

Given a graded bialgebra H, we define maps p_α,σ : H → H using iterated (co)multiplications, multigraded projections and permutations of tensor factors. We prove formulas for the composition and convolution of two such maps. When H is cocommutative, these generalize Patras's 1994 results, which in turn generalize Solomon's Mackey formula.

We also construct a combinatorial Hopf algebra PNSym ("permuted noncommutative symmetric functions") that governs these maps for arbitrary connected graded bialgebras in the same way as the well-known NSym does in the cocommutative case. We end by outlining an application to checking identities for connected graded Hopf algebras.

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. Some additional lectures from 2023 and one from 2021.

Motivated by a question and some enumerative conjectures of Richard Stanley, we explore the equivalence classes of words in the Weyl algebra, k < D,U | DU - UD = 1 >. We show that each class is generated by the swapping of adjacent balanced subwords, i.e., those which have the same number of D's as U's, and give several other characterizations, as well as a linear-time algorithm for equivalence checking. Armed with this, we deduce several enumerative results about such equivalence classes and their sizes. We extend these results to the class of c-Dyck words, where every prefix has at least c times as many U's as D's. We also connect these results to previous work on bond percolation and rook theory, and generalize them to some other algebras.

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_λ).

The Dowker theorem is a classical result in the topology of finite spaces, claiming that any binary relation between two finite spaces defines two homotopy-equivalent complexes (the Dowker complexes). Recently, Barmak strengthened this to a simple-homotopy-equivalence. We reprove Barmak's result using a combinatorial argument that constructs an explicit acyclic matching in the sense of discrete Morse theory.

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.

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

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.

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.

Graduate-level introduction to graph theory. Some additional materials from 2017.

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.

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

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.

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_i1 x_i2 ... x_in 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.

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

Let n be a positive integer. Let A be an n×n matrix with integer entries, and let v be a column vector of size n with integer entries. For each integer m ≥ 0, define g_m to be the greatest common divisor of the n entries of A^mv.

Prove that if g_m = 1 for at least one integer m ≥ n, then g_m = 1 for every integer m ≥ 0.

We show that if A is an n × n-matrix, then the diagonal entries of each power A^m are uniquely determined by the principal minors of A, and can be written as universal (integral) polynomials in the latter. Furthermore, if the latter all equal 1, then so do the former. These results are inspired by Problem B5 on the Putnam contest 2021, and shed a new light on the behavior of minors under matrix multiplication.

Given three nonnegative integers p, q, r and a finite field F, how many Hankel matrices (x_i+j)_{0 ≤ i ≤ p, 0 ≤ j ≤ q} over F have rank at most r? The classical answer is |F|^2r when r ≤ min {p, q}; this was obtained using different tools by Daykin, Elkies, Garcia Armas, Ghorpade and Ram.

We prove a refinement: if the first k entries x₀, x₁, ..., x_k-1 are fixed, where k ≤ r ≤ min {p, q}, then there are |F|^2r-k ways to choose the remaining entries x_k, x_k+1, ..., x_p+q so that the resulting Hankel matrix has rank at most r. This generalizes, and gives an alternative proof of, a result by Anzis, Chen, Gao, Kim, Li and Patrias on evaluations of Jacobi-Trudi determinants over finite fields.

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.

We confirm three conjectures of Z.-W. Sun on determinants. First, we show that any odd integer n > 3 divides a determinant involving the Jacobi symbol. We then prove divisibility results concerning two families of determinants. Finally, for any odd prime p and integers c and d not divisible by p, we completely determine the Legendre symbol of a further determinant S_c(d, p).

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.

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_{i1, i2, ..., ip} 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.

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.

Consider a finite set E. Assume that each e ∈ E has a "weight" w(e) ∈ ℝ assigned to it, and any two distinct e, f ∈ E have a "distance" d(e, f) = d(f, e) ∈ ℝ 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, 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 adds new elements one by one while maximizing the perimeter at each step.

We use this to define numerical invariants, and show that the maximum-perimeter subsets of all sizes form a strong greedoid, while the maximum-perimeter subsets of any given size are the bases of a matroid. This essentially generalizes the "P-orderings" constructed by Bhargava to define 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 numerical invariants of E, w, and d arising from this construction, along with an analogue in which maximum-perimeter subsets are replaced by maximum-perimeter tuples, allowing repeated elements.

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.

Ein Skript über Wettbewerbsungleichungen. Im Moment ist nur das Kapitel über die AM-GM-Ungleichung und ihre Anwendungen fertig. Geschrieben für die deutsche IMO-Vorbereitung 2021.

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

Detailed introduction to rings and fields from scratch, starting with elementary number theory. Different parts are at different levels of completion.

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.

We study two simplicial complexes arising from a directed graph G = (V, E) with two chosen vertices s and t: the path-free complex, consisting of all subsets F ⊆ E that contain no path from s to t, and the path-missing complex, its Alexander dual. Using discrete Morse theory, we prove that both complexes have well-behaved homotopy types — either contractible or homotopy-equivalent to spheres.

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

Over a (not necessarily commutative) ring, we prove two determinantal identities that sum determinants indexed by integer tuples. We use them to derive variants of Pieri rules from the literature.

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.

Rigorous and detailed introduction to enumerative combinatorics at the undergraduate level. Chapters 1 and 2 done, covering various types of subset counting, inclusion-exclusion, binomial identities and more. Further topics are covered in the Fall 2022 lecture notes.

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.

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

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

The grouplike elements of a coalgebra over a field are known to be linearly independent over that field. We prove three variants of this result: a generalization to coalgebras over a commutative ring, where linear independence is replaced by a weaker statement; a stronger statement for commutative bialgebras under stronger assumptions; and a linear-independence result for characters of a bialgebra.

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

Fix integers n ≥ k ≥ 0. 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 a 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.

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 at most r satisfying

∑_{σ ∈ Sn} (-1)^σ (A_1,σ(1) + A_2,σ(2) + ... + A_n,σ(n))^k ≠ 0.

I prove an identity for matrices over noncommutative rings, generalizing a MathOverflow question by Tom Copeland.

This paper studies integrality over commutative rings and over ideal semifiltrations, a common generalization of integrality over rings and integrality over ideals. It begins with proofs of classical results about integral elements, including faithful-module criteria, transitivity, and closedness under sums and products.

It then reduces integrality over an ideal semifiltration to ordinary integrality over a ring by a Rees-algebra construction. This yields transitivity and closedness results in the new setting, extensions involving two semifiltrations and accelerated semifiltrations, and a generalization of a lemma of Lombardi concerning an element integral over both A[x] and A[y].

We show that if N is a n×n-matrix over a commutative ring K, and if f is a univariate polynomial over K, then there exist two univariate polynomials a and b over K such that det(f(N)) = f a + χ_N b, where χ_N denotes the characteristic polynomial of N.

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.

The primary purpose of this note is to prove two recent conjectures concerning the n-body matrix that arose in recent papers of Escobar-Ruiz, Miller, and Turbiner on the classical and quantum n-body problem in d-dimensional space. First, whenever the positions of 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.

These notes explain the basics of the theory of network flows, using elementary methods. Written for undergraduate graph-theory and combinatorics classes, they are more self-contained than the earlier course notes from which they derive and work in a more general setting.

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.

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.

In this expository note, we prove the Lucas and Babbage congruences for binomial coefficients. The proof is elementary (by induction) and works for arbitrary integer parameters (as opposed to merely for nonnegative integers). Afterwards, we also prove that 0^k + 1^k + ... + (p-1)^k is divisible by p for any prime p and any nonnegative integer k that is not a positive multiple of p-1.

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 monomial and fundamental quasisymmetric functions, (skew) Schur functions, dual immaculate functions, and quasisymmetric (P, ω)-partition enumerators.

We prove an antipode formula under conditions that include the case where the second order is total, giving a new self-contained proof of a result of Malvenuto and Reutenauer. We then generalize the formula to a setting in which a group acts on the double poset by automorphisms.

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.

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.

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 like the invertibility of the antipode; and much more.)

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

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

This note gives an algebraic proof that the formal power series exp and log (more precisely, exp x − 1 and log(1 + x)) are mutually inverse. Along the way, it proves basic properties of derivatives of formal power series.

These are the notes for a substitute lecture I gave in the 18.781 (Introduction to Number Theory) course at MIT in 2016. (Though they contain more material that fits into a single lecture; I omitted some results and only sketched some of the proofs in the actual lecture.)

In Section 1, I define the floor function and show some of its basic properties; I then prove de Polignac's formula for the exponent of a prime in n! and use it to show that binomial coefficients are integers (there are better proofs of this, but it illustrates the power of the formula).

In Section 2, I introduce the standard arithmetic functions (φ, Möbius, sum of divisors, etc.), define multiplicativity and Dirichlet convolution, and prove the standard results: Möbius and φ are multiplicative; Dirichlet convolution is associative; the sum of φ(d) over all divisors d of n is n; the sum of μ(d) over all divisors d of n is 0 unless n = 1; the Möbius inversion formula; the Dirichlet convolution of two multiplicative functions is multiplicative. A variant of the Dirichlet convolution (called the "lcm-convolution") is also studied and its associativity proved.

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

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.

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.

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.

In 1913, Fleck discovered the following fact: If p is a prime, j is an integer, and n and q are two nonnegative integers satisfying q ≤ (n-1) / (p-1), then p^q divides the sum of (-1)^m (n choose m) over all nonnegative integers m which are congruent to j modulo p.

This note gives a detailed and elementary proof of this congruence using nothing but matrices and a bit of abstract algebra. (No algebraic integers are used.)

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.

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.

Attempt at a rigorous introduction to linear algebra. Currently, only the basics of matrix algebra are finished. This was originally written to accompany my Math 4242 class at the University of Minnesota.

Thanks to Meghal Gupta for some of the proofs!

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.

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

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.

These are notes I have written back in 2011, 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). As I have since learned, there are much better and more informative references around.

It should be kept in mind that the notation in my notes is not standard 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).

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.

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.

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.

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.

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

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

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.

Notes I have taken in Etingof's MIT lectures. Still unfinished (and no current plans to finish).

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.

Answering MathOverflow question #88399, I compute a certain combinatorial n!×n!-determinant using the representation theory of symmetric groups.

Problem U275 in Mathematical Reflections 4/2013, with solution.

Let μ be the number-theoretical Möbius function, and let a_f be a real number for every positive integer f. Prove that, for all positive integers m and n,

∑_{d ∣ m} ∑_{e ∣ n} ∑_{g ∣ gcd(d, e)} (μ(g)/g) d e a_de/g = ∑_{f ∣ mn} f a_f.

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

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.

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.

Problem O222 in Mathematical Reflections 1/2012, with solution.

Let (a₁, a₂, ..., a_n) and (b₁, b₂, ..., b_n) be n-tuples of nonnegative reals, and let σ be a permutation of {1, 2, ..., n}. For each k in {1, 2, ..., n}, let c_k be the maximum of {a₁b_k, a₂b_k, ..., a_kb_k} ∪ {a_kb₁, a_kb₂, ..., a_kb_k}.

Prove that a₁b_σ(1) + a₂b_σ(2) + ... + a_nb_σ(n) ≤ c₁ + c₂ + ... + c_n. The solution file contains background on the problem.

I abandoned scribing these lectures when I realized Lusztig had his own notes. Only included for the sake of completeness.

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.

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.

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

This note supplies detailed lemmas on α-equivalence and substitution in the lambda calculus that are used implicitly in Chapter 1, §2 of Krivine's Lambda-calculus, types and models. It also proves that Krivine's definition of α-equivalence agrees with definitions used elsewhere, and proves substitution rules needed for MathOverflow question #65420. Already partly obsolete.

This note discusses five properties of sequences of complex numbers x₁, x₂, ..., x_n satisfying either the equation

x₁ = 1/x₁ + x₂ = 1/x₂ + x₃ = ... = 1/x_n-1 + x_n

or the equation

x₁ = 1/x₁ + x₂ = 1/x₂ + x₃ = ... = 1/x_n-1 + x_n = 1/x_n.

Two of these properties have been posted on MathLinks and seem to be olympiad folklore.

Philip Matchett Wood and Doron Zeilberger have constructed identities for the Fibonacci numbers f_n of the form

1f_n = f_n;

2f_n = f_n-2 + f_n+1;

3f_n = f_n-2 + f_n+2;

4f_n = f_n-2 + f_n + f_n+2;

...;

kf_n = sum of f_n-i over all i from a fixed finite "lacunar" set of integers ("lacunar" means that no two elements of this set are consecutive integers).

This lacunar set depends on k only, and is unique for every k.

In this note we prove a generalization of these identities: For any family (a₁, a₂, ..., a_p) of integers, there exists one and only one finite lacunar set S of integers such that every high enough n satisfies

f_n+a1 + f_n+a2 + ... + f_n+ap = sum of f_n+s over all s in S.

("High enough" means high enough that all f_n+ai and all f_n+s are well-defined (some a_i as well as some elements of S may be negative).)

The proof uses the Fibonacci-approximating properties of the golden ratio φ; it would be interesting to find a purely combinatorial proof.

Here I give a proof of a curious combinatorial result by Percy Alexander MacMahon (1916):

If H(m) denotes the product 0! 1! 2! ... (m-1)! for any integer m ≥ 0, then any three integers a, b, c ≥ 0 satisfy

H(b+c) H(c+a) H(a+b) | H(a) H(b) H(c) H(a+b+c).

The proof uses basic linear algebra and is self-contained (the main lemma is Vandermonde's determinant, a proof of which - slightly generalized - is included in the note). The ratio ( H(a) H(b) H(c) H(a+b+c) ) / ( H(b+c) H(c+a) H(a+b) ) is written as a determinant of an integral matrix in two ways.

The note concludes with a bonus: a proof of the well-known fact that the product of the pairwise differences between m integers is always divisible by H(m). This is not directly related to MacMahon's result above, but it uses the same lemma (a generalization of Vandermonde's determinant).

An exercise in Introduction to representation theory on deformations of algebras is generalized and solved.

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.

A (rather ugly) proof of a lemma for Rep#2.

This gives detailed proofs of the results in Section 4 of Hazewinkel's "Witt vectors".

A 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 proves a simple assertion for any given prime p: 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.

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

Proofs of some basic identities for symmetric functions stated in Hazewinkel's "Witt vectors". Warning: this is near-unreadably boring. 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)).

Lemma on formal power series for Witt#4. Can be used as an exercise in commutative algebra.

We use symmetric functions 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 and overkill proof.

The integrality criterion 9.93 in Hazewinkel's "Witt vectors" 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, it equals an integer times qn/r). This generalizes a wellknown combinatorics exercise and many others.

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 (aka 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 is rather simple and probably not new.

We show some divisibility relations for the (big aka universal) Witt polynomials w_n. For example (Theorem 7 (c)), for any positive integers n and k, 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).

Proof of the Chinese Remainder Theorem for modules (only a part of it; the rest was proven in Witt#5). Actually, this theorem follows from the (well-known) ring version by tensoring, but the proof given here avoids tensor products.