Linkage

Two recent posts by Dave Richeson on connections between stamp folding and the design of circular labyrinths and their combinatorial enumeration as meanders (\(\mathbb{M}\)). See also Wikipedia on map folding and meanders.

Here’s a long-standing mistake in Wikipedia’s algorithms coverage (\(\mathbb{M}\)). From August 2013 until recently the quickselect article stated “quickselect has almost certain \(O(n)\) time complexity” or “a random pivot, which yields almost certain linear time”, or some other form of this statement. This turns out to be false. There is no constant \(C\) such that the probability of performing fewer than \(Cn\) comparisons goes to one in the limit as \(n\) goes to infinity. Instead, if you are using quickselect to find the minimum element (say), you will perform more than \(Cn\) comparisons in the case that the first \(2C\) pivots all land in the top half of the inputs, in decreasing order. This happens with constant probability, exponentially small in \(C\log C\) but independent of \(n\). Luc Devroye in two papers showed upper bounds on the probability of many comparisons, exponential and then (as above) superexponential in \(C\): see “Exponential bounds for the running time of a selection algorithm” (1984), and “On the probabilistic worst-case time of ‘Find’” (2001). So the probability of linearity is indeed very close to one, but it is not almost certain.

Thread by Terry Tao with images of historical manuscripts at the Institut de France, including Poincaré’s anticipation of special relativity, Pascal’s triangle (in a book by Pascal), Galois’s last letter, a Gutenberg bible, and some historical portraits.

Did you know that the first publication to connect carbon dioxide levels to global warming, by 19th century amateur scientist Eunice Newton Foote, went long forgotten until uncovered by feminist historians in the 1970s (\(\mathbb{M}\)). Via a profile of Wikipedia volunteer SusunW who significantly expanded Foote’s article last year, bringing it to Featured Article status.

Knitted origami (\(\mathbb{M}\)), techniques for embedding sharp creases as features in knitted fabric.

Two more recent Wikipedia Good Articles (\(\mathbb{M}\)):

• Unit fraction – you know, like 1/2, 1/3, 1/27, etc.

• Beckman–Quarles theorem, according to which the only mappings from the Euclidean plane to itself that preserve unit distances are the obvious ones: translations, rotations, mirror reflections, and glide reflections. In contrast, mappings into higher dimensions can be much messier; for instance, there is a unit-distance-preserving map from the plane to a set of only seven distinct points in six dimensions.

Selected paintings by Julian Stanczek (\(\mathbb{M}\)), very geometric in their use of color, form, and line.

Large libel models (\(\mathbb{M}\), via). Far more than you probably wanted to know about: when ChatGPT makes up fake scandals about real people, who is responsible for the resulting libel? Also via Wikipedia, where there have been multiple incidents of editors adding falsified LLM-written content to Wikipedia, and discussions about how to keep this junk out. But attempts to ban LLM content have been somewhat stymied by too many under-informed editors who think “isn’t it neat that computers can write Wikipedia articles” or “won’t someone think of the people who can’t write themselves but can get computers to write for them”.

Nonabelian Set (\(\mathbb{M}\)), a variation of the Set card game (in which one seeks triples of cards that form lines in a finite geometry) where the cards represent permutation group elements and the goal is to find sequences of tiles that compose to the identity. One of many neat mathematical projects and visualizations from a 2019 program, “Illustrating Mathematics”, at the Brown University Institute for Computational and Experimental Research in Mathematics.

Simon Tatham writes about two algorithms for randomly generating aperiodic tilings (\(\mathbb{M}\)), including the new hat tiling, which we might expect to see soon as one of the fields for the Loopy puzzle in Tatham’s puzzle collection.

Laplace’s Rule of Succession (\(\mathbb{M}\)). An intuitive explanation for why, after seeing \(k\) heads out of \(n\) flips of a coin with unknown bias, your estimate for the bias should be \((k+1)/(n+2)\).

Quanta on why randomness is useful in algorithm design (\(\mathbb{M}\)).

Igor Pak names and shames high-level journals claiming to cover all of mathematics, but actually excluding all of combinatorics (\(\mathbb{M}\)). The follow-up discussion also concerns similar prejudices against category theory, and how a hypothetical book on categorical combinatorics would be treated.

Kaktovik numerals, an intuitive system of base-20 digits invented by Iñupiat schoolchildren, are getting added to Unicode (\(\mathbb{M}\)).

Amusing to see an application of Mornington Crescent in group theory (\(\mathbb{M}\)). Peter Cameron looks at bases, sequences of the elements permuted by a permutation group whose permuted values are sufficient to identify which group element permuted them. For bases that are minimal under taking prefixes, the possible base lengths form a contiguous interval of integers.