https://dustingmixon.wordpress.com/feed

After nearly five years, it’s time to roll over the discussion. Aubrey’s most recent comment in the previous thread seems interesting. I’m reproducing it here for convenience:

In the course of discussing Asger’s graph (see above) and the one I found shortly afterwards, a new conjecture has arisen:

For all d >= 2 and 3 <= n <= d+2, there exists a (d+n-1)-chromatic unit-distance graph in R^d that does not contain any n-simplex.

Since there cannot be a simplex in R^d of size greater than d+1, this covers all meaningful cases.

The conjecture is interesting because there are only finitely many (d,n} for which it is not already known to be true. That’s because several years ago, Andrei Raigorodskii proved an exponential lower bound that is analogous to his famous one, but in which the vertices lie on a sphere. The key utility of his result from the perspective of this conjecture is that the sphere can have any radius > 1/2, so in particular it can have a radius < 1/Sqrt[3], on which any UDG must clearly be triangle-free.

But starting from d = 2 (i.e. the plane), it is worth enumerating what is known. In the plane, the conjecture is proven for both relevant values of n (namely 3 and 4), because we have 5-chromatic UDGs and we also have 4-chromatic triangle-free UDGs. In R^3, the recent papers by Asger and myself deal with the cases n=3 and n=4, leaving only n=5, i.e. the non-discovery of a 7-chromatic UDG of any kind.

In higher dimensions, however, there seems to have been no exploration of UDGs restricted by simplex size. All we have is the unrestricted cases (those with n = d+2). The situation there seems to be that, other than the d=3 case just mentioned, only three dimensions (d = 5, 6 and 8) are lacking, because the highest chromatic numbers known in those dimensions are 9, 12 and 16 as against the desired 11, 13 and 17. Above d=8 we already have graphs with chromatic number at least 2d+1 through d = 18, which is well into the territory where Andrei’s famous exponential lower bound does the job.

