This article is not about lattice filters in digital signal processing, which are electronic filters with a special recursive structure.
The Oxford English Dictionary says that a lattice is
1. In mathematics, a lattice in R^{n} is a discrete subgroup of R^{n} which spans the real vector space R^{n}. Every lattice in R^{n} can be generated from a basis for the vector space by considering all linear combinations with integral coefficients.
Equivalently, a lattice in R^{n} is an n-dimensional additive free group over Z which generates R^{n} over R.
A simple example of a lattice in R^{n} is the subgroup Z^{n}. A more complicated example is the Leech lattice, which is a lattice in R^{24}.
Similarly, a lattice in C^{n} is a discrete subgroup of C^{n} which spans the 2n-dimensional real vector space C^{n}. For example, the Gaussian integers form a lattice in C.
This concept is used in materials science, in which a lattice is a 3-dimensional array of regularly spaced points coinciding with the atom or molecule positions in a crystal. This is a special case of the first meaning given above.
It also occurs in computational physics, in which a lattice is an n-dimensional geometrical structure of sites, connected by bonds, which represent positions which may be occupied by atoms, molecules, electrons, spins, etc. For an article dealing with the formal representation of such structures see Lattice Geometries.
See also Minkowski's theorem.
More generally, a lattice Γ in a Lie group G is a discrete subgroup, such that G/Γ is of finite measure, for the measure on it inherited from Haar measure on G (left-invariant, or right-invariant - the definition is independent of that choice).
A lattice can also be algebraically defined as a set L, together with two binary operations ^ and v (pronounced meet and join, respectively), such that for any a, b, c in L,
a v a = a | a ^ a = a | idempotency laws |
a v b = b v a | a ^ b = b ^ a | commutativity laws |
a v (b v c) = (a v b) v c | a ^ (b ^ c) = (a ^ b) ^ c | associativity laws |
a v (a ^ b) = a | a ^ (a v b) = a | absorption laws |
If the two operations satisfy these algebraic rules then they define a partial order <= on L by the following rule: a <= b if and only if a v b = b, or, equivalently, a ^ b = a. L, together with the partial order <= so defined, will then be a lattice in the above order-theoretic sense.
Conversely, if an order-theoretic lattice (L, <=) is given, and we write a v b for the least upper bound of {a, b} and a ^ b for the greatest lower bound of {a, b}, then (L, v, ^) satisfies all the axioms of an algebraically defined lattice.
The class of all lattices forms a category if we define a homomorphism between two lattices (L, ^, v) and (N, ^, v) to be a function f : L -> N such that
Table of contents |
2 Important lattice-theoretic notions 3 Literature |
The lattice of submodules of a module and the lattice of normal subgroups of a group have the special property that x v (y ^ (x v z)) = (x v y) ^ (x v z) for all x, y and z in the lattice. A lattice with this property is called a modular lattice. The condition of modularity can also be stated as follows: If x <= z then then for all y we have the identity x v (y ^ z) = (x v y) ^ z.
A lattice is called distributive if v distributes over ^, that is, x v (y ^ z) = (x v y) ^ (x v z). Equivalently, ^ distributes over v. All distributive lattices are modular. Two important types of distributive lattices are totally ordered sets and Boolean algebras (like the lattice of all subsets of a given set). The lattice of natural numbers, ordered by divisibility, is also distributive. A lattice is said to be completely distributive if the above distributivity law hold for arbitrary (infinite) meets and joins. Distributive lattices are used to formulate pointless topology.
In the following, let L be a lattice.
A subset F of L is called a filter iff
A principal filter is a set of the form {x ≥ a | x in L} for some a in L. Such sets are always filters in the above sense.
A prime filter is a filter F with the additional property that for all elements a and b in L, if avb in F then either a in F or b in F. A filter where this generalizes to arbitrary (infinite) joins Va_{i} is called completely prime.
A maximal filter is a proper filter F such that there is no proper filter that contains F. These sets are sometimes called ultrafilters. In a Boolean algebra, the principal filters are exactly the ultrafilters.
The notions ideal, proper ideal, principal ideal, and prime ideal, etc. are obtained by exchanging "≤" and "≥", "^" and "v", and "meet" and "join" in the above definitions. Thus, ideals are the dual notion of filters. However, there is no "ultra-ideal".
An element x of L is called join-irreducible iff
An element x of L is called join-prime iff