BRICS RS-94-26 S. Riis: Count(q) versus the Pigeon-Hole Principle

BRICS

Basic Research in Computer Science

Count(q) versus the Pigeon-Hole Principle

S�ren Riis

BRICS Report Series RS-94-26 ISSN 0909-0878 August 1994 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1994, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@daimi.aau.dk

Count(q) versus the Pigeon-Hole Principle

Søren Riis ; BRICS^{∗}

June 1994

Abstract

For each p ≤ 2 there exist a model 𝕄^{∗} of IΔ_{0}(α) which satisfies the Count(p) principle. Furthermore if p contain all prime factors of q there exist n, r ∈ 𝕄^{∗} and a bijective map f ∈ Set(𝕄^{∗}) mapping {1, 2, ..., n} onto {1, 2, ..., n + q^{r}}.

A corollary is a complete classification of the Count(q) versus Count(p) problem. Another corollary solves an open question ([3]).

In this note I state and prove a Theorem which actually can be viewed as the main result of [9].

Theorem: Suppose that r(n) is an function with

(a) lim_{n→∞} r(n) = ∞.

(b) For all ϵ > 0 lim_{n→∞} \frac{q^{r(n)}}{n^{ϵ}} = 0 For each q, p ≥ 2 Count(p) ⊬ PHP_{∗+q^{r(∗)}}^{∗}(bij) if p divides a power of q.

Here PHP_{∗+s}^{∗}(bij) is the the elementary principle stating that there does not exists n and a bijective map from {1, 2, ..., n} onto {1, 2, ..., n + s}.And Count(p) is the elementary matching principle stating that if {1, 2, ..., n} is divided into disjoint p-element subsets, then p divides n. Proof: As in [9] let 𝕄 be a countable non-standard model of first order Arithmetic. Then by a similar forcing construction (which actually avoids certain technical problems) we expand 𝕄 by a generic bijection f mapping {1, 2, ..., n} onto {1, 2, ...., n + q^{r(n)}}. Assumption (a) allows us to assume that q^{r(n)} is a non-standard number. Furthermore condition (b) ensures that the circuit collapsing argument goes through. Now it follows by the analysis in [9] that the Count(p) principle can never be forced false. If it was false, there would exists an impossible 𝕄-definable object. In this case a forest of (D, R)-labelled trees where | R | − | D |= q^{r(n)}, but where all trees would have hight dominated by some standard number. This violates the main lemma (lemma 6.1.5) in [9]. Finally 𝕄^{∗} is got a the initial segment {m ∈ 𝕄 : n^{k} > m, k ∈ ℕ}. □

∗Basic Research in Computer Science, Centre of the Danish National Research Foundation.

Corollary 1: Let r(n) be as above. For each q, p ≥ 2 Count(p) ⊬ PHP_{∗+q^{r(∗)}}^{∗}(bij) if and only if p divides a power of q.

Corollary 2: For fixed q, p ≥ 2 the following is equivalent

(a) p divides a power of q

(b) Count(q) ⊢ Count(p).

Proof: The implication (a) ⇒ (b) was shown in [4] or [9]. The implication (b) ⇒ (a) follows from the Theorem. According to the Theorem Count(p) ⊬ PHP_{∗+q^{r(∗)}}^{∗}(bij) if Count(q) ⊢ Count(p). But then by the easy ‘only if’ in corollary 1, p must divide a power of q. □

Let PHP_{∗}^{∗+p}(inj) be the the statement that there is no n and no injective map from {1, 2, ...., n + p} into {1, 2, ...., n} and let PHP_{∗+p}^{∗}(sur) be the statement that there is no n and no surjective map from {1, 2, .., n} onto {1, 2, ..., n+p}. Corollary 3:

(a) PHP_{∗+1}^{∗}(bij) ⊬ PHP_{∗}^{∗+1}(inj).

(b) PHP_{∗}^{∗+1}(inj) ⊣⊢ PHP_{∗+1}^{∗}(sur).

(c) Count(q) ⊬ PHP_{∗}^{∗+1}(inj).

