In finite fields, is there anything analogous to Sturm sequences for counting the number of roots of a polynomial in a given interval? Alternatively, showing that there are zero roots in a given interval would be almost as useful.

With Sturm sequences, the problem is that sign has no meaning in finite fields, so I don't know of a meaningful way to count sign changes.

The Fourier–Budan theorem seems to also rely on sign changes.

  • $\begingroup$ What is an interval in a finite field? $\endgroup$ – Robert Israel May 24 at 15:39
  • $\begingroup$ For a field of prime order, it's analogous to an interval in integers, except wrapping around at the modulus and not allowed to be larger than the modulus. For a power of a prime, the conjunction of simple intervals (as above), one for each power of x. In binary fields, just understand the simple intervals as {0}, {1}, {}, or {0,1}. $\endgroup$ – Tehom - Tom Breton May 24 at 15:50

I didn't intend to post an answer to my own question, but Robert Israel's comment triggered an idea in my brain.

Here's a way to detect whether p(x) in a finite field has any roots in a given interval, or more generally in any given set of points.

All we need to do is to force any root in the interval to be a square, ie to have multiplicity at least two, and then detect squares.

So we precompute another polynomial r(x) that has exactly one root at each point of interest, and no roots elsewhere. Then we do square-finding on p(x)*r(x).

There is actually an analogy to Sturm sequences there, in that a common way to check for squares is to take the GCD of a polynomial and its derivative. But this is more efficient in that we don't need to compute signs or anything else on the remainders, we just check whether the result of GCD is a zero-degree polynomial or not.

This may not be an improvement over brute force, in that the degree of r(x) is just one less than the number of points we'd evaluate at to check by brute force. But if we have some freedom to choose our interval of interest, we can choose an interval such that r(x) and d r(x)/dx have some simple form, so there are grounds to hope that our work will be only proportional to the degree of p(x).

(Edit) I originally didn't think about false positives, because the above does what I need and my p(x) won't have roots with multiplicity. But it could give false positives when p(x) has some root outside the interval with multiplicity 2 or greater.

If that's a concern, you can detect squares on p(x) first, and then either remove the squares from p(x) or leave them and if the result of the GCD is the same as the known squares treat it as no root found.

| cite | improve this answer | |

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.