Limit Probabilities for Random Sparse Bit Strings

Katherine St. John ^{∗} Department of Mathematics University of Pennsylvania Philadelphia, Pennsylvania 19104

                      stjohn@math.upenn.edu

Submitted: May 12, 1997; Accepted: October 14, 1997

Abstract

Let n be a positive integer, c a real positive constant, and p(n) = c/n. Let U_{n,p} be the random unary predicate under the linear order, and S_{c} the almost sure theory of U_{n, \frac{c}{n}}. We show that for every first-order sentence ϕ:

f_{ϕ}(c) = lim_{n→∞} Pr[U_{n, \frac{c}{n}} has property ϕ]

is an infinitely differentiable function. Further, let S = ⋂_{c} S_{c} be the set of all sentences that are true in every almost sure theory. Then, for every c > 0, S_{c} = S. (Mathematical Reviews Subject Classification: 03C13, 60F20, 68Q05)

1 Introduction

Let n be a positive integer, and 0 ≤ p(n) ≤ 1. The random unary predicate U_{n,p} is a probability space over predicates U on [n] = {1, …, n} with the probabilities determined by Pr[U(x)] = p(n), for 1 ≤ x ≤ n, and the events U(x) are mutually independent over 1 ≤ x ≤ n. U_{n,p} is also called the random bit string.

Let ϕ be a first-order sentence in the language with linear order and the unary predicate. In [7], Shelah and Spencer showed that for every such sentence ϕ and for p(n) ≪ n^{−1} or n^{−1/k} ≪ p(n) ≪ n^{−1/(k+1)}, there exists a constant a_{ϕ} such that

lim_{n→∞} Pr[U_{n,p} ⊧ ϕ] = a_{ϕ}  (1)

∗Current Address: Department of Mathematics, Santa Clara University, Santa Clara, CA 95053-0290, kstjohn@scu.edu.

(Note that “U_{n,p} ⊧ ϕ” means that U_{n,p} has property ϕ. See Section 2 for this and other definitions.)

For each real constant c, let S_{c} be the almost sure theory of the linear ordering with p(n) = \frac{c}{n}. That is,

S_{c} = \{ϕ | lim_{n→∞} Pr[U_{n, \frac{c}{n}} ⊧ ϕ] = 1\}

Let T_{0} be the almost sure theory for p(n) ≪ n^{−1}, and T_{1} be the almost sure theory for n^{−1} ≪ p(n) ≪ n^{−1/2}. By the work of Dolan [2], U_{n,p} satisfies the 0-1 law for p(n) ≪ n^{−1} and n^{−1} ≪ p(n) ≪ n^{−1/2} (that is, for every ϕ, a_{ϕ} = 0 or 1 in Equation 1). This gives that T_{0} and T_{1} are complete theories. Dolan also showed that the 0-1 Law does not hold for n^{−1/k} ≪ p(n) ≪ n^{−1/(k+1)}, k > 1.

In this paper, we will characterize the theories between T_{0} and T_{1}, namely the S_{c}’s. For each first-order formula, ϕ, define the function:

f_{ϕ}(c) = lim_{n→∞} Pr[U_{n, \frac{c}{n}} ⊧ ϕ]

where c ranges over the real, positive numbers. We show that f_{ϕ}(c) is infinitely differentiable. Moreover, we show:

Theorem 1 For every first-order sentence ϕ, f_{ϕ}(c) is either

∑_{i=1}^{i=m} e^{−c} \frac{c^{t_{i}}}{t_{i}!} or 1 − ∑_{i=1}^{i=m} e^{−c} \frac{c^{t_{i}}}{t_{i}!}

for some finite (possibly empty) sequence of positive integers t_{1}, …, t_{m}.

Let S = ⋂_{c} S_{c} be the set of all sentences that are true in every almost sure theory. We show:

Theorem 2 For every real, positive c, S_{c} = S.

Other interesting structures that have also been examined in this fashion are random graphs (without order) with edge probability p(n) = c/n and p(n) = ln n/n+ c/n (see the work of Lynch, Spencer, and Thoma: [5], [6], and [9]). We achieve a simpler characterization of the limit probabilities than those for random graphs due to our underlying models.

To prove these theorems, we look first at the countable models of the almost sure theories (for more on this, see [8]). Let M ⊧ S_{c} be such a model. Each of these models satisfy a set of basic axioms Δ (defined in Section 3). Further, we show, using Ehrenfeucht-Fraisse games, that Δ ∪ {σ_{i}} is complete, where σ_{i} is the firstorder sentence that states “there are exactly i elements for which the unary predicate holds.” For every M, there is an i such that M ⊧ Δ ∪ {σ_{i}}. For each first-order sentence ϕ, either ϕ follows from only a finite number of complete extensions, or the negation of ϕ, ¬ϕ, follows from only a finite number of complete extensions. Let X be the number of elements for which the unary predicate holds in U_{n, \frac{c}{n}}. The Pr[X = i] has binomial distribution. These two facts give the desired form for f_{ϕ}(c) in Theorem 1 and are used to show Theorem 2.

In an effort to keep the paper self-contained and accessible, we have included many definitions and concepts that the expert in the field might wish to skip. Section 2 of this paper includes definitions from logic and finite model theory. To illustrate the definitions, we have included a section of Examples (Section 3). Section 4 includes the proofs of the results.

A note on notation: we will use lower case Greek letters for first-order sentences (ϕ, ψ, …), upper case Greek letters for sets of sentences (Γ, Δ, …), and lower case Roman letters to refer to elements in the universe (i, j, …).

2 Definitions

This section contains the definitions we need from first-order logic and finite model theory. A more thorough treatment of first-order logic can be found in Enderton [4], of finite model theory in Ebbinhaus and Flum [3], and of the probabilistic method in Alon, Spencer, and Erdős [1].

We concentrate on first-order logic over the basic operations {≤, U, =}. That is, we are interested in sentences made up of = (equality), ≤ (linear order), U (an unary predicate), the binary connectives ∨ (disjunction) and ∧ (conjunction), ¬ (negation), and the first-order quantifiers ∃ (existential quantification) and ∀ (universal quantification). “First-order” refers to the range of the quantifiers– we only allow quantification over variables, not sets of variables. For example,

(∃x)(∀y)(x ≤ y)

is a first-order sentence that expresses the property that there is a least element. The x and y are assumed to range over elements of the universe. A set of consistent sentences is often called a theory.

Our structures have an underlying set [n] = {1, …, n} with the basic operations: =, ≤ and U. Without loss of generality, we will interpret the ordering ≤ as the natural ordering on [n]. There are many choices for interpreting the unary predicate U over [n] (2^{n} to be precise). We can view the structures as ordered sequences of 0’s and 1’s, where the ith element in the sequence is 1 if and only if U(i). For example, if n = 5 and the unary predicate holds on the least element, then structure can be represented as [10000]. Let M =< [m], ≤, U >, M_{1} =< [m_{1}], ≤, U_{1} >, and M_{2} =< [m_{2}], ≤, U_{2} > be models where ≤ is a linear order on the universes (the underlying sets) of the structure, and U, U_{1}, and U_{2} are unary predicates on the universes of their respective structure. We will say M models ψ (written: M ⊧ ψ) just in case the property ψ holds of M. If for every model M we have M ⊧ Γ implies M ⊧ ψ, where Γ is a (possibly empty) set of sentences, then we write Γ ⊧ ψ (pronounced “Γ models ψ”). For the particular ψ above, M ⊧ ψ only if there is some element in [m] which is less than or equal to every other element in [m]. Every [m] has a least element (namely 1), so, M ⊧ ψ, and further, ⊧ ψ.

While many things can be expressed using first-order sentences, many cannot. For example, there is no first-order sentence that captures the property that a structure has an universe with an even number of elements (see [3], p. 21). That is, there is no first-order sentence ϕ such that for every model M =< [m], ≤, U >,

M ⊧ ϕ ⟺ m is even

One measure of the complexity of first-order sentences is the nesting of quantifiers. If a formula ϕ has no quantifiers, we say it has quantifier rank 0, and write qr(ϕ) = 0. For all formulas, we define quantifier rank by induction:

• If ϕ = ϕ_{1} ∨ ϕ_{2} or ϕ = ϕ_{1} ∧ ϕ_{2}, then qr(ϕ) = max(qr(ϕ_{1}), qr(ϕ_{2})).

• If ϕ = ¬ϕ_{1}, then qr(ϕ) = qr(ϕ_{1}).

• If ϕ = ∃xϕ_{1} or ϕ = ∀xϕ_{1}, then qr(ϕ) = qr(ϕ_{1}) + 1.

Definition 1 For each t, two models M_{1} and M_{2} are equivalent (with respect to t), M_{1} ≡_{t} M_{2} if they have the same truth value on all first-order sentences of quantifier rank at most t.

The equivalence of structures under all first-order sentences of quantifier rank less than or equal to t is connected to the t-pebble games of Ehrenfeucht and Fraisse, described in [3]. Given two structures M_{1} and M_{2}, M_{1} ≡_{t} M_{2} if and only if the second player has a winning strategy for every t-pebble Ehrenfeucht-Fraisse game played on M_{1} and M_{2}. We define the game below:

Definition 2 The t-pebble Ehrenfeucht-Fraisse game (EF game) on M_{1} and M_{2} is a two-person game of perfect information. For the game, we have:

• Players: There are two players:

– Player I, often called Spoiler, who tries to ruin any correspondence between the structures.

