Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$.

share|cite|improve this question
Do you have a reference you could give for the algorithm? Thanks, – Apollo Mar 9 '11 at 22:52
@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 '11 at 0:00
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 ab = m and ac =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 '11 at 20:56
@Gerhard: Dehornoy's book is perhaps the best reference for non set theorists. – Andrés Caicedo Mar 11 '11 at 21:08
@Gerhard:Dehornoy's book is good for both set theorists and non set theorists. It won an award. Also read Laver's original papers in Advances in Math. (90's, I think). They are well written. Mostly they concern the algebra of elementary embeddings, but there is something at the end about the Laver tables. – Justin Moore Mar 12 '11 at 1:25

1 Answer 1

up vote 5 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.