text:
# Emerging behavior in electronic bidding

## Abstract

We characterize the statistical properties of a large number of agents on two major online auction sites. The measurements indicate that the total number of bids placed in a single category and the number of distinct auctions frequented by a given agent follow power-law distributions, implying that a few agents are responsible for a significant fraction of the total bidding activity on the online market. We find that these agents exert an un-proportional influence on the final price of the auctioned items. This domination of online auctions by an unusually active minority may be a generic feature of all online mercantile processes.

Electronic commerce (E-commerce) is any type of business or commercial transaction that involves information transfer across the Internet. Over the past five years, E-commerce has expanded rapidly, taking the advantage of faster, cheaper and more convenient transactions over traditional ways. A synergetic combination of the Internet supported instantaneous interactions and traditional auction mechanisms, online auctions represent a rapidly expanding segment of E-commerce. Indeed, with the advent of the Internet most limitations of traditional auctions, such as geographical and time constraints, have virtually disappeared, making a significant fraction of the population potential auction participants 1 ; 2 . For example eBay, the largest consumer-to-consumer auction site, boosts over 40 million registered consumers, and has grown in revenue over 100,000 percent in the past five years. With the rapidly increasing number of agents the role of individuals diminishes and self-organizing processes increasingly dominate the market’s behavior 3 ; 4 . On the other hand, recently the self-organizing features of complex systems have attracted the attention of the statistical physics community because they contain diverse cooperations among numerous components of a system, resulting in patterns and behavior which are more than the sum of the individual action of the components. While many systematic studies have been carried out to understand such emerging patterns in various systems, little attention has been paid to electronic auctions. In this Letter, we collect auction data and show that the bidding of hundreds of thousands of agents leads to unexpected emerging behavior, impacting on everything from the bidding patterns of the participating agents to the final price of the auctioned item. We found that the total number of bids placed in a single category by a given agent follows a power-law distribution. The power-law behavior is rooted in the finding that an agent that makes frequent bids up to a certain moment is more likely to bid in the next time interval. Moreover, we find that the number of distinct items frequented by a given agent also follows a power-law distribution. The power-law behavior implies that a few powerful agents bid more frequently and on more distinct items than others. We will show that such powerful agents exert strong influence on the final prices in distinct auctions.

To be specific, we collected auction data from two different sources. First, we downloaded all auctions closing on a single day on eBay, including 264,073 auctioned items, grouped by the auction site in 194 subcategories. The dataset allowed us to identify 384,058 distinct agents via their unique user ID. To verify the validity of our findings in different markets and time spans, we collected data over a one year period from eBay’s Korean partner, auction.co.kr, involving 215,852 agents that bid on 287,018 items in 62 subcategories.

In a typical online auction a seller places the item’s description on the auction site and sets the starting and the closing time for the auction. Agents (bidders) submit bids for the item. Each new bid has to exceed the last available bid by a preset increment. Agents can bid manually, placing a fixed bid, or on some auction sites (such as eBay but not on their Korean partner) they can take advantage of proxy bidding. In proxy bidding an agent indicates to the auction house the maximum price he/she is willing to pay for the given item (proxy bid), which is not disclosed to other bidders. Each time a bidder increases the bid price, the auction house makes automatic bids for the agent with an active proxy bid, outbidding the last bid with a fixed increment, until the proxy price is reached. In online consumer-to-consumer auctions the agent with the highest bid wins and pays the amount of that bid; all other participants pay nothing.

Most online auction sites keep a detailed, publicly available record of all bids and identify the bidding agents via an unique login name. It is this transparency of the bidding history that allows us to characterize in quantitative terms the auction process. Each completed auction can be characterized by two quantities: the number of distinct agents bidding on the same item ($`n_{\mathrm{agent}}`$) and the total number of recorded bids for the item ($`n_{\mathrm{bids}}`$), where $`n_{\mathrm{bids}}n_{\mathrm{agent}}`$, as each agent can place multiple bids. In Fig. 1 we show the distribution of $`n_{\mathrm{agent}}`$ and $`n_{\mathrm{bids}}`$ over all auctions recorded on eBay, finding that they both follow $`P(n)\mathrm{exp}(n/n_0)`$, where $`n_0=5.6`$ for $`n_{\mathrm{bids}}`$ and $`n_0=2.5`$ for $`n_{\mathrm{agent}}`$. We obtained similar results for the Korean market, with $`n_0=10.8`$ for $`n_{\mathrm{bids}}`$ and $`n_0=7.4`$ for $`n_{\mathrm{agent}}`$. This simple exponential form is unexpected, as one expects that the bidding distribution is the result of many independent events, and therefore follows a Gaussian, peaked around the average number of bids and decreasing as $`\mathrm{exp}(an^2)`$ with a constant $`a`$. The deviation from a Gaussian distribution could come from the fact that Fig. 1a collapses data from different categories, displaying different bidding patterns. In Fig. 1b and c we show the distribution in two subcategories (sports trading cards and printed, recorded music), finding that they follow the same functional form as the aggregated data. Therefore, the exponential form for the activity distribution appears to be a general feature of all auctions, indicating that the majority of auctions have only a few bidders and auctions with a large number of bids or participating agents are exponentially rare.

To characterize the activity of individual agents we determined the number of bids placed by each agent on each auction. As agents place simultaneous bids on items that closely resemble each other, we denote by $`\kappa _{\mathrm{bid}}`$ the total number of bids placed by the same agent in auctions in the same category. For example, if several similar computers are sold on separate auctions, agents looking for a computer often bid simultaneously for several or all of them. We find that the distribution of $`\kappa _{\mathrm{bid}}`$ follows a power law

$$P(\kappa _{\mathrm{bid}})\kappa _{\mathrm{bid}}^\gamma ,$$
(1)
where $`\gamma =3`$ (Fig. 2a) on both eBay and the Korean auction. A similar power law characterizes the distribution of the number of different auctions, $`n_{\mathrm{auct}}`$, frequented by individual agents, finding that

$$P(n_{\mathrm{auct}})n_{\mathrm{auct}}^\beta ,$$
(2)
where $`\beta =3.5`$ (Fig. 2b). The power-law distribution shown in Fig. 2a implies that while most agents place only a small number of bids, a few agents bid very frequently, placing several hundred bids on the same day. Similarly, Fig. 2b indicates that while most agents participate in a few auctions only, a few agents bid very widely, some placing simultaneous bids on over a hundred distinct items on the same day. Therefore, unknown to most participants, the auction process is dominated by a small number of highly active agents, or power-agents, that pursue a very aggressive bidding pattern, placing simultaneously a large number of bids on a wide range of items. These power-agents are responsible for the power-law tail of the distribution shown in Fig. 2. Our measurements indicate that there is a strong correlation between the number of bids placed by an agent on an item and the number of items the same agent bids for, indicating that power agents simultaneously bid frequently and widely.

Agents with an aggressive bidding pattern significantly alter the nature of the bidding process, potentially distorting the chance of a typical agent to win an auction. To inspect the effect of the bidding pattern on the success rate of a given agent, we determined the fraction of auctions won by the most, the second, or the $`k`$-th most frequently bidding agents. We find that in 61% of all auctions the winner is the agent that makes the most bids, and in 29% of all auctions the second most frequently bidding agent wins the auction (Fig. 3a). Less than 0.3% of the auctions are won by agents whose activity ranks fifth or higher. As most auctions have only a few participating agents (Fig. 1a), it is useful to re-examine the winning patterns in auctions with the same number of agents. We find that if only two agents participate in an auction, and each place multiple bids, in 85% of the cases the agent with more bids wins the auction (Fig. 3b). The situation is similar for three agents as well (Fig. 3c): in 64% of the cases the more active agent wins, followed by the second most active, which wins in 32% of the cases. In auctions with larger number of participants (Fig. 3d-e) we observe a similar pattern. These results indicate that frequently bidding agents play a key role in setting the final price of most auctioned items: in the vast majority of the cases the agents who place the largest number of bids are the winners of the auction process. This finding indicates that despite the widespread practice of sniping among experienced users 5  when bidders place bids only in the last 60 seconds of the auction hoping to win the auctioned item, on average frequent bidders are more successful.

As the power law distribution (Fig. 2b) indicates that some agents bid rather widely, the question is, does such wide bidding result in economic advantage for power bidders? Our results indicate that power agents not only are the frequent winners of the auctions in which they participate, but they also pay less than other agents on similar items. Indeed, in Fig. 4 we show the fraction of times the most frequently bidding agent pays less for an item than other agents that win auction of items in the same category. We find that the more auctions an agent participates, the larger is its chance to pay less for the same item than the less widely bidding agents.

The observed power law distribution is rooted in the dynamics of the bidding process. Indeed, two processes contribute to the final number of bids placed on a given item: new agents entering the bidding process and agents that already placed a bid increase their bid. We find that this pattern is governed by a process often referred to as preferential attachment, similar to those responsible for the emergence of scaling in complex networks 6 : more bids an agent places on a given item up to a certain moment, more likely is that he/she will place an another bid in the future (Fig. 5). The linearity of the observed relationship is known to lead to power law distributions, as demonstrated by studies in both economics 7 ; 8  and complex networks 9 ; 10 ; 11 .

While power laws have been often observed in economic contexts, ranging from city 8  and company size distribution 12 ; 13  to Pareto’s observation of wide income distributions 14  and time series analysis 5 , they are rather unexpected during the frequency of bidding of individual users. In order to develop an analytical framework to capture the dynamics of the bidding process current auction models inevitably make use of equilibrium concept 15 ; 16 . Often this requires the assumption that the number of agents is fixed 15  which, while leads to analytically tractable models, is not realistic in the context of Internet auctions. Indeed, the power laws observed here are the result of the auction’s fundamental openness and non-equilibrium nature. In the past few years the observation of such non-equilibrium features in economic phenomena has led to an increased interest among physicists and mathematicians in the self-organizing processes governing economic systems 3 ; 4 ; 12 ; 17 ; 18 . Our finding, that similar non-equilibrium processes govern the behavior of online auctions places these mercantile processes in the realm of agent driven self-organization.

In conclusion, we have collected online auction data and analyzed the statistical properties of emerging patterns created by a large number of agents. We found that the total number of bids placed in a single category and the number of distinct auctions frequented by a given agent follow power-law distributions. Such power-law behaviors imply that the online auction system is driven by self-organized processes, involving all agents participated in a given auction activity. We also uncovered the empirical fact that the more bids an agent places up to a given moment, more likely it is that it will place another bid in the next time interval, which plays an important role in generating the power-law behavior in the bidding frequency distribution by a given agent.

