Borsuk–Ulam theorem, ham–sandwich theorem, mass partition problem.

1 Introduction↩︎

In this section, we review and formulate the main results of the present paper. Section 2 presents necessary results concerning equivariant cobordisms and proves Borsuk–Ulam-type theorems for products of spheres and Stiefel manifolds. Section 3 discusses conditions imposed on \(k\) hyperplanes in \(\mathbb{R}^d\) under which any subset of \(n\) such hyperplanes partitions each of \(m\) measures into \(2^n\) equal parts. Section 4 proves the main theorem on orthogonal mass partitions.

1.1 Borsuk–Ulam theorems for spheres and Stiefel manifolds.↩︎

In Section 2 we consider Borsuk–Ulam type (BUT) theorems for \(G\)–manifolds. In our opinion, the most useful tool for BUT–manifolds is equivariant cobordism theory, which goes back to the work of Conner and Floyd in the early 1960s [1]. In terms of equivariant cobordism theory, we obtained Theorems 1 and 3 in [2], see Theorems 9 and 10 in this paper. We applied these theorems to prove the BUT–theorem with \(G=(\mathbb{Z}/2)^k\) (Theorem 12 ). Here we formulate two Borsuk-Ulam type theorems for the product of spheres and Stiefel manifolds which follow from Theorem 12.

Let \(G=({\Bbb Z}/2)^k={\Bbb Z}/2\times\ldots\times{\Bbb Z}/2\). The group has \(k\) generators (\(\lambda_1=(1,0,...,0),...,\lambda_k=(0,...,0,1)\)) of order 2. Then each element \(q\in G\) can be represented in the form \[q=\varepsilon_1\lambda_1+...+\varepsilon_k\lambda_k \in G, \quad \varepsilon_i \in \mathbb{F}_2, \,i.e.\, \varepsilon_i =0, 1.\] It is well known that every irreducible linear representation of \(G\) is one–dimensional and to every \(q \in G\) corresponds an irreducible representation \(\rho_q: G \to \mathbb{R}_q\), where \(\rho_q(\lambda_i)(x)=-x\) if \(\varepsilon_i =1\) and \(\rho_q(\lambda_i)(x)=x\) otherwise. Here \(x \in \mathbb{R}_q\).

Let the action of the group \(({\Bbb Z}/2)^k\) on \({\Bbb S}^{i_1}\times\ldots\times{\Bbb S}^{i_k}=\{(v_1,...,v_k)\,|\, v_\ell\in {\Bbb S}^{i_\ell}, \; \ell=1,...,k\}\) be defined for all \(q=\varepsilon_1\lambda_1+...+\varepsilon_k\lambda_k \in G\) as \(q(v_1,...,v_k)=((1-2\varepsilon_1)v_1, ...,(1-2\varepsilon_k)v_k).\)

Let \[\mathcal{P}(i_1,...,i_k):= \mathbb{F}_2[a_1,...,a_k]/(a_1^{i_1+1},...,a_k^{i_k+1}).\] In other words, \(\mathcal{P}(i_1,...,i_k)\) is the group ring \(\mathbb{F}_2(C_{i_1+1}\times...\times C_{i_k+1})\), where \(C_n\) is a cyclic group of order \(n\).

A special case of this theorem, utilizing \(G\)–cobordisms, was proved in [2]. The cohomological theory of the \(G\)–index is used for theorems of this kind in [3]–[11], as well as in many other papers. In fact, in Theorem 1, instead of a product of spheres, one can take a manifold that is \(G\)–cobordant to a product of spheres (see Section 2); this significantly expands the class of manifolds.

Many results, such as the upper bounds in [8], obtained using the \(G\)–index technique, can be deduced from Theorem 1. In that case, the proofs reduce to an algebraic exercise involving polynomials over \(F_2\) and do not require complex calculations (see Section 4).

