2
$\begingroup$

In "Anatomy of Integers and Permutations", http://www.dms.umontreal.ca/~andrew/PDF/Anatomy.pdf, Granville gives a calibration of cycles of a permutation and prime factors of an integer. "We know roughly one out of evert $\log x$ integers up to $x$ is a prime, and that exactly one in every $N$ permutations on $N$ elements is a cycle, so we could try to calibrate by replacing $N$ when we measure the anatomy of a permutation with $\log x$ when we measure the anatomy of an integer."

Is there also a useful link between irreducible factors of a monic polynomial of degree $n$ over $F_q[T]$ and either cycles or prime factors?

A naive guess would be to say that the link between irreducible factors and cycles is trivial due to the similarity of the following theorems:

Prime Number Theorem for Permutations: A randomly selected permutation of $S_n$ will be an $n$-cycle with probability exactly $1/n$.

Prime Number Theorem for Monic Polynomials: The probability that a random monic polynomial $f\in F_q[T]$ of degree $n$ will be irreducible with probability $\approx 1/n$ when $q$ is fixed and $n$ is large (or if $n$ is fixed and characteristic of $F_q$ is large).

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

There is such a link and it is in fact much better understood in the polynomial setting. Namely, if $f$ is a separable polynomial over a finite field, then the action of the Frobenius element on the roots of $f$ gives rise to a permutation whose cycle structure corresponds to the factorization type of $f$.

Then, combinatorial arguments and/or algebraic arguments (such as the Chebotarev Density Theorem) tell us that the distribution of those permutations as $f$ varies over degree $n$ polynomials is roughly the uniform distribution on $S_n$ (as $q$ grows they get closer).

See Terry Tao's post on the subject, which refers to Granville's paper as well:

https://terrytao.wordpress.com/2015/07/15/cycles-of-a-random-permutation-and-irreducible-factors-of-a-random-polynomial/

Improve this answer
$\endgroup$
3
$\begingroup$

I wrote a blog post on this here. The basic result is that for fixed $k$ and $n$, as $q \to \infty$ the joint distribution of irreducible factors of degrees $1$ through $k$ of a random monic polynomial over $\mathbb{F}_q$ of degree $n$ asymptotically approaches the joint distribution of cycles of length $1$ through $k$ of a random permutation in $S_n$. I do not see how this result follows from the Chebotarev density theorem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I like your post! Regarding the density theorem - I want to elaborate, although I am not an expert. Let $a_0, \cdots, a_{n-1}$ be $n$ variables and consider the polynomial $P(T,a_0,\cdots,a_{n-1}) = T^n + \sum a_i T^i$ - the generic monic polynomial of degree $n$. Its Galois group over $\overline{\mathbb{F}_q}(a_0,\cdots,a_{n-1})$ is $S_n$. For each specialization of $a_0,\cdots,a_{n-1}$ we get a polynomial, whose factorization may be read from the action of the Frobenius. The function that associates to each specialization its Frobenius-induced permutation (up to conjugaction) is... $\endgroup$
    – Ofir Gorodetsky
    Commented Jan 19, 2017 at 22:29
  • $\begingroup$ (cont.) in fact, some sort of Artin symbol. Chebotarev tells us that the this Artin symbol is equidistributed in the Galois group of $P(T,a_0,\cdots,a_{n-1})$ as $q \to \infty$. See, for instance Proposition 3.1 in the paper by Bank et. al: arxiv.org/pdf/1302.0625v3.pdf . Technically they apply Lang-Weil, but it is Chebotarev in disguise. $\endgroup$
    – Ofir Gorodetsky
    Commented Jan 19, 2017 at 22:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .