Bizarre operation on polynomials

Question

There I was, innocently doing some category theory, when up popped a totally outlandish operation on polynomials. It seems outlandish to me, anyway. I'd like to know if anyone has seen this operation before, in any context.

The categorical background isn't relevant to the question, so I'll skip it. All I want to emphasize is that a priori, it has nothing to do with polynomials. It's just some universal property, which produces this in a special case. (For the curious, the categorical connection is that some functors $\mathbf{Set}^n \to \mathbf{Set}$ can be viewed as "polynomial", in the sense that they're built up from products, $\times$, and coproducts, $+$.)

By a polynomial I mean a polynomial in commuting variables $X_1, \ldots, X_n$, with coefficients in the natural numbers $\mathbb{N}$ (which include $0$).

Here's the operation. Given a polynomial $f = f(X_1, \ldots, X_n)$, define a new polynomial $f^*$ as follows.

1. Write $f$ as a sum of products of $X_i$'s.

2. Change every occurrence of $+$ to $\times$, and every occurrence of $\times$ to $+$. Call the resulting polynomial $f^*$.

Examples:

• Take $f(X, Y) = (X + Y)^2$. Step 1 writes $f$ as $$ f(X, Y) = (X \times X) + (X \times Y) + (X \times Y) + (Y \times Y). $$ Step 2 then gives $$ f^*(X, Y) = (X + X) \times (X + Y) \times (X + Y) \times (Y + Y) = 4XY(X + Y)^2. $$ Now let's calculate $f^{**}$. Step 1: $$ f^*(X, Y) = 4X^3 Y + 8X^2 Y^2 + 4X Y^3. $$ Step 2: $$ f^{**}(X, Y) = (3X + Y)^4 (2X + 2Y)^8 (X + 3Y)^4. $$

• Generally, if $$ f(X_1, \ldots, X_n) = A X_1^{a_1} \cdots X_n^{a_n} + B X_1^{b_1} \cdots X_n^{b_n} + \cdots $$ ($A, a_i, B, b_i, \ldots \in \mathbb{N}$) then $$ f^*(X_1, \ldots, X_n) = (a_1 X_1 + \cdots a_n X_n)^A (b_1 X_1 + \cdots + b_n X_n)^B \cdots. $$

• By the previous example, $f^{**} = f$ if $f$ is a monomial ($X_1^{a_1} \cdots X_n^{a_n}$) or linear ($a_1 X_1 + \cdots + a_n X_n$).

• Since the empty sum is 0 and the empty product is 1, it's meant to be implicit in (2) that 0s become 1s and 1s become 0s. E.g. if $f = 0$ then $f^* = 1$, and if $f(X) = X^2 + 1$ then $f^*(X) = 2X \times 0 = 0$. Edit: Similarly, if $f$ has nonzero constant term then $f^* = 0$.

I'm interested to hear about anywhere that anyone has seen this operation.

Feel free to add tags as appropriate.

Answer 1

I came across something similar in the context of extending boolean functions to real arguments. I thought it was pretty amusing, so let me share it here.

If we understand 1 to be "true" and 0 to be false, one way to define "x and y" is as xy. Similarly, "x or y" can be defined as x + y - xy, and "not x" can be 1 - x. There are good reasons to prefer these definitions over others. For example, if x and y are the probabilities of independent events, then xy, x + y - xy, etc. are respectively the probabilities of the conjunction, disjunction, etc. This gives a systematic way to extend boolean functions $\{\mathrm{false, true}\}^n\to\{\mathrm{false, true}\}$ to polynomials $[0,1]^n\to[0,1]$. These polynomials satisfy some (but relatively few) of the nice properties of their boolean counterparts, like de Morgan's law: x + y - xy = 1-(1-x)(1-y).

On the other hand, we could treat 0 as "true" and infinity as "false" and try to define boolean functions on the nonnegative real line $[0,\infty]$. It seems we can begin by taking our polynomials defined above, expressed appropriately, and interchanging addition with multiplication and subtraction with division!

