# Lower bound of disjointness by discrepancy?

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.

• Can you add an image of that exercise to the question? I would like to double check if my understanding is correct. – John L. Apr 24 '19 at 21:42
• The exercise is only a single line without any further descriptions: Just Prove $Disc_\mu(Disj) \geq 1/(2n+1)$ for any distribution $\mu$. But $Disc_\mu$, $Disj$ and $\mu$ are all defined somewhere before. I went over your answer (took me some time) and it absolutely makes sense for me, everything you have described. Thank you very much! – cz5 Apr 25 '19 at 16:36

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.

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