As of now, preliminary discussions have involved only Asger, myself, Andrei, his former PhD student Oleg Rubanov (who found a large graph satisfying {d,n} = {3,3} during his doctoral studies, and Vsevolod Voronov, who (among other VERY cool results) found two 5-chromatic UDGs on S^2, which have radii less than 1 and thus deliver 7-chromatic UDGs in R^4 by spindling of bi-pyramids. Dan Ismailescu and Geoffrey Exoo, who found a lot of the best known cases in small dimensions, are also joining in. We have decided to bring the discussion here so as to involve others. Let’s do this!

This summer, 3Blue1Brown launched the third installment of the Summer of Math Exposition contest. Every year, I’ve been impressed and inspired by the quality of some of the videos in this contest. Over the last couple of months, I worked with Boris Alexeev and John Jasper to throw our hat in the ring:

I was surprised by how much I learned from this experience. In what follows, I reflect on the process of making this video.

Part 1. The topic

We started brainstorming two months ago. We had a few cool ideas involving linear algebra and combinatorics, but we felt that the most interesting-to-normies video would discuss the mathematics of gerrymandering. Notably, since gerrymandering revolves around planar geometry, it’s well suited for the screen. We identified a few directions we could go:

1. Sometimes, fair districts are necessarily ugly.
2. You can probably gerrymander for the minority party using convex districts.
3. You can always gerrymander for the majority party using convex districts.
4. Typical maps can be sampled using MCMC.

These are listed in order of familiarity to us. First, 1 is based on our impossibility theorem for gerrymandering. Next, 2 is based on our paper that uses Brownian motion to determine the probability (under some random model of the voter distribution) of being able to gerrymander for the minority party with a straight line. The analysis in this paper is pretty slick, but Brownian motion is not terribly accessible, so it wasn’t a good fit. For 3, we would follow the proof ideas in this paper by Bespamyatnikh, Kirkpatrick, and Snoeyink. We decided that 4 was a little too mainstream to be novel.

At this point, it was a toss up between 1 and 3. Since we were already familiar with 1, I did a deep dive on 3. I decided the proof of the main result would be less technical if I modified the statement:

Theorem. Given sufficiently nice probability measures and over the plane and a natural number , there exists a partition of the plane into convex sets such that for each .

While the original paper focused on distributions of points, I would take and to have continuous distributions. This would allow me to mimic the proof idea in Figure 5 of the paper, but avoid annoying combinatorial arguments by instead passing through the intermediate value theorem. After writing out the argument, it was still too technical compared to the 3-paragraph proof of our impossibility theorem, so we decided to go with 1.

Part 2. The result

In the paper, we provide definitions of

(1) one person, one vote with parameter ,
(2) Polsby-Popper compactness with parameter , and
(3) bounded efficiency gap with parameters and

before stating the main result:

Theorem. Given , there exists a distribution of voters such that every partition into districts violates at least one of (1), (2), and (3).

This presentation of the result was particularly relevant since the efficiency gap metric was the subject of a SCOTUS case at the time. However, the efficiency gap is not terribly intuitive. Also, in our proof of the result, the second paragraph concludes that (1) and (2) together force every district to be won by the majority party, while the third paragraph just explains how this violates (3). This means we can simultaneously clarify the result and simplify its proof by replacing (3) with the more intuitive requirement

(3′) A minority party with at least of the vote gets at least one seat.

Next, the proof doesn’t use the full power of (1), but rather, that each district contains at least a fraction of the voters. Also, the argument focuses on an arbitrary district, which leads to yet another improvement in the theorem statement:

Theorem. Given , there exists a distribution of voters in which the minority party has at least of the vote, but any district with at least of the voters that has a Polsby-Popper score of at least is necessarily won by the majority party.

While this version of the result is much clearer than the original, it’s still not perfect. The statement would have more shock value if it took the form “fair districts must be ugly.” Also, the second paragraph of the proof uses multiple rounds of “it suffices to show”, which indicates that we’ll get a simpler argument after contraposition. This suggests yet another formulation:

Theorem. Given , there exists a distribution of voters in which the minority party has at least of the vote, but every majority-minority district with at least of the voters has a Polsby-Popper score less than .

Interestingly, the notion of “majority-minority district” can be applied not only to the political minority, but also to any racial minority. This application was not evident in the original formulation of the impossibility theorem since the efficiency gap is fundamentally a partisan metric. For exposition reasons, the bulk of the video takes , , and without affecting the idea of the proof.

Part 3. The proof

The above changes to the main result already give vast simplifications to the proof. We made two additional modifications to optimize for video.

First, our original proof doesn’t explicitly use the intuition captured in Figure 1 of the paper. In the figure, we take a grid of squares and distribute 5 majority voters and 4 minority voters in each square. For such an arrangement, the boundary of a majority-minority district needs to carefully split “cut squares” so as to aggregate minority population and make up for losses in the “inner squares”. This is implicitly used in the first display of the proof, but for the video, we made this explicit: At least a fifth of the squares that intersect the district need to be cut squares. This isolates how being majority-minority impacts the geometry of the district. Also, since the total number of squares corresponds to area and the cut squares correspond to perimeter, this naturally motivates the study of isoperimetry.

Next, we wanted to bound the number of cut squares in terms of the perimeter. Our original proof used an epsilon-net-type argument, but we wanted constants that weren’t so ugly. We investigated tight estimates from integral geometry, but we didn’t have any luck finding a slick proof of these. Instead, we found a bound with a clean constant along with a satisfying proof that uses the probabilistic method. We were heavily inspired by Buffon’s noodle, and I’m kinda surprised we pulled it off.

I didn’t expect that optimizing for exposition would have such a profound impact on my depth of understanding of my own research, but here we are. I suppose I should have expected this considering how much I learn when I teach.

Part 4. The content

Now that we fine tuned our result and its proof, it was time to make content.

For the video, I was pleasantly surprised by the capability of all the software that came with my MacBook Air. After storyboarding on Google Slides, I made animations in Keynote. Then I wrote a script and recorded using GarageBand. I’m not the best voice actor, so this took multiple takes and lots of editing. Then I used the Screenshot app to record my Keynote animations in presentation mode, and I edited this video to line up with the voiceover in iMovie. The lion’s share of this work was easily the animations, in part because I was simultaneously learning what all was possible. Before starting, we toyed with the idea of using Manim, but we didn’t know what the learning curve would be, so we went with a more familiar option. I assume Manim would give me more control of various elements a la LaTeX versus Microsoft Word.

While I cooked up the video, John put the web app together. He would send me iterations, and we would discuss possibilities. He seemed to enjoy solving the underlying programming puzzles while injecting a dose of artistry.

We shared a draft of our content to a few people for feedback and let it sit for a week before making the final edits. Some of the pacing was a little off in the initial version, but I was too close to notice, so it was nice to get outside opinions.

Part 5. The algorithm

The content was finalized by August 1, but we still had work to do. Not only do we want our video to be competitive in the SoME3 contest, we want it to perform well in the broader YouTube ecosystem. After a lot of research, it became clear that people won’t watch our video unless they click on it. Meanwhile, the only data that informs this decision is our title and thumbnail. So these need to be optimized.

First, the title should present a curiosity gap: give just enough information to entice the would-be viewer. Also, the title shouldn’t be much longer than 50 characters, since otherwise YouTube cuts it off and displays an ellipsis at the end. This led us to

Why You Want Voting Districts To Be Ugly

since this contradicts conventional wisdom. We thought the title would catch the eye better with numbers, so we decided to make a reference to the Polsby-Popper score:

Why You Want Voting Districts To Be 4% Pretty

Indeed, the main character of our story (IL-4) has a Polsby-Popper score of 0.04. Then we got a tip that this could be interpreted as “at least 4% pretty”, so we went with

Why You Want Voting Districts To Be Only 4% Pretty

notably, avoiding a split infinitive. We also added the hashtag #SoME3 to attract the 3Blue1Brown viewership.

The first draft of our thumbnail was eye-catching:

but we didn’t like all the text, and the background was too dark to be passable as a map when zoomed out. So then we went with

We liked that the green text contrasts with the light background, but when the picture is small, it’s hardly legible. So we flipped through a bunch of successful thumbnails and came up with this solution:

At this point, we’re pretty happy with the title and thumbnail, but they still might change if we learn more about what works. YouTube’s algorithm is pretty mysterious, and that’s a good thing (it keeps undesirable gamesmanship at bay). For example, I don’t know why, but our video is not showing up on the hashtag landing page.

Any pointers are welcome!

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.

2:40 – DM: Seems like a fun problem. How hard could it be?

7:21 – CS: The “Steven has real talent” note is a nice story, but it also strikes me as extremely weird. Like, why not tell SS directly that he has real talent, rather than writing it in a note to the headmaster that he eventually gets a carbon copy of?

8:00 – EK: My intro discrete math prof gave us the Twin Prime Conjecture as a “bonus problem” but didn’t tell us that it was a famous open problem.

8:35 – CS: I wish I was better at generating problems that are extremely challenging but solvable for students at various levels.

8:35 – DM: We should definitely pose appropriate math puzzles to interested young folks. There’s great source material from Martin Gardner, Project Euler, and the IMO, for example. For younger kids, this might be a useful resource.

9:18 – EK: That is a fun problem. I’m going to be distracted thinking about it rather than doing the work I need to do.

10:37 – EK: THIS! I think far too many students these days look up proofs online without struggling sufficiently.

10:37 – JJ: Is it possible that the benefit of being able to readily look things up will outweigh the benefits earned by the struggle? I don’t think so, but I want to consider the possibility. 

11:35 – DM: Even today, it seems that my best math ideas come when I’m procrastinating on an administrative task.

14:32 – CS: I can identify with this!

16:50 – JJ: I like the idea that the first part of any exposition (lecturing or writing) should be to get the students interested in the question. This is a nice way to structure the beginning of a lecture. Even more, I like the idea that motivation can simply come from asking an open-ended question like “what’s the distance between the sine and cosine functions?” In particular, the motivation need not come from a physics application or even an application to another area of math.

17:03 – CS: I love this formulation. 

19:40 – EK: I enjoy questions where the first step is discussing what the actual meaning of the question is.

19:40 – DM: Reminds me of how Vsauce used to title its YouTube videos, e.g., How Much Does a Shadow Weight? I’ll have to think about how I can use this trick more regularly when I teach.

21:40 – DM: SS makes a great point here. I hate sitting through a talk in which I don’t care about the problem but I’m being dragged through the solution.

21:40 – CS: This hits a little close to home, in that a collaborator and I just finished a paper in which we answered a question that nobody had asked. But it also makes me reflect that my paper-reading is unbalanced: if I’m reading a paper, it’s almost always because it contains a result I want to use, and almost never just because I want to learn to love a new question. 

25:54 – DM: His description of this proof gives me goosebumps. Pretty inspiring.

27:50 – JJ: This is a great take on a super important question: what motivates students? SS seems to agree with my take (from podcast #1 at 15:36) that approval from experts and competition are powerful sources of validation and motivation. SS adds that history, applications, and beauty are also sources of motivation for some students.

28:25 – JJ: The distinction between “beautiful” and “satisfying” strikes me as really useful language. I think I have used synonyms for beautiful when it would be more relatable (less exclusionary) to say satisfying. Indeed, some proofs are very satisfying in they way they come together, perhaps we can start a subreddit à la r/oddlysatisfying.

28:25 – CS: I like this as an alternative to the “math is beautiful” trope. In school I didn’t really love math, but I did like how it was a realm in which things usually fit together in a satisfying way. And now I’m not really coming up with beautiful theorems or even beautiful proofs, but the realization that this tool from over here is perfectly suited to solving that problem over there is really delightful.

28:55 – EK: “Beauty is exclusionary” is an interesting take.

30:01 – DM: It’s a good thought to be mindful of students who are motivated to do math as a way to change their socioeconomic status. Reminds me of how I would memorize vocabulary words to study for the SAT, since I was singularly motivated by being accepted into college. It also highlights the privilege wrapped up with insisting on being inspired in order to learn math.

32:47 – CS: What is the appropriate place for rigor in math? I mean, it seems clear that research papers should be pretty rigorous (which doesn’t mean they shouldn’t also communicate intuition), but probably most math talks, even seminar talks, would benefit from being less rigorous and more intuitive. And if most papers need to be fairly rigorous, that presumably means we need to train graduate students in being rigorous somewhere along the way. But what’s the appropriate venue for that? And how far down the scale does this really apply? And to what extent does mathematical rigor in a form different than you would find in a research paper come into this (I guess I have in mind engineering students, for whom rigor might mean something slightly different while still being important)?

33:58 – DM: Another way to motivate: You must complete this task in a short amount of time, so you need to learn and memorize enough to succeed at that task. Drilling has its benefits.

35:25 – EK: I recently saw a Tweet revealing a “life hack” that you could “flip” percentages, e.g., 4% of 75 is 75% of 4, with the latter being the easier calculation. A lot of people were shocked at the outcome, but maybe that’s because the “life hack” nature of commutativity (e.g., easier to add two 9’s than nine 2’s) was never explained to them.

35:35 – JJ: I really like teaching intuition before formalism. Two technical problems with this that I’m not 100% sure how to overcome. First, students will have trouble distinguishing between formal arguments and intuitive arguments. Calculus students are ONLY taught intuition, but then they get to real analysis we ask them to do formal proofs on the same material. Second, it’s difficult, but not impossible, to test their intuition.  

36:06 – DM: The main reason I don’t post lectures on YouTube is that I fear exhibiting a level of perfectionism by blowing too much time on video editing. On the other hand, we consistently post talks from the CodEx seminar series on YouTube with very little editing. This is a benefit of separating the content creator from the person who posts on YouTube.

39:20 – CS: I agree that it in principle it would be cool to connect, say, animators and mathematicians, but it’s a major logistical challenge which no institution is really incentivized to solve. But if you’re a mathematician, you don’t actually need an animator (or designer, or whatever): you can make your own animations!

40:40 – DM: This reminds me of the teacher-student collaboration model that GS proposed when launching the SoME1 competition. A similar collaboration was already successful in this video. It’s an interesting thought that this sort of interaction might scale.

43:12 – DM: It’s very believable to me that Elias Stein’s Complex Analysis course played a pivotal role in SS’s education. I had the pleasure of sitting in on this class as a grad student, and I was floored by Stein’s teaching style. The experience had such an influence on me that it made an appearance in my teaching statement when I was on the job market.

44:20 – DM: Reminds me of my own experience in undergrad. I was naturally drawn to math, but my family’s experience in the Air Force biased my career trajectory. I ended up doing math as an officer in the Air Force for 13 years before joining the faculty at Ohio State.

47:05 – CS: This whole chapter is a really good advertisement for one of the major potential benefits of being an undergraduate at an R1 university. I went to a very small college where the faculty (the math faculty, at least) was just not very engaged in research, so working on major open problems with world experts in your senior thesis was just not a thing that was going to happen. (For drawbacks in going to an R1 as an undergrad as opposed to a place which values teaching more highly, see earlier in the video.)

55:05 – DM: This ribbon story is great! I love it when a physical model helps to clarify thinking on a math problem. Another noteworthy example is the space-time globe for understanding special relativity.

55:58 – EK: That’s a cool application and test of topological invariants.

58:54 – DM: Learning while teaching is a great (but sometimes stressful!) way to learn. When developing my topics course on data science, I selected various results from papers that I already had a working knowledge of, but I needed a much deeper understanding before I’d feel comfortable enough to teach those things. It ended up being a lot of work, but definitely worth it.

59:10 – CS: I’m going to have to steal this line.

59:21 – JJ: There’s some great stuff about learning here. SS talks about how he could learn the subject (group theory) now, but he’d have to teach it. This is in contrast to his experience in school where he failed to learn it. He points out two differences: There’d be a “gun to his head,” and he could do what he couldn’t while in school, which is look stuff up. What seem obvious here is that we should be listening to the experts on what is the best way to learn math. Student presentations can mimic this for my students, but I don’t know how we model the “gun to the head” part, which I think is also super important. The pressure of presenting is good, but many student presentations take the form of reading a prepared speech full of statements that they don’t fully understand. Should they also be required to field questions coherently?

1:01:06 – DM: I had no idea about the Latin derivative of “radical.” That’s a nice connection.

1:01:51 – EK: Huh. I didn’t realize that convergence issues of Fourier series and not calculus motivated real analysis.

1:10:00 – CS: My sense is that most mathematicians think they know more about the history of math than they actually do. History is a difficult and complicated undertaking which is a long way from vaguely remembering a couple of paragraphs (which were probably apocryphal to begin with) about Hamilton inventing the quaternions or whatever. (Okay, GS and SS basically get into this a couple of minutes later.)

1:12:14 – CS: Somewhat distinct from history of mathematics, do people study mathematical folklore in the sense being discussed here? I guess Alberto Martínez’s book addresses some of these, but (not having read it), the book description seems to pitch it more as mythbusting than as studying why certain stories become popular and what purpose those stories might serve even if they’re not factually accurate.

1:15:59 – DM: Never let the truth get in the way of a good story! We embellish the truth even when describing events from the previous night. Stories are fun. In the context of math, stories get us to care about the material. Does it really matter whether a soldier actually disturbed Aristotle’s circles?

1:24:17 – DM: It seems that GS agrees with me.

1:25:00 – CS: This somehow reminds me of how my advisor Herman Gluck always described visualizing higher dimensions: “Visualizing higher dimensions is an exercise in creative lying”. Of course, the trick to it is knowing what it’s okay to lie about.

1:27:59 – DM: I really like this joke idea that Fourier wanted to solve the heat equation so that he could figure out why he needs to wear a heavy coat all the time. And I’m not concerned that this is historically inaccurate (in all likelihood).

1:29:09 – DM: For some reason, I have to fight myself to provide examples before discussing the more general underlying theory. I know it’s the right way to explain a thing, but for some reason, I want to hurry up and share the cool thing that’s calling the shots.

1:32:30 – CS: This is something that so many mathematicians say and think, and I find myself agreeing with it as well, which makes me almost want to push back on it. Like, if everybody thinks this is bad, but it doesn’t change, why is that? Is it actually good? Or is it just that everybody says they want a clear narrative and lots of motivation and examples, but then when they have to referee a 100 page paper they say “There’s only 20 pages of actual math in here, cut it way back!”?

1:33:00 – DM: I first learned of this one-sentence proof in this (otherwise very interesting) MathOverflow thread.

1:35:00 – DM: SS has a way with words.

1:38:14 – JJ: SS is talking about the zeta function, in particular, the equality of the infinite sum and infinite product forms. He explains what he calls a “very understandable proof.” This is really a byproduct of the notation for infinite sums and infinite products. We use this notation because it gives us useful intuition that we already have from finite sums and finite products. Just working with infinite series in this way is “considered not kosher” because many such manipulations would lead to false statements. I do think that this is the right intuition here, and, going back to an earlier point by SS, this is the right way to start the discussion about this fact. However, this is not the right way to PROVE this fact. This section is pointing to an important fact that a lot of math education is focused on producing the rigorous proofs, and much more should be focused on figuring out what is true, at least intuitively. Indeed, research time is mostly spent figuring out what is true.

1:38:48 – CS: I wonder how many results in math really have nice intuition and a nice story behind how the person figured out what was true. A lot of times for me, the answer is either “I computed a bunch of examples on my computer and this was always the result” or “I just knew it had to be true for reasons I can’t even entirely articulate”, neither of which is actually that interesting or informative to read. But maybe this is an argument there should be a lot fewer math papers in the world?

1:39:22 – DM: Here’s a link to the twitter thread GS mentions.

1:39:58 – EK: “is” vs. “ought” — I like that distinction as applied to mathematics.

1:48:42 – DM: I like this idea of people giving talks about work that they didn’t do. SS mentions that some seminars that follow this model, but I haven’t heard of it before (outside of presentations in my topics course).

1:49:46 – EK: Shout out to my CSU colleagues (Henry Adams, Justin O’Connor, Kyle Salois, Brittany Story, Ciera Street) for organizing that special session!

1:50:35 – CS: GS is basically describing the Current Events Bulletin at the Joint Meetings, which I think basically everybody enjoys, so it seems like there should be more venues for this kind of thing (other than writing textbooks, that is).

1:53:15 – DM: Here’s a link to the previous collaboration between GS and SS. In hindsight, this early 3Blue1Brown video follows GS’s suggested SoME1 model of having an elder collaborator provide the material and having a younger collaborator develop the animation.

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.

1:09 – HP: AK’s mother’s story is one that I would like to hear.

2:53 – HP: AK seems to share a belief among mathematicians: math is the best arena to train problem-solving skills that are widely applicable beyond math.

2:53 – DM: I’m stealing this joke.

4:21 – DM: The comparison to reading is funny. It’s wild to think of a society in which everyone supports the study of technical things like math. There’s certainly a push for STEM careers in the US today, but it hasn’t yet kept folks from bragging about how they were never good at math.

5:01 – HP: I am essentially ignorant of how mathematics is taught outside the US; I hope that GS digs deeper into these questions in a future podcast.

8:36 – HP: I strongly agree with AK here: “you need both”. There is a synergy effect: mechanical skills and conceptual understanding reinforce one another. “Intuition” is a hard thing to define (try it!), but it seems impossible to build mathematical intuition without rolling up sleeves and calculating.

8:54 – DM: I agree with the need for both understanding and drilling. Drilling is less attractive for obvious reasons, but it allows one to solve problems quickly. Does drilling have a place in higher-level math? For example, I can produce a proof of the spectral theorem given enough time, but I can also quickly recite the theorem from memory, and this is useful in research. Do we spend enough time drilling key theorem statements in class?

9:37 – JJ: My worry is that our teachers don’t have enough training to teach problem solving. Problem solving is much harder to teach than algorithmic stuff that avoids thinking.

11:08 – DM: The application of drilling here is familiar to me. But I’m also quick to code things up in a computer to help formulate conjectures. After discovering a conjecture, I tend verify small cases by hand to observe symbol manipulations that can prove the desired theorem.

15:32 – HP: AK’s point is really strong here. Mathematical “adults” can be frightened off by a vast literature surrounding an open problem, but there is still plenty of room for mathematical “kids” to play around (and teach the grown-ups).

15:36 – JJ: AK describes “racing” colleagues during research. Both GS and AK describe the excitement that kids sometimes have during math games on car rides, especially when they see excitement from adults. I think these are related. In particular, as a kid/student the positive feedback that we receive is a strong motivator. Indeed, it is an indication from people with more expertise (adults, profs, etc.) that we are doing something worth doing. During research we sometimes get the same validation from being the first to provide the proof of the claim we are all thinking about. This points to expert approval being an important motivator for learning. How can we best use this form of motivation for students? This “racing” makes research sound kind of intense (which it often is!). This may be a turnoff for some potential mathematicians.

20:01 – HP: I suspect that most mathematicians are too quick to discount their ability to engage in meaningful outreach. We should all care about making sure that people understand what we’re doing!

21:27 – HP: AK is being modest here; being editor-in-chief of a journal is both an honor and a responsibility. His description of Experimental Mathematics is appropriately sexy.

27:51 – HP: Now I want GS to interview a writer at Quanta about their background and process!

31:12 – JJ: Tweeting about your papers is a great exercise, if only to force one to write out something about the content of your paper in language designed for broader audience. AK suggests that people may have an easier time getting an idea of what is in his papers from reading a tweet. This sounds like the role that an abstract is supposed to play. Perhaps abstracts are only playing this role for experts in the field. Maybe what we need is a non-expert abstract in addition to the one written for experts. This could also be a remedy to a problem AK mentioned earlier, namely, that colloquium talks should be at the level of a 1st year graduate student. For colloquia, we could have speakers submit an abstract that is readable by a 1st year graduate student. Forcing colleagues to do this seems difficult, but forcing graduate students to do this for their job talks is very doable!

31:12 – DM: Oof. I think papers should be written in a way that maximizes understanding. If 140 characters elucidates a proof, then some version of those characters should appear in the paper. This is the opposite of a waste of space. We should remove the stigma of helpful explanation in papers much like how Experimental Mathematics removes the stigma of formulating conjectures and providing computational evidence for those conjectures. I have never received a review of one of my papers that asked to omit a helpful explanation.

33:11 – DM: Yeah, I appreciate thinking of the first-year graduate student as the intended audience of a colloquium. I wish more colloquium speakers applied this model of the audience.

33:56 – HP: AK makes an important point here: definitions are hard to parse without intuition, and intuition takes time to build. Different branches of math seem to rely on different intuition; I would also be upset to attend a talk that opened with an affine scheme over a totally real whatever.

36:41 – HP: Solid take-home advice from AK: to give better talks, give more talks and pay attention to the audience.

38:25 – DM: I’ve found that the chat and polling features in Zoom remove barriers to classroom discussion. On the other hand, Zoom can make it difficult for me to throttle the rate at which I cover various points in lecture, since Zoom can obscure nonverbal cues from students. I’m looking forward to returning to in-person lectures in the fall. I wonder if I should use an integrated approach. Live streams? Clickers? I’m certainly less afraid of technology now that the pandemic forced me to work with it.

42:39 – HP: AK mentions trying to collaborate with the math ed department. I wonder how well-known it is that math and math ed are two very distinct fields, and often (but not always) they are separate departments!

43:30 – DM: Oof, I don’t think mathematicians are the best problem solvers in all cases. By definition, they are the best solvers of math problems, but there are many types of problems in the world. George Pólya’s “How to Solve It” doesn’t explain how to solve the various social problems in the US. Also, I don’t think the NSF should mandate 10% time on non-math problems, but they can choose to fund more cross-disciplinary proposals, thereby incentivizing such research. Ohio State provides several opportunities for cross-pollination, e.g., the STEAM Factory and the Translational Data Analytics Institute.

46:17 – HP: Yes, please: more university-wide colloquia!

48:33 – DM: Heh. Lots of data science is about separating signal from noise, and there’s a lot of beautiful math that makes this work, but in many cases, industry can just purchase more signal. I hear this happens in big tech all the time. Pretty rough.

56:44 – DM: This reminds me of how I can use duality theory in convex analysis to systematically search for proofs of a certain form. I wonder what the learning curve is like for Lean.

58:56 – HP: GS asks a really important question here, wondering about the danger of asking an oracle. 

1:01:05 – DM: Is Lean sufficiently user friendly to bring into the classroom?

1:02:21 – JJ: I can see huge value in using Lean to separate the instructor from the evaluator in proof-based courses. As AK points out, students (including himself) often feel that they are losing points because the evaluator is “nitpicking.” I’m concerned that the students might feel that subjecting their proofs to a computer checker is the height of nitpicking. Moreover, it is not even the standard for proofs in mathematics. Meanwhile, it’s super easy to see how programming in MATLAB is not a contrived exercise since folks use it in the wild. This may become moot once Lean becomes more commonplace in the math community.

1:02:21 – HP: I really appreciate GS justifying the position that learning programming helps one learn to think mathematically. My own opinion: it is more important to learn programming than it is to learn any one particular piece of software. I would caution students that LEAN is under rapid development, and from their FAQ: “Documentation is not the main priority right now.”

1:02:21 – DM: When grading proofs, it can be difficult to convey to the student why points are being taken away. For example, in early proofs courses, “your logic is not clear” can be interpreted as “I just don’t like your writing style.” I like the idea of pitting the student against the compiler so that the teacher can be a coach more than an adversary. I’ve seen this sort of social move used in other aspects of the classroom, for example, separating the evaluator from the instructor in coordinated courses or qualifying exams.

1:04:52 – HP: Thanks to GS for extracting a prediction! I would buy AK’s prediction that at least one math journal requires a “formalized” proof in 20 years time (are there any now?), and I would be flabbergasted if this was the norm. The quest for formalization of mathematics is old and controversial; see this.

1:09:17 – HP: I don’t know the reference to “Tarski and somebody”, but it seems plausible that AK is referring to Russell and Whitehead’s Principia Mathematica, which proves that 1 + 1 = 2 on page 83 of Volume II. They were self-aware: it is immediately followed by the comment “The above proposition is occasionally useful.” This should give us some appreciation for how difficult formalizing mathematics can be.

1:10:04 – HP: I agree with AK: papers should tell stories! I need to remember this advice.

1:10:50 – DM: It seems that AK agrees that papers should include helpful explanations after all.

This is the seventeenth “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, we are finalizing a draft of a paper by D.H.J. Polymath. Like Aubrey’s original paper, this will be submitted for publication in Geombinatorics.

This post concludes the Polymath16 project. Of course, we anticipate that folks will continue to make progress on this problem on their own. If you’d like to update the Polymath16 community about your progress, feel free to comment on this post.

I asked Aubrey to offer a few words to reflect on our project:

The Polymath 16 project recently celebrated 1000 days of age. It had two main initial goals: to find 5-chromatic unit-distance graphs in the plane with fewer vertices than the 1581-vertex example that I had published in early 2018, and to identify proofs of that required less computer assistance than my construction needed (ideally none at all). Many ancillary goals were also mentioned at the outset.

By all standards, the project has been an immense success. The record for the smallest graph was progressively improved, including several times by Marijn Heule, and the present record is 509, achieved by Jaan Parts. Jaan also has the distinction of cracking the other main challenge: a few months ago he unveiled a proof of that he described only as “human-verifiable,” but that is too modest, because his method is certainly usable to create a proof from scratch without any computational assistance in no more than a week or two (for someone sufficiently diligent and non-error-prone!). Jaan has, in fact, been the most prolific of the contributors to the project over the years, having made numerous other contributions, some on his own and some in Polymath-esque rapid-fire collaboration with others.

Perhaps the most satisfying aspect of the project, to me, is its quite remarkable success in attracting amateur mathematicians like myself (of whom Jaan is one). At least half a dozen of us have been significant contributors over these three years, working side by side with numerous professionals including Terry Tao himself.

Given the diversity of Hadwiger-Nelson-type problems that we have investigated, it was always implausible that all our results would be gathered into a single publication. This was especially the case in view of the proportion (more than half) of our advances that were achieved by a single individual with little or no collaboration at the blog, and which were thus more properly published under that person’s name alone. However, one clear exception emerged: the set of questions concerning bounds on the sizes of circular disks and infinite strips of different chromatic number. It has turned out that at least five of us made major contributions to one or more such question, so this was the natural focus of what has just become the first (and, we must now anticipate, only) paper arising from Polymath 16 whose sole listed author is the canonical, fictional D.H.J. Polymath. Like several of the other reports, and like my original proof of , it will appear in the journal Geombinatorics, whose editor-in-chief Alexander Soifer was, via his timeless 2009 book, responsible for inspiring me to work on the Hadwiger-Nelson problem in the first place.

The energy that Polymath 16 has evoked will not dissipate easily. We plan to leave this blog open for further discussions and reports – which will surely emerge as time passes, since many fascinating Hadwiger-Nelson-type questions remain wide open in spite of our efforts. Let us hope that the merry band who have progressed this far will continue to grow and to make yet further inroads into this truly captivating family of questions.

Last summer, I launched an online seminar with Joey Iverson, John Jasper, and Emily King on the theory and applications of harmonic analysis, combinatorics, and algebra. We meet on Tuesdays at 1pm (Eastern time).

We’re kicking off the spring semester on January 26 with a talk from Steve Flammia on recent progress on Zauner’s conjecture.

Click here for the Zoom link and to sign up for the mailing list.

Click here for a list of past and upcoming talks.

Click here for the CodEx YouTube channel.

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 .

This graph provides a combinatorial abstraction of a quantum mechanical system. Specifically, denotes a set of photon sources, is the set of optical output paths, is the set of all possible photons, gives the mode number of photon , and the complex weights allow one to model quantum interference between the photon sources. Consider the following experiment: Place a detector at each , and let each randomly produce either correlated photons or no photons. We are interested in the event that all detectors simultaneously detect exactly one photon. The mode numbers of these photons can be viewed as a vertex coloring , and this coloring reveals some information about which sources produced which photons. Specifically, we say is -consistent if

• the neighborhoods form a partition of , and
• for every and every , it holds that .

In quantum optics, we cannot directly access the mode numbers of the photons, and in fact, we obtain a superposition of various possibilities. This superposition forms something called a Greenberger–Horne–Zeilinger (GHZ) state if satisfies an additional monochromatic property, defined below. Let denote the set of all -consistent , and define the weight of a coloring of to be

By convention, implies . We say is monochromatic if the weight of every coloring of takes the form

Here, denotes the image of the map . In words, is monochromatic if indicates whether gives every member of the same color in the palette . If is monochromatic, then the corresponding quantum mechanical system produces GHZ states, and the dimensionality of the state space is the size of the color palette .

In practice, one is interested in producing high-dimensional states with a given number particles, and the most practical of photon sources creates only two photons. For these reasons, we are particularly interested in the supremum of over all monochromatic such that and for every . Let denote this supremum. Notice that the constraint on implies that is monochromatic only if is even. For such , Mario poses the following conjecture:

Excitingly, there are two prizes associated with this conjecture. First, there’s a 3000-Euro prize for its resolution (i.e., for either a proof or a disproof). In addition, there’s a 1000-Euro best-paper award offered for the best results obtained in this vein (to be judged by Mario). See this page for more details.

To explain the source of Krenn’s Conjecture, we point out that “half” of the conjecture is known to be true; that is, the inequality holds, while the inequality is open for every with . We obtain this lower bound on by restricting our attention to for which

• for every and , and
• for every .

This restriction is convenient, since we can capture using the edge-colored multigraph with vertex set , edge set , assignment defined by , and edge coloring defined by for every . For such , the corresponding is monochromatic if and only if the following hold simultaneously:

• for every color , there exists a unique perfect matching of such that , and
• for every perfect matching of , it holds that is a singleton set.

This reduces our problem to finding multigraphs whose perfect matchings are all disjoint, since one may color edges in the th perfect matching with , and then color any remaining edges with . Let denote the supremum of for which there exists a multigraph on vertices with a total of perfect matchings, all of which are disjoint. Then the above discussion gives

Notice we can already conclude for every by taking to be a -factor. In the special case where , one may draw arbitrarily many edges between the two vertices to obtain , i.e., . It remains to consider with . In this case, the multigraph we seek can be taken to be a simple graph without loss of generality (i.e., multiple edges are not helpful here), and so in this language, Ilya Bogdanov proved that equals the right-hand side of Krenn’s Conjecture. The case corresponds to the -factorization of , while the remaining cases correspond to the -factorization of :

In order to determine whether this lower bound is sharp, one must consider more general choices of . In particular, do non-unit weights on allow for a larger color palette? Interestingly, Mario has an example of with , , , and for every . However, this graph is only monochromatic in the limit as , so this does not quite prove that is at least .

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.

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 .

One particularly interesting family of ETFs are of the form . In the quantum information theory community, these are known as symmetric, informationally complete positive operator–valued measures; the modern abbreviation for this mouthful is SIC. In his PhD thesis, Zauner predicted that SICs exist for every , but to date, they are only known to exist for finitely many . Almost all existing SICs are constructed by spinning a seed vector with a representation of the Weyl–Heisenberg group, and the entries of the seed vector are expressible in radicals. Frustratingly, the complexity of this description appears to grow like , which suggests that this is not the best representation for these seed vectors.

In 2018, Gene discovered an alternative that seems to be the “correct” representation. Specifically, the squares of the entries of appear to be obtained by applying a Galois automorphism to the Stark units of an abelian extension of with ramification at the primes dividing and at one infinite place. In the case when is prime, Gene gives a precise recipe to construct the entries of from their squares.

These equiangular tight frames exhibit field structure that is completely different from other known constructions. In general, given , the triple products with form an invariant over the left-action of and the right-action of . For all known ETF constructions other than SICs, either the ETF belongs to a continuum of inequivalent ETFs, or the triple products all belong to a cyclotomic field. This observation compelled Gene to formulate the following problem:

Kopp’s Whisky Prize. Find and such that

(i) ,

(ii) is an isolated point in , and

(iii) there exists such that .

To clarify, (i) prevents from being (the Naimark complement of) a SIC, (ii) prevents from belonging to a continuum of inequivalent ETFs, and (iii) prevents from having all triple products belonging to a cyclotomic field. (The field is the union of all cyclotomic fields.) Given a candidate solution , then (i) is easy to certify and (iii) reduces to a straightforward MAGMA query, while (ii) requires a bit more effort. One way to certify (ii) is to estimate the rank of the Jacobian matrix of the defining equations at . Complexifying these equations produces an algebraic variety of “quasi-ETFs.” If an ETF is an isolated point in , then it is also an isolated point in . For reference, Gene implemented this idea in a Mathematica notebook to certify that a particular member of satisfies (ii).

Finally, why is it called a whisky prize? The first person to discover any such and send it to Gene will be rewarded with a bottle of Dalwhinnie Winter’s Frost Single Malt Scotch Whisky, House Stark Game of Thrones Limited Edition. Mind the double-pun/homage: (House Stark Stark units) and (Game of Thrones Game of Sloanes).

Send your solution to Gene Kopp at this page.

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.