The constant of pointline incidence constructions Martin BalkoAdam SheerRuiwen Tang Abstract

2025-05-02 0 0 459.42KB 19 页 10玖币

侵权投诉

The constant of point–line incidence constructions

Martin Balko∗Adam Sheﬀer†Ruiwen Tang‡

Abstract

We study a lower bound for the constant of the Szemer´edi–Trotter theorem. In

particular, we show that a recent inﬁnite family of point-line conﬁgurations satisﬁes

I(P,L)≥(c+o(1))|P|2/3|L|2/3, with c≈1.27. Our technique is based on studying

a variety of properties of Euler’s totient function. We also improve the current best

constant for Elekes’s construction from 1 to about 1.27. From an expository perspective,

this is the ﬁrst full analysis of the constant of Erd˝os’s construction.

1 Introduction

In recent years, there has been signiﬁcant interest in ﬁnding exact constants for incidence-

related problems. For example, Yu and Zhao [18] derived the constant of the joints problem,

and Bukh and Chao [5] derived the constant of the ﬁnite ﬁeld Kakeya problem (building

upon previous works [8, 16]). In this work, we explore the constant of what one may call

the fundamental theorem of incidence theory: The Szemer´edi–Trotter theorem.

Throughout this paper we work in R2. Let Pbe a ﬁnite set of points and let Lbe a

