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:
-
If
is not a law over
, then we can set
and
to elements in
so that
-
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:
-
The FSA could map
and leave all others the same.
-
The FSA could map
to
when ever it sees this.
-
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]
Trackbacks