BRICS RS-94-21 S. Riis: Count(q) does not imply Count(p)

BRICS

Basic Research in Computer Science

Count(q) does not imply Count(p)

S�ren Riis

BRICS Report Series RS-94-21 ISSN 0909-0878 July 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) does not imply Count(p)

Søren Riis^{∗}

BRICS^{†}

August 1993 Revised May 1994

Abstract

I solve a conjecture originally studied by M. Ajtai. It states that for different primes q, p the matching principles Count(q) and Count(p) are logically independent. I prove that this indeed is the case. Actually I show that Count(q) implies Count(p) exactly when each prime factor in p also is a factor in q.

1 The logic of elementary counting

“She loves me, she loves me not, she loves me,… ” The final answer does not depend on the order in which the leaves are pulled of. Every child who is familiar with the process of counting knows that. The underlying logical principle states that a set A has a well-defined cardinality modulo 2. Yet, the Count(2) principle can fail in quite strong systems of Arithmetic [2],[3]. Similarly for the counting principle modulo p (=Count(p)) where she can be in p states of mind.

This is very difficult to visualise. In 1962 Cohen invented the famous technique of forcing. He used the method to show the independence of the continuum conjecture. Inspired by these ideas Ajtai showed that the elementary pigeon-hole principle need not hold in strong systems of Arithmetic [2]. Ajtais result was a major break through. The main novelty was the mixture of forcing and powerful probabilistic techniques.

The Count(q) versus Count(p) problem has various formulations and variants. The most famous variant is from circuit complexity theory [13]. It asks (in the base case) whether there exist bounded depth, polynomial size circuits which counts the number of 1’s (in the input string) modulo p. This was answered (negatively) independently in [13] and [1]. Later [14] gave a near optimal exponential lower bound. The question becomes particular challenging if we also allow gates which can count modulo q. In [27] the case was settled for different prime numbers q and p. The general classification is still open. It has been conjectured that the answer is positive exactly when q contains all prime factors in p [5]. However even the simple case where q = 6 and p = 5 has now been open for more than five years (PC. Haastad, Krajicek, Pudlak).

∗This work was initiated at Oxford University England.

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

Ajtais version of the problem is technically more involved (‘presumably more difficult’ to cite [16]). One formulation (given in [10]) concerns the question whether for different primes q and p there exist arithmetical models 𝕄, which satisfies the Count(q) principle, but which does \underline{not} satisfies the Count(p) principle? The method in [27] is not sufficient. Still circuit complexity (especially the method of collapsing circuits by use of random evaluations) is of major importance [16], [24].

In this paper I answer Ajtais question. Actually I give a complete classification. It agree with what has been conjectured for the circuits. I.e. the answer is positive exactly when all prime factors in p belong to q.

1.1 Non-standard Arithmetic

It it well known that there are interesting and useful geometrical structures in which the (obvious) parallel postulate fail. The models I construct in this paper (and the ones constructed in [2] and [3]) suggests that there exist a similar phenomenon in Arithmetic! As an illustration of this idea suppose that we live in some “non-Euclidean” Arithmetical world 𝕄. Locally the universe 𝕄 agrees with the real universe. Statements concerning concrete finite objects have unaltered truth value. However, globally i.e. when it comes to the behaviour at infinity, there can be disagreement. Thus even though each concrete (“finite”) set A of numbers has a well defined cardinality this property might not be globally valid.

To illustrate the idea further suppose (as an example) that the Count(2) principle is valid in 𝕄. What is the status of the Count(4) principle? Or slightly less general is it possible that there exists a “ number” n′ such that the ordered set {1, 2, ..., 4n′ +r} of “numbers” can be divided into disjoint 4-element subsets, and r ∈ {1, 2, 3}?

Consider the following argument: We want to show (reasoning inside 𝕄) that a set of numbers of the form {1, 2, ..., n} can be divided into a collection of disjoint 4 element subsets only when n is divisible by 4. Suppose that on the contrary some interval {1, 2, .., 4n′ + r}, r ∈ {1, 2, 3} can be divided into a collection P of disjoint 4 element subsets. The case where r = 1 or r = 3 can be excluded for trivial reasons. To see this sub-divide each 4-element subset into two 2-element subsets. This induces a partitioning of {1, 2, ..., 4n′ +r} into disjoint 2-element subsets violating the Count(2) principle.

The case where r = 2 require a more involved argument ^{3} . Consider all pairs of {1, 2, ..., 4n′ + 2}. It only requires a quite weak part of arithmetic to prove that these pairs are in 1-1 correspondence with \{1, 2, ..., \binom{4n′+2}{2}\}. And even less Arithmetical assumptions to show that \binom{4n′+2}{2} is an odd number. To get a contradiction (by violating the Count(2) principle) it suffices to show that the partitioning P induces a partitioning R of all pairs of {1, 2, ..., 4n′+2} into disjoint 2 element sets. Consider the pair {v_{1}, v_{2}}. If both v_{1} and v_{2} belongs to the same 4-element subset {v_{1}, v_{2}, v_{3}, v_{4}} ∈ P let {{v_{1}, v_{2}}, {v_{3}, v_{4}}} ∈ R. Otherwise suppose v_{1} ∈ {w_{1}, w_{2}, w_{3}, w_{4}} ∈ P and v_{2} ∈ {w̃_{1}, w̃_{2}, w̃_{3}, w̃_{4}} ∈ P. All elements are listed after size. So there are unique i, j ≤ 4 such that v_{1} = w_{i} and v_{2} = w̃_{j}. If i ≠ j let {{v_{1}, v_{2}}, {w̃_{i}, w_{j}}} ∈ R. If i = j let {{v_{1}, v_{2}}, {w_{i′}, w̃_{i′}}} ∈ R where 1′ = 2, 2′ = 1, 3′ = 4 and 4′ = 3. This completes the argument.

To summarise: We considered a structure S_{I} constructed from I := {1, 2, ..., n}. In this concrete case the structure consisted of all pairs of {1, 2, .., 4n′ + 2}. This structure S_{I} had the property that partial partitions of {1, 2, ..., 4n′+2} into 4 element subsets induced (in a flexible way) pairings of the elements in S_{I}. And crucially the structure S_{I} contained an odd number of elements. One could try to modify the type of argument to the case where for example q = 2 and p = 3. At an early stage in this research J.Krajicek showed me some ingenious constructions attempting show that Count(3) was a consequence of Count(2). However as J.Krajicek pointed out careful calculations always seems to give the wrong parities. Irrespectively of the ingenuity however clever the structures S was constructed, it always seemed to end up containing an even number of elements. So it seemed that strong “forces” wanted Count(2) and Count(3) to be independent.

In retrospect this is of course a simple consequence of the general classification. It is a direct consequence of the fact that the Count(2) and the Count(3) principles are independent in powerful Arithmetical structures. The first step in showing this was obtained when I reduced the general Count(q) versus Count(p) problem to the study of “generic systems”. And by introducing a certain refinement technique I was able to reduce the Count(q) versus Count(p) problem to questions concerning forests of specially labelled trees.

3I learned this type of argument from J. Krajicek and P.Pudlak.

1.2 A forest containing 16821302548060 trees

The first main result in the paper links the Count(q) versus Count(p) questions to a class of purely combinatorial problems.

Suppose T_{1}, T_{2}, ...., T_{u} is a collection of specially labelled trees (i.e. a forest). Suppose that each type of branch appears 0 modulo q times. Does q divide u ? This of course depends on how the trees are labelled. I consider labels of a type which is determined by two numbers (p, n). A naive conjecture states that (besides some trivial counter examples) q indeed divides u.

It turns out that there exist “exceptional” forests which violate this naive conjecture. As an example when q = 2 and p = 4, I show that there is a forest where each type of branch appears an even number of times. However the forest contains 635 trees (which is an odd number). When q = 3 and p = 9 there are also exceptional forests. In these each type of branch appears 0 modulo 3 times, yet the number of trees is not divisible by 3. The smallest concrete example I have found contains 16821302548060 trees.

The first main result in the paper shows that the existence of such exceptional forests and the existence of (non-trivial) implications between Count(q) and Count(p) are two sides of same coin. The two examples correspond to the fact that Count(2) implies Count(4) and that Count(3) implies Count(9). It turns out that Count(q) implies Count(p) in systems of Bounded Arithmetic when all prime factors in p appears in q. According to my first main result a priori there must exist exceptional forest for all such q and p. Actually I follow an alternative route. I show how one can construct proofs (in systems of Bounded Arithmetic) of Count(p) from Count(q) directly based on such forests.

Early in this research the exceptional forests caused a major complication. At that stage all my attempts to collapse forests to particularly nice normal forms failed. The probabilistic arguments did not quite work. Essentially the exceptional forests was the only obstacle. First when I managed to isolate these asymptotically, I was able to complete the analysis.

At present I do not have a complete picture of all exceptional forests. However it turns out that the asymptotic classification in this paper is sufficiently strong to provide a complete solution of the Count(q) versus Count(p) problem in the base-case (i.e. when the terms in underlying language have polynomial growth rate).

1.3 Why are these problems important

The counting principles themselves are of course trivial. Or more specifically they hold in the category of finite sets. There are various reasons to examine these elementary counting principles.

First of all they play an important role in Bounded Arithmetic. As already pointed out in non-Euclidean geometry the (obvious) parallel postulate is not assumed to hold. Bounded Arithmetic resembles this phenomenon. Here the (obvious) induction axiom scheme is restricted. Which parts of number theory holds in models of Bounded Arithmetic? This question was first studied intensively by J.Paris, A.Wilkie and many of their students. Many basic number theoretical facts are provable in system of Bounded Arithmetic [7]. Other facts require new proofs. I believe that Bounded Arithmetic raises an important and serious possibility. It seems that the provability (in specific systems of Bounded Arithmetic) of elementary number theoretical statements as a rule could be intimately linked to deeper number theoretical problems/theorems. At present there are only sporadic suggestions of this. One such is that if a certain fragment (often denoted by S_{2}^{1} [8]) proves that the set of prime numbers is in NP (this can be proved in ordinary Arithmetic), then the prime numbers must actually be polynomial time recognisable. At present this is only known conditionally by assuming the validity of the General Riemann Hypothesis [17]. A stronger fragment (often denoted S_{2}) are know to show the infinitude of the set of prime numbers. This fact goes hand in hand with Sylvesters prime number theorem [18]. Besides this consider the quantifier elimination phenomenon (the strength of eliminating logic!). Clearly Bounded Arithmetic does not have quantifier elimination. However, one might still be able to eliminate many of its logical-like features. It should be possible to get our hands on the underlying unifications features arising from the induction schema. So perhaps Bounded Arithmetic is tight up with the prestigious discipline of number theory (see [17] for a further discussion).

In any case the work by [18] and later [7] illustrates the central role of elementary counting principles in Bounded Arithmetic. In general the status of the elementary counting principles in models of Bounded Arithmetic seems to be a very deep problem. The paper solves this in the special case where all terms of the underlying language have polynomial growth rate, and contain at least one unspecified function or relation symbol ^{4} .

Second, systems of Bounded Arithmetic are linked to “low complexity reasoning”. One fundamental problem is to clarify the relation between automated versus intelligent reasoning. It seems natural to suggest that automatic reasoning (when this implemented in praxis) is only able to give a proper representation of objects of low complexity. The elementary process of counting introduces unpleasantly high complexity. A computation involving a counting task might (asymptotically) require exponentially many steps as a function of the length of the input. In practice this very soon becomes intractable for computers. Thus in low complexity reasoning we cannot assume that we are be able to count. To verify that the cardinality of a set A is unique, we would have verify that all bijections f : A → {1, 2, ..., m} requires the same m. This is computationally intractable even for small sets A.

4One of the major challenges is to understand the case where each function and relation are fully specified.

We can view Count(p) as a spark of pure intelligence. The paper shows that (mechanical) systems, more specifically systems which reason (using first or even second order logic) within finite structures in certain cases are not able to establish any link between Count(q) and Count(p).

Finally another (related) problem is to examine the efficiency of propositional proof systems. This type of problems has already been studied intensively in the literature [2], [3], [11], [16], [19], [21], [24]. In S.Cook and Recknow [11] it was shown that the efficiency of propositional proof systems is a natural way of studying the NP versus co-NP problem. Then later [19] these problems was linked to Bounded Arithmetic. And then in [2] the problems was shown also to be tight up with methods and problems from circuit complexity. Recently a fascinating ‘ultra filter construction’ by Razborov [22] even suggest links to higher set-theory. In any case the study of the complexity of elementary counting provides some of the strongest known results in the field of circuit complexity.

The growth rate of the terms in the underlying language L of Bounded Arithmetic is a very precise measure of the axiom systems “intelligence”. Most number theory is provable when the language contains function of exponential growth rate. At this level we have real intelligence. Ideally we would like to study what happens to the relative strength of the counting principles, when the intelligence of the underlying system approaches the level of real intelligence. The paper allows us to do this in principle. However, until we have a general picture of the exceptional forests, this problem remains open.

1.4 The main results

In the following discussion let L be a countable first order language. Assume that L contains function symbols for the basic arithmetical operations ‘+’ and ‘·’. Also assume that the behaviour of terms and (the specified) relations are specified through a suitable set Ψ_{L} of purely universal axioms. And assume that L contains at least one unspecified relation symbol.

