Relationship between $|a \cdot b|$ and $|a|$ , $|b|$

Question

Please help me about this problem.

What's the relationship between $|a \cdot b|$ and $|a|$,$|b|$?

For Example:
$$\begin{align}a&=\{11,0,1\} \\ b&=\{0,10\}\\ |a|&=3\\ |b|&=2\\ a\cdot b&=\{110, 1110,00,010,10,110\} = \{110,1110,00,010,10\}\end{align}$$

So: $|a \cdot b| = 5$ but if $b=\{0,110\}$ then $a \cdot b=\{110,11110,00,0110,10,1110\}$ So: $|a \cdot b|=6$

How to make a formula for it?

Answer 1

I assume that the $\cdot$ binary operation is the string concatenation extended to sets.

There are some special cases like $|a| = 0$ or $|a| = 1$ and similarly for $b$, but if $|a| \geq 2$ and $|b| \geq 2$, you can show a bit more: $|a|+|b| \leq |a\cdot b| \leq |a| |b|$. You can easily construct two extreme cases:

• $|a\cdot b| = |a| |b|$ for any $a \subseteq \{ (01|10)^*111 \}$ and $b \subseteq \{ 000(01|10)^* \}$ where $^*$ is the Kleene star,
• $|a|+|b| = |a\cdot b|$ for $a = \{ 0^k | k=1\ldots |a|\}$ and $b = \{ 0^k | k = 1\ldots |b|\}$.

Of course $|a\cdot b| \leq |a \times b| = |a||b|$. To prove that the second one is also an extreme case, let $c = a \cdot b$ and split all those sets by word length, i.e. let $a_k = \{ x \in a |\ \mathrm{length}(x) = k \}$, analogously for $b_k$ and $c_k$. We want to show that $$ \sum_i |a_i| + \sum_j |b_j| \leq \sum_k |c_k| \,. \quad\quad\quad(1)$$

First, consider the case where there is only one $k$ such that $a_k \neq 0$ (i.e. all the words from $a$ are the same length), then $|a\cdot b| = |a_k \cdot b| = |a_k||b| \geq |a|+|b|$ since $|a| \geq 2$ and $|b| \geq 2$. The similar case holds for $b$ if it contains words of the same length.

Now, let us assume (2) that there are words of different length in both $a$ and $b$. It is true that $$ |c_k| = \left|\bigcup_i a_i \cdot b_{k-i}\right| \geq \max_{i} \{ |a_i \cdot b_{k-i}|\}\,. $$ Let us say that $a_i$ participates in $c_k$ if $a_i \cdot b_{k-i}$ is not empty. From the equation above, if $a_i$ participates in $c_k$ then $$|a_i| \leq |c_k| \,, \quad\quad\quad(3)$$ same for $b_j$ (4). Thanks to the assumption (2) for every non-empty $a_i$ there are at least two sets $c_k$ it participates in. Also, there are similar two (or more) sets for every $b_j$, therefore there exists a perfect matching from non-empty $a$-s and $b$-s to non-empty $c$-s. Summing by this matching and applying one of (3),(4) we get (1) and that completes the proof.