Untestable Properties Expressible with FourFirst-Order Quantifiers?
Charles Jordan?? and Thomas Zeugmann? ? ?
Division of Computer Science
Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan{skip,thomas}@ist.hokudai.ac.jp

Abstract. In property testing, the goal is to distinguish between structures that have some desired property and those that are far from having
the property, after examining only a small, random sample of the structure. We focus on the classification of first-order sentences based on theirquantifier prefixes and vocabulary into testable and untestable classes.
This classification was initiated by Alon et al. [1], who showed that graphproperties expressible with quantifier patterns ∃∗ ∀∗ are testable but that
there is an untestable graph property expressible with a quantifier pattern ∀∗ ∃∗ . In the present paper, their untestable example is simplified.
In particular, it is shown that there is an untestable graph property expressible with each of the following quantifier patterns: ∀∃∀∃, ∀∃∀2 , ∀2 ∃∀and ∀3 ∃.
Key words: property testing, logic

1

Introduction

In property testing, we take a small, random sample of a large structure and wish
to determine if the structure has some desired property or if it is far from having
the property. The hope is that we can gain efficiency in return for not deciding
the problem exactly. We focus on the classification problem for testability, where
the goal is to determine exactly which prefix vocabulary classes of first-order logic
are testable and which are not.
Property testing was first introduced in the context of program verification(cf. Rubinfeld and Sudan [11] and Blum et al. [4]). The study of combinatorialproperty testing was initiated by Goldreich et al. [8], who focused on graphs.
Alon et al. [1] first considered the classification problem for testability, although
they restricted their attention to undirected, loop-free graphs. They showed thatall such first-order sentences1 with quantifier prefixes of the form ∃∗ ∀∗ express?

An earlier version with additional proofs is available as [9]. We would like to thankan anonymous referee for significant improvements to Theorem 2.
??
Supported by a Grant-in-Aid for JSPS Fellows under Grant No. 2100195209.
???
Supported by MEXT Grand-in-Aid for Scientific Research on Priority Areas underGrant No. 21013001.
1
We assume throughout that all sentences are in prenex normal form.

2

C. Jordan and T. Zeugmann

testable properties. They also showed that there exists an untestable property
expressible with the prefix ∀∗ ∃∗ . The example they give is (essentially) an encoding of graph isomorphism that can be expressed with a quantifier prefix ofthe form ∀12 ∃5 .
In studying the classification problem, it is necessary to determine the minimum number of quantifiers needed to express untestable properties. Additionally, the first-order theory of graphs is not restricted to undirected, loop-freegraphs. Here, we show that there exists an untestable property of directed graphsthat is expressible in first-order sentences with prefixes ∀∃∀∃, ∀∃∀2 , ∀2 ∃∀, and∀3 ∃, when equality (=) is allowed (see Theorem 2 for a more formal statement).
That is, with prefixes of these patterns and when equality is allowed, four firstorder quantifiers suffice to express an untestable graph property. The proof isa modification of the proof by Alon et al. [1], which is made possible by thepresence of directed edges and loops.
The results in Jordan and Zeugmann [10] show that one universal quantifier
is not sufficient to express an untestable property (regardless of the vocabulary),and so it would be interesting to determine the status of the remaining prefixes
with two universal quantifiers.
A class of first-order logic has the finite model property if every satisfiable
formula in the class has a finite model. Classes without the finite model property
contain infinity axioms, i.e. satisfiable formulas without finite models. The current classification for testability closely resembles the classification for the finite
model property. It would be particularly interesting to determine the testabilityof the “minimal” classes with infinity axioms [∀3 ∃, (0, 1)] and [∀∃∀, (0, 1)]2 .

2Preliminaries

In property testing, the goal is always to distinguish structures that have someproperty from those that are far from having the property. We are particularlyinterested in properties that are first-order definable, and so we begin by defining
our logic. Enderton [7] provides a more detailed introduction.
The atomic terms are the (countable) variable symbols xi . There are nofunction or constant symbols, and so the terms are exactly the atomic terms.
The atomic formulas are E(xi , xj ) and xi = xj , for any two variable symbols xi
and xj . The formulas are built from the atomic formulas using the usual Boolean
connectives (i.e., ∧, ∨, →, ↔), negation (¬) and first-order quantifiers (∀, ∃) inthe canonical way. The well-formed formulas or sentences are the formulas whichcontain no free variables. We have no further use for formulas that are not wellformed, and so we will refer to the well-formed formulas simply as formulas.
Our logic contains a special equality predicate symbol (=) which is always
interpreted as true equality (i.e., xi = xj is true iff the two symbols xi and xj
refer to the same object). It also contains a single binary predicate symbol, which
2

