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?
$\begingroup$
$\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$– François BrunaultCommented 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 RivinCommented 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$– Pace NielsenCommented Jan 2, 2012 at 18:52
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
4
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.
-
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$ Commented 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$– user6976Commented 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$– user6976Commented Dec 27, 2011 at 3:06
-
1$\begingroup$ I have posted a separate question mathoverflow.net/questions/84374/… . $\endgroup$– user6976Commented Dec 27, 2011 at 13:25
$\begingroup$
$\endgroup$
1
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.
-
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$ Commented Jan 2, 2012 at 19:31
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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.
-
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$ Commented 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$– ShahroozCommented Jan 3, 2012 at 14:48