Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds

We show that the proportion of polynomials of degree $n$ over the finite field with $q$ elements, which have a divisor of every degree below $n$, is given by $c_q n^{-1} + O(n^{-2})$. More generally, we give an asymptotic formula for the proportion of polynomials, whose set of degrees of divisors has no gaps of size greater than $m$. To that end, we first derive an improved estimate for the proportion of polynomials of degree $n$, all of whose non-constant divisors have degre...

Let $k,p\in \mathbb{N}$ with $p$ prime and let $f\in\mathbb{Z}[x_1,x_2]$ be a bivariate polynomial with degree $d$ and all coefficients of absolute value at most $p^k$. Suppose also that $f$ is variable separated, i.e., $f=g_1+g_2$ for $g_i\in\mathbb{Z}[x_i]$. We give the first algorithm, with complexity sub-linear in $p$, to count the number of roots of $f$ over $\mathbb{Z}$ mod $p^k$ for arbitrary $k$: Our Las Vegas randomized algorithm works in time $(dk\log p)^{O(1)}\sqrt...

Let $q\geqslant 2$ be a fixed prime power. We prove an asymptotic formula for counting the number of monic polynomials that are of degree $n$ and have exactly $k$ irreducible factors over the finite field $\mathbb{F}_q$. We also compare our results with the analogous existing ones in the integer case, where one studies all the natural numbers up to $x$ with exactly $k$ prime factors. In particular, we show that the number of monic polynomials grows at a surprisingly higher ra...

A degree-$d$ polynomial $p$ in $n$ variables over a field $\F$ is {\em equidistributed} if it takes on each of its $|\F|$ values close to equally often, and {\em biased} otherwise. We say that $p$ has a {\em low rank} if it can be expressed as a bounded combination of polynomials of lower degree. Green and Tao [gt07] have shown that bias imply low rank over large fields (i.e. for the case $d < |\F|$). They have also conjectured that bias imply low rank over general fields. In...

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string $x \...

The Function Field Sieve algorithm is dedicated to computing discrete logarithms in a finite field GF(q^n), where q is small an prime power. The scope of this article is to select good polynomials for this algorithm by defining and measuring the size property and the so-called root and cancellation properties. In particular we present an algorithm for rapidly testing a large set of polynomials. Our study also explains the behaviour of inseparable polynomials, in particular we...

We prove a low characteristic counterpart to the main result in (Peluse, 2019), establishing power saving bounds for the polynomial Szemer\'{e}di theorem for certain families of polynomials. Namely, we show that if $P_1, \dots, P_m \in (\mathbb{F}_p[t])[y]$ satisfy an equidistribution condition, which is a natural variant of the independence condition in (Peluse, 2019) for our context, then there exists $\gamma > 0$ such that for any $q = p^k$ and any $A_0, A_1, \dots, A_m \s...

Most integers are composite and most univariate polynomials over a finite field are reducible. The Prime Number Theorem and a classical result of Gau{\ss} count the remaining ones, approximately and exactly. For polynomials in two or more variables, the situation changes dramatically. Most multivariate polynomials are irreducible. This survey presents counting results for some special classes of multivariate polynomials over a finite field, namely the the reducible ones, th...

We establish a new asymptotic formula for the number of polynomials of degree $n$ with $k$ prime factors over a finite field $\mathbb{F}_q$. The error term tends to $0$ uniformly in $n$ and in $q$, and $k$ can grow beyond $\log n$. Previously, asymptotic formulas were known either for fixed $q$, through the works of Warlimont and Hwang, or for small $k$, through the work of Arratia, Barbour and Tavar\'e. As an application, we estimate the total variation distance between th...

In this paper, we give some counting results on integer polynomials of fixed degree and bounded height whose distinct non-zero roots are multiplicatively dependent. These include sharp lower bounds, upper bounds and asymptotic formulas for various cases, although in general there is a logarithmic gap between lower and upper bounds.