Assorted topics

Complex Projective 4-Space 2021-01-31

This is a digest of things that have happened this month, but which are individually too small to each warrant a separate cp4space post. Firstly, there have been a couple of exciting results in the field of combinatorics:

The Erdős-Faber-Lovász conjecture is proved for sufficiently large hypergraphs by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.
A special case of another conjecture by Erdős has been established by Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl.

Also, the functional analysis paper I coauthored with Tomasz Kania has been accepted by the journal Studia Mathematica. This is my first ever article in a peer-reviewed mathematics journal, finally giving me a finite Erdős number (specifically 4)! Many thanks go to the anonymous reviewer for his or her feedback.

The article on the Stockfish NNUE architecture reached the top position on Hacker News, resulting in a disproportionate amount of cp4space traffic (indeed, more views in a single hour than is typical in an entire week).

One quadrillion objects

The Catagolue census of objects arising from random 16-by-16 soups in Conway’s Game of Life has surpassed 10^15 objects. The total number of soups explored in this census is 46 trillion. One of these soups, discovered by Dylan Chen, takes a record-breaking 52513 generations to stabilise.

The parallel GPU-assisted soup search has examined nearly four times as many soups, specifically 164 trillion soups, but due to the search methodology not every object is censused. (Specifically, only soups that last sufficiently long or produce high-period oscillators or rare spaceships are rerun on the CPU and censused; ‘boring’ soups are discarded by the prefiltering stage on the GPU.)

Recent highlights of the GPU soup search include two variants of a period-7 oscillator, one by me and the other by Rob Liston. There was also a 50093-generation soup by Liston which held the longevity record for one week before being surpassed by Dylan Chen’s aforementioned 52513-generation soup.

Taken together, the CPU and GPU searches have simulated 210 trillion random 16-by-16 soups; you can view the collective results here.

BN curves where n has low Hamming weight

We previously discussed Barreto-Naehrig curves and the problem of trying to find curves where the (prime) number of points n on the elliptic curve has a low Hamming weight.

If x is the sum of two powers of 2, the Hamming weight of n is guaranteed to be at most 35, and heuristics based on the prime number theorem suggest that there should be infinitely many such values of x for which p and n are both prime. For example, $x = 2^{250} + 2^4$ is an example.

The situation is different for Hamming weights strictly below 35. Instead of a two-parameter family such as $x = 2^a + 2^b$ , there appear to only be a finite collection of one-parameter families, and the same heuristics suggest that there are only finitely many examples. In particular, the largest such x that I could find was $x = 33 \times 2^{267}$ , for which the Hamming weight of n is 34.

A particularly nice choice of x (in that it gives a reasonable security level without being too large) is $x = 47 \times 2^{56}$ . The resulting values of n and p are both 252-bit primes, and the Hamming weight of n is 35. Here are the values in hexadecimal:

x = 0x2f00000000000000p = 0xa787d240000000039081c0000000000cf180000000000011a00000000000001n = 0xa787d240000000039081c00000000009b520000000000011a00000000000001

If you’re willing to have a smaller bit-length, then $x = 17 \times 2^{43}$ provides a 194-bit prime where the Hamming weight of n is merely 29. Also, because x is congruent to 1 (mod 3), it follows that p is congruent to 4 (mod 9) and cube-roots can be computed efficiently in $\mathbb{F}_p$ as described in Appendix B of the paper introducing BN curves:

x = 0x880000000000p = 0x2de124000000565c800000006c60000000003300000000001n = 0x2de124000000565c800000005148000000003300000000001

The security level is quite mediocre, though: it only offers 96-bit security against Pollard’s rho algorithm for discrete log.