# Analogy between Integers and Permutations

I am reading Andrew Granville's Anatomy of Integers and Permutations where it is argued the factorization of a permutation into disjoint cycles is analogous to the factorization of a number into prime factors.

In the blog-sphere you can find these two ways of defining partitions of unity:

• $m = p_1\cdots{p_k} \in \mathbb{Z}$ and $\{ \frac{\log p_1}{\log m}, \dots, \frac{\log p_k}{\log m}\}$.
• $\sigma = C_1\dots C_k \in S_n$ and $\{ \frac{|C_1|}{n}, \dots, \frac{|C_n|}{n} \}$

One can prove both of these converge to the Poisson-Dirichlet process. It looks like $n \approx \log m$ in this analogy and $\mathbb{Z} \simeq S_n$.

This is a correspondence between partitions, but what could be permuted in the $\mathbb{Z}$ side?

It seems necessary to clarify, that the analogy between $\mathbb{Z}, \mathbb{F}_q[t],\mathbb{C}(z)$ has gotten attention recently and I have not read them closely enough:

I have found many individual parts of these papers difficult to grasp - and they are put together - and I maybe I can ask more questions on these topics later?

Today, my question may have to do with the last link... suppose we do have this machine comparing statistics on the function field $\mathbb{F}_q[t]$ to statistics of $S_n$ as Qiaochu say. How do we "dequantize" to get a result in $\mathbb{Z}$? The implication is there is some kind of permutation group action on the integers and I was wondering what it could be.

Maybe it's $q \to 1$ limit?

-
Do you think it's more than "if you compute certain statistics for (a) prime factorization; and (b) cycle decomposition of permutations, then for large $n$, the distributions are close to the same thing"? – Anthony Quas May 20 '14 at 23:44
I think the objects are $\mathbb{Z}/p\mathbb{Z}$ actions on the permutation groups $S_n$. – john mangual May 20 '14 at 23:53
Having a 1 min glance at the Granville article, it seems to me that the objects are integers and permutation. He factorizes integers into primes and gets a "partition of unity" from that (i.e. $(\log p_1/\log n,\ldots,\log p_d/\log n)$). He factorizes permutations into cycles and gets a partition of unity from that $(\ell_1(\sigma),\ldots,\ell_d(\sigma))$. So I think the analogy is 1) pick a prime of size roughly $e^N$ and find its partition of unity; pick a permutation on roughly $N$ symbols and find its partition of unity. Lo and Behold! they have (roughly) the same distribution! – Anthony Quas May 21 '14 at 5:20
Probably I'm telling you what you saw already. Apologies if this is the case. – Anthony Quas May 21 '14 at 5:21

The essential common feature that insures convergence to a Poisson Dirichlet distribution is explained in the book "Logarithmic Combinatorial Structures" by Arratia Barbour and Tavare. They do a great job, I think.

-

it's possible to extend the analogy to the factorization of polynomials over finite fields $\mathbb{F}_q$ (see this blog post for details; one needs to take $q \to \infty$ for the statistics to match, and in the post I only verify convergence in the sense of moments and am a bit sloppy). In this setting the permutation is Frobenius. But I don't think there's an analogous statement on the number field side.

I think results like this should be thought of as central limit-type theorems more than anything else; there are certain kinds of statistics that occur universally in certain general situations which otherwise don't necessarily have much in common.

-
I think I understand the Frobenius map really well $x \mapsto x^q$ but I certainly do not get Étale cohomology. – john mangual May 21 '14 at 0:14
What does that comment have to do with my answer? – Qiaochu Yuan May 21 '14 at 0:16
I am not asking about function fields, I am asking about number fields and $\mathbb{Z}$ – john mangual May 21 '14 at 0:18
I find that comment strange. If you're willing to take an analogy between prime factorization and cycle decomposition seriously I don't see how it could hurt to know that it factors through an analogy to factorization of polynomials over finite fields, which on the one hand is part of a well-established analogy between number fields and function fields (which requires no knowledge of etale cohomology to appreciate) and where on the other hand I can explicitly point to a permutation that determines the factorization. – Qiaochu Yuan May 21 '14 at 0:19
I"m claiming that there isn't anything being permuted if you only look at $\mathbb{Z}$ (obviously the logarithms of primes are not cycle lengths, e.g. they aren't commensurate), but also that there's no reason to restrict your attention to $\mathbb{Z}$. I'm reasonably confident that you get the same kind of statistics for any Dedekind domain $D$ such that $D/P$ is always finite for all prime ideals $P$. – Qiaochu Yuan May 21 '14 at 0:27

If I remember well, there is also a correspondence between the degrees of factors of polynomials in $\mathbb{F}_q[X]$, the size of cycles of riffle-shuffle permutations (a brand of non-uniform random permutations ), and the size of factors in the Lyndon decomposition of random words on an alphabet with $q$ letters, with the Poisson Dirichlet distribution as an asymptotic again. I think I found this in the following paper : Diaconis, M.J. McGrath, and J. Pitman, Riffle shuffles, cycles, and descents, Combinatorica, 1995, in which a correspondence by Ira Gessel was mentioned.

-