# Conjuncted: Integer Pivoting as a Polynomial-Time Algorithm

The Lemke-Howson Algorithm follows the edges of a polyhedron, which is implemented algebraically by pivoting as used by the simplex algorithm for solving a linear program. Let us see, if there is an efficient implementation that has no numerical errors by storing integers of arbitrary precision. The constraints defining the polyhedron are thereby represented as linear equations with nonnegative slack variables. For the polytopes P and Q in

P = {x ∈ RM| x ≥ 0, Bx ≤ 1},

Q = {y ∈ RN |Ay ≤ 1, y ≥ 0}

these slack variables are nonnegative vectors s ∈ RN and r ∈ RM so that x ∈ P and y ∈ Q iff

Bx + s = 1, r + Ay = 1 —– (1)

and

x ≥ 0, s ≥ 0, r ≥ 0, y ≥ 0 —— (2)

A binding inequality corresponds to a zero slack variable. The pair (x, y) is completely labeled iff xiri = 0 ∀ i ∈ M and yjsj = 0 ∀ j ∈ N, which by (2) can be written as the orthogonality condition

xr = 0, ys = 0

A basic solution to (1) is given by n basic (linearly independent) columns of Bx + s = 1 and m basic columns of r + Ay = 1, where the nonbasic variables that correspond to the m respectively n other (nonbasic) columns are set to zero, so that the basic variables are uniquely determined. A basic feasible solution also fulfills (2), and defines a vertex x of P and y of Q. The labels of such a vertex are given by the respective nonbasic columns.

Pivoting is a change of the basis where a nonbasic variable enters and a basic variable leaves the set of basic variables, while preserving feasibility (2).

Integer pivoting always maintains an integer matrix (or “tableau”) of coefficients of a system of linear equations that is equivalent to the original system Bx + s = 1, in the form

CBx + Cs = C1 —– (3)

In (3), C is the inverse of the basis matrix given by the basic columns of the original system, multiplied by the determinant of the basis matrix. The matrix C is given by the (integer) cofactors of the basis matrix; the cofactor of a matrix entry is the determinant of the matrix when the row and column of that element are deleted. When each entry has a bounded number of digits (by at most a factor of n log n compared to the original matrix entries), then integer pivoting is a polynomial-time algorithm. It is also superior to using fractions of integers or rational numbers because their cancelation requires greatest common divisor computations that take the bulk of computation time.

# Intuition

During his attempt to axiomatize the category of all categories, Lawvere says

Our intuition tells us that whenever two categories exist in our world, then so does the corresponding category of all natural transformations between the functors from the first category to the second (The Category of Categories as a Foundation).

However, if one tries to reduce categorial constructions to set theory, one faces some serious problems in the case of a category of functors. Lawvere (who, according to his aim of axiomatization, is not concerned by such a reduction) relies here on “intuition” to stress that those working with categorial concepts despite these problems have the feeling that the envisaged construction is clear, meaningful and legitimate. Not the reducibility to set theory, but an “intuition” to be specified answers for clarity, meaningfulness and legitimacy of a construction emerging in a mathematical working situation. In particular, Lawvere relies on a collective intuition, a common sense – for he explicitly says “our intuition”. Further, one obviously has to deal here with common sense on a technical level, for the “we” can only extend to a community used to the work with the concepts concerned.

In the tradition of philosophy, “intuition” means immediate, i.e., not conceptually mediated cognition. The use of the term in the context of validity (immediate insight in the truth of a proposition) is to be thoroughly distinguished from its use in the sensual context (the German Anschauung). Now, language is a manner of representation, too, but contrary to language, in the context of images the concept of validity is meaningless.

Obviously, the aspect of cognition guiding is touched on here. Especially the sensual intuition can take the guiding (or heuristic) function. There have been many working situations in history of mathematics in which making the objects of investigation accessible to a sensual intuition (by providing a Veranschaulichung) yielded considerable progress in the development of the knowledge concerning these objects. As an example, take the following account by Emil Artin of Emmy Noether’s contribution to the theory of algebras:

Emmy Noether introduced the concept of representation space – a vector space upon which the elements of the algebra operate as linear transformations, the composition of the linear transformation reflecting the multiplication in the algebra. By doing so she enables us to use our geometric intuition.

Similarly, Fréchet thinks to have really “powered” research in the theory of functions and functionals by the introduction of a “geometrical” terminology:

One can [ …] consider the numbers of the sequence [of coefficients of a Taylor series] as coordinates of a point in a space [ …] of infinitely many dimensions. There are several advantages to proceeding thus, for instance the advantage which is always present when geometrical language is employed, since this language is so appropriate to intuition due to the analogies it gives birth to.

Mathematical terminology often stems from a current language usage whose (intuitive, sensual) connotation is welcomed and serves to give the user an “intuition” of what is intended. While Category Theory is often classified as a highly abstract matter quite remote from intuition, in reality it yields, together with its applications, a multitude of examples for the role of current language in mathematical conceptualization.

This notwithstanding, there is naturally also a tendency in contemporary mathematics to eliminate as much as possible commitments to (sensual) intuition in the erection of a theory. It seems that algebraic geometry fulfills only in the language of schemes that essential requirement of all contemporary mathematics: to state its definitions and theorems in their natural abstract and formal setting in which they can be considered independent of geometric intuition (Mumford D., Fogarty J. Geometric Invariant Theory).

In the pragmatist approach, intuition is seen as a relation. This means: one uses a piece of language in an intuitive manner (or not); intuitive use depends on the situation of utterance, and it can be learned and transformed. The reason for this relational point of view, consists in the pragmatist conviction that each cognition of an object depends on the means of cognition employed – this means that for pragmatism there is no intuitive (in the sense of “immediate”) cognition; the term “intuitive” has to be given a new meaning.

What does it mean to use something intuitively? Heinzmann makes the following proposal: one uses language intuitively if one does not even have the idea to question validity. Hence, the term intuition in the Heinzmannian reading of pragmatism takes a different meaning, no longer signifies an immediate grasp. However, it is yet to be explained what it means for objects in general (and not only for propositions) to “question the validity of a use”. One uses an object intuitively, if one is not concerned with how the rules of constitution of the object have been arrived at, if one does not focus the materialization of these rules but only the benefits of an application of the object in the present context. “In principle”, the cognition of an object is determined by another cognition, and this determination finds its expression in the “rules of constitution”; one uses it intuitively (one does not bother about the being determined of its cognition), if one does not question the rules of constitution (does not focus the cognition which determines it). This is precisely what one does when using an object as a tool – because in doing so, one does not (yet) ask which cognition determines the object. When something is used as a tool, this constitutes an intuitive use, whereas the use of something as an object does not (this defines tool and object). Here, each concept in principle can play both roles; among two concepts, one may happen to be used intuitively before and the other after the progress of insight. Note that with respect to a given cognition, Peirce when saying “the cognition which determines it” always thinks of a previous cognition because he thinks of a determination of a cognition in our thought by previous thoughts. In conceptual history of mathematics, however, one most often introduced an object first as a tool and only after having done so did it come to one’s mind to ask for “the cognition which determines the cognition of this object” (that means, to ask how the use of this object can be legitimized).

The idea that it could depend on the situation whether validity is questioned or not has formerly been overlooked, perhaps because one always looked for a reductionist epistemology where the capacity called intuition is used exclusively at the last level of regression; in a pragmatist epistemology, to the contrary, intuition is used at every level in form of the not thematized tools. In classical systems, intuition was not simply conceived as a capacity; it was actually conceived as a capacity common to all human beings. “But the power of intuitively distinguishing intuitions from other cognitions has not prevented men from disputing very warmly as to which cognitions are intuitive”. Moreover, Peirce criticises strongly cartesian individualism (which has it that the individual has the capacity to find the truth). We could sum up this philosophy thus: we cannot reach definite truth, only provisional; significant progress is not made individually but only collectively; one cannot pretend that the history of thought did not take place and start from scratch, but every cognition is determined by a previous cognition (maybe by other individuals); one cannot uncover the ultimate foundation of our cognitions; rather, the fact that we sometimes reach a new level of insight, “deeper” than those thought of as fundamental before, merely indicates that there is no “deepest” level. The feeling that something is “intuitive” indicates a prejudice which can be philosophically criticised (even if this does not occur to us at the beginning).

In our approach, intuitive use is collectively determined: it depends on the particular usage of the community of users whether validity criteria are or are not questioned in a given situation of language use. However, it is acknowledged that for example scientific communities develop usages making them communities of language users on their own. Hence, situations of language use are not only partitioned into those where it comes to the users’ mind to question validity criteria and those where it does not, but moreover this partition is specific to a particular community (actually, the community of language users is established partly through a peculiar partition; this is a definition of the term “community of language users”). The existence of different communities with different common senses can lead to the following situation: something is used intuitively by one group, not intuitively by another. In this case, discussions inside the discipline occur; one has to cope with competing common senses (which are therefore not really “common”). This constitutes a task for the historian.

# High Frequency Traders: A Case in Point.

Events on 6th May 2010:

In the ordinary course of business, HFTs use their technological advantage to profit from aggressively removing the last few contracts at the best bid and ask levels and then establishing new best bids and asks at adjacent price levels ahead of an immediacy-demanding customer. As an illustration of this “immediacy absorption” activity, consider the following stylized example, presented in Figure and described below.

Suppose that we observe the central limit order book for a stock index futures contract. The notional value of one stock index futures contract is \$50. The market is very liquid – on average there are hundreds of resting limit orders to buy or sell multiple contracts at either the best bid or the best offer. At some point during the day, due to temporary selling pressure, there is a total of just 100 contracts left at the best bid price of 1000.00. Recognizing that the queue at the best bid is about to be depleted, HFTs submit executable limit orders to aggressively sell a total of 100 contracts, thus completely depleting the queue at the best bid, and very quickly submit sequences of new limit orders to buy a total of 100 contracts at the new best bid price of 999.75, as well as to sell 100 contracts at the new best offer of 1000.00. If the selling pressure continues, then HFTs are able to buy 100 contracts at 999.75 and make a profit of \$1,250 dollars among them. If, however, the selling pressure stops and the new best offer price of 1000.00 attracts buyers, then HFTs would very quickly sell 100 contracts (which are at the very front of the new best offer queue), “scratching” the trade at the same price as they bought, and getting rid of the risky inventory in a few milliseconds.

This type of trading activity reduces, albeit for only a few milliseconds, the latency of a price move. Under normal market conditions, this trading activity somewhat accelerates price changes and adds to the trading volume, but does not result in a significant directional price move. In effect, this activity imparts a small “immediacy absorption” cost on all traders, including the market makers, who are not fast enough to cancel the last remaining orders before an imminent price move.

This activity, however, makes it both costlier and riskier for the slower market makers to maintain continuous market presence. In response to the additional cost and risk, market makers lower their acceptable inventory bounds to levels that are too small to offset temporary liquidity imbalances of any significant size. When the diminished liquidity buffer of the market makers is pierced by a sudden order flow imbalance, they begin to demand a progressively greater compensation for maintaining continuous market presence, and prices start to move directionally. Just as the prices are moving directionally and volatility is elevated, immediacy absorption activity of HFTs can exacerbate a directional price move and amplify volatility. Higher volatility further increases the speed at which the best bid and offer queues are being depleted, inducing HFT algorithms to demand immediacy even more, fueling a spike in trading volume, and making it more costly for the market makers to maintain continuous market presence. This forces more risk averse market makers to withdraw from the market, which results in a full-blown market crash.

Empirically, immediacy absorption activity of the HFTs should manifest itself in the data very differently from the liquidity provision activity of the Market Makers. To establish the presence of these differences in the data, we test the following hypotheses:

