oh my gosh: how did I not know about this counting-out system called Yan-Tan...?! I was looking up something about the nursery rhyme Hickory Dickory Dock, which some people think is a counting out rhyme, and that led to this British sheep-counting system: https://t.co/NWfJgyicB6pic.twitter.com/azXjrpo8ob

Suppose you have a keypad that will unlock a door as soon as it sees a specified sequence of four digits. There’s no “enter” key to mark the end of a four-digit sequence, so the four digits could come at any time, though they have to be sequential. So, for example, if the pass code is 9235, if you started entering 1139235… the lock would open as soon as you enter the 5.
How long would it take to attack such a lock by brute force? There are 104 possible 4-digit codes, so you could enter 000000010002…99989999 until the lock opens, but there’s a more efficient way. It’s still brute force, but not quite as brute.

An interesting serendipitous read just as I’m coincidentally doing some other combinatorial work relating to Polya and De Bruijn.

A couple weeks ago I wrote about how De Bruijn sequences can be used to attack locks where there is no “enter” key, i.e. the lock will open once the right symbols have been entered.
Here’s a variation on this theme: what about locks that let you press more than one button at a time?

Originally bookarked on November 06, 2019 at 12:08PM

As it happens, he’d already done some work on coding theory—in the area of biology. The digital nature of DNA had been discovered by Jim Watson and Francis Crick in 1953, but it wasn’t yet clear just how sequences of the four possible base pairs encoded the 20 amino acids. In 1956, Max Delbrück—Jim Watson’s former postdoc advisor at Caltech—asked around at JPL if anyone could figure it out. Sol and two colleagues analyzed an idea of Francis Crick’s and came up with “comma-free codes” in which overlapping triples of base pairs could encode amino acids. The analysis showed that exactly 20 amino acids could be encoded this way. It seemed like an amazing explanation of what was seen—but unfortunately it isn’t how biology actually works (biology uses a more straightforward encoding, where some of the 64 possible triples just don’t represent anything). ❧

I recall talking to Sol about this very thing when I sat in on a course he taught at USC on combinatorics. He gave me his paper on it and a few related issues as I was very interested at the time about the applications of information theory and biology.

I’m glad I managed to sit in on the class and still have the audio recordings and notes. While I can’t say that Newton taught me calculus, I can say I learned combinatorics from Golomb.

A new proof from the Australian science fiction writer Greg Egan and a 2011 proof anonymously posted online are now being hailed as significant advances on a puzzle mathematicians have been studying for at least 25 years.

I wonder what happens when the reverse process is run on numbers like pi? This could be an interesting thing to take a look at in my current math class.

Last night was the first lecture of Dr. Miller’s Gems And Astonishments of Mathematics: Past and Present class at UCLA Extension. There are a good 15 or so people in the class, so there’s still room (and time) to register if you’re interested. While Dr. Miller typically lectures on one broad topic for a quarter (or sometimes two) in which the treatment continually builds heavy complexity over time, this class will cover 1-2 much smaller particular mathematical problems each week. Thus week 11 won’t rely on knowing all the material from the prior weeks, which may make things easier for some who are overly busy. If you have the time on Tuesday nights and are interested in math or love solving problems, this is an excellent class to consider. If you’re unsure, stop by one of the first lectures on Tuesday nights from 7-10 to check them out before registering.

Lecture notes

For those who may have missed last night’s first lecture, I’m linking to a Livescribe PDF document which includes the written notes as well as the accompanying audio from the lecture. If you view it in Acrobat Reader version X (or higher), you should be able to access the audio portion of the lecture and experience it in real time almost as if you had been present in person. (Instructions for using Livescribe PDF documents.)

We’ve covered the following topics:

Class Introduction

Erdős Discrepancy Problem

n-cubes

Hilbert’s Cube Lemma (1892)

Schur (1916)

Van der Waerden (1927)

Sylvester’s Line Problem (partial coverage to be finished in the next lecture)

Over the coming days and months, I’ll likely bookmark some related papers and research on these and other topics in the class using the class identifier MATHX451.44 as a tag in addition to topic specific tags.

Course Description

Mathematics has evolved over the centuries not only by building on the work of past generations, but also through unforeseen discoveries or conjectures that continue to tantalize, bewilder, and engage academics and the public alike. This course, the first in a two-quarter sequence, is a survey of about two dozen problems—some dating back 400 years, but all readily stated and understood—that either remain unsolved or have been settled in fairly recent times. Each of them, aside from presenting its own intrigue, has led to the development of novel mathematical approaches to problem solving. Topics to be discussed include (Google away!): Conway’s Look and Say Sequences, Kepler’s Conjecture, Szilassi’s Polyhedron, the ABC Conjecture, Benford’s Law, Hadamard’s Conjecture, Parrondo’s Paradox, and the Collatz Conjecture. The course should appeal to devotees of mathematical reasoning and those wishing to keep abreast of recent and continuing mathematical developments.

