6
$\begingroup$

Let $P\in \mathbb{R}\lbrack x\rbrack$ be given. (In practice, the coefficients could be given as, say, decimals to sufficient precision.) Let $M\geq 1$, and let $I$ be an interval in $\mathbb{R}/\mathbb{Z}$ of length $\epsilon \ll 1/M$. Can we find (more or less) quickly the values of $m$, $1\leq m\leq M$, such that that $P(m)\in I$?

Notes:

(a) For $P$ linear, this isn't hard. Let $P(x) = a_1 x + a_0$. By Dirichlet approximation (which we can implement quickly using continued fractions), there are $Q\sim M$, $q\leq Q$, $0\leq a<q$ such that $a_1 = a/q +\beta/q Q$, where $|\beta|\leq 1$. For $P(m) \in I$ to hold, we must have $m \equiv a^{-1} b \mod q$, where $b$ is of the form $(\lfloor (\alpha - a_0) q\rfloor + c) \mod q$, where $\alpha$ is the midpoint of $I$ (say) and $c=O(1)$. Let $0\leq r<q$ be such that $r\equiv q^{-1} b\mod q$. Then we are tasked with finding $k\leq L/q$ such that $P(k q + r) \in I$.

Now, $P(k q + r) \equiv \beta k/Q + a_1 r + a_0$, and so we must find $k\leq L/q\sim Q/q$ such that $\beta k/Q$ lies in an interval contained in $\lbrack 0,1/q\rbrack$. This we can do just by division (over $\mathbb{R}$).

(b) For $P$ of degree $\geq 2$, this cannot be very easy: for $q$ an integer, $L=q$, solving the special case $P(x) = x^2/q$ is equivalent to finding square roots mod $q$, and that is equivalent to factorizing $q$.

At the same time, I would see any algorithm that works in time $O_\epsilon(M^\epsilon)$ as being acceptable, so factorization isn't a hard barrier.

$\endgroup$
5
  • $\begingroup$ Can't (a refinement of) Sturm's theorem be of any help? $\endgroup$ May 26, 2016 at 14:50
  • $\begingroup$ This is an interesting suggestion, but I am skeptical. $\mathbb{R}/\mathbb{Z}$ doesn't have a natural linear ordering. $\endgroup$ May 26, 2016 at 16:07
  • $\begingroup$ What about a covering thereof to perform the calculations before switching back to the base space? $\endgroup$ May 26, 2016 at 16:59
  • $\begingroup$ I'm not sure I quite understand. Do you suggest testing for the real roots of P(x) = n for all integers n in a range? $\endgroup$ May 26, 2016 at 17:59
  • $\begingroup$ Yes, if really the linear ordering is a key ingredient, you can recover it with a spiral above $R/Z$ taking into account the number of laps while describing this spiral before projecting a given point there on on the circle $R/Z$. But it's just a suggestion that came to my mind rather out of the blue, there's no warranty it will actually work. $\endgroup$ May 26, 2016 at 19:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.