I’m going to try collecting additions to my Interesting Esoterica collection in let’s-say-weekly posts. I’ll link to each item, maybe paste its abstract, and write a sentence or two about it. Let’s see if it catches on. I’m not sure if I’ll have the will to do this regularly. I’m in a bit of a getting-things-done mood today.

As this is the first one, and I’ve added loads of stuff in January, for this first post I’m using everything I’ve added since the New Year. Future posts shouldn’t be anywhere near as long.

I should explain what the Interesting Esoterica collection is about. Basically, it’s where I put interesting stuff that I find. Most of the entries are proper research papers, though quite often a funny title is enough to merit inclusion. I certainly don’t read or even understand everything that goes in. I reckon it’s a fairly even split between stuff that’s really fascinating maths and stuff that’s just… esoteric. It’s a bit like a research-level maths version of QI.

The titles are links to the original sources, and I’m trying to sprinkle explanatory links throughout the rest of the text.

Carrots for dessert

Carrots for dessert is the title of a section of the paper ‘On polynomial-like mappings’ by Douady and Hubbard. In that section the authors define a notion of dyadic carrot fields of the Mandelbrot set $M$ and more generally for Mandelbrot like families. They remark that such carrots are small when the dyadic denominator is large, but they do not even try to prove a precise such statement. In this paper we formulate and prove a precise statement of asymptotic shrinking of dyadic Carrot-fields around $M$. The same proof carries readily over to show that the dyadic decorations of copies $M^{\prime }$ of the Mandelbrot set $M$ inside $M$ and inside the parabolic Mandelbrot set shrink to points when the denominator diverge to infinity.

I added this paper almost entirely because of the title. I didn’t know that carrots are a commonly-held metaphor for the ends of trees! At least, according to my colleague Nathan they are.

I just googled “carrot trees”. Somewhere, an algorithm just deducted five intellect points from House CP.

Said googling led me to this similarly intriguingly-titled forum thread, Why do we say “carrot”?

Anyway, I’ve got only a faint idea of what the paper’s about. Something to do with drawing a triangle on top of the Mandelbrot set $M$, and then cutting it in half over and over. The bits of $M$ inside the triangles look a bit like carrots, so together they form a “carrot field”. The paper seems to be saying that as the triangles get smaller, the carrots inside them get smaller too. This isn’t an obvious statement when dealing with fractals, I don’t think.

 

Complexity of Langton’s ant

This one seems to be behind a paywall, sorry. Anyway, it’s about Langton’s Ant, which you can either think of as a cellular automaton, or as a finite state machine wandering across a grid of black/white cells. Or it’s like a really simple Turtle robot, which just has a few rules governing its movement and changes the colour of the ground underneath it.

The paper shows that Langton’s Ant is Turing-complete, which means it can be made to do any computation that a Turing machine can, because it can simulate any boolean circuit. That’s interesting because it doesn’t look complicated enough to be a universal computer! It also means that you can use facts about the undecidability of problems on Turing machines to prove things about what Langton’s Ant can do.

 

On badly approximable numbers and certain games

This came up at December’s MathsJam. This dude Schmidt concocted a game which, when played perfectly, has solutions corresponding to numbers which are badly approximable.

According to the paper, a number is badly approximable if it is irrational and the numbers in its continued fraction representation are all bounded by some constant.

The MathWorld article on badly approximable numbers is a bit more enlightening.

It’s interesting how really weird-looking sets of numbers can arise from innocuous-looking situations, like this game.

Three-dimensional finite point groups and the symmetry of beaded beads

Beaded beads are clusters of beads woven together (usually around one or more large holes).
Their groups of symmetries are classified by the three-dimensional finite point groups, i.e. the finite subgroups of the orthogonal group of degree three, O(3). The question we answer is whether every finite subgroup of O(3) can be realized as the group of symmetries of a beaded bead. We show that this is possible, and we describe general weaving techniques we used to accomplish this feat, as well as examples of a beaded bead realizing each finite subgroup of O(3) or, in the case of the seven infinite classes of finite subgroups, at least one representative beaded
bead for each class.

Group theory plus beads. Galois goes to Mardi Gras.

It astounds me, given how much craft and decoration makes use of symmetry, that it took until the Enlightenment for anyone to write down the rules of group theory. Maybe if more previous men had allowed more previous women to take time off weaving baskets to write down what they knew then we would’ve got there earlier.

Anyway, this is a very readable and accessible investigation of which symmetry groups can be used to make weaving patterns for beaded beads. It explains just about everything either a group theorist or a bead-beader would need to know to understand the result, so I highly recommend you read it.

By the way, these beaded bead things seem to be tensegrity structures. How interesting!

 

How To Gamble If You’re In a Hurry

The beautiful theory of statistical gambling, started by Dubins and Savage (for subfair games) and continued by Kelly and Breiman (for superfair games) has mostly been studied under the unrealistic assumption that we live in a continuous world, that money is indefinitely divisible, and that our life is indefinitely long. Here we study these fascinating problems from a purely discrete, finitistic, and computational, viewpoint, using Both Symbol-Crunching and Number-Crunching (and simulation just for checking purposes).

Zeilberger and gang direct their ideology towards betting.

They pose some questions about what your best strategy should be when playing a game which you will win, on average. Obviously, this doesn’t describe casino gambling at all well, but might be applied to other risky profit-making ventures.

I’d say they don’t really answer their questions in any satisfying way, because they just provide Maple packages to find optimal strategies. Though I’m not sure what context the article exists in, so maybe that’s OK.

