# Is the Set of all Primitive Words a Prime Language?

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.

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.

• 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 Apr 24 at 8:45
• 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 Apr 24 at 10:16
• 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 Apr 24 at 10:23
• Good question! I'll have to get back to you on that one. – Klaus Draeger Apr 24 at 13:21
• 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 Apr 26 at 13:44