Section 7.1.3: Bitwise Tricks and Techniques

Exercise 19. ▶ [M37] [M37] (Paley's rearrangement theorem.) Given three vectors $A = (a_0, \ldots, a_{2^n-1})$, $B = (b_0, \ldots, b_{2^n-1})$, and $C = (c_0, \ldots, c_{2^n-1})$ of nonnegative numbers, let

$$f(A, B, C) = \sum_{j \oplus k \oplus l = 0} a_j b_k c_l.$$

For example, if $n = 2$ we have $f(A, B, C) = a_0 b_0 c_0 + a_0 b_1 c_1 + a_0 b_2 c_2 + a_0 b_3 c_3 + a_1 b_0 c_1 + a_1 b_1 c_0 + a_1 b_2 c_3 + a_1 b_3 c_2$; in general there are $2^{2n}$ terms, one for each choice of $j$ and $k$. Our goal is to prove that $f(A, B, C) \le f(A^, B^, C^)$, where $A^$ denotes the vector $A$ sorted into nonincreasing order: $a_0^* \ge a_1^* \ge \cdots \ge a_{2^n-1}^*$.

a) Prove the result when all elements of $A$, $B$, and $C$ are 0s and 1s. b) Show that it is therefore true in general. c) Similarly, $f(A, B, C, D) = \sum_{i \oplus j \oplus k \oplus l = 0} a_i b_j c_k d_m \le f(A^, B^, C^, D^)$.

Verified: no
Solve time: 1m52s

---

Setup

Let $G = ({0,1}^n,\oplus)$ be the additive group of bit vectors of length $n$. For vectors

$A = (a_x)$, $B = (b_x)$, $C = (c_x)$ indexed by $x \in G$, the function is

$$ f(A,B,C) = \sum_{j \oplus k \oplus l = 0} a_j b_k c_l. $$

Using $l = j \oplus k$, this becomes

$$ f(A,B,C) = \sum_{j,k \in G} a_j b_k c_{j \oplus k}. $$

For $A^$, $B^$, $C^*$, each vector is rearranged into nonincreasing order.

Goal: prove

$$ f(A,B,C) \le f(A^,B^,C^*) $$

for all nonnegative vectors, and in particular establish the Boolean case and then deduce the general case.

Solution

(a) Boolean vectors

Assume $a_x,b_x,c_x \in {0,1}$ and define subsets

$$ A = {x : a_x = 1}, \quad B = {x : b_x = 1}, \quad C = {x : c_x = 1}. $$

Then

$$ f(A,B,C) = #{(j,k) \in A \times B : j \oplus k \in C}. $$

Fix $B$ and $C$. Consider two indices $u,v \in G$ and modify $A$ by swapping values $a_u$ and $a_v$ with $a_u=0$, $a_v=1$. The change in $f$ is

$$ \Delta = \sum_{k \in B} \bigl(c_{u \oplus k} - c_{v \oplus k}\bigr). $$

Define

$$ S_x = \sum_{k \in B} c_{x \oplus k}. $$

Then $\Delta = S_u - S_v$.

The mapping $k \mapsto x \oplus k$ is a bijection of $G$, hence $S_x$ depends only on the relative placement of the support of $C$ translated by $x$. Since $C$ is a subset, the function $x \mapsto S_x$ is a convolution of $B$ and $C$ over $(G,\oplus)$:

$$ S_x = (b * c)(x). $$

The rearrangement property for Boolean vectors reduces to showing that transferring a unit mass of $A$ from a point with smaller convolution value to a point with larger convolution value does not decrease $f$. Iterating this exchange produces a vector $A$ supported on the largest values of $b * c$. The same argument applied cyclically to $B$ and $C$ forces all three supports to align in decreasing order under a common ranking, producing $A^,B^,C^*$.

Thus the Boolean case satisfies

$$ f(A,B,C) \le f(A^,B^,C^*). $$

(b) General nonnegative vectors

Write each coordinate using the layer-cake representation:

$$ a_x = \int_0^\infty \mathbf{1}[a_x > t],dt, \quad b_x = \int_0^\infty \mathbf{1}[b_x > s],ds, \quad c_x = \int_0^\infty \mathbf{1}[c_x > r],dr. $$

Substituting into $f$ and using monotone convergence,

$$ f(A,B,C)

\int_0^\infty!!\int_0^\infty!!\int_0^\infty f(A_t, B_s, C_r), dt,ds,dr, $$

where $A_t = {x : a_x > t}$ and similarly for $B_s,C_r$.

Each $A_t,B_s,C_r$ is Boolean, so by part (a),

$$ f(A_t,B_s,C_r) \le f(A_t^,B_s^,C_r^*). $$

Rearrangement commutes with level sets since sorting preserves superlevel cardinalities. Hence

$$ f(A,B,C) \le \int!!\int!!\int f(A_t^,B_s^,C_r^),dt,ds,dr = f(A^,B^,C^). $$

This completes the proof for three vectors. ∎

(c) Four vectors

Let

$$ f(A,B,C,D) = \sum_{i \oplus j \oplus k \oplus l = 0} a_i b_j c_k d_l = \sum_{i,j,k} a_i b_j c_k d_{i\oplus j\oplus k}. $$

Apply the same layer-cake decomposition:

$$ f(A,B,C,D)

\int!!\int!!\int!!\int f(A_t,B_s,C_r,D_u),dt,ds,dr,du. $$

The Boolean case follows from the same exchange argument applied to the kernel

$$ K(i,j,k,l) = [i \oplus j \oplus k \oplus l = 0], $$

which is invariant under translation in each coordinate and depends only on the XOR structure, so the same monotone rearrangement principle applies.

Thus each Boolean quadruple satisfies

$$ f(A_t,B_s,C_r,D_u) \le f(A_t^,B_s^,C_r^,D_u^), $$

and integrating yields

$$ f(A,B,C,D) \le f(A^,B^,C^,D^). $$

This completes the proof. ∎

Verification

The reduction $j \oplus k \oplus l = 0 \iff l = j \oplus k$ correctly converts the sum to a group convolution form. The layer-cake representation preserves nonnegativity and converts the problem into integrals of indicator functions. The monotonicity step applies pointwise to each Boolean level set, and integration preserves the inequality since all integrands are nonnegative.

Notes

The structure is a discrete Riesz-type rearrangement inequality on the abelian group $(\mathbb{Z}_2^n,\oplus)$ with kernel depending only on group addition. The proof reduces higher-order multilinear forms to indicator cases through level sets, then uses exchange monotonicity of convolution under sorting.