The Hairy Ball Problem is PPAD-Complete

Introduction

The Hairy Ball Theorem (HBT) is a well-known topological theorem stating that there is no non-vanishing continuous tangent vector field on an even-dimensional $k$-sphere. It has various informal statements such as “you can’t comb a hairy ball flat without creating a cowlick”https://en.wikipedia.org/wiki/Hairy_ball_theorem, or “there is a point on the surface of the earth with zero horizontal wind velocity”. The HBT is superficially reminiscent of the Borsuk-Ulam Theorem, stating that given any continuous mapping from the 2-sphere to the plane, there are two antipodal points that map to the same value. (Informally, “there are two antipodal points on the surface of the earth where the temperature and pressure are the same”). As we shall see, the present paper highlights a fundamental difference between the two, in terms of the complexity class naturally associated with each of them.

The HBT was first proved in 1885 by Poincaré for the case $k=2$. The theorem as stated for all even $k$ was proved in 1912 by Brouwer . Accordingly, this result is sometimes also called the Poincaré-Brouwer theorem. In fact, the result proved by Poincaré is stronger than stated above. It follows from it that for any (sufficiently well-behaved) 2-dimensional manifold with genus $g\neq 1$, any continuous tangent vector field must have a zero. In particular, this means that the HBT also holds for the torus of genus $g$ for $g\geq 2$, i.e. the 2-dimensional torus with $g$ holes. It is easy to see that it does not hold for the standard single-hole torus.

Over the years, various papers in the American Mathematical Monthly have presented alternative proofs of the Hairy Ball Theorem and variants, for example .

Topological existence results (such as the HBT, Borsuk-Ulam, and the Brouwer and Banach fixpoint theorems) have a very interesting relationship with complexity classes of search problems in which any instance has a guaranteed solution. Any such theorem has a corresponding computational challenge, of searching for such a solution, given a circuit that computes an appropriate function. The assumption that these complexity classes are distinct from each other (the ones of main interest here being PPAD and PPA, discussed below in more detail) provides a taxonomy of these theorems. Our results highlight a fundamental distinction between the HBT and Borsuk-Ulam, by showing that the corresponding search problem for the HBT is characterised by the complexity class PPAD, in contrast to Borsuk-Ulam, which is characterised by PPA . The complexity-theoretic analysis of topological search problems provides a well-defined sense in which the HBT is “Brouwer-like” rather than “Borsuk-Ulam-like”. It has previously been noted that the HBT may be used to prove Brouwer’s fixed point theorem , but not the other way around. Indeed, the existing proof of HBT using Sperner’s Lemma actually uses a generalisation of Sperner’s Lemma, which was not known to be equivalent to Brouwer’s fixed point theorem prior to our work.

The complexity class TFNP is the set of all total function computation problems in NP: functions where every input has an efficiently-checkable solution (in Section 2.2 we give a precise definition). Many problems in TFNP appear to be computationally difficult, notably Factoring, the problem of computing a prime factorisation of a given number, also Nash, the problem of computing a Nash equilibrium of a game. However, such problems are unlikely to be NP-hard, due to the 1991 result of Megiddo and Papadimitriou showing that TFNP problems cannot be NP-hard unless NP is equal to co-NP. This basic fact, that hard TFNP problems are in a very strong sense “NP-intermediate”, provides TFNP’s strong theoretical appeal. This has led to the classification of these problems in terms of certain syntactic subclasses of TFNP, whose problems are shown to be total due to some basic combinatorial principle. The best-known of these classes are PLS, PPP, PPAD, and PPA, identified by Papadimitriou in 1994 .

PPAD consists of problems whose totality is based on the principle that given a source in a directed graph whose vertices have in-degree and out-degree at most 1, there exists another degree-1 vertex. Its canonical problem End-of-Line consists of an exponentially-large graph of this kind, presented concisely via a circuit.

PPA differs from PPAD in that the graph need not be directed; being a more general principle, PPA is thus a superset of PPAD. Its canonical problem Leaf is similar, only the graph is undirected.

Subsequently, many TFNP problems of interest were shown PPAD-complete , while more recently others were shown PPA-complete . Despite their similar definitions, PPAD and PPA are usually conjectured to be different, and (along with other syntactic TFNP subclasses) are separated by oracles .

2 Our results and their significance

Given the long-standing interest in the Hairy Ball Theorem, it is natural to study the corresponding computational search problem. In this paper, we prove that computing an approximate zero of a Hairy Ball vector field is PPAD-complete. While many PPAD-completeness results already exist, a noteworthy novelty of our results is that we find that computing HBT solutions corresponds with multiple-source variants of the End-of-Line problem: given a large directed graph implicitly represented by a circuit, suppose you are shown several sources and told to find another degree-1 vertex. This is in contrast with previous PPAD-complete problems that naturally reduce to standard single-source End-of-Line.

In Section 8 we prove that these multiple-source End-of-Line variants are PPAD-complete (membership of PPAD being the tricky aspect). Our results make progress on the general question (studied in ) of whether there exist combinatorial principles indicating totality of search problems, that are fundamentally different from the known ones that give rise to complexity classes such as PPAD. In particular, in Section 8.2, we note that a proof of PPAD-completeness for the Imbalance problem by Beame et al. is incomplete and provide a full proof using our results.

The generalisation of Poincaré’s result to higher dimensions is called the Poincaré-Hopf theorem (see e.g. ). This theorem relates the number and types of zeros of a vector field on a manifold with its Euler characteristic, a topological invariant. In particular, if the Euler characteristic of a manifold is not , then any continuous tangent vector field on the surface must have a zero. The Euler characteristic of even-dimensional spheres is $2$, while it is $2(1-g)$ for 2-dimensional toruses of genus $g\geq 2$. For odd-dimensional spheres it is .

We believe that the reduction to multiple-source End-of-Line is not an artefact of our techniques, but instead intrinsically related to the Euler characteristic of the domain. Indeed, the reduction from the HBT problem on even-dimensional spheres to End-of-Line yields $2$ sources (Section 4). On the other hand, if we consider the HBT problem on the 2-dimensional torus of genus $g\geq 2$, then we obtain $2(g-1)$ sources (Section 7). The connection between HBT and directed graph problems has previously only appeared in a proof for the 2-dimensional sphere case .

Finally, we note that PPAD-hardness is obtained by constructing a HBT vector field from multiple copies of a discrete Brouwer fixpoint problem. The usage of multiple copies is a new conceptual feature, closely related to the multi-source aspect. Using the same high-level idea, we also provide a FIXP-hardness result for the problem of computing an exact solution (Section 5.2).

3 Other related work

Banach’s Fixed Point Theorem says that a contraction map has a unique fixpoint. Its corresponding computational problem Contraction, is to find a fixed point of a given contraction map. Some versions of Contraction have been shown complete for CLS, a subclassA very recent result shows that, in fact, CLS = PPAD $\cap$ PLS. of PPAD . The search for Brouwer fixpoints (including discretised versions of Brouwer functions) is PPAD-complete for most variants of the problem , which is why we say the HBT is “Brouwer-like”. Finally — in contrast — the computational problem of searching for a Borsuk-Ulam solution is PPA-complete . Other topological existence results that have PPA-complete search problems include the Hobby-Rice theorem and the Ham Sandwich Theorem .

4 Future research directions

We have obtained a satisfying answer to the question of the computational complexity of the Hairy Ball Theorem, if we are looking for an approximate solution. For other solution concepts related to exact solutions, we have provided a FIXP-hardness result. This leaves open the question of whether the problem is FIXP-complete in this case. A first step in that direction would be to try to reduce Hairy Ball to Borsuk-Ulam, even though no such (fully constructive) mathematical proof seems to be known.

Our reduction from approximate Hairy Ball to approximate Brouwer cannot be used on the exact versions of these problems, because the step where we reduce from multi-source End-of-Line to standard End-of-Line corresponds to a discontinuous mapping between the corresponding topological structures. This raises the question of whether continuous mappings are an important subclass of reductions and motivates further study on this topic.

Our results on multiple-source variants of the End-of-Line problem open the way for two new research directions. First, they provide a new tool for showing membership of PPAD, which can be used to put further problems in this class. It seems very unlikely that the Hairy Ball Theorem should be the only “natural” application of these results. Furthermore, a second interesting research direction is investigating the complexity of End-of-Line with a super-polynomial number of known sources (implicitly given in the input).

