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](http://www.math.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf) (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. $$



Orthogonal basis for the multilinear polynomials with zero "trace"
The basis appears in Murali K. Srinivasan's paper Symmetric chains, [Gelfand-Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme](http://arxiv.org/abs/1001.0280), though perhaps not as explicitly. The author shows that it is the canonically defined symmetric Gelfand–Tsetlin basis (up to scaling), as well as the one constructed by the de Bruijn–Tengbergen–Kruyswijk algorithm.


