![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoySo, here's something that had bugged me for a long time. Jacobsthal multiplication is associative, but the proof of this is unsatisfying. Normally the way you prove an operation is associative is that you show that a multiary version of it makes sense; you don't just literally show that a(bc)=(ab)c, you show that abc makes sense on its own as a ternary thing (or with even more operands) and that a(bc) and (ab)c are both equal to this.
But for Jacobsthal multiplication, the only proof I knew of its associativity was to show that a×(b×c) was equal to (a×b)×c; I wasn't able to find an interpretation of a×b×c on its own.
Now, some years ago, Paolo Lipparini found an order-theoretic interpretation of the Jacobsthal product, but it wasn't one that led to an immediate proof of associativity. But based on an observation of Isa Vialard, I think I finally have one! It's a little awkward, but of course it is; it's Jacobsthal multiplication, after all.
Let's say A and B are WPOs, and let's consider the lexicographic product A·B (note: B here is the coordinate that's compared first). Then o(A)o(B) ≤ o(A·B) ≤ o(A)×o(B).
But, actually, we can say more. Suppose B has k maximal elements, so that o(B) has finite part greater than or equal to k. Then, Vialard noted, we have o(A·B) = o(A)·(o(B)-k) + o(B)×k.
In particular, if o(B) has finite part equal to its number of maximal elements, then o(A·B)=o(A)×o(B). (In fact, as long as A has multiple distinct powers of ω in its Cantor normal form, the converse also holds.)
Btw, the finite part of o(B) is equal to the number of elements of B that have only finitely many elements above them. We could call such elements "almost maximal". So B satisfies this condition iff every almost maximal element is maximal.
Anyway, let's call a WPO that satisfies this condition "flat-topped". Note that flat-topped WPOs are closed under disjoint union, under Cartesian product, and, yes, under lexicographic product! So we can interpret α×β as the type of A·B for any flat-topped A,B with o(A)=α and o(B)=β; and we can do similarly with α×β×γ, etc. So this does it! We've interpreted multiary × and proved associativity nicely. Hooray!
EDIT 5/5: Actually, on writing to Lipparini about this, he pointed out to me that another observation of Vialard provides an even easier answer, namely, without needing the flat-topped condition, one has w(A·B)=w(A)×w(B), where w is width. I hadn't noticed this because, well, I've never really paid a lot of attention to widths, tbh.
But for Jacobsthal multiplication, the only proof I knew of its associativity was to show that a×(b×c) was equal to (a×b)×c; I wasn't able to find an interpretation of a×b×c on its own.
Now, some years ago, Paolo Lipparini found an order-theoretic interpretation of the Jacobsthal product, but it wasn't one that led to an immediate proof of associativity. But based on an observation of Isa Vialard, I think I finally have one! It's a little awkward, but of course it is; it's Jacobsthal multiplication, after all.
Let's say A and B are WPOs, and let's consider the lexicographic product A·B (note: B here is the coordinate that's compared first). Then o(A)o(B) ≤ o(A·B) ≤ o(A)×o(B).
But, actually, we can say more. Suppose B has k maximal elements, so that o(B) has finite part greater than or equal to k. Then, Vialard noted, we have o(A·B) = o(A)·(o(B)-k) + o(B)×k.
In particular, if o(B) has finite part equal to its number of maximal elements, then o(A·B)=o(A)×o(B). (In fact, as long as A has multiple distinct powers of ω in its Cantor normal form, the converse also holds.)
Btw, the finite part of o(B) is equal to the number of elements of B that have only finitely many elements above them. We could call such elements "almost maximal". So B satisfies this condition iff every almost maximal element is maximal.
Anyway, let's call a WPO that satisfies this condition "flat-topped". Note that flat-topped WPOs are closed under disjoint union, under Cartesian product, and, yes, under lexicographic product! So we can interpret α×β as the type of A·B for any flat-topped A,B with o(A)=α and o(B)=β; and we can do similarly with α×β×γ, etc. So this does it! We've interpreted multiary × and proved associativity nicely. Hooray!
EDIT 5/5: Actually, on writing to Lipparini about this, he pointed out to me that another observation of Vialard provides an even easier answer, namely, without needing the flat-topped condition, one has w(A·B)=w(A)×w(B), where w is width. I hadn't noticed this because, well, I've never really paid a lot of attention to widths, tbh.
no subject
Date: 2025-04-29 12:22 am (UTC)no subject
Date: 2025-04-29 03:17 am (UTC)In any case I wrote an email to Lipparini and Vialard with essentially the content of this entry, so they know about it at least...
I mean I've got other things where the proof is just in private correspondence, I can think of at least one formula where I sent a proof sketch to Alakh Chopra, and I don't think I wrote that one down here...