These classes do not permit equality and so Theorem 2 does not immediately imply
that the first is untestable.

Untestable Properties Expressible with Four First-Order Quantifiers

3

we have given the name E. Of course, the name of this symbol is not important;any fixed, unique name could have been chosen.
A structure is an object that allows us to interpret a sentence in our logic.
It consists of a finite universe U over which the variable symbols are allowed torange, and a binary relation E corresponding to the symbol E in our logic. Anysuch object can be considered as a (directed) graph, so from now on we refer tothese structures as graphs. See Diestel [6] for an introduction to graph theory.
Definition 1. A graph A = (U A , E A ) is a pair consisting of a finite set ofvertices U A and a binary edge relation E A ⊆ U A × U A .
The natural numbers are denoted by N := {0, 1, . . .}. For any set U wewrite |U | to denote the cardinality of U and generally identify U with the set{0, . . . , |U | − 1}. We denote the set of graphs on exactly n vertices by G n andthe set of all graphs by G := ∪n∈N G n . The size of the universe of a graph
A = (U A , E A ) is denoted by #(A) and defined as #(A) := |U A |.
A property P is any subset of G. Sentences are interpreted in the usual way,
and so we can decide A |= ϕ for any fixed graph A and first-order sentence ϕ.
Each sentence ϕ therefore defines a property, namely the set of its models,Pϕ := {A | A ∈ G and A |= ϕ} .
The properties that we use in the proof of Theorem 2 involve encodings of
isomorphisms. Graphs A = (U A , E A ) and B = (U B , E B ) are isomorphic if there
is a bijection f : U A → U B such that for all (x, y) ∈ U A × U A , (x, y) ∈ E A
iff (f (x), f (y)) ∈ E B . We say that a property P is closed under isomorphisms
if for all isomorphic A, B ∈ G, it is true that A ∈ P iff B ∈ P . All properties
expressible in our logic are closed under isomorphisms.
The goal in property testing is to distinguish between structures that haveproperties and structures that are far from having them. This requires a distancemeasure, which we define next. In the following, ⊕ denotes exclusive-or and E A
and E B are the edge relations of A and B, respectively.
Definition 2. Let n ∈ N and let U be any universe such that |U | = n. Furthermore, let A = (U, E A ) and B = (U, E B ) be any two graphs with universe U . The
distance between A and B isdist(A, B) :=|{(x1 , x2 ) | x1 , x2 ∈ U and E A (x1 , x2 ) ⊕ E B (x1 , x2 )}|.
n2Note that by definition, #(A) = #(B) = n. The dist distance is the fractionof edges on which the two graphs disagree. This is the dense graph model introduced by Goldreich et al. [8] and is essentially based on the adjacency matrix
representation. The dist distance generalizes to properties in the following way.
Definition 3. Let P ⊆ G be a property of graphs and let A ∈ G n be a graphwith n vertices. Then,dist(A, P ) :=min

A0 ∈G n ∩P

dist(A, A0 ) .

4

C. Jordan and T. Zeugmann