Hypothesis H1: HFTs are more likely than Market Makers to aggressively execute the last 100 contracts before a price move in the direction of the trade. Market Makers are more likely than HFTs to have the last 100 resting contracts against which aggressive orders are executed.

Hypothesis H2: HFTs trade aggressively in the direction of the price move. Market Makers get run over by a price move.

Hypothesis H3: Both HFTs and Market Makers scratch trades, but HFTs scratch more.

To statistically test our “immediacy absorption” hypotheses against the “liquidity provision” hypotheses, we divide all of the trades during the 405 minute trading day into two subsets: Aggressive Buy trades and Aggressive Sell trades. Within each subset, we further aggregate multiple aggressive buy or sell transactions resulting from the execution of the same order into Aggressive Buy or Aggressive Sell sequences. The intuition is as follows. Often a specific trade is not a stand alone event, but a part of a sequence of transactions associated with the execution of the same order. For example, an order to aggressively sell 10 contracts may result in four Aggressive Sell transactions: for 2 contracts, 1 contract, 4 contracts, and 3 contracts, respectively, due to the specific sequence of resting bids against which this aggressive sell order was be executed. Using the order ID number, we are able to aggregate these four transactions into one Aggressive Sell sequence for 10 contracts.

Testing Hypothesis H1. Aggressive removal of the last 100 contracts by HFTs; passive provision of the last 100 resting contracts by the Market Makers. Using the Aggressive Buy sequences, we label as a “price increase event” all occurrences of trading sequences in which at least 100 contracts consecutively executed at the same price are followed by some number of contracts at a higher price. To examine indications of low latency, we focus on the the last 100 contracts traded before the price increase and the first 100 contracts at the next higher price (or fewer if the price changes again before 100 contracts are executed). Although we do not look directly at the limit order book data, price increase events are defined to capture occasions where traders use executable buy orders to lift the last remaining offers in the limit order book. Using Aggressive sell trades, we define “price decrease events” symmetrically as occurrences of sequences of trades in which 100 contracts executed at the same price are followed by executions at lower prices. These events are intended to capture occasions where traders use executable sell orders to hit the last few best bids in the limit order book. The results are presented in Table below

For price increase and price decrease events, we calculate each of the six trader categories’ shares of Aggressive and Passive trading volume for the last 100 contracts traded at the “old” price level before the price increase or decrease and the first 100 contracts traded at the “new” price level (or fewer if the number of contracts is less than 100) after the price increase or decrease event.

Table above presents, for the six trader categories, volume shares for the last 100 contracts at the old price and the first 100 contracts at the new price. For comparison, the unconditional shares of aggressive and passive trading volume of each trader category are also reported. Table has four panels covering (A) price increase events on May 3-5, (B) price decrease events on May 3-5, (C) price increase events on May 6, and (D) price decrease events on May 6. In each panel there are six rows of data, one row for each trader category. Relative to panels A and C, the rows for Fundamental Buyers (BUYER) and Fundamental Sellers (SELLER) are reversed in panels B and D to emphasize the symmetry between buying during price increase events and selling during price decrease events. The first two columns report the shares of Aggressive and Passive contract volume for the last 100 contracts before the price change; the next two columns report the shares of Aggressive and Passive volume for up to the next 100 contracts after the price change; and the last two columns report the “unconditional” market shares of Aggressive and Passive sides of all Aggressive buy volume or sell volume. For May 3-5, the data are based on volume pooled across the three days.

Consider panel A, which describes price increase events associated with Aggressive buy trades on May 3-5, 2010. High Frequency Traders participated on the Aggressive side of 34.04% of all aggressive buy volume. Strongly consistent with immediacy absorption hypothesis, the participation rate rises to 57.70% of the Aggressive side of trades on the last 100 contracts of Aggressive buy volume before price increase events and falls to 14.84% of the Aggressive side of trades on the first 100 contracts of Aggressive buy volume after price increase events.

