Uniendo la teoría de números y la de grafos: Una conjetura sobre los números primos

Question

Algunos MOers han sido escépticos sobre si algo como gráficos de números naturales puede definirse de forma coherente de manera que todo grafo finito sea isomorfo a dicho grafo. (Ver mis preguntas anteriores [ 1 ], [ 2 ], [ 3 ], [ 4 ])

Sin pretender dar una definición general de gráficos de números naturales Le invito a considerar lo siguiente

DEFINICIÓN

Un número natural $d$ puede llamarse demi-prime si existe un número primo $p$ tal que $d = (p+1)/2$ . La distribución de los semiprimas es exactamente como la de los primos, sólo que encogida por el factor $2$ :

$$2, 3, 4, 6, 7, 9, 10, 12, 15, 16, 19, 21, 22, 24, 27, 30, 31, 34, 36, 37, 40, 42, 45, 49, ...$$

Dejemos que D ( $k,n$ ) es el conjunto formado por de los $k$ -hasta el $(k+n-1)$ -th número demi-primo.

Después de algunos cálculos -ligeramente exhaustivos- me siento bastante seguro de hacer lo siguiente

CONJUNTO

Para todo gráfico finito $G$ hay un $k$ y una biyección $d$ del conjunto de vértices $V(G)$ a D ( $k,|G|$ ) tal que $x,y$ son adyacentes si y sólo si $d(x),d(y)$ son coprime .

He conseguido demostrarlo rigurosamente para todos los gráficos de orden $n\leq $ 5 por cálculo de fuerza bruta, debiendo tener en cuenta todos los (demi-)primos $d$ hasta los 1.265.487 th uno para los gráficos de orden 5. Para los gráficos de orden 4, los primeros 1.233 primos fueron suficientes, para los gráficos de orden 3 los primeros 18.

Si se observan algunas estadísticas generadas para $n \leq$ 9 revela datos interesantes (1)(2) y que parezca probable (al menos para mí) que la conjetura anterior también es válida para los gráficos de orden $n >$ 5.

Habiendo reducido mi intuición inicial a un predicado concreto, me gustaría plantear lo siguiente

PREGUNTA

¿Tiene alguien alguna idea de cómo probar o refutar la conjetura anterior?

Mi impresión es que la pregunta es sobre la aleatoriedad de los números primos: ¿Están distribuidos y sus correspondientes demi-primos compuestos lo suficientemente al azar como para imitar - vía D ( $k,n$ ) y la coprimidad - ¿todos los gráficos (aleatorios)?

---

(1) Por ejemplo, hay un gráfico de orden 5 -bastante poco impresionante en términos de teoría de grafos- que es muy difícil de encontrar en comparación con todos los demás: se necesitan 1.265.487 primos para encontrar este tipo, frente a sólo 21.239 primos para el segundo más difícil. (Lección aprendida: ¡nunca dejes de buscar antes de tiempo!) Es -para quien sea de interés- $K_2 \cup K_3$ :

0 1 0 0 0
1 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0

(2) Añadido: Esta tabla muestra la posición del primo más pequeño (entre todos los primos) necesario para imitar los gráficos nombrados de orden $n$ . Todos los valores no mostrados son mayores que $\approx 2,000,000$

order    |   3     4      5      6       7      8
-------------------------------------------------
empty    |  14    45     89     89      89   3874 
complete |   5    64    336   1040   10864  96515 
path     |   1     6   3063  21814  
cycle    |   5   112  21235  49957

Answer 1

Teorema: La hipótesis H de Schinzel implica la conjetura.

Prueba: Elegir primos distintos $q_S > 100|G|$ indexado por los subconjuntos de 2 elementos $S$ de $G$ . Para cada $i \in G$ , dejemos que $Q_i$ sea el conjunto de $q_S$ para $S$ tal que $i \in S$ y el borde $S$ no forma parte de $G$ . Sea $P_i$ sea el producto de los primos en $Q_i$ . Sea $P = 4 \prod_S q_S^2$ .