Proof: (b) is a simple exercise, and (a) clearly follows from (c). To show (c) notice that PHP_{∗}^{∗+1}(inj) ⊢ PHP_{∗+q^{r(∗)}}^{∗}(bij) for any r. □ This solves an open question concerning the strength of the pigeon hole principle for injective maps [3]. Actually it shows that:

Corollary 4: There exists a model 𝕄^{∗} of IΔ_{0}(α) in which Count(p) holds for each p ∈ ℕ\{1}. Yet, there exists n ∈ 𝕄^{∗} and an injective map f ∈ Set(𝕄^{∗}) mapping {1, 2, ..., n + 1} into {1, 2, ..., n}.

Proof: By the completeness theorem it suffice to show that for each finite set p_{1}, p_{2}, .., p_{l} of integers, the conjunction Count(p_{1}) ∧ ....∧ Count(p_{l}) does not imply PHP_{∗}^{∗+1}(inj). This follows by an argument similar to the one given for (c) in corollary 3. □

References

[1] M.Ajtai; On the complexity of the pigeonhole principle. 29^{th} Annual symp. on Found. Comp.Sci.(1988),pp 340-355.

[2] M.Ajtai; Parity and the pigeon-hole principle, in Feasible Mathematics Birkhauser, (1990), pp 1-24.

[3] M.Ajtai; The independence of the modulo p counting principles, Proceedings 9^{th}-annual IEEE symposium on computer science (1994).

[4] P.Beame, R. Impagliazzo, J. Krajicek, T. Pitassi, P. Pudlak; Lower bounds on Hilbert’s Nullstellensatz and propositional proofs, preliminary version.

[5] J.Krajicek, P.Pudlak, and A.Wood, Exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle, submitted (1991).

[6] T.Pitassi, P.Beame, and R.Impagliazzo; Exponential lower bounds for the pigeonhole principle, preprint (1991).

[7] T.Pitassi, P.Beame; An Exponential separation between the Matching Principle and the pigeonhole principle. Proceedings 8^{th}-annual IEEE symposium on computer science (1993), pp 308-319

[8] S.M.Riis; Independence in Bounded Arithmetic; DPhil dissertation, Oxford University (1993)

[9] S.M.Riis; Count(q) does not imply Count(p); Submitted to APAL. Report Series, BRICS RS-94-21.

Recent Publications in the BRICS Report Series

RS-94-26 S�ren Riis. Count(q) versus the Pigeon-Hole Principle. August 1994, 3 pp.

RS-94-25 S�ren Riis. Bootstrapping the Primitive Recursive Functions by 47 Colors. August 1994, 5 pp.

RS-94-24 S�ren Riis. A Fractal which violates the Axiom of Determinacy. August 1994, 3 pp.

RS-94-23 S�ren Riis. Finitisation in Bounded Arithmetic. August 1994, 31 pp.

RS-94-22 Torben Bra� uner. A General Adequacy Result for a Linear Functional Language. August 1994, 39 pp. Presented at MFPS ’94.

RS-94-21 S�ren Riis. Count(q) does not imply Count(p). July 1994, 55 pp.

RS-94-20 Peter D. Mosses and Mart��n Musicante. An Action Semantics for ML Concurrency Primitives. July 1994, 21 pp. To appear in Proc. FME ’94 (Formal Methods Europe, Symposium on Industrial Bene�t of Formal Methods), LNCS, 1994.

RS-94-19 Jens Chr. Godskesen, Kim G. Larsen, and Arne Skou. Automatic Veri�cation of Real�Timed Systems Using Epsilon. June 1994, 8 pp. Appears in: Protocols, Speci�- cation, Testing and Veri�cation PSTV ’94.

RS-94-18 Sten Agerholm. LCF Examples in HOL. June 1994, 16 pp. To appear in: Proceedings of the 7th International Workshop on Higher Order Logic Theorem Proving and its Applications, LNCS, 1994.

RS-94-17 Allan Cheng. Local Model Checking and Traces. June 1994, 30 pp.

RS-94-16 Lars Arge. External-Storage Data Structures for Plane-Sweep Algorithms. June 1994, 37 pp.