Preliminaries

We work in the standard Turing machine model. All numbers appearing in computations are rational numbers where the numerator and denominator are integers represented in binary. For a rational number $x$, $\text{size}(x)$ denotes the size of the representation of $x$, i.e. the sum of the representation length of its numerator and denominator in binary. For an arithmetic circuit $F$, $\text{size}(F)$ denotes the number of gates in the circuit added to the representation length of any rational constants used by the circuit.

2 Formal definition of TFNP

A computational search problem is given by a binary relation $R\subseteq\{0,1\}^{*}\times\{0,1\}^{*}$, interpreted as follows: $y\in\{0,1\}^{*}$ is a solution to instance $x\in\{0,1\}^{*}$, if and only if $(x,y)\in R$. 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|)$. Here $\{0,1\}^{*}$ denotes all finite length bit-strings and $|x|$ is the length of bit-string $x$.

The class TFNP (Total Functions in NP ) contains all search problems $R$ that are in FNP and are total, i.e. every instance has at least one solution. Formally, this corresponds to requiring that for every $x\in\{0,1\}^{*}$ there exists $y\in\{0,1\}^{*}$ such that $(x,y)\in R$.

Let $R$ and $S$ be total search problems in TFNP. We say that $R$ (many-one) reduces to $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$ reduces to $S$ and $S$ reduces to $R$.

3 The End-of-Line problem

To be PPAD-complete, a problem must be equivalent to End-of-Line. The End-of-Line problem is informally defined as follows: given a directed graph where each vertex has in- and out-degree at most $1$ and given a known source of this graph, find a sink or another source. The problem is computationally challenging, because the graph is not given explicitly in the input. Instead, we are given an implicit concise representation of the graph through circuits that compute the predecessor and successor of a vertex in the graph. In what follows, we sometimes interpret the input and output of the circuits, which are elements in $\{0,1\}^{n}$, as the numbers $\{0,1,\dots,2^{n}-1\}$.

The End-of-Line problem is defined as: given Boolean circuits $S,P$ with $n$ input bits and $n$ output bits and such that $P(0)=0\neq S(0)$, find $x$ such that $P(S(x))\neq x$ or $S(P(x))\neq x\neq 0$.

The circuits define a graph as follows. There is a directed edge from vertex $x$ to $y$ ($x\neq y$), if and only if $S(x)=y$ and $P(y)=x$. Note that any badly defined edge, i.e. $S(x)=y$ and $P(y)\neq x$, or $P(y)=x$ and $S(x)\neq y$, qualifies as a solution of End-of-Line as defined above (because $P(S(x))\neq x$ or $S(P(x))\neq x$ respectively). Note that is a source of the graph, unless $P(S(0))\neq 0$, in which case is a valid solution to the problem as stated above.

It is easy to check that this formal definition of the problem is computationally equivalent to the informal description given above. By definition, End-of-Line is PPAD-complete . Furthermore, reduction from End-of-Line is a very common technique to show PPAD-hardness (e.g. ). In Section 8 we show that the multiple-source version MS-EoL (Definition 9) is equivalent to End-of-Line.

The Hairy-Ball Problem

The Hairy Ball Theorem naturally yields a corresponding computational problem. We are given a continuous tangent vector field $f$ on the unit sphere and have to find a point where it is zero. In trying to formalise this, some issues need to be addressed. First, one has to decide how the vector field should be represented in the input. Here we take the usual approach of assuming that it is represented as an arithmetic circuit.

Before we discuss the types of gates that we want to allow in the circuit, let us briefly handle the second issue: the vector field might not have a rational zero. Indeed, consider the following example: at $x\in S^{2}$ the vector field is simply the vector $(1,1,1)$ projected onto the tangent space of $S^{2}$ at $x$. In this case, the only solutions are $\pm(1/\sqrt{3},1/\sqrt{3},1/\sqrt{3})$. Thus, we cannot hope to always output an exact solution. We bypass this problem by asking for an approximate solution instead, i.e. a point $x\in S^{2}$ such that $\|f(x)\|_{\infty}\leq\varepsilon$ for some $\varepsilon>0$ provided in the input. This notion of approximate solution is the standard one used when studying topological existence theorems in the context of TFNP (e.g. Brouwer’s fixed point theorem or the Borsuk-Ulam theorem).

As mentioned above, the vector field will be represented as an arithmetic circuit. In the case of $S^{2}$, the circuit will have three input gates and three output gates. The arithmetic circuit will be allowed to use gates $\{+,-,\times\zeta,\max,\min\}$ and rational constants. All the gates have fan-in 2, except $\times\zeta$ which has fan-in 1 and corresponds to multiplication by a rational constant $\zeta$. Note that such a circuit is polynomially equivalent to a circuit only using gates $\{+,\times\zeta,\max\}$ and rational constants, since the other gates can be efficiently simulated using these. These circuits correspond to LINEAR-FIXP-type circuits that are known to be sufficient to obtain PPAD-hardness of Brouwer . A discussion about why we don’t use more powerful gates in our definition can be found in the next section.

This type of circuit yields piece-wise affine functions that are continuous. Furthermore, it has the following nice property: for any such arithmetic circuit $F$, and any rational $x$, we can compute $F(x)$ exactly in polynomial time in $\text{size}(F)$ and $\text{size}(x)$. One potential issue is that $F$ might not be tangent to the sphere, but this is easy to fix by simply considering the vector field given by the projection of $F$ onto the corresponding tangent space to the sphere. Thus, we define the computational problem as follows:

Let $k\geq 2$ be even. The $k$D-Hairy-Ball problem is defined as: given $\varepsilon>0$ and an arithmetic circuit $F$ with $k+1$ inputs and outputs, using gates $\{+,\times\zeta,\max\}$ and rational constants, find $x\in S^{k}$ such that $\left\|P_{x}[F(x)]\right\|_{\infty}\leq\varepsilon$.

$k$D-Hairy-Ball lies in TFNP. Clearly, any solution can be checked in polynomial time. Totality of $k$D-Hairy-Ball will immediately follow when we prove that it lies in PPAD (Corollary 5).

It is easy to see that if functions $f_{1}$ and $f_{2}$ are $L_{1}$- and $L_{2}$-Lipschitz respectively, then $f_{1}+f_{2}$ is $(L_{1}+L_{2})$-Lipschitz and $\max\{f_{1},f_{2}\}$ is $\max\{L_{1},L_{2}\}$-Lipschitz. Since any rational constant used in $F$ has absolute value bounded by $2^{\text{size}(F)}$, it follows that $f_{1}\times\zeta$ is $L_{1}2^{\text{size}(F)}$-Lipschitz. Using the fact that each input gate corresponds to a $1$-Lipschitz function, it follows that $F$ must be $2^{\text{size}(F)^{2}}$-Lipschitz.

Using the same kind of argument it is easy to show that for $x\in S^{k}$ we always have $\|F(x)\|_{\infty}\leq 2^{\text{size}(F)^{2}}$. Using the fact that $f_{1}\times f_{2}$ is $(\|f_{1}\|_{\infty}L_{2}+L_{1}\|f_{2}\|_{\infty})$-Lipschitz and the definition $P_{x}[v]=v-\langle v,x\rangle x$, we obtain that $x\mapsto P_{x}[F(x)]$ is Lipschitz-continuous on $S^{k}$ with constant $L\leq(3k+4)2^{\text{size}(F)^{2}}\leq k\cdot 2^{\text{size}(F)^{2}+3}$. ∎

Our main result is Theorem 3. Containment in PPAD, which turns out to be the most challenging part of this result, is presented in Section 4 (using the multiple-source End-of-Line results of Section 8). PPAD-hardness is presented in Section 5.

For all even $k\geq 2$, $k$D-Hairy-Ball is PPAD-complete.

2 About the power of the arithmetic circuit

