Hyperplane Mass Partitions

via Relative Equivariant Obstruction Theory

Pavle V. M. Blagojević, Florian Frick, Albert Haase, Günter M. Ziegler^{1}

Received: October 6, 2015 Revised: April 28, 2016

Communicated by Christian Bär

Abstract. The Grünbaum–Hadwiger–Ramos hyperplane mass partition problem was introduced by Grünbaum (1960) in a special case and in general form by Ramos (1996). It asks for the “admissible” triples (d, j, k) such that for any j masses in ℝ^{d} there are k hyperplanes that cut each of the masses into 2^{k} equal parts. Ramos’ conjecture is that the Avis–Ramos necessary lower bound condition dk ≥ j(2^{k} − 1) is also sufficient. We develop a “join scheme” for this problem, such that non-existence of an 𝔖_{k}^{±}-equivariant map between spheres (S^{d})^{∗k} → S(W_{k} ⊕ U_{k}^{⊕j}) that extends a test map on the subspace of (S^{d})^{∗k} where the hyperoctahedral group 𝔖_{k}^{±} acts non-freely, implies that (d, j, k) is admissible. For the sphere (S^{d})^{∗k} we obtain a very efficient regular cell decomposition, whose cells get a combinatorial interpretation with respect to measures on a modified moment curve. This allows us to apply relative equivariant obstruction theory successfully, even in the case when the difference of dimensions of the spheres (S^{d})^{∗k} and S(W_{k}⊕U_{k}^{⊕j}) is greater than one. The evaluation of obstruction classes leads to counting problems for concatenated Gray codes. Thus we give a rigorous, unified treatment of the previously announced cases of the Grünbaum–Hadwiger–Ramos problem, as well as a number of new cases for Ramos’ conjecture.

2010 Mathematics Subject Classification: 55N25, 51N20, 52A35, 55R20 Keywords and Phrases: Hyperplane mass partition problem, equivariant topological combinatorics, equivariant obstruction theory 1 Introduction

1P.B. was supported by the DFG via the Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”, and by the grant ON 174008 of Serbian Ministry of Education and Science.

F.F. and A.H. were supported by DFG via the Berlin Mathematical School.

G.M.Z. received funding from the ERC project no. 247029-SDModels and by DFG via the Research Training Group “Methods for Discrete Structures” and the Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”

Documenta Mathematica 21 (2016) 735–771

1.1 The Grünbaum–Hadwiger–Ramos hyperplane mass partition problem

In 1960, Grünbaum [10, Sec. 4.(v)] asked whether for any convex body in ℝ^{k} there are k affine hyperplanes that divide it into 2^{k} parts of equal volume: This is now known to be true for k ≤ 3, due to Hadwiger [11] in 1966, and remains open and challenging for k = 4. (A weak partition result for k = 4 was given in 2009 by Dimitrijević-Blagojević [8].) For k > 4 it is false, as shown by Avis [1] in 1984 by considering a measure on a moment curve. In 1996, Ramos [15] proposed the following generalization of Grünbaum’s problem.

The Grünbaum–Hadwiger–Ramos problem. Determine the minimal dimension d = Δ(j, k) such that for every collection of j masses M on ℝ^{d} there exists an arrangement of k affine hyperplanes H in ℝ^{d} that equiparts M.

The Ham Sandwich theorem, conjectured by Steinhaus and proved by Banach, states that Δ(d, 1) = d. The Grünbaum–Hadwiger–Ramos hyperplane mass partition problem was studied by many authors. It has been an excellent testing ground for different equivariant topology methods; see to our recent survey in [3]. The first general result about the function Δ(j, k) was obtained by Ramos [15], by generalizing Avis’ observation: The lower bound

Δ(j, k) ≥ \frac{2^{k}−1}{k}j

follows from considering k measures with disjoint connected supports concentrated along a moment curve in ℝ^{d}. Ramos also conjectured that this lower bound is tight.

The Ramos conjecture. Δ(j, k) = ⌈\frac{2^{k}−1}{k}j⌉ for every j ≥ 1 and k ≥ 1.

All available evidence up to now supports this, though it has been established rigorously only in special cases.

1.2 Product scheme and join scheme

It seems natural to use Y_{d,k} := (S^{d})^{k} as a configuration space for any k oriented affine hyperplanes/halfspaces in ℝ^{d}, which leads to the following product scheme: If there is no equivariant map

(S^{d})^{k} ⟶_{𝔖_{k}^{±}} S(U_{k}^{⊕j})

from the configuration space to the unit sphere in the space U_{k}^{⊕j} of values on the orthants of ℝ^{k} that sum to 0, which is equivariant with respect to the hyperoctahedral (signed permutation) group 𝔖_{k}^{±}, then there is no counterexample for the given parameters, so Δ(j, k) ≤ d.

Hyperplane Mass Partitions via Obstruction Theory 737

However, our critical review [3] of the main papers on the Grünbaum– Hadwiger–Ramos problem since 1998 has shown that this scheme is very hard to handle: Except for the 2006 upper bounds by Mani-Levitska, Vrećica & Živaljević [13], derived from a Fadell–Husseini index calculation, it has produced very few valid results: The group action on (S^{d})^{k} is not free, the Fadell–Husseini index is rather large and thus yields weak results, and there is no efficient cell complex model at hand. In this paper, we provide a new approach, which proves to be remarkably clean and efficient. For this, we use a join scheme, as introduced by Blagojević and Ziegler [4], which takes the form

F : (S^{d})^{∗k} ⟶_{𝔖_{k}^{±}} S(W_{k} ⊕ U_{k}^{⊕j}).

Here the domain (S^{d})^{∗k} ⊆ ℝ^{(d+1)×k} is a sphere of dimension dk + k − 1, given by

X_{d,k} := {(λ_{1}x_{1}, …, λ_{k}x_{k}) : x_{1}, …, x_{k} ∈ S^{d}, λ_{1}, …, λ_{k} ≥ 0, λ_{1} +⋯+λ_{k} = 1},

where we write λ_{1}x_{1} +⋯+λ_{k}x_{k} as a short-hand for (λ_{1}x_{1}, …, λ_{k}x_{k}). The codomain is a sphere of dimension j(2^{k} − 1) + k − 2. Both domain and co-domain are equipped with canonical 𝔖_{k}^{±}-actions. We observe that the map restricted to the points with non-trivial stabilizer (the “non-free part”)

F′ : X_{d,k}^{>1} ⊂ (S^{d})^{∗k} ⟶_{𝔖_{k}^{±}} S(W_{k} ⊕ U_{k}^{⊕j})

is the same up to homotopy for all test maps. If for any parameters (j, k, d) an equivariant extension F of F′ does not exist, we get that Δ(j, k) ≤ d. To decide the existence of this map, or at least obtain necessary criteria, we employ relative equivariant obstruction theory, as explained by tom Dieck [7, Sect. II.3]. This turns out to work beautifully, and have a few remarkable aspects:

• The Fox–Neuwirth [9]/Björner–Ziegler [2] combinatorial stratification method yields a simple and efficient cone stratification for the space ℝ^{(d+1)×k}, which is equivariant with respect to the action of 𝔖_{k}^{±} on the columns, and which respects the arrangement of k^{2} subspaces of codimension d given by columns of a matrix (x_{1}, …, x_{d}) being equal, opposite, or zero.

• This yields a small equivariant regular CW complex model for the sphere (S^{d})^{∗k} ⊆ ℝ^{(d+1)×k}, for which the the non-free part, given by an arrangement of k^{2} subspheres of codimension d + 1, is an invariant subcomplex. The cells D_{I}^{S}(σ) in the complex are given by combinatorial data.

• To evaluate the obstruction cocycle, we use measures on a non-standard (binomial coefficient) moment curve. For the resulting test map, the relevant cells D_{I}^{S}(σ) can be interpreted as k-tuples of hyperplanes such that some of the hyperplanes have to pass through prescribed points of the moment curve, or equivalently, they have to bisect some extra masses.

1.3 Statement of the main results

The join scheme reduces the Grünbaum–Hadwiger–Ramos problem to a combinatorial counting problem that can be solved by hand or by means of a computer: A k-bit Gray code is a k × 2^{k} binary matrix of all column vectors of length k such that two consecutive vectors differ by only one bit. Such a k-bit code can be interpreted as a Hamiltonian path in the graph of the k-cube [0, 1]^{k}. The transition count of a row in a binary matrix A is the number of bit-changes, not counting a bit change from the last to the first entry. By transition counts of a matrix A we refer to the vector of the transition counts of the rows of the matrix A. Two binary matrices A and A′ are equivalent, if A can be obtained from A′ by a sequence of permutations of rows and/or inversion of bits in rows.

Definition 1.1. Let d ≥ 1, j ≥ 1, ℓ ≥ 0 and k ≥ 1 be integers such that dk = (2^{k} − 1)j + ℓ with 0 ≤ ℓ ≤ d − 1. A binary matrix A of size k × j2^{k} is an ℓ-equiparting matrix if

(a) A = (A_{1}, …, A_{j}) for Gray codes A_{1}, …, A_{j} with the property that the last column of A_{i} is equal to the first column of A_{i+1} for 1 ≤ i < j; and

(b) there is one row of the matrix A with the transition count d − ℓ, while all other rows have transition count d.

Example 1.2. If d = 5, j = 2, ℓ = 1 and k = 3, then a possible 1-equiparting matrix is

A = (A_{1}, A_{2}) = (\begin{matrix}0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{matrix}) .

In this example the first row of A has transition count 4 while the remaining two rows have transition count 5.

Theorem 1.3. Let d ≥ 1, j ≥ 1, ℓ ≥ 0 and k ≥ 2 be integers with the property that dk = (2^{k} − 1)j + ℓ and 0 ≤ ℓ ≤ d − 1. The number of non-equivalent ℓ-equiparting matrices is the number of arrangements of k affine hyperplanes H that equipart a given collection of j disjoint intervals on a moment curve γ in ℝ^{d}, up to renumbering and orientation change of hyperplanes in H, when it is forced that one of the hyperplanes passes through ℓ prescribed points on γ that lie to the left of the j disjoint intervals.

In some situations this yields a solution for the Grünbaum–Hadwiger–Ramos problem.

Theorem 1.4. Let j ≥ 1 and k ≥ 3 be integers, with d := ⌈\frac{2^{k}−1}{k}j⌉ and ℓ := ⌈\frac{2^{k}−1}{k}j⌉k − (2^{k} − 1)j = dk − (2^{k} − 1)j, which implies 0 ≤ ℓ < k ≤ d. If the number of non-equivalent ℓ-equiparting matrices of size k × j2^{k} is odd, then

Δ(j, k) = ⌈\frac{2^{k}−1}{k}j⌉.

Theorem 1.4 is also true for k = 1 (and thus d = j, ℓ = 0), where it yields the Ham Sandwich theorem: In this case an equiparting matrix A is a row vector of length 2d and transition count d. Thus, each A_{i} is either (0, 1) or (1, 0), where A_{i} uniquely determines A_{i+1}. Hence, up to inversion of bits A is unique and so Δ(d, 1) ≤ d, and consequently Δ(d, 1) = d. While the situation for k = 1 hyperplane is fully understood, we seem to be far from a complete solution for the case of k = 2 hyperplanes. However, we do obtain the following instances.

Theorem 1.5. Let t ≥ 1. Then:

(i) Δ(2^{t} − 1, 2) = 3 · 2^{t−1} − 1, (ii) Δ(2^{t}, 2) = 3 · 2^{t−1}, (iii) Δ(2^{t} + 1, 2) = 3 · 2^{t−1} + 2.

The statements (i) and (iii) were already known: Part (i) is the only case where the lower bound of Ramos and the upper bound of Mani-Levitska, Vrećica, and Živaljević [13, Thm. 39] coincide. Part (ii) is Hadwiger’s result [11] for t = 1; the general case was previously claimed by Mani-Levitska et al. [13, Prop. 25]. However, the proof of the result was incorrect and not recoverable, as explained in [3, Sec. 8.1]. Here we recover this result by a different method of proof. Similarly, statement (iii) was claimed by Živaljević [17, Thm. 2.1] with a flawed proof; for an explanation of the gap see [3, Sec. 8.2], where we also gave a proof of (iii) via degrees of equivariant maps [3, Sec. 5]. Here we will prove all three cases of Theorem 1.5 in a uniform way. In the case of k = 3 hyperplanes we prove using Theorem 1.4 the following instances of the Ramos conjecture.

Theorem 1.6.

(i) Δ(2, 3) = 5,

(ii) Δ(4, 3) = 10.

Statement (i) was previously claimed by Ramos [15, Sec. 6.1]. A gap in the method that Ramos developed and used to get this result was explained in [3, Sec. 7]. It is also claimed by Vrećica and Živaljević in the recent preprint [16] without a proof for the crucial [16, Prop. 3]. The reduction result of Hadwiger and Ramos Δ(j, k) ≤ Δ(2j, k − 1) applied to Theorem 1.6 implies the following consequences. For details on reduction results see for example [3, Sec. 3.3].

Corollary 1.7.

(i) 4 ≤ Δ(1, 4) ≤ 5,

(ii) 8 ≤ Δ(2, 4) ≤ 10.

Note that Δ(1, 4) is the open case for Grünbaum’s original conjecture.

Acknowledgement

We are grateful to the referee for very careful and helpful comments on this paper.

2 The join configuration space test map scheme and equivariant obstruction theory

In this section we develop the join configuration test map scheme that was introduced in [5, Sec. 2.1]. A sufficient condition for Δ(j, k) ≤ d will be phrased in terms of the non-existence of a particular equivariant map between representation spheres.

2.1 Arrangements of k hyperplanes

Let Ĥ = {x ∈ ℝ^{d} : ⟨x, v⟩ = a} be an affine hyperplane determined by a vector v ∈ ℝ^{d}\{0} and a constant a ∈ ℝ. The hyperplane Ĥ determines two (closed) halfspaces

Ĥ^{0} = {x ∈ ℝ^{d} : ⟨x, v⟩ ≥ a} and Ĥ^{1} = {x ∈ ℝ^{d} : ⟨x, v⟩ ≤ a}.

Let H = (Ĥ_{1}, …, Ĥ_{k}) be an arrangement of k affine hyperplanes in ℝ^{d}, and let α = (α_{1}, …, α_{k}) ∈ (ℤ/2)^{k}. The orthant determined by the arrangement H and α ∈ (ℤ/2)^{k} is the intersection

O_{α}^{H} = Ĥ_{1}^{α_{1}} ∩ ⋯ ∩ Ĥ_{k}^{α_{k}}.

