Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Distance problems and points on curves : an algebraic approach Schwartz, Ryan 2014

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

Item Metadata

Download

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

Full Text

Distance Problems and Points onCurvesAn Algebraic ApproachbyRyan SchwartzB.Sc. in Mathematics and Computer Science, The University of theWitwatersrand, 2005B.Sc. (Honours) in Computer Science, The University of the Witwatersrand, 2005B.Sc. (Honours) in Mathematics, The University of the Witwatersrand, 2006M.Sc. in Mathematics, The University of British Columbia, 2009A 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)April 2014c© Ryan Schwartz, 2014AbstractIn this thesis we give results on unit and rational distances, structure resultsfor surfaces containing many points of a cartesian product and a survey ofvarious, mainly combinatorial, applications of the Subspace Theorem. Wetake an algebraic approach to most of the problems and use techniques fromcommutative algebra, incidence geometry, number theory and graph theory.In Chapter 2 we give extensions of a result of Elekes and Ro´nyai thatsays that if the graph of a real (or complex) polynomial contains manypoints of a cartesian product then the polynomial has a special additive ormultiplicative form. We extend this to asymmetric cartesian products and tohigher dimensions. Elekes and Ro´nyai’s result was used to prove a conjectureof Purdy on the number of distinct distances between two collinear pointsets in the plane. Our extensions give improved bounds for the conjecture.In Chapter 3 we prove a special case of the Erdo˝s unit distance problem.This problem asks for the maximum possible number of unit distances be-tween n points in the plane in the form of an asymptotic upper bound. Weprovide an upper bound of n1+7/√logn when we only consider unit distancescorresponding to roots of unity and give a superlinear lower bound. We alsoconsider related rational distance problems. We require an algebraic resultof Mann on the number of solutions of linear equations of roots of unity.In Chapter 4 we extend our result from the previous chapter to unitdistances coming from a multiplicative subgroup of C∗ of “low” rank. We usea corollary of the Subspace Theorem. In this case we get, for ε > 0, at mostcn1+ε unit distances. We show that the well known lower bound constructionof Erdo˝s for the general unit distance problem consists of distances fromsuch a subgroup and so our result applies to the best known maximal unitdistance sets.In Chapter 5 we give a survey of various applications of the SubspaceTheorem including less well known combinatorial applications such as sum-product estimates and line configurations with few distinct intersections.iiPrefaceThis thesis is based on four papers. The first three have been published andthe last has been accepted for publication. The first three papers are givenas published in this thesis with minor typographical and stylistic changes.The fourth paper is a survey paper and has been modified slightly in thisthesis as parts of it appear in the other papers.• Chapter 2 was published as:R. Schwartz, J. Solymosi and F. de Zeeuw, Extensions of a resultof Elekes and Ro´nyai, Journal of Combinatorial Theory, Series A120(7):1695-1713, 2013.The work was shared equally between the three authors.• Chapter 3 was published as:R. Schwartz, J. Solymosi and F. de Zeeuw, Rational distances withrational angles, Mathematika 58(2):409-418, 2012.This paper also appeared as Chapter 4 of Frank de Zeeuw’s PhD thesis.The work was shared equally between the three authors.• Chapter 4 was published as:R. Schwartz, Using the subspace theorem to bound unit distances,Moscow Journal of Combinatorics and Number Theory 3(1):108-117,2013.The idea of using the Subspace Theorem for this problem was givento me by Jo´zsef Solymosi.• Chapter 5 is based on a survey talk given by Jo´zsef Solymosi at theworkshop “Geometry, Structure and Randomness in Combinatorics”iiiPrefacein Pisa in September 2012. It is to appear in a special volume of pa-pers from the workshop in the Edizioni Della Normale di Pisa (editors:Jirka Matousˇek, Jarik Nesˇetrˇil and Marco Pellegrini).The work of writing up the material was shared between the two au-thors.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . ixDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Some notation . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Surfaces containing many points of a cartesian product . . . 21.3 The Erdo˝s unit distance problem . . . . . . . . . . . . . . . . 71.4 Combinatorial applications of the Subspace Theorem . . . . 121.5 Layout of this document . . . . . . . . . . . . . . . . . . . . 132 Extensions of a result of Elekes and Ro´nyai . . . . . . . . . 152.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3 Proof of Theorems 2.1.2 and 2.1.3 . . . . . . . . . . . . . . . 252.4 Proof of Theorems 2.1.4, 2.1.5, and 2.1.6 . . . . . . . . . . . 302.5 Applications and limitations . . . . . . . . . . . . . . . . . . 373 Rational distances with rational angles . . . . . . . . . . . . 413.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.2 Main results and proof sketch . . . . . . . . . . . . . . . . . 423.3 Mann’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 433.4 Rational distances and Mann’s Theorem . . . . . . . . . . . 46vTable of Contents3.5 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . 504 Using the Subspace Theorem to bound unit distances . . 514.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Proof of the main result . . . . . . . . . . . . . . . . . . . . . 524.3 Analysis of Erdo˝s’ lower bound . . . . . . . . . . . . . . . . . 545 Combinatorial applications of the Subspace Theorem . . . 595.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.2 Number-theoretic applications . . . . . . . . . . . . . . . . . 615.3 Combinatorial applications . . . . . . . . . . . . . . . . . . . 656 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696.1 Surfaces containing many points of a cartesian product . . . 696.2 The Erdo˝s unit distance problem . . . . . . . . . . . . . . . . 706.3 Combinatorial applications of the Subspace Theorem . . . . 71Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73viList of Tables1.1 The progression of lower bounds for the Erdo˝s distinct dis-tances problem up to the near complete solution of Guth andKatz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8viiList of Figures1.1 An example of a point-line incidence . . . . . . . . . . . . . . 31.2 Two collinear point sets P and Q. The distances betweenthe two point sets are shown in the second figure. The anglebetween the lines containing the point sets is α. . . . . . . . . 61.3 A collection of points is given in (a). A unit circle is drawnaround each point in (b). The correspondence between unitdistances and point-circle incidences is shown in (c). . . . . . 9viiiAcknowledgementsI would like to thank my research supervisor Jo´zsef Solymosi. I am indebtedto him for his constant support, reassurance and wealth of ideas. I would alsolike to thank Frank de Zeeuw for many helpful discussions and distractions.I am grateful to my supervisory committee for their input, time and effortand to everyone in the UBC Mathematics Department for all their help overthe years.For the work in Chapter 2, the authors would like to thank the refereesfor their helpful comments and suggestions.For the work in Chapter 3, the authors would like to thank Jirka Ma-tousˇek for making us aware of the lower bound for unit distances with nothree points on a line and to the anonymous referee for helpful comments,suggestions and corrections.For the work in Chapter 4, I am very grateful to Jo´zsef Solymosi forthe idea of using the Subspace Theorem and other useful discussions. Iwould also like to thank Yann Bugeaud for making me aware of Amorosoand Viada’s bound for the corollary of the Subspace Theorem giving theimproved bound in Theorem 4.1.1. Lastly I would like to thank ChristianElsholtz for helpful comments and corrections in the last section and thereferee for their helpful information.For the work in Chapter 5, the authors are thankful to Jarik Nesˇetrˇilfor the encouragement to write this survey. We are also thankful to theorganizers of the workshop in Pisa, ”Geometry, Structure and Randomnessin Combinatorics”, where the parts of this paper were presented.ixDedicationFor my family who provide the foundation for my strength and the wingsfor my dreams.xChapter 1IntroductionMany problems in combinatorial geometry deal with points on curves or sur-faces. Even grid points can be viewed as such arrangements by consideringthem as lying on collections of parallel lines. There are many useful resultsregarding the structure of such arrangements. Possibly the best known ex-ample, and a hallmark of the field, is the Szemere´di-Trotter Theorem whichbounds the number of point-line incidences in the plane. A number of ex-tensions of this result exist including analogues in higher dimensions and forcurves instead of lines.Distance problems are also common in combinatorial geometry. For ex-ample, it is natural to ask, given n points in the plane, how many timesa certain distance appears or how many distinct distances appear. Theseproblems are related to point-circle incidences. These two questions, firstasked by Erdo˝s, are called the unit distance problem and the distinct dis-tances problem respectively and have been studied extensively with the firststill open and the second being solved very recently. The first problem getsits name from the fact that by scaling we may assume that the distance inquestion is one.These problems have a strong combinatorial flavour and can often bestated quite simply but for many of them elementary techniques fail. Arange of results from various fields have been applied to such problems.These include analytic, probabilistic, topological, number-theoretic and al-gebraic methods. The geometric aspects of these problems make techniquesfrom algebraic geometry useful and the combinatorial aspects make number-theoretic tools useful. Combining these a number of previously unreachableproblems in the field have been solved.In this thesis we give a number of results regarding points on curves andsurfaces and distance problems using algebraic techniques. First we give ex-tensions of various results of Elekes and Ro´nyai on the structure of hypersur-faces and collections of lines containing many points of a cartesian product.Next we give a number of special cases of the Erdo˝s unit distance prob-lem where we only consider distances from multiplicative groups with “low”rank. Finally we give an overview of the Subspace Theorem of Schmidt and11.1. Some notationits extensions with particular emphasis on combinatorial applications. Wewill use tools from graph theory, incidence geometry, commutative algebraand number theory.The remainder of the introduction will give an overview of the researcharea, describe the main results of the thesis and provide the necessary back-ground to understand those results.1.1 Some notationMost of the results in this work are of an asymptotic nature so we will oftenuse c, c′, C, C ′, etc. to represent arbitrary constants. We may also use big Onotation and little-o notation. Specifically,• f(x) = O(g(x)) (or f(x) ≤ O(g(x))) if there are positive constants Mand x0 such that f(x) ≤Mg(x) for x > x0.• f(x) = o(g(x)) (or f(x) ≤ o(g(x))) if limx→∞f(x)/g(x) = 0.We may use grid to mean cartesian product and the plane to mean R2 withthe usual Euclidean distance.1.2 Surfaces containing many points of acartesian productWhen dealing with points and curves it is natural to ask how they interact.For example, given a collection of curves, we may want to bound the numberof intersections between pairs of curves. Bezout’s Theorem, from algebraicgeometry, bounds the number of intersections between two algebraic planecurves without a common factor by the product of their degrees. For detailssee [32]. Another example is, given a collection of points, to find the numberof connecting lines between pairs of points. Beck’s Theorem is a structureresult regarding this problem. It says that, given a set of n points in theplane, either cn of the points lie on the same line or the points determineat least cn2 distinct connecting lines [7]. A connecting line is a line betweentwo points in the point set. Notice that in the first case of Beck’s Theoremthere are cn2 pairs of points that give the same connecting line.Another important interaction is a point-line incidence. Given a col-lection of points P and a collection of lines L, a point-line incidence is apair (p, `) ∈ P × L such that p ∈ `. See Figure 1.1 for an example. Themore general point-curve incidences can be defined similarly. We will denote21.2. Surfaces containing many points of a cartesian productFigure 1.1: An example of a point-line incidencethe number of incidences between P and L (or a collection of curves C) byI(P,L) (or I(P, C)).The Szemere´di-Trotter Theorem gives an upper bound on the numberof point-line incidences in the plane. It was first proved by Szemere´di andTrotter in 1983 [64] using cell decomposition. A number of different proofshave been given with the simplest by Sze´kely using the crossing inequalityfor graphs [62]. The Szemere´di-Trotter Theorem says that the number ofpoint-line incidences between n points and m lines in the plane is at mostI(P,L) ≤ C(m2/3n2/3 +m+ n).Note that the m2/3n2/3 term above is dominant for√m ≤ n ≤ m2 andmost, if not all, applications of the Szemere´di-Trotter Theorem fall in thisrange. This theorem is tight up to the constant C with the lower boundcoming from a suitably chosen grid. Such a grid was first given by Erdo˝s[25] and a slightly simpler example was later given by Elekes [20].An equivalent form of the Szemere´di-Trotter Theorem exists which dealswith “rich” lines. Given a point set P and a positive integer k, a line is k-richon P if the line contains at least k points from P. The second formulationof the theorem states that, given a positive integer k and a point set P ofsize n, the number of k-rich lines on P is at most C(n2/k3 + n/k).The above two results hold for arbitrary point sets but more can besaid about the structure of the lines when the points form a grid. If wehave “many” lines and they all contain “many” points of the grid then thefollowing result of Elekes gives that a positive fraction of the lines are parallelor have the same intersection point [18]. A collection of lines is said to beconcurrent if they have the same intersection point.Lemma 1.2.1. Suppose A,B ⊂ R and |A| = |B| = n. For all c1, c2 > 031.2. Surfaces containing many points of a cartesian productthere exists C > 0, independent of n, such that if Cn lines in R2 are c1n-richon A×B, then at least c2n of them must be parallel or concurrent.Note that a line can contain at most n points of an n × n grid. So theabove lemma deals with lines containing “many” grid points. Also, an n×ngrid contains n2 points. So by the second formulation of the Szemere´di-Trotter Theorem we cannot have more than C ′n c1n-rich lines. Thus thelemma deals with “many” rich lines. An extension of this result appears asLemma 2.2.4 in Chapter 2. The extension deals with the case when we havefewer c1n-rich lines. Specifically, it says that given 2/3 ≤ α ≤ 1, if we haveat least cnα c1n-rich lines then at least c′n3α−2 of the lines are parallel orconcurrent. We retrieve Lemma 1.2.1 when α = 1. At the other extreme,if α = 2/3, then we only have a constant number of parallel or concurrentlines.A collection of lines are in general position if no two are parallel andno three are concurrent. Our generalised line lemma only holds for n2/3 ormore lines but a conjecture of Solymosi says that the same should hold fora constant number or at most nε lines in general position. For more detailssee [20]. A recent result of Amirkhanyan et al. addresses this conjecture [2].The theorems above give much information about points and lines butwhat if we have more complicated objects such as “well-behaved” curves?The following theorem of Pach and Sharir addresses this case [52, 53]. Wedefine this so-called good behaviour as follows. A collection C of continuousreal planar curves with no self-intersection has k degrees of freedom andmultiplicity-type s if any pair of curves in Γ have at most s intersectionpoints and for any k points there are at most s elements of Γ that containall k points.Theorem 1.2.2. Let P be a set of n points and C be a set of m curves asdefined above with k degrees of freedom and multiplicity type s. Then thereis a constant C > 0 depending on k and s such thatI(P, C) ≤ C(m(2k−2)/(2k−1)nk/(2k−1) +m+ n).Note that this theorem holds for algebraic curves of bounded degree sincethese curves can be split up into a small number (depending on the degree)of continuous curves without self-intersection.We already saw Elekes’ result about rich lines. In 2000 Elekes and Ro´nyaiused this result along with many other tools from algebra, graph theoryand incidence geometry to prove a structure theorem about surfaces whose41.2. Surfaces containing many points of a cartesian productgraphs contain many points of a grid [21]. It was the inspiration for Chap-ter 2. The Elekes-Ro´nyai Theorem states that if the graph of a two variablepolynomial f ∈ R[x, y] of bounded degree contains cn2 points of an n×n×ncartesian product then the polynomial has the formf(x, y) = g(k(x) + l(y)), or f(x, y) = g(k(x) · l(y)),where g, k, l ∈ R[t].So if the graph of a two variable real polynomial contains many pointsof a cartesian product then the polynomial should have a special additive ormultiplicative form.1.2.1 ResultsIn Chapter 2 we give a number of extensions of this result using our extensionof Elekes’ line lemma. Specifically, we get the result for a smaller assymetriccartesian product of size n × n5/6 × n and two analogous results in onedimension higher for cartesian products of size n × n × n × n and n × n ×n5/6+ε × n respectively. Using the result of Amirkhanyan et al. in place ofour line lemma even smaller cartesian products can be considered. We alsoprovide a construction using translations of a parabola on a grid to showthat one of our higher dimensional extensions is near optimal.Our proofs of these results were based on the original proof of Elekes andRo´nyai. The main difference was the generalised line lemma. The proofsproceed as follows:1. break up the surface into fibres,2. define curves from pairs of fibres and show that many of them are rich,3. use the Pach-Sharir Theorem to show that many of the curves coincide,4. show that many of the curves must share a common inner function,5. reduce to the case of lines to get many lines containing many pointsof a cartesian product,6. apply a line lemma to get many parallel or concurrent lines,7. use some algebra to get the required form for the polynomial.In this process the additive form comes from many parallel lines and themultiplicative form comes from many concurrent lines.51.2. Surfaces containing many points of a cartesian productQPα(a) Two collinear point sets.QPα(b) All distances between the point sets.Figure 1.2: Two collinear point sets P and Q. The distances between thetwo point sets are shown in the second figure. The angle between the linescontaining the point sets is α.For our extensions we require a number of algebraic results, the detailsof which can be found in Chapter 2. Most of these were given in Elekes andRo´nyai’s paper. For our higher dimensional extensions we require anotheralgebraic result. Namely a special case of the Schwartz-Zippel Lemma whichcan be considered as a generalisation to higher dimensions of the fact thata degree d univariate polynomial can have at most d roots. Details and aproof of the lemma can be found in [36]. We also require a graph-theoreticresult which states that if we colour the edges of a graph on n vertices withcn2 edges such that a bounded number of colours meet at each vertex thenthe graph contains a monochromatic (one colour) subgraph containing c′n2edges. This result also appears in Elekes and Ro´nyai’s work.The Elekes-Ronyai Theorem and our extensions of it seem quite abstractbut they can be applied to a number of combinatorial problems. They lendthemselves especially well to distance problems. For instance, consider thefollowing conjecture of Purdy. If the number of distinct distances betweentwo collinear point sets in the plane of size n each is Cn then the linescontaining the point sets must be parallel or orthogonal. Figure 1.2 containssuch a configuration. This problem can be translated into a problem aboutthe graph of a polynomial containing many points of a cartesian product.The Elekes-Ro´nyai Theorem then gives the stated conditions on the lines.Our extensions allow us to consider the same problem but with fewer pointson one of the lines.61.3. The Erdo˝s unit distance problem1.3 The Erdo˝s unit distance problemAs mentioned above the unit distance problem asks for the maximum pos-sible number u(n) of times the distance one occurs between n points in theplane. This problem was first asked by Erdo˝s in 1946 [25]. Erdo˝s showedthat u(n) ≥ n1+c/ log logn using a scaled portion of an integer lattice. Thebound requires number-theoretic tools. Specifically, bounds on the numberof representations of a number as a sum of two squares are used. Moredetails of this can be found in Chapter 4. Erdo˝s conjectured that the truemagnitude of u(n) is close to this lower bound. He was able to show thatu(n) ≤ cn3/2 by using the fact that two unit circles intersect in at most twopoints. This bound was later improved to cn4/3 by Spencer, Szemere´di andTrotter using a version of the Szemere´di-Trotter Theorem for unit circles[60]. A number of different proofs have been given, all providing differentproofs of the Szemere´di-Trotter Theorem for unit circles, but the bound hasnot been improved.In the same paper, Erdo˝s also introduced the distinct distances problemwhich asks for the minimum possible number g(n) of distinct distances be-tween n points in the plane. He gave the bounds cn1/2 ≤ g(n) ≤ cn/√log n.In this case the upper bound also comes from a suitably scaled portion ofan integer lattice and the lower bound comes from a simple counting ar-gument. Again, Erdo˝s conjectured that the true magnitude is close to theupper bound. Unlike the unit distance problem the best bound for thisproblem has been improved many times over the years. The progression ofthese results is given in Table 1.1. For an in-depth account of this progres-sion and a survey of the distinct distances and unit distance problems see[33] and [9].We will mention the near-optimal solution of this problem due to Guthand Katz [34]. They attained the lower bound cn/ log n which is very close tothe upper bound cn/√log n given by Erdo˝s. Before their proof the distinctdistances problem was reduced to an incidence problem in higher dimensionsby Elekes and Sharir using properties of rotations of the point set [22]. Guthand Katz were able to solve this problem using a number of powerful andingenious techniques. Their use of the polynomial ham-sandwich theoremof Stone and Tukey [61] to provide a well-behaved partitioning of the spacewas perhaps the most remarkable. Their proof shows the power of usingmethods from various fields for problems in combinatorial geometry.The unit distance and distinct distances problems are related in a verynice way. Specifically, a bound for the unit distance problem gives a boundfor the distinct distances problem as follows: suppose we have a point set of71.3. The Erdo˝s unit distance problemLower bound Author [Publication] Yearg(n) ≥ cn1/2 P. Erdo˝s [25] 1946g(n) ≥ cn2/3 L. Moser [50] 1952g(n) ≥ cn5/7 F.R.K. Chung [12] 1984g(n) ≥ cn4/5/ log n F.R.K. Chung, E. Szemere´di, 1992W.T. Trotter [13]g(n) ≥ cn4/5 L. Sze´kely [62] 1997g(n) ≥ cn6/7 J. Solymosi, C.D. Toth [59] 2001g(n) ≥ cn(4e/(5e−1))−ε G. Tardos [66] 2003g(n) ≥ cn((48−14e)/(55−16e))−ε N.H. Katz, G. Tardos [38] 2004g(n) ≥ cn/ log n L. Guth, N.H. Katz [34] 2010Table 1.1: The progression of lower bounds for the Erdo˝s distinct distancesproblem up to the near complete solution of Guth and Katz.size n with the minimum number, g(n), of distinct distances. There are(n2)pairs of points in total. So, by the pigeonhole principle some distance mustappear at least(n2)/g(n) times. In particular this tells us thatu(n) ≥1g(n)(n2)⇒ g(n) ≥1u(n)(n2).Thus if u(n) ≤ cn1+ε then g(n) ≥ c′n1−ε.The proof of the best upper bound for the unit distance problem usesthe Szemere´di-Trotter Theorem for unit circles. Unit circles are similar tolines in a certain topological sense. Notice that two lines intersect in atmost one point and two points uniquely define a line. Any collection ofcurves satisfying these properties are called pseudolines. For unit circles wehave similar properties. In particular, any two unit circles intersect in atmost two points and two points define at most two unit circles. By onlyconsidering the upper or lower halves of the circles the above properties oflines are satisfied and we get a collection of pseudolines. We choose theupper or lower halves according to which ones give us more incidences. Theremarkable thing about the proof of the Szemere´di-Trotter Theorem is thatit only uses the above properties of lines and so it also holds for pseudolines.So, for unit circles specifically, given a point set P of size n and a collectionof unit circles C of size m in the plane the number of point-circle incidencesis at most IU (P, C) ≤ C(m2/3n2/3 +m+ n).To prove the upper bound for the unit distance problem we consider n81.3. The Erdo˝s unit distance problem(a) A collection of pointsin the plane.(b) Unit circles centred atthe points.(c) Unit distances betweenthe points.Figure 1.3: A collection of points is given in (a). A unit circle is drawnaround each point in (b). The correspondence between unit distances andpoint-circle incidences is shown in (c).points in the plane and the n unit circles with the points as their centres.Note that two points have unit distance if each is on the unit circle centredat the other point. See Figure 1.3 for an example. So each unit distancecorresponds to two point-circle incidences. Thus by the Szemere´di-TrotterTheorem for unit circles the number of unit distances is at most Cn4/3.Notice that given a pair of points in the plane we get a distance vectorbetween them. This vector can be considered as a complex number and if thedistance between the points is one then the complex number has modulusone.Given a set of n points in the plane, the unit distance graph of the pointset is the graph with vertices the n points and edges the unit distances. Apath in this graph is call irredundant or nondegenerate if no subsum of thedistance vectors equal zero. More details of this will be given in Chapters 3and 4.We will be looking at the unit distance problem when the complex num-bers associated with the distance vectors come from a subgroup of C of lowrank. A subgroup Γ ⊂ C∗ has rank r (or just finite rank) if there exists afinitely generated subgroup Γ0 ⊂ Γ with r generators such that for everyx ∈ Γ there exists an integer k ≥ 0 such that xk ∈ Γ0. Note that the groupof roots of unity has rank 0 as every element of the group has finite order.We will use a corollary of the Subspace Theorem. More details of theSubspace Theorem will be given in the next section but for now we just focuson the corollary and its use in the unit distance problem. The corollarybounds the number of certain solutions of linear equations coming from a91.3. The Erdo˝s unit distance problemsubgroup of a field with finite rank. The bound depends on the rank of thesubgroup and the number of terms in the linear equation. This corollarywas due originally to Evertse, Schlickewei and Schmidt [30]. We will usea recent variant of this result of Amoroso and Viada [3] that gives, to ourknowledge, the best known bound.Suppose Γ is a subgroup of C∗ of finite rank r and a1, a2, . . . , ak ∈ C∗.A solution of the equationa1z1 + a2z2 + · · ·+ akzk = 1 (1.1)is called nondegenerate if no subsum of the left-hand side vanishes. That is∑j∈J ajzj 6= 0 for every nonempty J ⊂ {1, 2, . . . , k}. The corollary boundsthe number A(k, r) of nondegenerate solutions of this equation with zi ∈ Γa subgroup of C∗ of rank r. Specifically, A(k, r) ≤ (8k)4k4(k+kr+1).1.3.1 ResultsWe give bounds for two special cases of the unit distance problem and anumber of similar results where we consider rational distances and not justunit distances. For our first result we only consider unit distances withangle to the x-axis a rational multiple of pi. These distances correspond toroots of unity and so come from a multiplicative subgroup of C∗ of rank 0.We call the maximum number of these unit distances u1(n). We give otherresults dealing with rational distances with angle to the x-axis a rationalmultiple of pi. These results are similar to the first result but the boundsvary depending on how many points we allow on a line. Lastly we considerdistances coming from a multiplicative subgroup of C∗ of “low” rank. Werequire that the rank is at most c log n where n is the number of points. Wecall the maximum number of these unit distances u2(n).In the first case we get the boundscn log n ≤ u1(n) ≤ n1+7/√logn.The upper bound comes from an application of a result of Mann from 1965on the number of solutions of linear equations of roots of unity [44]. FromMann’s Theorem we get a corollary bounding the number of nontrivial so-lutions in roots of unity of a linear equation in k variables. The bounddepends only on k. The lower bound construction of Erdo˝s does not holdfor this case as the unit distances in the scaled integer lattice are not gen-erally roots of unity. The lower bound given comes from a modified versionof a construction of Erdo˝s and Purdy [27]. The construction is a projectionof a hypercube.101.3. The Erdo˝s unit distance problemFor the problems with rational distances the upper bounds also comefrom Mann’s Theorem and vary from n1+7/√logn to cn2 depending on howmany points we allow on a line. Near optimal lower bounds are given usinga similar construction to that of Erdo˝s and Purdy above. We were able toget these results by showing that Mann’s Theorem holds for sums of rationalmultiples of roots of unity.For our last problem concerning distances from a group with low rank,given ε > 0, we get the boundsn1+c/ log logn ≤ u2(n) ≤ n1+ε.The upper bound comes from the corollary of the Subspace Theorem. Herethe lower bound is the same as Erdo˝s’ construction as we show. This requiresa careful analysis of the lower bound construction. The fact that our resultworks for the best known lower bound shows its usefulness and suggests thatall maximal unit distance sets may have a special structure.Mann’s Theorem deals with linear equations of roots of unity and thecorollary of the Subspace Theorem deals with linear equations of elements ofa group of finite rank. So Mann’s Theorem is a special case of the corollaryand can be thought of as a starting point, at least from a combinatorialperspective, for the development of the Subspace Theorem.The idea of all the proofs is quite similar. We will only highlight theproofs for unit distances but the proofs for rational distances follow thesame lines. The proofs proceed as follows:1. consider the unit distance graph where we only include edges thatcorrespond to unit distances from the required group,2. count irredundant/nondegenerate paths of length k where k is to bedetermined,3. using simple degree arguments we get a lower bound for the numberof such paths between a pair of vertices,4. Mann’s Theorem or the corollary of the Subspace Theorem give us anupper bound on the number of such paths between the same pair ofvertices,5. putting these together and optimizing for k we get the stated bounds.Full details appear in Chapters 3 and 4.111.4. Combinatorial applications of the Subspace Theorem1.4 Combinatorial applications of the SubspaceTheoremA version of the Subspace Theorem was first proved by Schmidt in 1972[55]. We have already mentioned this theorem in the previous section withparticular emphasis on its corollary and its subsequent use for the unitdistance problem. It was a generalisation of the Thue-Siegel-Roth Theoremon the approximation of algebraic numbers to higher dimensions [54].The Subspace Theorem says that the solutions of linear equations in amultiplicative subgroup of a field of finite rank come from a finite numberof linear subspaces. Schmidt’s original theorem did not give a quantitativebound on the number of linear subspaces but just guaranteed finiteness.A quantitative version, along with the corollary mentioned in the previoussection, were subsequently given by Evertse, Schlickewei and Schmidt [30].The Subspace Theorem is a powerful tool in number theory. It hasappeared in various forms and been adapted and improved over time. Itsmore well known applications include diophantine approximation, resultsabout integral points on algebraic curves and the construction of transcen-dental numbers. But its usefulness extends beyond the realms of numbertheory. Other applications of the Subspace Theorem include linear recur-rence sequences and finite automata. The multitude of uses of the SubspaceTheorem are elegantly highlighted in the surveys of Bilu [8], Evertse andSchlickewei [29] and Corvaja and Zannier [16]. These surveys give manyproofs of results from number theory and algebraic geometry including thosementioned above.The proof of the Subspace Theorem is very deep and beyond the scope ofthis work. We plan to focus on its use as a tool for combinatorial problemswithout delving into the background of the theorem very much. We will,however, mention its origins and present two of its more well known appli-cations before proceeding to the combinatorial problems. The full detailsappear in Chapter 5.A linear recurrence sequence is a sequence where the first few terms aregiven explicitly and the remaining terms are given via a linear recurrencerelation. The Fibonacci numbers are probably the best known example of alinear recurrence sequence. The zero set of a linear recurrence sequence isthe set of terms in the sequence that equal zero.Given a set A of elements of a field we define the sum set and productset of A asA+A = {a+ b : a, b ∈ A}, and AA = {ab : a, b ∈ A}121.5. Layout of this documentrespectively. These sets and their relationship are well studied in com-binatorics and additive number theory. The idea behind the theory isthat addition and multiplication are somehow incompatible so if one ofthese sets is small then the other should be large. Note that the size ofthe sum set and product set are between |A| and |A|2. It was conjec-ture by Erdo˝s and Szemere´di that, given ε > 0, for any finite A ⊂ Z,|A + A| + |AA| ≥ |A|2−ε. The best known bound for this problem is dueto Solymosi with |A + A| + |AA| ≥ n4/3 − o(1) using an ingenious elemen-tary method involving a cartesian product [58]. This bound holds for realnumbers, not just integers, and a similar result has recently been given forcomplex numbers by Konyagin and Rudnev [40].1.4.1 ResultsFirst we give a few different formulations of the Subspace Theorem andstate the corollary mentioned above. Then we give two well known (non-combinatorial) applications. The first is an example of proving that a num-ber is transcendental. This involves considering the binary expansion ofthe number, assuming it is not transcendental and then using the SubspaceTheorem to show that it must then be rational, a contradiction. The secondexample shows that the zero set of certain special linear recurrence sequencesis finite. This involves considering the recurrence relation as a matrix andthen using properties of the characteristic polynomial to apply the corollaryof the Subspace Theorem.For the combinatorial applications, first we present a result of Changwhich states that if the product set is “very” small then the sum set is“very” large [10]. Specifically, if |AA| ≤ c|A| then |A+A| ≥ |A|2/2+O(|A|).Lastly, we give a bound for complex line configurations with few distinctintersections due to Chang and Solymosi [11].The main purpose of the chapter is to be an exposition of these resultsso that the methods may find more common use among discrete mathemati-cians.1.5 Layout of this documentIn Chapter 2 the extensions of the results of Elekes and Ro´nyai are given.The various extensions are stated in Section 2.1, the required background isgiven in Section 2.2, the proofs are given in Sections 2.3-2.4 and applicationsand lower bounds are given in Section 2.5.131.5. Layout of this documentIn Chapters 3–4 the special cases of the Erdo˝s unit distance problem aregiven. For the results using Mann’s Theorem, the statements of our upperbounds are given in Section 3.1, Mann’s result and its corollaries are given inSection 3.3, the proofs of the upper bounds are given in Section 3.4 and thelower bounds are given in Section 3.5. For the results using the SubspaceTheorem, the statement of our upper bound is given in Section 4.1, the proofof the upper bound is given in Section 4.2 and the analysis of Erdo˝s’ lowerbound is given in Section 4.3.In Chapter 5 an exposition of the Subspace Theorem and its combinato-rial applications is given. Background and various formulations and corol-laries of the Subspace Theorem are given in Section 5.1, two well knownapplications of the Subspace Theorem are given in Section 5.2 and the ap-plications of the Subspace Theorem to sum-product estimates and line con-figurations with few intersections are given in Section 5.3.Chapter 6 highlights the conclusions of this thesis and possible futurework. This includes the scope of the research and how it fits into the fieldand the limitations of the results and how they could be generalised orextended.14Chapter 2Extensions of a result ofElekes and Ro´nyai2.1 Introduction2.1.1 BackgroundWe are interested in polynomials on finite cartesian products, for instance ofthe form f(x, y) ∈ R[x, y] on A×B, with A,B ⊂ R and |A| = |B| = n. Wewill focus on the question of how small the image f(A,B) can be in termsof n.For two basic examples, x + y and xy, the image can be as small ascn, if A and B are chosen appropriately. For f(x, y) = x + y one can takeA = B = [1, n] (or any other arithmetic progression of length n), so thatf(A,B) = A + B = [2, 2n]; for f(x, y) = xy one can take a geometricprogression like A = B = {21, 22, . . . , 2n}, so that f(A,B) = A · B ={22, 23, . . . , 22n}. Similar small images can be obtained for polynomials ofthe form f(x, y) = g(k(x) + l(y)), for nonconstant polynomials g, k, l, bytaking A so that k(A) ⊂ [1, n], and B so that l(B) ⊂ [1, n]. A similar ideaworks for f(x, y) = g(k(x) · l(y)).For convenience, we will formulate the problem slightly differently: weconsider the surface z = f(x, y) in R3 and its intersection with a cartesianproduct A × B × C, with |A| = |B| = |C| = n. Then the image of f is‘small’ if and only if that intersection is ‘large’; for instance, z = x+ y hasintersection with [1, n]3 of size at least 14n2.In 2000, Elekes and Ro´nyai [21] proved the following converse of theabove observations.Theorem 2.1.1 (Elekes-Ro´nyai Theorem). For every c > 0 and positiveinteger d there exists n0 = n0(c, d) with the following property.Let f(x, y) be a polynomial of degree d in R[x, y] such that for an n > n0the graph z = f(x, y) contains cn2 points of A×B ×C, where A,B,C ⊂ R152.1. Introductionhave size n. Then eitherf(x, y) = g(k(x) + l(y)), or f(x, y) = g(k(x) · l(y)),where g, k, l ∈ R[t].In fact, they proved that the same is true for rational functions, if oneallows a third special form f(x, y) = g((k(x) + l(y))/(1− k(x)l(y))). Elekesand Szabo´ [23, 24] were able to extend this theorem to implicit surfacesF (x, y, z) = 0, and also showed that the surface need only contain n2−γpoints of the cartesian product for the conclusion to hold, for some absolute‘gap’ γ > 0.Elekes and Ro´nyai used their result to prove a famous conjecture ofPurdy. It says that given two lines in R2 and n points on each line, if thenumber of distinct distances between pairs of points, one on each line, is cnfor some c > 0, then the lines are parallel or orthogonal. Elekes [19] alsoproved a ‘gap version’, only requiring the number of distances to be less thancn5/4. For details and a proof of a variation of Purdy’s conjecture, using ourresults below, see Section 2.5.2.See [20, 46, 47] for more details and some related problems.2.1.2 ResultsIn this paper we prove a number of extensions of Theorem 2.1.1. We extendthe result to one dimension higher, to asymmetric cartesian products, and toboth at the same time. The proofs are based on the proof of Theorem 2.1.1by Elekes and Ro´nyai.First we consider a less symmetric cartesian product.Theorem 2.1.2. For every c > 0 and positive integer d there exist n0 =n0(c, d) and c˜ = c˜(c, d) with the following property.Let f(x, y) be a polynomial of degree d in R[x, y] such that for an n > n0 thegraph z = f(x, y) contains cn11/6 points of A × B × C, where A,B,C ⊂ Rand |A| = n, |B| = c˜n5/6, and |C| = n. Then eitherf(x, y) = g(k(x) + l(y)), or f(x, y) = g(k(x) · l(y)),where g, k, l ∈ R[t].Using a recent result of Amirkhanyan, Bush, Croot and Pryby [2], re-garding a conjecture of Solymosi about the number of lines in general posi-tion that can contain cn points of an n× n cartesian product (see Theorem162.1. Introduction2.2.6), we get the following theorem. we note that only Theorems 2.1.3,2.1.6, and 2.5.2 depend on it. Theorems 2.1.2 and 2.1.5 instead use ourLemma 2.2.4, a similar but weaker statement about lines on cartesian prod-ucts, which we prove using the same technique as our other theorems.Theorem 2.1.3. For every c > 0 and positive integer d there exists n0 =n0(c, d) with the following property.Let f(x, y) be a polynomial of degree d in R[x, y] such that for an n > n0 thegraph z = f(x, y) contains cn3/2+ε points of A×B ×C, where A,B,C ⊂ Rand |A| = n, |B| = n1/2+ε with ε > 0, and |C| = n. Then eitherf(x, y) = g(k(x) + l(y)), or f(x, y) = g(k(x) · l(y)),where g, k, l ∈ R[t].We also extend the Elekes-Ro´nyai Theorem to cartesian products of onedimension higher, i.e. to polynomials with one more variable.Theorem 2.1.4. For every c > 0 and positive integer d there exists n0 =n0(c, d) with the following property.Let f(x, y, z) be a polynomial of degree d in R[x, y, z] such that for an n > n0the graph w = f(x, y, z) contains cn3 points of A × B × C × D, whereA,B,C,D ⊂ R have size n each. Then eitherf(x, y, z) = g(k(x) + l(y) +m(z)), or f(x, y, z) = g(k(x) · l(y) ·m(z)),where g, k, l,m ∈ R[t].We can also prove a higher-dimensional version with a less symmetriccartesian product.Theorem 2.1.5. For every c > 0 and positive integer d there exists n0 =n0(c, d) with the following property.Let f(x, y, z) be a polynomial of degree d in R[x, y, z] such that for an n > n0the graph w = f(x, y, z) contains cn8/3+2ε points of A× B × C ×D, whereA,B,C,D ⊂ R and |A| = n, |B| = |C| = n5/6+ε with ε > 0, and |D| = n.Then eitherf(x, y, z) = g(k(x) + l(y) +m(z)), or f(x, y, z) = g(k(x) · l(y) ·m(z)),where g, k, l,m ∈ R[t].And using the previously mentioned result of Amirkhanyan et al. we getthe following:172.1. IntroductionTheorem 2.1.6. Given c > 0 and d a positive integer there exists n0 =n0(c, d) with the following property.Let f(x, y, z) be a polynomial of degree d in R[x, y, z] such that for an n > n0the graph w = f(x, y, z) contains cn2+2ε points of A × B × C × D, whereA,B,C,D ⊂ R and |A| = n, |B| = |C| = n1/2+ε with ε > 0, and |D| = n.Then eitherf(x, y, z) = g(k(x) + l(y) +m(z)), or f(x, y, z) = g(k(x) · l(y) ·m(z)),where g, k, l,m ∈ R[t].In Section 2.5.3 we will give an example of a polynomial f(x, y, z) whosegraph contains cn2 points of A×B×C×D, where |A| = |D| = n and |B| =|C| = c′n1/2, but f does not have the required additive or multiplicativeform of Theorem 2.1.6. This shows that Theorem 2.1.6 is near-optimal.Note that as for the two-variable case, the converses of Theorems 2.1.4–2.1.6 all hold for some appropriately chosen cartesian products. Specifically,if f(x, y, z) = g(k(x)+l(y)+m(z)), one can choose A, B, and C so that k(x),l(y), and m(z) have values in the same arithmetic progression. A similarconstruction works for the product case.Theorems 2.1.1, 2.1.2, 2.1.4 and 2.1.5 would all hold if we consider func-tions over C instead of R, but we will restrict ourselves to R here. Theproofs for three-variable polynomials could be extended to |B| 6= |C|, atsome cost to the exponents. It also seems possible to generalize our proofsto polynomials with even more variables.In Section 2.1.3 we give a short outline of the proof of the Elekes-Ro´nyaiTheorem, which provides a template for our subsequent proofs. Section 2.2contains a number of concepts and results required throughout our proofs.In Section 2.3 we give the proofs of Theorems 2.1.2 and 2.1.3, while Section2.4 contains the proofs of Theorems 2.1.4, 2.1.5, and 2.1.6. In Section 2.5we describe a method of Elekes and Ro´nyai for checking whether a functionhas such an additive or multiplicative form. We also give an extension ofthe conjecture of Purdy, and an example showing the near-optimality ofTheorem 2.1.6.2.1.3 Outline of proofsThe following is an outline of the proof that Elekes and Ro´nyai gave in [21]of Theorem 2.1.1. Our theorems are obtained by adjusting this proof tothree-variable f , and by using improved Line Lemmas (see Section 2.2.2) toget the asymmetric versions. All functions below are polynomials, and we182.1. Introductionrepeatedly recycle the positive constant c. We call a curve k-rich on a set ifit contains at least k points from that set.We split up the surface z = f(x, y) into the n curvesz = fi(x) = f(x, yi)with yi ∈ B. We wish to decompose a cn-sized subset of the fi asfi(x) = (p ◦ ϕi ◦ k)(x) = p(aik(x) + bi),where ϕi is linear and p and k are independent of i.Then the cn lines u = ϕi(t) = ait+bi will be cn-rich on an n×n cartesianproduct. For such sets of lines we have various lemmas (2.2.3–2.2.7) that saythat a cn-sized subset of them must be all parallel or all concurrent (havethe same intersection point).Given cn such decompositions with the lines ϕi all parallel, we can writef(x, yi) = p(ak(x) + bi), and then conclude by an algebraic argument thatthere exists an l(y) such that f(x, y) = p(k(x) + l(y)). If cn of the lines areconcurrent, we can write f(x, yi) = p(ai · (k(x)+ b)), and then conclude thatf(x, y) = p(k(x) · l(y)).To find the above decomposition of the fi, we first remove their commoninner functions (polynomials µ such that fi = λi ◦ µ) up to linear equiva-lence. We can do this because the number of decompositions up to linearequivalence of a polynomial of degree d depends only on d (Lemma 2.2.10),so for large enough n there must be a cn-sized subset of the fi that all havethe same inner function of maximal degree. This maximal inner functionwill be the k above, and we remove it by writing fi = f̂i ◦ k. Then we havea subset of f̂i with the property that if f̂i = µi ◦ λ and f̂j = µj ◦ λ, then λmust be linear.Now we combine pairs f̂i, f̂j into new curvesγij(t) = (f̂i(t), f̂j(t)).We observe that these γij are cn-rich on an n × n cartesian product, andthat we have cn2 of them. But by a theorem of Pach and Sharir (Lemma2.2.2), such a set of rich curves can have size at most c′n.This is not a contradiction: many of these γij may coincide as sets inR2. But if for instance γij and γi′j′ coincide, then by some algebra (Lemma2.2.12) they must be reparametrizations of the same curve (p(t), q(t)), whichmeans that we can writef̂i = p ◦ ϕ, f̂j = q ◦ ϕ,f̂i′ = p ◦ φ, f̂j′ = q ◦ φ.192.2. PreliminariesWe take one of these common decompositions, say with ϕ. Since we alreadyremoved all nonlinear common inner polynomials, ϕ must be linear. If wehave enough such decompositions, we can ensure that they all have the formfi = p ◦ ϕi for the same p. This gives us the desired decompositionsfi = f̂i ◦ k = p ◦ ϕi ◦ k.2.2 Preliminaries2.2.1 Discrete geometryWe will make frequent use of the following well-known theorem, first provedin [64]. We say that a line (or any other curve) is k-rich on a point set P ifit contains at least k points of P.Theorem 2.2.1 (Szemere´di-Trotter Theorem). There exists a positive con-stant CST > 0 such that given a set P of n points in R2, the number of linesk-rich on P is at most CST · (n2/k3 + n/k).This theorem was generalized by Pach and Sharir [52, 53] to continuousreal planar curves without self-intersection. We will use the following corol-lary for algebraic curves, which follows quite easily since algebraic curves(of bounded degree) can be split up into a small number (depending on thedegree) of curves without self-intersection. For details see Elekes and Ro´nyai[21].Lemma 2.2.2 (Curve Lemma). Given c > 0 and a positive integer d, thereexist CCL = CCL(c, d) and n0 = n0(c, d) such that the following holds.Given m distinct irreducible real algebraic curves of degree ≤ d that arecn-rich on A, where A ⊂ R2 and |A| ≤ n2, then for all n > n0 we havem < CCL · n.2.2.2 Line lemmasIn the proof of Theorem 2.1.1 by Elekes and Ro´nyai, an important ingredientwas the following result of Elekes [18] about lines containing many pointsfrom a cartesian product. We call a set of lines concurrent if they all havethe same intersection point.Lemma 2.2.3 (Line Lemma). Suppose A,B ⊂ R and |A| = |B| = n. Forall c1, c2 > 0 there exists CLL > 0, independent of n, such that if CLLn linesin R2 are c1n-rich on A × B, then at least c2n of them must be parallel orconcurrent.202.2. PreliminariesWe prove a generalization that will be crucial in Section 2.3. The proofis at the end of this section, and is modelled on that of Elekes.Lemma 2.2.4 (Generalized Line Lemma). Suppose A,B ⊂ R and |A| =|B| = n. For all c1, c2 > 0, and β ≥ 0 there exists CGLL > 0, independent ofn, such that if m lines in R2 are c1n-rich on A×B, with no c2nβ concurrentor parallel, thenm < CGLL · n2/3+β/3.A collection of lines in R2 is said to be in general position if no two linesare parallel and no three lines are concurrent. The second author conjecturedthe following extension of the above result. For details see [20].Conjecture 2.2.5. Suppose A,B ⊂ R and |A| = |B| = n. For all c > 0there exists CS > 0 such that if m lines in general position are cn-rich onA×B then m < CS.The following result of Amirkhanyan et al. is related to the above con-jecture [2].Theorem 2.2.6. For every ε > 0 there exists δ > 0 such that given nεlines in R2 in general position, they cannot all be n1−δ-rich on A×B, where|A| = |B| = n.Thus if a collection of lines L in general position is cn-rich on A×B then|L| < nε for any ε > 0. We will use it in the form of the following corollary.Corollary 2.2.7. If m lines in R2 are cn-rich on A×B, with |A| = |B| = n,such that no p are parallel and no q are concurrent, thenm ≤ (p+ q)nεfor every ε > 0.Proof. We show that the set of lines contains at least k =√m/√2(p+ q)lines in general position.We pick any line, and then successively choose a new line that is notparallel to any of the previously chosen lines, and does not go through theintersection point of any pair of them. If we have chosen k such lines, thenthere are k slopes we may not choose, which excludes less than pk lines.And there are at most(k2)intersection points that we must avoid, so sincethere are less than q lines concurrent at a point, this excludes less than q(k2)lines. Hence we can continue in this way at least until m ≤ q(k2)+ pk + k.212.2. PreliminariesThen we also have m ≤ (p + q)k2, so we can get k ≥√m/√p+ q lines ingeneral position. These lines are cn-rich on A× B. Thus k ≤ nε′for everyε′ > 0. This gives m ≤ (p+ q)nε for every ε > 0.We give the proof of Lemma 2.2.4 below. We will use the dual of atheorem of Beck [7], which roughly states that given a collection of points,either ‘many’ of the points are on the same line, or pairs of the pointsdetermine ‘many’ distinct lines.Theorem 2.2.8 (Dual of Beck’s Theorem). There exists CBT > 0 suchthat, given N lines in R2, either CBTN lines are concurrent or the linesdetermine CBTN2 distinct pairwise intersection points.Proof of Lemma 2.2.4. Let L be the set of lines and write |L| = m = cnα.For every pair (`i, `j) ∈ L2 we define the linear functions γij = `i ◦ `−1j andΓij = `−1j ◦ `i.First we will prove that large subsets of the γij and Γij are also rich.Consider the tripartite graph H with vertex sets A ∪ L ∪ B. Given a ∈ Aand ` ∈ L, (`, a) is an edge in H if `(a) ∈ B. Similarly, given ` ∈ L andb ∈ B, (`, b) is an edge if `−1(b) ∈ A. Given ` ∈ L, let degA(`) be the numberof edges between ` and A and degB(`) the number of edges between l andB. Since the lines in L are c1n-rich on A × B, we have degA(`) ≥ c1n anddegB(`) ≥ c1n for each ` ∈ L. Thus we have at least cc1n1+α edges betweenA and L and at least cc1n1+α edges between B and L.We will count cycles of length four in H with one vertex in A and onevertex in B. Every such C4 gives a point in B×B on y = γij(x) and a pointin A× A on y = Γij(x) for some pair (i, j). The number of paths of lengthtwo with one endpoint in A and the other in B is at least#P2 =∑`∈LdegA(`) degB(`) ≥ c21n2+α.Let pa,b be the number of paths of length two between a ∈ A and b ∈ B.Then#P2 =∑a∈A,b∈Bpa,b.Now, by Jensen’s Inequality, the number of C4’s we are looking for is#C4 =∑a∈A,b∈B(pa,b2)≥ |A×B|(#P2/|A×B|2)≥c41n2+2α4.222.2. PreliminariesSuppose there are fewer than (c41/8)n2α pairs (`i, `j) ∈ L2 with at least(c41/8)n2 C4’s between them. Then H would have fewer than (c41/4)n2+2αC4’s, a contradiction. Thus, setting c3 = c41/8, we have at least c3n2α pairs(i, j) for which γij and Γij are c3n-rich on B ×B and A×A respectively.Next we define a different graph G′ and analyze it. The vertex sets ofG′ consist of those γij that are c3n-rich on B × B and those Γi′j′ that arec3n-rich on A×A. If γij and γi′j′ coincide as point sets, we consider them asthe same vertex. Similarly we identify any coinciding Γij and Γi′j′ , but wedo not identify γij and Γi′j′ should they coincide. We place an edge betweenγij and Γij for each pair (i, j), which means the graph is bipartite.The graph may contain multiple edges, if we have `i, `j , `i′ , `j′ ∈ L suchthat both γij = γi′j′ and Γij = Γi′j′ . But this implies that the four lines areconcurrent: If `i and `j intersect in (u, v), then v = `i ◦ `−1j (v) = `i′ ◦ `−1j′ (v)and u = `−1j ◦ `i(u) = `−1j′ ◦ `i′(u), so (u, v) is also the intersection point of`i′ and `j′ .But with Beck’s Theorem we can get a subgraph without multiple edges.We will assume that β < α, and check it at the end of the proof. Then fewerthan c2nβ < CBT cnα = CBT |L| lines are concurrent, so by Theorem 2.2.8,the lines determine CBTn2α distinct intersection points. The correspondinglines span a subgraph G′′ without multiple edges, and at least CBTn2α edges.By the Szemere´di-Trotter Theorem, since all vertices are c3n-rich lines,the number of vertices is at most ≤ c4n for some constant c4 > 0. Theaverage degree in G′′ is then ≥ (CBT /c4)n2α−1. Thus G′′ contains a con-nected component H containing at least (CBT /c4)n2α−1 vertices and at least12(CBT /c4)2n4α−2 edges.Note that each γij and Γij have the same slope, so every vertex in H is aline with the same slope. If there are more than cc2nα+β edges in H then wewould have vertices γij1 , γij2 , . . . , γijt in this component with t ≥ c2nβ. Thisimplies that the lines `j1 , `j2 , . . . , `jt are all parallel, which is a contradiction.So we have a contradiction unlessC2BT2c24n4α−2 < cc2nα+β.From this we get that α ≤ 2/3+β/3, if we choose CGLL = c > C2BT /(2c2c24).2.2.3 Algebra and graph theoryIn the proofs of our higher-dimensional versions of the Elekes-Ro´nyai Theo-rem, we will need the following generalization of the fact that if a degree-d232.2. Preliminariespolynomial of one variable has d + 1 or more roots, then the polynomial isidentically zero. It is a special case of the Schwartz-Zippel lemma (see forinstance [36], Lemma 16.3).Lemma 2.2.9 (Vanishing Lemma). Let K be a field, F (y, z) ∈ K[y, z] withdegF = d, and B,C ⊂ K with |B| = |C| = m.If F (yi, zj) = 0 for 2dm of the pairs (yi, zj) ∈ B × C, then F (y, z) = 0.We will also need the following three algebraic lemmas, which appearwith proofs in [21]. Let K be a field. We call two decompositions f(x) =ϕ1(ψ1(x)) and f(x) = ϕ2(ψ2(x)) of a polynomial f ∈ K[x] into polynomialsfrom K[x] equivalent if ψ1(t) = aψ2(t) + b for some a, b ∈ K.Lemma 2.2.10. Let K be a field. Then no f ∈ K[x] can have more than2d non-equivalent decompositions, where d = deg f .Lemma 2.2.11.1. Let E be a field, ϕ ∈ E[x] a polynomial of degree d > 0. Then everyF ∈ E[x] can be written in the formF = a0 + a1x+ · · ·+ ad−1xd−1,where ai ∈ E(ϕ), in a unique way.2. Suppose further that E = L(y) is a rational function field over somefield L, and ϕ ∈ L[x]. Let m be the degree of F in y. Then the degreeof ai in y is at most m(d + 1). (Here ai is viewed as a polynomial ofϕ and y over L.)Lemma 2.2.12 (Reparametrization Lemma). Suppose that two parametriccurves (f1(t), g1(t)) and (f2(t), g2(t)) coincide as sets, with fi, gi ∈ K[t] fora field K. Then there are p, q, ϕ1, ϕ2 ∈ K[t] such thatf1 = p ◦ ϕ1, g1 = q ◦ ϕ1,f2 = p ◦ ϕ2, g2 = q ◦ ϕ2.Finally, we need the following graph-theoretic lemma, also proved in [21].Lemma 2.2.13 (Graph Lemma). For every c and k there is a CGL =CGL(c, k) with the following property.If a graph has N vertices and cN2 edges, and the edges are colored so thatat most k colors meet at each vertex, then it has a monochromatic subgraphwith CGLN2 edges.242.3. Proof of Theorems 2.1.2 and 2.1.32.3 Proof of Theorems 2.1.2 and 2.1.3Suppose z = f(x, y) contains cnα+1 points of A×B×C, where |A| = |C| = nand |B| = c˜nα; c˜ and α will be determined later. Throughout we will used = deg f . All functions will be polynomials.2.3.1 Constructing f̂iFor each of the c˜nα yi ∈ B definefi(x) = f(x, yi).Then each fi is a polynomial in R[x] of degree at most d.Lemma 2.3.1. If at least d+ 1 of the fi are identical, then f(x, y) = q(x).In particular, the conclusion of Theorems 2.1.2 and 2.1.3 holds.Proof. Suppose that fi(x) = q(x) at least d + 1 times. Then consideringF (y) = f(x, y)− q(x) as a polynomial in y over the field R(x), we have F (y)vanishing d+ 1 times, so F (y) = 0 identically.Assumption: Throughout the rest of this section we will assume that atmost d of the fi are identical.Let c1 = min(c/2, c˜/2). Then at least c1nα of the fi are c1n-rich onA × C. Otherwise z = f(x, y) would contain fewer than cnα+1 points ofA×B × C.We construct a graph G with the c1nα c1n-rich fi as vertices and edgeset E consisting of all pairs (fi, fj).Lemma 2.3.2. There is a subgraph of G with edge set Ê ⊂ E of size|Ê| ≥ c2n2α, such that the following holds. There is a polynomial k(x) suchthat for all (fi, fj) ∈ Ê we can writefi = f̂i ◦ k,fj = f̂j ◦ k,and f̂i and f̂j share no non-linear common inner function.The f̂i are also c1n-rich on k(A)× C.252.3. Proof of Theorems 2.1.2 and 2.1.3Proof. Color each edge (fi, fj) of G with the equivalence class of a commoninner function ϕ of maximum degree, i.e. fi(x) = g(ϕ(x)) and fj(x) =h(ϕ(x)), and no such ϕ of higher degree exists; two such inner functionsϕ, φ are equivalent if φ(x) = aϕ(x) + b.By Lemma 2.2.10, at every vertex there are at most 2d colors, so by theGraph Lemma 2.2.13, with N = c1nα, there is a monochromatic subgraphwith CGLN2 = CGLc21n2α edges. We take Ê to be the edge set of thissubgraph. This means that all the fi involved in this subgraph have acommon inner function k(x) (actually up to equivalence, but by modifyingthe f̂i that is easily overcome), and no pair corresponding to an edge of Êhas a common inner function of higher degree. That allows us to define thef̂i as in the theorem; they must be rich since otherwise the fi could not berich.2.3.2 Constructing γijFor the c2n2α pairs f̂i, f̂j for which (fi, fj) ∈ Ê, we construct the curvesγij(t) =(f̂i(t), f̂j(t)).Lemma 2.3.3.1. At least c3n2α γij are c3n-rich on C × C.2. Each γij is an irreducible algebraic curve of degree at most d2.Proof. 1. We define a bipartite graph with vertex set k(A)∪{f̂i}, and weconnect t ∈ k(A) with f̂i if f̂i(t) ∈ C. Since |Ê| ≥ c2n2α, the numberof f̂i is at least√c2nα, each of them c2n-rich, so the bipartite graphhas m ≥ c3/22 nα+1 edges. We count the paths of length two betweendifferent f̂i’s, using the fact that k(A) ≤ n:#P2 =∑t∈k(A)(deg(t)2)≥ |k(A)|(m/|k(A)|2)≥ c′n2α+1.Hence at least c′′n2α pairs (f̂i, f̂j) share c′′n common neighbors t inthis graph. In other words, c′′n2α of the γij have a point in C ×C forc′′n different t.It is possible that different t give the same point γij(t), so these γijcould have fewer than c′′n points in C×C. However, because deg f̂i ≤d, this can happen for at most d different t at a time, so each γij willcertainly be (c′′/d)n-rich. Setting c3 = c′′/d we are done.262.3. Proof of Theorems 2.1.2 and 2.1.32. We require the notion of the resultant of two polynomials; for proofs ofthe following facts see [48]. Let R(x, y) be the resultant with respectto t (so considering x, y as coefficients) of the two polynomials x− f̂i(t)and y − f̂j(t). This is a polynomial of degree ≤ d2 with the propertythat R(x, y) = 0 if and only if there is a t such that x = f̂i(t) andy = f̂j(t); in other words, γij is the algebraic curve R(x, y) = 0. ByTheorem 1 in [48], R(x, y) is a power of an irreducible polynomial,which means that the curve γij defined by it is irreducible.2.3.3 Decomposing f̂iLemma 2.3.4. There is a subset S of c′n2α−1 of the γij that all coincideas point sets, and such that the set T of f̂i occurring in the first coordinateof a γij ∈ S has size c4n2α−1.Proof. Since the γij are irreducible and have degree ≤ d2, we can apply theCurve Lemma 2.2.2. Thus there exists n0 such that for n > n0, there can beat most CCLn distinct c3n-rich curves on C × C, so c3n2α/CCLn = c′n2α−1of them must coincide.Set c4 = c′/d2. If fewer than c4n2α−1 of the f̂i occurred among thesecoinciding γij , then some f̂i would have to occur at least d+ 1 times, say inthe first coordinate. But if (f̂i, f̂j) and (f̂i, f̂j′) coincide, then we must havef̂j = f̂j′ . So we would have d + 1 of the f̂i coinciding, hence also d + 1 ofthe fi, contradicting our Assumption after Lemma 2.3.1.Lemma 2.3.5. There are c4n2α−1 fi withfi(x) = p(aik(x) + bi)where ai, bi ∈ R and p ∈ R[x].Proof. By the Reparametrization Lemma 2.2.12, for each coinciding pair ofcurves γij and γi′j′ from S, we can find p, ϕi, and ϕi′ such thatf̂i = p ◦ ϕi and f̂i′ = p ◦ ϕi′ .Hence we have such decompositions for each pair of the f̂i ∈ T .The f̂i were constructed so that any pair corresponding to an edge ofÊ has no nonlinear common inner function. That implies that the ϕi arelinear, hence invertible, which allows us to assume that all f̂i ∈ T can bedecomposed using the same p. Indeed, if f̂i = p ◦ϕi = q ◦φi and f̂j = q ◦φj ,272.3. Proof of Theorems 2.1.2 and 2.1.3then q = p◦ (ϕi ◦φ−1i ), so we can write f̂j = p◦ (ϕi ◦φ−1i ◦φj); by repeatedlymodifying the ϕi this way we can reach all f̂k ∈ T .Write ϕi(t) = ait + bi; then for the c4n2α−1 fi = f̂i ◦ k with f̂i ∈ T wehave fi = p ◦ ϕi ◦ k.2.3.4 Proof of Theorem 2.1.2At this point we will apply the Generalized Line Lemma 2.2.4 with β = 0to obtain Theorem 2.1.2. Then we need 2α− 1 = 2/3, so we set α = 5/6.Note that the c4n2/3 lines u = ϕi(t) = ait + bi live on k(A) × p−1(C),which is essentially an n× n cartesian product (both sets might be smallerthan n, but we can just add arbitrary points to fill them out). They arec1n-rich there, since otherwise the fi couldn’t be c1n-rich.We conclude that either d+ 1 of the lines u = ϕi(t) are parallel, or d+ 1are concurrent. Otherwise, by Lemma 2.2.4 with β = 0 there would befewer than CGLLn2/3 lines. But we can take c˜ in Theorem 2.1.2 to be largeenough so that c4 > CGLL. Indeed, one can easily check that each ci was anincreasing unbounded function of ci−1.By Lemma 2.3.6 below, if d+ 1 of the lines are parallel, then f has theadditive form f(x, y) = p(k(x) + l(y)). By Lemma 2.3.7 below, if d + 1of the lines are concurrent, then f has the multiplicative form f(x, y) =p(k(x) · l(y)). That finishes the proof of Theorem 2.1.2.2.3.5 Proof of Theorem 2.1.3We will now use Corollary 2.2.7, instead of Lemma 2.2.4 as above, whichwill result in Theorem 2.1.3.We start with α = 1/2 + ε. Then we end up with c4n2α−1 = c4n2ε linesu = ait + bi which are c1n-rich on an n × n cartesian product. Certainlyc4n2ε > 2(d+ 1)nε′for some ε′ > 0, so by Corollary 2.2.7 with p = q = d+ 1either d+ 1 of the lines are parallel or d+ 1 are concurrent.By Lemma 2.3.6 below, the parallel case would give the additive form forf , and Lemma 2.3.7 below, the concurrent case would give the multiplicativeform for f . That finishes the proof of Theorem 2.1.3.2.3.6 The parallel caseLemma 2.3.6. If d+1 of the lines ϕi are parallel, then there is a polynomiall(y) such that f(x, y) = p(k(x) + l(y)).282.3. Proof of Theorems 2.1.2 and 2.1.3Proof. The lines can be written as ϕi(t) = at + bi, so (replacing k by k/a)we can write fi(x) = p(k(x)+bi), for d+1 different fi. We use the followingtwo polynomial expansions of fi(x) = f(x, yi) = p(k(x) + bi):N∑l=0vl · (k(x) + bi)l =N∑m=0wm(yi) · k(x)m.The first is immediate from p(k(x) + bi); the second requires a little morethought.By Lemma 2.2.11, there is a unique expansion of the polynomial f of theform f(x, y) =∑D−1l=0 cl(k(x), y)xl, where D = deg k. By the same lemma,we have a unique expansion fi(x) =∑D−1l=0 dl(k(x))xl, so that we haveD−1∑l=0cl(k(x), yi)xl =D−1∑l=0dl(k(x))xl ⇒ cl(k(x), yi) = dl(k(x)).But since fi(x) = p(k(x) + bi), uniqueness implies that dl = 0 for l > 0,hence cl(k(x), yi) = 0 for l > 0. Since we have this for d + 1 different i, itfollows that cl(k(x), y) = 0 for l > 0, so f(x, y) = c0(k(x), y), which meansthere is an expansion f(x, y) =∑wm(y)k(x)m. Now plugging in y = yigives the required expansion.Comparing the coefficients of k(x)N−1 in the two expansions above, wegetvN−1 + (N − 1)vNbi = wN−1(yi),which implies that bi = 1(N−1)vN (wN−1(yi) − vN−1). If we now define thepolynomiall(y) =1(N − 1)vN(wN−1(y)− vN−1),we have that for d+ 1 of the yi (note that vl and wm do not depend on thechoice of yi)f(x, yi) = p(k(x) + l(yi)).Since the degree of f is d, this implies that f(x, y) = p(k(x) + l(y)).2.3.7 The concurrent caseLemma 2.3.7. If d+ 1 of the lines ϕi are concurrent, then there are poly-nomials P (t), K(x) and L(y) such thatf(x, y) = P (K(x) · L(y)).292.4. Proof of Theorems 2.1.4, 2.1.5, and 2.1.6Proof. The lines can be written as ϕi(t) = ait + b, so (replacing p(x) byp(x− b)) we can write fi(x) = p(ai · k(x)), for d + 1 different fi. We againuse two polynomial expansions of fi(x) = f(x, yi) = p(ai · k(x)):N∑l=0vl · (ai · k(x))l =N∑m=0wm(yi) · k(x)m.Both are obtained in the same way as in the proof of Lemma 2.3.6.We cannot proceed exactly as before, since ai might occur here onlywith exponents, and we cannot take a root of a polynomial. But we canwork around that as follows. Define M to be the greatest common divisorof all exponents m for which wm 6= 0 in the second expansion; then we canwrite M as an integer linear combination of these m, say M =∑µmm.Comparing the coefficients of any k(x)m with wm 6= 0 in the two expansionsabove, we getami =1vmwm(yi),which tells us thataMi =N∏m=0(ami )µm = L(yi),where L(y) is a rational function.If we define P (s) = p(s1/M ), or equivalently P (tM ) = p(t), then thedefinition of M gives that P (s) is a polynomial. We also define K(x) =kM (x). ThenP (K(x) · L(yi)) = P (kM (x) · aMi ) = p(k(x) · ai) = f(x, yi).Since we have this for d + 1 of the yi, we get that f(x, y) = P (K(x)L(y)).This also tells us that L(y) is in fact a polynomial, since otherwise f(x, y)could not be one.2.4 Proof of Theorems 2.1.4, 2.1.5, and 2.1.6Suppose w = f(x, y, z) contains cn1+2α points of A×B ×C ×D and |B| =|C| = nα. For Theorem 2.1.4 we have α = 1; for the other two theorems wewill determine the right choice of α later. Throughout we will use d = deg f .All functions will be polynomials. We will shorten or omit several of theproofs, because they are very similar to those in Section 2.3.302.4. Proof of Theorems 2.1.4, 2.1.5, and 2.1.62.4.1 Constructing f̂ijFor each of the n2α points (yi, zj) ∈ B × C, we cut a fibre out of the solid:w = fij(x) = f(x, yi, zj).Lemma 2.4.1. If at least 2dnα of the fij are identical, then f(x, y, z) =q(x).In particular, the conclusion of Theorems 2.1.4, 2.1.5, and 2.1.6 holds.Proof. Suppose that fij(x) = q(x) at least 2dnα times. Then for F (y, z) =f(x, y, z)− q(x) and K = R(x), the Vanishing Lemma 2.2.9 with b = c = nαgives F (y, z) = 0.Assumption: Throughout the rest of this proof we will assume that fewerthan 2dnα of the fij are identical.Let c1 = c/2. Then at least c1n2α of the fij are c1n-rich on A × D.Otherwise w = f(x, y, z) would contain fewer than cn1+2α points of A×B×C ×D.We construct a graph G with the c1n2α fij as vertices and edge set Econsisting of the pairs (fij , fi′j′).Lemma 2.4.2. There is a subgraph of G with edge set Ê ⊂ E of size|Ê| ≥ c2n4α, such that the following holds. There is a polynomial k(x) suchthat for all (fij , fi′j′) ∈ Ê we can writefij = f̂ij ◦ k,fi′j′ = f̂i′j′ ◦ k,and f̂ij and f̂i′j′ share no non-linear inner function.The f̂ij are also c2n-rich on k(A)×D.2.4.2 Constructing γiji′j′For the c2n4α pairs f̂ij , f̂i′j′ for which (fij , fi′j′) ∈ Ê we construct the curvesγ̂iji′j′(t) =(f̂ij(t), f̂i′j′(t)),Lemma 2.4.3.1. At least c3n4α of the γiji′j′ are c3n-rich on D ×D.312.4. Proof of Theorems 2.1.4, 2.1.5, and 2.1.62. Each γiji′j′ is an irreducible algebraic curve of degree at most d2.Proof. We omit the proof of the second part of the lemma as it is provedin the same way as the second part of Lemma 2.3.3. The proof of the firstpart follows.We define a bipartite graph with vertex set E = k(A) ∪ {f̂ij}, and weconnect t ∈ k(A) with fij if fij(t) ∈ D. Then this graph has m = c3/22 n1+2αedges. We count the 2-paths:#P2 =∑x∈k(A)(d(x)2)≥ |k(A)|(m/|k(A)|2)≥ c′n1+4α.Hence at least c′′n4α pairs f̂ij , f̂i′j′ share c′′n common neighbors t in thisgraph. This implies that if c3 = c′′/d then c3n4α of the γiji′j′ have at leastc3n points in D ×D.2.4.3 Decomposing f̂ijLemma 2.4.4. There is a subset of c4n4α−1 of the γiji′j′ that all coincide,and such that c4n3α−1 of the f̂ij occur in these γiji′j′.Proof. By the Curve Lemma, for n > n0, there can be at most CCLn distinctc3n-rich curves on D×D, so c′n4α−1 must coincide. Setting c4 = c′/d2 givesthat at least c4n3α−1 of the f̂ij occur.Lemma 2.4.5. There are c4n3α−1 pairs (i, j) for whichfij(x) = p(aijk(x) + bij)where aij , bij ∈ R and p ∈ R[x].Proof. For each coinciding pair of curves γiji′j′ and γaba′b′ , we can writef̂ij = p ◦ ϕij and f̂ab = p ◦ ϕabby the Reparametrization Lemma. By construction of the f̂ij , the ϕij mustbe linear, which allows us to assume that all pairs use the same p. Writeϕij(t) = aijt + bij ; then for the c4n3α−1 corresponding fij we have fij =p ◦ ϕij ◦ k.322.4. Proof of Theorems 2.1.4, 2.1.5, and 2.1.62.4.4 Proof of Theorem 2.1.4Here we set α = 1, so we have c4n2 rich lines u = ϕij(t) = aijt+ bij that arerich on the (essentially) n× n cartesian product k(A)× p−1(D).We claim that either c5n2 of the lines u = ϕij(t) are parallel, or c5n2are concurrent, counting multiplicities. By the Szemere´di-Trotter Theorem(2.2.1), at most CSTn of the lines are distinct. By our Assumption afterLemma 2.4.1, fewer than 2dn are identical. This implies that for some c′ wecan split the lines into c′n classes of size at least c′n, such that within eachclass the lines are identical, and between the classes the lines are distinct.We take a representative of each class and apply the Line Lemma 2.2.3to these c′n representatives, telling us that c′′n are parallel or c′′n are con-current. Taking all of the corresponding classes together gives (c′′ · c′)n2lines that are all parallel or all concurrent.By Lemma 2.4.6 below, we only need 2dn lines parallel, to show thatf has the additive form f(x, y, z) = p(k(x) + l(y) + m(z)), so c′′c′n2 willcertainly suffice. Similarly, by Lemma 2.4.6, if c′′c′n2 of the lines are con-current, then f has the multiplicative form f(x, y, z) = p(k(x) · l(y) ·m(z)).That finishes the proof of Theorem 2.1.4.2.4.5 Proof of Theorem 2.1.5We have c5n3α−1 c5n-rich lines, for an α to be determined below. Many ofthese lines may coincide, so let nβ be the number of classes of coincidinglines. The average size of a class is then c5n3α−1−β, so for some c′ > 0and ε > 0 we can find a subset of c′nβ classes that all have size at leastc′n3α−1−β−ε.To apply Lemmas 2.4.6 and 2.4.8 and finish the proof, we will need2dnα lines that are all parallel or concurrent. To obtain these we need2dc′ nα−(3α−1−β−ε) = 2dc′ n1+β+ε−2α representatives of the coinciding classesthat are all parallel or all concurrent, since each class has size at leastc′n3α−1−β−ε. To get these representatives using Lemma 2.2.4, we needc′nβ ≥2dc′n2/3+(1+β+ε−2α)/3,for which it will suffice to have 3β − ε ≥ 2 + 1 + β + ε− 2α, so we will needto choose α so that β ≥ 3/2 + ε− α.On the other hand, if any of the nβ classes contains at least 2dnα lines,then also 2dnα of the fij would be identical, contradicting our assumptionafter Lemma 2.4.1. Hence all classes are smaller than 2dnα, which implies332.4. Proof of Theorems 2.1.4, 2.1.5, and 2.1.6thatnβ ≥c52dn2α−1,hence we have β ≥ 2α− 1− ε.The second inequality for β will imply the first if we choose α so that2α− 1− ε ≥ 3/2 + ε− α,hence α = 5/6 + ε will do.2.4.6 Proof of Theorem 2.1.6For Theorem 2.1.6, we do the same as for Theorem 2.1.5, except that insteadof Lemma 2.2.4 we apply Corollary 2.2.7. To get the right number of parallelor concurrent lines, we set p = q = 2dn1+β+ε−2α in the Corollary, so werequirec′nβ > (p+ q)nε′= 4dn1+β+ε−2α+ε′for some ε′. That will hold if β > 1+β+ε−2α+ε′, or α ≥ 1/2+ε/2+ε′/2,which is satisfied for ε′ = ε and α = 1/2 + ε as in Theorem 2.1.6.2.4.7 The parallel caseLemma 2.4.6. If 2dnα of the lines ϕij are parallel, then there is a polyno-mial r(y, z) such that f(x, y, z) = p(k(x) + r(y, z)).Proof. We can write fij(x) = p(k(x) + bij). We use the following two poly-nomial expansions of fij(x) = f(x, yi, zj) = p(k(x) + bij):N∑l=0vl · (k(x) + bij)l =N∑m=0wm(yi, zj) · k(x)m.The first is immediate from p(k(x) + bij); the second requires a little moreexplanation.By Lemma 2.2.11, there is a unique expansion of the polynomial f ofthe form f(x, y, z) =∑D−1l=0 cl(k(x), y, z)xl, where D = deg k. By the samelemma, we have a unique expansion fij(x) =∑D−1l=0 dl(k(x))xl, so that wehaveD−1∑l=0cl(k(x), yi, zj)xl =D−1∑l=0dl(k(x))xl ⇒ cl(k(x), yi, zj) = dl(k(x)).342.4. Proof of Theorems 2.1.4, 2.1.5, and 2.1.6But since fij(x) = p(k(x) + bij), uniqueness implies that dl = 0 for l > 0,hence cl(k(x), yi, zj) = 0 for l > 0. We have this for every yi, zj such thatϕij is one of the parallel lines.Then we have 2dnα zeroes of cl(k(x), y, z), so applying the VanishingLemma with |B| = |C| = nα gives cl(k(x), y, z) = 0 for l > 0. Thusf(x, y, z) = c0(k(x), y, z), which means there is an expansion f(x, y, z) =∑wm(y, z)k(x)m. Now plugging in y = yi, z = zj gives the expansionrequired above.Comparing the coefficients of k(x)N−1 in the two expansions above, wegetvN−1 + (N − 1)vNbij = wN−1(yi, zj),which implies that bij = 1(N−1)vN (wN−1(yi, zj)−vN−1). If we now define thepolynomialr(y, z) =1(N − 1)vN(wN−1(y, z)− vN−1),we have that for our 2dnα pairs (yi, zj) (note that vl and wm do not dependon the choice of pair)f(x, yi, zj) = p(k(x) + r(yi, zj)).By the Vanishing Lemma with |B| = |C| = nα, applied to F (y, z) =f(x, y, z) − p(k(x) + r(y, z)) over K = R(x), we get the desired equalityf(x, y, z) = p(k(x) + r(y, z)).Lemma 2.4.7. There are polynomials l and m such thatf(x, y, z) = p(k(x) + l(y) +m(z)).Proof. By applying the above with the roles of x and y swapped, we canalso write f(x, y, z) = P (K(y) + R(x, z)). Then we calculate the quotientfx/fy (using the notation fx = ∂f/∂x) for both forms,fxfy=k′(x)ry(y, z)=Rx(x, z)K ′(y),which tells us that ry(y, z) (and Rx(x, z)) is independent of z. Integratingwith respect to y then gives that r(y, z) = l(y) + m(z), which proves ourclaim.352.4. Proof of Theorems 2.1.4, 2.1.5, and 2.1.62.4.8 The concurrent caseLemma 2.4.8. If 2dnα of the lines ϕij are concurrent, There are polyno-mials P (t), K(x) and R(y, z) such thatf(x, y, z) = P (K(x) ·R(y, z)).Proof. We can write fij(x) = p(aij · k(x)). We again use two polynomialexpansions of fij(x) = f(x, yi, zj) = p(aij · k(x)):N∑l=0vl · (aij · k(x))l =N∑m=0wm(yi, zj) · k(x)m.Both are obtained in the same way as in the proof of Lemma 2.4.6.We cannot proceed exactly as before, since aij might only occur herewith exponents, and we cannot take a root of a polynomial. But we canwork around that as follows. Define M to be the greatest common divisorof all exponents m for which wm 6= 0 in the second expansion; then we canwrite M as an integer linear combination of these m, say M =∑µmm.Comparing the coefficients of any k(x)m with wm 6= 0 in the two expansionsabove, we getamij =1vmwm(yi, zj),which tells us thataMij =∏(amij )µm = R(yi, zj),where R(y, z) is a rational function.If we define P (s) = p(s1/M ), or equivalently P (tM ) = p(t), then thedefinition of M gives that P (s) is a polynomial. We also define K(x) =kM (x). Then for each of the 2dnα pairs yi, zj we haveP (K(x) ·R(yi, zj)) = P (kM (x) · aMij ) = p(k(x) · aij) = f(x, yi, zj).Applying the Vanishing Lemma with |B| = |C| = nα over R(x) to the numer-ator of f(x, y, z)−P (K(x)R(y, z)), we get that f(x, y, z) = P (K(x)R(y, z)).This also tells us that R is in fact a polynomial, since otherwise f could notbe one.Lemma 2.4.9. There are polynomials L and M such that f(x, y, z) =P (K(x) · L(y) ·M(z)).362.5. Applications and limitationsProof. By applying the above with the roles of x and y swapped, we canalso write f(x, y, z) = P ∗(K∗(y) ·R∗(x, z)). Then we calculate the quotientfx/fz for both forms,fxfz=K ′(x)R(y, z)K(x)Rz(y, z)=R∗x(x, z)R∗z(x, z),which tells us thatRz(y, z)R(y, z)=∂∂zlog(R(y, z))is independent of y. Integrating we get that log(R(y, z)) = λ(y) + µ(z),henceR(y, z) = eλ(y) · eµ(z) = L(y)M(z),which also implies that L(y) and M(z) are polynomials, as desired.This finishes the proof.2.5 Applications and limitationsIn this section we give some applications and limitations of the main results.We start by giving a simple condition to check whether a function has therequired additive or multiplicative form required in the main results. Thenwe give a proof of our variant of Purdy’s conjecture. Finally we give aconstruction using parabolas that shows that the exponents in Theorem 2.1.6cannot be improved significantly.2.5.1 How to check if a function is additive or multiplicativeHere we extend a technique from [21] for checking whether a given functionhas the additive or multiplicative form in the conclusions of our theorems.Given a differentiable function f(x, y) : R2 → R, we defineqf (x, y) =∂2∂x∂ylog[∂f/∂x∂f/∂y].Suppose f is of the form f(x, y) = p(k(x)+l(y)) or f(x, y) = p(k(x)l(y)),where p, k and l are nonconstant. Then one can check thatqf (x, y) = 0identically.372.5. Applications and limitationsSo, if we have a differentiable function f : R2 → R, and qf is not iden-tically zero, then we know that the function does not have the additive ormultiplicative form. The converse of this result also holds, although we donot need that fact here.A similar condition holds for functions f of the form f(x, y, z) = p(k(x)+l(y) +m(z)) or f(x, y, z) = p(k(x)l(y)m(z)). If we defineqf (x, y, z) =∂2∂x∂ylog[∂f/∂x∂f/∂y].Then qf (x, y, z) = 0.Notice that with f in the form above,∂f/∂x∂f/∂y=k′(x)l′(y)or∂f/∂x∂f/∂y=k′(x)l(y)m(z)k(x)l′(y)m(z)=k′(x)l(y)k(x)l′(y)is independent of z. This provides another way of checking whether a func-tion does not have the additive or multiplicative form.Similar conditions could be checked using partial derivatives with respectto z. If f(x, y, z) = p(k(x) + l(y) +m(z)) or f(x, y, z) = p(k(x)l(y)m(z)) wegetrf (x, z) =∂2∂x∂zlog[∂f/∂x∂f/∂z]= 0andsf (y, z) =∂2∂y∂zlog[∂f/∂y∂f/∂z]= 0.Note that in this case the converse does not hold. In the example inSection 2.5.3 below qf = 0, rf = 0 and sf = 0, but f does not have therequired decomposition.2.5.2 On a conjecture of PurdyThe following theorem was conjectured by Purdy (for example, see [9]) andproved by Elekes and Ro´nyai in [21]. We will use the notation D(P,Q) ={d(p, q) : p ∈ P, q ∈ Q} for the set of distances between two point sets.Theorem 2.5.1. For all c there is an n0 such that for n > n0 the followingholds for any two lines `1 and `2 in R2 and sets Pi of n points on `i.If |D(P1, P2)| < cn then the two lines are parallel or orthogonal.Using Theorem 2.1.3 we can extend it to the asymmetric case when wehave fewer points on one of the lines. The proof is similar to that in [21].382.5. Applications and limitationsTheorem 2.5.2. For every c > 0 and ε > 0 there is an n0 such that forn > n0 the following holds for any two lines `1 and `2 in R2, P1 a set of npoints on `1, and P2 a set of n1/2+ε points on `2.If |D(P1, P2)| < cn then the two lines are parallel or orthogonal.Proof. Assume the lines are not parallel. Parametrize the lines from theirintersection point, l1 by x1 and l2 by x2, and let X1 and X2 represent P1and P2 in this parametrization. Then the condition on the distances meansby the Law of Cosines that the polynomial f(x1, x2) = x21 + 2λx1x2 + x22assumes < cn values on X1×X2, where −λ is the cosine of the angle betweenthe two lines.Then z = f(x1, x2) contains > c′n3/2+ε points of the cartesian productX1×X2×E where E = {a2 : a ∈ D(P1, P2)}. By Theorem 2.1.3, this impliesthat f has the additive or multiplicative form. Thus qf , as defined in Section2.5.1, should be identically zero. A quick calculation shows that this is onlypossible if λ = −1, 0, or 1, which means that the angle between the lines is0, which is not possible, or pi/2, which means the lines are orthogonal.2.5.3 Limits on the asymmetry of the cartesian productIn this section we show that Theorem 2.1.6 is near-optimal. We will use thenotation [a, b] = {a, a+ 1, . . . , b− 1, b}.Considerf(x, y, z) = x+ (y − z)2,and let A = D = [1, k2] and B = C = [1, k] for an even integer k. If we setn = k2, then |A| = |D| = n and |B| = |C| = n1/2. We can think of the solidw = f(x, y, z) as consisting of translates of the parabola w = y2 from thewy-plane.We have x+ (y − z)2 ∈ D when (for instance)x ∈ [1, k2/2], y ∈ [1, k/2] and z ∈ [1, k/2].Then the solid w = f(x, y, z) contains at least 18k4 = 18n2 points of A×B×C ×D.But the function f(x, y, z) = x+ (y− z)2 does not have one of the formsp(k(x) + l(y) + m(z)) or P (K(x)L(y)M(z)). Note that qf = 0, rf = 0 andsf = 0, so we cannot use the method above to show that f does not havethe additive or multiplicative form. Instead we consider a degree argument.Suppose f(x, y, z) = P (K(x)L(y)M(z)). Since each of P,K,L and Mmust have degree at least one, we would have deg f ≥ 3, a contradiction. Sof does not have the multiplicative form.392.5. Applications and limitationsNow suppose that f(x, y, z) = p(k(x) + l(y) + m(z)). Then p, k, l andm have degree at least one and at most two. If deg p = 2 then deg k = 1,implying f has a term of the form cx2, which it doesn’t. If deg p = 1, thenf couldn’t contain the term −2yz. So f does not have the additive formeither.Therefore the graph of w = f(x, y, z) = x+(y−z)2 contains many pointsof A×B×C ×D, but f cannot be written in the additive or multiplicativeform. Hence any extension of Theorem 2.1.4 with |B| = |C| would have tohave |B| = |C| ≥ cn1/2 for some constant c > 0. Theorem 2.1.6 supposes|B| = |C| = n1/2+ε for some ε > 0, so that condition cannot be improvedsignificantly.40Chapter 3Rational distances withrational angles3.1 IntroductionIn this chapter we prove our first special case of the unit distance problemalong with similar results for rational distances.We will show that the upper bound n1+7/√logn holds if we only considerunit distances that have rational angle, by which we mean that the linethrough the pair of points makes a rational angle in degrees with the x-axis(or equivalently, its angle in radians, divided by pi, is rational). Under thisrestriction, we can use an algebraic theorem of Mann [44] to get a uniformbound on the number of paths between two fixed vertices in the unit distancegraph, which will lead to a contradiction if there are too many unit distanceswith rational angle between the points.In fact, our proof also shows that the bound n1+7/√logn holds for thenumber of rational distances with rational angles, if we have no three pointson a line. The lower bound, n1+c/ log logn, of Erdo˝s does not apply in thiscase as we are restricted to rational angles. But a construction of Erdo˝sand Purdy gives a superlinear lower bound for unit (and hence rational)distances with rational angles.If instead we allow up to nα points on a line where 3/5 ≤ α ≤ 1, thenumber of rational distances with rational angles is bounded by 3n1+α. Thisbound is tight up to a constant factor with the lower bound now comingfrom an n1−α × nα square grid. If we allow up to nα points on a linewhere 0 < α < 3/5, the number of rational distances with rational angles isbounded above by n1+α+7/√logn. We get a lower bound of cn1+α from n1−αhorizontal lines each containing nα rational points so that no three pointson different lines are collinear.In Section 3.2 we will state our main results and give an outline of theproof. Section 3.3 contains the algebraic tools that we will use, including,for completeness, a proof of Mann’s Theorem. In Section 3.4 we use the413.2. Main results and proof sketchbounds obtained from Mann’s theorem and some graph theory to prove ourmain results. In Section 3.5 we give lower bounds for the main results.3.2 Main results and proof sketchWe will say that a pair of points in R2 has rational angle if the line segmentbetween them, viewed as a complex number z = repiiγ , has γ ∈ Q. Our firstresult is the following.Theorem 3.2.1. Given n points in R2, the number of pairs of points withunit distance and rational angle is at most n1+7/√logn.Roughly speaking, our proof goes as follows. Given n points in the plane,we construct a graph with the points as vertices, and as edges the unit linesegments that have rational angle. We can represent these unit line segmentsas complex numbers, which must be roots of unity because of the rationalangle condition. Then if this graph has many edges, it should have manycycles of a given length k, and each such cycle would give a solution to theequationk∑i=1ζi = 0,with ζi a root of unity. Using an algebraic theorem of Mann from 1965 [44],we could give a uniform bound on the number of such solutions, dependingonly on k (under the non-degeneracy condition that no subsum vanishes).If the number of non-degenerate cycles goes to infinity with n, this wouldgive a contradiction.However, dealing with cycles of arbitrary length is not so easy, so insteadin our proof we count non-degenerate paths (which we will call irredundantpaths) of length k between two fixed vertices, which correspond to solutionsof the equationk∑i=1ζi = a,where a ∈ C, a 6= 0 corresponds to the line segment between the two points.We have extended Mann’s theorem to this type of equation, giving a similarupper bound and proving our result.In fact, in our proof it turns out that it is not necessary for the lengths tobe 1, but that they only need to be rational. This is because our extension423.3. Mann’s Theoremof Mann’s theorem also works for equations of the typek∑i=1aiζi = a,where ai ∈ Q and a ∈ C, a 6= 0. This leads to the following results.Theorem 3.2.2. Suppose we have n points in R2, no three of which areon a line. Then the number of pairs of points with rational distance andrational angle is at most n1+7/√logn.Theorem 3.2.3. Suppose we have n points in R2, with no more than nα ona line, where 0 < α < 3/5. Then the number of pairs of points with rationaldistance and rational angle is at most n1+α+7/√logn.Theorem 3.2.4. Suppose we have n points in R2, with no more than nα ona line, where 3/5 ≤ α ≤ 1. Then the number of pairs of points with rationaldistance and rational angle is at most 3n1+α.Remark: It has been brought to the attention of the authors that a result ofConway and Jones gives an improved bound in Theorem 3.3.1 from the fol-lowing section [15]. Using this improved bound we can replace the 7/√log nin the exponents in Theorems 3.2.1–3.2.3 with c(log log n)1/3/(log n)2/3.3.3 Mann’s TheoremFor completeness we provide a proof of Mann’s Theorem. We then provethe extension that we will need to prove the main result in the next section.Theorem 3.3.1 (Mann). Suppose we havek∑i=1aiζi = 0,with ai ∈ Q, the ζi roots of unity, and no subrelations∑i∈Iaiζi = 0 where∅ 6= I ( [k]. Then(ζi/ζj)m = 1for all i, j, with m =∏p≤kp primep.433.3. Mann’s TheoremThe bound of Conway and Jones mentioned at the end of the last sectiongives m satisfying the inequality m ≤ ec√k log k.Proof. We can assume that ζ1 = 1 and a1 = 1, so that we have 1 +∑ki=2 aiζi = 0. We take a minimal m such that ζmi = 1 for each i.We will show that m must be squarefree, and that a prime p that divides mmust satisfy p ≤ k. Together these prove the theorem.Let p be a prime dividing m. Write m = pj ·m∗ with (p,m∗) = 1, and usethat to factor each ζi as follows:ζi = ρσi · ζ∗i ,with ρ a primitive pjth root of unity soρpj= 1, (ζ∗i )pj−1m∗ = 1, 0 ≤ σi ≤ p− 1.Now reorganize the equation as follows:0 = 1 +k∑i=2aiζi = 1 +p−1∑`=0α`ρ` = f(ρ),where the coefficients are of the formα` =∑i∈I`aiζ∗i ∈ Q(ζ∗2 , . . . , ζ∗k) = K,with I` = {i ∈ [k] : σi = `}. So f is a polynomial over the field K of degree≤ p − 1 and f(ρ) = 0. The polynomial f is not identically zero, since thatwould give a subrelation containing strictly fewer than k terms. To see this,observe that we must have σi ≥ 1 for at least one i, otherwise ζm/pi = 1 foreach i, contradicting the minimality of m.But we can compute the degree of ρ over K to bedegK(ρ) =φ(m)φ(pj−1m∗)=φ(pj)φ(pj−1)={p− 1 if j = 1p if j > 1.This is a contradiction unless j = 1, which proves that m is squarefree.Knowing that m is squarefree, we have m = p ·m∗ with (p,m∗) = 1, andζi = ρσi · ζ∗i , ρp = 1, (ζ∗i )m∗ = 1, 0 ≤ σi ≤ p− 1.Still f(ρ) = 0 for f(x) a polynomial over K, not identically zero. But weknow ([42], Ch. VI.3) that the minimal irreducible polynomial of ρ over Kis F (x) = xp−1 + xp−2 + · · ·+ x+ 1, hence we must have f(x) = cF (x) forsome c ∈ K. In particular, f has p terms, which implies that our originalrelation had at least p terms, so k ≥ p.443.3. Mann’s TheoremTheorem 3.3.2. Suppose we havek∑i=1aiζi = a,k∑j=1a∗jζ∗j = a,with a ∈ C, a 6= 0, ai ∈ Q, roots of unity ζi, and no subrelations∑i∈Iaiζi = 0or∑j∈Ja∗jζ∗j = 0 where ∅ 6= I ( [k] and ∅ 6= J ( [k]. Then for any ζ∗j thereis a ζi such that (ζ∗j /ζi)m= 1with m =∏p≤2kp primep.Proof. We have∑aiζi = a =∑a∗jζ∗j , which gives the single equationk∑i=1aiζi −k∑j=1a∗jζ∗j = 0. (3.1)Mann’s Theorem does not apply immediately, because there might be sub-relations. But we can break the equation up into minimal subrelations∑i∈I`aiζi −∑j∈I∗`a∗jζ∗j = 0, (3.2)where each I` 6= ∅, I∗` 6= ∅, and there are no further subrelations.Given ζ∗j , there is such a minimal subrelation of length ≤ 2k in which itoccurs, and which must also contain some ζi. Applying Mann’s Theorem tothis equation gives(ζ∗j /ζi)m= 1 with m =∏p≤2kp primep.Note that in the above proof we require a 6= 0. If a = 0 and there is noproper subrelation as in (3.2) then (3.1) still has the subrelationsk∑i=1aiζi = 0,k∑j=1a∗jζ∗j = 0,so we cannot use Mann’s Theorem to get a relation between a ζi and ζ∗j .453.4. Rational distances and Mann’s TheoremFor a ∈ C, a 6= 0, k ∈ Z, k > 0 we define Zka to be the set of k-tuples ofroots of unity (ζ1, . . . , ζk) for which there are ai ∈ Q such that∑ki=1 aiζi = awith no subrelations, i.e.:Zka = {(ζ1, . . . , ζk) | ∃ai ∈ Q :k∑i=1aiζi = a,∑i∈Iaiζi 6= 0 for ∅ 6= I ⊂ [k]}.Corollary 3.3.3. Let C(k) =∏p≤2kp primep. Given a ∈ C, a 6= 0, |Zka | ≤ (k ·C(k))k.Proof. Fix an element (ζ1, . . . , ζk) ∈ Zka and let m = C(k) and Mi = ζ−mifor 1 ≤ i ≤ k. Then for ζ∗j in any element of Zka , we have an i such thatMi(ζ∗j)m= 1. In other words ζ∗j is a solution of Mixm = 1. Each of thesek equations has m = C(k) solutions, hence there are at most k ·m = k ·C(k)choices for each ζ∗j .3.4 Rational distances and Mann’s TheoremWe are now in a position to prove the main results. Suppose we have agraph G = G(V,E) on v(G) = n vertices and e(G) = cn1+α edges. We willdenote the minimum degree in G by δ(G). The following lemma assuresus that we can remove low-degree vertices from our graph without greatlyaffecting the number of edges.Lemma 3.4.1. Let G be as above. Then G contains a subgraph H withe(H) = (c/2)n1+α edges such that δ(H) ≥ (c/2)nα.Proof. We iteratively remove vertices from G of degree less than (c/2)nα.Then, the resulting subgraph H has δ(H) ≥ (c/2)nα and we removed fewerthan (c/2)n1+α edges so H contains more than (c/2)n1+α edges.Note that the subgraph H constructed above contains at least v(H) =(c/2)1/2n1/2+α/2 vertices.Suppose we are given a path on k edges Pk = p0p1 . . . pk. We call thispath irredundant if ∑i∈I−−−→pipi+1 6= 0for any ∅ 6= I ⊂ {0, 1, . . . , k − 1}.463.4. Rational distances and Mann’s TheoremProof of Theorem 3.2.2. Let G be the graph with the n points in the planeas vertices and the rational distances with rational angles between pairs ofpoints as edges. Suppose there are n1+f(n) such distances for some positivefunction f . Then e(G) = n1+f(n). We will count the number of irredundantpaths Pk in G, for a fixed k that we will choose later. By Lemma 3.4.1 wecan assume that e(G) ≥ (1/2)n1+f(n), v(G) ≥ (1/2)n1/2+f(n)/2 and δ(G) ≥(1/2)nf(n).The number of irredundant paths Pk starting at any vertex v is at leastN =k−1∏`=0(δ(G)− 2` + 1),since, if we have constructed a subpath P` of Pk, then at most 2` − 1 ofthe at least δ(G) continuations are forbidden. Thus the total number ofirredundant paths Pk is at leastn1/2+f(n)/2N2≥(n1/2+f(n)/2/2) k−1∏`=0((1/2)nf(n) − 2` + 1) ≥n(k+1/2)f(n)+1/222k+1if 2k ≤ (1/2)nf(n), which is true as long as k < f(n) log n/ log 2. It followsthat there are two vertices v and w with at leastn1/2+f(n)/2Nn2≥(nf(n)/2−3/2) k−1∏`=0((1/2)nf(n) − 2` + 1) ≥n(k+1/2)f(n)−3/24kirredundant paths Pk between them. We will call the set of these paths Pvw,so that we have |Pvw| ≥(n(k+1/2)f(n)−3/2)/4k.Given Pk ∈ Pvw, Pk = p0p1 . . . pk, consider the k-tuple (ζ1, . . . , ζk) whereζi is the root of unity in the direction from pi−1 to pi, i.e. ζi =−−−→pi−1pi/|−−−→pi−1pi|.Note that (ζ1, . . . , ζk) ∈ Zka , because Pk is irredundant. Since there are nothree points on a line, this process gives an injective map from Pvw to Zkaso |Pvw| ≤ (k · C(k))k by Corollary 3.3.3. Thusn(k+1/2)f(n)−3/24k≤ (k · C(k))k =⇒ n(k+1/2)f(n)−3/2 ≤ (4k · C(k))k.But this givese((k+1/2)f(n)−3/2) logn ≤ ek log(4k·C(k)) =⇒ f(n) ≤log(4k) + log(C(k))log n+32k.473.4. Rational distances and Mann’s TheoremThe term log(C(k)) is the log of the product of the primes less thanor equal to 2k. This is a well known number-theoretic function called theChebyshev function and denoted by ϑ, specifically ϑ(2k) = log(C(k)). Weuse the following bound on ϑ (for a proof see [5]):ϑ(x) < 4x log 2 < 3x, for x ≥ 2.This givesf(n) <log(4k) + 6klog n+1k<7log nk +32k.Let k be an integer such that f(n) log n/16 < k < f(n) log n/14, (possiblesince otherwise f(n) = O(1/ log n) giving nf(n) = O(1)). Then the conditionthat k < f(n) log n/ log 2 is clearly satisfied, and we getf(n) <7log n·f(n) log n14+24f(n) log n=⇒ f(n) <7√log n.This completes the proof.Proof of Theorem 3.2.1. In the statement of Theorem 3.2.1, the requirementthat there are no three points on a line is unnecessary. This is because, fromany point, there is only one unit distance in any direction. Thus we canapply the same proof as in Theorem 3.2.2 to Theorem 3.2.1 without havingto worry about multiple points on a line. Thus we also have a proof ofTheorem 3.2.1.Consider a path Pk = p0p1 . . . pk. If the distance from pi−1 to pi is lessthan the distance from pi−1 to any vertex on the line connecting pi−1 andpi and not in Pi−1 = p0p1 . . . pi−1 then Pk is called a shortest path.Proof of Theorem 3.2.3. This proof is almost the same as the proof of The-orem 3.2.2 except that instead of considering all irredundant paths Pk, weonly consider shortest irredundant paths. Suppose there are n1+α+f(n) edgesin the rational distance graph. Since there are at most nα points on a line,we get that from any vertex v there are at leastN =k−1∏`=0(δ(G)nα− 2` + 1)≥nkf(n)4kshortest irredundant paths Pk, if k < f(n) log n/ log 2. For any two ver-tices v, w let Pv,w be the set of shortest irredundant paths Pk between v483.4. Rational distances and Mann’s Theoremand w. Then there are two vertices v, w such that the number of shortestirredundant paths between v and w is at least|Pv,w| ≥n(k+1/2)f(n)+α/2−3/24k.By Mann’s Theorem, since we are looking at shortest irredundant paths,|Pv,w| ≤ (k · C(k))k. Let k be an integer such that f(n) log n/16 < k <f(n) log n/14. Thenn(k+1/2)f(n)+α/2−3/24k≤ (k · C(k))k =⇒ f(n) <7√log n.Proof of Theorem 3.2.4. Assume we have a configuration of n points withat most nα on a line, 3/5 ≤ α ≤ 1, and n1+α+f(n) rational distances withrational angles, for some positive function f(n).The graph G on these points has e(G) = n1+α+f(n). By Lemma 3.4.1we can assume that e(G) ≥ n1+α+f(n)/2, v(G) ≥ n1/2+α/2+f(n)/2/2 andδ(G) ≥ nα+f(n)/2. We now count irredundant paths P2 of length 2. Notethat an irredundant path on two edges is just a noncollinear path.For any vertex v, since we have at most nα points on a line, v is themidpoint of at leastN = δ(G)(δ(G)− nα) ≥n2(α+f(n))8paths P2 if f(n) ≥ log 4/ log n (if f(n) < log 4/ log n then nf(n) < 4, com-pleting the proof.) Thus there are two vertices v and w with at least(1/8)n(5/2)(α+f(n))−3/2 noncollinear paths P2 between them.But by Corollary 3.3.3 there is a constant number of directions from eachof v and w. Since we are looking at noncollinear paths P2, the direction fromv and the direction from w uniquely determine the midpoint for a path P2.Thus there are at most (k · C(k))k = 144 noncollinear paths P2 between vand w, since k = 2.Putting these upper bounds and lower bounds together we get thatn(5/2)(α+f(n))−3/2 ≤ 2732. This givesf(n) ≤14 log 2 + 4 log 35 log n+35− α ≤14 log 2 + 4 log 35 log n<3log n,since α ≥ 3/5. But this gives nf(n) < 3, completing the proof.493.5. Lower bounds3.5 Lower boundsIn this section we give lower bounds for the theorems given in Section 3.2.The bounds in Theorems 3.2.1 and 3.2.2 are not far from optimal as thefollowing construction of Erdo˝s and Purdy [27] shows.Suppose we have n points, no three on a line, with the maximum possiblenumber of unit distances with rational angles; we call this number f(n).Consider these points as the set {z1, . . . , zn} of complex numbers. For anya ∈ C with |a| = 1, a 6= zi − zj for any i 6= j, the set {z1, . . . , zn, z1 +a, . . . , zn + a} contains at least 2f(n) + n unit distances since there aref(n) amongst each of the sets {z1, . . . , zn} and {z1 + a, . . . , zn + a} and|zi − (zi + a)| = 1 for each i. This new set may have three points on a line,but we show that we can choose a appropriately so this is not the case.Consider a pair of points zi and zj . For each zk, the set of points {zk+a :|a| = 1} intersects the line through zi and zj in at most two points. So thereare at most two values of a that will give three points on a line. There are(n2)pairs of points and n choices for zk so there are at most 2n(n2)= n2(n− 1)values of a that make a point zk + a collinear with two points zi and zj .Similarly we have n2(n− 1) values of a that make a point zk collinear withtwo points zi + a and zj + a. Thus there are only finitely many values of athat give three points on a line. There are infinitely many choices for a sowe are done.This shows that f(2n) ≥ 2f(n) + n for n > 2 and clearly f(2) = 1.From this we get that f(2k) ≥ 2k−1(k − 1) = 2k−1 log2(2k−1). Taking2k ≤ n < 2k+1 we get that f(n) ≥ cn log n for all n. This construction givesa lower bound for Theorems 3.2.1 and 3.2.2.The bound in Theorem 3.2.3 is not far from optimal. In fact we canget a lower bound of cn1+α. Consider n1−α lines parallel to the x-axis, andchoose nα rational points on each line such that no three points on differentlines are collinear (this can always be done since there are infinitely manyrational points to choose from). There are cn2α rational distances on eachhorizontal line and n1−α such lines giving at least cn1+α rational distanceswith rational angles (all the angles are zero).The bound in Theorem 3.2.4 is tight up to a constant factor as can beseen by considering an n1−α × nα square grid. Then there are at least cn2αrational distances on each of the n1−α horizontal lines in the grid containingnα points. This gives at least cn1+α rational distances with rational angles(the angles are all zero).50Chapter 4Using the Subspace Theoremto bound unit distances4.1 IntroductionIn this chapter we give our second special case of the Erdo˝s unit distanceproblem and show that the unit distances in the lower bound construction ofErdo˝s satisfy the conditions of our main result. In the previous chapter weconsidered unit distances that correspond to roots of unity. In this chapterwe consider unit distances coming from a group with “low” rank—rootsof unity come from a group with rank 0. Our main tool is a corollary ofthe Subspace Theorem which we state below. More details of the SubspaceTheorem can be found in the next chapter.Consider two points p = (p1, p2), q = (q1, q2) ∈ R2 with unit distance.Considering the vector −→pq between these two points we get the complexnumberz = z(p, q) = (q1 − p1) + i(q2 − p2), with |z| = 1.We will restrict our attention to unit distances with z coming from a multi-plicative subgroup of C∗ (the multiplicative group of nonzero complex num-bers) of finite rank. Recall that a subgroup Γ ⊂ C∗ has rank r if there existsa finitely generated subgroup Γ0 ⊂ Γ with r generators such that for everyx ∈ Γ there exists an integer k ≥ 0 such that xk ∈ Γ0.Suppose Γ is a subgroup of C∗ of finite rank r and a1, a2, . . . , ak ∈ C∗. Re-call that a solution of the equation a1z1+a2z2+· · ·+akzk = 1 is called nonde-generate if no subsum of the left-hand side vanishes. That is∑j∈J ajzj 6= 0for every nonempty J ⊂ {1, 2, . . . , k}. We will consider the number A(k, r) ofnondegenerate solutions of this equation with zi ∈ Γ. We now give the corol-lary of the Subspace Theorem with the best known bound due to Amorosoand Viada [3].Theorem 4.1.1. Suppose a1, a2, . . . , ak ∈ C∗ and Γ has finite rank r. Thenthe number of nondegenerate solutions of the equationa1z1 + a2z2 + · · ·+ akzk = 1 (4.1)514.2. Proof of the main resultwith zi ∈ Γ is at mostA(k, r) ≤ (8k)4k4(k+kr+1).Amoroso and Viada proved Theorem 4.1.1 over an arbitrary algebraicallyclosed field K of characteristic 0 but we only require it over C.We will use this to prove the following result.Theorem 4.1.2. Let ε > 0. Then there exist n0 = n0(ε), a positive integer,and c = c(ε) > 0 such that given n > n0 points in the plane, the number ofunit distances with z coming from a subgroup Γ ⊂ C∗ with rank r < c log nis at most n1+ε.We will prove this theorem in the next section and in Section 4.3 we willshow that the unit distances from the lower bound construction of Erdo˝ssatisfy the hypotheses of this theorem.4.2 Proof of the main resultThe proof of Theorem 4.1.2 is quite similar to the proof of Theorem 3.2.1in Section 3.4. The main difference is that we use the Subspace Theoreminstead of Mann’s result to get an upper bound for paths in the unit distancegraph.Suppose G = G(V,E) is a graph on v(G) = n vertices and e(G) = cn1+αedges. We denote the minimum degree in G by δ(G). The following lemmashows that we can remove low degree vertices from our graph without greatlyaffecting the number of edges.Lemma 4.2.1. Let G be as above. Then G contains a subgraph H withe(H) ≥ (c/2)n1+α edges such that δ(H) ≥ (c/2)nα.Proof. We remove vertices from G of degree less than (c/2)nα one by one.After removing a vertex some of its neighbours may have their degree re-duced to below (c/2)nα. If so then we add such vertices to the list of verticesto be removed. In total we remove fewer than (c/2)n1+α edges so the re-sulting subgraph H has at least (c/2)n1+α edges. Thus the above processmust stop and the resulting graph has δ(H) ≥ (c/2)nα.Note that the subgraph H constructed above contains at least v(H) =√cn1/2+α/2 vertices.524.2. Proof of the main resultSuppose we are given a path on k edges Pk = p0p1 . . . pk. We call thispath irredundant if ∑i∈I−−−→pipi+1 6= 0for every ∅ 6= I ⊂ {0, 1, . . . , k − 1}.Proof of Theorem 4.1.2. Let G be the graph with the n points in the planeas vertices and the unit distances with z coming from Γ as edges. Supposethere are n1+ε such distances. Then e(G) = n1+ε. We will show that we cantake ε as small as we like. We will count the number of irredundant pathsPk in G, for a fixed k that we will choose later. By Lemma 4.2.1 we canassume that e(G) ≥ (1/2)n1+ε, v(G) ≥ n1/2+ε/2 and δ(G) ≥ (1/2)nε.The number of irredundant paths Pk starting at any vertex v is at leastN ≥k−1∏`=0(δ(G)− 2` + 1) ≥nkε22k.The first inequality is true since if we have constructed a subpath P` of Pk,then at most 2`−1 of the at least δ(G) possible continuations are forbidden.In the second inequality we have assumed that 2k ≤ (1/2)nε, which is trueas long as k < ε log n/ log 2 − 1 (we will show that this holds at the endof the proof). Thus the total number of irredundant paths Pk is at leastNn1/2+ε/2/2 ≥ n1/2+(k+1/2)ε/22k+1. It follows that there are two vertices vand w with at least Nn1/2+ε/2/n2 ≥ n(k+1/2)ε−3/2/4k irredundant paths Pkbetween them. We will call the set of these paths Pvw, so that we have|Pvw| ≥n(k+1/2)ε−3/24k.Given Pk ∈ Pvw, Pk = p0p1 . . . pk, consider the k-tuple (z1, . . . , zk)where zi is the complex number in the direction from pi−1 to pi, i.e. zi =z(pi−1, pi) =−−−→pi−1pi. Let a = z(v, w). Then z1 + z2 + · · ·+ zk = a. Since thepath is irredundant no subsum on the left vanishes. So Pk corresponds to anondegenerate solution of Equation (4.1) with ai = 1/a for i = 1, 2, . . . , k.Thus, by Theorem 4.1.1,|Pvw| ≤ (8k)4k4(k+kr+1).Putting these inequalities together and taking logarithms we get((k + 1/2)ε− 3/2) log n ≤ k log 4 + 4k4(k + kr + 1) log(8k)≤ 5rk5 log k,534.3. Analysis of Erdo˝s’ lower boundwhere the last inequality holds for large k. From this we getε ≤5rk5 log k(k + 1/2) log n+32(k + 1/2)≤5rk4 log klog n+32k. (4.2)We consider the expression on the right hand side as a function of k.Optimizing this function we getk ≥ exp((1/5)W (5c2 log n/r))for some constant c2 > 0 where W is the positive real-valued function satis-fying x = W (x)eW (x). This function is called the Lambert W function andwas first studied by J.H. Lambert in 1758 [41]. The following asymptoticexpression is due to N.G. de Bruijn [17]:W (x) = log(x)− log log(x) +O( log log log xlog log x).We don’t require this much accuracy. One can easily check, and we will justuse the fact, that (1/2) log x ≤W (x) ≤ log x for x ≥ e.Then we can takec′(log nr)1/5≤ k ≤ c′′(log nr)1/5for some constants c′, c′′ > 0.For any ε > 0 there is a constant c > 0 such that if r + 1 ≤ c log n thenthe inequality in (4.2) holds for large n. When counting Pk’s we made theassumption that k ≤ ε log n/ log 2 − 1. Checking the above values of k andf we see that this holds for large n.This completes the proof.4.3 Analysis of Erdo˝s’ lower boundIt would be interesting to analyze the possible group structure of point setswith the maximum (or near maximum) number of unit distances. We willnow show that the lower bound configuration for the unit distance problemgiven by Erdo˝s satisfies the hypotheses of Theorem 4.1.2. Matousˇek hasgiven a very in-depth account of Erdo˝s’ lower bound and we will follow thathere [46].544.3. Analysis of Erdo˝s’ lower boundWe require the following number-theoretic functions:pid,a(x) =∑p≤xp≡a(d)1, ϑd,a(x) =∑p≤xp≡a(d)log p, ψd,a(x) =∑p`≤xp`≡a(d)log p,where the first two sums are over primes less than x of the form p = a+ kdand the last sum is over primes p and positive integers ` such that p` =a+ kd and p` ≤ x. These are analogues of the prime counting function andChebyshev functions for arithmetic progressions.We will use the following results regarding these functions all of whichare well known in number theory. For details see [35] and [49].Theorem 4.3.1 (The Prime Number Theorem for Arithmetic Progres-sions). Suppose a and d are positive integers such that (a, d) = 1. Thenpid,a(n) = (1 + o(1))1ϕ(d)·nlog n.A simple consequence of this result is that if a and d are positive integerssuch that a < d and (a, d) = 1 then the kth prime of the form pi = a+ kidsatisfies pk = (1 + o(1))k log k/ϕ(d).Theorem 4.3.2. Suppose a and d are positive integers such that (a, d) = 1.Thenψd,a(n) = (1 + o(1))nϕ(d).Theorem 4.3.2 can be deduced from Theorem 4.3.1 by partial summation.Theorem 4.3.3. Suppose a and d are positive integers such that (a, d) = 1.Thenϑd,a(n) = (1 + o(1))ψd,a(n).The above two theorems give ϑd,a(n) = (1 + o(1))n/ϕ(d).We will also use the following fact. For details see [51].Theorem 4.3.4. The number of integer solutions, R(m), of x2 + y2 = mwhere m = p1p2 . . . pr and the pi are distinct primes of the form pi = 4ki+1isR(m) = 2r+2.554.3. Analysis of Erdo˝s’ lower boundThe lower bound configuration consists of n points in a√n ×√n grid.The step in the grid is chosen to be 1/√m where m is the product of the firstr−1 primes of the form 4k+1 and r is the largest number with m ≤ n/4. Wewill in fact consider a√n×√n grid with step 1 and then count the distancesof length√m. This gives a lower bound to the unit distance problem byscaling the point set by 1/√m.We have 4p1p2 . . . pr−1 ≤ n < 4p1p2 . . . pr. From this the bound r ≥log n/(3 log log n) is found using the prime number theorem for arithmeticprogressions. Distances equal to√m in this configuration correspond tointeger solutions of x2 +y2 = m. In the lower bound, the fact that there areat least 2r−1/16 such distances is used. But an upper bound on the numberof such distances can also be found. By Theorem 4.3.4 there are at most4 · 2(r−1)+2 = 2r+3 such distances from any point so we have at most 2r+3nsuch distances in total. Erdo˝s’ construction gives a lower bound for r. If wecan find an upper bound for r then we are done as will be described below.We will briefly explain the reason that m is defined as above as thishighlights the generators to choose for a multiplicative subgroup of C∗ con-taining the unit distances of the configuration. A prime p has a uniqueexpression, up to the order of the terms, of the form x2 + y2 = p with xand y positive integers if and only if p = 2 or p = 4k+ 1 for some integer k.The Brahmagupta-Fibonacci identity says that the product of two numbers,each expressible as the sum of two squares, is itself expressible as the sumof two squares. Specifically(a2 + b2)(c2 + d2) = (ac− bd)2 + (ad+ bc)2= (ac+ bd)2 + (ad− bc)2.So as we multiply more primes of the form 4k + 1 together we get moreexpressions of the resulting number as a sum of two squares. So all solutionsof x2 + y2 = m can be described in terms of the solutions of x2j + y2j = pj .More formally, we consider the ring R of points in Z2 with additiondefined coordinate-wise, so (a, b) + (c, d) = (a+ c, b+ d), and multiplicationdefined as follows: (a, b) · (c, d) = (ac− bd, ad+ bc). One can check that R isactually a ring and is in fact isomorphic to the Gaussian integers Z[i] sincethe operations correspond to complex addition and complex multiplication.But Z[i] is a unique factorization domain so R is also a unique factorizationdomain. We will consider the elements of R as distance vectors.In our grid we are looking for the distance m = p1 . . . pr−1. By Theo-rem 4.3.4, the number of pairs (x, y) ∈ Z2 with x2 +y2 = m is R(m) = 2r+1.Suppose x2j + y2j = pj . We consider the point (xj , yj) ∈ R. The product of564.3. Analysis of Erdo˝s’ lower boundthese r − 1 points (x, y) = (x1, y1)(x2, y2) . . . (xr−1, yr−1) has magnitude|(x, y)| = |(x1, y1)| . . . |(xr−1, yr−1)| =√p1 . . . pr−1 =√m.So this product gives a point with length√m.Now, R is a unique factorization domain. That means that the point(x, y) = (x1, y1) . . . (xr−1, yr−1) has unique factorization. Specifically, in anyother factorization of (x, y) = (x′1, y′1) . . . (x′r−1, y′r−1) there is a bijection φof the factors such that (xj , yj) = uj(x′φ(j), y′φ(j)) where uj is a unit. Theunits in R correspond to the units in Z[i]. In the latter these are 1,−1, i,−iso in the former they are (1, 0), (−1, 0), (0, 1) and (0,−1). Two elements(a, b), (c, d) ∈ R are called associates if (a, b) = u(c, d) for some unit u. Soin a unique factorization domain the factorization of an element is uniqueup to ordering and associates. Now, since the pj ’s are odd primes we cannothave xj = ±yj for 1 ≤ j ≤ r−1. One can check that (xj , yj) and (xj ,−yj) arenot associates and (xj , yj), (xk, yk) are not associates for j 6= k. So we havetwo points to choose from for each pj , namely (xj , yj) and (xj ,−yj), giving2r−1 choices for (x, y). None of the factors are associates so these choicesfor (x, y) are all distinct. If we multiply a given (x, y) by a unit then we getfour different values. So we get 4.2r−1 = 2r+1 distinct points (x, y) each withlength√m. So these give all possible required distances by Theorem 4.3.4.The units are torsion points of R (they have finite multiplicative order inR) so they don’t affect the rank.Going back to unit distances, if we take the complex numberszj = m−1/(2r−2)(xj + iyj), wj = m−1/(2r−2)(xj − iyj)for 1 ≤ j ≤ r − 1 then these generate the multiplicative group of unitdistances in the configuration. Thus the unit distances come from a multi-plicative subgroup of C∗ of rank at most r − 1. So we just need to bound rfrom above.We do this by looking at the inequality p1 . . . pr−1 ≤ n/4. Taking log-arithms we get ϑ4,1(pr−1) ≤ log(n/4). By Theorems 4.3.2 and 4.3.3 wegetpr−12√2≤ log(n/4).By the remark after Theorem 4.3.1 we get(r − 1) log(r − 1)2√2≤ 2√2 log(n/4).574.3. Analysis of Erdo˝s’ lower boundSolving for r we getr ≤16 log nlog log n.Thus the unit distances come from a multiplicative subgroup of rank at mostr − 1 ≤ 16 log n/ log logn− 1. Since16 log nlog logn− 1 ≤ c log nfor large n this configuration is covered by Theorem 4.1.2.58Chapter 5Combinatorial applicationsof the Subspace Theorem5.1 IntroductionThe Subspace Theorem has appeared in various forms and been adaptedand improved over time. Its applications include diophantine approxima-tion, results about integral points on algebraic curves and the constructionof transcendental numbers. But its usefulness extends beyond the realmsof number theory. Other applications of the Subspace Theorem include lin-ear recurrence sequences and finite automata. In fact, these structures areclosely related to each other and the construction of transcendental numbers.The Subspace Theorem also has a number of remarkable combinatorialapplications. We have already seen its use for the unit distance problem.The purpose of this chapter is to give a survey of some other applicationsincluding sum-product estimates and bounds on line configurations withfew distinct intersection points. The presentation will be from the point ofview of a discrete mathematician. We will state a number of variants of theSubspace Theorem below but we will not prove any of them as the proofsare beyond the scope of this work. We have already seen a proof of Mann’sTheorem and its corollary in Section 3.3. The corollary of Mann’s Theoremalso has applications to combinatorics and can be considered as a specialcase of the Subspace Theorem.Wolfgang M. Schmidt was the first to state and prove a variant of theSubspace Theorem in 1972 [55]. His theorem has been extended multipletimes and has played a very important role in modern number theory. Beforewe state the Subspace Theorem we need some definitions. A linear form isan expression of the form L(x) = a1x1 + a2x2 + · · ·+ anxn where a1, . . . , anare constants and x = (x1, . . . , xn). A collection of linear forms is linearlyindependent if none of them can be expressed as a linear combination ofthe others. A complex number is algebraic if it is a root of a univariatepolynomial with rational coefficients. Given x = (x1, . . . , xn) we define the595.1. Introductionmaximum norm of x:‖x‖ = max(|x1|, . . . , |xn|).Theorem 5.1.1 (Subspace Theorem I). Suppose we have n linearly inde-pendent linear forms L1, L2, . . . , Ln in n variables with algebraic coefficients.Given ε > 0, the non-zero integer points x = (x1, x2, . . . , xn) satisfying|L1(x)L2(x) . . . Ln(x)| < ‖x‖−εlie in finitely many proper linear subspaces of Qn.This generalises the Thue-Siegel-Roth Theorem on the approximation ofalgebraic numbers [54] to higher dimensions.Theorem 5.1.1 has been extended in various directions by many authorsincluding Schmidt himself, Schlickewei, Evertse, Amoroso and Viada. Ana-logues have been proved using p-adic norms and over arbitrary number fieldsand bounds on the number of subspaces required have been found. Thesebounds depend on the degree of the number field and the dimension. Forsome of these results and more information see [29], [30] and [3].Now we give a p-adic version of the Subspace Theorem that we will use inthe next section. Given a prime p, the p-adic absolute value is denoted |x|pand satisfies |p|p = 1/p. |x|∞ denotes the usual absolute value so |x|∞ = |x|.We may refer to ∞ as the infinite prime.Theorem 5.1.2 (Subspace Theorem II). Suppose S = {∞, p1, . . . , pt} isa finite set of primes, including the infinite prime. For every p ∈ S letL1,p, . . . , Ln,p be linearly independent linear forms in n variables with alge-braic coefficients. Then for any ε > 0 the solutions x ∈ Zn of∏p∈Sn∏i=1|Li,p(x)|p ≤ ‖x‖−εlie in finitely many proper linear subspaces of Qn.The power and utility of the Subspace Theorem is already evident inthe above forms but there is a corollary, often itself called the SubspaceTheorem, which makes even more applications possible. We have alreadyseen this version in Chapter 4 but we state it here for completeness. Thebound given is due to Amoroso and Viada [3].605.2. Number-theoretic applicationsTheorem 5.1.3 (Subspace Theorem III). Given an algebraically closedfield K and a multiplicative subgroup Γ of K∗ of finite rank r, supposea1, a2, . . . , an ∈ K∗. Then the number of solutions of the equationa1z1 + a2z2 + · · ·+ anzn = 1 (5.1)with zi ∈ Γ and no subsum on the left-hand side vanishing is at mostA(n, r) ≤ (8n)4n4(n+nr+1).The structure of this paper will be as follows. In the next section we givetwo well known applications of the Subspace Theorem. Namely, we give anexample of showing that a number is transcendental and a result showingthat certain linear recurrence sequences can only have finitely many zeroterms. In Section 5.3 we give combinatorial applications. These include asum-product estimate of Chang for sets with small product set and a boundon line configurations with few distinct intersections of Chang and Solymosi.5.2 Number-theoretic applications5.2.1 Transcendental numbersAdamczewski and Bugeaud showed that all irrational automatic numbersare transcendental using the Subspace Theorem. An automatic number isa number for which there exists a positive integer b such that when thenumber is written in b-ary form it is the output of a finite automaton withinput the nonnegative integers written from right to left. For more detailssee [1] or [8].Here we will use a method similar to the proof of Theorem 3.3 in [8] toshow:Theorem 5.2.1. The number α given by the infinite sumα =∑n≥1122nis transcendental.Kempner showed in the early twentieth century that a large class of num-bers defined similarly to α are transcendental [39]. The Subspace Theoremprovides a tidy proof of this fact.615.2. Number-theoretic applicationsProof of Theorem 5.2.1. Consider the binary expansion:α =14+116+1256+165536+ · · · = 0.0101000100000001 . . .2 .So the binary expansion of α consists of sections of zeros of increasing lengthseparating solitary ones. Thus the expansion is not periodic and hence αis not rational. We let bn be the string given by the first n digits of thisexpansion. One can check that each bn has two disjoint substrings of zerosof length n/8.Assume α is not transcendental. Then it is algebraic. Now each bn startswith a string AOBO, where O is a string of zeroes, the length of O is atleast n/8 and A and B might have length zero. We will use the rationalnumber represented in base 2 by 0.AOBOBO . . . to approximate α. Callthis number pi. Thenpi =M2a(2b − 1)where M ∈ Z and a and b are the lengths of the strings A and OB respec-tively. Clearly b ≥ n/8 and a+ b ≤ n since AOB is a substring of bn. Sinceα starts with bn we have|α− pi| ≤12a+b+n/8=⇒ |2a+bα− 2aα−M | ≤12n/8.Now we apply the Subspace Theorem in the form given in Theorem 5.1.2.We let S = {2,∞} andL1,∞(x) = x1, L2,∞(x) = x2, L3,∞(x) = αx1 − αx2 − x3,L1,2(x) = x1, L2,2(x) = x2, L3,2(x) = x3.Note that by our assumption that α is not transcendental the linear formL3,∞ has algebraic coefficients. Let x = (2a+b, 2a,M). Now |M | ≤ 2a+bsince 0 < pi < 1. So ‖x‖ ≤ 2a+b ≤ 2n. Multiplying the absolute values ofthe linear forms together we get∏p∈S3∏i=1|Li,p(x)| = |2a|2|2a|∞|2a+b|2|2a+b|∞|M |2|2a+bα− 2aα−M |∞≤12n/8≤1‖x‖1/8.625.2. Number-theoretic applicationsThe first inequality holds because |α− pi| ≤ 2−a−b−n/8 and |2|2|2|∞ = 1.We can do this for each n and b = b(n) increases as n increases sinceb ≥ n/8. Thus infinitely many of the vectors x = x(n) are distinct. ByTheorem 5.1.2 these vectors are contained in finitely many subspaces of Q3.Thus one of these subspaces contains infinitely many of them. That is, thereexist c, d, e ∈ Q such thatc2a(n) + d2a(n)+b(n) + eM(n) = 0for infinitely many n. The coefficient e cannot be zero since b(n) → ∞ asn → ∞. Dividing by 2a(n)(2b(n) − 1) and taking limits we get α = −d/e soα is rational. This is a contradiction. Thus α must be transcendental.5.2.2 Linear recurrence sequencesA linear recurrence sequence is a sequence of numbers where the first fewterms are given and the higher order terms can be found by a recurrencerelation. A famous example is the Fibonacci sequence {Fn} where F0 =0, F1 = 1 and Fn = Fn−1+Fn−2 for n ≥ 2. More formally, a linear recurrencesequence consists of constants a1, . . . , ak in a field K for some k > 0 alongwith a sequence {Rm}∞m=0 with Ri ∈ K for 0 ≤ i ≤ k − 1 andRn = a1Rn−1 + a2Rn−2 + · · ·+ akRn−k, for n ≥ k.If {Rm} is not expressible by any shorter recurrence relation then it is saidto have order k. In this case ak 6= 0.We are interested in the structure of the zero set of a linear recurrencesequence. This is the setS({Rm}) = {i ∈ N : Ri = 0}.The Skolem-Mahler-Lech Theorem states that this set consists of the unionof finitely many points and arithmetic progressions [43]. Schmidt has givena quantitative bound for this theorem using various tools including the Sub-space Theorem [56].We will show a special case of this theorem using Theorem 5.1.3. We willrestrict our attention to simple nondegenerate linear recurrence sequences.To define such sequences we need to define the companion polynomial of therecurrence sequence. If {Rm} is given as above then the companion polyno-mial of {Rm} is C(x) = xk−a1xk−1−· · ·−ak−1x−ak. Suppose the roots ofthis polynomial are α1, . . . , α` with multiplicity b1, . . . , b` respectively. Eachαi is nonzero since ak 6= 0. If the companion polynomial has k distinct roots635.2. Number-theoretic applicationsit is called simple. If αi/αj is not a root of unity for any i 6= j then thesequence is called nondegenerate. A version of this theorem was given in[29]. The improved bound given here is due to Amoroso and Viada [4].Theorem 5.2.2. Suppose {Rm} is a simple nondegenerate linear recurrencesequence of order k with complex coefficients. Then|S({Rm})| ≤ (8k)8k6 .Proof. We can express the recurrence relation using a matrix equation:a1 a2 . . . ak−1 ak1 0 . . . 0 00 1 . . . 0 0....... . .......0 0 . . . 1 0n Rk−1Rk−2...R0=Rk−1+nRk−2+n...Rn. (5.2)We call the k × k matrix above A. The characteristic polynomial of A isgiven byχ(λ) = (−1)k(λk − a1λk−1 − · · · − ak).This is the same, up to sign, as the companion polynomial of {Rm}. Thus Ahas distinct nonzero eigenvalues and so can be diagonalized. So A = PDP−1for some invertible k × k matrix P andD =α1 0 . . . 00 α2 . . . 0....... . . 00 0 . . . αk.So Dn is a diagonal matrix with αni in the i-th row and column. Thus, multi-plying out PDnP−1 we see that every element of An is a linear combinationof the n-th powers of the αi’s. Now, by the matrix equation in (5.2) we seethat Rn is given by the k-th row of An multiplied by [Rk−1, Rk−2, . . . , R0]Tand soRn = c1αn1 + c2αn2 + · · ·+ ckαnk for every n ≥ k.Then applying Theorem 5.1.3 to the equation c1x1 + c2x2 + · · ·+ ckxk = 0with solutions from the group of rank at most k generated by {α1, . . . , αk}we get that the number of solutions is at mostA(k, k) ≤ (8k)4k4(k+k2+1) ≤ (8k)8k6.Since the sequence is nondegenerate we cannot have two values n, n′ givingthe same value for αni and αn′i for each i, hence each solution correspondsto a unique value from S({Rm}).645.3. Combinatorial applications5.3 Combinatorial applicationsThe corollary of the Subspace Theorem given in Theorem 5.1.3 gives a boundon the number of nondegenerate solutions of a linear equation from a mul-tiplicative group with rank not too large. What happens if the group inquestion has rank zero? This corresponds to solutions that are roots ofunity. The corollary can then be seen as a generalisation of Corollary 3.3.3,which is the corollary of Mann’s Theorem that we used to bound rationaldistances in Chapter 3.We mentioned before that the Subspace Theorem can be considered asa generalisation of the Thue-Siegel-Roth Theorem but Mann’s result pro-vides another possible starting point for the development of the SubspaceTheorem. The roots of unity give a relatively simple example of an infinitemultiplicative group.Although these results were developed in different fields and for verydifferent problems they seem to provide just what is required for manycombinatorial problems. We have seen one such application already andwill provide a few more below.5.3.1 Sum-product estimatesThe theory of sum sets and product sets plays an important part in combi-natorics and additive number theory. The goal of the field is to show thatfor any finite subset of a field either the sum set or the product set is large.We will focus on the complex numbers.Formally, given a set A ⊂ C, the sum set, denoted by A+A, and productset, denoted by AA, areA+A := {a+ b : a, b ∈ A}, AA := {ab : a, b ∈ A}.Note that|A| ≤ |A+A|, |AA| ≤(|A|+ 12)=|A|22+|A|2.The following long standing conjecture of Erdo˝s and Szemere´di [28] hasled to much work in the field.Conjecture 5.3.1. Let ε > 0 and A ⊂ Z with |A| = n. Then|A+A|+ |AA| ≥ Cn2−ε.655.3. Combinatorial applicationsThis conjecture is still out of reach. The best known bound, which holdsfor real numbers and not just integers, is Cn4/3−o(1) due to Solymosi [58].A similar bound was proved recently by Konyagin and Rudnev in [40].Chang showed that when the product set is small the Subspace The-orem can be used to show that the sum set is large [10]. The followingreformulation of Chang’s observation is due to Andrew Granville.Theorem 5.3.2. Let A ⊂ C with |A| = n. Suppose |AA| ≤ Cn. Then thereis a constant C ′ depending only on C such that|A+A| ≥n22+ C ′n.We will present a proof of Theorem 5.3.2 below. To use the SubspaceTheorem we need a multiplicative subgroup with finite rank to work with.The following lemma of Freiman, which appears as Lemma 1.14 in [31],provides this.Lemma 5.3.3 (Freiman). Let A ⊂ C. If |AA| ≤ C|A| then A is a subset ofa multiplicative subgroup of C∗ of rank at most r(C).Proof of Theorem 5.3.2. We consider solutions of x1 + x2 = x3 + x4 withxi ∈ A. A solution of this equation corresponds to two pairs of elements fromA that give the same element in A + A. Let us suppose that x1 + x2 6= 0(there are at most |A| = n solutions of the equation x1 + x2 = 0 withx1, x2 ∈ A.)First we consider the solutions with x4 = 0. Then by rearranging we getx1x3+x2x3= 1. (5.3)By Lemma 5.3.3 and Theorem 5.1.3 there are at most s1(C) solutions ofy1+y2 = 1 with no subsum vanishing. Each of these gives at most n solutionsof (5.3) since there are n choices for x3. There are only two solutions ofy1 + y2 = 1 with a vanishing subsum, namely y1 = 0 or y2 = 0, and each ofthese gives n solutions of (5.3). So we have a total of (s1(C) + 2)n solutionsof (5.3).For x4 6= 0 we getx1x4+x2x4−x3x4= 1. (5.4)Again by Freiman’s Lemma and the Subspace Theorem, the number of so-lutions of this with no vanishing subsum is at most s2(C)n. If we have avanishing subsum then x1 = −x2 which is a case we excluded earlier or665.3. Combinatorial applicationsx1 = x3 and then x2 = x4, or x2 = x3 and then x1 = x4. So we get at most2n2 solutions of (5.4) with a vanishing subsum (these are the x1+x2 = x2+x1identities.)So, in total, we have at most 2n2 + s(C)n solutions of x1 + x2 = x3 + x4with xi ∈ A. Suppose |A + A| = k and A + A = {α1, . . . , αk}. We mayassume that α1 = 0. Recall that we ignore sums ai + aj = 0. LetPi = {(a, b) ∈ A×A : a+ b = αi}, 2 ≤ i ≤ k.Thenk∑i=2|Pi| ≥ n2 − n = n(n− 1).Also, a solution of x1 +x2 = x3 +x4 corresponds to picking two values fromPi where x1 + x2 = αi. Thus2n2 + s(C)n ≥k∑i=2|Pi|2 ≥1k − 1(k∑i=2|Pi|)2≥n2(n− 1)2k − 1by the Cauchy-Schwarz inequality. The bound for k follows.5.3.2 Line configurations with few intersectionsA number of other combinatorial results follow from the Subspace Theorem.We give one more of these, from combinatorial geometry. This is similarto a result due to Chang and Solymosi [11]. A complex line is a line inthe complex plane. Specifically, a complex line is given by an equationax+ by = c where a, b, c ∈ C and x and y are the (complex) coordinates inC2. Given two lines L and M we denote their intersection point by L ∩M .Theorem 5.3.4. Let C > 0. Then there exists c > 0 such that for anyn + 3 lines L1, L2, L3,M1, . . . ,Mn in C2, with the Li not all parallel andL1 ∩ L2, L1 ∩ L3 and L2 ∩ L3 distinct the following holds. If the number ofdistinct intersection points Li ∩Mj , 1 ≤ i ≤ 3, 1 ≤ j ≤ n, is at most C√nthen any line L /∈ {L1, L2, L3} has at least cn distinct intersection pointsL ∩Mj , 1 ≤ j ≤ n.This is a structure result. We have already mentioned other structureresults in the form of Beck’s Theorem and the results of Elekes and Ro´nyaiand their extensions from Chapter 2.We do not prove Theorem 5.3.4 completely but only give a sketch ofhow it follows from the Subspace Theorem. We don’t try to find an efficient675.3. Combinatorial applicationsquantitative version here and we don’t explain the methods used in detail.The techniques applied are standard methods in additive combinatorics. Allthe details can be found in [65]. The proof requires the Szemere´di RegularityLemma [63] and the Balog-Szemere´di Theorem [6].Apply a projective transformation which moves L1 to the x-axis, L2 to they-axis, and L3 to the horizontal line y = 1. The three lines have distinctintersection points thus such a transformation exists. Let us denote thex-coordinates of L1 ∩Mi and L3 ∩Mj by xi and yj respectively. The twosets of x-coordinates are denoted by X and Y. Define a bipartite graph withvertices given by the x-coordinates of the intersection points of the linesMi with L1 and L3 (with vertex sets X and Y without multiplicity.) Twopoints are connected by an edge in the graph if they are connected by aline Mj . This is a bipartite graph on at most C√n vertices with n edges.Using Szemere´di’s Regularity Lemma one can find a regular (random-like)bipartite graph, G, with at least c′n edges and vertex sets V1 ⊂ X andV2 ⊂ Y. If Mi∩L2 is the point (0, α) then xi/yi = α/(α−1), or equivalentlyxi = αyi/(α − 1). The Balog-Szemere´di Theorem and Freiman’s Lemmaimply that there are large subsets X ′ ⊂ V1 and Y ′ ⊂ V2 so that X ′ andY ′ are subsets of a multiplicative subgroup of C∗ of rank at most r(C). AsG is regular, the subgraph spanned by X ′, Y ′ still has at least some c′′nedges. We show that the lines represented by these c′′n edges cannot havehigh multiplicity intersections outside of L1, L2, L3. If (a, b) is a point of Miconnecting two points of X ′ and Y ′ then (a−xi)/(a−yi) = b/(b−1), whichgives the solution (xi, yi) to the equation cx+ dy = 1 if a 6= 0, b 6= 0, 1. Herec, d depend on a and b only. As xi and yi are from a multiplicative group ofbounded rank, we have a uniform bound, B, on the number of lines betweenX ′ and Y ′ which are incident to (a, b). There are c′′n lines connecting atmost C√n points. No more than C√n/2 of them might be parallel to anygiven line. Any line intersects at least c′′n−C√n of them. Any intersectionpoint outside of the lines L1, L2, and L3 is incident to at most B lines, sothere are at least cn distinct intersection points L∩Mj , 1 ≤ j ≤ n, with anyother line.We are unaware of any proof of this fact without the Subspace Theorem.68Chapter 6ConclusionWe have given a number of results in this thesis using a wide range ofdifferent techniques from various fields. All of the problems covered havea rich history and background and have been studied by many researchers.Strong progress has been made towards these problems but many questionsstill remain and a number of the results have the potential to be altered orimproved.6.1 Surfaces containing many points of acartesian productOur extensions of the Elekes-Ro´nyai Theorem give results on asymmetriccartesian products and in one dimension higher. For the first case one couldask if even more asymmetric cartesian products can be considered. We knowthat Theorem 2.1.6 cannot be improved by much because of the constructiongiven in Section 2.5.3 but we could not find similar constructions for ourother theorems and it is believed that these results are not tight. We knowthis is true for certain polynomials as can be seen in the best bounds forPurdy’s Conjecture.For our higher dimensional cases we used similar techniques. But werequired an additional tool, namely the special case of the Schwartz-ZippelLemma. We believe that a similar method should work for even higherdimensional versions but we did not perform the analysis.Our main tool in improving Elekes and Ro´nyai’s result was Lemma 2.2.4,our generalised line lemma. The improvement in this lemma gave the im-proved bounds. The rest of the proof remained the same. We could not findany other places in the proof to improve the bounds. Perhaps a differentapproach to the problem could give better bounds. Our proof of the gen-eralised line lemma went along the same lines as that of Elekes. We justprovided a more careful analysis.The line lemma requires that all the lines are cn-rich on an n×n cartesianproduct. If we cannot guarantee this richness then none of the methods696.2. The Erdo˝s unit distance problemwork.As mentioned in Chapter 2, our generalised line lemma and all the otherelements of our proofs extend to curves over C.All our results hold for graphs of polynomials. But what if we insteadconsider implicit surfaces? Elekes and Szabo´ have given a version of theElekes-Ro´nyai Theorem in this case when the surface contains cn2−γ pointsof an n×n×n cartesian product for some small absolute constant γ [23, 24].The proof requires tools from algebraic geometry. Using our generalised linelemma it should be possible to extend this result as well.Regarding applications of the Elekes-Ro´nyai Theorem, much work hasbeen done on Purdy’s Conjecture. Around the same time as his work withRo´nyai, Elekes showed using a similar method, but tailored for the specificpolynomial from the problem, that Purdy’s Conjecture holds if there areat most cn5/4 distinct distances [19]. He conjectured that the same shouldhold for cn2−δ distinct distances. Very recently Sharir, Sheffer and Solymosihave shown that the number of distinct distances can be raised to cn4/3[57]. Their method is very different. They show that the collinear pointsets give rise to a collection of hyperbolas with two degrees of freedom andmultiplicity-type 2 and then they use the Pach-Sharir Theorem.6.2 The Erdo˝s unit distance problemWe have dealt with two special cases of the unit distance problem, thesecond generalising the first. For our stronger version using the corollary ofthe Subspace Theorem we have shown that the lower bound construction issatisfied by our result. This is promising in that it suggests that perhapsthe unit distances in any maximal configuration should have a special groupstructure. Possible future work could be to try and understand the structureof maximal unit distance sets and to show that the unit distances come froma group with “low” rank.During the 27th European Workshop on Computational Geometry, 2011,Jiˇr´ı Matousˇek highlighted a number of results he believed to be importantto the field of Discrete Geometry [47]. Our special case of the unit distanceproblem using Mann’s Theorem was mentioned showing the relevance of thiswork, and its subsequent generalisation, to the field.Using Mann’s Theorem we were also able to get bounds when consideringrational distances. We could not get similar results using the SubspaceTheorem as it depends on the coefficients of the linear equation.Instead of considering the Euclidean plane we could ask for the number706.3. Combinatorial applications of the Subspace Theoremof unit distances in other spaces. Matousˇek has given many results on theunit distance problem in different metric spaces [45]. In particular he hasshown that there are at most cn log n log logn unit distances for “most”norms on the plane. So the Euclidean norm is special in a way.Returning to the Euclidean distance but moving to higher dimensionsthe problem changes significantly. For R4 and higher the number of unitdistances increases dramatically and the problem is much simpler. Thefollowing construction shows this and was originally communicated to Erdo˝sby Lenz. Consider two orthogonal circles in R4 of radius 1/√2 and with thesame centre. For exampleC1 = {(x1, x2, 0, 0) : x21 + x22 = 1/2}, C2 = {(0, 0, x3, x4) : x23 + x24 = 1/2}.The distance between (x1, x2, 0, 0) and (0, 0, x3, x4) is√1/2 + 1/2 = 1. Thusevery point on the first circle has unit distance to every point on the secondcircle. So taking n/2 points on each circle we see that we have at least n2/4unit distances. A similar argument can be used in higher dimensions.In R3 the maximum number of unit distances is at least cn4/3 log log n.This was again shown by Erdo˝s using a scaled portion of a three dimensionalinteger lattice and using number-theoretic techniques [26]. The best knownupper bound is cn3/2 due independently to Kaplan et al. [37] and Zahl [69]using the polynomial partitioning method of Guth and Katz. These slightlyimproved the previous bound due to Clarkson et al. [14]. This might be aninteresting direction to consider.The unit distance problem is also interesting in C2. The same upperbound is possible since the Szemere´di-Trotter Theorem holds over C2 [67],[68]. Theorem 4.1.2, our main result of Chapter 4, holds in the complex planesince all elements of the proof including the Subspace Theorem extend tothe complex case.6.3 Combinatorial applications of the SubspaceTheoremA number of applications of the Subspace Theorem have been given and itis believed that many more should be possible. It is an extremely powerfultheorem that deserves to be recognised in yet another field. It has been usedto give relatively simple proofs of previously known results in combinatoricsand it has provided proofs to previously open problems. The generality ofthe Subspace Theorem means that it often gives results for complex numberswhere many other methods in combinatorics are restricted to the real case.716.3. Combinatorial applications of the Subspace TheoremIt seems likely that the Subspace Theorem can shed more light on sum-product problems. Chang’s result on the size of the sum set and product setgiven in Section 5.3.1 relies on Freiman’s Lemma saying that if the productset is small then the elements of A should come from a group of boundedrank. If we have that the elements of A come from a group of rank at mostc log |A| then |A + A| is at least |A|2−ε. So one could try and show that ifthe product set has size at most |A|2−δ then A comes from a group withrank at most c log |A|. This would prove Conjecture 5.3.1.72Bibliography[1] B. Adamczewski and Y. Bugeaud. On the complexity of algebraic num-bers I: Expansions in integer bases. Annals of Mathematics, 165:547–565, 2007.[2] G. Amirkhanyan, A. Bush, E. Croot, and C. Pryby. On richlines in general position in grids. Presented in “Additive Com-binatorics in Paris 2012”, Institut Henri Poincare´, July 2012.http://caparis2012en.files.wordpress.com/2011/05/ernie croot.pdf.[3] F. Amoroso and E. Viada. Small points on subvarieties of a torus. DukeMathematical Journal, 150(3):407–442, 2009.[4] F. Amoroso and E. Viada. On the zeros of linear recurrence sequences.Acta Arithmetica, 147:387–396, 2011.[5] T.M. Apostol. Introduction to Analytic Number Theory, chapter 4.5:Inequalities for pi(n) and pn, pages 82–85. Springer, 1976.[6] A. Balog and E. Szemere´di. A statistical theorem of set addition. Com-binatorica, 14:263–268, 1994.[7] J. Beck. On the lattice property of the plane and some problems ofDirac, Motzkin, and Erdo˝s in combinatorial geometry. Combinatorica,3(3):281–297, 1983.[8] Y. Bilu. The Many Faces of the Subspace Theorem (after Adamczewski,Bugeaud, Corvaja, Zannier...). Se´minaire Bourbaki, Expose´ 967, 59e`meanne´e (2006-2007); Aste´risque 317 (2008), 1-38., May 2007.[9] W. Brass, W. Moser, and J. Pach. Research Problems in Discrete Ge-ometry. Springer, 2006.[10] M.-C. Chang. Sum and product of different sets. Contributions toDiscrete Mathematics, 1(1), 2006.73Bibliography[11] M.-C. Chang and J. Solymosi. Sum-product theorems and incidencegeometry. Journal of the European Mathematical Society, 9(3):545–560,2007.[12] F.K.R. Chung. The number of different distances determined by npoints in the plane. Journal of Combinatorial Theory, Series A, 36:342–354, 1984.[13] F.K.R. Chung, E. Szemere´di, and W.T. Trotter. The number of dif-ferent distances determined by a set of points in the Euclidean plane.Discrete and Computational Geometry, 7:1–11, 1992.[14] K. Clarkson, H. Edelsbrunner, M. Sharir, and E. Welzl. Combinatorialcomplexity bounds for arrangements of curves and surfaces. Discreteand Computational Geometry, 5:99–160, 1990.[15] J.H. Conway and A.J. Jones. Trigonometric diophantine equations (onvanishing sums of roots of unity). Acta Arithmetica, 30:229–240, 1976.[16] P. Corvaja and U. Zannier. Applications of the subspace theorem to cer-tain diophantine problems. In H.P. Schlickewei, Schmidt K., and R.F.Tichy, editors, Diophantine Approximation, volume 16 of Developmentsin Mathematics, pages 161–174. Springer Vienna, 2008.[17] N.G. de Bruijn. Asymptotic Methods in Analysis. North-Holland, 1961.[18] Gy. Elekes. On linear combinatorics, I. Combinatorica, 17(4):447–458,1997.[19] Gy. Elekes. A note on the number of distinct distances. PeriodicaMathematica Hungarica, 38:173–177, 1999.[20] Gy. Elekes. Sums versus products in number theory, algebra and Erdo˝sgeometry. In Paul Erdo˝s and his Mathematics II, volume 11 of BolyaiSociety Mathematical Studies, pages 241–290. 2002.[21] Gy. Elekes and L. Ro´nyai. A combinatorial problem on polynomialsand rational functions. Journal of Combinatorial Theory, Series A,89:1–20, 2000.[22] Gy. Elekes and M. Sharir. Incidences in three dimensions and dis-tinct distances in the plane. Combinatorics, Probability and Computing,20(4):571–608, 2011.74Bibliography[23] Gy. Elekes, M. Simonovits, and E. Szabo´. A combinatorial distinctionbetween unit circles and straight lines. Combinatorics, Probability andComputing, 18:691–705, 2009.[24] Gy. Elekes and E. Szabo´. How to find groups? (and how to use themin Erdo˝s geometry?). Combinatorica, 32:537–571, 2012.[25] P. Erdo˝s. On sets of distances of n points. American MathematicalMonthly, 53(5):248–250, May 1946.[26] P. Erdo˝s. On sets of distances of n points in euclidean space. Magy.Tud. Akad. Mat. Kut. Int. Ko¨zl., 5:165–169, 1960.[27] P. Erdo˝s and G.B. Purdy. Some extremal problems in geometry, IV. InProceedings of The Seventh Southeastern Conference on Combinatorics,Graph Theory, and Computing, pages 307–322, 1976.[28] P. Erdo˝s and E. Szemere´di. On sums and products of integers. InStudies in Pure Mathematics, pages 213–218. Birkha¨user, 1983.[29] J.-H. Evertse and H.P. Schlickewei. The absolute subspace theoremand linear equations with unknowns from a multiplicative group. InK. Gyo¨ry, H. Iwaniec, and J. Urbanowicz, editors, Number theory inprogress: Proceedings of the international conference of number theoryin honour of the 60th birthday of Andrzej Schinzel, 1999.[30] J.-H. Evertse, H.P. Schlickewei, and W.M. Schmidt. Linear equationsin variables which lie in a multiplicative group. Annals of Mathematics,155(3):807–836, 2002.[31] G.A. Freiman. Foundations of a Structural Theory of Set Addition.Translations of Mathematical Monographs. American Mathematical So-ciety, 1973.[32] William Fulton. Algebraic Curves: An Introduction to Algebraic Ge-ometry. 1969.[33] J. Garibaldi, A. Iosevich, and S. Senger. The Erdo˝s Distance Problem,volume 56 of Student Mathematical Library. American MathematicalSociety Press, 2011.[34] L. Guth and N.H. Katz. On the Erdo˝s distinct distances problem inthe plane. Preprint, arXiv:1011.4105, 2010.75Bibliography[35] H. Iwaniec and E. Kowalski. Analytic Number Theory. Volume 53 ofAMS Colloquium Publications, 2004.[36] S. Jukna. Extremal Combinatorics. Springer, 2011.[37] A. Kaplan, J. Matousˇek, Z. Safernova´, and M. Sharir. Unit distances inthree dimensions. Combinatorics, Probability and Computing, 21:597–610, 2012.[38] N.H. Katz and G. Tardos. A new entropy inequality for the Erdo˝sdistance problem. 342:119–126, 2004.[39] A.J. Kempner. On transcendental numbers. Transactions of the Amer-ican Mathematical Society, 17(4):476–482, 1916.[40] S.V. Konyagin and M. Rudnev. On new sum-product type estimates.Preprint, arXiv:1207.6785, 2013.[41] J.H. Lambert. Observationes variae in mathesin puram. Acta Helvetica,physico-mathematico-anatomico-botanico-medica, 3:128–168, 1758.[42] S. Lang. Algebra. Addison-Wesley, 3rd edition, 1994.[43] C. Lech. A note on recurring series. Arkiv der Mathematik, 2:417–421,1953.[44] H.B. Mann. On linear relations between roots of unity. Mathematika,12:107–117, 1965.[45] J. Matousˇek. The number of unit distances is almost linear for mostnorms. Advances in Mathematics, 226:2618–2628, 2011.[46] J. Matousˇek. Lectures on Discrete Geometry. Springer, 2002.[47] J. Matousˇek. The dawn of an algebraic era in discrete geometry? Eu-roCG 2011, extended abstract, 2011.[48] J. McKay and S. Wang. An inversion formula for two polynomials intwo variables. Journal of Pure and Applied Algebra, 40:245–257, 1986.[49] H.L. Montgomery and R.C. Vaughan. Multiplicative number theory.I. Classical theory. Cambridge Studies in Advanced Mathematics, 97.Cambridge University Press, 2007.[50] L. Moser. On different distances determined by n points. AmericanMathematical Monthly, 59:85–91, 1952.76Bibliography[51] I. Niven, H.S. Zuckerman, and H.L. Montgomery. An introduction tothe theory of numbers. John Wiley & Sons, Inc., fifth edition, 1991.[52] J. Pach and M. Sharir. Repeated angles in the plane and related prob-lems. Journal of Combinatorial Theory, Series A, 59(1):12–22, 1992.[53] J. Pach and M. Sharir. On the number of incidences between points andcurves. Combinatorics, Probability and Computing, 7:121–127, 1998.[54] K.F. Roth. Rational approximations to algebraic numbers. Mathe-matika, 2(1):1–20, 1955.[55] W.M. Schmidt. Norm form equations. The Annals of Mathematics,Second Series, 96(3):526–551, 1972.[56] W.M. Schmidt. The zero multiplicity of linear recurrence sequences.Acta Mathematica, 182(2):243–282, 1999.[57] M. Sharir, A. Sheffer, and J. Solymosi. Distinct distances on two lines.Journal of Combinatorial Theory, Series A, 120(7):1732–1736, 2013.[58] J. Solymosi. Bounding multiplicative energy by the sumset. Advancesin Mathematics, 222(2):402–408, 2009.[59] J. Solymosi and C.D. To´th. Distinct distances in the plane. Discreteand Computational Geometry, 25:629–634, 2001.[60] J. Spencer, E. Szemere´di, and W. Trotter. Unit distances in the Eu-clidean plane. In B. Bollobas, editor, Graph Theory and Combinatorics:Proceedings of the Cambridge Combinatorial Conference, in Honour ofPaul Erdo˝s, pages 293–303. Academic Press, 1984.[61] A.H. Stone and J.W. Tukey. Generalized sandwich theorems. DukeMathematical Journal, 9:356–359, 1942.[62] L.A. Sze´kely. Crossing numbers and hard Erdo˝s problems in discretegeometry. Combinatorics, Probability and Computing, 6(3):353–358,1997.[63] E. Szemere´di. Regular partitions of graphs. In Proble`mes Combina-toires et The´orie des Graphes, pages 399–401, Orsay, 1978. ColloquesInternationaux C.N.R.S. (1976).[64] E. Szemere´di and W.T. Trotter. Extremal problems in discrete geom-etry. Combinatorica, 3(3-4):381–392, 1983.77Bibliography[65] T. Tao and V.H. Vu. Additive Combinatorics. Cambridge Studies inAdvanced Mathematics 105. Cambridge University Press, 2006.[66] G. Tardos. On distinct sums and distinct distances. Advances in Math-ematics, 180:275–289, 2003.[67] C.D. Toth. The Szemere´di-Trotter theorem in the complex plane.Preprint, arXiv:0305283, 2003.[68] J. Zahl. A Szemeredi-Trotter type theorem in R4. Preprint,arXiv:1203.4600, 2012.[69] J. Zahl. An improved bound on the number of point-surface incidencesin three dimensions. Contributions to Discrete Mathematics, 8(1):100–121, 2013.78

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items