# complexity of deciding whether there's a small polynomial with a given root

Let $$f\in (\mathbb{Z}/p\mathbb{Z})^\ast$$ be a nonzero element of a prime finite field. For $$d, r\in \mathbb{N}$$ consider the problem of deciding whether there is a nonzero polynomial $$P(x) = a_0 +a_1x+a_2x^2+...+~a_dx^d \in \mathbb{Z}[x]$$ of degree not exceeding $$d$$, and also $$|a_i|\leq r$$ for all $$i$$, and also such that $$\overline{P}(x)\in (\mathbb{Z}/p\mathbb{Z})[x]$$ has $$f$$ as a root. (So this is a decision problem depending on $$f, p, d, r$$). Is there anything known about the general time complexity of this problem?

• @EmilJeřábek that's very helpful. thank you – Tim kinsella Jun 27 '19 at 16:33
• @Emil, that looks to me like it should be an answer. – Peter Taylor Jun 28 '19 at 22:40
• I converted the comments to a proper answer. – Emil Jeřábek supports Monica Jul 1 '19 at 12:38

Here is an algorithm that solves the problem in time $$\tilde O\Bigl(\min\Bigl\{(2r+1)^{\frac{d+1}2},p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)}\Bigr\}\sqrt r\Bigl)\subseteq\tilde O(p).$$ The tildes hide $$(\log p)^{O(1)}$$ factors coming from operations in $$\mathbb F_p$$ and from implementation of sets by, say, min-heaps.

First, observe that the answer is always YES if $$d+1\ge\frac{\log(p+1)}{\log(r+1)}$$: there are $$(r+1)^{d+1}\ge p+1$$ polynomials $$P$$ of degree at most $$d$$ with coefficients in $$\{0,\dots,r\}$$, hence by the pigeonhole principle, there exist two such polynomials $$P_0\ne P_1$$ such that $$\overline{P_0}(f)=\overline{P_1}(f)$$. Then $$P=P_0-P_1$$ satisfies the requirements.

Thus, we may assume without loss of generality $$d+1\le\left\lfloor\frac{\log p}{\log(r+1)}\right\rfloor.$$ Then (assuming $$r\ge1$$) $$(2r+1)^{\frac{d+1}2}\le p^{\frac{\log(2r+1)}{2\log(r+1)}}\le p^{\frac12\bigl(1+\frac1{\log(r+1)}\bigr)},$$ hence it suffices to find an algorithm working in time $$\tilde O\Bigl((2r+1)^{\frac{d+2}2}\Bigr).$$

For any $$i\le d+1$$, let $$V_i=\{\overline P(f):P\in\mathbb Z[x],P\ne0,\deg(P) Using this notation, the problem is equivalent to finding out if $$0\in V_{d+1}$$, and we can compute $$V_i$$ using a simple recurrence. The whole algorithm looks like this:

1. If $$r=0$$, output NO.

2. If $$d+1\ge\frac{\log(p+1)}{\log(r+1)}$$, output YES.

3. For each $$j=\lceil\log(d+2)\rceil,\dots,1$$, compute $$V_{\lfloor(d+1)2^{-j}\rfloor}$$ and $$f^{\lfloor(d+1)2^{-j}\rfloor}$$ by using the recurrences \begin{align*} V_0&=\varnothing,\\ V_{2i}&=V_i\cup\bigl\{a+f^ib:a\in V_i\cup\{0\},b\in V_i\bigr\},\\ V_{2i+1}&=V_{2i}\cup\bigl\{a+f^{2i}b:a\in V_{2i}\cup\{0\},b\in\{\pm1,\dots,\pm r\}\bigr\}, \end{align*} where all the arithmetic operations are modulo $$p$$.

4. If $$d$$ is even, compute $$V_{\lceil(d+1)/2\rceil}$$ from $$V_{\lfloor(d+1)/2\rfloor}$$ as above.

5. If $$0\in V_{\lceil(d+1)/2\rceil}$$, output YES.

6. For each $$a\in V_{\lceil(d+1)/2\rceil}$$, if $$-af^{\lceil(d+1)/2\rceil}\in V_{\lfloor(d+1)/2\rfloor}$$, then output YES.

7. Output NO.

It should be clear from the discussion above that the algorithm is correct. Moreover, we have $$|V_i|\le(2r+1)^i,$$ and since these bounds form a geometric series, it is easy to see that the time needed to compute $$V_i$$ using the above recurrences is also $$\tilde O\Bigl((2r+1)^i\Bigr).$$ Thus, the algorithm runs in time $$\tilde O\Bigl((2r+1)^{\lceil(d+1)/2\rceil}\Bigr)\subseteq\tilde O\Bigl((2r+1)^{(d+2)/2}\Bigr).$$