– Player II, often called Duplicator, who tries to duplicate Spoiler’s last move.

• Equipment: We have t pairs of pebbles and the two structures M_{1} and M_{2} as game boards.

• Moves: The players take turns moving. At the ith move, the Spoiler chooses a structure and places his ith pebble on an element in that structure. Duplicator then places her ith pebble on an element in the other structure.

• Winning: If after any of Duplicator’s moves, the substructures induced by the pebbles are not isomorphic, then Spoiler wins. After both players have played t moves, if Spoiler has not won, then Duplicator wins.

We say a player has a winning strategy for the t-pebble game on M_{1} and M_{2}, if no matter how the opponent plays, the player can always win. These games form a powerful tool for showing theories are complete. A theory T is complete if for every sentence ϕ, either T ⊧ ϕ or T ⊧ ¬ϕ. Equivalently, a theory T is complete if any two models of T satisfy the same first order sentences. For each q, we can show this for sentences of quantifier rank q by proving that Duplicator has a winning strategy for the q-move EF game on any two models of T. We will use this reduction to games to show the completeness of our theories S_{c} (see Lemma 1).

3 Examples

To give some intuition about what these models and theories look like, we begin with an informal discussion of T_{0} and T_{1}. When p(n) ≪ n^{−1}, almost surely the unary predicate never holds (i.e. no 1’s occur). To see this, let A_{i} be the event that U(i) holds, X_{i} be the random indicator variable, and X = ∑_{i} X_{i}, the total number of 1’s that occur (i.e. the total number of elements for which the unary predicate holds). Then, E(X_{i}) = p(n), and by linearity of expectation,

E(X) = ∑_{i} E(X_{i}) = np(n).

As n gets large, E(X) → 0. Since Pr[X > 0] ≤ E(X), almost surely, no 1’s occur. This gives

lim_{n→∞} Pr[U_{n,p} ⊧ (∃x)U(x)] = 0.

The negation of this statement, (∀x)¬U(x), almost surely is true. So, (∀x)¬U(x) is in the almost sure theory T_{0}.

The almost sure theory also contains sentences about the ordering. Since every U_{n,p} is linearly ordered with a minimal and maximal element, the first-order sentences that state these properties are in T_{0}, T_{1}, and each S_{c}. Let Γ_{l} be the order axioms for the linear theory, that is, the sentences:

(∀xyz)[(x ≤ y ∧ y ≤ z) → x ≤ z]
(∀xy)[(x ≤ y ∧ y ≤ x) → x = y]
(∀x)(x ≤ x)
(∀xy)(x ≤ y ∨ y ≤ x)

The following sentences guarantee that there is a minimal element and a maximal element:

\begin{matrix}μ_{1} : & (∃x∀y)(x ≤ y) \\ μ_{2} : & (∃x∀y)(x ≥ y) \end{matrix}

Further, every element, except the maximal element, has a unique successor under the ordering, and every element, except the minimal element, has a unique predecessor. This can be expressed in the first-order language as:

\begin{matrix}η_{1} : & (∀x)[(∀y)(x ≥ y) ∨ (∃y∀z)((x ≤ y ∧ x ≠ z) → y ≤ z)] \\ η_{2} : & (∀x)[(∀y)(x ≤ y) ∨ (∃y∀z)((x ≥ y ∧ x ≠ z) → y ≥ z)] \end{matrix}

As n → ∞, the number of elements also goes to infinity. To capture this, we add, for each positive r, the axiom:

δ_{r} : (∃x_{1} … x_{r})(x_{1} < x_{2} < ⋯ < x_{r})

For n ≥ r, U_{n,p} ⊧ δ_{r}. Thus, for every U_{n,p},

U_{n,p} ⊧ Γ_{l} ∧ μ_{1} ∧ μ_{2} ∧ η_{1} ∧ η_{2} ∧ δ_{1} ∧ δ_{2} ∧ … ∧ δ_{n}

and Σ = {Γ_{l}, μ_{1}, μ_{2}, η_{1}, η_{2}, ⋀_{r} δ_{r}} ⊂ T_{k}, for k = 1, 2, and for each c, Σ ⊂ S_{c}.

For T_{0}, the only additional axiom we need is (∀x)(¬U(x)). The simplest model of T_{0} is an infinite decreasing chain of 0’s followed by an infinite increasing chain of 0’s (see Figure 1). More complicated models also satisfy Σ ∪ (∀x)(¬U(x)), namely those with arbitrarily many copies of of chains of 0’s, ordered like the integers (called “Z-chains”), with an infinite decreasing chain of 0’s at the beginning and an infinite increasing chain of 0’s at the end. The ordering of the Z-chains is not determined. It could be finite, infinite with discrete points, or it could be “dense.” By the latter, we mean that between any 2 Z-chains, there’s another.

