86 Communication Complexity — Func Inner Product

86.1 Overview

This module establishes a discrepancy lower bound for the mod-2 inner product function $\mathrm{IP}_n : \{ 0,1\} ^n \times \{ 0,1\} ^n \to \{ 0,1\} $. It shows that every combinatorial rectangle has discrepancy at most $2^{-n/2}$ under the uniform distribution, and derives from this a public-coin communication complexity lower bound via the discrepancy method.

86.2 Declarations

Definition 86.1 Overlap of two bit-vectors

✓

Given two $n$-bit inputs $x, y : \mathrm{BoolInput}\, n$, $\mathrm{overlap}(x, y)$ is the Finset of coordinates $i \in \mathrm{Fin}\, n$ on which both $x$ and $y$ are true.

Definition 86.2 Mod-2 inner product

✓

$\mathrm{innerProduct}(n, x, y) : \mathrm{Bool}$ is the mod-2 inner product of two $n$-bit vectors $x$ and $y$: it returns true exactly when the number of coordinates where both inputs are true is odd, i.e. when $\bigoplus _{i=1}^{n} (x_i \wedge y_i) = 1$.

Lemma 86.3 Inner product with the zero vector is false

✓

For every $n$-bit Boolean vector $x \in \{ 0,1\} ^n$, the mod-$2$ inner product of $x$ with the all-zero vector $\mathbf{0}$ equals $\mathrm{false}$; that is, $\bigoplus _{i=1}^{n} (x_i \wedge 0) = 0$.

Lemma 86.4 Uniform mass of each Boolean input

✓

Let $n$ be a natural number, and regard the type of $n$-bit Boolean inputs $\mathrm{Fin}\, n \to \mathrm{Bool}$ as a finite probability space, with its associated probability mass function $p$. Then for every input $x$, the mass assigned to $x$, viewed as a real number, is

\[ p(x) = \frac{1}{2^{\, n}}. \]

Lemma 86.5 Integral as arithmetic average over Boolean inputs

✓

Let $f \colon \mathrm{BoolInput}\, n \to \mathbb {R}$ be any real-valued function on the $n$-bit Boolean inputs. Then, integrating $f$ against the uniform probability measure on the $2^n$ inputs,

\[ \int f \; =\; \frac{1}{2^n} \sum _{x} f(x), \]

so that the integral equals the arithmetic average of the values $f(x)$ taken over all $x \in \mathrm{BoolInput}\, n$.

Lemma 86.6 Flipping an active coordinate toggles the mod-2 inner product

✓

Let $x, y$ be $n$-bit Boolean inputs, and let $i$ be a coordinate at which $y_i = \mathtt{true}$. Write $\langle u, v\rangle = \bigoplus _{j} (u_j \wedge v_j)$ for the mod-2 inner product of two $n$-bit inputs, and let $x'$ denote the input agreeing with $x$ at every coordinate except $i$, where $x'_i = \lnot \, x_i$. Then