We are now able to define property testing itself. The following definitions
are typical, but we will also mention several variations.
Definition 4. An ε-tester for property P is a randomized algorithm given an
oracle which answers queries for the universe size and queries for the existenceof edges connecting given nodes in a graph A. The tester must accept with probability at least 2/3 if A has P and must reject with probability at least 2/3 ifdist(A, P ) ≥ ε.
Definition 5. A property P is testable if for every ε > 0 there is an ε-tester
for P making a number of queries which is bounded from above by a function
depending only on ε.
We allow different ε-testers for each ε > 0 and our definitions are therefore non-uniform. The uniform case is strictly more difficult (see, e.g., Alon andShapira [3]). We are interested in proving untestability, and our results holdeven in the non-uniform case. In oblivious testing (see Alon and Shapira [2]),the testers are not given access to the size of the universe. Again, our results holdin the more general case where the testers may make decisions based on the sizeof the universe. In a similar way, the number of loops in a graph is asymptotically insignificant compared to the number of possible non-loops. Modifying thedefinition of distance to account for this makes testing strictly more difficult (seeJordan and Zeugmann [10]) and so we use the more general definition above.
However, the (possible) loops seem to affect the notion of indistinguishability
defined by Alon et al. [1]. We use the following modification of Definition 2.
Definition 6. Let n ∈ N and let U be any universe such that |U | = n. Furthermore, let A = (U, E A ) and B = (U, E B ) be any two graphs with universe U . For
notational convenience, let
d1 (A, B) :=|{x | x ∈ U and E A (x, x) ⊕ E B (x, x)}|, andn|{(x1 , x2 ) | x1 , x2 ∈ U, x1 6= x2 , and E A (x1 , x2 ) ⊕ E B (x1 , x2 )}|.
n2
The mr-distance between A and B is
d2 (A, B) :=mrdist(A, B) := max {d1 (A, B), d2 (A, B)} .
Again, note that #(A) = #(B) = n. Although the number of loops is asymptotically insignificant, a tester can easily restrict its queries to the form (x, x)
and distinguish between graphs that differ only in loops. Definition 6 is a special case of a definition from Jordan and Zeugmann [10], and mrdist abbreviates“maximum relational distance.” We use the following simple variation of indistinguishability for graphs that may contain loops.
Definition 7. Two properties P and Q of graphs are indistinguishable if they
are closed under isomorphisms and for every ε > 0 there exists an Nε such thatfor any graph A with universe of size n ≥ Nε , if A has P then mrdist(A, Q) ≤ ε
and if A has Q then mrdist(A, P ) ≤ ε.

Untestable Properties Expressible with Four First-Order Quantifiers

5

The important fact to note is that indistinguishability preserves testability.
The proof of the following theorem is analogous to that given in Alon et al. [1].
Theorem 1. If P and Q are indistinguishable, then P is testable if and only if
Q is testable.
Our classification definitions are from Börger et al. [5] except that we omit
function symbols. We omit a detailed discussion, but the following is for completeness. Let Π be a string over the four-character alphabet {∃, ∃∗ , ∀, ∀∗ }. Then[Π, (0, 1)]= is the set of sentences in prenex normal form which satisfy the following conditions:
1. The quantifier prefix is contained in the language specified by the regularexpression Π.
2. There are zero (0) monadic predicate symbols.
3. In addition to the equality predicate (=), there is at most one (1) binary
predicate symbol.
4. There are no other predicate symbols.
That is, [Π, (0, 1)]= is the set of sentences in the logic that we have defined above
whose quantifier prefixes in prenex normal form match Π.

3

An Untestable Property

We will begin by defining property P , which is essentially the graph isomorphism
problem for undirected loop-free graphs encoded in directed graphs that may
contain loops. We will begin by showing in Lemma 1 that P is indistinguishable
from property Pf (cf. Definition 9) which is expressible in any of the prefix
vocabulary classes mentioned in Theorem 2. We will then show that P is not
testable. Indistinguishability preserves testability and so this implies that Pf isalso untestable, which will suffice to show the following theorem.
Theorem 2. The following prefix classes are not testable:
1.
2.
3.
4.

[∀∃∀∃, (0, 1)]=[∀∃∀2 , (0, 1)]=[∀2 ∃∀, (0, 1)]=[∀3 ∃, (0, 1)]=

We define property P as follows. First, a graph that has property P must
consist of an even number of vertices, of which exactly half have loops. The
subgraph induced by the vertices with loops must be isomorphic to that inducedby the vertices without loops, ignoring all loops, and there must be no edges
connecting the vertices with loops to those without loops. Finally, all edges
must be undirected (i.e., an edge from x to y implies an edge from y to x). We
refer to such undirected edges as paired edges.
Definition 8. A graph G ∈ G n has P iff the following conditions are satisfied:6

C. Jordan and T. Zeugmann