This work is supported by the KOSEF Grant No. R14-2002-059-01000-0 in the ABRL program.


format: text

text:
# CAT(0) is an algorithmic property

## 1. Polyhedral geometry

We begin by reviewing the necessary background regarding polyhedral geometry. A metric space $`(K,d)`$ is called a *geodesic metric space* if every pair of points in $`K`$ can be connected by a geodesic. The geodesic metric spaces we will be primarily interested in will be cell complexes constructed out of convex polyhedral cells in $`^n`$, $`𝔼^n`$ or $`𝕊^n`$. After describing these spaces, we will quickly review their relationship with comparison geometry. Details can be found in , , , and .

###### Definition 1.1 (Polyhedral cells).

A *convex polyhedral cell* in $`^n`$ or $`𝔼^n`$is the convex hull of a finite set of points. The convex hull of $`n+1`$ points in general position is an *$`n`$-simplex*. A *polyhedral cone* in $`𝔼^n`$ is the positive cone spanned by a finite set of vectors. If the original vectors are linearly independent, it is a *simplicial cone*. A *cell (simplex) in $`𝕊^n`$* is the intersection of a polyhedral cone (simplicial cone) in $`𝔼^n`$ with $`𝕊^n`$.

A spherical cell which does not contain a pair of antipodal points is *proper*. All Euclidean and hyperbolic cells are considered proper. Notice that every spherical cell can be subdivided into proper spherical cells by it cutting along the coordinate axes. If $`\sigma `$ denotes a proper convex polyhedral cell, then $`\sigma ^{}`$ will denote its interior and $`\sigma `$ will denote its boundary.

###### Definition 1.2 ($`M_\kappa `$-complexes).

An *$``$-complex* \[$`𝔼`$-complex, $`𝕊`$-complex\] is a connected cell complex $`K`$ make up of proper hyperbolic \[Euclidean, spherical\] cells glued together by isometries along faces. A cell complex which has an $``$-complex, an $`𝔼`$-complex, or an $`𝕊`$-complex structure, will be called a *metric polyhedral complex*, or *$`M_\kappa `$-complex* for short where $`\kappa `$ denotes the curvature constant common to all of its cells. More generally, an $`M_\kappa `$-complex is formed from polyhedral cells with constant curvature $`\kappa `$.

###### Convention 1.3 (Subdivisions).

As noted above, every spherical cell can be subdivided into proper spherical cells. Since proper spherical cells are required in an $`𝕊`$-complex, a subdivision will occasionally be necessary in order to convert a complex built out of pieces of spheres to be considered an $`𝕊`$-complex.

###### Definition 1.4 (Shapes).

If $`K`$ is an $`M_\kappa `$-complex, then the isometry types of the cells of $`K`$ will be called the *shapes of $`K`$* and the collection of these isometry types will be denoted $`\text{Shapes}(K)`$. When $`\text{Shapes}(K)`$ is finite, $`K`$ is said to have only *finitely many shapes*. Notice that since cells of different dimensions necessarily have different isometry types, finitely many shapes implies that $`K`$ is finite dimensional. It does not, however, imply that $`K`$ is locally finite. Notice also that if $`K`$ is an $`M_\kappa `$-complex with only finitely many shapes, then there is a subdivision $`K^{}`$ of $`K`$ where the cells of $`K^{}`$ are proper and simplicial, and $`\text{Shapes}(K^{})`$ remains finite.

###### Definition 1.5 (Paths and Loops).

A *path $`\gamma `$* in a metric space $`K`$ is a continuous map $`\gamma :[0,\mathrm{}]K`$. A path is *closed* if $`\gamma (0)=\gamma (\mathrm{})`$. A *loop* is a closed path where the basepoint $`\gamma (0)`$ has been forgotten. Technically, a loop is viewed as a continuous map from a circle to $`K`$. The circle of perimeter $`\mathrm{}`$ will be denoted $`C_{\mathrm{}}`$.

###### Definition 1.6 (Piecewise geodesics).

Let $`K`$ be an $`M_\kappa `$-complex. A *piecewise geodesic* $`\gamma `$ in $`K`$ is a path $`\gamma :[a,b]K`$ where $`[a,b]`$ can be subdivided into a finite number of subintervals so that the restriction of $`\gamma `$ to each closed subinterval is a path lying entirely in some closed cell $`\sigma `$ of $`K`$ and that this path is the unique geodesic connecting its endpoints in the metric of $`\sigma `$. The *length* of $`\gamma `$, denoted $`\text{length}(\gamma )`$, is the sum of the lengths of the geodesics into which it can be partitioned. A *closed piecewise geodesic* and a *piecewise geodesic loop* are defined similarly. The *intrinsic metric* on $`K`$ is defined as follows:

$$d(x,y)=inf\{\text{length}(\gamma )|\gamma \text{ is a piecewise geodesic from }x\text{ to }y\}$$

In general $`d`$ is only a pseudometric, but when $`K`$ has only finitely many shapes, $`d`$ is a well-defined metric and $`(K,d)`$ is a geodesic metric space \[4, Theorem 7.19\].

###### Convention 1.7 (Parameterizations).

If $`\gamma :[0,\mathrm{}]`$ is a piecewise geodesic, we will always assume that the map $`\gamma `$ has been reparameterized by arc-length. In particular, $`\mathrm{}`$ should be the length of $`\gamma `$ and for all subintervals $`[a,b]`$ in $`[0,\mathrm{}]`$, the length of $`\gamma ([a,b])`$ should be exactly $`ba`$. Following the same convention, if a loop is a closed piecewise geodesic of length $`\mathrm{}`$, then we will assume that its domain is a circle whose circumference is $`\mathrm{}`$. We will use $`C_{\mathrm{}}`$ to denote such a circle and we will identify the points on $`C_{\mathrm{}}`$ with reals mod $`\mathrm{}`$ and in particular with the points $`[0,\mathrm{})`$.

###### Definition 1.8 (Size).

The *size* of a piecewise geodesic $`\gamma :[0,\mathrm{}]K`$ is the number of open cells of $`K`$ through which $`\gamma ([0,\mathrm{}])`$ passes, with multiplicities. Technically, the size of $`\gamma `$ is the minimal number of subintervals (open, half-open, or closed) into which $`[0,\mathrm{}]`$ must partitioned so that the image of each subinterval lies in a single open cell of $`K`$. Note that some of these subintervals may be single points. The fact that $`\gamma `$ is a piecewise geodesic ensures that the size of $`\gamma `$ is finite.

###### Definition 1.9 (Links).

Let $`K`$ be an $`M_\kappa `$-complex with only finitely many shapes and let $`x`$ be a point in $`K`$. The set of unit tangent vectors to $`K`$ at $`x`$ is naturally an $`𝕊`$-complex called the *link of $`x`$ in $`K`$*, or $`\text{link}(x,K)`$. If $`K`$ has only finitely many shapes, then $`\text{link}(x,K)`$ has only finitely many shapes.

When $`x`$ lies in the interior of a cell $`B`$ of $`K`$, $`\text{link}(x,B)`$ is a sphere of dimension $`k=dimB1`$ sitting inside $`\text{link}(x,K)`$. Moreover, the complex $`\text{link}(x,K)`$ can be viewed as a spherical join of $`𝕊^k`$ and another $`𝕊`$-complex, denoted $`\text{link}(B,K)`$, which can be thought of as the unit tangent vectors to $`x`$ in $`K`$ which are orthogonal to $`B`$. The complex $`\text{link}(B,K)`$ is called the *link of the cell $`B`$ in $`K`$*. Once again, if $`K`$ has only finitely many shapes, then $`\text{link}(B,K)`$ has only finitely many shapes as well.

###### Definition 1.10 (Local geodesics).

Let $`K`$ be an $`M_\kappa `$-complex. A piecewise geodesic $`\gamma `$ in $`K`$ is called a *local geodesic* if for each point $`x`$ on $`\gamma `$, the incoming and outgoing unit tangent vectors to $`\gamma `$ at $`x`$ are at a distance of at least $`\pi `$ from each other in $`\text{link}(x,K)`$.

The size and length of local geodesics are closely related.

###### Theorem 1.11 (Bridson).

If $`K`$ is an $`M_\kappa `$-complex with only finitely many shapes, then for every $`\mathrm{}>0`$ there exist an integer $`N>0`$, depending only on $`\text{Shapes}(K)`$, such that every local geodesic of size at least $`N`$ has length at least $`\mathrm{}`$.

For a proof of this result see \[3, Theorem 1.11\] or \[4, Theorem I.7.28\]. Both references state this theorem in a more general form using the concept of a taut-$`m`$-string. We merely need to note that local geodesics are taut-$`m`$-strings and the size of a local geodesic $`\gamma `$, as defined above, is within a constant factor of the integer $`m`$ when $`\gamma `$ is viewed as a taut-$`m`$-string.

###### Remark 1.12 (Constructing $`N`$).

The *existence* of a constant such as $`N`$ is important, but for our purposes, we need to know more. There needs to be an algorithm which constructs an integer $`N`$ which will work solely from $`\text{Shapes}(K)`$ and the real number $`\mathrm{}`$. There is indeed such an algorithm, and we will return to this issue later in the article. See Lemma 5.3.

Notice that it is in fact sufficient to construct an $`N`$ that will work for one particular value of $`\mathrm{}`$. That is, if every local geodesic of size $`N`$ has length at least $`\mathrm{}`$, then every local geodesic of size $`kN`$ will have length at least $`k\mathrm{}`$. Thus for an arbitrary $`\beta `$, the least integer greater than $`\frac{\beta }{\mathrm{}}N`$ will work for $`\beta `$.

## 2. Comparison geometry

Metric polyhedral complexes are particularly useful in the creation of metric spaces of non-positive curvature. As in the previous section, details can be found in , , , and .

###### Definition 2.1 (Globally $`\text{CAT}(\kappa )`$).