Let M = (μ_{1}, …, μ_{j}) be a collection of finite Borel probability measures on ℝ^{d} such that the measure of each hyperplane is zero. Such measures will be called masses. The assumptions about the measures guarantee that μ_{i}(Ĥ_{s}^{0}) depends continuously on Ĥ_{s}^{0}. An arrangement of affine hyperplanes H = (Ĥ_{1}, …, Ĥ_{k}) equiparts the collection of masses M = (μ_{1}, …, μ_{j}) if for every element α ∈ (ℤ/2)^{k} and every ℓ ∈ {1, …, j}

μ_{ℓ}(O_{α}^{H}) = \frac{1}{2^{k}} .

2.2 The configuration spaces

The space of all oriented affine hyperplanes (or closed affine halfspaces) in ℝ^{d} can be parametrized by the sphere S^{d}, where the north pole e_{d+1} and the south pole −e_{d+1} represent hyperplanes at infinity. An oriented affine hyperplane in ℝ^{d} at infinity is the set ℝ^{d} or ∅, depending on the orientation. Indeed, embed ℝ^{d} into ℝ^{d+1} via the map (ξ_{1}, …, ξ_{d})^{t} ⟼ (1, ξ_{1}, …, ξ_{d})^{t}. Then an oriented affine hyperplane Ĥ in ℝ^{d} defines an oriented affine (d−1)-dimensional subspace of ℝ^{d+1} that extends (uniquely) to an oriented linear hyperplane H in ℝ^{d+1}. The outer unit normal vector that determines the oriented linear hyperplane is a point on the sphere S^{d}. We consider the following configuration spaces that parametrize arrangements of k oriented affine hyperplanes in ℝ^{d}:

(1) The join configuration space: X_{d,k} := (S^{d})^{∗k} ≅ S(ℝ^{(d+1)×k}),

(2) The product configuration space: Y_{d,k} := (S^{d})^{k}. The elements of the join X_{d,k} can be presented as formal convex combinations λ_{1}v_{1} + ⋯ + λ_{k}v_{k}, where λ_{i} ≥ 0, ∑ λ_{i} = 1 and v_{i} ∈ S^{d}.

2.3 The group actions

The space of all ordered k-tuples of oriented affine hyperplanes in ℝ^{d} has natural symmetries: Each hyperplane can change orientation and the hyperplanes can be permuted. Thus, the group 𝔖_{k}^{±} := (ℤ/2)^{k} ⋊ 𝔖_{k} encodes the symmetries of both configuration spaces. The group 𝔖_{k}^{±} acts on X_{d,k} as follows. Each copy of ℤ/2 acts antipodally on the appropriate sphere S^{d} in the join while the symmetric group 𝔖_{k} acts by permuting factors in the join product. More precisely, for ((β_{1}, …, β_{k}) ⋊ π) ∈ 𝔖_{k}^{±} and λ_{1}v_{1} + ⋯ + λ_{k}v_{k} ∈ X_{d,k} the action is given by

((β_{1}, …, β_{k}) ⋊ τ) · (λ_{1}v_{1} + ⋯ + λ_{k}v_{k}) =

λ_{τ^{−1}(1)}(−1)^{β_{1}}v_{τ^{−1}(1)} + ⋯ + λ_{τ^{−1}(k)}(−1)^{β_{k}}v_{τ^{−1}(k)}.

The product space Y_{d,k} is a subspace of the join X_{d,k} via the diagonal embedding Y_{d,k} ⟶ X_{d,k}, (v_{1}, …, v_{k}) ⟼ \frac{1}{k} v_{1} + ⋯ + \frac{1}{k} v_{k}. The product Y_{d,k} is an invariant subspace of X_{d,k} with respect to the 𝔖_{k}^{±}-action and consequently inherits the 𝔖_{k}^{±}-action from X_{d,k}. For k ≥ 2, the action of 𝔖_{k}^{±} is not free on either X_{d,k} or Y_{d,k}. The sets of points in the configuration spaces X_{d,k} and Y_{d,k} that have nontrivial stabilizer with respect to the action of 𝔖_{k}^{±} can be described as follows:

X_{d,k}^{>1} = {λ_{1}v_{1} + ⋯ + λ_{k}v_{k} :

λ_{1} ⋯ λ_{k} = 0, or λ_{s} = λ_{r} and v_{s} = ±v_{r} for some 1 ≤ s < r ≤ k},

and

Y_{d,k}^{>1} = {(v_{1}, …, v_{k}) : v_{s} = ±v_{r} for some 1 ≤ s < r ≤ k}.

2.4 Test spaces

Consider the vector space ℝ^{(ℤ/2)^{k}}, where the group element ((β_{1}, …, β_{k})⋊τ) ∈ 𝔖_{k}^{±} acts on a vector (y_{(α_{1},...,α_{k})})_{(α_{1},...,α_{k})∈(ℤ/2)^{k}} ∈ ℝ^{(ℤ/2)^{k}} by acting on its indices as

((β_{1}, …, β_{k}) ⋊ τ) · (α_{1}, …, α_{k}) = (β_{1} + α_{τ^{−1}(1)}, …, β_{k} + α_{τ^{−1}(k)}). (1)

The subspace of ℝ^{(ℤ/2)^{k}} defined by

U_{k} = {(y_{α})_{α∈(ℤ/2)^{k}} ∈ ℝ^{(ℤ/2)^{k}} : ∑_{α∈(ℤ/2)^{k}} y_{α} = 0}

is 𝔖_{k}^{±}-invariant and therefore an 𝔖_{k}^{±}-subrepresentation. Next we consider the vector space ℝ^{k} and its subspace

W_{k} = {(z_{1}, …, z_{k}) ∈ ℝ^{k} : ∑_{i=1}^{k} z_{i} = 0}.

The group 𝔖_{k}^{±} acts on ℝ^{k} by permuting coordinates, i.e., for ((β_{1}, …, β_{k})⋊τ) ∈ 𝔖_{k}^{±} and (z_{1}, …, z_{k}) ∈ ℝ^{k} we have

((β_{1}, …, β_{k}) ⋊ τ) · (z_{1}, …, z_{k}) = (z_{τ^{−1}(1)}, …, z_{τ^{−1}(k)}).  (2)

In particular, the subgroup (ℤ/2)^{k} of 𝔖_{k}^{±} acts trivially on ℝ^{k}. The subspace W_{k} ⊂ ℝ^{k} is 𝔖_{k}^{±}-invariant and consequently a 𝔖_{k}^{±}-subrepresentation.

2.5 Test maps

The product test map associated to the collection of j masses M = (μ_{1}, …, μ_{j}) from the configuration space Y_{d,k} to the test space U_{k}^{⊕j} is defined by

ϕ_{M}:  Y_{d,k} ⟶ U_{k}^{⊕j},
(v_{1}, …, v_{k}) ⟼ ((μ_{i}(H_{v_{1}}^{α_{1}} ∩ ⋯ ∩ H_{v_{k}}^{α_{k}}) − \frac{1}{2^{k}} )_{(α_{1},...,α_{k})∈(ℤ/2)^{k}})_{i∈\{1,...,j\}}.

In this paper we mostly work with the join configuration space X_{d,k}. The corresponding join test map associated to a collection of j masses M = (μ_{1}, …, μ_{j}) maps the configuration space X_{d,k} into the related test space W_{k} ⊕ U_{k}^{⊕j}. It is defined by

ψ_{M}:  X_{d,k} ⟶ W_{k} ⊕ U_{k}^{⊕j},
λ_{1}v_{1} + ⋯ + λ_{k}v_{k} ⟼ (λ_{1} − \frac{1}{k} , …, λ_{k} − \frac{1}{k}) ⊕ (λ_{1} ⋯ λ_{k}) · ϕ_{M}(v_{1}, …, v_{k}).

Both maps ϕ_{M} and ψ_{M} are 𝔖_{k}^{±}-equivariant with respect to the actions defined in Sections 2.3 and 2.4. Let S(U_{k}^{⊕j}) and S(W_{k} ⊕ U_{k}^{⊕j}) denote the unit spheres in the vector spaces U_{k}^{⊕j} and W_{k} ⊕ U_{k}^{⊕j}, respectively. The maps ϕ_{M} and ψ_{M} are called test maps since we have the following criterion, which reduces finding an equipartition to finding zeros of the test map.

Proposition 2.1. Let d ≥ 1, k ≥ 1, and j ≥ 1 be integers.

(i) Let M be a collection of j masses on ℝ^{d}, and let

ϕ_{M}: Y_{d,k} ⟶ U_{k}^{⊕j} and ψ_{M}: X_{d,k} ⟶ W_{k} ⊕ U_{k}^{⊕j}

be the 𝔖_{k}^{±}-equivariant maps defined above. If 0 ∈ im ϕ_{M}, or 0 ∈ im ψ_{M}, then there is an arrangement of k affine hyperplanes that equiparts M.

(ii) If there is no 𝔖_{k}^{±}-equivariant map of either type

Y_{d,k} ⟶ S(U_{k}^{⊕j}) or X_{d,k} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}),

then Δ(j, k) ≤ d.

It is worth pointing out that 0 ∈ im ϕ_{M} if and only if 0 ∈ im ψ_{M}, while the existence of an 𝔖_{k}^{±}-equivariant map Y_{d,k} ⟶ S(U_{k}^{⊕j}) implies the existence of a 𝔖_{k}^{±}-equivariant map X_{d,k} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}) but not vice versa. The homotopy class of the restrictions of the test maps ϕ_{M} and ψ_{M} on the set of points with non-trivial stabilizer (as maps avoiding the origin) is independent of the choice of the masses M, by the following proposition.

Proposition 2.2. Let M and M′ be collections of j masses in ℝ^{d}. Then (i) 0 ∉ im ϕ_{M}|_{Y_{d,k}^{>1}} and 0 ∉ im ψ_{M}|_{X_{d,k}^{>1}},

(ii) ϕ_{M}|_{Y_{d,k}^{>1}} and ϕ_{M′}|_{Y_{d,k}^{>1}} are 𝔖_{k}^{±}-homotopic as maps Y_{d,k}^{>1} ⟶ U_{k}^{⊕j}\{0},

and (iii) ψ_{M}|_{X_{d,k}^{>1}} and ψ_{M′}|_{X_{d,k}^{>1}} are 𝔖_{k}^{±}-homotopic as maps X_{d,k}^{>1} ⟶ (W_{k} ⊕

U_{k}^{⊕j})\{0}.

Proof. (i) If (v_{1}, …, v_{k}) ∈ Y_{d,k}^{>1}, then v_{s} = ±v_{r} for some 1 ≤ s < r ≤ k. Consequently, the corresponding hyperplanes H_{v_{i}} and H_{v_{j}} coincide, possibly with opposite orientations. Thus some of the orthants associated to the collection of hyperplanes (H_{v_{1}}, …, H_{v_{k}}) are empty. Consequently, Proposition 2.1 implies that 0 ∉ im ϕ_{M}|_{Y_{d,k}^{>1}}.

In the case where λ_{1}v_{1} + ⋯ + λ_{k}v_{k} ∈ X_{d,k}^{>1} the additional case λ_{s} = 0 for some 1 ≤ s ≤ k may occur. If λ_{s} = 0, then the s-th coordinate of ψ(λ_{1}v_{1} + ⋯ + λ_{k}v_{k}) ∈ W_{k} ⊕ U_{k}^{⊕j} is equal to −\frac{1}{k}, and hence 0 ∉ im ψ_{M}|_{X_{d,k}^{>1}}. (ii) The equivariant homotopy between ϕ_{M}|_{Y_{d,k}^{>1}} and ϕ_{M′}|_{Y_{d,k}^{>1}} is just the lin-

ear homotopy in U_{k}^{⊕j}. For this the linear homotopy should not have zeros, compare [3, proof of Cor. 5.4]. It suffices to prove that for each point (v_{1}, …, v_{k}) ∈ Y_{d,k}^{>1}, the points ϕ_{M}(v_{1}, …, v_{k}) and ϕ_{M′}(v_{1}, …, v_{k}) belong to some affine subspace of the test space that is not linear. First, observe that ℝ^{(ℤ/2)^{k}}, considered as a real (ℤ/2)^{k} representation, is the real regular representation of (ℤ/2)^{k} and therefore it decomposes into the direct sum of all real irreducible representations. For this we use the fact that all real irreducible representations of (ℤ/2)^{k} are 1-dimensional. The subspace U_{k} seen as a real (ℤ/2)^{k} subrepresentation of (ℤ/2)^{k} decomposes as follows:

U_{k} ≅ ⨁_{α∈(ℤ/2)^{k}\{0}} V_{α}.  (3)

Here V_{α} is the 1-dimensional real representation of (ℤ/2)^{k} determined by β·v = −v for x ∈ V_{α} if and only if α · β := ∑ α_{s}β_{s} = 1 ∈ ℤ/2, for β ∈ (ℤ/2)^{k}. The isomorphism (3) is given by the direct sum of the projections π_{α}: U_{k} ⟶ V_{α}, α ∈ (ℤ/2)^{k}\{0},

(y_{β})_{β∈(ℤ/2)^{k}\{0}} ⟼ ∑_{α·β=1} y_{β} − ∑_{α·β=0} y_{β}.

Now let v_{s} = ±v_{r}. Consider α ∈ (ℤ/2)^{k} given by α_{s} = 1 = α_{r} and α_{ℓ} = 0 for ℓ ∉ {s, r}, and the corresponding projection π_{α}^{⊕j}: U_{k}^{⊕j} ⟶ V_{α}^{⊕j}. Then

π_{α}^{⊕j} ∘ ϕ_{M}(v_{1}, …, v_{k}) = π_{α}^{⊕j} ∘ ϕ_{M′}(v_{1}, …, v_{k}) = (±1, …, ±1).

(iii) Likewise, the linear homotopy between ψ_{M}|_{X_{d,k}^{>1}} and ψ_{M′}|_{X_{d,k}^{>1}} is equivariant and avoids zero. Let λ_{1}v_{1} + ⋯ + λ_{k}v_{k} ∈ X_{d,k}^{>1}. If λ := λ_{1} ⋯ λ_{k} ≠ 0, λ_{s} = λ_{r} and v_{s} = ±v_{r}, then

(π_{α}^{⊕j} ∘ η ∘ ψ_{M})(λ_{1}v_{1} + ⋯ + λ_{k}v_{k}) = = (π_{α}^{⊕j} ∘ η ∘ ψ_{M′})(λ_{1}v_{1} + ⋯ + λ_{k}v_{k}) = (±λ, …, ±λ),

