¿Podemos describir la multiplicación en$\mathbb{F}_{2^n}$ como acción en subconjuntos de$n$ - conjunto de elementos?

Question

La diferencia simétrica entre dos $A$ $B$ denotado $A \triangle B$ se define como el conjunto $(A - B) \cup (B - A)$ o, equivalentemente,$(A \cup B) - (A \cap B)$. Hace algunos años yo estaba muy entusiasmado para encontrar el conjunto $\mathcal{P}(N)$ de todos los $2^n$ subconjuntos de un $n$-element set $N$ formas un grupo abelian bajo el $\triangle$-operación.

Ser más viejo y sabio es fácil ver donde este grupo proviene de: la sustitución de cada subconjunto $A$ $N$ con su función de indicador, que es: por un vector de $n$ ceros y unos que indica si es o no el primer elemento de $N$$A$, sea o no el segundo elemento, etc, vemos que la toma de la diferencia simétrica de conjuntos corresponde a agregar el indicador de vectores mod 2. En otras palabras: el grupo que nos encontramos es el subyacente grupo abelian del espacio vectorial $\mathbb{F}_2^n$.

Ahora por la pregunta. $\mathbb{F}_2^n$ es más comúnmente escrito $\mathbb{F}_{2^n}$ y la razón es que en la parte superior de un espacio vectorial es un campo. En otras palabras: hay una, realmente hermoso, la forma de mutliplying estos vectores. La pregunta entonces es: ¿qué hace esta multiplicación aspecto cuando se la describe en términos de conjuntos? A partir de la 'resumen de campo' $\mathbb{F}_{2^n}$ parece ser que hay muchas maneras y una gran cantidad de opciones arbitrarias que intervienen a la hora de recoger la forma de escribir los elementos de los vectores, pero tal vez, a partir de los conjuntos con simétrica diferencias, además de que hay una "manera más bella' para añadir la multiplicación de la imagen?

Lo que queremos es un segundo de operaciones en los subconjuntos de a $N$ que distribuye más de $\triangle$ y, por supuesto, un ejemplo no es difícil de encontrar: la intersección va a hacer. Pero mirando a la imagen de vector de nuevo nos que da la estúpida pointwise la multiplicación de los vectores. Este es sin duda no en el campo de la multiplicación como la que produce cero (el conjunto vacío) cuando tratamos de 'multiplicar' dos subconjuntos disjuntos.

Así que mi pregunta es: ¿qué "incluso más" hermoso conjunto de la operación corresponde a la multiplicación en $\mathbb{F}_{2^n}$ cuando dejándola actuar sobre todos los subconjuntos de un conjunto de $n$ elementos?

EDIT: como se pide en los comentarios voy a decir algo sobre el pequeño de los casos. Primero para $n = 1$ tomamos nota de que, en este caso pequeños pointwise y campo de multiplicación coinciden, por lo que podemos utilizar la intersección. Pensando en las intersecciones se nota que (si no más) de la idea de tomar el elemento de campo 1 es el conjunto total $N$ podría ser algo a tener con nosotros a partir de este ejemplo con el mayor de los casos con más de lujo conjunto de operaciones. Después de todo, el 1 es el único elemento que además de 0 sabemos que está presente y fácilmente reconocible en cada campo, y del mismo modo el conjunto completo es el único subconjunto además el conjunto vacío, que es igual de fácil de identificar en todos los casos.

Correr con $1 = N$ nos deja con bastante sólo una posibilidad en el la $n = 2$ caso: cualquier singleton conjunto cuadrado le da a la otra singleton conjunto, mientras que su producto es igual a 1 (es decir, todos los de $N$). Escrito $c: \mathcal{P}(N) \to \mathcal{P}(N)$ para el complemento-operador de esta 'multiplicación' puede ser escrito como

$$A * B = c^{|A||B|}(A \cap B).$$ esta fórmula se ve bastante bien, pero ya se descompone en el $n = 1$ de los casos. Si tomamos el más agnóstico el punto de vista de que $A * B = c^{f(A, B)}(A \cap B)$ 'algunos' de la función $f$ todavía nos llevará a ninguna parte ya que esta fórmula está obligado a dar a los elementos de la satisfacción de $x^3 = 1$, mientras que nosotros queremos que todos los elementos para satisfacer $x^{2^n - 1} = 1$, con al menos un $x$ no satisfactorio $x^k = 1$ cualquier $k < 2^n -1$.

Sin embargo, si hay alguna buena idea en esta $n = 2$ estuche para llevar con nosotros a la mayor de los casos (similar a la idea de tomar de 1 a ser el conjunto de los n = 1 caso), a continuación, mi apuesta sería es la idea de tomar las $A^{-1}$ a ser el complemento de $A$. ACTUALIZACIÓN: nope. Tomando $A^{-1}$ a ser el complemento de $A$, (que es: $1 + A$ en la vista de campo) para todos los elementos de la $A$ conduce a una contradicción en el $n = 3$ de los casos. Tenemos que pensar en algo más.

Answer 1

Yo no creo que se consiga nada interesante desde este punto de vista (aunque puedo estar equivocado). El campo $\mathbb{F}_{2^{n}}$ es muy diferente de un anillo booleano (que es el más ambiente natural, para lo que están pensando).

Un gran problema es que, en su escenario (la interpretación campo finito de elementos como conjuntos), para cualesquiera dos conjuntos no vacíos $A$$B$, hay un conjunto $X$ que $A \cdot X = B$. Además, el grupo multiplicativo de un campo finito es cíclico, así que habrá algún tipo de sistema $\alpha$ tal que $A \cdot \alpha^{k}$ corresponderían a través de todos los conjuntos no vacíos como $k$ tuvo valores de$0$$q-2$.

