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