Statement of the Goldwasser-Sipser Set Low Bound Protocol I'm trying to understand the statement of the Goldwasser-Sipser Set Low Bound Protocol as presented in &quot;Computational Complexity: A Modern Approach&quot; by Arora and Barak.
In particular, I'm trying to understand why the following claims yields what we would want:
$S \subseteq \{0,1\}^m$ is a set such that membership can be certified. Both parties know a number $K$. Let $k$ be an integer such that $2^{k-2} &lt; K \le 2^{k-1}$.
Claim: Let $S \subseteq \{0,1\}^m$ satisfy $|S| \le 2^{k}/2.$ Then for $p=|S|/2^k$ we have $p \ge \mathbf{P}_{h \in_{_R} \mathcal{H}_{m,k}, y \in_{_R} \{0,1\}^k}\left[\exists x \in S: h(x)=y \right] \ge \frac{3p}{4}-\frac{p}{2^k}.$
My understanding is that we want:

If $|S| \ge K$ then the verifier should accept (corresponding to the prover finding such an $x$ in the claim) with &quot;high&quot; probability;
If  $|S| \le K/2$ then the verifier will accept with probability at most 1/2.

I'm getting thrown off by a few things here:

the claim assumes that $|S| \le 2^k/2 = 2^{k-1} = 2\times2^{k-2} &lt; 2 K$, so how does this place us in one of the relevant cases?
How do we actually use those left ($p$) and right ($3p/4 - p/2^k$) bounds to conlude what we want?

Overall, I'm understand bits and pieces of this setup, but I'm having trouble seeing how it all fits together. Can someone walk through the logic/algebra here?
To succeed in distinguishing the case of $|S|\ge K$ from $|S|\le\frac{K}{2}$, you just need a constant gap (independent of $|S|$) in the acceptance probability in both cases. If you managed to achieve such a gap, then applying Chernoff to multiple executions of the protocol would achieve high success probability.
Observe that the interesting case is $k\le m$, since otherwise $K\ge 2^{k-2}\ge2^{m-2}$, and the verifier can convince himself that $|S|\ge K$ simply by sampling strings in $\{0,1\}^m$ uniformly at random and checking whether they belong to $S$ (in this case $|S|\ge K$ implies that the probability of falling in $S$ is at least $1/4$, so Chernoff with a polynomial number of samples yields the desired result). From now on assume $m\ge k$, and thus the hash functions are $h_{a,b}:GF(2^m)\rightarrow GF(2^k)$ given by $h_{a,b}=(ax+b)_{1...k}$, where $x_{1...k}$ in the truncation of a string obtained by taking the first $k$ bits.
For uniformly distributed $a,b\in GF(2^m)$, and every $x\in GF(2^m)$, $ax+b$ is uniformly distributed. This means that $\forall x\in GF(2^m): \Pr\limits_{\substack{a,b\in GF(2^m)\\y\in GF(2^k)}}\left[(ax+b)_{1...k}=y\right]=\frac{1}{2^k}$. We conclude that $\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\le \frac{|S|}{2^k}$. On the other hand, we can lower bound the same probability by:
$$
\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\ge\\
\sum\limits_{x\in S}\Pr\limits_{a,b,y}\left[h_{a,b}(x)=y\right]-\sum\limits_{x\neq x'\in S}\Pr\limits_{a,b,y}\left[h_{a,b}(x)=y \land h_{a,b}(x')=y\right]=\\\frac{|S|}{2^k}-\frac{}{}\binom{|S|}{2}\frac{1}{2^{2k}}\ge \frac{|S|}{2^k}\left(1-\frac{|S|}{2^{k+1}}\right).
$$
So far there were no restrictions on the size of $S$. Now, if $|S|\le K\le 2^{k-1}$ then $\frac{|S|}{2^k}\le\frac{1}{2}$, and we obtain $\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\ge \frac{3}{4}\frac{|S|}{2^k}$. We conclude that if $|S|=K$ then the probability of acceptance is at least $\frac{3}{4}\frac{K}{2^k}$ (the bound trivially holds for larger $|S|$, just by taking a subset of size $K$). If on the other hand $|S|\le K/2$ then the acceptance probability is at most $\frac{1}{2}\frac{K}{2^K}$ and we have our constant gap $\ge\frac{1}{4}\frac{K}{2^k}$, and Chernoff completes the proof.