Let $`K`$ be a geodesic metric space, let $`T`$ be a geodesic triangle in $`K`$, and let $`\kappa =1`$, \[or $`0`$, or $`1`$\]. A *comparison triangle* for $`T`$ is a triangle $`T^{}`$ in $`^2`$, \[or $`𝔼^2`$ or $`𝕊^2`$\] with the same side lengths as $`T`$. Notice that for every point $`x`$ on $`T`$, there is a corresponding point $`x^{}`$ on $`T^{}`$. The space $`K`$ is called *globally $`\text{CAT}(\kappa )`$*, if for any geodesic triangle $`T`$ in $`K`$ \[of perimeter less than $`2\pi `$ when $`\kappa =1`$\] and for any points $`x`$ and $`y`$ on $`T`$, the distance from $`x`$ to $`y`$ in $`K`$ is less than or equal to the distance from $`x^{}`$ to $`y^{}`$ in $`^2`$ \[or $`𝔼^2`$ or $`𝕊^2`$\]. Finally, a space $`K`$ is called *locally $`\text{CAT}(\kappa )`$* if every point in $`K`$ has a neighborhood which is globally $`\text{CAT}(\kappa )`$. Locally $`\text{CAT}(0)`$ spaces are often referred to as *non-positively curved* and locally $`\text{CAT}(1)`$ spaces are called *negatively curved*.

###### Theorem 2.2.

In a globally $`\text{CAT}(0)`$ space, every pair of points is connected by a unique geodesic, and a path is a geodesic if and only if it is a local geodesic.

The next two results about $`M_\kappa `$-complexes show how global properties such as $`\text{CAT}(\kappa )`$ can be reduced to local properties and how local properties can be reduced to the existence of geodesics in $`𝕊`$-complexes.

###### Theorem 2.3.

Let $`K`$ be an $`M_\kappa `$-complex which contains only finitely many shapes.

1. If $`K`$ is an $``$-complex, then $`K`$ is globally $`\text{CAT}(1)`$ if and only if it is locally $`\text{CAT}(1)`$ and simply-connected.
2. If $`K`$ is an $`𝔼`$-complex, then $`K`$ is globally $`\text{CAT}(0)`$ if and only if it is locally $`\text{CAT}(0)`$ and simply-connected.
3. If $`K`$ is an $`𝕊`$-complex, then $`K`$ is globally $`\text{CAT}(1)`$ if and only if it is locally $`\text{CAT}(1)`$ and and there are no geodesic cycles of length $`<2\pi `$.

###### Theorem 2.4.

If $`K`$ is an $`M_\kappa `$-complex, then the following are equivalent:

1. $`K`$ is locally $`\text{CAT}(\kappa )`$.
2. The link of each vertex in $`K`$ is globally $`\text{CAT}(1)`$.
3. The link of each cell of $`K`$ is an $`𝕊`$-complex which contains no closed geodesic cycle of length less than $`2\pi `$.

Thus showing that $``$-complexes are $`\text{CAT}(1)`$ or that $`𝔼`$-complexes are $`\text{CAT}(0)`$ ultimately depends on being able to show that various $`𝕊`$-complexes contain no short geodesic cycles. In order to study short geodesic cycles we introduce the concept of a configuration. Configurations are related to the “finite models” used by Bridson and Haefliger . We will use configurations and the following theorem, which is a restatement of Theorem 1.11, to prove Theorem A.

###### Theorem 2.5.

If $`K`$ is an $`𝕊`$-complex with only finitely many shapes, then there is a constant $`N`$ depending only on $`\text{Shapes}(K)`$, such that every local geodesic of length less than $`2\pi `$ has size less than $`N`$. In other words, if $`K`$ contains a short closed geodesic $`\gamma `$, then $`\gamma `$ is contained in a finite subcomplex of $`K`$ which is the union of at most $`N`$ cells from $`\text{Shapes}(K)`$.

###### Definition 2.6 (Configurations).

A *configuration* $`C`$ is a finite $`𝕊`$-complex $`C`$ which contains at least one closed geodesic $`\gamma `$ of length less than $`2\pi `$. An $`M`$-complex $`K`$ *contains a configuration* $`C`$ if $`C`$ isometrically embeds as a subcomplex of $`\text{link}(B,K)`$ for some cell $`B`$ in $`K`$ and under this embedding at least one of the short closed geodesics contained in $`C`$ is sent to a short closed geodesic in $`\text{link}(B,K)`$. If $`K`$ does not contain a configuration $`C`$, then $`K`$ *avoids* this configuration.

If we fix the set of shapes under consideration and let the $`M_\kappa `$-complex vary, then Theorem 2.5 can be restated as an assertion about the existence of finite lists of forbidden configurations which characterize which of the complexes built out of these shapes are $`\text{CAT}(\kappa )`$.

###### Theorem A.

If $`𝒮`$ is a finite collection of shapes with curvature $`\kappa `$, then there exists a finite list of configurations $`𝒞`$ such that an $`M_\kappa `$-complex $`K`$ with $`\text{Shapes}(K)𝒮`$ is locally $`\text{CAT}(\kappa )`$ if and only if $`K`$ avoids all of the configurations in $`𝒞`$.

###### Proof.

By Theorem 2.4 it is sufficient to determine whether the link of a cell in $`K`$ contains a closed geodesic of length less than $`2\pi `$, and by Theorem 2.5 this closed geodesic must live in a finite subcomplex whose size is uniformly bounded by a constant which depends only on the set of shapes in $`𝒮`$. Since there are only a finite number of finite complexes of bounded size built out of the links of faces of shapes in $`𝒮`$ (up to isometry), the list of configurations which will destroy the property of being locally $`\text{CAT}(\kappa )`$ is contained in a finite list of possibilities. Even though this does not determine which ones they are, this does show that the list of forbidden configurations is finite. ∎

As we noted in the introduction, Theorem A merely asserts the existence of a finite list of forbidden configurations that need to be avoided but it does not provide an algorithm to construct the list. At present there are very few instances where the finite list for some collection of shapes is known explicitly. One of the main results along these lines is Moussong’s Lemma which was first stated by Gromov () in the special case where all $`1`$-cells in $`K`$ have length $`\pi /2`$ and proved in general by Moussong in his dissertation .

###### Example 2.7 (Moussong’s Lemma).

Moussong’s Lemma states that if $`K`$ is a simplicial $`𝕊`$-complex with only finitely many shapes and all of the $`1`$-cells of $`K`$ have length at least $`\frac{\pi }{2}`$, then $`K`$ is globally $`\text{CAT}(1)`$ if and only if $`K`$ is a metric flag complex. A simplicial complex is called a *flag complex* if every $`1`$-skeleton of an $`n`$-simplex is filled in with an $`n`$-simplex. A simplicial $`𝕊`$-complex is called a *metric flag complex* if every $`1`$-skeleton of an $`n`$-simplex whose edge lengths are those of a possible proper spherical $`n`$-simplex is filled in with a copy of that $`n`$-simplex. This means, for example, that three $`1`$-cells in an $`𝕊`$-complex each with length $`\pi `$ need not and cannot bound a spherical triangle.

When all of the $`1`$-cells have length $`\pi /2`$, the metric flag condition reduces to the (non-metric) flag condition. Moussong’s lemma thus enables a researcher to easily determine whether an $`n`$-dimensional cubical complex with the usual metric has a locally $`\text{CAT}(0)`$ structure. The finite list of forbidden configurations in this case is the collection of empty simplices in dimensions $`2`$ up to $`n1`$.

One way to paraphrase Theorem A is that for any finite collection of piecewise Euclidean or piecewise hyperbolic shapes, there is a finite description (similar to that in Moussong’s lemma) of the combinatorial conditions needed in order for a complex built out of these shapes to be $`\text{CAT}(0)`$ or $`\text{CAT}(1)`$. Such finite descriptions must exist by Theorem A, but most of them remain undiscovered.

## 3. Galleries

In this section we define one of our central concepts: that of a gallery. A gallery is a more precise tool than a configuration, as will become clear below. The term “gallery” has been borrowed from the study of Coxeter groups since a geodesic gallery in a Coxeter complex will be an example of a linear gallery as defined below. The galleries defined here will be either linear or circular and we begin by defining the linear ones.

###### Definition 3.1 (Linear Galleries).

Let $`K`$ be a $`M_\kappa `$-complex, let $`\gamma :[0,\mathrm{}]K`$ be a piecewise geodesic in $`K`$, let $`k`$ is the size of $`\gamma `$, and let $`\{\sigma _i^{}\}_{i=1}^k`$ be the sequence of open cells that $`\gamma `$ passes through. Finally, assume that for all $`1<i<k`$, $`\sigma _i`$ is either a common face of both $`\sigma _{i+1}`$ and $`\sigma _{i1}`$ which are distinct or else both of these are incompatible faces of $`\sigma _i`$. In the former case, we say that $`\sigma _i`$ is a *bottom cell*, and in the latter $`\sigma _i`$ is an *top cell* in the sequence.

The *linear gallery $`𝒢`$ determined by $`\gamma `$* is constructed inductively from this sequence of open cells. To start the induction, let $`𝒢_1`$ be a copy of the closed cell $`\sigma _1`$, let $`\alpha _1`$ be all of $`𝒢_1`$, and let $`\varphi _1:\alpha _1\sigma _1`$ be a specific isometry between $`\alpha _1`$ and $`\sigma _1`$. The cell $`\alpha _i`$ in $`𝒢_i`$, will always be isometric to $`\sigma _i`$ by a specific isometry $`\varphi _i`$ and the complex $`𝒢_{i+1}`$ will always contain the complex $`𝒢_i`$ as a subcomplex. We call $`\alpha _i`$ the *active cell in $`𝒢_i`$* . Next, assume that for some $`i1`$ we have defined the complex $`𝒢_i`$, its active cell $`\alpha _i`$, and an isometric $`\varphi _i:\alpha _i\sigma _i`$. The inductive step depends on whether $`\sigma _i`$ is a top cell or a bottom cell.

* If $`\sigma _{i+1}`$ is a bottom cell, then define $`𝒢_{i+1}=𝒢_i`$, define $`\alpha _{i+1}=\varphi _i^1(\sigma _{i+1})`$ and define $`\varphi _{i+1}`$ as the restriction of $`\varphi _i`$ to $`\alpha _{i+1}`$.
* If $`\sigma _i`$ is a top cell, then define let $`\alpha _{i+1}`$ be a copy of $`\sigma _{i+1}`$, let $`\varphi _{i+1}:\alpha _{i+1}\sigma _{i+1}`$ be an isometry between the two, and let $`𝒢_{i+1}`$ be the complex formed by gluing $`𝒢_i`$ to $`\alpha _{i+1}`$ along their distinguished faces isometric to $`\sigma _i`$. Specifically identify $`\varphi _{i+1}^1(\sigma _i)\alpha _{i+1}`$ with $`\alpha _i𝒢_i`$ in the obvious fashion. Note that when $`𝒢_i`$ is viewed as a subcomplex of $`𝒢_{i+1}`$, $`\varphi _{i+1}`$ is an extension of $`\varphi _i`$.

