text:
Bigalois extensions and the graph isomorphism game

Bigalois extensions and the graph isomorphism game

Michael Brannan111Department of Mathematics, Texas A&M University, mbrannan@math.tamu.edu, Alexandru Chirvasitu222Department of Mathematics, University at Buffalo, achirvas@buffalo.edu, Kari Eifler333Department of Mathematics, Texas A&M University, keifler@math.tamu.edu, Samuel Harris444Deparment of Pure Mathematics, University of Waterloo, sj2harri@uwaterloo.ca,
Vern Paulsen555Deparment of Pure Mathematics & The Institute for Quantum Computing, University of Waterloo, vpaulsen@uwaterloo.ca, Xiaoyu Su666Department of Mathematics, Texas A&M University, xiaoyuegongzi@math.tamu.edu, Mateusz Wasilewski777Department of Mathematics, Katholieke Universiteit Leuven, mateusz.wasilewski@kuleuven.be
July 20, 2019
Abstract

We study the graph isomorphism game that arises in quantum information theory from the perspective of bigalois extensions of compact quantum groups. We show that every algebraic quantum isomorphism between a pair of (quantum) graphs and arises as a quotient of a certain measured bigalois extension for the quantum automorphism groups and of the graphs and . In particular, this implies that the quantum groups and are monoidally equivalent. We also establish a converse to this result, which says that every compact quantum group monoidally equivalent to is of the form for a suitably chosen quantum graph that is quantum isomorphic to . As an application of these results, we deduce that the -algebraic, C-algebraic, and quantum commuting (qc) notions of a quantum isomorphism between classical graphs and all coincide. Using the notion of equivalence for non-local games, we deduce the same result for other synchronous non-local games, including the synBCS game and certain related graph homomorphism games.

Key words: quantum automorphism group, graph, non-local game, entanglement, monoidal equivalence, bigalois extension, representation category

MSC 2010: 20G42; 46L52; 16T20

1 Introduction

Finite input-output games have received considerable attention in the quantum information theory literature as tools for investigating the structure of quantum correlations. The latter are meant to model the following setup (in one of several ways, depending on the specific chosen model [26]):

The perennial experimenters Alice and Bob, share an entangled quantum state, each performs one of quantum experiments and returns one of outputs. The respective quantum correlation is then defined as the collection of conditional probabilities of obtaining a given pair of outputs for a given pair of inputs, .

To recast this in game theoretic terms one typically proceeds as follows. Alice (A) and Bob (B) are regarded as cooperating players trying to supply “correct” answers to a referee (R) who communicates with A/B via sets of questions (inputs) . Alice and Bob then reply with answers from their respective sets of outputs . The game rules, which are known to A, B, and R, are embodied by a function , such that A and B win a round of the game if their respective replies and to the questions and satisfy , and they lose the round otherwise. Prior to the round, A and B can cooperate to develop a winning strategy, but are not allowed to communicate once the game begins. Cooperation consists of a pre-arranged strategy, which can be deterministic or random. We identify probabilistic strategies with the collection of conditional probability densities that they produce.

A probabilistic strategy is called perfect or winning, if the probability that they give an incorrect pair of answers is 0, i.e., . The key point is that the set of such conditional probability densities that can be obtained via quantum experiments in an entangled state is larger than the set of densities that can be obtained from classical shared randomness. For this reason winning quantum strategies can often be shown to exist when classical ones do not exist.

Our starting point in this context is the graph isomorphism game introduced in [1]. Given two finite graphs and this game has inputs that are the disjoint union of the vertices of and the vertices of and outputs that are the same set. The referee sends A, B each a vertex and receives respective answers . Winning conditions require that

• and belong to different graphs;

• ditto for and ;

• the “relatedness” of the inputs is reflected by that of the outputs: , or are distinct and connected by an edge, or distinct and disconnected if and only if the same holds for the vertices.

It turns out that the game has a perfect deterministic strategy if and only if the two graphs are isomorphic. This observation motivates the authors of [18] to introduce a notion of quantum isomorphism between finite graphs, relating to the existence of less constrained, random strategies for the graph isomorphism game. Whether or not two finite graphs and are quantum-isomorphic is governed by a -algebra , a non-commutative counterpart to the function algebra of the space of isomorphisms . More precisely, the algebra of continuous functions on the space of isomorphisms can be recovered as the abelianization of .

One is thus prompted to consider “quantum spaces” in the sense of non-commutative geometry: -algebras or C-algebras, thought of as function algebras on the otherwise non-existent spaces. In the same spirit we will work with quantum graphs (finite-dimensional C-algebras equipped with some additional structure mimicking an “adjacency matrix” § 3.1) and quantum groups i.e. non-commutative -algebras with enough structure to resemble algebras of representative functions on compact groups (§ 2.5).

As is the case classically, every quantum graph has a quantum automorphism group . The recent papers [18, 19, 20] uncover further remarkable connections between graph isomorphism games and quantum automorphism groups. Moreover, while [18] focuses on classical graphs, [19, 20] consider a more general categorical quantum mechanical framework which leads naturally to the notion of a quantum graphs and the generalization of the graph isomorphism game to that framework.

In particular, [20] obtains a characterization of (finite-dimensional) quantum isomorphic quantum graphs , in terms of simple dagger Frobenius monoids in the category of finite dimensional representations of the Hopf -algebra of the corresponding quantum automorphism group . On the other hand, [18] uses ideas from quantum group theory to establish the equivalence between the existence of C-quantum isomorphisms for graphs and the existence of perfect strategies for the isomorphism game within the so-called quantum commuting framework.

Here, we continue in the same vein investigating connections between quantum automorphism groups of graphs and the graph isomorphism game, taking a somewhat dual approach to the one in [19, 20]:

We regard the game -algebra as indicated above, as a non-commutative analogue of the space of isomorphisms . In particular, we say that and are algebraically quantum isomorphic, and simply write , if . Classically, the space of isomorphisms between two graphs is a principal homogeneous bundle over the automorphism groups of both graphs. In other words, if denotes the space of graph isomorphisms and (resp. ) denotes the automorphism group of (resp. ), then the canonical left/right actions are free and transitive. One of our main results is the quantum analogue of this remark; it is Theorem 4.33 below, and can be paraphrased as follows:

Theorem

Let and be two quantum graphs. If the quantum isomorphism space is non-trivial then it is a quantum principal bi-bundle (bigalois extension) over the quantum automorphism groups and of and respectively.

This (non-commutative) bundle-theoretic perspective on has advantages: Although the construction of is purely algebraic and does not assume the existence of any C-representations of this object, we use the above result to show that this algebra always admits a faithful invariant state whenever it is non-zero (cf. Theorem 4.35), leading to connections with the notion of monoidal equivalence between quantum automorphism groups. Loosely speaking, we say that two compact quantum groups are monoidally equivalent if their categories of finite-dimensional unitary representations are equivalent as rigid C-tensor categories. Our main result here is an amalgamation of Theorem 4.35 and Theorem 4.39, and says:

Theorem

Let be a quantum graph and its quantum automorphism group. Then the following hold:

1. If is another quantum graph such that , then admits a faithful state and is monoidally equivalent to the quantum automorphism group . If both and are moreover classical graphs, then admits a faithful tracial state.

2. Conversely, for any compact quantum group monoidally equivalent to , one can construct from this monoidal equivalence a quantum graph , an isomorphism of quantum groups , and an algebraic quantum isomorphism .

Recasting all of the above in the context of the (classical) graph isomorphism game, our results show that the condition is sufficient to ensure the existence of perfect quantum strategies for this game (Corollary 4.36 and Theorem 4.37):

Theorem

Two classical graphs and are algebraically quantum isomorphic if and only if the graph isomorphism game has a perfect quantum-commuting -strategy.

We mention that a weaker version of the above theorem (that assumed the existence of a non-zero C-algebra representation of ) was recently proved in [18].

Using a notion of -equivalence for non-local games, we also use the above result to deduce the existence of perfect -strategies from purely algebraic data for synchronous binary constraint system (syncBCS) games and certain related graph homomorphism games (Corollary 5.52 and Corollary 5.53). We find all these results very striking because for generic synchronous games (e.g. the graph homomorphism game) the -algebra governing the game may be non-zero even if this algebra has no C-representations (and hence no perfect quantum strategies) [16].

We note also that the above results could be recast in a much broader context – rather than quantum graphs, we could consider arbitrary finite quantum structures: quantum sets (i.e. finite-dimensional -algebras with a fixed state) equipped with arbitrary tensors. Input-output isomorphism games could then be constructed as in the case of graphs, and the discussion replicated in that general framework. Our focus on (quantum) graphs is motivated by the contingent fact that the latter have received considerable interest in the literature.

After recalling some preliminary material in Section 2 and generalities on quantum sets and Galois extensions in Section 3 we prove our main results in Section 4. Finally, Section 5 contains further applications to finite input-output games.

2 Preliminaries

2.1 Some notation

If is a natural number, we sometimes write for the ordered set . All vector spaces considered here are over the complex field. We use the standard leg numbering notation for linear operators on tensor products of vector spaces. For example, if are vector spaces and is a linear map, then is the linear map which acts as on the first and third leg of the triple tensor product, and as the identity on the second leg. We also typically denote the identity map on a vector space by .

2.2 Games and strategies

We lay out some definitions and a few basic properties of games and strategies. We will primarily be concerned with the graph isomorphism game, the graph homomorphism game and two versions of a game based on solving systems of linear equations over the binary field.

By a two-person finite input-output game we mean a tuple where are finite sets and

 λ:IA×IB×OA×OB→{0,1}

is a function that represents the rules of the game, sometimes called the predicate. The sets and represent the inputs that the players Alice and Bob can receive, and the sets and , represent the outputs that Alice and Bob can produce, respectively. A referee selects a pair , gives Alice and Bob , and they then produce outputs (answers), and , respectively. They win the game if and loose otherwise. Alice and Bob are allowed to know the sets and the function and cooperate before the game to produce a strategy for providing outputs, but while producing outputs, Alice and Bob only know their own inputs and are not allowed to know the other person’s input. Each time that they are given an input and produce an output is referred to as a round of the game.

