博士論

文Testable and Untestable Classes of First-Order Logic（一階述語論理の検査可能・不可能なサブクラスについて）

北海道大学大学院情報科学研究科

Charles Jordan

Testable and Untestable Classes of First-Order Logic
Charles Jordan

Submitted in partial fulfillment of the requirements for the degree ofDoctor of Philosophy
in the field of
Computer Scienceat theGraduate School of Information Science and Technology,
Hokkaido University

March 2012Abstract
Property testing is essentially a kind of constant-time randomized approximation. Alon et al. [3] were the first to consider the idea of testing properties expressible in syntactic subclasses of first-order logic. They proved the testabilityof all properties of undirected, loop-free graphs expressible with quantifier prefix∃∗ ∀∗ , and also that there exist untestable properties of undirected, loop-free graphs
expressible with quantifier prefix ∀∗ ∃∗ .
In this dissertation, we continue the study of testing subclasses of first-orderlogic. In particular, we focus on the classification of prefix-vocabulary classes, orclasses defined by quantifier prefix and vocabulary, according to their testability.
The main results are as follows. First, we develop a framework for relational
property testing including variations corresponding to the diﬀerent models considered in the literature for non-uniform hypergraph testing. We then use thisframework to prove the following.
1. All (relational) properties expressible by formulae in Ackermann’s class withequality ([∃∗ ∀∃∗ , all ]= ) are testable in all of our models.
2. All (relational) properties expressible in Ramsey’s class ([∃∗ ∀∗ , all ]= ) aretestable in all of our models. This extends the result by Alon et al. [3] to thefull class.

iAbstract
3. There exist graph properties expressible in the class [∀3 ∃, (0, 1)]= that areuntestable in all of our models. This considerably sharpens the untestableclass of Alon et al. [3].
4. There exist graph properties expressible in the class [∀∃∀, (0, 1)]= (the KahrMoore-Wang prefix) that are untestable in all of our models.
5. There exist graph properties expressible in the class [∀∃∀, (0, 1)] (without
equality) that are untestable in (at least) one of our models.

ii

概要
近年は大規模なデータセットが増え、情報爆発の時代であると言われている。ある種のデータセットでは、その正確なサイズが不明であり、全てのデータを一瞥することすら困難なほど巨大である。例えば、インターネットはそのサイズが刻々と変化しており、また、様々なサーバに分散されている全ての情報にアクセスすることは現実的ではない。このような情報爆発に対応するため、新しいアルゴリ
ズムや手法が必要になってきている。
入力データ長に対してその線形時間がなければほとんど何も計算できないと考えられがちだが、実際には定数時間だけでも計算できるものが多数ある。その一つがプロパティー検査である。プロパティー検査とは、大規模なグラフやデータベースからランダムサンプリングを行い、そのごく僅かなサンプルを元に、確率的な近似アルゴリズムを用いて高速に結論を出力するタイプの検査手法である。プロパティー検査によって、NP 完全問題の一部も検査可能であると知られている。

Lovász [50] がいうように、プロパティー検査は帰納法の応用であると考えられる。
プロパティー検査は、形式的検証の分野において、計算量の高い検証を行う前の高速なフィルターとして提案された。形式的検証では、ユーザーが何かしら形式
論理等の形式言語で目的のプロパティーを定義し、コンピュータはシステムがそれを満たしているかどうかを計算する。このように形式言語で定義されるプロパ

iii

概要
ティーの検査は自然な課題である。また、大規模な関係データベースへの応用も考えられる。その場合は、ユーザーが SQL 等でクエリーを書いてコンピュータが自動的に効率的の良い確率的な近似を行えることが望ましい。SQL は一階述語論理の拡張に近いこと (Libkin [49] 等参考) や、形式的検証も形式論理でプロパティーを定義することからも、論理式の検査が重要になる。
本研究では、一階述語論理のプロパティー検査について研究する。一階述語論理
で定義できるプロパティーには検査可能と検査不可能なものが存在する。したがって、検査できるサブクラスとできないサブクラスにプロパティーを分類することが目的である。この課題は、Alon ら [3] が初めて研究を行い、一階述語論理を二つのクラスに分け、その一方は検査可能であり他方が検査不可能であると証明している。しかしながら、その結果はループなしの無向グラフに限っている。Alon
らの結果は深くて影響力もあるが、一階述語論理をより細かく分類するとより良い結果を導くことが可能である。
本研究の目的は、一階述語論理について、検査可能および検査不可能な文法的サブクラス（Börger ら [15] のように定義するもの）の完全な分類を行うことである。本研究の成果はゲーデルクラスを除けば完全な分類になっている。本研究の主な成果は、以下の通りである。

1. グラフプロパティー検査やハイパーグラフプロパティー検査の拡張である関係プロパティー検査を提案している。また、従来のモデルとの関係を明らかにし、いくつかのバリエーションも提案している。さらに、それぞれのバリ
エーションの差を明らかにし、関係プロパティー検査を元にしたプロパティー
検査の分類問題の定義を行っている。

2. 関係プロパティー検査において、いくつかの基本的な成果を証明している。
iv

概要
本研究では、この成果を何回も応用しているため、まとめて証明している。

3. Alon ら [3] が検査可能だと証明しているクラスを、ループなしの無向グラフ
から関係ストラクチャーへ拡張し、ラムゼイクラスという一階述語論理の古典的に有名なサブクラスが全て検査可能であることを証明している。検査可能とはバリエーションによらないで、どれを使っても検査可能である。この成果は Austin と Tao [11] が証明しているハイパーグラフ理論の複雑な成果を応用している。

4. 等号ありのアッカーマンクラスという一階述語論理の古典的に有名なサブク
ラスが全て検査可能であることを証明している。こちらの証明はモデル理論の議論からできている。

5. Alon ら [3] が検査不可能だと証明しているクラスのより強い成果を証明している。Alon らの証明では、量化子が 17 個あれば（パターンによって）検査不可能なプロパティーを定義できることが示されている。本研究の成果では、

Alon らと同じパターンで 4 個でも足りることを証明している。この証明は、Alon らが証明しているグラフ理論の定理を応用している。
6. Kahr-Moore-Wang クラスという一階述語論理の古典的に有名なサブクラスが検査不可能だと証明している。これは検査不可能性として最小クラスの一つである。この成果から、量化子が 3 個あるとこのパターンで検査不可能なものを表すことができると分かる。量化子が 2 個以下だと上の成果から検査可能だと分かるため、検査不可能なプロパティーを一階述語論理で定義するには量化子の必要充分な数は 3 であると分かる。この証明は、Alon ら [2] が示した、ブール関数の同型問題が検査不可能であることを証明するためのア
イディアを応用している。

v

概要

7. エコールなしの Kahr-Moore-Wang クラスは、検査不可能なプロパティーを含むことを証明している。ただし、この成果においては、関係プロパティー
検査のバリエーションに限る。すなわち、普段のバリエーションでは検査不可能だが、違うバリエーションでは検査可能かどうかは未だ証明していない。
形式的検証等への応用を考えると、ユーザーが定義するプロパティーを自動的に検査するために、コンピュータが与えられた論理式から検査アルゴリズムを自動的に作成ことが必要である。本研究で検査可能であると証明しているクラスについては、検査アルゴリズムを論理式から作る方法も同時に提案している。したがって、ユーザが与えた論理式から、自動的に定数時間の確率的近似を行うシス
テムを構築することが可能である。
本研究の成果を得るために、形式論理とモデル理論、グラフとハイパーグラフ
理論、ブール関数の理論等の道具を応用している。

vi

Contents
1
1.1

1.2
2

Introduction

1

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.1.1

Previous Work on the Classification . . . . . . . . . . . . . .

5Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7Preliminaries

10

2.1

Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2

Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3

Property Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3

2.3.1

Distance Measures . . . . . . . . . . . . . . . . . . . . . . . 16

2.3.2

Testing Definitions . . . . . . . . . . . . . . . . . . . . . . . 20

Basic Results

23

3.1

Testing is Hardest in Minimal Vocabularies . . . . . . . . . . . . . . 23

3.2

Comparing Models of Testability . . . . . . . . . . . . . . . . . . . 24
3.2.1

Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . 25

3.3

Indistinguishability . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.4

Yao’s Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4.1

Proof of Principle 1 . . . . . . . . . . . . . . . . . . . . . . . 33
vii

Contents
3.5
4

Testable Classes

Ackermann’s Class with Equality . . . . . . . . . . . . . . . . . . . 39

4.2

Ramsey’s Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.3

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Untestable Classes

5.1

5.2

64

Untestable Properties in [∀3 ∃, (0, 1)]= . . . . . . . . . . . . . . . . . 64
5.1.1

Proof of Lemma 16 . . . . . . . . . . . . . . . . . . . . . . . 69

5.1.2

Completing the Proof of Theorem 8 . . . . . . . . . . . . . . 76

The Kahr-Moore-Wang Class with Equality . . . . . . . . . . . . . 81
5.2.1

From Four to Three Quantifiers . . . . . . . . . . . . . . . . 82

5.2.2

Proof of Theorem 9 . . . . . . . . . . . . . . . . . . . . . . . 83

5.3

Untestable Classes without Equality . . . . . . . . . . . . . . . . . . 89

5.4

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
Conclusions

Bibliography

viii

39

4.1

5

6

Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

100
104

List of Figures
2.1

Comparison of distance measures dist, rdist and mrdist. . . . . . . . 19

2.2

A property tester. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.1

A sketch of the new structure . . . . . . . . . . . . . . . . . . . . . 43

5.1

Properties Pb , Pe and Pf . . . . . . . . . . . . . . . . . . . . . . . . 82ix

Acknowledgments
This dissertation would not have been written without the help and support ofmany people. I am especially grateful to my advisor, Prof. Thomas Zeugmann,for his endless support and constant discussions over the past six years, and also
for first introducing me to the paper that eventually led to this thesis. His love ofresearch and science has been inspiring.
I am thankful to Prof. Shin-ichi Minato for his generous help, continuous since
the day I first visited the Laboratory for Algorithmics, and also for providing accessto countless opportunities via the ERATO Minato project.
I am indebted to Prof. Hiroki Arimura for his guidance over the past six years,
and also for the generous support of the GCOE-NGIT project. His generosity has
allowed me to attend international conferences, visit the University of Latvia andspend a semester at the University of Massachusetts, Amherst.
I appreciate the help of Prof. Takuya Kida, most recently in proofreading theJapanese abstract for this dissertation.
Prof. Neil Immerman first introduced me to the beauty of descriptive complexity and finite model theory when I was an undergraduate at the University of
Massachusetts, Amherst. I am thankful to him for allowing me to take 741 as anundergraduate, and look forward to the future of descriptive programming.
I am thankful to Prof. Rūsiņš Freivalds, Prof. Beate Bollig and Neil Immerman
for hosting me as a visitor over the past years.
I would not have been able to complete this dissertation without the expert
help of Sachiko Soma, who ably saved me from being paralyzed by paperwork on
countless occasions. I am also grateful to the GCOE staﬀ, in particular Ayami
Yonemoto and Miyuki Yoshimura, for their understanding and assistance over the
past three years.
I appreciate the wonderful environment generously provided by the Graduate
School of Information Science and Technology at Hokkaido University. The amazing mountain view from my oﬃce has been inspirational. I am especially indebted
to the Japan Society for the Promotion of Science, which generously supported
me for three years with a research fellowship. I am very thankful to MEXT for
Grant No. 2100195209, which has supported my research over the past years, andalso for earlier scholarships.
I am thankful to Miki Sakurada for her patience and for keeping me sane over the
past few years. Finally, I will always be indebted to my family for their unfailinglove and support, for nurturing in me a love of understanding the world, and for
putting up with me being so far away for so long.

Chapter 1
Introduction
Property testing is an application of inductive reasoning. Given a large object, for example a massive graph or database, we wish to state some conclusion
about the entire structure after examining only a small, randomly selected sample. Lovász [50] has described it as the “third reincarnation” of this kind of generalapproach, after statistics and machine learning.
The astonishing growth in massive data-sets requires us to find new techniques
and approaches for much of the computation that we want to do. In fact, for manylarge data-sets of interest (e.g., the Internet), we cannot even determine the precise
size of the data. Such objects are generally stored remotely, and there is a nontrivial cost for examining particular bits. It may be impractical to move beyond
constant time if we cannot even determine the size of the data we are interested
in, and the sheer amount of data renders many common algorithms impractical.
Given the (time) cost of accessing remote data, we may also wish to minimize thenumber of bits that we examine.
At first, it may seem that linear time is a minimum requirement for meaningful1

CHAPTER 1. INTRODUCTION
computation; after all, how can we compute a property of some data that we
don’t have time to look at? Surprisingly, there is an entire world of interesting
computation that can be done in sub-linear time, and even in constant time.
Informally1 , we call a property testable if we can approximate it as closely
as we like in constant time. In this thesis, we focus on testing properties thatare expressible in first-order logic. The focus on queries expressed in a formal
languages is quite natural; in databases, for example, users generally make queries
against massive objects in a formal query language (e.g., SQL). Given the “unusualeﬀectiveness” of logic in computer science [35], it is natural to focus (in particular)
on first-order properties.
This thesis indicates the possibility of a system that takes queries in a restricted
formal language (e.g., the restricted syntactic fragments of first-order logic thatare testable), and automatically generates probabilistically approximate answers tothese queries in constant time. Such a system is also natural from the perspectiveof formal verification (where this general approach originated, see Section 1.1).
There, users generally specify properties of systems they wish to verify by writing(Boolean) queries in a logic. Given the computational demands of verification, avery fast (constant-time) randomized approximate verification could be useful by
allowing us to quickly reject very bad systems.
The idea of testing syntactic subclasses of first-order logic was first-consideredin an influential paper by Alon et al. [3] (see Section 1.1 for a discussion of relatedwork), and this thesis builds upon the classification that began there. Here, we

1

2

See Section 2.3 for formal definitions.

1.1. RELATED WORK
prove a nearly-complete classification of prefix-vocabulary classes2 according totheir testability.
The thesis is structured as follows. We begin by introducing related work,
together with a brief history of property testing in Section 1.1. Then, we state themain results of this thesis in Section 1.2.
Chapter 2 focuses on definitions and other preliminaries. In Chapter 3, we provebasic, fundamental results about property testing that we will need for proofs inlater chapters. These basic results first appeared in [38, 43], and will also appear
in [42]. We consider testable classes in Chapter 4. The results in Section 4.1
first appeared in [38] in a preliminary form with two-sided error. The results in
Section 4.2 first appeared in [39].
We proceed to untestable classes in Chapter 5. The results in Section 5.1 first
appeared in [40]. These last three results will also appear as [42]. The results in
Section 5.2 first appeared in [41], while the results in Section 5.3 have not beenpreviously published.

1.1

Related Work

We begin with a brief history and overview of property testing. There is a recent
introduction to graph property testing by Goldreich [28], and two recent surveys
by Ron, one focusing on connections with learning theory [61] and one focusing on
the algorithmic techniques [62] used in testability. There are also earlier surveys,
including those by Ron [60] and the wonderfully-titled Fischer [19].
2

A prefix-vocabulary class is defined by the pattern of quantifiers and vocabulary, see Definition 3 in Section 2.2.

3

CHAPTER 1. INTRODUCTION
Property testing is a form of approximation where we trade accuracy for eﬃciency. It seems that de Leeuw et al. [47] was the first to formalize probabilistic machines. They showed that such machines cannot compute uncomputableproperties under reasonable assumptions. However, they mention the possibility
that probabilistic machines could be more eﬃcient than deterministic machines,
a topic which was then investigated by Gill [26]. An early example of such a result
is Freivalds’ [25] matrix multiplication checker.
The study of property testing itself began in program verification (see, e.g.,Blum et al. [14] as well as Rubinfeld and Sudan [63]). Goldreich et al. [29] firstconsidered the testability of graph properties in a seminal paper and showed theexistence of testable NP-complete properties. An approach using incidence lists
to represent bounded-degree graphs was introduced by Goldreich and Ron [27].
Parnas and Ron [55] generalized this approach and attempted to move away fromthe functional representation of structures. There has been a great deal of recent
work on graph property testing, see the survey by Alon and Shapira [7].
For other types of structures, Alon et al. [5] showed that the regular languages
are testable and that there exist untestable context-free languages. Chockler and
Kupferman [17] extended the positive result to the ω-regular languages.
There is also recent work on testing properties of (usually uniform) hypergraphs.
Fischer et al. [22] defined a general model that is roughly equivalent to one of ourmodels, namely Tr based on Definition 5 below, and showed that hypergraph partition problems are testable in this framework. Very recently, Austin and Tao [11]have shown that all hereditary properties3 of colored, directed, non-uniform hyper3

4

A hereditary property is one that is closed under taking induced substructures.

1.1. RELATED WORKgraphs are testable in a model that is roughly equivalent to another of our models,Tmr based on Definition 8 below.
Szemerédi’s regularity lemma (see, e.g., the survey by Rödl and Schacht [59])has been extremely influential in (dense) graph property testing and there has
been a great deal of work on recent extensions (see, e.g., [30, 58, 68]) of thislemma to hypergraphs. We are not aware of any extensions to non-uniform hypergraphs or finite (relational) structures, but are very interested in such topics. As
Alon et al. [3] noted, proofs of testability that avoid the regularity lemma often
result in better query complexity. We therefore prove testability directly when weknow how to.
Alon et al. [3] began a logical characterization of the testable (graph) properties,
see Subsection 1.1.1. Alon and Shapira [8] gave a characterization of a natural
subclass of the graph properties testable with one-sided error, which Rödl and
Schacht [57] generalized to hypergraphs. Alon et al. [4] showed a combinatorial
characterization of the graph properties testable with a constant number of queries.
It would be particularly interesting to consider extensions of this last result tohypergraphs or relational structures.

1.1.1

Previous Work on the Classification

We briefly outline prior work on the classification for testability before stating
our main results. We begin with monadic first-order logic. Löwenheim [51] provedthat satisfiability is decidable4 for monadic first-order logic, and McNaughton and4

A class is said to be decidable (for satisfiability) if, given an arbitrary formula from the class,one can decide if there exists a (possibly infinite) model satisfying the formula.

5

CHAPTER 1. INTRODUCTION
Papert [52] showed that it (with ordering and some arithmetic) characterizes thestar-free regular languages. The testability of this class is then implied by a resultof Alon et al. [5]. Using instead Büchi’s [16] result that monadic second-order logic
characterizes the regular languages, we get a parallel with Skolem’s [66] extensionof Löwenheim’s result to second-order logic. Of course, we are focused on thetestability of classes of first-order formulae.
Below, we use the classification notation that will be introduced formally in
Definition 3. Informally, we represent classes with a triple [Π, p]e , where Π denotes
the pattern of quantifiers allowed, the infinite sequence p denotes the maximum
number of permitted predicate symbols for each arity (we omit trailing zeros andall means that any number of predicate symbols with any arities are permitted),and e denotes whether = is allowed.
Skolem [67] also showed that [∀∗ ∃∗ , all ] is a reduction class5 . Alon et al. [3] foundan untestable graph property (essentially an encoding of graph isomorphism). In
particular, this property is expressible in [∀∗ ∃∗ , (0, 1)]= , and an examination of theproof reveals that a prefix of ∀12 ∃5 suﬃces.
The class [∃∗ ∀∗ , all ]= was first studied in a seminal paper by Ramsey [56], whoshowed that it is decidable as part of a stronger result characterizing its spectrum.
Alon et al. [3] showed that the restriction of Ramsey’s class to undirected loop-freegraphs (a restriction of [∃∗ ∀∗ , (0, 1)]= ) is testable.

5

A class is a reduction class if the satisfiability problem for first-order logic can be reduced tothe satisfiability problem for the class. These classes are therefore undecidable (for satisfiability).

6

1.2. RESULTS

1.2

Results

As mentioned above, Alon et al. [3] found an untestable property expressible
with seventeen quantifiers (∀12 ∃5 ). Although this is an impressive result, we mightwish to know whether it is optimal. More concretely, we would like to know theminimum number of universal quantifiers, as well as of existential quantifiers, required to express an untestable property. In addition, we would like to know theminimum total number of quantifiers needed to express an untestable property, as
it is not prima facie necessary that one can achieve these two minima simultaneously. Previous work by Alon et al. [3] implies upper bounds of twelve universal,
five existential and seventeen total quantifiers, and it is natural to ask if thesebounds can be improved. The following is an informal summary of our results
addressing this question.
Remark 1. The minimum number of quantifiers suﬃcient to express an untestableproperty in a first-order relational language is
1. Two universal quantifiers;
2. One existential quantifier;3. Three quantifiers in total.
These minima can be achieved in the vocabulary of directed graphs (i.e., one binary
relation).
We now introduce the main results of this thesis. First, we develop a framework
for relational property testing including variations corresponding to the diﬀerent

