Integrality

Integrality is a term used in several branches of mathematics to denote a property of elements relative to an underlying ring or of optimization problems relative to a feasible region. In commutative algebra, an element x in a ring A containing a subring R is integral over R if it satisfies a monic polynomial with coefficients in R. Equivalently, R[x] is a finitely generated R-module. An extension A over R is called integral if every element of A is integral over R. The integral closure of R in A consists of all elements of A that are integral over R, and a domain that equals its own integral closure is called integrally closed.

In number theory, integrality leads to the notion of algebraic integers: elements that are integral over Z. The set of algebraic integers within a number field K forms the ring of integers O_K, which is the integral closure of Z in K. A familiar example is sqrt(2), which is a root of the monic polynomial x^2 − 2 with integer coefficients, hence integral over Z.

In optimization, integrality refers to the requirement that decision variables take integer values. In integer programming, these are enforced constraints; in many cases, however, the linear programming relaxation already yields integer optimal solutions. This occurs when the constraint matrix is totally unimodular and the right-hand side is integral, in which case solving the LP relaxation produces a valid integer solution without explicit integrality constraints. The integrality gap measures how far the best integer solution is from the optimum of the relaxed problem.

These notions connect algebraic structure with algorithmic implications, illustrating how integrality influences solvability and arithmetic properties across fields.