Linkage
-
A permutation generation algorithm in the work of 13th-century Kabbalist Abraham Abulafia (\(\mathbb{M}\), via). The resulting permutation sequence is the one you get by reversing suffixes whose lengths form the sequence \((((2, 3)^2, 2, 4)^3, 2, 5)^4, \dots\) but that’s not the generation rule. Instead the rule is: to generate the permutations of \(1, 2, 3,\dots, n,\) form its \(n\) cyclically rotated permutations (starting with \(1, 2, 3,\dots, n,\)) and for each one in order, recursively generate the permutations of its length-\((n-1)\) suffix.
The link claims that this is the first method for systematically listing permutations (long before the discovery of the Steinhaus–Johnson–Trotter algorithm for generating a different ordering, by 17th-century bell ringers). However, I’m not entirely convinced: it’s not the same as an enumeration algorithm, but factorials and lists of permutations were known long before to the Jain mathematicians, to scholars of the Talmudic period, and to medieval Arab grammarians and mathematicians (see Wikipedia on the history of the factorial). They may not have described their rules for generating lists of permutations, but they did generate those lists, presumably by following some rule. Priority arguments aside, though, I still think it’s interesting.
-
Complexity Class of the Week: \(\mathsf{L}_2^P\) (\(\mathbb{M}\)). This is a complexity class characterized by polynomial-time reductions to finding the minimum element of a comparator circuit that computes a total order, or finding a violation of total ordering for the circuit. It has interesting relations both to other complexity classes (e.g. \(\mathsf{NP}\subset\mathsf{P/poly}\) collapses \(\mathsf{PH}\) to \(\mathsf{L}_2^P\)) and to circuit complexity (it requires circuits of size \(\ge n^k\) for all fixed \(k\)).
-
Terry Tao on recent problematic behavior in mathematics research (\(\mathbb{M}\)): AI companies generate a solution to a well-known problem, take the publicity for their solution, but don’t take the effort to digest and explain the solution in a way that makes sense to human mathematicians.
-
Transliteration of unicode text from one script to another through its Locale Data Markup Language is Turing-complete (\(\mathbb{M}\), via). The proof is via Post tag systems. The widely-used ICU library guards against this by imposing a small limit on the number of times a unit can be rewritten, so there is no denial-of-service vulnerability in practice, but this limit is not in the spec.
-
Leslie Lamport’s dictum “State the problem before describing the solution” (\(\mathbb{M}\)).
-
Big spike in monthly submissions to arXiv Combinatorics (\(\mathbb{M}\)).
-
Q&A from the slop trenches (\(\mathbb{M}\), via). Two human machine-learning researchers on their recent experiences refereeing LLM-generated slop with bad references, and then getting their reject recommendations overridden as accept for oral presentation with an unenforceable request to fix the slop.
-
Asymptotically attaining the Moore bound (\(\mathbb{M}\)), Wouter Cames van Batenburg and Samuel Korsky, on the largest graphs with maximum degree \(d\) and diameter \(k\), for fixed \(k\) in the limit as \(d\) grows.
-
The mathematical beauty of hyperbezier curves (\(\mathbb{M}\)), on a curve family with the same control points as cubic Bézier curves but with smoother curvature variation and a larger range of parameters for which the curvature is monotonic.
-
The only reason you’ll ever need not to write with AI (\(\mathbb{M}\)): because it could expose you to charges of plagiarism.
-
Illinois Tech lays off roughly 160 tenured faculty members including Lance Fortnow (\(\mathbb{M}\)).
-
A stroll through the pentagram zoo (\(\mathbb{M}\)). Richard Evan Schwartz explains the mathematics behind some of his mathematical artworks, based on the pentagram map, a dynamical system that repeatedly replaces the vertices of a polygon by the crossing points of its diagonals.
-
Slides for my two talks at CCCG’26 are now online (\(\mathbb{M}\)):