I don’t understand Doron Zeilberger or his way of doing maths.

Just noticed I added this in December. Oh well, I’ve written something now, might as well keep it.

 

Random walks on finite groups

Markov chains on finite sets are used in a great variety of situations to approximate, understand and sample from their limit distribution. A familiar example is provided by card shuffling methods. From this viewpoint, one is interested in the “mixing time” of the chain, that is, the time at which the chain gives a good approximation of the limit distribution. A remarkable phenomenon known as the cut-off phenomenon asserts that this often happens abruptly so that it really makes sense to talk about “the mixing time”. Random walks on finite groups generalize card shuffling models by replacing the symmetric group by other finite groups. One then would like to understand how the structure of a particular class of groups relates to the mixing time of natural random walks on those groups. It turns out that this is an extremely rich problem which is very far to be understood.

Or, “how long does it take to shuffle a pack of cards?” And in general, questions like, “how long does it take to shuffle a Rubik’s cube?” or other group-theory-ish objects.

I think this idea just occurred to me one day, so I googled to see if it exists. It does. This is an article on the subject.

 

Computer evolution of buildable objects

Creating artificial life forms through evolutionary robotics faces a “chicken and egg” problem: Learning to control a complex body is dominated by inductive biases specific to its sensors and effectors, while building a body which is controllable is conditioned on the pre-existence of a brain.

The idea of co-evolution of bodies and brains is becoming popular, but little work has been done in evolution of physical structure because of the lack of a general framework for doing it. Evolution of creatures in simulation has been constrained by the “reality gap” which implies that resultant objects are not buildable.

The work we present takes a step in the problem of body evolution by applying evolutionary techniques to the design of structures assembled out of parts. Evolution takes place in a simulator we designed, which computes forces and stresses and predicts failure for 2-dimensional Lego structures. The final printout of our program is a schematic assembly, which can then be built physically. We demonstrate its functionality in several different evolved organisms.

A program which evolves a design for a LEGO model which will fulfil a given task. They get it to build a bridge and a crane.

 

A zero-knowledge Poker protocol that achieves confidentiality of the players’ strategy, or, How to achieve an electronic Poker face

The introduction to this is a bit long, so I’ll paraphrase:

Suppose that $P_1,P_2,\dots ,P_N$ want to play poker, but they’re nowhere near each other so they play over the internet. There’s no trusted central authority to serve as the dealer, so they need a way of agreeing on the order of the cards in the deck without any one player being able to work out what card’s coming next, or what cards anyone else is holding.

This is a prime opportunity to invent a zero-knowledge protocol! If you don’t know what a zero-knowledge protocol is, give your parents a copy of “how to explain zero-knowledge protocols to your children” by Quisquater and Guillou, then get them to explain it to you. ((this joke recycled wholesale from the latest edition of the Internet Maths Aperiodical))

The resulting protocol involves everyone picking a permutation of the cards ((basically shuffling a deck and recording the order of the cards)) and applying each permutation in turn to the virtual deck of cards being used. A couple of very clever protocols involving modular arithmetic make sure that everyone can play the game while convincing the other players that they’re not cheating.

 

A Generalized Fibonacci LSB Data Hiding Technique

The producers of the new Sherlock Holmes film put out a widely-reproduced press release about how they’d gone to the effort of getting some real mathematicians to make up some plausible maths for Moriarty to use.

The press release said they’d invented a cryptographic scheme using things called Fibonacci $p$-numbers, which I’d never heard of before.

This paper is the only source defining them that I could find on google. The interesting part is in Section III.

The paper itself is about using these Fibonacci p-numbers to do steganography.

 

Analysis of Casino Shelf Shuffling Machines

Many casinos routinely use mechanical card shuffling machines. We were asked to evaluate a new product, a shelf shuffler. This leads to new probability, new combinatorics, and to some practical advice which was adopted by the manufacturer. The interplay between theory, computing, and real-world application is developed.

Persi Diaconis and chums, who know a fair bit about shuffling, were asked to check that some casino card-shuffling machines were adequately random. They weren’t, and so a paper was born.

The machines were designed to pass the randomness tests previously developed by people like Diaconis and Fulham, but the authors looked at the probabilities of any of the possible permutations occurring, and found they weren’t quite uniform. To convince the skeptical engineers, they showed that they could correctly guess about twice as many cards from the deck as you’d expect if the deck was properly randomly shuffled.

 

The Collatz Fractal

In this blog post, the author generalises the procedure involved in the Collatz conjecture to work on complex numbers, and uses it to produce a fractal similar to the Mandelbrot set.

I love it when functions on the integers are extended to functions on the reals, or even further. If I was a real mathematician, i.e. an analyst, I’d probably find it less impressive.

This method definitely wasn’t invented by the bloggist, but I can’t find a source for the complex function. The basis of it seems to be the paper, “A continuous extension of the $3x+1$ problem to the real line,” which gives a real-valued function.

 

Ethnomathematics as a new research field, illustrated by studies of mathematical ideas in African history

Some Angolan people apparently create visual mnemonics to help them remember stories. While searching for maths posts on Google+, I found this post with some excellent pictures of the sona, or visual mnemonics.

The Google+ post is what you should really be looking at – it has lots of diagrams and lots of accompanying text explaining what’s going on.

 

Scooping the Loop Snooper

No general procedure for bug checks succeeds.
Now, I won’t just assert that, I’ll show where it leads:
I will prove that although you might work till you drop,
you cannot tell if computation will stop.

Finally, here’s a poem in the vein of Dr Seuss. It’s a proof that the halting problem is undecidable.