oh my gosh: how did I not know about this counting-out system called Yan-Tan...?!— Laura Gibbs (@OnlineCrsLady) November 15, 2019
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/NWfJgyicB6 pic.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.
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?
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.
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
- Hilbert’s Cube Lemma (1892)
- Schur (1916)
- Van der Waerden (1927)
- Sylvester’s Line Problem (partial coverage to be finished in the next lecture)
- Ramsey Theory
- Erdős (1943)
- Gallai (1944)
- Steinberg’s alternate (1944)
- DeBruijn and Erdős (1948)
- Motzkin (1951)
- Dirac (1951)
- Kelly & Moser (1958)
- Tao-Green Proof
- Homework 1 (homeworks are generally not graded)
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.
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.
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.
“Augmented cooking with machine intelligence”, with interesting remarks on generating food analogies… https://t.co/UluYk6p8TV
— michael_nielsen (@michael_nielsen) February 2, 2017
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  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  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.
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.
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.
If you’re not following him everywhere (?) yet, start with some of the sites below (or let me know if I’ve missed anything).
His most recent paper on arXiv:
Low Algorithmic Complexity Entropy-deceiving Graphs | .pdf
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]
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.
Universal Measures of Complexity
- A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity by Hector Zenil, Fernando Soler-Toscano, Narsis A. Kiani, Santiago Hernández-Orozco, Antonio Rueda-Toicen
- Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines by F. Soler-Toscano, H. Zenil, J.-P. Delahaye and N. Gauvrit; PLoS ONE 9(5): e96223, 2014.
- Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness by Jean-Paul Delahaye, Hector Zenil; Applied Mathematics and Computation 219, pp. 63-77, 2012.
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
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:
— Yannis C. Yortsos (@DeanYortsos) May 2, 2016
— Yannis C. Yortsos (@DeanYortsos) April 22, 2016
— Yannis C. Yortsos (@DeanYortsos) April 21, 2016
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.