The Stiefel manifold \(V_{n,k}\) is the set of all orthonormal \(k\)–frame \((u_1,...,u_k)\) in \(\mathbb{R}^n\), i.e. \[V_{n,k}:=\{(u_1,...,u_k)\in ({\mathbb{S}}^{n-1})^k ={\mathbb{S}}_1^{n-1}\times...\times {\mathbb{S}}_k^{n-1}\,|\, u_i\cdot u_j=0 \;for all\; 1\le i<j\le k\}\] \[=\{(u_1,...,u_k)\in ({\mathbb{S}}^{n-1})^k \,|\, u_i\cdot u_1=0, ..., u_i\cdot u_{i-1}=0 \;for all\; 1<i\le k\}.\] This definition yields that the dimension of \(V_{n,k}\) is \[n-1+n-2+...+n-k=nk-k(k+1)/2.\] Let \(G=({\Bbb Z}/2)^k\) with generators \(\lambda_1,\ldots,\lambda_k\) acting on \(V_{n,k}\) by \[\lambda_j(u_1, . . . ,u_j , . . . , u_k) = (u_1, . . . , -u_j , . . . , u_k), \quad j=1,...,k.\]

Theorem 1.1 in [5] is a particular case of Theorem 2. In this case \[m= \dim V_{n,k}=nk-k(k+1)/2, \qquad \mathbb{R}^m_\rho=(\mathbb{R}_{\lambda_1})^{n-1}\oplus \cdot\cdot\cdot \oplus (\mathbb{R}_{\lambda_k})^{n-k}.\]

1.2 Orthogonal mass partition.↩︎

The well-known ham–sandwich theorem states:

This theorem was proposed by Steinhaus and proved by Banach, for details see [12]. Stone & Tukey [13] proved the \(d\)–dimensional version of the theorem in a more general setting involving measures.

Mass partition theorems are usually stated in one of two settings: discrete or continuous. The continuous versions deal with measures in \(\mathbb{R}^d\). In this paper we assume that all measures are finite absolutely continuous with respect to the Lebesgue measure or, see [14], they are finite Borel measures such that every hyperplane has measure 0. (A measure \(\mu\) on \(\mathbb{R}^d\) is called finite if \(0<\mu(\mathbb{R}^d)<\infty\).)

We say that a hyperplane \(H\) bisects \(\mu\) (or divides \(\mu\) in half ) if \[\mu(H^+)=\frac{1}{2}\,\mu(\mathbb{R}^d),\] where \(H^+\) denotes one of the half–spaces defines by \(H\).

Let \(\mu_1,...,\mu_d\) be measures on \(\mathbb{R}^d\). Then there exists a hyperplane that simultaneously bisects all \(d\) measures.

A discrete version of this theorem states as follows, see [14]:

Let \(X_1,...,X_d\) be finite sets in \(\mathbb{R}^d\). Then there exists a hyperplane that simultaneously bisects \(X_1,...,X_d\).

Let \(\Delta(m,k)\) denote the minimal dimension \(d\) of Euclidean space such that for any set of \(m\) (finite absolutely continuous) measures in \(\mathbb{R}^d\) there exist \(k\) hyperplanes in \(\mathbb{R}^d\) that divide each of the \(m\) measures into \(2^k\) parts of equal size. There are lower and upper bounds for this number: \[\left\lceil{\left(\frac{2^k-1}{k}\right)m}\right\rceil \le \Delta(m,k) \le m+(2^{k-1}-1)2^{\lfloor \log_2 m \rfloor} \eqno (1.1)\] The lower bound was proved in 1996 by Ramos [15], and this upper bound was obtained in 2006 by Mani-Levitska, Vrećica, and Živaljević [8]. The only instance in which lower and upper bounds coincide is in the case when \(k=1\) or \(k = 2\) and \(m = 2^j-1\), \(j=1,2,...\)

Consider the case when the hyperplanes are mutually orthogonal. For a plane, this fact is well known, see [16]:

Given one finite area, two–dimensional pancake. Then there exists two perpendicular straight lines that cut the area of the pancake into four equal pieces.

Let \(\Delta^*(m,k)\) denote the minimal dimension \(d\) of Euclidean space such that for any set of \(m\) measures in \(\mathbb{R}^d\) there exist \(k\) mutually orthogonal hyperplanes in \(\mathbb{R}^d\) that divide each of the \(m\) measures into \(2^k\) parts of equal size. The following theorem generalizes (1.1):

It is clear that \(\Delta^*(m,k)\ge \Delta(m,k)\), however the upper bounds in (1.2) and (1.1) are the same.

Note that the bound in case (i) is also tight for (1.1). Let’s explain what’s happening. For \(k=2\) the lower bound in (1.1), \(b_1=\lceil y\rceil\), \(y=3m/2\). In (1.2) we have \(b_2=\lceil y+1/2\rceil\). If \(m\) is odd, then \(b_1=b_2=(3m+1)/2\).

