Hard problems and negative results

Stream: Equational

[Terence Tao]

I thought it might be good to have a catch-all thread for mentioning any outstanding implications or tricky equations that (a) do not already have a dedicated thread, and/or (b) have some negative results to report (e.g., a technique that works on other implications, does not work on these problems). This could help focus efforts and avoid redundant expenditure of CPU or human mental power on methods that have already shown to be ineffective.

I'll start by mentioning two problems reported on by @Jose Brox :

• 63 => 1692. This is a very similar implication to "Asterix => Oberlix" (and Jose calls it "Dupond => Dupont" accordingly; I think the English version would be "Thompson => Thomson"). The Knuth-Bendix algorithm does not seem to converge on this problem; but perhaps the greedy approach and/or the translation-invariant approach could be fruitful here.
• 5105 => 2. This is true for finite magmas (with a very short proof), but it was conjectured by Kisielewicz that there are infinite models. Again, Knuth-Bendix does not seem to converge here, but it is tempting to again try some combination of the greedy and translation-invariant approaches.

In terms of raw "yield" of number of potential implications, it's hard to beat the nice round Equation 2000 (or equivalently, 1167), with 39 outstanding implications (including to 1701, which is known to have some interesting infinite models), or 78 if one accounts for duality. However, Equation 2000 involves three variables so is likely quite overdetermined. It has a finite model of order 2, namely the right-absorptive magma; are there any other interesting models that could help understand this equation?

[Zoltan A. Kocsis (Z.A.K.)]

However, Equation 2000 involves three variables so is likely quite overdetermined. It has a finite model of order 2, namely the right-absorptive magma; are there any other interesting models that could help understand this equation?

This is encouraging news as far as the modified translation-invariant magma construction is concerned!

Acting on your suggestion in another thread, I'll draft a blueprint entry tonight on how to perform such constructions. I don't have anything like a general theory for why and when these work nicely, but I believe the underlying heuristics are dead simple. Here's a brief outline of what I plan to say:

The first ingredient needed is some infinite model of the antecedent. I've been calling this the base model. Your observation about Equation 2000 means that the right-absorptive magma on $\mathbb{N}$ constitutes a viable base model for potential implications 2000 -> ...!

[edit: this had a different example initially, from 2460. This was incorrect. I don't know how to resolve 2460->23, and I think it's an interesting law.]

My running example will be a model refuting 1659->45, since it's much simpler to construct than the ones for 1701. Let's start with the following infinite model, $(\mathbb{Z},\diamond)$ of 1659 on $\mathbb{Z}$:

$x\diamond y = \begin{cases} x+1 & \text{if } x,y \text{ have the same parity} \\ x -1 & \text{otherwise} \end{cases}$

This simple model, of course, satisfies equations 1659 and 4315. We will eventually modify it by setting

$x \diamond_m y = \begin{cases} 0 & \text{if } x=0,\: x,y \text{ have the same parity} \\ x+1 & \text{if } x\neq 0,\: x,y \text{ have the same parity} \\ x -1 & \text{otherwise} \end{cases}$

and checking that $(\mathbb{N}, \diamond_m )$ satisfies 1659 but refutes 4315.

How does one find this? Well, one can first insist that some elements (tuples) of the model should constitute a counterexample to the consequent. The consequent,Equation 4315 is $x \diamond (y \diamond x) = x \diamond (y \diamond z)$ in this case, which always holds if $x = z$. So let's insist that the tuple $(0,0,1)$ should constitute that counterexample.

The idea is to modify $\diamond$ minimally, causing this tuple to be an actual counterexample to 4315. We can compute $0 \diamond (0 \diamond 0) = 0 \diamond 1 = -1$ and similarly $0 \diamond (0 \diamond 1) = -1$. This calculation suggests that we could accomplish this by setting $0 \diamond_m 1$ to something other than $-1$. We have many choices here: should we take $0 \diamond_m 1 =0, 0 \diamond_m 1 = 1, 0 \diamond_m 1 = 2 \dots$ (not to mention the negatives)?

Well, it's easy to see that setting $0 \diamond_m 1 = 1$ wouldn't work: we'd have $0 \diamond_m (0 \diamond_m 0) = 0 \diamond_m 1 = \diamond_m (0 \diamond_m 1)$ again, which is precisely what we're trying to avoid. So let's start with setting $0 \diamond_m 1 = 0$ and $x \diamond_m y = x \diamond y$ for anything else, which at least breaks 4315.

