Author Archives: apgoucher

Associative universal gates

Posted on August 19, 2020 by apgoucher

The Boolean function NAND is famously universal, in that any Boolean function on n inputs and m outputs can be implemented as a circuit composed entirely of NAND gates. For example, the exclusive-or operation, A XOR B, can be written … Continue reading →

Posted in Uncategorized | 3 Comments

Another two rational dodecahedra

Posted on August 5, 2020 by apgoucher

Since finding one rational dodecahedron inscribed in the unit sphere, I decided to port the search program to CUDA so that it can run on a GPU and thereby search a larger space in a reasonable amount of time. Firstly, … Continue reading →

Posted in Uncategorized | 14 Comments

Banach-Tarski and the Axiom of Choice

Posted on August 3, 2020 by apgoucher

Tomasz Kania and I recently coauthored a paper about Banach spaces. The paper makes extensive use of the axiom of choice, involving a transfinite induction in the proof of Theorem B as well as several appeals to the fact that … Continue reading →

Posted in Uncategorized | Leave a comment

Rational dodecahedron inscribed in unit sphere

Posted on July 25, 2020 by apgoucher

Moritz Firsching asked in 2016 whether there exists a dodecahedron, combinatorially equivalent to a regular dodecahedron, with rational vertices lying on the unit sphere. The difficulty arises from the combination of three constraints: The twelve pentagonal faces must all be … Continue reading →

Posted in Uncategorized | 5 Comments

Fast-growing functions revisited

Posted on July 24, 2020 by apgoucher

There have been many exciting results proved by members of the Googology wiki, a website concerned with fast-growing functions. Some of the highlights include: Wythagoras’s construction of an 18-state Turing machine which takes more than Graham’s number of steps to … Continue reading →

Posted in Fast-growing functions | 8 Comments

4-input 2-output Boolean circuits

Posted on June 30, 2020 by apgoucher

In 2005, Donald Knuth determined the minimum cost required to implement each of the 2^32 different 5-input 1-output Boolean functions as a circuit composed entirely of: 2-input gates (there are 16 of these), each of which has cost 1; 1-input … Continue reading →

Posted in Boolean optimisation | 5 Comments

That group of order 348364800

Posted on June 14, 2020 by apgoucher

In nested lattices, we talked about the E8 lattice and its order-696729600 group of origin-preserving symmetries. In minimalistic quantum computation, we saw that this group of 8-by-8 real orthogonal matrices is generated by a set of matrices which are easily … Continue reading →

Posted in Uncategorized | 3 Comments

More quantum gates and lattices

Posted on May 20, 2020 by apgoucher

The previous post ended with unanswered questions about describing the Conway group, Co0, in terms of quantum gates with dyadic rational coefficients. It turned out to be easier than expected, although the construction is much more complicated than the counterpart … Continue reading →

Posted in Uncategorized | 2 Comments

Minimalistic quantum computation

Posted on May 10, 2020 by apgoucher

In the usual ‘circuit model’ of quantum computation, we have a fixed number of qubits, {q1, q2, …, qn}, and allow quantum gates to act on these qubits. The diagram below shows a Toffoli gate on the left, and an … Continue reading →

Posted in Uncategorized | 11 Comments

Nested lattices

Posted on May 3, 2020 by apgoucher

1, 240, 2160, 6720, 17520, 30240, 60480, 82560, 140400, … These terms count the number of points at distance from the origin in the E8 lattice, a highly symmetric arrangement of points which Maryna Viazovska recently (in 2016) proved is … Continue reading →

Posted in Uncategorized | 3 Comments