A Topological Characterization of Modulo-$p$ Arguments and Implications for Necklace Splitting

Introduction

The class TFNP (Megiddo and Papadimitriou, 1991) 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, Papadimitriou (1994) defined several subclasses of TFNP, such as PPAD, PPA and PPP, among others, each of which is associated with a different existence principle. For example, PPAD 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; PPA is based on a similar principle on an undirected graph, and PPP is based on the pigeonhole principle.

Among those, PPAD has been largely successful in capturing the complexity of many well-known problems, most prominently that of computing Nash equilibria in games (Daskalakis et al., 2009; Chen et al., 2009b). PPA and PPP have been more elusive in that regard for nearly two decades, until the recent results of Filos-Ratsikas and Goldberg (2018, 2019) and Sotiraki et al. (2018), 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 (Grigni, 2001)). Interestingly, the PPA-complete problems in (Filos-Ratsikas and Goldberg, 2018, 2019) that solidified the status of PPA 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 (Simmons and Su, 2003)).

Questions about the computational complexity of finding a solution were raised explicitly as early as when the first existence results were proven (Goldberg and West, 1985) and then later on by a series of papers (Alon, 1988, 1990; Meunier, 2008; Meunier and Sebő, 2009; Meunier and Neveu, 2012). The first definitive answer was provided by Filos-Ratsikas and Goldberg (2019), via their PPA-completeness result, following an initial PPAD-hardness result by Filos-Ratsikas et al. (2018). Crucially however, their result only applies to the case of two thieves.The authors also extend the PPA membership straightforwardly to numbers of thieves which are powers of $2$. In fact, the authors observed (also referencing de Longueville and Živaljević (2006) and Meunier (2014) as previously having made similar observations) that the version of the problem with $p\geq 3$ thieves does not seem to boil down to the principle associated with the class PPA. To this end, they conjectured that $p$-thief Necklace Splitting is complete for the computational class PPA-$p$, also defined by Papadimitriou (1994), 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 \textup{PPA-2}=\textup{PPA}.

The classes PPA-$p$ have been very recently studied by Hollender (2019) and Göös et al. (2020). The authors of the latter paper in fact provide the first PPA-$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 PPA-membership (Filos-Ratsikas et al., 2018) and for PPA-hardness (Filos-Ratsikas and Goldberg, 2019) of the problem, are obtained via reductions to/from a computational version of Tucker’s Lemma (Tucker, 1945), a discrete analogue to the Borsuk-Ulam theorem, proven to be PPA-complete by Papadimitriou (1994) and Aisenberg et al. (2020). 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 (Filos-Ratsikas et al., 2018) is in fact a direct adaptation of a combinatorial existence proof of Simmons and Su (2003) for the Consensus-Halving problem, which goes via Tucker’s lemma.

In order to obtain a PPA-$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 \textup{PPA}=\textup{PPA-2}, but also facilitated the success of PPAD 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 (Brouwer, 1911) and Sperner’s Lemma (Sperner, 1928)).To be more precise, several important PPAD-hardness results were obtained via reductions from the Generalized Circuit problem (Daskalakis et al., 2009; Chen et al., 2009b; Rubinstein, 2018), which was however proven to be PPAD-complete via the aforementioned topological problems. In a very related manner, Simmons and Su (2003) 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, Göös et al. (2020) explicitly raised the complexity of one of these generalizations, the BSS Theorem, as an open problem.

In this paper, we obtain such a topological characterization of the classes PPA-$p$, for all primes $p\geq 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 PPA-$p$. A highlight of our generalizations is the PPA-$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 PPA-$p$.

they solidify the status of the classes PPA-$p$ as classes containing interesting well-known problems (adding to the recent results of Göös et al. (2020)), and

they set up an essential toolkit for obtaining more completeness results for the classes, e.g., possibly the PPA-$p$-completeness of $p$-thief Necklace Splitting.

A combinatorial proof of the BSS theorem. The original proof by Bárány et al. (1981) 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 (Alon, 1987). This open problem was solved by Meunier (2014) 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 (Alon, 1987; Simmons and Su, 2003). 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 Theorem 6.5.

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 Section 1.1.1, which we call $k$-Polygon Tucker’s Lemma. Then, we present our results about the completeness of the well-studied BSS Theorem in Section 1.1.2. Finally, we briefly explain how we get our new combinatorial proof of Necklace Splitting and the containment in PPA-$p$, in Section 1.1.3.

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

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^{\circ}$ degrees, we assume equivariance to a rotation of $(360/k)^{\circ}$ degrees.

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 PPA-$p$-completeness results. Also, it is the only one of our topological problems which is defined for any $k\geq 2$, and thus the only problem which we are able to relate to the classes PPA-$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 (Bárány et al., 1981) 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.

The coloring function $\lambda$ is equivariant to a rotation of $\alpha^{\circ}$ degrees on the boundary if whenever the argument $\boldsymbol{x}$ is rotated by $\alpha^{\circ}$, the color is increased by $1\pmod{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 (Papadimitriou, 1994) and there have been various instantiations of this principle from which we can define corresponding computational problems (Göös et al., 2020; Hollender, 2019). In this paper, we mostly rely on the following instantiation defined by Hollender (2019):

Imbalance-mod-$k$ : Given a directed graph and a vertex that is imbalanced-mod-$k$, i.e., $(\mathsf{out}\text{-}\mathsf{degree})-(\mathsf{in}\text{-}\mathsf{degree})\neq 0\pmod{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 Imbalance-mod-$k$. Towards this goal, we provide a generalization of the standard path-following proof of Tucker’s lemma by Freund and Todd (1981). Importantly, in our proof (which is a reduction to Imbalance-mod-$k$) the edges of the path are directed by using a consistent direction of triangulations (inspired by the idea of Freund (1984)). This technique was in fact incorrectly applied in the past to the case of $k=2$, leading to a false statement of PPAD-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 Imbalance-mod-$k$ problem and we believe that this will be useful for future reductions in PPA-$k$.

The computational equivalence between $k$-Polygon Tucker’s Lemma and Imbalance-mod-$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 PPA-$k$-complete. If $k$ is not a prime power, then it is complete for a subclass of PPA-$k$, denoted by \textup{PPA-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 Imbalance-mod-$k$. If $k$ is a prime power, then this special case is in fact PPA-$k$-complete, but in general it can be weaker.

The formal definitions and the complete proofs, including the proof of 4, about the $k$-Polygon Borsuk-Ulam Theorem appear in Section 3.

1.2 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\geq 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^{\circ}$ that is a free action in any number of dimensions, namely, the point reflection with respect to the origin, i.e., $x\mapsto-x$. Hence, we have the following informal statement of the Borsuk-Ulam Theorem for a general number of dimensions.

The original proof of the BSS Theorem (Bárány et al., 1981) 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.

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 (Theorem 4.8).

The computational problem associated with $p$-Polygon Tucker’s Lemma is reducible to the computational problem associated with BSS Tucker’s Lemma (Theorem 4.10).

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

We defer the formal definition of the computational problem associated with the BSS Theorem and the complete proofs, including the proof of 8, about the BSS Theorem appear in Section 4.

1.3 Necklace Splitting with p𝑝p thieves is in PPA-p𝑝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 PPA-$p$. Towards this goal we provide a full combinatorial proof for both of these problems that simplifies the only existing combinatorial proof by Meunier (2014).

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 $\mu_{i}$ over the unit interval $$. The goal is to cut the interval$$ 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.

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 Section 1.2.

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

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

As a corollary of this result, we also obtain that for general $k\geq 2$, $k$-Necklace Splitting and Consensus-$1/k$-Division lie in PPA-$k$ under Turing reductions. In particular, if $k=p^{r}$ is a prime power, then the corresponding problems lie in PPA-$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.

Our results are summarized in Table 1, 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.

2 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 (Daskalakis et al., 2009; Chen et al., 2009b; Rubinstein, 2018), other PPAD-complete problems are computing equilibria in markets (Chen et al., 2009a, 2013), versions of envy-free cake cutting (Deng et al., 2012) and fixed-point theorems (Mehta, 2014; Goldberg and Hollender, 2019).

For PPA, the recent results by Filos-Ratsikas and Goldberg (2018, 2019) have solidified the status of the class as one that contains natural problems. In particular, they showed that $2$-thief Necklace Splitting is PPA-complete; the proof goes via its continuous version, the Consensus-Halving problem of Simmons and Su (2003)The hardness result of Filos-Ratsikas and Goldberg (2018, 2019) for the Consensus-Halving problem was strengthened recently by Filos-Ratsikas et al. (2020) to the case of simpler measures. Our PPA-$p$-membership result for the problem with $p$ thieves also uses the continuous variant, termed as Consensus-$1/p$-Division in (Simmons and Su, 2003); we note that Alon (1987) used the same problem in his existence proof, referring to it as a generalized Hobby-Rice Theorem. As we explained earlier, Filos-Ratsikas and Goldberg (2019) conjectured that the problem with $p$ thieves is complete for PPA-$p$.

The classes PPA-$p$ were introduced by Papadimitriou (1994) for any prime $p$, in the context of classifying a computational version of the Chevalley-Warning theorem (Chevalley, 1935; Warning, 1935). He proved that the corresponding problem Chevalley-mod-$p$ lies in PPA-$p$. Recently, Göös et al. (2020) showed that an explicit version of the problem is complete for PPA-$p$, therefore obtaining the first PPA-$p$-completeness result for a natural problem. The authors of (Göös et al., 2020), as well as Hollender (2019), independently also extended the definition of the classes PPA-$k$ to any $k\geq 2$, and provided several characterizations in terms of their defined-for-primes counterparts. Hollender (2019) also investigated the connection with the classes PMOD-$k$, which bear strong resemblance to PPA-$k$, and were defined seemingly independently of Papadimitriou’s work by Johnson (2011). From the work of Hollender (2019), we primarily make use of the PPA-$k$-complete computational problem Imbalance-mod-$k$, a generalization of the PPAD-complete problem Imbalance (Beame et al., 1998; Goldberg and Hollender, 2019).

Necklace Splitting: The origins of the Necklace Splitting problem (9), and its continuous variant (10), can be traced back to work of Neyman (1946) and Hobby and Rice (1965). The problem was firstly phrased as a necklace splitting problem by Bhatt and Leiserson (1982). Later on, Goldberg and West (1985) and Alon and West (1986) proved the first existence results for two thieves, and Alon (1987) extended the result to the case of any number $k\geq 2$ of thieves. For two thieves, the continuous version was studied independently by Simmons and Su (2003), who termed the problem as “Consensus-Halving” and came up with a combinatorial, constructive proof of existence; this proof was later modified into a PPA membership proof by Filos-Ratsikas et al. (2018). The importance of obtaining combinatorial proofs of existence was highlighted in a series of papers (de Longueville and Živaljević, 2006; Meunier, 2008, 2014; Meunier and Neveu, 2012); note that the proof of Alon (1987) uses two results of Bárány et al. (1981) and is therefore not combinatorial. The first fully combinatorial proof for Necklace Splitting (according to the definition of Ziegler (2002)) is due to Meunier (2014). 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, Alon and Graur (2020) 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 (Filos-Ratsikas and Goldberg, 2018, 2019; Filos-Ratsikas et al., 2020)).

The BSS Theorem: The BSS Theorem (6, Theorem 4.2), due to (Bárány et al., 1981), is perhaps the most well-known generalization of the Borsuk-Ulam theorem. Besides (Alon, 1987), it has been used to prove existence of other interesting problems, including a generalization of the Kneser-Lovász Theorem (Kneser, 1955; Lovász, 1978) due to Alon et al. (1986), a generalized van Kampen-Flores Theorem (Sarkaria, 1991) and the generalization to Tverberg’s Theorem, proven in (Bárány et al., 1981). We believe that our PPA-$p$-completeness result paves the way for studying the complexity of those problems as well.

Preliminaries

Let $\{0,1\}^{*}$ denote the set of all finite length bit-strings. For $x\in\{0,1\}^{*}$, let $|x|$ be its length. A computational search problem is given by a binary relation $R\subseteq\{0,1\}^{*}\times\{0,1\}^{*}$. The associated problem is: given an instance $x\in\{0,1\}^{*}$, find a $y\in\{0,1\}^{*}$ such that $(x,y)\in 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)\in R$ can be decided in polynomial time in $|x|+|y|$) and there exists some polynomial $p$ such that $(x,y)\in R\implies|y|\leq p(|x|)$. Thus, FNP is the search problem version of NP.

The class TFNP (Total Functions in NP (Megiddo and Papadimitriou, 1991)) contains all FNP search problems $R$ that are total: for every $x\in\{0,1\}^{*}$ there exists $y\in\{0,1\}^{*}$ such that $(x,y)\in 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\leq S$, if there exist polynomial-time computable functions $f,g$ such that

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\leq S$ and $S\leq 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.

2 The Classes PPA-k𝑘k

For $k\geq 2$, PPA-$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 PPA-$p$ (for prime $p$) were introduced by Papadimitriou (1994). The case $p=2$ corresponds to parity arguments, and in that case the class PPA-$2$ is simply called PPA. Recently, the definition of PPA-$k$ was extended to any $k\geq 2$ by Göös et al. (2020); Hollender (2019). The class PPA-$k$ is defined as the class of TFNP problems that reduce to the following problem.

Let $k\geq 2$. The problem Bipartite-mod-$k$ is defined as: given a Boolean circuit $C:\{0,1\}\times\{0,1\}^{n}\to(\{0,1\}\times\{0,1\}^{n})^{k}$ that computes a bipartite graph on the vertex set $(\{0\}\times\{0,1\}^{n},\{1\}\times\{0,1\}^{n})$ with $|C(00^{n})|\in\{1,\dots,k-1\}$, find

$x\neq 00^{n}$ such that $|C(x)|\notin\{0,k\}$

or $x,y$ such that $y\in C(x)$ but $x\notin 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\in\{0\}\times\{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\}\times\{0,1\}^{n}$. Similarly, if $x\in\{1\}\times\{0,1\}^{n}$, then $C(x)$ denotes the set of distinct bit-strings that appear in that list and that lie in $\{0\}\times\{0,1\}^{n}$. For any $x,y\in\{0,1\}\times\{0,1\}^{n}$, there exists an edge between $x$ and $y$ if and only if $y\in C(x)$ and $x\in C(y)$. It is easy to see that this indeed defines a bipartite graph.

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

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

