58
$\begingroup$

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.

Improve this question
$\endgroup$
13
  • 4
    $\begingroup$ 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. $\endgroup$
    – Gjergji Zaimi
    Commented Dec 27, 2011 at 10:59
  • 5
    $\begingroup$ 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. $\endgroup$
    – Ben Green
    Commented Dec 27, 2011 at 12:48
  • 4
    $\begingroup$ 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$. $\endgroup$
    – Ben Green
    Commented Dec 27, 2011 at 12:49
  • 5
    $\begingroup$ 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}$. $\endgroup$
    – Ben Green
    Commented Dec 27, 2011 at 16:39
  • 9
    $\begingroup$ 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. $\endgroup$
    – Ben Green
    Commented Dec 27, 2011 at 20:35

3 Answers 3

Reset to default
30
+100
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 11
    $\begingroup$ Thank you Eric. Here is a plot of your approximation in red vs number of solutions in blue: drememi.ludost.net/li.png $\endgroup$
    – joro
    Commented Dec 29, 2011 at 12:10
  • 3
    $\begingroup$ btw, need the number $>19$ be prime? I see no counterexamples up to $10^{8}$ for all $q$? $\endgroup$
    – joro
    Commented Dec 30, 2011 at 8:34
21
$\begingroup$

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:

{
inv1(p)=
local(q,a);
forprime(q=2,p-1,
a=lift(Mod(-1,p)/q);
if(isprime(a),return(1););
);
return(0);
}
default(primelimit,10^10)

forprime(p=23,10^9,a=inv1(p);if(a==0,print("+++",p);break; );/*print(p)*/)
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ @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. $\endgroup$
    – user6976
    Commented Dec 28, 2011 at 11:07
  • 1
    $\begingroup$ @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" $\endgroup$
    – joro
    Commented Dec 28, 2011 at 11:34
  • 16
    $\begingroup$ @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$$ $\endgroup$
    – Eric Naslund
    Commented Dec 29, 2011 at 10:31
  • $\begingroup$ @EricNaslund for large n, isn't yours asymptotically the same? $\endgroup$
    – joro
    Commented Oct 11, 2015 at 14:37
11
$\begingroup$

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))}. $$

Improve this answer
$\endgroup$

You must log in to answer this question.