Interesting Esoterica Summation
I feel like it’s time to do another summary of my recent additions to the Interesting Esoterica collection.
A reminder of what it’s all about: every now and then I encounter a paper or a book or an article that grabs my interest but isn’t directly useful for anything. It might be about some niche sub-sub-subtopic I’ve never heard of, or it might talk about something old from a new angle, or it might just have a funny title. I put these things in my Interesting Esoterica collection on Mendeley.
In this post the titles are links to the original sources, and I try to add some interpretation or explanation of why I think each thing is interesting below the abstract.
Some things might not be freely available, or even available for a reasonable price. Sorry.
Philosophy of Engineering
Volume 2 of the proceedings of a series of seminars held at the Royal Academy of Engineering
Sometimes engineers do a bit of philosophy! Who knew?
Claims Presper Eckert invented the computer. Controversial.
Gaming is a hard job, but someone has to do it!
We establish some general schemes relating the computational complexity of a video game to the presence of certain common elements or mechanics, such as destroyable paths, collecting items, doors activated by switches or pressure plates, etc.. Then we apply such “metatheorems” to several video games published between 1980 and 1998, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, and Starcraft. We obtain both new results, and improvements or alternative proofs of previously known results.
Uses a bit of artistic licence to put well-loved games into complexity classes.
The Hardness of the Lemmings Games, or Oh no, more NP-Completeness Proofs
In the computer game ‘Lemmings’, the player must guide a tribe of green-haired lemming creatures to safety, and save them from an untimely demise. We formulate the decision problem which is, given a level of the game, to decide whether it is possible to complete the level (and hence to find a solution to that level). Under certain limitations, this can be decided in polynomial time, but in general the problem is shown to be NP-Hard. This can hold even if there is only a single lemming to save, thus showing that it is hard to approximate the number of saved lemmings to any factor.
This paper is cited by the previous one as an inspiration. It’s much more detailed (and, in my opinion, rigorous) and has a funnier title.
Compositional Reasoning Using Intervals and Time Reversal
We apply Interval Temporal Logic (ITL), an established temporal formalism for reasoning about time periods, to extending known facts by looking at them in reverse and then reducing reasoning about infinite time to finite time. Time reversal then helps to compositionally analyse some aspects of concurrent behaviour involving mutual exclusion.
Something about proving facts about concurrent systems. The claim in the abstract that they look at things in reverse time was interesting, but it’s a very hard paper to read.
Continued fractions constructed from prime numbers
We give 50 digits values of the simple continued fractions whose denominators are formed from a) prime numbers, b) twin primes, c) generalized
-twins, d) primes of the form , e)primes of the form , f) Mersenne primes and g) primorial primes. All these continued fractions belong to the set of measure zero of exceptions to the theorems of Khinchin and Levy. We claim that all these continued fractions are transcendental numbers. Next we propose the conjecture which indicates the way to deduce the transcendence of some continued fractions from transcendence of another ones.
The thought suddenly occurred to me one day that it might be interesting to look at the continued fraction where the denominators are the prime numbers, in order, i.e.,
Well, I put “continued fraction prime numbers” into Google and this paper came up. It’s really quite interesting!
The most interesting fact about the continued fraction constructed from the primes is that it is perilously close to one of Rényi’s parking constants. What an interesting coincidence!
Tropical Mathematics
These are the notes for the Clay Mathematics Institute Senior Scholar Lecture which was delivered by Bernd Sturmfels in Park City, Utah, on July 22, 2004. The topic of this lecture is the “tropical approach” in mathematics, which has gotten a lot of attention recently in combinatorics, algebraic geometry and related fields. It offers an an elementary introduction to this subject, touching upon Arithmetic, Polynomials, Curves, Phylogenetics and Linear Spaces. Each section ends with a suggestion for further research. The bibliography contains numerous references for further reading in this field.
This came up in the last Newcastle MathsJam. This simple algebraic ring has an unexpectedly huge number of applications, though I feel like it’s the kind of thing I’ll never really get the knack for.
Gerrymandering and Convexity
This article integrates a variety of mathematical topics to give the reader insight into the vagaries of gerrymandering, in which each state re-carves itself into often highly non-convex shapes or districts which have roughly the same population but are designed to give unfair advantage to the party in power. Beginning with several simple examples to show how this works, the authors then give a clear overview of gerrymandering and measures of shape compactness and convexity that have been introduced over the past several decades. They then proceed to develop their own measure, the ‘convexity coefficient’ of a planar region, which is the probability that the line segment connecting two random points of the region is itself entirely contained within the region. They use Monte Carlo methods to approximate the convexity coefficient for each of the 435 congressional districts in the country, which allows the reader to compare their state to others.
But is this measure fair, comparing highly non-convex states to highly convex states? Delaware with only one district only gets a 0.855 rating. The authors are up to the challenge, modifying their measure to not only take into account the natural boundary of the state, but also non-uniform population distributions. To illustrate the subtle complexity of reapportionment, the paper ends with an example to show that gerrymandering can even occur if the boundaries of the districts look extremely regular and the population is distributed evenly across the geographic district.
I can’t remember how I found this, but it’s definitely interesting. It won an award for being so!
In retrospect: on the six-cornered snowflake
Philip Ball celebrates the fourth centenary of Johannes Kepler’s ice-crystal analysis.
Prompted by Matt Parker’s “snowfake” campaign.
Mapping an unfriendly subway system
We consider a class of highly dynamic networks modelled on an urban subway system. We examine the problem of creating a map of such a subway in less than ideal conditions, where the local residents are not enthusiastic about the process and there is a limited ability to communicate amongst the mappers. More precisely, we study the problem of a team of asynchronous computational entities (the mapping agents) determining the location of black holes in a highly dynamic graph, whose edges are defined by the asynchronous movements ofmobile entities (the subway carriers). We present and analyze a solution protocol. The algorithm solves the problem with the minimum number of agents possible. We also establish lower bounds on the number of carrier moves in the worst case, showing that our protocol is also move-optimal.
If someone had had a better idea in the 80s, this could have been another paper with a witty videogame-inspired title. Anyway, the problem is quite interesting. Apparently it’s useful for network engineers who want to detect crashed nodes. I hope it gets applied to a real subway system at some point.
Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles
We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier.
In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our physical protocols utilize scratch-off cards, similar to those used in lotteries, or even just simple playing cards.
The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by ”lay-people” and implementable without the use of computers.
I love zero-knowledge proof. This one shows how to convince somebody that you can solve a Sudoku puzzle, without revealing your solution. It even gives a couple of ideas of how to implement the protocol in real life, with pen and paper and scissors. I want to try it out at MathsJam.
Benjamin Peirce and the Howland Will
The Howland will case is possibly the earliest instance in American law of the use of probabilistic and statistical evidence. Identifying 30 downstrokes in the signature of Sylvia Ann Howland, Benjamin Peirce attempted to show that a contested signature on a will had been traced from another and genuine signature. He argued that their agreement in all 30 downstrokes was improbable in the extreme under a binomial model. Peirce supported his model by providing a graphical test of goodness of fit. We give a critique of Peirce’s model and discuss the use and abuse of the “product rule” for multiplying probabilities of independent events.
Brought to my attention by this Metafilter thread about the plaintiff, the enormously popularly disliked Hetty Green.
Good stories, pity they’re not true
A teacher friend-of-a-friend recently posted some golden ratio “resources” on the TES which repeated the false claim that the golden ratio can be found in the proportions of the human body. I dug up this article as evidence. I suppose this could be linked to Peter Rowlett’s musings about false-but-enjoyable maths history misconceptions.
Fibonacci Determinants — A Combinatorial Approach
In this paper, we provide combinatorial interpretations for some determinantal identities involving Fibonacci numbers. We use the method due to Lindstrom-Gessel-Viennot in which we count nonintersecting
-routes in carefully chosen digraphs in order to gain insight into the nature of some well-known determinantal identities while allowing room to generalize and discover new ones.
I’ve recently been thinking about the determinants of
I tried to do due diligence and see if anyone had looked at the same thing before. They probably have, but this is the closest thing I could get. It’s slightly different – it tries to find matrices which encapsulate identities about the Fibonacci sequence.
This paper talks about Gibonacci numbers as if they’re common knowledge. In fact, I found three completely contradictory definitions of Gibonacci numbers. The most they had in common was that they were all trying to generalise some property of the original Fibonacci numbers.
Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later
In principle, the exponential of a matrix could be computed in many ways. Methods involving approximation theory, differential equations, the matrix eigenvalues, and the matrix characteristic polynomial have been proposed. In practice, consideration of computational stability and efficiency indicates that some of the methods are preferable to others, but that none are completely satisfactory. Most of this paper was originally published in 1978. An update, with a separate bibliography, describes a few recent developments.
Recently, I was updating the maths functions in Numbas and noticed that there was no way to take a non-integer power of a matrix. I thought surely somebody must have written a bit of interesting esoterica on the subject.
I returned from Google ended up empty-handed, but I did find this paper about the opposite operation, where the matrix is the exponent. It’s a nice cautionary tale about the dangers of assuming that theoretically equivalent operations will produce the same results on limited-precision computers.
Pantologia. A new (cabinet) cyclopædia, by J.M. Good, O. Gregory, and N. Bosworth assisted by other gentlemen of eminence
David Cushing asked me this question, which I don’t have an answer for: does
converge?
Actually, just thinking about it now, I think I do have an answer.
Anyway, I did a search for “continued surd” and this book came up. Its entry on surds doesn’t seem to have an answer to David’s question but it does talks about some other interesting ones. It looks like the author got distracted by a fun bit of maths while writing.
Actually, the intelligibility of both the words and the notation make me wonder – has mathematical notation changed faster or slower than the English language? Is that a question that can even be answered, either way?
And I’ve just noticed that one of the authors was an honorary member of the Lit & Phil! Local bonus!
Fractions without quotients: Arithmetic of repeating decimals
The difficulties encountered in defining and performing addition and multiplication of real numbers.
This turns out to be another Pólya award-winning essay. It’s about how hard it is to do addition and multiplication when numbers aren’t written down the way you’re used to. I might try this out on the undergrads at the next MathsJam.