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).
 A: Call this language $L$. We want to find the complexity function $p_L\colon \mathbb N \to \mathbb N$ of this language, which maps string lengths ($n$) to the number of strings in $L$ that have that string length. It shouldn't be hard to see that:
$$
p_L(n) = \begin{cases}
2^n &\text{if $n = k^2$ for some $k \in \mathbb N$} \\
0 &\text{otherwise}
\end{cases}
$$
Since this function is not bounded above by a polynomial in $n$, we conclude that $L$ is not sparse.
A: No, this language would not be sparse. By definition, for every m that is a perfect square, all $2^m$ strings of length m are accepted. For any polynomial $p(n)$, choosing a sufficiently large square $m$ such that $2^m > p(m)$ shows that the complexity function is not polynomially bounded. 
A: 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.
