A Topological Characterization of Modulo-$p$ Arguments and Implications for Necklace Splitting
Aris Filos-Ratsikas Alexandros Hollender Katerina Sotiraki Manolis Zampetakis
cs.CC cs.CG cs.DM



Towards Better Opioid Antagonists Using Deep Reinforcement Learning
    
 Jianyuan Deng, M.Phil.^*1, Zhibo Yang, M.Phil.^*2, Yao Li, B.Sc.^3, 
Dimitris Samaras, Ph.D.^2, Fusheng Wang, Ph.D.^1,2
    2020-03-25
=============================================================================================================================





The classes p have attracted attention lately, because they are the main candidates for capturing the complexity of Necklace Splitting with p thieves, for prime p. However, these classes were not known to have complete problems of a topological nature, which impedes any progress towards settling the complexity of the Necklace Splitting problem.
On the contrary, topological problems have been pivotal in obtaining completeness results for PPAD and PPA, such as the PPAD-completeness of finding a Nash equilibrium <cit.> and the PPA-completeness of Necklace Splitting with 2 thieves <cit.>.

In this paper, we provide the first topological characterization of the classes -p. First, we show that the computational problem associated with a simple generalization of Tucker's Lemma, termed p-polygon-Tucker, as well as the associated Borsuk-Ulam-type theorem, p-polygon-Borsuk-Ulam, are -p-complete. Then, we show that the computational version of the well-known BSS Theorem <cit.>, as well as the associated BSS-Tucker problem are -p-complete. Finally, using a different generalization of Tucker's Lemma (termed ℤ_p-star-Tucker), which we prove to be -p-complete, we prove that p-thief Necklace Splitting is in -p. This latter result gives a new combinatorial proof for the Necklace Splitting theorem, the only proof of this nature other than that of <cit.>.

All of our containment results are obtained through a new combinatorial proof for ℤ_p-versions of Tucker's lemma that is a natural generalization of the standard combinatorial proof of Tucker's lemma by <cit.>. We believe that this new proof technique is of independent interest.







§ INTRODUCTION

The class  <cit.> is the class of Total Search Problems in NP, 
i.e., problems for which a solution is always guaranteed to exist, and can be verified 
in polynomial time. In a seminal paper, attempting to capture the complexity of numerous
interesting problems, <cit.> defined several subclasses of 
TFNP, such as ,  and , among others, each of which is associated with a different
existence principle. For example,  is based on the principle that given a source in 
a directed graph with in-degree and out-degree at most 1, there must exist another vertex of
degree 1;  is based on a similar principle on an undirected graph, and  is based on
the pigeonhole principle.

Among those,  has been largely  successful in capturing the complexity of many well-known 
problems, most prominently that of computing Nash equilibria in games 
<cit.>.  and  have been more elusive in that regard
for nearly two decades, until the recent results of <cit.> and
<cit.>, who provided the first “natural” complete problems for these classes
respectively. Here, a “natural” problem is one that does not explicitly include a polynomial-sized
circuit in its definition (as termed in <cit.>).
Interestingly, the -complete problems in <cit.> that solidified the status of  as a class containing such natural problems were the well-known Necklace Splitting problem for two thieves as well as its continuous variant (coined the Consensus-Halving problem in <cit.>). 

The Necklace Splitting problem is a classical problem in combinatorics, dating back to the mid-1980s and the works of <cit.>, <cit.> and <cit.>, among others. In this problem, k thieves are aiming to split an open necklace containing n beads of t different colors (with exactly k· a_i beads of color i, for some a_i ∈ℕ), such that each thief receives exactly a_i beads of color i. Furthermore, the thieves are allowed to use only (k-1)t cuts to obtain this division.
A solution to the Necklace Splitting problem is guaranteed to exist, as was proven by <cit.>. Earlier on, <cit.> and <cit.> had proven the existence of a solution for the case of 2 thieves; this result invokes a fundamental tool from mathematics, the Borsuk-Ulam Theorem <cit.>. Alon's proof for the general case proceeds in two steps. First, using a simple argument, he proves that if the theorem holds for any prime number p of thieves, it also holds for any other number of thieves. In the second step, which is significantly more involved, he proves the theorem for any prime number by using the BSS Theorem, a generalization of the Borsuk-Ulam Theorem due to <cit.>.

Questions about the computational complexity of finding a solution were raised explicitly as early as when the first existence results were proven <cit.> and then later on by a series of papers <cit.>. The first definitive answer was provided by <cit.>, via their -completeness result, following an initial -hardness result by <cit.>. Crucially however, their result only applies to the case of two thieves.[The authors also extend the  membership straightforwardly to numbers of thieves which are powers of 2.] In fact, the authors observed (also referencing <cit.> and <cit.> as previously having made similar observations) that the version of the problem with p ≥ 3 thieves does not seem to boil down to the principle associated with the class . To this end, they conjectured that p-thief Necklace Splitting is complete for the computational class -p, also defined by <cit.>, in which the associated principle is the following; Given a vertex with degree which is not a multiple of p in a bipartite graph, find another such vertex. It follows from the definition that 2=.

The classes p have been very recently studied by <cit.> and <cit.>. The authors of the latter paper in fact provide the first p-completeness result for a natural problem, a computational version of the Chevalley-Warning theorem. Importantly, they were able to obtain their completeness result via reductions to and from equivalent variants of the canonical problems of the class. To prove any results about p-thief Necklace Splitting however, such an approach seems insufficient. 

To see this, note that the results for p=2, both for the -membership <cit.> and for -hardness <cit.> of the problem, are obtained via reductions to/from a computational version of Tucker's Lemma <cit.>, a discrete analogue to the Borsuk-Ulam theorem, proven to be -complete by <cit.> and <cit.>. Tucker's lemma asserts that if we have an antipodally symmetric triangulation of a d-dimensional ball B and a labeling function which assigns complementary labels to antipodal points on the boundary, then there is a complementary edge, i.e., two adjacent points with equal-and-opposite labels. This connection is not a coincidence; for example, the idea in <cit.> is in fact a direct adaptation of a combinatorial existence proof of <cit.> for the Consensus-Halving problem, which goes via Tucker's lemma.

In order to obtain a p result for p-thief Necklace Splitting, it seems rather imperative to develop an “arsenal” of computational problems of a related nature, that we could reduce to/from, namely generalizations of the Borsuk-Ulam theorem and Tucker's lemma. Such “topological characterizations” did not only enable researchers in settling the complexity of the problem (and some other related problems) for = 2, but also facilitated the success of  to the utmost extent, seeing as virtually all the related important results go via the computational versions of the associated topological theorems (specifically Brouwer's Fixed-Point Theorem <cit.> and Sperner's Lemma <cit.>).[To be more precise, several important -hardness results were obtained via reductions from the Generalized Circuit problem <cit.>, which was however proven to be -complete via the aforementioned topological problems.] In a very related manner, <cit.> stressed the importance of obtaining such a generalization, in the quest for obtaining a combinatorial proof of Consensus-1/k-Division (the generalization of Consensus-Halving) and therefore, for Necklace Splitting with k thieves, for k>2. Lastly, <cit.> explicitly raised the complexity of one of these generalizations, the BSS Theorem, as an open problem.



 §.§ Our Results

In this paper, we obtain such a topological characterization of the classes p, for all primes p ≥ 3. Namely, we provide generalizations of the computational versions of the Borsuk-Ulam theorem and Tucker's lemma, parameterized by p, which are complete for p. A highlight of our generalizations is the -p completeness of the computational version of the BSS Theorem. Finally, we use a further generalization to prove that Necklace Splitting with p thieves lies in p.


The strength of our results lies in that


    
  ♢ they solidify the status of the classes -p as classes containing interesting well-known problems (adding to the recent results of <cit.>), and
    
  ♢ they set up an essential toolkit for obtaining more completeness results for the classes, e.g., possibly the -p-completeness of p-thief Necklace Splitting.


All of our p-membership results are obtained via a new combinatorial proof for ℤ_p-versions of Tucker's lemma. This new proof can be seen as a natural generalization of the standard combinatorial proof of Tucker's lemma by <cit.>. Thus, as a byproduct of our techniques we also obtain the following results:

    
  * A combinatorial proof of the BSS theorem. The original proof by <cit.> is not combinatorial, as it uses various tools from algebraic topology. Using our new technique, we are able to provide the first combinatorial proof for this theorem.
    
  * A combinatorial proof of the Necklace Splitting theorem. The existence of such a combinatorial proof had been an open problem since <cit.>. This open problem was solved by <cit.> using a rather complicated argument. In contrast, our new combinatorial proof uses more elementary tools and is conceptually simpler than Meunier's proof. 
    
  * A stronger statement of the continuous Necklace Splitting theorem which is called Consensus-1/p-Division <cit.>. The main advantage of our new theorem is that it actually works for valuation functions that are not necessarily additive and non-negative, for details see <ref>.

As a result, we believe that this new technique is of independent interest and will be useful for providing combinatorial proofs of other topological existence theorems such as Dold's Theorem <cit.>. We remark here that although the original proof of the Necklace Splitting theorem in <cit.> is via the BSS Theorem, our p membership result for Necklace Splitting does not go via the p membership result that we prove for BSS. This is due to the fact that for several steps of the proof of <cit.>, it is quite unclear whether they can be carried out in polynomial time. Instead, we construct a reduction directly from p, which we prove to be p-complete.




    In the remainder of this section, we informally state our main problems and 
results, and we give a short and high-level description of our proof 
techniques. We start with a topological theorem that is easy to state in <ref>, which we call k-Polygon Tucker's Lemma. Then, we present
our results about the completeness of the well-studied BSS Theorem in
<ref>.  Finally, we briefly explain how we get our new
combinatorial proof of Necklace Splitting and the containment in
p, in <ref>.



Throughout this paper, unless otherwise specified, k denotes an integer larger or equal to 2, and p denotes a prime number.
  


  §.§.§ The k-Polygon Borsuk-Ulam Theorem
 

 
The k-Polygon Borsuk-Ulam theorem can be understood  via the corresponding
statement of Borsuk-Ulam in 2 dimensions. First, let us introduce the following notion of equivariance for a function. 
Let S^1 be the unit circle
in 2-dimensions and B^2 be the unit disk. We say that a function g : S^1 →^2
is equivariant to a rotation of a^∘ degrees if whenever we
rotate the input x⃗ by a^∘, the image
g(x⃗) is also rotated by a^∘ degrees. We extend this definition to
functions f : B^2 →^2 and we say that f is equivariant to a rotation of
a^∘ degrees on the boundary if the restriction of f to the boundary S^1
is equivariant to a rotation of a^∘ degrees. 
Using this language, the following
is one of the many equivalent ways to state the classical Borsuk-Ulam Theorem in 2 dimensions (see the book by  <cit.> for various equivalent versions).

[2D Borsuk-Ulam Theorem] 
    Let f : B^2 →^2 be a continuous function that is equivariant to a rotation of
  180^∘ degrees on the boundary. Then, there exists 
  x⃗^⋆∈ B^2 such that f(x⃗^⋆) = 0.


The generalization, that we call k-Polygon Borsuk-Ulam Theorem,
comes as a clean extension of Borsuk-Ulam where instead of assuming equivariance to a 
rotation of 180^∘ degrees, we assume equivariance to a rotation of 
(360/k)^∘ degrees.

[k-Polygon Borsuk-Ulam Theorem] 
    Let f : B^2 →^2 be a continuous function that is equivariant to a rotation of
  360^∘/k degrees on the boundary. Then, there exists 
  x⃗^⋆∈ B^2 such that f(x⃗^⋆) = 0.


Apart from its own mathematical interest, the k-Polygon Borsuk-Ulam Theorem is
essential for our results, since it serves as a stepping stone towards showing all our topological
p-completeness results. Also, it is the only one of our topological
problems which is defined for any k ≥ 2, and thus the only problem which we are able to relate to the classes k, for general k.
 
  To prove the k-Polygon Borsuk-Ulam Theorem, we deviate from the topological 
techniques that have been used in the proof of similar extensions of the Borsuk-Ulam
Theorem <cit.> and we instead provide a combinatorial proof of a corresponding generalization of Tucker's lemma. We call this lemma k-Polygon Tucker's Lemma and an informal statement follows.

