Skip to main content
added 9 characters in body
Source Link
S.J.
  • 21
  • 3

The answer is no, not in general.

I am going to assume $f$ and $g$ are supermodular, real polynomials. I'll discuss what needs to happen for their product to be supermodular and then construct a counter example.

1.) $f$ and $g$ must have mixed terms or else they violate supermodularity as stated in your question.

Proving this fact amounts to showing that $ (x'^n + y'^n) + (x^n + y^n) \ngtr (x'^n + y^n) + (x^n + y'^n) $.

2.) If this property holds, then it must hold at zero. So consider $f(x, y) + f(0, 0) > f(x, 0) + f(y, 0)$. Because I am assuming these are polynomials, cancellation of terms leaves us with the expression $$axy + bx^2y + cxy^2 + dx^2y^2 + \ldots > 0$$ where $a, b, c, \ldots$ are the (possibly zero) coefficients of the mixed terms of $f$.

3.) Should $f*g$ satisfy supermodularity, then it must for $(x, y) > (0, 0).$ Therefore, $$f(x, y)g(x, y) + f(0, 0) g(0, 0) > f(x, 0) g(x, 0) + f(0, y)g(0, y)$$ should hold true.

The left-hand side contains the product of two polynomials plus the product of their constant terms. The right-hand side contains the product of the $x$-terms (including the constant) of $f$ and $g$ plus the product of the $y$-terms (including the constant) of $f$ and $g$.

The inequality rests on what happens with the cross-terms of $f(x, y)g(x, y)$. I am going to denote the mixed terms of $f$ as $m(f)$ and the remaining terms as $p(f) = p_x(f) + p_y(f) + p_c(f)$ for the $x$-only terms, $y$-only terms, and the constant term (respectively). So $f(x, y) = m(f) + p_x(f) + p_y(f) + p_c(f)$.

To clarify what I said earlier, the inequality is true so long as $$m(f)m(g) + m(f)p(g) + p(f)m(g) + \big[p_x(f)[p_y(g) + p_c(g)] + p_y(f)[p_x(g) + p_c(g)] + p_c(f)[p_x(g) + p_y(g)]\big] >0.$$ Call the mixed terms $\varphi(x, y)$. Then this expression simplifies to $$m(g)m(f) [p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)}] >0.$$ We know from (2) that $m(f)$ and $m(g)$ are both greater than 0. Is it not necessarily true, however, that $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} >0$.

So a counter example just needs to satisfy $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} \leq 0$. Here is one such example:

Let $$f(x, y) = -x + xy - y \quad \text{ and } \quad g(x, y) = x + xy + y$$

One can verify that both $f$ and $g$ satisfy supermodularity. Now, consider the product:

$$f(x, y)*g(x, y) = -x^2 - 2xy + x^2 y^2 - y^2$$

If this satisfied supermodularity, then for $x>0$ and $y>0$, you get

$$-x^2 - 2xy + x^2 y^2 - y^2 > -x^2 - y^2$$

which implies $$- 2xy + x^2 y^2 > 0$$ or $$xy - 2 >0$$

This is clearly false if $x = 1>0$ and $y=1>0$.

Notice that this relates to the discussion above. For this case $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} = 0 + \frac{-2(xy)}{(xy)^2} = \frac{-2}{xy} < 0$ for any $x, y > 0$.

Therefore the product of two supermodular functions is not necessarily supermodular.

The answer is no, not in general.

I am going to assume $f$ and $g$ are supermodular, real polynomials. I'll discuss what needs to happen for their product to be supermodular and then construct a counter example.

1.) $f$ and $g$ must have mixed terms or else they violate supermodularity as stated in your question.

Proving this fact amounts to showing that $ (x'^n + y'^n) + (x^n + y^n) \ngtr (x'^n + y^n) + (x^n + y'^n) $.

2.) If this property holds, then it must hold at zero. So consider $f(x, y) + f(0, 0) > f(x, 0) + f(y, 0)$. Because I am assuming these are polynomials, cancellation of terms leaves us with the expression $$axy + bx^2y + cxy^2 + dx^2y^2 + \ldots > 0$$ where $a, b, c, \ldots$ are the (possibly zero) coefficients of the mixed terms of $f$.

3.) Should $f*g$ satisfy supermodularity, then it must for $(x, y) > (0, 0).$ Therefore, $$f(x, y)g(x, y) + f(0, 0) g(0, 0) > f(x, 0) g(x, 0) + f(0, y)g(0, y)$$ should hold true.

