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
    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
    Jan 19, 2017 at 22:31

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.