Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a part of my answer to this question I think it deserves to be treated separately.

Conjecture Let $A$ be the set of all primes from $2$ to $p>19$. Let $q$ be the next prime after $p$. Then $q$ divides $rs+1$ for some $r,s\in A$.

I wonder if this conjecture is already known. I checked it for all $p<692,000$.

A reformulation of the conjecture is this (motivated by Gjergji Zaimi's comment). Let $p > 19$ be prime. Let $A$ be the set of primes $< p$ considered as a subset of the cyclic multiplicative group $\mathbb{Z}/p\mathbb{Z}^*$. Then the product $A\cdot A$ contains $-1$.

It is interesting to know how large $A\cdot A$ is. This seems to be related to Freiman-type results of Green, Tao and others. Also as Timothy Foo pointed out, perhaps Vinogradov's method of trigonometric sums can apply.

share|improve this question
Of course, $A\cdot A$ contains $-1$ iff $A+A^{-1}$ contains zero. I get a feeling that even for arbitrary A, at least one of these two sets has to be large. For primes, it's likely both are. –  Gjergji Zaimi Dec 27 '11 at 10:59
Interesting problem. I don't think either the sum-product idea or the trig sums idea will work immediately. In the latter case because one has a binary problem instead of one with three variables, and in the former because I think you can have both $A.A \subsetneq Z/pZ^*$ and $A + A^{-1} \subsetneq Z/pZ$ with $A$ reasonably large, even positive density. But both of these are good ideas on which to base further thought. –  Ben Green Dec 27 '11 at 12:48
I might add that I would expect trigonometric sums to allow one to show that $A \cdot A$ is almost all of $Z/pZ$ as $p \rightarrow \infty$. –  Ben Green Dec 27 '11 at 12:49
Geoff- there certainly is work on this. It's known that the smallest prime congruent to $a$ mod $q$ is $\ll q^{5.4}$ (or so). It's conjectured that it's $\ll q^{1 + \epsilon}$. The GRH would give $\ll q^{2 + \epsilon}$. –  Ben Green Dec 27 '11 at 16:39
Denis, I don't understand your comment. I only know two things that count as good reasons in the theory of prime numbers. First, a proof. Second, a decent heuristic or "statistical" argument. Here, the set of $1 + rs$ ought to look like a fairly random (give or take some irregularities mod small primes) subset of $[1,p^2]$ of density $1/\log^2 p$. The probability of $x \leq p^2$ being divisible by $p$ is $1/p$. I'd expect subsets of $[1,X]$ of densities $\alpha$ and $\beta$ to intersect as soon as $\alpha \beta \gg 1/X$ unless there is some good reason why not. –  Ben Green Dec 27 '11 at 20:35
show 7 more comments

3 Answers

This answer is a heuristic along the lines of Joro's.

We use $p,q,r$ to denote primes. Let $S(p,a)$ denote the number of pairs of primes $(q,r)$ with $q,r\leq p$ and $p|(qr+a)$. We are interested in the case $a=1$, but in general by the orthogonality relations of the characters we have $$ S(p,a)=\frac{1}{\phi(p)}\sum_{r\leq p}\sum_{q\leq p}\sum_{\chi\ \text{mod}\ p}\overline{\chi}(-a)\chi\left(qr\right).\ \ \ \ \ \ \ \ \ \ (1)$$ Rearranging this is $$S(p,a)=\frac{1}{p-1}\sum_{\chi\ \text{mod}\ p}\overline{\chi}(-a)\left(\sum_{q\leq p}\chi\left(q\right)\right)^{2}.$$

We might hope, as is the often the case, that the sums are all very small except when $\chi$ is principal, and that only the principal character contributes. With this in mind we expect

$$S(p,a)\approx \frac{1}{p} \text{li}(p)^2.$$

This is the same as conjecturing that $S(p,a)$ does not vary largely between $a$. In particular, if we average over all $a$ modulo $p$, then using (1) along with the orthogonality relation $\sum_{a\text{ mod } p}\sum_{\chi\text{ mod } p}\chi (a)=\phi(p)$, we see that $$\frac{1}{\phi(p)}\sum_{a\text{ mod } p} S(p,a)=\frac{1}{p-1}\sum_{r\leq p}\sum_{q\leq p}1=\frac{1}{p}\pi(p)^2\sim \frac{1}{p}\text{li}(p)^2.$$

Numerically this is remarkably close for $a=1$. Using the calculation done in Joro'sanswer, letting $a=1$ and $p=1000003$ we have $$S(p,1)=6184$$ whereas $$\frac{1}{p} \text{li}(p)^2=6182.307\dots $$

Now all that remains is to understand the sum $$\sum_{q\leq p}\chi\left(q\right)$$ for a character modulo $p$. However, I believe this is very difficult.

share|improve this answer
Thank you Eric. Here is a plot of your approximation in red vs number of solutions in blue: drememi.ludost.net/li.png –  joro Dec 29 '11 at 12:10
btw, need the number $>19$ be prime? I see no counterexamples up to $10^{8}$ for all $q$? –  joro Dec 30 '11 at 8:34
add comment

A pari/gp program verified the conjecture to $10^9$ in about 40 minutes.

On naiive probabilistic grounds I would expect the number of solutions to be about $\frac{p}{(\log{p})^2}$. For $p=1000003$ got 6184 solutions and the expectation was 5239.

Here is the pari program:


forprime(p=23,10^9,a=inv1(p);if(a==0,print("+++",p);break; );/*print(p)*/)
share|improve this answer
@joro: I used Maple which is very slow. I do have pari installed on my computer but never learned how to use it, unfortunately. Thank you for checking the conjecture. I think that the analytic tools work better when the density argument gives truthful answer. So there is a hope. –  Mark Sapir Dec 28 '11 at 11:07
@Mark if someone finds the pari program correct, probably you can do up to $10^10$ with it in about 10 hours (very rough estimate). The only change needed is replacing "10^9" with "10^10" –  joro Dec 28 '11 at 11:34
@joro: On the probabilistic grounds, we should be integrating the density and looking at $$\frac{1}{p}\left(\int_2^p \frac{1}{\log t}dt\right)^2=\frac{1}{p}\text{li}(p)^2.$$ Indeed, in the case plugging in $p=1000003$ we find the much closer approximation $$\frac{1}{p}\text{li}(p)^2=6182.307\dots$$ –  Eric Naslund Dec 29 '11 at 10:31
add comment

Perhaps this might be another perspective on this problem. In an answer to a question I had previously asked on Math Overflow, "A generalized Möbius function?", the following paper of Addison was cited (which I simply copy from that answer):

A Note on the Compositeness of Numbers, A. W. Addison, Proceedings of the American Mathematical Society, Vol. 8, No. 1 (Feb., 1957), pp. 151-154

In this paper, it is proven that if one divides the integers into $q$ classes according to whether $\Omega(n)$ is $0,1,\dots,q-1 \bmod q$, $q>2$ then the function $C_{q,i}(x)$ which counts integers less than $x$ with $\Omega(n) \equiv i \bmod q$ satisfies

$$ C_{q,i}(x) - \frac{x}{q} = \Omega_{\pm}\left(\frac{x}{(\log x)^r}\right) $$

where $r = 1-\cos(2\pi/q)$. (Here the variables $q$ and $r$ are taken from the paper and mean different things from elsewhere in this page.)

Let's assume that the relative frequencies of $\Omega(n) \bmod q$ should not differ much whether we consider $n\in [1,p^2]$ or $n\in (p\mathbb{Z}-1)\bigcap [1,p^2]$. Then we take $x$ to be about $p^2$ and $q$ to be about

$$ f(p)=\max_{n \in (p\mathbb{Z}-1)\bigcap [1,p^2]}\Omega(n). $$

Then a necessary (but not sufficient) condition for the conjecture is that $C_{f(p),2}(p^2)\geq 1$. I'm not really sure if one can take $x$ and $q$ in this relative range, but if so, then one can't even get a necessary condition from this because, using $1-\cos x \approx x^2/2$ for small $x$, we have

$$ f(p) \gg (\log p)^{1-\cos(2\pi/f(p))}. $$

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.