extraña operación de polinomios

Question

Allí estaba yo, inocentemente haciendo algunos categoría de teoría, cuando apareció totalmente extravagantes operación en polinomios. Parece extravagante para mí, de todos modos. Me gustaría saber si alguien ha visto esta operación antes de que, en cualquier contexto.

La categórica de fondo no es relevante para la pregunta, así que voy a omitir. Todo lo que quiero subrayar es que , a priori, no tiene nada que ver con polinomios. Sólo algunos universal de los bienes, lo que produce esto en un caso especial. (Para los curiosos, la categoría de conexión es que algunos de los functors $\mathbf{Set}^n \to \mathbf{Set}$ puede ser visto como "polinomio", en el sentido de que está construido a partir de productos, $\times$, y co-productos, $+$.)

Por un polinomio me refiero a un polinomio en los desplazamientos variables $X_1, \ldots, X_n$, con coeficientes en los números naturales $\mathbb{N}$ (que incluye a $0$).

Aquí está la operación. Dado un polinomio $f = f(X_1, \ldots, X_n)$, definir un nuevo polinomio $f^*$ como sigue.

1. Escribir $f$ como una suma de productos de $X_i$'s.

2. Cambiar todas las ocurrencias de $+$$\times$, y cada aparición de $\times$$+$. Llame a la resultante polinomio $f^*$.

Ejemplos:

• Tome $f(X, Y) = (X + Y)^2$. Paso 1 escribe $f$ $$ f(X, Y) = (X \times X) + (X \times Y) + (X \times Y) + (Y \times Y). $$ Paso 2 a continuación, da $$ f^*(X, Y) = (X + X) \times (X + Y) \times (X + Y) \times (Y + Y) = 4XY(X + Y)^2. $$ Ahora vamos a calcular el $f^{**}$. Paso 1: $$ f^*(X, Y) = 4X^3 Y + 8X^2 Y^2 + 4X Y^3. $$ Paso 2: $$ f^{**}(X, Y) = (3X + Y)^4 (2X + 2Y)^8 (X + 3Y)^4. $$

• En general, si $$ f(X_1, \ldots, X_n) = 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}$ ), a continuación, $$ f^*(X_1, \ldots, X_n) = (a_1 X_1 + \cdots a_n X_n)^(b_1 X_1 + \cdots + b_n X_n)^B \cdots. $$

• En el ejemplo anterior, $f^{**} = f$ si $f$ es un monomio ($X_1^{a_1} \cdots X_n^{a_n}$) o lineal ($a_1 X_1 + \cdots + a_n X_n$).

• Desde el vacío de la suma es 0 y el vacío del producto es 1, debe estar implícito en (2) que 0s convertido en 1s 1s y convertirse en 0s. E. g. si $f = 0$$f^* = 1$, y si $f(X) = X^2 + 1$$f^*(X) = 2X \times 0 = 0$. Edit: de la misma manera, si $f$ tiene un valor distinto de cero término constante, a continuación,$f^* = 0$.

Estoy interesado en escuchar acerca de cualquier lugar que nadie ha visto esta operación.

Siéntase libre de agregar etiquetas según corresponda.

Answer 1

Esto$\ast$ operación puede aparecer cuando se cuenta el número de transformaciones naturales entre endofunctors polinómicas en$Set$. Por ejemplo, si se abusa de manera que la notación$f$ es a la vez un polinomio univariado y su correspondiente endofunctor ecuación polinómica, seguida$|Nat(f,1_{Set})|=f^\ast(1)$.

Me encontré con este código recientemente cuando se escribe a memoize funciones polimórficas.

Answer 2

No recuerdo ninguna referencia en el momento pero he visto este tipo de "dualización" en temas relacionados con mayorización. Por ejemplo deje$$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)}$ $ Un resultado clásico de Muirhead es que$f$ es Schur-convexa con respecto al$\mathbf{a}$ (con$\mathbf{x}$ en el ortante positivo). No es un resultado que$f(\mathbf{x,a})^{*}$ será Schur-cóncava (dual adoptado con respecto a las x, por supuesto), por lo tanto$\*$ envía polinomios de Schur-convexos a los Schur-cóncavas.

Answer 3

No puedo recordar haber visto esto, pero un cambio de notación podría aclarar un poco. Si$f = \sum_\alpha a_\alpha x^\alpha$ #%% luego #%.

