# Interpolating Maximum function with symmetric polynomials

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$$.

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$$.
• 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. – Olivier Bégassat Apr 30 '19 at 14:42
• 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; – Olivier Bégassat Apr 30 '19 at 14:46