# Bounds on size of self-concatenation of Finite Languages

Given a finite language $L$ with $|L|$ number of elements, what is $|L^i|$ (the language $L$ concatenated with itself $i$ times)? If there is no exact result, is there an upper/lower bound?

Define concatenation of $L$ with itself to be as the classical definition: $LL = \{wx \space | \space w,x \in L\}$. Similarly, $L^n = \{a_1a_2...a_n \space | \space a_i \in L, \forall i \in [1, n] \}$.

Clearly, a non-tight upper bound is $|L|^i$ (each element in concatenation is unique) given that $|L| > 1$, but I would like to know if there is either a tight upper bound or tight lower bound.

• The upper bound $|L|^i$ is obviously tight (it is attained e.g. if all words in $L$ have the same length). On the other hand, $|L^i|$ may be as low as $i(|L|-1)+1$ (e.g., if $L=\{a^j:j=1,\dots,|L|\}$). Oct 1 '14 at 18:51
• Thanks on the first one. For the lower bound, is that attained when all the words have the same length?
– Ryan
Oct 1 '14 at 18:59
• No. The upper bound is attained when all words have the same length. Oct 1 '14 at 19:01
• @EmilJeřábek oh duh, you're right.
– Ryan
Oct 1 '14 at 19:50

You can show $|L|^i$ is a tight upper bound by using the following language:

$L = \{ ab,aab,aaab,\ldots,a^kb \mid k \geq 1 \}.$

Any concatenation gives a new string. For a lower bound, I can suggest the following unary language:

$U = \{a,aa,aaa,\ldots,a^k \mid k \geq 1 \}$.

Then, $U^i = \{ a^i,a^{i+1},\ldots,a^{ki} \}$ and so $|U^i| = i|U|-i+1$.

Emil's (Jerabek) comment appeared during writing my answer and so before posting my answer.

• Seeing as we made independently the same guess, I wonder whether the lower bound is optimal. Oct 1 '14 at 20:11
• It seems to be optimal to me.
– Ryan
Oct 1 '14 at 20:54
• Ah, yes, and more generally, if $L_0$ and $L_1$ are nonempty, then $|L_0L_1|\ge|L_0|+|L_1|-1$. Assume wlog $|L_0|\le|L_1|$, let $a\in L_0$ be of maximal length, and $b\in L_1$ of minimal length. Then $aL_1\cup L_0b\subseteq L_0L_1$ contains $|L_0|+|L_1|-1$ distinct words, unless there is $a\ne a'\in L_0$ of the same length as $a$, in which case $\{a,a'\}L_1$ are $2|L_1|\ge|L_0|+|L_1|$ distinct words. Oct 1 '14 at 21:37

If $L$ is any finite code (that is, if $L^*$ is a free monoid of basis $L$), then $|L^i| = |L|^i$. This is the case in particular if $L$ is a prefix code: no word of $L$ is a proper prefix of another word of $L$.

The lower bound is $i|L| - i$ (a slight improvement over the suggested $i|L| - i + 1$). It is obtained for $L = \{1, a, a^2, \ldots, a^{k-1}\}$.

EDIT. As pointed out by Emil Jeřábek, I miscounted the size of $\{1, a, a^2, \ldots, a^{k-1}\}$ and the lower bound is indeed $i|L| - i + 1$.

• You have miscounted the size of $\{a^j:j=0,\dots,i(k-1)\}$. The tight $i|L|-i+1$ lower bound is proved in my comment to Abuzer Yakaryilmaz’s answer. Oct 5 '14 at 11:25