Unfortunately, it also breaks 1659. For any $z$ in our magma, we now have $(0 \diamond_m 1) \diamond_m ((1 \diamond_m 1) \diamond_m z) = 0 \diamond_m (2 \diamond_m z)$ which equals $0 \diamond_m 1 = 0$ as desired for every even $z$, but equals $0 \diamond_m 3 = -1 \neq 0$ for every odd $z$. Fortunately, the breakage is tightly controlled: by considering what happens if $x \neq 0$ and $y \neq 1$ we see that all new counterexamples to 4315 are of this form.

The calculation now suggests setting $0 \diamond_m 3 = 0$ to fix this problem. But doing this just moves the issue one level higher: we then have $(0 \diamond_m 3) \diamond_m ((3 \diamond_m 3) \diamond_m z) = 0 \diamond_m (4 \diamond_m z)$ which equals $0 \diamond_m 3 = 0$ as desired for every even $z$, but equals $0 \diamond_m 5 = -1 \neq 0$ for every odd $z$. But at this point we can fix all these infinitely many problems in one go, before they even arise:

$x \diamond_m y = \begin{cases} 0 & \text{if } x=0,\: x,y \text{ have the same parity} \\ x+1 & \text{if } x\neq 0,\: x,y \text{ have the same parity} \\ x -1 & \text{otherwise} \end{cases}$

At this point we might as well truncate the model to $\mathbb{N}$ since the result of the $\diamond_m$ operation is nonnegative if the operands are nonnegative as well. This finishes the construction.

So the strategy is to trace the effects of this initial modification and then make some further adjustments which restore the antecedent. For "good" base models, this is a finite amount of work. The result may be a "really finite" modification in the sense that the operator tables of the original model and the new model differ in finitely many coefficients; or one which differs in infinitely many coefficients, but is still finitary in some syntactic/logical sense that one can describe the new operation using the old one and finitely many constant case distinctions.

The former sort of model is more desirable for multiple reasons: e.g. it should refute many more potential implications than the much more regular latter sort. However, more difficult refutations using this construction, like 1701->4587, usually require the latter sort of model.

Note: The missing key to understanding what I'm doing and how far this simple idea can stretch is, I think, a notion of "good" base model which ensures that the required modifications exist. I'm not sure what if anything this could look like at the moment, nor how much such a notion of goodness needs to depend on the consequent that I am trying to refute.

[Terence Tao]

Modifying the right absorptive magma for 2000 sounds like a promising idea to me because it partially gets around the objection that 2000 has three variables and as such will be usually so "overdetermined" that it is hard to engineer solutions to the law. For instance, if it can stay right-absorptive on the values of z ◇ z, then the value of y becomes irrelevant in x = (y ◇ (z ◇ z)) ◇ (z ◇ x) and so the law morally becomes a two-variable law again.

[Daniel Weber]

Equation 2000 (well, its dual 1659) was also discussed in #Equational > Equation 2126

[Zoltan A. Kocsis (Z.A.K.)]

I should mention @Terence Tao : I do already have a few countermodels of 1659 -> 4315 (and hence 2000 -> ...) implications using modified translation-invariant magmas worked out. I don't know yet how many of the implications they refute. But given the progress in the thread linked by @Daniel Weber I was thinking not to bother formalizing them, and just wait for the confluence methods to settle them.

[Fan Zheng]

It seems that this equation can be completed to an infinite sequence of rewriting rules that is complete, see #Equational > Equation 2126.

[Zoltan A. Kocsis (Z.A.K.)]

Contradicting what I said upthread, I now plan to imminently submit a PR resolving the 1659 -> ... implications.
Is this acceptable? I hope it doesn't cause any issues, as I really don't want to want to interfere with anyone else's contributions :(

I have three reasons:

• It decreases the number of unknowns, helps direct effort towards more difficult, more interesting cases.
• From tomorrow onward I'll be very busy, so I probably won't get to contribute much more to the project. This seems like a final chance for me to write at least a little bit of documentation on how I approach modifying translation-invariant magmas, using an example that turns out to be relatively straightforward compared to the difficult 1701 models.
• There should still be plenty of examples left for others to apply their methods to. In particular, confluence-style methods should resolve a lot of stuff, and without new base models, this method probably won't be applicable to those. And the infinite rewrite rule family for this equation is worthy of inclusion anyway, even if it's not the first to refute these unknowns.

[Shreyas Srinivas]

We can be sure of no overlap if you create a task

[Shreyas Srinivas]

We can make it a project task and you can claim it.

[Shreyas Srinivas]

I don't see any other tasks on the project dashboard for 1659

[Terence Tao]

I'll go ahead and create such a task now.

[Terence Tao]

equational#571