More pointsets with many rich lines

Basic Information

• Paper ID: 2510.09769
• Title: More pointsets with many rich lines
• Author: Gabriel Currier
• Classification: math.CO (Combinatorics)
• Publication Date: October 10, 2025
• Paper Link: https://arxiv.org/abs/2510.09769

Abstract

This paper presents novel sharp constructions for the Szemerédi-Trotter theorem. These constructions generalize previous work by Erdős, Elekes, Sheffer and Silier, Guth and Silier, and the author. Previously, arguments proving the optimality of these constructions required elementary number-theoretic knowledge and were quite technical, which limited the scope of applicability. This paper replaces these number-theoretic arguments with purely incidence-geometric reasoning, thereby achieving simpler proofs and more general results.

Research Background and Motivation

Core Problem

This research addresses the problem of sharp constructions for the Szemerédi-Trotter theorem, which concerns upper bounds on the number of incidences between point sets and line sets in the plane.

Problem Significance

1. Theoretical Importance: The Szemerédi-Trotter theorem is a fundamental result in discrete geometry with broad applications in number theory, combinatorial geometry, and theoretical computer science
2. Inverse Problem Research: Understanding what types of point-line configurations yield near-optimal incidence counts helps illuminate the essence of the theorem
3. Applied Value: Sharp Szemerédi-Trotter constructions are directly applicable to generating optimal constructions for other incidence geometry problems

Limitations of Existing Methods

1. Technical Complexity: Traditional proofs require elementary number theory knowledge with highly technical analysis
2. Limited Scope: The complexity of number-theoretic arguments grows with the degree of the number field, restricting generalization
3. Lack of Uniformity: Absence of a unified framework for handling constructions from arbitrary number fields

Research Motivation

This paper aims to replace number-theoretic arguments with purely incidence-geometric methods to:

• Simplify proofs
• Extend to number fields of arbitrary degree
• Provide a more unified theoretical framework

Core Contributions

1. Unified Construction Framework: Proposes a unified construction method based on the concept of "nice basis," encompassing all known classical constructions
2. Simplified Proof Techniques: Replaces complex number-theoretic analysis with purely incidence-geometric reasoning
3. Generalization to Arbitrary Number Fields: Extends the construction method to arbitrary algebraic number fields without degree restrictions
4. New Theoretical Tools: Introduces technical tools for handling generalized arithmetic progressions, laying groundwork for future research

Methodology Details

Problem Definition

Given positive integers n and r (where r ≤ n^{1/2}), construct a point set P containing n points such that the number of r-rich lines determined by P (lines containing at least r points) achieves Ω(n²/r³), thereby proving the sharpness of the Szemerédi-Trotter theorem.

Core Concepts

Nice Basis Definition

Let Λ = {λ₁, ..., λₐ} ⊂ ℂ be linearly independent over the integer ring Z. Λ is called a nice basis if for all 1 ≤ i, j ≤ d, the product λᵢλⱼ is a Z-linear combination of elements in Λ.

Generalized Arithmetic Progression Construction

For positive integer m, define:

Aₘ(Λ) := {a₁λ₁ + ··· + aₐλₐ : aᵢ ∈ Z, |aᵢ| ≤ m^{1/d}/3}

Main Theorem

Theorem 1.3: Let Λ be a nice basis, 0 < α ≤ 1/2, and P = A_{n^α}(Λ) × A_{n^{1-α}}(Λ). Then there exists C' > 0 (depending on d and Λ) such that for all r ≤ C'n^α, P determines Ω_Λ(n²/r³) r-rich lines.

Construction Method

Basic Strategy

1. Subset Selection: Take a small subset P' = A_{C₁n^α/r}(Λ) × A_{C₁n^{1-α}/r}(Λ) of P
2. Translation Construction: Consider multiple translated versions of P'
3. Line Collection: Collect all lines determined by translated versions
4. Rich Line Verification: Prove that these lines are all r-rich in the original point set P

Technical Details

The construction process consists of four key steps:

Step One - Local Line Counting: Each translation P' + (x,y), due to its Cartesian product structure, must determine Ω(n²/r⁴) lines by Beck's theorem.

Step Two - Rich Line Property: Utilizing the multiplicative closure property of nice basis, prove through algebraic manipulation that each collected line contains at least r points in P.

Step Three - Incidence Count Estimation: By computing contributions from all translated versions, obtain a total incidence count of Ω(n²/r²).

Step Four - Line Count Lower Bound: Apply the upper bound of the Szemerédi-Trotter theorem to derive a lower bound of Ω(n²/r³) on the line count.