The left-hand side contains the product of two polynomials plus the product of their constant terms. The right-hand side contains the product of the $x$-terms (including the constant) of $f$ and $g$ plus the product of the $y$-terms (including the constant) of $f$ and $g$.

The inequality rests on what happens with the cross-terms of $f(x, y)g(x, y)$. I am going to denote the mixed terms of $f$ as $m(f)$ and the remaining terms as $p(f) = p_x(f) + p_y(f) + p_c(f)$ for the $x$-only terms, $y$-only terms, and the constant term (respectively). So $f(x, y) = m(f) + p_x(f) + p_y(f) + p_c(f)$.

To clarify what I said earlier, the inequality is true so long as $$m(f)m(g) + m(f)p(g) + p(f)m(g) + \big[p_x(f)[p_y(g) + p_c(g)] + p_y(f)[p_x(g) + p_c(g)] + p_c(f)[p_x(g) + p_y(g)]\big] >0.$$ Call the mixed terms $\varphi(x, y)$. Then this expression simplifies to $$m(g)m(f) [p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)}] >0.$$ We know from (2) $m(f)$ and $m(g)$ are both greater than 0. Is it necessarily true, however, that $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} >0$.

So a counter example just needs to satisfy $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} \leq 0$. Here is one such example:

Let $$f(x, y) = -x + xy - y \quad \text{ and } \quad g(x, y) = x + xy + y$$

One can verify that both $f$ and $g$ satisfy supermodularity. Now, consider the product:

$$f(x, y)*g(x, y) = -x^2 - 2xy + x^2 y^2 - y^2$$

If this satisfied supermodularity, then for $x>0$ and $y>0$, you get

$$-x^2 - 2xy + x^2 y^2 - y^2 > -x^2 - y^2$$

which implies $$- 2xy + x^2 y^2 > 0$$ or $$xy - 2 >0$$

This is clearly false if $x = 1>0$ and $y=1>0$.

Notice that this relates to the discussion above. For this case $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} = 0 + \frac{-2(xy)}{(xy)^2} = \frac{-2}{xy} < 0$ for any $x, y > 0$.

Therefore the product of two supermodular functions is not necessarily supermodular.

The answer is no, not in general.

I am going to assume $f$ and $g$ are supermodular, real polynomials. I'll discuss what needs to happen for their product to be supermodular and then construct a counter example.

1.) $f$ and $g$ must have mixed terms or else they violate supermodularity as stated in your question.

Proving this fact amounts to showing that $ (x'^n + y'^n) + (x^n + y^n) \ngtr (x'^n + y^n) + (x^n + y'^n) $.

2.) If this property holds, then it must hold at zero. So consider $f(x, y) + f(0, 0) > f(x, 0) + f(y, 0)$. Because I am assuming these are polynomials, cancellation of terms leaves us with the expression $$axy + bx^2y + cxy^2 + dx^2y^2 + \ldots > 0$$ where $a, b, c, \ldots$ are the (possibly zero) coefficients of the mixed terms of $f$.

3.) Should $f*g$ satisfy supermodularity, then it must for $(x, y) > (0, 0).$ Therefore, $$f(x, y)g(x, y) + f(0, 0) g(0, 0) > f(x, 0) g(x, 0) + f(0, y)g(0, y)$$ should hold true.

The left-hand side contains the product of two polynomials plus the product of their constant terms. The right-hand side contains the product of the $x$-terms (including the constant) of $f$ and $g$ plus the product of the $y$-terms (including the constant) of $f$ and $g$.

The inequality rests on what happens with the cross-terms of $f(x, y)g(x, y)$. I am going to denote the mixed terms of $f$ as $m(f)$ and the remaining terms as $p(f) = p_x(f) + p_y(f) + p_c(f)$ for the $x$-only terms, $y$-only terms, and the constant term (respectively). So $f(x, y) = m(f) + p_x(f) + p_y(f) + p_c(f)$.

To clarify what I said earlier, the inequality is true so long as $$m(f)m(g) + m(f)p(g) + p(f)m(g) + \big[p_x(f)[p_y(g) + p_c(g)] + p_y(f)[p_x(g) + p_c(g)] + p_c(f)[p_x(g) + p_y(g)]\big] >0.$$ Call the mixed terms $\varphi(x, y)$. Then this expression simplifies to $$m(g)m(f) [p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)}] >0.$$ We know from (2) that $m(f)$ and $m(g)$ are both greater than 0. Is it not necessarily true, however, that $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} >0$.

So a counter example just needs to satisfy $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} \leq 0$. Here is one such example:

Let $$f(x, y) = -x + xy - y \quad \text{ and } \quad g(x, y) = x + xy + y$$

One can verify that both $f$ and $g$ satisfy supermodularity. Now, consider the product:

$$f(x, y)*g(x, y) = -x^2 - 2xy + x^2 y^2 - y^2$$

If this satisfied supermodularity, then for $x>0$ and $y>0$, you get

$$-x^2 - 2xy + x^2 y^2 - y^2 > -x^2 - y^2$$

which implies $$- 2xy + x^2 y^2 > 0$$ or $$xy - 2 >0$$

This is clearly false if $x = 1>0$ and $y=1>0$.

Notice that this relates to the discussion above. For this case $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} = 0 + \frac{-2(xy)}{(xy)^2} = \frac{-2}{xy} < 0$ for any $x, y > 0$.

Therefore the product of two supermodular functions is not necessarily supermodular.

There was an error in my characterization of what supermodular function multiply to something not supermodular.
Source Link
S.J.
  • 21
  • 3

The answer is no, not in general.

I am going to assume $f$ and $g$ are supermodular, real polynomials. I'll discuss what needs to happen for their product to be supermodular and then construct a counter example.

1.) $f$ and $g$ must have mixed terms or else they violate supermodularity as stated in your question.

Proving this fact amounts to showing that $ (x'^n + y'^n) + (x^n + y^n) \ngtr (x'^n + y^n) + (x^n + y'^n) $.

2.) If this property holds, then it must hold at zero. So consider $f(x, y) + f(0, 0) > f(x, 0) + f(y, 0)$. Because I am assuming these are polynomials, cancellation of terms leaves us with the expression $$axy + bx^2y + cxy^2 + dx^2y^2 + \ldots > 0$$ where $a, b, c, \ldots$ are the (possibly zero) coefficients of the mixed terms of $f$.

3.) Should $f*g$ satisfy supermodularity, then it must for $(x, y) > (0, 0).$ Therefore, $$f(x, y)g(x, y) + f(0, 0) g(0, 0) > f(x, 0) g(x, 0) + f(0, y)g(0, y)$$ should hold true.

The left-hand side contains the product of two polynomials plus the product of their constant terms. The right-hand side contains the product of the $x$-terms (including the constant) of $f$ and $g$ plus the product of the $y$-terms (including the constant) of $f$ and $g$.

The inequality rests on what happens when the sum ofwith the mixed termscross-terms of one function are multiplied by the other function plus vice versa$f(x, y)g(x, y)$.

  I am going to denote the mixed terms of $f$ as $m(f)$ and the remaining terms as $p(f)$$p(f) = p_x(f) + p_y(f) + p_c(f)$ for the $x$-only terms, $y$-only terms, and the constant term (respectively). So $f(x, y) = m(f) + p(f)$$f(x, y) = m(f) + p_x(f) + p_y(f) + p_c(f)$.

To restateclarify what I said earlier, the inequality is true ifso long as $$f(x, y) m(g) + g(x, y)m(f) >0.$$$$m(f)m(g) + m(f)p(g) + p(f)m(g) + \big[p_x(f)[p_y(g) + p_c(g)] + p_y(f)[p_x(g) + p_c(g)] + p_c(f)[p_x(g) + p_y(g)]\big] >0.$$ ThisCall the mixed terms $\varphi(x, y)$. Then this expression simplifies to $$m(g)m(f) [p(f) + p(g)] >0.$$$$m(g)m(f) [p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)}] >0.$$ We know from (2) $m(f)$ and $m(g)$ are both greater than 0. Is it necessarily true, however, that $p(f) + p(g) >0$? The answer is no!$p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} >0$.

So a counter example just needs to satisfy $p(f) + p(g) \leq 0$$p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} \leq 0$. Here is one such example:

Let $$f(x, y) = -x + xy - y \quad \text{ and } \quad g(x, y) = x + xy + y$$

One can verify that both $f$ and $g$ satisfy supermodularity. Now, consider the product:

$$f(x, y)*g(x, y) = -x^2 - 2xy + x^2 y^2 - y^2$$

If this satisfied supermodularity, then for $x>0$ and $y>0$, you get

$$-x^2 - 2xy + x^2 y^2 - y^2 > -x^2 - y^2$$

which implies $$- 2xy + x^2 y^2 > 0$$ or $$xy - 2 >0$$

This is clearly false if $x = 1>0$ and $y=1>0$.

Notice that this relates to the discussion above. For this case $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} = 0 + \frac{-2(xy)}{(xy)^2} = \frac{-2}{xy} < 0$ for any $x, y > 0$.

