7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ $A$ should be defined as a multiset (but Erdos–Sidon still works) $\endgroup$ – Fedor Petrov Mar 12 '20 at 15:07
  • 1
    $\begingroup$ Replaced "set" by "multiset" twice a @FedorPetrov suggested. $\endgroup$ – user6976 Mar 12 '20 at 15:25
  • $\begingroup$ What’s the name of the linked document? I can’t access it. $\endgroup$ – user76284 Mar 12 '20 at 16:21
  • $\begingroup$ It is a paper by Alon and Kleitman "Sum-free subsets". You can google it yourself. $\endgroup$ – user6976 Mar 12 '20 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.