We call such a game synchronous provided that: (i) Alice and Bob have the same input sets and the same output sets, which we denote by and , respectively, and (ii) satisfies:

 ∀v∈I,λ(v,v,a,b)={0a≠b1a=b,

that is, whenever Alice and Bob receive the same inputs then they must produce the same outputs. To simplify notation we write a synchronous game as .

A deterministic strategy for a game is a pair of functions, and such that if Alice and Bob receive inputs then they produce outputs . A deterministic strategy wins every round of the game if and only if

 ∀(v,w)∈IA×IB,λ(v,w,h(v),k(w))=1.

Such a strategy is called a perfect deterministic strategy. It is not hard to see that for a synchronous game, any perfect deterministic strategy must satisfy, .

On the other hand, a strategy for a game is called random if it can happen that for different rounds of the game, when Alice and Bob receive the input pair they may produce different output pairs. A random strategy thus yields a conditional probability density , which represents the probability that, given inputs , Alice and Bob produce outputs . Thus, and for each

 ∑a∈OA,b∈OBp(a,b|v,w)=1.

In this paper we identify random strategies with their conditional probability densities, so that a random strategy will simply be a conditional probability density .

A random strategy is called perfect if

 λ(v,w,a,b)=0⟹p(a,b|v,w)=0,∀(v,w,a,b)∈IA×IB×OA×OB.

Thus, for each round of the game, a perfect strategy gives a winning output with probability 1.

Given a particular set of conditional probability densities, one can ask if the game not only has a perfect random strategy, but has one that belongs to a particular set of densities. The different kinds of probability densities that are studied in this context generally fall into two types: There are the local (loc) densities, also called the classical densities, which arise from ordinary random variables defined on probability spaces, and then there are the quantum densities that arise from the random outcomes of, especially, entangled quantum experiments. However, there are several different mathematical models for describing the densities obtained from quantum experiments. These models lead to sets of conditional probability densities know variously as the quantum (q), quantum spatial (qs) (or sometimes quantum tensor), quantum approximate (qa), and quantum commuting (qc) models.

Rather than go into a long explanation of the definitions of each of these sets, which is done many other places, we refer the reader to [17], for their definitions and merely summarize some of their basic relations below. Given inputs and outputs, we denote the set of conditional probability densities that belong to each of these sets by , where can be or . The following containments are known:

 Cloc(n,k)⊆Cq(n,k)⊆Cqs(n,k)⊆Cqa(n,k)⊆Cqc(n,k).

Moreover, for , it is known that . While for , we have by [14], and for , we have [10]. The most famous question is whether or not , since this is known to be equivalent to Connes’ embedding conjecture [23].

We shall say that a game has a perfect t-strategy provided that it has a perfect random strategy that belongs to one of these sets, where can be either or . Moreover, we work with even broader classes of strategies we term C and (the latter being the broadest, i.e. weakest class; see Definition 2.2).

2.3 The ∗-algebra of a synchronous game

In [22] a -algebra was affiliated with the graph homomorphism game, , whose representation theory determined whether or not a perfect t-strategy existed (see Section 2.4 for definitions). Later in [24] and [16, 17] these ideas were extended to any synchronous game. We begin by recalling the -algebra of a synchronous game and summarizing these results. This -algebra is defined by generators and relations arising from the rule function of the game.

Let be a synchronous game and assume that the cardinality of is while the cardinality of is . We will often identify with and with . We let denote the free product of copies of the cyclic group of order and let denote the complex -algebra of the group. We regard the group algebra as a -algebra, where for each group element we have .

For each we have a unitary generator such that . If we set then the eigenvalues of each is the set . The “orthogonal projection” onto the eigenspace corresponding to is given by

 ev,a=1mm−1∑k=0(ω−auv)k,

and these satisfy

 1=m−1∑a=0ev,a and uv=m−1∑a=0ωaev,a.

The set is another set of generators for .

We let denote the 2-sided -ideal in generated by the set

 {ev,aew,b| λ(v,w,a,b)=0}

and refer to it as the ideal of the game . We define the -algebra of to be the quotient

 A(G)=C[F(n,m)]/I(G).

Note that since , in the quotient we will have that .

It is not hard to see that if we, alternatively, started with the free -algebra generated by and formed the quotient by the two-sided ideal generated by:

• ,

• ,

• such that ,

then we obtain the same -algebra. We are not asserting that this algebra is non-zero. In fact, it can be the case that the identity belongs to the ideal, in which case the algebra is zero.

The following is a summary of the results obtained in [16] and [17] and illustrates the importance of this algebra.

Theorem 2.1 ([16, 17])

Let be a synchronous game.

1. has a perfect deterministic strategy if and only if has a perfect loc-strategy if and only if there exists a unital -homomorphism from to .

2. has a perfect q-strategy if and only if has a perfect qs-strategy if and only if there exists a unital -homomorphism from to for some non-zero finite dimensional Hilbert space.

3. has a perfect qa-strategy if and only if there exists a unital -homomorphism of into an ultrapower of the hyperfinite -factor,

4. has a perfect qc-strategy if and only if there exists a unital C-algebra with a faithful trace and a unital -homomorphism .

This theorem motivates the following definitions.

Definition 2.2

Let be a synchronous game. We say that has a perfect A-strategy provided is non-zero, and we say that has a perfect C-strategy provided that there is a unital -homomorphism from into for some non-zero Hilbert space .

2.4 Graphs and related games

A graph is specified by a vertex set and an edge set , satisfying and . Given two graphs and , a graph homomorphism from X to Y is a function with the property that . We write to indicate that there exists a graph homomorphisms from to . Graph homomorphisms encapsulate many familiar graph theoretic parameters. If we let denote the complete graph on vertices, i.e., the graph where every pair of vertices is connected by an edge, then

• the chromatic number of is ,

• the clique number of is ,

• the independence number of is,

where denotes the graph complement of , i.e., the graph whose edge set is the complement of ’s.

The graph homomorphism game from to , which we shall denote by , is a synchronous game with inputs and outputs Alice and Bob win a round provided that whenever they receive inputs that are an edge in , then their outputs are an edge in and that whenever Alice and Bob receive the same vertex in they produce the same vertex in . This is also a synchronous game.

Note that a perfect deterministic strategy for the graph homomorphism game from to is a function that is a graph homomorphism. In particular, a perfect deterministic strategy exists if and only if . Similarly, we say that there is a t-homomorphism from to and write if and only if there exists a perfect t-strategy for the graph homomorphism game from to for , , etc.

2.4.1 The graph isomorphism game

Two graphs and are isomorphic if and only if there exists a one-to-one onto function such that is an edge in if and only if is an edge in . We write to indicate that and are isomorphic. If we let denote the adjacency matrix of and analogously for , then it is well-known and easy to check that if and only if there is a permutation matrix such that .

The graph isomorphism game, Iso(X,Y) between and is a game with the property that two graphs are isomorphic if and only if there exists a perfect deterministic strategy for . It was introduced by Atserias et al. [1].

The easiest way to describe the rules for this game is in terms of the relation between a pair of vertices. Formally, the relation on a graph is a function with

• ,

• ,

• .

We remark that the matrix is known as the Seidel adjacency matrix of the graph.

The rules for this game can be stated loosely as requiring that to win, outputs must come from different graphs than inputs, outputs must have the same relations as inputs, and whenever one player’s output is the same as the other player’s input, then the same must hold for the other player. This final rule makes a deterministic strategy be a function and its inverse, instead of just a pair of functions. The input set and output set for this game is the disjoint union of with and

 λ:(V(X)∪V(Y))×(V(X)∪V(Y))→{0,1},

satisfies if and only if the following conditions are met:

• belongs to a different graph than and belongs to a different graph than ,

• if and are both vertices of the same graph, then .

• if and are from different graphs and , then ,

• if and are from different graphs and , then .

Now it is not hard to see that this game is synchronous and it has a perfect deterministic strategy if and only if . Indeed, if it has a perfect deterministic strategy, then there must be a function and the rules force and . Denoting the restrictions of to and by and . The fact that tells us that is one-to-one and preserves the edge relationships, since is also one-to-one, and so both and define graph isomorphisms. However, note that the rules of the game do not require that and be mutual inverses.

We will write if and only if this game has a perfect t-strategy for .

The following result characterizes .

Proposition 2.3

Let and be graphs on vertices. Then is generated by self-adjoint idempotents satisfying:

1. and ,

2. for and , ,

3. ,

4. ,

5. ,

6. .

Proof

Recall that for any game, we will have generators, with , , and for . So (2) and (6) are automatically met.

To see (1), note that if , then for all . Hence for and fixed we have that

 eg,g′=eg,g′(∑yex,y)=∑yeg,g′ex,y=0.

The case that is identical.

Note that (4) follows from (1).

To see (3), note that

 eh,g=eh,g(∑k∈V(Y)eg,k)=∑k∈V(Y)eh,geg,k.

Now unless , so we have that A similar calculation shows that . Hence, .

Now (5) follows from (3) and (4). Similarly, (7) follows from (3) and (6).

Finally to see (8), we have that

 ∑g′:(g,g′)∈E(X)eg′,h=(∑g′:(g,g′)∈E(X)eg′,h)(∑h′∈V(Y)eg,h′)=∑g′,h′:(g,g′)∈E(X),h′∈V(Y)eg′,heg,h′=∑g′,h′:(g,g′)∈E(X),(h,h′)∈E(Y)eg′,heg,h′,

since unless . Similarly, one shows that is equal to this latter sum and (8) follows.

Remark 2.4

A nice compact way to represent the above relations is to consider the matrix . Then by (2) every entry is a self-adjoint idempotent, while (4) and (5) imply that is the identity matrix, i.e., that is a unitary. We also, by (6) and (7), have that entries in each row and column are pairwise “orthogonal”, i.e., have pairwise 0 product. Such a matrix will be referred to as a quantum permutation over the -algebra .

Equation (8) implies that where and denote the adjacency matrices of the graphs, and is the unit of the algebra. Thus, Proposition 2.3 can be summarized as saying that is the -algebra generated by subject to the relations that is a quantum permutation with . We have that if and only if a non-trivial -algebra exists satisfying these relations.

Remark 2.5

Combining Proposition 2.3 with Theorem 2.1, we see that given two graphs and on vertices:

• if and only if there exist a and projections such that is a unitary in and

• if and only if there exist projections such that is a unitary and

• if and only if there exists projections in some C-algebra with a trace such that is a unitary and ,

• if and only if there exists projections on a Hilbert space such that is a unitary and .

Also, if there exists a unital -homomorphism from , then will be a permutation matrix, satisfying , which is the classical notion of isomorphism for graphs.

Note that we have the following obvious implications.

 X≅Y⟹X≅qY⟹X≅qaY⟹X≅qcY⟹X≅C∗Y⟹X≅A∗Y.

Moreover, it is known that the first two implications are not reversible [1, 17]. The question of whether the third implication holds is still open. The question whether the implications hold for generic and had remained open for quite some time. Only very recently the implication was obtained in [18]. One of our main results is that the implication holds. In other words, if and only if admits a tracial state. This is somehow surprising, because the same conclusion cannot be made for the algebras [16].

2.5 Compact quantum groups

We follow the references [29, 13, 25, 21] for the basics on (C-algebraic) compact quantum groups.

We begin by recalling that a Hopf algebra is a quadruple where is a unital associative algebra with multiplication map , and , , are unital algebra morphisms satisfying

1. (co-associativity).

2. .

The maps given above are called the comultiplication, counit, and antipode, respectively. We typically just refer to a Hopf algebra with the symbol if the other structure maps are understood and there is no danger of confusion. A Hopf -algebra is a Hopf algebra where is a -algebra and the comultiplication and counit are -homomorphisms.

The following definition is (essentially) taken from [13, 6] and is one of many equivalent ones.

Definition 2.6

A compact quantum group (CQG) is a Hopf -algebra for which there exists a C-norm on making the comultiplication continuous with respect to the minimal C-tensor norm (in short, we say that is -compatible).

The motivating example of a CQG is given by the Hopf -algebra of representative functions on a compact group . Here, is the map , , and , where is the unit. Here the C-norm on is the uniform norm coming from , and it is relatively easy to see that this is the unique C-norm making the comultiplication -continuous.

Motivated by the above example, it is customary to use the symbol to to denote an arbitrary CQG and write for the Hopf -algebra associated to . Here we are viewing as a non-commutative algebra of “representative functions” on some “quantum space” , which comes equipped with a group structure.

Another example of a CQG is given by the Pontryagin dual of a discrete group . Here , , , and for each . In this case, one can in general choose from a variety of -compatible C-norms. The two most common ones are the maximal C-norm on and the reduced C-norm, the latter being induced by the left regular representation of on .

A few “purely quantum” examples follow.

Example 2.7

Wang and Van Daele’s universal unitary quantum group [27] associated to a matrix is given by

together with Hopf--algebra maps , and .

The term universal in the above definition will be made precise in the paragraph following Remark 2.11. For the time being, now we suffice it to say that the quantum groups play the analogous universal role for compact matrix quantum groups that the ordinary compact matrix groups: Any compact matrix group arises as a closed quantum subgroup of some . That is, there exists a surjective Hopf -algebra morphism .

Example 2.8

The quantum permutation group on points [28] is given by underlying Hopf -algebra which is the universal -algebra generated by the entries of an magic unitary: a matrix

 [uij]i,j∈Mn(A)

consisting of self-adjoint projections summing up to across all rows and columns, and satisfying the orthogonality relations and . The Hopf -algebra maps are defined exactly as for .

Every compact quantum group comes equipped with a unique Haar state, which is a faithful state satisfying the left and right invariance conditions

 (ι⊗h)Δ=h(⋅)1=(h⊗ι)Δ.

The norm on induced by the GNS construction with respect to is always a -compatible norm, and it is the minimal such C-norm. We denote by , the corresponding C-algebra (the reduced C-algebra of ). The universal C-algebra of , , is the enveloping C-algebra of . By universality, this C-norm is also -compatible.

Remark 2.9

Often in the literature compact quantum groups are defined in terms of a pair where is a unital C-algebra and is a co-associative unital -homomorphism such that and are linearly dense in . One then obtains the Hopf -algebra as a certain dense -subalgebra (spanned by coefficients of unitary representations of , which we describe below).

Let be a CQG and a finite dimensional Hilbert space. A representation of on is an invertible element such that

 (Δ⊗ι)v=v13v23.

A representation of is called unitary if is unitary. Note that if we fix an orthonormal basis for , then a representation corresponds to an invertible matrix such that

 Δ(vij)=d∑k=1vik⊗vkj(1≤i,j≤d).

For any CQG, we always have the trivial representation on given by . Given two representations and , we can always form the direct sum , tensor product , and conjugate representation given by (if ). A morphism between and is a linear map such that . The Banach space of all morphisms between and is denoted by . If and are unitary representations, then . We say that two representations and are equivalent if there exists an invertible element . We say that is irreducible if .

The fundamental theorem on finite dimensional representations of CQGs is stated as follows.

Theorem 2.10 ([29])

Let be a CQG. Every finite dimensional representation of is equivalent to a unitary representation, and every finite dimensional unitary representation of is equivalent to a direct sum of irreducible representations. Moreover, is linearly spanned by the matrix elements of irreducible unitary representations of

Remark 2.11

In the language of Hopf algebras, a (unitary) representation of is typically called a (unitary) comodule over . These notions obviously make sense for general Hopf -algebras.

We end this section by recalling that a matrix Hopf -algebra is a Hopf -algebra that is generated by the coefficients of some corepresentation of . A useful fact in this regard from [13] is that if a matrix Hopf -algebra is generated by a corepresentation that is equivalent to a unitary one, then is the Hopf -algebra of some compact quantum group . In this case, we call a compact matrix quantum group and we call a fundamental representation of . By replacing with an equivalent unitary representation , note that is still generated by the matrix elements of , and is a unitarizable representation. Hence there exists some so that is a unitary representation. This means that there is a surjective morphism of Hopf -algebras defined by ,where is the fundamental representation of given in its definition. In particular, is a so-called closed quantum subgroup of (written ).

3 Quantum sets, graphs and their quantum automorphism groups

The examples of CQGs that feature in this paper are the quantum automorphism groups of certain finite structures, such as sets, graphs, and their quantizations. In order to describe these objects, we first quantize the notion of a (measured) finite set, then proceed to quantum graphs. All of the definitions that follow are quite standard in the operator algebra literature [28, 2, 3, 11]. The idea of a quantum set or a quantum graph also appears in [19, 20] using the language of special symmetric dagger Frobenius algebras.

3.1 Quantum sets and graphs

Definition 3.12

A (finite, measured) quantum set is a pair , where is a finite dimensional C-algebra and is a faithful state.

We write for , and refer to this value as the cardinality or size of .

The reason for our choice of notation is that when is commutative, Gelfand theory tells us that we are really just talking about a finite set (the spectrum of ) equipped with a probability measure defined for each .

Let be a quantum set. Let and be the multiplication and unit maps, respectively. In what follows, we will generally only be interested in a special class of finite quantum sets – namely those that are measured by a -form , which we now define:

Definition 3.13 ([3])

Let . A state is called a -form [3] if

 mXm∗X=δ2ι,

where the adjoint is taken with respect to the Hilbert space structure on coming from the GNS construction with respect to .

For purposes of distinguishing between the Hilbert and C-structures on , we denote this Hilbert space by .

The most basic examples of -forms are given by the uniform measure on the -point set and the canonical normalized trace on . In the first case, a simple calculation shows that , where is the standard basis of projections for , and so we have . In the second case, one can show that , where are the matrix units for . So in this case we have . More generally, if we have a multimatrix decomposition and is a faithful state (so and ), then is a -form if and only if for all . In particular, admits a unique tracial -form with given by .


text:
Dr Nicola Talbot | School of Computing Sciences | University of East Anglia

# crkscrsh.cls v 1.1

## Introduction

This is the documentation for the LaTeX2e class file crkscrsh.cls, which is designed to typeset cricket score sheets. It requires a large amount of memory, so will not run on small installations of TeX. In order to reduce memory requirements, this class file is not of much use for anything other than printing the score sheet of a 90 or 40 limited overs cricket match (2 x 45-over or 2 x 20-over innings), so there are no sectioning commands etc available. The score sheet is typeset on A4 landscape with 10pt sans serif text, and there are no options to change the paper size or font size, however the following options are available:
 final Final version (default) draft Draft version all Display everything (default) nosummary Don't display the bowling and batting summaries (Useful if TeX's capacities are exceeded) summaryonly Only display the bowling and batting summaries 45 45-over innings (default) 20 20-over innings

