Take the 2-minute tour ×
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|improve this question
    
Do you have a reference you could give for the algorithm? Thanks, –  Apollo Mar 9 '11 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 '11 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 '11 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 '11 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 '11 at 20:56

1 Answer 1

up vote 4 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|improve this answer

Your Answer

 
discard

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.