Numerical coincidence: 476 ~ 503

Stream: Equational

[Terence Tao]

A strange coincidence I observed while inspecting the Equation Explorer statistics: Equation 476 x = y ◇ (x ◇ (y ◇ (y ◇ x))) and Equation 503 x = y ◇ (y ◇ (x ◇ (y ◇ x))) have identical implication statistics, despite not being dual (or equivalent). For instance, they share the same three unknown implications (to 359, 3852, and 4065). They do look like similar equations, but I don't have a good explanation for this coincidence. Perhaps there is a hidden symmetry here? I don't see it replicated elsewhere in the table, though.

[Vlad Tsyrklevich]

I wrote a script to look for vertices with identical outbound and inbound implications and found 19 matches, 10 after accounting for duals. (I ignored non-implications under the assumption that all unknowns are non-implications and so the implications data is more complete.)

124 1119 and their duals 206 2450
467 501 and their duals 3140 3106
476 503 and their duals 3076 3069
670 677 704 and their duals 2937 2910 2903
1076 1083 1110 and their duals 2531 2504 2497
1279 1286 and their duals 2328 2301
1692 1719 and their duals 1895 1888
3345 3352 and their duals 4157 4164
3548 3555 and their duals 3954 3961

The only duals I found with identical inbound/outbound implications were:
3355 4154

[Vlad Tsyrklevich]

Some like 124-1119 seem potentially interesting, though a lot of the higher numbered ones have so few inbound/outbound implications to compare that they seem like they could just be artifacts of the data we have.

[Floris van Doorn]

I think it's very likely that these mysterious twins are just an artifact of looking at laws with at most 4 operations, and their twin status would disappear if we increase the set of laws we look at.

[Vlad Tsyrklevich]

This must be true, since these pairs must either refute each other or have a still-unknown relationship

[Vlad Tsyrklevich]

The measure could still capture some type of similarity. If we restricted what implications we looked at to only be 2/3 operations, we may be able to find other cases that have already diverged in the current graph. I wonder what a measure of similarity would look like. Is it that Eqn476\Eqn503 only has equations with many more operations than they do? Is it possible that such a difference could be captured in a single equation?

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

Vlad Tsyrklevich said:

This must be true, since these pairs must either refute each other or have a still-unknown relationship

Non-equivalent equations will never satisfy this stringent a notion (this is a very weak version of the Yoneda lemma btw).

I think the original question was whether the counts coincide here because there is some yet undiscovered syntactic transformation akin to duality that would, if applied to all entries, send the (full, infinite) implication table of one to the other and vice versa; or whether this is indeed a coincidence because we haven't looked at enough equations. The latter's a good bet, but Yoneda-style considerations can't rule out the former (since that would also rule out duality, and we know duality exists).

[Daniel Weber]

We can search for non-trivial isomorphisms of the implication graph (modulo equivalence), see if there are any other than duality

[Vlad Tsyrklevich]

Unless I am misunderstanding, aren't all of these twins (modulo the ones with unknowns/unknown bys) already automorphisms?

[Daniel Weber]

No, they just have the same indegree and outdegree

[Vlad Tsyrklevich]

The ones I posted have the same in/out neighbors

[Daniel Weber]

Oh, then yeah, swapping them is an automorphism

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

Our truncated graph has automorphisms that the full infinite implication graph wouldn't and vice versa, right?

[Vlad Tsyrklevich]

The reverse must be true, and I could see the original also being true but I'm not sure I have a convincing argument as to why

[Vlad Tsyrklevich]

I hadn't thought about this as automorphisms before. Previously when I was thinking about limiting the operations to look for twins in N operations, that would in a sense also be looking for another possible subset of the automorphisms (depending on the shared implications they have in the full graph.) So perhaps the real question is to just find all automorphisms and look at them.

[Daniel Weber]

Zoltan A. Kocsis (Z.A.K.) said:

Our truncated graph has automorphisms that the full infinite implication graph wouldn't and vice versa, right?

hmm, that's right. So we want isomorphisms between large subgraphs of the truncated graph, I'm not sure if that's computationally feasible to find

[Vlad Tsyrklevich]

going to try using a package I found called NAUTY to compute this, let me see how much work this is to feed it our graph

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

I think questions about how homogeneous the full implication graph is can be interesting long-term. We know that there's a nontrivial automorphism, and we know that the structure is not homogenous, since the equivalence class of x=y cannot be switched with any other element.

Are there known (or easy) examples of classes E,F so that every automorphism sending E to F is necessarily duality?

Are there abstract arguments for or against the existence of wild automorphisms (ones that are not duality) on the full graph?

[Daniel Weber]

As it's an infinite graph, it's also theoretically possible that it's isomorphic to a strict subgraph of itself, which would be interesting

[Vlad Tsyrklevich]

I've got it running though I think it may not complete without more hints or a reduction in the problem space somehow. It has a found a few of the twins above. Currently it's running on the condensed graph, ~1450 vertices, ~4.5k edges reduced, ~28k edges closure. I think running over the closure is correct, but running it over the reduction is faster and I _believe_ should only give false-positives but no true-negatives. One idea I have is to collapse the graph further by marking duals as equivalent. I can't convince myself that this will not eliminate some interesting automorphisms, but if it just finishes that's also good.