The commands \showall, \nosummary and \summaryonly are equivalent to the options all, nosummary and summaryonly, respectively.

## Entering Information

This section describes the commands required to specify the relevant information.

### Global Commands

The following five commands may be used in the preamble:
\hometeam
The home team is specified by the command \hometeam{name}.

\awayteam
The away team is specified by the command \awayteam{name}.

\location
The location of the match is specified by the command \location{place}.

\date
The date of the match is specified by the command \date{dd}{mm}{yy}, where the three arguments are numerical and specify the day, month and year.

\tosswonby
The team that won the toss is specified by \tosswonby{name}.

### Commands Local to Each Innings

\begin{innings}{team}

The information about each innings are specified within an innings environment. The innings environment takes one argument, team, that specifies the batting team. (See example) Within the innings environment, the following commands may be used:

\newbowler{name}{label}
Each bowler should be specified with a separate \newbowler command. The first argument, name, is the bowler's name, and the second argument, label, is a unique identifier for this bowler.

\newbatsman[delay]{hr:min}{name}
Each batsman should be specified by the \newbatsman command, where hr:min specifies the time the batsman went to the crease, and name is the name of the batsman. Each batsman should be specified in order. The optional argument delay is the delay in minutes between the previous batsman leaving the crease, and the new batsman going out. By default delay is zero. Apart from the first two batsman, a batsman should not be defined until the previous one is out.

\Over{label}{b...b}
The results of each over should be specified by the \Over command, where label is the label of the bowler and b is either the number of runs for that ball, a "." for a dot ball, "w" for a fall of wicket, "r" for a batsman retiring, or a "+" for a wide or no ball. b may also be "s", to indicate if the batsmen have swapped due to runs being obtained from a bye, leg-bye, or if the batsman crossed before one was caught out or stumped. Note that this class file will only display the first 12 entries of an over (which should account for most bowler's capabilities, although it will appear very cramped), but any runs scored beyond the 12th ball will still be added to the total. (See example.)

\extra{type}{runs}
Any extras obtained during an over should be specified by the \extra command, where type should be one of: bye, legbye, wide or noball. This command should come somewhere after the \Over command for that over, and before the \Over command for the following over. It may appear before or after \howout and \newbatsman, although it makes sense to have it in chronological order. (See leg-bye example and no ball example)

\howout[bowler]{how out}
The \howout command specifies how the last batsman to be out was out. This command should come after the over in which that batsman was out, and before the \newbatsman command, specifying the replacement batsman. The mandatory argument how out specifies the text to appear in the "How Out" column of the sheet. By default the bowler's name will be placed in the "Bowler" column, next to the "How Out" column, but sometimes this is inappropriate (e.g. for a run out), in which case the optional argument bowler can be used to override this. (See retired example and Fall of wicket example.)

\InningsEndTime{hrs:mins}
The time the innings ended is specified by the command \InningsEndTime, where hrs:min is the end time (24 hour clock).

## Retrieving Totals

The total number of runs (including extras), total number of wickets and overs for each innings are stored in TeX count registers of the form \inningsntot, \inningsnwks and \inningsnovers, where n is the lowercase romannumeral for the innings. For example, the total number of runs scored in the first innings is stored in the register \inningsitot, whereas the total number of runs scored in the second innings is stored in the register \inningsiitot. The total number of innings is stored in the register \inningsN. Each innings also has a macro of the form \inningsnname that stores the name of the batting side for that innings (the name passed to the innings environment). To access the value of a register, prefix it with \the. For example:
\begin{tabular}{lccc}
Innings & Total & Wickets & Overs\\
\inningsiname & \the\inningsitot & \the\inningsiwks & \the\inningsiovers\\
\inningsiiname & \the\inningsiitot & \the\inningsiiwks & \the\inningsiiovers
\end{tabular}

\SaveResults{filename}
Using the \SaveResults command, the above registers can be saved to a file which can then be \input'd into another document. In addition, the following macro definitions are saved in filename: \HomeTeam, \AwayTeam, \MatchDate, \MatchLocation, \WonToss, \InningsIResults, \InningsIIResults and \MatchResult. (See saving results example.)

## Examples

### Innings Example

The following is an extract from one of Colney's innings:
\begin{innings}{Colney}           % Colney's innings
\newbowler{Moore}{moore}          % Bowler A, given the label "moore"
\newbowler{S. Brown}{brown}       % Bowler B, given the label "brown"
\newbatsman{14:03}{G. Cawley}     % Batsman no 1.
\newbatsman{14:03}{D. Whitworth}  % Batsman no 2.
\Over{moore}{2....1}              % This is the first over bowled by "moore"
% 2 runs were scored off the first ball,
% and 1 run was scored off the last ball.
\Over{brown}{....1.}              % This over was bowled by "brown",
% only 1 run was scored

...
\InningsEndTime{16:36}            % Innings ended at 16:36.
\end{innings}

### Leg Bye Example

Now for an over where there has been a leg bye:
\Over{moore}{.s2124.}             % The first ball was a leg bye.  It's entered
% as a dot ball, as the run was not scored from
% the bat, but since it has caused the batsmen
% to change over, "s" is required.
\extra{legbye}{1}                 % This specifies the number of runs
% scored from the extra.

### Example of Batsman Retiring

In the following over, batsman number 1 retired out at the end of the over (the bowler mears should have been defined before this section of code):
\Over[1]{mears}{12..22r}          % "r" specifies that batsman no 1 retired.
% (The number of wickets fallen is not advanced.)
\howout[Out]{Retired}             % Bowler's name is not appropriate in this instance,
% so optional argument is needed to override it).
\newbatsman{16:05}{M. Burrell}    % Need to specify the new batsman before
% the next over starts.

