# 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?

• Have you tried to list such $N$ for small values, say $N\le 10000$? it should be easy with any mathematical software. – YCor May 22 '20 at 14:52
• If my program is correct, it works for all $N$ from 2 to $200$. – Robert Israel May 22 '20 at 15:02
• Almost certainly. Note that all the products have to be even, and avoid being "in the middle" of large prime gaps, which (for small n) is about a third of the even numbers, and each such rules out something less than N pairings. So (2 13) and (2 17) and pairs multiplying to 50 and 56 are ruled out, etc. This should leave enough for a Hall argument to work. Gerhard "Plan For Many June Nuptials" Paseman, 2020.05.22. – Gerhard Paseman May 22 '20 at 15:10
• @GerhardPaseman: since primes (and hence $\{p\pm1\}$) have density zero, I'm doubtful that such an argument is going to work. – Greg Martin May 22 '20 at 16:38
• @Greg, if you have a heuristic argument that there are N which won't work, I think that would be a useful answer post. I will admit the possibility that such N exist, but I think using a density zero argument will itself fail to indicate failure. I think the factorization of p+-1 numbers are the key, and I suspect one can set up a Hall argument based on this. Gerhard "Working Towards A Happy Ending" Paseman, 2020.05.22. – Gerhard Paseman May 22 '20 at 17:37

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$$.
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?