1. For some s, n = 2s.
2. There are exactly s vertices x satisfying E(x, x). We will refer to the set ofsuch vertices as H1 and to the remaining s vertices as H2 .
3. The substructure induced by H1 is isomorphic to that induced by H2 when
all loops are removed. That is, there is a bijection f from H1 to H2 such thatfor distinct x, y ∈ H1 , it is true that G |= E(x, y) iff G |= E(f (x), f (y)).
4. There are no edges between H1 and H2 .
5. All edges are paired.
Graph isomorphism is not directly expressible in first-order logic, and so we
use the following encoding where the bijection f is made explicit by adding nedges between H1 and H2 .
Definition 9. A graph G ∈ G n has Pf iff the following conditions are satisfied:
1. For every vertex x, if E(x, x) then there is an edge from x to exactly one ysuch that ¬E(y, y).
2. For every vertex x, if ¬E(x, x) then there is an edge from x to exactly one
y such that E(y, y).
3. For all vertices x and y, E(x, y) iff E(y, x).
4. For all pairwise distinct vertices x1 , x2 , x3 , x4 , if E(x1 , x1 ), ¬E(x2 , x2 ),E(x3 , x3 ), ¬E(x4 , x4 ), E(x1 , x2 ) and E(x3 , x4 ), then E(x1 , x3 ) iff E(x2 , x4 ).
Expressing Conditions 1 and 2 as “there is at most one such y” and “there is
at least one such y,” Pf can be expressed in each of the classes [∀∃∀∃, (0, 1)]= ,[∀∃∀2 , (0, 1)]= , [∀2 ∃∀, (0, 1)]= and [∀3 ∃, (0, 1)]= .
For example, in the class [∀3 ∃, (0, 1)]= , we can express Pf byh∀x1 ∀x3 ∀x4 ∃x2 :
(E(x1 , x1 ) ↔ ¬E(x2 , x2 )) ∧ E(x1 , x2 ) ∧(E(x1 , x1 ) ↔ ¬E(x3 , x3 )) ∧ (E(x3 , x3 ) ↔ ¬E(x4 , x4 )) ∧
E(x1 , x3 ) ∧ E(x1 , x4 ) → x3 = x4 ∧E(x1 , x3 ) → E(x3 , x1 ) ∧[E(x1 , x1 ) ∧ E(x3 , x3 ) ∧ x1 6= x3 ∧ ¬E(x4 , x4 ) ∧ E(x3 , x4 )] →i(¬E(x2 , x2 ) ∧ E(x1 , x2 ) ∧ (E(x1 , x3 ) ↔ E(x2 , x4 ))) .
To express Pf with prefixes ∀2 ∃∀ and ∀∃∀2 , it suffices to reorder the quantifiers (keeping x2 existential and x1 first). The prefix ∀∃∀∃ requires a few additional modifications.
The two properties P and Pf differ only in the edges which make the isomorphism explicit in Pf but are forbidden in P . There are at most n such edges,
none of which are loops. This suffices to prove the following.
Lemma 1. Properties P and Pf are indistinguishable.

Untestable Properties Expressible with Four First-Order Quantifiers

7

