A Generalization of Erdos’s Proof of Bertrand-Chebyshev Theorem

Bertrand’s postulate states that for every positive integer n, there is always at least one prime psuch that np2n. This was proved by Chebyshev in 1850, Ramanujan in 1919 and Erdos in 1932.

Legendre’s conjecture states that there is a prime number between n2 and (n+1)2 for every positive integer n. It is one of the four Landau’s problems, considered as four basic problems about prime numbers. The other three problems are

  • Goldbach’s conjecture : Every even integer n > 2 can be written as the sum of two primes ?
  • Twin prime conjecture : There are infinitely many primes p such that p+2 is prime ?
  • Are there infinitely many primes p such that p-1 is a perfect square ?

All these problems are open till date !! Lets look at the following generalization of the Bertrand’s postulate :

Does there exist a prime number p, such that knp(k+1)n for all integer n>1 and k <=n ?

A positive answer for kn would prove Legendre’s conjecture. Recently I generalized Erdos’s Proof of Bertrand-Chebyshev’s Theorem and proved the following theorem :

Theorem : For any integer 1 < kn, there exists a number N(k) such that for all n >=N(k), there is at least one prime between kn and (k+1)n.

Like Erdos’s Proof, my generalization uses elementary combinatorial techniques without appealing to the prime number theorem. An initial draft is available on my homepage.

I have the following question :

Are there infinitely many primes p such that p+k is prime ?

Is the answer known for any fixed k > 2 ? What if k is allowed to depend on p ? If you know any papers addressing such questions, please leave a comment.

Random Restriction and Circuit Lower Bounds

The class \aczero\ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class \saczero\ is the semi-unbounded version of \aczero\ i.e., AND gates have constant fan-in.

The class AC^0 consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class SAC^0 is the semi-unbounded version of AC^0 i.e., AND gates have constant fan-in. In the class NC^0  both AND and OR gates have constant fan-in. The following strict hierarchy is known.

For all prime numbers p, NC^0 \subsetneq SAC^0 \subsetneq AC^0 \subsetneq AC^0[p] \subsetneq TC^0.

Todays post is is about the following theorem.

Theorem : SAC^0 \subsetneq AC^0

Proof : AC^0 is closed under complementation and SAC^0 is not.


Exercise : Prove that SAC^0 is not closed under complementation.