Therefore the product of two supermodular functions is not necessarily supermodular.

The answer is no, not in general.

I am going to assume $f$ and $g$ are supermodular, real polynomials. I'll discuss what needs to happen for their product to be supermodular and then construct a counter example.

1.) $f$ and $g$ must have mixed terms or else they violate supermodularity as stated in your question.

Proving this fact amounts to showing that $ (x'^n + y'^n) + (x^n + y^n) \ngtr (x'^n + y^n) + (x^n + y'^n) $.

2.) If this property holds, then it must hold at zero. So consider $f(x, y) + f(0, 0) > f(x, 0) + f(y, 0)$. Because I am assuming these are polynomials, cancellation of terms leaves us with the expression $$axy + bx^2y + cxy^2 + dx^2y^2 + \ldots > 0$$ where $a, b, c, \ldots$ are the (possibly zero) coefficients of the mixed terms of $f$.

3.) Should $f*g$ satisfy supermodularity, then it must for $(x, y) > (0, 0).$ Therefore, $$f(x, y)g(x, y) + f(0, 0) g(0, 0) > f(x, 0) g(x, 0) + f(0, y)g(0, y)$$ should hold true.

The left-hand side contains the product of two polynomials plus the product of their constant terms. The right-hand side contains the product of the $x$-terms (including the constant) of $f$ and $g$ plus the product of the $y$-terms (including the constant) of $f$ and $g$.

The inequality rests on what happens when the sum of the mixed terms of one function are multiplied by the other function plus vice versa.

  I am going to denote the mixed terms of $f$ as $m(f)$ and the remaining terms as $p(f)$. So $f(x, y) = m(f) + p(f)$.

To restate what I said earlier, the inequality is true if $$f(x, y) m(g) + g(x, y)m(f) >0.$$ This simplifies to $$m(g)m(f) [p(f) + p(g)] >0.$$ We know from (2) $m(f)$ and $m(g)$ are both greater than 0. Is it necessarily true that $p(f) + p(g) >0$? The answer is no!

So a counter example just needs to satisfy $p(f) + p(g) \leq 0$. Here is one such example:

Let $$f(x, y) = -x + xy - y \quad \text{ and } \quad g(x, y) = x + xy + y$$

One can verify that both $f$ and $g$ satisfy supermodularity. Now, consider the product:

$$f(x, y)*g(x, y) = -x^2 - 2xy + x^2 y^2 - y^2$$

If this satisfied supermodularity, then for $x>0$ and $y>0$, you get

$$-x^2 - 2xy + x^2 y^2 - y^2 > -x^2 - y^2$$

which implies $$- 2xy + x^2 y^2 > 0$$ or $$xy - 2 >0$$

This is clearly false if $x = 1>0$ and $y=1>0$.

Therefore the product of two supermodular functions is not necessarily supermodular.

The answer is no, not in general.

I am going to assume $f$ and $g$ are supermodular, real polynomials. I'll discuss what needs to happen for their product to be supermodular and then construct a counter example.

1.) $f$ and $g$ must have mixed terms or else they violate supermodularity as stated in your question.

Proving this fact amounts to showing that $ (x'^n + y'^n) + (x^n + y^n) \ngtr (x'^n + y^n) + (x^n + y'^n) $.

2.) If this property holds, then it must hold at zero. So consider $f(x, y) + f(0, 0) > f(x, 0) + f(y, 0)$. Because I am assuming these are polynomials, cancellation of terms leaves us with the expression $$axy + bx^2y + cxy^2 + dx^2y^2 + \ldots > 0$$ where $a, b, c, \ldots$ are the (possibly zero) coefficients of the mixed terms of $f$.

3.) Should $f*g$ satisfy supermodularity, then it must for $(x, y) > (0, 0).$ Therefore, $$f(x, y)g(x, y) + f(0, 0) g(0, 0) > f(x, 0) g(x, 0) + f(0, y)g(0, y)$$ should hold true.

The left-hand side contains the product of two polynomials plus the product of their constant terms. The right-hand side contains the product of the $x$-terms (including the constant) of $f$ and $g$ plus the product of the $y$-terms (including the constant) of $f$ and $g$.

The inequality rests on what happens with the cross-terms of $f(x, y)g(x, y)$. I am going to denote the mixed terms of $f$ as $m(f)$ and the remaining terms as $p(f) = p_x(f) + p_y(f) + p_c(f)$ for the $x$-only terms, $y$-only terms, and the constant term (respectively). So $f(x, y) = m(f) + p_x(f) + p_y(f) + p_c(f)$.