The linear gallery $`𝒢`$ is simply the final complex $`𝒢_k`$. The cells $`\alpha _1`$ and $`\alpha _k`$ in $`𝒢`$ are the *endcells* of $`𝒢`$. The *interior of $`𝒢`$*, denoted $`𝒢^{}`$, is the union of the *open* cells $`\alpha _i`$, $`i=1,\mathrm{},k`$ in $`𝒢`$. The *boundary of $`𝒢`$*, denoted $`𝒢`$, is the open cells in $`𝒢`$ which are not in the interior. Notice that since the various maps $`\varphi _i`$ are compatible on their overlaps, the gallery $`𝒢`$ comes equipped with a map $`\varphi :𝒢K`$ which is an isometry when restricted to any of the closed cells of $`𝒢`$.

###### Example 3.2.

Let $`K`$ be the $`2`$-dimensional $`𝔼`$-complex formed by attaching the boundaries of two regular Euclidean tetrahedra along a $`1`$-cell. The complex $`K`$ is shown in the upper left corner of Figure 1. Let $`\gamma `$ be the geodesic shown which starts at $`x`$ travels across the front of $`K`$, around the back, over the top, and ends at $`y`$. The gallery determined by $`\gamma `$ in shown in the upper right corner, its interior in the lower left corner and its boundary in the lower right of Figure 1.

###### Definition 3.3 (Circular Galleries).

Let $`K`$ be a $`M_\kappa `$-complex, let $`\gamma :C_{\mathrm{}}K`$ be a closed piecewise geodesic in $`K`$, let $`k`$ is the size of $`\gamma `$, and let $`\{\sigma _i^{}\}_{i=1}^k`$ be the sequence of open cells that $`\gamma `$ passes through. Finally, assume that for all $`1ik`$, $`\sigma _i`$ is either a common face of both $`\sigma _{i+1}`$ and $`\sigma _{i1}`$ which are distinct or else both of these are incompatible faces of $`\sigma _i`$ where the subscripts are interpreted $`modk`$.. In the former case, we say that $`\sigma _i`$ is a *bottom cell*, and in the latter $`\sigma _i`$ is an *top cell* in the sequence.

As in Definition 3.1, the *circular gallery $`𝒢`$ determined by $`\gamma `$* is constructed inductively from the sequence of open cells that $`\gamma `$ passes through. Let $`a`$ be an arbitrary point in $`C_{\mathrm{}}`$, say one whose image lies in $`\sigma _1^{}`$. If we cut the circle at $`a`$ we obtain a path $`\gamma ^{}`$ of length $`\mathrm{}`$ in $`K`$ which is a piecewise geodesic and which happens to start and end at the same point, $`\gamma ^{}(a)`$. Next, we construct a linear gallery $`𝒢^{}`$ for the path $`\gamma ^{}`$ as above. Finally, we identify the endcells of $`𝒢^{}`$ to form the circular gallery $`𝒢`$.

It should be clear that the end result is independent of the choice of $`a`$, and that the circular gallery $`𝒢`$ comes equipped with a map $`\varphi :𝒢K`$ which is an isometry when restricted to any of the cells of $`𝒢`$.

###### Definition 3.4 (Galleries in complexes).

Let $`K`$ be a $`M_\kappa `$-complex with only finitely many shapes. A complex $`𝒢`$ with a map $`\varphi :𝒢K`$ will be called a *linear gallery in $`K`$* if there is a piecewise geodesic $`\gamma `$ satisfying the necessary restrictions which determines $`𝒢`$ and $`\varphi `$. A *circular gallery in $`K`$* is defined analogously. We should note that when we speak of a linear gallery $`𝒢`$ in $`K`$, we implicitly assume that $`𝒢`$ has a specified pair of endcells, $`\sigma `$ and $`\tau `$, and a specified map $`\varphi :𝒢K`$. From this information we can recover the interior $`𝒢^{}`$ and the linear ordering on the open cells in $`𝒢^{}`$. Similarly, when we speak of a circular gallery $`𝒢`$ in $`K`$, we implicitly assume that $`𝒢`$ has a specified map $`\varphi :𝒢K`$. From $`𝒢`$ we can reconstruct its interior $`𝒢^{}`$ and the circular ordering of open cells in $`𝒢^{}`$.

###### Remark 3.5 (Recognizing Galleries).

Let $`\varphi :𝒢K`$ be map from a finite complex to $`K`$ which is an isometry when restricted to a closed cell of $`𝒢`$, and let $`\sigma `$ and $`\tau `$ be two distinguished closed cells in $`𝒢`$. It is easy to determine whether $`𝒢`$ is a linear gallery with endcells $`\sigma `$ and $`\tau `$ as determined by some piecewise geodesic in $`K`$. If $`𝒢`$ is a gallery, then the maximal cells in the face lattice of $`𝒢`$ are the top cells of the gallery. There needs to exist an ordering of these cells so that adjacent top cells have non-trivial intersections. These intersections are the bottom cells. If $`\sigma `$ or $`\tau `$ is not in the list of top cells then the cells containing them are also bottom cells. At this point, we simply check whether the two bottom cells adjacent to a top cell are incompatible. If all of these conditions are true, then $`𝒢`$ is a gallery determined by some piecewise geodesic. Since there are only finitely many maximal cells in $`𝒢`$ and only finitely many linear ordering on this set, we can check all of the possibilities. A similar procedure will determine whether a map $`\varphi :𝒢K`$ from a finite complex to $`K`$ which is an isometry when restricted to a closed cell of $`𝒢`$ is a circular gallery determined by some closed piecewise geodesic.

###### Lemma 3.6.

Let $`K`$ be an $`M_\kappa `$-complex and let $`\varphi :𝒢K`$ be the linear gallery determined by a piecewise geodesic $`\gamma :[0,\mathrm{}]K`$. The map $`\gamma `$ lifts through $`\varphi `$ in the sense that there is path $`\gamma ^{}:[0,\mathrm{}]𝒢`$ with $`\gamma =\varphi \gamma ^{}`$. Moreover, $`\gamma ^{}`$ is a piecewise geodesic in $`𝒢`$ which starts in the one endcell of $`𝒢`$, ends in the other, and passes monotonically through the open cells in $`𝒢^{}`$.

###### Proof.

The notation of Definition 3.1 will be used without comment. Partition the path $`\gamma `$ into open, closed and half-open subintervals so that the $`i`$-th subinterval is sent to the $`i`$-th open cell, $`\sigma _i^{}`$, in $`K`$ that $`\gamma `$ passes through. If $`\sigma _i`$ is a top cell, then it contains the adjacent bottom cells in its boundary and thus $`\sigma _i`$ contains the images of the $`(i1)`$-st and the $`(i+1)`$-st subintervals if they exist. Thus all three subintervals can be simultaneously lifted to $`\alpha _i𝒢^{}`$ via the isometry $`\varphi _i^1`$. Since these lifts agree on the bottom cells where they overlap, they combine to form the required path $`\gamma ^{}`$. The second assertion is immediate from the definition of $`𝒢`$. ∎

###### Remark 3.7 (Geodesics in galleries).

Note that several piecewise geodesics may determine the same linear gallery $`𝒢`$ in $`K`$. If $`\gamma `$ is one of these paths which determine $`𝒢`$, then we say that $`𝒢`$ *contains* $`\gamma `$. Notice in particular that if $`𝒢`$ contains $`\gamma `$, then the lift $`\gamma ^{}`$ of $`\gamma `$ to $`𝒢`$ will be a piecewise geodesic in $`𝒢^{}`$ which starts in one endcell of $`𝒢`$, ends in the other endcell of $`𝒢`$ and which progresses monotonically from one endcell to the other. Conversely given a piecewise geodesic $`\gamma ^{}`$ in $`𝒢`$ satisfying these restrictions, it is easy to see that its $`\varphi `$-image in $`K`$ will be a piecewise geodesic $`\gamma `$ which determines $`𝒢`$.

###### Lemma 3.8.

Let $`K`$ be an $`M_\kappa `$-complex, and let $`\varphi :𝒢K`$ be either the linear gallery determined by a geodesic $`\gamma :[0,\mathrm{}]K`$, or the circular gallery determined by a closed geodesic $`\gamma :C_{\mathrm{}}K`$. If $`\gamma ^{}`$ is the lift of $`\gamma `$ to $`𝒢`$ and $`\alpha _i^{}`$ is an open cell in $`𝒢^{}`$, then the inverse image of $`\alpha _i^{}`$ under $`\gamma ^{}`$ is a closed subinterval of $`[0,\mathrm{}]`$ or $`C_{\mathrm{}}`$ when $`\alpha _i`$ is a bottom cell and an open subinterval when $`\alpha _i`$ is a top cell.

###### Proof.

Notice that $`\alpha _i^{}`$ is a closed subspace of $`𝒢^{}`$ when $`\alpha _i`$ is a bottom cell in $`𝒢`$ and an open subspace when $`\alpha _i`$ is a top cell in $`𝒢`$. Thus the preimage of $`\alpha _i^{}`$ is a closed \[respectively open\] subspace of $`[0,\mathrm{}]`$ or $`C_{\mathrm{}}`$ when $`\alpha _i`$ is a bottom \[top\] cell. Since $`\gamma ^{}`$ proceeds monotonically through the interiors of the $`\alpha _i`$ (Lemma 3.6), these open/closed subspaces can only be open/closed subintervals. ∎

###### Lemma 3.9.

Let $`K`$ be an $`M_\kappa `$-complex, and let $`\varphi :𝒢K`$ be either the linear gallery determined by a geodesic $`\gamma :[0,\mathrm{}]K`$, or the circular gallery determined by a closed geodesic $`\gamma :C_{\mathrm{}}K`$. If $`\gamma ^{}`$ is the lift of $`\gamma `$ to $`𝒢`$ and $`\alpha `$ is a bottom cell in $`𝒢`$, then the inverse image of $`\alpha ^{}`$ under $`\gamma ^{}`$ is a single point. The same is true for circular gallery.

###### Proof.

If $`\alpha `$ is a bottom cell whose preimage under $`\gamma ^{}`$ is not a single point, then by considering $`\alpha `$ and an adjacent top cell, it is easy to see that $`\gamma ^{}`$ (and hence $`\gamma `$) is not a local geodesic. This shows that preimages of the interiors of bottom cells must be single points. ∎

###### Lemma 3.10.