Actually, Theorem 3 is a particular case of a more general theorem. Let \(\ell\ge1\) and \[\alpha_\ell(j):=\sum\limits_{i=1}^\ell { j \choose i}, \qquad \beta_\ell(j):=\sum\limits_{i=0}^{\ell-1} {j-1 \choose i}, \;where\; {0 \choose 0}=1, \; {s \choose i}=0, \, s<i.\]

Let \(1\le n \le k\) and \(\Delta^*(m,k,n)\) denote the minimal dimension \(d\) of Euclidean space such that for any set of \(m\) finite measures in \(\mathbb{R}^d\) there exist \(k\) mutually orthogonal hyperplanes in \(\mathbb{R}^d\) such that any \(n\) of these \(k\) hyperplanes divide each of the m measures into \(2^n\) parts of equal size.

Note that this quantity—without the orthogonality condition—was first considered in [17]. Recently, in [18], some upper bounds for \(\Delta^*(m,k,n)\) were obtained for \(n = 2\) and 3.

The main result of this paper regarding orthogonal mass partitioning is the following theorem.

It is easy to see that \[\alpha_k(k)=2^k-1, \quad \beta_k(k)=2^{k-1}, \quad \Delta^*(m,k,k)= \Delta^*(m,k).\] If \(n=k\) then (1.3) is equal to (1.2), i.e. Theorem 4 yields Theorem 3.

Let \(n=2\). Since \(\alpha_2(k)=k(k+1)/2\) and \(\beta_2(k)=k\), so by (1.3) we have \[\left\lceil{\frac{m(k+1)+k-1}{2}}\right\rceil \le \Delta^*(m,k,2) \le m+(k-1)\,2^{\lfloor \log_2 m \rfloor} \eqno(1.4)\]

It is easy to see that if \(m=2^j-1\), \(j\ge 1\), then the lower bound (1.4) is equal to the upper, which implies the following theorem.

In the case \(j=1\), i.e. \(m=1\), we have \(\Delta^*(1,k,2)=k\).

This fact is contained in Makeev’s paper [19]. However, in our opinion, this statement has not proven there.

These theorems have versions involving additional equivariant constraints—for instance, when the hyperplanes pass through a given set of points (see Section 3). Here is one possible generalization of Theorem 1.4.

It is easy to see that the analogue of Theorem 5 is the following statement.

1.3 Algorithms for mass partitioning.↩︎

In discrete versions of mass-partitioning results, the task involves partitioning several finite families of points in \(\mathbb{R}^d\) in a prescribed manner. If the total number of points is \(N\), it is desirable to have an algorithm for finding such a partition whose running time is expressed in terms of \(N\).

In two dimensions a ham–sandwich cut is a line \(h\) that bisects \(X_1\) and \(X_2\) with \(N\) points in total. Edelsbrunner and Waupotitsch [20] find an algorithm that can compute \(h\) in time \(O(N\log{N})\). Finally, Lo, Matoušek, and Steiger [21] proved that in the plane ham–sandwich cut can be computed in \(O(N)\) time. The paper also presents polynomial algorithms for finding ham–sandwich cuts in every dimension \(d > 1\).

Previously known algorithm for the pancake theorem is discovered in [22] and has \(O(N \log N)\) time complexity. Recently, we improve this result:

[23]. For any set of \(N\) points \(P\) in the plane, a partition of \(P\) by two orthogonal lines into four equal parts can be found in optimal time, linearly dependent on \(N\), i.e. in \(\Theta(N)\) time.

In [23] we also proved that the computational complexity of the discrete versions of Theorem 4 (the case where \(n = k = 2\)) and Corollary 6 is polynomial. However, the algorithms proposed in [23] are not optimal. An interesting problem is finding efficient and optimal algorithms for the orthogonal partitioning of masses for arbitrary parameters \(m, k\), and \(n\).

I would like to thank Pavle Blagojević, Florian Frick, Roman Karasev, Pablo Soberon, and Rade Živaljević for the helpful discussions, valuable comments, and useful references.

2 Borsuk–Ulam type theorems↩︎