High Frequency Traders participated on the Passive side of 34.33% of all aggressive buy volume. Consistent with hypothesis, the participation rate on the Passive side of Aggressive buy volume falls to 28.72% of the last 100 contracts before a price increase event. It rises to 37.93% of the first 100 contracts after a price increase event.

These results are inconsistent with the idea that high frequency traders behave like textbook market makers, suffering adverse selection losses associated with being picked off by informed traders. Instead, when the price is about to move to a new level, high frequency traders tend to avoid being run over and take the price to the new level with Aggressive trades of their own.

Market Makers follow a noticeably more passive trading strategy than High Frequency Traders. According to panel A, Market Makers are 13.48% of the Passive side of all Aggressive trades, but they are only 7.27% of the Aggressive side of all Aggressive trades. On the last 100 contracts at the old price, Market Makers’ share of volume increases only modestly, from 7.27% to 8.78% of trades. Their share of Passive volume at the old price increases, from 13.48% to 15.80%. These facts are consistent with the interpretation that Market Makers, unlike High Frequency Traders, do engage in a strategy similar to traditional passive market making, buying at the bid price, selling at the offer price, and suffering losses when the price moves against them. These facts are also consistent with the hypothesis that High Frequency Traders have lower latency than Market Makers.

Intuition might suggest that Fundamental Buyers would tend to place the Aggressive trades which move prices up from one tick level to the next. This intuition does not seem to be corroborated by the data. According to panel A, Fundamental Buyers are 21.53% of all Aggressive trades but only 11.61% of the last 100 Aggressive contracts traded at the old price. Instead, Fundamental Buyers increase their share of Aggressive buy volume to 26.17% of the first 100 contracts at the new price.

Taking into account symmetry between buying and selling, panel B shows the results for Aggressive sell trades during May 3-5, 2010, are almost the same as the results for Aggressive buy trades. High Frequency Traders are 34.17% of all Aggressive sell volume, increase their share to 55.20% of the last 100 Aggressive sell contracts at the old price, and decrease their share to 15.04% of the last 100 Aggressive sell contracts at the new price. Market Makers are 7.45% of all Aggressive sell contracts, increase their share to only 8.57% of the last 100 Aggressive sell trades at the old price, and decrease their share to 6.58% of the last 100 Aggressive sell contracts at the new price. Fundamental Sellers’ shares of Aggressive sell trades behave similarly to Fundamental Buyers’ shares of Aggressive Buy trades. Fundamental Sellers are 20.91% of all Aggressive sell contracts, decrease their share to 11.96% of the last 100 Aggressive sell contracts at the old price, and increase their share to 24.87% of the first 100 Aggressive sell contracts at the new price.

The number of price increase and price decrease events increased dramatically on May 6, consistent with the increased volatility of the market on that day. On May 3-5, there were 4100 price increase events and 4062 price decrease events. On May 6 alone, there were 4101 price increase events and 4377 price decrease events. There were therefore approximately three times as many price increase events per day on May 6 as on the three preceding days.

Testing Hypothesis H2. HFTs trade aggressively in the direction of the price move; Market Makers get run over by a price move. To examine this hypothesis, we analyze whether High Frequency Traders use Aggressive trades to trade in the direction of contemporaneous price changes, while Market Makers use Passive trades to trade in the opposite direction from price changes. To this end, we estimate the regression equation

Δyt = α + Φ . Δyt-1 + δ . yt-1 + Σi=120i . Δpt-1 /0.25] + εt

(where yt and Δyt denote inventories and change in inventories of High Frequency Traders for each second of a trading day; t = 0 corresponds to the opening of stock trading on the NYSE at 8:30:00 a.m. CT (9:30:00 ET) and t = 24, 300 denotes the close of Globex at 15:15:00 CT (4:15 p.m. ET); Δpt denotes the price change in index point units between the high-low midpoint of second t-1 and the high-low midpoint of second t. Regressing second-by-second changes in inventory levels of High Frequency Traders on the level of their inventories the previous second, the change in their inventory levels the previous second, the change in prices during the current second, and lagged price changes for each of the previous 20 previous seconds.)

for Passive and Aggressive inventory changes separately.

Table above presents the regression results of the two components of change in holdings on lagged inventory, lagged change in holdings and lagged price changes over one second intervals. Panel A and Panel B report the results for May 3-5 and May 6, respectively. Each panel has four columns, reporting estimated coefficients where the dependent variables are net Aggressive volume (Aggressive buys minus Aggressive sells) by High Frequency Traders (∆AHFT), net Passive volume by High Frequency Traders (∆PHFT), net Aggressive volume by Market Makers (∆AMM), and net Passive volume by Market Makers (∆PMM).

We observe that for lagged inventories (NPHFTt−1), the estimated coefficients for Aggressive and Passive trades by High Frequency Traders are δAHFT = −0.005 (t = −9.55) and δPHFT = −0.001 (t = −3.13), respectively. These coefficient estimates have the interpretation that High Frequency Traders use Aggressive trades to liquidate inventories more intensively than passive trades. In contrast, the results for Market Makers are very different. For lagged inventories (NPMMt−1), the estimated coefficients for Aggressive and Passive volume by Market Makers are δAMM = −0.002 (t = −6.73) and δPMM = −0.002 (t = −5.26), respectively. The similarity of these coefficients estimates has the interpretation that Market Makers favor neither Aggressive trades nor Passive trades when liquidating inventories.

For lagged price changes, coefficient estimates for Aggressive trades by High Frequency Traders and Market Makers are positive and statistically significant at lags 1-4 and lags 1-10, respectively. These results have the interpretation that both High Frequency Traders’ and Market Makers’ trade on recent price momentum, but the trading is compressed into a shorter time frame for High Frequency Traders than for Market Makers.

When High Frequency Traders are net buyers on May 3-5, prices rise by 17% of a tick in the next second. When HFTs execute Aggressively or Passively, prices rise by 20% and 2% of a tick in the next second, respectively. In subsequent seconds, prices in all cases trend downward by about 5% of a tick over the subsequent 19 seconds. For May 3-5, the results are almost symmetric for selling.

The results of this analysis are presented in the table below. Panel A provides results for May 3-5 and panel B for May 6. In each panel, there are five rows of data, one for each trader category. The first three columns report the total number of trades, the total number of immediately scratched trades, and the percentage of trades that are immediately scratched by traders in five categories. For May 3-6, the reported numbers are from the pooled data.

This table presents statistics for immediate trade scratching which measures how many times a trader changes his/her direction of trading in a second aggregated over a day. We define a trade direction change as a buy trade right after a sell trade or vice versa at the same price level in the same second.

This table shows that High Frequency Traders scratched 2.84 % of trades on May 3-5 and 4.26 % on May 6; Market Makers scratched 2.49 % of trades on May 3-5 and 5.53 % of trades on May 6. While the percentages of immediately scratched trades by Market Makers is slightly higher than that for High Frequency Traders on May 6, the percentages for both groups are very similar. The fourth, fifth, and sixth columns of the Table report the mean, standard deviation, and median of the number of scratched trades for the traders in each category.

Although the percentages of scratched trades are similar, the mean number of immediately scratched trades by High Frequency Traders is much greater than for Market Makers: 540.56 per day on May 3-5 and 1610.75 on May 6 for High Frequency Traders versus 13.35 and 72.92 for Market Makers. The differences between High Frequency Traders and Market Makers reflect differences in volume traded. The Table shows that High Frequency Traders and Market Makers scratch a significantly larger percentage of their trades than other trader categories.

# Osteo Myological Quantization. Note Quote.

The site of the parameters in a higher order space can also be quantized into segments, the limits of which can be no more decomposed. Such a limit may be nearly a rigid piece. In the animal body such quanta cannot but be bone pieces forming parts of the skeleton, whether lying internally as [endo]-skeleton or as almost rigid shell covering the body as external skeleton.