Let $`K`$ be an $`M_\kappa `$-complex and let $`\varphi :𝒢K`$ be the linear gallery determined by a geodesic $`\gamma :[0,\mathrm{}]K`$. If $`\gamma ^{}`$ is the lift of $`\gamma `$ to $`𝒢`$, and $`L=\{0=x_0<x_1<\mathrm{}<x_k=\mathrm{}\}[0,\mathrm{}]`$ is the list of point preimages of bottom cells under $`\gamma ^{}`$ together with the endpoints of the the interval, then the image of $`\gamma ^{}`$ in $`𝒢`$ is completely determined by the images of the points in $`L`$. Moreover, $`\gamma ^{}`$ is an embedding.

###### Proof.

If $`\alpha `$ denotes a top cell in $`𝒢`$, then the preimage of $`\alpha `$ under $`\gamma ^{}`$ is an closed subinterval $`[x_i,x_{i+1}]`$ for some $`i`$ (Lemma 3.8 and Lemma 3.9). Since $`\gamma ^{}`$ is a local geodesic, and since the image of this subinterval lies completely in the closed cell $`\alpha `$, this image must be the unique geodesic in $`\alpha `$ connecting $`\gamma ^{}(x_i)`$ to $`\gamma ^{}(x_{i+1})`$. This shows that $`\gamma ^{}`$ is an embedding and that it image is completely determined by the image of $`L`$ in $`𝒢`$ as required. ∎

###### Lemma 3.11.

Let $`K`$ be an $`M_\kappa `$-complex and let $`\varphi :𝒢K`$ be the circular gallery determined by a closed geodesic $`\gamma :C_{\mathrm{}}K`$. If $`\gamma ^{}`$ is the lift of $`\gamma `$ to $`𝒢`$, and $`L=\{0x_0<x_1<\mathrm{}<x_k<\mathrm{}\}[0,\mathrm{})`$ is the list of point preimages of bottom cells under $`\gamma ^{}`$, then the image of $`\gamma ^{}`$ in $`𝒢`$ is completely determined by the images of the points in $`L`$. Moreover, $`\gamma ^{}`$ is an embedding.

###### Proof.

If $`\alpha `$ denotes a top cell in $`𝒢`$, then the preimage of $`\alpha `$ under $`\gamma ^{}`$ is an closed subinterval $`[x_i,x_{i+1}]`$ for some $`i`$, or $`[x_k,x_0+\mathrm{}]`$ (Lemma 3.8 and Lemma 3.9). Since $`\gamma ^{}`$ is a local geodesic, and since the image of this subinterval lies completely in the closed cell $`\alpha `$, this image must be the unique geodesic in $`\alpha `$ connecting $`\gamma ^{}(x_i)`$ to $`\gamma ^{}(x_{i+1})`$. This shows that $`\gamma ^{}`$ is an embedding and that it image is completely determined by the image of $`L`$ in $`𝒢`$ as required. ∎

###### Lemma 3.12.

Let $`K`$ be an $`M_\kappa `$-complex, let $`\varphi :𝒢K`$ be the linear gallery determined by a piecewise geodesic $`\gamma :[0,\mathrm{}]K`$, and let $`\gamma ^{}:[0,\mathrm{}]𝒢`$ be the lift of $`\gamma `$ to $`𝒢`$. The map $`\varphi `$ restricted to $`𝒢^{}`$ is an immersion.

###### Proof.

Let $`𝒢`$ be the linear gallery determined by a geodesic $`\gamma `$ and let $`\varphi :𝒢K`$ be canonical map. The map $`\varphi `$ is clearly an embedding when restricted to each closed cell $`\alpha _i`$ in $`𝒢`$. For a point $`x`$ in the interior of a top cell of $`𝒢`$, there is a neighborhood of $`x`$ which lies completely in $`\alpha _i^{}`$. Thus $`\varphi `$ is an embedding in a neighborhood of $`x`$. If $`x`$ is a point in the interior of a bottom cell $`\alpha _i`$ (which is not an endcell of $`𝒢`$), then there is a neighborhood of $`x`$ which lies in $`(\alpha _{i1}_{\alpha _i}\alpha _{i+1})𝒢^{}`$. The restrictions on $`\gamma `$ now ensure that $`\varphi `$ is an embedding when restricted to this subcomplex. Finally, when $`\alpha _i`$ is a bottom cell which is an endcell, there is neighborhood of $`x`$ which lies in either $`\alpha _{i+1}𝒢^{}`$ or $`\alpha _{i1}𝒢^{}`$. ∎

###### Lemma 3.13.

Let $`K`$ be an $`M_\kappa `$-complex, let $`\varphi :𝒢K`$ be the linear $`[`$or circular$`]`$ gallery determined by a local $`[`$closed$`]`$ geodesic $`\gamma :[0,\mathrm{}]K`$, and let $`\gamma ^{}:[0,\mathrm{}]𝒢`$ be the lift of $`\gamma `$ to $`𝒢`$. There exists a deformation retraction from $`𝒢^{}`$ to the image of $`\gamma ^{}`$.

###### Proof.

To prove there is a deformation retraction from $`𝒢`$ to $`\gamma ^{}`$ we first note that for each bottom cell of $`𝒢`$, we can use a radial retraction from $`\alpha _i^{}`$ to the unique point where $`\gamma ^{}`$ intersects $`\alpha _i^{}`$ (Lemma 3.9). Next for each top cell $`\alpha _i`$ there are two points which determine the intersection of $`\gamma ^{}`$ with $`\alpha _i`$. These two points are either the two endpoints of $`\gamma ^{}`$, an endpoint and a point in the interior of a boundary cell of $`\alpha _i`$, or two points in the interiors of two incompatible boundary cells of $`\alpha _i`$. In all three cases it is easy to see that there is a retraction of $`\alpha _i𝒢^{}`$ which is compatible with the deformations already defined on the interiors of the boundary cell(s) of $`\alpha _i`$. ∎

###### Definition 3.14 (Equivalent galleries).

Let $`K`$ be an $`M_\kappa `$-complex and let $`𝒢`$ and $`𝒢^{}`$ be two of its galleries, both linear or both circular. The galleries $`𝒢`$ and $`𝒢^{}`$ will be considered *equivalent* if there is an isometry between them which preserves their cell structures. They will be considered *identical* if they are equivalent and they are immersed in $`K`$ in the same way. More specifically, if $`𝒢`$ and $`𝒢^{}`$ are immersed in $`K`$ by maps $`\varphi `$ and $`\varphi ^{}`$, then there is a map $`\rho :𝒢𝒢^{}`$ showing they are equivalent with $`\varphi =\varphi ^{}\rho `$.

###### Lemma 3.15.

Let $`K`$ be a $`M_\kappa `$-complex with $`\text{Shapes}(K)`$ finite, let $`\mathrm{}`$ be a fixed real number. If a number $`N`$ satisfying the conclusion of Theorem 1.11 can be constructed from $`\text{Shapes}(K)`$ and $`\mathrm{}`$, then there exists a finite, constructible list of linear galleries such that every geodesic in $`K`$ of length at most $`\mathrm{}`$ determines a gallery equivalent to a linear gallery in this list. There is a similar list of circular galleries such that every closed geodesic in $`K`$ of length at most $`\mathrm{}`$ determines a circular gallery equivalent to a gallery in this list.

###### Proof.

We prove the linear case; the circular case is analogous. Let $`\mathrm{\Gamma }`$ be the (infinite) collection of all geodesics in $`K`$ of length at most $`\mathrm{}`$. By Theorem 1.11 there is an $`N`$ such that each $`\gamma `$ in $`\mathrm{\Gamma }`$ passes through at most $`N`$ open cells of $`K`$. As a result each $`\gamma `$ in $`\mathrm{\Gamma }`$ determines a gallery formed by gluing together at most $`N`$ closed cells, each of which is isometric to a closed cell in $`\text{Shapes}(K)`$. Because $`\text{Shapes}(K)`$ is finite, there are only a finite number of complexes which can be formed in this way, and by Remark 3.5 we can determine which of these are linear galleries. The linear gallery determined by $`\gamma `$ must be equivalent to one of them. ∎

## 4. Detecting piecewise geodesics

In this section we discuss in detail how to search for piecewise geodesics of bounded length in a linear or circular gallery using boolean combinations of polynomial equations and inequalities.

###### Theorem 4.1.

If $`K`$ is finite $`n`$-dimensional $`𝕊`$-complex and $`𝒢`$ is a linear gallery in $`K`$, then we can construct a system of polynomial equations and inequalities which has a solution if and only if the gallery $`𝒢`$ contains a piecewise geodesic of length less than $`\pi `$. As a consequence, there exists an algorithm to test whether $`𝒢`$ contains such a piecewise geodesic.

###### Proof.

Let $`\gamma :[0,\mathrm{}]K`$ be a piecewise geodesic which is contained in $`𝒢`$, and let $`\gamma ^{}:[0,\mathrm{}]𝒢`$ be its lift to $`𝒢`$. For each bottom cell $`\alpha `$ in $`𝒢`$, let $`x_\alpha `$ be the smallest value in the preimage of $`\alpha ^{}`$ under $`\gamma ^{}`$. Such a value exists by Lemma 3.8. Clearly the ordering of the $`x_\alpha `$ is consistent with the linear ordering of the bottom cells in $`𝒢`$. Next, define a list $`L=\{0=x_0<x_1<\mathrm{}<x_k=\mathrm{}\}[0,\mathrm{}]`$ which consists endpoints of the domain together with the collection of $`x_\alpha `$ defined above. Let $`\alpha _1^{}`$ and $`\alpha _k^{}`$ denote the open cells of $`𝒢`$ containing $`\gamma ^{}(0)`$ and $`\gamma ^{}(\mathrm{})`$ and let $`\alpha _i^{}`$, $`1<i<k`$ denote the open bottom cell of $`𝒢`$ containing $`\gamma ^{}(x_i)`$.

If there is an $`i`$ such that $`\gamma ^{}`$ does not send this subinterval $`[x_i,x_{i+1}]`$ to the unique geodesic connecting $`\gamma ^{}(x_i)`$ and $`\gamma ^{}(x_{i+1})`$ in the unique top cell containing both points, then we can define a new path $`\gamma ^{\prime \prime }`$ with this property which determines the same list $`L`$, but with a strictly shorter length. Thus, if $`𝒢`$ contains a path of length less than $`\pi `$, it contains a path of this type. We may therefore assume that $`\gamma ^{}`$ has this shortest geodesic property for each $`i`$, and as a result that $`\gamma ^{}`$ intersects each bottom cell of $`𝒢`$ in a unique point.

