Let $n$ and $p$ be two positive integers. Consider the function $$\max_{n,p}:\{0,\dots,n\}^p\to\{0,\dots,n\}$$ that computes the maximum of a $p$-tuple of integers in the range $\{0,\dots,n\}$. Are there explicit expressions for symmetric polynomials $P_{n,p}\in\mathbb{Q}[\sigma_1,\dots,\sigma_p]$ such that $P_{n,p}(\sigma_1,\dots,\sigma_p)$ interpolates $\displaystyle\max_{n,p}$? Here the $\sigma_i$ are the elementary symmetric polynomials.

The case $p=2$ can be done by hand : $P_{n,2}(\sigma_1,\sigma_2)$ can be described by the formula $$\sum_{s=0}^{2n} \prod_{\substack{a=0\\a\neq s}} \frac{\sigma_1-a}{s-a} \cdot\left( \sum_{i=\max\{s-n,0\}}^{\lfloor s/2\rfloor} (s-i) \prod_{\substack{j=\max\{s-i,0\}\\j\neq i}}^{\lfloor s/2\rfloor} \frac{\sigma_2-j(s-j)}{i(s-i)-j(s-j)} \right)$$ Which you obtain by interpolating the maximum functions along the ``antidiagonals'' $x+y=s$, $0\leq x,y\leq n$.

As far as I can tell, the result from Interpolation for Symmetric Functions is inapplicable here.

I'm interested in this question to study networks. The special case where $n=p=2^N$ is of particular interest to me. Furthermore, I want to allow more invariant polynomials, specifically those that are invariant under a 2-Sylow group of $\mathfrak{S}_n$.


1 Answer 1


The following would be proof of existence of such polynomial rather then actual construction (and it's a generalization of your approach).

Define $S_i$ as a set of all possible values $\sigma_i(a)$ for $a\in\{0,1,\ldots, n\}^p$ and define $A=\{0,1\ldots, n\}^p$ Consider any $p$-tuple $a=(a_1, a_2, \ldots, a_p)\in A$ and define a polynomial $L_a\in\mathbb{Q}[\sigma_1,\sigma_2,\ldots,\sigma_p]$ as follows $$ L_a=\prod_{i=1}^{p}\prod_{t_i\in S_i\backslash\{s_i\}}\frac{\sigma_i-t_i}{s_i-t_i}, $$ where $s_i=\sigma_i(a_1, a_2, \ldots, a_p)$ ($L_a$ is well-defined due to Vieta's theorem). The main property of $L_a$ is that $L_a(a)=1$ and $L_a(b)=0$ for any $p$-tuple $b\in A\backslash \{a\}$.

Now, we can define $$ P_{n,p}=\sum_{a\in A}\max\{a_1, a_2, \ldots, a_p\}\cdot L_a. $$ Clearly, $P_{n,p}\in \mathbb{Q}[\sigma_1,\sigma_2,\ldots,\sigma_p]$ and $P_{n,p}(a)=\max\{a_1, a_2, \ldots, a_p\}$ for any $a\in A$.

  • $\begingroup$ Thank you for your answer. Indeed, that works :) and generalizes my own approach. Ideally I would like something "explicit" (the aim is to plug in special random variables and to compute the expectation). But there might be no ``better'' formula. $\endgroup$ Apr 30, 2019 at 14:42
  • 1
    $\begingroup$ The question of existence needs no proof : just take any multivariate polynomial that interpolates the max function, and average it over the symmetric group. The resulting polynomial is symmetrical (and thus a polynomial in the $\sigma_i$) interpolates the max function; $\endgroup$ Apr 30, 2019 at 14:46
  • $\begingroup$ Yes, indeed, existence is trivial. $\endgroup$
    – richrow
    Apr 30, 2019 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.