The Universe of DiscourseThe Universe of Discourse (Mark Dominus Blog)tag:,2005:/mathBlosxomhttp://perl.plover.com/favicon.ico2017-12-22T16:32:00Ztag:,2017:/math/orthogonal-polygonsOrthogonal polygons2017-12-22T16:32:00Z2017-12-22T16:32:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>A couple of years ago I wrote here about some interesting projects I
had not finished. One of these was <a href="https://blog.plover.com/prog/unfinished-projects.html#orthopoly">to enumerate and draw orthogonal
polygons</a>.</p>
<p>An orthogonal polygon is simply one whose angles are all right
angles. All rectangles are orthogonal polygons, but there are many
other types. For example, here are examples
of orthogonal decagons:</p>
<p><img src="https://pic.blog.plover.com/math/orthogonal-polygons/a256456.png" alt="orthogonal decagons" /></p>
<p>If you ignore the lengths of the edges, and pay attention only to the
direction that the corners turn, the orthogonal polygons fall into
types. The rectangle is the only type with four sides. There is also
only one type with six sides; it is an L-shaped hexagon. There are
four types with eight sides, as shown in the illustration.</p>
<p>Contributing to <a href="https://oeis.org/">OEIS</a> was a life goal of mine and
I was thrilled when I was able to contribute <a href="https://oeis.org/A256456">the sequence of the
number of types of orthogonal <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242n%24">-gons</a>.</p>
<p>Enumerating the types is not hard. For <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242n%24">-gons, there is one type
for each unordered sequence of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%2d2%24"> numbers whose sum is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%2b2%24">.
In the illustration above, <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d5%24"> and each type is annotated with its
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%2d2%3d3%24"> numbers whose sum is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%2b2%3d7%24">. But the number of types
increases rapidly with the number of sides, and it soons becomes
infeasible to draw them by hand as I did above. I had wanted to write
a computer program that would take a description of a type (the
sequence) and render a drawing of one of the polygons of that type.</p>
<p>The tricky part is how to keep the edges from crossing, which is not
allowed. I had ideas for how to do this, but it seemed troublesome,
and also it seemed likely to produce ugly, lopsided examples, so I did
not implement it. And eventually I forgot about the problem.</p>
<p>But <a href="https://mathlesstraveled.com/">Brent Yorgey</a> did <em>not</em> forget,
and he had a completely different idea. He wrote a program to convert
a type description to a set of constraints on the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24y%24">
coordinates of the vertices, and fed the constraints to an <a href="https://en.wikipedia.org/wiki/Satisfiability_modulo_theories">SMT
solver</a>,
which is a system for finding solutions to general sets of
constraints. The outcome is as handsome as I could have hoped. Here
is M. Yorgey's program's version of the hand-drawn diagram above:</p>
<p align="center"><a href="https://pic.blog.plover.com/math/orthogonal-polygons/yorgey-decagons.png"><img border=0
src="https://pic.blog.plover.com/math/orthogonal-polygons/yorgey-decagons-th.png" /></a></p>
<p>M. Yorgey rendered beautiful pictures of all types of orthogonal
polygons up to 12 sides. <a href="https://mathlesstraveled.com/2017/12/18/post-without-words-21/">Check it out on his
blog</a>.</p>
tag:,2017:/math/ramsey-wasteWasteful and frugal proofs in Ramsey theory2017-12-15T17:09:00Z2017-12-15T17:09:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p><a href="https://math.stackexchange.com/questions/2567469/among-any-11-integers-sum-of-6-of-them-is-divisible-by-6">This math.se
question</a>
asks how to show that, among any 11 integers, one can find a subset of
exactly six that add up to a multiple of 6. Let's call this
“Ebrahimi’s theorem”.</p>
<p>This was the last thing I read before I put away my phone and closed
my eyes for the night, and it was a race to see if I would find an
answer before I fell asleep. Sleep won the race this time. But the
answer is not too hard.</p>
<ol>
<li><p>First, observe that among any five numbers there are three that sum
to a multiple of 3: Consider the remainders of the five numbers upon
division by 3. There are three possible remainders. If all three
remainders are represented, then the remainders are <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b0%2c1%2c2%5c%5c%7d%24">
and the sum of their representatives
is a multiple of 3. Otherwise there is some remainder with three
representatives, and the sum of these three is a multiple of 3.</p></li>
<li><p>Now take the 11 given numbers. Find a group of three whose sum is
a multiple of 3 and set them aside. From the remaining 8 numbers,
do this a second time. From the remaining 5 numbers, do it a third
time. </p></li>
<li><p>We now have three groups of three numbers that each sum to a
multiple of 3. Two of these sums must have the same parity. The
six numbers in those two groups have an even sum that is a multiple
of 3, and we win.</p></li>
</ol>
<p>Here is a randomly-generated example:</p>
<p>$$3\quad 17\quad 35\quad 42\quad 44\quad 58\quad 60\quad 69\quad
92\quad 97\quad 97$$</p>
<p>Looking at the first 5 numbers <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%5c%2017%5c%2035%5c%2042%5c%2044%24"> we see that on
division by 3 these have remainders <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%5c%202%5c%202%5c%200%5c%202%24">. The remainder
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%24"> is there three times, so we choose those three numbers <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle17%5c%2035%5c%0a44%5crangle%24">, whose sum is a multiple of 3, and set them aside.</p>
<p>Now we take the leftover <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%2442%24"> and supplement them with
three more unused numbers <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%2458%5c%2060%5c%2069%24">. The remainders are <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%240%5c%200%5c%201%5c%200%5c%0a0%24"> so we take <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle3%5c%2042%5c%2060%5crangle%24"> and set them aside as a second group.</p>
<p>Then we take the five remaining unused numbers <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%2458%5c%2069%5c%2092%5c%2097%5c%2097%24">.
The remainders are <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%5c%200%5c%202%5c%201%5c%201%24">.
The first three <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%2058%5c%2069%5c%2092%5crangle%24">have all different
remainders, so let's use those as our third group.</p>
<p>The three groups are now <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%0a%5clangle17%5c%2035%5c%2044%5crangle%2c%20%0a%5clangle3%5c%2042%5c%2060%5crangle%2c%20%0a%5clangle58%5c%2069%5c%2092%5crangle%24">. The first one has an even sum and the
second has an odd sum. The third group has an odd sum, which matches
the second group, so we choose the second and third groups, and that is
our answer:</p>
<p>$$3\qquad 42\qquad 60\qquad 58 \qquad 69 \qquad 92$$</p>
<p>The sum of these is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24324%20%3d%206%5ccdot%2054%24">.</p>
<p>This proves that 11 input numbers are sufficient to produce one output
set of 6 whose sum is a multiple of 6. Let's write <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%28n%2c%20k%29%24"> to
mean that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> inputs are enough to produce <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%24"> outputs. That is,
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%28n%2c%20k%29%24"> means “any set of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> numbers contains <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%24"> distinct
6-element subsets whose sum is a multiple of 6.” Ebrahimi’s theorem,
which we have just proved, states that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2811%2c%201%29%24"> is true, and
obviously it also proves <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%28n%2c%201%29%24"> for all larger <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">.</p>
<p>I would like to consider the following questions:</p>
<ol>
<li>Does this proof suffice to show that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2810%2c%201%29%24"> is false?</li>
<li>Does this proof suffice to show that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2811%2c%202%29%24"> is false?</li>
</ol>
<p>I am specifically <em>not</em> asking whether <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2810%2c%0a1%29%24"> or <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2811%2c%202%29%24"> are <em>actually</em> false. There are easy
counterexamples that can be found without reference to the proof
above. What I want to know is if the proof, as given, contains
nontrivial information about these questions.</p>
<p>The reason I think this is interesting is that I think, upon more
careful examination, that I will find that the proof above <em>does</em>
prove at least one of these, perhaps with a very small bit of
additional reasoning. But there are many similar proofs that do not
work this way. Here is a famous example. Let <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%28n%2c%20k%29%24"> be
shorthand for the following claim:</p>
<blockquote>
<p>Let the integers from 1 to <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> be partitioned into two sets. Then
one of the two sets contains <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%24"> distinct subsets of three
elements of the form <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7ba%2c%20a%2bd%2c%20a%2b2d%5c%5c%7d%24"> for integers <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2c%20d%24">.</p>
</blockquote>
<p>Then: </p>
<blockquote>
<p><a href="https://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem">Van der Waerden's theorem</a>:
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%28325%2c%201%29%24"> is true.</p>
</blockquote>
<p><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%28%29%24">, like <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%28%29%24">, is monotonic: van der Waerden's theorem
trivially implies <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%28n%2c%201%29%24"> for all <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> larger than 325. Does it
also imply that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%28n%2c%201%29%24"> is false for smaller <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">? No, not at
all; this is actually untrue. Does it also imply that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24W%28325%2c%20k%29%24">
is false for <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%3e1%24">? No, this is false also.</p>
<p>Van der Waerden's theorem takes 325 inputs (the integers) and among
them finds one output (the desired set of three). But this is
extravagantly wasteful. A better argument shows that only 9 inputs
were required for the same output, and once we know this it is trivial
that 325 inputs will always produce at least 36 outputs, and probably
a great many more.</p>
<p>Proofs of theorems in Ramsey theory are noted for being extravagant in
exactly this way. But the proof of Ebrahimi's theorem is different.
It is not only frugal, it is optimally so. It uses no more inputs
than are absolutely necessary.</p>
<p>What is different about these cases? What is the source the frugality
of the proof of Ebrahimi’s theorem? Is there a way that we can see
from examination of the proof that it will be optimally frugal?</p>
<p>Ebrahimi’s theorem shows <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2811%2c%201%29%24">. Suppose instead we want to
show <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%28n%2c%202%29%24"> for some <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">. From Ebrahimi’s theorem itself we
immediately get <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2822%2c%202%29%24"> and indeed <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2817%2c%202%29%24">. Is this the
best we can do? (That is, is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2816%2c%202%29%24"> false?) I bet it isn't.
If it isn't, what went wrong? Or rather, what went <em>right</em> in the
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%3d1%24"> case that stopped working when <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%3e1%24">?</p>
<p>I don't know.</p>
tag:,2017:/math/pettifoggeryMathematical pettifoggery and pathological examples2017-11-23T00:00:00Z2017-11-23T00:00:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p><a href="https://blog.plover.com/math/quibbling.html">Last week I said</a>:</p>
<blockquote>
<p>Mathematicians do tend to be the kind of people who quibble
and pettifog over the tiniest details. This is because in
mathematics, quibbling and pettifogging <em>does</em> work.</p>
</blockquote>
<p>This example is technical, but I think I can explain it in a way that
will make sense even for people who have no idea what the question is
about. Don't worry if you don't understand the next paragraph.</p>
<p style="float: right; margin-left: 2em;"><a href="https://pic.blog.plover.com/math/pettifoggery/Nigel_Tufnel.jpg"><img
src="https://pic.blog.plover.com/math/pettifoggery/Nigel_Tufnel-th.png" border=0/></a></p>
<p>In <a href="https://math.stackexchange.com/q/1133010/25554">this math SE question</a>:
a user asks for an example of a connected topological space <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%0aX%2c%20%5ctau%5crangle%24"> where there is a strictly finer topology <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%27%24">
for which <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20X%2c%20%5ctau%27%5crangle%24"> is disconnected. This is a very
easy problem if you go about it the right way, and the right way
follows a very typical pattern which is useful in many situations.</p>
<p>The pattern is “TURN IT UP TO 11!​!” In this case:</p>
<ol>
<li>Being disconnected means you can find some things with a certain
property.</li>
<li>If <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%27%24"> is finer than <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%24">, that means it has all the same
things, plus even more things of the same type.</li>
<li>If you could find those things in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%24">, you can still find
them in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%27%24"> because <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%27%24"> has everything that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%24"> does.</li>
<li>So although perhaps making <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%24"> finer could turn a connected
space into a disconnected one, by adding the things you needed, it definitely can't turn a
disconnected space into a connected one, because the things will
still be there.</li>
<li><p>So a way to look for a connected space that becomes disconnected when
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%24"> becomes finer is:</p>
<blockquote>
<p>Start with some connected space. Then make <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%24"> fine as you
possibly can and see if that is enough.</p>
</blockquote></li>
<li><p>If that works, you win. If not, you can look at the reason
it didn't work, and maybe either fix up the space you started with, or
else use that as the starting point in a proof that the thing
you're looking for doesn't exist.</p></li>
</ol>
<p>I emphasized the important point here. It is: Moving toward finer
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%24"> can't hurt the situation and might help, so the first thing
to try is to turn the fineness knob all the way up and see if that is
enough to get what you want. Many situations in mathematics call for
subtlety and delicate reasoning, but this is not one of those.</p>
<p>The technique here works perfectly. There is a topology <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau_d%24"> of
maximum possible fineness, called the “discrete” topology, so that is
the thing to try first. And indeed it answers the question as well as
it can be answered: If <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20X%2c%20%5ctau%5crangle%24"> is a connected
space, and if there is <em>any</em> refinement <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%27%24"> for which <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%0aX%2c%20%5ctau%27%5crangle%24"> is disconnected, then <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20X%2c%20%5ctau_d%5crangle%24">
will be disconnected. It doesn't even matter what connected space you
start with, because <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau_d%24"> is always a refinement of
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5ctau%24">, and because <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clangle%20X%2c%20%5ctau_d%5crangle%24"> is always
disconnected, except in trivial cases. (When <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24X%24"> has fewer than two
points.)</p>
<p>Right after you learn the definition of what a topology is, you are
presented with a bunch of examples. Some are typical examples, which
showcase what the idea is really about: the “open sets” of the real
line topologize the line, so that topology can be used as a tool for
studying real analysis. But some are atypical examples, which showcase
the extreme limits of the concept that are as different as possible
from the typical examples. The discrete space is one of these.
What's it for? It doesn't help with understanding the real numbers,
that's for sure. It's a tool, it's the knob on the topology machine
that turns the fineness all the way up.<a href="#fn1">[1]</a> If you want to prove that the
machine does something or other for the real numbers, one way is to
show that it <em>always</em> does that thing. And sometimes part of showing
that it <em>always</em> does that thing is to show that it does that even if
you turn the knob all the way to the right.</p>
<p>So often the first thing a mathematician will try is:</p>
<blockquote>
<p>What happens if I turn the knob all the way to the right? If <em>that</em>
doesn't blow up the machine, nothing will!</p>
</blockquote>
<p>And that's why, when you ask a mathematician a question, often the
first thing they will say is “ťhat fails when <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%3d0%24">” or “that fails
when all the numbers are equal” or “ťhat fails when one number is very
much bigger than the other” or “that fails when the space is discrete”
or “that fails when the space has fewer than two points.” <a href="#fn2">[2]</a></p>
<p>After the last article, Kyle Littler reminded me that I should not
forget the important word “pathological”. One of the important parts
of mathematical science is figuring out what the knobs are, how far
they can go, what happens if you turn them all the way up, and what
are the limits on how they can be set if we want the machine to behave
more or less like the thing we are trying to study.</p>
<p>We have this certain knob for how many dents and bumps and spikes we
can put on a sphere and have it still be a sphere, as long as we do
not actually puncture or tear the surface. And we expected that no
matter how far we turned this knob, the sphere would still divide
space into two parts, a bounded inside and an unbounded outside, and
that these regions should behave basically the same as they do when
the sphere is smooth.<a href="#fn3">[3]</a></p>
<p>But no, we are wrong, the knob goes farther than we thought. If we
turn it to the “<a href="https://en.wikipedia.org/wiki/Alexander_horned_sphere">Alexander horned
sphere</a>”
setting, smoke starts to come out of the machine and the red lights
begin to blink.<a href="#fn4">[4]</a> Useful! Now if someone has some theory about how the
machine will behave nicely if this and that knob are set properly, we
might be able to add the useful observation “actually you <em>also</em> have
to be careful not to turn that “dents bumps and spikes” knob too far.”</p>
<p>The word for these bizarre settings where some of the knobs are in the
extreme positions is “pathological”. The Alexander sphere is a
pathological embedding of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%5e2%24"> into <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cBbb%20R%5e3%24">.</p>
<hr>
<p><a name="fn1">[1]</a> The leftmost setting on that knob, with the
fineness turned all the way down, is called the “indiscrete topology”
or the “trivial topology”.</p>
<p><a name="fn2">[2]</a> If you claim that <em>any</em> connected space can be
disconnected by turning the “fineness” knob all the way to the right,
a mathematican will immediately turn the “number of points” knob all
the way to the left, and say “see, that only works for spaces with at
least two points”. In a space with fewer than two points, even the
discrete topology is connected.</p>
<p><a name="fn3">[3]</a>For example, if you tie your dog to a post
outside the sphere, and let it wander around, its leash cannot get
so tangled up with the sphere that you need to walk the dog backwards
to untangle it. You can just slip the leash off the sphere.</p>
<p><a name="fn4">[4]</a> The dog can get its leash so tangled around the
Alexander sphere that the only way to fix it is to untie the dog and
start over. But if the “number of dimensions” knob is set to 2
instead of to 3, you can turn the “dents bumps and spikes” knob as far
as you want and the leash can always be untangled without untying or
moving the dog. Isn't that interesting? That is called the <a
href="https://en.wikipedia.org/wiki/Jordan_curve_theorem">Jordan curve
theorem</a>.</p>
tag:,2017:/math/expectation-exampleAn instructive example of expected value2017-11-22T14:57:00Z2017-11-22T14:57:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>I think this example is very illuminating of something, although I'm
not sure yet what.</p>
<p>Suppose you are making a short journey somewhere. You leave two
minutes later than planned. How does this affect your expected
arrival time? All other things being equal, you should expect to
arrive two minutes later than planned. If you're walking or driving,
it will probably be pretty close to two minutes no matter what
happens.</p>
<p>Now suppose the major part of your journey involves a train that runs
every hour, and you don't know just what the schedule is. Now how
does your two minutes late departure affect your expected arrival
time?</p>
<p>The expected arrival time is <em>still</em> two minutes later than planned.
But it is not uniformly distributed. With probability <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7b58%7d%7b60%7d%24">,
you catch the train you planned to take. You are unaffected by your
late departure, and arrive at the same time.
But with probability <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7b2%7d%7b60%7d%24"> you miss that train and have to
take the next one, arriving an hour later than you planned. The
expected amount of lateness is</p>
<p>$$0 \text{ minutes}·\frac{58}{60} + 60 \text{ minutes}·\frac{2}{60} = 2 \text{ minutes}$$</p>
<p>the same as before.</p>
<p>[ Addendum: Richard Soderberg points out that one thing illuminated by
this example is that the mathematics fails to capture the emotional
pain of missing the train. Going in a slightly different direction, I
would add that the expected value reduces a complex situation to a
single number, and so must necessarily throw out a lot of important
information. <a href="https://blog.plover.com/risk.html">I discussed this here a while
back</a> in connection with lottery
tickets.</p>
<p>But also I think this failure of the expected value is also a benefit:
it <em>does</em> capture something interesting about the situation that might
not have been apparent before: Considering the two minutes as a time
investment, there is a sense in which the cost is knowable; it costs
exactly two minutes. Yes, there is a chance that you will be hit by a
truck that you would not have encountered had you left on time. But
this is <em>exactly</em> offset by the hypothetical truck that passed by
harmlessly two minutes before you arrived on the scene but which would
have hit you had you left on time. ]</p>
tag:,2017:/math/quibblingMathematical jargon for quibbling2017-11-20T16:03:00Z2017-11-20T16:03:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>Mathematicians tend not to be the kind of people who shout and pound
their fists on the table. This is because in mathematics, shouting
and pounding your fist <em>does not work</em>. If you do this, other
mathematicians will just laugh at you. Contrast this with law or
politics, which do attract the kind of people who shout and pound
their fists on the table.</p>
<p>However, mathematicians do tend to be the kind of people who quibble
and pettifog over the tiniest details. This is because in
mathematics, quibbling and pettifogging <em>does</em> work.</p>
<p>Mathematics has a whole subjargon for quibbling and pettifogging, and
also for excluding certain kinds of quibbles. The word “nontrivial”
is preeminent here. To a first approximation, it means “shut up and
stop quibbling”. For example, you will often hear mathematicians
having conversations like this one:</p>
<blockquote>
<p>A: Mihăilescu proved that the only solution of Catalan's equation
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5ex%20%2d%20b%5ey%20%3d%201%24"> is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%5e2%20%2d%202%5e3%24">.</p>
<p>B: What about when <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24"> are consecutive and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%3dy%3d1%24">?</p>
<p>A: The only <em>nontrivial</em> solution.</p>
<p>B: Okay.</p>
</blockquote>
<p>Notice that <em>A</em> does not explain what “nontrivial” is supposed to mean
here, and <em>B</em> does not ask. And if you were to ask either of them,
they might not be able to tell you right away what they meant. For
example, if you were to inquire specifically about <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%5e1%20%2d%201%5ey%24">,
they would both agree that that is also excluded, whether or not that
solution had occurred to either of them before. In this example,
“nontrivial” really does mean “stop quibbling”. Or perhaps more
precisely “there is actually something here of interest, and if you
stop quibbling you will learn what it is”.</p>
<p>In some contexts, “nontrivial” does have a precise and technical
meaning, and needs to be supplemented with other terms to cover other
types of quibbles. For example, when talking about subgroups,
“nontrivial” is supplemented with “proper”:</p>
<blockquote>
<p>If a nontrivial group has no proper nontrivial subgroup, then it is
a cyclic group of prime order.</p>
</blockquote>
<p>Here the “proper nontrivial” part is not merely to head off quibbling;
it's the crux of the theorem. But the first “nontrivial” is there to
shut off a certain type of quibble arising from the fact that 1 is not
considered a prime number. By this I mean if you omit “proper”, or
the second “nontrivial”, the statement is still true, but inane:</p>
<blockquote>
<p>If a nontrivial group has no subgroup, then it is a cyclic group of
prime order.</p>
</blockquote>
<p>(It is true, but vacuously so.) In contrast, if you omit the first
“nontrivial”, the theorem is substantively unchanged:</p>
<blockquote>
<p>If a group has no proper nontrivial subgroup, then it is a cyclic
group of prime order.</p>
</blockquote>
<p>This is still true, except in the case of the trivial group that is no
longer excluded from the premise. But if 1 were considered prime, it
would be true either way.</p>
<p>Looking at this issue more thoroughly would be interesting and might
lead to some interesting conclusions about mathematical methodology.</p>
<ul>
<li>Can these terms be taxonomized?</li>
<li>How do mathematical pejoratives relate? (“Abnormal, irregular, improper,
degenerate, inadmissible, and otherwise undesirable”) Kelley says we use these terms to refer to “a problem we cannot
handle”; that seems to be a different aspect of the whole story.</li>
<li>Where do they fit in Lakatos’
<a href="https://en.wikipedia.org/wiki/Proofs_and_Refutations"><em>Proofs and Refutations</em></a>
theory? Sometimes inserting “improper” just heads off a quibble. In
other cases, it points the way toward an expansion of understanding,
as with the “improper” polyhedra that violate Euler's theorem and
motivate the introduction of the Euler characteristic.</li>
<li>Compare with the large and finely-wrought jargon that
distinguishes between proofs that are “elementary”, “easy”, “trivial”,
“straightforward”, or “obvious”.</li>
<li>Is there a category-theoretic formulation of what it means when we
say “without loss of generality, take <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%5clt%20y%24">”?</li>
</ul>
<p>[ Addendum: Kyle Littler reminds me that I should not forget “pathological”. ]</p>
tag:,2017:/math/24-puzzle-baconDown with the negation sign!2017-11-15T15:15:00Z2017-11-15T15:15:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>[ Credit where it is due: This was entirely <a href="http://wry.me/~darius/">Darius Bacon's</a> idea. ]</p>
<p>In connection with <a href="https://blog.plover.com/testblog/math/24-puzzle-2.html">“Recognizing when two arithmetic expressions are
essentially the
same”</a>, I had
several conversations with people about ways to normalize numeric
expressions. In that article I observed that while everyone knows the
usual associative law for addition $$ (a + b) + c = a + (b + c)$$
nobody ever seems to mention the corresponding law for subtraction: $$
(a+b)-c = a + (b-c).$$</p>
<p>And while everyone
“knows” that subtraction is not associative because $$(a - b) - c ≠ a
- (b-c)$$ nobody ever seems to observe that there <em>is</em> an associative
law for subtraction: $$\begin{align} (a - b) + c & = a - (b - c)
\\ (a -b) -c & = a-(b+c).\end{align}$$</p>
<p>This asymmetry is kind of a nuisance, and suggests that a more
symmetric notation might be better. Darius Bacon suggested a simple
change that I think is an improvement:</p>
<blockquote>
<p>Write the negation of
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> as $$a\star$$ so that one has, for all <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">, $$a+a\star =
a\star + a = 0.$$</p>
</blockquote>
<p>The <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> operation obeys the following elegant and simple laws:
$$\begin{align}
a\star\star & = a \\
(a+b)\star & = a\star + b\star
\end{align}
$$</p>
<p>Once we adopt <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24">, we get a huge payoff: <em>We can eliminate
subtraction</em>:</p>
<blockquote>
<p>Instead of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2db%24"> we now write <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2bb%5cstar%24">.</p>
</blockquote>
<p>The negation of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2bb%5cstar%24"> is $$(a+b\star)\star = a\star + b{\star\star} = a\star +b.$$</p>
<p>We no longer have the annoying notational asymmetry between <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2db%24">
and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2db%20%2b%20a%24"> where the plus sign appears from nowhere. Instead, one
is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2bb%5cstar%24"> and the other is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%5cstar%2ba%24">, which is obviously just the
usual commutativity of addition.</p>
<p>The <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> is of course nothing but a synonym for multiplication by
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d1%24">. But it is a much less clumsy synonym. <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5cstar%24"> means
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5ccdot%28%2d1%29%24">, but with less inkjunk.</p>
<p>In conventional notation the parentheses in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%28%2db%29%24"> are essential
and if you lose them the whole thing is ruined. But because <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> is
just a special case of multiplication, it associates with
multiplication and division, so we don't have to worry about
parentheses in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%5cstar%29b%20%3d%20a%28b%5cstar%29%20%3d%20%28ab%29%5cstar%24">. They are all equal to just
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24ab%5cstar%24">. and you can drop the parentheses or include them or write the
terms in any order, just as you like, just as you would with <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24abc%24">.</p>
<p>The surprising associativity of subtraction is no longer surprising,
because $$(a + b) - c = a + (b - c)$$ is now written as $$(a + b) + c\star
= a + (b + c\star)$$ so it's just the usual associative law for addition;
it is not even disguised. The same happens for the reverse
associative laws for subtraction that nobody mentions; they
become variations on $$ \begin{align} (a + b\star) + c\star & = a + (b\star + c\star)
\\ & = a + (b+c)\star \end{align} $$ and such like.</p>
<p>The <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> is faster to read and faster to say. Instead of “minus one”
or “negative one” or “times negative one”, you just say “star”. </p>
<p>The <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> is just a number, and it behaves like a number. Its role
in an expression is the same as any other number's. It is just a
special, one-off notation for a single, particularly important number.</p>
<p>Open questions:</p>
<ol>
<li><p>Do we now need to replace the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cpm%24"> sign? If so,
what should we replace it with?</p></li>
<li><p>Maybe the idea is sound, but the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> itself is a bad choice. It
is slow to write. It will inevitably be confused with the <tt>*</tt> that
almost every programming language uses to denote multiplication.</p></li>
<li><p>The real problem here is that the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d%24"> symbol is overloaded.
Instead of changing the negation symbol to <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> and eliminating
the subtraction symbol, what if we just eliminated subtraction?
None of the new notation would be incompatible with the old
notation: <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d%28a%2b%2db%29%20%3d%20b%2b%2da%24"> still means exactly what it used to.
But you are no longer allowed to abbreviate it to <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d%28a%2db%29%20%3d%20b%2da%24">.</p>
<p>This would fix the problem of the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> taking too long to write:
we would just use <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d%24"> in its place. It would also fix the
concern of point 2: <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5cpm%20b%24"> now means <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2bb%24"> or <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2b%2db%24"> which
is not hard to remember or to understand. Another happy result:
notations like <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d1%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2d2%24"> do not change at all.</p></li>
</ol>
<!--
One thing you do have to be careful of is mixing <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> with
exponents. <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e%7bbc%7d%20%3d%20a%20%5e%7bcb%7d%24">, but <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e%7b%5cstar%20b%7d%20%5cne%20a%5e%7bb%5cstar%7d%24">.
For example, <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%5e%7b%5cstar%202%7d%20%3d%20a%5e2%24">. This makes me wonder if perhaps
the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cstar%24"> should be a subscript instead of a superscript.
((Making it not a subscript at all made this whole problem go away.))
-->
<p>Curious footnote: While I was writing up the draft of this article,
it had a reminder in it: “How did you and Darius come up with
this?” I went back to our email to look, and I discovered the answer
was:</p>
<ol>
<li>Darius suggested the idea to me.</li>
<li>I said, “Hey, that's a great idea!”</li>
</ol>
<p>I wish I could take more credit, but there it is. Hmm, maybe I will
take credit for inspiring Darius! That should be worth at least
fifty percent, perhaps more.</p>
<p>[ This article had some perinatal problems. It escaped early from the
laboratory, in a not-quite-finished state, so I apologize if you are
seeing it twice. ]</p>
tag:,2017:/math/PM-translationA modern translation of the 1+1=2 lemma2017-11-07T18:50:00Z2017-11-07T18:50:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p><a href="https://blog.plover.com/math/PM.html">A while back I blogged an explanation of the “<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%2b1%3d2%24">” lemma from
Whitehead and Russell's <em>Principia
Mathematica</em></a>:</p>
<p align=center><img src="https://pic.blog.plover.com/math/PM-translation/1+1=2.png"></p>
<p>W. Ethan Duckworth of the Department of Mathematics and Statistics at
Loyola University translated this into modern notation and has kindly
given me permission to publish it here:</p>
<p align=center><img src="https://pic.blog.plover.com/math/PM-translation/1+1=2-translation.png"></p>
<p>I think it is interesting and instructive to compare the two versions.
One thing to notice is that there is no perfect translation. As when
translating between two natural languages (German and English, say),
the meaning cannot be preserved exactly. Whitehead and Russell's
language is different from the modern language not only because the
notation is different but because the underlying concepts are
different. To really get what <em>Principia Mathematica</em> is saying you have to immerse
yourself in the <em>Principia Mathematica</em> model of the world.</p>
<p>The best example of this here is the symbol “1”. In the modern
translation, this means the number 1. But at this point in <em>Principia Mathematica</em>, the
number 1 has not yet been defined, and to use it here would be
circular, because proposition ∗54.43 is an important step on
the way to defining it. In <em>Principia Mathematica</em>, the symbol “1” represents the class of all
sets that contain exactly one element.<a href="#fn1">[1]</a> Following
<a href="https://quod.lib.umich.edu/cache/a/a/t/aat3201.0001.001/00000381.tif.20.pdf#page=5;zoom=75">the definition of ∗52.01</a>, in modern notation we would write
something like:</p>
<p>$$1 \equiv_{\text{def}} \{x \mid \exists y . x = \{ y \} \}$$</p>
<p>But in many modern universes, that of ZF set theory in particular,
there is no such object.<a href="#fn2">[2]</a> The situation in ZF is
even worse: the purported definition is meaningless, because the
comprehension is unrestricted.</p>
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<A HREF="http://www.powells.com/partner/29575/biblio/0521626064"><font size="-2">Order</font><br>
<cite><font>Principia Mathematica (through section 56)</font></cite><br>
<IMG SRC="http://covers.librarything.com/devkey/4e7443e59f586e9306d61bb521a11d8e/medium/isbn/0521626064" BORDER="0" ALIGN="center" ALT="Principia Mathematica (through section 56)" ><br>
<font size="-2">from Powell's</font></a>
</td></tr></table></div>
<p>The <em>Principia Mathematica</em> notation for <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%7cA%7c%24">, the cardinality of set <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">, is
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24Nc%5c%2c%e2%80%98A%24">, but again this is only an approximate translation. The
meaning of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24Nc%5c%2c%e2%80%98A%24"> is something close to</p>
<blockquote>
<p>the unique class <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%24"> such
that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%5cin%20C%24"> if and only if there exists a one-to-one relation
between <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24x%24">.</p>
</blockquote>
<p>(So for example one might assert that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24Nc%5c%2c%e2%80%98%5cLambda%20%3d%200%24">, and in
fact this is precisely what <a href="https://quod.lib.umich.edu/cache/a/a/t/aat3201.0002.001/00000041.tif.20.pdf#page=13;zoom=75">proposition ∗101.1</a> does assert.)
Even this doesn't quite capture the <em>Principia Mathematica</em> meaning, since the modern
conception of a relation is that it is a special kind of set, but in
<em>Principia Mathematica</em> relations and sets are different sorts of things. (We would also
use a one-to-one <em>function</em>, but here there is no <em>additional</em>
mismatch between the modern concept and the <em>Principia Mathematica</em> one.)</p>
<p>It is important, when reading old mathematics, to try to understand in
modern terms what is being talked about. But it is also dangerous to
forget that the ideas themselves are different, not just the
language.<a href="#fn3">[3]</a> I extract a lot of value from
switching back and forth between different historical views, and
comparing them. Some of this value is purely historiological. But
some is directly mathematical: looking at the same concepts from a
different viewpoint sometimes illuminates aspects I didn't fully
appreciate. And the different viewpoint I acquire is one that most
other people won't have.</p>
<p>One of my current low-priority projects is reading
<a href="https://en.wikipedia.org/wiki/William_Burnside">W. Burnside</a>'s
important 1897 book <a href="https://archive.org/details/in.ernet.dli.2015.168629"><em>Theory of Groups of Finite
Order</em></a>. The
value of this, for me, is not so much the group-theoretic content, but
in seeing how ideas about groups have evolved. I hope to write more
about this topic at some point.</p>
<hr />
<p><a name="fn1">[1]</a> Actually the situation in <em>Principia Mathematica</em> is more
complicated. There is a different class 1 defined at each type. But
the point still stands.</p>
<p><a name="fn2">[2]</a> In ZF, if <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%24"> were to exist as defined above,
the set <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b1%5c%5c%7d%24"> would exist also, and we would have <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5c%5c%7b1%5c%5c%7d%20%5cin%0a1%24"> which would contradict the axiom of foundation.</p>
<div class="bookbox"><table align=right width="14%" bgcolor="#ffffdd" border=1><tr><td align=center>
<A HREF="http://www.powells.com/partner/29575/biblio/9781107534056"><font size="-2">Order</font><br>
<cite><font>Proofs and Refutations</font></cite><br>
<IMG SRC="https://covers.powells.com/9781107534056.jpg" BORDER="0" ALIGN="center" ALT="Proofs and Refutations" ><br>
<font size="-2">from Powell's</font></a>
</td></tr></table></div>
<p><a name="fn3">[3]</a> This was a recurring topic of study for Imre
Lakatos, most famously in his little book <a href="https://math.berkeley.edu/~kpmann/Lakatos.pdf"><em>Proofs and
Refutations</em></a>. Also
important is his article “Cauchy and the continuum: the significance
of nonstandard analysis for the history and philosophy of
mathematics.” <cite>Math. Intelligencer</cite> <b>1</b> (1978), #3,
p.151–161, which <a href="https://blog.plover.com/math/Cauchy.html">I discussed here
earlier</a>, and which you can read in its entireity by paying the
excellent people at Elsevier the nominal and reasonable—nay,
trivial—sum of only US$39.95.</p>
tag:,2017:/math/logic/cut-ruleThe Blind Spot and the cut rule2017-10-31T20:08:00Z2017-10-31T20:08:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>[ The Atom and RSS feeds have done an unusually poor job of preserving
the mathematical symbols in this article. It will be much more
legible if you <a href="https://blog.plover.com/math/logic/cut-rule.html">read it on my
blog</a>. ]</p>
<p>Lately I've been enjoying <em>The Blind Spot</em> by <a href="https://en.wikipedia.org/wiki/Jean-Yves_Girard">Jean-Yves
Girard</a>, a very famous
logician. (It is translated from French; the original title is <em>Le Point
Aveugle</em>.) This is an unusual book. It is solidly full of deep
thought and technical detail about logic, but it is also opinionated,
idiosyncratic and polemical. Chapter 2 (“Incompleteness”) begins:</p>
<blockquote>
<p>It is out of question to enter into the technical arcana of Gödel’s
theorem, this for several reasons:</p>
<p>(i) This result, indeed very easy,
can be perceived, like the late paintings of Claude Monet, but from
a certain distance. A close look only reveals fastidious details
that one perhaps does not want to know.</p>
<p>(ii) There is no need either, since this theorem is a scientific
cul-de-sac : in fact it exposes a way without exit. Since it is
without exit, nothing to seek there, and it is of no use to be
expert in Gödel’s theorem.</p>
<p>(<em>The Blind Spot</em>, p. 29)</p>
</blockquote>
<p>He continues a little later:</p>
<blockquote>
<p>Rather than insisting on those tedious details which «hide the
forest», we shall spend time on objections, from the most ridiculous
to the less stupid (none of them being eventually respectable).</p>
</blockquote>
<p>As you can see, it is not written in the usual dry mathematical-text
style, presenting the material as a perfect and aseptic distillation
of absolute truth. Instead, one sees the history of logic, the rise
and fall of different theories over time, the interaction and relation
of many mathematical and philosophical ideas, and Girard's reflections
about it all. It is a transcription of a lecture series, and reads
like one, including all of the speaker's incidental remarks and
offhand musings, but written down so that each can be weighed and
pondered at length. Instead of wondering in the moment what he meant
by some intriguing remark, then having to abandon the thought to keep
up with the lecture, I can pause and ponder the significance. Girard
is really, really smart, and knows way more about logic than I ever
will, and his offhand remarks reward this pondering. The book is
<em>profound</em> in a way that mathematics books often aren't. I wanted to
provide an illustrative quotation, but to briefly excerpt a profound
thought is to destroy its profundity, so I will have to refrain.<a href="#fn1">[1]</a>)</p>
<p>The book really gets going with its discussion of Gentzen's
<a href="https://en.wikipedia.org/wiki/Sequent_calculus">sequent calculus</a> in
chapter 3.</p>
<!-- careful, this next definition spoils your ability to close HTML comments! -->
<p>Between around 1890 (when Peano and Frege began to liberate logic from its
medieval encrustations) and 1935 when the sequent calculus was
invented, logical proofs were mainly in the “Hilbert style”.
Typically there were some axioms, and some rules of deduction by which
the axioms could be transformed into other formulas. A typical
example consists of the axioms $$A\to(B\to A)\\
(A \to (B \to C)) \to ((A \to B) \to (A \to C)) $$
(where <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%2c%20B%2c%20C%24"> are understood to be placeholders that can be
replaced by any well-formed formulas) and the deduction rule <em>modus
ponens</em>: having proved <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%5cto%20B%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">, we can deduce <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24">.</p>
<p>In contrast, sequent calculus has few axioms and many deduction
rules. It deals with <em>sequents</em> which are claims of implication.
For example: $$p, q \vdash r, s$$ means that if
we can prove <em>all</em> of the formulas on the left of the ⊢ sign, then we can conclude
<em>some</em> of the formulas on the right. (Perhaps only one, but at least
one.)</p>
<p>A typical deductive rule in
sequent calculus is:</p>
<p>$$
\begin{array}{c}
Γ ⊢ A, Δ \qquad Γ ⊢ B, Δ \\ \hline
Γ ⊢ A ∧ B, Δ
\end{array}
$$</p>
<p>Here <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24"> represent any lists of formulas, possibly empty.
The premises of the rule are:</p>
<ol>
<li><p><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%20%e2%8a%a2%20A%2c%20%ce%94%24">: If we can prove <em>all</em> of the formulas in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%24">, then we can
conclude either the formula <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> or <em>some</em> of the formulas in
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24">.</p></li>
<li><p><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%20%e2%8a%a2%20B%2c%20%ce%94%24">: If we can prove <em>all</em> of the formulas in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%24">, then we can
conclude either the formula <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24"> or <em>some</em> of the formulas in
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24">.</p></li>
</ol>
<p>From these premises, the rule allows us to deduce:</p>
<blockquote>
<p><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%20%e2%8a%a2%20A%20%e2%88%a7%20B%2c%20%ce%94%24">: If we can prove <em>all</em> of the formulas in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%24">, then we can
conclude either the formula <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%20%5cland%20B%24"> or <em>some</em> of the formulas in
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24">.</p>
</blockquote>
<p>The only axioms of sequent calculus are utterly trivial:</p>
<p>$$
\begin{array}{c}
\phantom{A} \\ \hline
A ⊢ A
\end{array}
$$</p>
<p>There are no premises; we get this deduction for free: If can prove
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">, we can prove <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">. (<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> here is a metavariable that can be
replaced with any well-formed formula.)</p>
<p>One important point that Girard brings up, which I had never realized
despite long familiarity with sequent calculus, is the symmetry
between the left and right sides of the turnstile ⊢. As I mentioned,
the interpretation of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%20%e2%8a%a2%20%ce%94%24"> I had been taught was that it
means that if every formula in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%24"> is provable, then some formula in
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24"> is provable. But instead let's focus on just one of the
formulas <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> on the right-hand side, hiding in the list <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24">. The sequent
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%20%e2%8a%a2%20%ce%94%2c%20A%24"> can be understood to mean that to prove
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">, it suffices to prove
all of the formulas in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%24">, and to <em>disprove</em> all the formulas in
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24">. And now let's focus on just one of
the formulas on the left side: <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%2c%20A%20%e2%8a%a2%20%ce%94%24"> says that to
disprove <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">, it suffices to prove all the formulas in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%24"> and
disprove all the formulas in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24">.</p>
<p>The all-some correspondence, which had previously caused me to wonder
why it was that way and not something else, perhaps the other way
around, has turned into a simple relationship about logical negation:
the formulas on the left are positive, and the ones on the right are
negative.<a href="#fn2">[2]</a>) With this insight, the sequent calculus negation laws
become not merely simple but trivial:</p>
<p>$$
\begin{array}{cc}
\begin{array}{c}
Γ, A ⊢ Δ \\ \hline
Γ ⊢ \lnot A, Δ
\end{array}
& \qquad
\begin{array}{c}
Γ ⊢ A, Δ \\ \hline
Γ, \lnot A ⊢ Δ
\end{array}
\end{array}
$$</p>
<p>For example, in the right-hand deduction: what is sufficient to prove
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> is also sufficient to disprove <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%c2%acA%24">.</p>
<p>(Compare also the rule I showed above for ∧: It now says
that if proving everything in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%24"> and disproving everything in
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24"> is sufficient for proving <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">, and likewise
sufficient for proving <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24">, then it is also sufficient for proving
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%5cland%20B%24">.)</p>
<p>But none of that was what I planned to discuss; this article is
(intended to be) about sequent calculus's “cut rule”.</p>
<p>I never really appreciated the cut rule before. Most of the deductive
rules in the sequent calculus are intuitively plausible and so simple
and obvious that it is easy to imagine coming up with them oneself.</p>
<p>But the cut rule is more complicated than the rules I have already
shown. I don't think I would have thought of it easily:</p>
<p>$$
\begin{array}{c}
Γ ⊢ A, Δ \qquad Λ, A ⊢ Π \\ \hline
Γ, Λ ⊢ Δ, Π
\end{array}
$$</p>
<p>(Here <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> is a formula and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%2c%20%ce%94%2c%20%ce%9b%2c%20%ce%a0%24"> are lists of
formulas, possibly empty lists.)</p>
<p>Girard points out that the cut rule is a generalization of modus
ponens: taking <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%2c%20%ce%94%2c%20%ce%9b%24"> to be empty and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%a0%20%3d%20%5c%5c%7bB%5c%5c%7d%24">
we obtain:</p>
<p>$$
\begin{array}{c}
⊢ A \qquad A ⊢ B \\ \hline
⊢ B
\end{array}
$$</p>
<p>The cut rule is also a generalization of the transitivity of implication:</p>
<p>$$
\begin{array}{c}
X ⊢ A \qquad A ⊢ Y \\ \hline
X ⊢ Y
\end{array}
$$</p>
<p>Here we took <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%20%3d%20%5c%5c%7bX%5c%5c%7d%2c%20%ce%a0%20%3d%20%5c%5c%7bY%5c%5c%7d%24">, and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%94%24"> and
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%9b%24"> empty.</p>
<p>This all has given me a much better idea of where the cut rule came
from and why we have it.</p>
<p>In sequent calculus, the deduction rules all come in pairs. There is
a rule about introducing ∧, which I showed before. It allows us
to construct a sequent involving a formula with an ∧, where
perhaps we had no ∧ before. (In fact, it is the only way to do
this.) There is a corresponding rule (actually two rules) for
getting rid of ∧ when we have it and we don't want it:</p>
<p>$$
\begin{array}{cc}
\begin{array}{c}
Γ ⊢ A\land B, Δ \\ \hline
Γ ⊢ A, Δ
\end{array}
& \qquad
\begin{array}{c}
Γ ⊢ A\land B, Δ \\ \hline
Γ ⊢ B, Δ
\end{array}
\end{array}
$$</p>
<p>Similarly there is a rule (actually two rules) about introducing <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5clor%24"> and
a corresponding rule about eliminating it.</p>
<p>The cut rule seems to lie outside this classification. It is not
paired.</p>
<p>But Girard showed me that it <em>is</em> part of a pair. The axiom </p>
<p>$$
\begin{array}{c}
\phantom{A} \\ \hline
A ⊢ A
\end{array}
$$</p>
<p>can be seen as an introduction rule for a pair of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">s, one on each side
of the turnstile. The cut rule is the corresponding rule for
eliminating <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> from both sides. </p>
<p>Sequent calculus proofs are
much easier to construct than
Hilbert-style proofs.
Suppose one wants to prove <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24B%24">.
In a Hilbert system the only deduction rule is modus ponens, which requires that we first
prove <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%5cto%20B%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> for some <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">. But what <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> should we choose? It could be
anything, and we have no idea where to start or how big it could be.
(If you enjoy suffering, try to prove the simple theorem <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%5cto%20A%24"> in
the Hilbert system I described at the beginning of the
article. (<a href="https://pic.blog.plover.com/math/logic/cut-rule/hilbert-proof.txt">Solution</a>) </p>
<p>In sequent calculus, there is only one way to prove each kind of
thing, and the premises in each rule are simply related to the
consequent we want. Constructing the proof is mostly a matter of
pushing the symbols around by following the rules to their
conclusions. (Or, if this is impossible, one can conclude that there
is no proof, and why.<a href="#fn3">[3]</a>) Construction of
proofs can now be done entirely mechanically!</p>
<p>Except! The cut rule <em>does</em> require one to guess a formula: If one
wants to prove <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%2c%20%ce%9b%20%e2%8a%a2%20%ce%94%2c%20%ce%a0%24">, one must guess what
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24"> should appear in the premises <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%93%2c%20A%20%e2%8a%a2%20%ce%94%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%ce%9b%20%e2%8a%a2%20A%2c%0a%ce%a0%24">. And there is no constraint at all on <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24A%24">; it could be
anything, and we have no idea where to start or how big it could be.</p>
<p>The good news is that
<a href="https://en.wikipedia.org/wiki/Gerhard_Gentzen">Gentzen</a>, the inventor
of sequent calculus, showed that one can dispense with the cut rule:
it is unnecessary:</p>
<blockquote>
<p>In Hilbert-style systems, based on common sense, the only rule is
(more or less) the Modus Ponens : one reasons by linking together
lemmas and consequences. We just say that one can get rid of that :
it is like crossing the English Channel with fists and feet bound !</p>
<p>(<em>The Blind Spot</em>, p. 61)</p>
</blockquote>
<p>Gentzen's demonstration of this shows how one can take any proof that
involves the cut rule, and algorithmically eliminate the cut rule from
it to obtain a proof of the same result that does not use cut.
Gentzen called this the “Hauptsatz” (“principal theorem”) and rightly
so, because it reduces construction of logical proofs to an algorithm
and is therefore the ultimate basis for algorithmic proof theory.</p>
<p>The bad news is that the cut-elimination process can
super-exponentially increase the size of the proof, so it does not
lead to a <em>practical</em> algorithm for deciding provability. Girard
analyzed why, and what he discovered amazed me. The only problem is
in the contraction rules, which had seemed so trivial and
innocuous—uninteresting, even—that I had never given them any thought:</p>
<p>$$
\begin{array}{cc}
\begin{array}{c}
Γ, A, A ⊢ Δ \\ \hline
Γ, A ⊢ Δ
\end{array}
& \qquad
\begin{array}{c}
Γ ⊢ A, A, Δ \\ \hline
Γ ⊢ A, Δ
\end{array}
\end{array}
$$</p>
<p>And suddenly Girard's invention of <a href="https://en.wikipedia.org/wiki/Linear_logic">linear
logic</a> made sense to me.
In linear logic, contraction is forbidden; one must use each formula
in one and only one deduction.</p>
<p>Previously it had seemed to me that this was a pointless restriction.
Now I realized that it was no more of a useless hair shirt than the
intuitionistic rejection of the law of the proof by contradiction:
<a href="https://blog.plover.com/math/IL-contradiction.html">not a stubborn refusal to use an obvious tool of
reasoning</a>, but a
restriction of proofs to produce <em>better</em> reasoning. With the
rejection of contraction, cut-elimination no longer explodes
proof size, and automated theorem proving becomes practical:</p>
<blockquote>
<p>This is why its study is, implicitly, at the very heart of these
lectures.</p>
<p>(<em>The Blind Spot</em>, p. 63)</p>
</blockquote>
<p>The book is going to get into linear logic later in the next chapter.
I have read descriptions of linear logic before, but never understood
what it was up to. (It has two logical and operators, and two logical
or operators; why?) But I am sure Girard will explain it marvelously.</p>
<hr />
<ol>
<li><a name="fn1"></a> In place of a profound excerpt, I will present
the following, which isn't especially profound but struck a chord for
me: “By the way, nothing is more arbitrary than a
modal logic « I am done with this logic, may I have another one ? »
seems to be the <i>motto</i> of these guys.” (p. 24)
<li><a name="fn2"></a> Compare <a
href="https://blog.plover.com/math/24-puzzle-2.html">my alternative representation of
arithmetic expressions</a> that collapses addition and subtraction,
and multiplication and division.
<li><a name="fn3"></a> A typically Girardian remark is that analytic tableaux are “the poor man's sequents”.
</ol>
<hr />
<p><a href="https://news.ycombinator.com/item?id=14249733">A brief but interesting discussion of <em>The Blind Spot</em> on Hacker
News</a>.</p>
<p><a href="https://www.maa.org/press/maa-reviews/the-blind-spot-lectures-on-logic">Review by Felipe
Zaldivar</a>.</p>
tag:,2017:/math/increasing-sequences-2Counting increasing sequences with Burnside's lemma2017-10-15T23:09:00Z2017-10-15T23:09:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>[ I started this article in March and then forgot about it. Ooops! ]</p>
<p>Back in February I posted <a href="https://blog.plover.com/math/increasing-sequences.html">an article about how there are exactly 715
nondecreasing sequences of 4
digits</a>.
I said that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%2810%2c%204%29%24"> was the set of such sequences and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%2810%2c%0a4%29%24"> was the number of such sequences, and in general $$C(d,n) =
\binom{n+d-1}{d-1} = \binom{n+d-1}{n}$$ so in particular $$C(10,4) =
\binom{13}{4} = 715.$$</p>
<p>I described more than one method of seeing this, but I didn't mention
the method I had found first, which was to use the
<a href="https://en.wikipedia.org/wiki/Burnside%27s_lemma">Cauchy-Frobenius-Redfeld-Pólya-Burnside counting
lemma</a>.
<a href="https://blog.plover.com/math/polya-burnside.html">I explained
the lemma in detail</a> some time ago,
with beautiful illustrated examples, so I won't repeat the explanation
here. The Burnside lemma is a kind of big hammer to use here, but I
like big hammers. And the results of this application of the big
hammer are pretty good, and justify it in the end.</p>
<p>To count the number of distinct sequences of 4 digits, where some
sequences are considered “the same” we first identify a symmetry group
whose orbits are the equivalence classes of sequences. Here the
symmetry group is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S_4%24">, the group that permutes the elements of the
sequence, because two sequences are considered “the same” if they have
exactly the same digits but possibly in a different order, and the
elements of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S_4%24"> acting on the sequences are exactly what you want
to permute the elements into some different order.</p>
<p>Then you tabulate how many of the 10,000 original sequences are left
fixed by each element <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24p%24"> of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S_4%24">, which is exactly the number of
cycles of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24p%24">. (<a href="https://blog.plover.com/math/fixpoints.html">I have also discussed cycle classes of permutations
before</a>.) If <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24p%24"> contains <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24">
cycles, then <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24p%24"> leaves exactly <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%2410%5en%24"> of the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%2410%5e4%24"> sequences fixed.</p>
<p><table align=center cellspacing=0 cellpadding=6>
<tr bgcolor=pink><td align=center><span style="font-size: 120%;">Cycle class</span>
<td>Number<br>of cycles<td>How many<br>permutations?<td>Sequences<br>left fixed
<tr bgcolor="white"><td><img src="https://pic.blog.plover.com/math/increasing-sequences-2/fp4-1111.jpg"><td>4<td align=right>1
<td align=right>10,000
<tr bgcolor="#eee"><td bgcolor=""><img
src="https://pic.blog.plover.com/math/increasing-sequences-2/fp4-211.jpg"><td>3
<td align=right>6
<td align=right>1,000
<tr bgcolor="white"><td>
<img src="https://pic.blog.plover.com/math/increasing-sequences-2/fp4-22.jpg"><br>
<img src="https://pic.blog.plover.com/math/increasing-sequences-2/fp4-31.jpg">
<td>2
<td align=right>3 + 8 = 11
<td align=right>100
<tr bgcolor="#eee"><td><img
src="https://pic.blog.plover.com/math/increasing-sequences-2/fp4-4.jpg">
<td>1
<td align=right>6
<td align=right>10
<tr style="border: black medium solid;" bgcolor="pink"><td bgcolor="pink">
<td><td align=right><span style="font-size: 130%;">24</span>
<td align=right><span style="font-size: 130%;">17,160</span>
</table></p>
<p>(Skip this paragraph if you already understand the table. The
four rows above are an abbreviation of the full table, which has 24
rows, one for each of the 24 permutations of order 4. The “How many
permutations?” column says how many times each row should be
repeated. So for example the second row abbreviates 6 rows, one for
each of the 6 permutations with three cycles,
which each leave 1,000 sequences fixed, for a total of 6,000 in the
second row, and the total for all 24 rows is 17,160. There are two
different types of permutations that have two cycles, with 3 and 8
permutations respectively, and I have collapsed these into a single
row.)</p>
<p>Then the magic happens: We average the number left fixed by each
permutation and get <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7b17160%7d%7b24%7d%20%3d%20715%24"> which we already know
is the right answer.</p>
<p>Now suppose we knew how many permutations there were with each number
of cycles. Let's write
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cdef%5cst%231%232%7b%5cleft%5c%5b%7b%231%5catop%20%232%7d%5cright%5d%7d%5cst%20nk%24"> for the number of
permutations of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> things that have exactly <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%24"> cycles. For example, from
the table above we see that
$$\st 4 4 = 1,\quad
\st 4 3 = 6,\quad
\st 4 2 = 11,\quad
\st 4 1 = 6.$$</p>
<p>Then applying Burnside's lemma we can conclude
that $$C(d, n) = \frac1{n!}\sum_i \st ni d^i .\tag{$\spadesuit$}$$ So for example the table above
computes <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%2810%2c4%29%20%3d%20%5cfrac1%7b24%7d%5csum_i%20%5cst%204i%2010%5ei%20%3d%20715%24">.</p>
<p>At some point in looking into this I noticed that
$$\def\rp#1#2{#1^{\overline{#2}}}%
\def\fp#1#2{#1^{\underline{#2}}}%
C(d,n) =
\frac1{n!}\rp dn$$ where <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5crp%20dn%24"> is the so-called “<a href="https://en.wikipedia.org/wiki/Rising_power">rising
power</a>” of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%24">: $$\rp dn = d\cdot(d+1)(d+2)\cdots(d+n-1).$$
I don't think I had a proof of this; I just noticed that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%28d%2c%201%29%20%3d%0ad%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%28d%2c%202%29%20%3d%20%5cfrac12%28d%5e2%2bd%29%24"> (both obvious), and the Burnside's
lemma analysis of the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%3d4%24"> case had just given me <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%28d%2c%204%29%20%3d%0a%5cfrac1%7b24%7d%28d%5e4%20%2b6d%5e3%20%2b%2011d%5e2%20%2b%206d%29%24">. Even if one doesn't immediately
recognize this latter polynomial it looks like it ought to factor and
then on factoring it one gets <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%28d%2b1%29%28d%2b2%29%28d%2b3%29%24">. So it's easy to
conjecture <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%28d%2c%20n%29%20%3d%20%5cfrac1%7bn%21%7d%5crp%20dn%24"> and indeed, this is easy to
prove from <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%5cspadesuit%29%24">: The <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cst%20n%20k%24"> obey the recurrence
$$\st{n+1}k = n \st nk + \st n{k-1}\tag{$\color{green}{\star}$}$$ (by an easy combinatorial argument<a href="#fn1"><sup>1</sup></a>)
and it's also easy to show that the
coefficients of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5crp%20nk%24"> obey the same recurrence.<a href="#fn2"><sup>2</sup></a></p>
<p>In general <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5crp%20nk%20%3d%20%5cfp%7b%28n%2bk%2d1%29%7dk%24"> so we have
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%28d%2c%20n%29%20%3d%20%5crp%20dn%20%3d%20%5cfp%7b%28n%2bd%2d1%29%7dn%20%3d%0a%5cbinom%7bn%2bd%2d1%7dd%20%3d%20%5cbinom%7bn%2bd%2d1%7d%7bn%2d1%7d%24"> which ties the knot with the formula from <a href="https://blog.plover.com/math/increasing-sequences.html">the
previous article</a>. In particular, <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24C%2810%2c4%29%20%3d%20%5cbinom%7b13%7d9%24">.</p>
<!--
f529ff60ac6fe02d4c0b3d6cf368d93a
I forget where this went. I think the RHS turns into a double sum
and then we can exchange the order of summation but I don't remember
where we end up.
-->
<p>I have a bunch more to say about this but this article has already
been in the oven long enough, so I'll cut the scroll here.</p>
<hr>
<p><a name="fn1">[1]</a> The combinatorial argument that justifies
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%5ccolor%7bgreen%7d%7b%5cstar%7d%29%24"> is as follows:
The Stirling number <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cst%20nk%24"> counts the number of permutations of
order <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> with exactly <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%24"> cycles.
To get a permutation of order <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%2b1%24"> with exactly <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%24"> cycles, we
can take one of the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cst%20nk%24"> permutations of order <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> with <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%24">
cycles and insert the new element into one of the existing cycles
after any of the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%24"> elements. Or we can take on of the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cst%0an%7bk%2d1%7d%24"> permutations with only <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24k%2d1%24"> cycles and add the new element
in its own cycle.)</p>
<p><a name="fn2">[2]</a> We want to show that the coefficients of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5crp%0ank%24"> obey the same recurrence as
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%5ccolor%7bgreen%7d%7b%5cstar%7d%29%24">. Let's say that the coefficient of the
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%5ei%24"> term in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5crp%20nk%24"> is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c_i%24">.
We have $$\rp n{k+1} = \rp nk\cdot (n+k) = \rp
nk \cdot n + \rp nk \cdot k $$ so the
coefficient of the
the <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24n%5ei%24"> term on the left is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c_%7bi%2d1%7d%20%2b%20kc_i%24">.</p>
tag:,2017:/math/24-puzzle-3Miscellanea about 24 puzzles2017-08-28T03:36:00Z2017-08-28T03:36:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>This is a collection of leftover miscellanea about twenty-four
puzzles. In case you forgot what that is:</p>
<blockquote>
<p>The puzzle «4 6 7 9 ⇒ 24»
means that one should take the numbers 4, 6, 7, and 9, and combine
them with the usual arithmetic operations of addition, subtraction,
multiplication, and division, to make the number 24. In this case the
unique solution is $$6\times\frac{7 + 9}{4}.$$ When the target number is
24, as it often is, we omit it and just write «4 6 7 9».</p>
<p>Prior articles on this topic:</p>
<ul>
<li><a href="https://blog.plover.com/math/17-puzzle.html">A simple but difficult arithmetic puzzle</a> (July 2016)</li>
<li><a href="https://blog.plover.com/math/24-puzzle.html">Solving twenty-four puzzles</a> (March 2017)</li>
<li><a href="https://blog.plover.com/math/24-puzzle-2.html">Recognizing when two arithmetic expressions are essentially the same</a> (August 2017)</li>
</ul>
</blockquote>
<h2>How many puzzles have solutions?</h2>
<p>For each value of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24T%24">, there are 715 puzzles
«a b c d ⇒ T».
(I discussed this digression in two more earlier articles:
<a href="https://blog.plover.com/math/increasing-sequences.html">[1]</a>
<a href="https://blog.plover.com/math/increasing-sequences-2.html">[2]</a>.)
When the target <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24T%20%3d%2024%24">, 466 of the 715 puzzles have solutions. Is this
typical? Many solutions of
«a b c d»
puzzles end with a multiplication of 6 and 4, or of 8 and 3, or
sometimes of 12 and 2—so many that one quickly learns to look for
these types of solutions right away. When <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24T%3d23%24">, there won't be
any solutions of this type, and we might expect that relatively few
puzzles with prime targets have solutions.</p>
<p>This turns out to be the case:</p>
<p><img src="https://pic.blog.plover.com/math/24-puzzle-3/scatterplot.svg" alt="ALT attribute suggestions welcome!"/></p>
<p>The <em>x</em>-axis is the target number <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24T%24">, with 0 at the left, 300 at right,
and vertical guide lines every 25. The <em>y</em> axis is the number of
solvable puzzles out of the maximum possible of 715, with 0 at the
bottom, 715 at the top, and horizontal guide lines every 100.</p>
<p>Dots representing prime number targets are colored black. Dots for
numbers with two prime factors (4, 6, 9, 10, 14, 15, 21, 22, etc.) are red;
dots with three, four, five, six, and seven prime factors are orange,
yellow, green, blue, and purple respectively.</p>
<p>Two countervailing trends are obvious: Puzzles with smaller targets
have more solutions, and puzzles with highly-composite targets have
more solutions. No target number larger than 24 has as many as 466
solvable puzzles.</p>
<p>These are only trends, not hard rules. For example, there are 156
solvable puzzles with the target 126 (4 prime factors) but only 93
with target 128 (7 prime factors). Why? (I don't know. Maybe because
there is some correlation with the number of <em>different</em> prime
factors? But 72, 144, and 216 have many solutions, and only two
different prime factors.)</p>
<p>The smallest target you can't hit is 417. The following
numbers 418 and 419
are also impossible. But there are 8 sets
of four digits that can be used to make 416 and 23 sets
that can be used to make 420. The largest target that
can be hit is obviously <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%246561%20%3d%209%e2%81%b4%24">; the largest target with two
solutions is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242916%20%3d%204%c2%b79%c2%b79%c2%b79%20%3d%206%c2%b76%c2%b79%c2%b79%24">.</p>
<p><a href="https://pic.blog.plover.com/math/24-puzzle-3/number-of-solvable-puzzles.txt">(The raw data are available
here)</a>.</p>
<p>There is a lot more to discover here. For example, from looking at
the chart, it seems that the locally-best target numbers often have
the form <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%5en3%5em%24">. What would we see if we colored the dots
according to their largest prime factor instead of according to their
number of prime factors? (I tried doing this, and it didn't look like
much, but maybe it could have been done better.)</p>
<h3>Making zero</h3>
<p>As the chart shows, 705 of the 715 puzzles of the type «a b c d ⇒ 0»,
are solvable. This suggests an interesting inverse puzzle that Toph
and I enjoyed: find four digits <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2cb%2cc%2c%20d%24"> that <em>cannot</em> be used to
make zero. (<a href="https://pic.blog.plover.com/math/24-puzzle-3/SOLUTIONS-zeroes.txt">The answers</a>).</p>
<h2>Identifying interesting or difficult problems</h2>
<p><b>(Caution: this section contains spoilers for many of the most
interesting puzzles.)</b></p>
<p>I spent quite a while trying to get the computer to rank puzzles by
difficulty, with indifferent success.</p>
<h3>Fractions</h3>
<p>Seven puzzles require the use of fractions. One of these is the
notorious «3 3 8 8» that I mentioned before. This is probably the
single hardest of this type. The other six are:</p>
<pre><code> «1 3 4 6»
«1 4 5 6»
«1 5 5 5»
«1 6 6 8»
«3 3 7 7»
«4 4 7 7»
</code></pre>
<p>(<a href="https://pic.blog.plover.com/math/24-puzzle-3/solutions-fractions.png">Solutions to these (formatted image)</a>;
<a href="https://pic.blog.plover.com/math/24-puzzle-3/solutions-fractions.txt">solutions to these (plain text)</a>)</p>
<p>«1 5 5 5» is somewhat easier than the others, but they all follow
pretty much the same pattern. The last two are pleasantly
symmetrical.</p>
<!-- Also worth mentioning in this connection is the interesting
«1 6 9 9 ⇒ 18».
Unfortunately it has two solutions, and the other one is easy.
-->
<h3>Negative numbers</h3>
<p>No puzzles require the use of negative intermediate values. This
surprised me at first, but it is not hard to see why.
Subexpressions with negative intermediate values can always
be rewritten to have positive intermediate values instead.</p>
<p>For instance,
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%20%c3%97%20%289%20%2b%20%283%20%2d%204%29%29%24"> can be rewritten as
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%20%c3%97%20%289%20%2d%20%284%20%2d%203%29%29%24">
and
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%285%20%2d%208%29%c3%97%281%20%2d9%29%24">
can be rewritten as
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%288%20%2d%205%29%c3%97%289%20%2d1%29%24">.</p>
<h3>A digression about tree shapes</h3>
<p>In one of the earlier articles I asserted that there are only two
possible shapes for the expression trees of a puzzle solution:</p>
<p align="center"><table><tr>
<td align="center"><img src="https://pic.blog.plover.com/math/24-puzzle-3/tree1.png" alt="(((a # b) # c) # d)">
<td align="center"><img src="https://pic.blog.plover.com/math/24-puzzle-3/tree2.png" alt="((a # b) # (c # d))">
<tr><td align="center">Form <i>A</i> <td align="center">Form <i>B</i>
</table></p>
<p>(Pink square nodes contain operators and green round nodes contain
numbers.)</p>
<p>Lindsey Kuper pointed out that there are five possible shapes, not
two. Of course, I was aware of this (it is a Catalan number), so what
did I mean when I said there were only two? It's because I had the
idea that any tree that wasn't already in one of those two forms could
be put into form <em>A</em> by using transformations like the ones in the
previous section.</p>
<p>For example, the expression <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%284%c3%97%28%281%2b2%29%c3%b73%29%29%24"> isn't in either form,
but we can commute the × to get the equivalent <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%281%2b2%29%c3%b73%29%c3%974%24">, which
has form <em>A</em>. Sometimes one uses the associative laws, for example to
turn <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%c3%b7%20%28b%20%c3%97%20c%29%24"> into <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%20%c3%b7%20b%29%20%c3%b7%20c%24">.</p>
<p>But I was mistaken; not every expression can be put into either of
these forms. The expression <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%288%c3%97%289%2d%282%c2%b73%29%29%24"> is an example.</p>
<h3>Unusual intermediate values</h3>
<p>The most interesting thing I tried was to look for puzzles whose
solutions require unusual intermediate numbers.</p>
<p>For example, the puzzle «3 4 4 4» looks easy (the other puzzles
with just 3s and 4s are all pretty easy) but it is rather tricky
because its only solution goes through the unusual intermediate number
28: <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%20%283%20%2b%204%29%20%2d%204%24">.</p>
<p>I ranked puzzles as follows: each possible intermediate number appears in a
certain number of puzzle solutions; this is the score for that
intermediate number.
(Lower scores are better, because they represent rarer intermediate numbers.)
The score
for a single expression is the score of its rarest intermediate
value. So for example <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%20%283%20%2b%204%29%20%2d%204%24"> has the intermediate
values 7 and 28. 7 is extremely common, and 28 is quite unusual,
appearing in only 151 solution expressions, so <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%20%283%20%2b%204%29%20%2d%204%24">
receives a fairly low score of 151 because of the intermediate 28.</p>
<p>Then each puzzle received a difficulty
score which was the score of its <em>easiest</em> solution expression. For
example,
«2 2 3 8»
has two solutions, one (<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%288%2b3%29%c3%972%2b2%24">) involving the quite unusual
intermediate value 22, which has a very good score of only 79. But
this puzzle doesn't
count as difficult because it also admits the obvious solution
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%248%c2%b73%c2%b7%5cfrac22%24"> and this is the solution that gives it its extremely
bad score of 1768.</p>
<p>Under this ranking, the best-scoring twenty-four puzzles, and their
scores, were:</p>
<pre><code> «1 2 7 7» 3
* «4 4 7 7» 12
* «1 4 5 6» 13
* «3 3 7 7» 14
* «1 5 5 5» 15
«5 6 6 9» 23
«2 5 7 9» 24
«2 2 5 8» 25
«2 5 8 8» 45
«5 8 8 8» 45
«2 2 2 9» 47
* «1 3 4 6» 59
* «1 6 6 8» 59
«2 4 4 9» 151
«3 4 4 4» 151
* «3 3 8 8» 152
«6 8 8 9» 152
«2 2 2 7» 155
«2 2 5 7» 155
«2 3 7 7» 155
«2 4 7 7» 155
«2 5 5 7» 155
«2 5 7 7» 156
«4 4 8 9» 162
</code></pre>
<p>(Something is not quite right here. I think «2 5 7 7» and «2 5 5 7»
should have the same score, and I don't know why they don't. But I
don't care enough to do it over.)</p>
<p>Most of these are at least a little bit interesting. The seven
puzzles that require the use of fractions appear; I have marked them
with stars. The top item is «1 2 7 7», whose only solution goes
through the extremely rare intermediate number 49. The next items
require fractions, and the one after that is «5 6 6 9», which I found
difficult. So I think there's some
value in this procedure.</p>
<p>But is there enough value? I'm not sure. The last item on the list,
«4 4 8 9», goes through the unusual number 36. Nevertheless I don't
think it is a hard puzzle.</p>
<p>(I can also imagine that someone might see the answer to «5 6 6 9» right
off, but find «4 4 8 9» difficult. The whole exercise is subjective.)</p>
<h3>Solutions with unusual tree shapes</h3>
<p>I thought about looking for solutions that involved unusual sequences
of operations. Division is much less common than the other three
operations.</p>
<p>To get it right, one needs to normalize the form of expressions, so
that the shapes <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%20%2b%20b%29%20%2b%20%28c%20%2b%20d%29%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20%28b%20%2b%20%28c%20%2b%20d%29%29%24"> aren't
counted separately. The Ezpr library can help here. But I didn't go
that far because the preliminary results weren't encouraging.</p>
<p>There are very few expressions totaling 24 that have the form
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%c3%b7b%29%c3%b7%28c%c3%b7d%29%24">. But if someone gives you a puzzle with a solution in
that form, then <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%c3%97d%29%c3%b7%28b%c3%97c%29%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%c3%97d%29%20%c3%b7%20%28b%c3%b7c%29%24"> are also
solutions, and one or another is usually very easy to see. For
example, the puzzle «1 3 8 9» has the solution <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%288%c3%b71%29%c3%b7%283%c3%b79%29%24">,
which has an unusual form. But this is an <em>easy</em> puzzle; someone with
even a little experience will find the solution <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%248%20%c3%97%20%5cfrac93%20%c3%97%201%24">
immediately.</p>
<p>Similarly there are relatively few solutions of the form
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%c3%b7%28%28b%2dc%29%c3%b7d%29%24">, but they can all be transformed into
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%c3%97d%c3%b7%28b%2dc%29%24"> which is not usually hard to find. Consider
$$\frac 8{\left(\frac{6 - 4}6\right)}.$$ This is pretty
weird-looking, but when you're trying to solve it
one of the first things you might notice is the 8, and then you would
try to turn the rest of the digits into a 3 by solving
«4 6 6 ⇒ 3»,
at which point it wouldn't take long to think of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac6%7b6%2d4%7d%24">. Or, coming at
it from the other direction, you might see the sixes and start looking
for a way to make «4 6 8 ⇒ 4», and it wouldn't take long to think of
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac8%7b6%2d4%7d%24">. </p>
<h3>Ezpr shape</h3>
<p>Ezprs (<a href="https://blog.plover.com/math/24-puzzle-2.html">see previous article</a>)
correspond more closely than abstract syntax trees do with our
intuitive notion of how expressions ought to work, so looking at the
shape of the Ezpr version of a solution might give better results than
looking at the shape of the expression tree. For example, one might
look at the number of nodes in the Ezpr or the depth of the Ezpr.</p>
<h3>Ad-hockery</h3>
<p>When trying to solve one of these puzzles, there are a few things I
always try first. After adding up the four numbers, I then look for
ways to make <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%248%c2%b73%2c%206%c2%b74%2c%24"> or <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%2412%c2%b72%24">; if that doesn't work I start
branching out looking for something of the type <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24ab%5cpm%20c%24">.</p>
<p>Suppose we take a list of all solvable puzzles, and remove all the very
easy ones: the puzzles where one of the inputs is zero, or where one of
the inputs is 1 and there is a solution of the form <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%c3%971%24">.</p>
<p>Then take the remainder and mark them as “easy” if they have solutions of
the form <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2bb%2bc%2bd%2c%208%c2%b73%2c%206%c2%b74%2c%24"> or <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%2412%c2%b72%24">. Also eliminate puzzles
with solutions of the type <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%20%2b%20%28c%20%2d%20c%29%24"> or <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%c3%97%5cleft%28%5cfrac%0acc%5cright%29%24">.</p>
<p>How many are eliminated in this way? Perhaps most? The remaining
puzzles ought to have at least intermediate difficulty, and perhaps
examining just those will suggest a way to separate them further into
two or three ranks of difficulty.</p>
<h3>I give up</h3>
<p>But by this time I have solved so many twenty-four
puzzles that I am no longer sure which ones are hard and which ones
are easy. I suspect that I have seen and tried to solve most of the
466 solvable puzzles; certainly more than half. So my brain is no
longer a reliable gauge of which puzzles are hard and which are easy.</p>
<p>Perhaps looking at puzzles with five inputs would work better for me
now. These tend to be easy, because you have more to work with. But
there are 2002 puzzles and probably some of them are hard.</p>
<h2>Close, but no cigar</h2>
<p>What's the closest you can get to 24 without hitting it exactly? The
best I could do was <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%245%c2%b75%20%2d%20%5cfrac89%24">. Then I asked the computer,
which confirmed that this is optimal, although I felt foolish when I
saw the simpler solutions that are equally good: <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%c2%b74%20%5cpm%5cfrac%2019%24">.</p>
<p>The paired solutions
$$5 × \left(4 + \frac79\right) < 24 < 7 × \left(4 - \frac59\right)$$
are very handsome.</p>
<h2><a name="phoneapp">Phone app</a></h2>
<p>The search program that tells us when a puzzle has solutions is only
useful if we can take it with us in the car and ask it about license
plates. A phone app is wanted. <a href="https://studio.code.org/projects/applab/32u24dDEOBMCO1vGVVw1YA">I built one with <em>Code Studio</em></a>.</p>
<p><a href="https://studio.code.org/projects/public">Code Studio is great</a>. It has a nice web interface, and beginners can
write programs by dragging blocks around. It looks very much like <a href="https://scratch.mit.edu/">MIT's
<em>scratch</em> project</a>, which is much
better-known. But Code Studio is a much better tool than Scratch. In
Scratch, once you reach the limits of what it can do, you are stuck,
and there is no escape. In Code Studio when you drag around those
blocks you are actually
writing JavaScript underneath, and you can click a button and see and
edit the
underlying JavaScript code you have written.</p>
<p>Suppose you need to convert <code>A</code> to 1 and <code>B</code> to 2 and so on. Scratch
does not provide an <code>ord</code> function, so with Scratch you are pretty
much out of luck; your only choice is to write a 26-way if-else tree,
which means dragging around something like 104 stupid blocks. In Code
Studio, you can drop down the the JavaScript level and type in <code>ord</code>
to use the standard <code>ord</code> function. Then if you go back to blocks,
the <code>ord</code> will look like any other built-in function block.</p>
<p>In Scratch, if you want to use a data structure other than an array,
you are out of luck, because that is all there is. In Code Studio,
you can drop down to the JavaScript level and use or build any data
structure available in JavaScript.</p>
<p>In Scratch, if you want to
initialize the program with bulk data, say a precomputed table of the
solutions of the 466
twenty-four puzzles, you are out of luck. In Code Studio, you can
upload a CSV file with up to 1,000 records, which then becomes
available to your program as a data structure.</p>
<p>In summary, you spend a lot of your time in Scratch working around the
limitations of Scratch, and what you learn doing that is of very
limited applicability. Code Studio is real programming and if it
doesn't do exactly what you want out of the box, you can get what you
want by learning a little more JavaScript, which is likely to be
useful in other contexts for a long time to come.</p>
<p>Once you finish your Code Studio app, you can click a button to send
the URL to someone via SMS. They can follow the link in their phone's
web browser and then use the app.</p>
<p>Code Studio is what Scratch should have been. <a href="https://studio.code.org/projects/public">Check it out</a>.</p>
<h2>Thanks</h2>
<p>Thanks to everyone who contributed to this article, including:</p>
<ul>
<li>my daughters Toph and Katara</li>
<li>Shreevatsa R.</li>
<li>Dr. Lindsey Kuper</li>
<li>Darius Bacon</li>
<li>everyone else who emailed me</li>
</ul>
tag:,2017:/math/24-puzzle-2Recognizing when two arithmetic expressions are essentially the same2017-08-21T01:53:00Z2017-08-21T01:53:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>[ Warning: The math formatting in the RSS / Atom feed for this article is badly mutilated. I suggest you <a href="https://blog.plover.com/math/24-puzzle-2.html">read the article on my blog</a>. ]</p>
<blockquote>
<p>In this article, I discuss “twenty-four puzzles”. The puzzle «4 6 7 9 ⇒ 24»
means that one should take the numbers 4, 6, 7, and 9, and combine
them with the usual arithmetic operations of addition, subtraction,
multiplication, and division, to make the number 24. In this case the
unique solution is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%c2%b7%5cfrac%7b7%20%2b%209%7d%7b4%7d%24">.</p>
<p>When the target number after the <code>⇒</code> is 24, as it often is, we omit
it and just write «4 6 7 9». Every example in this article has
target number 24.</p>
<p>This is a continuation of my previous articles on this
topic:</p>
<ul>
<li><a href="https://blog.plover.com/math/17-puzzle.html">A simple but difficult arithmetic puzzle</a> (July 2016)</li>
<li><a href="https://blog.plover.com/math/24-puzzle.html">Solving twenty-four puzzles</a> (March 2017)</li>
</ul>
</blockquote>
<p>My first cut at writing a solver for twenty-four puzzles was a straightforward
search program. It had a couple of hacks in it to cut down the search
space by recognizing that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2bE%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24E%2ba%24"> are the same, but other
than that there was nothing special about it and
<a href="https://blog.plover.com/math/24-puzzle.html">I've discussed it before</a>.</p>
<p>It would quickly and accurately report whether any particular twenty-four
puzzle was solvable, but as it turned out that wasn't quite good
enough. The original motivation for the program was this: Toph and I
play this game in the car. Pennsylvania license plates have three
letters and four digits, and if we see a license plate <code>FBV 2259</code> we
try to solve «2 2 5 9». Sometimes we can't find a solution and
then we wonder: it is because there isn't one, or is it because we
just didn't get it yet? So the searcher turned into a phone app,
which would tell us whether there was solution, so we'd know whether
to give up or keep searching.</p>
<p>But this wasn't quite good enough either, because after we would find
that first solution, say <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%c2%b7%285%20%2b%209%20%2d%202%29%24">, we would wonder: are there
any more? And here the program was useless: it would
cheerfully report that there were three, so we would rack our brains
to find another, fail, ask the program to tell us the answer, and
discover to our disgust that the three solutions it had in mind were:</p>
<p>$$
2 \cdot (5 + (9 - 2)) \\
2 \cdot (9 + (5 - 2)) \\
2 \cdot ((5 + 9) - 2)
$$</p>
<p>The computer thinks these are different, because it uses different
data structures to represent them. It represents them with an abstract
syntax tree, which means that each expression is either a single
constant, or is a structure comprising an operator and its two operand
expressions—always exactly two. The computer understands the three
expressions above as having these structures:</p>
<table align=center style="margin: auto;"><tr>
<td><img style="max-width: 100%;" src="https://pic.blog.plover.com/math/24-puzzle-2/t2.svg">
<td><img style="max-width: 100%;" src="https://pic.blog.plover.com/math/24-puzzle-2/t3.svg">
<td><img style="max-width: 100%;" src="https://pic.blog.plover.com/math/24-puzzle-2/t1.svg">
</tr></table>
<p>It's not hard to imagine that the computer could be taught to
understand that the first two trees are equivalent. Getting it to
recognize that the third one is also equivalent seems somewhat more
difficult.</p>
<h2>Commutativity and associativity</h2>
<p>I would like the computer to understand that these three expressions
should be considered “the same”. But what does “the same” mean? This
problem is of a kind I particularly like: we want the computer to do
<em>something</em>, but we're not exactly sure what that something is. Some
questions are easy to ask but hard to answer, but this is the
opposite: the real problem is to decide what question we want to ask.
Fun!</p>
<p>Certainly some of the question should involve commutativity and
associativity of addition and multiplication. If the only difference
between two expressions is that one has <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20b%24"> where the other has
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%20%2b%20a%24">, they should be considered the same; similarly <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20%28b%20%2b%0ac%29%24"> is the same expression as <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%20%2b%20b%29%20%2b%20c%24"> and as <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28b%20%2b%20a%29%20%2b%20c%24">
and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%20%2b%20%28a%20%2b%20c%29%24"> and so forth.</p>
<p>The «2 2 5 9» example above shows that commutativity and
associativity are not limited to addition and multiplication. There
are commutative and associative properties of subtraction also! For example,
$$a+(b-c) = (a+b)-c$$ and $$(a+b)-c = (a-c)+b.$$
There ought to be names for these laws but as far as I know there aren't. (Sure, it's
just commutativity and associativity of addition in disguise, but
nobody explaining these laws to school kids <em>ever</em> seems to point out
that subtraction can enter into it. They just observe that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%2db%29%2dc%0a%e2%89%a0%20a%2d%28b%2dc%29%24">, say “subtraction isn't associative”, and leave it at that.)</p>
<p>Closely related to these identities are operator inversion identities
like <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2d%28b%2bc%29%20%3d%20%28a%2db%29%2dc%24">, <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2d%28b%2dc%29%20%3d%20%28a%2db%29%2bc%24">, and their
multiplicative analogues. I don't know names for these algebraic laws
either.</p>
<p>One way to deal with all of this would to build a complicated
comparison function for abstract syntax trees that tried to transform
one tree into another by applying these identities. A better approach
is to recognize that the data structure is over-specified. If we want
the computer to understand that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%20%2b%20b%29%20%2b%20c%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20%28b%20%2b%20c%29%24">
are the same expression, we are swimming upstream by using a data
structure that was specifically designed to capture the difference
between these expressions.</p>
<p>Instead, I invented a data structure, called an <em>Ezpr</em> (“Ez-pur”), that
can represent expressions, but in a somewhat more natural way than
abstract syntax trees do, and in a way that makes commutativity and
associativity transparent. </p>
<p>An Ezpr has a simplest form, called its “canonical” or “normal” form.
Two Ezprs represent essentially the same mathematical expression if
they have the same canonical form. To decide if two abstract syntax
trees are the same, the computer converts them to Ezprs, simplifies
them, and checks to see if resulting canonical forms are identical.</p>
<h2>The Ezpr</h2>
<p>Since associativity doesn't matter, we don't want to represent it.
When we (humans) think about adding up a long column of numbers, we
don't think about associativity because we don't add them
pairwise. Instead we use an addition algorithm that adds them all at
once in a big pile. We don't treat addition as a binary operation; we
normally treat it as an operator that adds up the numbers in a list.
The Ezpr makes this explicit: its addition operator is applied to a
list of subexpressions, not to a pair. Both <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20%28b%20%2b%20c%29%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%0a%2b%20b%29%20%2b%20c%24"> are represented as the Ezpr</p>
<pre><code> SUM [ a b c - ]
</code></pre>
<p>which just says that we are adding up <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">, <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24">, and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c%24">. (The
<code>-</code> sign is just punctuation; ignore it for now.)</p>
<p>Similarly the Ezpr <code>MUL [ a b c ÷ ]</code> represents the product of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">,
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24">, and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c%24">. (Please ignore the <code>÷</code> sign for the time being.)</p>
<p>To handle commutativity, we want those <code>[ a b c ]</code> lists to be bags.
Perl doesn't have a built-in bag object, so instead I used arrays and
required that the array elements be in sorted order. (Exactly <em>which</em>
sorted order doesn't really matter.)</p>
<h2>Subtraction and division</h2>
<p>This doesn't yet handle subtraction and division, and the way I chose
to handle them is the only part of this that I think is at all
clever. A <code>SUM</code> object has not one but two bags, one for the positive
and one for the negative part of the expression. An expression like
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2d%20b%20%2b%20c%20%2d%20d%24"> is represented by the Ezpr:</p>
<pre><code>SUM [ a c - b d ]
</code></pre>
<p>and this is <em>also</em> the representation of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20c%20%2d%20b%20%2d%20d%24">, of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c%20%2b%20a%0a%2d%20d%20%2d%20b%24">, of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c%20%2d%20d%2b%20a%2db%24">, and of any other expression of the
idea that we are adding up <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c%24"> and then deducting <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%24">
and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24d%24">. The <code>-</code> sign separates the terms that are added from those
that are subtracted. </p>
<p>Either of the two bags may be empty, so for example <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20b%24"> is just
<code>SUM [ a b - ]</code>.</p>
<p>Division is handled similarly. Here conventional mathematical
notation does a little bit better than in the sum case: <code>MUL [ a c ÷ b
d ]</code> is usually written as <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7bac%7d%7bbd%7d%24">.</p>
<p>Ezprs handle the associativity and commutativity of subtraction and
division quite well. I pointed out earlier that subtraction has an
associative law <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%20%2b%20b%29%20%2d%20c%20%3d%20a%20%2b%0a%28b%20%2d%20c%29%24"> even though it's not usually called that.
No code is required to understand that those two expressions are
equal if they are represented as Ezprs, because they are represented
by completely identical structures:</p>
<pre><code> SUM [ a b - c ]
</code></pre>
<p>Similarly there is a commutative law for subtraction: <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20b%20%2d%20c%20%3d%20a%0a%2d%20c%20%2b%20b%24"> and once again that same Ezpr does for both.</p>
<h2>Ezpr laws</h2>
<p>Ezprs are more flexible than binary trees. A binary tree can
represent the expressions <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28a%2bb%29%2bc%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2b%28b%2bc%29%24"> but not the
expression <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2bb%2bc%24">. Ezprs can represent all three and it's easy to
transform between them. Just as there are rules for building
expressions out of simpler expressions, there are a few rules for
combining and manipulating Ezprs.</p>
<h3>Lifting and flattening</h3>
<p>The most important transformation is <em>lifting</em>, which is the Ezpr
version of the associative law. In the canonical form of an Ezpr, a
<code>SUM</code> node may not have subexpressions that are also <code>SUM</code> nodes. If
you have</p>
<pre><code> SUM [ a SUM [ b c - ] - … ]
</code></pre>
<p>you should lift the terms from the inner sum into the outer one:</p>
<pre><code> SUM [ a b c - … ]
</code></pre>
<p>effectively transforming <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2b%28b%2bc%29%24"> into <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%2bb%2bc%24">. More generally,
in</p>
<pre><code> SUM [ a SUM [ b - c ]
- d SUM [ e - f ] ]
</code></pre>
<p>we lift the terms from the inner Ezprs into the outer one:</p>
<pre><code> SUM [ a b f - c d e ]
</code></pre>
<p>This effectively transforms <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20%28b%20%2d%20c%29%20%2d%20d%20%2d%20%28e%20%2d%20f%29%29%24"> to <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%20%2b%20b%20%2b%0af%20%2d%20c%20%2d%20d%20%2d%20e%24">.</p>
<p>Similarly, when a <code>MUL</code> node contains another <code>MUL</code>, we can flatten
the structure.</p>
<p>Say we are converting the expression <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%247%20%c3%b7%20%283%20%c3%b7%20%286%20%c3%97%204%29%29%24"> to an Ezpr.
The conversion function is recursive and the naïve version computes
this Ezpr:</p>
<pre><code> MUL [ 7 ÷ MUL [ 3 ÷ MUL [ 6 4 ÷ ] ] ]
</code></pre>
<p>But then at the bottom level we have a <code>MUL</code> inside a <code>MUL</code>, so the
4 and 6 in the innermost <code>MUL</code> are lifted upward:</p>
<pre><code> MUL [ 7 ÷ MUL [ 3 ÷ 6 4 ] ]
</code></pre>
<p>which represents <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac7%7b%5cfrac%7b3%7d%7b6%5ccdot%204%7d%7d%24">.
Then again we have a <code>MUL</code> inside a <code>MUL</code>, and again the
subexpressions of the innermost <code>MUL</code> can be lifted:</p>
<pre><code> MUL [ 7 6 4 ÷ 3 ]
</code></pre>
<p>which we can imagine as <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%7b7%c2%b76%c2%b74%7d3%24">.</p>
<p>The lifting only occurs when the sub-node has the same type as its
parent; we may not lift terms out of a <code>MUL</code> into a <code>SUM</code> or vice
versa.</p>
<h3>Trivial nodes</h3>
<p>The Ezpr <code>SUM [ a - ]</code> says we are adding up just one thing, <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">,
and so it can be eliminated and replaced with just <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24">. Similarly
<code>SUM [ - a ]</code> can be replaced with the constant <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%2da%24">, if <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24a%24"> is a
constant. <code>MUL</code> can be handled similarly.</p>
<p>An even simpler case is <code>SUM [ - ]</code> which can be replaced by the
constant 0; <code>MUL [ ÷ ]</code> can be replaced with 1. These sometimes arise
as a result of cancellation.</p>
<h3>Cancellation</h3>
<p>Consider the puzzle «3 3 4 6».
My first solver found 49 solutions to this puzzle. One is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%283%20%2d%203%29%20%2b%20%284%20%c3%97%206%29%24">.
Another is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%284%20%2b%20%283%20%2d%203%29%29%20%c3%97%206%24">. A third is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%20%286%20%2b%20%283%20%2d%203%29%29%24">.</p>
<p>I think these are all the same: the solution is to multiply the 4 by
the 6, and to get rid of the threes by subtracting them to make a zero
term. The zero term can be added onto the rest of expression or to
any of its subexpressions—there are ten ways to do this—and it doesn't
really matter where.</p>
<p>This is easily explained in terms of Ezprs:
If the same subexpression appears in both of a node's bags,
we can drop it. For example,
the expression <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%284%20%2b%20%283%20%2d3%29%29%20%c3%97%206%24">
starts out as</p>
<pre><code> MUL [ 6 SUM [ 3 4 - 3 ] ÷ ]
</code></pre>
<p>but the duplicate threes in <code>SUM [ 3 4 - 3 ]</code> can be canceled, to
leave</p>
<pre><code> MUL [ 6 SUM [ 4 - ] ÷ ]
</code></pre>
<p>The sum is now trivial, as described in the previous section, so can
be eliminated and replaced with just 4:</p>
<pre><code> MUL [ 6 4 ÷ ]
</code></pre>
<p>This Ezpr records the essential feature of each of the three solutions to
«3 3 4 6» that I mentioned:
they all are multiplying the 6 by the 4, and then doing something else
unimportant to get rid of the threes.</p>
<p>Another solution to the same puzzle is <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%286%20%c3%b7%203%29%20%c3%97%20%284%20%c3%97%203%29%24">.
Mathematically we would write this as <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac63%c2%b74%c2%b73%24"> and we can see
this is just <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%246%c3%974%24"> again, with the threes gotten rid of by
multiplication and division, instead of by addition and subtraction.
When converted to an Ezpr, this expression becomes:</p>
<pre><code> MUL [ 6 4 3 ÷ 3 ]
</code></pre>
<p>and the matching threes in the two bags are cancelled, again leaving</p>
<pre><code> MUL [ 6 4 ÷ ]
</code></pre>
<p>In fact there aren't 49 solutions to this puzzle. There is only one,
with <a href="https://pic.blog.plover.com/math/24-puzzle-2/3346-solutions.txt">49 trivial variations</a>.</p>
<h3>Identity elements</h3>
<p>In the preceding example, many of the trivial variations on the
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%c3%976%24"> solution involved multiplying some subexpression by <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%0a33%24">. When one of the input numbers in the puzzle is a 1, one can
similarly obtain a lot of useless variations by choosing where to
multiply the 1.</p>
<p>Consider
«1 3 3 5»:
We can make 24 from <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%20%c3%97%20%283%20%2b%205%29%24">. We then have to get
rid of the 1, but we can do that by multiplying it onto any
of the five subexpressions of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%20%c3%97%20%283%20%2b%205%29%24">:</p>
<p>$$
1 × (3 × (3 + 5)) \\
(1 × 3) × (3 + 5) \\
3 × (1 × (3 + 5)) \\
3 × ((1 × 3) + 5) \\
3 × (3 + (1×5))
$$</p>
<p>These should not be considered different solutions.
Whenever we see any 1's in either of the bags of a <code>MUL</code> node,
we should eliminate them.
The first expression above, <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%241%20%c3%97%20%283%20%c3%97%20%283%20%2b%205%29%29%24">, is converted to the Ezpr</p>
<pre><code> MUL [ 1 3 SUM [ 3 5 - ] ÷ ]
</code></pre>
<p>but then the 1 is eliminated from the <code>MUL</code> node leaving</p>
<pre><code> MUL [ 3 SUM [ 3 5 - ] :- ]
</code></pre>
<p>The fourth expression,
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%20%c3%97%20%28%281%20%c3%97%203%29%20%2b%205%29%24">,
is initially converted to the Ezpr</p>
<pre><code> MUL [ 3 SUM [ 5 MUL [ 1 3 ÷ ] - ] ÷ ]
</code></pre>
<p>When the 1 is eliminated from the inner <code>MUL</code>, this leaves a trivial
<code>MUL [ 3 ÷ ]</code> which is then replaced with just 3, leaving:</p>
<pre><code> MUL [ 3 SUM [ 5 3 - ] ÷ ]
</code></pre>
<p>which is the same Ezpr as before.</p>
<p>Zero terms in the bags of a <code>SUM</code> node can similarly be dropped.</p>
<h3>Multiplication by zero</h3>
<p>One final case is that <code>MUL [ 0 … ÷ … ]</code> can just be simplified to 0.</p>
<p>The question about what to do when there is a zero in the denominator
is a bit of a puzzle.
In the presence of division by zero, some of our simplification rules
are questionable. For example, when we have <code>MUL [ a ÷ MUL [ b ÷ c ]
]</code>, the lifting rule says we can simplify this to <code>MUL [ a c ÷ b
]</code>—that is, that <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5cfrac%20a%7b%5cfrac%20bc%7d%20%3d%20%5cfrac%7bac%7db%24">. This is correct,
except that when <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24b%3d0%24"> or <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24c%3d0%24"> it may be nonsense, depending on what else is
going on. But since zero denominators never arise in the solution of
these puzzles, there is no issue in this application.</p>
<h2>Results</h2>
<p>The <code>Ezpr</code> module is around 200 lines of Perl code, including
everything: the function that converts abstract syntax trees to Ezprs,
functions to convert Ezprs to various notations (both <code>MUL [ 4 ÷ SUM [
3 - 2 ] ]</code> and <code>4 ÷ (3 - 2)</code>), and the two versions of the
normalization process described in the previous section. The
normalizer itself is about 35 lines.</p>
<p>Associativity is taken care of by the Ezpr structure itself, and
commutativity is not too difficult; as I mentioned, it would have been
trivial if Perl had a built-in bag structure. I find it much easier
to reason about transformations of Ezprs than abstract syntax trees.
Many operations are much simpler; for example the negation of
<code>SUM [ A - B ]</code> is simply <code>SUM [ B - A ]</code>. Pretty-printing is also easier
because the Ezpr better captures the way we write and think about
expressions.</p>
<p>It took me a while to get the normalization tuned properly, but the
results have been quite successful, at least for this problem domain.
The current puzzle-solving program reports the number of distinct
solutions to each puzzle. When it reports two different solutions,
they are really different; when it fails to support the exact solution
that Toph or I found, it reports one essentially the same. (There are
some small exceptions, <a href="#arguable">which I will discuss below</a>.)</p>
<p>Since there is no specification for “essentially the same” there is no
hope of automated testing. But we have been using the app for several
months looking for mistakes, and we have not found any.
If the normalizer failed to recognize that two expressions were
essentially similar, we would be very likely to notice: we would be
solving some puzzle, be unable to find the last of the solutions that
the program claimed to exist, and then when we gave up and saw what it was we
would realize that it was essentially the same as one of the solutions we
had found. I am pretty confident that there are no errors of this
type, but see <a href="#arguable">“Arguable points”</a> below. </p>
<p>A harder error to detect is whether the computer has erroneously
conflated two essentially dissimilar expressions. To detect this we
would have to notice that an expression was missing from the computer's solution list. I am
less confident that nothing like this has occurred, but as the months
have gone by I feel better and better about it.</p>
<p>I consider the problem of “how many solutions does this puzzle
<em>really</em> have to have?” been satisfactorily solved. There are some
edge cases, but I think we have identified them.</p>
<p><a href="https://github.com/mjdominus/24-puzzle-solver">Code for my solver is on
Github</a>. The Ezpr code
is in <a href="https://github.com/mjdominus/24-puzzle-solver/blob/master/Expr.pm">the <code>Ezpr</code> package in the <code>Expr.pm</code>
file</a>.
This code is all in the public domain.</p>
<h3>Some examples</h3>
<p>The original program claims to find 35 different solutions to «4 6 6
6». The revised program recognizes that these are of only two types:</p>
<table align=center>
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%206%20%c3%97%206%20%c3%b7%206%24"><td><tt>MUL [ 4 6 - ]</tt>
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%286%20%2d%204%29%20%c3%97%20%286%20%2b%206%29%24"><td><tt>MUL [ SUM [ 6 - 4 ] SUM [ 6 6 - ] ÷ ]
</table>
<p>Some of the variant forms of the first of those include:</p>
<p>$$
6 × (4 + (6 - 6)) \\
6 + ((4 × 6) - 6) \\
(6 - 6) + (4 × 6) \\
(6 ÷ 6) × (4 × 6) \\
6 ÷ ((6 ÷ 4) ÷ 6) \\
6 ÷ (6 ÷ (4 × 6)) \\
6 × (6 × (4 ÷ 6)) \\
(6 × 6) ÷ (6 ÷ 4) \\
6 ÷ ((6 ÷ 6) ÷ 4) \\
6 × (6 - (6 - 4)) \\
6 × (6 ÷ (6 ÷ 4)) \\
\ldots <br />
$$</p>
<p>In an even more extreme case, the original program finds 80 distinct
expressions that solve
«1 1 4 6»,
all of which are trivial variations on <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%c2%b76%24">.</p>
<p>Of the 715 puzzles, 466 (65%) have solutions; for 175 of these the
solution is unique. There are 3 puzzles with 8 solutions each
(«2 2 4 8»,
«2 3 6 9»,
and «2 4 6 8»), one with 9 solutions («2 3 4 6»), and one with 10 solutions
(«2 4 4 8»).</p>
<p>The 10 solutions for «2 4 4 8»
are as follows:</p>
<table align=center>
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%208%20%2d%202%20%c3%97%204%20%20%20%20%24"><td>SUM [ MUL [ 4 8 ÷ ] - MUL [ 2 4 ÷ ] ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%20%282%20%2b%208%20%2d%204%29%20%20%20%24"><td>MUL [ 4 SUM [ 2 8 - 4 ] ÷ ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%288%20%2d%204%29%20%c3%97%20%282%20%2b%204%29%20%24"><td>MUL [ SUM [ 8 - 4 ] SUM [ 2 4 - ] ÷ ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%20%284%20%2b%208%29%20%c3%b7%202%20%20%24"><td>MUL [ 4 SUM [ 4 8 - ] ÷ 2 ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%284%20%2d%202%29%20%c3%97%20%284%20%2b%208%29%20%24"><td>MUL [ SUM [ 4 - 2 ] SUM [ 4 8 - ] ÷ ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%248%20%c3%97%20%282%20%2b%204%2f4%29%20%20%20%20%20%24"><td>MUL [ 8 SUM [ 1 2 - ] ÷ ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%20%c3%97%204%20%c3%97%204%20%2d%208%20%20%20%20%24"><td>SUM [ MUL [ 2 4 4 ÷ ] - 8 ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%248%20%2b%202%20%c3%97%20%284%20%2b%204%29%20%20%20%24"><td>SUM [ 8 MUL [ 2 SUM [ 4 4 - ] ÷ ] - ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%2b%204%20%2b%202%20%c3%97%208%20%20%20%20%20%24"><td>SUM [ 4 4 MUL [ 2 8 ÷ ] - ]
<tr><td><img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%244%20%c3%97%20%288%20%2d%204%2f2%29%20%24"><td>MUL [ 4 SUM [ 8 - MUL [ 4 ÷ 2 ] ] ÷ ]
</table>
<p><a href="https://pic.blog.plover.com/math/24-puzzle-2/Solutions-24.txt">A complete listing of every essentially different solution to every
«a b c d» puzzle is available here</a>.
There are 1,063 solutions in all.</p>
<h2>Arguable points <a name="arguable"></a></h2>
<p>There are a few places where we have not completely pinned down what
it means for two solutions to be essentially the same; I think there
is room for genuine disagreement. </p>
<ol>
<li><p>Any solution involving <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%c3%972%24"> can be changed into a slightly different
solution involving <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%242%2b2%24"> instead. These expressions are
arithmetically different but numerically equal. For example, I
mentioned earlier that
«2 2 4 8»
has 8 solutions. But two of these are <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%208%20%2b%204%20%c3%97%20%282%20%2b%202%29%24"> and <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%0a%20%20%20%208%20%2b%204%20%c3%97%202%20%c3%97%202%24">. I am willing to accept these as
essentially different. Toph, however, disagrees.</p></li>
<li><p>A similar but more complex situation arises in connection with «1
2 3 7». Consider <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%c3%977%2b3%24">, which equals 24. To get a solution
to «1 2 3 7», we can replace either of the threes in <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%243%c3%977%2b3%24">
with <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%281%2b2%29%24">, obtaining <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%28%281%20%2b%202%29%20%c3%97%207%29%20%2b%203%24"> or <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%20%283%c3%977%29%2b%281%0a%20%20%20%20%2b2%29%24">. My program considers these to be different solutions.
Toph is unsure.</p></li>
</ol>
<p>It would be pretty easy to adjust the normalization process to handle
these the other way if the user wanted that.</p>
<h2>Some interesting puzzles</h2>
<p><a href="https://pic.blog.plover.com/math/24-puzzle-2/JJZ4631.jpg"><img align=right border=0 src="https://pic.blog.plover.com/math/24-puzzle-2/JJZ4631-sm.png" /></a></p>
<p>«1 2 7 7»
has only one solution, quite unusual. <a href="https://pic.blog.plover.com/math/24-puzzle-2/1277.txt">(Spoiler)</a>
«2 2 6 7»
has two solutions, both somewhat unusual. <a href="https://pic.blog.plover.com/math/24-puzzle-2/2267.txt">(Spoiler)</a></p>
<p>Somewhat similar to
«1 2 7 7»
is
«3 9 9 9»
which also has an unusual solution. But it has two other solutions
that are less surprising. <a href="https://pic.blog.plover.com/math/24-puzzle-2/3999.txt">(Spoiler)</a></p>
<p>«1 3 8 9» has an easy solution but also a quite tricky solution.
<a href="https://pic.blog.plover.com/math/24-puzzle-2/1389.txt">(Spoiler)</a></p>
<p>One of my neighbors has the license plate <code>JJZ 4631</code>.
«4 6 3 1» is one of the more difficult puzzles.</p>
<h2>What took so long?</h2>
<p><a href="https://blog.plover.com/math/24-puzzle.html">Back in March, I wrote</a>:</p>
<blockquote>
<p>I have enough material for at least three or four more articles
about this that I hope to publish here in the coming weeks.</p>
<p>But <a href="https://blog.plover.com/math/17-puzzle.html">the previous article on this
subject</a> ended similarly, saying</p>
<blockquote>
<p>I hope to write a longer article about solvers in the next week or so.</p>
</blockquote>
<p>and that was in July 2016, so don't hold your breath.</p>
</blockquote>
<p>And here we are, five months later!</p>
<p>This article was a <em>huge</em> pain to write. Sometimes I sit down to write
something and all that comes out is dreck. I sat down to write this
one at least three or four times and it never worked. The tortured
Git history bears witness. In the end I had to abandon all my earlier
drafts and start over from scratch, writing a fresh outline in an
empty file.</p>
<p>But perseverance paid off! WOOOOO.</p>
<p>[ Addendum 20170825: I completely forgot that Shreevatsa R. wrote <a href="https://shreevatsa.wordpress.com/2016/07/20/a-simple-puzzle-with-a-foray-into-inequivalent-expressions/">a very interesting article on the same topic as this one</a>,
in July of last year soon after I published my first article in this
series. ]</p>
<p>[ Addendum 20170829: A previous version of this article used the notations <code>SUM [ … # … ]</code>
and <code>MUL [ … # … ]</code>, which I said I didn't like. Zellyn Hunter has
persuaded me to replace these with <code>SUM [ … - … ]</code> and <code>MUL
[ … ÷ … ]</code>. Thank you M. Hunter! ]</p>
<p>[ <a href="https://blog.plover.com/math/24-puzzle-3.html">Yet more on this topic!</a> ]</p>
tag:,2017:/math/erdosThat time I met Erdős2017-08-08T21:06:00Z2017-08-08T21:06:00ZMark Dominushttp://www.plover.com/mjd@plover.com
<p>I should have written about this sooner, by now it has been so long
that I have forgotten most of the details.</p>
<p>I first encountered Paul Erdős in the middle 1980s at a talk by
<a href="https://www.math.nyu.edu/~pach/">János Pach</a> about almost-universal
graphs. Consider graphs with a countably infinite set of vertices.
Is there a "universal" graph <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24G%24"> such that, for any finite or
countable graph <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24H%24">, there is a copy of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24H%24"> inside of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24G%24">?
(Formally, this means that there is an injection from the vertices of
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24H%24"> to the vertices of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24G%24"> that preserves adjacency.) The answer
is yes; <a href="https://en.wikipedia.org/wiki/Rado_graph">it is quite easy to construct such a
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24G%24"></a> and in fact nearly
all random graphs have this property.</p>
<p>But then the questions become more interesting. Let <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24K_%5comega%24"> be the
complete graph on a countably infinite set of vertices. Say that
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24G%24"> is “almost universal” if it includes a copy of <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24H%24"> for every
finite or countable graph <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24H%24"> <em>except</em> those that contain a copy of
<img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24K_%5comega%24">. Is there an almost universal graph? Perhaps surprisingly,
no! (<a href="https://math.stackexchange.com/a/449625/25554">Sketch of
proof</a>.)</p>
<p>I enjoyed the talk, and afterward in the lobby I got to meet Ron
Graham and Joel Spencer and talk to them about their Ramsey theory
book, which I had been reading, and about a problem I was working on.
Graham encouraged me to write up my results on the problem and submit
them to <a href="https://en.wikipedia.org/wiki/Mathematics_Magazine"><em>Mathematics
Magazine</em></a>, but I
unfortunately never got around to this.
Graham was there babysitting Erdős, who was one of Pách's
collaborators, but I did not actually talk to Erdős at that time. I
think I didn't recognize him. I don't know why I was able to
recognize Graham.</p>
<p>I find the almost-universal graph thing very interesting.
<a href="https://arxiv.org/abs/1404.5757">It is still an open research area</a>.
But none of this was what I was planning to talk about. I will return
to the point. A couple of years later Erdős was to speak at the
University of Pennsylvania. He had a stock speech for general
audiences that I saw him give more than once. Most of the talk would
be a description of a lot of interesting problems, the bounties he
offered for their solutions, and the progress that had been made on
them so far. He would intersperse the discussions with the sort of
Erdősism that he was noted for: referring to the U.S. and the
U.S.S.R. as “Sam” and “Joe” respectively; his ever-growing series of
styles (Paul Erdős, P.G.O.M., A.D., etc.) and so on.</p>
<p>One remark I remember in particular concerned the $3000 bounty he
offered for proving what is sometimes known as
<a href="https://en.wikipedia.org/wiki/Erd%C5%91s_conjecture_on_arithmetic_progressions">the Erdős-Túran conjecture</a>:
if <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%24"> is a subset of the natural numbers, and if <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24%5csum_%7bn%5cin%0aS%7d%5cfrac%201n%24"> diverges, then <img src="https://chart.apis.google.com/chart?chf=bg,s,00000000&cht=tx&chl=%24S%24"> contains arbitrarily long arithmetic
progressions. (A special case of this is that the primes contain
arbitrarily long arithmetic progressions, which was
<a href="https://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem">proved in 2004 by Green and Tao</a>,
but which at the time was a long-standing conjecture.) Although the
$3000 was at the time the largest bounty ever offered by Erdős, he
said it was really a bad joke, because to solve the problem would
require so much effort that the per-hour payment would be minuscule.</p>
<p>I made a special trip down to Philadelphia to attend the talk, with
the intention of visiting my girlfriend at Bryn Mawr afterward. I
arrived at the Penn math building early and wandered around the halls
to kill time before the talk. And as I passed by an office with an
open door, I saw Erdős sitting in the antechamber on a small sofa. So I sat down
beside him and started telling him about my favorite graph theory
problem.</p>
<p>Many people, preparing to give a talk to a large roomful of strangers,
would have found this annoying and intrusive. Some people might not want to
talk about graph theory with a passing stranger. But most people are
not Paul Erdős, and I think what I did was probably just the right
thing; what you <em>don't</em> do is sit next to Erdős and then ask how his flight
was and what he thinks of recent politics. We talked about my problem, and to
my great regret I don't remember any of the mathematical details of
what he said. But he did not know the answer offhand, he was not able
solve it instantly, and he did say it was interesting. So! I had a
conversation with Erdős about graph theory that was not a waste of his
time, and I think I can count that as one of my lifetime
accomplishments.</p>
<p>After a little while it was time to go down to the auditorium for the
the talk, and afterward one of the organizers saw me, perhaps
recognized me from the sofa, and invited me to the guest dinner, which
I eagerly accepted. At the dinner, I was thrilled because I secured a
seat next to Erdős! But this was a beginner mistake: he fell asleep
almost immediately and slept through dinner, which, I learned later,
was completely typical.</p>
<!--
[ From searching of my email archives, I have learned that the first
episode took place on Friday, 5 January 1990, and I now think the two
episodes took place in the reverse order, with the dinner
happening in the late 1980s as I said. ]
-->