In this section we deal with \(G\)–BUT manifolds, where \(G=({\Bbb Z}/2)^k\), using the theory of equivariant cobordism. Let \(m\ge n\), we say that a \(G\)–manifold \(M^m\) is BUT (Borsuk–Ulam type) if for any continuous equivariant \(f: M^m\to {\Bbb R}^n\) the set of zeros \(Z_f:=f^{-1}(0)\) is not empty. The BUT–manifolds and spaces we considered in [2], [9], [24], [25].

2.1 \(G\)–BUT manifolds and equivariant cobordisms.↩︎

Consider closed (compact and without boundary) PL manifolds with an \(H\)-structure, such as unoriented, oriented, complex, etc. One can define a “cobordism with \(H\)-structure”, but there are various technicalities. In each particular case, cobordism is an equivalence relation on manifolds. A basic question is to determine the equivalence classes for this relationship, called the cobordism classes of manifolds. These form a graded ring called the cobordism ring \(\Omega^H_*\), with grading by dimension, addition by disjoint union, and multiplication by cartesian product.

Let \({\Omega}_*^H(G)\) denote the PL cobordism group with \(H\)-structure of free simplicial actions of a finite group \(G\). Let \(\rho:G\to \mathop{\rm GL}\nolimits(n,{\Bbb R})\) be a representation of a group \(G\) on \({\Bbb R}^n\) which also has \(H\)-structure. [2] Lemma 2.4 shows that for a generic simplicial equivariant map \(f: M^m\to{\Bbb R}^n\), \(m\ge n\), the cobordism class of the manifold \(Z_f\) is uniquely defined up to cobordism and so well defines a homomorphism \[\mu_{\rho}^G:\Omega_m^H(G)\to \Omega_{m-n}^H(G). \eqno (2.1)\]

Note that this homomorphism depends only on a representation \(\rho\) of a group \(G\) on \({\Bbb R}^n\). The invariant \(\mu_{\rho}^G\) is an obstruction for the existence of equivariant maps \(f: M\to {\Bbb R}^n\setminus \{0\}\).

Namely, we proved the following theorem [2].

In the case \(m=n\) the dimension of \(\Omega_{m-n}^H(G)\) is 0. In [2] we defined an invariant \(\deg_G(f) \in \mathbb{Z}_2\). In this case, condition \(\mu_{\rho}^G([M,\tau])\ne 0\) in the theorem can be replaced by \(\deg_G(f)=1\), see [2]. Given a finite group \(G\) acting free on a closed PL-manifold \(M^n\) and acting linearly on \({\Bbb R}^n\) with \(({\Bbb R}^n)^G=\{0\}\). Let \(f: M^n\to {\Bbb R}^n\) be a continuous equivariant transversal to zeros map. Since \(Z_f\) is a finite free \(G\)-invariant subset of \(M\), we have \(|Z_f|=k\,|G|\), where \(k\ge0\) is integer. Set \(\deg_G(f)=1\) if \(k\) is odd, and \(\deg_G(f)=0\) if \(k\) is even. The following theorem can be easily derived from Theorem 1 in our paper [2].

2.2 BUT – theorem for \(G={\Bbb Z}/2\).↩︎

Let \(H=O\) (unoriented cobordisms). The set of cobordism classes of closed unoriented \(n\)–dimensional manifolds is usually denoted by \(\mathfrak N_n\) (\(=\Omega_n^O\)). In 1954 René Thom proved \[\mathfrak N_*=\bigoplus\limits_{n\ge0}{\mathfrak N_n}=\mathbb{F}_2[x_k\,|\, k\ge1,\, k\ne 2^i-1]\]

Let \(G={\Bbb Z}/2\). We denote by \({\mathfrak N}_*({\Bbb Z}/2)\) the unoriented cobordism module of free involutions. Actually, \({\mathfrak N}_*({\Bbb Z}/2)\) is a free \({\mathfrak N}_*\)-module with basis \([{\Bbb S}^n,A]\), \(n\ge0\), where \([{\Bbb S}^n,A]\) is the cobordism class of the antipodal involution on the \(n\)–sphere [1]. Thus, every manifold \(M^m\) with a free involution \(T\) can be uniquely represented in \({\mathfrak N}_m({\Bbb Z}/2)\) in the form: \[[M,T]=\sum\limits_{k=0}^m {[V_k][{\Bbb S}^{m-k},A]}, \; V_k \in {\mathfrak N}_k.\]

