TCSLib

236 Boolean Analysis — Invariance — Coordinates

236.1 Overview

A multilinear polynomial splits into a part omitting a chosen coordinate and that coordinate times its derivative. Coefficient, influence, degree, and independence identities support coordinate replacement.

236.2 Declarations

Definition 236.1 Polynomial part omitting a coordinate
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). The coordinate-free part at \(i\) is the multilinear polynomial with coefficient \(0\) on sets containing \(i\) and coefficient \(a_S\) on every set \(S\) not containing \(i\).

Definition 236.2 Coefficient polynomial of a cube derivative
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). The coordinate derivative polynomial has, at each set \(S\), the Fourier coefficient indexed by \(S\) of the Boolean-cube derivative of \(F\) restricted to sign inputs.

Lemma 236.3 Coefficients of a coordinate derivative
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). The coefficient indexed by \(S\) in its coordinate derivative is \(0\) if \(i\in S\), and \(a_{S\cup \{ i\} }\) if \(i\notin S\).

Lemma 236.4 Degree reduction under coordinate differentiation
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). Define \(A_i(x)=\sum _{S:i\notin S}a_S\prod _{j\in S}x_j\) and \(D_i(x)=\sum _{S:i\notin S}a_{S\cup \{ i\} }\prod _{j\in S}x_j\). If \(F\) has degree at most \(k+1\), where \(k\ge 0\) is an integer, then \(D_i\) has degree at most \(k\).

Lemma 236.5 Cube evaluation of the derivative polynomial
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). On \(\{ -1,1\} ^n\), evaluation of its coordinate derivative polynomial equals the discrete derivative of the cube function \(F\), where the discrete derivative at \(i\) is \(\tfrac 12(F|_{x_i=1}-F|_{x_i=-1})\).

Lemma 236.6 Derivative coefficient energy equals influence
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). Define \(A_i(x)=\sum _{S:i\notin S}a_S\prod _{j\in S}x_j\) and \(D_i(x)=\sum _{S:i\notin S}a_{S\cup \{ i\} }\prod _{j\in S}x_j\). The sum of the squared coefficients of \(D_i\) is the influence of coordinate \(i\) on the uniform sign-cube function \(F\): \(\sum _{S:i\notin S}a_{S\cup \{ i\} }^2=I_i(F)=\sum _{S\ni i}a_S^2\).

Lemma 236.7 Evaluation over subsets omitting one coordinate
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). Let \(X_j\colon \Omega \to \mathbb R\) be arbitrary functions. For each \(\omega \in \Omega \), evaluation of the coordinate-free part of \(F\) on \(X(\omega )\) equals \(\sum _{S\subseteq \{ 1,\ldots ,n\} \setminus \{ i\} }a_S\prod _{j\in S}X_j(\omega )\).

Lemma 236.8 Derivative evaluation over the remaining inputs
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). Let \(X_j\colon \Omega \to \mathbb R\) be arbitrary functions. For each \(\omega \in \Omega \), evaluation of the coordinate derivative on \(X(\omega )\) equals \(\sum _{S\subseteq \{ 1,\ldots ,n\} \setminus \{ i\} }a_{S\cup \{ i\} }\prod _{j\in S}X_j(\omega )\).

Lemma 236.9 Affine decomposition at a coordinate
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). Define \(A_i(x)=\sum _{S:i\notin S}a_S\prod _{j\in S}x_j\) and \(D_i(x)=\sum _{S:i\notin S}a_{S\cup \{ i\} }\prod _{j\in S}x_j\). For any functions \(X_j\colon \Omega \to \mathbb R\) and \(\omega \in \Omega \), \(F(X(\omega ))=A_i(X(\omega ))+X_i(\omega )D_i(X(\omega ))\).

Lemma 236.10 Independence from the polynomial background
✓

Let \(F(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }a_S\prod _{j\in S}x_j\) be a real multilinear polynomial and fix \(i\in \{ 1,\ldots ,n\} \). Define \(A_i(x)=\sum _{S:i\notin S}a_S\prod _{j\in S}x_j\) and \(D_i(x)=\sum _{S:i\notin S}a_{S\cup \{ i\} }\prod _{j\in S}x_j\). If \((X_j)\) is an independent family of real functions on a measured space \((\Omega ,\mu )\) and each \(X_j\) is measurable up to a null set, then \(X_i\) is independent of the joint pair \((A_i(X),D_i(X))\).