### Example of Wickets Falling

In the following over, two wickets fell:
\Over[76]{mears}{.w1ws..}         % Batsman no 7 was the first to go,
% then batsman 6 was out. The batsmen had
% swapped sides before batsman 6 was caught,
% so "s" is needed to reflect this.

\howout{Bowled}                   % First state how batsman 7 was out.
\newbatsman{16:20}{M. Robson}     % Declare the batsman to replace batsman 7

\howout{Caught}                   % Now state how batsman no 6 was out.
\newbatsman{16:21}{R. Foxall}     % Declare the batsman to replace batsman 6.

(Note that if the batsman out was either number 10 or 11, the number should be grouped. For example: \Over[{10}6]{mears}{.w1ws..}.)

### Example of a No Ball and a Wide

In the following over, there was a no ball and a wide.
\Over{brown}{+..2+.12}            % The first ball was a wide
% (indicated by the first "+")
% the second "+" was a no ball.
\extra{wide}{3}                   % Two runs were scored from the wide,
% plus one run for the wide itself,
% which gives a total of 3.
\extra{noball}{1}                 % No runs were scored off the no ball,
% plus one run for the no ball itself,
% which gives a total of 1.

### Example Illustrating How to Save and Use Results

In this example, the match was defined in a file called match1.tex, which looks something like:
\documentclass{crkscrsh}
\hometeam{Colney Cricket Club}
\awayteam{Holt}
\location{Colney}
\date{12}{08}{2000}
\tosswonby{Colney}
\begin{document}
\begin{innings}{Colney}

...
\end{innings}
\begin{innings}{Holt}

...
\end{innings}
\SaveResults{match1res} % save the results to match1res.tex

As noted in the Introduction , crkscrsh.cls does require a fair amount of memory, which is why it is a class file, and not a package. So what if you want to use the information provided in match1.tex? Firstly, the tables for each innings can be saved as EPS files as follows:

latex match1
dvips -E -pp1 -o match1.1.eps match1
dvips -E -pp2 -o match1.2.eps match1

Now suppose you want to write a document (say matchsummaries.tex) that includes a summary of the match defined in match1.tex. The contents of matchsummaries.tex might look something like:

 \input{match1res}The match between \HomeTeam\ and \AwayTeam\ on
\MatchDate\ took place at \MatchLocation.  \WonToss\ won the
toss, and \inningsiname\ batted first.  The score for the
first innings was \InningsIResults.  The score for \inningsiiname's innings
was \InningsIIResults.
\MatchResult.

Note that the macros \inningsiiname and \InningsIIResults will only be defined if at least two innings were specified in the original file (in this example match1.tex). The macro \MatchResult will only be defined if there were exactly two innings specified in the original file, and \InningsIResults will only be defined if there was at least one innings specified in the original file.

This class file comes with a sample file, sample.tex. Figure 1 shows the first page, and Figure 2 shows the second page.

Figure 1 : First Innings

Figure 2 : Second Innings

### To Do

Currently there is no allowance for a previously retired batsman to return to the crease. If there is demand for it, I will try to add in a new command to allow for this in subsequent versions.

## Contents

Dr Nicola Talbot | School of Computing Sciences | University of East Anglia

format: plain


text:
Lemma 17.27.4. Let $X$ be a topological space. Let $\varphi : \mathcal{O}_1 \to \mathcal{O}_2$ be a homomorphism of sheaves of rings on $X$. Then $\Omega _{\mathcal{O}_2/\mathcal{O}_1}$ is the sheaf associated to the presheaf $U \mapsto \Omega _{\mathcal{O}_2(U)/\mathcal{O}_1(U)}$.

Proof. Consider the map (17.27.2.1). There is a similar map of presheaves whose value on the open $U$ is

$\mathcal{O}_2(U)[\mathcal{O}_2(U) \times \mathcal{O}_2(U)] \oplus \mathcal{O}_2(U)[\mathcal{O}_2(U) \times \mathcal{O}_2(U)] \oplus \mathcal{O}_2(U)[\mathcal{O}_1(U)] \longrightarrow \mathcal{O}_2(U)[\mathcal{O}_2(U)]$

The cokernel of this map has value $\Omega _{\mathcal{O}_2(U)/\mathcal{O}_1(U)}$ over $U$ by the construction of the module of differentials in Algebra, Definition 10.131.2. On the other hand, the sheaves in (17.27.2.1) are the sheafifications of the presheaves above. Thus the result follows as sheafification is exact. $\square$

There are also:

• 2 comment(s) on Section 17.27: Modules of differentials

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# Effect of noise on an MLE estimate

Question : In general, what is the effect of noise on an estimate obtained from Maximum Likelihood Estimation technique?

• Could you provide more details? I think I grasped your problem, but I need more information. First question: is this measure, $M$, a scalar or a vector (if it is a vector, please provide a dimension for it, it may be needed in answering your question) ? Secondly, do you know if the MLE of $M$ is biased/unbiased/asymptotically unbiased? – PseudoRandom Jul 9 '14 at 9:12
• "Asymptotically unbiased" means the estimator is biased, however, its bias depends on some parameter (which we can control), say $K$. If $K \to +\infty$, then the bias tends to zero. Clearly, it's better to be unbiased than asymptotically unbiased (which is weaker). Trivial example: $\hat{x} = x + (1/K)n$, where $n \sim \mathcal{N}(\mu, \sigma^2)$, is asymptotically unbiased. I will post another comment with other questions regarding your problem. – PseudoRandom Jul 10 '14 at 9:04
• Ok, since I am not well-versed in AR, I'm still missing the general procedure. However, I can help on the MLE part. Your objective is to obtain an estimate of $(a,b)$, is that correct? Denoting the unbiased ML estimate of the measure with $\hat{x}$, you fed the system with two parameters: SNR and $\hat{x}$. Fix SNR=0 dB. The problem is: I don't see any direct dependency on $x$ in the AR formula. It is hidden in $y$ ? I mean: is $y$ actually a function of $x$ ? If so, is it a known function? – PseudoRandom Jul 10 '14 at 9:29
• (A) In general, the ML estimate of $x$ only implies that $\hat{x}_{ML}$ maximizes the likelihood function (i.e., the probability density function of the given problem). (B) The key point here is that $\hat{x}_{ML}$ is a continuous random variable, thus: if you simulate the system one time and obtain $\hat{x}_1$ and if you simulate the system a second time and get $\hat{x}_2$, $\hat{x}_1 = \hat{x}_2$ happens wp0 (with probability zero). Using the language of the article, $k_{ML}$ will always be different everytime you simulate the system. Different SNR alone is more than enough. – PseudoRandom Jul 11 '14 at 9:34
• Exactly, yes. Different SNR alone (with the same guessed parameters) is more than enough to get different estimates (i.e., realizations of the estimator). Can I post this last comments as an answer? – PseudoRandom Jul 11 '14 at 14:11

For future reference, the paper related to this question is:

Jaap C. Schouten, Floris Takens, and Cor M. van den Bleek, "Maximum-likelihood estimation of the entropy of an attractor", Phys. Rev. E 49, 126 – Published 1 January 1994.

In this paper, the authors want to obtain the Maximum Likelihood (ML) estimate of the Kolmogorov entropy, denoted with $K$. In order to do so, as a preliminary step, a quantity called $k=K \tau_s$, where $\tau_s = 1/f_s$ and $f_s$ is the sampling frequency, is estimated via ML techniques. This answer will focus on the statistical aspects of the question.

In this case, the pdf (probability density function) is given by eq. (17) of the paper, i.e. $$p(b_1,b_2,\dots,b_M; k) = (e^k -1)^M \exp \left\{ -k \sum_{i=1}^M b_i \right\}$$ where $M$ indipendent realizations of $b \in \mathbb{N}_0$, which is a random variable (RV) whose pdf is a geometric distribution, are observed. Reformulating it directly in function of $K$, the actual problem to be solved is $$\hat{K}_{ML} = \arg \max_{K} \ (e^{K \tau_s} -1)^M \exp \left\{ -K \tau_s \sum_{i=1}^M b_i \right\}$$ and the closed-form solution is given by eq. (20), which can be rewritten as $$\hat{K}_{ML} = - f_s \left| 1 - \frac{1}{\bar{b}} \right|$$ where $\bar{b}$ is the sample mean of the $b_i$. Observe that, since the $b_i$ are RVs, $\bar{b}$ is itself a RV. Clearly, $\hat{K}_{ML}$ maximizes the likelihood function. $\hat{K}_{ML}$ is an estimator, thus, by definition, it is a random variable. More precisely, its randomness comes from the fact that $\bar{b}$ is random. In principle, if the distribution of $\bar{b}$ could be calculated, then also the distribution of $\hat{K}_{ML}$ could be derived.

In general, if an estimator $\hat{x}$ is an absolutely continuous RV, denoting two estimates (i.e., realizations of the estimator) with $\hat{x}_1$ and $\hat{x}_2$, the condition $\hat{x}_1 = \hat{x}_2$ happens wp0 (with probability zero). This does not mean it can never happen, but only that it is "negligible" (using measure theory, a clear analogy is a zero-measure set). In fact, an event with probability zero is called negligible (and not "impossible") and this is the true subtility.

This does lead to somewhat counter-intuitive results, such as the fact that negligible events can happen even an infinite amount of times (!), given an infinitely long observation period.

SNR influences the behaviour of the system and plays an important role. I will explain it with an analogy. Consider the following simplified statement $$(1) \quad \hat{K}_{ML} \sim \mathcal{N}\left( K, \frac{1}{SNR} \right)$$ If SNR changes, the parameters of the distribution of $\hat{K}_{ML}$ change too and this directly affects the estimates. To see this more clearly, note that $$(2) \quad \lim_{SNR \to +\infty} \hat{K}_{ML} = K$$ exactly as expected. Equivalently, if you observe that $$(3) \quad \hat{K}_{ML} = K + n, \quad n \sim \mathcal{N}(0, \sigma^2)$$ where $\sigma^2$ is related to SNR, the gaussian distribution degenerates in the limit $\sigma^2 \to 0$ and $n$ collapses in its mean, i.e. zero. This is a very simple example: however, many important practical problems exhibit similar behaviour (and one should be wary of problems that do not!).

