  We develop foundational tools for classifying the extreme valid functions for
the k-dimensional infinite group problem. In particular, (1) we present the
general regular solution to Cauchy's additive functional equation on bounded
convex domains. This provides a k-dimensional generalization of the so-called
interval lemma, allowing us to deduce affine properties of the function from
certain additivity relations. (2) We study the discrete geometry of additivity
domains of piecewise linear functions, providing a framework for finite tests
of minimality and extremality. (3) We give a theory of non-extremality
certificates in the form of perturbation functions.
  We apply these tools in the context of minimal valid functions for the
two-dimensional infinite group problem that are piecewise linear on a standard
triangulation of the plane, under the assumption of a regularity condition
called diagonal constrainedness. We show that the extremality of a minimal
valid function is equivalent to the extremality of its restriction to a certain
finite two-dimensional group problem. This gives an algorithm for testing the
extremality of a given minimal valid function.
