<p>Here is a counter-example showing that at least when <span class="math-container">$\log m \ll n$</span> isolation is not possible: with high probability, <em>every</em> weight has exponentially many sets summing to it, so no particular set is &quot;isolated&quot; 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, <span class="math-container">$m \gg 2^n$</span>.)</p>
<p>Take the set family to be all <span class="math-container">$2^n$</span> subsets of <span class="math-container">$[n]$</span>.  Take the weights to be in <span class="math-container">$\mathbb Z_m$</span> with addition mod <span class="math-container">$m$</span>. (Typically one would take, say, <span class="math-container">$m=n^2$</span>.)  Let the element weights <span class="math-container">$w(x)$</span> <span class="math-container">$(x\in [n])$</span> be selected independently and uniformly at random from <span class="math-container">$\mathbb Z_m$</span>.  Recall that the weight of a given set <span class="math-container">$S\subseteq [n]$</span> is defined to be <span class="math-container">$w(S) = (\sum_{x\in S} w(x))\bmod m$</span>.</p>
<p><strong>Theorem 1.</strong> <em>For every <span class="math-container">$k\ge 0$</span>, with probability at least <span class="math-container">$1 - 1/2^k$</span>, every weight <span class="math-container">$x$</span> in <span class="math-container">$\mathbb Z_m$</span>
has at least <span class="math-container">$2^{n - O(k\log m)}$</span> sets <span class="math-container">$S$</span> with weight <span class="math-container">$w(S)=x$</span>.</em></p>
<p>(No doubt the probability bound can be improved.)</p>
<p><em>Proof.</em> For <span class="math-container">$t\ge 0$</span> and <span class="math-container">$x\in\mathbb Z_m$</span>, define <span class="math-container">$C(t, x) = |\{S\subseteq [t] : w(S) = x\}|$</span> to be the number of weight-<span class="math-container">$x$</span> subsets of the first <span class="math-container">$t$</span> elements.
So <span class="math-container">$C(0,0)=1$</span> (for the empty set), <span class="math-container">$C(0, x) = 0$</span> for <span class="math-container">$x\ne 0$</span>,
and for <span class="math-container">$t\ge 1$</span> and <span class="math-container">$x\in\mathbb Z_m$</span>
<span class="math-container">$$C(t, x) = C(t-1, x) + C(t-1, x -_m w(t)),\hspace{1in}(1)\hspace{-1in}$$</span>
where <span class="math-container">$-_m$</span> denotes subtraction mod <span class="math-container">$m$</span>.</p>
<p>Define <span class="math-container">$m_t = |\{x\in\mathbb Z_m : C(t, x) \ge 1\}|$</span> to be the number of distinct set weights achieved by the end of round <span class="math-container">$t$</span>. Let r.v. <span class="math-container">$T$</span> be the number of rounds until <span class="math-container">$m_T = m$</span>, that is, <span class="math-container">$C(t, x)\ge 1$</span> for all <span class="math-container">$x\in\mathbb Z_m$</span>.
(Technically, in this definition we are imagining that the random experiment goes on indefinitely---more than <span class="math-container">$n$</span> rounds---adding a new random weight each time.)</p>
<p><strong>Lemma 1.</strong> <span class="math-container">$E[T] \le 1+3\ln m$</span></p>
<p><em>Proof of Lemma 1.</em>  By (1), in each round <span class="math-container">$t \le T$</span>, any given weight <span class="math-container">$x\not\in W_{t-1}$</span> enters <span class="math-container">$W_t$</span> if <span class="math-container">$x\in w(t) +_m W_{t-1}$</span>, that is, <span class="math-container">$x -_m w(t) \in W_{t-1}$</span>,
which (given that <span class="math-container">$w(t)$</span> is random, so <span class="math-container">$x -_m w(t)$</span> is random, and <span class="math-container">$|W_{t-1}|=m_{t-1}$</span>) happens with probability <span class="math-container">$m_{t-1}/m$</span>.  It follows that
<span class="math-container">$$\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}
$$</span></p>
<p>For <span class="math-container">$j\le m$</span> define
<span class="math-container">$\textstyle F(j) =  \sum_{i=1}^j \frac{2}{i} + \frac{1}{\max(m-i, 1)}.$</span></p>
<p>Using the definition of <span class="math-container">$F$</span> and <span class="math-container">$m_{t-1} \le m_t \le 2 m_{t-1}$</span>, we have <span class="math-container">$F(m_t)-F(m_{t-1})$</span> is at most
<span class="math-container">$$\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}}),
$$</span>
which with (2) implies <span class="math-container">$E[F(m_t)-F(m_{t-1}) \,|\, m_{t-1}] \ge 1$</span>.
By Wald's equation, <span class="math-container">$$E[F(m_T)] \ge F(m_0) + E[T] = E[T].$$</span></p>
<p>This implies <span class="math-container">$E[T] \le E[F(m_T)] = F(m)$</span>.</p>
<p>By calculation <span class="math-container">$F(m) = 2 H_m + H_{m-1} + 1 \le 1+3\ln m$</span>.<span class="math-container">$~~~~\Box$</span></p>
<p>Let <span class="math-container">$B = 2+6\ln m$</span>.
By Lemma 1 and the Markov bound, the probability of the &quot;bad&quot; event <span class="math-container">$T \ge B$</span> is at most <span class="math-container">$1/2$</span>.
So, with probability at least <span class="math-container">$1/2$</span>, the sets <span class="math-container">$S\subseteq [B]$</span> generate all <span class="math-container">$m$</span> weights.
By applying the same argument to the sets <span class="math-container">$S\subseteq \{B+1,B+2,\ldots, 2B\}$</span>, with probability at least <span class="math-container">$1/2$</span>, those sets generate all <span class="math-container">$m$</span> weights.
Likewise, partitioning the first <span class="math-container">$k B$</span> indices (in <span class="math-container">$[kB]$</span>) into <span class="math-container">$k$</span> groups of size <span class="math-container">$B$</span>,
each group of sets generates all weights with probability at least <span class="math-container">$1/2$</span>,
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 <span class="math-container">$1/2^k$</span>.
Assume this bad event does not happen.
Then, at the start of round <span class="math-container">$t_0=kB$</span>,
we have <span class="math-container">$\min_x C(t, x) \ge 1 = 2^0$</span> for all <span class="math-container">$x$</span>.</p>
<p>Then at the end of each round <span class="math-container">$t\ge t_0$</span>, recalling (1), we have <span class="math-container">$$\min_x C(t, x) \ge 2\min_{x'} C(t-1, x'),$$</span>
so inductively <span class="math-container">$\min_x C(t, x) \ge 2^{t-t_0}$</span>.
So, by the final round <span class="math-container">$t=n$</span> we have
<span class="math-container">$$\min_x C(n, x) \ge 2^{n-t_0} = 2^{n-kB} = 2^{n-O(k \log m)}.~~~~~\Box$$</span></p>

