This is a website for mathematics, elementary and advanced (mostly algebra and combinatorics).
About me and this website (this includes a FAQ, a CV, and instructions on opening the files on this site). 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 (older classes)
(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.)
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.
We prove the following congruences,
conjectured by Apagodu and
Zeilberger:
Let p be an odd prime, and r and s two nonnegative integers. Then,
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 an 18.781 (Introduction to Number Theory)
lecture at MIT I substituted 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
(not the best way to do it, but a demonstration of 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_{1}, a_{2}, ..., 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_{1}, a_{2},
..., a_{n}, b_{1}, b_{2},
..., b_{n} be 2n reals. Assume
that sum_{1≤i<j≤n} a_{i}a_{j}
≥ 0 or sum_{1≤i<j≤n} b_{i}b_{j}
≥ 0. Then,
(sum_{1≤i≤n, 1≤j≤n, i \neq j} a_{i}b_{j})^{2} ≥
4 sum_{1≤i<j≤n} a_{i}a_{j}
sum_{1≤i<j≤n} b_{i}b_{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_{1},
a_{2}, ..., a_{n}, b_{1}, b_{2}, ..., b_{n}
were required to be
nonnegative, while we only require sum_{1≤i<j≤n}
a_{i}a_{j}
≥ 0 or sum_{1≤i<j≤n}
b_{i}b_{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_{1}, x_{2}, ..., x_{n} be real numbers
such that x_{1} + x_{2} + ... + x_{n} = 1 and
such that x_{i} < 1 for every i in {1,2,...,n}. Prove that
sum_{1≤i<j≤n} x_{i}x_{j} / ((1-x_{i})(1-x_{j})) ≥ n / (2(n-1)).
[Note that we do not require x_{1}, x_{2}, ..., 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_{1}), f(x_{2}), ..., f(x_{n})
and f(some weighted mean of
x_{1}, x_{2}, ..., x_{n})
≥ convex combination of f(some other weighted means of
x_{1}, x_{2}, ..., x_{n}),
where f is a convex function on an interval I of the real axis
containing the reals x_{1},
x_{2}, ..., 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_{1}
+ x_{2} + ... + 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_{1}, a_{2},
..., 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_{1}, a_{2}, ..., 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_{1}, B_{2}, ..., 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.
This note is quite a pain to read, mostly due to its length. If you
are really interested in the proof, try the
abridged version first.
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_{1}, x_{2}, ..., x_{n}
satisfying either the equation
x_{1} = 1/x_{1} + x_{2} = 1/x_{2} + x_{3} = ... = 1/x_{n-1} + x_{n}
or the equation
x_{1} = 1/x_{1} + x_{2} = 1/x_{2} + x_{3} = ... = 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.