Featured

## A technique that could be used to construct and improve proof-of-work problems.

In this post, I am going to talk about a trick using hash functions that takes computational problems and makes them suited or better suited to use as cryptocurrency proof-of-work (POW) problems. Yes, this trick can be applied to any potential cryptocurrency POW problem.

Review and references

If you are already familiar with cryptocurrencies and cryptocurrency POW problems, then feel free to skip this section. If you are not familiar with cryptocurrencies and their POW problems, then please read Satoshi Nakamoto’s paper Bitcoin. For a more in-depth study of cryptocurrencies, I recommend the coursera course Bitcoin and Cryptocurrency Technologies (there is also a book Bitcoin and Cryptocurrency Technologies that I recommend).

If you have not read Satoshi Nakamoto’s paper and don’t plan to right now, then just take note that many cryptocurrencies are distributed by solving computational problems which are known as proof-of-work problems; the process of solving these problems is known as mining.

Requirements for cryptocurrency POW problems

Consider the following characteristics which are desirable or required in POW problems.

1. (Verifiable but intractible) The problem must be difficult to solve yet easy to verify.
2. (Fine tunability) The difficulty of the problem must be finely tunable so that coins are distributed at a constant rate.
3. (Automatic generation) Instances of the problem must be generated automatically and efficiently.
4. (Solution tied to block and solver) The solutions must depend on the block and the solver of the block so that a valid solution for Alice will no longer be a valid solution for Bob.
5. (Usefulness) The solution to the problem together with the process of obtaining the solution should have enough value outside the cryptocurrency to justify the resources used to solve the problem.

Let me now add a few more desired characteristics for proof-of-work problems.

1. (Endless problems) There should be an unlimited amount of problems to work on so that the POW will not quickly expire.
2. (Unbreakability) The problem should be cryptographically secure in the sense that it should be thought to be impossible for an entity to have a secret algorithm that solves the POW problem at a much faster rate than everyone else can. If an entity has a secret algorithm, then that entity could launch a 51 percent attack, and such a secret algorithm will produce an unfair wealth distribution.
3. (Progress-freeness and pre-computation resistance) Suppose that Alice and Bob are working on the POW problem and they both have an equal amount of computational power. If Alice has not solved the problem but Alice has started working on the problem five minutes ago, then Alice should have no advantage over Bob in solving the POW problem. Furthermore, Alice should have no way of computing the solutions in advance. The chance of someone solving the mining problem needs to be directly proportional to her computational power.

The multi-algorithm approach

So one way to alleviate the issues that arise with useful POW problems is to use multiple POW problems so that the cryptocurrency does not fall apart in the case that there is a bad POW problem or in the case that a POW problem becomes bad. Characteristics 1-4 and i-iii are required for all cryptocurrencies with a single POW problem, but characteristics i-iii though desired are not required for cryptocurrencies with many POW problems.

There may be some POW problems which are useful up to a point but where the practical value of these problems satisfies the law of diminishing returns, but with a multi-algorithm POW, certain problems may be retired from the problem schedule when their practical value is no longer worth the computational effort put into solving them. Multiple algorithm POW problems also help alleviate the initial distribution problem for cryptocurrencies since multiple algorithms will distribute a new cryptocurrency more evenly and fairly than a single algorithm could.

A POW scheme consisting of many algorithms is much more complex than a single algorithm scheme and it will take much more work to develop a multi-algorithm POW scheme than a single algorithm POW (in a multi-algorithm POW scheme, one also needs to develop techniques for removing broken or outdated problems; for example, in a multi-algorithm POW, one will need to have a system that automatically removes a broken problem once someone submits a formal proof that the POW problem can be solved in polynomial time).

The solution lottery technique

The solution lottery technique is a tool that one can use to make a POW problem obtain several of the advantages of hash based POW problems without any of their disadvantages. Stated informally, the solution lottery technique (SLT) is a technique where one increases the difficulty of a POW problem without changing any other characteristic of the POW problem simply by only accepting solutions with exceptionally low hashes. While the SLT uses hash functions, the SLT is designed so that a miner seldomly calls upon a hash function in order to solve the POW problems. Therefore, miners will focus their energy on solving the main problem rather than computing hashes.

Let me now state how the SLT is applied to a typical POW problem. Suppose that $D$ is a set of ordered pairs. Suppose that $H$ is a cryptographic hash function and $\text{Data}(k,x)$ is a piece of information that can be easily obtained when after one verifies that $(k,x)\in D$ but which cannot be obtained if one does not verify whether $(k,x)\in D$ or not.

Problem A without SLT: The objective of Problem A is to find an input $x$ and a suitable hash $k$ so that $(k,x)\in D$.

Problem A with SLT: The objective of Problem A with SLT is to find an input $x$ along with a suitable hash $k$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$.
For Problem A with or without the SLT, the data $k$ may be reused many times, so one does not have to compute very many hashes $k$ but one has to determine whether $(k,x)\in D$ many times. Similarly, one only has to compute the hash $H(k||x||\text{Data}(k,x))$ if $(k,x)\in D$. Since hash functions are computed seldomly with the SLT, miners will devote almost all of their resources into finding pairs $(k,x)\in D$ rather than in computing hashes, and hence the POW problems will retain their characteristics such as usefulness or ASIC resistance with or without the SLT. The input $\text{Data}(k,x)$ is necessary for the SLT to opeate correctly since otherwise a miner would solve Problem A with SLT simply by first computing $H(k||x)$ and if $H(k||x) < C$, then the miner would verify whether $(k,x)\in D$ (and hence the miner would most of the resources computing hashes rather than determinine whether $(k,x)\in D$).
Let us now look at a few ways that the SLT can improve cryptocurrency POW problems.

Fine-tunability: It may be difficult to fine tune the difficulty of a certain POW problem. However, with the SLT, it is much easier to fine tune the difficulty of the POW problem since the software simply has to adjust the parameter $C$ in order to make the problem easier or more difficult.

