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$ Commented Jun 18, 2014 at 21:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .