Lattice

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

A structure made of laths, or of wood or metal crossed and fastened together, with open spaces left between; used as a screen, e.g. in window openings and the like; a window, gate, screen, etc. so constructed.

Both of the mathematical usages treated below began as metaphors based on this concept defined in the dictionary. In the first case, geometric pictures of the simplest lattices look like lattices in the sense defined by the dictionary; in the second case, the Hasse diagrams of the posets look (in some simple cases) like the aforementioned lattices.

---

1. In mathematics, a lattice in Rⁿ is a discrete subgroup of Rⁿ which spans the real vector space Rⁿ. Every lattice in Rⁿ can be generated from a basis for the vector space by considering all linear combinations with integral coefficients.

Equivalently, a lattice in Rⁿ is an n-dimensional additive free group over Z which generates Rⁿ over R.

A simple example of a lattice in Rⁿ is the subgroup Zⁿ. A more complicated example is the Leech lattice, which is a lattice in R²⁴.

Similarly, a lattice in Cⁿ is a discrete subgroup of Cⁿ which spans the 2n-dimensional real vector space Cⁿ. 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).

---

2. In another mathematical usage, a lattice is a partially ordered set in which all nonempty finite subsets have a least upper bound and a greatest lower bound (also called supremum and infimum, respectively). The term "lattice" comes from the shape of the Hasse diagrams of such orders (see partially ordered set).

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

f(a ^ b) = f(a) ^ f(b)

f(a v b) = f(a) v f(b)

for all a, b in L. A bijective homomorphism whose inverse is also a homomorphism is called an isomorphism of lattices, and the two involved lattices are called isomorphic.

Table of contents

1 Properties of lattices 2 Important lattice-theoretic notions 3 Literature

Properties of lattices

A lattice is said to be bounded if it has a greatest element and a least element. The greatest element is often denoted by 1 and the least element by 0. If x is an element of a bounded lattice then any element y of the lattice satisfying x ^ y = 0 and x v y = 1 is called a complement of x. A bounded lattice in which every element has a (not necessarily unique) complement is called a complemented lattice.

A lattice in which every subset (including infinite ones) has a supremum and an infimum is called a complete lattice. Complete lattices are always bounded. Many of the most important lattices are complete. Examples include:

• The subsets of a given set, ordered by inclusion. The supremum is given by the union and the infimum by the intersection of subsets.
• The unit interval [0,1] and the extended real number line, with the familiar total order and the ordinary suprema and infima.
• The non-negative integers, ordered by divisibility. The supremum is given by the least common multiple and the infimum by the greatest common divisor.
• The subgroups of a group, ordered by inclusion. The supremum is given by the subgroup generated by the union of the groups and the infimum is given by the intersection.
• The submodules of a module, ordered by inclusion. The supremum is given by the sum of submodules and the infimum by the intersection.
• The ideals of a ring, ordered by inclusion. The supremum is given by the sum of submodules and the infimum by the intersection.
• The open sets of a topological space, ordered by inclusion. The supremum is given by the union of open sets and the infimum by the interior of the intersection.
• The convex subsets of a real or complex vector space, ordered by inclusion. The infimum is given by the intersection of convex sets and the supremum by the convex hull of the union.
• The topologies on a set, ordered by inclusion. The infimum is given by the intersection of topologies, and the supremum by the topology generated by the union of topologies.
• The lattice of all transitive binary relations on a set.
• The lattice of all sub-multisets of a multiset.
• The lattice of all partitions of a set.

The Knaster-Tarski theorem states that the set of fixed points of a monotone function on a complete lattice is again a complete lattice.

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.

Important lattice-theoretic notions

In the following, let L be a lattice.

A subset F of L is called a filter iff

• F is an upper set, i.e. a in F, b in L and a ≤ b imply b in F,
• F is closed under finite meets, i.e. a in F and b in F imply a ^ b in F.

A filter is proper iff it does not contain all elements of L.

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

• x = a v b implies x = a or x = b for any a, b in L,
• if L has a 0, x is sometimes required to be different from 0.

When the first condition is generalized to arbitrary joins Va_i, x is called completely join-irreducible. The dual notion is called meet-irreducability. Sometimes one also uses the terms v-irreducible and ^-irreducible, respectively.

An element x of L is called join-prime iff

• x<=a v b implies x ≤ a or x ≤ b.

Again, this can be generalized to obtain the notion completely join-prime and dualized to yield meet-prime. Any meet-prime element is also meet-irreducible. If the lattice is distributive the converse is also true.

Literature

• B. A. Davey, H. A. Priestley: Introduction to Lattices and Order. Cambridge University Press, 2002. (ISBN 0521784514)