Sparse Univariate Polynomials with Many Roots Over Finite Fields

For a $t$-nomial $f(x) = \sum_{i = 1}^t c_i x^{a_i} \in \mathbb{F}_q[x]$, we show that the number of distinct, nonzero roots of $f$ is bounded above by $2 (q-1)^{1-\varepsilon} C^\varepsilon$, where $\varepsilon = 1/(t-1)$ and $C$ is the size of the largest coset in $\mathbb{F}_q^*$ on which $f$ vanishes completely. Additionally, we describe a number-theoretic parameter depending only on $q$ and the exponents $a_i$ which provides a general and easily-computable upper bound fo...

We show that univariate trinomials $x^n + ax^s + b \in \mathbb{F}_q[x]$ can have at most $\delta \Big\lfloor \frac{1}{2} +\sqrt{\frac{q-1}{\delta}} \Big\rfloor$ distinct roots in $\mathbb{F}_q$, where $\delta = \gcd(n, s, q - 1)$. We also derive explicit trinomials having $\sqrt{q}$ roots in $\mathbb{F}_q$ when $q$ is square and $\delta=1$, thus showing that our bound is tight for an infinite family of finite fields and trinomials. Furthermore, we present the results of a lar...

We present a deterministic 2^O(t)q^{(t-2)(t-1)+o(1)} algorithm to decide whether a univariate polynomial f, with exactly t monomial terms and degree <q, has a root in F_q. A corollary of our method --- the first with complexity sub-linear in q when t is fixed --- is that the nonzero roots in F_q can be partitioned into at most 2 \sqrt{t-1} (q-1)^{(t-2)(t-1)} cosets of two subgroups S_1,S_2 of F^*_q, with S_1 in S_2. Another corollary is the first deterministic sub-linear algo...

For any fixed field $K\!\in\!\{\mathbb{Q}_2,\mathbb{Q}_3,\mathbb{Q}_5, \ldots\}$, we prove that all polynomials $f\!\in\!\mathbb{Z}[x]$ with exactly $3$ (resp. $2$) monomial terms, degree $d$, and all coefficients having absolute value at most $H$, can be solved over $K$ within deterministic time $\log^{7+o(1)}(dH)$ (resp. $\log^{2+o(1)}(dH)$) in the classical Turing model: Our underlying algorithm correctly counts the number of roots of $f$ in $K$, and for each such root gen...

Let K be a field and t>=0. Denote by Bm(t,K) the maximum number of non-zero roots in K, counted with multiplicities, of a non-zero polynomial in K[x] with at most t+1 monomial terms. We prove, using an unified approach based on Vandermonde determinants, that Bm(t,L)<=t^2 Bm(t,K) for any local field L with a non-archimedean valuation v such that v(n)=0 for all non-zero integer n and residue field K, and that Bm(t,K)<=(t^2-t+1)(p^f-1) for any finite extension K/Qp with residual...

We reveal a complexity chasm, separating the trinomial and tetranomial cases, for solving univariate sparse polynomial equations over certain local fields. First, for any fixed field $K\in\{\mathbb{Q}_2,\mathbb{Q}_3,\mathbb{Q}_5,\ldots\}$, we prove that any polynomial $f\in\mathbb{Z}[x]$ with exactly $3$ monomial terms, degree $d$, and all coefficients having absolute value at most $H$, can be solved over $K$ in deterministic time $O(\log^{O(1)}(dH))$ in the classical Turing ...

Let $\mathbb F_q$ be a finite field and $n$ a positive integer. In this article, we prove that, under some conditions on $q$ and $n$, the polynomial $x^n-1$ can be split into irreducible binomials $x^t-a$ and an explicit factorization into irreducible factors is given. Finally, weakening one of our hypothesis, we also obtain factors of the form $x^{2t}-ax^t+b$ and explicit splitting of $x^n-1$ into irreducible factors is given.

We obtain new upper bounds on the number of distinct roots of lacunary polynomials over finite fields. Our focus will be on polynomials for which there is a large gap between consecutive exponents in the monomial expansion.

We consider the problem of finding a sparse multiple of a polynomial. Given f in F[x] of degree d over a field F, and a desired sparsity t, our goal is to determine if there exists a multiple h in F[x] of f such that h has at most t non-zero terms, and if so, to find such an h. When F=Q and t is constant, we give a polynomial-time algorithm in d and the size of coefficients in h. When F is a finite field, we show that the problem is at least as hard as determining the multipl...

Let $\mathbb{F}_q$ be the finite field with $q$ elements, and $T$ a positive integer. In this article we find a sharp estimative of the total number of monic irreducible binomials in $\mathbb F_q[x]$ of degree less or equal to $T$, when $T$ is large enough.