7CHAPTER 1. INTRODUCTION
models considered in the literature for non-uniform hypergraph6 testing. We use
this framework to prove the following.
1. All (relational) properties expressible by formulae in Ackermann’s class withequality ([∃∗ ∀∃∗ , all ]= ) are testable in all of our models.
2. All (relational) properties expressible in Ramsey’s class ([∃∗ ∀∗ , all ]= ) aretestable in all of our models. This extends the result by Alon et al. [3] to thefull class.
3. There exist graph properties expressible in the class [∀3 ∃, (0, 1)]= that areuntestable in all of our models. This considerably sharpens the untestableclass of Alon et al. [3].
4. There exist graph properties expressible in the class [∀∃∀, (0, 1)]= (the KahrMoore-Wang prefix) that are untestable in all of our models.
5. There exist graph properties expressible in the class [∀∃∀, (0, 1)] (without
equality) that are untestable in (at least) one of our models.
The last four results improve upon results of Alon et al. [3] in various ways, andthe second result relies on an application of a strong result by Austin and Tao [11].
In the notation introduced as Definition 3 below, the current classification for
testability is as follows.
• Testable classes
1. Monadic first-order logic: [all , (ω)]= .
6

A hypergraph is uniform if all edges have the same arity, and non-uniform if edges may havediﬀerent arities.

8

1.2. RESULTS
2. Ackermann’s class with equality: [∃∗ ∀∃∗ , all ]= .
3. Ramsey’s class: [∃∗ ∀∗ , all ]= .
• Untestable classes
1. [∀3 ∃, (0, 1)]= .
2. [∀∃∀, (0, 1)]= .
3. [∀∃∀, (0, 1)]7 .

7

Our proof for this class without equality is currently restricted to one of our models of
testability (Tmr based on Definition 8 below). We suspect that this class is also untestable in
the other models, however Tmr -style testing seems the most natural to us.

9Chapter 2
Preliminaries
In this chapter, we introduce our notation and definitions. We separate thesepreliminaries into sections related to basic, fundamental notions (e.g., sets, etc.),
logic (e.g., prefix vocabulary classes) and property testing. Much of this material
is standard and readers familiar with a particular section can safely skip it. However, we introduce several variations of property testing for relational structuresin Section 2.3 and encourage readers unfamiliar with our variations to review, atleast, their relationship with other models from the literature.

2.1

Fundamentals

Before proceeding further, we recall fundamental definitions and introduce notation for familiar objects such as natural numbers, sets and strings. Our definitions
are standard and readers familiar with this material can safely skip to Section 2.2.
The natural numbers are denoted by N and are the set of non-negative integers.
We denote the set of real numbers by R, although these are generally used for10

2.1. FUNDAMENTALS
probabilities and so we usually use only real numbers p ∈ [0, 1]. We use boldcharacters to denote vectors, for example x ∈ R3 . Vectors are row vectors unlessotherwise noted, we denote the transpose of a vector by xT . If x = (x1 , . . . , xa ) isa vector, we call xi the i-th component of x.
The empty set is denoted by ∅. If A and B are sets, then the union of A
and B is A ∪ B := {x | x ∈ A or x ∈ B} and the intersection of A and B is
A ∩ B := {x | x ∈ A and x ∈ B}. Furthermore, the set diﬀerence of A and B is
A\B := {x | x ∈ A and x ̸∈ B}. We generalize the union and intersection in theusual way,∪i≥0 Ai := A0 ∪ A1 ∪ . . . and∩i≥0 Ai := A0 ∩ A1 ∩ . . . respectively.

Set A is a subset of set B, written A ⊆ B if A\B = ∅. Set A is a proper subset
of set B, written A ⊂ B if A ⊆ B and B\A ̸= ∅. The cardinality of a set A is thenumber of elements in the set, written |A|.
The product of sets A and B is the set of ordered pairs, A × B := {(a, b) | a ∈A and b ∈ B}. The set of n-tuples of set A, written An is defined inductively as
follows. First, A1 = A. Then, An+1 = An × A. We will always omit the extra
parentheses, and so (1, 2, 3) denotes ((1, 2), 3). The number of elements in thetuple is the arity n. A predicate P with arity n of set A is any subset of An . If
x ∈ An , we will generally abbreviate the proposition x ∈ P with P (x).
An alphabet Σ is a set of symbols, and a string w over Σ is some sequence ofthe symbols in Σ. The empty string is denoted by λ. For example, {0, 1} is thealphabet of binary strings and 0100 is an example of such a string. We number
the positions in a string w from left to right with 0, 1, . . . , n − 1 where n is thelength of the string. Of course, the empty string λ has length 0. As usual, Σ∗ isthe free monoid of Σ and any subset L ⊆ Σ∗ of it is a language.
11

CHAPTER 2. PRELIMINARIES
Let w be a string over the alphabet Σ. The concatenation of strings u and v
is uv, while the product of two sets of strings L1 and L2 is L1 L2 := {uv | u ∈←←L1 and v ∈ L2 }. The reversal of w is written w. Position i of w corresponds to
←

←−

←

position n − 1 − i of w. Formally, λ = λ and aw = wa for a ∈ Σ.
We mention a number of well-known classes of languages, for example the classesof regular and context-free languages. Hopcroft and Ullman [36] is a well-known
introduction to these classes.
It is natural to represent a binary string w ∈ {0, 1}∗ as a pair {U, S} where U is
the finite set of bit positions 0, . . . , n − 11 and S ⊆ A is a monadic predicate. We
will define S(i) to mean that “bit position i of w is 1.”
Graphs provide another natural example and allow for representation as a pair,(V, E). Here V is the set of vertices and the edge set E ⊆ V 2 , a set of ordered pairsof V . The “names” of the vertices are not interesting to us, and we will identify
them as 0, . . . , n − 1 where n is the number of vertices. It is therefore natural torepresent a graph as a pair {V, E} where E is a binary predicate over V .
We will formalize these notions more exactly in the following section. In particular, one of our goals is a generalized notion of property testing instead of restricting
ourselves to fixed kinds of structures such as graphs and binary strings. The definitions in the following section are therefore necessarily abstractions of the ideas
above.

1

12

The universe is the empty set if w is the empty string.

2.2. LOGIC

2.2

Logic

We are particularly interested in the testability of classes of first-order logic, andso we need various definitions related to logic. We begin with vocabularies andstructures.
Definition 1. A (relational) vocabulary τ is a tuple of distinct predicate symbols
Ri together with their arities ai ,

τ := (R1a1 , . . . , Rsas ) .

Two examples (unique up to renaming) of vocabularies are τG := (E 2 ), thevocabulary of directed graphs and τS := (S 1 ), the vocabulary of binary strings.
Definition 2. A τ -structure A is an (s + 1)-tupleA
A := (U, RA
1 , . . . , Rs ) ,aiwhere U is a finite universe and each RA
is a predicate corresponding toi ⊆ U

the predicate symbol Ri of τ .
We generally identify U with the non-negative integers {0, . . . , n − 1} and use
n = #(A) for the size of the universe of a structure A. The universe U of a binary
string is the set of bit positions, which we will identify as {0, . . . , n − 1} from left
to right. For i ∈ U , we interpret i ∈ S as “bit i of the string is 1.” We generally
omit the superscript A from the relations and include it only when we wish to
explicitly distinguish the same relation in diﬀerent structures.

13

CHAPTER 2. PRELIMINARIESThe set of all τ -structures with universe size n is STRUC n (τ ) and the set ofall (finite) τ -structures is STRUC (τ ) :=∪n≥0 STRUCn(τ ). A property P of τ -structures is any subset of STRUC (τ ). We also call such properties τ -properties.
We say that a τ -structure A has P if A ∈ P .
We use language to refer to string properties and P to denote properties. We
refer to members of STRUC (τG ) as graphs, and note that our graphs are directed
and may contain loops.
A simple example of a graph property is the property of being a complete graph.
This property is the set of all (finite) graphs which have full edge relations, i.e.,
PK :=

∪

n≥0 {(Un , E

G) | Un = {0, . . . , n − 1}, E G = Un × Un }.

We use a predicate logic with equality that does not contain function symbols.
There are no ordering symbols such as ≤ or arithmetic relations such as PLUS.
The first-order logic of vocabulary τ is built from the atomic formulae xi = xj andRi (x1 , . . . , xai ) for variable symbols xj and predicate symbols Ri ∈ τ by using theBoolean connectives and quantifiers ∃ and ∀ in the usual way.
Formula φ of vocabulary τ is evaluated in the usual way and defines property
P := {A | A ∈ STRUC (τ ) and A |= φ}. Lower-case Greek letters φ, ψ and γ referto first-order formulae and x, y, and z to first-order variables.
Our classification definitions are from Börger et al. [15] except that we omit
function symbols. Essentially, we classify first-order sentences according to theirpattern of quantifiers and vocabulary.
Definition 3. A prefix vocabulary class is specified as [Π, p]e , where Π is a string
over the four-character alphabet {∃, ∀, ∃∗ , ∀∗ }, p is a sequence over N and the first
infinite ordinal ω, and e is ‘=’ or the empty string.
14

2.3. PROPERTY TESTING
We often use all as an abbreviation for the sequence (ω, ω, ω, . . .). Now that wehave defined the syntactic specification of a prefix vocabulary class, we define theclass specified by a triple [Π, p]e . Recall that a first-order sentence φ is in prenex
normal form if it is in the form φ := π1 x1 π2 x2 . . . πr xr : ψ, with quantifiers πi ,1 ≤ i ≤ r, and quantifier-free ψ. Such a φ is a member of the prefix vocabularyclass given by [Π, (p1 , p2 , . . .)]e , where pi ∈ N ∪ {ω} if
1. The string π1 π2 . . . πr is contained in the language specified by Π when Π isinterpreted as a regular expression2 .
2. If p is not all, at most pi distinct predicate symbols of arity i appear in ψ.
3. Equality (=) appears in ψ only if e is ‘=’.
Here, Π is the pattern of quantifiers, p is the maximum number of predicate
symbols of each arity and e determines whether or not the equality symbol ispermitted.

2.3

Property Testing

In property testing, the basic goal is to distinguish between structures that havea desired property and those that are far from having the property. Formalizing this requires a definition of “far”, and diﬀerent definitions results in diﬀerent
models of testing. We will give three diﬀerent distance measures, each based onprogressively refining a generalization of the dense graph testing model introduced
by Goldreich et al. [29].
Technically, we also let the empty string match expressions ∀ and ∃. See the discussion in
Börger et al. [15].
215CHAPTER 2. PRELIMINARIES

2.3.1

Distance Measures

Our first definition is dist(A, B), the fraction of tuples with diﬀering assignments
in A and B. We use ⊕ to denote exclusive-or.
Definition 4. Let A, B ∈ STRUC (τ ) be any τ -structures such that #(A) =#(B) = n. The distance between structures A and B is∑sdist(A, B) :=aiAB
i=1 |{x | x ∈ U∑ and Ri (x) ⊕ Ri (x)}|
.
s
ai
i=1 n

This is a natural definition; it is equivalent to mapping the structures to binary
strings in the usual way and using the normal string testing definitions (basedon normalized Hamming distance). We note that Definition 4 is common in theliterature on graph property testing, but that it is generally not used in nonuniform hypergraph testing. However, it results in the weakest (cf. Theorem 1
below) notion of testability that we consider, and so we prefer to use it whenproving untestability results.
The simplicity of Definition 4 is attractive, however it has some shortcomings.
In particular, any diﬀerence in low-arity relations is asymptotically dominated by
the number of high-arity tuples. This has a number of undesirable eﬀects, as
testing relational structures degenerates roughly to testing uniform hypergraphs.
For example, consider (not necessarily admissible3 , vertex) 3-colored graphs withthe vocabulary τC := (E 2 , R1 , G1 , B 1 ), where we use the binary predicate E torepresent edges and the monadic predicates to represent colors. We might wish totest if the given coloring is admissible. However, if we use Definition 4, then (in316

An admissible vertex-coloring is one that assigns distinct colors to adjacent vertices.

2.3. PROPERTY TESTING
large graphs), the given coloring is insignificant and we actually test whether thegraph is 3-colorable. We need a diﬀerent model for our task.
Our first attempt to resolve this is rdist.
Definition 5. Let A, B ∈ STRUC n (τ ) be τ -structures. Then, the r-distance is
B|{x | x ∈ U ai and RA
i (x) ⊕ Ri (x)}|
.
1≤i≤s
n ai

rdist(A, B) := max

While Definition 4 gave equal weight to each tuple regardless of its arity, theabove gives equal weight to each relation. The model of testability resulting from
Definition 5 is essentially equivalent to the model used by Fischer et al. [22].
However, loops (i.e., self-edges (x, x)) in graphs and other subrelations of relations are similar to low-arity relations. In Definition 5, these are still dominatedby the “non-degenerate” tuples. Definition 8 will resolve this issue and result in amodel of testability essentially equivalent to that implicit in Austin and Tao [11].
We begin by defining the syntactic notion of subtype before proceeding to subrelations.
Definition 6. A subtype S of a predicate symbol with arity a is any partition of
the set {1, . . . , a}.
For example, graphs have a single, binary predicate symbol E 2 which has two
subtypes: {{1, 2}} and {{1}, {2}}, corresponding to loops and non-loops respectively. Let SUB(Riai ) denote the set of subtypes of predicate symbol Riai .
Definition 7. Let A ∈ STRUC (τ ) be a τ -structure with universe U , and let S bea subtype of predicate symbol Riai ∈ τ . We define the following.
17

CHAPTER 2. PRELIMINARIES• sU (S), the tuples that belong to S, is the set of (x1 , . . . , xai ) ∈ U ai satisfying
the following condition. For every 1 ≤ j, k ≤ ai , xj = xk iﬀ j and k arecontained in the same element of S.
• The subrelation sA (S) of A corresponding to S is sA (S) := sU (S) ∩ RAi .
Returning to our example of graphs, the sets of loops and non-loops are thesubrelations of the edge relation E corresponding to the subtypes {{1, 2}} and{{1}, {2}} of E 2 , respectively.
We denote the symmetric diﬀerence of sets U and V by U △ V , i.e.,

U △ V := (U \V ) ∪ (V \U ) .

Definition 8. Let A, B ∈ STRUC n (τ ) be τ -structures with universe size n. The
mr-distance between A and B is|sA (S) △ sB (S)|.
R∈τ S∈SUB(R) n!/(n − |S|)!

mrdist(A, B) := max max

The mr-distance between structures is the fraction of assignments that diﬀer inthe most diﬀerent subtype. Although this definition is the most involved, it has
a number of advantages. First, it is essentially equivalent to the model used by
Austin and Tao [11] based on the fraction of induced structures (of a particularsize) diﬀering between structures.
More importantly, it does not allow us to make untestable properties testableby increasing the arity of relations (i.e., untestable graph properties encoded inbinary subrelations of higher-arity relations remain untestable). This means that18

2.3. PROPERTY TESTING
the untestable properties (and prefix-vocabulary classes) are closed downwards inthe way required by Gurevich’s Classifiability Theorem4 , and so we are guaranteeda finite classification of the testable and untestable prefix vocabulary classes.

Figure 2.1. Comparison of distance measures dist, rdist and mrdist.

Figure 2.1 demonstrates the diﬀerences between the distance measures. The
colored graphs in the figure have a binary edge relation and a monadic color
relation. If we assume that the graphs are large enough for asymptotic behavior
to dominate, then we can make the following observations.
1. The dist between all graphs is small. This is because the non-loop edges do
not diﬀer, and these tuples dominate dist.
2. The rdist is large between G1 and G2 , large between G2 and G3 , and small between G1 and G2 . This is because the rdist reflects the diﬀerence in monadic
color assignments, but still allows non-loop edges to dominate loops in theedge relation.
3. The mrdist is large between all graphs. This is because rdist reflects diﬀerences in each subrelation.
Given that testers make queries to a small portion of the structure, mrdist is4

Gurevich [34] gives a nice introduction to this theorem, which first appeared as [32] (inEnglish as [33]). See Section 2.3 of Börger et al. [15] for a nice proof and related material.

19CHAPTER 2. PRELIMINARIES
particularly natural as a distance measure. This is because testers can notice differences in subrelations and low-arity relations, which are best reflected in mrdist.

2.3.2

Testing Definitions

All three distance measures generalize to distances from properties in the usual
way. The distance from a structure to a property is the distance to the closest
structure that has the property. For example, dist(A, P ) is defined as follows.
Definition 9. Let P be a τ -property and let A be a τ -structure with universe
size n. Then,dist(A, P ) :=min

A′ ∈P ∩STRUC n (τ )dist(A, A′ ) .

The remaining two distance measures extend in the same way.
Definition 10. An ε-tester for property P is a randomized algorithm given an
oracle which answers queries for the universe size and truth values of relations ondesired tuples in a structure A. The tester must accept with probability at least 2/3
if A has P and must reject with probability at least 2/3 if dist(A, P ) ≥ ε.
Testers are called oblivious (see Alon and Shapira [8]) if they are not allowed tomake decisions based on the size of the universe. More concretely, a tester in their
setting is only allowed to give the oracle a natural Q, and the oracle then uniformly
randomly selects Q elements of the universe of A and returns the resulting induced
substructure. However, if A is of size smaller than Q, then the entire structure
is returned. This is more restricted than our model, but our positive results holdeven in the oblivious setting.
20

2.3. PROPERTY TESTING

Figure 2.2. A property tester.

Figure 2.2 is an example of a property tester. Note that the sample is of constantsize – one must choose a new tester to get a new sample size. Also, note that
although the graph in Figure 2.2 is not bipartite, it is not far from being bipartite.
Some of our results hold even when the testers are restricted to one-sided error,
where the following definition applies.
Definition 11. An ε-tester for P has one-sided error if it accepts with probability 1
if A has P and rejects with probability at least 2/3 if dist(A, P ) ≥ ε.
Definition 12. Property P is testable if for every ε > 0 there is an ε-tester
making a number of queries which is upper-bounded by a function depending onlyon ε.
We say that a property P is testable with one-sided error if the ε-testers satisfy
the additional restriction of having one-sided error. Note that we allow the εtesters to be diﬀerent for each ε > 0, which results in uniform and non-uniform
versions of testability. Although most positive results in the literature hold foruniform testability, see Alon and Shapira [9] for a property that is testable onlywith uncomputable c(ε), or [43] for an undecidable property that is testable non-21

CHAPTER 2. PRELIMINARIES
uniformly but not uniformly. Our results hold in both cases5 and so we will not
distinguish between them.
We let T be the set of testable properties using the dist definition, Tr be theset of testable properties using the rdist definition and Tmr be the set of testableproperties using the mrdist definition. For convenience, we often refer to, e.g.,
Tmr -style testers or Tr -style testing.
Definition 13. We use the following conventions to avoid unwieldy language.
1. A sentence is (un)testable if the property it defines is (un)testable.
2. A prefix class is testable if every sentence in it expresses a testable property
for every vocabulary in which it is evaluable.
3. A prefix class is untestable if it contains an untestable sentence.

5

That is, our negative results hold for non-uniform testing and positive results for uniform
testing. In the uniform case, we must restrict Lemma 7 to decidable properties. All properties
considered in the present paper are clearly decidable.

22Chapter 3
Basic Results
In this chapter, we prove various basic results that we will need for later results.
We include the proofs here for completeness, even though these results are notparticularly diﬃcult.

3.1

Testing is Hardest in Minimal Vocabularies

We begin with the following simple lemma, which justifies the intuition that we
can focus on the minimal vocabulary needed in a formula and ignore vocabularies
that include extraneous predicate symbols. Here, an extension of a vocabulary τis any vocabulary formed by adding a new, distinct predicate symbol to τ .
Lemma 1. Let φ be a formula in the first-order logic of vocabulary τ and let τ ′be any extension of τ . If φ defines a testable τ -property, then the τ ′ -property it
defines is also testable.
Proof (Lemma 1). Let φ define τ -property P and τ ′ -property P ′ . Assume the“new” predicate symbol in τ ′ is N of arity a. Let Tετ be an ε-tester for P . We will
23

CHAPTER 3. BASIC RESULTS
show that it is also an ε-tester for P ′ . Assume A ∈ STRUC (τ ′ ) has property P ′ .
Removing the N predicate, the corresponding A′ ∈ STRUC (τ ) has property P
and so Tετ accepts with probability at least 2/3, as desired.
Assume that dist(A, P ′ ) ≥ ε and again let A′ be the structure of type τ formedby removing the N predicate from A. By the definition of distance,
∑s

ai
A′
B
i=1 |{x | x ∈ U ∑ and Ri (x) ⊕ Ri (x)}|≥dist(A , P ) = min
s
ai
B∈P
i=1 n
∑s
B
|{x | x ∈ U ai and RA
i (x) ⊕ Ri (x)}|∑min i=1= dist(A, P ′ ) ≥ ε .
s
a
a
i
B∈P
n + i=1 n′

The tester rejects such an A with probability at least 2/3, as desired.

Lemma 1

Testable properties remain testable when the vocabulary is extended. So it
suﬃces to consider the minimal relevant vocabulary. Simple modifications of theproof of Lemma 1 give the corresponding results for Tr and Tmr -style testing.

