Sets of integers closed under affine operators—the finite basis theorem

Dean G. Hoffman and David Anthony Klarner

Vol. 83 (1979), No. 1, 135–144

DOI: 10.2140/pjm.1979.83.135

Abstract

This paper is a continuation of investigations of sets T of integers closed under operations f of the form f(x₁,⋯,x_r) = m₁x₁ + ⋯ + m_rx_r + c, where r, m₁,⋯,m_r, c are integers satisfying r ≧ 2, 0∉{m₁,⋯,m_r}, and gcd(m₁,⋯,m_r) = 1. We have two goals here:

1. to prove that T = ⟨f∣A⟩ for some finite set A, where ⟨f∣A⟩ denotes the “smallest” set containing A and closed under f, and
2. to show that unless |T| = 1, T is a finite union of infinite arithmetic progressions, either all bounded below, or all bounded above, or all doubly infinite.

Mathematical Subject Classification

Primary: 10L05, 10L05

Secondary: 10A35

Milestones

Received: 12 October 1977

Revised: 1 November 1978

Published: 1 July 1979