<p>The answer is yes. Suppose we have a factorization <span class="math-container">$Q = A\cdot B$</span>. </p>

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

<p>Next we get that <span class="math-container">$a^mb^n\in A$</span> (and, completely analogously, <span class="math-container">$b^ma^n\in A$</span>) for all <span class="math-container">$m,n&gt;0$</span> by induction on <span class="math-container">$m$</span>:</p>

<p>For <span class="math-container">$m=1$</span>, since <span class="math-container">$ab^n\in Q$</span>, we must have <span class="math-container">$ab^n = uv$</span> with <span class="math-container">$u\in A, v\in B$</span>. Since <span class="math-container">$u\neq\epsilon$</span>, <span class="math-container">$v$</span> must be <span class="math-container">$b^k$</span> for some <span class="math-container">$k\le n$</span>. But if <span class="math-container">$k&gt;0$</span>, then since <span class="math-container">$b\in A$</span> we get <span class="math-container">$b^{1+k}\in Q$</span>, contradiction. So <span class="math-container">$v=\epsilon$</span>, and <span class="math-container">$ab^n\in A$</span>.   </p>

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

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

<p>For <span class="math-container">$r&gt;1$</span>, we use another induction on <span class="math-container">$m_1$</span>, which works very much the same way as the one for <span class="math-container">$r=1$</span> above: </p>

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

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

<hr>

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

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

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

<p>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.</p>

CC BY-SA 4.0
2019-04-24T08:45:13.287Z
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?
Henning
CC BY-SA 4.0
2019-04-24T10:16:49.467Z
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.
Klaus Draeger
CC BY-SA 4.0
2019-04-24T10:23:56.007Z
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?
Henning
CC BY-SA 4.0
2019-04-24T13:21:25.813Z
Good question! I'll have to get back to you on that one.
Klaus Draeger
CC BY-SA 4.0
2019-04-24T13:36:30.533Z
I would conjecture that languages are prime if their words are in some sense "dependent", for example, if the probability that we can exchange a prefix of a sentence with a random prefix of the same length so that the word stays a sentence is neglectable with regard to the length of the sentence without the prefix.
This would also show that $w^{-1}Q$ is prime for any $w$.
// edit: That conjecture is not true. Consider $\{ a, b \} Q$.
Henning
CC BY-SA 4.0
2019-04-25T07:19:24.113Z
Probably it can be repaired, but currently there seems to be a little gap in the proof: whenever the induction hypothesis is applied to $v$, one would need that $v$ is primitive, since $A$ only contains primitive words.
Thomas S
CC BY-SA 4.0
2019-04-25T07:58:56.327Z
@Thomas S If $v\in B$ is not primitive, just take its root which is in $A$.
Wei Zhan
CC BY-SA 4.0
2019-04-25T13:14:13.660Z
@Willard Zhan: you are right, no gap, my bad...
Thomas S
CC BY-SA 4.0
2019-04-25T15:28:52.397Z
@ThomasS If you are talking about $Q \cup \{ \epsilon \}$, I don't see how you can rule out that $ab^n \in B$.
Henning
CC BY-SA 4.0
2019-04-26T13:44:47.497Z
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.
Klaus Draeger
CC BY-SA 4.0
2019-04-28T19:31:44.337Z
I actually think now that $Q \cup \{ \epsilon \}$ is not prime.
I optimized my SAT construction and the SAT solver found [a solution that consideres all primitive words up to length 9](https://gist.github.com/hediet/911fe060c95ba5e7ec54f9d5fc7ca1f4) where I forced $a \in A$ and $ab \in B$.
The SAT solver also found a solution for all primitive words up to length 12.
Henning
CC BY-SA 4.0
2019-04-24T08:01:09.533Z
2019-04-26T13:43:19.350Z
2019-04-26T13:43:19.350Z
Klaus Draeger
<p>A word <span class="math-container">$w$</span> is called <em>primitive</em>, if there is no word <span class="math-container">$v$</span> and <span class="math-container">$k &gt; 1$</span> so that <span class="math-container">$w = v^k$</span>.
The set <span class="math-container">$Q$</span> of all primitive words over an alphabet <span class="math-container">$\Sigma$</span> is a well known language. WLOG we can choose <span class="math-container">$\Sigma = \{ a,b \}$</span>.</p>

<p>A language <span class="math-container">$L$</span> is <em>prime</em>, if for every language <span class="math-container">$A$</span> and <span class="math-container">$B$</span> with <span class="math-container">$L = A \cdot B$</span> we have <span class="math-container">$A = \{\epsilon\}$</span> or <span class="math-container">$B = \{ \epsilon \}$</span>.</p>

<p>Is Q prime?</p>

<p>With the help of a SAT solver I could show that we either have <span class="math-container">$\{a,b\} \subseteq A$</span> or <span class="math-container">$\{a,b\} \subseteq B$</span> as otherwise <span class="math-container">$\{ ababa, babab \} \subset Q$</span> cannot be factorized into <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, but have been stuck since then.</p>

<fl.formal-languages>
Is the Set of all Primitive Words a Prime Language?
Henning
# Is the Set of all Primitive Words a Prime Language?

(Asked by: username_0 on 2019-04-23)

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.

**Tags:** fl.formal-languages

---

## 1 answers

### Answer by username_1 on 2019-04-24. Score: 13 | Accepted answer

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, or $v=b^k$ for some $k. 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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: Good question! I'll have to get back to you on that one.  
> **username_0**: I would conjecture that languages are prime if their words are in some sense "dependent", for example, if the probability that we can exchange a prefix of a sentence with a random prefix of the same length so that the word stays a sentence is neglectable with regard to the length of the sentence without the prefix. This would also show that $w^{-1}Q$ is prime for any $w$. // edit: That conjecture is not true. Consider $\{ a, b \} Q$.  
> **username_2**: Probably it can be repaired, but currently there seems to be a little gap in the proof: whenever the induction hypothesis is applied to $v$, one would need that $v$ is primitive, since $A$ only contains primitive words.  
> **username_3**: @Thomas S If $v\in B$ is not primitive, just take its root which is in $A$.  
> **username_2**: @Willard Zhan: you are right, no gap, my bad...  
> **username_0**: @ThomasS If you are talking about $Q \cup \{ \epsilon \}$, I don't see how you can rule out that $ab^n \in B$.  
> **username_1**: 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.  
> **username_0**: I actually think now that $Q \cup \{ \epsilon \}$ is not prime. I optimized my SAT construction and the SAT solver found [a solution that consideres all primitive words up to length 9](https://gist.github.com/hediet/911fe060c95ba5e7ec54f9d5fc7ca1f4) where I forced $a \in A$ and $ab \in B$. The SAT solver also found a solution for all primitive words up to length 12.  

---