3.2

Comparing Models of Testability

In Subsection 2.3.1 above, we gave several distance definitions, each of which
results in a model of relational property testing. In this section, we consider these
diﬀerent models and prove the relationship between them. The main result is
Theorem 1, which shows that these models form a strict hierarchy.
Theorem 1. Tmr ⊂ Tr ⊂ T .
That is, Tmr -style testing is the most diﬃcult, while T -style testing is the easiest.
Theorem 1 provides guidance for many of our results: when possible, we prefer24

3.2. COMPARING MODELS OF TESTABILITY
to prove positive results in the strictest (Tmr ) model and negative results in theweakest (T ).
In addition, Tr -testing is equivalent to the model of Fischer et al. [22], while Tmr testing is equivalent to the model of Austin and Tao [11]. Theorem 1 therefore
provides some way of relating these results. However, we will see in Lemma 5 belowthat although in general these models are all distinct, Tr and Tmr are equivalent
for many natural classes of properties.

3.2.1

Proof of Theorem 1

We begin the proof of Theorem 1 with the following simple lemma.
Lemma 2. Let τ be a vocabulary and A, B ∈ STRUC n (τ ). Then,dist(A, B) ≤ rdist(A, B) ≤ mrdist(A, B).

Proof (Lemma 2). We first show dist(A, B) ≤ rdist(A, B). If an ε-fraction of all
assignments diﬀers and we partition the assignments, there must be a partition
such that at least an ε-fraction of the assignments diﬀers in the partition. Letdist(A, B) = ε and let αi be the fraction of Ri -assignments that diﬀer between the
structures,|{x | x ∈ U ai and RiA (x) ⊕ RiB (x)}|
.
αi :=
n ai
Then, rdist(A, B) = maxi αi and we can write dist(A, B) in terms of the αi ,∑α i n aidist(A, B) = ∑i ai = ε .
in
25

CHAPTER 3. BASIC RESULTS
This implies that∑i αi n

ai

=ε

∑

in

ai

, and so there must be an αi ≥ ε.

Next, we show that rdist(A, B) ≤ mrdist(A, B). The proof is nearly identical tothe above. If rdist(A, B) = ε then there is an Ri such that an ε-fraction of the Ri assignments diﬀers between the structures. If we partition the Ri -assignments into
the subtypes of Ri (which are disjoint), then there must be some partition suchthat at least an ε-fraction of the assignments in that partition diﬀer.

Lemma 2

Assume a tester distinguishes between structures A having some property P and
those for which mrdist(A, P ) ≥ ε. Lemma 2 trivially implies that it also distinguishes between structures A that have P and those for which rdist(A, P ) ≥ ε.
The case with rdist and dist is analogous, which proves the following.
Corollary 1. Tmr ⊆ Tr ⊆ T .
Of course it is always desirable to show that such containments are strict. We
show the separations by encoding the following language of binary strings; recall←

that u denotes the usual reversal of string u. It is also possible to use, e.g., one of
the untestable properties that will be seen in Chapter 5 to prove the separations
with a first-order expressible property that is closed under isomorphisms.
← ←Theorem 2 (Alon et al. [5]). Language L = {uuv v | u, v are strings over {0, 1}}
is not testable.
We are now ready to prove Theorem 1.
Proof (Theorem 1). The inclusions are by Corollary 1 and so only the separations
remain. We first show that T \Tr is not empty. It suﬃces to give a vocabulary τ26

3.2. COMPARING MODELS OF TESTABILITY
and a τ -property that is T -testable but not Tr -testable. We use the vocabulary
τC := (E 2 , S 1 ).
We will show P1 ∈ T \Tr , where P1 ⊆ STRUC (τC ) is the set of structures where
the S assignments encode the language L of Theorem 2. Recall that n denotes
the size of the universe and our convention is that S(i) is interpreted as “bit i ofthe string is 1”. Therefore, A has P1 if there is some 0 ≤ k ≤ n/2 such that for
all 0 ≤ i < k, S(i) is true iﬀ S(2k − 1 − i) is true and for all 0 ≤ j < (n − 2k)/2,
S(2k + j) is true iﬀ S(n − 1 − j) is true. The property uses only the low-arity
relation S; the E relation is for “padding” to make P1 testable under the dist
definition for distance.
We first show that P1 is in T . A structure with a universe of odd size cannot
have P1 . A tester can begin by checking the parity of n and rejecting if it is odd
and so we assume in the following that the size of the universe is even.
Lemma 3. Property P1 is testable under the dist definition for distance.
← ←Proof (Lemma 3). For any (even) n, 1n is of the form uuv v. Changing all S(i)assignments to true in any given A results in the string 1n . This involves at most n
modifications and so dist(A, P1 ) ≤ dist(A, A′ ) = O(n)/Θ(n2 ) < ε, where the final
inequality holds for suﬃciently large n. Let N (ε) be the smallest value of n forwhich it holds. The following is an ε-tester for P1 , where the input has universe
size n.
1. If n < N (ε), query all assignments and output whether the input has P1 .
2. Otherwise, accept.

27

CHAPTER 3. BASIC RESULTS
If A has P1 , we accept with zero error. If dist(A, P1 ) ≥ ε, then n < N (ε). In
this case we query all assignments and reject with zero error.

Lemma 3It remains to show that P1 is not testable when using the rdist definition for
distance. We do this by showing that it would contradict Theorem 2.
Lemma 4. Property P1 is not testable under the rdist definition for distance.
Proof (Lemma 4). Suppose there exist Tr -type ε-testers T ε for all ε > 0. The
following is an ε-tester using Definition 4 for the language L of Theorem 2. Let
the input be w, a binary string of length n.
1. Run T ε and intercept all queries.
2. When a query is made for S(i), return the value of S(i) in w.
3. When a query is made for E(i, j), return 0.
4. Output the decision of T ε .
We run T ε on the A ∈ STRUC n (τC ) that agrees with w on S and where all E
assignments are false. If w ∈ L, then any such A has property P1 and so our tester
accepts with probability at least 2/3.
Assume dist(w, L) ≥ ε. Then, rdist(A, P1 ) = dist(w, L) ≥ ε and so our tester
rejects with probability at least 2/3. These are testers for the untestable languageof Theorem 2, and so P1 is untestable under the rdist definition.

Lemma 4

Lemmata 3 and 4, together with Corollary 1 show Tr ⊂ T . The separation
Tmr ⊂ Tr is shown in a similar way, using a property with suﬃcient “padding” tomake Tr testing simple but Tmr testing would contradict Theorem 2.
28

3.2. COMPARING MODELS OF TESTABILITY
For example, one can use the property P2 of graphs in which the “loops” E(i, i)
encode the language from Theorem 2. That is, a graph has P2 if there is some0 ≤ k ≤ n/2 such that for all 0 ≤ i < k, E(i, i) is true iﬀ E(2k − 1 − i, 2k − 1 − i) istrue and for all 0 ≤ j < (n−2k)/2, E(2k +j, 2k +j) is true iﬀ E(n−1−j, n−1−j)is true. The non-loops are used as padding to ensure Tr testability while Tmr
testability would allow us to violate Theorem 2.

Theorem 1

There exist properties that are testable in the rdist sense but not in the mrdist
sense. However, the definition of subtypes and Tmr testability allows for a simple mapping between vocabularies such that rdist-testability of certain classes ofproperties implies mrdist-testability of the same classes. For these classes, proving
testability in the rdist sense is equivalent to proving it in the mrdist sense, and so
it suﬃces to use whichever definition is more convenient.
Lemma 5 is given in the context of the classification problem for first-orderlogic but it is not diﬃcult to prove similar results in other contexts. We will use
Lemma 5 in Section 4.1, to prove the testability of a class that has this particularform.
Lemma 5. Let C := [Π, all]= be a prefix vocabulary class. Then, C is testable in
the rdist sense iﬀ it is testable in the mrdist sense.
Proof. Recalling Theorem 1, Tmr testability implies Tr testability. We prove Tr
testability of such prefix classes implies Tmr testability using Lemma 6. In thefollowing, S(n, k) is the Stirling number of the second kind.
Lemma 6. Let C = [Π, (p1 , p2 , . . .)]= be a prefix vocabulary class and, furthermore,
let qj =∑i≥j pi S(i, j).

If C ′ = [Π, (q1 , q2 , . . .)]= is Tr testable, then C is Tmr
29

CHAPTER 3. BASIC RESULTS
testable.
Proof (Lemma 6). Let φ ∈ C be arbitrarily fixed and assume that the predicate
symbols of φ are {R11 , R21 , . . . , Rp11 , R12 , . . .}, where the arity of Rji is i. We constructa φ′ ∈ C ′ and show that Tr testability of φ′ implies Tmr testability of φ. In φ′ wewill use a distinct predicate symbol for each subtype of each Rji in φ. A subtype
S of Rji such that |S| = k is a partition of the integers {1, . . . , i} into k non-empty
sets and so there are S(i, k) such subtypes. We therefore require a total of qk
distinct predicate symbols of arity k.
For example, we will map the “loops” in a binary predicate E to a new monadic
predicate and the non-loops to a separate binary predicate.

Formally, recall

that sU maps the subtypes of a predicate to the sets of tuples comprising thesubtypes. For our example of a binary predicate, (0, 1) ∈ sU ({{1}, {2}}) and(0, 0) ∈ sU ({{1, 2}}). Next, we let r be a bijection from the subtypes of predicatesto their new names, the predicate symbols that we will use in φ′ .
We create φ′ by modifying φ. Replace all occurrences of Rji (x1 , . . . , xi ) with



∨


[
]
(x1 , . . . , xi ) ∈ sU (S) ∧ r(S, Rji )(y)  .

S∈SUB(Rji )Note that (x1 , . . . , xi ) ∈ sU (S) is an abbreviation for a simple conjunction, e.g.,x1 ̸= x2 ∧ x1 ̸= x3 ∧ · · · . Likewise, y is an |S|-ary tuple, formed by removing the
duplicate components of (x1 , . . . , xi ). The implicit mapping from (x1 , . . . , xi ) isinvertible given S. To continue our example of a binary predicate E, we would30

3.2. COMPARING MODELS OF TESTABILITY
replace all occurrences of E(x, y) in φ with([x = y ∧ E1 (x)] ∨ [x ̸= y ∧ E2 (x, y)]) .

We assume that φ′ is Tr testable, and so there exists an ε-tester T ε for it. We
run this tester and intercept all queries. For a query to r(S, Rji )(y), we return thevalue of Rji (x1 , . . . , xi ). This is possible because r is a bijection, and so we canretrieve S and Rji using its inverse. Then, we can reconstruct the full i-ary tuple(x1 , . . . , xi ) from y and S.
The tester implicitly defines a map1 from structures A which we wish to testfor φ to structures A′ (with the same universe as A) which we can test for φ′ .
Given an A |= φ, the corresponding A′ |= φ′ and so T ε will accept with probability at least 2/3.
We map each subtype S to a distinct predicate symbol with arity |S|. Therefore,
for any structures A, B, the implicit mapping to A′ , B ′ is such that

mrdist(A, B) = rdist(A′ , B ′ ).

For convenience, let P := {B | B |= φ} and P ′ := {B ′ | B ′ |= φ′ }. For an A suchthat mrdist(A, P ) ≥ ε, we simulate T ε on an A′ such that rdist(A′ , P ′ ) ≥ ε. The
tester T ε rejects with probability at least 2/3, as desired.

Lemma 6

Proving Tr testability for [Π, all]= implies proving it for all (q1 , . . .) that are
Explicitly, map A to an A′ with the same universe size, where y ∈ r(S, Rji ) in A′ if(x1 , . . . , xi ) ∈ Rji in A. Note that we have not yet defined the assignments of tuples y with
duplicate components. By construction, the assignments of these tuples do not aﬀect φ′ and so
any reasonable convention will do. For example, for any predicate symbol symbol Q of φ′ andany tuple z that has at least one duplicate component, we define z ̸∈ Q. The resulting map is
injective but not necessarily surjective.
131

CHAPTER 3. BASIC RESULTS“images” of some (p1 , . . .) and so Lemma 6 is stronger than required.

3.3

Lemma 5

Indistinguishability

Indistinguishability is a notion introduced by Alon et al. [3] that we use in severalof our proofs. Essentially, two τ -properties are indistinguishable if suﬃciently large
structures that have one of the properties become arbitrarily close to having theother (i.e., the limit of the distance goes to zero as the size of the structures
increases).
Definition 14 (Alon et al. [3]). Let P1 , P2 ⊆ STRUC (τ ) be τ -properties that areclosed under isomorphisms. We say that P1 and P2 are indistinguishable if forevery ε > 0 there exists an N := N (ε) ∈ N such that the following holds for alln > N . For every A ∈ STRUC n (τ ), if A has property P1 , then mrdist(A, P2 ) < ε
and if A has P2 , then mrdist(A, P1 ) < ε.
The most important fact regarding indistinguishability is that it preserves testability.
Lemma 7 (Alon et al. [3]). Let P1 , P2 ⊆ STRUC (τ ) be indistinguishable2 τ properties. Property P1 is testable iﬀ P2 is testable.
The proof by Alon et al. [3] extends to relational structures (from undirectedloop-free graphs) without diﬃculty once we use mrdist in Definition 14. In fact,
because the proof shows that one can construct an ε-tester for one of the properties
by taking the majority vote of three runs of an ε/2-tester for the other property,
the query complexities of the two properties are closely related.
2

32

If we are interested only in uniform testability, then the properties must also be decidable.

3.4. YAO’S PRINCIPLE

3.4

Yao’s Principle

There are a number of tools used to prove lower bounds for testing, including reductions to problems from communication complexity (cf. Blais et al. [13]). Yao’s
Principle (cf. Yao [69]), an interpretation of von Neumann’s minimax theorem [53]in the context of probabilistic computation, is probably the most commonly usedsuch tool, and several of our results in Chapter 5 rely on applications of thisprinciple.
There are many variations of Yao’s Principle; we use the following.
Principle 1 (Yao’s Principle). If there is an ε ∈ (0, 1) and a distribution overG n such that all deterministic testers with complexity c have an error-rate greaterthan 1/3 for property P , then property P is not testable with complexity c.
The definition of “testable” is of course our usual one involving random testers.
In applications, one usually seeks to show that for suﬃciently large n and someincreasing function c := c(n), there is a distribution of inputs such that all deterministic testers with complexity c have error-rates greater than 1/3.
For completeness, we prove our version of Principle 1. We prove only the direction of the minimax theorem that is required for our purposes; for a survey ofminimax theorems and their proofs see Simons [65].

3.4.1

Proof of Principle 1

We begin by providing the definitions required to state Principle 1.

33

CHAPTER 3. BASIC RESULTS
Definition 15. A deterministic tester is a binary tree where each internal nodeis labeled with a non-negative integer, each leaf is labeled “accept” or “reject,” andthe two edges from a node are labeled 0 and 1.
Given an input, we execute the tester as follows. Beginning at the root, weinterpret the labels on internal nodes as the bit position of the input that will be
queried. If the result of the query is 0, we follow the 0 edge and otherwise the
1 edge. When we reach a leaf we output the decision on the label. Note that it
is equivalent to label the internal nodes with atomic formulae such as E(0, 1) asthese are equivalent to specific bits of the input, the positions of which can beeasily computed.
Definition 16. The complexity of a deterministic tester is the number of internal
nodes, including the root unless it is a leaf, on the longest path from the root to aleaf.
The complexity of a deterministic tester is then the maximum number of queries
that it makes. Our interest is limited to testers of finite complexity, i.e., those that
output a decision in finite time. Without loss of generality, we can restrict ourattention to balanced binary trees, by making extra, useless queries on the shorter
paths in order to “pad” their lengths.
For testability, we are concerned only with the error-rate on inputs that either
have our desired property or are ε-far from having the property. Therefore, we
define the error-rate of a tester to be non-zero only on such examples. Because ofthis, it suﬃces to restrict our attention to distributions that give zero probability
to the remaining “possible” inputs (those that do not have the property in question,
34

3.4. YAO’S PRINCIPLE
but are also not ε-far from it).
We begin by proving the following direction of the minimax theorem. We saythat a vector x ∈ R|x| is a probability vector if each of its components is a nonnegative real number and the sum of its components is 1. For n > 0, we let Pn be
the set of probability vectors with n components,{Pn :=x | x = (x1 , . . . , xn ) ∈ Rn , xi ≥ 0 for all 1 ≤ i ≤ n, andn∑}xi = 1 .

i=1

It is well-known that equality holds in the following, however we restrict ourselves to stating and proving only the direction required for Principle 1, as mentioned above.
Theorem 3 (Minimax Theorem). Let M be an a × b matrix of non-negative
reals and X = Pa and Y = Pb be the sets of all probability vectors with a and bcomponents, respectively. Then,max min xM yT ≤ min max xM yT .
y∈Y x∈Xx∈X y∈Y(3.1)

Proof (Theorem 3). Let y∗ be any of the arg max on the left in (3.1),y∗ := arg max min xM yT ,
y∈Y

x∈X

and x∗ be any of the arg min on the left in (3.1),x∗ := arg min xM y∗ T .
x∈X

35

CHAPTER 3. BASIC RESULTS
Then, for any probability vector x ∈ X, by the definition of minimum,xM y∗ T ≥ x∗ M y∗ T .

(3.2)

Let x+ and y+ be any of the arg min and arg max on the right of (3.1), that is

x+ := arg min max xM yT and y+ := arg max x+ M yT .
x∈X

y∈Y

y∈Y

Then, by the definition of maximum, x+ M y+ ≥ x+ M y∗ T . Therefore, by (3.2),
T

min max xM yT = x+ M y+ ≥ x+ M y∗ T ≥ x∗ M y∗ T = max min xM yT .
Tx∈X y∈Yy∈Y x∈X

Theorem 3
Given Theorem 3, it is easy to show Principle 1. In (3.1), we call x on the left
and y on the right “inner vectors.” This is because we can think of them as being
chosen after the “outer vectors” (y on the left and x on the right) are fixed. For the“inner” vectors, it suﬃces to consider unit vectors ei , where component i is 1 andall other elements are 0. This is because once the outer vector is fixed, denoting
the i-th component of a vector z by [z]i ,min xM yT = earg mini [M yT ]i M yTx∈X

and likewise for the maximum on the right of (3.1). This proves the following
simple corollary of Theorem 3.
Corollary 2. Let M be an a × b matrix of non-negative reals and X = Pa and36

3.4. YAO’S PRINCIPLE
Y = Pb be the sets of all probability vectors with a and b components, respectively.
Then,
max min ei M yT ≤ min max xM eTj .
y∈Y ei ∈Xx∈X ej ∈Y(3.3)

Proof (Principle 1). Principle 1 is an interpretation of (3.3) in the context of testing. We let a be the number of deterministic testers with complexity c whose
queries are evaluable in structures of type τ that have n elements. We assume
that there is an enumeration of these testers. Then, a randomized tester withcomplexity c for structures of n elements is given by a probability vector x ∈ X,
where [x]i is interpreted as the probability that the randomized tester behaves likethe i-th deterministic tester. A unit vector ei ∈ X specifies the i-th deterministic
tester.
Likewise, we assume there is an enumeration of structures of type τ that haven elements and let b be the number of such structures. Then, a probability vectory ∈ Y is a distribution over these structures and a unit vector ej specifies the j-thstructure.
For matrix M , we let Mij be 1 if the i-th deterministic tester is incorrect on
the j-th input and this input either has the desired property or is ε-far from it.
Otherwise, we let Mij be 0.
We now have have an a × b matrix M and a meaning for a and b component
probability vectors and so we can interpret the meaning of Corollary 2. On the left,
ei M yT is the average-error of the i-th deterministic tester on a structure chosen
according to distribution y. Likewise, on the right, xM eTj is the error-rate of therandomized tester specified by x on the j-th structure.

37

CHAPTER 3. BASIC RESULTS
Therefore, the left side of (3.3) is the average-error of the “best” deterministic
tester on the “worst” distribution of inputs, when we define “best” as the lowest
average-error. If we find some distribution y+ of inputs such that all deterministic
testers have an error-rate greater than 1/3, then 1/3 is a lower bound on the left
side, and therefore the right side, of (3.3).
The right side of (3.3) is the error-rate of the “best” randomized tester on the“worst” input structure, when “best” is defined as the best worst-case. If the “best”
randomized tester with complexity c has an error-rate greater than 1/3 on an input,
we can conclude that the property in question is not testable with complexity c.
Principle 1

3.5

Summary

In this chapter, we proved various basic results that we will use in later chapters.
In particular, Theorem 1 relates the three models of testability that we introducedin Section 2.3. This encourages us to prove positive results in the strongest model(i.e., we will focus on Tmr in Chapter 4) and negative results in the weakest model(i.e., we will focus on T in Chapter 5).

38

