Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.3

Minimal Sets

Martin Kreh
Institute of Mathematics and Applied Computer Science
University of Hildesheim
Samelsonplatz 1
31141 Hildesheim


In this paper I consider the problem of finding minimal sets for some subsets of the natural numbers. This problem was first introduced by Shallit, but since then there has not been much progress.

Here, I consider the set of integers that can be written as a sum of two squares and develop an algorithm that constructs the minimal sets for congruence classes. In fact, this algorithm can be applied to a more general class of sets.

I show that minimal sets do not permit much structure, i.e., set-theoretic relations between two sets will, in general, not be passed on to the respective minimal sets. In addition to this, measure-theoretic tools cannot help in determining the number of elements in minimal sets.

Full version:  pdf,    dvi,    ps,    latex    

Received October 1 2014; revised versions received March 26 2015. Published in Journal of Integer Sequences, May 19 2015.

Return to Journal of Integer Sequences home page