89 Communication Complexity — Func Inner Product

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

89.2 Declarations

Definition 89.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 89.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 89.3 Inner product with the zero vector is false

✓

For every \(x : \mathrm{BoolInput}\, n\), the inner product of \(x\) with the all-zero input is false: \(\mathrm{innerProduct}(n, x, \mathbf{0}) = \mathtt{false}\).

Lemma 89.4 Uniform weight of each Boolean input

✓

Every element \(x : \mathrm{BoolInput}\, n\) has PMF weight \(2^{-n}\) under the uniform distribution: \(\mathrm{toPMF}(\mathrm{BoolInput}\, n,\, x) = 2^{-n}\).

Lemma 89.5 Integral as arithmetic average

✓

For any \(f : \mathrm{BoolInput}\, n \to \mathbb {R}\), the integral against the uniform distribution satisfies

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

Lemma 89.6 Flipping a set coordinate toggles the inner product

✓

If \(y_i = \mathtt{true}\), then flipping coordinate \(i\) of \(x\) toggles the inner product: \(\mathrm{innerProduct}(n, \mathrm{flipAt}(i, x), y) = \mathrm{innerProduct}(n, x, y) \oplus \mathtt{true}\).

Lemma 89.7 Walsh character sums to zero when \(z \ne \mathbf{0}\)

✓

If \(z : \mathrm{BoolInput}\, n\) has a coordinate \(i\) with \(z_i = \mathtt{true}\), then

\[ \sum _{x : \mathrm{BoolInput}\, n} \mathrm{boolSign}(\mathrm{innerProduct}(n, x, z)) = 0. \]

This is the orthogonality of Walsh characters for the inner product function.

Lemma 89.8 Walsh character sum is an indicator at the zero vector

✓

For every \(z : \mathrm{BoolInput}\, n\),

\[ \sum _{x : \mathrm{BoolInput}\, n} \mathrm{boolSign}(\mathrm{innerProduct}(n, x, z)) \; =\; \begin{cases} 2^n & \text{if } z = \mathbf{0}, \\ 0 & \text{otherwise.} \end{cases} \]

Definition 89.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 89.10 Pointwise evaluation of xorInput

✓

For all \(y, z : \mathrm{BoolInput}\, n\) and \(i : \mathrm{Fin}\, n\), \(\mathrm{xorInput}(y, z)(i) = y_i \oplus z_i\).

Lemma 89.11 xorInput equals zero iff inputs are equal

✓

\(\mathrm{xorInput}(y, z) = \mathbf{0}\) if and only if \(y = z\).

Lemma 89.12 Walsh character multiplicativity under xor

✓

For all \(x, y, z : \mathrm{BoolInput}\, n\),

\[ \mathrm{boolSign}(\mathrm{IP}(x, y)) \cdot \mathrm{boolSign}(\mathrm{IP}(x, z)) = \mathrm{boolSign}(\mathrm{IP}(x,\, y \oplus z)). \]

The Walsh character for the inner product is multiplicative in its second argument under coordinatewise XOR.

Lemma 89.13 Summed Walsh orthogonality for inner product

✓

For all \(y, z : \mathrm{BoolInput}\, n\),

\[ \sum _{x : \mathrm{BoolInput}\, n} \mathrm{boolSign}(\mathrm{IP}(x, y)) \cdot \mathrm{boolSign}(\mathrm{IP}(x, z)) \; =\; \begin{cases} 2^n & \text{if } y = z, \\ 0 & \text{otherwise.} \end{cases} \]

Lemma 89.14 Indicator function squared equals itself

✓

For any set \(B \subseteq \mathrm{BoolInput}\, n\) and \(y : \mathrm{BoolInput}\, n\), the indicator function satisfies \((\mathbf{1}_B(y))^2 = \mathbf{1}_B(y)\).

Lemma 89.15 Indicator function is at most one

✓

For any set \(B \subseteq \mathrm{BoolInput}\, n\) and \(y : \mathrm{BoolInput}\, n\), \(\mathbf{1}_B(y) \le 1\).

Lemma 89.16 Sum of squares equals sum over pairs

✓

For finite types \(\alpha \) and \(\beta \) and \(f : \alpha \to \beta \to \mathbb {R}\),

