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

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,487th 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(1)(2), 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?

(1) 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$:

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) 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

-
It is slightly amusing that you call your search up to 5 mildly exhaustive :P –  Mariano Suárez-Alvarez Mar 23 '10 at 2:11
Exhaustive with regard to the 10 million primes I checked, not with regard to the order 5, of course. –  Hans Stricker Mar 23 '10 at 7:17
GREAT QUESTION! Aside the intrinsic mathematical interest, it also has a foundational/metamathematical one (see my last question on Ackermann' s Yoga): basically what you seem to be after is an interpretation of (finite) graph theory inside arithmetics. Now, graphs are are the ground for a lot of other stuff, for instance categories, so... –  Mirco Mannucci Jun 7 '11 at 14:06

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!

-
Are you kidding (in your remark)? Or are you really confident? (To be honest: I guess not.) –  Hans Stricker Mar 23 '10 at 7:06
@HS: I think Bjorn is serious. Schinzel's hypothesis is one of several "standard" conjectures in analytic number theory that most experts in the field strongly believe to be true. Indeed, lots of people believe it enough to prove theorems like "Assuming Schinzel's hypothesis to be true, it follows that..." as Bjorn has done here. –  Pete L. Clark Mar 23 '10 at 13:46
@Pete, thanks for the clarification, now I understand the remark better. –  Hans Stricker Mar 23 '10 at 13:58
That's good news! –  Hans Stricker Mar 23 '10 at 13:59
Nice! Btw: strictly speaking, the $s_j$ should be distinct... –  fherzig Apr 28 '10 at 23:27

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?

-
Yes, it has been proven - see MR1760689. –  David Hansen Mar 23 '10 at 5:19
A little more bibliographic detail on the paper David Hansen references: D K L Shiu, Strings of congruent primes, J London Math Soc (2) 61 (2000) 359-373. According to the review, the author proves that for any relatively prime $a$ and $q$, there exist arbitrarily long lists of consecutive primes, each congruent to $a$ modulo $q$. –  Gerry Myerson Mar 23 '10 at 6:12
What's the intuition behind your surmise that large cliques, matchings or cliques together with an isolated vertex are good candidates for counter-examples? –  Hans Stricker Mar 23 '10 at 7:22
Thanks David and Gerry for the references. Quite interesting. –  Tony Huynh Mar 23 '10 at 15:07
@Hans - I wouldn't say that they are good candidates for counterexamples, only that for large graphs they would be the first thing I would investigate. This is simply because it's hard to get to grips with the condition for other large graphs (even say a large tree). As I said, I had no intuition for the problem initially, it just looked easier to find a counterexample than to prove it so I took the lazy man's approach. Actually, after Gerry and David's references I started to believe that the conjecture is true, and after Bjorn's answer, I really believe it. Nice question. –  Tony Huynh Mar 23 '10 at 15:15

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

-