Science, Faculty of
Mathematics, Department of
DSpace
UBCV
White, Ethan Patrick
Doctor of Philosophy - PhD
University of British Columbia
This dissertation is comprised of four articles, each related to a discrete extremal problem. Several topics appear in more than one chapter. These include polynomial methods, Fourier analysis, and combinatorial number theory. In Chapter 2 we prove that the number of directions contained in a set of the form A x B ⊂ AG(2,p) where p is prime, is at least |A||B| - min{|A|,|B|} + 2. Here A and B are subsets of GF(p) each with at least two elements and |A||B|<p. This bound is tight for an infinite class of examples. Our main tool is the use of the Rédei polynomial with Szőnyi's extension. In Chapter 3 we determine the optimal constant in a convolution inequality up to a 10⁻⁶ error. Furthermore, we prove that a unique minimizer exists. As a corollary, we obtain improvements on the maximum size of Bh(g) sets for (g,h) ∈ {(2,2),(3,2),(4,2),(1,3),(1,4)}. A combination of Fourier analysis and convex optimization is used to obtain the main result. In Chapter 4 we obtain a substantially improved lower bound for the minimum overlap problem asked by Erdős, very close to the best upper bound. Our approach uses elementary Fourier analysis to translate the problem to a convex optimization program. In Chapter 5 we study arrangements of intervals in R² for which many pairs are concyclic. We show that any set of intervals with many concyclic pairs must have underlying algebraic and geometric structure. In the most general case, we prove that the endpoints of many intervals belong to a single bicircular quartic curve.
Topics in Discrete AnalysisbyEthan Patrick WhiteM.Sc., The University of British Columbia, 2019A 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)May 2023© Ethan Patrick White, 2023The following individuals certify that they have read, and recommend to the Faculty ofGraduate and Postdoctoral Studies for acceptance, the dissertation entitled:Topics in Discrete Analysissubmitted by Ethan Patrick White in partial fulfillment of the requirements for the degreeof Doctor of Philosophy in Mathematics.Examining Committee:Jo´zsef Solymosi, Professor, Mathematics, UBCSupervisorRichard Anstee, Professor, Mathematics, UBCSupervisory Committee MemberAndrew Rechnitzer, Professor, Mathematics, UBCUniversity ExaminerBruce Shepherd, Professor, Computer Science, UBCUniversity ExaminerGa´bor Tardos, Professor, Alfre´d Re´nyi Institute of MathematicsExternal ExaminerAdditional Supervisory Committee Members:Joshua Zahl, Associate Professor, Mathematics, UBCSupervisory Committee MemberiiAbstractThis dissertation is comprised of four articles, each related to a discrete extremal problem.Several topics appear in more than one chapter. These include polynomial methods, Fourieranalysis, and combinatorial number theory.In Chapter 2 we prove that the number of directions contained in a set of the formA×B ⊂ AG(2, p), where p is prime, is at least |A||B|−min{|A|, |B|}+2. Here A and B aresubsets of GF (p) each with at least two elements and |A||B| < p. This bound is tight for aninfinite class of examples. Our main tool is the use of the Re´dei polynomial with Szo˝nyi’sextension.In Chapter 3 we determine the optimal constant in a convolution inequality up to a 10−6error. Furthermore, we prove that a unique minimizer exists. As a corollary, we obtain im-provements on the maximum size of Bh[g] sets for (g, h) ∈ {(2, 2), (3, 2), (4, 2), (1, 3), (1, 4)}.A combination of Fourier analysis and convex optimization is used to obtain the main result.In Chapter 4 we obtain a substantially improved lower bound for the minimum overlapproblem asked by Erdo˝s, very close to the best upper bound. Our approach uses elementaryFourier analysis to translate the problem to a convex optimization program.In Chapter 5 we study arrangements of intervals in R2 for which many pairs are concyclic.We show that any set of intervals with many concyclic pairs must have underlying algebraicand geometric structure. In the most general case, we prove that the endpoints of manyintervals belong to a single bicircular quartic curve.iiiLay SummaryThis dissertation focuses on discrete extremal problems. We study the minimum or maximumsize of a finite set, subject to constraints. Our results span the subject areas of number theoryand geometry. In Chapter 2 we use properties of special polynomials to estimate the numberof slopes in grids. A consequence is a reproduction of the best upper bound on the size ofPaley cliques. In Chapters 3 and 4 we use Fourier analysis to transfer a discrete problem toa continuous one. We formulate optimization problems that give improved estimates in oldproblems in combinatorial number theory. In Chapter 5, we use the seminal result of Guthand Katz on intersecting lines in three dimensions to study extremal configurations of linesegments in the plane.ivPrefaceThis dissertation is based on four articles: two collaborative and accepted in peer-reviewedjournals, as well as two single-authored and submitted to peer-reviewed journals. Apart fromstylistic changes, the main chapters of this dissertation are reproductions of the originalscited.• Chapter 2 is based on D. Di Benedetto, J. Solymosi, E. P. White, On the directionsdetermined by a Cartesian product in an affine Galois plane, Combinatorica 41 (2021),no. 6, 755–763 [13]. Studying directions in Cartesian products via Re´dei polynomialswas proposed by Jozsef Solymosi. Preliminary research discussions occurred jointly.Theorem 2.1 and Lemma 2.6 were formulated, proved, and written by me. Additionalwriting and formulation of corollaries was done jointly.• Chapter 3 is based on Erdo˝s’ minimum overlap problem [73], submitted for peer review.This work was undertaken alone.• Chapter 4,is based on An optimal L2 autoconvolution inequality [72], submitted forpeer review. This work was undertaken alone.• Chapter 5 is based on J. Solymosi, E. P. White, Concyclic intervals in the plane, toappear in Discrete & Computational Geometry [65]. The concept of mapping intervalsto lines in R3 to describe a combinatorial property was introduced in an earlier work,and is due to Jozsef Solymosi. The formulation of Theorem 5.2 and the analysiscarried out for its proof was done by me. Figure creation and main body writing wasalso done by me in consultation with Jozsef Solymosi. The introduction was writtencollaboratively.vContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Directions in finite geometries . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 An optimal L2 autoconvolution inequality . . . . . . . . . . . . . . . . . . . 51.3 Minimum overlap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4 Combinatorics of Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Directions in Finite Geometries . . . . . . . . . . . . . . . . . . . . . . . . . 142.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 Re´dei polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3 Directions in Cartesian products . . . . . . . . . . . . . . . . . . . . . . . . . 173 An optimal L2 autoconvolution inequality . . . . . . . . . . . . . . . . . . . 213.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Existence and uniqueness of the optimizer . . . . . . . . . . . . . . . . . . . 243.3 Useful identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.4 Quantitative results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.4.1 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . 303.4.2 Computing an upper bound . . . . . . . . . . . . . . . . . . . . . . . 323.4.3 Computing a lower bound . . . . . . . . . . . . . . . . . . . . . . . . 333.5 Number theoretic corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 35vi4 Minimum Overlap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.2 Outline of the proof of Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . 384.3 Properties of f, g,M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.3.1 Properties from Fourier analysis . . . . . . . . . . . . . . . . . . . . . 394.3.2 Properties using average values of M(x) on small intervals . . . . . . 434.4 Simplified linear program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.5 Full convex program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.5.1 Program output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.6 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565 Combinatorics of Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.2 The main result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.3 Set up: mapping intervals to lines . . . . . . . . . . . . . . . . . . . . . . . . 625.4 Proof of Theorem 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645.4.1 Concurrent lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.4.2 Coplanar lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655.4.3 Lines in a regulus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.5 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.5.1 C is a degenerate hyperbola . . . . . . . . . . . . . . . . . . . . . . . 705.5.2 C is a non-degenerate conic . . . . . . . . . . . . . . . . . . . . . . . 726 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.1 Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.2 Autoconvolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 766.3 Overlap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 766.4 Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79Appendix I: Minimum Overlap Program . . . . . . . . . . . . . . . . . . . . . . 85Primal program as a SOCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85Obtaining the Dual SOCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86Statement of SOCP dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90viiFeasibility verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90Reusing a feasible solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92Appendix II: Concyclic Intervals Curve . . . . . . . . . . . . . . . . . . . . . . 96viiiList of Tables1 Dissertation at a glance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Progress on the minimum overlap problem . . . . . . . . . . . . . . . . . . . 83 First values of {fk} for almost optimal f(x). . . . . . . . . . . . . . . . . . . 314 Constraint feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 Dual program output I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556 Dual program output II N, T,R = 25000, 7000, 10, and (q1, q2) = (−0.02, 0.02) 567 First Fourier cosine coefficients for lower and upper bound f(x). . . . . . . . 588 Variable expressions for SOCP . . . . . . . . . . . . . . . . . . . . . . . . . . 879 Data for SOCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8810 c-vectors with one nonzero entry . . . . . . . . . . . . . . . . . . . . . . . . . 9011 Variables for dual SOCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9112 Variable expressions for dual SOCP . . . . . . . . . . . . . . . . . . . . . . . 95ixList of Figures1 Comparison of D(λ) (upper curve) and λ2, the bound from [13] (lower curve).The three textures of the upper curve indicate the three cases of the defini-tion (1.2) of D(λ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Best 51-step function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Intervals forming trapezoids: five cases. . . . . . . . . . . . . . . . . . . . . . 124 Two pairs of concyclic intervals . . . . . . . . . . . . . . . . . . . . . . . . . 135 Degree 20 trigonometric polynomial shown in blue and its autoconvolutionshown in orange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Lower bound of 0.379005 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577 Degree 5 Fourier approximations of f(x),M(x) pairs. . . . . . . . . . . . . . 588 Two pairs of concyclic intervals . . . . . . . . . . . . . . . . . . . . . . . . . 599 An arrangement of intervals with the structure described in Theorem 5.2 Case2b. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6110 An arrangement of intervals with endpoints contained on a bicircular quartic.Every red-blue pair of intervals is concyclic. The bicircular quartic has theequation (x2 + y2)2 − 2 (4x+ y) (x2 + y2) + 8xy − 24y2 + 25 = 0. . . . . . . . 6111 Circular pencil of an interval. . . . . . . . . . . . . . . . . . . . . . . . . . . 6212 Case 1 of Theorem 5.2: Intervals corresponding to a set of concurrent lines inL. Both endpoints of intervals lie on a common circle. . . . . . . . . . . . . . 6513 Intersecting secants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6714 Case 2b of Theorem 5.2: Intervals corresponding to a set of coplanar lines in L. 6815 An arrangement of intervals with endpoints contained on a circular cubic.Every red-blue pair of intervals is concyclic. The lines containing intervalsfrom each family are concurrent at the green points. The circular cubic hasthe equation 120x (x2 + y2) + 160x2 + 300xy − 36y2 + 150x+ 9 = 0. . . . . . 7116 An arrangement of intervals with endpoints contained on an ellipse. Everyred-blue pair of intervals is concyclic. The intervals from the same family areparallel. The ellipse has the equation 4x2 + 9y2 = 32. . . . . . . . . . . . . . 72x17 An arrangement of intervals with endpoints contained on a bicircular quartic.Every red-blue pair of intervals is concyclic. The lines containing intervalsare all tangent to the parabola x2 + 2y = 0, shown in green. The bicircularquartic has the equation 2(x2 + y2)2 − 2 (x2 + y2) (3x+ 4y) − 24x2 − 16y2 +12xy + 36x+ 39y + 72 = 0. . . . . . . . . . . . . . . . . . . . . . . . . . . . 7318 An arrangement of intervals with endpoints contained on a bicircular quartic.Every red-blue pair of intervals is concyclic. The lines containing intervalsare all tangent to the hyperbola y2 − 4x2 − 1, shown in green. The bicircularquartic has the equation (x2 + y2)2+ 16x2 − 64y2 − 4. The figure has beenrotated 90 degrees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7419 A subset of the region in (h, p) space where opt(h, h, p, p) ≥ 0.379005. . . . 94xiAcknowledgementsMy graduate studies have benefited incalculably from the patient mentorship of my ad-visor Jo´zsef Solymosi. I thank him for introducing me to many beautiful problems andtechniques, maintaining a vibrant research group, and providing opportunities to interactwith members of the discrete community from abroad. You inspire me, Jo´zsef.I thank my committee members Richard Anstee and Joshua Zahl for their suggestionsthat have improved many drafts of my mathematical writing, including this one. I amalso grateful for the generous amount of time they have each spent providing me with re-search and career advice. I thank the other examiners of this thesis: Andrew Rechnitzer,Bruce Shepherd, and Ga´bor Tardos for their careful reading, insightful questions, and ap-preciation of the projects herein.Several of my doctoral projects have benefitted from excellent collaborators: GabrielCurrier, Daniel Di Benedetto, Ritesh Goenka, Richard Guy, Greg Martin, Kenneth Moore,Renate Scheidler, Jo´zsef Solymosi, and Kyle Yip. I thank you all for exciting discoveriesand instructive lessons. It has been an honour to be a member of the UBC mathematicsdepartment, and I am grateful to a long unnamed list of fellow students and faculty fornumerous helpful or happy conversations over the past years. I also thank the Killam Trustsfor financial support in the first two years of my doctorate.I thank the UBC Triathlon team for providing a way to balance many hours of sitting anda source of many cherished friendships. I am lucky to have a family away from home: thankyou to Jorge, Sandra, and Serena for many cheerful memories. To my family throughoutCanada and New Zealand, your support is very dear to me and I am profoundly gratefulfor it. In particular, I thank Emily and Maciek for their sense of adventure and humour,Grandma Pat for helping us all dream big, Grandpa John for my first mathematical lesson,and my parents Duncan and Melinda for all our time together, it means the world to me.Finally, to Ro: you brighten every day, no matter how hard the math gets. All that I dois buoyed by your relentless encouragement, boundless optimism, and fierce friendship.xiiDedicationTo my family, for their unwavering support.And to Ro, every day with you is a gift.xiii1 OverviewAn extremal problem asks to determine the minimum or maximum size of a set subject toconstraints. Within discrete mathematics, many extremal problems are studied in connec-tion with combinatorics, number theory, analysis, and geometry. Research in the subjectcan be classified into two main directions: estimating the size of maximum or minimumconfigurations, and determining the structure of optimal configurations.The contents of this dissertation are grouped into four main chapters, each relating to adifferent extremal problem. The central problems addressed by each chapter are summarizedin Table 1. Chapters 2, 3, and 4 cover topics in combinatorics, number theory, and analysis,and deal primarily in estimating the size of extremal sets. Chapter 5 lies in the subject ofextremal geometry, and our main theorem describes the algebraic and geometric structure ofextremal configurations. The follow subsections of this first chapter give brief introductionsto the chapters of this dissertation.Chapter Main topic2 Minimum number of directions determined by a cartesian product [13]3 Minimum L2 norm of an autoconvolution [73]4 Minimum size of overlap of complementary sets [72]5 Structure of sets of line segments with a combinatorial property on pairs [65]Table 1: Dissertation at a glance1.1 Directions in finite geometriesLet F be a field, and let U ⊂ F 2 be a finite set of ordered pairs. The set of directionsdetermined by U is defined to beDU ={b− da− c : (a, b), (c, d) ∈ U, (a, b) ̸= (c, d)}(1.1)considered as a subset of F ∪ {∞}, where ∞ is the vertical direction resulting from a = c.The theory of directions is well studied, particularly when F = GF (p) is a finite field and pis a prime—see for example [1, 68]. One of the most important results in the subject is the1following lower bound on the cardinality of DU , which was proved by Re´dei [56] in the case|U | = p and later extended by Szo˝nyi [68, Theorem 5.2] to any |U | ≤ p. Throughout we willdenote AG(2, p) the Desargusian affine plane.Theorem (Szo˝nyi [68]). Let p be a prime, and let U ⊂ AG(2, p) with 1 < |U | ≤ p. Theneither U is contained in a line, or U determines at least |U |+32directions.The main tool used in Re´dei and Szo˝nyi’s results are the properties of lacunary poly-nomials, these are polynomials with several consecutive coefficients equal to zero. Re´dei’smonograph [56], as well as Ball and Blokhuis’s chapter [1] contain many results on lacunarypolynomials and their applications. Understanding the possible sizes of |DU | and the associ-ated optimal point configurations has also been considered by several authors. Lova´sz andSchrijver proved that if |U | = p and |DU | = (p+ 3)/2, then U is an affine transformation ofthe set {(x, x p−12 ) : x ∈ GF (p)}. This result was later extended by Ga´cs.Theorem (Ga´cs [21]). For every prime p, besides lines and the example characterized byLova´sz and Schrijver, any set of p points in AG(2, p) determines at least ⌊2p−13⌋+1 directions.We combined Re´dei’s polynomial method with a simple variation of Stepanov’s methodto obtain the following bound for the number of directions determined by a Cartesian prod-uct. It improves Szo˝nyi’s bound by a factor of two up to lower order terms.Theorem 1.1 (Di Benedetto, Solymosi, EPW [13]). Let A,B ⊂ GF (p) be sets each of sizeat least two such that |A||B| < p. Then the set of points A × B ⊂ AG(2, p) determines atleast |A||B| −min{|A|, |B|}+ 2 directions.In Chapter 2 we give a full proof of Theorem 1.1. Let d > 1 be a divisor of p− 1 and letZd be a multiplicative subgroup of size d inside GF (p). If a set A satisfies A−A ⊂ Zd∪{0},then all of its directions are elements of Zd ∪ {0,∞}. Thus, as a corollary of Theorem 1.1,we obtain the following result, which was obtained earlier by Hanson and Petridis [31].Corollary 1.2 (Di Benedetto, Solymosi, EPW[13]). Let A ⊂ GF (p) be a set such thatA− A ⊂ Zd ∪ {0}. Then|A|(|A| − 1) ≤ d.In particular, if p is congruent to 1 modulo 4 and d = (p−1)/2 this gives an upper boundof (√2p− 1 + 1)/2 on the clique number of the Paley graph Gp. Recall that the vertices of2Gp are the elements of GF (p) with an edge between elements whose difference is a square inGF (p). Estimating the clique number of Paley graphs is a long-standing problem, and theupper bound stated above represents the most significant improvement to date.The bound of Theorem 2.1 is sometimes tight. For example if p = 41 and A ={0, 1, 5, 9, 10}, i.e., a maximal Paley clique, then the directions determined by A × A arethe quadratic residues and 0 and ∞. This totals 22 directions, matching the lower bound52 − 5 + 2 = 22 given by Theorem 2.1. Interestingly, this is the largest square grid wehave found in which Theorem 2.1 is tight. An infinite class of examples achieving exactlythe lower bound are the long rectangles A = {0, 1}, B = {0, 1, . . . , n − 1}, and p > 2n orA = {0, 1, 2}, B = {0, 1, . . . , n− 1}, n odd, and p > 3n.On the other hand, we expect for large Cartesian products when |A| = |B| the Theo-rem 2.1 bound can be improved. In the case that A = B is an arithmetic progression, weare able to asymptotically determine the precise number of directions. The statement of thenext theorem involves the continuous functionD(λ) =12π2λ2, λ ∈ [0, 1√2],6π2(2 Li2(λ2) + log2(λ2)− 2(1− λ2) log(λ−2 − 1) + 2(1− λ2))− 1, λ ∈ ( 1√2, 1),1, λ ≥ 1,(1.2)whereLi2(x) = −∫ x0log(1− t)tdt (1.3)is the dilogarithm function. Figure 1 shows the graph of D(λ) as a gold, turquoise, and red(solid and dashed) curve, where each color represents a piece of the piecewise defined function.We now state an asymptotic formula for the number of directions determined by [n]2, orequivalently by A2 for any arithmetic progression A of length n in GF (p) (since all such setsare linearly equivalent and thus yield the same set of directions).Theorem 1.3 (Martin, EPW, Yip [46]). The number of directions determined by [n]2 ⊂AG(2, p) isD(n√p)p+O(p3/4(log p)23/2+1),3Figure 1: Comparison of D(λ) (upper curve) and λ2, the bound from [13] (lower curve). Thethree textures of the upper curve indicate the three cases of the definition (1.2) of D(λ).where the function D(λ) is defined in equation (1.2).A key idea in the proof of Theorem 1.3 is the reduction of the problem of counting thenumber of directions to estimating the number of solutions to the Diophantine equationad + bc = p. Let N(p, n) denote the number of solutions (a, b, c, d) ∈ [n]4 to the equationad + bc = p. Since ad + bc ≤ 2n2 when (a, b, c, d) ∈ [n]4, we see that N(p, n) = 0 triviallywhen n <√p2.Theorem 1.4 (Martin, EPW, Yip [46]). Let p be a prime, let 1√2< λ < 1, and set n = λ√p.The number of solutions (a, b, c, d) ∈ [n]4 to the equation ad+ bc = p isN(p, n) =(12π2λ2 −D(λ))p+O(p3/4(log p)23/2+1), (1.4)where the function D(λ) is defined in equation (1.2), and the implied constant in the errorterm is absolute.We will not discuss the proof details of Theorems 1.3 and 1.4 in later chapters, but referthe reader to [46] for full details.41.2 An optimal L2 autoconvolution inequalityLet A,B be subsets of an additive group. Two main objects of study in the field of additivecombinatorics are sum and difference sets:A+B = {a+ b : a ∈ A, b ∈ B},A−B = {a− b : a ∈ A, b ∈ B}.The most important information about sum and difference sets is recorded by the con-volution and correlation of their indicator functions:1A ∗ 1B(x) =∑a+b=x1A(a)1B(b),1A ◦ 1B(x) =∑a−b=x1A(a)1B(b).Many interesting and well-studied questions can be phrased using convolutions and cor-relations. One in particular that has received significant attention in the past two decadesis the following, and was introduced by Schinzel and Schmidt [62]. For A ⊂ [N ], what is thelargest constant C(N) such thatN∥1A ∗ 1A∥∞ ≥ C(N)|A|2.Schinzel and Schmidt also consider the analogous continuous problem, namely to determinethe largest ν∞ ∈ R such that∥f ∗ f∥∞ ≥ ν∞∥f∥21, (1.5)for all nonnegative f : [0, 1] → R. Moreover, they prove that limN→∞C(N) = ν∞. The in-equalities contain in this problem are good examples of convolution inequalities, i.e.,inequalitiesinvolving convolutions. Many authors have improved estimates for α, but the best upperand lower bounds remain far apart: 1.28 ≤ ν∞ ≤ 1.50992. The best lower bound is dueto Cloninger and Steinerberger [11] and the best upper bound is due to Matolcsi and Vin-uesa [47].One application of the above problem is to the estimation of the size of Bh[g]-sets. Forg, h,N positive integers, a subset A ⊂ [N ] = {1, 2, . . . , N} is an Bh[g]-set if for every x ∈ Z,5there are at most g representations of the forma1 + a2 + . . .+ ah = x, ai ∈ A, 1 ≤ i ≤ h,where two representations are considered to be the same if they are permutations of eachother. We remark that B2[1] sets are the well known Sidon sets.A frequently studied problem is to estimate the constantσh(g) = limN→∞Rh[g](N)(gN)1/h.The above limit is known to exist only in the case of the classical Sidon sets, where wehave σ2(1) = 1. The key to improving upper bounds on σ2(g) for large g is to improve theconstant in (1.5). On the other hand, the key to improving upper bounds on σ2(g) for smallg is to improve an analogous inequality for L2 norm. This is the main focus of Chapter 3.Theorem 1.5 (EPW [73]). Defineν2 = inff : [0,1]→R≥0f ̸=0∥f ∗ f∥2∥f∥21.Then0.574636066 ≤ ν22 ≤ 0.574642912.Theorem 1.5 and (1.5) can be classified as autoconvolution inequalities because a functionis convolved with itself. Progress on (1.5) is limited by computation time on a nonconvexprogram introduced by Cloninger & Steinerberger [11]. In contrast, we obtain nearly tightbounds in Theorem 1.5 by transferring the problem to a quadratically constrained convex op-timization. Theorem 1.5 improves estimations of Green [24], and Martin and O’Bryant [45].By reusing methods of Green [24, Theorems 15, 17, 24] we obtain the following corollary.Corollary 1.6 (EPW [73]). The following asymptotic bounds on Bh[g] sets hold.σ2(g) ≤(2− 1/gν22)1/2, σ3(1) ≤(2ν22)1/3, σ4(1) ≤(4ν22)1/4,6where ν22 = 0.574636066 denotes the lower bound on ν22 stated in Theorem 3.1.Corollary 1.6 is an improvement on the previous best upper bounds for σh[g] for h = 2and 2 ≤ g ≤ 4 as well as g = 1 and h = 3, 4.The main strategy we use to prove Theorem 1.5 is to combine Fourier analysis andoptimization techniques. Using similar techniques, we construct a more elaborate programto obtain strong new lower bounds in Erdo˝s’ minimum overlap problem.71.3 Minimum overlapLet n be a positive integer and A∪B = [2n] be an equitable partition. For k ∈ Z, let Mk bethe number of solutions to a− b = k for a ∈ A and b ∈ B. We are interested in estimationsofM(n) = minA∪B=[n]maxkMk,where the minimum is taken over all equitable partitions of [2n]. Since there are n2 pairs(a, b) ∈ A×B and at most 4n− 2 values attainable for a− b, the pigeonhole principle givesus the lower bound M(n) > n/4. On the other hand, the partition with A = [n/2, 3n/2]gives us M(n) ≤ n/2. Erdo˝s posed the determination of M(n) as a problem in 1955, andalso conjecture that M(n) = n/2 is optimal. Shortly afterwards, this was disproven, andmany authors contributed better upper and lower bounds. Their progress is summarized inTable 2.Year Progress Author1955 n/4 < M(n) ≤ n/2 Erdo˝s [15]1955 (1− 2−1/2)n < M(n) Erdo˝s and Scherk [16]1956 M(n) ≤ 2n/5 Motzkin, Ralston, Selfridge [50]1958 (4− 6−1/2)n/5 ≤M(n) Swierczkowski [67]1959 0.356 ≈√4−√15n ≤M(n) Moser [48] (previous best lower bound)1996 M(n) ≤ 0.382n Haugland [32]2016 M(n) ≤ 0.3809n Haugland [33] (best upper bound)Table 2: Progress on the minimum overlap problemHaugland made important progress in 1996 by showing that the limitµ := limn→∞M(n)nexists [32]. We will refer to µ as the minimum overlap constant. A key step in Haug-land’s method is a theorem of Swinnerton-Dyer proving the equivalence between the originaldiscrete problem of Erdo˝s, and a continuous reformulation considered by Moser and Mur-deshwar [49].For all measurable functions f : [−1, 1]→ [0, 1] define the complementary function g : [−1, 1]→8[0, 1] such that f(x) + g(x) = 1 for all x ∈ [−1, 1]. We have thatµ = inffsupx∈[−2,2]Mf (x), where Mf (x) =∫ 1−1f(t)g(x+ t) dt, (1.6)where the infimum is taken over all measurable f : [−1, 1]→ [0, 1] satisfying ∫ 1−1 f(x) dx = 1.The current best upper bound is due to Haugland, and comes from the construction of a51-step function [33]. Part of the difficulty of estimating µ lies in the facts that the formu-lations discussed so far are all non-convex. For example, it is likely that finding the beststep function with 100 pieces would improve the upper bound on µ, but this is currentlycomputationally intractable.In contrast, using Fourier analysis, we derive an infinite one-parameter family of convexconstraints that captures most of the relevant structure of functions of the form Mf as in(1.6). Combining many of these constraints, and using a numerical optimizer, we obtain thefollowing significant improvement of the lower bound.Theorem 1.7 (EPW [72]). The minimum overlap constant is lower bounded by 0.379005.Recall that the best upper bound is 0.3809 and so the upper and lower bounds for µ nowdiffer by only 0.5%. We expect that the Theorem 1.7 bound can be slightly improved withmore computation time. A difficulty in determining µ to higher precision is that qualitativeproperties of the optimal f : [−1, 1]→ [0, 1] as in (1.6) are hard to find. For example, Haug-land has numerically searched for optimal step functions for up to 51-steps, and in all casesexcept for 2-steps, the best functions are even. Our own method to prove Theorem 1.7 alsocreates approximations to optimal functions f , and these also strongly suggests that optimalf will also be even. Despite the evidence, we are unable to prove this.One common technique in proving convolution or correlation inequalities is the use ofrearrangement inequalities. However, we have not found suitable rearrangements of themass of f that decreases the maximum overlap. The structure of optimal f for several ofthe best functions found by Haugland achieve a global maximum at several values of x, andhave multiple local maximums. In Figure 2 we display the best 51-step function found byHaugland, published in [33].9Figure 2: Best 51-step function101.4 Combinatorics of IntervalsMany central problems in extremal geometry can be framed as question of determining themaximum number of subsets of an n point set that are congruent, similar, homothetic, orotherwise related to a prescribed pattern. Perhaps the most important instance of this is theunit-distance problem, i.e., to determine how many pairs of n points in the plane can be atdistance one from each other. For repeated configurations of several points in C, Laczkovichand Ruzsa proved the number of similar copies depends on whether or not every cross ratioof four points is algebraic [55].Incidence estimates are among the most important tools for the extremal problems de-scribed above. A key theorem in the subject essentially resolves the distinct distance problem,where we want to know the fewest number of distances determined between pairs of n pointsin the plane. The cornerstone to resolving the distinct distance problem is a result on thenumber of incidences between points and lines in R3 proved by Guth and Katz [28]. A specialfeature of their theorem is that it also describes the necessary geometric structure possessedby the lines in R3 whenever many incidences occur. The results in Chapter 5 use the knownproperties of lines in R3 with many incidences to understand extremal configurations of linesegments in the plane.We will refer to line segments in the plane as intervals, and make the following formaldefinition. An interval in R2 is denoted by a four-tuple (a, b; c, d) ∈ R4, where (a, b), (c, d) ∈R2 are the coordinates of the endpoints. We require that (a, b) ̸= (c, d), so the interval haspositive length. Our works on intervals are concerned with the following question.If in a set of N intervals in the plane, many pairs of intervals form a particular geometricconfiguration, then what structure must the whole set of intervals possess?Our method is to map intervals of lines in R3 so that a pair of lines intersect if the cor-responding pair of intervals form the desired geometric configuration. The aforementionedtheorem of Guth and Katz shows that if a set of lines in R3 has sufficiently many intersec-tions, then there must be a large subset of lines that are concurrent, coplanar, or lie in acommon regulus. Our main theorems describe the precise structure held by the intervals,obtained by pulling back the known structure on lines to intervals. The primary geometricconfiguration of the first work are trapezoids, while the second is concyclic quadrilaterals.In Chapter 5 we will give a full treatment of the concylic quadrilateral case, but next give a11brief overview of the result for trapezoids.Consider a pair of distinct intervals, (a, b; c, d) and (a′, b′; c′, d′). We say that this pairforms a trapezoid if the convex hull of the two intervals is a trapezoid or a triangle. Thepossible ways this can occur is illustrated in Figure 3.Figure 3: Intervals forming trapezoids: five cases.Throughout this section we use the notation A ≳ B to mean there exists an absoluteconstant C > 0 for which A ≥ CB. The following is our main result for sets of intervalsforming many trapezoids.Theorem 1.8 (Di Benedetto, Solymosi, EPW [14]). Let I be a set of N distinct intervalsin R2. If ≳ N3/2 logN pairs of intervals form trapezoids then at least one of the followingholds.1. There are ≳ N1/2 logN parallel intervals.2. There is a centre S and a ratio λ such that for ≳ N1/2 intervals from I, one endpoint isthe image of the other under a homothety with centre S and ratio λ.3. There are two curves in R2 of degree at most 2 such that ≳ N1/2 intervals from I havean endpoint on each curve.We will not discuss the proof of Theorem 1.8 in depth. The overall strategy is similarto the case for concyclic pairs of intervals. In the remainder of the section we will presentour results for concyclic pairs. A pair of distinct intervals, (a, b; c, d) and (a′, b′; c′, d′) areconcyclic if there is a single circle containing the four endpoints (a, b), (c, d), (a′, b′), (c′, d′).We will not allow the radius of the inscribed circle to be infinite, i.e., for the two intervalsto be on a common line. See Figure 4 for examples of concyclic intervals.12Figure 4: Two pairs of concyclic intervalsBicircular quartic and circular cubic curves play a central role in our characterization ofsets of intervals with many concyclic pairs. A bicircular quartic curve is the zero set of abivariate polynomial curve with leading homogenous term divisible by (x2+ y2)2 and degree3 homogenous term is divisible by x2 + y2. Similarly, a circular cubic is a curve with degree3 homogenous term divisible by x2 + y2.Theorem 1.9 (Solymosi, EPW [65]). Let I be a set of N distinct intervals in R2, with nopair intervals contained in a common line. If more than N3/2 logN pairs of intervals areconcyclic then one of the following holds.1. There is a circle C in R2, such that ≳ N1/2 intervals have both endpoints on C.2. (a) ≳ N1/2 intervals are parallel and are perpendicularly bisected by a common line, or(b) after a translation of I, there exists a constant h ≥ 0 such that ≳ N1/2 intervals(a, b; c, d) satisfy (a2 + b2)(c2 + d2) = h and the lines containing these intervals areall concurrent.3. There are two subsets I1, I2 ⊂ I such that for any I1 ∈ I1 and any I2 ∈ I2, the intervalsI1, I2 are concyclic. In addition, |I1||I2| ≳ N . Moreover, all endpoints of intervals inI1 ∪ I2 lie on a bicircular quartic, circular cubic, or conic.We remark that in both Theorem 1.8 and Theorem 1.9, any single instance of the listedstructures produces only ≳ N pairs of intervals with the special structure. The gap betweenN and N3/2 occurs because it is possible to have many ‘separate’ instances of the specialstructures. For example, there could exist N1/2 circles such that the endpoints of N1/2intervals lie on each circle, thereby producing ≳ N3/2 pairs of concyclic intervals.132 Directions in Finite Geometries2.1 IntroductionLet U be a subset of the Desargusian affine plane AG(2, p), where p is a prime number.A direction is determined by U if two points of U lie on a line in that direction. We cancoordinatize AG(2, p) so that U = {(ai, bi) : 1 ≤ i ≤ |U |}, where ai, bi ∈ GF (p) for all1 ≤ i ≤ |U |, and then the set of directions determined by U is given byD ={bi − bjai − aj : 1 ≤ i < j ≤ n}.Note that D is a subset of GF (p) ∪ {∞}.The possible values of |D| have been studied by various authors. For a survey of resultson this topic see [1] and [69]. A key tool in this area are the properties of lacunary poly-nomials, which are polynomials with several consecutive coefficients equal to zero. Re´dei’smonograph [56], as well as Ball and Blokhuis’s chapter [1] contain many results on lacunarypolynomials and their applications, one of which is a sharp lower bound of (p+ 3)/2 on thesize of D for sets of size exactly p, excepting lines. The size of |D| has also been consideredin the setting AG(2, q), q a prime power, see for example [2].Re´dei’s method was later extended by Szo˝nyi [68] to sets U of size smaller than p. Ourresult uses Szo˝nyi’s extension of Re´dei’s method and relies on the fact that when U isa Cartesian product the relevant polynomials have a very special structure that can beexploited. In Section 2.3 we prove the following theorem, improving Szo˝nyi’s bound by afactor of two (up to lower order terms) for Cartesian product sets.Theorem 2.1. Let A,B ⊂ GF (p) be sets each of size at least two such that |A||B| < p.Then the set of points A × B ⊂ AG(2, p) determines at least |A||B| − min{|A|, |B|} + 2directions.Let d > 1 be a divisor of p − 1 and let Zd be a multiplicative subgroup of size d insideGF (p). As a corollary of Theorem 1, we obtain the following result on inclusions of the formA−A ⊂ Zd ∪ {0}, which was recently proved by Hanson and Petridis [31] using Stepanov’smethod.14Corollary 2.2. Let A ⊂ GF (p) be a set such that A− A ⊂ Zd ∪ {0}. Then|A|(|A| − 1) ≤ d.In particular, if p is congruent to 1 modulo 4 and d = (p−1)/2 this gives an upper boundof (√2p− 1 + 1)/2 on the clique number of the Paley graph Gp. Recall that the vertices ofGp are the elements of GF (p) with an edge between elements whose difference is a square inGF (p).Estimating the size of sets of the form (A − A)/(A − A) played a crucial role in earlysum-product estimates over finite fields, [22, 38], and it is still an important tool in provingsum-product type bounds (see e.g., in [51]). For A ⊂ GF (p) with |A|2 < p, Theorem 2.1gives that#{a− bc− d : (a, b, c, d) ∈ A4, a ̸= b, c ̸= d}≥ |A|2 − |A|.Hence there is a nonzero x ∈ (A − A)/(A − A) such that the number of representationsx = (a − b)/(c − d) with (a, b, c, d) ∈ A4 is at most |A|2 − |A|. Consider the set A − xA ={α−xβ : (α, β) ∈ A2}. The number of representations of a y ∈ α−xβ cannot be too high onaverage, otherwise x would have many representations in (A−A)/(A−A). This idea can bemade rigorous using the Cauchy-Schwarz inequality. The corresponding result is recorded inthe following corollary.Corollary 2.3. Let A be a subset of GF (p) such that |A|2 < p. There exist a, b, c, d ∈ Asuch that |(a− b)A+ (c− d)A| ≥ |A|3/(2|A| − 1).Our arguments for cartesian products can be extended to a set in GF (p) consisting of aunion of two cartesian products. A corollary of this is as follows.Corollary 2.4. Let A,B ⊂ GF (p) be disjoint sets each of size at least two such that eachof the difference sets A−A, A−B, B−B contain either only squares, or only non-squares,in addition to 0. Thenmin{|A|2 − 2|A|, |B|2 − 2|B|}+ |A||B|+ 2 ≤ p+ 32.For a subset A ⊆ GF (p), the directions determined by A × {0, 1} is the set (A − A) ∪{∞}. Hence by Theorem 2.1 we recover an instance of the well known Cauchy-DavenportTheorem [12].15Corollary 2.5. Let A ⊆ GF (p) be nonempty, then |A− A| ≥ min{p, 2|A| − 1}.2.2 Re´dei polynomialsLet U = {(ai, bi) : 1 ≤ i ≤ |U |} be a subset of the affine plane AG(2, p), and D be the setof directions determined by U . Suppose that AG(2, p) is coordinatized so that ∞ ∈ D. Putn = |U |. The Re´dei polynomial of U isH(x, y) =n∏i=1(x+ aiy − bi).Consider Hy(x) = H(x, y) as a polynomial with indeterminate x and coefficients inGF (p)[y]. Define the set Ay = {−aiy+ bi}ni=1. Observe that Hy(x) divides xp−x if and onlyif the elements of Ay are all distinct, and this is equivalent to y ̸∈ D. In the case y ̸∈ D, wesee that (xp − x)/Hy(x) has a root at every element of GF (p) \ Ay, i.e., the coefficients of(xp − x)/Hy(x) are symmetric polynomials of the form σk(GF (p) \ Ay), k = 1, 2, . . . , p− n.We can determine the symmetric polynomials σk(GF (p) \ Ay) in terms of the symmetricpolynomials {σi(Ay)}ki=1 recursively as follows.For 1 ≤ k < p− 1 we have σk(GF (p)) = 0 and sok∑i=0σi(Ay)σk−i(GF (p) \ Ay) = 0.This gives, for exampleσ1(GF (p) \ Ay) = −σ1(Ay), and σ2(GF (p) \ Ay) = σ21(Ay)− σ2(Ay).Continuing recursively we see that σk(GF (p) \Ay) is a polynomial in GF (p)[y] of degree atmost k and can be defined even when the elements of Ay are not all distinct. Put m = p−nand definef(x, y) = xm−σ1(GF (p)\Ay)xm−1+σ2(GF (p)\Ay)xm−2+· · ·+(−1)mσm(GF (p)\Ay). (2.1)Note that f is a degree m polynomial in GF (p)[x, y] and crucially we haveH(x, y)f(x, y) = xp − x16for all y ̸∈ D.For more on the construction and properties of H and f see [68, 69]. LetH(x, y)f(x, y) = xp + h1(y)xp−1 + h2(y)xp−2 + · · ·+ hp(y),and note that deg(hi) ≤ i. Since H(x, y)f(x, y) = xp − x, for every y ̸∈ D we see that ifi ̸= p−1 then hi(y) = 0 for all y ̸∈ D. Recall that there are p+1 directions in AG(2, p). Since∞ ∈ D, there are p+1−|D| directions not in D, and all such directions are in GF (p). Thisimplies that hi ≡ 0 if i < p+1−|D|. Equivalently, if hi ̸≡ 0, then |D| ≥ p+1− i. Thereforeshowing that there is a high degree term in this polynomial with a nonzero coefficient resultsin a lower bound on |D|. This is how we will proceed.2.3 Directions in Cartesian productsLet U be a Cartesian product set in AG(2, p), i.e., there exists a coordinatization such thatU = A × B, where A,B ⊂ GF (p). Assume that the elements of A and B are all distinct,and put |A| = m, |B| = n. Let A = {ai : 1 ≤ i ≤ m} and B = {bj : 1 ≤ j ≤ n}.If m = 1 or n = 1 then U is contained in a line and spans only one direction. Notice alsothat any subset of AG(2, p) with at least p + 1 elements determines all directions. This isbecause there are only p parallel lines in each direction, and so for each direction there mustbe a line in that direction containing at least two points from the set. Consequently, we willassume that m,n ≥ 2 and mn < p. Translating preserves the number of directions, and sowe will assume 0 ∈ B.The Re´dei polynomial of A×B isH(x, y) =∏i,j(x+ aiy − bj).Let Ay = {−aiy + bj : 1 ≤ i ≤ m; 1 ≤ j ≤ n}. Put k = p−mn and definef(x, y) = xk − σ1(GF (p) \ Ay)xk−1 + σ2(GF (p) \ Ay)xk−2 + · · ·+ σk(GF (p) \ Ay).17We will consider the Re´dei polynomial in the horizontal direction, y = 0. LetH(x, 0)f(x, 0) = f(x, 0)∏j(x− bj)m = xp + c1xp−1 + c2xp−2 + · · ·+ cp, (2.2)for some coefficients c1, . . . , cp ∈ GF (p). We will exploit the product structure of the poly-nomial above to obtain our result. We begin with a lemma.Lemma 2.6. Let R, S ∈ GF (p)[x] be polynomials each with constant term equal to 1 anddegR ≥ 1. Suppose that R and R′ are relatively prime and that R does not divide S. Thenxdeg(R)+deg(S)+1 does not divide Rm(x)S(x) − 1 for any positive integer m such that p doesnot divide m.Proof. Suppose for a contradiction that there exist R, S, and m satisfying the conditions ofthe Lemma. Then there exists a polynomial P (x) ∈ GF (p)[x] such thatRm(x)S(x) = 1 + xdeg(R)+deg(S)+1P (x). (2.3)Let k = deg(R) and n = deg(S). By differentiating (2.3) we obtainRm−1(x)(mR′(x)S(x) +R(x)S ′(x)) = xk+n((k + n+ 1)P (x) + xP ′(x)).Since the constant term in Rm−1(x) is 1, we see that xk+n divides mR′(x)g(x) +R(x)S ′(x).But the degree of mR′(x)S(x) + R(x)S ′(x) is at most k + n − 1 and so mR′(x)S(x) +R(x)S ′(x) = 0. Since R and R′ are relatively prime, it must be the case that R divides mS.Since m ̸= 0 in GF (p) we see R divides S, a contradiction.We remark that Lemma 2.6 can be proved with a different argument. Now we proveTheorem 2.1 by analyzing (2.2) and applying this lemma.Proof of Theorem 2.1. Recall that if ci ̸= 0, then there are at least p−i+1 directions in A×B.Suppose for a contradiction that c1 = c2 = . . . = ck+n−1 = 0. Put R(y) =∏nj=1(1− bjy), andS(y) = ykf(y−1, 0). We see that R(y), S(y) ∈ GF (p)[y], deg(R) = n − 1 and deg(S) ≤ k.Substitute x = y−1 in (2.2) and multiply by yp to obtainRm(y)S(y) = 1 + c1y + c2y2 + · · ·+ cpyp = 1 + yk+nQ(y),18for some polynomial Q(y) ∈ GF (p)[y]. Since the elements of B are distinct, all roots of Rhave multiplicity 1, and so R is relatively prime to R′. Let q be the highest power of Rdividing S. From the above we haveRm+q(SRq)= 1 + yk−q(n−1)+n[yq(n−1)Q(y)].We have the following relations on the above variables.mn+ k = p, and k − q(n− 1) ≥ 0.It is easy to obtain the relation m + q ≤ p − m/(n − 1) < p from the above. Thereforeby Lemma 2.6 we conclude that degR = 0, i.e., R(y) = 1. This gives B = {0}, which isa contradiction since we assumed |B| ≥ 2. It follows that at least one of c1, . . . , ck+n−1 isnonzero, and so there are at least p − k − n + 2 = mn − n + 2 directions in A × B. Byrotating the affine plane 90◦ and repeating the argument we obtain the result#{Directions in A×B} ≥ |A||B| −min{|A|, |B|}+ 2.We conclude with a proof of Corollary 2.4.Proof of Corollary 2.4. Let A,B ⊂ GF (p) be as in the statement of the corollary. Let|A| = m, |B| = n, and put A = {ai}mi=1, B = {bj}nj=1, and U = A×A∪B×B. Our strategywill be to bound the number of directions in U . Consequently, we can assume 0 ∈ A bytranslating U . Without loss of generality, we’ll assume m ≥ n. The Re´dei polynomialH(x, y) of U evaluated at y = 0 isH(x, 0) =m∏i=1(x− ai)mn∏j=1(x− bj)n.Let f(x, y) be the polynomial defined in (2.1) corresponding to U . Define k = deg(f) = p−m2−n2. Put H(x, 0)f(x, 0) = xp+G(x) for some G[x] ∈ GF (p)[x]. Define R(y) =∏mi=1(1−aiy)∏nj=1(1 − bjy), and S(y) = ykf(y−1, 0) (∏mi=1(1− aiy))m−n. Note that R(y), S(y) ∈GF (p)[y], deg(R) = m + n − 1, and degS ≤ k + (m − 1)(m − n). We make a similarsubstitution to that in the proof above as follows.19ypH(y−1, 0)f(y−1, 0) = Rn(y)S(y) = 1 + ypG(y−1).Let q be the highest power of R dividing S. The above givesRm+q(SRq)= 1 + ypG(y−1). (2.4)The following relations hold.m2 + n2 + k = p, and k + (m− 1)(m− n)− q(m+ n− 1) ≥ 0.It is easy to check that the above implies m+ q < p. The lowest degree term in ypG(y−1) isp− deg(G). Applying Lemma 2.6 to (2.4) givesp− degG ≤ k + (m− 1)(m− n) +m+ n− 1.Recall that the number of directions in U is at least deg(G) + 1. Therefore U determines atleast n2 +mn− 2n+ 2 directions. Every direction in U is a quotient of two squares, or twonon-squares in GF (p). Hence all directions are squares, or zero, or infinity. This amountsto no more than p+32directions, thereby giving the required result.203 An optimal L2 autoconvolution inequality3.1 IntroductionLet g, h,N be positive integers. A subset A ⊂ [N ] = {1, 2, . . . , N} is an Bh[g]-set if for everyx ∈ Z, there are at most g representations of x as the sum of h elements of A, i.e.,a1 + a2 + . . .+ ah = x, ai ∈ A, 1 ≤ i ≤ h,where two representations are considered to be the same if they are permutations of eachother. As a shorthand, we let Bh = Bh[1]. Note that B2 sets are the very well known Sidonsets. Let Rh[g](N) denote the largest size of subset A ⊂ [N ] such that A is a Bh[g] set.By counting the number of ordered h-tuples of elements of A, we have the simple bound(|A|+h−1h) ≤ hN , which implies Rh[g](N) ≤ (ghh!N)1/h. On the other hand, Bose and Chowlashowed that there exist Bh sets of size N1/h(1 + o(1)), where we use o(1) to denote a termgoing to zero as N → ∞ [5]. This lower bound result has been generalized to more pairs(g, h) by several authors, [6, 9, 41]. Recently the bound Rh[g](N) ≥ (Ng)1/h(1 − o(1)) forall N , g ≥ 1, and h ≥ 2 was obtained in [36]. In general, estimating the constantσh(g) = limN→∞Rh[g](N)(gN)1/h,is an open problem. In fact, the only case for which the above limit is known to exist is inthe case of the classical Sidon sets, where we have σ2(1) = 1. Henceforth we will understandupper and lower bounds on σh(g) to be estimates on the lim sup and lim inf, respectively.Several improved upper bounds for σh(g) have been obtained by various authors, forreferences to many of them, as well as an excellent resource on Bh[g] sets in general, see [52].In this work we will improve the upper bounds on σh(g) for h = 2 and 2 ≤ g ≤ 4, as wellas g = 1 and h = 3, 4. No improvement on σh(g) for g = 1 and h = 3, 4 has been madesince [24] in 2001. The most recent improvements on estimates for σ2(g) which are the bestfor 2 ≤ g ≤ 4 are the following.21σ2(g) ≤√1.75(2− 1/g) Green [24]≤√1.74217(2− 1/g) Yu [76]≤√1.740463(2− 1/g) Habsieger & Plagne [30]On the other hand, for g ≥ 5, the best recent upper bounds are below.σ2(g) ≤√3.4796 Cilleruelo, Ruzsa & Trujillo [10]≤√3.1696 Martin & O’Bryant [44]≤√3.1377 Matolcsi & Vinuesa [47]≤√3.1250 Cloninger & Steinerberger [11]Interestingly, the key to improving upper bounds on σ2(g) is to better estimate the 2-norm of an autoconvolution for small g and the infinity norm of an autoconvolution for largeg. In the case of the infinity norm, the best known results are0.64 ≤ inff : [−1/2,1/2]→R≥0∫f = 1∥f ∗ f∥∞ ≤ 0.75496.The lower bound is due to Cloninger & Steinerberger [11] and the upper bound is due toMatolcsi & Vinuesa [47]. It is believed that the upper bound above is closer to the truth.The method of Cloninger & Steinerberger is computational, and is limited by a nonconvexoptimization program.Throughout we denote by F the family of nonnegative functions f ∈ L1(−1/2, 1/2) suchthat∫f = 1. For 1 ≤ p ≤ ∞ we defineνp = inff∈F∥f ∗ f∥p = inff∈F(∫ 1−1(∫ 1/2−1/2f(t)f(x− t)dt)pdx)1/p,the minimum p-norm of the autoconvolution supported on a unit interval. Determining νpprecisely is an open problem for all values of p, and is the content of Problem 35 in BenGreen’s 100 open problems [25]. Prior to this work, the best known bounds for the p = 222case are0.574575 ≤ ν22 ≤ 0.640733,where the lower bound is due to Martin & O’Bryant [45] and the upper bound is due toGreen [24]. Our main theorem is the following, we improve upper and lower bounds for ν2.Theorem 3.1. The L2 norm of the autoconvolution f ∗ f for f ∈ F can be bounded asfollows.0.574636066 ≤ ν22 ≤ 0.574642912.We are also able to prove that there exists a unique minimizer f ∈ F of the L2 norm ofan autoconvolution. Combining our new bounds on ν22 with methods of Green [24, Theorems15, 17, 24] give the following corollary.Corollary 3.2. The following asymptotic bounds on Bh[g] sets hold.σ2(g) ≤(2− 1/gν22)1/2, σ3(1) ≤(2ν22)1/3, σ4(1) ≤(4ν22)1/4,where ν22 = 0.574636066 denotes the lower bound on ν22 stated in Theorem 3.1.Corollary 3.2 is an improvement on the previous best upper bounds for σh[g] for h = 2and 2 ≤ g ≤ 4 as well as g = 1 and h = 3, 4. One of the main theorems proved by Greenin [24] gives a bound on the additive energy of a discrete function on [N ]. We show thatour bound in the continuous case applies to the discrete one, and so the Theorem 3.1 boundgives another improved estimate.Corollary 3.3. Let H : [N ] → R≥0 be a function with∑Nj=1H(j) = N . Then for allsufficiently large N we have ∑a+b=c+dH(a)H(b)H(c)H(d) ≥ ν22N3.The methods of Habsieger & Plagne and Yu [30, 76], Cloninger & Steinerberger [11], andMartin & O’Bryant are all limited by long computation times. In contrast, the key to ourimprovement is a convex quadratic optimization program whose optimum value is shownto converge to ν22 . The strategy of using Fourier analysis to produce a convex program toobtain bounds on a convolution-type inequality was also employed recently by the authorto improve bounds on Erdo˝s’ minimum overlap problem in [72]. We hope that our methods23may also be useful in obtaining estimates for the infimum of an autoconvolution with respectto other p-norms.3.2 Existence and uniqueness of the optimizerIn this section we prove the existence and uniqueness to the solution of the following opti-mization problem.Infimum:∫ 1−1(f ∗ f)2(x) dx (3.1)Such that: f : [−1/2, 1/2]→ R≥0∫ 1/2−1/2f(x) dx = 1. (3.2)We remark that (3.2) defines the family F seen in the introduction. For all f ∈ L1(R)we define the Fourier transform on R asf˜(y) =∫Re−2πixyf(x) dx.For any f as in (3.2), we note that f˜ ∗ f = f˜ 2 and so by Parseval’s identity∫ 1−1(f ∗ f)2(x) dx =∫R|f˜(y)|4 dy. (3.3)The following proposition proves the existence and uniqueness of an optimizer in F to(3.1) using the ‘direct method in the calculus of variations’. A similar method is used toshow the existence of optimizers to autocorrelation inequalities in [43].Proposition 3.4. There exists a unique extremizing function f ∈ F to the optimizationproblem (3.1).Proof. Let {fn} ⊂ F be a minimizing sequence such that limn→∞ ∥fn ∗ fn∥2 = ν2. Since L1and L∞ are separable we can apply the sequential Banach-Alaoglu Theorem to conclude theexistence of f ∈ L1(−1/2, 1/2) and g ∈ L∞(R) such thatfn∗⇀ f converges weakly in L1(−1/2, 1/2),f˜n∗⇀ g converges weakly in L∞(R),24where possibly we passed to a subsequence of {fn} to make the above hold. For all h ∈ L1(R),by definition of convergence in the weak topology we have⟨g, h⟩ = limn→∞⟨f˜n, h⟩ = limn→∞⟨fn, h˜⟩ = ⟨f, h˜⟩ = ⟨f˜ , h⟩,hence g = f˜ . Note that for all y ∈ R we havef˜n(y) =∫Rfn(x)e−2πixy1(−1/2,1/2)(x) dx,and since e−2πixy1(−1/2,1/2)(x) ∈ L∞(R), by weak convergence we see limn→∞ f˜n(y) = f˜(y).In addition, limn→∞ |f˜n(y)|4 = |f˜(y)|4 and so by Fatou’s lemma:∫R|f˜(y)|4 dy ≤ lim infn→∞∫R|f˜n(y)|4 dy.Finally, we have1 = limn→∞⟨1(−1/2,1/2), fn⟩ = ⟨1(−1/2,1/2), f⟩ =∫ 1/2−1/2f(x) dx.We conclude that f ∈ F is an extremizing function. For uniqueness, suppose that f, g ∈ Fsatisfy ∥f˜∥4 = ∥g˜∥4 = ν1/22 . Then by Minkowski’s inequality,∥∥∥∥∥ f˜ + g˜2∥∥∥∥∥4≤ 12(∥f˜∥4 + ∥g˜∥4)= ν1/22 .Minkowski’s inequality above must be an equality, implying f and g are linearly dependant.Since f, g have the same average value, we conclude that f = g and so the extremizingfunction is unique.Note that the uniqueness of the optimizer implies that it must be even. Throughout wewill denote the unique optimizer by f♢ ∈ F .253.3 Useful identitiesFor ease of notation we will always use lowercase letters f, g to denote functions on [−1/2, 1/2],or period 1 functions. We define the Fourier transform of f : [−1/2, 1/2]→ R for k ∈ Z asfˆ(k) =∫ 1/2−1/2e−2πikxf(x) dx.We will use upper case letters F,G to denote functions on [−1, 1] or period 2 functions.We define the Fourier transform of F : [−1, 1]→ R for k ∈ Z asFˆ (k) =12∫ 1−1e−πikxf(x) dx.This is an abuse of the notation ‘ˆ’, but which of the two above transforms is meant willbe made clear by the letter case of the function notation. Let f ∈ F and define F (x) be theextension of f(x) to a function on [−1, 1] defined by setting F (x) = 0 outside of [−1/2, 1/2].Since supp(F ) ⊂ [−1/2, 1/2], the support of F ∗ F is contained in [−1, 1], henceF̂ ∗ F (k) = 12∫ 1−1e−πikxF ∗ F (x) dx = 12∫ 1−1e−πikx∫ 1/2−1/2f(t)f(x− t) dt dx=12∫ 1/2−1/2e−πiktF (t)∫ 1−1e−πik(x−t)F (x− t) dx dt = 2Fˆ (k)2.We calculate the relationship between Fˆ and fˆ below.Fˆ (m) =12∑kfˆ(k)∫ 1/2−1/2eπix(2k−m) dx =12 fˆ(m/2) if m is even(−1)(m+1)/2∑k∈Z fˆ(k)(−1)kπ(2k−m) if m is odd. (3.4)From Parseval’s theorem and the above we obtain∥F ∗ F∥22 = 2∑k∈Z|F̂ ∗ F (k)|2 = 8∑k∈Z|Fˆ (k)|4.=12∑m∈Z|fˆ(m)|4 + 8π4∑m∈Zm odd∣∣∣∣∣∑k∈Zfˆ(k)(−1)k2k −m∣∣∣∣∣4. (3.5)Since f(x) is real and even, we know that fˆ(k) = fˆ(−k) ∈ R for all k ∈ Z.26Lemma 3.5. For all f ∈ F we have the identity∥f ∗ f∥22 =12+∞∑m=1fˆ(m)4 +16π4∑m≥1m odd(1m+ 2∞∑k=1mfˆ(k)(−1)km2 − 4k2)4.Proof. Since fˆ(0) = 1, we have for all odd m ∈ Z∑k∈Zfˆ(k)(−1)km− 2k =1m+ 2∞∑k=1mfˆ(k)(−1)km2 − 4k2 .Substituting the above into (3.5) gives the result.We are unable to analytically determine the fˆ(k) such that ∥f ∗ f∥2 is minimized. In thefollowing section we will use Lemma 3.5 together with a convex program to provide upperbounds on ν2 as well as an assignment of fˆ(k) that is very close to optimal. The followinglemma suggests a method of obtaining strong lower bounds from good f ∈ F with small∥f ∗ f∥2, i.e., good lower bounds can be found from good upper bound constructions.Lemma 3.6. Let f, g be periodic real functions with period 1, such that∫ 1/2−1/2 f = 1 and∫ 1/2−1/2 g = 2. Define F,G : [−1, 1]→ R byF (x) =f(x) for x ∈ [−1/2, 1/2]0 otherwise , G(x) =1 for x ∈ [−1/2, 1/2]1− g(x) otherwise.Then1/2 =∑k ̸=0Fˆ (k)Gˆ(k) ≤(∑k ̸=0|Fˆ (k)|4)1/4(∑k ̸=0|Gˆ(k)|4/3)3/4. (3.6)Proof. By Plancherel’s theorem we have1 =∫ 1−1F (x)G(x) dx = ⟨F,G⟩ = 2⟨Fˆ , Gˆ⟩ = 2∑k∈ZFˆ (k)Gˆ(k).Since Gˆ(0) = 0, by applying Ho¨lder’s inequality we conclude (3.6).27Inequality (3.6) is tight only when |Fˆ (k)|3 = |Gˆ(k)| for k ̸= 0. Suppose that f(x) leads toan F (x) that is close to optimal for (3.6). We hypothesize that for some C ∈ R, the functiondefined by gˆ(k) = Cfˆ(k)3 for k ̸= 0 and gˆ(0) = 2 will create a G(x) that is also close tooptimal for (3.6). We use this idea to produce good lower bounds for ν2 in the followingsection.3.4 Quantitative resultsIn this section we describe a convex program used to approximate the optimal solution of(3.1) with finitely many variables. Our primal program is the following.Input: R, T ∈ NVariables: {fk, wk, xk}Tk=1, {ym, zm}Rm=1Minimize:12+T∑m=1xk +16π4R∑m=1zmSubject to: wk ≥ f 2k , xk ≥ w2k; 1 ≤ k ≤ T,ym ≥(12m− 1 + 2T∑k=1(2m− 1)fk(−1)k(2m− 1)2 − 4k2)2; 1 ≤ m ≤ R,zm ≥ y2m; 1 ≤ m ≤ R.(3.7)For any R, T ∈ N, let O(R, T ) be the optimum of the above program. We remark thatthe reason for the ‘redundant’ variables {wk, xk}Tk=1 and {ym, zm}Rm=1 is to demonstrate thatthe program is easily implemented as a quadratically constrained linear program. For anyT ∈ N, let FT ⊂ F be the subset of functions that are degree at most T in their Fourierseries expansion, i.e., f ∈ FT implies fˆ(k) = 0 for |k| > T .Proposition 3.7. Let R, T ∈ N, thenO(R, T ) ≤ minf∈FT∥f ∗ f∥22 ≤ ν22 + 3T−1 log T. (3.8)Moreover, if T ≥ 20 and 9R3 ≥ T 4/ log T , then |O(R, T )− ν22 | < 3T−1 log T.Proof. Fix arbitrary R, T ∈ N. The left inequality of (3.8) follows immediately from28Lemma 3.5. Fix a b ∈ N, and let f♢ ∈ F be the extremizer, define for all 0 < ϵ < 1/4a smoothed version of it:fϵ(x) = (1 + bϵ)f♢ ∗ h∗bϵ ((1 + bϵ)x),wherehϵ(x) =1/ϵ if − ϵ2 < x < ϵ20 otherwise, and h∗bϵ =b︷ ︸︸ ︷hϵ ∗ · · · ∗ hϵ .Note that since ϵ < 1/4 we can consider hϵ as a function on (−1/2, 1/2) with mass 1.Furthermore, f♢∗h∗bϵ is supported on [−(1+bϵ)/2, (1+bϵ)/2] and so fϵ ∈ F . Since ∥h˜ϵ∥∞ ≤ 1we have∫|f˜ϵ(y)|4 dy ≤∫ ∣∣∣∣f˜♢( y1 + bϵ)∣∣∣∣4 dy = (1 + bϵ)∫ |f˜♢(y)|4 dy ≤ (1 + bϵ)ν22 . (3.9)Let fϵ,T ∈ FT be the degree T Fourier approximation of fϵ, i.e.,fϵ,T (x) =∑|k|≤Tfˆϵ(k)e2πikx.Note that ∥fˆ♢∥∞ ≤ ∥f∥1 = 1, and so ∥fˆϵ,T∥∞ ≤ ∥fˆϵ∥∞ ≤ 1 as well. Consequently, wehave the estimate:∥fˆϵ,T − fˆϵ∥44 ≤ ∥fˆϵ,T − fˆϵ∥22 =∑|k|>T|fˆϵ(k)|2 =∑|k|>T|f˜ϵ(k)|2=∑|k|>T|f˜♢(k/(1 + bϵ))h˜bϵ(k/(1 + bϵ))|2≤ ∥f˜♢∥2∞∑|k|>T(1 + bϵπϵk)2b≤ 2(2b− 1)T 2b−1(1 + bϵπϵ)2b. (3.10)If 1 + bϵ ≤ π then from (3.9), (3.10) we have∥fˆϵ,T∥44 ≤ ∥fˆϵ∥44 + ∥fˆϵ,T − fˆϵ∥44 ≤ (1 + bϵ)ν22 +2(2b− 1)T 2b−1ϵ2b .29By choosing ϵ = T−2b−12b+1 and b = ⌈log T ⌉ we obtain∥f˜ϵ,T∥44 ≤ ν22 + T−2b−12b+1(ν22b+22b− 1)≤ ν22 + 3T−1 log T.This proves the right inequality of (3.8) since minf∈FT ∥f ∗ f∥22 ≤ ∥f˜ϵ,T∥44.Now add the hypotheses that R ≥ 2T ≥ 40. Let {fk}Tk=1 be the solution to the programwith inputs R, T . Define fP (x) =∑|k|≤T e2πikxf|k|. We haveminf∈FT∥f ∗ f∥22 ≤ ∥fP ∗ fP∥22 ≤ O(R, T ) +16π4∞∑m=R+1(12m− 1 + 2T∑k=1(2m− 1)fk(−1)k(2m− 1)2 − 4k2)4.(3.11)For all m ≥ R+1 and 1 ≤ k ≤ T we have (2m− 1)2− 4k2 ≥ 2m2. We can bound the insidesum above by Ho¨lder’s inequality.∣∣∣∣∣T∑k=1(2m− 1)fk(−1)k(2m− 1)2 − 4k2∣∣∣∣∣ ≤ (2m− 1)(T∑k=1f 4k)1/4( T∑k=1(2m2)−4/3)3/4≤ 2T3/43m.Substituting this estimate into (3.11) we obtainminf∈FT∥f ∗ f∥22 ≤ O(R, T ) +16π4∞∑m=R+1(3T 3/4/2m)4 ≤ O(R, T ) + 13(T/R)3.Since O(R, T ) ≤ minf∈FT ∥f ∗ f∥22, if 9R3 ≥ T 4/ log T we have 13(T/R)3 ≤ 3T−1 log T and soO(R, T )− 3T−1 log T ≤ ν22 ≤ O(R, T ) + 3T−1 log T.As a consequence of Proposition 3.7 we see that the optimum of our program will convergeto ν22 for the right choice of input, thereby giving good upper and lower bounds for ν22 .3.4.1 Computational resultsProposition 3.7 suggests that R/T should be large to produce the best estimates of ν22 byO(R, T ). In contrast, we found the best performance of the convex program when T/R islarge. Our best data comes from using our convex program with R = 5000 and T = 40000.30We used IBM’s CPLEX software on a personal computer to determine the optimal solution,and the full assignment of {fk}40000k=1 is available upon request. The first 20 values of fk aredisplayed below.fk : 1 ≤ k ≤ 10 fk : 11 ≤ k ≤ 20-0.297645963 -0.0942198820.216255517 0.090244578-0.178147938 -0.0867335710.154958273 0.083602996-0.138960878 -0.080788780.127073164 0.078241005-0.117792216 -0.0759201270.110286604 0.073794356-0.10405425 -0.071837810.098771678 0.07002916Table 3: First values of {fk} for almost optimal f(x).Here we have O(5000, 40000) = 0.574643014. By Proposition 3.7 we obtain the estimates0.573848267 ≤ ν22 ≤ 0.575437762. Using more careful calculation, and Lemma 3.6, belowwe produce substantially better estimates with the same data. In Figure 5 we display thedegree 20 trigonometric polynomial described in Table 3. We remark that the optimalfunctions created by the convex program appear to converge to a function with asymptotesat x = ±1/2 on the order of 1/√x. It is precisely this strength of singularity that createsan autoconvolution that neither vanishes nor ‘blows up’ at the boundary. Similar functionswere studied by Barnard in Steinerberger on their work on convolution inequalities [3].31Figure 5: Degree 20 trigonometric polynomial shown in blue and its autoconvolution shownin orangeFor the remainder of this section, let T = 40000, R = 5000. With fk the solutionpartially stated above, put fP (x) = 1 +∑0 ̸=|k|≤T f|k|e2πikx. Also let FP be the extensionof fP to [−1, 1], defined to be zero outside of [−1/2, 1/2]. In the following two subsectionswe calculate upper and lower bounds for ν22 thereby proving Theorem 3.1. We export ourcomputed solution {fk}40000k=1 to Matlab and used ‘Variable-Precision Arithmetic’ operationsto avoid floating-point rounding errors on the order of precision stated in our theorem, weused the default of 32 significant digits. In the calculation of our upper and lower bounds,we will use the following quantities related to {fk}40000k=1 .T∑k=1|fk| ≈ 138.986734521,T∑k=1|fk|3 ≈ 0.0748989557,T∑k=1k2|fk|3 < 257609. (3.12)3.4.2 Computing an upper boundWe want to estimate ∥fP ∗ fP∥22 from above. We will take advantage of the fact that theFourier coefficients FˆP (k) decay quickly. From (3.4) we see that FˆP (2m) = 0 for all |m| ≥32T + 1. Also, for odd |m| ≥ 4T we have|FˆP (m)| =∣∣∣∣∑k∈ZfˆP (k)(−1)kπ(2k −m)∣∣∣∣ ≤ 2mπ ∑|k|≤T |fˆP (k)|. (3.13)From (3.12) we obtain the estimate |FˆP (m)| < 178/m. This gives the bound on the tail sumfor all N ∈ N:∑m>N|Fˆ (2m− 1)|4 < 1784∫ ∞N(2x− 1)−4 dx = 1784(2N − 1)−3/6.From (3.5) we have for all N ≥ 2T :∥fP ∗ fP∥22 = 8∑m∈Z|FˆP (m)|4 ≤ 12+T∑m=1fˆP (m)4+16π4N∑m=1(12m− 1 + 2(2m− 1)T∑k=1fˆP (k)(−1)k(2m− 1)2 − 4k2)4+ 1784(2N − 1)−3/3.The choice of N = 107 gives the estimate ∥fP ∗ fP∥22 ≤ 0.574642912.3.4.3 Computing a lower boundWe use Lemma 3.6 to compute a good lower bound. To do this, we need to find a goodchoice of g(x) on [−1/2, 1/2]. As per the discussion following Lemma 3.6, a good choice gPmay have the Fourier coefficients gˆP (0) = 2 andgˆP (m) = αfˆP (m)3, m ∈ Z \ {0}.Below we optimize α to suit our particular fP , this ends up giving α = −13.342. Let GP beas in the statement for Lemma 3.6, i.e.,GP (x) =1 for x ∈ [−1/2, 1/2]1− gP (x) otherwise.We need to accurately bound∑m ̸=0 |GˆP (m)|4/3 from above. We can proceed similar to ourrecent upper bound calculation, using the decay of the Fourier coefficients. For m ̸= 0 we33haveGˆP (m) = −12(−1)m∫ 1/2−1/2gP (x)e−πimx dx. (3.14)The dependance of GˆP on gˆP was essentially calculated in (3.4), we restate it below.GˆP (m) =−12 gˆP (m/2) if m is even(−1)(m+1)/2∑k∈Z gˆP (k)(−1)kπ(2k−m) if m is odd.We see GˆP (2m) = 0 for all |m| ≥ T + 1. Fix an odd m ∈ Z, similar to (3.13) we have|GˆP (m)| =∣∣∣∣∑k∈ZgˆP (k)(−1)kπ(2k −m)∣∣∣∣ = 2πm∣∣∣∣1 + T∑k=1gˆP (k)(−1)k1− 4k2/m2∣∣∣∣=2πm∣∣∣∣1 + α T∑k=1|fk|31− 4k2/m2∣∣∣∣. (3.15)Using (3.15), we compute that the below sum is minimized for the choice α = −13.432.∑0̸=|m|≤2·107|GˆP (m)|4/3 = 1.885125792 . . . (3.16)It remains to bound the tail sum for the above. Define 1 + θk = 1/(1 − 4k2/m2). Then if|m| > 2 · 107 and |k| ≤ T we have 0 < θk ≤ 5k2/m2. Now using (3.12) we have∣∣∣∣1 + α T∑k=1|fk|31− 4k2/m2∣∣∣∣ ≤ ∣∣∣∣1 + α T∑k=1|fk|3∣∣∣∣+ |α| T∑k=1θk|fk|3= |1 + α(0.07487 . . .)|+ 5|α|m2· 257609 ≤ 6.982 · 10−4,for all |m| > 2 · 107. Hence via (3.15) we have |GˆP (m)| ≤ 4.45 · 10−4/m. This gives thebound on the tail sum:∑|m|>107|Gˆ(2m− 1)|4/3 < 2(4.45 · 10−4)4/3∫ ∞107(2x− 1)−4/3 dx < 3.76 · 10−7.Combining the above with (3.16) gives∑|m|̸=0 |GˆP (m)|4/3 < 1.885126168. By Lemma 3.634we haveν22 ≥12+12 · (1.885126168)3 > 0.574636066.This concludes the proof of Theorem 3.1.3.5 Number theoretic corollariesIn this section we briefly discuss how results on Bh[g] sets can be obtained from our estimatesof ν2. We rely heavily on the method of Green [24]. The cornerstone of several of the numbertheoretic results proved by Green is the following.Theorem 3.8 (Green [24], Theorem 6.). Let H : {1, . . . , N} → R be a function such that∑nj=1H(j) = N , and v,X be positive integers. For each r ∈ Z2N+v putHˆ(r) =∑x∈Z2N+ve2πirx/(2N+v)H(x),the discrete Fourier transform. Let g ∈ C1[−1/2, 1/2] be such that ∫ 1/2−1/2 g(x) dx = 2. Thenthere is a constant C, depending only on g such that∑0<|r|≤X|Hˆ(r)|4 ≥ γ(g)N4(1− C(vN+N2v2X+X2N)),whereγ(g) = 2(∑r≥1|g˜(r/2)|4/3|)−3.Green finds a function g ∈ C1[−1/2, 1/2] such that γ(g) > 1/7. Let gP ∈ C1[−1/2, 1/2]be as in Section 3.4.3. By equation 3.14 we haveγ(gP ) = 2(∑r≥1|2GˆP (r)|4/3|)−3> 1.885126168−3 = 2ν22 − 1,where ν22 = 0.574636066 denotes the lower bound on ν22 obtained in Section 3.4.3. Weconclude that Theorem 3.8 can be stated by replacing γ(g) with 2ν22 − 1.Proof of Corollary 3.2. To obtain the claimed bounds on σh[g] we simply reuse the method ofGreen, replacing the 1/7 bound with 2ν22 −1. The bound for σ4(1) is found on [24, Equation3530] and stated in [24, Theorem 15]. The bound for σ3(1) is obtained through [24, Lemma16] and stated in [24, Theorem 17]. Finally, the bound for σ2(g) is obtained by replacing 8/7with 2ν22 in [24, Equation 37], thereby giving an improved version of [24, Theorem 24].Lastly, in our proof of Corollary 3.3 we scale a function on [N ] to a simple function on[0, 1], and check that the inequalities work in our favour.Proof of Corollary 3.3. Let H : [N ] → R≥0 be a function with∑Nj=1H(j) = N . Recall thedefinition of discrete convolutionH ∗H(x) =N∑j=1H(j)H(x− j),and so the additive energy of H is given by∑Nj=1H ∗ H(x)2. Define the simple functionf : [0, 1)→ R byf(x) =N∑j=1H(j)1((j−1)/N,j/N ](x).Clearly f(x−1/2) ∈ F , and so ∥f ∗f∥22 ≥ ν22 . The function f ∗f consists of 2N line segmentswith domain ((j − 1)/N, j/N ] for j ∈ [2N ]. Moreover, for all j ∈ [2N ] we haveNf ∗ f((j − 1)/N) = H ∗H(j). (3.17)For any line segment ℓ : [a, b]→ R we have the following estimate by convexity.∫ baℓ(x)2 dx ≤ ℓ(a)2 + ℓ(b)22(b− a). (3.18)By (3.18) we have∫ 20f ∗ f(x)2 dx =2N∑j=1∫ j/N(j−1)/Nf ∗ f(x)2 dx ≤ N22N∑j=1(f ∗ f(j/N)2 + f ∗ f((j − 1)/N)2).And by (3.17) the above becomesN322N∑j=1(H ∗H(j)2 +H ∗H(j − 1)2) = N3 2N∑j=1H ∗H(j)2.This proves the additive energy bound.364 Minimum Overlap4.1 IntroductionIn 1955 Erdo˝s posed the following problem [15]. Let n be a positive integer and A,B ⊂ [2n] bea partition of [2n] such that |A| = |B| = n. For any such partition and integer −2n < k < 2n,define Mk =Mk(A,B) to be the number of solutions (a, b) ∈ A× B to a− b = k. Estimatethe size of the functionM(n) = minA∪B=[2n]max−2n<k<2nMk,where the minimum is taken over all partitions of [2n] into equal-sized sets. Erdo˝s provedthat M(n) > n/4, a result that can be obtained by the following averaging argument. Thesum over all −2n < k < 2n of |Mk| is exactly |A × B| = n2, and so the average value of|Mk| exceeds n/4. On the other hand, we can take A to be [n/2, 3n/2) giving the upperbound M(n) ≤ n/2. The minimum overlap problem appears in Richard Guy’s renownedbook, Unsolved Problems in Number Theory. See his book for a brief survey of the progressmade by many authors on improved estimates of M(n) [29, §C17].Haugland proved that the limitµ := limn→∞M(n)n,exists [32]. We will refer to µ as the minimum overlap constant. Prior to this work, the bestestimates of µ were0.356 ≈√4−√15 ≤ µ ≤ 0.380927.The lower bound above is due to Moser [48], and the upper bound is due to Haugland [33].Moser and Murdeshwar were the first to study the following function analogue of Erdo˝s’original problem. For all measurable functions f : [−1, 1]→ [0, 1] define the complementaryfunction g : [−1, 1]→ [0, 1] such that f(x) + g(x) = 1 for all x ∈ [−1, 1]. Estimate the valueofinffsupx∈[−2,2]∫ 1−1f(t)g(x+ t) dt, (4.1)where the minimum is taken over all measurable f : [−1, 1]→ [0, 1] satisfying ∫ 1−1 f(x) dx = 1.A key step in Haugland’s method is a theorem of Swinnerton-Dyer proving that (4.1) is infact also µ, see [32] for the proof. It will be easiest for us to work with (4.1) as our definition37of µ. In this work we obtain a significant improvement on the lower bound of µ, usingelementary Fourier analysis combined with convex programming.Theorem 4.1. The minimum overlap constant µ is lower bounded by 0.379005.4.2 Outline of the proof of Theorem 4.1Throughout this work, f(x), g(x),M(x) will always denote measurable functions satisfyingthe relationshipsf : [−1, 1]→ [0, 1] such that∫ 1−1f(x) dx = 1;g : [−1, 1]→ [0, 1] such that f(x) + g(x) = 1 for all x ∈ [−1, 1];M : [−2, 2]→ [0, 1] such that M(x) =∫ 1−1f(t)g(x+ t) dt. (4.2)The minimum overlap problem is to determine the largest µ such that ∥M∥∞ ≥ µ for allfunctions M satisfying (4.2). Lower bounds on µ can be obtained by observing propertiesheld by M(x). For example, a first simple property held by M(x) is∫ 2−2M(x) dx =∫ 2−2∫ 1−1f(t)g(x+ t) dtdx =∫ 1−1f(t)∫ 2−2g(x+ t) dxdt = 1. (4.3)Therefore the average value of M(x) is at least 0.25 and so µ ≥ 0.25. The discrete version ofthis argument was already mentioned in the introduction. A second property held by M(x),and the key insight in Moser and Murdeshwar’s method [48], [49] is that∫ 2−2(x− E(M))2M(x) dx ≤ 23, where E(M) =∫ 2−2xM(x) dx, (4.4)is the expected value of M(x). In other words, the variance of M(x) is upper bounded by2/3. The variance of a function is minimized when as much mass as possible is centred atits mean. Therefore the variance of M(x) is at least the variance ofM˜(x) =µ if − 12µ ≤ x ≤ 12µ0 otherwise.The variance of M˜ is 1/(12µ2). Since 1/(12µ2) ≤ 2/3 we have µ ≥ 1/√8 ≥ 0.353.38The key idea behind our improvement is that Fourier analysis can be used to constructan infinite family of new properties satisfied by M(x). The most important new propertywe find and use is that all even cosine Fourier coefficients of M(x) are nonpositive, i.e.,∫ 2−2cos(πkx)M(x) dx ≤ 0, for all k ≥ 1. (4.5)The way we take advantage of these new properties is by constructing a linear programwhere the variables represent the average value of M(x) over small intervals. With thisprogramming technique we can transfer (4.3), (4.4), and (4.5) into constraints of a linearprogram. This short program is the subject of Section 4.4. Under the assumption that anoptimal f(x) is even, the output of this program proves µ ≥ 0.375.In order to prove our larger lower bound in Theorem 4.1 and remove the assumption thatan optimal f(x) is even, we use a more complicated convex program. This is the subjectof Section 4.5. The new properties of f(x),M(x) pairs we find are derived in Section 4.3.These new properties become the constraints used in the linear program of Section 4.4 andthe convex program of Section 4.5. In Section 4.5 we discuss the data collected from theconvex program and prove Theorem 4.1.4.3 Properties of f, g,MIn this section we derive properties about f, g,M that will form key constraints in theprograms used in later sections.4.3.1 Properties from Fourier analysisThe properties derived in this subsection relate to the Fourier coefficients of f, g,M . We firstconsider f, g,M as functions on [−2, 2]. In the case of f and g we define f(x) = g(x) = 0for x ̸∈ [−1, 1]. We will understand f, g,M as 4-periodic functions on R when needed. TheirFourier transforms are defined for all k ∈ Z and given byfˆ(k) =14∫ 2−2e−πi2kxf(x) dx, gˆ(k) =14∫ 2−2e−πi2kxg(x) dx, Mˆ(k) =14∫ 2−2e−πi2kxM(x) dx.39Lemma 4.2. For all f,M satisfying (4.2) and k ∈ Z \ {0} we haveMˆ(k) =4kπsin (kπ/2) fˆ(k)− 4|fˆ(k)|2,where fˆ , Mˆ denote the Fourier transforms of f,M on [−2, 2].Proof. Denote the indicator function of [−1, 1] by 1[−1,1]. We haveMˆ(k) =14∫ 2−2e−πi2kxM(x) dx =14∫ 2−2e−πi2kx∫ 1−1f(t)g(x+ t) dt dx=14∫ 1−1eπi2ktf(t)∫ 2−2e−πi2k(x+t)g(x+ t) dx dt = 4fˆ(k)gˆ(k)= 4fˆ(k)(1ˆ[−1,1](k)− fˆ(k)).Combining the above with1ˆ[−1,1](k) =14∫ 1−1e−πi2kx =1kπsin (kπ/2) ,gives the claimed identity.It will be advantageous to work with real Fourier coefficients in our programs of the latersections. We will derive identities relating the coefficients of the sine-cosine Fourier series off(x) as a function on [−1, 1] with the sine-cosine Fourier series of f(x) andM(x) as functionson [−2, 2]. Letf(x) =12+∞∑k=1ck cos(kπx) +∞∑k=1dk sin(kπx), (4.6)be the sine-cosine Fourier series of f(x) on [−1, 1]. It will be notationally helpful to putc0 = 1/2. Also letf(x) =14+∞∑k=1ak cos(kπx/2) +∞∑k=1bk sin(kπx/2),M(x) =14+∞∑k=1Ak cos(kπx/2) +∞∑k=1Bk sin(kπx/2) (4.7)be the sine-cosine Fourier series of f and M on [−2, 2].40Lemma 4.3. Let f,M be as in (4.2) and their sine-cosine Fourier series be as in (4.6) and(4.7). Then for all m ≥ 1:am =12cm/2 if m is even2m sin(πm/2)π∑∞k=0(−1)km2−4k2 ck if m is odd;(4.8)bm =12dm/2 if m is even4 sin(πm/2)π∑∞k=1k(−1)km2−4k2dk if m is odd;(4.9)Am =4 sin (mπ/2)mπam − 2(a2m + b2m), and in particular A2m ≤ 0; (4.10)Bm = − 4mπsin (mπ/2) bm, and in particular B2m = 0. (4.11)Proof. Note that the denominators in equations (4.8) and (4.9) are never zero since m is anodd integer while 4k2 is even. The convergence of the two infinite sums in (4.8) and (4.9) isimplied by Lemma 4.4 below. To derive (4.8) we use the following integral identities, validfor all m ≥ 1.∫ 1−1cos(πmx/2) cos(πkx) dx =1 if m is even and k = m/20 if m is even and k ̸= m/24m(−1)k sin(πm/2)πm2−4πk2 if m is odd.We also have the identity∫ 1−1 cos(πmx/2) sin(πkx) dx = 0 for all k,m ∈ Z. Combining theseidentities witham =12∫ 1−1cos(πmx/2)f(x) dxgives (4.8). Similarly, we have for all m ≥ 1 the integral identity∫ 1−1sin(πmx/2) sin(πkx) dx =1 if m is even and k = m/20 if m is even and k ̸= m/28k(−1)k sin(πm/2)πm2−4πk2 if m is odd.For all k,m ∈ Z we have ∫ 1−1 sin(πmx/2) cos(πkx) dx = 0. Combining this and the abovewithbm =12∫ 1−1sin(πmx/2)f(x) dx41gives (4.9). To derive (4.10) and (4.11) we need relations between the exponential Fouriercoefficients and the sine-cosine Fourier coefficients. These are2fˆ(m) = am − ibm, 2fˆ(−m) = am + ibm,Am = Mˆ(m) + Mˆ(−m), Bm = i(Mˆ(m)− Mˆ(−m)).By Lemma 4.2 and the above identities we haveAm = Mˆ(m) + Mˆ(−m)=4mπsin(kπ/2)(fˆ(m) + fˆ(−m))− 4(|fˆ(m)|2 + |fˆ(−m)|2)=4 sin (mπ/2)mπam − 2(a2m + b2m).Equation (4.11) is derived similarly.The identities in Lemma 4.3 will be used to construct constraints in our later programs.In order to work with the infinite sums of (4.8) and (4.9) we will bound the tails of the seriesusing Parseval’s identity and the Cauchy-Schwarz inequality.Lemma 4.4. Let T be a positive integer, and f(x) be as in (4.2) with sine-cosine Fourierseries (4.6). Then for all integers 1 ≤ m < 2T we have∣∣∣∣∣2mπ∞∑k=T+1(−1)k sin(πm/2)m2 − 4k2 ck∣∣∣∣∣ ≤ 14−m2/T 2 · 2mπ√6T 3 ,and ∣∣∣∣∣ 4π∞∑k=T+1k(−1)k sin(πm/2)m2 − 4k2 dk∣∣∣∣∣ ≤ 14−m2/T 2 · 4π√2T .Proof. Let f˜ denote the Fourier transform of f(x) on [−1, 1] defined for k ∈ Z byf˜(k) =12∫ 1−1e−iπkxf(x) dx.For k ≥ 1 we have f˜(k) = (ck − idk)/2, and f˜(−k) = (ck + idk)/2. By Parseval’s identityand the fact f˜(0) = 1/2 we obtain1 ≥∫ 1−1f 2(x) dx = 2∑k∈Z|f˜(k)|2 = 12+∞∑k=1(c2k + d2k). (4.12)42Fix an integer 1 ≤ m < 2T . By the triangle inequality∣∣∣∣∣∞∑k=T+1(−1)k sin(πm/2)m2 − 4k2 ck∣∣∣∣∣ ≤∞∑k=T+1|ck|4k2 −m2 ≤14−m2/T 2∞∑k=T+1|ck|k2.By the Cauchy-Schwarz inequality and (4.12)( ∞∑k=T+1|ck|k2)2≤( ∞∑k=T+1c2k)( ∞∑k=T+11k4)≤ 12∫ ∞T1x4dx =16T 3.Combining the two last above lines gives the first tail estimate. We proceed similarly forthe second. By the triangle inequality∣∣∣∣∣∞∑k=T+1k(−1)k sin(πm/2)m2 − 4k2 dk∣∣∣∣∣ ≤∞∑k=T+1k|dk|4k2 −m2 ≤14−m2/T 2∞∑k=T+1|dk|k.By the Cauchy-Schwarz inequality and (4.12)( ∞∑k=T+1|dk|k)2≤( ∞∑k=T+1d2k)( ∞∑k=T+11k2)≤ 12∫ ∞T1x2dx =12T.Combining the two last above lines gives the second tail estimate.4.3.2 Properties using average values of M(x) on small intervalsIn our convex program, the Fourier coefficients ck, dk described above will be variables.The other main type of variable will represent average values of M(x) on small intervals.Throughout the remainder of this work N will denote a large positive integer and we’ll alsodefine L = 2/N . For each 1 ≤ j ≤ N definewj =1L∫ jL(j−1)LM(x) dx and vj =1L∫ −(j−1)L−jLM(x) dx.Note that1 =∫ 2−2M(x) dx =N∑j=1∫ jL(j−1)L(M(x) +M(−x)) dx = LN∑j=1(wj + vj). (4.13)43In this subsection we will estimate the Fourier coefficients, the second moment, and themean of M(x) using the average values {wj, vj}Nj=1. Let R be a positive integer. For all1 ≤ j ≤ N and 1 ≤ m ≤ R, let α+j,m and α−j,m be upper and lower bounds of cos(πmx/2) onthe interval [(j − 1)L, jL], i.e.,α+j,m ≥ max(j−1)L≤x≤jLcos(πmx/2) and α−j,m ≤ min(j−1)L≤x≤jLcos(πmx/2). (4.14)Similarly, define β+j,m and β−j,m to be upper and lower bounds of sin(πmx/2) on the sameintervals:β+j,m ≥ max(j−1)L≤x≤jLsin(πmx/2) and β−j,m ≤ min(j−1)L≤x≤jLsin(πmx/2). (4.15)Next, we use the arrays {α+j,m, α−j,m} and {β+j,m, β−j,m} to give estimates on the Fouriercoefficients of M(x).Lemma 4.5. For all 1 ≤ m ≤ RL2N∑j=1α−j,m(wj + vj) ≤ Am ≤L2N∑j=1α+j,m(wj + vj).L2N∑j=1(β−j,mwj − β+j,mvj) ≤ Bm ≤L2N∑j=1(β+j,mwj − β−j,mvj).Proof. Let m ≥ 1. We can break the integrals defining Ar into a sum of integrals on thesmall intervals:Am =12∫ 2−2cos(πmx/2)M(x) dx=12∫ 2−2cos(πmx/2)(M(x) +M(−x)) dx=12N∑j=1∫ jL(j−1)Lcos(πmx/2)(M(x) +M(−x)) dx. (4.16)By definition of α+j,m, for all 1 ≤ j ≤ N we have∫ jL(j−1)Lcos(πmx/2)(M(x)+M(−x)) dx ≤ α+j,m∫ jL(j−1)L(M(x)+M(−x)) dx = Lα+j,m(wj+vj).44Substituting the above back into (4.16) gives the stated upper bound on Am. The lowerbound is similar. We can also break Bm into the following sum of integrals.Bm =12N∑j=1∫ jL(j−1)Lsin(πmx/2)(M(x)−M(−x)) dx.For all 1 ≤ j ≤ N and (j − 1)L ≤ x ≤ jL we haveβ−j,mM(x)− β+j,mM(−x) ≤ sin(πmx/2)(M(x)−M(−x)) ≤ β+j,mM(x)− β−j,mM(−x).Substituting these estimates into the above expression for Bm gives the stated upper andlower bounds on Bm.Define the mean of f, g,M as follows.E(f) =∫ 1−1xf(x) dx, E(g) =∫ 1−1xg(x) dx, E(M) =∫ 2−2xM(x) dx.We will use a bound on the second moment of M(x). A similar bound is used in thework of Moser and Murdeshwar [49].Lemma 4.6. For all M as in (4.2) we have∫ 2−2x2M(x) dx =23+12E(M)2.Proof. By changing the order of integration, we obtainE(M) =∫ 1−1f(t)∫ 2−2(x+ t)g(x+ t) dxdt−∫ 1−1tf(t)∫ 2−2g(x+ t) dxdt = E(g)− E(f).45A similar change of order gives∫ 2−2x2M(x) dx =∫ 1−1f(t)∫ 2−2x2g(x+ t) dxdt=∫ 1−1f(t)∫ 2−2((x+ t)2 − 2t(x+ t) + t2)g(x+ t) dxdt=∫ 1−1x2g(x) dx− 2E(f)E(g) +∫ 1−1t2f(t) dt=∫ 1−1x2(g(x) + f(x)) dx− 2E(f)E(g) = 23− 2E(f)E(g).A simple calculation shows that E(f) = −E(g) and so E(f) = −E(M)/2. Substitutingthese identities into the above gives the claimed result.Now we give an estimation of the mean and second moment of M(x) using {wj, vj}Nj=1.Lemma 4.7. Let h1 ≤ h2 be real numbers such that h1 ≤ E(M) ≤ h2. Thenh1 ≤ L2N∑j=1(jwj − (j − 1)vj) and L2N∑j=1((j − 1)wj − jvj) ≤ h2,and23+h212≤ L3N∑j=1j2(wj + vj) and L3N∑j=1(j − 1)2(wj + vj) ≤ 23+h222.Proof. Once again we break down the appropriate integral into a sum of integrals.E(M) =∫ 2−2xM(x) dx =N∑j=1∫ jL(j−1)Lx(M(x)−M(−x)) dx.For all 1 ≤ j ≤ N we can upper and lower bound the summand above.(j − 1)L2wj − jL2vj ≤∫ jL(j−1)Lx(M(x)−M(−x)) dx ≤ jL2wj − (j − 1)L2vj.Substituting this back into the above expression for E(M) and then applying h1 ≤ E(M) ≤46h2 gives the upper and lower bounds stated. Secondly for the second moment:∫ 2−2x2M(x) dx =N∑j=1∫ jL(j−1)Lx2(M(x) +M(−x)) dx.For all 1 ≤ j ≤ N we can again upper and lower bound the summand above.(j − 1)2L3(wj + vj) ≤∫ jL(j−1)Lx2(M(x)−M(−x)) dx ≤ j2L3(wj + vj).Substituting this estimate into the above expression for the second moment givesL3N∑j=1j2(wj + vj) ≤∫ 2−2x2M(x) dx ≤ L3N∑j=1(j − 1)2(wj + vj).Applying Lemma 4.6 gives the two required inequalities.4.4 Simplified linear programIn this section we describe a simplified linear program version of our technique that is meantto convey the main idea of the more complex convex program in the following section. Inthis section we will derive a lower bound on ∥M∥∞ under the additional assumption thatM is even, i.e., M(x) = M(−x). The input of the linear program will be positive integersN,R. Throughout the remainder of the work, we will use the notation L = 2/N . We willalso explicitly choose values for the array {α−j,m} defined in (4.14). Setα−j,m = cos(πmL(j − 1/2)/2)− πmL/4, 1 ≤ j ≤ N, 1 ≤ m ≤ 2R.Note that the above choice satisfies the definition (4.14) since the derivative of cos(πmx/2)is bounded in absolute value by πm/2. Our linear program is the following.47Input: N,RVariables: Ω, w1, . . . , wNMinimize: ΩSubject to: 0 ≤ wj ≤ Ω; 1 ≤ j ≤ N, (4.17)N∑j=1wj =N4, (4.18)N∑j=1α−j,2mwj ≤ 0; 1 ≤ m ≤ R, (4.19)L3N∑j=1(j − 1)2wj ≤ 13. (4.20)Proposition 4.8. Let N,R be arbitrary positive integers, and M(x) be as in (4.2) with theadditional property that M(x) is even. If Ω∗ is the optimum of the above program, then∥M∥∞ ≥ Ω∗.Proof. Our strategy is to show that any even M(x) gives a feasible assignment of variablessuch that Ω ≤ ∥M∥∞. Let M(x) be even, fix positive integers N,R. Put Ω = ∥M∥∞ andwj =1L∫ jL(j−1)LM(x) dx. Clearly this assignment of variables satisfies the constraints in(4.17). Since M(x) is even, we have12=∫ 20M(x) dx =N∑j=1∫ jL(j−1)LM(x) dx = LN∑j=1wj,satisfying constraint (4.18). By Lemma 4.5 and (4.10) of Lemma 4.3, for all 1 ≤ m ≤ R wehaveL2N∑j=1α−j,2mwj ≤ A2m ≤ 0,satisfying constraint (4.19). Lastly, from Lemma 4.6 we haveL3N∑j=1(j − 1)2wj ≤∫ 20x2M(x) dx =13,satisfying constraint (4.20).48The optimum of this linear program increases with N and R. A linear program withhundreds of constraints and variables can be solved exactly. For our linear program, itis best to choose N ≥ 2000. At this scale of variables and constraints, exact-solvers arecomputationally slow, but numerical solvers are still very fast. The disadvantage of numericalsolvers is that additional post-processing steps must be taken to ensure the reported resultsare correct. Our strategy will be to find a feasible point in the dual program, which willgive a lower bound on the minimum to the primal problem. To guarantee our dual solutionis truly feasible, we will check that all inequalities that define the dual space are strictlysatisfied by a margin that exceeds the worst-case scenario for floating-point rounding errors.We implemented the linear program and its dual program in IBM’s CPLEX optimiza-tion software. Choosing N = 80000 and R = 20 and running the dual program returns afeasible point in the dual space with objective 0.375169005340707. We have verified that allconstraints are satisfied by a margin exceeding the worst-case floating point error accumu-lation. Therefore ∥M∥∞ ≥ 0.375 for all even M . By increasing N and R this bound can beimproved a little, but it seems that the limit of this approach is less than 0.3755. In the nextsection we will introduce nonlinear constraints that will give a substantial improvement.494.5 Full convex programIn this section we give and discuss our main program that will be used to prove Theorem ??.The convex program we will use includes the ideas of the previous linear program, but willalso add constraints coming from (4.11), which will be important since we no longer assumeM(x) is even. We will also add quadratic constraints coming from (4.10). There will beseveral inputs to our convex program. Let N,R denote positive integers, their role will beroughly the same as in the simplified linear program. A positive integer T ≥ R will also bean input, its role is as in Lemma 4.4 and determines when we truncate certain infinite sums.Finally our last inputs will be real numbers h1 < h2, p1 < p2, q1 < q2. These inputs will actas bounds on the mean of M(x), first cosine, and first sine Fourier coefficient of f(x). Wewill also explicitly choose values for the arrays {α−j,m, α+j,m} and {β−j,m, β+j,m} defined in (4.14)and (4.15). Setα−j,m = cos(πmL(j − 1/2)/2)− πmL/4, α+j,m = cos(πmL(j − 1/2)/2) + πmL/4,β−j,m = sin(πmL(j − 1/2)/2)− πmL/4, β+j,m = sin(πmL(j − 1/2)/2) + πmL/4,for all 1 ≤ j ≤ N and 1 ≤ m ≤ 2R. As above, these choices satisfy the definitions of (4.14)and (4.15) since the derivatives of cos(πmx/2) and sin(πmx/2) are bounded by πm/2. Ourfull convex program is the following.50Input: N, T,R, h1, h2, p1, p2, q1, q2Variables: Ω, {wj, vj}Nj=1, {ck, dk}Tk=1, {ϵ2m−1, δ2m−1}Rm=1,Variable expressions: For 1 ≤ m ≤ 2R :am =12cm/2 if m is evenϵm +2m sin(πm/2)π(12m2+∑Tk=1(−1)km2−4k2 ck)if m is oddbm =12dm/2 if m is evenδm + 4π∑Tk=1 k(−1)k sin(πm/2)m2−4k2 dk if m is oddMinimize: ΩSubject to: 0 ≤ wj, vj ≤ Ω ≤ 1; 1 ≤ j ≤ N, (4.21)LN∑j=1(wj + vj) = 1, (4.22)L2N∑j=1(jwj − (j − 1)vj) ≥ h1 (4.23)L3N∑j=1(j − 1)2(wj + vj) ≤ 23+h222, (4.24)L2N∑j=1α−j,m(wj + vj) ≤4 sin (mπ/2)mπam − 2(a2m + b2m); 1 ≤ m ≤ 2R, (4.25)L2N∑j=1(β−j,mwj − β+j,mvj) ≤ −8mπsin (mπ/2) bm; 1 ≤ m ≤ 2R, (4.26)L2N∑j=1(β+j,mwj − β−j,mvj) ≥ −8mπsin (mπ/2) bm; 1 ≤ m ≤ 2R, (4.27)|ϵ2m−1| ≤ 14−m2/T 2 ·2mπ√6T 31 ≤ m ≤ R, (4.28)|δ2m−1| ≤ 14−m2/T 2 ·4π√2T1 ≤ m ≤ R, (4.29)|ck|, |dk| ≤ 2π1 ≤ k ≤ T, (4.30)T∑k=1(c2k + d2k) ≤12, (4.31)p1 ≤ c1 ≤ p2, q1 ≤ d1 ≤ q2, (4.32)L2N∑j=1α+j,2(wj + vj) ≥ −12(p22 +max{q21, q22}). (4.33)51Our next proposition shows how the input and output of the convex program relate toan f(x),M(x) pair of functions.Proposition 4.9. Let N, T,R be arbitrary positive integers, and h1, h2, p1, p2, q1, q2 be realnumbers. Let Ω∗ be the optimum of the above program with this choice of input. Supposethat f(x),M(x) is as in (4.2) and satisfies(i) 0 ≤ h1 ≤ E(M) ≤ h2,(ii) 0 ≤ p1 ≤∫ 1−1 cos(πx)f(x) dx ≤ p2,(iii) q1 ≤∫ 1−1 sin(πx)f(x) dx ≤ q2.Then ∥M∥∞ ≥ Ω∗.Proof. Our strategy is to show that any f(x),M(x) satisfying the above hypotheses gives afeasible assignment of variables such that Ω ≤ ∥M∥∞. Let f(x),M(x) be as in (4.2) suchthat (i),(ii),(iii) above are also satisfied. We will show that the following choice of variablesis feasible. Set the variable Ω = ∥M∥∞. For each 1 ≤ j ≤ N setwj =1L∫ jL(j−1)LM(x) dx and vj =1L∫ −(j−1)L−jLM(x) dx.For all k ≥ 1 setck =∫ 1−1cos(πkx)f(x) dx and dk =∫ 1−1sin(πkx)f(x) dx. (4.34)The variables of the program ck, dk only run from the indices 1 ≤ k ≤ T , but we define ck, dkfor k ≥ T + 1 to aid in our definition of the last two types of variable. For each 1 ≤ m ≤ Rsetϵ2m−1 =2m(−1)m+1π∞∑k=T+1(−1)k(2m− 1)2 − 4k2 ck, andδ2m−1 =4(−1)m+1π∞∑k=T+1k(−1)k(2m− 1)2 − 4k2dk.We’ll now show that this assignment of variables is feasible. Constraint (4.21) followsimmediately from the definitions; the average ofM(x) on an interval cannot exceed the max-imum. The other constraints are satisfied for reasons contained in the lemmas of Section 4.3,52or hypotheses (i),(ii),(iii). The dependency of constraints on corresponding lemma(s) is out-lined in Table 4.• Constraint (4.22) follows from (4.13), i.e., because∫ 1−1M(x) dx = 1.• Constraints (4.23) and (4.24) follow from Lemma 4.7 and hypothesis (i). The con-straints represent bounds on the mean and second moment of M(x), respectively.• By Lemma 4.3, the righthand side of constraint (4.25) is the mth cosine Fourier coef-ficient of M(x). By Lemma 4.5, the lefthand side of (4.25) is a lower bound on thisFourier coefficient.• By Lemma 4.3, the righthand side of constraints (4.26) and (4.27) are the mth sineFourier coefficient of M(x). By Lemma 4.5, the righthand sides of (4.26) and (4.27)are lower and upper bounds, respectively, on this Fourier coefficient.• Constraints (4.28) and (4.29) follow from Lemma 4.4.• Constraint (4.30) follows from (4.34) since f(x) ∈ [0, 1] and ∥f∥1 = 1.• Constraint (4.31) follows from Parseval’s identity, in particular equation (4.12).• The left constraint of (4.32) follows from hypothesis (ii), since the integer in (ii) isprecisely c1. Similarly, the right constraint of (4.32) follows from hypothesis (iii).• By Lemma 4.3, in particular (4.8) and (4.10), the second cosine Fourier coefficient ofM(x) isA2 =12∫ 2−2cos(πx) dx = −12(c21 + d21).From constraint (4.32) we see that −12(p22 + max{q21, q22}) is a lower bound on therighthand side above. Also, from Lemma 4.5 we see that the lefthand side of constraint(4.33) is an upper bound on the lefthand side above.For the remainder of this paper, let f ∗,M∗ be an optimal pair in the sense that ∥M∗∥∞ = µ.Also denote the first sine and cosine Fourier coefficients of f ∗ by c∗1 and d∗1, i.e.,c∗1 =∫ 1−1cos(πx)f ∗(x) dx, d∗1 =∫ 1−1sin(πx)f ∗(x) dx.53Constraint Follows from(4.22) (4.13)(4.23), (4.24) Lemma 4.7 and (i)(4.25) Lemma 4.3: (4.10) and Lemma 4.5(4.26), (4.27) Lemma 4.3: (4.11) and Lemma 4.5(4.28), (4.29) Lemma 4.4(4.30) (4.34)(4.31) (4.12)(4.32) (ii) and (iii)(4.33) Lemma 4.3: (4.10), Lemma 4.5, (ii) and (iii)Table 4: Constraint feasibilityNote that f ∗(x), f ∗(−x), and 1−f ∗(x) are all also optimal. This means that without loss ofgenerality, we can assume that E(M∗) ≥ 0 and c∗1 ≥ 0. It’s also easy to see that E(M∗) ≤ 2and |c∗1|, |d∗1| ≤ 1. If we choose the inputs(h1, h2) = (0, 2), (p1, p2) = (0, 1), (q1, q2) = (−1, 1), (4.35)then the optimum of our convex program with this input gives a lower bound on µ. Howeverwith this input, the optimum ends up close to 0.25 for any choice of N, T,R. In order to useour program to give a good bound on µ, we use a ‘divide and conquer’ strategy of breakingup the valid ranges of parameters shown in (4.35) into small chunks. The minimum of allthe optimums over these smaller intervals will be our lower bound on µ.4.5.1 Program outputAs was the case with our simpler linear program in Section 4.4, it is best to choose theparameter N to be fairly large, i.e., at least 2000. This rules out the use of exact solveralgorithms, but numerical solvers are still fast enough for this purpose. To guarantee thecorrectness of our output, we find feasible points in the interior of the dual program space,sufficiently far from the boundary to compensate for any floating-point arithmetic errors.Floating-point arithmetic errors can be easily estimated, see [34]. The dual of a convexquadratically constrained problem is easiest to calculate by first reformulating the primalprogram as a second order cone program (SOCP). For more on SOCP and formulating the54dual, see [42]. The full details of calculating the dual and estimating floating-point errors areroutine, but lengthy. As a result we have placed the full details of these steps for interestedreaders in Appendix 1 6.4. In Table 5 we display the value of the objective function of thedual program for a verified feasible point in the dual space for several choices of input. Notethat we have used the ‘divide and conquer’ strategy mentioned above to narrow down thevalue of E(M∗), c∗1 and d∗1.Parameter assignmentN,T,R = 10000, 4000, 10Optimum lower bound(h1, h2), (p1, p2), (q1, q2) = (0.75, 2), (0, 1), (−1, 1) 0.38(h1, h2), (p1, p2), (q1, q2) = (0.4, 0.75), (0, 1), (−1, 1) 0.38(h1, h2), (p1, p2), (q1, q2) = (0.2, 0.4), (0, 1), (−1, 1) 0.38(h1, h2), (p1, p2), (q1, q2) = (0.1, 0.2), (0, 1), (−1, 1) 0.38(h1, h2), (p1, p2), (q1, q2) = (0.08, 0.1), (0, 1), (−1, 1) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0, 1), (−1,−0.05) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0, 1), (−0.05,−0.025) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0, 1), (0.05, 1) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0, 1), (0.025, 0.05) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0, 0.25), (−0.025, 0.025) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0.25, 0.3), (−0.025, 0.025) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0.3, 0.33), (−0.025, 0.025) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0.5, 1), (−0.025, 0.025) 0.38(h1, h2), (p1, p2), (q1, q2) = (0, 0.08), (0.45, 0.5), (−0.025, 0.025) 0.38(h1, h2), (p1, p2), (q1, q2) = (0.06, 0.08), (0.33, 0.45), (−0.025, 0.025) 0.38N,T,R = 20000, 5000, 10(h1, h2), (p1, p2), (q1, q2) = (0.0, 0.06), (0.33, 0.45), (−0.025,−0.02) 0.38(h1, h2), (p1, p2), (q1, q2) = (0.0, 0.06), (0.33, 0.45), (0.02, 0.025) 0.38(h1, h2), (p1, p2), (q1, q2) = (0.0, 0.06), (0.33, 0.35), (−0.02, 0.02) 0.37925Table 5: Dual program output IThe data of the first line of Table 5 shows that either µ ≥ 0.38 or E(M∗) ≤ 0.75.Combining all data from Table 5 shows that either µ ≥ 0.37925 or0 ≤ E(M∗) ≤ 0.06, 0.35 ≤ c∗1 ≤ 0.45, and − 0.02 ≤ d∗1 ≤ 0.02. (4.36)We can proceed in the same way by dividing the above intervals into small pieces andfinding feasible points for each of the corresponding inputs. The drawback to this approachis that in order to achieve a lower bound close to 0.379, many hundreds of feasible pointsneed to be computed and verified. Instead, we can use the observation that the parametersh1, h2, p1, p2 are not a part of the constraints in the dual program, i.e., they only affect the55objective function. As a result, for any choice of input N, T,R, h1, h2, p1, p2, q1, q2 and a feasi-ble assignment of dual variables, we have a lower bound on the optimum of the dual programfor any choice of h1, h2, p1, p2 by reusing the variable assignment, and simply re-computingthe objective function with the changed values of h1, h2, p1, p2. A precise statement, proof,and example of this idea is given in Appendix 6.4, specifically Lemma 6.6. We apply thistechnique by first calculating a feasible point in the dual with input such that h = h1 = h2and p = p1 = p2. Next we determine by how much can (h, p) change while keeping the restof the feasible point data fixed so that the objective function is always at least 0.379005.Since the dependence of the objective function on h and p is quadratic, the region for whichthe objective is at least 0.379005 will be an ellipse on (h, p)-axes. We compute seven fea-sible points such that the union of the ellipses described above covers the remaining regiondescribed in (4.36). The input of these feasible points is described in Table 6. The coveringellipses are shown in Figure 6.Label : Colour : Hatch in Figure 6 Initial parameter assignment Initial objective value1 : Green : None h = 0.015, p = 0.381 0.379052 : Blue : ⋆ h = 0.015, p = 0.385 0.379053 : Red : / h = 0.02, p = 0.375 0.379054 : Purple : + h = 0.004, p = 0.3875 0.379055 : Light green : × h = 0, p = 0.4 0.37916 : Orange : ◦ h = 0, p = 0.381 0.37917 : Light blue : ⃝ h = 0.03, p = 0.375 0.3794Table 6: Dual program output IIN, T,R = 25000, 7000, 10, and (q1, q2) = (−0.02, 0.02)The full variable assignments of all feasible solutions used in this section, as well asa CPLEX implementation of both the primal and dual programs are available [74]. Weconclude that the Theorem 4.1 bound µ ≥ 0.379005 is now verified.4.6 Concluding remarksThe data in the previous section suggests the following estimates:0 ≤ E(M∗) ≤ 0.01, 0.381 ≤ c∗1 ≤ 0.382, and − 0.02 ≤ d∗1 ≤ 0.02. (4.37)56Figure 6: Lower bound of 0.379005We ran our primal program with input corresponding to (4.37):h1 = 0, h2 = 0.01, p1 = 0.381, p2 = 0.382, q1 = −0.02, q2 = 0.02,and N = 25000, T = 7000, R = 10. The optimal value was 0.3797. We conjecture that thetrue value of µ is likely very close to 0.38. The main limiting factor in our method is per-haps the over-cautious error control on the floating-point arithmetic. With exact arithmeticcalculations, it seems possible that our lower bound method and Haugland’s upper boundmethod will converge to approximately the same value.The solution to our convex program with input (4.37) includes an assignment of thevariables {ck, dk}Tk=1, thereby giving us an idea of what the optimal f ∗ looks like. Thecurrent upper bound on µ comes from a construction of a 51-step simple function found byHaugland [33]. We can compare our best ‘lower bound f ’ to the best ‘upper bound f ’ foundby Haugland’s method. In Table 7 we display the first Fourier cosine coefficients of our lowerbound method, as well as the Fourier cosine coefficients of Haugland’s 51-piece step function.The sine Fourier coefficients of Haugland’s upper bound function are all 0 since the func-571 2 3 4 5Cosine coefficients lower bound 0.38100 -0.04832 0.10758 -0.05663 0.02849Cosine coefficients upper bound 0.38156 -0.05194 0.12607 -0.03716 0.01542Table 7: First Fourier cosine coefficients for lower and upper bound f(x).tion is even. The sine Fourier coefficients of the lower bound are all at most 0.00006. Weconjecture that the optimal f ∗ is even. This comparison seems to suggest that our lowerbound method produces functions that converge to the functions produced by Haugland’supper bound method, at least at the lower frequencies. We were unable to use our methodto produce a function that beats the current upper bound, but wonder if this can be done.In Figure 7 we have drawn the two f(x),M(x) pairs coming from Table 7.Figure 7: Degree 5 Fourier approximations of f(x),M(x) pairs.585 Combinatorics of Intervals5.1 IntroductionIntervals, or line segments in the plane have been studied in a wide variety of contexts.Specific topics include algorithms for computing intersections, binary space partitions, andvertical visibility. We refer to [8], [54], [70], [75] for examples of these topics, and alsoto [53] for a larger overview of related areas in geometry. In [13] the authors analyzedinterval configurations where many pairs formed a trapezoid. The methods applied there -in particular using line incidences in 3-space - are similar to the techniques used in this paper.We make the following formal definition for intervals. An interval in R2 is a line segment.We will denote an interval by a four-tuple (a, b; c, d) ∈ R4, where (a, b), (c, d) ∈ R2 denotesthe coordinates of the endpoints. We require that (a, b) ̸= (c, d), so the interval has positivelength. Consider a pair of distinct intervals, (a, b; c, d) and (a′, b′; c′, d′). We say that this pairis concyclic if there is a single circle containing the four endpoints (a, b), (c, d), (a′, b′), (c′, d′).We will not allow the radius of the inscribed circle to have infinite radius, i.e., for the twointervals to be on a common line. See Figure 8 for examples of concyclic intervals.Figure 8: Two pairs of concyclic intervalsThe main question we answer in this work is the following. Given a set of intervals forwhich many pairs are concyclic, what structure must the intervals possess? Our character-ization of such interval sets will enable us to create interesting sets of intervals with manyconcyclic pairs. Bicircular quartics play a central role in our characterization. A polyno-mial F (x, y) ∈ R[x, y] is a bicircular quartic if the leading homogenous term is divisible by(x2 + y2)2 and the degree 3 homogenous term is divisible by x2 + y2. Bicircular quarticsare important objects in classical analytic geometry. They appeared in Salmon’s Treatiseon Conic Sections [59] and its sequel, Higher Plane Curves [60]. These curves were analyzedand classified by Casey in 1871 (on more than 100 pages) in [7]. Bicircular quartics were verypopular subjects of research in the late 19th century, but they also appear in modern works,59like in [18]. More importantly to us, these curves play central role in recent works in discretegeometry [40, 64]. As a Green-Tao type [26] structural result for concyclic four-tuples Lin,Makhul, Mojarrad, Schicho, Swanepoel, and de Zeeuw proved the following theoremTheorem 5.1. [40] If n is sufficiently large depending on K, and P is a set of n pointsspanning at most Kn2 ordinary circles1, then all but O(K) points of P lie on a bicircularquartic.When the number of ordinary circles is very small then out of the N =(n2)intervals(point-pairs) at least cN3/2 pairs are concyclic, and then most of the points are on a bicircularquartic. Our main result can be seen as a density version of Theorem 5.1.5.2 The main resultThroughout the paper we use the notation A ≳ B to mean there exists a universal constantC > 0 for which A ≥ CB. A circular cubic is a curve with degree 3 homogenous termdivisible by (x2+y2). Circular cubics are also part of our characterization of sets of intervalswith many concyclic pairs. The main theorem we will prove is the following.Theorem 5.2. Let I be a set of N distinct intervals in R2, with no pair intervals containedin a common line. If more than N3/2 logN pairs of intervals are concyclic then one of thefollowing holds.1. There is a circle C in R2, such that ≳ N1/2 intervals have both endpoints on C.2. (a) ≳ N1/2 intervals are parallel and are perpendicularly bisected by a common line, or(b) after a translation of I, there exists a constant h ≥ 0 such that ≳ N1/2 intervals(a, b; c, d) satisfy (a2 + b2)(c2 + d2) = h and the lines containing these intervals areall concurrent.3. There are two subsets I1, I2 ⊂ I such that for any I1 ∈ I1 and any I2 ∈ I2, the intervalsI1, I2 are concyclic. In addition, |I1||I2| ≳ N . Moreover, all endpoints of intervals inI1 ∪ I2 lie on a bicircular quartic, circular cubic, or conic.Note that if a single instance of one of the above structures occur in a set of intervals,then only ≳ N pairs of intervals will be concyclic. The reason the gap between N and N3/2occurs is because it is possible to have many ‘separate’ instances of the above structures in a1a circle is ordinary if it contains exactly three points of P60set of intervals. For example, there could exist N1/2 circles such that the endpoints of N1/2intervals lie on each circle, thereby producing ≳ N3/2 pairs of concyclic intervals.The layout of our paper will be as follows. In Section 5.3 we will derive a correspondencebetween intervals in R2 and lines in R3 such that pairs of concyclic intervals correspond topairs of intersecting lines. A theorem of Guth and Katz characterizes the structure of a setof lines in R3 with many intersections. In Section 5.4 we determine the consequences of thestructure of lines in R3 on the intervals in R2 thereby proving Theorem 5.2. In Section 5.5we explicitly construct sets of intervals with many concyclic pairs by using our Section 5.3interval–line correspondence and a set of lines in R3 with many intersections, and providefurther discussion of the geometric properties of interval sets with many concyclic pairs. Forexamples of the structure described in Theorem 5.2, see Figure 9 and Figure 10.Figure 9: An arrangement of intervals with the structure described in Theorem 5.2 Case 2b.Figure 10: An arrangement of intervals with endpoints contained on a bicircular quar-tic. Every red-blue pair of intervals is concyclic. The bicircular quartic has the equation(x2 + y2)2 − 2 (4x+ y) (x2 + y2) + 8xy − 24y2 + 25 = 0.615.3 Set up: mapping intervals to linesIn this section we describe a map from intervals in R2 to lines in R3 such that concyclicpairs of intervals correspond to intersecting pairs of lines. For any interval I = (a, b; c, d),we define the circular pencil of I as the set of circles containing both endpoints (a, b) and(c, d). Two intervals are concyclic precisely when the intersection of their circular pencils isnonempty.Figure 11: Circular pencil of an interval.Given an interval I = (a, b; c, d) the centre of all circles in the circular pencil of I lie onthe line a+c2b+d2+d− ba− c t, t ∈ R.A circle in the circular pencil of I with centre (p, q) has square radius r2 = (p−a)2+(q−b)2.Therefore p2 + q2 − r2 = 2ap+ 2bq − a2 − b2, i.e., the quantity p2 + q2 − r2 depends linearlyon p and q. We’ll use this fact to parameterize the circular pencil of I linearly in t. Let(p, q) = (12(a + c), 12(b + d)) + (d − b, a − c)t be the centre of a circle in the circular pencil.Then pqp2 + q2 − r2 =a+c2b+d2ac+ bd+d− ba− c2(ad− bc) t. (5.1)The righthand side of (5.1) can be interpreted as a point in R3, and so we have establisheda map between circles in the circular pencil of an interval and points in R3. Furthermore, as62we range over all centres (p, q), the resulting set of points in R3 form a line. The expressionin (5.1) also gives the correspondence between circles in R2 and the set S = {(x, y, z) ∈R3 : x2 + y2 ≥ z}:{(x, y) ∈ R2 : (x− x0)2 + (y − y0)2 = x20 + y20 − z0} ←→ (x0, y0, z0) ∈ S. (5.2)Lemma 5.3. There is a map L from intervals in R2 to lines in R3 such that a pair ofintervals is concyclic if and only if their images under L intersect.Proof. To every interval (a, b; c, d) we associate the unique lineL(a, b; c, d) =a+c2b+d2ac+ bd+d− ba− c2(ad− bc) t : t ∈ R ⊂ R3. (5.3)Let (a, b; c, d) and (a′, b′; c′, d′) be an arbitrary pair of intervals. From (5.2) we know thatpoints in L(a, b; c, d) and L(a′, b′; c′, d′) correspond to circles belonging to the circular pencilsof (a, b; c, d) and (a′, b′; c′, d′), respectively. Therefore L(a, b; c, d) and L(a′, b′; c′, d′) intersectif and only if the circular pencils of (a, b; c, d) and (a′, b′; c′, d′) intersect, i.e., when (a, b; c, d)and (a′, b′; c′, d′) are concyclic.We remark that a pair of intervals I1, I2 are contained in a common line if and onlyif L(I1),L(I2) are parallel. We will work with sets of intervals for which this never occurs.Representing intervals by lines in space gives us a powerful tool analyzing concyclic intervals.As an illustration let’s see the following simple claimClaim 5.4. For any set of n intervals in the plane, the number of circles containing theendpoints of at least three intervals that are not all parallel or concurrent is O(n3/2).If a circle contains the endpoints of at least three intervals, then the corresponding linesin 3-space form a joint. Three lines form a joint if they are concurrent, but not coplanar.Answering a question of Bourgain, Guth and Katz proved that n lines can form O(n3/2)joints [27] (see also in [37]). Claim 5.4 follows directly from this result of Guth and Katz,and we don’t see a different simple proof using plane geometry.The main tool that we use to prove our sets of intervals have a particular structure isa theorem of Guth and Katz on incidences of lines in R3. The following is a corollary of63Theorem 1.2 in [28]. The proof of Theorem 5.5 uses a standard dyadic summation and canbe found in [13].Theorem 5.5 (Guth and Katz [28]). Let L be a set of N lines in R3. If the number of pairsof intersecting lines in L is ≳ N3/2 logN , then at least one of the following holds.1. There are N1/2 concurrent lines in L.2. There exists a plane containing ≳ N1/2 lines of L.3. There exists a regulus containing a subset of lines LR ⊂ L such that the number of pairsof intersecting lines in LR is ≳ N .Each of the three cases in Theorem 5.2 corresponds with the same numbered case inTheorem 5.5. In the following section we will use the R3 structure given by Theorem 5.5, toprove Theorem 5.2.5.4 Proof of Theorem 5.2Before beginning our proof of Theorem 5.2, we informally discuss what geometry mightbe ‘expected’ in a set of intervals with many concyclic pairs. Let I be a set of intervalscontaining many concyclic pairs. Suppose that many of the endpoints of intervals in I lieon a polynomial curve f(x, y) = 0. Recall that the inversion map (x, y) 7→(xx2+y2, yx2+y2), isan inversion in the unit circle, and maps circles and lines to circles and lines. Letf˜(x, y) = (x2 + y2)Dff(xx2 + y2,yx2 + y2)= 0,where 0 ≤ Df ≤ deg(f) is the minimum integer such that f˜ is a polynomial. Note thatby applying a translation to I, we can assume that no circle containing the endpoints of apair of intervals passes through the origin. This guarantees the image of I after inversionalso contains many pairs of concyclic intervals. Therefore it is reasonable to expect f and f˜belong to a family of algebraic curves that is closed under inversion. We will assume thatthe irreducible members of the family of ‘endpoint curves’ is bounded in degree, representingthe assumption that the endpoint curves should not be arbitrarily complex. Without loss ofgenerality, assume that f has the maximum degree in this family. Suppose f has degree nand decomposition into homogeneous components f = fn + fn−1 + · · · f0. Hencef˜(x, y) = (x2 + y2)Df(fn(x, y)(x2 + y2)n+fn−1(x, y)(x2 + y2)n−1+ · · ·+ f0).64In order for n = deg(f) ≥ deg(f˜), we need 2Df ≤ n. Therefore for all 0 ≤ j ≤ n/2 we musthave that fn−j is divisible by (x2 + y2)⌈n/2⌉−j. Polynomials f possessing these divisibilityproperties are called ⌈n/2⌉-circular of degree n. In conclusion, if the endpoints of I lie on acommon polynomial curve, then we expect the curve to be a circular curve.Throughout the remainder of this section, I will be a set of N distinct intervals in R2such that more than N3/2 logN pairs of intervals are concyclic. Using the definition inequation (5.3) we also define the set of lines L = {L(a, b; c, d) : (a, b; c, d) ∈ I} in R3. ByLemma 5.3, the lines L satisfy the hypotheses Theorem 5.5. As a result, many lines in L areconcurrent, or are coplanar, or belong to a common regulus. The following three subsectionsaddress these three configurations in turn. The content of Subsection 5.4.1, 5.4.2, 5.4.3 areproofs of statements 1,2,3 in Theorem 5.2, respectively.5.4.1 Concurrent linesIn this case we know that ≳ N1/2 lines in L are concurrent. Therefore, the circular pencilsof ≳ N1/2 intervals in I contain a common circle. In other words, there is a circle in theplane for which ≳ N1/2 intervals in I have both endpoints lying on the circle. See Figure 12for an illustration.Figure 12: Case 1 of Theorem 5.2: Intervals corresponding to a set of concurrent lines in L.Both endpoints of intervals lie on a common circle.5.4.2 Coplanar linesIn this case we have that ≳ N1/2 lines in L lie in a common plane. Let L′ ⊂ L be a set of≳ N1/2 lines in a common plane, and let I′ ⊂ I be the set of ≳ N1/2 intervals correspondingto L′. Note that since no two intervals in I are contained in a common line, all pairs of linesin L′ intersect, and so all pairs of intervals in I′ are concyclic. By translating I′, we can65assume that no line containing an interval of I′ passes through the origin. In this case, all(a, b; c, d) ∈ I′ obey ad− bc ̸= 0. Consequently, all lines in L′ take the formL(t) =BD0+AC1 t, t ∈ R, (5.4)where A,B,C,D ∈ R. The line L in (5.4) contains the points (B,D, 0) and (A+B,C+D, 1).Therefore the interval I corresponding to L has endpoints at the intersection of the two circles(x−B)2 + (y −D)2 = B2 +D2(x− (A+B))2 + (y − (C +D))2 = (A+B)2 + (C +D)2 − 1. (5.5)By subtracting the second equation above from the first we see that the endpoints of Ibelong to the line 2Ax+2Cy = 1. Suppose the lines in L′ are perpendicular to the direction(α, β, γ), thenαA+ βC + γ = 0.If γ = 0, then all the lines 2Ax + 2Cy = 1 are parallel. Two parallel intervals are concyclicif and only if they are perpendicularly bisected by the same line. Therefore in this case allintervals of I′ are parallel and perpendicularly bisected by the same line. If γ ̸= 0, then−αAγ− βCγ= 1,and so the point(− α2γ,− β2γ)belongs to all lines of the form 2Ax+2Cy = 1. In other words,the set of lines containing an interval in I′ are concurrent. By translation, assume that thispoint of concurrency is the origin. To complete our characterization of the intervals in thiscase, we recall the following classical result of elementary Euclidean geometry (see e.g., in[23]).Lemma 5.6 (Power of a point). Let A,B,C,D be points in the plane. Suppose the linecontaining A and B intersects the line containing C and D at a point P . Further supposethat P is on both line segments AB and CD or on neither line segment, see Figure 13. Then66A,B,C,D are concyclic if and only if|PA| · |PB| = |PC| · |PD|.PABCDPAC BDFigure 13: Intersecting secantsLemma 5.6 is easily proved by examining similar triangles. An immediate consequenceof Lemma 5.6 is that there exists a real number h ≥ 0 such that for all (a, b; c, d) ∈ I′,(a2 + b2)(c2 + d2) = h. (5.6)The set of four endpoints of two concyclic intervals is a convex set. Therefore either1. every interval in I′ has an endpoint at the origin;2. every interval contains the origin; or3. no interval contains the origin.These three cases are illustrated in Figure 14.5.4.3 Lines in a regulusA regulus is a doubly ruled surface, i.e., through every point of the regulus, there pass twolines contained in the regulus. Reguli and planes are the only doubly ruled surfaces, whichis why they appear in Theorem 5.5. A regulus contains two families of lines such that anyline in one family intersects every line in the other, while lines in the same family do notintersect. This ‘complete bipartite’ structure implies we have two subsets L1,L2 ⊂ L suchthat L1 and L2 are lines belonging to the two respective ruling families of lines in a regulus.Moreover, |L1||L2| ≳ N . Let I1, I2 ⊂ I be the two sets of intervals corresponding to L1,L2,67Figure 14: Case 2b of Theorem 5.2: Intervals corresponding to a set of coplanar lines in L.respectively. Any interval in I1 is concyclic with any interval in I2. This gives the first partof the conclusion of Theorem 5.2 Case 3. The heuristic argument at the start of Section 5.4suggests that the curve containing the endpoints of I1 ∪ I2 should be a circular curve. Inorder to prove this, and also find the precise relationship between intervals and bicircularquartics, we will use computer aided algebra.Given three pairwise skew lines ℓ1, ℓ2, ℓ3 in R3, there exists a degree two surfaceR(x, y, z) =0 that vanishes on the three lines. Such a surface is a regulus. If ℓ1, ℓ2, ℓ3 are perpendicular toa common direction then R(x, y, z) = 0 is a hyperbolic paraboloid. Otherwise, R(x, y, z) = 0defines a hyperboloid. Suppose (ai, bi; ci, di) ∈ I1 for i = 1, 2, 3. By the structure of regulimentioned above, we know that a necessary condition for (a, b; c, d) ∈ I2 is that (a, b; c, d) isconcyclic with (ai, bi; ci, di) for i = 1, 2, 3. Define the polynomialsFi(a, b, c, d) =∣∣∣∣∣∣∣∣∣∣∣∣∣a2 + b2 a b 1c2 + d2 c d 1a2i + b2i ai bi 1c2i + d2i ci di 1∣∣∣∣∣∣∣∣∣∣∣∣∣,for i = 1, 2, 3. The points (a, b), (c, d), (ai, bi), (ci, di) are concyclic if and only if Fi(a, b, c, d) =0, for more on determinants in elementary analytic geometry, see [19]. It follows that all inter-vals in (a, b; c, d) ∈ I2 belong to the variety corresponding to the polynomial ideal ⟨F1, F2, F3⟩.To simplify calculations, by applying a dilation, translation, and rotation to I we will assumethat (a3, b3; c3, d3) = (0, 0, 1, 0). Using SageMath, we calculated a lexicographically orderedGro¨bner basis of the ideal ⟨F1, F2, F3⟩. This allows us to find a polynomial of the form(b− d)P (a, b) ∈ ⟨F1, F2, F3⟩, where P (a, b) is a bicircular quartic with coefficients depending68on (ai, bi; ci, di) for i = 1, 2. The full polynomial P (a, b) is recorded in an appendix, since ithas many terms. The solutions b−d = 0 give intervals parallel to (a3, b3; c3, d3) = (0, 0, 1, 0),and so must take the form (a, b; 1 − a, b). Such intervals are concyclic with each other,and so this is an instance of the coplanar structure in Subsection 5.4.2. Since ⟨F1, F2, F3⟩is symmetric in (a, b), (c, d) we conclude that both pairs of endpoints (a, b), (c, d) lie in thebicircular quartic P (x, y) = 0. We will see in the following section that in special cases, thecurve containing endpoints can simplify to a circular cubic, or conic.The final part of Theorem 5.2 to verify is that the bicircular quartic P (x, y) = 0 alsocontains the endpoints of intervals in I1. For this we can check with a computer that thecurve P (x, y) = 0 contains each of (ai, bi), (ci, di) for i = 1, 2, 3. Moreover, let ℓ4, ℓ5, ℓ6 be anychoice of lines belonging to the same ruling family as ℓ1, ℓ2, ℓ3 in the regulus R(x, y, z) = 0.If I4, I5, I6 are the intervals in R2 corresponding to ℓ4, ℓ5, ℓ6, then the bicircular quarticcorresponding to I4, I5, I6 is also P (x, y) = 0. We conclude P (x, y) = 0 also includes theendpoints of I4, I5, I6, and in general the endpoints of all intervals belonging to either familyI1 or I2.5.5 ConstructionsIn this section we will discuss several instances of the structure of sets of intervals corre-sponding to reguli, as well as particular geometric features they possess. Suppose I1, I2 aresets of intervals corresponding to the two rulling families of lines in the regulusR(x, y, z) = C1x2+C2y2+C3z2+C4xy+C5yz+C6xz+C7x+C8y+C9z+C10 = 0. (5.7)As in Subsection 5.4.2, assume the lines in L1,L2 are of the form in equation (5.4). LetL(t) be an arbitrary line in L1 ∪ L2 with the form of equation (5.4). Since L(t) belongs tothe regulus, we have R(At + B,Ct + D, t) = 0 for all t ∈ R. Equating coefficients of t tozero gives the following system of equations.C1A2 + C2C2 + C3 + C4AC + C5C + C6A = 0 (5.8)2C1AB + 2C2CD + C4(AD +BC) + C5D + C6B + C7A+ C8C + C9 = 0C1B2 + C2D2 + C4BD + C7B + C8D + C10 = 0.(5.9)In Subsection 5.4.2 we showed that the interval I corresponding to L(t) is contained in69the line 2Ax + 2Cy = 1. By equation (5.8) above we see that (A,C) ∈ R2 lies on a conic,call this conic C. We remark that C depends entirely upon the regulus R(x, y, z) in (5.7).We will see that different structure in I1 ∪ I2 arises depending on C. Two simple cases arethe following. If C is a point, then all intervals lie on a single line. If C is a line, then theintervals have the coplanar structure discussed in Subsection 5.4.2. The remaining cases forC when C is either a parabola, or a centred conic (i.e., an ellipse or hyperbola) all arise fromparticular reguli. We begin by considering degenerate hyperbola; when C is the union of twolines.5.5.1 C is a degenerate hyperbolaSuppose that C is given by the equation(α1A+ β1C + γ1)(α2A+ β2C + γ2) = 0,for some αi, βi, γi ∈ R, i = 1, 2. Define the following two sets of lines corresponding to thetwo factors of C,Si = {2Ax+ 2Cy = 1: αiA+ βiC + γi = 0} for i = 1, 2.As seen in Subsection 5.4.2, if γi = 0 then all lines of Si have slope βi/αi, and if γi ̸= 0then all lines of Si have(− αi2γi,− βi2γi)as a point of concurrency. We will focus on the caseγ1γ2 ̸= 0, but a similar analysis for the other cases is possible. By a dilation, rotation, andtranslation of the plane, we will assume that α1 = α2 = 0 and β1 = −β2 = γ1 = γ2 = 1. Thesystem (5.9) now simplifies to(C + 1)(C − 1) = 0−2CD + C7A+ C8C + C9 = 0−D2 + C7B + C8D + C10 = 0.Solutions to the above can be parametrized, and give the two ruling families of lines asfollows.70{(s2 − C8s− C10C7, s, 0)+ t(2Cs− C8C − C9C7, C, 1): s ∈ R}for C = ±1. (5.10)It remains to transfer these families of lines back to intervals. For this we can solve (5.5)for (x, y), giving(x, y) =12(A2 + C2)(2BC2 − 2ACD + A± C∆, 2A2D − 2ABC + C ∓ A∆), (5.11)where∆2 = 4A2D2 − 8ABCD + 4B2C2 + 4AB + 4CD − 1,and the two choices of sign give the two endpoints. We illustrate a particular instance ofthis case in Figure 15.Figure 15: An arrangement of intervals with endpoints contained on a circular cubic. Everyred-blue pair of intervals is concyclic. The lines containing intervals from each family areconcurrent at the green points. The circular cubic has the equation 120x (x2 + y2)+160x2+300xy − 36y2 + 150x+ 9 = 0.If I1, I2, I3 are three intervals such that the lines containing the intervals are concurrent,then from Subsection 5.4.2 we know that L(I1),L(I2),L(I3) are perpendicular to a commondirection. Consequently, the reguli in this case are hyperbolic paraboloids. In Figure 15 weshow an example of this case, the regulus has the equation −10y2+10z2−6x−25y−25z−4 =710. When intervals in each family are parallel, the curve containing the endpoints of theintervals is a conic. We illustrate an example in Figure 16, the regulus has the equation2x2 − 8y2 − z − 4 = 0.Figure 16: An arrangement of intervals with endpoints contained on an ellipse. Every red-blue pair of intervals is concyclic. The intervals from the same family are parallel. Theellipse has the equation 4x2 + 9y2 = 32.5.5.2 C is a non-degenerate conicThe reguli corresponding to intervals in this case are hyperboloids. Denote the set of linescontaining the intervals byT = {2Ax+ 2Cy = 1: (A,C) ∈ C}. (5.12)In the degenerate hyperbola case above, we saw that the lines in T were concurrent atone of two points; possibly a point at infinity when the lines are parallel. In this case, wewill recall a few facts on dual curves to see that the lines in T are tangent to a conic.Remarks on dual curves. Let f(x, y, z) ∈ C[x, y, z] be a homogeneous polynomial suchthat f = 0 defines a curve in the complex projective plane. The dual curve of f is theenvelope of all tangent lines to the curve. The degree of the dual curve is called the class off . Plu¨cker’s formulae tell us that the class of f is always bounded by deg(f)(deg(f) − 1).An important consequence is that the dual of a non-degenerate conic is a non-degenerateconic. For more about dual curves and Plu¨cker’s formulae see [35].Calculating the dual curve for conics is straightforward. For α, β ∈ C, the dual curve ofthe parabolaαx2 + yz = 0 is x2/α + 4yz = 0, (5.13)72and the dual curve of the centred conicαx2 + βy2 + z2 = 0 is x2/α + y2/β + z2 = 0. (5.14)We conclude that for (A,C) ∈ C the lines Ax + Cy − 1 = 0 are tangent to a conic.Furthermore, the lines in T are also all tangent to a conic, call this conic C∗.C∗ is a parabola. By applying a rotation and translation, we will assume C∗ is a verticallyopening parabola with vertex at the origin. From (5.13) we know that C is too. Equation(5.8) reduces to C1A2 + C5C = 0 and so the equation of C∗ isC5C1x2 − 2y = 0.In Figure 17 we illustrate this case corresponding to the regulus 2x2−2yz−3x−6y+z+6 =0.Figure 17: An arrangement of intervals with endpoints contained on a bicircular quartic.Every red-blue pair of intervals is concyclic. The lines containing intervals are all tangentto the parabola x2 + 2y = 0, shown in green. The bicircular quartic has the equation2(x2 + y2)2 − 2 (x2 + y2) (3x+ 4y)− 24x2 − 16y2 + 12xy + 36x+ 39y + 72 = 0.C∗ is an ellipse or hyperbola. By applying a rotation and translation, we will assume C∗is axis-parallel and centred at the origin. From (5.14) we know that C is also axis-parallel73and centred at the origin. Equation (5.8) reduces to C1A2 + C2C2 + C3 = 0 and so theequation of C∗ is4C3C1x2 +4C3C2y2 + 1 = 0.In Figure 18 we illustrate an example when C∗ is a hyperbola. The corresponding regulusis 4x2 − y2 − 4z2 + 4 = 0.Figure 18: An arrangement of intervals with endpoints contained on a bicircular quartic.Every red-blue pair of intervals is concyclic. The lines containing intervals are all tangentto the hyperbola y2 − 4x2 − 1, shown in green. The bicircular quartic has the equation(x2 + y2)2+ 16x2 − 64y2 − 4. The figure has been rotated 90 degrees.746 ConclusionThere is possibility for generalizations and extensions of the results in each chapter of thisdissertation. Below we comment on our methods and discuss ways they could be improvedor extended.6.1 DirectionsTo achieve our bound on the number of directions determined by A × B we used that theRe´dei polynomial at y = 0 had the form H(x, 0) =∏j(x− bj)m. A set of points in AG(2, p)has a Re´dei polynomial of this form if n horizontal lines each contain exactly m points,and so does not necessarily need to be a Cartesian product. For example, let A = {ai}ni=1,B = {bi}ni=1, be subsets of GF (p) such that n2 < p and 0 ̸∈ B. Consider the following setsin AG(2, p)i. {(ai + a2j , aj) : 1 ≤ i, j ≤ n},ii. {(bi + b−1j , bj) : 1 ≤ i, j ≤ n}.Note that the vertical direction is not necessarily determined by either of the above sets,and so the number of directions determined is only at least n2 − n + 1. The below setsdescribe the reciprocal directions of the sets above, but exclude ∞ (formerly the direction0). Therefore the sets below each have size at least n2 − n.I. {(x− y)(z − w)−1 + (z + w) : w, x, y, z ∈ A, z ̸= w},II. {(x− y)(z − w)−1 − (zw)−1 : w, x, y, z ∈ B, z ̸= w}.This observation suggests that there may be more usable information contained in theRe´dei polynomialH(x, y) in addition toH(x, 0). We expect that our bound can be improved,particularly in the case of A× A.Problem 6.1. For prime p, and a fixed k <√p, determine∆k,p = minA⊂GF (p)|A|=k∣∣∣∣A− AA− A∣∣∣∣ .Theorem 2.1 proves that ∆k,p ≥ k2 − k + 2, and the example A = [n] shows that∆k,p ≤ 12k2/π2. We remark that Theorem 1.3 sharpens 12/π2 to find the precise asymptotic75constant. We are also interested to know the structure of sets that minimize ∆k,p, and expectthat arithmetic progressions are minimizers.6.2 AutoconvolutionIn Chapter 3 we introduced the Problem 35 in Ben Green’s 100 open problems [25] of deter-mining the minimum Lp norm of an autoconvolution. We restate it below.Problem 6.2. Let F be the family of nonnegative functions f ∈ L1(−1/2, 1/2) such that∫f(x) dx = 1. For 1 ≤ p ≤ ∞, determineνp = inff∈F∥f ∗ f∥p = inff∈F(∫ 1−1(∫ 1/2−1/2f(t)f(x− t)dt)pdx)1/p.In Chapter 3 we determine ν2 to 4 digits of precision. Many authors have worked toimprove estimations for ν∞, but the best upper and lower bounds remain far apart. We arenot aware of efforts to estimate νp for other values p ∈ (1,∞). By Ho¨lder’s inequalilty weobtain for all p ≥ 2 the bound νp ≥ 21p− 12ν2. Also, the constant function f(x) = 1 shows thebound νpp ≤ 2/(p+ 1) for all p ≥ 1.The upper bounds on Bh[g] sets given in Corollary 3.2 relied on techniques introducedby Green [24], and were not improved upon prior to our work. The precision of our auto-convolution inequality shows that these bounds cannot be further improved without a newidea. The work in [36] shows that σh(g) ≥ 1, and this is the best known lower bound. Incontrast, we obtain σ3(1) ≤ 1.52 and σ4(1) ≤ 1.63.There are more discrete applications of Fourier analytic techniques in convolution inequal-ities. For example, an old question of Re´dei and Re´nyi on difference bases is to compute theminimum size of B ⊂ Z such that B−B ⊃ [N ] [57]. Bernshteyn and Tait recently improveda long-standing lower bound of Leech, Re´dei, and Re´nyi [4]. A continuous analogue of thedifference base problem was considered by Barnard and Steinerberger [3].6.3 OverlapOur work in Chapter 4 determines a lower bound on the minimum overlap constant µthat is close to optimal. With more powerful computation the result be improved slightly.76It appears difficult to determine µ exactly, and would be surprising if an optimal partitionfunction could be determined. The following generalization of the minimum overlap problemwas first considered by S´wierczkowski [67].Problem 6.3. Fix λ ∈ [0, 1]. For all functions f, g : [−1, 1]→ [0, 1] such that f(x)+g(x) = 1and∫f(x) dx = λ, determineµλ = inffsupx∈[−2,2]∫ 1−1f(t)g(x+ t) dt.Later on, Moser and Murdeshwar [67] improved the estimate toλ(2− λ)√4− 10λ+ 2λ2 ≤ µλ ≤(λ− α)(2− 2α− λ)3+2α + λ6,where 0 ≤ α ≤ λ is a solution to 6αλ − 6α2 = 2λ2 − λ. Their upper bound is the resultof optimizing over a 6-step function. We expect an extension of our method to provideimprovements to the lower bound.Minimum overlaps in higher dimensions have not been previously investigated, but areanother natural generalization.Problem 6.4. Let d ≥ 1. For all functions f, g : [0, 1]d → [0, 1] such that f(x) + g(x) = 1and∫f(x) dx = 1/2, determine a lower bound onµ(d) = inffsupx∈[0,2]d∫[0,1]df(t)g(x+ t) dt.Note the change of domain, and so µ(1) = µ/2, with µ as in Chapter 4. By averagingwe obtain µ(d) ≥ 2−d−2, and the constant f(x) = 1/2 function shows µ(d) ≤ 1/4. We arecurious about the asymptotic behaviour of µ(d).6.4 IntervalsOur two interval works [14, 65] discuss configurations of line segments where many pairsform a trapezoid, orthodiagonal quadrilaterals, and cyclic quadrilaterals. Other configura-tions are possible within our framework so long as an appropriate map can be found. Forexample, suppose C is family of curves that depends linearly on three parameters. Sets of77intervals such that many pairs are contained in a curve from C is a condition that can beexpressed by intersecting lines in R3. Concyclic pairs of intervals is an example of this, andso are pairs of intervals on vertically opening parabolas. Beginning with geometric objectsother than intervals is also possible. Lines in R3 are a four dimensional family, and it seemsmost natural to use a planar object with the same dimension. For example, a set of similartriangles.Guth and Katz’s Theorem 5.5 was the key technical insight to solving Erdo˝s’ distinctdistance problem. Their theorem shows that if the number of pairs of intersecting lines in R3reaches a threshold, then there must be very special structure in a large subset of the lines.However, this structure is not easy to exploit to give a result on what sets determining fewdistances look like. The below problem is due to Erdo˝s [17], who conjectured that ϵ = 1/2can be taken. For more on this structural variant of distinct distances see [63, Chapter 10].Problem 6.5. Find an ϵ > 0 such that for all sets P of N points in the plane that determine≲ N/√logN distinct distances, there exists a line containing ≳ N ϵ points of P .78References[1] S. Ball, A. Blokhuis, Lacunary polynomials over finite fields. In: G. Mullen, D. Panario(Eds.), Handbook of Finite Fields, pp. 556-562. CRC Press, 2013.[2] A. Blokhuis, S. Ball, A. E. Brouwer, L. Storme, T. Szo˝nyi. On the slopes of the graphof a function defined on a finite field. J. Combin. Theory, Ser. A 86, no. 1, 187–196,1999.[3] R. C. Barnard and S. Steinerberger. Three convolution inequalities on the real line withconnections to additive combinatorics. J. Number Theory 207, 42–55, 2020.[4] A. Bernshteyn, and M Tait. Improved lower bound for difference bases, Journal ofNumber Theory, 205: 50–58, 2019.[5] R. C. Bose and S. Chowla. Theorems in the additive theory of numbers. Comment.Math. Helv. 37, 141–147, 1962/1963.[6] Y. Caicedo, J. Go´mez and C. Trujillo. Bh[g] modular sets from Bh modular sets. JP J.Algebra Number Theory Appl. 37(1), 1–19, 2015.[7] J. Casey, On Bicircular Quartics. In: Transactions of the Royal Irish Academy, Volume24, pp. 457–569, 1871.[8] B. Chazelle, H. Edelsbrunner. An optimal algorithm for intersecting line segments inthe plane, J. ACM 39(1), 1–54, 1992.[9] J. Cilleruelo, J Jime´nez-Urroz. Bh[g] sequences. Mathematika, 47, 109–115, 2000.[10] J. Cilleruelo, I. Z. Ruzsa and C. Trujillo. Upper and lower bounds for finite Bh[g]sequences. J. Number Theory, 97 no 1. 26–34, 2002.[11] A. Cloninger, S. Steinerberger. On Suprema of Autoconvolutions with an Applicationto Sidon sets. Proc. Amer. Math. Soc. 145, no 8, 3191–3200, 2017.[12] H. Davenport. On the addition of residue classes. J. London Math. Soc., 10, 30-32, 1935.[13] D. Di Benedetto, J. Solymosi, E. P. White. On the directions determined by a Cartesianproduct in an affine Galois plane. Combinatorica, 41, no. 6, 755–763, 2021.79[14] D. Di Bennedetto, J. Solymosi, E.P. White. Combinatorics of intervals in the plane I:trapezoids. Disc. & Comput. Geom. To appear 2023.[15] P. Erdo˝s. Some remarks on number theory (Hebrew, English summary), Riveon Le-matematika, 9 45–48; MR 17, 460, 1955.[16] P. Erdo˝s. Problems and results in additive number theory. Colloque sur la The´orie desNombres, Bruxelles, 1955, pp. 127–137. Georges Thone, Lie´ge; Masson & Cie, Paris,1956.[17] P. Erdo˝s, On some metric and combinatorial geometric problems, Discrete Math. 60,147–153, 1986.[18] R. R. Fletcher. Geometric Ramifications of Invariant Expressions in the Ternary Hy-percommutative Variety. In: Toni, B. (eds) New Trends and Advanced Methods in In-terdisciplinary Mathematical Sciences. STEAM-H: Science, Technology, Engineering,Agriculture, Mathematics & Health. Springer, Cham, 2017.[19] F. A. Foraker. Determinants in Elementary Analytic Geometry. Amer. Math. Mon. 27,no. 2: 57–61, 1920.[20] G.A. Freiman, Addition of finite sets. Soviet Mathematics. Doklady, 5: 1366–1370, 1964.[21] A. Ga´cs. On a generalization of Re´dei’s theorem. Combinatorica, 23 (4) 585–598, 2003.[22] M. Z. Garaev. An explicit sum-product estimate in Fp. Int. Math. Res. Not. no. 11,2007.[23] P. Glaister. Intersecting Chords Theorem: 30 Years on. Mathematics in School, 36(1),22–22, 2007.[24] B. Green, The number of squares and Bh[g]-sets. Acta Arith. 100, no. 4, 365–390, 2001.[25] B. Green, 100 open problems, manuscript, available on request to Professor Green.[26] B. Green, T. Tao. On Sets Defining Few Ordinary Lines. Disc. Comp. Geom. 50, 409–468, 2013.[27] L. Guth, N. H. Katz. Algebraic methods in discrete analogs of the Kakeya problem.Adv. Math. Volume 225, Issue 5, 2828–2839, 2010.80[28] L. Guth, N. H. Katz. On the Erdo˝s distinct distances problem in the plane. Ann. ofMath. (2) 181(1), 155-190, 2015.[29] R. K. Guy. Unsolved Problems in Number Theory, third ed. Problem Books in Math.,Springer-Verlag, New York, 2004.[30] L. Habsieger, A. Plagne. A numerical note on upper bounds for B2[g] sets. Exp. Math.27, no. 2, 208–214, 2018.[31] B. Hanson, G. Petridis. Refined estimates concerning sumsets contained in the roots ofunity, Proc. Lond. Math. Soc., 2020.[32] J.K. Haugland. Advances in the minimum overlap problem. Journal of Number Theory,58, no 1, 71–78, 1996.[33] J.K. Haugland, The minimum overlap problem revisited, arXiv:1609.08000 [math.GM],2016.[34] N.J. Higham. The accuracy of floating point summation. SIAM J. Sci. Comput. 14,78–799, 1993.[35] H. Hilton. Plane algebraic curves, Oxford, Oxford Clarendon Press, 1920.[36] G. Johnston, M. Tait, C. Timmons. Upper and lower bounds on the size of Bh[g] sets.emphAust. Jour. Comb. 83, no 1, 129–140, 2022.[37] Kaplan, H., Sharir, M. and Shustin. E. On Lines and Joints. Disc. Com. Geom. 44,838–843, 2010.[38] N. H. Katz, C. Shen. A slight improvement to Garaev’s sum product estimate. Proc.Amer. Math. Soc., 136, no. 7, 2499-2504, 2008.[39] J. Kolla´r, Szemere´di-Trotter-type theorems in dimension 3, Adv. in Math. 271, 30–61,2015.[40] A. Lin, M. Makhul, H.N. Mojarrad, J. Schicho, K. Swanepoel, F. de Zeeuw. On SetsDefining Few Ordinary Circles. Disc. Comp. Geom. 59, 59–87, 2018.[41] B. Lindstro¨m. Bh[g]-sequences from Bh-sequences. Proc. Amer. Math. Soc, 128, 657–659, 2000.81[42] M.S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret. Applications of second order coneprogramming. Linear Algebra Appl. 284 (1) 193–228, 1998.[43] J. Madrid, J. P. G. Ramos. On optimal autocorrelation inequalities on the real line.Commun. Pure Appl. Anal. 20, no. 1, 369–388, 2021.[44] G. Martin, K. O’Bryant. The supremum of autoconvolutions, with applications to ad-ditive number theory. Illinois J. Math. 53 (1) 219–235, 2009.[45] G. Martin, K. O’Bryant. The Symmetric Subset Problem in Continuous Ramsey Theory.Exp. Math. 16, no. 2, 145–165, 2007.[46] G. Martin, E. P. White, C. H. Yip. Asymptotics for the number of directions determinedby [n]× [n] in F2p. Mathematika, 68 (2), 2022.[47] M. Matolcsi and C. Vinuesa. Improved bounds on the supremum of autoconvolutions.Jour. Math. Anal. Appl. 372, no. 2, 439–447, 2010.[48] L. Moser. On the minimum overlap problem of Erdo˝s. Acta Arith. 5, 117–119, 1959.[49] L. Moser and M. G. Murdeshwar. On the overlap of a function with the translation ofits complement, Colloq. Math. 15, 93–97, 1966.[50] T. S. Motzkin, K. E. Ralston and J. L. Selfridge. Minimal overlapping under translation.Bull. Amer. Math. Soc. 62 558, 1956.[51] B. Murphy, G. Petridis, O. Roche-Newton, M. Rudnev, I. Shkredov. New results onsum-product type growth over fields. Mathematika, 65, 588–642, 2019.[52] K. O’Bryant. A complete annotated bibliography of work related to Sidon sequences.Elec. Jour. Comb. Dynamic surveys 11, no. 11, 1–39, 2004.[53] J. Pach, M. Sharir, Combinatorial geometry and its algorithmic applications: The Alcala´lectures (No. 152), Math. Surveys Monogr. American Mathematical Society, ProvidenceRI, 2009.[54] J. Pach, M. Sharir. On vertical visibility in arrangements of segments and the queuesize in the Bentley-Ottmann line sweeping algorithm. SIAM J. Comput. 20(3), 460–470,1991,82[55] M. Laczkovich, I. Ruzsa. The number of homothetic subsets. In: R. L. Graham and J.Nesˇetrˇil, editors, The Mathematics of Paul Erdo˝s, Vol. II, volume 14 of Algorithms andCombinatorics, pp. 294–302. Springer, Berlin, 1997.[56] L. Re´dei, “Lu¨ckenhafte Polynome u¨ber endlichen Ko¨rperrn,” Birkha¨user, Basel, 1970(Engl. trans. Lacunary Polynomials over Finite Fields, North Holland, Amsterdam,1973).[57] L. Re´dei, and A. Re´nyi. On the representation of the numbers 1, 2, . . . , N by differences(in Russian). Mat. Sbornik N. S. 24 (66), 385–389, 1949.[58] I. Z. Ruzsa. An infinite Sidon sequence. Journal of Number Theory, 68: 63–71, 1998.[59] G. Salmon. A treatise on conic sections. Hodges and Smith, Dublin, 1848. Reprint ofsixth edition, AMS Chelsea Pub, Providence, RI, 2005.[60] G. Salmon. A treatise on the higher plane curves, intended as a sequel to the treatiseon conic sections. Hodges and Smith, Dublin, 1852.[61] T. Sanders. The structure theory of set addition revisited, Bull. Amer. Math. Soc. 50:93–127, 2013.[62] A. Schinzel and W.M. Schmidt. Comparison of L1- and L∞-norms of squares of poly-nomials. Acta Arith. 104, no. 3, 283–296, 2002.[63] A. Sheffer. Polynomial Methods and Incidence Theory (Cambridge Studies in AdvancedMathematics). Cambridge: Cambridge University Press, 2022.[64] J. Solymosi and F. de Zeeuw, On a question of Erdo˝s and Ulam, Disc. Comp. Geom.43 (2): 393–401, 2010.[65] J. Solymosi, E.P. White. Concyclic intervals in the plane. Disc. Comp. Geom, to appear2023.[66] A. Sto¨hr, Gelo¨ste und ungelo¨ste Fragen u¨ber Basen der natu¨rlichen Zahlenreihe. I, II,J. Reine Angew. Math. 194, 40–65, 111–140, 1955.[67] S. S´wierczkowski. On the intersection of a linear set with the translation of its comple-ment. Colloq. Math. 5 185–197, 1958.83[68] T. Szo˝nyi. Around Re´dei’s theorem. Disc. Math. 208/209, 557–575, 1999.[69] T. Szo˝nyi. On the Number of Directions Determined by a Set of Points in an AffineGalois Plane. J. Combin. Theory, Ser. A 74, no. 1, 141–146, 1996.[70] Cs. D. To´th. Binary space partitions for disjoint line segments. Disc. Comp. Geom.45(4), 617–646, 2011.[71] G.N. Watson. A Treatise on the Theory of Bessel Functions. Cambridge UniversityPress, Cambridge, England, 1922.[72] E. P. White, Erdo˝s’ minimum overlap problem, arXiv: 2201.05704 [math.CO], 2022.[73] E. P. White, An almost-tight L2 autoconvolution inequality, arXiv: 2201.05704[math.CO], 2022.[74] E. P. White, Minimum-Overlap, GitHub repository, https://github.com/ethan-white/Minimum-Overlap/, 2023.[75] A. Wiernik, M. Sharir. Planar realizations of nonlinear Davenport-Schinzel sequencesby segments. Disc. Comp. Geom. 3, 15–47, 1988.[76] G. Yu. A note on B2[G] sets. Integers, 8, A58, 5pp, 2008.84Appendix I: Minimum Overlap ProgramPrimal program as a SOCPIn order to construct the dual program of the convex program in Section 4.5 we first reformu-late this primal program as a second order cone program (SOCP). In Appendix II, we reusethe data involved in the primal program to construct the dual SOCP. The input of both theprimal and the dual is the same as the input of the convex program in Section 4.5. Theconstraints in the primal SOCP are the exact same as the constraints in Section 4.5. Theonly difference is notation of variables and that the quadratic constraints must be rearrangedto become second order cone constraints. Throughout, it will be convenient to use squarebrackets to describe individual elements of vectors and arrays. For example A[i, j] = Aijdenotes the i, jth entry.Input: N,L = 2/N, T,R, h1, h2, p1, p2, q1, q2Variables: A (2N+2T+2R+1)×1 vector variable X. The entries of X correspond to thevariables in the original convex program. This correspondence is described in the followingtable of variable expressions. The entryX0 corresponds to variable Ω in the original program.Variable expressions and data: Variable expressions and data in the primal and dual(in Appendix II) will be arranged in arrays and vectors. See Table 8 for the expressions andTable 9 for the data. In the “Description” column we will indicate how the array or vector isindexed. We use the notation [a, b] to indicate the set of integers between a and b inclusively,and [1, a] = [a]. For example, an [a] × [2, b] array A will have entries A[i, j] for 1 ≤ i ≤ aand 2 ≤ j ≤ b.Objective: minimize ΦTX = X085Constraints:∥∥Acoscone[m]X + bcoscone[m]∥∥2 ≤ cT coscone[m]X + dcoscone[m], for all 1 ≤ m ≤ 2R∥∥AparX∥∥2 ≤ dpar,cT obndX + dobnd ≥ 0,cTwbnd[i, j]X ≥ 0, for all 1 ≤ i ≤ 2, 1 ≤ j ≤ N,cT vbnd[i, j]X ≥ 0, for all 1 ≤ i ≤ 2, 1 ≤ j ≤ N,cT sum[i]X + dsum[i] ≥ 0, for all 1 ≤ i ≤ 2,cTmeanX + dmean ≥ 0,cTmomeX + dmome ≥ 0,cT sin-lower[m]X ≥ 0, for all 1 ≤ m ≤ 2RcT sin-upper[m]X ≥ 0, for all 1 ≤ m ≤ 2RcT ckbnd[i, k]X + dckbnd[i, k] ≥ 0, for all 1 ≤ i ≤ 2, 1 ≤ k ≤ T,cT dkbnd[i, k]X + ddkbnd[i, k] ≥ 0, for all 1 ≤ i ≤ 2, 1 ≤ k ≤ T,cT c1bnd[i]X + dc1bnd[i] ≥ 0, for all 1 ≤ i ≤ 2,cT d1bnd[i]X + dd1bnd[i] ≥ 0, for all 1 ≤ i ≤ 2,cT ep[i,m]X + dep[i,m] ≥ 0, for all 1 ≤ i ≤ 2, 1 ≤ m ≤ R,cT del[i,m]X + ddel[i,m] ≥ 0, for all 1 ≤ i ≤ 2, 1 ≤ m ≤ R,cT cosupX + dcosup ≥ 0.The set of constraints above is precisely the same as our program in Section 4.5. Forexample, if both sides of the first constraint above are squared and simplified, we will obtainthe constraint from the original convex program (4.25).Remark: we will continue to use the values assigned to αj,m, βj,m in Section 4.5.Obtaining the Dual SOCPThe dual of a SOCP can be concisely stated using the data from the primal, see Section4.1 of [42] for details on dual SOCPs. The standard formulation of a dual SOCP involvesequality constraints. We will eliminate some variables of the dual SOCP so that no equalityconstraints are used. This will allow us to check a particular variable assignment is farenough inside the interior of the dual space, thereby guaranteeing that assignment is feasiblein spite of worst-case floating point arithmetic errors. We begin by reviewing the formulation86Name(s) Description Defining propertyw, v [N ]-expression vector wj = Xj, vj = XN+j for 1 ≤ j ≤ Nc, d [T ]-expression vector ck = X2N+k, dk = X2N+T+k for 1 ≤ k ≤ Tϵ, δ [R]-expression vector ϵm = X2N+2T+m, δm = X2N+2T+R+m for 1 ≤ m ≤ Ra∗m [2R]-expression vector a∗m ={12cm/2 if m is evenϵm +2m sin(πm/2)π∑Tk=1(−1)km2−4k2 ck if m is oddbm [2R]-expression vector bm ={12dm/2 if m is evenδm +4π∑Tk=1k(−1)k sin(πm/2)m2−4k2 dk if m is oddFcosLB [2R]-expression vector FcosLB[m] =L2∑Nj=1 α−j,m(wj + vj)FcosUB [2R]-expression vector FcosUB[m] =L2∑Nj=1 α+j,m(wj + vj)FsinLB [2R]-expression vector FsinUB[m] =L2∑Nj=1(β−j,mwj − β+j,mvj)FsinUB [2R]-expression vector FsinUB[m] =L2∑Nj=1(β+j,mwj − β−j,mvj)Table 8: Variable expressions for SOCPof a SOCP and its dual. The standard formulation of a SOCP takes the formminimize: ΦTxsubject to: ∥Aix+ bi∥ ≤ cTi x+ di, 1 ≤ i ≤ N, (6.1)where x is a n-vector variable, Φ ∈ Rn, Ai is an ni×n matrix, bi ∈ Rni , ci ∈ Rn, and di ∈ R.We have formulated our Appendix I primal SOCP in this way. The dual to (6.1) ismaximize: −N∑i=1(bTi zi + diyi)subject to:N∑i=1(ATi z + ciyi) = Φ∥zi∥ ≤ yi, 1 ≤ i ≤ N, (6.2)where zi is a ni-vector of variables, and yi is a nonnegative variable. There are n linearequations forming the equality constraints of (6.2). For our SOCP dual, we need to eliminatethe equality constraints. Suppose that for some row 1 ≤ j ≤ n of the system of equality87Name Description Defining propertyE Integer E = 2N + 2T + 2RΦ [0, E]-vector Φ0 = 1, Φj = 0 if 1 ≤ j ≤ EAcoscone [2R]× [3]× [0, E] arrayAcoscone[m, 1]X =sin(mπ/2)a∗mmπ−FcosLB[m]/2Acoscone[m, 2]X = a∗mAcoscone[m, 3]X = bmbcoscone [2R]× [3] arraybcoscone[m, 1] = −1/2 + 2 sin2(πm/2)/(mπ)2bcoscone [m, 2] = sin(πm/2)/(mπ)bcoscone [m, 3] = 0ccoscone [2R]× [0, E] array cT coscone[m]X = sin(mπ/2)a∗mmπ−FcosLB[m]/2dcoscone [2R]-vector dcoscone [m] = 1/2 + 2 sin2(πm/2)/(mπ)2Apar [2T ]× [0, E] array Apar[k]X = ck, andApar[T + k]X = dk for all 1 ≤ k ≤ Tdpar Real dpar = 1/√2cobnd [0, E]-vector cTobndX = −Ωdobnd Real dobnd= 1cwbnd [2]× [N ]× [0, E] array cTwbnd[1, j]X = Ω− wj , for all 1 ≤ j ≤ N , andcwbnd[2, j]X = wjcvbnd [2]× [N ]× [0, E] array cTvbnd[1, j]X = Ω− vj , for all 1 ≤ j ≤ N , andcvbnd[2, j]X = vjcsum [2]× [0, E] array cT sum[i]X = (−1)i+1∑Nj=1(Xj +XN+j), for i = 1, 2dsum [2]-vector dsum[i] = (−1)iN/2, for i = 1, 2cmean [0, E]-vector cTmeanX = L∑Nj=1(jXj − (j − 1)Xj−1)dmean Real −h1N/2cmome [0, E]-vector cTmomeX = −L2∑Nj=1(j − 1)2(Xj +XN+j)dmome Real (2/3 + h22/2)N/2csin-lower [2R]× [0, E] array cT sin-lowerX = − 8mπ sin (mπ/2) bm−FsinLB[m]csin-upper [2R]× [0, E] array cT sin-upperX = 8mπ sin (mπ/2) bm+FsinLB[m]cckbnd [2]× [T ]× [0, E] array cT ckbnd[i, k]X = (−1)i+1ck for i = 1, 2 and 1 ≤ k ≤ Tdckbnd [2]× [T ] array dckbnd[i, k] = 2/π for i = 1, 2 and 1 ≤ k ≤ Tcdkbnd [2]× [T ]× [0, E] array cT dkbnd[i, k]X = (−1)i+1dk for i = 1, 2 and 1 ≤ k ≤ Tddkbnd [2]× [T ] array ddkbnd[i, k] = 2/π for i = 1, 2 and 1 ≤ k ≤ Tcc1bnd [2]× [0, E] array cT c1bnd[i]X = (−1)i+1c1 for i = 1, 2dc1bnd [2]-vector dckbnd= [−p1, p2]cd1bnd [2]× [0, E] array cT d1bnd[i]X = (−1)i+1d1 for i = 1, 2dd1bnd [2]-vector ddkbnd= [−q1, q2]cep [2]× [R]× [0, E] array cT ep[i,m]X = (−1)i+1ϵm for i = 1, 2 and 1 ≤ m ≤ Rdep [2]× [R] array dckbnd[i,m] = 14−m2/T2 · 2mπ√6T3 for i = 1, 2 and 1 ≤ m ≤ Rcdel [2]× [R]× [0, E] array cT del[i,m]X = (−1)i+1δm for i = 1, 2 and 1 ≤ m ≤ Rddel [2]× [R] array ddkbnd[i,m] = 14−m2/T2 · 4π√2T for i = 1, 2 and 1 ≤ m ≤ Rccosup [0, E]-vector cT cosupX =FcosUB[2]dcosup Real dcosup=N2(p22 +max{q21 , q22}).Table 9: Data for SOCP88constraints in (6.2) there is an index 1 ≤ k ≤ N such that vector ck is all zero except for anonzero entry at row j, then we can solve for the variable yk in terms of the other variables:yk =1ck[j](Φj −∑1≤i≤Ni ̸=k(ATi z + ciyi)[j]) ≥ 0. (6.3)After adding the inequality on the righthand side of (6.3) to the constraints of program(6.2), we can eliminate variable yk and the row j equality constraint from program (6.2).Our primal program stated above has E + 1 = 2N + 2T + 2R + 1 variables, and so thecorresponding dual has E + 1 equality constraints, corresponding to the entries of vector Φ.For each 0 ≤ j ≤ E, there is a ‘c’ vector with a unique nonzero entry in the jth row. Thiscollection of ‘c’ vectors allows us to eliminate all equality constraints. The ‘c’ vectors we useto eliminate the equality constraints are described in Table 10.89Statement of SOCP dualVariables: See Table 11.Variable expressions: See Table 12.Objective: maximize obj (defined in Table 12).Constraints:yeobnd ≥ 0yewbnd 2[j] ≥ 0 for all 1 ≤ j ≤ Nyevbnd 2[j] ≥ 0 for all 1 ≤ j ≤ Nyeckbnd 2[k] ≥ 0 for all 1 ≤ k ≤ Tyedkbnd 2[k] ≥ 0 for all 1 ≤ k ≤ Tyeep 2[m] ≥ 0 for all 1 ≤ m ≤ Ryedel 2[m] ≥ 0 for all 1 ≤ m ≤ R(ycoscone[m])2 ≥3∑i=1(zcoscone[m, i])2 for all 1 ≤ m ≤ 2R(ypar)2 ≥2T∑k=1(zpar[k])2.Name Index of nonzero rowcobnd 0cwbnd[2, j] j for 1 ≤ j ≤ Ncvbnd[2, j] N + j for 1 ≤ j ≤ Ncckbnd[2, j] 2N + j for 1 ≤ j ≤ Tcdkbnd[2, j] 2N + T + j for 1 ≤ j ≤ Tcep[2, j] 2N + 2T + j for 1 ≤ j ≤ Rcdel[2, j] 2N + 2T +R+ j for 1 ≤ j ≤ RTable 10: c-vectors with one nonzero entryFeasibility verificationWe will use a numerical solver to find feasible points in the dual SOCP, thereby giving lowerbounds to the primal optimum. Given an assignment of values to the variables of the dual,90Name Descriptionzcoscone [2R]× [3] variable arrayycoscone [2R]-vector of nonnegative variableszpar [2T ]-vector of variablesypar nonnegative variableywbnd 1 [N ]-vector of nonnegative variablesyvbnd 1 [N ]-vector of nonnegative variablesysum [2]-vector of nonnegative variablesymean nonnegative variableymome nonnegative variableysin-lower [2R]-vector of nonnegative variablesysin-upper [2R]-vector of nonnegative variablesyckbnd 1 [T ]-vector of nonnegative variablesydkbnd 1 [T ]-vector of nonnegative variablesyc1bnd [2]-vector of nonnegative variablesyd1bnd [2]-vector of nonnegative variablesyep 1 [R]-vector of nonnegative variablesydel 1 [R]-vector of nonnegative variablesycosup nonnegative variableTable 11: Variables for dual SOCPwe need to verify that in spite of any floating point arithmetic errors, the constraints aresatisfied. We use IBM’s CPLEX optimization software, which employs a barrier algorithmto solve SOCP. CPLEX uses double-precision (64-bit) arithmetic in its computations witha rounding error unit of u = 2−53. For any x ∈ R, let fl(x) be its stored double-precisionvalue. If no overflow or underflow occurs, we have the following bounds.• Let x, y ∈ R and ⋆ ∈ {+,−,×,÷} be an operation where y = 0 and ⋆ = ÷ do notboth hold, then for sum |δ| ≤ u:fl(x ⋆ y) = (x ⋆ y)(1 + δ).• Let n ∈ N. If x1, . . . , xn ∈ R, and Sn =∑nk=1 xk, then∣∣Sn − fl(Sn)∣∣ ≤ (n− 1)u1− (n− 1)un∑k=1|xk|.Details of these estimates, and improvements on them can be found in [34]. Let n ∈ N,91and xk, yk ∈ R for k = 1, . . . , n. The arithmetic expressions involved in the constraints ofour dual SOCP take the formS =n∑k=1xkyk.By the earlier two floating point estimates we have:∣∣S − fl(S)∣∣ ≤ (n− 1)u1− (n− 1)un∑k=1|fl(xiyi)| ≤ (n− 1)u(1 + u)1− (n− 1)un∑k=1|xiyi|. (6.4)After receiving a proposed assignment of dual variable values from CPLEX, we verify thatevery constraint inequality is strictly satisfied by a margin of at least the above error bound.The error bound on the righthand side of (6.4) needs to be computed. We did this byroughly estimating the individual terms. For example, consider the final constraint in ourdual SOCP:(ypar)2 −2T∑k=1(zpar[k])2 ≥ 0. (6.5)For all feasible solutions to the dual SOCP we use in this paper, the maximum absolutevalue of {zpar[k]}2Tk=1 is less than 0.0005. Therefore, the error bound for (6.5) is less that10−13. On the other hand, the minimum value of the lefthand side of (6.5) for all feasiblesolutions we use exceeds 10−11.Reusing a feasible solutionBy inspecting Table 9 we see that the parameters h1, h2, p1, p2 are only used in the ‘d’ typedata (never in A, b, or c). From (6.1) and (6.2) we see this means that h1, h2, p1, p2 will onlyaffect the objective function of the dual, but not the constraints. Hence any single feasiblesolution to the dual, will give a lower bound on the optimum for any choice of h1, h2, p1, p2.We make this precise below.Lemma 6.6. Fix a choice of input N, T,R, h1, h2, p1, p2, q1, q2 for the dual program. Supposethere exists a feasible solution for this input and let ymean,ymome,yc1bnd, and ycosup be the valuesof the dual variables ymean,ymome,yc1bnd, and ycosup for this solution. Let h′1, h′2, p′1, p′2 ∈ Rand obj(h′1, h′2, p′1, p′2) be the value of the objective function for this solution and input choiceN, T,R, h′1, h′2, p′1, p′2, q1, q2. If opt(h′1, h′2, p′1, p′2) is the optimum of the dual program withinput N, T,R, h′1, h′2, p′1, p′2, q1, q2 then92opt(h′1, h′2, p′1, p′2) ≥ obj(h1, h2, p1, p2)+N4(2(h′1 − h1)ymean + (h22 − (h′2)2)ymome + 2(p22 − (p′2)2ycosup)+ (p′1 − p1)yc1bnd[1] + (p2 − p′2)yc1bnd[2]. (6.6)Proof. From the definitions of Table 9 and Table 12 the value of obj(h′1, h′2, p′1, p′2)−obj(h1, h2, p1, p2)is precisely the quantity on the second two lines of (6.6). Since opt(h′1, h′2, p′1, p′2) ≥ obj(h′1, h′2, p′1, p′2)we have the claimed result.We now discuss how Lemma 6.6 is applied. We can find a feasible point for our dualSOCP with input N = 25000, T = 7000, R = 10 andh1 = h2 = 0.015, p1 = p2 = 0.385, −q1 = q2 = 0.02, obj = 0.37905.This feasible point makes the following variable assignments:ymean = 0.0000014902ymome = 0.00010235ycosup = 0.000038011yc1bnd = (0.35962, 0).Let opt(h′1, h′2, p′1, p′2) be as defined Lemma 6.6. We can use this feasible point to deter-mine a set of h, p ∈ R such that h, p ∈ R has opt(h, h, p, p) ≥ 0.379005. By Lemma 6.6, ifh, p ∈ R is such that250004(2(h− 0.015) · 0.0000014902 + (0.0152 − h2) · 0.00010235 + 2(0.3852 − p2) · 0.000038011)+ (0.385− p) · 0.35962 ≥ 0.379005− 0.37905, (6.7)then we can conclude opt(h, h, p, p) ≥ 0.379005. The set of (h, p) that satisfy the aboveinequality lie inside an ellipse, shown in Figure 19.93Figure 19: A subset of the region in (h, p) space where opt(h, h, p, p) ≥ 0.379005.This gives a consequence on the original f,M functions of (4.2) by Proposition 4.9. Forany f,M as in (4.2), puth = E(M), p =∫ 1−1cos(πx)f(x)dx, and q =∫ 1−1sin(πx)f(x)dx.If −0.02 ≤ q ≤ 0.02 and (h, p) defined above satisfy (6.7), then ∥M∥∞ ≥ 0.379005.94Name Description DefinitionATzcoscone [0, E]-expression vector ATzcoscone[j] =∑2Rm=1∑3i=1Acoscone[m, i, j]zcoscone[m, i]cycoscone [0, E]-expression vector cycoscone[j] =∑2Rm=1ccoscone[m, j]ycoscone[m]ATzpar [0, E]-expression vector ATzpar [j] =∑2Tk=1Apar[k, j]zpar[k]cywbnd 1 [0, E]-expression vector cywbnd 1 [j] =∑Ni=1cwbnd[1, i, j]ywbnd 1[i]cyvbnd 1 [0, E]-expression vector cywbnd 1 [j] =∑Ni=1cvbnd[1, i, j]yvbnd 1[i]cysum [0, E]-expression vector∑2i=1cysum [i, j] =csum[i, j]ysum[i]cymean [0, E]-expression vector cymean [j] =cmean[j]ymeancymome [0, E]-expression vector cymome [j] =cmome[j]ymomecysine [0, E]-expression vectorcysine[j] =∑2Rm=1csin-lower[m, j]ysin-lower[m]+∑2Rm=1csin-upper[m, j]ysin-upper[m]cycd [0, E]-expression vectorcycd[j] =∑Tm=1cckbnd[1, k, j]yckbnd 1[k]+∑Tk=1cdkbnd[1, k, j]yckbnd 1[k]+∑2i=1(cc1bnd[i, j]yc1bnd[i]+cd1bnd[i, j]yd1bnd[i])cyepdel [0, E]-expression vectorcyepdel[j] =∑Rm=1cep[1,m, j]yep 1[m]+∑Rm=1cdel[1,m, j]ydel 1[m]cycosup [0, E]-expression vector cycosup [j] =ccosup[j]ycosupsubtotal [0, E]-expression vector subtotal is the sum of all previous [0, E]-expression vectors in this tableyeobnd expression 1−subtotal[0]yewbnd 2 [N ]-expression vector yewbnd 2[j] = − subtotal[j] for 1 ≤ j ≤ Nyevbnd 2 [N ]-expression vector yevbnd 2[j] = − subtotal[N + j] for 1 ≤ j ≤ Nyeckbnd 2 [T ]-expression vector yeckbnd 2[j] = − subtotal[2N + j] for 1 ≤ j ≤ Tyedkbnd 2 [T ]-expression vector yedkbnd 2[j] = − subtotal[2N + T + j] for 1 ≤ j ≤ Tyeep 2 [R]-expression vector yeep 2[j] = − subtotal[2N + 2T + j] for 1 ≤ j ≤ Ryedel 2 [R]-expression vector yedel 2[j] = − subtotal[2N + 2T +R+ j] for 1 ≤ j ≤ RbTzcoscone expression bTzcoscone=∑2Rm=1∑3i=1bcoscone[m, i]zcoscone[m, i]dycoscone expression dycoscone=∑2Rk=1dcoscone[k]ycoscone[k]dypar expression dypar=dparypardyobnd expression dyobnd=dobndyeobnddysum expression dysum=∑2i=1dsum[i]ysum[i]dymean expression dymean=dmeanymeandymome expression dymome=dmomeymomedycd expressiondycd=∑2i=1(dc1bnd[i]yc1bnd[i]+dd1bnd[i]yd1bnd[i])+∑Tk=1(dckbnd[1, k]yckbnd 1[k]+ddkbnd[1, k]ydkbnd 1[k]+dckbnd[2, k]yeckbnd 2[k]+ddkbnd[2, k]yedkbnd 2[k])dyepdel expressiondyepdel=∑Rm=1(dep[1,m]yep 1[m]+ddel[1,m]ydel 1[m])+∑Rm=1(dep[2,m]yeep 2[m]+ddel[2,m]yedel 2[m])dycosup expression dycosup=dcosupycosupobj expression −1 times the sum of the previous 10 expressionsTable 12: Variable expressions for dual SOCP95Appendix II: Concyclic Intervals CurveBelow we give the bicircular quartic curve P (a, b) = 0 discussed in Subsection 5.4.3. Theconstant term is 0. The degree four homogeneous component:(a2 + b2)2(a1d1b2 − a1d1d2 − b1c1b2 + b1c1d2 − b1a2d2 + b1b2c2 + d1a2d2 − d1b2c2)Degree three homogeneous component:(a2+ b2)(a21c1b2b− a21c1d2b− a21d1b2a + a21d1d2a + a21a2d2b− a21b2c2b− a1c21b2b + a1c21d2b− a1d21b2b + a1d21d2b− a1d1a22b + a1d1a2b− a1d1b22b− a1d1b2a + a1d1c22b− a1d1c2b + a1d1d22b + a1d1d2a− a1a2d2b + a1b2c2b + b21c1b2b− b21c1d2b− b21d1b2a + b21d1d2a+ b21a2d2b− b21b2c2b + b1c21b2a− b1c21d2a + b1c1a22b− b1c1a2b + b1c1b22b + b1c1b2a− b1c1c22b + b1c1c2b− b1c1d22b− b1c1d2a+ b1d21b2a− b1d21d2a− b1a22c2b + b1a22d2a + b1a2c22b + b1a2d22b + b1a2d2a− b1b22c2b + b1b22d2a− b1b2c22a− b1b2c2a− b1b2d22a− c21a2d2b + c21b2c2b + c1a2d2b− c1b2c2b− d21a2d2b + d21b2c2b + d1a22c2b− d1a22d2a− d1a2c22b− d1a2d22b− d1a2d2a + d1b22c2b− d1b22d2a + d1b2c22a + d1b2c2a + d1b2d22a)Degree two homogeneous component:− a21c1a22b2 + a21c1a2b2 − a21c1b22b2 − a21c1b2ab + a21c1c22b2 − a21c1c2b2 + a21c1d22b2 + a21c1d2ab + a21d1a22ab− a21d1a2d2a2 − a21d1a2d2b2− a21d1a2ab + a21d1b22ab + a21d1b2c2a2 + a21d1b2c2b2 + a21d1b2a2 − a21d1c22ab + a21d1c2ab− a21d1d22ab− a21d1d2a2 + a21a22c2b2 − a21a22d2ab− a21a2c22b2 − a21a2d22b2 + a21b22c2b2 − a21b22d2ab + a21b2c22ab + a21b2d22ab + a1c21a22b2 − a1c21a2b2 + a1c21b22b2 + a1c21b2ab− a1c21c22b2+ a1c21c2b2 − a1c21d22b2 − a1c21d2ab + a1d21a22b2 − a1d21a2b2 + a1d21b22b2 + a1d21b2ab− a1d21c22b2 + a1d21c2b2 − a1d21d22b2 − a1d21d2ab+ a1d1a22d2a2+ a1d1a22d2b2+ a1d1b22d2a2+ a1d1b22d2b2 − a1d1b2c22a2 − a1d1b2c22b2 − a1d1b2d22a2 − a1d1b2d22b2 − a1a22c2b2 + a1a22d2ab+ a1a2c22b2+ a1a2d22b2 − a1b22c2b2 + a1b22d2ab− a1b2c22ab− a1b2d22ab− b21c1a22b2 + b21c1a2b2 − b21c1b22b2 − b21c1b2ab + b21c1c22b2− b21c1c2b2 + b21c1d22b2 + b21c1d2ab + b21d1a22ab− b21d1a2d2a2 − b21d1a2d2b2 − b21d1a2ab + b21d1b22ab + b21d1b2c2a2 + b21d1b2c2b2+ b21d1b2a2 − b21d1c22ab + b21d1c2ab− b21d1d22ab− b21d1d2a2 + b21a22c2b2 − b21a22d2ab− b21a2c22b2 − b21a2d22b2 + b21b22c2b2 − b21b22d2ab+ b21b2c22ab + b21b2d22ab− b1c21a22ab + b1c21a2d2a2 + b1c21a2d2b2 + b1c21a2ab− b1c21b22ab− b1c21b2c2a2 − b1c21b2c2b2 − b1c21b2a2+ b1c21c22ab− b1c21c2ab + b1c21d22ab + b1c21d2a2 − b1c1a22d2a2 − b1c1a22d2b2 − b1c1b22d2a2 − b1c1b22d2b2 + b1c1b2c22a2 + b1c1b2c22b2+ b1c1b2d22a2+ b1c1b2d22b2 − b1d21a22ab + b1d21a2d2a2 + b1d21a2d2b2 + b1d21a2ab− b1d21b22ab− b1d21b2c2a2 − b1d21b2c2b2 − b1d21b2a2+ b1d21c22ab− b1d21c2ab + b1d21d22ab + b1d21d2a2 + b1a22c2ab− b1a22d2a2 − b1a2c22ab− b1a2d22ab + b1b22c2ab− b1b22d2a2 + b1b2c22a2+ b1b2d22a2 − c21a22c2b2 + c21a22d2ab + c21a2c22b2 + c21a2d22b2 − c21b22c2b2 + c21b22d2ab− c21b2c22ab− c21b2d22ab + c1a22c2b2 − c1a22d2ab− c1a2c22b2 − c1a2d22b2 + c1b22c2b2 − c1b22d2ab + c1b2c22ab + c1b2d22ab− d21a22c2b2 + d21a22d2ab + d21a2c22b2 + d21a2d22b2 − d21b22c2b2+ d21b22d2ab− d21b2c22ab− d21b2d22ab− d1a22c2ab + d1a22d2a2 + d1a2c22ab + d1a2d22ab− d1b22c2ab + d1b22d2a2 − d1b2c22a2 − d1b2d22a2Degree one homogeneous component:a21c1a22d2b− a21c1a2d2b + a21c1b22d2b− a21c1b2c22b + a21c1b2c2b− a21c1b2d22b− a21d1a22c2b + a21d1a2c22b + a21d1a2d22b + a21d1a2d2a− a21d1b22c2b− a21d1b2c2a− a1c21a22d2b + a1c21a2d2b− a1c21b22d2b + a1c21b2c22b− a1c21b2c2b + a1c21b2d22b− a1d21a22d2b + a1d21a2d2b− a1d21b22d2b + a1d21b2c22b− a1d21b2c2b + a1d21b2d22b + a1d1a22c2b− a1d1a22d2a− a1d1a2c22b− a1d1a2d22b + a1d1b22c2b− a1d1b22d2a+ a1d1b2c22a + a1d1b2d22a + b21c1a22d2b− b21c1a2d2b + b21c1b22d2b− b21c1b2c22b + b21c1b2c2b− b21c1b2d22b− b21d1a22c2b + b21d1a2c22b+ b21d1a2d22b + b21d1a2d2a− b21d1b22c2b− b21d1b2c2a + b1c21a22c2b− b1c21a2c22b− b1c21a2d22b− b1c21a2d2a + b1c21b22c2b + b1c21b2c2a− b1c1a22c2b + b1c1a22d2a + b1c1a2c22b + b1c1a2d22b− b1c1b22c2b + b1c1b22d2a− b1c1b2c22a− b1c1b2d22a + b1d21a22c2b− b1d21a2c22b− b1d21a2d22b− b1d21a2d2a + b1d21b22c2b + b1d21b2c2a96
Thesis/Dissertation
eng
Mathematics
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Solymosi, Jozsef, 1959-
Topics in discrete analysis
Text