# Polynomial-time complexity and a question and a remark of Serre

My question is about the theory of complexity, but let me first explain my motivation, which comes from number theory or more precisely from trying to understand a question/conjecture of Serre and a remark he made about it. Yesterday at Harvard, Jean-Pierre Serre gave a wonderful colloquium on "Variation with $p$ of the number of solutions mod $p$ of a system of polynomial equations". There was many things in it, most of them I knew (but beautifully explained nevertheless), but some lines of thought seemed completely new (and at least they surely where for me):

Let $P(X)$ be a fixed non-zero polynomial in $\mathbb{Z}[X]$. Let us denote by $N(p)$ the number of solution of $P(X) \equiv 0 \pmod{p}$. Serre noticed that there was a very simple, efficient and old algorithm, already present in a paper by Galois and probably older (since Galois refers to it as well-known), to compute $N(p)$ for big values of $p$: compute by Euclid's method the gcd of $X^p-X$ and $P(X)$ in $\mathbb{Z}/p\mathbb{Z}[X]$. The degree of this polynomial is the number of solutions $N(p)$. The algorithm, Serre said, runs in $O(\log(p)^{2+\epsilon})$.

Now if it happens that all roots of $P(X)$ are in a cyclotomic fields (for example, a quadratic polynomial) then $N(p)$ is determined by some congruences, that is there is an $m$ such that $N(p)$ depends only on $p \pmod{m}$ (For $P$ quadratic, it is just the quadratic reciprocity law), and in this case, determining $N(p)$ can be made in $O(\log p)$ steps obviously.

Serre asked (or conjectured, I don't remember for sure the term he used) if conversely, the existence of an algorihhm in linear time $O(\log p)$ to compute $N(p)$ would imply that all roots of $P$ are in a cyclotomic field.

After that he made a remark that I didn't fully understand, that he had asked some friends that were specialists of complexity theory and and that they told him there were not theorem proving statement like "for a given problem, there is no algorithm solving it in linear time", but I am not sure if this was really that, nor if he was talking only of this specific problem or of all computable problems.

Well, my question just aims to understand Serre's remark

Do we know of a computable question (with answer yes or no) depending of a parameter $n$ such that the answer can be given in $O((\log n)^r)$ steps but provably not in $O((\log n)^s)$, where $1 \leq s < r$ are real numbers? If yes, how do we do that? If no, are there conjecture that for some problem it is not possible?

(Remark:the answer to the question of Serre is a natural integer, not yes or no, but since this integer is less than the degree of $P$, obviously it can be transformed into a finite set of "yes or no" questions).

I am an absolute beginner in complexity theory. I made some research on the web this morning and yesterday, but I didn't find an answer or anything close. My question may be very basic and a reference to a text discussing this kind of questions would be a perfectly nice answer.

Yes, if $1\le r< s$, there exists a set of integers computable in time $O((\log x)^s)$, but not in time $O((\log x)^r)$, where $x$ is the input number written in binary. This is an instance of the time hierarchy theorem. However, the only known such problems are obtained by diagonalization. There is no known natural problem (say, from number theory or combinatorics) that would be computable in polynomial time, but provably required more than linear time.
• Also, the question itself assumes a reasonable computation model. For example, machines with an oracle containing $N(p)$ information for all primes $p$ will do much better on this particular problem, but will still polynomial-time compute the same things that a plain machine would. Sep 24, 2011 at 2:12