7
$\begingroup$

i couldn't find the answer to the following question:

The Isolation Lemma of Mulmuley, Vazirani and Vazirani uses the weight function $w:[n] \rightarrow [m]$ and assigns a subset $S \subseteq [n]$ the weight $w(S) = \sum_{x\in S} w(x)$, for $n,m \in \mathbb{N}$, where $w(x)$ are randomly chosen. The statement of the Lemma is, that for a family of subsets $S_i$ there is a subset $S_j$ that has a minimum weight and with probability $> 1-\frac{n}{m}$ it is unique. (Here $[n] := [1,...,n]$)

Is some generalization of the Isolation Lemma valid if the weight function maps to a Finite Field or even a Ring? For example if the weight function is changed to $w:[n] \rightarrow GF(2^q)$ or $w:[n] \rightarrow \mathbb{Z}_M$ for some integer $M$. Note that also the weight $w(S)$ of a subset is mapped to the Finite Field (or Ring). In this case there the notion of the "minimum weight" set is not well-defined because the elements of a field or ring are not ordered.

But are there conditions under which, say, there is at most one zero-sum subset with probability $> 1-\frac{n}{m}$?

Regards, Etsch

$\endgroup$
11
  • 2
    $\begingroup$ Finite fields or rings cannot be ordered. So how do you define minimal? $\endgroup$ Feb 14 at 20:52
  • $\begingroup$ Also, the URL is broken. $\endgroup$ Feb 14 at 20:54
  • $\begingroup$ Thx, i removed the link for now. Your comment i correct, i will rephrase the question - thx $\endgroup$
    – Etsch
    Feb 14 at 21:20
  • 2
    $\begingroup$ In general the answer to this is no. The Isolation Lemma holds even if all $2^n$ subsets are in the family, but in this case the average number of sets of a given weight is $2^n/m$. Consider the case when all $2^n$ sets are present and $w:[n]\to\mathbb Z_m$ with addition mod $m$. If the weights are randomly chosen as described, then by symmetry the expected number of weight-zero sets is $1+(2^n-1)/m$. Surely this number exceeds one probability more than $1-n/m$? (Will think about it.) $\endgroup$
    – Neal Young
    Feb 15 at 3:25
  • 1
    $\begingroup$ But if $m \ge 2^n$, instead of taking each weight $w(i)$ to be random, why not just take $w(i) = 2^{i-1}$? This guarantees that each set will have a unique weight. Maybe, to go any further with this inquiry, we would need to know more about the context / motivation. $\endgroup$
    – Neal Young
    Feb 16 at 21:21

2 Answers 2

6
$\begingroup$

Here is an alternative (and, hopefully, simpler) proof of Neal Young’s argument. To simplify the presentation, I take the set $\def\S{\mathcal S}\S$ of all $2^n-1$ nonempty subsets of $[n]$, and a uniformly random weight $w\colon[n]\to\def\z#1{\mathbb Z/#1\mathbb Z}\z m$ (the argument actually works for any abelian group of size $m$ just the same). I will prove

Theorem: With probability at least $1-4m^22^{-n}$, every weight in $\z m$ is attained by at least $\frac{2^n}{2m}$ sets.

