ABSTRACT Title of Dissertation: Applications of Graph Theory and Logic in Computer Science Shaopeng Zhu Doctor of Philosophy, 2023 Dissertation Directed by: Professor William I. Gasarch Department of Computer Science and Professor Michael C. Laskowski Department of Mathematics In Chapter 2 we study the CSP of unary expansions of directed graphs. When we expand the simple structure (Z,succ) with one unary predicate U , its CSP (Constraint Satisfaction Problem) may vary in complexity. We find some sufficient conditions for its tractability, prove bounds on its complexity, and then generalize our results to more com- plicated structures. We also give a Karp-equivalent characterization of CSP(Z, succ, U)s. Next, fixing α ∈ (0, 1], we generalized the axiomatizations in [1] to the class of hereditarily linearly sparse Kn-free graphs in Chapter 3, and made efforts towards con- necting this with almost sure theories of Shelah-Spencer graphs, a type of random graphs, which may be of interest in theory of computer science. In Chapter 4 we study the constraint satisfaction problems of selected infinite rela- tional structures. For α ∈ (0, 5 6 ], Kα := the class of hereditarily α-sparse graphs, Mα := the generic structure ofKα;Kα,Kn−free,Mα,Kn−free := theKn-free subclass and its generic structure respectively, we prove multiple structural properties of graphs presenting the Hrushovski-Fraı̈ssé class Kα,TF, strongly indicating that this class should have a finite homomorphic presentation when α is close to 5 6 from below, which would imply NP- completeness. More general results are explored along. We also study the complexity- theoretic implications of our findings on a relevant decision problem, namely the con- straint satisfaction problem of the corresponding generic structure. APPLICATIONS OF GRAPH THEORY AND LOGIC IN COMPUTER SCIENCE by Shaopeng Zhu Dissertation submitted to the Faculty of the Graduate School of the University of Maryland, College Park in partial fulfillment of the requirements for the degree of Doctor of Philosophy 2023 Advisory Committee: Professor William Gasarch, Chair/Advisor Professor Michael Laskowski, Co-Chair/Co-Advisor Professor Michael Cummings, Dean’s Representative Professor Lawrence Washington Associate Professor Robert Patro © Copyright by Shaopeng Zhu 2023 Acknowledgments First and foremost, the author is deeply thankful to his PhD Dissertation advisors: Dr. Michael Laskowski and Dr. William Gasarch, for their valuable advice. It was great to study graph theory, model theory, and complexity theory under their guidance. The author thanks Dr. David Doty and Dr. Xiaodi Wu, for patiently leading him through different stages of his career across seemingly disjoint subfields. The author thanks all members of his advisory committee: Professor William Gasarch, Professor Michael Laskowski, Professor Lawrence Washington, Professor Robert Patro, and Professor Michael Cummings, for kindly evaluating his dissertation and helping with the improvement of the presentation. The author thanks Dr. Ilchul Yoon and Mr. Jason Filippou for allowing him to serve as teaching assistants in multiple offerings of their Introduction to Computer Systems, Introduction to Computer Architecture (Dr. Yoon) and Discrete Structures (Mr. Filippou) courses. Without the TA salary, this dissertation would never ever have existed. Likewise, The author thanks Dr. Jeffrey Adams, Dr. Lawrence Washington, Dr. Alejandro Flores Velazco, Dr. David Doty, Dr. Robert Gysel, and Dr. Matthew Franklin for the teaching assistance opportunities in College Park, MD or Davis, CA since Fall ii 2015. Corollary to that, the author thanks all his co-TAs, graduate and undergraduate, for smooth collaboration, which helped maintain the author’s source of living. The author also thanks Dr. Xiaodi Wu and Dr. David Doty for research assistantships. The author thanks the anonymous reviewers for approving the few papers that he has published, and his colleagues for their collaboration: Dr. Michael Laskowski, Dr. William Gasarch, Dr. David Doty, Dr. Xiaodi Wu; Dr. Shih-Han Hung, Dr. Shouvanik Chakrabarti, Dr. Kesha Hietala, Dr. Mingsheng Ying, and Dr. Michael Hicks. In partic- ular, the author thanks Dr. Shih-Han Hung for countless discussion and enlightenment in several projects on quantum programming. The author thanks Dr. Thomas Haines and Dr. Jonathan Rosenberg for many years of mathematical education, and Dr. Naizhen Zhang and Ms. Rui Ma for chatting with him about mathematics. It has been fun. The author thanks Dr. David Doty, Dr. Yujia Wei Esq., Mr. Zhenlan Hu Esq., Dr. Shouvanik Chakrabarti, Mr. Ioannis Markakis, Dr. Ilchul Yoon, Mr. Jason Filippou, Mr. Seyed A. Esmaeili, Dr. Alejandro F. Velazco, Dr. Tingxiang Zou, Mr. Yuxiang Peng, Dr. Xuchen You, Mr. Thomas Hurst, Ms. Wenchi Yan, Mr. Yizhou Zeng, Mr. Andrew Fichman, Mr. Noah Chrein, and Dr. Hamed Saleh for shedding light on life, the universe, and everything1. The author thanks Mr. Susil Abeysinghe, Ms. Menghong Li, Ms. Rui Zhang, and Ms. Jingjing Huang for their generous help through the pandemic. The author thanks Mr. Rémi Barritault for a lively summer in 2022, and many joyful and warmly encouraging communications thereafter. Que les amitiés vivent longtemps. 1Not the book “life, the universe and everything” (which the author has not read). iii The author thanks his family for life, unconditional love, and so much more. iv Table of Contents Acknowledgements ii Table of Contents v List of Tables vii List of Figures viii Chapter 1: Introduction 1 1.1 Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Hrushovski-Fraı̈ssé Classes . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Constraint Satisfaction Problems Arising from Hrushovski-Fraı̈ssé Classes 4 Chapter 2: (Z, succ, U), (Z, E, U), and the hardness of their CSP’s 5 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 A Sufficient Condition for Tractability of CSP(Z, succ, U) . . . . . . . . 9 2.4 Bounds and Characterization of CSP(Z, succ, U) . . . . . . . . . . . . . 17 2.4.1 “Lower Bounds” of CSP(Z, succ, U) . . . . . . . . . . . . . . . . 18 2.4.2 Karp-Equivalent Characterizations of CSP(Z, succ, U) . . . . . . 19 2.5 From (Z, succ, U) to (Z, E, U) . . . . . . . . . . . . . . . . . . . . . . . 24 2.6 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Chapter 3: Mα,TF and Shelah-Spencer Triangle-Free Random Graphs 38 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Simple Axiomatization of Th(M′ α⃗,(mt)t ) . . . . . . . . . . . . . . . . . . 41 3.3 Connections with (0, 1)-law of the Shelah-Spencer Triangle-Free Random Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Chapter 4: Homomorphic Presentation of Hrushovski-Fraı̈ssé classes and CSP of their generic structures 62 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.2.1 The Hrushovski-Fraı̈ssé Classes (in the language {E}) . . . . . . 66 4.2.2 Constraint Satisfaction Problems (in the langauge {E}) . . . . . . 68 4.3 Motivation: Constraint Satisfaction Problems of Hrushovski-Fraı̈ssé Classes 69 4.3.1 Mα . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 v 4.3.2 Mα,TF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.3.3 Mα,Kn−free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.4 Homomorphic Presentation of Kα,TF . . . . . . . . . . . . . . . . . . . . 77 4.4.1 K 5 6 ,TF Reduces to (1, 1)-Types . . . . . . . . . . . . . . . . . . . 84 4.4.2 More Structural Properties of Homomorphic Presentation of Kα,TF 95 4.5 Open Problems and Future Directions . . . . . . . . . . . . . . . . . . . 111 4.6 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.6.1 Towards Homomorphism-Gluability Study of Hrushovski-Fraı̈ssé Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.6.2 On (Absolute) TF-homomorphic rigidity . . . . . . . . . . . . . . 122 4.6.3 Each Kα,TF has Unbounded Treewidth and Treedepth; Indepen- dent Proof for α ∈ (8 9 , 1] . . . . . . . . . . . . . . . . . . . . . . 125 4.6.4 Closing Remarks: Potential Approaches to ω-categorical Homo- morphic Presentation of Kα,TF . . . . . . . . . . . . . . . . . . . 130 Bibliography 135 vi List of Tables 4.1 Results on CSP(Mα,Kn−free). the CSP(P2/P1) column has CSP(P2) for α ∈ (1, 2] and CSP(P1) for α > 2, as discussed in Section 4.2. All “NP”s above are conjectured NPC. . . . . . . . . . . . . . . . . . . . . . . . . . 77 vii List of Figures 2.1 Some reductions: U , CSP(Z, succ, U), CSP(Z, succ, U,0). . . . . . . . . 10 2.2 Example of Theorem 2.24 Reduction . . . . . . . . . . . . . . . . . . . . 20 2.3 Bounds and Equivalences of CSP(Z, succ, U) . . . . . . . . . . . . . . . 24 2.4 Counter Example A↓ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.5 Results for A := (Z, E, U),A↓ := (Z, E). . . . . . . . . . . . . . . . . . 35 4.1 E1 and E2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2 With H ′, h−1(H ′) as circled by the dashed ovals, the edges ((b, x), (c, y)) contribute to−2α in LHS(upstairs),−α in RHS(upstairs), and 0 in RHS(upstairs- downstairs). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.3 “Odd-K4” and “Odd-K2 3”; figure credit: [2]. Wriggled and dotted lines stand for (pairwise only disjoint) paths. Dotted lines may have length zero. Wriggled lines have positive length. The word “odd” in a face indicates that the surrounding cycle is odd. . . . . . . . . . . . . . . . . . 106 4.4 Example where theG0 embeddings and disjoint homomorphisms can’t be strong. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 4.5 Example 4.56 illustrated . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.6 To my knowledge SCE1 was first mentioned without naming in [3] as an example with mad = 10 4 which does not admit a homomorphism to the Pe- tersen’s graph. This also says CSP(M 4 5 +ϵ,TF) ⊊ CSP(M 4 5 ,TF). To see that SCE1 has enough P4s, note that the only non-adjacent pair (a, b) not con- tained in an induced copy of C5 (123451, 1′234′5′1′, 1′21541′, 1′434′5′1′) are (1, 5′), (1, 4′), (5, 5′), (5, 4′). They are respectively connected by the following induced copies of P4: 121′5′, 1234′, 541′5′, 5434′. . . . . . . . . 124 4.7 Modifying g : B − v → C5 to g̃ : B → C5 . . . . . . . . . . . . . . . . . 129 4.8 Homomorphic Amalgamation Property (HAP), [4] . . . . . . . . . . . . 130 viii Chapter 1: Introduction 1.1 Constraint Satisfaction Problems In 1990, Hell and Nešetřil [5] showed that, fixing a finite undirected graph H , the decision problem “given finite input G, does there exist a map f : V (G) → V (H), s.t. ∀x, y ( (x, y) ∈ E(G) =⇒ (f(x), f(y)) ∈ E(H) ) ?” is in P if H is bipartite, NP-complete otherwise. Such edge-preserving maps are graph homomorphisms, and the problem is called H-coloring. The definition of homomorphisms naturally generalize to arbitrary relational structures by asserting each relation is unilaterally preserved by the map between domains. This gives rise to: Problem 1.1 (CSP(H)). Parameter (Fixed): H := (D;RD 1 , . . . , R D k ) a relational structure, with the sym- bol tuple (R1, . . . , Rk) its signature. Input: a finite (R1, . . . , Rk)-structure G. Output: does G homomorphically map to H? Such problems are called the constraint satisfaction problems (CSPs); we also use CSP(H) to denote the set of inputs that answers “Yes”. Correspondingly, the SEARCH- CSPs admit the same description, except on the “Yes” instances they output a witnessing 1 h ∈ Hom(G,H). Seeing Hell-Nešetřil’s H-coloring dichotomy theorem, one naturally wonders if similar dichotomy exists for all finite relational structures. A dividing line was conjec- tured by Feder and Vardi [6]. Classification of many subclasses of finite domain CSPs (e.g. [7, 8, 9] ) were studied over the years, but the conjecture remained open until in- dependently proved by Bulatov and Zhuk ([10, 11, 12] ) in 2017. A good reference for equivalent characterizations of the finite CSP dividing line can be found in [13]. For infinite domain CSPs, dichotomy has been established for many classes of “nice” structures; for example, fixing an infinite structure (A, τ), the class {A′ := (A, τ ′) : RA′ is first order definable in A for each R ∈ τ ′} is called first order reducts of A; that is, all relational structures with the same domain A and whose finitely many relations are respectively definable in terms of A. Dichotomy has been established for the first order reducts of the Rado graph [14], of unary structures [15], and of (Q, <) [16]. These struc- tures are “nice” in that their first order theory has (up to isomorphism) a unique countable model, a property called ω-categoricity. Another line of work focuses on dichotomiz- ing the “numeric domains”, such as first order reducts of (Z, succ) [17], more generally of (Z, <) [18], and of (Z,+, 1) containing 1 [19]. A long standing open problem is to characterize first order reducts of (Z,≤,+). For thorough introduction to these topics, see [13, 20]. Instead of studying first order reducts, my Chapter 2 studies unary expansions (i.e. asserting“pre-coloring of vertices”) of the infinite directed graphs (Z, succ) as well as unary expansions of general directed graphs (Z, E). We give equivalent characterizations of such CSPs, and discuss reductions upper bounding the hardness of certain classes of 2 such unary expansions. 1.2 Hrushovski-Fraı̈ssé Classes Originally constructed by Hrushovski [21] in languages of ternary hypergraphs, Hrushovski-Fraı̈ssé classes have inspired rich bodies of literature connecting various fields of mathematics. To name a few: Baldwin-Shi [22] proved that Th(Mα), the first order theory of the generic structure ofKα, a class of finite (undirected simple) graphs, coincide with the almost sure theory of G(n, n−α), the random graph with edge probability n−α (α ∈ (0, 1]∖Q), which had been proved complete by Shelah-Spencer [23]. Laskowski [1] gave a Π2 axiomatization of Th(Mα), inspiring subsequent work on model-theoretic ap- proximation of G(n, n−α) [24, 25] and atomic models and regular types of Baldwin-Shi hypergraphs [26, 27, 28*]. Recently, Ghadernezhad, Khalilian, and Pourmahdianwas proved that the automorphism group of Mα, at least for α ∈ Q, is not amenable. [29]. In Chapter 3 we focus on a specific type of Hrushovski-Fraı̈ssé class of relational structurals, which one may think of as hypergraphs with multiple types of hyperedges. Such classes are defined by hereditary sparsity and forbidden cliques. Developping upon [1], we prove a simple axiomatization of the first order theory of the generic structures of such classes, which are infinite structures which “encodes” the original class of finite structures in a nice way. Focusing on the language of graphs, we also record some efforts towards connections with the almost-sure theory of Shelah-Spencer graphs, which is a specific type of random graphs of wide interest in computer science. 3 1.3 Constraint Satisfaction Problems Arising from Hrushovski-Fraı̈ssé Classes In Chapter 4 we “combine the two areas”, in a manner of speaking. Namely, we focus on the language of (simple, undirected) graphs, and study the CSP of generic struc- tures Mα,∗ of some Hrushovski-Fraı̈ssé classes of hereditarily linearly sparse graphs for- bidding substructures. It should be mentioned that behavior of graphs forbidding cer- tain configurations is a heavily interested topic (e.g. [30, 31]). We have some conclu- sions for complexity of CSP(Mα,∗) when the parameter α ∈ (0, 1] is large, and we have some graph-theoretically interesting findings towards characterizing such CSPs for slightly smaller αs. Work in Chapter 2 was done in Spring 2021 through Fall 2021, then collected in 2022 for publication in [32]; work in Chapter 3 was done in Fall 2020 and Spring 2021; work in Chapter 4 spanned across late 2021 to late 2022 and was tidied up in early 2023. Project-specific introductions and preliminaries are collected at the beginning of each chapter. 4 Chapter 2: (Z, succ, U), (Z, E, U), and the hardness of their CSP’s 2.1 Introduction For general introduction to CSPs, see Chapter 1. In this chapter we temporarily shift our focus onto constraint satisfaction problems of infinite template, and, as mentioned in Chapter 1, aim at characterizing CSP of unary expansion of (Z, succ) and their compu- tational complexity. The main contents of this section have been published in [32], of which the author of this dissertation was the correspondence author. So why do we care about characterizing CSP(Z, succ := {(x, y) : y = x+ 1}, U)? On one hand, an efficient greedy algorithm solves CSP(Z, succ) (Section 2.2); on the other hand, with an infinite U ⊆ Z, CSP(Z, succ, U,0) can be hard: take U to be the halting set, for example, then the reduction n 7→ the direct (n+ 1)-path 0 . . . n witnesses the undecidability of CSP(Z, succ, U,0), and likewise for U a computationally harder set, say in Π3∖Σ2. One naturally wonders how wild CSP(Z, succ, U)s could be, (Z, succ, U) being virtually “sandwiched” between (Z, succ) and (Z, succ, U,0) for each U ⊆ Z. Moreover, (Z, succ) and (Z, succ, U,0) are both non-ω-categorical: the former has 2-types {(x, x + k)}k<ω, while the latter being connected, “well-distanced”, and pointed is rigid, i.e. has trivial automorphism group. This indicates that non-ω-categoricity, a model-theoretic “wildness” bears no overall impact on the tractability of the structure’s 5 CSP. Hence {(Z, succ, U)}U⊆Z affords another entry point for classification of the CSPs of non-ω-categorical structures.1 As mentioned above, recent work ([17, 18]; see also[20]) established that for a structure A over domain Z with finite relational signature, if each relation is first-order definable in (Z, <) without parameters, then CSP(A) is either in P or NP-complete. A dichotomy has also been established when the relations are definable from unary struc- tures [15]. (Z, succ, U) however is in neither case: succ is not first order definable from unary structures2 and the only 0-definable unaries in (Z, <) are ∅ and Z.3 Therefore we prove a class of “nicely gapped” unary expansions of (Z, succ) has efficient CSP (Sec- tion 2.3,Theorem 2.17), and proceed to characterize all CSP(Z, succ, U) by gaps in U (Section 2.4, Theorem 2.24). In particular, some CSP(Z, succ, U) might be candidates for relatively natural NP-intermediate problems (Section 2.4, Corollary 2.26 and discus- sion). The characterizations in Sections (2.3)(2.4), understandably, highly relies on the arithmetic nature of (Z, succ), so it is natural to ask if they could be generalized to unary expansions of undirected graphs over Z, i.e. the (Z, E, U)s with E just an irreflexive, symmetric binary relation. We record some progress in this direction in Section 2.5, 1Aut(Z, succ) ⊇ Aut(Z, succ, U), so any Aut(Z, succ, U)-orbit on Z2, which is of the form {g(a) : g ∈ Aut(Z, succ, U)} for some a ∈ Z2, is a subset of an Aut(Z, succ)-orbit. Therefore if Aut(Z, succ) fails to partition Z2 with finitely many orbits, so does Aut(Z, succ, U). Essentially we just argued that if G1 ⊆ G2 acts on S with the G2-action non-oligomorphic, so is the G1-action. 2Note again that (Z, succ) is non-ω-categorical while purely unary structures on Z are ω-categorical, failing to record the distances; furthermore succ on Z is not 0-definable from any unary structures on Z. See also Remark 2.34. We prove the latter. Assume for the sake of contradiction that succ is 0-definable from a unary structure (Z, U1, . . . , Uk) and let ψ(x, y) ∈ Sn{Uj}j be the defining formula. Then (by taking the x-slice) every unary appearing in ψ(x, y) with free variable x has to be ∅ or Z, so is every unary appearing in ψ(x, y) with free variable y. Thus ψ(x, y) is {U1, . . . , Uk}-equivalent to a sentence, while succ(x, y) is not. 3Indeed, for unaries to be 0-definable in (Z, <) they have to be preserved by Aut(Z, <) actions, which contains all translations. 6 and give some lower bound of CSP complexity (up to direct limits) assuming reasonable structural properties in the underlying digraph. In Section 2.6 we discuss some possible future directions. 2.2 Preliminaries Definition of constraint satisfaction problems and homomorphisms are introduced in Chapter 1. More generally, homomorphisms between relational structures with the same signatures (A;RA 1 , · · · , RA k ) → (B;RB 1 , · · · , RB k ) is a map h : A → B s.t. ∀j ∈ [1, k], (a1, · · · , arj) ∈ RA j =⇒ (h(a1), · · · , h(arj)) ∈ RB j , with rj the arity of Rj . In e.g. Section 2.5, we adopt the alternative formulation: Problem 2.1 (CSP(D,S), alternative formulation). Parameters (Fixed): A structure A = (A, τA) with τ a finite relational signature. Input: a first order sentence ψ :≡ ∃x1 . . . xrR(x1, . . . , xr), where R(x1, . . . , xr) is a finite conjunction of equations (“=”) and atomics in τ . Output: does A ⊨ ψ? A walk through the definitions should convince one that these two formulations are equivalent up to the transformation ψ :≡ ∃x1, . . . , xrR1(x⃗) ∧ . . . Rj(x⃗) 7→ the structure G on vertices {x1, . . . , xr} with each RG • (• ∈ [1, j]) as positively prescribed in ψ,4 and vice versa. 5 First order sentences (resp. formulae) in the form of inputs to Problem 2.1 4That is, for the j-ary relation Rj , each (y1, · · · , yj) ∈ {x1, · · · , xr}j is in RG j ⇐⇒ Rj(y1, · · · , yj) is a conjunct appearing in ψ. 5Background on the alternative formulation: In 1978, Schaefer [33] proved the following theorem: let S be a finite collection of relations over D := {0, 1}, which we call atomics. Then for any input formula R(x1, . . . , xr) overD formed by a conjunction of atomics and equalities, the decision problem: “does there exist x∗1, . . . , x ∗ r ∈ D s.t. (D,S) ⊨ R(x∗1, . . . , x∗r)?” is always NP-complete except for six special cases. Thus begins theorists’ quest for a characterization of hardness of the CSP problems. 7 are pp-sentence (resp. pp-formulae). For A = (A, τA), a relation R ⊆ Ar is pp-definable (resp. fo-definable) without parameters in A if there exists a pp(resp. first order) τ - formula ψ(x1, . . . , xr) s.t. (a1, . . . , ar) ∈ R ⇐⇒ A ⊨ ψ(a1, . . . , ar). For L1,L2 ⊆ ⋃ n<ω{0, 1}n ∼=Set Z, write L1 ≤p m L2, read as “L1 Karp reduces to L2”, if there exists a polynomial-time computable function f : ⋃ n<ω{0, 1}n →⋃ n<ω{0, 1}n s.t. x ∈ L1 ⇐⇒ f(x) ∈ L2. In that case, call f a “polynomial-time many-one/ Karp” reduction from L1 to L2. In comparison, write L1 ≤p T L2, read as “L1 Cook reduces to L2”, if given a L2 solver ML2 , L1 can be solved by calling ML2 polynomially — again with respect to input length — many times with polynomial time overhead. Note that L1 ≤p m L2 =⇒ L1 ≤p T L2 via overhead (time cost) of f and a single call to the L2 solver; the converse is not in general true, for example NP is closed under ≤p m but not ≤p T .6 Write L1 ≡p m L2 (resp. L1 ≡p T L2) if L1 ≤p m L2 ∧ L2 ≤p m L1 (resp. L1 ≤p T L2 ∧ L2 ≤p T L1). The following is well known: Fact 2.2. (e.g. [13]) Let relational structures A := (A, τA),A′ := (A, ζA ′ ) be such that for each R ∈ τ , RA is pp-definable in A′. Then CSP(A) ≤p m CSP(A′). When describing structures (A, τA), we drop the superscript if A is clear from con- text. E.g., A = (Z, succ) is technically (Z, succA := {(x, y) : y = x + 1}). Likewise for U ⊆ Z, A := (Z, succ, U) means the unary relation on in A is interpreted as UA := U . Both CSP(Z, succ) and SEARCH-CSP(Z, succ) can be solved by the same effi- cient greedy algorithm that, for each connected component Dc of the input D, starts by 6Any L ∈ NP poly-time Turing reduces to its complement in ⋃ n<ω{0, 1}n using one oracle call and constant overhead. Since each L′ ∈ coNP arises this way, if NP were closed under ≤p T we would have coNP ⊆ NP, which is not true. This also serves as an example to show that not all Turing reductions with 1 oracle call and polynomial (in fact constant) time and space cost are many-one reductions! 8 assigning an arbitrary vertex a ∈ Dc to 0 and then assigns each of a’s neighbor to −1 (if (∗, a) ∈ succD) or 1 (if (a, ∗) ∈ succD), then recurses on those neighbors. We refer to this algorithm as the CSP(Z, succ) decider / searcher. Let A be a τ -structure; Aut(A) (resp. End(A)) denotes its group of τ -automorphisms (resp. monoid of endomorphisms). A is ω-categorical if its first order theory Th(A) (namely all sentences satisfied by A) is ω-categorical, i.e. there is exactly one countably infinite model of Th(A) up to isomorphism. Another well known fact used in Section 2.5: Fact 2.3 (e.g. [34], equivalent characterization of ω-categoricity). Let τ be a countable signature, T a complete τ -theory which has infinite models. Then the following are equiv- alent: 1. All countable models of T are isomorphic; 2. Let A ⊨ T , then Aut(A) has finitely many orbits in its action (a1, . . . , an) 7→ (ga1, . . . , gan) on An, for any n ≥ 1. 3. Some countable model of T realizes only finitely many complete n-types for each n < ω. 2.3 A Sufficient Condition for Tractability of CSP(Z, succ, U) We collect the main results in this section in Figure 2.1, where the two (more-or- less) “horizontal” reductions are simple. U ≤exp m CSP(Z, succ, U,0) by constructing the directed path D := 0 → 1 → · · · → n with UD := {n},0D = 0;7 it is exponential time 7If we view the constant symbol 0 as a unary O = {0} in order to meet the narrow definition of relational structures, we end up with a Karp-equivalent CSP(Z, succ, U,O), so for our purposes it does 9 U ≤exp m , n 7−→ 0→ 1→ · · · → n CSP (Z, succ, U,0) CSP(Z, succ, U) ≤p m , id ≤ p T when ELG-SR 1⇝ k, ELG⇝ELMS, U ⇝ lim←j Uj Figure 2.1: Some reductions: U , CSP(Z, succ, U), CSP(Z, succ, U,0). since the length|⟨n⟩| = log(n). CSP(Z, succ, U) ≤p m CSP(Z, succ, U,0) using the same input pp-sentence. The “verticle” reduction is the main goal of this section. We do not believe there is a many-one or Turing reduction fromU to CSP(Z, succ, U); intuitively, without a 0 (or any constant for that matter) to “anchor the origin”, End(Z, succ) = Aut(Z, succ) ∼= Z and only the gap patterns in U decide whether a particular transla- tion of {succ}-homomorphism makes a {succ, U}-homomorphism. In Section 4 we shall formalize this intuition; here, we give some nice conditions on the gaps to guarantee the tractability of CSP(Z, succ, U). First, things are nice if U is periodical: Observation 2.4. Let U = aZ+ b for some a, b ∈ Z. Then CSP(Z, succ, U) ∈ P. Proof. Modify the greedy algorithm that determines if an input G ∈ CSP(Z, succ). for each component De ⊆ D = (D, succD, UD), if De ∩ UD = ∅, run the CSP(Z, succ) de- cider on De; otherwise pick an arbitrary de ∈ UD∩De, then run the greedy CSP(Z, succ) algorithm on De initiated by mapping de to b. When the algorithm accepts, it yields a {succ}-homorphism he : (D, succD) → (Z, succ); accepts on this component only if not matter. Indeed, to see CSP(Z, succ, U,0) ≤p m CSP(Z, succ, U,O = {0}), for each LHS input D with 0D = d construct D̃ with OD̃ = {d}; Conversely, collapse every member of OD to one arbitrary member thereof, or create an isolated new vertex if OD = ∅. 10 he(d ′ e) ∈ U for each d′e ∈ UD ∩De. Accept D only if all components accept. If the algorithm above accepts, obviously each he is a {succ, U}-homomorphism; conversely if D ∈ CSP(Z, succ, U), so is each component De. Hence there exists some homomorphism he sending de to some x ∈ b+ aZ. Now Aut(Z, succ, U) ∼= Z composes of translations by ak (k ∈ Z), so there exists h′e ∈ Homsucc,U(De, (Z, succ, U)) sending de to b, which is the one affording acceptance of De. CSP(Z, succ, U) also behaves tamely, with its hardness upper-bounded by U , if the gaps in U are eventually large. Let us generalize this observation. Definition 2.5. Let U = {u(i)}i<ω ⊆ Z. U is eventually largely gapped (ELG) if ∃c > 0, s.t. ∀n > c, ∀n′ ∈ ω ∖ {n}, |u(n)− u(n′)| > n. As the name suggests, ELG asserts that after certain point the gaps between ele- ments are at least “linearly large” with respect to its index. Example 2.6. Let f(x) ∈ Z[x] with deg(f(x)) ≥ 2, e.g. 6x3 + 4x + 7. One may verify that Uf := {f(x) : x < ω} is ELG. 8 Example 2.7. Likewise for any differentiable g(x) : R→ R, if g(ω) ⊆ Z with superpoly- nomial growth rate and some more mild assumptions, we have Ug := {g(x) : x < ω} is ELG. E.g. g(x) = −x · 2x. 9 8As x→∞, f is eventually monotonic, and the formal derivative |f ′(x)| ∼ Ω(x), and when |f ′(x)| ∼ Θ(x) the absolute value of coefficient of x-term is at least 2. For c >> 0 we have |f(x) − f(x∗)| ≥ max{|f(x) − f(x − 1)|, |f(x) − f(x + 1)|} > x whenever c < x ∈ ω, x∗ ∈ ω ∖ {x}. So indeed Uf is ELG. 9The two more mild assumptions are (1) g is eventually monotonic and (2) |g′(x)| ∼ ω(|x|). Indeed, for x >> 0 we have |g(x)−g(x−1)| 1 ≥ |g′(x − 1)| ∼ ω(x − 1) so LHS > x eventually, and similarly, |g(x+ 1)− g(x)| > x eventually. 11 Definition 2.8. Let U = {u(i)}i<ω ⊆ Z. U has small representation (SR) if there exists a p(x) ∈ N[x] s.t. |⟨u(i)⟩| ∼ O(p(i)) for each i < ω. 10 We say U is ELG-SR if U is ELG and has SR. Example 2.9. In Examples 2.6 and 2.7, both Uf and Ug have SR, and are hence ELG-SR. Note |⟨−2n⟩| ∼ O(n). Also if U = {f(x)}x∈ω for some f(x) ∈ Z[x], then U has small representation. 11 Proposition 2.10. Let U = {u(i)}i<ω be ELG-SR. Then CSP(Z, succ, U) ≤p T U . Proof. For each connected component Dc of the input D = (D, succD, UD), reject if the CSP(Z, succ)-solver rejects on Dc; otherwise the solver finds a succ-homomorphism h : (Dc, succD ∩ D2 c ) → (Z, succ). Thanks to ELG, one needs to shift h at most |Dc| times to decide if any translation makes h a (succ, U)-homomorphism. SR ensures the absence of exponential blowup in this algorithm. We describe the procedure in more details: upon input D = (D, succD, UD), for each component De: 1. If De ∩UD = ∅, run CSP(Z, succ) decider on (De, succD ∩D2 e); if |De ∩UD| = 1, run the CSP(Z, succ) algorithm beginning with assigning the unique de ∈ De ∩UD to an arbitrary b ∈ U . Correctness follows from the observation that, in these cases we are still free to translate a succ-homomorphism as long as one exists. 10Conventionally, ⟨•⟩ is the binary representation of an integer and | • | is the length. 11Use, e.g. p(x) ∈ N[x] such that each coefficient is the absolute value of the corresponding term of f(x). The values of p(x) and f(x) are asymptotically of the same order, so the binary code of f(x∗) is short compared to p(x∗) for each x∗. 12 2. Now |De∩UD| ≥ 2. Since U is ELG, by definition there exists c ∈ ω witnessing it, i.e. gaps in U are large after index c. Pick arbitrary de ∈ De∩UD. Run Algorithm 1: while i ≤ max{c, |De|} do run CSP(Z, succ) solver on De initiated by sending de to u(i) if CSP(Z, succ) rejects then reject else //CSP(Z, succ) found h ∈ Hom(De, (Z, succ)) with h(de) = u(i) for d′e ∈ De ∩ UD do Test if h(d′e) ∈ U , reject if not end accept for De end end Algorithm 1: The reduction CSP(Z, succ, U) ≤p T U . And D is accepted if and only if each De is accepted. To see efficiency: since U has SR, |⟨u(i)⟩| is polynomial in i, 12and i is linear in |De| ≤ |D|. If a {succ}- homomorphism h is found, we have polynomially many calls to the U -oracle; note that each h(d′e) ∈ [u(i) − n, u(i) + n], so it remains polynomial size. The whole algorithm is therefore poly-calls to U with poly-overhead. To see correctness, first observe the following fact: in a connected component of 12Note we need SR here, not just U ∈ P. 13 size n, for any vertices x ̸= y the longest “signed path” (vertices x0 := x, x1, . . . , xk := y s.t. for each i, either (xi, xi+1) ∈ E or (xi+1, xi) ∈ E) has at most n − 1 edges, and the signed length (computed by adding 1 if (xi, xi+1) ∈ E and subtracting 1 if (xi+1, xi) ∈ E).13 is at most n − 1. Whenever the component homomorphi- cally maps to (Z, succ) via some h, the signed length of any signed path must be h(y)− h(x). Now for any i > max{c, |De|}, |u(i)− ∗| > i > |De| for any ∗ ∈ U ∖ {u(i)}, and with |De∩UD| ≥ 2, this gap is too big for there to exist a homomorphism sending de to u(i). In other words, De ∈CSP(Z, succ, U) ⇐⇒ ∃h ∈ Homsucc(De, (Z, succ, U)) s.t. h(de) ∈ {u(i)}i≤max{|De|,c}, which is what the algorithm checks. Corollary 2.11. If U is ELG-SR, CSP(Z, succ, U) is in P. 14 Proof. The above reduced CSP(Z, succ, U) toO(|D|)-many tests of whether each h(d′e) ∈ U . But this can be done by asking “is h(d′e) = u(j)?” for each j ∈ [0,max{c, |De|}+1]”. Both h(d′e) and each u(j) are of size polynomial in |D|, thanks to SR and the connected- ness of De. Remark 2.12. If the gaps are “eventually small” instead, we are requiring U to be finite, which puts CSP(Z, succ, U) in P by running the CSP(Z, succ) decider |U | times. Proposition 2.10 generalizes to expansion of (Z, succ) by finitely many unaries, 13Note: if for some i both (xi, xi+1) and (xi+1, xi) are in E then the graph cannot homomorphically map to (Z, succ); if between x, y there exist two different signed paths with different signed lengths, the graph is also not in CSP(Z, succ). 14Examples include all the unaries in Example 2.6. 14 modulo the following caveat: one needs to handle the “cross-set” gaps and work with the “least upper bound” of the finite collection of unaries in terms of hardness. Definition 2.13. Let k ≥ 1. A collection U := { U1 = {u(i, 1)}i<ω, . . . , Uk = {u(i, k)}i<ω ⊆ Z } is eventually largely mutually separated (ELMS) if 1. Each Uj (j ∈ [k]) is ELG, and 2. For each (j, l) ∈ ( k 2 ) , ∃cj,l > 0, s.t. • ∀nj > cj,l, ∀nl < ω, |u(nj, j)− u(nl, l)| > nj , and • ∀nl > cj,l, ∀nj < ω, |u(nl, l)− u(nj, j)| > nl. Say U is ELMS-SR if it is ELMS and each Uj (j ∈ [k]) has SR. Example 2.14. For differentiable functions f1, f2 ∈ RR each as described in Example 2.7, if they have opposite signs when restricted to ω, {Uf1 , Uf2} is ELMS; in particular e.g. for f1(x) = x3, f2(x) = −2x, {Uf1 , Uf2} is ELMS-SR. Notation 2.15. Let U1, . . . , Uk ⊆ Z. We denote by lim−→j∈[k] Uj the following set: lim−→ j∈[k] Uj := {n = mk + (r mod k) : r ∈ [1, k],m ∈ Ur} (2.1) Remark 2.16. We note that lim−→j∈[k] Uj is the least upper bound of {Uj}j in the≤p m-order of Karp-equivalent classes.15 To see this, observe that each Ur ≤p m lim−→j Uj viam 7→ mk+(r mod k), and if Q ⊆ Z is s.t. Ur ≤p m Q via fr for each r ∈ [k], then lim−→j Uj ≤p m Q via 15for similar constructions in a different setting, see e.g. [35]. 15 x 7→ fr( x−(x mod k) k ) where r =  x mod k if k ∤ x k o.w. 16 Now we generalize Proposition 2.10 and Corollary 2.11 below. Both proofs resem- ble and generalize the single-unary case. Theorem 2.17. Let {Uj}j∈[k] be ELMS-SR. Then CSP(Z, succ, (Uj)j) ≤p T lim−→j Uj . Proof. Upon input D = (D, succD, UD 1 , . . . , U D k ), for each component De: 1. If |De∩( ⋃ j U D j )| ≤ 1, like in Proposition 2.10 the gaps within and across Ujs make no impact on existence of homomorphisms. One just needs to run the CSP(Z, succ) decider / searcher starting with assinging de to an arbitrary b ∈ Uj, where UD j is the unique unary intersecting De with de the unique intersection. 2. Otherwise, let c := max of the ≤ k + ( k 2 ) constants witnessing ELMS. Then for any (j, l) ∈ k2, any n > max{c, |De|}, any n′ ∈  N if l ̸= j N∖ {n} o.w. we have |u(n, j)−u(n′, l)| > n > |De|. It follows that one needs at mostO(|De|) ∼ O(|D|) iterations, for n ∈ [0,max(c, |De|)]. Fix arbitrary de ∈ De ∩ ( ⋃ j U D j ) before iterating. Within each iteration, run CSP(Z, succ) assigning de to some u(n, y) where de ∈ De ∩ UD y , n is the itera- tion number (n ≤ max(c, |De|)). Since Uy has SR, u(n, y) has size polynonial in n, and n is linear in |D|. If a succ-homomophism h is found, verify whether h(d′e) ∈ Uy′ for each d′e ∈ De ∩ UD y′ . Via Uy′ ≤p m (hence ≤p T ) lim−→j Uj , the deci- sion of Uy′-membership of h(d′e) reduces to calls to the lim−→j Uj-oracle. Note each 16Note when k ≥ 2, x 7→ x−(x mod k) k does not describe a many-one reduction from lim−→j Uj to any Uj as there are different congruent classes. 16 h(d′e) ∈ [u(n, y)−|De|, u(n, y)+ |De|], so the reduction is of time polynomial with respect to |D|. Corollary 2.18. If {Uj}j is ELMS-SR, Then CSP(Z, succ, U1, · · · , Uk) ∈ P. Proof. As in Corollary 2.11, for each h(d′e), ask if h(d′e) = u(s, t) for each t ∈ [1, k] involved, s ∈ [0,max{c, |De|} + 1]. By SR and connectedness, both h(d′e) and each u(s, t) have size polynomial in |D|. We exhibit an interesting application of the result in this section: Corollary 2.19. Let f(x), g(x) ∈ Z[x] with different degrees, both non-0, and different signs in the term of highest degree. Then CSP(Z, succ, {f(x)}x∈ω, {g(x)}x∈ω) ∈ P. Remark 2.20. With 3 or more polynomials, application of the Theorem may get issues in number theory.17 2.4 Bounds and Characterization of CSP(Z, succ, U) We now proceed to more general cases, bearing in mind that less restrictions on the unitaries usually means less control over the behavior of expansion of (Z, succ) with those unaries. 17Consider e.g. U3 = {x3}x∈ω . Then {U1, U2, U3} is not ELMS; in fact even {U1, U3} are not. In particular, x2 − y3 = 0 has infinitely many solutions (x, y) ∈ N2: take any prime p, then for each k > 0,( p3·2 k)2 = ( p2 k+1)3 . 17 2.4.1 “Lower Bounds” of CSP(Z, succ, U) Let U ⊆ Z be arbitrary. Recall CSP(Z, succ, U) ≤p m CSP(Z, succ, U,0) as the upper bound. It would be nice if the converse held, but we believe it is unlikely due to similar “anchoring” issues (See e.g. Section 2.3 and infra). However, Proposition 2.21. CSP(Z, succ, U,0) ≤p T lim−→ { U, CSP(Z, succ, U) } . Proof. Test the linearly many non-0 components of the input by CSP(Z, succ, U)-oracle calls. For the 0-component, find if a {succ,0}-homomorphism h exists, and makeO(|D|)- calls to the U -oracle to find if h is a {succ, U,0}-homomorphism. In more details: upon each input D = (D, succD, UD,0D), let D0 := the unique component containing 0D. Call CSP(Z, succ, U)-oracle on D∖D0 and echo if rejects. Call the CSP(Z, succ)-solver on (D0, succD ∩ D2 0) initiated by sending 0D to 0, and echo if rejects; otherwise, the unique succ-homomorphism h : (D0, succD ∩D2 0) → (Z, succ) that satisfies h(0D) = 0 has been found, and one just needs to verify if for each d we have h(d) ∈ U by calling the U -oracle. Note each h(d) ∈ [0 − |D0|, 0 + |D0|] so input size remains polynomial in |D0| ≤ |D|. The only oracles we called above are the U -oracles and CSP(Z, succ, U)-oracles, both of which Karp (hence Cook) reduces to the lim−→-oracle on RHS. Hence, up to taking direct limit with U , CSP(Z, succ, U) is “lower bounded” by CSP(Z, succ, U,0) in the ≤p T -order. A notable corollary: Corollary 2.22. IfU ∈ P, orU ≤p T CSP(Z, succ, U), then CSP(Z, succ, U) ≡p T CSP(Z, succ, U,0). Proof. If U ∈ P, calls to the U -oracle counts as polynomial time overhead; if U ≤p T 18 CSP(Z, succ, U), note the direct limit can be computed as  χU( n−1 2 ) if n = 2k + 1 χCSP(Z,succ,U)( n 2 ) o.w. , where χS(•) is the membership function of set S, and χU can be computed by computing χCSP(Z,succ,U) now at polynomial cost. 2.4.2 Karp-Equivalent Characterizations of CSP(Z, succ, U) Recall (e.g. Section 2.3) that intuitively, for any U ⊆ Z its gap patterns determine the members of CSP(Z, succ, U), and conversely one may recover the gap patters of U from CSP(Z, succ, U). Our characterization below formalizes this intuition. Definition 2.23. Let U ⊆ Z with |U | ≥ 2. Define Gap(U) := { (n, S1, S2) ∈ ( ω∖{0, 1} ) ×2( n 2)×[−n, n]S1 ∣∣∣ ∃t ∈ Un, (∀(i < j) ∈ S1)(t(j)−t(i) = S2(i, j)) } Informally Gap(U) is the collection of gap patterns “partially realized in U” by some U -tuple. In particular, S2 : S1 → [−n, n] is a function assigning each pair of in- dices (i, j) ∈ S1 to a distance ui − uj ∈ [−n, n] with ui, uj ∈ U , i.e. ui, uj witnesses the fact that such a distance is realized in U .18 Note, though, that having S1 ⊆ ( n 2 ) is crucial: we need to include the cases where only some distances between the n vertices are spec- ified. This corresponds to the fact that homomorphisms only remember adjacencies but tolerates non-adjacencies in the target. The machinery affords the following equivalent characterization: 18In the definition it should really read that n ∈ ω∖ {0, 1}, S1 ⊆ ( n 2 ) , S2 ∈ ( [−n, n]∖ 0 )S1 , and ∃t . . . . We write in the current way for a bit more succinctness of representation. 19 Theorem 2.24. Let U ⊆ Z with |U | ≥ 2. Then Gap(U) ≡p m CSP(Z, succ, U). Proof. The idea is as follows: on a Gap(U)-instance (n, S1, S2), construct D as follows: start with D = UD = {1, · · · , n}, then add paths of length S2(i, j) between vertices i, j for each (i < j) ∈ S1. Conversely, on a CSP(Z, succ, U)-instance D = (D, succD, UD), first let the subgraph D′ collect each D-component that intersects with UD at more than 1 vertices; let n := |D′ ∩ UD|, and let (S1, S2) keep track of the positive finite distances of each UD-pair that lies on the same component of D′. Before going into the full details, we illustrate the reductions with the following example (Figure 2.2): ( 3, ( 3 2 ) , (1, 3, 1) ) ( 3, ( 3 2 ) , (1, 3, 2) ) 7−→ 1⃝ 2⃝ 3⃝ ((1, 3), 1) ((1, 3), 2) 1 −→ 2⃝ −→ 3⃝ −→ 4 −→ 5⃝ 6 −→ 7 ←− [ ( n⃝ ∈ UD) Figure 2.2: Example of Theorem 2.24 Reduction 1. ≤p m: upon (n, S1, S2), construct D := {1, . . . , n}, succD = ∅, UD := D. Then for each (i < j) ∈ S1: (a) If S2(i, j) > 0, add intermediate vertices and edges i = ( (i, j), 0 ) succD−→( (i, j), 1 ) succD−→ . . . succD−→ ( (i, j), S2(i, j) ) = j. (b) If S2(i, j) < 0, add intermediate vertices and edges i = ( (i, j), 0 ) succD←−( (i, j), 1 ) succD←− . . . succD←− ( (i, j), |S2(i, j)| ) = j. (c) if S2(i, j) = 0, collapse vertices i ∼ j (so now the “vertex classes” [i] = [j]). 20 NowD = { [1], . . . , [n] } ∪ {( (i, j),m )} S2(i,j) ̸=0,m∈[1,|S2(i,j)|−1] andUD = { [1], . . . , [n] } . Note |D| ≤ n + n × ( n 2 ) , and as S1 is part of the tuple, |D| is polynomial in |⟨(n, S1, S2)⟩|, so (n, S1, S2) 7→ D = (D, succD, UD) is a polynomial-time con- struction. Further, (a) If (n, S1, S2) ∈ Gap(U) witnessed by t ∈ Un, let h : D → Z, [j] 7→ t(j) (j ∈ [1, n]) and extend naturally to the intermediates, i.e. ( (i, j),m ) 7→ t(i)+ sign(S2(i, j))×m. The map puts D ∈ CSP(Z, succ, U). (b) If D ∈CSP(Z, succ, U) by h, then ( t(i) = h([i]) ) i∈[1,n] witnesses (n, S1, S2) ∈ Gap(U). 2. p m ≥: Observe that s1 := ( 3, ( 3 2 ) , ( 1︸︷︷︸ S2(1,2) , 3︸︷︷︸ S2(1,3) , 1︸︷︷︸ S2(2,3) )) /∈Gap(U) due to triangle- inequality, and taking arbitrary u1 ̸= u2 ∈ U (not UD), s2 := ( 2, { (1, 2) } , ( u2 − u1 )) ∈ Gap(U). s1, s2 are input-independent. Now let D = (D, succD, UD). We want to produce a short tuple sD = (n, S1, S2) in time polynomial in |D|. We present an algorithm for that. (a) Run CSP(Z, succ) decider/searcher on D, and halt setting sD := s1 if reject was returned; else, we obtain an h ∈ Homsucc ( (D, succD), (Z, succ) ) from the run. (b) Throw away the components De with |De∩UD| ≤ 1, keeping D′ := ∐ e:|De∩UD|≥2De. If D′ = ∅, halt setting sD := s2. (c) Let n := |UD ∩ D′|; now n ∈ [2, |D′|]. Enumerate elements in UD ∩ D′ as v1, . . . , vn; let S1 := {(i < j) : vi, vj are from the same component }. Let 21 S2(i, j) := h(vj)− h(vi) with h from Step 2a. Let sD := ⟨(n, S1, S2)⟩. sD has size polynomial in |D| and the algorithm is efficient. Correctness: (a) Assume D ∈CSP(Z, succ, U) witnessed by h′, then sD ̸= s1 for h′ ∈ Homsucc ( (D, succD), (Z, succ) ) and the CSP(Z, succ)-decider should’ve caught a homomorphism. • If D′ ̸= ∅: for each vi ̸= vj from the same component in D′, h′(vj) − h′(vi) = h(vj) − h(vi). Therefore setting ti = h′(vi) for each i ∈ [1, n], we get a witness for (n, S1, S2) ∈ Gap(U). • If D′ = ∅, we exited with an s2 ∈ Gap(U). (b) Assume sD ∈ Gap(U), then again sD ̸= s1. • If sD = s2 then the h from Step 2a translates componentwise and then patches to a {succ, U}-homomorphism. • otherwise there exists t ∈ Un with t(j)− t(i) = S2(i, j) (∀(i < j) ∈ S1). Each component in D′ contains a vie ∈ UD ∩D′; shift h ↾De s.t. h(vie) = t(ie). Now for each vje ̸= vie ∈ De ∩ UD, h(vje) = h(vie) + S2(ie, je) = t(je) ∈ U . Do so for each component of D′. Lastly for each component in D∖D′, shift h if need be. Remark 2.25. It may be worthy of mentioning that, letting P := the set of prime num- bers, then the twin-prime conjecture is equivalent to a Π0 2 statement about Gap(P). In particular, the twin-prime conjecture holds if and only if the following statement holds: 22 ∀k > 4,∃k′ > k, s.t. ( k′, ( (1, 2), (2, 3), (3, 4) ) ,  (1, 2) 7→ 1, (2, 3) 7→ k′, (3, 4) 7→ 2 ) ∈ Gap(P). Each witnessing k′ is necessarily even. Indeed, if twin prime conjecture holds, for arbitrarily large k > 4 one may find k′ > k, p ∈ P , p − 3 = k′ and p + 2 ∈ P . Then (2, 3, p, p + 2) realizes the prescribed distance in P . Conversely if the statement above holds, then for any k > 4, k′ > k, we must have the witnessing (u1, u2) = (2, 3). Furthermore (u3, u4) is a twin prime with u3 − u2 = u3 − 3 = k′. Arbitrariness of k would ensure that there are infinitely many twin primes. We close the section with an interesting question: Question 2.26. Let V ⊆ ω be infinite. Is there a UV ⊆ Z s.t. V ≤T Gap(UV ), and if not, what’s an equivalent characterization? That is, we would like for any infinite set V of naturals, there exists a set UV whose “gap patterns” decide V -membership. Assuming that, an immediate corollary would be the unboundedness of computational complexity of Gap(U) and CSP(Z, succ, U)s in gen- eral. If, in addition, ≤T in Question 2.26 could be refined to ≡p m, then Ladner’s theo- rem [36] and a recent construction [13, 37] would imply the existence of NP-intermediate CSPs and CoNP-intermediate CSPs respectively of the form CSP(Z, succ, U). Combined with results from last section, we summarize our results in Figure 2.3. 23 U CSP(A) ≤ p T when A := (Z, succ, U) ELG-SR ≤p m , CSP (A,0) ≤exp m CSP (A,0) “≤ p T ”up to lim → {U, •} ≡p m Gap(U) Figure 2.3: Bounds and Equivalences of CSP(Z, succ, U) 2.5 From (Z, succ, U) to (Z, E, U) Now we generalize our results in Sections (2.3)(2.4) into arbitrary partially-1- colored digraphs on Z, i.e. structures of the form (Z, E, U) with E ⊆ Z2, U ⊆ Z. In particular, some primitive conditions for a Proposition 2.21-type reduction is presented (Theorem 2.31,Proposition 2.37), with the hope that some future research could yield further refined characterizations of (Z, E, U)-structures. Note that: 1. The converses of Proposition 2.21-type reductions, i.e. (Z, E, U) ≤p m (Z, E, U,0), always hold by the identity reduction (e.g. as pp-sentence).19 2. All arguments in Theorem 2.31 to Proposition 2.37 below generalize to (Z, E⃗, U⃗), i.e. with finitely many binaries and finitely many unaries; 0 may be changed to c for any c ∈ Z. In these general cases we need a careful definition of connected 19Similarly by (Z, E) ≤p m (Z, E, U), we know there are (Z, E, U)s whose CSP is not in NP: just let the underlying (Z, E) be such that its CSP is CoNP-complete, which exists by Theorem 13.3.1 [13].Although that digraph is not originally defined on Z, it is a Fraı̈ssé limit hence countable and by a bijection to Z on the vertices, it can be made into the form (Z, E). 24 components , 20 and the arguments would be longer, but still completely analogous. For the ease of presentation, we assume our current format in the main text. As a motivating example, fix any d ≥ 1 and consider the relation Diffd(x, y) ⇐⇒ y = x + d. Note that Diffd is pp-definable in (Z, succ). The digraph (Z,Diffd) consists of d pairwise isomorphic components, each on a coset of dZ. Each component is also isomorphic to (Z, succ), therefore (Z, succ)→ (Z,Diffd) by isomorphism with one com- ponent, while (Z,Diffd) → (Z, succ) by first collapsing all components to one and then applying the isomorphism with RHS. It follows that CSP(Z, succ) = CSP(Z,Diffd), and SEARCH-CSP(Z,Diffd) ∈ P by running the SEARCH-CSP(Z, succ) solver and then ap- plying the isomorphism with a (Z,Diffd)-component. Moreover, just as fixing one vertex fixes a homomorphism – if any exists – to (Z, succ), for finite connected {Diffd,0}- structure D we have D ∈ CSP(Z,Diffd,0) ⇐⇒ |HomDiffd,0(D, (Z,Diffd,0))| = 1 (2.2) Indeed, LHS ⇐= RHS because |HomDiffd,0(D, (Z,Diffd,0))| > 0, and =⇒ follows 20One may even have freedoms on the arities of the non unaries {Ej}j . In these cases, call x, y ∈ Z “ connected” if (a) (Base) there exists some j ∈ [1, k] s.t. (. . . , x, . . . , y, . . . ) or (. . . , y, . . . , x, . . . ) ∈ ED j . OR (b) ∃z s.t. x, z are connected and z, y are connected. Call D′ ⊂ind D a connected component of D if for any x ̸= y ∈ D′, x and y are connected; and ∀x ∈ D′, ∀z /∈ D′, x, z are not connected. (This happens if and only if the Gaifman graph of D′ is a connected component of the Gaifman graph of D.) Vacuously, an isolated vertex (an x ∈ D that does not appear in any ED j with arity ≥ 2) is a connected component. A {E1, . . . , Ek, c}-structure D is connected if D itself is a connected component; equivalently, D is not the disjoint union of two or more connected components. A notable property relevant to later discussion: when a finite, connected {E1, . . . , Ek}-structure D has ED j = ∅ for all j ∈ [1, k] then |HomE1,...,Ek,c(D, (Z, EA 1 , . . . , E A k , c A))| = 1 for free, because D = {cD} in this case: cD is its own connected component and D is connected. 25 from the fact that 0D must map to 0 and then the homomorphism must extend linearly as if in (Z, succ,0). Further expanding the structure by U ⊆ Z, we no longer have CSP(Z, succ, U) = CSP(Z,Diffd, U): the gaps are not preserved by the homomorphic equivalence between base structures. However by an argument similar to Section 2.3 Proposition 2.21, one may obtain: Observation 2.27. Let U ⊂ Z. Then CSP(Z,Diffd, U,0) ≤p T lim−→ { U, CSP(Z,Diffd, U) } . Proof. Similar to that of Proposition 2.21. 1. For each component De s.t. 0D /∈ De, call the CSP(Z, succ, U)-oracle, which reduces to the lim−→ { U, CSP(Z,Diffd, U) } -oracle. 2. For the unique component D0 ∋ 0D, run the greedy, efficient SEARCH-CSP(Z,Diffd) algorithm to decide if there is a (unique) {Diffd,0}-homomorphism h. Reject if none found. Having found h, for each u ∈ UD ∩ D0, call U -oracle on h(u). Note that h(u) ∈ [−|D|, |D|] and the oracle call once again reduces to calling lim−→ { U,CSP(Z,Diffd, U) } . Remark 2.28. Other interesting properties of CSP(Z,Diffd, U) may be said. For example: 1. One may define eventually d-largely gapped ( ELGd ) ( respectively eventually d- largely mutually separated ( ELMSd )) analogously to Definitions 2.5, 2.13, chang- ing “|u(n, ∗)− u(n′, ∗)| > n” into “|u(n, ∗)− u(n′, ∗)| > dn”. Keeping the defini- 26 tion of SR (2.8) unchanged, we have CSP(Z,Diffd, U) ≤p T U when ELGd-SR, and CSP(Z,Diffd, U⃗) ≤p T lim−→ U⃗ when ELMSd-SR. 2. Note that Aut(Z,Diffd) ∼= Sd × (dZ)d ∼= Sd × Zd as groups: indeed, an automor- phism permutes the connected components and then shifts on each component by a distance in dZ. Remark 2.29. The above does not necessarily work for (Z,Distd, U)s where Distd(x, y) ⇐⇒ |y − x| = d, a relation defined in e.g. [17]; to begin with, (Z,Distd) ̸→ (Z, succ), LHS failing to be directed acyclic. Now consider any partially-1-colored digraph A := (Z, E, U). We are interested in generalizing Section 2.3 results to complexity lower bounds of CSP(A). Definition 2.30. Let U ⊆ Z, E ⊆ Z2, and A := (Z, EA := E,UA := U). Consider its reduct21 A↓ := (Z, E). Let 0 be a constant.22 We say A↓ is 1. pointed homomorphically rigid (PHR) if if for any finite, connected {E,0}-structure D, D ∈ CSP(A↓,0) ⇐⇒ |Hom{E,0} ( D, (A↓,0) ) | = 1 (2.3) That is, for any {E,0}-structure D there exists at most one {E,0}-homomorphism to (A↓,0). 2. freely translational (FT) if AutE(A↓) contains all translations fz : x 7→ x + z (z ∈ Z). 21I.e., forgetting U . 22Any interpretation of 0 works; without loss of generality we pick 0(A,0) = 0 ∈ Z. 27 Note that the definition above does not “touch and concern” U . Therefore, Theorem 2.31. Let A↓ be PHR and FT. Then, for any U ⊆ Z, CSP(A,0) ≤p T lim−→ { U,CSP(A),SEARCH-CSP(A↓) } (2.4) Remark 2.32. When E = succ, we have SEARCH-CSP(Z, E) ≤p T CSP(Z, E) ∈ P which gives back Proposition 2.21. In general we do not know if the Search to Decision reduc- tion works for infinite structures. Proof. [Proof of Theorem 2.31] Similar to Proposition 2.21. Decompose input D = (Z, ED, UD,0D) into connected components.23 For components Db avoiding 0D, call the CSP(A) oracle. For D0 ∋ 0D, find an {E}-homomorphism h : D0 → (A↓) if it exists, by calling SEARCH-CSP(A↓). By FT, s : x 7→ x − h(0D) is an E-endomorphism, hence s ◦ h is an “pointed” E-homomorphism where 0D 7→ 0 = 0A, i.e. an {E,0}-homomorphism. By PHR, s ◦ h is the unique {E,0}-homomorphism D0 → (A↓,0). Now to check if s ◦ h is further an {E,0, U}-homomorphism, simply test if s ◦ h(u) ∈ U = UA for each u ∈ UD ∩D0.24 Theorem 2.31 says that when the underlying digraph A↓ = (Z, E) has nice alge- braic properties (PHR-FT), one obtains a generalized quasi-lowerbound of CSP(A) “up 23When further generalizing to multiple non-unary relations, worst case this involves looking at each (x, y) pair and for each pair looking at each ED j , which is O(|D|2 × |D|k), polynomially bounded. Note that k is a constant. 24Note that the runtime of this SEARCH-CSP accounts for the time to write down the h(x)s for each x ∈ D. Later when we compute the shift a − h(0D), the overhead is dominated by the runtime of the SEARCH-CSP. The total overhead of computing s ◦ h is therefore at most that of running O(|D|) times of the SEARCH-CSP cost. 28 to direct limit” , A being the unary expansion of A↓, and the bound is given by CSP of the pointed structure (A,0). In fact, this observation also has some structural implications: Proposition 2.33. For (A↓,0) = (Z, E,0), let A↓0 denote its central component, i.e. the pointed component of the underlying digraph containing 0. 1. If A↓ is PHR, then EndE,0(A ↓ 0) = {1}. The converse is false. 2. If A↓ is FT, then A↓0 has infinite domain. 3. If A↓ is PHR-FT, then (A↓,0) is not ω-categorical, unless E = ∅. Remark 2.34. If E = ∅ then (A,0) is indeed ω-categorical. For any n ≥ 1, a complete n-type (x1, . . . , xn) only needs to make a decision for each xi as to whether xi ∈ U , and whether xi = 0. Thus there are finitely many complete n-types for any n. Likewise (A↓,0) is ω-categorical for having even fewer n-types. Proof. [Proof of Proposition 2.33] 1. Assume for contradiction that EndE,0(A ↓ 0) ̸= {1}, so there exists σ ∈ EndE,0(A ↓ 0) and a ̸= b ∈ A↓0 s.t. σ(a) = b. Note that a ̸= 0 for σ preserves 0. By connect- edness, there exists a finite signed path 0 . . . a ⊆ A↓0, i.e. for each (i, i + 1) pair on [0, a], either (i, i + 1) ∈ EA↓ 0 or (i + 1, i) ∈ EA↓ 0 . Take D := A↓0[{0, . . . , a}] , which is again connected thanks to that signed path. Let h1 : D ↪→ A↓0 the em- bedding. Now, h2 := σ ◦ h1 ∈ HomE,0(D,A ↓ 0) with b = h2(a) ̸= h1(a) = a, contradicting PHR. We show that conversely, even ( EndE,0(A ↓ 0) = {1} ) + FT ≠⇒ PHR.25 In fact, Figure 2.4 below has ( EndE,0(A ↓ 0) = {1} ) + FT but no 25If the implication were true, for Theorem 2.31 we would have algebraic conditions without reference of “all finite connected τ -structures”, which would be considerably cleaner. 29 PHR: D embeds in (A↓,0) in 2 ways. Verification is routine . 26 0⃝ = 0A 2 4 6 . . .. . . −2−4−6 −5 −3 −1 1 3 5 ( A↓, 0 ) := (Z, E, 0) D : 0⃝ = 0D 1as above, Figure 2.4: Counter Example A↓ 2. Assume E ̸= ∅ and assume for the sake of contradiction that |A↓0| < ℵ0. (a) If |A↓0| = 1, take (a1, a2) ∈ E. Note that a1, a2 ̸= 0 since A↓ is iso- lated. The translation σ : x 7→ x − a1 fails to be an {E}-endomorphism, as (σ(a1), σ(a2)) /∈ EA↓ . This contradicts FT. (b) Otherwise ℵ0 > |A↓0| ≥ 2. Let b ∈ A↓0 ∖ {0} be of maximal absolute value in A↓0. As A↓ has FT and endomorphisms preserve connectedness, by repeatedly applying the translation x 7→ x+ b we obtain that {kb}k<ω ⊂ A↓0, contradicting ℵ0 > |A↓0|. 26Without naming the constant, each vertex has in-degree 2 and out-degree 2, so any translation is an {E}-endomorphism — in fact even an automorphism, yielding FT. Furthermore, after naming 0A := 0, its predecessors and successors are fixed: let σ ∈ EndE,0(A ↓,0). σ(2), σ(1) ∈ {2, 1} yet if σ(2) = 1, neither σ(1) = 1 nor σ(1) = 2 would give EA(σ(1), σ(2)). It follows that σ(2) = 2. Likewise, σ(±1) = ±1 and σ(−2) = −2. For |n| ≥ 3, σ(n) = n follows from induction. The fact that vertices further away are fixed follow from induction, so EndE,0(A ↓ 0) = EndE,0(A ↓, 0) = {1}. On the other hand, D := 0D = 0 → 1 embeds into both 0→ 1 ⊂ A and 0→ 2 ⊂ A. Remark 2.35. One might also want to note that a claim stronger than Prop. 2.33(1), that PHR =⇒ EndE,0((A ↓,0)) = {1}, is also false. Consider A↓ := (Z;E,0 := 0) with edges defined as · · · − 8→ −7→ −6→ −5 − 4← −3 − 2← −1 0→ 1→ 2→ 3→ 4→ . . . Any connected finite {E,0}-structure must homomorphically map to the non-negative, so a {E,0}- homomorphism exists iff D is loopless, directed acyclic, and each vertex has a non-negative signed dis- tance from 0D (i.e. never “a → 0D”). Each {E,0}-homomorphism from such Ds should it exist, must be unique, mapping each vertex to its distance from 0D. However End{E,0}((A ↓,0)) contains swapping −4← −3 with −2← −1. 30 3. We have EndE,0(A ↓ 0) = {1} and |A↓0| = ℵ0. Now AutE,0(A ↓,0) ⊆ AutE,0(A ↓ 0) ⊆ EndE,0(A ↓ 0) = {1}, so (A↓,0) = (Z, E,0) is rigid, and AutE,0(A ↓,0) on Z has infinitely many orbits. (A,0) being an expansion of (A↓,0) is also rigid. Proposition 2.33 (2) implies that, when |A↓0| < ℵ0, we need a different condition to guarantee a generalized lowerbound simialr to Section 2.3, which we address next. Definition 2.36. Let A = (Z, E, U) so (A↓,0) = (Z, E,0) with A↓0 its the central com- ponent. Say A↓= (Z, E) has Transitive Endomorphism-action on Hom sets (TEH) if for any finite, connectedE-structure D, EndE(A ↓[A↓0]) acts transitively on HomE(D,A ↓[A↓0]) by post-composition. Note that A↓[A↓0] is the substructure of A↓ induced on A↓0’s central component. Proposition 2.37. If |A↓0| < ℵ0 and A↓ has TEH, then: CSP(A,0) ≤p T lim−→ { U,CSP(A),CSP(A↓[A↓0]) } (2.5) Changing CSP(A↓[A↓0]) to SEARCH-CSP(A↓[A↓0]) would give us a stronger state- ment that remains correct, but we use the following fact to get the current more succinct form: Proposition 2.38 (e.g. Exercise in [38]without proof). Let A be a finite relational structure. Then SEARCH-CSP(A) ≤p T CSP(A). Proof of Proposition 2.38. A fun exercise. Conceptually mimics the Search to Decision reduction for SAT. As in graphs, a core B ⊂ind A is a minimal image of endomorphisms, 31 i.e. there exists no σ ∈ End(A) s.t. σ(A) ⊊ B. For finite As, cores always exist and are unique up to isomorphism [13]. are isomorphic,27 so hereinafter we talk about “the” core of A. Let B be the core of A, then inclusion B ↪→ A and the definitional endomorphism A → B shows homomorphic equivalence of A and B, so suffices to show SEARCH- CSP(A) ≤p T CSP(B).28 To make the description less cumbersome let’s define POINTED-CSP: fix arbitrary b ∈ B. POINTED-CSP(B, b) takes a pair (D, d) with D a finite τ -structure, d ∈ D, and returns 1 iff there exists h ∈ Homτ (D,B) s.t. h(d) = b. Claim: POINTED-CSP(B, b) ≤p m (hence ≤p T ) CSP(B). Proof of Claim. Upon a POINTED-CSP(B, b) input (D, d), let D̃ := D ∪B b ∼ d .29. This is a polynomial time construction since |B| ∼ O(1). I claim (D, d) ∈ POINTED-CSP(B, b) ⇐⇒ D̃ ∈ CSP(B). 1. =⇒ : let h : (D, d) → (B, b) be a basepoint-preserving homomorphism. Then h̃ : D̃→ B, h(x) :=  h(x), if x ∈ D x, o.w. is a homomorphism. 2. ⇐= : let h : D̃ → B be a homomorphism. Then h|B : B → B is an endomor- phism of the finite core B. Since an endomorphism of a core is an automorphism,30 27(e.g. [39] for proof of isomorphism of cores in the special case of graphs) Let B1,B2 ⊂ind A be cores, witnessed by e1 : A → B1, e2 : A → B2, two surjective homomorphisms (otherwise B∗ is not a core). Then e1|B2 is also surjective, for otherwise (e1|B2 ) ◦ e2 gives an induced substructure of B1 which is an endomorphic image. Dually e2|B1 is surjective. Therefore |B1| = |B2|, e1|B2 and e2|B1 are bijective homomorphisms, and we have the isomorphism. 28Note: A is input-independent, hence core(A) = B. 29That is, take a copy of D and a copy of B, glue b and d. 30e : B→ B must be surjective, so bijective. As Ime ⊆ind B, the bijectivity says Ime = B. In particular this says e preserves the number of solutions for each Ri, i.e. there cannot be (a1, . . . , ari) /∈ RB i s.t. (e(a1), . . . , e(ari)) ∈ RB i . It follows that e preserves the relations bidirectionally, hence an automorphism. 32 there exists σ ∈ Aut(B) = End(B) s.t. σ ◦ (h|B) = 1B. Now σ ◦ (h|D) is a ho- momorphism D→ B sending d to σ(h([d])) = σ(h([b])) = b, which is the desired witness. Analogously if we define a m-POINTED-CSP(B, b1, . . . , bm) it also Karp-reduces to CSP(B), the reduction being (D, d1, . . . , dm)⇝ D̃ := D ∪B {di ∼ bi}i∈[1,m] . 31 An algorithm that calls the CSP(B)-oracle to solve SEARCH-CSP(A) therefore goes as: if D /∈ CSP(B) then Reject for i ∈ [1, |D|] do for j ∈ [1, |B|] do if (D, d1, . . . , di) ∈ POINTED-CSP(B, h(d1), . . . , h(di−1), bj) then Set h(di) := bj break //break inner iteration, go to next i end reject end Algorithm 2: Querying CSP(B)-oracle to solve SEARCH-CSP(A) Algorithm 2 finds a full homomorphism D→ B ⇐⇒ D ∈ CSP(B) = CSP(A) so it solves SEARCH-CSP(A); furthermore it calls the CSP(B)-oracle O(nk) times. =⇒ 31Note e.g. when m = 2 in the ⇐= direction has σ ◦ h|D sending [di] to [bi] for both i as each bi ∈ B. 33 is by definition, and to see ⇐= , note that the existence of an h : D→ B means for each i ∈ [1, |D|] there exists some j ∈ [1, |B|] s.t. h(di) = bj , i.e. the existence of an accepting path.32 Proof of Proposition 2.37. As before, decompose D = (D,ED, UD,0D) into connected components and let the CSP(A) handle the non central components. For the central component, call SEARCH-CSP(A↓[A↓0]) oracle, which thanks to |A↓0| < ℵ0 and Fact 2.38 Cook reduces to CSP(A↓[A↓0]). If we found an h ∈ HomE((D,E D),A↓[A↓0]), by the assumption, all h′ ∈ HomE((D,E D),A↓[A↓0]) is of the form σh for different σs in EndE(A ↓[A↓0]). Note that |A↓0| < ℵ0 =⇒ |EndE(A ↓[A↓0])| ≤ |A↓0||A ↓ 0| < ℵ0 and |EndE(A ↓[A↓0])| is input-independent. Each σi ∈ |EndE(A ↓[A↓0])| is a finite domain function, whose en- coding is also input-independent.For each of the O(1)-many σi ∈ |EndE(A ↓[A↓0])|, com- pute σih (Since σi is input-independent and A↓0 is constant-sized, time and space cost is dominated by computing h, which is again dominated by the oracle call to CSP(A↓[A↓0])); then check if σih preserves 0D in O(1) time and if σih preserves the unary by calling the U -oracle. Corollary 2.39. Let U ∈ P. 1. If A↓ = (Z, E) is PHR-FT and if SEARCH-CSP(A↓) ≤p T CSP(A↓), OR 2. If |A↓0| < ℵ0 , A↓ has TEH, and if CSP(A↓[A↓0]) ≤p T CSP(A↓), 32The algorithm also has the benefit that whenever a homomorphism is found, the solution tuple (h(d1), . . . , h(d|D|)) = (bs,1, . . . , bs,|D|) is the minimal element in the dictionary order by indices in the target. That is, for any other solution (b′s,1, . . . , b ′ s,|D|) ∈ B|D| = (b1 ≺ · · · ≺ b|B|) |D|, (bs,1, . . . , bs,|D|) ⪯ (b′s,1, . . . , b ′ s,|D|). 34 then CSP(A,0) ≡p T CSP(A). Proof. With assumption set 1, by U ∈ P and CSP(A↓) ≤p m CSP(A), all other terms in the direct limit are reduced to CSP(A). Likewise for assumption set 2. We summarize our main results of this section in Figure 2.5. A := (Z, E, U) CSP (A,0)CSP (A,0) CSP (A,0)CSP (A,0) CSP (ACSP (A) ≤p m ” ≤ p T ” (**) (**): up to lim→{U,SEARCH-CSP(A↓), •} with conditions (e.g. (PHR + FT)) OR (**): up to lim→{U, CSP(A↓[A↓0]), •} with conditions (e.g. TEH) Figure 2.5: Results for A := (Z, E, U),A↓ := (Z, E). 2.6 Future Directions In Sections 2.3 and 2.4, we studied how properties of U impacts the complex- ity of CSP(Z, succ, U). In particular, Section 2.3 identified some properties for U to guarantee a relatively tame behavior of CSP(Z, succ, U), while Section 2.4 characterized CSP(Z, succ, U) by gaps in U . Some questions that initially motivated our research in that direction remains open: Problem 2.40. What are the equivalent conditions for CSP(Z, succ, U) to be tractable? Are there Us such that CSP(Z, succ, U) is NP-intermediate or coNP-intermediate, assum- ing P̸=NP? In particular, is the answer to Question 2.26 yes and can ≤T there be refined to ≡p m? 35 In Section 2.5 we generalized our quasi-lowerbound results to arbitrary (Z, E, U) where the underlying digraph has nice properties. Some next steps may include: 1. Study if with reasonable properties on E, the lim−→() in the quasi-lowerbound could be removed. 2. Refine the characterization of complexity of CSP(Z, E, U) by properties on E and U . As mentioned in Section 4.1, we believe these are solid first steps towards charac- terizing the CSP of non-ω-categorical binary structures. In fact, one meaningful subclass of non-ω-categorical structures where (Z, succ, U) lives is those that are mutually alge- braic (e.g. [40],[41]) ones, which also include all A = (Z, E, U)s where the underlying A↓ has (universally) bounded degree. Hence one may ask: Problem 2.41. Let A↓ = (Z, E) be of degree d ≥ 2, i.e. degA↓(v) ≤ d for any v ∈ Z. 1. Is CSP(A↓) either in P or in NPC? If not, are there meaningful dividing lines for tractability at least? 2. Can we fully characterize the complexity of CSP(Z, E, U) (U ⊆ Z) now that we further restricted the underlying E by degree? Some facts to bear in mind: that in general it is not true that the CSP of infinite digraphs have a P-NPC dichotomy [13, 37].33 On the other hand, for any d ≥ 2 the disjoint union of all (isomorphic types of) finite undirected graph of degree ≤ 2 has the 33See also, statuses of some other open questions in [13] or here. Also [37] showed that there are coNP-intermediate ω-categorical structures. 36 https://www.lix.polytechnique.fr/~bodirsky/publications/diss-problems.html same CSP as Kd+1, by e.g. Brook’s theorem. It also has the same CSP with Mα where d− 1 = kα ∈ ( 2 α , 2 α + 1], per Proposition 4.8 from last Chapter. Some final comments on CSP of (Z, succ, U) : in fact the research here was origi- nally motivated by dichotomizing mutually algebraic structures, which can be character- ized as models of weakly minimal and trivial theories [40], and as noted above can be viewed as a generalization of a hereditary graph property of bounded degree graphs [42]. It was recently proved that mutual algebraicity affords a dividing line for speed of growth of hereditary properties [42]. Although per a construction in [13], the computational complexity of mutually algebraic structures can be all over the places, it may still be interesting to study the dividing line between intractible and tractible CSPs of mutually algebraic structures. 37 Chapter 3: Mα,TF and Shelah-Spencer Triangle-Free Random Graphs 3.1 Introduction For general introduction on Hrushovski-Fraı̈ssé classes, see Chapter 1. Here we focus on the following classes of Hrushovski-Fraı̈ssé classes of relational structures, and, as advertised, aim at axiomatizing the first order theory of their generic structures. Let L := {R1, · · · , Rs} be a finite collection of finitary, irreflexive and symmetric relational symbols: that is, respectively, we assert for each R∗ to not contain tuples with identical coordinates and we identify two tuples of solutions up to permutation of entries. For example, when s = 1 and R1 is binary, L is just the language of simple undirected graphs. Denote the arities ar(Rt) =: rt ≥ 2 for each t ∈ [1, s]. For (αt)t ∈ (0, 1]s, define the (α⃗)-predimension on each L-structure A = (A,RA 1 , · · · , RA s ): δα⃗(A) := v(A)− ∑ t∈[1,s] αt · et(A) (3.1) where, just as for graphs, v(A) = |A| the “number of vertices”, et(A) = |R A t ∼ | with ∼ identifying all permutation of entries of a hyper-edge,1 so e.g. (x, y) ∼ (y, x) are considered the same binary edge. Now define the class of hereditarily α⃗-linearly sparse 1That is, more cumbersomely, (v1, · · · , vrt) ∼ (σ(v1), · · · , σ(vrt)) for each σ ∈ Srt the symmetric group. Also by irreflexivity, no i ̸= j ∈ [1, rt] exists s.t. vi = vj . 38 L-structures2 Kα⃗ := {finite L-structures A : ∀B ⊆ind A, δα⃗(B) ≥ 0}. (3.2) Next we fix some notations for “clique” in the r-ary setting. Recall the smallest binary clique is K3 = K2+1; likewise, let (mt)t ∈ (N>0)s . For each t, denote KRt,mt := the completeRt-hypergraph on vertices {1, 2, · · · , rt+mt}. Note thatKRt,mt has ( rt+mt rt ) hyperedges — recall symmetricityof the relation. Lastly, consider the subclass of Kα⃗ that avoids the cliques (KRt,mt )t: K′α,(mt)t := Kα ∩ ⋂ t∈[1,s] (KRt,mt -free) (3.3) When the forbidden configurations (KRt,mt )t are clear from context, we shorthand K′α,(mt)t as K′α. Example 3.1. Let s := 2, R1, R2 be binary and ternary respectively, α1 = α2 = 1 2 . For {m1 := 2,m2 := 1}, KR1,m1 = KR1,2 is the (labelled) 4-clique 1 4⊠ 2 3, while KR2,1 is the “ternary 4-hyperclique”, that is, the {R2}-structure on {1, 2, 3, 4} with hyperedges ( 4 3 ) . Then Kα⃗ is the collection of L-structures whose number of vertices is at least half the total number of edges and hyperedges, while K′α⃗ is the subclass of Kα⃗ avoiding both 1 4⊠ 2 3 and the ternary 4-hyperclique. It’s a proper subclass because e.g. the δ 1 2 (H) ≥ 0 for each H ⊆1 4 ⊠ 2 3. 2Note that when α⃗, r⃗ are both diagonal (i.e. αts are identical, and so are the rts), it can be verified using computation similar to what’s done in Chapter 4 that the class Kα⃗ has a “mad” characterization, i.e. {finite L− structures A : maxB⊆A ∑ v∈B degB(v) v(B) ≥ sr α }. 39 Since the argument for the key lemmas in Section 3.2 are a bit different when the relation is binary (as opposed to tertiaries and above), we keep the discussion there for general relational structures over finite signatures. For practicality concerns it is recom- mended that one imagines (finite simple undirected) graphs as running examples. We define strong structures (≤) and generic structures as follows, similar to Chap- ter 4 Preliminaries (Section 4.2) below: G ≤ H ⇐⇒ ( G ⊆ H ∧ δα(G) ≤ δα(G ′) for all G′ : G ⊆ind G′ ⊆ind H ) , where ⊆ind denote the substructure relation. For K := Kα⃗ or K′α⃗, (K,⪯) has a generic structure Mα,∗, which is a union of {Gi}i<ω ⊆ K (therefore countably infinite) with Gi ≤ Gi+1, s.t. ∀ ( G ≤ H ∈ Kα and f : G ↪→ Mα as in- duced subgraphs where the image f(G) ≤ Mα ) , there exists an extension embedding f̃ : H ↪→ Mα,∗ s.t. f̃(H) ≤ Mα,∗. It is routine to verify that for any L, any α⃗ and any (mt)t, the classes (Kα⃗,≤) and (K′α⃗,(mt)t ,≤) both satisfiesA1 ∼ A5+ amalgamation prop- erty in [43], therefore they each have an up-to-isomorphism unique generic structure. We denote these generic structures as Mα⃗,M ′ α⃗,(mt)t respectively for Kα⃗,K′α⃗,(mt)t . As above, we denote the latter generic structure as M′ α⃗ when the forbidden configurations are clear. Laskowski showed in [1] that for α⃗ ∈ (0, 1)s s.t. the components are Q-linearly independent with 1, Th(Mα⃗), the first order theory of Mα⃗, admits a Π2 set of axiomati- zations. Such axiomatizations were later generalized to arbitrary α⃗ ∈ (0, 1)s (e.g. [44]3). In Section 3.2 we show that Th(M′ α⃗,(mt)t ) admits a similar set of axiomatizations; the 3In [44] they also have some simple axiomatization for subclasses of Kα⃗ forbidding reduced substruc- tures, which requires there to be no non-trivial substructure with smaller δα. As for example a triangle is not reduced for α ≤ 2 3 , witnessed by a singleton substructure, our approach in this section is still interesting at least for covering different ranges of αs. An alternative approach of our job here would be to verify that M′ α⃗,(mt)t as a subclass of Mα satisfies the “Approximate Extension Property” in [44]. Since the Approximate Extension Property is essentially a generalization of Proposition 4.2 of [1] to arbitrary α ∈ (0, 1), we believe the tricks used to forbid triangle in the AEP approach for arbitrary α will be similar. 40 approach is highly reminiscent of [1]’s, but involves some new technicality, especially in the binary case. It is verified that, in L = {E} the language of graphs and when α⃗ ∈ ((0, 1)∖Q)s, the aforementioned set of Π2 axiomatizations are contained in the almost sure theory of Shelah-spencer graphs. Using the completeness of Th(Mα), one may see that (e.g. [1, 22, 23]) the same set actually axiomatizes the almost sure theory of Shelah-spencer graphs. In Section 3.3 we show some efforts in making similar connections between the Π2 axioms of Th(M′ α⃗) (with L = {E} and the only banned configuration K3) and the almost sure theory of “Shelah-Spencer triangle-free graphs”. 3.2 Simple Axiomatization of Th(M′ α⃗,(mt)t ) Let the finite signatureL = (Rt)t∈[1,s], density parameters α⃗ ∈ (0, 1]s, arities (rt)t ∈ (N≥2)s, and forbidden clique sizes (mt)t ∈ (N≥1)s be arbitrary, but fixed throughout this section. With the configurations chosen, description of the forbidden cliques (KRt,mt )t are clear, so hereinafter we abbreviate (K′α,(mt)t ,M′ α⃗,(mt)t ) as (K′α⃗,M′ α⃗). Consider the following set of ∀∃ sentences in L, which we denote by S ′α⃗: 1. “Any finite substructure is a member of K′α⃗”. Remark 3.2. This is a collection of sentences parameterized by n < ω, size of vertex set of the substructures. For example if L = {E}, α = 1 2 ,m = 1 (so banning triangles), S ′α ∋ ψ3 :≡ ∀xyz (( ¬E(x, y) ∧ E(y, z) ∧ E(x, z) )∨( E(x, y) ∧ ¬E(y, z) ∧ E(x, z) ) 41 ∨ . . . . . .︸ ︷︷ ︸ description of other finitely many proper substructures of K3 on {x,y,z} ) 2. “For all A ≤ B from K′α⃗, every copy of A as induced substructure extends to a copy of B as induced substructure. Remark 3.3. This is of course parameterized by (A ≤ B) ∈ K′α⃗ 2. For example in the language of graphs banning triangles, S ′α ∋ ϕP1,P2 :≡ ∀x∃y(E(x, y)) Therefore any model M |= S ′α contains no globally isolated vertices. Note: this does not contradict the fact that P1 ↪→M. The main result of this section is that S ′α⃗ axiomatizes Th(M′ α⃗). Theorem 3.4. Th(M′ α⃗) = Cn(S ′α⃗) (Cn= set of logical consequences). Our two core technical lemmas towards Theorem 3.4 are modifications of Lemma 4.1, Proposition 4.2 of [1]. Admittedly my arguments benefited largely from Proofs in [1], but I carefully and substantially adapted the approach to avoid generation of the forbidden configurations. Before diving into that, let us state without proof the following classical results [1, 45] which we directly use in the proof: Fact 3.5 ( [1, 45]). Fix α ∈ (0, 1)∖Q. 1. There are infinitely many pairs (a, b) ∈ (N≥1)2 s.t. |a b −α| < 1 b , andGα := {b−aα : a, b ∈ N≥1} is dense in R. 42 2. For each n ∈ N≥1, let qn := the unique integer satisfying 0 < nqnα < α. Denote q+n := qn + 1. Since α < 1, qn < qm whenever n < m < ω. 3. Let p ∈ N≥1. Call p locally optimal with respect to α if |p− q+p α| < |n− q+n α| for all 1 ≤ n ≤ p. Since Gα is dense in R, infinitely many positive integers p are locally optimal with respect to α. Now fix p > 1 locally optimal. For each 1 ≤ n < p, define dn := n− qnα, then define dp := p− q+p α Note that: (a) For each n ∈ [1, p), dn ∈ (0, α); (b) dp < 0; (c) dn − dm < α whenever 1 ≤ n < m ≤ p. Note the verification of this when m = p uses the local optimality of p. Then define ⟨sn : 1 ≤ n ≤ p⟩ by s1 := q1; sn := qn− qn−1− 1 for 1 < n < p; 43 and sp := q+p − qp−1 − 1. Then (d) for n ∈ [1, p), ∑ i∈[1,n] si telescopes and equals qn − (n− 1); thus (e) ∑ i∈[1,p] si = q+p − (p− 1). By qn < n α < qn + 1 (∀n ∈ N≥1) one obtains that (f) 0 ≤ sn < 1 α for all n ∈ [1, p) and 0 ≤ sp < 1 + 1 α . Our first core lemma: any sufficiently large B ∈ K′α⃗ has a “minimal” extension D ∈ K′α⃗ that’s “infinitesimally” denser than B. Colors in the statements and proofs below highlight some differences between my approach and [1]; note that as mentioned, we have new technicality especially in the forbidden of configurations (in particular for arity 2). Lemma 3.6. Denote α := mint∈[1,s]{αt}, and r := maxr∈[1,s]{rt}. Let ∅ ̸= B ∈ K′α⃗, X := {e1, e2, · · · , ek} disjoint from B with k > r(1/α + r) a set of new, isolated vertices4 . Define B∗ := B ⊕∅ X, and fix ϵ > 0. Then there exists D ∈ K′α⃗ extending B∗ s.t. 1. −ϵ < δα⃗(D/B ∗) < 0, and 2. for any proper D′ ⊊ D, δα⃗(D′/(D′ ∩B∗)) ≥ 0. Moreover D could be chosen so that RD = RB∗ = RB for all but one R ∈ L. Remark 3.7. The D obtained here achieves “maximal density” (of hyperedges) among all its induced substructures. 4i.e., let RX = ∅ for any R ∈ L in the L-structure X on X . 44 Proof. For each t ∈ [1, s] denote αRt by αt. Fix t∗ ∈ [1, s] an index at which αt∗ = α is realized. Since B ∈ K ′α and B ̸= ∅, δ(B∗) > δ(B) > 0 and by construction B∗ ∈ K ′α.5 One may assume ϵ < min{δ(B), α}.6 Since Gα is dense in R, one may find infinitely many locally optimal integers p with −ϵ < p − q+p α < 0; we fix one such p > 2 so large that p(1/α − 1) > |B∗|. Define the sequences ⟨dn, sn : 1 ≤ n ≤ p⟩ as in Facts 3.5, with respect to α. Our bound on k = |X| and f) in Facts 3.5 ensures that |X| > r(r + 1/α) > r(1 + 1/α) > r ·max{si : 1 ≤ i ≤ p}; it also follows from e) that∑p i=1 si = q+p − (p− 1) > qp − (p− 1) ∗ > p/α− p > |B∗| > |X| = k. 7 Let C := {c1, · · · , cp} be disjoint from B∗; let I(B) := the set of isolated vertices (w.r.t. Rt∗) in B. We build a finite structure D built from the following conditions: 1. The universe of D is B∗ ∪ C; 2. B∗ ⊆ D; 3. For each relation R ̸= Rt∗ , RD = RB∗ . 4. For each 1 ≤ i ≤ p, there are exactly si subsetsQi,1, · · · , Qi,si drawn fromB∗ each of size rt∗ − 1 s.t. (a) Qi,j ∪ {ci} ∈ Rt∗ D for each i ∈ [1, p], j ∈ [1, si] and (b) in each Qi,j there is at least 1 element from X ∪ I(B). This is possible since for each i: 5Any C ⊂ B∗, C ∩ B is a substructure of B lying in K ′ α, and so is C ∩ X. Since B ∩ X = ∅, C = (C ∩B)⊕ (C ∩ X) ∈ K ′ α. 6Otherwise, take 0 < ϵ′ < min{δ(B), α} and prove the two inequalities for ϵ′; note that in this case 0 < ϵ′ < ϵ so the inequalities, in particular (1), still hold for ϵ. 7(*): we have that qp > p/α− 1 by the definition of qp. Therefore qp − (p− 1) > p/α− p, as desired. 45 (a) if rt∗ ≥ 3: i. If I(B) = B then B∗ = X ∪ B = X ∪ I(B). Note that |X ∪ I(B)| > |X| > rt∗ ≥ 3 so number of choices for Qi,js are (|X∪I(B)| rt∗−1 ) ≥ |X| > si meaning we have sufficiently many choices. ii. Otherwise |B ∖ I(B)| ≥ 2 (note that B ∖ I(B) is the set of non-isolated vertices). So at least one has (|B∖I(B)| 1 ) · (|X∪I(B)| rt∗−2 ) ≥ |X| > si choices for the Qi,js. (b) if rt∗ = 2, all Qi,js are singletons and they all come from X ∪ I(B). So number of choices simply amounts to (|X∪I(B)| 1 ) ≥ |X| > si. In fact we shall soon give a canonical way of choosing these Qi,js later for each scenario, which we adopt as our algorithm creating Qi,js. Also, though seemingly obvious, we shall argue later that no KRt∗ ,mt∗ is created here. 5. Each b ∈ X ∪ I(B) is in at least one of the Qi,js: this is possible since: (a) If rt∗ ≥ 3: i. If I(B) = B, recall that X ∪ I(B) = B∗. A canonical way to do Step 4 is simply to give a listing {η1, η2, · · · , η|B∗|} of B∗, and walk through the list setting {η1, · · · , ηrt∗−1} =: Q1,1, {ηrt∗ , · · · , η2rt∗−2} =: Q1,2, etc, only coming back to the beginning and keeping walking when necessary. Since total size of the Qi,js are ∑p i=1 si · (rt∗ − 1) > ∑p i=1 si > |B∗|, it is guaranteed that the list will eventually be exhausted. For each i∗∗ ∈ [1, q], this process does not generate repeated Qi∗∗,js, as 46 si∗∗(rt∗ − 1) < maxi(si) · r < k < |B∗|.8 ii. If I(B) ⊊ B then similarly, in Step 4 one may list {η1, · · · , η|X∪I(B)|}, and let {η1, · · · , ηrt∗−2} ⊂ Q1,1, {ηrt∗−1, · · · , η2rt∗−4} ⊂ Q1,2, etc, with the remaining elements drawn from B ∖ I(B) arbitrarily. We still have∑p i=1 si · (rt∗ − 2) ≥ ∑p i=1 si > |B∗| > |X ∪ I(B)| and si∗∗(rt∗ − 2) < maxi(si)·r < k ≤ |X∪I(B)|, so exhaustion is guaranteed and repetition within the same i∗∗ is avoided. (b) If rt∗ = 2: in Step 4 list {η1, · · · , η|X∪I(B)|} and choose Qi,js as above. Now we have total size of all Qi,js: ∑ i≤p si > |B∗| ≥ |X ∪ I(B)| and fixing any i∗∗ ∈ [1, p], total size of Qi∗∗,js: si∗∗ · 1 < maxi(si) · r < k ≤ |X ∪ I(B)|, yielding again the exhaustion and non-repetition. 6. there is exactly one subset Zi ⊂ B∗ of size r∗ − 2 such that Zi ∪ {ci, ci+1} ∈ Rt∗ D for each 1 ≤ i < p,9 which does not create KRt∗ ,mt∗ either (See later argument) and 7. Rt∗ D contains no other subsets of D. We argue that no forbidden structure is created in D. Since the only modified relation is Rt∗ , it suffices to show that no KRt∗ ,mt∗ is created; by construction a KRt∗ ,mt∗ must involve either 1 or 2 vertices from C, so it suffices to show that neither Step 4 nor Step 6 creates any KRt∗ ,mt∗ : 1. If someKRt∗ ,mt∗ were created in clause (4), there must exist i ∈ [1, p], x1, · · · , xrt∗+mt∗−1 ∈⋃ j∈[1,si]Qi,j where: 8So the exhaustion will happen at some i∗∗ > 1. 9Note that in arity rt∗ = 2 this simply means {ci, ci+1} ∈ Rt∗ D for each i ∈ [1, p− 1]. 47 (a) for each size rt∗ subset S ⊂ {x1, xrt∗+mt∗−1}, S ∈ Rt∗ D ; and (b) for each size rt∗ − 1 subset S ′ ⊂ {x1, xrt∗+mt∗−1},{ci} ∪ S ′ ∈ Rt∗ D . However, let ⋃ j≤n Sj be a subset cover of {x1, · · · , xrt∗+mt∗−1} with each |Sj| = rt∗ , then S1, · · · , Sn ∈ Rt∗ D∧⋃ j Sj ⊂ ⋃ j∈[1,si]Qi,j ⊂ B∗ implies each Sj ∈ Rt∗ D|B∗ = Rt∗ B∗ = Rt∗ B∖I(B) , which gives ⋃ j Sj = {x1, · · · , xrt∗+mt∗−1} ⊂ B∖ I(B) . On the other hand by Clauses 4b,6,7 , in D no ci is Rt∗-related with any size-(rt∗ − 1) subset purely drawn from B ∖ I(B), contradicting Clause 1b. 2. For Clause (6) to create anKRt∗ ,mt∗ one would need some i ∈ [1, p−1], x1, · · · , xrt∗+mt∗−2 ∈⋃ j Zj ⊂ B∗ s.t. (a) S ∈ Rt∗ D for each S ⊂ {x1, · · · , xrt∗+mt∗−2} with size rt∗; (b) {ci} ∪ S ′, {ci+1} ∪ S ′ ∈ Rt∗ D for each S ′ ⊂ {x1, · · · , xrt∗+mt∗−2} with size rt∗ − 1; (c) {ci, ci+1} ∪ S ′′∈ Rt∗ D for each S ′′ ⊂ {x1, · · · , xrt∗+mt∗−2} with size rt∗ − 2; (⋆⋆⋆) Note that since rt∗ +mt∗ ≥ 3, Clause (2c) (Clause (⋆⋆⋆)) is not a trivial condition. We split the cases due to rt∗: (a) If rt∗ ≥ 3: Observe rt∗ +mt∗ − 2 ≥ rt∗ − 1 > rt∗ − 2 ≥ 1 so ( rt+mt−2 rt∗−2 ) > 1, meaning Clause (2c) above would describe more than 1 elements in Rt∗ D , yet we have exactly one relation {ci, ci+1, · · ·︸︷︷︸ =Zi⊂B∗ } ∈ Rt∗ D , contradiction. (b) If rt∗ = 2, Clause (2c) above says {ci, ci+1} ∈ Rt∗ D . Since a clique containing ci, ci+1 must in particular contain a triangle ci ∗ ▲ci+1 , this says there exists 48 some b ∈ X ∪ I(B) 10 s.t. ci b ▲ci+1 ↪→ Rt∗ D ; by construction, we have b ∈ Qi,j∩Qi+1,j′ for some j ∈ [1, si], j ′ ∈ [1, si+1]. This is impossible, because the total size of Qi,∗, Qi+1,∗ is si+si+1 ≤ 2 ·maxi si < k < |X ∪ I(B)|; pursuant to our algorithm creating Qi,js, this means we cannot exhaust X ∪ I(B) just by making Qi,∗, Qi+1,∗s, so they don’t touch each other, i.e. Qi,j ∩Qi+1,k = ∅ for any j ∈ [1, si], k ∈ [1, si+1]. We have established that KRt∗ ,mt∗ ̸↪→ D; since no other relations are changed, this means once we have D ∈ Kα we would have D ∈ K ′α. Moreover, observe that once we establish the inequalities in Lemma 3.6, by δ(D) = δ(D/B∗)+δ(B∗) >︸︷︷︸ Inequality (1) −ϵ+ϵ = 0 and δ(D′) = δ(D′/(D′∩B∗))+δ(D′∩B∗) ≥︸︷︷︸ Inequality (2) 0+δ(D′ ∩B∗︸ ︷︷ ︸ ⊆B∗∈K′ α ) ≥ 0 we would have D ∈ Kα. Thus the only remaining job is to verify the two inequalities in the statement of Lemma 3.6. First, D − B∗ has p elements; Clause (4) contributes to ∑p i=1 si more subsets in Rt∗ D while Clause (6) adds p−1 more. Then δ(D/B∗) = ( p−α( ∑p i=1 si+(p−1)) ) =( p − αq+p ) ∈ (−ϵ, 0) by our choice of locally optimal integer p at the beginning. The first inequality is proved. To show the second inequality, let us begin with the proper substructures fully con- taining B∗. For each 1 ≤ n < p, denote Dn ⊆ D with universe B∗ ∪ {c1, · · · , cn} and for 1 ≤ n < m ≤ p denote Dn,m ⊆ D with universe B∗ ∪ {cn+1, · · · , cm}. We have δ(Dn/B ∗) = n− α( n∑ i=1 si + (n− 1)) = n− qnα = dn > 0 (3.4) 10note that in arity 2 we only drew elements from X ∪ I(B) in Step 4 and drew no element from B∗ in Step 6; that is Zis are empty. 49 and δ(Dn,m/B ∗) = m− n− α((m− n− 1)︸ ︷︷ ︸ Clause 6 + n∑ i=m+1 si︸ ︷︷ ︸ Clause 4 ) = m− α( m∑ i=1 si +m− 1)− (n− α( n∑ i=1 si + n− 1)) + α =  m− qmα− (n− qnα) + α, if m ̸= p p− q+p α− (n− qnα) + α , if m = p = dm − dn + α > 0 since for any ∅ ≠ A ⊊ C letting DA := the substructure of D with the universe B∗ ∪ A, DA is a free join over B∗ of substructures of the form Dn and Dn,ms11, by closure of K ′α under free join one has δ(DA/B ∗) ≥ 0. Since δ(B∗/B∗) = 0, we conclude that for any proper B∗ ⊆ D′ ⊊ D, the second inequality holds. For general D′ ⊊ D, denote by B∗0,D ∗ resp. the substructure of D with universe D′ ∩ B∗, D′ ∪ B∗. Then D∗ is a join of D′ and B∗ over B∗0, and it suffices to show δ(D′/B∗0) ≥ 0. 1. If D∗ ̸= D, then from the predimension lemma (Lemma 2.3) in [1], δ(D∗/B∗) ≤ δ(D′/B∗0). Note that D∗ is a proper substructure of D containing B∗, so by the above δ(D∗/B∗) ≥ 0. We obtain δ(D′/B∗0) = δ(D′/(D′∩B∗)) ≥ δ(D∗/B∗) ≥ 0 as desired. 2. If D∗ = D then B∗0 ̸= B∗ since D′ is proper. The universe D′ must contain all of 11e.g. for p = 31, A = {ci ∈ C : i = 2g for some g}, then DA = ⊕ B∗{D2,D3,4,D7,8,D15,16}. Also there is no partition of D into the free join of any Dn,Dn′,m′s over B∗ : if n′ ≥ n, we miss the relation (cn, cn+1, · · · ), while if n′ < n, Dn ∩Dn′,m′ ̸= B∗. 50 C (for B∗ ∩ C = ∅) and avoid some b ∈ B∗ ∖B∗0; (a) if b ∈ I(B) ∪ X then by Clause (5), (b, ci, · · · ) ∈ Rt∗ D for some i; but then Rt∗ D∗ = Rt∗ D ̸= Rt∗ B∗ 0 ∪Rt∗ D′ , as both B∗0,D ′ avoids b; (b) Otherwise b ∈ B ∖ I(B), then some (b, · · · ) ∈ Rt∗ B ⊆ Rt∗ D but B∗0,D ′ avoids b so again Rt∗ D∗ = Rt∗ D ̸= Rt∗ B∗ 0 ∪Rt∗ D′ . By lemma 2.3 [1], δ(D′/B∗0) ≥ δ(D∗/B∗)+α = δ(D/B∗)+α >︸︷︷︸ first inequality −ϵ+α > 0, as desired. Another core result: For any strong pair (A ≤ B) ∈ K′α⃗ 2 and a finite collection of forbidden structures Φ ⊂fin K′α⃗, there exists an extension K′α ∋ D ⊇ B that strongly extends A, is “infinitesimally sparser” than A, and avoids all forbidden structures in Φ. Lemma 3.8. Let A ≤ B ∈ K′α⃗, µ > 0, and a finite set Φ ⊂ K ′α⃗ where B ⊂ C yet B ̸≤ C for each C ∈ Φ. Then there exists K′α⃗ ∋ D∗ ⊇ B, satisfying: 1. δ(D∗/A) < µ; 2. A ≤ D∗; and 3. no C ∈ Φ isomorphically embeds into D∗ over B (note: not “over B∗”, which would be weaker). Proof. Note that if B = ∅ then A ≤ B implies A = ∅ and Φ has to be empty as we require B ̸≤ C for any C ∈ Φ. The conclusion then follows by taking any D∗ with δ(D∗) < µ, such as B itself. Also when A = B, taking D∗ := B does the job. So we 51 assume B ̸= ∅, A ̸= B (so by the assumption that αRs are irrational, δ(B/A) > 0). Let X = {e1, · · · , ek} disjoint from B with k > r(1/α + r), RX = ∅ for all R ∈ L and B∗ := B⊕X. Note that A ≤ B =⇒ A ≤ B∗ by construction. It is also without loss of generality to assume δ(C/B) < 0 for all C ∈ Φ, as for the cases where δ(B/C) ≥ 0 one may replace C with a minimal C′ s.t. B ⊂ C′ ⊂ C and δ(C′) < δ(B).12 Now fix Z ∋ s′ > maxC∈Φ{|C|} and then choose ϵ > 0 so small that 1. ϵ < min{µ, δ(B/A), α}: note that this guarantees ϵ < δ(B∗/A) as well; and 2. s′ϵ < −δ(C/B) ≤ −δ(C/B∗ ∩ C) (recall δ(C ∩ B∗) ≥ δ(C ∩ B) = δ(B) by construction of B∗ so indeed δ(C/(C ∩B∗)) ≤ δ(C/B) < 0. We first work with B∗ instead of B to find D∗ s.t. δ(D∗/A) < µ and A ≤ D∗. Use Lemma (3.6) to find D ∈ K ′α for (B∗, ϵ): note that D is also an extension of B. Let γ = −δ(D/B∗) so 0 < γ < ϵ < δ(B∗/A) by Inequality (1) in Lemma (3.6). Choose an integer h s.t. hγ ≤ δ(B∗/A) ≤ (h + 1)γ, which exists since 1 · γ < δ(B∗/A) and hγ h→∞→ ∞. Let {Di : i < h} be h copies of D with Di ∩ Dj = B∗ for all i ̸= j and D∗ := ⊕ i