Chapter 4
Testable Classes
We are now ready to prove the testability of two large, syntactic subclassesof first-order logic. We prove the testability of Ackermann’s class with equality([∃∗ ∀∃∗ , all]= ) in Section 4.1, and of Ramsey’s class ([∃∗ ∀∗ , all]= ) in Section 4.2.

4.1

Ackermann’s Class with Equality

In this section we show that Ackermann’s class with equality ([∃∗ ∀∃∗ , all ]= ) is
testable. We begin by reviewing the history of this class, which has a number of
nice properties.
Ackermann’s class was first considered (without equality) by Ackermann [1],who showed that the satisfiability problem for the class is decidable and that it
has the finite model property1 . Kolaitis and Vardi [45] showed the satisfiability
problem for Ackermann’s class with equality is complete for NEXPTIME and1

A class is said to have the finite model property if every satisfiable formula in the class has afinite model. Classes without this property have infinity axioms, i.e., sentences with only infinite
models.

39

CHAPTER 4. TESTABLE CLASSES
that a 0-1 law holds for existential second-order logic2 where the first-order part
belongs to [∃∗ ∀∃∗ , all ]= . Lewis [48] proved that satisfiability for Ackermann’s classwithout equality is complete for (deterministic) EXPTIME. Grädel [31] showedthat satisfiability for Ackermann’s class without equality is complete for EXPTIME
even with the addition of arbitrarily-many function symbols.
If we allow equality and a unary function symbol, the result is Shelah’s class,which Shelah [64] proved decidable. Shelah’s class is a decidable class that does
not have the finite model property, and it would be interesting to determine if
it is testable. This would require extending relational testing to allow function
symbols.
Ackermann’s class with equality has been studied in other settings as well. For
example, Fermüller and Salzer [18] used an extension of resolution to decide anextension of Ackermann’s class with equality using automated theorem provers.
The main goal of this subsection is Theorem 4 below. Recalling Theorem 1, thisalso implies that such properties are testable in the dist and rdist senses. If the
vocabulary consists of a single relation, the rdist and dist definitions are equivalent
to the dense hypergraph model. We therefore obtain the corresponding results inthe dense hypergraph and dense graph models as special cases.
We denote the set of monadic predicate symbols in a vocabulary τ by M :={Ri | Ri ∈ τ and ai = 1}. The set of assignments of the symbols in M for anelement in a universe is called the color of the element and there are 2|M | possible
2

A class C of first-order logic has an associated 0-1 law if all existential second -order sentences
φ := ∃C1 . . . Ca ψ, where ψ is a first-order sentence in C, have the property that the limit as
n → ∞ of the probability that a random structure of size n satisfies φ exists and is either 0 or 1.
Recall that the focus is on existential second -order because all of first-order admits a 0-1 law,
see the references in Kolaitis and Vardi [46].

404.1. ACKERMANN’S CLASS WITH EQUALITY
colors. We define Col(A, c) to be the set of colors that occur at least c times in A.
Theorem 4. All formulae in [∃∗ ∀∃∗ , all ]= define properties that are in Tmr with
one-sided error.
Proof (Theorem 4). Recall that Ackermann’s class with equality is [∃∗ ∀∃∗ , all ]=and, therefore, it suﬃces to show the testability of property P of type τ =(R1a1 , . . . , Rsas ) defined by formula φ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb : ψ, where ψ isquantifier-free. Note that a is the number of leading existential quantifiers and b
is the number of trailing existential quantifiers. We can trivially test any φ thathas only finitely-many models with a constant number of queries and zero error,and so it suﬃces to assume that φ has infinitely-many models.
The class [∃∗ ∀∃∗ , all ]= is of the form required by Lemma 5 above, and so it
is mrdist-testable iﬀ it is rdist-testable. It therefore suﬃces to show that P is
testable in the rdist sense. We will show that the following is an ε-tester in therdist sense for P on input A ∈ STRUC n (τ ). Here, k := k(τ, ε) is the number of
elements queried and N := N (φ, τ, ε) is a constant, both of which are determined
below. Note the actual number of queries in Step 2 is not exactly k, but rather
a constant multiple of it depending on τ . Finally, we explicitly give κ := κ(φ, τ )below.
1. If n < N , query all of A and decide exactly whether A has P .
2. Uniformly and independently choose k members of the universe of A andquery all monadic predicates on the members in this sample. Let B be theobserved substructure.

41

CHAPTER 4. TESTABLE CLASSES
3. Search over all A′ ∈ STRUC κ (τ ). Accept if an A′ is found such that A′ |= φand Col(B, a + 1) ⊆ Col(A′ , a + 1).
4. Otherwise, reject.
We will show that the tester accepts (with probability 1) if A |= φ and rejects
with probability 2/3 if rdist(A, P ) > ε. We first show that if A |= φ, then the tester
is guaranteed to accept. Then, we will show in Lemma 9 that with probability atleast 2/3, we get a “good” sample in Step 2. A sample is “good” if it contains atleast (a + 1)-many distinct representatives of each color that occurs on at least anε/(2 · 2|M | ) fraction of the elements of A. We then show that the tester is correct
if it obtains a good sample, and therefore rejects with probability at least 2/3 ifrdist(A, P ) > ε.
We will now show that if A |= φ, the tester will accept with probability 1. We
begin with Lemma 8.
Lemma 8. Let A be a model of φ such that #(A) > N and let(∑sκ := a + 3b a + 2

i=1

∑ai
j=1

)
(aji )aai −j + 2|M | (a + 1).

Then, there is an A′ |= φ such that #(A′ ) = κ and Col(A, a + 1) ⊆ Col(A′ , a + 1).
Proof. Assume that N > κ. The structure A is a model of φ, and so there exists
at least one tuple of a elements (u1 , . . . , ua ) such that φ is satisfied when theexistential quantifiers bind ui to xi . We consider the xi and the substructure
induced by them to be fixed, and refer to this substructure as Ax .

42

4.1. ACKERMANN’S CLASS WITH EQUALITY

There are at most κ2 := a + 2

∑s
i=1

∑ai
j=1

(aji )aai −j many distinct structures con-structed by adding an element labeled y to Ax when we include the structures
where the label y is simply placed on one of the xi . We let v ≤ κ2 be the numberof such structures that occur in A and assume there is an enumeration of them.
For each of these v substructures there exist b elements, w1 , . . . , wb , such thatwhen we label wi with zi , the substructure induced by (x1 , . . . , xa , y, z1 , . . . , zb )models ψ. We construct Ai,j for 1 ≤ i ≤ 3 and 1 ≤ j ≤ v such that Ai,j is a copyof the w1 , . . . , wb used for the j-th structure (see Figure 4.1). We connect each Ai,jto Ax in the same way as in A, modifying assignments on tuples (Ax ∪ Ai,j )ak .
Ax

A1,1

A2,1

A3,1

A1,2

A2,2

A3,2

A1,v

A2,v

A3,v

Figure 4.1. A sketch of the new structure

For each wh in Ai,j , we consider the case where y is bound to wh . By construction
the substructure induced by (x1 , . . . , xa , y) occurs in A. We assume it is the g-th
structure and use the elements of Ai+1 mod 3,g to construct a structure satisfying ψ.
We modify the assignments of tuples as needed to create a structure identicalto that in A satisfying ψ. Note that by construction all of these assignments
are of tuples that contain wh and at least one element from Ai+1 mod 3,g . The
resulting structure, which we call A1 , is a model of φ. Before this step we have notmodified any assignments “spanning” the “columns” Ai,j of A1 and so there are no43

CHAPTER 4. TESTABLE CLASSES
assignments that we modify more than once.
However, there may be some color from Col(A, a + 1) that does not appear a + 1
times in A1 . We therefore add a new block, denoted Ae , of at most 2|M | (a + 1)
elements which consists of a + 1 copies of each color from Col(A, a + 1). Each ofthese colors occurred at least a + 1 times in A, and so for each such color C, there
is an element q in A with color C such that q is not part of Ax . If the substructure
induced by (Ax , q) in A is the j-th structure in our enumeration, then we do thefollowing for each member p of Ae that has the same color as q. First, we make thesubstructure induced by (Ax , p) identical to that induced by (Ax , q) in A. Next, we
make the substructure induced by (p, A1,j ) identical to that induced by q and thecorresponding zi in A. All of these modifications are on tuples containing a p ∈ Ae
and so we do not modify any tuples more than once. We call this structure A2 .
Finally, so far we only have an upper-bound on the size of A2 while the lemma
states it to be exactly of size κ. We therefore pad in the following simple way3 .
We know that N > κ > 2|M | a and so there is a color that occurs at least a + 1
times in A. If #(A2 ) < κ, we simply make an additional κ − #(A2 ) many copiesof this color in Ae and modify the assignments of tuples containing these newelements in the same manner as above. The resulting A′ has size κ and satisfies
the requirements of the lemma.

Lemma 8For any sample B of A, it is true that Col(B, a + 1) ⊆ Col(A, a + 1). If A |= φ,then Lemma 8 implies that our tester will find an A′ satisfying the conditions ofStep 3 and will therefore accept. This holds for any sample B and so the tester
will accept such A with probability 1.
3

44

One could instead change the tester to search structures with size at most κ.

4.1. ACKERMANN’S CLASS WITH EQUALITY
Next, assume that rdist(A, P ) ≥ ε. In this case we must show that the tester
rejects with probability at least 2/3. First, we show that the tester obtains a“good” sample with probability at least 2/3.
Lemma 9. There are constants k and N such that, with probability at least 2/3, thetester obtains a sample that contains at least (a + 1)-many distinct representativesof each color in Col(A, εn/(2 · 2|M | )).
Proof (Lemma 9). The probability that any particular query misses a fixed colorthat occurs on at least an ε/(2 · 2|M | ) fraction of A is at most (1 − ε/(2 · 2|M | )).
Moreover, the probability that we miss such a fixed color after k1 independent
queries is at most (1−ε/(2·2|M | ))k1 . There are at most 2|M | such colors, and so theprobability that a sample of k1 elements fails to contain at least one representativeof all such colors is at mostp1 := 2

|M |

(
)k
ε/2 1
1 − |M |.
2

The |M | is a constant, and we choose k1 such that (a + 1)p1 is at most 1/6.
Let k := (a + 1)k1 . We will make k independent queries, and consider the
total sample as (a + 1) separate samples of size k1 . All of these smaller samples
will contain at least one representative of every color in Col(A, εn/(2 · 2|M | )) withprobability at least 1 − (a + 1)p1 ≥ 5/6. However, there is the possibility thatsome of these smaller samples contain elements in common. We will choose N
such that for n > N , the probability that any particular element in the universeof A is chosen more than once is at most 1/6. In particular, if #(A) = n and we
define xy := x(x − 1) · · · (x − (y − 1)) = x!/(x − y)!, then the probability that some45

CHAPTER 4. TESTABLE CLASSES
element is queried more than once is

p2 := 1 −n!
n(a+1)k1=1−.
n(a+1)k1 (n − (a + 1)k1 )!
n(a+1)k1

The sample size (a+1)k1 is a constant, and so we can choose N such that p2 ≤ 1/6
for n > N .
The probability that the tester obtains a sample that contains at least (a + 1)many distinct representatives of each color in Col(A, εn/(2 · 2|M | )) is at least

1 − (a + 1)p1 − p2 ≥ 2/3.

Lemma 9
Our goal is to show that if rdist(A, P ) ≥ ε, then we reject with probability
at least 2/3. It is easier to show the contrapositive: if the tester accepts withprobability strictly greater than 1/3, then rdist(A, P ) < ε.
If we accept a structure A with probability strictly greater than 1/3, then wemust accept it when we obtain a good sample. We construct a B such that B |= φand rdist(A, B) < ε from the A′ that the tester must find to accept. We begin
with Lemma 10, which we will use to “grow” smaller models.
Lemma 10. Let φ := ∃x1 . . . ∃xa ∀y∃z1 . . . ∃zb : ψ be a formula with vocabulary τ ,where ψ is quantifier-free and A ∈ STRUC (τ ) be such that A |= φ. Additionally,let B ∈ STRUC (τ ) be any structure containing A as an induced substructure suchthat #(B) = #(A) + 1. If the additional element of B has a color that occurs atleast a + 1 times in A, then we can construct a B ′ |= φ by modifying at most a46

4.1. ACKERMANN’S CLASS WITH EQUALITY
constant number of non-monadic assignments in B.
Proof (Lemma 10). Structure B contains an induced copy of A and one additional
element, which we will denote by q. By assumption, A is a model of φ and therefore
contains an a-tuple (u1 , . . . , ua ) such that the formula is satisfied when xi is boundto ui . In addition, there are at least a + 1 elements in A that have the same color
as q. Therefore, there is at least one such element p that is not one of the ui . We
will make q equivalent to p without modifying any monadic assignments.
We begin by modifying the assignments as needed to make the structure inducedby (x1 , . . . , xa , q) identical to that induced by (x1 , . . . , xa , p). This requires at most∑s ∑ai (ai ) ai −j= O(1) modifications, all of which are non-monadic. Therei=1
j=1 j amust be (v1 , . . . , vb ) in A such that ψ is satisfied when zi is bound to vi andy to p. We modify the assignments needed to make the structure induced by(q, v1 , . . . , vb ) identical to that induced by (p, v1 , . . . , vb )4 . This requires at most∑s ∑ai (ai ) ai −j= O(1) modifications, all of which are non-monadic. The
i=1
j=1 j bresult has #(A) + 1 elements, models φ and was constructed from B by making a
constant number of modifications to non-monadic assignments.

Lemma 10

Let A be the structure that the tester is running on and A′ be the structure
found in Step 3 of the tester. As mentioned above, we will construct a B |= φfrom A′ such that B |= φ and rdist(A, B) < ε.
Note that there must exist at least one color in Col(A, εn/(2 · 2|M | )) and assume
that N is large enough that εn/(2 · 2|M | ) ≥ a + 1. We first make a constant-sized
portion of A identical to A′ . This requires at most O(1)-many modifications to

4

The case where vi = p can be handled by replacing vi with q in (q, v1 , . . . , vb ).

47

CHAPTER 4. TESTABLE CLASSES
each relation. All colors in Col(A, εn/(2 · 2|M | )) occur at least a + 1 times in A′ ,allowing us to recursively apply Lemma 10 and add the elements of A that havecolors in Col(A, εn/(2 · 2|M | )). This entails making O(1)-many modifications to
non-monadic relations (and none to monadic relations) at each step, for a total ofO(n) modifications to the non-monadic relations.
Finally, we consider the elements of A that have colors which occur at mostεn/(2 · 2|M | ) times. There are at most 2|M | such colors and at most εn/2 elementswith these colors. We change the monadic assignments on such elements as required to give them colors contained in Col(A, εn/(2 · 2|M | )). This requires at most
εn/2 modifications to each of the monadic assignments. We again recursively apply Lemma 10 to A, making O(1) modifications to non-monadic assignments ateach step. The resulting structure is B and is such that B |= φ.
Finally, we show that rdist(A, B) < ε. If Ri is a monadic relation, then thei-th term of the maximum in the definition of rdist (cf. Definition 5 above) is at
most ε/2 + o(1). If Ri has arity at least two, then the i-th term of the maximumis O(n)/Ω(n2 ) = o(1). All o(1) terms can be made arbitrarily small by choosing
N (φ, τ, ε) appropriately and so we can assume that all terms are strictly less than ε.
The maximum is then strictly less than ε and so rdist(A, B) < ε as desired.
Theorem 4

4.2

Ramsey’s ClassIn this section we revisit a result of Alon et al. [3] in the light of recent workby Austin and Tao [11]. The main result is the testability of the full Ramsey’s

48

4.2. RAMSEY’S CLASS
class (i.e., removing the restriction to undirected loop-free graphs). As we did for
Ackermann’s class with equality in Section 4.1, we begin by reviewing the history
and properties of the class, denoted [∃∗ ∀∗ , all ]= .
Ramsey’s class is also known as the Bernays-Schönfinkel-Ramsey class. Bernays
and Schönfinkel [12] proved the finite model property and that satisfiability is
decidable for the class without equality. Ramsey [56] extended these results to theclass with equality as part of a stronger result. Lewis [48] showed that satisfiability
is NEXPTIME-complete for Ramsey’s class and Kolaitis and Vardi [44] proved thata 0-1 law holds for existential second-order logic where the first-order part belongsto [∃∗ ∀∗ , all ]= . Omodeo and Policriti [54] have recently shown that the class issemidecidable for set theory.
The main goal of this subsection is Theorem 5 below. Recalling Theorem 1, thisalso implies testability in the T and Tr senses. The proof of Theorem 5 follows
the proof by Alon et al. [3], and relies on a reduction to a strong result by Austin
and Tao [11].
An outline of the proof is as follows. First, we show that all sentences in[∃∗ ∀∗ , all ]= define properties which are indistinguishable from instances of a generalized colorability problem. Next, we note that all such problems are hereditary
and therefore testable when mapped to the setting defined by Austin and Tao [11].
Finally, we show that this implies testability under our definitions, which gives thefollowing.
Theorem 5. All sentences in [∃∗ ∀∗ , all ]= define properties in Tmr .
We begin the proof of Theorem 5 by defining a generalized colorability problem,

49

CHAPTER 4. TESTABLE CLASSES
as did Alon et al. [3].
For any fixed set F of structures with vocabulary τ , some positive number ofcolors c, and functions that assign a color between 1 and c to each element ofeach structure in F , we define the F -colorability problem as follows. A structure
A ∈ STRUC (τ ) is F -colorable if there exists some (not necessarily proper) ccoloring of A such that A does not contain any induced substructures isomorphic
to a member of F . We let PF be the set of structures that are F -colorable.
For example, we can consider the case of graphs and let F contain c copies of K2 .
We enumerate these copies in some fashion from 1 to c, and for copy i, color bothvertices with i. The resulting problem is of course the usual (k- or equivalently)
c-colorability. The following is a straightforward generalization of the proof by
Alon et al. [3].
Lemma 11. Let φ be any first-order sentence in the class [∃∗ ∀∗ , all ]= . Thereexists an instance of the F -colorability problem that is indistinguishable from P ,the property defined by φ.
Proof (Lemma 11). Let ε > 0 be arbitrary and φ := ∃x1 . . . ∃xt ∀y1 . . . ∀yu : ψ be
any first-order formula with quantifier-free ψ and vocabulary τ . We note, as did
Alon et al. [3], that we can restrict our attention to formulae ψ where it is suﬃcient
to consider only cases where the variables are bound to distinct elements. Thisis because, given any ψ ′ , we can construct a ψ satisfying this restriction that isequivalent on structures with at least t + u elements, and the smaller structures
do not matter in the context of indistinguishability.
Let P = {A | A ∈ STRUC (τ ), A |= φ} be the property defined by φ. We

50

4.2. RAMSEY’S CLASS
now define an instance of F -colorability that we will show to be indistinguishable
from P . We denote our c colors by the elements of{(0, 0)} ∪ {(a, b) | 1 ≤ a ≤ π1 , 1 ≤ b ≤ π2 , a, b ∈ N} .

Here, π1 is the number of distinct structures of vocabulary τ with exactly t elements, π1 := 2

∑s

i=1 t

ai

. Similarly, we denote by π2 the number of ways it is possible

to “connect” or “add” a single element to some existing, fixed t-element structureof vocabulary τ , i.e., π2 := 2∑si=1∑ai −1j=1(aji )tai −j . We will use fixed enumerationsof these π1 structures with t elements and π2 ways of connecting an additional
element to a fixed t element structure.
We impose on the coloring of the structure the following restrictions. Each canbe expressed by prohibiting finite sets of colored induced substructures.
(1) The color (0, 0) may be used at most t times. Therefore, we prohibit all(t + 1)-element structures that are colored completely with (0, 0).5
(2) The graph must be colored using only {(0, 0)} ∪ {(a, b) | 1 ≤ b ≤ π2 } forsome fixed a ∈ {1, . . . , π1 }. Therefore, we prohibit all two-element structurescolored ((a, b), (a′ , b′ )) with a ̸= a′ .
(3) We now consider some fixed coloring of a u-element structure V , whose
universe we identify with {v1 , . . . , vu }. We assume that this coloring satisfies
the previous restriction and that color (0, 0) does not appear. We must
decide whether to prohibit this structure. In order to do so, we first take the5Note that introducing a constraint guaranteeing the existence of t such elements cannot bedone by forbidding finite sets of structures, and would result in a non-hereditary property.

51