where η: W_{k} ⊕ U_{k}^{⊕j} ⟶ U_{k}^{⊕j} is the projection. Finally, in the case when λ_{s} = 0 for some 1 ≤ s ≤ k, ψ_{M}(λ_{1}v_{1} + ⋯ + λ_{k}v_{k}) and ψ_{M′}(λ_{1}v_{1} + ⋯ + λ_{k}v_{k}) after projection to the sth coordinate of the subrepresentation W_{k} are equal to −\frac{1}{k}.

Denote the radial projections by

ρ: U_{k}^{⊕j}\{0} ⟶ S(U_{k}^{⊕j}) and ν: (W_{k} ⊕ U_{k}^{⊕j})\{0} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}).

Note that ρ and ν are 𝔖_{k}^{±}-equivariant maps. Now the criterion stated in Proposition 2.1 (ii) can be strengthened as follows.

Theorem 2.3. Let d ≥ 1, k ≥ 1 and j ≥ 1 be integers, and let M be a collection of j masses in ℝ^{d}. We have the following two criteria:

(i) If there is no 𝔖_{k}^{±}-equivariant map

Y_{d,k} ⟶ S(U_{k}^{⊕j})

whose restriction to Y_{d,k}^{>1} is 𝔖_{k}^{±}-homotopic to ρ ∘ ϕ_{M}|_{Y_{d,k}^{>1}}, then Δ(j, k) ≤ d.

(ii) If there is no 𝔖_{k}^{±}-equivariant map

X_{d,k} ⟶ S(W_{k} ⊕ U_{k}^{⊕j})

whose restriction to X_{d,k}^{>1} is 𝔖_{k}^{±}-homotopic to ν ∘ ψ_{M}|_{X_{d,k}^{>1}}, then Δ(j, k) ≤ d.

2.6 Applying relative equivariant obstruction theory

In order to prove Theorems 1.4, 1.5, and 1.6 via Theorem 2.3(ii), we study the existence of an 𝔖_{k}^{±}-equivariant map

X_{d,k} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}),  (4)

whose restriction to X_{d,k}^{>1} is 𝔖_{k}^{±}-homotopic to ν ∘ ψ_{M}|_{X_{d,k}^{>1}} for some fixed collection M of j masses in ℝ^{d}. If we prove that such a map cannot exist, Theorems 1.4, 1.5, and 1.6 follow.

Denote by

N_{1} := (d + 1)k − 1

the dimension of the sphere X_{d,k} = (S^{d})^{∗k}, and by

N_{2} := (2^{k} − 1)j + k − 2

the dimension of the sphere S(W_{k} ⊕ U_{k}^{⊕j}). If N_{1} ≤ N_{2}, then

dim X_{d,k} = N_{1} ≤ conn(S(W_{k} ⊕ U_{k}^{⊕j})) + 1 = N_{2}.

Consequently, all obstructions to the existence of an 𝔖_{k}^{±}-equivariant map (4) vanish and so the map exists. Here conn(·) denotes the connectivity of a space. Therefore, we assume that N_{1} > N_{2}, which is equivalent to the Ramos lower bound d ≥ \frac{2^{k}−1}{k}j. Furthermore, the following prerequisites for applying equivariant obstruction theory are satisfied:

• The N_{1}-sphere X_{d,k} can be given the structure of a relative 𝔖_{k}^{±}-CW complex X := (X_{d,k}, X_{d,k}^{>1}) with a free 𝔖_{k}^{±}-action on X_{d,k}\X_{d,k}^{>1}: In Section 3 we construct an explicit relative 𝔖_{k}^{±}-CW complex that models X_{d,k}.

• The sphere S(W_{k} ⊕ U_{k}^{⊕j}) is path connected and N_{2}-simple, except in the trivial case of k = j = 1 when N_{2} = 0. Indeed, the group π_{1}(S(W_{k} ⊕ U_{k}^{⊕j})) is abelian for N_{2} = 1 and trivial for N_{2} > 1 and therefore its action on π_{N_{2}}(S(W_{k} ⊕ U_{k}^{⊕j})) is trivial.

• The 𝔖_{k}^{±}-equivariant map h: X_{d,k}^{>1} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}) given by the composition h := ν ∘ ψ_{M}|_{X_{d,k}^{>1}}, for a fixed collection of j masses M, serves as the base map for extension.

Since the sphere S(W_{k}⊕U_{k}^{⊕j}) is (N_{2}−1)-connected, the map h can be extended to a 𝔖_{k}^{±}-equivariant map from the N_{2}-skeleton X^{(N_{2})} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}). A necessary criterion for the existence of the 𝔖_{k}^{±}-equivariant map (4) extending h is that the 𝔖_{k}^{±}-equivariant map h = ν ∘ ψ_{M}|_{X_{d,k}^{>1}} can be extended to a map

from the (N_{2} + 1)-skeleton X^{(N_{2}+1)} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}). Given the above hypotheses, we can apply relative equivariant obstruction theory, as presented by tom Dieck [7, Sec. II.3], to decide the existence of such an extension. If g is an equivariant extension of h to the N_{2}-skeleton X^{(N_{2})}, then the obstruction to extending g to the (N_{2} + 1)-skeleton is encoded by the equivariant cocycle

𝔬(g) ∈ C_{𝔖_{k}^{±}}^{N_{2}+1}(X_{d,k}, X_{d,k}^{>1} ; π_{N_{2}}(S(W_{k} ⊕ U_{k}^{⊕j}))).

The 𝔖_{k}^{±}-equivariant map g: X^{(N_{2})} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}) extends to X^{(N_{2}+1)} if and only if 𝔬(g) = 0. Furthermore, the cohomology class

[𝔬(g)] ∈ H_{𝔖_{k}^{±}}^{N_{2}+1}(X_{d,k}, X_{d,k}^{>1} ; π_{N_{2}}(S(W_{k} ⊕ U_{k}^{⊕j}))), vanishes if and only if the restriction g|_{X^{(N_{2}−1)}} to the (N_{2} − 1)-skeleton can be extended to the (N_{2} + 1)-skeleton X^{(N_{2}+1)}. Any two extensions g and g′ of h to the N_{2}-skeleton are equivariantly homotopic on the (N_{2} − 1)-skeleton and therefore the cohomology classes coincide: [𝔬(g)] = [𝔬(g′)]. Hence, it suffices to compute the cohomology class [𝔬(ν ∘ ψ_{M}|_{X^{(N_{2})}})] for a fixed collection of j masses M with the property that 0 ∉ im(ψ_{M}|_{X^{(N_{2})}}). Let f be the attaching map for an (N_{2} + 1)-cell θ and e its corresponding basis element in the cellular chain group C_{N_{2}+1}(X_{d,k}, X_{d,k}^{>1}). Then

𝔬(ν ∘ ψ_{M}|_{X^{(N_{2})}})(e) = [ν ∘ ψ_{M} ∘ f|_{∂θ}]

is the homotopy class of the map represented by the composition

\xymatrix{∂θ_{j} \ar[r]^{f|_{∂θ}} & X^{(N_{2})} \ar[r]^{ν∘ψ_{M}|_{X^{(N_{2})}}} & S(W_{k} ⊕ U_{k}^{⊕j}).}

Since ∂θ and S(W_{k}⊕U_{k}^{⊕j}) are spheres of the same dimension N_{2}, the homotopy class [ν ∘ ψ_{M} ∘ f|_{∂θ}] is determined by the degree of the map ν ∘ ψ_{M} ∘ f|_{∂θ}. Here we assume that the 𝔖_{k}^{±}-CW structure on X_{d,k} is endowed with cell orientations, and in addition an orientation on the sphere S(W_{k} ⊕ U_{k}^{⊕j}) is fixed in advance. Therefore, the degree of the map ν ∘ ψ_{M} ∘ f|_{∂θ} is well-defined. Let α := ψ_{M} ∘ f|_{∂θ}. In order to compute the degree of the map ν ∘ α and consequently the obstruction cocycle evaluated at e, fix the collection of measures as follows. Let M be the collection of masses (I_{1}, …, I_{j}) where I_{r} is the mass concentrated on the segment γ((t_{r}^{1}, t_{r}^{2})) of the moment curve in ℝ^{d}

γ(t) = (t, \binom{t}{2}, \binom{t}{3}, …, \binom{t}{d})^{t},

such that

ℓ < t_{1}^{1} < t_{1}^{2} < t_{2}^{1} < t_{2}^{2} < ⋯ < t_{j}^{1} < t_{j}^{2},

for an integer ℓ, 0 ≤ ℓ ≤ d−1. The intervals (I_{1}, …, I_{j}) determined by numbers t_{r}^{1} < t_{r}^{2} can be chosen in such a way that 0 ∉ im(ψ_{M}|_{X^{(N_{2})}}). For every concrete situation in Section 4 this is verified directly. Now consider the following commutative diagram:

\xymatrix{∂θ \ar[r]^{f|_{∂θ}} \ar[d] & X^{(N_{2})} \ar[r]^{ψ_{M}|_{X^{(N_{2})}}} \ar[d] & W_{k} ⊕ U_{k}^{⊕j}\\{0\} \ar[d] \ar[r]^{ν} & S(W_{k} ⊕ U_{k}^{⊕j}) \\ θ \ar[r]^{f} & X^{(N_{2}+1)} \ar[r]^{ψ_{M}|_{X^{(N_{2}+1)}}} & W_{k} ⊕ U_{k}^{⊕j}}

where the vertical arrows are inclusions, and the composition of the lower horizontal maps is denoted by β := ψ_{M}|_{X^{(N_{2}+1)}} ∘ f. Furthermore, let B_{ε}(0) be a ball with center 0 in W_{k} ⊕ U_{k}^{⊕j} of sufficiently small radius ε > 0. Set θ̃:= θ\β^{−1}(B_{ε}(0)). Since dim θ = dim W_{k} ⊕ U_{k}^{⊕j} we can assume that the set of zeros β^{−1}(0) ⊂ relint θ is finite, say of cardinality r ≥ 0. Again, in every calculation presented in Section 4 this assumption is explicitly verified. The function β is a restriction of the test map and therefore the points in β^{−1}(0) correspond to arrangements of k hyperplanes H in relint θ that equipart M. Moreover, the facts that the measures are intervals on a moment curve and that each hyperplane of the arrangement from β^{−1}(0) cuts the moment curve in d distinct points imply that each zero in β^{−1}(0) is isolated and transversal. The boundary of θ̃ consists of the boundary ∂θ and r disjoint copies of N_{2}- spheres S_{1}, …, S_{r}, one for each zero of β on θ. Consequently, the fundamental class of ∂θ is equal to the sum of fundamental classes ∑[S_{i}] in H_{N_{1}}(θ̃; ℤ). Here the fundamental class of ∂θ is determined by the cell orientation inherited from the 𝔖_{k}^{±}-CW structure on X_{d,k}. The fundamental classes of [S_{i}] are determined in such a way that the equality [∂θ] = ∑[S_{i}] holds. Thus

∑(ν∘β|θ̃)_{∗}([S_{i}]) = (ν∘β|θ̃)_{∗}([∂θ]) = (ν∘α)_{∗}([∂θ]) = deg(ν∘α)·[S(W_{k}⊕U_{k}^{⊕j})].

Recall, we have fixed the orientation on the sphere S(W_{k} ⊕ U_{k}^{⊕j}) and so the fundamental class [S(W_{k} ⊕ U_{k}^{⊕j})] is also completely determined. On the other hand,

∑(ν ∘ β|_{S_{i}})_{∗}([S_{i}]) = ( ∑ deg(ν ∘ β|_{S_{i}})) · [S(W_{k} ⊕ U_{k}^{⊕j})].

Hence, deg(ν ∘α) = ∑ deg(ν ∘β|_{S_{i}}) where the sum ranges over all arrangements of k hyperplanes H in relint θ that equipart M; consult [14, Prop. IV.4.5]. In other words,

𝔬(ν ∘ ψ_{M}|_{X^{(N_{2})}})(e) = [ν ∘ ψ_{M} ∘ f|_{∂θ}] = deg(ν ∘ α) · ζ = ∑ deg(ν ∘ β|_{S_{i}}) · ζ, (5)

where ζ ∈ π_{N_{2}}(S(W_{k} ⊕ U_{k}^{⊕j})) ≅ ℤ is a generator, and the sum ranges over all arrangements of k hyperplanes H in relint θ that equipart M. If in addition we assume that all local degrees deg(ν ∘β|_{S_{i}}) are ±1 and that the number of arrangements of k hyperplanes H in relint θ that equipart M is odd, then we conclude that 𝔬(ν ∘ ψ_{M}|_{X^{(N_{2})}})(e) ≠ 0. It will turn out that in many situations this information implies that the cohomology class [𝔬(ν ∘ ψ_{M})] is not zero, and consequently the related 𝔖_{k}^{±}-equivariant map (4) does not exist, concluding the proof of corresponding Theorems 1.4, 1.5, and 1.6.

3 A regular cell complex model for the join configuration space

In this section, motivated by methods used in [2] and [6], we construct a regular 𝔖_{k}^{±}-CW model for the join configuration space X_{d,k} = (S^{d})^{∗k} ≅ S(ℝ^{(d+1)×k}) such that X_{d,k}^{>1} is a 𝔖_{k}^{±}-CW subcomplex. Consequently, (X_{d,k}, X_{d,k}^{>1}) has the structure of a relative 𝔖_{k}^{±}-CW complex. For simplicity the cell complex we construct is denoted by X := (X_{d,k}, X_{d,k}^{>1}) as well. The cell model is obtained in two steps:

(1) the vector space ℝ^{(d+1)×k} is decomposed into a union of disjoint relatively open cones (each containing the origin in its closure) on which the 𝔖_{k}^{±}- action operates linearly permuting the cones, and then

(2) the open cells of a regular 𝔖_{k}^{±}-CW model are obtained as intersections of these relatively open cones with the unit sphere S(ℝ^{(d+1)×k}).

The explicit relative 𝔖_{k}^{±}-CW complex we construct here is an essential object needed for the study of the existence of 𝔖_{k}^{±}-equivariant maps X_{d,k} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}) via the relative equivariant obstruction theory of tom Dieck [7, Sec. II.3].

3.1 Stratifications by cones associated to an arrangement

The first step in the construction of the 𝔖_{k}^{±}-CW model is an appropriate stratification of the ambient space ℝ^{(d+1)×k}. First we introduce the notion of the stratification of a Euclidean space and collect some relevant properties.

Definition 3.1. Let A be an arrangement of linear subspaces in a Euclidean space E. A stratification of E (by cones) associated to A is a finite collection C of subsets of E that satisfies the following properties:

(i) C consists of finitely many non-empty relatively open polyhedral cones in E.

(ii) C is a partition of E, i.e., E = ⨄_{C∈C} C. (iii) The closure \overline{C} of every cone C ∈ C is a union of cones in C. (iv) Every subspace A ∈ A is a union of cones in C. An element of the family C is called a stratum.