The main disadvantage of defining $k$D-Hairy-Ball as in Definition 2 is that the type of circuit used seems quite restrictive. Clearly, it would be natural to also allow $\times$-gates that compute the product of two intermediate outputs (as opposed to just multiplication by a fixed constant). Unfortunately, allowing the $\times$-gate leads to technical complications in the definition of the problem because of repeated squaring (see below). These technicalities would make Definition 2 more cumbersome and less intuitive overall. In the interest of simplicity and clarity of exposition we have thus decided to use the simpler definition that only allows $\{+,\times\zeta,\max\}$ gates.

From the standpoint of computational complexity, this restriction turns out to be irrelevant. Indeed, in Section 4 we prove that a very abstract formulation of the Hairy-Ball problem lies in PPAD. Namely, we only require that the tangent vector field be polynomially computable and polynomially continuous (Definition 3). These two assumptions are very natural and desirable in any TFNP-style definition of the problem. In particular, properly defining the problem with the additional $\times$-gates would also yield a problem that lies in PPAD. Furthermore, in Section 5 we prove that $k$D-Hairy-Ball is PPAD-hard. It immediately follows that formulations with more powerful circuits are also PPAD-hard. Thus, it turns out that allowing $\times$-gates yields a problem that is polynomially equivalent to this more restricted version that we use.

Before we close this section, we give some details about the complication that arises when allowing the $\times$-gates and how this can be circumvented in order to define a TFNP-problem. The main issue is that if the circuit is allowed to use $\times$-gates, then we might not be able to evaluate the function it represents efficiently. For example, consider the arithmetic circuit that does repeated squaring, i.e. it has a sequence of $n$ $\times$-gates that multiply the output of the previous gate by itself. On input $2$, this circuit outputs $2^{2^{n}}$, which is doubly exponential in the size of the circuit and input to the circuit. Even putting aside the fact that we cannot efficiently represent this number in our model, this also causes the Lipschitz-constant to be doubly exponential. In order to solve this we can enforce an upper bound $M$ on all computations of the circuit. This means that every gate would have an output in $[-M,M]$. $M$ would have representation size polynomial in the size of the circuit. Without loss of generality we can take $M=1$. However, we still might not be able to compute the output of the (bounded) circuit exactly. Indeed, the same circuit as earlier, on input $1/2$, would output $2^{-2^{n}}$. We would need an exponential (w.r.t. the number of bits of the input and the size of the circuit) number of bits to represent this.

One nice property of this kind of circuit is that the condition that $F$ be tangential to $S^{k}$ can be enforced syntactically. Indeed, we can extend the circuit to output $F(x)-\langle F(x),x\rangle x$, instead of $F(x)$. Some care is required here, because the computations of the circuit are bounded in $$, but this can be solved by multiplying$F(x)$by$1/k$before projecting and using$\varepsilon/k$instead of$\varepsilon$. Thus, we could always assume that the circuit given in the input describes a tangential vector field on the sphere.

As mentioned above, we do not use this kind of circuit because it introduces unnecessary complications and clutter.Another more elegant option would be to consider well-behaved circuits, as defined in . However, a closer inspection of the proof of Theorem 4 yields that this problem also lies in PPAD and thus turns out to be equivalent to $k$D-Hairy-Ball.

The Hairy-Ball Problem is in PPAD

In this section we present our main result: the problem of computing an approximate Hairy Ball solution reduces to End-of-Line, the canonical PPAD-complete problem.

From a purely mathematical standpoint, our proof can be used to provide a (fairly cumbersome) proof of the Hairy Ball theorem by using Brouwer’s fixed point theorem. Indeed, it is known that End-of-Line reduces to Brouwer (in fact, even 2D-Brouwer ). Thus, given a Hairy Ball function $f$, using our reduction and Brouwer’s fixed point theorem, one can prove the existence of a point $x_{k}$ such that $\|f(x_{k})\|\leq 1/2^{k}$ for any $k$ (using the fact that $f$ must be uniformly continuous since the sphere is compact). Then, since any sequence in a compact set must have a converging subsequence it follows that there must exist $x$ such that $f(x)=0$. Finding a more direct way to deduce the Hairy Ball theorem from Brouwer’s fixed point theorem is an interesting open question.

Our goal is to prove that the Hairy Ball problem lies in PPAD in a setting that is as general and encompassing as possible. The way the function is represented, as a circuit or otherwise, should not play a role. Thus, we are only going to make two assumptions about the tangent vector field: that it can be evaluated in polynomial time and that it is polynomially continuous in some well-defined sense. The first assumption is very natural: if we are given a Hairy Ball function, we expect to be able to evaluate it efficiently. The motivation for the second assumption is that if we omit it, then there is no guarantee that there will exist an approximate solution with representation size that is polynomial in the input size.

Let $\mathcal{F}$ be a class of Hairy Ball functions.

$\mathcal{F}$ is polynomially computable, if there exists some polynomial $p$ such that for any $f\in\mathcal{F}$ and any rational input $x\in S^{k}$, $f(x)$ can be computed in time $p(\text{size}(f)+\text{size}(x))$.

$\mathcal{F}$ is polynomially continuous, if there exists some polynomial $q$ such that for any $f\in\mathcal{F}$ and any rational $\varepsilon>0$, there exists a rational $\delta>0$ with $\text{size}(\delta)\leq q(\text{size}(f)+\text{size}(\varepsilon))$ such that for all $x,y\in S^{k}$ we have $\|x-y\|_{\infty}\leq\delta\implies\|f(x)-f(y)\|_{\infty}\leq\varepsilon$.

Note that $k$D-Hairy-Ball yields a class $\mathcal{F}$ that is both polynomially computable and polynomially continuous (by Lemma 2).

Let $\mathcal{F}$ be a class of Hairy Ball functions. The problem Hairy-Ball($\mathcal{F}$) is defined as: given $f\in\mathcal{F}$ and $\varepsilon>0$, find $x\in S^{k}$ such that $\|f(x)\|_{\infty}\leq\varepsilon$.

For simplicity we assume that we can recognise whether some string in $\{0,1\}^{*}$ represents an element $f\in\mathcal{F}$ in polynomial time. If this does not hold, then Hairy-Ball($\mathcal{F}$) has to be studied as a promise problem. The reduction to End-of-Line given in the proof below still holds. However, this does not imply that the problem lies in PPAD, because TFNP requires the problem to be total without any promise.

2 The general problem lies in PPAD

Let $\mathcal{F}$ be a class of Hairy Ball functions that is polynomially computable and polynomially continuous. Then, Hairy-Ball($\mathcal{F}$) lies in PPAD.

For all even $k\geq 2$, $k$D-Hairy-Ball lies in PPAD.

The proof can be subdivided into two parts. In the first part, we reduce $k$D-Hairy-Ball to a 2-source End-of-Line problem. In the second part, we show that the 2-source version reduces to the standard version of End-of-Line, where a single source is known. Surprisingly, the reduction from 2 sources to 1 is non-trivial. The proof for this is presented separately in Section 8. In fact, we prove the more general result: as long as the number of known sources in an End-of-Line instance is polynomial, we can reduce to standard End-of-Line. Various implications of this result are also presented in Section 8.

We now give some details about the first part of the proof, in which we reduce $k$D-Hairy-Ball to 2-source End-of-Line through a Sperner argument. The inspiration for this comes from a proof of the 2-dimensional Hairy Ball Theorem via a generalisation of Sperner’s Lemma, given by Jarvis and Tanton . Our contribution here is two-fold: we extend their proof to any higher (even) dimension and we turn it into a polynomial-time reduction. Even though Sperner’s Lemma is known to be PPAD-complete , this result does not apply to the general version of Sperner’s Lemma that is used here. Indeed, by using standard techniques, this general version can only be reduced to a 2-source instance of End-of-Line. This is why we then require our technical results about multiple-source End-of-Line from Section 8.

where $[\cdot]_{j}$ indicates the $j$th coordinate for $j\in\{0,1,\dots,k\}$. It is straightforward to check that $b_{1},\dots,b_{k}$ are continuous tangent vector fields that yield an orthonormal basis of the tangent space of $S^{k}$ at every $x\in S^{k}\setminus\{p\}$.

Continuity of $\boldsymbol{g}$. Clearly, $g$ is continuous. Moreover, since $\mathcal{F}$ is polynomially continuous, we can extend this to $g$ in the following sense.

