With more about the Separating Words Problem

Anoop S K M is a PhD student in the theory group of I.I.T. Madras in Chennai, India. His comment two weeks ago Monday was the 20,000th reader comment (including trackbacks) on this blog.

Today we thank Anoop and all our readers and say more about the subject of his comment.

Anoop’s advisor is Jayalal Sarma, who has a further connection to me (Ken). Sarma has co-authored three papers with my PhD graduate Maurice Jansen, whose work we have also featured here.

The comment was Anoop’s first and thus far only one on the blog. In passing we note that after one’s first comment is moderated through, subsequent ones appear freely and immediately. Thus one can say that Anoop had only a 0.005% chance of hitting the milestone.

Dick and I would also like to give a warm shout out to someone else who in another sense had almost a 56% chance of hitting it: Jon Awbrey, who writes the blog Inquiry Into Inquiry and also contributes to the nLab Project.

As we were twenty-seven comments into our third myriad at the time of drafting this post, we note that most of his 15-of-27 comments are trackback citations of our previous post on proof complexity, but he wrote two long comments as well. We have not had time to act on them; for my part, chess cheating has found ways to mutate into new kinds of cases even as I see hope for stemming the main online outbreak of it. But comments can also be resources for others, especially students who may be emboldened to take a swing at progress from where we’ve left off.

## Anoop’s Comment and SWP Ideas

Anoop’s comment was in our recent post on the Separating Word Problem (SWP). He asked about a technical report by Jiří Wiedermann claiming a clean best-possible ${O(\log n)}$ bound on the SWP over alphabet ${\{0,1\}}$.

Wiedermann’s idea is simple to state—maybe too simple: Consider finite state automata (FSAs) ${A}$ whose ${2m}$ states form two ${m}$-cycle “tracks”:

$\displaystyle q_0 \rightarrow q_1 \rightarrow \cdots \rightarrow q_{m-1} \rightarrow q_0; \qquad q'_0 \rightarrow q'_1 \rightarrow \cdots \rightarrow q'_{m-1} \rightarrow q'_0$

