# Darij Grinberg

Assistant Professor
Drexel University

/ Karlsruhe (Germany)

• AB@gmail.com (main)
• AB@protonmail.com (backup)
• A.B@drexel.edu (teaching)
where A = darij and B = grinberg .

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

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

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

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

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 p2;
• 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 p2;
• the sum of (n + m choose m)2 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)2 over all n = 0, 1, ..., r-1 and all m = 0, 1, ..., s-1) modulo p2,
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 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 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 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 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 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.

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