Número mínimo de operaciones $|\cdot|$ necesarias para expresar $\max$

Question

Para dos variables, su máximo $\max\{x_1,x_2\}$ se puede expresar usando una operación $|\cdot|$: $$ \max\{x_1,x_2\} = \frac12(x_1+x_2+|x_1-x_2|). $$ Para $3$ variables, parece bastante claro que son necesarias tres operaciones de $|\cdot|$, aunque solo puedo demostrar suficiencia: $$ \max\{x_1,x_2,x_3\} = \frac14\left[ 2x_1+x_2+x_3+|x_2-x_3|+2\left|x_1-\frac12(x_2+x_3+|x_2-x_3|)\right| \right] . $$ Para $5$ variables, se ha afirmado aquí https://twitter.com/ereliuer_eteer/status/1669081421007454209 que el número mínimo de operaciones de $|\cdot|$ es 54, aunque no he verificado ni la suficiencia ni la necesidad.

Pregunta: ¿Cuántas operaciones de $|\cdot|$ son necesarias para $n$ variables? Para ser explícito acerca de las reglas, además de $|\cdot|$, se permiten las 4 operaciones aritméticas.

Actualización. Ese post de Twitter al que enlacé en realidad está calculando la mediana, no el máximo de 5 variables. Entonces la pregunta análoga para la complejidad de operaciones absolutas, pero ahora para la mediana, es bastante natural.

Answer 1

Sea $f(k)$ el número mínimo de operaciones $|\cdot|$ para expresar el máximo de $2^k$ variables. Utilizando las identidades $$\max\{x_1,x_2\} = (x_1+x_2+|x_1-x_2|)/2,$$ $$\max\{x_1,\ldots,x_{2^{k+1}}\} = \max\{\max\{x_1,\ldots,x_{2^k}\},\max\{x_{2^k+1},\ldots,x_{2^{k+1}}\}\},$$ se sigue que $f(1)=1$ y $f(k+1)\leq 4f(k)+1$. Por lo tanto, se concluye por inducción que $$f(k)\leq (4^k-1)/3.$$ Ahora consideremos el caso de $n$ variables. Si $2^{k-1}, entonces el número mínimo de operaciones correspondientes $|\cdot|$ es menor que $4^k/3$, que es menor que $(4/3)n^2$.

Añadido. De hecho, el número mínimo de operaciones $|\cdot|$ es menor que $(3/8)n^2$. Para más detalles, consulte la respuesta de AspiringMat y los comentarios a continuación.

Answer 2

Esta es solo un análisis más estricto del análisis de @GH de MO.

Sea $f(n)$ el número mínimo de operaciones $|\cdot|$ para calcular $\max(x_1, \ldots, x_n)$. Entonces $f(1)=0$ y para $n\geq 1$:

$$f(n)\leq 1+2\min_{1\leq j < n}\left( f(j)+f(n-j)\right)$$

Generando los primeros valores, obtenemos para $n\geq 2$: $1, 3, 5, 9, 13, 17, \ldots$ que, al insertar en OEIS, da como resultado esta secuencia (Desplazada por 2). Al ingresar, obtenemos

$$f(n) \leq n 2^{\lfloor \log_2(n) \rfloor } - \frac{2\cdot 4^{\lfloor \log_2(n) \rfloor} + 1}{3}$$

En las notas, se menciona que esta es la solución a la recurrencia $$a(n)=1+2a(\lfloor n/2 \rfloor)+2a(\lceil n/2 \rceil) $$ lo que sugiere que la minimización anterior ocurre precisamente en $j=\lfloor n/2 \rfloor$.

El límite superior se comporta como $1/3 n^2$. Comparando el límite superior anterior y $4/3 n^2$, obtenemos:

Una nota interesante es que si consideramos el PD

$$f(n)\leq \min_{i,j | 0\leq i+j

Lo cual utiliza la segunda identidad en la respuesta del OP ($x_1$ aparece dos veces, y $x_2, x_3$ aparecen 4 veces, con $3$ extra $|\cdot|$), entonces parece minimizarse precisamente en los mismos mínimos que en el caso 2D. Sería interesante si hay expresiones alternativas para $n=3$ que utilicen menos variables y que puedan usarse para obtener mejores límites.