Proof. Let ε > 0 be arbitrary and let Nε = ε−1 . Assume that G is a structurethat has property P and that #(G) > Nε . We will show that mrdist(G, Pf ) < ε.
Structure G has P and so there is a bijection f satisfying Condition 3 ofDefinition 8. For all x ∈ H1 , we add the edges E(x, f (x)) and E(f (x), x) andcall the result G0 . Property Pf differs from P only in that the isomorphism ismade explicit by the edges connecting loops and non-loops, and so G0 has Pf .
Indeed, it satisfies Conditions 1 and 2 of Definition 9 because G had no edges
between loops and non-loops and we have connected each to exactly one of theother, following the bijection f . Next, G0 satisfies Condition 3 of Definition 9
because G satisfied Condition 5 of Definition 8 and we added only paired edges.
Finally, G0 satisfies Condition 4 of Definition 9 because the edges between loops
and non-loops follow the isomorphism f from Condition 3 of Definition 8.
We have added exactly n (directed) edges, none of which are loops and so
mrdist(G, P ) ≤ mrdist(G, G0 ) = 0 + n/n2 < ε, where the inequality holds forn > Nε . The converse is analogous; given a G that has property Pf , we simply
remove the n edges between loops and non-loops after using them to construct
the isomorphism f .
tuProperties P and Pf are indistinguishable. Testability is preserved by indistinguishability (cf. Theorem 1) and thus showing that P is not testable suffices
to prove that Pf is not testable (and therefore Theorem 2). The proof closely
follows that of Alon et al. [1]. The crucial lemma is the following, a combinationof Lemmata 7.3 and 7.4 from Alon et al. [1]. We use countH (T ) to refer to thenumber of times that a graph T occurs as an induced subgraph in H. A bipartite
graph is a graph where we can partition the vertices into two sets H1 and H2 suchthat there are no edges “internal” to the partitions. That is, for all x1 , y1 ∈ H1
and x2 , y2 ∈ H2 , ¬E(x1 , y1 ) and ¬E(x2 , y2 ). See Jordan and Zeugmann [9] foran explicit proof of Lemma 2, which is technical and long.
Lemma 2 (Alon et al. [1]). There exists a constant ε0 > 0 such that for every
D ∈ N, there exist two undirected bipartite graphs H = H(D) and H 0 = H 0 (D)satisfying the following conditions.
1. Both H and H 0 have a bipartition into classes U1 and U2 , each of size t.
2. In both H and H 0 , for all subgraphs X with size t/3 ≤ #(X) ≤ t, there are
more than t2 /18 undirected edges between X and the remaining part of thegraph.
3. The minimum degree of both H and H 0 is at least t/3.
4. dist(H, H 0 ) ≥ ε0 .
5. For all D-element graphs T , countH (T ) = countH 0 (T ).
It is worth noting that the above is for undirected, loop-free graphs. However,bipartite graphs never have loops and “undirected” in our setting results inpaired edges. It is easy to show that if two structures agree on the counts for all
size D induced subgraphs, they agree on the counts for all induced subgraphs ofsize at most D. This is done by applying Lemma 3 inductively.

8

C. Jordan and T. Zeugmann