We now establish a system of equations and inequalities which will test whether the sum of the distances from $`x_i`$ to $`x_{i+1}`$, $`i=0,\mathrm{},k1`$ is less than $`\pi `$ or not. In one sense all we need to do is to add up the lengths of the unique individual arcs connecting $`\gamma ^{}(x_i)`$ to $`\gamma ^{}(x_{i+1})`$, but we wish to do this with polynomial equations. Let $`V`$ denote the set of $`0`$-cells in $`𝒢`$ and let $`E`$ denote the set of $`1`$-cells in $`𝒢`$. We will introduce the necessary variables and equations in three stages. The spaces and maps used are summarized in Figure 2.

Step 1: For every $`vV`$ we introduce a vector $`\stackrel{}{u}_v=(u_{v,1},\mathrm{},u_{v,n+1})`$ in $`^{n+1}`$ and we add the equation $`\stackrel{}{u}_v\stackrel{}{u}_v=1`$ to our system. In other words, we introduce $`n`$ new variables $`u_{v,i}`$, $`i=1,\mathrm{},n+1`$ and the polynomial equation $`u_{v,1}^2+u_{v,2}^2+\mathrm{}+u_{v,n+1}^2=1`$. The vector notation is simply a convenient shorthand. Next, for each $`1`$-cell $`eE`$ connecting $`v`$ to $`v^{}`$ we add the equation $`\stackrel{}{u}_v\stackrel{}{u}_v^{}=\mathrm{cos}(\theta )`$ to our system, where $`\theta `$ is the arc length of $`e`$. Notice that the solutions to this system of equations defined so far are in one-to-one correspondence with the possible maps from $`𝒢`$ to $`𝕊^n`$ which restrict to an isometry on each closed cell of $`𝒢`$.

Step 2: For each $`x_i`$ in $`L`$, we introduce a vector $`\stackrel{}{y}_i=(y_{i,1},\mathrm{},y_{i,n+1})`$, and add the equation $`\stackrel{}{y}_i\stackrel{}{y}_i=1`$ which stipulates that $`\stackrel{}{y}_i`$ has length $`1`$. In addition, we add equations and inequalites which stipulate that $`\stackrel{}{y}_i`$ is a positive linear combination of the vectors $`\stackrel{}{u}_v`$ corresponding to the $`0`$-cells $`v`$ of $`\alpha _i`$. When $`\alpha _i`$ is $`0`$-dimensional the positive linear combination will reduce to a set of equations of the form $`\stackrel{}{y}_i=\stackrel{}{u}_v`$.

Notice that we are treating the position of $`\gamma (x_i)`$ in $`\alpha _i^{}`$ as unspecified. For example, if the start point $`\gamma (x)`$ lies in a $`1`$-cell $`e`$ in $`𝒢`$ with $`0`$-cells $`v`$ and $`v^{}`$, then the equations added so far only state that the image of the endpoint $`x`$, $`\stackrel{}{y}_1`$, is a positive linear combination of the vectors $`\stackrel{}{u}_v`$ and $`\stackrel{}{u}_v^{}`$. They do not state what coefficients of that positive linear combination are. The variables and equations in steps $`1`$ and $`2`$ ensure that encoded in each solution to these system is the description of a distinct piecewise geodesic path between the endcells of $`𝒢`$.

Step 3: To check whether the total length of $`\gamma ^{}`$ is at least $`\pi `$, we use a $`2`$-dimensional model space. For each point $`x_i`$ in $`L`$ we introduce a new vector $`\stackrel{}{z}_i=(z_{i,1},z_{i,2})`$ in $`^2`$ starting with $`\stackrel{}{z}_0=(0,1)`$. Then we add the following equations:

$$\begin{array}{cccc}\hfill \stackrel{}{z}_i\stackrel{}{z}_i& =& 1,\hfill & \text{ for }i=0,1,\mathrm{},k\hfill \\ \hfill \stackrel{}{z}_{i1}\stackrel{}{z}_i& =& \stackrel{}{y}_{i1}\stackrel{}{y}_i,\hfill & \text{ for }i=1,\mathrm{},k\hfill \\ \hfill det(\stackrel{}{z}_{i1},\stackrel{}{z}_i)& >& 0,\hfill & \text{ for }i=1,\mathrm{},k\hfill \end{array}$$

These equations stipulate that the length of $`\stackrel{}{z}_i`$ is $`1`$, that the angle between $`\stackrel{}{z}_i`$ and $`\stackrel{}{z}_{i+1}`$ equals the angle between $`\stackrel{}{y}_i`$ and $`\stackrel{}{y}_{i+1}`$, and that $`(\stackrel{}{z}_i,\stackrel{}{z}_{i+1})`$ is a positively oriented frame for $`^2`$. The third set of equations has this interpretation because the cells of $`𝒢`$ are proper and thus all distances in these cells are less than $`\pi `$. Taken together, the second and third sets of equations ensure that $`\stackrel{}{z}_i`$ is obtained from $`\stackrel{}{z}_{i1}`$ by a counterclockwise rotation through an angle equal to the distance from $`\gamma (x_{i1})`$ to $`\gamma (x_i)`$ in $`𝒢`$. In other words the points $`\stackrel{}{z}_0`$, $`\stackrel{}{z}_1`$, etc. are marching around the unit circle in $`^2`$ in a counterclockwise direction starting on the positive $`x`$-axis.

Step 4: Finally, since each angle is less than $`\pi `$, the length of the geodesic will be less than $`\pi `$ if and only if each $`\stackrel{}{z}_i`$, $`i>0`$, has a positive second coordinate. Thus we add the equations $`z_{i,2}>0`$, for $`i=1,\mathrm{},k`$.

Combining all of the variables and equations introduced in each of these steps, we get a system of equations and inequalities which has a solution if and only if $`𝒢`$ contains a piecewise geodesic of length less than $`\pi `$. The second assertion follows immediately from Tarski’s theorem. ∎

###### Example 4.2.

To illustrate the procedure described in Theorem 4.1 consider the $`1`$-dimensional $`𝕊`$-complex on the left in Figure 3. The gallery determined by the sequence of points $`\{x,A,B,C,D,B,C,y\}`$ is shown on the right and the model space for this sequence is shown in Figure 4. The vectors in the model space are the vectors $`\stackrel{}{z}_i`$. In this example $`\stackrel{}{z}_6`$ and $`\stackrel{}{z}_7`$ have negative second coordinates, the total length is at least $`\pi `$, and thus this is not a solution to the system of equations and inequalities.

There is a similar theorem for circular galleries.

###### Theorem 4.3.

If $`K`$ is a finite $`n`$-dimensional $`𝕊`$-complex and $`𝒢`$ is a circular gallery in $`K`$, then we can construct a boolean combination of polynomial equations and inequalities which has a solution if and only if the gallery $`𝒢`$ contains a closed piecewise geodesic of length less than $`2\pi `$. As a consequence, there exists an algorithm to test whether $`𝒢`$ contains such a closed piecewise geodesic.

###### Proof.

The proof is nearly identical to the one above, so only the differences will be noted. We begin noting that the circular gallery $`𝒢`$ was constructed by first creating a linear gallery $`𝒢^{}`$ and then identifying the two endcells of $`𝒢^{}`$ by an isometry. We will need the unidentified linear gallery $`𝒢^{}`$ to create some of our equations. By picking a point in top cell as a basepoint of the loop, we may assume that the endcells of $`𝒢^{}`$ are top cells.

The notation is as before, but slightly modified since $`𝒢`$ is circular. There is a loop $`\gamma ^{}:C_{\mathrm{}}𝒢`$ and a path $`\gamma ^{\prime \prime }:[0,\mathrm{}]𝒢^{}`$. There is a list $`L=\{0<x_1<x_2<\mathrm{}<x_k<\mathrm{}\}[0,\mathrm{})`$ where the point $`\gamma ^{}(x_i)`$ is contained in the interior of a bottom cell of $`𝒢^{}`$ denoted $`\alpha _i`$. Moreover, $`\gamma ^{}`$ is a piecewise geodesic whose image is determined by the points $`\gamma ^{}(x_i)`$. Let $`V`$ denote the set of $`0`$-cells in $`𝒢^{}`$, let $`E`$ denote the set of $`1`$-cells in $`𝒢^{}`$.

Step 1: Same as above with $`𝒢`$ replaced by $`𝒢^{}`$. The solutions to this system of equations are in one-to-one correspondence with the possible maps from $`𝒢^{}`$ to $`𝕊^n`$ which restrict to an isometry on each closed cell of $`𝒢^{}`$.

Step 2: Same as above with the addition that since $`x_1`$ and $`x_k`$ are two preimages of the same point in $`𝒢`$, we add equations that state that each coefficient variable used to describe $`\stackrel{}{y}_0`$ as a positive linear combination of the vectors $`\stackrel{}{u}_v`$ corresponding to the $`0`$-cells in $`\alpha _1`$, is equal to the corresponding coefficient variable used to describe $`\stackrel{}{y}_k`$ as a positive linear combination of the vectors $`\stackrel{}{u}_v`$ corresponding to the $`0`$-cells in $`\alpha _k`$. The correspondence of the $`0`$-cells is determined by the isometry used to obtain $`𝒢`$ from $`𝒢^{}`$. The variables and equations in steps $`1`$ and $`2`$ ensure that encoded in any solution to the system so far is the description of a piecewise geodesic loop which travels monotonically around $`𝒢`$.

Step 3: Same as above.

Step 4: When we were checking length less than $`\pi `$ this only involved checking whether all the second coordinates were positive. This time the length calculation should determine whether the length is less than $`2\pi `$ which is more involved. For each $`i=2,\mathrm{},k1`$ add new variables $`p_i`$ and $`q_i`$ and equations of the form

$$\begin{array}{c}p_i\stackrel{}{z}_i+q_i\stackrel{}{z}_{i+1}=\stackrel{}{z}_1\\ p_i<0\text{ or }q_i<0\end{array}$$

This is just a polynomial way of saying that $`\stackrel{}{z}_1`$ is not a nonnegative linear combination of $`\stackrel{}{z}_i`$ and $`\stackrel{}{z}_{i+1}`$ (which ensures that the total length is less than $`2\pi `$). To see this note that if $`z_{i+1}`$ ever comes back around the full circle in this model space, then $`z_1`$ will be a nonnegative linear combination of $`z_i`$ and $`z_{i+1}`$, $`i>1`$.

