MASARYK
UNIVERSITY
Quasirandomness in
combinatorics
F i l i p K u č e r ák
Master's Thesis
Faculty of Informatics
Brno, Spring 2025
Supervisor: prof. RNDr. Daniel Kráľ, Ph.D., DSc.
Declaration
Hereby I declare that this thesis is my original authorial work, which I have
worked out on my own. A l l sources, references, and literature used or excerpted
during elaboration of this work are properly cited and listed in complete reference
to the due source.
During the preparation of this thesis, I used the following A I tools: Grammarly
for grammar check and C h a t G P T for short snippets of code. I declare
that I used these tools in accordance with the principles of academic integrity.
I checked the content and take full responsibility for it.
Filip Kucerak
1
Acknowledgments
I would lik e to thank my supervisor, D a n Kráľ, for all of the invaluable advice
and opportunities I was given throughout my studies. I would also lik e to thank
my partner and family for their support during my time at Brno. Finally, I
would lik e to thank my colleagues from the faculty for our many (un)productive
conversations.
2
Abstract
A n object is said to be quasirandom if it resembles a truly random object from
the same structure class. In this thesis, we focus on determining the boundary
of sufficient conditions for the property in the combinatorial setting of permutations.
It is known that a permutation is quasirandom if and only if the density
of all four-element permutations does not significantly deviate from their expected
density of 1/24. Subsets of permutations that can be similarly used
to capture the quasirandomness are called quasirandom-forcing. Two natural
question arise: determining the size of the smallest such set and classifying
the inclusion-wise minimal forcing sets. The aim of the thesis is to contribute
towards these questions.
It was known that collections of at most three permutations and collections
of four permutations of size four are not quasirandom-forcing. There also exists
a quasirandom-forcing set of size six; this is conjectured to be the best possible
in terms of the size of a quasirandom-forcing set. We employ analytical methods
to show that there is no quasirandom-forcing set of four permutations of size at
most five.
Keywords
permutations, permutation limits, quasirandomness, quasirandom-forcing
Contents
1 Introduction 7
2 Permutation Limits 11
3 First-order M e t h o d 15
3.1 Gradient Polynomial 16
3.2 Subsampling and Fuzzy Covers 18
4 Second-order M e t h o d 24
4.1 Walking i n the Zero Set 24
4.2 Example 30
5 Profiles of Forcing Sets 34
5.1 Homogeneous Sets 39
5.2 Sets with One Exceptional Permutation 41
5.3 Matched Profile 42
5.4 A n d the Rest 44
6 Conclusion 45
Bibliography 47
Appendix A Elements of multilinear calculus 49
Appendix B Certificates for Four-Value L e m m a 51
Appendix C Implementation of the First-order M e t h o d 53
Appendix D Second-order Certificates 54
4
Notation and Conventions
We use N to denote non-negative integers including zero. We use [n] to denote
the set of first n positive integers and use [n]o to denote the first n + 1 nonnegative
integers. We use C to denote not-necessarily proper subsets, i.e., we
would use C to denote proper subset had there been a chance. A s such, we have
N c N . Given a set A, we adopt the notation J^t f(a
) f ° r s u m s a n
d u s e
this
notation whenever possible, e.g., for sums, products, minimums, maximums,
and probabilities. We use the notation {xi)\ for tuple (possibly infinite) of
values indexed by set / and use {xi}{ for set whose elements are indexed by
/ . Given functions / : A —> B and g : B —> C, we use gf to always mean
composition g o / : A —> C. We use notation (x H> f(x)) to denote function
literals, i.e., symbol (x i—> x2
) is the same to the set of functions K —> K as
the symbol 5 is to the set of natural numbers N . Given a proposition V, we
write 1(V) for one if V is true and zero if V is false, i.e., 1 serves as a indicator
function. Given a set A and natural number k £ N , we use A^ for set of all kelement
subsets of A and use binomial coefficient (?) to denote the cardinality of
[n](fc
'; note that if n < k, we have (£) = 0 and (Q) = 1. Given a map / : A —» B,
we define the kernel of / to be the partition of domain A into classes which map
to the same value under / .
Given vector spaces U and V, we use C(U, V) to denote the space of linear
maps between U and V. Given n, m £ N , we denote by M.mXn
the space of real
matrices with m rows and n columns and use standard notation ( M ) j j to denote
the element of the matrix i n i-th row and j-th column and so ( M ) j j = ej Mej,
where we use ej for the i-th standard basis vector. Given n, m £ N , we denote
by W1
^™ the space of linear maps £(]R™,]Rm
) and identify this set with ] R m x n
under the representation i n the canonical basis. Whenever we discuss a matrix
which is associated to a linear map, we use K 5 > _
notation and use ] R _ X _
otherwise, e.g., when discussing representations of bilinear forms. Given a set
A, we use M A to mean vector space of formal linear combinations of finitely
many elements from A with real coefficients, i.e., the free real vector space on
A. Given a subset U C V of vectors, we use MU to denote the subspace spanned
by the vectors from U and use M.u as a shorthand for ]R{u}.
Let us for set A denote by Aut(A) the set of functions of the form A —> A
that are bijections. Let S„ denote the group of permutations on n elements,
i.e., the set Aut([n]) with multiplication defined by function composition. Let
5
CONTENTS 6
123 132 213 231 312 321
Figure 1: Elements of symmetric group S3 and their cover matrices.
§ = U^S„ be the set of all permutations without further structure and define
\a\ to be the natural number n such that a is an element of S„. Throughout
the text, we represent permutation a £ Sfc by a tuple (cr(l), <r(2), ...,a(k)) and
when k is small, we omit both the parentheses and commas, e.g., we write 132
for permutation (1,3,2). To permutation a € we associate linear bijection
Aa £ Rk
^k
with Aaei = ea(i) whose matrix we call the cover matrix of a. It
is easy to see that mapping sending permutation to its cover matrix is a group
homomorphism Sfc —> SL(fc, M), where SL(fc, K ) denotes the special linear group
of matrices of the form M f c x f c
with determinant one. Note that there is another
standard representation Baei = ea-i^ = Aa-iei = A^a which we do not use
here.
Chapter 1
Introduction
A n object of some structure class is said to be quasirandom if it resembles a
random object of the same class. The theory was classicaly built i n 1980s i n the
setting of graphs by Rodl [22], Thomason [26] and Chung, Graham and Wilson
[4] although the intuitive motive as stated is quite general and has indeed been
studied i n variety of combinatiorial settings, e.g., i n the settings of digraphs,
tournaments [3, 12, 1, 8], Latin squares [6], permutations [18, 2, 19, 9, 17], i n
algebraic settings, e.g., for groups [11], and even i n the more general model
theoretic settings [8].
Before investigating permutations which are the main subject of the thesis,
let us briefly discuss quasirandomness i n the setting of graphs. To this end, we
choose Erdos-Reryi graph G(n,p) to be our random graph model. Graph G ~
G(n,p) is a graph on vertex set [n], where we declare vertex pair ij £ [n]^2
' to
be an edge independently with probability p. We say that G(n,p) has property
V if the probability that a graph sampled according to G(n,p) has the property
V with high probability, formally
lim F%M
(G eV) = l.
n—»oo
A n easy argument using Chernoff bounds can show that G{n, p) has p + o(l)
proportion of edges and one can—using slightly more nuanced concentraction
results—generalize the argument to all subobjects. Formally, let us denote by
t{H, G) for graphs H and G the probability that if we sample random set injection
ip : V(H) —> V(G), the map ip is a graph homomorphism, i.e., we have that
if uv e V(H)W
is an edge of H, then ip(u)ip(v) is an edge i n G. Using linearity,
we can observe that given n > \H\, the expected value of the quantity t(H, G)
for G ~ G(n,p) is tc(n,p) : =
p^E
^H
^ and moreover, given graph H we have
that for random graph sequence G, := ( G „ ) ^ with Gn ~ G(n,p) the density
sequence {t(H, G „ ) ) „ converges to this expectation almost surely. This motivates
the following definition. We call graph sequence G, = ( G „ ) ^ convergent if
sup^1
| G „ | = oo and the limit t(H, G . ) := l i n v ^ ^ t(H, Gn) exists, and call such
sequence quasirandom if t(H,G,) = t&(n,p){H) for every graph H; notice that
7
CHAPTER 1. INTRODUCTION 8
a random sequence is quasirandom almost surely. A similar definition can be
used for any class of structures with good notion of a random model—playing
the role of G(n,p)—and good notion of an subobject or structure preserving
mapping—playing the role of subgraphs and graph homomorphisms 1
.
The definition as stated is a priori infinitary in the sense that for sequence
G . , one needs to check behaviour of infititely many density sequences {t(H, G n ) ) „
one for each graph H. A n important question in the broad area of quasirandomness
is determining equivalent, necessary, and sufficient conditions for structure
sequence to be quasirandom. Chung, Graham and Wilson, building on an earler
work of Rodl [22] and Thomason [26], give a number of equivalent conditions of
which we present only few.
Theorem 1 (Chung-Graham-Wilson [4]). Given a growing graph sequence G . ,
the following are equivalent
1. the sequence is p-quasirandom,
2. for X C V(Gn) we have e(X) = p | X | ( 2
) + o(n2
),
3. t{K2, Gn) = p and t ( C 4 ) G . ) = p\
4. if A i > ... > A„ are the eigenvalues of the adjacency matrix of G , then
Ai = pn + o(n) and max" |Aj| = o(n).
We focus on condition 3 that is quite surprising when seen for the first time.
It states that not only do we need to check only finitely many density sequences,
if we know that the edge density in G . converges to p, we only need to check a
single graph, the 4-cycle. We call a set of graphs S quasirandom-forcing if for
convergent sequence G . we have that if there exists edge density p £ [0,1] and for
every H in set S it holds that t(H, G . ) = t&(n,p){H), then G . is p-quasirandom.
A n important area of study i n quasirandom graph theory is to determine which
sets S are quasirandom-forcing. Chung, Graham and Wilson have shown that
one can replace G4 by any even cycle and any complete bipartite graph _K~2,t for
t > 2. A result of Skokan and T h o m a [25] showed that one can genarize this to
Ka£, i.e., that {K2,Ka^} is forcing and the Forcing Conjecture of Conlon, Fox
and Sudakov [5] states that the set {K2,H} is quasirandom forcing if and only
if H is bipartite and contains a cycle.
Similar results can be found in the study of other structures. For tournaments
(orientations of complete graphs) it is known that singleton set {H} is
quasirandom-forcing if and only if it is a transitive tournament on at least four
vertices or an exceptional tournament on five vertices [8, 1, 8, 13]; for Latin
squares it is known that patterns of size 2 x 3 are quasirandom forcing [6].
In this thesis, we focus on the study of forcing quasirandomness in the setting
of permutations. We start by formally defining the required notions and
preliminary results, starting with defining the notion of a subobject.
1
A reader may ask if the choice of subgraphs as our subobjects instead of induced subgraphs
and counting labeled occurrences instead of unlabeled is arbitrary, i.e., it has no influence on
which convergent sequences are quasirandom, or the choice is deliberate. The theory tells us
that the former is the case.
CHAPTER 1. INTRODUCTION
P = { 1 , 3 , 4 } P = {2, 3,4} P = {2, 3, 5} P = {2,4, 5}
Figure 1.1: A l l four sets P C [6] for which (351246)|P = 312.
Given a permutation IT £ S„ and a fc­element subset P C [n], we define
n\p £ Sfc to be the unique permutation such that for i,j £ [k] with i < j , we
have that 7r(Pj) < 7r(Pj) if and only if ir\p(i) < 7r|p(j), where P i < ... < Pfc are
ordered elements of P . A s an example, given permutation IT = (3,1,4, 2, 5) £ § 5 ,
and set P = {1, 3,4} we have ir\p = (2, 3,1). Given permutations a £ and
7T e §„ we use d(a, IT) for density of a in 7r, which we define to be the probability
that for uniformly chosen P £ [n]^ it holds that n\p = a. We denote by dp(a)
the expected density of a in permutation uniformly chosen from S„ for n > \a\:
note that this is well­defined as the expectation is the same for all n > \a\,
namely it is l/|«r|!. Given a permutation sequence IT, = (7r„)^, we say that
the sequence is convergent if sup„|7r„| = 00 and d(a, 7r.) = l i n v ^ o o d(a, 7r„)
converges for all a e S and say that convergent sequence is quasirandom if
d(a, 7T.) = dp(cr) for all a £ S. We denote the space of convergent permutation
sequences by iS. Given a map F : S —> Rs
for some set S, we say that the
map is quasirandom­forcing (from now on forcing) if for convergent permutation
sequence IT, £ <S, we have that if F (IT,) = 0 holds then IT is quasirandom, i.e.,
the zero set of F contains only quasirandom sequences.
Given a set of permutations S C S a natural map of the sort is the map
Gs • S —> Rs
which sends n, to (d(a, n,) — dp(a))aes which we call the density
discrepancy function. We say that the set of permutations is quasirandomforcing
(from now on also forcing) if the associated map Gs is. A result of Kráľ
and Pikhurko i n [18] states that S4 is forcing, while the sets S; are known not
to be forcing for I < 4 [7, 18]; this means that—similarly as for graphs, tournaments
and Latin squares —quasirandomness i n permutations is also captured by
only finitely many pattern densities. A natural goal is to classify inclusion­wise
minimal forcing sets with first step being understanding the forcing set with
minimal size which we denote us. F or the latter, only bounds are known. F or
upper bounds, the aforementioned result of Kráľ and Pikhurko i n [18] shows
that u) < 24 which was later improved first by Chan et al. in [2] to us < 8 and
later by Crudele et al. in [9] to ui < 6. To discuss these works we first need
some definitions.
We define the linear space of superpermutations2
MS to be the free vector
2
Here, we take inspiration from terminology of quantum graphs taken from [20] by adapting
CHAPTER 1. INTRODUCTION 10
space generated by the set S, i.e., elements of MS are formal linear combinations
of finitely many permutations. We extend definitions of d(—,7r) and dp(—)
linearly to MS so that for v = J2a
a
o-o~ we have d(v, IT) = J2aa
a-d(a, IT) and
dp(v) = Yla a
rrdp(a). In [2] and [9], authors study forcing of a map Gv : S —> R
associated with v £ MS which sends IT, to d{v, -K,) — dp{v), that is, they consider
discrepancy of the mixed densities. Let us define supp v C S to be the set of
those permutations a which have non-zero coefficients aa i n v and let us say
that v is of order k if the largest permutation i n v is of order k. Notice that if Gv
is forcing and S = supp then so is G 5 : let a £ M s
be the real vector so that
v = J2a aaa, then Gv = aT
Gs meaning if GS(TT,) = 0 then Gu(ir.) = 0 and
7T. is quasirandom by forcing of Gv. The main result of [2] is full description of
quasirandom forcing superpermutations v £ MS4, producing v with |supp v\ = 8
in the process, thus showing us < 8. In [9], authors determine superpermutation
v £ MS4 0 MS3 with support of size 6 which is forcing, giving us the currently
best-known upper bound ui < 6 that is believed to be tight. Moreover, [9] shows
that if the coefficients va of v are positive and v has support of size at most 5,
then Gv is not forcing. We discuss the result and tools required i n Chapter 3.
For lower bound, the best known bound is us > 3 by Kurecka shown i n [19].
We discuss the result and tools used i n Chapter 3. The main aim of this thesis
is to contribute to establishing bound us > 4. In this direction, result of [17]
shows that given a 4-element set of permutations 5 C § 4 , the set S cannot be
forcing; we review the tools used i n Chapter 4. O u r main result is an extension
of this result to sets of four small permutations.
Theorem 2. Let S be a set of four permutations of order at most five, then S
is not forcing.
We briefly review the structure of the thesis. In Chapter 2, we survey results
regarding permutation limits which give us a workable description of function
Gs and serve as a main source of convergent permutation sequences i n this
thesis. In Chapter 3, we survey gradient-based tools from [19] and their consequences
found i n [9]. In Chapter 4, we discuss Hessian-based methods found
in [17] and describe a non-forcing certificate which we obtain computationally.
Finally, i n Chapter 5, we use all the aforementioned methods and results to
prove the main claim of this thesis. T h e main body of the text is followed by a
series of appendices, the most important of which is Appendix D that describes
our computationally found certificates that play a crucial role i n various proofs.
the term superposition. There is a different notion of a superpermutation, namely a string
of n symbols which contains every permutation on n elements as a substring. Although the
clash in names is somewhat unfortunate, I believe it should cause no confusion.
Chapter 2
Permutation Limits
In recent years, study of large combinatorial structures and study of growing
combinatorial sequences—e.g., in the study of random graphs, quasirandom
graphs and extremal combinatorics—gave rise to a theory of combinatorial limits.
The area asks to, for a sequence of combinatorial objects, to create a single
object capturing the properties of the elements i n the sequence. The exact
properties one has in mind heavily depend on the intended use. One viable
approach is a very general "syntactic" approach which views combinatorial objects
as models of first-order theories and leverages tools coming from the area
of model theory such as ultralimit constructions to create "logical" limits—limit
objects which satisfy the same first-order formulae as a "large" portion of elements
of the sequence—and even "density" limits—limit objects which capture
behaviour of the subobject density functionals—using the flag algebra approach
originally defined by Razborov [21] which has been an important tool in the
area of extremal combinatorics.
The aim of this section is to review one such density limit of convergent
permutations sequences (for definition of convergent sequence see introduction),
i.e., for convergent sequence IT, we aim to define an object ji together with a
functional d(—, ji) : MS —> K with the property that d(v, n) = d(v, 7r.) for every
superpermutation v G MS. A simple yet illustrative way is to define the sequence
itself to be the limit. This approach represents the most skeletal approach to
limit building. The approach of flag-algebras—slightly more concrete—is to
proclaim an appropriately chosen subset of functionals ip : MS —> M to be the
limit. Even though flag algebras are both crucial, fascinating and main tool
used in the proof u> < 6, its survey is outside the scope of this thesis.
In this thesis, we instead focus on a concrete analytical limit, namely measure
theoretic object studied in [16, 15] 1
. We define permuton to be a Borel measure
H on [0, l ] 2
with uniform marginals, i.e., we require n([a, b] x [0,1]) = ^j([0, 1] x
[a, b\) = b — a for all 0 < a < b < 1. To define subpermutation density d(—, ji) :
l r
The analytical object studied in the cited works slightly differs from the object presented
but Lemma 2.2 and Definition 2.3 in the former citation can be used to translate one to the
other.
11
CHAPTER 2. PERMUTATION LIMITS 12
MS —> M, we first need to establish some definitions. Given k distinct members
x = of some linear order L (reader should think [n] for some n £ N),
we say that collection x induces permutation IT if x^-i^ < x^-i^) < ••• <
XTT-1
(k) (note that for any collection x there is a unique permutation IT with this
property). A s an example, vector (0.5,3.14,10,2) £ M4
induces permutation
7T = (1,3,4,2) £ S 3 as TT"1
= (1,4,2,3) and 0.5 < 2 < 3.14 < 10. Given
two collections x1
and x2
of fc-distinct elements in some linear order L, we
say that they induce permutation IT if x1
induces TTI, X2
induces 7T2, and IT =
7T27T]"1
. A s an example, take sequence ((1, 5), (3, 2), (4,4), (2,10)) £ Z 2 x 4
which
induces (3,4,1, 2) £ S3; projection of the sequence to the first coordinate induces
permutation (1, 3,4, 2) £ S3, projection of the sequence to the second coordinate
induces permutation (3,1,2,4) £ S 3 and (3,1, 2,4)(1, 3,4, 2 ) " 1
= (3,4,1,2).
We define density of IT in permuton \i to be the probability d(7T, \J) that k
independently /j-sampled points (xi,t/i)^ induce permutation n. Although the
notion of a permutation induced by a set of points is only meaningful as long
as all coordinates are distinct, due to the uniform marginals condition, the
probability that we sample distinct coordinates is one.
A n important class of permutons are step permutons n[A] associated to
doubly-stochastic matrix A £ M.nXn
which we define for any Borel X C [0, l ] 2
by
ß[A](X) = n'£AiijX(Xn(Pnxli))= / n ^ ^ , , l 7 i x 4
„• a -J x.y • •
(x,y)d\,
where A is the Lebesgue measure and Pn = [{i—l)/n, i/n] C [0,1]. Intuitively,
permuton fx corresponds to graphical representation of the matrix A in the unit
square, each cell of the matrix viewed as a constant square with side of length
1/n.
The following lemma gives us a simple formula to compute permutation
densities in step permutons. Given two posets A and B, let Ord(^4, B) be
the set of order preserving mappings from A to B, i.e., mappings / such that
a <A a' = > /(a) <B / ( « ' ) for all a, a' £ A.
Lemma 3 ([2] L e m m a 10). Given permutation a £ Sfc and permuton fi[A]
associated with A £ M™x
™, it holds that
n k
/,f l =oi(k[»]) I F IZ-HOIIs-HOI
The main result of [16] and [15] shows that permutons are a "good" definition
of a limit i n the sense that for every convergent sequence of permutations 7T.
there is a unique permuton \i associated to 7r. such that d(—,7r.) = d(—,n)
(completeness) and moreover that for every permuton fj, there is a convergent
sequence 7r. such that the permuton associated to IT, is ji almost everywhere
CHAPTER 2. PERMUTATION LIMITS 13
(analogue to permutations being "dense" in the space of permutons2
).
Let us now relate the study of quasirandom sequences with the area of permutation
limits. First, by the completeness, we have that each quasirandom
sequence corresponds to a single permuton, namely the uniform permuton p defined
to be the Lebesgue measure on the unit square; p as defined is a permuton
and moreover, the probability that k points (xi,yt)^ induce any permutation
a £ Sfc is exactly dp(a) = 1/kl. Given a set of permutations S C S, define
Gs : V —> M s
to be a mapping which to each permuton p £ V and a £ S
assigns the density d(a, p) — d(a, p). A s the permuton associated to any quasirandom
sequence 7r. is p and for every permuton there is a convergent sequence
to which it is associated, to ask whether set S is forcing is to ask, whether there
is non-uniform p such that Gs(p) = 0; the remaining of the presented work
aims to produce for sets S such permuton p. To do this, we show that the
discussed sets S cannot force p even on subset V' C V, i.e., even restrictions of
Gs\v contain non-uniform zeros; in such cases we say that S is not P'-forcing.
A s Gs is forcing if and only if Gs is forcing, and there is a clear correspondence
between sets iS and V, we abuse notation and denote both functions by
G s .
The theory of permutation limits plays an important role in the proof of the
fact that the set S4 is forcing.
Theorem 4 ([18] Theorem 3). The set S4 is forcing.
A result of [10] generalizes the above to show that permutons which are
structurally simple can be also forced by a finite set of permutations, i.e., if
p = ctiAi for some non-negative reals a, and non-trivial polygons Ai, then
there exists a set S such that the zero set of the map Hs(p') = (d(ir,p') —
d(n, p))% : V —> K contains only p.
We conclude this section by reviewing a standard parametrization of a neighbourhood
of p with hope to finding the desired non-uniform permutons p in said
neighbourhood. Let n be a natural number, then for i,j £ [n — 1] we define
B%,i = (e
i ~ e
i+i)(e
j ~ e
j+i)T £
K"x
™ to be the n-perturbation at (i, j). Given
formal variables x = (xij)^ 1
' , we define matrix J(x) : R n X n
by equation
[«-i]2
3{x) = J + ^2 x
i,jBi,j-
i,3
For given n £ N , we define the set of perturbed permutons Vn to be the set
of permutons which are Cn(x) := pl(x) for some x £ R[™_ 1
1 . Our aim will be
to show that any set S C S<5 of order four cannot be P^-forcing for some n £ N
and thus cannot be forcing. Let (n(x) € V„ be a perturbed permuton, then
using L e m m a 3 we can observe that for any a £ the density d(a,Cn(x)) is
2
A reader may ask whether the space of permutations and permutons admits a metric
under which convergent sequences correspond to Cauchy sequences. The answer is yes but
the metric d\j called cut distance is not trivial to set up and we do not need it here.
CHAPTER 2. PERMUTATION LIMITS
t
14
3=1,1 + h -Xl,2 + k
+ X2,l + 3 Xlti
-X2,l + I
B2.I
Xl,2
X2,l ~ 2:2,2 + g
I{x)
X2,2 +
I 0 0 0 \
1 -1 0
\
-1 1 0
/
13 1 7
.'!() :s 30
13 7 1
30 15 10
2 1 2
15 r> :s
1 1 2
10 ' 10' 10 '
£2,2 + \
L _2
10' 10' 10' 3I)
Figure 2.1: Construction of perturbed permuton £3(2;) £ P3 for a; £ M 2
defined
by = 1/10, ari,2 = 1/10, ar2 ,i = 2/10, and a;2 ,2 = 1/3.
polynomial i n M[x], we call this polynomial fn><7 £ K[ar] the density polynomial
of a. Further, we define polynomial gn>(J = fn><7 — d(a, p) which we call the
discrepancy polynomial. The above states that Gs\vn
0
Cn '• —> Rs
is
a polynomial i n each coordinate; our aim is to find a small nontrivial common
root of these polynomials.
Chapter 3
First-order Method
The first method—method which will allow us to exclude majority of the studied
sets—will be based on the properties of the Jacobian of Gn>s :
= Gs\vn ° Cn
and use of Implicit Function Theorem. Informally, our aim is to show that
majority of permutation 4-sets are "independent", which gives us enough degrees
of freedom with respect to perturbing the random permuton that we can indeed
construct permuton which contradicts "P„-forcing. This method is the main tool
used in [19] and serves as the uniform reason why 3-sets with sufficiently large
permutations are not forcing.
We start by reviewing elements of real analysis. We denote by Cn
the set of
function with continuous partial derivatives of order at most n and denote by
C°° the set of smooth functions, i.e., functions with continuous partial derivatives
of all orders. For function F : W1
—> M m
differentiable at point p, we denote
by DXPF : M.n
^m
the Jacobian of F with respect to variables x evaluated at
point p and use DPF : M.n
^m
to denote the Jacobian of F at point p. Let us
recall the Implicit Function Theorem which gives a sufficient condition which
allows us to locally express the level set of a smooth function F : W+c
—> R c
around a point {xo,yo) G W+c
as a graph of a smooth function 0 : W —> K c
.
The statement, its proof and further discussion can be found in any standard
text on multivariable calculus, e.g., [24].
Theorem 5 (Implicit Function Theorem). Let r, c G N and let F : W+c
—> R c
be a smooth function with F(XQ, yo) = 0, where XQ G W and yo G M.c
. Suppose
the matrix DY^XOYO)F is invertible. Then there are open sets XQ G U C M.R
and
jo 6 F C I c
and a smooth function 0 : U —> V so that for x G U and y G V,
we have that F(x, y) = 0 if and only if <p(x) = y.
Given a permutation set S, we say that the set is n-independent, if DoGn^s
does not have deficient rank. The following lemma tells us that such sets cannot
be forcing. We repeat the proof of [19] for completeness as Chapter 4 builds
upon the argument which follows.
Lemma 6 ([19] Lemma 5). Let S be a finite set of permutations and n a positive
integer with (n - l ) 2
> \S\. If S is n-independent, then S is not 'P„-forcing.
15
CHAPTER 3. FIRST-ORDER METHOD 16
Proof. Let S be a finite set of permutations with DoGn^s '• R(™ 1
-) _ i
"', s
' of rank
|<S|, i.e., DoGn^s does not have deficient rank and is a linear surjection. A s linear
surjections split, let L : R l , s
l ^ ' ( n _ 1
) be a map so that DQG„^L is identity and
let v £ Im L be a non-zero vector which exists by (n — l ) 2
> \S\. Define
F : M 1 +
I 5
I -> M l 5
l by sending {x,y) £ M 1 + | 5 1
to Gn,s(xv + Ly). A s DyflF =
DoGn^sL is invertible, it follows from the Implicit Function Theorem that there
exist open sets U C M.1
and V C M ' 5
' and a smooth function <j> : U —> V such
that for x £ U we have F(x,<j>(x)) = Gn>s{xv + L<p(x)) = 0. B y choosing
i ^ O and noticing that L<p(x) + xv ^ 0 as v is a non-zero vector orthogonal to
image of L, £n(L(fi(x) + xv) is a non-uniform permuton with correct densities
for permutations a £ S, proving S is not 'Pn -forcing. •
3.1 Gradient Polynomial
In this section, our aim is to find a sufficient condition for set S to be ndependent
for some sufficiently large natural number n £ N without determining
the rank of individual Jacobians DoGnts- To this end, the gradient
A)5n,a e R (
™ - 1 ) 2 _ > 1
can be viewed as a matrix Mn>a £ RC™"1
)^™"1
) defined by
{Mnt<7)itj = (£)
ofln,o-)i,(i,j). Let s„i C r : (0, l ) 2
—> K be a step function associated
to Mn><7 which maps (a, {3) £ (0, l ) 2
to {Mn>a)^an^^pn^. The pointwise limit
sa(a,/3) of the sequence (s„i C T (a,/3))„ now represents a infinitesimal perturbation
in p at (a, /3) with radius going to zero and thus the limit sa is identically
zero.
To avoid vanishing, author in [19] normalizes the sequence and introduces
for permutation a £ Sk the notion of a gradient polynomial defined by
Pa(a,f3) = lim n3
sna(a,/3).
71—¥00
Result of Kurecka is that not only is this function well defined, it is i n fact
non-trivial and a polynomial in a and f3. The aim of this section is to describe
the polynomial and survey the consequences of its existence.
Given k £ N , let Bk : R ( f e
" 1
) ^ f e
and Dk : M ^ " 1
) ^ " 1
) be matrices defined
by
{Bk)i,i = (-IT (. [ J and (£>*)*,, = l(i = 0(-l)'+ 1
(* ~ J),
where recall that we define (^) to be zero whenever n < m. Note that Dk
is an invertible diagonal matrix and that Bk is an injective linear map with
cokernel equal to the span of the all-ones vector j £ K.k
; namely this implies
that B^j = 0. Let us define {a1
ft \ f) to be the coefficient of the monomial
a1
ft in the polynomial / £ R[a,/3]. We define the fc-th coefficient matrix
of the polynomial / £ R[a,/3] to be the matrix T^f : ]R(f c
+1
)^(f c
+1
) with
{T^f)itj = (a^-Vfti-V | / ) for i,j e[k + 1]. We are now ready to describe
the polynomial Pa.
CHAPTER 3. FIRST-ORDER METHOD 17
Theorem 7 ([19]). Let k > 2 be a natural number and a £ Sk with cover
matrix Aa £ M.k
~*k
, then PC T is a real polynomial i n a,/3 with (a1
ft | / ) = 0 if
i > k — 2 or j > k — 2. Moreover,
TCT := T ( f c
- 2
) P C T = CkDlBlAaBkDk
where ck = k(k — l)/(fc — 2)! is a positive real number. We call TC T the gradient
matrix of permutation cr.
Notice that due to the fact that {aq
'ft \ Pa) = 0 holds for i or j greater
than k — 2, it holds that Ta fully describes the polynomial Pa. Given a superpermutation
v = Y^f v
<J0
°f order fc, define Pv = Yf v
<JP<J and define
Tv := T ( f e
- 2
) P „ = YZv
<?T(k
~2)p
^ n o t e t h a t
matrices T^k
~2
^Pa : ^-\)^{k-i)
are not necessarily matrices Ta : ]R(I°'I_ 1
)_ J
*(I0
'I_ 1
) but the former can be a "zeropadded"
version of the latter. Let us at this point extend the definition of a
cover matrix to the spaces MSk, by defining it for v = ^o-o" with finite set
S C Sfc to be the matrix Av = J2a VaAa. Note that due to distributivity of
matrix multiplication, it holds that T„k
^ = ckDj.BkAvBkDk for v £ RSfc.
Given a set S, we say that it is independent if the polynomials (Pa)f are
independent as elements of the vector space R [ a , /3]. If they are dependent,
there exists v £ MS whose support is subset of S with Pv = 0; we call such
superpermutation the dependence witness. The following lemma relates the two
notions of dependence presented so far and its proof can be found in [19] in the
proof of L e m m a 8 which we state as Proposition 9. A s the argument is short
and the lemma is not directly present in the source as stated, we include it for
completeness.
L e m m a 8. Let S be a finite set of permutations and let N £ N. If S is
independent, then it is n-independent for some n > N.
Proof. Let |5| = m and assume that there exists N £ N such that S independent
but is n-dependent for all n > N. Let (£„)«"" be a sequence of normed vectors
tn £ [— l , l ] s
with t^Gn>s = 0 for every n > N. A s [— l , l ] s
is sequentially
compact and norm is a continuous function, there is an injective h £ O r d ( N , N)
such that (th(„))n~N
converges to some t £ [— l , l ] s
of norm one. A s Pa =
l i n i n ^ O O n3
sn,s = hmn-S-OO ^(w)3
Sh(N),s and product of limits is limit of products
given the limits converge, we have
s s s
E f P
- = E ( l
T *M»>)( l
T h
(nfsh{n),a) = l i m h(n)3
J2tkn)sh(n),a = 0
*—* z
—J
n—»OO V 3
n—»OO n—»00 Z
— J K
'
a a a
as t^G„ts = 0 implies Ylf ^ns
n,a = 0. The just presented equality contradicts
the assumption that S is independent. •
A direct consequence of L e m m a 8 and L e m m a 6 is the following.
Proposition 9 ([19] Lemma 8). Let S be a finite set of permutations. If S is
independent, then S is not forcing.
CHAPTER 3. FIRST-ORDER METHOD 18
This theorem gives us a simple algorithm by which we can computationally
eliminate majority of the cases: iterate sets S systematically—we do so
in Chapter 5—construct T$ := (Tak 2
-)
)f where k is the order of the largest
permutation i n the set and use Gaussian Elimination to determine if matrices
in Ts are independent as elements of linear space ] R ( f c _ 1
) x
( f c _ 1
) . If yes, the set
S cannot be forcing. If no, we add set S to the set of possibly forcing sets for
which we need stronger tools.
Before discussing higher-order tools, we briefly review important consequences
of the theorem above. Note that the theorem claims that any forcing
set S has a dependence witness v. We can use this information with the very explicit
description of polynomial Pv through Tv to obtain the following corollary
used in [19, 9, 17].
Corollary 10. Let v = vao for S C S j . If Pv = 0, then Av = c j for some
c £ EL Namely, if S C SK is forcing with dependence witness v £ MS, then
Av = c j .
Proof. Let us denote the matrix Av by A. A s all permutations in S are of order
k, it holds that Tv = ckD\B^ABkDk by distributivity. Now as Tv = 0, we have
B^ABk = 0 as Cfc ^ 0 and both Dk and D^ are full-rank diagonal matrices. Let
us split Mk
= Mj © j x
and note that both subspaces are invariant with respect
to Av: as Av is linear combination of doubly-stochastic matrices, we have that
AT
j = Aj = \j for some A £ M which for u £ j ±
implies (j, Au) = u) = 0.
We thus split A to Aj © Aj±, where Aj : Mk
—> Mj has the property that
ker Aj = j1
- and AJJL : Mk
—> j1
- with property that k e r A ^ = Mj. Then
note that 0 = Bl(A} © A3±)Bk = B\AjBk + B]:Aj±Bk = Bk
r
Aj±Bk = 0 as
AjBk = 0. The last equality and the fact that Bk is an isomorphism of Mk
onto
j ±
implies Aj± = 0. A s Ajj = Ajj = Aj and Aj has rank at most one, we have
A = Aj © Aj± = Aj = ±jjT
as desired. •
3.2 Subsampling and Fuzzy Covers
We now turn to the notion of a "fuzzy" permutation covers used in [9]. For this,
we need to review an important property of the space of superpermutation,
namely the subsampling identity sometimes called the chain rule—as we reserve
the latter name for the standard analytical chain rule, we stick to the former.
Given permutations a £ SK, TT £ S„ and an integer I such that k < I < n, we
have
Si / s, \
= Y^ T)d(r, TT) = d I ^ d(a, T)T, TT I. (3.1)
To see (3.1), consider the following experiment. Let us uniformly at random
sample U £ [n]^ after which we uniformly at random sample P £ U^k
K It
is clear that this induces uniform distribution on P £ [n]^ and as such, we
CHAPTER 3. FIRST-ORDER METHOD 19
have d(a, ir) = P(7r|p = a). B y law of total probability, we can express this
probability as
Si
F(n\P = a \ n\u = T)F(n\u = T)
T: V(TT\U=T)>0
and as P is uniformly sampled from U^k
\ we see that P(7r|p = a \ TT\U = T ) =
d(a,r) and F(7r|[/ = T ) = d(r, ir) for r with P(7r|t/ = r ) ^ 0. The claim follows
as for T with P(7r|j/ = r ) = 0 we have d(r, ir) = 0.
We define L^a = jfT' d(a, T)T £ MS; to be the l-th. lift of a and define the
l-th lift cover A^ to be the cover matrix of the superpermutation L^a. The
subsampling equality motivates the definition of the quotient space A, given by
factoring out the subspace generated by the set {a — L^a | a £ Sfc, I > k} from
space MS. Due to (3.1), we see that d(—,n) : MS —> M. for every permuton /i
factors through d(—, ji) : A —> M. From this, we conclude the following property
of gradient polynomial P : MS —> M[a, [S\.
L e m m a 11. T h e linear map P : MS —> M.[a, f3] factors through P : A —> R [ a ,
Proof. W e need to show that Pa_La)(J = 0 for any a £ Sfc and any I > k. It
holds that
s,
P a _ L ( n ) a = Pa-J2d(a,T)PT
T
s,
= l i m n3
s„tCr — d(a, r ) l i m n 3
s „ i T
77.—»00 ' ^- ^ 77.—^OO
lim n 3
( s n i C T - d(a, r)sn T)
= l i m n • 0 = 0,
77—»00
where we use that P is linear on MS, l i m „ _ I > 0 0 is linear on convergent sequences
and D0g„^ = D0gn L ( n ) a = d(a,n)D0g„,7r by subsampling and linearity of
D0. •
A s i n [9], we for I > k define l-th fuzzy cover of a £ Sfc to be the matrix
: R1
^1
defined by
where
CHAPTER 3. FIRST-ORDER METHOD 2 0
A T , = F,
(-1)
CTl -L <J\
1F(5)
20 CT
1 120 CT
1
A . , = K
(-1)
•
•
C"2 0"2
1 ^ ( 5 )
20 CT
2 120 CT
2
Figure 3.1: The 4th, 5th, 6th, and 7th lift of permutation a\
a2 = 3142
1342 and
Note that if I = k, it holds that fj:^{u) = l(u = j) from which it follows that
(k)
Fa = A J . We again extend the definition of lift cover and fuzzy cover linearly
to space MS; for a £ Sfc and I < k, define A1
^ = Fa^ = 0 for completeness,
at no point of what follows is this pathology important. The following lemma
establishes important connection between the notion of a lift cover A^o~ and
fuzzy cover F^a.
Lemma 12 ([9] Lemma 4.5). Given a £ and I > k, it holds that
(k - 1)!\k
X
B y the just stated lemma, it is immediate that Fa
1
^ has eigenvector j for all
a £ Sfc and I > k.We repeat a simple direct computation from [9] which shows
that eigenvalue corresponding to eigenvector is (I — 1)1/(k — 1)!To
determine the corresponding eigenvalue, we first note that
E
i-k+j
E
u=j
where the last equality is witnessed by a bijection which sends A £ [l]^ to
(Aj,A n { 1 , A j - 1}, A n {Aj + 1 , I } ) , where Aj is the j - t h element i n the
set A according to the natural order on A C [I]. We conclude
CHAPTER 3. FIRST-ORDER METHOD 21
u Vfc/ j
that together with the equality
implies
['] [fc]
^ ( F « ) M = ( / - f c ) ! ^ / ^ . ( l ) = (/-fc)!
« — 1 \ _ ( / - ! ) !
fc-V ( f c - 1 ) ! '
(AO
We say that superpermutation v £ MS of order k has constant cover, if F„
(or equivalently A ^ ' ) is a constant matrix, i.e., it is a scalar multiple of J , and
(k)
say that v has non-vanishing constant fuzzy cover, if Fi, = c j for c f 0. The
next lemma shows that any dependency-witness has a constant cover.
L e m m a 13. Let v £ MS be a superpermutation of order k with Pv = 0 and let
I > k. Then FP E K J .
Proo/. A s v and = L ' ' V £ R S , map to the same element i n A, we have that
Pv(i) = 0 which in turn by Corollary 10 implies that Aum = A$ £ K J . This
together with linear extension of Lemma 12 concludes the proof. •
Superpermutations v £ K S with support of size four and non-vanishing
constant fuzzy covers were fully described in [9].
Theorem 14 ([9] Proposition 4.22). Let v = Ylf^ be a superpermutation
with non-vanishing constant fuzzy cover, then one of the following cases occurs:
1. all permutations in the support are of order at most three,
2. all permutations i n the support are of order four and form a Latin square,
i.e., their cover matrices have disjoint supports as functions [4]2
—> {0,1},
3. up to action of symmetries of a square1
and scaling by a scalar, it belongs
1
We postpone the formal definition of the action to Chapter 5 page 36.
CHAPTER 3. FIRST-ORDER METHOD 22
to the finite set
3(1234) + 3(4321) - 4(123) + 3(12),
3(1234) + 3(4321) - 4(123) - 3(21),
3(1324) + 3(4231) - 4(123) + 3(12),
3(1324) + 3(4231) - 4(123) - 3(21),
3(2143) + 3(3412) + 4(123) + 3(12),
3(2413) + 3(3142) + 4(123) + 3(12),
3(1234) + 3(4321) - 2(123) - 2(321),
3(1324) + 3(4231) - 2(123) - 2(321),
3(2143) + 3(3412) + 2(123) + 2(321),
3(2413) + 3(3142) + 2(123) + 2(321),
36(12345) - 36(52341) + 15(2143) + 10(321),
36(12345) - 36(52341) - 15(3412) - 10(123),
36(12435) - 36(52431) + 15(2143) + 10(321),
36(12435) - 36(52431) - 15(3412) - 10(123).
The theorem above has an important consequence. Let S be a forcing set
of size four whose largest permutation has order k and let v be its dependencywitness.
T h e n as F^ is constant, either v is one of only finitely many described
(k)
in Theorem 14, or = 0. From now on, we denote the set of supports of
permutations in Theorem 14 by T>+. Using tools from next chapter, we establish
that none of the sets i n V+ is forcing, strengthening the statement that the
superpermutations mentioned are not forcing.
Before continuing, let us discuss limitations of this method. It is clear that
one cannot hope to exclude all sets using only the first-order information as
there are examples—e.g., all sets contained in T>+—that are dependent but one
may hope that there is only finitely many such sets. The following infinite family
of dependent sets shows that this is not the case.
Example 15. Let I > 2 be a positive integer and let Si be a set containing
permutations \d2i+i £ § 2 ( + i , T ( i ( + 2 £ § 2 ( + I , id2 j £ S2i and T ^ + I £ S 2 ( , where
idfc denotes the identity element of symmetric group Sfc and TJJ £ denotes
transposition of i £ [I] and j £ [I]. The set Si is dependent.
i d 7
T
3,5 i d 6
T
3A
Figure 3.2: Dependent set S3.
CHAPTER 3. FIRST-ORDER METHOD 23
Proof. We show that for v = id2 ?+i - T M + 2 - (21 + l)(l + l ) ~ 2
( i d 2 ? we
have Pv = 0. Let v\ = id2i+i — and v-i = ^21 — T~L,I+I- First, it
is easy to see that AV1 = (e; — ei+2)(ei — ei+2)T
and similarly AV2 = (e; —
ei+i)(ei — ei+i)T
; for intuition see Figure 3.2. Our aim is to show that for
vectors v = Djl+1Bjl+1(ei — ei+2) and u = D^Bj^ei — ei+\) we have that
Vi = (21 — l)(l + for i G [21 — 1] and Vi = Ui = 0 for i = 21. This shows
the claim, for TVl = C2i+\vvT
, T„2 = C2iuuT
, and identity
(2Z — l ) 2
(21 + 1)21 (21 - l)2
(21-1)21(21 + 1) 21 + 1
c
2*+l „ , - TKi TTT „ , ^ 9 - ~7Wi oTT n , -,^9 ~ c
2'
(i + i)2
(2/-1)! (i + iy (2i-2)\ (i + iy Zl
(i + i)2
implies TV1 = (21 + l)(l + 1)~2
T^1 1
\ Expanding the definition reveals for
k > 2 and a, 6 £ [k] the identity
> « ' • • - - (1:1) i - " " ' ((-'>*(« -1) - (
- I ) l
G - . ) )
which i n turn implies
». = ( - . ) - ' ( 2
' - ! ) ( ( , ' , ) - ( , M l —
«-1 y \ vz - iy v +1
- < - . r - ( » - ) ( ( ( : > ( ! ) ) - ( - ^ : f ) C r
for every i 6 [21 — 1] and Vi = 0 for i = 21. Now note that Vi = Ui = 0 for
j < I — 1 and otherwise a direct computation expanding the binomial coefficients
reveals that
i \ ( i \ \ ( i + l \ 1
2l — i
+
and
l - l j \1 + 1J \ I J l + l
21 - 1\ (21 - 2 \ 21-1
i - 1 ) \ i - l ) 21 -i
by which we conclude that for I — 1 < i < 21—and consequently for i < 21—it
holds that vt = (21 - l)(l + l)~1
ui. •
Chapter 4
Second-order Method
In this section, we review the main method used in [17], providing superficially
different but morally equivalent proof of Theorem 5 and Corollary 11 which is
the main mathematical result needed for our work. We then move to lemmas
which allow us to, in a computer assisted fashion, certify that a dependent set
is not forcing. We finish the section by describing certificate for dependent set
S and illustrate the method on a simple example.
4.1 Walking in the Zero Set
We start by continuing the review of multivariable calculus. Given a smooth
function F : Rn
—> Rm
, we define HXF to be the bilinear map induced by
Dx(y i—^ DyF): note that Dx(y i-> DyF) is element of the set C(Rn
, C(Rn
, Rm
))
a priori, but there is a canonical isomorphism with the set of bilinear maps
C(Rn
<g> K n
, Rm
) which maps ip to (ei ® ej H> <p(ei)ej). A s such we have
(HxF(ei,ej))k = HxFk(ei,ej) = Dx(y -> DyFk)(ei)ej
d2
Fk
= Dx(y -> DyFke3)(ei) = ^ ,
where the second to last equality follows from a version of Leibniz rule which
can be found in Appendix A . In what follows, we need to determine Hessian of
a composition of two maps F : Rn
—> Rm
and G : Rm
—> Rs
which we do using
the following equality
Hx(GF)(u,v) = HF{x)G{DxFu, DxFv) + (DF{x)G)HxF(u,v)
which is derived in Appendix A . In what follows, we primarily study functions
of the form / : Rn
—> R in which case Hxf is a bilinear map of the form
I " x I " -> I and as such we identify it with a matrix M £ ^™x
™ f o r which
it holds that Hxf(u,v) = uT
Mv which is standardly called the Hessian matrix
of function / at x. It is a standard result of theory of smooth maps that such
matrix is for a smooth map / : Rn
- > I a real symmetric matrix.
21
CHAPTER 4. SECOND-ORDER METHOD 25
Let us start by stating a lemma from the area of differential topology that
states function / : R™ —> R without linear behaviour and with quadratic behaviour
which is not degenerate behaves like c + ^}™\—1)'*^» for c £ R and
k £ N for all i £ [TO] up to smooth change of coordinates.
L e m m a 16 (Morse Lemma). ([14] L e m m a 1.1) Let / : R™ -> R be a smooth
function with DQJ = 0 (zero is a critical point), and with HQJ being invertible
(the critical point is nondegenerate). T h e n there are neighbourhoods U, V C R™
of zero and a diffeomorphism u : U —> V such that u(0) = 0 and for all x £ U
it holds that
A n
f(x) = f(0)-,
£ui(x)2
+ Y, u
^)2
'
i=l i=A+l
where A = Ao(/) is the Morse index of the critical point 0, i.e., A is the number
of negative eigenvalues of the Hessian HQJ .
Let us for natural number n £ N , smooth function / : R™ —> R, and a
vector x £ R™ define d+
jd~ to be the dimension of the sum of positive/negative
eigenspaces of Hxf. We define Kx(f) = mm{d+
,d~}.
L e m m a 17. Let / : R™ —> R be a smooth function with /(0) = 0, zero being
a critical point, and Ko(f) > k. Then there is an injective smooth map p :
[-1, l ] f c
-> R™ with p(0) = 0 such that fp = /(0) = 0.
Proof. A s Ko(f) > k, there is a linear injection J : M.2k
~*n
with the property
that JT
HofJ is an invertible matrix with k positive and k negative eigenvalues:
consider map J which sends the standard basis to the system of 2k orthonormal
eigenvectors that are guaranteed by the Spectral Theorem applied to Hof and
assumption Ko(f) > k. For g = fj : R 2 f c
—> R, we have D0g = (D0f)J = 0 as
zero is a critical point of / . Moreover, as J is a linear map, we have HQJ = 0
from which it holds that
H0g(x, y) = HJ{0)f(Jx, Jy) + (DJ{0)f)H0J(x, y) = (JT
(H0f)J)(x, y)
and so as Hog = JT
(Hof) J, we have Ko(g) > k with zero being a nondegenerate
critical point of g. B y Morse Lemma, we have open sets U, V C R 2 f c
and a
diffeomorphism u : U —> V such that for x £ U, it holds that
k 2k k
g{x) = fl(0) - Ui(x)2
+ Y u
i(x
)2
= + ^ K + i ( z ) 2
" Ui(x)2
).
i=l i=k+l i=l
Let p > 0 be a real number such that the ball at origin of radius p is contained
in V, formally Bp(0) = {x £ R 2 f c
| \x\ < p) C V, and let S > 0 be a real number
such that S < p ( 4 f c ) - 1
/ 2
. Define a mapping r : [—1, l ] f c
—> R 2 f c
by
A:
r
(i
) = s
y^Ji(e
i + efc+i),
CHAPTER 4. SECOND-ORDER METHOD 26
where recall that is the i-th standard basis vector of R 2 f c
. Due to the inequality
+ e f c + l ) | | 2
= 2S2
*? < 2^2
fc < \ P
2
< p\
i=l i=l
we conclude that the image of r is contained in V. Define q = u _ 1
r : [-1,1]* -r
U, where the composition is well defined by the previous comment. M a p q is
injective as r is clearly injective by definition and u is a diffeomorphism. We
have that
k k
Uj{q{t)) = (ej,uu~1
(5'Y^U{ei + &k+S)) = S^2u(l(j = i) + l(j = k + i)).
i=l i=l
As such Ui(q(t)) = Uk+i(q(t)) = 5U for every i £ [k]. A t last, we have
k
g(q(t)) = g(0) + Y,(uk+i(q(t))2
- Ui(q(t))2
) = g(Q).
i=l
Finally, setting p to be the composition of two injections Jq finishes the proof
as fp = fJq = gq = g(0) = /(0). •
L e m m a 18. Let F : R™ —> W71
be a smooth map with F(0) = 0 and with
Jacobian DQF of rank at least m — 1. Let w £ M m
be a vector of norm one such
that Wt
(DQF) = 0 and KQ(WT
F) > m. Then there exists a smooth injective
map p : [—1,1] —>• Rn
such that Fp = 0.
Proof. Let us define P = (1 — wwT
) to be the linear map which projects M " 1
onto w x
. Let F1 : Rn
-> w x
C M m
be defined as F i = = (1 - wwT
)F. As
w±
is (m — l)-dimensional and WT
DQF = 0, we have that Do-Fi is surjective
onto (m — l)-dimensional subspace w x
. It follows from the Implicit Function
Theorem that there exist open sets U C R n _ m + 1
, V C and a smooth
map <j) : U —> V with the property that for every x £ U and y £ V it holds
that F\(x,y) = 0 if and only if y = <fi(x). Define T : U —> R™ to be a map
which sends x to (x, 4>{x)) so that FXT = 0 with T(0) = 0 by Pi(0) = 0. It is
immediate that the Jacobian DQT is an injective linear map.
Next, we examine the map i<2 = w1
FT : U —> R; here, reader should view
F2 as a map F — F\ = wwT
F : M.n
—> w K restricted to the (n — m + 1)dimensional
manifold of the level set of PF around zero which we obtained
by the Implicit Function Theorem. First, let us note that by chain rule, we
have D0F2 = wT
(D0F)(D0T) = 0, where we use the fact that T(0) = 0 and
WT
{DQF) = 0. Moreover, we have that for all x, y £ R™ it holds that
H0F2(x,y) = HT{0)(wT
F)((D0T)x, (D0T)y) + D0(wT
F)H0T(x,y)
= H0(wT
F)((D0T)x,(D0T)y)
where the last equality is due to the assumption DQ(WT
F) = 0. B y assumption
we have that KQ(WT
F) > m and so both the space of positive eigenvectors and
CHAPTER 4. SECOND-ORDER METHOD 27
the space of negative eigenvectors of HQ(WT
F) are of dimension at least m. A s
DQT is a linear injection onto a subspace Im T C M m
of dimension n — m+1, i.e.,
of codimension m — 1, it follows that Im T has nontrivial intersection with the
space of positive and the space of negative eigenvectors of HQ(WT
F). Thus, we
conclude that matrix (DQT)T
HQ(WT
F)(DQT) has both a positive and a negative
eigenvalue, i.e., reoC^) > 1- From L e m m a 17 applied to F2, we obtain a smooth
injective map q : [—1,1] —> M.n
~m+1
such that F2q = F2(Q) = 0. Finally, take
p = Tq: [-1,1] -> R™ then
F p = (1 - w T
+ wwT
)FTq = PFTq + wwT
FTq = F\Tq + wF2q = 0.
•
The above lemma serves as the main mathematical tool of this chapter. Before
stating the problem-specific corollary, we first remark that Ko(wT
Gnts) can
be determined from eigenvalues of Yl„ w
Tr(Hog„t7r) £ R n X n
as due to repeated
application of linearity of derivatives, we get
H0(wT
Gn,s) = D0(x 1 ^ Dx{wT
Gn>s)) = D0(x ^ wT
DxGn,s)
s s
= D0(x H> ^ w ^ D j G ^ s ^ ) = WTT-DQ(X H> D x g n ^
7T 7T
s
= ^ w-n{H0gn^).
Corollary 19 ([17] Corollary 11). Let Q C S C § be a set of permutations
with \Q\ + 1 = \S\ = m , where Q is n-independent and S is n-dependent with
wT
£ M7
™-
**1
being the witness to this fact, i.e., wT
DoGn>s = 0. If the matrix
s
H%Gn,s : = ^ w n H 0 g n ! n £ R n
^ n
has at least m positive and m negative eigenvalues, then S is not P„-forcing.
Proof. Due to Q being n-independent, we have that the rank of D0Gn^ is
m — 1. Let w £ M.m
be the non-zero element of the kernel of (DoGnis)T
of norm
one. B y L e m m a 18, there exists an injective map p : [—1,1] —> IR^™- 1
'2
such
that Gn>sP = Gs\vnCnP = 0. A s such permuton \i = Cn(p(e)) for e > 0 is a
non-uniform permuton with Gsl'PnIJ' = 0 contradicting "P„-forcing of S. •
As our approach is computational, we need to be aware of numerical precision
and problems associated with doing numerical computations. For this, we
introduce simple lemmas which allow us to safely certify lower bound on the
count of positive resp. negative eigenvalues of a matrix.
Given a set of vectors (vi)^ i n K " , we define its associated linear map to
be map V : R k
^ n
sending to Vi. We say that collection of vectors (?;»)[*' is
CHAPTER 4. SECOND-ORDER METHOD 28
ortho-normal if it holds that VT
V = Ik £ Hk
~*k
, where Ik is the identity map on
Rf c
. Given a symmetric matrix M : M.nXn
, we define its associated symmetric
bilinear form ( a ; , y ) M 1
to be xT
My.
L e m m a 20. Let 5 > 0, M £ M™x
™ be a real symmetric matrix, and (vi)^ £
(R™)[m
l be an orthogonal collection of vectors with the property that for all
i,j £ [TO] either i = j and {vi,Vj)M > 8 or i ^ j and | ( W ^ ^ M I < 8/(m2
— TO).
Then for all u £ R{wj}[m
' we have that {u, U)M > 0.
Proof. Let V : JR"1*"™
be the linear map associated to the collection We
want to show that for u £ Im V C K " it holds that {U,U)M > 0. It is enough
to consider u = Vw = X^™'w
i v
i with ||w|| = 1. After expanding the product
and applying the triangle inequality, we obtain
[m]2
[m] [m]2
(U,U)M = ^ WiWj{Vi,Vj)M = y^;W2
{Vi,Vi)M + y^WiWj(Vi,Vj)M
L e m m a 21. Let 8 > 0, M : ]R™X
™ be a real symmetric matrix, and ^
( R " ) [ m
l be an orthogonal collection of vectors as i n L e m m a 20. Then M has at
least TO positive eigenvalues.
Proof. A s M is a real symmetric matrix, it holds by the Spectral Theorem that
there exists a real orthogonal matrix V and a real diagonal matrix A such that
M = WAWT
, W is associated with an orthonormal system of eigenvectors of
M, and (A^)'™' = (Aj)[n
' is a nonincreasing sequence of eigenvalues of M.
For contradiction, assume that \ m < 0 so that M has at mostTO— 1 positive
eigenvalues. Let -/V be the subspace spanned by eigenvectors (wj)™= m with nonpositive
eigenvalues. Let V C K " be the subspace spanned by • A s
dim TV + dim V = n — m + l+ m = n+l, we conclude that V f) N 0. Let
v £ V n -/V be a non-zero vector. A s v is contained i n the subspace N, it can be
written as a linear combination v = X ^ " = m
v
i w
i meaning Mv = J2"=mVi\iWi
^^Note that the product may not be positive-definite, i.e., it is not an inner product on the
space M™.
2
where note that for ||w|| = 1, we have < 1 for all i £ [TO •
CHAPTER 4. SECOND-ORDER METHOD 29
and so at last we obtain inequality
n n
(V, V)M = (V, Mv) = ( ^ ViWi, ^ v
i^i
i=m i=m
n n
= ^ ViVj\j{Wi,Wj) = ^ V
i^i - 0
i=m,j=m i=m
where the last inequality is due to Ai being non-positive for all i >m. The just
made conclusion contradicts Lemma 20 as v £ V. •
We finish this section by stating a problem-specific corollary which we call
second-order certificate lemma as it describes the main sufficient condition of
this section. Given a matrix A : WnXn
, let us define the diagonal gap 7 : R n x
™ —>
[0, +00] to be
1 { A ) _ m i n f 1
1^,, I
if there is a non-zero element off the diagonal, otherwise set j(A) to be the
positive infinity.
Definition 1. Let M : M " x
" be a real symmetric matrix. We call the linear map
V : R m
^ n
associated to a collection of vectors C Rn
a positive/negative
m-witness for M , if
(i) VT
V is diagonal, i.e., is an orthogonal set,
(ii) VT
MV has positive/negative diagonal, i.e., all elements on diagonal are
greater/less than zero, and
(Hi) j(VT
MV) > m(m - 1).
Lemma 22. If V is a positive m-witness for a matrix M : M " x
" , then V is a
negative m-witness for matrix (—M) : R n _ y n
Proof. Property (i) is independent of M. For property (ii) note that j(—A) =
7(A). Finally, (VT
(-M)V)^ = -(VT
MVT
)^ < 0 by V being a positive
m-witness. •
Lemma 23. If V is a positive m-witness for a real symmetric matrix M : M™x
™,
then M has at least m positive eigenvalues.
Proof. A s VT
V is a diagonal matrix with positive diagonal, the set (fi)[m
'
associated with V is orthogonal. Let 5 = m m j m
' (v;, VI)M > 0 SO that for all
i £ [m] the inequality («i,Wi)M > 8 holds. B y j(VT
MV) > m{m — 1) for all
i,j £ [m] with i ^ j, it holds that
\(vi,Vj)M\ < m a x K ^ ^ M l < j(VT
MV)'1
mm\{vi,Vi)M\ < —, rrt
m(m — i j
CHAPTER 4. SECOND-ORDER METHOD 30
B y L e m m a 21 with vectors , we have that matrix M has at least m
positive eigenvalues. •
L e m m a 24 (Certification Lemma). Let n £ N and let S C § be a set of four
permutations with DoGn>s of rank three together with n-dependence witness
w £ Rs
, i.e., we have wT
DoGn,s = 0. If there is a positive 4-witness and a
negative 4-witness for matrix H^Gn^s, then S is not Pn-forcing.
Proof. Let V+, V- be the positive and negative m-witnesses respectively. B y
Lemma 23 with V+ and H := HffGn^s, the hessian H has at least m positive
eigenvalues. B y L e m m a 23 and L e m m a 22 with V-, the hessian H has at least
m negative eigenvalues.
As D0Gn^s has rank three and KQ(W7
'Gn,s) > m, we conclude by L e m m a 18
that there exists an injective smooth path p : [—1,1] —> R™ such that Gn>sP = 0.
Let e be a real positive number, then for any a £ S we have (Gn>s(p(e)))a =
d(<7, C(p(£
))) ~~ P) = 0 even though C(p(e
)) is n
° t the uniform measure. •
4.2 Example
Throughout what follows, we heavily rely on a large number of computationally
obtained certificates as described in L e m m a 24. Due to the number of certificates
and their size, we do not include them i n the main body of the text and instead
point reader to Appendix D whenever it is appropriate. We devote this section
to a concrete example use of the method, namely we use it to show that the set
S = (1234,1324, 2143,123) is not forcing.
Let n = 4 be the order of the perturbed permuton being considered, i.e., our
goal is to prove that S is not ^ - f o r c i n g . We display D = DQG^S on Figure 4.1
and claim that w = (1,4/5,3/5, —4/5)T
generates kernel of D T
' , which implies
that set S is 4-dependent and moreover that DQG^S is of rank 3. Our aim is to
show that Hessian HQG^S displayed on Figure 4.2 has four positive and four
negative eigenvalues. To this end, we use L e m m a 24 with positive 4-witness
V+ displayed on Figure 4.3 and negative 4-witness V- displayed on Figure 4.4.
To see that V+ is indeed a positive witness, direct computation whose result
is displayed on Figure 4.3 shows that the matrix V+V+ is a diagonal matrix,
values on diagonal of matrix Vj'HQGn>sV+ are indeed positive, and finally that
we have the inequality f{V?H%>G4TSV+) = 8638640/311781 « 27.7074 > 12.
Similarly, we verify that V- is a negative 4-witness with 7 { V Z H Q G^SVJ) =
00 > 12. Due to L e m m a 24 the set S cannot be forcing.
CHAPTER 4. SECOND-ORDER METHOD 31
( 1061 1052 - 4 8 3 2016 \
419 356 363 1152
- 9 1 - 1 0 0 669 288
419 356 363 1152
533 92 525 1152
419 356 363 1152
- 9 1 - 1 0 0 669 288
419 356 363 1152
y 1061 1052 - 4 8 3 2016 /
Figure 4.1: Jacobian D = D0G^S : R 9
^ 4
for S = {1234,1324, 2143,123}. The
rank of the Jacobian is 3 and vector w = (1,4/5, 3/5, —4/5)T
spans the kernel
of DT
.
1 7 - 5 - 9 - 5 - 2 0 21 - 9 21 27 \
- 5 7 - 5 31 - 5 - 1 7 - 3 - 9 21
- 9 - 5 7 - 3 28 - 5 3 - 3 - 9
- 5 31 - 3 7 - 5 - 9 - 5 - 1 7 21
- 2 0 - 5 28 - 5 7 - 5 28 - 5 - 2 0
21 - 1 7 - 5 - 9 - 5 7 - 3 31 - 5
- 9 - 3 3 - 5 28 - 3 7 - 5 - 9
21 - 9 - 3 - 1 7 - 5 31 - 5 7 - 5
V 27 21 - 9 21 - 2 0 - 5 - 9 - 5 7 /
Figure 4.2: Hessian H = H^GltS • R 9 x 9
for S = {1234,1324, 2143,123}.
CHAPTER 4. SECOND-ORDER METHOD 32
v+v!
V+HVi
Cl
0 -29050
-3320 -21580
58100 -32370
3320 -21580
0 -34860
-3320 -21580
-58100 -32370
3320 -21580
0 -29050V
/ 2046780
C2
C3
0
0 2066700
-20750
39010
0
39010
0
-39010
0
-39010
20750
0
0
0 2092845
-36485 \
-14084
28259
-14084
43202
-14084
28259
-14084
-36485 )
0 \
0
00
0 0 0 2084127 J
( 7170071200 0 0 0 \
0 23077461100 0 258778230
0 0 135180091400 0
V 0 258778230 0 145431644139 /
Figure 4.3: The positive 4-witness V+ for S = {1234,1324,2143,123} with
n = 4, diagonal dap 7+ = 8638640/311781 « 27.7074, C l = 83000"1
, c2 =
2075000"1
, and c3 = 1102240000000"1
.
CHAPTER 4. SECOND-ORDER METHOD
V-Vl
V-HV1
Cl
(••2
C3
/ -66 12 0 0
- 1 8 - 4 50 50
0 -45 6 0
- 1 8 - 4 -50 -50
0 74 0 0
18 - 4 50 -50
0 -45 - 6 0
18 - 4 -50 50
\ 66 12 0 0 )
/ 5004 0 0 o \
0 4939 0 0
0 0 5036 0
0 0 0 5000 /
-21150 0 0 0 \
0 -20097 0 0
0 0 -20282 0
0 0 0 -10000 /
Figure 4.4: The negative 4-witness V- for S = {1234,1324, 2143,123} with
n = 4, diagonal dap 7_ = +oo, a = 100"1
, c2 = 5000"1
, and c 3 = 400000"1
.
Chapter 5
Profiles of Forcing Sets
In this chapter, we systematically investigate all possible four element permutation
sets, based on the order profile of the permutations in the quadruple.
Formally, let profile of a set S C S be the vector (|7r|)^ where the permutations
in S are ordered so that IT < a if \a\ < \ir\ or IT and a are of the same size and
7r is before a i n the lexicographical ordering of S|C T |; the profile vector is thus
non-increasing. Throughout this section, we for v £ MS with support of size m
use enumeration (ai)^ of the set supp v according to the just defined ordering,
i.e., <7; < <7j if and only if i < j, and use vt := va. for every i £ [TO].
We start by describing necessary condition on the shape of the profile of a
forcing set, namely we discuss result shown in [19] that implies that any profile
of a forcing set S £ S^4
' needs to be of the form (fci, fci, fo, ^3); where ki = k\
or ki = k\ — 1. We review a rephrasing of the argument, obtaining lemmas that
are needed in what follows.
L e m m a 25. Let v £ MSfc be a superpermutation, where all permutations in
the support are of size k and let u £ K f e _ 1
. If Tvu = 0, then AvE>kDkU = 0.
Moreover, if u = is a basis vector, then AvBkei = 0.
Proof. For the proof, let D = Dk, B = Bk, and c = Ck as defined i n Section 3.1.
Let u £ Mk
~1
be a non-zero vector (for otherwise the claim follows immediately)
such that Tvu = cDT
BT
AiyBDu = 0. Then BT
AvBDu = 0 as c ^ 0 and
D = DT
is a linear isomorphism. It follows that AvBDu £ ker BT
= M.j and
thus AvBDu = aj for some scalar a £ R. A s j £ M f c
is an eigenvector of both
Av and A?, we have jT
AvBDu = ( X ] ™ p p
" va)jT
BDu = 0 as jT
B = 0, and
jT
AvBDu = jT
aj = ak. Thus a = 0 holds and consequently AvBDu = 0 for
u / 0. If u = ej, simply note that £>ej = cfei for some non-zero scalar d by
definition of D. •
Let ^fc be an operator on matrices M f c x f c
which "horizontally flips" their
matrix representation in the standard basis, i.e., the operator 'I'fc can be seen as
precomposition by the permumation matrix associated to tpk = (k, k — 1 , 1 ) £
34
CHAPTER 5. PROFILES OF FORCING SETS ;sr>
§fc so that (^feM)ej = MA^kei = Mek-i+i for every i £ [k] and every matrix
M e R k x k
.
L e m m a 26. Let v = v\o~\ + V2O2 with permutations ai,a2 £ §fc, non-zero
scalars 1/1,1^2 £ R \ { 0 } , and singular. Then \v\\ = \i>2\- Moreover, HTvek-\ =
0, then V2 = (—l)f c
^i, ^kAp = (—\)h
Ap and if k is even, 02 = o~iipkProof.
For the proof, let D = Dk, B = Bk, and c = Ck with fc = |<7i| = |o"21 as
defined in Section 3.1. If Tv is singular, then there is non-zero vector u £ K f c _ 1
such that Tvu = 0. B y Lemma 25, there exists a non-zero vector w such
that AvBw = 0. A s B is injective, this implies that there exists a non-zero
vector v such that 0 = Avv = v\Aaiv + V2A<72v from which it follows that
|^i^4C T 1 w|| = 11^2^40-2^11 and consequently that \v\\ \\v\\ = \v2\ IMI as permuting
coordinates of v does not change its norm. The fact that o ^ 0 shows \i>i \ = l ^ l Now
assume that Tveu-\ = 0. B y Lemma 25, we have that AvBkek-\ =
0, i.e., we obtain the equality v\AaiBkek-\ = - ^ ^ B t e / t - i . Viewing the
equality coordinate-wise, we obtain that it is true for every I £ [k] that
which together with \v\\ = \i>2\ implies that
fc-1 \ / k - 1
and thus either a1 ~1
(l) = 02 1
(I) or a^"1
(l) = 1 + k — a1 ~1
(l). A s o\ ^ 02, we
have that there exists I such that <T^~1
(I) ^ o"f1
(0 and consequently <T^~1
(I) =
1 + k — a1 ~1
(l). Returing to 5.1 with this choice of I, we see that
s g n ( ^ 1 ) s g n ( ^ 2 ) ( - l ) 1 + < 7
i " 1
W + ^ " 1
« = s g n ( ^ ) s g n ( ^ 2 ) ( - l ) f c
= 1
from which we conclude that v\ = (—l)F C
^2- Finally, our aim is to show that
^kAv = ( — l ) k
A v for every k and that 02 = cii^k if k is even. We start
with the latter. If k is even, we see that there is no I £ [k] such that a\ 1 }
(Z) =
o\ 1
' (0:
otherwise, returing to 5.1 with such I shows that sgn(^i)sgn(^2)(—1) =
1, contradicting v\ = (—l)F C
^2 = V2- A s such, we have <T^~1
(I) = 1 + k — a f 1
(I)
for every I and so ff2
_1
= ipkO'i1
which in turn implies 02 = criipk- For k even,
we have
^ k A v = 1>k(viAai + VXAa^A^h) = ViAriAhfc + " l A r i = Av.
Let fc be odd. If I £ [fc] is such that <r1~1
(l) = a^~1
(l), then
ef{^kAv) = {vieT
a-i{l) - Vlel-1{l))A^k = QA^k = 0 = {-l)ef Av.
If I is such that a f 1
(I) = 1 + fc — a^"1
(l), then
= {-l)efAv.
As such, we in both cases have that ^kAv = ( — l ) k
A v . •
CHAPTER 5. PROFILES OF FORCING SETS Mi
The following lemma can be deduced from Lemma 13 and proof of Lemma
15 i n [19].
L e m m a 27 ([19]). Let v £ MS with supp v = {<7i, ...,am} for m > 3 such that
Wi\ > \<T2\ > ... > k m | and Pv = 0. Then = \a2\and \a3\ £ {|ai|, |crx | - 1}.
Proof. Let = fc. Note that TC T 1 is a matrix of rank fc — 1: let u £ ]Rf c _ 1
be
a vector such that TC T 1 w = 0, then by Lemma 25 it holds that AaiBkDku = 0
and so u = 0 as AaiBkDk is an injective linear map. A s Tai has full rank,
the first row contains non-zero value, i.e., there exists j £ [fc — 2]o such that
(a(k
~2
^ ft | P a i ) 7^ 0. Assuming \a2\ < \<TI\, we get that polynomial Pv — v\P<71 is
in each variable of degree at most k — 3 which in turn implies that the polynomial
Pv = Pv — v\Pai + v\Pai cannot be zero, contradicting the assumption of the
statement.
For contradiction, assume |o"31 < |<7i| — 1 = \a2\ — 1. Let p = v\<j\ + v2a2.
Due to argument similar to the one above, we have that Pp = v\Pai + v2Pa2
has no monomials with variable of degree at least k — 3, i.e. we have that both
Tpek-i = 0 and Tpek-2 = 0. Lemma 26 implies that \i>i \ = \v2\ and Lemma 25
implies that ApB^eu-i = ApBkek-2 = 0. Let i £ [k] be an integer for which
a = <r1~1
(i) cr2 ~1
(i) = &, then ef Ap = v\e^ + i>2ef. A s \i>i \ = \i>2\ we have that
\e^Bkek-i \ = \elBkek-i \ and \e^Bkek-2 \ = \e^Bkek-2\ which by definition of
Bk implies (k
aZ\) = (Izl) and {k
aZ\) = (k
bZf) which together with a ^ b leads
to a contradiction. •
Throughout what follows, we need to enumerate all possible sets with given
profile. T h e following lemma shows that we need only to consider sets modulo
action of the dihedral group D4. Let D4 be the group of symmetries of a square,
formally given by presentation (a, {3 | a 4
= ft2
= 1, a/3 = / 3 _ 1
a _ 1
) . There is
a natural action pn : D4 —> Aut(M™x
™) on the space of real square matrices
which "horizontally flips" the matrix under /3, i.e., p„(f3) := and rotates
the matrix anti-clockwise by 90 degrees under a, i.e., pn(a)(M) := {^nM)T
.
Note that the subset of permutation matrices is invariant under this action. To
define action Q : D4 —> Aut(S), we send g £ D4 to a map which sends IT to
the permutation associated with the matrix p^(g)(An). We extend this action
to m-element permutation sets § ( m
' and the space of superpermutations MS
naturally. From now on, we use gir, gS, and gv to denote C(s)(7r
); C{g){S)i and
CCsX").
L e m m a 28. Let S be a finite set of permutations and let g £ D4 be a dihedral
group element. Then S is forcing if and only if gS is.
Proof. Let us show that d(a,ir) = d(ga,gir). Let k = \a\ and n = \ir\. To
show d(a, 7r) < d(ga,gir) it is enough to construct an injection from the set
A = {P £ [n]W I n\P = a} to the set B = {Q £ [ n ] ^ | (gn)\Q = ga}, where
the other inequality holds by considering d(ga, gir) < d(g~1
ga,g~1
gir) = d(a,ir).
Let 31 = /3 = /3'1
, then map P e A to Q = l + n - P = {l + n - p}£:
the map is clearly an injection and {PTT)\Q = P{ir\p) = P& as desired. Let g2 =
CHAPTER 5. PROFILES OF FORCING SETS 37
a = 1423 aa = 4213 a2
a = 2314 o?a = 2431
0 H H H3a = 3241 afla = 1342 a2
8a = 4132 o?Ba = 3124
Figure 5.1: Orbit of permutation a = 1423 under the action of dihedral group
a/3 = / 3 _ 1
a _ 1
, i.e., g2 is the group element sending IT to 7 r _ 1
. To construct the
injection, map P £ A to Q = ir(P) = {^(p)}p • We need to show that Q £ B. A s
7r|p = a it holds that 7r(Pj) = 7r(P)a (j) with (P»)[f c
' being the enumeration of the
set P C [n] under the natural order and similarly for enumeration (7r(P)j)[f e
' of
the set 7r(P) C [n]. Consequently, it holds that 7r_ 1
|7 r (p) = a - 1
as 7r_ 1
(7r(P)i) <
7r_ 1
(7r(P)j) holds if and only if 7r_ 1
(7r(Pc r -i(i))) < 7r_ 1
(7r(Pc r -i(j))) which holds
if and only if P^-i^ < Pa-i^ which holds if and only if <r_ 1
(i) < a _ 1
( j ) . A s
any g £ P/4 can be expressed as string of g\ and g2, e.g., a = a - 1
= 3251 and
(3 = = g±, the general claim follows by transitivity of <.
Assume that S is forcing. To show that gS is forcing, let IT, be a convergent
sequence so that for every ga £ gS it holds that
0 = d(ga,ir.) - dp(ga) = lim d{ga,-nn) - dp{ga) = l i m d{a,g~L
-KN) - dp(a),
where we use that dp(ga) = l/\ga\l = 1/|<T|! = dp(a). The equality together
with the fact that S is forcing implies that g - 1
7 r . is quasirandom, which in
turn implies that for every r £ § 4 , we have d(r, g~1
ir,) = 1/24. A s §4 is
invariant under action of P 4 , we have that for every r £ S4 it holds that
d(g(~^T, g^^n,) = d(r,7r.) = 1/24. Thus due to Theorem 4, the sequence
7T. is forcing as desired. •
Thus from now on, we work with sets of orbits instead of the individual sets.
As such, any time a concrete set S is mentioned as dependent and or possibly
forcing, reader should think of its whole orbit.
Finally, let us make a simple observation here so that we do not repeat it in
proofs which follow. If S is a minimal forcing set, S does not contain the set
for any k £ N : due to law of total probability, we have d{a, fi) = 1 which
CHAPTER 5. PROFILES OF FORCING SETS 38
implies that for any a £ Sfc it holds that d(a, fx) = 1 — J ^ * ^ 0
^ a n
d consequently
it holds that if Gg^^fi = 0, then G§kfi = 0 holds; this contradicts the minimality
of S. A s no collection of three permutations is forcing, this immediately
implies that any four-element forcing set S does not contain permutation of
order one or two permutations of order two.
We are ready to show that none of the sets in T>+ from Theorem 14 is forcing.
Theorem 29. Let S be a set of four permutations that are support of a superpermutation
v with non-vanishing constant fuzzy cover, i.e., S is an element of
the set T>+. Then S is not forcing.
Proof. Let S £ X>+. B y Theorem 14, we know that S £ S% S £ S^4 )
, or S is
(up to action of the group D4) one of
(1234,4321,123,12), (1234,4321,123, 21),
(1324,4231,123,12), (1324,4231,123, 21),
(2143, 3412,123,12), (2413, 3142,123,12),
(1234,4321,123, 321), (1324,4231,123, 321),
(2143, 3412,123, 321), (2413, 3142,123, 321),
(12345, 52341, 2143,321), (12345, 52341, 3412,123),
(12435, 52431, 2143,321), (12435, 52431, 3412,123),
We denote the last set £. A s sets S £ S44
' are not forcing by Theorem 4, we
only need to consider the first and the third case.
Let S £ S^g with dependence witness v. B y Lemma 27, we know that S
contains two permutations of size three and as S 3 is not forcing, we know that
\S n S 3 1 < 3. A s S cannot contain two permutations of size two or permutation
of size one, profile of S is (3, 3, 3, 2). Enumerating all such sets using computer,
we determined that if S is dependent, it is (up to action of D4) one of the
following
(123,132,213,12), (123,132,213,21), (123,132,321,12),
(123,132,321,21), (123,231,312,12), (123,231,312,21).
For the sets above and set £ we use the second-order method to conclude
that none of the sets mentioned are in fact forcing; the certificates can be found
in Appendix D . •
We conclude this section by stating corollary, which allows us to assume that
forcing sets have vanishing fuzzy covers.
Corollary 30. Let S be a forcing set of size four with dependency witness
v £ MS of order k. Then F^k)
= 0.
(k)
Proof. B y L e m m a 13, we know that if v is of order k, it holds that F„ = cj
for some real number c £ EL Assume c > 0, then S belongs to set T>+ and thus
it is not forcing by Theorem 29. We conclude Fv = 0. •
CHAPTER 5. PROFILES OF FORCING SETS
5.1 Homogeneous Sets
We first look at sets where all permutations are of order k £ N . A s the set of
all permutations of size k for k < 3 is known not to be forcing and sets S £ S^4
'
are known not to be forcing by Theorem 4, we focus on regime k > 5. Let
S £ S^4
' be a forcing set for k > 5, then as Av = c j for some c £ R and the
number of non-zero elements of any row in Av is bounded from above by the
size of the support of v, we conclude that F^ = Av = 0. The following lemma
serves as a necessary condition on set S £ S^4
' being forcing which we use to
restrict the space of possible forcing sets so that their enumeration becomes
computationally feasible even for larger values of k. Before doing so, we need
the following definition.
Given a permutation r : Sfc, it defines a map r— : Sfc —> Sfc defined by
T(<T) = TO which we extend to map r— : —> S^' and r— : MSfc —> MSfc. Note
that if Av = 0 for some v £ MSfc, then for any r £ Sfc we have that ATV = 0.
L e m m a 31. Let v £ Sfc be an 5-supported superpermutation for some S £ S^4
'
such that Av = 0. Then there exists T £ Sfc and ordering s : [4] —> S such that
the set 5 ' = TS, ordering s' = TS of set 5", and superpermutation v' = TV have
the following properties:
(i) Av, = 0,
(ii) = i d f c , s'(2)(l) = 1, and
(Hi) = - i / , ( 2 ) = i / , ( 3 ) = - 1 ^ , ( 4 ) .
Moreover, set 5 ' with ordering s' and properties (i), (ii), and (Hi) is determined
by s'(2) and s'(3).
Proof. Let ^ £ Sfc be an 5-supported superpermutation with = 0. Given
i £ [k] let i * : 5 —> [k] be a map sending permutation a £ S to a (i) £ [fc] so
that keri* represents the partitioning of set S into sets Ci for £ £ [k] with the
property that for o~\,o~2 £ it holds that o~\(i) = 02(2) = I.
Notice that as Av = 0, we have that for every i £ [k] the partition ker i * does
not contain singleton sets: assume it does so that there exists i £ [k] and a £ S
such that a(i) ^ o"'(i) for all a' £ 5" \ {a} which together with ^ 0 implies
that (^4„)o-(i),i 7^ 0 contradicting Av = 0. There are only two types of partitions
of four elements without singletons, namely matching with two classes of size
two and the trivial partition with single class containing all four elements.
Let G be a graph with vertex set S and let o~\ ~ 02 be an edge if and only
if <7i 7^ (72 and there is i such that {o"1,02} £ keri* (note that this implies not
only that ai(i) = 0-2(1) but also that az{i) 7^ o"i(i) and 0-4,(1) 7^ cri(i)). We show
that G = C4. First, let us show that from this the claim follows.
First, an edge o\ ~ 02 implies that va i = —va2 which implies that there
is ordering of the cycle s : [4] —> S such that Vs(i) = — Vs(2) = v
s(3) = ~^s^)B
y discussion above, it holds that ker 1* is either a matching in which case we
CHAPTER 5. PROFILES OF FORCING SETS 40
choose a' £ Sfc so that {3(1), cr'} £ k e r l * , or k e r l * is trivial i n which case we
choose a' = s(2); i n both cases we have s(l) ~ a' and s ( l ) ( l ) = <T'(1). N O W
choose one of the two orderings of the cycle s so that s(l) = s(l) and s(2) = a'
by which s ( l ) ( l ) = s(2)(l).
Let T = s ( l ) _ 1
, let 5" = TS be the transformed set with ordering s' = TS for
which it holds that s'(l) = lfc and s'(2)(l) = s ' ( l ) ( l ) = 1, and set z/ = TV SO
that ^g/(!) = —v
's'(2) =
^«'(3) =
~~ ^s'(4)Let
u s s n o w
that given s'(2) and s'(3),
we can reconstruct s'(4). This is immediate as by property (Hi) and property
(i) we have that A s , { i ) = As,{1) - As,{2) + As,{3) = Aidk - As,{2) + As,{3).
Finally, we prove that G = C4. The graph G cannot contain odd cycle, for
otherwise the permutations on the odd cycle need to have zero coefficient in
v which contradicts the fact that S = supp v. Let us show that for degrees
we have d(a) > 2 for all a £ S; this concludes the proof as there is a single
bipartite graph on four vertices with minimum degree 2, namely -^2,2 — C4.
Assume that permutation a £ S is isolated: this implies that keri* is trivial for
all i £ [k] which implies that all the permumations are the same permutation
which is clearly a contradiction. Assume d(a) = 1 and let a' be a neighbour of
a in G. Observe that this implies a = a' which is a contradiction: let i £ [k],
then keri* is either a matching in which case {<r,a'} £ keri* and a(i) = a'(i)
or the kernel is trivial i n which case we have the same conculsion. •
Proposition 32. Let k < 5 let S £ S^4
'. Then S is not forcing.
Proof. A s S; is not forcing for I < 4 and any set S £ S^4
' is not forcing by Theorem
4, let k > 5. Given two distinct permutations 0 2 , 0 3 £ Sfc of which neither
is the identity permutation, let S{o~2iO~z) be the set {idfc,0-2,03,0-4} if matrix
M = A-1(\k — Aa2 + Aa3 is a permutation matrix associated with permutation
04 £ S5 which is different from idfc, o~2 and 03, and let S(a2iO~z) be the empty
set otherwise. Let T(<72,<73) = { r . S ' ^ , 0 3 ) | r £ Sfc}. I claim that
Assume that S £ Sf c is a forcing and let v be an 5-supported superpermutation
with Av = 0. Then by L e m m a 31, there exists r such that S' = TS =
{idfc,<72,03,0-4} and Aak— Aa2+Aa3— A a i = 0. This implies that S1
= S{o~2iO~z)
and consequently S = T _ 1
5 " £ T{u2,o'z)Let
k = 5. We computationally enumerate all elements of the right-hand
side of (5.2) which produces 159 sets in total. For these we use the second-order
method; the list of the 159 permutation sets and their certificates can be found
in Appendix D . •
s1
{S £ S[V
I S is forcing} C (5.2)
CHAPTER 5. PROFILES OF FORCING SETS 41
5.2 Sets with One Exceptional Permutation
Next, we show that sets with profile p(k, I) = (k, k, k, I) for k < 6 and I < k are
not forcing. We start by considering regime 4 < k < 6 in which we show that
all p(k, Z)-sets are independent and thus cannot be forcing by Proposition 9.
L e m m a 33. Let a £ for I > 3, then F„+1
^ has at least three non-zero values
in every column but the first and the last, i.e., the vectors F&+1
^have for
2 < i < I support of size at least three.
Proof. F i x 2 < v < I. Expanding the definition of F&+
^ gives
It follows that {Fil+
^)u^v is non-zero if and only if there exists j £ [I]
for which all binomial coefficients i n the j-the summand are non-zero. After
considering supports of the individual binomial coefficients, we get that
(.F'i'+ 1
')
)U i „ is non-zero if and only if there exists j £ [I] such that v £ {j,j + 1}
and u £ {a(j),a(j) + 1} or differently, if j = v and u £ {a(v),a(v) + 1} or
j = v — 1 and y £ {a(v — 1), a(v — 1) + 1}; note that as 2 < v < I both cases
do occur. Consequently, {Fil+
^)u^v is non-zero if u is an element of the set
Yv = {a(v),a(v) + l,a(v — l),a(v — 1) + 1}. A s Yv is a subset of [/ + 1], it
remains to show that the set Yv contains at least three elements, but this is
immediate as a(v) ^ a(v — 1). •
(k)
L e m m a 34. Let a £ S; for I > 2, then F& for k > I + 1 contains a column
with support of size at least four.
Proof. Due to similar analysis as i n L e m m a 33, we see that (F^k)
)UtV > 0
if and only if there exists j £ [I] such that v £ {j, + k — 1} and u £
{<r(j),a(j)+k—I}. Notice that if {F^)u>v is non-zero for some pair u, v £ [k],
then (Fak+1
^)u,v is also non-zero. Thus, it is enough to consider the case
k = I + 2. Choose v = 2 so that ( i ^ + 2 )
) „ , 2 > 0 if u £ {a(j), a(j) + 1, a(j) + 2}
for some j £ {1,2}. This in turn implies that there are at least four distinct
values of u such that {Fa+2
^)u^ is non-zero as <r(l) ^ o"(2). •
L e m m a 35. Let a £ S; for 4 < I < 5, the submatrix spanned by all columns
except the first and the last contains four distinct non-zero values, i.e., for linear
map U : which sends to ej+i, the matrix of Fa+1
^U contains at
least four distinct non-zero values.
Proof. Here, we unfortunately have no better method than to enumerate all
permutations of S4 U §5 up to action of group D4 and find the values manually.
We list the values i n Appendix B . •
CHAPTER 5. PROFILES OF FORCING SETS 12
Proposition 36. Let k < 6 and let S be a (k, k, k, l)-set of permutations for
I < k. Then S is not forcing.
Proof. A s minimal forcing set cannot contain a permutation of order one, we
can assume I > 2. B y Corollary 30, we assume F^ = 0. Assume k > I + 2,
(k)
then as every column of F„JV = A v - V i < J i has support of size at most three
(k)
and P^4 o-4 has a column whose support has size at least four by L e m m a 34, their
sum cannot be the zero matrix, a contradiction.
As such, assume k = 1 + 1. For k £ {3,4}, there are only seven dependent
sets (up to action of D4) with profile (4,4,4, 3), or (3, 3, 3, 2), namely
(123,132,213,12) (123,132,213,21) (123,132,321,12)
(123,132,321,21) (123,231,312,12) (123,231,312,21)
(1234,1324,2143,123)
which we resolve using the second-order method; their certificates can be found
in Appendix D .
Let k £ {5, 6}. We have F^ = vi~1
{v\Aai +i>2Acr2 +v^Aa3). B y Lemma 33,
(k)
it holds that for every natural number 2 < i < fc, vector Fa4 ei contains three
nonzero values which implies that <ri(i), «72(2), and az{i) are all distinct and so
Fa
k
^ei contains three non-zero values, namely v a i , v a 2 , and This in turn
implies that the submatrix of Fa
k
^ spanned by all columns but the first and
the last contains only three named values. This contradicts the conclusion of
Lemma 35 as I = k — 1 implies 4 < I < 5. •
5.3 Matched Profile
In this Section, we consider permutation sets with profile m(k, I) = (k, k, I, I) for
I < k. B y Lemma 27, we know that any set S with profile m(k, I) for I < k — 1
cannot be forcing and thus focus on case I = k — 1.
Lemma 37. Let k > 5 and let S be a forcing set with profile (k, k, k — 1, k — 1),
together with a dependence witness v. Then k is odd, ^2 = —v\, and v4 = —v^.
Proof. Let v = £ + rj with £ £ MS>k and rj £ MSfc_i. A s Pv = 0, and consequently
P^ = —Pv, it holds that T^ek-i = —T^ e^-i = 0 and is singular with
kernel element ek-i- B y Lemma 26, it holds that coefficients i n £ are related
by v\ = (—l)F C
^2 and 'I'fcAj = (—l)k
A^. A s such, matrix A^ has rank at most
[fc/2j < k — 3 for k > 5: if k is even, the claim is immediate by horizontal
symmetry, and for k odd, the claim follows from horizontal antisymmetry and
Aje
|-fc/21 = * f e ^ e r f e / 2 ] = -A^eik/2-] = 0.
As such T^ and T^k 2
' both have rank of at most k — 3 and thus Tn is
singular. B y Lemma 26, we have \v%\ = \v4\, i.e., v4 = (—l)x
vz f ° r
some x £ N .
CHAPTER 5. PROFILES OF FORCING SETS 43
B y Corollary 30, it follows that Fo = 0, from which together with the
discussion above, we conclude
V l { A a i + (-l)k
Aa2) = -^{F™ + (-l)*i*J>). (5.3)
As j is an eigenvector of Aa with eigenvalue one for any a £ Sfc, and recall that
j is an eigenvector of F^1
with eigenvalue (k — l)!/(fc — 2)! = k — 1 for a £ Sfc_i,
by applying both sides of 5.3 to j , we obtain the equality
V! (1 + ( - l ) f c
) j = - 1) (1 + (-l)x
)j. (5.4)
If k is even, then the equality implies 2vi = —vz(k — 1)(1 + (—l)x
) which
implies that x is even as both v\ and v% are non-zero. Thus we conclude v^ = v%.
We show that this conclusion leads to a contradiction. Assume it to be true,
then
V l { A a i + A a 2 ) = - ^ { F ^ + F ^ )
holds but the left-hand side is a matrix where each column has support of size
at most two, whereas the right-hand side has a column with support of size at
least three by L e m m a 33 and the fact (F^)ij > 0 for all i,j £ [k], i.e., the size
(k) (k)
of the support of a column in F„3' + i v 4 is at least the size of the support of
the column in the summands.
Let k be odd. Then by 5.4 it holds that x is odd as i>±, ^3, and k — 1 are
non-zero. A s such = —i>3 which concludes the proof. •
The above gives us a computationally checkable necessery condition for
(k, k, k — 1, k — l)-set S with k > 5 to be forcing. Namely, if v is the dependency
witness of S, it has to hold that matrices T^_^2 and T ^ - a l have to
be linearly dependent as i>iT^k
_^2 + v^T^^)^ = T^k
~2
^Pv = 0. Before moving
to the main proposition of this section, we note that due to Example 15, this is
the best result possible using only dependence condition.
Proposition 38. Let k < 6 and let S be a (k, k, I, l)-set of permutations for
I < k. Then S is not forcing.
Proof. A s S does not contain sets §1 and §2, we can assume I > 3 and by
Lemma 27, we can assume k = I + 1. For k > 5, it holds that k has to be odd
by L e m m a 37 and so it suffices to solve cases k £ {4, 5}. Let S be a forcing
set with profile (k, k, k — 1, k — 1) and dependency witness v whose fuzzy cover
is the zero matrix by Corollary 30. Then it is (up to action of D4) one of the
following:
(1234,4321,123, 321) (1324,4231,123, 321)
(2143, 3412,123, 321) (2413, 3142,123, 321)
(12345,14325,1234,1324) (12345,14325,4231,4321)
(12543,14523,1234,1324) (12543,14523,4231,4321)
(25314,41352,2413,3142).
CHAPTER 5. PROFILES OF FORCING SETS 44
For k = 4, we used computer to enumerated all sets with the appropriate profile
(up to action of D4) and checked dependence of the system T$ as described
in Chapter 3 to exclude all but the four mentioned sets. For k = 5, we used
computer to enumerate all sets with appropriate profile (up to action of D4) and
checked whether the matrices A = T ^ * _ ^ and B = T j * _ ^ are linearly dependent.
For the sets above, we use the second-order method and the certificates
can be found in Appendix D . •
5.4 And the Rest
Unfortunately, for the most general case, I found no better approach than to
computationally enumerate all of the sets.
Proposition 39. Let k\ < 5 and let S be a (fci, hi, k2, k^-set of permutations
for kz < k2 < k\. Then S is not forcing.
Proof. A s S i cannot be a subset of a minimal forcing set, we assume ks > 1
and as a consequence k\ > 4. Due to L e m m a 27, we can assume k2 = k\ — 1.
We used computer to enumerate all sets with profiles (5, 5,4, 3), (5, 5,4, 2), and
(4,4, 3, 2) and checked dependence of system the T$ as described i n Chapter 3
to conclude that if set S with one of the mentioned profiles is dependent, it is
(up to action of D4) one of
(12345, 52341, 2143,321), (12345, 52341, 3412,123),
(12435, 52431, 2143,321), (12435, 52431, 3412,123),
(1234,4321,123,12), (1234,4321,123, 21),
(1324,4231,123,12), (1324,4231,123, 21),
(2143, 3412,123,12), (2143, 3412,123, 21),
(2413, 3142,123,12), (2413, 3142,123, 21).
We use the second-order method to conclude that none of the sets mentioned
are in fact forcing; the certificates can be found i n Appendix D . •
Proof of Theorem 2. Let S be a forcing set with profile (k\, k2, ks, £4) with k± <
kz < k2 < k\ < 5. B y Lemma 27 we have that k2 = k\ which together with
Proposition 32, Proposition 36, Proposition 38, and Proposition 39 shows the
statement. •
Chapter 6
Conclusion
The prime objective of this thesis was to improve our understanding of the
boundary between systems of pattern densities that do and those that do not
force quasirandomness i n convergent permutation sequences. In [9], authors
show that any forcing superpermutation with positive coefficients needs to have
a support of size at least six. In the same work, the authors conjecture that
this is true even without constraints on the coefficients, and authors in [17]
strengthen the conjecture to say that any forcing set needs to contain at least
six permutations; note that a set attaining the bound is known and can be found
in [9].
Conjecture 40. There exists no quasirandom-forcing set of size at most five.
In this direction, we contribute i n the form of Theorem 2, by showing that
sets of four small permutations cannot force quasirandomness. In this work,
our proofs heavily rely on computer assistance, both in the form of enumerating
sets with linearly dependent gradient polynomials and computing the secondorder
witnesses as described in Chapter 4. It would be of great value to replace
our proofs with "human" proofs; those not relying on any computer-obtained
witnesses.
The first goal of future work would be to classify sets with dependent gradients,
the same way Theorem 14 classifies superpermutations with non-vanishing
constant covers. This goal extends the question posed by Crudele et al. of classifying
superpermutations whose constant fuzzy covers are vanishing. In this
direction, one may not hope to get classification in terms of a finite set due to
an infinite class of dependent sets constructed in Example 15; the same was
observed for the Crudele et al. question in their work. To achieve this, a better
understanding of fuzzy covers is of interest and more lemmas similar to those
found i n Chapter 5 are needed, e.g., controlling the shape of the coefficients,
structure of the support of fuzzy covers and sets of their distinct non-zero values.
Throughout the text, we study Hessians of discrepancy functions for pertur-
15
CHAPTER 6. CONCLUSION 16
bations of various orders, with the largest perturbation being of order eight. A t
this value, it becomes computationally difficult to produce even the symbolic
expression of the discrepancy polynomial and it is probably not practical to go
much further beyond this value. A s such, a human approach is needed, with the
aforementioned infinite class of Example 15 being a good first case to tackle.
A plausible course is to study Hessian sequences instead of the individual Hessians,
the same way the work of [19] studies the Jacobian sequence instead of
the individual Jacobians. To this end we have only very limited preliminary
results.
Bibliography
[1] M . Bucič, E . Long, A . Shapira, and B . Sudakov. "Tournament quasirandomness
from local counting". In: Combinatorica 41.2 (2021), pp. 175­
208.
[2] T . F . N . Chan, D . K r á ľ , J. A . Noel, Y . Pehova, M . Sharifzadeh, and J.
Volec. "Characterization of quasirandom permutations by a pattern sum".
In: Random Structures & Algorithms 57A (2020), pp. 920­939.
[3] F . Chung and R . L . Graham. "Quasi­random tournaments". In: Journal
of Graph Theory 15.2 (1991), pp. 173­198.
[4] F . Chung, R . L . Graham, and R. M . Wilson. "Quasi­random graphs". In:
Combinatorica 9.4 (1989), pp. 345­362.
[5] D . Conlon, J . Fox, and B . Sudakov. " A n approximate version of Sidorenko's
conjecture". In: Geometric and Functional Analysis 20 (2010), pp. 1354­
1366.
[6] J . W . Cooper, D . K r á ľ , A . Lamaison, and S. Mohr. "Quasirandom latin
squares". In: Random Structures & Algorithms 61.2 (2022), pp. 298­308.
[7] J . Cooper and A . Petrarca. "Symmetric and asymptotically symmetric
permutations". In: arXiv preprint arXiv.O8Ol.4i8l (2008).
[8] L . N . Coregliano and A . A . Razborov. " O n the density of transitive tournaments".
In: Journal of Graph Theory 85.1 (2017), pp. 12­21.
[9] G . Crudele, P. J . Dukes, and J . A . Noel. "Six permutation patterns force
quasirandomness". In: Discrete Analysis (2024).
[10] R . Glebov, A . Grzesik, T . Klimošová, and D . Kráľ. "F initely forcible
graphons and permutons". In: Journal of Combinatorial Theory, Series
B 110 (2015), pp. 112­135.
[11] W . T . Gowers. "Quasirandom groups". In: Combinatorics, Probability and
Computing 17.3 (2008), pp. 363­387.
[12] R . Hancock, A . Kabela, T . Martins, R . Parente, F . Skerman, J . Volec,
et al. "No additional tournaments are quasirandom­forcing". In: European
Journal of Combinatorics 108 (2023).
47
BIBLIOGRAPHY 18
[13] R . Hancock, A . Kadela, D . Král, T . Martins, R . Parente, F . Skerman,
and J. Volec. "No additional tournaments are quasirandom­forcing". In:
European Journal of Combinatorics 108 (2023).
[14] M . W . Hirscli. Differential topology. Vol. 33. Springer Science & Business
Media, 2012.
[15] C . Hoppen, Y . Kohayakawa, C . G . Moreira, B . Rath, and R . M . Sampaio.
"Limits of permutation sequences". In: Journal of Combinatorial Theory.
Series B 103.1 (2013), pp. 93­113.
[16] C . Hoppen, Y . Kohayakawa, C . G . T . d. A . Moreira, and R . M . Sampaio.
"Limits of permutation sequences through permutation regularity". In:
arXiv preprint arXiv:1106.1663 (2011).
[17] D . K r á ľ , J.­b. Lee, and J. A . Noel. "F orcing quasirandomness with 4­point
permutations". In: arXiv preprint arXiw.2Jj.01'.06869 (2024).
[18] D . K r á ľ and O. Pikhurko. "Quasirandom permutations are characterized
by 4­point densities". In: Geometric and Functional Analysis 23.2 (2013),
pp. 570­579.
[19] M . Kurečka. "Lower bound on the size of a quasirandom forcing set of
permutations". In: Combinatorics, Probability and Computing 31.2 (2022),
pp. 304­319.
[20] L . Lovász. L arge networks and graph limits. Vol. 60. 2012.
[21] A . A . Razborov. "F lag algebras". In: The Journal of Symbolic L ogic 72.4
(2007), pp. 1239­1282.
[22] V . Rôdl. " O n universality of graphs with uniformly distributed edges". In:
Discrete Mathematics 59.1­2 (1986), pp. 125­134.
[23] The Sage Developers. SageMath, the Sage Mathematics Software System
(Version 10.6). h t t p s : / / w w w . s a g e m a t h . o r g . 2025.
[24] T . Shifrin. Multivariable mathematics: linear algebra, multivariable calculus,
and manifolds. John Wiley & Sons, 2004.
[25] J . Skokan and L . Thoma. "Bipartite subgraphs and quasi­randomness".
In: Graphs and Combinatorics 20 (2004), pp. 255­262.
[26] A . Thomason. "Pseudo­random graphs". In: North­Holland Mathematics
Studies. Vol. 144. 1987, pp. 307­331.
Appendix A
Elements of multilinear
calculus
Let F : R™ —> Rm
be a smooth function, recall that we define DXF to be the
Jacobian matrix of F at point x £ R™ and we define HXF to be the Hessian
bilinear form of F at point x £ R™ which we define as the bilinear form associated
to Dx(y —> DyF). The main goal of this section is to derive an equation for the
Hessian of compositions of two smooth maps. I believe the equation presented
to be standard but I failed to find a suitable reference.
Throughout this section, for matrix M : R ™ X m
and i £ [TO] and j £ [n], we
write M%
j for M^j, e.g., we have DXF\ = (dFi/dxk){x). We use • to denote
any other multiplication than direct function composition or direct matrix multiplication.
That is for F : R™ -> Rm
^° and G : R™ -> R°^p
we use G • F to
denote the function which sends x £ R™ to G(x)F(x) £ R m _ i , p
.
Given a differentiable map F : R™ —> R m _ J ,
° and natural numbers k £ [n],
i £ [o], and j £ [m], we use (DxF)kl
j to denote (<9i^ /dxk)(x). Let _F : R™ —>
R m
^ ° and G : R 7 1
—>• R 0 _ i
* p
be differentiable maps, then the following holds:
3 ( G - J T , | l a ( G V F ' , ) M 3 0 » , ^ | ^ ^
&rf c ^ <9a;fc ^ <9a;fc
j
' &rf c
which for D X ( G • F ) £ £(R™, R m
" ^ ) and u £ R™ in turn implies
DX(G • F)(u) = (DxG(u))F(x) + G(x)(DxF(u)). ( A . l )
which can be seen as a version of a Leibniz rule. Using A . l , we obtain the main
result of this section. Given smooth functions F : R™ -» R m
and G : Rm
->• R°
19
APPENDIX A. ELEMENTS OF MULTILINEAR CALCULUS 50
as above and « , » 6 K " , w e have
Hx(GF)(u,v) = Dx(y ^ Dy(GF))(u,v)
= Dx{y H . {DF{y)G){DyF)){u,v)
= Dx((y^ DF{y)G) • (y ^ DVF))(u, v)
= [Dx(y I ^ DF{y)G)(u)] (DxF)v + (DF[x)G)[Dx(y ^ DyF)(u)]v
= [Dx((y I ^ DVG)F)(u)] (DxF)v + DF{x)G HxF(u, v)
= [{DF{x)(y^ DyG))(DxFu)](DxF)v + (DF{x)G)HxF(u,v)
= HF{x)G(DxFu, DxFv) + (DF{x)G)HxF(u, v),
where the second equality is due to use of chain rule, fourth is due to ( A . l ) ,
sixth is due to chain rule and the remaining equations are definitional.
Appendix B
Certificates for Four-Value
Lemma
This Appendix accompanies the proof of Lemma 35. Given a permutation
a € Sfc, we use (u, v) H> x to denote the fact that {F^k+1>>
)UtV = x. What follows
is enumeration of all a G S4 U §5 (up to action of the group D4) together with
the four non-zero values of as described in the statement of the lemma:
a -= 1234 (1 2) h+4/5, (2 2) 1—^ 2, (3, 2) H- 6/5, (3, 3) H- 8/5
a -= 1243 (1 2) h+4/5, (2 2) 1—^ 2. (3, 2) H- 6/5, (4, 3) H- 2/5
a -= 1324 (1 2) h+4/5, (2 2) 1—^ 1/5, (3, 2) H- 6/5, (4, 2) H- 9/5
a -= 1342 (1 2) h+4/5, (2 2) 1—^ 1/5, (3, 2) H- 6/5, (4, 2) 1—^9/5
a -= 1432 (1 2) h+4/5, (2 2) 1—^ 1/5, (4, 2) h+3/5, (5, 2) 1—^ 12/5:
a -= 2143 (1 2) H- 12/5, (2 2) 1—^ 6/5, (3, 2) ^ 2 / 5 , (1, 3) ^ 8 / 5 ;
a -= 2413 (2 2) h+3/5, (3, 2) 1—^ 2/5, (5, 2) 1—^ 12/5, (1, 3) ^ 8 / 5 :
a = 12345 (1 2) 1—^ 5/6, (2 2) 1—^ 17/6, (3, 2) ^ 4 / 3 , (3, 3) 1—^ 13/6:
a = 12354 (1 2) 1—^ 5/6, (2 2) 1—^ 17/6, (3, 2) ^ 4 / 3 , (3, 3) 1—^ 13/6:
a = 12435 (1 2) 1—^ 5/6, (2 2) 1—^ 17/6, (3, 2) ^ 4 / 3 , (3, 3) 1—^2/3
a = 12453 (1 2) H- 5/6, (2 2) 1—^ 17/6, (3, 2) ^ 4 / 3 , (3, 3) H- 2/3
a = 12543 (1 2) 1—^ 5/6, (2 2) 1—^ 17/6, (3, 2) ^ 4 / 3 , (3, 3) 1—^2/3
a = 13254 (1 2) 1—^ 5/6, (2 2) 1—^ 1/6, (3, 2) ^ 2 , (4, 3) 1—^ 1
a = 13425 (1 2) H- 5/6, (2 2) 1—^ 1/6, (3, 2) ^ 2 , (3, 3) H- 1
a = 13452 (1 2) 1—^ 5/6, (2 2) 1—^ 1/6, (3, 2) ^ 2 , (3, 3) 1—^ 1
a = 13524 (1 2) 1—^ 5/6, (2 2) 1—^ 1/6, (3, 2) (3, 3) 1—^ 1
a = 13542 (1 2) H- 5/6, (2 2) 1—^ 1/6, (3, 2) ^ 2 , (3, 3) H- 1
a = 14325 (1 2) 1—^ 5/6, (2 2) 1—^ 1/6, (4, 2) ^ 4 / 3 , (5, 2) ^ 8 / 3 :
a = 14352 (1 2) 1—^ 5/6, (2 2) 1—^ 1/6, (4, 2) ^ 4 / 3 , (5, 2) ^ 8 / 3 :
51
APPENDIX B. CERTIFICATES FOR FOUR-VALUE LEMMA 52
a = 14523 (1,2) H. 5/6, (2,2) ^ 1/6, (4,2) h+4/3, (5,2) ^ 8 / 3 :
a = 14532 (1,2) H. 5/6, (2,2) ^ 1/6, (4,2) ^ 4 / 3 , (5,2) ^ 8 / 3 :
a = 15342 (1,2) H. 5/6, (2,2) ^ 1/6, (5,2) ^ 2 / 3 , (6,2) i — ^ 10/3
a = 15432 (1,2) H. 5/6, (2,2) ^ 1/6, (5,2) ^ 2 / 3 , (6,2) i — ^ 10/3
a = 21354 (1,2) H. 10/3, (2,2) ^ 4 / 3 , (3,2) * 1/3, (1,3) i — ^ 5/3:
a = 21453 (1,2) H. 10/3, (2,2) ^ 4 / 3 , (3,2) * 1/3, (1,3) i — ^ 5/3:
a = 21543 (1,2) H. 10/3, (2,2) h+4/3, (3,2) ^ 1/3, (1,3) H. 5/3:
a = 23514 (2,2) ^ 2 / 3 , (3,2) ^ 7 / 3 , (4,2) ^ 2 , (3,3) ^ i ;
a = 24153 (2,2) ^ 2 / 3 , (3,2) ^ 1/3, (4,2) h+4/3, (5,2) i — ^ 8/3:
a = 24513 (2,2) ^ 2 / 3 , (3,2) ^ 1/3, (4,2) ^ 4 / 3 , (5,2) i — ^ 8/3:
a = 25314 (2,2) ^ 2 / 3 , (3,2) ^ 1/3, (6,2) i — ^ 10/3, (3,3) 3/2:
Appendix C
Implementation of the
First-order Method
Throughout the main body of this thesis, we often point to a computational
enumeration of sets S C § and computer-assisted determination of the rank of
the system T$ as described in Chapter 3. This was achieved using mathematics
software system SageMath[23] and the source code in the form of a Jupyter
Notebook can be found as an attachment f i r s t - o r d e r , ipynb. For installation
of the software, we point reader to Installation G u i d e 1
, and for guide to launching
Jupyter Notebook with SageMath, we point reader to Lauching G u i d e 2
. The
code was tested on version 10.6.
1
https://doc.sagemath.org/html/en/installation/index.html
2
https://doc.sagemath.org/html/en/installation/launching.html
Appendix D
Second-order Certificates
There are 187 needed certificates. A s such, we include them only in computer
readable form. This is done in the form of an attachment c e r t i f i c a t e s . z i p
that can be found attached to the thesis. The archive contains computer readable
files
d e p e n d e n t . t x t : file contains enumeration of all dependent sets S whose
profile is in the set {(3, 3, 3, 2), (4,4, 3, 2), (4,4, 3, 3), (4,4,4, 3), (5, 5,4, 2),
(5,5,4,3), (5,5,4,4), (5,5,5,5)};
fc1fc2fc3fc4.txt: file contains enumeration of all dependent sets S whose
profile is (fci, k$, fct);
c r u d e l e e t a l . t x t : file contains enumeration of all sets S from Theorem 29
whose resolution is needed to prove the claim.
The list contained in d e p e n d e n t . t x t is union of the lists in the other files;
other files are provided only for convenience. For each file in the list above,
there is an accompanying certification file whose suffix is _ c e r t . t x t , i.e., for
d e p e n d e n t . t x t there is a file d e p e n d e n t _ c e r t . t x t . Each line of the certification
file contains the following list of values delimited by semicolon:
1. the permutation set S for which this line is a second-order certificate,
2. natural number n which determines the function GUts whose Hessian is
being studied,
3. a diagonal gap 7+ £ Q U { + 0 0 } for matrix M+ = VjHV+ (see below),
4. a diagonal gap 7_ £ Q U { + 0 0 } for matrix M _ = VlHV- (see below),
5. the Jacobian D 0 G „ i S £ Q (
™ _ 1 )
~^4
written as a list of four gradient vectors
(D0g„,a)i,
6. a vector w £ Q 4
in kernel of (DoGn<s)T
,
51
APPENDIX D. SECOND-ORDER CERTIFICATES 55
7. a Hessian matrix H = H0Dn,s £ Q ( ™ - i ) 2
x ( « - i ) 2
,
8. a positive 4-witness V+ £ Q 4
- >
( ™ - 1
) 2
written as a list of vectors -4
' to
which F + is associated, where Vi is an element of Q ( r l _ 1
) for every i £ [4],
9. a matrix M + = V ^ i f V + £ Q 4 x 4
used for verifying the fact that V+ is a
positive witness written as a list of rows,
10. a negative 4-witness V _ £ Q 4
^ " - 1
) written as a list of vectors (fi)|4
' to
which V- is associated, where Vi is an element of Q ( n _ 1
) for every i £ [4],
11. a matrix M _ = Vi HV- £ Q 4 x 4
used for verifying the fact that V- is a
negative witness written as a list of rows.
Symbolic variables (a:i,j)'j 1
' are always (for computation of gradients and
Hessian matrices) ordered lexicographically, e.g., for n = 3 we have x±.i <
%1,2 < £2,1 < %2,2- A l l the objects are computed in field of rational numbers Q,
meaning we can run the computations exactly. The theory of the certificates
can be found i n Chapter 4 and example application can be found in Section 4.2.