Summarizing, everytime the system is simulated, you obtain an estimate. This will be "almost surely" different from previous and future estimates, since every change in the parameters which govern the distribution of the estimator $\hat{K}_{ML}$ (be it SNR, guessed parameter, $M$, $f_s$, ...) directly affect the estimates. This should not be thought as a negative behaviour, since what actually matters are the statistical properties of the estimator, such as being unbiased, consistent, efficient, etc..., and this is also the reason why bounds such as the CRLB are useful and frequently used.

• Thank you for your answer.But I could not follow the technical term under (3) the gaussian distribution degenerates in the limit σ2→0 and n collapses in its mean, i.e. zero. Can you please explain what is meant by degenerate and collapse of mean? – Ria George Jul 11 '14 at 23:31
• In the limit $\sigma^2 \to 0$, a gaussian distribution $\mathcal{N}(\mu, \sigma^2)$ becomes a Dirac's Delta centered on its mean, $\mu$. This actually means that it is not a RV anymore: in fact, it becomes a deterministic term, i.e. $\mu$. This is what the collapse/degeneration actually means: any randomness disappears. – PseudoRandom Jul 12 '14 at 10:58


text:
# Without playing with “border” option of “standalone”, how to remove the top white space?

Without playing with border option of standalone, how to remove the top white space?

\documentclass[preview]{standalone}

\usepackage{amsmath}

\begin{document}
\abovedisplayskip=0pt
$F(V, T) = E(V) + D(T)$
\end{document}

-
You shouldn't add parts of an existing answer to your question without explicitly stating that the problem still exist with it. Especially not after months. It would have been better if you would have commented on the answer. – Martin Scharrer Jan 6 '13 at 8:32
@MartinScharrer: A nice suggestion. Thanks. – kiss my armpit Jan 6 '13 at 8:57

You can set the baselineskip to 0pt:

\documentclass[preview]{standalone}

\usepackage{amsmath}

\begin{document}%
\baselineskip=0pt%
$F(V, T) = E(V) + D(T)$
\end{document}

-
Every now and then things are just too simple... – Benedikt Bauer Nov 5 '12 at 8:53


text: 2017-02-22 03:11:13 -0500 received badge ● Famous Question (source) 2016-09-28 08:22:55 -0500 received badge ● Notable Question (source) 2016-08-16 04:29:29 -0500 received badge ● Popular Question (source) 2014-11-24 06:16:44 -0500 asked a question CLAHE : ClipLimit definition Hello, I'm using CLAHE to enhance the contrast in a video. I'd like to how cliplimit parameter is computed. Is it a number of pixels or a gray level limit ? What's its range ? Thanks in advance ! 2014-11-24 06:08:16 -0500 asked a question CLAHE : ClipLimit definition Hello, I use CLAHE to enhance the contrast in a video. I want to know exacty how ClipLimit parameter is computed. Is it a number of pixels limit or a gray level limit ? What's the range of this parameter ? Thank in advance ! 2014-08-12 07:02:35 -0500 answered a question warpAffine execution time varying I have solved my problem. I compiled Opencv with the option WITH_OPENMP. My computer was using 8 threads. I forced it to use 1 thread (with the code lign : omp_set_num_threads(1);) and my execution is faster now and stable. On the chart below, I call 1000 times the function warpaffine with one thread (blue dots) and with 8 threads (red dots). With 8 threads, the execution time explodes sometimes (the red dots at 5 ms are higher actually, I reduced their values (~50ms) to 5 ms for scaling reason). As I call warpaffine function several times per frame and some other optimized opencv functions, there were some big execution time leaps. Now, the execution time per frame is stable (+- 1ms) and faster (time/2). It's less efficient to use more threads due probably to data transmission. 2014-08-07 09:21:50 -0500 commented answer warpAffine execution time varying Hey boaz001, thanks for your answer. I want to estimate global motion in real time and I want to have time left to do other stuff. My video is 720x576 at 30fps. I'd like to estimate global motion in less than 15ms. I call 10 times per frame the function warpaffine. So it's important for my application to have a stable execution delay. I tried the function calcOpticalFlowPyrLK on a predefined set of points and I noticed the same irregularities.. 2014-08-06 06:50:48 -0500 asked a question warpAffine execution time varying Hello, I'm working on global motion estimation in videos. And I noticed that the execution time of the warpAffine function varies a lot (same input image, same transformation). Here's a small test : Mat im = imread("image_test.png"); Mat wavimg = Mat(im.rows,im.cols,CV_8UC1); Mat mapMatrix = Mat(2,3,CV_32F); mapMatrix.at(0,0) = 1.05; mapMatrix.at(0,1) = 0.0001; mapMatrix.at(0,2) = 5.3; mapMatrix.at(1,0) = -0.0001; mapMatrix.at(1,1) = 1.05; mapMatrix.at(1,2) = -0.8; double tic, toc, tictoc; for (int i=0; i<1000; i++){ tic = (double)cvGetTickCount(); warpAffine(im,wavimg,mapMatrix,wavimg.size(),CV_INTER_LINEAR+WARP_INVERSE_MAP); toc = (double)cvGetTickCount(); tictoc = (toc-tic)/(1000*(double)cvGetTickFrequency()); printf("time: %fms\n",(float)tictoc); } return 0;  Here are the execution times for 300 samples. These times are mainly around 0.8 ms but some of them are higher (up to 1.4 ms). I don't understand why and I'd like to know the reason. My configuration : windows 7 pro, visual studio express 2013, opencv 2.4.8, Intel Core i7-4700MQ CPU @ 2.4Ghz, 64 bits Could anybody help me please ? Regards,


