Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers - MathOverflow

Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

2010-03-23T00:50:42Z

Some MOers have been skeptic whether something like natural number graphs can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [1], [2], [3], [4])

Without attempting to give a general definition of natural number graphs, I invite you to consider the following

DEFINITION

A natural number $d$ may be called demi-prime iff there is a prime number $p$ such that $d = (p+1)/2$. The demi-primes' distribution is exactly like the primes, only shrinked by the 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, ...$$

Let D($k,n$) be the set which consists of the $k$-th up to the $(k+n-1)$-th demi-prime number.

After some - mildly exhaustive - calculations I feel quite confident to make the following

CONJECTURE

For every finite graph $G$ there is a $k$ and a bijection $d$ from the vertex set $V(G)$ to D($k,|G|$) such that $x,y$ are adjacent if and only if $d(x),d(y)$ are coprime.

I managed to show this rigorously for all graphs of order $n\leq $ 5 by brut force calculation, having to take into account all (demi-)primes $d$ up to the 1,265,487^th one for graphs of order 5. For graphs of order 4, the first 1,233 primes did suffice, for graphs of order 3 the first 18 ones.

Looking at some generated statistics for $n \leq$ 9 reveals interesting facts⁽¹⁾⁽²⁾, correlations, and lack of correlations, and let it seem probable (at least to me) that the above conjecture also holds for graphs of order $n >$ 5.

Having boiled down my initial intuition to a concrete predicate, I would like to pose the following

QUESTION

Has anyone a clue how to prove or disprove the above conjecture?

My impression is that the question is about the randomness of prime numbers: Are they distributed and their corresponding demi-primes composed randomly enough to mimick – via D($k,n$) and coprimeness – all (random) graphs?

⁽¹⁾ E.g., there is one graph of order 5 - quite unimpressive in graph theoretic terms - that is very hard to find compared to all the others: it takes 1,265,487 primes to find this guy, opposed to only 21,239 primes for the second hardest one. (Lesson learned: Never stop searching too early!) It's – to whom it is of interest – $K_2 \cup K_3$:

⁽²⁾ Added: This table shows the position of the smallest prime (among all primes) needed to mimick the named graphs of order $n$. All values not shown are greater than $\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 by Tony Huynh for Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

2010-03-23T01:47:25Z

I don't really know the answer, but I suppose I would first start by trying to disprove the conjecture. After all, it has only been verified for graphs up to order 5. The obvious counterexamples I would check are large cliques and large anti-cliques.

So, do there exist arbitrary long sequences of consecutive demi-primes that are pairwise co-prime? What about arbitrary long sequences of consecutive demi-primes such that each pair has a common factor?

The number theorists can feel free to chime in here anytime.

If those don't work, then some other candidates for counterexamples would be large matchings or large cliques together with an isolated vertex.

Edit: I just read that it is strongly believed that there are arbitrarily long sequences of consecutive primes such that each prime is congruent to 3 (mod 4). If true, this would give a representation of arbitrarily large anti-cliques, since the corresponding sequence of demi-primes would all be even. Does anyone know if this has been proven?

Answer by Bjorn Poonen for Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

2010-03-23T02:11:40Z

Theorem: Schinzel's hypothesis H implies the conjecture.

Proof: Choose distinct primes $q_S > 100|G|$ indexed by the 2-element subsets $S$ of $G$. For each $i \in G$, let $Q_i$ be the set of $q_S$ for $S$ such that $i \in S$ and the edge $S$ is not part of $G$. Let $P_i$ be the product of the primes in $Q_i$. Let $P = 4 \prod_S q_S^2$.

By the Chinese remainder theorem, for each $i$ we can find a positive integer $a_i$ such that

$a_i \equiv 1 \bmod{\ell^2}$ for each prime $\ell \le 10|G|$,

$a_i \equiv q-1 \bmod{q^2}$ for each $q \in Q_i$, and

$a_i \equiv 1 \bmod{q_S}$ for each $q_S \notin Q_i$.

Moreover, we can choose the $a_i$ to be distinct. Let $J$ be the set of positive integers up to $\operatorname{max} a_i$, but excluding all of the $a$'s themselves (i.e., $J$ consists of the numbers in the gaps). For each $j \in J$ choose a prime $s_j$ much larger than all the $a_i$ and all the $q_S$.

Consider the linear polynomials $P n + a_i$ and $(P n + a_i + 1)/(2P_i)$ In $\mathbf{Z}[n]$. For each prime $\ell \le 10|G|$ and each $\ell$ of the form $q_S$, all these $2|G|$ polynomials are nonzero mod $\ell$ at $n=0$. For each other prime $\ell$, there exists $n$ such that all these polynomials are nonzero mod $\ell$, since $n$ needs to avoid no more than $2|G|$ residue classes mod $\ell$. Furthermore, we can impose the condition that $P n+j$ is divisible by $s_j^2$ for each $j \in J$, and still find $n$ as above. Therefore Schinzel's hypothesis H implies that there exist arbitrarily large positive integers $n$ such that the numbers $P n+a_i$ and $(P n + a_i + 1)/(2P_i)$ are all prime, and such that $P n+j$ is not prime for $j \in J$. This makes the numbers $p_i:=P n + a_i$ consecutive primes such that $(p_i+1)/2 = P_i r_i$ for some prime $r_i$. If $n$ is sufficiently large, then these primes $r_i$ are all distinct and larger than all of the $q_S$. So the greatest common factor of $(p_i+1)/2$ and $(p_j+1)/2$ for $i \ne j$ equals $1$ if there is an edge between $i$ and $j$, and $q_{\{i,j\}}$ otherwise. $\square$

Remark: Given how little is known about consecutive primes, it seems unlikely that the conjecture can be proved unconditionally. But at least now we can be confident that it's true!

Answer by Jon Awbrey for Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers

2010-04-28T15:04:23Z

On the general theme of Gödel codings of graphs, see my work on Riffs and Rotes, for example, here.