Jozsef Solymosi

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|

We discuss three problems related to combinatorial geometry, based on two separate works. The first work concerns arrangements of intervals in R² for which there are many pairs forming trapezoids, meaning the convex hull of the pair is a trapezoid. We characterise arrangements forming more than a certain number of trapezoids, showing that all such sets have underlying algebraic structure. An important role is played in particular by conic curves. The proof uses a transformation from intervals in the plane to lines in R³ and then relies on a theorem of Guth and Katz on intersecting lines in R³. The second work concerns combinatorial problems for discretised sets, where objects are only distinguishable up to some small scale. Discretised sets can be used to approximate fractal sets, and our results imply improved quantitative bounds for the 1/2-Furstenberg set problem in R² and the upper Minkowski dimension of Besicovitch sets in R³, as well as slight generalisations of each of these problems. The techniques involved in this second work are mostly combinatorial and our main ingredient is the discretised sum-product theorem from additive combinatorics. In particular, we reduce the 1/2-Furstenberg set problem to the discretised-sum product problem and reduce the Besicovitch set problem to the Furstenberg set problem.

View record

Extremal problems, in general, ask for the optimal size of certain finite objects when some restrictions are imposed. In extremal combinatorics, a major field in combinatorics, one studies how global properties guarantee the existence of local substructures, or equivalently, how avoiding local substructures poses a constraint on global quantities. In this thesis, we study the following three problems in combinatorics.The first problem is related to the Brown–Erdos–Sos conjecture, which can bereformulated as a problem of finding a dense substructure, namely a large numberof triples, spanned by a given number of elements in a quasigroup. In the special case of finite groups, we show in Chapter 2 that in every dense set of triples, there exists a subset of m elements which spans 4m/3 (1 − o(1)) triples, as m tends to infinity, which is much higher than the conjectured amount m − 3 for a general quasigroup. Later in the chapter, we give an elementary proof that, in finite groups, the maximum number of triples spanned by m elements has order m².The second problem concerns planar polygons in the 3-space. The maximum possible number of polygons from a given number of points is controlled by their intersection properties. Two hexagons in the space are said to intersect badly if their intersection consists of at least one common vertex as well as an interior point. In Chapter 3, we show that the number of hexagons on n points in 3-space without bad intersections is o(n²), under a mild assumption that the hexagons are ‘fat’. The main tool we used is the triangle removal lemma.The last problem in this dissertation is about the sum-product conjecture of Erdos and Szemeredi. The sum-product estimate concerns the larger size of the sumset and productset in terms of the size of the set itself. In Chapter 4 we prove an estimate with exponent 4/3 for the ring of quaternions and a certain family of well-conditioned matrices, using the boundedness of the kissing numbers.

View record

In this thesis, we investigate topics related to the Green-Tao theorem on arithmetic progression in primes in higher dimensions. Our main tool is the pseudorandom measure majorizing primes defined in [51] concentrated on almost primes. In chapter 2, we combine the sieve technique used in constructing pseudorandom measure (in this case, Goldston-Yildirim sum and almost primes) with the circle method of Birch to study the number of almost prime solutions of diophantine systems (with some rank conditions). Our rank condition is similar to the integer case, due to the heuristics that almost primes are pseudorandom. In chapter 3, we investigate the generalization of Green-Tao’s theorem to higher dimensions in the case of corner configuration. We apply the transference principle of Green-Tao (with hyperplane separation technique of Gowers) in this setting. This problem is also related to the densification trick in [16]. In chapter 4, we extend the result of Chapter 3 to obtain the full multi-dimensional analogue of the Green-Tao’s theorem, using hypergraph regularity method by directly proving a version of hypergraph removal lemma in the weighted hypergraphs. The method is to run an energy increment on a parametric weight systems of measures, rather than on a single measure space, to overcome the presence of intermediate weights. Contrary to [110], [68] where theauthors investigate the problem using a measure supported on primes and infinite linear form conditions, relying on the Gowers Inverse Norms Conjecture.

View record

In this thesis we give results on unit and rational distances, structure results for surfaces containing many points of a cartesian product and a survey of various, mainly combinatorial, applications of the Subspace Theorem. We take an algebraic approach to most of the problems and use techniques from commutative algebra, incidence geometry, number theory and graph theory. In Chapter 2 we give extensions of a result of Elekes and Rónyai that says that if the graph of a real (or complex) polynomial contains many points of a cartesian product then the polynomial has a special additive or multiplicative form. We extend this to asymmetric cartesian products and to higher dimensions. Elekes and Rónyai’s result was used to prove a conjecture of Purdy on the number of distinct distances between two collinear point sets in the plane. Our extensions give improved bounds for the conjecture. In Chapter 3 we prove a special case of the Erdős unit distance problem. This problem asks for the maximum possible number of unit distances between n points in the plane in the form of an asymptotic upper bound. We provide an upper bound of n^(1+7/sqrt(log(n))) when we only consider unit distancescorresponding to roots of unity and give a superlinear lower bound. We also consider related rational distance problems. We require an algebraic result of Mann on the number of solutions of linear equations of roots of unity. In Chapter 4 we extend our result from the previous chapter to unit distances coming from a multiplicative subgroup of ℂ^* of “low” rank. We usea corollary of the Subspace Theorem. In this case we get, for ε > 0, at most cn^(1+ε) unit distances. We show that the well known lower bound construction of Erdős for the general unit distance problem consists of distances from such a subgroup and so our result applies to the best known maximal unit distance sets. In Chapter 5 we give a survey of various applications of the Subspace Theorem including less well known combinatorial applications such as sum-product estimates and line configurations with few distinct intersections.

View record

This thesis includes three papers and one expository chapter as backgroundfor one of the papers. These papers have in common that they combinealgebra with discrete geometry, mostly by using algebraic tools to provestatements from discrete geometry. Algebraic curves and number theoryalso recur throughout the proofs and results. In Chapter 1, we will detailthese common threads.In Chapter 2, we prove that an infinite set of points in R² such that allpairwise distances are rational cannot be contained in an algebraic curve,except if that curve is a line or a circle, in which case at most 4 respectively 3points of the set can be outside the line or circle. In the proof we use theclassification of curves by their genus, and Faltings' Theorem.In Chapter 3, we informally present an elementary method for computingthe genus of a planar algebraic curve, illustrating some of the techniques inChapter 2.In Chapter 4, we prove a bound on the number of unit distances that canoccur between points of a finite set in R², under the restriction that the linesegments corresponding to these distances make a rational angle with thehorizontal axis. In the proof we use graph theory and an algebraic theoremof Mann.In Chapter 5, we give an upper bound on the length of a simultaneousarithmetic progression (a two-dimensional generalization of an arithmeticprogression) on an elliptic curve, as well as for more general curves. Wegive a simple proof using a theorem of Jarnik, and another proof using theCrossing Inequality and some bounds from elementary algebraic geometry,which gives better explicit bounds.

View record