# Darij Grinberg

Karlsruhe (Germany) / Cambridge, Massachusetts (USA)

A=gmail.com
where the letter A should be replaced by darijgrinberg
and the sign = by the sign @.
(Apologies for this obstruction; I am trying to protect my mailbox against spammers
automatically searching for everything that looks like an email address.)

qedmo | lambda | hopf
geo1 | geo2 | solutions | german

last update 18 Apr 2016

This is a website for mathematics, from elementary to advanced. Formerly, it used to be entirely dedicated to the Geometry of the Triangle; this has now been moved to two subpages: Geometry Publications and Geometry Unpublished Notes. I am currently working on combinatorial algebra and representation theory, so do not expect any more geometry to appear here, but new notes on algebra will surface from time to time.

About me and this website (this includes a FAQ and instructions on opening the files on this site).

## Writings

Some advanced algebra (work in progress), Lambda-rings and Hopfalgebren (lecture notes after Prof. Hans-Jürgen Schneider, in German)

German papers 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

A few texts I have written for diverse purposes, arranged according to potential usefulness (i. e., the first in the list are probably the most useful).

English

• Darij Grinberg, A few facts on integrality (version 30 November 2010).
PDF file.
Detailed version with all the proofs much more formalized. Old version (version 20 August 2009) with slightly weaker Theorem 1. Sourcecode of all the files.

This is a five-part note about commutative algebra. Rings mean commutative rings with unity.