Let \(\nu\) be the 1–dimensional linear representation of \({\Bbb Z}/2\) defined by \(\nu(x)=-x\), \(x\in \mathbb{R}\). In this case \(\mu_{\nu}^{{\Bbb Z}_2}=\Delta_\nu=\Delta\), where \[\Delta:{\mathfrak N}_k({\Bbb Z}/2) \to {\mathfrak N}_{k-1}({\Bbb Z}/2)\] is the Smith homomorphism, and if \[\mathbb{R}^n_\rho= \mathbb{R}_{\nu}\oplus \cdot\cdot\cdot \oplus \mathbb{R}_{\nu}, \;i.e.\; \rho=(\nu,...,\nu), \; \rho(u)=-u, \; u\in \mathbb{R}^n,\] then \(\mu_{\rho}^{{\Bbb Z}_2}=\Delta^n\) [1]. This fact yields, see Lemma 5.1 [2], the following equality \[\mu_{\rho}^{{\Bbb Z}/2}([M^m,T])=\Delta^n\left(\sum\limits_{k=0}^m {[V_k]\,[{\Bbb S}^{m-k},A]}\right)= \sum\limits_{k=0}^{m-n} {[V_k]\,[{\Bbb S}^{m-n-k},A]}.\]

Our generalization of the classical Borsuk–Ulam theorem is Theorem 2 from [2].

The class of BUT manifolds is very wide. For instance, “half” of two-dimensional oriented manifolds are \({\Bbb Z}/2\)–cobordant to \([\mathbb{S}^2,A]\), namely, any \([M_g^2,T]\), where the genus \(g\) is even and \(T\) is a free involution, is \({\Bbb Z}/2\)–cobordant to \([\mathbb{S}^2,A]\).

2.3 \(({\Bbb Z}/2)^k\)–cobordisms.↩︎

Let \(G=({\Bbb Z}/2)^k={\Bbb Z}/2\times\ldots\times{\Bbb Z}/2\). In this case, see [1], we have \[{\mathfrak N}_*(({\Bbb Z}/2)^k)={\mathfrak N}_*({\Bbb Z}/2)\otimes\ldots\otimes{\mathfrak N}_*({\Bbb Z}/2). \eqno (2.2)\] Equivalently, \({\mathfrak N}_*(({\Bbb Z}/2)^k)\) is a free \({\mathfrak N}_*\)-module with generators \(\{\gamma_{i_1}\otimes\ldots\otimes{\gamma_{i_k}}\}\), where \(i_1,\ldots,i_k\) are non–negative integers and \(\gamma_i:=[{\Bbb S}^{i},A]\in {\mathfrak N}_i({\Bbb Z}/2)\).

Let \(\Gamma(i_1,...,i_k)\) denote the generator \(\gamma_{i_1}\otimes\ldots\otimes{\gamma_{i_k}}\) in \({\mathfrak N}_*(({\Bbb Z}/2)^k)\), i.e. that is \([M]_G\), where \(M={\Bbb S}^{i_1}\times\ldots\times{\Bbb S}^{i_k}\) with a group action by \(\lambda_\ell(x)=-x, \, x\in {\Bbb S}^{i_\ell}\subset {\Bbb R}^{i_\ell+1}\), \(\ell=1,...,k\). .

Let \(\rho_q: G \to \mathbb{R}_q\) be an irreducible 1–dimensional linear representation of \(G\) and \(\Delta_q:=\mu^G_{\rho_q}\). Then by (2.1) we have a homomorphism \[\Delta_q:{\mathfrak N}_m(({\Bbb Z}/2)^k) \to {\mathfrak N}_{m-1}(({\Bbb Z}/2)^k).\] Let us denote \[a_i:= \Delta_{\lambda_i}, \quad i=1,...,k.\] It is not hard to see that (2.1), Theorem 11(c), and (2.2) yield the following lemmas

2.4 General BUT – theorem for \(G=({\Bbb Z}/2)^k\).↩︎

The following theorem follows directly from Theorem 9 and Lemma 4.

2.5 Borsuk–Ulam theorem for the product of spheres.↩︎