CC BY-SA 4.0
2022-02-16T18:02:12.667Z
2022-02-16T21:27:44.863Z
2022-02-16T21:27:44.863Z
Neal Young
<p>Here is an alternative (and, hopefully, simpler) proof of Neal Young’s argument. To simplify the presentation, I take the set <span class="math-container">$\def\S{\mathcal S}\S$</span> of all <span class="math-container">$2^n-1$</span> <em>nonempty</em> subsets of <span class="math-container">$[n]$</span>, and a uniformly random weight <span class="math-container">$w\colon[n]\to\def\z#1{\mathbb Z/#1\mathbb Z}\z m$</span> (the argument actually works for any abelian group of size <span class="math-container">$m$</span> just the same). I will prove</p>
<blockquote>
<p><strong>Theorem:</strong> With probability at least <span class="math-container">$1-4m^22^{-n}$</span>, every weight in <span class="math-container">$\z m$</span> is attained by at least <span class="math-container">$\frac{2^n}{2m}$</span> sets.</p>
</blockquote>
<p>For any <span class="math-container">$a\in\z m$</span>, let <span class="math-container">$W_a$</span> denote the random variable
<span class="math-container">$$\bigl|\{S\in\S:w(S)=a\}\bigr|,$$</span>
and for <span class="math-container">$S\in\S$</span>, let <span class="math-container">$W_{a,S}\in\{0,1\}$</span> be the indicator of <span class="math-container">$w(S)=a$</span>, so that
<span class="math-container">$$W_a=\sum_{S\in\S}W_{a,S}.$$</span>
By fixing <span class="math-container">$w$</span> for all but one element of <span class="math-container">$S$</span>, we see that
<span class="math-container">$\DeclareMathOperator\E{E}\E W_{a,S}=\frac1m$</span>, hence
<span class="math-container">$$\E W_a=\frac{2^n-1}m.$$</span>
Moreover, for fixed <span class="math-container">$a$</span>, the variables <span class="math-container">$\{W_{a,S}:S\in\S\}$</span> are pairwise independent: given <span class="math-container">$S\ne S'$</span>, fix (wlog) <span class="math-container">$i\in S'\let\bez\smallsetminus\bez S$</span>. Then <span class="math-container">$w(S)$</span> is determined by <span class="math-container">$w\restriction([n]\bez\{i\})$</span>, and it is <span class="math-container">$a$</span> with probability <span class="math-container">$1/m$</span>, while conditioned on any fixed choice of <span class="math-container">$w\restriction([n]\bez\{i\})$</span>, <span class="math-container">$w(S')=a$</span> with probability <span class="math-container">$1/m$</span>. Thus,
<span class="math-container">$$\DeclareMathOperator\var{var}\var W_a=\sum_{S\in\S}\var W_{a,S}=\frac{2^n-1}m\left(1-\frac1m\right).$$</span>
By Chebyshev’s inequality,
<span class="math-container">$$\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}$$</span>
as long as <span class="math-container">$m\le2^n$</span> (which we may assume as otherwise the statement of the theorem holds vacuously). By the union bound,
<span class="math-container">$$\Pr\left[\forall a\in\z m\:W_a&gt;(2^n-1)\left(\frac1m-\delta\right)\right]\ge1-\frac1{2^n\delta^2}.$$</span>
Taking <span class="math-container">$\delta=1/(2m)$</span> gives the theorem.</p>