Part 1 (Integrality over rings) is an (over-formalized) writeup of proofs to some known and less known results about integrality over rings. If A is a subring of a ring B, and n is an integer, then an element u of B is said to be n-integral over A if there exists a monic polynomial P of degree n with coefficients in A such that P(u) = 0. We show that:
- (Theorem 1) An element u of B is n-integral over A if and only if there exists an n-generated (= generated by n elements) A-submodule U of B such that uU is a subset of U and such that v = 0 for every v in B satisfying vU = 0.
- (Theorem 1 as well) An element u of B is n-integral over A if and only if there exists an n-generated (= generated by n elements) A-submodule U of B such that 1 lies in U and uU is a subset of U.
- (Theorem 1 in the old version) An element u of B is n-integral over A if and only if there exists a faithful n-generated (= generated by n elements) A-submodule U of some B-module such that uU is a subset of U.
- (Theorem 2) If a0, a1, ..., an are elements of A and v is an element of B such that SUM_{i=0}^{n} aivi = 0, then SUM_{i=0}^{n-k} ai+kvi is n-integral over A for every 0 ≤ k ≤ n. (This result, and its Corollary 3, generalize exercise 2-5 in J. S. Milne's Algebraic Number Theory.)
- (Theorem 4) If some element v of B is m-integral over A, and some element u of B is n-integral over A[v], then u is nm-integral over A. (This is a known fact. I derive it from Theorem 1, just as most people do. Maybe I will also write up a different proof using resultants.)
- (Theorem 5) Any element of A is 1-integral over A. If some element x of B is m-integral over A, and some element y of B is n-integral over A, then x+y and xy are nm-integral over A. (This is known again. I use Theorem 4 to prove this.)
- (Corollary 6) Let v be an element of B, and n and m two positive integers. Let P be a polynomial of degree n-1 with coefficients in A, and let u = P(v). If vu is m-integral over A, then u is nm-integral over A. (This follows from Theorems 2 and 5 but may turn out useful, though I don't expect much.)

Part 2 (Integrality over ideal semifiltrations) gives a common generalization to integrality over rings (as considered in Part 1) and integrality over ideals (a less known, but still important notion).
We define an ideal semifiltration of a ring A as a sequence (Ii)i≥0. of ideals of A such that I0 = A and IaIb is a subset of Ia+b for any a ≥ 0 and b ≥ 0. (This notion is weaker than that of an ideal filtration, since we do not require that In+1 is a subset of In for every n ≥ 0.)
If A is a subring of a ring B, if (Ii)i≥0 is an ideal semifiltration of A, and if n is an integer, then an element u of B is said to be n-integral over (A,(Ii)i≥0) if there exists a monic polynomial P of degree n with coefficients in A such that P(u) = 0 and the i-th coefficient of P lies in Ideg P - i for every i in {0, 1, ..., deg P}.
While this notion is much more general than integrality over rings (which is its particular case when (Ii)i≥0 = (A)i≥0) and integrality over ideals (which is its particular case when B = A and (Ii)i≥0 = (Ii)i≥0 for some fixed ideal I), it still can be reduced to basic integrality over rings by a base change. Namely:
- (Theorem 7) The element u of B is n-integral over (A,(Ii)i≥0) if and only if the element uY of the polynomial ring B[Y] is n-integral over the Rees algebra A[(Ii)i≥0*Y]. (This Rees algebra A[(Ii)i≥0*Y] is defined as the subring I0Y0 + I1Y1 + I2Y2 + ... of the polynomial ring A[Y]. Not that I would particularly like the notation A[(Ii)≥0*Y], but I have not seen a better one.)
(The idea underlying this theorem is not new, but I haven't seen it stated in standard texts on integrality.)
Using this reduction, we can generalize Theorems 4 and 5:
- (Theorem 8, generalizing Theorem 5) An element of A is 1-integral over (A,(Ii)i≥0) if and only if it lies in I1. If some element x of B is m-integral over (A,(Ii)i≥0), and some element y of B is n-integral over (A,(Ii)i≥0), then x+y is nm-integral over (A,(Ii)i≥0). If some element x of B is m-integral over (A,(Ii)i≥0), and some element y of B is n-integral over A (not necessarily over (A,(Ii)i≥0) !), then xy is nm-integral over (A,(Ii)i≥0).
- (Theorem 9, generalizing Theorem 4) If some element v of B is m-integral over A, and some element u of B is n-integral over (A[v], (IiA[v])i≥0), then u is nm-integral over (A,(Ii)i≥0).
Note that Theorem 9 doesn't seem to yield Theorem 8 as easily as Theorem 5 could be derived from Theorem 4 !

Part 3 (Generalizing to two ideal semifiltrations) continues Part 2, generalizing a part of it even further:
Let A be a subring of a ring B. Let (Ii)i≥0 and (Ji)i≥0 be two ideal semifiltrations of A. Then, (IiJi)i≥0 is an ideal semifiltration of A, as well. Now, we can give a "relative" version of Theorem 7:
- (Theorem 11) An element u of B is n-integral over (A,(IiJi)i≥0) if and only if the element uY of the polynomial ring B[Y] is n-integral over the (A[I], (JiA[I])i≥0), where A[I] is a shorthand for the Rees algebra A[(Ii)i≥0*Y].
Using this, we can generalize the xy part of Theorem 8 even further:
- (Theorem 13) If some element x of B is m-integral over (A,(Ii)i≥0), and some element y of B is n-integral over (A,(Ji)i≥0), then xy is nm-integral over (A,(IiJi)i≥0).

Part 4 (Accelerating ideal semifiltrations) extends Theorem 7:
- (Theorem 16, a generalization of Theorem 7) Let s ≥ 0 be an integer. An element u of B is n-integral over (A,(Isi)i≥0) if and only if the element uYs of the polynomial ring B[Y] is n-integral over the Rees algebra A[(Ii)i≥0*Y].
Actually, this can be further generalized in the vein of Theorem 11 (to Theorem 15).
As a consequence, Theorem 2 is generalized as well.

Part 5 (Generalizing a lemma by Lombardi) is mostly about the following fact:
- (Theorem 22) Let x, y and u be three elements of B. If u is integral over A[x] and over A[y], then u is also integral over A[xy].
This generalizes Theorem 2 from Lombardi's Hidden Constructions (1). We also show a relative version (Theorem 23) and reprove Corollary 3.

• Darij Grinberg, Zeckendorf family identities generalized (version 18 March 2010).
PDF file.
Also avaliable at http://arxiv.org/abs/1103.4507.
Sourcecode.
There is also a detailed (and twice as long) version. It should best only be consulted if something is unclear about the brief version above.

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 "holey" set of integers ("holey" means that no two elements of this set are consecutive integers).
This holey 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 holey set S of integers such that every n high enough 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, Notes on the combinatorial fundamentals of algebra (PRIMES 2015 reading project: problems and solutions) (work in progress).
PDF file.
Sourcecode.
A version without solutions, for spoilerless searching.

A set of notes on binomial coefficients, permutations and determinants written for a PRIMES reading project 2015. 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, Fleck's binomial congruence using circulant matrices (version 10 April 2016).
PDF file.
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.

In this note, I give 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 (version 14 April 2016).
PDF file.
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.

• Darij Grinberg, A hyperfactorial divisibility (version 27 July 2015).
PDF file.
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 Vornicu-Schur inequality and its variations (version 13 August 2007).
PDF file.
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).
PDF file.
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 (version 5 December 2010).
PDF file (with solution).
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).
PDF version. 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).
PDF file.

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.

I am working on an update of this note focussing more on the finite differences lemma and less on Problems 1 and 2 (not like I want to remove these problems, but I want to add more about finite differences and a few other applications).

• Darij Grinberg, An algebraic approach to Hall's matching theorem (version 6 October 2007).
PDF file.
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).
PDF file; 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.

Deutsch
• Darij Grinberg, Fulton-Harris Proposition 15.15 (Version 29. Januar 2011).
PDF-Datei; siehe auch TeX-Quellcode.

Ein Beweis, daß die Darstellung von GL(V), die man durch Schur-Weyl-Dualität aus der irreduziblen Darstellung cλℂ[Sm] von Sm erhält, als Darstellung der Liealgebra sl(V) das höchste Gewicht λ1L1 + λ2L2 + ... + λnLn hat (wenn die Cartan-Unteralgebra und die Weylkammer "richtig" gewählt wird). Dies ist Proposition 15.15 in Fulton-Harris, wo ein nicht ganz richtiger Beweis gegeben wird. Der Beweis hier versucht, diesen Fehler zu vermeiden.