¿Qué grosor tiene el recíproco de los cuadrados

Question

Existe un único conjunto no vacío $B$ de enteros no negativos tales que todo número entero positivo puede escribirse de la forma $$b + s^2, b\in B, s\ge0$$ en un número par de formas.

$B = \{0, 1, 2, 3, 5, 7, 8, 9, 13, 17, 18, 23, 27, 29, 31, 32, 35, 37,$ $ 39, 41, 45, 47, 49, 50, 53, 55, 59, 61, 63, 71, 72,$ $ 73, 79, 81, 83, 87, 89, 91, 97, 98, 101, 103, 107,$ $ 109, 113, 115, 117, 121, 127, 128, 137, 139, 149,$ $ 151, 153, 157, 159, 162, 167, 171, 173, 181, 183,$ $ 191, 193, 197,\dots\}$

¿El conjunto $B$ tienen densidad positiva?

Ahora un poco de contexto. Cada conjunto $A$ de enteros no negativos que contiene 0 tiene un conjunto único $B$ de enteros no negativos de forma que $$\left( \sum_{a\in A} q^a \right) \, \left( \sum_{b\in B} q^b \right) = 1$$ en el ring ${\mathbb F}_2[[q]]$ de series de potencias binarias. Llamamos $B$ el recíproco de $A$ .

Como consecuencia del teorema del número pentagonal de Euler, el recíproco del conjunto $\{n(3n+1)/2 \colon n \in \mathbb{Z}\}$ es el conjunto $\{ n \colon p(n)\equiv 1 \bmod 2\}$ donde $p(n)$ es la función de partición ordinaria. No se sabe casi nada interesante sobre la paridad de la función de partición, pero computacionalmente parece ser par e impar con igual frecuencia. Esta pregunta surge de un esfuerzo por situar la paridad de la función de partición en algún contexto.

En este artículo ( arxiv , Int. J. Number Theory 2 (2006), no. 4, 499--522 ), Josh Cooper, Dennis Eichhorn y yo investigamos las propiedades del $A$ que conducen a $B$ que tiene densidad positiva, y todos nuestros datos y resultados parciales pueden resumirse en la siguiente conjetura:

Conjetura : Si $A$ contiene 0, no es periódica, y es uniformemente en cada clase de congruencia módulo de cada potencia de 2, entonces $B$ tiene densidad positiva.

Dejar $A$ sea el conjunto de los cuadrados, pudimos demostrar que los números pares en $B$ son exactamente $\{2k^2 \colon k\ge 0\}$ y pudimos clasificar los $1\mod 4$ elementos de $B$ .

Actualización La respuesta de Greg Kuperberg sobre la conjetura expuesta más arriba es, aunque no del todo refutable, totalmente convincente. Tan convincente que ya no entiendo cómo pude pensar que la conjetura pudiera ser cierta. En nuestro papel La describimos como "la conjetura más sólida que concuerda con nuestros teoremas, nuestros experimentos y la conjetura 1.1", así que veo que no estábamos demasiado entusiasmados con su veracidad. Deberíamos haberlo sido aún menos.

La pregunta planteada directamente, la densidad del recíproco de los cuadrados, sigue sin respuesta. Paul Monsky ha introducido un nuevo (para mí, al menos) enfoque, y ha hecho sorprendentes progresos tanto en la respuesta que sigue como en su respuesta a esta pregunta .

Me encanta la respuesta de Greg a la pregunta que no me atreví a hacer, y quiero aceptarla, pero la de Paul es más directamente relevante para la pregunta que sí hice.

He aquí algunos recuentos computacionales del número de elementos de $B\cap[0,2^{23}]$ en determinadas clases de congruencia.

(1 mod 4, 371867), (3 mod 4, 760697)
(1 mod 8, 185336), (5 mod 8, 186531), (3 mod 8, 294045), (7 mod 8, 466652)
(1 mod 16, 92703), (5 mod 16, 93236), (9 mod 16, 92633), (13 mod 16, 93295),
(3 mod 16, 147232), (11 mod 16, 146813),
(7 mod 16, 204808), (15 mod 16, 261844)
(7 mod 32, 102487), (23 mod 32, 102321), 
(15 mod 32, 130895), (31 mod 32, 130949)

Como había una petición específica de datos 15 mod 32, aquí están los 10 primeros números de este tipo en $B$ : (47,79,271,559,623,687,719,815,879,911). He aquí los 10 últimos que he calculado: (8388539, 8388551, 8388559, 8388563, 8388567, 8388571, 8388581, 8388591, 8388593, 8388603, 8388607)

Answer 1