Example 3.2. Let E be a Euclidean space of dimension d, let L be a linear subspace of codimension r, where 1 ≤ r ≤ d, and let A be the arrangement {L}. Choose a flag that terminates at L, i.e., fix a sequence of linear subspaces in E

E = L^{(0)} ⊃ L^{(1)} ⊃ ⋯ ⊃ L^{(r)} = L,  (6)

so that dim L^{(i)} = d − i. The family C associated to the flag (6) consists of L and of the connected components of the successive complements

L^{(0)}\L^{(1)}, L^{(1)}\L^{(2)}, …, L^{(r−1)}\L^{(r)}.

A L^{(i)} is a hyperplane in L^{(i−1)}, each of the complements L^{(i−1)}\L^{(i)} has two connected components. This indeed yields a stratification by cones for the arrangement A in E.

Definition 3.3. Let (A_{1}, A_{2}, …, A_{n}) be a collection of arrangements of linear subspaces in the Euclidean space E and let (C_{1}, C_{2} …, C_{n}) be the associated collection of stratifications of E by cones. The common refinement of the stratifications is the family

C := {C_{1} ∩ C_{2} ∩ ⋯ ∩ C_{n} ≠ ∅ : C_{i} ∈ C_{i} for all i}.

In order to verify that the common refinement of stratifications is again a stratification, we use the following elementary lemma.

Lemma 3.4. Let A_{1}, …, A_{n} be relatively open convex sets in E that have nonempty intersection, A_{1} ∩ ⋯ ∩ A_{n} ≠ ∅. Then the following relation holds for the closures:

\overline{A_{1} ∩ ⋯ ∩ A_{n}} = \overline{A_{1}} ∩ ⋯ ∩ \overline{A_{n}}.

Proof. The inclusion “⊆” follows directly. For the opposite inclusion take x ∈ \overline{A_{1}} ∩ ⋯ ∩ \overline{A_{n}}. Choose a point y ∈ A_{1} ∩ ⋯ ∩ A_{n} ≠ ∅ and consider the line segment (x, y] := {λx+(1−λ)y : 0 ≤ λ < 1}. As each A_{i} is relatively open, the segment (x, y] is contained in each of the A_{i} and consequently it is contained in A_{1} ∩ ⋯ ∩ A_{n}. Thus we obtain a sequence in this intersection converging to x, which implies that x ∈ \overline{A_{1} ∩ ⋯ ∩ A_{n}}.

Proposition 3.5. Given stratifications by cones C_{1}, C_{2} …, C_{n} associated to linear subspace arrangements A_{1}, A_{2}, …, A_{n}, their common refinement is a stratification by cones associated to the subspace arrangement A := A_{1} ∪ ⋯ ∪ A_{n}.

Proof. Properties (i) and (ii) of Definition 3.1 follow immediately from the definition of the common refinement. To verify property (iv), observe that a subspace A_{t} ∈ A_{t} is a union of strata from C_{t}, say A_{t} = ⋃_{s} U_{t,s} where U_{t,s} ∈ C_{t}. Hence, taking the union of intersections C_{1} ∩ ⋯ ∩ U_{t,s} ∩ ⋯ ∩ C_{n} for all C_{i} ∈ C_{i} where i ≠ t, and all U_{t,s} gives A_{t}. Property (iii) follows from Lemma 3.4.

Example 3.6. Let E be a Euclidean space of dimension d and let A = {L_{1}, …, L_{s}} be an arrangement of linear subspaces of E. As in Example 3.2, for each of the subspaces L_{i} in the arrangement A fix a flag L_{i}^{(s)} and form the corresponding stratifications C_{1}, …, C_{s}. The common refinement of stratifications C_{1}, …, C_{s} is a stratification by cones associated to the subspace arrangement A.

An arrangement of linear subspaces is essential if the intersection of the subspaces in the arrangement is {0}.

Proposition 3.7. The intersection of a stratification C of E by cones associated to an essential linear subspace arrangement with the sphere S(E) gives a regular CW-complex.

Proof. The elements C ∈ C are relative open polyhedral cones. As {0} is a stratum by itself, none of the strata contains a line through the origin. Thus C ∩ S(E) is an open cell, whose closure \overline{C} ∩ S(E) is a finite union of cells of the form C′ ∩ S(E), so we get a regular CW complex.

3.2 A stratification of ℝ^{(d+1)×k}

Now we introduce the stratification of ℝ^{(d+1)×k} that will give us a 𝔖_{k}^{±}-CW model for X_{d,k}. One version of it, C, arises from the construction in the previous section. However, we also give combinatorial descriptions of relatively-open convex cones in the stratification C′ directly, for which the action of 𝔖_{k}^{±} is evident. We then verify that C and C′ coincide.

3.2.1 Stratification

Let elements x ∈ ℝ^{(d+1)×k} be written as x = (x_{1}, …, x_{k}) where x_{i} = (x_{t,i})_{t∈[d+1]} is the i-th column of the matrix x. Consider the arrangement A consisting of the following subspaces:

L_{r} := {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{r} = 0},  1 ≤ r ≤ k
L_{r,s}^{+} := {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{r} − x_{s} = 0}, 1 ≤ r < s ≤ k
L_{r,s}^{−} := {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{r} + x_{s} = 0}, 1 ≤ r < s ≤ k.

With each subspace we associate a flag:

(i) With L_{r} = {x_{r} = 0} we associate

ℝ^{(d+1)×k} ⊃ {x_{1,r} = 0} ⊃ {x_{1,r} = x_{2,r} = 0} ⊃ ⋯ ⊃

{x_{1,r} = x_{2,r} = ⋯ = x_{d+1,r} = 0},

(ii) With L_{r,s}^{+} = {x_{r} − x_{s} = 0} we associate

ℝ^{(d+1)×k} ⊃ {x_{1,r} −x_{1,s} = 0} ⊃ {x_{1,r} −x_{1,s} = x_{2,r} −x_{2,s} = 0} ⊃ ⋯ ⊃ {x_{1,r} − x_{1,s} = x_{2,r} − x_{2,s} = ⋯ = x_{d+1,r} − x_{d+1,s} = 0},

(iii) L_{r,s}^{−} = {x_{r} + x_{s} = 0} we associate

ℝ^{(d+1)×k} ⊃ {x_{1,r} +x_{1,s} = 0} ⊃ {x_{1,r} +x_{1,s} = x_{2,r} +x_{2,s} = 0} ⊃ ⋯ ⊃ {x_{1,r} + x_{1,s} = x_{2,r} + x_{2,s} = ⋯ = x_{d+1,r} + x_{d+1,s} = 0}.

The construction from Example 3.2 shows how every subspace in A leads to a stratification by cones of ℝ^{(d+1)×k}. The stratifications associated to the subspaces L_{r}, L_{r,s}^{+}, L_{r,s}^{−} are denoted by C_{r}, C_{r,s}^{+}, C_{r,s}^{−}, respectively. Now, if we apply Example 3.6 to this concrete situation we obtain the stratification by cones C of ℝ^{(d+1)×k} associated to the subspace arrangement A. This means that each stratum of C is a non-empty intersection of strata from the stratifications C_{r}, C_{r,s}^{+}, C_{r,s}^{−} where 1 ≤ r < s ≤ k.

3.2.2 Partition

Let us fix:

• a permutation σ := (σ_{1}, σ_{2}, …, σ_{k}) ≡ (σ_{1}σ_{2} … σ_{k}) ∈ 𝔖_{k}, σ: t ↦ σ_{t},

• a collection of signs S := (s_{1}, …, s_{k}) ∈ {+1, −1}^{k}, and

• integers I := (i_{1}, …, i_{k}) ∈ {1, …, d + 2}^{k}.

Furthermore, define x_{0} to be the origin in ℝ^{(d+1)×k}, σ_{0} = 0 and s_{0} = 1. Define

C_{I}^{S}(σ) = C_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k}) ⊆ ℝ^{(d+1)×k}

to be the set of all points (x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k}, x_{i} = (x_{1,i}, …, x_{d+1,i}), such that for each 1 ≤ t ≤ k,

• if 1 ≤ i_{t} ≤ d + 1, then s_{t−1}x_{i_{t},σ_{t−1}} < s_{t}x_{i_{t},σ_{t}} with s_{t−1}x_{i′,σ_{t−1}} = s_{t}x_{i′,σ_{t}} for every i′ < i_{t},

• if i_{t} = d + 2, then s_{i_{t−1}}x_{σ_{t−1}} = s_{i_{t}}x_{σ_{t}}. Any triple (σ|I|S) ∈ 𝔖_{k} × {1, …, d + 2}^{k} × {+1, −1}^{k} is called a symbol. In the notation of symbols we abbreviate signs {+1, −1} by {+, −}. The defining set of “inequalities” for the stratum C_{I}^{S}(σ) is briefly denoted by:

C_{I}^{S}(σ) = C_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k})
= {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : 0 <_{i_{1}} s_{1}x_{σ_{1}} <_{i_{2}} s_{2}x_{σ_{2}} <_{i_{3}} ⋯ <_{i_{k}} s_{k}x_{σ_{k}}},

where y <_{i} y′, for 1 ≤ i ≤ d + 1, means that y and y′ agree in the first i − 1 coordinates and at the i-th coordinate y_{i} < y′_{i}. The inequality y <_{d+2} y′ denotes that y = y′. Each set C_{I}^{S}(σ) is the relative interior of a polyhedral cone in (ℝ^{d+1})^{k} of codimension (i_{1} − 1) + ⋯ + (i_{k} − 1), i.e.,

dim C_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k}) = (d + 2)k − (i_{1} + ⋯ + i_{k}).

Let C′ denote the family of strata C_{I}^{S}(σ) defined by all symbols, i.e.,

C′ = {C_{I}^{S}(σ) : (σ|I|S) ∈ 𝔖_{k} × {1, …, d + 2}^{k} × {+1, −1}^{k}}.

Different symbols can define the same set, and

C_{I}^{S}(σ) ∩ C_{I′}^{S′}(σ) ≠ ∅ ⟺ C_{I}^{S}(σ) = C_{I′}^{S′}(σ).

In order to verify that the family C′ is a partition of ℝ^{(d+1)×k} it remains to prove that it is a covering.

Lemma 3.8. ⋃ C′ = ℝ^{(d+1)×k}.

Proof. Let (x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k}. First, choose signs r_{1}, …, r_{k} ∈ {+1, −1} so that the vectors r_{1}x_{1}, …, r_{k}x_{k} are greater or equal to 0 ∈ ℝ^{(d+1)×k} with respect to the lexicographic order, i.e., the first non-zero coordinate of each of the vectors r_{i}x_{i} is greater than zero. The choice of signs is not unique if one of the vectors x_{i} is zero. Next, record a permutation σ ∈ 𝔖_{k} such that

0 <_{lex} r_{σ_{1}}x_{σ_{1}} <_{lex} r_{σ_{2}}x_{σ_{2}} <_{lex} ⋯ <_{lex} r_{σ_{k}}x_{σ_{k}},

where <_{lex} denotes the lexicographic order. The permutation σ is not unique if r_{i}x_{i} = r_{t}x_{t} for some i ≠ t. Define s_{i} := r_{σ_{i}}. Finally, collect coordinates i_{t} where vectors s_{t−1}x_{σ_{t−1}} and s_{t}x_{σ_{t}} first differ, or put i_{t} = d + 2 if they coincide. Thus, (x_{1}, …, x_{k}) ∈ C_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k}).

Example 3.9. Let d = 0 and k = 2. Then the plane ℝ^{2} is decomposed into the following cones. There are 8 open cones of dimension 2:

\begin{aligned}C_{1,1}^{+,+}(12) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < x_{1} < x_{2}\}, \\ C_{1,1}^{−,+}(12) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < −x_{1} < x_{2}\}, \\ C_{1,1}^{+,−}(12) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < x_{1} < −x_{2}\}, \\ C_{1,1}^{−,−}(12) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < −x_{1} < −x_{2}\}, \\ C_{1,1}^{+,+}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < x_{2} < x_{1}\}, \\ C_{1,1}^{−,+}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < −x_{2} < x_{1}\}, \\ C_{1,1}^{+,−}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < x_{2} < −x_{1}\}, \\ C_{1,1}^{−,−}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < −x_{2} < −x_{1}\}. \end{aligned}

Furthermore, there are 8 cones of dimension 1:

\begin{aligned}C_{1,2}^{+,+}(12) & = & C_{1,2}^{+,+}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < x_{1} = x_{2}\}, \\ C_{1,2}^{−,+}(12) & = & C_{1,2}^{+,−}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < −x_{1} = x_{2}\}, \\ C_{1,2}^{+,−}(12) & = & C_{1,2}^{−,+}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < x_{1} = −x_{2}\}, \\ C_{1,2}^{−,−}(12) & = & C_{1,2}^{−,−}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 < −x_{1} = −x_{2}\}, \\ C_{2,1}^{+,+}(12) & = & C_{2,1}^{−,+}(12) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 = x_{1} < x_{2}\}, \\ C_{2,1}^{+,−}(12) & = & C_{2,1}^{−,−}(12) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 = x_{1} < −x_{2}\}, \\ C_{2,1}^{+,+}(21) & = & C_{2,1}^{−,+}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 = x_{2} < x_{1}\}, \\ C_{2,1}^{+,−}(21) & = & C_{2,1}^{−,−}(21) & = & \{(x_{1}, x_{2}) ∈ ℝ^{2} : 0 = x_{2} < −x_{1}\}. \end{aligned}

The origin in ℝ^{2} is given by C_{2,2}^{±,±}(12) = C_{2,2}^{±,±}(21). The example illustrates a property of our decomposition of ℝ^{(d+1)×k}: There is a surjection from symbals to cones that is not a bijection, i.e., different symbols can define the same cones.

Example 3.10. Let d = 2 and k = 4. The stratum associated to the symbol (2143 | 2, 3, 1, 4 | + 1, −1, +1, −1) can be described explicitly as follows.

\{( \begin{matrix}x_{1,1} & x_{1,2} & x_{1,3} & x_{1,4} \\ x_{2,1} & x_{2,2} & x_{2,3} & x_{2,4} \\ x_{3,1} & x_{3,2} & x_{3,3} & x_{3,4} \end{matrix} ) ∈ (ℝ^{3})^{4} :

\begin{matrix}0 & = & x_{1,2} & = & −x_{1,1} & < & x_{1,4} & = & −x_{1,3} \\ 0 & < & x_{2,2} & = & −x_{2,1} & & x_{2,4} & = & −x_{2,3} \\ & & x_{3,2} & < & −x_{3,1} & & x_{3,4} & = & −x_{3,3} \end{matrix} \} .

In particular,

C_{2,3,1,4}^{+,−,+,−}(2143) = C_{2,3,1,4}^{+,−,−,+}(2134).

3.2.3 C and C′ coincide

We proved that C is a stratification by cones of ℝ^{(d+1)×k}, and that C′ is a partition of ℝ^{(d+1)×k}. Since both C and C′ are partitions it suffices to prove

Figure 1: Illustration of the stratification in Example 3.9

that for every symbol (σ|I|S) ∈ 𝔖_{k} × {1, …, d + 2}^{k} × {+1, −1}^{k} the cone C_{I}^{S}(σ) ∈ C′ also belongs to C. Consider the cone C_{I}^{S}(σ) in C′. It is determined by

C_{I}^{S}(σ) = C_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k})
= {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : 0 <_{i_{1}} s_{1}x_{σ_{1}} <_{i_{2}} s_{2}x_{σ_{2}} <_{i_{3}} ⋯ <_{i_{k}} s_{k}x_{σ_{k}}}.

The defining inequalities for C_{I}^{S}(σ) imply that (x_{1}, …, x_{k}) ∈ C_{I}^{S}(σ) if and only if

• 0 <_{min{i_{1},...,i_{a}}} s_{a}x_{a} for 1 ≤ a ≤ k, and

• s_{a}x_{a} <_{min{i_{a+1},...,i_{b}}} s_{b}x_{b} for 1 ≤ a < b ≤ k, if and only if

• (x_{1}, …, x_{k}) belongs to the appropriate one of two strata in the complement

L_{a}^{(min{i_{1},...,i_{a}}−1)} \ L_{a}^{(min{i_{1},...,i_{a}}−2)}

of the stratification C_{a} depending on the sign s_{a} where 1 ≤ a ≤ k, and • (x_{1}, …, x_{k}) belongs to the appropriate one of two strata in the complement

L_{a,b}^{s_{a}s_{b}}^{(min{i_{a+1},...,i_{b}}−1)} \ L_{a,b}^{s_{a}s_{b}}^{(min{i_{a+1},...,i_{b}}−2)}

of the stratification C_{a,b}^{s_{a}s_{b}} depending on the sign of the product s_{a}s_{b} where 1 ≤ a < b ≤ k. The product s_{a}s_{b}, appearing in the “exponent notation” of L_{a,b}^{s_{a}s_{b}}, is either “+” when the product s_{a}s_{b} = 1, or “−” when s_{a}s_{b} = −1.

Here we use the notation of Examples 3.2 and 3.6. Thus we have proved that C_{I}^{S}(σ) ∈ C and consequently C = C′.

3.3 The 𝔖_{k}^{±}-CW model for X_{d,k}

The action of the group 𝔖_{k}^{±} on the space ℝ^{(d+1)×k} induces an action on the family of strata C by as follows:

π · C_{I}^{S}(σ) = C_{I}^{S}(πσ),  (7)
ε_{t} · C_{I}^{S}(σ) = ε_{t} · C_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k})
= C_{i_{1},...,i_{k}}^{s_{1},...,−s_{t},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k}),  (8)

where π ∈ 𝔖_{k} and ε_{1}, …, ε_{k} are the canonical generators of the subgroup (ℤ/2)^{k} of 𝔖_{k}^{±}. The 𝔖_{k}^{±}-CW complex that models X_{d,k} = S(ℝ^{(d+1)×k}) is obtained by intersecting each stratum C_{I}^{S}(σ) with the unit sphere S(ℝ^{(d+1)×k}). Each stratum is a relatively open cone that does not contain a line. Therefore the intersection

D_{I}^{S}(σ) = D_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k}) := C_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k}) ∩ S(ℝ^{(d+1)×k})

is an open cell of dimension (d + 2)k − (i_{1} + ⋯ + i_{k}) − 1. The action of 𝔖_{k}^{±} is induced by (7) and (8):

π · D_{I}^{S}(σ) = D_{I}^{S}(πσ),  (9)
ε_{t} · D_{I}^{S}(σ) = ε_{t} · D_{i_{1},...,i_{k}}^{s_{1},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k})
= D_{i_{1},...,i_{k}}^{s_{1},...,−s_{t},...,s_{k}}(σ_{1}, σ_{2}, …, σ_{k}).  (10)

Thus we have obtained a regular 𝔖_{k}^{±}-CW model for X_{d,k}. In particular, the action of the group 𝔖_{k}^{±} on the space ℝ^{(d+1)×k} induces a cellular action on the model.

Theorem 3.11. Let d ≥ 1 and k ≥ 1 be integers, and N_{1} = (d + 1)k − 1. The family of cells

{D_{I}^{S}(σ) : (σ|I|S) ≠ (σ|d + 2, …, d + 2|S)}

forms a finite regular N_{1}-dimensional 𝔖_{k}^{±}-CW complex X := (X_{d,k}, X_{d,k}^{>1}) that models the join configuration space X_{d,k} = S(ℝ^{(d+1)×k}). It has

• one full 𝔖_{k}^{±}-orbit in maximal dimension N_{1}, and

• k full 𝔖_{k}^{±}-orbits in dimension N_{1} − 1. The (cellular) 𝔖_{k}^{±}-action on X_{d,k} is given by (9) and (10). Furthermore the collection of cells

{D_{I}^{S}(σ) : i_{s} = d + 2 for some 1 ≤ s ≤ k}

is a 𝔖_{k}^{±}-CW subcomplex and models X_{d,k}^{>1}.

Example 3.12. Let d ≥ 1 and k ≥ 2 be integers with dk = (2^{k} −1)j +ℓ, where 0 ≤ ℓ ≤ d − 1. Consider the cell θ := D_{ℓ+1,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k) of dimension N_{1} − ℓ = N_{2} + 1 in X_{d,k}. It is determined by the following inequalities:

0 <_{ℓ+1} x_{1} <_{1} x_{2} <_{1} ⋯ <_{1} x_{k}.

For the process of determining the boundary of θ, depending on value of ℓ, we distinguish the following cases.

(1) Let ℓ = 0. Then θ := D_{1,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k). The cells of codimension 1 in the boundary of θ are obtained by introducing one of the following extra equalities:

x_{1,1} = 0 , x_{1,1} = x_{1,2} , … x_{1,k−1} = x_{1,k}.

Each of these equalities will give two cells of dimension N_{2}, hence in total 2k cells of codimension 1, in the boundary of θ.

(a) The equality x_{1,1} = 0 induces cells:

γ_{1} := D_{2,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k), γ_{2} := D_{2,1,1,...,1}^{−,+,+,...,+}(1, 2, 3, …, k)

that are related, as sets, via γ_{2} = ε_{1} · γ_{1}. Both cells γ_{1} and γ_{2} belong to the linear subspace

V_{1} = {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{1,1} = 0}.

(b) The equality x_{1,r−1} = x_{1,r} for 2 ≤ r ≤ k gives cells:

γ_{2r−1} := D_{1,...,1,2,1,...,1}^{+,+,+,...,+}(1, …, r − 1, r, r + 1, …, k),
γ_{2r} := D_{1,...,1,2,1,...,1}^{+,+,+,...,+}(1, …, r, r − 1, r + 1, …, k)

satisfying γ_{2r} = τ_{r−1,r}·γ_{2r−1}. In these cells the index 2 in the subscript 1, …, 1, 2, 1, …, 1 appears at the position r. These cells belong to the linear subspace

V_{r} = {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{1,r−1} = x_{1,r}}.

Let e_{θ} denote a generator in C_{N_{2}+1}(X_{d,k}, X_{d,k}^{>1}) that corresponds to the cell θ. Furthermore let e_{γ_{1}}, …, e_{γ_{2k}} denote generators in C_{N_{2}}(X_{d,k}, X_{d,k}^{>1}) related to the cells γ_{1}, …, γ_{2k}. The boundary of the cell θ is contained in the union of the linear subspaces V_{1}, …, V_{k}. Therefore we can orient the cells γ_{2i−1}, γ_{2i} consistently with the orientation of V_{i}, 1 ≤ i ≤ k, that is given in such a way that

∂e_{θ} = (e_{γ_{1}} + e_{γ_{2}}) + (e_{γ_{3}} + e_{γ_{4}}) + ⋯ + (e_{γ_{2k−1}} + e_{γ_{2k}}).

Consequently,

∂e_{θ} = (1 + (−1)^{d}ε_{1}) · e_{γ_{1}} + ∑_{i=2}^{k}(1 + (−1)^{d}τ_{i−1,i}) · e_{γ_{2i−1}}.  (11)

(2) Let ℓ = 1. Then θ := D_{2,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k). Now the cells in the boundary of θ are obtained by introducing extra equalities:

x_{2,1} = 0 , (0 =) x_{1,1} = x_{1,2} , … x_{1,k−1} = x_{1,k}.

Each of these equalities, except for the second one, will give two cells of dimension N_{2}, which yields 2(k − 1) cells in total, in the boundary of θ. The equality x_{1,1} = x_{1,2} will give additional four cells in the boundary of θ.

(a) The equality x_{2,1} = 0 induces cells:

γ_{1} := D_{3,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k), γ_{2} := D_{3,1,1,...,1}^{−,+,+,...,+}(1, 2, 3, …, k)

that are related, as sets, via γ_{2} = ε_{1} · γ_{1}. Notice that both cells γ_{1} and γ_{2} belong to the linear subspace

V_{1} = {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{1,1} = x_{2,1} = 0}.

(b) The equality x_{1,1} = x_{1,2} yields the cells

γ_{3} := D_{2,2,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k), γ_{31} := D_{2,2,1,...,1}^{+,−,+,...,+}(1, 2, 3, …, k),

γ_{32} := D_{2,2,1,...,1}^{+,+,+,...,+}(2, 1, 3, …, k), γ_{33} := D_{2,2,1,...,1}^{−,+,+,...,+}(2, 1, 3, …, k).

They satisfy set identities γ_{31} = ε_{2} · γ_{3}, γ_{32} = τ_{1,2} · γ_{3}, and γ_{33} = ε_{1}τ_{1,2} · γ_{3}. All four cells belong to the linear subspace

V_{2} = {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : 0 = x_{1,1} = x_{1,2}}.

(c) The equality x_{1,r−1} = x_{1,r} for 3 ≤ r ≤ k gives cells:

γ_{2r−1} := D_{2,...,1,2,1,...,1}^{+,+,+,...,+}(1, …, r − 1, r, r + 1, …, k),
γ_{2r} := D_{2,...,1,2,1,...,1}^{+,+,+,...,+}(1, …, r, r − 1, r + 1, …, k)

satisfying γ_{2r} = τ_{r−1,r} · γ_{2r−1}. In these cells the second index 2 in the subscript 2, …, 1, 2, 1, …, 1 appears at the position r. These cells belong to the linear subspace

V_{r} = {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{1,1} = 0, x_{1,r−1} = x_{1,r}}.

Again e_{θ} denotes a generator in C_{N_{2}+1}(X_{d,k}, X_{d,k}^{>1}) corresponding to θ. Let e_{γ_{1}}, e_{γ_{2}}, e_{γ_{3}}, e_{γ_{31}}, e_{γ_{32}}, e_{γ_{33}}, e_{γ_{4}} …, e_{γ_{2k}} denote generators in C_{N_{2}}(X_{d,k}, X_{d,k}^{>1}) related to the cells γ_{1}, γ_{2}, γ_{3}, γ_{31}, γ_{32}, γ_{33}, …, γ_{2k}. The boundary of the cell θ, as before, is contained in the union of the linear subspaces V_{1}, …, V_{k}. Therefore we can orient cells consistently with the orientation of V_{i}, 1 ≤ i ≤ k, that is given in such a way that

∂e_{θ} = (e_{γ_{1}} + e_{γ_{2}}) + (e_{γ_{3}} + e_{γ_{31}} + e_{γ_{32}} + e_{γ_{33}}) + ⋯ + (e_{γ_{2k−1}} + e_{γ_{2k}}).

Consequently,

∂e_{θ} = (1 + (−1)^{d−1}ε_{1}) · e_{γ_{1}} +  (12)

(1 + (−1)^{d}ε_{2} + (−1)^{d}τ_{1,2} + (−1)^{d+d}ε_{1}τ_{1,2}) · e_{γ_{3}} +

∑_{i=3}^{k}(1 + (−1)^{d}τ_{i−1,i}) · e_{γ_{2i−1}}.

(3) Let 2 ≤ ℓ ≤ d − 1. Then θ := D_{ℓ+1,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k). The cells in the boundary of θ are now obtained by introducing following equalities:

x_{ℓ+1,1} = 0 , (0 =)x_{1,1} = x_{1,2} , … x_{1,k−1} = x_{1,k}.

Each of them will give two cells of dimension N_{2} in the boundary of θ, all together 2k.

(a) The equality x_{ℓ+1,1} = 0 induces cells:

γ_{1} := D_{ℓ+2,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k), γ_{2} := D_{ℓ+2,1,1,...,1}^{−,+,+,...,+}(1, 2, 3, …, k)

that are related, as sets, via γ_{2} = ε_{1} · γ_{1}. Both cells γ_{1} and γ_{2} belong to the linear subspace

V_{1} = {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{1,1} = ⋯ = x_{ℓ+1,1} = 0}.

(b) The equality (0 =)x_{1,1} = x_{1,2} gives the cells

γ_{3} := D_{ℓ+1,2,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k), γ_{4} := D_{ℓ+1,2,1,...,1}^{+,−,+,...,+}(1, 2, 3, …, k)

that satisfy γ_{4} = ε_{2} · γ_{3}. Both cells belong to the linear subspace

V_{2} = {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{1,1} = ⋯ = x_{ℓ,1} = 0, x_{1,1} = x_{1,2}}.

(c) The equality x_{1,r−1} = x_{1,r} for 3 ≤ r ≤ k gives cells:

γ_{2r−1} := D_{ℓ+1,...,1,2,1,...,1}^{+,+,+,...,+}(1, …, r − 1, r, r + 1, …, k),
γ_{2r} := D_{ℓ+1,...,1,2,1,...,1}^{+,+,+,...,+}(1, …, r, r − 1, r + 1, …, k)

satisfying γ_{2r} = τ_{r−1,r}·γ_{2r−1}. In these cells the index 2 in the subscript ℓ + 1, …, 1, 2, 1, …, 1 appears at the position r. These cells belong to the linear subspace

V_{r} = {(x_{1}, …, x_{k}) ∈ ℝ^{(d+1)×k} : x_{1,1} = ⋯ = x_{ℓ,1} = 0, x_{1,r−1} = x_{1,r}}.