An axiom system (= IΔ_{0}(L) or just IΔ_{0} when L is clear from the context) of Bounded Arithmetic consists of the axioms Ψ_{L} together with the celebrated induction axiom schema, (θ(0) ∧ ∀x (θ(x) ⇒ θ(x + 1))) → ∀z θ(z). However, in Bounded Arithmetic (unlike in ordinary Arithmetic), we require all quantifiers in each θ to be bounded by terms in the language L. More specifically, each quantifier is required to appear in the context ∀x(x ≤ t → ... or ∃x(x ≤ t ∧ ....

The elementary pigeon-hole principle (=PHP_{p} p ∈ ℕ) states (in one of its many formulations) that for no n do there exists a bijection from {1, 2, ..., n} onto {1, 2, ..., n+ p}. More specifically, the Δ_{0}-PHP_{p} axiom schema states (for each bounded formula θ(x, y)) that,

∀z (¬∀x ≤ z∃!y ≤ z + p θ(x, y, z) ∨ ¬∀y ≤ z + p∃!x ≤ z θ(x, y, z)).

A weak form of the pigeon-hole principle is obtained by only considering monotone bijections. It is not hard to show that this form of the pigeon hole principle is equivalent to the usual induction principle.

The Count(p) principle (for a fixed number p ∈ ℕ) states that if {1, 2, ...., n} is divided into disjoint subsets each containing exactly p elements, then p divides n. More specifically, the Δ_{0}-Count(p) principle is the schema,

∀z ((∀x_{1} ≤ z∃!x_{2}, ...., x_{p} ≤ z (x_{2} < x_{3} < ... < x_{p} ∧ θ(x_{1}, x_{2}, ..., x_{p})
∧¬x_{1} = x_{2} ∧ .... ∧ ¬x_{1} = x_{p})) → ∃y y · p = z).

In the first section I show,

Theorem Assume that p ≥ 2. Let L be any language where all terms have subexponential growth rate. Then there exists a model 𝕄^{∗} in which

(1) The Count(p) principle fails.

(2) All Δ_{0}-pigeon-hole principles holds.

A similar result was proved by Ajtai in [3], but only in case where all terms was assumed to have polynomial growth rate. Later Krajicek, Pudlak and Wood [16] made a major improvement in the underlying probabilistic method. They showed the theorem (in essence) in the case where (2) is replaced by the Δ_{0}-induction principle (or equivalent the Δ_{0}-pigeon-hole principle for monotone bijections). The theorem has been shown independently by Beame and Pitassi [21]. Actually they showed a different (but essentially equivalent) result concerning the length of proofs in propositional proof systems.

In section 2, the next section I construct the model 𝕄^{∗}. And in the next two sections I show that 𝕄^{∗} has the required properties. Actually in section 4 it is shown that,

Theorem Besides (1) and (2) the model 𝕄^{∗} satisfies the Δ_{0}-Count(q) principle exactly (under some weak extra assumptions) when there are no forest T_{1}, T_{2}, ...T_{u} of (p, n)-labelled trees where all branches appear 0 modulo q times, but u ≠ 0 modulo q.

The precise formulation of the result link the growth rate of terms in the underlying language L to an extra condition on the asymptotic hight of the trees.

In section 5 I develop a general method to produce exceptional forests. It is shown that exceptional forests exist (for q and p) when all prime factors in p divides q. Furthermore the construction of such forests can be carried out inside any model of Bounded Arithmetic, so we get the following \underline{positive} part of the classification.

Proposition Let 𝕄^{∗} be a model of Bounded Arithmetic in which the Δ_{0}-Count(q) principle holds. If all prime factors in p divides q, then 𝕄^{∗} satisfies the Δ_{0}-Count(p) principle.

In section 6 I return to the main problem. This is to show that Count(p) not is a logical consequence of Count(q) when p contains a prime factor not in q. This is shown (in the case all terms have polynomial growth rate) by showing

(1) For each exception q-forests T_{1}, T_{2}, ..., T_{u} of (p, n) trees, one can construct an exceptional q-forest T′_{1}, T′_{2}, .., T′_{u′} of labelled trees related to the PHP_{q^{k}}-principle. No tree in this new forests has higher hight than all trees in the old forest.

(2) Suppose that T′_{1}, T′_{2}, ..., T′_{u′} is an exceptional q-forest of decision trees for the PHP_{q^{k}}-principle. Then at least one of the trees has hight ≥ k. Combining this we get,

Theorem Suppose that q and p are fixed. Suppose that p contains a prime factor which does not divide q. For each k there exists n_{k} such that for each n ≥ n_{k} there are no exceptional q-forests of (p, n)-labelled trees.

Finally in section 7 I combine this result with theorem 1.4 and proposition 1.4. This gives the full classification,

Main Theorem (formulation 1) Let T be any system of Bounded Arithmetic over some countable language L. Suppose that L in addition to containing the language of arithmetic also contains at least one undefined relational symbol. Suppose that all terms t in L have polynomial growth rate. Then for all q, p ∈ ℕ the following are equivalent:

(a) there exists a model 𝕄 of T in which Count(q) holds and Count(p) fails.

(b) All prime factors in p divide q.

The result has various essentially equivalent formulations.

Main Theorem (formulation 2) Let ACA^{top} be the following modification of the celebrated system ACA. As ACA the system ACA^{top} has the full arithmetical comprehension. And it is equipped with the full induction axiom for sets. The “only” difference between this system and the normal second order Arithmetic is that the basic universal axioms are modified so the that universe contains a largest (unspecified) number c. All basic operations are modified (e.g. c + 1 = c). Any list of purely universal axioms might also be added. Suppose that the axiomatisation is non-trivial e.g. allows an infinite model. Then the following are equivalent:

(a) Count(p) holds in all structures which satisfies ACA^{top} and the Count(q) principle.

(b) All prime factors in p appear in q.

Another formulation states that,

Main Theorem (formulation 3) Let P be one of the usual textbook systems in Hilbert style propositional logic. Let Count_{scheme}(q) denote the substitution axiom scheme which arrives from the canonical Booleanization of the Count(q) principle. Let P′ := P+ Count_{schema}(q). Then there are polynomial-size bounded depth P′- proofs of Count(p) exactly when all prime factors in p divide q.

In all formulations the negative part of the classification has a heuristic explanation. The analysis shows that when k becomes large, it becomes arbitrarily difficult ^{5} (but as it turns out never impossible) to show PHP_{q^{k}} from Count(q). On the other hand if p contains a prime factor not in q it is uniformly (in k) easy to show PHP_{q^{k}} from Count(p). So Count(p) is not a consequence (a bounded depth polynomial-size consequence in formulation 2) of Count(q) in this case.

Finally I mention the recent and independent developments in [4] and [6].

2 Constructing the model

2.1 Translating formulas into circuits

Let 𝕄 be a countable non-standard model of Th(ℕ) over a countable first order language L (which extends the language of arithmetic). Let p ∈ ω, p ≥ 2 and let I := {1, 2, ..., n} ⊆ 𝕄, n ∈ 𝕄 \ ω be fixed. Here ω denote the set of standard integer in 𝕄. As is common a set A ⊆ 𝕄 is said to be 𝕄-definable if there exists m ∈ 𝕄 such that a ∈ A if and only if a belong to the sequence coded by m.

5Measured by the hight of the corresponding forest.

Definition 2.1.1 For each A ⊆ I with | A |= p we introduce a variable p_{A}. The set of all such variables is denoted by VAR_{I,p}. ♣

Definition 2.1.2 A (Boolean) circuit π (with input variables in X) of size s(π) and depth d(π) is defined inductively as follows:

(a) The constants ‘0’ and ‘1’ are circuits with s(‘1’) = s(‘0’) = d(‘1’) = d(‘0’) = 1.

(b) Each p ∈ X is a circuit with s(p) = d(p) = 1.

(c) If π is a circuit, then ¬π is a circuit with s(¬π) = s(π)+1 and d(¬π) = d(π)+1.

(d) If π_{1}, π_{2}, ..., π_{r} are circuits, then ∧_{j}π_{j} and ∨_{j}π_{j} are circuits with s(∧_{j}π_{j}) = s(∨_{j}π_{j}) = 1 + Σ_{j} s(π_{j}) and d(∧_{j}π_{j}) = d(∨_{j}π_{j}) = 1 + max_{j}d(π_{j}). ♣

Definition 2.1.3 Let B_{d}(X) denote the (Boolean) circuits π with input variables X of depth d(π) ≤ d. Let B_{<ω}(X) := ∪_{d∈ω} B_{d}(X). ♣

Definition 2.1.4 For ψ ∈ B_{<ω}(VAR_{I,p}) and ρ : VAR_{I,p} → {0, 1} (not required to be 𝕄-definable), we define the truth-table evaluation ψ^{ρ} inductively as follows:

(a) ‘0’^{ρ} = 0, ‘1’^{ρ} = 1.

(b) p_{A}^{ρ} = 1 iff ρ(p_{A}) = 1.

(c) (¬π)^{ρ} = 1 iff π^{ρ} = 0.

(d) (∧_{j}π_{j})^{ρ} = 1 iff π_{j}^{ρ} = 1 for all j.

(e)  (∨_{j}π_{j})^{ρ} = 1 iff π_{j}^{ρ} = 1 for some j.  ♣

Let L_{𝕄} be L extended by a constant c_{a} for each a ∈ 𝕄. Let L_{𝕄}(P) be L_{𝕄} extended with an p-ary relation symbol. There exists a canonical translation of Bounded L_{𝕄}(P)-sentences into circuits in B_{<ω}(VAR_{I,p}).

Definition 2.1.5 For each sentence ψ ∈ L_{𝕄}(P) we define ϵ_{ψ} ∈ B_{<ω}(VAR_{I,p}) inductively as follows:

(a) For any k-ary relation symbol (≠ P): ϵ_{R(a_{1},...,a_{k})} :=‘1’ if 𝕄 ⊧ R(a_{1}, .., a_{k}), ‘0’ otherwise.

(b) ϵ_{P (a_{1},...,a_{p})} := p_{A} if A = {a_{1}, ..., a_{p}} ⊆ I and | A |= p, ‘0’ otherwise.

(c) ϵ_{¬π} := ¬ϵ_{π}.

(d) ϵ_{π∨π′} := ϵ_{π} ∨ ϵ_{π′}

(e) ϵ_{π∧π′} := ϵ_{π} ∧ ϵ_{π′}

(f) ϵ_{∃x(x≤u∧θ(x,u))} := ∨_{a≤u} ϵ_{θ(a,u)}.

(g)  ϵ_{∀x(x≤u→θ(x,u))} := ∧_{a≤u} ϵ_{θ(a,u)}.  ♣

Notice that if ψ ∈ L_{𝕄}(P) has ≤ d quantifiers, all bounded by t ∈ 𝕄, and ψ contains k logical connectives, then s(ϵ_{ψ}) ≤ kt^{d} and d(ϵ_{ψ}) ≤ d + k.

Lemma 2.1.6 Suppose that P is a partitioning of {1, 2, ..., n} into disjoint classes each containing exactly p elements. Let ρ_{P} : VAR_{I,p} → {0, 1} be defined by A ∈ P ↔ ρ_{P} (p_{A}) = 1. Then for ψ ∈ L_{𝕄}(P) the following statements are equivalent:

(a) (𝕄, P) ⊧ ψ.

(b) (ϵ_{ψ})^{ρ_{P}} = 1.

Proof: Induction on the number of logical constants in ψ. □

2.2 The forcing set up

As above let 𝕄 be a countable non-standard model of Th(ℕ) over a countable first order language L which extends the language of arithmetic. We have fixed p ≥ 2 and I := {1, 2, ..., n} ⊆ 𝕄, n ∈ 𝕄 \ ω. Let L_{𝕄} and L_{𝕄}(P) be defined as above.

Definition 2.2.1 We say that ρ is a partial p-partitioning iff

(a) ∀A ∈ ρ A ⊆ I.

(b) ∀A ∈ ρ | A |= p.

(c) ∀A, B ∈ ρ A ≠ B → A ∩ B = ∅.

Let Set(ρ) := ∪_{A∈ρ} A ⊆ I. ♣

Definition 2.2.2 For k ∈ ℕ let

P_{k} := {ρ : ρ is a partial p −partitioning and (n− | Set(ρ) |)^{k} ≥ n}.

We define P := ∪_{k∈ℕ} P_{k}. The elements in P are ordered under inclusion. An element ρ ∈ P is called a (forcing) condition. We use letters A, B, C, ... to denote subsets of P. ♣

Notice that P_{1} ⊆ P_{2} ⊆ .... ⊆ P_{r} ⊆ .... ⊆ P, for each r ∈ ω. The idea is to use (P, ⊆) as the set of forcing conditions. As in [23]:

Definition 2.2.3 We say that D ⊆ P is dense iff ∀g ∈ P∃h ∈ D h ⊇ g.

We say that D is quasi-definable iff there exists a formula θ(x) ∈ L_{𝕄}(R_{ω}) such that D := {m ∈ 𝕄 : 𝕄 ⊧ θ(m)} (the relation R_{ω} is defined by R_{ω}(a) ↔ a ∈ ω). ♣

Example 2.2.4 P is dense and quasi-definable. P is not L_{𝕄}-definable.

Definition 2.2.5 We say that ρ_{G} ⊆ P is a generic filter iff

(i) ∀α ∈ ρ_{G}∀β ∈ P β ⊆ α → β ∈ ρ_{G}. (ii) ∀α, β ∈ ρ_{G}∃γ ∈ ρ_{G} γ ⊇ α ∧ γ ⊇ β. (iii) For D ⊆ P dense and quasi-definable ρ_{G} ∩ D ≠ ∅.

We use the abbreviation ρ̃_{G} := ∪_{α∈ρ_{G}} α. ♣

2.3 Generic objects

Lemma 2.3.1 If ρ_{G} ⊆ P is a generic filter, then ρ̃_{G} defines a partition of {1, 2, ..., n} into disjoint p-subsets.

Proof: The only problem is to show Set(ρ_{G}) = I. For an arbitrary u ∈ I let D_{u} := {α ∈ P : u ∈ set(α)}. It is straightforward to show that D_{u} is dense and quasi-definable so D_{u} ∩ ρ_{G} ≠ ∅. Thus for each u ∈ I there exists α_{u} ∈ D_{u} ∩ ρ_{G}, and thus each u ∈ Set(ρ̃_{G}). □

Lemma 2.3.2 For each ρ_{0} ∈ P there exists a generic filter ρ_{G} ⊆ P such that ρ_{0} ∈ ρ_{G}.

Proof: Recall that both 𝕄 and L are assumed to be countable, so there are only countably many quasi-definable dense sets. Let these be D_{1}, D_{2}, .... According to the definition of denseness there exists a sequence of conditions ρ_{1} ⊆ ρ_{2} ⊆ .... ∈ P with ρ_{j} ∈ D_{j}, j = 1, 2, ... and ρ_{1} ⊇ ρ_{0}. Clearly ρ_{0} ∈ ρ_{G} := {ρ : ρ ⊆ ρ_{k} for some k ∈ ω} is a generic filter. □

Definition 2.3.3 For a sentence ψ ∈ L_{𝕄}(P) we define the forcing relation |⊢ by letting ρ |⊢ ψ iff (𝕄, ρ̃_{G}) ⊧ ψ for all generic filters ρ_{G} ∋ ρ. ♣

Lemma 2.3.4 If (𝕄, ρ̃_{G}) ⊧ ψ for a generic filter ρ_{G}, then there exists ρ_{0} ∈ P such that ρ_{0} |⊢ ψ.

Proof: By use of induction on the logical complexity of a general formula ψ(x⃗), it is not hard to show that {(a⃗, ρ) ∈ 𝕄^{r} × P : ρ |⊢ ψ(ca⃗)} is quasi-definable. Continuing this argument for each L_{𝕄}(P)-sentence ψ, D := {ρ ∈ P : ρ |⊢ ψ ∨ ρ |⊢ ¬ψ} is both quasi-definable and dense. For the required ρ_{0} take any ρ_{G} ∩ D. □

Definition 2.3.5 For θ, ψ ∈ B_{<ω}(VAR_{I,p}) and ρ ∈ P, θ ≡_{ρ} ψ if θρ̃_{G} = ψρ̃_{G} for each generic filter ρ_{G} ∋ ρ.

For θ ∈ B_{<ω}(VAR_{I,p}) and ρ ∈ P we say that ρ forces θ^{P} = 1 (θ^{P} = 0) if for all generic ρ_{G} ∋ ρ, θρ̃_{G} = 1 (θρ̃_{G} = 0). This is written ρ |⊢ θ^{P} = 1 (ρ |⊢ θ^{P} = 0). ♣ The next lemma shows how each appearance of ¬ can be eliminated.

Lemma 2.3.6 Suppose that i_{0} ∈ A, A ⊆ I, | A |= p.

Suppose that π_{1} := ¬p_{A} and π_{2} := ∨_{B} p_{B}, where B runs through all B ⊆ I with | B |= p, A ≠ B and i_{0} ∈ B. Then π_{1} ≡_{ρ} π_{2} for all ρ ∈ P.

Proof: Direct verification. □

Lemma 2.3.7 For any Boolean circuit θ ∈ B_{d}(VAR_{I,p}), there exists a negation-free circuit θ̃ ∈ B_{d}(VAR_{I,p}) such that θ ≡_{ρ} θ̃ for any ρ ∈ P. Furthermore, s(θ̃) ≤ s(θ) · \binom{n−1}{p−1}.

Proof: First notice that ¬ ∨_{i} π_{i} ≡_{∅} ∧_{i} ¬π_{i}, and that ¬ ∧_{i} π_{i} ≡_{∅} ∨_{i} ¬π_{i}. So without loss of generality we can assume that negations appear only in front of the input variables. For each input variable p_{A} pick i_{0} ∈ A and replace each appearance of ¬p_{A} with ∨_{B: i_{0}∈B∧B≠A} p_{B}. According to lemma 2.3.6 θ ≡_{∅} θ̃. This new circuit θ̃, still has depth d. Furthermore, s(θ̃) ≤ s(θ) · max_{i_{0}}(s(∨_{B: i_{0}∈B,B≠A} p_{B})) = s(θ) · \binom{n−1}{p−1}. □

Lemma 2.3.8 For each bounded ψ ∈ L_{𝕄}(P), ρ |⊢ ψ iff ρ |⊢ (ϵ_{ψ})^{P} = 1.

Proof: Induction on the number of logical constants in ψ. □

Definition 2.3.9 Two conditions α and β are incompatible (α ⊥ β) if ∃A ∈ α∃B ∈ β A ≠ B ∧ A ∩ B ≠ ∅.

Two conditions α and β are compatible (α || β) if ∀A ∈ α∀B ∈ β A ≠ B → A ∩ B = ∅. ♣

Definition 2.3.10 B ⊆ P is a basis for P iff

(a) ∀α, β ∈ B α ≠ β → α ⊥ β.

(b)  ∀ρ ∈ P∃α ∈ B ρ || α.  ♣

Definition 2.3.11 || B ||:= max_{β∈B}(| Set(β) |). ♣

Lemma 2.3.12 Suppose that || B ||^{k}< n for all k ∈ ω (or in short-hand notation || B ||< n^{\frac{1}{ω}}). If ρ ∈ P and ρ || β, then ρ ∪ β ∈ P.

Proof: Assume that ρ ∈ P. Thus there are k_{0} ∈ ω such that (n− | Set(ρ) |)^{k_{0}} ≥ n. Also assume that β ∈ B, where || B ||≤ n^{\frac{1}{ω}}. Clearly | Set(β) |^{2k_{0}}≤ n. Suppose ρ || β. We have to show ρ ∪ β ∈ P. To show this, it suffices to show that

(n− | set(ρ ∪ β) |)^{2k_{0}} ≥ (n− | set(ρ) | − | Set(β) |)^{2k_{0}}

≥ (n^{\frac{1}{k_{0}}} − n^{\frac{1}{2k_{0}}} )^{2k_{0}} ≥ n.

To do this notice that 2^{k}n^{\frac{1}{2}} ≤ n for any k ∈ ω. □

The next lemma shows an important technical point in Ajtai’s choice of P. It allows us to assume that ∅ |⊢ ψ in cases where ρ_{0} |⊢ ψ for some ρ_{0} ∈ P. To see this replace I := {1, 2, ..., n} by I′ := {1, 2, ...., n′} where n′ := n− | Set(ρ_{0}) |. The lemma shows that if P’ is defined as P but with the underlying set I replaced by I′, then P’ can be identified with the set of conditions in P which extends ρ_{0}.

Lemma 2.3.13 Fix ρ ∈ P. Define

P^{ρ} := {ρ̃: ρ̃ is a partial p-partition of I \ set(ρ) and ρ̃ ∪ ρ ∈ P},

P_{k}(J) := {ρ̃: ρ̃ is a partial p-partition of J and (n′− | Set(ρ̃) |)^{k} ≥ n′} where J ⊆ I and n′ :=| J |.

Let P(J) := ∪_{k∈ω} P_{k}(J).

If J = Set(ρ) for ρ ∈ P, then P^{ρ} = P(Set(ρ)).

Proof: First we show the inclusion P^{ρ} ⊆ P(Set(ρ)). Suppose that ρ̃ ∈ P^{ρ}. By definition for some k_{0} ∈ ω, such that n′ ≤ n ≤ (n− | Set(ρ̃ ∪ ρ) |)^{k_{0}} = (n− | Set(ρ̃) | − | Set(ρ) |)^{k_{0}} = (n′− | Set(ρ̃) |)^{k_{0}}, so ρ̃ ∈ P(Set(ρ)).

Second, we show that the inclusion P(Set(ρ)) ⊆ P^{ρ}. According to the assumption that ρ ∈ P there exists l_{0} ∈ ω such that (n− | Set(ρ) |)^{l_{0}} ≥ n. According to the assumption that ρ̃ ∈ P^{ρ}, there exists l_{1} ∈ ω such that (n− | Set(ρ) | − | Set(ρ̃) | )^{l_{1}} ≥ n− | Set(ρ) |. Now (n− | Set(ρ ∪ ρ̃) |)^{l_{0}l_{1}} = (n− | Set(ρ) | − | Set(ρ̃) |)^{l_{0}l_{1}} ≥ (n− | Set(ρ) |)^{l_{0}} ≥ n, so ρ ∪ ρ̃ ∈ P. □

Lemma 2.3.14 Suppose that B is a basis for P and H ⊆ B. Suppose also that || B ||< n^{\frac{1}{ω}}. Then

(a) ρ |⊢ (∨_{h∈H} h)^{P} = 1 iff ρ is incompatible with all conditions h′ ∈ B \ H.

(b) ρ |⊢ (¬ ∨_{h∈H} h)^{P} = 1 iff ρ is incompatible with all conditions h′ ∈ H.

Proof: (a) ⇒: Suppose that ρ |⊢ (∨_{h∈H} h)^{P} = 1, but ρ is compatible with h′ ∈ B\H. By use of lemma 2.3.12 ρ′ := ρ ∪ h′ ∈ P. By using property (a) of a basis (definition 2.3.10) h′ is incompatible with all conditions in H. Clearly ρ′ ⊇ h so ρ′ is incompatible with all conditions in H. But then (∨_{h∈H} h)ρ̃_{G} = 0 for each generic filter ρ_{G} ∋ ρ′ (which exists by lemma 2.3.2). This contradicts ρ |⊢ (∨_{h∈H} h)^{P} = 1.

(a) ⇐: Assume that ρ is incompatible with all h′ ∈ B \ H, and let D := {ρ′ ∈ P : (ρ′ is compatible with some h′ ∈ H) or (ρ′ is incompatible with ρ)}. By definition 2.3.10, D ⊆ P is dense. Also D is quasi-definable. So according to lemma 2.3.2, there exists a generic filter ρ_{G} ∋ ρ. By definition 2.2.5 (iii) there exists α ∈ D ∩ ρ_{G}, so there exists h ∈ H with h ⊆ α ⊆ ρ̃_{G}.

(b) ⇒ / (b) ⇐ are proved as (a) ⇒ / (a) ⇐. □

Lemma 2.3.15 Let ϵ_{1}, ϵ_{2}, ...., ϵ_{u} u ∈ 𝕄, be an 𝕄-definable sequence of Boolean circuits, each of the form ϵ_{j} :≡ ∨_{h∈H_{j}} h. Let B_{1}, ..., B_{u} be an 𝕄-definable sequence and suppose that t < n^{\frac{1}{ω}} such that:

(a) for each j = 1, 2, ...u B_{j} ⊆ P, is a basis for P,

(b) for each j = 1, 2, .., u || B_{j} ||< t,

(c) for each j = 1, 2, ..., u, H_{j} ⊆ B_{j}. Then for every generic filter ρ_{G} either

(a) for all j ∈ {1, 2, .., u}, ϵρ̃_{G} ; j = 0, or

(b) there exists j_{0} ≤ u such that ϵρ̃_{G} ; j_{0} = 1 and ϵρ̃_{G} ; j = 0 for each j < j_{0}.

Proof: Let

D := {ρ ∈ P : (∃j_{0}∃β ∈ H_{j_{0}} β || ρ ∧ ∀γ ∈ ∪_{j<j_{0}}H_{j} ρ ⊥ γ) or (∀γ ∈ ∪_{j≤u}H_{j} ρ ⊥ γ)}.

Clearly D is quasi-definable. For each ρ_{0} ∈ P, if ρ_{0} is compatible with some β ∈ ∪_{j}H_{j}, then there must be a smallest j_{0} such that ρ_{0} is compatible with some β ∈ H_{j_{0}}. Here we uses that the least number principle is valid in 𝕄. Now ρ := h∪ρ_{0} ∈ P (by lemma 2.3.12), and thus ρ ∈ D. So D is dense. By definition 2.2.5 (iii) there exists ρ ∈ ρ_{G}∩D. This condition ρ is incompatible with all h ∈ H_{j}, j < j_{0}. As ρ̃_{G} ⊇ ρ ⊇ h ∈ H_{j_{0}} clearly (∨_{h∈H_{j_{0}}} h)ρ̃_{G} = 1. □

2.4 The key lemma

Recall that 𝕄 is a countable non-standard model of Th(ℕ) over a countable first order language L. As above we have fixed p ∈ ω\{1}, and I := {1, 2, ..., n} ⊆ 𝕄, n ∈ 𝕄\ω. As above the set P of forcing conditions consists of partial p-partitions ρ of I with | Set(ρ) |≤ n − n^{\frac{1}{ω}} for some k ∈ ω.

Lemma 2.4.1 (key lemma) Let θ_{1}, θ_{2}, ..., θ_{u} be an 𝕄-definable sequence of depth ≤ d ∈ ω circuits with Σ_{j=1}^{u} s(θ_{j}) ≤ n^{t} for some t < n^{\frac{1}{ω}} (i.e. t^{k} < n for all k ∈ ω).

Let ρ_{0} ∈ P. There exists ρ ⊇ ρ_{0}, ρ ∈ P and an 𝕄-definable sequence ϵ_{1}, ϵ_{2}, ..., ϵ_{u} of circuits together with an 𝕄-definable sequence B_{1}, B_{2}, .., B_{u} such that

(a) for j = 1, 2, .., u each B_{j}, is a basis for P,

(b) for j = 1, 2, ...u each ϵ_{j} is of the form ∨_{h∈H_{j}} h for some H_{j} ⊆ B_{j},

(c) for each j = 1, 2, ..., u, θ_{j} ≡_{ρ} ϵ_{j},

(d) for some s ≤ t · log(t) (actually for some s ≤ ω · t), || β ||≤ s.

If we combine the key lemma with lemma 2.3.15 we get:

Corollary 2.4.2 If θ_{1}, θ_{2}, ....θ_{u} is an 𝕄-definable sequence of depth d ∈ ω circuits with Σ_{j=1}^{n} s(θ_{j}) ≤ n^{t} for some t < n^{\frac{1}{ω}}, then for any generic filter ρ_{G} ⊆ P either

(a) for all j ≤ u θρ̃_{G} ; j = 1, or

(b) there exists j_{0} ≤ u, such that θρ̃_{G} ; j_{0} = 1 and θ̃ρ̃_{G} ; j = 0 for all j < j_{0}.

Before we prove the key lemma, we need to do some preparatory work.

2.5 Random conditions

My aim is to add a suitable probability distribution μ on the space P of forcing conditions.

Lemma 2.5.1 For k ≥ 2p + 1, k ∈ ℕ, and fix m < n such that (n − m)^{k+1} > n ≥ (n − m)^{k}. Let μ_{sym} be the symmetrical probability distribution (perceived from inside 𝕄) on the set \{ρ ∈ P :| Set(ρ) |= m\}. For each h ∈ P with | h |< n^{\frac{1}{ω}}, Pr(h ⊆ ρ) > n^{\frac{1}{2}} Pr(h || ρ ∧ ¬(h ⊆ ρ)).

Proof: Notice that for fixed J ⊆ I with | J |= m the number η(m, p) of partial p-partitions ρ with Set(ρ) = J is

η(m, p) = \frac{m!}{(p!)^{\frac{m}{p}} (\frac{m}{p})!}

when m is divisible by p and 0 otherwise. The set {ρ ∈ P :| Set(ρ) |= m} contains \binom{n}{m} · η(m, p) elements. If h ∈ P, | Set(h) |= up and J ⊆ I \ Set(h) with | J |= b, then

Pr(h ⊆ ρ∧J ∩Set(ρ) = ∅) = \frac{\binom{n−up−b}{m−up} η(m − up, p)}{\binom{n}{m} η(m, p)} = \frac{(n − up − b)!(n − m)!(p!)^{u}(\frac{m}{p})!}{n!(n − m − b)!(\frac{m}{p} − u)!}

Now suppose n − n^{\frac{1}{k}} ≤ m < n − n^{\frac{1}{k+1}} , and b, u < n^{\frac{1}{ω}}. There exists a suitable real (in the sense of 𝕄) c ∈ [0, 1] such that Pr(h ⊆ ρ ∧ J ∩ Set(ρ) = ∅) = (\frac{1}{n})^{u(p−1)+b(1− \frac{1}{k+c})}. Here we use the fact that a sufficiently strong part of real analysis can be developed inside 𝕄. Now

Pr(h || ρ ∧ ¬(h ⊆ ρ)) = Σ_{j=0}^{u−1}Σ_{h′⊆h,|h′|=j} Pr(h′ ⊆ ρ ∧ (Set(h) \ Set(h′) ∩ Set(ρ) = ∅))

= Σ_{j=0}^{u−1}Σ_{h′⊆h,|h′|=j} (\frac{1}{n})^{( \frac{p}{k+c} −1)j+pu(1− \frac{1}{k+c})}

= Σ_{j=0}^{u−1} \binom{u}{j}(\frac{1}{n})^{( \frac{p}{k+c} −1)j+pu(1− \frac{1}{k+c})}

In general Σ_{j=0}^{u−1}\binom{u}{j}a^{j} = (a + 1)^{u} − a^{u}. Let a := n^{1− \frac{p}{k+c}}, and notice that Σ_{j=0}^{u−1}\binom{u}{j}a^{j} ≤ 2ua^{u−1}. Thus

Σ_{j=0}^{u−1}\binom{u}{j}(\frac{1}{n})^{( \frac{p}{k+c} −1)j+pu(1− \frac{1}{k+c})} = 2u(\frac{1}{n})^{pu(1− \frac{1}{k+c})} · (\frac{1}{n})^{( \frac{p}{k+c} −1)(u−1)}

= 2u · (\frac{1}{n})^{(p−1))u+(1− \frac{p}{k+c})}

= Pr(h ⊆ ρ) · 2u(\frac{1}{n})^{(1− \frac{p}{k+c})} ≤ Pr(h ⊆ ρ) · (\frac{1}{n})^{\frac{1}{2}}

when k ≥ 2p + 1. In all estimates c is chosen as a suitable real constant in [0, 1]. □

Lemma 2.5.2 Fix k ∈ ℕ. Also fix t < n^{\frac{1}{ω}}. Then there exists a (global) probability distribution μ_{glo} on the 𝕄-definable set consisting of all partial p-partitions, such that for each h ∈ P with | h |≤ t

(i) If C(ρ) is a monotone property (i.e. C(ρ) ∧ ρ ⊆ ρ′ → C(ρ′)), then

Pr(C(ρ) | h || ρ) ≥ \frac{1}{8} · Pr(C(ρ) | h || ρ ∧ ¬(h ⊆ ρ)),

(ii) there is s ∈ 𝕄 \ ω such that Pr(ρ ∉ P_{4k} ∨ (ρ ∉ P \ P_{k})) ≥ 1 − exp(n^{s}).

Proof: Notice that in general Pr(C | B_{1} ∨ B_{2} ∨ ... ∨ B_{k}) ≤ max_{j}Pr(C | B_{j}), so if h := ∪_{i∈F} {A_{i}}, it suffices to construct a suitable μ_{glo} which besides (ii) has Pr(C | ∧_{i∈F} A_{i} ∈ ρ) ≥ Pr(C | (∧_{i∈G} A_{i} ∈ ρ) ∧ (∧_{j∈F \G} Set(ρ) ∩ A_{j} = ∅)) for any G ⊆ F. Let A :≡ ∧_{i∈F} (A_{i} ∈ ρ), B :≡ ∧_{i∈G} (A_{i} ∈ ρ) ∧ (∧_{i∈F \G} (A_{i} ∩ Set(ρ) = ∅)), C ≡ C(ρ), and for l = 0, 1, 2, ... let D_{l} :≡| ρ |= l. Let P_{l} :≡ Pr(D_{l}), and let g :=| G |. We choose μ_{glo} symmetric on each each set {ρ : D_{l}}. We define μ_{glo} by choosing suitable numbers p_{0}, p_{1}, ...p_{u} with Σ_{j}p_{j} = 1. Notice that any μ_{glo} defined this way, for any l = g, g + 1, ...., u has Pr(C | A ∧ D_{l}) ≥ Pr(C | B ∧ D_{l−g}). To see this notice that any monotone property C can be written as a disjunction ∨_{δ} (δ ⊆ ρ). Thus for l = g, g + 1, ..., u we have

(∗)  \frac{Pr(C ∧ A ∧ D_{l})}{Pr(A ∧ D_{l})} ≥ \frac{Pr(C ∧ B ∧ D_{l−g})}{Pr(B ∧ D_{l−g})}

We have to show that \frac{Pr(C∧A)}{Pr(A)} ≥ \frac{1}{8} · \frac{Pr(C∧B)}{Pr(B)}. Now

\frac{Pr(C ∧ A)}{Pr(A)} = \frac{Σ_{l} Pr(C ∧ A ∧ D_{l}) · p_{l}}{Σ_{l} Pr(A ∧ D_{l}) · p_{l}} ≥ (1 + Σ_{l=0}^{g−1})^{−1} · \frac{Σ_{l=g}^{u} Pr(C ∧ A ∧ D_{l}) · p_{l}}{Σ_{l=g}^{u} Pr(A ∧ D_{l}) · p_{l}}

The inequality holds because A is a monotone property and Σ_{l=0}^{g−1} Pr(A ∧ D_{l})p_{l} ≤ Σ_{l=0}^{g−l}Pr(A ∧ D_{g})p_{l} ≤ Σ_{l=g}^{2g} Pr(A ∩ D_{l})p_{l} ≤ Σ_{l=g}^{u}Pr(A ∧ D_{l})p_{l}. This holds because 2g < n^{\frac{1}{ω}} < l_{0} as long as p_{l+g} ≥ p_{l} for l ≤ g. But by (∗)

\frac{Σ_{l=g}^{u} Pr(C ∧ A ∧ D_{l}) · p_{l}}{Σ_{l=g}^{u} Pr(A ∧ D_{l}) · p_{l}} ≥ \frac{Σ_{0}^{u−g} Pr(C ∧ B ∧ D_{l}) · p_{l+g}}{Σ_{l=0}^{u−g} Pr(B ∧ D_{l}) · p_{l+g}}

≥ \frac{Σ_{l} Pr(C ∧ B ∧ D_{l}) · p_{l} · min_{l}(\frac{p_{l+g}}{p_{l}})}{Σ_{l} Pr(B ∧ D_{l}) · p_{l} · max_{l}(\frac{p_{l+g}}{p_{l}})} = min_{l}(\frac{p_{l+g}}{p_{l}}) · min_{l}(\frac{p_{l}}{p_{l+g}}) · \frac{Pr(C ∧ B)}{Pr(B)}.

Now we are ready to define p_{0}, p_{1}, .... Recall that g ≤| h |≤ t.

For l < l_{0} let p_{l+1} := 2^{\frac{1}{t}} · p_{l}, and for l_{0} ≤ l let p_{l+1} := 2^{− \frac{1}{t}} p_{l}. Now min_{l}(\frac{p_{l+t}}{p_{l}}) = min_{l}(\frac{p_{l}}{p_{l+t}}) = \frac{1}{2} and (1 + Σ_{l=0}^{t−1}p_{j})^{−1} ≤ \frac{1}{2} so

\frac{Pr(C ∧ A)}{Pr(A)} ≥ \frac{1}{8} · \frac{Pr(C ∧ B)}{Pr(B)}.

Thus (i) holds. Furthermore notice that if (n − pl_{0})^{k} ≥ n > (n − pl_{0})^{k−1} then the probabilities are sufficiently concentrated around l_{0} to ensure that (ii) is satisfied. □

The factor \frac{1}{8} can be replaced by any standard rational q < 1. Also notice that there are many other choices of the distribution p_{0}, ..., p_{u}. One can for instance choose the binomial distribution with mean l_{0}. The point is that min_{l}(\frac{p_{l+t}}{p_{l}}) · min_{l}(\frac{p_{l}}{p_{l+t}}) is not too small, while at the same time the probability distribution tails off sufficiently fast.

Notice that a phenomenon reminiscent of the complementary principle, is involved. If μ_{glo} is focussed on some P_{k} then (i) cannot hold. On the other hand if μ_{glo} is unfocussed and global (ii) cannot hold. As an example of the first claim consider the property C(ρ) :≡ ∃δ (| δ |= l_{0}− | h | +1 ∧ Set(δ) ∩ Set(h) = ∅ ∧ δ ⊆ ρ. If p_{l_{0}} = 1 then Pr(C | h ⊆ ρ) = 0 while Pr(C | h || ρ ∧ ¬(h ⊆ ρ)) = 1. By lemma 2.5.1 this is a violation of condition (i).

Corollary 2.5.3 For k ≥ 2p + 1, k ∈ ℕ and t < n^{\frac{1}{ω}} there exists a 𝕄-definable probability distribution μ on P_{4k}, such that

(1) for each h ∈ P with | h |< t, Pr(h ⊆ ρ) > n^{\frac{1}{2}} · Pr(h || ρ ∧ ¬(h ⊆ ρ)),

(2) for each monotone property C(ρ) Pr(C(ρ) ∨ ρ ∉ P_{2k} | h || ρ) ≥ \frac{1}{8} · Pr(C(ρ) ∨ ρ ∉ P_{2k} | h || ρ ∧ ¬(h ⊆ ρ)).

Proof: Let μ be the (normalised) probability distribution obtained by restricting μ_{glo} to P_{4k}. □

We need the following elementary fact:

Lemma 2.5.4 For each number w,

Pr(A | B ∧ C) ≥ w · Pr(A | B) iff Pr(C | A ∧ B) ≥ w · Pr(C | B).

Proof: Both sides holds iff Pr(A ∧ B ∧ C)Pr(B) ≥ w · Pr(A ∧ B)Pr(B ∧ C). □

Corollary 2.5.5 If μ is chosen on P_{4k} such that condition (1) and (2) in corollary 2.5.3 hold, then

Pr(h^{j} ⊆ ρ ∨ ρ ∉ P_{2k} | h^{j} || ρ ∧ (ρ⊥h^{1}) ∧ .... ∧ (ρ⊥h^{j−1})) ≥ \frac{1}{8} · Pr(h^{j} ⊆ ρ | h^{j} || ρ).

Proof: Let A :≡ (ρ^{j} ⊆ ρ), B :≡ h^{j} || ρ and let C ≡ (ρ⊥h^{1})∧....∧(ρ⊥h^{j−1})∨¬ρ ∈ P_{2k}. The lemma now follows by use of condition (2) in corollary 2.5.3 and lemma 2.5.4. □

2.6 Collapse of circuits

In order to prove the key lemma we prove that:

Lemma 2.6.1 Suppose that θ :≡ ¬(∨_{h∈H} h) where s(θ) ≤ n^{t} for some t < n^{\frac{1}{ω}}. Let s < n^{\frac{1}{ω}}. Suppose that μ is a probability distribution satisfying (1) and (2) in corollary 2.5.3 on P_{4k} for some k ≥ 2p + 1, k ∈ ω. Then there exists an 𝕄-definable set C ⊆ P_{k} such that C ⊆ {ρ ∈ P_{4k} : ∃H̃ ⊆ P, || H̃ ||≤ ps such that θ ≡_{ρ} ∨_{h∈H̃} h with s(∨_{h∈H̃} h) ≤ n^{t}} and such that

μ(C) ≥ 1 − (\frac{1}{n})^{\frac{ks−2ps}{2k}}

Corollary 2.6.2 Let ϵ_{1}, ϵ_{2}, ..., ϵ_{u} be an 𝕄-definable sequence of depth ≤ d circuits with Σ_{j} s(ϵ_{j}) ≤ n^{t} for some t < n^{\frac{1}{ω}}. Let ρ_{0} ∈ P. There exists ρ ⊇ ρ_{0}, ρ ∈ P and an 𝕄-definable sequence ϵ′_{1}, ...., ϵ′_{u} of depth ≤ d − 1 (when d ≥ 3) circuits, with Σ_{j} s(ϵ′_{j}) ≤ n^{t} such that s(ϵ′_{j}) ≤ s(ϵ_{j}) j = 0, 1, 2, ..... When d = 2 there exists an 𝕄-definable sequence ϵ′_{1}, ϵ′_{2}, ..., ϵ′_{u} of depth ≤ 2 circuits of the form ϵ′_{j} :≡ ∨_{h∈H_{j}} h. Furthermore, each set H_{j} ⊆ P contains conditions h which have all | Set(h) |≤ ps for some s with s > ω · t, and s < n^{\frac{1}{ω}}.

Proof: (lemma 2.6.1 ⇒ corollary 2.6.2). By use of lemma 2.3.7 we can assume ϵ_{1}, ϵ_{2}, ..., ϵ_{u} are all negation-free. There is an 𝕄-definable sequence ϵ̃_{1}, ..., ϵ̃_{u} of depth ≤ d − 1 circuits, where all “input nodes” are depth ≤ 2 circuits. Let π_{1}, π_{2}, ..., π_{r} be the 𝕄-definable sequence of these. Clearly r ≤ n^{t}. Without loss of generality, each π_{j} is either a “disjunction of conjunctions” or is a “conjunction of disjunctions”. Notice Σ_{j} s(π_{j}) < n^{t}. By use of lemma 2.6.1 (which according to lemma 2.3.13 also holds when the underlying set I is replaced by I′ := I \ Set(ρ_{0})) for some fixed k ≥ 2p + 1, for each j ≤ r there exists an 𝕄-definable sequence C_{1}, ..., C_{r} ⊆ P_{k} each with

μ(C_{j}) ≥ 1 − (\frac{1}{n− | Set(ρ) |})^{\frac{ks−2ps}{2k}}

such that for j = 1, 2, .., r and all ρ ∈ C_{j} π_{j} ≡_{ρ} ∨_{h∈H′}h if π_{j} is a disjunction of conjunctions, and π_{j} ≡_{ρ} ¬(∨_{h∈H′} h) if π_{j} is a conjunction of disjunctions.

Now μ(C_{1} ∩ C_{2} ∩ .... ∩ C_{r}) ≥ 1 − r · (\frac{1}{n})^{\frac{ks−2ps}{2k}} > 0 (when s ≥ 2kt). So there exists ρ ∈ C_{1} ∩ .... ∩ C_{r} with ρ ⊇ ρ_{0}. Replace each depth ≤ 2 “input” circuits with a suitable depth ≤ 2 circuit. □

Repeated use of this corollary (applied at most d times) reduces problem of proving the key lemma to that of proving lemma 2.6.1.

2.7 The switching lemma

Definition 2.7.1 For i ∈ I let

E_{i} := {h′ : h′ ⊇ h ∧ Set(h′) ⊇ Set(h) ∪ {i}∧ | h′ |≤| h | +1}.
♣

Definition 2.7.2 We say that H_{2} ⊆ P is an atomic tree-like refinement of H_{1} ⊆ P, (H_{1} →_{ATR} H_{2}) if ∃h ∈ H_{1}∃i ∈ I H_{2} = (H_{1} ∪ E_{i}(h)) \ {h}.

We say that H̃ is a tree-like refinement of H, (H →_{T R} H̃) if there exists an 𝕄-definable sequence (H_{0}, H_{1}, ..., H_{r}) such that H_{0} = H, H_{r} = H̃ and for each j < r H_{j} →_{AT R} H_{j+1}. ♣

Definition 2.7.3 B ⊆ P is a tree-like basis if {∅} →_{T R} B. ♣

Lemma 2.7.4 Suppose that B ⊆ P is 𝕄-definable and that || B ||< n^{t} for some fixed t < \frac{1}{ω}. If B is a tree-like basis, then B is a basis for P.

Proof: First notice that each α, β ∈ B (α ≠ β) are incompatible. Suppose that ρ_{0} ∈ P is incompatible with all β ∈ B. Let (B_{0}, ..., B_{r}) be an 𝕄-definable sequence with B_{0} := {∅}, B_{r} := B and where B_{j} →_{AT R} B_{j+1} for j = 0, 1, ..., r − 1. 𝕄 satisfies the least number principle so there must be a smallest j_{0} such that ρ_{0} is incompatible with all β ∈ B_{j_{0}}. There exists β′ ∈ B_{j_{0}−1} compatible with ρ_{0}. As | set(β′) |≤ n^{\frac{1}{ω}} by lemma 2.3.12 ρ = ρ_{0} ∪ β′ ∈ P. Let i_{0} ∈ I such that B_{j_{0}} = (B_{j_{0}−1} ∪ E_{i_{0}}(β′′)) \ {β′′}.

Now as ρ (like ρ_{0}) is incompatible with all conditions in B_{j_{0}}, β′ ∉ B_{j_{0}} and thus β′ = β′′. We get the required contradiction by noticing that ρ ∈ P must be compatible with some ρ′ ∈ E_{i_{0}}(β′) □

Definition 2.7.5 For H ⊆ P and for ρ ∈ P let

H^{ρ} := {h′ ∈ P : h′ = h \ ρ for some h ∈ H with h || ρ}.

We say that B refines H if for each β ∈ B and each h ∈ H if β || h, there is h′ ∈ H such that h′ ⊆ β. ♣

Lemma 2.7.6 If B is a basis which refines H, and H_{B} := {β ∈ B : ∃h ∈ H β ⊇ h} then ∨_{h∈H} h ≡_{ρ} ∨_{h′∈H_{B}} h′ for all ρ ∈ P.

Proof: Straightforward. □

Lemma 2.7.7 Let H ⊆ P be a collection of conditions with ∀h ∈ H, | Set(h) |≤ n^{t} for some fixed t < n^{\frac{1}{ω}}. Let ρ_{0} ∈ P_{k}, k ∈ ω, and let μ be a probability distribution on P_{4l}(I \ Set(ρ_{0})) (l ≥ 2p + 1) which satisfies the conditions in corollary 2.5.3.

If ρ ∈ P_{4l}(I \ Set(ρ_{0})) is chosen randomly according to the probability distribution μ, then for each s < n^{\frac{1}{ω}}, with probability ≥ 1−(\frac{1}{n−|Set(ρ_{0})|})^{\frac{ks−2ps}{2k}} there exists a tree-like basis B which refines H^{ρ} such that || B ||≤ ps.

This lemma immediately implies lemma 2.6.1. To see this let

C := {ρ : ∃B a tree − like basis which refines H and || B ||≤ ps}.

Notice C is 𝕄-definable. According to lemma 2.7.6, the θ in lemma 2.6.1, has θ ≡_{ρ} ∨_{h∈H_{B}} h where H_{B} := {β ∈ B : ∃h ∈ H β ⊇ h}. Thus to show the key lemma it suffices to show lemma 2.7.7.

2.8 Some games involving forcing

As above assume 𝕄 to be a countable non-standard model. Assume also that p ∈ ℕ \ {1} and I := {1, 2, ..., n} ⊆ 𝕄, with n ∈ 𝕄 \ ω be fixed. Let P_{1} ⊆ P_{2} ⊆ .... ⊆ P_{r} ⊆ .... ⊆ P, r ∈ ω, be the stratification of P defined above. Our aim is to show lemma 2.7.7.

Definition 2.8.1 Suppose that t ≤ s where s < n^{\frac{1}{ω}} (e.g. t, s are small) and let < h^{1}, h^{2}, ..., h^{v} >∈ 𝕄, v ∈ 𝕄 be a sequence of conditions with | Set(h^{j}) |≤ t, j ≤ v. Suppose also that {h^{1}, h^{2}, ..., h^{v}} is complete for P (i.e. ∀ρ ∈ P ∃j ≤ v ρ || h^{j}). The game G(n, k, t, s, < h^{1}, h^{2}, ..., h^{v} >) is played by two players I and II as follows:

\underline{Round 0:} Player I selects a condition ρ ∈ P_{k}.

\underline{Round 1:} Consider the first i ≤ v where h_{1} := h^{i} is compatible with ρ (which exists because the collection {h^{1}, .., h^{v}} is assumed to be complete for P).

If ρ ⊇ h_{1} player I wins and the output of the game is ∅.

If Set(h_{1}) \ Set(ρ) ≠ ∅ let a_{1} := min(Set(h_{1}) \ Set(ρ)) ∈ I. Player II selects an p-element set A ⊆ I such that:

(1) {A} is compatible with ρ ({A} || ρ).

(2) {A} is incompatible with h_{1} ({A} ⊥ h_{1}).

(3) a_{1} ∈ A. Let δ_{1} := {A} and proceed to the next round. \underline{Round j+1:} Consider the next condition h_{j+1} := h^{i_{j+1}}, i_{j+1} > i_{j} compatible with ρ∪δ_{j} (according to lemma 2.3.12 such exists because ρ∪δ_{j} ∈ P when j ≤ s, and {h^{1}, ..., h^{v}} is complete for P).

If ρ ∪ δ_{j} ⊇ h_{j+1} player I wins and the output of the game is δ_{j}.

If Set(h_{j+1}) \ Set(ρ) ≠ ∅ let a_{j+1} := min(Set(h_{j+1}) \ Set(ρ)) ∈ I. Player II selects a p-element set A ⊆ I such that:

(1) A ∩ Set(ρ) = ∅.

(2) {A} is incompatible with h_{j+1}.

(3) a_{j+1} ∈ A. Let δ_{j+1} := δ_{j} ∪ {A}, and proceed to the next round. \underline{Round s+1:} If this round is reached, player II wins and the game is terminated. ♣

Notice that player I does influence the game after the choice of ρ. The strategies of player I can thus be identified with the conditions in P_{k}.

Definition 2.8.2 We call ρ ∈ P_{k} a winning strategy for player I, if player wins irrespectively of what player II chooses. ♣

Lemma 2.8.3 Suppose that H = H_{0} ∪H_{1} is complete for P (i.e. ∀ρ ∈ P ∃h ∈ H ρ || h). Suppose that H_{0} := {h^{1}, ..., h^{u}} and H_{1} := {h^{u+1}, ..., h^{v}} u ≤ v ∈ 𝕄. Consider the game G(n, k, t, s, < h^{1}, h^{2}, ..., h^{v} >), and suppose that ρ ∈ P_{k} is a winning strategy for player I. Let B be the set of possible outputs (when player II varies his/her possible plays). Then B is a tree-like basis relative to I \ Set(ρ). Furthermore, B refines H_{0}^{ρ} and has || B ||≤ ps.

Proof: We are given a winning strategy ρ for player I. We have to show that B is a tree-like basis. We view each δ constructed at a certain stage in an actually played game, as a (uniquely defined) “situation”. Let S(δ) denote the situations which can be reached from δ. We want to construct B as a sequence

{∅} →_{AT R} B_{1} →_{AT R} .... →_{AT R} B_{j} →_{AT R} B_{j+1} → .... → B.

Suppose that B_{j} has been constructed. Pick any situation δ′ which has not been reached so far, but which can be reached from a situation corresponding to a δ ∈ B_{j} which has already been considered. Let B_{j+1} := (B_{j} ∪ E_{a}(δ)) \ {δ} where a := min(Set(h) \ Set(ρ)). Here h denotes the next h^{i} compatible with ρ in the situation corresponding to δ. As ρ was assumed to be a winning strategy for player I, this procedure terminates, and all β ∈ B get | Set(β) |≤ ps.

Finally we show that B refines H_{0}^{ρ}. We have to show that if h || β for some h ∈ H_{0}^{ρ} and β ∈ B, then there exists h′ ∈ H_{0}^{ρ} such that h′ ⊆ β. So suppose β is compatible with (h^{j})^{ρ} ∈ {(h^{1})^{ρ}, (h^{2})^{ρ}, ..., (h^{u})^{ρ}}. If β ⊇ (h^{j})^{ρ} we are done. If ¬(β ⊇ (h^{j})^{ρ} the game which produced β, must have terminated \underline{before} h^{j} so there must be j′ < j such that (h^{j′})^{ρ} ⊆ β. As the sequence h^{1}, h^{2}, ..., h^{u}, h^{u+1}, ..., h^{v} had all the elements from H_{0} listed in the beginning, (h^{j′})^{ρ} ∈ H_{0}^{ρ}. □ The next theorem shows that “almost all” (in the sense of μ) strategies ρ are winning strategies for player I. More specifically: Theorem 2.8.4 Consider the game G(n, k, t, s, < h^{1}, h^{2}, ..., h^{v} >). Let W_{I} ⊆ P_{k} be the set of winning strategies for player I (we only consider 𝕄-definable strategies). If μ is a probability distribution on P_{4k} which satisfies condition (1) and (2) in corollary 2.5.3, then

μ(W_{I}) ≥ 1 − (\frac{1}{n})^{\frac{ks−2ps}{2k}} .

Notice that t does not enter the estimate as long as t < n^{\frac{1}{ω}}.

We show theorem 2.8.4 by comparing the game G(n, k, t, s, < h^{1}, h^{2}, .., h^{v} >) with another game G′(n, k, t, s). Definition 2.8.5 The game G′(n, k, t, s) is played by two players I and II as follows (all sets etc. are 𝕄-definable).

Player II selects J ⊆ I, with | J |≤ ps, and selects a sequence h^{1}, h^{2}, .., h^{l} of conditions each with Set(h^{i}) ⊆ I \ J, and | Set(h^{i}) |≤ t.

Player I then selects a condition ρ ∈ P_{k}. Consider the first condition h := h^{j} compatible with ρ (if there is no such player I wins). If h ⊆ ρ player I wins, otherwise player II wins. ♣ In this game player II makes the choices \underline{before} player I. Clearly player I always has a winning reply (just choose ρ ⊇ h^{1}). We claim almost all player I’s replies are winning: Theorem 2.8.6 Let W̃_{I}(τ) be the set (𝕄-definable) of replies ρ which ensure a win for player I after player II made a choice τ. Then if μ is a probability distribution which satisfies condition (1) and (2) in corollary 2.5.3,

μ(W̃_{I}(τ)) ≥ 1 − (\frac{1}{n})^{\frac{1}{2}} .

Proof: First notice

μ(W̃_{I}(τ)) ≥ min_{j} Pr(h^{j} ⊆ ρ | h^{j} || ρ ∧ ρ ⊥ h^{1} ∧ ... ∧ ρ ⊥ h^{j−1}).

According to lemma 2.5.4 and condition (2) in corollary 2.5.3 for any j

Pr(h^{j} ⊆ ρ | h^{j} || ρ ∧ (ρ ⊥ h^{1}) ∧ .... ∧ (ρ ⊥ h^{j−1})) ≥ Pr(h^{j} ⊆ ρ | h^{j} || ρ)

(let A ≡ (h^{j} ⊆ ρ), B ≡ h^{j} || ρ and C ≡ ρ ⊥ h^{1} ∧ .... ∧ ρ ⊥ h^{j−1}). But by condition (1) in corollary 2.5.3

Pr(h^{j} ⊆ ρ | h^{j} || ρ) = \frac{Pr(h^{j} ⊆ ρ)}{Pr(h^{j} ⊆ ρ) + Pr(h^{j} || ρ ∧ ¬(h^{j} ⊆ ρ))} ≥ 1 − (\frac{1}{n})^{\frac{1}{2}} . □

Lemma 2.8.7 Suppose that μ satisfies condition (1) and (2) in corollary 2.5.3. Let w = max_{τ}(μ(W̃_{I}(τ)). Then for each strategy v of player II in the first game

μ(W̃_{I}(v)) ≥ 1 − (1 − w)^{s} ≥ 1 − (\frac{1}{n})^{\frac{s}{2}} .

Proof: The task for player II to survive round 1 of the game G′(n, k, t, s) (if player I selects the reply ρ randomly) is “easier” than the task of surviving any specific round j of the game G(n, k, t, s, < h^{1}, h^{2}, ..., h^{v} >). More formally the probability Pr(survives round k | history of the game) is

≥ min_{j}P r(h^{j} ⊆ ρ | h^{j} || ρ ∧ (ρ ⊥ h^{1}) ∧ ... ∧ (ρ ⊥ h^{j−1})) ≥ min_{j} Pr(h^{j} ⊆ ρ | h^{j} || ρ).

□

Lemma 2.8.8

μ(W_{I}) ≥ 1 − (Σ_{v}(μ(W̃_{I}(v)))) ≥ 1 − (\frac{1}{n})^{\frac{s}{2}} · n^{\frac{ps}{k}} ≥ 1 − (\frac{1}{n})^{\frac{ks−2ps}{2k}} > 0

when k ≥ 2p + 1.

Proof: The number of strategies for player II in the first game is ≤ n^{\frac{ps}{k}}. □ This completes the proof of theorem 2.8.4. Now lemma 2.7.7 follows by combining lemma 2.8.3 and theorem 2.8.4.

2.9 Some consequences

Suppose that 𝕄 is a countable non-standard model of Th(ℕ) in some countable first order language L. Suppose L extends the language of Arithmetic. Let p ≥ 2, p ∈ ω and let n ∈ 𝕄 \ ω. Assume that n not is divisible by p. Let

𝕄_{n}^{∗} := {m ∈ 𝕄 : t(n) > m for some term t ∈ L}.

So far we are able to prove:

Theorem 2.9.1 (weak version) If all terms t ∈ L have sub-exponential growth rate, then for each generic filter ρ_{G} (𝕄_{n}^{∗}, ρ̃_{G}) ⊧ ¬Count(p). On the other hand (𝕄_{n}^{∗}, ρ̃_{G}) satisfies induction for bounded L_{P} -formulas. As above ρ̃_{G} := ∪_{α∈ρ_{G}} α.

In the next two sections I strengthen this result. I show that the the model (𝕄_{n}^{∗}, ρ̃_{G}) satisfies the Count(q) principle exactly when certain exceptional forests do not exists. Proof: The argument is very similar to the argument in [2]. So I only outline the argument.

It suffices to show that the least number principle is valid for bounded L_{P} -formulas with parameters in 𝕄_{n}^{∗}. Now translate each instance of the least number principle into a Boolean circuit of the form LNP_{u}(π_{1}, π_{2}, .., π_{u}) := π_{u} ∨(∨_{j≤u}(¬π_{j} ∧(∧_{k<j} π_{k}))). According to the general collapsing result from section 1, each π_{j} can be replaced (and this can be done simultaneously) by disjunction of small positive conjunctions (or by negations of disjunctions of small positive conjunctions). According to the key lemma (lemma 2.4.1) for \underline{any} generic filter ρ_{G} if (π_{u})ρ̃_{G} = 0 there exists j_{0} ≤ u with (π_{j_{0}})ρ̃_{G} = 0 and with (π_{j})ρ̃_{G} = 1 for all j < j_{0}. A simple argument shows that LNP_{u}(π_{1}, ..., π_{u})ρ̃_{G} = 1. By lemma 2.1.6 (𝕄_{n}^{∗}, ρ̃_{G}) satisfies induction for bounded L_{P} -formulas with parameters in 𝕄_{n}^{∗}. □

3 Forests of decision trees

The specially labelled trees we are going to consider can also be viewed as decision trees ^{6} . In our case the decisions concern a (hypothetical) partitioning of a finite set I := {1, 2, ..., n} into disjoint p element subsets. To avoid trivial counter examples we always assume n is much larger than both p and the hight of the trees. All trees are rooted and finite (in later parts of the argument “finite” in the sense of a non-standard model of first order Arithmetic). When we follow a branch from the root towards the leafs we make successive decisions building up (parts of) some mathematical object. In this case a partial partitioning of I into disjoint p-element subsets. At each vertex v, except at the leafs, there is assigned a “question” i_{v} ∈ I. At the vertex v we are asked to decide which p element subset A ⊆ I the element i_{v} belongs to. All possible choices which define the partitioning at i_{v} have to be represented. There is a one to one correspondence between possible choices (at i_{v}) and the sons from i_{v}. The label α of a branch is identified with the final object (here a partial partitioning) which has been constructed. Suppose that we are given a forest T_{1}, T_{2}, ..., T_{u} of decision trees. If each object (label on branch) appears 0 modulo q times, does q divide u? If there exists a global object (in this case when p divides n) the answer is always positive. This type of question has not previously been considered in the literature. For almost any mathematical structure, it is possible to define such decision trees. They specify the local diagrams. In section 6 our analysis naturally leads us to consider another type of decision trees. Now let us focus on (p, n)-labelled trees. Notice first that each (p, n)-labelled tree is a graphical representation of a tree-like basis. Because of this, the concepts from section 2 (like conditions and restrictions ) will keep their obvious meaning.

6I think that this view is due to P.Beame and T.Pitassi

My aim is show that we have the following characterisation.

Theorem Let q, p ≥ 2 and h ∈ ℕ. Suppose that h > q. Then the following statements always hold simultaneously.

(a) All prime factors in p divide q.

(b) There exists n_{0} such that for all n > n_{0} which are not divisible by p there is a (p, n)-labelled forest T_{1}, T_{2}, ...., T_{u} such that:

(i) All trees have hight ≤ h.

(ii) Each type of branch appears 0 modulo q times.

(iii) u ≠ 0 modulo q.

Later I also discuss the general case where there are less restrictions on the (asymptotic) hight of the trees.

3.1 Some easy results

First let me illustrate the definition with a few trivial observations.

Example 3.1.1 Suppose that p divides q and that p does \underline{not} divide n. Consider the forest

[figure: .; .; 1; 2; n]

It contains n trees (≠ 0 modulo q) trees. Each branch appears exactly q (=0 modulo q) times.

This type of forests are so simple that we don’t consider them as exceptional. They correspond to the fact that in the special case where p divides q, Count(p) is a (trivial) consequence of Count(q).

Observation 3.1.2 Suppose that F is a forest of (p, n)-labelled trees. Suppose that each branch appears 0 modulo q times. Then there exists a forest F′ of (p, n + p)- labelled trees such that

(i) The forest F′ contains the same number of trees as F.

(ii) Each branch in F′ appears 0 modulo q times.

(iii) The hight of the highest trees in F′ is at most 1 higher than the highest tree in F.

This immediately shows that if there exists an exceptional forest F for some n, this will also be the case for all larger n′ as long as n′ = n modulo p. Here are two easy negative results,

Theorem 3.1.3 Suppose that p divides n. Suppose that T_{1}, T_{2}, ..., T_{u} is a (p, n)- labelled forest where each branch appears 0 modulo q times. Then u = 0 modulo q.

Proof: According to the assumption p divides n so there exists a partitioning ρ_{global} of \{1, 2, ..., n\} into disjoint sets A_{1}, A_{2}, .., A\frac{n}{p} ⊆ \{1, 2, .., n\} each containing p elements. The partition ρ_{global} extends exactly one branch from each tree. Clearly, ρ_{global} allows us to define a partitioning of the trees T_{1}, T_{2}, ..., T_{u} into disjoint classes each containing exactly q trees. □ Using a similar idea we notice

Theorem 3.1.4 Suppose that T_{1}, T_{2}, ..., T_{u} is a forest of (p, n)-labelled trees. Suppose that the sum of the heights of all trees is smaller than \frac{n}{p}. If all branches appear 0 modulo q times, then u = 0 modulo q.

Proof: Select a branch β_{1} := α_{1} from the tree T_{1}. The branch must be compatible with at least one branch α_{2} ∈ T_{2}. Let β_{2} := β_{1} ∪ α_{2}. This branch (=condition) must be compatible to at least one branch α_{3} ∈ T_{3}. Eventually we construct a condition ρ which extends exactly one branch in each tree. □ One can try to elaborate on this type of argument. A (very naive) strategy is to try to choose short branches from each tree. It is not hard to see that this method breaks down when u > n.

In [24] I presented a graph theoretical argument. It used a generalisation of a well-known theorem from graph theory. This theorem states that if in a graph G all vertex have degree at least as large as \frac{1}{2}· | G_{vertex} |, then G contains a Hamiltonian circuit. This type of argument breaks down even when u is significantly smaller than n^{2}. Very early in this work it was clear that results relevant for Bounded Arithmetic all would require techniques which at least would be able to deal (when n tends to infinity) with the case where u > n^{k} for arbitrarily fixed k.

3.2 Breaking down trees

Let T be a (p, n)-labelled tree. Consider the following “move“.

[figure: .; .; .; +; +; +; +; +; T; T; T; T; T; T; T; 1; 2; v; v; 2; 1; 0; T; T; T; T; T; 0; 0; 0; 0; 0]

Suppose that F := {T_{1}, ..., T_{u}} is any forest. Repeated application of this allows us to break down the trees in F. Eventually all trees can be brought on the following normal form.

[figure: .; .; .; .; .; .; .; +; +; +; +]

Let us call such trees perfectly unbalanced (=PU). Clearly we have,

Lemma 3.2.1 Fix q ≥ 2, q ∈ ℕ. Let F := {T_{1}, ..., T_{u}} be any forest. There exists a forest F′ := {T′_{1}, T′_{2}, ...., T′_{u′}} in which each (type of) branch counted modulo q appears the same number of times as in F. Furthermore (also counted modulo q) the number u′ of trees in F′ equals the number u of trees in the forest F.

Notice that the PU-trees have a very simple representation. The PU-tree represented by,

(u_{1,1}, {u_{1,2}, ..., u_{1,p}})(u_{2,1}, {u_{2,2}, ..., u_{2,p}})...(u_{h−1,1}, {u_{h−1,2}, ..., u_{h−1,p}})(u_{h}),

where u_{i,j} ∈ I.

3.3 Bringing the forest on a special normal form

Now here are some nice operations on PU-trees.

Example 3.3.1 Consider the PU-trees

T := (4, {5, 6})(1, {2, 3})(7)

and

T′ := (1, {2, 3})(4, {5, 6})(7).

Notice that T and T′ contain the same branches of length 3. The branch β := {{1, 2, 3}, {4, 5, 6}} does not appear in T and T′. Except for the branch β the tree T contains the same branches of length ≤ 2 as the tree (4, {5, 6})(1). Also, except for the branch β the tree T′ contains the same branches of length ≤ 2 at the tree (1, {2, 3})(4). This can be expressed by the equation,

(4, {5, 6})(1, {2, 3})(7) = (1, {2, 3})(4, {5, 6})(7) − (4, {5, 6})(1) + (1, {2, 3})(4).

The equation expresses the fact that both sides of the identity contain 1 tree (counted with signs). And it expresses the fact that both sides contain exactly the same set of branches. Here is another operation. Example 3.3.2 We have the identity,

(2, {1, 3})(4) = (1, {2, 3})(4) − (1) + (2).

The identities from the examples can be expressed generally. Lemma 3.3.3 We have the following identities.

(1)  (w_{1}, W_{1})(w_{2}, W_{2})...(b, B)(a, A)...(w_{h}) =

(w_{1}, W_{1})(w_{2}, W_{2})...(a, A)(b, B)...(w_{h})−(w_{1}, W_{1})(w_{2}, W_{2})...(a)+(w_{1}, W_{1})(w_{2}, W_{2})...(b).

(2)  (w_{1}, W_{1})(w_{2}, W_{2})...(a_{2}, {a_{1}, a_{3}, .., a_{p}})...(w_{h}) =
(w_{1}, W_{1})...(a_{1}, {a_{2}, a_{3}, .., a_{p}})...(w_{h}) − (w_{1}, W_{1})...(a_{2}) + (w_{1}, W_{1})...(a_{1}).

It follows immediately from these principles that, Lemma 3.3.4 Let F′ := {T′_{1}, .., T′_{u′}} be a forest where all trees are PU-trees. Then there exist a forest F′′ := {T′′_{1}, ...T′′_{u′′}} where all trees are of the form

(u_{1,1}, {u_{1,2}, .., , u_{1,p}})...(u_{i,1}, {u_{i,2}, ..., u_{i,p}})...(u_{h})

where u_{1,1} < u_{2,1} < ... < u_{h−1,1}, and where u_{i,1} < u_{i,2} < ... < u_{i,p} for i = 1, 2, .., h − 1. Furthermore,

(i) The forests F′ and F′′ contain the same number of trees (modulo q). (ii) Each (type of) branch appears the same number (modulo q) of times in the forests F′ and F′′. We will come back to this normal form.

4 The first main result

Suppose that 𝕄 is a countable non-standard model of Th(ℕ) over a countable first order language L, which extends the language of Arithmetic. Suppose that p ≥ 2 and I := {1, 2, ..., n} ⊆ 𝕄 for some n ∈ 𝕄 \ ω. Assume that n is not divisible by p. As above, let 𝕄_{n}^{∗} := {m ∈ 𝕄 : t(n) > m, for some term t ∈ L}.

Theorem 4.0.5 (Main result) Suppose that all terms t ∈ L have sub-exponential growth rate. Then for each generic filter ρ_{G} (see definition 2.2.5, page 12),

(a) (𝕄)_{n}^{∗}, ρ̃_{G}) ⊧ ¬ Count(p).

(b) (𝕄_{n}^{∗}, ρ̃_{G}) satisfies induction for bounded L_{P} -formulas.

(c) (𝕄_{n}^{∗}, ρ̃_{G}) satisfies (all versions of) the pigeon-hole principle for bounded L_{P} - formulas.

Furthermore, there exists a sequence s_{k}(x), k = 1, 2, .... of (arithmetical) functions (which depend on the exact growth rate of the terms in L), such that (under the harmless extra assumption that the underlying language L might need an extension) the following are equivalent:

(i) (𝕄_{n}^{∗}, ρ̃_{G}) satisfies the Count(q) principle. (ii) Each forest T_{1}, T_{2}, .., T_{u} of (p, n)-labelled trees in which all trees have hight ≤ s_{k}(n) where each branch appears 0 modulo q times, has u = 0 modulo q. (iii) As (ii) but for (p, n)-labelled PU-trees.

Suppose that all terms in L have (at most) polynomial growth rate. Then s_{k}(x) := k gives the required characterisation.

In general s_{k}(x) can be chosen such that (s_{k}(n))^{l} < n for all l ∈ ℕ.

Our overall question is when systems of Bounded Arithmetic extended by an axiom scheme for the Count(q) principle, are able to prove Count(p). The first main result, links this to an understanding of the structure of exceptional forests. Furthermore, it shows that the asymptotic hight of the trees in the minimal exceptional forests is directly linked to the strength of the underlying axiom system.

I have already proved (a) and (b). I have also showed (iii) ⇒ (ii). To show (i) ⇒ (iii) assume that there is a forest F which violates (iii). Assume that the language contains a suitable relation symbol which allows us to define the forest by a Bounded formula (this is the harmless extra assumption). I claim that the Count(q) principle fails in (𝕄_{n}^{∗}, ρ̃_{G}). To see this, notice that there is a Bounded L_{P} -formula with parameters in 𝕄_{n}^{∗} which defines (by use of ρ̃_{G} a partitioning of the trees in the forest F. And this in such a way that each class contains exactly q trees. But by assumption F contains trees T_{1}, T_{2}, ..., T_{u} for some u with u ≠ 0 modulo q.

The difficult implication is (iii) ⇒ (i). As it turns out our proof of (c) also provides a first step in showing the implication (i) ⇒ (iii).

Lemma 4.0.6 Suppose that for some a ∈ 𝕄_{n}^{∗}, some bounded L_{𝕄}(P)-formula θ(·, ·) (with parameters in 𝕄_{n}^{∗}) defines a bijection from a to b. Let ρ_{0} ∈ ρ_{G} be given. Then there exists an 𝕄-definable sequence H_{i,j} and B_{i,j}, (i, j) ∈ a × b such that for some ρ ⊇ ρ_{0}, ρ ∈ P:

(i) for all (i, j) ∈ a × b, B_{i,j} is a tree-like basis on I \ Set(ρ), (ii) for all (i, j) ∈ a × b, || B_{i,j} ||≤ t for some fixed t < n^{\frac{1}{ω}}, (iii) for all (i, j) ∈ a × b, H_{i,j} ⊆ B_{i,j}, (iv) For each i_{0} ≤ a : B\overrightarrow{i_{0}} := ∪_{j≤b} H_{i_{0},j} is a basis for P,

(v) For each j_{0} ≤ b : B_{j_{0}}^{↓} := ∪_{i≤a} H_{i,j_{0}} is a basis for P.

Proof: Suppose that some Bounded L_{𝕄}(P)-formula θ(·, ·) defines a bijection from h : {1, 2, .., a} onto {1, 2, .., b} for a ≠ b. According to lemma 2.1.5 there exists d ∈ ω and t ∈ 𝕄_{n}^{∗} and a 𝕄-definable sequence of circuits θ_{i,j} (i, j) ∈ a × b, such that each (θ_{i,j})ρ̃_{G} holds exactly when (𝕄_{n}^{∗}, ρ̃_{G}) ⊧ θ(i, j). Now according to the key lemma (lemma 2.4.1) there exists ρ ⊇ ρ_{0}, ρ ∈ P, an 𝕄-definable sequence B_{i,j} (i, j) ∈ a × b where each B_{i,j} is a tree-like basis, and an 𝕄-definable sequence H_{i,j} ⊆ B_{i,j} (i, j) ∈ a × b such that for each (i, j) ∈ a × b:

θ_{i,j} ≡_{ρ} ∨_{h∈H_{i,j}} h.

We claim that the sequences B_{i,j} and H_{i,j} satisfy (i)-(v). By use of the fact that h is an injective function it is straightforward to show that the conditions in B\overrightarrow{i} must be pairwise incompatible. The fact that h is a (mono-valued) function ensures that conditions in B_{j}^{↓} are pairwise incompatible.

The only problem is to show that each B\overrightarrow{i} and each B_{j}^{↓} are complete for P(I \ Set(ρ)) (i.e. satisfies condition (2) in definition 2.5.3). We can simplify the notation by assuming that ρ = ∅. This simplification is possible by lemma 2.3.13 because the lemma allows us to replace I by I \ Set(ρ).

Suppose that ρ′ ∈ P is incompatible with all conditions in B\overrightarrow{i} for some fixed i ≤ a. Let ρ_{G} be a generic filter (without the simplification we assume ρ_{G} ∋ ρ). Now for each j ≤ b, ρ̃_{G} is incompatible with all conditions in H_{i,j}, so by use of lemma 2.3.14 θρ̃_{G} ; i,j = 0 for all j ≤ b. This is in contradiction with lemma 2.3.4 which ensures that ∅ (or ρ in the un-simplified case) forces h to take a value j ≤ b.

The completeness of the conditions in each B_{j}^{↓} follows by use of the assumption that h was forced onto. □

4.1 Using a combinatorial phenomenon

My aim here is to show that (i)-(v) in lemma 4.0.6 can be only satisfied when a = b. First we show

Lemma 4.1.1 Suppose that for some a, b ∈ 𝕄_{n}^{∗} there exist 𝕄 definable sequences B_{i,j} and H_{i,j} (i, j) ∈ a × b. If they satisfy condition (i)-(iii) in lemma 4.0.6, together with:

(iv)′ For each i_{0} ≤ a : B\overrightarrow{i_{0}} := ∪_{j≤b} H_{i_{0},j} is a tree-like basis.

(v)′ For each j_{0} ≤ b : B_{j_{0}}^{↓} := ∪_{i≤a} H_{i,j_{0}} is a tree-like basis.

Then a = b.

Proof: First, notice that we can assume that all conditions h, h′ ∈ H_{i,j} have | h |=| h′ |. Otherwise make suitable tree-like refinements. Second, notice that P (the set of forcing conditions), has the property that the number N(n, p, c) of conditions in a tree-like basis where all conditions h have | h |= c, only depends on n, p and c. Now ac = Σ_{i≤a} | B\overrightarrow{i} |= Σ_{i≤a,j≤b} | H_{i,j} |= Σ_{j≤b} | B_{j}^{↓} |= bc, so a = b. □

Suppose that we could replace “is a basis for P” with “is a tree-like basis” in lemma 4.0.6. Then according to lemma 4.1.1 this would ensure that the pigeon-hole principle could never be forced false. So if a basis B for P in general would be tree-like, we would be done. Unfortunately, the reality is more complex.

Example 4.1.2 The converse of lemma 2.7.4 does not hold in general. The following example (p = 2) is due to Krajicek (personal communication). The collection

B := {{{1, 2}}, {{1, 3}}, {{2, 3}}, {{1, i}, {2, j}, {3, k}}_{i,j,k≥4∧|{i,j,k}|=3}}

is a basis for P. However B is \underline{not} a tree-like basis (there is no i_{0} ∈ I such that all β ∈ B has i_{0} ∈ Set(ρ)).

Observation 4.1.3 Consider example 4.1.2. Let B′ := (B∪E_{1}({{2, 3}})\{{{2, 3}}}, so B →_{TR} B′. Notice that B′ is a tree-like basis. To see this, notice that B′ can be obtained from {∅} by the atomic tree-like refinements:

E_{1}(∅),

E_{2}({1, 4}), E_{2}({1, 5}), ...., E_{2}({1, n}),
E_{3}({{1, 4}, {2, 5}}), E_{3}({{1, 4}, {2, 6}), ..., E_{3}({{1, 4}, {2, n}}),
E_{3}({{1, 5}, {2, 4}}), E_{3}({{1, 5}, {2, 6}}), ...., E_{3}({{1, 5}, {2, n}}),
....
E_{3}({{1, n}, {2, 4}}), E_{3}({{1, n}, {2, 5}}), ...., E_{3}({{1, n}, {2, n − 1}}).

This observation is part of a general phenomenon. It turns out (and this was the combinatorial discovery which made my general approach possible), that any basis B for P has a tree-like refinement to a tree-like basis.

Lemma 4.1.4 Assume that B is a basis for P, and that u ∈ I. Then there exists a tree-like refinement B’ of B such that for all β′ ∈ B′ u ∈ Set(β′).

Proof: Let B′ := ∪_{β∈B} E_{u}(β). Notice that this is actually a tree-like refinement of B, and that B′ has the required properties. □

Definition 4.1.5 For U ⊆ I, we let C_{U} denote the tree-like basis {α : ∀A ∈ α ∃u ∈ U u ∈ A ∧ Set(α) ⊇ U}. We say B is a tree-like basis on U ⊆ I if for each α ∈ C_{U}, there exists β ∈ B with β ⊇ α. ♣

Lemma 4.1.6 Suppose that B is a basis for P, and U ⊆ I with | U |< n^{\frac{1}{ω}}. There is a tree-like refinement B’ of B, such that B’ is a tree-like basis on U.

Proof: Let U = {u_{1}, u_{2}, ..., u_{r}}. According to lemma 4.1.4 there exists a sequence

B = B_{0} →_{TR} B_{1} →_{TR} .... →_{TR} B_{r},

such that for all β ∈ B_{j} u_{j} ∈ Set(β). Let B′ := B_{r}. We have to show that for each α ∈ C_{U} there exists β ∈ B’, β ⊇ α. Now by use of a calculation similar to the one in the proof of lemma 2.3.12, B’ is a basis for P, so each α ∈ C_{U} is compatible with some β ∈ B’. Now as Set(β) ⊇ U actually β ⊇ α. □

Lemma 4.1.7 Suppose that || B ||≤ t for some t < n^{\frac{1}{ω}}. Also suppose that the conditions in B are pairwise incompatible. Then B is a basis for P iff each condition ρ ∈ P_{1} is compatible with some β ∈ B.

Proof: Repeated application of lemma 4.1.6. □

Lemma 4.1.8 If B is a basis for P, and || B ||≤ t for some t < n^{\frac{1}{ω}}, then there exists a tree-like basis B̃ such that || B̃ ||< pt(t + 1) and such that B →_{TR} B̃.

Proof: First we construct B̃’. Pick a set V ⊆ I such that V := Set(β) for some β ∈ B. According to lemma 4.1.6 there exists a tree-like refinement B_{1} of B such that B_{1} is tree-like on V. Now fix γ ∈ C_{V} and consider B_{1}^{γ} ⊆ P(I \V). It is not hard to show B_{1}^{γ} is a basis for P(I \ V). Now by use of lemma 4.1.7 we notice that we can prove the lemma by use of induction after t inside 𝕄. Let B_{1}(γ) := {β : β′ ∩ γ = β, β′ ∈ B_{1}^{γ}}. Notice that B_{1}(γ) is a tree-like refinement of γ. Finally let B̃ := ∪_{γ} B_{1}(γ). By induction after t we have || B̃ ||≤| Set(γ) | +p(t−1)t. Now | Set(γ) |≤ pt, from which the required inequality follows. □

We need a two-dimensional version of lemma 4.1.8.

Lemma 4.1.9 Suppose that there exists an 𝕄-definable “generic system”. That is a sequence H_{i,j}, (i, j) ∈ a × b such that:

(i) For each i ≤ a B\overrightarrow{i} := ∪_{j≤b} H_{i,j} is a basis for P.

(ii) For each j ≤ b B_{j}^{↓} := ∪_{i≤a} H_{i,j} is a basis for P.

(iii) max_{(i,j)∈a×b} || H_{i,j} ||≤ t for some t < n^{\frac{1}{ω}}.

Then there exists an 𝕄-definable “tree-like generic system”. That is a sequence H̃_{i,j} (i, j) ∈ a × b such that:

(i)′ For each i ≤ a B̃\overrightarrow{i} := ∪_{j≤b} H̃_{i,j} is a tree-like basis.

(ii)′ For each j ≤ b B̃_{j}^{↓} := ∪_{i≤a} H̃_{i,j} is a tree-like basis.

(iii)′ max_{(i,j)∈a×b} || H̃_{i,j} ||≤ p^{3}(t + 1)^{4}.

Proof: Fix i ≤ a. According to lemma 4.1.8 there exists a tree-like refinement B_{i}^{′→} of B\overrightarrow{i}, which is a tree-like basis. For each j ≤ b this procedure induces a tree-like refinement H′_{i,j} of H_{i,j}. This way we get an 𝕄-definable sequence H′_{i,j}, (i, j) ∈ a × b, so (i)’, (ii) and || H′_{i,j} ||≤ pt(t + 1).

Now fix j ≤ b. Again according to lemma 4.1.8 there exists a tree-like refinement B̃_{j}^{↓} of B_{j}^{′↓}, which is a tree-like basis. For each i ≤ a this procedure induces a tree-like refinement H̃_{i,j} of H′_{i,j}. Now notice that B̃\overrightarrow{i} remains tree-like basis, and thus the 𝕄-definable sequence H̃_{i,j}, (i, j) ∈ a × b satisfies (i)’, (ii)’. Clearly also (iii)’ holds because || H̃_{i,j} ||≤ p(pt(t + 1) + 1)(pt(t + 1)) ≤ p^{3}(t + 1)^{4}. □

This immediately shows (c) in theorem 4.0.5, in the case of the bijective pigeonhole principle. The other versions of the pigeon-hole principle are treated with minor changes.

4.2 Reducing the Count(q) versus Count(p) problem

The implication (i) ⇒ (iii) follows by the same type of argument.

Lemma 4.2.1 Suppose that θ(x_{1}, x_{2}, ..., x_{q}) is a bounded L(P)-formula with q free variables, and all its parameters in (𝕄_{n}^{∗}, ρ̃_{G}). If θ defines a partition of I_{a} := {1, 2, .., a}, a ∈ 𝕄_{n}^{∗}, then there exists an 𝕄_{n}^{∗}-definable map A → H_{A}, which to each q-subset A of I_{a} assigns a collection of conditions H_{A} ⊆ P such that for some t < n^{\frac{1}{ω}}, max_{A}(|| H_{A} ||) ≤ t. Furthermore, for each v ∈ I_{a}, B_{v} := ∪_{A⊆I_{a},|A|=q,v∈A} H_{A} is a basis for P.

Proof: Suppose that some bounded L(P)-formula θ(x_{1}, x_{2}.., x_{q}) defines a partition of {1, 2, ..., a} into disjoint q-subsets, and q does not divide a. According to 2.1.5 there exists d ∈ ω, t < n^{\frac{1}{ω}} and an 𝕄-definable sequence of circuits θ_{v_{1},...,v_{q}}, v_{1}, ..., v_{q} ∈ I_{a}, such that θρ̃_{G} ; i_{1},...,i_{q} exactly when (𝕄_{n}^{∗}, ρ̃_{G}) ⊧ θ(i_{1}, ..., i_{q}). Now according to the key lemma (lemma 2.4.1), there exists ρ ⊇ ρ_{0} (for any given ρ_{0}), and an 𝕄-definable sequence B_{v_{1},..,v_{q}} v_{1}, .., v_{q} ∈ I_{a} where each B_{v_{1},..,v_{q}} ⊆ P is a tree-like basis with || B_{v_{1},...,v_{q}} ||≤ t. Furthermore, there exists a 𝕄-definable sequence H_{v_{1},v_{2},...,v_{q}} ⊆ B_{v_{1},..,v_{q}} such that for each v_{1}, ..., v_{q} ∈ I_{a},

θ_{v_{1},v_{2}...,v_{q}} ≡_{ρ} ∨_{h∈H_{v_{1},v_{2},..,vq}} h.

Fix v ∈ I_{a} and consider B_{v} := ∪_{A⊆I_{a},v∈A} H_{A}. For α, β ∈ B_{v}, α ≠ β we claim α⊥β. To see this notice that otherwise there would exist ρ ⊇ α ∪ β, and ρ ∈ P would force both θ_{v_{1},...,v_{q}} and θ_{v′_{1},...,v′_{q}} true. Now v ∈ {v_{1}, ..., v_{q}}∩{v′_{1}, ..., v′_{q}} so this is only possible when {v_{1}, ..., v_{q}} = {v′_{1}, ..., v′_{q}}. Thus both α and β belong to H_{v_{1},..,v_{q}} ⊆ B_{v_{1},..,v_{q}}. As B_{v_{1},...,v_{q}} is a (tree-like) basis, α⊥β.

It remains to show that B_{v}, v ∈ I_{a} is complete for P({1, 2, .., n}\Set(ρ_{0})). Assume for the simplicity of the notation that ρ_{0} = ∅. According to lemma 2.3.13, this assumption is harmless. We have to show that no ρ ∈ P is incompatible with all the conditions h ∈ B_{v}. Now using lemma 2.3.14 each generic filter ρ_{G} contains some h ∈ B_{v_{1},...,v_{q}} for each v_{1}, v_{2}, .., v_{q} ∈ I_{a}. But this contradicts the assumption that ρ_{0} (in our case ∅) forces θ to define a total partition of I_{a} into disjoint q subsets. □

We conjecture that Count(q) is always forced true (when p and q are different primes. To show that Count(q) is never forced false, it suffices to show that if H_{A} is an 𝕄-definable assignment as in lemma 4.2.1, then q must divide a.

Example 4.2.2 Suppose that a << n. Consider I_{a} := {1, 2, ..., a}. Pick ρ_{1} ⊆ ρ_{2} ⊆ .... ⊆ ρ_{a} such that for each v ≤ a there is α_{v} ∈ B_{v} such that α_{v} ⊆ ρ_{v}. This is possible whenever ρ_{v} ∈ P, v = 1, 2, ..., a (which is the case when a << n). Notice that ρ_{a} induces an 𝕄-definable partition of I_{a} into disjoint q-subsets. As 𝕄 shares its first order properties with ℕ, this is only possible when q divides a.

As a major step in solving the Count(q) versus Count(p) problem, I show that we can strengthen the conclusion by replacing ‘each B_{v} is a basis for P’, with ‘each B_{v} to be a tree-like basis’.

Lemma 4.2.3 Let t < n^{\frac{1}{ω}} , a ∈ 𝕄. Let P be the set of forcing conditions defined as on page 11. Suppose that A → H_{A} is an 𝕄-definable map which assigns a collection of conditions H_{A} ⊆ P, to each q-subset A of I_{a} = {1, 2, .., a} such that

(i)  max_{A}(|| H_{A} ||) ≤ t
(ii)  B_{v} := ∪_{A⊆I_{a},|A|=q,v∈A} H_{A} is a basis for P (v = 1, 2, ..., a).

Then there exists a 𝕄-definable map A → H̃_{A} which assigns a tree-like refinement H̃_{A} of H_{A}, to each q-subset A of I_{a} := {1, 2, .., a} such that

(i)′  max_{A}(|| H_{A} ||) ≤ qpt(t + 1)
(ii)′  B̃_{v} := ∪_{A⊆I_{a},|A|=q,v∈A} H̃_{A} is a tree − like basis (v = 1, 2, ..., a).

As a first attempt of a proof consider the following argument. According to lemma 4.1.8 there exists a tree-like basis B_{1}^{(1)} which is a tree-like refinement of B_{1} := ∪_{1∈A} H_{A}. This refinement induces tree-like refinements H_{A} →_{TR} H_{A}^{(1)} for each A ⊆ I_{a}, | A |= q (when 1 ∉ A, H_{A}^{(1)} = H_{A}). For each v ∈ I_{a} let B_{v}^{(1)} := ∪_{v∈A} H_{A}^{(1)}.

Again by lemma 4.1.8 there exists a tree-like basis B_{2}^{(2)} which is a tree-like refinement of B_{2}^{(1)}. This refinement induce a tree-like refinement H_{A}^{(1)} →_{TR} H_{A}^{(2)} for each A ⊆ I_{a}, | A |= q (when 2 ∉ A, H_{A}^{(2)} = H_{A}^{(1)}). For each v ∈ I_{a} let B_{v}^{(2)} := ∪_{v∈A} H_{A}^{(2)}.

Eventually (again using lemma 4.1.8) there exists a tree-like basis B_{2}^{(a)} which is a tree-like refinement of B_{a}^{(a−1)}. This refinement induces a tree-like refinement H_{A}^{(a−1)} →_{TR} H_{A}^{(a)} for each A ⊆ I_{a}, | A |= q (when a ∉ A, H_{A}^{(a)} = H_{A}^{(a−1)}). For each v ∈ I_{a} let B_{v}^{(a)} := ∪_{a∈A} H_{A}^{(a)}.

Let H̃_{A} := H_{A}^{(a)}. We claim that each B̃_{v} := ∪_{v∈A} H̃(a)_{A} is a tree-like basis. To see this notice B̃_{v} = B_{v}^{(a)}. By construction each B_{v}^{(v)} is a tree-like basis. Now

B_{v}^{(v)} →_{TR} B_{v}^{(v+1)} →_{TR} ... →_{TR} B_{v}^{(a)}

so B_{v}^{(a)} is a tree-like basis.

This argument has to be adjusted. We have to ensure that all conditions h are small throughout the construction. To this end we need some more lemmas.

Definition 4.2.4 For H, H′ ⊆ P let H × H′ := {h ∪ h′ : h ∈ H, h′ ∈ H′}. ♣

Lemma 4.2.5 Let A → H_{A} and A → H′_{A} be two 𝕄-definable maps. Suppose that

(i) for each condition in H_{A} is compatible with some condition in H′_{A} and vice versa.

(ii) for A, B with A ≠ B and A ∩ B ≠ ∅, all conditions in H_{A} are incompatible with all conditions in H′_{A} and vice versa.

Suppose that both the maps A → H_{A} and A → H′_{A} satisfy conditions (i) and (ii) in lemma 4.2.3. Then the 𝕄-definable map A → H_{A} × H′_{A} ensures that (i) and (ii) remain valid with t replaced by 2t.

Proof: Direct verification. □

Lemma 4.2.6 Suppose that B_{0} is a basis for P. If both B_{1} and B_{2} are tree-like refinements of B_{0}, then B_{1} × B_{2} is a tree-like refinement of both B_{1} and B_{2}.

Proof: Proved by induction on the number of atomic tree-like refinements needed to get from B_{0} to B_{1} added to the number of atomic tree-like refinements needed to get from B_{0} to B_{2}. □

The following proof simplifies an argument in an earlier and preliminary version of this paper. Proof of lemma 4.2.3: For each v ∈ I_{a} let H_{A}^{v} be the tree-like refinement of H_{A} induced when B_{v} := ∪_{A∋v} H_{A} is refined to a tree-like basis B_{v}^{v}. Consider the 𝕄-definable map

A → H̃_{A} := H_{A}^{a_{1}} × H_{A}^{a_{2}} × .... × H_{A}^{a_{q}},

where A = {a_{1}, a_{2}, ..., a_{q}}. Now B_{v}^{v} := ∪_{A∈v} H_{A}^{v} is a tree-like basis. Furthermore, H̃ ≡ H_{A}^{v} × (H_{A}^{a_{2}} × ... × H_{A}^{a_{q}}) where A = {v, a_{2}, a_{3}, ..., a_{q}}. To see this notice that according to lemma 4.2.6 for fixed a_{2}, .., a_{q}, (∪_{A∋v} H_{A}^{v}) × (B^{a_{2}} × B^{a_{3}} × ... × B^{a_{q}}) is a tree-like refinement of ∪_{A∋v} H_{A}^{v}. This tree-like refinement induces a tree-like refinement H_{A}^{v} →_{TR} H_{A}^{v} × (H_{A}^{a_{2}} × ... × H_{A}^{a_{q}}).

Thus for each v ∈ I_{a}, B̃_{v} := ∪_{A∋v} H̃_{A}^{v} is a tree-like refinement of ∪_{A∋v} H_{A}^{v}, which was constructed as a tree-like basis. Thus each B̃_{v} is a tree-like basis. □

Combining these results it is not hard to show that (i) ⇒ (iii).

5 The positive part

In this section I develop a method of constructing exceptional forests. And the existence of these forests immediately gives us the positive part of the classification.

Definition 5.0.7 By [i_{1}, ..., i_{l}]_{p} we denote the (p, n)-labelled trees which contain all the branches α of the form α = {A_{1}, ..., A_{r}} where A_{j} ⊆ I, | A_{j} |= p, j = 1, 2, .., r and where A_{j} ∩ A_{k} = ∅ for j ≠ k. Besides that we require that,

(a) A_{j} ∩ {i_{1}, i_{2}, ..., i_{l}} ≠ ∅ for j = 1, 2, ..., r,

(b) ∀k ≤ l ∃j ≤ r i_{k} ∈ A_{j}. ♣.

Definition 5.0.8 Let p, q ≥ 2. The forest F_{p,r,n}^{Hom} (Hom for homogeneous) consists of all the trees [i_{1}, i_{2}, ..., i_{r}]_{p} where i_{1} < i_{2} < ... < i_{r} ≤ n. ♣

Definition 5.0.9 By A_{p,l,r} we denote the number of ways it is possible to select r elements from the sets {1, 2, ..., p}, {p+1, p+2, ..., 2p}, ..., {pl−p+1, pl−p+2, ..., pl}, such that at least one element is chosen from each of the p elements sets. ♣

Lemma 5.0.10 The forest F_{p,r,n}^{Hom} of (p, n)-labelled trees, contains \binom{n}{r} trees. Each branch α with | α |= l appears in A_{p,l,r} trees.

Proof: Clearly | F_{p,r,n}^{Hom} |= \binom{n}{r}. Suppose that α = {i_{1}^{1}, i_{2}^{1}, ..., i_{p}^{1}}, {i_{1}^{2}, .....i_{p}^{2}}, ..., {i_{1}^{l}, i_{2}^{l}, ..., i_{p}^{l}}} where i_{2}^{1} < i_{1}^{2} < .... < i_{1}^{l} and where i_{1}^{j} < i_{2}^{j} < ... < i_{p}^{j} for j = 1, 2, ..., l. Now there is a one to one correspondence between the r element subset of ∪α, which contains at least one element from each member in α, and the trees in F_{p,r,n}^{Hom} which contain α. □

Lemma 5.0.11 Let q be a fixed prime number. Let s be any fixed number. Then for each v ≥ 1, Count(q^{v} · s) ⊢ Count(q^{v+1} · s).

Proof: Without loss of generality we can assume that q is not a prime factor in s. Consider the forest F which contains q^{v−1} copies of the forest F_{p,r,n}^{Hom} where p := q^{v+1}·s, r := q^{v}. The critical cases (the only non-trivial cases) are when n = q^{v+1}n′ + r · q^{v}, r = 1, 2, ..., q −1. The forest contains k ·q^{v−1} modulo q^{v} trees (for k ∈ {1, 2, .., p−1}). The most critical case is branches of length 1. They appears q^{v−1} ·\binom{q^{v+1}·s}{q^{v}} = 0 modulo q^{v} times. Longer branches also appears 0 modulo q^{v} times. □ This gives the positive part of the classification:

Corollary 5.0.12 If p, q ≥ and all prime factors in p appears in q then, Count(q) ⊢ Count(p).

5.1 Some examples

Before I show the negative part of the classification I will examine the structure of the exceptional forests when these are on the PU-form. Each (irreducible) exceptional forest F of PU-trees I have found can be derived from the forests given in definition 5.0.8.

Example 5.1.1 Let q = 2, p = 4 and n = 4n′ + 2, n′ ≥ 2. Consider the forest F_{2,4,n} of (4, n)-labelled PU-trees which contains: All PU-trees of the form (i_{1}, W_{1})(i_{2}) where i_{1} < i_{2} ≤ n and where W_{1} ⊆ {1, 2, ..., n} has 3 elements. The PU-trees (1), (3), (5), ....., (4n′ + 1).

Each branch of length 2 appears 16 times. A branch {j_{1}, j_{2}, j_{3}, j_{4}} of length 1, appears in mod(j_{1}, 2) + mod(j_{2}, 2) + mod(j_{3}, 2) + mod(j_{4}, 2) trees of hight 1. And the branch appears in \binom{n−2}{3} − 4n + 6 + j_{1} + j_{2} + j_{3} + j_{4} trees of hight 2.

The forests F_{2,4,n} contain \binom{n}{2}\binom{n−2}{3}+ \frac{n}{2} trees. This is always an odd number. When n′ = 2 the forests contain 2525 trees.

Example 5.1.2 Let n = 4n′ + 2. For each n′ ≥ 2 there exists a 2-exceptional forest of (4, n)-labelled trees. The forest contains all trees: (j_{1}, {j_{2}, j_{3}, j_{4}})(j_{5}) where j_{1} < j_{2} < j_{3} < j_{4} and where j_{1} < j_{5} < j_{2} or j_{3} < j_{5} < j_{4}. (1), (3), ...., (4n′ + 1).

Each branch of length 2 appears an even number of times. The branch {{i_{1}, i_{2}, i_{3}, i_{4}}, {i_{5}, i_{6}, i_{7}, i_{8}}} appears a number of times depending on the number of vertical lines in the following kind of figure:

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  ^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  4  4  2  0

The branch {{i_{1}, i_{2}, i_{3}, i_{4}}} appears in all trees (of hight 2) except (i_{2} − i_{1}) + (i_{4} − i_{3}) which counted modulo 2 is i_{1} + i_{2} + i_{3} + i_{4}. This is the same number (modulo 2) it appears in trees of hight 1.

When n′ = 2 this is a forest of 635 trees. I conjecture that for q = 2 this is the smallest exceptional forest of PU-trees.

The next example is derived from lemma 5.0.10 Example 5.1.3 Let q = 3, p = 9 and n = 9n′ + 3, n′ ≥ 3. Consider the forests F_{3,9,n} which contain the (9, n)-labelled PU-trees:

(1) The trees of the form (i_{1}, W_{1})(i_{2}, W_{2})(i_{3}) where i_{1} < i_{2} < i_{3} ≤ n and where W_{1}, W_{2} are two disjoint 8-element subsets of {1, 2, ..., n} \ {i_{1}, i_{2}, i_{3}}.

(2) Two copies of each tree of the form (i_{1}, W_{1})(i_{2}) where i_{2} = 1 modulo 3 and i_{1} < i_{2} ≤ n.

(3) Each tree of the form (i_{1}, W_{1})(i_{2}) where i_{2} = 2 modulo 3 and i_{1} < i_{2}.

(4) Each tree of the form (i_{1}) where \binom{n−i_{1}}{2} = 1 modulo 3.

(5) Two copies of each tree of the form (i_{1}) where \binom{n−i_{1}}{2} = 2 modulo 3. A careful checking shows that each branch appears 0 modulo 3 times. The forests contains 1 modulo 3 trees. In the smallest case (i.e. when n’=3) the forest contains

\binom{30}{3}\binom{27}{8}\binom{19}{8} + Σ_{i}Σj > i, j =_{3} 1 2 + Σ_{i}Σ_{j>i,j=_{3}2} 1 + Σ_{i} mod(\binom{n − i}{2}, 3)

trees. This is a forest of 681259986982585 trees. It is not the smallest exceptional forest for q = 3.

There are smaller exceptional forests

Example 5.1.4 Consider the forest F which contains: t copies of each tree (i_{1}, {i_{2}, i_{3}, ..., i_{9}})(j_{1}, {j_{2}, ...j_{9}})(k) where i_{1} < i_{2} < ... < i_{9}, i_{1} < j_{1} , j_{1} < j_{2} < ... < j_{9} and if i_{r} < k < i_{r+1} and j_{s} < k < j_{s+1} then r + s = t modulo 3. t copies of each tree (i_{1}, {i_{2}, ...i_{9}})(j) where i_{1} < i_{2} < ... < i_{9} and if i_{r} < j < i_{r+1} then t = r modulo 3. t copies of each tree (i) where t = i modulo 3.

I claim (without proof) that each branch appears 0 modulo 3 times. However for each n = 9n′ +3 n′ ≥ 3 | F |≠ 0 modulo 3. More specifically | F |= \frac{1}{3} ·\binom{n}{9}\binom{n−9}{9}·(n− 18). In the case when n′ = 3 F only contains 16821302548060 PU-trees. I conjecture that this is the smallest exceptional forest for q = 3.

From the examples we notice a general feature. The trees of maximal hight h are very homogeneously organised and easy to describe. The Trees of hight h − 1 are still quite regular but each such tree’s frequency 0 ≤ v < q is slightly more complicated to describe. The collection of trees of hight 1 have the frequencies which are the most complicated to calculate.

In the next section I show that all exceptional forests asymptotically (when n → ∞ and the hight of all trees is bound by a constant) can be assumed to have the same feature.

6 The negative part

The negative part of the classification states that Count(q) does not imply Count(p) when p contains a prime factor which is not in q. We consider the case where all terms in the underlying language L have (at most) polynomial growth-rate. By the first main result theorem 4.0.5 it suffice to show that for each h ∈ ℕ asymptotically (when n → ∞, and h(F) ≤ h) there are no q-exceptional forests T_{1}, T_{2}, ..., T_{u} of (p, n)-labelled trees.

This is shown by considering forests T′_{1}, T′_{2}, ..., T′_{u} of specially labelled trees corresponding to the Count(q) versus PHP_{q^{k}}

Definition 6.0.5 A (D, R)-labelled tree T is a decision tree for constructing a partial bijection f : D → R. We always assume that D ∩ R = ∅. Each vertex v ∈ T corresponds to a certain stage f_{v} in the construction of f. At the root v_{root} we have f_{v_{root}} = ∅.

At each vertex v (except the top node) there is a assigned a “question”, i.e. an element u ∈ D ∪ R \ (dom(f_{v}) ∪ ran(f_{v})). Each “answer” corresponds to the sons of v. If u ∈ D, there is an edge to a son, for each r ∈ R \ ran(f_{v}). Each of these edges lead to a vertex v′ in which f_{v′} ⊇ f_{v}, and f_{v′}(u) = r (and | f_{v′} |=| f_{v} | +1). Similarly if u ∈ R. In this case there is an edge for each d ∈ D \ dom(f_{v}). Each of these edges lead to a vertex v′ in which f_{v′} ⊇ f_{v}, and f_{v′}(d) = u (and | f_{v′} |=| f_{v} | +1).

The type of a branch through T is identified with the partial map f_{v} constructed at the leafs v. ♣

This labelling is more manageable than the (p, n)-labelling.

Definition 6.0.6 The hight h(F) of the forest F denotes the maximal hight of a tree T ∈ F. ♣

Definition 6.0.7 A (D, R)-labelled tree T is a PU-labelled tree (= on PU-form) if at each level all but possible one vertex is a top node. □

Observation 6.0.8 A (D, R)-labelled tree T on PU-form can be written of the form:

(u_{1}^{1}, u_{2}^{1})(u_{1}^{2}, u_{2}^{2})...(u_{1}^{l−1}, u_{2}^{l−1})(u^{l})

If u_{1}^{i} ∈ D then u_{2}^{i} ∈ R and if u_{1}^{i} ∈ R then u_{2}^{i} ∈ D ( i = 1, 2, ..., l − 1). The element u^{l} belongs to either D or R. In the first case we say T is of D-type, while we say that T is on R-type.

As an example consider the following (obvious) proposition:

Proposition 6.0.9 Suppose that F solely consists of (D, R)-labelled trees of D-type. Suppose also (as usual) that | D |≤| R |. Suppose that each branch α in F appears 0 modulo q times. Then the forest F contains 0 modulo q trees.

Proof: Let ρ : D → R be an (total) injection. Each tree T ∈ F contains exactly one branch α with α ⊆ ρ. Thus ρ induces a partitioning of the trees in F into disjoint classes which each contains 0 modulo q trees. □ If the forest F contains trees of both D-type and R-type the situation becomes more complicated.

Example 6.0.10 Let q ∈ ℕ. Consider the following forests F of (D, R)-labelled trees. For each d ∈ D it contain (q − 1) copies of (d), and for each r ∈ R it contain the tree (r).

This forests F contains | R | − | D | modulo q trees. Each type of branch appears 0 modulo q times. So trivially if | R |≠| D | modulo q, there exists a forest F in which all branches appears 0 modulo q times, but | F |≠ 0 modulo q.

This type of forest is trivial. It corresponds to the obvious fact that Count(q) implies PHP_{p} when p ≠ 0 modulo q. This type of forests are so simple that we will not consider them as exceptional.

Definition 6.0.11 A forest F of (D, R)-labelled trees is called (q, l)-exceptional if (i) Each type branch appears 0 modulo q times. (ii) | R |=| D | +q^{l}. (iii) The number of trees in F′ is not divisible by q. ♣

Example 6.0.12 Suppose | R | − | D |= 4p′ + 2 for some p′ ∈ ℕ. Assume that | R | is an odd number. Let F denote the (D, R)-labelled forest which contains the following PU-trees:

(1) All trees of the form (d, r_{1})(r_{2}) where d ∈ D and r_{1} > r_{2} when | r_{1} − r_{2} | is odd, and r_{1} < r_{2} when | r_{1} − r_{2} | is even.

(2) All trees of the form (d_{1}, r)(d_{2}) where r ∈ R and d_{1} < d_{2}. Each branch appears an even number in F. However, the forest F contains

| D | \binom{| R |}{2}+ | R | \binom{| D |}{2}

trees which is always an odd number. The smallest example of this form is when | D |= 5 and | R |= 7. In this case F contains 175 trees. I claim without proof that this is the smallest (2, 1)-exceptional forest. The forest resemble the fact that Count(2) implies PHP_{2}.

There are (q, l)-exceptional forests for each q, l ∈ ℕ, q ≠ 1 (we do not need this fact). This follows by combining:

(1) We have a version of theorem 4.0.5 for the Count(q) versus PHP_{q^{l}} problem.

(2) Trivially PHP_{1} follows from Count(q)

(3) By [24] PHP_{q^{l}} follows from PHP_{1}.

It is interesting to notice that this proof is non-constructive. It only shows that the exceptional forests exists. It does not shows how to constructs them. It turns out that they can be constructed along the same lines as the constructions in section 4.

6.1 Projecting forests

Let T be a (p, n)-labelled tree. Suppose n = pn′ + q^{l} for q ∈ ℕ \ {1} and l ∈ ℕ. Then we can transform it to a (D, R)-labelled tree by the following procedure.

First divide I := {1, 2, ..., n} into p disjoint sets D_{1}, D_{2}, ..., D_{p−1} and R such that | D_{1} |=| D_{2} |= .... =| D_{p−1} |= n′ and | R |= n′+q^{l}. Let D := D_{1}. For j = 1, 2, ..., p−1 chose bijections y_{j} : D_{j} → D. Let us call a subset {i_{1}, i_{2}, .., i_{p}} ⊆ I for regular if i_{p} ∈ R, i_{j} ∈ D_{j}, j = 1, 2, .., p − 1 and y_{1}(i_{1}) = y_{2}(i_{2}) = ... = y_{p−1}(i_{p−1}). A branch {A_{1}, .., A_{r}} is regular if each A_{j}, j = 1, 2, .., r is regular. By use of this definition it is straight forward to show that,

Lemma 6.1.1 Let T be a (p, n)-labelled tree. Suppose that n = pn′ + q^{l} and let D_{1}, .., D_{p−1} and R be given as above. Then the set of regular branches in T form a new tree T′ which is (D, R)-labelled. Furthermore h(T′) ≤ h(T).

If T is on PU-form, then T′ will also be on PU-form.

Instead of projecting a single tree we can project forests. The important point is that the projection of an q-exceptional forest of (p, n)-labelled trees produces an (q, l)- exceptional forest of (D, R)-labelled trees.

Lemma 6.1.2 Let F := {T_{1}, T_{2}, .., T_{u}} be a forest of (p, n)-labelled trees. Suppose F is an q-exceptional forest. Or more specifically that p does not divide q and each branch in F appears 0 modulo q times, but u ≠ 0 modulo q. Suppose also that n = pn′ + q^{l}. The projection of the trees T_{1}, ..., T_{u} gives an (q, l)-exceptional (D, R)-labelled forest (with | D |= n′ and | R |= n′ + q^{l}). Furthermore h(F′) ≤ h(F).

Proof: This is left to the reader to verify. □ The condition that n = pn′ + q^{l} might not in general be satisfied for a given n. However, usually we do not lose any generality by assuming n is of this form. To see this consider the following procedure:

Definition 6.1.3 Suppose that ρ is a partial partition of I := {1, 2, ..., n} into disjoint p-element subsets. Consider a (p, n)-labelled tree T. For each branch (=condition) α through T consider the following procedure. If α is incompatible with ρ remove it. Otherwise replace it by β := α \ ρ.

Suppose that ρ′ is a partial bijection from D to R. Consider a (D, R)-labelled tree T. For each branch (=condition) α′ through T consider the following procedure. If α′ is incompatible with ρ′ remove it. Otherwise replace it by β′ := α′ \ ρ′. ♣

Lemma 6.1.4 (Stability) Suppose that T is a (p, n)-labelled tree. Let ρ be a partial partition of I = {1, 2, ..., n} into disjoint p-element subsets. Suppose that p · (h(T)+ | ρ |) < n. Then the collection of all branches β which are produced from some α ∈ T (as described in definition 6.1.3) can be organised into a (p, n′)-labelled tree T^{ρ} where n′ = n − p | ρ |. Suppose that T′ is a (D, R)-labelled tree. Let ρ′ be a partial bijection from D to R. Suppose that h(T)+ | ρ′ |< n. Then the collection of all branches β′ which are produced from some α′ ∈ T (as described in the second part of definition 6.1.3) can be organised into a (D′, R′)-labelled tree T^{′ρ′} where D′ := D \ dom(ρ′) and R′ := R \ ran(ρ′). If T (T′) is a PU-tree then T^{ρ} (T^{′ρ′}) is a PU-tree.

Proof: It suffice to show the lemma when | ρ |= 1. Suppose that ρ := {{i_{1}, i_{2}, ..., i_{p}}}. Let V be the set of vertex in T which have assigned v ∈ {i_{1}, .., i_{p}}. Let E_{⊥} denote the set of edges in T which has assigned p-subset A ⊆ I with non-trivial intersection with {i_{1}, .., i_{p}} (i.e. ≠ ∅ and ≠ A). Let E_{||} be the set of edges which have assigned A = {i_{1}, i_{2}, .., i_{p}}.

For each vertex (=question) in V all edges (but exactly one) edge (=answer) belongs to E_{⊥}. Remove all these edges (and the sub-tree above this). Then contract the edge in E_{||}. Finally, after having exhausted this procedure, remove all edges in E_{⊥} (and the sub-tree above this). The condition that p(h(T)+ | ρ |) < n is exactly what in general is required to ensure that T^{ρ} actually becomes a properly labelled tree. The second part of the lemma is showed similarly. The last claim is also straight forward to check. □ The lemma is one of many stability results which are important for the overall argument. In short it shows that trees (PU-trees) remains on this form when they are “hit” by a restriction ρ.

The main lemma gives us an understanding of the asymptotic behaviour of exceptional (D, R)-labelled trees.

Lemma 6.1.5 (Main lemma) Let q be a prime number. Let k, l ∈ ℕ. There exists d_{0} ∈ ℕ such that for any (q^{k}, l)-exceptional forest of (D, R)-labelled trees, where d_{0} ≤| D |≤| R |, we have h(F′) ≥ q^{l−k}.

Corollary 6.1.6 Let p be any prime number which does not appear in q = q_{1}^{α_{1}}q_{2}^{α_{2}}...q_{r}^{α_{r}}. Fix h ∈ ℕ. There exists n_{0} such that for each n ≥ n_{0} each forest F := {T_{1}, T_{2}, ..., T_{u}} of (p, n)-labelled trees never simultaneously satisfies:

(1) All branches appears 0 modulo q times.

(2) h(F) ≤ h.

(3) u ≠ 0 modulo q.

Proof: Suppose that (1) and (3) hold. Choose j ∈ {1, 2, .., r} such that u ≠ 0 modulo q_{j}^{α_{j}}. According to the assumptions F is an q_{j}^{α_{j}}-exceptional forest of (p, n)-labelled trees. By lemma 6.1.4 we can assume that n = pn′ + q_{j}^{l} for any l given in advance (of course l has to be reasonable i.e. q^{l} << n etc). Choose l such that q_{j}^{l−α_{j}} > h. By lemma 6.1.2 the projected forest F′ is (q_{j}^{α_{j}}, l)-exceptional and h(F′) ≤ h(F). According to lemma 6.1.5 h(F′) ≥ q^{l−α_{j}} > h. Now h(F′) ≤ h(F) so this contradicts (2). □

6.2 Creating order among trees of maximal hight h

Lemma 6.2.1 Fix q ∈ ℕ \ {1}, and fix l, h ∈ ℕ. For each d_{0} ∈ ℕ with d_{0} ≥ h, there exists (a very large) d_{1} ∈ ℕ such that for each forest F = {T_{1}, T_{2}, ..., T_{u}} of (D, R)-labelled trees with | R |=| D | +q^{l} and | D |≥ d_{1} the following is true: There exists a partial bijection ρ : D → R, such that the forest F^{ρ} := {T_{1}^{ρ}, T_{2}^{ρ}, .., T_{u}^{ρ}} of (D′, R′)-labelled trees, with D′ = D \ dom(ρ) and R′ = R \ ran(ρ), satisfies:

(1) For each h − 1 element subset {d_{1}, d_{2}, .., d_{h−1}} ⊆ D′ with d_{1} < d_{2} < ... < d_{h−1} and for each permutation π : {1, 2, .., h} → {1, 2, .., h} the number (modulo q) of trees (in the forest F^{ρ}) of the form

(d_{1}, r_{π(1)})(d_{2}, r_{π(2)})....(d_{h−1}, r_{π(h−1)})(r_{π(h)})

does \underline{not} depend on the elements r_{1} < r_{2} < ... < r_{h} in R′.

(2) For each (h − 1)-element subset {d_{1}, d_{2}, ..., d_{h−1}} ⊆ D′ (where d_{1} < d_{2} < ... < d_{h−1}), for each element d_{h} ∈ D′ \ {d_{1}, d_{2}, .., d_{h−1}}, and for each permutation π : {1, 2, ..., h − 1} → {1, 2, ..., h − 1} the number (modulo q) of trees of the form

(d_{1}, r_{π(1)})(d_{2}, r_{π(2)})....(d_{h−1}, r_{π(h−1)})(d_{h})

does \underline{not} depend on the elements r_{1} < r_{2} < ... < r_{h−1} in R′.

(3) | D′ |≥ d_{0}.

Proof: Let D_{1} ⊆ D be a subset with | D_{1} |≥ d′_{0} for some number much larger than d_{0}. The size of d′_{0} can be expressed in terms of the estimates arising from the second part of the argument (where we ensure the validity of property (3)). For each h − 1 element subset {d_{1}, d_{2}, ..., d_{h−1}} ⊆ D_{1} with d_{1} < d_{2} < ... < d_{h−1} and for each permutation π : {1, 2, .., h} → {1, 2, ..., h} we define a map F (d_{1}, d_{2}, ..., d_{h−1}; π) which maps h-element subsets of R to the set {0, 1, 2, .., q − 1}. It is defined by letting F (d_{1}, d_{2}, ..., d_{h−1}; π)({r_{1}, r_{2}, ..., r_{h}}) (where r_{1} < r_{2} < ... < r_{h}) denote the number (modulo q) of the PU-trees

(∗)  (d_{1}, r_{π(1)})(d_{2}, r_{π(2)})....(d_{h−1}, r_{π(h−1)})(r_{π(h)})

These maps induce as a map F̃ which to each h element subset {r_{1}, r_{2}, ..., r_{h}} ⊆ R takes one of q^{\binom{|d_{0}|}{h−1}h!}-values. This value expresses uniquely for each h−1 element subset of D_{1} and each permutation π : {1, 2, .., h} → {1, 2, ..., h}, the number (modulo q) of PU-trees of the form (∗).

Now by Ramseys theorem ^{7} if d_{1} is sufficiently large (not depending on F ) there must be a set R_{1} ⊆ R which is homogeneous for the “collaring” F̃. By possible making R_{1} slightly smaller we can ensure that | D \ D_{1} |=| R \ R_{1} |. Choose a partial bijection ρ : D → R such that dom(ρ) = D \ D_{1} and ran(ρ) = R \ R_{1}. This ensure that the new restricted forest satisfies property (2).

This procedure is now repeated (with d′_{0} replaced by d_{0}) such that property (3) are satisfied. Notice that application of a new ρ′ does not destroy property (2). □

Definition 6.2.2 Two tuples < r_{1}, r_{2}, .., r_{h} > and < r′_{1}, r′_{2}, ..., r′_{h} > have the same order structure if for the same permutation π we have that r_{π(1)} < r_{π(2)} < ... < r_{π(h)} and r′_{π(1)} < r′_{π(2)} < ... < r′_{π(h)}. ♣

Lemma 6.2.3 (Stability) Suppose that F := {T_{1}, T_{2}, ..., T_{u}} is a forest of (D, R)- labelled PU-trees. Suppose all trees of maximal hight h satisfies (1) and (2) in lemma 6.2.1. For any partial bijection ρ : D → R, with h+ | ρ |<| D |, the forest F′ := {T_{1}^{ρ}, T_{2}^{ρ}, ..., T_{u}^{ρ}} of (D′, R′)-labelled trees (D′ := D \ dom(ρ), R′ := R \ ran(ρ)) also satisfies (1) and (2).

Proof: By the second part of lemma 6.1.4, we only have to check that (1) and (2) in lemma 6.2.1 will be satisfied. To show (1) we have to prove that the PU-trees

(d_{1}, r_{1})(d_{2}, r_{2})...(d_{h−1}, r_{h−1})(r_{h})

7The application of Ramseys theorem seems to play a similar role in [6].

and

(d′_{1}, r′_{1})(d′_{2}, r′_{2})...(d′_{h−1}, r′_{h−1})(r′_{h})

appears the same number of times (modulo q) when d_{1} < d_{2} < ... < d_{h−1}, when d′_{1} < d′_{2} < ... < d′_{h−1}, and when the order type of < r_{1}, r_{2}, .., r_{h} > and < r′_{1}, r′_{2}, ..., r′_{h} > are the same. This follows from the fact that none of the representations can have been altered by ρ. □

6.3 Creating order among trees of hight h′ < h

Let F be a forest of (D, R)-labelled trees of PU-form. Suppose that all trees satisfies condition (1) and (2) in lemma 6.2.1. Wright F as the union F_{1} ∪ F_{2} ∪ ... ∪ F_{h}, where the sub-forest F_{h′} contains all trees of hight h′. By the same argument as in lemma 6.2.1 there exists (provided D and R are sufficiently large compared to h(F)) a restriction ρ (i.e. a partial bijection) such that for each h′ ∈ {1, 2, .., h} all trees in F_{h′}^{ρ} satisfies (1) and (2) in lemma 6.2.1 with h replaced by h′.

Consider the trees in F^{ρ} of some hight h′ < h. Clearly there is a flux of trees from each F_{h′′} with h′ < h′′ ≤ h.

Definition 6.3.1 (Strong normal form) A forest F := {T_{1}, T_{2}, ..., T_{u}} is on strong normal form if for each h′ ≤ h:

(1) For each d_{1} < d_{2} < ... < d_{h′−1} and for each permutation π : {1, 2, ..., h} → {1, 2, .., h} the number (modulo q) of trees of the form

(d_{1}, r_{π(1)})(d_{2}, r_{π(2)})...(d_{h−1}, r_{π(h−1)})(r_{π(h)})

only depends on residue classes modulo q^{h−h′} of the elements r_{1} < r_{2} < ... < r_{h}.

(2) For each d_{1} < d_{2} < ... < d_{h′−1}, for each d_{h′} ∈ D \ {d_{1}, d_{2}, .., d_{h′−1}} and for each permutation π : {1, 2, ..., h′ − 1} → {1, 2, .., h′ − 1} the number (modulo q) of trees of the form

(d_{1}, r_{π(1)})(d_{2}, r_{π(2)})...(d_{h′−1}, r_{π(h′−1)})(d_{h′})

only depends on residue classes modulo q^{h−h′} of the elements r_{1} < r_{2} < ... < r_{h−1}. ♣

Lemma 6.3.2 (Stability) If F is on strong normal form, then F^{ρ} is on strong normal from (provided that h(F)+ | ρ |<| D |≤| R |).

Proof: There are 3 ways the representation of a PU-tree T

(d_{1}, r_{1})(d_{2}, r_{2})....(d_{l−1}, r_{l−1})(d_{l}, h_{l})...(d_{h−1}, r_{h−1})(r_{h})

might change. In all cases suppose that the lowest place where it get ‘hit’ is on level l.

(1) < d_{l}, r_{l} >∈ ρ. The tree T^{ρ} is of the form (d_{1}, r_{1})...(d_{l−1}, r_{l−1})(d_{l+1}, r_{l+1})...(r_{h}). If this tree get ‘hit’ by ρ again there are 3 ways this can happen...(repeat the reduction).

(2) < d_{l}, r′ >∈ ρ where r′ ≠ r_{l}. The tree T^{ρ} has the representation (d_{1}, r_{1})(d_{2}, r_{2})...(d_{l−1}).

(3) < d′, r_{l} >∈ ρ where d′ ≠ d_{l}. The tree T^{ρ} has the representation (d_{1}, r_{1})(d_{2}, r_{2})....(d_{l−1}, r_{l−1})(d_{l}).

From this observation it is not hard to see that the regularity among the trees of hight l, are inherited (after the restriction) by trees of smaller hight. □ If we combine this lemma with lemma 6.1.4, 6.2.3 and lemma 6.2.1 we get:

Lemma 6.3.3 (Strong normal form) Fix q ∈ ℕ\{1}. For all h, l ∈ ℕ there exists d ∈ ℕ such that the following hold: Suppose that F := {T_{1}, T_{2}, ..., T_{u}} is a (D, R)-labelled forest where all trees have hight ≤ h and where d ≤| D | and where | R |=| D | +q^{l}. Then there exists a partial bijection ρ : D → R such that F^{ρ} := {T_{1}^{ρ}, T_{2}^{ρ}, ..., T_{u}^{ρ}} is a forest of (D′, R′)-labelled trees (where D′ := D \ dom(ρ) and R′ := R \ ran(ρ)) on the strong normal form.

Furthermore if F is (q, l)-exceptional, then F^{ρ} is (q, l)-exceptional.

6.4 Proof of the main lemma

Now we are ready to show the main lemma (lemma 6.1.5) in this section. Proof: According to lemma 6.3.3 we lose no generality by assuming that F is on strong normal form. For each d ∈ D and r ∈ R we can consider the branch {< d, r >} of length 1. It appears 0 modulo q^{k} times so we have the identity:

(1) (d, ∗) ⇝ −(d, r) ⇝ +(r) = 0 modulo q^{k}. Here (d, ∗) ⇝ of course denotes the number of PU-trees of the form

(d, r_{1})(u_{1}^{2}, u_{2}^{2})....(u_{1}^{l−1}, u_{2}^{l−1})(u^{l})

Similarly (d, r) ⇝ denotes the number of PU-trees of the form

(d, r)(u_{1}^{2}, u_{2}^{2})....(u_{1}^{l−1}, u_{2}^{l−1})(u^{l}),

and (r) denote the number of appearances of the tree (r). The trees in (d) does not enter the equation because we assume | R |= 0 modulo q^{k}.

The number u of trees in the forest F is given by:

(2) u = Σ_{d∈D} (d, ∗) ⇝ +Σ_{d∈D} (d) + Σ_{r∈R} (r) Now for each d ∈ D consider d_{2}, d_{3}, .., d_{l−1}, d_{l}. Consider the set of trees of the form (d, r_{1})(d_{2}, r_{2})...(d_{l−1}, r_{l−1})(r_{l}) or (d, r_{1})(d_{2}, r_{2})...(d_{l−1}, r_{l−1})(d_{l}) where r_{1}, r_{2}, .., r_{l} belongs to a certain type (expressed by the relative size of r_{1}, .., r_{l}, but also taking their residue classes modulo q^{k} into account). The number of such trees is 0 modulo q^{l−k} provided | R |=| D | +q^{l}. But then:

(3) (d, ∗) ⇝= 0 modulo q^{k} for each d ∈ D. But according to (1)

(4) (d, r) ⇝= (r) modulo q^{k} for all d ∈ D and r ∈ R. According to (2) and the assumption that u ≠ 0 modulo q^{k}, for each d ∈ D

(5) Σ_{d′∈D} (d′) + Σ_{r∈R}(d, r) ⇝≠ 0 modulo q^{k}. But in general

(6) Σ_{r∈R} (d, r) ⇝= (d, ∗) ⇝ so by combining (3) and (5)

(7) Σ_{d∈D} (d) ≠ 0 modulo q^{k}.

But by the normal form theorem we can assume that D is divided into disjoint classes D_{1}, D_{2}, ...., D_{r} which each have 0 modulo q^{l−h} elements. And thus if l − h ≥ k the sum Σ_{d∈D} (d) = Σ_{j=1}^{r}Σ_{d∈D_{j}} (d). By the normal form theorem (d) the number of trees in (d) is constant on each D_{j}, j = 1, 2, .., r so the must equal 0 modulo q^{l−h}. This a is contradiction if l − h ≥ k. □

6.5 Brief discussion of the general problem

The method in the last subsection only give an asymptotic classification of exceptional forest. This is good enough for a complete classification of the Count(q) versus Count(p) problem in the case of polynomial growth rate.

The fact that forests on the strong normal form remains on this form when ‘hit’ by a (randomly chosen?) restriction is very important. And it is very promising for the full classification (when n is large). The critical question is whether we can create order fast enough? Is it possible to create sufficiently much regularity before we have used the elements in I = {1, 2, ..., n}. This seems to be a race between different forces!

In the first version of this paper I tried to bring a hypothetically given exceptional forests F on a strong normal form. This was done by selecting a suitable collection G of group actions on F. For each g ∈ G I defined a forest F^{g} containing the same number of trees as F. Now by a suitable choice of G (so u· | G |≠ 0 modulo q) the forest ∪_{g∈G} F^{g} remains exceptional. By a proper choice of G I was able to show that the resulting forest gets efficiently closer to the strong normal form. This idea does not a priory require any strong assumptions on the hight of the forest. However the argument depend on the validity of a certain modular identity. At present this validity is open. Its validity could be important for the full classification in the general case of sub-exponential growth rate.

7 Some applications

There are various alternative formulations of the classification. It is well known that complexity theory can be viewed as recursion theory done within a finite set of unspecified size. The levels in Arithmetical Hierarchy correspond to the levels in Polynomial Hierarchy [8]. It can be argued that low complexity reasoning is reasoning which can be formalised within (arbitrarily large) finite structures. Suppose that the universe is such an unspecified finite set. Although this is almost impossible to picture it is consistent. Such an “axiomatic finite” universe can be axiomatised in various ways. Its models (which are highly non-recursive) are of course not really finite.

As an example consider the following axiomatisation over second order logic. Suppose that we have the full Arithmetical comprehension axiom schema,

∀z ∃ X ψ(x, z) ↔ x ∈ X.

Here ψ is any first order formula. We allow ψ to contain set-variables. And assume that we have the usual induction axiom

0 ∈ X ∧ ∀n (n ∈ X → n + 1 ∈ X) → ∀n n ∈ X.

If the underlying universe was not assumed to be finite this would be the celebrated and powerful system ACA of analysis. If the underlying universe is axiomatic finite (e.g. satisfies the pigeon-hole principle) we denote the axiom system by ACA^{top}. For this system

Theorem 7.0.1 Count(p) holds in all structures of ACA^{top} + Count(q) exactly when all prime divisors in p appear in q.

Proof: Combine the conservation results in [23],[24] with results for Bounded Arithmetic. By these results the system has the same deductive strength as Bounded Arithmetic axiomatised without functions symbols. By use of the usual coding methods the system is able to handle terms of polynomial growth rate. Thus the positive part of the classification can obtained. □ It is also possible to link the result to length of proofs in propositional logic. This type of link was first pointed out in [19].

Definition 7.0.2 A Boolean formula is a Boolean circuit where for each disjunction ∨_{j} π_{j} and for each conjunction ∧_{j} π_{j} a particular bracketing is specified. The size and the depth of a Boolean formula is defined in the obvious way. In the calculation of the depth, disjunctions ∨_{j}π_{j} and conjunctions ∧_{j}π_{j} are chosen maximally. ♣

Definition 7.0.3 A general propositional proof system ℙ consists of:

(1) A finite number of substitution schemes.

A substitution scheme is a Boolean formula θ which only contains special variables (substitution variables). A substitution instance of θ is obtained by substituting the substitution variables y_{1}, ..., y_{k} by Boolean formulas η_{1}, ..., η_{k}.

(2) A finite number of deduction rules.

A deduction rule \frac{θ_{1},θ_{2},...,θ_{k}}{θ} where θ_{1}, ..., θ_{k} and θ are substitution schemes. A substitution instance is obtained by substituting the substitution variables y_{1}, ..., y_{k} by Boolean formulas η_{1}, ..., η_{k}.

A ℙ-proof (in Hilbert style) of η is a sequence η_{1}, ..., η_{u} = η of Boolean formulas, such that each η_{j}, j = 1, 2, ...., u is either a substitution instance of a substitution scheme, or there are i_{1}, ..., i_{k} < j such that \frac{η_{i_{1}},...,η_{i_{k}}}{η_{j}} is a substitution instance of a deduction rule.

We only consider general propositional proof systems which are consistent and prove the usual tautologies.

The size s of a propositional proof is s := Σ_{j}s(η_{j}), and the depth d is d := max_{j} d(η_{j}). ♣

Definition 7.0.4 A Frege proof system (or a textbook proof system) is a general propositional proof system, where modus ponens \frac{y_{1},¬y_{1}∨y_{2}}{y_{2}} is the only deduction rule.

♣

Definition 7.0.5 Let Count_{n}(p) denote the tautology:

(∨_{i≤n} ∨_{{A:i∈A}} ∨_{{B:i∈B∧A≠B}} (p_{A} ∧ p_{B})) ∨ (∨_{i≤n} ∧_{{i∈A}} ¬p_{A})

where the sets A and B run through the p subsets of {1, 2, ..., n}. ♣

Theorem 7.0.6 Fix p ∈ ℕ. Let A_{p} be the collection of all substitution schemes of the Count(q) principle for q ∈ ℕ which contain all prime factors of p. Let ℙ be any general proof system to which all the schemes in A_{p} are added. Then the tautologies Count_{n}(p), do not have bounded depth polynomial size ℙ-proofs.

Proof: Suppose that for arbitrarily large n ∈ ℕ, there exists a ℙ-proof of depth ≤ d and size ≤ exp(n^{ϵ(n)}). Let R be a suitable relation with domain ℕ^{r}, r ∈ ω, which codes these proofs. Let 𝕄 be a countable non-standard model of Th(ℕ) over some countable language L which extends the language of Arithmetic and contains R. By overspill there exists a non-standard number n ∈ 𝕄 which is not divisible by p, and there exists an 𝕄-definable sequence θ_{1}, θ_{2}, ..., θ_{u} of formulas, which (within 𝕄) is a general propositional ℙ-proof of Count_{n}(p). Furthermore, we can assume that the depth of the proof is ≤ d, and that the size of the proof is ≤ exp(n^{t}) for some t < \frac{1}{ω} (the map ϵ : ℕ → ℚ_{+} can without loss of generality be assumed to be L-definable, because otherwise L can be extended with a relation which defines ϵ).

Now choose a generic truth-table evaluation ρ̃_{G}. Such an evaluation exists according to lemma 2.3.2. Consider the sequence θ_{1}, ..., θ_{u} (considered as circuits) and notice that (θ_{u})ρ̃_{G} = (Count_{n}(p))ρ̃ = 0. According to corollary 2.4.2 there exists j_{0} ≤ u such that (θ_{j_{0}})ρ̃_{G} = 0 but (θ_{j})ρ̃_{G} = 1 for all j < j_{0}. Now each substitution instance θ_{j} of a substitution scheme has (θ_{j})^{ρ} = 1 for each general truth-table evaluation ρ. If θ_{j} is obtained from a deduction rule then (θ_{j})^{ρ} = 1 provided that all the premises also have truth-value 1.

Finally I claim that all substitution instances of the Count(q) principle also get truth-value 1. Now if it got the truth value 0, then by the work in section 3 there would be a 𝕄-definable generic system. By our refinement technique this would imply the existence of a specially labelled (I, p)-forest in which all branches appear 0 modulo q times. And the forest would contain a number of trees not divisible by q. According to the combinatorial results in section 6 this (first order) statement fails in the standard universe. We chose 𝕄 to be a model of first order arithmetic, so this is a contradiction. □

Theorem 7.0.7 Let 𝕄 be a countable non-standard model of Th(ℕ) over a countable first order language L (which contains the language of arithmetic). Suppose that p ∈ ℕ, p ≥ 2 and I := \{1, 2, ..., n\} ⊆ 𝕄 (for some n ∈ 𝕄 \ ω \underline{not} divisible by p). Let

𝕄_{n}^{∗} := {m ∈ 𝕄 : t(n) > m for some term t ∈ L}.

For any generic filter ρ_{G} the partition ρ̃_{G} (see definition 2.2.5 page 12) partitions I into disjoint classes, each containing exactly p elements. If the terms t ∈ L all have polynomial growth rate

(a) (M_{n}^{∗}, ρ_{G}) ⊧ ¬Count(p).

(b) (M_{n}^{∗}, ρ_{G}) satisfies induction for bounded L(P)-formulas.

(c) (M_{n}^{∗}, ρ_{G}) ⊧ Count(q) for all q which contains all prime factors in p.

Proof: It suffices to show that the least number principle is valid for bounded L(P)- formulas with parameters in 𝕄_{n}^{∗}. Now each instance of the least number principle gets translated into a Boolean circuit (or Boolean formula if we specify the bracketing) of the form LNP_{n}(π_{1}, ..., π_{u}) := π_{u} ∨ (∨_{j≤u}(¬π_{j} ∧ (∧_{k<j}π_{k}))). Furthermore, according to earlier observation, each translated instance gets depth ≤ 4 and size ≤ exp(n^{t}) for some t < n^{\frac{1}{ω}}. According to the key lemma (lemma 2.4.1) for \underline{any} generic filter ρ_{G} if (π_{u})ρ̃_{G} = 1, there exists j_{0} ≤ u with (π_{j_{0}})^{ρ} = 1 and (π_{j})^{ρ} = 0 for j < j_{0}. A simple argument shows that LPN_{n}(π_{1}, ...., π_{u})ρ̃_{G} = 1. Using lemma 2.1.6 (𝕄, ρ̃_{G}) satisfies induction for bounded L(P)-formulas with parameters in 𝕄_{n}^{∗}.

Again all Count(q) much be forced true when p contains a prime factor not in q. If not there would exists an 𝕄-definable generic system. And thus by the refinement argument there would be a (I, p) forest with ≠ 0 modulo q trees, in which each (type of) branch appears 0 modulo q times. This is a contradiction when p does not divide q. □

Theorem 7.0.8 Suppose that all terms in L have polynomial growth rate, and contains at least one unspecified relation symbol. Then IΔ_{0}(L)+ Count(q) prove Count(p) exactly when all prime factors in p divides q.

Proof: (𝕄_{n}^{∗}, ρ̃_{G}) ⊧ IΔ_{0}(L) + ¬ Count(p) + Count(q). □

8 Final remarks

The first version of this paper contained the complete reduction of the Count(q) versus Count(p) problem. This reduced the problem to a purely combinatorial problem. The revised version solves this problem explicitly (in the case of polynomial growth-rate). In addition the revised paper develops the underlying theory in more details.

To end, I am happy to learn that the topic is related to Hilberts Nullstellensatz [6], and by [4] also to representations of symmetrical groups. I hope these very interesting links will be further clarified and developed in the future.

References

[1] M.Ajtai; Definability in first order structures; Annals of Pure and Applied Logic 24, (1983) pp 1-48.

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

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

[4] M.Ajtai; The independence of the modulo p counting principles, preprint.

[5] Barrington, Beigel, Rudich; Representing Boolean functions as Polynomials Modulo composite numbers, 24th ACM STOC (1992) pp 455-461.

[6] P.Beame, R. Impagliazzo, J. Krajicek, T. Pitassi, P. Pudlak; Lower bounds on Hilberts Nullstellensatz and propositional proofs, preliminary version.

[7] A.Berrarducci, B.Intrigila; Combinatorial principles in elementary number theory, Annals of Pure and Applied Logic 55 (1991) pp 35-50.

[8] S.Buss; Bounded Arithmetic. Ph.D. dissertation, Princeton University, (1985). As book, Bibliopolis, Napoli (1986).

[9] S.Buss; The propositional pigeonhole principle has polynomial size Frege proofs, Journal of Symbolic logic 52 (1987)) pp 916-927

[10] P.Clote, J.Krajicek, ; Open problems in: Arithmetic, Proof theory and computorial complexity, Oxford university press (1993) pp 289-319.

[11] S.Cook, Recknow; The relative efficiency of Propositional proof systems, Journal of Symbolic logic 44 (1977) pp 36-50

[12] P.D’aquino; Local behavior of the Chebychev theorem in models of IΔ_{0}; Journal of Symbolic Logic 57, (1992) pp 12-27.

[13] Furst, Saxe, Simpser; Parity circuits and the polynomial time hirarchy, Proc 22nd IEEE FOCS (1981) pp 260-270.

[14] J.Haastad; Almost optimal lower bounds for small depth circuits, Proc 18th ACM STOC (1986) pp 6-20. J. Haastad; Computorial limitations for small depth circuits, Ph.D thesis M.I.T. (1986)

[15] J.Krajicek; On Frege and Extended Frege Proof Systems. To appear.

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

[17] A.Macintyre; The strength of weak systems, in: Schriftenreite der Wittgenstein Gessellschaft 13, Logic, Philosophy of Science and Epistemology, Wien (1987) pp43-50.

[18] J.Paris, A.Wilkie, A.Woods; Provability of the pigeonhole principle and the existence of infinitely many primes. Journal of Symbolic Logic 53, (1988), pp 1231-1244.

[19] J.Paris, A.Wilkie; Counting problems in Bounded Arithmetic, in: Methods in Mathematical Logic, LNM 1130, Springer (1985), pp 317-340.

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

[21] 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

[22] A.Razborov; On the method of approximation, in: Proc. 21th ACM STOC (1989) pp 168-176.

[23] S.M.Riis; Making infinite structures finite in models of Second Order Bounded Arithmetic, in: Arithmetic, Proof theory and computorial complexity, Oxford university press (1993) pp 289-319.

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

[25] S.M.Riis; Count(p) versus the pigeon-hole principle; To appear.

[26] S.M.Riis; Finitisation in Bounded Arithmetic; To appear.

[27] R.Smolensky; Algebraic methods in the theory of lower bounds for boolean circuit complexity; Proc. 19th ACM STOC (1987) pp 77-82.

Recent Publications in the BRICS Report Series

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.

RS-94-15 Mogens Nielsen and Glynn Winskel. Petri Nets and Bisimulations. May 1994, 36 pp.

RS-94-14 Nils Klarlund. The Limit View of In�nite Computations. May 1994, 16 pp. To appear in the LNCS proceedings of Concur ’94, LNCS, 1994.

RS-94-13 Glynn Winskel. Stable Bistructure Models of PCF. May 1994, 26 pp. Preliminary draft. Invited lecture for MFCS ’94. To appear in the proceedings of MFCS ’94, LNCS, 1994.

RS-94-12 Glynn Winskel and Mogens Nielsen. Models for Concurrency. May 1994, 144 pp. To appear as a chapter in the Handbook of Logic and the Foundations of Computer Science, Oxford University Press.