En una pregunta relacionada, (¿Por qué suele haber..), O'Bryant caracterizó los elementos de B que = 3 mod 8, y preguntó por qué el número de tales que son como máximo X parece ser pequeño; mi respuesta a su pregunta mostró que el número es O(Xloglog(X)/log(X). respuesta a su pregunta mostró que el número es O(Xloglog(X)/log(X)). En esta respuesta esbozaré una prueba de que el mismo resultado es válido para elementos de B que =7 mod 16. (El caso caso restante de elementos que =15 mod 16 parece mucho más difícil). Necesitamos un resultado de caracterización:

Lemma : Sea g en Z/2[[x]] 1+x+x^4+x^9+.., siendo los exponentes los cuadrados. Si n=16m+1 el coeficiente de x^n en 1/g^7 es 1 precisamente cuando n es un cuadrado.

Para ver esto dejemos que f=1+x+x^3+x^6+.., siendo los exponentes los números triangulares. Entonces xf^8+g= g^4, por lo que 1/g^7=(xf^8/g^8)+(1/g^4). Como n es impar, el coeficiente en cuestión es el de x^n en xf^8/g^8, que es el coeficiente de x^2m en f/g. La respuesta a mi pregunta MO, "Variaciones..", muestra que es 1 precisamente cuando 2m es triangular, es decir, cuando n es un cuadrado.

Resultado de la caracterización: Supongamos k=7 (16). Entonces k está en B precisamente cuando el número de formas de escribir k como 2(cuadrado)+4(cuadrado)+cuadrado es impar.

Prueba: 1/g=(g^2) (g^4) (1/g^7). Así que el coeficiente de x^k en 1/g es la reducción mod 2 de el número de formas de escribir k como 2(cuadrado)+4(cuadrado)+(el exponente,c, de un monomio que aparece de forma no trivial en 1/g^7). c debe ser impar, y como 1/g^7=g/g^8, c=1 (8). Si c=9 (16), entonces mod 16, 7=2(cuadrado)+4(cuadrado)+9, lo cual es imposible. Entonces c=1 (16), y por el lema c es un cuadrado. A la inversa, si k=2(cuadrado) +4(cuadrado) +un cuadrado s, entonces s=1 (16), y el lema demuestra que x^(s) aparece de forma no trivial en 1/g^7.

Teorema: Supongamos k en B=7(16). Entonces hay a lo sumo 2 primos que ocurren al exponente impar en la factorización de k. Así que el número de tales k en B que son a lo sumo X es O(Xloglog(X)/ log(X)).

