An Almost Orthogonal Basis of Inner Product Polynomials

Abstract

Consider drawing i.i.d. $n$-dimensional standard Gaussian vectors $d_i$. We study functions of the $d_i$ which are rotationally invariant, i.e. they only depend on the pairwise angles and norms of the $d_i$, such as $$E[ \langle d_1,d_2 \rangle \cdot \langle d_2,d_3 \rangle \cdot \langle d_3,d_4 \rangle \cdot \langle d_4,d_1 \rangle ]$$ Some beautiful combinatorics arises based on the topology of the underlying graph. With the intent of doing Fourier analysis, we give an (almost) orthogonal basis for this space. We also study the cases of Boolean and spherical $d_i$; when the d_i are spherical instead of Gaussian, interesting examples suggest a connection to graph planarity. Based on joint work with Aaron Potechin.