First, let us prove a bound on $\|f(x)\|_{\infty}$ for all $x\in S^{k}$. Let $\bar{\delta}>0$ be such that $\|f(x)-f(y)\|_{\infty}\leq 1$ if $\|x-y\|_{\infty}\leq\bar{\delta}$. Recall that $\text{size}(\bar{\delta})$ is polynomially bounded in $\text{size}(f)$. Since $f$ is continuous on the sphere $S^{k}$, there exists some $x^{*}\in S^{k}$ such that $f(x^{*})=0$. The arc distance between $x$ and $x^{*}$ is at most $\pi$ and we pick points $y^{(0)},y^{(1)},\dots,y^{(m)}\in S^{k}$ along the arc such that $y^{(0)}=x,y^{(m)}=x^{*}$ and $\|y^{(i)}-y^{(i+1)}\|_{\infty}\leq\|y^{(i)}-y^{(i+1)}\|_{2}\leq\bar{\delta}$. We can take $m\leq\lceil\pi/\bar{\delta}\rceil\leq 4/\bar{\delta}$ (assuming $\bar{\delta}\leq 1/2$). Then, we have

Note that for all $i$, $z\mapsto b_{i}(x(z))$ is Lipschitz-continuous with a Lipschitz constant of the form $m\sqrt{k}$ for some constant $m$ ($m=20$ is enough). This can be checked by direct computation. Recalling that $x(z)$ is short for $SP^{-1}(z)$, the fact that $SP^{-1}$ is $4\sqrt{k}$-Lipschitz and $f$ is polynomially continuous, the claim then follows. ∎

Pick $\delta>0$ so that $\|z-z^{\prime}\|_{\infty}\leq\delta$ implies

By 1, it is possible to pick such $\delta$ with $\text{size}(\delta)\leq\text{poly}(\text{size}(f),\text{size}(\varepsilon))$.

Let the $\delta$-fine $k$-simplex $z^{(0)},\dots,z^{(k)}$ be panchromatic. Since $[g(z^{(0)})]_{j}\geq 0$ for all $j$, there exists $i$ such that $[g(z^{(0)})]_{i}=\|g(z^{(0)})\|_{\infty}$. However, it must hold that $[g(z^{(i)})]_{i}<0$ and thus $\|g(z^{(0)})\|_{\infty}\leq|[g(z^{(0)})]_{i}-[g(z^{(i)})]_{i}|$. Since $\|z^{(0)}-z^{(i)}\|_{\infty}\leq\delta$, it follows by (2) that $\|g(z^{(0)})\|_{\infty}\leq\varepsilon/8\sqrt{k}\leq\varepsilon/\sqrt{k}$, i.e. $z^{(0)}$ yields a solution. ∎

Intuitively, we want to pick a $\delta$-fine triangulation of the ball and construct a directed graph on the triangles. There is a directed edge between two triangles if they share a facet coloured $1,2$ and the edge is directed such that it crosses the facet with the colour $1$ on its left-hand side and the colour $2$ is on its right-hand side. Then, because of the structure of the colouring on the boundary, we obtain two known sources and any sink or other source of this directed graph corresponds to a panchromatic simplex, i.e. a solution.

This intuition is formalised in the following lemma, which is proved below.

By Theorem 14 in Section 8 it then follows that the problem lies in PPAD, which concludes the proof of Theorem 4. ∎

In order to investigate the colouring, we first prove some properties of an ideal colouring that we define below and then show that the actual colouring is “close” enough to the ideal colouring and also satisfies these properties.

The following properties of $w$ are easy to check by direct computation.

If $w(z)\leq 0$, then $z\geq 0$ or $z\leq 0$.

The ideal colouring is “close” to the actual colouring. We now show that if $\|z\|_{2}$ is sufficiently large, then the ideal colouring is very close to the actual colouring. Namely, we will show that $w(z)$ is almost equal to $\widehat{g}(z)$, a “normalisation” of $g$ defined by $\widehat{g}(z)=c(z)\cdot g(z)$, where $c(z)=\frac{1+\|z\|_{2}^{2}}{v\|z\|_{2}^{2}}$. Note that $\widehat{g}$ and $g$ yield the exact same colour for any $z\neq 0$.

Since $f$ is polynomially continuous, there exists $\widehat{\delta}$ such that $\|f(x)-f(p)\|_{\infty}\leq\varepsilon/16\sqrt{k(k+1)}$ with $\textup{size}(\widehat{\delta})=\textup{poly}(\textup{size}(f),\textup{size}(\varepsilon))$. Using the definition of $SP^{-1}$ it is easy to check that $\|x(z)-p\|_{2}\leq 2/\sqrt{1+\|z\|_{2}^{2}}$. Thus, we can construct $t\geq 4$ with $\textup{size}(t)=\textup{poly}(\textup{size}(f),\textup{size}(\varepsilon))$ such that $\|f(x(z))-f(p)\|_{\infty}\leq\varepsilon/16\sqrt{k(k+1)}$ for all $z$ with $\|z\|_{2}\geq t$.

Let $\bar{g}(z)$ denote the colour-direction obtained at $z$ if we use $f(p)$, instead of $f(x(z))$, i.e. $\bar{g}_{i}(z)=\langle f(p),b_{i}(x(z))\rangle$. Then, for all $z$ with $\|z\|_{2}\geq t$, we have

Recalling that $f(p)=(0,v,v,\dots,v)/\sqrt{k}$ and using equation (1) and the definition of $SP^{-1}$, we can write for all $i$

We obtain that for any $z$ with $\|z\|_{2}\geq t$

where we used (3), $v>\varepsilon$ and $t\geq 4$. ∎

The unit cross-polytope can be triangulated efficiently by using a standard efficient triangulation of the $k$-simplex $0,e^{(1)},\dots,e^{(k)}$ (see e.g. ) and then extending it to the rest of the cross-polytope by mirroring along each axis. Thus, using a $\delta/m$-fine efficient triangulation of the simplex, extending it to the cross-polytope and then scaling to $C_{m}$, yields an efficient $\delta$-fine triangulation of $C_{m}$. We call this triangulation $T$. In particular, given a simplex of $T$ and one of its facets, we can compute the other simplex of $T$ that shares this facet in polynomial time (or decide that it does not exist, if the facet lies on the boundary of $C_{m}$). Note that $\text{size}(\delta/m)$ is polynomial in the size of the input.

The restriction of the triangulation $T$ to $\partial C_{m}\setminus(\partial C_{m}^{+}\cup\partial C_{m}^{-})$ does not contain any $(k-1)$-simplex coloured $1,2,\dots,k$ (in the actual colouring).

Let $y^{(1)},\dots,y^{(k)}$ be a $\delta$-fine $(k-1)$-simplex on $\partial C_{m}$ such that $y^{(i)}$ has colour $i$. By 3 (Item 3) it suffices to show that $w(y^{(i)})\leq 0$ for all $i$. Note that since $\|y^{(i)}-y^{(j)}\|_{\infty}\leq\delta$, it follows by (2)

since $v>\varepsilon$ and $\|z\|_{2}\geq t\geq 1$.

Orientation of $\boldsymbol{\partial C_{m}^{+}}$ and $\boldsymbol{\partial C_{m}^{-}}$. The following simple observation is crucial.

The $(k-1)$-simplices $\partial C_{m}^{+}$ and $\partial C_{m}^{-}$ have the same orientation with respect to the Sperner boundary conditions.

This is the only point in the proof where we use the fact that $k$ is even. However, it is indeed crucial, since this ensures that the two ends of line that we know are both sources (or both sinks), as we will see below. If $k$ is odd, our reduction yields an instance with a known source and sink. In this case, there is no guarantee that a solution – another end of line – even exists.

