Let $(a_1,b_1), \dots, (a_k,b_k)$ be finitely many pairs of positive integers, and let $\Gamma$ be the graph whose vertices are the prime numbers and in which two vertices $p$ and $q$ are connected by an edge if and only if $a_ip + b_i = q$ or $a_iq + b_i = p$ for some $i \in \{1, \dots, k\}$.

Question: Is it true that necessarily all connected components of $\Gamma$ are finite?

Update of May 21, 2018: So far this question has gathered two deleted answers.

  • 6
    $\begingroup$ @BrevanEllefsen: E.g. edges of the form ($p, 2p+1$) can bridge arbitrarily large gaps. -- So, no. $\endgroup$ – Stefan Kohl May 13 '18 at 16:10
  • 5
    $\begingroup$ @მამუკაჯიბლაძე: Well -- for $k = 1$ the assertion is merely that a trajectory of a mapping of the form $n \mapsto an+b$ cannot consist of prime numbers only. For any modulus $m$ coprime to $a$, any such trajectory is periodic modulo $m$. Now take $m$ to be one of the iterates. Then after one period (mod $m$) there is another iterate which is divisible by $m$ but larger than $m$ -- so not a prime number. -- Case done. -- In other words -- the difficulty in answering the question comes from having multiple affine mappings to choose from. $\endgroup$ – Stefan Kohl May 14 '18 at 12:19
  • 2
    $\begingroup$ Just a remark: The union (call it $U$) of all connected components that are not singletons should have $0$ relative density within the primes: Denote by $\mathbb{P}$ the set of primes. For any fixed $a,b\in\mathbb{N}$, the set $\{p\in\mathbb{P}:ap+b\in\mathbb{P}\}$ should have $0$ relative density within the primes (I imagine this follows "easily" from sieve theory but I could only find references when $a=1$) and so a finite union of such sets still has relative density $0$. And $U$ is contained in this union. $\endgroup$ – Joel Moreira May 14 '18 at 19:28
  • 2
    $\begingroup$ @StefanKohl of course, but that is not what I´m talking about, my question is if one can find some fixed values $(a_i,b_i)$, such that for any natural number $N$, there is a connected component of size greater than $N$, which trivially is the only way one can make sense to my question. $\endgroup$ – Gerardo Arizmendi May 15 '18 at 4:54
  • 2
    $\begingroup$ @GerardoArizmendi Assuming the Dickson conjecture (en.wikipedia.org/wiki/Dickson%27s_conjecture) we should expect arbitrarily large components even when $k=1$. For instance, let $a_1=2,b_1=1$, then the statement that there exists a connected component with cardinality $M$ is equivalent to the existence of a prime $p$ such that $2^kp+2^k-1$ is prime for every $k=0,\dots,M$. $\endgroup$ – Joel Moreira May 15 '18 at 23:12

(After I finished writing the paragraphs below, I realized that the assumption that the affine step was a partial matching (paths only of length 1) was wrong. I suggest studying the model anyway with a subset of the affine step represented as a matching, and then relaxing this to K steps where J of them are matchings, and see how the estimates change. My guess is that when J is more than K/2, the quality of the estimates does not change much and the answer will still be no, the connected components will not grow significantly.)

Short (non-)answer: I don't know.

Long (also non-) answer: I suspect not, based on heuristics involving random partial matchings in graphs. In addition to other computer experiments to try, I suggest modelling the problem along the lines below.

The affine step for a given relation can be thought of as a partial matching between some vertices in a graph. Instead of walking to infinity, let us consider how large a connected component can be when using a graph with N primes and picking K many partial matchings. I will freely ignore multiplicative constant factors and make reasonable but unverified estimates in this model.

Each step thus is represented by about N/(log N) edges in the graph. (If Hardy and Littlewood can guess at the number of twin prime pairs, I can assume 1/log N fraction of edges with likely the same reasoning and different numeric, but don't take my word for it. A reasonable experiment would see how reality contrasts with this estimate.) So a subset of vertices about the 1/log N the size of the whole graph is involved in the matching. If we wanted to connect the whole graph, we would need K to be at least log N.

If we were choosing subsets at random, two of these subsets would have an intersection about 1/(log N)^2 the size of the whole set, and for K of these the size of the common intersection would vary widely but would be expected to be about 1/(log N)^K, for K reasonably small. The union would be expected to be about a little less than K*(log N) in size.

For K=2, note that if we want a path longer than length 2, one of the edges of the matching has to belong to the intersection of (the subsets of vertices involved in) the two matchings. This is less likely, and I imagine that of the vertices in the intersection, much less than 1/log N match one another. While longer paths are possible, I expect adding an edge decreases the count of such paths of that length by a factor of log N or more.

My guess is that for K fixed, increasing N drops the likelihood of a path of length L to zero.

Gerhard "Start With Assuming No Iterates" Paseman, 2018.05.21.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.