Darij Grinberg

Assistant Professor
Drexel University
Philadelphia, PA (USA)
/ Karlsruhe (Germany)

Email addresses: (anti-spam encoded)

• AB@gmail.com (main)
• AB@protonmail.com (backup)
• A.B@drexel.edu (teaching)

where A = darij and B = grinberg .

about | new | algebra | errata
qedmo | github | teaching
geo1 | geo2 | solutions | german

last update 18 Mar 2025
recent changes

This is a website for mathematics, elementary and advanced (mostly algebra and combinatorics).

Writings

Abstract Algebra and Combinatorics (papers, preprints and notes)
(including notes on Hopf algebras in combinatorics (joint with Victor Reiner), notes on lambda-rings, and Hopfalgebren (lecture notes after Prof. Hans-Jürgen Schneider, in German), and various exposition and research).

Teaching archive
(including homework sets, solutions and sometimes partial notes)

Errata and marginalia (to others' works)

German writings on Elementary Mathematics / Deutschsprachige Aufsätze über Elementarmathematik
(inkl. Arbeiten über Elementargeometrie und Lösungen von Wettbewerbsaufgaben)

Elementary Geometry: Publications and Unpublished notes

Solutions to review problems
(Some problems from American Mathematical Monthly and other sources, with my solutions.)

Lecture notes

These are quick links to some of my lecture notes. See the teaching archive for more of the respective classes, including homework sets (some with solutions).

• An introduction to the symmetric group algebra: 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, Young-Jucys-Murphy elements and the Artin-Wedderburn theorem, among other topics (much more to be added one day).

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

• Graph Theory: Graduate-level introduction to graph theory. Some additional materials from 2017.

• An Introduction to Algebraic Combinatorics: Power series and generating functions, partitions, permutations, alternating sums and Schur polynomials. Work in progress, but mostly complete.

• Mathematical Problem Solving 2020: Detailed introduction to some problem solving techniques and useful elementary results. Some additional lectures from 2023 and one from 2021.

• Enumerative Combinatorics: Rigorous and detailed introduction to enumerative combinatorics. 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.

• An introduction to the algebra of rings and fields: Graduate-level introduction to rings and fields, assuming familiarity with groups.

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

• Notes on linear algebra: Attempt at a rigorous introduction to linear algebra. Currently, only the basics of matrix algebra are finished.

Other works

The notes below have been written for various purposes. These are not my most useful writings (see Abstract Algebra and Combinatorics for those).

• Darij Grinberg, Notes on the combinatorial fundamentals of algebra (PRIMES 2015 reading project: problems and solutions).
  Sourcecode.
  A version without solutions, for spoilerless searching.
  
  A set of notes on binomial coefficients, permutations and determinants. Currently covers some binomial coefficient identities (the Vandermonde convolution and some of its variations), lengths and signs of permutations, and various elementary properties of determinants (defined by the Leibniz formula).
  
  The sourcecode of the project is also tracked on github.

• Darij Grinberg, On binomial coefficients modulo squares of primes.
  Sourcecode.
  An older version is also avaliable at https://arxiv.org/abs/1712.02095.
  
  We prove the following congruences, conjectured by Apagodu and Zeilberger: Let p be an odd prime, and r and s two nonnegative integers. Then,

  • the sum of (2n choose n) over all n = 0, 1, ..., p-1 is congruent to η_p modulo p²;
  • more generally, the sum of (2n choose n) over all n = 0, 1, ..., rp-1 is congruent to η_p times (the sum of (2n choose n) over all n = 0, 1, ..., r-1) modulo p²;
  • the sum of (n + m choose m)² over all n = 0, 1, ..., rp-1 and all m = 0, 1, ..., sp-1 is congruent to η_p times (the sum of (n + m choose m)² over all n = 0, 1, ..., r-1 and all m = 0, 1, ..., s-1) modulo p²,
  where η_p is a specific integer depending on the residue of p modulo 3 (namely, 0, 1 or -1, if the residue is 0, 1 and 2 respectively).
  

• Darij Grinberg, Fleck's binomial congruence using circulant matrices.
  Sourcecode.
  
  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.)
  