\textup{PPA-k}[\#1]=\cap_{p\in PF(k)}\textup{PPA-p}, where $PF(k)$ denotes the set of prime factors of $k$.

In this paper, we will also use the following definition of PPA-$k$, which was shown to be equivalent to the standard one (Hollender, 2019). The class PPA-$k$ is the set of all TFNP problems that reduce to the following problem.

Let $k\geq 2$. The problem Imbalance-mod-$k$ is defined as: given Boolean circuits $S,P:\{0,1\}^{n}\to(\{0,1\}^{n})^{k}$ with $|S(0^{n})|-|P(0^{n})|\neq 0\mod k$, find

$x\neq 0^{n}$ such that $|S(x)|-|P(x)|\neq 0\mod k$

or $x,y$ such that $y\in S(x)$ but $x\notin P(y)$, or $y\in P(x)$ but $x\notin S(y)$.

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:

for any prime $p$ and any $r\geq 1$, \textup{PPA-p^{r}}=\textup{PPA-p}

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 Appendix A. There, we also define our value and index functions, which allow us to enumerate over simplices, and access simplices that contain a point $\mathbf{x}$ in the domain respectively.

k𝑘k-Polygon Borsuk-Ulam: a PPA-k​[#​1]PPA-kdelimited-[]#1\textup{PPA-$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 \textup{PPA-k}[\#1]. This gives the first topological characterization of the classes \textup{PPA-k}[\#1] but also reveals in a very intuitive way the relation between the different \textup{PPA-k}[\#1] classes and PPAD. Recall that when $k=p^{r}$ is a prime power, \textup{PPA-k}[\#1]=\textup{PPA-k}=\textup{PPA-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.

In other words, $\theta_{k}$ corresponds to a clockwise rotation by an angle of $2\pi/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 (Matoušek, 2008)).

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

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 $\textup{PPAD}\subseteq\textup{PPA}$, since Brouwer is complete for PPAD and Borsuk-Ulam is complete for PPA. We now present our extension, that we call $k$-Polygon Borsuk-Ulam Theorem.

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 \textup{PPA-k}[\#1] which is also in line with the fact that \textup{PPAD}\subseteq\textup{PPA-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.

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 \textup{PPA-k}[\#1].

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

it is symmetric with respect to $\theta_{k}$ on the boundary. This means that for every edge $\psi\in T$ such that $\psi\subseteq\partial W_{k}$ it holds that $\theta_{k}(\psi)\in T$.

The above theorem can be proved if we invoke Dold’s Theorem from algebraic topology Dold (1983). 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.

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 Lemma 3.5 and Lemma 3.6.

$k$-Polygon Borsuk-Ulam (Theorem 3.3) implies $k$-Polygon Tucker’s Lemma (Theorem 3.4).

Now, let $\sigma^{\star}$ be a full-dimensional simplex of $T$ that contains $\mathbf{x}^{\star}$. If the vertices of $\sigma^{\star}$ have only two consecutive labels, say $1$ and $2$ (corresponding to vectors $\mathbf{u}_{1}$ and $\mathbf{u}_{2}$), then it is impossible to have $h(\mathbf{x}^{\star})=0$ since it is a non-zero linear interpolation of $\mathbf{u}_{1}$ and $\mathbf{u}_{2}$ and these vectors are linearly independent. Hence, it has to be that the vertices of $\sigma^{\star}$ have either two non-consecutive labels or three different labels and $k$-Polygon Tucker’s Lemma follows. ∎

$k$-Polygon Tucker’s Lemma (Theorem 3.4) implies $k$-Polygon Borsuk-Ulam (Theorem 3.3).

In this case, $3$-Polygon Tucker’s Lemma implies that there exists a simplex $\sigma\in T$ whose vertices $\boldsymbol{v}_{1}$, $\boldsymbol{v}_{2}$, $\boldsymbol{v}_{3}$ contain all the labels $1$, $2$, and $3$ respectively. This implies the following set of inequalities by the definition of the labeling $\lambda$

Hence, it is easy to see that the maximum angle between any of $h(\boldsymbol{v}_{1})$, $h(\boldsymbol{v}_{2})$ and $h(\boldsymbol{v}_{3})$ is at least $2\pi/3$. Now, assume for the sake of contradiction that for all $\boldsymbol{v}_{1}$, $\boldsymbol{v}_{2}$, $\boldsymbol{v}_{3}$ it holds that

This together with the fact that the maximum angle is at least $2\pi/3$ implies that the maximum distance is at least $2\sin(2\pi/6)\varepsilon$. But this implies that

which contradicts the definition of the triangulation $T$, where the vertices of the same simplex are at most $\delta$ far from each other and hence their images are at most $\varepsilon/k=\varepsilon/3$ far from each other. This implies that our assumption was wrong and hence for at least one $i\in$ it holds that $\left\|h(\boldsymbol{v}_{i})\right\|\leq\varepsilon$ and the result for this case follows.

In this case, $k$-Polygon Tucker’s Lemma implies that there exists an edge $\psi\in T$ whose vertices $\boldsymbol{v}_{1}$ and $\boldsymbol{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 $\lambda$ this implies that

Hence, it is easy to see that the angle between $h(\boldsymbol{v}_{1})$ and $h(\boldsymbol{v}_{2})$ is at least $2\pi/k$. Now, for sake of contradiction we assume that

This together with the fact that the angle is at least $2\pi/k$ implies that the distance $\left\|h(\boldsymbol{v}_{1})-h(\boldsymbol{v}_{2})\right\|$ is at least $2\sin(2\pi/k)\varepsilon>\varepsilon/k$ which contradicts the definition of $T$.

Therefore, in both cases for every $\varepsilon>0$ we can find a $\boldsymbol{v}\in W_{k}$ such that $\left\|h(\boldsymbol{v})\right\|\leq\varepsilon$. This, by standard arguments and the compactness of $W_{k}$, implies that there exists a point $\boldsymbol{x}^{\star}\in W_{k}$ such that $h(\boldsymbol{x}^{\star})=\boldsymbol{0}$ and hence the result follows. ∎

1.2 Proof of k𝑘k-Polygon Tucker’s Lemma

In this section, we prove $k$-Polygon Tucker’s Lemma. A corollary of our proof combined with Lemma 3.6 is that the computational problems associated with $k$-Polygon Tucker’s Lemma and $k$-Polygon Borsuk-Ulam both belong to \textup{PPA-k}[\#1]. The proof technique that we introduce here is a generalization of the combinatorial proof of Tucker’s lemma given by Freund and Todd (1981).

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 -dimensional simplex $\{\boldsymbol{0}\}$ which will have degree $1$,

vertices that are balanced $\pmod{k}$, i.e., $(\mathsf{out}\text{-}\mathsf{degree})-(\mathsf{in}\text{-}\mathsf{degree})=0\pmod{k}$,

vertices that are different from $\{\boldsymbol{0}\}$ and are not balanced $\pmod{k}$.

Due to a simple modulo-$k$ argument and because $\{\boldsymbol{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 Imbalance-mod-$k[\#1]$.

For any simplex $\sigma\in T$ we define $S(\sigma)$ and $\lambda(\sigma)$:

$S(\sigma)\subseteq[k]$ is the minimal subset of $[k]$ such that $\sigma$ lies in the cone defined by $\{\boldsymbol{u}_{i}:i\in S(\sigma)\}$,

$\lambda(\sigma)=\{\lambda(\boldsymbol{x}):\boldsymbol{x}\text{ is a vertex of }\sigma\}$,

and we let $S(\{\boldsymbol{0}\})=\emptyset$.

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

A simplex $\sigma\in T$ is called happy if and only if $S(\sigma)\subseteq\lambda(\sigma)$. See also Figure 1 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:

vertices that correspond to a simplex $\sigma\in T$ such that $\sigma\not\in\partial T$ and $\sigma$ is happy,

vertices that correspond to a simplex $\psi\in\partial T$ such that $\psi$ is happy and:

$\psi=\{u_{1}\}$, if $\psi$ is -dimensional

$\psi\subseteq\mathsf{conv}(\{\boldsymbol{u}_{1},\boldsymbol{u}_{2}\})$, if $\psi$ 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 $(\mathsf{out}\text{-}\mathsf{degree})=(\mathsf{in}\text{-}\mathsf{degree})=0$ or as having a self-loop. In both cases, these vertices are balanced.

We add an edge $(v,v^{\prime})$ to the graph $G$ only if the simplices $\sigma$ and $\sigma^{\prime}$ that correspond to $v$ and $v^{\prime}$ are both relevant and one of the following rules applies:

case $\boldsymbol{\sigma\not\in\partial T,\sigma^{\prime}\not\in\partial T:}$ We add the edge if $\sigma^{\prime}\subseteq\sigma$ and the labels of $\sigma^{\prime}$ suffice to make $\sigma$ happy, i.e., $S(\sigma)\subseteq\lambda(\sigma^{\prime})$,

case $\boldsymbol{\sigma\not\in\partial T,\sigma^{\prime}\in\partial T:}$ Observe that since $v^{\prime}$ is relevant and $\sigma^{\prime}\in\partial T$, $v^{\prime}$ is of type (b). So, instead of checking whether $\sigma^{\prime}\subseteq\sigma$, we check whether there exists $t\in[k]$ such that $\tau:=\theta^{(t)}_{k}(\sigma^{\prime})\subseteq\sigma$ and $\tau$ suffices to make $\sigma$ happy, i.e., $S(\sigma)\subseteq\lambda(\tau)$.

The edge between $\sigma$ and $\sigma^{\prime}$ is directed in the following natural way:

if $\sigma$ is 1-dimensional, then $\sigma$ and $\sigma^{\prime}$ lie in $\mathsf{conv}(\{0,\boldsymbol{u}_{i}\})$ for some $i$, and the edge is directed “away from ”. Formally, if $\sigma=\{\boldsymbol{z}_{0},\boldsymbol{z}_{1}\}$ and $\sigma^{\prime}=\{\boldsymbol{z}_{1}\}$ are connected by an edge, then write $\boldsymbol{z}_{0}=\alpha_{i}u_{i}$ and $\boldsymbol{z}_{1}=\beta_{i}u_{i}$. If $\alpha_{i}-\beta_{i}>0$, then the edge is incoming into $\sigma$. If $\alpha_{i}-\beta_{i}<0$, then the edge is outgoing out of $\sigma$.

if $\sigma$ is 2-dimensional, then $\sigma$ and $\sigma^{\prime}$ lie in $\mathsf{conv}(\{0,\boldsymbol{u}_{i},\boldsymbol{u}_{j}\})$ for some $i,j$ with $i-j=\pm 1\pmod{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 $\sigma=\{\boldsymbol{z}_{0},\boldsymbol{z}_{1},\boldsymbol{z}_{2}\}$ and $\sigma^{\prime}=\{\boldsymbol{z}_{1},\boldsymbol{z}_{2}\}$ are connected by an edge, where $\lambda(\boldsymbol{z}_{1})=i$ and $\lambda(\boldsymbol{z}_{2})=j$, then write $\boldsymbol{z}_{0}=\alpha_{i}\boldsymbol{u}_{i}+\alpha_{j}\boldsymbol{u}_{j}$, $\boldsymbol{z}_{1}=\beta_{i}\boldsymbol{u}_{i}+\beta_{j}\boldsymbol{u}_{j}$ and $\boldsymbol{z}_{2}=\gamma_{i}\boldsymbol{u}_{i}+\gamma_{j}\boldsymbol{u}_{j}$. Construct the matrix

If $\det M>0$, then the edge is incoming into $\sigma$. If $\det M<0$, then the edge is outgoing out of $\sigma$. Notice that $\det M\neq 0$, because $\sigma$ is a simplex. Furthermore, note that the determinant of the matrix does not change if we switch both $i$ and $j$, and $\boldsymbol{z}_{1}$ and $\boldsymbol{z}_{2}$ (i.e., $\beta$ and $\gamma$). Thus, the direction is well-defined.

If $\sigma^{\prime}$ corresponds to a vertex of type (b), then we apply the rule above to $\sigma$ and $\tau$ 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 $\{\boldsymbol{0}\}\in T$ has out-degree $1$ and in-degree .

Since $\{\boldsymbol{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 $\psi\in T$ that is not contained in a linear segment of the form $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$ cannot be a neighbor of $\{\boldsymbol{0}\}$, because it requires two labels to become happy and $\{\boldsymbol{0}\}$ has only one single label. Hence, $\{\boldsymbol{0}\}$ can only be connected to a $1$-dimensional simplex $\{\boldsymbol{0},\boldsymbol{z}_{i}\}$ contained in $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$ for some $i$. Observe also that $S(\{\boldsymbol{0},\boldsymbol{z}_{i}\})=\{i\}$, which implies that $S(\{\boldsymbol{0},\boldsymbol{z}_{i}\})=\{\lambda(\boldsymbol{0})\}$. Therefore, there is exactly one 1-dimensional simplex that is connected to $\{\boldsymbol{0}\}$, namely $\{\boldsymbol{0},\boldsymbol{z}_{i}\}$, where $i=\lambda(\boldsymbol{0})$.

Furthermore, since $\{\boldsymbol{0}\}$ and its neighbor $\{\boldsymbol{0},\boldsymbol{z}_{i}\}$ lie in $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$, the edge is directed away from $\{\boldsymbol{0}\}$. Formally, if we write $\boldsymbol{z}_{i}=\alpha_{i}u_{i}$ and $\boldsymbol{0}=\beta_{i}u_{i}$, it will hold that $\alpha_{i}-\beta_{i}=\alpha_{i}>0$. This means that the edge is incoming into $\{\boldsymbol{0},\boldsymbol{z}_{i}\}$ and the lemma follows. ∎

Any vertex $v$ in $G$ that is imbalanced modulo-$k$, i.e., $(\mathsf{out}\text{-}\mathsf{degree}(v))\neq(\mathsf{in}\text{-}\mathsf{degree}(v))\pmod{k}$ and does not correspond to the simplex $\{\boldsymbol{0}\}$, corresponds to a simplex $\sigma$ that is either trichromatic or $\lambda(\sigma)\not\subseteq\{i,i+1\}$ for all $i\in[k]$.

For this proof, we consider all three cases for the dimension of the simplex $\sigma^{\star}$ that corresponds to an imbalanced node of $G$ separately.

Dimension of $\boldsymbol{\sigma^{\star}}$ is $\boldsymbol{0}$. In this case, $\sigma^{\star}=\{\boldsymbol{z}^{\star}\}$. It is easy to see that $\sigma^{\star}$ cannot make happy any $2$-dimensional simplex since a $2$-dimensional simplex $\sigma$ has $|S(\sigma)|=2$. So, $\sigma^{\star}$ can only be a neighbor of a $1$-dimensional simplex $\psi$. Additionally, $\sigma^{\star}$ cannot make happy any $1$-dimensional $\psi$ such that $|S(\psi)|=2$. Thus, a neighbor of $\sigma^{\star}$ should be contained in the segment $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$ where $i$ is such that $\lambda(\sigma^{\star})=i$. If $\boldsymbol{z}^{\star}\neq\boldsymbol{u}_{i}$, then $\sigma^{\star}$ is connected to both of its two neighboring $1$-dimensional simplices in the segment $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$. Then, since the edges are directed away from $\boldsymbol{0}$, $\sigma^{\star}$ has one incoming and one outgoing edge. Formally, let $\{\boldsymbol{z}_{0},\boldsymbol{z}^{*}\}$ and $\{\boldsymbol{z}^{*},\boldsymbol{z}_{0}^{\prime}\}$ be the two neighboring $1$-dimensional simplices, and write $\boldsymbol{z}_{0}=\alpha_{i}u_{i}$, $\boldsymbol{z}_{0}^{\prime}=\alpha_{i}^{\prime}u_{i}$ and $\boldsymbol{z}^{*}=\beta_{i}u_{i}$. It is easy to see that $\alpha_{i}-\beta_{i}$ and $\alpha_{i}^{\prime}-\beta_{i}$ always have opposite signs, since $\boldsymbol{z}_{0}$ and $\boldsymbol{z}_{0}^{\prime}$ lie on opposite sides of $z^{\star}$ on $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$.

If $\boldsymbol{z}^{\star}=\boldsymbol{u}_{i}$, then from the definition of relevant vertices of $G$ we have that $\boldsymbol{z}^{\star}=\boldsymbol{u}_{1}$ and $\{\boldsymbol{u}_{1}\}$ is happy, i.e., $\lambda(\boldsymbol{u}_{1})=1$. Thus, by the boundary conditions, for every $t\in[k]$, it holds that $\lambda(\theta_{k}^{(t)}(\boldsymbol{u}_{1}))=t+1$. In other words, $\lambda(\boldsymbol{u}_{i})=i$ for all $i\in[k]$. As a result, it follows that for each $i\in[k]$, $\{\boldsymbol{u}_{1}\}$ has an edge with the simplex $\{\boldsymbol{u}_{i},\boldsymbol{z}_{i}\}$ which lies in $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$. This holds because $\theta_{k}^{(i)}(\{\boldsymbol{u}_{1}\})$ suffices to make $\{\boldsymbol{u}_{i},\boldsymbol{z}_{i}\}$ happy. Clearly, $\theta_{k}^{(i)}(\{\boldsymbol{u}_{1}\})$ cannot make any other simplex happy, by the same arguments as above. Finally, note that all the edges are incoming into $\{\boldsymbol{u}_{1}\}$, because edges are directed away from $\boldsymbol{0}$ on any $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$. Formally, if we write $\boldsymbol{z}_{i}=\alpha_{i}u_{i}$ and $\boldsymbol{u}_{i}=\beta_{i}u_{i}$, then we always have $\alpha_{i}-\beta_{i}=\alpha_{i}-1<0$, so the edge is outgoing out of $\{\boldsymbol{u}_{i},\boldsymbol{z}_{i}\}$. Thus, in this case, $\boldsymbol{z}^{\star}$ has $k$ neighbors and all of them with the same direction. Therefore, $\boldsymbol{z}^{\star}$ is always balanced modulo-$k$. In conclusion, an imbalanced vertex of $G$ different from $\{\boldsymbol{0}\}$ cannot have dimension .

Dimension of $\boldsymbol{\sigma^{\star}}$ is $\boldsymbol{1}$. First, assume that $\sigma^{\star}=\{\boldsymbol{z}^{\star}_{1},\boldsymbol{z}^{\star}_{2}\}$ belongs to one of the line segments $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$. If additionally $\lambda(\boldsymbol{z}^{\star}_{1})=\lambda(\boldsymbol{z}^{\star}_{2})$, then $\sigma^{\star}$ is happy if $\lambda(\boldsymbol{z}^{\star}_{1})=\lambda(\boldsymbol{z}^{\star}_{2})=i$. Therefore, $\left|\lambda(\sigma^{\star})\right|=1$ and hence $\sigma^{\star}$ cannot be a neighbor of a $2$-dimensional $\sigma$ since $\left|S(\sigma)\right|=2$ and $\sigma^{\star}$ cannot make $\sigma$ happy. So, $\sigma^{\star}$ has exactly the two neighbors $\{\boldsymbol{z}^{\star}_{1}\}$ and $\{\boldsymbol{z}^{\star}_{2}\}$ since both of them make $\sigma^{\star}$ 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 $\boldsymbol{0}$ on $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$. Formally, if we write $\boldsymbol{z}^{\star}_{1}=\alpha_{i}u_{i}$ and $\boldsymbol{z}^{\star}_{2}=\alpha_{i}^{\prime}u_{i}$, then $\alpha_{i}-\alpha_{i}^{\prime}$ and $\alpha_{i}^{\prime}-\alpha_{i}$ always have opposite signs.

The next case we consider is when $\sigma^{\star}\subseteq\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i}\})$ with $i=\lambda(\boldsymbol{z}^{\star}_{1})\neq\lambda(\boldsymbol{z}^{\star}_{2})=j$. If $i-j\neq\pm 1$, then $\sigma^{\star}$ yields a solution to $k$-Polygon Tucker, and so is allowed to be imbalanced. On the other hand, if $j=i\pm 1\pmod{k}$, $\sigma^{\star}$ has exactly two neighbors, the simplex $\{\boldsymbol{z}^{\star}_{1}\}$, which makes $\sigma^{\star}$ happy, and the unique $2$-dimensional simplex $\sigma=\{\boldsymbol{z}^{\star}_{1},\boldsymbol{z}^{\star}_{2},\boldsymbol{z}_{3}\}$ that contains $\sigma^{\star}$ as a face and is contained in the cone $\mathsf{conv}(\{\boldsymbol{u}_{i},\boldsymbol{0},\boldsymbol{u}_{j}\})$. Also, one of the edges is incoming and other one outgoing and hence $\sigma^{\star}$ cannot be imbalanced. Formally, write $\boldsymbol{z}_{2}^{\star}=\beta_{i}u_{i}$, $\boldsymbol{z}_{1}^{\star}=\beta_{i}^{\prime}u_{i}$ and $\boldsymbol{z}_{3}=\alpha_{i}u_{i}+\alpha_{j}u_{j}$. Then, it holds that the edge goes from $\{\boldsymbol{z}^{\star}_{1}\}$ to $\{\boldsymbol{z}^{\star}_{1},\boldsymbol{z}^{\star}_{2}\}$ if $\beta_{i}^{\prime}-\beta_{i}>0$, and otherwise in the other direction. Furthermore, the edge goes from $\sigma=\{\boldsymbol{z}^{\star}_{1},\boldsymbol{z}^{\star}_{2}\}$ to $\sigma=\{\boldsymbol{z}^{\star}_{1},\boldsymbol{z}^{\star}_{2},\boldsymbol{z}_{3}\}$, if $\det M>0$, where we can compute that $\det M=(\alpha_{i}-\beta_{i})\alpha_{j}-(\alpha_{i}-\beta_{i}^{\prime})\alpha_{j}=\alpha_{j}(\beta_{i}^{\prime}-\beta_{i})$. Since $\alpha_{j}>0$, it follows that both expressions have the same sign, and thus $\sigma^{\star}$ is balanced.

If $\sigma^{\star}\in\partial T$, then $\sigma^{\star}$ is relevant only if $\sigma^{\star}\subseteq\mathsf{conv}(\{\boldsymbol{u}_{1},\boldsymbol{u}_{2}\})$. In this case, $\sigma^{\star}$ has exactly $k$ neighbors each of which is a $2$-dimensional simplex that has as a face one of the $k$ symmetric copies of $\sigma^{\star}$. Namely, the neighbors of $\sigma^{\star}$ are $\sigma_{1},\dots,\sigma_{k}$, where $\theta_{k}^{(i)}(\sigma^{\star})$ makes $\sigma_{i}$ happy for all $i\in[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 $\mathsf{conv}(\{\boldsymbol{0},\boldsymbol{u}_{i},\boldsymbol{u}_{i+1}\})$. More formally, the sign of the determinant of the matrix $M(\sigma_{i},\theta_{k}^{(i)}(\sigma^{\star}))$ constructed to determine the direction of the edge with $\sigma_{i}$, will be the same for all $i\in[k]$. For a full formal proof, we again refer to the proof of Theorem 5.3.

Dimension of $\boldsymbol{\sigma^{\star}}$ is $\boldsymbol{2}$. Let $\sigma^{\star}=\mathsf{conv}(\{\boldsymbol{z}^{\star}_{1},\boldsymbol{z}^{\star}_{2},\boldsymbol{z}^{\star}_{3}\})$. Assume that $\sigma^{\star}$ is contained in the simplex $\mathsf{conv}(\{\boldsymbol{u}_{i},\boldsymbol{0},\boldsymbol{u}_{j}\})$, with $j=i\pm 1\pmod{k}$ and without loss of generality $\lambda(\boldsymbol{z}^{\star}_{1})=i$, $\lambda(\boldsymbol{z}^{\star}_{2})=j$. If $\lambda(\boldsymbol{z}^{\star}_{3})\not\in\{i,j\}$ then $\sigma^{\star}$ is a trichromatic triangle, and thus it can be imbalanced. Assume that $\lambda(\boldsymbol{z}^{\star}_{3})\in\{i,j\}$ and without loss of generality $\lambda(\boldsymbol{z}^{\star}_{3})=i$. In this case, $\sigma^{\star}$ has exactly two neighbors: the $1$-dimensional simplices $\psi_{1}=\mathsf{conv}(\{\boldsymbol{z}^{\star}_{1},\boldsymbol{z}^{\star}_{2}\})$ and $\psi_{2}=\mathsf{conv}(\{\boldsymbol{z}^{\star}_{3},\boldsymbol{z}^{\star}_{2}\})$. Once again, one edge is incoming and the other one is outgoing, and thus $\sigma^{\star}$ 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 $\boldsymbol{z}^{\star}_{1}=\alpha_{i}u_{i}+\alpha_{j}u_{j}$, $\boldsymbol{z}^{\star}_{2}=\beta_{i}u_{i}+\beta_{j}u_{j}$ and $\boldsymbol{z}^{\star}_{3}=\alpha_{i}^{\prime}u_{i}+\alpha_{j}^{\prime}u_{j}$, then it holds that:

by using standard rules about the determinant.

Hence, the only imbalanced vertices different from $\{\boldsymbol{0}\}$ correspond to either trichromatic simplices or simplices such that $\lambda(\sigma)\not\subseteq\{i,i+1\}$ for all $i\in[k]$. ∎

Finally, from the definition of the graph $G$ and Lemma 3.7, we have that there has to be a vertex in $G$ that is imbalanced $\pmod{k}$ and different from $\{\boldsymbol{0}\}$. By Lemma 3.8, any such vertex proves the validity of $k$-Polygon Tucker’s Lemma.

1.3 Computational Problems and Containment in PPA-k​[#​1]PPA-kdelimited-[]#1\textup{PPA-$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$-polygon-Tucker and $k$-polygon-Borsuk-Ulam respectively. Following the ideas presented in Section 3.1.2, we show that $k$-polygon-Tucker is in \textup{PPA-k}[\#1]. The membership of $k$-polygon-Tucker in \textup{PPA-k}[\#1] combined with the results of Section 3.1.1 implies that $k$-polygon-Borsuk-Ulam is also in \textup{PPA-k}[\#1].

For the edge parallel triangulation $\widehat{T}(m)$ of $W_{k}$ the following facts are easy to verify.

The diameter of $\widehat{T}(m)$ is at most $1/2^{m}$.

Given a set of binary vectors $A=\{\boldsymbol{a}_{i}\}_{i}$ where $\boldsymbol{a}_{i}\in\{0,1\}^{b}$, there exists an efficient procedure that determines whether $\mathsf{conv}(A)$ is a simplex of $\widehat{T}(m)$ or not.

Because of 3.10, we can assume that the labeling $\lambda$ of $\widehat{T}(m)$ is given via a circuit $\mathcal{L}$ with $b=\lceil\log(k)\rceil+2m+3$ input bits and $\lceil\log(k)\rceil$ output bits. The input to the circuit $\mathcal{L}$ is the representation of a potential vertex $\boldsymbol{x}$ in $\widehat{T}(m)$ according to 3.10 and the output is the label $\lambda(x)\in[k]$ of this vertex $\boldsymbol{x}$. Observe that 3.10 also guarantees that it is easy to check whether an input $\boldsymbol{a}\in\{0,1\}^{b}$ to the circuit $\mathcal{L}$ corresponds to a valid vertex $\boldsymbol{x}\in\widehat{T}(m)$. We are now ready to define the total search problem that is associated with $k$-Polygon Tucker’s Lemma.

$k$-polygon-Tucker Input: A circuit $\mathcal{L}:\{0,1\}^{b}\to\{0,1\}^{\lceil\log(k)\rceil}$, with $b=\lceil\log(k)\rceil+2m+3$. Output: One of the following. 1. Two binary vectors $\boldsymbol{a}_{1},\boldsymbol{a}_{2}\in\{0,1\}^{b}$ such that $\boldsymbol{a}_{1}$, $\boldsymbol{a}_{2}$ correspond to vertices $\boldsymbol{x}_{1}$, $\boldsymbol{x}_{2}$ on $\partial\widehat{T}(m)$ with $\boldsymbol{x}_{2}=\theta_{k}(\boldsymbol{x}_{1})$, but $\mathcal{L}(\boldsymbol{a}_{2})\neq\mathcal{L}(\boldsymbol{a}_{1})+1\pmod{k}$. 2. Three binary vectors $\boldsymbol{a}_{1},\boldsymbol{a}_{2},\boldsymbol{a}_{3}\in\{0,1\}^{b}$ such that the simplex $\sigma=\mathsf{conv}(\{\boldsymbol{a}_{1},\boldsymbol{a}_{2},\boldsymbol{a}_{3}\})$ belongs to $\widehat{T}(m)$ and all the labels $\mathcal{L}(\boldsymbol{a}_{1})$, $\mathcal{L}(\boldsymbol{a}_{2})$, $\mathcal{L}(\boldsymbol{a}_{3})$ are different from each other. 3. Two binary vectors $\boldsymbol{a}_{1},\boldsymbol{a}_{2}\in\{0,1\}^{b}$ such that the edge $\psi=\mathsf{conv}(\{\boldsymbol{a}_{1},\boldsymbol{a}_{2}\})$ belongs to $\widehat{T}(m)$ and labels $\mathcal{L}(\boldsymbol{a}_{1})$, $\mathcal{L}(\boldsymbol{a}_{2})$ are different and they satisfy $\mathcal{L}(\boldsymbol{a}_{1})-\mathcal{L}(\boldsymbol{a}_{2})\neq\pm 1\pmod{k}$.

It holds that $k$-polygon-Tucker is in \textup{PPA-k}[\#1].

This lemma follows from the proof of $k$-Polygon Tucker’s Lemma that we presented in Section 3.1.2. We only need to add the description of the circuits $\mathcal{S}$, $\mathcal{P}$ that define the graph $G$ constructed in the proof. Then, using these circuits we reduce $k$-polygon-Tucker to Imbalance-mod-$k[\#1]$. As we showed in Lemma 3.8, every solution to the resulting instance of Imbalance-mod-$k[\#1]$ corresponds to a solution of $k$-polygon-Tucker. Hence, $k$-polygon-Tucker is in \textup{PPA-k}[\#1].