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 $n$ points in $\mathbf{CP}^{d-1}$ for $d\in\{2,\ldots,7\}$ and for $n\in\{d+2,\ldots,49\}$. 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 $\mathbb{F}_p$ denote the field with $p$ elements, and let $Q_p$ denote the multiplicative subgroup of quadratic residues. For each prime $p\equiv 1\bmod 4$, we consider the Paley graph $G_p$ with vertex set $\mathbb{F}_p$, where two vertices are adjacent whenever their difference resides in $Q_p$. For example, the following illustration from Wikipedia depicts $G_{13}$:

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 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.

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:

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.

MATH 8610: Mathematics of Data Science

This spring, I’m teaching a graduate-level special topics course called “Mathematics of Data Science” at the Ohio State University. This will be a research-oriented class, and in lecture, I plan to cover some of the important ideas from convex optimization, probability, dimensionality reduction, clustering, and sparsity.

The current draft consists of a chapter on convex optimization. I will update the above link periodically. Feel free to comment below.

UPDATE #1: Lightly edited Chapter 1 and added a chapter on probability.

UPDATE #2: Lightly edited Chapter 2 and added a section on PCA.

UPDATE #3: Added a section on random projection.

UPDATE #4: Lightly edited Chapter 3. The semester is over, so I don’t plan to update these notes again until I teach a complementary special topics course next year.

UPDATE #5: As mentioned above, I’m teaching a complementary installment of this class this semester. I fixed several typos throughout, and I added a new section on embeddings from pairwise data.

UPDATE #6: Added a section on the clique problem.

UPDATE #7: Added a section on the Lovasz number.

UPDATE #8: Added a section on planted clique.

UPDATE #9: Added sections on maximum cut and minimum normalized cut.

UPDATE #10: Added a section on k-means clustering.

UPDATE #11: Started a chapter on compressed sensing.

UPDATE #12: Started a section on uniform guarantees.

UPDATE #13: Started a chapter on matrix analysis.

UPDATE #14: Started a section on matrix representations.

UPDATE #15: Started a section on spectral theory.

UPDATE #16: Added to the section on spectral theory.

UPDATE #17: Added more to the section on spectral theory.

UPDATE #18: Added even more to the section on spectral theory.

UPDATE #19: Finished the section on spectral theory and added a section on tensors.

UPDATE #20: Finished the section on tensors.

UPDATE #21: Added a section on random graphs.

A few paper announcements

This last semester, I was a long-term visitor at the Simons Institute for the Theory of Computing. My time there was rather productive, resulting in a few (exciting!) arXiv preprints, which I discuss below.

1. SqueezeFit: Label-aware dimensionality reduction by semidefinite programming.

Suppose you have a bunch of points in high-dimensional Euclidean space, some labeled “cat” and others labeled “dog,” say. Can you find a low-rank projection such that after projection, cats and dogs remain separated? If you can implement such a projection as a sensor, then that sensor collects enough information to classify cats versus dogs. This is the main idea behind compressive classification.

A neat application of the polynomial method

Two years ago, Boris Alexeev emailed me a problem:

Let $n \geq 2$.  Suppose you have $n^2$ distinct numbers in some field.  Is it necessarily possible to arrange the numbers into an $n\times n$ matrix of full rank?

Boris’s problem was originally inspired by a linear algebra exam problem at Princeton: Is it possible arrange four distinct prime numbers in a rank-deficient $2\times 2$ matrix? (The answer depends on whether you consider $-2$ to be prime.) Recently, Boris reminded me of his email, and I finally bothered to solve it. His hint: Apply the combinatorial nullstellensatz. The solve was rather satisfying, and if you’re reading this, I highly recommend that you stop reading here and enjoy the solve yourself.

Polymath16, eleventh thread: Chromatic numbers of planar sets

This is the eleventh “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.

Here’s a brief summary of the progress made in the previous thread:

– Let w(k) denote the supremum of w such that $[0,w]\times\mathbb{R}$ is k-colorable. Then of course $w(1)=-\infty$ and $w(k)=\infty$ for every $k\geq 7$. Furthermore,

$\displaystyle{w(2)=0, \quad w(3)=\frac{\sqrt{3}}{2}, \quad w(4)\geq\sqrt{\frac{32}{35}}, \quad w(5)\geq\frac{13}{8}, \quad w(6)\geq \sqrt{3}+\frac{\sqrt{15}}{2}.}$

Colorings that produce these lower bounds are depicted here. The upper bound for k=3 is given here.

– The largest known k-colorable disks for k=2,3,4,5 are depicted here.

Presumably, we can obtain descent upper bounds on w(4) by restricting (a finite subset of) the ring $\mathbb{Z}[\omega_1,\omega_3,\omega_4]$ to an infinite strip.