Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T02:53:56Z http://mathoverflow.net/feeds/question/19076 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19076/bringing-number-and-graph-theory-together-a-conjecture-on-prime-numbers Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers Hans Stricker 2010-03-23T00:50:42Z 2010-04-28T15:04:23Z <p>Some MOers have been skeptic whether something like <em>natural number graphs</em> can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [<a href="http://mathoverflow.net/questions/17989/can-every-finite-graph-be-represented-by-one-prescribed-sequence-of-natural-numbe" rel="nofollow">1</a>], [<a href="http://mathoverflow.net/questions/17875/can-every-finite-graph-be-represented-by-an-arithmetic-sequence-of-natural-number" rel="nofollow">2</a>], [<a href="http://mathoverflow.net/questions/18562/uniformly-computable-classes-of-graphs" rel="nofollow">3</a>], [<a href="http://mathoverflow.net/questions/11647/natural-models-of-graphs" rel="nofollow">4</a>])</p> <p>Without attempting to give a general definition of <em>natural number graphs</em>, I invite you to consider the following</p> <blockquote> <p><strong>DEFINITION</strong></p> <p>A natural number $d$ may be called <strong>demi-prime</strong> 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$:</p> <p>$$2, 3, 4, 6, 7, 9, 10, 12, 15, 16, 19, 21, 22, 24, 27, 30, 31, 34, 36, 37, 40, 42, 45, 49, ...$$</p> <p>Let <strong>D</strong>($k,n$) be the set which consists of the $k$-th up to the $(k+n-1)$-th demi-prime number. </p> </blockquote> <p>After some - mildly exhaustive - calculations I feel quite confident to make the following</p> <blockquote> <p><strong>CONJECTURE</strong></p> <p>For every finite graph $G$ there is a $k$ and a bijection $d$ from the vertex set $V(G)$ to <strong>D</strong>($k,|G|$) such that $x,y$ are adjacent if and only if $d(x),d(y)$ are <strong>coprime</strong>.</p> </blockquote> <p>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<sup>th</sup> 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. </p> <p>Looking at some generated statistics for $n \leq$ 9 reveals interesting facts<sup>(1)(2)</sup>, 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. </p> <p>Having boiled down my initial intuition to a concrete predicate, I would like to pose the following</p> <blockquote> <p><strong>QUESTION</strong></p> <p>Has anyone a clue how to prove or disprove the above conjecture?</p> </blockquote> <p>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 &#x2013; via <strong>D</strong>($k,n$) and coprimeness &#x2013; all (random) graphs? </p> <hr> <p><sup>(1)</sup> 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 &#x2013; to whom it is of interest &#x2013; $K_2 \cup K_3$:</p> <pre><code>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 </code></pre> <p><sup>(2)</sup> <strong>Added:</strong> 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$</p> <pre><code>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 </code></pre> http://mathoverflow.net/questions/19076/bringing-number-and-graph-theory-together-a-conjecture-on-prime-numbers/19078#19078 Answer by Tony Huynh for Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers Tony Huynh 2010-03-23T01:47:25Z 2010-03-23T04:29:47Z <p>I don't really know the answer, but I suppose I would first start by trying to <em>disprove</em> 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. </p> <p>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? </p> <p>The number theorists can feel free to chime in here anytime.</p> <p>If those don't work, then some other candidates for counterexamples would be large matchings or large cliques together with an isolated vertex.</p> <p><strong>Edit:</strong> 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?</p> http://mathoverflow.net/questions/19076/bringing-number-and-graph-theory-together-a-conjecture-on-prime-numbers/19080#19080 Answer by Bjorn Poonen for Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers Bjorn Poonen 2010-03-23T02:11:40Z 2010-03-23T06:02:04Z <p><strong>Theorem:</strong> Schinzel's hypothesis H implies the conjecture. </p> <p><strong>Proof:</strong> 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$.</p> <p>By the Chinese remainder theorem, for each $i$ we can find a positive integer $a_i$ such that </p> <p>$a_i \equiv 1 \bmod{\ell^2}$ for each prime $\ell \le 10|G|$,</p> <p>$a_i \equiv q-1 \bmod{q^2}$ for each $q \in Q_i$, and </p> <p>$a_i \equiv 1 \bmod{q_S}$ for each $q_S \notin Q_i$. </p> <p>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$.</p> <p>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$ <em>consecutive</em> 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 <code>$q_{\{i,j\}}$</code> otherwise. $\square$</p> <hr> <p><strong>Remark:</strong> 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!</p> http://mathoverflow.net/questions/19076/bringing-number-and-graph-theory-together-a-conjecture-on-prime-numbers/22862#22862 Answer by Jon Awbrey for Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers Jon Awbrey 2010-04-28T15:04:23Z 2010-04-28T15:04:23Z <p>On the general theme of Gödel codings of graphs, see my work on Riffs and Rotes, for example, <a href="http://oeis.org/wiki/Riffs_and_Rotes" rel="nofollow">here</a>.</p>