[Vlad Tsyrklevich]

There are also many configuration options for this, and I suspect better understanding the algorithm and how to tune it may also solve this.

[Daniel Weber]

I don't think running over the reduction should be add false positives - an automorphism of the transitive reduction will also be an automorphism of the full graph

[Vlad Tsyrklevich]

You're right, I had a particular example in mind but running through it just now I see that it's erroneous.

[Vlad Tsyrklevich]

I've gotten as far as discovering all of the twins above in the dual-condensed graph. I will let it crunch for a while and see if it terminates in a few hours, I need to get back to reading in the mean time.

[Vlad Tsyrklevich]

I've been running the algorithm on the implications as a directed graph. Running this on the implications graph as an undirected graph returns almost instantaneously, even without condensing duals. Can someone else confirm that they believe that the automorphisms of the undirected graph are a strict superset of the directed graph?

[Vlad Tsyrklevich]

Looking at the undirected automorphisms, the only ones are the twins above and the single massive dual automorphism. In particular, other than duals, there are no generators with more than 1 transposition which is what I was particularly interested in finding.

[Terence Tao]

If an undirected automorphism of a Hasse diagram preserves the maximum element x=x or the minimum element x=y then it must preserve the directions I think as one can use the flow towards or away from those elements to orient the graph.

[Terence Tao]

Probably any twin w ~ w' for a truncated graph will not persist indefinitely. Any law w implies all substitutions of that law in which a variable is replaced with a longer word, but it would be very strange for another law w' to imply all such substitutions of w without also implying w itself.

Possibly one clue to investigate this phenomenon further is to calculate the affine scheme associated to each law - that is to say, the space of coefficients a, b in an unspecified field or ring for which the linear magma x ◇ y = ax + by obey the given law. I would suspect that twin laws generate almost identical affine schemes, which could be a partial explanation for the phenomenon.

[Jose Brox]

Terence Tao ha dicho:

Probably any twin w ~ w' for a truncated graph will not persist indefinitely.

I finally had time to run Prover9 (Mace4 actually) on does 476(x,y) imply 503(xy,y)? The answer is no.

(Please check that 503(x*y,y) indeed is x * y = y * (y * ( ( x * y ) * (y * ( x * y )))) )

As for their affine schemes, note that the substitution of the linear product (over a commutative ring) is easily drawn from an equation: write a polynomial for each variable, with a monomial for each repetition of the variable, and each monomial having a power of a equal to the number of times the variable is at the left and a power of b equal to the number of times it is at the right when "denesting" the term (i.e., when looking at the tree representation of the term, we go from the variable up to the root, count the number of left branches for the power of a, and the number of right branches for the power of b).

In this case, following that rule it is easy to see that the systems of polynomials are
ab+b^4 = 1, ab^3+ab^2+a = 0 for 476 and
ab^2+b^4 = 1, ab^3+ab+a = 0 for 503.
These systems have the same 4 degenerate solutions (with a=0), but disjoint sets of nontrivial solutions.

[Terence Tao]

Thanks for working this out. This begins to nudge me more towards the camp of "probably just a coincidence" than "a deep unexplained phenomenon" here. (I was hoping to see some sort of symmetry between the two algebraic solution sets.)

[Kevin Buzzard]

Before falling back on the "it's a coincidence" explanation, one might reflect on the chances that such a coincidence could happen. Naively it sounds astronomically small!

[Jose Brox]

Terence Tao ha dicho:

Any law w implies all substitutions of that law in which a variable is replaced with a longer word, but it would be very strange for another law w' to imply all such substitutions of w without also implying w itself.

I don't think this phenomenon is impossible in general (a very interesting question in my opinion, it also ocurred to me when you published this coincidence!).

But for this case note that we would have:
1) A a magma satisfying x=p(x,y)
2) B a magma satisfying x=q(x,y)
3) Con(B)=Con(A)-{(x,p)}\cup {(x,q)} and vice versa.
Then since x=p(x,y) in A, we get q(x,y)=p(q(x,y),y) in A and also in B, unless x=q(x,y) in A or q(x,y)=p(x,y)=x in A (and we are done since then Con(A)=Con(B)). So p(q(x,y),y)=q(x,y) in B, but q(x,y)=x in B, so p(x,y)=x in B, and again Con(B)=Con(A).

[Terence Tao]

I see, the point is that if a magma obeys a law such as x=p(x,y) then every element is expressible as a compound word, and hence every instance of a law is also an instance of a longer law formed by a substitution. So for such a magma, one cannot imply every substitution of a law, without also obeying the law itself.

I guess somehow twins such as 476 and 503 are "very close" in some topology on the implication graph, but the graph remains "Hausdorff" and one is eventually able to separate the two. The remaining question is why such "anomalously close" pairs in the graph exist. I had thought maybe that the corresponding varieties were somehow close together, but this does not seem to be obviously the case; so it's still very mysterious to me.