Suggested Prerequisites

Some exposure to advanced mathematical methods, particularly those pertaining to number theory and matrix theory. Most in the class are taking the course for “fun” and the enjoyment of learning, so there is a huge breadth of mathematical abilities represented–don’t not take the course because you feel you’ll get lost.

I’d complained to the UCLA administration before about how dirty the windows were in the Math Sciences Building, but they went even further than I expected in fixing the problem. Not only did they clean the windows they put in new flooring, brand new modern chairs, wood paneling on the walls, new projection, and new white boards! I particularly love the new swivel chairs, and it’s nice to have such a lovely new environment in which to study math.

Category Theory for Winter 2019

As I mentioned the other day, Dr. Miller has also announced (and reiterated last night) that he’ll be teaching a course on the topic of Category Theory for the Winter quarter coming up. Thus if you’re interested in abstract mathematics or areas of computer programming that use it, start getting ready!

By making the first progress on the “chromatic number of the plane” problem in over 60 years, an anti-aging pundit has achieved mathematical immortality.

Perhaps you've heard about IBM's giant Watson computer, which dispenses ingredient advice and novel recipes. Jaan Altosaar, a PhD candidate at Princeton University, is working on a recipe recommendation engine that anyone can use.

I found the article in it so interesting, there was some brief conversation around it and I thought to recommend it to my then new friend Jeremy Cherfas, whose Eat This Podcast I had just recently started to enjoy. Mostly I thought he would find it as interesting as I, though I hardly expected he’d turn it into a podcast episode. Though I’ve been plowing through back episodes in his catalog, fortunately this morning I ran out of downloaded episodes in the car so I started streaming the most recent one to find a lovely surprise: a podcast produced on a tip I made.

While he surely must have been producing the episode for some time before I started supporting the podcast on Patreon last week, I must say that having an episode made from one of my tips is the best backer thank you I’ve ever received from a crowd funded project.

Needless to say, I obviously found the subject fascinating. In part it did remind me of a section of Herve This’ book The Science of the Oven (eventually I’ll get around to posting a review with more thoughts) and some of his prior research which I was apparently reading on Christmas Day this past year. On page 118 of the text This discusses the classic French sauces of Escoffier’s students Louis Saulnier and Theodore Gringoire [1] and that a physical chemical analysis of them shows there to be only twenty-three kinds. He continues on:

A system that I introduced during the European Conference on Colloids and Interfaces in 2002 [2] offers a new classification, based on the physical chemical structure of the sauce. In it, G indicates a gas, E an aqueous solution, H a fat in the liquid state, and S a solid. These “phases” can be dispersed (symbol /), mixed (symbol +), superimposed (symbol θ), included (symbol @). Thus, veal stock is a solution, which is designated E. Bound veal stock, composed of starch granules swelled by the water they have absorbed, dispersed in an aqueous solution, is thus described by the formula (E/S)/E.

This goes on to describe in a bit more detail how the scientist-cook could then create a vector space of all combinations of foods from a physical state perspective. A classification system like this could be expanded and bolted on top of the database created by Jaan Altosaar and improved to provide even more actual realistic recipes of the type discussed in the podcast. The combinatorics of the problem are incredibly large, but my guess is that the constraints on the space of possible solutions is brought down incredibly in actual practice. It’s somewhat like the huge numbers of combinations the A, C, T, and Gs in our DNA that could be imagined, yet only an incredibly much smaller subset of that larger set could be found in a living human being.

Small World

The additional byproduct of catching this episode was that it finally reminded me why I had thought the name Jaan Altosaar was so familiar to me when I read his article. It turns out I know Jaan and some of his previous work. Sometime back in 2014 I had corresponded with him regarding his fantastic science news site Useful Science which was just then starting. While I was digging up the connection I realized that my old friend Sol Golomb had also referenced Jaan to me via Mark Wilde for some papers he suggested I read.

References

[1]

T. Gringoire and L. Saulnier, Le répertoire de la cuisine. Dupont et Malgat, 1914.

📖 Read pages 191 – 215 of At Home in the Universe by Stuart Kauffman

In chapter 9 Kauffman applies his NK landscape model to explain the evolution seen in the Cambrian explosion and the re-population following the Permian extinction. He then follows it up with some interesting discussion which applies it to technological innovation, learning curves, and growth in areas of economics. The chapter has given me a few thoughts on the shape and structure (or “landscape”) of mathematics. I’ll come back to this section to see if I can’t extend the analogy to come up with something unique in math.

