Chronicles of Harry

Apparently this was recently proven by Thomas Browning, and the paper also proves that the set is closed! Wow!

I haven't yet had time to actually read this, but I've already gone and updated the page on my website... (Though as of when I'm writing this, the update hasn't gone through yet. :P )

OK, I've turned a bunch of my recent thinking about equational probabilities into a webpage!

OK, just a quick followup to these entries: Loops with the inverse property are not enough to get gaps or well-ordering. You can iterate the "generalized dihedral loop" construction, and if the input is a loop with the inverse property, then so is the output. Meanwhile the fraction of involutions approaches 1.

So: It might work for groups. It might work for Moufang loops. (It definitely works for abelian groups.) But it doesn't work for monoids (you can't get rid of inverses) and it doesn't work for loops with the inverse property (you do need some sort of associativity). (Notionally, one could try it for Bol loops or Bruck loops? I am probably not going to do that.)

Meanwhile, over on the ring-like-things side of things, it currently seems entirely plausible to me that all this works even for rngs without associativity, i.e., having absolutely no constraints on the multiplication other than distributivity. Being built on top of an abelian group does a lot, I guess?

-Harry

So continuing from last entry, I thought I'd see what are the biggest actual non-1 probabilities I can get for small Moufang loops (for involutions, commutativity, and associativity); so if there are indeed gaps, we can get an idea what they might be.

Searching for small finite Moufang loops quickly turned up this paper; according to it, most of the non-associative Moufang loops of small order are what I'm going to call "generalized dihedral Moufang loops" (the paper, oddly, doesn't seem to give them a name).

Basically, if you have a group G, you can define a Moufang loop L of order 2|G| by adjoining an element x and defining (for g,h∈G)

gh = gh
g(hx) = (hg)x
(gx)h = (gh^-1)x
(gx)(hx) = h^-1g.

You'll notice that if G is abelian, then L is just the generalized dihedral group G⋊C₂. If G is nonabelian, however, then L is a nonassociative Moufang loop.

Because these are most of the ones of small order, I decided to focus on these, in the hopes that these would give me the best non-1 probabilities. Also, in the group case, we know that the best non-1 probabilities for a²=1 and for ab=ba both come from the dihedral group D₈, so this seemed like a decent direction to try.

The results are interesting. First off, involutions and commutativity. These follow exactly the same formulas as they do in the group case... except since the input no longer has to be abelian, we can now get larger numbers out!

Specifically,
P_L(a²=1) = 1/2 + 1/2 * P_G(a²=1).

Picking G=D₈, so P_G(a²=1) = 3/4 (i.e. the maximum), we get P_L(a²=1) = 7/8, which is what's better than what's possible for a group!

Again, this is the same formula as in the case where L is a group and G is abelian; but in that case our maximum non-1 input would be 1/2.

As for commutativity, we get
P_L(ab=ba) = 1/4 * P_G(ab=ba) + 3/4 * P_G(a²=1).

So again picking G=D₈, yielding probabilities of 5/8 and 3/4 respectively (i.e. the maxima once again), we get a commuting probability of 23/32, again better than the 5/8 that's possible for a group!

Once again, this is the same formula as where L is a group and G is abelian, just, now we can pick larger inputs.

Edit: Worth noting also, that when we look at the "commutalizers", we see that some of them are of order 12, and so not subloops. So that's why it's possible to do better than the 3/4 and 5/8 bounds, it would seem.

Finally, what about associativity? What do we get for that? Well, what we end up getting is
P_L((ab)c=a(bc)) = 1/8 + 3/4 * P_G(ab=ba) + 1/8 * P_G(abc=cba).

(Note there's no parentheses on the equation abc=cba, as it's taking place in a group.)

Now, that last probability is a new one, but it's not a difficult one. It's pretty easy to adapt the usual 5/8 commutativity argument to this case and see that this probability also can never be more than 5/8 if the group is not abelian; and that 5/8 is once again achieved by D₈. (Indeed, for a generalized dihedral group, this probability will always be equal to the commutation probability.)

So, plugging this in, we get an association probability of 9/16. So, it is possible to have a nonassociative Moufang loop where the probability that 3 random elements associate is at least 9/16.

Of course, this is just what's possible with these generalized dihedral Moufang loops! It's possible the real numbers could be higher... or that there could not be a gap at all. But hey, these could be the correct numbers, right? :) (Hell, I'd say there's a decent chance they are!) And they certainly constrain what's possible...

Edit again: Actually, with regard to associativity, this is not the best possible! If we look at the octonion Moufang loop of 16 elements, then if I've done my calculations correctly, this has an association probability of 43/64, which is bigger than 9/16. Of course, its commutation probability is much worse...

-Harry

So the past few weeks I've gotten sucked back into thinking about probabilities of equations being satisfied in groups after deciding to get in touch with Sean Eberhard. (You may notice I've added a bit to that page.) I know, I know, I should be thinking about integer complexity, but, y'know, sometimes something else calls.

