Distinct distances between points and lines

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Erdos Distinct Distances Problem and Extensions over Finite Spaces

Van Thang Pham

In this thesis we study a number of problems in Discrete Combinatorial Geometry in finite spaces. The contents in this thesis are structured as follows: In Chapter 1 we will state the main results and the notations which will be used throughout the thesis. Chapter 2 is a version of the paper entitled "Sumsets of the distance sets in finite spaces", which has been submitted for publication, (2017). Chapter 3 is a version of the paper entitled "Three-variable expanding polynomials and higher-dimensional distinct distances", which has been submitted for publication, co-authored with L. A. Vinh and de Zeeuw. The author was one of the main investigators of this chapter. Chapter 4 is a postprint version of the paper entitled "Distinct distances on regular varieties over finite fields", Journal of Number Theory, 173(2017), 602-613, co-authored with D. D. Hieu. The author was one of the main investigators of this chapter. Chapter 5 is a postprint version of the paper entitled " Incidences between points and generalized spheres over finite fields and related problems", Forum Mathematicum, Volume 29, Issue 2 (Mar 2017), co-authored with N. D. Phuong and L. A. Vinh. The author was one of the main investigators of this chapter. Chapter 6 is a version of the paper entitled "Distinct spreads in finite spaces", which has been submitted for publication, co-authored with B. Lund and L. A. Vinh. The author was one of the main investigators of this chapter. Chapter 7 is a version of the paper entitled "Paths in pseudo-random graphs", which has been submitted for publication, co-authored with L. A. Vinh. The author was one of the main investigators of this chapter. Chapter 8 is a version of the paper entitled "Conditional expanding bounds for two-variable functions over arbitrary fields", which has been submitted for publication, co-authored with Hossein Nassajian Mojarrad. The author was one of the main investigators of this chapter. Chapter 9 is a postprint version of the paper entitled "A Szemeredi-Trotter type theorem, sum-product estimates in finite quasifields, and related results", Journal of Combinatorial Theory Series A, 147(2017), 55-74, co-authored with Michael Tait, Craig Timmons, Le Anh Vinh. The author was one of the main investigators of this chapter. The content of this chapter also appears in Michael Tait's Phd thesis. In Chapter 10, we will mention some open problems on Erd\H{o}s distinct distances problem and generalizations.

EPFL2017

Algebraic and topological methods in combinatorics

Adrian Claudiu Valculescu

The present thesis deals with problems arising from discrete mathematics, whose proofs make use of tools from algebraic geometry and topology. The thesis is based on four papers that I have co-authored, three of which have been published in journals, and one has been submitted for publication (and also appeared as a preprint on the arxiv, and as an extendend abstract in a conference). Specifically, we deal with the following four problems: \begin{enumerate} \item We prove that if

M\in \mathbb{C}^{2\times2}

is an invertible matrix, and

B_M:\mathbb{C}^2\times\mathbb{C}^2\to\mathbb{C}

is a bilinear form

B_M(p,q)=p^TMq

, then any finite set

S

contained in an irreducible algebraic curve

C

of degree

d

\mathbb{C}^2

determines

\Omega_d(|S|^{4/3})

distinct values of

B_M

, unless

C

is a line, or is linearly equivalent to a curve defined by an equation of the form

x^k=y^l

, with

k,l\in\mathbb{Z}\backslash\\{0\\}

, and

\gcd(k,l)=1

. \item We show that if we are given

m

points and

n

lines in the plane, then the number of distinct distances between the points and the lines is

\Omega(m^{1/5}n^{3/5})

, as long as

m^{1/2}\le n\le m^2

. Also, we show that if we are given

m

points in the plane, not all collinear, then the number of distances between these points and the lines that they determine is

\Omega(m^{4/3})

. We also study three-dimensional versions of the distinct point-line distances problem. \item We prove the lower bound

\Omega(|S|^4)

on the number of ordinary conics determined by a finite point set

S

\mathbb{R}^2

, assuming that

S

is not contained in a conic, and at most

c|S|

points of

S

lie on the same line (for some $0

EPFL2017

Erdos Distinct Distances Problem and Extensions over Finite Spaces

Van Thang Pham

EPFL2017

Algebraic and topological methods in combinatorics

Adrian Claudiu Valculescu

M\in \mathbb{C}^{2\times2}

is an invertible matrix, and

B_M:\mathbb{C}^2\times\mathbb{C}^2\to\mathbb{C}

is a bilinear form

B_M(p,q)=p^TMq

, then any finite set

S

contained in an irreducible algebraic curve

C

of degree

d

\mathbb{C}^2

determines

\Omega_d(|S|^{4/3})

distinct values of

B_M

, unless

C

is a line, or is linearly equivalent to a curve defined by an equation of the form

x^k=y^l

, with

k,l\in\mathbb{Z}\backslash\\{0\\}

, and

\gcd(k,l)=1

. \item We show that if we are given

m

points and

n

lines in the plane, then the number of distinct distances between the points and the lines is

\Omega(m^{1/5}n^{3/5})

, as long as

m^{1/2}\le n\le m^2

. Also, we show that if we are given

m

points in the plane, not all collinear, then the number of distances between these points and the lines that they determine is

\Omega(m^{4/3})

. We also study three-dimensional versions of the distinct point-line distances problem. \item We prove the lower bound

\Omega(|S|^4)

on the number of ordinary conics determined by a finite point set

S

\mathbb{R}^2

, assuming that

S

is not contained in a conic, and at most

c|S|

points of

S

lie on the same line (for some $0

EPFL2017