Combining all of the variables and equations introduced in each of these steps, we get a boolean combination of polynomial equations and inequalities which has a solution if and only if $`𝒢`$ contains a piecewise geodesic loop of length less than $`2\pi `$. The second assertion follows immediately from Tarski’s theorem. ∎

###### Remark 4.4 (Coefficients).

The only equations in these systems with potentially non-rational coefficients are the equations of the form $`\stackrel{}{u}_v\stackrel{}{u}_v^{}=\mathrm{cos}(\theta )`$. Such an equation can be rewritten as the equation $`(\stackrel{}{u}_v\stackrel{}{u}_v^{})^2=\mathrm{cos}^2(\theta )`$, and an inequality stipulating that $`\stackrel{}{u}_v\stackrel{}{u}_v^{}`$ has the appropriate sign. Thus, if $`\mathrm{cos}(\theta )`$ is at worst a square root of a rational number, using this alternative ensures the systems use only rational coefficients. Such considerations can play a significant role when implementing algorithms, and we will explore the issue of coefficients in greater detail in Section 6.

## 5. Detecting local geodesics

In this section we discuss how to search for local geodesics of bounded length in a linear or circular gallery using boolean combinations of polynomial equations and inequalities. The requirement that the paths be local geodesics instead of merely piecewise geodesics is the main complication. In the process we show how to bound the length of a linear gallery which can contain a short geodesic. The results in this section will be proved by induction on $`n`$. We begin with dimension $`n=1`$.

###### Theorem 5.1.

If $`K`$ is a finite $`n`$-dimensional $`𝕊`$-complex and $`𝒢`$ is a linear gallery in $`K`$, then there exists a boolean combination of polynomial equations and inequalities which has a solution if and only if $`𝒢`$ contains a local geodesic of length less than $`\pi `$ whose image in $`K`$ is also a geodesic. As a consequence there exists an algorithm which determines whether or not $`𝒢`$ contains such a geodesic.

###### Proof.

When $`n=1`$, the system created is the one created in the proof of Theorem 4.1. Because $`K`$ and hence $`𝒢`$ have dimension $`1`$, the piecewise geodesics encoded in a solution to this system will be precisely the local geodesics contained in $`𝒢`$, and they will also remain local geodesics when immersed into $`K`$.

For $`n>1`$, we may assume that results in this section have already been proved in lower dimensions. Let $`P`$ denote the system created in the proof of Theorem 4.1. In essence, we will start with $`P`$ and then add restrictions to require that any piecewise geodesics encoded in a solution to $`P`$ will be locally geodesic at the transitions between the geodesic pieces. We will use the notations established in the proof of Theorem 4.1 without further comment.

Let $`\alpha _i`$ be a bottom cell of $`𝒢`$. Given any two points $`a`$ and $`b`$ in $`\alpha _i^{}`$, the links $`\text{link}(\varphi (a),K)`$ and $`\text{link}(\varphi (b),K)`$ are canonically isometric. Let $`L_i`$ be this well-defined $`𝕊`$-complex and note that its dimension is strictly less than $`n`$. In general the cells in $`L_i`$ will not be proper so we assume that it has been suitably subdivided. Notice that the three points $`\gamma (x_{i1})`$, $`\gamma (x_i)`$ and $`\gamma (x_{i+1})`$ determine two points in $`L_i`$. The complex $`L_i`$ will have a finite number of galleries which could possibly contain a geodesic of length less than $`\pi `$ by Lemma 5.6. Let $`G_i`$ be the list of such galleries in $`L_i`$. For each gallery in $`G_i`$ we write down the variables and equations necessary to the encode a generic path determined by crossing points into the gallery (this would be steps $`1`$ and $`2`$ in Theorem 4.1). Do this for each gallery in $`G_i`$ and repeat this procedure for each of the links $`L_i`$. Each gallery in each link will use distinct variables.

For each $`i`$ and for each gallery $`_j`$ in $`G_i`$, we create a system $`V_{i,j}`$ which is a boolean combination of polynomial equations and inequalities. First we create the equations and inequalities needed to say that the three points $`\gamma (x_{i1})`$, $`\gamma (x_i)`$ and $`\gamma (x_{i+1})`$ determine two points in $`L_i`$ which lie in the endcells of $`_j`$. Then we add the boolean combination of polynomial equations and inequalities (which exist by the lower-dimensional versions of this theorem) which have a solution if and only if there is a local geodesic in $`_j`$ connecting these exact points in its endcells.

Intuitively, the system $`V_{i,j}`$ has a solution if and only if the the piecewise geodesic in $`𝒢`$ which is encoded in a solution of the system $`P`$, there is a path less than $`\pi `$ contained in the gallery $`_j`$ in the link of the point $`\gamma (x_i)`$ pushed into $`K`$. More informally, we might say that the solutions to $`V_{i,j}`$ encode the piecewise geodesics in $`𝒢`$ which have a “kink” at $`\varphi (\gamma (x_i))`$ as witnessed by a short path through gallery $`_j`$.

The final system is one which starts with $`P`$ and subtracts off the solutions to each of the $`V_{i,j}`$. Clearly, this is a boolean combination of these solution sets. This final system will have a solution if and only if $`𝒢`$ contains a piecewise geodesic of length less than $`\pi `$ which does not fail to be locally geodesic in any of the finite number of possible ways which are available to it. In other words, if and only if $`𝒢`$ contains a local geodesic of length less than $`\pi `$. Finally, the algorithmic assertion follows immediately from Tarski’s Theorem. ∎

There is a similar theorem for circular galleries.

###### Theorem 5.2.

If $`K`$ is a finite $`n`$-dimensional $`𝕊`$-complex and $`𝒢`$ is a circular gallery in $`K`$, then there exists a boolean combination of polynomial equations and inequalities which has a solution if and only if $`𝒢`$ contains a local geodesic of length less than $`2\pi `$ whose image in $`K`$ is also a local geodesic. As a consequence there exists an algorithm which determines whether or not $`𝒢`$ contains such a geodesic.

###### Proof.

The proof is identical to the one above, but starting with the system created in the proof of Theorem 4.3. Everything else is unchanged. ∎

Next, we show how to construct the number $`N`$ in dimension $`n`$.

###### Lemma 5.3.

If $`K`$ be a $`n`$-dimensional $`𝕊`$-complex with finitely many shapes and $`\mathrm{}>0`$ is a real number, then there is an algorithm which computes an integer $`N`$ such that every local geodesic contained in a linear geodesic $`𝒢`$ of size $`N`$ in $`K`$ has length at least $`\mathrm{}`$.

###### Proof.

Note that Theorem 5.1 shows that it is possible to determine whether any specific linear gallery $`𝒢`$ contains a local geodesic of length less than $`\pi `$. To find the smallest value of $`N`$ which will work for $`\mathrm{}=\pi `$ we simply test a representative of each equivalence class of galleries of size $`1`$, then a representative of each equivalence class of galleries of size $`2`$, etc. That there is a finite constructible list of such galleries is guaranteed by Lemma 3.15. As soon as we find an $`N`$ such that all galleries of size $`N`$ do not contain a local geodesic of less than length $`\pi `$, we are essentially done since by Remark 1.12 it is sufficient to find $`N`$ for a single number $`\mathrm{}`$. That such an $`N`$ must exist follows from Theorem 1.11 and the fact that local geodesics contained in linear galleries of size $`N`$ themselves have size $`N`$. Note that we are using the fact that geodesics “contained in” $`𝒢`$ remain in the interior of the gallery (Remark 3.7). A geodesic between the endcells of $`𝒢`$ which is allowed to contain points from the boundary of $`𝒢`$ may very well have a smaller size. ∎

Now that we have shown that the $`N`$ in Theorem 1.11 is constructible, we can state the following corollaries.

###### Corollary 5.4.

Let $`K`$ be a finite $`n`$-dimensional $`𝕊`$-complex and let $`\mathrm{}`$ be a fixed real number. Given open cells $`\sigma ^{}`$ and $`\tau ^{}`$ in $`K`$ there is a finite, constructible list of linear galleries from $`\sigma `$ to $`\tau `$, based only on $`\text{Shapes}(K)`$ and $`\mathrm{}`$, such that every geodesic from $`\sigma `$ to $`\tau `$ of length at most $`\mathrm{}`$ determines a gallery in this list.

###### Proof.

Let $`N`$ be a size which guarantees a length greater than $`\mathrm{}`$ and then construct all possible linear galleries with size at most $`N`$ up to equivalence (Lemma 3.15), and then construct all possible maps from $`𝒢`$ to $`K`$ starting at $`\sigma `$. This is possible since $`N`$ exists (Theorem 1.11), it is constructible (Lemma 5.3), and $`K`$ is locally-finite. ∎

###### Corollary 5.5.

Let $`K`$ be a finite $`n`$-dimensional $`𝕊`$-complex and let $`\mathrm{}`$ be a fixed real number. There is a finite, constructible list of circular galleries such that every closed geodesic of length at most $`\mathrm{}`$ determines a circular gallery in this list.

###### Proof.

Let $`N`$ be a size which guarantees a length greater than $`\mathrm{}`$ and then construct all possible circular galleries $`𝒢`$ with size at most $`N`$ up to equivalence (Lemma 3.15), and then construct all possible maps from $`𝒢`$ to $`K`$. This is possible since $`N`$ exists (Theorem 1.11), it is constructible (Lemma 5.3), and $`K`$ is locally finite. ∎

Finally, we prove a lemma to complete the induction.

###### Lemma 5.6.

Let $`K`$ be a finite $`n`$-dimensional $`𝕊`$-complex. Given open cells $`\sigma ^{}`$ and $`\tau ^{}`$ in $`K`$, there exists a boolean combination of polynomial equations and inequalities which has a solution if and only if there is a geodesic in $`K`$ from some point in $`\sigma ^{}`$ to some point in $`\tau ^{}`$ of length less than $`\pi `$. A similar statement holds when the points in $`\sigma ^{}`$ and $`\tau ^{}`$ are specified.

###### Proof.

First note that any such geodesic determines a linear gallery. By Corollary 5.4 we can construct a finite list $`L`$ which contains all linear galleries $`𝒢K`$ from $`\sigma `$ to $`\tau `$ which could possibly be determined by a geodesic of length less than $`\pi `$. For each gallery in $`L`$, use Theorem 5.1 to create a system of polynomial equations which has a solution if and only if this particular gallery does not contain a piecewise geodesic of length less than $`\pi `$. If each of these systems are created using distinct variables, then their union will be a finite system which has a solution if and only if there does not exist a path in $`K`$ from $`\sigma ^{}`$ to $`\tau ^{}`$ of length less than $`\pi `$. ∎