[k-Polygon Tucker's Lemma] 
    For k≥ 3, let T be a triangulation of B^2 with k-fold rotationally symmetric boundary. Suppose that every vertex
  ∈ T has a color λ() ∈ℤ_k such that λ is
  equivariant to a rotation of 360^∘/k degrees on the boundary. Then,
  in T there exists (i) a trichromatic triangle, or (ii) an edge with distinct non-consecutive colors.


The coloring function λ is equivariant
to a rotation of α^∘ degrees on the boundary if whenever the 
argument x⃗ is rotated by α^∘, the color is increased by 
1 k. Arguably, for k=3 the above statement of k-Polygon Tucker's Lemma bears more resemblance to
 Sperner's Lemma than to the original version of Tucker's Lemma, because the solution is necessarily a 
trichromatic triangle. However, this is due to the fact that we are considering only the 
two-dimensional case here. The connection with the original version of Tucker's Lemma will become more
apparent when we present other high-dimensional modulo-p generalizations of Tucker's Lemma.

  In the proof of k-Polygon Tucker's Lemma, the only inefficient step is the use
of a modulo-k counting argument. A simple way to visualize this 
argument is to imagine that if a space has cardinality 
that is non-zero modulo k and if we can group points in this space that are non-solutions into groups of
size k, then in this space there should exist a solution. This kind of existential argument has
been formalized by Papadimitriou in his seminal paper 
<cit.> and there have been various
instantiations of this principle from which we can define corresponding computational
problems <cit.>. In this paper, we mostly rely on 
the following instantiation defined by <cit.>:


  k : Given a directed graph and a vertex that is imbalanced-mod-k, i.e., (𝗈𝗎𝗍-𝖽𝖾𝗀𝗋𝖾𝖾) - (𝗂𝗇-𝖽𝖾𝗀𝗋𝖾𝖾) ≠ 0  k, find another such vertex.


Our main technical contribution in this section is to show that the 
computational problem associated with k-Polygon Tucker's Lemma is 
polynomial time equivalent to the computational version of k. Towards this goal, we provide a generalization of the standard path-following proof of Tucker's lemma by <cit.>. Importantly, in our proof (which is a reduction to k) the edges of the path are directed by using a consistent direction of triangulations (inspired by the idea of <cit.>). This technique was in fact incorrectly applied in the past to the case of k=2, leading to a false statement of -membership for Borsuk-Ulam. However, it turns out that the technique is very relevant in showing the equivalence between topological problems and modulo-k arguments for k>2.
We illustrate
the appropriate way to use this technique via the k problem and we believe 
that this will be useful for future reductions in k.

  The computational equivalence between k-Polygon Tucker's Lemma and k 
together with the computational equivalence of 
k-Polygon Tucker's Lemma and the k-Polygon Borsuk-Ulam implies the following 
theorem, which is our main result in this section.

 
    If k is a prime power, the computational problem associated with the k-Polygon Borsuk-Ulam Theorem is k-complete. If k is not a prime power, then it is complete for a subclass of
  k, denoted by k[#1].


The reason for this differentiation depending on whether k is a prime power or not, is that we actually show equivalence of k-Polygon Tucker's Lemma with a special case of k. If k is a prime power, then this special case is in fact k-complete, but in general it can be weaker.

  The formal definitions and the complete proofs, including the proof of <ref>, about the k-Polygon Borsuk-Ulam Theorem
appear in <ref>.



  §.§.§ Complexity of Finding Solutions to the BSS Theorem
 

  In this section, we present our results regarding the computational complexity of 
finding solutions  guaranteed to exist by the BSS Theorem, a famous
generalization of the celebrated Borsuk-Ulam Theorem. The BSS Theorem should be thought of as the 
corresponding k-Polygon Borsuk-Ulam in higher dimensions. We clarify though
that the BSS Theorem only works with k = p where p is a prime, and it applies only when
the number of dimensions is a multiple of p - 1. Hence, for p ≥ 5 the
p-Polygon Borsuk-Ulam Theorem does not follow directly from the BSS Theorem. This is why we 
consider it a separate result and devote a separate section to it.

  When moving to more than two dimensions, we need to find an equivariance notion
corresponding to the equivariance of a rotation that we defined in the previous
section. A fundamental feature of a rotation in the plane is that it is a 
free action on the boundary, i.e., there is no point on the boundary
S^1 that remains fixed if we apply the rotation. This free action property of 
rotations is crucial in the proof of k-Polygon Borsuk-Ulam Theorem and without
this property the theorem does not hold. Unfortunately, in higher
dimensions the rotations with respect to any axis no longer possess this property, as they always have a 
fixed point on the boundary S^m - 1 of the m-dimensional ball B^m. Thus, in higher dimensions  other operations acting 
 freely on S^m - 1 emerge.

  For the case of k = 2, there is a very simple generalization of the rotation by
180^∘ that is a free action in any number of dimensions, namely, the
point reflection with respect to the origin, i.e., x ↦ -x. Hence, we have the following
informal statement of the Borsuk-Ulam Theorem for a general number of dimensions.

[Borsuk-Ulam Theorem] 
    Let f : B^m →^m be a continuous function that on the boundary is 
  equivariant to point reflection with respect to the origin. Then, there exists
  x⃗^⋆∈ B^m such that f(x⃗^⋆) = 0.


Observe that the order of the point reflection operation is equal to 
k = 2, since if we apply the same operation twice, we return to the same
point. It is also trivial to see that the rotation by 360^∘/k degrees has 
order k, since after k times of applying this operation we return to the same 
point and if we apply this operation less than k times, then we end up on a different 
point. These observations together with the requirement for a free action suggest
that in order to generalize the k-Polygon Borsuk-Ulam theorem to higher dimensions we need
a free action of order k on the boundary S^m - 1 of the m-dimensional ball
B^m. Unfortunately, finding such operations is not as easy as in the case k = 2.
In particular, for m = 2 ℓ + 1 the sphere S^2 ℓ has a free action of order k
only for k = 2 <cit.>. The starting point of the BSS Theorem is 
defining an operation α_p that has order p, where p is a prime number,
and defines a free action on the sphere S^n (p - 1) - 1. These restrictions on α_p 
are the reason why, as we mentioned in the beginning of the section,
BSS only applies to dimensions that are multiples of p - 1 and for k = p 
where p is a prime number. Using the operation α_p, we can informally state
the BSS Theorem as follows:

[BSS Theorem <cit.>] 
    Let f : B^n (p - 1)→^n (p - 1) be a continuous function that is
  equivariant with respect to α_p on the boundary. Then, there exists 
  x⃗^⋆∈ B^n (p - 1) such that f(x⃗^⋆) = 0.


The original proof of the BSS Theorem <cit.> goes through the definition of
indices of functions in algebraic topology. One of our main contributions is to provide 
a combinatorial proof of the BSS Theorem. As in the case of 
k-Polygon Borsuk-Ulam, we provide a combinatorial proof of the BSS Theorem via
the corresponding version of Tucker's Lemma, which we call BSS Tucker's Lemma and we informally
state below.

[BSS Tucker's Lemma] 
    Let p be a prime and T be a triangulation of B^n (p - 1) with an α_p-symmetric boundary. Suppose that
  every vertex x⃗∈ T has a color 
  λ(x⃗) ∈ℤ_p × [n] such that λ is 
  equivariant with respect to α_p on the boundary. Then, there exists
  a (p - 1)-simplex in T that has all the colors (1, j), … (p, j) for 
  some j ∈ [n].


Our main technical contribution in this section is to show the following 
statements.



  
  ▹ The computational problem that is associated with
  BSS Tucker's Lemma is polynomial time equivalent to the computational problem
  associated with the BSS Theorem (<ref>).
  
  ▹ The computational problem associated with 
  p-Polygon Tucker's Lemma is reducible to the computational problem associated with
  BSS Tucker's Lemma (<ref>).
  
  ▹ The computational problem associated with BSS Tucker's
  Lemma is reducible to the computational problem associated with 
  ℤ_p-star Tucker's Lemma (<ref>).


ℤ_p-star Tucker's Lemma is an existence theorem that we define 
informally in the next section and is the basic building block for proving the membership
of Necklace Splitting in p. As we will see in the next section, we 
prove that the computational problem associated with ℤ_p-star Tucker's
Lemma is inside p. This result combined with <ref>,
which shows the PPA-p-completeness of the
p-Polygon Borsuk-Ulam Theorem, and the equivalence of the p-Polygon Borsuk-Ulam Theorem and p-Polygon Tucker's lemma, implies the main result of this section.

 
    The computational problem associated with the BSS Theorem 
  is p-complete.


We defer the formal definition of the computational problem associated with the BSS Theorem and the complete proofs, including the proof of
 <ref>, about the BSS Theorem appear in
<ref>.
 


  §.§.§ Necklace Splitting with p thieves is in p
 

  Our main goal in the last part of the paper is to show that the computational
problems associated with the p-Necklace Splitting Theorem and the Consensus-1/p-Division Theorem are in p. Towards this goal we provide a full 
combinatorial proof for both of these problems that simplifies the only existing 
combinatorial proof by <cit.>.

Our proof uses a different generalization of Tucker's Lemma which we call ℤ_p-star Tucker's Lemma. Both
the statement of ℤ_p-star Tucker Lemma and the proof are simple enough so 
that they do not invoke the involved definition of simplotopal complexes of 
<cit.>. These simplotopal complexes were used by Meunier in order to obtain a direct proof of the Necklace-Splitting theorem, without proving its continuous version. In contrast, we use standard simplicial complexes, since we are not only interested in the Necklace Splitting theorem, but also in its continuous generalization: the Consensus-1/k-Division Theorem (informally defined below).

  Recall that in the k-Necklace Splitting problem, k thieves are aiming to split an open 
necklace containing n beads of t different colors, with exactly k · a_i
beads of color i, for some a_i ∈ℕ, such that each thief
receives exactly a_i beads of color i. The k-Necklace Splitting Theorem states
the following.

[k-Necklace Splitting Theorem <cit.>] 
    The k-Necklace Splitting problem always has a solution with (k - 1)t cuts.


The Consensus-1/k-Division problem resembles the continuous version of the
k-Necklace Splitting problem. In this problem, each one of t agents has a 
probability measure μ_i over the unit interval [0, 1]. The goal is to cut the
interval [0, 1] into pieces and assign one of k possible colors to each piece
such that every agent measures the total mass of each different color the same.

[Consensus-1/k-Division Theorem <cit.>] 
    The Consensus-1/k-Division problem always has a solution with (k - 1)t cuts.


Both the k-Necklace Splitting Theorem and the Consensus-1/k-Division Theorem 
have significant applications to combinatorics and social choice; see <ref>.

  As we have already mentioned, the proof that for prime p the computational problems associated with
the p-Necklace Splitting Theorem and the Consensus-1/p-Division Theorem are 
inside p, is based on a different generalization of Tucker's Lemma for 
modulo-p arguments, ℤ_p-star Tucker's Lemma. The main difference of
ℤ_p-star Tucker's Lemma with BSS Tucker's Lemma is the domain on which we 
define the triangulation. In the case of BSS Tucker's Lemma, the triangulation is
defined over a convex domain and hence is homeomorphic with the ball B^m. On the 
other hand, the triangulation for ℤ_p-star Tucker's Lemma is defined over 
a star-convex set which is not
homeomorphic to the ball B^m anymore. This d-dimensional domain, which we denote by R^d_p, is a slightly modified version of the domain used by <cit.> in his combinatorial proof of the p-Necklace Splitting Theorem. It admits a natural free action θ_p of order p. We can informally state ℤ_p-star Tucker's
Lemma similarly to BSS Tucker's lemma as follows.

[ℤ_p-star Tucker's Lemma] 
    Let p be a prime and T be a triangulation of R^t(p - 1)_p. Suppose 
  that every vertex x⃗∈ T has a color 
  λ(x⃗) ∈ℤ_p × [t] such that λ is
  equivariant with respect to θ_p on the boundary. Then, there exists a
  (p - 1)-simplex of T that has all the colors (1, j), … (p, j) for some
  j ∈ [t].


Our main technical contributions in this section are summarized in the following 
statements.



  
  ▹ The computational problems that are associated with the 
  p-Necklace Splitting Theorem and the Consensus-1/p-Division Theorem are 
  polynomial time reducible to ℤ_p-star Tucker's Lemma (<ref>).
  
  ▹ The computational problem associated with 
  ℤ_p-star Tucker's Lemma is inside p (<ref>). This is again proved by a reduction to p, but this time we construct a weighted directed graph.
  
  ▹ The computational problem associated with BSS Tucker's Lemma
  is polynomial time reducible to the computational problem associated with 
  ℤ_p-star Tucker's Lemma (<ref>).


  The above statements combined with the results in the previous sections imply our main result for
this part of the paper.

 
    The computational problem associated with ℤ_p-star Tucker's
  Lemma is p-complete. The computational problems that are associated with
  the p-Necklace Splitting Theorem and the Consensus-1/p-Division Theorem are in
  p.


As a corollary of this result, we also obtain that for general k ≥ 2, k-Necklace Splitting and Consensus-1/k-Division lie in k under Turing reductions. In particular, if k=p^r is a prime power, then the corresponding problems lie in p. Furthermore, our reductions also provide a new combinatorial proof of the Necklace Splitting theorem, that is conceptually simpler and does not use any involved machinery.

  The formal definitions and the complete proofs, including the proof of <ref>, about ℤ_p-star Tucker's
  Lemma, the p-Necklace Splitting Theorem and the Consensus-1/p-Division Theorem appear in
<ref> and <ref>.



Our results are summarized in <ref>, where we also highlight where they fit in the computational landscape of the classes of interest. Relevant further related work is discussed in the next section.















 §.§ Discussion and Further Related Work





Computational Classes: As mentioned earlier, among the classes of TFNP, PPAD has been the most successful in capturing the complexity of well-known problems. Besides the complexity of computing a Nash equilibrium <cit.>, other -complete problems are computing equilibria in markets <cit.>, versions of envy-free cake cutting 
<cit.> and fixed-point theorems <cit.>. 

For , the recent results by <cit.> have solidified the status of the class as one that contains natural problems. In particular, they showed that 2-thief Necklace Splitting is -complete; the proof goes via its continuous version, the Consensus-Halving problem of <cit.>[The hardness result of <cit.> for the Consensus-Halving problem was strengthened recently by <cit.> to the case of simpler measures.] Our p-membership result for the problem with p thieves also uses the continuous variant, termed as Consensus-1/p-Division in <cit.>; we note that <cit.> used the same problem in his existence proof, referring to it as a generalized Hobby-Rice Theorem. As we explained earlier, <cit.> conjectured that the problem with p thieves is complete for p.

The classes p were introduced by <cit.> for any prime p, in the context of classifying a computational version of the Chevalley-Warning theorem <cit.>. He proved that the corresponding problem Chevalley-mod-p lies in p. Recently, <cit.> showed that an explicit version of the problem is complete for p, therefore obtaining the first p-completeness result for a natural problem. The authors of <cit.>, as well as <cit.>, independently also extended the definition of the classes k to any k ≥ 2, and provided several characterizations in terms of their defined-for-primes counterparts. <cit.> also investigated the connection with the classes PMOD-k, which bear strong resemblance to k, and were defined seemingly independently of Papadimitriou's work by <cit.>. From the work of <cit.>, we primarily make use of the k-complete computational problem k, a generalization of the -complete problem Imbalance <cit.>.


Necklace Splitting: The origins of the Necklace Splitting problem (<ref>), and its continuous variant (<ref>), can be traced back to work of <cit.> and <cit.>. The problem was firstly phrased as a necklace splitting problem by <cit.>. Later on, <cit.> and <cit.> proved the first existence results for two thieves, and <cit.> extended the result to the case of any number k ≥ 2 of thieves. For two thieves, the continuous version was studied independently by <cit.>, who termed the problem as “Consensus-Halving” and came up with a combinatorial, constructive proof of existence; this proof was later modified into a  membership proof by <cit.>. The importance of obtaining combinatorial proofs of existence was highlighted in a series of papers <cit.>; note that the proof of <cit.> uses two results of <cit.> and is therefore not combinatorial. The first fully combinatorial proof for Necklace Splitting (according to the definition of <cit.>) is due to <cit.>. However, the proof comes up with a rather involved construction based on the notion of simplotopal complexes, and thus is notably hard to follow without an advanced understanding of the theory of simplicial complexes. Since our proof is based on a reduction, it is also inherently combinatorial. Very recently, <cit.> studied approximate versions of both the continuous and the discrete variants, and provided polynomial-time algorithms for either large enough approximations or a larger number of cuts (i.e., cases not captured by the hardness results of <cit.>).


The BSS Theorem: The BSS Theorem (<ref>, <ref>), due to <cit.>, is perhaps the most well-known generalization of the Borsuk-Ulam theorem. Besides <cit.>, it has been used to prove existence of other interesting problems, including a generalization of the Kneser-Lovász Theorem <cit.> due to <cit.>, a generalized van Kampen-Flores Theorem <cit.> and the generalization to Tverberg's Theorem, proven in <cit.>. We believe that our -p-completeness result paves the way for studying the complexity of those problems as well.








§ PRELIMINARIES




 §.§ Total NP Search Problems


Let {0,1}^* denote the set of all finite length bit-strings. For x ∈{0,1}^*, let |x| be its length. A computational search problem is given by a binary relation R ⊆{0,1}^* ×{0,1}^*. The associated problem is: given an instance x ∈{0,1}^*, find a y ∈{0,1}^* such that (x,y) ∈ R, or return that no such y exists. The search problem R is in FNP (Functions in NP), if R is polynomial-time computable (i.e., (x,y) ∈ R can be decided in polynomial time in |x|+|y|) and there exists some polynomial p such that (x,y) ∈ R  |y| ≤ p(|x|).  Thus, FNP is the search problem version of NP.

The class TFNP (Total Functions in NP <cit.>) contains all FNP search problems R that are total: for every x ∈{0,1}^* there exists y ∈{0,1}^* such that (x,y) ∈ R. Note that the totality of problems in TFNP does not rely on any “promise”. Instead, there is a syntactic guarantee of totality: for any instance in {0,1}^*, there is always at least one solution.

Let R and S be total search problems in TFNP. We say that R (many-one) reduces to S, denoted R ≤ S, if there exist polynomial-time computable functions f,g such that

    (f(x),y) ∈ S  (x,g(x,y)) ∈ R.

Note that if S is polynomial-time solvable, then so is R. We say that two problems R and S are (polynomial-time) equivalent, if R ≤ S and S ≤ R.

Sometimes a more general notion of reduction is used. A Turing reduction from R to S is a polynomial-time oracle Turing machine that solves problem R with the help of queries to an oracle for S. Note that a Turing reduction that only makes a single oracle query immediately yields a many-one reduction.



 §.§ The Classes k


For k ≥ 2, k is a subclass of TFNP that aims to capture the complexity of TFNP problems whose totality is proved by using an argument modulo k. The classes p (for prime p) were introduced by <cit.>. The case p=2 corresponds to parity arguments, and in that case the class 2 is simply called . Recently, the definition of k was extended to any k ≥ 2 by <cit.>. The class k is defined as the class of TFNP problems that reduce to the following problem.


Let k ≥ 2. The problem k is defined as: given a Boolean circuit C: {0,1}×{0,1}^n → ({0,1}×{0,1}^n)^k that computes a bipartite graph on the vertex set ({0}×{0,1}^n, {1}×{0,1}^n) with |C(00^n)| ∈{1,…, k-1}, find

    
  * x ≠ 00^n such that |C(x)| ∉{0,k}
    
  * or x,y such that y ∈ C(x) but x ∉ C(y).



The circuit C computes a bipartite graph as follows. The output of circuit C on some input x is a list of k bit-strings, each of length n+1. If x ∈{0}×{0,1}^n, then we let C(x) denote the set of distinct bit-strings that appear in that list and that lie in {1}×{0,1}^n. Similarly, if x ∈{1}×{0,1}^n, then C(x) denotes the set of distinct bit-strings that appear in that list and that lie in {0}×{0,1}^n. For any x,y ∈{0,1}×{0,1}^n, there exists an edge between x and y if and only if y ∈ C(x) and x ∈ C(y). It is easy to see that this indeed defines a bipartite graph.


Let k ≥ 2 and 1 ≤ℓ≤ k-1. The problem kℓ is defined as k (<ref>) but with the additional condition |C(00^n)| = ℓ.


Note that this condition can be enforced syntactically and so this problem also lies in TFNP (see <cit.> for a definition of “syntactic”). 


Let k ≥ 2 and 1 ≤ℓ≤ k-1. The class kℓ is defined as the set of all  problems that many-one reduce to kℓ.


The following result relates these special subclasses to the main ones.


k[#1] = ∩_p ∈ PF(k)p, where PF(k) denotes the set of prime factors of k.


In this paper, we will also use the following definition of k, which was shown to be equivalent to the standard one <cit.>. The class k is the set of all TFNP problems that reduce to the following problem.


Let k ≥ 2. The problem k is defined as: given Boolean circuits S,P : {0,1}^n → ({0,1}^n)^k with |S(0^n)|-|P(0^n)| ≠ 0  k, find

    
  * x ≠ 0^n such that |S(x)|-|P(x)| ≠ 0  k
    
  * or x,y such that y ∈ S(x) but x ∉ P(y), or y ∈ P(x) but x ∉ S(y).

For 1 ≤ℓ≤ k-1, kℓ is defined with the additional condition |S(0)|-|P(0)| = ℓ.




We obtain a seemingly more general version of this problem by allowing the edges to have integer weights. In that case the imbalance of a vertex is measured as the difference of the weights of all incoming edges and the weights of all outgoing edges. It is easy to see that this problem is in fact equivalent to k. First, all the weights can be assumed to be in {0,1, …, k-1}, since we can reduce them modulo k. Next, we can split an edge with weight ℓ into ℓ copies of the edge. Finally, to ensure that we don't have multi-edges, we add a new vertex in the middle of every edge.
Note that the new vertex will be balanced by construction, and will thus not introduce any new solutions.

  It is easy to see that in all the aforementioned problems a solution is always
guaranteed to exist. The search problems are not trivial though, because the graph can
have exponential size with respect to its description. Indeed, the graph is given by 
Boolean circuits that compute the successors and predecessors of every vertex. 

We make use of the following known properties of these classes:


It holds that:

    
  * for any prime p and any r ≥ 1, p^r = p
    
  * for any k, ℓ≥ 1, k⊆kℓ







  
Topological Definitions and Details: Our results in the next sections will require several definitions from topology, as well as the corresponding notation. The more experienced reader might already be familiar with some of these concepts, but all the relevant details are included in <ref>. There, we also define our value and index functions, which allow us to enumerate over simplices, and access simplices that contain a point 𝐱 in the domain respectively. 




§ K-POLYGON BORSUK-ULAM: A K[#1]-COMPLETE PROBLEM IN 2D-SPACE


  In this section we present a generalization of the Borsuk-Ulam Theorem in two 
dimensional space. Surprisingly this theorem is not captured by the BSS Theorem and
hence has its own topological interest. Our proof of this theorem is combinatorial
and is based on a generalization of Tucker's Lemma which we call 
Polygon Tucker's Lemma, hence it is very different from the proof of the BSS
Theorem. Our main result is that k-Polygon Borsuk-Ulam is complete for k[#1].
This gives the first topological characterization of the classes k[#1] but also
reveals in a very intuitive way the relation between the different k[#1] classes
and . Recall that when k = p^r is a prime power, k[#1] = k = p.


  We start this section with a unified description of Brouwer's Fixed Point Theorem, the Borsuk-Ulam Theorem and our generalization: the k-Polygon Borsuk-Ulam Theorem. For 
this we will need the following definition.

 
    We define the k-th rotation operator 
  θ_k : ^2 →^2 as follows: 
  θ_k(x⃗) = R_k x⃗, where R_k is the following two 
  dimensional rotation matrix 
  
    R_k = [  cos(-2 π/k) -sin(-2 π/k);  sin(-2 π/k)  cos(-2 π/k) ].

In other words, θ_k corresponds to a clockwise rotation by an angle of 2 π/k.


  We continue with a statement of Brouwer's Fixed Point Theorem that is 
different from the standard statement, but is well known to be equivalent to that (e.g., see <cit.>).

 
    Let f : B^2 →^2 be a continuous function such that f(x⃗) = x⃗
  for all x⃗∈∂ B^2. Then there exists x⃗^⋆∈ B^2
  such that f(x⃗^⋆) = 0.


  Next, using the same language, we give a statement of the Borsuk-Ulam Theorem.

 
    Let f : B^2 →^2 be a continuous function such that 
  f(θ_2(x⃗)) = θ_2(f(x⃗)) for all 
  x⃗∈∂ B^2. Then there exists x⃗^⋆∈ B^2 such that
  f(x⃗^⋆) = 0.


  It is clear from the above expression that the Borsuk-Ulam Theorem is a
generalization of Brouwer's Fixed Point Theorem. This observation is in line with 
the fact that ⊆, since Brouwer is 
complete for  and Borsuk-Ulam is complete for . We now present our 
extension, that we call k-Polygon Borsuk-Ulam Theorem.

 
    Let f : B^2 →^2 be a continuous function such that 
  f(θ_k(x⃗)) = θ_k(f(x⃗)) for all 
  x⃗∈∂ B^2. Then there exists x⃗^⋆∈ B^2 such that
  f(x⃗^⋆) = 0.


  As we will see the k-Polygon Borsuk-Ulam Theorem is also a generalization of 
Brouwer's Fixed Point Theorem and it is complete for k[#1] which is also in
line with the fact that ⊆k[#1]. Another interesting fact about the
k-Polygon Borsuk-Ulam Theorem is that it does not directly follow from the traditional 
generalization of the Borsuk-Ulam Theorem, namely the BSS Theorem, as we will see
in the next section.




 §.§ k-Polygon Tucker's Lemma and k-Polygon Borsuk-Ulam in k[#1]



  In this section, we define k-Polygon Tucker's Lemma and we prove
that it is equivalent to the k-Polygon Borsuk-Ulam Theorem. Additionally, we provide a 
combinatorial proof of k-Polygon Tucker's Lemma using a modulo-k
argument. This combinatorial proof puts both k-Polygon Tucker and k-Polygon Borsuk-Ulam
in the class k[#1]. 

Before showing the equivalence of the two statements, we provide some necessary notation and 
definitions.


    For k ≥ 3, let W_k be the regular k-polygon, i.e., regular k-gon, centered at 0⃗∈ℝ^2
  with radius 1. Let
  _1, …, _k denote the vertices of W_k, ordered such that θ_k(_i) = _i+1 k for all i ∈ [k]. We define T^⋆ to be
  the triangulation of W_k that includes the simplices 
  σ_i = ({0⃗, u⃗_i, u⃗_i + 1 k}) for 
  i ∈ [k]. We call a triangulation T nice if it satisfies the following two 
  properties:
  
      
  * it is a refinement of T^⋆, and
      
  * it is symmetric with respect to θ_k on the boundary. This
  means that for every edge ψ∈ T such that ψ⊆∂ W_k it 
  holds that θ_k(ψ) ∈ T.
  


 
    For k≥ 3, let W_k be a k-regular polygon. Fix some nice triangulation 
  T of W_k. Suppose that every vertex ∈ T has a label 
  λ() ∈ℤ_k such that for any ∈∂ T we have
  λ(θ_k()) = λ() + 1 k. Then at least one of the
  following exists: (1) a simplex σ∈ T with vertices v⃗_1,
  v⃗_2, v⃗_3 such that all the labels λ(v⃗_1),
  λ(v⃗_2), λ(v⃗_3) are different, or (2) an edge 
  ψ∈ T with vertices v⃗_1, v⃗_2 such that 
  λ(v⃗_1) - λ(v⃗_2) k∉{0, 1, -1}.



    The above theorem can be proved if we invoke Dold's 
  Theorem from algebraic topology <cit.>. However this proof is 
  not a constructive proof and hence it cannot be used for our purposes and
  for this reason we reprove this theorem using a constructive combinatorial
  proof. Of course, this is only a special case of the general Dold's Theorem
  and it is an interesting open problem what is the relation of Dold's 
  Theorem with the subclasses of TFNP as we state in the Conclusions 
  section.




  §.§.§ Equivalence of k-Polygon Tucker and k-Polygon Borsuk-Ulam
 

  We start by showing that k-Polygon Tucker's Lemma is implied by k-Polygon
Borsuk-Ulam Theorem and then we also show the converse, in 
<ref> and 
<ref>.

 
    k-Polygon Borsuk-Ulam (<ref>) implies
 k-Polygon Tucker's Lemma (<ref>).



    We interpret each label i ∈ℤ_k as the vector _i, which is 
  the i-th vertex of the polygon W_k. Let h: W_k → W_k  be the piecewise linear extension of 
  the function that has value _λ(x⃗) on any vertex x⃗∈ T. Finally 
  we define g : B^2 →^2 as the composition of h and a homeomorphism between W_k and
  B^2 that maps 0⃗ to 0⃗ and is θ_k-equivariant. Notice that by the definition of h and g
  and the equivariance assumption on λ, it holds that 
  g(θ_k()) = θ_k(g()) for ∈∂ B^2. Then, it
  follows from <ref> that there exists an 
  ^⋆∈ B^2 such that g(^⋆) = 0 and hence there exists a
  ^⋆∈ W_k such that h(^⋆) = 0.
     
    Now, let σ^⋆ be a full-dimensional simplex of T that
  contains ^⋆. If the vertices of σ^⋆ have only two consecutive labels,
  say 1 and 2 (corresponding to vectors _1 and _2), then it is impossible to 
  have h(^⋆) = 0 since it is a non-zero linear
  interpolation of _1 and _2 and these vectors are linearly independent.
  Hence, it has to be that the vertices of σ^⋆ have either two non-consecutive labels or three different labels
  and k-Polygon Tucker's Lemma follows.


 
    k-Polygon Tucker's Lemma (<ref>) implies
  k-Polygon Borsuk-Ulam (<ref>).



    Let h : W_k →^2 be the function obtained from f by using a  
  homeomorphism between W_k and B^2 that fixes 0⃗ and is θ_k-equivariant. Using standard arguments,
  that are used in the proof of both Brouwer's Fixed Point Theorem via Sperner's
  Lemma and the proof of Borsuk-Ulam via Tucker's Lemma, it is enough if for every
  ε > 0 we find a point  such that h()≤ε, for
  details we refer to <cit.>. Since h is a continuous function in a
  compact set, it is also uniformly continuous. Thus for every ε > 0 there
  exists a δ > 0 such that for any , ' ∈ W_k, if 
  - '_2 < δ, then 
  h() - h(') < ε / k. Assume that T is a nice 
  triangulation of W_k such that any simplex σ∈ T has diameter 
  at most δ.

    We define the labeling λ() = i to be equal to the index of the vertex
  u⃗_i of W_k that is closest to h(). We break ties between i and i+1, by picking i. Note that the only other kind of tie that can occur is if h()=0. In that case all labels are tied. If =0, we pick one arbitrarily. Otherwise, i.e., if ≠ 0, we apply the same rule as for h() above, but for  instead. It is easy to check that this tie-breaking is ℤ_k-equivariant. For any ∈∂ W_k because of the equivariance
  assumption on g we have that λ(θ_k()) = λ() + 1k
  and hence the assumptions of k-Polygon Tucker's Lemma are satisfied. Now we 
  distinguish two cases.
  

  
k = 3. In this case, 3-Polygon Tucker's Lemma implies that there
  exists a simplex σ∈ T whose vertices v⃗_1, v⃗_2, 
  v⃗_3 contain all the labels 1, 2, and 3 respectively. This implies the 
  following set of inequalities by the definition of the labeling λ
  
    h(v⃗_1) - u⃗_1≤min(h(v⃗_1) - u⃗_2, h(v⃗_1) - u⃗_3)

  
    h(v⃗_2) - u⃗_2≤min(h(v⃗_2) - u⃗_1, h(v⃗_2) - u⃗_3)

  
    h(v⃗_3) - u⃗_3≤min(h(v⃗_3) - u⃗_1, h(v⃗_3) - u⃗_2).

  Hence, it is easy to see that the maximum angle between any of 
  h(v⃗_1), h(v⃗_2) and h(v⃗_3) is at least 2 π/3. Now, assume
  for the sake of contradiction that for all v⃗_1, v⃗_2, v⃗_3 it holds
  that
  
    h(v⃗_1)≥ε,  h(v⃗_2)≥ε,  h(v⃗_3)≥ε.

  This together with the fact that the maximum angle is at least 2 π/3 
  implies that the maximum distance is at least 2 sin(2 π/6) ε. But this
  implies that 
  
    max(h(v⃗_1) - h(v⃗_2), h(v⃗_2) - h(v⃗_3), h(v⃗_1) - h(v⃗_3)) ≥√(3)·ε > ε/3

  which contradicts the definition of the triangulation T, where the 
  vertices of the same simplex are at most δ far from each other and hence 
  their images are at most ε/k= ε/3 far from each other. This implies that our
  assumption was wrong and hence for at least one i ∈ [3] it holds that
  h(v⃗_i)≤ε and the result for this case follows.
  

  
k > 3. In this case, k-Polygon Tucker's Lemma implies that there
  exists an edge ψ∈ T whose vertices v⃗_1 and v⃗_2
  have labels that differ by more that one, without loss of generality assume that these
  labels are 1 and 3 respectively. By the definition of the labeling λ this
  implies that
  
    h(v⃗_1) - u⃗_1≤min_i(h(v⃗_1) - u⃗_i),    h(v⃗_2) - u⃗_3≤min_i(h(v⃗_2) - u⃗_i)

  Hence, it is easy to see that the angle between h(v⃗_1) and h(v⃗_2) is at
  least 2 π/k. Now, for sake of contradiction we assume that
  
    h(v⃗_1)≥ε,  h(v⃗_2)≥ε.

  This together with the fact that the angle is at least 2 π/k implies
  that the distance h(v⃗_1) - h(v⃗_2) is at least 
  2 sin(2 π / k) ε > ε / k which contradicts the definition of 
  T.
  Therefore, in both cases for every ε > 0 we can find a v⃗∈ W_k such that 
  h(v⃗)≤ε. This, by standard arguments and the compactness of W_k,
  implies that there exists a point x⃗^⋆∈ W_k such that 
  h(x⃗^⋆) = 0⃗ and hence the result follows.




  §.§.§ Proof of k-Polygon Tucker's Lemma
 

In this section, we prove k-Polygon Tucker's Lemma. A corollary of our proof
combined with <ref> is that the
computational problems associated with k-Polygon Tucker's Lemma and k-Polygon 
Borsuk-Ulam both belong to k[#1]. The proof technique that we introduce here is a generalization of the combinatorial proof of Tucker's lemma given by <cit.>.


  We use a modulo-k argument to prove this theorem. We define a directed 
graph where the vertices correspond to the simplices of T, and we also identify the symmetric edges of
T on the boundary of W_k as the same vertex. Then, in this graph we describe a 
rule for defining edges such that there exist three types of vertices:

  
  * the vertex that corresponds to the 0-dimensional simplex {0⃗} which 
  will have degree 1,
  
  * vertices that are balanced k, i.e., 
  (𝗈𝗎𝗍-𝖽𝖾𝗀𝗋𝖾𝖾) - (𝗂𝗇-𝖽𝖾𝗀𝗋𝖾𝖾) = 0 k,
  
  * vertices that are different from {0⃗} and are not balanced k.

Due to a simple modulo-k argument and because {0⃗} is not balanced
we can conclude that the constructed graph contains a vertex of type 3. Finally, we 
prove that all vertices of type 3 correspond to either a trichromatic triangle or a 
bichromatic edge with distinct non-consecutive labels and hence k-Polygon Tucker's Lemma 
follows. Our proof also gives us a reduction of the computational problem associated
with k-Polygon Tucker's Lemma to the problem k[#1].


For any simplex σ∈ T we define S(σ) and λ(σ): 

    
  ▹ S(σ) ⊆ [k] is the minimal subset of [k]
    such that σ lies in the cone defined by {u⃗_i : i ∈ S(σ)},
    
  ▹ 
    λ(σ) = {λ(x⃗) : x⃗ is a vertex of σ},

and we let S({0⃗}) = ∅.
 

    Observe that because T is a refinement of T^*, we have that every 
  simplex σ∈ T is contained in a cone defined by two consecutive 
  vectors u⃗_i, u⃗_i +1. Hence, for σ≠{0⃗},  
  S(σ) contains either a single number i ∈ [k] or two consecutive numbers
  i, i +1. 




 A simplex σ∈ T is called happy if and only if 
S(σ) ⊆λ(σ). See also
<ref> for an example that explains the definition.


  We will define a graph G with vertex set V(G) = T. In G, we will only add
directed edges to the following vertices, which we call relevant:

  
  (a) vertices that correspond to a simplex σ∈ T such that 
  σ∉∂ T and σ is happy,
  
  (b) vertices that correspond to a simplex ψ∈∂ T such that ψ is happy and:
  
      
  * ψ = {u_1}, if ψ is 0-dimensional
      
  * ψ⊆({u⃗_1, u⃗_2}), if ψ is 1-dimensional.
  

The reason for this distinction between simplices on the boundary and 
simplices not on the boundary is that we want to identify the symmetric simplices on
the boundary as a super vertex in order to correctly use a modulo-k argument, as
we described in the sketch of the proof.


    The rest of the vertices in V(G) that do not correspond to type (a) or (b) simplices
  can be thought of as having 
  (𝗈𝗎𝗍-𝖽𝖾𝗀𝗋𝖾𝖾) = (𝗂𝗇-𝖽𝖾𝗀𝗋𝖾𝖾) = 0 or
  as having a self-loop. In both cases, these vertices are balanced.


  We add an edge (v, v') to the graph G only if the simplices σ and
σ' that correspond to v and v' are both relevant and one of the following rules applies:

  
  * case 
  σ∉∂ T, σ' ∉∂ T: We
  add the edge if σ' ⊆σ and the labels of 
  σ' suffice to make σ happy, i.e., 
  S(σ) ⊆λ(σ'),
  
  * case 
  σ∉∂ T, σ' ∈∂ T:  Observe that since v' is 
  relevant and σ' ∈∂ T, v' is of type (b). So, instead of checking whether σ' ⊆σ, we check whether there exists t ∈ [k] such that τ := θ^(t)_k(σ') ⊆σ and τ suffices to make σ happy, i.e., S(σ) ⊆λ(τ).




  
*Directing the edges. The edge between σ and σ' is directed in the following natural way:

    
  * if σ is 1-dimensional, then σ and σ' lie in ({0,u⃗_i}) for some i, and the edge is directed “away from 0”. Formally, if σ = {z⃗_0, z⃗_1} and σ' = {z⃗_1} are connected by an edge, then write z⃗_0 = α_i u_i and z⃗_1 = β_i u_i. If α_i-β_i > 0, then the edge is incoming into σ. If α_i-β_i < 0, then the edge is outgoing out of σ.
    
  * if σ is 2-dimensional, then σ and σ' lie in ({0,u⃗_i,u⃗_j}) for some i,j with i-j = ± 1 k. If j=i+1, then the edge is directed such that “we keep label i to our right, and label j=i+1 to our left, when we move in the direction of the edge”. If j=i-1, then the edge is directed such that “we keep label j=i-1 to our right, and label i to our left, when we move in the direction of the edge”. Formally, if σ = {z⃗_0, z⃗_1, z⃗_2} and σ'={z⃗_1, z⃗_2} are connected by an edge, where λ(z⃗_1)=i and λ(z⃗_2)=j, then write z⃗_0=α_i u⃗_i+α_j u⃗_j, z⃗_1=β_i u⃗_i+β_j u⃗_j and z⃗_2=γ_i u⃗_i+γ_j u⃗_j. Construct the matrix
    
    M= [α_i-β_i   α_i -γ_i
    α_j-β_j   α_j - γ_j]

    If M > 0, then the edge is incoming into σ. If M < 0, then the edge is outgoing out of σ. Notice that M ≠ 0, because σ is a simplex. Furthermore, note that the determinant of the matrix does not change if we switch both i and j, and z⃗_1 and z⃗_2 (i.e., β and γ). Thus, the direction is well-defined.

If σ' corresponds to a vertex of type (b), then we apply the rule above to σ and τ instead.




  Based on the description of the edges in the graph G we can prove the following
Lemmas which complete the proof of k-Polygon Tucker's Lemma.

 
    The vertex that corresponds to the simplex {0⃗}∈ T has out-degree 1 
  and in-degree 0.



    Since {0⃗} is a 0-dimensional simplex, it does not have any sub-simplices
  and hence it can only be connected to a 1-dimensional simplex, i.e., an edge. An
  edge ψ∈ T that is not contained in a linear segment of the form
  ({0⃗, u⃗_i}) cannot be a neighbor of {0⃗}, because it requires
  two labels to become happy and {0⃗} has only one single label. 
  Hence, {0⃗} can only be connected to a 1-dimensional simplex {0⃗, z⃗_i} contained 
  in ({0⃗, u⃗_i}) for some i. 
  Observe also that S({0⃗, z⃗_i}) = {i}, which implies that
  S({0⃗, z⃗_i}) = {λ(0⃗)}. Therefore, there is exactly one 1-dimensional 
  simplex that is connected to {0⃗}, namely {0⃗, z⃗_i}, where i = λ(0⃗).
  
  Furthermore, since {0⃗} and its neighbor {0⃗, z⃗_i} lie in ({0⃗, u⃗_i}), the edge is directed away from {0⃗}. Formally, if we write z⃗_i = α_i u_i and 0⃗= β_i u_i, it will hold that α_i-β_i = α_i > 0. This means that the edge is incoming into {0⃗, z⃗_i} and the lemma follows.


 
    Any vertex v in G that is imbalanced modulo-k, i.e.,
  (𝗈𝗎𝗍-𝖽𝖾𝗀𝗋𝖾𝖾(v)) ≠ (𝗂𝗇-𝖽𝖾𝗀𝗋𝖾𝖾(v)) k 
  and does not correspond to the simplex {0⃗}, corresponds to a simplex σ
  that is either trichromatic or λ(σ) ⊈{i, i+1} for all i ∈ [k].



    For this proof, we  consider all three cases for the dimension of the 
  simplex σ^⋆ that corresponds to an imbalanced node of G separately.
  Dimension of σ^⋆ is 0. In this case, σ^⋆ = {z⃗^⋆}. It is easy to see that
  σ^⋆ cannot make happy any 2-dimensional simplex since a  
  2-dimensional simplex σ has |S(σ)| = 2. So, σ^⋆ can only 
  be a neighbor of a 1-dimensional simplex ψ. Additionally, σ^⋆ cannot make happy
  any 1-dimensional ψ such that |S(ψ)| = 2. Thus, a neighbor of σ^⋆
  should be contained in the segment
  ({0⃗, u⃗_i}) where i is such that λ(σ^⋆) = i. If
  z⃗^⋆≠u⃗_i, then σ^⋆ is connected to both of its
  two neighboring 1-dimensional simplices in the segment ({0⃗, u⃗_i}). Then, since the edges are directed away from 0⃗, σ^⋆ has one incoming and one outgoing edge. Formally, let {z⃗_0, z⃗^*} and {z⃗^*,z⃗_0'} be the two neighboring 1-dimensional simplices, and write z⃗_0 = α_i u_i, z⃗_0' = α_i' u_i and z⃗^* = β_i u_i. It is easy to see that α_i-β_i and α_i'-β_i always have opposite signs, since z⃗_0 and z⃗_0' lie on opposite sides of z^⋆ on ({0⃗, u⃗_i}).
  
  If z⃗^⋆ = u⃗_i, then from the
  definition of relevant vertices of G we have that z⃗^⋆ = u⃗_1 and {u⃗_1} is happy, i.e., λ(u⃗_1)=1. Thus, by the boundary conditions, for every t ∈ [k], it holds that λ(θ_k^(t)(u⃗_1)) = t + 1. In other words, λ(u⃗_i) = i for all i ∈ [k]. As a result, it follows that for each i ∈ [k], {u⃗_1} has an edge with the simplex {u⃗_i, z⃗_i} which lies in ({0⃗,u⃗_i}). This holds because θ_k^(i)({u⃗_1}) suffices to make {u⃗_i, z⃗_i} happy. Clearly, θ_k^(i)({u⃗_1}) cannot make any other simplex happy, by the same arguments as above. Finally, note that all the edges are incoming into {u⃗_1}, because edges are directed away from 0⃗ on any ({0⃗,u⃗_i}). Formally, if we write z⃗_i = α_i u_i and u⃗_i = β_i u_i, then we always have α_i - β_i = α_i -1 < 0, so the edge is outgoing out of {u⃗_i,z⃗_i}. Thus, in this case, z⃗^⋆ has k neighbors and all of them with the 
  same direction. Therefore, z⃗^⋆ is always balanced modulo-k. In conclusion, an
  imbalanced vertex of G different from {0⃗} cannot have dimension 0.
  Dimension of σ^⋆ is 1. First, assume 
  that σ^⋆ = {z⃗^⋆_1, z⃗^⋆_2} belongs to
  one of the line segments ({0⃗, u⃗_i}). If additionally 
  λ(z⃗^⋆_1) = λ(z⃗^⋆_2), then σ^⋆
  is happy if
  λ(z⃗^⋆_1) = λ(z⃗^⋆_2) = i. Therefore,
  λ(σ^⋆) = 1 and hence σ^⋆ cannot be a neighbor of a
  2-dimensional σ since S(σ) = 2 and σ^⋆
  cannot make σ happy. So, σ^⋆ has exactly the two neighbors 
  {z⃗^⋆_1} and {z⃗^⋆_2} since both of them make 
  σ^⋆ happy. Furthermore, the vertex is balanced, because one of the edges is incoming and the other one is outgoing, since edges are directed away from 0⃗ on ({0⃗, u⃗_i}). Formally, if we write z⃗^⋆_1 = α_i u_i and z⃗^⋆_2 = α_i' u_i, then α_i -α_i' and α_i'-α_i always have opposite signs.
  
  The next case we consider is when
  σ^⋆⊆({0⃗, u⃗_i}) with
  i = λ(z⃗^⋆_1) ≠λ(z⃗^⋆_2) = j. If 
  i - j ≠± 1, then σ^⋆ yields a solution to k-Polygon Tucker, and so is allowed to be imbalanced. On the other hand, if j = i ± 1 k, σ^⋆ has
  exactly two neighbors, the simplex {z⃗^⋆_1}, which makes
  σ^⋆ happy, and the unique 2-dimensional simplex σ = {z⃗^⋆_1, z⃗^⋆_2, z⃗_3} that contains σ^⋆ as a face
   and is contained in the cone 
  ({u⃗_i, 0⃗, u⃗_j}). Also, one of the edges is incoming and other one outgoing and hence σ^⋆ cannot be imbalanced. Formally, write z⃗_2^⋆ = β_i u_i, z⃗_1^⋆ = β_i' u_i and z⃗_3 = α_i u_i + α_j u_j. Then, it holds that the edge goes from {z⃗^⋆_1} to {z⃗^⋆_1,z⃗^⋆_2} if β_i'-β_i > 0, and otherwise in the other direction. Furthermore, the edge goes from σ = {z⃗^⋆_1, z⃗^⋆_2} to σ = {z⃗^⋆_1, z⃗^⋆_2, z⃗_3}, if M > 0, where we can compute that M = (α_i-β_i) α_j - (α_i-β_i')α_j = α_j (β_i'-β_i). Since α_j > 0, it follows that both expressions have the same sign, and thus σ^⋆ is balanced.
  
    The final case for 1-dimensional σ^⋆ is when 
  σ^⋆ is not contained in any line segment of the form
  ({0⃗, u⃗_i}). Let σ^⋆
  be contained in the cone ({u⃗_⃗i⃗, 0⃗, u⃗_i+1}). If σ^⋆
  is not relevant, then it cannot be imbalanced. To be relevant, and hence happy, it must hold that
  λ(z⃗^⋆_1) = i and λ(z⃗^⋆_2) = i+1. If 
  σ^⋆ is not in the boundary ∂ T, then
  σ^⋆ is the face of exactly two 2-dimensional simplices 
  σ, σ' that are both contained in 
  ({u⃗_i, 0⃗, u⃗_i + 1}). Therefore, σ^⋆ makes
  happy both of them and no other simplex, and consequently it has an edge with both of them and no other edge. Furthermore, one of the edges is incoming and other one is outgoing (from the perspective of σ^⋆), so it cannot be imbalanced. Intuitively, if we let σ={z⃗^⋆_1,z⃗^⋆_2,z⃗_3} and σ'={z⃗^⋆_1,z⃗^⋆_2,z⃗_3'}, then z⃗_3 and z⃗_3' lie on opposite sides of the line defined by {z⃗^⋆_1,z⃗^⋆_2}. Thus, the basis of ℝ^2 defined by {z⃗_3-z⃗^⋆_1, z⃗_3-z⃗^⋆_2} has opposite orientation compared to the basis {z⃗_3'-z⃗^⋆_1, z⃗_3'-z⃗^⋆_2}. As a result, M will have a different sign for the two edges. For a formal proof of this, we refer to the proof of <ref>, where we prove a more general version of this fact.
  
  
  If 
  σ^⋆∈∂ T, then σ^⋆ is relevant only if
  σ^⋆⊆({u⃗_1, u⃗_2}). In this case, σ^⋆ has exactly k neighbors each 
   of which is a 2-dimensional simplex that has as a face one of the k 
  symmetric copies of σ^⋆. Namely, the neighbors of σ^⋆ are σ_1, …, σ_k, where θ_k^(i)(σ^⋆) makes σ_i happy for all i ∈ [k]. To see that all k edges are incoming or all are outgoing, notice that if we have 1 to our right and 2 to our left when we reach the boundary, then it will hold that we have i on our right and i+1 on our left when we reach the boundary at the corresponding position in cone ({0⃗,u⃗_i,u⃗_i+1}). More formally, the sign of the determinant of the matrix M(σ_i, θ_k^(i)(σ^⋆)) constructed to determine the direction of the edge with σ_i, will be the same for all i ∈ [k]. For a full formal proof, we again  refer to the proof of <ref>.
  
  
  
  Dimension of σ^⋆ is 2. Let 
  σ^⋆ = ({z⃗^⋆_1, z⃗^⋆_2, z⃗^⋆_3}).
  Assume that σ^⋆ is contained in the simplex 
  ({u⃗_i, 0⃗, u⃗_j}), with j = i ± 1 k and
  without loss of generality λ(z⃗^⋆_1) = i, 
  λ(z⃗^⋆_2) = j. If λ(z⃗^⋆_3) ∉{i, j} 
  then σ^⋆ is a trichromatic triangle, and thus it can be imbalanced. 
  Assume that
  λ(z⃗^⋆_3) ∈{i, j} and without loss of generality 
  λ(z⃗^⋆_3) = i. In this case, σ^⋆ has exactly two 
  neighbors: the 1-dimensional simplices ψ_1 = ({z⃗^⋆_1, z⃗^⋆_2}) and
  ψ_2 = ({z⃗^⋆_3, z⃗^⋆_2}). Once again, one edge is incoming and the other one is outgoing, and thus σ^⋆ is balanced. Intuitively, this follows from the fact that if we move with i to our left and j to our right, then we can “enter” the simplex from one side, and “exit” from the other one. More formally, if we write z⃗^⋆_1 = α_i u_i + α_j u_j, z⃗^⋆_2 = β_i u_i + β_j u_j and z⃗^⋆_3 = α_i' u_i + α_j' u_j, then it holds that:
  
    [ α_i-β_i   α_i-α_i'
    α_j - β_j   α_j - α_j'] = - [ α_i'-β_i   α_i'-α_i
    α_j' - β_j   α_j' - α_j]

  by using standard rules about the determinant.
 
  Hence, the only imbalanced vertices different from {0⃗} correspond to either trichromatic simplices or
  simplices such that λ(σ) ⊈{i, i+1} for all i ∈ [k].


  Finally, from the definition of the graph G and 
<ref>, we have that there has to be a vertex in
G that is imbalanced k and different from {0⃗}. By
<ref>, any such vertex proves
the validity of k-Polygon Tucker's Lemma.



  §.§.§ Computational Problems and Containment in k[#1]
 

  In this section, we define the computational problems associated with
k-Polygon Tucker's Lemma and the k-Polygon Borsuk-Ulam Theorem, which we call 
k and k respectively. Following the ideas 
presented in <ref>, we show that k
is in k[#1]. The membership of k in k[#1] combined with the results of
<ref> implies that 
k is also in k[#1].

  To define the computational problem associated with k-Polygon Tucker's Lemma we
need succinct access to the labels λ(x⃗) for the vertices x⃗ in
a nice triangulation T of W_k. This succinct access resembles the one in the 
definition of the computational version of the original Borsuk-Ulam Theorem
<cit.> and the computational version 
of Brouwer's Fixed Point Theorem <cit.>. To define
this succinct access, we fix for any m ∈ℕ a triangulation T(m) with 
 diameter (i.e., max distance between two vertices of a simplex)  at most 1/2^m, where we can refer to a
simplex in T(m) using O(m + k) bits. For our case this triangulation will be the 
following.


    For every m ∈ℕ, we define T(m) to be the following nice 
  triangulation of W_k. Starting from T^⋆ (see  
  <ref>) we define a simplicial complex 
  T_i(m) of every simplex 
  σ^⋆_i = ({u⃗_i, 0⃗, u⃗_i + 1 k}) and 
  then  set T(m) = ∪_i ∈ [k]T_i(m). To define T_i(m), we 
  divide the edges ψ^i_1 = ({u⃗_i, 0⃗}), 
  ψ^i_2 = ({u⃗_i, u⃗_i + 1 k}) and
  ψ^i_3 = ({0⃗, u⃗_i + 1 k}) of σ^⋆_i equally into
  2^m + 1 intervals. Then, from any endpoint of the subintervals of the edge 
  ψ^i_2 we consider the lines that are parallel to either ψ^i_1 or ψ^i_3
  and from any endpoint of the subintervals in ψ_1^i and ψ_3^i we consider the line that is parallel
  to ψ^i_2, as shown in <ref>.  We define T_i(m) to be the
  set of simplices that are created by these lines and lie inside σ^⋆_i. Namely, the intersection points and endpoints of subintervals  are the 0-dimensional simplices in T_i(m), the line segments and the triangles between 0-dimensional simplices are also simplices in T_i(m). It is simple to see that T(m) is nice;  we call T(m) an edge parallel triangulation of W_k.


For the edge parallel triangulation T(m) of W_k the following facts are
easy to verify.

 
    The diameter of T(m) is at most 1/2^m.


 
    We can indicate uniquely a simplex 
  σ^⋆_i using ⌈log(k) ⌉ bits. Then, using 2 m + 3 bits we can indicate uniquely a combination of
  two lines: (1) one of the 2 · 2^m + 1 lines that are parallel to either
  ψ^i_1 or ψ^i_3, and (2) one of the 2^m + 1 lines that are parallel to
  ψ^i_2. This combination uniquely determines a point x⃗∈ℝ^2
  and we can efficiently check whether this point belongs to σ^⋆_i or 
  not. Of course this way the points that lie on the rays from 0⃗ to u⃗_i have two different representations but we can easily resolve this discrepancy by choosing as valid only the representation that is lexicographically first. Hence,  we can uniquely determine any vertex in
  T(m) with b = ⌈log(k) ⌉ + 2 m + 3 bits.


 
    Given a set of binary vectors A = {a⃗_i}_i where 
  a⃗_i ∈{0, 1}^b, there exists an efficient procedure that determines
  whether (A) is a simplex of T(m) or not.  


  Because of <ref>, we can assume that the labeling
λ of T(m) is given via a circuit ℒ with 
b = ⌈log(k) ⌉ + 2 m + 3 input bits and ⌈log(k) ⌉ output bits. The input to the
circuit ℒ is the representation of a potential vertex x⃗ in T(m) according to <ref> 
and the output is the label λ(x) ∈ [k] of this vertex x⃗. Observe that <ref> also guarantees that it is easy to check whether
an input a⃗∈{0, 1}^b to the circuit ℒ corresponds to a valid
vertex x⃗∈T(m). We are now ready to define the 
 total search problem that is associated with k-Polygon Tucker's Lemma.



    
k 


Input: A circuit ℒ : {0, 1}^b →{0, 1}^⌈log(k) ⌉,
with b = ⌈log(k) ⌉ + 2 m + 3.


Output: One of the following.



    
  * Two binary vectors a⃗_1, a⃗_2 ∈{0, 1}^b such that a⃗_1, 
    a⃗_2 correspond to vertices x⃗_1, x⃗_2 on ∂T(m) with 
    x⃗_2 = θ_k(x⃗_1), but ℒ(a⃗_2) ≠ℒ(a⃗_1) + 1 k.
    

    
  * Three binary vectors a⃗_1, a⃗_2, a⃗_3 ∈{0, 1}^b such 
    that the simplex σ = ({a⃗_1, a⃗_2, a⃗_3}) belongs to
    T(m) and all the labels ℒ(a⃗_1),
    ℒ(a⃗_2), ℒ(a⃗_3) are different from each other.
    

    
  * Two binary vectors a⃗_1, a⃗_2 ∈{0, 1}^b such that the
    edge ψ = ({a⃗_1, a⃗_2}) belongs to T(m) and labels
    ℒ(a⃗_1), ℒ(a⃗_2) are different and they satisfy ℒ(a⃗_1) - ℒ(a⃗_2) ≠± 1 k.





 
    It holds that k is in k[#1].



    This lemma follows from the proof of k-Polygon Tucker's Lemma that we 
  presented in <ref>. We only need to
  add the description of the circuits 𝒮, 
  𝒫 that define the graph G constructed in the proof. Then, using these circuits
  we reduce k to 
  k[#1]. As we showed in <ref>,
  every solution to the resulting instance of k[#1] corresponds to a solution
  of k. Hence, k is in k[#1].
  
    Since the vertices of the graph G correspond to simplices in T(m) and 
  the maximum degree of any node in G is k, we define the circuits 𝒮,
  𝒫 to have 3 · b binary inputs and k · (3 b) outputs, hence
  𝒮 : {0, 1}^3 b→ ({0, 1}^3 b)^k and 
  𝒫 : {0, 1}^3 b→ ({0, 1}^3 b)^k. For the construction of the circuits, both
  𝒮 and 𝒫 first check whether an input 
  (a⃗_1, a⃗_2, a⃗_3) is valid or not. An input 
  (a⃗_1, a⃗_2, a⃗_3) is valid in the following cases.
  
    
  ▹ If all a⃗_1, a⃗_2, a⃗_3 are different, 
    then (a⃗_1, a⃗_2, a⃗_3) is valid if
    a⃗_1, a⃗_2, a⃗_3 are in lexicographical order and the simplex
    ({x⃗_1, x⃗_2, x⃗_3}), where x⃗_i is the point in 
    ℝ^2 that corresponds to a⃗_i according to <ref>, is a valid simplex of T(m).
    Observe that we can check this using a polynomial size circuit by <ref>.
    
  ▹ If  {a⃗_1, a⃗_2, a⃗_3} has two
    different vectors, then (a⃗_1, a⃗_2, a⃗_3) is valid if
    the lexicographically first is a⃗_1, the lexicographically second is
    a⃗_2 = a⃗_3 and the edge
    ({x⃗_1, x⃗_2}), where x⃗_i is the point in 
    ℝ^2 that corresponds to a⃗_i according to <ref>, is a valid simplex of T(m). Observe
    that we can check this using a polynomial size circuit by <ref>.
    
  ▹ If a⃗_1 = a⃗_2 = a⃗_3, then (a⃗_1, a⃗_2, a⃗_3) is valid if the point 
    x⃗_1 in ℝ^2 that corresponds to a⃗_1 according to <ref> is a valid vertex of T(m). Observe
    that we can check this using a polynomial size circuit by <ref>.
  
  
    If input 
  (a⃗_1, a⃗_2, a⃗_3) is not valid, then both circuits 
  𝒮 and 𝒫 output (a⃗_1, a⃗_2, a⃗_3) 
  concatenated with itself k times. On the other hand, if 
  (a⃗_1, a⃗_2, a⃗_3) is valid, then both circuits check whether
  this input corresponds to a relevant simplex as we defined in  
  <ref>. It is easy to see that checking relevance can 
  be done efficiently. Again, if 
  (a⃗_1, a⃗_2, a⃗_3) is not relevant, both circuits 𝒮
  and 𝒫 output (a⃗_1, a⃗_2, a⃗_3) concatenated with
  itself k times. Finally, if (a⃗_1, a⃗_2, a⃗_3) is valid and 
  relevant, then we define the edges of the corresponding vertex in G as described
  in <ref>. From the construction of G, it follows that 
  the successors and the predecessors can be computed efficiently. If the
  vertex in G that corresponds to (a⃗_1, a⃗_2, a⃗_3) has less than
  k incoming or outgoing edges, then we repeat the lexicographically last neighboring
  vertex enough times such that the number of bits in the output of both 𝒮
  and 𝒫 is k · (3 b).
  
    Using our analysis in <ref>, it follows that the above 
  construction of 𝒮 and 𝒫 defines a reduction from 
  k to k1.






We now define the computational problem associated with the k-Polygon Borsuk-Ulam
Theorem. For this
computational problem we need a representation of the continuous function f that is
the input to the k-Polygon Borsuk-Ulam Theorem. Following standard techniques in
the literature, we use arithmetic circuits with gates ×ζ (multiplication by a constant), +, -, <, min, and 
max and rational constants to define this function.






    
k 


Input: An arithmetic circuit 𝒞 : B^2 →^2, an
accuracy parameter ε > 0 and a Lipschitz-constant L.


Output: One of the following.



    
  * A point ∈ S^1 such that 𝒞(θ_k()) - θ_k(𝒞())≥η(ε,k) := ε/8 k^4.
    

    
  * Two points , ∈ B^2 such that 𝒞()-𝒞() > L -.
    

    
  * A point ^* ∈ B^2 such that 𝒞(^*)≤ε.




The first type of solution corresponds to a violation of the boundary conditions. Since we cannot compute θ_k exactly, we let θ̃_k denote a function that computes θ_k with error at most ξ(ε,L,k) := ε/2^7 L k^4. The second type of solution corresponds to a violation of L-Lipschitz-continuity. Note that the function computed by the circuit 𝒞 might not be continuous, because of the comparison gate. Thus we add this extra violation, which ensures that the function is Lipschitz-continuous. This allows us to relate this problem to k (and in particular to show that it always has a solution).




 
    The problem k reduces to the problem k. 
  Therefore, k is in k.



  This result is obtained by following the idea of the proof of
<ref>, and constructing a labeling
ℒ that uses the circuit 𝒞 as a sub-routine to compute
the labels of the corresponding k instance. The details are a
bit tricky because we have to account for small errors in various computations.

In more detail, the regular procedure for picking a label at some point is to first compute an approximate value of its coordinates and then based on this to compute an approximate value of the function. However, this might introduce bogus boundary condition violations, even if the function perfectly satisfies the boundary conditions. We can resolve this as follows. For any vertex  that lies on the boundary, but not between _1 and _2, we first check how far away the label obtained through the regular procedure is from the label that satisfies the boundary condition. If it happens that the regular procedure is close to outputting the label that does not violate the boundary conditions then we enforce the output of this label and ignore the output of the regular procedure. Otherwise, we output the label of the regular procedure. Then, we can show that from any solution of k-Polygon Tucker we can either extract an approximate zero of 𝒞, or a violation of the boundary conditions of 𝒞 (in their approximate version), or a violation of Lipschitz continuity.

  We will use the triangulation T(m) where m is picked
sufficiently small so that the diameter of the triangulation when mapped to
B^2 by the homeomorphism is at most δ=ε/2^7 L k^4. The Boolean circuit
computing ℒ performs the following operations. Recall that the input
to the circuit is the bits representing the index of the vertex 
∈ W_k of the triangulation, as per <ref>.

    
  * Let ∈ B^2 denote the image of  under the homeomorphism
    used in the proof of <ref>.
    Compute an approximation  of  with error at most 
    η_1 = δ = ε/2^7 L k^4, i.e., - ≤η_1. Note this
    is done in two steps, first compute an approximate value for the coordinates
    of , which is given through its index, and compute an approximate value
    of the homeomorphism given the approximate value of the coordinates of 
    . These steps can be done efficiently by using standard techniques 
    <cit.> so that the total approximation error is η_1.
    
  * Compute 𝒞() exactly.
    
  * For each i ∈ [k], compute an estimate v_i() of the 
    inner product ⟨𝒞(), _i ⟩ with error
    at most η_2 = ε/64 k^4, where the approximation error is introduced
    in computing the coordinates of _i.
    
  * If ∉∂T(m) or if 
    ∈({_1, _2}) ∖{_2}, then output 
    the label _i v_i() (break ties arbitrarily but
    deterministically, e.g., lexicographically).
    
  * Otherwise, there exists ℓ∈ [k-1] and a vertex 
    ' ∈({_1, _2}) ∖{_2}, such that 
    = θ_k^ℓ ('). In that case, compute 
    r = max_i v_i() and j = ℒ(') + ℓ k. Let η_3 = ε/16 k^4 (3 + k).
    If r - v_j() ≤η_3 
    then output 
    ℒ(') + ℓ k, otherwise output
    _i v_i() (again break ties arbitrarily but 
    deterministically, e.g., lexicographically).


We will use the following useful invariant: if vertex  has label j, then

    ⟨𝒞(), _j ⟩≥max_i ⟨𝒞(), _i ⟩ - 2η_2 - η_3.

This follows from our labeling procedure.

We begin by considering standard solutions of k and distinguish between
the cases k = 3 and k > 3. The other type of solution, namely boundary violations are treated for any k ≥ 3 at the end of the proof.



  
k = 3. In this case a standard solution to ℒ 
consists of a simplex with vertices _1, _2, _3 that have labels
1, 2, 3 respectively. Let _1, _2, _3 denote
the corresponding points computed in the aforementioned step 1. of the 
computation of ℒ with input _1, _2, _3 respectively. Assume that 𝒞(_i)≥ε for 
i = 1, 2, 3, since we have found a solution otherwise.
Using elementary linear algebra, it is easy to show that for any 
∈ B^2 with 𝒞()≥ε, it
holds that 
max_i ⟨𝒞(), _i ⟩≥ε/2 and
min_i ⟨𝒞(), _i ⟩≤ -ε/2.

Let j = _i ⟨𝒞(_1), _i ⟩. Then it follows that ⟨𝒞(_1), _j ⟩≤ -ε/2, which
implies that 
⟨𝒞(_j), _j ⟩≤ -ε/4, since

    |⟨𝒞(_1), _j ⟩ - ⟨𝒞(_j), _j⟩| ≤𝒞(_1) - 𝒞(_j)≤ L _1 - _j≤ L(δ+2η_1) ≤ε/4

unless _1 and _j yield a violation of L-Lipschitz continuity of 𝒞, in which case we have found a solution. Now, recall that _j has label j. By the invariant, it must hold that ⟨𝒞(_j), _j ⟩≥max_i ⟨𝒞(_j), _i ⟩ - 2η_2 - η_3. But since max_i ⟨𝒞(_j), _i ⟩≥ε/2, this means that ⟨𝒞(_j), _j ⟩≥ε/2 - 2η_2 - η_3, which contradicts the fact that ⟨𝒞(_j), _j ⟩≤ -ε/4.




  
k > 3. In this case a solution to ℒ consists of an edge _1,_2 of the triangulation such that the two vertices have labels j_1,j_2 that differ by more than one. Assume that 𝒞(_1)≥ε and 𝒞(_2)≥ε. Note that _1 lies in some cone ({0,_t,_t+1}). By elementary linear algebra, one can show that

    max_i ∈{t,t+1}⟨𝒞(_1), _i ⟩ - max_i ∉{t,t+1}⟨𝒞(_1), _i ⟩≥ε/2(1-cos(2π/k)) ≥ε/k^3

Since ε/k^3≥η_3+2η_2, it follows that the label j_1 of x_1 must be one of t or t+1. As a result, j_2 ∉{t,t+1}, since it cannot be adjacent to j_1. Furthermore, since j_1 was picked as the label of x_1, by the invariant it holds that ⟨𝒞(_1), _j_1⟩≥max_i ⟨𝒞(_1), _i ⟩ - 2η_2 - η_3. Together with equation (<ref>), it follows that

    ⟨𝒞(_1), _j_1⟩ - ⟨𝒞(_1), _j_2⟩≥ε/k^3 -2η_2-η_3.

On the other hand, since x_2 has label j_2, this means that

    ⟨𝒞(_2), _j_1⟩ - ⟨𝒞(_2), _j_2⟩≤ 2η_2 + η_3.

As a result, it must be that 𝒞(_1) - 𝒞(_2)≥ε/2k^3 - 2η_2 - η_3. Note that this is a violation of Lipschitz continuity, since normally we should have

    𝒞(_1) - 𝒞(_2)≤ L _1 - _2≤ L (δ + 2 η_1)

and this quantity is smaller than ε/2k^3 - 2η_2 - η_3.



  
Boundary violations.
  Let  be a violation of the boundary conditions, i.e., the label at vertex
 is j_1, and the label at θ_k () is j_2 ≠ j_1 + 1  k.
This means that at least one of the two vertices did not obtain its “intended”
label. Without loss of generality, assume that  has not obtained
its intended label. Let ℓ∈ [k - 1] and 
_0 ∈({_1,_2}) ∖{_2} be such that
θ_k^ℓ(_0) =. Since  did not obtain its “intended” label,
it follows that max_i v_i() - v_j() > η_3, where 
 is the corresponding point in B^2 computed in step 1. This
implies that

    max_i ⟨𝒞(), _i ⟩ - ⟨𝒞(), _j ⟩ > η_3 - 2η_2.

On the other hand, since 
_0 ∈({_1,_2}) ∖{_2} has label 
j - ℓ k, it holds that

    max_i ⟨𝒞(_0), _i ⟩ - ⟨𝒞(_0), _j-ℓ k⟩≤ 2 η_2.

where _0 is the corresponding point of _0 in B^2 
computed in step 1. By noting that

    max_i ⟨𝒞(_0), _i ⟩ - ⟨𝒞(_0), _j-ℓ k⟩ = max_i ⟨θ_k^ℓ(𝒞(_0)), _i ⟩ - ⟨θ_k^ℓ(𝒞(_0)), _j ⟩

we thus obtain that there exists i ∈ [k] such that

    |⟨𝒞(), _i ⟩ - ⟨θ_k^ℓ(𝒞(_0)), _i ⟩| > (η_3-4η_2)/2.

This implies that 𝒞() - θ_k^ℓ(𝒞(_0))≥ (η_3-4η_2)/2. Since

    𝒞() - θ_k^ℓ(𝒞(_0)) = ∑_i=0^ℓ-1θ_k^i𝒞(θ_k^-i()) - θ_k^i+1(𝒞(θ_k^ℓ-i-1(_0)))

it follows that there exists i ∈{0,1,…, ℓ-1} such that 

    θ_k^i𝒞(θ_k^-i()) - θ_k^i+1(𝒞(θ_k^ℓ-i-1(_0)))≥ (η_3-4η_2)/(2k).


Now let ^*= θ_k^ℓ-i-1(_0). Then ^*
yields a violation of the boundary conditions for 𝒞 by noting that

    𝒞(θ̃_k(^*)) - θ̃_k(𝒞(^*))   ≥ (η_3-4η_2)/(2k) - 𝒞(θ̃_̃k̃(^*)) - 𝒞(θ_k(^*)) - θ̃_̃k̃(𝒞(^*)) - θ_k(𝒞(^*))
       ≥ (η_3-4η_2)/(2k) - L(2η_1+ξ(ε,L,k)) - ξ(ε,L,k)

unless we find a violation of Lipschitz continuity. Indeed, note that
(η_3-4η_2)/(2k) - L(2η_1+ξ(ε,L,k)) - ξ(ε,L,k) ≥η(ε,k).






 §.§ k-Polygon Borsuk-Ulam and k-Polygon Tucker are k[#1]-hard



  In this section we show the k[#1]-hardness of both k and
k. We start by observing that 
using the ideas from <ref> we
can prove that k is reducible to k. Then we show 
that k is k[#1]-hard. Finally the results of this section
together with the results of the previous 
<ref> imply that both 
k and k are k[#1]-complete.

 
    The problem k reduces to the problem k.



  This Lemma follows from the proof of <ref> combined with standard 
  arguments on how to construct an arithmetic circuit approximately computing the piecewise linear function g: B^2 →^2 described in <ref>. Recall that the function g is constructed by interpolating within simplices of the triangulation using the labels given by ℒ. Given a precision parameter γ and the Boolean circuit ℒ, we can construct an arithmetic circuit 𝒞 that computes the function g with error at most γ, using standard techniques <cit.>. To be more precise, we can invoke Theorem E.2 from <cit.> by observing that the function g is polynomially approximately computable via standard numerical analysis techniques <cit.>. Furthermore, the function computed by 𝒞 will be Lipschitz-continuous with a Lipschitz constant L̃ that has bit-size polynomial in m and log (1/γ) (where m is the parameter of the triangulation used by ℒ).
  
  For any ∈ B^2 that does not lie in a simplex that is a solution of ℒ, it must hold that g()≥ 1/2. This can easily be shown by taking into account that at most two labels (that are also adjacent) are used for the interpolation in that case. As a result, as long as we ensure that 1/2-γ > ε, any point with 𝒞()≤ε will yield a solution of the k instance.
  
  It remains to show that no bogus boundary condition violations occur. Note that unless the simplex containing ∈∂ B^2 yields a boundary condition violation for ℒ, it must hold that g(θ_k()) = θ_k(g()) (as shown in <ref>). Thus, it follows that
  
    𝒞(θ̃_k()) - θ̃_k (𝒞())   ≤𝒞(θ_k()) - θ_k(𝒞()) + 𝒞(θ̃_k()) - 𝒞(θ_k()) + θ̃_k (𝒞()) - θ_k(𝒞())
       ≤ 2 γ + L̃·ξ(ε,L,k) + ξ(ε,L,k).

  Note that we want this quantity to be strictly less than η(ε,k). Thus, we pick ε=1/4 and then set γ and L so that

      
  * L ≥L̃,
      
  * γ < 1/2 - ε,
      
  * 2 γ + L̃·ξ(ε,L,k) + ξ(ε,L,k) < η(ε,k),

which can easily be achieved by picking γ sufficiently small and L sufficiently large. Note that since 𝒞 is L̃-Lipschitz-continuous, it will also be L-Lipschitz-continuous.








Now we present our main proposition in this section.
  

For all k ≥ 3, k is k[#1]-. 


Recall that k[#1] = ∩_p ∈ PF(k)p, where PF(k) denotes the set of prime factors of k.



To prove this hardness result we reduce from Bipartite-mod-k[#1] (see <ref> for the formal definition). Recall that in this problem we are given a bipartite graph on the set of nodes A ∪ B, where A = {0}×{0,1}^n and B = {1}×{0,1}^n, such that the node 00^n ∈ A has degree 1. The goal is to find any other node that has degree ≠ 0  k. All nodes have degree in {0,1,…,k} and we can assume (see e.g., <cit.>) that the circuit C which implicitly represents the bipartite graph is consistent, i.e., for all x,y we have y ∈ C(x) iff x ∈ C(y).
	
Consider the regular k-polygon W_k in ℝ^2 with the edge parallel triangulation (<ref>). For any i ∈ℤ_k let R(i,i+1) denote the triangle with endpoints {0,_i,_i+1}. In this proof we refer to nodes of the Bipartite-mod-k[#1] instance and to vertices of the triangulation of W_k.

To every node x ∈ (A ∖{00^n}) ∪ B we associate a distinct interval on the outer boundary of R(1,2), i.e., on the edge ({_1,_2}). This interval, which we denote by K_1(x), is picked such that it covers 4k vertices of the triangulation. It is easy to see that we can pick the triangulation to be fine enough so that there are indeed enough vertices on ({_1,_2}) to associate a distinct interval of 4k vertices to each node x ∈ (A ∖{00^n}) ∪ B. Since the triangulation is symmetric on the boundary with respect to θ_k, we can immediately also extend this association to the outer boundary of R(i,i+1) for all other i. In other words, for any i ∈ℤ_k and any x ∈ (A ∖{00^n}) ∪ B, we let K_i(x) = (θ_k)^i-1 (K_1(x)), which is an interval of 4k vertices on ({_i,_i+1}). Thus, for any x there are k distinct intervals on the boundary associated to it, one in each of ({_i,_i+1}), i ∈ℤ_k.

In the rest of this proof we explain how to assign a label in ℤ_k to every vertex of the triangulation so that the k boundary conditions are satisfied and any solution (i.e., a trichromatic triangle or an edge with non-consecutive labels) must contain a vertex that lies in some interval K_i(x) where x is a solution-node of Bipartite-mod-k[#1] (i.e., a node with degree ≠ 0  k). This will ensure that from any solution of the k instance we can easily obtain a solution-node of the Bipartite-mod-k[#1] instance.

We begin by defining the “environment” label for every vertex of the triangulation. This corresponds to the standard label that the vertex will have, unless we specify it otherwise in the construction. Any vertex lying in R(i,i+1) ∖({0,_i+1}) has the environment label i. Next, we define “cables”, which will be used to embed the edges of the Bipartite-mod-k[#1] instance in our construction.



  
Wires and Cables.
A “wire” has an associated label i ∈ℤ_k and it simply consists of a path of vertices in the triangulation such that all vertices on the path have the label i. A “cable” is made out of k-1 wires, where each wire has a distinct associated label. The wires are arranged in parallel inside the cable so that only wires with consecutive labels are allowed to touch. More precisely, if the cable uses labels ℤ_k ∖{i}, then the wires are arranged according to their labels in the order i+1,i+2,…,i+(k-1) from right to left, in the forward direction of the cable. Note that while wires are not directed, we can define a direction for every cable, based on the order of the wires inside the cable. A cable using the labels ℤ_k ∖{i} is only allowed to exist inside a region with environment label i. This ensures that any vertex that is adjacent to either side of the cable, and thus to the wire labeled i+1 or i+(k-1), is labeled i and does not introduce a solution. The construction of the cables ensures that the wires are “isolated” from each other and from the environment, in the sense that no solution is introduced along the cable. However, if the start or end of a cable using the labels ℤ_k ∖{i} is allowed to “touch” the environment label i, then this will necessarily yield a trichromatic triangle at that point. See <ref> for an illustration of how a cable is constructed.





It is easy to see that a cable can turn without introducing solutions. Next, let us see how a cable can transition from one environment to another. Consider a cable in environment i ∈ℤ_k, i.e., it uses the labels ℤ_k ∖{i} and lies in R(i,i+1). If the cable arrives on the boundary ({0,_i+1}) of R(i,i+1), we can transform it into a cable that uses the labels ℤ_k ∖{i+1} and continues into R(i+1,i+2), i.e., in the environment i+1, on the other side of ({0,_i+1}). Importantly, the direction of the cable does not change and we do not introduce any new solutions. This transformation of the cable is shown in <ref>. The idea is simple. Consider a cable in environment i that arrives on ({0,_i+1}) moving forward. The wires are arranged according to their labels in the order i+1,i+2,…,i+(k-1) from right to left, in the forward direction of the cable. When the cable reaches ({0,_i+1}), the right-most wire (which is labeled i+1) is dropped from the cable, i.e., it merges into the environment i+1 of R(i+1,i+2). On the other side of the cable, a new wire with label i = i+1+(k-1) is created by using the environment i of R(i,i+1). Thus, we obtain a cable with wires i+2,…,i+1+(k-1) (from right to left) in the environment i+1, as desired. It is easy to see that this construction does not introduce any new solutions, because we have ensured that non-consecutive labels do not “touch”.





When a cable starts or ends on the outer boundary of R(i,i+1), i.e., on ({_i,_i+1}), the k boundary conditions force a cable to start or end at the corresponding position in each of the regions R(j,j+1), j ∈ℤ_k ∖{i}. These k-1 cables will have the same direction as the original cable. In other words, if the cable in region R(i,i+1) ends on the outer boundary, then the k-1 corresponding cables will also end on their corresponding boundary. Similarly, if the original cable starts on the boundary, then the k-1 corresponding cables will start on their corresponding boundary.





  
Construction of the instance.
Before we begin, let us introduce the following useful terminology.
Every node x of the Bipartite-mod-k[#1] instance has some number ℓ∈{0,1,…, k} of neighbors, as given by C(x). For any i ∈ [ℓ], we define the “ith neighbor of x” to be the ith node in the lexicographically ordered list of neighbors of x.

We are now ready to begin describing the instance we construct.
Recall that we have defined an environment label for every vertex of the triangulation except 0. Now consider the labeling where every vertex is simply labeled by its environment label. Clearly, this labeling satisfies the k boundary conditions. Furthermore, no matter how we pick the label of 0, there will be a solution there, since 0 is adjacent to all environments. Now it is easy to see that we can “move” this solution by locally modifying some of the labels. Namely, instead of having all labels meet at 0, we can instead construct a cable that uses the labels ℤ_k ∖{1} and moves into the region with environment label 1. As a result, there is no longer a solution at 0, but instead there is now a solution at the end of the cable. In more detail, every environment label except 1 yields a wire with the corresponding label and the wires are arranged into a cable that uses the labels ℤ_k ∖{1}. <ref> illustrates this construction in the case k=5.





Recall that the node 00^n ∈ A has exactly one neighbor y ∈ B. Let j ∈ [k] be the number such that 00^n is the jth neighbor of y. The cable that we just constructed at the center of the instance will be routed so that it ends at K_j(y) (a segment on the outer boundary of R(j,j+1), as defined above). Furthermore, for any x ∈ A ∖{00^n} and y ∈ B such that x and y are neighbors, there will be a cable starting at K_i(x) and ending at K_j(y), where i,j ∈ [k] are such that x is the jth neighbor of y, and y is the ith neighbor of x. This ensures that the following properties hold.

Consider a node x ∈ A ∖{00^n} that has ℓ neighbors, where ℓ∈{0,1,…,k}.
If ℓ = 0, i.e., x is an isolated node, then for all i ∈ [k] there is no cable at K_i(x). In particular, there is no k solution in any K_i(x).
If ℓ∈ [k], then for all i ∈ [ℓ] there is a cable starting at K_i(x) (and ending at some K_j(y)). For all i ∈ [k] ∖ [ℓ], there is a start of a cable at K_i(x), but the cable just stops immediately and does not go anywhere. This ensures that the k boundary conditions are satisfied, but also that there is a k solution at K_i(x) for all i ∈ [k] ∖ [ℓ] (because of an exposed end of cable). Thus, we obtain that

	
  * if ℓ∈ [k-1], there is a solution at K_i(x) for some i ∈ [k],
	
  * if ℓ∈{0,k}, then there is no solution in any K_i(x).


Similarly, consider a node y ∈ B that has ℓ neighbors, where ℓ∈{0,1,…,k}.
If ℓ = 0, i.e., y is an isolated node, then for all j ∈ [k] there is no cable at K_j(y). In particular, there is no k solution in any K_j(y).
If ℓ∈ [k], then for all j ∈ [ℓ] there is a cable ending at K_j(y) (that started at some K_i(x)). For all j ∈ [k] ∖ [ℓ], there is an end of a cable at K_j(y), but the cable just started there and does not come from anywhere else. This ensures that the k boundary conditions are satisfied, but also that there is a k solution at K_j(y) for all j ∈ [k] ∖ [ℓ] (because of an exposed start of cable). Thus, we obtain that

	
  * if ℓ∈ [k-1], there is a solution at K_j(y) for some j ∈ [k],
	
  * if ℓ∈{0,k}, then there is no solution in any K_j(y).


As a result, if the cables can indeed be constructed to connect the various K_i(x) and K_j(y) as desired, then any k solution of the instance will have to be next to some K_i(x) such that x is a solution-node or next to some K_j(y) such that y is a solution node. One immediate obstacle to routing the cables as desired is that we are working in two dimensions and it is very likely that cables will have to cross each other. Fortunately, there is a simple “trick” that has been used in prior work to resolve this issue <cit.>. Consider the following idea: cut the two cables that want to cross each other at the point of crossing. This creates two ends of cables and two starts of cables. It is easy to see that we can connect an end of cable with a start of cable, and the other end with the other start, so that no crossing occurs anymore. This modification of the cables is completely local and does not have any impact on the rest of the instance.



  
Constructing the labeling function.
Since we want to be able to construct a circuit for the labeling function, we need to be a bit more precise about the path followed by every cable. One way to achieve this is to reserve a separate “circular lane” for each pair (y,j), where y ∈ B and j ∈ [k]. A circular lane is a path of sufficient width that simply stays parallel to the outer boundary in each region R(i,i+1) and thus makes a full “circle” around the center of the domain. By picking a fine enough triangulation, we can ensure that there is a separate, disjoint circular lane L_y,j for each pair (y,j), where y ∈ B and j ∈ [k]. Then the cable going from some K_i(x) to some K_j(y) will be routed as follows. Starting at K_i(x), move perpendicularly to the outer boundary towards the inside of the domain, until the circular lane L_y,j is reached. Next, follow the lane in clockwise direction. When following the lane, the cable might have to transition from some environment to the next and this is implemented as described earlier. The cable stops following the lane when it reaches the part of the lane lying just “above” K_j(y). In other words, the cable stops following the lane when it is at the point where it can just turn left and move straight towards the boundary to end up at K_j(y), as desired. Clearly, we can pick the triangulation fine enough so that this routing is indeed well defined.

This construction has two advantages. First of all, it ensures that any crossing involves at most two cables, not more. We can then use the trick described above to locally resolve these crossings. Furthermore, it ensures that we can construct a Boolean circuit computing the labeling function. Indeed, given any vertex of the triangulation we can easily determine on which circular lane and on which path perpendicular to the outer boundary it lies. This gives us enough information to then use the Bipartite-mod-k[#1] circuit C as a sub-routine to determine whether the vertex lies on a cable and if so, how exactly the cable behaves locally (including possible crossing-avoiding trick). The circuit C only needs to be queried a constant number of times and thus the resulting circuit for the labeling will have polynomial size with respect to the size of C and n. We omit the full details, since this part of the proof is essentially the same as in prior work (see e.g., <cit.>).


  Based on the results presented in this and the previous section we get the  
following theorem.

 
    The problems k and k are both k[#1]-complete.

In particular, if k=p^r is a prime power, then k and k are p-complete.



§ THE BSS THEOREM IS P-COMPLETE



The main result of this section is the p-completeness of the computational problem associated with the BSS Theorem. We refer to this problem as p-BSS and we define it formally in <ref>. We state the main theorem of the section below.



For every prime p, the problem p-BSS is p-complete.


In order to prove the theorem, first we show that the BSS theorem is equivalent to a generalization of Tucker's Lemma, which we call , and then we define the corresponding computational problems and show that they are equivalent. Then, we show the p-completeness of , which then implies <ref>. We show the p-hardness via a reduction from the p problem, proven to be p-complete in the previous section. The membership in p is proven in <ref>, where we show that  reduces to another variant of Tucker's lemma, which we call p (<ref>), and for which we prove membership in p.  




 §.§ The BSS Theorem and Equivalent Formulations



Our notation follows that of <cit.>. 
Let p ≥ 2 prime, n ∈ℕ and let P = {(_1,_2, …, _p) ∈ (ℝ^n)^p : ∑_i=1^p _i = 0} and P_2 = {∈ P : _2 ≤ 1}.
It holds that


    P ≅ℝ^n(p-1) and  P_2 ≅  B^n(p-1).
 

Note that P is a hyperplane of ^np with dimension n(p-1). Let ℬ be an orthogonal basis of P in ^np and let ϕ:P_2 → B^n(p-1) be the function that maps ∈ P_2 to its coefficients in base ℬ. Then, ϕ is a homeomorphism of P_2 and B^n(p-1). Notice that ϕ(∂ P_2) = S^n(p-1)-1 and that ϕ and ϕ^-1 are efficiently computable. 
The same mapping shows that  P and ℝ^n(p-1) are homeomorphic. 


Let 

    θ(_1, …, _p) = (_p,_1, …, _p-2,_p-1).


The function θ has order p; namely the composition by itself p times is equal to the identity. Also,  for all i ∈{1, …, p-1} and all ∈ P ∖{0}, θ^i() ≠. In other words,  for any i < p, θ^i restricted to P ∖{0} has no fixed points. Hence, θ acts freely on P ∖{0}. It follows with a similar argument that the function θ acts freely also on P_2 ∖{0} and on ∂ P_2.




The original statement of the BSS Theorem requires the notion of CW-complexes, but since in our work we do not use CW-complexes, we will not define them formally. Intuitively, a CW-complex consists of building blocks that can be topologically glued together.

Let p be a prime, n ≥ 1 and X be a CW-complex consisting of p copies of the n(p-1)-dimensional ball glued on their boundaries.

Let α: ℝ^n(p-1)→ℝ^n(p-1) such that α = ϕ∘θ∘ϕ^-1. Note that α acts freely on ℝ^n(p-1)∖{0}, B^n(p-1)∖{0} and S^n(p-1)-1. Let ω be the extension of α on X defined as follows:

    ω(,r,q) = (α, r, q+1  p),

where (,r,q) denotes the point of the q-th ball with radius r and direction ∈ S^n(p-1)-1.

The map ω is a free action on X and the following theorem holds:


For the mapping ω and any continuous map h:X →^n,
there exists an ∈ X such that h() = h(ω) = … = h(ω^p-1).


The following equivalent formulations of <ref> are useful for defining the computational problem related to BSS.



The following statements are equivalent to the BSS Theorem:

    
  * Let g: P_2 → P be continuous and such that g(θ) = θ g() for all ∈∂ P_2. Then, there exists ∈ P_2 such that g()=0.
    
  * Let g: B^n(p-1)→ℝ^n(p-1) be continuous and such that g(α) = α g() for all ∈ S^n(p-1)-1. Then, there exists ∈ B^n(p-1) such that g()=0.





We first show that the two statements are equivalent and then that statement (2) is equivalent to <ref>.


  
(1) ⟺ (2) The equivalence follows from  P_2 ≅ B^n(p-1) and P ≅ℝ^n(p-1), as well as from the equivariance of ϕ.



  
(2) ⟺ (BSS) 
We first show that the BSS Theorem implies (2). Recall that the CW-complex X consists of p copies of B^n(p-1) with their boundaries “glued” together. 
Define h: X →ℝ^n as follows: for = (,r,i) ∈ X, let h() = [ϕ^-1∘ g ∘α^1-i (r)]_2-i∈ℝ^n, where for j ∈ℤ_p ≡ [p], [·]_j denotes the j-th component of an element in (ℝ^n)^p (i.e., [(_1, …, _p)]_j = _j). The mapping h is well-defined and continuous on the glued boundary, because for all i and ∈ S^n(p-1)-1, we have h(,1,i) = [ϕ^-1∘ g ∘α^1-i()]_2-i = [θ^1-iϕ^-1∘ g ()]_2-i = [ϕ^-1∘ g ()]_1 (which does not depend on i). Finally, note that any = (,r,1) ∈ X with h()=h(ω)= … = h(ω^p-1) yields = r∈ B^n(p-1) with [ϕ^-1∘ g()]_1=…=[ϕ^-1∘ g()]_p, which implies ϕ^-1∘ g() = 0 (by definition of P), and thus g()=0.

Conversely, (2) implies BSS.
We identify B^n(p-1) with the first ball in the CW-complex X. Given a continuous function h:X →ℝ^n, define g: B^n(p-1)→ℝ^n(p-1) by g()= ϕ(h(ω^p)-h(ω^p-1), h(ω^p-1) - h(ω^p-2), …, h(ω)-h()). It is easy to check that g(α) = α g() for all ∈ S^n(p-1)-1 by noting that ω = α for such .





 §.§ The  Lemma


In this section, we define a generalization of Tucker's Lemma, that we call the  Lemma and show that it is equivalent to the  Theorem.
The  Lemma applies to triangulations of P_2 that have some special properties. 

For j ∈ [n], let _j ∈ℝ^n be the j-th unit vector. For (i,j) ∈_p × [n], let

    ^i,j=1/2(p-1)(-_j, …, -_j, (p-1)_j, -_j, …, -_j) ∈ P

where the term (p-1)_j is in the i-th position. For each = (s_1,…, s_n) ∈ [p]^n, we define the simplex σ_ = {0}∪{^i,j s.t. for each  j ∈ [n], i ∈_p∖{s_j}}. Note that |V(σ_)| = (p-1)n + 1.


 T^* = {τ: τ⊆σ_ with ∈ [p]^n} is a triangulation  of P_2.



Let C = ((^i,j)_(i,j) ∈_p × [n]). Then, by definition of T^*, C ≅T^* . So, the lemma follows from the fact that C ≅ P_2.




We say that a triangulation T of P_2 is nice if it satisfies the following two conditions:

    
  * If σ∈ T ∩∂ P_2 then θσ∈ T.
    
  * T refines the triangulation T^* (that is, for each σ∈ T there
is τ∈ T^* with σ⊆τ ).






Let T be a nice triangulation of P_2. Let λ = (λ_1, λ_2) : V(T) →ℤ_p × [n] be a labeling such that for all ∈∂ T, λ(θ) = (λ_1()+1, λ_2()). Then, there exists a (p-1)-simplex σ of T such that λ(σ) = ℤ_p ×{j} for some j ∈ [n], where λ(σ) = {λ() : ∈ V(σ)}.






    The BSS Theorem (<ref>) implies
  the  Lemma (<ref>).



We interpret each label (i,j) ∈ℤ_p × [n] as the vector ^i,j and we set g to be the extension of λ to a piecewise linear function on P_2. Notice that g(θ) = θ g() for ∈∂ P_2.  Then, it follows from <ref> that there exists an ∈ P_2 such that g() = 0. The lemma follows by noting that any convex combination of different vectors ^i,j that equals 0 must contain p vectors ^i_1,j_1, …, ^i_p,j_p such that {i_k, j_k}_k ∈ [p] = ℤ_p ×{j}. Hence, the point  lies in a simplex with a (p-1)-dimensional face σ such that λ(σ) = ℤ_p ×{j} for some j ∈ [n]. 




    The  Lemma (<ref>) implies
  the BSS Theorem (<ref>).




We show that  implies Statement (1) of <ref>.
Using standard arguments, it suffices to show that for every ε > 0 we can find a point  such that g()_∞≤ε. 
Since g:P_2 → P is a continuous function in a compact set, it is also uniformly continuous. Thus, for every ε > 0, there exists δ such that if - '_2 < δ, then g() - g(')_∞ < ε/n. 
Assume that T is a nice triangulation of P_2 with diameter at most δ.

For any point ∈ V(T), the label λ()=(i^*,j^*) is defined as follows. For (i,j) ∈× [n], let [g()]_i,j denote the (i,j)-coordinate of g() ∈ P. First, consider the case where g() ≠0. Then, pick j^* = _j ∈ [n]max_i ∈ [p] [g()]_i,j. Break ties by picking the smallest such j. Let S = {i : [g()]_i,j^* = max_ℓ [g()]_ℓ,j^*} and pick i^* = T_p(S), where T_p is the _p-equivariant tie-breaking function of <ref>. Note that S ∉{∅, [p]}, because g() ≠0 and by the choice of j^*. If g() = 0, then if = 0, we assign an arbitrary label, and if ≠0, we use the same procedure as above but with  instead of g().

With this definition of the labeling, it is easy to check that for any ∈∂ T, we always have λ(θ) = (λ_1()+1, λ_2(x)), since g(θ) = θ g(). Hence, by <ref> there exists a σ = {_1, …, _p}∈ T and a j^* ∈ [n] such that λ(_i) = (i,j^*) for all i ∈ [p].  

The lemma follows by showing that there exists i ∈ [p] such that g(_i)_∞≤ε. First of all, note that for any ∈ P, by definition we have that g()_∞≤ n ·max_i,j [g()]_i,j. Now, assume for the sake of contradiction that g(_i)_∞ > ε for all i ∈ [p]. Then, it follows that [g(_i)]_i,j^* > ε/n for all i ∈ [p]. But by the choice of diameter for the triangulation and uniform continuity of g, this implies that [g(_1)]_i,j^* > 0 for all i ∈ [p], which contradicts _1 ∈ P.







 §.§ Computational problems: p- and p-


Motivated by <ref> and <ref>, we define the computational problems corresponding to the BSS Theorem and the  Lemma. Combining the proof ideas in <ref> and <ref>, together with some efficiency requirements of the triangulation, as per <ref>, we show that the two computational problems are polynomially equivalent.
 
As before, we assume that the input functions are represented as arithmetic circuits with operations ×ζ, +, -, <, min, and max and rational constants. Similarly to our definition of k, and for the same reasons, we will add a solution type to ensure that it is Lipschitz-continuous.





The computational analogue of the BSS theorem is based on statement (2) of <ref>. It takes as input an arithmetic circuit, which evaluates the function g: B^n(p-1)→^n(p-1). In order to deal with the polynomial-size representation of any of the solutions we allow as a solution any approximate violation of the equivariance condition of the BSS theorem, as we did with p in Section <ref>.





    
p-BSS: 



Input: An integer n ≥ 1, an accuracy parameter ε > 0, 
a Lipschitz constant L, 
and an arithmetic circuit 𝒞.


Output: 



    
  * A point ∈ S^n(p-1)-1 such that 𝒞(α) - α𝒞() > η(ε, p) := ε/8 p^4
    

    
  * Two points , ∈ B^n(p-1) such that 𝒞() - 𝒞()  > L  -
    

    
  * A point ^* ∈ B^n(p-1) such that 𝒞(^*)_∞≤ε

           
           
A valid output of the p- problem is either a point that violates the boundary condition of <ref>, two points that violate the Lipschitz-continuity or an approximate root of the function g.




The computational analogue of the  Lemma is based on <ref> and is parameterized by a “triangulation scheme” 𝒯. Namely, given an m ∈ℕ, 𝒯(m) yields a nice triangulation T with diameter at most 1/2^m. The triangulation T is given through two arithmetic circuits,  and  (see <ref>), that have size polynomial in n and m. Assume that for m =0, 𝒯 yields the ^* and ^* circuits of T^*.





    
p-[𝒯]: 



Input: An arithmetic  circuit λ that outputs a number in _p × [n]. 



Output: 



    
  * A vertex ∈∂ T such that λ(θ) ≠ (λ_1()+1, λ_2())
    

    
  * A simplex σ^* ∈ T such that λ(σ^*) = _p ×{j} for some j ∈ [n]



The valid outputs of the p- problem correspond either to points that
violate the boundary condition of <ref> or to a fully labeled simplex in T.



  
Remark: To efficiently check whether ∈∂ T, we use the ^* and ^* circuits of T^*, which exist by assumption on 𝒯 for m = 0. If ^*(^*()) does not contain 0, then by definition of T^* and the fact that T is a nice triangulation ∈∂ T.




p-[𝒯] and p- are polynomially equivalent.




First, we show that p-[𝒯] reduces to p- and then that p- reduces to p-[𝒯]. For simplicity of the presentation and in order for the main ideas to be clear we present here a proof sketch of these reductions where we assume that η(ε, p) = 0 in the p-problem. The complete proof then follows using the tedious but straightforward case analysis that we used in the proof of Lemma <ref>. 



  
p-[𝒯] ≤ p-:  Pick ε < 1/(np)^2. Define the circuit 𝒞 using the procedure described in <ref> and the homeomorphism ϕ of B^n(p-1) and P_2. Note that 𝒞 is L-Lipschitz-continuous for some L = O(2^m).
Thus, a solution of this instance of p- is:

    
  * a point ∈ S^n(p-1)-1 such that 𝒞(α) ≠α𝒞(). In this case, let σ be the simplex such that ϕ^-1() ∈σ, then there exists a vertex ∈ V(σ) such that λ(θ) ≠ (λ_1()+1, λ_2()). Observe that σ = ((ϕ^-1())) and that it has at most n(p-1)+1 vertices. Hence, we can efficiently find .
    

    
  * a point ^* ∈ B^n(p-1) such that 𝒞(^*)_∞≤ε. In this case, ϕ^-1(^*) must lie in a simplex with a fully labeled (p-1)-dimensional face; this follows from the choice of ε and the proof ideas of <ref>. Observe that ϕ^-1(𝒞(^*)) is the convex combination of at most n(p-1) + 1 different e^i,j's. Hence, there must be a vector ^i^*,j^* that appears in the convex combination with coefficient at least 1/n(p-1)+1.
    If there is an i' such that ^i',j^* does not appear in the convex combination, then ϕ^-1(𝒞(^*)) has at least one coordinate at least as large as 1/n(p-1) + 1. Hence, ϕ^-1(𝒞(^*))_2≥ϕ^-1(𝒞(^*))_∞≥1/n(p-1) + 1, which means that 𝒞(^*)_2≥1/n(p-1) + 1. This is a contradiction since it implies that  𝒞(^*)_∞≥𝒞(^*)_2/√(np)≥1/(np)^2 > ε.
    
    
    The point ϕ^-1(^*) lies in the simplex σ = ((ϕ^-1())), which has at most n(p-1) + 1 vertices. Hence, finding the (p-1)-dimensional fully labeled face can be done efficiently. 





  
p- ≤ p-[𝒯]: Set m in 𝒯 such that 1/2^m  ≤ε/n L. The labeling λ is defined as in <ref> using as function g: P_2 → P the function given by ϕ^-1∘𝒞∘ϕ, where ϕ is the homeomorphism of B^n(p-1) and P_2; note that all operations can be described with an arithmetic circuit. A solution of this instance of p-[𝒯] is:

    
  * a vertex ∈∂ T such that λ(θ) ≠ (λ_1()+1, λ_2()). In this case, it must hold that 𝒞(α∘ϕ()) ≠α𝒞(ϕ()). Thus, ϕ() is a solution of p-.
    

    
  * a simplex σ^* ∈ T such that λ(σ^*) = _p ×{j} for some j ∈ [n]. In this case, following the proof of <ref>, there exists a vertex  in σ^* such that g()_∞≤ε (or a violation of L-Lipschitz-continuity). Then, since ϕ as defined in <ref> preserves the ℓ_2 distances between P_2 and B^n(p-1), 𝒞(ϕ())_∞≤𝒞(ϕ())_2≤ε. Thus, ϕ() is a solution of p-.






In order to use Kuhn's triangulation we work on the domain C_∞ = {(c^1, …, c^p) ∈ ([0,1]^n)^p | ∀ j ∈ [n], ∃ i ∈ [p] : c^i_j = 0 } instead of P_2. These are coordinates with respect to the vectors e^i,j. Note that C_∞≅ P_∞, where P_∞ = {∑_i,j c^i_j e^i,j | (c^1, …, c^p) ∈ C_∞}, and clearly P_∞≅ P_2.

We can triangulate C_∞ by using Kuhn's triangulation (<ref>) to triangulate each cube {(c^1, …, c^p) ∈ C_∞ | ∀ j ∈ [n] : c^i_j_j = 0 } for each (i_1, …, i_n) ∈ [p]^n. By the properties of Kuhn's triangulation, it immediately follows that this yields a triangulation of C_∞. In particular, the triangulations of two cubes “match” on their common subspace. Since we constructed the triangulation separately on each cube, it follows that it refines the triangulation T^*. Furthermore, for any simplex σ lying on the boundary of C_∞, it follows that θσ is also a simplex of the triangulation. This is easy to see, because θ just changes the order of the coordinates, and the Kuhn triangulation is invariant with respect to such transformations by definition. Thus, Kuhn's triangulation is indeed a nice triangulation.





 §.§  is p-complete


Having defined the computational problems corresponding to the BSS Theorem and to , we are ready to prove <ref>. The following theorem follows from <ref>, presented in <ref>.


For any prime p, p-[𝒯] is in p. 




Next we prove that p- is p-hard, through a reduction from p.



For any prime p ≥ 3, p- is p-hard, even for fixed dimension n ≥ 1.



Note that for p=2, p- corresponds to the standard version of Tucker's lemma, which is known to be -hard for any n ≥ 2 <cit.>.


Here we prove that p- is p-hard for n=1. The hardness for any n ≥ 1 then follows from <ref>, which gives a reduction from n to n+1.

To show the hardness for n=1 we will reduce from p to p-. Instead of the triangulation we used in the presentation of p, we will use Kuhn's triangulation (<ref>). It can be shown that the hardness of p proved in <ref>, also holds if we use Kuhn's triangulation, since there is a simple homeomorphism between the two domains. We omit the details for this.

Let λ be an instance of p with Kuhn's triangulation of size m. Thus, the domain for this problem can be written as

    A = {(c_1, …, c_p) ∈ (U_m)^p | ∃ i ∈ [p], ∀ j ∉{i, i+1} : c_j = 0}.


We construct an instance of p- with n=1 on the domain C_∞ with Kuhn's triangulation of size m. Recall that the set of vertices can be written as C_∞ := {(c_1, …, c_p) ∈ U_m^p | ∃ i ∈ℤ_p : c_i = 0}. Let D := ∪_i ∈ℤ_p D_i, where D_i := {(c_1, …, c_p) ∈C_∞ | ∀ j ∉{i, i+1} : c_j = 0}.

We are going to embed the p domain A into D in the most natural way. Since we are using Kuhn's triangulation, the restriction of the triangulation of C_∞ to D corresponds to Kuhn's triangulation on that domain, and thus to Kuhn's triangulation of A. We define λ' : C_∞→ℤ_p:

    λ'(c_1, …, c_p) = {λ(c_1,…,c_p)    if (c_1,…,c_p) ∈ D
    T_p({j : c_j = 0})    otherwise
    .

where T_p is the ℤ_p-equivariant tie-breaking function defined in <ref>. Note that λ' is well-defined, because if (c_1,…,c_p) ∈ D, then it corresponds to a point in the p domain. Furthermore, if (c_1,…,c_p) ∉ D, then |{j : c_j = 0}| ∈ [1,p-1], so is a valid input to T_p.

Since θ D = D, λ(θ c) = λ(c) + 1 and T_p({j: (θ c)_j = 0}) = T_p({j : c_j = 0}) + 1, it follows that λ' satisfies the boundary conditions.

Let c^1, c^2, …, c^p be a (p-1)-simplex of C_∞ that carries all the labels in ℤ_p (with respect to λ'). We now show how this yields a solution to the p instance. Without loss of generality, we can assume that c^1, c^2, …, c^p are ordered in the order in which the simplex is defined by Kuhn's triangulation. Namely, for every i ∈{1, …, p-1}, there exists j_i such that c^i+1_j_i = c^i_j_i + 1/m and c^i+1_j = c^i_j for all j ≠ j_i. Furthermore, the j_i are all distinct. Note that if for some i^*, c^i^*∉ D, then c^i ∉ D for all i ≥ i^*. The following cases can occur:

    
  * the simplex does not intersect D: it follows that c^1 ≠ 0 ∈ D, and thus there exists j such that c^1_j > 0. But then c^i_j > 0 for all i and the label j cannot be obtained by any vertex of this simplex.
    
  * the intersection of the simplex with D is a face of dimension 2: then the three vertices of this face have pairwise distinct labels, and thus yield a solution to p.
    
  * the intersection of the simplex with D is a face of dimension 1: then it must hold that c^1,c^2 ∈ D and c^3, …, c^p ∉ D. We distinguish between the two sub-cases:
    
        
  * c^2_j_1 > 0 and c^2_j = 0 for all j ≠ j_1. Then, since c^3 ∉ D, it follows that j_2 ∉{j_1-1,j_1,j_1+1}. By definition of the j_i, we have that c^3_j_1 > 0 and c^3_j_2 > 0, which implies that c^3, …, c^p can only have labels in ℤ_p ∖{j_1,j_2}. As a result, c^1 and c^2 must have labels j_1 and j_2 (in any order). This yields a solution to p, because the labels are distinct and non-consecutive.
        
  * there exists j^* such that c^2_j^* > 0, c^2_j^*+1 > 0 and c^2_j = 0 for all j ∉{j^*,j^*+1}. Since c^3 ∉ D, it must hold that j_2 ∉{j^*,j^*+1}. Thus we have c^3_j_2 > 0, and the vertices c_3, …, c_p can only obtain the labels ℤ_p ∖{j^*,j^*+1, j_2}. It follows that the simplex cannot possibly be fully labeled.
    
    
  * the intersection of the simplex with D is a face of dimension 0: then c^2 ∉ D, and thus there exist distinct j,j' (and non-consecutive, but we don't need this here) such that c^2_j > 0 and c^2_j' > 0. But then, the vertices c_2, …, c_p can only obtain the labels ℤ_p ∖{j,j'}. It follows that the simplex cannot possibly be fully labeled.

This completes the proof.





§ THE P LEMMA: STATEMENT AND P-COMPLETENESS
 

In this section, we introduce a ℤ_p-generalization of Tucker's Lemma. We further define the associated computational problem p, and show that it is p-complete. In the next section, we will use this problem to prove the membership of p-thief Necklace Splitting in p.

In p, the coordinates of the vertices lie on a star-like domain. This domain was used by <cit.> for the first fully combinatorial proof of necklace splitting with p thieves.



For any prime p and any m ≥ 1, we define R_p,m = {0}∪{*^i j : i ∈ℤ_p, j ∈ [m]}, where [m] = {1,2,…, m}. For ease of notation, we also let *^i 0 = 0 for all i ∈ℤ_p. The symbols *^1, …, *^p should be interpreted as p different “signs” that will generalize the use of “+” and “-” in Tucker's Lemma. The way to picture R_p,m is as follows: the point 0 lies at the center and there are p segments of length m leaving from 0 in p different directions. In that sense, we also call R_p,m a p-star. The boundary of the p-star is the set of points *^1 m, …, *^p m. 

The ℤ_p-action θ is defined on R_p,m in the natural way, i.e., θ(*^ij) = *^i+1 j (recall that i ∈ℤ_p). In particular, θ(0)=0. For any d ≥ 1, θ can be extended to R_p,m^d := (R_p,m)^d by simply applying θ separately to each coordinate. Note that θ is a free action when restricted to the boundary of R_p,m^d (i.e., the points that have at least one coordinate of the form *^· m). See <ref>.

There is a very natural metric on R_p,m. (*^i_1j_1,*^i_2j_2) is defined to be |j_1-j_2| if i_1=i_2, and j_1+j_2 otherwise. We let _∞(·, ·) denote the generalization to R_p,m^d (where we take the maximum). Finally, we triangulate the domain R_p,m^d by using Kuhn's triangulation on every subcube (see <ref> below for details). We can now state a Tucker's lemma for this domain.


Let p be prime and m,t ≥ 1, d=t(p-1), and T be Kuhn's triangulation of R_p,m^d. Let λ: R_p,m^d → R_p,t∖{0}[Notice that the set R_p, t∖{0} is isomorphic to the set [p] × [t].] be any labeling that satisfies λ(θ x) = θλ(x) for all x ∈∂ R_p,m^d. Then there exists a (p-1)-simplex x_1, …, x_p of T and j ∈ [t] such that λ(x_i) = *^i j for all i ∈ [p].


In particular, by the properties of Kuhn's triangulation, it holds that for every solution x_1, …, x_p, we have _∞(x_i,x_k) ≤ 1 for all i,k ∈ [p].

Note that ℤ_2-star Tucker's Lemma corresponds to the standard version of Tucker's Lemma. Since we are interested in the computational aspect, we also define the naturally corresponding TFNP problem.





    
    
    p: 



Input: m,t ≥ 1, d=t(p-1) and a Boolean circuit computing a labeling λ: R_p,m^d → R_p,t∖{0} that satisfies λ(θ x) = θλ(x) for all x ∈∂ R_p,m^d


Output: A (p-1)-simplex x_1, …, x_p ∈ R_p,m^d and j ∈ [t] such that λ(x_i) = *^i j for all i ∈ [p]



Note that the property “λ(θ x) = θλ(x) for all x ∈∂ R_p,m^d” can be enforced syntactically. Thus, p is not a promise problem. 

The main result of the section is the following theorem.


For all primes p, p is p-complete.

The proof of the theorem will follow from <ref> and <ref> below. The hardness is obtained by a reduction from p- , which is p-hard for all primes p, as shown in <ref>.



The domain R_p,m^d can be triangulated in a standard way as follows. We start by subdividing the domain into hypercubes {*^i_1 (a_1-1), *^i_1 a_1}×…×{*^i_d (a_d-1), *^i_d a_d} for a_1,…, a_d ∈ [m] and i_1, …, i_d ∈ℤ_p. Then, we can use Kuhn's triangulation on each hypercube.

Similarly to <ref>, the triangulation T of R_p,m^d has the following nice properties:

    
  * The restriction of T on any sub-orthant of R_p,m^d (i.e., a subspace of the form A_1 × A_2 ×…× A_d, where A_ℓ = {*^i_ℓ j : 0 ≤ j ≤ m} or A_ℓ = {0}) yields a triangulation of that sub-orthant.
    
  * On the boundary of R_p,m^d, the triangulation T is symmetric with respect to θ : for any simplex σ of T that lies on the boundary of R_p,m^d, the simplices θσ, θ^2σ, …, θ^p-1σ are also simplices of T (that also lie on the boundary).
    
  * T is computationally efficient, in the sense that we can perform pivoting and indexing operations in polynomial time.








 §.§ p is in p

First, we prove the membership of p in p. We have the following theorem.


For all primes p, p lies in p.


 

The result is proved by reducing the problem to p. In particular, this also provides a combinatorial proof of ℤ_p-star Tucker's Lemma (<ref>). This proof can be seen as a generalization of the combinatorial proof of Tucker's Lemma given by <cit.>. We provide an overview of the proof below; the full proof can be found in <ref>.





  §.§.§ Proof Overview of <ref>


As noted earlier, 2 corresponds to the standard version of Tucker's Lemma and the domain is equivalent to {-m,-(m-1)…,0,…,m}^d. The computational problem is known to lie in  (recall that = 2) by using an argument given by <cit.>. More precisely, Freund and Todd gave a constructive proof of Tucker's Lemma and as noted by <cit.>, this yields a reduction to . The constructive proof relies on a path-following argument on a graph where the nodes are simplices of the triangulation. We start by giving some details about their argument, since our proof is a generalization of their construction.

The nodes of the graph G consist of all simplices of the triangulation that satisfy some properties that depend on the labels of the simplex (and the coordinate subspace orthant in which the simplex lies). Following the presentation of the proof given by <cit.>, we call these “happy simplices”. Undirected edges are added between happy simplices based on some simple rules (e.g., if they share a facet and that facet has some desired labels, etc). Given the definition of the edges, it is easy to show that the happy simplex 0^d has degree 1 and any other node of degree 1 is either a solution, or is a happy simplex lying on the boundary of the domain. In the latter case, because of the boundary conditions, this means that there must be another such simplex that lies on the antipodally opposite side of the domain and also has degree 1. Thus, merging these two nodes into a single one yields a vertex of degree 2, eliminating these “fake” solutions.

Our first contribution is to note that the edges of the graph can be directed in a consistent way in Freund and Todd's construction. Namely, any non-merged degree-2 vertex has one incoming and one outgoing edge, and any merged vertex has either two incoming edges, or two outgoing edges. This yields a reduction to Imbalance-mod-2. Note that if all degree 2 vertices were always perfectly balanced, then we would obtain a reduction to End-of-Line, which is impossible, unless =.

When we move to the case p>2, the notions used to define the graph can be generalized in a natural way, despite the unusual domain R_p,m^d. While the ability to direct edges was not actually needed for p=2, it now becomes absolutely necessary. Indeed, for any degree-1 happy simplex on the boundary, there are now p-1 other such simplices (by using θ). Merging these into a single node yields degree p. We show that directing the edges yields a merged node that is balanced modulo p (namely, all p edges are incoming, or they are all outgoing).

However, another difficulty arises for p>2. Recall that a path can visit simplices of various dimensions. The vertices where the dimension changes are special vertices, that we call super-happy simplices. These super-happy simplices have one edge with a same or lower-dimensional happy simplex, and k edges with k different higher-dimensional happy-simplices, where k ∈ [p-1]. Directing the edges as before, yields that the k edges are directed the same way, and in the opposite direction to the single edge. By changing the way the direction of edges is defined, it is possible to salvage the situation for p=3. However, this fails for any p ≥ 5.

The solution is to carefully assign weights to all edges. The weight of an edge only depends on the nature of the coordinate subspace orthants in which it lies, in particular the dimension. With these weights, we show that any vertex that is not a solution is now balanced modulo p (except the trivial solution 0^d). Namely, the non-solution vertices of the graph are:

    
  * the trivial solution 0^d: all its edges are outgoing and it has degree (-1)^t  p
    
  * the merged simplices on the boundary: p edges, all incoming/outgoing, all the same weight
    
  * happy, but not super-happy simplices: once incoming edge, one outgoing, both same weight
    
  * super-happy simplices: one incoming edge with weight w and k ∈ [p-1] outgoing edges, each with weight w/k (or opposite direction for all edges)

Thus, apart from the trivial solution and any actual solutions, all vertices are balanced modulo p.




Even though this proof is a natural generalization of the argument by <cit.>, it is not a path-following argument for p ≥ 3. Indeed, in the case where p ≥ 3, it is not clear how we could explore this graph by following a path that is guaranteed to end at a solution. In fact, we provide strong evidence that it is not possible to prove p by a path-following argument. Since p is p-hard (see next Section), and since a path-following proof of p would presumably show that the problem lies in , this would imply that p⊆, for prime p ≥ 3. However, this is not expected to hold <cit.>.

Similarly, if one can show that p is p-hard for some prime p ≥ 3, then this would provide strong evidence that the Necklace Splitting theorem with p thieves cannot be proved by a path-following argument.





 §.§ p is p-hard


In this section we prove that p is p-hard, by reducing from p-, which is p-hard by <ref>.


For any prime p, p is p-hard, even for fixed dimension t ≥ 1.



We show this by reducing from p- with n=t.
Let λ be an instance of p- for some prime p and some n ≥ 1, where we use Kuhn's triangulation.

In this case the domain of p- corresponds to

    C_∞ = {(c^1, …, c^p) ∈ U^np_m | ∀ j ∈ [n], ∃ i ∈ [p] : c^i_j = 0 }.

On the other hand, the domain of p can be described as

    A = {(a^1, …, a^p) ∈ U^np(p-1)_m | ∀ j,k ∈ [n] × [p-1], ∃ i^* ∈ [p] : a^i_j,k = 0  i ∈ [p] ∖{i^*}}.

Note that θ (c^1,…, c^p) = (c^p,c^1, …, c^p-1) and θ (a^1,…, a^p) = (a^p,a^1, …, a^p-1).

Define Ψ : A → C_∞ as Ψ(a^1, …, a^p) = (ψ(a^1), …, ψ(a^p)), where ψ_j(a^i) = max{a^i_j,k : k ∈ [p-1]} for all i ∈ [p], j ∈ [n]. Note that Ψ is well-defined, namely if a ∈ A, then Ψ(a) ∈ C_∞. Indeed, for any j ∈ [n], it holds that |{i ∈ [p]| ψ_j(a^i) > 0}| = |{i ∈ [p]| ∃ k ∈ [p-1] : a^i_j,k > 0}| ≤ |{(i,k) ∈ [p] × [p-1] | a^i_j,k > 0}| ≤ p-1, since for every k ∈ [p-1] there exists at most one i ∈ [p] such that a^i_j,k > 0 (for any fixed j). Furthermore, it is easy to see that Ψ(θ a) = θΨ(a) by construction.

Now define the labeling λ': A →ℤ_p × [n] by λ'(a) := λ(Ψ(a)). Since Ψ(A) ⊆ C_∞, λ' is well-defined. Furthermore, for any a ∈∂ A, it holds that Ψ(a) ∈∂ C_∞. Thus, we get that for any a ∈∂ A, λ'(θ a) = λ(Ψ(θ a)) = λ(θΨ(a)) = θλ(Ψ(a)) = θλ'(a), i.e., λ' satisfies the boundary conditions.

If σ = {z_1, …, z_p} is a (p-1)-simplex of A such that λ'(σ) = ℤ_p ×{j} for some j ∈ [n], then the set of vertices Ψ(σ) = {Ψ(z_1), …, Ψ(z_p)} satisfies λ(Ψ(σ)) = ℤ_p ×{j}. Thus, the proof is completed by the following claim:

If σ = {z_1, …, z_p} is a (p-1)-simplex in Kuhn's triangulation of A, then Ψ(σ) = {Ψ(z_1), …, Ψ(z_p)} is a simplex in Kuhn's triangulation of C_∞.



Since we use Kuhn's triangulation, without loss of generality, we can assume that z_1, …, z_p are ordered such that z_1 ≤ z_2 ≤…≤ z_p (component-wise) and z_1-z_p_∞≤ 1/m. By construction of Ψ it holds that Ψ(a) ≤Ψ(a') whenever a ≤ a'. Thus, Ψ(z_1) ≤…≤Ψ(z_p). In order to show that Ψ(σ) is a simplex in Kuhn's triangulation of C_∞, it remains to prove that Ψ(z_1) - Ψ(z_p)_∞≤ 1/m. To see this, note that if a-a'_∞≤ 1/m, then for all i ∈ [p] and j ∈ [n], we get that |ψ_j(a^i) - ψ_j(a'^i)| = |max{a^i_j,k : k ∈ [p-1]} - max{a'^i_j,k : k ∈ [p-1]}| ≤ 1/m.


This concludes the proof of <ref>.






§ NECKLACE SPLITTING WITH P THIEVES LIES IN P
 

In this section, we prove our main result regarding the Necklace Splitting Theorem; we prove that the associated computational problem p lies in p for any prime p.



For every prime p, p is in p. 


As a corollary, we also obtain that:

    
  * p^r is in p^r for any prime p and r ≥ 1
    
  * k lies in k under Turing reductions for any k ≥ 2.


As we explained in the introduction, our reduction will go via the continuous version of the problem, the
ε-Consensus-1/p-Division problem, which is the computational analogue of the Consensus-1/p-Division problem of <cit.>. We will show the inclusion of ε-Consensus-1/p-Division in p via a reduction to p, which also implies the p membership for p.
We prove the following main statement:


For any prime p, Consensus-1/p-Division reduces to p.



The proof is presented in <ref>, where we prove an even stronger version of this theorem. Indeed, we show that this result holds for any probability measures (not only step functions), as long as they are efficiently computable and sufficiently continuous (in some precise sense).

We start with the complete definitions of the computational problems corresponding to k-thief Necklace Splitting and Consensus-1/k-Division. 



    
k <cit.>



Input: An open necklace with n beads, each of which has one of t colors. 

There are exactly a_i k beads of color i =1,…,t, where a_i ∈ℕ.


Output: A partitioning of the necklace into k (not necessarily connected) pieces such that each piece contains exactly a_i beads of color i, using at most (k-1)t cuts.
 

As proved by <cit.>, this problem always has a solution. Furthermore, for any proposed splitting of the necklace it is easy to check if it is a solution. Thus, the problem k lies in TFNP.

<cit.> proved the necklace-splitting theorem by showing existence for a more general continuous version and then “rounding” a solution of the continuous problem to obtain a splitting of the necklace. When investigating the complexity of k, it is also convenient to consider the more general continuous version. Even though the continuous theorem is termed as a “generalized Hobby-Rice theorem” by <cit.>, we instead use the term Consensus-1/k-Division proposed by <cit.>. 



    
ε-Consensus-1/k-Division <cit.> 



Input: ε > 0 and continuous probability measures μ_1, …, μ_t on [0,1]. 

The probability measures are given by their density functions on [0,1], which are step functions (explicitly given in the input).


Output: A partitioning of the unit interval into k (not necessarily connected) pieces A_1,…,A_k using at most (k-1)t cuts, such that |μ_j(A_i) - μ_j(A_ℓ)| ≤ε for all i,j,ℓ.
 



The fact that this problem also lies in TFNP immediately follows from showing that it lies in k under Turing reductions (<ref>). Note that we can equivalently ask for μ_j(A_i) = 1/k ±ε for all i,j. Indeed, the computational problems are equivalent.


Furthermore, using the same technique as <cit.>, one can show that if ε is sufficiently small (with respect to the representation size of the step functions), then one can efficiently compute an exact solution from an ε-approximate solution. It follows that ε-Consensus-1/k-Division is equivalent to exact Consensus-1/k-Division. In particular, the problem always has an exact solution that is rational. Thus, we will sometimes refer to this problem just as Consensus-1/k-Division.

Alon's rounding procedure yields a reduction from k to exact Consensus-1/k-Division. <cit.> extended this result by showing that k reduces to ε-Consensus-1/k-Division, even when ε is not small enough to ensure that we can get an exact solution.


For any k ≥ 2, k reduces to ε-Consensus-1/k-Division.


Before we proceed with the proof of <ref>, we present the consequences of <ref>, in terms of computational complexity and mathematical existence.



  §.§.§ Consequences: Computational Complexity



For any k ≥ 2, k and Consensus-1/k-Division lie in the Turing closure of k. In particular, if k=p^r where p is prime and r ≥ 1, then the problems lie in p.

The Turing closure of k is the class of all TFNP problems that Turing-reduce to a k-complete problem (e.g., k). Note that when k is not a prime power, k is not believed to be closed under Turing reductions <cit.>.


<ref> and <ref> immediately imply that for any prime p, Consensus-1/p-Division lies in p. As noted by <cit.>, for any k,ℓ≥ 2, a Consensus-1/(kℓ)-Division can be obtained by first finding a Consensus-1/k-Division – which divides the interval into k (not necessarily connected) pieces – and then finding a Consensus-1/ℓ-Division of each of the k pieces. Note that we obtain (at most) the desired number of cuts. Thus, we can solve an instance of Consensus-1/(kℓ)-Division by first solving an instance of Consensus-1/k-Division, and then k instances of Consensus-1/ℓ-Division.

In particular, for any prime p and any r ≥ 1, Consensus-1/p^r-Division can be solved by solving 1+p+p^2+ … + p^r-1 instances of Consensus-1/p-Division. Thus, we obtain a Turing reduction from Consensus-1/p^r-Division to Consensus-1/p-Division. Since Consensus-1/p-Division lies in p and p is closed under Turing reductions <cit.>, it follows that Consensus-1/p^r-Division lies in p.


Now consider any k = ∏_i=1^m p_i^r_i, where m ≥ 1, r_i ≥ 1 and the p_i are distinct primes. Then, Consensus-1/k-Division can be solved by a query to Consensus-1/p_1^r_1-Division, then p_1^r_1 queries to Consensus-1/p_2^r_2-Division (which can be turned into a single query to p_2), then p_1^r_1p_2^r_2 queries to Consensus-1/p_3^r_3-Division (which can also be turned into a single query to p_3), etc. Thus, Consensus-1/k-Division can be solved by a query to p_1, then a query to p_2, then one to p_3, …, and finally a query to p_m. Since p_i⊆k for i = 1, …, m (<ref>), it follows that there is a Turing reduction from Consensus-1/k-Division to a k-complete problem (e.g., k).

Since k reduces to Consensus-1/k-Division (<ref>), the results also hold for k.





  §.§.§ Consequences: Mathematical Existence


<ref> yield a reduction from Consensus-1/p-Division to p. Since every instance of p has a solution (and the proof of this is trivial), we obtain a proof that Consensus-1/p-Division always has a solution. Thus, this proves that if the probability measures are step functions (described by rational numbers), there always exists a consensus-1/p-division. While we have given the proof in terms of a reduction (since this is required for our complexity results), it can also be written as a mathematical proof of existence (without any computational considerations).

Once existence of a consensus-1/p-division for step functions has been proved, a constructive argument by <cit.> also gives existence for p-necklace-splitting. Putting everything together, the proof of p-necklace-splitting thus obtained is a fully combinatorial proof that does not use any advanced machinery and is easier to follow than existing proofs. Indeed, as we mentioned in the introduction, the original proof by <cit.> used the BSS theorem of <cit.> as a black box. The only other fully combinatorial proof by <cit.>, while quite elegant, is significantly more involved.

Going back to consensus-1/p-division, the proof we obtain (which uses ℤ_p-star Tucker's lemma) actually works for any probability measures, not only step functions. Moreover, similarly to <cit.>, our proof does not make use of the fact that the measures are additive and non-negative. Thus, we obtain a stronger version of the consensus-1/p-division theorem given by <cit.> (which he calls a generalization of the Hobby-Rice theorem). Let ℬ([0,1]) denote the Borel σ-algebra on the unit interval and let λ denote the Lebesgue measure on the unit interval. Finally, let  denote the symmetric difference, i.e., A  B = (A ∖ B) ∪ (B ∖ A).

 
Let p be any prime and t ≥ 1. Let v_1, …, v_t : ℬ([0,1]) →ℝ be such that for all 1 ≤ j ≤ t v_j satisfies the following continuity condition:
for all ε > 0 there exists δ > 0 such that

    |v_j(A) - v_j(B)| ≤ε  for all  A,B ∈ℬ([0,1])  that satisfy λ(A  B) ≤δ.

Then, there exists a consensus-1/p-division. Namely, it is possible to partition the unit interval into p (not necessarily connected) pieces A_1, …, A_p using at most (p-1)t cuts, such that v_j(A_i) = v_j(A_ℓ) for all 1 ≤ i,ℓ≤ p, 1 ≤ j ≤ t.


Before we move on to the proof, let us briefly explain why we only obtain the result for prime p. In the usual setting where the valuations are probability measures, it is enough to prove the statement for primes. Indeed, using the standard argument by <cit.>, if a consensus-1/k-division and a consensus-1/ℓ-division always exist, then a consensus-1/(kℓ)-division exists. But Alon's argument makes use of the additivity property of the measures. Indeed, consider the non-additive setting and say that we are trying to show that a consensus-1/4-exists. We know that a consensus-1/2-division exists and this yields a partition of [0,1] into A_1 and A_2. We have that v_j(A_1) = v_j(A_2) for all j. Following Alon's argument, find a consensus-1/2-division of A_1 and of A_2. This yields A_11∪ A_12 = A_1 and A_21∪ A_22 = A_2 such that v_j(A_11) = v_j(A_12) and v_j(A_21) = v_j(A_22) for all j. However, we might not have v_j(A_11) = v_j(A_22), since we no longer have v_j(A_11) + v_j(A_12) = v_j(A_21) + v_j(A_22).

If we assume that the valuations are additive (even just finite additivity), but still allow them to take negative values, then Alon's argument works as before and thus the result again holds for any k ≥ 2.


Using ℤ_p-star Tucker's lemma (<ref>) it follows that for any ε > 0, there exists an ε-approximate consensus-1/p-division, i.e., we can partition the interval into p pieces A_1, …, A_p (using at most (p-1)t cuts) such that |v_j(A_i) - v_j(A_ℓ)| ≤ε for all 1 ≤ i,ℓ≤ p, 1 ≤ j ≤ t. Indeed, it suffices to follow the same steps as in the proof of <ref>.

Let R_p denote the continuous version of R_p,m. R_p consists of p copies of the segment [0,1] (namely *^1[0,1], …, *^p[0,1]) that share the same origin (i.e., *^10 = … = *^p0). Using the interpretation given in the proof of <ref>, every point in R_p^d corresponds to a way to partition [0,1] into p (not necessarily connected) pieces using at most (p-1)t cuts. Since (R_p^d,_∞) is a compact metric space, every sequence must have a subsequence that converges. Thus, a sequence (x_n)_n, where x_n ∈ R_p^d is a 1/2^n-approximate consensus-1/p-division, must have a subsequence that converges to some x ∈ R_p^d. For any i,j the function f: R_p^d →ℝ, y ↦ v_j(A_i(y)) is continuous. It follows that x must correspond to an exact consensus-1/p-division.





 §.§ Reduction from Consensus-1/p-Division to p


In order to make our p-membership result as strong as possible, we define a computational problem that is much more general than ε-Consensus-1/p-Division. Namely, we allow any computationally reasonable probability measures that are also sufficiently continuous.

The probability measures are given by their cumulative functions. Let ℱ be a class of cumulative distribution functions on [0,1]. Thus, for any f ∈ℱ and any a ∈ [0,1], f(a) is the probability of the interval [0,a] according to f. For any f ∈ℱ, let (f) denote the size of the representation of f. E.g., if f is represented as a circuit, then (f) is the size of the circuit. For any rational number x, (x) denotes the representation length of x, i.e., the length of the binary representation of the denominator and numerator of x. We will require two properties from ℱ:


    
  * ℱ is polynomially computable: there exists a polynomial q_1 such that for all f ∈ℱ and all rational x ∈ [0,1], f(x) can be computed in time q_1((f)+(x)).
    
  * ℱ is polynomially continuous: there exists a polynomial q_2 such that for all f ∈ℱ and all rational ε > 0, there exists rational δ > 0 with (δ) ≤ q_2((f)+(ε)) such that |x-y| ≤δ |f(x)-f(y)| ≤ε for all x,y ∈ [0,1].

These properties are quite natural and they were used by <cit.> in the context of fixed point problems. In particular, they hold when ℱ is the class of all cumulative distribution functions given by step function densities (represented explicitly). But they also hold for much more general families.


Let k ≥ 2 and let ℱ be a polynomially computable and polynomially continuous class of cumulative distribution functions on [0,1]. The problem ε-Consensus-1/k-Division[ℱ] is defined exactly as ε-Consensus-1/k-Division, except that the probability measures are given by cumulative distribution functions in ℱ.


Notice that ε-Consensus-1/k-Division corresponds to the special case where ℱ is the class of all cumulative distribution functions given by step function densities (represented explicitly). Thus, the following is a stronger version of <ref>.


Let p be prime and ℱ be a polynomially computable and polynomially continuous class of cumulative distribution functions on [0,1]. Then ε-Consensus-1/p-Division[ℱ] reduces to p.




Let ε > 0 and μ_1, …, μ_t be probability measures on [0,1] given by functions in ℱ. We consider the domain D = R_p,m^d, where d=t(p-1) and m ≥ 1 will be set later. A point in D represents a way to partition [0,1] into p (not necessarily connected) pieces using at most t(p-1) cuts. This is a slight modification of the domain that was used by <cit.> to encode a splitting of a necklace. Intuitively it can be explained as follows. Let x=(*^i_1 j_1, …, *^i_d j_d) ∈ D. We interpret each element i ∈ℤ_p as a different color. Then:

    
  * Paint the whole interval [0,1] with the color 1.
    
  * For ℓ = 1,2, …, d : paint [0,j_ℓ/m] with the color i_ℓ

Note that applying a fresh coat of paint on a previously painted part of the interval covers up the old paint. The way the interval [0,1] is colored at the end of this procedure gives us the partition encoded by x ∈ D. An important advantage of this encoding is that it is sufficiently continuous in a certain sense. Indeed, small changes in the coordinates of x have a small effect on the corresponding partition. Other simpler encoding schemes do not have this property.

Formally, this encoding can be described as follows. Add a “fake” 0th coordinate *^i_0 j_0 = *^1 m. Place cuts at all positions j_0/m, j_1/m, …, j_d/m. This subdivides the interval [0,1] into at most d+1=t(p-1)+1 subintervals. Then, allocate the subinterval [a,b] to i_ℓ∈ℤ_p, where ℓ = max{0 ≤ℓ≤ d : j_ℓ/m ≥ b}.

This encoding also behaves nicely with respect to θ. For any x ∈∂ D, θ x encodes the same partition as x, except that i has been replaced by i+1, for all i ∈ℤ_p. This is easy to see since for any x ∈∂ D, there exists ℓ≥ 1 such that j_ℓ = m and thus the “fake” coordinate *^i_0 j_0 does not play any role.

We are now ready to define the labeling λ : D → R_p,t∖{0}. This labeling is a natural generalization of the one used by <cit.>. Given x ∈ D, construct the partition it encodes, namely A_1(x), …, A_p(x). Then, for all i ∈ℤ_p and j ∈ [t], let μ_j,i(x) = μ_j(A_i(x)), i.e., the total measure of type j that is allocated to i. Finally, set λ(x) = *^i j, where i,j are determined as follows:

    
  * Pick j ∈ [t] that maximizes max_i_1,i_2 |μ_j,i_1(x) - μ_j,i_2(x)|. Break ties by picking the minimum such j.
    
  * Then, pick i ∈ℤ_p that maximizes μ_j,i(x). If there are multiple i's that maximize this, break ties by picking the one such that min A_i(x) is minimal (i.e., such that A_i(x) contains the point closest to the left end of the unit interval).


By using the observation above about the behavior of θ on ∂ D, it is easy to see that λ(θ x) = θλ(x) for all x ∈∂ D. Thus, λ is a valid instance of p and we obtain a solution x_1, …, x_p ∈ D and ∈ [t], such that _∞ (x_i,x_k) ≤ 1 and λ(x_i) = *^i for all i,k ∈ [p]. It remains to show that by picking m large enough, we obtain a solution to ε-Consensus-1/p-Division[ℱ].

Let ε' = ε/2t(p-1). Since ℱ is polynomially continuous, we can pick m large enough so that the value μ_j([0,a]) changes by at most ε', if a moves by 1/m. Note that m has representation length polynomial in the size of the instance. If a single coordinate of x changes by 1, μ_j,i(x) changes by at most ε' for all i,j. Since there are d=t(p-1) coordinates, it follows that |μ_j,i(x_k) - μ_j,i(x_ℓ)| ≤ε' t (p-1) = ε/2 for all i,j  and for all k,ℓ∈ [p].

Let x := x_1. By construction of the labeling, we obtain that for all j,i,ℓ

    |μ_j,i(x) - μ_j,ℓ(x)| ≤max_i_1,i_2 |μ_,i_1(x) - μ_,i_2(x)| ≤ε

The first inequality holds because λ(x) = *^1. The second inequality holds because if we instead had μ_,i_1(x) > μ_,i_2(x) + ε for some i_1, i_2, then it would follow that μ_,i_1(x_i_2) > μ_,i_2(x_i_2), contradicting λ(x_i_2) = *^i_2. Thus, x corresponds to an ε-approximate solution.







§ CONCLUSION AND FUTURE WORK


Our topological characterization of p can possibly enable us to obtain similar membership or hardness results for other interesting problems. For example, are the problems whose totality is established via the BSS Theorem, like the Chromatic Number of Kneser Hypergraphs[The computational version of this problem would be of the form: given a coloring (as a circuit) that cannot possibly be correct everywhere, because it does not use enough colors, find any edge where it makes a mistake.] studied in <cit.> in p? Are they p-complete? We believe that due to its simplicity, our p problem can be a very useful tool for obtaining hardness results for these problems. What about other problems that generalize problems that are known to be in  or are even -complete? For example, <cit.> showed that the discrete Ham-Sandwich problem is also -complete. Is there a generalization of the problem that could be complete for p? A computational version of the Center Transversal Theorem <cit.> might be a good candidate. Another interesting open problem is to investigate the connection of the general statement of Dold's Theorem <cit.> from algebraic topology with the subclasses of TFNP. Finally, although our paper takes a definitive step in the direction of resolving the complexity of p-thief Necklace Splitting and Consensus-1/p-Division, proving a p-hardness result remains a challenging open problem. In very recent work <cit.>, we have made a first step in that direction, by providing a significantly simpler proof (and strengthening) of the 2-hardness result of <cit.>, as well as the first hardness result for Consensus-1/3-Division, showing that it is hard for the class . Showing the -hardness of the Consensus-1/p-Division problem for p > 3 is also a very interesting first step that might be easier than showing the p-hardness.





  §.§.§ Acknowledgments

Alexandros Hollender is supported by an EPSRC doctoral studentship (Reference 1892947). Katerina Sotiraki is supported in part by NSF/BSF grant #1350619, an MIT-IBM grant, and a DARPA Young Faculty Award,  MIT Lincoln Laboratories and Analog Devices. Part of this work was done while the author was visiting the Simons Institute for the Theory of Computing. Manolis Zampetakis is supported by a Google Ph.D. Fellowship and NSF Award #1617730.  


We would like to thank Paul Goldberg and Frédéric Meunier for helpful discussions and comments, as well as the anonymous reviewers for their suggestions that helped improve the paper.



plainnat








§ TOPOLOGICAL DEFINITIONS



In this section, we include all the necessary notation and topological definitions that are used throughout the paper. For a more detailed exposition on simplicial complexes, we refer the interested reader to <cit.>.



  
Notation: Let B^n = {x ∈ℝ^n : x_2 ≤ 1} denote the n-dimensional unit ball and S^n-1 = ∂ B^n be the corresponding unit sphere.


A homeomorphism of topological spaces (X_1, 𝒪_1) and
(X_2, 𝒪_2) is a bijection ϕ: X_1 → X_2 such that for every U ⊆ X_1, ϕ(U) ∈𝒪_2 if and only if U ∈𝒪_1. In other words, a bijection ϕ: X_1 → X_2 is a
homeomorphism if and only if both ϕ and ϕ^-1 are continuous. If there is a homeomorphism ϕ: X_1 → X_2, we write X ≅ Y.


We say that a function f has order p if f^p = f, where the notation f^i denotes to the composition of f by itself i times.

Let f: X → Y be a function of order p and let P be a set. We say that f acts freely on P if for all x ∈ X and all i ∈{1, …, p-1}, f^i(x) ≠ x. 



We call the points _1, _2, …, _k affine dependent if there exist numbers a_1, a_2, …, a_k ∈ not all 0 such that ∑_i = 1^k a_i_i = 0 and ∑_i = 1^k a_i = 0. Otherwise, _1, …, _k are called affine independent.


Geometrically, some examples of simplices are points, lines and triangles. Formally, the definition requires the notion of affine independence.


A simplex σ is the convex hull of a finite set A of affine independent vectors in ^n. The points in  A are called the vertices of σ and denoted by V(σ). The dimension of σ is equal to |A| - 1. Namely, a k dimensional simplex, called k-simplex for short, has k+1 vertices. The convex hull of an arbitrary subset of the vertices of σ is called a face of σ. A proper face of σ is called facet.


From the above definitions, it holds that every face is itself a simplex. For simplicity, we denote a simplex as the set of its vertices.




 §.§ Simplicial Complexes, Value & Index Functions and Triangulations

Very central to our paper is the notion of geometric simplicial complexes, which are used to describe subspaces of ^d. These subspaces consist of simple building blocks, such as points, line segments, triangles, tetrahedra, that are pasted together. 




A simplicial complex K is a non-empty set of simplices that satisfies the following properties:

    
  * Each face of a simplex σ∈ K is also a simplex in K.
    
  * The intersection σ_1 ∩σ_2 of any two simplices σ_1, σ_2 ∈ K is a face of both σ_1 and σ_2. 

The union of the simplices in K is called the polyhedron of K and is denoted by K. The dimension of K is 𝖽𝗂𝗆(𝖪) := max_σ∈ K{𝖽𝗂𝗆(σ)} and the vertex set of K, denoted by V(K), is the union of the vertex sets of all its simplices.

We denote by Σ_σ for a simplex σ the simplicial complex that contains all simplices τ such that τ⊆σ.


According to the above definition, zero-dimensional simplicial complexes correspond to points and one-dimensional simplicial complexes to sets of non-intersecting line segments as shown in <ref>.



The notion of triangulation relates simplicial complexes with topological spaces. 

A simplicial complex K is a triangulation of a topological space X if K≅ X.


For instance, the boundary of the n-simplex σ_n, namely a simplicial complex containing all proper faces of σ_n, is a triangulation of the sphere S^n-1.

Triangulation is a very powerful tool in studying the computational complexity of topological problems, because they allow us to partition a simplicial complex into smaller simplices that are connected in useful ways. We will mainly use the Kuhn triangulation, which is described in more detail below. We refer the interested reader to <cit.> and <cit.> for further information.



We define two functions of a triangulation,  and , that are essential for the definition of our computational problems and our reductions.


 
    Let K be a simplicial complex consisting of k
  simplices, including the non-full dimensional ones and
  let M > k. We define the value function
  : [M] →K̅, where K̅ = K ∪{∅}, to be an
  efficiently computable function such that
  
  
  *  is bijective on K,
    
  * if (x) = {v⃗_1, …, v⃗_ℓ}, then x 
    is called the index of the simplex σ∈ K with vertices 
    {v⃗_1, …, v⃗_ℓ}, and
    
  * if (x) = ∅ then x does not correspond to a valid 
    index of any non-empty simplex in K,
  
  
    We also define the index function 
  :^n → [M] to be an efficiently computable function such
  that if x⃗∈K then x⃗∈((x⃗)). 


Intuitively,  provides a way to enumerate over the simplices and  on input a point  returns the simplex that contains . 







Kuhn's triangulation is a standard way to triangulate a domain that is a cube. For any n ∈ℕ, the cube [0,1]^n is triangulated with granularity m ∈ℕ as follows:

    
  * the set of vertices of the triangulation is U_m^n, where U_m = {0,1/m,2/m, …, m/m}
    
  * every x ∈ (U_m ∖{1})^n is the base of the cube containing all vertices {y : y_i ∈{x_i,x_i + 1/m}}
    
  * every such cube is subdivided into n! n-dimensional simplices as follows: for every permutation π of [n], σ = {y^0,y^1, …, y^n} is a simplex, where y^0 = x and y^i = y^i-1 + 1/me_π(i) for all i ∈ [n] (e_i is the ith unit vector)

It is easy to see that Kuhn's triangulation has the following properties:

    
  * For any simplex σ = {z^1, …, z^k} it holds that z^i-z^j_∞≤ 1/m for all i,j, and there exists a permutation π of [k] such that z^π(1)≤…≤ z^π(k) (component-wise).
    
  * The restriction of Kuhn's triangulation of [0,1]^n on some subspace A_1 × A_2 ×…× A_n of [0,1]^n, where for each i ∈[n], A_i ∈{{0}, [0,1]}, coincides with Kuhn's triangulation of that subspace.
    
  * Every n-dimensional simplex can be indexed by its smallest vertex (component-wise), which is also the base of the cube containing the simplex, and by the permutation that yields this simplex within this cube. Given some index, it is easy to check whether this is a valid index, and if so, output the vertices of the simplex. Thus, the  function can be computed efficiently.
    
  * Given a point x ∈ [0,1]^n, we can efficiently determine the index of a simplex that contains it as follows. First find the base y of a cube of U_m^n that contains x. Next, find a permutation π such that x_π(1)-y_π(1)≥…≥ x_π(n)-y_π(n). Then, it follows that (y,π) is the index of a simplex containing x. Thus, the  function can be computed efficiently.
    
  * Given an n-simplex {z^0, …, z^n} and i ∈{0,1,…, n}, we can efficiently compute the index of the other n-simplex that also has {z^0, …, z^n}∖{z_i} as a facet. This is called a pivot operation.






 §.§ The Borsuk-Ulam Theorem and Tucker's Lemma


Here, we provide the definitions of the problems that we generalize. Note that in <ref>, we explain how the Borsuk-Ulam Theorem can be interpreted under a more general definition, which explains how our definition of Polygon Borsuk-Ulam is indeed a generalization. We start with the Borsuk-Ulam Theorem, which is usually stated as “for every continuous function from S^n to ℝ^n, there exists a point 𝐱∈ℝ^n, such that f(𝐱)=f(-𝐱)”. We present an alternative definition (as stated in <cit.>), which is more appropriate for our results.


For every antipodal mapping f:S^n →ℝ^n (i.e., a function f which is continuous and f(𝐱) = f(-𝐱)), there exists a point 𝐱∈ S^n such that f(𝐱)=0. 


Tucker's lemma is a well-known combinatorial existence theorem, which is an analogue of the Borsuk-Ulam Theorem. It is usually stated on the d-dimensional unit ball or sphere. For computational purposes the following version is more commonly used.


Let m,d ≥ 1. Let λ: ([-m,m] ∩ℕ)^d →{± 1, ± 2, …, ± d} be any labeling that satisfies λ(-x) = - λ(x) for all x ∈ ([-m,m] ∩ℕ)^d such that ∃ i with |x_i|=m. Then there exist two points x,y ∈ ([-m,m] ∩ℕ)^d with x-y_∞≤ 1 that have opposite labels, i.e., λ(x) = - λ(y).

The corresponding computational problem Tucker is known to be PPA-complete <cit.>, even if the dimension is fixed to be d=2.




 §.§ ℤ_p-equivariant tie-breaking


For some of our constructions, we will require a tie-breaking that is ℤ_p-equivariant and efficiently computable. Observe that non-efficient tie breaking rules exist by carefully choosing one representative for any equivalence class but this is not sufficient for our proofs. We define an efficiently computable rule below for any set S ∈ 2^ℤ_p∖{∅, ℤ_p}, let S+i := {x+i : x ∈ S}.



For any prime p, the ℤ_p-equivariant tie-breaking function T_p : 2^ℤ_p∖{∅, ℤ_p}→ℤ_p is computed as follows on input S ∈ 2^ℤ_p∖{∅, ℤ_p}:

    
  * For every i ∈_p, write S+i as a bit-string of length p. Namely, construct the bit-string b(i) where the jth bit from the left indicates whether j ∈ S+i (for j=0, …, p-1).
    
  * Output -i^* ∈ℤ_p, where i^* = _i b(i) (b(i) interpreted as a number in binary).





For any prime p, the ℤ_p-equivariant tie-breaking function T_p : 2^ℤ_p∖{∅, ℤ_p}→ℤ_p is well-defined and satisfies for any S ∈ 2^ℤ_p∖{∅, ℤ_p}:

    
  * T_p(S) ∈ S
    
  * T_p(S+i) = T_p(S)+i for all i ∈ℤ_p.




If p is prime and S+ i = S for some i ∈_p ∖{0}, then S ∈{∅, ℤ_p}. This follows from observing that the corresponding bit strings b(0) and b(i) must be equal and that this implies that the bits of b(0) with index {k· i}_k ∈_p are all equal. Since p is prime, {k· i}_k ∈_p = _p.


Hence, |{S+i: i ∈ℤ_p}| = p for any S ∈ 2^ℤ_p∖{∅, ℤ_p}. Thus, the bit-strings b(i) are all distinct, T_p(S) is unique and T_p is well-defined. Next, by construction, it is easy to see that T_p(S+i) = -(i^*-i) = T_p(S) + i. Finally, since S ≠∅, i^* will be such that b(i^*) has a 1 in the left-most position. Thus, 0 ∈ S+i^*, which implies that -i^* ∈ S.




  
Example. Let p = 3 and S = {2}. Then, S + 0 = {2}, S + 1 = {0}, S + 2 = {1}, and b(0) = 010, b(1) = 001 and b(2) = 100 (in binary). From <ref>, T_3(S) = 2.









§ (P,N)- REDUCES TO (P,N+1)-


Let (p,n)- denote the p- problem with dimension parameter n. We have the following lemma.



For all n ≥ 1 and prime p ≥ 2, (p,n)- reduces to (p,n+1)-.




The domain of (p,n)- with Kuhn's triangulation can be written as

    X_n = {(c^1, …, c^p) ∈ U^np_m | ∀ j ∈ [n], ∃ i ∈ [p] : c^i_j = 0 }.


Note that the subset of X_n+1 corresponding to c^1_n+1 = … = c^p_n+1 = 0 can be identified with X_n. Since we use Kuhn's triangulation in both cases, the triangulations “match”.

Let λ be an instance of (p,n)-. We construct an instance λ' of (p,n+1)- as follows. For any vertex (c^1, …, c^p), we set 

    λ'(c^1, …, c^p) = {[                            λ(c^1, …, c^p),                if  c^1_n+1 = … = c^p_n+1=0; (k,n+1)  where  k = T_p(_i ∈ [p] c^i_n+1),                                  otherwise ].

In the second case, we have used the tie-breaking rule defined in <ref>. Since this tie-breaking is ℤ_p-equivariant, it is easy to see that λ' also satisfies the boundary conditions.

Consider any solution to this instance, i.e., a (p-1)-simplex σ that has all labels (1,ℓ), …, (p,ℓ) for some ℓ.  If ℓ = n+1, then there exists i ∈ [p] such that c^i_n+1=0 for all vertices of σ. This follows from the fact that the triangulation is “nice”. But then, σ cannot have the label (i,n+1). Hence, it must be that ℓ < n+1 and σ is contained in the region identified with X_n where λ = λ'. Thus, σ also yields a solution to the original instance.












§ P IS IN P, FULL PROOF


In this section, we provide the full proof of <ref>. Namely, we show how to reduce p to p.


The proof is a generalization of the construction given by <cit.> for Tucker's lemma. The main difficulties in generalizing their approach are:

    
  * For p=2, when a path hits the boundary, there is a corresponding path that also hits the boundary on the antipodal side, and we can join the two endpoints. For p > 2, when a path hits the boundary, there are now p-1 other corresponding paths that also hit the boundary. We ensure that no solution occurs there by directing all the edges. We show how to direct the edges consistently and efficiently.
    
  * For p=2, the original construction associates a label with each axis of the domain. For p > 2, there are more axes than labels, and so a single label must be associated to multiple axes. This creates imbalanced nodes in the graph that are not solutions. We solve this problem by carefully assigning weights to the edges of the graph.





  
*Sub-orthants. Recall that d=t(p-1). Consider the domain R_p,m^d with a labeling function λ given by a Boolean circuit. Let T be Kuhn's triangulation of R_p,m^d as described earlier. The domain R_p,m^d can be subdivided into what we call sub-orthants, which are orthants of coordinate subspaces. Formally, a sub-orthant is a space of the form A_1 × A_2 ×…× A_d, where A_ℓ = {*^i_ℓ j : 0 ≤ j ≤ m} or A_ℓ = {0} for ℓ=1, …, d.

We associate a label to every axis of R_p,m^d as follows. The label *^i j is associated to the *^i-axis of the [(j-1)(p-1) + ℓ]th copy of R_p,m, for ℓ = 1,2,…,p-1. Thus, every label is associated to exactly p-1 axes. For any sub-orthant X, let S(X) denote the set of labels associated with the axes that are used by X. For any simplex σ of T, we let O(σ) denote the smallest sub-orthant that contains σ.

For any sub-orthant O and j ∈ [t], let r_j(O) be the number of coordinates in the range (j-1)(p-1)+1, …, j(p-1) that are equal to 0 in O. In particular, we have ∑_j=1^t r_j(O) = t(p-1) - (O). Note that if |S(O)| =  (O), then r_j(O) = p-1 - |{i ∈ℤ_p : *^i j ∈ S(O)}|. We abuse notation and denote r_j(σ) := r_j(O(σ)).



  
*Happy simplices.
Let k ∈{0,1,…, d}. A k-dimensional simplex σ of T is happy, if

    
  * (O(σ)) = k (σ is full-dimensional in its sub-orthant)
    
  * |S(O(σ))| =  (O(σ)) (the sub-orthant uses ≤ 1 axis associated with each label)
    
  * S(O(σ)) ⊆λ(σ) (σ carries all the labels associated with its sub-orthant)

A happy simplex is called super-happy if we actually have S(O(σ)) ⊊λ(σ). In particular, the 0-dimensional simplex 0^d is super-happy.


Consider a happy simplex σ that has a facet τ⊂∂ R_p,m^d such that λ(τ) = S(O(σ)). Such a simplex is called a boundary-happy simplex. If σ is such a simplex, then the simplex that has θτ as a facet is also boundary-happy. Thus, we group τ, θτ, …, θ^p-1τ together into an equivalence class [τ]. Every such equivalence class has size exactly p. Formally, let B be the set of all simplices τ⊂∂ R_p,m^d such that λ(τ) = S(O(τ)) and |S(O(τ))| =  (O(τ)). We define an equivalence relation on B by τ_1 ≡τ_2 if and only if ∃ i ∈ℤ_p such that τ_1 = θ^i τ_2.


We construct a graph G. The vertices of G are the happy simplices of T and the equivalence classes [τ] (for all τ∈ B).



  
*Orientation.
We now define an orientation for our simplices. Fix an ordering of the labels, e.g., *^1 1, *^2 1, …, *^p 1, *^1 2, …. Let σ be any happy k-simplex, k ≥ 1, and let x_0 x_1 … x_k be any ordering of its vertices. Let x_0, x_1, …, x_k ∈ℕ^k denote the coordinates of x_0, x_1, …, x_k in O(σ), where the coordinates are ordered according to the fixed ordering of the labels. Note that there is at most one coordinate associated to each label (because |S(O(σ))| = k) and thus the coordinate vectors are uniquely determined. Furthermore, note that the coordinates are non-negative. We define the k × k matrix M = [x_0-x_1, x_0 - x_2, …, x_0-x_k], i.e., the ith column is x_0 - x_i. Then, we define the orientation of happy simplex σ with ordering x_0x_1… x_k as (σ|x_0 … x_k) =  M. Note that by construction of the triangulation T, we always have M ∈{-1,+1}. Indeed, it is easy to check that M can be transformed into the identity matrix by elementary operations that can only change the sign of the determinant.



  
*Edges.
Let σ be a happy k-simplex, k ≥ 1. If σ is super-happy, then it has a single facet τ such that λ(τ) = S(O(σ)). If it is not super-happy, then it has exactly two facets τ_1 and τ_2 such that λ(τ_i) = S(O(σ)), i=1,2. In any case, any such facet τ of σ yields an edge as follows:

    
  * If τ does not lie in the boundary of the sub-orthant O(σ), then there is exactly one other k-simplex σ' in O(σ) that also has τ as its facet. σ' is also happy, and we put an edge between σ and σ'.
    
  * If τ lies in the boundary of the sub-orthant O(σ), there are two cases:
    
        
  * τ lies in ∂ R_p,m^d. In that case, σ is a boundary-happy simplex and we put an edge between σ and [τ].
        
  * τ does not lie in ∂ R_p,m^d. Then, τ is a super-happy (k-1)-simplex and we put an edge between σ and τ.
    

In all of these cases, the direction of the edge is determined as follows. Let x_0x_1 … x_k be the ordering of the vertices of σ such that τ = {x_1, …, x_k} and x_1 … x_k are ordered according to their labels. If (σ|x_0 … x_k) = 1, then the edge is incoming into σ. Otherwise, it is outgoing out of σ. Finally, the weight of the edge is always ∏_j=1^t r_j(σ)!.


By the definition, it follows that there are three types of edges:

    
  * (Type 1) An edge between two happy k-simplices σ_1, σ_2 that lie in the same sub-orthant and share a facet τ with λ(τ) = S(O(σ_i)), i=1,2.
    
  * (Type 2) An edge between a happy simplex σ and its super-happy facet τ such that λ(τ) = S(O(σ)).
    
  * (Type 3) An edge between a boundary-happy simplex σ and its facet equivalence class [τ].


An edge of Type 2 or 3 is always “created” by exactly one of its endpoints. Thus, its direction and weight are well-defined. An edge of Type 1 however, is “created” by both of its endpoints and we will prove that it is well-defined, i.e., both endpoints agree on its direction and weight. For the weight this is easy to see, since O(σ_1)=O(σ_2) implies that r_j(σ_1) = r_j(σ_2) for all j. For the direction, we postpone this consistency check to the end of the proof.

We now prove that all vertices of G that do not yield a solution are balanced modulo p, except 0^d.



  
*The trivial solution 0^d.
We have λ(0^d) = *^i j. There are exactly p-1 sub-orthants O such that S(O) = {*^i j} and each of them contains a happy 1-simplex σ that has 0^d as a facet. It follows that 0^d has p-1 edges, each with weight ((p-1)!)^t/(p-1). Furthermore, all the edges are outgoing, because (σ|x_0 0^d) = 1 (i.e., incoming into σ). It follows that the total imbalance of 0^d is (p-1) ((p-1)!)^t/(p-1) = ((p-1)!)^t = (-1)^t  p, where we used (p-1)! = -1  p since p is prime (Wilson's theorem). It follows that 0^d is always a valid trivial solution for Imbalance-mod-p, because (-1)^t ≠ 0  p for all t ≥ 1.



  
*Happy, but not super-happy.
Consider a happy k-simplex σ with two facets τ_1, τ_2 that satisfy λ(τ_i) = S(O(σ)), i=1,2. Then, σ has two edges and they both have the same weight. Let x_0x_1 … x_k be the ordering of σ such that τ_1 = {x_1, …, x_k} and x_1… x_k are ordered according to their labels. Let i ∈ [k] be the index such that x_i and x_0 have the same label. In particular, τ_2 = {x_1, …, x_i-1,x_0,x_i+1,…, x_k} and x_1 … x_i-1x_0x_i+1… x_k are ordered according to their labels. We have

    [x_0-x_1, x_0 - x_2, …, x_0-x_k]    =  [x_i-x_1, …, x_i - x_i-1, x_0 - x_i, x_i - x_i+1, …, x_i-x_k]
       = -  [x_i-x_1, …, x_i - x_i-1, x_i - x_0, x_i - x_i+1, …, x_i-x_k]

where we first subtracted the ith column from all other columns, and then multiplied the ith column by -1. It follows that (σ|x_0 … x_k) = - (σ|x_i x_1 … x_i-1 x_0 x_i+1… x_k). Thus, one edge is incoming and the other outgoing, i.e., σ is balanced.



  
*Equivalence class.
Consider an equivalence class [τ]. Let σ be the happy k-simplex that has τ as a facet. In G, [τ] has exactly p edges: one with each of σ, θσ, θ^2 σ, …, θ^p-1σ. Since S(O(θ^i σ)) = θ^i S(O(σ)) for all i, it follows that r_j(θ^i σ) = r_j(σ) for all i,j. Thus, all p edges have the same weight. Let x_0 … x_k be the ordering of σ such that τ = {x_1, …, x_k} and x_1… x_k are ordered according to their labels. Let y_i = θ x_i for all i. Then, y_1 … y_k might not be ordered according to their labels. We let π denote the permutation that we would have to apply to order them correctly. As before, x_i denotes the coordinates of x_i restricted to O(σ), where the coordinates are ordered according to the associated label. y_i denotes the coordinates of y_i restricted to O(θσ), where the coordinates are ordered according to the associated label. Since the associated labels have changed according to θ, it follows that if we re-order the coordinates of x_i according to π we obtain y_i for all i=0,1,…, k. Thus, we have

    (θσ|y_0 π(y_1 … y_k))    = (π)  [y_0-y_1, y_0 - y_2, …, y_0-y_k]
       = (π)^2 [x_0-x_1, x_0 - x_2, …, x_0-x_k]
       = (σ|x_0 … x_k)

It follows that all edges of [τ] are directed the same way, i.e., they are all incoming or all outgoing. Since there are p edges and they also have the same weight, it follows that [τ] has imbalance 0 modulo p.
In this argument we assumed that λ satisfies the boundary conditions. Thus, if [τ] is not balanced modulo p, we obtain a counter-example, which is a solution.



  
*Super-happy.
Consider a super-happy k-simplex σ, k ≥ 1. Note that σ has a single facet τ that satisfies λ(τ) = S(O(σ)). Thus, σ “creates” a single edge. Let x_0 … x_k be the ordering of σ such that τ = {x_1, …, x_k} and x_1 … x_k are ordered according to their labels. The edge has weight ∏_j=1^t r_j(σ)! and it is incoming if (σ|x_0 … x_k) = 1, outgoing otherwise.

Since σ is super-happy, we have λ(x_0) ∉λ(τ) = S(O(σ)). Let *^i ℓ = λ(x_0). If {*^j ℓ | j ∈ [p] ∖{i}}⊆ S(O(σ)), or equivalently if r_ℓ(σ) = 0, then σ yields a solution. Otherwise, there are exactly r_ℓ(σ) different sub-orthants O such that O(σ) ⊂ O and S(O) = S(O(σ)) ∪{*^i ℓ}. Thus, there are exactly r_ℓ(σ) happy (k+1)-simplices ρ such that σ is a facet of ρ and ρ is happy because of σ (i.e., S(O(ρ))=λ(σ)). It follows that σ has r_ℓ(σ) additional edges (apart from the one it “created”). Each of these edges has weight ∏_j=1^t r_j(ρ)! = (r_ℓ(σ))^-1∏_j=1^t r_j(σ)!, since r_ℓ(ρ) = r_ℓ(σ)-1. Thus, if these r_ℓ(σ) edges have opposite direction to the edge “created” by σ (from the perspective of σ), σ will be balanced.

Consider any such ρ. Let x_0… x_k+1 be the ordering of ρ such that σ = {x_1, …, x_k+1} and x_1 … x_k+1 are ordered according to their labels. Let t ∈ [k+1] be the index of label *^i ℓ if we order the labels in S(O(ρ)). Then, we also have that τ = σ∖{x_t}. Furthermore, x_1 … x_t-1 x_t+1… x_k+1 are also ordered according to their labels. From the perspective of σ, the edge it “created” is directed according to (σ|x_t x_1 … x_t-1 x_t+1… x_k+1) and the edge created by ρ is directed according to - (ρ|x_0 x_1 … x_k+1). As before, let x_j denote the coordinates of x_j restricted to O(ρ), where the coordinates are ordered according to the associated label. Let x̅_j denote the coordinates of x_j restricted to O(σ), where the coordinates are ordered according to the associated label. Note that if we remove the tth coordinate from x_j, then we obtain x̅_j. We now have

    (ρ|x_0 x_1 … x_k+1)    =  [x_0-x_1, …, x_0-x_k+1]
       =  [x_t-x_1, …, x_t-x_t-1, x_0-x_t, x_t-x_t+1, …, x_t-x_k+1]
       = (-1)^t+t [x̅_t-x̅_1, …, x̅_t-x̅_t-1, x̅_t-x̅_t+1, …, x̅_t-x̅_k+1]
       = (σ|x_t x_1 … x_t-1 x_t+1… x_k+1)

where we first subtracted the tth column from all other columns, and then we used Laplace's determinant formula along the tth row. Note that the tth entry in x_t-x_j is 0 for all j ∈ [k+1] and it is 1 in x_0-x_t.





  
*Consistency.
The only thing that remains to be checked is that edges of Type 1 are well-defined, in terms of the direction. Let σ_1,σ_2 be two happy k-simplices that lie in the same sub-orthant and share a facet τ with λ(τ) = S(O(σ_i)), i=1,2. Let {x_1, …, x_k} = τ and x_1 … x_k be the ordering according to their labels. Let {x_0} = σ_1 ∖τ and {x_0'} = σ_2 ∖τ. We want to show that (σ_1|x_0 x_1 … x_k) and (σ_2|x_0' x_1 … x_k) have opposite signs. This can be proved directly combinatorially by using the way the triangulation is constructed, but we provide a proof that is more general here. Let ϕ: ℝ^k →ℝ^k be the unique linear function such that ϕ(x_0-x_1)=x_0'-x_1 and ϕ(x_1-x_i)=x_1-x_i for all i ∈ [k] ∖{1}. ϕ is unique, because x_0-x_1, x_1-x_2, …, x_1-x_k form a basis of ℝ^k. ϕ is the identity function on the hyperplane given by x_1-x_2, …, x_1-x_k and maps x_0-x_1 to x_0'-x_1. Since x_0 and x_0' lie on opposite sides of the hyperplane defined by τ, it follows that x_0-x_1 and x_0'-x_1 lie on opposite sides of the hyperplane on which ϕ is the identity. It follows that ϕ < 0. Thus, we can write

    [x_0'-x_1, …, x_0'-x_k]    =  [x_0'-x_1, x_1-x_2 …, x_1-x_k]
       = ϕ [x_0-x_1, x_1-x_2 …, x_1-x_k]
       = ϕ [x_0-x_1, …, x_0-x_k]

and the claim follows.



