Welcome to MathOverflow

Question

12

3

Richard Laver proved that there is a unique binary operation $*$ on $\{1,\ldots,2^n\}$ which satisfies $$a*1 \equiv a+1 \mod 2^n$$ $$a* (b* c) = (a* b) * (a * c).$$ This is the $n$th Laver table $(A_n,*)$.

There is an algorithm for computing $a * b$ in $A_n$, but in general (and especially for small values of $a$), this requires one to compute much of the rest of $A_n$. What is the largest value for $n$ for which someone can, in a modest amount of time, compute an arbitrary entry in $A_n$? I am able to compute entries in $A_{27}$.

I should note that the map which sends $a$ to $a\ \mathrm{mod}\ 2^m$ defines a homomorphism from $A_n$ to $A_m$ for $m < n$ and hence the problem becomes strictly harder for larger $n$.

Edit: I have actually been able to compute $A_{28}$, not just $A_{27}$.

edited Mar 12 2011 at 17:27

asked Mar 9 2011 at 18:48

Justin Moore
3,051●11●22

Do you have a reference you could give for the algorithm? Thanks, – Apollo Mar 9 2011 at 22:52

1

@Apollo: The one I used to get to $A_{27}$ is based on ideas in Dehornoy's book "Braids and self distributivity" where he discusses the function $\theta$. The basic idea for computing in $A_n$ is given by the following identities: $a*k = (a+1)_{[k+1]}$ for $a < 2^n$ and $2^n * k = k$. Here $a_{[k]}$ is the $k$th left associated power of $a$. This allows you to start at the bottom of the table and work up. Implementing this directly allows me to get to $A_{19}$ (there are problems both with time and memory for $A_{20}$). Contact me offlist for code, if you like. – Justin Moore Mar 10 2011 at 0:00

Thanks. I'd be surprised if there was a faster method (based on the need (maybe) for very powerful large cardinals (at least more than PRA) to prove facts about the periodicity of the top row) to compute arbitrary entries... – Apollo Mar 10 2011 at 23:42

The speed of the algorithm is not so bad, actually, when one considers that $A_n$ has $2^n$ rows. I don't expect to get to $A_{1000}$, but I'm curious whether there are tricks that allow for a single computation in, say, $A_{40}$ on a desktop computer with a typical amount of memory and 24 hours. The naive algorithm makes single computations very fast (just a consultation to memory) but there is a large up front price. The revised algorithm makes single computations a little more expense, but with less up front. I'm asking for even more trade off of this sort. – Justin Moore Mar 11 2011 at 2:18

1

It might be that you can run the distribution "backwards". Do you know how to find a,b,and c, given m and n, such that a*b = m and a*c =n ? Also, can you give a reference for Laver's result that left self-distributive * is unique up to isomorphism? Gerhard "Ask Me About System Design" Paseman, 2011.03.11 – Gerhard Paseman Mar 11 2011 at 20:56

show 6 more comments

Justin Moore · Accepted Answer · 2011-03-24 19:52:01Z UTC

3

I've been in contact with Patrick Dehornoy and Ales Drapal and both thought that $A_{28}$ is likely the current record for a Laver table computation.

answered Mar 24 2011 at 19:52

Justin Moore
3,051●11●22

What is the largest Laver table which has been computed?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.