Lower bound of disjointness by discrepancy?

Question

I need to show that $Disc_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \{0,1\}^n \times \{0,1\}^n \to [0,1]$. Disjointness is defined as

$Disj(X,Y)=\left\{ \begin{array}[ll]+1 & \text{if $X \cap Y = \emptyset$} \\ 0 & \text{otherwise}\end{array}\right.$

The discrepancy for a function is defined as $Disc_\mu(f) = \max_R \{Disc_\mu(R,f)\}$ over all rectangles $R$ and further

$$Disc_\mu(R,f) = |\Pr_\mu [(x,y) \in R \wedge f(x,y)=1] - \Pr_\mu[(x,y) \in R \wedge f(x,y) =0] |.$$

I don't understand where the $\frac{1}{2n+1}$ comes from and how to define a proper rectangle $R$.

The problem is given as an exercise without a solution in the book Communication Complexity by E. Kushilevitz and N. Nisan on page 40.

Answer 1

Let me clarify the question first.

• $\mu$ is a probability distribution over the sample space $S=\{0,1\}^n \times \{0,1\}^n$.
• A combinatorial rectangle (or just rectangle) $R$ is a subset of $S$ of the form $A\times B$, where $A\subseteq \{0,1\}^n$ and $B\subseteq \{0,1\}^n$.
• For all $x\in \{0,1\}^n$, we can think of $x$ as the characteristic vector of a subset of $\{1, \cdots, n\}$. That is, $x=(x_1, x_2, \cdots, x_n)$ where $x_i=1$ if and only if $i$ is in that subset. We may abuse $x$ to mean that subset.
• We define $Disj(x, y) = 1$ for $x,y\in \{0,1\}^n$ if and only if the subset $x$ and the subset $y$ are disjoint. ($Disj(x, y) = 0$ if and only if they are not disjoint.)

---

For the sake of contradiction, suppose that $Disc_\mu(Disj) < \frac{1}{2n+1}$.

So, $Disc_\mu(S,Disj) = \left|\Pr_\mu [Disj(x,y)=1] - \Pr_\mu[Disj(x,y) =0] \right| < \frac{1}{2n+1}\tag{1},$ and $Disc_\mu(R_i,Disj) \lt \frac{1}{2n+1}\tag{2},$ where $R_i=X_i\times X_i$, $X_i$ is the set of all $x\in \{0,1\}^n$ that are subsets of $\{1, \cdots, n\}$ that contain $i$.

Since $Disj(x,y)=1$ means $x,y\in X_i$ for some $i$, $$\begin{aligned}\Pr_\mu [Disj(x,y)=1] &\le\sum_{i=1}^n\Pr_\mu [(x,y)\in X_i\times X_i]\\ &=\sum_{i=1}^n\left|\Pr_\mu[(x,y) \in R_i \wedge Disj(x,y)=1] - \Pr_\mu[(x,y) \in R_i \wedge Disj(x,y) =0] \right|\\ &=\sum_{i=1}^n Disc_\mu(R_i,Disj) \lt \frac{n}{2n+1} \end{aligned}$$

Combining the inequality (1), we know that $$\Pr_\mu [Disj(x,y)=0] \lt \frac {n+1}{2n+1}.$$

So $\Pr_\mu [Disj(x,y)=1] + \Pr_\mu[Disj(x,y) =0] <1$. However, the left hand side should be 1 since $Disj(x,y)$ is either 1 or 0. That is a contradiction. QED.

Answer 2

You asked two questions. I'll answer the second. A rectangle is a set $R$ of the form

$$R = \{(x_1,\dots,x_n) : \ell_1 \le x_1 \le u_1, \dots, \ell_n \le x_n \le u_n\}$$

for some $\ell_1,\dots,\ell_n,u_1,\dots,u_n$.