\[ \langle x', y\rangle = \langle x, y\rangle \oplus \mathtt{true}, \]

so negating the $i$-th coordinate of $x$ flips the value of the inner product.

Lemma 86.7 Vanishing Walsh character sum for a nonzero index

✓

Fix $n \in \mathbb {N}$, and let $z$ be an $n$-bit Boolean input that is $\mathrm{true}$ in at least one coordinate, say $z_i = \mathrm{true}$ for some index $i$. For a Boolean input $x$, write $\langle x, z\rangle = \bigoplus _{j} (x_j \wedge z_j)$ for their mod-2 inner product, and let $s(x) \in \{ \pm 1\} $ be the sign $+1$ when $\langle x, z\rangle $ is $\mathrm{false}$ and $-1$ when it is $\mathrm{true}$. Then summing this sign over all $2^n$ Boolean inputs $x$ gives

\[ \sum _{x} s(x) = 0. \]

Lemma 86.8 Character sum of the mod-2 inner product

✓

Fix a bit-string $z \in \{ 0,1\} ^n$, and for each $x \in \{ 0,1\} ^n$ let $\langle x, z\rangle \in \{ 0,1\} $ denote the mod-2 inner product of $x$ and $z$. Summing the Boolean sign $(-1)^{\langle x, z\rangle }$ over all $2^n$ inputs $x$ gives

\[ \sum _{x \in \{ 0,1\} ^n} (-1)^{\langle x, z\rangle } \; =\; \begin{cases} 2^n & \text{if $z$ is the all-zero string,} \\ 0 & \text{otherwise.} \end{cases} \]

Definition 86.9 Coordinatewise xor of Boolean inputs

✓

$\mathrm{xorInput}(y, z) : \mathrm{BoolInput}\, n$ is the coordinatewise XOR of $y$ and $z$: $(\mathrm{xorInput}(y, z))_i = y_i \oplus z_i$.

Lemma 86.10 Coordinatewise xor evaluated at a coordinate

✓

Let $y, z \colon \mathrm{Fin}\, n \to \mathrm{Bool}$ be two $n$-bit Boolean inputs, and let $i \in \mathrm{Fin}\, n$ be a coordinate. Then the $i$-th coordinate of their coordinatewise xor equals the xor of their individual $i$-th coordinates, namely $y_i \oplus z_i$.

Lemma 86.11 Coordinatewise xor vanishes exactly on equal inputs

✓

Let $y, z \in \mathbb {F}_2^n$ be two $n$-bit Boolean strings, and let $y \oplus z$ denote their coordinatewise xor, the string whose $i$-th bit is $y_i \oplus z_i$. Then $y \oplus z$ is the all-zero string if and only if $y = z$.

Lemma 86.12 Multiplicativity of the inner-product sign under coordinatewise XOR

✓

Fix $n \in \mathbb {N}$, and for $u,v \in \mathrm{BoolInput}\, n$ write $\langle u, v\rangle \in \mathrm{Bool}$ for the mod-$2$ inner product, and $s(b) \in \{ \pm 1\} $ for the Boolean sign of $b$ (so $s(\mathrm{false}) = 1$ and $s(\mathrm{true}) = -1$). Then for all $x, y, z \in \mathrm{BoolInput}\, n$,

\[ s\big(\langle x, y\rangle \big)\cdot s\big(\langle x, z\rangle \big) = s\big(\langle x,\, y \oplus z\rangle \big), \]

where $y \oplus z$ denotes the coordinatewise XOR of $y$ and $z$.

Lemma 86.13 Summed Walsh orthogonality for the mod-2 inner product

✓

Fix $n \in \mathbb {N}$. For a Boolean value $b$, let $\varepsilon (b) \in \{ \pm 1\} $ denote its Boolean sign, equal to $+1$ when $b$ is $\mathrm{false}$ and $-1$ when $b$ is $\mathrm{true}$; and for $n$-bit Boolean inputs $x, y$, let $\langle x, y\rangle $ denote their mod-2 inner product (which is $\mathrm{true}$ exactly when the number of coordinates $i$ with $x_i = y_i = \mathrm{true}$ is odd). Then for any two $n$-bit Boolean inputs $y$ and $z$,

\[ \sum _{x} \varepsilon \bigl(\langle x, y\rangle \bigr)\, \varepsilon \bigl(\langle x, z\rangle \bigr) = \begin{cases} 2^n & \text{if } y = z, \\ 0 & \text{if } y \neq z, \end{cases} \]

where the sum ranges over all $2^n$ Boolean inputs $x$.

Lemma 86.14 Idempotence of the 0–1 indicator function

✓

Let $B$ be a set of $n$-bit Boolean inputs, and let $\mathbf{1}_B \colon (\mathrm{Fin}\, n \to \mathrm{Bool}) \to \mathbb {R}$ be its indicator function, taking the value $1$ at points of $B$ and $0$ elsewhere. Then for every $n$-bit Boolean input $y$,

\[ \bigl(\mathbf{1}_B(y)\bigr)^2 = \mathbf{1}_B(y). \]

Lemma 86.15 Indicator function bounded by one

✓

Let $B \subseteq \mathrm{BoolInput}(n)$ be a set of $n$-bit Boolean inputs, and let $\mathbf{1}_B \colon \mathrm{BoolInput}(n) \to \mathbb {R}$ denote its indicator function, taking the value $1$ on $B$ and $0$ elsewhere. Then for every $y \in \mathrm{BoolInput}(n)$ one has $\mathbf{1}_B(y) \le 1$.

Lemma 86.16 Sum of squared row-sums as a sum over column pairs

✓

Let $\alpha $ and $\beta $ be finite types and let $f : \alpha \to \beta \to \mathbb {R}$. Then

\[ \sum _{x \in \alpha } \Bigl(\sum _{y \in \beta } f(x,y)\Bigr)^2 \; =\; \sum _{(y,z) \in \beta \times \beta } \; \sum _{x \in \alpha } f(x,y)\, f(x,z). \]

That is, squaring each row-sum of $f$ and summing over rows yields the same value as summing, over every ordered pair of columns $(y,z)$, the inner product of those two columns.

Lemma 86.17 Factoring scalars out of a sum of products

✓

Let $\alpha $ be a finite type, let $a, b \in \mathbb {R}$ be constants, and let $f, g : \alpha \to \mathbb {R}$ be functions. Then

\[ \sum _{x : \alpha } (a\, f(x))\, (b\, g(x)) \; =\; a\, b \sum _{x : \alpha } f(x)\, g(x). \]

Lemma 86.18 Diagonal collapse of an indexed sum

✓

Let $\alpha $ be a finite type with decidable equality, let $h \colon \alpha \times \alpha \to \mathbb {R}$ be any function, and let $c \in \mathbb {R}$. Summing $h(y,z)$ against the weight that equals $c$ when $y = z$ and $0$ otherwise, over all ordered pairs, leaves only the diagonal terms:

\[ \sum _{(y,z)\, \in \, \alpha \times \alpha } h(y,z)\cdot \bigl(\text{$c$ if $y = z$, else $0$}\bigr) \; =\; \sum _{y\, \in \, \alpha } h(y,y)\cdot c. \]

Lemma 86.19 Weighted orthogonality identity

✓

Let $\alpha $ and $\beta $ be finite index sets, and let $\phi : \alpha \times \beta \to \mathbb {R}$ be a real-valued array whose columns are mutually orthogonal with a common squared length: for a fixed constant $c \in \mathbb {R}$,

\[ \sum _{x \in \alpha } \phi (x,y)\, \phi (x,z) = \begin{cases} c & \text{if } y = z,\\ 0 & \text{if } y \neq z,\end{cases} \]

for all $y, z \in \beta $. Then for any weights $b : \beta \to \mathbb {R}$,

\[ \sum _{x \in \alpha } \Bigl(\sum _{y \in \beta } b(y)\, \phi (x,y)\Bigr)^{2} \; =\; c \sum _{y \in \beta } b(y)^{2}. \]

Lemma 86.20 Parseval identity for mod-2 inner-product characters

✓

Let $b$ be an arbitrary real-valued function on the set of $n$-bit Boolean inputs. For two such inputs $x,y$, write $\langle x,y\rangle = \sum _{i=1}^{n}(x_i \wedge y_i)$ for the number of coordinates on which both are true, so that $(-1)^{\langle x,y\rangle }$ is the sign of their mod-2 inner product, equal to $+1$ when $\langle x,y\rangle $ is even and $-1$ when it is odd. Then

\[ \sum _{x}\Bigl(\sum _{y} b(y)\, (-1)^{\langle x,y\rangle }\Bigr)^2 \; =\; 2^n \sum _{y} b(y)^2, \]

where both the inner and outer sums range over all $n$-bit Boolean inputs.

Lemma 86.21 A second-moment bound for character sums over a Boolean set

✓

Let $n \in \mathbb {N}$, and identify the set of $n$-bit Boolean inputs with $\{ 0,1\} ^n$. For $x, y \in \{ 0,1\} ^n$, write $\langle x, y\rangle = \bigoplus _{i=1}^{n} (x_i \wedge y_i) \in \{ 0,1\} $ for their mod-$2$ inner product, so that $(-1)^{\langle x, y\rangle }$ equals $+1$ when $\langle x, y\rangle = 0$ and $-1$ when $\langle x, y\rangle = 1$. Then for every subset $B \subseteq \{ 0,1\} ^n$,

\[ \sum _{x \in \{ 0,1\} ^n} \Bigl(\, \sum _{y \in B} (-1)^{\langle x, y\rangle } \Bigr)^{2} \; \le \; \bigl(2^{n}\bigr)^{2}. \]

Lemma 86.22 Second-moment bound for the sign-weighted inner-product average

✓

Let $B \subseteq \{ 0,1\} ^n$ be an arbitrary set of $n$-bit Boolean inputs, with indicator $\mathbf1_B$, and write $\langle x,y\rangle = \bigoplus _{i=1}^{n} (x_i \wedge y_i)$ for the mod-2 inner product of $x,y \in \{ 0,1\} ^n$. Taking $x$ and $y$ to range independently over $\{ 0,1\} ^n$ under the uniform probability measure,

\[ \int _{x}\left(\int _{y} \mathbf1_B(y)\, (-1)^{\langle x,y\rangle }\right)^{2} \; \le \; \frac{1}{2^{n}}. \]

Here $(-1)^{\langle x,y\rangle }$ is the $\pm 1$ value that is $-1$ when the inner product is $1$ and $+1$ when it is $0$; equivalently, the average over uniformly random $x$ of the square of the average over uniformly random $y$ of $\mathbf1_B(y)\, (-1)^{\langle x,y\rangle }$ is at most $2^{-n}$.

Lemma 86.23 Discrepancy of a rectangle as an iterated integral

✓

Fix $n$, work over the type $\mathrm{BoolInput}(n)$ of $n$-bit Boolean inputs equipped with a finite probability measure on the product $\mathrm{BoolInput}(n)\times \mathrm{BoolInput}(n)$, and let $\mathrm{IP}$ denote the mod-$2$ inner product. For any two subsets $A, B \subseteq \mathrm{BoolInput}(n)$, the discrepancy of $\mathrm{IP}$ on the combinatorial rectangle $A\times B$ factors as the iterated integral

\[ \mathrm{disc}\bigl(\mathrm{IP},\, A\times B\bigr) = \int _{x} \mathbf{1}_A(x)\left(\int _{y} \mathbf{1}_B(y)\, \sigma \bigl(\mathrm{IP}(x,y)\bigr)\right), \]

where $\mathbf{1}_A$ and $\mathbf{1}_B$ are the indicator functions of $A$ and $B$, and $\sigma $ is the Boolean sign map sending $\mathrm{false}\mapsto 1$ and $\mathrm{true}\mapsto -1$.

Lemma 86.24 Squared discrepancy of an inner-product rectangle

✓

Fix $n \in \mathbb {N}$ and equip the product $\mathrm{BoolInput}(n) \times \mathrm{BoolInput}(n)$ with its uniform probability measure. For any two sets $A, B \subseteq \mathrm{BoolInput}(n)$, the discrepancy of the mod-2 inner product $\mathrm{IP}_n$ over the combinatorial rectangle $A \times B$ satisfies

\[ \bigl(\mathrm{disc}(\mathrm{IP}_n,\, A \times B)\bigr)^2 \; \le \; \frac{1}{2^n}. \]

Theorem 86.25 Rectangle discrepancy bound for the inner product

✓

Fix a natural number $n$ and equip the set $\{ 0,1\} ^n \times \{ 0,1\} ^n$ of pairs of $n$-bit Boolean vectors with the uniform probability measure. Let $\mathrm{IP}_n(x,y) = \bigoplus _{i=1}^{n}(x_i \wedge y_i)$ be the mod-2 inner product. Then for every rectangle $R \subseteq \{ 0,1\} ^n \times \{ 0,1\} ^n$ — that is, every set of the form $R = A \times B$ with $A, B \subseteq \{ 0,1\} ^n$ — the discrepancy of $\mathrm{IP}_n$ on $R$ satisfies

\[ \bigl|\mathrm{disc}(\mathrm{IP}_n, R)\bigr| \; \le \; \sqrt{\frac{1}{2^{n}}}, \]

where the discrepancy is the expectation over a uniformly random pair $(x,y)$ of $\mathbf{1}_R(x,y)\, \sigma (\mathrm{IP}_n(x,y))$, with $\sigma $ the sign map sending $\mathrm{false} \mapsto 1$ and $\mathrm{true} \mapsto -1$.

Theorem 86.26 Public-coin lower bound for the inner product

✓

Let $k, n \in \mathbb {N}$ and let $\varepsilon \in \mathbb {R}$. If

\[ 2^{k}\, \sqrt{1/2^{n}} \; \lt \; 1 - 2\varepsilon , \]

then $k$ is strictly smaller than the $\varepsilon $-error public-coin randomized communication complexity of the mod-2 inner product function on $n$-bit inputs; that is, $k \lt \mathrm{R}^{\mathrm{pub}}_{\varepsilon }\! \bigl(\mathrm{IP}_{n}\bigr)$.