2-source End-of-Line. We now explain how the problem of finding a panchromatic $k$-simplex in the triangulation $T$ of $C_{m}$ reduces to a 2-source End-of-Line problem. Let us briefly recall how a standard $k$-dimensional Sperner instance reduces to End-of-Line. A fully detailed and formal presentation of this is given in [15, Proposition 2.2]. In the standard $k$-dimensional Sperner problem, we have a big $k$-simplex triangulated into $k$-simplices and a colouring that satisfies the Sperner boundary conditions. The End-of-Line graph is constructed as follows. Every $k$-simplex of the triangulation is a node in the graph. There is an edge between two nodes if the corresponding $k$-simplices have a common facet coloured $1,\dots,k$ (called a door-facet). The edge is directed by considering the orientation of the $k$-simplices with respect to the common facet. This yields an End-of-Line graph where every degree-1 node is either a panchromatic $k$-simplex or a $k$-simplex that has a door-facet lying on the boundary of the instance, i.e. on the boundary of the big $k$-simplex. Note that all the door-facets lying on the boundary of the instance lie on the $1,\dots,k$-facet of the big $k$-simplex. In order to obtain a single source, there are various standard tricks, see e.g. [33, Chapter 4]. If we use the so-called “artificial start” trick, then as shown in , we obtain a slightly larger Sperner instance that has a single door-facet “exposed” to the outside, i.e. lying on the boundary of the instance.

We can use these standard techniques on our problem. The boundary of our instance is $\partial C_{m}$. By 6, all door-facets on the boundary are contained in $\partial C_{m}^{+}$ or $\partial C_{m}^{-}$. By applying the trick mentioned above on $\partial C_{m}^{+}$ (interpreted as a facet of a $k$-dimensional Sperner instance) we obtain a single door-facet that is “exposed” in this whole region. Applying the exact same trick on $\partial C_{m}^{-}$ also yields a single door-facet that is “exposed” in this whole region. Thus, overall we only have two door-facets that lie on the boundary of our instance. Fig. 2 shows how the “artificial start” trick is used on a 2-dimensional example.

Finally, the important observation here is that the orientation of the “exposed” door-facet obtained by using the trick only depends on the orientation of the big facet on which it is used. Since $\partial C_{m}^{+}$ and $\partial C_{m}^{-}$ have the same orientation (7), the two “exposed” door-facets have the same orientation. This means that we have two “entrances” for the standard Sperner path-following algorithm. By applying the formal arguments in the reduction from Sperner to End-of-Line this yields a two-source End-of-Line instance. ∎

Computational Hardness for Hairy Ball Problems

By making this idea fully constructive and efficient, we obtain reductions from Brouwer problems to Hairy Ball problems. Thus, existing PPAD- and FIXP-hardness results for Brouwer also hold for the corresponding Hairy Ball problems. We note that these reductions always involve using two copies of a Brouwer instance to obtain a single Hairy Ball instance. This further supports our claim that the fact that we obtain two sources when reducing $k$D-Hairy-Ball to End-of-Line (Section 4) is not an artefact of our reduction, but intrinsic to the problem.

For all even $k\geq 2$, $k$D-Hairy-Ball is PPAD-hard.

Note that this result is particularly strong, because the type of circuit allowed in the definition of $k$D-Hairy-Ball (Definition 2) is particularly weak. Furthermore, the hardness is proved for inversely exponential $\varepsilon/L$ (where $L$ is the Lipschitz constant of the function), which is the best we can hope for in the fixed dimension case. Indeed, if $\varepsilon/L$ is inversely polynomial, then the following is a polynomial time algorithm that solves the problem: divide the domain into a sufficiently small (but polynomial) number of regions and check an arbitrary point in each region.

Our reduction essentially shows that some hardness results known for the Brouwer problem also hold for the Hairy Ball problem. One direction that we do not explore here is the hardness of approximation when the dimension is not fixed. It seems quite likely that the problem should be hard even for constant $\varepsilon/L$ in that case, since this is known to hold for the Brouwer problem .

One way to prove this result is to take an instance $F$ of a 2D-Brouwer problem, which is known to be PPAD-complete , and embed a copy $F$ and a copy $-F$ on the south and north hemisphere of $S^{2}$ respectively. However, since our $2$D-Hairy-Ball circuit can only use gates in $\{+,\times\zeta,\max\}$, we first shrink the domain of $F$ so that we embed it in a small region around the south pole. This ensures that even after projection onto the tangent space, no bogus solutions will appear. We do the same for $-F$ in the north pole and then define $G$ on the rest of the sphere in such a way that no solution appears there.

In spirit, we follow this general proof idea, but take a slight detour, because it gives us the chance to define and study a discrete analog to $2$D-Hairy-Ball: the $2$D-Hairy-Cube problem. Intuitively, this problem is obtained from $2$D-Hairy-Ball the same way that discrete 2D-Brouwer is obtained from continuous 2D-Brouwer. The domain is discretised by a grid and a circuit computes the local direction of the function in every grid-square. The natural way to discretise the sphere $S^{2}$ is to replace it by a cube with a grid on each face. The advantage of $2$D-Hairy-Cube is that PPAD-hardness is easy to prove: just put a (slightly modified) discrete 2D-Brouwer instance on one face, and the inverse instance on the opposite face. Defining the instance on the remaining faces is trivial in this case. Section 6 defines the problem and proves PPAD-hardness.

The next step is reducing $2$D-Hairy-Cube to $2$D-Hairy-Ball. Even though it seems natural that this should hold, the reduction is technically tedious. In particular, we have to simulate a Boolean circuit using an arithmetic circuit, but the input bits cannot always be computed exactly. Thus, we need to use an averaging trick (see ). The details are in Appendix A.

This yields PPAD-hardness for $2$D-Hairy-Ball. The final step is to extend this to $k$D-Hairy-Ball, by showing that $k$D-Hairy-Ball reduces to $(k+2)$D-Hairy-Ball. The proof can be found in Appendix B. ∎

2 FIXP-hardness

Up to this point we have only considered the problem of computing an approximate Hairy Ball solution. However, there are other computational problems one could consider, e.g. computing a point that is close to an exact solution, or computing the first $n$ bits of an exact solution.

The corresponding problems for Brouwer fixed points have been studied by Etessami and Yannakakis . In particular, they define the class FIXP that captures the complexity of computing an exact fixed point of a function given by an arithmetic circuit and mapping the unit cube into itself. They prove that computing an exact Nash equilibrium of a 3-player game is FIXP-complete. In doing so, they use a special type of reduction, called an SL-reduction, that ensures that the reduction also holds for three problems that can be studied in the standard Turing machine model: the “strong approximation problem” (i.e. find a point close to an exact solution), the “partial computation” problem (i.e. compute the first $n$ bits of an exact solution) and various decision problems. This means that computing a strong approximation for 3-player Nash is as hard as computing a strong approximation of a Brouwer function given by an arithmetic circuit. We prove that the corresponding problems for the Hairy Ball Theorem are at least as hard as their Brouwer counterparts. For the formal definition of the class FIXP, see [15, p. 2570, Lemma 4.1, Theorem 4.7], and for the formal definition of SL-reductions, see [15, p. 2540]. We define our exact computation problem for the Hairy Ball Theorem as follows:

Note that the vector field will be continuous since we never divide by . The vector field can be syntactically forced to be tangent to the sphere because we can compute the projection exactly using this kind of circuit.

Exact-Hairy-Ball is FIXP-hard. Furthermore, the corresponding strong approximation, partial computation and decision problems are also hard for the corresponding versions of FIXP (as defined in ).

Following Etessami and Yannakakis, we could define a class HB that captures the complexity of computing an exact Hairy Ball solution (and corresponding versions of the class for the related problems) by taking the set of all problems that reduce to Exact-Hairy-Ball. Then, Theorem 8 is saying that FIXP $\subseteq$ HB. Note that the three discrete problems that can be studied in the Turing machine model lie in PSPACE, by using the same technique as in [15, Proposition 4.2].

The proof is based on an idea used by Milnor to show that the Hairy Ball theorem implies Brouwer’s fixed point theorem. Note, however, that Milnor’s proof proceeds by contradiction, whereas our proof is fully constructive.

We embed two copies of a Brouwer instance (after some preprocessing) on the sphere such that any exact Hairy Ball solution yields an exact Brouwer fixed point. Note that this reduction makes use of the $\times$ and $/$ gates and cannot be used to prove PPAD-hardness of $k$D-Hairy-Ball.

Compute $y=\frac{x}{\max\{1,\|x\|_{\infty}\}}$

Output $-x\cdot\min\{1,\|x-y\|_{\infty}\}+(G(y)-x)\cdot\max\{0,1-\|x-y\|_{\infty}\}$

