Results on halving lines and k-sets: the theorems, Dey's bound, the packing estimate and the tools of its proof, with their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Power saving for halving lines (OpenAI) — Theorem A. There are absolute constants eps > 0 and C such that every set of n points in the plane, n even, no three on a line, has at most C n^(4/3 - eps) halving pairs. Proved in the twelfth lesson.
• Uniform bound for rank sweeps (OpenAI) — Theorem B. S_k(P) <= C N^(4/3 - eps) for every generic configuration P of N points and every rank k.
• k-sets (OpenAI) — Corollary C. A set of n points in the plane, no three on a line, has at most C_0 n (k+1)^(1/3 - eps0) k-sets for 1 <= k <= n/2. Proved in the last lesson.
• Halving pairs are middle switches — Lemma 2.2. For N = 2m, a pair of a generic configuration is halving exactly when its step is a switch of the rank-m sweep, so h(P) = S_m(P).
• Crossing inequality with designated endpoints — Lemma 5.1. A straight-line drawing with e edges on v points, every edge having an endpoint in a set of m vertices, satisfies e^3 <= 2304 m v cr + 13824 v^3.
• Classical packing bound — Theorem 6.1. In a rank sweep of N points, every family of step-disjoint intervals of activity at least b has at most C_1 (N/b)^(4/3) members.
• Dey's bound — Corollary 6.2. S_k(P) <= C_1 N^(4/3) for every generic configuration of N points and every rank k.
• Uniform activity packing (OpenAI) — Theorem 1.1. For every xi > 0 there is Q such that, when N/b >= Q, every family of step-disjoint intervals of activity at least b has at most xi (N/b)^(4/3) members. Proved in the twelfth lesson.
• Packing gives a power (OpenAI) — Proposition 3.1. If the packing estimate holds for every xi > 0, then S_k(P) <= C N^(4/3 - eps) with absolute constants eps > 0 and C.
• Weak compactness — Theorem 3.2. Every sequence of finite Borel measures with bounded total mass on a compact metric space has a weakly convergent subsequence; one subsequence serves countably many sequences.
• Blaschke selection — Theorem 4.1. Every sequence of nonempty closed subsets of a compact metric space has a subsequence converging in Hausdorff distance to a nonempty closed set.
• Conditional measures — Proposition 5.1. A finite measure nu on Z x [0,1], Z compact metric, has probability measures h_z on [0,1], Borel in z, with nu(F x J) equal to the integral of h_z(J) over F with respect to the image of nu on Z.
• Rank charts — Proposition 3.2. For nonempty windows A preceding B, the map (r_A, r_B) is a homeomorphism of the plane onto the open unit square.
• Crossing grid — Proposition 4.1. Crossings between edges of two disjoint windows, placed at their rank coordinates with mass M^(-2), integrate a continuous f >= 0 to at most the grid average of f plus its modulus of continuity at 3/M.
• Edge mass and vertex mass — Lemma 2.1. lambda_J(F)^3 <= C s_J^3 mu_J(F) for every window J and Borel set F; in particular edge mass is absolutely continuous with respect to vertex mass.
• No atoms in conditional time — Lemma 3.1. For lambda-almost every label z, the conditional time measure h_z has no atoms.
• Monotone functions of two variables (Saks; Chabrillac and Crouzeix) — Theorem 2.2. A bounded Borel function on an open rectangle of the plane that is monotone in each variable is differentiable almost everywhere.
• Critical images — Lemma 3.1. For any map F of an open planar set into the plane, the image of the points where F is differentiable with derivative of rank below 2 is a null set.
• Opposite sides — Lemma 1.1. In a square, a path from the left side to the right side meets every path from the bottom to the top; the same holds in any parallelogram.
• Three foliations (OpenAI) — Theorem 2.1. Homeomorphisms monotone along three families of parallel lines, whose limits keep the three directions, with F_j(0) = 0 and |F_j(v_1)| = 1, converge along a subsequence to plus or minus the identity, together with their inverses.
• Radial comparison (OpenAI) — Proposition 4.1. At each point of the good set there is C_p such that, for fixed small h and late configurations, the smallest displacement on the circle of radius h/T is at least the largest on the circle of radius h divided by C_p T, and symmetrically.
• Spatial limit (OpenAI) — Proposition 1.1. A positive part of the labels has a single limit position, and the limiting vertex measure there gives every disk of radius r < 1 mass at most C r^(32/17) and every strip of width r mass at most C r^(15/17).
• Three strips — Lemma 1.1. For cuts of a finite set whose normals turn by at most theta, the participating points in a region B inside the disk of radius D lie in three strips of width 6 D theta, apart from at most twice the number of transfers with exactly one endpoint in B.
• Moment bound (Clarkson and Shor) — Lemma 2.2. For a random sample of the lines with probability p, the expected sum of |K(Delta)|^gamma over the cells below the lower envelope is at most C_gamma (n p + 1) p^(-gamma).
• Levels with few lines below — Proposition 3.1. Every arrangement of n lines in general position has at most C_2 n (k+2)^(beta - 1) vertices with exactly k lines below, beta = 4/3 - eps.

Reading order

Read the first lesson first: it sets up rank sweeps and states Theorems A and B and Corollary C. The second and third lessons reduce the theorems to a packing estimate, which the fifth to twelfth lessons prove by contradiction. The fourth and seventh lessons are self-contained tools from measure theory and real analysis. The last lesson needs only the first lesson and Theorem B.