5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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"? $\endgroup$
    – Anthony Quas
    May 20, 2014 at 23:44
  • $\begingroup$ I think the objects are $\mathbb{Z}/p\mathbb{Z}$ actions on the permutation groups $S_n$. $\endgroup$
    – john mangual
    May 20, 2014 at 23:53
  • 1
    $\begingroup$ 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! $\endgroup$
    – Anthony Quas
    May 21, 2014 at 5:20
  • $\begingroup$ Probably I'm telling you what you saw already. Apologies if this is the case. $\endgroup$
    – Anthony Quas
    May 21, 2014 at 5:21

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I think I understand the Frobenius map really well $x \mapsto x^q$ but I certainly do not get Étale cohomology. $\endgroup$
    – john mangual
    May 21, 2014 at 0:14
  • 5
    $\begingroup$ What does that comment have to do with my answer? $\endgroup$
    – Qiaochu Yuan
    May 21, 2014 at 0:16
  • $\begingroup$ I am not asking about function fields, I am asking about number fields and $\mathbb{Z}$ $\endgroup$
    – john mangual
    May 21, 2014 at 0:18
  • 5
    $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    May 21, 2014 at 0:19
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Qiaochu Yuan
    May 21, 2014 at 0:27
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.