11
$\begingroup$

Given $p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]$ such that coefficients of $p,q$ are bounded by $B$, does $p\equiv q$ hold?

Schwartz-Zippel lemma applies here since it holds for general fields and $\Bbb Z\subset\Bbb Q$ and there is an efficient randomized algorithm for this problem.

We expect this problem to have efficient derandomization.

What is the consequence if this problem does not have an efficient derandomization?

$\endgroup$
  • 1
    $\begingroup$ How are $p$ and $q$ given? $\;$ $\endgroup$ – user6973 Sep 11 '15 at 3:40
  • $\begingroup$ @RickyDemer How is it given in regular polynomial identity testing? $\endgroup$ – user34945 Sep 11 '15 at 4:23
  • $\begingroup$ Doesn't the Kabanets-Impagliazzo result say that we DON'T expect an efficient derandomization ? $\endgroup$ – Suresh Venkat Sep 11 '15 at 5:52
  • 1
    $\begingroup$ Yes. $\:$ I figured I'd bring that up since with the standard representation, $\hspace{1.76 in}$ different strings represent distinct elements. $\;\;\;\;$ $\endgroup$ – user6973 Sep 11 '15 at 6:41
  • 3
    $\begingroup$ @SureshVenkat: Kabanets & Impagliazzo proved several things, including: 1. If PIT can be derandomized, either NEXP has no polysize (boolean) circuits or the permanent has no polysize (arithmetic) circuits; 2. If the permanent requires superpoly-size circuits, PIT can be "weakly" derandomized. Since the conclusions of 1. are generally conjectured to hold as well as the premise of 2., I would say contrary to you that KI result says that we DO expect an efficient derandomization. $\endgroup$ – Bruno Sep 11 '15 at 14:06
8
$\begingroup$