To clarify what I said earlier, the inequality is true so long as $$m(f)m(g) + m(f)p(g) + p(f)m(g) + \big[p_x(f)[p_y(g) + p_c(g)] + p_y(f)[p_x(g) + p_c(g)] + p_c(f)[p_x(g) + p_y(g)]\big] >0.$$ Call the mixed terms $\varphi(x, y)$. Then this expression simplifies to $$m(g)m(f) [p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)}] >0.$$ We know from (2) $m(f)$ and $m(g)$ are both greater than 0. Is it necessarily true, however, that $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} >0$.

So a counter example just needs to satisfy $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} \leq 0$. Here is one such example:

Let $$f(x, y) = -x + xy - y \quad \text{ and } \quad g(x, y) = x + xy + y$$

One can verify that both $f$ and $g$ satisfy supermodularity. Now, consider the product:

$$f(x, y)*g(x, y) = -x^2 - 2xy + x^2 y^2 - y^2$$

If this satisfied supermodularity, then for $x>0$ and $y>0$, you get

$$-x^2 - 2xy + x^2 y^2 - y^2 > -x^2 - y^2$$

which implies $$- 2xy + x^2 y^2 > 0$$ or $$xy - 2 >0$$

This is clearly false if $x = 1>0$ and $y=1>0$.

Notice that this relates to the discussion above. For this case $p(f) + p(g) + \frac{\varphi(x)}{m(g)m(f)} = 0 + \frac{-2(xy)}{(xy)^2} = \frac{-2}{xy} < 0$ for any $x, y > 0$.

Therefore the product of two supermodular functions is not necessarily supermodular.

Source Link
S.J.
  • 21
  • 3

The answer is no, not in general.

I am going to assume $f$ and $g$ are supermodular, real polynomials. I'll discuss what needs to happen for their product to be supermodular and then construct a counter example.

1.) $f$ and $g$ must have mixed terms or else they violate supermodularity as stated in your question.

Proving this fact amounts to showing that $ (x'^n + y'^n) + (x^n + y^n) \ngtr (x'^n + y^n) + (x^n + y'^n) $.

2.) If this property holds, then it must hold at zero. So consider $f(x, y) + f(0, 0) > f(x, 0) + f(y, 0)$. Because I am assuming these are polynomials, cancellation of terms leaves us with the expression $$axy + bx^2y + cxy^2 + dx^2y^2 + \ldots > 0$$ where $a, b, c, \ldots$ are the (possibly zero) coefficients of the mixed terms of $f$.

3.) Should $f*g$ satisfy supermodularity, then it must for $(x, y) > (0, 0).$ Therefore, $$f(x, y)g(x, y) + f(0, 0) g(0, 0) > f(x, 0) g(x, 0) + f(0, y)g(0, y)$$ should hold true.

The left-hand side contains the product of two polynomials plus the product of their constant terms. The right-hand side contains the product of the $x$-terms (including the constant) of $f$ and $g$ plus the product of the $y$-terms (including the constant) of $f$ and $g$.

The inequality rests on what happens when the sum of the mixed terms of one function are multiplied by the other function plus vice versa.

I am going to denote the mixed terms of $f$ as $m(f)$ and the remaining terms as $p(f)$. So $f(x, y) = m(f) + p(f)$.

To restate what I said earlier, the inequality is true if $$f(x, y) m(g) + g(x, y)m(f) >0.$$ This simplifies to $$m(g)m(f) [p(f) + p(g)] >0.$$ We know from (2) $m(f)$ and $m(g)$ are both greater than 0. Is it necessarily true that $p(f) + p(g) >0$? The answer is no!

So a counter example just needs to satisfy $p(f) + p(g) \leq 0$. Here is one such example:

Let $$f(x, y) = -x + xy - y \quad \text{ and } \quad g(x, y) = x + xy + y$$

One can verify that both $f$ and $g$ satisfy supermodularity. Now, consider the product:

$$f(x, y)*g(x, y) = -x^2 - 2xy + x^2 y^2 - y^2$$

If this satisfied supermodularity, then for $x>0$ and $y>0$, you get

$$-x^2 - 2xy + x^2 y^2 - y^2 > -x^2 - y^2$$

which implies $$- 2xy + x^2 y^2 > 0$$ or $$xy - 2 >0$$

This is clearly false if $x = 1>0$ and $y=1>0$.

Therefore the product of two supermodular functions is not necessarily supermodular.