Elementary works

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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

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

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

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.

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

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.

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.

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.

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

A rather esoteric generalization of Witt#5, proving necklace divisibilities (for integers and more generally elements of abelian groups) with variable coefficients. Almost all proofs are exactly the same as in Witt#5 (and often are copied from Witt#5).

The main result of this note is the following inequality:

Theorem 1.1. Let a₁, a₂, ..., a_n, b₁, b₂, ..., b_n be 2n reals. Assume that ∑_{1 ≤ i < j ≤ n} a_ia_j ≥ 0 or ∑_{1 ≤ i < j ≤ n} b_ib_j ≥ 0. Then,

(∑_{1 ≤ i ≤ n, 1 ≤ j ≤ n, i ≠ j} a_ib_j)² ≥ 4 ∑_{1 ≤ i < j ≤ n} a_ia_j ∑_{1 ≤ i < j ≤ n} b_ib_j.

This result can either be deduced from the Aczel inequality (one of the many variations on Cauchy-Schwarz), or verified more directly by algebraic manipulation. It appeared in the 39th Yugoslav Federal Mathematical Competition 1998 as problem 1 for the 3rd and 4th grades, but in a weaker form (the reals a₁, a₂, ..., a_n, b₁, b₂, ..., b_n were required to be nonnegative, while we only require ∑_{1 ≤ i < j ≤ n} a_ia_j ≥ 0 or ∑_{1 ≤ i < j ≤ n} b_ib_j ≥ 0).

After proving Theorem 1.1, we apply it to establish some inequalities, including an n-variable generalization of Walther Janous'

a / (b + c) · (v + w) + b / (c + a) · (w + u) + c / (a + b) · (u + v) ≥ √(3(vw + wu + uv)) ≥ 3(vw + wu + uv) / (u + v + w).

Let x₁, x₂, ..., x_n be real numbers such that x₁ + x₂ + ... + x_n = 1 and such that x_i < 1 for every i in {1, 2, ..., n}. Prove that

∑_{1 ≤ i < j ≤ n} x_ix_j / ((1 - x_i)(1 - x_j)) ≥ n / (2(n - 1)).

[Note that we do not require x₁, x₂, ..., x_n to be nonnegative — otherwise, the problem would be much easier.]

The point of this note is to prove a result by Dan Schwarz (appearing as problem 4 (c) on the Romanian MO 2004 for the 9th grade and as a generalization of CWMO 2006 problem 8 provided by a MathLinks user named tanlsth):

Let X be a set. Let n and m ≥ 1 be two nonnegative integers such that |X| ≥ m (n-1) + 1. Let B₁, B₂, ..., B_n be n subsets of X such that |B_i| = m for every i. Then, there exists a subset Y of X such that |Y| = n and Y has at most one element in common with B_i for every i.

We establish a general criterion for inequalities of the kind

convex combination of f(x₁), f(x₂), ..., f(x_n) and f(some weighted mean of x₁, x₂, ..., x_n)

≥ convex combination of f(some other weighted means of x₁, x₂, ..., x_n),

where f is a convex function on an interval I of the real axis containing the reals x₁, x₂, ..., x_n, to hold. Here, the left hand side contains only one weighted mean, while the right hand side may contain as many as possible, as long as there are finitely many. The weighted mean on the left hand side must have positive weights, while those on the right hand side must have nonnegative weights.

This criterion entails Vasile Cîrtoaje's generalization of the Popoviciu inequality (in its standard and in its weighted forms) as well as a cyclic inequality that sharpens another result by Vasile Cîrtoaje. This cyclic inequality (in its non-weighted form) states that

2 ∑_{i = 1}ⁿ f(x_i) + n(n - 2) f(x) ≥ n ∑_{s = 1}ⁿ f(x + (x_s - x_s+r) / n),

where indices are cyclic modulo n, and x = (x₁ + x₂ + ... + x_n) / n.

Using a lemma about finite differences (which is proven in detail), the following two problems are solved:

Problem 1 (Saint Petersburg Mathematical Olympiad 2003). For any prime p and for any n integers a₁, a₂, ..., a_n with n ≥ p, show that the number

∑_{k = 0}ⁿ (-1)^k · (number of subsets T of {1, 2, ..., n} with k elements such that the sum of these k elements is divisible by p)

is divisible by p.

Problem 2 (user named "lzw75" on MathLinks). Let p be a prime, let m be an integer, and let n > (p - 1)m be an integer. Let a₁, a₂, ..., a_n be n elements of the vector space F_p^m. Prove that there exists a non-empty subset T of {1, 2, ..., n} such that ∑_{t ∈ T} a_t = 0.

I am working on an update of this note focussing more on the finite differences lemma and less on Problems 1 and 2 (I want to add more about finite differences and a few other applications).

Hall's matching theorem (also called marriage theorem) has received a number of different proofs in combinatorial literature. Here is a proof which appears to be new. However, due to its length, it is far from being of any particular interest, except for one idea applied in it, namely the construction of the matrix S. See the corresponding MathLinks topic for details.

I have since learned that the idea is not new, having been discovered by Tutte long ago, rendering the above note completely useless.

The so-called Vornicu-Schur inequality states that x(a-b)(a-c) + y(b-c)(b-a) + z(c-a)(c-b) ≥ 0, where a, b, c are reals and x, y, z are nonnegative reals. Of course, this inequality only holds when certain conditions are imposed on a, b, c, x, y, z, and the purpose of this note is to collect some of the possible conditions that make the inequality valid. For instance, (a ≥ b ≥ c and x + z ≥ y) is one such sufficient condition (covering the most frequently used condition (a ≥ b ≥ c and (x ≥ y ≥ z or x ≤ y ≤ z))). Another sufficient condition is that x, y, z are the sidelengths of a triangle. An even weaker, but still sufficient one is that x, y, z are the squares of the sidelengths of a triangle. A yet different sufficient condition is that ax, by, cz are the sidelengths of a triangle - or, again, their squares.

These, and more, conditions are discussed, and some variations and equivalent versions of the Vornicu-Schur inequality are shown. The note is not primarily focused on applications, but a few inequalities that can be proven using the Vornicu-Schur inequality are given as exercises.