Other works
This is a legacy page: all its content is now available in my catalogue of writings, where it is better searchable and subject to updates. This page used to be part of the main index page.
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. 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 is also tracked
on github.
Darij Grinberg,
On binomial coefficients modulo squares of primes.
Sourcecode.
An older version is also available 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,
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 pq 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
0k + 1k + ... + (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 available 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 fn of the
form
1fn = fn;
2fn = fn-2 + fn+1;
3fn = fn-2 + fn+2;
4fn = fn-2 + fn +
fn+2;
...;
kfn = sum of fn-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 (a1, a2, ..., ap) of
integers, there exists one and only one finite lacunar set S of
integers such that every high enough n satisfies
fn+a1 + fn+a2 + ... +
fn+ap = sum of fn+s over all s in
S.
("High enough" means high enough that all
fn+ai and all fn+s are
well-defined (some ai 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 a1, a2,
..., an, b1, b2,
..., bn be 2n reals. Assume
that sum_{1≤i<j≤n} aiaj
≥ 0 or sum_{1≤i<j≤n} bibj
≥ 0. Then,
(sum_{1≤i≤n, 1≤j≤n, i \neq j} aibj)2 ≥
4 sum_{1≤i<j≤n} aiaj
sum_{1≤i<j≤n} bibj.
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 a1,
a2, ..., an, b1, b2, ..., bn
were required to be
nonnegative, while we only require sum_{1≤i<j≤n}
aiaj
≥ 0 or sum_{1≤i<j≤n}
bibj ≥ 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 x1, x2, ..., xn be real numbers
such that x1 + x2 + ... + xn = 1 and
such that xi < 1 for every i in {1,2,...,n}. Prove that
sum_{1≤i<j≤n} xixj / ((1-xi)(1-xj)) ≥ n / (2(n-1)).
[Note that we do not require x1, x2, ..., xn 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(x1), f(x2), ..., f(xn)
and f(some weighted mean of
x1, x2, ..., xn)
≥ convex combination of f(some other weighted means of
x1, x2, ..., xn),
where f is a convex function on an interval I of the real axis
containing the reals x1,
x2, ..., xn,
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(xi) + n(n-2)
f(x) ≥ n SUM_{s=1}^{n} f(x + (xs - xs+r)/n),
where indices are cyclic modulo n, and x = (x1
+ x2 + ... + xn)/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 a1, a2,
..., an 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
a1, a2, ..., an be n elements of
the vector space Fpm. Prove
that there exists a non-empty subset T of {1, 2, ..., n} such that
SUM_{t in T} at = 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 B1, B2, ..., Bn
be n subsets of X such
that |Bi| = 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 Bi
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
x1, x2, ..., xn
satisfying either the equation
x1 = 1/x1 + x2 = 1/x2 + x3 = ... = 1/xn-1 + xn
or the equation
x1 = 1/x1 + x2 = 1/x2 + x3 = ... = 1/xn-1 + xn = 1/xn.
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.
Other works
Darij Grinberg