17
$\begingroup$

A word $w$ is called primitive, if there is no word $v$ and $k > 1$ so that $w = v^k$. The set $Q$ of all primitive words over an alphabet $\Sigma$ is a well known language. WLOG we can choose $\Sigma = \{ a,b \}$.

A language $L$ is prime, if for every language $A$ and $B$ with $L = A \cdot B$ we have $A = \{\epsilon\}$ or $B = \{ \epsilon \}$.

Is Q prime?

With the help of a SAT solver I could show that we either have $\{a,b\} \subseteq A$ or $\{a,b\} \subseteq B$ as otherwise $\{ ababa, babab \} \subset Q$ cannot be factorized into $A$ and $B$, but have been stuck since then.

$\endgroup$
13
$\begingroup$

The answer is yes. Suppose we have a factorization $Q = A\cdot B$.

One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of $A,B$ can contain $\epsilon$. We can assume wlog (since the other case is completely symmetric) that $\epsilon\in B$. Then since $a$ and $b$ cannot be factored into non-empty factors, we must have $a,b\in A$.

Next we get that $a^mb^n\in A$ (and, completely analogously, $b^ma^n\in A$) for all $m,n>0$ by induction on $m$:

For $m=1$, since $ab^n\in Q$, we must have $ab^n = uv$ with $u\in A, v\in B$. Since $u\neq\epsilon$, $v$ must be $b^k$ for some $k\le n$. But if $k>0$, then since $b\in A$ we get $b^{1+k}\in Q$, contradiction. So $v=\epsilon$, and $ab^n\in A$.

For the inductive step, since $a^{m+1}b^n\in Q$ we have $a^{m+1}b^n = uv$ with $u\in A, v\in B$. Since again $u\neq\epsilon$, we have either $v = a^kb^n$ for some $0<k<m+1$, or $v=b^k$ for some $k<n$. But in the former case, $v$ is already in $A$ by the induction hypothesis, so $v^2\in Q$, contradiction. In the latter case, we must have $k=0$ (i.e. $v=\epsilon$) since from $b\in A$ we get $b^{1+k}\in Q$. So $u=a^{m+1}b^n\in A$.

Now consider the general case of primitive words with $r$ alternations between $a$ and $b$, i.e. $w$ is either $a^{m_1}b^{n_1}\ldots a^{m_s}b^{n_s}$, $b^{m_1}a^{n_1}\ldots b^{m_s}a^{n_s}$ (for $r=2s-1$), $a^{m_1}b^{n_1}\ldots a^{m_{s+1}}$, or $b^{m_1}a^{n_1}\ldots b^{m_{s+1}}$ (for $r=2s$); we can show that they are all in $A$ using induction on $r$. What we did so far covered the base cases $r=0$ and $r=1$.

For $r>1$, we use another induction on $m_1$, which works very much the same way as the one for $r=1$ above:

If $m_1=1$, then $w=uv$ with $u\in A, v\in B$, and since $u\neq\epsilon$, $v$ has fewer than $r$ alternations. So $v$ (or its root in case $v$ itself is not primitive) is in $A$ by the induction hypothesis on $r$ for a contradiction as above unless $v=\epsilon$. So $w=u\in A$.

If $m_1>1$, in any factorization $w=uv$ with $u\neq\epsilon$, $v$ either has fewer alternations (and its root is in $A$ unless $v=\epsilon$ by the induction hypothesis on $r$), or a shorter first block (and its root is in A unless $v=\epsilon$ by the induction hypothesis on $m_1$). In either case we get that we must have $v=\epsilon$, i.e. $w=u\in A$.


The case of $Q' := Q\cup\{\epsilon\}$ is rather more complicated. The obvious things to note are that in any decomposition $Q = A\cdot B$, both $A$ and $B$ must be subsets of $Q'$ with $A\cap B = \{\epsilon\}$. Also, $a,b$ must be contained in $A\cup B$.

With a bit of extra work, one can show that $a$ and $b$ must be in the same subset. Otherwise, assume wlog that $a\in A$ and $b\in B$. Let us say that $w\in Q'$ has a proper factorization if $w=uv$ with $u\in A\setminus\{\epsilon\}$ and $v\in B\setminus\{\epsilon\}$. We have two (symmetric) subcases depending on where $ba$ goes (it must be in $A$ or $B$ since it has no proper factorization).

  • If $ba\in A$, then $aba$ has no proper factorization since $ba,a\notin B$. Since $aba\in A$ would imply $abab\in A\cdot B$, we get $aba\in B$. As a consequence, $bab$ is neither in $A$ (which would imply $bababa\in A\cdot B$) nor in $B$ (which would imply $abab\in A\cdot B$). Now consider the word $babab$. It has no proper factorization since $bab\notin A\cup B$ and $abab,baba$ are not primitive. If $babab\in A$, then since $aba\in B$ we get $(ba)^4\in A\cdot B$; if $babab\in B$, then since $a\in A$ we get $(ab)^3\in A\cdot B$. So there is no way to have $babab\in A\cdot B$, contradiction.
  • The case $ba\in B$ is completely symmetric. In a nutshell: $bab$ has no proper factorization and cannot be in $B$, so it must be in $A$; therefore $aba$ cannot be in $A$ or $B$; therefore $ababa$ has no proper factorization but also cannot be in either $A$ or $B$, contradiction.

I am currently not sure how to proceed beyond this point; it would be interesting to see if the above argument can be systematically generalized.

$\endgroup$
  • $\begingroup$ Wow, you have my respect. I'll go through it later today or tomorrow as I don't have time right now, but I am seriously impressed :) It took me a few hours to get that {a, b} are in A but I didn't exploit that \epsilon is not a primitive word. How did you approach this problem (or was it "just do it"?)? How long did it take you to come up with that proof? $\endgroup$ – Henning Apr 24 at 8:45
  • $\begingroup$ Thanks! I got the main idea (showing that any nonempty proper suffix of words must be in $A$) by thinking about what happens to some "simple" words. $\epsilon, a$, and $b$ were relatively straightforward, $a^n$ or $b^n$ were out of the question, and considering $ab, abb, abbb, \ldots$ got me on the right path. $\endgroup$ – Klaus Draeger Apr 24 at 10:16
  • 4
    $\begingroup$ Your proof is beautiful and not as hard as I thought (I feel quite stupid now, I spent some time thinking about it). However it seems to heavily relay on epsilon not being element of Q. Is $Q \cup \{ \epsilon \}$ also prime? $\endgroup$ – Henning Apr 24 at 10:23
  • 1
    $\begingroup$ Good question! I'll have to get back to you on that one. $\endgroup$ – Klaus Draeger Apr 24 at 13:21
  • 2
    $\begingroup$ Thanks for the comments, and sorry for the delay. The case where we want to include the empty word seems to be more complicated, see update. $\endgroup$ – Klaus Draeger Apr 26 at 13:44

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.