Given $m,n\in\Bbb Z_{>1}$ is there a way to quantify smallest degree (when exists) $f(x)\in\Bbb Z_m[x]$ with $f(q)\bmod m\equiv1\iff q<n\mbox{ is prime }$ and is $deg(f(x))=O(\log(mn))$?

Prime detection has a polynomial size circuit because of the existence of a polynomial time algorithm.

The open problem here is 'Can prime detection have a polynomial size formula?'.

$m=O(n^c)$ and $deg(f(x))=O((\log(mn))^c)$ will give a polynomial size formula and $c=1$ gives a linear size formula.


migrated from mathoverflow.net Nov 17 '17 at 4:36

This question came from our site for professional mathematicians.

  • 2
    $\begingroup$ Surely if $m=n$ and $n$ is prime then the minimum degree is $\pi(n-1)\sim n/\log(n)$. $\endgroup$ – Neil Strickland Oct 27 '17 at 9:52
  • $\begingroup$ @NeilStrickland Sure bound is true? $\endgroup$ – T.... Oct 27 '17 at 15:48
  • $\begingroup$ What you state looks like upper bound. Why does the minimum degree have to follow prime number theorem? $\endgroup$ – T.... Oct 28 '17 at 10:39

If $m$ is a prime, then the integers mod $m$ form a field and the fundamental theorem of algebra holds: to have $\pi(n-1)$ roots, you need to have degree $\pi(n-1)$. So $O(\log(mn))$ cannot hold in general.

  • $\begingroup$ actually degree $\pi(n-1)$ also can have poly size formula if polynomial is sparse or has a highly non-trivial internal structure. $\endgroup$ – T.... Nov 12 '17 at 22:25
  • 1
    $\begingroup$ @Turbo You changed the question with your recent edits. I was addressing only your original question. If you'd like an answer to the new question, it should be posted as a separate question. $\endgroup$ – Charles Nov 12 '17 at 22:33
  • $\begingroup$ a poly size formula? $\endgroup$ – T.... Nov 12 '17 at 22:48

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.