Uniform estimates for almost primes over finite fields
We establish a new asymptotic formula for the number of polynomials of degree n with k prime factors over a finite field Fq. The error term tends to 0 uniformly in n and in q. Previously, asymptotic formulas were known either for fixed q, through the works of Warlimont [Arch. Math. (Basel) 60 (1993)...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
American Mathematical Society
2022
|
| _version_ | 1826312293021908992 |
|---|---|
| author | Elboim, D Gorodetsky, O |
| author_facet | Elboim, D Gorodetsky, O |
| author_sort | Elboim, D |
| collection | OXFORD |
| description | We establish a new asymptotic formula for the number of polynomials of degree n with k prime factors over a finite field Fq. The error term tends to 0 uniformly in n and in q. Previously, asymptotic formulas were known either for fixed q, through the works of Warlimont [Arch. Math. (Basel) 60 (1993), pp. 58-72] and Hwang [Random Structures Algorithms 13 (1998), pp. 17-47], or for small k, through the work of Arratia, Barbour and Tavaré [Math. Proc. Cambridge Philos. Soc. 114 (1993), pp. 347-368]. As an application, we estimate the total variation distance between the number of cycles in a random permutation on n elements and the number of prime factors of a random polynomial of degree n over Fq. The distance tends to 0 at rate 1/(q√log n). Previously this was only understood when either q is fixed and n tends to ∞, or n is fixed and q tends to ∞, by results of Arratia, Barbour and Tavaré. |
| first_indexed | 2024-03-07T08:25:20Z |
| format | Journal article |
| id | oxford-uuid:db5decf9-2e4d-462b-a44e-daa2911abab0 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T08:25:20Z |
| publishDate | 2022 |
| publisher | American Mathematical Society |
| record_format | dspace |
| spelling | oxford-uuid:db5decf9-2e4d-462b-a44e-daa2911abab02024-02-14T08:48:47ZUniform estimates for almost primes over finite fieldsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:db5decf9-2e4d-462b-a44e-daa2911abab0EnglishSymplectic ElementsAmerican Mathematical Society2022Elboim, DGorodetsky, OWe establish a new asymptotic formula for the number of polynomials of degree n with k prime factors over a finite field Fq. The error term tends to 0 uniformly in n and in q. Previously, asymptotic formulas were known either for fixed q, through the works of Warlimont [Arch. Math. (Basel) 60 (1993), pp. 58-72] and Hwang [Random Structures Algorithms 13 (1998), pp. 17-47], or for small k, through the work of Arratia, Barbour and Tavaré [Math. Proc. Cambridge Philos. Soc. 114 (1993), pp. 347-368]. As an application, we estimate the total variation distance between the number of cycles in a random permutation on n elements and the number of prime factors of a random polynomial of degree n over Fq. The distance tends to 0 at rate 1/(q√log n). Previously this was only understood when either q is fixed and n tends to ∞, or n is fixed and q tends to ∞, by results of Arratia, Barbour and Tavaré. |
| spellingShingle | Elboim, D Gorodetsky, O Uniform estimates for almost primes over finite fields |
| title | Uniform estimates for almost primes over finite fields |
| title_full | Uniform estimates for almost primes over finite fields |
| title_fullStr | Uniform estimates for almost primes over finite fields |
| title_full_unstemmed | Uniform estimates for almost primes over finite fields |
| title_short | Uniform estimates for almost primes over finite fields |
| title_sort | uniform estimates for almost primes over finite fields |
| work_keys_str_mv | AT elboimd uniformestimatesforalmostprimesoverfinitefields AT gorodetskyo uniformestimatesforalmostprimesoverfinitefields |