text: G Represent morphisms (g , η) in the category as squares, so that the action of Φ on such 1 γ a square is given by: − − (cid:73) g γ g γ 1 γg γ 1 γ g 1 1 1 1 η Φ(cid:55)→γ η = γ (cid:66) η = γ (cid:66) η (37) g2 γ g2 γ−1 γg2γ−1 γ (cid:73) g2 where g = ∂(η)g . Likewise we can represent the morphism Φ (g) (which has no direct 2 1 (γ1,χ) analog in the action notation) as − (cid:73) γ g γ 1 γ g 1 1 1 − (cid:73) (cid:66) − Φ(γ1,χ)(g) = χ χ h = χ(γ1 g) χ 1 (38) γ2 g γ−1 γ2 (cid:73) g 2 where γ = ∂(χ)γ . 2 1 It follows from (37) that Φ (g , η) has the correct source and target. Φ is a functor, since γ 1 − γ ◦ it preserves identities, Φ (g, 1 ) = (γgγ 1, 1 ) (immediate), and composition, i.e. Φ (g , η ) γ H H γ 2 2 Φ (g , η ) = Φ (g , η η ), where g = ∂(η )g , because of: γ 1 1 γ 1 2 1 2 1 1 − γ g γ 1 1 − γ g γ 1 η 1 1 − γ g2 γ 1 = η2η1 η 2 γ g3 γ−1 γ g3 γ−1 It then follows immediately from (38) that Φ (g) has the correct source and target. The ◦ (γ1,χ) ◦ naturality condition (17), i.e. Φ (g , η) Φ (g ) = Φ (g ) Φ (g , η), is the equality: γ2 1 (γ1,χ) 1 (γ1,χ) 2 γ1 1 − − γ g γ 1 γ g γ 1 1 1 1 1 1 1 − χ χ h η − − γ2 g1 γ2 1 = γ1 g2 γ1 1 − η χ χ h γ2 g2 γ−1 γ2 g2 γ−1 2 2 which follows from the interchange law by evaluating the vertical compositions on both sides ﬁrst. 16 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: G

text: Represent

text: morphisms

text: (g

text: η)

text: in

text: the

text: category

text: as

text: squares,

text: so

text: that

text: the

text: action

text: of

text: Φ

text: on

text: such

text: γ

text: a

text: square

text: is

text: given

text: by:

text: g

text: γ

text: g

text: γ

text: γg

text: γ

text: γ

text: g

text: η

text: η

text: γ

text: η

text: γ

text: η

text: γ

text: γ−1

text: γg2γ−1

text: γ

text: where

text: g

text: ∂(η)g

text: Likewise

text: we

text: can

text: represent

text: the

text: morphism

text: Φ

text: (g)

text: (which

text: has

text: no

text: direct

text: analog

text: in

text: the

text: action

text: notation)

text: as

text: γ

text: g

text: γ

text: γ

text: g

text: χ

text: χ

text: h

text: χ(γ1

text: g)

text: χ

text: γ2

text: g

text: γ−1

text: γ2

text: g

text: where

text: γ

text: ∂(χ)γ

text: It

text: follows

text: from

text: that

text: Φ

text: (g

text: η)

text: has

text: the

text: correct

text: source

text: and

text: target.

text: Φ

text: is

text: a

text: functor,

text: since

text: γ

text: γ

text: it

text: preserves

text: identities,

text: Φ

