13
$\begingroup$

Let $P(n)$ be the set of all monic polynomials of degree $n$ with integer coefficients, such that all coefficients have absolute value at most $2^n$.

Given a positive integer $n$ let us define $A(n)$ as the minimal number $m$ such that for any $f \in P(n)$ there exists a field $k$ with at most $m$ elements such that for some $x\in k$ we have $\bar f(x)=0$, where $\bar f$ is the reduction of $f$ modulo the characteristic of $k$.

Q: What is the asymptotic behaviour of $A(n)$? In particular is it true that $\liminf_{n} \frac{A(n)}{n} = 0$ ?

$\endgroup$
  • 6
    $\begingroup$ Here's a heuristic that suggests not: a randomly chosen polynomial over $\Bbb F_q$ has some probability $c_q$ of not having a root, and that probability (probably) goes to $1/e$ as $q\to\infty$ by comparison with a Poisson process. Assuming independence, the probability of a randomly chosen polynomial not having a root modulo any prime up to $n$ is roughly $1/e^{n/\log n}$; since $e^{n/\log n} = o(n2^n)$, this suggests that there are still lots of polynomials in $P(n)$ without roots modulo any of those primes (or, by the same argument, in any finite field of size less than $n$). $\endgroup$ – Greg Martin Jan 16 '18 at 23:39
  • 1
    $\begingroup$ Consider the polynomial $g(x)=x(x-1)(x-2)\cdots(x-n)+1$ and the number $N = {\rm lcm}(1,2,\cdots,n)$. Then $N$ is of size about $\exp(n)$ and one can take the remainder of the coefficients of $g$ modulo $N$ to obtain a monic polynomial $f$ with coefficients bounded by $\exp(n)$. This polynomial has no roots in prime fields for all $p\leq n$. Maybe there is a similar construction that takes also care of field extensions. $\endgroup$ – Andreas Thom Jan 17 '18 at 21:25
5
$\begingroup$

No to the final question, stealing an idea from Andreas Thom. For all primes $p$ and degrees $d$ with $p^d>m$, there is a degree $d$ monic polynomial over $\mathbb F_p$ that has no roots in any field of characteristic $p$ of order $\leq m$. Indeed, an irreducible polynomial of degree $d$ does the trick.

Applying this, for any degree $d$ with $2^d > m$, there is a degree $d$ monic polynomial over $\mathbb Z/ P_m \mathbb Z$ where $P_m= \prod_{p\textrm{ prime}, p \leq m} p $ which does not have any roots in any field of cardinality at most $m$.

We can now lift this to an integral polynomial, with coefficients $<P_m$. So any $n$ with $2^n \geq P_m$ and $2^n > m$ has $A(n)>m$. Obviously the first condition is the interesting one, so we have $$n \approx \log_2 P_m = \sum_{p \textrm{ prime}, p \leq m} \frac{\log p}{\log 2} \approx \frac{m}{\log 2}$$ by the prime number theorem.

So $A(n) $ is greater than, approximately, $n \log 2$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.