Lemma 3. Let H and H 0 be two graphs, both of size s, and let 2 < D ≤ s. If
for every graph T of size D, countH (T ) = countH 0 (T ), then for every graph T 0
of size D − 1, countH (T 0 ) = countH 0 (T 0 ).
Proof. Assume H and H 0 satisfy the initial conditions of Lemma 3, but that
there exists a T 0 of size D − 1 such that countH (T 0 ) 6= countH 0 (T 0 ). Let C ={T | #(T ) = DPand T contains T 0 as an induced subgraph}.
Note P
that T ∈C countH (T ) countT (T 0 ) = countH (T 0 )(s − D + 1) and likewise for T ∈C countH 0 (T ) countT (T 0 ). We have assumed that H and H 0 satisfy
countH (T ) = countH 0 (T ) for T ∈ C, but countH (T 0 ) 6= countH 0 (T 0 ), giving acontradiction and the Lemma follows.
tuLemma 4. Property P is not testable.
Proof. Assume that P is testable. Then, there exists an ε-tester for
ε := min {ε0 /8, 1/144} ,where ε0 is the constant from Lemma 2. We can assume without loss of generalitythat the tester queries all edges in a random sample of D := D(ε) vertices.
Consider the graph G which contains two copies of the H = H(D) from
Lemma 2, where one of the copies is marked by loops on each vertex and there
are no edges between the copies. This graph has property P , and so the tester
must accept it with probability at least 2/3. Next, consider the graph G0 whichcontains one copy of H marked by loops and one copy of H 0 , again where
there are no edges between the two (induced) subgraphs. Graph G0 is such that
dist(G0 , P ) ≥ ε (cf. Lemma 5) and so it must be rejected with probability atleast 2/3. Both G and G0 consist of two bipartite graphs, each of which has abipartition into two classes of size t, and so #(G) = #(G0 ) = 4t.
However, G and G0 both contain exactly the same number of each induced
subgraph with D vertices. This is because both have loops on exactly half ofthe vertices and the two halves are not connected by any edges. Some of the Dvertices must be in the first copy of H and the others in the second H (resp. H 0 ).
By Lemma 3, H and H 0 contain the same number of each induced subgraph withsize at most D. The tester therefore obtains any fixed sample with the sameprobability in G and G0 and is unable to distinguish between them. Hence, it isunable to accept G with probability 2/3 and also reject G0 with probability 2/3.
This completes the proof, taking into account Lemma 5 below.
tuRecall that testing is easiest under the dist definition, and so Lemma 4 also
implies P is not testable under other definitions.
Lemma 5. The graph G0 is such that dist(G0 , P ) ≥ ε.
Proof. Suppose that dist(G0 , P ) < ε. Then, there is an M ∈ P such that
dist(G0 , M ) < ε. Let M1 be the set of vertices with loops in M and let M2 bethe set of vertices without loops. We will refer to the subgraph induced by thevertices with loops in G0 as H and to that induced by those without loops as H 0 .

Untestable Properties Expressible with Four First-Order Quantifiers

9

Without loss of generality, assume that |M1 ∩H| ≥ |M1 ∩H 0 |. Then, |M1 ∩H| ≥ t.
We let α1 be the set M1 \H and α2 be M2 \H 0 . Note that |α1 | = |α2 | and |α1 | ≤ tbecause |M1 ∩ H| ≥ t.
Informally, M is formed by moving the vertices α1 from H 0 to H and thevertices α2 from H to H 0 , and then possibly making other changes. There arethree cases, which we will consider in order.
1. |α1 | = 0.
2. |α1 | ≥ t/3.
3. 0 < |α1 | < t/3.
If |α1 | = 0, then we can construct M from G0 without exchanging vertices
between H and H 0 , and in particular, construct H 0 from H (ignoring loops), bymaking less than ε(4t)2 modifications. However, dist(H, H 0 ) ≥ ε0 by Lemma 2
and so this must require at least ε0 (2t)2 modifications. By definition, ε < ε0 /4
so ε(4t)2 < ε0 (2t)2 . The first case is therefore not possible.
Recall that |α1 | ≤ t. If |α1 | ≥ t/3, then by Condition 2 of Lemma 2 there
exists at least t2 /18 undirected edges between α1 and H 0 \α1 and between α2and H\α2 . All of these edges must be removed to satisfy P because each would
connect a vertex with a loop to a vertex without a loop. Therefore,dist(G0 , M ) ≥4t2 /18= 1/72 .
(4t)2But, ε < 1/72 and so the second case is not possible.
Therefore, it must be that 0 < |α1 | < t/3. Here, we will show that it must be
the case that α1 and α2 are relatively far apart. If they are not far apart, then it
is possible to modify them instead of swapping them. This essentially results inthe first case considered above. Condition 3 of Lemma 2 requires that each vertex
has relatively high degree. These edges can be either internal to α1 (resp. α2 )or connecting α1 (α2 ) with H 0 \α1 (H\α2 ). If α1 and α2 are relatively far apart,
then we will see that this forces too many edges “outside” of α1 (resp. α2 ),resulting in a similar situation to the second case considered above.
We have assumed that dist(G0 , M ) < ε and that we can construct M from0
G by making less than ε(4t)2 modifications if we move α1 to H and α2 to H 0 .
This entails the following modifications.
1. Removing all edges connecting α1 to H 0 \α1 .
2. Removing all edges connecting α2 to H\α2 .
3. Adding any required edges between α1 and H\α2 .
4. Adding any required edges between α2 and H 0 \α1 .
5. Changing α1 , α2 , H\α2 and H 0 \α1 to their final forms.
We can assume that the total number of modifications is less than ε(4t)2 .
It must be that dist(α1 , α2 )|α1 |2 /(4t)2 + ε ≥ ε0 /4. If this does not hold, thenwe could first modify α1 to make it identical to α2 and then make H 0 identicalto M2 . Next, M2 is identical to M1 , which we could make identical to H. This

10

C. Jordan and T. Zeugmann

would require less than ε0 (2t)2 modifications, which would violate Lemma 2.
Therefore,
16(ε0 /4 − ε)t2
dist(α1 , α2 ) ≥.
(1)|α1 |2
If both α1 and α2 are complete graphs then they cannot be far apart. Given
that all vertices in α1 (α2 is analogous) have degree at least t/3, then there mustbe at least|α1 |(t/3 − |α1 | + 1) + 2r
edges connecting α1 to H 0 \α1 , where r is the number of edges internal to α1that must be omitted to satisfy (1). The simple lower bound on r, the numberof edges needed for two graphs with at most r edges to be dist(α1 , α2 )-far, that
follows from dist(α1 , α2 ) ≤ 2r/|α1 |2 is sufficient. Finally, combining this with
Inequality (1) yieldsr ≥ 8(ε0 /4 − ε)t2 .
(2)
The number of edges connecting α1 to H 0 \α1 is therefore, by (2), at least|α1 |(t/3 − |α1 | + 1) + 16(ε0 /4 − ε)t2 ≥ 16(ε0 /4 − ε)t2 .
All of these edges must be removed to move α1 (resp. α2 ), and sodist(G0 , M ) ≥ε016(ε0 /4 − ε)t2
=
− ε.
2
(4t)
4

We have defined ε ≤ ε0 /8 and so dist(G0 , M ) ≥ ε, a contradiction.
The cases are exhausted and so dist(G0 , P ) ≥ ε as desired.

4tuConclusion

Property testing is an application of induction (in the philosophy of science
sense), in which we obtain a small, random sample of a structure and seek todetermine whether the structure has a desired property or is far from having theproperty. We have considered the classification problem for testability, wherein
we classify the prefix vocabulary classes of first-order logic according to theirtestability. In particular, we simplified the untestable property, expressible withquantifier prefix ∀12 ∃5 , from Alon et al. [1] for the case of directed graphs which
may contain loops. This implies that there exists an untestable property expressible with quantifier prefixes ∀∃∀∃, ∀∃∀2 , ∀2 ∃∀ and ∀3 ∃.
In the classification problem for testability, it is necessary to determine theminimal untestable classes. Informally, we seek the untestable properties thatare easiest to express. Jordan and Zeugmann [10] showed that classes with (atmost) one universal quantifier are testable, and so there are at least two minimal
untestable classes which have either two or three universal quantifiers.
The current classification for testability closely resembles the classification
for the finite model property (see, e.g., Section 6.5 of Börger et al. [5]). The“minimal” classes without this property (i.e., those with infinity axioms) are[∀3 ∃, (0, 1)] and [∀∃∀, (0, 1)], while the case of [∀2 ∃, (0, 1)]= is apparently open.
It would be particularly interesting to determine the testability of these classes.

Untestable Properties Expressible with Four First-Order Quantifiers

11

Acknowledgments We would like to thank an anonymous referee for significantly improving Theorem 2 by eliminating one variable from each prefix, adding∀∃∀∃, and also for simplifying the example following Definition 9.

References[1] Alon, N., Fischer, E., Krivelevich, M., Szegedy, M.: Efficient testing of large
graphs. Combinatorica 20(4) (2000) 451–476[2] Alon, N., Shapira, A.: A characterization of the (natural) graph properties testablewith one-sided error. SIAM J. Comput. 37(6) (2008) 1703–1727[3] Alon, N., Shapira, A.: A separation theorem in property testing. Combinatorica
28(3) (2008) 261–281[4] Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications tonumerical problems. J. of Comput. Syst. Sci. 47(3) (1993) 549–595[5] Börger, E., Grädel, E., Gurevich, Y.: The Classical Decision Problem. SpringerVerlag (1997)[6] Diestel, R.: Graph Theory. third edn. Springer (2006)[7] Enderton, H.B.: A Mathematical Introduction to Logic. second edn. Academic
Press (2000)[8] Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection tolearning and approximation. J. ACM 45(4) (1998) 653–750[9] Jordan, C., Zeugmann, T.: Contributions to the classification for testability:
Four universal and one existential quantifier. Technical Report TCS-TR-A-09-39,
Hokkaido University, Division of Computer Science (November 2009)[10] Jordan, C., Zeugmann, T.: Relational properties expressible with one universal
quantifier are testable. In Watanabe, O., Zeugmann, T., eds.: Stochastic Algorithms: Foundations and Applications, 5th International Symposium, SAGA
2009, Sapporo, Japan, October 2009, Proceedings. Volume 5792 of Lecture Notes
in Computer Science., Springer (2009) 141 – 155[11] Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2) (1996) 252–271