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

Improve this question
$\endgroup$
12
  • $\begingroup$ Do you have a reference you could give for the algorithm? Thanks, $\endgroup$
    – Apollo
    Commented Mar 9, 2011 at 22:52
  • 2
    $\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$
    – Justin Moore
    Commented Mar 10, 2011 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$
    – Gerhard Paseman
    Commented Mar 11, 2011 at 20:56
  • 1
    $\begingroup$ @Gerhard: Dehornoy's book is perhaps the best reference for non set theorists. $\endgroup$
    – Andrés E. Caicedo
    Commented Mar 11, 2011 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$
    – Justin Moore
    Commented Mar 12, 2011 at 1:25

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • 1
    $\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$
    – Timothy Chow
    Commented Oct 28, 2020 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$
    – Timothy Chow
    Commented Oct 28, 2020 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$
    – Joseph Van Name
    Commented Apr 22, 2021 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$
    – Joseph Van Name
    Commented Apr 22, 2021 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$
    – Joseph Van Name
    Commented Apr 22, 2021 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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Well, in view of John Baez's answer, this answer now seems very outdated. :-) $\endgroup$
    – Todd Trimble
    Commented May 7, 2017 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$
    – Timothy Chow
    Commented Oct 28, 2020 at 4:19
  • 1
    $\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$
    – Joseph Van Name
    Commented Apr 22, 2021 at 17:25
  • 1
    $\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$
    – Joseph Van Name
    Commented Apr 22, 2021 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$
    – Joseph Van Name
    Commented Apr 22, 2021 at 18:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .