The Generalized Makeev Problem Revisited

Andrés Mejı́a, Steven Simon, Jialin Zhang

TL;DR

This paper provides significantly improved upper bounds for the Generalized Makeev Problem, a central question in geometric combinatorics. The authors show that by relaxing the requirement from "all $k$ hyperplanes must equipartition a mass" to "any subset of $\ell$ hyperplanes must equipartition a mass," one can achieve equipartition in much lower dimensions—often exponentially smaller than previously known bounds.

What Problem Does This Paper Address?

At its heart, this is a "fair division" problem in high-dimensional geometry. The classic Ham Sandwich Theorem tells us that any $d$ "masses" (like blobs of clay or probability distributions) in $d$-dimensional space can be simultaneously bisected by a single hyperplane.

The Grünbaum–Hadwiger–Ramos Problem asks for the minimum dimension $d$ needed so that $m$ masses can be cut into $2^k$ equal pieces by $k$ hyperplanes. This is notoriously difficult and remains open for most values of $m$ and $k$.

The Generalized Makeev Problem (proposed in 2012) asks a slightly different question: Given $m$ masses, what is the minimum dimension $d$ such that there exist $k$ hyperplanes where any subset of $\ell$ hyperplanes equipartitions each mass? This paper tackles this generalized version, specifically focusing on cases where $\ell < k$, and provides new, tighter bounds on the required dimension.

Methods

The authors employ the configuration-space/test-map paradigm, a standard but powerful tool in topological combinatorics.

  1. Configuration Space: They represent the set of all possible $k$-hyperplane arrangements as a product of spheres $(S^d)^k$.
  2. Fourier Perspective: Instead of looking at the geometric regions directly, they use a "Fourier expansion" of the mass distributions. This allows them to characterize the "equipartition" condition as the vanishing of specific Fourier coefficients.
  3. Equivariant Topology: The problem is transformed into finding a zero of a continuous map that respects certain symmetries (specifically the action of the group $\mathbb{Z}_2^k$).
  4. Polynomial Criteria: They use ideal-valued cohomological index theory to determine if such a zero must exist. By analyzing the properties of specific polynomials in the cohomology ring of the group, they derive the existence of the required hyperplanes in specific dimensions.

Datasets

As a theoretical mathematics paper, no empirical datasets were used. The "evaluation" consists of rigorous mathematical proofs and comparisons against previously established theoretical lower and upper bounds.

Key Insights and Ideas

  • The Power of $\ell < k$: The most striking insight is that requiring only a subset $\ell$ of the $k$ hyperplanes to do the work drastically reduces the required dimension. For example, while the dimension needed for $k=4$ is quite high, the dimension needed for $\ell=3, k=4$ is much lower and nearly matches the theoretical lower bound.
  • Exponential Improvement: When the number of masses $m+1$ is a power of two, the new bounds are exponentially smaller than the best-known bounds for the standard case where $\ell=k$.
  • Orthogonality for "Free": The authors show that in many cases, you can impose the additional constraint that the $k$ hyperplanes must be pairwise orthogonal without needing to increase the dimension of the space.
  • Transversal Extensions: They extend the results from "masses" to "families of convex sets." Using a Radon-type intersection theorem, they prove that if families of sets aren't "too disjoint," they can be "pierced" (intersected) by the union of these hyperplanes.

Key Results

  • New Upper Bounds: For $m$ masses, the authors establish that the minimum dimension $\Delta(m; \ell/k)$ satisfies:
  • $\Delta(2^{q+1}-t; 2/k) \leq 2^q(k+1) - t$
    • $\Delta(2^{q+1}-t; 3/4) \leq 7 \cdot 2^q - 2t$
  • Near Optimality: These bounds are shown to be nearly tight (within 1 or 2 dimensions of the lower bound) when $m+1$ is a power of two.
  • Orthogonal Version: Similar bounds were proven for $\Delta^\perp(m; \ell/k)$, where hyperplanes must be pairwise orthogonal.
  • Concrete Example: For three masses in $\mathbb{R}^6$, there exist three hyperplanes such that any two of them equipartition two of the masses, and two of them equipartition the third.

Limitations and Future Work

  • Specific $\ell, k$ Values: While the $\ell=2$ case is solved for arbitrary $k$, the $\ell=3$ case is only fully addressed for $k=4$. Generalizing these specific polynomial calculations for higher $\ell$ and $k$ remains a challenge.
  • The Gap to Lower Bounds: Although the bounds are "nearly tight," there is still a small gap (usually a constant like 1 or 2) between the proven upper bounds and the conjectured lower bounds.
  • Topological Obstructions: The methods rely on the non-vanishing of certain cohomology classes. If these classes vanish, the topological method "fails" to provide a bound, even if the geometric result might still be true. Finding tighter combinatorial or geometric arguments to close these small gaps is a likely next step.

Summary updated

Abstract

Based on a result of Makeev, in 2012 Blagojević and Karasev proposed the following problem: given any positive integers $m$ and $1\leq \ell\leq k$, find the minimum dimension $d=Δ(m;\ell/k)$ such that for any $m$ mass distributions on $\mathbb{R}^d$, there exist $k$ hyperplanes, any $\ell$ of which equipartition each mass. The $\ell=k$ case is a central question in geometric and topological combinatorics which remains open except for few values of $m$ and $k$. For $\ell&lt; k$ and arbitrary $m$, we establish new upper bounds on $Δ(m;\ell/k)$ when (1) $\ell=2$ and $k$ is arbitrary and (2) $\ell=3$ and $k=4$. When $\ell=k-1$ and $m+1$ is a power of two these bounds are nearly optimal and are exponentially smaller than the current best upper bounds when $\ell=k$. Similar remarks apply to our upper bounds when the hyperplanes are prescribed to be pairwise orthogonal. Lastly, we provide transversal extensions of our results along the lines recently established by Frick et al.: given $m$ families of compact convex sets in $\mathbb{R}^d$ such that no $2^\ell$ members of any family are pairwise disjoint, we show that every member of each family is pierced by the union of any $\ell$ of some collection of $k$ hyperplanes.
BibTeX
@inproceedings{meja2024generalized,
  author = {Andrés Mejı́a and Steven Simon and Jialin Zhang},
  title = {{The Generalized Makeev Problem Revisited}},
  booktitle = {Beiträge},
  year = {2024},
  doi = {10.1007/s13366-024-00737-y},
}

Loading related content...

Figure