Notes and papers on algebra and algebraic combinatorics
Darij Grinberg, Notes on the combinatorial
fundamentals of algebra.
PDF file.
Sourcecode and Github repository.
A version without solutions,
for spoilerless searching.
A set of notes on binomial coefficients, permutations and
determinants (originally written for a
PRIMES
reading project 2015, but massively extended since).
It covers some binomial coefficient identities
(such as Vandermonde convolution),
lengths and signs of permutations,
and various elementary properties
of determinants (defined by the Leibniz formula).
Darij Grinberg, Notes on
linear algebra (unfinished draft, currently frozen).
PDF file.
Github repository.
An attempt at a rigorous introduction to linear algebra, currently
frozen (as it has proven to be more work than I have time for). It
currently covers matrix operations (multiplications etc.), various
properties of matrices (triangularity, invertibility, permutation) and
some basics of vector spaces. It was written to accompany
my Math 4242 class
at the University of Minnesota.
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 a 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.
Algebra notes
Darij Grinberg