ﬁnite set of lines. An incidence is a point–line pair (p, `)∈ P × L such that p∈`. The

number of incidences in P × L is denoted as I(P,L).

Theorem 1.1 (Szemer´edi–Trotter).Every set of points Pand set of lines Lsatisfy that

I(P,L) = O(|P|2/3|L|2/3+|P| +|L|).

Theorem 1.1 has a large number of applications in a wide-variety of ﬁelds, including

combinatorics, harmonic analysis, number theory, theoretical computer science, and model

theory (for example, see [3, 4, 6, 7]). This theorem has been known to be asymptotically tight

since its appearance about 40 years ago. However, the exact constant remains unknown.

When |L| =O(|P|1/2), the bound of Theorem 1.1 is dominated by the term |P|. When

|L| = Ω(|P|2), the bound of Theorem 1.1 is dominated by the term |L|. These are considered

as less interesting extreme cases. The main case is when1|L| =ω(|P|1/2) and |L| =o(|P|2),

so the dominating term is |P|2/3|L|2/3.

∗Faculty of Mathematics and Physics, Charles University, Czech Republic. balko@kam.mﬀ.cuni.cz. Sup-

ported by the grant no. 21/32817S of the Czech Science Foundation (GA ˇ

CR) and by the Center for Foun-

dations of Modern Computer Science (Charles University project UNCE/SCI/004). This article is part of a

project that has received funding from the European Research Council (ERC) under the European Union’s

Horizon 2020 research and innovation programme (grant agreement No 810115).

†Department of Mathematics, Baruch College, City University of New York, NY, USA.

adamsh@gmail.com. Supported by NSF award DMS-1802059 and by PSCCUNY award 63580.

‡Stuyvesant High School. 345 Chambers St, New York, NY 10282. ruiwentang@gmail.com.

1The notation X=ω(Y) means “Xis asymptotically larger than Y.” The notation X=o(Y) means

“Xis asymptotically smaller than Y.”

arXiv:2210.04821v1 [math.CO] 10 Oct 2022

The current best upper bound, taken from [1], is I(P,L)≤2.44|P|2/3|L|2/3(this im-

proves the previous bound of 2.5 from [14]). The status of the lower bound is not as simple.

During the 20th century, only a single construction with Θ(|P|2/3|L|2/3) incidences was

known, due to Erd˝os (see Section 2). Pach and T´oth [15] analyzed Erd˝os’s construction,

to obtain c|P|2/3|L|2/3incidences, where c= (3/4π2)1/3≈0.42. Most of the steps of this

analysis were omitted in the paper [15], making it diﬃcult to verify. Twenty years later,

Cibulka, Valtr, and the ﬁrst author of the current work [12] spotted a mistake in the part of

the analysis in [15] that did appear on the paper. Fixing this mistake leads to the improved

bound c= 3 ·(3/4π2)1/3≈1.27. It remained unclear whether additional issues appear in

the portion of the analysis that is omitted in [15].

In the early 2000s, Elekes [9] discovered a simpler point–line conﬁguration that achieves

Θ(|P|2/3|L|2/3) incidences (see Section 2). The best constant previously obtained for this

construction was by Apfelbaum [2], who showed that I(P,L)≥ |P|2/3|L|2/3. In other words,

Apfelbaum obtained the constant c= 1.

We set n=|P|. In Erd˝os’s construction, Pis a √n×√nsection of the integer lattice.

In Elekes’s construction, Pis a much taller and thinner section of the integer lattice. Re-

cently, Silier and the second author of the current work [17] discovered an inﬁnite family of

constructions with Θ(|P|2/3|L|2/3) incidences. In this family, the point set is an nα×n1−α

section of the integer lattice, where 1/3≤α≤1/2. Erd˝os’s construction is obtained when

α= 1/2 and Elekes’s construction is obtained when α= 1/3. For a description of this

family, see Section 2. Previously, no work analyzed the constants of these constructions.

The following theorem is the main result of the current work.

Theorem 1.2. Consider a construction P,Lfrom the inﬁnite family with 1/3≤α≤1/2,

|L| =o(|P|2), and |L| =ω(|P|2−3α). Then I(P,L)=(c+o(1))|P|2/3|L|2/3, where c=

3·(3/4π2)1/3≈1.27.

The condition |L| =o(|P|2) only means that we are in the main case, where the number

of incidences is dominated by the term |P|2/3|L|2/3. The condition |L| =ω(|P|2−3α) is more

restrictive when α < 1/2. For example, when α= 1/3, this condition asks for the number

of lines to be asymptotically larger than the number of points.

We believe that Theorem 1.2 is of interest for several reasons:

•Generalizing the analysis of Erd˝os’s construction to the entire family is not trivial and

requires multiple new ideas.

•The constant of Elekes’s construction is improved from 1 to about 1.27.

•From an expository perspective, the proof from [15] is now fully explained and veriﬁed.

This clariﬁes some details, such as that an additional +o(1) should appear in the

bound.

Recently, Guth and Silier [10] discovered another inﬁnite family of constructions with

Θ(|P|2/3|L|2/3) incidences. It may be interesting to analyze the constants of this family.

In Section 2, we describe the constructions of Erd˝os and Elekes, and the inﬁnite family of

constructions. In Section 3, we derive a variety of results related to Euler’s totient function,

which are required in our analysis. In Section 4, we prove Theorem 1.2.

2 The constructions

The purpose of this section is to brieﬂy provide intuition for Erd˝os’s construction, Elekes’s

construction, and the inﬁnite family of constructions from [17]. For simplicity and intuition,

we only describe the case where |P| =|L| and with simpliﬁed sets of lines. These simpler

sets do lead to Θ(|P|2/3|L|2/3) incidences, but the constant hidden by the O(·)-notation is

not optimal. For example, all lines in this section have positive slopes. In Section 4, we

consider the general case and sets of lines that optimize the constant.

For positive integers sand t, we deﬁne (s, t) = GCD(s, t). In other words, (s, t) is the

largest positive integer that divides both sand t.

Figure 1: Left: Erd˝os’s construction. Right: Elekes’s construction.

Erd˝os’s construction. In Erd˝os’s construction, the point set is a √n×√nsection of

the integer lattice:

P={(i, j)∈N2: 1 ≤i, j ≤√n}.

The line slopes are rational numbers between 0 and 1, where the numerator and denominator

are not too large. In particular, the set of lines is

L=ny=a

b(x−c) + d:a, b ∈N,(a, b)=1,1≤a<b≤n1/6,

1≤c≤b, √n/2≤d≤3√n/4o.

After ﬁxing the slope of a line (that is, ﬁxing a, b), the parameters cand ddeﬁne a family

of b√n/4 lines with this slope. To see why |L| ≈ n, we require tools that are introduced in

Section 3. This conﬁguration is depicted in Figure 1.

Elekes’s construction. In Elekes’s construction, the point set is a tall and thin section

of the integer lattice:

P={(i, j)∈N2: 1 ≤i≤n1/3,1≤j≤n2/3}.

The line slopes are the integers between 1 and n1/3. For each slope, there are n2/3lines

with that slope. In particular, the set of lines is

L={y=ax +b:a, b ∈N,1≤a≤n1/3,1≤b≤n2/3}.

Unlike Erd˝os’s construction, in this case it is easy to see that |L| =n. This conﬁguration

is depicted in Figure 1.

The inﬁnite family of constructions. In Erd˝os’s construction, the point set is a

√n×√nsection of the integer lattice. In Elekes’s construction, the point set is an n1/3×n2/3

section of the integer lattice. These are the two extreme cases of the following family. We

ﬁx 1/3< α < 1/2 and consider the point set

P={(i, j)∈N2: 1 ≤i≤nα,1≤j≤n1−α}.

In Erd˝os’s construction, the line slopes are rational numbers between 0 and 1. In Elekes’s

construction, the line slopes are integers between 1 and n1/3. We now mix these two cases,

deﬁning

L=y=a+b

c(x−i) + d:a, b, c, d, i ∈N,0≤a<n1−2α/4,

1≤b<c≤nα−1/3,(b, c) = 1,0≤i < c, n1−α/2≤d < 3n1−α/4.

As αapproaches 1/2, this set of lines approaches the set from Erd˝os’s construction. As α

approaches 1/3, this set of lines approaches the set from Elekes’s construction. Thus, we

can indeed consider the constructions of Erd˝os and Elekes as the endpoints of the inﬁnite

family of constructions.

3 Preliminaries: Euler’s totient function

For an integer j > 0, we recall that Euler’s totient function of jis

φ(j) = |{i∈ {1,2, . . . , j −1}: (i, j) = 1}|.

Our analysis in Section 4 heavily relies on properties of this totient function and of relatively

prime integers. In this section, we discuss these properties. Throughout the paper, all

logarithms are of base e.

Lemma 3.1.

(a)

j=1

φ(j) = 3n2

π2+O(nlog n).

(b)

j=1

j·φ(j) = 2n3

π2+O(n2log n).

(c)

j=1

j2·φ(j) = 3n4

2π2+O(n3log n).

(d)

j=1

φ(j)

j=6n

π2+O(√n).

Proof. (a) This is a classic formula. For example, see [11, Theorem 330].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Theconstantofpoint{lineincidenceconstructionsMartinBalko*AdamSheerRuiwenTangAbstractWestudyalowerboundfortheconstantoftheSzemeredi{Trottertheorem.Inparticular,weshowthatarecentinnitefamilyofpoint-linecongurationssatisesI(P;L)(c+o(1))jPj2=3jLj2=3,withc1:27.Ourtechniqueisbasedonstudyingavarie...

展开>> 收起<<

The constant of pointline incidence constructions Martin BalkoAdam SheerRuiwen Tang Abstract.pdf

共19页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

The constant of pointline incidence constructions Martin BalkoAdam SheerRuiwen Tang Abstract

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: