Sea $N$ sea un número entero positivo. Queremos encontrar una función completamente multiplicativa $f(n)$ con valores $\pm 1$ para $n \le N$ tal que la discrepancia $$D=\max_{n \le N} |\{\sum_{i=1}^nf(i)\}|$$ sea lo más pequeño posible. Este es el problema de la discrepancia de Erdos para funciones multiplicativas.
Consideremos el siguiente algoritmo codicioso:
Después de asignar los valores $f(2),f(3),\dots f(p_i)$ para la primera $i$ primos asignan el valor $f(p_{i+1})$ para minimizar la discrepancia máxima $|\{\sum_{i=1}^nf(i)\}|$ en cada suma parcial en la que las entradas no asignadas de $f$ obtener el valor cero.
Pregunta: ¿Cómo funciona este algoritmo codicioso?
Se aceptan tanto respuestas experimentales o heurísticas como pruebas rigurosas.
Para más información y preguntas relacionadas, consulte esta entrada .
Variación
Consideremos el mismo algoritmo codicioso cuando se impone la condición de que $f(m)=0$ a menos que $m$ es cuadrado libre. (Si $m$ no es cuadrado libre $f$ es multiplicativo y tiene valores $\pm1$ .)
Pregunta: ¿Cómo funciona nuestro algoritmo codicioso en la versión sin cuadrados?
En concreto, nos gustaría entender el comportamiento de la discrepancia de la función obtenida por nuestro algoritmo codicioso. Mientras que para EDP existen ejemplos conocidos con $\log N$ discrepancia, esto no se conoce para la versión sin cuadrados.
Actualización:
La muy buena respuesta de rlo sugiere que el algoritmo codicioso da una discrepancia cercana a $n^{1/3}$ más o menos, y rlo lo espera también para la variación libre cuadrada. ¿Puede un límite superior de $N^{1/2-\epsilon}$ ¿se puede demostrar? ¿Y un límite inferior de $N^{\epsilon}$ . Otra cuestión interesante es si se puede mejorar el algoritmo codicioso para obtener una discrepancia menor. Nuestro codicioso ignorar 0 en los intervalos. Un algoritmo codicioso que ignorar los intervalos con 0's se consideró en polymath5 y a lo mejor de mi memoria lograr discrepancia $n^{1/2}$ . ¿Quizás una interpolación inteligente entre estas dos variantes haga un mejor trabajo que ambas?
Más meditación y una nueva variante
Parece que en nuestro algoritmo codicioso las decisiones que tomamos para primos pequeños son bastante irrelevantes. Una forma de comprobarlo:
Ejecuta el algoritmo para N y comprueba cuál es la discrepancia para un intervalo [1,T] donde T es, digamos, $\sqrt N$ . Yo esperaría que la respuesta fuera aproximadamente $\sqrt T$ .
Así que ahora podemos pensar en la siguiente variación:
Sea $a>1$ sea un número real. Ejecutamos el algoritmo codicioso anterior pero nuestra decisión para $f(p)$ se basa únicamente en intervalos $[1,n]$ donde $n \le p^a$ . (Por supuesto, sólo consideramos $n \le N$ .
Preguntas: ¿Puede esta variante conducir a una menor discrepancia?
¿Cuál es el valor óptimo de $a$ ?
