ON SPARSE LANGUAGES L SUCH THAT LL=SIGMA-ASTERISK

A language L is-an-element-of SIGMA is said to be sparse if L contain s a vanishingly small fraction of all possible strings of length n in SIGMA. C. Ponder asked if there exists a sparse language L such that LL = SIGMA. We answer this question in the affirmative. Several diffe rent constructions are provided, using ideas from probability theory, fractal geometry, and analytic number theory. We obtain languages that are optimally sparse, up to a constant factor. Finally, we consider t he generalization L(j) = SIGMA.