Again e_{θ} denotes a generator in C_{N_{2}+1}(X_{d,k}, X_{d,k}^{>1}) that corresponds to the cell θ. Furthermore e_{γ_{1}}, …, e_{γ_{2k}} denote generators in C_{N_{2}}(X_{d,k}, X_{d,k}^{>1}) related to the cells γ_{1}, …, γ_{2k}. As before, the boundary of the cell θ is contained in the union of the linear subspaces V_{1}, …, V_{k}. Thus we can orient cells γ_{2i−1}, γ_{2i} consistently with the orientation of V_{i}, 1 ≤ i ≤ k, that is given in such a way that

∂e_{θ} = (e_{γ_{1}} + e_{γ_{2}}) + (e_{γ_{3}} + e_{γ_{4}}) + ⋯ + (e_{γ_{2k−1}} + e_{γ_{2k}}).

Hence,

∂e_{θ} = (1+(−1)^{d−ℓ}ε_{1})·e_{γ_{1}} +(1+(−1)^{d}ε_{2})·e_{γ_{3}} +∑_{i=3}^{k}(1+(−1)^{d}τ_{i−1,i})·e_{γ_{2i−1}}.

(13)

The relations (11), (12) and (13) that we have now derived will be essential in the proofs of Theorems 1.4 and 1.5.

3.4 The arrangements parametrized by a cell

In this section we describe all arrangements of k hyperplanes parametrized by the cell

θ := D_{ℓ+1,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k),

where 1 ≤ ℓ ≤ d − 1. This description will be one of the key ingredients in Section 4 when the obstruction cocycle is evaluated on the cell θ. Recall that the cell θ is defined as the intersection of the sphere S(ℝ^{(d+1)×k}) and the cone given by the inequalities:

0 <_{ℓ+1} x_{1} <_{1} x_{2} <_{1} ⋯ <_{1} x_{k}.

Consider the binomial coefficient moment curve γ̂: ℝ ⟶ ℝ^{d} defined by

γ̂(t) = (t, \binom{t}{2}, \binom{t}{3}, …, \binom{t}{d})^{t}.  (14)

After embedding ℝ^{d} ⟶ ℝ^{d+1}, (ξ_{1}, …, ξ_{d})^{t} ⟼ (1, ξ_{1}, …, ξ_{d})^{t} it corresponds to the curve γ: ℝ ⟶ ℝ^{d+1} given

γ(t) = (1, t, \binom{t}{2}, \binom{t}{3}, …, \binom{t}{d})^{t}.

Consider the following points on the moment curve γ:

q_{1} := γ(0), …, q_{ℓ+1} := γ(ℓ).  (15)

Next, recall that each oriented affine hyperplane Ĥ in ℝ^{d} (embedded in ℝ^{d+1}) determines the unique linear hyperplane H such that Ĥ = H ∩ ℝ^{d}, and almost vice versa. Now, the family of arrangements parametrized by the (open) cell θ is described as follows:

Lemma 3.13. The cell θ = D_{ℓ+1,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k) parametrizes all arrangements H = (H_{1}, …, H_{k}) of k linear hyperplanes in ℝ^{d+1}, where the order and orientation are fixed appropriately such that

• Q := {q_{1}, …, q_{ℓ}} ⊂ H_{1},

• q_{ℓ+1} ∉ H_{1},

• q_{1} ∉ H_{2}, …, q_{1} ∉ H_{k}, and

• H_{2}, …, H_{k} have unit normal vectors with different (positive) first coordinates, that is, |{⟨x_{2}, q_{1}⟩, ⟨x_{3}, q_{1}⟩, …, ⟨x_{k}, q_{1}⟩}| = k − 1.

Here x_{i} ∈ S(ℝ^{(d+1)×k}) is a unit normal vector of the hyperplane H_{i}, for 1 ≤ i ≤ k.

Proof. Observe that {q_{1}, …, q_{ℓ}} ⊂ H_{1} holds if and only if ⟨x_{1}, q_{1}⟩ = ⟨x_{1}, q_{2}⟩ = ⋯ = ⟨x_{1}, q_{ℓ}⟩ = 0 if and only if x_{1,1} = x_{2,1} = ⋯ = x_{ℓ,1} = 0: This is true since we have the binomial moment curve, so q_{i} = γ(i − 1) has only the first i coordinates non-zero. Furthermore, q_{ℓ+1} ∉ H_{1} holds if and only if x_{ℓ+1,1} ≠ 0; choosing an appropriate orientation for H_{1} we can assume that x_{ℓ+1,1} > 0.

The third condition is equivalent to 0 ∉ {⟨x_{2}, q_{1}⟩, ⟨x_{3}, q_{1}⟩, …, ⟨x_{k}, q_{1}⟩}, that is, x_{1,2}, x_{1,3}, …, x_{1,k} ≠ 0. Choosing orientations of H_{2}, …, H_{k} suitably this yields x_{1,2}, x_{1,3}, …, x_{1,k} > 0. Since the values x_{1,2} = ⟨x_{2}, q_{1}⟩, x_{1,3} = ⟨x_{3}, q_{1}⟩, …, x_{1,k} = ⟨x_{k}, q_{1}⟩ are positive and distinct, we get 0 < x_{1,2} < x_{1,3} < ⋯ < x_{1,k} by choosing the right order on H_{2}, …, H_{k}.

4 Proofs

4.1 Proof of Theorem 1.3

Let d ≥ 1, j ≥ 1, ℓ ≥ 0 and k ≥ 2 be integers with the property that dk = j(2^{k} − 1) + ℓ for 0 ≤ ℓ ≤ d − 1. Consider a collection of j ordered disjoint intervals M = (I_{1}, …, I_{j}) along the moment curve γ. Let Q = {q_{1}, …, q_{ℓ}} ⊂ γ be a set of ℓ predetermined points that lie to the left of the interval I_{1}. We prove Theorem 1.3 in two steps.

Lemma 4.1. Let A be an ℓ-equiparting matrix, that is, a binary matrix of size k × j2^{k} with one row of transition count d − ℓ and all other rows of transition count d such that A = (A_{1}, …, A_{j}) for Gray codes A_{1}, …, A_{j} with the property that the last column of A_{i} is equal to the first column of A_{i+1} for 1 ≤ i < j. Then A determines an arrangement H of k affine hyperplanes that equipart M = (I_{1}, …, I_{j}) and one of the hyperplanes passes through each point in Q.

Proof. Without loss of generality we assume that the first row of the matrix A has transition count d − ℓ while rows 2 through k have transition count d. For a row a_{s} of the matrix A, denote by t_{s} its transition count, 1 ≤ s ≤ k. Place j(2^{k} + 1) ordered points q_{ℓ+1}, …, q_{ℓ+j(2^{k}+1)} on γ, such that

I_{i} = [q_{ℓ+(i−1)2^{k}+i}, q_{ℓ+i2^{k}+i}]

and each sequence of 2^{k}+1 points divides I_{i} into 2^{k} subintervals of equal length. Ordered refers to the property that q_{r} = γ(t_{r}) if t_{1} < t_{2} < ⋯ < t_{j(2^{k}+1)}. We now define the hyperplanes in H by specifying which of the points they pass through and then choosing their orientations. Force the affine hyperplane H_{1} to pass through all of the points in Q. For s = 1, …, i, the affine hyperplane H_{s} passes through x_{ℓ+r+i} if there is a bit change in row a_{s} from entry r to entry r + 1 for (i − 1)2^{k} < r ≤ i2^{k}. Orient H_{s} such that the subinterval [q_{r}, q_{r+1}] is on the positive side of H_{s} if it corresponds to a 0-entry in a_{s}. Since each A_{1}, …, A_{j} is a Gray code, the arrangement H is indeed an equipartition.

Lemma 4.2. Every arrangement of k affine hyperplanes H that equiparts M = (I_{1}, …, I_{j}) and where one of the hyperplanes passes through each point of Q induces a unique binary matrix A as in Lemma 4.1.

Proof. Since dk = j(2^{k} − 1) + ℓ and 0 ≤ ℓ ≤ d − 1, the hyperplanes in H must pass through the points q_{ℓ+(i−1)2^{k}+i+1}, …, q_{ℓ+i2^{k}+i−1} of the intervals I_{i} for i ∈ {1, …, j}. Recording the position of the subintervals [q_{ℓ+r}, q_{ℓ+r+1}], for r ≠ i2^{k} + i, with respect to each hyperplane leads to a matrix as in described in Lemma 4.1.

Figure 2: Illustration of one step in the proof of Lemma 4.1. Here H_{1} is an affine hyperplane bisecting two intervals I_{1} and I_{2} on the 5-dimensional moment curve.

Thus the number of non-equivalent ℓ-equiparting matrices is the same as the number of arrangements of k affine hyperplanes H that equipart the collection of j disjoint intervals on the moment curve in ℝ^{d}, up to renumbering and orientation change of hyperplanes in H, when one of the hyperplanes is forced to pass through ℓ prescribed points on the moment curve lying to the left of the intervals. This concludes the proof of Theorem 1.3.

4.2 Proof of Theorem 1.4

Let j ≥ 1 and k ≥ 3 be integers with d = ⌈\frac{2^{k}−1}{k}j⌉ and ℓ = dk − (2^{k} − 1)j. In addition, assume that the number of non-equivalent ℓ-equiparting matrices of size k × j2^{k} is odd. In order to prove that Δ(j, k) ≤ d it suffices by Theorem 2.3 to prove that there is no 𝔖_{k}^{±}-equivariant map

X_{d,k} ⟶ S(W_{k} ⊕ U_{k}^{⊕j}),

whose restriction to X_{d,k}^{>1} is 𝔖_{k}^{±}-homotopic to ν ∘ψ_{M}|_{X_{d,k}^{>1}} for M = (I_{1}, …, I_{j}). Following Section 2.6 we verify that the cohomology class

[𝔬(g)] ∈ H_{𝔖_{k}^{±}}^{N_{2}+1}(X_{d,k}, X_{d,k}^{>1} ; π_{N_{2}}(S(W_{k} ⊕ U_{k}^{⊕j}))),

does not vanish, where g = ν ∘ ψ_{M}|_{X^{(N_{2})}}. Consider the cell θ := D_{ℓ+1,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k) of dimension (d+1)k −1−ℓ = N_{2} + 1 in X_{d,k}, as in Example 3.12. Let e_{θ} denote the corresponding basis element of the cell θ in the cellular chain group C_{N_{2}+1}(X_{d,k}, X_{d,k}^{>1}), and let h_{θ} be the attaching map of θ. This cell is cut out from the unit sphere S(ℝ^{(d+1)×k}) by the following inequalities:

0 <_{ℓ+1} x_{1} <_{1} x_{2} <_{1} ⋯ <_{1} x_{k}.

In particular, this means that the first ℓ coordinates of x_{1} are zero, i.e., x_{1,1} = x_{2,1} = x_{3,1} = ⋯ = x_{ℓ,1} = 0, and x_{ℓ+1,1} > 0.

Let us fix ℓ points Q = {q_{1}, …, q_{ℓ}} on the moment curve (14) in ℝ^{d+1} as it was done in (15): q_{1} := γ(0), …, q_{ℓ} := γ(ℓ − 1). Then, by Lemma 3.13, the relative interior of D_{ℓ+1,1,1,...,1}^{+,+,+,...,+}(1, 2, 3, …, k) parametrizes the arrangements H = (H_{1}, …, H_{k}) for which orientations and order of the hyperplanes are fixed with H_{1} containing all the points from Q. According to the formula (5) we have that

𝔬(g)(e_{θ}) = [ν ∘ ψ_{M} ∘ h_{θ}|_{∂θ}] = ∑ deg(ν ∘ ψ_{M}|_{X^{(N_{2}+1)}} ∘ h_{θ}|_{S_{i}}) · ζ,

where as before ζ ∈ π_{N_{2}}(S(W_{k} ⊕ U_{k}^{⊕j})) ≅ ℤ is a generator, and the sum ranges over all arrangements of k hyperplanes in relint θ that equipart M. Here, as before, S_{i} denotes a small N_{2}-sphere around a root of the function ψ_{M}|_{X^{(N_{2}+1)}}∘h_{θ}, i.e., the point that parametrizes an arrangements of k hyperplanes in relint θ that equipart M. Now, the local degrees of the function ν ∘ ψ_{M}|_{X^{(N_{2}+1)}} ∘ h_{θ} are ±1. Indeed, in a small neighborhood U ⊆ relint θ around any root the test map ψ_{M} is a continuous bijection. Thus ψ_{M}|_{∂U} is a continuous bijection into some N_{2}-sphere around the origin in W_{k} ⊕U_{k}^{⊕j} and by compactness of ∂U is a homeomorphism. Consequently,

𝔬(g)(e_{θ}) = ∑ deg(ν ∘ ψ_{M}|_{X^{(N_{2}+1)}} ∘ h_{θ}|_{S_{i}}) · ζ = ( ∑ ±1) · ζ = a · ζ, (16)

where the sum ranges over all arrangements of k hyperplanes in relint θ that equipart M. According to Theorem 1.3 the number of (±1)’s in the sum (16) is equal to the number of non-equivalent ℓ-equiparting matrices of size k×j2^{k}. By our assumption this number is odd and consequently a ∈ ℤ is an odd integer. We obtained that

𝔬(g)(e_{θ}) = a · ζ,  (17)

where a ∈ ℤ is an odd integer.

Remark 4.3. It is important to point out that the calculations and formulas up to this point also hold for k = 2. The assumption k ≥ 3 affects the 𝔖_{k}^{±} = (ℤ/2)^{k} ⋊ 𝔖_{k} module structure on π_{N_{2}}(S(W_{k} ⊕ U_{k}^{⊕j})) ≅ ℤ. For k ≥ 2 every generator ε_{i} of the subgroup (ℤ/2)^{k} acts trivially, while each transposition τ_{i,t}, a generator of the subgroup 𝔖_{k}, acts as multiplication by −1 in the case k ≥ 3, and as multiplication by (−1)^{j+1} in the case k = 2.

Finally, we prove that [𝔬(g)] does not vanish and conclude the proof. This will be achieved by proving that the cocycle 𝔬(g) is not a coboundary. Let us assume to the contrary that 𝔬(g) is a coboundary. Thus there exists a cochain

𝔥 ∈ C_{𝔖_{k}^{±}}^{N_{2}}(X_{d,k}, X_{d,k}^{>1} ; π_{N_{2}}(S(W_{k} ⊕ U_{k}^{⊕j})))

such that 𝔬(g) = δ𝔥, where δ denotes the coboundary operator. In the case when (1) ℓ = 0 the relation (11) implies that

