Pairs of integers whose product is one more or less than a prime Given a positive integer N it is often possible to pair each of the integers 1, 2, 3, ..., N with a different integer between N + 1 and 2 N so that the product of each pair is one less or more than a prime. 
For example, if N = 10, such a pairing is (1,12), (2,11), (3,14), (4,13), (5,16), (6,15), (7,18) (8,17), (9, 20), and (10, 19).
Is this possible for infinitely many N? For all, but a finite number of N?
 A: You can find the number of such prime numbers in special case. Denote $qk\pm 1=p$ with $k\in [N+1,2N]$ and $q\in [1,\log^A N]$. From this we will write the sum $\displaystyle \sum_{\substack{q(N+1)\leq p \leq 2qN \\ p \equiv (\pm 1 \mod q)}}1$ that controls the interval for $k$ and counts the prime numbers in the above form. An estimate for such a sum is made as for the proof of Siegel-Walfisz theorem, through equality $\displaystyle {\frac {1}{\phi (q)}}\sum _{\chi }{\bar {\chi }}(a)\chi (n)={\begin{cases}1,&{\text{ if }}n\equiv a{\pmod {q}}\\0,&{\text{ otherwise, }}\end{cases}}$ with $(a,q)=1$. We obtain $\displaystyle \sum_{\substack{q(N+1)\leq p \leq 2qN \\ p \equiv (\pm 1\mod q)}}1\sim \frac{qN}{\phi (q)\log N}$. (Linnik's theorem)[https://en.m.wikipedia.org/wiki/Linnik%27s_theorem] gives a larger interval for $q$, but not enough. Linnik's constant $L$ equal to $2$ will give the desired result since $q\leq (qN)^\frac{1}{2}$, under GRH $L=2+\epsilon$. 
A: Note that any such pairing gives products greater than $N$ and at most $2N^2$, and thus all the products must be even or the number 3. So with one exception, odd numbers at most N are paired with even numbers greater than N, and for N greater than 2 odd numbers greater than N are paired with even numbers less than N.  So what pairings do not lead to products of the desired form?
Let r be even with r not adjacent to a prime. The smallest r start with 26, then 34,50,56,64,76,86,92,94,116,118,120,122,124,134.  A paring is a factorization of one of these special even numbers (p,q) with the product being r and one of the factors being odd.  Skipping the case that the odd number is 1, we have in most cases these numbers have one odd factor, with the exceptions in the previous list being 50,64, and 120.  In this small sample, we have  on average little more than one forbidden edge for each candidate.  This supports the notion that for small N one can always find a mapping.
Also, not every disallowed edge needs to be considered. If 210 were a disallowed product (it isn't) then (2,105) would be a problem edge only for N in (52,105), and (14,15) only for N=14, so not all seven possibilities (excluding (1,210) are in play for any given N.  So the number of bad edges blocking a matching appears to be small.  Again ignoring 1, these edges are (5,10),(2,13),(2,17),(2,25),(7,8),(4,19),(4,23)(2,47), on up. This means one problem edge for N=5, 3 for N=7, 2 for N=8, 3 for N=9, and so on. Given that when N=10 there are fifty edges with five coming from each vertex, having three problem edges seems like nothing. (If we include 1, there are more problem edges, but there are also many edges coming from 1 on the order of 2N/ln(2N) many.)
It seems reasonable to estimate (and challenging to prove, which I won't do now) that for every N, that the product graph (which associates to each k less than n those j in (N,2N] for which kj is adjacent to a prime) for N described above has each node with a degree about N/(2ln N).  This does not prove there is a matching, but I think it makes it very likely, especially since the (set of) vertices connected to a j less than N will often be quite different to (set of) those connected to a k less than N. Unfortunately, we need something like Linnik's theorem to show no isolated vertices in this graph.
Gerhard "Not Strengthening Linnik's Theorem Yet" Paseman, 2020.05.24.