(La prueba sigue las mismas líneas que mi respuesta al problema del cuadrado 11 de O'Bryant, pero ahora hay que trabajar con la forma ternaria x^2+y^2+2*z^2 en lugar de la x^2+y^2+z^2 de Gauss).

Answer 2

[ Edita: Estoy reescribiendo muchas cosas en respuesta a los comentarios y a las claras deficiencias y errores de las versiones anteriores de la respuesta].

Como en su artículo, expresemos las secuencias como series de potencias binarias $a(x)$ y $b(x)$ de modo que su relación es la ecuación $a(x)b(x) = 1$ . (Sólo estoy cambiando su variable de $q$ a $x$ .) Mi conjetura es que si elige $b(x)$ al azar con densidad lentamente decreciente, entonces con probabilidad 1, el recíproco $a(x)$ está uniformemente distribuida en cada clase de congruencia módulo de cada $n$ . De hecho, conjeturo mucho más, que $a(x)$ es indistinguible de uniformemente aleatoria según una variedad de comprobaciones estadísticas locales.

Es importante tener en cuenta algunos principios estadísticos de los bits aleatorios. En primer lugar, dada una lista finita $L$ de bits aleatorios, toda la información de correlación conjunta de los mismos se expresa mediante los sesgos de las sumas de subconjuntos de los bits en $L$ Estos sesgos son una transformación de Hadamard de la distribución de probabilidad conjunta de los bits. En particular, si todas estas sumas son insesgadas, entonces los bits de $L$ son independientes e imparciales. En segundo lugar, si se define el sesgo de un bit $b$ ser la expectativa $E[(-1)^b]$ entonces estos sesgos se multiplican al añadir bits independientes. Tercero, si $L$ es una lista finita de bits y el sesgo medio de $a+b$ para un par de bits $a$ y $b$ en $L$ es bajo, entonces aproximadamente la mitad de los bits en $L$ son 0 y aproximadamente la mitad son $1$ . Si el tamaño de $L$ va a $\infty$ y el sesgo medio $a+b$ va a $0$ entonces en el límite $L$ casi seguro que tiene densidad $1/2$ .

Consideremos primero un modelo de juguete en el que $b(x)$ es aleatorio como en el párrafo anterior, y $a(x) = b(x)c(x)$ donde $c(x)$ es alguna serie de potencias específica como $$c(x) = 1+x+x^4+x^9+\cdots.$$ Supongamos que el $x^n$ coeficiente de $b(x)$ es 1 con probabilidad $1/\ln (n+3)$ (decir). Entonces $a_n$ El $x^n$ coeficiente de $a(x)$ es una suma de bits sesgados independientes. Es fácil que haya suficientes términos en la suma como para que el sesgo de $c_n$ converge a 0 a medida que $n \to \infty$ . Además, en lugar de un término $a_n$ se puede observar el sesgo de $a'= a_k+a_n$ avec $k,n \gg 0$ . De nuevo, el sesgo es bajo porque hay contribuciones de muchos bits independientes. El cálculo correspondiente muestra que $a(x)$ tiene densidad $1/2$ casi seguro. Un cálculo más refinado muestra que los bits de $a(x)$ también están equidistribuidos módulo $n$ para cualquier $n$ además, que los subcadenas locales de los coeficientes de $a(x)$ de una longitud fija parecen aleatorios.

En el problema real, $a(x)$ viene dada por la ecuación funcional $$a(x) = b(x)a(x^2).$$ Esto es más complicado, pero $a(x^2)$ puede seguir desempeñando el papel de $c(x)$ . En concreto, podemos decir que el $x^n$ coeficiente de $b(x)a(x^2)$ es una suma de términos simples y compuestos, donde por definición los términos simples utilizan $b_k$ avec $k > n/2$ . Estas variables aleatorias no influyen $a(x^2)$ . Lo que creo que ocurre es que la suma de los términos simples es un bit con un sesgo muy bajo, y el sesgo no puede aumentarse añadiendo ninguna combinación hipotética de términos compuestos. Y, como en el modelo de juguete, se pueden tomar pares de bits $a_n+a_k$ avec $n, k \gg 0$ . Suponiendo que $n > k$ , $a_n$ contiene términos sencillos que no aparecen en $a_k$ y esto es suficiente para dar a su suma un sesgo bajo. La estadística de las subcadenas es otra complicación, pero vuelvo a pensar que una versión más complicada de la misma idea debería demostrar que $a(x)$ está equidistribuido, etc.

---

Por supuesto, lo anterior no es un argumento riguroso de que un azar $b(x)$ te da un contraejemplo. Para apoyar aún más el punto, escribí un programa de Sage para encontrar la distribución mod 32 de los bits de $a(x) = 1/b(x)$ al grado $2^{20}$ tomando $P[b_n = 1] = 1/\sqrt{n+1}$ .

bits = 2^20; radix = 32
R.<x> = PowerSeriesRing(Integers(2))
b = R([int(random() < 1/sqrt(n+1.)) for n in xrange(bits)]) + O(x^bits)
a = list(1/b)
distrib = [0]*radix
for n in xrange(len(a)):
    if a[n]: distrib[n%radix] += 1
print distrib`

Este es el resultado:

[16444, 16354, 16342, 16396, 16391, 16065, 16227, 16449, 16478,
16325, 16447, 16220, 16418, 16400, 16374, 16344, 16394, 16369,
16326, 16251, 16324, 16421, 16379, 16364, 16124, 16422, 16422,
16374, 16469, 16531, 16370, 16441]

---

Si el esquema anterior funciona, también motiva esta pregunta: Supongamos que un número $0 \le x \le 1$ se elige al azar con dígitos independientes pero sesgados en base $b$ . Para concretar supongamos que los dígitos son todos $0$ ou $1$ y que la densidad llega a 0 con suficiente lentitud. Entonces es $1/x$ en $b$ -número normal ¿casi seguro?

Answer 3

O'Bryant et. al. demostraron que los elementos de B en 12 de las clases de congruencia mod 16 forman un conjunto de densidad 0. En mi respuesta a esta pregunta y a otras 2 preguntas utilicé un resultado de Gauss para demostrar que los k en B que son 3, 7 u 11 mod 16 también forman conjuntos de densidad 0. Así que sólo queda el caso de k congruente a 15 mod 16.

NO OBSTANTE, creo que los resultados anteriores son algo accidentales, y que un k congruente con 15 (16) tiene "la misma probabilidad de estar en B que fuera de él", de modo que la densidad de B es 1/32. Aquí están los datos de respaldo, proporcionados por Kevin, para k<2^23.

k=15 (64): 2*(65536) elementos, 65446 en B

k=31 (64): 2*(65536) elementos, 65247 en B

k=47 (64): 2*(65536) elementos, 65449 en B

k=63 (64): 2*(65536) elementos, 65702 en B

Invitamos a los lectores a realizar otros cálculos, pero los anteriores son muy sugerentes.