# 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

## 2 Answers

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?

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.