Kopp’s Whisky Prize

At the end of his recent CodEx talk, Gene Kopp posed a problem with a prize attached to it. I was excited to learn about this, so I enlisted both Gene Kopp and Mark Magsino to help me write this blog entry to provide additional details.

First, let denote the set of matrices in such that

Here, denotes conjugate transpose, denotes entrywise squared modulus, denotes the identity matrix, and denotes the all-ones matrix. In words, the columns of form an equiangular tight frame (ETF) for of size .

Polymath16, sixteenth thread: Writing the paper and chasing down loose ends, II

This is the sixteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

The paper writing has found a second wind between Philip Gibbs, Aubrey de Grey, Jaan Parts and Tom Sirgedas. For reference, I wanted to compile a list of related publications that have emerged since starting our project. (Feel free to any references I missed in the comments.) There has certainly been a bit of activity since Aubrey’s paper first hit the arXiv two years ago!

P. Ágoston, Probabilistic formulation of the Hadwiger–Nelson problem.

F. Bock, Epsilon-colorings of strips, Acta Math. Univ. Comenianae (2019) 88: 469-473.

G. Exoo, D. Ismailescu, A 6-chromatic two-distance graph in the plane, arXiv preprint arXiv:1909.13177 (2019).

G. Exoo, D. Ismailescu, The chromatic number of the plane is at least 5: A new proof, Discrete & Computational Geometry (2019): 1-11.

G. Exoo, D. Ismailescu, The Hadwiger-Nelson problem with two forbidden distances, arXiv preprint arXiv:1805.06055 (2018).

N. Frankl, T. Hubai, D. Pálvölgyi, Almost-monochromatic sets and the chromatic number of the plane, arXiv preprint arXiv:1912.02604 (2019).

M. J. H. Heule, Computing a Smaller Unit-Distance Graph with Chromatic Number 5 via Proof Trimming, arXiv preprint arXiv:1907.00929 (2019).

M. J. H. Heule, Searching for a Unit-Distance Graph with Chromatic Number 6, SAT COMPETITION 2018: 66.

M. J. H. Heule, Trimming Graphs Using Clausal Proof Optimization, In International Conference on Principles and Practice of Constraint Programming, pp. 251-267. Springer, Cham, 2019.

J. Parts. A small 6-chromatic two-distance graph in the plane, Geombinatorics, vol. 29, No. 3 (2020), pp.111-115.

J. Parts. Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane, Geombinatorics, vol. 29, No. 4 (2020), pp.137-166.

Polymath16, fifteenth thread: Writing the paper and chasing down loose ends

This is the fifteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

At this point, much of the effort is transitioning to the writing stage, which is taking place on Overleaf. See this comment to obtain writing privileges for the paper. This thread can be used to discuss the write-up as well as any remaining research items.

Spherical codes and designs

Later this month, Hans Parshall will participate in a summer school on “Sphere Packings and Optimal Configurations.” In preparation for this event, Hans was assigned the task of writing lecture notes that summarize the main results of the following paper:

P. Delsarte, J. M. Goethals, J. J. Seidel,

Spherical codes and designs,

Geometriae Dedicata 6 (1977) 363–388.

I found Hans’ notes to be particularly helpful, so I’m posting them here with his permission. I’ve lightly edited his notes for formatting and hyperlinks.

Without further ado:

Game of Sloanes

Emily King recently launched an online competition to find the best packings of points in complex projective space. The so-called Game of Sloanes is concerned with packing points in for and for . John Jasper, Emily King and I collaborated to make the baseline for this competition by curating various packings from the literature and then numerically optimizing sub-optimal packings. See our paper for more information:

J. Jasper, E. J. King, D. G. Mixon, Game of Sloanes: Best known packings in complex projective space

If you have a packing that improves upon the current leader board, you can submit your packing to the following email address:

asongofvectorsandangles [at] gmail [dot] com

In this competition, you can win money if you find a new packing that achieves equality in the Welch bound; see this paper for a survey of these so-called equiangular tight frames (ETFs).

Some news regarding the Paley graph

Let denote the field with elements, and let denote the multiplicative subgroup of quadratic residues. For each prime , we consider the Paley graph with vertex set , where two vertices are adjacent whenever their difference resides in . For example, the following illustration from Wikipedia depicts :

The purpose of this blog entry is to discuss recent observations regarding the Paley graph.

Polymath16, fourteenth thread: Automated graph minimization?

This is the fourteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

The biggest development in the previous thread:

• The smallest known 5-chromatic unit distance graph has 510 vertices and 2508 edges.

The method used for finding this graph is vaguely described here and here. It seems that the method is currently more of an art form than an algorithm. A next step might be to automate the art away, code up any computational speedups that are available, and then throw more computing power at the problem.

Algebra, geometry, and combinatorics of subspace packings

Last week, the SIAM Conference on Applied Algebraic Geometry hosted a session on “Algebra, geometry, and combinatorics of subspace packings,” organized by Emily King and myself. Sadly, I wasn’t able to attend, but thankfully, most of the speakers gave me permission to post their slides on my blog. Here’s the lineup:

Emily King — Algebra, Geometry, and Combinatorics of Subspace Packings

Romanos Malikiosis — Group frames, full spark, and other topics

John Jasper — Equiangular tight frames from nonabelian groups

Gene Kopp — SIC-POVM existence and the Stark conjectures

Polymath16, thirteenth thread: Bumping the deadline?

This is the thirteenth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

Interest in this project has spiked since approaching (and passing) our original deadline of April 15. For this reason, I propose we extend the deadline to October 15, 2019. We can discuss this in the Polymath proposal page.

Here are some recent developments:

• The fractional chromatic number of the plane is at least 3.98.
• The smallest known 5-chromatic unit distance graph has 529 vertices and 2630 edges.
• Dömötör has an exciting idea for finding a human-verifiable proof that the chromatic number of the plane is at least 5.

I’m interested to see if this last point has legs!

Polymath16, twelfth thread: Year in review and future plans

This is the twelfth “research” thread of the Polymath16 project to make progress on the Hadwiger–Nelson problem, continuing this post. This project is a follow-up to Aubrey de Grey’s breakthrough result that the chromatic number of the plane is at least 5. Discussion of the project of a non-research nature should continue in the Polymath proposal page. We will summarize progress on the Polymath wiki page.

Activity on this project has slowed considerably, as we’ve gone 6 months without having to roll over to a new thread. As mentioned in the original thread, the deadline for this project is April 15, 2019, so we only have a couple of weeks remaining. Dömötör and Aubrey took the time to summarize the highlights of what we’ve accomplished in the last year (see below). While we don’t have a single killer result to publish, there are several branches of minor results that warrant publication. Feel free to comment on additional results that were missed in the summaries below, as well as possible venues for publication.