Report Number: CS-TR-72-275
Institution: Stanford University, Department of Computer Science
Title: Sets generated by iteration of a linear operation.
Author: Klarner, David A.
Date: March 1972
Abstract: This note is a continuation of the paper "Arithmetic properties of certain recursively defined sets," written in collaboration with Richard Rado. Here the sets under consideration are those having the form S = <\$m_1 x_1 + \ldots\ + m_r x_r : 1\$> where \$m_1,\ldots ,m_r\$ are given natural numbers with greatest common divisor 1. The set S is the smallest set of natural numbers which contains 1 and is closed under the operation \$m_1 x_1 + \ldots\ + m_r x_r\$. Also, S can be constructed by iterating the operation \$m_1 x_1 + \ldots\ + m_r X_r\$ over the set {1}. For example, <2x + 3y: 1> = {1, 5, 13, 17, 25, \$\ldots\ } = (1 + 12N) \$\cup\$ (5 + 12N) where N = {0,1,2,\$\ldots\$}. It is shown in this note that S contains an infinite arithmetic progression for all natural numbers r-1,\$m_1,\ldots ,m_r\$. Furthermore, if (\$m_1,\ldots ,m_r\$) = (\$m_1\ldots m_r,m_1 + \ldots\ + m_r\$) = 1, then S is a per-set; that is, S is a finite union of infinite arithmetic progressions. In particular, this implies is a per-set for all pairs {m,n} of relatively prime natural numbers. It is an open question whether S is a per-set when (\$m_1,\ldots ,m_r\$) = 1, but (\$m_1\ldots m_r,m_1 + \ldots\ + m_r\$) > 1.
http://i.stanford.edu/pub/cstr/reports/cs/tr/72/275/CS-TR-72-275.pdf