Darij GrinbergKarlsruhe (Germany) / Cambridge, Massachusetts (USA) |
about | new | algebra qedmo | lambda | hopf geo1 | geo2 | solutions | german last update 19 May 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).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.)
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_{0}, a_{1}, ..., a_{n}
are elements of A and v is an element of
B such that SUM_{i=0}^{n} a_{i}v^{i}
= 0, then SUM_{i=0}^{n-k} a_{i+k}v^{i} 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_{0} = A and I_{a}I_{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})_{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_{0}Y^{0} + I_{1}Y^{1}
+ I_{2}Y^{2} + ... 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_{1}. 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_{i}A[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_{i}J_{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_{i}J_{i})_{i≥0}) if and only if the
element uY of
the polynomial ring B[Y] is n-integral over the (A_{[I]},
(J_{i}A_{[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_{i}J_{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_{1}, a_{2}, ..., 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, 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 p^{q} 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 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 (version 5 December 2010).
PDF file (with solution).
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).
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_{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).
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_{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.
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_{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).
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_{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.