a · ζ = 𝔬(g)(e_{θ}) = δ𝔥(e_{θ}) = 𝔥(∂e_{θ})
= (1 + (−1)^{d}ε_{1}) · 𝔥(e_{γ_{1}}) + ∑_{i=2}^{k}(1 + (−1)^{d}τ_{i−1,i}) · 𝔥(e_{γ_{2i−1}})

= (1 + (−1)^{d}) · 𝔥(e_{γ_{1}}) + ∑_{i=2}^{k}(1 + (−1)^{d+1}) · 𝔥(e_{γ_{2i−1}})
= 2b · ζ,

for some integer b. Since a is an odd integer this is not possible, and therefore 𝔬(g) is not a coboundary.

(2) ℓ = 1 the relation (12) implies that

a · ζ = 𝔬(g)(e_{θ}) = δ𝔥(e_{θ}) = 𝔥(∂e_{θ})
= (1 + (−1)^{d−1}ε_{1}) · 𝔥(e_{γ_{1}}) +

(1 + (−1)^{d}ε_{2} + (−1)^{d}τ_{1,2} + (−1)^{d+d}ε_{1}τ_{1,2}) · 𝔥(e_{γ_{3}}) +

∑_{i=3}^{k}(1 + (−1)^{d}τ_{i−1,i}) · 𝔥(e_{γ_{2i−1}})

= (1 + (−1)^{d−1}) · 𝔥(e_{γ_{1}}) + (1 + (−1)^{d} + (−1)^{d+1} − 1) · 𝔥(e_{γ_{3}}) +

∑_{i=3}^{k}(1 + (−1)^{d+1}) · 𝔥(e_{γ_{2i−1}})

= (1 + (−1)^{d−1}) · 𝔥(e_{γ_{1}}) + ∑_{i=3}^{k}(1 + (−1)^{d+1}) · 𝔥(e_{γ_{2i−1}})
= 2b · ζ,

for b ∈ ℤ. Again we reached a contradiction, so 𝔬(g) is not a coboundary.

(3) 2 ≤ ℓ ≤ d − 1 the relation (13) implies that

a · ζ = 𝔬(g)(e_{θ}) = δ𝔥(e_{θ}) = 𝔥(∂e_{θ})
= (1 + (−1)^{d−ℓ}ε_{1}) · 𝔥(e_{γ_{1}}) + (1 + (−1)^{d}ε_{2}) · 𝔥(e_{γ_{3}}) +

∑_{i=3}^{k}(1 + (−1)^{d}τ_{i−1,i}) · 𝔥(e_{γ_{2i−1}})

= (1 + (−1)^{d−ℓ}) · 𝔥(e_{γ_{1}}) + (1 + (−1)^{d}) · 𝔥(e_{γ_{3}}) +

∑_{i=3}^{k}(1 + (−1)^{d+1}) · 𝔥(e_{γ_{2i−1}})

= 2b · ζ,

for an integer b. Since a is an odd integer this is not possible. Again, 𝔬(g) is not a coboundary.

4.3 Proof of Theorem 1.5

Let j ≥ 1 be an integer with d = ⌈\frac{3}{2}j⌉ and ℓ = 2d − 3j ≤ 1. The proof of this theorem is done in the footsteps of the proof of Theorem 1.4. In all three cases we rely on Theorem 2.3 and prove

• the non-existence of 𝔖_{2}^{±}-equivariant map X_{d,2} ⟶ S(W_{2} ⊕ U_{2}^{⊕j}) whose restriction to X_{d,2}^{>1} is 𝔖_{2}^{±}-homotopic to ν ∘ ψ_{M}|_{X_{d,2}^{>1}} for M = (I_{1}, …, I_{j})

• by evaluating the obstruction cocycle 𝔬(g) for g = ν ∘ ψ_{M}|_{X^{(N_{2})}} on cells D_{1,1}^{+,+}(1, 2) or D_{2,1}^{+,+}(1, 2), depending on ℓ being 0 or 1, using Theorem 1.3; and then

• prove that the cocycle 𝔬(g) cannot be a coboundary, utilizing boundary formulas from Example 3.12.

4.3.1 2-bit Gray codes

In order to evaluate the obstruction cocycle 𝔬(g) on the relevant cells in the case k = 2 we need to understand (2 × 4)-Gray codes. These correspond to equipartitions of an interval I on the moment curve into four equal orthants by intersecting with two hyperplanes H_{1} and H_{2} in altogether three points of the interval. There are two such configurations: either H_{1} cuts through the midpoint of I and H_{2} separates both halves of I into equal pieces by two additional intersections, or the roles of H_{1} and H_{2} are reversed. In terms of Gray codes we can express this as follows.

Lemma 4.4. There are two different 2-bit Gray codes that start with the zero column (or any other fixed binary vector of length 2):

(\begin{matrix}0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{matrix})  and  (\begin{matrix}0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \end{matrix})

Proof. The second column of the Gray code determines the rest of the code, and there are only two choices for a bit flip.

This means that in the case k = 2 an ℓ-equiparting matrix A has a more compact representation: it is determined by the first column – a binary vector of length 2 – and j additional bits, one for each A_{i}, encoding whether the first bit flip in A_{i} is in the first or second row. These j bits cannot be chosen independently since there are restrictions imposed by the transition count.

Lemma 4.5. Let j ≥ 1 be an integer with d = ⌈\frac{3}{2}j⌉ and ℓ = 2d − 3j ≤ 1.

(1) If ℓ = 0, then the number of non-equivalent 0-equiparting matrices is equal

to

\frac{1}{2} \binom{j}{\frac{j}{2}}.

(2) If ℓ = 1, then the number of non-equivalent 1-equiparting matrices is equal

to

\binom{j}{\frac{j+1}{2}}.

Proof. We count the number of non-equivalent ℓ-equiparting matrices of the form A = (A_{1}, …, A_{j}) where A_{i} is a 2-bit Gray code. A (2 × 4)-Gray code with the first bit flip in the first row has in total two bit flips in the first row and one bit flip in the second row.

(1) Let ℓ = 0. Then 2d = 3j and consequently j has to be even. The matrix A must have transition count d in each row. Thus, half of the A_{i}’s have the first bit flip in the first row. Consequently, 0-equiparting matrices A with a fixed first column are in bijection with \frac{j}{2}-element subsets of a set with j elements. By inverting the bits in each row we can fix the first column of A to be the zero vector. Additionally, we are allowed to interchange the rows. Up to this equivalence there are \frac{1}{2} \binom{j}{j/2} such matrices.

(2) Let ℓ = 1. Then 2d = 3j + 1 and so j is odd. The matrix A must have transition count d in one row while transition count d − 1 in the remaining row. Without loss of generality we can assume that A have transition count d in the first row. Assume that r of the A_{i}’s have the first bit flip in the first row. Consequently, j − r of the A_{i}’s have the first bit flip in the second row. Now the transition count of the first row is 2r + j − r while the transition count of the second row is r + 2(j − r). The system of equations 2r + j − r = d, r + 2(j − r) = d − 1 yields that r = \frac{j+1}{2}. Therefore, up to equivalence, there are \binom{j}{r} such matrices.

4.3.2 The case ℓ = 0 ⇔ 2d = 3j

Let θ := D_{1,1}^{+,+}(1, 2), and let e_{θ} denote the related basis element of the cell θ in the top cellular chain group C_{2d+1}(X_{d,2}, X_{d,2}^{>1}) which, in this case, is equivariantly generated by θ. According to equation (16), which also holds for k = 2 as explained in Remark 4.3,

𝔬(g)(e_{θ}) = ( ∑ ±1) · ζ = a · ζ,  (18)

where ζ ∈ π_{2d+1}(S(W_{2} ⊕ U_{2}^{⊕j})) ≅ ℤ is a generator, and the sum ranges over all arrangements of two hyperplanes in relint θ that equipart M. Since θ parametrizes all arrangements H = (H_{1}, H_{2}) where orientations and order of hyperplanes are fixed, the sum in (18) ranges over all arrangements of two hyperplanes that equipart M where orientation and order of hyperplanes are fixed. Therefore, by Theorem 1.3, the number of (±1)’s in the sum of (18) is equal to the number of non-equivalent 0-equiparting matrices of size 2 × 4j. Now, Lemma 4.5 implies that the number of (±1)’s in the sum of (18) is \frac{1}{2} \binom{j}{j/2}. Consequently, integer a is odd if and only if \frac{1}{2} \binom{j}{j/2} is odd. Assume that the cocycle 𝔬(g) is a coboundary. Hence, there exists a cochain

𝔥 ∈ C_{𝔖_{2}^{±}}^{2d}(X_{d,2}, X_{d,2}^{>1} ; π_{2d}(S(W_{2} ⊕ U_{2}^{⊕j})))

with the property that 𝔬(g) = δ𝔥. The relation (11) for k = 2 transforms into

∂e_{θ} = (1 + (−1)^{d}ε_{1}) · e_{γ_{1}} + (1 + (−1)^{d}τ_{1,2}) · e_{γ_{3}}.

Thus we have that

a · ζ = 𝔬(g)(e_{θ}) = δ𝔥(e_{θ}) = 𝔥(∂e_{θ})
= (1 + (−1)^{d}ε_{1}) · 𝔥(e_{γ_{1}}) + (1 + (−1)^{d}τ_{1,2}) · 𝔥(e_{γ_{3}})
= (1 + (−1)^{d}) · 𝔥(e_{γ_{1}}) + (1 + (−1)^{d+j+1}) · 𝔥(e_{γ_{3}})
= 2b · ζ.

Consequently, 𝔬(g) is not a coboundary if and only if a is odd if and only if \frac{1}{2} \binom{j}{j/2} is odd. Having in mind the Kummer criterion stated below we conclude

that: A 𝔖_{2}^{±}-equivariant map X_{d,2} ⟶ S(W_{2} ⊕ U_{2}^{⊕j}) whose restriction to X_{d,2}^{>1} is 𝔖_{2}^{±}-homotopic to ν ∘ ψ_{M}|_{X_{d,2}^{>1}} does not exists if and only is 𝔬(g) is not a

coboundary if and only if a is an odd integer if and only if \frac{1}{2} \binom{j}{j/2} is odd if and only if j = 2^{t} for t ≥ 1.

Lemma 4.6 (Kummer [12]). Let n ≥ m ≥ 0 be integers and let p be a prime. The maximal integer k such that p^{k} divides \binom{n}{m} is the number of carries when m and n − m are added in base p.

Thus we have proved the case (ii) of Theorem 1.5. Moreover, since the primary obstruction 𝔬(g) is the only obstruction, we have proved that a 𝔖_{2}^{±}-equivariant map X_{d,2} ⟶ S(W_{2} ⊕ U_{2}^{⊕j}) whose restriction to X_{d,2}^{>1} is 𝔖_{2}^{±}-homotopic to ν ∘ ψ_{M}|_{X_{d,2}^{>1}} exists if and only if j, an even integer, is not a power of 2.

4.3.3 The case ℓ = 1 ⇔ 2d = 3j + 1

Let θ := D_{2,1}^{+,+}(1, 2), and again let e_{θ} denote the related basis element of the cell θ in the cellular chain group C_{2d}(X_{d,2}, X_{d,2}^{>1}) which, in this case, is equivariantly generated by two cells D_{2,1}^{+,+}(1, 2) and D_{1,2}^{+,+}(1, 2). Again, the equation (16) implies that

𝔬(g)(e_{θ}) = ( ∑ ±1) · ζ = a · ζ,  (19)

where ζ ∈ π_{2d+1}(S(W_{2} ⊕ U_{2}^{⊕j})) ≅ ℤ is a generator, and the sum ranges over all arrangements of k hyperplanes in relint θ that equipart M. The cell θ parametrizes all arrangements H = (H_{1}, H_{2}) where H_{1} passes through the given point on the moment curve and orientations and order of hyperplanes are fixed. Thus, the sum in (19) ranges over all arrangements of two hyperplanes that equipart M where H_{1} passes through the given point on the moment curve with order and orientation of hyperplanes being fixed. Therefore, by Theorem 1.3, the number of (±1)’s in the sum of (19) is the same as the number of nonequivalent 1-equiparting matrices of size 2 × 4j. Again, Lemma 4.5 implies that the number of (±1)’s in the sum of (19) is \binom{j}{(j+1)/2}. The integer a is odd if and only if \binom{j}{(j+1)/2} is odd if and only if j = 2^{t} − 1 for t ≥ 1. Assume that the cocycle 𝔬(g) is a coboundary. Then there exists a cochain

𝔥 ∈ C_{𝔖_{2}^{±}}^{2d−1}(X_{d,2}, X_{d,2}^{>1} ; π_{2d−1}(S(W_{2} ⊕ U_{2}^{⊕j}))) with the property that 𝔬(g) = δ𝔥. Now, the relation (12) for k = 2 transforms into

∂e_{θ} = (1 + (−1)^{d−1}ε_{1}) · e_{γ_{1}} + (1 + (−1)^{d}ε_{2} + (−1)^{d}τ_{1,2} + (−1)^{d+d}ε_{1}τ_{1,2}) · e_{γ_{3}}.

Thus, having in mind that j has to be odd, we have

a · ζ = 𝔬(g)(e_{θ}) = δ𝔥(e_{θ}) = 𝔥(∂e_{θ})
= (1 + (−1)^{d−1}ε_{1}) · 𝔥(e_{γ_{1}}) +
(1 + (−1)^{d}ε_{2} + (−1)^{d}τ_{1,2} + (−1)^{d+d}ε_{1}τ_{1,2}) · 𝔥(e_{γ_{3}})
= (1 + (−1)^{d−1}) · 𝔥(e_{γ_{1}}) + (1 + (−1)^{d} + (−1)^{d+j+1} + (−1)^{j+1}) · 𝔥(e_{γ_{3}})
= (1 + (−1)^{d−1}) · 𝔥(e_{γ_{1}}) + (1 + (−1)^{d} + (−1)^{d} + 1) · 𝔥(e_{γ_{3}})
= \begin{cases}2𝔥(e_{γ_{1}}), & d odd \\ 4𝔥(e_{γ_{3}}), & d even. \end{cases}  (20)

Now, we separately consider cases depending on parity of d and value of j.

(1) Let d be odd. Recall that a is odd if and only if j = 2^{t} − 1 for t ≥ 1. Since d = \frac{1}{2}(3j + 1) = 3 · 2^{t−1} − 1 and d is odd we have that for j = 2^{t} − 1, with t ≥ 2, the integer a is odd and consequently 𝔬(g) is not a coboundary. Thus a 𝔖_{2}^{±}-equivariant map X_{d,2} ⟶ S(W_{2} ⊕ U_{2}^{⊕j}) whose restriction to X_{d,2}^{>1} is 𝔖_{2}^{±}-homotopic to ν ∘ ψ_{M}|_{X_{d,2}^{>1}} does not exists. We have proved the case (ii) of Theorem 1.5 for t ≥ 2.

