Operación extraña sobre polinomios

Question

Allí estaba yo, haciendo inocentemente algo de teoría de categorías, cuando apareció una operación totalmente extravagante sobre polinomios. Al menos a mí me parece extravagante. Me gustaría saber si alguien ha visto esta operación antes, en cualquier contexto.

El trasfondo categórico no es relevante para la pregunta, así que lo obviaré. Lo único que quiero destacar es que a priori No tiene nada que ver con los polinomios. Es sólo una propiedad universal, que produce esto en un caso especial. (Para los curiosos, la conexión categórica es que algunos funtores $\mathbf{Set}^n \to \mathbf{Set}$ pueden considerarse "polinómicas", en el sentido de que se construyen a partir de productos, $\times$ y coproductos, $+$ .)

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

Aquí está la operación. Dado un polinomio $f = f(X_1, \ldots, X_n)$ definan un nuevo polinomio $f^*$ de la siguiente manera.

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

2. Cambiar cada ocurrencia de $+$ a $\times$ y cada ocurrencia de $\times$ a $+$ . Llama al polinomio resultante $f^*$ .

Ejemplos:

• Tome $f(X, Y) = (X + Y)^2$ . Paso 1 escribe $f$ como $$ f(X, Y) = (X \times X) + (X \times Y) + (X \times Y) + (Y \times Y). $$ El paso 2 da entonces $$ f^*(X, Y) = (X + X) \times (X + Y) \times (X + Y) \times (Y + Y) = 4XY(X + Y)^2. $$ Ahora vamos a calcular $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) = 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}$ ) entonces $$ 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. $$

• Por 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$ ).

• Como la suma vacía es 0 y el producto vacío es 1, se supone que está implícito en (2) que los 0 se convierten en 1 y los 1 en 0. Por ejemplo, si $f = 0$ entonces $f^* = 1$ y si $f(X) = X^2 + 1$ entonces $f^*(X) = 2X \times 0 = 0$ . Modifier : Del mismo modo, si $f$ tiene un término constante no nulo, entonces $f^* = 0$ .

Me interesa saber si alguien ha visto esta operación en algún lugar.

Siéntase libre de añadir etiquetas según corresponda.

Answer 1

Me encontré con algo similar en el contexto de la ampliación de las funciones booleanas a los argumentos reales. Me pareció bastante divertido, así que permítanme compartirlo aquí.

Si entendemos que 1 es "verdadero" y 0 es falso, una forma de definir "x e y" es como xy. Del mismo modo, "x o y" puede definirse como x + y - xy, y "no x" puede ser 1 - x. Hay buenas razones para preferir estas definiciones a otras. Por ejemplo, si x e y son las probabilidades de sucesos independientes, entonces xy, x + y - xy, etc. son respectivamente las probabilidades de la conjunción, disyunción, etc. Esto proporciona una forma sistemática de extender las funciones booleanas $\{\mathrm{false, true}\}^n\to\{\mathrm{false, true}\}$ a los polinomios $[0,1]^n\to[0,1]$ . Estos polinomios satisfacen algunas (pero relativamente pocas) de las buenas propiedades de sus homólogos booleanos, como la ley de Morgan: x + y - xy = 1-(1-x)(1-y).

Por otro lado, podríamos tratar el 0 como "verdadero" y el infinito como "falso" e intentar definir funciones booleanas en la recta real no negativa $[0,\infty]$ . Parece que podemos empezar tomando nuestros polinomios definidos anteriormente, expresados adecuadamente, e intercambiando la 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$

Divertidamente, estas sustituciones conservan la ley de Morgan: $xy/(x + y) = 1/(1/x + 1/y)$ . No creo que se pueda correr con esto hasta la meta. Por ejemplo, el polinomio para el exclusivo-o es x + y - 2xy, pero no veo una forma fácil de expresarlo para que la sustitución pase. Sin embargo, creo que tenemos lo siguiente:

Para cada función booleana $\{\mathrm{false, true}\}^n\to\{\mathrm{false, true}\}$ existe una extensión polinómica $f:[0,1]^n\to[0,1]$ y una extensión racional $g:[0,\infty]^n\to [0,\infty]$ de tal manera que, expresado adecuadamente, $f$ y $g$ se obtienen entre sí mediante el intercambio de suma/multiplicación 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 utilizamos un polinomio "no canónico". Sin embargo, hay otros ejemplos en los que podemos utilizar el polinomio canónico. Por ejemplo, para la función mayoritaria 3-aria, tenemos

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

Sé que esto no es exactamente lo que has preguntado, ya que implica una sustracción y en realidad es una operación sobre expresiones no funciones, pero espero que sea con el espíritu adecuado.

Answer 2

Este $\ast$ puede aparecer cuando se cuenta el número de transformaciones naturales entre endofunctores polinómicos en $Set$ . Por ejemplo, si abusamos de la notación para que $f$ es a la vez un polinomio univariado y su correspondiente endofunctor polinómico, entonces $|Nat(f,1_{Set})|=f^\ast(1)$ .

Me encontré con esto recientemente al escribir código para memoizar funciones polimórficas.

Answer 3

No recuerdo ninguna referencia en este momento pero he visto este tipo de "dualización" en temas relacionados con la especialización. Por ejemplo $$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-convexo con respecto a $\mathbf{a}$ (con $\mathbf{x}$ en el ortante positivo). Existe un resultado que $f(\mathbf{x,a})^{*}$ será cóncava de Schur (dual tomada con respecto a las x, por supuesto), por lo que $*$ envía los polinomios Schur-convexos a los Schur-concavos.

Answer 4

No recuerdo haber visto esto, pero un cambio de notación podría aclarar un poco. Si $f = \sum_\alpha a_\alpha x^\alpha$ entonces $f^* = \prod_\alpha \langle \alpha, x \rangle^{a_\alpha}$ .

Tomar una formal el logaritmo del LHS da $\log f^* = \sum_\alpha a_\alpha \log \langle \alpha, x \rangle$ .

Así que hasta un logaritmo/exponencial formal su operación estrella mapea $x^\alpha$ a $\log \langle \alpha, x \rangle$ . Compara esto con $\log x^\alpha \equiv \langle \alpha, \log x \rangle$ donde el logaritmo se define por componentes.

Answer 5

(De nuevo, disculpas a los administradores por no haberme registrado todavía. Esperemos a la fusión).

En la teoría de celosías (conjunto con meet y join que satisfacen relaciones agradables), los polinomios de celosía se modifican a veces de esta manera, sobre todo al examinar las propiedades duales. En el álgebra booleana, se utiliza una operación similar, excepto que las variables y el producto completo utilizado se niegan (leyes de DeMorgan). Esto se utiliza con cierto efecto en los anillos booleanos, así como en el diseño de circuitos digitales.

Para los polinomios sobre los números naturales, no tanto. Es posible que desee tener cuidado de cómo tratar con los coeficientes, ya que puede haber rareza en la conversión de +1 en *0.

Gerhard "Ask Me About System Design" Paseman, 2010.01.19