No puedo pensar en ninguna intuitivo conjunto de operaciones que correspondan a estas propiedades.

(Además, yo no diría que $\mathbb{F}_{2}^{n}$ es más comúnmente conocido como el $\mathbb{F}_{2^{n}}$, aunque puede naturalmente ser visto de esta manera. La razón para pensar de estos objetos son diferentes, es que el espacio vectorial $\mathbb{F}_{2}^{n}$ viene en una gran cantidad de ajustes, donde el campo de multiplicación no tiene sentido o no es útil para la tarea a mano. Así que yo no diría que $\mathbb{F}_{2}^{n}$ es un campo así como de un espacio vectorial; aunque es cierto que con un definido adecuadamente la multiplicación se puede hacer en un campo. También se puede hacer en un anillo booleano mediante la definición de multiplicación para ser intersección de conjuntos.)

Answer 2

Yo no sé acerca de hermosas maneras de hacer esto. Sin embargo, no hay ninguna naturales maneras de hacer esto, al menos para $n > 2$.

Prueba. Supongamos que hay una forma natural para equipar, para un conjunto finito $X$, la $\mathcal P(X)$, con una estructura de campo. Al menos, connaturalidad significa que por cada bijection $X \to X$, la inducida por el mapa de $\mathcal P(X) \to \mathcal P(X)$ es un isomorfismo.

Sin embargo, hay $n!$ bijections $X \to X$, pero sólo hay $n$ automorfismos del campo $\mathbb F_{2^n}$. Desde $n! > n$$n > 2$, llegamos a la conclusión de que no es natural de la estructura del campo en el set $\mathcal P(X)$.

Observación. En una dirección diferente, decir que una operación binaria $\odot \colon \mathcal P(X) \times \mathcal P(X) \to \mathcal P(X)$ está dado por el conjunto de las operaciones , si es que puede ser definido por una combinación de $\cup$, $\cap$, y $(-)^c$.

La reclamación. La única operaciones binarias con la identidad que se da por el conjunto de las operaciones de $\triangle$$\cup$, y su 'complementos'$(-)^c \circ \triangle$$\cap$. En particular, no puede nunca ser elementos de orden $> 2$.

Prueba. En efecto, si la operación $\odot$ está dado por el conjunto de las operaciones, y si $U,V \subseteq X$ son subconjuntos del conjunto, entonces la validez de la declaración de $x \in U \odot V$ está dado por algunos de la tabla de verdad $$\begin{array}{ccc}x \in U & x \in V & x \in U \odot V \\ 0 & 0 & a_{00}\\ 0 & 1 & a_{01}\\ 1 & 0 & a_{10}\\ 1 & 1 & a_{11}.\\\end{array}$$ Ahora supongamos que wlog que la identidad de $\odot$ está dado por $\varnothing$ (la única otra alternativa, por connaturalidad, se $X$). Entonces $a_{00} = 0$, $a_{01} = 1$, y $a_{10} = 1$. A continuación, cualquiera de $a_{11} = 0$, lo $\odot = \triangle$ o$a_{11} = 1$$\odot = \cup$. En el primer caso. cada elemento de a $\mathcal P(X)$ orden $2$, y en el segundo caso sólo se $\varnothing$ es invertible. El caso en el que la identidad es $X$ da a las otras dos posibilidades.

Por lo tanto, vamos a ver, por $n \geq 2$ que la operación de campo en $\mathbb F_{2^n}$ no puede ser dada por un conjunto de operaciones, debido a que existe un elemento de orden multiplicativo $2^n - 1$.

Observación. Sin embargo, para $n=2$, si nos permiten el intercambio de operador $s^* \colon \mathcal P(X) \to \mathcal P(X)$ dado tirando hacia atrás a lo largo de la transposición $s \colon X \to X$, se puede describir la estructura de campo: se puede mostrar por la mano que la operación $$U \cdot V = (U \cap V) \triangle ((s^*U \triangle U) \cap (s^*V \triangle V))$$ da la operación de campo en $\mathbb F_4 = \mathbb F_2[\alpha]$ donde $\alpha^2 = \alpha + 1$. Aquí, $\alpha$ corresponde a uno de los singleton pone en $X$, e $\alpha^2$ a la otra (por supuesto, por connaturalidad no importa cual es cual!), mientras que $0 = \varnothing$$1 = X$. Usando la distributividad de $\cap$$\triangle$, podemos reescribir esto como $$U \cdot V = (s^*U \cap s^*V) \triangle (s^*U \cap V) \triangle (U \cap s^*V).$$ Una muestra de que las operaciones de acuerdo $\triangle$ $\cdot$ está de acuerdo con la suma y la multiplicación en $\mathbb F_4$, respectivamente, y, por tanto, a fortiori, el producto $\cdot$ es asociativa, etc.

Finalmente, en el caso de $n=1$, la respuesta es trivialmente sí: el habitual de operaciones ( $\triangle$ $\cap$ ) dan el campo de la $2$ elementos.

Observación. Podemos utilizar métodos similares para mostrar que no son ni naturales operaciones en $\mathcal P(X)$ lo que es isomorphisc como un anillo a $\mathbb Z/2^n \mathbb Z$: el último sólo ha $1$ anillo automorphism.

Nuestro segundo argumento incluso muestra que la subyacente estructura de grupo en la $\mathbb Z/2^n \mathbb Z$ no está dada por un conjunto de operaciones para $n > 1$, ya que tiene elementos de orden $> 2$.