News aggregator

Mark Jason Dominus: Math.SE report 2015-05

Planet Haskell - Thu, 06/18/2015 - 9:01pm

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 into and tranforms into ? 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 to be the number of integers that are no larger than for which . For this is the famous Euler totient function, written .

    But then I realized that the reason it has no name is that it's simply 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 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 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 (where are prime), the choice of is unique. That is, the mapping 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 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 be prime and consider . This must have exactly one of the three forms or for some integer . It obviously has the form almost never (the only exception is ). 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 and and 616 are of the type .

    So we should expect the value 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 questions: OP makes a conjecture that never occurs or that there are no examples with property , when actually almost always occurs or every example has property .

    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 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”. ]

Categories: Offsite Blogs

shakespeare >= 2.0.2 fails to install in OS X 10.6.8, Haskell-platform 2014.2.0.0; cabal-install

haskell-cafe - Thu, 06/18/2015 - 6:38pm
(I already sent a comment on the Shakespeare site but couldn't get too far. So, if this isn't the right place for this issue, I'd appreciate you point me to the right one.) Hi, I can't install yesod. Doing a cabal install yesod-bin or cabal install yesod fails because it fails to build shakespeare. I tried with all versions of shapeare >= 2.0, as required by yesod-bin. Below are all outputs. My environment: OS X 10.6.8, Xcode 3.2 Haskell-platform 2014.2.0.0 ghc-7.8.3 cabal-install using version of the Cabal library. This corresponds to a fresh install of the HP, ghc, and cabal I didn't before trying to install yesod. The developer of Shakespeare suspects that be a bug of HP and suggested I try a clean install of GHC as explained in However, the bindist available there doesn't work with my OS 10.6.8 I have a large screen output from those trials that you can check on the Shakespeare github page corresponding to the thread I star
Categories: Offsite Discussion

Mild confusion around type family

haskell-cafe - Thu, 06/18/2015 - 5:19pm
Below is a very simple almost canonical natural number model. I'm slightly confused by how type families work Wikipedia says.... "Type families are a feature of some type systems<> that allow PARTIAL functions between types to be defined by pattern matching<>" So... lets do something simple I want this to be a type error!...but the above type family appears to not be partial...this IS defined...."Sub Z (S Z)" is a type! (I thought it wasn't) CONFIDENTIALITY NOTICE This e-mail (and any attached files) is confidential and protected by copyright (and other intellectual property rights). If you are not the intended recipient please e-mail the sender and then delete the email and any attached files immediately. Any further use or dissemination is prohibited. While MTV Networks Europe has taken steps to ensure that this email and any attachments are virus free, it is your responsibility to ensure that this messag
Categories: Offsite Discussion

Haskell and Spark

haskell-cafe - Thu, 06/18/2015 - 4:59pm
Hello, There was a posting from a Polish guy(Wojcieh .,,,, been trying to contact him) on implementing a library/wrapper for Spark. Does anybody know the status? Vasili _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe< at >
Categories: Offsite Discussion

No way to retrieve the base of a Set or Map in O(1)

libraries list - Thu, 06/18/2015 - 11:27am
Hello, there seems to be no way to retrieve the base of a Set or Map in O(1), since there is no relevant function in the respective libraries and the constructors Bin and Tip are not exported in any module. I think retrieving any one element from a Set or Map might be useful sometimes, so I modestly ask for an implementation. I see that there is splitRoot, but the docs advice, not to rely on the current form of the resulting list, since it might be subject to change. Having this function, with its current result, it might be interesting to be able to efficiently build the union of the lower and the upper parts by simply connecting the trees at their bases. What do you think? Kind regards, André _______________________________________________ Libraries mailing list Libraries< at >
Categories: Offsite Discussion

SHA sums of cabal-install binaries

libraries list - Wed, 06/17/2015 - 9:03pm
Hi, are the SHA sums of cabal-install binaries available somewhere? GHC provides them on the download pages, but I couldn't find them anywhere for cabal-install. If not, would it be possible to provide them? Thanks, Petr _______________________________________________ Libraries mailing list Libraries< at >
Categories: Offsite Discussion

zlib-0.6.1 bug?

libraries list - Wed, 06/17/2015 - 1:00pm
Agda sees some segmentation faults when compiled with zlib-0.6.1.x, but not with zlib- You might want to constrain zlib < 0.6 for now. (I reported the issue to the maintainer a couple of weeks ago, but have not gotten any response yet.) Cheers, Andreas
Categories: Offsite Discussion

Math in Haddock

libraries list - Sun, 06/14/2015 - 10:06pm
I thought folks might be interested in a little example of what is now possible in Haddock (assuming my PR is accepted): Anyone wanting to live on the edge can build their own haddock and upload their haddocks manually to hackage: Dominic Steinitz dominic< at >
Categories: Offsite Discussion

Math in Haddock

libraries list - Sun, 06/14/2015 - 10:01pm
I thought folks might be interested in a little example of what is now possible in Haddock (assuming my PR is accepted): <> Anyone wanting to live on the edge can build their own haddock and upload their haddocks manually to hackage: Dominic Steinitz dominic< at > _______________________________________________ Libraries mailing list Libraries< at >
Categories: Offsite Discussion

New gtk2hs 0.12.4 release

gtk2hs - Wed, 11/21/2012 - 12:56pm

Thanks to John Lato and Duncan Coutts for the latest bugfix release! The latest packages should be buildable on GHC 7.6, and the cairo package should behave a bit nicer in ghci on Windows. Thanks to all!


Categories: Incoming News