Factorization patterns on nonlinear families of univariate polynomials over a finite field
Tóm tắt
We estimate the number $$|\mathcal {A}_{{\varvec{\lambda }}}|$$ of elements on a nonlinear family $$\mathcal {A}$$ of monic polynomials of $$\mathbb {F}_{q}[T]$$ of degree r having factorization pattern $${\varvec{\lambda }}:=1^{\lambda _1}2^{\lambda _2}\ldots r^{\lambda _r}$$. We show that $$|\mathcal {A}_{{\varvec{\lambda }}}|= \mathcal {T}({\varvec{\lambda }})\,q^{r-m}+\mathcal {O}(q^{r-m-{1}/{2}})$$, where $$\mathcal {T}({\varvec{\lambda }})$$ is the proportion of elements of the symmetric group of r elements with cycle pattern $${\varvec{\lambda }}$$ and m is the codimension of $$\mathcal {A}$$. We provide explicit upper bounds for the constants underlying the $$\mathcal {O}$$-notation in terms of $${\varvec{\lambda }}$$ and $$\mathcal {A}$$ with “good” behavior. We also apply these results to analyze the average-case complexity of the classical factorization algorithm restricted to $$\mathcal {A}$$, showing that it behaves as good as in the general case.
Tài liệu tham khảo
Bank, E., Bary-Soroker, L., Rosenzweig, L.: Prime polynomials in short intervals and in arithmetic progressions. Duke Math. J. 164(2), 277–295 (2015)
Benoist, O.: Degrés d’homogénéité de l’ensemble des intersections complètes singulières. Ann. Inst. Fourier (Grenoble) 62(3), 1189–1214 (2012)
Cafure, A., Matera, G.: Improved explicit estimates on the number of solutions of equations over a finite field. Finite Fields Appl. 12(2), 155–185 (2006)
Cafure, A., Matera, G.: An effective Bertini theorem and the number of rational points of a normal complete intersection over a finite field. Acta Arith. 130(1), 19–35 (2007)
Cafure, A., Matera, G., Privitelli, M.: Singularities of symmetric hypersurfaces and Reed–Solomon codes. Adv. Math. Commun. 6(1), 69–94 (2012)
Cafure, A., Matera, G., Privitelli, M.: Polar varieties, Bertini’s theorems and number of points of singular complete intersections over a finite field. Finite Fields Appl. 31, 42–83 (2015)
Caniglia, L., Galligo, A., Heintz, J.: Equations for the projective closure and effective Nullstellensatz. Discrete Appl. Math. 33, 11–23 (1991)
Cesaratto, E., Matera, G., Pérez, M.: The distribution of factorization patterns on linear families of polynomials over a finite field. Combinatorica 37(5), 805–836 (2017)
Chatzidakis, Z., van den Dries, L., Macintyre, A.: Definable sets over finite fields. J. Reine Angew. Math. 427, 107–135 (1992)
Cohen, S.: The distribution of polynomials over finite fields. Acta Arith. 17, 255–271 (1970)
Cohen, S.: Uniform distribution of polynomials over finite fields. J. Lond. Math. Soc. (2) 6(1), 93–102 (1972)
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, New York (1992)
D’Andrea, C., Krick, T., Szanto, A.: Subresultants in multiple roots. Linear Algebra Appl. 438(5), 1969–1989 (2013)
Danilov, V.: Algebraic varieties and schemes. In: Shafarevich, I.R. (ed.) Algebraic Geometry I. Encyclopaedia of Mathematical Sciences, vol. 23, pp. 167–307. Springer, Berlin (1994)
Eisenbud, D.: Commutative Algebra with a View Toward Algebraic Geometry. Graduate Texts in Mathematics, vol. 150. Springer, New York (1995)
Ernst, T.: Generalized Vandermonde Determinants, Report 2000:6 Matematiska Institutionen, Uppsala Universitet. http://www.math.uu.se/research/pub/. Accessed 31 Aug 2010 (2000)
Flajolet, P., Fusy, E., Gourdon, X., Panario, D., Pouyanne, N.: A hybrid of Darboux’s method and singularity analysis in combinatorial asymptotics. Electron. J. Combin. 13(1) (2006) research paper r103
Flajolet, P., Gourdon, X., Panario, D.: The complete analysis of a polynomial factorization algorithm over finite fields. J. Algorithms 40(1), 37–81 (2001)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Fried, M., Haran, D., Jarden, M.: Effective counting of the points of definable sets over finite fields. Israel J. Math. 85(1–3), 103–133 (1994)
Fried, M., Smith, J.: Irreducible discriminant components of coefficient spaces. Acta Arith. 44(1), 59–72 (1984)
Fulton, W.: Intersection Theory. Springer, Berlin (1984)
Gao, S., Howell, J., Panario, D.: Irreducible polynomials of given forms. In: Finite Fields: Theory, Applications, and Algorithms. Fourth International Conference, Waterloo, Ontario, Canada, 12–15 Aug 1997. American Mathematical Society, Providence, pp. 43–54 (1999)
Geddes, K., Czapor, S., Labahn, G.: Algorithms for Computer Algebra. Kluwer Academic Publishers, Dordrecht (1992)
Ghorpade, S., Lachaud, G.: Étale cohomology, Lefschetz theorems and number of points of singular varieties over finite fields. Mosc. Math. J. 2(3), 589–631 (2002)
Ghorpade, S., Lachaud, G.: Number of solutions of equations over finite fields and a conjecture of Lang and Weil. In: Agarwal, A.K., et al. (eds.) Number Theory and Discrete Mathematics (Chandigarh, 2000), pp. 269–291. Hindustan Book Agency, New Delhi (2002)
Gibson, C.: Elementary Geometry of Algebraic Curves: An Undergraduate Introduction. Cambridge University Press, Cambridge (1998)
Golomb, S., Gaal, P.: On the number of permutations of \(n\) objects with greatest cycle length \(k\). Adv. Appl. Math. 20(1), 98–107 (1998)
Graham, R., Knuth, D., Patashnik, O.: Concrete Mathematics: A Foundation for Computer Science, 2nd edn. Addison-Wesley, Reading (1994)
Greene, D., Knuth, D.: Mathematics for the Analysis of Algorithms, 3rd edn. Birkhäuser, Basel (1990)
Ha, J.: Irreducible polynomials with several prescribed coefficients. Finite Fields Appl. 40, 10–25 (2016)
Harris, J.: Algebraic Geometry: A First Course. Graduate Texts in Mathematics, vol. 133. Springer, New York (1992)
Heintz, J.: Definability and fast quantifier elimination in algebraically closed fields. Theoret. Comput. Sci. 24(3), 239–277 (1983)
Knopfmacher, A., Knopfmacher, J.: The distribution of values of polynomials over a finite field. Linear Algebra Appl. 134, 145–151 (1990)
Knuth, D.E.: The Art of Computer Programming II: Semi-numerical Algorithms, vol. 2, 3rd edn. Addison-Wesley, Reading (1998)
Kunz, E.: Introduction to Commutative Algebra and Algebraic Geometry. Birkhäuser, Boston (1985)
Lascoux, A., Pragacz, P.: Jacobians of symmetric polynomials. Ann. Comb. 6(2), 169–172 (2002)
Lachaud, G., Rolland, R.: On the number of points of algebraic sets over finite fields. J. Pure Appl. Algebra 219(11), 5117–5136 (2015)
Lidl, R., Niederreiter, H.: Finite Fields. Addison-Wesley, Reading (1983)
Matera, G., Pérez, M., Privitelli, M.: On the value set of small families of polynomials over a finite field, II. Acta Arith. 165(2), 141–179 (2014)
Matera, G., Pérez, M., Privitelli, M.: Explicit estimates for the number of rational points of singular complete intersections over a finite field. J. Number Theory 158(2), 54–72 (2016)
Merca, M.: A note on the determinant of a Toeplitz–Hessenberg matrix. Spec. Matrices 1, 10–16 (2013)
Muir, T.: The Theory of Determinants in the Historical Order of Development. Dover Publications Inc., New York (1960)
Pardo, L.M., San Martín, J.: Deformation techniques to solve generalized Pham systems. Theoret. Comput. Sci. 315(2–3), 593–625 (2004)
Pérez, M.: Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos. Ph.D. thesis, Univ. Buenos Aires, Argentina (2016)
Pollack, P.: Irreducible polynomials with several prescribed coefficients. Finite Fields Appl. 22, 70–78 (2013)
Shafarevich, I.R.: Basic Algebraic Geometry: Varieties in Projective Space. Springer, New York (1994)
Shepp, L., Lloyd, S.: Ordered cycle lengths in a random permutation. Trans. Amer. Math. Soc. 121, 340–357 (1996)
Shoup, V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press, Cambridge (2005)
von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (1999)
von zur Gathen, J., Matera, G.: Explicit estimates for polynomial systems defining irreducible smooth complete intersections. Preprint arXiv:1512.05598 [math.NT] (2018), to appear in Acta Arith
Vogel, W.: Results on Bézout’s Theorem. Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 74. Tata Institute of Fundamental Research, Bombay (1984)
Zassenhaus, H.: On Hensel factorization I. J. Number Theory 1, 291–311 (1969)