Por el teorema del resto chino, para cada $i$ podemos encontrar un número entero positivo $a_i$ tal que

$a_i \equiv 1 \bmod{\ell^2}$ para cada primo $\ell \le 10|G|$ ,

$a_i \equiv q-1 \bmod{q^2}$ para cada $q \in Q_i$ y

$a_i \equiv 1 \bmod{q_S}$ para cada $q_S \notin Q_i$ .

Además, podemos elegir el $a_i$ para ser distintos. Sea $J$ sea el conjunto de enteros positivos hasta $\operatorname{max} a_i$ pero excluyendo todos los $a$ (es decir, $J$ consiste en los números de los huecos). Para cada $j \in J$ elegir un primo $s_j$ mucho más grande que todos los $a_i$ y todos los $q_S$ .

Consideremos los polinomios lineales $P n + a_i$ y $(P n + a_i + 1)/(2P_i)$ En $\mathbf{Z}[n]$ . Para cada primo $\ell \le 10|G|$ y cada $\ell$ de la forma $q_S$ Todos estos $2|G|$ los polinomios son distintos de cero mod $\ell$ en $n=0$ . Para cada uno de los otros primos $\ell$ existe $n$ tal que todos estos polinomios son distintos de cero mod $\ell$ ya que $n$ necesita evitar no más de $2|G|$ clases de residuos mod $\ell$ . Además, podemos imponer la condición de que $P n+j$ es divisible por $s_j^2$ para cada $j \in J$ y aún así encontrar $n$ como en el caso anterior. Por tanto, la hipótesis H de Schinzel implica que existen enteros positivos arbitrariamente grandes $n$ tal que los números $P n+a_i$ y $(P n + a_i + 1)/(2P_i)$ son todos primos, y tales que $P n+j$ no es primordial para $j \in J$ . Esto hace que los números $p_i:=P n + a_i$ consecutivos primos tales que $(p_i+1)/2 = P_i r_i$ para algún primo $r_i$ . Si $n$ es suficientemente grande, entonces estos primos $r_i$ son todos distintos y más grandes que todos los $q_S$ . Así que el mayor factor común de $(p_i+1)/2$ y $(p_j+1)/2$ para $i \ne j$ es igual a $1$ si hay una arista entre $i$ y $j$ y $q_{\{i,j\}}$ de lo contrario. $\square$

---

Observación: Dado lo poco que se sabe sobre los primos consecutivos, parece poco probable que la conjetura pueda demostrarse incondicionalmente. Pero al menos ahora podemos estar seguros de que es cierta.

Answer 2

No sé realmente la respuesta, pero supongo que primero empezaría por intentar refutar la conjetura. Al fin y al cabo, sólo se ha verificado para grafos de hasta orden 5. Los contraejemplos obvios que yo comprobaría son las camarillas grandes y las anticlillas grandes.

Entonces, ¿existen secuencias largas arbitrarias de semiprimas consecutivos que sean coprimas por parejas? ¿Y qué pasa con las secuencias largas arbitrarias de demi-primos consecutivos que tienen un factor común en cada par?

Los teóricos de los números pueden sentirse libres de intervenir aquí cuando quieran.

Si estos no funcionan, otros candidatos a contraejemplos serían los emparejamientos grandes o las camarillas grandes junto con un vértice aislado.

Edit : Acabo de leer que se cree firmemente que hay secuencias arbitrariamente largas de primos consecutivos tales que cada primo es congruente con 3 (mod 4). De ser cierto, esto daría una representación de anticliques arbitrariamente grandes, ya que la correspondiente secuencia de demi-primos sería toda par. ¿Sabe alguien si esto se ha demostrado?

Answer 3

Sobre el tema general de las codificaciones de Gödel de los grafos, véase mi trabajo sobre Riffs y Rotes, por ejemplo, aquí .