12
$\begingroup$

This problem is motivated by the polymath4 project. There, the aim was to find an efficient deterministic algorithm for finding a prime larger than $N$. The hope was to find a polynomial algorithm in $n=\log N$ which can be done assuming the truth of either plausible but intractable number theory conjectures or plausible but intractable problems in computational complexity. What was achieved was an algorithm that runs in time $N^{1/2-c}$ for some small $c>0$ to find the parity of the number of primes in an arbitrary interval of integers smaller than $N$. In view of this, identifying a single interval with an odd number of primes could be useful. Here are some questions regarding primes and parity.

1)

Let $N$ be an integer. consider the intervals $[N,2N]$, $[2N,3N], \dots$ $[kN,(k+1)N]$ What is the smallest $k$ that we can guarantee that one of these intervals contain an odd number of primes?

Based on Cramer's probabilistic modeling we can expect $k=a \log N$ to work for every $N$ and some constant $a$. Results about gaps between primes assert that when $k$ is exponential in $N$ we can find such an interval with one, hence an odd number of, primes. (For that we need two consecutive large gaps, apparently this is known but I am not aware of an elementary argument as for one gap.)

Is there some hope to prove it for $k=N^{100}$, $k=N$? $k=N^{1/2}$? A proof for $k=N^{1/2-c}$ will allow us by divide and conquer to find a prime $p$ larger than $N$ is time $p^{1/2-c}$.

2)

For which of the following sequences of intervals $[a(n),2a(n)]$ would it be possible to prove that that (i) there are infinitely many cases of odd number of primes; (ii) this occurs in half the cases?

2.1 $a(n)=n$ or an a.p. (I think (i) is ok);

2.2 $a(n)=p_n$;

2.3 $a_n=n^2$;

2.4 $a_n=2^n$

Is showing that there are infinitely many $n$s for which there are odd number of $n$-digits primes entirely hopeless (like Cramer's conjecture)?

3)

Let $p_n$ be the $n$th prime. What can be said/proved about the zeta-like function $$ \prod_{k=1}^\infty {{1}\over{1-(-1)^kp_k^{-s}}}$$

4)

Beside polymath4, were such questions about primes and parity considered before?

5)

Mark Lewko proposed the following question in a comment below: Consider subsets $A\subset [n]$ of density $n/log(n)$. What is the smallest collection of arithmetic progressions such that at least one is guaranteed to intersect every such $A$ with odd parity?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ For 3), do you want the exponent of $p_k$ to be $-s$? $\endgroup$
    – Stopple
    Commented Jan 30, 2015 at 16:14
  • 1
    $\begingroup$ Related MO question (and see rlo's answer there): mathoverflow.net/questions/164936/… $\endgroup$
    – Lucia
    Commented Jan 30, 2015 at 18:12
  • 1
    $\begingroup$ A somewhat different question related to getting around the $\sqrt{n}$ barrier is the following: First recall that the Polymath4 result allows one to compute the parity of primes in an arithmetic progression intersecting [n,2n] "efficiently" (in time $n^{1/2-\delta}$ for some small $\delta$). Consider a subset $A \subseteq [n]$ of density $n/\log(n)$. What is the smallest collection of arithmetic progressions such that at least one is guaranteed to intersect $A$ with odd parity? More generally, it would be nice to reduce the problem to something not explicitly involving primes. $\endgroup$
    – Mark Lewko
    Commented Feb 10, 2015 at 16:26
  • $\begingroup$ 1) Assuming Oppermann's conjecture, if you set $k=N+1$, you have primes in every interval. Don't know about the parity, though. $\endgroup$
    – Fred Daniel Kline
    Commented Feb 10, 2015 at 18:14
  • $\begingroup$ Dear Mark, my highly uneducated guess would be that just based on density (or even on other known properties or even on RH) you want be able to find a small collection of such AP's. $\endgroup$
    – Gil Kalai
    Commented Feb 12, 2015 at 13:22

0

Reset to default

You must log in to answer this question.