Note the partition of the body into three main segments: Head (cephalique), pectral (breast), caudal (tail), materializing the KH order limit M>= 3 or the KHK dimensional limit N>= 3. Notice also the quantization into more macroscopic segments such as of the abdominal part into several smaller segments beyond the KHK lower bound N=3. Lateral symmetry with a symmetry axis is remarkable. This is of course an indispensable consequence of the modified Zermelo conditions, which entails also locomotive appendages differentiating into legs for walking and wings for flying in the case of insects.

Two paragraphs of Kondo addressing the simple issues of what bones are, mammalian bi-lateral symmetry, the numbers of major body parts and their segmentation, the notion of the mathematical origins of wings, legs and arms. The dimensionality of eggs being zero, hence their need of warmth for progression to locomotion and the dimensionality of snakes being one, hence their mode of locomotion. A feature of the biological is their attention to detail, their use of line art to depict the various forms of living being – from birds to starfish to dinosaurs, the use of the full latin terminology and at all times the relationship of the various form of living being to the underlying higher order geometry and the mathematical notion of principle ideals. The human skeleton is treated as a hierarchical Kawaguchi tree with its characteristic three pronged form. The Riemannian arc length of the curve k(t) is given by the integral of the square root of a quadratic form in x’ with coefficients dependent in x’. This integrand is homogenous of the first order in x’. If we drop the quadratic property and retain the homogeneity, then we obtain the Finsler geometry. Kawaguchi geometry supposes that the integrand depends upon the higher derivatives x’’ up to the k-th derivative xk. The notation that Kondo uses is:

K(M)L,N

For:

L Parameters N Dimensions M Derivatives

The lower part of the skeleton can be divided into three prongs, each starting from the centre as a single parametric Kawaguchi tree.

…the skeletal, muscular, gastrointestinal, circulation systems etc combine into a holo-parametric whole that can be more generally quantized, each quantum involving some osteological, neural, circulatory functions etc.

…thus globally the human body from head through trunk to limbs are quantized into a finite number of quanta.

# Of Topos and Torsors

Let X be a topological space. One goal of algebraic topology is to study the topology of X by means of algebraic invariants, such as the singular cohomology groups Hn(X;G) of X with coefficients in an abelian group G. These cohomology groups have proven to be an extremely useful tool, due largely to the fact that they enjoy excellent formal properties, and the fact that they tend to be very computable. However, the usual definition of Hn(X;G) in terms of singular G-valued cochains on X is perhaps somewhat unenlightening. This raises the following question: can we understand the cohomology group Hn(X;G) in more conceptual terms?

As a first step toward answering this question, we observe that Hn(X;G) is a representable functor of X. That is, there exists an Eilenberg-MacLane space K(G,n) and a universal cohomology class η ∈ Hn(K(G,n);G) such that, for any topological space X, pullback of η determines a bijection

[X, K(G, n)] → Hn(X; G)

Here [X,K(G,n)] denotes the set of homotopy classes of maps from X to K(G,n). The space K(G,n) can be characterized up to homotopy equivalence by the above property, or by the the formula πkK(G,n)≃ ∗ if k̸ ≠ n

or

G if k = n.

In the case n = 1, we can be more concrete. An Eilenberg MacLane space K(G,1) is called a classifying space for G, and is typically denoted by BG. The universal cover of BG is a contractible space EG, which carries a free action of the group G by covering transformations. We have a quotient map π : EG → BG. Each fiber of π is a discrete topological space, on which the group G acts simply transitively. We can summarize the situation by saying that EG is a G-torsor over the classifying space BG. For every continuous map X → BG, the fiber product X~ : EG × BG X has the structure of a G-torsor on X: that is, it is a space endowed with a free action of G and a homeomorphism X~/G ≃ X. This construction determines a map from [X,BG] to the set of isomorphism classes of G-torsors on X. If X is a well-behaved space (such as a CW complex), then this map is a bijection. We therefore have (at least) three different ways of thinking about a cohomology class η ∈ H1(X; G):

