OctoInformBeta

Power savings for planar halving lines and k-sets

Let P⊂ℝ2P\subset\mathbb R^2 be a set of nn points with no three collinear. For even nn, a halving pair consists of two points of PP whose line leaves exactly (n−2)/2(n-2)/2 other points in each open halfplane. Write h(P)h(P) for the number of unordered halving pairs. The halving-line problem asks for the largest possible value of h(P)h(P) at a given nn. Call PP generic if its first coordinates are distinct, its determined slopes are distinct, and no proper intersection of two segments joining its points lies on a third such segment. For a generic configuration and an integer 0≤k≤n0\le k\le n, the sweep at rank kk increases the slope ss from −∞-\infty to +∞+\infty and, away from the determined slopes, marks the kk points (x,y)∈P(x,y)\in P with smallest y−sxy-sx. A switch is an exchange of one marked point for one unmarked point. Write Sk(P)S_k(P) for the total number of switches in this sweep. A kk-set of PP is a kk-point subset strictly separable from the remaining points by a line.

Dey proved the upper bound h(P)=O(n4/3)h(P)=O(n^{4/3}). Tóth constructed configurations with nexp⁡(Ω(log⁡n))n\exp(\Omega(\sqrt{\log n})) halving pairs.

The preprint proves that there are absolute constants ε>0\varepsilon>0, C<∞C<\infty and n0n_0 such that h(P)≤Cn4/3−εh(P)\le Cn^{4/3-\varepsilon} for every even n≥n0n\ge n_0. The preprint also proves that there are absolute constants ε>0\varepsilon>0 and C<∞C<\infty such that Sk(P)≤Cn4/3−εS_k(P)\le Cn^{4/3-\varepsilon} for every generic nn-point configuration with n≥1n\ge1 and every integer 0≤k≤n0\le k\le n. For some absolute ε0>0\varepsilon_0>0, the preprint further derives the bound O(n(k+1)1/3−ε0)O(n(k+1)^{1/3-\varepsilon_0}) for the number of kk-sets when 1≤k≤n/21\le k\le n/2, a corollary not contained in the Lean library.

The Lean library is the reference for the results on these pages because Lean has checked every result of the Lean library. Each result is stated as the Lean library states it and is linked to the Lean declaration behind it. Where the preprint states a result differently, the Lean library’s statement is given with the preprint’s beside it. The preprint is a guide only, giving the results their order and names.

The Lean library: HalvingLines

HalvingLines is a Lean library: 24 items, in eight groups. Each has a page written by OctoInform, listed below.

§1. Introduction 3 items
  1. §1 (setting): halving pairs and generic rank sweeps Halving pairs and switches of projection ranks.
  2. Theorem 1.1 A power saving for halving pairs.
  3. Theorem 1.2 A power saving across all ranks.
§2. Sweeps, activity, and exchange graphs 6 items
  1. §2 (setting): states, activity, endpoint distance and batches Separating marked sets at increasing slopes.
  2. Theorem 2.1 A cubic bound for sweep activity.
  3. Lemma 2.2 Sweep activity forces endpoint separation.
  4. Lemma 2.3 Greedy checkpoints bound interval packings.
  5. Lemma 2.4 Exchange edge partitions control the number of crossings.
  6. Lemma 2.5 A vertex cover controls drawing crossings.
§3. Rank coordinates and limiting measures 5 items
  1. §3 (setting): rank coordinates and the extremal limiting setup Rank coordinates from convex graph families.
  2. §3 (setting): vertex, edge, crossing and conditional-time measures Rank labels admit joint measure limits.
  3. Lemma 3.1 Cubic bounds for limiting edge mass.
  4. Lemma 3.2 Atomless time laws from normalized sweep limits.
  5. Lemma 3.3 Crossing null sets control edge labels.
§4. Differentiable coordinates and transverse directions 5 items
  1. Lemma 4.1 Differentiability on rectangles and under linear changes.
  2. Lemma 4.2 Critical points have a null planar image.
  3. §4 (setting): the positive chart and allowed directions Differentiable rank limits in signed coordinates.
  4. Lemma 4.3 Transverse subwindows at almost every active label.
  5. Lemma 4.4 Local independence forces three distinct directions.
§5. Three transverse foliations determine the zoom 1 item
  1. Lemma 5.1 Normalized foliated maps admit signed identity limits.
§6. A spatial measure with dimension greater than seven quarters 1 item
  1. Proposition 6.1 Radial comparison yields separated spatial witnesses.
§7. Boundary activity and the packing contradiction 2 items
  1. Lemma 7.1 Boundary transfers bound activity outside three strips.
  2. Lemma 7.2 Boundary control for enhanced edge limits.
§8. From activity packing to a power saving 1 item
  1. Proposition 8.1 Activity packing gives uniform switch bounds.

No item matches.