When n^{−1} ≪ p(n) ≪ n^{−1/2}, almost surely isolated 1’s occur. Using the notation above, we have E(X) → ∞ as n → ∞. Since all the events are independent, Var[X] ≤ E[X]. By the Second Moment Method (see [1], chapter 4 for details),

Pr[X = 0] ≤ \frac{Var[X]}{E[X]^{2}} ≤ \frac{E[X]}{E[X]^{2}} = \frac{1}{E[X]} → 0

[000 ⋯) (⋯ 000]

Figure 1: A model of T_{0}

[00 ⋯)(⋯ 00100 ⋯) \underbrace{(⋯ 00100 ⋯)}_{“a Z-chain”} · · · · · · (⋯ 00100 ⋯)(⋯ 00100 ⋯)(⋯ 00]

Figure 2: A model of T_{1}

Thus, Pr[X > 0] → 1. Let B_{i} be the event that i and i+1 are 1’s, let Y_{i} be its random indicator variable, and Y = ∑_{i} Y_{i}. Then, E(Y_{i}) = Pr[B_{i}] = p^{2} and E(Y) ∼ np^{2} → 0. So, almost surely, 1’s occur, but no 1’s occur adjacent in the order. If, for each r > 0, we let C_{i,r} be the event that i and i + r are 1’s and C_{r} = ∑_{i} C_{i,r}, we can show, by similar argument, that C_{r} → 0. This works for any fixed r, so, the 1’s that do occur are isolated from one another by arbitrarily many 0’s.

For models of T_{1}, we cannot have a single infinite chain, since all the 1’s must be isolated. So, we must have infinitely many Z-chains that contain a single 1. Between these can be any number of Z-chains that contain no 1’s. Call any Z-chain that contains a 1 distinguished. For any distinguished Z-chain, except the maximal distinguished chain, almost surely, there’s a least distinguished Z-chains above it (this follows from the discreteness of the finite models). In other words, every distinguished Z-chain, except the maximal 1, has a distinguished successor Z-chain. This rules out a “dense” ordering of the distinguished Z-chains and leads to a “discreteness” of 1’s, similar to the discreteness of elements we encountered above. It says nothing about Z-chains without 1’s– those could have any countable order type they desire. So, the simplest model is pictured in Figure 2.

By the earlier discussion, we know that the basic axioms Σ ⊂ T_{1}. The only further axioms needed are those that guarantee arbitrarily many 1’s occurring far apart and the “discreteness” of 1’s. These axioms echo the basic axioms listed before, for each

[00 ⋯)(⋯ 00100 ⋯)(⋯ 00100 ⋯)(⋯ 00]

Figure 3: A model of S_{c}

r we have:

μ′_{1} : (∃x)(∀y)[(U(x) ∧ U(y)) → (x ≤ y)]
μ′_{2} : (∃x)(∀y)[(U(x) ∧ U(y)) → (x ≥ y)]
δ′_{r} : (∃x_{1} … x_{r})(x_{1} < x_{2} < ⋯ < x_{r} ∧ U(x_{1}) ∧ ⋯ ∧ U(x_{r}))
ϵ_{r} : (∀x_{1}, x_{2})[(U(x_{1}) ∧ U(x_{2}) ∧ x_{1} < x_{2}) →
(∃y_{1}, …, y_{r})(¬U(y_{1}) ∧ … ∧ ¬U(y_{r}) ∧ x_{1} < y_{1} < ⋯ < y_{r} < x_{2})]

These axioms, along with Σ, axiomatize T_{1}, which follows from an EF game argument.

When p = c/n, the expected number of 1’s in U_{n, \frac{c}{n}} is (using the notation from above):

E(X) = ∑_{i=1}^{n} E(X_{i}) = ∑_{i=1}^{n} p(n) = n · \frac{c}{n} = c.

In fact, Pr[X = t] has binomial distribution and the limiting probability is Poisson (see Lemma 3). So, with probability Pr[X = t] → e^{−c} \frac{c^{t}}{t!} , U_{n, \frac{c}{n}} has exactly t 1’s. In any countable model of the almost sure theory, S_{c}, the 1’s occur arbitrarily far apart, as in models of T_{1}. A simple model of S_{c}, which occurs with probability e^{−c} \frac{c^{2}}{2!} is in Figure 3. Let Δ be the axioms Σ along with the axiom schema ϵ_{r} for every r that guarantees the 1’s are isolated (that is, Δ = Σ ∪ ⋃_{r}{ϵ_{r}}). For each S_{c}, Δ ⊂ S_{c}.

4 The Results

For each natural number i, let σ_{i} be the first-order sentence that says “there exist exactly i 1’s.” So,

