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](https://math.stackexchange.com/q/3525591/407165)



Finite concatenation-free languages
$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.


