Linkage from Montréal

The Higher Geometer gets grumpy over paywalls for back issues of The Duke Mathematical Journal. Some but not all of them can also be found on the Internet Archive. But everything before 1943 is out of copyright and should be free.

“Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent” (\(\mathbb{M}\)) is this year’s winner of the WADS best paper award for its authors, Ofek Gila, Mike Goodrich, and Bob Tarjan. Gila is one of Mike’s students at UCI. The paper continues a line of research on random binary search trees (where the keys are assumed to be insertion-only, arriving in random order), treaps (which use randomly chosen priorities and rotations to get behavior like that of random arrivals for inputs with non-random insertion and deletion operations), and zip trees (which simplify treaps using a zip-and-unzip mechanism in place of rotations, but give up some amount of balance to do so). The new zip-zip trees have the same random shape distribution as random trees and treaps, the same zip mechanism and low number of random bits as zip trees, and the same strong history-independence properties as zip trees (useful in some crypto applications).

Graph Drawing 2023 accepted papers (\(\mathbb{M}\)). These should start appearing slowly on arXiv but the proceedings deadline is not until early September so some of them may cut it close to then.

My wife caught one of the kittens in his new favorite box (\(\mathbb{M}\)), a little stylized by her phonecam.

UnsolvedMrE asks: which rectangles have two-piece dissections into a square?

Isaac Grosof posts: The first period-41 oscillator in Conway’s Game of Life was just found by Nico Brown (\(\mathbb{M}\)). With that, oscillators of every period are known: Conway’s Game of Life is omniperiodic! This has been one of the major open problems in the study of Conway’s Game of Life even since its invention over fifty years ago. This comes just 7 days after the second-to-last period, period 19, was discovered.

In case anyone, like me, has a link to a Wikipedia user page from their Mastodon profile, and wants it to be marked in green as a verified link (via the rel=me attribute at the user page your profile links to), you can now do this (\(\mathbb{M}\))! This adds a special code to your Wikipedia user page so that your Mastodon profile can verify that it really belongs to you.

Somehow recent events in social media remind me of this song by X about a former friend who turned super-racist and had to go away (\(\mathbb{M}\)).

Origami-inspired art by Australian artist Cassandra Laing (\(\mathbb{M}\)): “Fortune Teller (it will all end in stars)”, and “No Time To Waste” (also visible with three other similar pieces in this gallery view). They look like photos of origami but are actually large photorealistic pencil drawings. A newspaper story about Laing in The Age mentions two more, “My Paper Ancestors” with an origami dinosaur, and “Last migration”, in which “flocks of origami pteranodons fly over the Antarctic icebergs”, but I haven’t been able to find online images of them.

Women of the Manhattan Project (\(\mathbb{M}\)).

On a thread about why expm1 and log1p are included in mathematics libraries when we could almost as easily write \(\exp(x)-1\) and \(\log(1+x)\) (answer: because they’re commonly used for \(x\) close to zero, for which those other expressions would be numerically unstable) Jannis Harder points out an important use case: If you want to compute \((1-p)^n\), the probability of success after many trials with a low failure probability, you should use exp(n*log1p(-p)). Doing it that way rather than the more obvious expression results in a much smoother and more accurate approximation to the correct answer.

Why wavy brick walls use fewer bricks than straight walls (\(\mathbb{M}\), via): because you don’t need to make them so thick to prevent them from falling down.

Sophie makes an epicycle clock app. The minute hand is attached to the end of the hour hand and traces out a loopy path. There’s also a not-very-helpful second-hand version.

The independent set version of the Hadwiger–Nelson problem (\(\mathbb{M}\), on coloring the infinite unit distance graph of points in the plane) asks: what fraction of the plane can you cover by points that are all at least one unit of distance apart? You can get 1/7 by using one of the seven color classes of a 7-coloring of the plane, but a significantly larger area, roughly 23%, is possible. Quanta magazine reports on progress in the other direction, bringing the upper bound below 25%. Based on “The density of planar sets avoiding unit distances”, Gergely Ambrus, Adrián Csiszárik, Máté Matolcsi, Dániel Varga, and Pál Zsámboki.