Technical Innovations

1. Geometric Reasoning: Completely avoids congruence calculations and prime factorization from number theory
2. Unified Treatment: Handles different types of algebraic structures uniformly through the nice basis concept
3. Modular Design: Decomposes complex proofs into independent geometric lemmas
4. Extensibility: Method naturally extends to arbitrary-dimensional algebraic number fields

Theoretical Analysis

Main Lemmas

Lemma 2.3 (Algebraic Closure)

Let Λ be a d-dimensional nice basis, and m, m' be positive reals. If a ∈ Aₘ(Λ) and a' ∈ Aₘ'(Λ), then:

• a ± a' ∈ A_{2d·max{m,m'}}(Λ)
• aa' ∈ A_{(d²C_Λ)^d·mm'}(Λ)

This lemma guarantees closure of algebraic operations within generalized arithmetic progressions, forming the algebraic foundation of the entire construction.

Proof Architecture

The proof consists of four core assertions:

1. Assertion 1: Each translation determines sufficiently many local lines
2. Assertion 2: Each collected line is r-rich
3. Assertion 3: Total incidence count achieves the expected lower bound
4. Assertion 4: Apply the Szemerédi-Trotter theorem to obtain the line count lower bound

Results and Applications

Main Results

Theorem 1.3 encompasses all known classical constructions:

• Erdős Construction: α = 1/2, Λ = {1}
• Elekes Construction: arbitrary α, Λ = {1}
• Guth-Silier Construction: α = 1/2, Λ = {1, √k}
• Author's Previous Construction: arbitrary α, Λ as basis of arbitrary algebraic number field

Application Extensions

1. Szemerédi-Trotter Theorem: Directly establishes sharpness of incidence count upper bounds
2. Other Incidence Geometry Problems: Provides optimal constructions for related problems
3. Theoretical Computer Science: Potential applications in algorithm design

Related Work

Historical Development

1. Szemerédi-Trotter (1983): Establishes fundamental incidence count upper bounds
2. Erdős Construction: Earliest sharp construction based on integer lattice points
3. Elekes Construction: Simplified construction method
4. Sheffer-Silier: Interpolation-based construction
5. Guth-Silier: Extension to quadratic number fields
6. Author's Previous Work: Generalization to arbitrary algebraic number fields

Contributions of This Paper

Compared to existing work, the main advantages are:

• Simplification of proof methods
• Expansion of applicable scope
• Unification of theoretical framework

Conclusions and Discussion

Main Conclusions

1. Successfully constructs a new family of sharp constructions for the Szemerédi-Trotter theorem
2. Demonstrates the effectiveness of purely geometric methods for such problems
3. Provides new tools for inverse problem research in incidence geometry

Theoretical Significance

• Methodological Innovation: Demonstrates advantages of geometric methods over number-theoretic approaches
• Unification: Provides a unified framework for handling different algebraic structures
• Extensibility: Lays groundwork for subsequent research

Future Directions

1. Explore more general algebraic structures
2. Investigate generalizations to higher dimensions
3. Seek applications to other incidence geometry problems

In-Depth Evaluation

Strengths

1. Technical Innovation: Successfully replaces complex number-theoretic analysis with geometric methods
2. Theoretical Unification: Incorporates scattered construction methods into a unified framework
3. Proof Clarity: Modular proof structure facilitates understanding and verification
4. Broad Applicability: Method applies to arbitrary algebraic number fields

Limitations

1. Constant Dependence: Constants in results depend on algebraic structure and may be large
2. Construction Complexity: Actual construction still requires knowledge of algebraic number fields
3. Application Scope: Primarily limited to theoretical research with limited practical applications

Impact

1. Theoretical Contribution: Provides new research tools for incidence geometry
2. Methodological Value: Demonstrates the power of interdisciplinary methods
3. Future Research: May inspire more geometrized proof techniques

Applicable Scenarios

• Discrete geometry theoretical research
• Optimal constructions for incidence geometry problems
• Interdisciplinary research between number theory and geometry
• Combinatorial optimization in theoretical computer science

References

The paper cites 24 relevant references, covering the major developments in the Szemerédi-Trotter theorem and its applications, providing readers with complete background knowledge and directions for further research.

Overall Assessment: This is a high-quality theoretical paper that addresses an important combinatorial geometry problem through innovative geometric methods. While the results are primarily of theoretical value, its methodological contributions and unified framework are of significant importance to the development of this field.