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

http://i.stanford.edu/pub/cstr/reports/cs/tr/72/275/CS-TR-72-275.pdf