CC BY-SA 4.0
2022-02-17T20:37:49.907Z
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.
Neal Young
CC BY-SA 4.0
2022-02-18T06:38:56.267Z
All right, thank you.
Emil Jeřábek
CC BY-SA 4.0
2022-02-23T14:19:17.627Z
Thx Emil, i marked your answer as correct, since the proof is more comprehensible. Also thx to Neal for the first one.
Etsch
CC BY-SA 4.0
2022-02-17T09:17:14.770Z
2022-02-17T14:11:34.563Z
2022-02-17T14:11:34.563Z
Emil Jeřábek
<p>i couldn't find the answer to the following question:</p>
<p>The <a href="https://en.wikipedia.org/wiki/Isolation_lemma" rel="nofollow noreferrer">Isolation Lemma</a> of Mulmuley, Vazirani and Vazirani uses the weight function <span class="math-container">$w:[n] \rightarrow [m]$</span> and assigns a subset <span class="math-container">$S \subseteq [n]$</span> the weight <span class="math-container">$w(S) = \sum_{x\in S} w(x)$</span>, for <span class="math-container">$n,m \in \mathbb{N}$</span>, where <span class="math-container">$w(x)$</span> are randomly chosen. The statement of the Lemma is, that for a family of subsets <span class="math-container">$S_i$</span> there is a subset <span class="math-container">$S_j$</span> that has a minimum weight and with probability <span class="math-container">$&gt; 1-\frac{n}{m}$</span> it is unique. (Here <span class="math-container">$[n] := [1,...,n]$</span>)</p>
<p>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 <span class="math-container">$w:[n] \rightarrow GF(2^q)$</span> or <span class="math-container">$w:[n] \rightarrow \mathbb{Z}_M$</span> for some integer <span class="math-container">$M$</span>. Note that also the weight <span class="math-container">$w(S)$</span> of a subset is mapped to the Finite Field (or Ring).  In this case there the notion of the &quot;minimum weight&quot; set is not well-defined because the elements of a field or ring are not ordered.</p>
<p>But are there conditions under which, say, there is at most one <em>zero-sum</em> subset with probability <span class="math-container">$&gt; 1-\frac{n}{m}$</span>?</p>
<p>Regards,
Etsch</p>

