# Orthogonal basis for the multilinear polynomials with zero “trace”

We say that a multilinear polynomial $P(x_1,\ldots,x_n)$ in $n$ commuting variables over $\mathbb{R}$ has zero trace if $$\frac{d}{dt} P(t,\ldots,t) = 0.$$ Equivalently, $$\left(\sum_{i=1}^n \frac{\partial}{\partial x_i}\right) P = 0.$$ (Suggestions for a better name are welcome.)

Such functions come up, for example, when considering the Johnson association scheme: every function on $\binom{[n]}{k} = \{(x_1,\ldots,x_n\}) \in \{0,1\}^n : \sum_i x_i = k\}$ can be represented as a zero trace multilinear polynomial of degree at most $k$ (assuming $k \leq n/2$); see Bannai and Ito, Association schemes, Proposition III.2.7.

For $d \leq n/2$, the dimension of the linear space of all zero trace multilinear polynomials of degree at most $d$ is $\binom{n}{d}$.

Are there known orthogonal bases for the linear span of all zero-trace multilinear polynomials in $n$ variables of degree at most $n/2$?

Orthogonality is with respect to the uniform measure on $\binom{[n]}{k}$, though the orthogonal basis proposed below is orthogonal with respect to any measure which is permutation-invariant.

Is the following orthogonal basis known?

Here is a conjectured orthogonal basis which can be gleaned from Young's orthogonal representation of $S_n$. Given two sequences $A = a_1,\ldots,a_d$ and $B = b_1,\ldots,b_d$ of distinct numbers in $[n]$, we say that $A < B$ if $A$ and $B$ are disjoint and $a_i < b_i$ for all $i$. We say that a sequence $B$ is a top set if $B$ is increasing and there exists a sequence $A$ smaller than $B$. It turns out that there are $\binom{n}{d} - \binom{n}{d-1}$ top sets of size $d$, a fact mentioned by Frankl and Graham (this can be proved using Bertrand's ballot problem). For each top set $B$ of size $d$ there is a basis vector $$\sum_{A < B} \prod_{i=1}^d (x_{a_i} - x_{b_i}).$$ For example, for $d=1$ the $n-1$ basis vectors are $$\sum_{i=1}^{b-1} (x_i - x_b), \quad 2 \leq b \leq n.$$

• Very nice question! But I think you mean Young's natural, not orthogonal representation. – darij grinberg May 9 '14 at 14:13
• @darij I obtained the basis by taking the double cosets corresponding to $\binom{[n]}{k}$, computing Young's orthogonal representation, summing all rows (or all columns), and normalizing to remove all the square roots. I'm not sure that's the same as what you'd get from Young's natural representation, but I didn't check. – Yuval Filmus May 9 '14 at 21:35
• I am a bit puzzled: in your last example, are your basis vectors multilinear in any conventional sense? It looks like the $b$-th vector is of degree $b-1$ in $x_b$. – Vladimir Dotsenko Feb 3 '15 at 14:03
• @VladimirDotsenko They are multilinear in the sense that the square of a variable never appears. It's a summation $\sum$ rather than a product $\prod$. The first few vectors are $x_1-x_2$, $x_1+x_2-2x_3$, $x_1+x_2+x_3-3x_4$, and so on. Looks pretty multilinear to me. Moreover, for given $d$, the basis function is a homogeneous degree $d$ polynomial, so in this example, everything is a (homogeneous) linear polynomial. – Yuval Filmus Feb 3 '15 at 15:21
• @VladimirDotsenko It's available here: cs.toronto.edu/~yuvalf/WimmerFriedgut.pdf. – Yuval Filmus Feb 4 '15 at 16:31