• Michael Mitzenmacher is making an unusual request for publicity for his NON-participation in a conference (\(\mathbb{M}\)). It calls itself ICAIM, the International Conference on Artificial Intelligence and Mathematics, to be held in Nanjing in September, and it falsely lists Mitzenmacher as a conference chair, Mike Goodrich as program chair, and Jelani Nelson as a program committee member, among others. None of Michael, Mike, and Jelani have agreed to allow their names to be used in this way. The conference contact email goes to a known spam/phishing site. It appears to be a scam. Be aware!

  • Here’s an example of why it’s important to base Wikipedia’s mathematics content on published sources rather than going by your intuition (\(\mathbb{M}\)). Wikipedia has an article on the classification of manifolds, topological spaces that look “locally” like Euclidean spaces, in the sense that each point has a neighborhood within which the topology is the same as a Euclidean space. From 2007 until very recently this article has said that there are only two connected 1-dimensional manifolds: the circle and the line. You can draw other curves, of course, but they will be topologically equivalent to one or the other of these two spaces. But this is wrong (for the naive definition above; often manifolds are restricted to have a countable open cover, to avoid this sort of example)! There are two more possibilities, the long line obtained by gluing together an uncountable number of copies of a unit interval, and a line-like space obtained by gluing together an ordinary real ray and a long ray. See Frolík (1962), “On the classification of 1-dimensional manifolds”. You might think that just as there is more than one line, there might be more than one long line, obtained by gluing together sets of intervals of different cardinalities. But no, it stops here: apparently only the smallest uncountable ordinal works as a gluing pattern. Anything else would have a limit point where more than countably many unit intervals appear in every neighborhood, and that limit point is not locally Euclidean.

  • If you were using Google Chart to render LaTeX formulas in web pages, it’s long past time to change to something else (\(\mathbb{M}\)). That’s been deprecated so long ago that the deprecation expired in 2015, and it seems it finally stopped working.

  • West Virginia University, the main public university in its state, shuts down pure mathematics as a research topic (\(\mathbb{M}\)). See also Inside Higher Education, “A Flagship Research University… Without Language Degrees or Math Ph.D.s?” (archive) and The New Yorker, “An ‘academic transformation’ takes on the math department”. I’m not in a mathematics department, but I completely agree with the sentiment of an operations researcher quoted by Peter Cameron in the comments of his post: “I could not hold up my head if I were in a university with no mathematics department”.

  • A very easy union bound in probability (\(\mathbb{M}\)) states that, for a collection of independent events whose expected number (the sum of the probabilities of the events) is \(\mu\), the probability \(p\) of the union (that is, the probability of getting at least one event) obeys \(p\ge 1-e^{-\mu}\). When you expect to see many events, even if each one is individually unlikely, the probability of seeing at least one is high. This is a lower bound, unlike the more famous “union bound” \(p\le\mu\) (which doesn’t assume independence), and makes sense even when \(\mu\) is large. See e.g. this stackexchange post asking how to prove it. I have a different question: what is this lower bound on the union called? I looked through the probability inequalities listed by Wikipedia and didn’t see it, but perhaps I missed something obvious.

  • Edited view of the Salvator Dali Museum spiral makes it even trippier.

  • Quanta on integer distances (\(\mathbb{M}\)). The linked article highlights new research of Rachel Greenfeld, Sarah Peluse, and Marina Iliopoulou (arXiv:2401.10821), on sets of planar points with integer distances. A paper of Solymosi shows that any such set has size at most linear in the diameter, achieved by evenly spaced points on the line. There also exist arbitrarily large cocircular integer-distance sets. The new preprint shows that everything else must be small: if you remove the largest point or circle from an integer-distance set, the number of points remaining is polylogarithmic in the diameter. Don’t be confused (as I initially was) by the restriction that the points lie in \([-N,N]^2\): they can have any real coordinate in that range, not just integers. The range limit \(N\) is just a stand-in for the diameter.

    This is all motivated by the Erdős-Anning theorem: if an integer-distance set does not lie entirely on one line, it must be finite. See also my own recent work extending the Erdős-Anning theorem and Solymosi’s diameter bounds in a different direction to various non-Euclidean but two-dimensional spaces, arXiv:2401.06328. A paragraph of the Greenfeld-Peluse-Iliopoulou preprint at the end of section 1.1, claiming that all prior work uses low degree algebraic geometry and because of that could not improve on Solymosi’s work, is somewhat inaccurate. My preprint is prior to theirs, does move beyond Solymosi (in a different direction), and explicitly avoids any algebraic geometry in favor of a topological analysis of Voronoi diagrams that works in other spaces.

  • Fast and simple sorting using partial information (arXiv:2404.04552) (\(\mathbb{M}\)), Bernhard Haeupler, Richard Hladík, John Iacono, Vaclav Rozhon, Robert Tarjan, and Jakub Tětek. Tarjan gave a distinguished seminar on this at my department recently. The result is that if you are given the outcomes of some comparisons on a totally ordered set, as a directed acyclic graph with \(n\) vertices, \(m\) edges, and \(T\) topological orders (linear extensions), you can do more comparisons to complete the sorting proces in time \(O(n+m+\log T)\) using \(O(\log T)\) comparisons. The main ideas include:

    • Combining a greedy topological ordering algorithm with a priority queue on available items to pick out the smallest available item at each step.

    • Using a priority queue with the “working set property”: the time to insert or delete an element \(x\) is logarithmic in the maximum number of other elements that were inserted after \(x\) and active at the same time as each other and \(x\).

    • Proving the working set property for pairing heaps, a simple priority queue.

    • Using a clique decomposition of an interval graph, formed from the lifetimes of elements in the priority queue, to show that the working set bound on the priority queue almost matches the claimed bound on comparisons in terms of \(T\).

    • Some special case handling of input DAGs with long paths to fix up the cases where the two bounds don’t quite match

  • Formal verification of the empty hexagon number (arXiv:2403.17370) (\(\mathbb{M}\)), Bernardo Subercaseaux, Wojciech Nawrocki, James Gallicchio, Cayden Codel, Mario Carneiro, and Marijn J. H. Heule. Heule and Scheucher proved earlier using a SAT solver that sets of 30 or more points in the plane in general position always have an empty hexagon; this is tight as sets of 29 points with no empty hexagon are also known. This new preprint uses Lean to prove the “by hand” part, but the authors write that more needs to be done to connect formal provers to the automatic parts of SAT solver results.

  • Avi Wigderson is this year’s Turing Award winner (\(\mathbb{M}\), see also).

  • Two more newly-promoted Good Articles on Wikipedia (\(\mathbb{M}\)):

    • Random binary tree – not just binary search trees produced through random insertion orders (although those are a central topic) but also uniformly random trees, trees produced through stochastic branching processes, and digital search trees for random binary numbers. These different distributions give different properties: for instance, random-insertion trees have logarithmic depth but for uniformly random trees it is proportional to the square root. For certain branching processes, even the expected number of nodes is unbounded.

    • Earth–Moon problem – how many colors would you need to color a political map in a future in which each Earth nation has a contiguous Moon colony? Unlike the situation with the four-color theorem, the answer remains unknown. Beyond sci-fi cartography, there are some applications in printed-circuit board testing.

  • The Italian court system continues its attack on the public domain (\(\mathbb{M}\), via, see also), ruling that the Florence gallery that owns Michelangelo’s David also owns “image rights” to the statue, can require licensing fees for any image depicting it, and can impose additional fines for presenting it in a distorted way. It is perhaps important to note that the statue, created in 1504, was on outdoor exhibit in a public square in Florence until 1873, and a replica is still visible there.

  • Somehow I ended up with the following two images adjacent in my Mastodon favorites list (\(\mathbb{M}\)): the ceiling of a museum in Uzbekistan, intricately decorated by two sizes of 60°-90°-120°-90° kites, and a tiling by approximate 60°-120° diamonds, distorted to reduce in size as they approach a central limit. Both remind me of my old work on diamond-kite meshes, which combine these two shapes to allow the mesh to vary in scale without distortion. See also another image inspired by this post.

  • US government holds back new grants to an entire university (\(\mathbb{M}\), archived), the University of California, San Diego, because some guy retired in 2022 without finishing his final grant reports. The story says he’s doing them now, but what would have happened if he got hit by a bus?