Recently I came up with an alternate proof of the above theorem using the technique of random restriction of Furst, Saxe and Sipser [FSS'81]. I think my proof can be given as a cool homework problem in introductory complexity theory course. Here it goes…..

Let G(V,E) be a directed simple graph (i.e., G does not have self-loops or multi-edges) with |V|=n and |E|=m. Let indegree(v) represent the indegree of a vertex v \in V. Motivated by cycle languages, we define the language Positive Indegree as follows :

Positive Indegree = \{ <G(V,E)>\ |\ indegree(v)\ \geq\ 1\ \forall\ v\ \in\ V\}.

G is represented as (x_1,y_1),\dots,(x_m,y_m) where each x_i and y_i is in \{1,2,\dots,n\} encoded as binary strings. The meaning of (x,y) is that there is a directed edge from x to y. We may assume that circuits computing Positive Indegree will have m = O(n^2) binary inputs in a prespecified order.

Exercise : Positive Indegree \in AC^0.

Lemma : If a CNF or a DNF computes Positive Indegree, then
  • each term includes at least n-1 variables, and
  • there are at least n terms.

Hence there is no SAC^0 circuit of depth two for Positive Indegree.

    Proof : We will prove this lemma for CNFs. The proof for DNFs is similar. Let \mathcal{C} be a CNF circuit computing Positive Indegree.
    • Assume that \mathcal{C} has some term t that depends on less than n-1 variables. Then when all inputs to t are 0, t outputs 0 and hence \mathcal{C} outputs 0. Consider the graph H consisting of a cycle on n-1 vertices (say v_1,\dots,v_{n-1}) and an isolated vertex v_n. Note that H \notin Positive Indegree. Let H_i be the graph obtained by adding the edge (v_i,v_n) to H. Now H_i \in Positive Indegree for 1 \leq i \leq n-1. If t does not depend on all variables of the form (v_i,v_n) then \mathcal{C} outputs 0 for some H_i, which is a contradiction.
    • Consider the graph F^i consisting of a cycle on n-1 vertices (these are the vertices from v_1,\dots,v_{n} except v_i) and an isolated vertex v_i. \mathcal{C} must output zero on F^i for 1 \leq i \leq n. \mathcal{C} outputs 0 only when one of the terms (OR gates) outputs zero. But each OR gate outputs 0 on exactly one assignment of the input variables, Hence, \mathcal{C} must have at least n terms.
    Restriction : Let \mathcal{C} be a circuit computing Positive Indegree. Setting an input of \mathcal{C} to 0 (resp. 1) corresponds to deleting (resp. contracting) the corresponding edge from the input graph G.

    Observation : If some of the inputs of \mathcal{C} are restricted to 0 or 1, the resulting circuit still computes Positive Indegree, albeit on a smaller graph.

    Theorem : Positive Indegree \notin SAC^0.
    Proof : We assume that there is an SAC^0 circuit (say \mathcal{C} of some constant depth d) computing Positive Indegree and derive a contradiction. Using the random restriction technique of [FSS'81] we squash \mathcal{C} down to depth d-1 while still computing Positive Indegree on many variables. This squashing still preserves the constant fanin of AND gates. We repeat this method d-2 times to obtain an SAC^0 circuit of depth 2 with constant AND fanin, which contradicts the previous lemma.

    Corollary : SAC^0 \subsetneq AC^0.

    References :
    • [FSS'81] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In FOCS, pages 260–270, 1981.

    Relativization Barrier

    I am back in Atlanta after attending an awesome Barriers Workshop. This workshop is mainly about the barriers in resolving P vs NP problem and possible techniques to overcome these barriers. It is a five day workshop covering circuits lower bounds, arithmetic circuits, proof complexity, learning theory and pseudo-random generators. I enjoyed every talk and panel discussions. Everybody seemed very positive that P \neq NP.

    Today’s post is a quick introduction to Relativization Barrier. I will write separate posts about natural proofs and algebrization barriers soon. Relativization Barrier is one of the first barriers we learn in an introductory graduate level complexity course.

    In relativized world we grant the Turing machine M the access to an oracle that could compute some function A in a single time step. Such a machine, called oracle TM, computes relative to A, is represented by M^A. Oracle TMs are used in Turing-reducibility, a generalization of mapping-reducibility.

    The method of diagonalization relativizes i.e.,  any separation result in the real world, proved using diagonalization, extends to the relativized world. Baker, Gill and Solovay [BGS'75] showed that there exists oracles A and B for which P^A and NP^A are provably different and P^B and NP^B are provably equal. That is P vs NP has different answers in different worlds !! Hence techniques such as diagonalization, cannot be used to resolve P versus NP.

    Theorem : An oracle A exists such that P^A \neq NP^A. An oracle B exists such that P^B = NP^B.

    Let B be any PSPACE-complete problem. We have NP^B \subseteq NPSPACE \subseteq PSPACE \subseteq P^B. The first and third containments are trivial and the second containment follows from Savitch’s theorem. Hence P^B = NP^B. Constructing A is a non-trivial task. Look at Sipser’s book (page 350) for details of constructing A.

    Therefore any solution to the P versus NP problem will require non-relativizing techniques i.e., techniques that exploit properties of computation that are specific to the real world i.e., techniques that analyze the computations not just simulate them.

    References :

    • [BGS'75] T. Baker, J. Gill, and R. Solovay : Relativizations of the P=?NP question. SIAM J. Comput., 4:431–442, 1975.

    Baker, Gill and Solovay [BGS'75] showed that techniques such as diagonalization,
    cannot be used to resolve P versus NP. Such techniques would work in [relativized]
    world, where both P and NP machines could compute some function
    f in a single time step.
    However, there are some relativized
    worlds where P = NP, and other relativized worlds
    where P != NP. Therefore any solution to the P versus NP
    problem will require non-relativizing techniques i.e., techniques
    that exploit properties of computation that are specific to
    the real world.