4
$\begingroup$

This is a (self-contained) followup question to https://math.stackexchange.com/questions/380672/analogue-of-the-schwartz-zippel-lemma-for-subspaces.

Let $f : \mathbb{R}^n \to \mathbb{R}$ be a nonzero multivariate polynomial of total degree $d$ over a field $\mathbb{R}$, and $S \subset \mathbb{R}$ be finite. Pick a positive integer $k$, choose $y_1, \ldots, y_k$ randomly and uniformly from $S^n$, and consider the $k$-variable polynomial

$$g(t_1,\ldots,t_k) = f(t_1 y_1 + \cdots + t_k y_k)$$

We seek an upper bound on the probability that $g(t)$ is the zero polynomial. Setting $t_i = \delta_{ij}$ for each $j$ and applying the Schwartz-Zippel lemma, we have

$$\Pr(g(t)=0) \le \frac{d^k}{|S|^k}$$

However, this bound does not use the fact that we have an entire subspace on which to be nonzero.

Question 1: Is there a slightly stronger unconditional bound when $k > 1$?

My reason for hope here is that the Schwartz-Zippel bound is achieved by a univariate polynomial with $d$ distinct roots, but in the subspace case $g(t) = 0$ only if we pick the same root for all $y_i$, giving $$\Pr(g(t)=0) \le \frac{d}{|S|^k}$$ if $f(x)$ depends on only one variable. In this case, we might save up to a factor of $d^{k-1}$.

Question 2: Say $f(x)$ is irreducible over $\mathbb{R}$, and we condition on $y_i$ being full rank. Is there an even stronger bound when $d > 1$, ideally growing in strength with $n$?

Edit: Question 2 is false as stated, because $y_i$ might be full rank but lower rank when projected onto the variables on which $f(x)$ depends. I am still hoping it holds if a suitable "depends on all variables" condition is added, but am not sure how to phrase this.

$\endgroup$

1 Answer 1

5
+50
$\begingroup$

For question 1, I think it's enough to take a fixed $z$ that is transcendental over $\mathbb{Q}(S)$, and consider $$g(z,z^2,\dots,z^k)=f(zy_1+z^2y_2+\dots+z^k y_k).$$

Each coordinate of $zy_1+\dots+z^ky_k$ is independently uniform on $$S'=\{zs_1+\dots+z^k s_k \, | \, s_1, \dots, s_k \in S\},$$ so by Schwarz-Zippel we have $$P(g(z,z^2,\dots,z^k)=0) \leq \frac{d}{|S'|}=\frac{d}{|S|^k}$$

$\endgroup$
1
  • $\begingroup$ Thanks Kevin, that's a beautiful argument! As a bonus, it works over an arbitrary field as well by considering the field of rational functions $K(z)$. Question 2 is actually less important for my purposes, since in the corresponding code I have no way of guaranteeing linear independence. Having question 1 nailed down so simply is wonderful. $\endgroup$ Jun 18, 2014 at 21:30

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.