Darij Grinberg

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.

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 a₀, a₁, ..., a_n are elements of A and v is an element of B such that SUM_{i=0}^{n} a_ivⁱ = 0, then SUM_{i=0}^{n-k} a_i+kvⁱ 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 (I_i)_i≥0. of ideals of A such that I₀ = A and I_aI_b is a subset of I_a+b for any a ≥ 0 and b ≥ 0. (This notion is weaker than that of an ideal filtration, since we do not require that I_n+1 is a subset of I_n for every n ≥ 0.)
  If A is a subring of a ring B, if (I_i)_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,(I_i)_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 I_{deg 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 (I_i)_i≥0 = (A)_i≥0) and integrality over ideals (which is its particular case when B = A and (I_i)_i≥0 = (Iⁱ)_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,(I_i)_i≥0) if and only if the element uY of the polynomial ring B[Y] is n-integral over the Rees algebra A[(I_i)_i≥0*Y]. (This Rees algebra A[(I_i)_i≥0*Y] is defined as the subring I₀Y⁰ + I₁Y¹ + I₂Y² + ... of the polynomial ring A[Y]. Not that I would particularly like the notation A[(I_i)_≥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,(I_i)_i≥0) if and only if it lies in I₁. If some element x of B is m-integral over (A,(I_i)_i≥0), and some element y of B is n-integral over (A,(I_i)_i≥0), then x+y is nm-integral over (A,(I_i)_i≥0). If some element x of B is m-integral over (A,(I_i)_i≥0), and some element y of B is n-integral over A (not necessarily over (A,(I_i)_i≥0) !), then xy is nm-integral over (A,(I_i)_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], (I_iA[v])_i≥0), then u is nm-integral over (A,(I_i)_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 (I_i)_i≥0 and (J_i)_i≥0 be two ideal semifiltrations of A. Then, (I_iJ_i)_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,(I_iJ_i)_i≥0) if and only if the element uY of the polynomial ring B[Y] is n-integral over the (A_[I], (J_iA_[I])_i≥0), where A_[I] is a shorthand for the Rees algebra A[(I_i)_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,(I_i)_i≥0), and some element y of B is n-integral over (A,(J_i)_i≥0), then xy is nm-integral over (A,(I_iJ_i)_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,(I_si)_i≥0) if and only if the element uY^s of the polynomial ring B[Y] is n-integral over the Rees algebra A[(I_i)_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 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 "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 (a₁, a₂, ..., a_p) of integers, there exists one and only one finite holey set S of integers such that every n high enough 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, 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).
  

• 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 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 (version 5 December 2010).
  PDF file (with solution).
  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).
  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(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).
  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 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.
  
  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, Proof of a CWMO problem generalized (version 7 September 2009).
  PDF file.
  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).
  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 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.

• 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_λℂ[S_m] von S_m erhält, als Darstellung der Liealgebra sl(V) das höchste Gewicht λ₁L₁ + λ₂L₂ + ... + λ_nL_n 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.