CHAPTER 4. TESTABLE CLASSES
fixed a guaranteed by the previous restriction, and consider the t-element
structure E, whose universe we identify with {e1 , . . . , et }, that is the ath
structure in our enumeration of t element structures. We connect each vi to
E in the following way. If vi is colored (a, b), we use the bth way of connecting
an additional element to a t-element structure in our enumeration. We denote
the resulting (t + u)-element structure as M and allow (do not prohibit) V
iﬀ M is a model of ψ when we replace xi with ui and yj with vj .
We now show that the resulting F -colorability problem is indistinguishable
from P . Recall the definition of indistinguishability (Definition 14) and assume
that we are given an A |= φ. Color the t vertices existentially bound to the xi with
(0, 0). Then, we can color all remaining vertices vi with (a, b), where a corresponds
to the substructure induced by {x1 , . . . , xt } in our enumeration of t-element structures, and b corresponds to the connection between vi and {x1 , . . . , xt }. It is easy
to see that this coloring satisfies the restrictions of our F -colorability problem. We
have not made any modifications to the structure and so clearly mrdist(A, PF ) = 0(i.e., A ∈ PF ).
Next, we assume that we are given a structure with a coloring that satisfies ourrestrictions. We will show that we can obtain a model of φ by making only a small
number of modifications. First, if there are less than t elements colored (0, 0), we
arbitrarily choose additional elements to color (0, 0) so that there are exactly tsuch elements. We will denote these t elements with {e1 , . . . , et }. Restriction (2)guarantees that all colors which are not (0, 0) share the same first component.
Let a be this shared component. We make the structure induced by {e1 , . . . , et }identical to the ath structure in our enumeration of t-element structures, requiring52

4.2. RAMSEY’S CLASS
at most

∑s

i=1 t

ai

= O(1) modifications. Next, for each element vi that is colored(a, b) with a, b ̸= 0, we modify the connections between vi and {e1 , . . . , et } in orderto make these connections identical to the bth way of making such connections in
our enumeration. This requires at most])r a∑i −1 [(∑
ai ai −j(n − t)t= O(n)j
i=1 j=1
additional modifications, all of which are to non-monadic subrelations. Binding xi
to ei , the resulting structure is a model of φ. We made at most O(1) modifications
to monadic subrelations and O(n) modifications to non-monadic subrelations, andso mrdist(A, P ) ≤ max{O(1)/n, O(n)/Ω(n2 )} = o(1) < ε, where the inequality
holds for suﬃciently large n.
Therefore, all such properties P are indistinguishable from instances of F colorability, as desired.

Lemma 11

Recall that a hereditary property of relational structures is one which is closed
under taking induced substructures. F -colorability is clearly a hereditary property;
if A is F -colorable, then so are its induced substructures. However, the definitionsof Austin and Tao [11] are significantly diﬀerent from ours and so we explicitly
reduce the following translation in our setting to their result.
Theorem 6 (Translation of Austin and Tao). Let P be a hereditary property ofrelational structures which is closed under isomorphisms. Then, property P is
testable in the sense of Tmr with one-sided error.
Theorem 6 is, in a sense, the latest in a series of generalizations of Corollary 6.3of Alon et al. [3], i.e., the testability of colorability problems for undirected loop53

CHAPTER 4. TESTABLE CLASSES
free graphs. The first such generalization was by Fischer [20], who extended theresult to more general colorability problems with counting restrictions. This wasfollowed by Alon and Shapira [8] who extended it to hereditary graph properties.
Ishigami [37] extended the testability result to hereditary partite uniform hypergraph properties, and Rödl and Schacht [57] extended it to hereditary uniform
hypergraph properties. These generalizations are closely related to extensions of
Szemerédi’s Regularity Lemma and the Removal Lemma, see the references in
Section 1.1.
Before reducing Theorem 6 to its statement in [11], we first briefly introduce
their definitions. All of the definitions in Subsection 4.2 are from Austin and
Tao [11], although we omit definitions which are not necessary for our purposes.

Framework of Austin and Tao
We begin by introducing their analogue of vocabularies: finite palettes.
Definition 17. A finite palette K is a sequence K := (Kj )∞j=0 of finite sets, ofwhich all but finitely-many are singletons. The singletons are called points anddenoted pt. A point is called trailing if it occurs after all non-points.
We will write K = (K0 , . . . , Kk ), omitting trailing points and call k the orderof K. We use the elements of Kj to color the j-ary edges in hypergraphs.
Definition 18. A vertex set V is any set which is at most countable. If V, W arevertex sets, then a morphism f from W to V is any injective map f : W → V andthe set of such morphisms is denoted Inj(W, V ). For N ∈ N, we denote the set{1, . . . , N } by [N ].
54

4.2. RAMSEY’S CLASS
Of course, [N ] is a vertex set. Our structures are finite so we are mostly interested in finite vertex sets. Next, we define the analogue of relational structures.
Definition 19. Let V be a vertex set and K be a finite palette. A K-colored
hypergraph G on V is a sequence G := (G)∞j=0 , where each Gj : Inj([j], V ) → Kj
is a function. Let K (V ) be the set of K-colored hypergraphs on V .
Only finitely many of the Kj are not points, and so only finitely many Gj are
non-trivial. The Gj assign colors from Kj to the morphisms in Inj([j], V ). In
our relational setting, this set of morphisms corresponds to the set of j-ary tuples(x1 , . . . , xj ) with pairwise distinct components.
Before defining hereditary K-properties, we need one last technical definition.
Definition 20. Let V, W be vertex sets and f ∈ Inj(W, V ) be a morphism from
W to V . The pullback map K (f ) : K (V ) → K (W ) is()
K (f ) (G) j (g) := Gj (f ◦ g) ,(V )for all G = (Gj )∞, j ≥ 0 and g ∈ Inj([j], W )). If W ⊆ V and f ∈j=0 ∈ K

Inj(W, V ) is the identity map on W , we abbreviate

G ⇂W := K (f ) .

Abusing notation, the pullback map K (f ) maps K-colored hypergraphs on V to
those on W , by assigning the color of f ◦ g to g, for all tuples g. Note that G ⇂W
is equivalent to the induced subhypergraph on W . For clarity, we reserve P for
properties of relational structures and use P to denote properties of hypergraphs.
55

CHAPTER 4. TESTABLE CLASSES
Definition 21. Let K = (Kj )∞j=0 be a finite palette. A hereditary K-property P is
an assignment P : V 7→ P (V ) of a collection P (V ) ⊆ K (V ) of K-colored hypergraphs
for every finite vertex set V such that for every morphism f ∈ Inj(W, V ) between
finite vertex sets,
K (f ) (P (V ) ) ⊆ P (W ) .
Finally, we state the definition of (one-sided error) testability used by Austin( )and Tao [11]. For vertex set V and c ∈ N, we write Vc := {V ′ | V ′ ⊆ V, |V ′ | = c}to denote the set of subsets of V with exactly c elements.
Definition 22. Let K be a finite palette with order k ≥ 0 and P be a hereditary
K-property. Property P is testable with one-sided error if for every ε > 0, there
exists N ≥ 1 and δ > 0 satisfying the following. For all vertex sets V with |V | ≥ N ,if G ∈ K (V ) satisfies
{

1

(V )
N

( )
}
V
(W )
W |W ∈, G ⇂W ∈ P≥ 1−δ,
N(4.1)

then there exists a G′ ∈ P (V ) satisfying
1

(V )
k

{

( )
}
V
′
W |W ∈, G ⇂W ̸= G ⇂W
≤ ε.
k

(4.2)

To see that this is a variant of testability, it is easiest to consider the contrapositive. If there is a G′ satisfying (4.2), then G is not ε-far from P, using the implicit
distance measure based on the fraction of diﬀering induced subhypergraphs withsize k. If there is no such G′ (i.e., G is ε-far from P) and P is testable, then (4.1)
must not hold. That is, there are many induced subhypergraphs of size N that do

56

4.2. RAMSEY’S CLASS
not have P. The definition is for hereditary P, and so if G has P, then so do all
induced subhypergraphs. This allows the construction of testers.
Finally, we can state one of the main results of Austin and Tao [11].
Theorem 7 (Austin and Tao [11]). Let K be a finite palette and let P be ahereditary K-property. Then, P is testable with one-sided error.
In the following subsection we will map our vocabularies, structures and properties to this setting. We will then show that hereditary properties in our setting
correspond to hereditary properties (in the sense of Definition 21 above) here, andthat testability in the sense of this section (Definition 22) implies testability ofthe original relational properties. That is, we explicitly reduce our translation(Theorem 6) to Theorem 7.

Reducing Theorem 6 to Theorem 7
To begin, we map vocabulary τ = {R1a1 , . . . , Rsas } to finite palette Kτ = (Ki )∞i=0 .
We use the color of a “tuple” to represent the set of assignments on it. The difference between the set of j-ary tuples over a finite universe U and Inj([j], U ) isthat the latter does not permit repeated components. If S ∈ SUB(Riai ) is suchthat |S| < ai , the corresponding subrelation consists of tuples with repeated components. We treat such S as relations with arity |S| and no repeated components.
Recall that S(n, k) is the Stirling number of the second kind.
For a ≥ 1, let Pa := {Riai | Riai ∈ τ, ai = a} be the set of predicate symbols with[ ∑i]
|Pj |S(j,i)
jarity a. We now define palette K. Let K0 := pt and Ki := 2
. Thereare finitely-many predicate symbols and so only finitely-many Ki ̸= pt.
57

CHAPTER 4. TESTABLE CLASSESLet Sa := {Sai | Sai ∈ SUB(Riai ), |Sai | = a, 1 ≤ i ≤ s} be the set of subtypes withcardinality a for all a ≥ 1. Now, 2|Sa | = |Ka | and we have exactly enough colors
to encode the set of assignments of the a-ary subtypes on a-ary tuples.
We will now define a map h from relational structures A on universe U to
hypergraphs GA ∈ K (U ) . For any Sai ∈ Sa , there is a bijectionr(Sai ) : sU (Sai ) → {(x1 , . . . , xa ) | xi ∈ U, xi ̸= xj for i ̸= j}from sU (Sai ) to the a-ary tuples without duplicate components, formed by removing
the duplicate components. That is, r(Sai ) maps (x1 , . . . , xai ) to (xi1 , . . . , xia ) where1 ≤ i1 < i2 < . . . < ia ≤ ai . We can now define GA = h(A).
For j > 0, we define Gj : Inj([j], U ) → Kj as follows. Assign to f ∈ Inj([j], U )the color encoding the set of assignments of the subtypes Sj on (f (1), . . . , f (j)),
using the inverses (r(Sji ))−1 to get assignments for subtypes of high-arity relations.
For j = 0, Inj([j], U ) = ∅ and K0 = pt and we can use a trivial map.
Of course, we extend the map to properties in the obvious way. If P is aproperty of relational structures, we let P (U ) := {h(A) | A ∈ P }. Formally, wedefine P(U ) := P (U ) , but there is a small technical point. We have identified
finite universes with subsets of the naturals, allowing us to call STRUC (τ ) a set.
However, Definition 18 in this section allows a vertex set to be any finite set
and Definition 21 requires hereditary hypergraph properties to be closed underbijections between vertex sets. To remedy this, for each finite vertex set W , we fix

58

4.2. RAMSEY’S CLASS
a6 bijection g W : W → {0, . . . , |W | − 1}. We then define P := h(P ) formally asP(W ) :=


P (W ) ,if W = {0, 1, . . . , |W | − 1};


)

W (

K (g ) P ({0,...,|W |−1}) , otherwise.

Hereditary relational properties are mapped to hereditary hypergraph properties, which are testable in the sense of this section (Definition 22 above) by
Theorem 7.
Lemma 12. If P is a hereditary property of relational structures, then h(P ) is ahereditary property of hypergraphs.
Proof (Lemma 12). Let P be a hereditary property of relational structures withvocabulary τ . Assume that P := h(P ) is not a hereditary K-property. Then,by Definition 21 above, there exist finite vertex sets V and W , and a morphismf ′ ∈ Inj(W, V ) such that
K (f ) (P (V ) ) ̸⊆ P (W ) .

(4.3)

Since f ′ exists, Inj(W, V ) cannot be the empty set and so |V | ≥ |W |. Let
UV := {0, . . . , |V | − 1} and UW := {0, . . . , |W | − 1}. By the definition of P, we can)(V
fix bijections g V : V → UV and g W : W → UW such that P (V ) = K (g ) P (UV ))W (and P (W ) = K (g ) P (UW ) . By the definition of P = h(P ), this implies

K

6

(f )

(

)
( (U ) ))
W (
gV )
(
̸⊆ K (g ) P (UW ) .
K
P V

Our properties are closed under isomorphisms, so any fixed bijection is acceptable.

59

CHAPTER 4. TESTABLE CLASSES
Bijections are invertible, and so this implies

K

(
)
−1 (
g V ◦f ◦(g W ))P (UV ) ⊆
̸ P (UW ) .

( )−1
Rename f ′ := g V ◦ f ◦ g W
and note f ′ ∈ Inj(UW , UV ). Let A′ ∈ P (UV ) be such′that K (f ) (A′ ) ̸∈ P (UW ) .
We defined P as h(P ) for a hereditary property P of relational structures. Property P is closed under isomorphisms, and so there is an

A := h−1 (A′ ) ∈ P ∩ STRUC |UV | (τ )such that the |UW |-element structure induced by {a | a = f ′ (u) for some u ∈ Uw }does not have P . This contradicts the hereditariness of P and so P must be
hereditary in the sense of this section (Definition 21).
Lemma 12We mapped hereditary relational properties to hereditary hypergraph properties,
which are testable by Theorem 7. We will show this implies testability of theoriginal properties.
Definition 23. Let A, B ∈ STRUC n (τ ) be structures with vocabulary τ and universe U := {0, . . . , n − 1} of size n, k := maxi ai be the maximum arity of thepredicate symbols, and h : STRUC n (τ ) → K (U ) be the map defined above. The
h-distance between A and B is1

hdist(A, B) := (U )
k

60

{

( )
}
U
.
W |W ∈, h(A) ⇂W ̸= h(B) ⇂W
k4.2. RAMSEY’S CLASS
We now relate the two distances with the following simple lemma.
Lemma 13. Let A, B ∈ STRUC n (τ ) be relational structures with vocabulary τand size n. Then, hdist(A, B) ≥ mrdist(A, B).
Proof (Lemma 13). Assume that mrdist(A, B) = ε. Then, there exists a predicate
symbol Riai ∈ τ and subtype S ∈ SUB(Riai ) such thatsA (S) △ sB (S) /(n!/(n − |S|)!) = ε .

Let k := maxi ai and let the universe of both structures be Un := {0, . . . , n − 1}.
Consider a random permutation of the universe (i.e., a bijection r : Un → Un )chosen uniformly from the set of such permutations. The probability that thesubstructures induced on {r(0), . . . , r(k − 1)} diﬀer in A and B is hdist(A, B).
The probability that the tuple of the first |S| elements, i.e. (r(0), . . . , r(|S| − 1)),
diﬀer in sA (S) and sB (S) is ε and so hdist(A, B) ≥ ε.

Lemma 13Equality is obtained when |S| = k. It is possible to show that the two distances
diﬀer by at most a constant factor, and so the corresponding notions of testability
are essentially equivalent. However, Lemma 13 suﬃces for our purposes.
Lemma 14. Let P ⊆ STRUC (τ ) be a property of relational structures which ismapped by h to a property of hypergraphs that is testable with one-sided error.
Then, P is testable with one-sided error.
Proof (Lemma 14). Let P := h(P ) be the hypergraph property which P maps to.
We show that the following is an ε-tester for P with one-sided error. Let N ≥ 1,

61

CHAPTER 4. TESTABLE CLASSES
δ > 0 be the constants of Definition 22 above for ε. Assume that we are testing a
structure A ∈ STRUC n (τ ) and recall that U = {0, . . . , n − 1}.
1. If #(A) ≤ N , query the entire structure and decide exactly whether A ∈ P .
2. Otherwise, repeat the following q(δ) times.
(a) Uniformly select N elements and query the induced substructure.
(b) If it has P , continue. Otherwise, reject.
3. Accept if all of the induced substructures had P .
If A ∈ P , then all induced substructures have P because P is hereditary andthe tester accepts with probability 1. Next, assume mrdist(A, P ) > ε. We use
Definition 22 above to show the tester will find a witness for A ̸∈ P with probability
at least 2/3. By Lemma 13, hdist(A, P ) ≥ mrdist(A, P ) > ε. We assumed h(P ) is
hereditary, and so (by Theorem 7) it is testable in the sense of Definition 22. The
probability that a uniformly chosen N -element substructure does not have P is atleast δ. We use q(δ) to amplify the success probability from δ to 2/3.
Lemma 14This completes the proof of the testability of Ramsey’s class (Theorem 5). All
properties expressible in Ramsey’s class are indistinguishable from instances ofF -colorability. Indistinguishability preserves testability and so it suﬃced to showthat these instances are testable. All instances of F -colorability are hereditary
relational properties, which are testable by Theorem 6, which we reduced to thestatement by Austin and Tao [11].

624.3. SUMMARY

4.3

Summary

We proved the testability of two classes in this chapter. In Section 4.1, we usedmodel-theoretic techniques to prove testability for Ackermann’s class with equality
and explicitly constructed testers for each formula in the class. This result first
appeared in [38] with two-sided error, and the improved (i.e., one-sided) version
proven here will appear in [42].
In Section 4.2, we used a reduction to a strong result by Austin and Tao [11] toprove testability for Ramsey’s class. This extends a result of Alon et al. [3] fromloop-free, undirected graphs to relational structures, and answers a question of
Fischer [20] (who asked whether the hypergraph properties expressible with prefix∃∗ ∀∗ are testable). This result first appeared in [39], and will also appear in [42].
It is interesting to consider the query complexities for these two classes. In
particular, our construction for Ramsey’s class gives a tremendous dependence onε (towers of 1/ε). Improving the query complexity for Ramsey’s class is diﬃcult,and is closely linked to open problems in extremal (hyper)graph theory (see theConclusion in Chapter 6).

63

Chapter 5
Untestable Classes
In the previous chapter, we saw that two large syntactic classes of first-order logic
are testable. However, there are also first-order properties that are not testable.
In this chapter, we prove that several classes are untestable.

5.1

Untestable Properties in [∀3∃, (0, 1)]=

As mentioned in Subsection 1.1.1, Alon et al. [3] proved that there exists anuntestable property of undirected, loop-free graphs expressible with quantifier prefix ∀12 ∃5 . In this section, we simplify their untestable example and thereby showthat the classes [∀3 ∃, (0, 1)]= , [∀2 ∃∀, (0, 1)]= , [∀∃∀2 , (0, 1)]= and [∀∃∀∃, (0, 1)]= areuntestable. The focus on graphs is justified by recalling that monadic first-orderlogic is testable.
We will improve on three of these prefixes in Section 5.2, where we prove that
there are untestable properties in [∀∃∀, (0, 1)]= . However, we still need Theorem 8
for the prefix [∀3 ∃, (0, 1)]= and we present it first due to its relative simplicity.
645.1. UNTESTABLE PROPERTIES IN [∀3 ∃, (0, 1)]=
The class [∀3 ∃, (0, 1)] (usually without equality) is well-known in the literature.
It is trivial to prove that this class does not have the finite model property. In
addition, Kolaitis and Vardi [45] showed that a 0-1 law does not hold for secondorder existential logic when the first order part is in this class (even without
equality). However, it is an essentially finite class (i.e., it can only express a finite
number of properties up to logical equivalence) and therefore decidable.
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 15 that P is indistinguishable
from property Pf (cf. Definition 25 below) which is expressible in any of the prefix
vocabulary classes mentioned in Theorem 8 below. We will then show that P is
not testable. Indistinguishability preserves testability and so this implies that Pf
is also untestable, which will suﬃce to show the following theorem.
Theorem 8. The following prefix classes are not testable:1.

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

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

[∀2 ∃∀, (0, 1)]=4.

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

We define property P as follows. First, a graph that has property P must consistof an even number of vertices, of which exactly half have loops. The subgraphinduced by the vertices with loops must be isomorphic to that induced by thevertices without loops, ignoring all loops, and there must be no edges connecting
65CHAPTER 5. UNTESTABLE CLASSES
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 undirectededges as paired edges.
Definition 24. A graph G ∈ G n has P iﬀ the following conditions are satisfied:
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 allloops 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) iﬀ 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 . This of course reduces the complexity from the levelof finding an isomorphism to the level of checking a given one, in order to achieve
first-order expressivity. However, it maintains hardness for testability: essentially,
our samples are too small to see any part of the given isomorphism.
Definition 25. A graph G ∈ G n has Pf iﬀ 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).
66

5.1. UNTESTABLE PROPERTIES IN [∀3 ∃, (0, 1)]=
2. For every vertex x, if ¬E(x, x) then there is an edge from x to exactly one ysuch that E(y, y).
3. For all vertices x and y, E(x, y) iﬀ 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 ) iﬀ 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 by∀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 ̸= x3 ∧ ¬E(x4 , x4 ) ∧ E(x3 , x4 )] →)](¬E(x2 , x2 ) ∧ E(x1 , x2 ) ∧ (E(x1 , x3 ) ↔ E(x2 , x4 ))) .

