20,000 Comments and More

With more about the Separating Words Problem

I.I.T. Madras page

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.

src

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 bound on the SWP over alphabet .

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

Each edge goes to the next state on the same track on both and unless we place a “crossover” so that the edges switch tracks on . The primed track has accepting states. It does not matter whether the start state is or , but it is the same for any pair of strings of length that we wish to distinguish.

Let be the set of places where and differ. Now suppose we have such that the intersection of with the residue class is odd. Make by placing one “crossover” at point on the tracks; that is, make the transitions for and be

where the addition is modulo . Then whenever a place where and 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, accepts and rejects or vice-versa.

If for every we could find such and with then SWP would fall with the best possible logarithmic size, nullifying anything like Zachary Chase’s improvement from to . The “” is not hiding any factors with a tilde—it is just a bare 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 is not only independent of particular strings but also independent of the lengths of the string, except insofar as the maximum index in constrains the smallest that works. But then the report states a theorem that invests 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 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 does not help separate any more strings: If and both have even cardinality then adding two crossovers at and 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 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 is

where are words over . We will think of as embeddings within the group of the binary strings we want to separate. The law says that for all substitutions of and as elements in . Thus

is a law that holds in abelian groups. Every finite group satisfies the law

where 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 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 or less elements. The size of a law is the maximum of the length of the words and .

Laws and SWP

Suppose that we wish to construct a FSA that can tell from . We assume that and are distinct long strings over . Pick a finite group . The key is two observations:

1. If is not a law over , then we can set and to elements in so that

   

2. There is a FSA that can compute the values of and as elements in with order states.

This then proves that we can separate the words with order the size of states.

Warning It is important that the FSA operates on and 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 holds in all finite groups of size at most . Alas this is not true. Well not exactly. Our laws are of the form

Since there are no inverses allowed in and these are called positive laws. If we drop that restriction, then short laws do exist. There are laws of size that hold for all groups of order . 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 objects is . The shortest such identity in has length :

They also note that:

The problem is to find upper bounds on the function . This problem is inverse to finding the asymptotics of the length of the shortest identity in full transformation semigroups .

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

Where and are as before words over . Assume that for all small groups this is always true when we set and to elements.

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

This means that the law must be robust to modifications that can be done with few states. As examples, the FSA could:

1. The FSA could map and leave all others the same.

2. The FSA could map to when ever it sees this.

3. The FSA could delete the even letters. Thus

   

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

where is a new letter. Thus

becomes

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?

Again we thank Anoop and all our readers for stimulating comments.

[changed wording in section 2 and improved transition to the rest]