UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Finite configurations in sparse sets Chan, Vincent 2014

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2014_spring_chan_vincent.pdf [ 466.96kB ]
Metadata
JSON: 24-1.0166905.json
JSON-LD: 24-1.0166905-ld.json
RDF/XML (Pretty): 24-1.0166905-rdf.xml
RDF/JSON: 24-1.0166905-rdf.json
Turtle: 24-1.0166905-turtle.txt
N-Triples: 24-1.0166905-rdf-ntriples.txt
Original Record: 24-1.0166905-source.json
Full Text
24-1.0166905-fulltext.txt
Citation
24-1.0166905.ris

Full Text

Finite Configurations in Sparse SetsbyVincent ChanB. Mathematics, University of Waterloo, 2009M. Mathematics, University of Waterloo, 2010a thesis submitted in partial fulfillmentof the requirements for the degree ofDoctor of Philosophyinthe faculty of graduate and postdoctoralstudies(Mathematics)The University Of British Columbia(Vancouver)April 2014c© Vincent Chan, 2014AbstractWe prove a result which adds to the study of continuous analogues ofSzemere´di-type problems. Let E ⊆ Rn be a Lebesgue-null set of Haus-dorff dimension α, k,m be integers satisfying a suitable relationship, and{B1, . . . , Bk} be n × (m − n) matrices. We prove that if the set of matri-ces Bi are non-degenerate in a particular sense, α is sufficiently close to n,and if E supports a probability measure satisfying certain dimensionalityand Fourier decay conditions, then E contains a k-point configuration ofthe form {x + B1y, . . . , x + Bky}. In particular, geometric configurationssuch as collinear triples, triangles, and parallelograms are contained in setssatisfying the above conditions.iiPrefacePart of Chapter 1 and Chapters 2 through 5 of this thesis were producedfrom a manuscript [7] accepted for publication in Journal d’Analyse Math-ematique:V. Chan, I.  Laba, and M. Pramanik. Finite configurations insparse sets, March 2014.The identification of the research program was made by Izabella  Labaand Malabika Pramanik. Research activities were conducted equally by allthree authors. Writing of the manuscript was conducted largely by VincentChan, with feedback and additions given by Izabella  Laba and MalabikaPramanik.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Discrete case . . . . . . . . . . . . . . . . . . . . . . . 21.1.2 Continuous case . . . . . . . . . . . . . . . . . . . . . 41.2 Notation and definitions . . . . . . . . . . . . . . . . . . . . . 91.3 The main result . . . . . . . . . . . . . . . . . . . . . . . . . . 111.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 A multilinear form for counting configurations . . . . . . . 142.1 Fourier-analytic representation of the multilinear form . . . . 142.2 Extension of the multilinear form to measures . . . . . . . . . 212.3 Counting geometric configurations in sparse sets . . . . . . . 26iv2.3.1 Existence of candidate ν . . . . . . . . . . . . . . . . . 262.3.2 Proof of Proposition 2.8.(a) . . . . . . . . . . . . . . . 302.3.3 Proof of Proposition 2.8.(b) . . . . . . . . . . . . . . . 302.3.4 Proof of Proposition 2.8.(c) . . . . . . . . . . . . . . . 313 Estimates in the absolutely continuous case . . . . . . . . . 383.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2 Almost periodic functions . . . . . . . . . . . . . . . . . . . . 423.3 Ubiquity of almost periodic functions . . . . . . . . . . . . . . 473.4 Proof of Proposition 3.1. . . . . . . . . . . . . . . . . . . . . . 523.5 Quantitative Szemere´di bounds fail for general A . . . . . . . 544 Proof of the main result . . . . . . . . . . . . . . . . . . . . . 565 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676.1 Overview of the results . . . . . . . . . . . . . . . . . . . . . . 676.2 Possible directions for future research . . . . . . . . . . . . . 686.2.1 Non-degeneracy . . . . . . . . . . . . . . . . . . . . . . 686.2.2 Valid range of m . . . . . . . . . . . . . . . . . . . . . 686.2.3 Linear configurations . . . . . . . . . . . . . . . . . . . 696.2.4 Non-linear configurations . . . . . . . . . . . . . . . . 70Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72vList of TablesTable 1.1 Summary of results on bounds for C(n, θ) . . . . . . . . . 6viList of SymbolsZ IntegersN Strictly positive integersQ Rational numbersR Real numbersC Complex numbersP Prime numbersS1 Unit circle in R2Ek k-fold Cartesian product of E#E Number of elements in set E|E| Lebesgue measure of set EM(E) Set of probability measures supported on EC∞c (Rn) Infinitely differentiable functions on Rn with compact supportS(Rn) Schwartz functions on Rnf̂ Fourier transform of the function fµ̂ Fourier transform of the measure µAt Transpose of matrix AIn×n n× n identity matrix0a×b a× b zero matrix1E(x) Indicator function on Ef−1(E) Preimage of E under fE(b|B) Conditional expectation of b with respect to sigma-algebra Bf . g f ≤ Cg for a constant Cf & g f ≥ Cg for a constant C∇ Gradientvii‖f‖Lpx Lp norm of f in the x variable‖f‖Lp(E) Lp norm of f on space E‖f‖p Lp norm of f|||x||| Distance from x to closest integerdxe Smallest integer larger than xbxc Largest integer smaller than xN (A) Null space of matrix AE[δ] δ-thickened EQε Squares of side-length ε with corners in εZ2Symk Symmetric group on k elementsid Identity permutation∅ Empty setviiiAcknowledgmentsI would like to thank my advisors, Izabella  Laba and Malabika Pramanik, fortheir constant support and assistance throughout the past four years. Theirknowledge, insight, and advice has made this work possible. I would alsolike to thank Akos Magyar for being a part of my supervisory committee.I am thankful to the National Sciences and Engineering Research Counciland to the University of British Columbia for their financial support andemployment opportunities.The UBC mathematics department, in particular the staff members,deserves credit for making my experience a pleasant one, and for all thesupport they have given me in my activities.My life has been enriched by the friends by my side, both old and new,and for that they have my heartfelt gratitude. I am deeply grateful tomy family for their affection and support. I am especially indebted to myparents, without whom I would not be.ixDedicationTo my wife, Vicki, for her support, sacrifices,encouragement, and love.xChapter 1Introduction1.1 HistoryErdo˝s [9] once made the following conjecture: for any infinite set of realnumbers F , there exists a set E of positive measure which does not containany non-trivial affine copies of F . This is an example of a larger class ofproblems, measuring a set from a geometrical point of view: one wouldlike to determine conditions on a set E which will guarantee the existenceof certain configurations in E, or in the negative direction, will ensure theabsence of these configurations. The precise meaning of this will vary, as willthe ambient space for E. For instance, we may have another fixed set F inconsideration, and ask if there is a geometrically similar copy of F containedin E; or we may ask if E contains various geometric shapes or sets of pointswhich satisfy some set of linear equations. The solution to Erdo˝s’ problemis still unknown in general, however there are many similar problems thathave been solved.In the special case when F ⊆ R consists of a decreasing sequence xnconverging to 0 such that lim inf xi+1/xi = 1 (that is, a slowly decayingsequence), Falconer [12] shows there exists a closed set E ⊆ R of positivemeasure which does not contain any affine copies of F , using a Cantor-likeconstruction. In fact, his construction is much stronger; his set E misses allbut finitely many entries of any affine copy of F . It is worth noting that if1the sequence decays geometrically fast, such as {2−i}, the result is unknown.Bourgain [6] proves that for any infinite set S ⊆ R, there exists a setE ⊆ R3 of positive measure which does not contain any affine copies ofF = S × S × S ⊆ R3, using a probabilistic method. His proof of thisresult also yields that for any infinite sets S1, S2, S3 ⊆ R, there exists aset E ⊆ R3 of positive measure which does not contain any affine copies ofF = S1 + S2 + S3, where + refers to the usual set addition.For more results concerning the case when F is a sequence, see Ariasde Reyna [1] and Miller [34], where they construct sets E of second Bairecategory; Borwein and Ditor [5], which examines the related problem when‘affine’ is replaced with ‘translated’; Komja´th [29], a generalization of Bor-wein and Ditor’s result; Bourgain [6] , which considers the case when F iscertain cross products or sum sets; and Kolountzakis [28], which gives a neg-ative result concerning almost all affine copies (in Lebesgue measure sense)rather than all copies.We will focus on the case when the configuration is finite. Althoughthe continuous case is of primary interest, the discrete case offers some richhistory and motivation for the analogous results.1.1.1 Discrete caseIn the case when the ambient space is the positive integers N, a simpleconfiguration to consider is an arithmetic progression {x, x+ y, . . . , x+ (k−1)y} where y 6= 0, called a k-term arithmetic progression. In 1936, Erdo˝sand Tura´n [11] made the following conjecture related to sets containingarithmetic progressions.Conjecture 1.1. Let k ≥ 3 be an integer and 0 < δ ≤ 1. If N is suffi-ciently large depending on k and δ, then every subset A of {1, 2, . . . , N} ofcardinality at least δN contains a k-term arithmetic progression.This notion of the set A containing a proportion of {1, 2, . . . , N} leadsus to consider the density of a set relative to the natural numbers. To be2precise, define the upper asymptotic density of a set A ⊆ N to be the quantityδ∗(A) = lim supN→∞#(A ∩ {1, . . . , N})N,where #S denotes the number of elements of S ⊆ N. A seemingly weakerbut equivalent statement to Conjecture 1.1 is as follows:Conjecture 1.2. Let E ⊆ N be an arbitrary set withδ∗(E) > 0. (1.1)Then E contains a k-term arithmetic progression for any integer k ≥ 3.The simplest case of k = 3 was proved by Roth [35] in 1953. Later,Szemere´di [38] proved the case k = 4, and then completed the conjectureby proving the result for any k ≥ 4 in 1975 [39] in a combinatorial manner.Furstenberg [14] applied ergodic theory to provide a second proof of the casek ≥ 4, and Gowers [16] used harmonic analysis and introduced higher orderFourier analysis to prove this case. Furstenberg and Katznelson [15] proveda multidimensional variant of Szemere´di’s Theorem.A set can fail to have 3-term arithmetic progressions even if (1.1) failsjust barely; Salem and Spencer [37] showed that for large N , there exists asubset A ⊆ {1, 2, . . . , N} of cardinality about N1−c/ log logN which containsno 3-term arithmetic progressions, and Behrend [2] improved on this witha power of 1− c/√N in place of 1− c/ log logN on N . However, there arecases when (1.1) fails for the set E, yet E still contains k-term arithmeticprogressions, so long as E is sufficiently random in some sense. The primenumbers P have an upper asymptotic density of 0, yet Roth/Szemere´di-type results still apply. Define the relative upper asymptotic density of a setA ⊆ N relative to a set B ⊆ N with A ⊆ B to be the quantityδ∗B(A) = lim supN→∞#(A ∩ {1, . . . , N})#(B ∩ {1, . . . , N}).The analogous result is:3Theorem 1.3. Let E ⊆ P be an arbitrary set withδ∗P(E) > 0. (1.2)Then E contains k-term arithmetic progression for any integer k ≥ 3.Green [18] proved the case k = 3, then with Tao [19] proved the gen-eral case k ≥ 3. A multidimensional variant of this result was proven byTao and Ziegler [41] using a weighted version of the Furstenberg correspon-dence principle, and also by Cook, Magyar, and Titichetrakun [8] based ona hypergraph approach.In a similar vein, certain random sets probabilistically have 3-term arith-metic progressions even with 0 upper asymptotic density, as in the followingtheorem proved by Kohayakawa,  Luczak, and Ro¨dl [27].Theorem 1.4. For integers 1 ≤ M ≤ n, let R(n,M) be the probabilityspace consisting of M -element subsets of {1, . . . , n} equipped with the uni-form measure. Let 0 < δ ≤ 1. There exists a constant C = C(δ) such thatif C√n ≤M ≤ n, then with probability tending to 1 as n→∞, the randomset R ∈ R(n,M) has the property that any subset of R of cardinality at leastδ(#R) contains k-term arithmetic progression.We shall see that these results provide motivation for some of the resultsin the continuous case.1.1.2 Continuous caseA first step is to see how the measure theoretic size of E ⊆ Rn determines ifit contains particular configurations; we will use |E| to denote the Lebesguemeasure of E.Definition 1.5. (a) We say ψ : Rn → Rn is a similarity map if there existsc > 0 such that |ψ(x)− ψ(y)| = c|x− y| for every x, y ∈ Rn.(b) We say E ⊆ Rn contains a similar copy of F ⊆ Rn if there exists asimilarity map ψ such that ψ(F ) ⊆ E.4It is a consequence of the Lebesgue density theorem that a set of positivemeasure contains a similar copy of every finite set. We may ask if theconverse is true, that is, if a set E contains a copy of every finite set, must wehave |E| > 0? Erdo˝s and Kakutani [10] showed the answer to this is negative,by constructing a compact (and perfect), measure 0 set which contains asimilar copy of every finite set. Certainly not every set of measure 0 has thisproperty, but what condition on E would ensure various configurations? Toanswer this, we require some way of distinguishing between sets of measure0. In this case, we can explore how the dimensional size of a set will affectits capacity to contain or avoid configurations. There are several ways ofdefining dimension, of particular use is Hausdorff dimension.Definition 1.6. If U ⊆ Rn is a non-empty set, we define its diameter to bediam(Ui) = sup{|x− y| : x, y ∈ U}.We say that the countable collection {Ui} is a δ-cover for E ⊆ Rn if E ⊆⋃i Ui and diam(Ui) ≤ δ.Suppose E ⊆ Rn and s > 0. For δ > 0 we defineHsδ(E) = inf{∞∑i=1diam(Ui)s : {Ui} is a δ-cover of E}.We define the s-dimensional Hausdorff measure of E to beHs(E) = limδ→0Hsδ(E);clearly the limit exists. Finally, we define the Hausdorff dimension of E tobedimH(E) = inf{s : Hs(E) = 0} = sup{s : Hs(E) =∞}.Suppose F consists of three points, a triangle. Since any similar copy of atriangle preserves its angles, one question that arises is how large Hausdorffdimension can a set in Rn (n ≥ 2) have if it avoids three points forming aparticular angle θ. For ease, we say E ⊆ Rn contains the angle θ if there5exist distinct points x, y, z ∈ E such that the angle between the vectors y−xand z − x is θ, and write ∠θ ∈ E. DefineC(n, θ) = sup{s : ∃E ⊆ Rn compact with dimH(E) = s,∠θ /∈ E}.Harangi, Keleti, Kiss, Maga, Ma´the´, Mattila, and Strenner [20] give upperbounds on C(n, θ) (which they show is tight for θ = 0, pi), and Ma´the´ [32]provides lower bounds. Their results are summarized below.θ lower bound on C(n, θ) upper bound on C(n, θ)0, pi n− 1 n− 1pi/2 n/2 b(n+ 1)/2ccos2 θ ∈ Q n/4 n− 1other θ n/8 n− 1Table 1.1: Summary of results on bounds for C(n, θ)Also explored by Harangi et al [20] is the question of how large Haus-dorff dimension a set can have if it avoids not just the angle α, but a δ-neighborhood of α.If we instead fix the configuration, a simple case to consider is, like inthe discrete case, a 3-term arithmetic progression. The following theoremgives a stronger result:Theorem 1.7 (Keleti [25]). There exists a compact set in R with Hausdorffdimension 1 which does not contain any “one-dimensional parallelogram”{x, x+ y, x+ z, x+ y + z}, with y, z 6= 0.Keleti’s proof involves a Cantor-like construction: Start with the interval[0, 1] and on the mth step, each interval remaining is split into 6m intervalsof length 1/(6m−1m!), and every sixth interval is selected, but a shift isintroduced on some of the intervals in order to avoid parallelograms. It canbe seen to be of full dimension via the mass distribution principle (cf. [13]4.6). One consequence of Keleti’s result is that full dimension of a set Ein R does not guarantee existence of 3-term arithemetic progressions in E,seen by taking y = z.6As in the discrete case, where even with 0 upper density certain typesof sets can be guaranteed to contain 3-term arithmetic progressions, thereare cases where measure 0 sets must contain a 3-term arithmetic progres-sion.  Laba and Pramanik [30] show that essentially with sufficient Fourierdimension, E does contain 3-term arithemetic progressions. To make thisprecise:Theorem 1.8 ( Laba, Pramanik [30]). Suppose E ⊆ [0, 1] is a closed setwhich supports a probability measure µ with the following properties:(i) µ([x, x+ ε]) ≤ C1εα for all 0 < ε ≤ 1,(ii) |µ̂(ξ)| ≤ C2|ξ|−β/2 for all ξ 6= 0,2/3 < β ≤ 1. If α is close enough to 1 (depending on C1, C2, and β), thenE contains a 3-term arithmetic progression.In the prequel, µ̂(ξ) =∫e−2piix·ξdµ(x). The first condition is relatedto Hausdorff dimension. Indeed, Frostman’s Lemma (see [33]) says that ifE ⊆ Rn is compact, thendimH(E) = sup{α ≥ 0 : ∃µ ∈M(E) with µ(B(x, ε)) ≤ Cεα},where M(E) is the set of probability measures supported on E. Thencondition (i) implies that E has Hausdorff dimension of at least α. Thesecond condition is related to the Fourier dimension, defined asdimF (E) = sup{β ∈ [0, n] : ∃µ ∈M(E)with |µ̂(ξ)| ≤ C(1 + |ξ|)−β/2 ∀ξ ∈ Rn}.(1.3)This means (ii) implies that E has Fourier dimension of at least β. It isthus useful to discuss the relationship between the Hausdorff dimension andFourier dimension.It can be shown (see [33]) thatdimH(E) = sup{s ≥ 0 : ∃µ ∈M(E) with∫|x|s−n|µ̂(x)|2 dx <∞}.7Notice∫|x|s−n|µ̂(x)|2 dx < ∞ implies |µ̂(x)| < |x|−s/2 for “most” x withlarge norm, but this does not necessarily hold for all x. Comparing with(1.3), we see that dimF (E) ≤ dimH(E) for all E ⊆ Rn. Strict inequality ispossible, as the following example illustrates.Example 1.9. It is well-known that the middle thirds Cantor set has Haus-dorff dimension of log 2/ log 3. Let µ be the standard Cantor measure, therestriction of Hs to the Cantor set where s = log 2/ log 3. Then the Fouriertransform is given byµ̂(x) =∞∏j=1cos(3−jx),and so µ̂(3`pi) 6→ 0 as `→∞. In general, it is also true that the Cantor setsupports no non-zero Radon measure whose Fourier transform would tendto 0 at infinity [23], so has Fourier dimension 0.When equality occurs for a set E, E is said to be a Salem set ; thespheres Sn−1 in Rn are simple examples of Salem sets with dimension n−1.Deterministic Salem sets of non-integral dimension are uncommon, someconstructions are due to Kahane [21] and Kaufman [24]. Salem [36] con-structed random Salem sets, and Kahane [22] has shown that Salem setsare abound as random sets. In particular, if E ⊆ Rn is compact withdimH(E) = α < n/2, then the image of E under n-dimensional brownianmotion is almost surely a Salem set of dimension 2α. Further probabbilisticconstructions of Salem sets can be found in [3], [4], and [30].In this sense, condition (ii) above relates to a “randomness” condition,which is an analogue of Theorems 1.3 and 1.4. It should be mentionedthat although Salem sets are related to the two conditions, the conceptsare not equivalent—conditions (i) and (ii) do not necessitate equality inHausdorff and Fourier dimension, although we need to have some controlover the constants C1, C2.  Laba and Pramanik modify Salem’s constructionto produce explicit constants in the estimates. Keleti improved upon theresult that full dimension does not guarantee 3 term arithmetic progressionsin the following.8Theorem 1.10 (Keleti [26]). For a given distinct triple of points {x, y, z},there exists a compact set in R with Hausdorff dimension 1 which does notcontain any similar copy of {x, y, z}.The method of proof is similar to the ideas from [25]. Another way toextend Theorem 1.7 is in the ambient dimension:Theorem 1.11 (Maga [31]). There exists a compact set in Rn with Haus-dorff dimension n which does not contain any parallelogram {x, x + y, x +z, x+ y + z}, with y, z 6= 0.This construction is the exact analogue of the construction from Theorem1.7, using cubes instead of intervals. In the same paper, Maga also extendsTheorem 1.10.Theorem 1.12 (Maga [31]). For distinct points x, y, z ∈ R2, there exists acompact set in R2 with Hausdorff dimension 2 which does not contain anysimilar copy of {x, y, z}.Maga [31] posed the following question:Question 1.13. If E ⊆ R2 is compact with dimH(E) = 2, must E containthe vertices of an isosceles triangle?The previous results and question will motivate our present result, whichrequires some technical definitions to set up.1.2 Notation and definitionsThroughout this document, norms of functions are used which may requirespecial attention to details. We shall use ‖f‖Lpx to denote the Lp norm of fin the x variable, in case f depends on multiple variables, ‖f‖Lp(E) to denotethe Lp norm of f on the space E, in case specifying the space is necessary,and ‖f‖p for the Lp norm when the context is clear.Many estimates are made via inequalities where we are unconcernedabout constants as a multiplier. We thus use f . g to mean f ≤ Cg whereC is a constant, and f & g to mean f ≥ Cg where C is a constant.We now develop some notation specific to the main result.9Definition 1.14. Fix integers n ≥ 2, k ≥ 3 and m ≥ n. Suppose B1, . . . , Bkare n× (m− n) matrices.(a) We say E contains a k-point B-configuration if there exists x ∈ Rn andy ∈ Rm−n \ {0} such that {x+Bjy}kj=1 ⊆ E.(b) Given any finite collection of subspaces V1, . . . , Vq ⊆ Rm−n such thatdim(Vi) < m − n, we say that E contains a non-trivial k-point B-configuration with respect to (V1, . . . , Vq) if there exists x ∈ Rn andy ∈ Rm−n \⋃qi=1 Vi such that {x+Bjy}kj=1 ⊆ E.For both of these definitions, we will drop the k from the notation if there isno confusion.Let A1, . . . , Ak be n ×m matrices. For any set of distinct indices J ={j1, . . . , js} ⊆ {1, . . . , k}, define the ns×m matrix AJ byAtJ = (Atj1 · · · Atjs),where At denotes the transpose of A. We shall use A = A{1,...,k}.Let r be the unique positive integer such thatn(r − 1) < nk −m ≤ nr. (1.4)If we have nk −m components and account for r − 1 groups of size n, weare left with nk−m−n(r−1). This quantity is useful in the main theorem,and bulky to repeatedly use. We shall denoten′ = nk −m− n(r − 1). (1.5)Notice if nk−m is a multiple of n, then n′ = n, and in general, 0 < n′ ≤ n.Definition 1.15. We say that {A1, . . . , Ak} is non-degenerate if for anyJ ⊆ {1, . . . , k} with #(J) = k − r and any j ∈ {1, . . . , k} \ J , the m ×mmatrix(AtJ A˜jt)is non-singular for any choice of (n− n′)×m submatrix A˜j of Aj.101.3 The main resultWe use dxe to denote the smallest integer larger than x.Theorem 1.16. Supposen⌈k + 12⌉≤ m < nk (1.6)and2(nk −m)k< β < n. (1.7)Let {B1, . . . , Bk} be a collection of n × (m − n) matrices such that Aj =(In×n Bj) is non-degenerate in the sense of Definition 1.15, where In×n isthe n × n identity matrix. Then for any constant C, there exists a positivenumber 0 = 0(C, n, k,m,B)  1 with the following property. Suppose theset E ⊆ Rn with |E| = 0 supports a positive, finite, Radon measure µ withthe two conditions:(a) (ball condition) sup x∈E0<r<1µ(B(x;r))rα ≤ C,(b) (Fourier decay) supξ∈Rn |µ̂(ξ)|(1 + |ξ|)β/2 ≤ C.If n− ε0 < α < n, then:(i) E contains a k-point B-configuration in the sense of Definition 1.14(a).(ii) Moreover, for any finite collection of subspaces V1, . . . , Vq ⊆ Rm−n withdim(Vi) < m−n, E contains a non-trivial k-point B-configuration withrespect to (V1, . . . , Vq) in the sense of Definition 1.14 (b).This can be viewed as a multidimensional analogue of [30]. The existenceand constructions of measures on R that satisfy (a), (b) are discussed indetail in [30]. In higher dimensions, it should be possible to generalize theconstruction in [30, Section 6] to produce examples in Rn; alternatively, itis easy to check that if µ = µ˜(dr) × σ(dω) is a product measure in radialcoordinates (r, ω), where µ˜ is a Salem measure on [0, 1] as in [30, Section6] and σ is the Lebesgue measure on Sn−1, then µ satisfies the conditions(a), (b) of Theorem 1.16.111.4 ExamplesMotivated by the discussion in Section 1.1.2, we provide some examples ofgeometric configurations which are covered by Theorem 1.16; proofs andfurther discussion will be contained in Chapter 5.Corollary 1.17. Let a, b, c be three distinct collinear points in Rn. Supposethat E ⊂ Rn satisfies the assumptions of Theorem 1.16 with ε0 sufficientlysmall depending on a, b, c, C. Then E must contain three distinct pointsx, y, z that form a similar image of the triple a, b, c.This result includes 3-term arithmetic progressions, so can be viewedas an extension of Theorem 1.8 to higher dimensions. It should be notedthat their proof would also work for any fixed 3-point configuration, the1-dimensional version of Corollary 1.17. For nonlinear triples, Theorem 1.16does not seem to cover general triangles in dimensions n ≥ 3, but there is apositive result for the plane.Corollary 1.18. Let a, b, c be three distinct points in R2. Suppose thatE ⊂ R2 satisfies the assumptions of Theorem 1.16 with ε0 sufficiently smalldepending on a, b, c, C. Then E must contain three distinct points x, y, zsuch that the triangle 4xyz is a similar copy of the triangle 4abc.Compare this to the results of Harangi, Keleti, Kiss, Maga, Ma´the´, Mat-tila, and Strenner as summarized in Table 1.1. Corollary 1.18 shows thatif θ is given, then any E ⊆ R2 as in Theorem 1.16 must not only containthe angle θ, but in fact θ can be realized as the angle of an isosceles tri-angle with vertices in E (or any other pre-determined shape); this answers,in part, Question 1.13. Note that Maga’s result described in Theorem 1.12shows the result is false without the assumption of Fourier decay.For larger configurations, we first consider parallelograms.Corollary 1.19. Suppose that E ⊂ Rn satisfies the assumptions of The-orem 1.16, with ε0 sufficiently small depending on C. Then E contains aparallelogram {x, x+y, x+z, x+y+z}, where the four points are all distinctand x, y, z ∈ Rn.12Recall Theorem 1.11 by Maga, which shows the result is false withoutthe assumption of Fourier decay.We end with a polynomial example.Corollary 1.20. Let a1, . . . , a6 be distinct numbers, all greater than 1. Sup-pose that E ⊂ R3 satisfies the assumptions of Theorem 1.16, with ε0 smallenough depending on C and ai. Then E contains a configuration of the formx, x+B2y, x+B3y, x+B4y, (1.8)for some x ∈ R3 and y ∈ R6 with Biy 6= 0 for i = 2, 3, 4, whereB2 =1 . . . 1a1 . . . a6a21 . . . a26 , B3 =a31 . . . a36a41 . . . a46a51 . . . a56 , B4 =a61 . . . a66a71 . . . a76a81 . . . a86 .This is a non-trivial result in the following sense. Since Vandermondematrices are non-singular, the set of 6 vectors1a1...a51, . . . ,1a6...a56forms a basis for R6. It follows that if a, b, c ∈ E, there is a unique y ∈ R6such that b = a+ B2y and c = a+ B3y. This also determines uniquely thepoint a + B4y, which might or might not be in E. Our result asserts that,under the conditions of Corollary 1.20, we may choose x and y so that infact all 4 points in (1.8) lie in E.13Chapter 2A multilinear form forcounting configurationsWe will consider the following multilinear form, initially defined for fj ∈C∞c (Rn), the smooth functions on Rn with compact support:Λ(f1, . . . , fk) =∫Rmk∏j=1fj(Aj~x) d~x. (2.1)If fj = f for all j, we write Λ(f) instead of Λ(f, . . . , f). Clearly if Λ(f) 6= 0,then the support of f contains configurations of the form {Aj~x : 1 ≤ j ≤ k}for a set of ~x of positive measure. We will later rewrite Λ(f1, . . . , fk) in aform that will allow us to extend it to measures, not just functions, thenshow that it is suitable for counting configurations in sparse sets.2.1 Fourier-analytic representation of themultilinear formIt turns out that working with the Fourier transforms of fj allows for goodestimates on Λ. Recall the Fourier transform of a function f ∈ C∞c (Rn)is defined by f̂(ξ) =∫Rn e−2piix·ξf(x) dx. The following result provides ameans to make use of the Fourier transform in Λ.14Proposition 2.1. For fj ∈ C∞c (Rn), Λ(f1, . . . , fk) defined in (2.1) admitsthe representationΛ(f1, . . . , fk) = C∫Sk∏j=1f̂j(ξj) dσ(ξ1, · · · , ξk),where σ is the Lebesgue measure on the subspaceS =ξ = (ξ1, . . . , ξk) ∈ (Rn)k :k∑j=1Atjξj = ~0(2.2)and C = C(A) is a constant only depending on the matrices Aj.We will require a sort of approximate identity result to prove this propo-sition. For a p× d (p ≤ d) matrix P of full rank p, defineV = {ξ ∈ Rd : Pξ = 0} = N (P ),the null space of P , and let v = dim(V ) = d− p.Definition 2.2. Fix an orthonormal basis {~α1, . . . , ~αv} of V . The surfacemeasure dσ on V is defined as follows:∫VF dσ =∫RvFv∑j=1xj~αj dx1 · · · dxvfor every F ∈ Cc(Rd).Note that this definition is independent of the choice of basis. In-deed, if {~β1, . . . , ~βv} is another orthonormal basis of V , then the mapping(x1, . . . , xv) 7→ (y1, . . . , yv) given by∑xj~αj =∑yj ~βj is a linear isome-try, hence given by an orthogonal matrix which has determinant 1. Thend~x = d~y and hence∫RvFv∑j=1xj~αj dx1 · · · dxv =∫RvFv∑j=1yj ~βj dy1 · · · dyv.15Lemma 2.3. For any g ∈ Cc(Rd) and any Ψ ∈ S(Rp) with Ψ(0) 6= 0,limε→0+∫Rdg(y1, y2)1εpΨ̂(y2ε)dy1dy2 = Ψ(0)∫Rd−pg(y1, 0) dy1.Here, y = (y1, y2) ∈ Rd, with y1 ∈ Rd−p and y2 ∈ Rp.Proof. Fix κ > 0. Our goal is to show∣∣∣∣∫Rdg(y1, y2)1εpΨ̂(y2ε)dy1dy2 −Ψ(0)∫Rd−pg(y1, 0) dy1∣∣∣∣ < κfor all ε > 0 sufficiently small. Then for every ε > 0, we have by definitionof Ψ(0)∣∣∣∣∫Rdg(y1, y2)1εpΨ̂(y2ε)dy1dy2 −Ψ(0)∫Rd−pg(y1, 0) dy1∣∣∣∣=∣∣∣∣∫Rdg(y1, y2)1εpΨ̂(y2ε)dy1dy2 −∫Rp∫Rd−pg(y1, 0)1εpΨ̂(y2ε)dy1dy2∣∣∣∣≤∫∫|g(y1, y2)− g(y1, 0)|1εp∣∣∣Ψ̂(y2ε)∣∣∣ dy1dy2.We now partition our region of integration into where |y2| is small and whereit is large. By uniform continuity of g on its compact support K, we maychoose η > 0 sufficiently small so thatsupy1∈K|g(y1, y2)− g(y1, 0)| <κ2|Ψ(0)|(2.3)if |y2| ≤ η. On this region,∫∫|y2|≤η|g(y1, y2)− g(y1, 0)|1εp∣∣∣Ψ̂(y2ε)∣∣∣ dy1dy2<∫∫κ2|Ψ(0)|1εp∣∣∣Ψ̂(y2ε)∣∣∣ dy1dy2 =κ2.Since Ψ̂ is integrable, we can make the tail integral as small as we would16like. In particular, there exists ε > 0 sufficiently small relative to η so that∫|y2|>η/ε|Ψ̂(y2)| dy2 <κ4‖g‖∞diam(K). (2.4)Then for this ε,∫∫|y2|>η,y∈K|g(y1, y2)− g(y1, 0)|1εp∣∣∣Ψ̂(y2ε)∣∣∣ dy1dy2≤ 2‖g‖∞diam(K)∫|y2|>η/ε|Ψ̂(y2)| dy2 <κ2.As this inequality holds for every κ > 0, the result follows.Proposition 2.4. For any P as above, there exists a constant CP > 0 withthe property that for any Φ ∈ S(Rp) with Φ(0) = 1, the limitlimε→0+∫RdF (ξ)1εpΦ̂(Pξε)dξexists and equals CP∫V F dσ.Proof. Fix Φ ∈ S(Rp) with Φ(0) = 1. Let {~α1, . . . , ~αv} be an orthonormalbasis of V . Extend this to an orthonormal basis of Rd, say{~α1, . . . , ~αv, ~αv+1, . . . , ~αd}.Given any function H ∈ Cc(Rd), we define GH : Rd → R as follows:GH(x1, . . . , xd) = Hd∑j=1xj~αj .Notice GH ∈ Cc(Rd) as well. Then by definition,∫VF dσ =∫RvFv∑j=1xj~αj dx1 · · · dxv=∫RvGF (x1, . . . , xv, 0, . . . , 0) dx1 · · · dxv.17By Lemma 2.3 with g = GF , y1 = (x1, . . . , xv), and y2 = (xv+1, . . . , xd), wehave∫VF dσ=1Ψ(0)limε→0+∫RdGF (x1, . . . , xv, xv+1, . . . , xd)1εpΨ̂(xd+1ε, . . . ,xdε)d~x,for any Ψ ∈ S(Rd) with Ψ(0) 6= 0, where ~x = (x1, . . . , xd). By the definitionof GF , this gives∫VF dσ =1Ψ(0)limε→0+∫RdF (ξ)1εpΨ̂(xv+1ε, . . . ,xdε)d~x, (2.5)for any Ψ ∈ S(Rd) with Ψ(0) 6= 0, where we denote ξ =∑dj=1 xj~αd. Now,let Q be the p× p matrix defined byQxv+1...xd =d∑j=v+1xjP~αj .Since P is of full rank and acting on basis vectors, Q is non-singular. RecallV = {ξ : Pξ = 0} and {~α1, . . . , ~αv} is a basis for V , so P~αj = 0 for 1 ≤ j ≤v. Thenxv+1...xd = Q−1d∑j=v+1xjP~αj = Q−1d∑j=1xjP~αj = Q−1Pξ. (2.6)Define Ψ ∈ S(Rd) byΨ̂(ξ) = Φ̂(Qξ).Then by (2.5) and (2.6),∫VF dσ =1Ψ(0)limε→0+∫RdF (ξ)1εpΨ̂(Q−1Pξε)d~x18=1Ψ(0)limε→0+∫RdF (ξ)1εpΦ̂(Pξε)d~x.Finally,Ψ(0) =∫RpΨ̂(ξ) dξ=∫RpΦ̂(Qξ) dξ=1|Q|∫RpΦ̂(ξ) dξ=1|Q|Φ(0) =1|Q|and so the result follows with CP = |Q|. Note that Q is also independent ofthe choice of basis, and is a function only of P .We are now in a position to prove Proposition 2.1.Proof of Proposition 2.1. For Φ ∈ S(Rm) with Φ(0) = 1, the dominatedconvergence theorem givesΛ(f1, . . . , fk) = limε→0+∫Rmk∏j=1fj(Aj~x)Φ(~xε) d~x.Applying the Fourier inversion formula in Rn, g(y) =∫Rn e2piiy·ξ ĝ(ξ) dξ, wegetΛ(f1, . . . , fk)= limε→0+∫Rmk∏j=1[∫Rne2piiAj~x·ξj f̂j(ξj) dξj]Φ(~xε) d~x= limε→0+∫~ξ=(ξ1,...,ξk)∈(Rn)kk∏j=1f̂j(ξj)[∫Rme2pii~x·Atξ Φ(~xε) d~x]d~ξ= limε→0+∫~ξ∈(Rn)kk∏j=1f̂j(ξj)1εpΦ̂(Atξε)d~ξ19= CAt∫Sk∏j=1f̂j(ξj) dσ(ξ),for some constant CAt . This last step follows from Proposition 2.4, withp = m, d = nk, V = S, P = At, and F =∏f̂j .Proposition 2.5. Let g ∈ S(Rm), fj ∈ C∞c (Rn). Then the integralΘ(g; f1, . . . , fk) :=∫Rmg(~x)k∏j=1fj(Aj~x) d~xis absolutely convergent, and admits the representationΘ(g; f1, . . . , fk) =∫(Rn)kĝ(−At~ξ)k∏j=1f̂j(~ξj) d~ξ.Proof. By Fourier inversion,Θ(g; f1, . . . , fk) =∫Rmg(~x)k∏j=1[∫Rne2piiAj~x·~ξj f̂j(~ξj) d~ξj]d~x,which is absolutely convergent since f̂j , g ∈ S(Rm). Then by Fubini’s The-orem,Θ(g; f1, . . . , fk) =∫(Rn)kk∏j=1f̂j(~ξj)[∫Rmg(x)e2pii~x·At~ξ d~x]d~ξ=∫(Rn)kĝ(−At~ξ)k∏j=1f̂j(~ξj) d~ξ,where the last line follows by the definition of the Fourier transform.202.2 Extension of the multilinear form tomeasuresWith S as in (2.2), denote S⊥ = {τ ∈ (Rn)k : τ · ξ = 0 for all ξ ∈ S} andfix a τ ∈ S⊥. We will use the variableη = (η1, . . . , ηk) = ξ + τ = (ξ1, . . . , ξk) + (τ1, . . . , τk) ∈ S + τ, (2.7)where ξ ∈ S, and ηj , ξj , τj ∈ Rn. DefineΛ∗τ (g1, . . . , gk) =∫S+τk∏j=1gj(ηj) dσ(η), (2.8)initially defined for gj ∈ Cc(Rn) so that the integral is absolutely convergent.If gj = g for all j, we write Λ∗τ (g) instead of Λ∗τ (g, . . . , g). We will use Λ∗ inplace of Λ∗0. Our next proposition shows that we may extend this multilinearform to continuous functions with appropriate decay.In applications, gj will be µ̂, with µ as in Theorem 1.16. While definingthe multilinear form Λ for measures requires only the use of Λ∗0 (so that theintegration is on S as in Proposition 2.1), the proof of our main result willrely crucially on estimates on Λ∗τ uniform in τ .Proposition 2.6. Let {A1, . . . , Ak} be a non-degenerate collection of n×mmatrices in the sense of Definition 1.15. Assume that nk/2 < m < nk andg1, . . . , gk : Rn → C are continuous functions satisfying|gj(κ)| ≤M(1 + |κ|)−β/2, κ ∈ Rn, (2.9)for some β > 2(nk −m)/k. Then the integral defining Λ∗τ = Λ∗τ (g1, . . . , gk)is absolutely convergent for every τ ∈ S⊥. Indeed,supτ∈S⊥Λ∗τ (|g1|, . . . , |gk|) ≤ Cwhere C depends only on n, k,m,M , and A.Since S + τ for τ ∈ S⊥ includes all possible translates of S, Proposition212.6 gives a uniform upper bound on the integral of∏gj over all affine copiesof S.The proof of this proposition is based on a lemma which requires someadditional notation. Let 0a×b denote the a × b matrix consisting of 0’s .Let In×n denote the n × n identity matrix . Define the nk × n matrix Ej(1 ≤ j ≤ k) byEtj = (0n×n · · · In×n · · · 0n×n),where In×n is in the jth block. For any ~ε = (ε1, . . . , εn) ∈ {0, 1}n, wedenote In×n(~ε) = diag(ε1, . . . , εn). For a subset J ′ ⊆ {1, . . . , n} and indexj ∈ {1, . . . , k}, define the nk × n matrixEj(J′)t = (0n×n · · · In×n(~ε) · · · 0n×n),where In×n(~ε) is in the jth block and εi = 1 if and only if i ∈ J ′. Finally,for ξ ∈ S we defineξj(J′) = Ej(J′)ξ.Lemma 2.7. Let {A1, . . . , Ak} be a non-degenerate collection of n × mmatrices in the sense of Definition 1.15. Let J = {j1, . . . , jr} ⊆ {1, . . . , k}and J ′ ⊆ {1, . . . , n} be collections of distinct indices with #(J ′) = n′, definedby (1.5). Then the projection of (ξj1 , . . . , ξjr−1 , ξjr(J′)) on S is a coordinatesystem on S as defined in (2.2). In particular, there exists a constant C =C(J, J ′, j,A) such that dσ(ξ) = C dξj1 · · · dξjr−1dξjr(J′), where σ(ξ) is theLebesgue measure on S.Proof. It suffices to proveS′ = {ξ ∈ S : ξj1 = ξj2 = · · · = ξjr−1 = ξjr(J′) = 0}has dimension 0.We will examine S′ = {ξ ∈ S : ξ1 = ξ2 = · · · = ξr−1 = ξr(J ′) = 0}; the22other cases are similar. S′ is the subspace defined by ξ ∈ (Rn)k satisfyingAt1 At2 · · · Atr−1 Atr Atr+1 · · · AtkIn×n 0 · · · 0 0 0 · · · 00 In×n · · · 0 0 0 · · · 0....... . .............0 0 · · · In×n 0 0 · · · 00 0 · · · 0 In×n(~1− ~ε) 0 · · · 0ξ = 0,where εi = 1 if and only if i 6∈ J ′, and ~1 = (1, . . . , 1). For dimS′ = 0, weneed the kernel of the above (m+ nr)× nk matrix to have dimension 0, sowe need the rank of said matrix to be nk. Notice In×n is of rank n and wehave r − 1 of these, and In×n(~1− ~ε) has rank n′ = nk −m− n(r − 1), so itsuffices forrank((Ar(~ε))t Atr+1 · · · Atk)= nk − n(r − 1)− n′ = m.A similar condition holds if we examine S′ = {ξ ∈ S : ξi1 = ξi2 = · · · =ξir−1 = ξir(J′) = 0} in general, and upon taking the transpose we arrive atthe sufficient conditionrank(AIAik−(r−1)(~ε))= m (2.10)for I = {i1, . . . , ik−r} ⊆ {1, . . . , k} a set of distinct indices, and ~ε ·~1 = n−n′.Notice this means the matrix is of full rank. (2.10) follows from the non-degeneracy assumption in Definition 1.15.Proof of Proposition 2.6. Fix τ ∈ S⊥. We use Symk to denote the sym-metric group on k elements. For a permutation θ ∈ Symk, we define theregionΩθ = {η ∈ S + τ : |ηθ(1)| ≤ |ηθ(2)| ≤ · · · ≤ |ηθ(k)|}23so thatS + τ =⋃θ∈SymkΩθ.For simplicity and without loss of generality, we will examine the case ofθ = id, the identity permutation, and write Ωid as Ω; the other cases areanalogous. It then suffices to show the convergence of the integralI =∫Ωk∏j=1|gj(ηj)| dσ .∫Ωk∏j=1(1 + |ηj |)−β/2 dσ.Let L =∏r−1j=1(1 + |ηj |)−β/2. By Ho¨lder’s inequality over k − (r − 1)terms,I .∫Ωk∏j=1(1 + |ηj |)−β/2 dσ=∫ΩLk∏i=r(1 + |ηi|)−β/2 dσ=∫Ωk∏i=r[L1/(k−(r−1))(1 + |ηi|)−β/2]dσ≤k∏i=r∫S+τ|η1|≤···≤|ηr−1|≤|ηi|L(1 + |ηi|)−β2 (k−(r−1)) dσ1/(k−(r−1))≤∫S+τ|η1|≤···≤|ηr|r−1∏j=1(1 + |ηj |)−β/2(1 + |ηr|)−β2 (k−(r−1)) dσ.In the last inequality, we see that for each i, the integral is the same witha different dummy variable, so we collect the terms under the single indexi = r. Recalling our decomposition of η into ξ and τ as per (2.7) and sinceτ is fixed, we arrive atI .∫S|ξ1+τ1|≤···≤|ξr+τr|r−1∏j=1(1 + |ξj + τj |)−β/2(1 + |ξr + τr|)−β2 (k−(r−1)) dσ(ξ).24Suppose ηr = (ηr,1, . . . , ηr,n), and for any permutation pi ∈ Symn, letηpir = (ηr,pi(1), . . . , ηr,pi(n′)).As in the beginning of this section, we may partition our current region ofintegration into a finite number of regions of the form {|ηr,pi(1)| ≥ · · · ≥|ηr,pi(n)|} for pi ∈ Symn. Then |ηr| ≤ n|ηr,pi(1)|, so that |ηr| ≈ |ηpir |.By Lemma 2.7, dσ(ξ) = C dξ1 · · · dξr−1dξpir , henceI .∫S|ξ1+τ1|≤···≤|ξr+τr|r−1∏j=1(1 + |ξj + τj |)−β/2· (1 + |ξpir + τpir |)−β2 (k−(r−1)) dξ1 · · · dξr−1dξpir.∫Rn′r−1∏j=1∫ξj+τj∈Rn|ξj+τj |≤|ξpir +τpir |(1 + |ξj + τj |)−β/2 dξj· (1 + |ξpir + τpir |)−β2 (k−(r−1)) dξpir .Translating ξj by τj ,I .∫Rn′r−1∏j=1∫ξj∈Rn|ξj |≤|ξpir |(1 + |ξj |)−β/2 dξj (1 + |ξpir |)−β2 (k−(r−1)) dξpir.∫Rn′[∫ |ξpir |0(1 + ρ)−β/2+n dρ]r−1(1 + |ξpir |)−β2 (k−(r−1)) dξpir.∫Rn′(1 + |ξpir |)(n−β/2)(r−1)−β2 (k−(r−1)) dξpir=∫Rn′(1 + |ξpir |)n(r−1)−βk/2 dξpir ,where the Jacobian in making the spherical change of coordinates ρ = |ξj |above is independent of τj . This last expression is finite (with a boundindependent of τ) whenβk/2− n(r − 1) > n′ = nk −m− n(r − 1),25which holds since 2(nk −m)/k < β < n and m > nk/2.2.3 Counting geometric configurations in sparsesetsIn this section, we will show that the multilinear form Λ∗ defined in (2.8)is effective in counting non-trivial configurations supported on appropriatesparse sets.Proposition 2.8. Suppose nk/2 < m < nk and 2(nk−m)/k < β < n. Let{A1, . . . , Ak} be a collection of n ×m matrices that are non-degenerate inthe sense of Definition 1.15. Let µ be a positive, finite, Radon measure µwithsupξ∈Rn|µ̂(ξ)|(1 + |ξ|)β/2 ≤ C. (2.11)Then there exists a non-negative, finite, Radon measure ν = ν(µ) on [0, 1]msuch that(a) ν(Rm) = Λ∗(µ̂).(b) supp ν ⊆ {x ∈ Rm : A1x, . . . , Akx ∈ suppµ}.(c) For any subspace V ⊆ Rm with dimV < m, ν(V ) = 0.2.3.1 Existence of candidate νFix a non-negative φ ∈ S(Rm) with∫φ = 1 and let φε(y) = ε−nφ(ε−1y).Let µε = µ ∗ φε. Notice φ̂ ∈ S(Rm) since φ ∈ S(Rm), so|µ̂ε(ξ)| = |µ̂(ξ)φ̂(εξ)| ≤ C(1 + |ξ|)−β/2 (2.12)with C = ‖φ̂‖∞ independent of ε. Furthermore, φ̂(εξ)→ φ̂(0) =∫φ = 1 asε→ 0, henceµ̂ε(ξ)→ µ̂(ξ) pointwise as ε→ 0. (2.13)We prove that the multilinear form Λ∗τ satisfies a weak continuity property,in the following sense:26Lemma 2.9. Λ∗τ (µ̂ε)→ Λ∗τ (µ̂) as ε→ 0 for every fixed τ ∈ S⊥.Proof. Fix τ ∈ S⊥. By definition,Λ∗τ (µ̂ε) =∫S+τk∏j=1µ̂ε(ξj) dξ.By (2.12), |µ̂ε(η)| ≤ C(1 + |η|)−β/2 =: g(η) uniformly in ε, sok∏j=1|µ̂ε(ξj)| ≤ Ck∏j=1g(ξj).By Proposition 2.6, Λ∗τ (g) is finite, so by (2.13) and the dominated conver-gence theorem,Λ∗τ (µ̂ε)→ Λ∗τ (µ̂).For F ∈ C([0, 1]m) such that F̂ ∈ S(Rm), define the linear functional νby〈ν, F 〉 = limε→0∫RmF (~x)k∏j=1µε(Aj~x) d~x. (2.14)We will prove in Lemma 2.10 below that the limit exists and extends as abounded linear functional on C([0, 1]). Clearly, 〈ν, F 〉 ≥ 0 if F ≥ 0. Bythe Riesz representation theorem, there exists a non-negative, finite, Radonmeasure ν that identifies this linear functional; namely 〈ν, F 〉 =∫F dν.Lemma 2.10. There exists a non-negative, bounded, linear functional ν onC([0, 1]), that is,|〈ν, F 〉| ≤ C‖F‖∞ (2.15)for some positive constant C independent of F ∈ C([0, 1]), which agrees with(2.14) if F̂ ∈ S(Rm).27Proof. Assume the limit (2.14) exists for F ∈ C([0, 1]), F̂ ∈ S(Rm). Then|〈ν, F 〉| ≤ limε→0∫Rm|F (~x)|k∏j=1µε(Aj~x) d~x≤ ‖F‖∞ limε→0Λ(µε)= ‖F‖∞ limε→0Λ∗(µ̂ε)≤ C‖F‖∞,where the last line follows by Proposition 2.6, with a constant C independentof ε. Thus, (2.15) holds.It remains to prove that 〈ν, F 〉 is well-defined. We will prove this byshowing that the limit in (2.14) exists for F ∈ C([0, 1]m) with F̂ ∈ S(Rm)and use density arguments to extend the functional to all of C([0, 1]m).Applying Proposition 2.5 with g = F , f1 = . . . = fk = µε, we obtain〈ν, F 〉 = limε→0Θ(F ;µε, . . . , µε) = limε→0∫RnkF̂ (−Atξ)k∏j=1µ̂ε(ξj) dξ. (2.16)By (2.13),F̂ (−Atξ)k∏j=1µ̂ε(ξj)→ F̂ (−Atξ)k∏j=1µ̂(ξj)pointwise, and by (2.12),∣∣∣∣∣∣F̂ (−Atξ)k∏j=1µ̂ε(ξj)∣∣∣∣∣∣≤ C|F̂ (−Atξ)|k∏j=1(1 + |ξj |)−β/2.Existence of the limit in (2.16) will follow from the dominated convergencetheorem, if we prove |F̂ (Atξ)|∏kj=1(1 + |ξj |)−β/2 ∈ L1(Rnk). To this end,let g(t) = (1 + |t|)β/2 for t ∈ Rn. Then∫Rnk|F̂ (Atξ)|k∏j=1(1 + |ξj |)−β/2 dξ =∫Rm|F̂ (κ)|∫Atξ=κk∏j=1g(ξj) dσ(ξ)dκ28=∫Rm|F̂ (κ)|Λ∗τ(κ)(g) dκ≤ C∫Rm|F̂ (κ)| dκ <∞.Here τ(κ) is the unique vector in S⊥ such that {Atξ = κ} = S + τ(κ). Wehave used Proposition 2.6 to bound Λ∗τ(κ) in the last displayed inequalityabove, and used the fact that F̂ ∈ S(Rm) to deduce that F̂ ∈ L1(Rm). Bythe dominated convergence theorem, the limit in (2.14) exists.To extend ν to all of C([0, 1]m), fix F ∈ C([0, 1]m). Extend F toF˜ ∈ Cc(Rm) so that F = F˜ on [0, 1]m. We will reuse F to mean F˜ for con-venience. Get a sequence of functions Fn ∈ C∞([0, 1]m) with F̂n ∈ S(Rm)such that ‖F − Fn‖∞ → 0. By the preceding proof,|〈ν, Fn − Fm〉| ≤ C‖Fn − Fm‖∞ → 0as n,m→∞ since Fn is Cauchy in supremum norm. Thus the sequence ofscalars 〈ν, Fn〉 is Cauchy and hence converges. Define〈ν, F 〉 = limn→∞〈ν, Fn〉.Clearly,|〈ν, F 〉| = limn→∞|〈ν, Fn〉| ≤ C limn→∞‖Fn‖∞ = C‖F‖∞.The proof of Lemma 2.10 yields the following corollary which will beused later in the sequel:Corollary 2.11. For F ∈ C([0, 1]m) with F̂ ∈ S(Rm),〈ν, F 〉 =∫RnkF̂ (−Atξ)k∏j=1µ̂(ξj) dξ.292.3.2 Proof of Proposition 2.8.(a)Proof. We haveν(Rm) = 〈ν, 1〉 = limε→0∫Rmk∏j=1µε(Ajx) dx = limε→0Λ(µε) = limε→0Λ∗(µ̂ε) = Λ∗(µ̂)by Lemma 2.9, with τ = 0.2.3.3 Proof of Proposition 2.8.(b)Proof. DefineX := {x ∈ Rm : A1x, . . . , Akx ∈ suppµ}.Since suppµ is closed, X is closed. Let F be any continuous function on Rmwith suppF disjoint from X, then dist (suppF,X) > 0. In order to provethat ν is supported on X, we aim to show that 〈ν, F 〉 = 0. To this end, letus defineXN := {~x ∈ Rm : dist (Aj~x, supp (µ)) ≤ 1/N for every 1 ≤ j ≤ k}=k⋂j=1{~x ∈ Rm : dist (Aj~x, supp (µ)) ≤ 1/N}.Then X ⊆ XN for every N , and X =⋂∞N=1XN . Furthermore,XcN =k⋃j=1{~x ∈ Rm : dist (Aj~x, supp (µ)) > 1/N}is an open set for every N ≥ 1, withsupp (F ) ⊆ Xc =∞⋃N=1XcN .Introducing a smooth partition of unity subordinate to {XcN}N , we can writeF =∑N FN where each FN ∈ C∞c (Rm) with supp (FN ) ⊆ XcN . Note that30since supp (F ) is a compact subset of Xc, it follows from the definition of apartition of unity that the infinite sum above is in fact a finite sum, so thereis no issue of convergence.Let µAjε (~x) := µε(Aj~x). To compute〈ν, FN 〉 = limε→0∫RmFN (~x)k∏j=1µε(Aj~x) d~x= limε→0∫RmFN (~x)k∏j=1µAjε (~x) d~xfor a fixed N ≥ 1, we observe thatsupp (µAjε ) ⊆ {~x ∈ Rm : dist (Aj~x, supp (µ)) ≤ ε}⊆ {~x ∈ Rm : dist (Aj~x, supp (µ)) ≤ 1/N}if ε ≤ 1/N . Thus the product∏kj=1 µAjε (~x) is supported on XN , whereasFN is supported on XcN . This implies∫RmFN (~x)k∏j=1µAjε (~x) d~x = 0for all ε ≤ 1/N , so that 〈ν, FN 〉 = 0 for every N ≥ 1. Therefore, 〈ν, F 〉 = 0as claimed.2.3.4 Proof of Proposition 2.8.(c)Proof. It suffices to prove the proposition for dimV = v = m − 1, sincesmaller subspaces have even less measure. Let PV denote the projectiononto V . Fix v0 ∈ V and defineVδ,γ = {x ∈ Rm : |v0 − PV x| ≤ γ,dist (x, V ) = |PV ⊥x| ≤ δ}.31It suffices to prove ν(Vδ,∞)→ 0 as δ → 0. If φδ is any smooth function withφδ =1 on Vδ,1,0 on Rm \ Vδ,2,(2.17)then ν(Vδ,∞) ≤∫φδ dν = 〈ν, φδ〉, so we aim to show that 〈ν, φδ〉 → 0 asδ → 0.Fix bases {a1, . . . , am−1} and {b} for V and V ⊥ respectively, such that{a1, . . . , am−1, b} forms an orthonormal basis of Rm. Thus, for any x ∈ Rm,there is a unique decompositionx = u+ w, with u =m−1∑j=1ajaj ∈ V,w = bb ∈ V ⊥,where ~a = (a1, . . . , am−1)t ∈ Rm−1, b ∈ R.(2.18)Without loss of generality, we may assume φδ as in (2.17) to be variable-separated asφδ(x) = φV (~a)φV ⊥(δ−1b), (2.19)where φV ∈ C∞c (Rm−1) is supported on {~a : |∑m−1j=1 ajaj − v0| ≤ 2} andφV ⊥ ∈ C∞c (R) is supported on {b : |b| ≤ 2}.By Corollary 2.11,〈ν, φδ〉 =∫Rnkφ̂δ(−Atξ)k∏j=1µ̂(ξj) dξ. (2.20)We will show that this integral tends to 0 as δ → 0. The estimation of thisintegral relies on an orthogonal decomposition of Rnk into specific subspaces,which we now describe. LetW = {ξ ∈ Rnk : Atξ · x = 0 for all x ∈ V }. (2.21)Then S is clearly a subspace of W , as Atξ = 0 if ξ ∈ S. It is also not difficultto see that dimW = nk − v = nk − (m − 1). The proof of this has been32relegated to Lemma 2.12 below. A consequence of this fact is thatdimW ∩ S⊥ = 1 (2.22)since S is (nk −m)-dimensional. Now write ξ ∈ Rnk asξ = ζ + η + λ, where ζ ∈ S, η ∈W ∩ S⊥, λ ∈W⊥,so that dξ = dσS+η+λ(ξ) dη dλ. Here dσS+η+λ denotes the surface measureon S + η + λ, as defined in Definition 2.2. We will soon show, in Lemmas2.13 and 2.14 below, that the two factors of the integrand in (2.20) obey thesize estimates:∣∣∣∣∣∣k∏j=1µ̂(ξj)∣∣∣∣∣∣. (1 + |At(η + λ) · b|)−εG(ξ), (2.23)and|φ̂δ(−Atξ)| ≤ δCM (1 + |λ|)−M (1 + δ|At(η + λ) · b|)−M (2.24)for any M ≥ 1. Here, G(ξ) =∏kj=1 g(ξj), where g(ξj) = (1 + |ξj |)−β/2+εand ε > 0 is chosen sufficiently small so thatβ − 2ε > 2(nk −m)/k. (2.25)Notice this is possible since β > 2(nk −m)/k.Assuming (2.23) and (2.24) temporarily, the estimation of (2.20) pro-ceeds as follows.|〈ν, φδ〉| ≤∫Rnk∣∣∣∣∣∣φ̂δ(−Atξ)k∏j=1µ̂(ξj)∣∣∣∣∣∣dξ.∫W⊥[∫W∩S⊥[∫S+η+λG(ξ) dσS+η+λ(ξ)]J(η, λ) dη](1 + |λ|)−M dλ,33whereJ(η, λ) = δCM (1 + |At(η + λ) · b|)−ε(1 + δ|At(η + λ) · b|)−M .We claim that ∫S+η+λG(ξ) dσ(ξ) ≤ C (2.26)andsupλ∈W⊥∫W∩S⊥J(η, λ) dη ≤ CMδε/2. (2.27)These two estimates yield, for M ≥ dim(W⊥) + 1,|〈ν, φδ〉| . CMδε/2∫W⊥(1 + |λ|)−M dλ. CMδε/2 → 0as δ → 0, as required.It remains to establish the estimates in (2.26) and (2.27). For the former,we observe that the left hand side of the inequality is Λ∗η+λ(g), so the desiredconclusion follows from Proposition 2.6 and our choice (2.25) of ε.To prove (2.27), we recall (2.22) so we may parametrize η = sw0 forsome fixed unit vector w0 ∈ W ∩ S⊥ \ {0}, with dη = ds. To confirm thatJ(η, λ) has decay in η, we need to verify that Atw0 · b 6= 0. Indeed, ifAtw0 · b = 0, then Atw0 ∈ V since b ∈ V ⊥. Since w0 also lies in W givenby (2.21), this implies Atw0 · Atw0 = 0, so that Atw0 = 0. But the lastequation says w0 ∈ S, whereas w0 ∈ S⊥ by assumption. This forces w0 = 0,a contradiction as w0 is a unit vector.We now set c0 := Atw0 · b which is nonzero by the discussion in thepreceding paragraph. Making a linear change of variable t = sc0 + Atλ · b,with Jacobian ds = dt/c0, we proceed to estimate the integral in (2.27) bypartitioning the region of integration as follows,∫W∩S⊥J(η, λ) dη34= δCM∫R(1 + |t|)−ε(1 + δ|t|)−Mdtc0= δCM∫|t|≤δ−1/2(1 + |t|)−ε(1 + δ|t|)−M dt+ δCM∫|t|>δ−1/2(1 + |t|)−ε(1 + δ|t|)−M dt. δCM∫|t|≤δ−1/21 dt+ δε/2δCM∫|t|>δ−1/2(1 + δ|t|)−M dt. δ1/2CM + δε/2δCM∫R(1 + δ|η|)−M dη≈ δ1/2CM + δε/2CM . δε/2CM .This completes the proof of (2.27) and hence the proof of the proposition.Now we prove the three lemmas required earlier for this proof.Lemma 2.12. Define W as in (2.21). Then dimW = nk−v = nk−(m−1).Proof. As before, let PV denote the projection onto V . By (2.21),W = {ξ ∈ Rnk : Atξ · x = 0 for all x ∈ V }= {ξ ∈ Rnk : Atξ · PV x = 0 for all x ∈ Rm}= {ξ ∈ Rnk : P tV Atξ · x = 0 for all x ∈ Rm}= {ξ ∈ Rnk : P tV Atξ = 0}= N (P tV At).Writing Rm as V ⊕V ⊥, the dimension of A(V ) must be equal to dimV = m−1 as A is of full rank and hence an isomorphism from Rm to the range of A.Then APV is an isomorphism from V to the range of APV , so rank(P tV At) =dim(V ) = m− 1, and thus dimW = nk − (m− 1).Lemma 2.13. With µ, ξ, η, λ, β defined as in the proof of Proposition 2.8(c),we have∣∣∣∣∣∣k∏j=1µ̂(ξj)∣∣∣∣∣∣. (1 + |At(η + λ) · b|)−εk∏j=1(1 + |ξj |)−β/2+ε,35for any ε > 0.Proof. The decay condition (2.11) on µ̂ gives∣∣∣∣∣∣k∏j=1µ̂(ξj)∣∣∣∣∣∣≤ Ck∏j=1(1 + |ξj |)−εk∏j=1(1 + |ξj |)−β/2+ε,for any ε > 0. We have|η + λ| ≤ |ξ| ≤ k max1≤j≤k|ξj |,and by Cauchy-Schwarz|At(η + λ) · b| = |(η + λ) · Ab| ≤ |η + λ||Ab|.Since Ab is fixed, |At(η + λ) · b| . |η + λ|, and so∣∣∣∣∣∣k∏j=1µ̂(ξj)∣∣∣∣∣∣. (1 + |η + λ|)−εk∏j=1(1 + |ξj |)−β/2+ε. (1 + |At(η + λ) · b|)−εk∏j=1(1 + |ξj |)−β/2+ε.Lemma 2.14. With φδ, ξ, ζ, η, λ, β defined as in the proof of Proposition2.8(c), we have|φ̂δ(−Atξ)| ≤ δCM (1 + |λ|)−M (1 + δ|At(η + λ) · b|)−M ,for any M ∈ R.Proof. Since ζ ∈ S implies Atζ = 0, we haveφ̂δ(−Atξ) = φ̂δ(−At(ζ + η + λ))= φ̂δ(−At(η + λ))36=∫∫φV (~a)φV ⊥(δ−1b)e2piiAt(η+λ)·(u+w) du dw.By definition, η ∈W and u ∈ V give Atη · u = 0, and soφ̂δ(−Atξ) =[∫VφV (~a)e2piiAtλ·A0~a du] [∫V ⊥φV ⊥(δ−1)e2piibAt(η+λ)·bb dw]=[∫Rm−1φV (~a)e2piiAt0Atλ·~a d~a] [∫RφV ⊥(δ−1b)e2piibAt(η+λ)·b db],where we have used u =∑m−1i=1 aiai = A0~a for some matrix A0, w = bb, anddu dw = da db.The first factor is by definition φ̂V (−At0Atλ). Since φ̂V ∈ S(Rm−1), forevery M ∈ R we have|φ̂V (−At0Atλ)| ≤ CM (1 + |At0Atλ|)−M .We claim |At0Atλ| & |λ| for all λ ∈ W⊥. Since At0At is linear, it suffices toprove At0Atλ 6= 0 for any λ ∈ W⊥. If λ ∈ W⊥, then by definition of W⊥there exists x ∈ V \ {0} such that (Atλ, x) 6= 0. Then x = A0~a for some~a 6= 0, so(At0Atλ,~a) = (Atλ,At0~a) 6= 0,and hence At0Atλ 6= 0. Then for every M ∈ R,|φ̂V (−At0Atλ)| ≤ CM (1 + |λ|)−M .The second factor is, upon scaling, δφ̂V ⊥(−δAt(η + λ) · b). As φ̂V ⊥ ∈S(R), for every M ∈ R we have|δφ̂V ⊥(−δAt(η + λ) · b)| ≤ δ(1 + δ|At(η + λ) · b|)−M ,completing the proof.37Chapter 3Estimates in the absolutelycontinuous caseIn this chapter, we prove a quantitative lower bound on Λ(µ1) in the casewhen µ1 is absolutely continuous with bounded density. This provides ameasure of control on the main term of the decomposition of Λ(µ) for ageneral measure µ. We we will restrict to the case when Aj is of the formAj = (In×n Bj), where Bj are n × (m − n) matrices, for reasons that willbecome clear in Section 3.5. Set x ∈ Rn and y ∈ Rm−n, so that our configu-rations are of the form {x+B1y, . . . , x+Bky}. With r defined as in (1.4),we will also assume k − 1 ≥ 2r, or equivalently, nd(k + 1)/2e ≤ m, the firstinequality of condition (1.6) of the main result.Proposition 3.1. For every δ,M > 0, there exists a constant c(δ,M) > 0with the following property: for every function f : [0, 1]n → R, 0 ≤ f ≤ M ,∫f ≥ δ, we have Λ(f) ≥ c(δ,M).We will proceed as in the proof of Varnavides’ Theorem given in [40].The strategy will be to decompose f = g + b into a “good” function gwhich is the major contribution and a “bad” function b whose contributionis negligible. This will be made precise in the following section.383.1 PreliminariesProposition 3.2. Let f be as in Proposition 3.1. Suppose f = g + b where‖g‖∞, ‖b‖∞ ≤M ; ‖g‖1, ‖b‖1 = δ.ThenΛ(f) = Λ(g) +O(C(M, δ)‖b̂‖∞).Proof. We use the decomposition f = g+ b and the linearity of Λ to decom-pose Λ(f) into 2k pieces. The main piece will be Λ(g) and the remainingpieces which constitute the error term have at least one copy of b. By thehypothesis and Ho¨lder’s inequality,‖g‖22, ‖b‖22 ≤Mδ.We will apply Lemma 3.3 below to estimate each of the 2k − 1 summandsin the error term, arriving at an upper bound of (2k − 1)‖b̂‖∞(Mδ)r.We now prove the lemma required for the previous proposition.Lemma 3.3. Let fj be as in Proposition 3.1. Assume moreover that k−1 ≥2r and ‖fj‖1 ≤ 1 for 1 ≤ j ≤ k. Then|Λ(f1, . . . , fk)| ≤M‖f̂k‖∞‖fr‖1/21 ‖f2r‖1/212r−1∏j=1j 6=r‖f̂j‖2.We have a similar bound for permutations of f1, . . . , fk.Proof. Let us recall the Fourier representation of Λ from Proposition 2.1,which gives|Λ(f1, . . . , fk)| ≤∫Sk∏j=1|f̂j(ξj)| dσ(ξ).Since ‖f̂j‖∞ ≤ ‖fj‖1 ≤ 1 for each j, reducing the number of factors in theproduct that appears in the last integrand only makes the integral larger.We use the hypothesis k − 1 ≥ 2r to drop (k − 1 − 2r) of these factors39and split the remaining 2r into two groups and apply the Cauchy-Schwarzinequality. Executing these steps leads to|Λ(f1, . . . , fk)|≤∫Sk∏j=1|f̂j(ξj)| dσ(ξ)≤ ‖f̂k‖∞∫Sr∏j=1|f̂j(ξj)|2r∏j=r+1|f̂j(ξj)| dσ(ξ)≤ ‖f̂k‖∞∫Sr∏j=1|f̂j(ξj)|2 dσ(ξ)1/22r∏j=r+1|f̂j(ξj)|2 dσ(ξ)1/2.Both of the above integrals are estimated in the same way; we will focus onlyon the first. If ξj = (ξj,1, . . . , ξj,n), let ξ′j = (ξj,1, . . . , ξj,n′) with n′ as definedin Definition 1.5; notice this is the same as ξidj as defined in Proposition 2.6.By Lemma 3.4 below, ‖f̂r‖2L2ξ′r≤M‖fr‖1, and so by Lemma 2.7,∫Sr∏j=1|f̂j(ξj)|2 dσ(ξ)=∫Sr∏j=1|f̂j(ξj)|2 dξ′rdξ1 · · · dξr−1≤∫Rn(r−1)M‖fr‖1r−1∏j=1|f̂j(ξj)|2 dξ1 · · · dξr−1= M‖fr‖1r−1∏j=1‖f̂j‖22.The result follows.Lemma 3.4. Let 1 ≤ j ≤ k. If ξj = (ξj,1, . . . , ξj,n), we denote ξ′j =(ξj,1, . . . , ξj,n′) and ξ′′j = (ξj,n′+1, . . . , ξj,k). Suppose(a) |fj | ≤M ,40(b) supp fj ⊆ [0, 1]n.Then‖f̂j‖2L2ξ′≤M‖fj‖1uniformly for all ξ′′j .Proof. Fix ξ′′j , and let F (x′, ξ′′j ) =∫fj(x′, x′′)e−2piiξ′′j ·x′′dx′′, where x′, x′′ arethe dual variables to ξ′j , ξ′′j respectively. Then (a) and (b) give |F (x′, ξ′′j )| ≤M for all x′ so that‖F‖∞ ≤M.We calculate‖F‖L1x′=∫|F (x′, ξ′′j )| dx′ ≤∫∫|fj(x′, x′′)| dx′dx′′ = ‖fj‖1.By Ho¨lder’s inequality,‖F‖2L2x′≤ ‖F‖∞ ‖F‖L1x′≤M‖fj‖1.Now,f̂j(ξ′j , ξ′′j ) =∫F (x′, ξ′′j )e−2piiξ′j ·x′dx′,which is the Fourier transform of F in x′. Therefore by Plancherel’s theoremin the x′ variables,‖f̂j‖2L2ξ′j= ‖F‖2L2x′≤M‖fj‖1.Before moving on, we shall prove an approximation identity that is usefulin the following sections.Lemma 3.5. Suppose ‖fj‖∞, ‖gj‖∞ ≤ C and ‖fj−gj‖p ≤ κ for 1 ≤ j ≤ R,for some 1 ≤ p ≤ ∞. Then∥∥∥∥∥∥R∏j=1fj −R∏j=1gj∥∥∥∥∥∥p≤ RCR−1κ.41Proof.∥∥∥∥∥∥R∏j=1fj −R∏j=1gj∥∥∥∥∥∥p≤∥∥∥∥∥∥f1 ·R∏j=2fj − g1 ·R∏j=2fj∥∥∥∥∥∥p+∥∥∥∥∥∥g1 · f2 ·R∏j=3fj − g1 · g2 ·R∏j=3fj∥∥∥∥∥∥p+ · · ·+∥∥∥∥∥∥R−1∏j=1gj · fR −R−1∏j=1gj · gR∥∥∥∥∥∥p≤R∏j=2‖fj‖∞ ‖f1 − g1‖p+ ‖g1‖∞R∏j=3‖fj‖∞ ‖f2 − g2‖p+ · · ·+R−1∏j=1‖gj‖∞ ‖fR − gR‖p≤ RCR−1κ.3.2 Almost periodic functionsIn light of Proposition 3.2, our next goal will be to identify a large class of“good” functions g for which we can bound Λ(g) from below. It turns outthat almost periodic functions, defined analogously to [40], can be used forthis purpose.Definition 3.6. 1. A character is a function χ : [0, 1]n → C of the formχ(x) = e2piiv·x for some v ∈ Zn.2. If K ∈ N, then a K-quasiperiodic function is a function f of the form∑K`=1 c`χ` where each χ` are characters (not necessarily distinct), andc` are scalars with |c`| ≤ 1.423. If σ > 0, then f : [0, 1]n → C is (σ,K)-almost periodic if there existsa K-quasiperiodic function fQP such that ‖f − fQP ‖L2([0,1]n) ≤ σ. Wecall fQP a K-quasiperiodic function approximating f within σ.Lemma 3.7. Let K ∈ N, M > 0, 0 < δ < 1, and0 < σ ≤δk4kMk−1. (3.1)Then there exists c(K, δ,M) > 0 such that for any non-negative (σ,K)-almost periodic function f bounded by M and obeying∫f ≥ δ,Λ(f) ≥ c(K, δ,M).Proof. Our goal is to bound Λ(f) from below by a multiple of ‖f‖k1, whichis known to be at least as large as δk. We will achieve this by approximatingeach factor in the integral defining Λ by f , on a reasonably large set withacceptable error terms.To this end, let fQP be a K-quasiperiodic function approximating fwithin σ, say fQP (x) =∑K`=1 c`e2piiv`·x and ‖f − fQP ‖2 ≤ σ. Let ε > 0 be asmall constant to be fixed later, and defineCε = {y ∈ Rm−n :∣∣∣∣∣∣Atjv` · y∣∣∣∣∣∣ ≤ ε, for all 1 ≤ j ≤ k, 1 ≤ ` ≤ K}, (3.2)where |||t||| denotes the distance of t ∈ R to the nearest integer. A pigeonholeargument gives that|Cε| ≥ c(ε,K) > 0 (3.3)for some c(ε,K) possibly dependent on k, m and n but independent of f .This non-trivial result will be shown in Corollary 3.9 following this proof.Let T a be the shift map T af(x) := f(x + a). For y ∈ Cε and anyx ∈ [0, 1]n,|TBjyfQP (x)− fQP (x)| =∣∣∣∣∣K∑`=1c`e2piiv`·x(1− e2piiv`·Ajy)∣∣∣∣∣43≤K∑`=1|1− e2piiAtjv`·y|≤K∑`=1|Atjv` · y|≤ Kε. (3.4)The bound above leads to the following estimate:‖TBjyf − f‖L1x ≤ ‖TBjyf − TBjyfQP ‖L2x + ‖TBjyfQP − fQP ‖L∞x+ ‖fQP − f‖L2x= 2‖fQP − f‖L2x + ‖TBjyfQP − fQP ‖L∞x≤ 2σ +Kε≤δk2kMk−1+Kε.In the sequence of inequalities above, we have used Ho¨lder’s inequality inthe first step, triangle inequality in the second step, norm-invariance of theshift operator in the third step, and (3.4) in the last step.We now choose ε = δk/(4kMk−1), so that‖TBjyf − f‖L1x ≤3δk4kMk−1. (3.5)For every 1 ≤ j ≤ k, the bound ‖TBjyf‖L∞x = ‖f‖∞ ≤ M holds trivially,so by Lemma 3.5 with C = M , fj = f , gj = TBjyf , R = k, p = 1, andκ = (3δk)/(4kMk−1), we have∥∥∥∥∥∥k∏j=1TBjyf − fk∥∥∥∥∥∥L1x≤ kMk−13δk4kMk−1=3δk4using (3.5). On the other hand, the bounded non-negativity of f , the hy-pothesis∫f ≥ δ, and Ho¨lder’s inequality lead to‖fk‖1 ≥ ‖f‖k1 ≥ δk,44and so for y ∈ Cε,∥∥∥∥∥∥k∏j=1TBjyf∥∥∥∥∥∥L1x≥∥∥∥fk∥∥∥1−∥∥∥∥∥∥k∏j=1TBjyf − fk∥∥∥∥∥∥L1x≥δk4. (3.6)We now combine 3.3, the positivity of f and the above to obtainΛ(f) =∫Rm−n∫Rnk∏j=1fj(x+Bjy) dx dy=∫Rm−n∥∥∥∥∥∥k∏j=1TBjyf∥∥∥∥∥∥L1xdy≥∫Cε∥∥∥∥∥∥k∏j=1TBjyf∥∥∥∥∥∥L1xdy≥ δkc(ε,K)/4= c(K, δ,M).Lemma 3.8. Given 0 < ε < 1 and any integer K ≥ 1, there exists a positiveconstant c′(ε,K) such that|{t ∈ [0, 1] : |||tv`||| ≤ ε for all 1 ≤ ` ≤ K}| ≥ c′(ε,K),for any choice of v1, . . . , vK ∈ Z.Proof. Clearly it suffices to prove the lemma for the case when ε ≤ 1. Let Nbe the unique integer that N−1 < ε ≤ (N −1)−1, and consider the partitionof the unit cube [0, 1]K into NK disjoint cubes of side length N−1. That is,the vertices of the cubes are at points of the form N−1ZK mod 1. DefineXQ = {t ∈ [0, 1] : (tv1, . . . , tvK) mod 1 ∈ Q}.45Then since |[0, 1]| = 1, there must exist a cube Q such that|XQ| ≥1NK≥(ε2)K,where we have used that ε ≤ (n− 1)−1. For t ∈ XQ,(tv1, . . . , tvK) mod 1 ∈ Q−Q ⊆ [−n−1, n−1]K ⊆ [−ε, ε]K ,and so |||tv`||| ≤ ε for every 1 ≤ ` ≤ K. Notice|XQ −XQ| ≥ |XQ| ≥(ε2)K,and so by symmetry|{t ∈ [0, 1] : |||tv`||| ≤ ε for all 1 ≤ ` ≤ K}| ≥12(ε2)K.Corollary 3.9. Given 0 < ε < 1, and integers k,K,m, n ∈ N, m > n, thereexists a positive constant c depending on all of these quantities, for whichthe setCε = {y ∈ Rm−n :∣∣∣∣∣∣Atjv` · y∣∣∣∣∣∣ ≤ ε, for all 1 ≤ j ≤ k, 1 ≤ ` ≤ K}.defined as in Lemma 3.7 obeys the size estimate|Cε| ≥ cfor any choice of matrices {Aj} and vectors {v`}.Proof. Let Atjv`(i) denote the ith component of Atjv`. LetDi = {yi ∈ [0, 1] :∣∣∣∣∣∣Atjv`(i)yi∣∣∣∣∣∣ ≤ ε/(m− n) for all 1 ≤ j ≤ k, 1 ≤ ` ≤ K}.By Lemma 3.8,|Di| ≥ c′(ε/(m− n),K)k46for 1 ≤ i ≤ m− n. If y = (y1, . . . , ym−n) ∈∏m−ni=1 Di, then∣∣∣∣∣∣Atjv` · y∣∣∣∣∣∣ =∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣m−n∑i=1Atjv`(i)yi∣∣∣∣∣∣∣∣∣∣∣∣∣∣∣≤ (m− n)εm− n= ε,and soCε ⊇ D1 × · · ·Dm−n.Therefore,|Cε| ≥ c′(ε/(m− n),K)k(m−n) = c(ε,K).3.3 Ubiquity of almost periodic functionsTo make use of Lemma 3.7, we will approximate a general function f by analmost periodic function. In the following sequence of lemmas, we constructan increasingly larger family of σ-algebras with the property that any func-tion measurable with respect to these will be almost periodic. We do this byan iterative random mechanism, the building block of which is summarizedin the next result.Lemma 3.10. Let 0 < ε  1 and let χ be a character. Viewing C asR2, partition the complex plane C =⋃Q∈Qε Q into squares of side-length εwith corners lying in the lattice εZ2. For ω ∈ [0, 1]2, define Bε,χ,ω to be theσ-algebra generated by the atoms{χ−1(Q+ εω) : Q ∈ Qε}.There exists ω such that1. ‖χ− E(χ|Bε,χ,ω)‖∞ ≤ Cε.2. For every σ > 0 and M < 0, there exists K = K(σ, ε,M) suchthat every function f which is measurable with respect to Bε,χ,ω with‖f‖∞ ≤M is (σ,K)-almost periodic.47Proof. (1) follows from definition of Bε,χ,ω, for any ω.To prove (2), it suffices to prove: for each integer ` > `0 for some suf-ficiently large `0, there exists a set Ω` ⊆ [0, 1]2, |Ω`| > 1 − C2−`ε with thefollowing property. For ω ∈ Ω`, there exists K = K(σ, ε,M) such that everyfunction f which is measurable with respect to Bε,χ,ω with ‖f‖∞ ≤ M is(σ,K)-almost periodic, for σ = 2−`.Indeed, taking Ω =⋂`>`0 Ω`, we have|Ω| > 1− C∑`>`02−`ε ≥ 1− C2−`0εand so we may find ω ∈ Ω. Then if σ > 0, get ` > `0 with 2−` ≤ σ, and bythe above, there exists K = K(2−`, ε,M) such that every function f whichis measurable with respect to Bε,χ,ω with ‖f‖∞ ≤ M is (2−`,K)-almostperiodic. Thus, we fix σ = 2−`.Let N be the number of atoms of Bε,χ,ω. Recall that the atoms are ofthe form χ−1(Q + εω) for Q ∈ Qε. Since the image of χ lies in the unitcircle S1, the preimage of (Q + εω) under χ is non-empty if and only if(Q + εω) ∩ S1 6= ∅. Since diam(Q + εω) =√2ε, this holds if and only if(Q+ εω) lies in the (√2ε)-thickened unit circle,S1[√2ε]= {x ∈ C : dist (x,S1) ≤√2ε}.It is easy to calculate |S1[√2ε]| = pi4√2ε and |Q+ εω| = ε2 for every Q ∈ Qε,so since the squares Q+ εω are disjoint,N ≤|S1√2ε||Q+ εω|=pi4√2ε.In particular, Bε,χ,ω has at most Cε−1 atoms; we use this fact to reduce theproof of Lemma 3.10 to a simpler form. Namely, it suffices to prove that forf an indicator function of one of those atoms, sayf(x) = fQ,ω(x) := 1χ−1(Q+εω)(x) = 1Q(χ(x)− εω),48there exists a C(σ, ε)-quasiperiodic function gQ,ω such that ‖fQ,ω−gQ,ω‖2 ≤C−1σε with probability 1− Cσε−1. (Here and below, C(σ, ε) will denote aconstant which may change from line to line, but always depends only onM,σ, ε, in particular remains independent of f .) Indeed, if this were thecase, then any measurable f may be written asf(x) =∑i∈IcifQi,ω(x)where fQi,ω(c) = 1Qi(χ(x)− εω)(x), Qi ∈ Qε are distinct, and #I ≤ Cε−1.Notice ‖f‖∞ ≤ M and the fact that fQi,ω have disjoint support means|ci| ≤ M for i ∈ I. Letting gQi,ω be a C(σ/M, ε)-quasiperiodic functionapproximating fQi,ω to within C−1M−1σε, we have that g =∑i∈I cigQi,ωis C(σ, ε)-quasiperiodic (repeating gQi,ω at most M times if necessary) and‖f − g‖2 ≤∑i∈I|ci| · ‖fQi,ω − gQi,ω‖2 ≤ σ.Thus we restrict to the case when f is the indicator function of one ofthose atoms, which we denote fω for ease.f(x) = fω(x) := 1Q(χ(x)− εω).Let 0 ≤ h ≤ 1 be a continuous function on [−2, 2]2 which is a good L2-approximation for 1Q; precisely,‖1Q − h‖2L2([−2,2]2) <σ3ε310CM2. (3.7)By the Weierstrass Approximation Theorem, there exists a polynomial Psuch that‖h− P‖L∞([−2,2]2) <(σ3ε310CM2)1/2. (3.8)Let hω(x) := h(χ(x) − εω), and gω(x) = P (χ(x) − εω); notice gω can bewritten as a linear combination of at most C(σ, ε) characters, with coeffi-cients at most C(σ, ε). Repeating characters if necessary, we may reduce the49coefficients to be less than 1 and so gω is C(σ, ε)-quasiperiodic. It shouldalso be noted that ‖gω‖∞ ≤ ||gω − hω||∞ + ||hω||∞ ≤ 2.It remains to show ‖fω − gω‖2 ≤ C−1M−1σε with probability at least1− Cσε−1. DefineF (ω) = ‖fω − gω‖22 =∫[0,1]n|fω(x)− gω(x)|2 dx.By an application of Cauchy-Schwarz inequality on the integrand, combinedwith (3.7) and Tonelli’s Theorem, we obtain‖F‖L1ω =∫[0,1]2∫[0,1]n|fω(x)− gω(x)|2 dx dω≤ 2∫[0,1]2∫[0,1]n[|fω(x)− hω(x)|2 + |hω(x)− gω(x)|2] dx dω<σ3ε32CM2+∫[0,1]n∫[0,1]2|hω(x)− gω(x)|2 dω dx<σ3ε32CM2+∫[0,1]n∫[0,1]2|h(χ(x)− εω)− P (χ(x)− εω)|2 dω dx.Using the change of variables ω′ = χ(x) − εω for fixed x ∈ [0, 1]n, we havedω′ = ε2 dω. Notice ω′ belongs to [0, ε]2 shifted by χ(x), so is contained in[−2, 2]2. By (3.8),‖F‖1 ≤σ3ε32CM2+∫[0,1]n∫ω′∈[−2,2]2|h(ω′)− P (ω′)|2dω′ε2dx≤σ3ε32CM2+∫[0,1]n∫ω′∈[−2,2]2|h(ω′)− P (ω′)|2dω′ε2dx=σ3ε32CM2+∫[0,1]n1ε2‖h− P‖2L2([−2,2]2) dx≤σ3ε32CM2+∫[0,1]n1ε2(σ3ε310CM2)dx<1ε2(σ3ε3CM2).50By Markov’s inequality,|{ω ∈ [0, 1]2 : ‖fω − gω‖22 > C−2M−2σ2ε2}|= |{ω ∈ [0, 1]2 : F (ω) > C−2M−2σ2ε2}|≤C2M2‖F‖1σ2ε2≤C2M2 1ε2(σ3ε3CM2)σ2ε2= Cσε−1.Thus,|{ω ∈ [0, 1]2 : ‖fω − gω‖22 ≤ C−1M−1σε}| ≥ 1− Cσε−1,as required.The above proof also gives the following result.Corollary 3.11. Let 0 < ε 1 and let χ be a character. Then the σ-algebraBε,χ,ω described in the statement of Lemma 3.10 can be chosen to have theadditional property that for every atom χ−1(Q + εω), Q ∈ Qε, there existsa K-quasiperiodic function gQ,ω that obeys ‖gQ,ω(·) − 1Q(χ(·) − εω)‖2 < σfor every σ > 0, and in addition ‖gQ,ω‖∞ ≤ 2.We can concatenate the σ-algebras from Lemma 3.10. If B1, . . . ,BR areσ-algebras, denote by B1 ∨ · · · ∨ BR the smallest σ-algebra which containsall of them.Corollary 3.12. Let 0 < ε1, . . . , εR  1 and let χ1, . . . , χR be characters.Let Bε1,χ1 , . . . ,BεR,χR be the σ-algebras arising from Lemma 3.10. Then forevery σ > 0, there exists K = K(R, σ, ε1, . . . , εR) such that every functionf which is measurable with respect to Bε1,χ1 ∨ · · · ∨ BεR,χR with ‖f‖∞ ≤ Mis (σ,K)-almost periodic.Proof. Since there are at most C(R, ε1, . . . , εR) atoms in Bε1,χ1∨· · ·∨BεR,χR ,it suffices to prove the claim in the case when f is the indicator func-tion of a single atom. Then f is the product of R indicator functionsf1, . . . , fR, where fj is the indicator function of an atom from Bεj ,χj . Let gjbe a K(σ/(R2R−1), εj)-quasiperiodic function approximating fj to within51σ/(R2R−1) as provided in Corollary 3.12; notice ‖gj‖∞ ≤ 2. Then g =∏gjis a K-quasiperiodic function where K =∏K(σ/(R2R−1), εj) dependsonly on R, σ, ε1, . . . , εR. Finally, by Lemma 3.5 with C = 2, p = 2, andκ = σ/(R2R−1), we have∥∥∥∥∥∥R∏j=1fj −R∏j=1gj∥∥∥∥∥∥2≤ σ.3.4 Proof of Proposition 3.1.We will need two more auxiliary results, analogous to [40, Lemma 2.10 and2.11].Lemma 3.13. Let b be a function bounded by M with ‖b̂‖∞ ≥ σ > 0. Thenthere exists 0 < ε σ, a character χ, and an associated σ-algebra Bε,χ (asdefined earlier in this section) such that‖E(b|Bε,χ)‖2 ≥ C−1σ.Proof. Since ‖b̂‖∞ ≥ σ, there exists a character χ such that∣∣∣∣∣∫[0,1]nb(x)χ(x) dx∣∣∣∣∣≥σ2. (3.9)On the other hand, the σ-algebra Bε,χ is generated by the atoms {χ−1(Q+εω);Q ∈ Qε} for some ω in the unit square. On each atom, χ can vary byat most Cε, hence‖χ− E(χ|Bε,χ)‖∞ ≤ Cε. (3.10)Since b is bounded by M , (3.9) and (3.10) yield∫[0,1]nb(x)E(χ|Bε,χ)(x) dx ≥σ2−MCε.52Conditional expectation being self-adjoint, the inequality above may berewritten as ∫[0,1]nE(b|Bε,χ)(x)χ(x) dx ≥σ2−MCε.Recalling that χ is bounded above by 1, the desired result now follows bychoosing ε sufficiently small relative to σ and M , and applying Cauchy-Schwarz inequality to the integral on the left.Lemma 3.14. Let F : R+×R+ → R+ be an arbitrary function, let 0 < δ ≤1, and let f ≥ 0 be a function bounded by M with∫f ≥ δ. Let σ satisfy(3.1). Then there exists a K with 0 < K ≤ C(F, δ) and a decompositionf = g + b where g ≥ 0 is a bounded (σ,K)-almost periodic function with∫g ≥ δ, and b obeys the bound‖b̂‖∞ ≤ F (δ,K). (3.11)The proof of Lemma 3.14 is exactly identical to [40, 2.11].Proof of Proposition 3.0.8. Let F : R+ × R+ → R+ be a function to bechosen later. Decompose f = g + b as in Lemma 3.14. By Lemma 3.7,Λ(g) ≥ c(K, δ,M).By Proposition 3.2, (3.11), and the above inequality,Λ(f) ≥ c(K, δ,M) +O(C(M, δ)F (δ,K)).By choosing F sufficiently small and since K ≤ C(F, δ), we getΛ(f) ≥ c(δ,M)as required.533.5 Quantitative Szemere´di bounds fail forgeneral AAt the beginning of this chapter, we restricted to the case when Aj is of theform Aj = (In×n Bj) where Bj are n × (m − n) matrices. The reason forthis is that generic Ai will not provide a lower bound on Λ when∫f = δ,even when satisfying the non-degeneracy condition.In the case n = 2, k = 3,m = 4, consider the function f = 1B((0,1),δ), theindicator of the ball centered at (0, 1) with radius δ ≤ 1/3. DefineA1 =(1 0 0 00 1 0 0),A2 =(0 0 1 00 0 0 1),A3 =(0 1 1 01 0 0 1).It is clear that (2.10) holds for these matrices. In the integral definingΛ, we consider the conditions for ~x = (x1, . . . , x4) to be in the support of∏3i=1 f(Ai~x). The first term of the product gives f(A1~x) = f(x1, x2), andso in particular, |x2 − 1| < δ which implies|x2| > 1− δ. (3.12)Similarly, considering the second term yields in particular|x3| < δ, (3.13)while the third term gives|x2 + x3| < δ. (3.14)On the other hand, (3.12) and (3.13) give|x2 + x3| ≥ |x2| − |x3| > 1− 2δ ≥ δ.54Then the support of∏4i=1 f(Ai~x) is empty, and Λ = 0.55Chapter 4Proof of the main resultThe preceding section gave a quantitative lower bound on the Λ quantityin the case of absolutely continuous measures with bounded density. Thissuggests the strategy of decomposing the measure µ as µ = µ1 + µ2 whereµ1 is absolutely continuous with bounded density, and µ2 gives negligiblecontribution. In light of the Fourier form of Λ, the key property of µ2 herewill be having good bounds on the Fourier transform.Let φ ∈ S(Rn) be a non-negative function supported on B(0, 1) with∫φ = 1. For any positive integer N , define φN (x) = Nnφ(Nx). Let N  1be a large constant to be determined later, and letµ1(x) = µ ∗ φN (x).Clearly, µ1 ≥ 0 is a C∞ function of compact support with∫dµ1 = 1. SinceφN is supported on B(0, N−1),|µ1(x)| ≤∫B(x,N−1)|φN (x− y)| dµ(y)=∫B(x,N−1)Nn|φ(N(x− y))| dµ(y)≤ CNnµ(B(x,N−1))≤ CNn−α56where the last inequality follows by the ball condition (a). Then |µ1(x)| ≤M = Ce if N = e1/(n−α), which tends to infinity as α→ n−.Focusing now on µ2, we will prove that∣∣µ̂2(ξ)∣∣ . N−εβ2 (1 + |ξ|)−β2 (1−ε) (4.1)for some constant ε > 0 to be chosen later. Since∫φ = 1 and φ ∈ S(Rn),|1− φ̂(ξ)| = |φ̂(0)− φ̂(ξ)| =∣∣∣∣∫ 10ddtφ̂(tξ) dt∣∣∣∣ ≤∫ 10|ξ · ∇φ̂| dt ≤ C|ξ|.In particular, defining µ2 = µ− µ1 we have|µ̂2(ξ)| . |µ̂(ξ)|min(1, |ξ|N−1).Notice if |ξ| ≥ N , then|µ̂2(ξ)| ≤ |µ̂(ξ)|. (1 + |ξ|)−β/2= (1 + |ξ|)−εβ/2(1 + |ξ|)−β/2(1−ε). N−εβ/2(1 + |ξ|)−β/2(1−ε).On the other hand, if |ξ| < N , then we still have|µ̂2(ξ)| ≤ |µ̂(ξ)|. (1 + |ξ|)−β/2|ξ|N−1= (1 + |ξ|)−β/2|ξ|εβ/2|ξ|1−εβ/2N−1. N−εβ/2(1 + |ξ|)−β/2(1−ε).Now, decomposeΛ∗(µ̂) = Λ∗(µ̂1) + Λ(µ̂2, µ̂1, . . . , µ̂1) + · · ·+ Λ(µ̂2).By Proposition 3.1, Λ∗(µ̂1) = Λ(µ1) > c(δ,M). It remains to show the57Λ∗ quantities containing at least one copy of µ2 are negligible relative toc(δ, Ce). These quantities can be written as Λ∗(g1, . . . , gk) where for each1 ≤ j ≤ k, gj is either µ̂1 or µ̂2 and at least one gj is µ̂2. Without loss ofgenerality, suppose g1 = µ̂2, so that|g1(η1)| . N−εβ/2(1 + |ηj |)−β/2(1−ε)by the above estimate on µ̂2. For j ≥ 2, we have|gj(ηj)| . (1 + |ηj |)−β/2(1−ε)by the above estimate on µ̂2 and the general Fourier decay condition (b) onµ. ThenΛ∗(g1, . . . , gk) =∫Sk∏j=1gj(ηj) dσ≤ N−εβ/2∫Sk∏j=1(1 + |ηj |)−β/2(1−ε) dσ.Since β > 2(nk − m)/k, we may choose ε > 0 so that β′ = β(1 − ε) >2(nk − m)/k. Then by Proposition 2.6 with β′ in place of β, the integralabove is bounded by a constant independent of N . Then we may choose Nsufficiently large that Λ∗(g1, . . . , gk) ≤ 2−kc(δ,M), and soΛ∗(µ̂) ≥ 2−kc(δ,M).The result follows by Proposition 2.8.58Chapter 5ExamplesFor a fixed choice of n ≥ 1 and k ≥ 3, let m be a multiple of n that satisfies(1.6). Non-degeneracy in the sense of Definition 1.15 in this case will be theconditionrankAi1...Aim/n = rankIn×n Bi1......In×n Bim/n = m,for i1, . . . , im/n ∈ {1, . . . , k} distinct. Reducing,rankIn×n Bi10n×n Bi2 −Bi1......0n×n Bm/n −Bi1= m.Since In×n is of rank n, it suffices forrankBi2 −Bi1...Bim/n −Bi1 = m− n, (5.1)for i1, . . . , im/n ∈ {1, . . . , k} distinct. Notice that while it is necessary tocheck (5.1) for every choice of m/n indices i1, . . . , im/n, we do not need to59check for permutations of the indices—any permutation suffices.Example 5.1 (Triangles). We now prove the claim in Corollary 1.18 thatif a, b, c are three distinct points in the plane, then any set E ⊂ R2 obeyingthe assumptions of Theorem 1.16 with ε0 small enough (depending on Cand on a, b, c) must contain a similar copy of the triangle 4abc. Note thatour proof allows for degenerate triangles where a, b, c are collinear.Let θ be the angle between the line segments ab and ac, measuredcounter-clockwise, and let λ = |c−a||b−a| . Permuting the points a, b, c if nec-essary, we may assume without loss of generality that θ ∈ (0, pi]. Then itsuffices to prove that E contains a configuration of the formx, x+ y, x+ λyθ, (5.2)where yθ is the vector y rotated by an angle θ counter-clockwise, for somex, y ∈ R2 with y 6= 0.Fix n = 2, k = 3, and m = 4. Let B1 = 02×2, By (5.1), non-degeneracymeans thatrank(Bj) = 2, rank(B3 −B2)= 2,for j = 2, 3. With θ ∈ (0, pi] and λ > 0 as above, letB2 =(1 00 1), B3 =(λ cos θ −λ sin θλ sin θ λ cos θ).It is easy to check that non-degeneracy holds, and this collection of matricescorresponds to configurations of the form (5.2). Letting V = {0}, Theorem1.16 asserts that any set E ⊂ R2 obeying its assumptions with ε0 smallenough must contain such a configuration, non-degenerate in the sense thaty 6= 0. This proves Corollary 1.18.Example 5.2 (Collinear triples). We prove that if a, b, c are three distinctcollinear points in Rn, then any set E ⊂ Rn obeying the assumptions ofTheorem 1.16 with ε0 small enough (depending on C and on a, b, c) mustcontain a non-degenerate similar copy of {a, b, c}.60Without loss of generality, suppose |c − a| > |b − a| Let λ = |c−a||b−a| > 1.Then it suffices to prove that E contains a configuration of the formx, x+ y, x+ λy, (5.3)for some x, y ∈ Rn with y 6= 0.Fix a positive integer n, k = 3, and m = 2n. Let B1 = 0n×n, B2 = In×n,B3 = λIn×n. Similarly to Example 5.1, this system of matrices producesconfigurations of the form (5.3), and the non-degeneracy condition (5.1)becomesrank(Bj) = n, rank(B3 −B2)= n,for j = 2, 3, which is easy to check for Bj as above. Applying Theorem 1.16with V = {0} as before, we get the desired conclusion.Example 5.3 (Parallelograms). We now prove Corollary 1.19, by provinga more general result.Corollary 5.4. Suppose that E ⊂ Rn satisfies the assumptions of Theorem1.16, with ε0 sufficiently small depending on C. Then E contains a config-uration of the form {x, x+ y1, . . . , x+ yk−2, x+ y1 + · · ·+ yk−2}, where thek points are all distinct and x, y1, . . . , yk−2 ∈ Rn.Note that there is no relationship imposed on k and n. Geometrically,such configurations can be viewed as corresponding to k of the vertices ofa (k − 2)-parallelotope sitting in n dimensions; an “origin” vertex, (k − 2)“generator” vertices, and the vertex diagonal from the origin vertex. Inparticular, parallelograms are the special case when k = 4.Proof. Fix n ≥ 1, k ≥ 4, and m = (k − 1)n. LetB1 =(0n×n 0n×n 0n×n · · · 0n×n),B2 =(In×n 0n×n 0n×n · · · 0n×n),B3 =(0n×n In×n 0n×n · · · 0n×n),...61Bk−1 =(0n×n 0n×n 0n×n · · · In×n),Bk = B2 +B3 + · · ·+Bk−1=(In×n In×n In×n · · · In×n).(5.1) tells us non-degeneracy will be the conditionrankBi1Bi2...Bik−2= (k − 2)n, rankB2 −BkB3 −Bk...Bk−1 −Bk= (k − 2)nfor i1, i2, . . . , ik−2 ∈ {2, 3, 4, . . . , k} distinct.If i1, i2, . . . , ik−2 ∈ {2, 3, 4, . . . , k − 1}, then by rearranging,rankBi1Bi2...Bik−2= rankIn×n 0n×n · · · 0n×n0n×n In×n · · · 0n×n....... . ....0n×n 0n×n · · · In×n= (k − 2)n.If one of the indices is k, say ik−2 = k, then replacing Bik−2 with Bik−2 −(Bi1 +· · ·+Bik−3) reduces the matrix to the previous case as rank is invariantunder elementary row operations. Finally, it is easy to see thatrankB2 −BkB3 −Bk...Bk−1 −Bk= rank0n×n In×n · · · In×nIn×n 0n×n · · · In×n....... . ....In×n In×n · · · 0n×n= (k − 2)n.In this example, we may consider degeneracy to be the case where twoor more points coincide; the exceptional subspaces are then of the form{yi1,j1 = yi2,j2}, 1 ≤ i1, i2 ≤ k − 1, 1 ≤ j1, j2 ≤ n, of which there are finitelymany. The result follows by Theorem 1.16.62Example 5.5 (Polynomial configurations). Finally, we prove Corollary1.20. We will in fact prove a stronger statement, namely that the resultin Corollary 1.20 holds in Rn for all n ≥ 3, with (1.8) replaced by 4-pointconfigurations defined below in Corollary 5.6.As in Example 5.3, fix n ≥ 1, k = 4, and m = 3n, and let B1 = 0n×2n.We will use a Vandermonde-style matrix for the remaining Bi. To make thenotation less cumbersome, for a functiong : N× N→ R(i, j) 7→ g(i, j),we denote by (g(i, j))a×b the a × b matrix whose entry in the ith row andjth column is given by g(i, j).Corollary 5.6. Let a1, . . . , a2n > 1 be distinct real numbers, and let η +1, d ∈ N. Consider the following matrices:B2 = (aη+(i−1)dj )n×2n,B3 = (aη+(n+i−1)dj )n×2n,B4 = (aη+(2n+i−1)dj )n×2n.Suppose that E ⊂ Rn obeys the assumptions of Theorem 1.16, with 0 smallenough depending on C and ai. Then E contains a configuration of the formx, x+B2y, x+B3y, x+B4y (5.4)for some x ∈ Rn and y ∈ R2n with Biy 6= 0 for i = 2, 3, 4.The proof of Corollary 5.6 will rely on two short lemmas.Lemma 5.7. Suppose 0 ≤ η1 < η2 < . . . < ηt are integers. Then for anychoice of constants c1, c2, . . . , ct that are not all zero, the polynomialP (x) =t∑i=1cixηi63has fewer than t distinct positive roots.Proof. We prove this with induction. For t = 1, it is clear that c1xη1 cannothave a positive root since c1 6= 0, so the base case is satisfied. We make theinductive hypothesis that the lemma holds for t, and check t + 1. Supposeto the contrary that there exist constants c1, c2, . . . , ct+1, not all zero, suchthat the polynomialP (x) =t+1∑i=1cixηihas at least t+ 1 distinct positive roots. But thenx−η1P (x) = c1 + c2xη2−η1 + · · ·+ ct+1xηt+1−η1 ,so by Rolle’s Theorem, the following polynomial has at least t distinct pos-itive roots:P1(x) :=ddx(x−η1P (x))= c2(η2 − η1)xη2−η1−1 + c3(η3 − η1)xη3−η1−1 + · · ·+ ct+1(ηt+1 − η1)xηt+1−η1−1=t∑i=1ci+1(ηi+1 − η1)xηi+1−η1−1Since ηi were strictly increasing integers, ci+1(ηi+1 − η1) are not all zero,and ηi+1 − η1 − 1 ≥ 0 are strictly increasing integers. This contradicts theinduction hypothesis and completes the proof.Lemma 5.8. IfA = (aηij )t×swhere a1, a2, . . . , as are distinct, positive real numbers and 0 ≤ η1 < η2 <. . . < ηt are integers, then A has full rank.Proof. Without loss of generality, t ≤ s. It suffices to show the followingsubmatrix has full rank:At = (aηij )t×t.64This holds if and only if detAt 6= 0. If to the contrary detAt = 0, then we canfind constants c1, c2, . . . , ct that are not all zero such that∑ti ciRi = ~0, whereRi is the ith row of At; considering the kth position this says∑ti=1 ciaηij = 0for 1 ≤ j ≤ t. That is, the polynomialP (x) =t∑i=1cixηihas at least the t distinct positive roots x = aj for 1 ≤ j ≤ t. This contradictsLemma 5.7, so we must have detAt 6= 0 and hence A has full rank.Proof of Corollary 5.6. By Lemma 5.8,rank(Bi1Bi2)= 2nfor i1, i2 ∈ {2, 3, 4} distinct. It remains to checkrank(B2 −B4B3 −B4)= rank((aη+(i−1)dj − aη+(2n+i−1)dj )n×2n(aη+(n+i−1)dj − aη+(2n+i−1)dj )n×2n)= 2n. (5.5)For constants c1, . . . , c2n, consider the polynomialQc1,...,c2n(x) = c1(xη − xη+2nd) + c2(xη+d − xη+(2n+1)d) + · · ·+ cn(xη+(n−1)d − xη+(3n−1)d) + cn+1(xη+nd − xη+2nd)+ · · ·+ c2n(xη+(2n−1)d − xη+(3n−1)d)(5.6)If (5.5) fails to hold, then as in the proof of Lemma 5.8, there areconstants c1, . . . , c2n not all 0 whose corresponding polynomial Q(x) :=Qc1,...,c2n(x) has at least the 2n distinct roots a1, . . . , a2n, all of which arelarger than 1. We may simplify Q(x) asQ(x) = c1xη(1− x2nd) + c2xη+d(1− x2nd) + · · ·+ cnxη+(n−1)d(1− x2nd)65+ cn+1xη+nd(1− xnd) + · · ·+ c2nxη+(2n−1)d(1− xnd)= (1− xnd)[c1xη(1 + xnd) + c2xη+d(1 + xnd) + · · ·+ cnxη+(n−1)d(1 + xnd) + cn+1xη+nd + · · ·+ c2nxη+(2n−1)d]= (1− xnd)P (x),whereP (x) = c1xη + c2xη+d + · · ·+ cnxη+(n−1)d+ (c1 + cn+1)xη+nd + · · ·+ (cn + c2n)xη+(2n−1)d.The roots of Q(x) which are larger than 1 coincide with the roots of P (x).Notice that not all of the coefficients of P (x) are 0, since not all of c1, . . . , c2nare 0. Then by Lemma 5.7, P (x) has fewer than 2n positive roots, a contra-diction. Thus, (5.5) holds and {A1, . . . , Ak} is non-degenerate. The resultfollows by applying Theorem 1.16, with Vi = {y ∈ R2n : Biy = 0} fori = 2, 3, 4.It should be noted that a nearly identical proof will work for general k.If k is of the form 2` or 2`+ 1 for ` ∈ N, then m = (`+ 1)n and the matricesare populated as before, using distinct real numbers a1, . . . , a`n > 1. Theproof of the analogue of (5.5) relies on a polynomial similar to that in (5.6),and uses the fact that 1− xnd divides 1− xand for any a ∈ N.66Chapter 6Conclusion6.1 Overview of the resultsMany interesting results have been produced which are related to Sze-mere´di’s theorem of k-term arithmetic progressions in sets of positive densityin the integers. In Section 1.1.1, we discussed a few of the motivating re-sults in the discrete case. This was followed by some continuous analogues inthe Euclidean setting of Szemere´di-type problems. Of particular note wasTheorem 1.8 on 3-term arithmetic progressions in subsets of R, of whichthis thesis can be seen to be an extension via Theorem 1.16, in terms ofdimension and included patterns.Similar to [30], a Fourier-analytic representation of the Λ multilinearform was proved in Proposition 2.1. This form allowed us to use Fourierdecay to control the size of Λ as well as provide a way to use Λ with measures.This extension of Λ to measures, Λ∗, was the main result of Section 2.2.Proposition 2.8 showed that Λ∗(µ̂) > 0 is the necessary bound to proveexistence of the appropriate patterns.The key idea behind proving positivity of Λ∗(µ̂) was decomposing µ asµ = µ1 + µ2, where µ1 is absolutely continuous with bounded density, andµ2 is singular but obeys good Fourier bounds. The portion involving onlyµ1 is handled by a quantitative lower bound given by Proposition 3.1, usinga similar method as used by Tao in [40] to prove Varnavides’ Theorem.67The other portions were shown to be relatively negligible in Chapter 4, tocomplete the proof.Chapter 5 contained several examples of geometric configurations cov-ered by the main result. Of interest are the instances where negative resultshave been proved in the absence of the Fourier decay condition. In partic-ular, Example 5.1 shows a similar copy of a specific triangle is contained insets satisfying the assumptions of Theorem 1.16; Maga’s result (Theorem1.12) shows that this is not the case if the Fourier decay condition is notsatisfied. Likewise, Example 5.3 shows existence of parallelograms in setssatisfying the assumptions of Theorem 1.16, while Maga (Theorem 1.11)indicates this is false without Fourier decay. Finally, Example 5.2 providesa multidimensional generalization of  Laba and Pramanik’s result (Theorem1.8).6.2 Possible directions for future researchIn this section, we will discuss possible directions for future research, inher-ently touching upon some of the the limitations of the research.6.2.1 Non-degeneracyWe begin by recalling our notion of non-degeneracy for a set of appropriately-sized matrices as given in Definition 1.15. Although such a constraint on theAj allows us to use ξj as a basis for S as in Lemma 2.7, it is not necessarilya requirement for the result to hold. We thus ask what happens in the casethat non-degeneracy fails.Question 6.1. Suppose {A1, . . . , Ak} is a collection of degenerate matrices.Is it necessarily true that the result of Theorem 1.16 fails?6.2.2 Valid range of mAlong the lines of examining the hypotheses of Theorem 1.16, recall therestriction placed on the variables n,m, k given by (1.6). In particular, werequired m ≥ n d(k + 1)/2e, which was needed for the estimate made in68Lemma 3.3 to produce suitable bounds on |Λ(f1, . . . , fk)|. Prior to thispoint, we needed only that m > nk/2 in order to prove the integrand inΛ was absolutely convergent in Proposition 2.6, which is strictly weaker forn ≥ 2 and k even or n ≥ 3 and k odd.Question 6.2. Can Theorem 1.16 hold with the weaker condition nk/2 <m < nk instead of (1.6)?It is worth noting that in proving Proposition 2.6, we made use of thefact that|gj(ηj)| . (1 + |ηj |)−β/2, ηj ∈ Rn.If |ηj | & |η| for all j, then the integrand in Λ has good decay as |η| → ∞:∣∣∣∣∣∣k∏j=1gj(ηj)∣∣∣∣∣∣. (1 + |η|)−kβ/2,so that the integral is convergent whenever kβ/2 > nk −m. This holds forβ sufficiently close to n if kn/2 > nk−m, or equivalently, m > nk/2. Thus,this is the best range of m we could hope for, using the method outlined inthe previous chapters.6.2.3 Linear configurationsEven having a lower bound of nk/2 for m precludes some nice geometricconfigurations in the theory. In general, m can be viewed as the number of“free variables” over which we have no control. Recall in Example 5.3 thatthe set-up for parallelograms in R2 was n = 2, k = 4, and m = 3 · 2 = 6.The free variables correspond to a starting point x ∈ R2, and two otherarbitrary points x+ y, x+ z ∈ R2 for a total of 6 entries. The fourth pointis determined by the other three, via x + y + z. Another simple geometricconfiguration would be a square in R2, which has 2 · 2 = 4 free variables.Givenx, x+(y1y2),69where x ∈ R2 and y1, y2 ∈ R, a square is generated by the following vertices:x, x+(y1y2), x+(−y2y1), x+(y1 − y2y1 + y2).Unfortunately, m > nk/2 is not satisfied in this case, and so Theorem 1.16fails regardless of the answer to Question 6.2.A similar issue occurs when we attempt to get all the vertices of a generalparallelotope, rather than just the generator vertices and the diagonal vertexas described in the discussion following Corollary 5.4. Here, a p-parallelotopein Rn would be given by a general n ≥ 1, k = 2p, and m = (p + 1)n. Notethat m > nk/2 fails if p ≥ 3.Another nice, geometric configuration which cannot be covered are co-linear k-tuples for k ≥ 4, since m = 2n in this case. In particular, 4-termarithmetic progressions will not satisfy the conditions of the theorem. Asmentioned in the introduction, Gowers utilized higher order Fourier analysisto handle longer arithmetic progressions in the integers, which also appearsin the work of Green and Tao [19] in showing primes contain arithmeticprogressions of arbitrary length. Gowers and Wolf [17] show more recentlythat this notion can provide results involving more general configurations aswell. This leads to the following questions.Question 6.3. Could higher order Fourier analysis be utilized in place oflinear Fourier analysis to provide better bounds on m? In particular, cank-term arithmetic progressions be included in this theory?Question 6.4. If the answer to the previous question is yes, can such atheory also include geometric configurations such as squares (in R2) andparallelotopes (in Rn)?6.2.4 Non-linear configurationsFinally, we note that the analysis involved in proving Theorem 1.16 reliedon linear configurations. Two simple, non-linear configurations are patternsof the form {x, x+ y, x+ y2} and regular polytopes.70Question 6.5. Is there a version of Theorem 1.16 which applies to a patternof the form {x, x+ y, x+ y2}?Question 6.6. Is there a version of Theorem 1.16 which applies to regularpolytopes?71Bibliography[1] J. Arias de Reyna. Some results connected with a problem of Erdo˝s.III. Proc. Amer. Math. Soc., 89(2):291–292, 1983. → pages 2[2] F. A. Behrend. On sets of integers which contain no three terms inarithmetical progression. Proc. Nat. Acad. Sci. U. S. A., 32:331–332,1946. → pages 3[3] C. Bluhm. Random recursive construction of Salem sets. Ark. Mat.,34(1):51–63, 1996. → pages 8[4] C. Bluhm. On a theorem of Kaufman: Cantor-type construction oflinear fractal Salem sets. Ark. Mat., 36(2):307–316, 1998. → pages 8[5] D. Borwein and S. Z. Ditor. Translates of sequences in sets of positivemeasure. Canad. Math. Bull., 21(4):497–498, 1978. → pages 2[6] J. Bourgain. Construction of sets of positive measure not containingan affine image of a given infinite structures. Israel J. Math.,60(3):333–344, 1987. → pages 2[7] V. Chan, I.  Laba, and M. Pramanik. Finite configurations in sparsesets. ArXiv e-prints, July 2013. → pages iii[8] B. Cook, A´. Magyar, and T. Titichetrakun. A MultidimensionalSzemere´di Theorem in the primes. ArXiv e-prints, June 2013. →pages 4[9] P. Erdo˝s. Remarks on some problems in number theory. Math.Balkanica, 4:197–202, 1974. Papers presented at the Fifth BalkanMathematical Congress (Belgrade, 1974). → pages 1[10] P. Erdo˝s and S. Kakutani. On a perfect set. Colloq. Math., 4:195–196,1957. → pages 572[11] P. Erdo˝s and P. Tura´n. On Some Sequences of Integers. J. LondonMath. Soc., S1-11(4):261. → pages 2[12] K. J. Falconer. On a problem of Erdo˝s on sequences and measurablesets. Proc. Amer. Math. Soc., 90(1):77–78, 1984. → pages 1[13] K. J. Falconer. Fractal geometry. John Wiley & Sons Inc., Hoboken,NJ, second edition, 2003. Mathematical foundations and applications.→ pages 6[14] H. Furstenberg. Ergodic behavior of diagonal measures and a theoremof Szemere´di on arithmetic progressions. J. Analyse Math.,31:204–256, 1977. → pages 3[15] H. Furstenberg and Y. Katznelson. An ergodic Szemere´di theorem forcommuting transformations. J. Analyse Math., 34:275–291 (1979),1978. → pages 3[16] W. T. Gowers. A new proof of Szemere´di’s theorem. Geom. Funct.Anal., 11(3):465–588, 2001. → pages 3[17] W. T. Gowers and J. Wolf. The true complexity of a system of linearequations. Proc. Lond. Math. Soc. (3), 100(1):155–176, 2010. → pages70[18] B. Green. Roth’s theorem in the primes. Ann. of Math. (2),161(3):1609–1636, 2005. → pages 4[19] B. Green and T. Tao. The primes contain arbitrarily long arithmeticprogressions. Ann. of Math. (2), 167(2):481–547, 2008. → pages 4, 70[20] V. Harangi, T. Keleti, G. Kiss, P. Maga, A. Ma´the´, P. Mattila, andB. Strenner. How large dimension guarantees a given angle? Monatsh.Math., 171(2):169–187, 2013. → pages 6[21] J.-P. Kahane. Sur certains ensembles de Salem. Acta Math. Acad. Sci.Hungar., 21:87–89, 1970. → pages 8[22] J.-P. Kahane. Some random series of functions, volume 5 ofCambridge Studies in Advanced Mathematics. Cambridge UniversityPress, Cambridge, second edition, 1985. → pages 8[23] J.-P. Kahane and R. Salem. Ensembles parfaits et se´riestrigonome´triques. Hermann, Paris, second edition, 1994. With notes73by Kahane, Thomas W. Ko¨rner, Russell Lyons and Stephen WilliamDrury. → pages 8[24] R. Kaufman. On the theorem of Jarn´ık and Besicovitch. Acta Arith.,39(3):265–267, 1981. → pages 8[25] T. Keleti. A 1-dimensional subset of the reals that intersects each ofits translates in at most a single point. Real Anal. Exchange,24(2):843–844, 1998/99. → pages 6, 9[26] T. Keleti. Construction of one-dimensional subsets of the reals notcontaining similar copies of given patterns. Anal. PDE, 1(1):29–33,2008. → pages 9[27] Y. Kohayakawa, T.  Luczak, and V. Ro¨dl. Arithmetic progressions oflength three in subsets of a random set. Acta Arith., 75(2):133–163,1996. → pages 4[28] M. N. Kolountzakis. Infinite patterns that can be avoided by measure.Bull. London Math. Soc., 29(4):415–424, 1997. → pages 2[29] P. Komja´th. Large sets not containing images of a given sequence.Canad. Math. Bull., 26(1):41–43, 1983. → pages 2[30] I.  Laba and M. Pramanik. Arithmetic progressions in sets offractional dimension. Geom. Funct. Anal., 19(2):429–456, 2009. →pages 7, 8, 11, 67[31] P. Maga. Full dimensional sets without given patterns. Real Anal.Exchange, 36:79–90, 2010. → pages 9[32] A. Ma´the´. Sets of large dimension not containing polynomialconfigurations. ArXiv e-prints, January 2012. → pages 6[33] P. Mattila. Geometry of sets and measures in Euclidean spaces,volume 44 of Cambridge Studies in Advanced Mathematics.Cambridge University Press, Cambridge, 1995. Fractals andrectifiability. → pages 7[34] H. I. Miller. Some results connected with a problem of Erdo˝s. II.Proc. Amer. Math. Soc., 75(2):265–268, 1979. → pages 2[35] K. F. Roth. On certain sets of integers. J. London Math. Soc.,28:104–109, 1953. → pages 374[36] R. Salem. On singular monotonic functions whose spectrum has agiven Hausdorff dimension. Ark. Mat., 1:353–365, 1951. → pages 8[37] R. Salem and D. C. Spencer. On sets of integers which contain nothree terms in arithmetical progression. Proc. Nat. Acad. Sci. U. S.A., 28:561–563, 1942. → pages 3[38] E. Szemere´di. On sets of integers containing no four elements inarithmetic progression. Acta Math. Acad. Sci. Hungar., 20:89–104,1969. → pages 3[39] E. Szemere´di. On sets of integers containing no k elements inarithmetic progression. Acta Arith., 27:199–245, 1975. Collection ofarticles in memory of Juri˘ı Vladimirovicˇ Linnik. → pages 3[40] T. Tao. Arithmetic progressions and the primes. Collect. Math., (Vol.Extra):37–88, 2006. → pages 38, 42, 52, 53, 67[41] T. Tao and T. Ziegler. A multi-dimensional Szemere´di theorem for theprimes via a correspondence principle. ArXiv e-prints, June 2013. →pages 475

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0166905/manifest

Comment

Related Items