Evasiveness and the Distribution of Prime Numbers

Details Evasiveness and the Distribution of Prime Numbers Evasiveness and the Distribution of Prime Numbers

2010-01-27

arxiv.org/abs/1001.4829v2

Computer Science

Computational Complexity

12 pages (conference version for STACS 2010)

Scientific paper

We confirm the eventual evasiveness of several classes of monotone graph properties under widely accepted number theoretic hypotheses. In particular we show that Chowla's conjecture on Dirichlet primes implies that (a) for any graph $H$, "forbidden subgraph $H$" is eventually evasive and (b) all nontrivial monotone properties of graphs with $\le n^{3/2-\epsilon}$ edges are eventually evasive. ($n$ is the number of vertices.) While Chowla's conjecture is not known to follow from the Extended Riemann Hypothesis (ERH, the Riemann Hypothesis for Dirichlet's $L$ functions), we show (b) with the bound $O(n^{5/4-\epsilon})$ under ERH. We also prove unconditional results: (a$'$) for any graph $H$, the query complexity of "forbidden subgraph $H$" is $\binom{n}{2} - O(1)$; (b$'$) for some constant $c>0$, all nontrivial monotone properties of graphs with $\le cn\log n+O(1)$ edges are eventually evasive. Even these weaker, unconditional results rely on deep results from number theory such as Vinogradov's theorem on the Goldbach conjecture. Our technical contribution consists in connecting the topological framework of Kahn, Saks, and Sturtevant (1984), as further developed by Chakrabarti, Khot, and Shi (2002), with a deeper analysis of the orbital structure of permutation groups and their connection to the distribution of prime numbers. Our unconditional results include stronger versions and generalizations of some result of Chakrabarti et al.

Affiliated with

Also associated with

No associations

Rating

Evasiveness and the Distribution of Prime Numbers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Evasiveness and the Distribution of Prime Numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Evasiveness and the Distribution of Prime Numbers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-238339