Let \(q=\varepsilon_1\lambda_1+...+\varepsilon_k\lambda_k \in G=({\Bbb Z}/2)^k,\) \[S(i_1,...,i_k):={\Bbb S}^{i_1}\times\ldots\times{\Bbb S}^{i_k}=\{(v_1,...,v_k)\,|\, v_\ell\in {\Bbb S}^{i_\ell}, \; \ell=1,...,k\},\] \[q(v_1,...,v_k)=((1-2\varepsilon_1)v_1, ...,(1-2\varepsilon_k)v_k).\]

Lemma 3 implies the following fact:

2.6 Borsuk–Ulam type theorems for Stiefel manifolds.↩︎

The Stiefel manifold \[V_{n,k}=\{(u_1,...,u_k)\in ({\mathbb{S}}^{n-1})^k \,|\, u_i\cdot u_1=0, ..., u_i\cdot u_{i-1}=0 \;for all\; 1<i\le k\}\] fit into a family of fiber bundles; for their sequential construction, they can be represented as a tower of fiber bundles. The first unit vector \(u_1\) lies in \(\mathbb{S}^{n-1}\). Once we have chosen this first vector, the remaining \(k-1\) vectors must be orthonormal to it. This means they must all lie in the \((n-1)\)-dimensional orthogonal complement of the first vector. This gives us the projection map: \[p: V_{n,k} \longrightarrow \mathbb{S}^{n-1}\] where \(p\) takes a \(k\)–frame and retains only the first vector. The fiber of this projection (the space of “remaining choices”) is \(V_{n-1,k-1}\). We can repeat this logic recursively. By successively discarding one vector at a time, we obtain a sequence of nested bundles. \[V_{n-1,k-1} \longrightarrow V_{n,k} \longrightarrow \mathbb{S}^{n-1}.\] \[V_{n-2,k-2} \longrightarrow V_{n-1,k-1} \longrightarrow \mathbb{S}^{n-2}\] ... and so on, until we reach \(V(n-k+1,1)\), which is just the sphere \(\mathbb{S}^{n-k}\). In short, the Stiefel manifold is “built” by attaching spheres of decreasing dimensions (\(\mathbb{S}^{n-1}, \mathbb{S}^{n-2}, ...,\mathbb{S}^{n-k})\) to one another through these fiber bundle relations. Thus, \(u_1\in \mathbb{S}^{n-1}\), \(u_2 \in \mathbb{S}^{n-2}\), ..., \(u_k \in \mathbb{S}^{n-k}\).

Let \(G=({\Bbb Z}/2)^k\) with generators \(\lambda_1,\ldots,\lambda_k\) acting on \(V_{n,k}\) by \[\lambda_j(u_1, . . . ,u_j , . . . , u_k) = (u_1, . . . , -u_j , . . . , u_k), \quad j=1,...,k.\]

3 Equipartition of measures: functions \(g_\mu\)↩︎

3.1 Hyperplanes in \(\mathbb{R}^d\)↩︎

We represent hyperplanes in \(\mathbb{R}^d\) as points in \(\mathbb{S}^d\). Let \(v = (t_0, t_1, . . . , t_d)\) be a point (unit vector) in the unit sphere \(\mathbb{S}^d \subset \mathbb{R}^{d+1}\). If at least one of the components \(t_1, . . . , t_d\) is nonzero, we assign to the point \(v\) a hyperplane \(H_0(v)\) in \(\mathbb{R}^d\). Let \[H_0(v):=\{(x_1,...,x_d)\in \mathbb{R}^d: t_1x_1+...+t_dx_d=t_0\}.\] \[H(v):=\{(x_1,...,x_d)\in \mathbb{R}^d: t_1x_1+...+t_dx_d\le t_0\},\] then half–spaces \(H(v)\) and \(H(-v)\) are bounded by \(H_0(v)\). For \(v=\pm e_0\), \(e_0:=(1,0,...,0)\), \(H_0(v)\) is not defined, but we have \[H(e_0)= \mathbb{R}^d, \quad H(-e_0)= \emptyset.\] We are interested in hyperplanes that bisect finite measures in \(\mathbb{R}^d\), i.e. \(\mu(H(v))=\mu(H(-v))\), this cannot happen when \(v=\pm e_0\), so this case can be ignored. Then, for any set of unit vectors \(v_1,...,v_k\), \(v_i=(t_{i0},t_{i1},...,t_{ik})\ne\pm e_0\), in \(\mathbb{S}^d \subset \mathbb{R}^{d+1}\) we have a corresponding set of hyperplanes \(H_0(v_1),..., H_0(v_k)\) in \(\mathbb{R}^d\). Thus, \((v_1,...,v_k) \in S_{d,k}\).

