Bizarre operation on polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T20:39:07Z http://mathoverflow.net/feeds/question/12363 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12363/bizarre-operation-on-polynomials Bizarre operation on polynomials Tom Leinster 2010-01-20T01:39:03Z 2010-01-21T04:37:53Z <p>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.</p> <p>The categorical background isn't relevant to the question, so I'll skip it. All I want to emphasize is that <em>a priori</em>, 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, $+$.) </p> <p>By a <strong>polynomial</strong> I mean a polynomial in commuting variables $X_1, \ldots, X_n$, with coefficients in the natural numbers $\mathbb{N}$ (which include $0$).</p> <p>Here's the operation. Given a polynomial $f = f(X_1, \ldots, X_n)$, define a new polynomial $f^*$ as follows.</p> <ol> <li><p>Write $f$ as a sum of products of $X_i$'s. </p></li> <li><p>Change every occurrence of $+$ to $\times$, and every occurrence of $\times$ to $+$. Call the resulting polynomial $f^*$. </p></li> </ol> <p><b>Examples:</b></p> <ul> <li><p>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 <code>$$f^*(X, Y) = (X + X) \times (X + Y) \times (X + Y) \times (Y + Y) = 4XY(X + Y)^2.$$</code> Now let's calculate $f^{**}$. Step 1: <code>$$f^*(X, Y) = 4X^3 Y + 8X^2 Y^2 + 4X Y^3.$$</code> Step 2: <code>$$f^{**}(X, Y) = (3X + Y)^4 (2X + 2Y)^8 (X + 3Y)^4.$$</code></p></li> <li><p>Generally, if <code>$$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$$</code> ($A, a_i, B, b_i, \ldots \in \mathbb{N}$) then <code>$$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.$$</code></p></li> <li><p>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$). </p></li> <li><p>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 <code>$f^*(X) = 2X \times 0 = 0$</code>. <b>Edit</b>: Similarly, if $f$ has nonzero constant term then $f^* = 0$. </p></li> </ul> <p>I'm interested to hear about anywhere that anyone has seen this operation. </p> <p>Feel free to add tags as appropriate.</p> http://mathoverflow.net/questions/12363/bizarre-operation-on-polynomials/12365#12365 Answer by Steve Huntsman for Bizarre operation on polynomials Steve Huntsman 2010-01-20T02:09:10Z 2010-01-20T02:09:10Z <p>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}$. </p> <p>Taking a <em>formal</em> logarithm of the LHS gives $\log f^* = \sum_\alpha a_\alpha \log \langle \alpha, x \rangle$. </p> <p>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.</p> http://mathoverflow.net/questions/12363/bizarre-operation-on-polynomials/12367#12367 Answer by Gerhard Paseman for Bizarre operation on polynomials Gerhard Paseman 2010-01-20T02:21:59Z 2010-01-20T02:21:59Z <p>(Again, apologies to the admins for not yet registering. Let's wait on merging.)</p> <p>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.</p> <p>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.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2010.01.19</p> http://mathoverflow.net/questions/12363/bizarre-operation-on-polynomials/12378#12378 Answer by Darsh Ranjan for Bizarre operation on polynomials Darsh Ranjan 2010-01-20T05:11:50Z 2010-01-20T05:11:50Z <p>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. </p> <p>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). </p> <p>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! </p> <p>Conjunction: $x\cdot y \to x + y$</p> <p>Disjunction: $(x + y) - (x\cdot y) \to (x\cdot y) / (x + y)$</p> <p>Negation: $1 - x \to 1 / x$</p> <p>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: </p> <blockquote> <p>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. </p> </blockquote> <p>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 </p> <p>$$xy + xz + yz - 2xyz \to (x + y)(x + z)(y + z)/(x + y + z)^2.$$</p> <p>I know this is not exactly what you asked about, since it involves subtraction and it's really an operation on <i>expressions</i>, not functions, but I hope it's in the right spirit. </p> http://mathoverflow.net/questions/12363/bizarre-operation-on-polynomials/12460#12460 Answer by Dan Piponi for Bizarre operation on polynomials Dan Piponi 2010-01-20T22:42:08Z 2010-01-21T01:15:51Z <p>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)$.</p> <p>I came across this recently when writing code to memoize polymorphic functions.</p> http://mathoverflow.net/questions/12363/bizarre-operation-on-polynomials/12496#12496 Answer by Gjergji Zaimi for Bizarre operation on polynomials Gjergji Zaimi 2010-01-21T04:37:53Z 2010-01-21T04:37:53Z <p>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.</p>