__
Revision #1 to TR13-161 | 7th May 2014 04:59
__
#### The Frequent Paucity of Trivial Strings

**Abstract:**
A 1976 theorem of Chaitin can be used to show that arbitrarily dense sets of lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. This proof is much simpler than previously published proofs, and it gives a tighter paucity bound.

__
TR13-161 | 23rd October 2013 23:05
__

#### The Frequent Paucity of Trivial Strings

**Abstract:**
A 1976 theorem of Chaitin, strengthening a 1969 theorem of Meyer,says that infinitely many lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. This proof is much simpler than previously published proofs. It also gives a tighter paucity bound, and it shows that the set of lengths n at which there is a paucity of trivial strings is not only infinite, but has positive Schnirelmann density.