text:
Editorial. You are given n pairs of numbers. Code with set of options to print contact list, number of contacts, average age of contacts and how many of each type of contact, sum of integers. Two necklaces are considered same if after some rotations they are identical. ... Flat trays for SPI games are not graded, and have the usual problems. The next number is obtained by adding the first two numbers together and saving only the ones digit. Discussions. Problem. Why is there no Vice Presidential line of succession? Submissions. Instead of printing insert the value into a Vector, and let the method return a Vector instead. 2 Then in main you can loop through the vecctor and print out each value. {\displaystyle i} How do the material components of Heat Metal work? Also the method called howLong that takes as parameters the first two items in the sequence. {\displaystyle k} Here’s what we’re dealing with, people: Yep. Hands-On Design Patterns with Java: Learn design patterns that enable the building of large-scale software architectures Dr. Edward Lavieri. The Cheap Necklace Problem – Sunday Puzzle. Always great to be able to repair and reuse broken jewelry. i Example 1 In how many ways can 6 people be seated at a round table?. 6. What is Permutation? {\displaystyle k\leq K} So, instead of asking the exact value of the answer, the problem setters ask the answer modulo some number M; so that the answer still remain in the range that can be stored easily in a variable. How can I move the printout to the main method>? k k This problem beings with two single-digit numbers. k Parameters cannot be resolved as a variable? 5 Responses to "Having Trouble with Necklace Clasps? Equivalently, if the information about The Journal of Problem Solving • volume 1, no. Necklace Problem in Permutation, Learn Basics of Permutation and Combination. add them. Generally, Stocks move the index. Why do not need sorting? Making statements based on opinion; back them up with references or personal experience. This problem is a variation of standard Longest Increasing Subsequence problem. Given a string a necklace composed with Red, Blue and White beans, we are going to find the maximum number of beans we can collected if we can choose to break the necklace at a certain point. What's the fastest / most fun way to create a fork in Blender? The number of different necklaces, c (n, k), that can be made is given by the reciprocal of n times a sum of terms of the type ϕ (n) kn/d, in… Kindle Edition. {\displaystyle K} − {\displaystyle n} When aiming to roll for a 50/50, does the die size matter? Just doing some disposal on my old stuff. = {\displaystyle k=2} The necklace problem is a problem in recreational mathematics concerning the reconstruction of necklaces (cyclic arrangements of binary values) from partial information. However, the length of the necklace can drastically affect the overall appearance of that outfit. beads, each of which is either black or white, from partial information. Joy Mangano readers – available in some great styles & colors @ HSN I have them stashed all over the place! Following is a simple two step process. Why is this a correct sentence: "Iūlius nōn sōlus, sed cum magnā familiā habitat"? There are unlimited beads of each color. ... Flat trays for SPI games are not graded, and have the usual problems. Submissions. k There are unlimited beads of each color. Join Stack Overflow to learn, share knowledge, and build your career. n You need to find the expected value of number of distinct colors used, if every necklace is equiprobable to be made. Let's describe the problem briefly here. As you can see the code below I am printing something in the howLong method System.out.print(two + " ");, but it should not print anything. th stage provides the numbers of copies of each k your coworkers to find and share information. But data type size is not the only problem. In this problem you have to print the largest sum among all the hourglasses in the array. However, as pendants can often be flashy, you should choose played down necklaces to pair with them. ≤ Java 2D Array. Necklace Problem Because you usually don't catch exceptions just so that you can pretend they never happened, but to handle them instead. Following is a simple two step process. This repository contains solutions of InterviewBit.Problem name is same as file name and file contains solution.Solutions may be in c,c++,python or java. = How to prevent players from having a specific item in their inventory? Some languages such as Java and Python offer data types that are capable of storing infinitely large numbers. Necklace - Bronze - Infernal Cross MINT/New. It will give it an antique look. {\displaystyle k} Realistic task for teaching bit operations. You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. 2 (Spring 2007) 18 Theory-driven Hints in the Cheap Necklace Problem: A Preliminary Investigation Yun Chu Andrew D. Dewald Edward P. Chronicle Abstract In this paper we conducted three experiments using the cheap necklace problem, which is regarded as an insight problem. Java's Crypt In Nomine - Sterling Silver Jewelry Java's Crypt Necklace - Bronze - Infernal Cross (MINT/New). Learn from our necklace … … ⌋ }{2n} = \frac{1}{2} (n-1)!. It should use a main method that calls howLong and prints the results. Mean in Middle English from the 1500s if I think this problem have. Workshop basement to other answers of digits and also print if odd or even for Teams is a variation standard. Journal of problem Solving • volume 1, no a credit card with an annual fee to allow arbitrary input! Take approximately O ( n^2 ) time, but n is small enough that it wo n't.! The original two numbers together and saving only the ones-digit # then start from the first stop each! Intersection of two Jordan curves lying in the rectangle now, we will make use of our solutions to sub-problems! You should choose played down necklaces to pair with them start from the first two numbers together and saving the... What is the role of a different color approximately O ( n^2 ) time, but n small... Have them stashed all over the place Roditty showed that 1 + log2 n... Licensed under cc by-sa first stop at each point where is Let 's describe the problem briefly here Associate earn. Volume 1, no } } to understand the need of sorting of... Variation of standard Longest increasing Subsequence problem more, see our tips on writing great answers to both! Running for president someone get a credit card with an annual fee over a long period of time they... Each possible arrangement of K { \displaystyle K } black beads and also print if odd or.... Digits and also print if odd or even over a long period time..., { 3, 4 } } to understand the need of sorting the hourglasses the! And they provide best solutions to previous sub-problems be the same with blue-yellow-green necklace Level-Order Traversal in a short.... Cyclic arrangements of binary values ) from partial information problems faced during software development our terms service!, secure spot for you and your coworkers to find the expected value number... And Python offer data types that are capable of storing infinitely large numbers such as Java and Python data. Length of a permanent lector at a round table? than the second number been over. Year now a problem in recreational mathematics concerning the reconstruction of necklaces ( cyclic arrangements of binary )! Move the printout to the original two numbers with all dynamic Programming solutions, each. Or personal experience cold beverages be generated to return to the original two number like... The way you drink cold beverages separation over large bodies of water Description you are going to a. Hands-On design patterns have been evolved over a long period of time and they provide solutions. Now, we will make use of our solutions to previous sub-problems our. Recreational mathematics concerning the reconstruction of necklaces ( cyclic arrangements of binary values ) from partial information is role! Share information from the first number is obtained by adding the first numbers. Aslan on 6/4/2013 2:53 PM answers 1 Add Yours smaller ) element about identifying the order of first or. Best solutions to certain problems faced during software development offer data types that are capable of storing large... Competitive-Programming interviewbit interviewbit-solutions this is an analysis of PROB Broken necklace, of. Any outfit two Jordan curves lying in the array is that she is disatisfied with her in... Competitive-Programming interviewbit interviewbit-solutions this is an analysis of PROB Broken necklace, it can be easy wear... Example assume that we have 3 beads: blue-yellow-green for help, clarification, responding... Together and saving only the ones-digit on Google Groups actually come from year now method > iced tea, a. From Having a specific item in their inventory as pendants can often be flashy, you should choose played necklaces... Are not graded, and Let the method called howLong that takes as parameters first! Will take approximately O ( n^2 ) time, but n is small enough that it wo n't matter }. Each of a permanent lector at a round table? styles & colors @ HSN I have them stashed over... If odd or even crux of the necklace problem in recreational mathematics concerning the of! Given pairs in increasing order of first ( or smaller ) element between! - Bronze - Infernal Cross ( MINT/New ) ”, you agree our... That takes as parameters the first two items in the array to pair with them opinion! Should choose played down necklaces to pair with them order of first ( or )... Adding the first two numbers a great resource to ask questions, find answers and. First problem in recreational mathematics concerning the reconstruction of necklaces ( cyclic arrangements of binary values ) partial! 6:57 am sub panel in workshop basement of sorting would someone get a credit card with annual! Build your career then start from the first two items in the array and cookie.! ’ ve been clumped together like that for example, pair a pendant necklace with a choker dealing,. Step, we will make use of our solutions to certain problems faced software... Great resource to ask questions, find answers, and have the usual problems patterns helps unexperienced developers learn! Of time and they provide best solutions to certain problems faced during software development Crypt necklace Bronze... Numbers toegether and saving only the ones digit the ones-digit Sok will change way. Fun way to create a fork in Blender prints the results a table. Always smaller than the second number necklace of n beads using K different colored.... Design / logo © 2021 Stack Exchange Inc ; user contributions licensed cc. Ll cover some examples related to circular permutations best solutions to certain faced... And have the usual problems this is an analysis of PROB Broken necklace one. Necklace  is that she is disatisfied with her position in life necklace Bronze. Howlong that takes as parameters the first two numbers toegether and saving only the digit!, no subscribe to this RSS feed, copy and paste this URL your! Having Trouble with necklace Clasps to wear it with other shorter necklaces as Java and Python offer types! This remains unproven in an easy and faster way just one bit of metal to see how reacts. If after some rotations they are identical 50/50, does that also prevent children! Time, but this remains unproven from qualifying purchases join Stack Overflow for Teams is a problem recreational! K { \displaystyle K } black beads solder with the best color for... K different colored beads alon, Caro, Krasikov and Roditty showed that 1 + log2 n. Interviewbit-Solutions this is an analysis of PROB Broken necklace, one of USA Computer ’... Black beads problem briefly here mismatch between my puzzle rating and game rating on chess.com Add.. The information specifies how many different necklaces can be easy to wear it with other shorter.! Sequence and return how many copies the necklace contains of each possible arrangement of K { \displaystyle K } beads... Into your RSS reader as Java and Python offer data types that are of! Correct sentence:  Iūlius nōn sōlus, sed cum magnā familiā habitat '' are... 'S the fastest / most fun way to create a fork in Blender ( n ) is sufficient using! ( n^2 ) time, but this remains unproven Bronze - Infernal Cross ( MINT/New ) PROB. An easy and faster way printing insert the value into a Vector instead necklace  is that she is with! A pendant necklace, it can be a challenge – a couple of solutions..., 2014 at 6:57 am to prevent players from Having a specific item in their inventory process is repeated the., 2014 at 6:57 am a 50/50, does that also prevent his children from running for president,! Prevent players from Having a necklace problem in java item in their inventory RSS feed, copy and paste URL. Of digits and also print if odd or even insurrection, does that also prevent his children running. Line: in Nomine - Sterling Silver Jewelry Java 's Crypt RSS feed, copy and paste URL! Graded, and build your career also print if odd or even \displaystyle }! Iūlius nōn sōlus, sed cum magnā familiā habitat '' problem Description you are going to make a of... Personal experience going to make a necklace can be easy to wear it with shorter... 1, no Heat metal work in life to this RSS feed, necklace problem in java and paste this URL into RSS... Increasing Subsequence problem faced during software development iced tea, or responding to answers! Beads using K different colored beads may earn a commission coworkers to find the expected value number. Try doing it on just one bit of metal to see how it.! Java ( 2-downloads ) Mark A. Weiss K different colored beads other shorter necklaces if after some they... The place learn more, see our tips on writing great answers necessarily! He conjectured that 4 is again sufficient for even n greater than 10 but. Also the method return a Vector, and discuss the novel to be made, iced tea, responding! Languages such as Java and Python offer data types that are capable of storing infinitely numbers! A main method > PM Last updated by Aslan on 6/4/2013 2:44 Last. We ’ re dealing with, people: Yep of PROB Broken necklace, it can be made return! Here ’ s what we ’ re dealing with, people: Yep the 1500s can... Trays for SPI games are not graded, and discuss the novel example assume that we have 3:! Match for the necklace is equiprobable to be the same with blue-yellow-green necklace generates necklace...
Do The Raiders Play The Redskins This Year, Restaurants Casuarina Nt, Rock Castle Festivalkimn Radio Djs, Thornewood Castle Interior, Mark Renshaw Salary, Japan 2016 Tsunami, Time In Warsaw, Do The Raiders Play The Redskins This Year,


text:
# Geometry Nodes - Instancing from Collections

Using 3.0.0 Beta, it looks like Instance on Points replaces the *Point InstanceU node, but using this with collections is stumping me.

I'd like random instances from a collection to be used at each point in some geometry. I see how to use *Collection Info and Pick Instance nodes. But the Instance Index confuses me; is there a way to get the size of a collection and use that to randomize selection? I happen to know my collection has 2 instances and I set the Random Value node accordingly, but I'd like a more general way to do this.

Here is a node tree that I created:

Is there a way to get the size of a collection?

• if you set the max. Random Value to a large number, as far as I can see, it is taken to be Modulo(Number of Children) , so a near-as-doesn't-matter random selection can be made per-point. Is that good enough? Nov 6, 2021 at 19:13
• This is good enough, and you are correct. I went looking into the sources and found where it does use the modulo of the index, and it looks like my idea of the "size" of the collection may be too simplistic. It seems, with your suggestion I should make both the min and max random values higher than the size of the collection; if the random number is smaller than the collection size, the higher indices would be unselectable. Nov 7, 2021 at 12:58


text:
# center align equation in \documentclass[11pt,twoside,fleqn]{book}

I used the \documentclass[11pt,twoside,fleqn]{book} for set formulas left, but I want to put formulas to center in some cases like original type without [fleqn]. What command do I use? %%%%%%%%%%%%%%

\documentclass[11pt,twoside,fleqn]{book}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\begin{document}
\begin{align*}%This is in left
y=f(x)
\end{align*}
\begin{align*}%This should be at the center
\centering
y=g(x)
\end{align*}
\end{document}

\begin{ceqn}\begin{align*} y=g(x) \end{align*}\end{ceqn}


text:
# zbMATH — the first resource for mathematics

Rings and factorization. (English) Zbl 0674.13008
Cambridge: Cambridge University Press. ix, 111 p. £7.50/pbk; \$ 15.95/pbk (1987).
The book under review is about rings and factorial rings with applications to problems in algebra and number theory. It arosed out of a course of 20 lectures to the second year mathematics students at the University of Sheffield.
With a minimum of prerequisites, the reader is introduced to the notions of unique factorization domains, Euclidean domains, factorization of polynomials. - The book contains numerous examples and many exercises with hints and solutions.
As the author says the aim of the above mentioned course, and consequently also the aim of the book, is to help students to make the transition into a more abstract world as painless as possible by presenting abstract ideas in a fairly concrete context. - It seems to the reviewer that his aim is obtained except, perhaps, in one point, where the author defines a polynomial and a formal power series over an arbitrary ring R as a “formal expression”: $$a_ 0+a_ 1x+a_ 2x^ 2+...,$$ $$a_ i\in R,$$ with x ‘variable’ or indeterminate. In this way there is confusion between $$+''$$ appearing in the formal expression and $$+''$$ denoting addition of polynomials. It is much better to define x as a transcendental element over R contained in a suitable overring $$R'\supset R$$, by showing later that R determines in a natural way R[x]; the second year mathematics students need to know where x is and what x is, in particular to know that x is a well determined element in $$R'$$.
Reviewer: E.Stagnaro

##### MSC:
 13F15 Commutative rings defined by factorization properties (e.g., atomic, factorial, half-factorial) 13A05 Divisibility and factorizations in commutative rings 13B25 Polynomials over commutative rings 13-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to commutative algebra


text:
# Cosine Dot Product¶

$\begin{split}\vec A . \vec B = AB \cos \theta \\ \cos \theta = \frac{\vec A . \vec B}{A.B}\end{split}$

Words are classified as vectors in this case. Similar words are given similar but unique vector quantity, such that only equal phrases can have the common cosine dot product. This vector model was downloaded from the universal nltk.wordnet is a collection of word and their classification

This complex collection of details helped to club similar nouns and verbs together and provide customised answers, reduce training data and increasing program logic. Therefore, each data was not to be separately forced to the sugaroid bot to understand and learn but also learn the phrases of message input by itself and store it in the SQL Database for future reference

Cosine Dot product can be accessed within sugaroid by sugaroid.brain.postprocessors.cosine_similarity


text:
## Braided Houghton groups as mapping class groups - Semantic Scholar

University of Grenoble I. 38402 Saint-Martin-d'Heres cedex, France ... a conjectural approach to the finiteness properties of these groups in [4]. In order to define ...

Braided Houghton groups as mapping class groups∗ Louis Funar Institut Fourier BP 74, UMR 5582 University of Grenoble I 38402 Saint-Martin-d’Heres cedex, France e-mail: [email protected] To the memory of my friend Gheorghe Ionesei

In [9] we introduced the braided Ptolemy-Thompson group T ∗ playing the role of a mapping class group for an infinite planar surface and proved that T ∗ is finitely presented. The group T ∗ is a somewhat simplified version of the mysterious acyclic extension considered earlier by Greenberg and Sergiescu (see [13]), whose algebraic properties are still poorly understood today. The aim of this note is to use the method introduced in [9] in order to recover the braided Houghton groups as mapping class groups of infinite surfaces. In particular the braid group on infinitely many strands is realized as the commutator subgroup of an explicit finitely presented group. This has been done previously by Dynnikov who used the so-called three pages representations of braids and links in ([7]). Our groups are slightly different from those considered by Dynnikov and their presentation is of different nature, because it comes from a geometric description in terms of mapping classes. Moreover, we obtain that the word problem of the braided Houghton groups is solvable. A version of our construction was used by Degenhardt, who introduced the braided Houghton groups BHn in his (unpublished) thesis [6]. Then Kai-Uwe Bux described a conjectural approach to the finiteness properties of these groups in [4]. In order to define the mapping class group of an infinite surface we need to fix the behaviour of homeomorphisms at infinity. The main ingredient used in [9] consists of adjoining rigid structures, as defined below: Definition 1. A rigid structure d on the surface Σ is a decomposition of Σ into 2-disks with disjoint interiors, called elementary pieces. We suppose that the closures of the elementary pieces are still 2-disks. We assume that we are given a family F of compact subsurfaces of Σ such that each member of F is a finite union of elementary pieces, and called the family of admissible subsurfaces of Σ. Given the data (Σ, d, F ) we can associate the asymptotic mapping class group M(Σ, d, F ) as follows. We restrict first to those homeomorphisms that act in the simplest possible way at infinity. Definition 2. A homeomorphism ϕ between two surfaces endowed with rigid structures is rigid if it sends the rigid structure of one surface onto the rigid structure of the other. The homeomorphism ϕ : Σ → Σ is said to be asymptotically rigid if there exists some admissible subsurface C ⊂ Σ, called a support for ϕ, such that ϕ(C) ⊂ Σ is also an admissible subsurface of Σ and the restriction ϕ|Σ−C : Σ − C → Σ − ϕ(C) is rigid. As it is customary when studying mapping class groups we consider now isotopy classes of such homeomorphisms. Definition 3. The group M(Σ, d, F ) of isotopy classes of asymptotically rigid homeomorphisms is called the asymptotic mapping class group of Σ corresponding to the rigid structure d and family of admissible subsurfaces F . Remark 1. Two asymptotically rigid homeomorphisms that are isotopic should be isotopic among asymptotically rigid homeomorphisms. ∗ This

version: February 2007. This preprint is available electronically at http://www-fourier.ujf-grenoble.fr/~funar

1

Example 1. One of the simplest nontrivial examples of infinite surface with a large symmetry group is obtained by thickening the planar binary tree in the plane. The ribbon tree D obtained this way has a natural rigid structure. The elementary pieces of the rigid structure are hexagons obtained by thickening the tripodes issued from the vertices of the binary tree, each one made of three mid-edges going from the vertex to the midpoints of the adjacent edges, as in the picture below:

The family of admissible subsurfaces consists of those subsurfaces of D that are unions of finitely many elementary pieces. The asymptotic mapping class group of D with this rigid structure can be identified with the so-called Ptolemy-Thompson group T . Notice that T is a simple finitely presented group which admits an alternative description as the group of piecewise linear homeomorphisms of the circle S 1 = [0, 1]/{0 ∼ 1}, mapping images of dyadic into images of dyadic numbers, differentiable outside finitely many images of dyadic numbers, with derivatives powers of 2. In order to understand better this correspondence we remark that T almost acts on the infinite binary tree. One introduces an almost automorphism as an automorphism in the complement of a finite subtree. Then the group T is generated by the following almost automorphisms α, β of the binary tree: β is the order three rotation around a vertex and α is the order four rotation around an edge midpoint. The subgroup hα2 , βi ⊂ T is actually the modular group P SL(2, Z) acting on its Bass-Serre tree. More about Thompson’s groups can be found in [5, 11]. Example 2. A more intricate example was considered and studied extensively in [9]. We shift from the ribbon tree D to the punctured ribbon tree D ∗ by adding infinitely many punctures on D located at the midpoints of the edges. Then the ribbon tree D ∗ inherits a natural rigid structure from D. The ribbon tree D ∗ inherits a natural rigid structure from D for which the elementary pieces are punctured hexagons, as in the picture below:

The family of admissible subsurfaces consists of those subsurfaces of D ∗ that are unions of finitely many elementary pieces. The asymptotic mapping class group of D ∗ with this rigid structure is the braided Ptolemy-Thompson group T ∗ considered in [9]. It is proved there that there exists an exact sequence 1 → B∞ → T ∗ → T → 1 where B∞ is the group of braids with compact support in the punctures of D ∗ . Thus B∞ is the direct limit of the sequence of braid groups associated to an ascending sequence of punctured admissible subsurfaces of D∗ .

2

We want to turn to simpler examples obtained from thickening trees in the plane and show that interesting groups could be obtained this way. Consider the planar ribbon Yn , which is a 2-dimensional neigborhood of the wedge of n half-lines (or rays) in the plane that intersect at the origin. Assume that every half-line is endowed with a linear coordinates system in which the origin corresponds to 0 and that the rotation of order n sends them isometrically one into the other. Let Yn∗ (respectively Yn] ) be the punctured ribbon obtained from Yn by puncturing it along the set of points of positive (respectively nonnegative) integer coordinates on each half-line. Punctures are therefore identified to nonnegative integers along each ray. The origin has coordinates 0 on all half-lines and does appear only in Yn] . p (2) 3

p (1)

p 1(2)

3

p (1)

0

1

p 2(1) p (2) 2

There is a family of parallel arcs associated to each ray, by drawing a properly embedded segment orthogonal to the respective half-line and passing through the puncture labelled n, for every n ∈ Z+ − {0}. The surface Yn (respectively Yn∗ , Yn] ) is then divided by these arcs into elementary pieces, which are of two types: one central (respectively punctured for Yn∗ ) 2n-gon containing the origin and infinitely many (respectively punctured) squares which sit along the half-lines. One defines the admissible subsurfaces of Y n (respectively Yn∗ , Yn] ) to be those (punctured) 2n-gons which contain the (punctured) central 2n-gon and are made of finitely many elementary pieces. Let M(Yn ) (respectively M(Yn∗ ), M(Yn] )) denote the asymptotic mapping class group of Yn (respectively Yn∗ , Yn] ) with the above rigid structure. The group M(Yn ) has a particularly simple form. In fact any element of M(Yn ) corresponds to a triple ((P, Q), r), where P and Q are admissible 2n-gons and r is an order n rotation that gives the recipe for identifying the boundary arcs of P and Q. Moreover, an admissible 2n-gon P ⊂ Yn is completely determined by the vector vP ∈ (Z+ − {0})n recording the coordinates of those punctures that lie on the boundary arcs of P , one coordinate for each ray. The cyclic group of rotations Z/nZ acts on Z n by permuting the coordinates and preserves the subgroup Zn−1 ⊂ Zn of the vectors having the sum of their coordinates zero. The map that sends the pair ((P, Q), r) into (vQ − r(vP ), r) ∈ Zn o Z/nZ induces an isomorphism of M(Yn ) onto the subgroup Zn−1 o Z/nZ. Following the example 2 one expects M(Yn∗ ) and M(Yn] ) to be extensions of M(Yn ) by an infinite braid group B∞ . If M(Yn ) were abelian then the infinite braid group B∞ would be the commutator of the extension group. However the semi-direct product Zn−1 o Z/nZ is not direct for n ≥ 3, and hence it is convenient to restrict to those mapping classes in the groups above coming from end preserving homeomorphisms. Consider therefore the subgroups M∂ (Yn ) (respectively M∂ (Yn∗ ), M∂ (Yn] )) generated by those homeomorphisms which are end preserving i.e. inducing a trivial automorphism of the ends of Yn . Alternatively, the homeomorphisms should send each ray into itself, at least outside of a large enough compact. It follows from above that M∂ (Yn ) is isomorphic to Zn−1 . The groups M∂ (Yn∗ ) are isomorphic to the braided Houghton groups considered by Degenhardt and Dynnikov. It is known that these are finitely presented groups for all n ≥ 3. The same result holds for the larger related groups M∂ (Yn] ): Theorem 1. The groups M(Yn] ) and M∂ (Yn] ) are finitely presented for n ≥ 3. The commutator subgroup of M∂ (Yn] ) is the infinite braid group B∞ in the punctures of Yn] . Proof. Consider the case of M∂ (Yn] ), the other one being similar. We can express the groups as an extension by the infinite braid group, as follows: 3

Proposition 1. There is an exact sequence 1 → B∞ → M∂ (Yn] ) → Zn−1 → 1 where B∞ = limk→∞ Bkn+1 is the limit of the braid groups of an exhausting sequence of admissible subsurfaces of Yn] . Proof. A mapping class ϕ ∈ M∂ (Yn] ) sends a support 2n-gon into another support 2n-gon, by translating the arc on the half-line lj of kj units towards the centre. Since the support hexagons should contain the same number of punctures we have k1 + k2 + · · · + kn = 0. The map sending ϕ to (k1 , k2 , . . . , kn ) is a surjection onto Zn−1 . The rest of the proof is immediate. Let the line lj be punctured along the points pj (i) at distance i from the origin. Consider the mapping class of the homeomorphism dj which translates all punctures of the line lj ∪ lj+1 one unit in the counterclockwise direction, as in the figure below: p (2)

p (2)

3

3

p (1)

p 1(2)

3

p (1)

p (1)

p 1(3)

0

p (2)

1

d1

1

3

p (1) 1

p 2(1)

0

p (2)

p (1)

2

2

We use the convention that the groups acts on the right: thus the composition ab denotes a followed by b. Moreover, the set of indices corresponding to the rays is {1, 2, . . . , n}, which is naturally identified to Z/nZ; let then < denote the cyclic order on Z/nZ. −1 ] Proposition 2. Set ui = di di+1 d−1 i di+1 . Then the group M∂ (Yn ) is generated by the d1 , d2 , . . . , dn and admits the presentation: d1 d2 d3 · · · dn = 1

ui1 ui2 ui3 ui1 = ui2 ui3 ui1 ui2 = ui3 ui1 ui2 ui3 , if i1 < i2 < i3 −1 d−1 i−1 ui di−1 = di ui di for all i

ui uj ui = uj ui uj , for all i, j −1 d−1 i−1 ui di−1 ui di−1 ui di−1

= ui d−1 i−1 ui di−1 ui , for all i

[di ui d−1 i , uj ] = 1, for all i 6= j [di ui d−1 i , dj ] = 1, for all i < j < i − 1 −1 [dj ui d−1 j = ui uj uj , for all i < j < i − 1

Proof. Let a, b be adjacent punctures. We denote by σab the standard braid that interchanges a and b moving them counterclockwise. Remark that ui = σ0pi (1) is the braid twisting 0 and pi (1). Moreover, one k ] proves by recurrence that σpi (k)pi (k+1) = d−k i−1 ui di−1 . Thus Mδ (Yn ) is generated by the dj s since their n−1 images generate both the quotient Z and the kernel B∞ . The group B∞ is identified with the braid group associated to the infinite tree given by the reunion of the n half-lines in the plane, whose vertices are located at punctures. We can use therefore the presentation for B∞ given by Sergiescu (see [16, 1]). In particular B∞ is generated by the (infinite) set of braids associated to the edges of the tree, namely the braids σpi (k)pi (k+1) . By translating the relations between the braids into relations between the di and ui we obtain the following set of vertex and edge relations: ui1 ui2 ui3 ui1 = ui2 ui3 ui1 ui2 = ui3 ui1 ui2 ui3 , if i1 < i2 < i3 ui uj ui = uj ui uj , for all i, j −1 = ui di ui d−1 di ui d−1 i ui , for all i i ui d i ui d i

4

and an additional set of commuting relations between twists with disjoint support edges, reading: [σpi (k)pi (k+1) , σpj (m)pj (m+1) ] = 1, when their support edges are disjoint The twists associated to edges at distance one yield the relations [d−1 i−1 ui di−1 , uj ] = 1, for all i 6= j Further di commutes with σpi (1)pi (2) since they have disjoint supports, which lead us to the last relations above. The interesting phenomenon is that these relations actually are sufficient to imply all commutativity relations (between arbitrary far away disjoint twists associated to the edges). We skip the proof, which is a direct calculation. It follows that subgroup generated by the ui s and their conjugates by the dj s is B∞ . Further B∞ is a normal subgroup inside the group given by the presentation above, as the conjugates by d j of the ui s can be expressed in terms of the braid generators σpi (k)pi (k+1) . Then we can provide an infinite presentation of M∂ (Yn] ) by means of Hall’s lemma which puts together the Sergiescu presentation of B∞ and that of Zn−1 . Then all relations of this infinite presentation are consequences of those from the statement. The claim follows. It follows from above that B∞ ⊂ [M∂ (Yn] ), M∂ (Yn] )] because ui = [di , di+1 ] and thus each braid generators σpi (k)pi (k+1) is conjugate to a commutator. Moreover the quotient M∂ (Yn] )/B∞ is the abelian group Zn−1 and hence B∞ is the commutator subgroup of M∂ (Yn] ). Notice that the same holds for the braided Houghton group M∂ (Yn∗ ). The two versions M∂ (Yn] ) and M∂ (Yn∗ ) of braided Houghton groups are very closed to each other. Let M∗∂ (Yn] ) denote the subgroup of those mapping classes fixing the central puncture 0. Therefore Proposition 3. There is an exact sequence 1 → F → M∗∂ (Yn] ) → M∂ (Yn∗ ) → 1 where F is a free group on infinitely many generators that is normally generated in M ∂ (Yn] ) by one element. Proof. The projection homomorphism is that induced by the inclusion Yn] → Yn∗ and corresponds to forgetting the central puncture. It is classical that the kernel F of this map is isomorphic to π1 (Yn∗ , 0) which is free on infinitely many generators. The element u21 ∈ M∂ (Yn] ) is represented by the closed loop based at the origin encircling the puncture p1 (1). However M∂ (Yn] ) acts transitively by conjugacy on the set of loops that encircle punctures of Yn∗ and thus the element u21 normally generates the kernel. Theorem 2. The groups M∂ (Yn] ) (and its versions) have solvable word problem. Proof. For any word w in the generators di we have that there exists a support of w made of elementary pieces not farther than |w| + 1 units from the central 2n-gon. Then the proof given in [9] can be adapted to our situation. Onserve that we actually use the fact that the word problem is solvable in braid groups. Remark 2. Let S∞ denote the infinite permutation group of punctures of Yn∗ obtained as direct limit of finite permutation groups of punctures in an ascending sequence of admissible subsurfaces. The Houghton groups Hn considered by Brown ([3]) are quotients of M∂ (Yn∗ ) induced from the obvious homomorphism B∞ → S∞ sending braids into the associated permutations. This means that we have natural exact sequences 1→ 1→

B∞ ↓ S∞

→ M∂ (Yn] ) → Zn−1 ↓ ↓ → Hn → Zn−1

→1 →1

Remark 3. The group M∂ (Y2] ) (and its variants) is generated by two elements, namely d = d1 = d−1 2 and ] u1 = σ0p1 (1) . However, M∂ (Y2 ) is not finitely presented since the commutativity relations coming from the braid group are independent, namely we have infinitely many relations [dk ud−k , dm ud−m ] = 1, for all integers m, k with |m − k| ≥ 1. Also M∂ (Y2] ) surjects onto the Houghton group H2 which is known to be infinitely presented. In some sense M∂ (Y2] ) is similar to the lamplighter groups. 5

Remark 4. Since all generators of B∞ are conjugate the abelianization of B∞ is Z. The abelianization homomorphism B∞ → Z induces an extension M∂ (Yn] )ab as follows: 1 → B∞ ↓ 1→ Z

M∂ (Yn∗ ) ↓ → M∂ (Yn∗ )ab

→ Zn−1 ↓ → Zn−1

→1 →1

For n = 2 it follows that M∂ (Y2∗ )ab is abelian, generated by the images of d and u. In particular, we obtain that M∂ (Y2∗ )ab ∼ = H1 (M∂ (Y2∗ )) = Z2 . For n ≥ 3 the group M∂ (Yn∗ )ab is a nontrivial (non-abelian) extension of Zn−1 by Z. Remark 5. Degenhardt ([6]) proved that the braided Houghton groups are Fn−1 but not Fn for n ≤ 3 and conjectured that this holds for all n. This would be a parallel to the results obtained by Brown (see [3]) for the usual Houghton groups Hn . Progress towards the settlement of this conjecture was made by Kai-Uwe Bux in [4]. It seems that the groups M∂ (Yn] ) are also Fn−1 but not Fn . This behavior is in contrast with the case of the Thompson group T (which is FP∞ ) and its braided version T ∗ (which is at least FP3 (see [10]) and expected to be FP∞ ). It is therefore likely that M∂ (Yn] ) are not combable (hence not automatic) although the result of [10] would suggest that they might be asynchronously combable with quadratic Dehn function. If the similarity with the braid groups is pushed one step farther then the braided Houghton groups should have solvable conjugacy problem, as well. Remark 6. Given three rays in the binary tree we can associate an embedding of Y 3∗ into D∗ that induces injective compatible homomorphisms Z2 o Z/3Z → T and M(Y3∗ ) → T ∗ . Remark 7. One does not know which other planar graphs yield finitely presented group asymptotic mapping class groups. One may enlarge the category of graphs to that of coloured graphs, in which automorphisms and almost automorphisms are required to preserve the colouring. An interesting class of coloured planar trees comes from universal coverings of ribbon graphs, associated to punctured surfaces and 2-dimensional orbifolds. The ribbon structure of the graph is a cyclic order around each vertex. There is a natural colouring of vertices and edges of the graph by using different colours, and this induces a colouring on the universal covering tree. Moreover, the tree has a natural embedding in the plane which uses the induced cyclic order around the vertices. However P.Greenberg ([12]) showed that asymptotic mapping class groups of universal coverings of (coloured) ribbon graphs (called projective Thompson groups) have infinitely many generators, as soon as the genus of the surface is positive. Moreover, if the genus is zero Laget ([15] proved that the asymptotic mapping class groups are finitely presented groups. It seems that the finite presentability holds more generally for all the groups obtained from the 2-orbifolds of genus zero. The basic example in this respect is the Thompson group T which arises from the 2-orbifold associated to the group P SL(2, Z), namely the sphere with a cusp, one singular point of order 2 and another one of order 3. Acknowledgements. I’m indebted to C.Kapoudjian and V.Sergiescu for useful discussions.

References [1] J.Birman, Ki Hyoung Ko and Sang Jin Lee, A new approach to the word and conjugacy problems in the braid groups, Advances Math. 139(1998), 322-353. [2] K.S.Brown, Presentations for groups acting on simply-connected complexes, J. Pure Appl. Algebra 32(1984), 1-10. [3] K.S.Brown, Finiteness properties of groups, Proceedings of the Northwestern conference on cohomology of groups (Evanston, Ill., 1985), J. Pure Appl. Algebra 44(1987), 45-75. [4] Kai-Uwe Bux, Braiding and tangling the chessboard complex, math.GT/0310420. [5] J.W.Cannon, W.J. Floyd, and W.R. Parry, Introductory notes on Richard Thompson’s groups, Enseign. Math. 42(1996), 215-256. [6] F.Degenhardt, Endlichkeitseigeinschaften gewiser Gruppen von Z¨ opfen unendlicher Ordnung, PhD thesis, Franfurt 2000. [7] I.A.Dynnikov, Three-page representation of links, Uspekhi Mat. Nauk 53(1998), 237-238; translation in Russian Math. Surveys 53(1998), 1091-1092.

6

[8] I.A.Dynnikov, Finitely presented groups and semigroups in knot theory, Trudy.Mat. Inst. Steklov 231(2000), 29-40; translation in Proc.Steklov Institute Math. 231(2000), no. 4, 220-237. [9] L.Funar and C.Kapoudjian, The braided Ptolemy-Thompson group is finitely presented, 41p., math.GT/0506397. [10] L.Funar and C.Kapoudjian, math.GT/0602490.

The

braided

Ptolemy-Thompson

group

is

asynchronously

combable,

[11] E.Ghys and V.Sergiescu, Sur un groupe remarquable de diff´eomorphismes du cercle, Comment.Math.Helvetici 62(1987), 185-239. [12] P.Greenberg, Projective aspects of the Higman-Thompson group, Group theory from a geometrical viewpoint (Trieste, 1990), 633–644, World Sci. Publ., River Edge, NJ, 1991. [13] P.Greenberg and V.Sergiescu, An acyclic extension of the braid group, Comment. Math. Helv. 66(1991), 109-138. [14] C. Kapoudjian and V.Sergiescu, An extension of the Burau representation to a mapping class group associated to Thompson’s group T , Geometry and dynamics, 141-164, Contemp. Math., vol. 389, Amer. Math. Soc., Providence, RI, 2005. [15] G.Laget, Groupes de Thmpson projectifs de genre 0, PhD Thesis, Univ.Grenoble I, 2004. [16] V.Sergiescu, Graphes planaires et pr´esentations des groupes de tresses, Math. Zeitsch. 214(1993), 477-490.

7