Since PIT is in $\mathsf{coRP}$, if there is no efficient derandomization then $\mathsf{P} \neq \mathsf{RP}$ (and, in particular, $\mathsf{P} \neq \mathsf{NP}$, but that's not so surprising, since we expect that to be true anyways). This also implies, of course, that $\mathsf{P} \neq \mathsf{BPP}$, so anything which implies $\mathsf{P} = \mathsf{BPP}$ becomes false. For example, sufficiently strong pseudorandom number generators do not exist, and $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$ would have subexponential size circuits!

$\endgroup$
  • $\begingroup$ So this holds irrespective of ground field (coefficients in $\Bbb Q_p$ where $p\in\{2,3,5,7,\dots\}\cup\{\infty\}$ with some bounds on coefficients)? $\endgroup$ – user34945 Sep 11 '15 at 20:39
  • $\begingroup$ Indeed, as you already pointed out Schwarz-Zippel-DeMillo-Lipton applies over arbitrary fields, and all it needs is a bound on the degree of the polynomials (not the size of coefficients nor the circuit size). With a very small number of exceptions, PIT typically means the degree-bounded version (degree bounded by a polynomial in the number of variables). $\endgroup$ – Joshua Grochow Sep 11 '15 at 21:00
  • $\begingroup$ May be a silly thing. You mentioned indepenence on size of coefficients and circuit size. I assumed size depends on degree and size of coeff. Am I wrong? $\endgroup$ – user34945 Sep 11 '15 at 21:17
  • 2
    $\begingroup$ Circuit size can depend on size of coeff., depending on your model (the model in which it does depend is usually called "constant-free"). Circuit size only depends very loosely on degree, in the sense that size is at least log of the degree, but really the coRP algorithm coming out of S-Z-D-L is just about degree. It doesn't even depend on the functions being given as circuits - just in some form in which they can be easily evaluated ("black-box"). $\endgroup$ – Joshua Grochow Sep 11 '15 at 21:51
  • $\begingroup$ Thank you. It is a little troubling that derandomization can be done without loss in efficiency even if the coefficients themselves can be constructively complicated $\endgroup$ – user34945 Sep 11 '15 at 21:54
0
$\begingroup$

You are wondering about big picture issues here. A natural number can canonically be represented in unary notation, but this representation is quite space inefficient. You could also represent it in binary notation, which is more space efficient, but no longer canonical, because you could also use tenary notation, or decimal notation. But notice that representation by circuits is not significantly less efficient than binary notation, see for example

101101 = (((1+1)*(1+1)+1)*(1+1)+1)*(1+1)*(1+1)+1

And notice that (...)*(1+1) can be replaced by x:=(...) in x+x, so you don't even need multiplication for this. But because you do have multiplication, you can even efficiently represent numbers like 1011^101101. Also note that you can efficiently add, subtract and multiply numbers in this representation. But this representation isn't limited to numbers, it even work exactly the same way for multivariate polynomial functions. And for polynomials, it is even a quite natural representation, because polynomials are the free algebra for commutative rings, and the representation as circuit can be used for any free algebra.

But let's get back to (natural) numbers for a moment, numbers like $c=10^{10^{10^{10^{10}}}}$. N J Wildberger has written some ultrafinitist rants, for example Set Theory: Should You Believe?. In the section But what about the natural numbers? the existence of numbers like $c$ is admitted, because you can obviously write them down. But the existence of nearly all natural numbers between $0$ and $c$ is denied, because most of those numbers would contain more information than could possibly be represented by the physical universe. Most of the rant just made me laugh, but this point got me thinking. Philosophers like Willard Van Orman Quine have protested against claiming the existence of unactualized possibles, among others because those lead to disorderly elements which cannot meaningfully be said to be identical with themselves and distinct from one another. So I found it quite reasonable to wonder about number presentations for which one still perform addition, subtraction and multiplication, and at least meaningfully determine whether two numbers are distinct from one another. The circuit representation achieves this...

Back to polynomials and circuit representations of free algebras. Here are some big picture questions:

  • Does this representation of a free algebra always allows efficient probabilistic identity testing, or is this limited to commutative rings?
    -> Identity testing is often even undecidable: For $n\geq 4$, the free modular lattice generated by $n$ elements is infinite and in fact has an undecidable word problem (Freese, Herrmann).
  • Is there a free algebra for which efficient deterministic identity testing would invalidate any commonly believed conjectures, like P!=NP?
    -> Yes, identity testing for the free algebra for regular commutative rings is NP-complete. Didn't noticed this for a long time, see below...
  • Would efficient deterministic identity testing for $\Bbb Z[x_1,\dots,x_n]$ (=the free algebra of commutative rings) invalidate any interesting conjectures?

I'm especially wondering about the free algebra for regular commutative rings here (i.e. rings with a generalized inverse operation), as they would allow to represent rational numbers and rational functions. Note that if we had used this representation only for numbers, then we might have wondered whether we can efficiently test a < b for this representation. This question doesn't make sense for the free commutative ring, but it could make sense for polynomials, if we interpret them in the context of free partially ordered rings. But a partially ordered ring is only a relational structure instead of an algebra, so this is a different kind of question...


Schwartz-Zippel lemma applies here since it holds for general fields and $\Bbb Z\subset\Bbb Q$ and there is an efficient randomized algorithm for this problem.

Well, it is true that Schwartz-Zippel lemma applies here, and that there is an efficient randomized algorithm for this problem, but these two facts are not directly related. Recall that it is easy to efficiently represent polynomials like $((3^3+3)^3+x)^3-((2^2+5)^3+x)^2x$ by a circuit. So if $n$ is the circuit size, then coefficient magnitudes of $7^{2^{n/2}}$, or $5^{3^{n/3}}$ are easy to achieve. That said, probabilistic polynomial identity testing still works over $\mathbb Z$. The bound on the coefficients is something like $B=\exp(\exp(n))$, and you just need to randomly guess a prime number which doesn't simultaneously divides all coefficients. Enough prime numbers of order $O(\log B)$ exists for doing this in an efficient probabilistic fashion.


I would find it quite surprising if PIT over $\Bbb Z[x_1,\dots,x_n]$ could be derandomized. But a similar surprise happened to me before, when primality testing was derandomized.

On the other hand, I also believe that you can just use any reasonable pseudorandom number generator and thereby decide PIT for all practical purposes, if you just test long enough. I only believe that you can never get rid of the remaining (infinitesimal small) doubt, similar to sets of measure zero, which remain annoying by not being empty.

$\endgroup$
  • $\begingroup$ you mean $P!=NP$? $\endgroup$ – user34945 Sep 13 '15 at 21:46
  • $\begingroup$ I am thinking of a free algebra issue only but not what you are thinking of $\endgroup$ – user34945 Sep 13 '15 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy