Thursday, September 27, 2012

Counting permutations: an open question

Nati Linial is giving a talk in Lille. As I am typing, he is stating an elegant combinatorial result and open problem, that I had never seen before.

One dimension ({0,1} n*n matrix with exactly one 1 per row or column): The number of permutations satisfies Stirling's formula: it's [(1+o(1)(n/e)]^n

Two dimensions ({0,1} n*n*n matrix with exactly one 1 per row, column or shaft): The number of Latin squares, as seen from Van Lint and Wilson's book, is [(1+o(1))(n/e^2)]^{n^2}.

Conjecture: in d dimensions, it's [(1+o(1))(n/e^d)]^{n^d}

Linial and Zur Luria proved the "less than or equal to" side. The "greater than or equal to" is still open.

Wednesday, September 26, 2012

Poincaré and dynamical systems

Etienne Ghys, a famous French mathematician in dynamical systems, is giving a general audience talk in front of me in Lille as I type. He admires Henri Poincaré greatly. Here is one example of a problem studied by Poincaré. You are playing a lottery game with a wheel decomposed into sectors colored red and black in alternation, ask someone to give the wheel a push, wait until it stops, and win or lose according to the color of the outcome. How do you know that the probability of the outcome of the red is 1/2? This is really about studying a map from the initial velocity to the final effect, i.e. the total angle that the wheel will turn. The push will make the wheel turn perhaps up to 50 turns. What do we know about this map? Essentially nothing, but we know that it's a map with a "big derivative". That may sound crazy: what can that mean, when there is no unit? Well, sure there is: for the outcome of the system, the unit is one full turn, i.e. 360 degrees; for the initial velocity, the unit is the smallest difference in velocity that can be perceived. Poincaré: "Ce sont là des différences que le sens musculaire ne peut apprécier et qui échapperaient aux instruments de mesure les plus délicats. La différence dans la cause est imperceptible. La différence dans l'effet est pour moi de plus haute importance, puisqu'il y va de mon argent." Poincare proves that if the cause is distributed according to some diffuse probability measure, then the result is an equidistribution. He says: "You are asking me to predict future phenomena. If, quite unluckily, I happen to know the laws of these phenomena, I could achieve those goals only at the prize of inextricable computations, and I should renounce to answer you. But if I am lucky enough to not know them, I can answer you right away, and the most astonishing thing is that my answer will be correct".