¿Podemos encontrar el promedio de tres números de esta manera?

Question

Deje $f_n$ denotar el "promedio" de la función $[0,1]^n \rightarrow [0,1]$ define de la siguiente manera. $$f_n(x_0,\cdots,x_{n-1}) = \frac{x_0 + \cdots + x_{n-1}}{n}$$

Entonces, claramente, es posible expresar $f_4$ en términos de $f_2$.

$$f_4(a,b,c,d) = \frac{a+b+c+d}{4} = \frac{\frac{a+b}{2}+\frac{c+d}{2}}{2} = f_2(f_2(a,b),f_2(c,d)).$$

Pregunta. Podemos expresar $f_3$ en términos de $f_2$ de esta manera, el uso de $0$ $1$ también, si fuera necesario? Tal vez esto es algo trivial, pero no puedo ver la respuesta.

Una más precisa declaración del problema.

Deje $A$ denotar el siguiente conjunto de "primitivos símbolos." $$\{a,b,c,0,1\}.$$ We define a class of "valid expressions" $B$ as the least superset of $$ such that if $\alpha,\beta \B$, then $f_2(\alpha,\beta) \in B$.

El problema puede ser resuelto de dos maneras, que se enumeran a continuación.

1. Opción 1. Encontrar una expresión en $B$ que define correctamente $f_3(a,b,c).$
2. Opción 2. Mostrar que no hay tal expresión existe.

Answer 1

No se puede construir la $f_3$ de tal manera.

Una primera solución, no el más riguroso, pero se tiene la idea de todo sin usar demasiado álgebra:

Deje $R$ ser cualquier anillo donde se $2$ es invertible. A continuación, $\frac{x+y}{2}$ se define en los elementos de $R$.

Esto nos permite definir un mapeo $\varphi: B \times R^3 \to R$ donde $\varphi(\beta,a,b,c)$ es el resultado de evaluar la expresión simbólica $\beta$, con los valores de $a,b,c \in R$ sustituidos.

(Por ejemplo, si $\beta = f_2(f_2(a,b),c)$,$\varphi(\beta,a,b,c) = \frac{a+b}{4} + \frac{c}2$.)

Supongamos que hay una expresión $\beta \in B$ tal que $\varphi(\beta,a,b,c) = \frac{a+b+c}{3}$. A continuación,$\varphi(\beta,1,0,0) = \frac{1}3$, y por lo $3$ es invertible en a $R$.

(Esta parte me molesta un poco, porque es un poco presuntuoso incluso escribir la expresión de la $\frac{a+b+c}{3}$. Tal vez sería mejor declaró que $3 \varphi(\beta,a,b,c) = a+b+c.$ cualquier manera, $3$ termina siendo invertible tan largo como el 2 es, si suponemos que podemos construir $f_3$ itera $f_2$, y dejarnos a sustituir en 1 y 0.)

Y, así, basta con señalar que hay anillos de $R$ 3 no es invertible, pero 2 es. Uno de esos anillo es $\mathbb{Z}/3$.

---

Tengo la intención de la solución anterior, para evitar posiblemente confuso abstracción, pero en respuesta a los comentarios a continuación voy a ser super riguroso:

Deje $S = \mathbb{Z}[\frac{1}2]$ denotar el anillo de los números racionales con denominador una potencia de dos. Podemos definir una asignación de conjuntos de $\tau : B \to S[a,b,c]$ mediante el envío de $a,b,c,0,1$ a sí mismos, y $f_2(x,y)$$\frac{1}2 (\tau(x) + \tau(y))$. Una simple inducción demuestra que la imagen de $\tau$ consiste únicamente lineal de los polinomios.

El mapa de $\tau$ se extiende linealmente a un mapa de $S-$módulos de $\varphi: SB \to S[a,b,c]$. Tenemos también el cambio de los anillos de morfismos $\theta : S[a,b,c] \to \mathbb{R}[a,b,c]$, y la evaluación de los mapas de $ev_{(x,y,z)} : \mathbb{R}[a,b,c] \to \mathbb{R}$.

Esto le da a las cadenas de $S$-módulo de morfismos

$$SB \xrightarrow{\varphi} S[a,b,c] \xrightarrow{\theta} \mathbb{R}[a,b,c] \xrightarrow{ev} \mathbb{R}.$$

donde $ev$ es uno de los muchos evaluación de los mapas podemos elegir.

El mapa de $\varphi$ también ha de imagen únicamente entre el lineal de los polinomios, mientras que $\theta$ es inyectiva y el grado de preservación.

Si $ev_{(x,y,z)}P = ev_{(x,y,z)} Q$ por cada $x,y,z \in [0,1]$, e $P,Q,$ son lineales, polinomios, a continuación,$P = Q$.

Por lo tanto, es suficiente para mostrar que no es $\beta \in SB$ tal que $\theta (\varphi(\beta)) = \frac{a+b+c}{3}.$

Prueba de reclamación: Supongamos lo contrario. A continuación,$\theta (3 \varphi(\beta)) = 3\theta (\varphi (\beta)) = a+b+c$. El mapa de $\theta$ es inyectiva, por lo $3\varphi(\beta) = a+b+c$. La evaluación en $(a,b,c) = (1,0,0)$ da $3\varphi(\beta)(1,0,0) = 1 \in S$; sin embargo, $3$ no es invertible en a $S$ (*). Esto le da una contradicción.

(*) Por varias razones: a pegarse a mi las armas un poco, un ser que, desde el $2$ es una unidad en $\mathbb{Z}/3$, no hay un único anillo de morfismos $S \to \mathbb{Z}/3$ ampliación de la canónica cociente mapa de $\mathbb{Z} \to \mathbb{Z}/3$. Como $3$ no es una unidad en $\mathbb{Z}/3$, no puede ser una unidad de $S$.

Answer 2

Vamos a probar algo un poco más general. Podemos demostrar que la composición no puede tomar el valor de $1/3$ cuando se suministra $0$'s y $1$'s como argumento. Definimos $B'$ a todas las funciones $[0,1]^n \to \mathbb{R}$ que puede ser escrito como una composición de $f_2$, $0$ y $1$.

Más precisamente, $B'$ es el más pequeño de superconjunto de a $A' = \{f_2,0,1\}$ donde $0,1$ son las constantes de las funciones, de tal manera que $B'$ es cerrado bajo la composición.

Es claro que el $B$ definido en el problema, interpretado adecuadamente, es un subconjunto de este.

1. $B'$ está dado por finito composiciones de elementos de $A'$, ya que este es un superconjunto de a $A'$ que es cerrado bajo la composición de $f_2$, y cualquier superconjunto debe contener finito composiciones. Este es un argumento estándar en definiciones recursivas. Más precisamente, vamos a $A_0' =A'$$A_{k+1}' = A_k' \cup \{f_2 \circ (\beta_1,\beta_2) \mid \beta_1,\beta_2 \in A_k'\}$. A continuación,$B' = \cup_k A_k'$. Para ser aún más precisos, se debe incluir arity $ar(\beta)$ de los elementos de la $\beta \in A_k'$ y la tupla $(\beta_1,\beta_2)$ tendrá diferentes opciones de arity entre el $\min(ar(\beta_1),ar(\beta_2))$ $ar(\beta_1)+ar(\beta_2)$ dependiendo de cómo se mezclan los argumentos.

2. Para cualquier $\beta \in B'$ de arity $n$, y cualquier $n$-vector $v$ $0$'s y $1$s, $\beta(v)$ es racional, y en la forma reducida, el denominador es una potencia de $2$. Esto es demostrado fácilmente a través de la inducción en $k$ anteriormente, ya que el $\beta \in A_k'$ algunos $k$.