Smoothly tuning coarse parameters with SLT: In some POW problems, changing the set $D$ could change the difficulty of the POW problem in an unpredictable manner. The SLT could help smoothly change the set $D$ in these cases. Suppose that the POW problem at block $n$ is to find a hash $k$ and data $x$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$. Then the POW starting in block $n+1$ would be to find a hash $k$ and data $x$ so that ($(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$) or ($(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$) where $C'$ is chosen so that it is easier to find $k,x$ so that $(k,x)\in D$ and $H(k||x||\text{Data}(k,x)) < C$ than it is to find $k,x$ so that $(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$. Then the constant $C'$ will gradually increase. At the same time, the constant $C$ will decrease so that the difficulty of the POW problem remains constant until $C=0$ and when $C=0$, the POW problem will simply be to find $k,x$ so that $(k,x)\in D'$ and $H(k||x||\text{Data}(k,x)) < C'$.
Security boost: The SLT can also take very low security POW problems and make these problems viable as cryptocurrency POW problems even though their security level without the SLT is very low.

Progress freeness: The SLT could also be used to take a POW problem which is not progress free and make it into a problem which is progress free. For example, suppose that one wants to use a POW problem that incentivizes the development of computers that can perform tasks at higher and higher frequencies (I am currently as of January of 2018 not endorsing nor opposing this kind of POW problem as a useful POW problem). Then the POW problem should be a problem which can be easily verified but where the most efficient algorithm for solving the POW problem requires one to perform N steps in a sequence so that the person with the computer that runs at the highest frequency always wins the block reward. This POW problem without the SLT however is a very bad problem for cryptocurrencies since the entity with the fastest processor will always win; this problem is not progress free. However, the SLT can take this problem and turn it into a progress free problem which still incentivizes people to develop faster computers. Suppose that $N$-step version of this POW problem without the SLT is to find a pair $(k,x)$ such that $(k,x)\in D_{N}$. Then the goal of this POW problem with the SLT is to find a pair $(k,x)$ where $k$ is a hash and $x$ is data so that $(k,x)\in D_{N}$ and $H(k||x||\text{Data}(k,x)) Suppose that the problem of finding a suitable hash$k$along with data$x$so that$(k,x)\in D$has only 32 bits of security. Furthermore, suppose that any increase in the security level of the cryptocurrency POW problem will make the verification of the POW problem too inefficient to use in practice (useful POW problems tend to take a much longer time to validate than useless POW problems). Then while the problem of finding some$(k,x)\in D$will not be a viable POW problem since its difficulty cannot be increased beyond 32 bits of security, the problem of finding some$(k,x)\in D$where$H(k||x||\text{Data}(k,x)) < C$could be made arbitrarily difficult. The lost solution problem for the SLT In a useful POW problem that employs the SLT where the solutions to the problems themselves are of a practical use, someone needs to keep a record of the solutions$(k,x)$where$(k,x)\in D$but$H(k||x||\text{Data}(k,x)) \geq C$which are thrown out using the solution lottery technique; the fact that the SLT throws out useful solutions to a POW problem shall be called the lost solution problem (LSP) for this post. The solution thrown out by the SLT do not need to be posted on the blockchain nor should they be put on the blockchain, but they need to be publicly available. For useful POW problems where the process of obtaining a solution rather than the solution itself is what is important, the LSP is not an issue, but it is an issue to useful POW problems where the solution itself is of interest. The most basic solution to the LSP is for the miners to post their inputs$(k,x)$where$k$is an appropriate hash and where$(k,x)\in D$but$H(k||x||\text{Data}(k,x))\geq C$or where$(k,x)$is an otherwise good solution simply as a matter of courtesy. Miners would probably be willing to post these solutions as a matter of courtesy since it does not take very much work to post these solutions. If a miner is discourteous and does not post his solutions, then the POW will not be as useful as it could be, but the cryptocurrency will not suffer from any security weaknesses, so discourteous miners can only do a limited amount of harm against the reputation of the cryptocurrency. Courtesy may not be a strong enough incentive for miners to compel them to post their solutions since courtesy does not give miners any financial incentive. Furthermore, if the miners have an incentive to keep their solutions as a secret, they will not be willing to post their solutions simply out of courtesy. Therefore, in order to solve the SLT problem by incentivizing miners to post their solutions, the cryptocurrency protocol should require all miners to accept the blockchain fork backed up with the highest number of posted solutions$(k,x)$such that$(k,x)\in D$. Since the cryptocurrency miners do not want their blocks to become orphan blocks, they will post all of their solutions$(k,x)$such that$(k,x)\in D$and they will only mine on the fork with the most solutions$(k,x)$such that$(k,x)\in D$. The miners may also be encouraged to boycott all chains if they suspect that the miner has not posted all of his solutions and such a boycott against suspected bad miners may be incorporated into the cryptocurrency protocol (for a simplistic example of such a protocol, the protocol could be to always accept a block from an established miner over a block from a new miner (or someone pretending to be a new miner) if the new miner does not post at least the average number of solutions per block and to outright reject all blocks from established miners if they are suspected of intentionally withholding more than 10 percent of solutions with a 3 sigma confidence). Conclusion It will probably be very difficult to make useful POW problems if one just used a single algorithm per cryptocurrency that does not employ the SLT. However, if one uses many kinds of POW problems in a cryptocurrency and if one employs the SLT in many of these problems, then constructing a new useful POW problem is no longer as difficult. With multiple POW problems and with the SLT a useful POW problem only needs to be useful, difficult to solve, easy to verify, automatically generated, and the solutions need to be tied to the solver and the blockchain. Since the problem of constructing useful POW problems is a tractible applied mathematics research problem with great economic benefit, it will be a good idea for mathematicians and other experts to work on developing such problems. Featured ## A warning against proof-of-stake cryptocurrencies and against altcoins I am making this post since recently several altcoins which are not mined by proof-of-work problems have gained a very high market cap and because I see a major downside to these non-minable coins. Furthermore, the newer cryptocurrencies are non-minable, and people should be very wary of non-minable coins. To make things short, there are two ways in which transactions are verified in a cryptocurrency without the use of a central authority, namely proof-of-work (POW) and proof-of-stake (POS). With POW, people gain the right to validate cryptocurrency transactions by solving a computationally difficult problem (the process of solving this problem is known as “mining”), and the people are rewarded for solving these POW problems and validating the transactions with newly minted coins and with transaction fees. The difficulty of this problem is automatically adjusted so that the average time it takes to solve the problem remains constant. POS does away with the need to solve such a computationally difficult problem. With POS, the cryptocurrency rewards an entity the right to validate transactions according to how much of the cryptocurrency the entity possesses. POS should be thought of as a cheap alternative to POW, and by cheap I mean that POS is of low quality rather than inexpensive as a result of a community unwilling to put the effort into making a good POW problem and solving these problems. In this post, I am not going to discuss whether POS is suitable as a mechanism for validating transactions in the long run since I am currently far from the best person to write about such an issue (this post will therefore not be very technical). However, I am going to make the case that one needs POW in order to fairly initially distribute a cryptocurrency and that POS is insufficient for initially distributing the cryptocurrency. Most of the ideas in this post are not original ideas and they have been broadcasted elsewhere by other people. We observe that recently POS coins have been gaining a high market cap while the POW coins have not received such great gains. Furthermore, the newer cryptocurrencies with a high market cap are all POS coins as opposed to POW coins. I also want to make it clear that my criticism of POS is only limited to the initial distribution of the coin. So there is about 800 billion dollars in cryptocurrencies floating around as of 1/06/2017. With such a high market cap, we must now ask the question as to whether the people who own these cryptocurrencies have truly earned the coins that they have. A related question one should also ask is whether the coins have been distributed evenly and fairly. If these cryptocurrencies have not been distributed fairly, we must then find and employ the best strategy for fairly distributing these new coins. One possible solution to the initial distribution problem without resorting to POW is to give every single person in a certain region of the world. For example, in the cryptocurrency Auroracoin, an equal number of coins were given to each citizen of Iceland. This solution however has its problems. Cryptocurrencies distributed like Auroracoin have a major competitive disadvantage since such cryptocurrencies are limited to certain regions of the world, and as a result any coin similar to Auroracoin will probably have a low market cap. By limiting a cryptocurrency to a certain part of the world, such a cryptocurrency is not that much different from fiat currencies since cryptocurrencies should not be limited to certain groups of people. Fairly distributing a cryptocurrency to every citizen of a nation also has some logistic disadvantages since during the initial distribution, not every citizen would accept such a cryptocurrency and there is no guarantee that the citizens of that nation would accept such a cryptocurrency in the future. It is difficult to distribute a currency if the people do not want that new currency. Auroracoin’s solution to the initial distribution problem is the best possible solution to this problem without resorting to POW. Other solutions to the initial distribution problem in a POS system are very unfair and/or logistical nightmares. For example, if the coin has been initially distributed through an ICO (initial coin offering), then one’s wealth is determined solely by how much one gives to a central non-government organization. While this method of initial distribution works well for distributing stocks, it is not a fair way to distribute new cryptocurrencies because it is necessary for cryptocurrencies to be distributed as evenly as possible. There is no way to evenly and fairly distribute a new cryptocurrency solely through a high risk ICO since ICOs distribute coins based on how much people are willing to risk their money at cryptocurrency projects which have not been launched yet and which have not stood the test of time. ICOs are unnecessary to develop a new cryptocurrency since new cryptocurrencies could be launched simply by cutting and pasting, and the development of the cryptocurrency could be funded by a sort of treasury system similar to that of the cryptocurrency Dash. Let us also observe that many ICOs are complete scams. If a cryptocurrency must use an ICO, then only a small portion of the total number of coins should be distributed through that ICO and the rest of the coins should be distributed by using POW (Ethereum has combined ICO with POW for its initial distribution and that is fine). Would you like your national currency to be initially distributed based on how much money one gives to someone who may or may not be a scam artist? Or would you instead like your national currency to be distributed to people according to how much they work for it? Many people say that POS is cheaper than POW. But the damage to an economy caused by POS because all of the wealth has been distributed to the wrong people will be much more expensive than POW could ever be. Even though I consider POW to be a fair way to initial distribute a new cryptocurrency, one still has to be careful with POW coins since POW still could have major initial distribution problems if it is not done correctly. The initial distribution mining period needs to be long enough for the cryptocurrency to be fairly distributed among the users. If most of the coins are given to the early adopters and the cryptocurrency gains a high market cap only after most of the coins have been distributed, then a few people will have an excessive amount of wealth that they have not worked for and which they have not earned. In my opinion, the initial distribution period should last at least a decade for a fair distribution, and Bitcoin’s halving period of four years is too short for newer cryptocurrencies (of course even a one year initial distribution period using POW is much better than any ICO since at least with a POW people are investing in a cryptocurrency that has been launched). With what I had said, you may be tempted to cry foul at the initial distribution of Bitcoin, but I would not consider the initial distribution of Bitcoin to be unfair in any way. The early investors into Bitcoin became rich, but they also provided a great deal of value to the cryptocurrency community. The early investors into Bitcoin were the people who made the notion of a cryptocurrency what it is today, and the early investors of Bitcoin were necessary in order for the market caps of cryptocurrencies to grow to where they are today. However, one cannot make the argument that if someone becomes rich from being an early adopter of an altcoin, then that person has truly earned his money. An early adopter of an altcoin has not helped make cryptocurrencies become mainstream so it is unfair for such an entity to have an enormous amount of wealth. The early adopters of Bitcoin also deserve their wealth because they decided to get Bitcoin early because they truly understood either how Bitcoin works or how Bitcoin is important; the same cannot be said of the early adopters of altcoins. Since Bitcoin early adopters truly deserve their wealth because they believed in the system and because they helped bring cryptocurrencies into the mainstream, one could argue that Bitcoin is the most fairly distributed cryptocurrency. The cryptocurrency must also choose a useful POW problem that has real-world applications outside of the cryptocurrency community. For example, the POW problem for Bitcoin is to find a SHA256 hash$k$so that$k < C$where$C$is a number that changes every 2016 blocks; the hashes$k$with$k < C$have no purpose outside of the cryptocurrency itself, nor is the process of mining bitcoins of much value. Bitcoin mining therefore becomes a nearly useless job whose only purpose outside the cryptocurrency is to keep people employed doing a nearly useless job. A useful POW problem cannot be seen as wasteful in any way since the work needed to solve that problem will be used to advance science, technology, or mathematics. If a person gets rich from solving useless POW problems from cryptocurrencies, then that person has not done work to improve anyone’s lives. It is not fair for someone to get rich off a cryptocurrency by performing a nearly useless job. It is definitely not fair for all coins in a cryptocurrency to arise from performing a nearly useless job. We need a useful POW problem also because people should get paid for performing useful jobs rather than useless jobs. Unfortunately, the cryptocurrencies launched so far have not successfully employed useful POW problems, so mathematicians still have a lot of work to do. Now, it is not solely up to the cryptocurrency authorities to solve the initial distribution problem, but the people can also help solve the initial distribution problem by investing in a diversified set of cryptocurrencies. One will incur a much lower risk by investing in a diverse set of cryptocurrencies at least until stable cryptocurrencies emerge. While useful POWs whose mining period elapses over several years will help fairly distribute cryptocurrencies, the people need to also do their part by investing in a diverse set of cryptocurrencies and creating systems that will allow others to more easily invest in a diverse set of cryptocurrencies. I should mention that POW and POS are not the only ways of initially distributing new cryptocurrencies since one could use proof-of-burn in order to transfer coins from an existing cryptocurrency to a new cryptocurrency. However, proof-of-burn is a rarely used consensus and initial distribution mechanism, so proof-of-burn currently should not be considered to be a substitute for proof-of-work or proof-of-stake. Let me know your thoughts about the cryptocurrency initial distribution problem. Extraneous remarks: If you want to know if a cryptocurrency is a proof-of-work coin or a proof-of-stake coin, go to https://coinmarketcap.com/ and look for the cryptocurrency; if you see an asterisk next to the cryptocurrency, that means that the coin is not minable and hence it is not a proof-of-work coin. One may claim that Auroracoin’s solution to the initial distribution problem is an act of socialism, but Auroracoin is not quite as socialistic as one might think at first glance. First of all, the people of Iceland have the choice of accepting Auroracoin as a legitimate currency or not, and since the people may choose to accept Auroracoin, Auroracoin should be considered as a part of a capitalistic society even though the initial distribution of Auroracoin is socialistic. Second of all, Auroracoin is only a socialistic in its initial distribution, so the socialistic distribution of Auroracoin will only dominate the cryptocurrency in the short-term. Finally, the socialistic initial distribution of Auroracoin is not intended to spread socialism but instead to solve the initial distribution problem. While I have criticized POS coins in this post, we must give the POS coins some credit for testing POS in practice so that people better understand its advantages and disadvantages. Featured ## A POW problem that can incentivize the energy efficient CNOT computer. So in my previous posts, I have talked about a cryptocurrency POW which I call R5 which will incentivize the construction of the reversible computer. The POW R5 however does not incentivize the early stages of reversible computation when it is difficult to construct energy efficient implementations of reversible gates. My solution to this problem is to develop a new cryptocurrency POW problem which I shall temporarily call Slimeland (I will think of a better name in the future, I promise). Incentivizing CNOT circuits instead of full-blown reversible circuits So recall that the CNOT gate is the logic gate$(x,y)\mapsto(x,x\oplus y)$. Since the CNOT gate is a linear transformation, the CNOT gate is not universal for reversible computation. The goal of Slimeland is to incentivize the construction of a circuit composed mainly of CNOT gates. There are several reasons why a CNOT gate circuit should be easier to construct than a full-blown reversible circuit including the following: 1. The CNOT gate is not universal for reversible computation. 2. The CNOT gate acts on only two bits while universal reversible gates must act on at least 3 bits. 3. The CNOT gate is linear. It is therefore safe to assume that the research and development costs for developing an energy efficient reversible circuit composed almost exclusively of CNOT gates will be far less than that of developing a reversible circuit composed mainly of universal gates. Therefore, if one can construct a cryptocurrency POW problem that will incentivize the development of the energy reversible circuit composed mainly of CNOT gates, then energy efficient circuits that efficiently compute the CNOT gate will be developed very soon in order to quickly receive a return on investment. Problem description Suppose that$f$is a suitable function. Suppose that$m,n$are natural numbers and$D$is an adjustable real number. Then he objective of the POW problem Slimeland is to find a$m$bit hash$k$along with an$n$bit string$x$so that$f(k||x)<2^{m+n}/D$. The function$f$should be composed mostly of CNOT gates. However, since the CNOT gate is linear, the function$f$cannot be composed exclusively of CNOT gates. 1. The most efficient circuit for computing the function$f$should consist solely of reversible gates without resorting to any ancilla or garbage bits. 2. The circuit for the function$f$should have a very high ratio of CNOT gates to non-linear gates in order to incentivize the construction of energy circuits composed mainly of CNOT gates. 3. The circuit for the function$f$needs to have enough non-linear gates to be cryptographically secure. 4. The function$f$should be as efficiently verifiable as possible. Properties 2-4 are at odds with each other, so it is a challenge to construct a function$f$that satisfies these conditions. The internal testing technique So the internal testing technique is method that I have come up with that can ensure that a cryptocurrency remains secure even if the cryptographic security of its POW problem is questionable. Suppose that a cryptocurrency has Problem A as its POW problem. Suppose furthermore that Problem A has an adjustable level of security (the level security of symmetric cryptosystems can be adjusted simply by adding more rounds). Then a cryptocurrency applying the internal testing technique for Problem A will have two POW problems which we shall denote by Problem$A_{test}$and Problem$A_{secure}$. Suppose that$N$is an adjustable natural number. Then$A_{test}$will have security level$N$while$A_{secure}$will have security level$3N$. Problem$A_{test}$will also be weakened in other ways. While the security level for$A_{test}$is decreased, the difficulty of$A_{test}$will be increased (for example to 1000 times the difficulty of$A_{secure}$) so that it is not feasible for a miner to solve Problem$A_{test}$using a brute force attack, and a miner must therefore solve$A_{test}$by partially breaking its security. If$A_{test}$is solved too often (for example, if$A_{test}$is solved for more than one percent of all blocks), then the underlying cryptocurrency will automatically increment the number$N$by one. As a security measure, the blocks for which$A_{test}$is solved cannot be too close together. Using the internal testing technique, the security of the underlying cryptocurrency POW problem will automatically be adjusted in case of any advancement in cryptanalytic techniques. By using the internal testing technique, Slimeland can remain secure even though the circuit used that solves Slimeland is mostly composed of the linear CNOT gates. Featured ## Security report for R5, the POW problem for Nebula. Hello everyone, Attached is the security report for R5, the POW problem for Nebula. I had to give an account on the security of Nebula since Nebula employs new kinds of cryptosystems which have not been implemented in practice so far. Keep in mind that it is ill-advised to employ a new symmetric cryptosystem in practice as soon as it is developed. It typically takes a couple of years for people to thoroughly investigate a new symmetric cryptosystem before it is employed in practice, and for public key cryptosystems it takes much longer. However, by the nature of R5, a security report that should be sufficient to ensure the security of R5 since it is much more difficult for something to go wrong with R5 that it is for something to go wrong with a symmetric cryptosystem such as a hash function. I will at one point release an updated version of the security report for R5 since there is information about R5 which I do not want to reveal publicly at the moment (I apologize for my violation of Kerckhoffs’s principle.Don’t worry. All information about R5 will be openly available soon enough though. And my violation for Kerckoff’s principle are not for cryptographic security reasons but instead for logistical reasons). Featured ## A lesson to be learned from the recent cryptocurrency dip Today in the news, you can find countless articles which tell us that China has just banned ICO’s (an ICO, an initial coin offering, is the way that many people fund new cryptocurrency endeavors. In an ICO, investors buy new cryptocurrency tokens since they believe that the upcoming cryptocurrency will eventually become valuable). As a result on this ban on ICOs, the total market cap for all cryptocurrencies has fallen from an all-time high of 180 billion USD (on September 2, 2:00 UTC) to 138 billion USD at the time of writing. The price of a bitcoin was almost 5000 USD but now after the dip, a bitcoin now costs 4100 USD. One government action has the power to sway the value of cryptocurrencies so that they lose 20-25 percent of their value overnight. It is therefore necessary for those who value cryptocurrencies to make a great effort to improve the reputation of cryptocurrencies so that the world’s governments accept these cryptocurrencies. Not only are governments able to harm cryptocurrencies by passing laws against them, but these governments also have the power to launch attacks against cryptocurrencies and thus break the security of these cryptocurrencies and likely destroy these cryptocurrencies. Cryptocurrencies currently have a mixed reputation. Since it is possible for cryptocurrencies to disrupt global economies, replace any national currency, and cause other changes that people will not want to accept, governments may want to place restrictions and regulations upon cryptocurrencies to keep them under control. Today, cryptocurrencies are not backed by gold or any other precious metals, and the process of mining new coins does not provide any product or service of value outside the cryptocurrency except for pollution. Since cryptocurrencies are not produced by providing useful products or useful services and cannot be traded for precious metals, cryptocurrencies do not have nearly as many advantages over fiat currencies as they could have, but they could improve their reputation simply by making mining useful. It is therefore necessary for cryptocurrencies to employ useful proof-of-work problems which provide benefits outside the cryptocurrency. My solution in my upcoming cryptocurrency Nebula is to use a proof-of-work problem R5 so that in order to efficiently solve R5, one will need to construct a reversible computer and advance computational technology. The proof-of-work R5 is nearly as efficient as a cryptographic hash function, so R5 does not suffer from negative characteristics which are present in other so-called useful proof-of-work problems. R5 is also much more useful than all other proof-of-work problems proposed so far since one cannot question the future value of reversible computation. Since Nebula will advance technology, the people and hence the governments will view cryptocurrencies more favorably (at least Nebula anyways). As a consequence, governments will be less willing to place restrictions on cryptocurrencies if some of those cryptocurrencies advance science in positive ways. The only way for cryptocurrencies to last among a skeptical population is if people only use a cryptocurrency which employs a good useful proof-of-work problem. If we keep on using the same cryptocurrencies with the same proof-of-work problems, then people will rightfully see these cryptocurrencies as useless and wasteful. I have hope that eventually, people will only use the cryptocurrencies with useful proof-of-work problems since people will rightfully perceive these new cryptocurrencies as being much more valuable than our current cryptocurrencies. Unfortunately, it is too late for Bitcoin to start using a useful proof-of-work problem since most bitcoins have already been mined and switching a proof-of-work will require a destructive hard-fork, so one will need to start using new altcoins instead. Fortunately, in recent months, altcoins have come to dominate over half of the total market cap of all cryptocurrencies, and new altcoins are constantly being created. In a few years, the dominant cryptocurrencies will likely be ones which have not been launched yet but which will employ new innovations. Nebula is one of these cryptocurrencies with a new innovation that challenges the status quo in the cryptocurrency community. A message to the skeptics There have been many people in the pure mathematics community who have denied the possibility that reversible computing may be more energy efficient than conventional (by conventional I mean irreversible) computing. I hope you know that if conventional computing can potentially be infinitely efficient, then one could construct a computer that could decrease entropy within a closed system. You are denying the second law of thermodynamics. You are denying everything that people know about statistical mechanics. Stop denying science. There are also other skeptics who have denied the value of cryptocurrencies altogether. To those of you I will say that you need to read and understand the original paper Bitcoin by Satoshi Nakamoto. Featured ## Generalizations of Laver tables is posted (140 pages) The full version of the paper Generalizations of Laver tables is now posted. In the paper, I have focused on building the general theory of Laver tables rather than solving a major problem with regards to the Laver tables. In fact, one should consider this paper as an account of “what everyone needs to know about Laver tables” rather than “solutions to problems about Laver tables.” This paper lays the foundations for future work on Laver tables. Since there is only one paper on the generalizations of Laver tables as of August 2017, an aspiring researcher currently does not have to go through many journal articles in order to further investigate these structures. I hope and expect that this paper on Laver tables will incite a broad interest on these structures among set theorists and non-set theorists, and that further investigation on these structures will be made possible by this paper. Researching Laver tables If you would like to investigate Laver tables, then please investigate the permutative LD-systems, multigenic Laver tables, and endomorphic Laver tables instead of simply the classical Laver tables. Very little work has been done on the classical Laver tables since the mid 1990’s. The classical Laver tables by themselves are a dead-end research direction unless one investigates more general classes of structures. The most important avenue of further investigation will be to evaluate the security and improve the efficiency of the functional endomorphic Laver table based cryptosystems. Here are some ways in which one can directly improve functional endomorphic Laver table based cryptography. 1. Try to break these cryptosystems. 2. Compute$A_{96}$. 3. Find compatible linear orderings on Laver-like LD-systems. 4. Find new multigenic Laver tables and new Laver-like LD-systems. It usually takes about 15 years from when a new public key cryptosystem is proposed for the public to gain confidence in such a cryptosystem. Furthermore, people will only gain confidence in a new public key cryptosystem if the mathematics behind such a cryptosystem is well-developed. Therefore, any meaningful investigation into large cardinals above hugeness and the Laver tables will indirectly improve the security of these new cryptosystems. While people have hoped for a strong connection between knots and braids and Laver tables, the Laver tables so far have not produced any meaningful results about knots or braids that cannot be proven without Laver tables. The action of the positive braid monoid is essential for even the definition of the permutative LD-systems, so one may be able to apply the permutative LD-systems to investigating knots and braids or even apply knots and braids to investigating permutative LD-systems. However, I would regard any investigation into the application of Laver tables to knots and braids to be a risky endeavor since so far people have not been able to establish a deep connection between these two types of structures. If you are a set theorist investigating the Laver tables and you are not sure if you will stay in academia for your entire career, then I recommend for you to work on something that requires extensive computer programming. This will greatly improve your job prospects if you ever leave academia for any reason. Besides, today nearly all respectable mathematicians need to also be reasonably proficient computer programmers. You do not want to be in academia trying to help students get real-world jobs when you do not yourself have the invaluable real-world skill of computer programming. My future work I will not be able to work on Laver-like algebras too much in the near future since I am currently preoccupied with my work on Nebula, the upcoming cryptocurrency which will incentivize the construction of the reversible computer. I am already behind on my work on Nebula since this paper has taken most of my time already, so I really need to work more on Nebula now. Since developing and maintaining a cryptocurrency is a full-time job, I will probably not be able to continue my investigations on Laver tables. Featured ## Slides from talk at BLAST 2017 and a rant on giving talks about the classical Laver tables Here are my slides for my talk at the BLAST 2017 conference at Vanderbilt University in Nashville, Tennessee. As a side note, I just noticed this other conference. All of the talks at that other conference on Laver tables are woefully outdated (i.e. 1995 or so). They only talk about the classical Laver tables. As an analogy, only talking about the classical Laver tables is like only talking about the cyclic groups of order$3^{n}$and then claiming that they some how represent group theory as a whole. If you are going to give a talk about Laver tables or write a paper on the Laver tables, then please read the abridged version of my paper before you do so. The classical Laver tables by themselves are a rather dead-end research area that have not been active within the last 20 years (one can probably try to analyze the fractal structure obtained from the classical Laver tables but such an analysis will probably be difficult and incremental). In order to advance further research in this area, one needs to consider the generalizations including Laver-like algebras, multigenic Laver tables, and functional endomorphic Laver tables. The classical Laver tables do not explain what the subalgebras of$\mathcal{E}_{\lambda}/\equiv^{\gamma}$generated by multiple elements look like (one cannot even show that$\mathcal{E}_{\lambda}/\equiv^{\gamma}$is locally finite without using the multigenic Laver tables). The classical Laver tables do not have any cryptographic applications. The classical Laver tables are just one sequence of structures, and it is hard to advance mathematics simply by looking at only one kind of structure with limited complexity. There is no reason at all to look at the classical Laver tables without looking at more general structures. It is better to call the structures$A_{n}=(\{1,…,2^{n}\},*_{n})$“classical Laver tables ” instead of simply “Laver tables.” There are other structures to consider. How to give a classical Laver table talk. The first step to giving a presentation on the classical Laver tables is to make sure you give your talk to the proper audience. The best audience to give a classical Laver table talk to is an audience of middle schoolers or maybe high schoolers (it is not that hard to fill out the multiplication table of a classical Laver table). Once you have your audience of middle schoolers present, you should get them to fill out an$8\times 8$classical Laver table and then a$16\times 16$classical Laver table. After they fill out the$16\times 16$classical Laver table. And yes, middle schoolers are completely capable of filling out classical Laver tables. It is not that hard. After they are done filling out the tables, you can show them pictures that arise from the classical Laver tables on the projector and hint about how these objects come from infinity. Featured ## A remedial public service announcement about the second law of thermodynamics. So it appears that some people in the mathematical community have some trouble with the second law of thermodynamics since they do not believe in science. They instead believe in perpetual motion machines, the world is flat (or a torus, or a projective sphere), and that computers, refrigerators, TV’s, cars, and airplanes are powered by demons rather than gasoline and electricity. Let me therefore give you a few experiments that you can do at home on the second law of thermodynamics. WARNING: All of these experiments are AT YOUR OWN RISK. I cannot be held responsible for any electric shocks, burns, other injuries, dumb patents, or any other damages as a result of these experiments. A scientific experiment on perpetual motion machines So let me give you a do-it-yourself experiment that you can do that will hopefully convince you that perpetual motion machines do not exist. Step 1: Find an extension cord. Extension cords can typically be found attached to electrical outlets or around equipment that requires electricity such as televisions or computers. If you cannot find an extension cord, then you may be able to buy one at Wal-Mart or Staples. Step 2: Plug the extension cord into itself. Step 3: Turn the extension cord on and then plug other things into the extension cord. Step 4: Does the light on the extension cord turn on and do the things plugged into the extension cord turn on and/or power up? If the light on the extension cord turns on and your appliances receive power, then, congratulations, you have created perpetual energy. Go and patent your invention and make trillions of dollars. If the light does not turn on, then perpetual energy does not exist, and the second law of thermodynamics is true. An experiment on the second law of thermodynamics Step 1: Make a cup of some hot coffee. Do not drink the coffee. Step 2: Measure the temperature of the coffee with a thermometer and the temperature of the room which the coffee is in. If you do not have a thermometer, then you may find one at Wal-Mart or some other store. The temperature of the coffee should be much hotter than the temperature of the room. Please make sure that you have a thermometer and not a moisture meter. Step 3: Wait 24 hours. Do not move the coffee. Store the coffee in a regular cup. Do not store the coffee in a thermos. Make sure that your mother does not heat up your coffee again since that will ruin this experiment. Step 4: Measure the temperature of the coffee and the temperature of the room which you have left the coffee in. Step 5: If the temperature of the coffee is equal to the temperature of the room, then the second law of thermodynamics is correct. If you find that the temperature of the coffee is still near a boiling temperature, then you may have been using a moisture meter instead of a thermometer. In this case, you should (at your own risk of course) stick your finger into the coffee. If you do not get burned, then the second law of thermodynamics is correct after all. If you do get burned, then you need to ask your mother if she heat up the coffee again. If she denies heating up your coffee again, then the second law of thermodynamics is false. You should therefore publish your results in the top physics journal. If they reject you, then they are persecuting you. A computer experiment on the second law of thermodynamics Here is another remedial experiment which you can perform to convince you that not only does the second law of thermodynamics apply to our physical universe, but the second law also applies to any time reversible universe. Step 1: Click here Step 2: Draw an image in the field. You may draw any image that you like. Step 3: Select a rule or input a rule yourself. You may use any rule that you like. After you select a rule, then you should run the rule for at least 100,000 generations. Step 4: If the resulting image looks something like this, then try running your cellular automaton under a different rule and repeat steps 1-4 a few times. If the image still looks orderly every time, the perhaps the second law of thermodynamics does not hold for all universes. On the other hand, if the resulting image looks like this, then the second law of thermodynamics works not just in our physical universe but also in any hypothetical or simulated universe such as a cellular automaton as long as that universe is time reversible. An experiment on the second law of thermodynamics With this experiment, you will be able to tell whether the universe will spontaneously violate the second law of thermodynamics and make all of the oxygen molecules migrate to the other side of the room while the nitrogen molecules stay on your side of the room. Step 1: Gather the materials. For this experiment, you will need an oxygen mask and a full tank of oxygen. Please make sure you know how to use the oxygen mask before starting this experiment. You should also bring a fidget spinner to entertain yourself since this experiment may take a long time to complete and you may get bored. Oh. And make sure to pack some lunch and dinner since this experiment may take a while. Step 2: Once you have the required materials, go to a room and lock the door. Please prepare to stay in that room for up to 10 hours since it may take a while for the second law of thermodynamics to be violated. Step 3: If you feel like you cannot breathe, then all of the oxygen molecules have migrated to the other side of the room in violation of the second law of thermodynamics. In this scenario, immediately put on your oxygen mask since it may take a while for the violation of the second law of thermodynamics to wear off. If the second law of thermodynamics is still being violated as your oxygen tank is about to be depleted, then please leave the room and get some fresh air. At this point, you should probably determine whether this phenomenon is a true violation of the second law of thermodynamics or whether your house is haunted. In order to tell if your house is haunted, please get it inspected. Any good home inspector will be able to tell whether evil spirits live in your home or not. If you paid 40,000 dollars for a house that normally costs 500,000 dollars, then your house is probably haunted; I mean, why would anyone sell a non-haunted house for 1/10th of its worth? Step 4: If nothing happens and you do not have to put your oxygen mask on after 10 hours, then the second law of thermodynamics is probably correct. Satire notice: This post is satire. I wrote this post in order to address the anti-scientific beliefs which I have found among the mathematical community, namely the denial of Landauer’s principle. Featured ## Nebula-The cryptocurrency that will produce the reversible computer So I have just posted the paper outlining the proof-of-work problem for my upcoming cryptocurrency Nebula. Here is the link for the paper. I hope to launch Nebula as soon as possible. The idea behind Nebula is to use a reversible computing optimized proof-of-work (RCO-POW) problem instead of an ordinary proof-of-work problem (if you do not know what I am talking about, I suggest for you to read the original paper on Bitcoin). An RCO-POW problem is like an ordinary proof-of-work problem except for the fact that the RCO-POW problem can be solved by a reversible computing device just as easily as it can be solved using a conventional computing device. It is very rare for a problem to be solvable by a reversible computing device using just as many steps as it is solvable using a conventional computing device. In general, it takes more steps to solve a problem using a reversible computation than it takes to solve the same problem using conventional computation. Therefore, since reversible computation has this computational overhead and since reversible computers currently do not exist, chip manufacturers do not have much of an incentive to manufacture reversible computing devices. However, since RCO-POW problems are just as easily solved using nearly reversible computational devices, chip manufacturers will be motivated to produce energy efficient reversible devices to solve these RCO-POW problems. After chip manufacturers know how to produce reversible devices that can solve these RCO-POW problems better than conventional devices, these manufacturers can use their knowledge and technology to start producing reversible devices for other purposes. Since reversible computation is theoretically much more efficient than conventional computation, these reversible computing devices will eventually perform much better than conventional computing devices. Hopefully these reversible computational devices will also eventually spur the development of quantum computers (one can think of reversible computation as simply quantum computation where the bits are not in a superposition of each other). Nebula shall use the RCO-POW which I shall call R5. R5 is a POW that consists of five different algorithms which range from computing reversible cellular automata to computing random reversible circuits. I use the multi-algorithm approach in order to ensure decentralization and to incentivize the production of several different kinds of reversible devices instead of just one kind of device. The only thing that will be different between Nebula and one of the existing cryptocurrencies is the POW problem since I did not want to add features which have not been tested out on existing cryptocurrencies already. Featured ## Cryptographic applications of very large cardinals-BLAST 2017 In August, I will be giving a contributed talk at the 2017 BLAST conference. I am going to give a talk about the applications of functional endomorphic Laver tables to public key cryptography. In essence, the non-abelian group based cryptosystems extend to self-distributive algebra based cryptosystems, and the functional endomorphic Laver tables are, as far as I can tell, a good platform for these cryptosystems. ABSTRACT: We shall use the rank-into-rank cardinals to construct algebras which may be used as platforms for public key cryptosystems. The well-known cryptosystems in group based cryptography generalize to self-distributive algebra based cryptosystems. In 2013, Kalka and Teicher have generalized the group based Anshel-Anshel Goldfeld key exchange to a self-distributive algebra based key exchange. Furthermore, the semigroup based Ko-Lee key exchange extends in a trivial manner to a self-distributive algebra based key exchange. In 2006, Patrick Dehornoy has established that self-distributive algebras may be used to establish authentication systems. The classical Laver tables are the unique algebras$A_{n}=(\{1,…,2^{n}-1,2^{n}\},*_{n})$such that$x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$and$x*_{n}1=x+1\mod 2^{n}$for all$x,y,z\in A_{n}$. The classical Laver tables are up-to-isomorphism the monogenerated subalgebras of the algebras of rank-into-rank embeddings modulo some ordinal. The classical Laver tables (and similar structures) may be used to recursively construct functional endomorphic Laver tables which are self-distributive algebras of an arbitrary arity. These functional endomorphic Laver tables appear to be secure platforms for self-distributive algebra based cryptosystems. The functional endomorphic Laver table based cryptosystems should be resistant to attacks from adversaries who have access to quantum computers. The functional endomorphic Laver table based cryptosystems will be the first real-world application of large cardinals! Featured ## Where are your manners? So if you remember, I recently made this post calling out the trolls, haters, and science denying crackpots on another network. I have removed all the content from this post since things have been getting out of hand and because that post has been getting too many views. I have a couple questions though. If you have noticed, this post had very little content to it. Why does a content-free post get so much more attention than a post which actually has content to it? It seems like the people here are attracted to contentless click-bait posts much more than they are to actual content. This is really pissing me off. Your attraction to click-bait articles and false and hateful rumors is disgusting and deplorable. You should be interested in new ideas instead of immediately rejecting them out of hatred. People have been ruining my reputation since they are more interested in stupid rumors than in truth. I realize that some of my posts are quite technical, but some of them are not. Some of them just announce some new program that I have written which you can launch in your browser where the only thing you have to do is read a couple directions and click a few buttons and produce a few pictures that you can hang on your wall. You do not even have to do anything. P.S. So today, the logicians have been extremely rude. Please stop it. Featured ## How cryptocurrencies could incentivize the development of efficient reversible computers and the cryptocurrency market cap reaches 100 billion dollars. I have some amazing news. The total market cap for all cryptocurrencies has for the first time has reached 100 billion dollars. On April 24,2017 the total market map for all cryptocurrencies has hit 30 billion for the first time and it has been growing ever since. At the same time, while Bitcoin has in the past been the only major cryptocurrency, Bitcoin no longer is the only major cryptocurrency since Bitcoin currently amounts for about 45 percent of the total market cap for all cryptocurrencies (on March 1,2017 Bitcoin amounted to about 85 percent of the total market cap for all cryptocurrencies). I believe that unless most of the world’s governments wage a cyber war against cryptocurrencies, in the somewhat near future cryptocurrencies will for the most part replace fiat currencies or at least compete with government fiat currencies. Governments today have an incentive to produce more fiat currencies since governments are able to fund their programs by printing more of their own money (producing more money is a bit more subtle than simply taxing people). However, there is no motivation for anyone to exponentially inflate any particular cryptocurrency (I would never own any cryptocurrency which will continue to exponentially inflates its value). For example, there will never be any more than 21 million bitcoins. Since cryptocurrencies will not lose their value through an exponential inflation, people will gain more confidence in cryptocurrencies than they would with their fiat currencies. Furthermore, cryptocurrencies also have the advantage that they are not connected to any one government and are supposed to be decentralized. Hopefully the world will transition from fiat currencies to digital currencies smoothly though. Cryptocurrencies are still very new and quite experimental, but cryptocurrencies have the potential to disrupt the global economy. There are currently many problems and questions about cryptocurrencies which people need to solve. One of the main issues with cryptocurrencies is that the proof-of-work problem for cryptocurrencies costs a lot of energy and resources and these proof-of-work problems produce nothing of value other than securing the cryptocurrency. If instead the proof-of-work problems for cryptocurrencies produce something of value other than security, the public image of cryptocurrencies will be improved, and as a consequence, governments and other organizations will be less willing to attack or hinder cryptocurrencies. In this post, I will give another attempt of producing useful proof-of-work problems for cryptocurrencies. In my previous post on cryptocurrencies, I suggested that one could achieve both security and also obtain useful proofs-of-work by employing many different kinds of problems into the proof-of-work scheme instead of a single kind of problem into such a scheme. However, while I think such a proposal is possible, it will be difficult for the cryptocurrency community to accept and implement such a proposal for a couple of reasons. First of all, in order for my proposal to work, one needs to find many different kinds of proof-of-work problems which are suitable for securing cryptocurrency blockchains (this is not an easy task). Second of all, even if all the proof-of-work problems are selected, the implementation of the proposal will be quite complex since one will have to produce protocols to remove broken problems along with a system that can work together with all the different kinds of problems. Let me therefore propose a type of proof-of-work problem which satisfies all of the nice properties that hash-based proof-of-work problems satisfy but which will spur the development of reversible computers. I am seriously considering creating a cryptocurrency whose proof-of-work problem will spur the development of reversible computers, and this post should be considered a preliminary outline of how such a proof-of-work currency would work. The next time I post about reversible computers spurred by cryptocurrencies, I will likely announce my new cryptocurrency, a whitepaper, and other pertinent information. What are reversible computers? Reversible computers are theoretical super-efficient classical computers which use very little energy because they can in some sense recycle the energy used in the computation. As analogies, an electric motor can recover the kinetic energy used to power a vehicle using regenerative braking by running the electric motor in reverse, and when people recycle aluminum cans the aluminum is used to make new cans. In a similar manner, a reversible computer can theoretically in a sense regenerate the energy used in a computation by running the computation in reverse. A reversible computer is a computer whose logic gates are all bijective and hence have the same number of input bits as output bits. For example, the AND and OR gates are irreversible gates since the Boolean operations AND and OR are not bijective. The NOT gate is a reversible gate since the NOT function is bijective. The Toffoli gate and Fredkin gates are the functions$T$and$F$respectively defined by $$T:\{0,1\}^{3}\rightarrow\{0,1\}^{3},T(x,y,z)=(x,y,(x\wedge y)\oplus z)$$ and $$F:\{0,1\}^{3}\rightarrow\{0,1\}^{3},F(0,y,z)=(0,y,z),F(1,y,z)=(1,z,y).$$ The Toffoli gate and the Fredkin gate are both universal reversible gates in the sense that Toffoli gates alone can simulate any circuit and Fredkin gates can also simulate any circuit. While reversible computation is a special case of irreversible computation, all forms of classical computation can be somewhat efficiently simulated by reversible circuits. Furthermore, when reversible computers are finally constructed, one should be able to employ a mix of reversibility and irreversibility to optimize efficiency in a partially reversible circuit. Reversible computation is an improvement over classical computation since reversible computation is potentially many times more efficient than classical computation. Landauer’s principle states that erasing a bit always costs$k\cdot T\cdot\ln(2)$energy where$T$is the temperature and$k$is the Boltzmann constant. Here the Boltzmann constant is$1.38064852\cdot 10^{−23}$joules per Kelvin. At the room temperature of 300 K, Landauer’s principle requires$2.8\cdot 10^{−21}$joules for every bit erased. The efficiency of irreversible computation is limited by Landauer’s principle since irreversible computation requires one to erase many bits. On the other hand, there is no limit to the efficiency of reversible computation since reversible computation does not require anyone to erase any bit of information. Since reversible computers are potentially more efficient than classical computers, reversible computers do not generate as much heat and hence reversible computers can potentially run at much faster speeds than ordinary classical computers. While the hardware for reversible computation has not been developed, we currently have software that could run on these reversible computers. For example, the programming language Janus is a reversible programming language. One can therefore produce, test, and run much reversible software even though the super-efficient reversible computers currently do not exist. The proof-of-work problem Let me now give a description of the proof-of-work problem. Suppose that 1.$a_{i,j},b_{i,j},c_{i,j}\in\{0,1\}$are randomly generated whenever$1\leq i\leq 128,1\leq j\leq 85$, 2.$T_{i,j}:\{0,1\}^{3}\rightarrow\{0,1\}$is the mapping defined by $$T_{i,j}(x,y,z)=((a_{i,j}\oplus x)\wedge(b_{i,j}\oplus y))\oplus c_{i,j}\oplus z,$$ 3.$a_{i}\in\{1,\ldots,256\}$for$i\in\{1,\ldots,128\},$4.$((a_{i,1,1},a_{i,1,2},a_{i,1,3}),…,(a_{i,85,1},a_{i,85,2},a_{i,85,3}))$is a randomly generated partition of$\{1,\ldots,256\}\setminus\{a_{i}\}$for$1\leq i\leq 128$, 5. For$i\in\{1,…,128\},j\in\{1,…,85\}$,$f_{i,j}:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$is the mapping where$f_{i,j}((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$if and only if$x_{n}=y_{n}$whenever$n\neq a_{i,j,3}$and $$y_{a_{i,j,3}}=T_{i,j}(x_{a_{i,j,1}},x_{a_{i,j,2}},x_{a_{i,j,3}}),$$ 6. $$f_{i}=f_{i,1}\circ…\circ f_{i,85},$$ 7.$\sigma:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$is the mapping where$\sigma((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$precisely when$x_{n}=y_{n}$for$n>128$and$y_{n}=x_{n}+x_{n+128}$whenever$n\leq 128$, 8.$\mu:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$is the mapping where$\mu((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$precisely when$x_{n}=y_{n}$for$n>128$and$y_{n}=x_{n}+x_{257-n}$whenever$n\leq 128$, 9.$\tau:\{0,1\}^{256}\rightarrow\{0,1\}^{256}$is the mapping where$\tau((x_{n})_{n=1}^{256})=(y_{n})_{n=1}^{256}$precisely when$x_{n}=y_{n}$for$n>64$and$y_{n}=x_{n}+x_{n+64}$whenever$n\leq 64$, 10. $$f=\tau\circ\sigma\circ f_{128}\circ…\circ f_{1}\circ \sigma\circ\mu.$$ The function$f$can be computed by a reversible circuit which we shall denote by$C$with 132 different layers. The 128 layers in the circuit$C$which are used to compute the functions$f_{1},…,f_{128}$shall be called rounds. The circuit$C$consists of 10880 Toffoli-like gates along with 576 CNOT gates (The circuit$C$has a total of 11456 gates). Since the randomizing function$f$is randomly generated, one will be able to replace the function$f$with a new randomly generated function$f$periodically if one wants to. Proof-of-work problem: Let$\alpha$be an adjustable 256 bit number. Let$k$be a 128 bit hash of the current block in the blockchain. Then the proof-of-work problem is to find a 128 bit nonce$\mathbf{x}$such that$f(k\#\mathbf{x})\leq\alpha$. The number$\alpha$will be periodically adjusted so that the expected value of the amount of time it takes to obtain a new block in the blockchain remains constant. Efficiency considerations It is very easy to check whether a solution to our proof-of-work problem is correct or not but it is difficult to obtain a correct solution to our proof-of-work problem. Furthermore, the randomizing function$f$in our proof-of-work problem can be just as easily computed on a reversible computer as it can on an irreversible computer. If reversible gates are only slightly more efficient than irreversible gates, then using a reversible computer to solve a proof-of-work problem will only be profitable if the randomizing function is specifically designed to be computed by a reversible circuit with no ancilla, no garbage bits, and which cannot be computed any faster by using an irreversible circuit instead. Standard cryptographic hash functions are not built to be run on reversible computers since they require one to either uncompute or to stockpile garbage bits that you will have to erase anyways. Security considerations The security of the randomizing permutation$f$described above has not yet been thoroughly analyzed. I do not know of any established cryptographic randomizing permutation$f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$that is written simply as a composition of reversible gates. I therefore had to construct a cryptographic randomizing permutation specifically as a proof-of-work problem for cryptocurrencies. There are several reasons why I have chosen to use mostly randomness to construct the function$f$instead of intentionally designing each gate of the function$f$. The circuit$C$has depth 132 which is quite low. Perhaps I can slightly increase the security or the efficiency of the proof-of-work problem by designing each particular gate without any randomness but I do not believe that I can increase the security or efficiency by much. If the function$f$is constructed once using random or pseudorandom information, then one can set up a system to automatically replace the function$f$with a new function generated in the same manner (periodically changing the function). A randomly constructed function$f$may even provide better security than a function$f$constructed without randomness because it seems like since the function$f$is constructed randomly, the function$f$would be difficult to analyze. Another reason why I chose a randomly constructed circuit is that a randomly constructed circuit$f$has a much simpler design than a function such as the SHA-256 hash. In the worst case that the randomizing function is suspected to be insecure, one would have to increase the number of rounds in the randomizing function$f$from 128 to a larger number such as 192 or 256 so that the randomizing function$f$would become secure (it is better if 128 rounds is suspected to be insecure before the cryptocurrency is launched since if we need to increase the number of rounds from 128 to 192, then that would require a hard fork which will annoy users and miners and devalue such a currency). The security requirement for the randomizing permutation$f$as a proof-of-work problem is weaker than the security problem for a randomizing permutation when used to construct a cryptographic hash function or a symmetric encryption-decryption system. For a cryptographic hash function or a symmetric encryption or decryption to remain secure when used for cryptographic purposes, such a function must remain secure until the end of time, so an adversary may potentially use an unlimited amount of resources in order to attack an individual instance of a cryptographic hash function or symmetric encryption/decryption system. Furthermore, in the case of symmetric cryptography, an adversary will have access to a large quantity of data encrypted with a particular key. However, the current blockchain data$k$changes every few seconds, so it will be quite difficult to break the proof-of-work problem. Reversible computers are half-way in-between classical computers and quantum computers I believe that the large scale quantum computer will by far be the greatest technological advancement that has ever or will ever happen. When people invent the large scale quantum computer, I will have to say “we have made it.” Perhaps the greatest motivation for constructing reversible computers is that reversible computers will facilitate the construction of large scale quantum computers. There are many similarities between quantum computers and reversible computers. The unitary operations that make up the quantum logic gates are reversible operations, and a large portion of all quantum algorithms consists of just reversible computation. Both quantum computation and reversible computation must be adiabatic (no heat goes in or out) and isentropic (entropy remains constant). However, quantum computers are more complex and more difficult to construct than reversible computers since the quantum gates are unitary operators and the quantum states inside quantum computers must remain in a globally coherent superposition. Since quantum computers are more difficult to construct than reversible computers, a more modest goal would be to construct reversible computers instead of quantum computers. Therefore, since reversible computers will be easier to construct than large scale quantum computers, we should now focus on constructing reversible computers rather than large scale quantum computers. The technology and knowledge used to construct super efficient reversible computers will then likely be used to construct quantum computers. An anti-scientific attitude among the mathematics community I have seen much unwarranted skepticism against Landauer’s principle and the possibility that reversible computation can be more efficient than classical irreversible computation could ever be. The only thing I have to say to you is that you are wrong, you are a science denier, you are a troll, and you are just like the old Catholic church who has persecuted Galileo. Featured ## 2D heat maps and 3D topographical surfaces from endomorphic Laver tables At this link you can create 2D heat maps and 3D topographical surfaces from the endomorphic Laver tables. Here is what the pictures which you could obtain from the endomorphic Laver tables look like. I was able to obtain pictures from the endomorphic Laver tables simply by giving the coordinate$(i,j)$temperature and elevation$t^{\sharp}(\mathfrak{l}_{1},\mathfrak{l}_{2},\mathfrak{l}_{3})(\mathbf{0}^{i}\mathbf{1}^{j})$. Obviously, the images that you can produce here only show a small portion of the functional endomorphic Laver tables and the functional endomorphic Laver table operations are too complicated to be completely represented visually. Featured ## A variety of mathematical proof-of-work problems will provide better security for cryptocurrencies than hash-based proof-of-work problems I have some great news. For the first time, the total market cap as of 5/23/2017 for all cryptocurrencies is at \$80,000,000,000 (a month ago it was at \$30,000,000,000 but who knows what it will be in a month or two). Furthermore, as of 5/17/2017, for the first time cryptocurrencies other than Bitcoin consist of more than 50 percent of the total market cap for all cryptocurrencies. These historic events should not be taken lightly. I predict that in the future, cryptocurrencies will for the most part replace fiat currencies. The rise of cryptocurrencies will undoubtably change the world in many important ways. For example, some have predicted that cryptocurrencies will end all war (it will be hard to fund wars with cryptocurrencies)! To learn more about cryptocurrencies, you can read the original paper on the first cryptocurrency Bitcoin. A proof-of-work problem is a computational problem that one must do to in order to produce new coins in the cryptocurrency and to maintain the security of the cryptocurrency. For example, in Bitcoin, the proof-of-work problem consists of finding suitable strings which produce exceptionally low SHA-256 hashes (the hashes must be low enough so that only one person produces a such hash every 10 minutes or so). In this post, I am going to outline how employing many different kinds of more mathematical proof-of-work problems will provide much better security for cryptocurrencies than if one were to employ only one type of proof-of-work problem and how some of the issues that arise with useful proof-of-work problems are resolvable. I believe that hash problems are popular proof-of-work problems for cryptocurrencies not because they are the best but simply because they are simple and these hash-based proof of work problems have been the best proof of work problems in instances where a proof-of-work was needed before cryptocurrencies came into being. For example, hash-based proof-of-work problems are used to thwart denial-of-service attacks and spam since for a normal user the proof-of-work problems are not too difficult to solve but the problems will be too difficult for an attacker to compute. While the hash-based proof-of-work problems are ideal to thwarting denial-of-service attacks and spammers, they are not ideal as proof-of-work schemes for cryptocurrencies. Cryptocurrencies with a many kinds of proof-of-work problems can satisfy very lax requirements compared to cryptocurrencies with only one type of proof-of-work problem. The security of cryptocurrencies depends on the fact that no single entity can solve more than 50 percent of the proof-of-work problems. If a malicious entity solves more than 50 percent of the proof-of-work problems, then such an entity can undermine the security of the entire cryptocurrency (such an attack is called a 51 percent attack). If a cryptocurrency has only one kind of proof-of-work problem, then that proof-of-work problem must satisfy very strict requirements. But if the same cryptocurrency has many different kinds of proof-of-work problems, then those proof-of-work problems are only required to satisfy relatively mild conditions, and it is therefore feasible for many useful proof-of-work problems to satisfy those conditions (here temporarily assume that there is a good protocol for removing broken proof-of-work problems). Let me list those conditions right here. The conditions colored orange are always absolutely essential for any proof-of-work problem on a cryptocurrency. The conditions colored green are essential when there is only one kind of proof-of-work problem, but these conditions in green are not necessary when there are many different kinds of proof-of-work problems for the cryptocurrency. 1. Verifiable but intractible -These problems need to be difficult to solve but it must be easy to verify the solution to these problems. 2. Utility The solution to the problem should have other uses than simply securing the cryptocurrency. The solution should have practical applications as well, or at the very least, the solutions to the problem should advance mathematics or science. Right now, the proof-of-work problem for Bitcoin is amounts to simply finding data whose SHA-256 hash is exceptionally low. 3. Scalability. For Bitcoin, the proof-of-work problems need to be solved approximately every 10 minutes (with an exponential distribution), and in any cryptocurrency, the proof-of-work problem must consistently be solved in about the same amount of time. As time goes on, the proof-of-work problems need to get more difficult to accomodate for faster computers, quicker algorithms, more people working on the problem, and more specialized computer chips solving the problem. If$X$is the distribution of the amount of time it takes to compute the proof-of-work problem, then$X$should have a consistent mean and the distributions$X,1/X$should have low variance (we do not want to solve the problem for one block in one second and solve the problem for the next block in one hour). 4. Efficient automatic generation -The proof-of-work problems need to be generated automatically based on the previous blocks in the blockchain. Cryptocurrencies are decentralized so there cannot be a central agency which assigns each individual proof-of-work problem. 5. Progress-freeness Progress freeness for search problems means that the probability that the first solution is found at time$t$follows an exponential distribution. Progress freeness for problems whose objective is to optimize$f(x)$means that for all$\alpha$the probability of finding a solution where$f(x)\geq\alpha$at time$t$follows an exponential distribution. In other words, solutions are found randomly without regard of how long one has been working on obtaining a solution. Said differently, if Alice spends 30 minutes attempting to find a solution without finding a solution, then Alice will not have any advantage if she has not spent any of the 30 minutes searching for a solution. If there is only one kind of proof-of-work problem for a cryptocurrency, and that proof-of-work problem is far from progress free, then the entity who has the fastest computer will always win, and such an entity could launch a 51 percent attack. As an extreme example of why progress-freeness is needed, suppose that a problem always takes 1000 steps to solve. If Alice has a computer that can do 500 steps a second and Bob has a computer that can do 1000 steps a second, then Bob will solve the problem in 1 second and Alice will solve the problem in 2 seconds. Therefore Bob will always win. However, a lack of progress freeness is no longer a problem if in the cryptocurrency, there are many proof-of-work problems running simultaneously. For example, in the above scenario, even if Bob is able to solve a particular problem better than everyone else, Bob will have to spend much of his computational power solving that particular problem, and Bob will not have enough resources to solve the other proof-of-work problems, and therefore Bob will be unable to launch a 51 percent attack. 6. Optimization-freeness By optimization-freeness, I mean that people need to be confident that in the future an entity will not be able to obtain a faster algorithm than we have today. The motivation behind optimization freeness is that if an entity has a secret algorithm which is much faster or better than all the other algorithms, then such an entity will be able to launch a 51 percent attack. However, a cryptocurrency employs many different kinds of proof-of-work problems, then such an entity will be able to solve a particular problem better than all others but that entity will not be able to launch a 51 percent attack. In fact, if a cryptocurrency employs many different kinds of proof-of-work problems, then optimization freeness will make the cryptocurrency less secure instead of more secure. 7. Pre-computation resistance Pre-computation refers to when an entity solves a proof-of-work problem before the proof-of-work problem for a particular block is determined. 8. Unlimited problems There needs to be an unlimited supply of proof-of-work problems to solve. This is only an issue if there is only one kind of proof-of-work problem for the cryptocurrency. If there are many kinds of proof-of-work problems in a cryptocurrency, then a particular type of proof-of-work problem can simply be removed by an automatic procedure or when all of the particular instances of the problem have been solved. The problem-removal-protocol So for a cryptocurrency which employs many different kinds of proof-of-work problems, the list of all problems which are currently being used in the cryptocurrency shall be called the problem schedule. If there are many different types of proof-of-work problems in the problem schedule, there is a good chance that a few of these proof-of-work problems should eventually be broken and should therefore be removed from the problem schedule. Since cryptocurrencies are meant to be as decentralized as possible, the process of removing broken proof-of-work problems from he problem schedule needs to be done automatically without a change to the programming of the cryptocurrency. Let me therefore list three different ways that a proof-of-work problem could be automatically removed from the problem schedule. 1. Formal proof of break The proof-of-work problem will be considered to be broken and removed from the problem schedule if an entity submits a formal proof that the proof-of-work problem can be solved in polynomial time. The entity who submits the formal proof will win a pre-determined number of blocks in the blockchain and hence new coins. 2. Heuristic algorithm for break The proof-of-work problem will be considered to be broken and removed form the problem schedule if an entity named Alice submits an algorithm that breaks the proof-of-work problem. For search problems, the algorithm is simply expected to consistently find a fast and accurate solution even if the difficulty of the proof-of-work problem is increased to very high levels. For optimization problems, the breaking algorithm must quickly and consistently give solutions which are at least as good as solutions obtained using other algorithms. In the case of optimization problems broken by a heuristic algorithm, the protocol for removing a problem from the problem schedule is more involved. Alice will first need to openly submit her algorithm for solving the proof-of-work problem. Alice is then required to follow her own algorithm and obtain a solution which is at least as optimized as the solutions produced by all other entities (keep in mind that other entities may use Alice’s algorithm or attempt to improve upon Alice’s algorithm. Furthermore, the optimization process will last long enough for other entities to attempt to improve upon Alice’s algorithm). If Alice satisfies these requirements, then the problem is removed from the problem schedule, Alice is given a pre-determined number of blocks in the blockchain, and Alice will be awarded plenty of coins. 3. Automatic removal of broken proof-of-work problems For search problems, if the proof-of-work problem is repeatedly quickly solved (possibly with multiple solutions) even when the difficulty of the problem increases without bounds, then the proof-of-work problem will be automatically removed from the problem schedule. For optimization problems, if the best solution or best solutions are consistently obtained early within the timespan for solving the problem, then the proof-of-work problem will automatically be removed from the problem schedule and after the problem is removed, no entity will be awarded any blocks in the blockchain as a prize. The automatic removal system should preferrably be implemented in a way so that an entity with a secret algorithm can always provide the best solutions to this proof-of-work problem simply by producing solutions which always win but which fall below the threshold-of-removal. However, the automatic removal system should also be implemented so that if the secret algorithm that breaks the system becomes publicly available, then the problem will easily be removed. In other words, an entity can cross the threshold-of-removal if he wants to but such an entity can just as easily remain just below the threshold-of-removal in order to obtain many coins. The benefits of having many kinds of proof-of-work problems The most obvious benefit to our composite proof-of-work system with many kinds of proof-of-work problems is that our proof-of-work system allows for a wide flexibility of problems and hence it allows for proof-of-work problems which have useful benefits besides securing the cryptocurrency. Useful proof-of-work problems will greatly benefit cryptocurrencies Useful proof-of-work problems will obviously provide benefits since the solution to those proof-of-work problems will have practical applications or at least advance mathematics. Useful proof-of-work problems will also provide a benefit to the cryptocurrencies themselves since useful proof-of-work problems will greatly help the public image of cryptocurrencies. The public image of cryptocurrencies is one of the most important battles that advocates of cryptocurrencies must face. After all, cryptocurrencies directly threaten many of the powers that governments possess, and governments have the power to ban cryptocurrencies. Not only can governments ban cryptocurrencies, but powerful governments also have the power to undermine the security of cryptocurrencies by launching 51 percent attacks against them since governments have nearly unlimited resources. Cryptocurrencies therefore need to obtain and maintain a strong public image in order to avoid governmental backlash as much as possible. Another reason for cryptocurrencies need to obtain a strong public image is that cryptocurrencies are still new and many people do not consider cryptocurrencies as legitimate currencies (those dinosaurs are wrong). People therefore need to accept cryptocurrencies as legitimate currency. Today, many people view the process of mining cryptocurrencies and maintaining the blockchain for a cryptocurrency as being incredibly wasteful and bad for the environment, and these criticisms against cryptocurrencies are justified. Cryptocurrency advocates would respond by saying that cryptocurrency mining is useful for securing and decentralizing the blockchain and hence not wasteful, but in any case, it is much better and much more efficient for these proof-of-work problems to have applications besides securing the blockchain (many cryptocurrencies have attempted to do away with proof-of-work problems since proof-of-work problems are seen as wasteful). I personally will not give cryptocurrencies my full endorsement until they are used to solve useful problems with mathematical, scientific, or practical merit. Today people receive about 4 million dollars worth of bitcoins every day from mining these bitcoins. Unfortunately, in order to mine these bitcoins, people need to use much energy to power the computers that make these calculations. Imagine how much cryptocurrencies can be used to advance mathematics and science if the proof-of-work problems are selected with scientific advancements in mind. Imagine how much these advancements to science could boost the public image of cryptocurrencies. A multitude of proof-of-work problems will increase the security of cryptocurrencies It is less obvious that our composite proof-of-work system also strengthens the security of the cryptocurrency against 51 percent attacks. It is much more straightforward for an entity to launch a 51 percent attack against a cryptocurrency with only one type of proof-of-work problem than it is to launch an attack against a cryptocurrency with many types of proof-of-work problems. After all, to launch a 51 percent attack against a single proof-of-work hash-based problem, one must simply spend a lot of money to produce a lot of ASICs for solving that problem and at any time the attacker can completely break the problem. On the other hand, to launch a 51 percent attack against many proof-of-work problems, one must obtain many different types of ASICs in order to solve many different kinds of problems. Furthermore, in some cases, an attacker may not be able to solve some of these problems since the attacker may not have access to a secret algorithm for solving this problem, and an attacker will not have access to some specialized knowledge which will allow one to quickly solve the problem. How our system could be implemented on established cryptocurrencies Cryptocurrencies are supposed to be decentralized currencies. Since cryptocurrencies are supposed to be decentralized, there should be as few changes to cryptocurrencies as possible. This poses a problem for cryptocurrencies which are attempting to switch from useless proof-of-work problems to useful proof-of-work problems. My solution is to only make a change to the cryptocurrency protocol once. In order to minimize backlash and other chaos, the changes stated in the cryptocurrency protocol will be implemented gradually. Let me now give an example of how the change from useless proof-of-work problems to useful proof-of-work problems could take place. Let$t$be the number of years before the change of the proof-of-work protocol were to take place. When$t=-4$, the cryptocurrency will begin selecting 144 different proof-of-work problems to be used in the cryptocurrency. At time$t=-1$, all 144 of the proof-of-work problems will be selected and the changes to the cryptocurrency protocol will be finalized. At time$t=0$, the cryptocurrency protocol will be modified but these modifications will take effect over a process of 6 years. Every day an average of 144 blocks will be generated. Every month from time$t=0$to time$t=6$, two out of these 144 proof-of-work problems will be selected at random to be implemented into the problem schedule. At the$m$-th month from$t=0$, every day approximately$144-2m$of the blocks on the blockchain will have a hash-based proof-of-work problem while the$2m$other blocks will be from the 144 proof-of-work problems which have already been implemented into the problem schedule. At time$t=10$, a collection of new proof-of-work problems will be selected to replace the problems which have already been broken or which will be broken in the future. Featured ## An open invitation to evaluate endomorphic Laver table based cryptosystems-Part II In this post, I will give an analysis of the Ko-Lee key exchange for the functionally endomorphic Laver tables (the Ko-Lee key exchange for functional endomorphic Laver tables is simpler to analyze than the distributive version of the Anshel-Anshel-Goldfeld key exchange). In the next post, I will simply link a JavaScript program here on this site which will allow one to analyze the Ko-Lee key exchange for functional endomorphic Laver tables. We will leave an analysis of the more complex but probably more secure distributive version of the Anshel-Anshel-Goldfeld key exchange for functional endomorphic Laver tables for a later post (we believe that the distributive Anshel-Anshel-Goldfeld key exchange would be more secure for the functional endomorphic Laver tables). Critical points Suppose that$(X,*)$is a Laver-like algebra. Then if$x,y\in X$, then define$\mathrm{crit}(x)\leq\mathrm{crit}(y)$if$x^{n}*y\in\mathrm{Li}(X)$for some$n$. We say that$\mathrm{crit}(x)=\mathrm{crit}(y)$if$\mathrm{crit}(x)\leq\mathrm{crit}(y)$and$\mathrm{crit}(y)\leq\mathrm{crit}(x)$. We shall call$\mathrm{crit}(x)$the critical point of the element$x$. Let$\mathrm{crit}[X]=\{\mathrm{crit}(x)|x\in X\}$. Then$\mathrm{crit}[X]$is a linearly ordered set. If$\alpha\in\mathrm{crit}[X]$, then there is some$r\in X$with$\mathrm{crit}(r)=\alpha$and$r*r\in\mathrm{Li}(X)$. Suppose now that$\alpha\in\mathrm{crit}[X],\mathrm{crit}(r)=\alpha,r*r=\mathrm{Li}(X)$. Then define a congruence$\equiv^{\alpha}$on$X$by letting$x\equiv^{\alpha}y$if and only if$r*x=r*y$. Then the congruence$\equiv^{\alpha}$does not depend on the choice of$\alpha$. The congruence$\equiv^{\alpha}$is the smallest congruence on$X$such that if$\mathrm{crit}(x)\geq\alpha$, then$y\in\mathrm{Li}(X)$for some$y$with$y\equiv^{\alpha}x$. If$x\in X$, then define the mapping$x^{\sharp}:\mathrm{crit}[X]\rightarrow\mathrm{crit}[X]$by letting$x^{\sharp}(\mathrm{crit}(y))=\mathrm{crit}(x*y)$. The mapping$x^{\sharp}$is monotone; if$\alpha\leq\beta$, then$x^{\sharp}(\alpha)\leq x^{\sharp}(\beta)$. Suppose that$(X,E,F)$is a Laver-like endomorphic algebra. Then suppose that$\alpha\in\mathrm{crit}(\Gamma(X,E))$. Then define the congruence$\equiv^{\alpha}$on$(X,E,F)$by letting$x\equiv^{\alpha}y$if and only if$f(x_{1},…,x_{n_{f}},x)=f(x_{1},…,x_{n_{f}},y)$where$x_{1},…,x_{n_{f}}\in X$and$\mathrm{crit}(f,x_{1},…,x_{n_{f}})=\alpha$and$(f,x_{1},…,x_{n_{f}})*(f,x_{1},…,x_{n_{f}})\in\mathrm{Li}(\Gamma(X,E))$. In the Laver-like LD-systems which we have looked at which are suitable for cryptographic purposes,$\mathrm{crit}[X]$tends to be rather small (for cryptographic purposes,$X$should have at least about 9 critical points, but the largest classical Laver table ever computed$A_{48}$has 49 critical points).$\mathbf{Proposition}:$1. If$y\equiv^{\alpha}z$, then$x*y\equiv^{x^{\sharp}(\alpha)}x*z$and$x\circ y\equiv^{x^{\sharp}(\alpha)}x\circ z$. 2. Suppose that$X$is a Laver-like LD-system and$x\in X$. Let$\alpha$be the least critical point such that$x^{\sharp}(\alpha)=\max(\mathrm{crit}[X])$. Then if$y\equiv^{\alpha}z$, then$x*y=x*z$and$x\circ y=x\circ z.$Therefore if$\mathbf{y}\in X/\equiv^{\alpha}$is the equivalence class of$y\in X$, then define$x*\mathbf{y}$to be the equivalence class of$x*y$in the quotient algebra$X/\equiv^{x^{\sharp}(\alpha)}$and define$x\circ\mathbf{y}$to be the equivalence class of$x\circ\mathbf{y}$in$X/\equiv^{x^{\sharp}(\alpha)}$.$\mathbf{Proposition}$Suppose that$(X,t^{\bullet})$is an$n+1$-ary Laver-like LD-system. Suppose that$\mathfrak{u}_{1},…,\mathfrak{u}_{n},\mathfrak{v}_{1},…,\mathfrak{v}_{n}\in\Diamond(X,t^{\bullet})$. Then$\mathrm{crit}(\mathfrak{u}_{1},…,\mathfrak{u}_{n})\leq\mathrm{crit}(\mathfrak{v}_{1},…,\mathfrak{v}_{n})$in$\Gamma(\Diamond(X,t^{\bullet}))$if and only if$\mathrm{crit}(\mathfrak{u}_{1}(\varepsilon),…,\mathfrak{u}_{n}(\varepsilon))\leq\mathrm{crit}(\mathfrak{v}_{1}(\varepsilon),…,\mathfrak{v}_{1}(\varepsilon))$. We may therefore define$\mathrm{crit}(\mathfrak{u}_{1},…,\mathfrak{u}_{n})=\mathrm{crit}(\mathfrak{u}_{1}(\varepsilon),…,\mathfrak{u}_{1}(\varepsilon))$.$\mathbf{Proposition}$Suppose that$(X,t^{\bullet})$is an$n+1$-ary Laver-like LD-system and$\alpha\in\mathrm{crit}(\Gamma(X,t^{\bullet}))=\mathrm{crit}(\Gamma(\Diamond(X,t^{\bullet})))$. Then$(\Diamond(X,t^{\bullet}))/\equiv^{\alpha}\simeq\Diamond((X,t^{\bullet})/\equiv^{\alpha})$. In particular, define a mapping$\phi:\Diamond(X,t^{\bullet})\rightarrow\Diamond((X,t^{\bullet})/\equiv^{\alpha})$as follows. Let$\mathfrak{l}\in\Diamond(X,t^{\bullet})$. Let$\mathbf{BAD}_{\mathfrak{l}}$be the set of all strings$i\mathbf{x}\in\{1,…,n\}^{*}$with$\mathrm{crit}(1\mathbf{x},…,n\mathbf{x})\geq\alpha$. Let$\mathbf{GOOD}_{\mathfrak{l}}$be the set of all strings in$\{1,…,n\}^{*}$which are not in$\mathbf{BAD}_{\mathfrak{l}}$nor have suffixes in$\mathbf{BAD}_{\mathfrak{l}}$. Then$\phi(\mathfrak{l})(\mathbf{x})=\mathfrak{l}(\mathbf{x})/\equiv^{\alpha}$whenever$\mathbf{x}\in\mathbf{GOOD}_{\mathfrak{l}}$and$\phi(\mathfrak{l})(\mathbf{x})=\#$otherwise. Then$\phi$is a homomorphism whose kernel is$\equiv^{\alpha}$. Analysis of the Ko-Lee key exchange for Laver-like LD-systems. The security of the Ko-Lee key exchange for Laver-like LD-systems depends on the difficulty of the following problem. Problem A for$(a,x,b)$in$X$: Suppose that$X$is a Laver-like algebra. Suppose that$a,x,b\in X,r=a\circ x,s=x\circ b$. Let$\alpha$be the least ordinal such that$a^{\sharp}(\alpha)=\max(\mathrm{crit}[X])$and let$\beta$be the least ordinal such that$r^{\sharp}(\beta)=\max(\mathrm{crit}[X])$. INPUT:$x,r,s,\alpha,\beta$are known. OBJECTIVE: Find$a’$such that$r=a’\circ x$(Problem A-1) or find$\mathbf{b}\in X/\equiv^{\beta}$such that$x\circ\mathbf{b}\equiv^{\alpha}s$(Problem A-2). Note: In the above problem, we assume that$\alpha$is known since$X$usually has a limited number of critical points and$\alpha$can either be solved or there are a limited number of possibilities for$\alpha$. We take note that problem A is asymmetric in the roles of$a$and$b$. In particular, Problem A-2 seems to be an easier problem than problem A-1 since$X/\equiv^{\beta}$is simpler than$X$. Constructing endomorphic Laver tables Suppose that$(X,*)$is a Laver-like LD-system. If$t:X^{n}\rightarrow X$is a mapping that satisfies the identity$x*t(x_{1},…,x_{n})=t(x*x_{1},…,x*x_{n})$, then define an operation$T:X^{n+1}\rightarrow X$by letting$T(x_{1},…,x_{n},x)=t(x_{1},…,x_{n})*x$. Then the algebra$(X,T)$is a Laver-like endomorphic algebra.$\mathbf{Proposition:}$Suppose that$(X,*)$is a Laver-like LD-system and$t:X^{n}\rightarrow X$is a mapping that satisfies the identity$x*t(x_{1},…,x_{n})=t(x*x_{1},…,x*x_{n})$. Then define$T:X^{n+1}\rightarrow X$by letting$T(x_{1},…,x_{n},x)=t(x_{1},…,x_{n})*x$. Then$\mathrm{crit}(T,x_{1},…,x_{n})\leq\mathrm{crit}(T,y_{1},…,y_{n})$in$\Gamma(X,T)$if and only if$\mathrm{crit}(t(x_{1},…,x_{n}))\leq\mathrm{crit}(t(y_{1},…,y_{n}))$in$(X,*)$. By the above Proposition, we will hold to the convention that$\mathrm{crit}(T,x_{1},…,x_{n})=\mathrm{crit}(t(x_{1},…,x_{n}))$. If$x>0$, then define$(x)_{r}$to be the unique integer with$1\leq(x)_{r}\leq r$and where$(x)_{r}=x\mod\,r$. If$n\geq m$, then define a mapping$\pi_{n,m}:A_{n}\rightarrow A_{m}$by letting$\pi_{n,m}(x)=(x)_{2^{m}}$. Define a linear ordering$\leq^{L}_{n}$on the classical Laver table$A_{n}$by induction on$n$by letting$x<^{L}_{n+1}y$if and only if$\pi_{n+1,n}(x)<^{L}_{n}\pi_{n+1,n}(y)$or$\pi_{n+1,n}(x)=\pi_{n+1,n}(y),x < y$. For simplicity, we shall simply write$\leq^{L}$for$\leq^{L}_{n}$. Then$y\leq^{L}z\rightarrow x*_{n}y\leq^{L}x*_{n}z$. Suppose that$\mathbf{S}$is a function such that 1. if$n$is a natural number and$x_{1},…,x_{r}\in A_{n}$, then$\mathbf{S}(n;x_{1},…,x_{r})\in\{0,1\}$, and 2. if$x_{1},…,x_{r}\in A_{m},y_{1},…,y_{r}\in A_{n}$and there is an isomorphism$\iota:\langle x_{1},…,x_{r}\rangle\rightarrow\langle y_{1},…,y_{r}\rangle$with$\iota(x_{1})=y_{1},…,\iota(x_{r})=y_{r}$and which preserves$\leq^{L}$, then$\mathbf{S}(m,x_{1},…,x_{r})=\mathbf{S}(n,y_{1},…,y_{r})$. Then define a mapping$\mathbf{S}_{n}:A_{n}^{r}\rightarrow A_{n}$for all$n$by induction on$n$. Suppose that$\mathbf{S}_{n}$has been defined already and suppose that$x_{1},…,x_{r}\in A_{n+1}$. Then let$v=\mathbf{S}_{n}(\pi_{n+1,n}(x_{1}),…,\pi_{n+1,n}(x_{r}))$. If$|\{v,v+2^{n}\}\cap\langle x_{1},…,x_{r}\rangle|=1$, then let$\mathbf{S}_{n+1}(x_{1},…,x_{r})$be the unique element in$\{v,v+2^{n}\}\cap\langle x_{1},…,x_{r}\rangle$. If$|\{v,v+2^{n}\}\cap\langle x_{1},…,x_{r}\rangle|=2$, then let$\mathbf{S}_{n}(x_{1},…,x_{r})=v+2^{n}\cdot\mathbf{S}(n;x_{1},…,x_{r})$. Then for all$n$, the operation$\mathbf{S}_{n}$satisfies the identity$x*_{n}\mathbf{S}_{n}(x_{1},…,x_{r})=\mathbf{S}_{n}(x*_{n}x_{1},…,x*_{n}x_{r})$. Analysis of the Ko-Lee key exchange for functional endomorphic Laver tables. For our analysis of the Ko-Lee key exchange for functional endomorphic Laver tables, assume that$t:A_{n}^{2}\rightarrow A_{n}$is a mapping that satisfies the identity$x*_{n}t(y,z)=t(x*_{n}y,x*_{n}z)$and$T^{\bullet}:A_{n}^{3}\rightarrow A_{n}$is defined by$T^{\bullet}(x,y,z)=t(x,y)*z$. In the classical Laver table$A_{n}$, we have$\mathrm{crit}(x)\leq\mathrm{crit}(y)$if and only if$\gcd(x,2^{n})\leq\gcd(y,2^{n})$. Therefore, for the classical Laver table$A_{n}$, we define$\mathrm{crit}(x)=\log_{2}(\gcd(x,2^{n}))$. In the classical Laver table$A_{n}$, we have$x\equiv^{m}y$if and only if$x=y\mod 2^{m}$. If$x\in A_{n}$, then let$o_{n}(x)$be the least natural number$m$such that$x*_{n}2^{m}=2^{n}$. In other words,$o_{n}(x)$is the least critical point$\alpha\in\mathrm{crit}[A_{n}]$where in$A_{n}$, we have$x^{\sharp}(\alpha)=\max(\mathrm{crit}[A_{n}])$. Let$\mathfrak{u}_{1},\mathfrak{u}_{2},\mathfrak{l}_{1},\mathfrak{l}_{2},\mathfrak{v}_{1},\mathfrak{v}_{2}\in\Diamond(X,T^{\bullet})$. Then in order for problem A for$(\mathfrak{u}_{1},\mathfrak{u}_{2}),(\mathfrak{l}_{1},\mathfrak{l}_{2}),(\mathfrak{v}_{1},\mathfrak{v}_{2})$to be difficult, one needs for$o_{n}(t(\mathfrak{u}_{1}(\varepsilon),\mathfrak{u}_{2}(\varepsilon))\circ_{n}t(\mathfrak{l}_{1}(\varepsilon),\mathfrak{l}_{2}(\varepsilon)))$to be as large as possible. We therefore recommend for$o_{n}(t(\mathfrak{u}_{1}(\varepsilon),\mathfrak{u}_{2}(\varepsilon))\circ_{n}t(\mathfrak{l}_{1}(\varepsilon),\mathfrak{l}_{2}(\varepsilon)))\geq 4$for the functional endomorphic Laver table based Ko-Lee key exchange to be secure. Unfortunately,$o_{n}(x\circ y)$is usually very small$\leq 4$except for highly specialized values of$ x,y$. If$x,y\in A_{n}$, then$o_{n}(x\circ_{n}y)\leq\min(o_{n}(x),o_{n}(y))$, so$o_{n}(x\circ_{n}y)$is typically very small. The following function shows that$o_{n}(x)$is usually small (usually 2 or 4). Function:The following function maps$n$to the number of elements$x\in A_{20}$with$o_{20}(x)=n$. [0→1,1→20,2→555085,3→ 107010,4→ 316545,5→ 55,6→ 37235,7→ 7255,8→ 21230,9→ 24, 10→2193, 11→462, 12→1191, 13→12, 14→144, 15→41, 16→58, 17→4, 18→8, 19→2, 20→1 ] Increasing$n$past$10$in$A_{n}$will probably not increase the security of functional endomorphic Laver table based cryptosystems. While$\{o_{n+1}(x),o_{n+1}(x)+2^{n}\}\subseteq\{o_{n}(x),o_{n}(x)+2^{n}\}$, and$o_{n+1}(x+2^{n})=o_{n}(x)$, the following data indicates that for$n\geq 10$increasing$n$has little effect on$o_{n}(x)$since it is very rare for$o_{n+1}(x)=o_{n}(x)+1$as$n$gets large. The n-th entry in the following data list is the probability (from a sample size of 100000) that$o_{n}(x)-o_{n}((x)_{2^{n-1}})=1$for$x\in A_{n}$. [1→0.5004, 2→ 0.50211, 3→ 0.5006, 4→ 0.37539, 5→ 0.37352, 6→ 0.25163, 7→ 0.18058, 8→ 0.11521, 9→ 0.0929, 10→ 0.05558, 11→ 0.0364, 12→ 0.02191, 13→ 0.01572, 14→ 0.00878, 15→ 0.00513, 16→ 0.00324, 17→ 0.00242, 18→ 0.00124, 19→ 0.00072, 20→ 0.00043, 21→ 0.00041, 22→ 0.0002, 23→ 0.00012, 24→ 2.e-05, 25→ 4.e-05, 26→ 1.e-05, 27→ 2.e-05, 28→ 0., 29→ 0., 30→ 0., 31→ 0., 32→ 0., 33→ 0., 34→ 0., 35→ 0., 36→ 0., 37→ 0., 38→ 0., 39→ 0., 40→ 0., 41→ 0., 42→ 0., 43→ 0., 44→ 0., 45→ 0., 46→ 0., 47→ 0., 48→ 0. ] While one can show that$o_{n}(1)\rightarrow\infty$using large cardinals, there is no known proof in ZFC that$o_{n}(1)\rightarrow\infty$and it is known that if$o_{n}(1)\rightarrow\infty$, then$o_{n}(1)$must diverge very slowly. Increases$n$past about 10 or so does not seem to increase the security of the functional endomorphic Laver table based cryptosystems. If$n$is much larger than$10$, and if$f$is a$k$-ary term in$\Diamond(X,T^{\bullet})$and$\mathfrak{l}_{1},…,\mathfrak{l}_{k}\in\Diamond(X,T^{\bullet})$, then$f(\mathfrak{l}_{1},…,\mathfrak{l}_{k})(\mathbf{x})$is either very close to$2^{n}$, very close to$1$, or very close to$\mathfrak{l}_{i}(\mathbf{y})$for some string$\mathbf{y}$. Said differently, increasing the size of$n$past about 10 or so does not seem to make problem A (or any other cryptographic problem) much harder to solve. Featured ## An open invitation to evaluate endomorphic Laver table based cryptosystems-Part I In my research on the generalizations of Laver tables, I found that the endomorphic Laver tables could be used as platforms for several cryptosystems. I am currently the only one looking at endomorphic Laver table based cryptosystems, and it is unclear whether endomorphic Laver table based cryptosystems are secure or not. I am therefore giving this post to invite researchers to evaluate the security of endomorphic Laver table based cryptosystems and to give them some basic information about such cryptosystems. While these posts will give some information that will allow a basic cryptanalysis of endomorphic Laver table based cryptosystems, one would definitely need to read my paper generalizations of Laver tables for a thorough understanding of the algebras involved in these cryptosystems. One should also read the chapter Elementary Embeddings and Algebra in the Handbook of Set Theory (Chapter 11) and Chapters 10-13 in Dehornoy’s book Braids and Self-Distributivity for the an outline of the development of the classical Laver tables before I started my work in 2015. If you are interested in evaluating the security of endomorphic Laver table based cryptosystems, then please post a comment to this post or send me an e-mail or otherwise contact me. As a general principle, the non-abelian group based cryptosystems extend to self-distributive algebra based cryptosystems. In particular, the Ko-Lee key exchange, Anshel-Anshel-Goldfeld key exchange, and conjugacy based authentication system, which are some of the most important non-abelian group based cryptosystems, extend from group based cryptosystems to self-distributive algebra based cryptosystems, and the endomorphic Laver tables seem to be good platforms for these self-distributive algebra based cryptosystems. It seems like endomorphic Laver tables based cryptosystems would even remain secure even against adversaries who have access to quantum computers. I do not believe that quantum computers pose any more of a threat to these cryptosystems than classical computers would since none of the techniques for constructing quantum algorithms (besides Grover’s algorithm which works in general) seem applicable to anything remotely related endomorphic Laver tables. Unless there is a fairly obvious attack, I do not foresee that we will be able to mathematically prove that there is an polynomial time classical or quantum algorithm that breaks these cryptosystems. Nevertheless, I am concerned that these cryptosystems may be susceptible to heuristic attacks. I have only been able to efficiently compute the endomorphic Laver table operations for two months now (see my previous post for more information about the difficulties in computing the endomorphic Laver table operations and how it was overcome), so these algebras and cryptosystems are fairly unknown. Endomorphic algebras An LD-system is an algebra$(X,*)$that satisfies the self-distributivity identity$x*(y*z)=(x*y)*(x*z)$. LD-systems arise naturally in set theory and in the theory of knots and braids. One can generalize the notion of self-distributivity to algebras with multiple operations, operations of higher arity, and algebras where only some of the fundamental operations are self-distributive. Suppose that$(X,E,F)$is an algebraic structure where each$f\in E$has arity$n_{f}+1$. If$f\in E,a_{1},\dots,a_{n_{f}}\in X$, then define the mapping$L_{f,a_{1},\dots,a_{n_{f}}}$by letting$L_{f,a_{1},\dots,a_{n_{f}}}(x)=f(a_{1},\dots,a_{n_{f}},x)$. Then we say that$(X,E,F)$is a partially endomorphic algebra if the mapping$L_{f,a_{1},\dots,a_{n_{f}}}$is an endomorphism of$(X,E,F)$whenever$f\in E,a_{1},\dots,a_{n_{f}}\in X$. If$F=\emptyset$, then we shall call$(X,E,F)$an endomorphic algebra (and we may write$(X,E)$to denote the endomorphic algebra$(X,E,\emptyset)$). If$(X,t)$is an endomorphic algebra and$t$is an$n+1$-ary operation, then we shall call$(X,t)$an$n+1$-ary self-distributive algebra. The partially endomorphic algebras are the universal algebraic analogues of the LD-systems. If$(X,E)$is an endomorphic algebra, then let $$\Gamma(X,E)=(\bigcup_{f\in E}\{f\}\times X^{n_{f}},*)$$ where the operation$*$is defined by $$(f,x_{1},\dots,x_{n_{f}})*(g,y_{1},\dots,y_{n_{g}})=(g,f(x_{1},\dots,x_{n_{f}},y_{1}),\dots,f(x_{1},\dots,x_{n_{f}},y_{n_{g}})).$$ Then$\Gamma(X,E)$is an LD-system. Endomorphic algebra based cryptosystems The Ko-Lee key exchange for semigroups The following key exchange is a simplified version of the Ko-Lee key exchange for semigroups. The simplified Ko-Lee key exchange: A semigroup$(X,\circ)$along with an element$x\in X$are public. 1. Alice selects an element$a\in X$and sends$r=a\circ x$to Bob. 2. Bob selects an element$b\in X$and sends$s=x\circ b$to Alice. 3. Let$K=a\circ x\circ b$. 4. Alice computes$K$using the fact that$K=a\circ s$. 5. Bob computes$K$using the fact that$K=r\circ b$. An eavesdropper listening in to the communications between Alice and Bob cannot compute$K$. The full-fledged Ko-Lee key exchange would not work for Laver-like algebras since the associative operation on Laver-like algebras has very little commutativity. The Anshel-Anshel-Goldfeld key exchange for self-distributivity In this paper, Kalka and Teicher have extended the Anshel-Anshel-Goldfeld key exchange to LD-systems. The following key exchange extends this cryptosystem by Kalka and Teicher to partially endomorphic algebras. The Anshel-Anshel-Goldfeld key exchange for endomorphic algebras: An partially endomorphic algebra$(X,E,F)$along with$x_{1},\dots,x_{m},y_{1},\dots,y_{n}\in X$are public. Let $$A=\langle x_{1},\dots,x_{m}\rangle,B=\langle y_{1},\dots,y_{n}\rangle.$$ 1. Alice selects some$a\in A$along with some term$t$such that$t(x_{1},\dots,x_{m})=a$. Alice selects an$f\in E$along with a tuple$\mathbf{a}=(a_{1},\dots,a_{n_{f}})\in X^{n_{f}}$. Alice then sends $$u_{1}=f(\mathbf{a},y_{1}),\dots,u_{n}=f(\mathbf{a},y_{n}),p_{0}=f(\mathbf{a},a)$$ to Bob. 2. Bob selects some$g\in E$along with$\mathbf{b}=(b_{1},\dots,b_{n_{g}})\in B^{n_{g}}$and terms$t_{1},\dots,t_{n_{g}}$such that $$b_{1}=t_{1}(y_{1},\dots,y_{n}),\dots,b_{n_{g}}=t_{n_{g}}(y_{1},\dots,y_{n}).$$ Bob then sends the elements$v_{1}=g(\mathbf{b},x_{1}),\dots,v_{m}=g(\mathbf{b},x_{m})$to Alice. 3. Let$K=f(\mathbf{a},g(\mathbf{b},a))$. 4. Alice computes$K$. Alice is able to compute$K$since Alice knows$f,\mathbf{a}$and since $$g(\mathbf{b},a)=g(\mathbf{b},t(x_{1},\dots,x_{m}))=t(g(\mathbf{b},x_{1}),\dots,g(\mathbf{b},x_{m})) =t(v_{1},\dots,v_{m}).$$ 5. Bob computes$K$. Bob is able to compute$K$since $$K=f(\mathbf{a},g(\mathbf{b},a))=f(\mathbf{a},g(b_{1},\dots,b_{n_{g}},a))$$ $$=g(f(\mathbf{a},b_{1}),\dots,f(\mathbf{a},b_{n_{g}}),f(\mathbf{a},a))$$ $$=g(f(\mathbf{a},t_{1}(y_{1},\dots,y_{n})),\dots,f(\mathbf{a},t_{n_{g}}(y_{1},\dots,y_{n})),p_{0})$$ $$=g(t_{1}(f(\mathbf{a},y_{1}),\dots,f(\mathbf{a},y_{n})),\dots,t_{n_{g}}(f(\mathbf{a},y_{1}),\dots,f(\mathbf{a},y_{n})),p_{0})$$ $$=g(t_{1}(u_{1},\dots,u_{n}),\dots,t_{n_{g}}(u_{1},\dots,u_{n}),p_{0}).$$ 6. No third party will be able to compute the common key$K$. Laver tables The classical Laver table$A_{n}$is the unique algebraic structure$(\{1,\dots,2^{n}\},*_{n})$that satisfies the self-distributivity identity$x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$and where$x*_{n}1=x+1\,\mod 2^{n}$for$x\in A_{n}$. The operation$*_{n}$can easily be computed from a 2.5 MB file of precomputed data as long as$n\leq 48$. We believe that it is feasible with current technology to compute$*_{n}$when$n\leq 96$though. The classical Laver tables alone are unsuitable as platforms for self-distributive algebra based cryptosystems (the classical Laver tables will offer at most 96 bits of security and in practice such cryptosystems based on the classical Laver tables are effortlessly and instantly broken). The multigenic Laver tables are not suitable as platforms for such cryptosystems either since elements in multigenic Laver tables can easily be factored. If$(X,*)$is an LD-system, then a subset$L\subseteq X$is said to be a left-ideal if$x*y\in L$whenever$y\in L$. An element$x\in X$is said to be a left-identity if$x*y=y$whenever$y\in X$. Let$\mathrm{Li}(X)$denote the set of all left-identities in the set$(X,*)$. We say that an LD-system$(X,*)$is Laver-like if 1.$\mathrm{Li}(X)$is a left-ideal in$X$, and 2. Whenever$x_{n}\in X$for all natural numbers$n$, there is some$N$such that$x_{0}*\dots*x_{N}\in\mathrm{Li}(X)$(here the implied parentheses are grouped on the left. i.e.$x*y*z=(x*y)*z$. ). For example, the classical Laver tables$A_{n}$are always Laver-like. If$(X,*)$is an LD-system, then define the Fibonacci terms$t_{n}$for$n\geq 1$by letting$t_{1}(x,y)=y,t_{2}(x,y)=x$and$t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y)$. If$(X,*)$is a Laver-like LD-system, then define an operation$\circ$on$X\setminus\mathrm{Li}(X)$by letting$x\circ y=t_{n+1}(x,y)$whenever$t_{n}(x,y)\in\mathrm{Li}(X)$(the operation$\circ$does not depend on the choice of$n$). The operation$\circ$is associative and hence suitable for the Ko-Lee key exchange. The operation$\circ$also satisfies the identity$(x\circ y)*z=x*(y*z)$. A partially endomorphic algebra$(X,E,F)$is said to be Laver-like if the hull$\Gamma(X,E)$is Laver-like. Any Laver-like algebra may be used to induce a partially endomorphic Laver table, but for simplicity, we shall only define the functional endomorphic Laver tables induced by the endomorphic algebras with only one fundamental operation. Suppose now that$(X,t^{\bullet})$is a$n+1$-ary Laver-like algebra. Let$\Diamond(X,t^{\bullet})$be the algebra with underlying set consisting of all functions$\mathfrak{l}:\{1,\dots,n\}^{*}\rightarrow X\cup\{\#\}$such that 1.$\mathfrak{l}(\varepsilon)\in X$. 2. If$\mathfrak{l}(\mathbf{x})\in\#$, then$\mathfrak{l}(i\mathbf{x})\in\#$for all$i\in\{1,\dots,n\}$. 3. If$\mathfrak{l}(\mathbf{x})\in X$, then either$\mathfrak{l}(i\mathbf{x})\in X$for all$i\in\{1,\dots,n\}$or$\mathfrak{l}(i\mathbf{x})=\#$for all$i\in\{1,\dots,n\}$. 4. If$\mathfrak{l}(i\mathbf{x})\in X$for all$i\in\{1,\dots,n\}$, then$(\mathfrak{l}(1\mathbf{x}),\dots,\mathfrak{l}(n\mathbf{x}))\not\in \mathbf{Li}(\Gamma((X,t^{\bullet})))$. 5. If$\mathfrak{l}(\mathbf{x})\in X$, and$\mathfrak{l}(i\mathbf{x})\in X$for all$i\in\{1,\dots,n\}$, then there is some$x\in X$where$t(\mathfrak{l}(1\mathbf{x}),\dots,\mathfrak{l}(n\mathbf{x}),x)=\mathfrak{l}(\mathbf{x})$. 6.$\mathfrak{l}(\mathbf{x})\in X$for only finitely many strings$\mathbf{x}\in\{1,\dots,n\}^{*}$. If$\mathfrak{l}_{1},\dots,\mathfrak{l}_{n}\in\Diamond(X,t)$and$(\mathfrak{l}_{1}(\varepsilon),\dots,\mathfrak{l}_{n}(\varepsilon))\not\in\Gamma((X,t^{\bullet}))$, then define$t_{x}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})\in\Diamond(X,t^{\bullet})$by$t(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})(\varepsilon)=t^{\bullet}(\mathfrak{l}_{1}(\varepsilon),\dots,\mathfrak{l}_{n}(\varepsilon),x)$and where$t(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})(\mathbf{x}i)=\mathfrak{l}_{i}(\mathbf{x})$. Now define an operation$t^{\sharp}:\Diamond(X,t^{\bullet})^{n+1}\rightarrow\Diamond(X,t^{\bullet})$by letting 1.$t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})=\mathfrak{l}$whenever$(\mathfrak{l}_{1}(\varepsilon),\dots,\mathfrak{l}_{n}(\varepsilon))\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$, 2. otherwise, if$\mathfrak{l}(i)=\#$for$1\leq i\leq n$, then define$t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})=t_{\mathfrak{l}(\varepsilon)}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})$, 3. otherwise if$\mathfrak{l}=t(\mathfrak{u}_{1},\dots,\mathfrak{u}_{n})$, then $$t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})$$ $$=t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},t_{x}(\mathfrak{u}_{1},\dots,\mathfrak{u}_{n}))$$ $$=t^{\sharp}(t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{u}_{1}),\dots,t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{u}_{n}),t_{x}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})).$$ Then the algebra$(\Diamond(X,t^{\bullet}),t^{\sharp})$is an$n+1$-ary self-distributive algebra which we shall refer to as a functional endomorphic Laver table. Every functional endomorphic Laver table is a Laver-like endomorphic algebra. If one has an efficient algorithm for computing$\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l}$, then one also has a reasonably efficient algorithm for computing$t^{\sharp}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})$. The Ko-Lee key exchange for endomorphic Laver tables One could apply the Ko-Lee key exchange to the operation$\circ$in$\Gamma(\Diamond(X,t^{\bullet}),t^{\sharp})$. However, since we are only able to compute$t^{\bullet}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})(\mathbf{x})$instead of the entire function$t^{\bullet}(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n},\mathfrak{l})$, we will need to modify the Ko-Lee key exchange so that the endomorphic Laver tables can be used as a platform for this cryptosystem. The self-distributive Anshel-Anshel-Goldfeld key exchange can be modified in the same way. The Ko-Lee key exchange for endomorphic Laver tables: Suppose that$(X,t^{\bullet})$is an$n+1$-ary Laver-like algebra. Then in this key exchange algorithms for computing$\mathfrak{l}_{1},\dots,\mathfrak{l}_{n}\in\Diamond(X,t^{\bullet})$are public. 1. Alice selects secret algorithms for computing$\mathfrak{u}_{1},\dots,\mathfrak{u}_{n}\in\Diamond(X,t^{\bullet})$. Let$(\mathfrak{j}_{1},\dots,\mathfrak{j}_{n})=(\mathfrak{u}_{1},\dots,\mathfrak{u}_{n})\circ(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})$. Then Alice has secret algorithms for computing$\mathfrak{j}_{1},\dots,\mathfrak{j}_{n}$. 2. Bob selects secret algorithms for computing$\mathfrak{v}_{1},\dots,\mathfrak{v}_{n}\in\Diamond(X,t^{\bullet})$. Let$(\mathfrak{k}_{1},\dots,\mathfrak{k}_{n})=(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})\circ(\mathfrak{v}_{1},\dots,\mathfrak{v}_{n})$. Bob has secret algorithms for computing$\mathfrak{k}_{1},\dots,\mathfrak{k}_{n}$. Let $$(\mathfrak{w}_{1},\dots,\mathfrak{w}_{n})$$ $$(\mathfrak{u}_{1},\dots,\mathfrak{u}_{n})\circ(\mathfrak{l}_{1},\dots,\mathfrak{l}_{n})\circ(\mathfrak{v}_{1},\dots,\mathfrak{v}_{n}).$$ 3. Let$i\in\{1,\dots,n\},\mathbf{x}\in\{1,\dots,n\}^{*}$, and let$K=\mathfrak{w}_{i}(\mathbf{x})$. 4. Alice computes$K$. Bob will not reveal the algorithms for computing$\mathfrak{k}_{1},\dots,\mathfrak{k}_{n}$since Bob’s algorithms for computing$\mathfrak{k}_{1},\dots,\mathfrak{k}_{n}$depend on his algorithms for computing$\mathfrak{v}_{1},\dots,\mathfrak{v}_{n}$. However, upon request from Alice, Bob will send specific values of the form$\mathfrak{k}_{j}(\mathbf{y})$to Alice. Alice will be able to compute$K$using her algorithms for computing$\mathfrak{u}_{1},\dots,\mathfrak{u}_{n}$and using the values$\mathfrak{k}_{j}(\mathbf{y})$sent from Bob. In general, Alice will need to ask Bob for the values of$\mathfrak{k}_{j}(\mathbf{y})$several times. 5. Bob computes$K$in a similar manner. Alice will not reveal algorithms for computing$\mathfrak{j}_{1},\dots,\mathfrak{j}_{n}$either. However, Alice will reveal specific values of the form$\mathfrak{j}_{j}(\mathbf{y})$to Bob. Bob will therefore compute$K$using his secret algorithms for computing$\mathfrak{v}_{1},\dots,\mathfrak{v}_{n}$along with values of the form$\mathfrak{j}_{j}(\mathbf{y})$sent by Alice. Remark: The common key$K$may only have a couple of bits of entropy so the common key$K$could be found by an eavesdropping party by guessing the most common possibilities. The most obvious way to mitigate this problem is to perform the above key exchange multiple times in order to obtain a large enough key. Another probably more efficient way to mitigate this problem is to use$(\mathfrak{w}_{i}(\mathbf{x}_{0}),\dots,\mathfrak{w}_{i}(\mathbf{x}_{r}))$as the common key instead where$(\mathbf{x}_{0},\dots,\mathbf{x}_{r})$is an enumeration of the suffixes of$\mathbf{x}$. To be continued In the second post, I will give a detailed analysis of the Ko-Lee key exchange for endomorphic Laver tables. Furthermore, at the same time, I will release an online JavaScript program for analyzing the Ko-Lee key exchange for endomorphic Laver tables. Featured ## Endomorphic Laver tables can be computed efficiently The partially endomorphic Laver tables are the generalizations of the notion of the classical Laver table to algebraic structures which may have an arbitrary number of fundamental operations each of arbitrary arity and where only some of the fundamental operations are required to be self-distributive. While the endomorphic Laver tables have much richer combinatorial structure than is found in the corresponding classical Laver tables and multigenic Laver tables, we are still able to somewhat efficiently compute information about the output of the fundamental operations on endomorphic Laver tables. In fact, as I have mentioned before, you may compute in endomorphic Laver tables here and here. Since we are able to compute the endomorphic Laver tables, it is plausible that the endomorphic Laver tables could be used as platforms for cryptosystems which are secure against classical attacks and even quantum attacks, but much more research still needs to be done on this topic. The definition of Laver-like partially endomorphic algebras and partially endomorphic Laver tables The definition of the partially endomorphic Laver tables is somewhat complicated. For simplicity, we shall only define the well-founded partially endomorphic Laver tables induced from known partially endomorphic Laver-like algebras. Suppose that$X$is a set and$E,F$are sets of operations on$X$. Suppose that each$\mathfrak{g}\in F$has arity$n_{\mathfrak{g}}$and each$f\in E$has arity$n_{f}+1$. If$f\in E,a_{1},…,a_{n_{f}}\in X$then let$L_{f,a_{1},…,a_{n_{f}}}:X\rightarrow X$be the mapping defined by$L_{f,a_{1},…,a_{n_{f}}}(x)=f(a_{1},…,a_{n_{f}},x)$. Then we say that$(X,E,F)$is an endomorphic algebra if each mapping$L_{f,a_{1},…,a_{n_{f}}}$is an endomorphism of$(X,E,F)$. In other words, the partially endomorphic algebras are precisely the algebras where one has the notion of an inner endomorphism. If$F=\emptyset$and$(X,E,F)$is a partially endomorphic algebra, then we say that$(X,E)$is an endomorphic algebra. We say that an algebra$(X,*)$is an LD-system (or left-distributive algebra) if$(X,*)$satisfies the identity$x*(y*z)=(x*y)*(x*z)$. Suppose that$(X,*)$is a left-distributive algebra. Then we say that a subset$L\subseteq X$is a left-ideal if$x*y\in L$whenever$y\in L$. We say that an element$x\in X$is a left-identity if$x*y=y$for all$y\in X$. Let$\mathrm{Li}(X)$denote the set of all left-identities in$X$. A left-distributive algebra$(X,*)$is said to be Laver-like if$\mathrm{Li}(X)$is a left-ideal and whenever$x_{n}\in X$for all$n\in\omega$there is some$N$where$x_{0}*…*x_{N}\in\mathrm{Li}(X)$. If$(X,*)$is Laver-like, then define$\preceq$to be the smallest partial ordering on$X$where$x\preceq x*y$whenever$x\in X\setminus\mathrm{Li}(X)$. Then$(X,\preceq)$is a dual well-founded partially ordered set and the dual well-foundedness of$(X,\preceq)$is necessary for all inductive proofs involving the generalizations of Laver tables. If$(X,E)$is an endomorphic algebra, then define the hull$\Gamma(X,E)$of$(X,E)$to be the algebra with underlying set$\bigcup_{f\in E}\{f\}\times X^{n_{f}}$and binary operation$*$defined by $$(f,x_{1},…,x_{n_{f}})*(g,y_{1},…,y_{n_{g}})$$ $$=(g,f(x_{1},…,x_{n_{f}},y_{1}),…,f(x_{1},…,x_{n_{f}},y_{n_{g}})).$$ Then the hull$\Gamma(X,E)$of an endomorphic algebra is always a left-distributive algebra. We say that a partially endomorphic algebra$(X,E,F)$is Laver-like if$\Gamma(X,E)$is Laver-like. Suppose that$\mathcal{V}=(V,(f^{\mathcal{V}})_{f\in E},(\mathfrak{g}^{\mathcal{V}})_{\mathfrak{g}\in F})$is a Laver-like partially endomorphic algebra. Suppose furthemore that$X$is a set of variables and$v_{x}\in V$for all$x\in X$. For each$x\in X$and$f\in E$, let$f_{x}$be an$n_{f}$-ary function symbol. Let$\mathcal{G}=\{f_{x}\mid f\in E,x\in X\}\cup F$. Let$\mathbf{T}_{\mathcal{G}}[X]$be the set of all terms in the language$\mathcal{G}$with variables in$X$. Let$L$be the subset of$\mathbf{T}_{\mathcal{G}}[X]$and let$\phi:L\rightarrow V$be the mappings defined by induction on the complexity of the term$\ell\in\mathbf{T}_{\mathcal{G}}[X]$according to the following rules: 1.$X\subseteq L$and$\phi(x)=v_{x}$for each$x\in X$. 2. If$\mathfrak{g}\in F$and$\ell_{1},…,\ell_{n_{\mathfrak{g}}}\in L$, then$\mathfrak{g}(\ell_{1},…,\ell_{n_{\mathfrak{g}}})\in L$and$\phi(\mathfrak{g}(\ell_{1},…,\ell_{n_{\mathfrak{g}}}))=\mathfrak{g}(\phi(\ell_{1}),…,\phi(\ell_{n_{\mathfrak{g}}}))$. 3. if$f\in E,x\in X$and$\ell_{1},…,\ell_{n_{f}}\in L$, then$f_{x}(\ell_{1},…,\ell_{n_{f}})\in L$if and only if $$(f,\phi(\ell_{1}),…,\phi(\ell_{n_{f}}))\not\in\mathrm{Li}(\Gamma(V,(f^{\mathcal{V}})_{f\in E})).$$ If$f_{x}(\ell_{1},…,\ell_{n_{f}})\in L$, then $$\phi(f_{x}(\ell_{1},…,\ell_{n_{f}}))=f^{\mathcal{V}}(\phi(\ell_{1}),…,\phi(\ell_{n_{f}}),v_{x})).$$ For each$f\in E$, define an operation$f^{\sharp}$on$L$by$f^{\sharp}(\ell_{1},…,\ell_{n},\ell)=\ell$whenever$f_{x}(\ell_{1},…,\ell_{n})\in L$and if$f_{x}(\ell_{1},…,\ell_{n})\not\in L$then 1.$f^{\sharp}(\ell_{1},…,\ell_{n},x)=f_{x}(\ell_{1},…,\ell_{n})$2.$f^{\sharp}(\ell_{1},…,\ell_{n},\mathfrak{g}(u_{1},…,u_{n_{g}}))
=\mathfrak{g}(f^{\sharp}(\ell_{1},…,\ell_{n},u_{1}),…,f^{\sharp}(\ell_{1},…,\ell_{n},u_{n_{g}})),$3.$f^{\sharp}(\ell_{1},…,\ell_{n},g_{x}(u_{1},…,u_{n_{g}}))
=g^{\sharp}(f^{\sharp}(\ell_{1},…,\ell_{n_{g}},u_{1}),…,f^{\sharp}(\ell_{1},…,\ell_{n_{g}},u_{n_{g}}),f_{x}(\ell_{1},…,\ell_{n_{g}})).$Then we shall write$\mathbf{L}((v_{x})_{x\in X},\mathcal{V})$for the algebra$(L,(f^{\sharp})_{f\in E},F)$. The algebra$(L,(f^{\sharp})_{f\in E},F)$is a Laver-like partially endomorphic algebra. Endomorphic Laver tables are usually infinite The classical Laver tables and multigenic Laver tables are always locally finite. Furthermore, every Laver-like LD-system is locally finite. In particular, the quotient algebra of elementary embeddings$\mathcal{E}_{\lambda}/\equiv^{\gamma}$is always locally finite. On the other hand, the partially endomorphic Laver tables with at least one fundamental operation of arity at least 3 that we have looked at are all infinite. Since the endomorphic Laver tables that we have looked at are all infinite, it is unclear as to how these endomorphic Laver tables could arise naturally from the algebras of rank-into-rank embeddings. Endomorphic Laver tables are abundant There are many ways to construct$N$-ary operations$t:A_{n}^{N}\rightarrow A_{n}$with$x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$. If$t$satisfies the identity$x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$, then define a mapping$T:A_{n}^{N+1}\rightarrow A_{n}$by letting$T(x_{1},…,x_{N},x)=t(x_{1},…,x_{N})*x$. Then$(X,T)$is a Laver-like$N+1$-ary algebra. Every term$t$in the language of LD-systems satisfies the identity$x*t(x_{1},…,x_{N})=t(x*x_{1},\ldots,x*x_{N})$. Let$(x)_{r}$be the unique natural number such that$1\leq(x)_{r}\leq r$and$(x)_{r}=x\mod\,r$. Then define a mapping$\pi_{n,m}:A_{n}\rightarrow A_{m}$by$\pi_{n,m}(x)=(x)_{2^{m}}$whenever$n\geq m$. If$x,y\in A_{n}$, then say that$x\leq^{L}y$if$x=y$or if$m$is the least natural number with$\pi_{n,m}(x)\neq\pi_{n,m}(y)$, then$\pi_{n,m}(x)<\pi_{n,m}(y).$Then$\leq^{L}$is a linear ordering with$y\leq^{L}z\rightarrow x*y\leq^{L}x*z$whenever$x,y,z\in A_{n}$. Define an operation$T_{k,r}:A_{n}^{r}\rightarrow A_{n}$by letting$T_{k,r}(x_{1},...,x_{r})=x_{\sigma(k)}$where$\sigma$is a permutation of$\{1,...,r\}$with$x_{\sigma(1)}\leq^{L}...\leq^{L}x_{\sigma(n)}$. Then$A_{n}$satisfies the identity$x*T_{k,r}(x_{1},...,x_{r})=T_{k,r}(x*x_{1},...,x*x_{r})$as well. There are more complex techniques for constructing mappings$t:A_{n}^{N}\rightarrow A_{n}$that satisfy the identity$x*t(x_{1},...,x_{N})=t(x*x_{1},\ldots,x*x_{N})$. At least exponential growth in output length Let$e$be a variable. Let$\ell_{1}=e$. Let$\mathcal{V}=(A_{n},t^{\mathcal{V}})$where$t^{\mathcal{V}}$is the operation defined by$t^{\mathcal{V}}(x,y,z)=y*z$. Let$L=\mathbf{L}((1)_{r\in\{e\}},\mathcal{V})$. For$1\leq i<2^{n}$, let$\ell_{i+1}=t(\ell_{i},\ell_{i})$. Then the term$\ell_{i}$has$2^{i-1}$instances of the variable$e$and by induction one can show that in$L$, we have$t^{\sharp}(\ell_{r},\ell_{r},\ell_{s})=\ell_{r*_{n}s}$. Such large output is typical for endomorphic Laver table operations. Therefore the output of an endomorphic Laver table operation is often too large to be stored completely by a computer. Some computer experiments suggest that the output size of the endomorphic Laver table operations may be super-exponential. The trick to computing endomorphic Laver tables In one sense, the endomorphic Laver table operations are not efficiently computable since our output grows at least exponentially, but we are able to find a sense in which the endomorphic Laver table operations are efficiently computable. The first idea to computing endomorphic Laver tables is not to compute the entire term$t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$but to recursively compute just a piece of information from the term$t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$or an approximation of the term$t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$. We shall see that these approximations of the term$t^{\sharp}(\ell_{1},…,\ell_{n},\ell)$are analogous to how floating point numbers approximate the real numbers. The second idea is to use the original endomorphic Laver-like algebra to extract the necessary information about the terms. For simplicity of notation, assume that$(X,t^{\bullet})$is an$n+1$-ary Laver-like algebra. Let$\Diamond(X,t^{\bullet})$be the set of all functions$\mathfrak{l}:\{1,…,n\}^{*}\rightarrow X\cup\{\#\}$that satisfy the following conditions: 1.$\mathfrak{l}(\varepsilon)\in X$. 2. If$\mathfrak{l}(\mathbf{x})=\#$, then$\mathfrak{l}(i\mathbf{x})=\#$for$1\leq i\leq n$. 3. If$\mathfrak{l}(\mathbf{x})\in X$, then either$\mathfrak{l}(i\mathbf{x})\in X$for$1\leq i\leq n$or$\mathfrak{l}(i\mathbf{x})=\#$for$1\leq i\leq n$. 4. If$\mathfrak{l}(i\mathbf{x})\in X$for$1\leq i\leq n$, then$(\mathfrak{l}(1\mathbf{x}),…,\mathfrak{l}(n\mathbf{x}))\not\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$. 5. If$\mathfrak{l}(i\mathbf{x})\in X$for$1\leq i\leq n$, then there is some$x\in X$where$t^{\bullet}(\mathfrak{l}(1\mathbf{x}),…,\mathfrak{l}(n\mathbf{x}),x)=\mathfrak{l}(\mathbf{x})$. 6.$\mathfrak{l}(\mathbf{x})\in X$for only finitely many$\mathbf{x}\in X$. Now if$\mathfrak{l}_{1},…,\mathfrak{l}_{n}\in\Diamond(X,t^{\bullet})^{n}$and$(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon))\not\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$, and$x\in X$, then define$t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n}):\{1,…,n\}^{*}\rightarrow X\cup\{\#\}$by letting$t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})(\varepsilon)=t^{\bullet}(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon),x)$and where$t_{x}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})(\mathbf{x}i)=\mathfrak{l}_{i}(\mathbf{x})$whenever$i\mathbf{x}\in\{1,…,n\}^{*}$. Then there is a unique operation$t^{\sharp}:\Diamond(X,t^{\bullet})^{n+1}\rightarrow\Diamond(X,t^{\bullet})$such that 1.$t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})=\mathfrak{l}$whenever$(\mathfrak{l}_{1}(\varepsilon),…,\mathfrak{l}_{n}(\varepsilon))\in\mathrm{Li}(\Gamma(X,t^{\bullet}))$, 2. Otherwise, if$\mathfrak{l}(i)=\#$for$1\leq i\leq n$, then$t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})=t_{\mathfrak{l}(\varepsilon)}(\mathfrak{l}_{1},…,\mathfrak{l}_{n})$, and 3. $$t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},t^{\sharp}(\mathfrak{u}_{1},…,\mathfrak{u}_{n},\mathfrak{u}))$$ $$=t^{\sharp}(t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u}_{1}),…, t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u}_{n}),t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{u})).$$ Then the algebra$\Diamond(X,t^{\bullet})$is isomorphic to a quotient of the endomorphic Laver table$\mathbf{L}((x)_{x\in X},(X,t^{\bullet}))$by a very small congruence. Furthermore, it is easy to embed any desired endomorphic Laver table into an algebra of the form$\Diamond(X,t^{\bullet})$. Instead of computing the entire output$t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})$, one could just compute$t^{\sharp}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})(\mathbf{x})$for some string$\mathbf{x}$. Endomorphic Laver tables can be computed quickly Suppose that$(X,t^{\bullet})$is an$r+1$-ary Laver-like algebra. By our experiments, we have concluded that if$f(x_{1},…,x_{r})$is a term whose only function symbol is$t^{\sharp}$, then in$\Diamond(X,t^{\bullet})$, the value of$f(\mathfrak{l}_{1},…,\mathfrak{l}_{r})(\mathbf{x})$is usually computable in a few seconds as long as$|\mathbf{x}|<500$or so in the language JavaScript on a web browser. When$\mathbf{x}$gets to long, I usually run out of memory or the computation fails from too deep recursion errors. A limitless source of combinatorial complexity. While the classical Laver tables and multigenic Laver tables collectively can be thought of as an unlimited source of combinatorial complexity, since every classical Laver table and multigenic Laver table is locally finite, each classical Laver table and multigenic Laver table must only have a limited amount of combinatorial complexity. However, each endomorphic Laver table seems to contain an unlimited amount of combinatorial complexity and there does not appear to be a formula for computing$t^{\bullet}(\mathfrak{l}_{1},…,\mathfrak{l}_{n},\mathfrak{l})(\mathbf{x})$even for endomorphic Laver tables originally obtained from$A_{5}$. The output of an endomorphic Laver table operation is usually unpredictable, but among the complexity of the output of the endomorphic Laver tables, there is some order amidst the complexity. The output of endomorphic Laver table operations seem to exhibit a sort of periodicity which is similar to the periodicity found in the classical and multigenic Laver tables. Possible applications to public key cryptography The endomorphic Laver tables incorporate the following attributes which are necessary for public key cryptography. 1. The classical Laver tables are combinatorially complicated since they may be used to produce recursive functions which grow faster than the Ackermann function. The multigenic Laver tables are even more complicated. However, the combinatorial richness of the classical Laver tables and multigenic Laver tables is surpassed by the combinatorial complexity that arises from the endomorphic Laver tables. 2. While the endomorphic Laver tables are combinatorially intricate, the endomorphic Laver tables still retain much algebraic structure. In other words, there is order to the chaos that arises from endomorphic Laver tables. 3. The endomorphic Laver tables are fairly easy to compute. 4. The endomorphic Laver tables currently have nothing to do with linear algebra, fourier transforms, or anything of that sort. This is an advantage since quantum algorithms tend to rely on these techniques that have nothing to do with Laver tables. Therefore since quantum algorithms do not seem to help with calculating anything related to Laver tables, endomorphic Laver tables may be useful in post-quantum cryptography (post-quantum cryptography refers to the study of public key cryptosystems that resist attacks from parties that have access to quantum computers). I will put up a post soon about the various endomorphic Laver tables based cryptosystems along with a preliminary analysis of one of those cryptosystems. It is currently unclear as to whether endomorphic Laver table based cryptosystems are secure and much more investigation on endomorphic Laver tables is necessary before I can gain any confidence about the security of endomorphic Laver table based cryptosystems. Featured ## Generalizations of Laver tables Abridged posted! The abridged version of the paper containing all the research on generalizations of Laver tables which I have done on and off for about two years is now posted here. This version contains all definitions, theorems, but I have omitted the proofs of the theorems since I am still editing the proofs. The unabridged version of the paper should be about 135 pages or so. From the mid 1990’s to about 2012, no results have been published on Laver tables or the quotient algebras of elementary embeddings. Nevertheless, set theorists have considered the algebras of elementary embeddings to be important enough that they have devoted Chapter 11 in the 24 chapter Handbook of Set Theory to the algebras of elementary embeddings. Since I am the only one researching generalizations of Laver tables, and only 3 other people have published on Laver tables since the 1990’s, I have attempted to make the paper self-contained and readable to a general mathematician. Any comments or criticism either by e-mail or on this post about the paper would be appreciated including typos and other errors. Let me now summarize some of the results from the paper. 1. The double inductive definition of a Laver table extends greatly to a universal algebraic context where we may have some of the following: • The algebra may be generated by many elements (multigenic Laver tables). • The algebra may have many fundamental operations (multi-Laver tables). • The algebra may have fundamental operations of higher arity (endomorphic Laver tables). • Only some of the fundamental operations are self-distributive (partially endomorphic Laver tables). • The fundamental operations satisfy a twisted version of self-distributivity such as $$t(a,b,c,t(w,x,y,z))$$ $$=t(t(a,b,c,w),t(b,c,a,x),t(c,a,b,y),t(a,b,c,z))$$ (twistedly endomorphic Laver tables). 2. The notion of a permutative LD-system algebraizes most of the properties that one obtains from the quotient algebras of elementary embeddings. For instance, permutative LD-systems have a notion of a composition operation, critical point, and equivalence up to an ordinal and these notions satisfy most of the properties that algebras of elementary embeddings satisfy. These notions are not contrived to look like the algebras of elementary embeddings since the critical point, composition, and equivalence up to an ordinal are fundamental to the theory of permutative LD-systems. Every quotient algebra of elementary embeddings$\mathcal{E}_{\lambda}/\equiv^{\gamma}$is a permutative LD-system but the converse does not hold. The notion of a permutative LD-system provides a natural framework by which one can prove results about finite structures using large cardinal hypotheses. 3. The set$(A^{\leq 2^{n}})^{+}$consisting of all non-empty strings from the alphabet$A$of length at most$2^{n}$can be endowed with a unique self-distributive operation$*$such that$\mathbf{x}*\mathbf{y}=\mathbf{y}$whenever$|\mathbf{x}|=2^{n}$and where$\mathbf{x}*a=\mathbf{x}a$whenever$|\mathbf{x}|<2^{n}$($((A^{\leq 2^{n}})^{+},*)$is a multigenic Laver table). The operation$*$can be computed on a standard computer as long as$n$is at most 26 or so (if$n=26$, then the output$\mathbf{x}*\mathbf{y}$could have length up to$2^{26}$so we run into some memory issues). All of the combinatorial information in the operation$*$is contained within the classical Laver table$A_{n}$along with a function$FM_{n}^{-}:\{1,...,2^{n}\}\times\{1,...,2^{n}\}\rightarrow\mathbb{Z}\setminus\{0\}$called the final matrix. Entries in$FM_{n}^{-}$can generally be computed on a standard computer in milliseconds as long as$n\leq 48$(we reach the limit$n\leq 48$since$A_{48}$is the largest classical Laver table ever computed.). While the entries in$FM_{n}^{-}$can be computed fairly quickly when one knows the classical Laver table$A_{n}$, the final matrices are combinatorially complex objects which contain intricacies which are not present in the classical Laver tables. The positive entries of the final matrix presumably form a subset of the Sierpinski triangle. There are many phenomena in the final matrices which I have observed experimentally but which have not been proven mathematically and which currently do not have any explanation. 4. The multigenic Laver tables$(A^{\leq 2^{n}})^{+}$form an inverse system. If for all$n$, there exists an$n$-huge cardinal, then almost every finite or countable subset of$\varprojlim_{n}(A^{\leq 2^{n}})^{+}$freely generates a free LD-system (and even a free LD-monoid). Recall that Richard Laver has proven in the 1990’s that the free left-distributive algebra on one generator can be embedded into an inverse limit of classical Laver tables. I have therefore constructed the machinery to prove an analogous result for free left-distributive algebras on multiple generators. 5. We present methods of producing new finite permutative LD-systems from old finite permutative LD-systems including • extending a multigenic Laver table to a larger multigenic Laver table with one more critical point, and • extending a permutative LD-system to a larger permutative LD-system by adding one point at a time. 6. Not every finite reduced permutative LD-system arises as a subalgebra of a quotient of an algebra of elementary embeddings. This counterexample suggests that there may be an inconsistency in the large cardinal hierarchy first appearing somewhere between the huge cardinals and Berkeley cardinals (and hopefully at the level above I0). 7. While the output of the endomorphic Laver table operations is typically very large. One can still compute information about the output of the endomorphic Laver table operations. As one would expect, the endomorphic Laver tables exhibit a sort of combinatorial complexity beyond the classical and multigenic Laver tables. 8. Non-abelian group based cryptosystems such as the Anshel-Anshel-Goldfeld and Ko-Lee key exchanges extend to self-distributive algebras and also endomorphic algebras. The endomorphic Laver tables may be a good platform for such cryptosystems, but I do not know much about the security of the endomorphic Laver table based cryptosystem, and I have much uneasiness about the security of such cryptosystems even though I have not yet launched an attack (I have an idea of how an attack may work though). Featured ## Ternary Laver table calculator (now optimized for efficiency) At this link, you can find an easy-to-use ternary Laver table calculator which I have just programmed which returns specific information about the output of a ternary Laver table operation. The calculator works for very specific types of ternary Laver tables. Furthermore, at this link, you can find another ternary Laver table calculator that will return the entire (sometimes very large) output of a certain ternary Laver table operation. The ternary Laver tables are much different than the classical and multigenic Laver tables (I used to call the multigenic Laver tables “generalized Laver tables”) computationally in the following ways: 1. Unlike the classical Laver tables and multigenic Laver tables which are locally finite, the endomorphic Laver tables are infinite. 2. The output of a ternary Laver table operation can grow exponentially with respect to the size of the input. 3. While the fundamental operation on the multigenic Laver tables$(A^{\leq 2^{n}})^{+}$can be completely described by the final matrix, there does not seem to be any final matrix for the ternary Laver tables. Each ternary Laver table seems to offer unlimited combinatorial complexity. 4. The ternary Laver tables are much more abundant than the multigenic Laver tables. We have very general methods of constructing many ternary Laver tables. 5. While the classical Laver tables and multigenic Laver tables are not suitable platforms for public key cryptosystems, it seems like the ternary Laver tables could be platforms for public key cryptosystems. And I will probably post the version of the paper on Generalizations of Laver tables (135 pages with proofs and 86 pages without proofs) without proofs in a couple of days. Let me know if the calculator is easy to use or not. As with the classical and multigenic Laver tables, the ternary Laver tables also produce vivid images. I will post these images soon. Featured ## Zoom into the classical Laver table fractals At this link, you may zoom into the fractal representing the classical Laver tables. For all$n$, let$L_{n}:\{0,\ldots,2^{n-1}\}\rightarrow\{0,\ldots,2^{n-1}\}$be the mapping that reverses the digits in the binary expansion of a natural number. Let$L_{n}^{\sharp}:\{1,\ldots,2^{n}\}\rightarrow\{1,\ldots,2^{n}\}$be the mapping where$L_{n}^{\sharp}(x)=L_{n}(x-1)+1$. Let$\#_{n}$be the operation on$\{1,\ldots,2^{n}\}$defined by$x\#_{n}y=L_{n}^{\sharp}(L_{n}^{\sharp}(x)*_{n}L_{n}^{\sharp}(y))$where$*_{n}$is the classical Laver table operation on$\{1,\ldots,2^{n}\}$. Let$C_{n}=\{(\frac{x}{2^{n}},\frac{x\#_{n}y}{2^{n}})\mid x,y\in\{1,\ldots,2^{n}\}\}$. Then$C_{n}$is a subset of$[0,1]\times[0,1]$and the sets$C_{n}$converge in the Hausdorff metric to a compact subset$C\subseteq[0,1]\times[0,1]$. The link that I gave gives images of$C$that you may zoom in to. Since$A_{48}$is still the largest classical Laver table ever computed, we are only able to zoom into$C$with$2^{48}\times 2^{48}$resolution (which is about 281 trillion by 281 trillion so we can see microscopic detail). As I kind of expected, these images of the classical Laver tables are quite tame compared to the wildness of the final matrix which one obtains from the generalized Laver tables$(A^{\leq 2^{n}})^{+}$; the generalized Laver tables give more fractal-like images while the classical Laver tables give more geometric images. I conjecture that the set$C$has Hausdorff dimension$1$though I do not have a proof. The simplicity of these images of the classical Laver tables gives some hope for computing the classical Laver tables past even$A_{96}$. Some regions in the set$C$may look to be simply smooth vertical or diagonal lines, but if there exists a rank-into-rank cardinal, then every single neighborhood in$C$has fractal features if you zoom in far enough (I suspect that you will need to zoom in for a very very long time before you see any fractal features and I also suspect that you will need to zoom into the right location to see the fractal behavior). Featured ## Some new results on finite algebras whose only known proof uses large cardinals (updated) The large cardinals above hugeness are a very powerful tool for proving results about finite self-distributive algebras, but mathematicians so far have neglected to exploit the tremendous power of these very large cardinals to prove results about finite objects. Initially around the late 80’s and early 90’s, Laver and other mathematicians have established some very good classical results about the Laver tables. On the other hand, from the later 1990’s to the 2010’s, no mathematician has published any original research that directly relates to what I call Laver-like LD-systems. Furthermore, before my work on the algebras of elementary embeddings, nobody has investigated what will happen in the algebras of elementary embeddings generated by more than one element. There are two results about the classical Laver tables which presumably require large cardinals to establish. One of these results states that the inverse limit of the classical Laver tables contains free left-distributive algebras on one generator while the other result states that in the classical Laver table$A_{n}$, we have$2*_{n}x=2^{n}\Rightarrow 1*_{n}x=2^{n}$. All of the other results about the classical Laver tables are known to hold in ZFC. In this post, we shall use large cardinals and forcing to prove the existence of certain classes of finite self-distributive algebras with a compatible linear ordering. The results contained in this note shall be included in my (hopefully soon to be on Arxiv) 100+ page paper Generalizations of Laver tables. In this post, I have made no attempt to optimize the large cardinal hypotheses. For background information, see this post or see Chapter 11 in the Handbook of Set Theory. We shall let$\mathcal{E}_{\alpha}$denote the set of all elementary embeddings$j:V_{\alpha}\rightarrow V_{\alpha}.$By this answer, I have outlined a proof that the algebra$\mathcal{E}_{\lambda}/\equiv^{\gamma}$is locally finite. We therefore have established a deep connection between the top of the large cardinal hierarchy and finite algebras. In this note, we shall use two important ideas to construct finite self-distributive algebras. The main idea is to generalize the square root lemma for elementary embeddings so that one obtains elementary embeddings with the desired properties.$\textbf{Theorem: (Square Root Lemma)}$Let$j\in\mathcal{E}_{\lambda+1}$. Then there is some$k\in\mathcal{E}_{\lambda}$where$k*k=j|_{V_{\lambda}}$.$\mathbf{Proof}:$By elementarity $$V_{\lambda+1}\models\exists k\in\mathcal{E}_{\lambda}:k*k=j|_{V_{\lambda}}$$ if and only if $$V_{\lambda+1}\models\exists k\in\mathcal{E}_{\lambda}:k*k=j(j|_{V_{\lambda}})$$ which is true. Therefore, there is some$k\in\mathcal{E}_{\lambda}$with$k*k=j|_{V_{\lambda}}$.$\mathbf{QED}$The other idea is to work in a model such that there is a cardinal$\lambda$where there are plenty of rank-into-rank embeddings from$V_{\lambda}$to$V_{\lambda}$but where$V_{\lambda}\models\text{V=HOD}$. If$V_{\lambda}\models\text{V=HOD}$, then$V_{\lambda}$has a definable linear ordering which induces a desirable linear ordering on rank-into-rank embeddings and hence linear orderings on finite algebras. The following result can be found in this paper.$\mathbf{Theorem}$Suppose that there exists a non-trivial elementary embedding$j:V_{\lambda+1}\rightarrow V_{\lambda+1}$. Then in some forcing extension$V[G]$there is some elementary embedding$k:V[G]_{\lambda+1}\rightarrow V[G]_{\lambda+1}$where$V[G]_{\lambda}\models\text{V=HOD}$. Therefore it is consistent relative to large cardinals that there exists a non-trivial elementary embedding$j:V_{\lambda+1}\rightarrow V_{\lambda+1}$such that$V_{\lambda}\models\text{V=HOD}$. Now suppose that$V_{\lambda}\models\text{V=HOD}$. Then there exists a linear ordering$\ll$of$V_{\lambda}$which is definable in$V_{\lambda}$. If$j\in\mathcal{E}_{\lambda}$and$\gamma$is a limit ordinal with$\gamma<\lambda$, then define$j\upharpoonright_{\gamma}:V_{\gamma}\rightarrow V_{\gamma+1}$by$j\upharpoonright_{\gamma}(x)=x\cap V_{\gamma}$for each$x\in V_{\gamma}.$Take note that$j\upharpoonright_{\gamma}=k\upharpoonright_{\gamma}$if and only if$j\equiv^{\gamma}k$. Define a linear ordering$\trianglelefteq$on$\mathcal{E}_{\lambda}$where$j\trianglelefteq k$if and only if$j=k$or there is a limit ordinal$\alpha$where$j\upharpoonright_{\alpha}\ll k\upharpoonright_{\alpha}$but where$j\upharpoonright_{\beta}=k\upharpoonright_{\beta}$whenever$\beta<\alpha$. Define a linear ordering$\trianglelefteq$on$\{j\upharpoonright_{\gamma}\mid j\in\mathcal{E}_{\lambda}\}$by letting$j\upharpoonright_{\gamma}\triangleleft k\upharpoonright_{\gamma}$if and only if there is some limit ordinal$\beta\leq\gamma$where$j\upharpoonright_{\beta}\ll k\upharpoonright_{\beta}$but where$j\upharpoonright_{\alpha}=k\upharpoonright_{\alpha}$whenever$\alpha$is a limit ordinal with$\alpha<\beta$. By elementarity, the linear ordering$\trianglelefteq$satisfies the following compatibility property: if$k\upharpoonright_{\gamma}\trianglelefteq l\upharpoonright_{\gamma}$, then$(j*k)\upharpoonright_{\gamma}\trianglelefteq(j*l)\upharpoonright_{\gamma}$. We say that a linear ordering$\leq$on a Laver-like LD-system$(X,*)$is a compatible linear ordering if$y\leq z\Rightarrow x*y\leq x*z$. If$V_{\lambda}\models\text{V=HOD}$, then$\mathcal{E}_{\lambda}/\equiv^{\gamma}$has a compatible linear ordering defined by$[j]_{\gamma}\leq[k]_{\gamma}$if and only if$j\upharpoonright_{V_{\gamma}}\trianglelefteq k\upharpoonright_{V_{\gamma}}$. Using generalized Laver tables, we know that the set$\{\text{crit}(j):j\in\langle j_{1},…,j_{n}\rangle\}$has order-type$\omega$. Let$\text{crit}_{r}(j_{1},…,j_{n})$be the$r$-th element of the set $$\{\text{crit}(j):j\in\langle j_{1},…,j_{n}\rangle\}$$ ($\text{crit}_{0}(j_{1},…,j_{n})$is the least element of$\{\text{crit}(j):j\in\langle j_{1},…,j_{n}\rangle\}$). Let$T:\bigcup_{n\in\omega}\mathcal{E}_{\lambda}^{n}\rightarrow V_{\omega\cdot 2}$be a mapping definable in$(V_{\lambda+1},\in)$where$T(j_{1},…,j_{m})=T(k_{1},…,k_{n})$if and only if$m=n$and if$\gamma=\text{crit}_{r} (j_{1},…,j_{m})$and$\delta=\text{crit}_{r}(k_{1},…,k_{n})$, then there is some isomorphism$\phi:\langle j_{1},…,j_{m}\rangle/\equiv^{\gamma}\rightarrow\langle k_{1},…,k_{n}\rangle/\equiv^{\delta}$where$\phi([j_{i}]_{\gamma})=[k_{i}]_{\delta}$. We remark that if$T(j_{1},…,j_{m})=T(k_{1},…,k_{n})$, then the subspaces$\overline{\langle j_{1},…,j_{m}\rangle}$and$\overline{\langle k_{1},…,k_{n}\rangle}$of$\mathcal{E}_{\lambda}$are homeomorphic by an isomorphism of algebras preserving$*,\circ$($\mathcal{E}_{\lambda}$can be given a complete metric that induces a canonical uniformity on$\mathcal{E}_{\lambda}$). The following technical result is a generalization of the Square-Root Lemma, and a simplified special case of the following results can be found in this answer that I gave.$\mathbf{Theorem:}$Suppose the following: 1.$\ell_{1},…,\ell_{p},j_{1},…,j_{m}\in\mathcal{E}_{\lambda}$and$(k_{r,s})_{1\leq r\leq n,1\leq s\leq p}\in(\mathcal{E}_{\lambda})^{n\cdot p}$. 2.$\ell_{1},…,\ell_{p}$are I1 embeddings. 3.$T(\ell_{i}*j_{1},…,\ell_{i}*j_{m},k_{1,i},…,k_{n,i})=x_{i}$whenever$1\leq i\leq p$. 4.$v$is a natural number. 5. there is some$\mu<\lambda$where$\mu=\text{crit}_{v}(k_{1,1},...,k_{n,1})=\ldots=\text{crit}_{v}(k_{1,p},...,k_{n,p})$. 6.$k_{r,1}\equiv^{\mu}…\equiv^{\mu}k_{r,p}$for$1\leq r\leq n$. 7.$\ell_{1}\equiv^{\mu+\omega}…\equiv^{\mu+\omega}\ell_{p}$. Then there are$(w_{r,s})_{1\leq r\leq n,1\leq s\leq p}$in$\mathcal{E}_{\lambda}$where 1.$T(j_{1},…,j_{m},w_{1,i},…,w_{n,i})=x_{i}$for$1\leq i\leq p$, 2. there is some$\alpha<\lambda$where$\text{crit}_{v}(w_{1,i},...,w_{n,i})=\alpha$for$1\leq i\leq p$, and 3.$w_{r,1}\equiv^{\alpha}\ldots\equiv^{\alpha}w_{r,p}$for$1\leq r\leq n$.$\mathbf{Proof:}$For$1\leq i\leq p$, let$A_{i}$$$=\{(w_{1}\upharpoonright_{\text{crit}_{v}(w_{1},…,w_{n})},…,w_{n}\upharpoonright_{\text{crit}_{v}(w_{1},…,w_{n})}): T(j_{1},…,j_{m},w_{1},…,w_{n})=x_{i}\}.$$ Then$\ell_{i}(A_{i})$$$=\{(w_{1}\upharpoonright_{\text{crit}_{v}(w_{1},…,w_{n})},…,w_{n}\upharpoonright_{\text{crit}_{v}(w_{1},…,w_{n})}): T(\ell_{i}*j_{1},…,\ell_{i}*j_{m},w_{1},…,w_{n})=x_{i}\}.$$ Therefore, $$(k_{1,i}\upharpoonright_{\mu},…,k_{n,i}\upharpoonright_{\mu})\in\ell_{i}(A_{i})$$ for$1\leq i\leq p$. Since$k_{r,1}\upharpoonright_{\mu}=…=k_{r,p}\upharpoonright_{\mu}$, we have $$(k_{1,1}\upharpoonright_{\mu},…,k_{n,1}\upharpoonright_{\mu})=…=(k_{1,p}\upharpoonright_{\mu},…,k_{n,p}\upharpoonright_{\mu}).$$ Therefore, let $$(\mathfrak{k}_{1},…,\mathfrak{k}_{n})=(k_{1,1}\upharpoonright_{\mu},…,k_{n,1}\upharpoonright_{\mu}).$$ Then $$(\mathfrak{k}_{1},…,\mathfrak{k}_{n})\in\ell_{1}(A_{1})\cap…\ell_{p}(A_{p})\cap V_{\mu+\omega}$$ $$=\ell_{1}(A_{1})\cap…\cap\ell_{1}(A_{p})\cap V_{\mu+\omega}$$ $$\subseteq\ell_{1}(A_{1}\cap…\cap A_{p}).$$ Therefore,$A_{1}\cap…\cap A_{p}\neq\emptyset.$Let$(\mathfrak{w}_{1},…,\mathfrak{w}_{n})\in A_{1}\cap…\cap A_{p}$. Then there are$(w_{r,s})_{1\leq r\leq n,1\leq s\leq p}$in$\mathcal{E}_{\lambda}$where $$(\mathfrak{w}_{1},…,\mathfrak{w}_{n})=(w_{1,i}\upharpoonright_{\text{crit}_{v}(w_{1,i},…,w_{n,i})},…,w_{n,i}\upharpoonright_{\text{crit}_{v}(w_{1,i},…,w_{n,i})})$$ and $$T(j_{1},…,j_{m},w_{1,i},…,w_{n,i})=x_{i}$$ for$1\leq i\leq p.$Therefore, there is some$\alpha<\lambda$with$\text{crit}_{v}(w_{1,s},...,w_{n,s})=\alpha$for$1\leq s\leq p$and where$w_{r,1}\equiv^{\alpha}\ldots\equiv^{\alpha}w_{r,p}$for$1\leq r\leq n$.$\mathbf{QED}\mathbf{Remark:}$The above theorem can be generalized further by considering the classes of rank-into-rank embeddings described in this paper.$\mathbf{Theorem:}$Suppose that there exists an I1 cardinal. Suppose furthermore that 1.$U_{1},…,U_{p},V_{1},…,V_{m}$and$(W_{r,s})_{1\leq r\leq n,1\leq s\leq p}$are unary terms in the language with function symbols$*,\circ$, 2.$L$is an$np+1$-ary term in the language with function symbols$*,\circ$, 3.$v$is a natural number, 4. There is some classical Laver table$A_{N}$where in$A_{N}$, we have $\mu=\text{crit}_{v}(W_{1,1}(1),…,W_{n,1}(1))=…=\text{crit}_{v}(W_{1,p}(1),…,W_{n,p}(1))<\text{crit}(2^{n}).$ 5. For all$N$, we have$W_{r,1}\equiv^{\mu}\ldots\equiv^{\mu}W_{r,p}(1)$for$1\leq r\leq n$, 6.$U_{1}(1)\equiv^{\mu^{+}}\ldots\equiv^{\mu^{+}}U_{p}(1)$. If$Y$is a finite reduced Laver-like LD-system, then let$\approx$be the relation on$Y^{<\omega}$where$(x_{1},...,x_{m})\approx(y_{1},...,y_{n})$if and only if$m=n$and whenever$\langle x_{1},...,x_{m}\rangle$and$\langle y_{1},...,y_{n}\rangle$both have more than$v+1$critical points, then there is an isomorphism $\iota:\langle x_{1},...,x_{m}\rangle/\equiv^{\text{crit}_{v}(x_{1},...,x_{m})}\rightarrow \langle y_{1},...,y_{n}\rangle/\equiv^{\text{crit}_{v}(y_{1},...,y_{n})}$ where$\iota([x_{i}])=[y_{i}]$for$1\leq i\leq n$. Then there is some finite reduced Laver-like LD-system$X$along with $x,(y_{r,s})_{1\leq r\leq n,1\leq s\leq p}\in X$ such that 1.$X$has a compatible linear ordering, 2. $(U_{s}(x)*V_{1}(x),…,U_{s}(x)*V_{m}(x),W_{1,s}(x),…,W_{n,s}(x))$ $\approx(V_{1}(x),…,V_{m}(x),y_{1,s},…,y_{n,s}),$ 3. ind 4. there is some critical point$\alpha$where$\text{crit}_{v}(y_{1,s},…,y_{n,s})=\alpha$for all$s$, and 5.$y_{r,1}\equiv^{\alpha}\ldots\equiv^{\alpha}y_{r,p}$. 6.$L(x,(y_{r,s})_{1\leq r\leq n,1\leq s\leq p})\neq 1$. Challenge I challenge the readers of this post to remove the large cardinal hypotheses from the above theorem (one may still use the freeness of subalgebras$\varprojlim_{n}A_{n}$and the fact that$2*_{n}x=2^{n}\Rightarrow 1*_{n}x=2^{n}$though). Added 2/4/2017 So it turns out that by taking stronger large cardinal axioms, one can induce a linear ordering on the algebras of elementary embeddings without having to resort to working in forcing extensions. We say that a cardinal$\delta$is an I1-tower cardinal if for all$A\subseteq V_{\delta}$there is some$\kappa<\delta$such that whenever$\gamma<\delta$there is some cardinal$\lambda<\delta$and non-trivial elementary embedding$j:V_{\lambda+1}\rightarrow V_{\lambda+1}$such that$\text{crit}(j)=\kappa$and where$j(\kappa)>\delta$and where$j(A)=A$. If$A$is a good enough linear ordering on$V_{\delta}$, then$A\cap V_{\lambda}$induces a compatible linear ordering the set of all elementary embeddings$j:V_{\lambda}\rightarrow V_{\lambda}$such that$j(A\cap V_{\gamma})=A\cap V_{j(\gamma)}$for all$\gamma<\lambda$. It is unclear where the I1-tower cardinals stand on the large cardinal hierarchy or whether they are even consistent. Added 2/12/2017 It turns out that we can directly show that if$j:V_{\lambda+1}\rightarrow V_{\lambda+1}$is a non-trivial elementary embedding, then there is a linear ordering$B$of$V_{\lambda}$where$j(B)=B$. In fact, if$j:V_{\lambda}\rightarrow V_{\lambda}$is a non-trivial elementary embedding,$\mathrm{crit}(j)=\kappa$, and$A$is a linear ordering of$V_{\lambda}$, then if we let$B=\bigcup_{n}j^{n}(A)$, then$B$is a linear ordering of$V_{\lambda}$and$j(B\cap V_{\gamma})=B\cap V_{j(\gamma)}$whenever$\gamma<\lambda$. In particular, if$j$extends to an elementary embedding$j^{+}:V_{\lambda+1}\rightarrow V_{\lambda+1}$, then$j^{+}(B)=B$. One can therefore prove the results about finite permutative LD-systems by working with the linear ordering that comes from$B$instead of the linear ordering that comes from the fact that$V_{\lambda}[G]\models V=HOD$in some forcing extension. One thing to be cautious of when one announces results before publication is that perhaps the proofs are not optimal and that one can get away with a simpler construction. Philosophy and research project proposals In the above results, we have worked in a model$V$where there are non-trivial maps$j:V_{\lambda}\rightarrow V_{\lambda}$and where$V_{\lambda}\models\text{V=HOD}$in order to obtain compatible linear orderings on finite algebras. However, if we work in different forcing extensions with rank-into-rank embeddings instead, then I predict that one may obtain from large cardinals different results about finite algebras. I predict that in the near future, mathematicians will produce many results about finite or countable self-distributive algebras using forcing and large cardinals where the large cardinal hypotheses cannot be removed. I also predict that rank-into-rank cardinals will soon prove results about structures that at first glance have little to do with self-distributivity. The question of consistency I must admit that I am not 100 percent convinced of the consistency of the large cardinals around the rank-into-rank level. My doubt is mainly due to the existence of finite reduced Laver-like LD-systems which cannot be subalgebras of$\mathcal{E}_{\lambda}/\equiv^{\gamma}$. However, if no inconsistency is found, then the results about finite or countable structures that arise from very large cardinals would convince me not only of the consistency of very large cardinals but also the existence of these very large cardinals. Therefore, people should investigate the finite algebras which arise from very large cardinals in order to quell all doubts about the consistency or the existence of these very large cardinals. Since it is much more likely that the Reinhardt cardinals are inconsistent than say the I1 cardinals are inconsistent, I also propose that we attempt to use the algebras of elementary embeddings to show that Reinhardt cardinals are inconsistent. I have not seen anyone investigate the self-distributive algebras of elementary embeddings at the Reinhardt level. However, I think that investigating the self-distributive algebras of elementary embeddings would be our best hope in proving that the Reinhardt cardinals are inconsistent. Featured ## Some new pages on Laver tables. I have added the following new pages on the classical Laver tables. The classical Laver tables can be given in ZFC a linear ordering such that the endomorphisms are monotone functions. When we reorder the classical Laver tables according to this compatible linear ordering we get the tables in the following link. http://boolesrings.org/jvanname/lavertables-database-classical-fullcompatibletabletoa5/ The following link gives the compressed versions of the multiplication table for the classical Laver tables reordered according to the compatible linear ordering. http://boolesrings.org/jvanname/lavertables-database-classical-alltablescompatibletoa10/ The compatible linear ordering on the classical Laver tables produces fractal like patterns that converge to a compact subset of the unit square. These images are found on the following link. http://boolesrings.org/jvanname/lavertables-visualization-classical-imagesofcompatibletables/ And this page gives images of the fractal pattern that comes from the classical Laver tables. http://boolesrings.org/jvanname/lavertables-visualization-classical-imagesoftables/ Hopefully I will be able to finish my long paper on the classical Laver tables over the next couple of months. Featured ## Why complete regularity rather than Hausdorff is the correct cutoff point between lower and higher separation axioms Disclaimer: By regular (completely regular) we mean regular (completely regular) and$T_{0}$In general topology, there are two different kinds of topological spaces. There are the topological spaces that satisfy higher separation axioms such as the 3 dimensional space that we live in; when most people think of general topology (especially analysts and algebraic topologists), they usually think of spaces which satisfy higher separation axioms. On the other hand, there are topological spaces which only satisfy lower separation axioms; these spaces at first glance appear very strange since sequences can converge to multiple points. They feel much different from spaces which satisfy higher separation axioms. These spaces include the Zariski topology, finite non-discrete topologies, and the cofinite topology. Even spaces that set theorists consider such as the ordinal topology on a cardinal$\kappa$or the Stone-Cech compactication$\beta\omega$satisfy higher separation axioms; after all,$\beta\omega$is the maximal ideal space of$\ell^{\infty}$. The general topology of lower separation axioms is a different field of mathematics than the general topology of higher separation axioms. However, can we in good conscience formally draw the line between the lower separation axioms and the higher separation axioms or is the notion of a higher separation axiom simply an informal notion? If there is a line, then where do we draw the line between these two kinds of topological spaces? As the sole owner of a silver badge in general topology on mathoverflow, I declare that the axiom complete regularity is the place where we need to draw the line between the lower separation axioms and the higher separation axioms. I can also argue that complete regularity is correct cutoff point by appealing to an authority greater than myself; the American Mathematical Society’s MSC-classification (the authority on classifying mathematics subjects) also delineates the lower separation axioms and the higher separation axioms at around complete regularity: 54D10-Lower separation axioms ($T_0$–$T_3$, etc.) 54D15-Higher separation axioms (completely regular, normal, perfectly or collectionwise normal, etc.) Let me now give a few reasons why complete regularity is the pivotal separation axiom. Hausdorffness is not enough. We need at least regularity. Hausdorff spaces are appealing to mathematicians because Hausdorff spaces are precisely the spaces where each net (or filter) converges to at most one point. However, the condition that every net converges to at most one point should not be enough for a space to feel like it satisfies higher separation axioms. Not only do I usually want filters to converge to at most one point, but I also want the closures of the elements in a convergent filter to also converge. However, this condition is equivalent to regularity.$\mathbf{Proposition}:$Let$X$be Hausdorff space. Then$X$is regular if and only if whenever$\mathcal{F}$is a filter that converges to a point$x$, the filterbase$\{\overline{R}\mid R\in\mathcal{F}\}$also converges to the point$x$. The next proposition formulates regularity in terms of the convergence of nets. The intuition behind the condition in the following proposition is that for spaces that satisfy higher separation axioms, if$(x_{d})_{d\in D},(y_{d})_{d\in D}$are nets such that$x_{d}$and$y_{d}$get closer and closer together as$d\rightarrow\infty$, and if$(y_{d})_{d\in D}$converges to a point$x$, then$(x_{d})_{d\in D}$should also converge to the same point$x$.$\mathbf{Proposition}$Let$X$be a Hausdorff space. Then$X$is regular if and only if whenever$(x_{d})_{d\in D}$is a net that does not converge to a point$x$, there are open neighborhoods$U_{d}$of$x_{d}$such that whenever$y_{d}\in U_{d}$for$d\in D$, the net$(y_{d})_{d\in D}$does not converge to the point$x$either.$\mathbf{Proof:}\rightarrow$Suppose that$(x_{d})_{d\in D}$does not converge to$x$. Then there is an open neighborhood$U$of$x$where$\{d\in D\mid x_{d}\not\in U\}$is cofinal in$D$. Therefore, there is some open set$V$with$x\in V\subseteq\overline{V}\subseteq U$. Therefore, let$U_{d}=(\overline{V})^{c}$whenever$d\in D$and$U_{d}$be an arbitrary set otherwise. Then whenever$y_{d}\in U_{d}$for each$d\in D$, the set$\{d\in D\mid y_{d}\not\in U\}$is cofinal in$D$. Therefore,$(y_{d})_{d\in D}$does not converge to$x$either.$\leftarrow$Suppose now that$X$is not regular. Then there is an$x\in X$and an open neighborhood$U$of$x$such that if$V$is an open set with$x\in V$, then$V\not\subseteq U$. Therefore, let$D$be a directed set and let$U_{d}$be an open neighborhood of$x$for each$d\in D$such that for all open neighborhoods$V$of$x$there is a$d\in D$so that if$e\geq d$, then$U_{d}\subseteq V$. Then let$x_{d}\in\overline{U_{d}}\setminus U$for all$d\in D$. Then$(x_{d})_{d\in D}$does not converge to$x$. Now suppose that$V_{d}$is a neighborhood of$x_{d}$for each$d\in D$. Then for each$d\in D$, we have$V_{d}\cap U_{d}\neq\emptyset$. Therefore, let$y_{d}\in V_{d}\cap U_{d}$. Then$(y_{d})_{d\in D}$does converge to$x$.$\mathbf{QED}$. Complete regularity is closed under most reasonable constructions If there is a main separation axiom that draws the line between higher separation axioms and lower separation axioms, then this main separation axiom should be closed under constructions such as taking subspaces and taking arbitrary products. Since every completely regular space is isomorphic to a subspace$[0,1]^{I}$, the crossing point between lower and higher separation axioms should be no higher than complete regularity. Not only are the completely regular spaces closed under taking products and subspaces, but the completely regular spaces are also closed under taking ultraproducts, the$P$-space coreflection, box products and other types of products, and various other constructions. Since we want our main separation axiom to be closed under most reasonable standard constructions and no lower than regularity, regularity and complete regularity are the only two candidates for our main separation axiom. We shall now find out why complete regularity is a better candidate than regularity for such a separation axiom. Completely regular spaces can be endowed with richer structure The completely regular spaces are precisely the spaces which can be given extra structure that one should expect to have in a topological space. While a topological space gives one the notion of whether a point is touching a set, a proximity gives on the notion of whether two sets are touching each other. Every proximity space has an underlying topological space. Proximity spaces are defined in terms of points and sets with no mention of the real numbers, but proximity spaces are always completely regular. Furthermore, the compatible proximities on a completely regular space are in a one-to-one correspondence with the Hausdorff compactifications of the space.$\mathbf{Theorem:}$A topological space is completely regular if and only if it can be endowed with a compatible proximity. The notion of a uniform space is a generalization of the notion of a metric space so that one can talk about concepts such as completeness, Cauchy nets, and uniform continuity in a more abstract setting. A uniform space gives one the notion of uniform continuity in the same way the a topological space gives one the notion of continuity. The definition of a uniform space is also very set theoretic, but it turns out that that every uniform space is induced by a set of pseudometrics and hence completely regular.$\mathbf{Theorem:}$A topological space is completely regular if and only if it can be endowed with a compatible uniformity. For example, it is easy to show that every$T_{0}$-topological group can be given a compatible uniformity. Therefore, since the topological groups can always be given compatible uniformities, every topological group (and hence every topological vector space) is automatically completely regular. Complete regularity is the proper line of demarcation between low and high separation axioms since the notions of a proximity and uniformity (which capture intuitive notions related to topological spaces without referring to the real numbers) induce precisely the completely regular spaces. The Hausdorff separation axiom generalizes poorly to point-free topology I realize that most of my readers probably have not yet been convinced of the deeper meaning behind point-free topology, but point-free topology gives additional reasons to prefer regularity or complete regularity over Hausdorffness. Most concepts from general topology generalize to point-free topology seamlessly including separation axioms (regularity, complete regularity, normality), connectedness axioms (connectedness, zero-dimensionality, components), covering properties (paracompactness,compactness, local compactness, the Stone-Cech compactification), and many other properties. The fact that pretty much all concepts from general topology extend without a problem to point-free topology indicates that point-free topology is an interesting and deep subject. However, the notion of a Hausdorff space does not generalize very well from point-set topology to point-free topology. There have been a couple attempts to generalize the notion of a Hausdorff space to point-free topology. For example, John Isbell has defined an I-Hausdorff frame to be a frame$L$such that the diagonal mapping$D:L\rightarrow L\oplus L$is a closed localic mapping ($\oplus$denotes the tensor product of frames). I-Hausdorff is a generalization of Hausdorffness since it generalizes the condition “$\{(x,x)\mid x\in X\}$is closed” which is equivalent to Hausdorffness. Dowker and Strauss have also proposed several generalizations of Hausdorffness. You can read more about these point-free separation axioms at Karel Ha’s Bachelor’s thesis here. These many generalizations of the Hausdorff separation axioms are not equivalent. To make matters worse, I am not satisfied with any of these generalizations of Hausdorffness to point-free topology. It is often the case that when an idea from general topology does not extend very well to point-free topology, then that idea relies fundamentally on points. For example, the axiom$T_{0}$is completely irrelevant to point-free topology since the axiom$T_{0}$is a pointed concept. Similarly, the axiom$T_{1}$is not considered for point-free topology since the notion of a$T_{1}$-space is also fundamentally a pointed notion rather than a point-free notion. For a similar reason, Hausdorffness does not extend very well to point-free topology since the definition of Hausdorffness seems to fundamentally rely on points. Just like in point-set topology, in point-free topology there is a major difference between the spaces which do not satisfy higher separation axioms and the spaces which do satisfy higher separation axioms. The boundary between lower separation axioms and higher separation axioms in point-set topology should therefore also extend to a boundary between lower separation axioms and higher separation axioms in point-free topology. Almost all the arguments for why complete regularity is the correct boundary between lower and higher separation axioms that I gave here also hold for point-free topology. Since Hausdorffness is not very well-defined in a point-free context, one should not regard Hausdorffness as the line of demarcation between lower separation axioms and higher separation axioms in either point-free topology or point-set topology. Conclusion Spaces that only satisfy lower separation axioms are good too. While completely regular spaces feel much different from spaces which are not completely regular, spaces which satisfy only lower separation axioms are very nice in their own ways. For example, non$T_{1}$-spaces have a close connection with ordered sets since every non-$T_{1}$-space has a partial ordering known as the specialization ordering. I do not know much about algebraic geometry, but algebraic geometers will probably agree that spaces which only satisfy the lower separation axioms are important. Frames (point-free topological spaces) which only satisfy lower separation axioms are also very nice from a lattice theoretic point of view; after all, frames are precisely the complete Heyting algebras. The underappreciation for complete regularity The reason why Hausdorffness is often seen as a more important separation axiom than complete regularity is that Hausdorffness is easy to define than complete regularity. The definition of Hausdorffness only refers to points and sets while complete regularity refers to points, sets, and continuous real-valued functions. Unfortunately, since the definition of complete regularity is slightly more complicated than the other separation axioms, complete regularity is not often given the credit it deserves. For example, in the hierarchy of separation axioms, complete regularity is denoted as$T_{3.5}$. It is not even given an integer. However, Hausdorffness is denoted as$T_{2}$, regularity is denoted as$T_{3}$and normality is denoted as$T_{4}$. Furthermore, when people often mention separation axioms they often fail to give complete regularity adequate attention. When discussing separation axioms in detail, one should always bring up and emphasize complete regularity. In practice, the Hausdorff spaces that people naturally comes across are always completely regular. I challenge anyone to give me a Hausdorff space which occurs in nature or has interest outside of general topology which is not also completely regular. The only Hausdorff spaces which are not completely regular that I know of are counterexamples in general topology and nothing more. Since all Hausdorff spaces found in nature are completely regular, complete regularity should be given more consideration than it is currently given. Featured ## The classical and generalized Laver tables can be computed quickly. The Laver tables have the noteworthy distinction of being the only structures which originally arose in modern set theory from very large cardinals but which have been studied experimentally using computer calculations. Among other things, these computer calculation can be used to generate images of fractals that resemble the Sierpinski triangle. Classical Laver tables computation Recall that the classical Laver table is the unique algebra$A_{n}=(\{1,…,2^{n}\},*_{n})$such that$x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$,$x*_{n}1=x+1$for$x<2^{n}$, and$2^{n}*_{n}1=1$. The operation$*_{n}$is known as the application operation. Even though the definition of the classical Laver tables is quite simple, the classical Laver tables are combinatorially very complicated structures, and there does not appear to be an efficient algorithm for computing the classical Laver tables like there is for ordinary multiplication. If$x,r$are positive integers, then let$(x)_{r}$denote the unique integer in$\{1,…,r\}$such that$x=(x)_{r}\,(\text{mod}\,r)$. The mappings$\phi:A_{n+1}\rightarrow A_{n},\iota:A_{n}\rightarrow A_{n+1}$defined by$\phi(x)=(x)_{\text{Exp}(2,n)}$and$\iota(x)=x+2^{n}$are homomorphisms between self-distributive algebras. If one has an efficient algorithm for computing$A_{n+1}$, then these homomorphisms allow one to compute$A_{n}$efficiently as well. Therefore, the problem of computing$A_{n}$gets more difficult as$n$gets larger. Randall Dougherty was able to write an algorithm that computes the application in$A_{48}$around 1995. This algorithm is outlined in his paper [1] and will be outlined in this post as well. So far no one has written any algorithm that improves upon Dougherty’s algorithm nor has anyone been able to compute even$A_{49}$. However, with enough effort, it may be possible to compute in$A_{n}$for$n\leq 96$with today’s computational resources, but I do not think that anyone is willing to exert the effort to compute$A_{96}$at this moment since in order to compute in$A_{96}$one needs to construct a rather large lookup table. The basic Laver table algorithms We shall begin by outlining three algorithms for computing in classical Laver tables, and after discussing these three algorithms for classical Laver table computation, we shall explain Dougherty’s algorithm. Algorithm 1: The easiest to write algorithm for computing the classical Laver tables is simply the algorithm that directly uses the definition of a classical Laver table. In other words, in this algorithm, we would evaluate$x*1$to$x+1$, and we evaluate$x*y$to$(x*(y-1))*(x+1)_{\text{Exp}(2,n)}$whenever$y>1$. This algorithm is extremely inefficient. This algorithm works for$A_{4}$on my computer, but I have not been able to compute in$A_{5}$using this algorithm. Even though this algorithm is terrible for computing the application in classical Laver tables, a modification of this algorithm can be used to calculate the application operation in generalized Laver tables very efficiently. Algorithm 2: In this algorithm, we fill up the entire multiplication table for$A_{n}$by computing$x*y$by a double induction which is descending on$x$and for each$x$we compute$x*y$by an ascending induction on$y$. Here is the code for constructing the multiplication for algorithm 2 in GAP (the multiplication table for$A_{n}$is implemented in GAP as a list of lists). table:=[]; table[2^n]:=[1..2^n]; for i in Reversed([1..2^n-1]) do table[i]:=[i+1]; for j in [2..2^n] do table[i][j]:=table[table[i][j-1]][i+1]; od; od;  I have been able to calculate$A_{13}$using this algorithm before running out of memory. The difference between algorithm 1 and algorithm 2 is analogous to two algorithms for computing the Fibonacci numbers. The following program fibslow in GAP for computing the Fibonacci numbers is analogous to algorithm 1. fibslow:=function(x) if x=1 or x=2 then return 1; else return fibslow(x-1)+fibslow(x-2); fi; end; This program takes about fibslow(x) many steps to compute fibslow(x) which is very inefficient. Algorithm 1 is inefficient for similar reasons. However, by computing the Fibonacci numbers in a sequence and storing the Fibonacci numbers in memory as a list, one obtains the following much more efficient algorithm fibfast for computing the Fibonacci numbers. fibfast:=function(x) local list,i; if x<3 then return 1; else list:=[1,1]; for i in [3..x] do list[i]:=list[i-1]+list[i-2]; od; return list[x]; fi; end; One can calculate the classical Laver tables much more quickly using algorithm 2 instead of using algorithm 1 for reasons similar to why the Fibonacci numbers are more easily computable using fibfast than fibslow. Algorithm 3: One of the first things that one notices when one observes the classical Laver tables is that the rows in the classical Laver tables are periodic, and this periodicity allows the classical Laver tables to be more quickly computed. Click here for the full multiplication tables for the Laver tables up to$A_{5}$. Algorithm 3 is similar to algorithm 2 except that one computes only one period for each row. For example, instead of computing the entire 2nd row$[3,12,15,16,3,12,15,16,3,12,15,16,3,12,15,16]$in$A_{4}$, in algorithm 3 one simply computes$[3,12,15,16]$once and observe that$2*_{4}x=2*_{4}(x)_{4}$whenever$1\leq x\leq 16$. Using this algorithm, I am able to calculate up to$A_{22}$on a modern computer before running out of memory. If one compresses the data computed by this algorithm, then one should be able to calculate up to$A_{27}$or$A_{28}$before running out of memory. The lengths of the periods of the rows in classical Laver tables are all powers of 2 and the lengths of the periods of the rows in the classical Laver tables are usually quite small. Let$o_{n}(x)$denote the least natural number such that$x*_{n}o_{n}(x)=2^{n}$. The motivation behind$o_{n}(x)$lies in the fact that$x*_{n}y=x*_{n}z$iff$y=z(\text{mod}\,\text{Exp}(2,o_{n}(x)))$, so$2^{o_{n}(x)}$is the period of the$x$-th row in$A_{n}$. The maximum value of$o_{n}(x)$is$n$, but in general$o_{n}(x)$is usually quite small. We have$E(o_{10}(x))=2.943$,$E(o_{20}(x))=3.042$, and$E(o_{48}(x))=3.038$(Here$E$denotes the expected value.$E(o_{48}(x))$has been calculated from a random sample from$A_{48}$of size 1000000). Therefore, since$o_{n}(x)$is usually small, one can calculate and store the$x$-th row in memory without using too much space or time even without compressing the computed data. Dougherty’s algorithm Dougherty’s algorithm for computing in the classical Laver tables is based on the following lemmas.$\mathbf{Lemma}$Suppose that$t\leq n$and$L:A_{n-t}\rightarrow A_{n}$is the mapping defined by$L(x)=x\cdot 2^{t}$. If the mapping$L$is a homomorphism, then 1.$2^{t}x*_{n}y=(y)_{\text{Exp}(2,t)}-2^{t}+2^{t}\cdot(x*_{n-t}(\frac{y-(y)_{\text{Exp}(2,t)}}{\text{Exp}(2,t)}+1))$whenever$1\leq x\leq 2^{n-t}$and$1\leq y\leq 2^{n}$and 2.$2^{t}x\circ_{n}y=2^{t}x+y$whenever$1\leq y<2^{t}$and$1\leq x<2^{n-t}$. The following result by Dougherty gives examples for when the premise of the above Lemma holds.$\mathbf{Theorem}$(Dougherty) Suppose that$t=2^{r}$for some$r$and$n\leq 3t$. Then the mapping$L:A_{n-t}\rightarrow A_{n}$defined by$L(x)=x\cdot 2^{t}$is a homomorphism . More generally Dougherty has proven the following result. Assume that$s\leq n$and$n-s\leq Gcd(2^{\infty},2s)$. Then the mapping$L:A_{n-s}\rightarrow A_{n}$defined by$L(x)=x\cdot 2^{s}$is a homomorphism. Now assume that$t=2^{r},n\leq 3t$and that$x*_{n}y$has already been computed whenever$x\leq 2^{t},y\leq 2^{n}$. Then we may compute$x*_{48}y$for any$x,y\in A_{n}$by using the following algorithm: 1. If$x<2^{t}$then$x*_{n}y$has already been computed so there is no work to be done here. 2. If$x$is a multiple of$2^{t}$, then we may use Dougherty’s theorem to compute$x*_{n}y$and we may use recursion on this same algorithm to compute the operation$*_{n-t}$. 3. Suppose that the above cases do not hold. Then by Dougherty’s theorem we have$x=(x-(x)_{\text{Exp}(2,t)})\circ(x)_{\text{Exp}(2,t)}$. Therefore, we evaluate$x*_{n}y$using the fact that$x*_{n}y=((x-(x)_{\text{Exp}(2,t)})\circ_{n}(x)_{\text{Exp}(2,t)})*_{n}y=((x-(x)_{\text{Exp}(2,t)})*_{n}((x)_{\text{Exp}(2,t)}*_{n}y)$. Using the above algorithm and the precomputed values$x*_{48}y$for$x\leq 2^{16}$, I have been able to compute 1,200,000 random instances of$x*_{48}y$in a minute on my computer. One could also easily compute in$A_{48}$by hand using this algorithm with only the precomputed values$x*_{48}y$where$x\leq 2^{16}$for reference (this reference can fit into a book). Dougherty’s algorithm for computing the clasical Laver tables has been implemented here. Precomputing the$x$-th row for$x\leq 2^{t}$. In order for Dougherty’s algorithm to work for$A_{n}$, we must first compute the$x$-th row in$A_{n}$for$x\leq 2^{t}$. However, one can compute this data by induction on$n$. In particular, if$n<3t$and one has an algorithm for computing$A_{n}$, then one can use Dougherty's algorithm along with a suitable version of algorithm 3 to compute the$x$-th row in$A_{n+1}$for$x\leq 2^{t}$. I was able to compute from scratch$x*_{48}y$for$x\leq 2^{16}$in 757 seconds. Generalized Laver tables computation Let$n$be a natural number and let$A$be a set. Let$A^{+}$be the set of all non-empty strings over the alphabet$A$. Then let$(A^{\leq 2^{n}})^{+}=\{\mathbf{x}\in A^{+}:|\mathbf{x}|\leq 2^{n}\}$. Then there is a unique self-distributive operation$*$on$(A^{\leq 2^{n}})^{+}$such that$\mathbf{x}*a=\mathbf{x}a$whenever$|\mathbf{x}|<2^{n},a\in A$and$\mathbf{x}*\mathbf{y}=\mathbf{y}$whenever$|\mathbf{x}|=2^{n}$. The algebra$((A^{\leq 2^{n}})^{+},*)$is an example of a generalized Laver table. If$|A|=1$, then$(A^{\leq 2^{n}})^{+}$is isomorphic to$A_{n}$. If$|A|>1$, then the algebra$(A^{\leq 2^{n}})^{+}$is quite large since$|(A^{\leq 2^{n}})^{+}|=|A|\cdot\frac{|A|^{\text{Exp}(2,n)}-1}{|A|-1}$. Let$\mathbf{x}[n]$denote the$n$-th letter in the string$\mathbf{x}$(we start off with the first letter instead of the zero-th letter). For example,$\text{martha}[5]=\text{h}$. When computing the application operation in$(A^{\leq 2^{n}})^{+}$, we may want to compute the entire string$\mathbf{x}*\mathbf{y}$or we may want to compute a particular position$(\mathbf{x}*\mathbf{y})[\ell]$. These two problems are separate since it is much easier to compute an individual position$(\mathbf{x}*\mathbf{y})[\ell]$than it is to compute the entire string$\mathbf{x}*\mathbf{y}$, but computing$\mathbf{x}*\mathbf{y}$by calculating each$(\mathbf{x}*\mathbf{y})[\ell]$individually is quite inefficient. We shall present several algorithms for computing generalized Laver tables starting with the most inefficient algorithm and then moving on to the better algorithms. These algorithms will all assume that one already has an efficient algorithm for computing the application operation in the classical Laver tables. Algorithm A: If$x,y\in\{1,…,2^{n}\}$, then let$FM_{n}^{+}(x,y)$denote the integer such that in$(A^{\leq 2^{n}})^{+}$if$FM_{n}^{+}(x,y)>0$then$(a_{1}…a_{x}*b_{1}…b_{2^{n}})[y]=b_{FM_{n}^{+}(x,y)}$and if$FM_{n}^{+}(x,y)<0$then$(a_{1}...a_{x}*b_{1}...b_{2^{n}})[y]=a_{-FM_{n}^{+}(x,y)}$. If one has an algorithm for computing$FM_{n}^{+}(x,y)$, then one can compute the application operation simply by referring to$FM_{n}^{+}(x,y)$. The function$FM_{n}^{+}$can be computed using the same idea which we used in algorithm 2 to calculate the classical Laver tables. In particular, in this algorithm, we compute$FM_{n}^{+}(x,y)$by a double induction on$x,y$which is descending on$x$and for each$x$the induction is ascending on$y$. I was able to calculate up to$FM_{13}^{+}$using this algorithm. Using the Sierpinski triangle fractal structure of the final matrix, I could probably compute up to$FM_{17}^{+}$or$FM_{18}^{+}$before running out of memory. Algorithm B: Algorithm B for computing in the generalized Laver tables is a modified version of algorithm 1. Counterintuitively, even though algorithm 1 is very inefficient for calculating in the classical Laver tables, algorithm B is very efficient for computing the application operation in generalized Laver tables. If$\mathbf{x}$is a string, then let$|\mathbf{x}|$denote the length of the string$\mathbf{x}$(for example,$|\text{julia}|=5$). If$\mathbf{x}$is a non-empty string and$n$a natural number, then let$(\mathbf{x})_{n}$denote the string where we remove the first$|\mathbf{x}|-(|\mathbf{x}|)_{n}$elements of$\mathbf{x}$and keep the last$(|\mathbf{x}|)_{n}$elements in the string$\mathbf{x}$. For example,$(\text{elizabeth})_{5}=\text{beth}$and$(\text{solianna})_{4}=\text{anna}$. One calculates$\mathbf{x}*\mathbf{y}$in$(A^{\leq 2^{n}})^{+}$using the following procedure: 1. If$|\mathbf{x}|=2^{n}$then$\mathbf{x}*\mathbf{y}=\mathbf{y}$. 2.$|\mathbf{y}|>o_{n}(|\mathbf{x}|)$, then$\mathbf{x}*\mathbf{y}=\mathbf{x}*(\mathbf{y})_{\text{Exp}(2,o_{n}(|\mathbf{x}|))}$. In this case, one should therefore evaluate$\mathbf{x}*\mathbf{y}$to$\mathbf{x}*(\mathbf{y})_{\text{Exp}(2,o_{n}(|\mathbf{x}|))}$. 3. If$|\mathbf{x}|*_{n}|\mathbf{y}|=|\mathbf{x}|+|\mathbf{y}|$and$|\mathbf{y}|\leq \text{Exp}(2,o_{n}(|\mathbf{x}|))$, then$\mathbf{x}*_{n}\mathbf{y}=\mathbf{x}\mathbf{y}$. Therefore, one should evaluate$\mathbf{x}*_{n}\mathbf{y}$to$\mathbf{x}\mathbf{y}$in this case. 4. If 1-3 do not hold and$\mathbf{y}=\mathbf{z}a$the one should evaluate$\mathbf{x}*_{n}\mathbf{y}$to$(\mathbf{x}*_{n}\mathbf{z})*\mathbf{x}a$. It is not feasible to compute the entire string$\mathbf{x}*\mathbf{y}$in$(A^{\leq 2^{n}})^{+}$when$n$is much larger than 20 due to the size of the outputs. Nevertheless, it is very feasible to compute the symbol$(\mathbf{x}*\mathbf{y})[\ell]$in$(A^{\leq 2^{n}})^{+}$whenever$n\leq 48$by using a suitable modification of algorithm B. I have been able to compute on my computer using this suitable version of algorithm B on average about 3000 random values of$(\mathbf{x}*\mathbf{y})[\ell]$in$(A^{\leq 2^{48}})^{+}$in a minute. To put this in perspective, it took me on average about 400 times as long to compute a random instance of$(\mathbf{x}*\mathbf{y})[\ell]$in$(A^{\leq 2^{48}})^{+}$than it takes to compute a random instance of$x*y$in$A_{48}$. I have also been able to compute on average 1500 values of$(\mathbf{x}*\mathbf{y})[\ell]$in$(A^{\leq 2^{48}})^{+}$per minute where the$\mathbf{x},\mathbf{y},\ell$are chosen to make the calculation$(\mathbf{x}*\mathbf{y})[\ell]$more difficult. Therefore, when$\mathbf{x},\mathbf{y},\ell$are chosen to make the calculation$(\mathbf{x}*\mathbf{y})[\ell]$more difficult, it takes approximately 800 times as long to calculate$(\mathbf{x}*\mathbf{y})[\ell]$than it takes to calculate an entry in$A_{48}$. This is not bad for calculating$(\mathbf{x}*\mathbf{y})$to an arbitrary precision in an algebra of cardinality about$10^{10^{13.928}}$when$|A|=2$. Algorithm C: Algorithm C is a modification of algorithm B that uses he same ideas in Dougherty’s method of computing in classical Laver tables to compute in the generalized Laver tables$(A^{\leq 2^{n}})^{+}$more efficiently.$\mathbf{Theorem}$Suppose that$L:A_{n-t}\rightarrow A_{n}$is the mapping defined by$L(x)=x\cdot 2^{t}$for all$x\in A_{n-t}$and$L$is a homomorphism. Define a mapping$\iota:((A^{2^{t}})^{\leq 2^{n-t}})^{+}\rightarrow(A^{\leq 2^{n}})^{+}$by letting$\iota((a_{1,1},…,a_{1,2^{t}})…(a_{r,1},…,a_{r,2^{t}}))=a_{1,1},…,a_{1,2^{t}}…a_{r,1},…,a_{r,2^{t}}$. Then$\iota$is an injective homomorphism between generalized Laver tables. More generally, we have the following result.$\mathbf{Theorem}$Suppose that$L:A_{n-t}\rightarrow A_{n}$is the mapping defined by$L(x)=x\cdot 2^{t}$and the mapping$L$is a homomorphism. Then 1. Suppose that$|\mathbf{x}|$is a multiple of$2^{t}$,$\mathbf{x}=(x_{1,1}…x_{1,2^{t}})…(x_{u,1}…x_{u,2^{t}})$, and$\mathbf{y}=(y_{1,1}…y_{1,2^{t}})…(y_{v-1,1}…y_{v-1,2^{t}})(y_{v,1}…y_{v,w})$. Furthermore, suppose that $$\langle x_{1,1},…,x_{1,Exp(2,t)}\rangle…\langle x_{u,1},…,x_{u,Exp(2,t)}\rangle*_{n-t} \langle y_{1,1},…,y_{1,Exp(2,t)}\rangle…\langle y_{1,1},…,y_{1,Exp(2,t)}\rangle\langle y_{v,1},…,y_{v,w}\rangle$$ $$=\langle z_{1,1},…,z_{1,Exp(2,t)}\rangle…\langle z_{p-1,1},…,z_{p-1,Exp(2,t)}\rangle\langle z_{p,1},…,z_{p,w}\rangle.$$ Then$\mathbf{x}*_{n}\mathbf{y}=(z_{1,1}…z_{1,Exp(2,t)})…(z_{p-1,1}…z_{p-1,Exp(2,t)})(z_{p,1}…z_{p,w}).$2. Suppose that$|\mathbf{x}|$is a multiple of$2^{t}$and$|\mathbf{x}|<2^{n}$. Furthermore, suppose that$1<|\mathbf{y}|<2^{t}$. Then$\mathbf{x}\circ_{n}\mathbf{y}=\mathbf{x}\mathbf{y}.$One can compute$\mathbf{x}*_{n}\mathbf{y}$recursively with the following algorithm: 1. First we select a natural number$t$with$t\leq n$and$n-t\leq\text{Gcd}(2^{\infty},2t)$. 2. If$|\mathbf{y}| > o_{n}(|\mathbf{x}|)$, then evaluate$\mathbf{x}*_{n}\mathbf{y}$to$\mathbf{x}*_{n}(\mathbf{y})_{\text{Exp}(2,o_{n}(|\mathbf{x}|))}$. 3. if$|\mathbf{x}|=2^{n}$then evaluate$\mathbf{x}*_{n}\mathbf{y}$to$\mathbf{y}$. 4. if$|\mathbf{x}| < 2^{t}$then evaluate$\mathbf{x}*_{n}\mathbf{y}a$to$(\mathbf{x}*_{n}\mathbf{y})*\mathbf{x}a.$5. Assume$|\mathbf{x}|$is a multiple of$2^{t}$. Suppose that$\mathbf{x}=x_{1,1}…x_{1,2^{t}}…x_{u,1}…x_{u,2^{t}}$and$\mathbf{y}=y_{1,1}…y_{1,2^{t}}…y_{v-1,1}…y_{v-1,2^{t}}y_{v,1}…y_{v,w}$. Suppose also that$\langle x_{1,1},…,x_{1,2^{t}}\rangle…\langle x_{u,1},…,x_{u,2^{t}}\rangle*_{n-t}
\langle y_{1,1},…,y_{1,2^{t}}\rangle…\langle y_{v-1,1},…,y_{v-1,2^{t}}\rangle\langle y_{v,1},…,y_{v,w}\rangle=\langle z_{1,1},…,z_{1,2^{t}}\rangle…\langle z_{p-1,1},…,z_{p-1,2^{t}}\rangle\langle z_{p,1},…,z_{p,w}\rangle$. Then evaluate$\mathbf{x}*_{n}\mathbf{y}$to$z_{1,1}…z_{1,2^{t}}…z_{p-1,1}…z_{p-1,2^{t}}z_{p,1}…z_{p,w}$. 6. Assume now that 1-5 do not hold and$2^{t}<|\mathbf{x}|<2^{n}$. Then let$\mathbf{x}=\mathbf{x}_{1}\mathbf{x}_{2}$where$\mathbf{x}_{2}=(\mathbf{x})_{\text{Exp}(2,t)}$. Then$\mathbf{x}*_{n}\mathbf{y}=(\mathbf{x}_{1}\circ_{n}\mathbf{x}_{2})*_{n}\mathbf{y}= \mathbf{x}_{1}*_{n}(\mathbf{x}_{2}*_{n}\mathbf{y})$(The composition in$A^{\leq 2^{n}}$is a partial function). We therefore evaluate$\mathbf{x}*_{n}\mathbf{y}$to$\mathbf{x}_{1}*_{n}(\mathbf{x}_{2}*_{n}\mathbf{y})$. As with algorithms A and B, there is a local version of algorithm C that quickly computes the particular letter$\mathbf{x}*\mathbf{y}[\ell]$. Both the local and the global versions of algorithm C are about 7 or so times faster than the corresponding version of algorithm B. Algorithm C for computing generalized Laver tables has been implemented online here. Conclusion The simple fact that calculating$(\mathbf{x}*\mathbf{y})[\ell]$is apparantly hundreds of times more difficult than calculating in$A_{48}$is rather encouraging since this difficulty in calculation suggests that the generalized Laver tables have some combinatorial intricacies that go far beyond the classical Laver tables. These combinatorial intricacies can be seen in the data computed from the generalized Laver tables. Much knowledge and understanding can be gleaned from simply observing computer calculations. Dougherty’s result which allowed one to compute$A_{48}$in the first place was proven only because computer calculations allowed Dougherty to make the correct conjectures which were necessary to obtain the results. Most of my understanding of the generalized Laver tables$(A^{\leq 2^{n}})^{+}\$ has not come from sitting down and proving theorems, but from observing the data computed from the generalizations of Laver tables. There are many patterns within the generalized Laver tables that can be discovered through computer calculations.

While the problems of computing the generalized Laver tables have been solved to my satisfaction, there are many things about generalizations of Laver tables which I would like to compute but for which I have not obtained an efficient algorithm for computing. I am currently working on computing the fundamental operations in endomorphic Laver tables and I will probably make a post about endomorphic Laver table computation soon.

All of the algorithms mentioned here have been implemented by my using GAP and they are also online here at boolesrings.org/jvanname/lavertables. While the problems of computing the generalized Laver tables have been solved to my satisfaction, there are many things about generalizations of Laver tables which I would like to compute but for which I have not obtained an efficient algorithm for computing.

I must mention that I this project on the generalizations of Laver tables is the first mathematical project that I have done which makes use of computer calculations.

1. Critical points in an algebra of elementary embeddings, II. Randall Dougherty. 1995.