3b1b podcast #3

Grant Sanderson (of 3Blue1Brown fame) recently launched the 3b1b podcast as part of the SoME1 math exposition challenge. This page annotates the third episode of the podcast:

In this episode, Grant Sanderson (GS) interviews Steven Strogatz (SS) about research, pedagogy, and exposition, and what follows is some commentary by John Jasper (JJ), Emily King (EK), Clayton Shonkwiler (CS), and me (DM). Feel free to discuss further in the comments.

3b1b podcast #1

Grant Sanderson (of 3Blue1Brown fame) recently launched the 3b1b podcast as part of the SoME1 math exposition challenge. To celebrate, some friends and I decided to launch an experiment on this blog by annotating the first episode of the podcast:

In this episode, Grant Sanderson (GS) interviews Alex Kantorovich (AK) about all things academia, and what follows is some commentary by John Jasper (JJ), Hans Parshall (HP), and me (DM). Feel free to discuss further in the comments.

A graph coloring problem from quantum physics (with prizes!)

What follows is a nice problem that was recently posed by Mario Krenn. Progress on this problem may lead to new insights in quantum physics (see this, this, this, and this for details). In addition, Mario has announced two cash prizes to encourage work in this direction. (!)

Consider a weighted and edge-colored bipartite graph consisting of

• disjoint vertex sets and ,
• an edge set ,
• an edge coloring , and
• a complex vertex weighting .

MATH 2568: Linear Algebra

This spring, I’m teaching a first-semester course on Linear Algebra at the Ohio State University.

Click here for a draft of my lecture notes.

I will update the above link periodically. Feel free to comment below.

Update #1: Added two sections to Chapter 1.

Update #2: Updated Chapter 1 and started Chapter 2.

Update #3: Added a section to Chapter 2.

Update #4: Added another section to Chapter 2.

Update #5: Added another section to Chapter 2.

Update #6: Added Chapter 3 and started Chapter 4.

Update #7: Updated Section 4.1.

Update #8: Added Section 4.2.

Update #9: Started Section 4.3.

Update #10: Added Section 4.4.

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:

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.

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.

Click here for a draft of my lecture notes.

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 neat application of the polynomial method

Two years ago, Boris Alexeev emailed me a problem:

Let .  Suppose you have distinct numbers in some field.  Is it necessarily possible to arrange the numbers into an  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 matrix? (The answer depends on whether you consider 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.

Notes on Zauner’s conjecture

Last week, I visited Joey Iverson at the University of Maryland, and we spent a lot of time working through different approaches to Zauner’s conjecture. In general, my relationship with this problem is very similar to Steve Flammia‘s description, as paraphrased by smerkel on Physics Stack Exchange:

[Flammia described] the SIC-POVM problem as a “heartbreaker” because every approach you take seems super promising but then inevitably fizzles out without really giving you a great insight as to why.

Case in point, Joey and I identified a promising approach involving ideas from our association schemes paper. We were fairly optimistic, and Joey even bet me $5 that our approach would work. Needless to say, I now have this keepsake from Joey:

While our failure didn’t offer any great insights (as Flammia predicted), the experience forced me to review the literature on Zauner’s conjecture a lot more carefully. A few things caught my eye, and I’ll discuss them here. Throughout, SIC denotes “symmetric informationally complete line set” and WH denotes “the Weyl-Heisenberg group.”

Introduction to the polynomial method (and other similar things)

The polynomial method has made some waves recently (see this and that, for instance), and last week, Boris Alexeev gave a very nice talk on various applications of this method. This post is loosely based on his talk. All errors are my own.

It’s hard to pin down what exactly the polynomial method is. It’s a technique in algebraic extremal combinatorics, where the goal is to provide bounds on the sizes of objects with certain properties. The main idea is to identify the desired cardinality with some complexity measure of an algebraic object (e.g., the dimension of a vector space, the degree of a polynomial, or the rank of a tensor), and then use algebraic techniques to estimate that complexity measure. If at some point you use polynomials, then you might say you applied the polynomial method.

What follows is a series of instances of this meta-method.