3
$\begingroup$

I would like to construct (or determine the existence/inexistence) of a polynomial $p(x_1,...,x_k, y_1,...,y_n)$ satisfying the following properties:

  1. $p$ is symmetric with relation to the variables $x_1,...,x_k$, in the sense that swapping any two of these variables do not alter the polynomial. Observe that for the variables $y_i$ no symmetry condition is imposed.
  2. $p$ has degree at most $k-1$.
  3. each variable in $\{x_1,...,x_k,y_1,...,y_n\}$ appears in at most $k-2$ monomials.
  4. $p$ is connected. By connectedness I mean that the graph whose vertices are monomials, and whose edges connect monomials having a common variable, is connected.

My question is: Given $k\in \mathbb{N}$, does such a polynomial $p(x_1,...,x_k,y_1,...,y_n)$ exists? Here the number $n$ of $y$ variables can be as large as needed.

Observation: The problem becomes trivial if any of the conditions above are removed. In particular no y variable is needed in this case.

  1. If p is not required to be connected, just take the polynomial $p=x_1+ x_2 + ... + x_k$
  2. If p can have degree k, then just take $p= x_1x_2...x_k$
  3. If a variable can appear in k-1 monomials, then take the polynomial $p=\sum_{i\neq j} x_1x_j$.

I would appreciate any proof of existence/inexistence of such polynomials, or a construction. References dealing with polynomials that are symmetric only in some variables are also welcome.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

There are none.

Write it in the monomial basis with respect to $x_1,\ldots,x_k$, with coefficients being polynomials in $y_1,\ldots,y_n$. The only monomial basis functions with $k$ variables such that each variable occurs in at most $k-2$ terms are 1, $x_1^s+\cdots+x_k^s$ for $s\ge 1$, and $x_1^t x_2^t\cdots x_k^t$ for $t\ge 1$. (Because: if a monomial has $r$ variables there are at least $\binom kr$ similar monomials and each $x_j$ appears in at least $\frac kr \binom kr =\binom{k-1}{r-1}$ of them, which is more than $k-2$ unless $r\in\lbrace 0,1,k\rbrace$.) The function $x_1^t x_2^t\cdots x_k^t$ has too high a degree, so the only chances have the form $$p(\mathbf{x},\mathbf{y}) = r(\mathbf{y}) + \sum_s q_s(\mathbf{y})(x_1^s+\cdots+x_k^s).$$ We must have $q_s(\mathbf{y})$ independent of $\mathbf{y}$ (i.e. constant) for each $s$, or else some $y_j$ occurs in at least $k$ monomials. But then $p$ is disconnected.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.