Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
I'll be the first to comment that this doesn't fit the classic Math Overflow mould of a precise mathematical question with a precise mathematical answer. But I hope people think it's a good use of the site. As brief justification: imagine trying to look this up on MathSciNet, google etc. –  Tom Leinster Jan 20 '10 at 2:03
2  
I don't understand. If I have the polynomial $f(X) = 2$, then I write it as a sum of empty products: $f(X) = 1 + 1$. Then I change the empty products into empty sums, and the sum into a product: $f*(X) = 0 * 0 = 0$. So the * of any constant is 0. And actually the * of anything with non-trivial constant part is 0? –  Theo Johnson-Freyd Jan 20 '10 at 4:26
5  
What? I'm pretty sure it's the other way around. –  Qiaochu Yuan Jan 20 '10 at 5:14
1  
Theo: you understand correctly. The * of any polynomial with nonzero constant term is 0. Harry: I believe I've stated the definition of * correctly, regardless of whether one agrees that the empty product is 1. –  Tom Leinster Jan 20 '10 at 5:15
1  
Qiaochu: yes, if we're speaking categorically (which I wasn't), the empty product is the terminal object. –  Tom Leinster Jan 20 '10 at 5:20
show 5 more comments

5 Answers 5

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.

share|improve this answer
    
Darsh, thanks, that does seem to be in the same spirit. –  Tom Leinster Jan 20 '10 at 5:19
add comment

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.

share|improve this answer
2  
Aha! This is in fact very close to what I was doing. I was looking at something involving the closed structure for the Day tensor product (in as far as it exists) on [Set^n, Set]. I'd be interested to hear what you've done on this kind of thing. –  Tom Leinster Jan 21 '10 at 6:20
3  
I don't know how your Haskell programming is but the code I was writing is here: blog.sigfpe.com/2009/11/… The weird thing is that I was tempted recently to post a question about a bizarre polynomial operation myself. It came from considering natural transforms from polynomial functor F to polynomial functor G. The number of these is, I think, $G(0)^{f_0}G(1)^{f_1}G(2)^{f_2}...$ where $F(X)=f_0+f_1X+f_2X^2+...$ (or close). I'd never seen two polynomials weaved together in this way before. To my shame, I don't know what the Day tensor product is. –  Dan Piponi Jan 21 '10 at 6:35
2  
Thanks. Will take a look, and will probably write something about how I got to this on the n-Cafe, but not for a while yet. In the case of one variable (and over Set), F*(Y) is characterized by being universal equipped with a map F(X) x F*(Y) --> X x Y for each set X, naturally in X. –  Tom Leinster Jan 21 '10 at 7:22
1  
So F(X), besides being a container of X's, contains a rule for picking out an element of Y from F*(Y) and vice versa. So F(X) (or even just F(1)) acts like a pointer into the data structure F*(Y), and vice versa. This is really neat! Pointers into structures are usually thought of in terms of derivatives of functors so this is a nice twist. –  Dan Piponi Jan 21 '10 at 15:39
add comment

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.

share|improve this answer
1  
Thanks! I'll see what I can find, but if you remember any references, I'd love to know. –  Tom Leinster Jan 21 '10 at 6:18
add comment

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.

share|improve this answer
1  
Agreed about the notation - it's more or less what I use privately. But I don't see where you're going with the logarithms. –  Tom Leinster Jan 20 '10 at 2:29
    
This operation smells like a cumulant generating function or a Baker-Campbell-Hausdorffy sort of thing to me. –  Steve Huntsman Jan 20 '10 at 2:33
add comment

(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

share|improve this answer
1  
Right, taking the "de Morgan dual" of a polynomial with coefficients in {true, false} is another example of the categorical construction I hinted at. Re coefficients: this construction simply is what it is; it comes out of something more general, and I don't think any there's any flexibility in it. –  Tom Leinster Jan 20 '10 at 2:26
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.