The beginning of Chapter 10 he begins discussing power laws and covering the concept of emergence from ecosystems, coevolution, and the evolution of coevolution. In one part he evokes Adam Smith’s invisible hand which seemingly benefits everyone acting for its own selfishness. Though this seems to be the case since it was written, I do wonder what timescales and conditions it works under. As an example, selfishness on the individual, corporate, nation, and other higher levels may not necessarily be so positive with respect to potential issues like climate change which may drastically affect the landscape on and in which we live.

A new paper (arXiv) and some videos on entropy and algorithmic complexity

I’ve run across some of his work before, but I ran into some new material by Hector Zenil that will likely interest those following information theory, complexity, and computer science here. I hadn’t previously noticed that he refers to himself on his website as an “information theoretic biologist” — everyone should have that as a title, shouldn’t they? As a result, I’ve also added him to the growing list of ITBio Researchers.

If you’re not following him everywhere (?) yet, start with some of the sites below (or let me know if I’ve missed anything).

A common practice in the estimation of the complexity of objects, in particular of graphs, is to rely on graph- and information-theoretic measures. Here, using integer sequences with properties such as Borel normality, we explain how these measures are not independent of the way in which a single object, such a graph, can be described. From descriptions that can reconstruct the same graph and are therefore essentially translations of the same description, we will see that not only is it necessary to pre-select a feature of interest where there is one when applying a computable measure such as Shannon Entropy, and to make an arbitrary selection where there is not, but that more general properties, such as the causal likeliness of a graph as a measure (opposed to randomness), can be largely misrepresented by computable measures such as Entropy and Entropy rate. We introduce recursive and non-recursive (uncomputable) graphs and graph constructions based on integer sequences, whose different lossless descriptions have disparate Entropy values, thereby enabling the study and exploration of a measure’s range of applications and demonstrating the weaknesses of computable measures of complexity.

Subjects: Information Theory (cs.IT); Computational Complexity (cs.CC); Combinatorics (math.CO)
Cite as: arXiv:1608.05972 [cs.IT] (or arXiv:1608.05972v4 [cs.IT]

YouTube

Yesterday he also posted two new introductory videos to his YouTube channel. There’s nothing overly technical here, but they’re nice short productions that introduce some of his work. (I wish more scientists did communication like this.) I’m hoping he’ll post them to his blog and write a bit more there in the future as well.

Cross-boundary Behavioural Reprogrammability Reveals Evidence of Pervasive Turing Universality by Jürgen Riedel, Hector Zenil
Preprint available at http://arxiv.org/abs/1510.01671

Ed.: 9/7/16: Updated videos with links to relevant literature

The world has certainly lost one of its greatest thinkers, and many of us have lost a dear friend, colleague, and mentor.

I was getting concerned that I hadn’t heard back from Sol for a while, particularly after emailing him late last week, and then I ran across this notice through ITSOC & the IEEE:

Solomon W. Golomb (May 30, 1932 – May 1, 2016)

Shannon Award winner and long-time ITSOC member Solomon W. Golomb passed away on May 1, 2016.
Solomon W. Golomb was the Andrew Viterbi Chair in Electrical Engineering at the University of Southern California (USC) and was at USC since 1963, rising to the rank of University and Distinguished Professor. He was a member of the National Academies of Engineering and Science, and was awarded the National Medal of Science, the Shannon Award, the Hamming Medal, and numerous other accolades. As USC Dean Yiannis C. Yortsos wrote, “With unparalleled scholarly contributions and distinction to the field of engineering and mathematics, Sol’s impact has been extraordinary, transformative and impossible to measure. His academic and scholarly work on the theory of communications built the pillars upon which our modern technological life rests.”

In addition to his many contributions to coding and information theory, Professor Golomb was one of the great innovators in recreational mathematics, contributing many articles to Scientific American and other publications. More recent Information Theory Society members may be most familiar with his mathematics puzzles that appeared in the Society Newsletter, which will publish a full remembrance later.

A quick search a moment later revealed this sad confirmation along with some great photos from an award Sol received just a week ago:

A sad day 4 @USC@USCViterbi@USCMingHsiehEE with the loss of beloved Sol Golomb. Was only last week we celebrated his Franklin medal.

As is common in academia, I’m sure it will take a few days for the news to drip out, but the world has certainly lost one of its greatest thinkers, and many of us have lost a dear friend, colleague, and mentor.

I’ll try touch base with his family and pass along what information sniff I can. I’ll post forthcoming obituaries as I see them, and will surely post some additional thoughts and reminiscences of my own in the coming days.