Step 2: From Brouwer to Hairy Ball. The high-level idea in order to construct a Hairy Ball vector field is to use the output of $\widehat{G}(x)$ as coordinates in some continuous tangent basis on $S^{k}$. However, as noted before, it is impossible to define a continuous tangent basis on all of $S^{k}$. As a result, we use two different bases (namely $\widehat{b}_{i}(x)$ and $-\widehat{b}_{i}(-x)$) and obtain two tangent vectors at $x$: $w^{-}$ and $w^{+}$. The final output $u$ is then obtained by taking a convex combination of $w^{-}$ and $w^{+}$, according to a parameter $\alpha$. This parameter $\alpha$ ensures that we do not use a tangent basis when we are close to the pole where it is not a basis. Furthermore, it also ensures that the case where $u$ is obtained as a strict convex combination (namely $\alpha\in(0,1)$) can only occur at points where $\widehat{G}(x)=-x$, which makes this case easier to analyse.

Compute $v=\widehat{G}(x_{1},\dots,x_{k})$

Compute $w^{-}=\sum_{i=1}^{k}v_{i}\widehat{b}_{i}(x)$ and $w^{+}=\sum_{i=1}^{k}(-v_{i})\widehat{b}_{i}(-x)$

Compute $\alpha=\max\{0,\min\{1,1/2-x_{0}\}\}$

is the non-normalised version of the tangent basis used in the proof of Theorem 4. In particular, the $\widehat{b}_{i}(x)$ form an orthogonal basis of the tangent space at $x$ (as long as $x_{0}<1$) and we have $\|\widehat{b}_{i}(x)\|_{2}=1-x_{0}$. Note that the output $u$ of the circuit is always tangent to the sphere at $x$.

If $x_{0}\leq-1/2$, then $u=w^{-}$, and thus, using the fact that the $\widehat{b}_{i}(x)$ form an orthogonal basis, we obtain

Since $1-x_{0}\geq 1$, this implies that $\|u\|_{2}\geq\|v\|_{2}$, i.e. $\|F(x_{0},x_{1},\dots,x_{k})\|_{2}\geq\|\widehat{G}(x_{1},\dots,x_{k})\|_{2}$. This means that any zero of $F$ yields a zero of $\widehat{G}$ by dropping the first coordinate.

If $x_{0}\geq 1/2$, then $u=w^{+}$, and the analogous computation yields that $\|u\|_{2}^{2}=\sum_{i=1}^{k}v_{i}^{2}\|\widehat{b}_{i}(-x)\|_{2}^{2}=\|v\|_{2}^{2}(1+x_{0})^{2}$. Since $1+x_{0}\geq 1$, we again obtain that $\|u\|_{2}\geq\|v\|_{2}$, and the same conclusion follows.

The last remaining case is when $|x_{0}|<1/2$. If we let $x^{\prime}=(x_{1},\dots,x_{k})$, then, since $\|x\|_{2}=1$, it must be that $\|x^{\prime}\|_{2}\geq 1/2$, which implies that $v=\widehat{G}(x^{\prime})=-x^{\prime}$. It follows that

which implies that $F$ has no zero in this region.

The reduction we have provided is an SL-reduction, since a solution of the original instance can be obtained by applying a separable linear transformation (with rational coefficients that are computable in polynomial time from the original instance) to any solution of the final instance. Furthermore, the coefficients of the separable linear transformation are always powers of $2$. It follows (see ) that the corresponding strong approximation, partial computation and decision problems are also hard for the corresponding FIXP classes. ∎

The 2D-Hairy-Cube Problem

In this section we define the 2D-Hairy-Cube problem: a discretised version of 2D-Hairy-Ball. As the name suggests, one of the main differences is that 2D-Hairy-Cube is defined on the surface of a cube instead of the surface of a ball. It will follow from our results that this discretised problem is indeed computationally equivalent to the continuous formulation.

We consider this problem mainly for two reasons. First of all, we believe it is nice to have a corresponding discrete version of 2D-Hairy-Ball that might easier to work with in some cases. This is similar to Brouwer, where the discrete version is often very useful. Another more technical point is that 2D-Hairy-Cube also serves as an intermediate step to prove PPAD-hardness of 2D-Hairy-Ball. Indeed, as we will see below, proving PPAD-hardness for 2D-Hairy-Cube is pretty straightforward using a result by Chen and Deng on a 2-dimensional Brouwer fixpoint problem.

The 2D-Hairy-Cube problem is defined on the surface of the unit cube. Every face of the cube is subdivided into $2^{n}\times 2^{n}$ identical small squares, that we call squarelets. Every squarelet contains one of four possible axis-aligned arrows tangential to its face. A solution is given by two adjacent squarelets that contain arrows going into opposite directions. Here adjacent is taken to mean that the squarelets touch, even in a single point. However, we need one additional type of solution, namely at corners. Three squarelets adjacent at a corner form a solution, if the three arrows all point towards the corner or all three point away from the corner. An arrow points towards the corner if it points towards an edge that contains the corner. Thus, for any corner squarelet, out of the four possible arrows that it can contain, two point towards the corner and two point away from it.

Note that any two adjacent faces of the cube can be thought of as being one big plane, because we can rotate one of the faces so that this is the case. This is the interpretation that is used when deciding whether two adjacent squarelets, lying on two different but adjacent faces, form a solution: we rotate one of the two faces until it is on the same plane as the other one, and then proceed as if the two squarelets were on the same face. Fig. 3 shows a 2D-Hairy-Cube instance with various solutions.

For any integer $m\geq 1$, we let $[m]:=\{1,2,\dots,m\}$. Note that we can interpret elements in $\{0,1\}^{n}$ as elements in $[2^{n}]$.

For the definition of the computational problem we assume that we are given a Boolean circuit $C:\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{3}\to\{0,1\}^{2}$ that represents a function $[2^{n}]\times[2^{n}]\times\to$. The input in $\{0,1\}^{3}$ is interpreted as an element in $\{1,2,\dots,6\}$ that determines a face of the cube. The input in $\{0,1\}^{n}\times\{0,1\}^{n}$ determines a squarelet on that face. The output in $\{0,1\}^{2}$ is interpreted as an element in $\{1,2,3,4\}$, which yields one of the four arrows allowed on this face. We say that $C$ computes a discrete field on the cube surface.

The 2D-Hairy-Cube problem is defined as: given a Boolean circuit $C:\{0,1\}^{n}\times\{0,1\}^{n}\times\{0,1\}^{3}\to\{0,1\}^{2}$ that computes a discrete field on the cube surface, find:

two adjacent squarelets that contain arrows going in opposite directions, or

three adjacent corner squarelets, such that all three arrows point towards the corner, or all three point away from the corner.

In Appendix A we prove that this problem reduces to 2D-Hairy-Ball (Proposition 18). Thus, it also lies in PPAD by Corollary 5. Below we prove that it is also PPAD-hard (Proposition 11), which yields:

2 PPAD-hardness

In this section we prove that 2D-Hairy-Cube is PPAD-hard. The proof uses the PPAD-hardness of the discrete 2D-Brouwer problem by embedding an instance of a slightly modified discrete 2D-Brouwer problem on two opposite faces of the cube. We start by defining the modified discrete 2D-Brouwer problem and proving that it is PPAD-hard.

The 2-dimensional discrete Brouwer fixpoint problem we will consider is defined on a big square that is partitioned into $2^{n}\times 2^{n}$ squarelets. Every squarelet contains one of four possible cardinal direction arrows: right, left, up, down. A solution is given by two adjacent squarelets that contain arrows pointing in opposite directions. Two squarelets are adjacent if they have at least one point in common (in particular, squarelets can also be adjacent diagonally).

The input is a Boolean circuit $C:[2^{n}]\times[2^{n}]\to\{(1,0),(-1,0),(0,1),(0,-1)\}$ that computes the cardinal arrow in a given input squarelet. We say that $C$ satisfies the Brouwer boundary conditions, if $C(1,a)=(1,0)$, $C(2^{n},b)=(-1,0)$, $C(b,1)=(0,1)$ and $C(a,2^{n})=(0,-1)$, for all $a\in[2^{n}]\setminus\{1\}$ and $b\in[2^{n}-1]$. This corresponds to requiring that, in squarelets forming the boundary of the domain, the arrows point inwards. Note that this condition can be enforced syntactically on the circuit. If $C$ satisfies the Brouwer boundary conditions, then there must exist a solution. Otherwise, we could use the instance to define a continuous function from the square to itself which does not have a fixpoint, a contradiction to Brouwer’s Fixpoint theorem. We now give the formal definition of the problem.

