BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We study the Erd\H os-Falconer distance problem for a set A⊂F2, where F is a field of positive characteristic p. If F=Fp and the cardinality ∣A∣ exceeds p5/4, we prove that A determines an asymptotically full proportion of the feasible p distances. For small sets A, namely when ∣A∣≤p4/3 over any F, we prove that either A determines ≫∣A∣2/3. For both large and small sets, the results proved are in fact for pinned distances.
We prove a nontrivial energy bound for a finite set of affine transformations over a general field and discuss a number of implications. These include new bounds on growth in the affine group, a quantitative version of a theorem by Elekes about rich lines in grids. We also give a positive answer to a question of Yufei Zhao that for a plane point set P for which no line contains a positive proportion of points from P, there may be at most one line, meeting the set of lines defined by P in at most a constant multiple of |P| points.
Let f be a smooth real function with strictly monotone first k derivatives. We show that for a finite set A, with ∣A+A∣≤K∣A∣, ∣2kf(A)−(2k−1)f(A)∣≫k∣A∣k+1−o(1)/KOk(1). We deduce several new sum-product type implications, e.g. that A+A being small implies unbounded growth for a many enough times iterated product set A⋯A.
It is shown that the number of distinct types of three-point hinges, defined by a real plane set of n points is ≫n2log−3n, where a hinge is identified by fixing two pair-wise distances in a point triple. This is achieved via strengthening (modulo a logn factor) of the Guth-Katz estimate for the number of pair-wise intersections of lines in R3, arising in the context of the plane Erd\H os distinct distance problem, to a second moment incidence estimate. This relies, in particular, on the generalisation of the Guth-Katz incidence bound by Solomon and Sharir.
Consider the projections of a finite set A⊂Rn onto the coordinate hyperplanes. How small can the sum of the sizes of these projections be, given the size of A? In a different form, this problem has been studied earlier in the context of edge-isoperimetric inequalities on graphs, and it is can be derived from the known results that there is a linear order on the set of n-tuples with non-negative integer coordinates, such that the sum in question is minimised for the initial segments with respect to this order. We present a new, self-contained and constructive proof, enabling us to obtain a stability result and establish algebraic properties of the smallest possible projection sum. We also solve the problem of minimising the sum of the sizes of the one-dimensional projections.
We prove that for some universal c, a non-collinear set of N>c1 points in the Euclidean plane determines at least clogNN distinct areas of triangles with one vertex at the origin, as well as at least clogNN distinct dot products. This in particular implies a sum-product bound ∣A⋅A±A⋅A∣≥clog∣A∣∣A∣2 for a discrete A⊂R.
We prove that a finite subset A of the projective line FP1 over a field F of positive characteristic p determines Ω(∣A∣2) distinct cross-ratios, as long as ∣A∣<p.
We discuss a unified approach to a class of geometric combinatorics incidence problems in 2D, of the Erdös distance type. The goal is obtaining the second moment estimate, that is given a finite point set S and a function f on S×S, an upper bound on the number of solutions of f(p,p′)=f(q,q′)=0,(p,p′,q,q′)∈S×S×S×S.(∗) E.g., f is the Euclidean distance in the plane, sphere, or a sheet of the two-sheeted hyperboloid. Our tool is the Guth-Katz incidence theorem for lines in RP3, but we focus on how the original 2D problem is made amenable to it. This procedure was initiated by Elekes and Sharir, based on symmetry considerations. However, symmetry considerations can be bypassed or made implicit. The classical Plücker-Klein formalism for line geometry enables one to directly interpret a solution of (∗) as intersection of two lines in RP3. This allows for a very brief argument extending the Euclidean plane distance argument to the spherical and hyperbolic distances. We also find instances of the question (∗) without underlying symmetry group. The space of lines in the three-space, the Klein quadric K, is four-dimensional. We start out with an injective map F:S×S→K, from a pair of points in 2D to a line in 3D and seek a combinatorial problem in the form (∗), which can be solved by applying the Guth-Katz theorem to the set of lines in question. We identify a few new such problems and generalise the existing ones.
Let F be a field of characteristic p>2 and A⊂F have sufficiently small cardinality in terms of p. We improve the state of the art of a variety of sum-product type inequalities. In particular, we prove that ∣AA∣2∣A+A∣3≫∣A∣6,∣A(A+A)∣≫∣A∣3/2. We also prove several two-variable extractor estimates: ∣A(A+1)∣≫∣A∣9/8, ∣A+A2∣≫∣A∣11/10,∣A+A3∣≫∣A∣29/28,∣A+1/A∣≫∣A∣31/30. Besides, we address questions of cardinalities ∣A+A∣ vs ∣f(A)+f(A)∣, for a polynomial f, where we establish the inequalities max(∣A+A∣,∣A2+A2∣)≫∣A∣8/7,max(∣A−A∣,∣A3+A3∣)≫∣A∣17/16. Szemerédi-Trotter type implications of the arithmetic estimates in question are that a Cartesian product point set P=A×B in F2, of n elements, with ∣B∣≤∣A∣<p2/3 makes O(n3/4m2/3+m+n) incidences with any set of m lines. In particular, when ∣A∣=∣B∣, there are ≪n9/4 collinear triples of points in P, ≫n3/2 distinct lines between pairs of its points, in ≫n3/4 distinct directions. Besides, P=A×A determines ≫n9/16 distinct pair-wise distances. These estimates are obtained on the basis of a new plane geometry interpretation of the incidence theorem between points and planes in three dimensions, which we call collisions of images.
Let F be a field with positive odd characteristic p. We prove a variety of new sum-product type estimates over F. They are derived from the theorem that the number of incidences between m points and n planes in the projective three-space PG(3,F), with m≥n=O(p2), is O(mn+km), where k denotes the maximum number of collinear planes. The main result is a significant improvement of the state-of-the-art sum-product inequality over fields with positive characteristic, namely that \begin{equation}\label{mres} |A\pm A|+|A\cdot A| =Ω\left(|A|^{1+\frac{1}{5}}\right), \end{equation} for any A such that ∣A∣<p85.
This paper is an erratum to our paper, entitled "On an application of Guth-Katz theorem", Math. Res. Lett. 18 (2011), no. 4, 691-697. Let F be the real or complex field and ω a non-degenerate skew-symmetric bilinear form in the plane F2. We prove that for finite a point set P⊂F2∖{0}, the set Tω(P) of nonzero values of ω in P×P, if nonempty, has cardinality Ω(N9/13). A presumably near-sharp estimate Ω(N/logN) was claimed in the abovemnetioned paper over the reals for a symmetric or skew-symmetric form ω. However, the set-up for the proof was flawed. We discuss why we believe that justifying this claim in full strength is a major open problem. In the special case when P=A×A, where A is a set of at least two reals, we establish the following sum-product type estimates: ∣AA+AA∣=Ω(∣A∣19/12), and ∣AA−AA∣=Ω(log2/17∣A∣∣A∣26/17).
We prove an incidence theorem for points and planes in the projective space P3 over any field F, whose characteristic p=2. An incidence is viewed as an intersection along a line of a pair of two-planes from two canonical rulings of the Klein quadric. The Klein quadric can be traversed by a generic hyperplane, yielding a line-line incidence problem in a three-quadric, the Klein image of a regular line complex. This hyperplane can be chosen so that at most two lines meet. Hence, one can apply an algebraic theorem of Guth and Katz, with a constraint involving p if p>0. This yields a bound on the number of incidences between m points and n planes in P3, with m≥n as O(mn+mk), where k is the maximum number of collinear planes, provided that n=O(p2) if p>0. Examples show that this bound cannot be improved without additional assumptions. This gives one a vehicle to establish geometric incidence estimates when p>0. For a non-collinear point set S⊆F2 and a non-degenerate symmetric or skew-symmetric bilinear form ω, the number of distinct values of ω on pairs of points of S is Ω[min(∣S∣32,p)]. This is also the best known bound over R, where it follows from the Szemerédi-Trotter theorem. Also, a set S⊆F3, not supported in a single semi-isotropic plane contains a point, from which Ω[min(∣S∣21,p)] distinct distances to other points of S are attained.
We use elementary methods to prove an incidence theorem for points and spheres in Fqn. As an application, we show that any point set of P⊂Fq2 with ∣P∣≥5q determines a positive proportion of all circles. The latter result is an analogue of Beck's Theorem for circles which is optimal up to multiplicative constants.
We extend the recent Solymosi's sum-product estimate for reals to the complex case.
New lower bounds involving sum, difference, product, and ratio sets for a set $A\subset \C$ are given. The estimates involving the sum set match, up to constants, the one obtained by Solymosi for the reals and are obtained by generalising his approach to the complex plane. The bounds involving the difference set are slightly weaker. They improve on the best known ones, including the case A⊂R, which also due to Solymosi, by means of combining the use of the Szemerédi-Trotter theorem with an arithmetic combinatorics technique.
Given two points p,q in the real plane, the signed area of the rectangle with the diagonal [pq] equals the square of the Minkowski distance between the points p,q. We prove that N>1 points in the Minkowski plane R1,1 generate Ω(logNN) distinct distances, or all the distances are zero. The proof follows the lines of the Elekes/Sharir/Guth/Katz approach to the Erd\H os distance problem, analysing the 3D incidence problem, arising by considering the action of the Minkowski isometry group ISO∗(1,1). The signature of the metric creates an obstacle to applying the Guth/Katz incidence theorem to the 3D problem at hand, since one may encounter a high count of congruent line intervals, lying on null lines, or "light cones", all these intervals having zero Minkowski length. In terms of the Guth/Katz theorem, its condition of the non-existence of "rich planes" generally gets violated. It turns out, however, that one can efficiently identify and discount incidences, corresponding to null intervals and devise a counting strategy, where the rich planes condition happens to be just ample enough for the strategy to succeed. As a corollary we establish the following near-optimal sum-product type estimate for finite sets A,B⊂R, with more than one element: ∣(A±B)⋅(A±B)∣≫log∣A∣+log∣B∣∣A∣∣B∣.
It is shown that any subset E of a plane over a finite field $\F_q$, of cardinality ∣E∣>q determines not less than 2q−1 distinct areas of triangles, moreover once can find such triangles sharing a common base. It is also shown that if ∣E∣≥64qlog2q, then there are more than 2q distinct areas of triangles sharing a common vertex. The result follows from a finite field version of the Beck theorem for large subsets of $\F_q^2$ that we prove. If ∣E∣≥64qlog2q, there exists a point z∈E, such that there are at least 4q straight lines incident to z, each supporting the number of points of E other than z in the interval between 2q∣E∣ and q2∣E∣. This is proved by combining combinatorial and Fourier analytic techniques. We also discuss higher-dimensional implications of these results in light of recent developments.
There is a parallelism between growth in arithmetic combinatorics and growth in a geometric context. While, over R or C, geometric statements on growth often have geometric proofs, what little is known over finite fields rests on arithmetic proofs. We discuss strategies for geometric proofs of growth over finite fields, and show that growth can be defined and proven in an abstract projective plane -- even one with weak axioms.
Let P be a set of N points in the Euclidean plane, where a positive proportion of points lies off a single straight line. This note points out two facts concerning the number of equivalence classes of triangles that P determines, namely that (i) P determines Ω(N2) different equivalence classes of congruent triangles, and (ii) P determines Ω(logNN2) different equivalence classes of similar triangles. The first fact follows from the recent theorem by Guth-Katz on point-line incidences in R3. The second one, perhaps not so well known, is due to Solymosi and Tardos.
We prove an elementary additive combinatorics inequality, which says that if A is a subset of an Abelian group, which has, in some strong sense, large doubling, then the difference set A-A has a large subset, which has small doubling.
This note improves the best known exponent 1/12 in the prime field sum-product inequality (for small sets) to 1/11, modulo a logarithmic factor.
New lower bounds involving sum, difference, product, and ratio sets for $A\subset \C$ are given.
Let P=A×A⊂Fp×Fp, p a prime. Assume that P=A×A has n elements, n<p. See P as a set of points in the plane over Fp. We show that the pairs of points in P determine ≥cn1+1/267 lines, where c is an absolute constant. We derive from this an incidence theorem: the number of incidences between a set of n points and a set of n lines in the projective plane over $\F_p$ (n<p) is bounded by Cn3/2−1/10678, where C is an absolute constant.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.