CC BY-SA 4.0
2022-02-14T20:52:30.177Z
Finite fields or rings cannot be ordered. So how do you define *minimal*?
Emil Jeřábek
CC BY-SA 4.0
2022-02-14T20:54:48.120Z
Also, the URL is broken.
Emil Jeřábek
CC BY-SA 4.0
2022-02-14T21:20:06.003Z
Thx, i removed the link for now. Your comment i correct, i will rephrase the question - thx
Etsch
CC BY-SA 4.0
2022-02-15T03:25:23.453Z
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.)
Neal Young
CC BY-SA 4.0
2022-02-16T08:16:13.850Z
Yes, this is right Neal, i came up with something similar. I dont think the Isolation Lemma can be extendet this way. Maybe because i am still dont know how to define mimimal as Emil has noted - except focusing directly on the zero-sum subset. Thx
Etsch
CC BY-SA 4.0
2022-02-16T19:58:37.060Z
Why not just take an arbitrary total order over the finite field and require the weight to be the minimal with respect to that order? Neal's argument would still give a counterexample if the finite field is small, but if it is larger than $2^n$, maybe the lemma might work?
Or Meir
CC BY-SA 4.0
2022-02-16T20:46:34.053Z
@OrMeir The original isolation lemma over $\mathbb Z$ does not work if you replace the standard order with an arbitrary order; it essentially relies on the fact that addition is increasing. Why would you expect the case of finite fields to be any better?
Emil Jeřábek
CC BY-SA 4.0
2022-02-16T21:14:58.277Z
I added an answer that shows that as long as $\log m \ll n$ there is no hope --- all sets will have exponentially many sets with the same weight.  In the case that $m \gg 2^{2n}$, with high probability *every* set will a unique weight (this is essentially the birthday paradox).  In the intermediate case $2^n \ll m \ll 2^{2n}$ many but not all sets will have unique weights, so there are certainly pre-determined rules that will select such a set... maybe the minimum-weight set is one?
Neal Young
CC BY-SA 4.0
2022-02-16T21:21:56.153Z
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.
Neal Young
CC BY-SA 4.0
2022-02-17T07:37:26.997Z
Yes, with probability at least $1-\frac{3^n}m$ or so, the weights of all the sets will be pairwise different, and this holds over any ring. however, this is an exponentially worse bound than the actual isolation lemma, and I doubt it is useful for similar purposes.
Emil Jeřábek
CC BY-SA 4.0
2022-02-17T15:28:13.120Z
The case $m \geq 2^n$ is indeed not of interest. But the idea to take $w(i) = 2^{i-1}$ is actually a nice idea of independent interest. I am still reading the answers below, they look promising. Thx
Etsch
<pr.probability>
Isolation Lemma over finite fields
Etsch
# Isolation Lemma over finite fields

(Asked by: username_0 on 2022-02-14)

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

The [Isolation Lemma](https://en.wikipedia.org/wiki/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

**Tags:** pr.probability
> **Comments:**
> **username_1**: Finite fields or rings cannot be ordered. So how do you define *minimal*?  
> **username_1**: Also, the URL is broken.  
> **username_0**: Thx, i removed the link for now. Your comment i correct, i will rephrase the question - thx  
> **username_2**: 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.)  
> **username_0**: Yes, this is right Neal, i came up with something similar. I dont think the Isolation Lemma can be extendet this way. Maybe because i am still dont know how to define mimimal as Emil has noted - except focusing directly on the zero-sum subset. Thx  
> **username_3**: Why not just take an arbitrary total order over the finite field and require the weight to be the minimal with respect to that order? Neal's argument would still give a counterexample if the finite field is small, but if it is larger than $2^n$, maybe the lemma might work?  
> **username_1**: @OrMeir The original isolation lemma over $\mathbb Z$ does not work if you replace the standard order with an arbitrary order; it essentially relies on the fact that addition is increasing. Why would you expect the case of finite fields to be any better?  
> **username_2**: I added an answer that shows that as long as $\log m \ll n$ there is no hope --- all sets will have exponentially many sets with the same weight.  In the case that $m \gg 2^{2n}$, with high probability *every* set will a unique weight (this is essentially the birthday paradox).  In the intermediate case $2^n \ll m \ll 2^{2n}$ many but not all sets will have unique weights, so there are certainly pre-determined rules that will select such a set... maybe the minimum-weight set is one?  
> **username_2**: 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.  
> **username_1**: Yes, with probability at least $1-\frac{3^n}m$ or so, the weights of all the sets will be pairwise different, and this holds over any ring. however, this is an exponentially worse bound than the actual isolation lemma, and I doubt it is useful for similar purposes.  
> **username_0**: The case $m \geq 2^n$ is indeed not of interest. But the idea to take $w(i) = 2^{i-1}$ is actually a nice idea of independent interest. I am still reading the answers below, they look promising. Thx  

---

## 2 answers

### Answer by username_1 on 2022-02-17. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: All right, thank you.  
> **username_0**: Thx Emil, i marked your answer as correct, since the proof is more comprehensible. Also thx to Neal for the first one.  

---

### Answer by username_2 on 2022-02-16. Score: 5

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$$


---

