{
  "id": "1807.08052",
  "version": "v1",
  "published": "2018-07-20T23:09:18.000Z",
  "updated": "2018-07-20T23:09:18.000Z",
  "title": "Factorization patterns on nonlinear families of univariate polynomials over a finite field",
  "authors": [
    "Guillermo Matera",
    "Mariana Pérez",
    "Melina Privitelli"
  ],
  "comment": "37 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We estimate the number $|\\mathcal{A}_{\\boldsymbol\\lambda}|$ of elements on a nonlinear family $\\mathcal{A}$ of monic polynomials of $\\mathbb{F}_q[T]$ of degree $r$ having factorization pattern $\\boldsymbol\\lambda:=1^{\\lambda_1}2^{\\lambda_2}\\cdots r^{\\lambda_r}$. We show that $|\\mathcal{A}_{\\boldsymbol\\lambda}|= \\mathcal{T}(\\boldsymbol\\lambda)\\,q^{r-m}+\\mathcal{O}(q^{r-m-{1}/{2}})$, where $\\mathcal{T}(\\boldsymbol\\lambda)$ is the proportion of elements of the symmetric group of $r$ elements with cycle pattern $\\boldsymbol\\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 $\\boldsymbol\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-20T23:09:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "factorization pattern",
      "univariate polynomials",
      "nonlinear family",
      "finite field",
      "explicit upper bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 37,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}