# Stronger version(2) of Isolation Lemma for linear forms

Klivans and Spielman give isolation lemma for linear forms in their paper Randomness Efficient Identity Testing of Multivariate Polynomials. Lemma 4 in this paper says.

"Let $C$ be any collection of distinct linear forms in variables $z_1\ldots z_l$ with coefficients in range {$0,\ldots, K$}. If $z_1,\ldots,z_l$ are independently chosen uniformly at random from set $S = \{0\ldots Kl/\epsilon\}$, then with probability greater than 1-$\epsilon$, there is a unique form of minimal value at $z_1,\ldots,z_l$".

Is there a stronger version of this lemma? Namely, can we choose set $S$ to be of size sublinear in $K$? Assume that $l$ is small compared to $K$.

Let me introduce a different notion of "stronger". Suresh Chari, Pankaj Rohatgi and Aravind Srinivasan give Generalized isolating lemma in their paper Randomness-Optimal Unique Element Isolation, With Applications to Perfect Matching and Related Problems. Lemma 2[Generalized isolating lemma] in this paper says

Let ($S$, $\mathcal{F}$) be any set system and let $Z$ be a give upper bound on the size of unknown family $\mathcal{F}$. There is a simple scheme which uses $O(\log Z + \log N)$ random weights to assign integer weights to the $x_i$'s in the range $[0,N^7)$ such that with probability atleast $\frac{1}{4}$, there is a unique minimum weight set in $\mathcal{F}$. Here $S=\{x_1,x_2,\ldots x_N\}$ and $\mathcal{F}\subset2^S$.

Do we have something similar for isolating linear forms? Namely, if we know that number of linear forms is bounded by $Z$, can we reduce random bits as compared to $O(N\log(KN))$ random bits used in Randomness Efficient Identity Testing of Multivariate Polynomials. We also want that weights should not be too large, again weights sublinear in $K$ should be interesting.

• First part of question has been solved by domotorp. But I think it's still interesting to reduce number of bits when we know that number of linear forms is bounded by some $Z$. May 29 '13 at 16:02

For your first question, if $l=1$, then $\frac{K^\frac 23}\epsilon$ is sufficient. This follows the fact that the lower envelope of some lines has the same complexity as the upper convex hull of its dual point system and if you have a convex polygon with integer vertices in $[0,K]^2$, then it can have at most $O(K^\frac 23)$ sides. I know I did not explain the details, but this is anyhow only a partial answer to your question...
• Nice observation! In fact, plugging this directly into Klivans and Spielman's proof reduces their bound from $Kl/\epsilon$ to $O(K^{2/3}l/\epsilon)$. May 24 '13 at 22:01
• Then up to the $l$ factor, this is best possible, as the above also gives a construction with $\Omega(K^\frac 23/\epsilon)$ non-unique minimal values. May 26 '13 at 5:05
• I can give you the proof instead. Suppose it has $8K^\frac 23$ sides. Direct them clockwise. Each becomes a vector from $[-K,K]^2$ and each vector can occur at most once. In one of the quadrants, say $[0,K]^2$, there are at least $2K^\frac 23$ vectors. At most $K^\frac 23$ of these are in $[0,K^\frac 13]^2$. The rest are either long in the $x$-direction or in the $y$-direction. But having $\frac 12 K^\frac 23$ vectors of length $\ge K^\frac 13$ pushes us out from [0,K]. May 28 '13 at 14:58