# Mea Culpa

*Plus more on the separating word problem*

Mea Culpa is not someone we introduced on the blog before. She does not come from the same world as Lofa Polir or Neil L. As in the French movie poster at right, the meaning is “my fault.”

Today we apologize for some oversights and hasty omissions regarding the last post. Then we will explain Dick’s “laws with errors”.

Let’s be clear. The paper we discussed in the last post claiming an order upper bound is wrong. The best upper bound is still due to Zachary Chase and is order , with some log’s.

At GLL we try to be fair and upbeat, especially with proof attempts. We know how hard it is to put yourself out there when you claim a new result. Whether for a famous open problem or not, it is always difficult. Mistakes are possible, miss understandings are possible.

But perhaps this time we have gone too far, and for that we apologize. We just love the SWP, and want to reiterate the idea the post was supposed to be (only) about, an approach to SWP.

There is also Nostra Culpa—“our fault,” Ken says too. Not only is there a short film with that title, there is a 2013 one-singer opera of that title with libretto drawn from a 2012 Twitter feud between the economist Paul Krugman and the president of Estonia. At least our issue did not break out on Twitter. We were instead contacted privately by some friends who knew more about the erroneous paper highlighted in our post. We could have contacted them first—that was our omission.

Again sorry for any confusion we created. Let’s turn to the approach we want to share about SWP.

## Laws with Errors

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

where and are words over the letters and . Recall we can tell if and are different provided there is a finite group so that for some in the value of and are different. This can be computed by a FSA with at most order states. So the smaller is the better.

The trouble is it does not seem to the case that strong enough lower bounds are known for positive laws. This suggest that we make it harder for a law to work.

The idea is to use a FST, that is a finite state transducer. This is a finite state device that reads a symbol, updates its state, and outputs one or more symbols. If is the FST and is a string, let be the result of applying . For example, suppose that is an input . Let the transducer add a after each . Thus maps to:

Then the following is true:

Lemma 1Let be group and let be a transducer with states. Then we can separate from by a FSA with order states provided

is not a law in .

*Proof:* The key is to simulate as we read the input, and at the same time update the group element. This can be done by a FSA with the product and states.

## Open Problems

The hope is that having a law that is invariant for all FST, even only those with few states, is difficult.

A conjecture: Positive laws that can handle all FST transducers with states must be large.

That is are large enough to advance our best bounds on SWP. What do you think?

less maxima culpa, more felix culpa 😉

Thanks Jon as always

Best

Dick