\[ \sum _{x : \alpha } \Bigl(\sum _{y : \beta } f(x, y)\Bigr)^2 \; =\; \sum _{(y_1, y_2) : \beta \times \beta } \sum _{x : \alpha } f(x, y_1) \cdot f(x, y_2). \]

Lemma 89.17 Scalar factoring in a double sum

✓

For a finite type \(\alpha \) and constants \(a, b \in \mathbb {R}\) and functions \(f, g : \alpha \to \mathbb {R}\),

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

Lemma 89.18 Diagonal reduction for ite sums

✓

For a finite type \(\alpha \) with decidable equality, a function \(h : \alpha \to \alpha \to \mathbb {R}\), and a scalar \(c \in \mathbb {R}\),

\[ \sum _{(y_1, y_2) : \alpha \times \alpha } h(y_1, y_2) \cdot [\! [y_1 = y_2]\! ] \cdot c \; =\; \sum _{y : \alpha } h(y, y) \cdot c, \]

where \([\! [\cdot ]\! ]\) denotes the indicator of the condition.

Lemma 89.19 Weighted orthogonality identity

✓

Let \(\phi : \alpha \to \beta \to \mathbb {R}\) be a family of functions satisfying the orthogonality condition \(\sum _{x:\alpha } \phi (x,y)\, \phi (x,z) = c \cdot [\! [y=z]\! ]\) for a constant \(c\). Then for any weights \(b : \beta \to \mathbb {R}\),

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

Lemma 89.20 Parseval identity for inner product Walsh characters

✓

For any \(b : \mathrm{BoolInput}\, n \to \mathbb {R}\),

\[ \sum _{x : \mathrm{BoolInput}\, n} \Bigl(\sum _{y : \mathrm{BoolInput}\, n} b(y)\, \mathrm{boolSign}(\mathrm{IP}(x,y))\Bigr)^2 \; =\; \sum _{y : \mathrm{BoolInput}\, n} b(y)^2 \cdot 2^n. \]

Lemma 89.21 Second moment of indicator-weighted Walsh sum is bounded

✓

For any set \(B \subseteq \mathrm{BoolInput}\, n\),

\[ \sum _{x : \mathrm{BoolInput}\, n} \Bigl(\sum _{y : \mathrm{BoolInput}\, n} \mathbf{1}_B(y)\, \mathrm{boolSign}(\mathrm{IP}(x,y))\Bigr)^2 \; \le \; (2^n)^2. \]

Lemma 89.22 Integral second moment bound for discrepancy computation

✓

For any set \(B \subseteq \mathrm{BoolInput}\, n\),

\[ \int _{x} \Bigl(\int _{y} \mathbf{1}_B(y)\, \mathrm{boolSign}(\mathrm{IP}(x,y))\Bigr)^2 \; \le \; \frac{1}{2^n}. \]

This is the key second-moment estimate used in the discrepancy bound.

Lemma 89.23 Discrepancy of a rectangle as a product integral

✓

For sets \(A, B \subseteq \mathrm{BoolInput}\, n\), the discrepancy of the rectangle \(A \times B\) for the inner product function equals

\[ \mathrm{disc}(\mathrm{IP}, A \times B) = \int _x \mathbf{1}_A(x) \int _y \mathbf{1}_B(y)\, \mathrm{boolSign}(\mathrm{IP}(x,y)). \]

Lemma 89.24 Squared discrepancy of a rectangle is at most \(2^{-n}\)

✓

For all \(A, B \subseteq \mathrm{BoolInput}\, n\),

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

Theorem 89.25 Rectangle discrepancy bound for inner product

✓

Every combinatorial rectangle \(R \subseteq \mathrm{BoolInput}\, n \times \mathrm{BoolInput}\, n\) has discrepancy at most \(2^{-n/2}\) for the mod-2 inner product function under the uniform distribution:

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

Theorem 89.26 Public-coin lower bound for inner product

✓

If \(k, n \in \mathbb {N}\) and \(\varepsilon \in \mathbb {R}\) satisfy \(2^k \cdot \sqrt{1/2^n} \lt 1 - 2\varepsilon \), then

\[ k \; \lt \; \mathrm{CC}_{\varepsilon }^{\mathrm{pub}}(\mathrm{IP}_n), \]

providing a public-coin communication complexity lower bound for the inner product function via the discrepancy method.