Conjunction: $x\cdot y \to x + y$

Disjunction: $(x + y) - (x\cdot y) \to (x\cdot y) / (x + y)$

Negation: $1 - x \to 1 / x$

Amusingly, these substitutions preserve de Morgan's law: $xy/(x + y) = 1/(1/x + 1/y)$. I don't think you can run with this all the way to the finish line. For example, the polynomial for exclusive-or is x + y - 2xy, but I don't see an easy way to express that to make the substitution go through. However, I do believe we have the following:

For every boolean function $\{\mathrm{false, true}\}^n\to\{\mathrm{false, true}\}$, there is a polynomial extension $f:[0,1]^n\to[0,1]$ and a rational extension $g:[0,\infty]^n\to [0,\infty]$ such that, expressed appropriately, $f$ and $g$ are obtained from one another by the addition/multiplication interchange described above.

For example, for exclusive-or, we have $(x + y - xy)(1 - xy) \to xy/(x+y) + 1/(x+y) = (1 + xy)/(x + y)$. However, $(x + y - xy)(1-xy) = x + y - 2xy + xy(1-x)(1-y) \neq x + y - 2xy$, so we used a "noncanonical" polynomial. There are other examples where we can use the canonical polynomial, though. For example, for the 3-ary majority function, we have

$$xy + xz + yz - 2xyz \to (x + y)(x + z)(y + z)/(x + y + z)^2.$$

I know this is not exactly what you asked about, since it involves subtraction and it's really an operation on expressions, not functions, but I hope it's in the right spirit.

Answer 2

This $\ast$ operation can appear when you count the number of natural transformations between polynomial endofunctors on $Set$. For example, if we abuse notation so that $f$ is both a univariate polynomial and its corresponding polynomial endofunctor, then $|Nat(f,1_{Set})|=f^\ast(1)$.

I came across this recently when writing code to memoize polymorphic functions.

Answer 3

I don't remember any reference at the moment but I have seen this kind of "dualization" in majorization related topics. For example let $$f(\mathbf{x,a})=f(x_1,x_2,\dots x_n\; a_1,a_2,\dots,a_n)=\sum_{\sigma \in S_n}x_{1}^{\sigma (a_1)}\cdots x_{n}^{\sigma (a_n)}$$ A classical result of Muirhead is that $f$ is Schur-convex with respect to $\mathbf{a}$ (with $\mathbf{x}$ in the positive orthant). There is a result that $f(\mathbf{x,a})^{*}$ will be Schur-concave (dual taken with respect to the x's, of course), thus $*$ sends Schur-convex polynomials to Schur-concave ones.

Answer 4

I can't recall seeing this, but a change of notation might clarify a bit. If $f = \sum_\alpha a_\alpha x^\alpha$ then $f^* = \prod_\alpha \langle \alpha, x \rangle^{a_\alpha}$.

Taking a formal logarithm of the LHS gives $\log f^* = \sum_\alpha a_\alpha \log \langle \alpha, x \rangle$.

So up to a formal logarithm/exponential your star operation maps $x^\alpha$ to $\log \langle \alpha, x \rangle$. Compare this with $\log x^\alpha \equiv \langle \alpha, \log x \rangle$ where the logarithm is defined componentwise.

Answer 5

(Again, apologies to the admins for not yet registering. Let's wait on merging.)

In lattice theory (set with meet and join satisfying nice relations), lattice polynomials are sometimes altered this way, especially in looking at dual properties. In Boolean algebra, a similar operation is used, except the variables and the full product used are negated (DeMorgan's laws). This is used to some effect in Boolean rings, as well as in digital circuit design.

For polynomials over the natural numbers, not so much. You may want to take care how you deal with coefficients, as there may be weirdness in turning +1 into *0.

Gerhard "Ask Me About System Design" Paseman, 2010.01.19