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

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.

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

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.

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.

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.

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.

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

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.

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

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

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.

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

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.

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.

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

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

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.

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

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.

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.

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

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.

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