To express Pf with prefixes ∀2 ∃∀ and ∀∃∀2 , it suﬃces to reorder the quantifiers(keeping x2 existential and x1 first). The prefix ∀∃∀∃ requires a few additional
modifications.
The two properties P and Pf diﬀer only in the edges which make the isomorphism explicit in Pf but are forbidden in P . There are at most n such edges, none67CHAPTER 5. UNTESTABLE CLASSES
of which are loops. This suﬃces to prove the following.
Lemma 15. Properties P and Pf are indistinguishable.
Proof (Lemma 15). Let ε > 0 be arbitrary and let Nε = ε−1 . Assume that G
is a structure that 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 of Definition 24. For all x ∈ H1 , we add the edges E(x, f (x)) and E(f (x), x) and callthe result G′ . Property Pf diﬀers from P only in that the isomorphism is madeexplicit by the edges connecting loops and non-loops, and so G′ has Pf . Indeed, itsatisfies Conditions 1 and 2 of Definition 25 because G had no edges between loops
and non-loops and we have connected each to exactly one of the other, following
the bijection f . Next, G′ satisfies Condition 3 of Definition 25 because G satisfied
Condition 5 of Definition 24 and we added only paired edges. Finally, G′ satisfies
Condition 4 of Definition 25 because the edges between loops and non-loops follow
the isomorphism f from Condition 3 of Definition 24.
We have added exactly n (directed) edges, none of which are loops and so wehave mrdist(G, P ) ≤ mrdist(G, G′ ) = 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 theisomorphism f .

Lemma 15

Properties P and Pf are indistinguishable. We saw in Section 3.3 that testability
is preserved by indistinguishability (cf. Theorem 7) and thus showing that P is
not testable suﬃces to prove that Pf is not testable (and therefore Theorem 8).
68

5.1. UNTESTABLE PROPERTIES IN [∀3 ∃, (0, 1)]=The proof closely follows that of Alon et al. [3]. The crucial lemma is the following,
a combination of Lemmata 7.3 and 7.4 from Alon et al. [3]. We use countH (T ) to
refer to the number 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 U1and U2 such that there are no edges “internal” to the partitions. That is, for all
x1 , y1 ∈ U1 and x2 , y2 ∈ U2 , ¬E(x1 , y1 ) and ¬E(x2 , y2 ).
Lemma 16 (Alon et al. [3]). There exists a constant ε′ > 0 such that for every
D ∈ N, there exist two undirected bipartite graphs H = H(D) and H ′ = H ′ (D),and a number t satisfying the following conditions.
1. Both H and H ′ have a bipartition into classes U1 and U2 , each of size t.
2. In both H and H ′ , 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 ′ is at least t/3.
4. dist(H, H ′ ) ≥ ε′ .
5. For all D-element graphs T , countH (T ) = countH ′ (T ).
Lemma 16 is due to Alon et al. [3], although they only sketch the proof. We
include a complete proof here for completeness.

5.1.1

Proof of Lemma 16

We follow the proof outlined by Alon et al. [3] and begin with their proof of thefollowing simple lemma.
69CHAPTER 5. UNTESTABLE CLASSES
Lemma 17 (Alon et al. [3]). There exist constants ε and N such that every graph2

H with n > N (labelled) vertices is ε-far from all but at most 2n /5 other graphswith the same vertex set.
Proof (Lemma 17). Choose an ε < 1/2 such that( e )εε< 21/10 and an N > ε−12such that nn < 2n /10 for n > N . The number of graphs that are less than ε-far
from a given H with n > N vertices is at mostn!

εn2 ((n))
∑
2

i

i=0

(5.1)

.

( ) ( ) (a−1)( n2 )
We apply the identity ab = a−1+ b inductively to εn
2 . A simple inductiveb−1
proof shows that applying this identity once to each term, repeating for a levels,( n2 ) ∑a (a)( n2 −a )gives εn= i=0 i εn2 −i =: L(a), and so
2
(

n2
εn2

)
= L(n) =)n ( )( 2
∑
n
n −n
i=0

i

εn2 − i.

(5.2)

∑n ( n )= 2n , there are 2n > εn2 total “terms” in the summation.
∑ 2 ((n))
2Each term in the summation εn
can therefore be paired with a term fromi=0
iRecalling thati=0i(5.2) that upper-bounds it. Combining with (5.1), we see that the number ofgraphs that are less than ε-far from H is less than
( 2)( )εn2n
2n e<n< 2n /5 ,n!
2εnεas desired.

Lemma 17

Next, we show that most (suﬃciently large) bipartite graphs satisfy Conditions 2
and 3 of Lemma 16. We use the following statement of Chernoﬀ bounds (see70

5.1. UNTESTABLE PROPERTIES IN [∀3 ∃, (0, 1)]=
Appendix A of Alon and Spencer [10]);

Pr[X < a] ≤ E[e−λX ]eλa ,(5.3)

where λ is chosen to optimize the bound, and also the following lemma.
Lemma 18 (Lemma A.1.5 in Alon and Spencer [10]).
eλ + e−λ2= cosh(λ) ≤ eλ /2 .
2

(5.4)

Lemma 19 (Alon et al. [3]). There exists an N ′ such that for n > N ′ , at least
1 n2
2 of the bipartite graphs with a given (labeled) bipartition U1 , U2 where |U1 | =2|U2 | = n satisfy both of the following conditions.
(191) The minimum degree is at least n/3.
(192) For every subset X of U1 ∪ U2 with size n/3 ≤ |X| ≤ n, there are more thann2 /18 edges between X and (U1 ∪ U2 )\X.
Proof (Lemma 19). We let G be a random bipartite graph with a given, labeled
bipartition U1 , U2 chosen in the following way. Each possible edge (u, v) ∈ U1 × U2
is placed independently and uniformly with probability 1/2. There are n2 possible
2edges, and so each of the 2n possible such bipartite graphs is generated withequal probability. The probability of G satisfying (19.1) and (19.2) above is (bydefinition)|{H | H is such a graph that satisfies (19.1) and (19.2)}|
.
2n2

71

CHAPTER 5. UNTESTABLE CLASSES
We want a lower-bound on the number of such graphs, or equivalently a lower2

2

bound on Pr[G satisfies (19.1) and (19.2)]·2n that is greater than 12 2n . It suﬃces
therefore to show that this probability is at least 1/2. Using the union bound,
Pr[G satisfies (19.1) and (19.2)] ≥1 − Pr[G does not satisfy (19.1)] − Pr[G does not satisfy (19.2)] .

We will show in Claims 1 and 2 that this is at least 1 − o(1) > 1/2, where theinequality holds for suﬃciently large N ′ . We will let U = U1 ∪ U2 be the set of allvertices.
Claim 1. Pr[G does not satisfy (19.1)] = o(1).
Proof (Claim 1). Let deg(v) be the degree of a vertex v. By the union bound,

Pr[G does not satisfy (19.1)] ≤∑Pr[deg(v) ≤ n/3].

v∈U

Let Nuv be an “indicator” variable for the event that there is an edge E(u, v)
which is normalized to take the following values,−1, if ¬E(u, v);
Nuv := 1, if E(u, v).

Then, deg(v) ≤ n/3 iﬀ

Yv :=

∑
{u|u∈U1 if v∈U2 , u∈U2 if v∈U1 }72

Nuv ≤ −n/3 ,(5.5)

5.1. UNTESTABLE PROPERTIES IN [∀3 ∃, (0, 1)]=and so∑v∈U Pr[deg(v)≤ n/3] =∑v∈U Pr[Yv≤ −n/3]. We apply (5.3) andLemma 18, and so

Pr[Yv ≤ −n/3] ≤ E[e−λYv ]e−λn/3 = cosh(λ)e−λn/3 ≤ eλ n/2−λn/3 .
2Minimizing the bound by setting λ = 1/3 gives

Pr[G does not satisfy (19.1)] ≤ (2n)e−n/18 = o(1) ,as desired.

Claim 1Claim 2. Pr[G does not satisfy (19.2)] = o(1).
Proof (Claim 2). By the union bound,∑

Pr[G does not satisfy (19.2)] ≤Pr[G violates (19.2) with X] .

{X|X⊆U,n/3≤|X|≤n}(5.6)
Let a := |X ∩ U1 |, b := |X ∩ U2 |, i := a + b = |X|. As in (5.5), we let Nuv
be a normalized indicator for the event E(u, v). Let YX :=∑{u,v|u∈X,v∈U \X} Nuv .

Then, G violates (19.2) with X iﬀ YX < −i(2n − i) + n2 /9. Using again (5.3),∑

Pr[G violates (19.2) with X]=

Pr[YX < −i(2n − i) + n2 /9]≤E[e−λYX ]eλ(−i(2n−i)+n /9)={X|X⊆U,n/3≤|X|≤n}∑{X|X⊆U,n/3≤|X|≤n}∑2{X|X⊆U,n/3≤|X|≤n}∑∏E[e−λNuv ]eλ(−i(2n−i)+n /9) .
2

(5.7)

{X|X⊆U,n/3≤|X|≤n} {u,v|u∈X,v∈U \X}73

CHAPTER 5. UNTESTABLE CLASSES
We can divide the product into four cases,





∏



∏



−λNuv

e +e
2

−λ



eλ  ·
∏



]=



