Report Number: CS-TR-72-269
Institution: Stanford University, Department of Computer Science
Title: Arithmetic properties of certain recursively defined sets.
Author: Klarner, David A.
Abstract: Let R denote a set of linear operations defined on the set P of positive integers; for example, a typical element of R has the form $\rho (x_1, \ldots ,x_r) = m_0 + m_1 x_1 + \ldots + m_r x_r where m_0, \ldots ,m_r$ denote certain integers. Given a set A of positive integers, there is a smallest set of positive integers denoted which contains A as a subset and is closed under every operation in R. The set can be constructed recursively as follows: Let $A_0$ = A, and define $A_{k+1} = A_k \cup \{\rho (\bar{a}): \rho \in R,\bar{a}\in A_k \times \ldots \times A_k\}$ (k = 0,1,\ldots ), then it can be shown that = $A_0 \cup A_1 \cup \ldots$. The sets sometimes have an elegant form, for example, the set <2x + 3y: 1> consists of all positive numbers congruent to 1 or 5 modulo 12. The objective is to give an arithmetic characterization of elements of a set , and this paper is a report on progress made on this problem last year. Many of the questions left open here have since been resolved by one of us (Klarner).