3.2 Function \(g_\mu\).↩︎

Let \(\mathop{\boldsymbol{v}}\nolimits=\{v_1,...,v_n\} \in S_{d,n}:=(\mathbb{S}^d)^n=S(d,...,d)\), \(\mathop{\boldsymbol{s}}\nolimits=\{s_1,...,s_n\}\) be a vector of signs, i.e. \(s_i\) is \(+1\) or \(-1\), \(i=1,...,n\), and \[H(\mathop{\boldsymbol{v}}\nolimits,\mathop{\boldsymbol{s}}\nolimits):= \bigcap\limits_{j=1}^n{H(s_jv_j)}.\]

Let \(\mu\) be a finite measure on \(\mathbb{R}^d\). We denote by \(r(\mathop{\boldsymbol{s}}\nolimits)\) the number of negative \(s_i\) in \(\mathop{\boldsymbol{s}}\nolimits\), \[g^{(n)}_\mu(\mathop{\boldsymbol{v}}\nolimits)=g_\mu(\mathop{\boldsymbol{v}}\nolimits):=\sum\limits_{\mathop{\boldsymbol{s}}\nolimits\in C^n} {(-1)^{r(\mathop{\boldsymbol{s}}\nolimits)}\mu(H(\mathop{\boldsymbol{v}}\nolimits,\mathop{\boldsymbol{s}}\nolimits))}, \quad C^n:=(\{-1,+1\})^n.\]

Let \(G=({\Bbb Z}/2)^n\), \(\lambda_1,..., \lambda_n\) are generators of \(G\), and \(\omega_n:=\lambda_1+...+\lambda_n \in G\). The next lemma follows easily from the definition of \(g^{(n)}_\mu(\mathop{\boldsymbol{v}}\nolimits)\).

Note that Lemma 7 contains \(2^n-1\) independent equations. Now we consider an extension of this lemma.

Repeated application of the Lemma 9 leads to the following theorem:

3.3 Additional constraints in Theorem 13.↩︎

Let \(p=(x_1,...,x_d)\) be a point in \(\mathbb{R}^d\), \(v=(t_0,t_1,...,t_d)\in \mathbb{S}^d\), and \[g_p(v):=t_0-(t_1x_1+...t_dx_d).\] Then \(g_p(-v)=-g_p(v)\), i.e. \(g_p\) is an equivariant function. If \(g_p(v)=0\), then \(H_0(v)\) passes through the point \(p\) in \(\mathbb{R}^d\). Therefore, if \(S=\{p_1,...,p_\ell\}\) then equations \[g_{p_i}(v_j)=0,\; i=1,...,\ell, \; j=1,...,k, \eqno (3.3)\] yield that all hyperplanes \(H_0(v_1),...,H_0(v_k)\) pass through \(S\).

Another set of equivariant constraints arises when the hyperplanes are required to be mutually orthogonal.

4 Proof of the theorem on orthogonal partitions↩︎

Let \(1\le j \le n \le k\) \[Q_{k,j}(a_1,...,a_k):=\prod_{ \varepsilon_{1}+...\varepsilon_{k}=j} {(\varepsilon_{1}a_1+...+\varepsilon_{k}a_{k})}, \,where all\, \varepsilon_{i}=1or\, 0.\] \[P_{k,n}(a_1,...,a_k):=\prod_{j=1}^n {Q_{k,j}(a_1,...,a_k)}.\] Then \(Q_{k,1}=a_1...a_k, \; Q_{k,2}=(a_1+a_2)...(a_1+a_k)...(a_{k-1}+a_k),....\) It is clear that \[\deg Q_{k,j} = {k \choose j}, \quad \deg P_{k,n} =\deg Q_{k,1}+...+\deg Q_{k,n} = \alpha_n(k). \eqno(4.1)\]

O. R. Musin, University of Texas Rio Grande Valley, School of Mathematical and Statistical Sciences, One West University Boulevard, Brownsville, TX, 78520, USA.

E-mail address: oleg.musin@utrgv.edu

References↩︎