Tomando un logaritmo formal de la LHS da$f^* = \prod_\alpha \langle \alpha, x \rangle^{a_\alpha}$.

Así hasta un logaritmo formales / exponencial su estrella operación de mapas$\log f^* = \sum_\alpha a_\alpha \log \langle \alpha, x \rangle$ a$x^\alpha$. Compárese esto con$\log \langle \alpha, x \rangle$, donde el logaritmo se define componente a componente.

Answer 4

(De nuevo, mis disculpas a los administradores para que aún no registrarse. Vamos a esperar en la fusión.)

En el entramado de la teoría (conjunto con encontrar y unirse a la satisfacción de niza relaciones), celosía polinomios son a veces la alteración de esta manera, especialmente en mirar doble propiedades. En el álgebra Booleana, una operación similar se utiliza, a excepción de las variables y el producto completo utilizados son negados (las leyes de DeMorgan). Esto es usado para algún efecto en Booleana anillos, así como en digital el diseño de circuitos.

Para polinomios sobre los números naturales, no tanto. Puede que desee tener cuidado en cómo lidiar con los coeficientes que, como no puede ser de rareza en el giro de +1 a *0.

Gerhard "Me Preguntan Sobre El Diseño Del Sistema" Paseman, 2010.01.19

Answer 5

Me encontré con algo similar en el contexto de la ampliación de funciones booleanas con argumentos reales. Pensé que era muy divertido, así que permítanme compartir aquí.

Si entendemos a la 1 en "true" y 0 es falso, una manera de definir "x y y" es como xy. Del mismo modo, "x o y" puede ser definida como x + y - xy, y "no x" puede ser 1 - x. Hay buenas razones para preferir estas definiciones sobre los demás. Por ejemplo, si x e y son la probabilidad de eventos independientes, entonces xy, x + y - xy, etc. son, respectivamente, las probabilidades de que la conjunción, la disyunción, etc. Esto le da una forma sistemática para ampliar funciones booleanas $\{\mathrm{false, true}\}^n\to\{\mathrm{false, true}\}$ a los polinomios $[0,1]^n\to[0,1]$. Estos polinomios satisfacer a algunos (pero relativamente pocos) de las propiedades de sus booleano homólogos, como de la ley de de Morgan: x + y - xy = 1-(1-x)(1-y).

Por otro lado, se podría tratar a 0 como "verdadero" y el infinito como "falso", y tratar de definir funciones booleanas en el real no negativo de la línea de $[0,\infty]$. Parece que podemos empezar nuestro polinomios definidos anteriormente, se expresa adecuadamente, y el intercambio de suma con la multiplicación y la resta con la división!

Conjunción: $x\cdot y \to x + y$

Disyunción: $(x + y) - (x\cdot y) \to (x\cdot y) / (x + y)$

Negación: $1 - x \to 1 / x$

Sorprendentemente, estas sustituciones preservar de la ley de de Morgan: $xy/(x + y) = 1/(1/x + 1/y)$. Yo no creo que se pueda ejecutar con esto todo el camino hasta la línea de meta. Por ejemplo, el polinomio exclusivo-o es x + y - 2xy, pero no veo una manera fácil de expresar que para hacer la sustitución ir a través de. Sin embargo, yo creo que tenemos las siguientes:

Para cada función booleana $\{\mathrm{false, true}\}^n\to\{\mathrm{false, true}\}$, no es un polinomio de extensión de la $f:[0,1]^n\to[0,1]$ y racional de la extensión de $g:[0,\infty]^n\to [0,\infty]$ de manera tal que, expresado de forma adecuada, $f$ $g$ son obtenidos a partir de uno a otro por la adición o multiplicación de intercambio descrito anteriormente.

Por ejemplo, para la exclusiva-o, tenemos $(x + y - xy)(1 - xy) \to xy/(x+y) + 1/(x+y) = (1 + xy)/(x + y)$. Sin embargo, $(x + y - xy)(1-xy) = x + y - 2xy + xy(1-x)(1-y) \neq x + y - 2xy$, por lo que se utilizó un "no canónicos" polinomio. Hay otros ejemplos donde podemos utilizar el polinomio canónico, aunque. Por ejemplo, para el 3-ary mayoría función, tenemos

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

Sé que esto no es exactamente lo que le pidieron, ya que implica la sustracción y es realmente una operación en las expresiones, no funciones, pero espero que en el espíritu correcto.