0
$\begingroup$

Assume we have a real multilinear polynomial $P : \mathbb{R}^n \rightarrow \mathbb{R}$ for which we know $|P(X_1,\dots,X_n)| \leq 1$ whenever $X_1, \dots, X_n \in \{-1,1\}$ (or even $X_1, \dots, X_n \in [-1,1]$). Here, "multilinear" means that each variable cannot be raised to a power greater than 1 in each monomial (for instance $4x_1x_2+x_2x_3$ is multilinear, but $4x_1x_2+x_2x_3^2$ not).

Let $Q$ be a polynomial obtained from $P$ by removing some of its monomials. I would like to prove $|Q(X_1,\dots,X_n)| \leq 1$ whenever $X_1, \dots, X_n \in \{-1,1\}$, or find a counterexample... We can assume that $P$ is homogeneous in a first time (all the monomials have the same degree).

More generally, I'm interested in any result that deals with "removing monomials from a polynomial" (does it have a name?)

$\endgroup$
  • $\begingroup$ By multilinear do you mean that $P$ has the form $P(x_1,\dots,x_n)=c_1x_1+\dots+c_nx_n$ for some $c_i\in\mathbb{R}$? $\endgroup$ – user2520938 Jan 4 '17 at 13:24
  • $\begingroup$ no, I mean that each variable cannot be raised to a power greater than 1 in each monomial. For instance, $4x_1x_2 + x_2x_3$ is multilinear, but $4x_1x_2 + x_2x_3^2$ is not. $\endgroup$ – permanganate Jan 4 '17 at 13:28
  • $\begingroup$ And you do not assume that $P$ is homogeneous I guess? $\endgroup$ – user2520938 Jan 4 '17 at 13:33
  • $\begingroup$ we can assume $P$ to be homogeneous in a first time :) $\endgroup$ – permanganate Jan 4 '17 at 13:34
  • $\begingroup$ ...and even $|P(X)| \leq 1$ for all $X \in [-1,1]^n$ (not just $\{-1,1\}^n$) $\endgroup$ – permanganate Jan 4 '17 at 15:07
1
$\begingroup$

I got a counterexample in case of non-homogeneous polynomials. Take $P=(X+Y+Z-XYZ)/2$ and $Q = (X+Y+Z)/2$. Then $P$ is bounded by $1$ on $\{-1,1\}^3$ but $Q(1,1,1) = 3/2 > 1$.

$\endgroup$
1
$\begingroup$

For a homogeneous counterexample, let

$$f(w,x,y,z) = \frac{wy}{2} + \frac{wz}{2} + \frac{xz}{2} - \frac{xy}{2}$$

$$g(w,x,y,z) = \frac{wz}{2} + \frac{xz}{2} - \frac{xy}{2}$$

Then $|f(w,x,y,z)| = 1$, for all $(w,x,y,z) \in \{-1,1\}^4$, but $g(1,1,-1,1) = 3/2$.

$\endgroup$

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.