For any $a\in\z m$, let $W_a$ denote the random variable $$\bigl|\{S\in\S:w(S)=a\}\bigr|,$$ and for $S\in\S$, let $W_{a,S}\in\{0,1\}$ be the indicator of $w(S)=a$, so that $$W_a=\sum_{S\in\S}W_{a,S}.$$ By fixing $w$ for all but one element of $S$, we see that $\DeclareMathOperator\E{E}\E W_{a,S}=\frac1m$, hence $$\E W_a=\frac{2^n-1}m.$$ Moreover, for fixed $a$, the variables $\{W_{a,S}:S\in\S\}$ are pairwise independent: given $S\ne S'$, fix (wlog) $i\in S'\let\bez\smallsetminus\bez S$. Then $w(S)$ is determined by $w\restriction([n]\bez\{i\})$, and it is $a$ with probability $1/m$, while conditioned on any fixed choice of $w\restriction([n]\bez\{i\})$, $w(S')=a$ with probability $1/m$. Thus, $$\DeclareMathOperator\var{var}\var W_a=\sum_{S\in\S}\var W_{a,S}=\frac{2^n-1}m\left(1-\frac1m\right).$$ By Chebyshev’s inequality, $$\Pr\left[W_a\le(2^n-1)\left(\frac1m-\delta\right)\right]\le\frac{\var W_a}{(2^n-1)^2\delta^2}=\frac{1-1/m}{(2^n-1)\delta^2m}\le\frac1{2^n\delta^2m}$$ as long as $m\le2^n$ (which we may assume as otherwise the statement of the theorem holds vacuously). By the union bound, $$\Pr\left[\forall a\in\z m\:W_a>(2^n-1)\left(\frac1m-\delta\right)\right]\ge1-\frac1{2^n\delta^2}.$$ Taking $\delta=1/(2m)$ gives the theorem.

$\endgroup$
3
  • $\begingroup$ Oh, very nice... FYI this variance bound can replace the use of Lemma 1 in the proof I gave, giving a tighter bound, but I think that even with that modification the bound that proof gives isn't as good as the bound your simpler proof gives. $\endgroup$
    – Neal Young
    Feb 17 at 20:37
  • $\begingroup$ All right, thank you. $\endgroup$ Feb 18 at 6:38
  • $\begingroup$ Thx Emil, i marked your answer as correct, since the proof is more comprehensible. Also thx to Neal for the first one. $\endgroup$
    – Etsch
    Feb 23 at 14:19
5
$\begingroup$

Here is a counter-example showing that at least when $\log m \ll n$ isolation is not possible: with high probability, every weight has exponentially many sets summing to it, so no particular set is "isolated" by its weight. (The example still leaves open the possibility that, say, the minimum-weight set could be likely to be isolated in the case that, say, $m \gg 2^n$.)

Take the set family to be all $2^n$ subsets of $[n]$. Take the weights to be in $\mathbb Z_m$ with addition mod $m$. (Typically one would take, say, $m=n^2$.) Let the element weights $w(x)$ $(x\in [n])$ be selected independently and uniformly at random from $\mathbb Z_m$. Recall that the weight of a given set $S\subseteq [n]$ is defined to be $w(S) = (\sum_{x\in S} w(x))\bmod m$.

Theorem 1. For every $k\ge 0$, with probability at least $1 - 1/2^k$, every weight $x$ in $\mathbb Z_m$ has at least $2^{n - O(k\log m)}$ sets $S$ with weight $w(S)=x$.

(No doubt the probability bound can be improved.)

Proof. For $t\ge 0$ and $x\in\mathbb Z_m$, define $C(t, x) = |\{S\subseteq [t] : w(S) = x\}|$ to be the number of weight-$x$ subsets of the first $t$ elements. So $C(0,0)=1$ (for the empty set), $C(0, x) = 0$ for $x\ne 0$, and for $t\ge 1$ and $x\in\mathbb Z_m$ $$C(t, x) = C(t-1, x) + C(t-1, x -_m w(t)),\hspace{1in}(1)\hspace{-1in}$$ where $-_m$ denotes subtraction mod $m$.

Define $m_t = |\{x\in\mathbb Z_m : C(t, x) \ge 1\}|$ to be the number of distinct set weights achieved by the end of round $t$. Let r.v. $T$ be the number of rounds until $m_T = m$, that is, $C(t, x)\ge 1$ for all $x\in\mathbb Z_m$. (Technically, in this definition we are imagining that the random experiment goes on indefinitely---more than $n$ rounds---adding a new random weight each time.)

Lemma 1. $E[T] \le 1+3\ln m$

Proof of Lemma 1. By (1), in each round $t \le T$, any given weight $x\not\in W_{t-1}$ enters $W_t$ if $x\in w(t) +_m W_{t-1}$, that is, $x -_m w(t) \in W_{t-1}$, which (given that $w(t)$ is random, so $x -_m w(t)$ is random, and $|W_{t-1}|=m_{t-1}$) happens with probability $m_{t-1}/m$. It follows that $$\textstyle E[m_t - m_{t-1} \,|\, m_{t-1}=i] = (m-m_{t-1})\frac{m_{t-1}}{m} = \frac{1}{1/m_{t-1} + 1/(m-m_{t-1})}.\hspace{.6in}(2)\hspace{-.6in} $$

For $j\le m$ define $\textstyle F(j) = \sum_{i=1}^j \frac{2}{i} + \frac{1}{\max(m-i, 1)}.$

Using the definition of $F$ and $m_{t-1} \le m_t \le 2 m_{t-1}$, we have $F(m_t)-F(m_{t-1})$ is at most $$\textstyle \sum_{i=m_{t-1}+1}^{m_{t}} \frac{2}{i} + \frac{1}{\max(m-i, 1)} \ge (m_{t} - m_{t-1})(\frac{2}{m_{t}} + \frac{1}{m-m_{t-1}} \ge (m_{t} - m_{t-1})(\frac{1}{m_{t-1}} + \frac{1}{m-m_{t-1}}), $$ which with (2) implies $E[F(m_t)-F(m_{t-1}) \,|\, m_{t-1}] \ge 1$. By Wald's equation, $$E[F(m_T)] \ge F(m_0) + E[T] = E[T].$$

This implies $E[T] \le E[F(m_T)] = F(m)$.

By calculation $F(m) = 2 H_m + H_{m-1} + 1 \le 1+3\ln m$.$~~~~\Box$

Let $B = 2+6\ln m$. By Lemma 1 and the Markov bound, the probability of the "bad" event $T \ge B$ is at most $1/2$. So, with probability at least $1/2$, the sets $S\subseteq [B]$ generate all $m$ weights. By applying the same argument to the sets $S\subseteq \{B+1,B+2,\ldots, 2B\}$, with probability at least $1/2$, those sets generate all $m$ weights. Likewise, partitioning the first $k B$ indices (in $[kB]$) into $k$ groups of size $B$, each group of sets generates all weights with probability at least $1/2$, so (using independence of the groups) the probability of the bad event that none of the group's sets generates all the weights is at most $1/2^k$. Assume this bad event does not happen. Then, at the start of round $t_0=kB$, we have $\min_x C(t, x) \ge 1 = 2^0$ for all $x$.

Then at the end of each round $t\ge t_0$, recalling (1), we have $$\min_x C(t, x) \ge 2\min_{x'} C(t-1, x'),$$ so inductively $\min_x C(t, x) \ge 2^{t-t_0}$. So, by the final round $t=n$ we have $$\min_x C(n, x) \ge 2^{n-t_0} = 2^{n-kB} = 2^{n-O(k \log m)}.~~~~~\Box$$

$\endgroup$

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.