/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
cross p q x is the cross product $(q - p) \times (x - p)$. For $p \neq q$ it is positive if x
lies strictly to the left of the line from p to q, negative if x lies strictly to the right,
and zero if x lies on the line pq.
imbalance X p q is the absolute difference between the numbers of points of X on the two sides
of the line through
p and q. The points of X on the line itself are on neither side.
Let $X \subset \mathbb{R}^2$ be a set of $n$ points. Does there exist a line $\ell$ through at
least two points of $X$ such that the numbers of points on either side of $\ell$ differ by at
most $100$?
This is a form of the Kupitz-Perles conjecture [Gr24]. We take $n \geq 2$, since a line through
two points of $X$ needs two points. If all points of $X$ are collinear, the line through them has
no points on either side.
Is there a constant $C$ such that every finite set $X \subset \mathbb{R}^2$ with at least two
points has a line through two points of $X$ whose sides differ by at most $C$? This is the
question of Kupitz in the form of [CL25, Section 1], where the constant is not specified.
Pinchasi [Pi03] proved that the answer to green_75 is yes if $100$ is replaced by
$C \log \log n$ for an absolute constant $C$, where $n = |X|$ [Gr24]. This is the best known bound.
[CL25, Theorem 1.1] states Pinchasi's theorem for generalised configurations (points with
pseudolines); sets of points with lines are a special case. The hypothesis $n \geq 3$ ensures
that $\log \log n > 0$.
Kupitz conjectured that one can take the difference to be at most $1$ [CL25, Section 1]. Alon
showed that this is false: there are finite point sets for which, for every line through two of
its points, the numbers of points on the two sides differ by at least $2$ [CL25, Section 1].
[Gr24] phrases this as: the answer to green_75 is no if $100$ is replaced by $2$. Since the
sets in [CL25] have differences of at least $2$, they show that $100$ cannot be replaced by $1$.
We state the form given in [CL25].