A language L∈Σ* is said to be sparse if L contains a vanishingly small fraction of all possible strings of length n in Σ*. C. Ponder asked if there exists a sparse language L such that LL=Σ*. The authors answer this question in the affirmative. Several different constructions are provided, using ideas from probability theory, fractal geometry, and analytic number theory. The authors obtain languages that are optimally sparse, up to a constant factor. Finally, they consider the generalization Lj=Σ*.