text: (g,

text: (γgγ

text: (immediate),

text: and

text: composition,

text: i.e.

text: Φ

text: (g

text: η

text: γ

text: H

text: H

text: γ

text: Φ

text: (g

text: η

text: Φ

text: (g

text: η

text: η

text: where

text: g

text: ∂(η

text: )g

text: because

text: of:

text: γ

text: γ

text: γ

text: g

text: γ

text: γ

text: g

text: γ

text: η

text: γ

text: γ

text: η2η1

text: η

text: γ

text: γ−1

text: γ

text: γ−1

text: It

text: then

text: follows

text: immediately

text: from

text: that

text: Φ

text: (g)

text: has

text: the

text: correct

text: source

text: and

text: target.

text: The

text: naturality

text: condition

text: i.e.

text: Φ

text: (g

text: η)

text: Φ

text: (g

text: Φ

text: (g

text: Φ

text: (g

text: η),

text: is

text: the

text: equality:

text: γ2

text: γ1

text: γ

text: g

text: γ

text: γ

text: g

text: γ

text: χ

text: χ

text: h

text: η

text: γ2

text: γ2

text: γ1

text: γ1

text: η

text: χ

text: χ

text: h

text: γ2

text: γ−1

text: γ2

text: γ−1

text: which

text: follows

text: from

text: the

text: interchange

text: law

text: by

text: evaluating

text: the

text: vertical

text: compositions

text: on

text: both

text: sides

text: ﬁrst.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: where in the ﬁrst equation we have a composable pair, since (if the target of f is y): (cid:73) ◦ ◦ t((1 , 1 ), f) = (1 , 1 ) f = Φ (y) Φ (f) = Φ (y) f = f G H G H (1G,1H) 1G (1G,1H) using (24) in the second equality, functoriality of Φ in the third equality and property F2 (see Def. 3.1.1 ) in the ﬁnal equality. Finally, the inverse functor assigns, to every ((γ, χ), f) in the category of morphisms, its − − (cid:73) − − − − (cid:66) − inverse ((γ 1, χ h), (γ, χ) f), where we note that (γ 1, χ h) = (γ 1, (∂(χ)γ) 1 χ 1) = − − (cid:66) − (γ 1, γ 1 χ 1). This follows immediately from (45). Functoriality of the inverse functor D G (cid:3) follows easily from (20) and functoriality of the horizontal inverse in ( ). Since Cat is actually a 2-category, it could be objected that our construction is implicitly assuming that one is requiring that diagrams commute strictly, and that all pullbacks are strict rather than weak. That is, that we are taking a strict internal category in Cat. A more subtle approach might consider weakening the axioms to various degrees. However, we will not do this here, for reasons outlined in Appendix . On the other hand, there is a diﬀerent drawback to this construction of a Cat-category which we will address, which has to do with the apparent asymmetry of its deﬁnition. 4.2 The Transformation Double Category The construction we have given in the previous section naturally produces a groupoid internal to Cat. However, the view of a double category as an internal category in Cat obscures the underlying symmetry of this structure, and the structure in the “transverse” direction to the categories of objects and morphisms. As we remarked in Section , Cat-categories are equivalent to a structure deﬁned in a more symmetric way, having two types of morphisms (horizontal and vertical), and squares. The properties can be deduced from the equivalence: for example, the “interchange law”, which says that mixed horizontal and vertical composites can be taken in any order, amounts to the ◦ functoriality of the composition . Now, the deﬁnition of double categories is symmetric under exchanging the roles of “hori- zontal” and “vertical” morphisms in our diagrams of squares. One can reﬂect all squares in a diagonal, and obtain another double category, which we call the transpose of the ﬁrst double category. This result, naturally, still has an interpretation as a category internal to Cat. More(cid:101)technically, we have the following: D D Deﬁnition 4.2.1 If is an internal category in Cat, then let the transpose of , which we D denote , be the internal category in Cat deﬁned by the following: • The category of objects has D – Objects: the objects of the category (0) D – Morphisms: the objects of the category (1) • The category of morphisms has D – Objects: the morphisms of the category (0) D (cid:101) (cid:101) (cid:101) (cid:101) – Morphisms: the morphisms of the category (1) • ◦ The identity inclusion, source and target, and composition functors (e, s, t, ) have as object D maps the corresponding structure maps from the category (0), and as morphism maps the D corresponding structure maps from the category (1) This is a double-category analog of the operation of taking the “opposite” of a category: another category in which morphisms are taken to be oriented in the opposite direction. Indeed, together with such opposite operations in both horizontal and vertical directions, the transpose generates a whole group of operations which take one double category to another: it is plainly 21

text: where

label: paragraph

text: in

text: the

text: ﬁrst

text: equation

text: we

text: have

text: a

text: composable

text: pair,

text: since

text: (if

text: the

text: target

text: of

text: f

text: is

text: y):

text: f)

text: f

text: Φ

text: (y)

text: Φ

text: (f)

text: Φ

text: (y)

text: f

text: f

text: G

text: H

text: G

text: H

text: using

text: in

text: the

text: second

text: equality,

text: functoriality

text: of

text: Φ

text: in

text: the

text: third

text: equality

text: and

text: property

text: (see

text: Def.

text: in

text: the

text: ﬁnal

text: equality.

text: Finally,

text: the

text: inverse

text: functor

text: assigns,

text: to

text: every

text: ((γ,

text: χ),

text: f)

text: in

text: the

text: category

text: of

text: morphisms,

text: its

text: inverse

text: ((γ

text: χ

text: h),

text: (γ,

text: χ)

text: f),

text: where

text: we

text: note

text: that

text: (γ

text: χ

text: h)

text: (γ

text: (∂(χ)γ)

text: χ

text: (γ

text: γ

text: χ

text: This

text: follows

text: immediately

text: from

text: Functoriality

text: of

text: the

text: inverse

text: functor

text: D

text: G

text: follows

text: easily

text: from

text: and

text: functoriality

text: of

text: the

text: horizontal

text: inverse

text: in

text: Since

text: Cat

text: is

text: actually

text: a

text: it

text: could

text: be

text: objected

text: that

text: our

text: construction

text: is

text: implicitly

text: assuming

text: that

text: one

text: is

text: requiring

text: that

text: diagrams

text: commute

text: strictly,

text: and

text: that

text: all

text: pullbacks

text: are

text: strict

text: rather

text: than

text: weak.

text: That

text: is,

text: that

text: we

text: are

text: taking

text: a

text: strict

text: internal

text: category

text: in

text: Cat.

text: A

text: more

text: subtle

text: approach

text: might

text: consider

text: weakening

text: the

text: axioms

text: to

text: various

text: degrees.

text: However,

text: we

text: will

text: not

text: do

text: this

text: here,

text: for

text: reasons

text: outlined

text: in

text: Appendix

text: On

text: the

text: other

text: hand,

text: there

text: is

text: a

text: diﬀerent

text: drawback

text: to

text: this

text: construction

text: of

text: a

text: Cat-category

text: which

text: we

text: will

text: address,

text: which

text: has

text: to

text: do

text: with

text: the

text: apparent

text: asymmetry

text: of

text: its

text: deﬁnition.

text: The

text: Transformation

text: Double

text: Category

text: The

text: construction

text: we

text: have

text: given

text: in

text: the

text: previous

text: section

text: naturally

text: produces

text: a

text: groupoid

text: internal

text: to

text: Cat.

text: However,

text: the

text: view

text: of

text: a

text: double

text: category

text: as

text: an

text: internal

text: category

text: in

text: Cat

text: obscures

text: the

text: underlying

text: symmetry

text: of

text: this

text: structure,

text: and

text: the

text: structure

text: in

text: the

text: “transverse”

text: direction

text: to

text: the

text: categories

text: of

text: objects

text: and

text: morphisms.

text: As

text: we

text: remarked

text: in

text: Section

text: Cat-categories

text: are

text: equivalent

text: to

text: a

text: structure

text: deﬁned

text: in

text: a

text: more

text: symmetric

text: way,

text: having

text: two

text: types

text: of

text: morphisms

text: (horizontal

text: and

text: vertical),

text: and

text: squares.

text: The

text: properties

text: can

text: be

text: deduced

text: from

text: the

text: equivalence:

text: for

text: example,

text: the

text: “interchange

text: law”,

text: which

text: says

text: that

text: mixed

text: horizontal

text: and

text: vertical

text: composites

text: can

text: be

text: taken

text: in

text: any

text: order,

text: amounts

text: to

text: the

text: functoriality

text: of

text: the

text: composition

text: Now,

text: the

text: deﬁnition

text: of

text: double

text: categories

text: is

text: symmetric

text: under

text: exchanging

text: the

text: roles

text: of

text: “hori-

text: zontal”

text: and

text: “vertical”

text: morphisms

text: in

text: our

text: diagrams

text: of

text: squares.

text: One

text: can

text: reﬂect

text: all

text: squares

text: in

text: a

text: diagonal,

text: and

text: obtain

text: another

text: double

text: category,

text: which

text: we

text: call

text: the

text: transpose

text: of

text: the

text: ﬁrst

text: double

text: category.

text: This

text: result,

text: naturally,

text: still

text: has

text: an

text: interpretation

text: as

text: a

text: category

text: internal

text: to

text: Cat.

text: we

text: have

text: the

text: following:

text: D

text: D

text: Deﬁnition

text: If

text: is

text: an

text: internal

text: category

text: in

text: Cat,

text: then

text: let

text: the

text: transpose

text: of

text: which

text: we

text: D

text: denote

text: be

text: the

text: internal

text: category

text: in

text: Cat

text: deﬁned

text: by

text: the

text: following:

text: The

text: category

text: of

text: objects

text: has

text: D

text: Objects:

text: the

text: objects

text: of

text: the

text: category

text: D

text: Morphisms:

text: the

text: objects

text: of

text: the

text: category

text: The

text: category

text: of

text: morphisms

text: has

text: D

text: Objects:

text: the

text: morphisms

text: of

text: the

text: category

text: D

text: Morphisms:

text: the

text: morphisms

text: of

text: the

text: category

text: The

text: identity

text: inclusion,

text: source

text: and

text: target,

text: and

text: composition

text: functors

text: (e,

text: s,

text: t,

text: have

text: as

text: object

text: D

text: maps

text: the

text: corresponding

text: structure

text: maps

text: from

text: the

text: category

text: and

text: as

text: morphism

text: maps

text: the

text: D

text: corresponding

text: structure

text: maps

text: from

text: the

text: category

text: This

text: is

text: a

text: double-category

text: analog

text: of

text: the

text: operation

text: of

text: taking

text: the

text: “opposite”

text: of

text: a

text: category:

text: another

text: category

text: in

text: which

text: morphisms

text: are

text: taken

text: to

text: be

text: oriented

text: in

text: the

text: opposite

text: direction.

text: Indeed,

text: together

text: with

text: such

text: opposite

text: operations

text: in

text: both

text: horizontal

text: and

text: vertical

text: directions,

text: the

text: transpose

text: generates

text: a

text: whole

text: group

text: of

text: operations

text: which

text: take

text: one

text: double

text: category

text: to

text: another:

text: it

text: is

text: plainly


text: • → ∈ Horizontal Category: same as C, with morphisms x f y H = C(1) composed as usual • Vertical Category: same as C(0)//G(0), with morphisms displayed as x (−γ→,x) γ (cid:73) x ∈ G (cid:48) (cid:73) ◦ V = (C(0)// (0))(1) with source and target as shown and composed by (γ , γ x) (γ, x) = (cid:48) (γ γ, x) • ×G ×G G Squares: S = (C )(1) = C(1) (1) consists of pairs of morphisms from C and , with elements of S denoted by (γ, χ), f , displayed as f (cid:47)(cid:47) x y (54) (γ,x) (γ,χ),f (∂(χ)γ,y) (cid:15)(cid:15) (cid:15)(cid:15) (cid:73) (cid:47)(cid:47) (cid:73) γ x (cid:73) (∂(χ)γ) y (γ,χ) f with horizontal and vertical source and target as shown in the display. Horizontal and vertical composition (equivalent to pasting of diagrams of the form (54)) is given by: ◦ ◦ (γ , χ ), g (γ , χ ), f = (γ , χ χ ), g f (55) 2 2 h 1 1 1 2 1 where γ = ∂(χ )γ , and: 2 1 1 (cid:73) ◦ (cid:66) (γ , χ ), (γ , χ ) f (γ , χ ), f = (γ γ , χ (γ χ )), f (56) 1 1 3 2 v 3 2 1 3 1 1 2 D G where the underlying squares in ( ) are given in (18). G Theorem 4.2.5 C// is a well-deﬁned double category. Proof: Most of the points to be checked are directly implied by the properties of the internal G (cid:93)G categories C// and C// , e.g. the vertical target of the vertical composition of squares is well- deﬁned due to (46). We note that the vertical target of the horizontal composition of squares, equals the composition of the vertical targets of the two squares, i.e. (cid:73) ◦ (cid:73) ◦ (cid:73) (γ , χ χ ) (g f) = ((γ , χ ) g) ((γ , χ ) f) (57) 1 2 1 2 2 1 1 by the functoriality of Φˆ in (20). Likewise the horizontal target of the vertical composition of squares equals the composition of the horizontal targets of the two squares, i.e. (cid:66) (∂(χ )γ ∂(χ )γ , y) = (∂(χ (γ χ ))γ γ , y). (58) 1 1 2 3 1 1 2 1 3 This follows in a straightforward fashion from crossed module properties. Associativity of the horizontal and vertical composition of squares is an immediate conse- G (cid:93)G quence of the associativity of the composition functors in C// and C// . Finally the interchange law for horizontal and vertical composition of squares corresponds to the proof of functoriality G of the composition functor in C// (Lemma 4.1.2) and reduces to stating the interchange law D G (cid:3) for four squares (47) in ( ). 24 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: list

text: Horizontal

text: Category:

text: same

text: as

text: C,

text: with

text: morphisms

text: x

text: f

text: y

text: H

text: composed

text: as

text: usual

text: Vertical

text: Category:

text: same

text: as

text: with

text: morphisms

text: displayed

text: as

text: x

text: (−γ→,x)

text: γ

text: x

text: G

text: V

text: with

text: source

text: and

text: target

text: as

text: shown

text: and

text: composed

text: by

text: (γ

text: γ

text: x)

text: (γ,

text: x)

text: (γ

text: γ,

text: x)

text: ×G

text: ×G

text: G

text: Squares:

text: S

text: (C

text: consists

text: of

text: pairs

text: of

text: morphisms

text: from

text: C

text: and

text: with

text: elements

text: of

text: S

text: denoted

text: by

text: (γ,

text: χ),

text: f

text: displayed

text: as

text: f

label: equation

font: default

text: x

text: y

text: (γ,x)

text: (γ,χ),f

text: (∂(χ)γ,y)

text: γ

text: x

text: (∂(χ)γ)

text: y

text: (γ,χ)

text: f

text: with

text: horizontal

text: and

text: vertical

text: source

text: and

text: target

text: as

text: shown

text: in

text: the

text: display.

text: Horizontal

text: and

text: vertical

text: composition

text: (equivalent

text: to

text: pasting

text: of

text: diagrams

text: of

text: the

text: form

text: is

text: given

text: by:

text: (γ

text: χ

text: g

text: (γ

text: χ

text: f

text: (γ

text: χ

text: χ

text: g

text: f

text: h

text: where

text: γ

text: ∂(χ

text: )γ

text: and:

text: (γ

text: χ

text: (γ

text: χ

text: f

text: (γ

text: χ

text: f

text: (γ

text: γ

text: χ

text: (γ

text: χ

text: f

text: v

text: D

text: G

text: where

text: the

text: underlying

text: squares

text: in

text: are

text: given

text: in

text: G

text: Theorem

text: C//

text: is

text: a

text: well-deﬁned

text: double

text: category.

text: Proof:

text: Most

text: of

text: the

text: points

text: to

text: be

text: checked

text: are

text: directly

text: implied

text: by

text: the

text: properties

text: of

text: the

text: internal

text: G

text: categories

text: C//

text: and

text: C//

text: e.g.

text: the

text: vertical

text: target

text: of

text: the

text: vertical

text: composition

text: of

text: squares

text: is

text: well-

text: deﬁned

text: due

text: to

text: We

text: note

text: that

text: the

text: vertical

text: target

text: of

text: the

text: horizontal

text: composition

text: of

text: squares,

text: equals

text: the

text: composition

text: of

text: the

text: vertical

text: targets

text: of

text: the

text: two

text: squares,

text: i.e.

text: (γ

text: χ

text: χ

text: (g

text: f)

text: ((γ

text: χ

text: g)

text: ((γ

text: χ

text: f)

text: by

text: the

text: functoriality

text: of

text: Φˆ

text: in

text: Likewise

text: the

text: horizontal

text: target

text: of

text: the

text: vertical

text: composition

text: of

text: squares

text: equals

text: the

text: composition

text: of

text: the

text: horizontal

text: targets

text: of

text: the

text: two

text: squares,

text: i.e.

text: (∂(χ

text: )γ

text: ∂(χ

text: )γ

text: y)

text: (∂(χ

text: (γ

text: χ

text: ))γ

text: γ

text: y).

text: This

text: follows

text: in

text: a

text: straightforward

text: fashion

text: from

text: crossed

text: module

text: properties.

text: Associativity

text: of

text: the

text: horizontal

text: and

text: vertical

text: composition

text: of

text: squares

text: is

text: an

text: immediate

text: conse-

text: G

text: quence

text: of

text: the

text: associativity

text: of

text: the

text: composition

text: functors

text: in

text: C//

text: and

text: C//

text: Finally

text: the

text: interchange

text: law

text: for

text: horizontal

text: and

text: vertical

text: composition

text: of

text: squares

text: corresponds

text: to

text: the

text: proof

text: of

text: functoriality

text: G

text: of

text: the

text: composition

text: functor

text: in

text: C//

text: (Lemma

text: and

text: reduces

text: to

text: stating

text: the

text: interchange

text: law

text: D

text: G

text: for

text: four

text: squares

text: in

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: deﬁnitions specify the objects of three equivalent 2-categories. 2.1.1 2-Groups as 2-Categories One very useful deﬁnition of a 2-group is motivated by analogy to the deﬁnition of a group as a (small) one-object category whose morphisms are all invertible. In this case, the elements of the group are the set of morphisms of the category, and the group multiplication is the composition. This highlights the way the deﬁnition of a category generalized the notion of “composition” which begins with algebraic gadgets such as groups. One might equally well deﬁne a (small) category in algebraic language as a unital semigroupoid. Taking the deﬁnition of category as more basic gives a group as a special case. While of course not the standard deﬁnition of a group, it is at least straightforward to generalize to “higher” groups in the sense of higher category theory. (We will assume some familiarity with 2-categories in what follows, though for readers who are not so familiar we suggest the succinct note by Leinster [11] as a starting point, and the more comprehensive survey by Lack [10] and Chapter 7 of Borceux [4] for more detail.) G G { } Deﬁnition 2.1.1 A 2-group is a 2-category with one object ( (0) = (cid:63) ), for which all ∈ G ∈ G 1-morphisms γ (1) and 2-morphisms χ (2) are invertible. ∈ G Note that in the case of χ (2), we requrie invertibility with respect to both horizontal and vertical composition. Let us unpack this deﬁnition more explicitly. G Suppose is a 2-group. There are various 1-morphisms from (cid:63) to itself, which have a composition operation, since all such morphisms have matching source and target: (cid:111)(cid:111) (cid:111)(cid:111) (cid:111)(cid:111) (cid:63) (cid:63) (cid:63) = (cid:63) ◦ (cid:63) (1) γ1 γ2 γ1 γ2 Composition of morphisms is the multiplication, which is therefore associative, and every G ◦ morphism must have an inverse by the deﬁnition of a 2-group, so ( (1), ) forms a group. Moreover, there are 2-morphisms between the 1-morphisms. They have both a horizontal ◦ and a vertical composition. The horizontal composition we denote , since this is the same · direction as the composition of 1-morphisms. The vertical composition we denote . The two compositions must be compatible, in the sense that the following composite is well-deﬁned: (cid:48) γ3 γ3 (cid:48) (cid:3)(cid:3) (cid:111)(cid:111) (cid:11)(cid:19) χ2 (cid:3)(cid:3) (cid:111)(cid:111) (cid:11)(cid:19) χ2 (cid:63)(cid:91)(cid:91) (cid:63)(cid:91)(cid:91) (cid:63) (2) γ2 γ2(cid:48) (cid:11)(cid:19) χ1 (cid:11)(cid:19) χ(cid:48)1 γ1 γ1(cid:48) This is expressed as the “interchange law” · ◦ (cid:48) · (cid:48) ◦ (cid:48) · ◦ (cid:48) (χ χ ) (χ χ ) = (χ χ ) (χ χ ) (3) 1 2 1 2 1 1 2 2 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: deﬁnitions

text: specify

text: the

text: objects

text: of

text: three

text: equivalent

label: section

text: as

text: One

text: very

text: useful

text: deﬁnition

text: of

text: a

text: is

text: motivated

text: by

text: analogy

text: to

text: the

text: deﬁnition

text: of

text: a

text: group

text: as

text: a

text: (small)

text: one-object

text: category

text: whose

text: morphisms

text: are

text: all

text: invertible.

text: In

text: this

text: case,

text: the

text: elements

text: of

text: the

text: group

text: are

text: the

text: set

text: of

text: morphisms

text: of

text: the

text: category,

text: and

text: the

text: group

text: multiplication

text: is

text: the

text: composition.

text: This

text: highlights

text: the

text: way

text: the

text: deﬁnition

text: of

text: a

text: category

text: generalized

text: the

text: notion

text: of

text: “composition”

text: which

text: begins

text: with

text: algebraic

text: gadgets

text: such

text: as

text: groups.

text: One

text: might

text: equally

text: well

text: deﬁne

text: a

text: (small)

text: category

text: in

text: algebraic

text: language

text: as

text: a

text: unital

text: semigroupoid.

text: Taking

text: the

text: deﬁnition

text: of

text: category

text: as

text: more

text: basic

text: gives

text: a

text: group

text: as

text: a

text: special

text: case.

text: While

text: of

text: course

text: not

text: the

text: standard

text: deﬁnition

text: of

text: a

text: group,

text: it

text: is

text: at

text: least

text: straightforward

text: to

text: generalize

text: to

text: “higher”

text: groups

text: in

text: the

text: sense

text: of

text: higher

text: category

text: theory.

text: (We

text: will

text: assume

text: some

text: familiarity

text: with

text: in

text: what

text: follows,

text: though

text: for

text: readers

text: who

text: are

text: not

text: so

text: familiar

text: we

text: suggest

text: the

text: succinct

text: note

text: by

text: Leinster

text: as

text: a

text: starting

text: point,

text: and

text: the

text: more

text: comprehensive

text: survey

text: by

text: Lack

text: and

text: Chapter

text: of

text: Borceux

text: for

text: more

text: detail.)

text: G

text: G

text: Deﬁnition

text: A

text: is

text: a

text: with

text: one

text: object

text: for

text: which

text: all

text: G

text: G

text: γ

text: and

text: χ

text: are

text: invertible.

text: G

text: Note

text: that

text: in

text: the

text: case

text: of

text: χ

text: we

text: requrie

text: invertibility

text: with

text: respect

text: to

text: both

text: horizontal

text: and

text: vertical

text: composition.

text: Let

text: us

text: unpack

text: this

text: deﬁnition

text: more

text: explicitly.

text: G

text: Suppose

text: is

text: a

text: There

text: are

text: various

text: from

text: to

text: itself,

text: which

text: have

text: a

text: composition

text: operation,

text: since

text: all

text: such

text: morphisms

text: have

text: matching

text: source

text: and

text: target:

text: γ1

text: γ2

text: γ1

text: γ2

text: Composition

text: of

text: morphisms

text: is

text: the

text: multiplication,

text: which

text: is

text: therefore

text: associative,

text: and

text: every

text: G

text: morphism

text: must

text: have

text: an

text: inverse

text: by

text: the

text: deﬁnition

text: of

text: a

text: so

text: forms

text: a

text: group.

text: Moreover,

text: there

text: are

text: between

text: the

text: They

text: have

text: both

text: a

text: horizontal

text: and

text: a

text: vertical

text: composition.

text: The

text: horizontal

text: composition

text: we

text: denote

text: since

text: this

text: is

text: the

text: same

text: direction

text: as

text: the

text: composition

text: of

text: The

text: vertical

text: composition

text: we

text: denote

text: The

text: two

text: compositions

text: must

text: be

text: compatible,

text: in

text: the

text: sense

text: that

text: the

text: following

text: composite

text: is

text: well-deﬁned:

text: γ3

text: γ3

text: χ2

text: χ2

text: γ2

text: χ1

text: γ1

text: This

text: is

text: expressed

text: as

text: the

text: “interchange

text: law”

text: (χ

text: χ

text: (χ

text: χ

text: (χ

text: χ

text: (χ

text: χ

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: { } A set t , . . . , t − of unitary transformations is k-cyclic if it has the form → 0 k 1 → → → t = (q q ), t = (q q ), . . . , t − = (q − q − ), t − = (q − q ), 0 0 1 1 1 2 k 2 k 2 k 1 k 1 k 1 0 where the q are distinct. i Lemma 1. Let T be a set of unitary transformations. { } (cid:62) (cid:104) (cid:105) 1. If T has a k-cyclic subset t , . . . , t − with k 3, then T is not aperiodic. 0 { k 1 } → 2. If T contains a subset T = t , t , t , t , t , t where t = (q q ) ∈ 6 (cid:104) (cid:105)01 10 12 13 21 31 i,j i j and q , q , q , q Q, then T is not aperiodic. 0 1 2 3 Proof. Without loss of generality, we can replace q by i in both claims. i (cid:54) 1. Suppose that T contains t , . . . , t − , where k n, t = (q, q + 1) for − 0 − k →1 q q = 0, . . . , k 2, and t − = (k 1 0). Then t − t − . . . t t t − maps − k 1 − − − k 2 k 3 1 0 k 1 0 to 1, 1 to 2, . . . , k 3 to k 2, k 2 to 0, and k 1 to 0, and does not aﬀect { − } any other states. Thus the set 0, 1, . . . , k 2 is cyclically permuted, which (cid:104) (cid:105) shows that T is not aperiodic. { } ⊆ 2. If t , t , t , t , t , t T, then the transformation t t t t t t 01 12 13 10 21 31 (cid:104) (cid:105) 12 01 13 21 10 3(cid:116)(cid:117)1 transposes 0 and 1; hence T is not aperiodic. D Theorem 1. If = (Q, Σ, δ, 0, F) is unitary, the following are equivalent: D 1. is aperiodic. D (cid:62) 2. The set of generators of does not contain any k-cyclic subsets with k 3, and does not contain any sets of type T . 6D 3. Every strongly connected component of is a bipath. ⇒ Proof. 1 2: This follows from Lemma 1. ⇒ | | 2 3: Consider a strongly connected component C. If C = 1, the claim ∈ → holds. Otherwise, suppose p C and (p q) is a transition. Then there must → also be a directed path from q to p. If the last transition in that path is (r p), (cid:54) where r = q, then the set of generators must contain a k-cyclic subset with (cid:62) → k 3, which is a contradiction. Hence the transition (q p) must be present. → → → Next, suppose that there are transitions (p q), (p r), and (p s). → → By the argument above there must also be transitions (q p), (r p), and → (r s). But then the set of generators contains a subset of type T , which is 6 again a contradiction. It follows that every strongly connected component is a bipath, and the graph D of the transitions of is a loop-free connection of such bipaths. ⇒ 3 1: Since a bipath is monotonic, it is aperiodic by Proposition 1. By Schu¨tzenberger’s theorem [16], the language of all words taking any state of the D bipath to any other state of that bipath is star-free. Since the graph of is a D loop-free connection of bipaths, the language of all words taking any state of D D (cid:116)(cid:117) to any other state of is star-free. Hence is aperiodic. A unitary DFA is complete if the addition of any unitary transition results in a DFA that is not aperiodic. Theorem 2. A maximal aperiodic unitary semigroup is isomorphic to the tran- D sition semigroup of a complete unitary DFA (n , . . . , n ), where (n , . . . , n ) u 1 m 1 m is some distribution of Q. 12

text: A

text: set

text: t

text: t

text: of

text: unitary

text: transformations

text: is

text: k-cyclic

text: if

text: it

text: has

text: the

text: form

text: k

text: t

text: (q

text: q

text: t

text: (q

text: q

text: t

text: (q

text: q

text: t

text: (q

text: q

text: k

text: k

text: k

text: k

text: k

text: where

text: the

text: q

text: are

text: distinct.

text: i

text: Lemma

text: Let

text: T

text: be

text: a

text: set

text: of

text: unitary

text: transformations.

text: If

text: T

text: has

text: a

text: k-cyclic

text: subset

text: t

text: t

text: with

text: k

text: then

text: T

text: is

text: not

text: aperiodic.

text: k

text: If

text: T

text: contains

text: a

text: subset

text: T

text: t

text: t

text: t

text: t

text: t

text: t

text: where

text: t

text: (q

text: q

text: i,j

text: i

text: j

text: and

text: q

text: q

text: q

text: q

text: Q,

text: then

text: T

text: is

text: not

text: aperiodic.

text: Proof.

text: Without

text: loss

text: of

text: generality,

text: we

text: can

text: replace

text: q

text: by

text: i

text: in

text: both

text: claims.

text: i

text: Suppose

text: that

text: T

text: contains

text: t

text: t

text: where

text: k

text: n,

text: t

text: (q,

text: q

text: for

text: k

text: →1

text: q

text: q

text: k

text: and

text: t

text: (k

text: Then

text: t

text: t

text: t

text: t

text: t

text: maps

text: k

text: k

text: k

text: k

text: to

text: to

text: k

text: to

text: k

text: k

text: to

text: and

text: k

text: to

text: and

text: does

text: not

text: aﬀect

text: any

text: other

text: states.

text: Thus

text: the

text: set

text: k

text: is

text: cyclically

text: permuted,

text: which

text: shows

text: that

text: T

text: is

text: not

text: aperiodic.

text: If

text: t

text: t

text: t

text: t

text: t

text: t

text: T,

text: then

text: the

text: transformation

text: t

text: t

text: t

text: t

text: t

text: t

text: transposes

text: and

text: hence

text: T

text: is

text: not

text: aperiodic.

text: D

text: Theorem

text: If

text: (Q,

text: Σ,

text: δ,

text: F)

text: is

text: unitary,

text: the

text: following

text: are

text: equivalent:

text: D

text: is

text: aperiodic.

text: D

text: The

text: set

text: of

text: generators

text: of

text: does

text: not

text: contain

text: any

text: k-cyclic

text: subsets

text: with

text: k

text: and

text: does

text: not

text: contain

text: any

text: sets

text: of

text: type

text: T

text: Every

text: strongly

text: connected

text: component

text: of

text: is

text: a

text: bipath.

text: Proof.

text: This

text: follows

text: from

text: Lemma

text: Consider

text: a

text: strongly

text: connected

text: component

text: C.

text: If

text: C

text: the

text: claim

text: holds.

text: Otherwise,

text: suppose

text: p

text: C

text: and

text: (p

text: q)

text: is

text: a

text: transition.

text: Then

text: there

text: must

text: also

text: be

text: a

text: directed

text: path

text: from

text: q

text: to

text: p.

text: If

text: the

text: last

text: transition

text: in

text: that

text: path

text: is

text: (r

text: p),

text: where

text: r

text: q,

text: then

text: the

text: set

text: of

text: generators

text: must

text: contain

text: a

text: k-cyclic

text: subset

text: with

text: k

text: which

text: is

text: a

text: contradiction.

text: Hence

text: the

text: transition

text: (q

text: p)

text: must

text: be

text: present.

text: Next,

text: suppose

text: that

text: there

text: are

text: transitions

text: (p

text: q),

text: (p

text: r),

text: and

text: (p

text: s).

text: By

text: the

text: argument

text: above

text: there

text: must

text: also

text: be

text: transitions

text: (q

text: p),

text: (r

text: p),

text: and

text: (r

text: s).

text: But

text: then

text: the

text: set

text: of

text: generators

text: contains

text: a

text: subset

text: of

text: type

text: T

text: which

text: is

text: again

text: a

text: contradiction.

text: It

text: follows

text: that

text: every

text: strongly

text: connected

text: component

text: is

text: a

text: bipath,

text: and

text: the

text: graph

text: D

text: of

text: the

text: transitions

text: of

text: is

text: a

text: loop-free

text: connection

text: of

text: such

text: bipaths.

text: Since

text: a

text: bipath

text: is

text: monotonic,

text: it

text: is

text: aperiodic

text: by

text: Proposition

text: By

text: Schu¨tzenberger’s

text: theorem

text: the

text: language

text: of

text: all

text: words

text: taking

text: any

text: state

text: of

text: the

text: D

text: bipath

text: to

text: any

text: other

text: state

text: of

text: that

text: bipath

text: is

text: star-free.

text: Since

text: the

text: graph

text: of

text: is

text: a

text: D

text: loop-free

text: connection

text: of

text: bipaths,

text: the

text: language

text: of

text: all

text: words

text: taking

text: any

text: state

text: of

text: D

text: D

text: to

text: any

text: other

text: state

text: of

text: is

text: star-free.

text: Hence

text: is

text: aperiodic.

text: A

text: unitary

text: DFA

text: is

text: complete

text: if

text: the

text: addition

text: of

text: any

text: unitary

text: transition

text: results

text: in

text: a

text: DFA

text: that

text: is

text: not

text: aperiodic.

text: Theorem

text: A

text: maximal

text: aperiodic

text: unitary

text: semigroup

text: is

text: isomorphic

text: to

text: the

text: tran-

text: D

text: sition

text: semigroup

text: of

text: a

text: complete

text: unitary

text: DFA

text: (n

text: n

text: where

text: (n

text: n

text: u

text: m

text: m

text: is

text: some

text: distribution

text: of

text: Q.


text: Proof. This follows by induction on m. For m = 1 we have a bipath. For m > 1, D D (∆ (n , . . . , n )) is the semiconstant sum of (∆ (n , . . . , n )) and Dscti Q 1 m scti Q 1 r (∆ (n , . . . , n )). By the inductive assumption and Lemma 3 we know sctiD Q r+1 m that (∆ (n , . . . , n )) is also aperiodic. And by Lemma 4 we know that no scti Q 1 m (cid:116)(cid:117) more transitions can be added. In order to count the size of the semigroup of a semiconstant sum, we extend the concept of partial transformations to k-partial transformations. Deﬁnition 4. A k-partial transformation of Q is a transformation of Q into ∪ {(cid:3) (cid:3) (cid:3) } (cid:3) (cid:3) (cid:3) Q , , . . . , , where , , . . . , are pairwise distinct, and distinct 1 ∈2 k 1 2 k from all q Q. A Let = (Q, Σ, δ, s, F) be a DFA, and let t be a k-partial transformation of A (cid:48) ∈ Q. We say that t is consistent for if there exists t in δ such that if qt Q, (cid:48) ∈ then qt = qt for all q Q. The set of consistent k-partial transformations of a semigroup describes its potential for forming a large number of transformations, when used in a semicon- (cid:62) stant sum. For a ﬁxed n 6, there exist semigroups with smaller cardinalities than the maximal ones, but with larger numbers of consistent k-partial transfor- mations for some k. Thus k-partial transformations are useful for ﬁnding such non-maximal semigroups, as they can result in larger semigroups when used in sums. A N → N The transition semigroup of can be characterized by a function fA : counting all consistent k-partial transformations for a given k. For example, for A k = 1, fA is the number of all consistent partial transformations for . For a DFA A D D = (n , . . . , n ), fA(1) is the size of the semigroup of (n , . . . , n , 1). ui 1 m ui 1 m From the proof of Theorem 3 we know that the number of consistent k-partial (cid:18) (cid:19) (cid:18) (cid:19)(cid:18) (cid:19) transformations for a bipath of size n h(cid:88)aving an identity transformation is − − − n 1 2n 1 − n n + h 1 m (n, k) = + kn h . bi n h h h=0 A B Theorem 5. Let and be strongly connected DFAs with n and m states, respectively. Let fA(k) and fB(k) be the functions counting their consistent k- partial transformations. Then the function fC counting the consistent k-partial C A B transformations of the semiconstant sum = ( , ) is − fC(k) = fA(m + k)fB(k) + n(k + 1)n((k + 1)m km). (cid:104) A B (cid:105) Proof. Consider a transformation t in ( , ) . | ∩ | ◦ If QBt QA = 0, then t = tB tA, where tB is a k-partial transformation of Q into Q , and t is a k-partial transformation of QA into QB. Moreover tB B B A and tA are uniquely deﬁned by the images QBt and QAt, respectively. We have fB(k) possible t transformations, and fA(m + k) possible tA transformations, B A since tA corresponds to an (m + k)-partial transformation of . So we have fA(m + k)fB(k) diﬀerent k-partial transformations t in this case. 18

text: Proof.

text: This

text: follows

text: by

text: induction

text: on

text: m.

text: For

text: m

text: we

text: have

text: a

text: bipath.

text: For

text: m

text: D

text: D

text: (n

text: n

text: is

text: the

text: semiconstant

text: sum

text: of

text: (n

text: n

text: and

text: Dscti

text: Q

text: m

text: scti

text: Q

text: r

text: (n

text: n

text: By

text: the

text: inductive

text: assumption

text: and

text: Lemma

text: we

text: know

text: sctiD

text: Q

text: m

text: that

text: (n

text: n

text: is

text: also

text: aperiodic.

text: And

text: by

text: Lemma

text: we

text: know

text: that

text: no

text: scti

text: Q

text: m

text: more

text: transitions

text: can

text: be

text: added.

text: In

text: order

text: to

text: count

text: the

text: size

text: of

text: the

text: semigroup

text: of

text: a

text: semiconstant

text: sum,

text: we

text: extend

text: the

text: concept

text: of

text: partial

text: transformations

text: to

text: k-partial

text: transformations.

text: Deﬁnition

text: A

text: k-partial

text: transformation

text: of

text: Q

text: is

text: a

text: transformation

text: of

text: Q

text: into

text: Q

text: where

text: are

text: pairwise

text: distinct,

text: and

text: distinct

text: ∈2

text: k

text: k

text: from

text: all

text: q

text: Q.

text: A

text: Let

text: (Q,

text: Σ,

text: δ,

text: s,

text: F)

text: be

text: a

text: DFA,

text: and

text: let

text: t

text: be

text: a

text: k-partial

text: transformation

text: of

text: A

text: Q.

text: We

text: say

text: that

text: t

text: is

text: consistent

text: for

text: if

text: there

text: exists

text: t

text: in

text: δ

text: such

text: that

text: if

text: qt

text: Q,

text: then

text: qt

text: qt

text: for

text: all

text: q

text: Q.

text: The

text: set

text: of

text: consistent

text: k-partial

text: transformations

text: of

text: a

text: semigroup

text: describes

text: its

text: potential

text: for

text: forming

text: a

text: large

text: number

text: of

text: transformations,

text: when

text: used

text: in

text: a

text: semicon-

text: stant

text: sum.

text: For

text: a

text: ﬁxed

text: n

text: there

text: exist

text: semigroups

text: with

text: smaller

text: cardinalities

text: than

text: the

text: maximal

text: ones,

text: but

text: with

text: larger

text: numbers

text: of

text: consistent

text: k-partial

text: transfor-

text: mations

text: for

text: some

text: k.

text: Thus

text: k-partial

text: transformations

text: are

text: useful

text: for

text: ﬁnding

text: such

text: non-maximal

text: semigroups,

text: as

text: they

text: can

text: result

text: in

text: larger

text: semigroups

text: when

text: used

text: in

text: sums.

text: A

text: N

text: N

text: The

text: transition

text: semigroup

text: of

text: can

text: be

text: characterized

text: by

text: a

text: function

text: fA

text: counting

text: all

text: consistent

text: k-partial

text: transformations

text: for

text: a

text: given

text: k.

text: For

text: example,

text: for

text: A

text: k

text: fA

text: is

text: the

text: number

text: of

text: all

text: consistent

text: partial

text: transformations

text: for

text: For

text: a

text: DFA

text: A

text: D

text: D

text: (n

text: n

text: is

text: the

text: size

text: of

text: the

text: semigroup

text: of

text: (n

text: n

text: ui

text: m

text: ui

text: m

text: From

text: the

text: proof

text: of

text: Theorem

text: we

text: know

text: that

text: the

text: number

text: of

text: consistent

text: k-partial

text: transformations

text: for

text: a

text: bipath

text: of

text: size

text: n

text: an

text: identity

text: transformation

text: is

text: n

text: n

text: n

text: h

text: m

text: (n,

text: k)

text: kn

text: h

text: bi

text: n

text: h

text: h

text: A

text: B

text: Theorem

text: Let

text: and

text: be

text: strongly

text: connected

text: DFAs

text: with

text: n

text: and

text: m

text: states,

text: respectively.

text: Let

text: fA(k)

text: and

text: fB(k)

text: be

text: the

text: functions

text: counting

text: their

text: consistent

text: k-

text: partial

text: transformations.

text: Then

text: the

text: function

text: fC

text: counting

text: the

text: consistent

text: k-partial

text: C

text: A

text: B

text: transformations

text: of

text: the

text: semiconstant

text: sum

text: is

text: fC(k)

text: fA(m

text: k)fB(k)

text: n(k

text: km).

text: A

text: B

text: Proof.

text: Consider

text: a

text: transformation

text: t

text: in

text: If

text: QBt

text: QA

text: then

text: t

text: tB

text: tA,

text: where

text: tB

text: is

text: a

text: k-partial

text: transformation

text: of

text: Q

text: into

text: Q

text: and

text: t

text: is

text: a

text: k-partial

text: transformation

text: of

text: QA

text: into

text: QB.

text: Moreover

text: tB

text: B

text: B

text: A

text: and

text: tA

text: are

text: uniquely

text: deﬁned

text: by

text: the

text: images

text: QBt

text: and

text: QAt,

text: respectively.

text: We

text: have

text: fB(k)

text: possible

text: t

text: transformations,

text: and

text: fA(m

text: k)

text: possible

text: tA

text: transformations,

text: B

text: A

text: since

text: tA

text: corresponds

text: to

text: an

text: (m

text: k)-partial

text: transformation

text: of

text: So

text: we

text: have

text: fA(m

text: k)fB(k)

text: diﬀerent

text: k-partial

text: transformations

text: t

text: in

text: this

text: case.


text: V ∪ Now, at each iteration, compute the Voronoi diagram (P X), and compute the set of bad features F ∪ (P X, P , P ). Compute the minimum ball in pencil(f) (see Eq. (4.1)) for each of the bad features b∈adF ∪ 1 2 f (P X, P , P ). Let b = ball(p, r) be the smallest ball encountered. Let P be a constant size bad 1 2 b set of points, such that any ball that intersects b (and is at least as large), must intersect P . Such a set b can be easily constructed by sprinkling a r-dense set in the enlarged ball ball(p, 2r). Note that P must b also stab b. The resulting set P has constant size (for example, by using grid points of the appropriate ← ∪ b size). Set X X P , and repeat. b sectioncolor 5.1.2. The Result (cid:0) (cid:1) Theorem 5.1. Let P be a set of n points in IRd, and (P , P ) be a given pair of disjoint subsets of P. One Z 1 2 can compute a Voronoi separator that realizes this partition. The algorithm runs in O(n2 log n) time (cid:100) (cid:101) for d = 2, and in O n d/2 +1 time, for d > 2. The algorithm provides a constant factor approximation to the smallest Voronoi separator realizing this partition. Proof. Observe the optimal solution is ﬁnite, as one can place d + 1 points around each point of P , 1 close enough, so that they Voronoi separate this point from the rest of P. As such, the optimal solution | | | | is of size at most (d + 1) min( P , P ). 1 2 As for the quality of approximation, this is a standard exchange argument. Indeed, consider the optimal solution, and observe that, at each iteration, the minimum ball found b must contain at least one point of the optimal solution, and the greedy algorithm replaces it in the approximation by the set P , such that any ball that is stabbed by a point of the optimal solution that is contained in b, and is b at least as big as b is also stabbed by some points of P . In particular, if c is the maximum size set P b b constructed by the algorithm (which is a constant), then the quality of approximation of the algorithm is c. (cid:0) (cid:1) The above implies that the algorithms terminates with at most O(n) points added. Since computing (cid:0) (cid:1) the Voronoi diagram takes O(n log n) time in the plane, this implies that the running of the algorithm (cid:100) (cid:101) in the plane is O(n2 log n). In higher dimensions, computing the Voronoi diagram takes O n d/2 , and (cid:100) (cid:101) overall, the algorithm takes O n d/2 +1 time. sectioncolor 5.2. Polynomial time approximation scheme Given a set P of n points in IRd, a parameter ε > 0, and a pair of disjoint subsets (P , P ) of P, we Z 1 2 show here how to (1 + ε)-approximate, in nO(1/εd) time, a Voronoi separator for (P , P ). 1 2 As implied by Lemma 4.3, this problem boils down to a hitting set problem. That is, the desired partition give rise to a set of balls B, such that our task is to approximate the minimum size hitting set for B. The challenge here is that B is an inﬁnite set, see Eq. (4.2) . (cid:0) (cid:1) p10 We need an improved separator theorem, as follows. | | Theorem 5.2. Let X be a set of points in IRd, and k > 0 be an integer suﬃciently smaller than X . | | Z − S One can compute, in O( X ) expected time, a set of O k1 1/d points and a sphere containing Θ(k) points of X inside it, such that for any set B of balls stabbed by X, we have that every ball of B that S Z intersects is stabbed by a point of . Due to space limitations, we had delegated the proof of Theorem 5.2 to Appendix – it is a careful extension of the proof of Theorem 3.7. sectioncolor 13

text: V

text: Now,

text: at

text: each

text: iteration,

text: compute

text: the

text: Voronoi

text: diagram

text: (P

text: X),

text: and

text: compute

text: the

text: set

text: of

text: bad

text: features

text: F

text: (P

text: X,

text: P

text: P

text: Compute

text: the

text: minimum

text: ball

text: in

text: pencil(f)

text: (see

text: Eq.

text: for

text: each

text: of

text: the

text: bad

text: features

text: b∈adF

text: f

text: (P

text: X,

text: P

text: P

text: Let

text: b

text: ball(p,

text: r)

text: be

text: the

text: smallest

text: ball

text: encountered.

text: Let

text: P

text: be

text: a

text: constant

text: size

text: bad

text: b

text: set

text: of

text: points,

text: such

text: that

text: any

text: ball

text: that

text: intersects

text: b

text: (and

text: is

text: at

text: least

text: as

text: large),

text: must

text: intersect

text: P

text: Such

text: a

text: set

text: b

text: can

text: be

text: easily

text: constructed

text: by

text: sprinkling

text: a

text: r-dense

text: set

text: in

text: the

text: enlarged

text: ball

text: ball(p,

text: Note

text: that

text: P

text: must

text: b

text: also

text: stab

text: b.

text: The

text: resulting

text: set

text: P

text: has

text: constant

text: size

text: (for

text: example,

text: by

text: using

text: grid

text: points

text: of

text: the

text: appropriate

text: b

text: size).

text: Set

text: X

text: X

text: P

text: and

text: repeat.

text: b

text: sectioncolor

text: The

text: Result

text: Theorem

text: Let

text: P

text: be

text: a

text: set

text: of

text: n

text: points

text: in

text: IRd,

text: and

text: (P

text: P

text: be

text: a

text: given

text: pair

text: of

text: disjoint

text: subsets

text: of

text: P.

text: One

text: Z

text: can

text: compute

text: a

text: Voronoi

text: separator

text: that

text: realizes

text: this

text: partition.

text: The

text: algorithm

text: runs

text: in

text: log

text: n)

text: time

text: for

text: d

text: and

text: in

text: O

text: n

text: time,

text: for

text: d

text: The

text: algorithm

text: provides

text: a

text: constant

text: factor

text: approximation

text: to

text: the

text: smallest

text: Voronoi

text: separator

text: realizing

text: this

text: partition.

text: Proof.

text: Observe

text: the

text: optimal

text: solution

text: is

text: ﬁnite,

text: as

text: one

text: can

text: place

text: d

text: points

text: around

text: each

text: point

text: of

text: P

text: close

text: enough,

text: so

text: that

text: they

text: Voronoi

text: separate

text: this

text: point

text: from

text: the

text: rest

text: of

text: P.

text: As

text: such,

text: the

text: optimal

text: solution

text: is

text: of

text: size

text: at

text: most

text: (d

text: min(

text: P

text: P

text: As

text: for

text: the

text: quality

text: of

text: approximation,

text: this

text: is

text: a

text: standard

text: exchange

text: argument.

text: Indeed,

text: consider

text: the

text: optimal

text: solution,

text: and

text: observe

text: that,

text: at

text: each

text: iteration,

text: the

text: minimum

text: ball

text: found

text: b

text: must

text: contain

text: at

text: least

text: one

text: point

text: of

text: the

text: optimal

text: solution,

text: and

text: the

text: greedy

text: algorithm

text: replaces

text: it

text: in

text: the

text: approximation

text: by

text: the

text: set

text: P

text: such

text: that

text: any

text: ball

text: that

text: is

text: stabbed

text: by

text: a

text: point

text: of

text: the

text: optimal

text: solution

text: that

text: is

text: contained

text: in

text: b,

text: and

text: is

text: b

text: at

text: least

text: as

text: big

text: as

text: b

text: is

text: also

text: stabbed

text: by

text: some

text: points

text: of

text: P

text: In

text: particular,

text: if

text: c

text: is

text: the

text: maximum

text: size

text: set

text: P

text: b

text: b

text: constructed

text: by

text: the

text: algorithm

text: (which

text: is

text: a

text: constant),

text: then

text: the

text: quality

text: of

text: approximation

text: of

text: the

text: algorithm

text: is

text: c.

text: The

text: above

text: implies

text: that

text: the

text: algorithms

text: terminates

text: with

text: at

text: most

text: O(n)

text: points

text: added.

text: Since

text: computing

text: the

text: Voronoi

text: diagram

text: takes

text: O(n

text: log

text: n)

text: time

text: in

text: the

text: plane,

text: this

text: implies

text: that

text: the

text: running

text: of

text: the

text: algorithm

text: in

text: the

text: plane

text: is

text: log

text: n).

text: In

text: higher

text: dimensions,

text: computing

text: the

text: Voronoi

text: diagram

text: takes

text: O

text: n

text: and

text: overall,

text: the

text: algorithm

text: takes

text: O

text: n

text: time.

text: sectioncolor

text: Polynomial

text: time

text: approximation

text: scheme

text: Given

text: a

text: set

text: P

text: of

text: n

text: points

text: in

text: IRd,

text: a

text: parameter

text: ε

text: and

text: a

text: pair

text: of

text: disjoint

text: subsets

text: (P

text: P

text: of

text: P,

text: we

text: Z

text: show

text: here

text: how

text: to

text: ε)-approximate,

text: in

text: time,

text: a

text: Voronoi

text: separator

text: for

text: (P

text: P

text: As

text: implied

text: by

text: Lemma

text: this

text: problem

text: boils

text: down

text: to

text: a

text: hitting

text: set

text: problem.

text: That

text: is,

text: the

text: desired

text: partition

text: give

text: rise

text: to

text: a

text: set

text: of

text: balls

text: B,

text: such

text: that

text: our

text: task

text: is

text: to

text: approximate

text: the

text: minimum

text: size

text: hitting

text: set

text: for

text: B.

text: The

text: challenge

text: here

text: is

text: that

text: B

text: is

text: an

text: inﬁnite

text: set,

text: see

text: Eq.

text: We

text: need

text: an

text: improved

text: separator

text: theorem,

text: as

text: follows.

text: Theorem

text: Let

text: X

text: be

text: a

text: set

text: of

text: points

text: in

text: IRd,

text: and

text: k

text: be

text: an

text: integer

text: suﬃciently

text: smaller

text: than

text: X

text: Z

text: S

text: One

text: can

text: compute,

text: in

text: O(

text: X

text: expected

text: time,

text: a

text: set

text: of

text: O

text: points

text: and

text: a

text: sphere

text: containing

text: Θ(k)

text: points

text: of

text: X

text: inside

text: it,

text: such

text: that

text: for

text: any

text: set

text: B

text: of

text: balls

text: stabbed

text: by

text: X,

text: we

text: have

text: that

text: every

text: ball

text: of

text: B

text: that

text: S

text: Z

text: intersects

text: is

text: stabbed

text: by

text: a

text: point

text: of

text: Due

text: to

text: space

text: limitations,

text: we

text: had

text: delegated

text: the

text: proof

text: of

text: Theorem

text: to

text: Appendix

text: it

text: is

text: a

text: careful

text: extension

text: of

text: the

text: proof

text: of

text: Theorem

text: sectioncolor


text: Why Voronoi separators are interesting? Some meshing algorithms rely on computing a Delaunay triangulation of geometric models to get good triangulations that describe solid bodies. Such meshes in turn are fed into numerical solvers to simulate various physical processes. To get good triangulations, one performs a Delaunay reﬁnement that involves inserting new points into the triangulations, to guarantee that the resulting elements are well behaved. Since the underlying geometric models can be quite complicated and these reﬁnement processes can be computationally intensive, it is natural to try and break up the data in a balanced way, and Voronoi separators provide one way to do so. More generally, small Voronoi separators provide a way to break up a point set in such a way that there is limited interaction between two pieces of the data. Geometric hitting set. Given a set of objects in IRd, the problem of ﬁnding a small number of points that stab all the objects is an instance of geometric hitting set. There is quite a bit of research on this problem. In particular, the problem is NP-Hard for almost any natural instance, but a polynomial time (1 + ε)-approximation algorithm is known for the case of balls in IRd [Cha03], where one is allowed to place the stabbing points anywhere. The discrete variant of this problem, where there is a set of allowable locations to place the stabbing points, seems to be signiﬁcantly harder and only weaker results are known [HL12]. One of the more interesting versions of the geometric hitting set problem, is the art gallery problem, where one is given a simple polygon in the plane, and one has to select a set of points (inside or on the boundary of the polygon) that “see” the whole polygon. While much research has gone into variants of this problem [O’R87], nothing is known as far as an approximation algorithm (for the general problem). The diﬃculty arises from the underlying set system being inﬁnite, see [EH06] for some eﬀorts in better understanding this problem. Geometric local search. Relatively little is known regarding local search methods for geometric approximation problems. Arya et al. [AGK+01] gave a local search method for approximating k-median clustering by a constant factor, and this was recently simpliﬁed by Gupta and Tangwongsan [GT08]. Closer to our settings, Mustafa and Ray [MR09] gave a local search algorithm for the discrete hitting set problem over pseudo disks and r-admissible regions in the plane, which yields a PTAS. Chan and Har-Peled [CH12] gave a local search PTAS for the independent set problem over fat objects, and for pseudodisks in the plane. Both works use separators in proving the quality of approximation. sectioncolor 1.1. Our Results In this paper we give algorithms for the following: (cid:0) (cid:1) listcolorComputing a small Voronoi separator. Given a set P of n points in IRd, we show how to − compute, in expected linear time, a balanced Voronoi separator of size O n1 1/d . This is described in Section . The existence of such a separator was not known before, and our proof is relatively simple and elegant. Such a separator can be used to break a large data-set into a small number of chunks, such that each chunk can be handled independently – potentially in parallel on diﬀerent computers. Exact algorithm for computing the smallest Voronoi separator realizing a given partition. In Section , given a partition (P , P ) of a point set P in IRd, we describe an algorithm that computes 1 2 the minimum size Voronoi separator realizing this separation. The running time of the algorithm is nO(b), where b is the cardinality of the optimal separating sets (the O notation is hiding a constant that depends on d). Constant approximation algorithm for the smallest Voronoi separator 3

text: Why

text: Voronoi

text: separators

text: are

text: interesting?

text: Some

text: meshing

text: algorithms

text: rely

text: on

text: computing

text: a

text: Delaunay

text: triangulation

text: of

text: geometric

text: models

text: to

text: get

text: good

text: triangulations

text: that

text: describe

text: solid

text: bodies.

text: Such

text: meshes

text: in

text: turn

text: are

text: fed

text: into

text: numerical

text: solvers

text: to

text: simulate

text: various

text: physical

text: processes.

text: To

text: get

text: good

text: triangulations,

text: one

text: performs

text: a

text: Delaunay

text: reﬁnement

text: that

text: involves

text: inserting

text: new

text: points

text: into

text: the

text: triangulations,

text: to

text: guarantee

text: that

text: the

text: resulting

text: elements

text: are

text: well

text: behaved.

text: Since

text: the

text: underlying

text: geometric

text: models

text: can

text: be

text: quite

text: complicated

text: and

text: these

text: reﬁnement

text: processes

text: can

text: be

text: computationally

text: intensive,

text: it

text: is

text: natural

text: to

text: try

text: and

text: break

text: up

text: the

text: data

text: in

text: a

text: balanced

text: way,

text: and

text: Voronoi

text: separators

text: provide

text: one

text: way

text: to

text: do

text: so.

text: More

text: generally,

text: small

text: Voronoi

text: separators

text: provide

text: a

text: way

text: to

text: break

text: up

text: a

text: point

text: set

text: in

text: such

text: a

text: way

text: that

text: there

text: is

text: limited

text: interaction

text: between

text: two

text: pieces

text: of

text: the

text: data.

text: Geometric

text: hitting

text: set.

text: Given

text: a

text: set

text: of

text: objects

text: in

text: IRd,

text: the

text: problem

text: of

text: ﬁnding

text: a

text: small

text: number

text: of

text: points

text: that

text: stab

text: all

text: the

text: objects

text: is

text: an

text: instance

text: of

text: geometric

text: hitting

text: set.

text: There

text: is

text: quite

text: a

text: bit

text: of

text: research

text: on

text: this

text: problem.

text: In

text: particular,

text: the

text: problem

text: is

text: NP-Hard

text: for

text: almost

text: any

text: natural

text: instance,

text: but

text: a

text: polynomial

text: time

text: ε)-approximation

text: algorithm

text: is

text: known

text: for

text: the

text: case

text: of

text: balls

text: in

text: IRd

text: where

text: one

text: is

text: allowed

text: to

text: place

text: the

text: stabbing

text: points

text: anywhere.

text: The

text: discrete

text: variant

text: of

text: this

text: problem,

text: where

text: there

text: is

text: a

text: set

text: of

text: allowable

text: locations

text: to

text: place

text: the

text: stabbing

text: points,

text: seems

text: to

text: be

text: signiﬁcantly

text: harder

text: and

text: only

text: weaker

text: results

text: are

text: known

text: One

text: of

text: the

text: more

text: interesting

text: versions

text: of

text: the

text: geometric

text: hitting

text: set

text: problem,

text: is

text: the

text: art

text: gallery

text: problem,

text: where

text: one

text: is

text: given

text: a

text: simple

text: polygon

text: in

text: the

text: plane,

text: and

text: one

text: has

text: to

text: select

text: a

text: set

text: of

text: points

text: (inside

text: or

text: on

text: the

text: boundary

text: of

text: the

text: polygon)

text: that

text: “see”

text: the

text: whole

text: polygon.

text: While

text: much

text: research

text: has

text: gone

text: into

text: variants

text: of

text: this

text: problem

text: nothing

text: is

text: known

text: as

text: far

text: as

text: an

text: approximation

text: algorithm

text: (for

text: the

text: general

text: problem).

text: The

text: diﬃculty

text: arises

text: from

text: the

text: underlying

text: set

text: system

text: being

text: inﬁnite,

text: see

text: for

text: some

text: eﬀorts

text: in

text: better

text: understanding

text: this

text: problem.

text: Geometric

text: local

text: search.

text: Relatively

text: little

text: is

text: known

text: regarding

text: local

text: search

text: methods

text: for

text: geometric

text: approximation

text: problems.

text: Arya

text: et

text: al.

text: gave

text: a

text: local

text: search

text: method

text: for

text: approximating

text: k-median

text: clustering

text: by

text: a

text: constant

text: factor,

text: and

text: this

text: was

text: recently

text: simpliﬁed

text: by

text: Gupta

text: and

text: Tangwongsan

text: Closer

text: to

text: our

text: settings,

text: Mustafa

text: and

text: Ray

text: gave

text: a

text: local

text: search

text: algorithm

text: for

text: the

text: discrete

text: hitting

text: set

text: problem

text: over

text: pseudo

text: disks

text: and

text: r-admissible

text: regions

text: in

text: the

text: plane,

text: which

text: yields

text: a

text: PTAS.

text: Chan

text: and

text: Har-Peled

text: gave

text: a

text: local

text: search

text: PTAS

text: for

text: the

text: independent

text: set

text: problem

text: over

text: fat

text: objects,

text: and

text: for

text: pseudodisks

text: in

text: the

text: plane.

text: Both

text: works

text: use

text: separators

text: in

text: proving

text: the

text: quality

text: of

text: approximation.

text: sectioncolor

text: Our

text: Results

text: In

text: this

text: paper

text: we

text: give

text: algorithms

text: for

text: the

text: following:

text: listcolorComputing

text: a

text: small

text: Voronoi

text: separator.

text: Given

text: a

text: set

text: P

text: of

text: n

text: points

text: in

text: IRd,

text: we

text: show

text: how

text: to

text: compute,

text: in

text: expected

text: linear

text: time,

text: a

text: balanced

text: Voronoi

text: separator

text: of

text: size

text: O

text: This

text: is

text: described

text: in

text: Section

text: The

text: existence

text: of

text: such

text: a

text: separator

text: was

text: not

text: known

text: before,

text: and

text: our

text: proof

text: is

text: relatively

text: simple

text: and

text: elegant.

text: Such

text: a

text: separator

text: can

text: be

text: used

text: to

text: break

text: a

text: large

text: data-set

text: into

text: a

text: small

text: number

text: of

text: chunks,

text: such

text: that

text: each

text: chunk

text: can

text: be

text: handled

text: independently

text: potentially

text: in

text: parallel

text: on

text: diﬀerent

text: computers.

text: Exact

text: algorithm

text: for

text: computing

text: the

text: smallest

text: Voronoi

text: separator

text: realizing

text: a

text: given

text: partition.

text: In

text: Section

text: given

text: a

text: partition

text: (P

text: P

text: of

text: a

text: point

text: set

text: P

text: in

text: IRd,

text: we

text: describe

text: an

text: algorithm

text: that

text: computes

text: the

text: minimum

text: size

text: Voronoi

text: separator

text: realizing

text: this

text: separation.

text: The

text: running

text: time

text: of

text: the

text: algorithm

text: is

text: nO(b),

text: where

text: b

text: is

text: the

text: cardinality

text: of

text: the

text: optimal

text: separating

text: sets

text: (the

text: O

text: notation

text: is

text: hiding

text: a

text: constant

text: that

text: depends

text: on

text: d).

text: Constant

text: approximation

text: algorithm

text: for

text: the

text: smallest

text: Voronoi

text: separator


text: bisector q pencil(p, q) q p p (A) (B) Figure 2.1: (A) The unbounded bisector induced by p and q. (B) The pencil of p and q. sectioncolor 2. Preliminaries ⊆ V For a point set P IRd, the Voronoi(cid:110)diagram(cid:12) of P, denoted by(cid:111) (P) is the partition of space into ∈ (cid:12) convex cells, where the Voronoi cell of p P is (cid:12) C ∈ (cid:107) − (cid:107) ≤ (p) = q IRd q p d(q, P) , P (cid:107) − (cid:107) where d(q, P) = min ∈ q s is the distance of q to the set P. Voronoi diagrams are a staple topic s P in Computational Geometry, see [BCKO08], and we include the deﬁnitions here for the sake of com- (cid:110) (cid:12) (cid:111) pleteness. In the plane, the Voronoi diagram has linea(cid:12)r descriptive complexity. For a point set P, and ∈ (cid:12) points p, q P, the geometric loci of all points in IRd that have both p and q as nearest neighbor, is the ∈ (cid:107) − (cid:107) (cid:107) − (cid:107) ∈ bisector of p and q – it is denoted by β = s IRd s p = s q = d(s, P) . A point s β is p,q p,q the center of a ball whose interior does not contain any point of P and that has p and q on its boundary. The set of all such balls induced by β is the pencil of p and q, denoted by pencil(p, q). p,q (((((DACBE))))) Deﬁnition 2.1. Let P be a set of points in IRd, and P and P be two disjoint subsets of P. The sets ∈ 1 2 ∈ P and P are Voronoi separated in P if for all p P and p P , we have that their Voronoi cells 1 2 C ∩ C ∅ 1 1 2 2 are disjoint; that is, (p ) (p ) = . P 1 P 2 ⊆ Deﬁnition 2.2. For a set P, a partition of P is a pair of sets (P , P ), such that P P, and \ Z 1 2 ⊆ 1 P = P P . A set is a Voronoi separator for a partition (P , P ) of P IRd, if P and P are 2 1 ∪ Z V 1∪ Z2 1 2 Voronoi separated in P ; that is, the Voronoi cells of P in (P ) do not intersect the Voronoi Z 1 cells of P . We will refer to the points of the separator as guards. 2 See Figure 1.1 for an example of the above deﬁnitions. Deﬁnition 2.3. For a ball b, its covering number is the minimum number of (closed) balls of half the radius that are needed to cover it. The doubling constant of a metric space is the maximum cover (cid:108) (cid:109) number over all possible balls. Let cd be the doubling constant for IRd. dbl √ ≤ d The constant cd is expon√ential in d, and cd 2 d – indeed, cover a ball (say, of unit radius) dbl dbl by a grid with sidelength 1/ d, and observe that each grid cell has diameter 1, and as such can be covered by a ball of radius 1/2. 5 ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: bisector

text: q

text: pencil(p,

text: q)

text: q

text: p

text: p

text: (A)

text: (B)

text: Figure

text: (A)

text: The

text: unbounded

text: bisector

text: induced

text: by

text: p

text: and

text: q.

text: (B)

text: The

text: pencil

text: of

text: p

text: and

text: q.

text: sectioncolor

text: Preliminaries

text: V

text: For

text: a

text: point

text: set

text: P

text: IRd,

text: the

text: of

text: P,

text: denoted

text: (P)

text: is

text: the

text: partition

text: of

text: space

text: into

text: convex

text: cells,

text: where

text: the

text: Voronoi

text: cell

text: of

text: p

text: P

text: is

text: C

text: (p)

text: q

text: IRd

text: q

text: p

text: d(q,

text: P)

text: P

text: where

text: d(q,

text: P)

text: min

text: q

text: s

text: is

text: the

text: distance

text: of

text: q

text: to

text: the

text: set

text: P.

text: Voronoi

text: diagrams

text: are

text: a

text: staple

text: topic

text: s

text: P

text: in

text: Computational

text: Geometry,

text: see

text: and

text: we

text: include

text: the

text: deﬁnitions

text: here

text: for

text: the

text: sake

text: of

text: com-

text: pleteness.

text: In

text: the

text: plane,

text: the

text: Voronoi

text: diagram

text: has

text: descriptive

text: complexity.

text: For

text: a

text: point

text: set

text: P,

text: and

text: points

text: p,

text: q

text: P,

text: the

text: geometric

text: loci

text: of

text: all

text: points

text: in

text: IRd

text: that

text: have

text: both

text: p

text: and

text: q

text: as

text: nearest

text: neighbor,

text: is

text: the

text: bisector

text: of

text: p

text: and

text: q

text: it

text: is

text: denoted

text: by

text: β

text: s

text: IRd

text: s

text: p

text: s

text: q

text: d(s,

text: P)

text: A

text: point

text: s

text: β

text: is

text: p,q

text: p,q

text: the

text: center

text: of

text: a

text: ball

text: whose

text: interior

text: does

text: not

text: contain

text: any

text: point

text: of

text: P

text: and

text: that

text: has

text: p

text: and

text: q

text: on

text: its

text: boundary.

text: The

text: set

text: of

text: all

text: such

text: balls

text: induced

text: by

text: β

text: is

text: the

text: pencil

text: of

text: p

text: and

text: q,

text: denoted

text: by

text: pencil(p,

text: q).

text: p,q

text: (((((DACBE)))))

text: Deﬁnition

text: Let

text: P

text: be

text: a

text: set

text: of

text: points

text: in

text: IRd,

text: and

text: P

text: and

text: P

text: be

text: two

text: disjoint

text: subsets

text: of

text: P.

text: The

text: sets

text: P

text: and

text: P

text: are

text: Voronoi

text: separated

text: in

text: P

text: if

text: for

text: all

text: p

text: P

text: and

text: p

text: P

text: we

text: have

text: that

text: their

text: Voronoi

text: cells

text: C

text: C

text: are

text: disjoint;

text: that

text: is,

text: (p

text: (p

text: P

text: P

text: Deﬁnition

text: For

text: a

text: set

text: P,

text: a

text: partition

text: of

text: P

text: is

text: a

text: pair

text: of

text: sets

text: (P

text: P

text: such

text: that

text: P

text: P,

text: and

text: Z

text: P

text: P

text: P

text: A

text: set

text: is

text: a

text: Voronoi

text: separator

text: for

text: a

text: partition

text: (P

text: P

text: of

text: P

text: IRd,

text: if

text: P

text: and

text: P

text: are

text: Z

text: V

text: 1∪

text: Voronoi

text: separated

text: in

text: P

text: that

text: is,

text: the

text: Voronoi

text: cells

text: of

text: P

text: in

text: (P

text: do

text: not

text: intersect

text: the

text: Voronoi

text: Z

text: cells

text: of

text: P

text: We

text: will

text: refer

text: to

text: the

text: points

text: of

text: the

text: separator

text: as

text: guards.

text: See

text: Figure

text: for

text: an

text: example

text: of

text: the

text: above

text: deﬁnitions.

text: Deﬁnition

text: For

text: a

text: ball

text: b,

text: its

text: covering

text: number

text: is

text: the

text: minimum

text: number

text: of

text: (closed)

text: balls

text: of

text: half

text: the

text: radius

text: that

text: are

text: needed

text: to

text: cover

text: it.

text: The

text: doubling

text: constant

text: of

text: a

text: metric

text: space

text: is

text: the

text: maximum

text: cover

text: number

text: over

text: all

text: possible

text: balls.

text: Let

text: cd

text: be

text: the

text: doubling

text: constant

text: for

text: IRd.

text: dbl

text: d

text: The

text: constant

text: cd

text: is

text: expon√ential

text: in

text: d,

text: and

text: cd

text: d

text: indeed,

text: cover

text: a

text: ball

text: (say,

text: of

text: unit

text: radius)

text: dbl

text: dbl

text: by

text: a

text: grid

text: with

text: sidelength

text: d,

text: and

text: observe

text: that

text: each

text: grid

text: cell

text: has

text: diameter

text: and

text: as

text: such

text: can

text: be

text: covered

text: by

text: a

text: ball

text: of

text: radius

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 8 MATHIAS LEDERER P t u Ď Proof of Theorem 2 (i). Let ∆ stn and rows(∆) := ∆0, . . . , ∆l bĎe the multiset of its rows. Let I S be an ideal deﬁning a point in Hn,ét(A2). We write A := supp(S/I) A2 for the set of n points corresponding to I. Propositions 3 and 5 imply that I deﬁnes a point in H∆ (A2) if, and only if, lex ‚ | | ´ ‚ |∆0| points of A sit on a horizontal line V(x2 ´ λ0), ‚ ∆1 points of A sit on a horizontal line V(x2 λ1), etc., and ‚ | | ´ ∆l points of A sit on a horizontal line V(x2 λl), ‰ ‰ P and λi λj for i j. Figure 4 shows an example of a conﬁguration of points deﬁning an ideal I H∆ (A2). The full moduli space H∆ (A2) is the space of conﬁgurations of n points in which the horizontal lex lex lines may move freely along the x -axis as long as they don’t collide, and the points on each horizontal ´ 2 line V(x2 λj) may move freely along this line as long as they don’t collide. λ3 λ2 λ1 ∆ λ0 = P Figure 4. A conﬁguration of points deﬁning an ideal I H∆ (A2) lex Within the moduli space Hn(A2), however, points have more freedom to move. Consider a conﬁgu- ration A of n reduced points deﬁning a point in H∆,ét(A2) such the one from Figure 4. Understanding to which conﬁguration of n reduced points the given conﬁguration A may degenerate without leaving H∆,ét(A2) amounts to determining the closure of H∆ (A2) in Hn,ét(A2). Here is how to determine that lex ´ degeneration: First off, none of the points sitting on a horizontal line V(x2 λj) may leave the line they sit on. Moreover, none of the points may collide with each other. However, it may and will happen that different horizontal lines merge into one. Of course if this happens, the points sitting on the respective lines will still stay away from each other. The combinatorial shadow of the merging process of horizontal ď ž lines in A2 is encoded in the partial ordering , as described earlier in the present section. What we ét have just proven is the inclusion H∆(A2) Ď H∆1 (A2). lex ∆ď ∆1 ét 1 As for the converse inclusion, it’s easy to see that each conﬁguration A of points corresponding to a point 1 in H∆ (A2) has arbitrarily close approximations by conﬁgurations A of points corresponding to points in H∆ (leAx 2). (cid:3) lex ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: TPTKVG+URWPalladioL-Roma

text: MATHIAS

text: LEDERER

text: P

text: t

text: u

text: Ď

text: Proof

font: HSLGKC+URWPalladioL-Ital

text: of

text: Theorem

text: (i).

text: Let

font: GVZZFR+PazoMath

text: stn

text: and

text: rows(∆)

text: ∆l

text: bĎe

text: the

text: multiset

text: of

text: its

text: rows.

text: Let

text: I

text: S

text: be

text: an

text: ideal

text: deﬁning

text: a

text: point

text: in

text: We

text: write

text: A

text: supp(S/I)

font: GVHONP+PazoMathBlackboardBold

text: for

text: the

text: set

text: of

text: n

text: points

text: corresponding

text: to

text: I.

text: Propositions

text: and

text: imply

text: that

text: I

text: deﬁnes

text: a

text: point

text: in

text: H∆

text: if,

text: and

text: only

text: if,

text: lex

text: points

text: of

text: A

text: sit

text: on

text: a

text: horizontal

text: line

text: ∆1

text: points

text: of

text: A

text: sit

text: on

text: a

text: horizontal

text: line

text: etc.,

text: and

text: ∆l

text: points

text: of

text: A

text: sit

text: on

text: a

text: horizontal

text: line

text: λl),

text: P

text: and

text: λi

text: λj

text: for

text: i

text: j.

text: Figure

text: shows

text: an

text: example

text: of

text: a

text: conﬁguration

text: of

text: points

text: deﬁning

text: an

text: ideal

text: I

text: H∆

text: The

text: full

text: moduli

text: space

text: H∆

text: is

text: the

text: space

text: of

text: conﬁgurations

text: of

text: n

text: points

text: in

text: which

text: the

text: horizontal

text: lex

text: lex

text: lines

text: may

text: move

text: freely

text: along

text: the

text: x

text: -axis

text: as

text: long

text: as

text: they

text: don’t

text: collide,

text: and

text: the

text: points

text: on

text: each

text: horizontal

text: line

text: λj)

text: may

text: move

text: freely

text: along

text: this

text: line

text: as

text: long

text: as

text: they

text: don’t

text: collide.

text: λ3

text: λ2

text: λ1

text: λ0

text: P

text: Figure

text: A

text: conﬁguration

text: of

text: points

text: deﬁning

text: an

text: ideal

text: I

text: H∆

text: lex

text: Within

text: the

text: moduli

text: space

text: however,

text: points

text: have

text: more

text: freedom

text: to

text: move.

text: Consider

text: a

text: conﬁgu-

text: ration

text: A

text: of

text: n

text: reduced

text: points

text: deﬁning

text: a

text: point

text: in

text: such

text: the

text: one

text: from

text: Figure

text: Understanding

text: to

text: which

text: conﬁguration

text: of

text: n

text: reduced

text: points

text: the

text: given

text: conﬁguration

text: A

text: may

text: degenerate

text: without

text: leaving

text: amounts

text: to

text: determining

text: the

text: closure

text: of

text: H∆

text: in

text: Here

text: is

text: how

text: to

text: determine

text: that

text: lex

text: degeneration:

text: First

text: off,

text: of

text: the

text: points

text: sitting

text: on

text: a

text: horizontal

text: line

text: λj)

text: may

text: leave

text: the

text: line

text: they

text: sit

text: on.

text: Moreover,

text: of

text: the

text: points

text: may

text: collide

text: with

text: each

text: other.

text: However,

text: it

text: may

text: and

text: will

text: happen

text: that

text: different

text: horizontal

text: lines

text: merge

text: into

text: one.

text: Of

text: course

text: if

text: this

text: happens,

text: the

text: points

text: sitting

text: on

text: the

text: respective

text: lines

text: will

text: still

text: stay

text: away

text: from

text: each

text: other.

text: The

text: combinatorial

text: shadow

text: of

text: the

text: merging

text: process

text: of

text: horizontal

text: ď

text: ž

text: lines

text: in

text: is

text: encoded

text: in

text: the

text: partial

text: ordering

text: as

text: described

text: earlier

text: in

text: the

text: present

text: section.

text: What

text: we

text: ét

text: have

text: just

text: proven

text: is

text: the

text: inclusion

text: Ď

text: lex

text: ∆ď

text: ∆1

text: ét

text: As

text: for

text: the

text: converse

text: inclusion,

text: it’s

text: easy

text: to

text: see

text: that

text: each

text: conﬁguration

text: A

text: of

text: points

text: corresponding

text: to

text: a

text: point

text: in

text: H∆

text: has

text: arbitrarily

text: close

text: approximations

text: by

text: conﬁgurations

text: A

text: of

text: points

text: corresponding

text: to

text: points

text: in

text: H∆

text: (leAx

text: lex

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: We use the above theorem to prove the depth 4 lower bound for the NW (X) polynomial (Theorem 4). Let us consider the polynomial NW (X) over any ﬁeld F[X].n√,(cid:15)First, we ﬁx an (cid:31) (cid:31) · · · (cid:31) n,(cid:15) ordering on the variables: x x x . We ﬁx a threshold k = µ n where µ is a 11 12 nn constant to be ﬁxed later. { } ∈ ≤ ≤ Consider the sets of variables of the form x , x , . . . , x such that i [n] for 1 j k. 1i1 2i2 kik j ∈ F Corresponding to any such set of variables, we can ﬁnd a univariate polynomial a(z) [z] of ≤ ≤ n degree < (cid:15)n such that a(j) = i for 1 j k. Number of such diﬀerent sets of size k is nk. Let j us represent these sets by S , S , . . . , S . 1 2 nk ≤ ≤ Now, we partition the monomials of NW (X) into sets B , B , . . . , B such that for 1 i n,(cid:15) 1 2 nk k, each monomial in the set B contains all the variables of the set S . i i ∈ Let P (X) be the polynomial corresponding to the sum of monomials in B for all i [nk]. We i i can express the polynomial NW (X) as follows. n,(cid:15) (cid:88) nk NW (X) = P (X) n,(cid:15) i i=1 Now, if we diﬀerentiate the polynomial NW (X) with respect to any particular set { } n,(cid:15) of variables S = x , x , . . . , x , we can see that only one of the polynomials in { j 1i1 } 2i2 kik P (X), P (X), . . . , P (X) contributes a leading monomial. Since any two monomials can in- 1 2 n−k tersect at at most (cid:15)n 1 places, t√he distance between the leading monomials (that we get after ≥ − − ∈ diﬀerentiation) will be ∆ n µ n (cid:15)n. We can consider any (cid:15) (0, 1), and then ﬁx c to be ≥ (cid:100) (cid:101) any constant −2 . Finally, we ﬁx µ to any value such that 0 < µ < 1 . 1 (cid:15) (cid:104) (cid:105) 40c Thus, we get at least nk diﬀerent polynomials in ∂=k(f) such that any two of their leading ≥ monomials have pair-wise distance n/c. Now we apply Theorem 17 with δ = 1 to obtain the following theorem (Theorem 4, restated from Section ). √ √ Theorem 18. Any depth four ΣΠ[O√( n)]ΣΠ[ n] circuit for computing the NWn,(cid:15)(X) polynomial (over any ﬁeld) must be of size 2Ω(cid:15)( nlogn). In [KSS13] and [FLMS13], the po√lynomials for which the similar lower bounds were proved have matching upper bounds of 2O( nlogn). F√rom [GKKS13a], the current depth 4 size lower bounds for Determinant and Permanent are 2Ω( n). To the best of our knowledge, the polynomial NWn,(cid:15)√(X) is t√he ﬁrst example of an explicit poly√nomial in VNP for which we have the depth four ΣΠ[O( n)]ΣΠ[ n] circuit size lower bound of 2Ω( nlogn) but no known matching upper bound. 8 Conclusion Then main interesting open problem is to prove that over the ﬁxed-size ﬁelds, any ΣΠΣ × circuit computing the determinant polynomial for a n n matrix must be of size 2Ω(nlogn). For an optimist, the task will be to ﬁnd a ΣΠΣ circuit of size 2o(nlogn) for the determinant polynomial. It seems that we need signiﬁcantly new ideas and techniques to make progress either on the lower bound side or on the upper bound side. References [Alo99] Noga Alon. Combinatorial nullstellensatz. Combinatorics, Probability and Comput- ing, 8, 1999. [AV08] Manindra Agrawal and V Vinay. Arithmetic circuits: A chasm at depth four. In Proceedings-Annual Symposium on Foundations of Computer Science, pages 67–75. IEEE, 2008. 12 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: We

text: use

text: the

text: above

text: theorem

text: to

text: prove

text: the

text: depth

text: lower

text: bound

text: for

text: the

text: NW

text: (X)

text: polynomial

text: (Theorem

text: Let

text: us

text: consider

text: the

text: polynomial

text: NW

text: (X)

text: over

text: any

text: ﬁeld

text: we

text: ﬁx

text: an

text: ordering

text: on

text: the

text: variables:

text: x

text: x

text: x

text: We

text: ﬁx

text: a

text: threshold

text: k

text: µ

text: n

text: where

text: µ

text: is

text: a

text: nn

text: constant

text: to

text: be

text: ﬁxed

text: later.

text: Consider

text: the

text: sets

text: of

text: variables

text: of

text: the

text: form

text: x

text: x

text: x

text: such

text: that

text: i

text: [n]

text: for

text: j

text: k.

text: kik

text: j

text: F

text: Corresponding

text: to

text: any

text: such

text: set

text: of

text: variables,

text: we

text: can

text: ﬁnd

text: a

text: univariate

text: polynomial

text: a(z)

text: [z]

text: of

text: n

text: degree

text: such

text: that

text: a(j)

text: i

text: for

text: j

text: k.

text: Number

text: of

text: such

text: diﬀerent

text: sets

text: of

text: size

text: k

text: is

text: nk.

text: Let

text: j

text: us

text: represent

text: these

text: sets

text: by

text: S

text: S

text: S

text: nk

text: Now,

text: we

text: partition

text: the

text: monomials

text: of

text: NW

text: (X)

text: into

text: sets

text: B

text: B

text: B

text: such

text: that

text: for

text: i

text: nk

text: k,

text: each

text: monomial

text: in

text: the

text: set

text: B

text: contains

text: all

text: the

text: variables

text: of

text: the

text: set

text: S

text: i

text: i

text: Let

text: P

text: (X)

text: be

text: the

text: polynomial

text: corresponding

text: to

text: the

text: sum

text: of

text: monomials

text: in

text: B

text: for

text: all

text: i

text: [nk].

text: We

text: i

text: i

text: can

text: express

text: the

text: polynomial

text: NW

text: (X)

text: as

text: follows.

text: nk

text: NW

text: (X)

text: P

text: (X)

text: i

text: Now,

text: if

text: we

text: diﬀerentiate

text: the

text: polynomial

text: NW

text: (X)

text: with

text: respect

text: to

text: any

text: particular

text: set

text: of

text: variables

text: S

text: x

text: x

text: x

text: we

text: can

text: see

text: that

text: only

text: one

text: of

text: the

text: polynomials

text: in

text: j

text: kik

text: P

text: (X),

text: P

text: (X),

text: P

text: (X)

text: contributes

text: a

text: leading

text: monomial.

text: Since

text: any

text: two

text: monomials

text: can

text: in-

text: n−k

text: tersect

text: at

text: at

text: most

text: places,

text: t√he

text: distance

text: between

text: the

text: leading

text: monomials

text: (that

text: we

text: get

text: after

text: diﬀerentiation)

text: will

text: be

text: n

text: µ

text: n

text: We

text: can

text: consider

text: any

text: and

text: then

text: ﬁx

text: c

text: to

text: be

text: any

text: constant

text: −2

text: Finally,

text: we

text: ﬁx

text: µ

text: to

text: any

text: value

text: such

text: that

text: µ

text: Thus,

text: we

text: get

text: at

text: least

text: nk

text: diﬀerent

text: polynomials

text: in

text: ∂=k(f)

text: such

text: that

text: any

text: two

text: of

text: their

text: leading

text: monomials

text: have

text: pair-wise

text: distance

text: n/c.

text: Now

text: we

text: apply

text: Theorem

text: with

text: δ

text: to

text: obtain

text: the

text: following

text: theorem

text: (Theorem

text: restated

text: from

text: Section

text: Theorem

text: Any

text: depth

text: four

text: ΣΠ[O√(

text: n)]ΣΠ[

text: n]

text: circuit

text: for

text: computing

text: the

text: polynomial

text: (over

text: any

text: ﬁeld)

text: must

text: be

text: of

text: size

text: nlogn).

text: In

text: and

text: the

text: po√lynomials

text: for

text: which

text: the

text: similar

text: lower

text: bounds

text: were

text: proved

text: have

text: matching

text: upper

text: bounds

text: of

text: nlogn).

text: F√rom

text: the

text: current

text: depth

text: size

text: lower

text: bounds

text: for

text: Determinant

text: and

text: Permanent

text: are

text: n).

text: To

text: the

text: best

text: of

text: our

text: knowledge,

text: the

text: polynomial

text: is

text: t√he

text: ﬁrst

text: example

text: of

text: an

text: explicit

text: poly√nomial

text: in

text: VNP

text: for

text: which

text: we

text: have

text: the

text: depth

text: four

text: ΣΠ[O(

text: n)]ΣΠ[

text: n]

text: circuit

text: size

text: lower

text: bound

text: of

text: nlogn)

text: but

text: no

text: known

text: matching

text: upper

text: bound.

text: Conclusion

text: Then

text: main

text: interesting

text: open

text: problem

text: is

text: to

text: prove

text: that

text: over

text: the

text: ﬁxed-size

text: ﬁelds,

text: any

text: ΣΠΣ

text: circuit

text: computing

text: the

text: determinant

text: polynomial

text: for

text: a

text: n

text: n

text: matrix

text: must

text: be

text: of

text: size

text: For

text: an

text: optimist,

text: the

text: task

text: will

text: be

text: to

text: ﬁnd

text: a

text: ΣΠΣ

text: circuit

text: of

text: size

text: for

text: the

text: determinant

text: polynomial.

text: It

text: seems

text: that

text: we

text: need

text: signiﬁcantly

text: new

text: ideas

text: and

text: techniques

text: to

text: make

text: progress

text: either

text: on

text: the

text: lower

text: bound

text: side

text: or

text: on

text: the

text: upper

text: bound

text: side.

text: References

text: Noga

text: Alon.

text: Combinatorial

text: nullstellensatz.

text: Combinatorics,

text: Probability

text: and

text: Comput-

text: ing,

text: Manindra

text: Agrawal

text: and

text: V

text: Vinay.

text: Arithmetic

text: circuits:

text: A

text: chasm

text: at

text: depth

text: four.

text: In

text: Proceedings-Annual

text: Symposium

text: on

text: Foundations

text: of

text: Computer

text: Science,

text: pages

text: IEEE,

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##