σ_{1} := (∃x)[U(x) ∧ (∀y)(U(y) → y = x)]
σ_{i+1} := (∃x_{1}x_{2} … x_{i+1})[U(x_{1}) ∧ U(x_{2}) ∧ … ∧ U(x_{i+1})
∧ x_{1} < x_{2} ∧ x_{2} < x_{3} ∧ ⋯ x_{i} < x_{i+1}
∧ (∀y)(U(y) → (y = x_{1} ∨ y = x_{2} ∨ ⋯ ∨ y = x_{i+1}))]

Recall that we defined the set of sentences S to be all sentences that hold in every almost sure theory (that is, S = ⋂_{c} S_{c}). Then:

Lemma 1 For each i, S ∪ {σ_{i}} is complete.

Proof: Note that the basic axioms Δ (defined in Section 3) are contained in S. So, it suffices to show that Δ ∪ {σ_{i}} is complete (that is for every sentence ϕ, either Δ ∪ {σ_{i}} ⊧ ϕ or Δ ∪ {σ_{i}} ⊧ ¬ϕ). We will show this is a complete theory by giving, for every t, a winning strategy for Duplicator for the t-move game on two models, M_{1} and M_{2} of Δ ∪ {σ_{i}}. The essence of the proof is that in our theories the 1’s are spaced arbitrarily far apart. So, what matters in pebble placement is the distance to the closest 1. Since t pebbles can only tell distances of length ≤ 2^{t}, we define the t-type of an interval to keep track of small distances from 1’s.

Let the t-type of an interval [a, b] to be (L, R, O, Z), with O the number of 1’s in the interval; Z the number of 0’s in the interval; L the minimal nonnegative number with a + L a 1; R the minimal nonnegative number with b − R a 1 – but if any of these numbers are not in the set {0, 1, …, 2^{t}} call them by a special symbol MANY_{t}. (That is, if the first 2^{t} + 1 symbols of the interval are 0’s then L = MANY_{t}).

The strategy for Duplicator with t moves remaining and x_{1} < … < x_{s} the moves already made on model M_{1}; x′_{1} < … < x′_{s} the moves already made on model M_{2} is to ensure that for all i intervals [x_{i}, x_{i+1}], [x′_{i}, x′_{i+1}] have the same t-type. To include the end intervals, assume Spoiler starts by playing the minimal and maximal elements of M to which Duplicator of course follows on M′. Since both M_{1} and M_{2} model σ_{i}, each has the same number of 1’s occurring, the t-type of the initial moves are the same, namely (MANY_{t}, MANY_{t}, MANY_{t}, MANY_{t}) for i sufficiently larger than t (i > 3^{t} suffices).

We show that if [a, b], [a′, b′] have the same t-type then for all x ∈ [a, b] (Spoiler move) there exists x′ ∈ [a′, b′] (Duplicator move) with [a, x], [a′, x′] having the same (t − 1)-type and [x, b], [x′, b′] also having the same (t − 1)-type (similarly for every x′ ∈ [a′, b′]). We proceed by induction on t, the number of moves remaining. For t = 1, if U(x), then we must have O > 0. So, there must be a x′ ∈ [a′, b′] such that U(x′). If ¬U(x), then Z > 0 and there must be a x′ ∈ [a′, b′] such that ¬U(x′). Thus, Duplicator has a winning strategy for the game on intervals with the same 1-type and with 1 move remaining.

For t > 1, assume that [a, b] and [a′, b′] have the same t-type: (L, R, O, Z). Let (L_{l}, R_{l}, O_{l}, Z_{l}) be the (t − 1)-type of [a, x] and (L_{r}, R_{r}, O_{r}, Z_{r}) be the (t − 1)-type of [x, b]. If Z ≠ MANY_{t}, then the lengths of the intervals [a, b] and [a′, b′] are equal and ≤ 2^{t}. In this case, the t-type fully determines the occurrence and placement of any 1 in the interval (if one occurs). Let x′ = a′ + x − a. If O = 0, then L = R = 0, and both intervals are all 0’s. If O = 1 (the only other possibility since Z ≠ MANY_{t} and the 1’s occur arbitrarily far apart), then the 1 occurs the exact same distance from x and x′. So, the resulting intervals [a, x] and [a′, x′], and [x, b] and [x′, b′] have the same t-types, and thus, (t − 1)-types.

