DIMACS TR: 94-03

Independence of Solution Sets and Minimal Asymptotic Bases

Authors: Paul Erdos, Melvyn B. Nathanson and Prasad Tetali


Let $k \geq 2$. The set $A$ of nonnegative integers is a minimal asymptotic basis of order $k$ if every sufficiently large integer can be written as the sum of $k$ elements of $A$, but no proper subset of $A$ has this property. In this paper, combinatorial methods are used to find criteria for an asymptotic basis of order $k$ to contain a minimal asymptotic basis of order $k$, and probabilistic methods are used to prove the existence of asymptotic bases that satisfy these criteria.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-03.ps
DIMACS Home Page