Are strings of length $n^2$ sparse?

Question

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).

Answer 1

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.

Answer 2

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.

Answer 3

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.