Abstract Over 25 years ago, the first author conjectured in [15] that the existence of arbitrarily large primes is provable from the axioms IΔ0(π) + def(π), where π(x) is the number of primes not exceeding x, IΔ0(π) denotes the theory of Δ0 induction for the language of arithmetic including the new function symbol π, and def(π) is an axiom expressing the usual recursive definition of π. We prove a modified version in which π is replaced by a more general function ξ that counts some of the primes below x (which primes depends on the values of parameters in ξ), and has the property that π is provably Δ0(ξ) definable.

The exact complexity of the weak pigeonhole principle is an old and fundamental problem in proof complexity.Using a diagonalization argument, Paris, Wilkie and Woods [9] showed how to prove the weak pigeonhole principle with bounded-depth, quasipolynomial-size proofs.Their argument was further refined by Krajf~ek [5].In this paper, we present a new proof: we show that the the weak pigeonhole principle has quasipolynomial-size proofs where every formula consists of a single AND/OR. of polylog fan-in.Our proof is conceptually simpler than previous arguments, and is optimal with respect to depth.

The properties of any system of k simultaneous equations in n variables over GF(q), are studied, with a particular emphasis on unsatisfiable systems. A general formula for the number of solutions is given, which can actually be useful for computing that number in the special case where all the equations are of degree 2. When such a quadratic system has no solution, there is always a proof of unsatisfiability of size q/sup n/2/ times a polynomial in n and q, which can be checked deterministically in time satisfying a similar bound. Such a proof can be found by a probabilistic algorithm in time asymptotic to that required to test, by substitution in k quadratic equations, all q/sup n/ potential solutions.

Abstract Letφbe a monadic second order sentence about a finite structure from a class which is closed under disjoint unions and has components. Compton has conjectured that if the number ofnelement structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilitiesν(φ)(μ(φ)respectively) forφalways exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number of single component -structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates.

Abstract It is shown, assuming the linear case of Schinzel's Hypothesis, that the first-order theory of the structure 〈ω; +, P〉, where P is the set of primes, is undecidable and, in fact, that multiplication of natural numbers is first-order definable in this structure. In the other direction, it is shown, from the same hypothesis, that the monadic second-order theory of 〈ω S, P〉 is decidable, where S is the successor function. The latter result is proved using a general result of A. L. Semënov on decidability of monadic theories, and a proof of Semënov's result is presented.

In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP).We also obtain an ~(log log rz)depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle.Our theorem nearly completes the search for the exact complexity of the PHP, as Sam Buss has constructed polynomial-size, log ndepth Frege proofs for the PHP.The main lemma in our proof can be viewed as a general H&.stad-style Switching Lemma for restrictions that are partial matchings.Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.

In this note we shall be interested in the following problems. Problem 1. Can IΔ0 ⊢ ∀x∃y > x(y is prime)? Here I Δ0 is Peano arithmetic with the induction axiom restricted to bounded (i.e. Δ0) formulae. Problem 2. Can IΔ0 ⊢ Δ0 PHP? Here Δ0 PHP (Δ0 pigeonhole principle) is the schema for θ ∈ Δ0, or equivalently in IΔ0, for a Δ0 formula F(x,y) written . By obtaining partial solutions to Problem 2 we shall show that Problem 1 has a positive solution if IΔ0 is replaced by IΔ0 + ∀xxlog(x) exists. Our notation will be entirely standard (see for example [3] and [4]). In particular all logarithms will be to the base 2 and in expressions like log(x), (1 + ε)x, etc. we shall always mean the integer part of these quantities. Concerning Problem 2 we remark that it is shown in [5] that for k ∈ N and F ∈ Δ0, As far as we know this is the best result of this form, in that we do not know how to replace log(z)k by anything larger. However, as we shall show in Theorem 1, we can do much better if we increase the difference between the sizes of the domain and range of F. In what follows let M be a countable nonstandard model of IΔ0, and let be those subsets of M defined by Δ0 formulae with parameters from M. Theorem 1. For k ∈ N andF ∈ Δ0, Here log0(x) = x, logk + 1(x) = log(logk(x)). Proof. To simplify matters, consider first the case k = 1. So assume M ⊨ alog(a) exists and with and a > 1. The idea of the proof is the following.