21
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ Do you have a reference you could give for the algorithm? Thanks, $\endgroup$
    – Apollo
    Mar 9 '11 at 22:52
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 10 '11 at 0:00
  • 1
    $\begingroup$ 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 $\endgroup$ Mar 11 '11 at 20:56
  • 1
    $\begingroup$ @Gerhard: Dehornoy's book is perhaps the best reference for non set theorists. $\endgroup$ Mar 11 '11 at 21:08
  • 2
    $\begingroup$ @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. $\endgroup$ Mar 12 '11 at 1:25
16
$\begingroup$

On Azimuth, on May 6, 2016, Joseph van Name wrote:

The largest classical Laver table computed is actually $A_{48}$. The 48th table was computed by Dougherty and the algorithm was originally described in Dougherty's paper here. With today's technology I could imagine that one could compute $A_{96}$ if one has access to a sufficiently powerful computer.

One can compute the classical Laver tables up to the 48th table on your computer here at my website.

$\endgroup$
5
  • $\begingroup$ What does it mean to "compute" $A_{48}$? The naive interpretation would be to write down all the entries explicitly, but $A_{48}$ has $2^{96}$ entries, which I think is about a billion times the world's data storage capacity. Maybe it just means that someone has code that computes the $(p,q)$ entry of $A_{48}$ in a "reasonable" amount of time? An even weaker interpretation would be that we're just trying to compute the period of the first row of $A_{48}$. $\endgroup$ Oct 28 '20 at 4:16
  • $\begingroup$ Reading the question more carefully, I see that the OP asks for the second interpretation I suggested above (computing the $(p,q)$ entry for given $p$ and $q$). In that case, my followup question is how one is able to determine an upper bound on the time and space needed to compute the worst-case entry (which is what would seem to be needed to substantiate a claim that $A_n$ "has been computed"). $\endgroup$ Oct 28 '20 at 13:19
  • $\begingroup$ @TimothyChow Computing the first row in $A_{n}$ is not that hard (though, I have no proof that my calculation is correct). In Hexadecimal, for $2^{8}<n\leq 3\cdot 2^{8}$, the first row of $A_{n}$ is $(2,2^{n}-2^{100}+C,2^{n}-FFF2,2^{n}-FF10,2^{n}-FF0E,2^{n}-FF04,2^{n}-FF02,2^{n}-100,2^{n}-FE,2^{n}-F4,2^{n}-F2,2^{n}-10,2^{n}-E,2^{n}-4,2^{n}-2,2^{n})$. This pattern will probably continue much further than $3\cdot 2^{8}$. Computing $A_{n}$ seems to be much harder than simply computing the first row. $\endgroup$ Apr 22 at 17:10
  • $\begingroup$ Randall's algorithm that produces an output $p*q$ in $A_{n}$ on input $(p,q)$ provably takes a very small amount of time on any input (this fact is clear by observing the algorithm). In fact, if one has the pre-computed data (in a compressed format) one can run this algorithm by hand for computing $A_{n}$ for $n\leq 3\cdot 2^{4}$. $\endgroup$ Apr 22 at 17:13
  • $\begingroup$ I have made it up to $A(3\cdot 4^4)$ (I am now working on $A(4^5)$), but I have no proof that my calculation is correct not can I formulate a succinct natural looking conjecture that implies that my calculations of $A(3\cdot 4^4)$ are free from any errors (my algorithm consisted of a lot of searching for and correcting non-distributivity combined with Dougherty's algorithm). $\endgroup$ Apr 22 at 22:07
8
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Well, in view of John Baez's answer, this answer now seems very outdated. :-) $\endgroup$
    – Todd Trimble
    May 7 '17 at 1:01
  • $\begingroup$ More likely, I think, is that people are using different definitions of what it means to "compute" a Laver table. $\endgroup$ Oct 28 '20 at 4:19
  • $\begingroup$ But storing the entire Laver table on a drive will take too much space. For $A_{7\cdot 4}$ and without compressing the mostly repeating data at all, you will need about half a millions terabytes of storage space. Anyone who computes the Laver tables beyond about $A_{2\cdot 7}$ uses some sort of compression, and Dougherty's algorithm is simply a more advanced form of compression. $\endgroup$ Apr 22 at 17:25
  • $\begingroup$ In any case, I agree that there are a few different notions of what it means to compute a Laver table that are practically applicable to Laver table computation. For example, if an algorithm returns the correct output on 99.9999% of all inputs, can we say that we have computed the Laver table (I say no because the 0.0001% of all inputs are the most important ones)? Does the algorithm have to come with a proof of its correctness? What if the proof requires strong large cardinal hypotheses? $\endgroup$ Apr 22 at 17:57
  • $\begingroup$ There are also issues about how to represent elements of $A_{n}$ and what it means to compute the fundamental operation of $A_{n}$. For example, in generalizations of Laver tables such as multigenic Laver tables and endomorphic Laver tables, one generally cannot fully compute the output $t(x,y,z)$ or $x*y$ but one can still compute arbitrary bits of information of $x*y$ and $t(x,y,z)$ (there just may be over a googol bits of information). $\endgroup$ Apr 22 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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