Low complexity functions and convex sets in mathbbZkmathbb{Z}^k

In 1938 Morse and Hedlund proved that a function is periodic if the number of different n-blocks with does not exceed n for some n. In 1940 they studied such functions f with for all positive integers n. These are closely related to Sturmian sequences, which occur in many branches of mathematics, computer science and physics. Recently the authors studied k-dimensional functions with , where is the set of different vectors with for a given configuration . In this paper, we characterize functions satisfying for all configurations . Our proof requires a separation theorem for convex sets of lattice points, which may be of independent interest. Received July 20, 1998