The problem 2D-Variant-Brouwer is defined as: given a Boolean circuit $C:[2^{n}]\times[2^{n}]\to\{(1,0),(-1,0),(0,1),(0,-1)\}$ such that $C(1,a)=(1,0)$, $C(2^{n},b)=(-1,0)$, $C(b,1)=(0,1)$ and $C(a,2^{n})=(0,-1)$, for all $a\in[2^{n}]\setminus\{1\}$ and $b\in[2^{n}-1]$, find $x$ and $y$ such that $\|x-y\|_{\infty}\leq 1$ and $C(x)+C(y)=0$.

The main difference to the standard discrete 2D-Brouwer problem is that we have $4$ possible arrows instead of the three $(1,0),(0,1),(-1,-1)$ and we are looking for a place where two opposite arrows meet, instead of a place where all three types of arrows meet. Any 2D-Variant-Brouwer instance can also be interpreted as a 2D-Tucker instance . Indeed, if we interpret $(1,0),(-1,0),(0,1),(0,-1)$ as $+1,-1,+2,-2$, then the boundary satisfies the Tucker conditions (i.e. two boundary squarelets that are diametrically opposite each other with respect to the centre of the domain, contain opposite numbers). Furthermore, 2D-Variant-Brouwer-solutions exactly correspond to 2D-Tucker-solutions. Thus, one might think that 2D-Variant-Brouwer could be PPA-complete instead of PPAD-complete. However, the corresponding 2D-Tucker instances have the specificity of having monochromatic sides (except for the corners) and this puts the problem in PPAD. Indeed, the proof of PPA-hardness of 2D-Tucker uses instances with non-monochromatic sides .

Membership in PPAD follows from the fact that 2D-Variant-Brouwer reduces to 2D-Hairy-Cube (Proposition 11), which reduces to 2D-Hairy-Ball (Proposition 18) which is in PPAD (Corollary 5). Alternatively, one could also reduce 2D-Variant-Brouwer to the continuous 2D-Brouwer problem (by interpolating between centres of the squarelets) which takes a continuous function as input (represented as an arithmetic circuit) and is known to lie in PPAD .

It remains to show that 2D-Variant-Brouwer is PPAD-hard. This is done by using the same idea as for the standard 2D-Brouwer problem , namely by embedding a 2-dimensional End-of-Line instance on the grid into a 2D-Variant-Brouwer instance. Since the 2-dimensional End-of-Line problem is PPAD-hard , the result follows.

The only difference with is that in our case, paths are implemented using an “upward” arrow at the centre of the path, a “right” arrow on the left side of the path, and a “left” arrow on the right side of the path. The environment, where there is no path, is filled with “downward” arrows. As a result, a solution, i.e., a point where two opposite arrows meet, can only occur when a path starts or stops in the environment. The same type of construction for the paths (if we interpret labels as arrows) was used to show that 2D-Tucker is PPAD-hard . The correctness of the reduction follows by the arguments presented in .

We provide a few more details about the construction for the interested reader. Consider any 2-dimensional End-of-Line instance on the $[2^{n}]\times[2^{n}]$ grid. We will construct a 2D-Variant-Brouwer instance on the $[2^{n+3}]\times[2^{n+3}]$ grid. Every grid node in the original End-of-Line instance corresponds to a region of $8\times 8$ squarelets. In this region, the End-of-Line path is represented by squarelets containing the “upward” arrow $(0,1)$. Thus, if the path comes into the grid node from the left neighbour and leaves towards the bottom neighbour, then the $8\times 8$ region will contain a width-2 path of squarelets that starts at the centre of the left side of the region, makes a right angle at the centre of the region and then goes to the centre of the bottom side of the region. All the squarelets on this width-$2$ path get the arrow $(0,1)$. Any squarelets that are adjacent to the path from the left side (with respect to the direction of the path) get the arrow $(1,0)$. Any squarelets that are adjacent to the path from the right side get the arrow $(-1,0)$. All other squarelets get the arrow $(0,-1)$.

If a grid node is isolated, then we just assign the arrow $(0,-1)$ to all of its squarelets. If a grid node is a source or a sink, then there will be a solution, since the path of $(0,1)$ arrows will touch the environment of $(0,-1)$ arrows. The 2D-Variant-Brouwer boundary conditions can be enforced without changing the solutions. We just need to be careful at the bottom side, since the boundary has arrow $(0,1)$ and we don’t want them to touch the environment of $(0,-1)$ arrows. To avoid this we also require that the stripe of width $1$ just above the bottom boundary be filled with $(-1,0)$ arrows. It is easy to see that a careful construction of the region corresponding to the origin of the grid (the known source of the End-of-Line instance) ensures that no solution occurs there. It follows that any solution to the 2D-Variant-Brouwer instance must yield a solution to the 2-dimensional End-of-Line instance. Furthermore, the circuit $C$ computing the arrow in each squarelet can be constructed efficiently. ∎

We reduce from 2D-Variant-Brouwer. By Lemma 10 the result then follows. Consider an instance $C$ of 2D-Variant-Brouwer. We construct an instance of 2D-Hairy-Cube as follows. The top face of the cube is identical to the instance represented by $C$. The bottom face is identical to the negation of the instance represented by $C$, i.e. all arrows are negated (in particular, on the boundary they point outwards, instead of inwards). The other four faces of the cube are uniformly filled with an arrow pointing towards the top face. It is easy to check that a solution can only appear on the top or bottom face and corresponds to a solution to the original problem. Furthermore, the circuit computing the arrow in any squarelet of the surface of the cube can be constructed efficiently from $C$. ∎

The Hairy-Ball Problem on the Torus of Genus g𝑔g

In this section we consider the 2-dimensional torus of genus $g$ (also called $g$-holed torus, or $g$-torus) instead of the sphere. The Hairy Ball theorem does not hold on the torus of genus $1$, i.e. the standard torus. It is straightforward to define a continuous tangent field that never vanishes. However, as proved by Poincaré , the theorem does hold for the 2-dimensional torus of genus $g$ for all $g\geq 2$.

We prove that the corresponding computational problem is again PPAD-complete. Even though the general techniques are very similar to those seen in previous sections, the interesting point is that the reduction to End-of-Line yields $2(g-1)$ sources instead of $2$. Thus, we can make full use of the multiple-source End-of-Line results of Section 8. We believe that the reduction to a $2(g-1)$-source End-of-Line instance is a natural and necessary step in the reduction and that this multiple source aspect is intrinsic to the problem, since the torus of genus $g$ has Euler characteristic $2-2g$ .

We use the term “$g$-torus” to refer to the torus of genus $g$, i.e. the 2-dimensional torus with $g$ holes, embedded in $3$-dimensional space. This should not be confused with the 1-holed torus embedded in $g$-dimensional space. We mainly work with the 2-torus, since all the arguments generalise to the $g$-torus in a straightforward way. We define the 2-torus as follows: $(x_{1},x_{2},x_{3})$ lies on the 2-torus if it satisfies the equation

where $d_{1}$ is the distance of $(x_{1},x_{2},0)$ to $(0,0,0)$, $d_{2}$ is the distance to $(5,0,0)$, and $d_{3}$ is the distance to the segment $(0,0,0)$-$(5,0,0)$. Fig. 4 provides an illustration of this 2-torus.

Using the expression above, one can always efficiently check whether a given $(x_{1},x_{2},x_{3})$ lies on the 2-torus. However, it is not always possible to exactly compute the projection of a vector onto the tangent space at some point on the 2-torus.

This construction is easy to generalise to the $g$-hole torus, for any $g\geq 2$. We call the corresponding object the $g$-torus and denote it by $T_{g}$.

