we-solve (beta)

Math-1646 · mathematics · Geometry

Halving lines and k-sets

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $S\subset\mathbb R^2$ consist of $n$ distinct points, with no three collinear. A $k$-set is a subset $A\subset S$ of size $k$ for which some line disjoint from $S$ strictly separates $A$ from $S\setminus A$. Count distinct subsets, not the infinitely many separating lines. Define \[ K_2(n,k)=\max_{|S|=n}\#\{A\subset S:A\text{ is a }k\text{-set}\}. \] Find sharp bounds as functions of both $n$ and $1\le k\le n-1$.

For even $n$, a halving line is a line through two points of $S$ with exactly $(n-2)/2$ of the remaining points in each open half-plane. Determine the largest number $H_2(n)$ of these lines. The halving-line count is a closely related extremal question; its objects are not the separating lines in the preceding definition.

In $\mathbb R^d$, take sets in affine general position, define $k$-sets by strict separation with a hyperplane, and determine the analogous $K_d(n,k)$. A halving hyperplane passes through $d$ points and has equally many remaining points on each side, so this equal-split version requires $n-d$ even. Count each resulting affine hyperplane once.

Short English statement

Determine how many subsets of a point configuration can be cut off by a line or hyperplane, with particular emphasis on equal-size splits.

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1646-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1646

Planar halving-line saving: A fixed power improvement over the n^(4/3) planar halving-line upper bound is proved, with generic all-rank upper bounds as well; matching lower bounds, exact order and the bundled higher-dimensional cases are not determined.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Halving lines and k-sets

OpenAI's claim

Planar halving-line saving: The claimed number of halving pairs in a sufficiently large even planar configuration with no three collinear is $O(n^{4/3-\varepsilon})$ for one absolute $\varepsilon>0$. The constants are existential.

Mathematical statement of the claimed result

Mathematical claim 1.
For an even-sized planar point set $P$, with no three points collinear, let $h(P)$ count pairs whose line leaves $(|P|-2)/2$ points in each open halfplane. The claimed constants $\epsilon>0,C<\infty,n_0$ are absolute and satisfy \[h(P)\le C|P|^{4/3-\epsilon}\quad(|P|\ge n_0).\] The all-ranks theorem also bounds by $CN^{4/3-\epsilon}$ the number $S_k(P)$ of switches of the $k$ points minimizing $y-sx$ as $s$ ranges from $-\infty$ to $+\infty$, for every rank $0\le k\le N$ of a generic $N$-point configuration. This power improvement does not give matching sharp bounds at every rank. Here the all-ranks genericity conditions prohibit three collinear points, repeated first coordinates, equal slopes from different point pairs, and any proper intersection of two point-pair segments lying on a third such segment. Its parameters range over $N\ge1$ and $0\le k\le N$.

Outline of the argument

Planar halving-line saving: Rotating rank sweeps track membership changes in the lower point set, including points that later return. Complete bipartite exchange graphs and convex-chain decompositions control crossings of intervals with high activity. Near saturation yields limiting rank-coordinate measures with an impossible concentration pattern; a little-oh packing improvement at one fixed scale then contracts the recurrence.

Formal verification

Family 183 describes Lean coverage for the existential halving-pair power improvement and the stated generic sweep-level estimate.

Planar halving-line saving: The manuscript links HalvingLines.lean.

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →