43
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • 6
    $\begingroup$ @BrevanEllefsen: E.g. edges of the form ($p, 2p+1$) can bridge arbitrarily large gaps. -- So, no. $\endgroup$
    – Stefan Kohl ♦
    May 13, 2018 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, 2018 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, 2018 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, 2018 at 4:54
  • 3
    $\begingroup$ This smells like Collatz conjecture applied to an infinite subset of primes. It could be easily undecidable. I truly suspect it being very difficult. $\endgroup$
    – user113386
    May 18, 2018 at 19:58

1 Answer 1

Reset to default
2
$\begingroup$

(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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It seems to me that, with some tweaking maybe, what you wrote a is basically a euristic proof of the conjecture, which is probably all one can hope for currently. $\endgroup$
    – Yaakov Baruch
    Apr 6, 2021 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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