On sparse languages \(L\) such that \(LL= \Sigma^*\) (Q1331892)

A language \(L \in \Sigma^*\) is called a sparse language if \(L\) contains a small part of all the possible strings of length \(n\) (more precisely, \(\lim_{n \to \infty} | L cap \Sigma^{\leq n}| /| \Sigma^{\leq n}| = 0\), where \(\Sigma^{\leq n}\) is the set of all the strings over \(\Sigma\) having the length at most \(n\)). The paper provides different constructions (using ideas from probability theory, fractal geometry and analytic number theory) for getting languages \(L\) over \(\Sigma\) such that \(L\) is a sparse language and \(LL = \Sigma^*\) -- an open problem due to C. Ponder. Finally a generalization of this problem, \(L\) is sparse and \(L^ j = \Sigma^*\) is also developed.