Uniform estimates for smooth polynomials over finite fields

Uniform estimates for smooth polynomials over finite fields, Discrete Analysis 2023:16, 31 pp.

A positive integer $n$ is called $m$-smooth if its largest prime factor has size at most $m$. (Sometimes such numbers are called $m$-friable: the word “friable” means “crumbly” and captures the idea that $n$ can be broken up into small pieces.) Smooth numbers play an important role in several parts of number theory, particularly parts with a computational component, such as integer factorization.

An obvious question to ask is how common smooth numbers are. A well known result in this direction, due to Dickman, states that if $n=m^t$ with $t\geq 1$, then the number of $m$-smooth numbers less than $n$ is equal to $(\rho(t)+o(1))n$, where the function $\rho$, now known as the Dickman-de Bruijn function is defined for $t\geq 1$ by the differential equation

$$\rho(t)=\rho(t-1)+t\rho'(t)=0$$
together with the “initial condition” $\rho(t)=1$ for $0\leq t\leq 1$. (An equation of the form above is known as a differential delay equation.)

One can formulate a notion of smoothness whenever one has a class of objects with some measure of size and some kind of unique factorization. Two particularly important examples are permutations, where the size is just the number of objects permuted and the factorization is the cycle decomposition, and polynomials, where the size is the degree and the factorization is into irreducible polynomials.

It turns out that these two examples are closely related. In 1997, Knopfmacher and Manstavičius proved that for fixed $q$ the expected length of the largest cycle in the cycle decomposition of a random permutation of $n$ elements is asymptotically equal to the expected degree of the largest irreducible factor of a random polynomial of degree $n$ over $\mathbb F_q$. Very roughly, the explanation they gave for this phenomenon was that cycle lengths of random permutations are naturally modelled by Poisson random variables with a certain conditioning, while degrees of factors of random polynomials are naturally modelled by geometric random variables. One can then show that these two model distributions approximately agree on suitable ranges of the parameters. Furthermore, the Dickman-de Bruijn function shows up again: the probability that a random permutation in $S_n$ is $m$-smooth is $\rho(n/m)+o(1)$, as is the probability that a random polynomial over $\mathbb F_q$ of degree $n$ is $m$-smooth. (Note that this relates quite naturally to the integer result, since $q^n$, the number of monic polynomials of degree $n$, is equal to $(q^m)^{n/m}$.)

This paper investigates the relationship between smoothness probabilities for permutations and polynomials in much more detail, obtaining improved error estimates over a greater range of values of $m$ (given $n$). If $m$ is too small then the asymptotics are no longer comparable. For instance, the number of 2-smooth permutations is easily seen to be at most $2^nn^{n/2}$ (since every product of 2-cycles can be obtained by choosing a subset $A$ of $\{1,2,\dots,n\}$ of size at most $n/2$ and for each $a\in A$ choosing a partner). As the total number of permutations is $n!\geq(n/e)^n$, the probability that a random permutation is $2$-smooth is subexponentially small, whereas the probability that a random polynomial of degree $n$ over $\mathbb F_q$ is 2-smooth is trivially at least $q^{-n}$.

It turns out that there are two thresholds of interest. For $m\geq(2+\epsilon)\log n$, the ratio between the two probabilities is close to 1. For $m$ between $(1+\epsilon)\log n$ and $(2-\epsilon)\log n$ the ratio is no longer close to 1 but is given by a function of $m/\log n$ that is somewhat complicated to define. And for $m\leq(1-\epsilon)\log n$ there is no longer a fixed ratio.

The proofs of these results are interesting in that they do not yield asymptotics for either of the two probabilities being compared. Rather, they work directly with the difference and show that it is small, by showing that the difference between two related generating functions is small. Applying known lower bounds for one of the probabilities is then sufficient to show that the ratio of the two is close to 1.

Unlike many results that prove analogues for polynomials of results about the integers, the results of this paper concern a phenomenon (the comparison of polynomials with permutations) that does not apply in any obvious way to the integer case and requires genuinely different insights. The introduction to the paper also contains a useful short survey of related results in the literature, to which this paper is a valuable addition.

The video below is of a talk by the author about smooth numbers and smooth polynomials.