Are strings of length $n^2$ sparse? Let L be the language of strings of length $m$, where $m$ is a perfect square. (So strings of length $1, 4, 9, 16, 25, \dots$ are accepted, other lengths are not.)
As $m$ increases, less and less strings are accepted.
Is this language sparse?

a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length $n$ in the language, is bounded by a polynomial function of $n$.


A symbol is $1$ or $0$.
A string is a finite sequence of symbols. For example $7$ in binary = $111$. (Unlike binary integers, strings can be padded with $0$'s and be distinct; $0111 \neq 111$.)
A language is a set of strings.
A language is sparse if only a polynomial number of its $2^m$ strings are accepted, (where $m$ is the length of the string).

It's not sparse:
Every time we encounter a perfect square m=k^2 we add 2^m strings to the language.
Even though we're adding less strings as n increases (perfect squares occur less and less), every time we add strings, we're adding exponential (2^m) strings.
So overall we're still adding exponential strings.
