Unsolved problem in mathematics :
For how many points is it always possible to projectively transform the points into convex position?
The McMullen problem is an open problem in discrete geometry named after Peter McMullen .
Statement [ edit ]
In 1972, David G. Larman wrote about the following problem:[1]
Determine the largest number
ν
(
d
)
{\displaystyle \nu (d)}
such that for any given
ν
(
d
)
{\displaystyle \nu (d)}
points in
general position in the
d
{\displaystyle d}
-dimensional affine space
R
d
{\displaystyle \mathbb {R} ^{d}}
there is a
projective transformation mapping these points into
convex position (so they form the vertices of a
convex polytope ).
Larman credited the problem to a private communication by Peter McMullen.
Equivalent formulations [ edit ]
Gale transform [ edit ]
Using the Gale transform , this problem can be reformulated as:
Determine the smallest number
μ
(
d
)
{\displaystyle \mu (d)}
such that for every set of
μ
(
d
)
{\displaystyle \mu (d)}
points
X
=
{
x
1
,
x
2
,
…
,
x
μ
(
d
)
}
{\displaystyle X=\{x_{1},x_{2},\dots ,x_{\mu (d)}\}}
in linearly general position on the sphere
S
d
−
1
{\displaystyle S^{d-1}}
it is possible to choose a set
Y
=
{
ε
1
x
1
,
ε
2
x
2
,
…
,
ε
μ
(
d
)
x
μ
(
d
)
}
{\displaystyle Y=\{\varepsilon _{1}x_{1},\varepsilon _{2}x_{2},\dots ,\varepsilon _{\mu (d)}x_{\mu (d)}\}}
where
ε
i
=
±
1
{\displaystyle \varepsilon _{i}=\pm 1}
for
i
=
1
,
2
,
…
,
μ
(
d
)
{\displaystyle i=1,2,\dots ,\mu (d)}
, such that every open hemisphere of
S
d
−
1
{\displaystyle S^{d-1}}
contains at least two members of
Y
{\displaystyle Y}
.
The numbers
ν
{\displaystyle \nu }
of the original formulation of the McMullen problem and
μ
{\displaystyle \mu }
of the Gale transform formulation are connected by the relationships
μ
(
k
)
=
min
{
w
∣
w
≤
ν
(
w
−
k
−
1
)
}
ν
(
d
)
=
max
{
w
∣
w
≥
μ
(
w
−
d
−
1
)
}
{\displaystyle {\begin{aligned}\mu (k)&=\min\{w\mid w\leq \nu (w-k-1)\}\\\nu (d)&=\max\{w\mid w\geq \mu (w-d-1)\}\end{aligned}}}
Partition into nearly-disjoint hulls [ edit ]
Also, by simple geometric observation, it can be reformulated as:
Determine the smallest number
λ
(
d
)
{\displaystyle \lambda (d)}
such that for every set
X
{\displaystyle X}
of
λ
(
d
)
{\displaystyle \lambda (d)}
points in
R
d
{\displaystyle \mathbb {R} ^{d}}
there exists a
partition of
X
{\displaystyle X}
into two sets
A
{\displaystyle A}
and
B
{\displaystyle B}
with
conv
(
A
∖
{
x
}
)
∩
conv
(
B
∖
{
x
}
)
≠
∅
,
∀
x
∈
X
.
{\displaystyle \operatorname {conv} (A\backslash \{x\})\cap \operatorname {conv} (B\backslash \{x\})\not =\varnothing ,\forall x\in X.\,}
The relation between
μ
{\displaystyle \mu }
and
λ
{\displaystyle \lambda }
is
μ
(
d
+
1
)
=
λ
(
d
)
,
d
≥
1
{\displaystyle \mu (d+1)=\lambda (d),\qquad d\geq 1\,}
Projective duality [ edit ]
An arrangement of lines dual to the regular pentagon. Every five-line projective arrangement, like this one, has a cell touched by all five lines. However, adding the line at infinity produces a six-line arrangement with six pentagon faces and ten triangle faces; no face is touched by all of the lines. Therefore, the solution to the McMullen problem for d = 2 is ν = 5.
The equivalent projective dual statement to the McMullen problem is to determine the largest number
ν
(
d
)
{\displaystyle \nu (d)}
such that every set of
ν
(
d
)
{\displaystyle \nu (d)}
hyperplanes in general position in d -dimensional real projective space form an arrangement of hyperplanes in which one of the cells is bounded by all of the hyperplanes.
Results [ edit ]
This problem is still open. However, the bounds of
ν
(
d
)
{\displaystyle \nu (d)}
are in the following results:
David Larman proved in 1972 that[1]
2
d
+
1
≤
ν
(
d
)
≤
(
d
+
1
)
2
.
{\displaystyle 2d+1\leq \nu (d)\leq (d+1)^{2}.}
Michel Las Vergnas proved in 1986 that[2]
ν
(
d
)
≤
(
d
+
1
)
(
d
+
2
)
2
.
{\displaystyle \nu (d)\leq {\frac {(d+1)(d+2)}{2}}.}
Jorge Luis Ramírez Alfonsín proved in 2001 that[3]
ν
(
d
)
≤
2
d
+
⌈
d
+
1
2
⌉
.
{\displaystyle \nu (d)\leq 2d+\left\lceil {\frac {d+1}{2}}\right\rceil .}
The conjecture of this problem is that
ν
(
d
)
=
2
d
+
1
{\displaystyle \nu (d)=2d+1}
. This has been proven for
d
=
2
,
3
,
4
{\displaystyle d=2,3,4}
.[1] [4]
References [ edit ]
^ a b c Larman, D. G. (1972), "On sets projectively equivalent to the vertices of a convex polytope", The Bulletin of the London Mathematical Society , 4 : 6–12, doi :10.1112/blms/4.1.6 , MR 0307040
^ Las Vergnas, Michel (1986), "Hamilton paths in tournaments and a problem of McMullen on projective transformations in
R
d
{\displaystyle \mathbb {R} ^{d}}
", The Bulletin of the London Mathematical Society , 18 (6): 571–572, doi :10.1112/blms/18.6.571 , MR 0859948
^ Ramírez Alfonsín, J. L. (2001), "Lawrence oriented matroids and a problem of McMullen on projective equivalences of polytopes", European Journal of Combinatorics , 22 (5): 723–731, doi :10.1006/eujc.2000.0492 , MR 1845496
^ Forge, David; Las Vergnas, Michel ; Schuchert, Peter (2001), "10 points in dimension 4 not projectively equivalent to the vertices of a convex polytope", Combinatorial geometries (Luminy, 1999), European Journal of Combinatorics , 22 (5): 705–708, doi :10.1006/eujc.2000.0490 , MR 1845494