By the way, a question I forgot to ask about on the original page is whether these sets are closed. That question's been added now.

Here are some things I've learned -- some of which has been added to my website page, some of which has not:

1. I asked what happens if we allow for compact groups instead of just finite groups. Well, for the case of [a,b], i.e. commuting probabilities, what happens is nothing! (Aside from the inclusion of 0.) Eberhard shows in this blog post that given any compact group, with commuting probability greater than 0, there's a finite group with the same commuting probability.

2. For a^p, p an odd prime, the set is definitely not closed... at least not for finite groups. The point (p-1)/p is a limit point, but not in the set. However, it is in the set if we allow more general compact groups.

This raises the question of whether, for a given word, the set for compact groups might be equal to the closure of the set for finite groups. (Remember, in the case of [a,b], it's conjectured that the set for finite groups might be already closed, aside from 0.)

If the set for [a,b] is closed, it would have to be for a pretty crazy reason. Like, for [a,b], the limit point 1/2 is approached by 1/2 + 1/2²ⁿ⁺¹; the latter is realized by a group G which consists of the product of n copies of D₈, but with their centers identified. But 1/2 is instead realized by S₃. Yeah...

3. If you do want to consider compact groups, connected compact groups will get you nowhere. In a connected compact group, regardless of the word, you'll only ever get 0 or 1.

Unfortunately, that doesn't mean you can just pass to G modulo the connected component of the identity, and thereby only consider profinite groups; taking this quotient may change the probability. (E.g., consider if G is S¹⋊C₂, the generalized dihedral group over the circle, and your word is a²; the correct probability is 1/2, but if you mod out you'll get a probability of 1.)

Still, it does simplify things somewhat, as it does mean you only need consider each way of assigning a connected component to each variable, and seeing whether that gets you 0 or 1; you can then average that over the connected components.

4. A thing I didn't make clear last time -- I mentioned that the 5/8-gap argument for [a,b] is simple enough that it obviously applies to compact groups; I didn't mention that the same is obviously true of the 3/4-gap argument for a². (Unfortunately, the only 7/9-gap arguments I can find for a³ seem specific to finite groups.) But way more is true!

In their paper Groups with automorphisms inverting most elements, Liebeck and MacHale give a classification of finite groups with over half the elements being involutions; in particular, the probabilities you get this way are 1/2 + 1/(2n). So, that's our top ω for a², or ω+1 if you include 1/2 itself.

But what the authors don't note is that -- as far as I can tell -- their proofs work just as well (with only a little modification) for compact groups as well! Their classification goes through with only minimal modification, and you get the same probabilities! (Basically: In Type I*, A can now be infinite, although [A:C_A(x)] must still be finite, and in the other types, Z can now be infinite. If we're concerned with counting involutions, then for the other types that means E can now be infinite.)

The most significant thing to note about the necessary modifications, FWIW, is that for Theorem 3.5, which is pretty key, you don't need to assume that H is finite index; rather, you can conclude it! If H is infinite index, you get a contradiction. Similarly with 3.6; you don't need to assume that the q_i are finite, you can conclude it. Note that you'll need Zorn's Lemma to prove the existence of a maximal abelian subgroup.

Unfortunately, it's probably going to be really hard for anyone to get that into the literature...

5. If we're looking at top ω's, then for [a,b], this is known as well, plus a little more. In his paper What is the probability that two elements of a finite group commute?, David Rusin finds that, for finite groups, the top probabilities are 1/2 + 1/2²ⁿ⁺¹ (as mentioned above), then 1/2, then 7/16, then 11/27, then 2/5, then 25/64, then 3/8, then 5/14, then 11/32. So, that's the top ω+8.

Except... he doesn't actually include 5/14 (realized by D₁₄); I added that in. This doesn't seem to be a fundamental mistake, just a minor omission in case 2; he failed to realize that setting p=7, n=2 yields 5/14 > 11/32; he claimed that p=7 always yields something less than 11/32, which is false.

Dunno if anyone's corrected that in the literature; doubt it though.

Rusin's methods seem specific to finite groups, but by Eberhard's work above we know that doesn't matter!

6. Eberhard's proof that the probabilities for [a,b] are reverse-well-ordered really doesn't seem to imply that the order type is ω^ω, even though it seems like it should. :-/ (The main problem seems to be that the mapping p↦q need not be injective.)

There's more I could say, but I think this is a good place to stop.

-Harry

I posted a series of tweets about this the other day, but, y'know what, let's write this up a little more properly on DW.

Whenever I see a theorem or conjecture about a gap, between the smallest element of a set and the second-smallest, I ask if this is the start of a well-ordering. Obviously, this applies in reverse too; if there's a gap between the largest and second-largest, I ask if it's a reverse well-ordering.

(And remember, when asking about your set's order type, don't forget to ask if it's closed, or to consider the closure if it's not!)

What are some examples of this? Well, of course, there's all my theorems and/or conjectures on integer complexity and addition chains (and all sorts of variants), but I'll skip going into that for now, because I've discussed that at length here already.

There's the group theory problem I mentioned in my last entry. That's certainly a good one; the numerical data looks promising there.

Here are some others I can think of, off the top of my head:

The 1/3-2/3 conjecture: Given a finite poset P, define δ(P) to be the maximum over all pairs of distinct elements (x,y) of the minimum of the fraction of linearizations in which x<y and the fraction of linearizations in which y<x. (So, δ(P)=0 iff P is already a total order.) Then the 1/3-2/3 conjecture says that any P with δ(P)>0 in fact has δ(P)≥1/3. I.e., it's a gap conjecture. Could the values of δ be well-ordered?

(Maybe they can't! I don't know a lot about this sort of thing, maybe there's already a counterexample.)

(EDIT October 2021: Yup, they're not.)

What about various number-theoretic sets of real algebraic integers? Like, there's Lehmer's conjecture, which conjectures that there's a gap between 1 and the next-smallest Mahler measure. However, Mahler measures can't be well-ordered, because the include the Pisot numbers. That said, we can still ask about order type! In particular, the order type of the Pisot numbers is known, and it's a nifty one! Though it begins with an initial ω, it isn't a well-order after that. Still, like I said, it's a nifty order.

In fact, I'd conjecture that if you considered integer complexity or addition chains with subtraction allowed, and considered the defects arising from those, and then either took the closure or added whole numbers (because those should probably give the same set), that the result would be order-isomorphic to the Pisot numbers. But I'm not trying to prove that right now; I tried briefly and found that, total orders get much harder once they're not well-orders! Someday, I hope to get back to this, but certainly not now.

Anyway, they won't be well-ordered, but one could still ask about order types of (or closures of) Salem numbers or Mahler measures or Perron numbers.

(EDIT October 2021: No, not really; it turns out that each Pisot number is approached on boy sides by Salem numbers, and so Salem numbers are not well-ordered either; and Mahler measures and Perron numbers include the Salem and Pisot numbers and so are definitely not well-ordered either. Indeed, I already noted this for Mahler measures above...? This entry seems a bit inconsistent...)

Of course maybe you get nothing like that. Like in the theorem mentioned in this MathOverflow answer, where you start out with a gap, then another gap, but then you just get all real numbers past that point. What can I say, nothing's guaranteed.

Still, I think this is a question people should ask more often. So: What are other examples of sets of numbers with gap theorems, that we could ask if they're well-ordered? I'm sure I must have missed a ton.

-Harry

By "irresponsible speculation", I mean "speculation without having done my homework first", i.e., without having even tried to look at the existing literature beyond this paper or actually really tried anything at all.

So, Juan Arias de Reyna recently pointed out to me the following paper: Commuting Probabilities of Finite Groups, by Sean Eberhard.

EDIT DEC 1: The paper has been updated; the following refers to the original version of the paper. See the comments for discussion of the updated version.

So: If you have a finite group, you can consider the probability that a randomly chosen ordered pair of elements from it commutes. You could then consider the set of all probabilities obtained this way; this is some set of rational numbers between 0 and 1.

In this paper, Eberhard shows that this set is in fact reverse well-ordered! Its order type is of the form ω^α where 2≤α≤ω². (Though Juan Arias de Reyna points out that it's not too hard to find examples that show that in fact α≥ω, so the order type is at least ω^ω.) He also shows that all the limit points of this set are rational. I think it should be pretty obvious why I'm interested in this! (Even though I have no plans to actually study this, my hands are full as it is.)

Now for the irresponsible speculation:

1. Instead of just doing finite groups, one could generalize to compact groups; one can consider probabilities there as well. How would this affect the set? It would be really nice if this just gave you the closure of the probability set for finite groups! Though Arias de Reyna tells me it's conjectured that the finite group commuting probability set is closed in (0,1], so that would be saying that using general compact groups only gives you 0 in addition. (I mean, it certainly does give you 0 in addition!)

2. I'm reminded of some work of John Wiltshire-Gordon and Gene Kopp. They considered probabilities of randomly chosen elements from a compact group satisfying some general word; the case of commuting probabilities is the case where the word w is aba^-1b^-1. I wonder if the same phenomenon might be seen for other words.

Probably it would be best to first look at words in one variable. Obviously using w=a generates an ω if we stick to finite groups and an ω+1 if we allow general compact groups -- not ω^ω, but still well-ordered. As for a² or a³... well, I don't know, and I don't really intend to work on it as I said above, but it seems vaguely plausible and it's an interesting question!

So yeah that's basically all I have to say on the matter.

-Harry