(2) Let d = 2 and j = 1 = 2^{1} − 1. Then the integer a is again odd and consequently cannot be divisible by 4 implying again that 𝔬(g) is not a coboundary. Therefore a 𝔖_{2}^{±}-equivariant map X_{2,2} ⟶ S(W_{2} ⊕ U_{2}) whose restriction to X_{2,2}^{>1} is 𝔖_{2}^{±}-homotopic to ν ∘ ψ_{M}|_{X_{2,2}^{>1}} does not exists. This concludes the proof of the case (ii) of Theorem 1.5.

(3) Let d ≥ 4 be even. Now we determine the integer a by computing local degrees deg(ν ∘ ψ_{M}|_{X^{(N_{2}+1)}} ∘ h_{θ}|_{S_{i}}); see (16) and (19). We prove, almost identically as in [3, Proof of Lem. 5.6], that all local degrees equal, either 1 or −1. That local degrees of ν ∘ψ_{M}|_{θ} are ±1 is simple to see since in a small neighborhood U in relint θ around any root λu + (1 − λ)v the test map ψ_{M}|_{θ} is a continuous bijection. Indeed, for any vector w ∈ W_{2} ⊕ U_{2}^{⊕j}, with sufficiently small norm, there is exactly one λu′ + (1 − λ)v′ ∈ U with ψ_{M}(λu′ + (1 − λ)v′) = w. Thus ψ_{M}|_{∂U} is a continuous bijection into some 3j-sphere around the origin of W_{2} ⊕ U_{2}^{⊕j} and by compactness of ∂U is a homeomorphism. Next we compute the signs of the local degrees. First we describe a neighborhood of every root of the test map ψ_{M} in relint θ. Let λu + (1 − λ)v ∈ relint θ with ψ_{M}(λu + (1 − λ)v) = 0. Consequently λ = \frac{1}{2}. Denote the intersections of the hyperplane H_{u} with the moment curve by x_{1}, …, x_{d} in the correct order along the moment curve. Similarly, let y_{1}, …, y_{d} be the intersections of H_{v} with the moment curve. In particular, x_{1} is the point q_{1} that determines the cell θ, see Lemma 3.13. Choose an ϵ > 0 such that ϵ-balls around x_{2}, …, x_{d} and around y_{1}, …, y_{d} are pairwise disjoint with the property that these balls intersect the moment curve only in precisely one of the intervals I_{1}, …, I_{j}. Pairs of hyperplanes (H_{u′}, H_{v′}) with λu′ + (1 − λ)v′ ∈ relint θ that still intersect the moment curve in the corresponding ϵ-balls parametrize a neighborhood of \frac{1}{2}u + \frac{1}{2}v. The local neighborhood consisting of pairs of hyperplanes with the same orientation still intersecting the moment curve in the corresponding ϵ-balls where the parameter λ is in some neighborhood of \frac{1}{2}. For sufficiently small ϵ > 0 the neighborhood can be naturally parametrized by the product

(\frac{1}{2} − ϵ, \frac{1}{2} + ϵ) × ∏_{i=2}^{2d}(−ϵ, ϵ),

where the first factor relates to λ, the next d − 1 factors correspond to neighborhoods of the x_{2}, …, x_{d} and the last d factors to ϵ-balls around y_{1}, …, y_{d}. A natural basis of the tangent space at \frac{1}{2}u + \frac{1}{2}v is obtained via the push-forward of the canonical basis of ℝ^{2d} as tangent space at (\frac{1}{2}, 0, …, 0)^{t}. Consider the subspace Z ⊆ relint θ that consists all points λu + (1 − λ)v associated to the pairs of hyperplanes (H_{u}, H_{v}) such that both hyperplanes intersect the moment curve in d points. In the space Z the local degrees only depend on the orientations of the hyperplanes H_{u} and H_{v}, but these are fixed since Z ⊆ relint θ. Indeed, any two neighborhoods of distinct roots of the test map ψ_{M} can be mapped onto each other by a composition of coordinate charts since their domains coincide. This is a smooth map of degree 1: the Jacobian at the root is the identity map. Let \frac{1}{2}u + \frac{1}{2}v and \frac{1}{2}u′ + \frac{1}{2}v′ be roots in Z of the test map ψ_{M} and let Ψ be the change of coordinate chart described above. Then ψ_{M} and ψ_{M} ∘ Ψ differ in a neighborhood of \frac{1}{2}u + \frac{1}{2}v just by a permutation of coordinates. This permutation is always even by the following:

Claim. Let A and B be finite sets of the same cardinality. Then the cardinality of the symmetric sum A △ B is even.

The orientations of the hyperplanes H_{u} and H_{v} are fixed by the condition that \frac{1}{2}u + \frac{1}{2}v ∈ relint θ. Thus, H_{u} and H_{v} are completely determined by the set of intervals that H_{u} cuts once. Let A ⊆ {1, …, j} be the set of indices of intervals I_{1}, …, I_{h} that H_{u} intersects once, and let B ⊆ {1, …, j} be the same set for H_{v}. Then Ψ is a composition of a multiple of A △ B transpositions and, hence, an even permutation. This means that all the local degrees (±1’s) in the sum (19) are of the same sign, and consequently a = ±\binom{j}{(j+1)/2}. Now, since d is even the equality (20) implies that

a · ζ = 4b · ζ.

Thus, if 𝔬(g) is a coboundary a is divisible by 4. In the case j = 2^{t} + 1 where t ≥ 2, and d = 3 · 2^{t−1} + 2 the Kummer criterion implies that the binomial coefficient \binom{j}{(j+1)/2} is divisible by 2 but not by 4. Hence, 𝔬(g) is not a coboundary and a 𝔖_{2}^{±}-equivariant map X_{d,2} ⟶ S(W_{2} ⊕ U_{2}^{⊕j}) whose restriction to X_{d,2}^{>1} is 𝔖_{2}^{±}-homotopic to ν ∘ ψ_{M}|_{X_{d,2}^{>1}} does not exist. This concludes the final instance (iii) of Theorem 1.5.

4.4 Proof of Theorem 1.6

We prove both instances of the Ramos conjecture Δ(2, 3) = 5 and Δ(4, 3) = 10 using Theorem 1.4. Thus in order to prove that

• Δ(2, 3) = 5 it suffices to show that the number of non-equivalent 1-equiparting matrices of size 3 × 2 · 2^{3} is odd, Proposition 4.8;

• Δ(4, 3) = 10 it suffices to show that the number of non-equivalent 2-equiparting matrices of size 3 × 4 · 2^{3} is also odd, Enumeration 4.9.

Consequently we turn our attention to 3-bit Gray codes. It is not hard to see that the following lemma holds.

Lemma 4.7. Let c_{1} ∈ {0, 1}^{3} be a choice of first column.

(i) There are 18 different 3-bit Gray codes A = (c_{1}, c_{2}, …, c_{8}) ∈ {0, 1}^{3×8} that start with c_{1}. They have transition counts (3, 2, 2), (3, 3, 1), or (4, 2, 1).

(ii) There are 3 equivalence classes of Gray codes that start with with c_{1}. The three classes can be distinguished by their transition counts.

Proof. (i): Starting at a given vertex of the 3-cube, there are precisely 18 Hamiltonian paths. This can be seen directly or by computer enumeration. (ii): Follows directly from (i), as all equivalence classes have size 6: If c_{1} = (0, 0, 0)^{t} then all elements in a class are obtained by permutation of rows. For other choices of c_{1}, they are obtained by arbitrary permutations of rows followed by the “correct” row bit-inversions to obtain c_{1} in the first column.

Proposition 4.8. There are 13 non-equivalent 1-equiparting matrices that are of size 3 × (2 · 2^{3}).

Proof. Let A = (A_{1}, A_{2}) be a 1-equiparting matrix. This means that both A_{1} and A_{2} are 3-bit Gray codes and the last column of A_{1} is equal to the first column of A_{2}. In addition, the transition counts cannot exceed 5 and must sum up to 14. Having in mind that A is a 1-equiparting matrix it follows that A must have transition counts {5, 5, 4}. Hence two of its rows must have transition count 5 and one row must have transition count 4. In the following a realization of transition counts is a Gray code with the prescribed transition counts. Since we are counting 1-equiparting matrices up to equivalence we may fix the first column of A, and hence first column of A_{1}, to be (0, 0, 0)^{t} and choose for A_{1} one of the matrices from each of the 3 classes of 3-bit Gray codes described in Lemma 4.7(ii). If A_{1} has transition counts (3, 2, 2), i.e., the first row has transition count 3 while remaining rows have transition count 2, then its last column is (1, 0, 0)^{t}. The next Gray code A_{2} in the matrix a can have transition counts (2, 3, 2), (2, 2, 3), or (1, 3, 3), each having 2 realizations A_{2}, each with first column (1, 0, 0)^{t}. If A_{1} has transition (3, 3, 1), then its last column is (1, 1, 0)^{t}. The Gray code A_{2} can have transition counts (2, 2, 3), having 2 realizations, or (1, 2, 4), having 1 realization, or (2, 1, 4), having 1 realization, each with first column (1, 1, 0)^{t}. If A_{1} has transition counts (4, 2, 1), then its last column is (0, 0, 1)^{t}. The Gray code A_{2} can have transition counts (1, 2, 4), having 1 realization, or (1, 3, 3), having 2 realizations, each with first column (0, 0, 1)^{t}. In total we have 6 + 4 + 3 = 13 non-equivalent 1-equiparting matrices A = (A_{1}, A_{2}).

Enumeration 4.9. There are 2015 non-equivalent 2-equiparting matrices that are of size 3 × 4 · 2^{3}.

Proof. Using Lemma 4.7 we enumerate non-equivalent 2-equiparting matrices by computer. Let A = (A_{1}, A_{2}, A_{3}, A_{4}) be a 2-equiparting matrix. It must have transition counts {10, 10, 8}. Similarly as above, A is constructed by fixing the first column to be (0, 0, 0)^{t} and A_{1} to be one representative from each of the 3 classes of Gray codes. Then all possible Gray codes for A_{2}, A_{3}, A_{4} are checked, making sure that the last column of A_{i} is equal to the first column of A_{i+1} and that the transition counts of A_{1}, …, A_{4} sum up to {10, 10, 8}. This leads to 2015 possibilities.

This concludes the proof of Theorem 1.6.

Remark 4.10. By means of a computer we were able to calculate the number N(j, k, d) of non-equivalent ℓ-equiparting matrices for several values of j ≥ 1 and k ≥ 3, where d = ⌈\frac{2^{k}−1}{k}j⌉ and ℓ = dk − (2^{k} − 1)j. See Table 1.

Number N(j, k, d) of non-equiv ℓ-equiparting matrices given j ≥ 2, and k ≥ 3.

j  k  ℓ  d  N(j, k, d)
2  3  1  5  13
3  3  0  7  60
4  3  2  10  2015
5  3  1  12  35040
6  3  0  14  185130
7  3  2  17  7572908
8  3  1  19  132909840
9  3  0  21  732952248
1  4  1  4  16
2  4  2  8  37964

Table 1: Number N(j, k, d) of non-equivalent ℓ-equiparting matrices given j ≥ 2 and k ≥ 3, where d = ⌈ \frac{2^{k}−1}{k} j⌉ and ℓ = dk − (2^{k} − 1)j.

References

[1] David Avis, Non-partitionable point sets, Inform. Process. Letters 19 (1984), no. 3, 125–129.

[2] Anders Björner and Günter M. Ziegler, Combinatorial stratification of complex arrangements, J. Amer. Math. Soc. 5 (1992), 105–149.

[3] Pavle V. M. Blagojević, Florian Frick, Albert Haase, and Günter M. Ziegler, Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem, Preprint, 27 pages, February 2015; arXiv:1502.02975.

[4] Pavle V. M. Blagojević, Wolfgang Lück, and Günter M. Ziegler, Equivariant topology of configuration spaces, J. Topology 8 (2015), 414–456.

[5] Pavle V. M. Blagojević and Günter M. Ziegler, The ideal-valued index for a dihedral group action, and mass partition by two hyperplanes, Topology Appl. 158 (2011), no. 12, 1326–1351.

[6] , Convex equipartitions via equivariant obstruction theory, Israel J. Math. 200 (2014), 49–77.

[7] Tammo tom Dieck, Transformation Groups, Studies in Mathematics, vol. 8, Walter de Gruyter, Berlin, 1987.

[8] Aleksandra S. Dimitrijević Blagojević, A mass partition problem in R^{4}, Mat. Vesnik 61 (2009), 61–69.

[9] Ralph Fox and Lee Neuwirth, The braid groups, Math. Scandinavica 10 (1962), 119–126.

[10] Branko Grünbaum, Partitions of mass-distributions and of convex bodies by hyperplanes, Pacific J. Math. 10 (1960), no. 4, 1257–1261.

[11] Hugo Hadwiger, Simultane Vierteilung zweier Körper, Arch. Math. 17 (1966), no. 3, 274–278.

[12] Ernst E. Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math. 44 (1852), 93–146.

[13] Peter Mani-Levitska, Siniša Vrećica, and Rade T. Živaljević, Topology and combinatorics of partitions of masses by hyperplanes, Adv. Math. 207 (2006), no. 1, 266–296.

[14] Enrique Outerelo and Jesús M. Ruiz, Mapping degree theory, vol. 108, American Mathematical Society, 2009.

[15] Edgar A. Ramos, Equipartition of mass distributions by hyperplanes, Discrete Comput. Geom. 15 (1996), no. 2, 147–167.

[16] Siniša Vrećica and Rade T. Živaljević, A proof of an equipartition result of Ramos, Preprint, 8 pages, August 6, 2015; arXiv:1508.01552v1.

[17] Rade T. Živaljević, Computational topology of equipartitions by hyperplanes, Top. Meth. Nonlinear Analysis 45 (2015), 63–90.

Pavle V. M. Blagojević Math. Institut SANU Knez Mihailova 36 11001 Beograd Serbia and Institute of Mathematics Freie Universität Berlin Arnimallee 2 14195 Berlin Germany pavleb@mi.sanu.ac.rs Florian Frick Department of Mathematics Cornell University Ithaca NY 14853 USA ff238@cornell.edu

Albert Haase Institute of Mathematics Freie Universität Berlin Arnimallee 2 14195 Berlin Germany a.haase@fu-berlin.de Günter M. Ziegler Institute of Mathematics Freie Universität Berlin FU Berlin Arnimallee 2 14195 Berlin Germany ziegler@math.fu-berlin.de 772

Documenta Mathematica 21 (2016)