## 6. Coefficients

The results in this section are a slight digression. Let $`K`$ be a finite $`n`$-dimensional $`𝔼`$-complex. In this section we show that the type of numbers which show up as coefficients of the polynomials used to test whether $`K`$ is locally $`\text{CAT}(0)`$ are no worse than the types of numbers which show up as lengths of $`1`$-cells in $`K`$. A precise version of this claim is contained in Theorem 6.6 where it is presented in terms of $`F`$-simplices.

###### Definition 6.1 ($`F`$-simplices).

Let $`F`$ be a subfield of $``$ and let $`\sigma `$ be $`n`$-dimensional Euclidean simplex. If the square of the length of each $`1`$-cell in $`\sigma `$ lies in $`F`$, then $`\sigma `$ is called an *$`F`$-simplex*.

###### Lemma 6.2.

Let $`F`$ be a subfield of $``$, let $`\sigma ^n`$ be an $`k`$-dimensional Euclidean simplex with vertices $`v_i`$, $`i=0,\mathrm{},k`$, and let $`\stackrel{}{v}_i`$ be the vector from $`v_0`$ to $`v_i`$. The following conditions are equivalent:

1. $`\sigma `$ is an $`F`$-simplex,
2. $`\stackrel{}{v}_i\stackrel{}{v}_jF`$ for all $`i,j`$,

###### Proof.

($`21`$) Since $`\stackrel{}{v}_i^2=\stackrel{}{v}_i\stackrel{}{v}_i`$ we conclude that the square of the length of the edge connecting $`v_0`$ to $`v_i`$ lies in $`F`$, and since

$$\stackrel{}{v}_j\stackrel{}{v}_i^2=(\stackrel{}{v}_j\stackrel{}{v}_i)(\stackrel{}{v}_j\stackrel{}{v}_i)=\stackrel{}{v}_i^2+\stackrel{}{v}_j^22\stackrel{}{v}_i\stackrel{}{v}_j$$

we conclude that square of the length of the edge connecting $`v_i`$ to $`v_j`$, $`i,j>0`$, lies in $`F`$ as well. ($`12`$) Since the square of the length of the edge connecting $`v_0`$ to $`v_i`$ is $`\stackrel{}{v}_i^2=\stackrel{}{v}_i\stackrel{}{v}_i`$, we conclude that $`\stackrel{}{v}_i\stackrel{}{v}_j`$ lies in $`F`$ when $`i=j`$. Similarly, the square of the length of the edge connecting $`v_i`$ to $`v_j`$ is $`\stackrel{}{v}_j\stackrel{}{v}_i^2=\stackrel{}{v}_i^2+\stackrel{}{v}_j^22\stackrel{}{v}_i\stackrel{}{v}_j`$. Since this result lies in $`F`$, $`2`$ is in $`F`$, and the first two of its terms lies in $`F`$ by assumption, we conclude that $`\stackrel{}{v}_i\stackrel{}{v}_jF`$ for $`ij`$ as well. ∎

###### Lemma 6.3.

Let $`F`$ be a subfield of $``$ and let $`\sigma ^n`$ be an $`k`$-dimensional $`F`$-simplex with one vertex, $`v_0`$, at the origin. There is an orthogonal basis $`U`$ of $`^n`$ such that the squared length of each basis vector in $`U`$ lies in $`F`$ and all of the coordinates of all of the vertices of $`\sigma `$, relative to $`U`$, lies in $`F`$.

###### Proof.

By replacing $`^n`$ with the subspace spanned by the vectors $`\stackrel{}{v}_i`$ if necessary, we may assume that $`k=n`$ and that collection of vectors $`V=\{\stackrel{}{v}_i\}_{i=1}^n`$ is a basis for $`^n`$. Next apply the Gramm-Schmidt process to $`V`$ without normalizing the final result. Specifically, let $`\stackrel{}{u}_1=\stackrel{}{v}_1`$, and for $`i>1`$ inductively define

$$\stackrel{}{u}_i=\stackrel{}{v}_i\underset{j=1}{\overset{i1}{}}\frac{\stackrel{}{v}_i\stackrel{}{u}_j}{\stackrel{}{u}_j\stackrel{}{u}_j}\stackrel{}{u}_j.$$

An easy induction shows that $`\stackrel{}{u}_i`$ is an $`F`$-linear combination of the vectors $`\stackrel{}{v}_j`$, $`ji`$ so that the fraction in front of the vector $`\stackrel{}{u}_j`$ in the above equation is an element of $`F`$. In particular, the change of basis matrix connecting $`U`$ and $`V`$ is an upper triangular matrix over $`F`$ with $`1`$’s down the diagonal. As a result, the same is true about the change of basis matrix going in the other direction, thus showing that each $`\stackrel{}{v}_i`$ is an $`F`$-linear combination of the vectors $`\stackrel{}{u}_j`$ with $`ji`$. ∎

###### Lemma 6.4.

If $`F`$ be a subfield of $``$ and $`\sigma `$ is a $`F`$-simplex, then the square of each trigonometric function of each dihedral angle in $`\sigma `$ lies in $`F`$.

###### Proof.

First note that it is sufficient to prove this for the square of the cosine of such an angle. Let $`V=\{v_0,\mathrm{},v_k\}`$ be the set of vertices of $`\sigma `$. A dihedral angle between two faces of $`\sigma `$ is determined by a subset $`SV`$ and distinct $`s,tVS`$. In particular, there is a dihedral angle $`\theta `$ between the face determined by $`S\{s\}`$ and the face determined by $`S\{t\}`$. By renumbering if necessary we may assume that $`S=\{v_0,\mathrm{},v_{i1}\}`$, $`s=v_i`$, and $`t=v_{i+1}`$. Using the orthogonal basis $`U`$ derived in Lemma 6.3, it is clear that $`\mathrm{cos}^2(\theta )`$ lies in $`F`$. Specifically, $`\theta `$ is angle between the projections of $`vecv_i`$ and $`\stackrel{}{v}_{i+1}`$ into the subspace perpendicular to the subspace determined by $`S`$. In the basis $`U`$, this projection is accomplished by simply “zeroing out” the first $`i1`$ coordinates. As a result these projections are still $`F`$-linear combinations of the basis vectors. That $`\mathrm{cos}^2(\theta )`$ lies in $`F`$ now follows immediately. ∎

One special case which deserves to be highlighted is where the field $`F=`$. An angle $`\theta `$ for which $`\mathrm{cos}^2(\theta )`$ is rational is called *geodetic*. See  for a computational description of the space of geodetic angles.

###### Corollary 6.5.

If $`\sigma `$ be a Euclidean $``$-simplex, then every dihedral angle in $`\sigma `$ is geodetic.

Notice that $``$-simplices are quite common. For example, every simplex in a simplicial decomposition of a rational polytope will be a $``$-simplex.

###### Theorem 6.6 (Coefficients).

Let $`K`$ be a finite simplicial $`𝔼`$-complex and let $`F`$ be a subfield of $``$. If every simplex in $`K`$ is an $`F`$-simplex, then the systems of polynomial equations and inequalities used to test whether $`K`$ is locally $`\text{CAT}(0)`$ have coefficients which belong to $`F`$.

###### Proof.

As we mentioned in Remark 4.4, the only coefficients used which are not integers are equal to $`\mathrm{cos}^2(\theta )`$ for some dihedral angle $`\theta `$ in some simplex of $`K`$. But by Lemma 6.4, this number lies in $`F`$. ∎

Similar theorems could clearly be derived for other curvatures, but they will not be pursued here.

## 7. The Main Theorem

At this point the proof of Theorem B is nearly immediate.

###### Theorem 7.1.

There exists an algorithm which determines whether or not a finite $`𝕊`$-complex contains a closed geodesic of length less than $`2\pi `$, and as a consequence there exists an algorithm which determines whether or not a finite $`𝕊`$-complex is globally $`\text{CAT}(1)`$.

###### Proof.

A closed geodesic of length less than $`2\pi `$ in the complex would determine a circular gallery which contains it. By Corollary 5.5 there is a finite, constructible list of circular galleries in $`K`$ which could possibly contain a closed geodesic of length less than $`2\pi `$, and by Theorem 5.2 we can test each one for the presence of a short closed geodesic which survives in $`K`$. This proves the first assertion.

To prove the second let $`K`$ be the finite $`𝕊`$-complex under consideration. By Theorem 2.3 and Theorem 2.4 it is sufficient to show that $`K`$ contains no closed geodesic of length less than $`2\pi `$ and that for each cell $`B`$ in $`K`$, $`\text{link}(B,K)`$ contains no closed geodesic of length less than $`2\pi `$. Since $`K`$ and $`\text{link}(B,K)`$ are finite $`𝕊`$-complexes for all cells $`B`$, the first part of the proof shows that these are checkable conditions. ∎

###### Theorem B.

There exists an algorithm which determines whether or not a finite $`M_\kappa `$-complex is locally $`\text{CAT}(\kappa )`$.

###### Proof.

For each vertex $`v`$ in $`K`$, the link $`\text{link}(v,K)`$ is a finite $`𝕊`$-complex and by Theorem 7.1 we can check whether it is globally $`\text{CAT}(1)`$. By Theorem 2.4 this is sufficient. ∎

As can be seen from the proof, it is actually sufficient for the complex $`K`$ to be locally-finite, so long as (1) only a finite list of finite $`𝕊`$-complexes occur as links of $`0`$-cells up to isometry, and (2) there is a constructive procedure for enumerating this finite list.

Computational real algebraic geometry is able to show that testing curvature conditions is decidable and algorithmic, but the real algebraic sets described here quickly reach the limit of what is realistically computable using current techniques. For the working geometric group theorist who would like software which determines the local curvature of a finite $`M_\kappa `$-polyhedral complex, there are essentially two main options:

* use sophisticated techniques from computational real algebraic geometry to speed up the computations, or
* develop alternative, simpler algorithms which work directly with the geometry.

Both strategies are currently under investigation. The latter strategy, in particular, has already produced results in the form of a direct geometric algorithm to determine the local curvature of a $`3`$-dimensional $`M_\kappa `$-complex using only elementary $`3`$-dimensional geometry. This result can be found in . At this point, the following question remains open:

###### Open Question 7.2.

Is there a direct *geometric* algorithm which determines the local curvature of a finite $`M_\kappa `$-complex in dimensions greater than $`3`$?