User:Richard Pinch/sandbox-13

Trace

Trace may refer to

• Trace on a field extension
• Trace of a square matrix
• Trace on a C*-algebra
• Trace of a trace-class operator
• An element of a trace monoid
• Reduced trace on a central simple algebra

Trace monoid

Let $A$ be an alphabet with an irreflexive symmetric relation $I$ called independence. The complementary relation $I = A \times A \setminus I$ is the "dependence" relation. Such an alphabet is a concurrence or dependency alphabet. The free monoid on $A$ modulo the relations $ab=ba$ when $a,b \in I$ is the trace monoid on $(A,D)$. The elements of a trace monoid are "traces" and the subsets are the "trace languages".

Trace monoids are used to model concurrency in computer languages.

References

• Diekert, Volker; Rozenberg, Grzegorz (edd) "The Book Of Traces" (World Scientific, 1995) ISBN 981-02-2058-8

Trace-class operator

An operator $T$ on a Hilbert space $H$ with complete orthonormal set $(e_n)$ for which the sum $\sum_n \langle Tx_n , x_n \rangle$ is finite. For such operators, the trace is defined to be the value of this sum. The set of trace-class operators on $H$ coincides with the set of squares of Hilbert-Schmidt operators.

Downset

lower set, lower cone

A subset $S$ of a partially ordered set $(P,{\le})$ with the property that if $x \in S$ and $y \le x$ then $y \in S$.

The principal downset on an element $a \in P$ is the set $x^\Delta$, also denoted $(x]$, is defined as $x^\Delta = \{y \in P : y \le x \}$.

The dual notion of upset (upper set, upper cone) is defined as a subset $S$ of with the property that if $x \in S$ and $x \le y$ then $y \in S$. The principal upset on an element $a \in P$ is the set $x^\nabla$, also denoted $[x)$, is defined as $x^\nabla = \{y \in P : x \le y \}$.

The terms "ideal" and "filter" are sometimes used for downset and upset respectively. However, it is usual to impose the extra condition that an ideal contain the supremum of any two elements and, dually, that a filter contain the infimum of any two element. See the comments at Ideal and Filter.

Span

Span may refer to

• Linear hull, also called linear span or span
• Span (category theory)

Span (category theory)

A diagram in a category of the form $$ \begin{array}{ccccc} & & C & & \\ & f \swarrow & & \searrow g & \\ A & & & & B \end{array} $$

Two spans with arrows $(f,g)$ and $(f',g')$ are equivalent if for all $D,p,q$ the diagrams $$ \begin{array}{ccccc} & & C & & \\ & f \swarrow & & \searrow g & \\ A & & & & B \\ & p \searrow & & \swarrow q \\ & & D & & \\ \end{array} \ \ \text{and}\ \ \begin{array}{ccccc} & & C & & \\ & f' \swarrow & & \searrow g' & \\ A & & & & B \\ & p \searrow & & \swarrow q \\ & & D & & \\ \end{array} $$ either both commute or both do not commute.

A pushout is the colimit of a span.

References

[1]	S. MacLane, "Categories for the working mathematician" , Springer (1971). ISBN 0-387-98403-8

Standard construction

A concept in category theory. Other names are triple, monad and functor-algebra.

Let $\mathfrak{S}$ be a category. A standard construction is a functor $T:\mathfrak{S} \rightarrow \mathfrak{S}$ equipped with natural transformations $\eta:1\rightarrow T$ and $\mu:T^2\rightarrow T$ such that the following diagrams commute: $$ \begin{array}{ccc} T^3 Y & \stackrel{T\mu_Y}{\rightarrow} & T^2 Y \\ \mu_{TY}\downarrow& & \downarrow_Y \\ T^2 & \stackrel{T_y}{\rightarrow} & Y \end{array} $$ $$ \begin{array}{ccccc} TY & \stackrel{TY}{\rightarrow} & T^2Y & \stackrel{T_{\eta Y}}{\leftarrow} & TY \\ & 1\searrow & \downarrow\mu Y & \swarrow1 & \\ & & Y & & \\ \end{array} $$

The basic use of standard constructions in topology is in the construction of various classifying spaces and their algebraic analogues, the so-called bar-constructions.

References

[1]	J.M. Boardman, R.M. Vogt, "Homotopy invariant algebraic structures on topological spaces" , Springer (1973)
[2]	J.F. Adams, "Infinite loop spaces" , Princeton Univ. Press (1978)
[3]	J.P. May, "The geometry of iterated loop spaces" , Lect. notes in math. , 271 , Springer (1972)
[4]	S. MacLane, "Categories for the working mathematician" , Springer (1971)

Comments

The term "standard construction" was introduced by R. Godement [a1] for want of a better name for this concept. It is now entirely obsolete, having been generally superseded by "monad" (although a minority of authors still use the term "triple" ). Monads have many other uses besides the one mentioned above, for example in the categorical approach to universal algebra (see [a2], [a3]).

References

[a1]	R. Godement, "Théorie des faisceaux" , Hermann (1958)
[a2]	E.G. Manes, "Algebraic theories" , Springer (1976)
[a3]	M. Barr, C. Wells, "Toposes, triples and theories" , Springer (1985)

Ostrowski representation

MSC 11A67

Let $[a_1,a_2,\ldots]$ be the partial quotients of an infinite continued fraction and $(c_n)$ the corresponding continuants, $c_0 = 1$, $c_1 = a_1$ and $c_{n+1} = a_{n+1} c_n + c_{n-1}$. An Ostrowski representation of $N$ is $$ N = \sum_{k=0}^n x_{k+1} c_k $$ where $0 \le x_k \le a_k$ and if $x_k = a_k$ then $x_{k-1} = 0$. Every positive integer $M$ has a unique Ostrowski representation.

When the $a_n$ are all equal to $1$, the $c_n$ are the Fibonacci numbers, and the Ostrowski representation is just the Zeckendorf representation. The addition of two $n$-digit numbers in Ostrowski representation based on a given continued fraction can be computed by three linear passes over the input.

References

• Philipp Hieronymi; Alonza Terry jun. "Ostrowski numeration systems, addition, and finite automata" Notre Dame J. Formal Logic 59 (2018) 215-232 Zbl 06870290