Both of our reductions will use a base field $F_{B}$, which is defined everywhere except on the two flat regions of the 2-torus. If $x_{1}^{2}+x_{2}^{2}\in$ or if $x_{1}^{2}+x_{2}^{2}\in$ and $x_{1}\leq 0$, then $F_{B}(x_{1},x_{2},x_{3})=(x_{2},-x_{1},0)$. If $(x_{1}-5)^{2}+x_{2}^{2}\in$ or if $(x_{1}-5)^{2}+x_{2}^{2}\in$ and $x_{1}\geq 5$, then $F_{B}(x_{1},x_{2},x_{3})=(x_{2},-x_{1}+5,0)$. If $x_{1}\in$ and $|x_{2}|\in$, then $F_{B}(x_{1},x_{2},x_{3})=(x_{2},0,0)$. This partial field is continuous and does not have any zeros. Note that the field does not depend on $x_{3}$ and is always contained in the $(x_{1},x_{2})$-plane.

The computational problem is defined as follows:

Let $g\geq 2$. The Hairy-$g$-Torus problem is defined as: given $\varepsilon>0$ and an arithmetic circuit $G$ with 3 inputs and outputs, using gates $\{+,\times\zeta,\max\}$ and rational constants, find $x\in T_{g}$ such that $\|P_{x}^{\varepsilon}[G(x)]\|_{\infty}\leq\varepsilon$.

Here $P_{x}^{\varepsilon}$ denotes the projection onto the tangent space to $T_{g}$ at $x\in T_{g}$ with error at most $\varepsilon/2$, i.e. $\|P_{x}[G(x)]-P_{x}^{\varepsilon}[G(x)]\|_{\infty}\leq\varepsilon/2$, where $P_{x}$ is the exact projection.

For any $g\geq 2$, Hairy-$g$-Torus is PPAD-complete.

In Proposition 13 below, we show that Hairy-$g$-Torus reduces to $2(g-1)$-source End-of-Line. Using the results in Section 8 (Theorem 14), it follows that the problem lies in PPAD. PPAD-hardness is proved in Appendix C by embedding $2(g-1)$ modified copies of a 2D-Variant-Brouwer instance. ∎

2 Hairy-g𝑔g-Torus is in PPAD

For any $g\geq 2$, Hairy-$g$-Torus reduces to $2(g-1)$-source End-of-Line.

We will prove the result for $g=2$. The proof immediately generalises to any other larger value of $g$.

For this proof we need a sufficiently fine triangulation of the $2$-torus that is also locally efficiently computable. For any point on the $2$-torus, we should be able to efficiently compute all nearby triangles. In particular, given a triangle we should be able to efficiently obtain all adjacent triangles. Moreover, the triangulation should be sufficiently fine, meaning that, given some $\delta>0$, we should have a triangulation such that all corners of a triangle are within distance $\delta$ of each other. We call this a $\delta$-fine triangulation.

We can construct such a triangulation as follows. We start with a fixed triangulation of the $2$-torus, such that the curved region delimited by each triangle is sufficiently flat. Then, we can easily construct a fine triangulation of every triangle. Finally, we compute the (approximate) projection of the points of this fine triangulation on the surface of the $2$-torus. By taking a fine enough triangulation of the triangles and a good enough approximation of the projection, we can ensure that the triangulation is $\delta$-fine. Note that when we take the approximate projection, we compute a point that exactly lies on the $2$-torus and is close to the true projection. Thus, all the points of the triangulation lie exactly on $T_{2}$.

Let $(\varepsilon,G)$ be an instance of Hairy-$2$-Torus. Using similar arguments to the proof of Lemma 2, it is straightforward to show that $x\to P_{x}[G(x)]$ is $L$-Lipschitz continuous on the $2$-torus, for a similar value of $L$. Pick a $\delta$-fine triangulation of the $2$-torus as described above with $\delta=\varepsilon\sqrt{2(1-\cos 1^{\circ})}/(2L)$. We will now colour every node of the triangulation with one of three colours $\{A,B,C\}$ and use a Sperner argument on this colouring. To construct the colouring we will use the base field $F_{B}$, defined earlier. We just need to decide how to extend the base field to also be defined on the two flat regions (at $x_{3}=1$ and $x_{3}=-1$). Here, the simplest way to do this is to draw an X-shape on the flat region and assign one of the four cardinal flat vectors to each of the four regions (see Fig. 5). Then, the base field is defined for any point on $T_{2}$ (if the point lies on a boundary, resolve ties arbitrarily), even though it is no longer continuous.

For any node $x$ of the triangulation, its colour depends on $\theta\in[0^{\circ},360^{\circ})$ : the angle between $P_{x}[G(x)]$ and the base field at $x$. The angle is measured from $P_{x}[G(x)]$ to the base field vector in counter-clockwise direction when looking from outside the $2$-torus. If $0^{\circ}\leq\theta<120^{\circ}$ then the colour is $A$, if $120^{\circ}\leq\theta<240^{\circ}$ it is $B$, and if $240^{\circ}\leq\theta<360^{\circ}$ it is $C$. Unfortunately, we cannot exactly compute $P_{x}[G(x)]$, nor the angle between two vectors. Thus, we compute a sufficiently good approximation of $P_{x}[G(x)]$ and of the angle and choose the colour based on this approximation. Specifically, we compute a good enough approximation such that if $\|P_{x}[G(x)]\|_{\infty}\geq\varepsilon/2$, then the angle has error at most $1^{\circ}$.

We can assume that at the centre of the cross in the top flat region ($x_{3}=1$), the triangulation is such that there are four points such that each lies in one of the four regions, and they form two triangles of the triangulation. Let $x^{(1)},x^{(2)},x^{(3)},x^{(4)}$ be those four points. Note that the pairwise distance between any of those four points is at most $2\delta$. Thus, by the choice of $\delta$, we must have that $\|P_{x^{(i)}}[G(x^{(i)})]-P_{x^{(j)}}[G(x^{(j)})]\|_{\infty}\leq\varepsilon\sqrt{2(1-\cos 1^{\circ})}$, for any $i,j$. Note that since we are in the flat region, we can project exactly, i.e. $P_{x}^{\varepsilon}[G(x)]=P_{x}[G(x)]$. If there exists $i$ such that $\|P_{x^{(i)}}[G(x^{(i)})]\|_{\infty}\leq\varepsilon$, then we are done. If this is not the case, then the angle of $P_{x^{(i)}}[G(x^{(i)})]$ varies by at most one degree for $i\in\{1,2,3,4\}$. It follows that the angle $\theta_{i}$ computed for each of the four points is equal to the angle between the base field and some fixed vector, with an error of at most $1^{\circ}$. Since the four points’ base vectors correspond to the four cardinal flat vectors, it is easy to check that the four points get the colours $A,B,C$ in clockwise order (and one of the colours is repeated, i.e. $A,A,B,C$ or $A,B,B,C$ or $A,B,C,C$). The $AB$ segment is our first Sperner-source. Applying the same arguments to the bottom flat region ($x_{3}=-1$) yields four points that again get the colours $A,B,C$ in clockwise order. Thus, we get a second $AB$ segment that is another Sperner-source. Each of those sources is the beginning of a Sperner path that will eventually lead to a trichromatic triangle. Since the $2$-torus is orientable, the two paths cannot cancel each other out.

It remains to show that any trichromatic triangle yields a solution to the Hairy-$2$-Torus instance. Consider any trichromatic triangle with three vertices $x^{(1)},x^{(2)},x^{(3)}$. Assuming we have picked $\delta$ smaller than some constant, the base field can vary at most by an angle of $90^{\circ}$ on these three vertices. If $\|P_{x^{(i)}}^{\varepsilon}[G(x^{(i)})]\|_{\infty}\leq\varepsilon$ for some $i$, then we are done. Assume that this is not the case. For all $i,j$ we also have that $\|P_{x^{(i)}}[G(x^{(i)})]-P_{x^{(j)}}[G(x^{(j)})]\|_{\infty}\leq L\delta\leq\varepsilon\sqrt{2(1-\cos 1^{\circ})}/2$ and thus the angle between those two vectors is at most $1^{\circ}$ (because $\|P_{x^{(i)}}[G(x^{(i)})]\|_{\infty}>\varepsilon/2$). Thus, the $\theta_{i}$ can vary by at most $93^{\circ}$ for $i=1,2,3$ (because every $\theta_{i}$ is computed with error at most $1^{\circ}$ in this case). It follows that it is impossible to get all three colours.