• Darij Grinberg, 18.781 (Spring 2016): Floor and arithmetic functions.
  Sourcecode.
  
  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.
  

• Darij Grinberg, A hyperfactorial divisibility (version 27 July 2015).
  There is also a detailed (and longer) version. It should best only be consulted if something is unclear about the brief version above.
  Sourcecode of both versions.
  
  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).
  

• Darij Grinberg, The Lucas and Babbage congruences.
  Sourcecode.
  
  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.
  

• Darij Grinberg, Zeckendorf family identities generalized.
  Also avaliable at https://arxiv.org/abs/1103.4507.
  Sourcecode.
  There is also a detailed (and twice as long) version (sourcecode). Sourcecode of old versions (2011).
  
  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.
  

• Darij Grinberg, Integrality over ideal semifiltrations.
  
  See the abstract algebra page for more about this preprint.

• Darij Grinberg, The Vornicu-Schur inequality and its variations (version 13 August 2007).
  
  Sourcecode.
  
  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.

• Darij Grinberg, An inequality involving 2n numbers (version 22 August 2007).
  Sourcecode.
  
  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 sum_{1≤i<j≤n} a_ia_j ≥ 0 or sum_{1≤i<j≤n} b_ib_j ≥ 0. Then,
  
  (sum_{1≤i≤n, 1≤j≤n, i \neq j} a_ib_j)² ≥ 4 sum_{1≤i<j≤n} a_ia_j sum_{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 sum_{1≤i<j≤n} a_ia_j ≥ 0 or sum_{1≤i<j≤n} b_ib_j ≥ 0).
  
  After proving Theorem 1.1, we apply it to establish some inequalities, including an n-numbers generalization of Walther Janous'
  
  a/(b+c) · (v+w) + b/(c+a) · (w+u) + c/(a+b) · (u+v) ≥ sqrt(3(vw+wu+uv)) ≥ 3(vw+wu+uv) / (u+v+w).

• Darij Grinberg, Math Time problem proposal #1 (with solution) (version 5 December 2010).
  Sourcecode.
  
  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
  
  sum_{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.]

• Darij Grinberg, Generalizations of Popoviciu's inequality (version 4 March 2009).
  This note was published in arXiv under arXiv:0803.2958, but the version there is older (20 March 2008), though the changes are non-substantial.
  Additionally, here you can find a "formal version" (PDF) of the note (i. e. a version where proofs are elaborated with more detail; you won't need the formal version unless you have troubles with understanding the standard one).
  Sourcecode.
  
  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 SUM_{i=1}^{n} f(x_i) + n(n-2) f(x) ≥ n SUM_{s=1}^{n} f(x + (x_s - x_s+r)/n),
  
  where indices are cyclic modulo n, and x = (x₁ + x₂ + ... + x_n)/n.

• Darij Grinberg, St. Petersburg 2003: An alternating sum of zero-sum subset numbers (version 14 March 2008).
  
  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
  SUM_{k=0}^{n} (-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 SUM_{t in T} a_t = 0.
  

• Darij Grinberg, Proof of a CWMO problem generalized (version 7 September 2009).
  Sourcecode.
  
  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.

• Darij Grinberg, An algebraic approach to Hall's matching theorem (version 6 October 2007).
  Sourcecode.
  
  There is also an abridged version, which is probably easier to read as it omits some straightforward details.
  
  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.
  
  It turned out that the idea is not new, having been discovered by Tutte long ago, rendering the above note completely useless.

• Darij Grinberg, Two problems on complex cosines (version 19 March 2011).
  A copy (possibly outdated) is also downloadable from the MathLinks forum as an attachment in the topic "Algebraic equation for 2 cos (pi/(n+2))".
  Sourcecode.
  
  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.

Texts written for internet forums:

- MO65420 (sourcecode). This shows some properties of alpha-equivalence and substitution in lambda-calculus that were required for MO question #65420. Already partly obsolete.