An Experimental (yet fully rigorous!) Study of a certain "Measure Of Disarray" that 12-year Noga Alon Proved was always Even
By Shalosh B. Ekhad and Doron Zeilberger
.pdf
.tex
First Written: Sept. 29, 2021. This version: Oct. 14, 2021.
Last update of this web-page (but not article): Dec. 16, 2021
In a beautiful new "coffee table book", "Do not Erase", by the very talented artistic photographer Jessica Wynne, there are
pictures of more than one hundred blackboards by a very diverse set of mathematicians. One of them is
Noga Alon's blackboard.
Each blackboard photo is accompanied by a short essay by the creator of the blackboard, where they often
describe how they decided to become mathematicians. According to Noga Alon, the "epiphany" occured when he
was 12 years old, when he settled a heated argument in a
"Eurovision watching party" that his parents threw,
where he conclusively proved that a certain "measure of disarray" must always be even, in particular
causing one of the guests, "a grown-up engineer", to concede that he was wrong in claiming that it was a coincdence that the scores turned out to be all even.
According to Noga, the fact that a 12-year-old can win an argument against a grown-up (especially one who is an engineer)
shows the objectivity of mathematical truth, and reinforced his decision to become a mathematician.
While I do agree that mathematical knowledge is more objective than most other kinds, it is not as objective as it seems.
But the point of the present article is to investigate, in a purely empirical (yet fully rigorous!) way, that same measure of disarry,
that turned out to be called "Spearman's footrule", going far beyond just proving that it is always even,
considerably extending a 1977 paper by Persi Diaconis and Ron Graham, debunking yet-another myth:
that mathematics is always deductive.
Here is the talk.
Added Sept. 30, 2021: Stoyan Dimitrov told us about these two interesting papers:
-
The generating function for total displacement
by T. Kyle Petersen and Mathieu Guay-Paquet, a
-
Moments of permutation statistics and central limit theorems
by Stoyan Dimitrov and Niraj Khare.
Added Oct. 6, 2021: Read
Martin Rubey's insightful comments .
Added Oct. 14, 2021: T. Kyle Petersen has shown us how to stick inversions in the Motzkin approach. This is now implemented in the current version of the Maple package.
Maple packages
-
Noga12.txt (version of Oct. 14, 2021)
The following Maple package is not refereed to in the paper. It contains all the functions of the former package and extra ones regaring Spearman's other "measure of disarray", the
so-called Spearman's ρ (the sum of the squares of (pi[i]-i) rather than the sum of the absolue values). To get a list of the new procedures (about Spearman's ρ) , use ezraRho();
-
Noga12Rho.txt
In order to use it you also need to download the following data set
Input and Output files for Noga12.txt
-
If you want to see an article with explicit expressions for the first 12 moments of Spearman's footrule (that only took 17 seconds to generate), and a partial (elementary!) proof of
asymptotic normality, first proved (completely, but using heavy machinery) by Persi Diaconis.
the input file yields
the output file
-
If you want to see an article with many mixed moments of Noga Alon's permutation statistic (aka Spearman's footrule) and the more famous measure of disarray called "number of inversions",
and a partial (elementary!) proof that they are joint-normal, but, of course, not independently so (the asymptotic correlation turned out to be 3/sqrt(10))
the input file yields
the output file
-
If you want to see the weight-enumerators according to Spearman's footrule of the symmetric groups on {1,...,n}, in other words
the polynomial in q whose coefficient of qi is the number of permutations on {1,...,n} whose Spearman's footrule equals i
for n from 1 to 25
the input file yields
the output file
Note that indeed there are no odd powers (as proved by 12-year-old Noga Alon in general)
-
If you want to see the Joint weight-enumerators according to the pair [Number of Inversions, Spearman's footrule] of the symmetric groups on {1,...,n}, in other words
the polynomial in the variables p and q whose coefficients of piqj is the number of permutations on {1,...,n} whose number of inversions is i and Spearman's footrule equals j
for n from 1 to 22
the input file yields
the output file
-
[Added Oct. 4, 2021] As mentioned about Stoyan Dimitov pointed my attention to this interesting article.
The generating function for total displacement
by T. Kyle Petersen and Mathieu Guay-Paquet. This makes computing the weight-enumerators much faster. In particular, now we have the first
18 moments, and probably can go much further. To see them
the input file yields
the output file
-
[Added Dec. 16, 2021] If you want to see the leading terms, to order 3, for the even (2r)-th moment, and odd , (2r+1)-th moment,
for ARBITRARY (symbolic) r, proving (modulo routine chencking), with a vengenace, the asympototic normality
(that only needs the leading terms to order 1),
the input file yields
the output file
Input and Output files for Noga12Rho.txt
-
If you want to see an article with explicit expressions for the first 5 moments of Spearman's Rho, and a partial (elementary!) proof of
asymptotic normality, first (probably) proved completely, by Persi Diaconis
the input file yields
the output file
-
If you want to see an article with many mixed moments of Spearman's Rho "measure of disarray", and the more famous measure of disarray called "number of inversions",
and a partial (elementary!) proof that they are joint-normal, with the perfect (asymptotic!) correlation of 1
the input file yields
the output file
-
If you want to see the weight-enumerators according to Spearman's RHO of the symmetric groups on {1,...,n}, in other words
the polynomial in q whose coefficient of qi is the number of permutations on {1,...,n} whose Spearman's RHO equals i
for n from 1 to 22
the input file yields
the output file
-
If you want to see the Joint weight-enumerators according to the pair [Number of Inversions, Spearman's Rho] of the symmetric groups on {1,...,n}, in other words
the polynomial in the variables p and q whose coefficients of piqj is the number of permutations on {1,...,n} whose number of inversions is i and Spearman's rho equals j
for n from 1 to 20
the input file yields
the output file
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page