The complexity of functions on lattices

✍ Scribed by J.W. Sander; R. Tijdeman

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 212 KB
• Volume: 246
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00078-x

✦ Synopsis

Let f : Z → {0; 1} be a given function. In 1938, Morse and Hedlund observed that if the number of distinct vectors (f(x + 1); : : : ; f(x + n)), x ∈ Z, called complexity, is at most n for some positive integer n, then f is periodic with period at most n. This result is best possible. Functions with low complexity have been studied to a large extent, and relations with or applications to many branches of mathematics, computer science and physics are known. In the present paper we discuss the above phenomenon in greater generality. To begin with, we observe that f is periodic if the number of distinct vectors (f(x + a 1); : : : ; f(x + an)), x ∈ Z, is at most n for some n and given integers a1 ¡ • • • ¡ an, but that the period cannot be bounded as a function of n only. Our main topic are multi-dimensional functions f : Z k → {0; 1} with the property that for some n and distinct vectors a1; : : : ; an ∈ Z k , the number of distinct vectors (f(x + a1); : : : ; f(x + an)), x ∈ Z k , is bounded by n. We show that such a function with arbitrary k is periodic if n63. For n = 4, there are non-periodic examples which we determine completely. Finally limitations to the general periodicity principle are discussed. A conjecture for convex bodies {a1; : : : ; an} in Z 2 is made, and we prove it for n64.