Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Configurations in fractal sets in Euclidean and non-Archimedean local fields Fraser, Robert 2018

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

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata


24-2018_may_fraser_robert.pdf [ 776.25kB ]
JSON: 24-1.0364399.json
JSON-LD: 24-1.0364399-ld.json
RDF/XML (Pretty): 24-1.0364399-rdf.xml
RDF/JSON: 24-1.0364399-rdf.json
Turtle: 24-1.0364399-turtle.txt
N-Triples: 24-1.0364399-rdf-ntriples.txt
Original Record: 24-1.0364399-source.json
Full Text

Full Text

Configurations in Fractal Sets inEuclidean and Non-ArchimedeanLocal FieldsbyRobert FraserA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)March 2018c© Robert Fraser 2018AbstractWe discuss four different problems. The first, a joint work with MalabikaPramanik, concerns large subsets of Rn that do not contain various typesof configurations. We show that a collection of v points satisfying a con-tinuously differentiable v-variate equation in R can be avoided by a set ofHausdorff dimension 1v−1 and Minkowski dimension 1. The second problemconcerns large subsets of vector spaces over non-archimedean local fieldsthat do not contain configurations. Results analogous to the real-variablecases are obtained in this setting. The third problem is the construction ofmeasure-zero Besicovitch-type sets in Kn for non-archimedean local fieldsK. This construction is based on a Euclidean construction ofWisewell and an earlier construction of Sawyer. The fourth problem, a jointwork with Kyle Hambrook, is the construction of an explicit Salem set inQp. This set is based on a Euclidean construction of Kaufman.iiLay SummaryHow large can a set be if the set does not contain a certain pattern?This problem remains open in some important cases: for example, in thecase where the pattern is an equilateral triangle and the space is three-dimensional. We obtain bounds on the answer for generic patterns.Suppose that a set in the plane contains a line segment in every direction.How large must it be? Surprisingly, such sets can have zero area. We showthat, in a different 2-dimensional space, such sets can also have area zero.Can we construct a non-random set that does not correlate well withhigh-frequency waves? Such behaviour is typical of random sets, but con-structing non-random examples is difficult. This question has been solvedin 1 and 2 dimensions, but not in higher dimensions. We consider the 1-dimensional version of this question in a slightly different setting.iiiPrefaceThis thesis is based on four previous works, one of which has been publishedand the other three of which are submitted for publication in academicjournals.The material in Chapters 2 and 3 is based on the work “Large SetsAvoiding Patterns.” This is a joint work with Malabika Pramanik that hasbeen accepted for publication in Analysis and PDE. I proved the buildingblock lemma in the case where the gradient of the function was nonvanishing.I also devised the queueing procedure used in the construction of the set.The material in Chapters 4 and 5 is based on the work “Large Subsets ofLocal Fields Not Containing Configurations.” This is a single-author work.I was responsible for all aspects of the project, starting from the formulationof the problem, developing the methodology, and the solution.The material in Chapters 6 and 7 is based on the paper “Kakeya-typesets in local fields with finite residue field” appearing in Mathematika, Vol-ume 62, Pages 614-629. I was responsible for all aspects of this project,including finding the problem, finding the relevant literature, and develop-ing the construction appearing in this work.The material in Chapters 8 and 9 is based on the work “Explicit Salemsets, Fourier restriction, and metric Diophantine approximation in the p-adic numbers.” This is a joint work with Kyle Hambrook. I established theexponential sum estimate used in the construction and proved the theoremin the one-dimensional case.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . vAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Sets Avoiding Configurations . . . . . . . . . . . . . . . . . . 11.2 Sets Avoiding Configurations in Local Fields . . . . . . . . . 31.3 Besicovitch Sets . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Salem Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.5 Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Dimensions of Sets . . . . . . . . . . . . . . . . . . . . . . . . . 102.1 Minkowski Dimension . . . . . . . . . . . . . . . . . . . . . . 102.2 Hausdorff Dimension . . . . . . . . . . . . . . . . . . . . . . 112.3 Frostman’s Lemma . . . . . . . . . . . . . . . . . . . . . . . 133 Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.1.1 Two Constructions of Keleti . . . . . . . . . . . . . . 163.1.2 The Constructions of Maga and Ma´the´ . . . . . . . . 173.2 Discussion of Main Results . . . . . . . . . . . . . . . . . . . 193.2.1 Nonsimultaneous Avoidance . . . . . . . . . . . . . . 193.2.2 Polygons and Polyhedra . . . . . . . . . . . . . . . . 253.2.3 Simultaneous Avoidance . . . . . . . . . . . . . . . . 263.3 A Single Step . . . . . . . . . . . . . . . . . . . . . . . . . . . 27vTable of Contents3.3.1 One Dimension, Nonvanishing Gradient . . . . . . . . 283.3.2 One Dimension, General Case . . . . . . . . . . . . . 333.3.3 Higher Dimensions . . . . . . . . . . . . . . . . . . . 353.4 Construction of E . . . . . . . . . . . . . . . . . . . . . . . . 413.4.1 Construction . . . . . . . . . . . . . . . . . . . . . . . 423.4.2 Nonexistence of Solutions . . . . . . . . . . . . . . . . 443.4.3 Hausdorff Dimension of E . . . . . . . . . . . . . . . 453.4.4 Minkowski Dimension of E . . . . . . . . . . . . . . . 473.5 Simultaneous Avoidance . . . . . . . . . . . . . . . . . . . . 474 Background on Local fields . . . . . . . . . . . . . . . . . . . . 544.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.3 K-Valued Functions . . . . . . . . . . . . . . . . . . . . . . . 574.4 Hensel’s Lemma . . . . . . . . . . . . . . . . . . . . . . . . . 584.5 The Height Function . . . . . . . . . . . . . . . . . . . . . . 604.5.1 Finite Characteristic Case . . . . . . . . . . . . . . . 614.5.2 p-Adic Case . . . . . . . . . . . . . . . . . . . . . . . 614.5.3 Negatives of Elements of Finite Height . . . . . . . . 625 Configurations II . . . . . . . . . . . . . . . . . . . . . . . . . . 635.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 635.2 A Single Step . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.2.1 Polynomial, Nonsingular Case . . . . . . . . . . . . . 645.2.2 One Dimension, Nonsingular Case . . . . . . . . . . . 655.2.3 One Dimension, General Case . . . . . . . . . . . . . 675.2.4 Multidimensional Case . . . . . . . . . . . . . . . . . 695.3 Construction of E . . . . . . . . . . . . . . . . . . . . . . . . 715.3.1 General Procedure . . . . . . . . . . . . . . . . . . . . 715.3.2 Hausdorff Dimension of E . . . . . . . . . . . . . . . 745.3.3 Minkowski Dimension of E . . . . . . . . . . . . . . . 775.4 Simultaneous Avoidance . . . . . . . . . . . . . . . . . . . . 786 Besicovitch Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 806.1 The Kakeya Problem . . . . . . . . . . . . . . . . . . . . . . 806.2 The Kakeya Problem for Finite Fields . . . . . . . . . . . . . 817 Local Field Besicovitch Sets . . . . . . . . . . . . . . . . . . . 837.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 837.1.1 Previous Constructions . . . . . . . . . . . . . . . . . 83viTable of Contents7.1.2 A Besicovitch Set in Fq[[t]]2 . . . . . . . . . . . . . . 857.2 Adapting to Local Fields . . . . . . . . . . . . . . . . . . . . 877.2.1 Construction of φ . . . . . . . . . . . . . . . . . . . . 877.2.2 Estimates on the Range of f(x, φ(x)) . . . . . . . . . 887.2.3 Kakeya-Like Sets . . . . . . . . . . . . . . . . . . . . 927.2.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 937.2.5 A Kakeya Needle Set . . . . . . . . . . . . . . . . . . 958 Background on Salem Sets . . . . . . . . . . . . . . . . . . . . 968.1 Fourier Dimension . . . . . . . . . . . . . . . . . . . . . . . . 968.2 Fourier Analysis on Non-Archimedean Local Fields . . . . . 988.3 The Fourier Transform on Spaces Other than L1 . . . . . . . 1018.4 The Case K = Qp . . . . . . . . . . . . . . . . . . . . . . . . 1028.5 Hausdorff and Minkowski Dimension . . . . . . . . . . . . . 1049 An Explicit Salem Set . . . . . . . . . . . . . . . . . . . . . . . 1069.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1069.2 A Salem Set in Zp . . . . . . . . . . . . . . . . . . . . . . . . 1079.2.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 1079.2.2 Estimates on F̂M . . . . . . . . . . . . . . . . . . . . 1089.2.3 Estimates on µ̂k . . . . . . . . . . . . . . . . . . . . . 1109.3 Fourier Dimension of W (m,n, τ) . . . . . . . . . . . . . . . . 1119.3.1 Fourier Transform of φq,r . . . . . . . . . . . . . . . . 1139.3.2 Estimate on F̂M . . . . . . . . . . . . . . . . . . . . . 1149.3.3 Concluding Remarks Regarding W (m,n, τ) . . . . . . 11610 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11710.1 Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . 11710.1.1 Squares of Differences . . . . . . . . . . . . . . . . . . 11710.1.2 Configurations and Fourier Dimension . . . . . . . . . 11810.1.3 Local Fields . . . . . . . . . . . . . . . . . . . . . . . 11910.2 Besicovitch Sets on Local Fields . . . . . . . . . . . . . . . . 11910.3 Salem Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122viiAcknowledgementsI would like to thank my supervisory committee members Izabella  Laba andJozsef Solymosi for their help and support.I would like to thank all of my friends in the mathematics departmentfor all of their encouragement.I would like to extend a special thanks to Myrto Mavraki and PamSargent for their help with keeping me on track to finish my thesis.I would like to thank my family for their emotional support throughoutthe process of writing this thesis.I would like to thank my Master’s supervisor and former Ph.D. co-supervisor Akos Magyar for everything he taught me as a Master’s studentand as a first-year Ph. D. student.I would like to thank the senior students in UBC’s harmonic analysisgroup for welcoming me into the department.I would like to thank my friend and collaborator, Kyle Hambrook, forall of his contributions to our joint project.Most of all, I would like to thank my supervisor, Malabika Pramanik,for all of the advice and support she provided. Without her, none of thework in this thesis would have been possible.viiiDedicationTo my friends and familyixChapter 1IntroductionWe start with an overview of the main results of this thesis.1.1 Sets Avoiding ConfigurationsIn a joint work with Pramanik, [19], we consider questions of the followingform: given a collection of patterns, how large can a set E be if it doesnot contain any v distinct points in any of those patterns? To answer thisquestion, we need a notion of the size of Lebesgue-null subsets of Rn, whichwill be discussed in Chapter 2.This question was motivated by results of Keleti [28] [29], Maga [33],and Ma´the´ [34]. For example, given a linear three-point configuration inone dimension [29] (resp. 2 dimensions [33]), there is a subset of R (resp.R2) of Hausdorff dimension 1 (resp. 2) that does not contain any similarcopy of the three-point configuration. As another example, given an angleθ, Ma´the´ constructs a set of Hausdorff dimension n8 (orn4 if cos2(θ) happensto be rational) that does not contain 3 points that form an angle θ.We prove a result that applies for a broader class of configurations. Wedefine a configuration to be the locus of points x1, . . . , xv in Rn such thatf(x1, . . . , xv) = 0 for some function f : Rnv → Rm. We consider functionssatisfying certain smoothness and nondegeneracy conditions. We primarilyconcern ourselves with the case m = 1 but also prove a weaker result form > 1. In the m = 1 case, we have the following theorem.Theorem 1.1.1 (Theorem 1.1 from [19]). For any η > 0 and integer v ≥ 3,let fq : Rv → R be a countable family of functions in v variables with thefollowing properties:(a) There exists rq ≥ 1 such that fq ∈ Crq([0, η]v),(b) For each q, some partial derivative of fq of order rq ≥ 1 does not vanishat any point of [0, η]v .11.1. Sets Avoiding ConfigurationsThen there exists a set E ⊆ [0, η] of Hausdorff dimension at least 1v−1 andMinkowski dimension 1 such that fq(x1, . . . , xv) is not equal to zero for anyv-tuple of distinct points x1, . . . , xv ∈ E and any function fq.This theorem can be used to locate large sets that simultaneously avoida countable collection of sufficiently smooth configurations.Of special note is that there is no need to assume that fq has a nonva-nishing partial first derivative: all that is needed is that each fq has somenonvanishing partial derivative of some order on [0, η]v .Notice that, if the sequence {fq} consists of a single function f , theconditions of Theorem 1.1.1 will always hold provided that f is analyticon some interval [0, η] and not identically zero. This gives a wide range offunctions for which this theorem is applicable.One application of Theorem 1.1.1 that will be further discussed in Chap-ter 3 involves subsets of a curve that avoid isosceles triangles. It is shownthat, regardless of the ambient dimension, any smooth curve in Rd containsa subset of Hausdorff dimension 12 that does not contain the vertices of anyisosceles triangle.For functions f : Rnv → Rm with m > 1, we have the following weakertheorem that requires a non-degeneracy condition on the first derivative.Theorem 1.1.2 (Theorem 1.2 from [19]). Fix η > 0 and positive integersm,n, v such that v ≥ 3, and m ≤ n(v−1). Let fq : Rnv → Rm be a countablefamily of C2 functions with the following property: for every q, the derivativeDfq(x1, · · · , xv) has full rank on [0, η]nv at every point (x1, · · · , xv) in thezero set of fq such that xr 6= xs for all r 6= s.Then there exists a set E ⊆ [0, η]n of Hausdorff dimension at least mv−1 andMinkowski dimension n such that fq(x1, . . . , xv) is not equal to zero for anyv-tuple of distinct points x1, . . . , xv ∈ En and any function fq.This result can be used for certain geometric constructions that will befurther detailed in Chapter 3.We also construct a set that does not contain any configurations with aspecified linearization.Theorem 1.1.3 (Theorem 1.3 from [19]). Given any constant K > 0 anda vector α ∈ Rv such thatα · u 6= 0 for every u ∈ {0, 1}v with u 6= 0, u 6= (1, 1, . . . , 1) (1.1)and such thatv∑j=1αj = 0, (1.2)21.2. Sets Avoiding Configurations in Local Fieldsthere exists a positive constant c(α) and a set E = E(K,α) ⊆ [0, 1] ofHausdorff dimension c(α) > 0 with the following property.The set E does not contain any nontrivial solution of the equationf(x1, · · · , xv) = 0, x1, · · · , xv not all identical,for any C2 function f of the formf(x1, · · · , xv) =v∑j=1αjxj +G(x1, · · · , xv) (1.3)where |G(x)| ≤ Kv∑j=2(xj − x1)2. (1.4)This theorem is useful for simultaneously avoiding related configurationsof a given type. For example, this theorem is used to construct a subset E ⊂R, such that, for any sufficiently smooth injective mapping with boundedsecond derivative from R to Rn, E maps to a set of points that does notcontain the vertices of an isosceles triangle.1.2 Sets Avoiding Configurations in Local FieldsWe are also interested in non-archimedean local fields, such as the p-adicnumbers Qp, as a model for the Euclidean setting. The field Qp consists ofnumbers of the form ∞∑j=Mdjpjwhere dj ∈ {0, 1, . . . , p−1} and M is an integer. If the sum has only finitelymany nonzero terms, then this sum lies in Q. An absolute value is defined onthis field in the following way: if d is a p-adic number such that M satisfiesdM 6= 0 and dj = 0 for all j < M , then |d| = p−M . With respect to thisnorm, Qp is a locally compact abelian group. More details about Qp andother non-archimedean local fields will be given in Chapter 4.The ring of integers of Qp is known as the ring Zp of p-adic integers, andconsists of sums of the form ∞∑j=0djpj.We will also concern ourselves with the local field Fq((t)), consisting offormal Laurent series with coefficients in the finite field Fq, and Fq[[t]], thering of formal power series with coefficients in Fq.31.2. Sets Avoiding Configurations in Local FieldsThe main results from [34] and from [19] apply to the non-archimedeanlocal fields Qp and Fq((t)) [18]. Here is the adaptation of Ma´the´’s theorem.Theorem 1.2.1 (Theorem 1.1 from [18]). Let {fℓ} : Rnvℓ → R be a count-able family of nonzero polynomials of degree at most d with integer coeffi-cients, where R = Zp or Fq[[t]]. Then there exists a set E ⊂ Rn of Hausdorffdimension nd and Minkowski dimension n such that, for all ℓ, the set E doesnot contain vℓ distinct points x1, . . . , xvℓ such that fℓ(x1, . . . , xvℓ) = 0.One important application of this result is the case where f(x1, x2, x3) =x1 − 2x2 + x3. This function is equal to zero whenever x1, x2, and x3 lie inarithmetic progression. Thus Theorem 1.2.1 gives a subset of K of Hausdorffdimension 1 that does not contain 3-term arithmetic progressions forK = Qpor Fq((t)).We also establish analogues of Theorems 1.1.1, 1.1.2, and 1.1.3 in non-archimedean local fields. However, a stronger assumption than continuousdifferentiability is needed here because the mean value theorem does notapply to local fields. The notion of strict differentiability will be discussedin Chapter 4.Theorem 1.2.2 (Theorem 1.2 from [18]). Let K = Qp and R = Zp, orlet K = Fq((t)) and R = Fq[[t]]. For any ball B ⊂ R and integer v ≥ 3,let fℓ : R → K be a countable family of functions in v variables with thefollowing properties:(a) There exists rℓ <∞ such that fℓ is rℓ times strictly differentiable.(b) For each ℓ, some partial derivative of fℓ of order rℓ ≥ 1 does not vanishat any point of Bv.Then there exists a set E ⊆ B of Hausdorff dimension at least 1v−1 andMinkowski dimension 1 such that fℓ(x1, . . . , xv) is not equal to zero for anyv-tuple of distinct points x1, . . . , xv ∈ E and any function fℓ.This theorem does not have the same consequences regarding, say, isosce-les triangles for non-archimedean local fields as Theorem 1.1.1 does for thereal numbers. This is because, for a fixed x and for y not close to x, thedistance function d(x, y) on Kn is a locally constant function of y, so thepartial derivative condition does not hold. Nonetheless, many importantfunctions on local fields, such as the exponential function, are defined bypower series and thus Theorem 1.2.2 applies to them.41.2. Sets Avoiding Configurations in Local FieldsTheorem 1.2.3 (Theorem 1.3 from [18]). Let K = Qp and R = Zp, or letK = Fq((t)) and R = Fq[[t]]. Fix a ball B ⊂ R and positive integers m,n, vsuch that v ≥ 3, and m ≤ n(v − 1). Let fℓ : (Rn)v → Km be a countablefamily of twice strictly differentiable functions with the following property:the first derivative Dfℓ has full rank on the portion of the zero set of fℓcontained in Bnv for every ℓ.Then there exists a set E ⊆ Bn of Hausdorff dimension at least mv−1 andMinkowski dimension n such that fℓ(x1, . . . , xv) is not equal to zero for anyv-tuple of distinct points x1, . . . , xv ∈ En and any function fℓ.Again, caution is required when considering functions involving distance:unlike the Euclidean case, the distance function does not satisfy the require-ments of this theorem.Theorem 1.2.4 (Theorem 1.4 from [18]). Let K = Qp and R = Zp, orlet K = Fq((t)) and R = Fq[[t]]. Given any constant C > 0 and a vectorα ∈ Kv such thatα · u 6= 0 for every u ∈ {0, 1}v with u 6= 0, u 6= (1, 1, . . . , 1) (1.5)and such thatv∑j=1αj = 0, (1.6)there exists a positive constant c(α,K) and a set E = E(C,α,K) ⊆ R ofHausdorff dimension c(K,α) > 0 with the following property.The set E does not contain any nontrivial solution of the equationf(x1, · · · , xv) = 0, x1, · · · , xv not all identical,for any twice strictly differentiable function f of the formf(x1, · · · , xv) =v∑j=1αjxj +G(x1, · · · , xv) (1.7)where |G(x)| ≤ Cv∑j=2|xj − x1|2. (1.8)Here, the absolute value on K is chosen so that a uniformizing elementt satisfies |t| = q, where q is the number of elements of Fq in the case ofFq((t)) or q = p in the case of Qp.51.3. Besicovitch SetsThis theorem, once again, can be used to find large sets that avoidconfigurations that are “close” to 3-term arithmetic progressions. However,unlike the Euclidean case, this will not map to a set that is free of isoscelestriangles under a strictly smooth function γ. However, it will map to a setthat is free of triples (xj, yj) ∈ K2 : j = 1, 2, 3 such that, for example,exp(y3 − y2) + exp(x3 − x2) = exp(y2 − y1) + exp(x2 − x1). To see this,consider three points t1, t2, t3: under the map γ(t) = (x(t), y(t)), we wantto avoid solutions toexp(y(t3)−y(t2))+exp(x(t3)−x(t2)) = exp(y(t2)−y(t1))+exp(x(t2)−x(t1)).Near the diagonal (t, t, t) the linearization of this equation isy′(t)(t3 − t2) + x′(t)(t3 − t2) = y′(t)(t2 − t1)x′(t)(t2 − t1)This simplifies to(x′(t) + y′(t))(t3 − 2t2 + t1) = 0so, regardless of the function (x(t), y(t)), so long as x′(t) + y′(t) does notvanish, the linearization is t3− 2t2+ t1 and therefore Theorem 1.2.3 appliesprovided that x′(t)+y′(t) remains bounded and that x′′(t) and y′′(t) remainbounded.1.3 Besicovitch SetsA Besicovitch set in Rn is a set that contains a line segment of length 1 inevery direction. Besicovitch [3] constructed the first example of Besicovitchsets in Rn, n ≥ 2 with Lebesgue measure zero. A brief introduction to thetheory of Besicovitch sets in Rn is presented in Chapter 6.Let K be a non-archimedean local field. In contrast to the Rn definition,a subset E of Kn is called a Besicovitch Set if it contains a line in everydirection; that is, for every vector v ∈ Kn, there is a point x ∈ Kn suchthat the lineℓ = {x+ tv : t ∈ K}is contained in E. Note that t ranges over all of K and not just a subset.Although Besicovitch sets in Kn had been previously constructed byWright, the construction was unavailable in the literature. In [20], a con-struction of a measure-zero Besicovitch set is presented. In the process ofconstructing this set, the following result is established.61.4. Salem SetsTheorem 1.3.1 (Wisewell function for non-archimedean local fields, [20,Theorem 1.1]). Let R = Zℓ or R = Fℓ[[t]]. Let K be the field of fractions of R(i.e., K = Qℓ or Fℓ((t))). There is a continuous function φ : Kp → Kq withthe following property. Let f(x, y) : Kp ×Kq → Kn−d where p ≤ n− d ≤ qbe a measurable function that is very strongly differentiable in the x and yvariables on every compact subset of Kp ×Kq, and such that the Jacobian∂f/∂y has full rank a.e. in x and y with respect to the Haar measure onKp ×Kq. Then the set{f(x, φ(x)) : x ∈ Kp}has measure zero with respect to the Haar measure on Kn−d.This is an equivalent of a result of Wisewell [52] for the non-archimedeanlocal fields Qℓ and Fℓ((t)).Theorem 1.3.1 requires that R is a complete discrete valuation ring,which was erroneously omitted from the assumptions in [20]. One distinctivefeature here is that the function described in Theorem 1.3.1 is continuous,which contrasts with the real-variable case.Theorem 1.3.1 allows for the construction of Besicovitch sets of measurezero. In fact, it allows for the construction of sets containing a smoothly-parameterized family of smooth surfaces, provided that the family of surfacessatisfies appropriate dimensionality conditions.Theorem 1.3.2 (Wisewell Set for Non-Archimedean Local Fields, [20, The-orem 1.2]). Let K be either Qp or Fq((t)), and let f(x, y, w) : Kp×Kq×Kd →Kn−d be a measurable function such that f(·, ·, w) satisfies the same differ-entiability properties in the x and y variables as in Theorem 1.3.1. Thenthe setT := {(w, z) : z = f(x, φ(x), w);x ∈ Kp, w ∈ Kd}has measure zero with respect to the Haar measure on Kn.The proof of this theorem, as well as some applications, is given in Chap-ter 7.1.4 Salem SetsThe Fourier dimension of a set E ⊂ Rn relates to the decay of the Fouriertransform of measures supported on E. A set that is additively randomor curved will have large Fourier dimension. If the Hausdorff dimension ofE is equal to its Fourier dimension, E is called a Salem set. Salem sets71.4. Salem Setsand Fourier dimension on Rn and on Kn will be discussed in more detail inChapter 8.Most known examples of Salem sets in Rn of non-integer dimension areconstructed through random constructions. The first such construction wasdue to Salem [44]. Kaufman [27] gave an explicit example of a Salem setin R. Kaufman’s example consists of well-approximable numbers and isdiscussed in more detail in Chapter 8. A detailed exposition of Kaufman’sresult was authored by Bluhm [4].The study of Salem sets over non-archimedean local fields was initiatedby Papadimitropoulos. Papadimitropoulos adapted Salem’s construction inorder to locate Salem sets in Qp [40], and later over every non-archimedeanlocal field [39].In a joint work with Hambrook, we identify an explicit Salem set in thelocal field Qp and its ring of integers Zp. Our set is given byW (τ) = {x ∈ Zp : |xq − r|p ≤ max(|q|, |r|)−τfor infinitely many (q, r) ∈ Z2}.Theorem 1.4.1 (Theorem 1.4.1 from [21]). For every τ > 2, W (τ) isa Salem set with Hausdorff and Fourier dimension 2/τ . Moreover, thereexists a Borel probability measure µ supported on E(τ) such that|µ̂(ξ)| . |ξ|−1/τp log3(1 + |ξ|p) ∀ξ ∈ Qp, ξ 6= 0We also obtain a Fourier dimension bound on a related set W (m,n, τ)in Zm·np defined byW (m,n, τ) = {x ∈ Zmnp : ‖xq − r‖p ≤ max(|q|, |r|)−τfor infinitely many (q, r) ∈ Zn × Zm}.The Fourier dimension bound obtained on this set is not sufficient to showthat W (m,n, τ) is a Salem set.Theorem 1.4.2. For every τ > (m+n)/m, there exists a Borel probabilitymeasure µ supported on W (m,n, τ) such that|µ̂(ξ)| . |ξ|−n/τp logn+2(1 + |ξ|p) ∀ξ ∈ Qmnp , ξ 6= 0.Background on Fourier analysis on non-archimedean local fields will begiven in Chapter 8, and the proofs of Theorems 1.4.1 and 1.4.2 will be givenin Chapter 9.81.5. Layout1.5 LayoutChapter 2 introduces the concepts of Hausdorff dimension and Minkowskidimension, which will be used throughout the thesis. Frostman’s lemma,which is used in several later chapters, is introduced here. All of the back-ground necessary for Chapter 3 is presented in Chapter 2.Chapter 3 concerns the proof of Theorems 1.1.1, 1.1.2, and 1.1.3. Someexamples of these theorems are discussed.Chapter 4 discusses local fields, with a particular focus on the p-adicnumbers Qp and the function field Fq((t)). The material in this chapter isused in all subsequent chapters.Chapter 5 contains the proof of Theorems 1.2.1, 1.2.2, 1.2.3, and 1.2.4.Some differences between these Theorems and their Euclidean counterpartsare discussed.Chapter 6 discusses the theory of Besicovitch sets in both the Euclideanand Local Field settings. This material sets the stage for Chapter 7.Chapter 7 discusses the proof of Theorems 1.3.1 and 1.3.2. Some specificexamples of these theorems are also presented.Chapter 8 concerns Salem sets as well as p-adic Fourier analysis. A de-scription of the characters on Qp is presented as well as some basic theoremsof Fourier analysis on Qp.Chapter 9 contains the proof of Theorems 1.4.1 and 1.4.2. The chapterconcludes with a brief discussion of the gap between the Hausdorff dimensionof W (m,n, τ) and the Fourier dimension computed in Theorem 2Dimensions of Sets2.1 Minkowski DimensionIn the context of fractal sets, it is useful to have a notion of dimension thatallows for non-integer dimensions. One notion of dimension that plays animportant role in geometric measure theory is Minkowski (or box-counting)dimension.Let E ⊂ Rn be compact. Consider covers of E by balls of radius r. If Eis, for example, a line segment of length ℓ, then E can always be covered byℓr−1 + O(1) balls of radius r. If E is a square of side length ℓ, then E canbe covered by ℓ2r−2 +O(1) balls of radius r. The main feature here is thatthe exponent on r is −1 in the case of a line segment (which should havedimension 1), and the exponent on r is −2 in the case of a square (whichshould have dimension 2).This motivates a definition for the Minkowski dimension of a set E:Definition 2.1.1 (Definition of Minkowski Dimension). Let E ⊂ Ω ⊂ Rnwhere Ω ⊂ Rn is compact, and E is a Borel set. Let Cr(E) be the minimalnumber of balls of radius r in Rn required to cover E. Then we define theupper Minkowski dimension of E bydimME = lim supr→0− logCr(E)log rand the lower Minkowski dimension of E bydimME = lim infr→0− logCr(E)log r.If these two dimensions are the same, we call this quantity the Minkowskidimension of E [35, Section 5.3].The upper and lower Minkowski dimension measure the size of the set Eat different scales r. A set with large upper Minkowski dimension appearslarge at some sequence of scales r approaching zero; a set with large lowerMinkowski dimension appears large at all sufficiently small scales.102.2. Hausdorff DimensionThe Minkowski dimension can often behave unpredictably. For example,the Minkowski dimension is not countably stable. A standard example ofthis is the family of points {1/n : n ∈ N} ∪ {0}. Each singleton {1/n} hasMinkowski dimension 0 (since it can always be covered by a single ball ofarbitrarily small radius), so we would expect that this set {1/n : n ∈ N}∪{0}should also have Minkowski dimension 0. However:Example 2.1.2 (Countable set with positive Minkowski dimension). Theset of pointsE := {1/n : n ∈ N} ∪ {0}has Minkowski dimension 12 .Proof. Consider coverings of E by balls of radius r := t−2 for some t ∈ R.For any k > t, we have1k− 1k + 1=1k2 + k≤ 1k2≤ t−2.Therefore, E contains a point in each t−2 neighbourhood of any x ∈ [0, t−1].It follows that at least t/3 balls are necessary to cover all of E, and sincet = r−1/2 we have that the lower Minkowski dimension of E is at least 12 .Conversely, let t ∈ R. Then the number of k such that 1k > t−1 is atmost t. Therefore, the set [t−1, 1] ∩ E can be covered by at most t balls ofradius t−2. Using the fact that [0, t−1] can be covered by t balls of radiust−2, we conclude that E can be covered by at most t balls of radius t−2,which shows that the upper Minkowski dimension of E is at most 1/2. This example shows that a countable compact set can have positiveMinkowski dimension. The bizarre behaviour exhibited by this exampleoccurred because the balls were required to have the same radius. If weinstead allow for coverings by balls of different radii, we arrive at a notionof dimension that is compatible with countable unions.2.2 Hausdorff DimensionDefinition 2.2.1 (Definition of Hausdorff Dimension). Let E ⊂ Ω ⊂ Rnwhere Ω is compact and E is a Borel set. We define the quantities Hsr (E)byinfU∑U∈Udiam(U)swhere the infimum is taken over collections U of balls of diameter at mostr that cover E. Evidently the infimum will increase as r decreases since the112.2. Hausdorff Dimensioninfimum is taken over a smaller set of coverings. Define the s-dimensionalHausdorff measure of E by:Hs(E) := limr→0Hsr (E).The expressions Hs are Borel measures [35, Theorem 4.5]. There exists aunique s0 such that Hsr (E) = ∞ for s < s0 and Hsr (E) = 0 for s > s0 [35,Theorem 4.7]. This exponent s0 is called the Hausdorff dimension of E[35, Definition 4.8].We will now show that the countable set in Example 2.1.2 has Hausdorffdimension zero.Example 2.2.2 (Computation of Hausdorff dimension for a countable set).The set of pointsE := {1/n : n ∈ N} ∪ {0}has Hausdorff dimension 0.Proof. Let s, r > 0 and let 0 < ǫ < r2 . We will define the covering Us,ǫ inthe following way: Place a ball of diameter ǫn−2/s centered at each point 1n ,and a ball of diameter ǫ centered at 0. Clearly U covers E, each ball of Uhas radius at most 2ǫ < r, and we have that∑u∈Us,ǫdiam(U)s = ǫs + ǫs∞∑n=1n−2 = (1 + π2/6)ǫsThis quantity approaches 0 as ǫ → 0. Therefore Hsr (E) = 0 for everyr, s > 0 and Hs(E) = 0 for every s > 0. This establishes that the Hausdorffdimension of E is 0. In fact, the proof given in Example 2.2.2 can be modified to show that theHausdorff dimension of any countable set is zero. This example illustrateshow Definition 2.2.1 is useful when obtaining upper bounds for the Hausdorffdimension of a Borel set E: all that needs to be done is to show that thereexist coverings Uj of E such that∑U∈Uj diam(U)s → 0. On the other hand,using this definition to obtain lower bounds on the Hausdorff dimension ofa Borel set E can be more involved: in order to obtain lower bounds, it isnecessary to consider all coverings of E by balls of radius at most r, andconsider the behaviour as r → 0.122.3. Frostman’s Lemma2.3 Frostman’s LemmaIt is usually better to refer to Frostman’s lemma [22] when computing lowerbounds for the Hausdorff dimension of a set. Frostman’s lemma relates theHausdorff dimension of a Borel set E to the behaviour of Borel measuressupported on E. We present the version of Frostman’s lemma appearing inWolff’s lecture notes [55, Proposition 8.2].Theorem 2.3.1 (Frostman’s Lemma). Let E be a Borel set in Rn. Thenthe Hausdorff dimension of E is the supremum of the values of t such thatE supports a Borel probability measure µ with the property that, for all ballsB ⊂ Rn,µ(B) .t,µ diam(B)t.Since µ is a probability measure, the ball condition from Theorem 2.3.1is automatically satisfied for large balls B, and this characterization onlydepends on the small-scale behaviour of the measure µ.Example 2.3.2 (The Cantor middle-thirds set has Hausdorff dimensionlog 2log 3). We will define a sequence Ej of nested sets in the following way. Theset E0 = [0, 1]. For j > 0, Ej will be obtained from Ej−1 by deleting the(open) middle third of each interval in Ej−1. ThusE1 = [0, 1] \ (1/3, 2/3)= [0, 1/3] ∪ [2/3, 1],andE2 = ([0, 1/3] \ (1/9, 2/9)) ∪ ([2/3, 1] \ (7/9, 8/9))= [0, 1/9] ∪ [2/9, 1/3] ∪ [2/3, 7/9] ∪ [8/9, 1].The intervals that constitute Ej are called the jth stage basic intervals ofE. We define E =⋂∞j=1Ej . Then the set E has Hausdorff dimensionlog 2/ log 3.Proof. To see that E has Hausdorff dimension at most log 2/ log 3, considerthe sequence of coverings Uj,ǫ of E obtained by extending the basic intervalsof E by ǫ. We extend by ǫ because the balls in our covering are technicallyrequired to be open. This gives a family of 2j balls of radius 3−j + ǫ.Therefore, we have that Hs1(E) ≤ 2j(3−j + ǫ)s ≤ Cs2j3−js+2jǫs. If we haves > log 2/ log 3, then this quantity goes to zero as ǫ → 0 and j → ∞, soHs1(E) = 0 and thus Hs(E) = 0.132.3. Frostman’s LemmaTo see that E has Hausdorff dimension at least log 2/ log 3, we will definea measure µ on E satisfying the condition in Theorem 2.3.1. To do this,we define the measures dµj(x) =1Ej|Ej |dx to be the uniformly distributedprobability measure on Ej . The measure µ will be taken to be the weaklimit of these measures. We have that µk(F ) = µj(F ) = 2−j for any j-th level basic interval F . Each such interval has Lebesgue measure 3−j ,and a simple geometric argument shows that no intervals of length 3−j canbe assigned a µk-measure larger than 2−j for any k ≥ j. It remains toshow the ball condition for intervals of length between 3−j−1 and 3−j . Ofcourse, such intervals can only intersect at most 3 of the j + 1-stage basicintervals occurring in the construction of E, and therefore will be assigneda µ-measure of no more than 3×2−j−1. In any case we get a bound of C2−jon the µk measures of any such interval for k ≥ j. Passing to the weaklimit gives that the same holds for µ and therefore that E has Hausdorffdimension log 2log 3 . This example illustrates the power of Frostman’s lemma: by placing anatural measure on the set E, we manage to obtain an optimal lower boundon the Hausdorff dimension of E.Frostman’s lemma has a formulation in terms of energy integrals fromMattila’s textbook [36, Section 2.5].Definition 2.3.3 (Definition of s-energy of a measure). Let µ be a BorelMeasure. Then the s-energy Is(µ) is defined by the integralIs(µ) =∫∫x,y|x− y|−sdµ(x)dµ(y).We are interested in when the energy integral Is(µ) is finite. Notice thatthe singularity becomes more severe the larger s is. The following theoremrestates Frostman’s lemma in terms of energy integrals [36, Theorem 2.8].Theorem 2.3.4 (Energy integral formulation of Frostman’s lemma). If E ⊂Ω ⊂ Rn is a Borel set, where Ω is compact, then the Hausdorff dimension ofE is the supremum value of t such that there exists a measure µt supportedon E such that It(µt) <∞.There is a Fourier-analytic expression for the energy integral Is(µ) [36,Theorem 3.10].Theorem 2.3.5 (Fourier-analytic expression for energy integrals). Let µ bea compactly supported Borel probability measure. ThenIs(µ) = C(n, s)∫|µ̂(ξ)|2|ξ|s−n dξ142.3. Frostman’s Lemmafor some constant C(n, s) depending only on n and s.Combining Theorem 2.3.5 and Theorem 2.3.4 gives a Fourier-analyticversion of Frostman’s lemma:Corollary 2.3.6 (Fourier-analytic version of Frostman’s lemma). Let E ⊂Ω ⊂ Rn be a Borel set, where Ω is compact. Then the Hausdorff dimensionof E is the supremum value of t such that there exists a measure µt supportedon E such that(1|B(0, r)|∫B(0,r)|µ̂t(ξ)|2dξ)1/2.µt,t (1 + |ξ|)−t/2.The left-hand side of this expression is an L2-average of µ̂ over the ballof radius r centered at 0.15Chapter 3Configurations3.1 Background3.1.1 Two Constructions of KeletiIn 1998, Keleti [28] constructed a set E of Hausdorff dimension 1 such thatE does not contain 4 points x1, x2, x3, x4 such thatx2 − x1 = x4 − x3for any x1 < x2 ≤ x3 < x4 ∈ E. Keleti later modified this construction in2008 [29].Theorem 3.1.1. [Keleti’s construction of a set avoiding countably manylinear configurations] Let {αj} be a countable collection of real numbersstrictly greater than 1. Then there exists a set E ⊂ R of Hausdorff di-mension 1 such that the equationx3 − x1 = αj(x2 − x1) (3.1)does not have any solutions for distinct x1, x2, x3 ∈ E.Keleti constructs the set E using a Cantor-like construction that is sum-marized here. The construction begins with the set E0 = [0, 1], and con-tinues in the following way. Given a set Ek, which is a union of m1 · · ·mkintervals of length δk. mk and δk are chosen appropriately in order to guar-antee that the set E has Hausdorff dimension 1.Given Ek, Keleti effectively constructs a list of triples of intervalsΓ′k := {(Ika , Ikb , Ikc ) : a, b, c ∈ N; a < b < c ≤ m1 · · ·mk}.Keleti does not give an explicit ordering on this list Γ′k, but for simplicity andby analogy to the rest of the section, we will order the list lexicographicallyin the triple (a, b, c). We define the queueΓk :=k⋃j=1Γ′j .163.1. BackgroundThis list contains all of the triples of intervals at stage j for every j < k.At step k, we consider the kth element of the queue Γk. This will consistof a triple of intervals, which Keleti calls (Jk,Kk, Lk). Given Ek−1, Keletidefines Ek so that (3.1) does not have any solutions for x1 ∈ Ek−1 ∩ Jk,x2 ∈ Ek−1 ∩Kk, or x3 ∈ Ek−1 ∩ Lk.To do this, Keleti retains subintervals of each interval I in Ek−1 accordingto whether I ⊂ Jk, I ⊂ Kk, I ⊂ Lk, or I ⊂ Ek−1 \ (Jk ∪ Kk ∪ Lk). Forintervals I ⊂ Jk, Keleti retains mk subintervals of length δk whose leftendpoint is of the form 3(i+ 12)αkδkαk−1 for some integer i. For I ⊂ Kk, Keletiretains mk intervals of length δk with left endpoints of the form 3jαkδk forsome j ∈ Z. For I ⊂ Lk, Keleti retains mk intervals of length δk with leftendpoints of the form 3ℓδk for some ℓ ∈ Z. For other intervals I, Keletidoes not impose any restrictions other than that mk intervals of length δkare retained, and that the retained intervals are separated by at least δk. Aquick algebraic calculation shows that there are no x1, x2, x3 satisfying (3.1)with x1 ∈ Jk ∩ Ek, x2 ∈ Kk ∩ Ek, and x3 ∈ Lk ∩ Ek.A careful selection of the quantities δk and mk guarantees that E hasHausdorff dimension 1, and the fact that each triple (J,K,L) of intervals inEk occurs in each queue Γj for all j > k guarantees that there can be nonontrivial solution to (3.1).A similar principle to this queue is the key to the construction [19],conducted jointly with Malabika Pramanik, that is the main subject of thischapter.3.1.2 The Constructions of Maga and Ma´the´The construction in [28] was extended to Rd by Maga [33, Theorem 2.3]:Theorem 3.1.2. [Parallelogram-free set] For any d = 1, 2, · · · there existsa subset A of Rd of full Hausdorff dimension such that A does not containthe vertices of any parallelogram.This is a vector-valued version of the result appearing in [28], becausethe vertices of a parallelogram satisfy the equation (3.1).Maga also used a complex-valued version of Keleti’s argument [29] toestablish the following result in R2 [33, Theorem 2.8]:Theorem 3.1.3. [Set not containing similar copies of countably many tri-angles] Let {Pj} = (p(j)1 , p(j)2 , p(j)3 ) ⊂ R2×3 be a collection of triangles in R2;that is, p(j)1 , p(j)2 , p(j)3 are distinct for each j. Then there exists a compactE ⊂ R2 such that dimH(E) = 2 and E does not contain a triangle similarto any triangle Pj .173.1. BackgroundIn fact, Theorem 2.8 of [33] states this only for a single triangle P , butMaga observes at the beginning of Section 3 that the proof of this theoremcan be modified to show Theorem 3.1.3.Ma´the´ [34, Theorem 2.3] establishes a result that further generalizes theresults of Keleti and Maga.Theorem 3.1.4. [Set not containing any of a countable set of rational poly-nomial configurations] Let n ≥ 1. Let J be a countable set. For each j ∈ J ,let vj be a positive integer and let Pj : Rnvj → R be a (non identically zero)polynomial in nvj variables with rational coefficients. Assume that d is themaximum degree of the polynomials Pj (j ∈ J). Then there exists a compactset E ⊂ Rn of Hausdorff dimension n/d such that for every j ∈ J , E doesnot contain vj distinct points x1, . . . , xvj satisfying Pj(x1, . . . , xvj ) = 0.This theorem directly implies Keleti’s result [28] on parallelograms, andMaga’s result, Theorem 3.1.2. While it is not immediately apparent that thisimplies Theorems 3.1.1 or 3.1.3, the proof of this theorem yields a strongerresult mentioned later in the paper [34, Theorem 6.1]:Theorem 3.1.5. [Set not containing any of a countable set of rational poly-nomial configurations applied to diffeomorphisms] Let n ≥ 1. Let J be acountable set. For each j ∈ J , let vj be a positive integer, let Pj : Rnvj be a(non identically zero) polynomial in nvj variables with rational coefficients,and let Φj,1, . . . ,Φj,vj be C1-smooth diffeomorphisms of Rn. Assume that dis the maximum degree of the polynomials Pj (j ∈ J). Then there exists acompact set E ⊂ Rn of Hausdorff dimension n/d such that for every y ∈ J ,E does not contain vj distinct points x1, . . . , xmj satisfyingPj(Φj,1(x1), . . . ,Φj,vj(xvj )) = 0.This theorem immediately implies Theorem 3.1.1, since the functions(x3 − x1) − αj(x3 − x2) are polynomials in x1, αjx2, and (αj − 1)x3, andmultiplication by αj and by αj−1 is a diffeomorphism of R. Less obviously,it also implies Theorem 3.1.3 using a similar argument where the αj arereplaced by similarity matrices Aj. This argument does not work in dimen-sions 3 and higher because there is no unique similarity carrying the vectorsb− a to c− a in the class of triangles abc that are similar to a given triangleT .We now discuss the main results of [19]: Theorems 1.1.1, 1.1.2, and Discussion of Main Results3.2 Discussion of Main Results3.2.1 Nonsimultaneous AvoidanceNotice that if Theorem 1.1.1 is being applied to a single function f , thetheorem gives a nontrivial result only if the components of ∇f sum to zero;otherwise, a set E of positive measure can be constructed simply by takingan appropriate translate of a small interval centered at the origin.The points in E are taken to be distinct; however, this assumption cansometimes be circumvented by choosing the sequence fj appropriately. Forexample, suppose we wanted to, as in [28], avoid parallelograms of pointsthat satisfy(x4 − x3)− (x2 − x1) = 0where x3 could possibly equal x2. Then we can simply takef1(x1, x2, x3, x4) = (x4 − x3)− (x2 − x1)andf2(x1, x2, x3, x4) = x4 − 2x2 + x1.This trick is only possible if it preserves the nonvanishing condition on thepartial derivatives of f . Note that Theorem 1.1.1 gives a suboptimal resultin this instance: 1v−1 is only equal to13 , which is inferior to the Hausdorffdimension obtained by Keleti [28]. This example illustrates a weaknessof Theorem 1.1.1: this theorem gives poor bounds if the functions f arepolynomials of low degree with integer coefficients.Another weakness of Theorem 1.1.1 relative to other results in the litera-ture is that Theorem 1.1.1 requires that the number of variables be bounded.For example, a simple consequence of Theorem 3.1.4 is that there is a Haus-dorff dimension 1 subset of R that is linearly independent over Q. However,this example requires avoiding configurations with an arbitrary number ofvariables, so Theorem 1.1.1 does not apply to this example.For illustrative purposes, we give the following examples.Example 3.2.1 (Avoiding isosceles triangles). Let Γ be a C1 curve in Rd.How large a subset of Γ can be found that does not contain an isosceles trian-gle or 3-term arithmetic progression (which will be considered a degenerateisosceles triangle)?We can apply some of the results in the literature to this problem, as wellas Theorem 1.1.1. Theorem 3.1.1 applies if the curve Γ is a line segment:in this case Γ is parameterized by a function γ(t) where all components of193.2. Discussion of Main Resultsγ are affine-linear functions of t, so the problem is equivalent to finding a3-term AP-free subset of [0, 1], which was considered in [28]. The result inthis paper implies that we can find a subset of Γ of Hausdorff dimension 1that does not contain any 3-term arithmetic progressions.If the curve Γ has a parameterization given by γ(t) = (γ1(t), · · · γd(t))where each γj(t) is a polynomial with rational coefficients of degree at mostD, then we can apply Ma´the´’s result, Theorem 3.1.4. We assume thatthis parameterization is bi-Lipschitz, which can be guaranteed provided wechoose an appropriately small arc of Γ. We will define the functionf2(t1, t2, t3) :=d∑j=1(γj(t3)− γj(t2))2 −d∑j=1(γj(t2)− γj(t1))2,for t1 < t2 < t3, which is zero precisely when the distance between γ(t1)and γ(t2) is equal to the distance between γ(t2) and γ(t3). It is possible toargue, as in [19], that it suffices to apply Theorem 3.1.4 to this example.However, we will argue somewhat differently here. Letf1(t1, t2, t3) :=d∑j=1(γj(t3)− γj(t1))2 −d∑j=1(γj(t1)− γj(t2))2,andf3(t1, t2, t3) :=d∑j=1(γj(t2)− γj(t3))2 −d∑j=1(γj(t1)− γj(t3))2.Then locating E ⊂ [0, 1] such that there are no solutions to fk(t1, t2, t3) = 0for k = 1, 2, 3, we have that γ(E) will be a subset of Γ with no isoscelestriangles.So if each component of γ has degree at most D, then we can applyTheorem 3.1.4 to {f1, f2, f3} to locate a set E ⊂ [0, 1] of Hausdorff dimension12D such that γ(E) contains no isosceles triangles. Since γ is bi-Lipschitz,this implies that γ(E) also has Hausdorff dimension 12D .In fact, this result is improved by Theorem 1.1.1. Simply apply thistheorem to {f1, f2, f3}: each function is a real function of three real variables,so this theorem gives a set of Hausdorff dimension 12 that does not containany isosceles triangles.Here is another example of Theorem Discussion of Main ResultsExample 3.2.2 (A Transcendental Function). Consider the functionf(x1, x2, x3) = sin(x3 − x2)− (x2 − x1).How large a subset of R can we find that does not contain three pointsx1, x2, x3 that satisfy f(x1, x2, x3) = 0?There is no obvious family of diffeomorphisms φ1, φ2, φ3 such thatf(φ1(x), φ2(x), φ3(x)) is a polynomial. So we cannot apply Theorem 3.1.4.Nonetheless, Theorem 1.1.1 still applies, and we can locate a subset of R ofHausdorff dimension 12 that does not contain this configuration.We present an example of Theorem 1.1.2 with m > 1. In order topresent this example, we need a signed distance function d, defined along aparameterized curve γ(t). We defined(γ(t1), γ(t2)) ={|γ(t1)− γ(t2)| if t1 ≥ t2−|γ(t1)− γ(t2)| if t1 < t2.(3.2)The point of this definition is that the function d is differentiable in t1 andt2.Lemma 3.2.3 (Lemma 6.1 from [19]). Given a C2 parameterization γ :[0, η]→ Rn of a curve Γ. Then the distance functionF (t1, t2) := d(γ(t1), γ(t2)) is differentiable on [0, η]2. Furthermore, if γ isparameterized by its arclength; that is, |γ′(t)| ≡ 1, then∂F∂t1(t, t) = 1∂F∂t2(t, t) = −1Proof. We only need to check the case t1 = t2, since d is clearly differentiablefor t1 6= t2. Consider t1 = t2 = t. Let h ≥ k. ThenF (t+ h, t+ k) = d(γ(t+ h), γ(t + k)) = |γ(t+ h)− γ(t+ k)|= |γ′(t)| |h− k|+O(h2 + k2)= |γ′(t)|(h− k) +O(h2 + k2).Where we used the fact h ≥ k to conclude both that d(γ(t+ h), γ(t+ k)) =|γ(t+ h)− γ(t+ k)|, and that |h− k| = h− k.213.2. Discussion of Main ResultsIf h < k, we haved(γ(t+ h), γ(t + k)) = −|γ(t+ h)− γ(t+ k)|= −|γ′(t)| |h− k|+O(h2 + k2)= |γ′(t)|(h − k) +O(h2 + k2).This time, because h < k, we have d(γ(t+h), γ(t+k)) = −|γ(t+h)−γ(t+k)|,but we also have that |h− k| = −(h− k). The two minus signs “cancel out”and we therefore get that ∂f∂t1 = γ′(t) when t1 = t2 = t and ∂f∂t2 = −|γ′(t)|when t1 = t2 = t. In addition to the case t1 = t2 = t discussed in Lemma 3.2.3, we cancompute the derivative of d(γ(t1), γ(t2)) for t1 6= t2. If t1 > t2, thend(γ(t1), γ(t2)) is the usual distance |γ(t1) − γ(t2)|. The derivative of thisin the γ1 variable is precisely the quantityγ′(t1) · γ(t1)− γ(t2)|γ(t1)− γ(t2)| ,the projection of γ′(t1) onto the one-dimensional space spanned by the vectorγ(t1) − γ(t2). A similar argument allows for the calculation of the partialderivative in the t2 variable and the partial derivatives in the case wheret1 < t2.Example 3.2.4. Let Γ ⊂ R2 be a curve parameterized by a smooth functionγ : R→ R2. Call a trapezoid ABCD, with AD parallel to BC, special if itssidelengths satisfy the relation |BC|2 = |AB||CD|. How large a subset of Γcan we find that does not contain the vertices of any special trapezoid?If we take A = γ(t1), B = γ(t2), C = γ(t3), and D = γ(t4), we needt1, t2, t3, t4 to satisfy two linearly independent conditions: the sides AD andBC must be parallel, and the side lengths must satisfy the special relation.We then definef1(t1, t2, t3, t4) = det[(γ(t4)− γ(t1))t, (γ(t3)− γ(t2))t] (3.3)f2(t1, t2, t3, t4) = d(γ(t4), γ(t3))d(γ(t2), γ(t1))− d(γ(t3), γ(t2))2. (3.4)Here d(x, y) is the signed distance function given in equation (3.2), t rep-resents the transpose operation, and det represents the determinant. Thisdeterminant is zero if the vectors γ(t4)− γ(t1) and γ(t3)− γ(t2) are parallel(or if either vector is zero).223.2. Discussion of Main ResultsLemma 3.2.5 (Full Rank Condition for Special Trapezoids). Letting f =(f1, f2), The derivative Df has full rank on the points of the zero set of fwhere t1, t2, t3, t4 are distinct.It will follow from Lemma 3.2.5 and Theorem 1.1.2 that there is a set Eof Hausdorff dimension 23 that does not contain any special trapezoids. Wenow prove this lemma.Proof of Lemma 3.2.5, Lemma 6.3 of [19]. By symmetry, and by taking asmall enough arc of Γ, we can (and do) assume Γ is strictly convex, andthat all components of γ′ are positive. We consider the 2-by-2 submatrixof Df consisting of the entries ∂fi/∂tj where i ∈ {1, 2} and j ∈ {1, 4}.We aim to show that this submatrix has nonzero determinant, which willbe accomplished by showing that ∂f1/∂tj is nonzero for j = 1, 4, and thatthese two derivatives have the same sign, but ∂f2∂tj are nonzero and haveopposite signs. This is sufficient to show that the second row of the Jacobianis not a scalar multiple of the first row; therefore, Df must be nonsingular.We begin by computing the derivatives ∂f1/∂tj on the set of t1, t2, t3, t4for which f1 is zero. On this set, we haveγ2(t3)− γ2(t2)γ1(t3)− γ1(t2) =γ2(t4)− γ2(t1)γ1(t4)− γ1(t1) . (3.5)In words, this equation says that the slope of the line connecting γ(t2) toγ(t3) is equal to the slope of the line connecting γ(t1) to γ(t4).If we write out the determinant in (3.3) explicitly, we get the expressionf1(t1, t2, t3, t4) := (γ1(t4)− γ1(t1))(γ2(t3)− γ2(t2)) (3.6)− (γ2(t4)− γ2(t1))(γ1(t3)− γ1(t2)) (3.7)Therefore, we have the partial derivatives∂f1∂t1= −γ′1(t1)(γ2(t3)− γ2(t2)) + γ′2(t1)(γ1(t3)− γ1(t2)) (3.8)∂f1∂t4= γ′1(t4)(γ2(t3)− γ2(t2))− γ′2(t4)(γ1(t3)− γ1(t2)). (3.9)We can substitute (3.5) into (3.8) and (3.9):∂f1∂t1= −γ′1(t1)(γ1(t3)− γ1(t2))γ2(t4)− γ2(t1)γ1(t4)− γ1(t1) + γ′2(t1)(γ1(t3)− γ1(t2)).∂f1∂t4= γ′1(t4)(γ1(t3)− γ1(t2))γ2(t4)− γ2(t1)γ1(t4)− γ1(t1) − γ′2(t4)(γ1(t3)− γ1(t2)).233.2. Discussion of Main ResultsWe now let F1 and F4 be defined by F1 =[−γ2(t4)−γ2(t1)γ1(t4)−γ1(t1) +γ′2(t1)γ′1(t1)]and F4 =[γ2(t4)−γ2(t1)γ1(t4)−γ1(t1) −γ′2(t4)γ′1(t4)]. With these definitions, we arrive at the equations∂f1∂t1= γ′1(t1)(γ1(t3)− γ1(t2))F1 (3.10)∂f1∂t4= γ′1(t4)(γ1(t3)− γ1(t2))F4. (3.11)It is now time to use our assumptions about γ. By assumption, γ′1 is non-negative, and therefore, the sign of ∂f1∂t1 ·∂f1∂t4is equal to the sign of F1F4.The expressions for F1 and F4 are handled using the convexity of γ. Thequantityγ′2(t1)γ′1(t1)is the slope of the tangent line to γ at t1,γ′2(t4)γ′1(t4)is the slopeof the tangent line to γ at t4, andγ2(t4)−γ2(t1)γ1(t4)−γ1(t1) is the slope of the secant lineconnecting γ(t1) to γ(t4). The convexity of Γ thus guarantees that F1 andF4 have the same sign, and thus that∂f1∂t1and ∂f4∂t4 also have the same sign.Now, we need to show that ∂f2∂tj have opposite signs for j = 1 and j = 4.Evidently f2 is nonzero if t4−t3 and t2−t1 have opposite signs. So we assumethat t4 − t3 and t2 − t1 have the same sign: (t4 − t3)(t2 − t1) > 0. From thediscussion following the proof of Lemma 3.2.3, we have the equations∂∂t4d(γ(t4), γ(t3)) = γ′(t4) · γ(t4)− γ(t3)|γ(t4)− γ(t3)|and∂∂t1d(γ(t2), γ(t1)) = −γ′(t1) · γ(t2)− γ(t1)|γ(t2)− γ(t1)|Thus∂f2∂t4= γ′(t4) · γ(t4)− γ(t3)|γ(t4)− γ(t3)|d(γ(t2), γ(t1)) (3.12)∂f2∂t1= −γ′(t1) · γ(t2)− γ(t1)|γ(t2)− γ(t1)|d(γ(t4), γ(t3)) (3.13)(3.14)Here, γ′(t4) · (γ(t4)− γ(t3)) has the same sign as γ′(t1) · (γ(t2)− γ(t1)), andd(γ(t2), γ(t1)) and d(γ(t4), γ(t3)) have the same sign because t4 − t3 andt2 − t1 have the same sign. Thus ∂f2∂t1 and∂f2∂t4have opposite signs. 243.2. Discussion of Main Results3.2.2 Polygons and PolyhedraFor example, consider the problem of finding a subset of R2 that does notcontain any equilateral triangles. Maga [33] has shown that it is possible tofind such a set with Hausdorff dimension 2. This is a 3-point configuration(hence v = 3) consisting of points (x1, x2, x3) that satisfy the conditions:d(x1, x2) = d(x1, x3) and d(x1, x2) = d(x2, x3). Here d(x, y) is the usualEuclidean distance from x to y: a function that is differentiable on the setof points where x1, x2 and x3 are distinct. So, for this example, we havem = 2 and v = 3, so Theorem 1.1.2 will give a set of Hausdorff dimension 1that does not contain any equilateral triangles. Not only is this inferior toMaga’s result, it is entirely trivial: a line, for example, is a set of Hausdorffdimension 1 that does not contain any equilateral triangles.The situation is improved somewhat if we consider regular polygons withmore sides. For example, a square in R2 is a family of 4 points (xj , yj) : j =1, 2, 3, 4 satisfying the following family of equations:(y2 − y1)2 + (x2 − x1)2 = (y3 − y1)2 + (x3 − x1)2(x2 − x1)(y2 − y1) = −(x3 − x1)(y3 − y1)(y2 − y4)2 + (x2 − x4)2 = (y3 − y4)2 + (x3 − x4)2(x2 − x4)(y2 − y4) = −(x3 − x4)(y3 − y4)Where (x1, y1), (x2, y2), (x3, y3), and (x4, y4) are distinct. Notice that aslong as these points are distinct, the corresponding Jacobian matrix has fullrank. Thus Theorem 1.1.2 applies (with n = 2,m = 4, v = 4) to give a setof Hausdorff dimension 43 that does not contain the vertices of any square.This dimension can be taken to be as large as 2v−4v−1 if the configuration tobe avoided is a regular v-gon. Note that even this bound, while nontrivial,is inferior to that of Maga: Maga’s result can be applied to any 3 points ina regular v-gon in order to find a subset of R2 of Hausdorff dimension 2 thatdoes not contain any regular v-gons.Ma´the´ poses the problem of finding a set of large Hausdorff dimensionin R3 that does not contain any regular tetrahedron [34, Remark 6.3]. Un-fortunately, Theorem 1.1.2 does not shed any light on this question: thereare 4 points in a regular tetrahedron that satisfy 5 conditions, giving a setof Hausdorff dimension 1 that does not contain a regular tetrahedron. Thisbound is, of course, unsatisfactory: a plane also does not contain any regulartetrahedra. Nonetheless, if we consider similarity classes of larger polyhe-dra, we can get a nontrivial result. For example, a regular dodecahedron253.2. Discussion of Main Resultshas 20 vertices. After 2 vertices (x1, y1, z1) and (x2, y2, z2) are placed, avertex adjacent to (x1, y1, z1) must lie in a specific circle in R3. Once thispoint is placed, there are only a finite number of possible choices for theremaining points, so we can think of the 20 points of a regular dodecahe-dron as satisfying 53 independent conditions. Thus Theorem 1.1.2 gives aset of Hausdorff dimension 5319 that does not contain any regular dodecahe-dra. A similar argument can show that there is a subset of R3 of Hausdorffdimension 6v−92v−1 that does not contain a right v-prism, and a subset of R3of Hausdorff dimension 3v−7v−1 that does not contain any regular v-gon. Notethat these quantities approach 3 as v →∞.3.2.3 Simultaneous AvoidanceTheorem 1.1.3, although stated for a single configuration, can be modified(with a reduction in the Hausdorff dimension) to apply to a finite numberof configurations. However, the theorem does not apply for countably manyconfigurations.In order to shed some light on Theorem 1.1.3, we will consider an ex-ample similar to Example 3.2.1. Let Γ be a smooth curve with arclengthparameterization γ. This means that |γ′(t)| ≡ 1 for all t. Suppose the cur-vature of γ is bounded above by a constant, so that γ(t2) − γ(t1) is equalwithin K(t2− t1)2 of γ′(t1)(t2− t1) for t2, t1 with |t2− t1| sufficiently small.Then, for a fixed K, we have the following result.Example 3.2.6. For any fixed K > 0 There exists a set EK with posi-tive Hausdorff dimension (not depending on K) such that, for any curve γsatisfying the above conditions, γ(E) does not contain the vertices of anyisosceles triangle. The set E does not depend on the curve γ. Furthermore,the dimension of this set can be taken to be log 2log 3 .In fact, the set E that we will use is simply a slightly shrunken versionof the Cantor middle thirds set. We can arrive at the set E by applyingTheorem 1.1.3.Here, we will need the following lemma.Lemma 3.2.7 (Lemma 6.2 from [19]). Let γ : [0, η] → Rn be an injectiveparametrization of a C2 curve withγ′(0) 6= 0 and sup{||γ′′(t)|| : t ∈ [0, η]} ≤ K.If η is sufficiently small depending on |γ′(0)| and K, then there are no isosce-les triangles γ(t1), γ(t2), γ(t3) with 0 ≤ t1 < t2 < t3 ≤ η whose sides of equallength meet at γ(t1) or at γ(t3).263.3. A Single StepProof. We showed in Lemma 3.2.3 that d is differentiable. So we can writed(γ(t3), γ(t1))− d(γ(t2), γ(t1)) =∫ t3t2∂∂td(γ(t), γ(t1)) dt=∫ t3t2γ′(t) · γ(t)− γ(t1)|γ(t) − γ(t1)| dt.We estimate the direction vector γ(t)−γ(t1)|γ(t)−γ(t1)| as follows:γ(t)− γ(t1)|γ(t)− γ(t1)| =[γ′(t1)(t− t1) +O(K(t− t1)2)]| [γ′(t1)(t− t1) +O(K(t− t1)2)] |=γ′(t1) +O(Kη)|γ′(t1) +O(Kη)|=γ′(0) +O(Kη)|γ′(0) +O(Kη)|=γ′(0)|γ′(0)|[1 +O(Kη|γ′(0)|)].The estimate in the last line holds provided that η is sufficiently small be-cause the γ′(0) term in the denominator is nonzero and does not depend onη.This gives us, upon plugging into the integrand:γ′(t) · γ(t)− γ(t1)|γ(t)− γ(t1)| =[γ′(0) +O(Kη)] · γ′(0)|γ′(0)|[1 +O(Kη|γ′(0)|)]≥ |γ′(0)|26= 0,provided that η is sufficiently small. A similar argument shows that γ(t3)cannot be in the middle, either. Therefore, in order to avoid isosceles triangles in our example, it isenough to avoid the zeros of d(γ(t3), γ(t2)) − d(γ(t2), γ(t1)). But Lemma3.2 shows that the linearization of this function at a point (t, t, t) is alwayst3−2t2+t1, so Theorem 1.1.3 applies, giving a set E with positive Hausdorffdimension with the desired property. The specific bound dimE > log 2log 3 willbe calculated alongside the proof of Theorem A Single StepThe proofs of Theorems 1.1.1 and 1.1.2 are based on an iterative construc-tion. We will describe a typical step of this construction.273.3. A Single StepWe start with a function f : Rnv → Rm, and a set T ⊂ Rnv. We constructa set S ⊂ T such that f(x1, . . . , xv) is nonzero for (x1, . . . , xv) ∈ S. Thisdoes not immediately give the desired set, because S cannot be expressedas the v-fold product of a set in Rn with itself. This is similar to Keleti’sstrategy for proving Theorem One Dimension, Nonvanishing GradientWe will begin with a real-valued continuously differentiable function f inv variables with nonvanishing gradient defined in a neighbourhood of theorigin containing [0, η]v . Note that this assumption is stronger than theassumption in Theorem 1.1.1; nonetheless, an iterative argument will allowus to overcome this difficulty.Suppose that we are given i0 ∈ {1, 2, · · · v}, an integer M ≥ 1, a smallconstant c0 > 0 and compact subsets T1, . . . , Tv ⊂ [0, 1].1. Each Ti is a union of closed intervals of length M−1 with disjointinteriors. Let us denote by JM(Ti) this collection of intervals.2. The interior of Ti is disjoint from the interior of Ti′ if i 6= i′.3.∣∣∣ ∂f∂xi0 (x)∣∣∣ ≥ c0 and |∇f(x)| ≤ c−10 for all x ∈ T1 × · · · × Tv.Proposition 3.3.1 (Proposition 3.1 from [19]). Given f,M, i0, c0 and T =(T1, · · · , Tv) satisfying these assumptions, there exist a small rational con-stant c1 > 0 and an integer N0 (depending on all these quantities), for whichthe following conclusions hold.There is a sequence of arbitrarily large integers N ≥ N0 with NM , c1N ∈ Nsuch that for each N in this sequence, one can find compact subsets Si ⊆ Tifor all 1 ≤ i ≤ v such that(a) There are no solutions to f(x) = 0 with x ∈ S1 × · · · × Sv.(b) For each J ∈ JM(Ti), let us decompose J into closed intervals of lengthN−1 with disjoint interiors and call the resulting collection of intervalsIN (J, i). Then for each i 6= i0 and each I ∈ IN (J, i), the set Si ∩ I isan interval of length c1N1−v.(c) For every J ∈ JM (Ti0), there exists I ′N (J, i0) ⊆ IN (J, i0) with#(I ′N(J, i0)) ≥ (1− 1M )#(IN(J, i0)) (3.15)283.3. A Single Stepsuch that for each I ∈ I ′N (J, i0),|Si0 ∩ I| ≥c1N. (3.16)Unlike part (b), Si0∩I need not be an interval; however, it can be writtenas a union of intervals of length c1N1−v with disjoint interiors.The reader should imagine that N0 and thus N appearing in this propositionis much larger than M . Thus, accruing additional powers of M in thisargument will be considered only a small loss.Proof. In order to simplify the proof, we will assume without loss of gen-erality that i0 = v. The proof will proceed in the following manner: wewill select sets S1, . . . , Sv−1 using a very simple procedure, and then se-lect Sv to avoid the places where f(x1, . . . , xv) = 0 for some (x1, . . . , xv−1)in S1 × · · · × Sv−1. This is exactly the strategy that Keleti uses to proveTheorem 3.1.1.We select, for 1 ≤ i ≤ v − 1:Si =⋃{[ai, ai + c1N1−v] : [ai, bi] = I ∈ IN (Ji) for some J ∈ JM (Ti)}.Here, c1 is a small positive rational constant, and N will be specified later.This means that we take the leftmost interval of length c1N1−v of each 1N -interval that constitutes Ti. Part (b) of the proposition clearly holds for thischoice of Si.We define the family of points A in Rv−1 to be the bottom-left cornersof the Cartesian product of the Si for i ≤ v − 1:A :=v−1∏i=1{ai : [ai, bi] = I ∈ IN (J, i) for some J ∈ JM (Ti)}.Note that for each i, there are (assuming η < 1) at most N possible choicesfor ai; therefore, we have a bound#AN ≤ Nv−1. (3.17)In Lemma 3.3.2 we will show that for every fixed a′ ∈ AN , we have that#{xv : f(a′, xv) = 0} ≤M.We will defineB := {xv : ∃a′ ∈ AN such that f(a′, xv) = 0},293.3. A Single Stepa set that, by (3.17) and by Lemma 3.3.2 has at most MNv−1 elements.We select I ′N (J, v) ⊂ IN (J, v) as follows: we declare thatI ∈ I ′N (J, v) if #(B ∩ I) ≤ 2M3Nv−2.Now we do a quick count. There are at most MNv−1 points in B,and we have that if I ∈ IN(J, v) \ I ′N(J, v), there are at least 2M3Nv−2points of B in I. Because these intervals are essentially disjoint, it followsfrom the pigeonhole principle that there are at most M−2N intervals inIN (J, v) \ I ′N (J, v). Because there are NM intervals in IN (J, v) implies thebound in part (c) of the lemma.Now, we partition I ∈ I ′N (J, v) into consecutive subintervals of lengthC0c1/Nv−1 with disjoint interiors, and denote the successive intervals byI˜ℓ(I). Here, C0 is an integer depending on f , M , T1, . . . , Tv (but not on N)that will be specified in Lemma 3.3.3. It is convenient that c1 is rational, sothat we can select N in order to guarantee that Nv−2C0c1is an integer.We then discard intervals from I˜ℓ(I) that contain an element of B or areadjacent to an interval containing an element of B, as well as the leftmostand rightmost intervals of I˜ℓ(I). The union of the remaining intervals ischosen as Sv:Sv =⋃{I˜ℓ(I) :I˜k(I) ∩ B = ∅ for |k − ℓ| ≤ 1, I ∈ I ′N(J, v),J ∈ JM(Tv), 1 < ℓ < Nv−2/(C0c1)}.Sv is a union of intervals of length c1/Nv−1. Because of the way I ′N (J, v)was defined, there can only be at most 6M3Nv−2 + 2 ≤ 7M3Nv−2 removedintervals. This implies that the total length of the intervals removed is atmost7C0c1M3Nv−2/Nv−1. This is at most 7M3C0c1/N . This is bounded aboveby (1−c1)N provided that c1 is chosen small enough to guarantee that 7M3C0c1is no more than 1− c1.Then, by Lemma 3.3.3, given any x′ = (x1, . . . , xv−1) ∈ S1 × S2 ×· · · × Sv−1, we have that the xv such that f(x′, xv) = 0 must lie withina C0c1/Nv−1 neighbourhood of the set B. This establishes (a), completingthe proof of the Lemma. This selection algorithm ultimately results in a set of Hausdorff dimen-sion 1v−1 because of the factor of N1−v occurring in part (b) of the Lemma.Suppose that f : Rv → R is a linear function with nonzero integercoefficients:f(x1, . . . , xv) =v∑i=1αixi.303.3. A Single StepThis is the case in Keleti’s paper [28]. Without loss of generality, assumethat each Ti is a finite union of intervals J of the form Z/M + [0, 1/M ]. Wecould select Si for i < v differently from the method in Proposition 3.3.1.TakeSi ∩ I := [k/N, (k + c1)/N ]where c1 will be selected shortly. If xi ∈ Si for i < v, and f(x1, . . . , xv) = 0,then it is easily seen that xv has to be of the formxv = − 1αvv−1∑k=1αixi.If we select c1 such thatc1v−1∑i=1|αi| < 14,then we have that any such xv is within14|αv |N of an integer multiple of1|αv|N .dist(xv,Z|αv|N)<14|αv |N (3.18)whenever f(x1, . . . , xv) = 0 for some x1 ∈ S1, . . . , xv−1 ∈ Sv−1.Choose Sv as follows: for any I = |αv|−1[k/N, (k + 1)/N ] ⊂ Tv,Sv ∩ I := 1|αv |[kN+1− c12N,kN+1 + c12N].Now, we remember that c1 is bounded above by14 , so it follows that ifxv ∈ Sv∩I, then x is within c12N ≤ 18N of an odd multiple of 12N . This meansthat xv is a distance of at least38N from any integer multiple of1N . Thus,by (3.18), f(x1, . . . , xv) is nonzero for x1 ∈ S1, . . . , xv ∈ Sv.We now prove Lemmas 3.3.2 and 3.3.3, which will complete the proof ofProposition 3.3.1. Both of these lemmas will make use of the fact that ∂f∂xvis nonzero on T1 × · · · × Tv.Lemma 3.3.2 (Lemma 3.2 from [19]). Let AN and f be defined as in Propo-sition 3.3.1. Then we have that, for any fixed a′ in AN , there are at mostM numbers xv such that f(a′, xv) = 0.Proof. For any fixed a′ ∈ AN , we will consider the solutions to f(a′, xv) = 0with xv ∈ J for each J ∈ JM(Tv). Since the number of such J is at most313.3. A Single StepM , we will be done if we can show that there is at most one solution in eachsuch J .As a matter of fact, this follows directly from Rolle’s theorem and thefact that ∂f∂xv is nonzero on T1 × · · · × Tv. If we assume that there existx(1)v , x(2)v ∈ J such that f(a′, x(1)v ) = f(a′, x(2)v ) = 0, then Rolle’s theoremimplies that ∂f∂xv (a′, xv) must be equal to zero for some point in J , whichcontradicts the assumption on f . Lemma 3.3.3 (Lemma 3.3 from [19]). Let f,M, and T1, . . . , Tv be as inProposition 3.3.1. Then there exists an integer C0 depending on f,M, andon T1, . . . , Tv such that for the choice of S1, . . . , Sv−1 given in the proof ofProposition 3.3.1dist(xv,B) ≤ C0c1Nv−1for any xv such that f(x) = 0, where x′ = (x1, . . . , xv−1) ∈ S1 × · · · × Sv−1.Proof. Let J = J1 × · · · × Jv = J′ × Jv ∈∏vj=1 JM (Ti) be a v-dimensionalcube of sidelength 1M that contains a point of the zero set of f . Since∂f∂xvisnonvanishing on J, it follows from the implicit function theorem that existsa (v− 1)-variate C1 function gJ defined on J′ and a constant C0 (which canbe chosen to be an integer) such thatf(x) = 0, x ∈ J implies xv = g(J)(x′), (3.19)and|∇gJ| ≤ C0√von J′. (3.20)Given x = (x′, xv) ∈ S1 × · · · × Sv such that f(x) = 0, let Jx denote the v-dimensional 1m cube J in which x lies (if x lies on the boundary of such cubes,simply select one), and let I′x = I1 × · · · × Iv−1 =∏v−1i=1 [ai, bi] ∈∏ IN (Ji, i)be the (v − 1)-dimensional subcube of J′x of sidelength 1/N containing x′.Thenxv = gJ(x′), a′ = (a1, · · · , av−1) ∈ AN ,gJ(a′) ∈ B, and |x′ − a′| ≤ c1√vNv−1.Thus, we have that the distance from xv to B is bounded above by‖∇gJ‖∞ |x′−a′|. The bound (3.20) implies that ‖∇gJ‖∞ | is bounded aboveby C0√v, so we have that the distance from xv to B is bounded above byC0c1Nv−1 .323.3. A Single Step3.3.2 One Dimension, General CaseNow, our presentation will diverge somewhat from [19].Instead of directly using Proposition 3.3.1 as the basis for the construc-tion, we will iterate this proposition in order to prove a version that doesnot require the gradient to be nonvanishing. Proving this proposition nowwill greatly simplify the construction of the set in Theorem 1.1.1.We use the usual multi-index notation for derivatives: If α = (α1, . . . , αv)is a multi-index, we define |α| = α1 + · · · + αv. For a C |α| function f , wethen define∂αf =∂α1∂xα11· · · ∂αv∂xαvvf.Because f is assumed to be C |α|, the order of the partial differential operatorsis irrelevant.We will outline the assumptions required to state this proposition. Sup-pose that we have a multi-index α satisfying |α| = r, an integer M ≥ 1, asmall constant c0 > 0, compact subsets T1, . . . , Tv ⊂ [0, 1], and a Cr functionf . We will make the following assumptions:1. Each Ti is a union of closed intervals of length M−1 with disjointinteriors. Let us denote by JM (Ti) this collection of intervals. We willconsider a function f such that the derivative ∂αf is nonzero.2. The interior of Ti is disjoint from the interior of Ti′ if i 6= i′.3. The partial derivative ∂αf does not vanish on T1 × · · · × Tv, and isbounded below by c0 on this set.Proposition 3.3.4. Given f,M,α, c0 and T = (T1, · · · , Tv) satisfying theseassumptions, there exist a small rational constant c1 > 0 and an integer N0(depending on all these quantities), for which the following conclusions hold.There is a sequence of arbitrarily large integers N ≥ N0 with NM , c1N ∈ Nsuch that for each N in this sequence, one can find compact subsets Si ⊆ Tifor all 1 ≤ i ≤ v such that(a) There are no solutions to f(x) = 0 with x ∈ S1 × · · · × Sv.(b) For each J ∈ JM(Ti), let us decompose J into closed intervals of lengthN−1 with disjoint interiors and call the resulting collection of intervalsIN (J, i).333.3. A Single StepFor every J ∈ JM (Ti) and every i, there exists I ′N(J, i) ⊆ IN (J, i) with#(I ′N (J, i)) ≥ c2#(IN (J, i)) (3.21)such that for each I ∈ I ′N (J, i), |Si ∩ I| is nonempty. Si ∩ I need notbe an interval; however, it can be written as a union of intervals oflength c1N1−v with disjoint interiors. Here, c2 > 0 and may depend onf, r, v, c0, and M but not on N .We lose some control over the structure of the sets Sj in passing from Propo-sition 3.3.1 to Proposition 3.3.4. However, much of the structure of Propo-sition 3.3.1 is not necessary for the proof of Theorem 1.1.1.Given such a function f , we define, for 0 ≤ k ≤ r, a sequence of differ-ential operatorsDk = ∂αk∂xαkthat lead to α in the following way: αk−1 is obtained by reducing the largestentry of αk by 1, and leaving the others unchanged. In the case of a tie, wepick one maximal index arbitrarily. Then |αk| = k.We will prove Proposition 3.3.4 by induction: assuming we have setsT(k)1 × · · · × T (k)v on which Dkf is nonvanishing, we apply Proposition 3.3.1in order to locate S(k)1 , . . . , S(k)v on which Dk−1f is nonzero. We then takethe sets S(k)1 , . . . , S(k)v to be the sets T(k−1)1 , . . . , T(k−1)v .Proof of Proposition 3.3.4. The proof proceeds by induction on the variabler. The r = 1 case is implied by Proposition 3.3.1.Now, suppose that Drf = ∂αf , and the sets T1, . . . , Tv, satisfy the con-ditions of the proposition. We will show that the sets S1, . . . , Sv promisedby applying Proposition 3.3.1 to the function f∗ = Dr−1f satisfy the re-quirements for T1, . . . , Tv in Proposition 3.3.4 for ∂βf = Dr−1f (though notwith the same constants), completing the induction.Accordingly, we define f∗ := Dr−1f , and check the three assumptions ofProposition 3.3.1. Then1. Evidently, each Ti can be expressed as a union of intervals of sidelengthM−1, by the first assumption in Proposition The condition that Ti and Ti′ have disjoint interiors is also clearlyimplied by the second assumption in Proposition The third condition in Proposition 3.3.1 implies that ∂f∗∂xi0is nonzerofor the index i0 of the derivative that is taken to get from Dk−1 to Dk.343.3. A Single StepFurthermore, there exists c′0 such that |∇f(x)| ≤ (c′0)−1, because f isr times continuously differentiable, and hence all rth order derivativesof f are continuous and thus bounded on the compact set T1×· · ·×Tv.Then assumption 3 of Proposition 3.3.1 holds for the constant c∗0, takento be the minimum of c0 and c′0.Thus we can apply Proposition 3.3.1 to f∗, the sets T1, . . . , Tv, the constantc∗0, the constant M , and an appropriately large number N′. In so doing, wearrive at sets S′1, . . . , S′v such that Dk−1f is nonzero on S′1 × · · · × S′v, eachS′j is a union of intervals of length c′1(N′)1−v with disjoint interiors, and,for each J ∈ JM (Ti), a family I ′N ′(J, i) such that for each I ∈ I ′N ′(J, i), theintersection S′i0 ∩ I contains at least one interval of length c′1(N ′)1−v (manysuch intervals if i = i0; one such interval for other values of i).We will now apply the inductive assumption. We will take the setsT ∗1 , . . . , T∗v to be S′1, . . . , S′v respectively, and take M∗ ≥ (c′1)−1(N ′)v−1. LetN ≫ N ′ be some value for which the inductive assumption applies. LetS1, . . . , Sv be the sets resulting from the application of the inductive as-sumption, and let c∗2 be the value of c2 in this application of the inductiveassumption. Evidently f(x1, . . . , xv) 6= 0 for x1 ∈ S1, . . . , xv ∈ Sv.Decompose T1, . . . , Tv into subintervals of length N . We have thatfor each J ∈ JM (Ti), there is a collection I ′N ′(J, i) ⊂ IN ′(J, i) such that#I ′N ′(J, i) ≥(1− 1M)#IN ′(J, i) and such that each element of I ′N ′(J, i)contains an interval of length c′1(N′)1−v that is contained in S′i Further-more, the inductive assumption implies that each such interval containsc∗2(c′1)−1c1(N ′)v−1N−1 intervals of length N that contain at least one subin-terval of length c1(N)1−v in Si. It therefore follows that ac′1(1− 1M)(N ′)2−vc∗2 fraction of the intervals of length N−1 in J containan interval of length c1(N)1−v as desired. The proof is complete becausec2 := c′1(1− 1M)(N ′)2−vc∗2 does not depend on N . 3.3.3 Higher DimensionsFor the higher-dimensional case, we do not concern ourselves with situa-tions in which the derivative is singular. Unlike the one-dimensional case,however, we need to make a size assumption on M in order for the proof tosucceed. Let m,n ≥ 1 and v ≥ 3 satisfy m ≤ n(v−1), and let f : Rnv → Rmbe a C2 function whose zero set has a nontrivial intersection with [0, 1]nv .Suppose M ≥ M∗ is a large integer, C0, C1, C2 are real constants andT1, . . . , Tv ⊂ [0, 1]n are sets with the following properties:353.3. A Single Step1. Each Ti is expressible as a union of closed disjoint balls of radius q−µ,the collection of which will be called Jµ(Tk). The sets Ti and Ti′ willbe disjoint for i 6= i′.2. On {x ∈ T1 × · · · × Tv : f(x) = 0}, the matrix Df is of full rank, witha submatrix B whose determinant is bounded below by C0, and whoseentries are bounded above by C1.3. On [0, η]nv the matrix norm of the Hessian D2f is bounded above byC2.We are now ready to state the main proposition in the multidimensionalsetting. This proposition is a slight modification of Proposition 3.4 from[19].Proposition 3.3.5 (Proposition 3.4 from [19]). Given f , M , C0, C1, andC2 as above, there exists a rational constant C3 > 0 and an integer N0depending on these quantities for which the following conclusions hold. ForN ≥ N0, set ℓ = C3Nn(1−v)/m. If N is such that NM , 1/(ℓN) ∈ Z, then onecan find compact subsets Si ⊆ Ti for all 1 ≤ i ≤ v such that(a) There are no solutions to f(x) = 0 with x ∈ S1 × · · · × Sv.(b) For each 1 ≤ i ≤ v and J ∈ JM (Ti), let us decompose J into closed axis-parallel cubes of length N−1 with disjoint interiors and call the resultingcollection of cubes IN (J, i). There exists I ′N (J, i) ⊆ IN(J, i) such thatSi ⊆⋃{I : J ∈ JM (Ti), I ∈ I ′N(J, i)}.More precisely, for each I ∈ I ′N(J, i), the set Si ∩ I is a single axis-parallel cube of sidelength ℓ = C3Nn(1−v)/m, provided i 6= v. For i = vand I ∈ I ′N(J, v), the set Sv ∩ I is not necessarily a single cube ofsidelength ℓ, but a union of such cubes, with the property that|Sv ∩ I| ≥(1− 1M)1Nn. (3.22)(c) The subcollections I ′N (J, i) of cubes are large subsets of the ambient col-lection IN (J, i), in the sense that for all 1 ≤ i ≤ v, J ∈ JM (Ti),#(I ′N(J, i)) ≥ (1− 1M)#(IN(J, i)). (3.23)363.3. A Single StepAs in the one-dimensional case, the specific dependence of C3 on theparameter M in the estimates of Proposition 3.3.5 does not impact theHausdorff dimension obtained in Theorem 1.1.2. The power of N is essentialfor the Hausdorff dimension bound.The restriction m ≤ n(v − 1) is essential for Theorem 1.1.2; otherwise,the theorem could not hold since the claimed Hausdorff dimension mv−1 wouldbe larger than n. This assumption is also used in the proof of Proposition3.3.5 in order to have ℓ ≪ N−1. In the case m < n(v − 1), the value ofℓ, selected to be ǫ0M−RN−n(v−1)/m will be less than 1N if N is sufficientlylarge depending on ǫ0 and M ; in the case m = Nv−1, ℓ will be less than 1Nprovided that M∗ is sufficiently large.The special treatment of xv is not necessary for the proof; xv could bereplaced with any xi0 .Proof. Let Zf = {x = (x1, . . . , xv) ∈ ([0, 1]n)v : f(x) = 0} be the zero setof the function f . A co-area formula argument can be used to show thatZf can be covered by at most Cǫm−nv cubes of sidelength ǫ for some largeconstant C that is independent of ǫ; however, we present an alternative proofin Lemma 3.3.6 because this lemma will be convenient in Chapter 5.We will project Zf successively onto the coordinates x1, x2, . . ., and selectthe sets Si so as to avoid the projected zero sets. The main ingredient ofthis argument is described in Lemma 3.3.7.Fix ℓ ≪ 1N , which will be specified later. We use Iα−1(J, i) to denotethe collection of axis-parallel subcubes of sidelength α that constitute apartition of J ∈ JM(Ti). We will define a collection of bad boxes, B1,defined as follows:B1 = {Q ∈v∏i=1Iℓ−1(Ji, i) : Q intersects Zf ; Ji ∈ JM (Ti)}. (3.24)Lemma 3.3.6 establishes that #(B1) ≤ CMnvℓm−nv, where C is a constantdepending only on the function f and on the value c0.We construct S1, . . . , Sv as follows. First, we project the boxes in B1onto their (x2, . . . , xv) coordinates (each n-dimensional), and use Lemma3.3.7 with r = v, T = T1, T′ = T2 × · · · × Tv and B = B1 to arrive atS1 ⊂ T1 and a family of n(v − 1)-dimensional boxes B′ = B2 satisfying theconclusions of that lemma. S1, of course, satisfies the conclusions of Part bof Proposition 3.3.5. Lemma 3.3.7 also gives a bound on#(B2) ≤Mn+1Nnℓn#(B1) ≤ CMnv+(n+1)Nnℓm−n(v−1)373.3. A Single Stepand that f(x) 6= 0 for any x = (x1, x′) such that x1 ∈ S1 and x′ ∈ T2×· · ·×Tvthat is not contained in the cubes that constitute B2.We iterate this procedure. At the end of step j, we will have selectedS1 ⊂ T1, . . . , Sj ⊂ Tj , and we will be left with a family Bj+1 of cubes ofdimension n(v − j) of sidelength ℓ such that#Bj+1 ≤ CMnv+(n+1)jN jnℓm−n(v−j) (3.25)and so that f(x′′, x′) is nonzero for any (x1, . . . , xj) ∈∏ji=1 Si, any x′ ∈∏vi=j+1 Ti, and any x′ that avoids the cubes in Bj+1. We now apply Lemma3.3.7 withT = Tj+1, T′ = Tj+1 × · · · × Tv, B = Bj+1to arrive at Sj+1 ⊂ Tj+1 that satisfy the requirements of part b. The lemmaalso gives B′ = Bj+2 of n(v−j−1)-dimensional cubes of side length ℓ, whosecardinality obeys (3.25) with j replaced by j+1. This allows us to continuethe induction.We use this strategy for v−1 steps, ultimately obtaining sets S1, . . . , Sv−1and a collection Bv containing at most CMnv+(n+1)(v−1)Nn(v−1)ℓm−n cubesof side length ℓ and dimension n contained in Tv. We then define Sv usingLemma 3.3.8, the conclusion of which satisfies both parts of the proposition.Lemma 3.3.6. There exists M0(C0, C1, C2) > 0 such that the followingstatement holds for all M ≥ M0. Let T be an nv-dimensional closed cubeof sidelength M−1 and let f(x1, . . . , xv) : T → Rm be a function such thatDf has an m-by-m minor that is, in absolute value, at least a constantC0 on all of T and whose entries are bounded above in absolute value by aconstant C1. Suppose further that C2 is an upper bound for the operatornorm of the second derivative of f . Let Zf be the set of (x1, . . . , xv) ∈ Tsuch that f(x1, . . . , xv) = 0. Subdivide the cube T into balls of radius ℓ. If ℓis sufficiently small, then the number of balls that intersect the zero set of fis at most C3(Mℓ)(m−nv) where M0 and C3 can depend on C0, C1, and C2but not on ℓ.Proof. Let x0 be an arbitrary point in Zf ∩ T (If this set is empty thereis nothing to show). If M is large enough depending on C0, C1, and C2,then there exists a fixed submatrix B of Df such that |det(B)| ≥ C0 for allx ∈ T. Let (j1, . . . , jm) be the indices of the columns of B. Consider thevector space U spanned by eji , where the jith component of ej1 is equal to1, and all of the other components of eji are equal to zero. Consider points383.3. A Single Stepof the form x0 + u, where u ∈ U and ‖u‖ ≤ M−1. By the assumption onDf , we have that f(x0 + u) = f(x0) +Dfx0(u) +O(‖u‖2). Here f(x0) = 0,‖Dfx0u‖ > k0 ‖u‖, where k−10 is the operator norm of B−1. The implicitconstant in the O(‖u‖2) depends on C0, C1, and C2.We can estimate k0 using the adujgate formula for B−1. The operatornorm of B−1 is bounded above by the sum of the absolute values of the en-tries of B−1. Each such entry is bounded above by a constant depending onthe dimension and on C0 and C1, so the same is true for ||B−1||. Therefore,we have that ‖f(x0 + u)‖ ≥ k0 ‖u‖−O(‖u‖2), which is positive if M is largeenough.Let ℓ < M−1. For a given x ∈ Zf , consider the set consisting of pointsx+U+w where w has a zero in each ji component; i.e. w is in the orthogonalcomplement U⊥ of U . The set of points x+ U + w is the ℓ-neighbourhoodof x+ U . Let x+ u+ w be a point in this slab. We have thatf(x+ u+ w) = f(x) +Dfx(u+ w) +O(‖u+w‖2).This has norm at least k0 ‖u‖−mC1 ‖w‖+O(‖u+ w‖2). Therefore f(x+u+w) is nonzero provided that ‖u‖ is larger than 2C1mk0 ‖w‖, which will happenas long as ‖u‖ ≥ 2C1mk0 ℓ, and provided that M is sufficiently large that theO(‖u+ w‖2) term has norm smaller than k04 ‖u‖. We make this assumptionon M0. If we subdivide the slab x+U +w into ℓ-cubes, we get that Zf willonly intersect at most(2C1mk0)mcubes of sidelength ℓ in the slab. Takingthe union over essentially disjoint parallel slabs covering T, we have that atotal of O((C1k0)m(Mℓ)m−nv)cubes of sidelength ℓ that intersect Zf . Fix 2 ≤ r ≤ v and consider sets T ⊂ [0, 1]n and T ′ ⊂ [0, 1]n(r−1) ex-pressible as unions of axis-parallel cubes of sidelength M−1 and disjointinteriors. We use JM (T ) and JM (T ′) to denote the collections of thesecubes. Given any J ∈ JM(T ), we decompose J into axis-parallel cubes ofsidelength N−1; the corresponding collection is called IN(J). We will alsofix a subset B ⊂ T × T ′, a union of a collection B of cubes of sidelength ℓ.Here M,N, and ℓ are as specified in Proposition 3.3.5. Since Nℓ is taken tobe an integer, we may assume that each cube in B is contained in exactlyone cube in IN(J).Lemma 3.3.7 (Lemma 3.5 from [19]). Given T, T ′, B as above, there existsets S ⊆ T , B′ ⊆ T ′ and a collection of boxes B′ with the following properties:(a) The set S is a union of closed axis-parallel cubes of sidelength ℓ anddisjoint interiors. More precisely, for every J ∈ JM(T ), there exists393.3. A Single StepI ′N (J) ⊆ IN(J) such that#(I ′N (J)) ≥ (1−M−1)#(IN (J)),and S ∩ I is a single ℓ-cube for each I ∈ I ′N (J). For I ∈ IN (J) \I ′N (J),the interior of the set S ∩ I is empty.(b) The set B′ is the union of the ℓ-cubes in B′.(c) #(B′) ≤Mn+1Nnℓn#(B).(d) (S × T ′) ∩B ⊆ S ×B′Proof. Fix J ∈ JM (T ). For I ∈ IN (J), define a slabWN [I] :=⋃{Q = I × I ′for some I ′ ∈ IN (J) for some J ∈ JSo a slab is the union of all of the boxes of sidelength 1N whose projectiononto the x1-coordinate is the cube I. We define the wafersWℓ−1 [I] to be theunion of all cubes of sidelength ℓ that project onto I in x1-space. Observethat a slab is an essentially disjoint union exactly N−nℓ−n wafers, and thetotal number of wafers supported by a cube J is M−nℓ−n. A wafer is inturn a union of ℓ-cubes.We will call a wafer Wℓ−1 [I] good if it contains at most Mn+1ℓn#(B)boxes of B. By the pigeonhole principle, the fraction of wafers that are badis at most 1M . Now, call a slab good if it contains at least one good wafer.Clearly, at most a 1M -fraction of the slabs can be bad. Let us define IN (J) asthe collection of all cubes I such that the slab WN [I] is good. For each cubeI ∈ I ′N (J), we select a cube I0 = I0(I) ⊂ I such that the wafer Wℓ−1 [I0]is good. Take S to be the union of all ℓ-cubes I0(I), with I ∈ I ′N (J) andJ ∈ JM(T ). This covers everything in part (a) of the lemma.Let B′ be the union of the collection B′ of all ℓ-cubes Q′ ⊂ T ′ such thatQ×Q′ ∈ B for some ℓ-cube Q ⊂ S. Then (b) and (d) hold by definition. (c)Follows from the good wafer property: for any of the selected cubes Q ⊂ Sthe number of cubes Q′ such that Q × Q′ ∈ B is at most Mn+1ℓn#B. Onthe other hand, each Q comes from a distinct slab, so the number of suchQ is at most Nn. This gives the bound in part (c). 403.4. Construction of EWhen r = 1, we need a small variant of this Lemma. It is very similarto Lemma 3.3.7.Lemma 3.3.8 (Lemma 3.6 from [19]). Fix ℓ ≪ N−1 ≪ M−1. Let T ⊂[0, 1]n be a union of closed axis-parallel cubes of sidelength M−1 and dis-joint interiors. Let B ⊂ T be a union of similar cubes with sidelength ℓ.Decompose T into axis-parallel cubes of sidelength N−1, denoting the corre-sponding collection T. Suppose that#B ≤ CMnv+(n+1)(v−1)Nn(v−1)ℓm−nwithℓ ≤ C−1/mM−1/m(nv+(n+1)v+1)N−n(v−1)m .Then there exist S ⊂ T and T∗ ⊂ T such that(a) S ∩B is empty.(b) #T∗ ≥ (1− 1/M)#T(c) S is a union of a large number of ℓ-cubes coming from T∗. More pre-cisely, |S ∩ I| ≥ (1−M−1)N−n for each I ∈ T∗.Proof. Decomposing each cube I ∈ T into subcubes of sidelength ℓ, wedeclare I to be good if it contains at most Mn+1N−n#B subcubes of B.As in the proof of Lemma 3.3.7, the pigeonhole principle implies that thefraction of bad cubes in T is at mostM−1. We define T∗ to be the collectionof good cubes in T, and S to be the union of all the subcubes of sidelengthℓ that are disjoint from B. Then, for every I ∈ T∗,|I ∩B| ≤Mn+1N−n#Bℓn ≤ CMnv+(n+1)vNn(v−2)ℓm ≤M−1N−n.3.4 Construction of EThe construction of the set E is similar to Keleti’s construction: we willcreate an appropriate queue, and at each stage the corresponding queueelement will tell us which configuration to avoid, and the intervals on whichthe configuration will be avoided.413.4. Construction of E3.4.1 ConstructionWe will construct the set E together with a queue that will keep track ofv-tuples of intervals contained in the set E. We will describe the first fewsteps of the construction and then describe a general step j.The details of this construction are slightly different from those in [19]in order to simplify the presentation. We will perform the constructions forTheorems 1.1.1 and 1.1.2 together.Step 0: At the initializing step, we set, in the case of Theorem 1.1.1, fork = 1, . . . , v:Ik[0] =[(k − 1)ηv,kηv], E0 = {I1[0], . . . , Iv[0]}, M0 = vη.In the case of Theorem 1.1.2, we instead define {Ik[0], 1 ≤ k ≤ vn} to besome enumeration of the n-dimensional cubes formed from these v intervals.We also need to take M0 to be the least common multiple ofvη and thevalue M∗ required to apply Proposition 3.3.5 to the function f1. Let L0 = vor vn as is appropriate, and let Σ0 denote the collection of injections from{1, . . . , v} into {1, . . . , L0}. We define an ordered queueQ0 = {(1, σ, 0) : σ ∈ Σ0}We order Q0 lexicographically in σ (viewing σ as a collection of v-tuplestaking values in {1, . . . , v}). Then (1, σ, 0) will precede (1, σ′, 0) if σ < σ′with respect to this lexicographic ordering.For any σ, we define the ordered v-tuple of intervalsIσ[0] = (Iσ(1)[0], . . . , Iσ(v)[0]).Step 1 Consider the first member of Q0, which is (1, σ, 0). We will ap-ply Proposition 3.3.4 in the case of Theorem 1.1.1, or Proposition 3.3.5 inthe case of Theorem 1.1.2, to the function f on the sets Ti = Iσ1(i), withM = M0. The conclusion of the appropriate proposition then holds forsome constant d0 = c1(M0,T) > 0 and for arbitrarily large integers N1. Inapplying Proposition 3.3.4, we also have a constant e0 = c2(M0,T) > 0. Weselect N1 > eM0/d0e0 . The proposition then ensures the existence of largesubsets Sj ⊂ Tj for 1 ≤ j ≤ v, each of which is a union of cubes of sidelengthℓ1 =d0Nv−1mwithf1(x) 6= 0 for x = (x1, . . . , xv) ∈ S1 × · · · × Sv.423.4. Construction of EFor any cubes not contained in T1, . . . , Tv , we retain all cubes of lengthℓ1 contained in these cubes.These are the basic cubes for the first stage.We will let E1 = {I1[1], I2[1], . . . , IL1 [1]} be an enumeration of the first-stage basic cubes, Σ1 the collection of injective mappings from {1, . . . , v}to {1, . . . , L1}. We view an element of Σ1 as an ordered v-tuple of distinctindices from {1, . . . , L1}. As before, Σ1 is arranged lexicographically. SetQ′1 = {(q, σ, 1); 1 ≤ q ≤ 2;σ ∈ Σ1}.The list Q′1 is ordered in the following way: (q, σ, 1) precedes (q′, σ′, 1)if σ < σ′, and (q, σ, 1) precedes (q′, σ, 1) if q < q′. Q′1 is appended to Q0 toform the queue Q1, which concludes the first step.Step j At the end of step j, we have the following:• The jth iterate Ej of the construction: a union of jth level basiccubes of length ℓj = dj−1/Nv−1j . Here , {dj′ : j′ < j} is a sequence ofsmall constants obtained as c1 from applications of Proposition 3.3.4or 3.3.5, that depends on the collection of functions {fq : q ≤ j}.Thus, dj depends only on the parameters from the first j steps of theconstruction, even though it has no direct bearing on the size of Ej oron the intervals in Ej. The sequence Nj is chosen in order to satisfyNj > exp(j∏k=1(Nkek−1dk)R)for all j ≥ 1.for some large constant R. Here, ek−1 is the value of c2 from applyingProposition 3.3.4 or equal to(1− 1Mk−1)in the case of Proposition3.3.5.• The collection of basic cubes Ej that constitute Ej . This is denotedby Ej = {I1[j], I2[j], . . . , ILj [j]}.• The queue Qj = Qj−1 ∪Q′j , whereQ′j = {(q, σ, j) : 1 ≤ q ≤ j, σ ∈ Σj}.Here, Σj is the collection of all injections from{1, . . . , v} into {1, . . . , Lj}. This can also be viewed as the collec-tion of all v-dimensional vectors with distinct entries taking values in433.4. Construction of E{1, . . . , Lj} and endowed with the lexicographical order. The new listQ′j is ordered the same way as described in step 1 and appended toQj−1. Notice that the number of members in Qj is much larger thanj.We also know that fq(x) is nonzero for appropriate choices of q and x. Givenany 3-tuple of the form (q, σ, j), we know from the application of Proposition3.3.4 or 3.3.5 that fq(x) does not vanish for x1 ∈ Iσ(1)[j], . . . , xj ∈ Iσ(v)[j].Now, consider the (j + 1)st entry of the queue Qj , which is denoted by(q0, σ0, j′). We would like to apply Proposition 3.3.4 or 3.3.5 straightaway,to the function fq0 with T1 = Iσ(1)[j′]∩Ej , . . . , Tv = Iσ(v)[j′]∩Ej , and withM−1 = ℓj . This will work for the case of Proposition 3.3.4, but there is aproblem in trying to apply Proposition 3.3.5: ℓ−1 may not be larger than thequantity M∗ appearing in the statement of that proposition. Thus we splitthe cubes of Ej into sub-cubes of sidelength Mj where Mj = max(M∗, ℓ−1j ).This does not modify the sets T1, . . . , Tv , but changes the way these sets arepartitioned into smaller cubes.After this step, we can apply Proposition 3.3.4 or 3.3.5. We obtain acollection of Ej+1 of (j+1)st basic cubes of side length ℓj+1 = djNn(v−1)mj+1. Foreach cube of side length Mj that is not contained in T1, . . . , Tv, we partitionthe cubes into cubes of sidelength ℓj+1 and retain all of the cubes. Thiscollection of cubes, Ej+1 = {I1[j+1], . . . , ILj+1 [j+1]}, will be the collectionof stage j + 1 basic cubes.We now use these newly constructed basic cubes to form the queue Q′j+1:The elements of Q′j+1 are triples of the form (q, σ, j + 1), where 1 ≤ q ≤j+1, and σ ∈ Σj+1, the collection of injective functions from {1, . . . , v} into{1, . . . , Lj+1}. Append Q′j+1 to Qj to form the queue Qj+1. This concludesstep j of the construction.3.4.2 Nonexistence of SolutionsFix q ≥ 1 and a tuple (x1, . . . , xv) of distinct points in E. Since ℓj → 0, thereis some j′ for which the points x1, . . . , xv are ℓj′-separated. Then there existssome j′ ≥ q in the construction of E such that these points lie in distinctbasic cubes E1, . . . , Ev in Ej′ . For an appropriate j, the jth element of of thequeue will be (q, σ, j′), where σ is such that Iσ(1)[j′], . . . , Iσ(v)[j′]. It followsfrom the conclusion of Proposition 3.3.4 or 3.3.5 that there are no solutionsto fq(y1, . . . , yv) = 0 with y1 ∈ E1, . . . , yv ∈ Ev. Thus f(x1, . . . , xv) 6= 0.443.4. Construction of E3.4.3 Hausdorff Dimension of EWe will use the version of Frostman’s lemma presented as Lemma 2.3.1 inorder to determine the Hausdorff dimension of E. Any ball can be coveredby a cube of side length equal to the diameter, and that any cube can becovered by a finite number of balls (which may depend on the dimension n)whose diameter is equal to the side length of a given cube, so Lemma 2.3.1is just as effective if cubes are considered instead of spheres.We therefore aim to construct a probability measure µ on E with theproperty that for every ǫ > 0, there exists Cǫ > 0 such thatµ(I) ≤ Cǫl(I)mv−1−ǫ. (3.26)Here, l(I) denotes the side length of the cube I.Let us recall that Ej denotes the collection of all basic cubes with aside length of ℓj at step j. We decompose each cube Ej into subcubes oflength N−1j , and let Fj+1 denote the collection of such that contain a cubein Ej+1. Let Fj+1 be the union of the cubes in Fj+1. We define a sequenceof measures µj, νj on the sets Ej , Fj defined recursively.We begin by defining µ0 on E0 to be the uniform measure on [0, η]n.Given a measure µj supported on the set Ej , we define νj to be the measuresupported on Fj+1 defined by evenly splitting the measure µj of each cubein Ej among its children in Fj+1. Given νj , the measure µj will be supportedon Ej and will be defined by evenly splitting the measure νj of each cube inFj among its children in Ej. It follows from the mass distribution principlethat the measures µj have a weak limit µ. We claim that µ obeys therequirement (3.26).The proof of this claim depends on the following proposition.Proposition 3.4.1 (Proposition 4.1 from [19]). Let K ∈ Ej , J ∈ Fj+1 withJ ⊂ K. Then(a)µ(K)/|K| ≤ µ(J)/|J | ≤ e−1j µ(K)/|K|.(b)µ(J) ≤ Aj|J |, where Aj =j∏k=1e−1k (ℓkNk)−n.Proof. We first prove Part (a). Each K ∈ Ej is decomposed into (Mj+1ℓj)nsubcubes of length M−1j+1. Each of these subcubes is further split into453.4. Construction of E(Nj+1Mj+1)nsubcubes of sidelength N−1j+1. Propositions 3.3.4 and 3.3.5 assertthat at least an ej-fraction of each of these subcubes contain a cube fromEj+1 and hence lie in Fj+1. Thus, the number of descendants J ∈ Fj+1 of agiven cube K ∈ Ej is therefore at most (ℓjNj+1)n and at least ej(ℓjNj+1)n =ej |K|/|J |. Since µ(K) is evenly distributed among such J , part (a) follows.We prove Part (b) by applying Part (a) iteratively. Suppose that J¯ isthe cube in Fj that contains K. Thenµ(J)|J | ≤ e−1jµ(K)|K| ≤ e−1jµ(J¯)K=e−1j |J¯ ||K|µ(J¯)|J¯ | =e−1j(ℓjNj)nµ(J¯)|J¯ | .Now, we will apply Proposition 3.4.1 to prove (3.26). Suppose that I isa cube with sidelength l(I) between ℓj+1 and ℓj. There are two possibilitiesthat will be considered: the first case is the one for whichN−1j+1 ≤ l(I) ≤ ℓjand the second case is the one for whichℓj+1 ≤ l(I) ≤ N−1j+1.In the first case, I can be covered by at most C|I|Nnj+1 cubes of sidelength1Nj+1. A priori, all of these cubes could be in Fj+1. If J is a generic elementof Fj+1, we obtain from Proposition 3.4.1 thatµ(I) ≤ C|I|Nnj+1µ(J) ≤ C|I|Nnj+1Aj|J | ≤ CAj|I|≤ C e−1j Aj−1(ℓjNj)n|I| ≤ CAj−1e−1j d− mv−1j−1 ℓmv−1−nj |I|≤ Cǫℓmv−1−n−ǫj |I| ≤ Cǫl(I)mv−1−ǫ.Here, we used the growth rate of the Nj , together with the definition of ℓj.Next, we will consider the case in which ℓj+1 ≤ l(I) ≤ N−1j+1. If µ(I) > 0,the cube I intersects at least one cube J in Fj+1 in which case it is containedin the union of at most (3n− 1) cubes of the same dimension adjacent to it.Proposition 3.4.1 then yields thatµ(I) ≤ Cnµ(J) ≤ CnAj |J | = CnAjN−nj+1= CnAjd− mv−1j ℓmv−1j+1 ≤ Cǫℓmv−1−ǫj+1 ≤ Cǫl(I)mv−1−ǫ,applying the growth rate of the Nj and the definition of ℓj, as before. Thisproves the inequality (3.26).463.5. Simultaneous Avoidance3.4.4 Minkowski Dimension of EWe would like to show that E has Minkowski dimension n. In order to showthis, it is enough to show that for any ℓ we haveNℓ(E) ≥ cǫℓ−n+ǫ for any 0 < ℓ≪ 1.Here, Nℓ(A) refers to the minimum number of closed cubes of sidelength ℓrequired to cover A. Given 0 < ℓ ≪ 1, we first fix the index j such thatℓj ≤ ℓ < ℓj−1. Because it is enough to show this for small values of ℓ, wemay assume j is as large as necessary.If j is sufficiently large, then there exists a cube I in Ej−2 such that I isnot contained in any of the sets T(j−1)1 , . . . , T(j−1)v or T(j)1 , . . . , T(j)v that playthe role of T1, . . . , Tv at step j − 1 or step j of the construction of E. Byconstruction, all of the cubes of sidelength ℓj occurring from the appropriatepartition of I are retained as elements of Ej. There are ℓnj−2ℓ−nj such boxes.Furthermore, each element of Ej intersects E.A box of sidelength ℓ such that ℓj ≤ ℓ < ℓj−1 can only intersect at mosta constant times ℓnℓ−nj of the elements of Ej. Therefore, we require at least(ℓnj−2ℓ−nj ) · (ℓ−nℓnj ) = ℓnj−2 · ℓ−n boxes of sidelength ℓ to cover the set E.By construction, this is at least ℓ−n+ǫ, establishing the desired bound forNℓ(E).3.5 Simultaneous AvoidanceWe will now prove Theorem 1.1.3. This is also a Cantor-like set. For thisconstruction, we will not need to use a queue as in the proofs of Theorems1.1.1 or 1.1.2. The construction will instead proceed in the following way:we will begin with an interval E0 = [0, η] for a small constant η and retaintwo small subintervals of this original interval. These two subintervals willform the set E1. We then retain two small subintervals of each constituentinterval of E1 in order to form the set E2. The set Ej will be composed of 2jintervals, and we will retain two small subintervals from each such intervalin order to form the set Ej+1.Proposition 3.5.2 will describe the procedure for choosing the subinter-vals of Ej to be retained at each stage. This proposition will follow byiterating Lemma 3.5.1.Let α ∈ Rv be as in the statement of Theorem 1.1.3, and let C be anonempty proper subset of the index set {1, 2, . . . , v}. Let δ > 0. Considerdisjoint intervals [a1, b1] and [a2, b2] of length λ, with a1 < b1 ≤ a2 < b2.473.5. Simultaneous AvoidanceWe define two quantities ǫleft and ǫright depending on C, a1, b1, a2, b2, and δas follows.ǫleft := sup ǫ :∣∣ v∑j=1αjzj∣∣ ≥ δλ for {zj ∈ [a1, a1 + ǫλ] for all j /∈ Czj ∈ [a2, a2 + ǫλ] for all j ∈ C.(3.27)ǫright := sup ǫ :∣∣ v∑j=1αjzj∣∣ ≥ δλ for {zj ∈ [a1, a1 + ǫλ] for all j /∈ Czj ∈ [b2 − ǫλ, b2] for all j ∈ C.(3.28)Lemma 3.5.1 (Lemma 5.1 from [19]). Given any α ∈ Rv as in Theorem1.1.3, there exists δ0 > 0 depending only on α such that for any λ > 0and any choice of intervals J1 = [a1, b1] and J2 = [a2, b2] of equal lengthλ with a1 < b1 ≤ a2 < b2, the following property holds. For any δ < δ0,there exists ǫ0 = ǫ0(C, δ) that does not depend on a1, a2, b1, b2, or λ such thatmax(ǫleft, ǫright) ≥ ǫ0.In particular, there exist subintervals Ĵ1 ⊂ J1,and Ĵ2 ⊂ J2 with |Ĵ1| =|Ĵ2| = ǫ0λ and dist(Ĵ1, Ĵ2) ≥ (1− ǫ0)λ such that|α · x| ≥ δλ for all x ∈ Rv such that{xj ∈ Ĵ1 for j /∈ C,xj ∈ Ĵ2 for j ∈ C.Proof. Set g(y) =∑j αjyj, and consider g(z∗), where z∗ = (z∗1 , . . . , z∗v) isdefined to be the v-dimensional vector with z∗j = a1 if j /∈ C and z∗j = a2 ifj ∈ C. Setting C∗ =∑j |αj |, we have|g(z) − g(z∗)| ≤ C∗ǫλ whenever zj − z∗j | ≤ ǫλ, 1 ≤ j ≤ v. (3.29)We will split into two cases depending on the value of g(z∗).If |g(z∗)| > (δ + ǫ0C∗)λ, then (3.29)) implies that |g(z)| ≥ δλ for anyz = (z1, . . . , zv) with zj ∈ [a1, a1 + ǫ0λ] for j /∈ C and zj ∈ [a2, a2 + ǫ0λ]for j ∈ C. Thus ǫleft ≥ ǫ0, and the conclusion of the lemma holds withĴ1 = [a1, a1 + ǫ0λ], and Ĵ2 = [a2, a2 + ǫλ].On the other hand, if |g(z∗)| ≤ δ + ǫ0C∗λ, let ẑ = (ẑ1, . . . , ẑv) be thev-dimensional vector with ẑj = a1 if j /∈ C. Then, we have that g(ẑ) =g(z∗)+α·(ẑ−z∗) = g(z∗)±(b2−a2)C0 = g(z∗)±λC0, where C0 =∣∣∣∑j∈C αj∣∣∣.C0 is nonzero by the assumptions in Theorem 1.1.3. So, if z is such thatzj ∈ [a1, a1 + ǫ0λ] for j /∈ C and zj ∈ [b2 − ǫ0λ, b2] if j ∈ C, then we can use483.5. Simultaneous Avoidance(3.29) to obtain the estimate|g(z)| ≥ |g(ẑ)| − |α · (z − ẑ)| ≥ |C0λ± g(z∗)| − C∗ǫ0λ≥ C0λ− (δ + C∗ǫ0)λ− C∗ǫ0λ ≥ C0λ− (δ + 2ǫ0C∗)λ,, which is greater than or equal to δλ provided that δ < C0/2 =: δ0 andǫ0 ≤ (C0 − 2δ)/(2C∗). One has ǫright ≥ ǫ0 for this choice of ǫ0, with theconclusion of the lemma verified for Î1 = [a1, a1 + ǫ0λ], Î2 = [b2 − ǫ0λ, b2].We will now present an illustrative example: we will discuss the casewhen α = (1,−2, 1), which is relevant to Example 3.2.6. We will considerthe case where C is equal to {3}. We will obtain bounds on both ǫleft andǫright. Note that α · (x1, x2, x3) is zero precisely when x1, x2, and x3 are inarithmetic progression. For x1, x2 ∈ [a1, a1 + ǫλ], and x3 ∈ [a2, a2 + ǫλ], itis easy to see thatx1 − x2 + x3 ≥ a1 + a2 − 2(a1 + ǫλ = a2 − a1 − 2ǫλ ≥ (1− 2ǫ)λ.Therefore, we can select ǫleft =1−δ2 for this choice of α, and for any a1, a2, b1,and b2.If x1, x2 ∈ [a1, a1 + ǫλ], and x3 ∈ [b2 − ǫλ, b2], thenx1 − 2x2 + x3 ≥ a1 + b2 − ǫλ− 2(a1 + ǫλ) = b2 − a1 − 3ǫλTherefore ǫright =2−δ3 .The bound on ǫ0 obtained in the statement of Lemma 3.5.1 may not beoptimal for a specific α because the signs of the components of α are nottaken into account.Proposition 3.5.2 (Proposition 5.2 from [19]). Given any α ∈ Rv satisfyingthe hypotheses of Theorem 1.1.3, there exist fixed small constants 0 < ǫ <3/4 and δ(ǫ) > 0 depending on α with the following property. Let I be anyinterval say of length ℓ, and let I1 and I2 denote the two halves of I. Thenone can find subintervals I ′1 and I′2 of I1 and I2 of length ǫℓ such that|α · x| ≥ δℓ for every sufficiently small δ ≤ δ(ǫ),and for any choice of x1, x2, . . . , xv ∈ I ′1 ∪ I ′2, not all of which are in I ′i fora single i = 1, 2. The subintervals I ′1 and I′2 are separated by at least ℓ/4.493.5. Simultaneous AvoidanceProof. Let {C1, . . . ,CR} be an enumeration of the nonempty proper subsetsof {1, . . . , v}. We will iteratively apply Lemma 3.5.1 for each of these choicesof C. Given any x = (x1, . . . , xv) such that xj ∈ I for all j, with not all xjin I1 and not all xj in I2, there exists 1 ≤ m ≤ R such that j ∈ Cm if andonly if xj ∈ I2. SetCm :=∣∣∣∣∣∣∑j∈Cmαj∣∣∣∣∣∣ and δ0 = 12 min(C1, . . . , CR).With these choices, Lemma 3.5.1 can be applied for any δ < δ0 and anyC = Cm, 1 ≤ m ≤ R.We will start with I1 and I2 and apply Lemma 3.5.1 with C = C1,J1 = I1, J2 = I2, and λ = ℓ/2. For a small but fixed δ1 > 0 with 2δ1 ≤ δ0,this gives a constant ǫ1 = ǫ0(C1, 2δ1) > 0 and two subintervals I(1)1 ⊂ I1 andI(1)2 ⊂ I2 of length ǫ1ℓ/2 obeying the conclusions of the lemma. Withoutloss of generality, we can assume that ǫ1 ≤ 12 , so thatdist(I(1)1 , I(1)2 ) ≥ (1− ǫ1)ℓ2≥ ℓ4. (3.30)We apply this procedure recursively. Let 2 ≤ k ≤ R, with the same valuefor δ1, andC = Ck,J1 = I(k−1)1 ,J2 = I(k−1)2 , λ = ǫ1 · · · ǫk−1ℓ/2After the kth step, this yields a constant ǫk = ǫ0(Ck, 2δ) and subintervalsI(k)1 ⊂ I(k−1)1 ⊂ · · · ⊂ I1, I(k)2 ⊂ I(k−1)2 ⊂ I2, each of length ǫ1 · · · ǫkℓ/2 suchthat, for any m ≤ k:|α · x| ≥ δ1ǫ1 · · · ǫk−1ℓ for all x such that{xj ∈ I(k)1 for j /∈ Cmxj ∈ I(k)2 for j ∈ CmThis establishes the conclusion of Proposition 3.5.2 forI ′1 = I(R)1 , I′2 = I(R)2 , ǫ =12R∏k=1ǫk, and δ(ǫ) = δ1ǫ1 · · · ǫR−1.The separation condition follows from the first application of in 3.5.1 andthe fact that I ′1 ⊂ I(1)1 and I ′2 ⊂ I(1)2 . 503.5. Simultaneous AvoidanceWe would again like to point out what happens in the case of Example3.2.6. In particular, this is the case in which α = (1,−2, 1). Recall thatα · (x1, x2, x3) = 0 whenever x2− x1 = x3− x2. However, notice that in anyinterval [a, a + ℓ], we can consider the intervals I ′1 = [a, a + (1− δ)ℓ/3] andI ′2 = [a + ℓ − (1 − δ)ℓ/3, a + ℓ]. It is easily seen that these intervals meetthe requirements of Proposition 3.5.2, and therefore optimal choice for ǫ isgreater than or equal to (1− δ)/3.In general, we have the estimateǫ ≥R∏m=1(Cm − 2δ1)(2C∗). (3.31)Here C∗ is defined as∑vj=1 |αj |. We are now ready to prove Theorem 1.1.3.Proof of Theorem 1.1.3. Let ǫ and δ = δ(ǫ) be the positive α-dependentconstants given by Proposition 3.5.2. We will continue to use the notationg(x1, . . . , xv) =∑vj=1 αjxj.We will begin with the interval [0, η], where the positive constant 0 <η ≪ 1 is chosen so that 2Kvη < δ (Here, K is the constant in the statementof Theorem 1.1.3. Applying Proposition 3.5.2 with I = E0, we will arriveat intervals I ′1 =: J1 ⊂ [0, η/2] and I ′2 =: J2 ⊂ [η/2, η] of length ℓ1 = ǫηthat obey its conclusions. Let E1 = J1 ∪ J2. In general, if Ej is a disjointunion of 2j basic intervals of length ℓj = ǫjη,t hen at step (j + 1), we applyProposition 3.5.2 in order to arrive at two further subintervals of lengthℓj+1 := ǫℓj = ǫj+1η, and separated by a distance of at least ℓj/4. The unionof the resulting 2j+1 intervals forms the set Ej+1.We now define E =⋂∞j=1Ej. We will show, for f as in the statement ofTheorem 1.1.3, and for x1, . . . , xv ∈ E not all identical, that f(x1, . . . , xv) 6=0. For any such choice of x1, . . . , xv, there exists a largest index j suchthat x1, . . . , xv lie in the same basic interval I in Ej. This means that if I′1and I ′2 are the two subintervals of I generated by Proposition 3.5.2, thenx1, . . . , xv lie in I′1∪ I ′2, but not all of x1, . . . , xv lie in the same interval I ′1 orI ′2. Therefore, the conclusion of Proposition 3.5.2 implies that |g(x)| ≥ δℓj .But because |f(x)−g(x)| ≤ Kvℓ2j , and by the fact that 2Kvη < δ, it followsthat |f(x)| ≥ δℓj2 for ℓj < η.The only remaining task is to compute the Hausdorff dimension of E.The (j + 1)st step of the construction generates exactly two children fromeach parent. We define µj to be the measure on Ej that is evenly spreadabout the intervals in Ej. It is clear that µj has a weak limit µ. We willshow that µ is a Frostman measure on E.513.5. Simultaneous AvoidanceConsider an interval I of length ℓ < η that intersects the set E. We selectj such that ℓj+1 ≤ ℓ ≤ ℓj . An interval of length ℓ can only intersect at most 2constituent intervals of Ej and at mostℓℓj+1+1 constituent intervals of Ej+1.Thus µj+1(ℓ) is bounded above by 2−j−1 ·(ℓℓj+1+ 1)≤ 2−j−1 · (ǫ−1 + 1).Now we consider µj+k(I) for k > 1. Recall that I intersects at mostℓℓj+1= ǫ−1+1 of the constituent intervals of Ej+1. Because each interval ofEj+1 has exactly 2k−1 children in Ej+k, it follows that I intersects at most2k−1(ǫ−1 + 1)constituent intervals of Ej+k. Furthermore, each constituentinterval of Ej+k has µj+k-measure equal to 2−j−k. Therefore, the µj+k-measure of I is at most 2−j−k · 2k−1 · (ǫ−1 + 1). This is equal to 2−j−1 ·(ǫ−1 + 1).Therefore, it follows that for I satisfying ηǫj+1 ≤ |I| < ηǫj , we have thatµ(I) ≥ 2−(j+1) (ǫ−1 + 1). Therefore, µ(I) is at least Cǫ2−j = Cǫ|I|− log 2log ǫ ,which, together with Lemma 2.3.1, implies that E has Hausdorff dimensionat least log 2− log ǫ . Notice that this proof will also succeed if the condition 1.4 in Theorem1.1.3 is weakened to |G(x)| ≤ K∑vj=2(xj − x1)1+ǫ. for any ǫ > 0.We will once again consider the example α = (1,−2, 1) in order to com-plete the Hausdorff dimension calculation for Example 3.2.6.Let δj be the sequence δj =1j+C for some large constant C. (The pointis that δj is a sequence that slowly decreases to zero. It follows from thediscussion following the proof of Proposition 3.5.2 that ǫ(δj) = ǫj can bechosen as (1− δj)/3. We will now use the same construction as in the proofof Theorem 1.1.3, but instead of using a fixed δ, we will use the parameterδj at step j at step j instead of using a fixed δ for the entire proof.The following consequences are immediate:ℓj = ǫ1 · · · ǫjη so that ℓj ≤ Cη3−jj + C.|g(x)| ≥ δjℓj and |f(x)− g(x)| ≤ Kvℓ2j so that|f(x)| ≥ (δj −Kvℓj)ℓj ≥(1j + C− KvηCj + C3−j)ℓj > 0when x is such that all of the components of x lie in the same constituentinterval of Ej but not of Ej+1. Furthermore, an argument similar to the onein the proof of Theorem 1.1.3 shows that the Hausdorff dimension of E is523.5. Simultaneous Avoidancebounded from below bylimj→∞log(2j)− log(2ℓj) = limj→∞log(2j)− log(3−jη∏jk=1(1− δk)/2) = log 2log 3.where the last limit follows from the slow decay of the δj .53Chapter 4Background on Local fields4.1 ExamplesWe will present two examples of non-archimedean local fields. The discussionof non-archimedean local fields in this thesis will be primarily limited to thesetwo examples. The first such example will be the field Qp, known as thep-adic numbers.Each x ∈ Z has a finite base-p expansion∞∑j=0xjpjwhere only finitely many xj are nonzero. If x 6= 0, we define |x|p to be p−j,where xj is the lowest-degree nonzero term in the expansion. If we takethe completion of Z with respect to this absolute value, we get the ring ofelements of the form ∞∑j=0xjpj .This ring is called the ring of p-adic integers, denoted Zp. This ring isequipped with an absolute value defined as follows: |x|p = p−M if xM isnonzero and xj = 0 for all j < M , and |0|p = 0. Any element of Zp withabsolute value equal to 1 has a multiplicative inverse in Zp. Therefore, Zpcontains every rational number rq whose denominator q is relatively primeto p. This is a compact abelian group under addition.Zp has a unique prime ideal pZp, generated by the element p. Further-more every ideal of Zp is a power of this prime ideal. It therefore follows thateach ideal of Zp is generated by a power pk and therefore Zp is a principalideal domain. A principal ideal domain with a unique prime ideal is calleda discrete valuation ring.The field of fractions of Zp is denoted Qp and is known as the field ofp-adic numbers. As an additive group, Qp is locally compact. The fieldFp is called the residue class field of Qp: it is the quotient field Zp/pZp.544.2. IntroductionA second example of a non-archimedean local field is the field Fq((t))of formal Laurent series over the finite field Fq. Such fields are sometimesknown as function fields. The ring of integers Fq[[t]] consists of formalpower series over Fq. Unlike the case for Qp, the field Fq((t)) has finitecharacteristic p where q = pf . The ring Fq[[t]] is also a discrete valuation ringwith prime ideal tFq[[t]]. This time, the quotient Fq[[t]]/tFq[[t]] is isomorphicto the finite field Fq. The field Fq is called the residue class field of Fq((t)).These two examples are central to the theory of non-archimedean localfields. Every non-archimedean local field is either isomorphic to Fq((t)) orto a finite extension of Qp. [51, Theorem 5 of Section 1.3 and Theorem 8 ofSection 1.8].4.2 IntroductionWe now generalize some of the concepts from the previous section.A discrete valuation ring R is a principal ideal domain with a uniqueprime ideal [46]. Because R is a principal ideal domain, the prime ideal of Ris generated by a single element of R; such elements are called uniformizersor uniformizing elements of R. Let t be a uniformizing element of R.Because tR is the only prime ideal of R, it follows that tR is not properlycontained in any other prime ideals of R; therefore, tR is a maximal ideal.It follows that the quotient R/tR is a field. This field R/tR is called theresidue class field of R. We will exclusively consider the situation in whichR/tR is a finite field Fq.Suppose q = pf for some f . Then Fq has characteristic p, and p · 1 =1 + 1 + · · · + 1︸ ︷︷ ︸p timesbelongs to the ideal tR. If p · 1 = 0, then the ring R hascharacteristic p; otherwise, R has characteristic zero. For example, Zp hascharacteristic zero and Fp[[t]] has characteristic p.Let S be a family of additive cosets of tR in R with the property that0 ∈ S. Every element x of R can be expressed uniquely in the formx =∞∑j=0xjtj (4.1)where xj runs over a family S of the additive cosets of tR such that 0 ∈ S.If each infinite sum of this form corresponds to an element x ∈ R, then thediscrete valuation ring R is called complete.For the rest of this section, we will assume R is a complete discretevaluation ring. Let x ∈ R and write x as in (4.1). We define the absolute554.2. Introductionvalue |x| of x to be 0 if x = 0, and q−j if xj 6= 0 and xk = 0 for all k < j.With respect to this absolute value, R forms a complete metric space. Thisabsolute value is discrete (this is the origin of the term discrete valuationring), taking only values {q−j : j ∈ Z} and zero. The closed balls of radiusq−j in the metric induced by this absolute value are nonzero. This absolutevalue respects multiplication: |xy| = |x||y|. Furthermore, the absolute valuesatisfies the ultrametric inequality|x+ y| ≤ max(|x|, |y|). (4.2)We will take a few moments to consider the importance of inequality (4.2).Consider the (closed) ball of radius r = q−j centered at x. Let y be anypoint in R such that |x − y| ≤ r, and let z ∈ R be such that |y − z| ≤ r.Then we have|x− z| = |(x− y) + (y − z)| ≤ max(|x− y|, |y − z|) ≤ r.So the closed ball of radius r centered at x is precisely the same ball as theclosed ball of radius r centered at y. This implies that if two closed balls ofradius r intersect, then they must be equal.The discrete nature of the absolute value also has some profound im-plications for the topology on R. For example, consider the family of ballsof radius q−j−1 contained in a closed ball of radius q−j centered at x. If|x − y| = q−j−1 exactly, then x and y lie in the same coset of tj−1R butnot in the same coset of tjR. Since there are q cosets of tjR contained ineach coset of tj−1R, it follows that there are precisely q balls of radius q−jcontained in each ball of radius q−j. We can also conclude that if two ballsof radius q−j differ, then they are separated by a distance of at least q−j.In the same spirit as for R, we define a norm on Rn by∥∥∥(x(1), . . . , x(n))∥∥∥ = max(|x(1)|, . . . , |x(n)|).This norm also satisfies the ultrametric property under addition, and there-fore also has the property that two distinct balls of the same radius q−j areseparated by at least q−j , and has the further property that each ball ofradius q−j−1 contains exactly qn balls of radius q−j.We now describe the Haar probability measure dx on R: The ballB(0, 1) = R is assigned a measure of 1, and any closed ball of radius q−j isassigned a measure of q−j. With respect to this Haar measure, any coset oftjR has measure q−j . We will also write dx for the Haar measure on Rn,which is the n-fold product of the Haar measure on R.564.3. K-Valued FunctionsGiven a complete discrete valuation ring R, we let K be the field offractions over R. Each nonzero element of K is of the formx =∞∑j=Mxjtj (4.3)for some M with xM 6= 0. The field K is called a non-archimedean localfield. We extend the absolute value on R to all of K by defining |x| = q−M ,where M is as in (4.3). We extend the Haar probability measure on R toa σ-finite Haar measure on K by defining the measure of a closed ball ofradius qj to be qj , and extend the Haar measure on Rn to a σ-finite Haarmeasure on Kn that assigns a measure of qjn to a closed ball of radius qj .Note that R can be recovered from K algebraically as the ring of integersof K, and topologically as the closed unit ball of K.4.3 K-Valued FunctionsWe will briefly discuss the notions of continuity and differentiability of func-tions from K to K for non-archimedean lcoal fields K. A good resource forthis is [41].Continuity of functions is defined in the same way as for any metricspace. Note that a series of functions∞∑j=0fj(x),where fj : K → K, is uniformly convergent on some set S whenever theabsolute values of fj(x) approach zero uniformly on S. This follows fromthe fact that a series of elements of K converges if and only if the termsapproach zero.A function f is said to be differentiable at the point x if the limitlimh→0f(x+ h)− f(x)hexists at the point h. The function f is said to be continuously differentiableon a set E if f is differentiable for all x ∈ E and f ′(x) is continuous for allx in E.The main point of departure from complex-valued functions is the fol-lowing. If a complex-valued function f is continuously differentiable on acompact set E, it follows that f(x+h) = f(x)+hf ′(x)+o(h), where the o(h)574.4. Hensel’s Lemmaterm is independent of x. This follows because of the uniform continuity ofthe derivative on E and the mean value theorem: given ǫ > 0, there is a δindependent of x such that |f ′(x) − f ′(y)| < ǫ whenever |x − y| < δ, so bythe mean value theorem, we have that f(x)− f(y) must be within ǫ(y − x)of f ′(x)(y − x). This shows the desired inequality.There is no simple “mean value theorem” for non-archimedean local fieldsK, and in fact it we do not have an x-independent estimate of the form f(x+h) = f(x)+hf ′(x)+ o(h) for K-valued continuously differentiable functionson a compact set E. The following example is presented in Robert’s book[41, Chapter 5, Subsection 1.1, Example 1]:Example 4.3.1 (Example of a continuously differentiable function that isnot strictly differentiable). Let K = Qp, and let Let f(x) be the functionthat is equal to p2n on the open ball of radius p−2n centered at pn, and 0 offof such open balls. For all nonzero x, we have that f ′(x) = 0 because f(x) islocally constant away from zero. At 0, it is easily seen that f ′(0) = 0 becausethe difference quotient f(x)−f(0)x will always be at most p−n in absolute valuefor |x| ≤ p−n. However, the difference quotient for x = pn and y = pn+ p2nis seen to be 1: the numerator and denominator are both p2n.To prevent such behaviour, we need a condition that is stronger thancontinuous differentiability.Definition 4.3.2 (Strictly Differentiable Function). A function f : K → Kis said to be strongly differentiable on a compact set E if f(x+ h) = f(x) +hf ′(x) + o(h), where the o(h) constant does not depend on x ∈ E.Of course, such a function is necessarily continuously differentiable.In [20], the term Very Strongly Differentiable is used for functionswhere the error term o(h) is in fact O(hk) for some k > 1, where the implicitconstant cannot depend on x. This implies a Ho¨lder condition of order k−1on f ′.4.4 Hensel’s LemmaNonarchimedean local fields K have a special property that guarantees theexistence of solutions to certain kinds of equations given the existence of“near-solutions”. This fact is very useful for locating configurations in suchfields. We will follow the presentation of Hensel’s lemma in [41].Lemma 4.4.1. [Hensel’s Lemma] Let f : R→ K be a strictly differentiablefunction satisfying the inequality |f(x+h)−f(x)−hf ′(x)| < |h| for all x ∈ R.584.4. Hensel’s Lemma(For instance, any polynomial with coefficients in R has this property.) Letx0 be such that |f(x0)| < 1 and |f ′(y)| = 1 for all y such that |y−x0| < 1. (Iff is a polynomial with coefficients in R, it is enough to verify that |f(x0)| < 1and that f ′(x0) = 1 in order for this condition to hold.) Then there exists apoint x such that |x− x0| < 1 and such that f(x) = 0.Proof. We will use a procedure similar to Newton’s method to locate a zerox of f in K. If f(x0) = 0, then we can simply take x = x0. So we supposeinstead that x 6= x0. We consider the quantity x1 = x0 − f(x0)/f ′(x0). Iclaim that f(x1) has absolute value less than q−1, where q−1 is the absolutevalue of a uniformizing element of K.To see this, notice that f(x1) = f(x0 − f(x0)/f ′(x0)). By the assump-tions on f , x1 satisfies the inequality|f(x1)| =∣∣∣∣f(x1)− (f(x0)− f ′(x0) f(x0)f ′(x0))∣∣∣∣ < ∣∣f(x0)/f ′(x0)∣∣ .Therefore, by the bound on f ′(x0), we have that |f(x1)| ≤ |f(x0)|. Further-more, by assumption, we have that |f ′(x1)| = 1We can iterate this procedure. Suppose by induction that |xj − x0| < 1,|f ′(xj)| = 1 and f(x) ≤ q−j for some j. We let xj+1 = xj − f(xj)f ′(xj) . Thenxj+1 satisfies the inequality|f(xj+1)| =∣∣∣∣f(xj+1)− (f(xj)− f ′(xj) f(xj)f ′(xj))∣∣∣∣ < ∣∣f(xj)/f ′(xj)∣∣and by the discrete nature of the absolute value it follows that f(xj+1) isstrictly less than q−(j+1). We have that f ′(xj+1) = 1 by assumption because|xj+1 − x0| ≤ max(|xj+1 − xj|, |xj − x0|) < 1.Therefore, xj is a Cauchy sequence of points in R such that f(xj)→ 0.It follows that the limit of this sequence, x, satisfies f(x) = 0. This proof works under somewhat weaker assumptions than those givenabove.Lemma 4.4.2. [Hensel’s Lemma, General Version] Let B ⊂ K be an openball and let f : B → K be a strictly differentiable function satisfying theinequality |f(x + h) − f(x) − hf ′(x)| < |hf ′(x)| for all x ∈ B and all h <rad(B). Suppose there exists x0 ∈ B such that∣∣∣ f(x0)f ′(x0) ∣∣∣ is less than the radiusof B. Then there exists a unique point x such that x ∈ B and such thatf(x) = 0.594.5. The Height FunctionThe proof of this lemma is a straightforward adaptation of Lemma 4.4.1and will be omitted.The most important application of this lemma is the case where f is apolynomial (or power series) with coefficients in R. In this instance, theerror in approximating f(x+h) linearly is bounded above in absolute valueby |h2| < |hr|. Taking r = f ′(x0), we have that the error in the linearapproximation is bounded above by hf ′(x0) on a ball of radius f ′(x0). Aslong as there exists x0 such that∣∣∣ f(x0)f ′(x0) ∣∣∣ ≤ f ′(x0), i.e. |f(x0)| < |f ′(x0)|2,then there will be a unique zero in the ball of radius f ′(x0) centered at x0.It is important to note that the condition that |f(x+h)−f(x)−hf ′(x)| <|hf ′(x)| implies that |f ′(x)| is constant on B. To see this, suppose that thereare x, y ∈ B such that |f ′(x)| 6= |f ′(y)|. Because |f(y)−f(x)−(y−x)f ′(x)| isstrictly smaller than |(y−x)f ′(x)|, we have that |f(y)−f(x)| = |(y−x)f ′(x)|.Then, on the one hand, we have that |f(y)− f(x)| = |(y − x)f ′(x)| = |y −x||f ′(x)|, and on the other hand, we have that |f(y)−f(x)| = |(y−x)f ′(y)| =|y − x||f ′(y)| so |f ′(x)| = |f ′(y)|.This theorem can be further strengthened to show that, under the condi-tions of the lemma, f maps B bijectively onto a ball of radius rad(B)/|f ′(x)|centered at 0. The uniqueness follows from the fact that if f(x) = 0, then|f(x+h)−hf ′(x)| < |hf ′(x)|, and so |f(x+h)| = |hf ′(x)| by the ultrametricinequality.Theorem 4.4.3 (Inverse Function Theorem for Local Fields). Let f : B →K be a strictly differentiable function defined on a ball B ⊂ K such that|f(x + h) − f(x) − hf ′(x)| < |hf ′(x)| and such that |f ′(x)| ≥ rad(B) forall x in some open ball B and all |h| < rad(B). Then |f ′(x)| is constanton B. Furthermore, f maps B bijectively onto an open ball f(B) of radiusf ′(x)rad(B). Thus, f−1 is well-defined on f(B) and the derivative of f−1is given by (f−1)′(y) = 1f ′(f−1(y)) for all such y. In particular, |(f−1)′(y)| isconstant and equal to 1|f ′(x)| on f(B).4.5 The Height FunctionFor the purposes of this section, we will assume thatK = Qp or K = Fq((t)).The results in Chapter 5 require a notion of the height of an element of Knfor K = Qp and Fq((t)). We will first define a height function for the localfields Fq((t)) and for Qp, and build up a height function for arbitrary localfields using these two examples. This function is discussed in [18].604.5. The Height Function4.5.1 Finite Characteristic CaseLet K be a function field Fq((t)): a local field of finite characteristic. Let xbe an element of R, the ring of integers of K. We can write x in the form∞∑j=0xjtjwhich is a power series in the variable t, where xj ∈ Fq for q = pf . Additionin R is componentwise: if x =∑∞j=0 xjtj and y =∑∞j=0 yjtj thenx+ y =∞∑j=0(xj + yj)tjandxy =∞∑j=0 ∑k1+k2=jxk1yk2 tj.Each sum∑k1+k2=jxk1yk2 is finite, so this product is well-defined.If x and y are known to be polynomials (i.e., they only have a finitenumber of nonzero terms), then deg(x + y) ≤ max(deg(x),deg(y)) anddeg(xy) ≤ deg(x) + deg(y). We can then define a height on R in the fol-lowing way: if x 6= 0 is a polynomial in R, then the height hFq((t))(x) of xwill be defined to be the degree of x; if x has infinitely many nonzero terms,then the height hFq((t))(x) will be defined to be ∞.4.5.2 p-Adic CaseSomething similar can be done if K = Qp and R = Zp. We can write x ∈ Zpin the formx =∞∑j=0xjpj.If the sum is finite, then x can be thought of as an integer written in basep. So we can define a height function on Zp as follows: the height hQp(x)of x ∈ Zp is the number of digits in the base p expansion of x minus one ifx has a finite expansion in Zp, and infinity if x has infinitely many nonzeroterms.It would have been convenient if this function hQp had the same addi-tion and multiplication bounds as the function hFq((t)); however, this is notthe case: the sum hQp(x + y) may be as large as max(hQp(x), hQp(y)) + 1.However, hQp(xy) ≤ hQp(x) + hQp(y).614.5. The Height Function4.5.3 Negatives of Elements of Finite HeightIn the case where K = Fq((t)), the height function satisfies hFq((t))(−x) =hFq((t))(x) for all x of finite height. Unfortunately, no analogue of this equa-tion exists for Qp. For example, the element 1 has height equal to 1. How-ever, the element −1 is equal to∞∑j=0(p− 1)jand therefore does not have finite height. However, the negative of an ele-ment of Zp of finite height still has a predictable pattern.Let z ∈ Zp. Then z has an expansion of the form 4.1:z =∞∑j=0zjpj .We will call the collection of digits {z0, . . . , zd−1} the d least significant digitsof z. We will say that z(1) and z(2) ∈ Zp differ only in the d least significantdigits if z(1)j = z(2)j for all j ≥ d.If z has height at most h, then −z will differ from −1 in only the h leastsignificant digits. This fact allows us to prove the following lemmaLemma 4.5.1 (Corollary 2.2 from [18]). Let x and y be elements of Zp ofheight at most h, and let δ ∈ R, δ 6= 0 satisfy the inequality |δ| ≤ p−(h+1).Then we have that |(−x+ δ) − y| ≥ |δ|.Proof. We first consider the case in which x = 0. If y = 0 as well, then(−x+ δ)− y is equal to δ. If x = 0 and y is nonzero, then |(−x+ δ)− y| isequal to |y− δ|. Since y is nonzero and has height at most h, it follows that|y| ≥ p−h+1. Because |δ| ≤ p−(h+1) < p−h+1, it follows from the ultrametricinequality that |y − δ| = |y| > |δ|.So we are left with the case in which x 6= 0. Because x has heightat most h, it follows from the above discussion that −x differs from −1in only the first h digits. In particular, this implies that if we write−xas in (4.1), then (−x)h must be equal to p − 1. Thus (−x)h is nonzero.Then the nonzero term (−x)hph in the expansion of −x has absolute valueexactly p−h. Thus the term (−x+ δ)h is also equal to p − 1 because of thecondition on |δ|. However, y(k1,k2)h = 0 because y has height at most h. Thus|(−x+ δ)− y| ≥ p−h > p−h−1 ≥ |δ| as desired. 62Chapter 5Configurations II5.1 IntroductionWe will now discuss the proofs of Theorems 1.2.1, 1.2.2, 1.2.3, and 1.2.4.We will begin by giving some context for these results.A major problem in additive combinatorics is locating arithmetic pro-gressions in sets. A classic result in the area is due to Roth [42]. Rothestablishes that, for any δ, and any sufficiently large N ≥ N0(δ), any subsetof Z/NZ containing at least δN elements must contain a 3-term arithmeticprogression. On the other hand, for any ǫ > 0 Behrend [2] presents an ex-ample of a subset of Z/NZ for N ≥ N1(ǫ) with at least CǫN1−ǫ elementsthat does not contain a 3-term arithmetic progression.The question of how large a set guarantees the existence of a 3-termarithmetic progression remained open for finite abelian groups other thanZ/NZ. The problem of obtaining bounds on the maximum size of a subsetof (Z/3Z)n that does not contain a 3-term arithmetic progression is calledthe capset problem.The largest known construction of a subset of (Z/3Z)n that does notcontain a 3-term arithmetic progression is due to Edel [13]. This set containsCn1 elements for some C < 3. The best known upper bound, of the formCn2 for some C1 < C2 < 3 is due to Ellenberg and Gijswijt [16], who use apolynomial method based on a similar argument of Croot, Lev, and Pach[9]. A summary of the history of problems related to arithmetic progressionsin finite groups prior to the 2017 results is given by Wolf [53].It is natural to ask about infinite versions of the capset problem. The-orem 1.2.1 establishes that there are subsets of K = F3((t)) of Hausdorffdimension 1 that do not contain 3-term arithmetic progressions. This issomewhat surprising, because the ring of integers R of K (viewed as anabelian group) is the projective limit of the groups (Z/3Z)n.The proofs of all four theorems follow the same general procedure ofChapter 3.635.2. A Single Step5.2 A Single Step5.2.1 Polynomial, Nonsingular CaseWe will start by describing a step of the construction for Theorem 1.2.1. Wewill make use of the height function described in Chapter 4.Proposition 5.2.1. [Proposition 2.3 from [18]] Let T1, . . . , Tv be sets, eachof which is a union of balls of radius q−µ, and let p(x1, . . . , xv) be a poly-nomial satisfying∣∣∣ ∂p∂xi0 ∣∣∣ ≥ q−A for some i0 and for all (x1, . . . , xv) ∈ T1 ×. . .× Tv. Then there exists a positive real number c depending on A, on thefield K, and on µ with the following property. Subdivide each ball of radiusq−µ into balls of radius q−ν. Then, if µ is sufficiently large, there exist setsS1 ⊂ T1, . . . , Sv ⊂ Tv such that:(a) There are no solutions to p(x1, . . . , xv) = 0 with x1 ∈ S1, . . . , xv ∈ Sv.Furthermore, p satisfies the bound |p(x1, . . . , xv)| ≥ cq−ν on S1×· · ·×Sv.(b) For 1 ≤ i ≤ v and any ball U of radius q−ν contained in one of theq−µ-balls of Ti, we have that Si ∩ U is a ball of radius ≥ cq−νn/D.Proof. For convenience, we will also assume that the index i0 = v.Each closed ball B of radius q−ν contains exactly one element of Rn ofheight at most ν (here, the height of an element of Rn is the maximum of theheights of the components.) Suppose x1, . . . , xv ∈ Rn and each of x1, . . . , xvhas height at most ν. Let p be an nv-variate polynomial of degree at mostd, with coefficients of height at most b. Let s :=(d+nvnv)be the dimension ofthe space of nv-variate polynomials of degree d. Then p(x1, . . . , xv) is a sumof at most s terms, each of which is either of height at most b+ hd, or thenegative of an element of height at most b+dν. For us, the important pointis that the coefficient of ν is equal to d. Thus we can write p(x1, . . . , xv) asa sum of two terms: a term with height at most b+dν+ s, and the negativeof such a term (the s is unnecessary in the case of Fq((t))). It follows fromCorollary 4.5.1 (or, in the case of Fq((t)), the fact that the negative of anelement of finite height also has finite height) that if |δ| ≤ q−(b+dν+s+1) that|p(x1, . . . , xv) + δ| ≥ |δ|.This fact will serve as a local-field substitute for the following algebraicfact in Rn: if p is an nv-variate polynomial of degree d with coefficients in Zand x1, . . . , xv are multiples of N−1 for some integer N , then p(x1, . . . , xv) isa multiple of N−d, so p(x1, . . . , xv) is a multiple of N−d, so p(x1, . . . , xv)+ δdiffers from 0 by at least δ provided that |δ| < 2N−d. This simple algebraicfact is the key to Ma´the´’s construction of the set in Theorem A Single StepWe now use the fact that, if δ < 1 and if p satisfies the bound q−A ≤∣∣∣ ∂p∂xv ∣∣∣uniformly on a compact set T1× · · · ×Tv, then q−A|δ| ≤ |p(x1, . . . , xv + δ)−p(x1, . . . , xv)| ≤ δ, where the last inequality holds because any polynomialwith coefficients in R has derivatives bounded in absolute value by 1 on R.This implies that if |δ| < q−(b+dν+s+1) and x1, . . . , xv all have height at mosth, then p(x1, . . . , xv + δ) is not within q−A|δ| of zero.Finally, since all of the derivatives of p are bounded above by 1 in absolutevalue, we have that the same bound holds provided that x1, . . . , xv are allwithin closed balls of radius q−A−(b+dν+s+1)−1 determined in the followingway: given B ⊂ Tj of radius q−ν for 1 ≤ j ≤ v − 1, select Sj ∩B to be theunique ball containing an element of height h. Then, selecting any δ with|δ| = q−A−(b+dν+s+1)−1, we define Sv ∩ B to be the unique ball containingxB + δ, where xB is the unique element of height at most ν in B. 5.2.2 One Dimension, Nonsingular CaseWe will establish an analogue of Proposition 3.3.1. The proof follows asimilar strategy. The analogue of Rolle’s theorem that will be used for thispurpose is Theorem 4.4.3.Let f be a strictly differentiable K-valued function in v variables withnonvanishing gradient defined in an open ball B ⊂ R containing the origin.Suppose that we are given i0 ∈ {1, 2, · · · v}, an integer µ ≥ 1, a smallconstant c0 > 0 and compact subsets T1, . . . , Tv ⊂ R. We will assume thatthe sets T1, . . . , Tv satisfy the following conditions.1. Each Ti is a union of disjoint closed balls of radius q−µ. Let us denoteby Jµ(Ti) this collection of balls.2. The set T1 is disjoint from the set Ti′ if i 6= i′.3.∣∣∣ ∂f∂xi0 (x)∣∣∣ ≥ c0 and |∇f(x)| ≤ c−10 for all x ∈ T1 × · · · × Tv.Proposition 5.2.2. Given f, µ, i0, c0 and T = (T1, · · · , Tv) satisfying theseassumptions, there exist a small rational constant c1 > 0 and an integer ν0(depending on all these quantities), for which the following conclusions hold.For all ν ≥ ν0, one can find compact subsets Si ⊆ Ti for all 1 ≤ i ≤ v suchthat(a) There are no solutions of f(x) = 0 with x ∈ S1 × · · · × Sv.655.2. A Single Step(b) For each J ∈ Jµ(Ti), we decompose J into closed balls of radius q−ν withdisjoint interiors and call the resulting collection of intervals Iν(J, i).Then for each i 6= i0 and each I ∈ Iν(J, i), the set Si ∩ I is an intervalof length c1q(1−v)ν .(c) For every J ∈ Jµ(Ti0), there exists I ′ν(J, i0) ⊆ Iν(J, i0) with#(I ′ν(J, i0)) ≥ (1− 1qµ )#(Iν(J, i0)) (5.1)such that for each I ∈ I ′ν(J, i0),|Si0 ∩ I| ≥ c1q−ν . (5.2)Unlike part (b), Si0 ∩ I need not be a ball; however, it can be written asa union of disjoint balls of radius c1qν(1−v).Proof. We want to mimic the strategy of the proof of Proposition 3.3.1.Let f(x1, . . . , xv) be a strictly differentiable, nonsingular function definedon T satisfying the above conditions. For simplicity, we will assume i0 = v.Then, by the definition of strict differentiability, there exists an integer µ0such that qµ0 > c−10 and such that, for any open ball B of radius at mostq−µ0 , x ∈ B, and h < rad(B),|f(x+ h)− f(x)− hf ′(x)| ≤ |hf ′(x)|. (5.3)If µ < µ0, then decompose each constituent ball of T1×· · ·×Tv into balls ofradius µ0. Because we can always perform this operation without affectingthe proof of the lemma, we will always assume that µ ≥ µ0 for this value ofµ. Let ν > µ. For each ball B of radius q−ν contained in Ti for any i 6= v,we will take Si ∩ B to consist of a single (arbitrarily chosen) ball of radiusc1q−ν(v−1), where c1 is a constant to be determined later.For a fixed x1 ∈ S1, . . . , xv−1 ∈ Sv−1, we will define the functionfx1,...,xv−1 : Tv → K by fx1,...,xv−1(xv) = f(x1, . . . , xv). We will consider thebehaviour of this function on a single ball of radius q−µ. Let J ∈ Jµ(Tv). Wehave that∣∣∣ ∂f∂xv ∣∣∣ ≥ c0 for x ∈ T. Furthermore, by the choice of µ0, we havethat fx1,...,xv−1 satisfies the inequality (5.3) on J . Therefore, we can applyTheorem 4.4.3 on J . This theorem states that |f ′x1,...,xv−1(x)| is constanton J and that fx1,...,xv−1 maps J bijectively onto a ball of radius equal to|f ′x1,...,xv−1(x)|q−µ. The bijectivity of this map guarantees that, for a fixedx1, . . . , xv−1 there is at most one x ∈ J such that fx1,...,xv−1(x) = 0.665.2. A Single StepLet A be a collection of points (x1, . . . , xv−1) such that A contains a singlerepresentative from each of the cubes of radius c1q−ν(v−1) that constituteS1 × · · · × Sv−1. Then A will have no more than qν(v−1) elements. Let Ibe a ball of radius c1q−ν(v−1) contained in Sv. For each x′ = (x1, . . . , xv−1)in A, we will consider the image fx′(I). By the argument in the previousparagraph, this image has radius at most c−10 c1q−ν(v−1).Now we will consider fx′+h(J) for |h| < c1q−ν(v−1) and an arbitrary ballJ ∈ Jµ(Ti). By assumption each component of the derivative of f is boundedabove by c−10 on T; therefore, fx′+h(x) differs from fx′(x) by an amount thatis strictly less than c−10 c1q−ν(v−1). Thus fx′+h(x) is contained inside the ballfx′(I). It follows from this argument that if x satisfies fx∗(x) = 0 for somex∗ ∈ S1 × · · · × Sv−1 and some x ∈ J that x is within a c−10 c1q−ν(v−1)-neighbourhood of a zero of fx′ for some x′ ∈ A. Call these zeros bad points.There are at most qν(v−1) such values of x′, so there are at most qν(v−1)bad points. Let Sv be the union of balls of radius c−10 c1q−ν(v−1) that do notcontain a bad point.Select c1 = c0q−3µ. Then each ball in Jµ(Tv) contains qνq−µ balls ofradius q−ν , each of which contains c0c−11 qν(v−2) = q3µqν(v−2) balls of ra-dius c−10 c1q−ν(v−1). Consider the balls of radius q−ν that contain more thanq2µqν(v−2) balls of radius c1qν(v−1) that contain a bad point. The pigeon-hole principle implies that the maximum possible number of such balls isqν(v−1)q−2µqν(v−2)= q−2µqν . Therefore, for each J ∈ Jµ(Tv), we have that allexcept for at most a q−µ-fraction of the balls in I(J, v) contain at least(c0c−11 − q2µ)qν(v−2) = (q3µ − q2µ)qν(v−2) balls of Sv. This is at least a(1− q−µ) fraction, as desired. 5.2.3 One Dimension, General CaseWe will iterate Proposition 5.2.2 or Proposition 5.2.1 in order to establish thefollowing proposition, which applies even in situations where ∇f vanishessomewhere on T.Suppose that we have a multi-index α satisfying |α| = r, an integerµ ≥ 1, a small constant c0 > 0 and compact subsets T1, . . . , Tv ⊂ R, andan r-times strictly differentiable function f . We will make the followingassumptions:1. Each Ti is a union of disjoint closed balls of radius q−µ. Let us denoteby Jµ(Ti) this collection of balls. We will consider a function f suchthat the derivative ∂αf is nonzero.675.2. A Single Step2. T1 and Ti′ are disjoint if i 6= i′.3. The partial derivative ∂αf does not vanish on T1 × · · · × Tv, and isbounded below in absolute value by c0 on this set.Proposition 5.2.3. Given f, µ, α, c0 and T = (T1, · · · , Tv) satisfying theseassumptions, there exist a small constant c1 > 0 and an integer ν0 (depend-ing on all these quantities), for which the following conclusions hold.For ν ≥ ν0, there exist compact subsets Si ⊆ Ti for all 1 ≤ i ≤ v such that(a) There are no solutions to f(x) = 0 with x ∈ S1 × · · · × Sv.(b) For each J ∈ Jµ(Ti), let us decompose J into disjoint closed balls ofradius q−µ and call the resulting collection of balls IN (J, i).For every J ∈ Jµ(Ti) and every i, there exists I ′ν(J, i) ⊆ Iν(J, i) with#(I ′ν(J, i)) ≥ c2#(IN (J, i)) (5.4)such that for each I ∈ I ′ν(J, i), |Si ∩ I| is nonempty. Si ∩ I need not bea ball; however, it can be written as a union of disjoint balls of radiusc1q−ν(v−1). Here, c2 > 0 and may depend on f, r, c0, v, and µ, but noton ν.The proof of this proposition is omitted because of its similarity to the proofof Proposition 3.3.4. We can similarly iterate Proposition 5.2.1 to arrive atthe following proposition.Proposition 5.2.4. Given a polynomial function f of degree d, with integercoefficients, and a set T = (T1, · · · , Tv) that is expressible as a disjoint unionof q−µ-balls, there exist a small constant c1 > 0 and an integer ν0 (dependingon all these quantities), for which the following conclusions hold.For ν ≥ ν0, there exist compact subsets Si ⊆ Ti for all 1 ≤ i ≤ v such that(a) There are no solutions to f(x) = 0 with x ∈ S1 × · · · × Sv.(b) For each J ∈ Jµ(Ti), let us decompose J into disjoint closed balls ofradius q−µ and call the resulting collection of balls IN (J, i).For every J ∈ Jµ(Ti) and every i, there exists I ′ν(J, i) ⊆ Iν(J, i) with#(I ′ν(J, i)) ≥ c2#(IN (J, i)) (5.5)such that for each I ∈ I ′ν(J, i), |Si ∩ I| is nonempty. Si ∩ I is a ball ofradius c1q−ν(n/d). Here, c2 > 0 and may depend on f, c0, v, and µ, butnot on ν.685.2. A Single StepThis is proven by iterating Proposition 5.2.1 in the same way as in Propo-sitions 3.3.4 and Multidimensional CaseWe begin by proving a proposition, which is an analogue of Proposition3.3.5.Let m,n ≥ 1 and v ≥ 3 satisfy m ≤ n(v − 1), and let f : Knv → Kmbe a twice strictly differentiable function whose zero set has a nontrivialintersection with R. Suppose µ ≥ µ∗, where µ∗ is a large integer to beselected later, c0 > 0 is a small constant and T1, . . . , Tv ⊂ Rn are sets withthe following properties:1. Each Ti is expressible as a union of closed disjoint balls of radius q−µ,the collection of which will be called Jµ(Tk). The sets Ti and Ti′ willbe disjoint for i 6= i′.2. On {x ∈ T1 × · · · × Tv : f(x) = 0}, the matrix Df is of full rank, witha submatrix B whose determinant is bounded below by C0, and whoseentries are bounded above by C1.3. On Rnv the operator norm of the Hessian D2f is bounded above byC2.We are now ready to state the main proposition in the multidimensionalsetting.Proposition 5.2.5. Given f, µ C0, C1 and C2 as above, there exists aconstant c1 > 0 and an integer ν0 depending on these quantities for whichthe following conclusions hold. For ν ≥ ν0, set qλ = c1q−ν(v−1). There existcompact subsets Si ⊆ Ti for all 1 ≤ i ≤ v such that(a) There are no solutions to f(x) = 0 with x ∈ S1 × · · · × Sv.(b) For each 1 ≤ i ≤ v and J ∈ Jµ(Ti), let us decompose J into disjointclosed balls of radius q−ν and call the resulting collection of balls Iν(J, i).There exists I ′ν(J, i) ⊆ Iν(J, i) such thatSi ⊆⋃{I : J ∈ JM (Ti), I ∈ I ′ν(J, i)}.More precisely, for each I ∈ I ′ν(J, i), the set Si ∩ I is a single ball ofradius q−λ, provided i 6= v. For i = v and I ∈ I ′ν(J, v), the set Sv ∩ I695.2. A Single Stepis not necessarily a single ball of radius q−λ, but a union of such balls,with the property that|Sv ∩ I| ≥(1− q−µ) q−nν . (5.6)(c) The subcollections I ′ν(J, i) of balls are large subsets of the ambient col-lection Iν(J, i), in the sense that for all 1 ≤ i ≤ v, J ∈ Jµ(Ti),#(I ′ν(J, i)) ≥ (1− q−µ)#(Iν(J, i)) . (5.7)Except for the proof of Lemma 3.3.6, the proof of Proposition 3.3.5depends only on the combinatorial structure of the bad boxes (recall thata ball in Rn is an n-fold Cartesian product of balls in R), and thereforecan be repeated in the non-archimedean setting. Therefore, we will restrictourselves to proving a non-archimedean version of Lemma 3.3.6.Lemma 5.2.6 (Lemma 3.1 from [18]). There exists µ0(C0, C1, C2) > 0 suchthat the following statement holds for all µ ≥ µ0. Let T be an nv-dimensionalball of radius q−µ and let f(x1, . . . , xv) : T → Km be a function such thatDf has an m-by-m minor that is, in absolute value, at least a constantC0 on all of T and whose entries are bounded above in absolute value by aconstant C1. Suppose further that C2 is an upper bound for the operatornorm of the second derivative of f . Let Zf be the set of (x1, . . . , xv) suchthat f(x1, . . . , xv) = 0. Subdivide the ball T into balls of radius q−λ. If λ issufficiently large, then the number of balls that intersect the zero set of f isat most C3q−µ+λ(nv−m) where µ0 and C3 can depend on C0, C1, and C2 butnot on λ.Proof. Let x0 be a point in Zf . If µ is sufficiently large, then there existsa fixed m-by-m submatrix B of Df , indexed by the columns (j1, . . . , jm),such that B has determinant with absolute value at least C0 for all x ∈ T.Consider the vector space U spanned by the vectors eji whose ji componentis 1 and whose other components are 0. Consider points of the form x0 + uwhere u is a vector in the vector space U of magnitude at most q−µ. Bythe assumptions on Df , we have f(x0 + u) = f(x0) + Dfx0u + O(‖u‖2).Here, f(x0) = 0, and ‖Dfx0u‖ ≥ k0 ‖u‖, where k0 = C0C−(m−1)1 , as canbe seen from the adjugate formula for the inverse of B. So we have that‖f(x0 + u)‖ ≥ C0 ‖u‖+O(‖u‖2). This is guaranteed to be positive providedthat µ is sufficiently large.Let λ be larger than µ. For a given x ∈ Zf , consider the slab consistingof points x + U + w where w has a zero in each of the ji components and705.3. Construction of Esatisfies |w| ≤ q−λ; i.e., the q−λ-neighbourhood of x+ U . Let x+ u+ w besome point in this slab. We have that f(x+ u+w) = f(x) +Dfx(u+w) +O(‖u+ w‖2) = Dfx(u+w)+O(‖u+ w‖2). This has norm at least k0 ‖u‖−C1 ‖w‖ + O(‖u+ w‖2). Therefore, f(x + u + w) is nonzero provided that‖u‖ is greater than C1k0 ‖w‖, and provided that µ is sufficiently large that theO(‖u+ w‖2) term has norm smaller than k0 ‖u‖. Recall that ‖w‖ ≤ q−λ, soif µ is sufficiently large this inequality will hold provided that ‖u‖ is at least2C1k0q−λ. Thus, subdividing this slab into q−λ-balls, we have Zf will intersectonly at most(2C1k0)mballs in the slab. Taking the union over disjoint parallelslabs that cover the q−µ ball, we have a total of O((C1k0)mqλ(nv−m)−µ)intersections. 5.3 Construction of EThe construction of E is very similar to the construction of the set E inChapter 3. We will start with E0 = Bn, where B ⊂ R is a sufficiently smallball to satisfy the conditions of Theorem 1.2.1, 1.2.2, or 1.2.3. We will letD be equal to the dimension in the appropriate theorem statement: D = ndin the case of Theorem 1.2.1, D = 1v−1 in the case of Theorem 1.2.2, andD = mv−1 in the case of Theorem General ProcedureWe will keep a running queue Q that will guide the construction.One minor difference in the proof of Theorem 1.2.1 is that the numberof variables v is allowed to vary. For the cases of Theorems 1.2.2 and 1.2.3,take v = v1 = v2 = · · · throughout the rest of this argument.Fix a sequence ǫj such that ǫj → 0. We select λ0 sufficiently large so thatthe ball E0 contains at least v1 + 1 balls of radius q−λ0 . Let B(0)1 , . . . , B(0)M0be an enumeration of the balls of radius q−λ0 contained in Bn and let Σ0 bethe family of v1-tuples of distinct such balls, ordered lexicographically andidentified in the usual way with the family of injections from {1, . . . , v1} into{1, . . . ,M0}. Let Q0 be the queue consisting of 3-tuples{(1, σ, 0) : σ ∈ Σ0},where the queue elements are ordered so that (1, σ, 0) precedes (1, σ′, 0)whenever σ < σ′.715.3. Construction of EStage 1 At Stage 1, we consider the first queue element (1, σ, 0). LetT1 = B(0)σ(1) , . . . , Tv = B(0)σ(v).First, we will consider the case of Theorems 1.2.1 and 1.2.2. Let f = f1.We have by assumption that there is a lower bound q−A1 on the derivative|∂αf | for some appropriate i0. We decompose each ball of radius q−λ0 intoballs of radius q−µ1 , where µ1 ≥ λ0 and µ1 > µ∗, where µ∗ is as in Proposi-tion 5.2.3 or 5.2.4 applied to T1, . . . , Tv . We apply either Proposition 5.2.3 orProposition 5.2.4 to arrive at sets S1, . . . , Sv with the properties guaranteedby the corresponding proposition. Let e0 be the quantity c2 appearing inthe proposition. We can select ν = ν1 in the proposition to be sufficientlylarge that the quantity q−λj := c2q−ν1n/D appearing in Proposition 5.2.4or in Proposition 5.2.3 is larger than q−ν1(n/D+ǫ1). We will also select νsufficiently large that q−ν1ǫ1 < e0 and so that ν1 > exp(µ1).Now, we will consider the case of Theorem 1.2.3. In the case of Theorem1.2.3, we know thatDf1 has full rank on T1×· · ·×Tv by assumption. Becausethis set is compact, it follows that there exists some C0 such that, for eachx ∈ T1×· · ·×Tv, Df1 has a minor with absolute value greater than or equal toC0 at x, and that each of the entries of Df will be bounded above in absolutevalue by C1 for some C1. The uniform continuity ofD2f also guarantees thatD2f will be bounded above by C2 in operator norm, for some appropriatevalue C2. We can then select µ1 ≥ µ∗, where µ∗ is as in Proposition 5.2.5.Select ν = ν1 in Proposition 5.2.5 to be sufficiently large so that that thequantity q−λ1 := cq−ν1/D+Cµ1 appearing in Proposition 5.2.5 is larger thanq−ν1(n/D+ǫ1) For convenience, we will simply take e0 = 12 <(1− 1qµ1). Wealso will take ν1 > exp(µ1).In any case, we arrive at sets S1 ⊂ T1, . . . , Sv ⊂ Tv with the propertythat f1 is nonzero for x1 ∈ S1, . . . , xv ∈ Sv. We will define a subset E1 ⊂ E0in the following way. We take E1 ∩ T1 = E0 ∩ S1, E1 ∩ T2 = E0 ∩ S2, . . . ,E1 ∩ Tv = E0 ∩ Sv. All x ∈ E0 \ (T1 ∪ · · · ∪ Tv) will be in E1. This gives asubset E1 ⊂ E0 that can be expressed as a disjoint union of balls of radiusq−λ1 .Let E1 be the collection of balls of radius q−λ1 whose disjoint union isE1. Enumerate the balls of E1 as B(1)1 , . . . , B(1)M1 . For ℓ = 1, 2, define Σ(ℓ)1 tobe the collection of vℓ tuples of distinct such balls, ordered lexicographicallyand identified in the usual way with the family of injections from {1, . . . , vℓ}into {1, . . . ,M1}. We then form the queue Q′1 consisting of 4-tuples of theform{(ℓ, σ, 1) : 1 ≤ ℓ ≤ 2;σ ∈ Σ(ℓ)1 },arranged so that (ℓ, σ, 1) precedes (ℓ′, σ′, 1) if ℓ < ℓ′, and so that (ℓ, σ, 1)725.3. Construction of Eprecedes (ℓ, σ′, 1) if σ < σ′. Arrive at the queue Q1 by appending the queueQ′1 to Q0.Stage j We will now describe Stage j of the construction for j > 1. Wefollow essentially the same procedure as in Stage 1. We begin with a de-creasing family of sets E0, . . . Ej−1. Each Ej′ is a union of balls of radiusq−λj′ , the collection of which is called Ej′ . The family of vℓ′ tuples of dis-tinct balls in Ej′ will be denoted Σ(ℓ′)j′ . We have a queue Qj−1 consistingof 3-tuples (ℓ′, σ′, j′), where we have 0 ≤ j′ ≤ j − 1, 1 ≤ ℓ ≤ j′ + 1,and σ′ ∈ Σ(ℓ′)j′ . The set Ej−1 has the property that fℓ′(x1, . . . , xv) 6= 0 forx1 ∈ B(j′)σ′(1) ∩ Ej−1, . . . , xv ∈ B(j′)σ′(vℓ′ )∩ Ej−1 for any (ℓ′, σ′, j′) in the firstj − 1 elements of the queue Qj−1. Consider the jth queue element (ℓ, σ, j0),where ℓ ≤ j0 ≪ j. Let T1, . . . , Tv be the sets Bσ(1)∩Ej−1, . . . , Bσ(vℓ)∩Ej−1.We consider a variety of cases depending on whether we are consideringTheorem 1.2.1, Theorem 1.2.2, or Theorem 1.2.3.Case 1: Theorem 1.2.1 or 1.2.2 Let f = fℓ. In this case, we have byassumption that |∂αf | is nonzero on all of T1 × · · · × Tv for an appropriatemulti-index α. Let q−A be the lower bound on this partial derivative. Selectµj ≥ λj−1 to be larger than the quantity µ∗ appearing in Proposition 5.2.3or Proposition 5.2.4, as is appropriate. We can then apply Proposition 5.2.3or Proposition 5.2.4 to the sets T1, . . . , Tv, with the quantity ν = νj takento be sufficiently large that the quantity q−λj := c1q−nνj/D appearing inProposition 5.2.4 or in Proposition 5.2.3 is larger than q−νj(n/D+ǫj) Further-more, we also need q−ǫjνj < ej−1, where ej−1 is the quantity appearing asc0 in the appropriate proposition. We will also select νj > exp(µj).Case 2: Theorem 1.2.3. We have that on T1 × · · · × Tv that Df hasa nonvanishing minor and that D2f is continuous. By compactness, weconclude that Df is bounded below in absolute value by some value C0 andthe entries of Df are bounded above in absolute value by some number C1on T1 × · · · × Tv. We also have an upper bound C2 on the operator normof D2f . We can then select µj ≥ λj−1 to be larger than the quantity µ∗appearing in Proposition 5.2.5. We can then apply Proposition 5.2.5 tothe sets T1, . . . , Tv with the quantity νj taken to be sufficiently large thatthe quantity q−λj := c1q−νj/D appearing in Proposition 5.2.5 is larger thanq−νj(n/D+ǫj). We will select ǫj−1 = 12 in this case. We will also select νj sothat νj > exp(µj).735.3. Construction of EIn any case, we arrive at sets S1 ⊂ T1, . . . , Sv ⊂ Tv such that fℓ is nonzerofor (x1, . . . , xv) ∈ S1 × · · · × Sv. We will define a subset Ej ⊂ Ej−1 in thefollowing way. We take Ej ∩ T1 = Ej−1 ∩ S1, Ej ∩ T2 = Ej−1 ∩ S2, . . . ,Ej ∩ Tv = Ej−1 ∩ Sv. All x ∈ Ej−1 \ (T1 ∪ · · · ∪ Tv) will be in Ej. Thisgives a subset Ej ⊂ Ej−1 that can be expressed as a disjoint union of ballsof radius q−λj . Call the collection of such balls Ej , and let B(j)1 , . . . , B(j)Mjbe an enumeration of the balls in Ej. For each 1 ≤ ℓ ≤ j, we define Σ(ℓ)jto be the collection of vℓ-tuples of distinct balls in Ej. We equip Σ(ℓ)j withthe lexicographic order and identify Σ(ℓ)j with the set of injections from{1, . . . , vℓ} into Ej . Consider the queue Q′j consisting of 3 tuples (ℓ, σ, j),where 1 ≤ ℓ ≤ j + 1 and σ ∈ Σ(ℓ)j . We order the queue Q′j in the followingway: (ℓ, σ, j) will precede (ℓ′, σ′, j) if ℓ < ℓ′, and (ℓ, σ, j) precedes (ℓ, σ′, j) ifσ < σ′. We append the queue Q′j to Qj−1 to arrive at the queue Qj .5.3.2 Hausdorff Dimension of EWe compute the Hausdorff dimension of the set E. Unlike the calculationin Chapter 3, we use the definition of Hausdorff dimension directly insteadof appealing to Frostman’s lemma.Let U be a disjoint covering of a set E. Define the s-contribution of aball V (not necessarily in U) to bes(V ) :=∑U∈UU⊂Vr(U)swhere r(U) is the radius. Note that if U ∈ U , then we have that s(U) =r(U)s, and that if V1, . . . , Vr are disjoint subsets of V , then s(V1) + . . . +s(Vr) ≤ s(V ).Lemma 5.3.1. Let V be a ball of radius q−µj , and let s < D, where D isthe dimension promised for E in Theorem 1.2.1, 1.2.2, or 1.2.3. Suppose jis sufficiently large that sD < 1− 10ǫj . Then:1. If the majority of the volume of U contained in V is in balls of U ofradius strictly larger than q−λj+1 , then s(V ) ≥ 14q−µjs.2. If the majority of the volume of U contained in V is in balls of U ofradius no more than q−λj+1, then V contains at least q(λj+1−µj)s ballsof radius q−λj+1 that contain a ball of U .745.3. Construction of EProof of 1. We consider two cases: the case in which∑U∈Ur(U)≥q−νjr(U)n ≥ q−µjn4(5.8)and the case in which this inequality is not satisfied.Case 1 If the inequality (5.8) is satisfied, then we haveq−µjn4≤∑U∈Ur(U)≥q−νjr(U)n=∑µj≤ρ≤νj#(ρ)q−nρ=∑µj≤ρ≤νj#(ρ)q−sρq(s−n)ρ≤∑µj≤ρ≤νj#(ρ)q−sρq(s−n)µjwhere #(ρ) is the number of balls of radius q−ρ in U , and the last line holdsbecause s − n is negative. Dividing both sides of the inequality by q(s−n)µjgives ∑µj≤ρ≤νj#(ρ)q−sρ ≥ q−sµj4as desired.Case 2 Suppose that the inequality (5.8) is not satisfied. Let U ′ be thecollection of balls U ′ of radius q−νj that contain a ball of U . By Proposition5.2.4, Proposition 5.2.3, or Proposition 5.2.5 whichever is appropriate, wehave that at least an ej-fraction of the balls of radius q−νj contained in Bintersect E, and since the balls of radius larger than q−νj cover a set ofmeasure strictly smaller than q−µjn4 , it follows that U ′ must cover a set ofmeasure at least q−µjn4 . Therefore U ′ must consist of at leastejq(νj−µj )n4 balls.Each ball in U ′ intersects E and therefore contains at least one ball inEj+1. Thus, letting U ′′ ⊂ U be the collection of balls in U that are contained755.3. Construction of Ein a ball in U ′, we have that∑U∈U ′′r(U)s ≥ ejq−nDνjsqνjn−µjn=ej4qνj(n−nDs).Since we assumed sD < 1− 10ǫj , we know that the coefficient on νj is largerthan 10ǫj . Because νj > exp(µj) and because q−ǫjνj < ej , it follows that,for sufficiently large j, this is larger than 14q−µjs. Proof of 2. This argument is similar to Case 2 above. We define U ′ to bethe collection of balls of radius q−λj+1 that contain a ball of U . By thestatements in Propositions 5.2.4, 5.2.3 and 5.2.5, we have that V containsat least ejqνj−µj balls of radius q−λj+1 that intersect E. Therefore, if atleast half of the volume of U ′ is contained in balls of radius at most q−λj+1 ,this means that there must be at least ejq(νj−µj)n/2 balls of radius q−µj+1that contain a ball of U ′. But because sD < 1 − 10ǫj , it follows from thefact that νj ≥ exp(µj) and the choice of λj that ejqνj−µj/2 > q(λj+1−µj)s forsufficiently large j, as in Case 2 above. In the second part of the statement, provided that no more than a quarterof the measure of U ′ is contained in balls of radius between q−µj+1 andq−λj+1 , we can in fact replace λj+1 by µj+1 because if B is a ball of radiusq−λj+1 that intersects E, then each ball of radius q−µj+1 contained in B alsointersects E. Therefore, the proposition also holds with µj+1 replaced byλj+1.If, on the other hand, at least a quarter of the volume is contained insuch balls, then we can replace U by a covering U ′ in which any ball ofradius q−λj+1 containing such an intermediate ball is replaced by U ′; thes-contribution of U ′ will then be bounded by qs times the s-contribution ofU .So up to a constant factor, the statement in the preceding propositionalso applies with µj+1 in place of λj+1. This will allow us to use an inductiveargument to compute the Hausdorff dimension of the set E:Proposition 5.3.2. Let V be a ball of radius q−µj in Ej , and let U be acovering of V ∩E by balls of radius larger than q−µk contained in V , wherek > j. Let s < D. If j is sufficiently large depending on s, then for thecovering U we have s(V ) ≥ Cq−µjs for some appropriate constant C.765.3. Construction of EProof. Let s < t < n/D. We prove this statement by induction on k − j.If k − j = 1, this statement is implied by part 1 of Lemma 5.3.1 and thediscussion following that lemma. So it only remains to show the inductivestep.Suppose first that the majority of the volume of U is contained in ballsof radius strictly larger than q−µj+1 . Then we can apply part 1 of Lemma5.3.1, and the following discussion, to conclude that s(V ) ≥ Cq−µjs, andwe’re done. Therefore, we can assume that the majority of the volume ofU is contained in balls of radius at most q−µj+1 . Then by part 2 of Lemma5.3.1, there exist balls V1, . . . , Vr of radius q−µj+1 , where r > q(µj+1−µj)s,such that each ball Vj contains an element of U . By the additivity of s wehave s(V1) + . . . + s(Vr) ≤ s(V ), and by the inductive assumption we havethat s(Vt) ≥ Cq−µj+1s for each t. Thus s(V ) ≥ Cq−µjs as desired. 5.3.3 Minkowski Dimension of ELemma 5.3.3. The Minkowski dimension of the set E is equal to 1 (in thecase of Theorem 1.2.2) or n (in the case of Theorems 1.2.1 and 1.2.3).Proof. Let Nµ(E) be the number of closed balls of radius q−µ that arerequired to cover E. Notice that this is equivalent to the number of balls ofradius q−µ that intersect E. So we need to count the number of such ballsthat intersect E. Let q−µj denote the radius of the balls in Ej .If µ = µj for some j, and B is a ball of radius q−µj−1 that is not containedin T1, . . . , Tv at stage j of the construction, then the number of balls of radiusq−µj required to cover B is precisely(q−µj−1q−µj)n. This is greater than or equalto (qµj )−n+ǫ (provided that qµ is sufficiently small) by the growth rate ofthe νj.Now suppose µj < µ < µj+1, and consider any ball B of radius q−µj−1such that B is not contained in T1 ∪ · · · ∪ Tv at either stage j or stage j + 1of the construction. Such a ball will always exist provided that j is largeenough.Then by the argument from before, E intersects all of the balls of radiusq−µ contained in B, and thus at least (q−µj )−n+ǫ of radius q−µj inside theball B. Evidently E must then intersect at least (q−µj+µ)n · q−µj(−n+ǫ) ≥qµ(n−ǫ) of the balls of radius q−µ, as desired. This completes the proofs of Theorems 1.2.1, 1.2.2, and Simultaneous Avoidance5.4 Simultaneous AvoidanceThe other result applies to a (possibly uncountable) family of functionsf(x1, . . . , xv) that have agreeing, unchanging, nondegenerate linearizationsalong the diagonal. The specific conditions are outlined in the statement ofTheorem 1.2.4.As in the case of the Theorems 1.2.2, and 1.2.3, the construction is aCantor-like set constructed in the same manner as Chapter 3. This lemmaoutlines the strategy for a single step of the construction.Lemma 5.4.1. Let B1, B2 ⊂ B be distinct (and thus disjoint) balls of ra-dius q−λ. Let A ⊂ {1, . . . , v} be an arbitrary nonempty proper subset of{1, . . . , v}. Then we can find B′1 ⊂ B1, B′2 ⊂ B2 of radius at least C1q−λsuch that |α1x1 + · · · + αvxv| ≥ C1r for xj ∈ B′1 if j ∈ A and xj ∈ B′2 ifj /∈ A, where C1 is a constant depending on the vector α, the local field K,and on A.Proof. Since the bounds in this lemma are allowed to depend on α, we willnormalize α so that every component of α is in R and at least one componentof α is invertible in R; that is, the norm of α will be taken to be 1.Assuming this normalization, let C1 = q−1∣∣∣∑j /∈A αj∣∣∣. This was assumedto be strictly positive in the statement of Theorem 1.2.4.Then, selecting B′1 and B′′2 to be any balls of radius C1q−λ containedin B1 and B2, we consider the set α · B, where B = B(1) × · · · × B(v), andB(j) = B′1 if j ∈ A and B(j) = B′′2 otherwise. Since each component of αis in R, we have immediately that α · B is contained in a ball A ⊂ R ofradius at most C1q−λ. If this ball is not the unique C1q−λ-ball containingzero, then we can take B′2 = B′′2 to complete the proof. If not, then selectany element b ∈ R with |b| = q−λ−1 and define B′2 := B′′2 + b ⊂ B2. Thendefining the ball B′ to be B(1)∗ × · · · ×B(v)∗, with B(j)∗ = B′1 if j ∈ A andB(j)∗ = B′2 otherwise, we have that α · B′ maps into A+ b∑j∈AC αj , whichis a ball of radius C1q−λ that does not contain 0. This lemma can be applied iteratively in the following way: Startingwith a ball B of radius q−λ, we can pick two balls B1, B2 ⊂ B of radiusq−λ−1. Then, for some A, apply Lemma 5.4.1 to arrive B′1 and B′2. Now,pick a different A and apply the lemma to these balls to arrive at B′′1 andB′′2 . Repeat this process for all nonempty proper subsets A ⊂ {1, . . . , v},and we arrive at B∗1 ⊂ B1, B∗2 ⊂ B2 where B1 and B2 have radius at leastC∗q−λ for some C∗, and α1x1+ · · ·+αvxv is at least C∗q−λ in absolute value785.4. Simultaneous Avoidancefor all x1, . . . , xv ∈ B∗1 ∪B∗2 not all coming from B∗1 and not all coming fromB∗2 .Proposition 5.4.2. There exists C∗ depending only on α and on the localfield K with the following property. For any ball B with q−λ := radius(B),there exist B∗1 , B∗2 ⊂ B such that B∗1 , B∗2 are balls of radius C∗q−λ and suchthat α1x1 + · · · + αvxv has absolute value at least C∗q−λ for x1, · · · , xv ∈B∗1 ∪B∗2 provided that not all of the x1, · · · , xv are in B∗1 , and not all of thex1, . . . , xv are in B∗2 .We are now ready to prove Theorem 1.2.4.Proof of Theorem . This construction closely follows the one appearing inChapter 3.In order to construct the set E, we begin by selecting a ball E0 of radiusq−λ0 where λ0 is chosen sufficiently large so that Cq−λ0v < (C∗)3, where C∗is the constant from Proposition 5.4.2.We will construct the set E by applying Proposition 5.4.2 inductively.Ej will always be a union of 2j balls of radius (C∗)jq−λ0 with the propertythat |α · (x1, . . . , xv)| ≥ (C∗)jq−λ0 for x1, . . . , xv ∈ Ej unless x1, . . . , xv allbelong to the same ball in Ej . To construct Ej+1, we apply Proposition 5.4.2to each of the balls that constitute Ej. The result will be a collection Ej+1of 2j balls of radius (C∗)j+1q−λ0 with the property that |α · (x1, . . . , xv)| ≥(C∗)j+1q−λ0 unless x1, . . . , xv belong to the same ball in Ej+1. Let E =⋂∞j=0Ej . It follows from a routine computation that the Cantor set E haspositive Hausdorff dimension.It remains to be seen that f(x1, . . . , xv) is nonzero for x1, . . . , xv ∈ Enot identical. To see this, notice that there exists a minimal ball B suchthat x1, . . . , xv ∈ B. Say that this ball B is a basic ball of Ej−1. LetB1 and B2 be the children of this ball in the construction. Then we have|α · (x1, . . . , xv)| ≥ (C∗)jq−λ0 . Since x1, . . . , xv ∈ B1∪B2 ⊂ B, we have that(|x2 − x1|2 + · · · + |xv − x1|2) ≤ v(C∗)2j−2q−2λ0 .Therefore we have that|f(x1, . . . , xv)| ≥ (C∗)jq−λ0 > 0as long asCv(C∗)2j−2q−2λ0 < (C∗)jqλ0by the ultrametric inequality. Noting that Cq−λ0v < (C∗)3, we getCv(C∗)2j−2q−2λ0 ≤ (C∗)2j+1q−λ0 ≤ C∗jq−λ0as desired. 79Chapter 6Besicovitch Sets6.1 The Kakeya ProblemIn the early 20th century, Kakeya asked the following question: Let E bea measurable subset of R2 through which a line segment of unit lengthcan be continuously rotated all the way around, so that the line segmentends up in the same orientation as it began. How small is it possible forthe Lebesgue measure of E to be? This problem is known as the Kakeyaneedle problem, and a set E with this property is called aKakeya needleset. Evidently, a circle with radius 12 is a Kakeya needle set with Lebesguemeasure π4 . Kakeya conjectured that the smallest such set was a 3-pointedhypocycloid.In 1928, Besicovitch showed, remarkably, that such a set can have arbi-trarily small Lebesgue measure. In order to construct such sets, Besicovitchbegan with a triangle, and performed a sequence of translations of the tri-angle in order to minimize the possible area. Then, he connected variousparts of the figure with narrow hallways to arrive at a Kakeya needle set.As a byproduct of this construction, Besicovitch arrived at a method forconstructing a subset of R2 of Lebesgue measure zero that contains a unit-length line segment pointing in every direction. Such a set is now known asa Besicovitch set or Kakeya set.Besicovitch’s construction also implies the existence of measure-zeroBesicovitch sets in dimensions d > 2: Simply taking the Cartesian product ofa 2-dimensional Besicovitch set with the rectangle [0, 1]d−2 gives an example.Although Besicovitch sets can have Lebesgue measure zero, for d > 2 itis unknown whether a Besicovitch set in Rd can have Hausdorff dimensionstrictly less than d. The question of whether such sets exist is known as theKakeya problem. TheKakeya conjecture is the claim that a Besicovitchset in Rd necessarily has Hausdorff dimension d. This was established in thed = 2 case by Roy Davies [10].806.2. The Kakeya Problem for Finite Fields6.2 The Kakeya Problem for Finite FieldsIn order to help tackle the study of Euclidean Kakeya problems, Tom Wolff[54] introduced the finite field version of the Kakeya conjecture. Let Fq bethe finite field with q elements. A Besicovitch Set in Fdq is a subset of Fdqthat contains a line taω + bω with aω parallel to ω for every direction ω inthe projective space PFd−1q . The Finite Field Kakeya Conjecture askswhether a Besicovitch set in Fdq must contain a constant (depending on dbut not q) fraction of the qd elements of Fdq .Theorem 6.2.1 (Finite Field Kakeya Conjecture). Every Besicovitch setin Fdq contains at least Cdqd elements.This conjecture was established by Dvir in 2009 [12]. Dvir used a tech-nique known as the polynomial method to establish this result.Proof taken from [12]. Let K be some Besicovitch set in Fdq . Then there isa polynomial p 6= 0 of degree .d |K|1/d that vanishes on all of K. Let s bethe degree of this polynomial. Let y ∈ Fdq and let x ∈ Fdq be such that Kcontains the line x+ ty. Because p vanishes on K we have that p(x+ ty) = 0on all of K. If we assume that |K| .d (q − 1)d, then we get that the degrees of p is no more than q − 1, and therefore p(x+ ty), as a polynomial in t,is the zero polynomial. The coefficient of the ts term of this polynomial isprecisely ps(y), the homogeneous degree s part of p. Then ps(y) is a nonzeropolynomial that vanishes for all y, which is a contradiction. This short proof showed the power of the polynomial method, and sincethis proof of Dvir emerged in 2009, variants of the polynomial method havebeen applied to solve all kinds of problems in incidence geometry, additivecombinatorics, and harmonic analysis.The result in [12] was improved by Ellenberg, Oberlin, and Tao in [17].In the Euclidean setting, the Kakeya conjecture is implied by an estimateon the Kakeya maximal operator. Ellenberg, Oberlin, and Tao define ananalogue of the Kakeya maximal operator for finite fields:Definition 6.2.2 (Kakeya Maximal Operator). Let PFd−1q d−1-dimensionalprojective space over Fq, and let f be a complex-valued function defined onFdq . Then the Kakeya maximal function Mf is defined by the formulaMf(ω) =1qsupx∑t|f(x+ ty)|816.2. The Kakeya Problem for Finite Fieldswhere the vector y points in the direction ω and t ranges over Fq (the sumdoes not depend on which y is chosen for each ω).Ellenberg, Oberlin and Tao obtain the following Ld-to-Ld estimate forthe Kakeya maximal operator M :Theorem 6.2.3 (Kakeya maximal operator estimate on Fq). The KakeyaMaximal operator M satisfies the bound||Mf ||Ld(ν) ≤ Cd||f ||Ld(µ)where the measure µ is the normalized counting measure on Fdq , and ν is thenormalized counting measure on PFd−1q .In the last section of [17], the authors posed the question of whetherTheorems 6.2.1 and 6.2.3 can be shown for local fields.82Chapter 7Local Field Besicovitch Sets7.1 Background7.1.1 Previous ConstructionsIn 1987, Sawyer [45] constructed a measure-zero Besicovitch set in R2 usinga novel trick. Sawyer observed that, for any Borel measurable function φ,the family of line segments E := {(x, tx − φ(t)) : x ∈ [0, 1]; t ∈ R} formsa Besicovitch set (with the minor caveat that this set does not containa vertical line segment). Of course, it is enough to restrict t to be in [0, 1]because R is a countable union of dilates of the interval [0, 1] and a reflectionabout the point 0, and thus a Besicovitch set can be obtained by stretchingthe line segments vertically and reflecting about the line y = 0. If thefunction φ is chosen appropriately, the set E can be taken to have Lebesguemeasure 0 in R2.Sawyer uses the following strategy to construct an appropriate functionφ. Suppose that φ has the property that, for each a ∈ [0, 1], the range ofthe function ℓa(t) = at − φ(t) : [0, 1] → R has measure zero as a subset ofR. Then we have that|E| =∫∫[0, 1]1E(x, y) dx dy=∫[0,1]|{y : y = tx− φ(t) for some t}| dxWe now observe that the set {y : y = tx − φ(t) for some t} must havemeasure zero for any fixed x: this follows from the choice of φ. Thus theLebesgue measure of E is zero.So it is possible to construct a measure-zero Besicovitch set by construct-ing a function φ with this property. We will define φ as an infinite sum ofpiecewise constant functions φj . Let q1, q2, . . . be a sequence of rational num-bers in [0, 1] that contains each rational number in [0, 1] an infinite numberof times. Define φ1(t) to be a function that is equal to q1 · 01 = 0 everywhere.837.1. BackgroundNext, define φ2(1/2) =q22 , and define φ2(t) byφ2(t) ={q2 · 02 if 0 ≤ t < 12q2 · 12 if 12 ≤ t ≤ 1In particular, notice that φ2(t) is bounded above byq22 ≤ 12 . Note furtherthat the range of q2t− φ2(t) is contained in the interval [0, q22 ].Now we define φ3(t) in the following way:φ3(t) =q3 · 06 if 06 ≤ t < 16q3 · 16 if 16 ≤ t < 26q3 · 26 if 26 ≤ t < 36q3 · 06 if 36 ≤ t < 46q3 · 16 if 46 ≤ t < 56q3 · 26 if 56 ≤ t ≤ 66Now, we have that φ3(t) is bounded above byq33 ≤ 13 , and that, because φ1and φ2 are both constant on the interval [0,12), we have, for t ∈ [02 , 12 )∣∣∣∣∣q3t− (3∑r=1φr(t)) + (φ1(0) + φ2(0))∣∣∣∣∣= |q3t− φ3(t) + (φ2(0)− φ2(t)) + (φ1(0)− φ1(t))|= |q3t− φ3(t)|≤ q3t6We get a similar inequality for t ∈ [12 , 1] where φ1(0) and φ2(0) are replacedby φ1(12 ) and φ2(12).We then continue this strategy. We define φM to be constant on intervalsof the form [ jM ! ,j+1M ! ), and to be equal to qM · j−kM ! on this interval, where kis the largest multiple of M that is less than or equal to j. Thus, 0 ≤ φM ≤1(M−1)! , and φM is constant on intervals of the form [jM ! ,j+1M ! ). Furthermore,since φ1, . . . , φM−1 are constant on intervals of the form [ j(M−1)! ,j+1(M−1)!), wehave that qMx−∑Mr=1 φr(x)+∑M−1r=1 φr(k(M−1)!) is bounded above by1M ! onthe interval [ k(M−1)! ,k+1(M−1)! ). Thus, qMx −∑Mr=1 φr(x) is contained within(M − 1)! intervals of length 1M ! , a set with Lebesgue measure at most 1M .847.1. BackgroundFurthermore, if we let c be a number such that |c − qM | < ǫ, thenthe error in approximating cx + d by qMx for an appropriate d on theinterval [ k(M−1)! ,k+1(M−1)!) is bounded above byǫ(M−1)! . Thus we get thatcx−∑Mj=1 φj(x) is contained in at most (M −1)! intervals of length at mostǫ(M−1)!+1M ! for such numbers c. Using the estimate 0 ≤ φ(x)−∑Mj=1 φj(x) =∑∞j=(M+1) φj(x) ≤∑∞j=(M+1)1(j−1)! ≤ 2M ! , we get that for such c, cx− φ(x)is contained in at most (M − 1)! intervals of length at most 3M ! + ǫ(M−1)! , aset of measure at most 3M + ǫ. By the density of the rational numbers andby the choice of the sequence qj, it follows that φ(x)− cx has measure zerofor any number c ∈ [0, 1].Sawyer extends this observation in the following way: by replacing thelines qx by an appropriate family of C1 functions, it is possible to constructa Borel measurable function φ(t) : [0, 1] → R with the property that, forany differentiable function f(t) : [0, 1]→ R, the range of the function f − φhas measure zero. Furthermore, Sawyer selects the function φ in a way thatguarantees that the function φ is right-continuous and has only countablymany discontinuities. This construction allows for measure zero sets con-taining translates of a one-dimensional families of smooth curves that areparameterized in a smooth way.Sawyer’s construction was improved by Wisewell [52, Lemma 4].Wisewell observed that Sawyer’s method could be adapted to construct aBorel measurable function ψ with the following property.Theorem 7.1.1 (Wisewell’s function). There exists a function ψ : Rp → Rqwith the following property: Let f(y, ω) : Rp×Rq → Rn−d, with p ≤ n−d ≤ qand d < n. If f is C1 and ∂f∂ω always has rank n − d and is Lipschitz, thenthe range of f(·, ψ(·)) is of measure zero.This function ψ is then used in the following way. Let Γ(y, ω) be thesurface consisting of points (t, f(y, ω, t)) for t ∈ Rd, f : Rp×Rq×Rd → Rn−da differentiable function with full rank as a function of y and ω for a.e. t.This is a d-dimensional surface in Rn parameterized by the variable t. Thefamily itself is parameterized by y and ω. Using this function ψ, Wisewellconstructs a set E of measure zero containing the surface Γ(y, ψ(y)) for everyy ∈ Rp. Of special note is that this function ψ does not depend on f .7.1.2 A Besicovitch Set in Fq[[t]]2As a matter of fact, Sawyer’s Besicovitch set construction [45] can be adaptedto all non-archimedean local fields. This was first discovered by Wright in857.1. Backgroundan unpublished work in the 1990s. Nonetheless, in 2010, Ellenberg, Oberlin,and Tao [17] proposed the problem of constructing a measure-zero Besicov-itch set in Fq[[t]]2. Dummit and Hablicsek [11] constructed such a set usinga linear-algebraic method.Let a ∈ Fq[[t]]. Then a has an expansion of the form (4.1). Here,the coefficients are elements of Fq, addition is defined componentwise, andmultiplication is defined as multiplication of power series. Dummit andHablicsek define the ∗ function a 7→ a∗ wherea∗i ={0 if i = 2k − 2 for some natural number kai+1 otherwise.This ∗-function is used to construct a half-Besicovitch set H:H := {(x, y) ∈ Fq[[t]]2 : ax+ y = a∗ for some a ∈ Fq[[t]]}. (7.1)This set of points contains a line of “slope” a for every a ∈ Fq[[t]].Although this does not quite cover all of the possible directions for lines inFq[[t]]2, a Besicovitch set can be constructed by taking the union of this setwith its “transpose” in which the roles of x and y are swapped. Therefore,establishing that H has Haar measure zero yields a measure-zero Besicovitchset construction in Fq[[t]]2.In order to show that H has Haar measure zero, the equation appearingin (7.1) is re-written as an infinite system of linear equations over Fq. Noticethat this step is impossible for other discrete valuation rings such as Zp: inZp addition is not done term-by-term but has a carry as well. This spoilsthe linearity so the construction does not work over such rings.The linear system that characterizes H consists of equations of the formanx0 + an−1x1 + · · · + a0xn + yn = a∗n. (7.2)One key point here is that the n = 0 equation does not involve any com-ponent of a other than a0; the equations for n ≤ 2 do not involve anycomponent of a other than a0, a1, a2; and, in fact, the n ≤ 2k − 2 equationdoes not involve any component of a other than a0, a1, . . . , a2k−1.A point (x, y) belongs to H if and only if the system of equations (7.2)has a solution in a. Dummit and Hablicsek interpret the Haar measure onFq[[t]] as a probability measure and show that, conditioned on the systemof equations for n ≤ 2k − 2 having exactly qℓ solutions, the system of equa-tions with n ≤ 2k+1 − 2 will have 0 solutions with probability q−1qℓ+2, qℓ withprobability 1 − qqℓ+1, and qℓ+1 with probability 1qℓ+2. By a Markov-chain867.2. Adapting to Local Fieldsargument, it follows that the number of solutions to (7.2) for a randomlychosen point (x, y) will, with probability 1, be equal to zero at some finitecutoff point. Therefore H has measure zero.7.2 Adapting to Local Fields7.2.1 Construction of φThe construction of this function φ follows the construction of φ in [45] andψ in [52]. For convenience, the function φ will be taken to be defined on R,the ring of integers of K, instead of all of K; this is sufficient because wecan define extend φ to all of K periodically.We will fix a family of coset representatives of K. Define Sk ⊂ K to bethe set of elements of K whose lowest-degree term is at least − log k andwhose highest-degree term has degree at most k. Notice that the set Sk isfinite, and⋃∞k=0 Sk is dense in K. We define the families Ωk of functionsRp → Sk to be the functions that are locally constant on balls of radius ℓ−k,where ℓ is the number of elements of the residue field of K. Such locallyconstant functions are continuous (in fact they are smooth). Because Rcontains only finitely many open balls of radius ℓ−k and Sk is finite, itfollows that each set Ωk is also finite. It is easily seen that⋃k Ωk is the setof all locally constant functions from Rp to K, which is a dense subspaceof the space of continuous functions on Rp(recalling that Rp is compact, socontinuous functions are bounded).We let rj be a family of all the q × p matrices with elements in Ω0,followed by a list of all the matrices whose entries are contained in Ω1, etcetera. Each matrix consisting of elements of Ωk occurs infinitely manytimes in the sequence rj, because Ωk ⊂ Ωk′ for all k′ > k.An analogue of the factorial expansion, which was key to the construc-tions in [52] and [45], is provided by the sequence of projection functionspj . For nonnegative integers j, define η(j) = j(j + 1)/2. Given x ∈ R withexpansion (4.1), define the projection pj(x) to be the finite sumη(j+1)−1∑i=η(j)xiti.Then we have that |pj(x)| ≤ ℓ−η(j). For vectors x ∈ Rp, we define pj(x) to877.2. Adapting to Local Fieldsbe the componentwise application of pj. We then takeφ(x) :=∞∑k=0rj(x)pj(x),an absolutely convergent sum.Note that each function rj(x)pj(x) is a locally constant Kq-valued func-tion on Rp. Because the sum of the rj(x)pj(x) is absolutely and uniformlyconvergent on Rp, it follows that φ(x) is a continuous function from Rp toKq. In fact, φ is bounded with |φ(x)| ≤ 1 for all x; hence, the range of φ iscontained in Rq.7.2.2 Estimates on the Range of f(x, φ(x))We are now ready to prove Theorem 1.3.1. In order to prove Sawyer’s result[45], points of the form x = 1N ! , and their images under φ, were used aslandmarks for the function φ. We will use the partial sumsx(m) :=m−1∑j=0pj(x) (7.3)andφ(m)(x) =m−1∑j=0rj(x)pj(x) (7.4)as landmarks for the local field setting.We will show that the range of f(x, φ(x)) has measure at most ℓ−A forany fixed A > 0, showing that the range must therefore have measure zero.The function f(x, φ(x)) is decomposed into six pieces I, . . . ,VI with VIbeing the main term- which will only take finitely many values.887.2. Adapting to Local FieldsThe six pieces areI := f(x, φ(x))− f(x(N), φ(x))− ∂f∂x∣∣∣∣(x,φ(x))(x− x(N))II := f(x(N), φ(x)) − f(x(N), φ(N)(x))− ∂f∂y∣∣∣∣(x(N),φ(x))(φ(x) − φ(N)(x))III :=∂f∂y∣∣∣∣(x(N),φ(x))(φ(x) − φ(N)(x))− ∂f∂y∣∣∣∣(x,φ(x))(φ(x)− φ(N)(x)).IV :=∂f∂y∣∣∣∣(x,φ(x))(φ(x)− φ(N+1)(x)) + ∂f∂x∣∣∣∣(x,φ(x))(x− x(N+1))V :=∂f∂y∣∣∣∣(x,φ(x))rN (x)pN (x) +∂f∂x∣∣∣∣(x,φ(x))pN (x)VI := f(x(N), φ(N)(x)).It is not difficult to verify that the sum I + II + III + IV + V + VI adds upto f(x, φ(x)) remembering thatpN (x) + (x− x(N+1)) = x− x(N)andrN (x)pN (x) + (φ(x)− φ(N−1)(x)) = φ(x)− φ(N)(x),which are simple consequences of equations (7.3) and (7.4), respectively.We will briefly summarize the strategy for estimating these terms. Wewill then describe the estimates in detail.There exist natural numbers NI, NII, NIII, and NIV such that I, II, III,and IV are all bounded above by ℓ−η(N)−A. For I and II, such boundsfollow directly from the very strong differentiability of f in the x and yvariables, respectively. III follows from a Ho¨lder condition on ∂f∂y , which isweaker than the very strong differentiability assumed for f . The bound onIV follows from the boundedness of ∂f∂x and∂f∂y , together with the fact thatη(N + 1) = η(N) +N for all N .Lemma 7.2.1. Given A > 0, there exists NI such that for N ≥ NI, term Ihas norm no more than ℓ−α(N)−A.Proof. Pick NI so that we have for every x ∈ Rp, y ∈ Rq and h ∈ Rp suchthat ‖h‖ < ℓ−NI , that∥∥∥∥∥f(x+ h, y)− f(x, y)− ∂f∂x∣∣∣∣(x,y)h∥∥∥∥∥ ≤ ℓ−A ‖h‖ .897.2. Adapting to Local FieldsWe can do this by the strict differentiability assumption on f , and thefact that Rp ×Rq is a compact set. Then if N > NI,∥∥x− x(N)∥∥ is no morethan ℓ−η(N) ≤ ℓ−η(NI) ≤ ℓ−NI , so the above bound applies with h = x(N)−x,and we have that‖I‖ ≤ ℓ−Aℓ−η(N),as desired. Lemma 7.2.2. Given A > 0, there exists NII such that for N ≥ NII, termII has norm no more than ℓ−η(N)−A.Proof. We will select NII to take advantage of the very strong differentia-bility in the y-variable. The choice of NII should be large enough so thatη(N) − log(N) > N for all N ≥ NII. We will also want NII to have theproperty that for any h with ‖h‖ = ℓ−s < ℓ−NII , and any x ∈ Rp, y ∈ Rq,∥∥∥∥∥f(x, y + h)− f(x, y)− ∂f∂y∣∣∣∣(x,y)h∥∥∥∥∥ < ℓ−A−log(s) ‖h‖ .This is possible because of the very strong differentiability- ‖h‖1+α is equalto ℓ−(1+α)s, which is smaller than ℓ−s−log s−A if s is large enough.For any N , we have that∥∥φ(N)(x)− φ(x)∥∥ is no more than ℓ−η(N)+log(N).So if N > NII then, taking h to be φ(N)(x) − φ(x), the error in the linearapproximation will be bounded above byℓ−A−η(N)+log(N)−log(η(N)−log(N)),which is in turn smaller than ℓ−A−η(N) because η(N)− log(N) is larger thanN . This proves the desired bound. Lemma 7.2.3. Given A > 0, there exists an NIII such that for N ≥ NIII,term III has norm no more than ℓ−η(N)−A.Proof. Pick NIII for the Ho¨lder condition on∂f∂y discussed after the definitionof very strong differentiability to guarantee that for the value h = x(N) − x,∥∥∥∥∥ ∂f∂y∣∣∣∣(x,φ(x))− ∂f∂y∣∣∣∣(x+h,φ(x))∥∥∥∥∥ ≤ ℓ−Aℓ− log(s)if ‖h‖ = ℓ−s where s ≥ NIII. Also, we must select NIII sufficiently large thatη(N) − logN > N for all N > NIII.907.2. Adapting to Local FieldsThen, because we have the bound∥∥φ(x)− φ(N)(x)∥∥ ≤ ℓ−η(N)+log(N), weobtain the bound‖III‖ ≤ ℓ−Aℓ− log(η(N)−log(N))ℓ−η(N)+log(N),and by the choice of NIII this is no more than ℓ−η(N)−A. Lemma 7.2.4. There exists an integer NIV such that for N ≥ NIV, termIV has norm no more than ℓ−η(N)−A.Proof. Let B be the integer such thatℓB = maxx∈Rpy∈Rqmax(∥∥∥∥∥ ∂f∂x∣∣∣∣(x,y)∥∥∥∥∥ ,∥∥∥∥∥ ∂f∂y∣∣∣∣(x,y)∥∥∥∥∥ ,∥∥∥∥∥ ∂f∂x∣∣∣∣(x,y)∥∥∥∥∥ ·∥∥∥∥∥ ∂f∂y∣∣∣∣(x,y)∥∥∥∥∥).Pick NIV for which NIV ≥ log(NIV + 1) + A + B. For any N > NIV,it follows that this same inequality holds with N in place of NIV. LetN > NIV. Because η(N + 1) = η(N) +N , it follows from the choice of NIVthat pN+j has norm no more than ℓ−(η(N)+A+B+log(N+j)) for every j > 0,and by assumption rN+j has norm no more than ℓlog(N+j). Performing themultiplication gives‖IV‖ ≤ ℓ−η(N)−A.In contrast, V is only small for certain choices of N . Nonetheless, thereare infinitely many such choices: choosing rN to approximate the matrix− ∂f∂y−1∣∣∣∣(x,φ(x))∂f∂x∣∣∣∣(x,φ(x)),which is possible because of the rank assumption on ∂f∂y , we obtain a sat-isfactory bound of ℓ−η(N)−A for such values of N . Here, ∂f∂y−1is the rightinverse of ∂f∂y .Lemma 7.2.5. There exist arbitrarily large values of N for which the termV has norm no more than ℓ−η(N)−A for almost every value of x.Proof. As in Lemma 7.2.4, define B so thatℓB = maxx∈Rpy∈Rqmax(∥∥∥∥∥ ∂f∂x∣∣∣∣(x,y)∥∥∥∥∥ ,∥∥∥∥∥ ∂f∂y∣∣∣∣(x,y)∥∥∥∥∥ ,∥∥∥∥∥ ∂f∂x∣∣∣∣(x,y)∥∥∥∥∥ ·∥∥∥∥∥ ∂f∂y∣∣∣∣(x,y)∥∥∥∥∥).917.2. Adapting to Local FieldsWe selected rN to be a dense sequence of q-by-p matrices of continuousfunctions from Rp into K. Note that ∂f∂y has a right inverse for almost everyx by the assumption that ∂f∂y has full rank and the assumption that q ≥ n−d.Therefore, we can pick arbitrarily large N for which∥∥∥∥∥rN (x) + ∂f∂y −1∣∣∣∣(x,φ(x))∂f∂x∣∣∣∣(x,φ(x))∥∥∥∥∥is almost everywhere smaller than ℓ−A−B as a function of x. V can bewritten asV =(∂f∂y∣∣∣∣(x,φ(x))rN (x) +∂f∂x∣∣∣∣(x,φ(x)))pN (x).The norm of pN (x) is no larger than ℓ−η(N) by the definition of pN , and thechoice of N guarantees that the term multiplying pN (x) has norm no largerthan ℓ−A. Therefore, we can pick an N larger than max(NI, NII, NIII, NIV) thatsatisfies the condition in Lemma 7.2.5. For this value of N , the norm ofI+II+III+IV+V is, by the ultrametric inequality, no more than the largestof the norms of I, II, III, IV, and V, which is bounded almost everywhere byℓ−A−η(N). Therefore, for almost every x, the value f(x, φ(x)) is containedin balls of radius ℓ−A−η(N) centered at each point f(x(N), φ(N)(x)). But thevalues of x(N) and φ(N)(x) depend only on the coefficients x0, . . . , xη(N)−1.This means that f(x(N), φ(N)(x)) can only take on at most ℓη(N)p values. Sof(x, φ(x)) is contained in at most ℓη(N)p balls of radius at most ℓ−η(N)−A inKn−d for almost every x. Each such ball has measure ℓ(−η(N)−A)(n−d), so thetotal measure of the union of the balls is no more than ℓ(−η(N)−A)(n−d)ℓη(N)p.If n − d ≥ p, then this is no more than ℓ(−A(n−d)). Since A was arbitrary,this is sufficient to show that the range of f(x, φ(x)) has measure zero.7.2.3 Kakeya-Like SetsWe can use the function φ from Theorem 1.3.1 to construct Kakeya-like setsof the type described in Theorem 1.3.2. Specifically, suppose that f(x, y, w)is a measurable function such that for almost every w, the Jacobian ∂f∂y hasfull rank almost everywhere. We will think of f as a family of surfaces, wherex and y index the family of surfaces, and each surface is parameterized by thew variable. We want to include one surface {(w, z) : z = f(x, y, w);w ∈ Kd}for each x ∈ Kp.927.2. Adapting to Local FieldsWe claim that the setT := {(w, z) : z = f(x, φ(x), w);x ∈ Kp, w ∈ Kd}has measure zero. We know from Theorem 1.3.1 that, for almost every w,the “cross-section” {f(x, φ(x), w) : w ∈ Kn} has measure zero. By Fubini’stheorem, this implies that if T is measurable, then it must have measure zero.Therefore, the only thing that remains to be seen is that T is measurable.Note that it is enough to show that the setT ′ := {(w, z) : z = f(x, φ(x), w);x ∈ Rp, w ∈ Kd}is measurable, because T can be expressed as the countable union⋃a{(w, z) : z = f(x+ a, φ(x+ a), w);x ∈ Rp, w ∈ Kd}where a ranges over the elements of Kp such that all the terms have negativedegree. Writing T this way is useful because Rp is a compact set.We will now write T ′ in a way that makes its Borel measurability clear.The next thing we use is that T ′ can be thought of as the set of (w, z) forwhich there exists a sequence xn in Rp with ‖f(xn, φ(xn), w) − z‖ < 1n . Thisis sufficient to be in T ′ because the compactness of Rp guarantees that asubsequence of the xn will have a limit x, and the continuity of the functionsf and φ guarantees that ‖f(x, φ(x), w) − z‖ will equal zero. Furthermore,we can also impose the condition that the sequence elements xn lie in acountable dense subset R˜p of Rp. Therefore, T ′ can be realized as the set⋂n∈Z⋃x∈R˜p{(w, z) : ||f(x, φ(x), w) − z|| < 1n}.This set is measurable because f(x, φ(x), ·) is measurable for every x. There-fore, the set T ′ is measurable, and T is measurable and has measure zero.7.2.4 ExamplesThe motivating example for this problem is that of Besicovitch sets:Example 7.2.6 (Measure-Zero Besicovitch Sets in Non-Archimedean LocalFields). The vector space K2 has a Besicovitch set of Haar measure zero forany non-archimedean local field K.937.2. Adapting to Local FieldsProof. We apply Theorem 1.3.2 to the function f(x, y, w) = xw − y. Thevariables x and y parameterize the space of lines in K2, with w as theindependent variable in the equation for the line. Here, p = 1 and q = 1:x is Kp-valued and y is Kq-valued. So Theorem 1.3.2 says that the set Tdefined byT := {(w, z) : z = f(x, φ(x), w);x ∈ Kp, w ∈ Kd}has measure zero. This set will contain the line consisting of points of theform (w, xw − φ(x)) for each x. This guarantees that w contains a line ofevery non-vertical slope. Of course, Example 7.2.6 implies the existence of Besicovitch sets ofmeasure zero for any Kn, n ≥ 2, by taking the Cartesian product T ×Kn−2.Notice that the dimensionality constraints on Theorem 1.3.2 mean thatTheorem 1.3.2 (and, in the Euclidean case, Theorem 7.1.1) cannot be usedto locate (n, k) Besicovitch sets of measure zero- that is, sets of measure zerocontaining a k-flat pointing in every possible direction- because the (n, k)-dimensional Grassmannian has dimension p = k(n − k) but the family oftranslations that do not fix a given plane has dimension only q = n − k,which is strictly less than p unless k = 1 In fact, for n ≥ 4, 2 ≤ k ≤ n/2 wehave k(n−k) ≥ n, so there is no hope of ever achieving the bound p ≤ n−drequired for the application of theorem 1.3.2, even if we’re allowed to applysome non-translation transformations such as folding the k-planes somehow.Another example given in [20] concerns paraboloids.Example 7.2.7. [Set of Haar measure zero containing a 1-dimensional fam-ily of Paraboloids] Consider the family of paraboloids P (a, b) in Kn givenbywn = a(w1 − b)2 + · · ·+ a(wn−1 − b)2.Each such paraboloid is d = n− 1 dimensional, and parameterized byw1, . . . , wn−1. Defining A and B byA :=⋃aP (a, φ(a))B :=⋃bP (φ(b), b)we have that both A and B have measure zero.A final example concerns the Veronese map. This example, as presentedin [20], is erroneous: the first d components should be w1, . . . , wd instead ofa1w1 + b1, . . . , adwd + bd.947.2. Adapting to Local FieldsExample 7.2.8. [Family of Veronese-like Curves of Measure Zero] Considerthe surfaces fa,b of the formfa,b(w1, . . . , wd) :=w1w2...wdad+1w21 + bd+1...a(d+ss )wsd + b(d+ss )These are d-dimensional surfaces, as they are parameterized by d variablesw1, . . . , wd. These surfaces are contained in Kn, where n =(d+ss). Wedefine sets A and B:A :=⋃a{fa,φ(a)(w) : w ∈ Kd},B :=⋃b{fφ(b),b(w) : w ∈ Kd}and these sets have measure zero. Here, p = n− d = q = (d+ss )− d.7.2.5 A Kakeya Needle SetIn R2, a set E is called a Kakeya Needle Set if a line segment of length1 can be continuously rotated through the set and return to its originallocation in reverse orientation. Such Kakeya needle sets necessarily havepositive measure as they must contain a circle sector of radius at least 1− ǫthrough a circle arc of angle at least δ for some ǫ, δ > 0. However, Besicovitch[3] observed that such sets can have arbitrarily small Lebesgue measure.Over non-archimedean local fields K, Caruso [7] defines a Kakeya nee-dle set as a set E such that, for every direction in Kn, E contains a linexw + φ(x) where φ(x) is a continuous function of x. This agrees with theusual definition of Kakeya needle sets in R2. Under this definition, the setconstructed in Example 7.2.6 is a Kakeya-needle set of Haar measure zero.Caruso shows that, under an appropriate probability measure on Lipschitzcontinuous functions φ with Lipschitz constant 1, the set of points{(w, xw + φ(x)) : w ∈ K}will have Haar measure zero a.s., providing an abundance of measure-zeroKakeya needle sets.95Chapter 8Background on Salem Sets8.1 Fourier DimensionBefore defining the notion of Fourier dimension, We consider an explicitexample from [55]. Let σn be the surface area measure on Sn−1. Seeing ashow the sphere Sn−1 is a hypersurface of dimension n−1 and the measure σnis spread out over Sn−1, we expect from Corollary 2.3.6 that |σ̂(ξ)| should, onaverage, be on the order of |ξ|−n−12 , possibly with an ǫ-loss in the exponent.In fact, we have the formula from [55, Corollary 6.7]Example 8.1.1 (Asymptotic formula for Fourier transform of σn). Thesurface measure of σn has the asymptotic formulaσ̂n(ξ) = 2|ξ|−(n−1)/2 cos(2π(|ξ| − n− 18)) +O(|x|−(n+1)/2)For this example, we have a pointwise estimate of the form |σ̂(ξ)| .|ξ|−(n−1)/2. It turns out that this is a feature of the curvature of the setSn−1. We will now consider the hyperplane Hn := {x : xn = 0}, andshow that this kind of pointwise Fourier decay cannot occur for any Borelprobability measure µ supported on the hyperplane Hn:Example 8.1.2 (Lack of Fourier decay for Borel probability measures sup-ported on Hn). Let µ be any measure supported on Hn. Then µ̂(ξ) does notdepend on ξn, so there exists a constant C > 0 and ξ arbitrarily far awayfrom zero such that |µ̂(ξ)| ≥ C.In fact, for any hyperplane a · x = b, there will be no Fourier decayin lines pointing in the direction a. We define a notion of dimension thatdepends on the pointwise Fourier decay of measures supported on E [36,Definition 3.12].Definition 8.1.3 (Definition of Fourier Dimension). Let E ⊂ Ω ⊂ Rn bea Borel set, and let Ω be compact. Then the Fourier dimension of E is thesupremum value of t such that E supports a measure µt satisfying|µ̂t(ξ)| .t,µ |ξ|−t/2.968.1. Fourier DimensionIt follows from Definition 8.1.3 and Corollary 2.3.6 that the Fourier di-mension of a Borel set E is no more than the Hausdorff dimension of E.In the case of Sn−1, the Fourier dimension is n − 1, and in the case of thehyperplane Hn, the Fourier dimension is zero.This is a general principle: flat sets and self-similar fractals will tendto have Fourier dimension zero; curved sets and random fractals will tendto have positive Fourier dimension. A set whose Fourier dimension andHausdorff dimension are equal is called a Salem set (definition taken from[36], Definition 3.11 and the discussion below Definition 3.12).Example 8.1.4. The middle-thirds Cantor set has Fourier dimension 0.The computation of the Fourier dimension of this set is difficult and istherefore omitted.Unlike for Hausdorff dimension, the Fourier dimension is not countablystable. This was shown by Ekstro¨m, Persson, and Schmeling [15]. However,a countable set will necessarily have Fourier dimension 0 because the Fourierdimension is bounded above by the Hausdorff dimension.The first examples of Salem sets with non-integer dimension were exhib-ited by Raphae¨l Salem [44]. Salem used a random construction that involvesa Cantor-like construction with random interval lengths at each stage. Thisconstruction gives a set that almost surely has Fourier dimension 1. Manyother random Cantor set constructions in the same spirit exist.An explicit example of a Salem set has been provided by Kaufman [27],and an exposition of Kaufman’s example was provided by Bluhm [5]. Con-sider the set of real numbersE(τ) := {x ∈ [0, 1] : |qx− r| ≤ max(q, r)τfor infinitely many pairs of integers q, r}.This set is called the set of τ-approximable numbers. For τ ≤ 1, E(τ)is the interval [0, 1], as is implied by the Dirichlet principle, but for τ > 1,E(τ) is a proper subset of [0, 1] with Hausdorff dimension 21+τ . Kaufmanestablished that the Fourier dimension of E(τ) is also 21+τ by constructing ameasure on E(τ) that has the appropriate pointwise Fourier decay. ExplicitSalem sets of arbitrary dimension in R2 have been constructed by Hambrook[23] using a complex version of Kaufman’s construction, but there are noknown explicit Salem set constructions in higher dimensions.978.2. Fourier Analysis on Non-Archimedean Local Fields8.2 Fourier Analysis on Non-Archimedean LocalFieldsLet K be a non-archimedean local field with ring of integers R. There is anon-unique continuous, unitary character χ on K that is equal to 1 on allof R, but not equal to 1 on all of the fractional ideal t−1R. We will fix sucha χ. Every continuous, unitary character of K is of the form χ(xs) for somes ∈ K. Given a complex-valued L1 function f on K, we define the Fouriertransform of f at s to bef̂(s) =∫x∈Kf(x)χ(xs) dx.This defines f̂(s) as a function on χ(xs).In order to establish the basic properties of the Fourier transform, weneed a basic theorem on the orthogonality of characters. This is somewhatmore powerful than the orthogonality of characters for Euclidean functions.Lemma 8.2.1 (Orthogonality of Characters on Balls). Suppose |s1 − s2| >q−j . Then we have that ∫B(x,qj)χ(xs1)χ(xs2) = 0for any ball B(x, qj) ⊂ K.Proof. Let x ∈ K, and let s1, s2 ∈ K such that |s1 − s2| > q−j. We want tocalculate ∫B(x,qj)χ(s1y)χ(s2y) dyWe quickly make a change of variables to re-center the integral at the origin:χ((s1 − s2)x)∫B(0,qj)χ(s1y)χ(s2y) dyAnd we perform another change of variables to focus on the ball of radius1:qjχ((s1 − s2)x)∫B(0,1)χ(s1q−jy)χ(s2q−jy) dyThe last line requires a small bit of explanation. Unlike the Euclideancase, we have a minus sign appearing in this exponent in the integral. Thisis because B(0, qj) is precisely the set of points of the form q−jx where988.2. Fourier Analysis on Non-Archimedean Local Fieldsx ∈ B(0, 1), unlike the Euclidean setting. Notice that since |s1 − s2| > q−j,it follows that |(s1−s2)q−j| > 1. Therefore, it is enough to show the theoremfor |s1 − s2| > 1 and for the ball B(0, 1).So consider the integral∫B(0,1)χ(s1x)χ(s2x) =∫B(0,1)χ((s1 − s2)x)where s1 and s2 differ by more than 1 in absolute value. Letting s = s1−s2,we have ∫B(0,1)χ(sx)where s > 1. But the character χ(sx) is nonconstant on the locally compactabelian group R = B(0, 1) for |s| > 1 by assumption, and a nonconstantcharacter on a locally compact abelian group always integrates to 0. We will briefly focus on the case of K = Qp.We can define the Fourier series of a function f supported on Zp in asimilar way. We define the p-adic integer part [x]p of a p-adic number x withexpansion as in (4.3) by[x]p =∞∑j=0xjpjand we define the p-adic fractional part by{x}p =−1∑j=−Mxjpj.Then |[x]p|p ≤ 1. Using this notation, we can extend a function f : Zp → Cto all of Qp byf(x) = f([x]p).A function of this form will be called a Zp-periodic function.Using this definition, we define the Fourier series of f(x) for L1 functionsf : Zp → C byf̂(s) =∫x∈Zpf(x)χ(sx) dxHere s ranges over those values in Qp such that [s]p = 0 (modifying theinteger part of s would not change the value of the character). As an additivegroup, this has the same structure as the quotient Qp/Zp, known as thePru¨fer group.998.2. Fourier Analysis on Non-Archimedean Local FieldsIn fact, for any non-archimedean local field K, the group of characterson the ring of integers R of K will be isomorphic to the additive group K/R,and the reasoning is similar to the case for Qp.A central fact when dealing with local fields is the uncertainty principle[49].Theorem 8.2.2 (Uncertainty principle). Let f(x) ∈ L1 be a complex-valuedfunction on a local field. Then1. If f(x) is supported on a ball of radius qj, then |f̂(s)| is constant onballs of radius q−j.2. If f(x) is supported on a ball of radius qj centered at the origin, thenf̂(s) is constant on balls of radius q−j.3. If f(x) is constant on balls of radius qj , then f̂(s) is supported on aball of radius q−j centered at the origin.Proof. Let s ∈ K. For part 1 of this theorem, we assume that f(x) issupported on B(y, q−j) and computef̂(s) =∫Kf(x)χ(sx) dx=∫B(y,qj)f(x)χ(sx) dx= χ(sy)∫B(0,qj)f(x+ y)χ(sx) dxWe similarly get, for |s′| < q−j :f̂(s+ s′) = χ((s+ s′)y)∫B(0,qj)f(x+ y)χ((s + s′)x) dxNow by the assumptions on s′, we have that s′x has absolute value at most1; i.e., s′x ∈ R. This means that χ(s′x) = 1, so we getf̂(s+ s′) = χ((s+ s′)y)∫B(0,qj)f(x+ y)χ(sx) dxwhich is equal to χ(s′y)f̂(s). This is immediately seen to have absolutevalue |f̂(s)|, and, if y = 0, is exactly equal to f̂(s). This establishes parts 1and 2 of the theorem.1008.3. The Fourier Transform on Spaces Other than L1For part 3, assume f(x) is constant on balls of radius qj .f̂(s) =∫Kf(x)χ(sx) dx=∑xf(x)∫B(x,qj)χ(sx) dxHere the sum in contains one element of every ball of radius qj inK (of whichthere are only countably many). Since f(x) is in L1 the sum is absolutelyconvergent and therefore well-defined. By Lemma 8.2.1, the integral of χ(sx)will vanish whenever s has absolute value greater than qj , because in thisinstance the character χ is non-constant on the ball B(x, qj). Therefore, wehave that f̂(s) = 0 if |s| > qj. This uncertainty principle is an exact, explicit theorem that relates tothe Euclidean uncertainty principle, quoted here [55, Chapter 5]:The uncertainty principle is the heuristic statement that if ameasure µ is supported on [a rectangle] Q, then for many pur-poses µ̂ may be regarded as being constant on any dual ellipsoidQ∗.8.3 The Fourier Transform on Spaces Other thanL1As is the case for the Euclidean setting, we have the Plancherel theorem[49].Theorem 8.3.1 (Plancherel’s Theorem). Let K be a non-archimedean localfield, and Let f ∈ L1 ∩ L2(K). Then ||f̂ ||L2(K) = ‖f‖L2(K) and thus theFourier transform can be extended to an isometry on all of L2(K). Byapplying the Riesz-Thorin interpolation theorem, we see that the Fouriertransform is bounded from Lp(K) to Lp′(K) for all 1 ≤ p ≤ 2 with operatornorm 1.Furthermore, we can extend the Fourier transform to a space of tempereddistributions. We now define the Schwartz-Bruhat space S, which is ananalogue of the Schwartz space of functions in the Euclidean domain.Definition 8.3.2. A function f(x) on K is said to be in the Schwartz-Bruhat space if there exists j such that:1018.4. The Case K = Qp• f(x) is supported on a ball of radius qj• f(x) is constant on balls of radius q−j .By the Theorem 8.2.2, the Schwartz-Bruhat space maps to itself underthe Fourier transform, and by the Fourier inversion theorem, the map is abijection.The dual of the Schwartz-Bruhat space is the space of distributions onK. Given a distribution f , we define the Fourier transform of f to be thedistribution f̂ that satisfies the equation:〈f̂ , φ〉=〈f, φ̂〉In particular, this definition is consistent with the usual definition of theFourier transform of a measure:µ̂(s) =∫Kχ(sx) dµ(x).Notice that, unlike the Euclidean setting, the indicator function 1B(0,1)for the ball B(0, 1) is smooth, because the set of points where 1B(0,1) isequal to 1 is separated from the set of points where 1B(0,1) is equal to 0 bya distance of 1. So the indicator function 1B(0,1) is in S, and in fact satisfiesthe identity1̂B(0,1) = 1B(0,1)This identity is of great value: unlike the Euclidean case, non-archimedeanlocal fields admit compactly supported functions with compactly supportedFourier transforms. This often obviates the need for mollifiers, therebygreatly simplifying many of the standard arguments that are used in theEuclidean case, and making non-archimedean local fields a simplified modelfor the Euclidean setting.8.4 The Case K = QpIn the special case K = Qp, we have another way of defining the Fouriertransform. If x ∈ Qp, x has an expansion of the form (4.3):x =∞∑j=Mxjpj .If x is nonzero, we can assume that xM 6= 0. The index M is nonnegative ifand only if x ∈ Zp.1028.4. The Case K = QpWe will define the p-adic integer part [x]p and the p-adic fractionalpart {x}p of x ∈ Qp as follows: if x ∈ Zp, then [x]p = x and {x}p = 0. Forx ∈ Qp \ Zp we define[x]p =∞∑j=0xjpj (8.1)and{x}p =−1∑j=Mxjpj (8.2)We now consider the function e2πi{x}p =: e({x}p). We define this by re-interpreting the sum (8.2) as a rational number in [0, 1]. The p-adic frac-tional part is a locally constant (and hence continuous) function on Qp thatsatisfies {x+y}p = {x}p+{y}p. This implies that e({x}p) is a unitary char-acter on Qp. Thus we can select χ(x) to be this character. Every characteron Qp is of the form e({xs}p) for some s ∈ Qp. Furthermore, every characteron Qnp is of the form e({x · s}p) for some s ∈ Qnp .If f is an L1 complex-valued function on Qnp , the Fourier transform of fis the complex-valued function defined on Qnp byf̂(s) =∫Qpf(x)e(x · s) dx.This definition can be extended to distributions in the usual way. Thisdefinition specializes to Borel measures µ in the following way:µ̂(s) =∫Qpe(x · s) dµ(x)The character e({x}p) is constant on Zp. In fact, for x ∈ Zp, the function{xs}p is equal to {xs′}p whenever {s}p = {s′}p. So the character associatedto s is the same as the character associated to s′ whenever s−s′ ∈ Zp. Thusthe character group on Zp is isomorphic to the Pru¨fer group Qp/Zp. TheFourier series of a function f : Zp → C is the function defined on Qp/Zpdefined byf̂(s) =∫Zpf(x)e({xs}p) dx.We present some calculations of some Fourier transforms that will be usefulin Chapter 9.1038.5. Hausdorff and Minkowski DimensionLemma 8.4.1. [Lemma 2.2.1 from [21]] For every k ∈ Z, a ∈ Qdp, ands ∈ Qdp, we have∫B(a,p−k)e({s · x}p) dx ={p−dke({s · a}p) if |s|p ≤ pk0 if |s|p > pkProof. By a change of variable,∫B(a,p−k)e({s · x}p)dx = p−dke({s · a}p)∫B(0,1)e({pks · x}p)dx,so it will suffice to prove the result when a = 0 and k = 0.As the d > 1 case follows from the d = 1 case, we will also assume d = 1.If |s|p ≤ 1, then {sx}p = 0 for all x ∈ B(0, 1), and so∫B(0,1) e({sx}p)dx = 1.Now suppose |s|p > 1. By first making a change of variable and thenusing that B(−1, 1) = B(0, 1), we get∫B(0,1)e({sx}p)dx = e({s}p)∫B(−1,1)e({sx}p)dx= e({s}p)∫B(0,1)e({sx}p)dx.Therefore, since e({s}p) 6= 1, we must have∫B(0,1) e({sx}p)dx = 0. The Fourier transform on Qdp has the following property.Lemma 8.4.2. Let µ be a Borel measure on Qdp with support contained inZdp, and let φ be a positive, non-increasing function defined on (0,∞). If|µ̂(s)| ≤ φ(|s|p) for all s ∈ Qp with [s]p = 0, then |µ̂(s)| ≤ φ(|s|p) for alls ∈ Qdp with |s|p ≥ 1.Proof. If µ is an absolutely continuous measure supported on Zdp, it imme-diately follows that µ̂ is constant on balls of radius 1, which immediatelyshows the result. For more general Borel measures µ the result follows froman approximation argument. 8.5 Hausdorff and Minkowski DimensionThe definitions of the Hausdorff dimension and Minkowski dimension of aBorel set E carry over with no modification to any metric space. However,we would like to discuss some of the analogues of the Euclidean theory of the1048.5. Hausdorff and Minkowski Dimensionbehaviour of the Fourier transform on singular measures. These analoguesappear in the Ph.D. thesis of Papadimitropoulos [38].For example, we have the following theorem. The energy integral isdefined in the same way as in the Euclidean setting:Theorem 8.5.1 (Energy Integral Formulation of Frostman’s Lemma forLocal Fields, taken directly from Proposition 4.3.3 in [38]). If E ⊂ Ω ⊂ Knis a Borel set, where Ω is compact, then the Hausdorff dimension of E isthe supremum value of t such that there exists a measure µt supported on Esuch that It(µ) <∞.There is a Fourier-analytic expression for the energy integral Is(µ) [38,Lemma 4.3.4, part (ii)]:Theorem 8.5.2 (Fourier-analytic expression for energy integrals). Let Kbe a non-archimedean local field with residue field Fq. Let E ⊂ K be acompact set and µ be a Borel probability measure supported on E. Then for0 < t < 1, t-energy It(µ) is given by the formulaIt(µ) =1− qt1− qt−1∫Kµ̂(ξ)2|ξ|1−t dx.As is the case for singular measures in Euclidean space, this implies thatthe Hausdorff dimension of a bounded Borel set E is characterized by theL2-averaged Fourier decay of Borel probability measures supported on E.We then define the Fourier dimension of such sets E in the following way[38, Discussion before Definition 4.3.5]:Definition 8.5.3 (Definition of Fourier dimension). Let E ⊂ Ω ⊂ Kn bea Borel set, and let Ω be compact. Then the Fourier dimension of E is thesupremum value of t such that E supports a measure µt satisfying|µ̂t(ξ)| .t,µ |ξ|−t/2.We way that E is a Salem Set if its Hausdorff dimension is equal to itsFourier dimension[38, Definition 4.3.5].105Chapter 9An Explicit Salem Set9.1 IntroductionWe begin by discussing some properties of the sets W (τ) and W (m,n, τ)mentioned in Theorems 1.4.1 and 1.4.2. Recall the definition of this setW (τ) = {x ∈ Zp : |xq−r|p ≤ max(|q|, |r|)−τ for infinitely many (q, r) ∈ Z2}.In Kaufman’s example E(τ) replacing max(|q|, |r|) by q does not change theset E(τ). For the set W (τ) the bound max(|q|, |r|)−τ is of utmost impor-tance; replacing this by |q|−τ would give all of Zp by the p-adic Dirichletprinciple.For τ ≤ 2, we also have that W (τ) = Zp. This also follows from theDirichlet principle. For τ > 2, Melnicˇuk proved that W (τ) has Hausdorffdimension 2/τ [37]. Together with Theorem 1.4.1, this shows that W (τ) isa Salem set.For m,n ∈ N, we identify the m×n matrix with ij-th entry xij with thepointx = (x11, . . . , x1n, . . . , xm1, . . . , xmn).We will first consider the Euclidean set of well-approximable vectorsE(m,n, τ) defined byE(m,n, τ) = {x ∈ [−1, 1]mn : ‖xq − r‖p ≤ max(|q|, |r|)−τfor infinitely many (q, r) ∈ Zn × Zm}It follows from Minkowski’s theorem on linear forms that E(m,n, τ) = Rmnwhenever τ ≤ n/m. Bovey and Dodson showed that the Hausdorff dimen-sion of E(m,n, τ) is equal to m(n − 1) + (m+n)1+τ whenever τ > n/m. Then = 1 case was done earlier by Jarn´ık [25] and Eggleston [14].Hambrook [24] generalized Kaufman’s argument in order to obtain alower bound on Fourier dimension of the sets E(m,n, τ). Hambrook con-structs a measure on E(m,n, τ) with sufficient Fourier decay to guaranteethat E(m,n, τ) has Fourier dimension at least 2n/(1+ τ). Theorem 1.4.2 isa p-adic version of this result.1069.2. A Salem Set in ZpRecall that we define W (m,n, τ) byW (m,n, τ) = {x ∈ Zmnp : ‖xq − r‖p ≤ max(|q|, |r|)−τfor infinitely many (q, r) ∈ Zn×m}Unlike the case for W (m,n, τ), it is only necessary to use the Dirichletpigeonhole principle in order to show that W (m,n, τ) = Zmnp for τ ≤ (m+n)/m. Abercrombie [1] showed that W (m,n, τ) has Hausdorff dimensionm(n− 1) + (m+ n)/τ whenever τ > (m+ n)/n.9.2 A Salem Set in Zp9.2.1 SetupLet τ > 2. For each M ∈ N, defineQM ={q ∈ Z : 12pM ≤ q < pM , |q|p = 1, q prime},RM = {r ∈ Z : 0 ≤ r < pM}.We will assume that M ≥ 2 in order to guarantee that QM is nonempty.For q ∈ QM and r ∈ RM , define the function φq,r on Zp byφq,r(x) = p⌈τM⌉1B(0,1)(p−⌈τM⌉(xq − r)) ∀x ∈ Zp.The function φq,r is a weighted indicator function for the ball of radiusp−⌈τM⌉ centered at rq . For each M ∈ N, we will define the function FM onZp byFM (x) = |QM |−1|RM |−1∑q∈QM∑r∈RMφq,r(x) ∀x ∈ Zp.For any M , FM has integral 1.We will choose a rapidly increasing sequence of positive integers (Mk)∞k=0such that for all k ∈ N,⌈τMk−1⌉ < Mk,p⌈τMk−1⌉ < log(pMk),k−1∏i=1p⌈τMi⌉|QMi ||RMi |< log(pMk).We will then define the measure µk on Zp bydµk(x) = FM1(x) · · ·FMk(x) dx.1079.2. A Salem Set in ZpFor convenience, we take dµ0 = dµ−1 = dx We will need the followinglemmas in order to construct the desired measure µ.Lemma 9.2.1 (Lemma 3.2.2 from [21]). For all M ∈ N and s ∈ Qp/Zp,F̂M (s) = 1 if s = 0 (9.1)F̂M (s) = 0 if 0 < |s|p ≤ pM (9.2)|F̂M (s)| . |s|−1/τ log2(|s|p) if pM < |s|p ≤ p⌈τM⌉ (9.3)F̂M (s) = 0 if |s|p > p⌈τM⌉ (9.4)Lemma 9.2.2 (Lemma 3.2.3 from [21]). For all integers k ≥ 0 and alls ∈ Qp/Zp,µ̂k(s) = 1 if s = 0 (9.5)µ̂k(s) = µ̂k−1(s) if 0 < |s|p ≤ pMk (9.6)|µ̂k(s)| . |s|−1/τ log2(|s|p) if pMk < |s|p ≤ p⌈τMk⌉ (9.7)µ̂k(s) = 0 if |s|p > p⌈τMk⌉ (9.8)The equation (9.5) implies that each µk is a probability measure. ByProhorov’s theorem, which can be found in [26, vol. 2, p. 202], the sequenceof (µk)∞k=1 has a subsequence that converges weakly to a probability measureµ. Though µ is a measure on Zp, it extends to a measure on Zp by definingµ(A) = µ(A∩ Zp) for A ⊂ Qp. We have that supp(µ) is contained in W (τ):of course supp(µ) ⊂ supp(FMk). But every point x in supp(FMk) is withinp−⌈τMk⌉ of a rational number rq where (q, r) ∈ QMk ×RMk . But the growthrate of the Mk guarantees that the sets QMk are disjoint for different valuesof k.Furthermore, by the conditions in Lemma 9.2.2,|µ̂(s)| ≤ supk∈N|µ̂k(s)| . |s|−1/τp log3(|s|p) ∀s ∈ Qp/Zp, s 6= 0.The strategy of the proof is the following: we will first prove Lemma9.2.1 using an exponential sum estimate. Then, we will use Lemma 9.2.1together with a convolution estimate to prove Lemma Estimates on F̂MProof. This is the part of the proof that differs the most from the Euclideanresult in [27]. Let M ∈ N and let s ∈ Qp/Zp. For |s|p > p⌈τM⌉, we have(9.4) as a direct consequence of the formula (Lemma 8.4.1) for the Fourier1089.2. A Salem Set in Zptransform of φq,r. For |s|p ≤ p⌈τM⌉, we use the formula for the Fouriertransform of φq,r to conclude thatF̂M (s) = |QM |−1|RM |−1∑q∈QM∑0≤r<pMe({rs/q}p). (9.9)If we set s = 0, then each exponential term e({rs/q}p) is equal to 1. ThusF̂M (0) = 1. This establishes (9.1). Now we need only compute F̂M (s) for0 < |s|p ≤ p⌈τM⌉. Therefore, |s|p = pℓ for some ℓ ∈ {1, . . . , ⌈τM⌉}. We willconsider the inside sum in r occurring in equation (9.9). Fix q ∈ QM . Since|q|p = 1 (by the choice of QM ) we have that |s/q|p = |s|p = pℓ. Thus thep-adic expansion s/q has the formsq=∞∑i=−ℓcipi, ci ∈ {0, 1, . . . , p− 1}, c−ℓ 6= 0. (9.10)Viewing {s/q}p as an element of Q, we have that 0 < {s/q}p < 1, and soe({s/q}) 6= 1. Thus we can apply the geometric series formula to conclude∑0≤r<pMe({rs/q}p) = 1− e({spM/q}p)1− e({s/q}p) . (9.11)If |s|p ≤ pM , then |pMs| ≤ 1 and we have {spM/q}p = 0. In this case itfollows that e({spM/q}p) = 1 and the sum in (9.11) is zero. This establishes(9.2).Therefore only (9.3) needs to be shown. We will thus assume that pM <|s|p = pℓ ≤ p⌈τM⌉. For all z ∈ R, |1 − e(z)| = 2| sin(πz)| = 2 sin(π ‖z‖) ≥π ‖z‖, where ‖z‖ := mink∈Z |z−k| denotes the distance from z to the nearestinteger. Thus the sum in (9.11) satisfies∣∣∣∣∣∣∑0≤r<pMe({rs/q}p)∣∣∣∣∣∣ ≤ min{1‖{s/q}p‖ , pM}. (9.12)We write sq as in (9.10), and conclude‖{s/q}p‖ ={{s/q}p =∑−1i=−ℓ cipi if {s/q}p ≤ 121− {s/q}p = 1−∑−1i=−ℓ cipi if {s/q}p > 12 .Therefore, we get the estimate|F̂M (s)| ≤ |QM |−1|RM |−1ℓ∑k=1∑12≤q<pM|q|p=1, q primep−k≤‖{s/q}p‖<p−k+1min{pk, pM} (9.13)1099.2. A Salem Set in ZpIn order to estimate this sum, we need to better understand the distributionof the fractional part {s/q}p modulo pℓ. If these fractional parts are well-distributed for every s, then the sum (9.13) should be controlled.Fix k such that 1 ≤ k ≤ ℓ. We will estimate the number of termsin the sum over q in (9.13). This estimate is similar to, and was inspiredby, a similar argument from a work of Cilleruelo and Garaev [8, Theorem1]. Consider any prime q with 12pM ≤ q < pM , |q|p = 1, and p−k ≤‖{s/q}‖ < p−k+1. Define N = ‖{s/q}p‖ pℓq. Note that N is a positiveinteger that is at most pM+ℓ−k+1: ||{s/q}p|| is bounded above by p−k+1 and qis bounded above by pM . If {s/q}p ≤ 1/2, then N = (s/q − [s/q]p) pℓq ≡ spℓ(mod pℓ). If {s/q}p > 1/2, then N = (1− s/q + [s/q]p) pℓq ≡ −spℓ (modpℓ). Therefore, q is a prime ≥ 12pM that divides a positive integer N withN ≤ pM+ℓ−k+1 and N ≡ ±spℓ (mod pℓ). The number of positive integers Nwith N ≤ pM+ℓ−k+1 and N ≡ ±spℓ (mod pℓ) is . max{pM−k+1, 1}, and thenumber of primes q ≥ 12pM that divide a specified positive integer N is atmost a constant times logNlog pM. Therefore, for a fixed k, the number of termsin the sum over q in (9.13) is. max{pM−k+1, 1} log pM+ℓ−k+1log pM.Therefore, (9.13) implies|F̂M (s)| . |QM |−1|RM |−1ℓ∑k=1min{pk, pM}max{pM−k+1, 1} log pM+ℓ−k+1log pM.Because |s|p = pℓ is between pM and p⌈τM⌉, |QM | & pM/ log pM , and |RM | =pM , we have the desired estimate. 9.2.3 Estimates on µ̂kProof. Let s ∈ Qp/Zp. The proof is by induction on k. The case k = 0follows immediately from the choice of ψ0 and the choice dµ0 = dµ−1 =ψ0 dx.So, we prove the inductive step. Assume k ≥ 1. Then the inductivehypothesis is that the equations in 9.2.2 hold with k replaced by k − 1. Bya standard argument we haveµ̂k(s) = ̂FMkµk−1(s) =∑t∈Qp/ZpF̂Mk(s− t)µ̂k−1(t). (9.14)1109.3. Fourier Dimension of W (m,n, τ)If the summand F̂Mk(s − t)µ̂k−1(t) is nonzero, then |t|p ≤ p⌈τMk−1⌉, whichcan be seen by applying the inductive hypothesis to µ̂k−1(t). Furthermore,we must have that FMk(s − t) is nonzero, so either s = t, orpMk < |s − t|p ≤ p⌈τMk⌉by Lemma 9.2.1 and by the assumption that ⌈τMk−1⌉ < Mk. Therefore, if|s|p > p⌈τMk⌉, every term of the sum in (9.14) is zero (since at least one of|s− t|p and |t|p must be greater than p⌈τMk⌉). This proves (9.8).If, instead, |s|p ≤ pMk , then only the t = s term contributes to the sum(since otherwise |s − t|p < pMk) and thus µ̂k(s) = F̂Mk(0)µ̂k−1(s). Thisestablishes (9.6), and also establishes (9.5) because the inductive hypothesisimplies that µ̂k−1(0) = 1. Only (9.7) needs to be shown. Suppose thatpMk < |s|p ≤ p⌈τMk⌉ as in (9.7). For all t ∈ Qp/Zp with F̂Mk(s− t)µ̂k−1(t) 6=0, we must have |s|p = |s − t|p (since |t|p must be at most p⌈τMk−1⌉ or elseµ̂k−1(t) will vanish by the inductive assumption (9.8) applied to k−1) and so(9.3) gives that |F̂Mk(s−t)| . |s|−1/τ log2(|s|p). By the inductive hypothesisand the fact that µk−1 is a positive measure, |µ̂k−1(t)| ≤ µ̂k−1(0) = 1 forall t ∈ Qp/Zp. The number of t ∈ Qp/Zp with |t|p ≤ p⌈τMk−1⌉ is exactlyp⌈τMk−1⌉; hence, the sum in (9.14) has at most p⌈τMk−1⌉ nonzero terms.Then we get|µ̂k(s)| . p⌈τMk−1⌉|s|−1/τp log2(|s|p)We apply our assumption that p⌈τMk−1⌉ < log(|s|p) in order to complete theproof. 9.3 Fourier Dimension of W (m, n, τ)The proof of this theorem is similar to the proof of Theorem 1.4.1.General SetupLet τ > (m+n)/m. For each M ∈ N we define QM and RM as in the proofof Theorem 1.4.1. ThenQnM ={q ∈ Zn : 12pM ≤ qj < pM , |qj |p = 1, qjprime ∀1 ≤ j ≤ n},RmM = {r ∈ Zm : 0 ≤ ri < pM ∀1 ≤ i ≤ m}.We will assume that M > 1 in order to guarantee that QM is nonempty.For each q ∈ QnM and r ∈ RmM , define the function φq,r on Zmnp byφq,r(x) = pm⌈τM⌉1B(0,1)(p−⌈τM⌉(xq − r)) ∀x ∈ Zmnp .1119.3. Fourier Dimension of W (m,n, τ)and we define the function FM on Zmnp byFM (x) = |QnM |−1|RmM |−1∑q∈QnM∑r∈RmMφq,r(x) ∀x ∈ Zmnp .Choose a strictly increasing sequence of integers (Mk)∞k=0 with M0 ≥ 2 suchthat for all k ∈ N,⌈τMk−1⌉ < Mk, (9.15)pmn⌈τMk−1⌉ < log(pMk) (9.16)As before, we take dµ−1(x) = dµ0(x) = dx for notational convenience. Forany s ∈ (Qp/Zp)mn, defineD(s) ={q ∈ Zn : {sij/qj}p = {sij′/qj′}p ∀1 ≤ i ≤ m, 1 ≤ j, j′ ≤ n}.Note that the set D(s) will be empty unless the column space of D(s) hasdimension 1. The set D(s) gives a family of q for which φ̂q,r(s) may benonzero:Lemma 9.3.1. For all M ∈ N, q ∈ QnM , r ∈ RmM , and s ∈ (Qp/Zp)mn,φ̂q,r(s) ={e(∑mi=1{risi1/q1}p) if |s|p ≤ p⌈τM⌉ and q ∈ D(s)0 otherwise.We now state the multidimensional versions of Lemmas 9.2.1 and 9.2.2.Lemma 9.3.2. For all M ∈ N and s ∈ (Qp/Zp)mn,F̂M (s) = 1 if s = 0 (9.17)F̂M (s) = 0 if 0 < |s|p ≤ pM (9.18)|F̂M (s)| . |s|−n/τ logn+1(|s|p) if pM < |s|p ≤ p⌈τM⌉ (9.19)F̂M (s) = 0 if |s|p > p⌈τM⌉ (9.20)Lemma 9.3.3. For all integers k ≥ 0 and all s ∈ (Qp/Zp)mn,µ̂k(s) = 1 if s = 0 (9.21)µ̂k(s) = µ̂k−1(s) if 0 < |s|p ≤ pMk (9.22)|µ̂k(s)| . |s|−n/τ logn+2(|s|p) if pMk < |s|p ≤ p⌈τMk⌉ (9.23)µ̂k(s) = 0 if |s|p > p⌈τMk⌉ (9.24)We will not prove that these lemmas imply Theorem 1.4.2 because thisfollows in the same way as Theorem 1.4.1. We will also omit the proof ofLemma 9.3.3 because of the similarity to the proof of Lemma 9.2.2. We willprove Lemma 9.3.1 and Lemma Fourier Dimension of W (m,n, τ)9.3.1 Fourier Transform of φq,rProof. Let M ∈ N, let q ∈ QnM , r ∈ RmM , and s ∈ Qp/Zp be given. Defineφr on Zmp to be the complex-valued functionφr(x) = pm⌈τM⌉1(0,1)(p−⌈τM⌉(x− r)) ∀x ∈ Zmp .φr is an m-dimensional tensor product of the weighted indicator function ofthe ball of radius p−⌈τM⌉. Therefore, it is easy to compute φ̂r using Lemma8.4.1.φ̂r(k) ={e({r · k}p) if |k|p ≤ p⌈τM⌉0 if |k|p > p⌈τM⌉.By p-adic Fourier inversion [49, p. 120], we haveφr(x) =∑k∈(Qp/Zp)mφ̂r(k)e(−{k · x}p) ∀x ∈ Zmp .Therefore, since |qj |p = 1 for all 1 ≤ j ≤ n,φq,r(x) = φr(xq) =∑k∈(Qp/Zp)mφ̂r(k)e(−{k · xq}p) ∀x ∈ ZmnpHere, the product xq denotes the usual matrix product of x and q, and theexpression k · xq is the dot product of the vectors k and xq in Zmnp . ByFubini’s theorem:φ̂q,r(s) =∑k∈(Qp/Zp)mφ̂r(k)∫Zmnpe({s · x}p)e(−{k · xq}p) dx=∑k∈(Qp/Zp)mφ̂r(k)m∏i=1n∏j=1∫Zpe({xij(sij − kiqj)}p) dxij .Now, fix k ∈ (Qp/Zp). By Lemma 8.4.1,∫Zpe({xij(sij − kiqj)}p) dxij ={1 if |sij − kiqj|p ≤ 10 otherwise.Note that, since ki ∈ Qp/Zp and |qj|p = 1, the condition that |sij−kiqj |p ≤ 1is equivalent to the condition that ki = {sij/qj}p. Therefore, we have thatφ̂q,r(s) ={φ̂r({s11/q1}p, . . . , {sm1/q1}p) if q ∈ D(s)0 otherwise.1139.3. Fourier Dimension of W (m,n, τ)The only thing that remains to be checked is that φ̂q,r(s) = 0 if |s|p > p⌈τM⌉,in which case either one component |{si1/q1}p|p is larger than p⌈τM⌉, or|si1|p 6= |sij|p for some i, j, in which case D(s) is empty. In either case,φ̂q,r(s) vanishes. The only thing that remains to be shown is Lemma 9.3.2. This lemmarelies on both Lemma 9.3.1 and on Lemma Estimate on F̂MLet M ∈ N and s ∈ (Qp/Zp)mn. Choose 1 ≤ i0 ≤ m and 1 ≤ j0 ≤ n suchthat |si0j0 |p = |s|p (In the only nontrivial case, the one in which which D(s)is nonempty, we can assume that j0 = 1). For |s|p > p⌈τM⌉, Lemma 9.3.1implies that F̂M (s) = 0. This proves (9.20). For |s|p ≤ p⌈τM⌉ it follows fromLemma 9.3.1 thatF̂M (s) = |QnM |−1|RmM |−1∑q∈QmM∩D(s)(9.25) ∑0≤r1<pMe({r1s1j0/qj0}p) · · · ∑0≤rm<pMe({rmsmj0/qj0}p) .We get equation (9.1) by setting s = 0 and using the fact that D(s) = QmMwhen s = 0.We will then assume instead that 0 ≤ |s|p ≤ p⌈τM⌉. So |s|p = pℓ for someℓ ∈ {1, . . . , ⌈τM⌉}. We will consider the sum over ri0 . Fix q ∈ QnM ∩D(s).Since |qj0 |p = 1, we have that |si0j0/qj0 |p = |si0j0 |p = |s|p = pℓ. Thereforethe p-adic expansion of si0j0/qj0 has the formsi0j0qj0=∞∑i=−ℓcipi, ci ∈ {0, 1, . . . , p − 1}, c−ℓ 6= 0. (9.26)As a real number, we have that 0 < {si0j0/qj0}p < 1 and so e({si0j0/qj0}p) 6=1. Therefore, we can use the geometric series formula∑0≤ri0<pMe({ri0si0j0/qj0}p) =1− e({pMsi0j0/qj0}p)1− e({si0j0/qj0}p). (9.27)If |s|p ≤ pM , we have {pMsi0j0/qj0}p = 0; hence, the sum in (9.27) vanishes.Then one of the factors on the right hand side of (9.25) is zero, and F̂M (s) =0. This proves (9.18). So the only thing left to do is prove (9.19).1149.3. Fourier Dimension of W (m,n, τ)We will assume pM < |s|p = pℓ ≤ p⌈τM⌉. For all z ∈ R, |1 − e(z)| =2| sin(πz)| = 2 sin(π ‖z‖) ≥ π ‖z‖, where ‖z‖ =: mink∈Z |z−k| is the distancefrom z to the nearest integer. Then, as in the proof of Lemma 9.2.1:∣∣∣∣∣∣∑0≤ri0<pMe({ri0si0j0/qj0}p)∣∣∣∣∣∣ ≤ min{1‖si0j0/qj0‖, pM}. (9.28)We also use the trivial bound∣∣∣∣∣∣∑0≤ri<pMe({risij0/qj0})∣∣∣∣∣∣ ≤ pM ∀ 1 ≤ i ≤ m. (9.29)In the notation of (9.26), we have‖{si0j0/qj0}p‖ ={∑−1i=−ℓ cipi if {si0j0/qj0}p ≤ 1/21−∑−1i=−ℓ cipi if {si0j)/qj0}p > 1/2.As in the proof of Lemma 9.2.1:|F̂M (s)| ≤ |QnM |−1|RmM |−1ℓ∑k=1∑q∈QnM∩D(s)p−k≤‖{si0j0/qj0}p‖<p−k+1p(m−1)M min{pk, pM}.(9.30)We will now claim that (q1, . . . , qn) → qj0 is an injection from QnM ∩ D(s)into the set {qj0 ∈ Z :12pM ≤ qj0 < pM , |qj0 |p = 1, qj prime}.This claim follows from the following two observations. First, for eachq ∈ QnM and 1 ≤ j ≤ n, we have {si0j0/qj0}p = {si0j/qj}p if and onlyif |si0j0 − si0j/qj|p (since |qj|p = |qj0 |p = 1), which happens if and only if|qj−qj0si0js−1i0j0 |p ≤ |s−1i0j0 |p = p−ℓ, which happens if and only if qj ≡ si0js−1i0j0(mod pℓ). Second, for any given b ∈ Qp, there can be at most one integersatisfying a ≡ b (mod pℓ) and 12pM ≤ a < pM ≤ pℓ. This establishes thatthe map is an injection and thus|F̂M (s)| ≤ |QnM |−1|RmM |−1 (9.31)ℓ∑k=1∑12pM≤qj0<pM|qj0 |p=1,qj0 primep−k≤‖{si0j0/qj0}p‖<p−k+1p(m−1)M min{pk, pM}.1159.3. Fourier Dimension of W (m,n, τ)We make the same argument as in Lemma 9.2.1 to conclude that for eachfixed k, the number of terms in the sum over qj0 in (9.32) is. max{pM−k+1, 1} log pM+ℓ−k+1log pM.So we get a bound of|QnM |−1|RmM |−1ℓ∑k=1p(m−1)M min{pk, pM}max{pM−k+1, 1} log pM+ℓ−k+1log pMon |F̂M (s)|. Since pM < |s|p = pℓ ≤ p⌈τM⌉, |QnM | ≈ pnM/(log pM )n, andbecause |RmM | = pmM , we get (9.19).9.3.3 Concluding Remarks Regarding W (m,n, τ)We elaborate a small amount on the gap between the Fourier dimensionbound in Theorem 1.4.2 and the known Hausdorff dimension from Aber-crombie’s paper [1]. The Fourier transform F̂M (s) is supported on a smallset: if the matrix s does not have column rank 1, then D(s) is empty andF̂M (s) vanishes. The small support of F̂M (s) can be used to show that µ̂k(s)cannot have good pointwise decay.Heuristically, we should not expect the set W (m,n, τ) to be a Salemset: it is contained in small neighbourhoods of a relatively small numberof hyperplanes. No upper bound is currently known on the upper Fourierdimension of W (m,n, τ) or its Euclidean analogue E(m,n, τ).116Chapter 10ConclusionThe results of this thesis raise some interesting questions that warrant fur-ther study. We will provide a brief discussion of some of the research prob-lems that are relevant to the work described in this thesis.10.1 Configurations10.1.1 Squares of DifferencesAlthough the results in [19] apply to a very broad class of functions, thereis no reason to believe that these results will be optimal when applied to aspecific problem. For example, consider the specific function f(x1, x2, x3) =(x3 − x1)2 − (x2 − x1). Theorem 1.1.1 and Theorem 3.1.4 can be applied tothis configuration in order to locate a subset of R of Hausdorff dimension12 that does not contain 3 distinct points x1, x2, x3 such that f(x1, x2, x3)vanishes.However, in the discrete setting, certain additional results are availablefor this function. In fact, Ruzsa [43] constructs a subset S of {1, . . . , N}containing at least c1x12(1+ log 7log 65)points such that for any distinct x, y ∈ S,the value x−y is not a perfect square. Of course, this implies that S does notcontain any nontrivial solutions to the equation f(x1, x2, x3) = 0. Unfortu-nately, there does not seem to be a simple way to use this result to constructa subset E ⊂ R that does not contain any solutions to f(x1, x2, x3) = 0.There is also a positive result for the function f on finite fields. Bourgainand Chang [6] show that there exists a constant c1 > 0 such that if A ⊂ |Fp|contains at least c1p14/15 elements, then A must contain three distinct pointssuch that f(x1, x2, x3) = 0. This gives some hope that a method similar tothe one used by  Laba and Pramanik [32] will give some condition on asubset of R that guarantees the existence of 3 points x1, x2, x3 such that(x2 − x1) = (x3 − x1)2. Shaoming Guo, Malabika Pramanik, and I areinterested in pursuing this question further.11710.1. Configurations10.1.2 Configurations and Fourier DimensionThe theorems presented in Chapter 3 concern the Hausdorff and Minkowskidimensions of subsets E ⊂ Rn that do not contain certain types of con-figurations. This leaves open the question of what can be said about theFourier dimension of such sets E. This question is interesting because, inthe case of 3-term arithmetic progressions,  Laba and Pramanik [32] providea Fourier decay condition on a set E that guarantees that E contains a3-term arithmetic progression:Theorem 10.1.1 (Theorem 1.2 from [32]). Assume that E ⊂ [0, 1] thatsupports a probability measure µ with the following properties:• µ([x, x+ ǫ]) ≤ C1ǫα for all 0 < ǫ ≤ 1,• |µ̂(k)| ≤ C2(1− α)−B |k|−β2 for all k 6= 0.where 0 < α < 1 and 2/3 < β ≤ 1. If α > 1 − ǫ0, where ǫ0 is a sufficientlysmall constant depending only on C1, C2, B, β, then E contains a nontrivial3-term arithmetic progression.In light of this theorem, it seems reasonable to conjecture that any setE of Fourier dimension 1 should contain a 3-term arithmetic progression.In particular, the second condition of this theorem appears at first glanceto be saying that E has Fourier dimension equal to β. However, the depen-dence of α on the constants C1 and C2 makes the theorem statement morecomplicated. In fact, Shmerkin [47] constructed a set of Fourier dimension1 that does not contain any 3-term arithmetic progressions.This raises the question of what can be said for arbitrary configurations.The case of linear configurations has been addressed by Ko¨rner [31]: Ko¨rnerestablishes that there is a set E ⊂ Rn of Fourier dimension 1v−1 that doesnot contain any v points (x1, . . . , xv) satisfying any nontrivial algebraic re-lation∑vj=1 ajxj for integers xj . This dimension1v−1 is consistent with thestatement of Theorem 1.1.1. Therefore, it is natural to ask whether thestatement of Theorem 1.1.1 is true for Fourier dimension instead of Haus-dorff dimension. If 1v−1 is replaced by1v , a straightforward random Cantorset construction should give the desired set; the Euclidean equivalent of thisresult was also established by Ko¨rner [30] using a Baire category argumentinstead of a direct construction.In a joint project with Pramanik, we will attempt to establish a resultsimilar to that of Ko¨rner for arbitrary (not necessarily linear) configurations.The strategy is to adapt the proof of Ko¨rner’s result [31] to this setting.11810.2. Besicovitch Sets on Local Fields10.1.3 Local FieldsThe discrepancy between the capset result [16] and Theorem 1.2.1 raises thefollowing question: what conditions on a set are sufficient to guarantee thata set E ⊂ Kn contains a 3-term arithmetic progression? The first placeto look for an answer to this question is Theorem 10.1.1. I conjecture thata condition analogous to the conditions of this theorem will be enough toguarantee the existence of 3-term arithmetic progressions on Kn.If K has finite characteristic, the situation might be somewhat differentfrom the characteristic 0 case. There do not appear to be any obstructions tomodifying Shmerkin’s construction [47] to work in the p-adic setting. How-ever, the capset result presents a real barrier to applying this constructionon function fields Fq((t)) because Shmerkin’s construction relies on a con-struction of Behrend [2] of a subset of {1, . . . , N} of size greater than CǫN1−ǫthat does not contain any 3-term arithmetic progressions. The capset resultimplies that such sets cannot exist in (Fq)n.In fact I will make the conjecture that any subset of (Fq)n with Fourierdimension sufficiently close to 1 must contain an arithmetic progression.Such a result might follow from a modification of the proof of Theorem10.1.1, but this has yet to be seriously pursued.10.2 Besicovitch Sets on Local FieldsTwo important problems related to Besicovitch sets are the Kakeya problemand the restriction problem. The Kakeya problem asks the following ques-tion: if E ⊂ Rn is a Kakeya set, must E have Hausdorff dimension n? Thisproblem is connected to a large family of problems in Harmonic analysis.The Kakeya problem was solved in dimension 2 by Davies [10].A related problem is the Fourier restriction problem. The restrictionproblem concerns questions of the following type: if S is a sufficiently curvedsurface in Rn and σ is the surface measure on S, for which values of pand q is the map from Sp(Rn) → Lq(Rn) defined by f 7→ (f̂)|S bounded?Here, Sp(Rn) is the Schwartz space of functions on Rn equipped with theLp norm. Tomas [50] established an Lp-to-L2 restriction estimate for thesurface area measure on the sphere Sd−1 for 1 ≤ p < 2(d+1)d+3 ; the endpointestimate p = 2(n+1)n+3 was achieved by Elias Stein, as is mentioned in [48]. ForLp → L2 restriction estimates, this is the best possible result. The Fourierrestriction conjecture concerns other values of q.11910.3. Salem SetsConjecture 10.2.1 (Restriction Conjecture). The spherical surface mea-sure σ satisfies an Lp-to-Lq restriction estimate for any pair (p, q) such thatp < 2dd+1 , q ≤ p(d−1)(p−1)(d+1) .By comparison to the Euclidean setting, the status of restriction andKakeya-type results over local fields is less well-understood. Ellenberg,Oberlin, and Tao [17] proposed the discrete valuation ring Fp[[t]] as a modelcase for the study of Kakeya problems, with the hope of such Kakeya-typeresults as a stepping stone for translating the polynomial method and Dvir’sfinite field Kakeya result to the Euclidean setting, where little work on re-striction has been done.Dummit and Hablicsek [11] established that a Besicovitch set in Fq[[t]]2must have Minkowski dimension 2. There does not appear to be an analogueof Davies’ result [10] on the Hausdorff dimension of Kakeya sets. It is pos-sible that such a result could be obtained via a sharpening of the methodsin [11].The restriction problem for the sphere does not make sense in the non-archimedean local field setting, because the unit sphere in Kn has positiveHaar measure. Nonetheless, it is possible to consider parabolic versionsof the restriction problem for such fields. Restriction problems for non-archimedean local fields are a subject of ongoing research, currently beingpursued by Hickman and Wright.10.3 Salem SetsAlthough Theorem 1.4.1 is sufficient to precisely determine the Fourier di-mension of W (τ), Theorem 1.4.2 is not sufficient to precisely determine theFourier dimension of W (m,n, τ). Computing upper bounds on the Fourierdimension of a set E is typically a difficult problem because it requires astatement about the pointwise Fourier decay of all measures on E.There does not appear to be a simple way to modify the argument ofTheorem 1.4.1 to apply to local fields other than Qp because of the difficultyof establishing the exponential sum estimate used to prove Lemma 9.2.1 inthis setting. Together with Hambrook, we will aim to consider this problem.Some preliminary computations seem to indicate that a similar estimateshould hold over arbitrary local fields.The problem of computing explicit Salem sets of arbitrary Fourier dimen-sion in Qnp for n > 1 is still open. Hambrook [23] has constructed explicitSalem sets of arbitrary Fourier dimension in R2, but no such sets are knownin Rn for n > 2.12010.3. Salem SetsHambrook and I are interested in constructing Salem sets in Rn. Asa prototype for this argument, we are exploring alternative matrix-basedconstructions for Salem sets in R2.We are also interested in the problem of computing the Fourier dimensionof a modified version of E(τ), so that the numerators r are restricted to liein a subset of {0, . . . , q} such as the quadratic residues mod q.121Bibliography[1] A. G. Abercrombie. The Hausdorff dimension of some exceptional setsof p-adic integer matrices. J. Number Theory, 53(2):311–341, 1995.[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.[3] A. S. Besicovitch. On Kakeya’s problem and a similar one. Math. Z.,27(1):312–320, 1928.[4] C. Bluhm. Random recursive construction of Salem sets. Ark. Mat.,34(1):51–63, 1996.[5] C. Bluhm. On a theorem of Kaufman: Cantor-type construction oflinear fractal Salem sets. Ark. Mat., 36(2):307–316, 1998.[6] J. Bourgain and M.-C. Chang. Nonlinear Roth type theorems in finitefields. Israel J. Math., 221(2):853–867, 2017.[7] X. Caruso. Almost all non-archimedean Kakeya sets have measure zero.Manuscript. Available at On-line; accessed January 19, 2018.[8] J. Cilleruelo and M. Z. Garaev. Concentration of points on two andthree dimensional modular hyperbolas and applications. Geom. Funct.Anal., 21(4):892–904, 2011.[9] E. Croot, V. F. Lev, and P. P. Pach. Progression-free sets in Zn4 areexponentially small. Ann. of Math. (2), 185(1):331–337, 2017.[10] R. O. Davies. Some remarks on the Kakeya problem. Proc. CambridgePhilos. Soc., 69:417–421, 1971.[11] E. P. Dummit and M. Hablicsek. Kakeya sets over non-Archimedeanlocal rings. Mathematika, 59(2):257–266, 2013.122Bibliography[12] Z. Dvir. On the size of Kakeya sets in finite fields. J. Amer. Math.Soc., 22(4):1093–1097, 2009.[13] Y. Edel. Extensions of generalized product caps. Des. Codes Cryptogr.,31(1):5–14, 2004.[14] H. G. Eggleston. Sets of fractional dimensions which occur in someproblems of number theory. Proc. London Math. Soc. (2), 54:42–93,1952.[15] F. Ekstro¨m, T. Persson, and J. Schmeling. On the Fourier dimensionand a modification. J. Fractal Geom., 2(3):309–337, 2015.[16] J. S. Ellenberg and D. Gijswijt. On large subsets of Fnq with no three-term arithmetic progression. Ann. of Math. (2), 185(1):339–343, 2017.[17] J. S. Ellenberg, R. Oberlin, and T. Tao. The Kakeya set and maxi-mal conjectures for algebraic varieties over finite fields. Mathematika,56(1):1–25, 2010.[18] R. Fraser. Large subsets of local fields not containing configurations.Submitted. Available at On-line; accessed January 19, 2018.[19] R. Fraser and M. Pramanik. Large sets avoiding patterns. Submitted.[20] R. Fraser. Kakeya-type sets in local fields with finite residue field.Mathematika, 62(2):614–629, 2016.[21] R. Fraser and K. Hambrook. Explicit salem sets, Fourier restriction,and metric diophantine approximation in the p-adic numbers. Sub-mitted. Available at Online; ac-cessed January 19, 2018.[22] O. Frostman. Potentiel de´quilibre et capacite´ des ensembles avecquelques applications a` la the´orie des fonctions. Lunds Univ. MathSem., 3:1–118, 1935.[23] K. Hambrook. Explicit Salem sets in R2. Adv. Math., 311:634–648,2017.[24] K. Hambrook. Explicit salem sets and applications to metrical dio-phantine approximation. To Appear in Tran. Amer. Math. Soc.123Bibliography[25] V. Jarn´ık. u¨ber die simultanen diophantischen Approximationen. Math.Z., 33(1):505–543, 1931.[26] J.-P. Kahane. Some random series of functions, volume 5 of Cam-bridge Studies in Advanced Mathematics. Cambridge University Press,Cambridge, second edition, 1985.[27] R. Kaufman. On the theorem of Jarn´ık and Besicovitch. Acta Arith.,39(3):265–267, 1981.[28] T. Keleti. A 1-dimensional subset of the reals that intersects each of itstranslates in at most a single point. Real Anal. Exchange, 24(2):843–844, 1998/99.[29] T. Keleti. Construction of one-dimensional subsets of the reals notcontaining similar copies of given patterns. Anal. PDE, 1(1):29–33,2008.[30] T. W. Ko¨rner. Measures on independent sets, a quantitative version ofRudin’s theorem. Proc. Amer. Math. Soc., 135(12):3823–3832, 2007.[31] T. W. Ko¨rner. Fourier transforms of measures and algebraic relations ontheir supports. Ann. Inst. Fourier (Grenoble), 59(4):1291–1319, 2009.[32] I.  Laba and M. Pramanik. Arithmetic progressions in sets of fractionaldimension. Geom. Funct. Anal., 19(2):429–456, 2009.[33] P. Maga. Full dimensional sets without given patterns. Real Anal.Exchange, 36(1):79–90, 2010/11.[34] A. Ma´the´. Sets of large dimension not containing polynomial configu-rations. Adv. Math., 316:691–709, 2017.[35] P. Mattila. Geometry of sets and measures in Euclidean spaces, vol-ume 44 of Cambridge Studies in Advanced Mathematics. CambridgeUniversity Press, Cambridge, 1995. Fractals and rectifiability.[36] P. Mattila. Fourier analysis and Hausdorff dimension, volume 150 ofCambridge Studies in Advanced Mathematics. Cambridge UniversityPress, Cambridge, 2015.[37] J. V. Melnicˇuk. Hausdorff dimension in Diophantine approximations ofp-adic numbers. Ukrain. Mat. Zh., 32(1):118–124, 144, 1980.124Bibliography[38] C. Papadimitropoulos. Fourier Restriction Phenomenon in Thin Sets.PhD thesis, University of Edinburgh, 2010.[39] C. Papadimitropoulos. Salem sets in local fields, the Fourier restric-tion phenomenon and the Hausdorff-Young inequality. J. Funct. Anal.,259(1):1–27, 2010.[40] C. Papadimitropoulos. Salem sets in the p-adics, the Fourier restrictionphenomenon and optimal extension of the Hausdorff-Young inequality.In Vector measures, integration and related topics, volume 201 of Oper.Theory Adv. Appl., pages 327–338. Birkha¨user Verlag, Basel, 2010.[41] A. M. Robert. A course in p-adic analysis, volume 198 of GraduateTexts in Mathematics. Springer-Verlag, New York, 2000.[42] K. Roth. Sur quelques ensembles d’entiers. C. R. Acad. Sci. Paris,234:388–390, 1952.[43] I. Z. Ruzsa. Difference sets without squares. Period. Math. Hungar.,15(3):205–209, 1984.[44] R. Salem. On singular monotonic functions whose spectrum has a givenHausdorff dimension. Ark. Mat., 1:353–365, 1951.[45] E. Sawyer. Families of plane curves having translates in a set of measurezero. Mathematika, 34(1):69–76, 1987.[46] J.-P. Serre. Local fields, volume 67 of Graduate Texts in Mathematics.Springer-Verlag, New York-Berlin, 1979. Translated from the Frenchby Marvin Jay Greenberg.[47] P. Shmerkin. Salem Sets with No Arithmetic Progressions. Int. Math.Res. Not. IMRN, (7):1929–1941, 2017.[48] E. M. Stein and S. Wainger. Problems in harmonic analysis related tocurvature. Bull. Amer. Math. Soc., 84(6):1239–1295, 1978.[49] M. H. Taibleson. Fourier analysis on local fields. Princeton UniversityPress, Princeton, N.J.; University of Tokyo Press, Tokyo, 1975.[50] P. A. Tomas. A restriction theorem for the Fourier transform. Bull.Amer. Math. Soc., 81:477–478, 1975.[51] A. Weil. Basic number theory. Classics in Mathematics. Springer-Verlag, Berlin, 1995. Reprint of the second (1973) edition.125Bibliography[52] L. Wisewell. Families of surfaces lying in a null set. Mathematika,51(1-2):155–162 (2005), 2004.[53] J. Wolf. Finite field models in arithmetic combinatorics—ten years on.Finite Fields Appl., 32:233–274, 2015.[54] T. Wolff. Recent work connected with the Kakeya problem. In Prospectsin mathematics (Princeton, NJ, 1996), pages 129–162. Amer. Math.Soc., Providence, RI, 1999.[55] T. Wolff. Lecture Notes on Harmonic Analysis, volume 29 of UniversityLecture Series. AMS, 2003.126


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



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"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items