So, assume Z = MANY_{t}, that is, the lengths of the intervals [a, b] and [a′, b′] are at least 2^{t} but may not be equal. If x − a < 2^{t−1}, let x′ = a′ + x − a. By construction, [a, x] and [a′, x′] have the same length and the same number of 1’s. If the number of 1’s is zero, then L_{l} = R_{l} = O_{l} = 0 and Z_{l} = x − a for both intervals. If the number of 1’s is one (the only other possibility), then L_{l} = L, R_{l} = MANY_{t−1}, O_{l} = 1, Z_{l} = x − a − 1 for both [a, x] and [a′, x′]. Since x − a < 2^{t−1}, we have b − x > 2^{t−1} and Z_{r} = MANY_{t−1}. If O_{l} = 0, then the number of 1’s in [x, b] and [x′, b′] is the same as the number of 1’s in the original intervals (i.e. O). If the number of 1’s is greater than 2^{t−1}, then O_{r} = MANY_{t−1}. Otherwise, O_{r} = O. If O_{l} = 1, then the number of 1’s in [x, b] and [x′, b′] is one less than that in the original intervals. So, O_{r} = MANY_{t−1} if O − 1 > 2^{t−1}, otherwise, O_{r} = O − 1. Thus, [a, x] and [a′, x′], and [x, b] and [x′, b′] have the same t-types, and thus, (t − 1)-types. If b − x < 2^{t−1} follows by a similar argument.

So, assume a + 2^{t−1} ≤ x ≤ b + 2^{t−1}. This gives that the length of both the leftside and rightside intervals is at least 2^{t−1}. Let −2^{t−1} < y < 2^{t−1} be such that U(x + y) if such a y exists. Let x′ be such that U(x′ + y) and if x + y is the ith 1 counting from the left for i ≤ 2^{t−1}, then x′ + y is also the ith 1 counting from the left (such exists since both [a, x] and [a′, x′] have the same value for O). Similarly, if x + y is the ith 1 counting from the right for i ≤ 2^{t−1}, then x′ + y is also the ith 1 counting from the right. If neither of these hold, choose x′ such that x′ + y is the ith 1 for i > 2^{t}. By construction, the resulting intervals will have the same values for L_{l}, L_{r}, R_{l}, R_{r}, O_{l}, O_{r}. The values for Z_{l} = Z_{r} = MANY_{t}. So, [a, x] and [a′, x′], and [x, b] and [x′, b′] have the same t-types, and thus, (t − 1)-types.

Lastly, assume a + 2^{t−1} ≤ x ≤ b + 2^{t−1} but no y such that U(x + y) and −2^{t−1} < y < 2^{t−1} exists. Then x is at least 2^{t−1} from a, b, and every i such that U(i). This gives L_{r} = R_{l} = Z_{l} = Z_{r} = MANY_{t−1}. As before, the values of L_{l} and R_{r} depend on L and R (since they count the distance from endpoints that did not move). So, we only need for our choice of x′ that it is at least 2^{t−1} from any occurrence of 1 and has the same value for O_{l} and O_{r} that [a, x] and [x, b] does. If O_{l} < 2^{t−1}, choose x′ so that it occurs at least 2^{t−1} above the O_{l}th 1. If O_{r} < 2^{t−1}, then [x′, b] also has the same number of 1’s since O = O_{l} + O_{r} is the value for both [a, b] and [a′, b′]. If O_{r} = MANY_{t−1}, then, again [x′, b] also has the value O_{r} = MANY_{t−1}. A similar argument works for O_{r} < 2^{t−1}. If both O_{l} = O_{r} = MANY_{t−1}, then choose x′ so that it occurs at least 2^{t−1} above the 2^{t−1}th 1 (such an x′ exists, since O = MANY_{t}). So, [a, x] and [a′, x′], and [x, b] and [x′, b′] have the same t-types, and thus, (t − 1)-types.

Thus, [a, x] and [a′, x′] have the same (t − 1)-types, as well as [x, b] and [x′, b′]. By inductive hypothesis, Duplicator can win the (t − 1)-move game played on [a, x] and [a′, x′], and on [x, b] and [x′, b′]. Duplicator can win the t-move game on [a, b] and [a′, b′] by placing x′ (x) according to the above strategy, and then following the strategy given by inductive hypothesis for the remaining t − 1 moves. □

Definition 3 For each first-order sentence ϕ, let M(ϕ) = {i | S ∪ {σ_{i}} ⊧ ϕ}.

Lemma 2 For each first-order ϕ, M(ϕ) is finite or co-finite.

Proof: Let ϕ be a first-order sentence. Let t = qr(ϕ), the quantifier rank of ϕ. We claim that either max{i ∈ M(ϕ)} < 3^{t} or max{i ∈ M(¬ϕ)} < 3^{t}.

Assume not. Then, there exists i, j > 3^{t} such that i ∈ M(ϕ) and j ∈ M(¬ϕ). Let M_{1} ⊧ Δ ∪ {σ_{i}} and M_{2} ⊧ Δ ∪ {σ_{j}}. i ∈ M(ϕ) also implies M_{1} ⊧ ϕ, and j ∈ M(¬ϕ) implies M_{2} ⊧ ¬ϕ. Since i and j are sufficiently larger than t, the strategy in Lemma 1, gives that M_{1} and M_{2} agree on all first-order sentences of quantifier rank ≤ t. This gives a contradiction since M_{1} and M_{2} disagree on ϕ. □