Each edge goes to the next state on the same track on both ${0}$ and ${1}$ unless we place a “crossover” so that the edges switch tracks on ${1}$. The primed track has accepting states. It does not matter whether the start state is ${q_0}$ or ${q'_0}$, but it is the same for any pair of strings ${u,v}$ of length ${n \gg m}$ that we wish to distinguish.

Let ${S \subseteq [n]}$ be the set of places where ${u}$ and ${v}$ differ. Now suppose we have ${b \in [m]}$ such that the intersection of ${S}$ with the residue class ${R_{m,b} = \{am + b : a \in \mathbb{N}\}}$ is odd. Make ${A = A_{m,b}}$ by placing one “crossover” at point ${b}$ on the tracks; that is, make the transitions for ${q_b}$ and ${q'_b}$ be

$\displaystyle (q_b,0,q_{b+1}),~(q_b,1,q'_{b+1}),~(q'_b,0,q'_{b+1}),~(q'_b,1,q_{b+1}),$

where the addition is modulo ${m}$. Then whenever a place where ${u}$ and ${v}$ differ enters the crossover, the strings flip their status of being on the same track or different tracks. Since this happens an odd number of times, ${A_{m,b}}$ accepts ${u}$ and rejects ${v}$ or vice-versa.

If for every ${S \subseteq [n]}$ we could find such ${m}$ and ${b}$ with ${m = O(\log n)}$ then SWP would fall with the best possible logarithmic size, nullifying anything like Zachary Chase’s improvement from ${m = \tilde{O}(n^{2/5})}$ to ${m = \tilde{O}(n^{1/3})}$. The “${m = O(\log n)}$” is not hiding any ${\log n}$ factors with a tilde—it is just a bare ${\log n}$ factor. The report claims this complete resolution, but it makes and then unmakes a point in a way we don’t follow. The point is that the idea of focusing on subsets ${S}$ is not only independent of particular strings ${u,v}$ but also independent of the lengths ${n}$ of the string, except insofar as the maximum index in ${S}$ constrains the smallest ${m}$ that works. But then the report states a theorem that invests ${n}$ itself with significance that contradicts said point, so it just appears wrong.

The report anyway does not appear either on Wiedermann’s publications page or his DBLP page. Its conclusion references a 2015 post on this blog in which SWP was included, but we had not heard of this until Anoop’s comment. So it goes in our mistake file. We have been grappling all week with the subject of claims and mistakes on a much larger scale with complicated papers and techniques. In the old days, ideas and errors would be threshed out in-person at conferences and workshops and only the finished product would be visible to those outside the loop. Now we not only have Internet connectivity but also the pandemic has curtailed the “in-person” aspect. Thus we are not averse to promoting the threshing and wonder how best to extract the useful novelty from new attempts that likely have errors.

The ${A_{m,b}}$ construction is neat but has a weakness that can be framed as motivation for Dick’s idea in the rest of this post. Adding more crossovers for a fixed ${m}$ does not help separate any more strings: If ${S \cap R_{m,b}}$ and ${S \cap R_{m,c}}$ both have even cardinality then adding two crossovers at ${b}$ and ${c}$ has no effect. Intuitively speaking, all crossovers behave merely as the same non-unit element of the two-element group. In particular, they commute with each other. The idea moving forward is, can we get more interesting behavior from non-commutative groups that still yield small automata ${A}$ separating given pairs of strings?

## Laws on Finite Groups

Let’s start to explain a connection of SWP with finite groups. A law for a group ${G}$ is

$\displaystyle U = V,$

where ${U,V}$ are words over ${\{ A,B \}}$. We will think of ${U,V}$ as embeddings within the group of the binary strings ${u,v}$ we want to separate. The law says that ${U=V}$ for all substitutions of ${A}$ and ${B}$ as elements in ${G}$. Thus

$\displaystyle AB = BA$

is a law that holds in abelian groups. Every finite group ${G}$ satisfies the law

$\displaystyle A^{n} = 1,$

where ${n}$ is the size of the group.

There has been quite a bit of research on laws for groups.

• Some are on the complexity of checking if they hold. It is a famous result that with randomness one can check to see if ${AB=BA}$ with few tests.

• Some are on the structure of laws.

• Most relevant to SWP is the interest in the smallest size law that holds for all groups of ${n}$ or less elements. The size of a law is the maximum of the length of the words ${U}$ and ${V}$.

## Laws and SWP

Suppose that we wish to construct a FSA that can tell ${\alpha}$ from ${\beta}$. We assume that ${\alpha}$ and ${\beta}$ are distinct ${n}$ long strings over ${A,B}$. Pick a finite group ${G}$. The key is two observations:

1. If ${\alpha = \beta}$ is not a law over ${G}$, then we can set ${A}$ and ${B}$ to elements in ${G}$ so that

$\displaystyle \alpha \neq \beta.$

2. There is a FSA that can compute the values of ${\alpha}$ and ${\beta}$ as elements in ${G}$ with order ${G}$ states.

This then proves that we can separate the words ${A,B}$ with order the size of ${G}$ states.

Warning It is important that the FSA operates on ${\alpha}$ and ${\beta}$ independently. Moreover, the FSA must run the same computation on these strings—the output must be different.

I liked this approach since I hoped there would be useful results on laws in groups. There is quite a bit known. It would have been neat if there was a paper that proved: No law of length ${n}$ holds in all finite groups of size at most ${n^{1/4}}$. Alas this is not true. Well not exactly. Our laws are of the form

$\displaystyle U = V.$

Since there are no inverses allowed in ${U}$ and ${V}$ these are called positive laws. If we drop that restriction, then short laws do exist. There are laws of size ${O(n^{2/3})}$ that hold for all groups of order ${n}$. But I believe it is still open whether positive laws can be small.

## Positive Laws

I (Dick) started to search the web about laws in groups. I quickly found a paper by Andrei Bulatov, Olga Karpova, Arseny Shur, Konstantin Startsev on exactly this approach, titled “Lower Bounds on Words Separation: Are There Short Identities in Transformation Semigroups?” They study the problem, prove some results, and do some computer searches. They say:

It is known that the shortest positive identity in the symmetric group on ${3}$ objects ${S_{3}}$ is ${x^{2}y^{2} = y^{2}x^{2}}$. The shortest such identity in ${S_{4}}$ has length ${11}$:

$\displaystyle x^{6}y^{2}xy^{2} = y^{2}xy^{2}x^{6}.$

They also note that:

The problem is to find upper bounds on the function ${Sep}$. This problem is inverse to finding the asymptotics of the length of the shortest identity in full transformation semigroups ${T_{k}}$.

I believe the last part of their statement is true, but perhaps misleading. I would argue that laws are related to SWP with a twist. The hope is that this twist is enough to make progress. Let me explain.

## Laws with Errors

I think there is hope that positive laws must be large, if we extend what it mean by a law. Suppose that we have a law

$\displaystyle U_{1} \cdots U_{n} = V_{1} \cdots V_{n}.$

Where ${U}$ and ${V}$ are as before words over ${\{A,B\}}$. Assume that for all small groups this is always true when we set ${A}$ and ${B}$ to elements.

We note however we can have the FSA do more than just substitutions. We could have it modify the ${U}$ and ${V}$. We can have the FSA make some changes to ${U}$ and ${V}$: Of course the FSA must do the same to ${U}$ and ${V}$, and it must keep the number of states down.

This means that the law ${U=V}$ must be robust to modifications that can be done with few states. As examples, the FSA could:

1. The FSA could map ${A^{2} \rightarrow A}$ and leave all others the same.

2. The FSA could map ${ABBBA}$ to ${A}$ when ever it sees this.

3. The FSA could delete the even letters. Thus

$\displaystyle \begin{array}{rcl} A^{6}B^{2}AB^{2} &=& B^{2}AB^{2}A^{6} \\ AAAAAA BB A BB &=& BB A BB AAAAAA \\ A~ A~ A~ B~ A ~ B &=& B~ A~ B ~ A~ A~ A \\ AAABA &=& BABAAA. \end{array}$

Note the FSA could even add new letters. Thus it could

$\displaystyle AB \rightarrow ACB,$

where ${C}$ is a new letter. Thus

$\displaystyle AAAAAA BB A BB = BB A BB AAAAAA$

becomes

$\displaystyle AAAAAA CBB A CBB = BB A C BB AAAAAA.$

And so on.

## Open Problems

Can we get better lower bounds on positive laws if we require them to be resilient to such modifications? Ones that can be done by a small state FSA. What do you think?