de Bruijn sequences (also known as Ouroborean rings in Professor Stewart’s Cabinet of Mathematical Curiosities, p. 44) are an interesting topic that have a surprising connection to moving across a square, and the security of most phone unlock screens. These sequences make a compact listing of all the possible values, in a repeating (cyclical) string of values.
An Ouroborean ring is one that easily lists all combinations of certain elements, with a list that is gone through moving one character by one character. For example a simple one is:
0011
This is considered to be repeating, so this is (00110), which when read two at a time is 00, 01, 11, 10, which are all the combinations of two 0s and 1s. These are moving one at a time so this equates to moving around a square by reading off a sequence two at a time:
Similarly visiting a three dimensional cube’s corner points, going along the edges, will give you the coordinates that give you the Ouroborean ring from the book, for 3-tuple (0,1,1), (1,1,1), (1,1,0),…:
01110100…
Higher dimensions for higher tuples have the same pattern.
Key codes and security
Remember the Ford vehicles with the numbered unlock buttons on the side? Some older versions of this have an issue where they can be “picked” by inputting a long string of numbers until it unlocks, within 20 minutes. According to Craig Smith‘s book “This method works because the key codes roll into one another. The vehicle doesn’t know where one code ends and the other one starts, which means that you don’t have to try each possibility in order to stumble on the right combination.” Someone even built a robot to crack the code on the older Ford key code locks.
In other words the lock in some of those old cars checked the most recent digits entered. Requiring some wait period or “enter” key would have upped the maximum time to unlock to over an hour. This is an interesting bit of history and likely a reason why phones are the direct opposite – you must press enter after entering your unlock code. If this were not the case, and there were not a limit on the speed of entry as was added in some later vehicles, then this could be a serious security issue on a device that holds your personal information! It seems later phones and devices learned the lesson from some of the older vehicles and the mathematics of Ouroborean ring that weakened security of a handy keyless entry.