Lattice

1. In one mathematical usage, a lattice is a discrete subgroup of Rⁿ or Cⁿ. Every lattice can be generated from a basis for the underlying vector space by considering all linear combinations with integral coefficients.

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

See also Minkowski's theorem.

---

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.

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. Distributive lattices are used to formulate pointless topology.

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.

---

3. In materials science 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.

---

4. In digital signal processing, lattice filters[?] are filters with a special recursive structure.