{u,v|u∈X∩U2 ,v∈U2 \X}
λ{u,v|u∈X∩U1 ,v∈U2 \X}{u,v|u∈X,v∈U \X} E[e∏eλ  

{u,v|u∈X∩U1 ,v∈U1 \X}



∏

λ

{u,v|u∈X∩U2 ,v∈U1 \X}

−λ

e +e
2


.

Recalling Lemma 18 and combining with (5.7), Pr[G does not satisfy (19.2)] ≤()
22
λ(a(n−a)+b(n−b))+ λ2 (a(n−b)+b(n−a))+λ −i(2n−i)+ n9

∑

e

.

(5.8)

{X⊆U |n/3≤|X|≤n}

There are at most(n)( n )ai−achoices of X with size i when a = |X ∩ U1 | andb = i − a = |X ∩ U2 |, and so after simplifying, (5.8) is at most)i ( )(
n
∑
∑
λ2
n
n
2
2
2
eλ(2ai+n /9−2a −in)+ 2 (2a +in−2ai) .
a
i−a
a=0

(5.9)

i=⌈n/3⌉Using the simple bound
i
n
∑
∑

(n )
k

≤

( en )kk, we get that (5.9) is at mostλ2

ei+a ln(n/a)+(i−a) ln(n/(i−a))+λ(2ai+n /9−2a −in)+ 2 (2a +in−2ai) .
2

2

2(5.10)

i=⌈n/3⌉ a=0

Let us consider 2ai + n2 /9 − 2a2 − in. If a ≥ 5n/6, thenn2 25 2n2
2
− 2a − in ≤ 2in +− n − in
2ai +
9
9
18
5 2
≤ − n = −Θ(n2 ) .
18
If a < 5n/6, then the maximum of 2ai + n2 /9 − 2a2 − in occurs at a = i/2.

74

5.1. UNTESTABLE PROPERTIES IN [∀3 ∃, (0, 1)]=
Therefore,

2ai +

n2
n2 i 2i2 n2− 2a2 − in ≤ i2 +− − in = +
− in
9
9
2
2
9
n2 n2 n2n2≤+−
= − = −Θ(n2 ) ,
18
9
3
6

because the maximum occurs at the boundary i = n/3. Applying these bounds,(5.10) is at most
n
i
∑
∑

λ2

ei+a ln(n/a)+(i−a) ln(n/(i−a))+λ(−n /6)+ 2 (2a +in−2ai) .
2

2(5.11)

i=⌈n/3⌉ a=0√
Choosing the non-optimal λ = 1/ n and looking only at asymptotics, we see from
(5.11) that Pr[G does not satisfy (19.2)] ≤
i
n
∑
∑

3/2
3/2
eO(n)+O(n ln n)−Θ(n )+O(n) = O(n2 )e−Θ(n ) = o(1) .

i=⌈n/3⌉ a=0

Claim 2
Lemma 19

The two claims combine to give the lemma.

We are now ready to complete the proof of Lemma 16. We let ε′ be the ε ofLemma 17, and choose a suﬃciently large s = 2n > max(N, 2N ′ ) where N and N ′D
are from Lemmata 17 and 19 respectively. There are at most E := 2( 2 ) graphs

on D vertices and each appears at most sD times as an induced subgraph in aDgraph on s vertices. An “appearance count” for a graph is an 2( 2 ) -tuple giving, foreach of the possible graphs on D vertices, the number of appearances as an induced
subgraph. There are therefore at most (sD )E = 2DE log s many distinct appearance
2

counts (tuples). By Lemma 19, there are at least 21 2n bipartite graphs satisfying75CHAPTER 5. UNTESTABLE CLASSES
the conditions of that lemma, and
1 n2
2
2
2
2
2 = 2s /4−1 = 2s /20−1 2s /5 > 2DE log s 2s /5 ,2
where the inequality holds for suﬃciently large s.
There are at most 2DE log s distinct appearance counts and so there must be some2

appearance count shared by more than 2s /5 of the above graphs. By Lemma 17,
there must be two such graphs (satisfying the conditions of Lemma 19 and withthe same appearance count) that are ε-far from each other. This completes theproof of Lemma 16.

5.1.2

Completing the Proof of Theorem 8

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 in pairededges. 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 of size at
most D. This is done by applying the following lemma inductively.
Lemma 20. Let H and H ′ be two graphs, both of size s, and let 2 < D ≤ s. If
for every graph T of size D, countH (T ) = countH ′ (T ), then for every graph T ′ ofsize D − 1, countH (T ′ ) = countH ′ (T ′ ).
Proof (Lemma 20). Assume H and H ′ satisfy the initial conditions of Lemma 20,
but that there exists a T ′ of size D − 1 such that countH (T ′ ) ̸= countH ′ (T ′ ). Let
C = {T | #(T ) = D and T contains T ′ as an induced subgraph}.

765.1. UNTESTABLE PROPERTIES IN [∀3 ∃, (0, 1)]=
Note that∑∑′′
T ∈C countH (T ) countT (T ) = countH (T )(s − D + 1) and likewise for′
T ∈C countH ′ (T ) countT (T ).

We assumed that H and H ′ satisfy countH (T ) =countH ′ (T ) for T ∈ C, but countH (T ′ ) ̸= countH ′ (T ′ ), giving a contradiction andLemma 20

the Lemma follows.
Lemma 21. Property P is not testable.

Proof (Lemma 21). Assume that P is testable. Then, there exists an ε-tester for

ε := min {ε′ /8, 1/144} ,where ε′ is the constant from Lemma 16 above. We can assume without loss ofgenerality that the tester queries all edges in a random sample of D := D(ε)
vertices.
Consider the graph G which contains two copies of H = H(D) from Lemma 16,
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 G′ which contains one
copy of H marked by loops and one copy of H ′ , again where there are no edges
between the two (induced) subgraphs. Graph G′ is such that dist(G′ , P ) ≥ ε (cf.
Lemma 22 above) and so it must be rejected with probability at least 2/3. Both G
and G′ consist of two bipartite graphs, each of which has a bipartition into twoclasses of size t, and so #(G) = #(G′ ) = 4t.
However, G and G′ 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 D77

CHAPTER 5. UNTESTABLE CLASSES
vertices must be in the first copy of H and the others in the second H (resp. H ′ ).
By Lemma 20 above, H and H ′ contain the same number of each induced subgraphwith size at most D. The tester therefore obtains any fixed sample with the sameprobability in G and G′ and is unable to distinguish between them. Hence, it isunable to accept G with probability 2/3 and also reject G′ with probability 2/3.
This completes the proof, taking into account Lemma 22 below.

Lemma 21

Recall that testing is easiest under the dist definition, and so Lemma 21 also
implies P is not testable under other definitions.
Lemma 22. The graph G′ is such that dist(G′ , P ) ≥ ε.
Proof (Lemma 22). Suppose that dist(G′ , P ) < ε. Then, there is an M ∈ P suchthat dist(G′ , M ) < ε. Let M1 be the set of vertices with loops in M and let M2
be the set of vertices without loops. We will refer to the subgraph induced by thevertices with loops in G′ as H and to that induced by those without loops as H ′ .
Without loss of generality, assume that |M1 ∩ H| ≥ |M1 ∩ H ′ |. Then, |M1 ∩ H| ≥ t.
We let α1 be the set M1 \H and α2 be M2 \H ′ . Note that |α1 | = |α2 | and |α1 | ≤ tbecause |M1 ∩ H| ≥ t.
Informally, M is formed by moving vertices α1 from H ′ to H and vertices α2from H to H ′ , and then possibly making other changes. There are three cases,
which we will consider in order.
1. |α1 | = 0.
2. |α1 | ≥ t/3.
3. 0 < |α1 | < t/3.
78

5.1. UNTESTABLE PROPERTIES IN [∀3 ∃, (0, 1)]=
If |α1 | = 0, then we can construct M from G′ without exchanging vertices
between H and H ′ , and in particular, construct H ′ from H (ignoring loops), bymaking less than ε(4t)2 modifications. However, dist(H, H ′ ) ≥ ε′ by Lemma 16
above and so this must require at least ε′ (2t)2 modifications. By definition, ε < ε′ /4so ε(4t)2 < ε′ (2t)2 . The first case is therefore not possible.
Recall that |α1 | ≤ t. If |α1 | ≥ t/3, then by Condition 2 of Lemma 16 there exists
at least t2 /18 undirected edges between α1 and H ′ \α1 and between α2 and H\α2 .
All of these edges must be removed to satisfy P because each would connect avertex with a loop to a vertex without a loop. Therefore,dist(G′ , 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 ispossible to modify them instead of swapping them. This essentially results in thefirst case considered above. Condition 3 of Lemma 16 requires that each vertex
has relatively high degree. These edges can be either internal to α1 (resp. α2 ) or
connecting α1 (α2 ) with H ′ \α1 (H\α2 ). If α1 and α2 are relatively far apart, thenwe will see that this forces too many edges “outside” of α1 (resp. α2 ), resulting ina similar situation to the second case considered above.
We have assumed that dist(G′ , M ) < ε and that we can construct M from G′
by making less than ε(4t)2 modifications if we move α1 to H and α2 to H ′ . Thisentails the following modifications.

79CHAPTER 5. UNTESTABLE CLASSES
1. Removing all edges connecting α1 to H ′ \α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 ′ \α1 .
5. Changing α1 , α2 , H\α2 and H ′ \α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 +ε ≥ ε′ /4. If this does not hold, then we could
first modify α1 to make it identical to α2 and then make H ′ identical to M2 . Next,
M2 is identical to M1 , which we could make identical to H. This would requireless than ε′ (2t)2 modifications, which would violate Lemma 16. Therefore,dist(α1 , α2 ) ≥16(ε′ /4 − ε)t2.
|α1 |2(5.12)

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 ′ \α1 , where r is the number of edges internal to α1 thatmust be omitted to satisfy (5.12). 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 suﬃcient. Finally, combining this with
Inequality (5.12) yieldsr ≥ 8(ε′ /4 − ε)t2 .
80(5.13)

5.2. THE KAHR-MOORE-WANG CLASS WITH EQUALITY
The number of edges connecting α1 to H ′ \α1 is therefore, by (5.13), at least|α1 |(t/3 − |α1 | + 1) + 16(ε′ /4 − ε)t2 ≥ 16(ε′ /4 − ε)t2 .

All of these edges must be removed to move α1 (resp. α2 ), and soε′16(ε′ /4 − ε)t2
dist(G , M ) ≥
=
− ε.
(4t)2
4
′

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

5.2

Lemma 22

The Kahr-Moore-Wang Class with Equality

In Section 5.1, we saw an untestable first-order property that is an encoding ofgraph isomorphism similar to the untestable property of Alon et al. [3]. However,expressing graph isomorphism seems to require us to use four quantifiers, as we’dlike to say that some edge is present if some other (in general, disjoint) edge ispresent. In this section we prove the untestability of a prefix with length three,using a variant of graph isomorphism that is closely related to Boolean function
isomorphism.
The main result of this section is Theorem 9.
Theorem 9. The prefix class [∀∃∀, (0, 1)]= is not testable.

81

CHAPTER 5. UNTESTABLE CLASSES

5.2.1

From Four to Three Quantifiers

We begin by introducing the idea that allows us to remove one quantifier from theprefix while maintaining the hardness of our property for testing. Recall that graphisomorphism is generally hard for testing (see, e.g., Fischer and Matsliah [21]). In
fact, restricting the properties to checking an explicitly given isomorphism between
undirected, bipartite graphs (see Figure 5.1(a)) maintains hardness for testing.

(a) A graph with Pb(b) A graph with Pe(c) A graph with Pf

Figure 5.1. Properties Pb , Pe and Pf

Sharing one of the partitions (see Figure 5.1(b)) would seem to remove the needfor four quantifiers. The resulting property is perhaps closer to a variant of function
isomorphism, e.g., for functions f, g : [n] → {0, 1}n where bit i of f (j) is 1 if there
is an edge from j in the leftmost partition to i in the middle partition and likewisefor g(j) and the right partition. This property is not first-order expressible, butthere is a somewhat tedious first-order encoding that is similar (see Figure 5.1(c)and the formula in Subsection 5.2.2 below).
This connection with function isomorphism allows us to leverage recent workon the testability of (Boolean) function isomorphism and use recent ideas andtechniques from Alon and Blais [2] to prove Lemma 23.

82

5.2. THE KAHR-MOORE-WANG CLASS WITH EQUALITY

5.2.2

Proof of Theorem 9

We begin by outlining the proof. First, we define Pf , a property expressible
in the class [∀∃∀, (0, 1)]= which, as described above, is in some sense a somewhat
tedious but first-order expressible variant of checking (explicit) isomorphism of
undirected bipartite graphs in tripartite graphs. We then define a variant P2 , inwhich the isomorphism is not explicitly given and we must test whether there exists
some suitable isomorphism. Although this increases the complexity of deciding the
problem from checking an isomorphism to finding one, it does not change hardness
for testing. We will show that P2 and Pf are indistinguishable and so P2 is testable√iﬀ Pf is testable. Finally, we prove directly that P2 is untestable, even with o( n)queries, using an argument based on a recent proof by Alon and Blais [2].
Proof (Theorem 9). We begin by defining Pf . Formally, it is the set of graphs satisfying the following conjunction of four clauses (see Figure 5.1(c) for an example).

∀x∃y∀z : { ((¬E(x, x) ∧ ¬E(z, z) ∧ x ̸= z) → E(x, z))∧(E(x, x) → (E(x, y) ∧ ¬E(y, y) ∧ [(¬E(z, z) ∧ E(x, z)) → y = z]))∧(¬E(x, x) → (E(y, x) ∧ E(y, y) ∧ [(E(z, z) ∧ E(z, x)) → y = z]))∧((E(x, x) ∧ E(z, z)) → [¬E(y, y) ∧ E(x, y) ∧ (E(x, z) ↔ E(y, z))]) }A graph satisfies this formula if the following conditions are all satisfied.
1. The nodes without loops form a complete subgraph.
2. For every node x with a loop, there is exactly one y without a loop such that
there is an edge from x to y.
83CHAPTER 5. UNTESTABLE CLASSES
3. For every node y without a loop, there is exactly one x with a loop such that
there is an edge from x to y.
4. For all nodes x, z with loops, and y the unique node without a loop suchthat E(x, y), it holds that E(x, z) iﬀ E(y, z).
Property P2 below is similar to Pf , except that the isomorphism is not explicitly
given.
Definition 26. A graph G = (V, E) has P2 if it satisfies the following conditions.
1. There is a partition1 V1 , V2 ⊆ V such that |V1 | = |V2 |, there are loops(E(x, x)) on all x ∈ V1 and no loops (¬E(x, x)) for all x ∈ V2 .
2. The nodes without loops form a complete subgraph.
3. There are no edges from a node with a loop to a node without a loop.
4. There exists a bijection b : V1 → V2 such that if x, z have loops, then E(x, z)
iﬀ E(b(x), z).
It is not diﬃcult to show that properties Pf and P2 are indistinguishable.
Claim 3. Properties Pf and P2 are indistinguishable.
Proof (Claim 3). Let ε > 0 be arbitrary and let Nε = ε−1 . Assume that G has
property P2 and that #(G) > Nε . We will show that mrdist(G, Pf ) < ε.
Graph G has P2 and so there is a bijection satisfying Condition 4 of Definition 26.
We therefore add the edges E(i, b(i)) making the isomorphism (from V1 to V2 )explicit. The resulting graph Gf has Pf .
184

V1 , V2 partition V if V1 ∩ V2 = ∅ and V1 ∪ V2 = V .

5.2. THE KAHR-MOORE-WANG CLASS WITH EQUALITY
We have made exactly n/2 modifications, all to non-loops, and n − 1 ≥ Nε , so
mrdist(G, Pf ) ≤ mrdist(G, Gf ) = 1/2(n − 1) < ε.
The converse is analogous; given a G that has Pf , simply remove the n/2 edges
from loops to non-loops after using them to construct a suitable bijection b.
Claim 3
Properties Pf and P2 are indistinguishable and so (by Lemma 7), it suﬃces toshow that P2 is is untestable. Lemma 23 below is stronger than necessary, and√actually implies a Ω( n) lower bound for testing Pf per the discussion following
Lemma 7.

Theorem 9√
Lemma 23. Fix 0 < ε < 1/2. Any ε-tester for P2 must perform Ω( n) queries.
Proof (Lemma 23). The proof is via Yao’s Principle (cf. Principle 1), and so wedefine two distributions, Dno and Dyes and show that all deterministic testers havean error-rate greater than 1/3 for property P2 when the input is chosen randomly
from Dno with probability 1/2 and from Dyes with probability 1/2.
In the following, we consider a distribution over graphs of suﬃciently large
size 2n, and an arbitrary fixed partition of the vertices into V1 and V2 such that
|V1 | = |V2 | = n (for example, let the vertices be the integers V := [2n], V1 := [n]and V2 := V \V1 ).
We begin with Dno , defined as the following distribution.
1. Place a loop on each vertex in V1 and place no loops in V2 .
2. Place all edges (except loops) in V2 × V2 .

85

CHAPTER 5. UNTESTABLE CLASSES
3. Place each possible edge (except loops) in V1 × V1 and V2 × V1 uniformly andindependently with probability 1/2.
That is, Dno is the uniform distribution of graphs (with this particular partition)satisfying the first three conditions of P2 .
Next, we define Dyes as the following.
1. Choose uniformly a random bijection π : V1 → V2 .
2. Place a loop on each vertex in V1 and place no loops in V2 .
3. Place all edges (except loops) in V2 × V2 .
4. For each possible edge (i, j ̸= i) ∈ V1 × V1 , uniformly and independently
place both (i, j) and (π(i), j) with probability 1/2 (otherwise place neither ).
It is easy to see that Dyes generates only positive instances. Next, we show thatDno generates negative instances with high probability.
Lemma 24. Fix 0 < ε < 1/2 and let n be suﬃciently large. Then,

Pr

G∼Dno

[dist(G, P2 ) ≤ ε] = o(1) .

Proof (Lemma 24). Dno is the uniform distribution over graphs of size 2n with aparticular partition satisfying the first three conditions of P2 . Let Gε be the setof graphs G′ of size 2n satisfying these conditions and such that dist(G′ , P2 ) ≤ ε(regardless of partition).
Counting the number of such graphs shows
( )
)
( )
⌈ε2n2 ⌉ (2n n(n−1) ∑ 2n2
2n n(n−1) H(ϵ)2n2|Gε | ≤
2
n!
≤
2
n!2
,
n
i
n
i=0
86

5.2. THE KAHR-MOORE-WANG CLASS WITH EQUALITY
where H(ε) := −ε log ε − (1 − ε) log(1 − ε) is the binary entropy function (cf.
Lemma 16.19 in Flum and Grohe [23] for the bound on the summation).
2

Distribution Dno produces each of 2n(n−1) 2n graphs with equal probability, so

Pr

G∼Dno

[dist(G, P2 ) ≤ ε] ≤

( )
2n
2
2
≤
n!2H(ϵ)2n /2nn|Gε |2n(n−1)+n2

4n n!2H(ϵ)2n
√
≈
πn2n2

2

= o(1) .

The approximation is asymptotically tight, which suﬃces.

Lemma 24

We have shown that Dyes generates only positive instances and that (with highprobability) Dno generates instances that are ε-far from P2 . Next, we show that(again, with high probability) the two distributions look the same to testers making√
only o( n) queries.
The proof is similar to a proof by Alon and Blais [2]. We begin by defining two
random processes, Pno and Pyes , which answer queries from testers and generateinstances according to Dno and Dyes , respectively.
Process Pno is defined in the following way.
1. Choose uniformly a random bijection π : V1 → V2 .
2. Intercept all queries from the tester and respond as follows.
(a) To queries E(i, i) with i ∈ V1 : respond 1.
(b) To queries E(i, i) with i ∈ V2 : respond 0.
(c) To queries E(i, j) with i ∈ V1 and j ∈ V2 : respond 0.
(d) To queries E(i, j) with i ̸= j ∈ V2 : respond 1.

87

CHAPTER 5. UNTESTABLE CLASSES(e) To queries E(i, j) with i ̸= j ∈ V1 : quit if we have queried E(π(i), j),otherwise respond 1 or 0 randomly with probability 1/2 in each case.
(f) To queries E(i, j) with i ∈ V2 and j ∈ V1 : quit if we have queriedE(π −1 (i), j), otherwise respond 1 or 0 randomly with probability 1/2
in each case.
3. When the process has quit or the tester has finished its queries, complete
the generated instance in the following way. First, fix the edges that werequeried according to our answer. Next, place loops on each vertex in V1 , noloops in V2 , all non-loop edges in V2 and no edges from V1 to V2 . For eachremaining possible edge, place it (uniformly, independently) with probability
1/2, ignoring π.
We define Pyes in the same way, except for the final step. When Pyes quits or thetester finishes, it fixes the edges that were queried according to its answers, andalso fixes the corresponding edges (when relevant) according to π. More precisely,for each fixed E(i, j) with i ̸= j ∈ V1 , we also fix E(π(i), j) and for fixed E(i, j)with i ∈ V2 , j ∈ V1 , we also fix E(π −1 (i), j), in both cases the same as our responseto E(i, j) (not randomly). The remaining edges are placed as in Pno .
Note that Pno generates instances according to Dno and Pyes generates instances according to Dyes . In addition, Pyes and Pno behave identically until
they quit or answer all queries. In particular, if a tester does not cause the process
to quit, the distribution of responses of its queries is identical for the two processes.
√
We show that, with high probability, a tester that makes o( n) queries does notcause either process to quit.
88

5.3. UNTESTABLE CLASSES WITHOUT EQUALITY√
Lemma 25. Let T be a deterministic tester which makes o( n) queries, and let
T interact with Pyes or Pno . In both cases,

Pr [T causes the process to quit] = o(1) .

Proof (Lemma 25). The condition causing the process to quit is identical in Pyes
and Pno . The probability that any pair of queries E(i, j) and E(i′ , j ′ ) cause theprocess to quit is at mostPr [i′ = π(i) or i = π(i′ )] ≤(n − 1)!
= 1/n .
n!

√
The tester makes at most o( n) queries and so√
Pr [T causes the process to quit] ≤ o( n)2 O(1/n) = o(1) .

Lemma 25√
Any deterministic tester T which makes o( n) queries can only distinguishbetween Dyes and Dno with probability o(1), but it must accept Dyes with probability 2/3, and reject Dno with probability 2/3 − o(1). It is impossible for T tosatisfy both conditions, and the lemma follows from Principle 1.

5.3

Lemma 23

Untestable Classes without Equality

We now consider classes without equality. Of course, any prefix class that is
testable with equality remains testable without equality (because we are not forced

89

CHAPTER 5. UNTESTABLE CLASSES
to use equality). However, we now show that there are some untestable properties
that are expressible in first-order logic even without equality.
Theorem 10. There are properties in [∀∃∀, (0, 1)] that are not Tmr -testable, even√given o( n) queries.
Note that Theorem 10 is restricted to Tmr -testability. It is trivial to modify
the proof for Tr -testability of [∀∃∀, (1, 1)]. It remains open whether this class is
T -testable, however we suspect that [∀∃∀, (0, 1)] is not T -testable.
Proof (Theorem 10). The proof is similar to the proof of Theorem 9. We will begin
by defining a property Pf that is expressible in our class. We will then define aproperty P which is indistinguishable from Pf , and use Yao’s Principle to showthat P is not Tmr -testable.
A graph has property Pf if it satisfies the following conditions.
1. For every x with a loop, there is an outgoing edge to at least one y withouta loop.
2. For every x without a loop, there is an incoming edge from at least one y
without a loop.
3. There are no edges between vertices without loops.
4. For every x with a loop, there is an edge to at least one y without a loop
such that for all z with loops, the following holds. There is a directed edge
from y to z iﬀ there are an odd number2 of directed edges between x and z.
2

There is an odd number of edges between x and z if there is a directed edge from x to z orfrom z to x, but not both. Note that a loop is counted as an even number of edges.

905.3. UNTESTABLE CLASSES WITHOUT EQUALITY
5. For every x without a loop, there is an incoming edge from at least one ywith a loop such that for all z with loops, the following holds. There isa directed edge from x to z iﬀ there are an odd number of directed edges
between y and z.
More formally, Pf is the set of graphs that satisfy the following formula.

∀x∃y∀z :{ (E(x, x) → (¬E(y, y) ∧ E(x, y)))∧(¬E(x, x) → (E(y, y) ∧ E(y, x)))∧((¬E(x, x) ∧ ¬E(z, z)) → ¬E(x, z))∧((E(x, x) ∧ E(z, z)) → ((E(x, z) ⊕ E(z, x)) ↔ E(y, z)))∧((¬E(x, x) ∧ E(z, z)) → ((E(y, z) ⊕ E(z, y)) ↔ E(x, z))) }Next, we define a property P that we will show to be indistinguishable from Pf .
A graph has property P if it satisfies the following conditions.
1. There is a partition of the vertices into (non-empty) V1 , V2 .
2. All vertices in V1 have loops and no vertices in V2 have loops.
3. There are no edges in V2 × V2 .
4. There exist functions f : V1 → V2 and g : V2 → V1 satisfying the following.
For all x, z ∈ V1 , there is an edge from f (x) to z iﬀ there are an odd numberof directed edges between x and z. For all x ∈ V2 and z ∈ V1 , there is anedge from x to z iﬀ there are an odd number of directed edges between g(x)and z.

91

CHAPTER 5. UNTESTABLE CLASSES
It is not diﬃcult to show that P and Pf are indistinguishable.
Lemma 26. Properties P and Pf are indistinguishable.
Proof (Lemma 26). Let G be graph with property Pf and let ε > 0 be arbitrary.
Then, G also has property P , that is mrdist(G, P ) = 0. In the other direction, if
G has property P , then we can satisfy property Pf by adding at most O(n) (nonloop) edges from x to f (x) and g −1 (y) to y. Thus, mrdist(G, Pf ) ≤ O(n)/Θ(n2 ) =o(1) < ε for suﬃciently large graphs.

Lemma 26

Indistinguishability preserves testability (cf. Lemma 7) and so it suﬃces to showthat P is untestable. Lemma 27 below is stronger than necessary and actually√
implies a Ω( n) lower bound for testing Pf per the discussion following Lemma 7
in Section 3.3.

Theorem 10

Lemma 27. There is an 0 < ε < 1/2 such that any Tmr -style ε-tester for P must√
perform Ω( n) queries.
Proof (Lemma 27). The proof is via Yao’s Principle (cf. Principle 1) and so wemust define a distribution of inputs and show that all deterministic ε-testers havean error rate greater than 1/3 for P on inputs from the distribution. For our
distribution, we will draw from a distribution Dno with probability 1/2 and froma distribution Dyes with probability 1/2.
In the following, we consider distributions over graphs with suﬃciently large
vertex set [2n] and an arbitrary fixed partition of the vertices into V1 and V2 suchthat |V1 | = |V2 | = n.
We begin with Dno , defined as the following distribution.

925.3. UNTESTABLE CLASSES WITHOUT EQUALITY
1. Place loops on all vertices in V1 and no loops in V2 .
2. For each ordered pair in V1 × V2 , place a directed edge with probability 1/2.
3. For each unordered pair (i, j ̸= i) ∈ V1 × V1 , with probability 1/2 place noedge, and with probability 1/2 place a single directed edge, from i to j if
i ≤ j and from j to i if j ≤ i.
4. For each ordered pair in V2 × V1 , with probability 1/2 place the directed edge
and with probability 1/2 do not.
Note that Dno is the uniform distribution of graphs that satisfy the following
conditions.
1. The vertex set is [2n] and the vertices with loops follow the given partition.
2. There are no undirected edges between vertices with loops (when a loop is
not considered an undirected edge).
3. There are no edges between vertices without loops.
4. All directed edges (i, j) between vertices with loops satisfy i ≤ j.
Next, we define Dyes .
1. Place loops on all vertices in V1 and no loops in V2 .
2. For each ordered pair in V1 × V2 , place a directed edge with probability 1/2.
3. Choose uniformly a random bijection π : V1 → V2 .

93

CHAPTER 5. UNTESTABLE CLASSES
4. For each unordered pair in (i, j ̸= i) ∈ V1 × V1 , with probability 1/2 do thefollowing. Place directed edges (π(i), j) and (π(j), i), and then place either(i, j) (if i ≤ j) or (j, i) (if j ≤ i). Otherwise, do not place any edges rightnow.
Distribution Dyes generates only positive instances for P . Now, we show thatwith high probability, Dno generates instances that are ε-far.
Lemma 28. Let ε > 0 be suﬃciently small and n be suﬃciently large. Then,

Pr

G∼Dno

[mrdist(G, P ) ≤ ε] = o(1) .

Proof (Lemma 28). Distribution Dno is the uniform distribution over graphs ofsize 2n with a fixed partition V1 , V2 satisfying the following.
1. All vertices in V1 have loops and no vertices in V2 have loops.
2. There are no undirected edges between vertices with loops.
3. There are no edges between vertices without loops.
4. All directed edges (x, y) between vertices with loops satisfy x ≤ y.
We want a small upper-bound on the probability of a graph being drawn from
Dno that is not ε-far from P . Dno is the uniform distribution over a certain classof graphs, and so this probability is|{G | G ∼ Dno , mrdist(G, P ) ≤ ε}|.
|{G | G ∼ Dno }|n
2
2
The number of distinct graphs produced by Dno is 2( 2 ) 22n = 22.5n −n/2 .

94

5.3. UNTESTABLE CLASSES WITHOUT EQUALITYLet G2n be the set of graphs with vertices [2n] that have property P and are
not ε-far from all graphs in Dno . Then,∑ 2 ⌋ (4n2 )|G2n | ⌊4εni=0i.
Pr [mrdist(G, P ) ≤ ε] ≤
2.5n
G∼Dno
2 2 −n/2(5.14)

Any graph G that is not ε-far from all graphs in Dno must have loops onn − εn ≤ j ≤ n + εn vertices. Therefore, |G2n | ≤( )( )2n (2j ) j(2n−j) 2n−j
2n 2(n+εn2
4 2j≤ (2εn + 1)
2 2 )+(n+εn) +(n+εn) log (n+εn) .
jnj=n−εnn+εn∑(5.15)
Using the (asymptotically tight)

(2n)
n

√
≈ 4n / πn, we see that (5.15) is approxi-

mately(2εn + 1) 2n+(n+εn)2 +(n+εn)(n+εn−1)+(n+εn) log(n+εn)√2.
πnCombining this with (5.14) and using∑⌊ε4n2 ⌋ (4n2 )i=0i≤ 2H(ε)4n , where H(ε) =2−ε log ε − (1 − ε) log(1 − ε) is the binary entropy function (cf. Lemma 16.19 inFlum and Grohe [23]), we get PrG∼Dno [mrdist(G, P ) ≤ ε] ≤2εn + 1 −n2 /2+4H(ε)n2 +3/2n+2(ε2 +ε)n2 +εn+(n+εn) log (n+εn)√2= o(1) ,πnbecause the −n2 /2 in the exponent dominates when ε is suﬃciently small.
Lemma 28
We have shown that Dyes generates only positive instances and, with high probability, Dno generates ε-far instances. Next, we show that, with high probability,√
the two distributions look identical to testers making only o( n) queries. The

95

CHAPTER 5. UNTESTABLE CLASSES
proof is similar to a proof by Alon and Blais [2].
We begin by defining two random processes, Pno and Pyes , which answer queries
from testers and generate instances according to Dno and Dyes , respectively.
Process Pno is defined in the following way.
1. Choose uniformly a random bijection π : V1 → V2 .
2. Intercept all queries from the tester and respond as follows.
(a) To queries E(i, i) with i ∈ V1 , respond 1.
(b) To queries E(i, i) with i ∈ V2 , respond 0.
(c) To queries E(i, j) with i ∈ V2 , j ∈ V2 , respond 0.
(d) To queries E(i, j) with i ∈ V1 , j ∈ V2 , randomly respond 1 or 0 withprobability 1/2 in each case.
(e) To queries E(i, j) with i > j ∈ V1 , respond 0.
(f) To queries E(i, j) with i < j ∈ V1 , quit if we have queried E(π(i), j) orE(π(j), i). Otherwise randomly respond 1 or 0 with probability 1/2 ineach case.
(g) To queries E(i, j) with i ∈ V2 , j ∈ V1 , quit if we have queried E(π −1 (i), j)or E(j, π −1 (i)). Otherwise randomly respond 1 or 0 with probability
1/2 in each case.
3. When the process has quit, or the tester has finished its queries, complete
the generated instance in the following way. First, fix the edges that werequeried according to our answers. Next, place loops on all vertices in V1 , noloops in V2 and no edges internal to V2 . Place each edge in V1 × V2 uniformly
965.3. UNTESTABLE CLASSES WITHOUT EQUALITY
and independently with probability 1/2. For each remaining possible edge(i, j) ∈ V1 × V1 , place the edge uniformly and independently with probability
1/2 if i < j and do not place the edge if i > j. For each remaining possibleedge in V2 × V1 , place the edge uniformly and independently with probability
1/2 (ignoring π).
We define Pyes in the same way, except for the final step. When Pyes quits or
the tester finishes, it fixes the edges that were queried according to its answers, andalso fixes the corresponding edges (when relevant) according to π. More precisely,for each fixed E(i, j) with i ̸= j ∈ V1 , we also fix E(π(i), j) and E(j, π(i)), and for
fixed E(i, j) with i ∈ V2 , j ̸= π −1 (i) ∈ V1 , we also fix E(π −1 (i), j) and E(j, π −1 (i)),
in both cases according to our previous decision. The remaining edges are placed
as in Pno .
Note that Pno generates instances according to Dno and Pyes generates instances according to Dno . In addition, Pyes and Pno behave identically until they
quit or answer all queries. In particular, if a tester does not cause the process toquit, the distribution of responses to queries is identical for the two processes. We√
show that, with high probability, a tester that makes o( n) queries does not cause
either process to quit.
√
Lemma 29. Let T be a deterministic tester which makes o( n) queries, and let
T interact with Pyes or Pno . In both cases,

Pr[T causes the process to quit] = o(1) .

Proof (Lemma 29). The condition causing the process to quit is identical in Pyes
97

CHAPTER 5. UNTESTABLE CLASSES
and Pno . The probability that any fixed pair of queries E(i, j) and E(i′ , j ′ ) cause
the process to quit is at mostPr[i′ = π(i) or i′ = π(j)] ≤2(n − 1)!
= 2/n .
n!

√
The tester makes at most o( n) queries and so√
Pr[T causes the process to quit] ≤ o( n)2 O(1/n) = o(1) .

Lemma 28√
Any deterministic tester T which makes o( n) queries can only distinguishbetween Dyes and Dno with probability o(1), but it must accept Dyes with probability at least 2/3 and reject Dno with probability at least 2/3 − o(1). It is
impossible for T to satisfy both conditions, so the lemma follows from Principle 1.
Lemma 27

5.4

Summary

In this chapter, we proved that several classes of first-order properties of directed
graphs are not testable. We used a diﬀerent variant of graph isomorphism in eachcase. We began with the prefix ∀3 ∃ in Section 5.1. This result first appeared in [40],and we thank an anonymous referee from LATA for improving it significantly. This
result will also appear in [42].
In Section 5.2, we proved the untestability of ∀∃∀ by using a variant of graph isomorphism related to Boolean function isomorphism. The connection with Boolean
985.4. SUMMARY
function isomorphism allows us to leverage recent ideas from Alon and Blais [2].
This result first appeared in [41].
Finally, we considered classes without equality in Section 5.3. There, we showed
that, even without equality, ∀∃∀ can express untestable properties of directed
graphs. However, this proof is currently limited to Tmr -style testing and it remains
open whether this class is Tr -testable. Our suspicion is that it is untestable in allof our models. This result appears here for the first time.
We’re grateful to Neil Immerman for pointing out that removing equality in our
untestable properties does not really change the “spirit” of why they’re untestable.
Section 5.3 formalizes this for one of our classes; we suspect that similar arguments
will also allow us to remove equality from the classes in Section 5.1. We’re also
grateful to Hiro Ito for pointing out an omission in a previous version of the proof
of Lemma 23.

99

Chapter 6
Conclusions
In this thesis, we focused on the testability of prefix-vocabulary classes of first-orderlogic, extending work that was initiated by Alon et al. [3]. They first considered
the idea of testing syntactic subclasses of first-order logic, and showed that all
properties of undirected, loop-free graphs expressible in first-order sentences withquantifier pattern ∃∗ ∀∗ are testable, while there exists an untestable property
expressible with quantifier pattern ∀∗ ∃∗ .
Their proof of the latter result implies upper bounds of twelve, five and seventeen
for the minimum number of universal, existential and total quantifiers, respectively,
suﬃcient to express an untestable property. One of our goals was to optimize thesebounds and find the minimum number of universal and existential quantifiers,
as well as quantifiers in total, suﬃcient to express an untestable property. Our
results imply that these minima are two universal, one existential and three total
quantifiers, respectively. In addition, we remove the restriction to undirected,
loop-free graphs and focus on relational structures.
Our main results are as follows. First, we proved that all properties express100

Conclusions
ible in Ackermann’s class with equality ([∃∗ ∀∃∗ , all ]= ) are testable. Then, we
extended the positive result of Alon et al. [3] from undirected, loop-free graphs
to relational structures by using a result from Austin and Tao [11]. This answers
a question of Fischer [20] on the testability of hypergraph properties expressible
with quantifier pattern ∃∗ ∀∗ , although much of the work for this case is by Austin
and Tao [11]. Next, we simplified the untestable property of Alon et al. [3] andshowed that there are untestable properties of directed graphs expressible withquantifier prefixes ∀3 ∃. Finally, we used a variant of graph isomorphism related
to Boolean function isomorphism to prove that there are untestable properties of
directed graphs expressible with prefix ∀∃∀ (for Tmr testability, this remains true
without equality).
The current classification of prefix-vocabulary classes for testability is the following.
• Testable classes
1. Monadic first-order logic: [all , (ω)]= .
2. Ackermann’s class with equality: [∃∗ ∀∃∗ , all ]= .
3. Ramsey’s class: [∃∗ ∀∗ , all ]= .
• Untestable classes
1. [∀3 ∃, (0, 1)]= .
2. [∀∃∀, (0, 1)]= .
3. [∀∃∀, (0, 1)]1 .
We only prove this for Tmr testability, although we suspect that it also holds for our othermodels.
1

101

Conclusions
It is interesting to compare this classification for testability with known (complete) classifications for other properties. For example, the current classification
for testability is consistent with the classifications for the finite model property(see, e.g., Chapter 6 of Börger et al. [15]), for docility2 (see Kolaitis and Vardi [46])and for 0-1 laws for fragments of existential second-order logic (see Kolaitis andVardi [46]). These classifications may be helpful in providing guidance in theclassification for testability.
This similarity between classifications may indicate a deeper connection between
these seemingly distinct properties. We would like to know which (if any) of the
traditional classifications coincides with the classification for testability, and hopeto understand the connections between testability and other properties of prefixvocabulary classes.
As concrete open problems, we are especially interested in the testability of[∀3 ∃, (0, 1)] (without equality) and variants of the Gödel class (i.e., classes whose
prefix contain at least ∀2 ∃). Determining the testability of these classes may suﬃce
to complete the classification. We are also interested in the special case of predicate
logic with equality.
There are many possible variations of the classification for testability. For example, one could be more interested in classes which are constructively testable,i.e., where it is possible to compute an ε-tester given ε and a formula from theclass. However, in the present paper we are fortunate that many of the possible classifications coincide. Namely, all of our positive results are for constructive(and therefore uniform) testability in the most-restricted model (Tmr ) that we con2

A class is said to be docile (or decidable for finite satisfiability) if given an arbitrary formulafrom the class, one can decide if there exists a finite model of the property.

102

Conclusions
sider, while all of the negative results hold even for non-uniform testability in theleast-restricted model (T ).
As is common in the literature, we have focused on testable properties, i.e., thosewhich can be approximated with a number of queries (or time) depending on ε but
not on n. Given the deep connection between dense graph property testing and applications of strong versions of Szemerédi’s regularity lemma (see Alon et al. [4]), it
is not surprising that there are testable properties with enormous query complexity(e.g., towers of 1/ε with height growing in 1/ε). Even relatively simple properties
such as triangle-freeness3 are testable, but not with query complexity polynomial
in 1/ε4 . However, in practice we are perhaps more interested in properties thatcan be tested with a number of queries polynomial in 1/ε.
Our construction for Ramsey’s class (cf. Section 4.2) results in a rather large
query complexity. However, this class contains the problems of triangle-freenessand R-freeness (for finite sets R of finite structures). Significantly improving thequery complexity of these problems is considered to be a diﬃcult open problem,and so significantly improving the query complexity for Ramsey’s class (in general)is likely to be challenging.

3

A graph is triangle-free if it contains no 3-cliques.
See Alon and Shapira [6] for the lower-bound. The best known upper-bound, a tower of 1/εof height logarithmic in 1/ε is due to Fox [24].
4103Bibliography[1] Wilhelm Ackermann. Über die Erfüllbarkeit gewisser Zählausdrücke. Mathematische Annalen, 100:638–649, 1928.
[2] Noga Alon and Eric Blais. Testing Boolean function isomorphism. In Approximation, Randomization, and Combinatorial Optimization, Algorithms andTechniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 2010, Proceedings, volume 6302 of Lecture Notes in Computer Science, pages 394–405.
Springer, 2010.
[3] Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Eﬃcienttesting of large graphs. Combinatorica, 20(4):451–476, 2000.
[4] Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial
characterization of the testable graph properties: It’s all about regularity. In
STOC ’06: Proceedings of the 38th Annual ACM Symposium on Theory ofComputing, pages 251–260, New York, NY, USA, 2006. ACM.
[5] Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy. Regular
languages are testable with a constant number of queries. SIAM Journal on104Bibliography
Computing, 30(6):1842–1862, 2001.
[6] Noga Alon and Asaf Shapira. A characterization of easily testable induced
subgraphs. Combinatorics, Probability and Computing, 15(6):791–805, 2006.
[7] Noga Alon and Asaf Shapira. Homomorphisms in graph property testing. In
M. Klazar, J. Kratochvíl, M. Loebl, J. Matoušek, R. Thomas, and P. Valtr,
editors, Topics in Discrete Mathematics, volume 26 of Algorithms and Combinatorics, pages 281–313. Springer, 2006.
[8] Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties testable with one-sided error. SIAM Journal on Computing, 37(6):1703–
1727, 2008.
[9] Noga Alon and Asaf Shapira. A separation theorem in property testing.
Combinatorica, 28(3):261–281, 2008.
[10] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley, third
edition, 2008.
[11] Tim Austin and Terence Tao. On the testability and repair of hereditary hypergraph properties. Random Structures & Algorithms, 36(4):373–463, 2010.
[12] Paul Bernays and Moses Schönfinkel. Zum Entscheidungsproblem der mathematischen Logik. Mathematische Annalen, 99(1):342–372, 1928.
[13] Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds
via communication complexity. In Proceedings, 26th Annual IEEE Confer-105

Bibliography
ence on Computational Complexity, CCC 2011, 8–10 June 2011, San Jose,
California, pages 210–220. IEEE Computer Society, 2011.
[14] Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correctingwith applications to numerical problems. Journal of Computer and System
Sciences, 47(3):549–595, 1993.
[15] Egon Börger, Erich Grädel, and Yuri Gurevich. The Classical Decision Problem. Springer-Verlag, 1997.
[16] J. Richard Büchi.

Weak second-order arithmetic and finite-automata.

Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 6:66–
92, 1960.
[17] Hana Chockler and Orna Kupferman. ω-regular languages are testable witha constant number of queries. Theoretical Computer Science, 329(1-3):71–92,
2004.
[18] Christian Fermüller and Gernot Salzer. Ordered paramodulation and resolution as decision procedure. In Logic Programming and Automated Reasoning,
4th International Conference, LPAR’93, St. Petersburg, Russia, July 13-20,
1993, Proceedings, volume 698 of Lecture Notes in Computer Science, pages
122–133. Springer, 1993.
[19] Eldar Fischer. The art of uninformed decisions. Bulletin of the European Association for Theoretical Computer Science, 75:97–126, October 2001. Columns:
Computational Complexity.

106Bibliography[20] Eldar Fischer. Testing graphs for colorability properties. Random Structures& Algorithms, 26(3):289–309, 2005.
[21] Eldar Fischer and Arie Matsliah. Testing graph isomorphism. SIAM Journal
on Computing, 38(1):207–225, 2008.
[22] Eldar Fischer, Arie Matsliah, and Asaf Shapira. Approximate hypergraphpartitioning and applications. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007, pages 579–589,
2007.
[23] Jörg Flum and Martin Grohe. Parametrized Complexity Theory. Springer,
2006.
[24] Jacob Fox. A new proof of the graph removal lemma. Annals of Mathematics,
174(1):561–579, 2011.
[25] Rūsiņš Freivalds. Fast probabilistic algorithms. In Mathematical Foundationsof Computer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3-7, 1979, volume 74 of Lecture Notes in Computer Science,
pages 57–69. Springer-Verlag, 1979.
[26] John Gill. Computational complexity of probabilistic Turing machines. SIAM
Journal on Computing, 6(4):675–695, 1977.
[27] O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, 32:302–343, 2002.

107

Bibliography[28] Oded Goldreich. Introduction to testing graph properties. Technical Report
TR10-082, Electronic Colloquium on Computational Complexity (ECCC),
May 2010.
[29] Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its
connection to learning and approximation. Journal of the ACM, 45(4):653–
750, 1998.
[30] W. T. Gowers. Hypergraph regularity and the multidimensional Szemerédi
theorem. Annals of Mathematics, 166(3):897–946, 2007.
[31] Erich Grädel. Satisfiability of formulae with one ∀ is decidable in exponential
time. Archive for Mathematical Logic, 29:256–276, 1990.
[32] Yuri Gurevich. The decision problem for the logic of predicates and operations. Algebra i Logika, 8:284–308, 1969. In Russian.
[33] Yuri Gurevich. The decision problem for the logic of predicates and operations. Algebra and Logic, 8:160–174, 1969.
[34] Yuri Gurevich. On the classical decision problem. Bulletin of the European
Association for Theoretical Computer Science, pages 140–150, October 1990.
[35] Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis,
Moshe Y. Vardi, and Victor Vianu. On the unusual eﬀectiveness of logic incomputer science. The Bulletin of Symbolic Logic, 7(2):213–236, 2001.

108

Bibliography[36] John E. Hopcroft and Jeﬀerey D. Ullman. Introduction to Automata Theory,
Languages, and Computation. Adison-Wesley Publishing Company, Reading,
Massachusets, USA, 1979.
[37] Yoshiyasu Ishigami. Removal lemma for infinitely-many forbidden hypergraphs and property testing. arXiv:math/0612669v2, 2008.
[38] Charles Jordan and Thomas Zeugmann. Relational properties expressible
with one universal quantifier are testable. In Osamu Watanabe and Thomas
Zeugmann, editors, Stochastic Algorithms: Foundations and Applications, 5thInternational Symposium, SAGA 2009, Sapporo, Japan, October 2009, Proceedings, volume 5792 of Lecture Notes in Computer Science, pages 141–155.
Springer, 2009.
[39] Charles Jordan and Thomas Zeugmann. A note on the testability of Ramsey’sclass. In Jan Kratochvíl, Angsheng Li, Jiří Fiala, and Petr Kolman, editors,
Theory and Applications of Models of Computation, 7th International Conference, TAMC 2010, Prague, Czech Republic, June 2010, Proceedings, volume6108 of Lecture Notes in Computer Science, pages 296–307. Springer, 2010.
[40] Charles Jordan and Thomas Zeugmann. Untestable properties expressible
with four first-order quantifiers. In Adrian-Horia Dediu, Henning Fernau,
and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, 4th International Conference, LATA 2010, Trier, Germany, May
2010, Proceedings, volume 6031 of Lecture Notes in Computer Science, pages
333–343. Springer, 2010.

109

Bibliography[41] Charles Jordan and Thomas Zeugmann. Untestable properties in the KahrMoore-Wang class. In Lev D. Beklemishev and Ruy de Queiroz, editors,
Logic, Language, Information and Computation, 18th International Workshop, WoLLIC 2011, Philadelphia, PA, USA, May 18-21, 2011, Proceedings, volume 6642 of Lecture Notes in Artificial Intelligence, pages 176–186.
Springer, 2011.
[42] Charles Jordan and Thomas Zeugmann. Testable and untestable classes offirst-order formulae. Journal of Computer and System Sciences, to appear,2012.
[43] Skip Jordan and Thomas Zeugmann. Indistinguishability and first-order logic.
In Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li, editors,
Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi’an, China, April 2008, Proceedings, volume 4978 of
Lecture Notes in Computer Science, pages 94–104. Springer, 2008.
[44] P. Kolaitis and M. Vardi. The decision problem for the probabilities of higherorder properties. In STOC ’87: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 425–435, New York, NY, USA, 1987.
ACM.
[45] Phokion G. Kolaitis and Moshe Y. Vardi. 0-1 laws and decision problems forfragments of second-order logic. Information and Computation, 87(1-2):302–
338, 1990.

110

Bibliography[46] Phokion G. Kolaitis and Moshe Y. Vardi. 0-1 laws for fragments of existential
second-order logic: A survey. In Mogens Nielsen and Branislav Rovan, editors, Mathematical Foundations of Computer Science 2000, 25th International
Symposium, MFCS 2000, Bratislava, Slovakia, August/September 2000, Proceedings, volume 1893 of Lecture Notes in Computer Science, pages 84–98.
Springer, 2000.
[47] K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro. Computability by
probabilistic machines. In C.E. Shannon and J. McCarthy, editors, Automata
Studies, pages 183–212. Princeton University Press, Princeton, NJ, 1956.
[48] Harry R. Lewis. Complexity results for classes of quantificational formulas.
Journal of Computer and System Sciences, 21(3):317–353, 1980.
[49] Leonid Libkin. Expressive power of SQL. Theoretical Computer Science,
296:379–404, 2003.
[50] László Lovász. Some mathematics behind graph property testing. In Yoav
Freund, László Györfi, György Turán, and Thomas Zeugmann, editors, Algorithmic Learning Theory, 19th International Conference, ALT 2008, Budapest, Hungary, October 2008, Proceedings, volume 5254 of Lecture Notes in
Computer Science, page 3. Springer, 2008.
[51] Leopold Löwenheim. Über Möglichkeiten im Relativkalkül. Mathematische
Annalen, 76:447–470, 1915.
[52] Robert McNaughton and Seymour Papert. Counter-Free Automata. M.I.T.
Press, 1971.
111

Bibliography[53] J. v. Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen,
100(1):295–320, 1928.
[54] Eugenio Omodeo and Alberto Policriti. The Bernays-Schönfinkel-Ramsey
class for set theory: Semidecidability. Journal of Symbolic Logic, 75(2):459–
480, June 2010.
[55] Michal Parnas and Dana Ron. Testing the diameter of graphs. Random
Structures & Algorithms, 20(2):165–183, 2002.
[56] F. P. Ramsey. On a problem of formal logic. Proceedings of the London
Mathematical Society, series 2, 30:264–286, 1930.
[57] Vojtěch Rödl and Mathias Schacht. Generalizations of the removal lemma.
Combinatorica, 29(4):467–501, 2009.
[58] Vojtěch Rödl and Mathias Schacht. Regular partitions of hypergraphs: Regularity lemmas. Combinatorics, Probability and Computing, 16(6):833–885,
2007.
[59] Vojtěch Rödl and Mathias Schacht. Regularity lemmas for graphs. In Gyula
O. H. Katona, Alexander Schrijver, Tamás Szőnyi, and Gábor Sági, editors,
Fete of Combinatorics and Computer Science, volume 20 of Bolyai Society
Mathematical Studies, pages 287–325, 2010.
[60] Dana Ron. Property testing. In Sanguthevar Rajasekaran, Panos M. Pardalos,
John H. Reif, and José Rolim, editors, Handbook of Randomized Computing,volume II, chapter 15, pages 597–649. Kluwer Academic Publishers, 2001.

112

Bibliography[61] Dana Ron. Property testing: A learning theory perspective. Foundations andTrends in Machine Learning, 1(3):307–402, 2008.
[62] Dana Ron. Algorithmic and analysis techniques in property testing. Foundations and Trends in Theoretical Computer Science, 5(2):73–205, 2009.
[63] Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing,25(2):252–271, 1996.
[64] Saharon Shelah. Decidability of a portion of the predicate calculus. Israel
Journal of Mathematics, 28(1-2):32–44, 1977.
[65] Stephen Simons. Minimax theorems and their proofs. In Ding-Zhu Du andPanos M. Pardalos, editors, Minimax and Applications, pages 1–23. Kluwer
Academic Publishers, 1995.
[66] Th. Skolem.

Untersuchungen über die Axiome des Klassenkalküls undüber Produktations und Summationsprobleme, welche gewisse Klassen
von Aussagen betreﬀen.

Videnskapsselskapets skrifter, I. Matematisk-

naturvidenskabelig klasse, (3):37–71, 1919.
[67] Th. Skolem. Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit
und Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte
Mengen.

Videnskapsselskapets skrifter, I. Matematisk-naturvidenskabelig

klasse, (4):1–36, 1920.
[68] Terence Tao. A variant of the hypergraph removal lemma. Journal of Combinatorial Theory, Series A, 113(7):1257–1280, 2006.
113

Bibliography[69] Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer
Science, pages 222–227. IEEE Computer Society, 1977.

114