(1) As a G-valued singular cocycle on X, which is well-defined up to coboundaries.

(2) As a continuous map X → BG, which is well-defined up to homotopy.

(3) As a G-torsor on X, which is well-defined up to isomorphism.

The singular cohomology of a space X is constructed using continuous maps from simplices ∆k into X. If there are not many maps into X (for example if every path in X is constant), then we cannot expect singular cohomology to tell us very much about X. The second definition uses maps from X into the classifying space BG, which (ultimately) relies on the existence of continuous real-valued functions on X. If X does not admit many real-valued functions, then the set of homotopy classes [X,BG] is also not a very useful invariant. For such spaces, the third approach is the most powerful: there is a good theory of G-torsors on an arbitrary topological space X.

There is another reason for thinking about H1(X;G) in the language of G-torsors: it continues to make sense in situations where the traditional ideas of topology break down. If X is a G-torsor on a topological space X, then the projection map X → X is a local homeomorphism; we may therefore identify X with a sheaf of sets F on X. The action of G on X determines an action of G on F. The sheaf F (with its G-action) and the space X (with its G-action) determine each other, up to canonical isomorphism. Consequently, we can formulate the definition of a G-torsor in terms of the category ShvSet(X) of sheaves of sets on X without ever mentioning the topological space X itself. The same definition makes sense in any category which bears a sufficiently strong resemblance to the category of sheaves on a topological space: for example, in any Grothendieck topos. This observation allows us to construct a theory of torsors in a variety of nonstandard contexts, such as the étale topology of algebraic varieties.

Describing the cohomology of X in terms of the sheaf theory of X has still another advantage, which comes into play even when the space X is assumed to be a CW complex. For a general space X, isomorphism classes of G-torsors on X are classified not by the singular cohomology H1sing(X;G), but by the sheaf cohomology H1sheaf(X; G) of X with coefficients in the constant sheaf G associated to G. This sheaf cohomology is defined more generally for any sheaf of groups G on X. Moreover, we have a conceptual interpretation of H1sheaf(X; G) in general: it classifies G-torsors on X (that is, sheaves F on X which carry an action of G and locally admit a G-equivariant isomorphism F ≃ G) up to isomorphism. The general formalism of sheaf cohomology is extremely useful, even if we are interested only in the case where X is a nice topological space: it includes, for example, the theory of cohomology with coefficients in a local system on X.

Let us now attempt to obtain a similar interpretation for cohomology classes η ∈ H2 (X ; G). What should play the role of a G-torsor in this case? To answer this question, we return to the situation where X is a CW complex, so that η can be identified with a continuous map X → K(G,2). We can think of K(G,2) as the classifying space of a group: not the discrete group G, but instead the classifying space BG (which, if built in a sufficiently careful way, comes equipped with the structure of a topological abelian group). Namely, we can identify K(G, 2) with the quotient E/BG, where E is a contractible space with a free action of BG. Any cohomology class η ∈ H2(X;G) determines a map X → K(G,2), and we can form the pullback X~ = E × BG X. We now think of X as a torsor over X: not for the discrete group G, but instead for its classifying space BG.

To complete the analogy with our analysis in the case n = 1, we would like to interpret the fibration X → X as defining some kind of sheaf F on the space X. This sheaf F should have the property that for each x ∈ X, the stalk Fx can be identified with the fiber X~x ≃ BG. Since the space BG is not discrete (or homotopy equivalent to a discrete space), the situation cannot be adequately described in the usual language of set-valued sheaves. However, the classifying space BG is almost discrete: since the homotopy groups πiBG vanish for i > 1, we can recover BG (up to homotopy equivalence) from its fundamental groupoid. This suggests that we might try to think about F as a “groupoid-valued sheaf” on X, or a stack (in groupoids) on X.