18
$\begingroup$

Is the following problem still open? Let $S$ be a non-empty set of prime numbers such that whenever $p,q\in S$, all the prime factors of $pq+1$ are also elements of $S$. Is $S$ infinite?

$\endgroup$
3
  • 8
    $\begingroup$ If one replaces "all the prime factors" by the weaker condition "some prime factor" then the answer is no, an example is given by $\{2,5,11,23,47\}$. $\endgroup$ Dec 26, 2011 at 13:30
  • 7
    $\begingroup$ When you say "still open": do you know of anyone asking the question before you? $\endgroup$
    – Igor Rivin
    Dec 26, 2011 at 14:54
  • $\begingroup$ It appears that $S$ is infinite, even when we restrict to the case $p=q$. Why did you focus on two elements of $S$? Is the result known if we allow some fixed number of elements of $S$? $\endgroup$ Jan 2, 2012 at 18:52

4 Answers 4

10
$\begingroup$

The answer is most probably "It is always the set of all prime numbers or empty". Indeed, assume that $S$ is not empty. First of all, $S$ must contain $2$ (if it contains $p>2$, then $p^2+1$ is even). Then it also contains $2\cdot 2+1=5, 2\cdot 5+1=11, 7\mid 5\cdot 11+1, 3\mid 2\cdot 7+1,$ etc. It looks like then $S$ contains all prime numbers. I cannot prove it yet, but the proof should not be that difficult.

Update Here is a stronger conjecture. Let $S$ be the set of all primes from $2$ to $p>17$. Let $q$ be the next prime after $p$. Then $q$ divides $rs+1$ for some $r,s\in S$. This of course implies the statement above. I wonder if my conjecture is already known. I checked it for all $p<100,000$. I stop checking and will wait for an opinion of a real number theorist.

$\endgroup$
4
  • 1
    $\begingroup$ I wonder if this is known, it is related to your strong conjecture, let $q$ be a large prime, let $A$ be the set of primes less than $q$ as a subset of $\mathbb Z/q\mathbb Z$ and let $B$ be the set of their inverses. is the sumset $A+B$ large? Can we prove that it is of size $O(q)$? $\endgroup$ Dec 27, 2011 at 2:23
  • 1
    $\begingroup$ That is a question for Green and Tao:) The density of $A$ is small, unfortunately, and so is the density of $B$. But I am not a specialist. I still think that my question has a chance to be less of a monster than, say, Goldbach's conjecture because it is about products, not sums. But I may be too naive. $\endgroup$
    – user6976
    Dec 27, 2011 at 2:54
  • 1
    $\begingroup$ Actually we need to show that $A\cdot A$ contains $-1$. So the question is how large $A\cdot A$ is. I think there were results like that for cyclic groups (and recently even for nilpotent groups). $\endgroup$
    – user6976
    Dec 27, 2011 at 3:06
  • 1
    $\begingroup$ I have posted a separate question mathoverflow.net/questions/84374/… . $\endgroup$
    – user6976
    Dec 27, 2011 at 13:25
5
$\begingroup$

This was given as a problem in one of the MAA journals in the 1980's as a double-starred problem (no solution provided). I met it as a challenge problem on an assignment in John Poland's (Carleton University) modern algebra course. I worked on it for a few months, observing as Mark Sapir does that such a set contains 2, 5, 11, etc.

$\endgroup$
1
  • 2
    $\begingroup$ If you're the same JC who posted the question, you might want to ask one of the moderators to merge the two accounts $\endgroup$
    – Yemon Choi
    Jan 2, 2012 at 19:31
2
$\begingroup$

Not claiming to be a real number theorist or anything of that sort...Just wondering, is one possible approach to Mark Sapir's strong conjecture (assuming an answer isn't already known) to calculate $$ \sum_{\substack{r,s < q\\ q| rs+1}}\Lambda(r)\Lambda(s) $$

by

$$ \int_0^1 \left(\sum_{r,s < q}\Lambda(r)\Lambda(s)e((rs+1)\alpha)\right)\left(\sum_{m <q}e(-qm \alpha)\right)d\alpha $$

where $e(x) = e^{2 \pi i x}$ and then apply the circle method? If it can't be solved in this manner, perhaps it can still be made equivalent to a conjecture on some error terms.

$\endgroup$
1
$\begingroup$

Dear Currie

The below problem is still open:

Do we have infinite prime number of the form $2p+1$, where $p$ is prime?

One of interesting way to examine this problem is %Sandram$ table. For further information about Sandram table, you can see the book

" Ingenuity in Mathematics" by Ross Hansberger

Also, with some calculation and using the Jacobi symbol, you will find this problem is equivalent to this problem:

The polynomial $n^2+n-1$ generate infinite prime number, that it is open problem. You can find some further information about this question in the Richard Guy's book with name:

" Open problem in number theory".

So I think your problem is a kind of open problem.

$\endgroup$
2
  • 1
    $\begingroup$ I don't see why a solution to James Currie's original question would imply a solution to this well known open question $\endgroup$
    – Yemon Choi
    Jan 3, 2012 at 4:47
  • $\begingroup$ Dear Choi, It is possible that we construct a sandram-like table that is equivalent to the original question in this post. I saw this problem when I was in India and some people worked on this problem. I don't know that they published their works or not. $\endgroup$
    – Shahrooz
    Jan 3, 2012 at 14:48

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.