# Finite concatenation-free languages

Suppose, $$A$$ is a finite alphabet. $$L \subset A^*$$ is a language. Let's call $$L$$ concatenation-free iff $$\forall u, v \in L$$ we have $$uv \notin L$$.

Does there exist some function $$c: \mathbb{N} \to (0; 1)$$, such that for any finite language $$L \subset A^*$$, there exists a concatenation-free sublanguage $$L_0 \subset L$$, such that $$|L_0| \geq c(|A|)|L|$$?

The only thing I currently know about this problem, is that we can take $$c(1) = \frac{1}{3}$$. That is a direct consequence of Erdos-Sidon theorem, that states:

$$\forall A \subset \mathbb{Z}$$ $$\exists$$ a sum-free $$A_0 \subset A$$, such that $$|A_0| \geq \frac{|A|}{3}$$

However, I do not know how to deal with $$|A| \geq 2$$.

This question on MSE

$$c(n)=1/3$$ works for every $$n$$. Let $$L$$ be a finite language, $$A$$ be the multiset (say, nondecreasing sequence) of lengths of words in $$L$$. Then there exists a sum-free submultiser (subsequence) $$B$$ of $$A$$ of cardinality $$\ge |A|/3$$. Take $$L_0$$ to be the set of all words in $$L$$ whose lengths are in $$B$$. $$L_0$$ is concatenation-free and contains $$\ge |L|/3$$ words.See the paper "Sum-free subsets" by Alon and Kleitman https://documentcloud.adobe.com/link/track?uri=urn%3Aaaid%3Ascds%3AUS%3A038f5fe3-82b8-4e2a-bd71-53e1612d4dc9, Proposition 1.2.
• $A$ should be defined as a multiset (but Erdos–Sidon still works) Mar 12 '20 at 15:07