Lemma 3 Let c be a real positive constant and i a positive integer. Let X be the number of 1’s occurring in U_{n,c/n}. Then Pr[X = i] has a binomial distribution and lim_{n→∞} Pr[X = i] is Poisson.

Moreover,

lim_{n→∞} Pr[X = i] = lim_{n→∞} Pr[U_{n, \frac{c}{n}} ⊧ σ_{i}] = e^{−c} \frac{c^{i}}{i!}

Proof: For each i and c, the probability that a set of size i is all 1’s is (\frac{c}{n})^{i}. The probability that the remaining n − i vertices are all 0’s is (1 − \frac{c}{n})^{n−i}. Since there are \binom{n}{i} ways to choose such an i element set,

Pr[X = i] = (\begin{matrix}n \\ i \end{matrix}) (\frac{c}{n})^{i}(1 − \frac{c}{n})^{n−i}

As we let n gets large:

lim_{n→∞} Pr[X = i] = lim_{n→∞} (\begin{matrix}n \\ i \end{matrix}) (\frac{c^{i}}{n^{i}})(1 − \frac{c}{n})^{n}(1 − \frac{c}{n})^{−i}
= lim_{n→∞}(\frac{n^{i}}{i!} )(\frac{c^{i}}{n^{i}})e^{−c} · 1
= e^{−c} \frac{c^{i}}{i!}
□

Proofs of the Theorems

Proof of Theorem 1 : Let ϕ be a first-order sentence. Then, by Lemma 2, M(ϕ) is finite or co-finite. Assume first that M(ϕ) is finite (the co-finite case follows by similar argument on M(¬ϕ)), and there exists positive integers t_{1} < t_{2} < … < t_{m} such that M(ϕ) = {t_{1}, …, t_{m}}. By Lemma 3, for each positive integer, i,

q_{i} = lim_{n→∞} Pr[U_{n, \frac{c}{n}} ⊧ σ_{i}] = e^{−c} \frac{c^{i}}{i!}

Then,

lim_{s_{0}→∞} ∑_{s=0}^{s_{0}} q_{s} = ∑_{s=0}^{∞} q_{s} = ∑_{s=0}^{∞} e^{−c} \frac{c^{s}}{s!} = e^{−c} ∑_{s=0}^{∞} \frac{c^{s}}{s!} = e^{−c}e^{c} = 1

So, for any positive ϵ > 0, there exists s_{0} > t_{m} such that

|1 − ∑_{s=1}^{s_{0}} q_{s}| < ϵ

Let β_{s_{0}} = ¬ ⋁_{s≤s_{0}} σ_{s}. We have

lim_{n→∞} Pr[U_{n,c/n} ⊧ β_{s_{0}}] = 1 − ∑_{s=1}^{s_{0}} q_{s} < ϵ  (2)

Claim 1 ϕ has limiting probability ∑_{s∈M(ϕ)} q_{s}.

Proof of Claim: If suffices to show that ϕ ↔ ¬ ⋁_{t∈M(ϕ)} σ_{t} has limiting probability 0. This breaks into the cases of ϕ ∧ ¬ ⋁_{t∈M(ϕ)} σ_{t} and ¬ϕ ∧ ⋁_{t∈M(ϕ)} σ_{t}. For the first, fix ϵ > 0 and choose s_{0} such that Equation 2 holds. Then (ϕ ∧ ¬ ⋁_{t∈M(ϕ)} σ_{t}) ↔ β_{s_{0}} ∨ ⋁_{s≤s_{0},s∉M(ϕ)}(ϕ ∧ σ_{s}) is in the almost sure theory. ⋁_{s≤s_{0},s∉M(ϕ)}(ϕ ∧ σ_{s}) is a finite disjunction of sentences with limiting probability 0. So,

lim_{n→∞} Pr[U_{n,c/n} ⊧ (ϕ ∧ ¬ ⋁_{t∈M(ϕ)} σ_{t})]
= lim_{n→∞} Pr[(U_{n,c/n} ⊧ β_{s_{0}} ∨ ⋁_{s≤s_{0},s∉M(ϕ)}(ϕ ∧ σ_{s}))]
≤ max{lim_{n→∞} Pr[U_{n,c/n} ⊧ β_{s_{0}}],
lim_{n→∞} Pr[U_{n,c/n} ⊧ ⋁_{s≤s_{0},s∉M(ϕ)}(ϕ ∧ σ_{s})]}
≤ max{ϵ, 0}
= ϵ

Since ϵ is arbitrary, lim_{n→∞} Pr[U_{n,c/n} ⊧ (ϕ ∧ ¬ ⋁_{t∈M(ϕ)} σ_{t})] = 0.

For the second case of ¬ϕ ∧ ⋁_{t∈M(ϕ)} σ_{t}, we have the finite disjunction of (¬ϕ ∧ σ_{t}), for t ∈ M(ϕ), each of which has limit probability 0. So,

lim_{n→∞} Pr[U_{n,c/n} ⊧ ¬ϕ ∧ ⋁_{t∈M(ϕ)} σ_{t}] = 0.

□

Using the claim,

f_{ϕ}(c) = lim_{n→∞} Pr[U_{n,c/n} ⊧ ϕ]
= lim_{n→∞} Pr[U_{n,c/n} ⊧ (σ_{t_{1}} ∨ … ∨ σ_{t_{m}})]
= ∑_{t∈M(ϕ)} lim_{n→∞} Pr[U_{n,c/n} ⊧ σ_{t}]
= ∑_{t∈M(ϕ)} e^{−c} \frac{c^{t}}{t!}

□

Proof of Theorem 2: By definition, S is contained in S_{c} (since S is defined to be the intersection of the almost sure theories, ⋂_{c} S_{c}). So, we need to show, that for every c, S_{c} ⊆ S. Fix a real positive constant d, and let ϕ be a first order sentence contained in S_{d}. Then, by definition, f_{ϕ}(d) = 1. So, M(ϕ) ≠ ∅. Assume M(ϕ) is finite and M(ϕ) = {t_{1}, …, t_{m}}. By Theorem 1, for every positive c,

\begin{aligned}f_{ϕ}(c) & = & e^{−c} ∑_{i=1}^{i=m} \frac{c^{t_{i}}}{t_{i}!} < e^{−c} ∑_{i=1}^{i=∞} \frac{c^{i}}{i!} \\ & < & e^{−c} · e^{c} = 1 \end{aligned}

which gives the contradiction: f_{ϕ}(d) < 1. So, M(ϕ) must not be finite.

By Lemma 2, M(ϕ) is either finite or co-finite. From above, M(ϕ) is not a nonempty finite set. If t ∉ M(ϕ), then t ∈ M(¬ϕ). So, we must have M(¬ϕ) is finite. Assume M(¬ϕ) is non-empty, and for some t_{1}, …, t_{m}, M(¬ϕ) = {t_{1}, …, t_{m}}. Then,

f_{ϕ}(c) = 1 − e^{−c} ∑_{i=1}^{i=m} \frac{c^{t_{i}}}{t_{i}!} < 1 for c > 0

which contradicts f_{ϕ}(d) = 1. So, we must have that M(¬ϕ) = ∅. This gives that f_{ϕ} is constantly one. So, ϕ ∈ S_{c} for every c, and thus, ϕ ∈ S.

Therefore, S = ⋂_{c} S_{c}. □

5 Future Work

The work of [7] and [8] characterize the almost sure theories and their countable models for p(n) ≪ n^{−1} and n^{−1/k} ≪ p(n) ≪ n^{−1/(k+1)} for k ≥ 1. In this paper, we fill the “gap” between p(n) ≪ n^{−1} and n^{−1} ≪ p(n) ≪ n^{−1/2} by characterizing the almost sure theories of U_{n, \frac{c}{n}} and giving the form of the function f_{ϕ}(c) for each first-order sentence ϕ. What happens for the gaps at p(n) = cn^{−1/k} for larger k? That is, what does

g_{k,ϕ} = lim_{n→∞} Pr[U_{n,cn^{−1/k}} ⊧ ϕ]

look like for each integer k > 1 and first-order sentence ϕ? How does this answer change if ϕ is allowed to be from the extended language of monadic second order logic?

6 Acknowledgments

The author would like to thank Joel Spencer for his many insightful comments on this paper and for his help in clarifying Theorem 1.

References

[1] Noga Alon, Joel H. Spencer, and Paul Erdős. The Probabilistic Method. John Wiley and Sons, Inc, New York, 1992.

[2] Peter Dolan. A zero-one law for a random subset. Random Structures and Algorithms, 2:317–326, 1991.

[3] Heinz-Dieter Ebbinghaus and Jorg Flum. Finite Model Theory. Springer, Berlin, 1995.

[4] Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press, San Diego, 1972.

[5] James F. Lynch. Probabilities of sentences about very sparse random graphs. Random Structures and Algorithms, 3:33–54, 1992.

[6] Saharon Shelah and Joel H. Spencer. Can you feel the double jump. Random Structures and Algorithms, 5(1):191–204, 1994.

[7] Saharon Shelah and Joel H. Spencer. Random sparse unary predicates. Random Structures and Algorithms, 5(3):375–394, 1994.

[8] Joel H. Spencer and Katherine St. John. Random unary predicates: Almost sure theories and countable models. Submitted for publication, 1997.

[9] Joel H. Spencer and Lubos Thoma. On the limit values of probabilities for the first order properties of graphs. Technical Report 97-35, DIMACS, 1997.