A lot of the stuff I've written in the past couple of years has been
on math.StackExchange. Some of it is pretty mundane, but some is
interesting. My summary of April's interesting posts was
well-received, so here are the noteworthy posts I made in May 2015.
What matrix transforms !!(1,0)!! into !!(2,6)!! and tranforms
!!(0,1)!! into
!!(4,8)!!? was a
little funny because the answer is $$\begin{pmatrix}2 & 4 \\ 6 & 8
\end{pmatrix}$$ and yeah, it works exactly like it appears to,
there's no trick. But if I just told the guy that, he might feel
unnecessarily foolish. I gave him a method for solving the problem
and figured that when he saw what answer he came up with, he might
learn the thing that the exercise was designed to teach him.
Is a “network topology'” a topological
space?
is interesting because several people showed up right away to say
no, it is an abuse of terminology, and that network topology really
has nothing to do with mathematical topology. Most of those comments
have since been deleted. My answer was essentially: it is
topological, because just as in mathematical topology you care about
which computers are connected to which, and not about where any of
the computers actually are.
Nobody constructing a token ring network thinks that it has to be a
geometrically circular ring. No, it only has to be a topologically
circular ring. A square is fine; so is a triangle; topologically
they are equivalent, both in networking and in mathematics. The
wires can cross, as long as they don't connect at the crossings.
But if you use something that isn't topologically a ring, like say
a line or a star or a tree, the network doesn't work.
The term “topological” is a little funny. “Topos” means “place”
(like in “topography” or “toponym”) but in topology you don't care
about places.
Is there a standard term for this generalization of the Euler
totient function?
was asked by me. I don't include all my answers in these posts, but
I think maybe I should have a policy of including all my questions.
This one concerned a simple concept from number theory which I was
surprised had no name: I wanted !!\phi_k(n)!! to be the number of
integers !!m!! that are no larger than !!n!! for which !!\gcd(m,n) =
k!!. For !!k=1!! this is the famous Euler totient function, written
!!\varphi(n)!!.
But then I realized that the reason it has no name is that it's
simply !!\phi_k(n) = \varphi\left(\frac n k\right)!! so there's no need
for a name or a special notation.
As often happens, I found the answer myself shortly after I asked
the question. I wonder if the reason for this is that my time to
come up with the answer is Poisson-distributed. Then if I set a time
threshold for how long I'll work on the problem before asking about
it, I am likely to find the answer to almost any question that
exceeds the threshold shortly after I exceed the threshold. But if
I set the threshold higher, this would still be true, so there is
no way to win this particular game. Good feature of this theory: I
am off the hook for asking questions I could have answered myself.
Bad feature: no real empirical support.
how many ways can you divide 24 people into groups of
two? displays a
few oddities, and I think I didn't understand what was going on at
that time. OP has calculated the first few special cases:
1:1 2:1 3:3 4:3 5:12 6:15
which I think means that there is one way to divide 2 people into
groups of 2, 3 ways to divide 4 people, and 15 ways to divide 6
people. This is all correct! But what could the 1:1, 3:3, 5:12
terms mean? You simply can't divide 5 people into groups of 2.
Well, maybe OP was counting the extra odd person left over as a sort
of group on their own? Then odd values would be correct; I didn't
appreciate this at the time.
But having calculated 6 special cases correctly, why can't OP
calculate the seventh? Perhaps they were using brute force: the
next value is 48, hard to brute-force correctly if you don't have a
enough experience with combinatorics.
I tried to suggest a general strategy: look at special cases, and
not by brute force, but try to analyze them so that you can come
up with a method for solving them. The method is unnecessary for
the small cases, where brute force enumeration suffices, but you can
use the brute force enumeration to check that the method is
working. And then for the larger cases, where brute force is
impractical, you use your method.
It seems that OP couldn't understand my method, and when they tried
to apply it, got wrong answers. Oh well, you can lead a horse to
water, etc.
The other pathology here is:
I think I did what you said and I got 1.585times 10 to the 21
for the !!n=24!! case. The correct answer is
$$23\cdot21\cdot19\cdot17\cdot15\cdot13\cdot11\cdot9\cdot7\cdot5\cdot3\cdot1
= 316234143225 \approx 3.16\cdot 10^{11}.$$ OP didn't explain how
they got !!1.585\cdot10^{21}!! so there's not much hope of
correcting their weird error.
This is someone who probably could have been helped in person, but
on the Internet it's hopeless. Their problems are Internet
communication problems.
Lambda calculus
typing isn't
especially noteworthy, but I wrote a fairly detailed explanation of
the algorithm that Haskell or SML uses to find the type of an
expression, and that might be interesting to someone.
I think Special representation of a
number is the
standout post of the month. OP speculates that, among numbers of
the form !!pq+rs!! (where !!p,q,r,s!! are prime), the choice of
!!p,q,r,s!! is unique. That is, the mapping !!\langle
p,q,r,s\rangle \to pq+rs!! is reversible.
I was able to guess that this was not the case within a couple of
minutes, replied pretty much immediately:
I would bet money against this representation being unique.
I was sure that a simple computer search would find
counterexamples. In fact, the smallest is !!11\cdot13 + 19\cdot 29
= 11\cdot 43 + 13\cdot 17 = 694!! which is small enough that you
could find it without the computer if you are patient.
The obvious lesson to learn from this is that many elementary
conjectures of this type can be easily disproved by a trivial
computer search, and I frequently wonder why more amateur
mathematicians don't learn enough computer programming to
investigate this sort of thing. (I wrote recently on the topic of
An ounce of theory is worth a pound of search
, and this is an interesting
counterpoint to that.)
But the most interesting thing here is how I was able to instantly
guess the answer. I explained in some detail in the post. But the
basic line of reasoning goes like this.
Additive properties of the primes are always distributed more or
less at random unless there is some obvious reason why they can't
be. For example, let !!p!! be prime and consider !!2p+1!!. This
must have exactly one of the three forms !!3n-1, 3n,!! or !!3n+1!!
for some integer !!n!!. It obviously has the form !!3n+1!! almost
never (the only exception is !!p=3!!). But of the other two forms
there is no obvious reason to prefer one over the other, and indeed
of the primes up to 10,000, 611 are of the type !!3n!! and and 616
are of the type !!3n-1!!.
So we should expect the value !!pq+rs!! to be distributed more or
less randomly over the set of outputs, because there's no obvious
reason why it couldn't be, except for simple stuff, like that it's
obviously almost always even.
So we are throwing a bunch of balls at random into bins, and the
claim is that no bin should contain more than one ball. For that to
happen, there must be vastly more bins than balls. But the bins are
numbers, and primes are not at all uncommon among numbers, so the
number of bins isn't vastly larger, and there ought to be at least
some collisions.
In fact, a more careful analysis, which I wrote up on the site,
shows that the number of balls is vastly larger—to have them be
roughly the same, you would need primes to be roughly as common as
perfect squares, but they are far more abundant than that—so as you
take larger and larger primes, the number of collisions increases
enormously and it's easy to find twenty or more quadruples of primes
that all map to the same result. But I was able to predict this
after a couple of minutes of thought, from completely elementary
considerations, so I think it's a good example of Lower Mathematics
at work.
This is an example of a fairly common pathology of math.se
questions: OP makes a conjecture that !!X!! never occurs or that
there are no examples with property !!X!!, when actually !!X!!
almost always occurs or every example has property !!X!!.
I don't know what causes this. Rik Signes speculates that it's just
wishful thinking: OP is doing some project where it would be useful
to have !!pq+rs!! be unique, so posts in hope that someone will tell
them that it is. But there was nothing more to it than baseless
hope. Rik might be right.
[ Addendum 20150619: A previous version of this article included the delightful typo “mathemativicians”. ]