text: ﬂags to the agents’ states that indicate in which part of their current subroutine they are. Our protocols ensure that the agents that might inﬂuence each others routines are always nearby. Therefore, every agent can also check before starting its routine check if the other agents are ﬁnished with their routines. Furthermore, to check whether they have arrived to the immediate vicinity of another agents, they can (to be on the safe side), always visit their neighboring cells after every (sub)routine. For the sake of readability, these checks are omitted and assumed to be implicitly in the protocols. (cid:48) We begin by introducing a simple routine that allows two agents a and a − positioned in cells (x, y) and (x, y 1) to move to cells (x, y +1) and (x, y). Note (cid:48) that given this conﬁguration, agents a and a have implicitly encoded to which direction is “south”. They would not be able to distinguish this conﬁguration from the conﬁguration where their locations are reversed (or horizontally aligned for that matter). The same routine can be implemented to any cardinal direction analogously. For the simplicity of presentation, we introduce some convenient subroutines listed below. Local Search Subroutine LocalSearch(k) stands for a local search that is a building block for the other operations. Subroutine LocalSearch(k) is a simple DFS type search where the agents visit every cell (some perhaps multiple times) in a constant distance k and ﬁnds its way back by storing the visited ports in its memory. It easy to verify that this can be implemented by a single agent in our model. (cid:48) For the following operations, we assume that agents a and a are within at most constant distance k from each other and that k is known to the agents. (cid:48) (cid:48) Swap Operation Swap(a, a ) swaps the locations of agents a and a . Agent (cid:48) a ﬁnds the location of agent a by executing LocalSearch(k) and stores a port (cid:48) sequence leading to a in its memory. Then, a returns to its starting location and once the starting location is reached, assumes a special state that indicates (cid:48) that the original location is reached. Agent a performs LocalSearch(k) (possibly many times) until it ﬁnds agent a. Then, agent a can simply walk to the original (cid:48) location of a using the port sequence it stored. (cid:48) Distance Assume agents a and a are within distance k bounded by a constant. (cid:48) The distance subroutine measures Dist(a, a ) which can be achieved by executing LocalSearch(k). (cid:48) (cid:48) Around For subroutine Around(a , a), we assume that agents a and a are within at most two hops from each other. Consider ﬁrst the case that the distance (cid:48) − is one and assume that a occupies (x, y) and a occupies (x, y 1). The goal is (cid:48) to move agent a to cell (x, y + 1), i.e., “move around” agent a. Note that all other cases where the distance between the agents is 1 work analogously. (cid:48) First, agent a performs LocalSearch(1) to ﬁgure out which port leads to (cid:48) agent a, say port 1. Then, a performs LocalSearch(3) to ﬁnd a port sequence − S that leads to a that does not involve port 1 from cell (x, y 1). Note that − moving according to S from (x 1, y) cannot involve entering cell (x + 1, y), − since the distance from (x 1, y) to (x + 1, y) is greater than 2 through any (cid:48) other port than port 1. Now, a moves according to S to a cell adjacent to a. 25

text: ﬂags

text: to

text: the

text: agents’

text: states

text: that

text: indicate

text: in

text: which

text: part

text: of

text: their

text: current

text: subroutine

text: they

text: are.

text: Our

text: protocols

text: ensure

text: that

text: the

text: agents

text: that

text: might

text: inﬂuence

text: each

text: others

text: routines

text: are

text: always

text: nearby.

text: Therefore,

text: every

text: agent

text: can

text: also

text: check

text: before

text: starting

text: its

text: routine

text: check

text: if

text: the

text: other

text: agents

text: are

text: ﬁnished

text: with

text: their

text: routines.

text: Furthermore,

text: to

text: check

text: whether

text: they

text: have

text: arrived

text: to

text: the

text: immediate

text: vicinity

text: of

text: another

text: agents,

text: they

text: can

text: (to

text: be

text: on

text: the

text: safe

text: side),

text: always

text: visit

text: their

text: neighboring

text: cells

text: after

text: every

text: (sub)routine.

text: For

text: the

text: sake

text: of

text: readability,

text: these

text: checks

text: are

text: omitted

text: and

text: assumed

text: to

text: be

text: implicitly

text: in

text: the

text: protocols.

text: We

text: begin

text: by

text: introducing

text: a

text: simple

text: routine

text: that

text: allows

text: two

text: agents

text: a

text: and

text: a

text: positioned

text: in

text: cells

text: (x,

text: y)

text: and

text: (x,

text: y

text: to

text: move

text: to

text: cells

text: (x,

text: y

text: and

text: (x,

text: y).

text: Note

text: that

text: given

text: this

text: conﬁguration,

text: agents

text: a

text: and

text: a

text: have

text: implicitly

text: encoded

text: to

text: which

text: direction

text: is

text: “south”.

text: They

text: would

text: not

text: be

text: able

text: to

text: distinguish

text: this

text: conﬁguration

text: from

text: the

text: conﬁguration

text: where

text: their

text: locations

text: are

text: reversed

text: (or

text: horizontally

text: aligned

text: for

text: that

text: matter).

text: The

text: same

text: routine

text: can

text: be

text: implemented

text: to

text: any

text: cardinal

text: direction

text: analogously.

text: For

text: the

text: simplicity

text: of

text: presentation,

text: we

text: introduce

text: some

text: convenient

text: subroutines

text: listed

text: below.

text: Local

text: Search

text: Subroutine

text: LocalSearch(k)

text: stands

text: for

text: a

text: local

text: search

text: that

text: is

text: a

text: building

text: block

text: for

text: the

text: other

text: operations.

text: Subroutine

text: LocalSearch(k)

text: is

text: a

text: simple

text: DFS

text: type

text: search

text: where

text: the

text: agents

text: visit

text: every

text: cell

text: (some

text: perhaps

text: multiple

text: times)

text: in

text: a

text: constant

text: distance

text: k

text: and

text: ﬁnds

text: its

text: way

text: back

text: by

text: storing

text: the

text: visited

text: ports

text: in

text: its

text: memory.

text: It

text: easy

text: to

text: verify

text: that

text: this

text: can

text: be

text: implemented

text: by

text: a

text: single

text: agent

text: in

text: our

text: model.

text: For

text: the

text: following

text: operations,

text: we

text: assume

text: that

text: agents

text: a

text: and

text: a

text: are

text: within

text: at

text: most

text: constant

text: distance

text: k

text: from

text: each

text: other

text: and

text: that

text: k

text: is

text: known

text: to

text: the

text: agents.

text: Swap

text: Operation

text: Swap(a,

text: a

text: swaps

text: the

text: locations

text: of

text: agents

text: a

text: and

text: a

text: Agent

text: a

text: ﬁnds

text: the

text: location

text: of

text: agent

text: a

text: by

text: executing

text: LocalSearch(k)

text: and

text: stores

text: a

text: port

text: sequence

text: leading

text: to

text: a

text: in

text: its

text: memory.

text: Then,

text: a

text: returns

text: to

text: its

text: starting

text: location

text: and

text: once

text: the

text: starting

text: location

text: is

text: reached,

text: assumes

text: a

text: special

text: state

text: that

text: indicates

text: that

text: the

text: original

text: location

text: is

text: reached.

text: Agent

text: a

text: performs

text: LocalSearch(k)

text: (possibly

text: many

text: times)

text: until

text: it

text: ﬁnds

text: agent

text: a.

text: Then,

text: agent

text: a

text: can

text: simply

text: walk

text: to

text: the

text: original

text: location

text: of

text: a

text: using

text: the

text: port

text: sequence

text: it

text: stored.

text: Distance

text: Assume

text: agents

text: a

text: and

text: a

text: are

text: within

text: distance

text: k

text: bounded

text: by

text: a

text: constant.

text: The

text: distance

text: subroutine

text: measures

text: Dist(a,

text: a

text: which

text: can

text: be

text: achieved

text: by

text: executing

text: LocalSearch(k).

text: Around

text: For

text: subroutine

text: Around(a

text: a),

text: we

text: assume

text: that

text: agents

text: a

text: and

text: a

text: are

text: within

text: at

text: most

text: two

text: hops

text: from

text: each

text: other.

text: Consider

text: ﬁrst

text: the

text: case

text: that

text: the

text: distance

text: is

text: one

text: and

text: assume

text: that

text: a

text: occupies

text: (x,

text: y)

text: and

text: a

text: occupies

text: (x,

text: y

text: The

text: goal

text: is

text: to

text: move

text: agent

text: a

text: to

text: cell

text: (x,

text: y

text: i.e.,

text: “move

text: around”

text: agent

text: a.

text: Note

text: that

text: all

text: other

text: cases

text: where

text: the

text: distance

text: between

text: the

text: agents

text: is

text: work

text: analogously.

text: First,

text: agent

text: a

text: performs

text: to

text: ﬁgure

text: out

text: which

text: port

text: leads

text: to

text: agent

text: a,

text: say

text: port

text: Then,

text: a

text: performs

text: to

text: ﬁnd

text: a

text: port

text: sequence

text: S

text: that

text: leads

text: to

text: a

text: that

text: does

text: not

text: involve

text: port

text: from

text: cell

text: (x,

text: y

text: Note

text: that

text: moving

text: according

text: to

text: S

text: from

text: (x

text: y)

text: cannot

text: involve

text: entering

text: cell

text: (x

text: y),

text: since

text: the

text: distance

text: from

text: (x

text: y)

text: to

text: (x

text: y)

text: is

text: greater

text: than

text: through

text: any

text: other

text: port

text: than

text: port

text: Now,

text: a

text: moves

text: according

text: to

text: S

text: to

text: a

text: cell

text: adjacent

text: to

text: a.


text: a’ a’ a’ 1 N 1 1 N 1 N a 2 a 3 a’ 2 a3 2 (cid:48) (cid:48) Figure 5: To execute Around(a , a), agent a , denoted by the black circle, ﬁnds out which port leads to agent a, denoted by the red circle. Excluding this (cid:48) port, agent a performs LocalSearch(2) in all adjacent cells. The LocalSearch(2) (cid:48) performed one step to the north of the location a , denoted by the red cells, (cid:48) cannot lead to a. Therefore, a ﬁnds a cell either to the east or to the west from a. The subroutine is ﬁnished by performing an analogous trick. (cid:48) Note that agent a does not know which of the two possible cells adjacent to a it has entered. (cid:48) Assume w.l.o.g., that the port leading to a from the current location of a is (cid:48) port 1 and the port from which a entered its current location is port 2. The (cid:48) last step of a is to execute LocalSearch(3) to ﬁnd a port sequence that does not (cid:48) involve ports 1 and 2 (from the current cell of a ) and leads to the cell occupied by a, and move two steps according to this port sequence, to the cell adjacent to (cid:48) agent a. Agent a has now entered cell (x + 1, y). Please refer to Figure 5 for an illustration. The case where the initial distance is two is almost analogous. Assume that, (cid:48) − − (cid:48) initially, agent a occupies the cell (x 1, y 1). The goal is now to move agent a (cid:48) diagonally over a to the cell (x + 1, y + 1). Agent a begins by ﬁnding a port that − leads to a cell adjacent to a, say (x 1, y) by executing LocalSearch(2). Similarly (cid:48) to the case above agent a can ﬁnd its way to the cell (x, y + 1), store the port from which it entered and ﬁgure out which port leads to the cell occupied by a. (cid:48) As the last step, agent a performs a LocalSearch(2) from the ports not leading back nor to agent a and can derive that cell (x + 1, y + 1) is the one from which LocalSearch(2) leads to a. All other diagonal cases work analogously. Now, we are ﬁnally ready to introduce the movement routines that allow a pair of agents to move towards a desired cardinal or intermediate direction. Similarly to before, the agents are not aware of the actual cardinal direction, (cid:48) but we can ﬁx one for the sake of simplicity. Assume that agents a and a − occupy cells (x, y) and (x 1, y), respectively. The goal is to move agent a to (cid:48) cell (x + 1, y) and agent a to cell (x, y). Movement Given the subroutines above, it is now easy to implement a move- ment protocol for a pair of agents towards any cardinal or intermediate direction. (cid:48) More precisely, assume that agents a and a are aligned according to some cardi- nal or intermediate direction, say southwest, i.e., agent a is in some cell (x, y) (cid:48) (cid:48) (cid:48) and agent a in the cell (x + 1, y + 1). Now, agent a ﬁrst performs Around(a , a), (cid:48) − − (cid:48) that leads agent a to the cell (x 1, y 1). Performing Swap(a, a ) leads agent − − (cid:48) a to the cell (x 1, y 1) and agent a to the cell (x, y). In other words, agents 26 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: a’

label: paragraph

font: default

text: a’

text: a’

text: N

text: N

text: N

text: a

text: a

text: a’

label: caption

text: Figure

text: To

text: execute

text: Around(a

text: a),

text: agent

text: a

text: denoted

text: by

text: the

text: black

text: circle,

text: ﬁnds

text: out

text: which

text: port

text: leads

text: to

text: agent

text: a,

text: denoted

text: by

text: the

text: red

text: circle.

text: Excluding

text: this

text: port,

text: agent

text: a

text: performs

text: in

text: all

text: adjacent

text: cells.

text: The

text: performed

text: one

text: step

text: to

text: the

text: north

text: of

text: the

text: location

text: a

text: denoted

text: by

text: the

text: red

text: cells,

text: cannot

text: lead

text: to

text: a.

text: Therefore,

text: a

text: ﬁnds

text: a

text: cell

text: either

text: to

text: the

text: east

text: or

text: to

text: the

text: west

text: from

text: a.

text: The

text: subroutine

text: is

text: ﬁnished

text: by

text: performing

text: an

text: analogous

text: trick.

text: Note

text: that

text: agent

text: a

text: does

text: not

text: know

text: which

text: of

text: the

text: two

text: possible

text: cells

text: adjacent

text: to

text: a

text: it

text: has

text: entered.

text: Assume

text: w.l.o.g.,

text: that

text: the

text: port

text: leading

text: to

text: a

text: from

text: the

text: current

text: location

text: of

text: a

text: is

text: port

text: and

text: the

text: port

text: from

text: which

text: a

text: entered

text: its

text: current

text: location

text: is

text: port

text: The

text: last

text: step

text: of

text: a

text: is

text: to

text: execute

text: to

text: ﬁnd

text: a

text: port

text: sequence

text: that

text: does

text: not

text: involve

text: ports

text: and

text: (from

text: the

text: current

text: cell

text: of

text: a

text: and

text: leads

text: to

text: the

text: cell

text: occupied

text: by

text: a,

text: and

text: move

text: two

text: steps

text: according

text: to

text: this

text: port

text: sequence,

text: to

text: the

text: cell

text: adjacent

text: to

text: agent

text: a.

text: Agent

text: a

text: has

text: now

text: entered

text: cell

text: (x

text: y).

text: Please

text: refer

text: to

text: Figure

text: for

text: an

text: illustration.

text: The

text: case

text: where

text: the

text: initial

text: distance

text: is

text: two

text: is

text: almost

text: analogous.

text: Assume

text: that,

text: initially,

text: agent

text: a

text: occupies

text: the

text: cell

text: (x

text: y

text: The

text: goal

text: is

text: now

text: to

text: move

text: agent

text: a

text: diagonally

text: over

text: a

text: to

text: the

text: cell

text: (x

text: y

text: Agent

text: a

text: begins

text: by

text: ﬁnding

text: a

text: port

text: that

text: leads

text: to

text: a

text: cell

text: adjacent

text: to

text: a,

text: say

text: (x

text: y)

text: by

text: executing

text: Similarly

text: to

text: the

text: case

text: above

text: agent

text: a

text: can

text: ﬁnd

text: its

text: way

text: to

text: the

text: cell

text: (x,

text: y

text: store

text: the

text: port

text: from

text: which

text: it

text: entered

text: and

text: ﬁgure

text: out

text: which

text: port

text: leads

text: to

text: the

text: cell

text: occupied

text: by

text: a.

text: As

text: the

text: last

text: step,

text: agent

text: a

text: performs

text: a

text: from

text: the

text: ports

text: not

text: leading

text: back

text: nor

text: to

text: agent

text: a

text: and

text: can

text: derive

text: that

text: cell

text: (x

text: y

text: is

text: the

text: one

text: from

text: which

text: leads

text: to

text: a.

text: All

text: other

text: diagonal

text: cases

text: work

text: analogously.

text: Now,

text: we

text: are

text: ﬁnally

text: ready

text: to

text: introduce

text: the

text: movement

text: routines

text: that

text: allow

text: a

text: pair

text: of

text: agents

text: to

text: move

text: towards

text: a

text: desired

text: cardinal

text: or

text: intermediate

text: direction.

text: Similarly

text: to

text: before,

text: the

text: agents

text: are

text: not

text: aware

text: of

text: the

text: actual

text: cardinal

text: direction,

text: but

text: we

text: can

text: ﬁx

text: one

text: for

text: the

text: sake

text: of

text: simplicity.

text: Assume

text: that

text: agents

text: a

text: and

text: a

text: occupy

text: cells

text: (x,

text: y)

text: and

text: (x

text: y),

text: respectively.

text: The

text: goal

text: is

text: to

text: move

text: agent

text: a

text: to

text: cell

text: (x

text: y)

text: and

text: agent

text: a

text: to

text: cell

text: (x,

text: y).

text: Movement

text: Given

text: the

text: subroutines

text: above,

text: it

text: is

text: now

text: easy

text: to

text: implement

text: a

text: move-

text: ment

text: protocol

text: for

text: a

text: pair

text: of

text: agents

text: towards

text: any

text: cardinal

text: or

text: intermediate

text: direction.

text: More

text: precisely,

text: assume

text: that

text: agents

text: a

text: and

text: a

text: are

text: aligned

text: according

text: to

text: some

text: cardi-

text: nal

text: or

text: intermediate

text: direction,

text: say

text: southwest,

text: i.e.,

text: agent

text: a

text: is

text: in

text: some

text: cell

text: (x,

text: y)

text: and

text: agent

text: a

text: in

text: the

text: cell

text: (x

text: y

text: Now,

text: agent

text: a

text: ﬁrst

text: performs

text: Around(a

text: a),

text: that

text: leads

text: agent

text: a

text: to

text: the

text: cell

text: (x

text: y

text: Performing

text: Swap(a,

text: a

text: leads

text: agent

text: a

text: to

text: the

text: cell

text: (x

text: y

text: and

text: agent

text: a

text: to

text: the

text: cell

text: (x,

text: y).

text: In

text: other

text: words,

text: agents

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

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: (cid:48) 2. After turning southwest at the end of exploring T , agents a, a , NorthGuide, i − WestGuide, and EastGuide are located in cells ( 1, i), (0, i + 1), (0, i), − − − − ( 2i + 1, i + 1), and (2i 1, i + 1), respectively. 3. Every cell in T is visited by at least one agent. i Now, it is easy to verify the following observation that leads to Theorem 6 by observing that T , for any i, takes ﬁnite time. i Observation 5. Every triangle T is explored correctly. i Theorem 6. Five asynchronous agents can ﬁnd the treasure in the port num- bering model. 8 Conclusion In this paper, we considered the collaborative grid exploration problem with agents controlled by asynchronous ﬁnite automata. While this paper shows tight bounds for the minimum number of agents required to explore the grid in diﬀerent timing models, it remains an intriguing open question to generalize these results, especially ﬁnding non-trivial lower bounds, to more complex structures. References [1] Susanne Albers and Monika Henzinger. Exploring Unknown Environments. SIAM Journal on Computing, 29:1164–1188, 2000. [2] Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoﬀ. Random walks, universal traversal sequences, and the complexity of maze problems. In FOCS, pages 218–223, 1979. [3] Igor Averbakh and Oded Berman. A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discrete Appl. Math., 68(1-2):17–32, 1996. [4] Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins. Searching in the Plane. Information and Computation, 106:234–252, 1993. [5] M. A. Bender and D. K. Slonim. The power of team exploration: two robots can learn unlabeled directed graphs. In FOCS, pages 75–85, 1994. [6] M. Blum and W. J. Sakoda. On the capability of ﬁnite automata in 2 and 3 dimensional space. In FOCS, pages 147–161, 1977. [7] Manuel Blum and Dexter Kozen. On the power of the compass (or, why mazes are easier to search than graphs). In FOCS, pages 132–142, 1978. [8] Lothar Budach. Automata and labyrinths. Mathematische Nachrichten, 86(1):195–282, 1978. [9] Marek Chrobak, Leszek Gasieniec, Thomas Gorry, and Russell Martin. Group Search on the Line, pages 164–176. Springer Berlin Heidelberg, 2015. 30

label: list

text: After

text: turning

text: southwest

text: at

text: the

text: end

text: of

text: exploring

text: T

text: agents

text: a,

text: a

text: NorthGuide,

text: i

text: WestGuide,

text: and

text: EastGuide

text: are

text: located

text: in

text: cells

text: i),

text: i

text: i),

text: i

text: and

text: i

text: respectively.

text: Every

text: cell

text: in

text: T

text: is

text: visited

text: by

text: at

text: least

text: one

text: agent.

text: i

text: Now,

text: it

text: is

text: easy

text: to

text: verify

text: the

text: following

text: observation

text: that

text: leads

text: to

text: Theorem

text: by

text: observing

text: that

text: T

text: for

text: any

text: i,

text: takes

text: ﬁnite

text: time.

text: i

text: Observation

text: Every

text: triangle

text: T

text: is

text: explored

text: correctly.

text: i

text: Theorem

text: Five

text: asynchronous

text: agents

text: can

text: ﬁnd

text: the

text: treasure

text: in

text: the

text: port

text: num-

text: bering

text: model.

text: Conclusion

text: In

text: this

text: paper,

text: we

text: considered

text: the

text: collaborative

text: grid

text: exploration

text: problem

text: with

text: agents

text: controlled

text: by

text: asynchronous

text: ﬁnite

text: automata.

text: While

text: this

text: paper

text: shows

text: tight

text: bounds

text: for

text: the

text: minimum

text: number

text: of

text: agents

text: required

text: to

text: explore

text: the

text: grid

text: in

text: diﬀerent

text: timing

text: models,

text: it

text: remains

text: an

text: intriguing

text: open

text: question

text: to

text: generalize

text: these

text: results,

text: especially

text: ﬁnding

text: non-trivial

text: lower

text: bounds,

text: to

text: more

text: complex

text: structures.

text: References

text: Susanne

text: Albers

text: and

text: Monika

text: Henzinger.

text: Exploring

text: Unknown

text: Environments.

text: SIAM

text: Journal

text: on

text: Computing,

text: Romas

text: Aleliunas,

text: Richard

text: M.

text: Karp,

text: Richard

text: J.

text: Lipton,

text: Laszlo

text: Lovasz,

text: and

text: Charles

text: Rackoﬀ.

text: Random

text: walks,

text: universal

text: traversal

text: sequences,

text: and

text: the

text: complexity

text: of

text: maze

text: problems.

text: In

text: FOCS,

text: pages

text: Igor

text: Averbakh

text: and

text: Oded

text: Berman.

text: A

text: heuristic

text: with

text: worst-case

text: analysis

text: for

text: minimax

text: routing

text: of

text: two

text: travelling

text: salesmen

text: on

text: a

text: tree.

text: Discrete

text: Appl.

text: Math.,

text: Ricardo

text: A.

text: Baeza-Yates,

text: Joseph

text: C.

text: Culberson,

text: and

text: Gregory

text: J.

text: E.

text: Rawlins.

text: Searching

text: in

text: the

text: Plane.

text: Information

text: and

text: Computation,

text: M.

text: A.

text: Bender

text: and

text: D.

text: K.

text: Slonim.

text: The

text: power

text: of

text: team

text: exploration:

text: two

text: robots

text: can

text: learn

text: unlabeled

text: directed

text: graphs.

text: In

text: FOCS,

text: pages

text: M.

text: Blum

text: and

text: W.

text: J.

text: Sakoda.

text: On

text: the

text: capability

text: of

text: ﬁnite

text: automata

text: in

text: and

text: dimensional

text: space.

text: In

text: FOCS,

text: pages

text: Manuel

text: Blum

text: and

text: Dexter

text: Kozen.

text: On

text: the

text: power

text: of

text: the

text: compass

text: (or,

text: why

text: mazes

text: are

text: easier

text: to

text: search

text: than

text: graphs).

text: In

text: FOCS,

text: pages

text: Lothar

text: Budach.

text: Automata

text: and

text: labyrinths.

text: Mathematische

text: Nachrichten,

text: Marek

text: Chrobak,

text: Leszek

text: Gasieniec,

text: Thomas

text: Gorry,

text: and

text: Russell

text: Martin.

text: Group

text: Search

text: on

text: the

text: Line,

text: pages

text: Springer

text: Berlin

text: Heidelberg,


text: [10] Lihi Cohen, Yuval Emek, Oren Louidor, and Jara Uitto. Exploring an inﬁnite space with ﬁnite memory scouts. In SODA, pages 207–224, 2017. [11] Xiaotie Deng and Christos Papadimitriou. Exploring an Unknown Graph. Journal of Graph Theory, 32:265–297, 1999. [12] Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, and Andrzej Pelc. Tree Exploration with Little Memory. Journal of Algorithms, 51:38–63, 2004. [13] Yann Disser, Jan Hackfeld, and Max Klimm. Undirected graph exploration with θ(log log n) pebbles. In SODA, pages 25–39, 2016. [14] Stefan Dobrev, Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung. Finding Short Right-Hand-on-the-Wall Walks in Graphs, pages 127–139. Springer Berlin Heidelberg, 2005. [15] Christian A. Duncan, Stephen G. Kobourov, and V. S. Anil Kumar. Optimal constrained graph exploration. ACM Trans. Algorithms, 2(3):380–402, 2006. [16] Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Watten- hofer. How many ants does it take to ﬁnd the food? Theor. Comput. Sci., 608:255–267, 2015. [17] Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer. Solving the ANTS Problem with Asynchronous Finite State Machines. In ICALP, pages 471–482, 2014. [18] Ofer Feinerman, Amos Korman, Zvi Lotker, and Jean-Sebastien Sereni. Collaborative Search on the Plane Without Communication. In PODC, pages 77–86, 2012. [19] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Distributed coordination of a set of autonomous mobile robots. In Intelligent Vehicles Symposium, pages 480–485, 2000. [20] Pierre Fraigniaud and David Ilcinkas. Digraphs Exploration with Little Memory, pages 246–257. Springer Berlin Heidelberg, 2004. [21] Frank Hoﬀmann. One pebble does not suﬃce to search plane labyrinths. In FCT, pages 433–444, 1981. [22] Alejandro Lo´pez-Ortiz and Graeme Sweet. Parallel Searching on a Lattice. In CCCG, pages 125–128, 2001. [23] Petri¸sor Panaite and Andrzej Pelc. Exploring unknown undirected graphs. In SODA, pages 316–322, 1998. [24] H. A. Rollik. Automaten in planaren graphen, pages 266–275. Springer Berlin Heidelberg, Berlin, Heidelberg, 1979. [25] Kazuo Sugihara and Ichiro Suzuki. Distributed algorithms for formation of geometric patterns with many mobile robots. Journal of Robotic Systems, 13(3):127–139, 1996. 31

label: reference

text: Lihi

text: Cohen,

text: Yuval

text: Emek,

text: Oren

text: Louidor,

text: and

text: Jara

text: Uitto.

text: Exploring

text: an

text: inﬁnite

text: space

text: with

text: ﬁnite

text: memory

text: scouts.

text: In

text: SODA,

text: pages

text: Xiaotie

text: Deng

text: and

text: Christos

text: Papadimitriou.

text: Exploring

text: an

text: Unknown

text: Graph.

text: Journal

text: of

text: Graph

text: Theory,

text: Krzysztof

text: Diks,

text: Pierre

text: Fraigniaud,

text: Evangelos

text: Kranakis,

text: and

text: Andrzej

text: Pelc.

text: Tree

text: Exploration

text: with

text: Little

text: Memory.

text: Journal

text: of

text: Algorithms,

text: Yann

text: Disser,

text: Jan

text: Hackfeld,

text: and

text: Max

text: Klimm.

text: Undirected

text: graph

text: exploration

text: with

text: θ(log

text: log

text: n)

text: pebbles.

text: In

text: SODA,

text: pages

text: Stefan

text: Dobrev,

text: Jesper

text: Jansson,

text: Kunihiko

text: Sadakane,

text: and

text: Wing-Kin

text: Sung.

text: Finding

text: Short

text: Right-Hand-on-the-Wall

text: Walks

text: in

text: Graphs,

text: pages

text: Springer

text: Berlin

text: Heidelberg,

text: Christian

text: A.

text: Duncan,

text: Stephen

text: G.

text: Kobourov,

text: and

text: V.

text: S.

text: Anil

text: Kumar.

text: Optimal

text: constrained

text: graph

text: exploration.

text: ACM

text: Trans.

text: Algorithms,

text: Yuval

text: Emek,

text: Tobias

text: Langner,

text: David

text: Stolz,

text: Jara

text: Uitto,

text: and

text: Roger

text: Watten-

text: hofer.

text: How

text: many

text: ants

text: does

text: it

text: take

text: to

text: ﬁnd

text: the

text: food?

text: Theor.

text: Comput.

text: Sci.,

text: Yuval

text: Emek,

text: Tobias

text: Langner,

text: Jara

text: Uitto,

text: and

text: Roger

text: Wattenhofer.

text: Solving

text: the

text: ANTS

text: Problem

text: with

text: Asynchronous

text: Finite

text: State

text: Machines.

text: In

text: ICALP,

text: pages

text: Ofer

text: Feinerman,

text: Amos

text: Korman,

text: Zvi

text: Lotker,

text: and

text: Jean-Sebastien

text: Sereni.

text: Collaborative

text: Search

text: on

text: the

text: Plane

text: Without

text: Communication.

text: In

text: PODC,

text: pages

text: P.

text: Flocchini,

text: G.

text: Prencipe,

text: N.

text: Santoro,

text: and

text: P.

text: Widmayer.

text: Distributed

text: coordination

text: of

text: a

text: set

text: of

text: autonomous

text: mobile

text: robots.

text: In

text: Intelligent

text: Vehicles

text: Symposium,

text: pages

text: Pierre

text: Fraigniaud

text: and

text: David

text: Ilcinkas.

text: Digraphs

text: Exploration

text: with

text: Little

text: Memory,

text: pages

text: Springer

text: Berlin

text: Heidelberg,

text: Frank

text: Hoﬀmann.

text: One

text: pebble

text: does

text: not

text: suﬃce

text: to

text: search

text: plane

text: labyrinths.

text: In

text: FCT,

text: pages

text: Alejandro

text: Lo´pez-Ortiz

text: and

text: Graeme

text: Sweet.

text: Parallel

text: Searching

text: on

text: a

text: Lattice.

text: In

text: CCCG,

text: pages

text: Petri¸sor

text: Panaite

text: and

text: Andrzej

text: Pelc.

text: Exploring

text: unknown

text: undirected

text: graphs.

text: In

text: SODA,

text: pages

text: H.

text: A.

text: Rollik.

text: Automaten

text: in

text: planaren

text: graphen,

text: pages

text: Springer

text: Berlin

text: Heidelberg,

text: Berlin,

text: Heidelberg,

text: Kazuo

text: Sugihara

text: and

text: Ichiro

text: Suzuki.

text: Distributed

text: algorithms

text: for

text: formation

text: of

text: geometric

text: patterns

text: with

text: many

text: mobile

text: robots.

text: Journal

text: of

text: Robotic

text: Systems,


text: q q q (a) q (b) Figure 1: Figure 1a illustrates Case 2 of our schedule. In this case, an agent is scheduled until some state q in some cell c occurs for the second time. In Figure 1a, we illustrate Case 3 where one agent alone, walks inﬁnitely far away from the other two agents. This case cannot occur, since otherwise, the two remaining agents would have to explore the grid without the third agent. ensures that there is such a (ﬁnite) point in time t. Note that Case 3 can (cid:54) (cid:54) only occur if x = 0 or y = 0. Moreover, if this case actually occurs, then the complete subsequent sched- ule is adapted according to the following special rule (overriding all of the (cid:54) above): After time t, the two agents a , r = i are scheduled for one time r step each (in arbitrary order), then agent a is scheduled for k time steps, i i.e., exactly one travel period, and then we iterate this new scheduling. Note that according to this schedule, the number of time steps a scheduled agent can stay put in a cell during one of its subschedules is upper bounded by N. We now collect a few lemmas that highlight certain properties of the three cases. Lemma 1. Case 3 cannot occur. Proof. Assume that Case 3 occurs and let a denote the agent that would move i on indeﬁnitely without meeting another agent. Then, at the beginning of the ﬁrst iteration according to the special rule, the distance of agent a to any of i the other agents is more than k in at least one (of x- and y-) direction and a moves away from the agents according to the travel vector. After each of i the other agents makes a step, this distance is still at least k. Hence, agent a i cannot encounter one of the other agents during its next k steps, since in total it moves away from the other agents, according to the speciﬁcation of Case 3. The direction of the travel vector also ensures that the distance to the other agents is again increased to more than k (in at least one direction). Thus, the same arguments hold for the next iteration, and we obtain by induction that agent a will never encounter another agent after the occurrence of Case 3. It follows i that, if three agents suﬃce to explore the grid, then also a team of two agents and a separate single agent can explore the grid without any communication between the team and the single agent. From [16], we know that this is not possible since two agents can only explore a band of constant width. Following Lemma 1, we will assume in the following that Case 3 does not occur, i.e., each agent’s subschedule ends because it encounters another agent or because it repeats a pair state/cell. This allows us to group the possible S subschedules of an agent into two categories: We say that a subschedule i is of S j S type 1 if i ends because of the condition given in Case 1, and of type 2 if i j j ends because of the condition given in Case 2. 8 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: q

text: q

text: q

text: (a)

text: q

text: (b)

text: Figure

text: Figure

text: illustrates

text: Case

text: of

text: our

text: schedule.

text: In

text: this

text: case,

text: an

text: agent

text: is

text: scheduled

text: until

text: some

text: state

text: q

text: in

text: some

text: cell

text: c

text: occurs

text: for

text: the

text: second

text: time.

text: In

text: Figure

text: we

text: illustrate

text: Case

text: where

text: one

text: agent

text: alone,

text: walks

text: inﬁnitely

text: far

text: away

text: from

text: the

text: other

text: two

text: agents.

text: This

text: case

text: cannot

text: occur,

text: since

text: otherwise,

text: the

text: two

text: remaining

text: agents

text: would

text: have

text: to

text: explore

text: the

text: grid

text: without

text: the

text: third

text: agent.

text: ensures

text: that

text: there

text: is

text: such

text: a

text: (ﬁnite)

text: point

text: in

text: time

text: t.

text: Note

text: that

text: Case

text: can

text: only

text: occur

text: if

text: x

text: or

text: y

text: Moreover,

text: if

text: this

text: case

text: actually

text: occurs,

text: then

text: the

text: complete

text: subsequent

text: sched-

text: ule

text: is

text: adapted

text: according

text: to

text: the

text: following

text: special

text: rule

text: (overriding

text: all

text: of

text: the

text: above):

text: After

text: time

text: t,

text: the

text: two

text: agents

text: a

text: r

text: i

text: are

text: scheduled

text: for

text: one

text: time

text: r

text: step

text: each

text: (in

text: arbitrary

text: order),

text: then

text: agent

text: a

text: is

text: scheduled

text: for

text: k

text: time

text: steps,

text: i

text: i.e.,

text: exactly

text: one

text: travel

text: period,

text: and

text: then

text: we

text: iterate

text: this

text: new

text: scheduling.

text: Note

text: that

text: according

text: to

text: this

text: schedule,

text: the

text: number

text: of

text: time

text: steps

text: a

text: scheduled

text: agent

text: can

text: stay

text: put

text: in

text: a

text: cell

text: during

text: one

text: of

text: its

text: subschedules

text: is

text: upper

text: bounded

text: by

text: N.

text: We

text: now

text: collect

text: a

text: few

text: lemmas

text: that

text: highlight

text: certain

text: properties

text: of

text: the

text: three

text: cases.

text: Lemma

text: Case

text: cannot

text: occur.

text: Proof.

text: Assume

text: that

text: Case

text: occurs

text: and

text: let

text: a

text: denote

text: the

text: agent

text: that

text: would

text: move

text: i

text: on

text: indeﬁnitely

text: without

text: meeting

text: another

text: agent.

text: Then,

text: at

text: the

text: beginning

text: of

text: the

text: ﬁrst

text: iteration

text: according

text: to

text: the

text: special

text: rule,

text: the

text: distance

text: of

text: agent

text: a

text: to

text: any

text: of

text: i

text: the

text: other

text: agents

text: is

text: more

text: than

text: k

text: in

text: at

text: least

text: one

text: (of

text: x-

text: and

text: y-)

text: direction

text: and

text: a

text: moves

text: away

text: from

text: the

text: agents

text: according

text: to

text: the

text: travel

text: vector.

text: After

text: each

text: of

text: i

text: the

text: other

text: agents

text: makes

text: a

text: step,

text: this

text: distance

text: is

text: still

text: at

text: least

text: k.

text: Hence,

text: agent

text: a

text: i

text: cannot

text: encounter

text: one

text: of

text: the

text: other

text: agents

text: during

text: its

text: next

text: k

text: steps,

text: since

text: in

text: total

text: it

text: moves

text: away

text: from

text: the

text: other

text: agents,

text: according

text: to

text: the

text: speciﬁcation

text: of

text: Case

text: The

text: direction

text: of

text: the

text: travel

text: vector

text: also

text: ensures

text: that

text: the

text: distance

text: to

text: the

text: other

text: agents

text: is

text: again

text: increased

text: to

text: more

text: than

text: k

text: (in

text: at

text: least

text: one

text: direction).

text: Thus,

text: the

text: same

text: arguments

text: hold

text: for

text: the

text: next

text: iteration,

text: and

text: we

text: obtain

text: by

text: induction

text: that

text: agent

text: a

text: will

text: never

text: encounter

text: another

text: agent

text: after

text: the

text: occurrence

text: of

text: Case

text: It

text: follows

text: i

text: that,

text: if

text: three

text: agents

text: suﬃce

text: to

text: explore

text: the

text: grid,

text: then

text: also

text: a

text: team

text: of

text: two

text: agents

text: and

text: a

text: separate

text: single

text: agent

text: can

text: explore

text: the

text: grid

text: without

text: any

text: communication

text: between

text: the

text: team

text: and

text: the

text: single

text: agent.

text: From

text: we

text: know

text: that

text: this

text: is

text: not

text: possible

text: since

text: two

text: agents

text: can

text: only

text: explore

text: a

text: band

text: of

text: constant

text: width.

text: Following

text: Lemma

text: we

text: will

text: assume

text: in

text: the

text: following

text: that

text: Case

text: does

text: not

text: occur,

text: i.e.,

text: each

text: agent’s

text: subschedule

text: ends

text: because

text: it

text: encounters

text: another

text: agent

text: or

text: because

text: it

text: repeats

text: a

text: pair

text: state/cell.

text: This

text: allows

text: us

text: to

text: group

text: the

text: possible

text: S

text: subschedules

text: of

text: an

text: agent

text: into

text: two

text: categories:

text: We

text: say

text: that

text: a

text: subschedule

text: i

text: is

text: of

text: S

text: j

text: S

text: type

text: if

text: i

text: ends

text: because

text: of

text: the

text: condition

text: given

text: in

text: Case

text: and

text: of

text: type

text: if

text: i

text: j

text: j

text: ends

text: because

text: of

text: the

text: condition

text: given

text: in

text: Case

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: TORSION PAIRS OVER N-HEREDITARY RINGS 3 where the modules F are ﬁnitely generated and free (or projective) modules, for ≤ ≤ i FP every 0 i n. Denote by the class of all ﬁnitely n-presented modules. FP n FP Thus is the class of ﬁnitely generated modules, and is the class of ﬁnitely 0 FP 1 presented modules. For convenience, we let − be the whole class of R-modules. FP 1∞ Also we consider the class, ∞, of the ﬁnitely -presented modules, formed by modules that posses a resolution by ﬁnitely generated free (or projective) modules. FP Note that the class ∞ is not empty, since any ﬁnitely generated projective ∞ module is ﬁnitely -presented. We immediately observe the following descending chain of inclusions: FP ⊇ FP ⊇ · · · ⊇ FP ⊇ FP ⊇ · · · ⊇ FP ∞. (1.1) 0 1 n n+1 We include two examples of rings to show how the chain (1.1) behaves; for more details about these two examples we refer the reader to [BP17]. Example 1. Let k be a ﬁeld and R be the following polynomial ring: R := k[x , x , x , . . .]/(x x ) ≥ . 1 2 3 i j i,j 1 In this ring every ﬁnitely 2-presented module is ﬁnitely generated free. Also we can ∈ FP \FP ∈ FP \FP quickly check that R/(x ) and that (x ) . Thus we have 1 1 2 1 0 1 that the chain of inclusions in (1.1) collapses at 2: FP ⊃ FP ⊃ FP FP FP = = ∞. 0 1 2 n The next example shows that (1.1) may never collapse. Example 2. Let k be a ﬁeld and consider the following ring: R := k[. . . , x , x , x , y , y , y , . . .]/(x x , x y , y y ) ≥ 3 2 1 1 2 3 j+1 j 1 1 1 i i,j 1 ∈ FP \ FP ∈ FP \ FP ≥ Then (y ) , and (x ) for i 1. Hence in this case, the 1 0 1 i i i+1 chain in (1.1) is strict at every level. FP FP Several results about and ∞ are collected in [BP17]. We inlude here n the following results. ≥ FP Proposition 3. Let n 0. is closed under cokernels of monomorphisms, n extensions, and direct summands. FP The class ∞ has all the properties from the previous proposition and one more, as indicated in the following result. FP Theorem 4. ∞ is closed under kernels of epimorphisms. We say that a class of modules is resolving if it is closed under extensions, direct summands, kernels of epimorphisms in that class and contains the ﬁnitely generated FP projective modules. Indeed the class of ∞ is resolving. ≤ Remark 5. For any ﬁnitely generated module M, we have that Card(M) {ℵ } S max , Card(R) . Hence we can choose , a set of representatives of ﬁnitely 0 FP n FP generated modules in , such that every module in is isomorphic to a S n n module in . n In the next two sections, we will use the class of ﬁnitely n-presented modules to describe two types of rings.

text: TORSION

text: PAIRS

text: OVER

text: N-HEREDITARY

text: RINGS

text: where

text: the

text: modules

text: F

text: are

text: ﬁnitely

text: generated

text: and

text: free

text: (or

text: projective)

text: modules,

text: for

text: i

text: FP

text: every

text: i

text: n.

text: Denote

text: by

text: the

text: class

text: of

text: all

text: ﬁnitely

text: n-presented

text: modules.

text: FP

text: n

text: FP

text: Thus

text: is

text: the

text: class

text: of

text: ﬁnitely

text: generated

text: modules,

text: and

text: is

text: the

text: class

text: of

text: ﬁnitely

text: FP

text: presented

text: modules.

text: For

text: convenience,

text: we

text: let

text: be

text: the

text: whole

text: class

text: of

text: R-modules.

text: FP

text: 1∞

text: Also

text: we

text: consider

text: the

text: class,

text: of

text: the

text: ﬁnitely

text: -presented

text: modules,

text: formed

text: by

text: modules

text: that

text: posses

text: a

text: resolution

text: by

text: ﬁnitely

text: generated

text: free

text: (or

text: projective)

text: modules.

text: FP

text: Note

text: that

text: the

text: class

text: is

text: not

text: empty,

text: since

text: any

text: ﬁnitely

text: generated

text: projective

text: module

text: is

text: ﬁnitely

text: -presented.

text: We

text: immediately

text: observe

text: the

text: following

text: descending

text: chain

text: of

text: inclusions:

text: FP

text: FP

text: FP

text: FP

text: FP

text: n

text: We

text: include

text: two

text: examples

text: of

text: rings

text: to

text: show

text: how

text: the

text: chain

text: behaves;

text: for

text: more

text: details

text: about

text: these

text: two

text: examples

text: we

text: refer

text: the

text: reader

text: to

text: Example

text: Let

text: k

text: be

text: a

text: ﬁeld

text: and

text: R

text: be

text: the

text: following

text: polynomial

text: ring:

text: R

text: k[x

text: x

text: x

text: .]/(x

text: x

text: i

text: j

text: i,j

text: In

text: this

text: ring

text: every

text: ﬁnitely

text: module

text: is

text: ﬁnitely

text: generated

text: free.

text: Also

text: we

text: can

text: FP

text: \FP

text: FP

text: \FP

text: quickly

text: check

text: that

text: R/(x

text: and

text: that

text: (x

text: Thus

text: we

text: have

text: that

text: the

text: chain

text: of

text: inclusions

text: in

text: collapses

text: at

text: FP

text: FP

text: FP

text: FP

text: FP

text: n

text: The

text: next

text: example

text: shows

text: that

text: may

text: never

text: collapse.

text: Example

text: Let

text: k

text: be

text: a

text: ﬁeld

text: and

text: consider

text: the

text: following

text: ring:

text: R

text: k[.

text: x

text: x

text: x

text: y

text: y

text: y

text: .]/(x

text: x

text: x

text: y

text: y

text: y

text: j

text: i

text: i,j

text: FP

text: FP

text: FP

text: FP

text: Then

text: (y

text: and

text: (x

text: for

text: i

text: Hence

text: in

text: this

text: case,

text: the

text: i

text: i

text: chain

text: in

text: is

text: strict

text: at

text: every

text: level.

text: FP

text: FP

text: Several

text: results

text: about

text: and

text: are

text: collected

text: in

text: We

text: inlude

text: here

text: n

text: the

text: following

text: results.

text: FP

text: Proposition

text: Let

text: n

text: is

text: closed

text: under

text: cokernels

text: of

text: monomorphisms,

text: n

text: extensions,

text: and

text: direct

text: summands.

text: FP

text: The

text: class

text: has

text: all

text: the

text: properties

text: from

text: the

text: previous

text: proposition

text: and

text: one

text: more,

text: as

text: indicated

text: in

text: the

text: following

text: result.

text: FP

text: Theorem

text: is

text: closed

text: under

text: kernels

text: of

text: epimorphisms.

text: We

text: say

text: that

text: a

text: class

text: of

text: modules

text: is

text: resolving

text: if

text: it

text: is

text: closed

text: under

text: extensions,

text: direct

text: summands,

text: kernels

text: of

text: epimorphisms

text: in

text: that

text: class

text: and

text: contains

text: the

text: ﬁnitely

text: generated

text: FP

text: projective

text: modules.

text: Indeed

text: the

text: class

text: of

text: is

text: resolving.

text: Remark

text: For

text: any

text: ﬁnitely

text: generated

text: module

text: M,

text: we

text: have

text: that

text: Card(M)

text: {ℵ

text: S

text: max

text: Card(R)

text: Hence

text: we

text: can

text: choose

text: a

text: set

text: of

text: representatives

text: of

text: ﬁnitely

text: FP

text: n

text: FP

text: generated

text: modules

text: in

text: such

text: that

text: every

text: module

text: in

text: is

text: isomorphic

text: to

text: a

text: S

text: n

text: n

text: module

text: in

text: n

text: In

text: the

text: next

text: two

text: sections,

text: we

text: will

text: use

text: the

text: class

text: of

text: ﬁnitely

text: n-presented

text: modules

text: to

text: describe

text: two

text: types

text: of

text: rings.


text: 4 DANIEL BRAVO AND CARLOS E. PARRA 2. n-Hereditary rings and n-coherent rings As deﬁned in [CE99], recall that a ring is said to be left hereditary if every left ideal is a projective module. This is also equivalent to saying that every submodule of a projective left module is also a projective module, or that every quotient (ho- momorphic image) of an injective left module is injective. A bit more general are left semi-hereditary rings; that is, rings such that every ﬁnitely generated left ideal is projective. This is equivalent to saying that every ﬁnitely generated submodule of a projective left module is also a projective module, or that every quotient (ho- momorphic image) of a FP-injective left module is FP-injective [Meg70, Theorem 2]. From these observations we deﬁne the following: − Deﬁnition 6. A ring is said to be left n-hereditary if every ﬁnitely (n 1)-presented submodule of a ﬁnitely generated projective left module is also a projective module. This way a left 1-hereditary ring is the same as a left semi-hereditary ring, − and if we allow for ﬁnitely ( 1)-presented modules to be any module, then left 0-hereditary rings coincide with left hereditary. From now on, and unless otherwise noted, the term n-hereditary ring will mean left n-hereditary ring. A characterization of n-hereditary rings can be given in terms of the class of ﬁnitely n-presented modules, pd(M), the projective dimension of an R-module M, wd(M), the weak dimension of the R-module M. ≥ Lemma 7. Let n 2. The following statements are equivalent. (1) R is a n-hereditary ring. ≤ ∈ FP (2) pd(M) 1 for all M . ≤ ∈ FPn (3) wd(M) 1 for all M . n Furthermore if n = 1, then we have the following statement: R is 1-hereditary if ≤ ∈ FP and only if pd(M) 1 for all M . 1 ⇒ ∈ FP Proof. (1) (2): Suppose R is an n-herditary ring and let M . Consider n the following short exact sequence: → → → → 0 ΩM Rk M 0. ∈ FP Since ΩM − and Rk is a ﬁnitely generated and projective module, then n 1 ≤ ΩM is also projective. Thus pd(M) 1. ⇒ ≤ ∈ (2) (3): This is clear, since wd(M) pd(M) for any M R-Mod. ⇒ ∈ FP (3) (1): Suppose that N − is a submodule of a ﬁnitely generated ∈ FPn 1 ≤ projective module P. Then P/N , and so wd(P/N) 1; hence N is ﬂat. ≥ FP n But n 2, so N is at least in . Thus, [EJ11, Proposition 3.2.12] gives that N 1 is projective, showing that R is n-hereditary. Finally, for the last statement, observe that if I is a ﬁnitely generated ideal, then ∈ FP R/I and so I is projective; thus R is semi-hereditary, or 1-hereditary. For 1 ⇒ (cid:3) the converse, note that the proof of (1) (2) also applies. Using this last characte(cid:76)rization, we give an example of a (commutative) 2- hereditary ring, that is not 1-hereditary. Z ⊕ Z Z Example 8. Let R = ≥ /2 with addition deﬁned component wise, and i 1 multiplication given by(cid:76) · (m, a) (n, b) = (mn, mb + na + ab) ∈ Z ∈ Z Z · where m, n , a, b ≥ /2 and m a = (ma , ma , ma , . . .). i 1 1 2 3

text: DANIEL

text: BRAVO

text: AND

text: CARLOS

text: E.

text: PARRA

label: section

text: n-Hereditary

text: rings

text: and

text: n-coherent

text: rings

text: As

text: deﬁned

text: in

text: recall

text: that

text: a

text: ring

text: is

text: said

text: to

text: be

text: left

text: hereditary

text: if

text: every

text: left

text: ideal

text: is

text: a

text: projective

text: module.

text: This

text: is

text: also

text: equivalent

text: to

text: saying

text: that

text: every

text: submodule

text: of

text: a

text: projective

text: left

text: module

text: is

text: also

text: a

text: projective

text: module,

text: or

text: that

text: every

text: quotient

text: (ho-

text: momorphic

text: image)

text: of

text: an

text: injective

text: left

text: module

text: is

text: injective.

text: A

text: bit

text: more

text: general

text: are

text: left

text: semi-hereditary

text: rings;

text: that

text: is,

text: rings

text: such

text: that

text: every

text: ﬁnitely

text: generated

text: left

text: ideal

text: is

text: projective.

text: This

text: is

text: equivalent

text: to

text: saying

text: that

text: every

text: ﬁnitely

text: generated

text: submodule

text: of

text: a

text: projective

text: left

text: module

text: is

text: also

text: a

text: projective

text: module,

text: or

text: that

text: every

text: quotient

text: (ho-

text: momorphic

text: image)

text: of

text: a

text: FP-injective

text: left

text: module

text: is

text: FP-injective

text: Theorem

text: From

text: these

text: observations

text: we

text: deﬁne

text: the

text: following:

text: Deﬁnition

text: A

text: ring

text: is

text: said

text: to

text: be

text: left

text: n-hereditary

text: if

text: every

text: ﬁnitely

text: (n

text: submodule

text: of

text: a

text: ﬁnitely

text: generated

text: projective

text: left

text: module

text: is

text: also

text: a

text: projective

text: module.

text: This

text: way

text: a

text: left

text: ring

text: is

text: the

text: same

text: as

text: a

text: left

text: semi-hereditary

text: ring,

text: and

text: if

text: we

text: allow

text: for

text: ﬁnitely

text: modules

text: to

text: be

text: any

text: module,

text: then

text: left

text: rings

text: coincide

text: with

text: left

text: hereditary.

text: From

text: now

text: on,

text: and

text: unless

text: otherwise

text: noted,

text: the

text: term

text: n-hereditary

text: ring

text: will

text: mean

text: left

text: n-hereditary

text: ring.

text: A

text: characterization

text: of

text: n-hereditary

text: rings

text: can

text: be

text: given

text: in

text: terms

text: of

text: the

text: class

text: of

text: ﬁnitely

text: n-presented

text: modules,

text: pd(M),

text: the

text: projective

text: dimension

text: of

text: an

text: R-module

text: M,

text: wd(M),

text: the

text: weak

text: dimension

text: of

text: the

text: R-module

text: M.

text: Lemma

text: Let

text: n

text: The

text: following

text: statements

text: are

text: equivalent.

text: R

text: is

text: a

text: n-hereditary

text: ring.

text: FP

text: pd(M)

text: for

text: all

text: M

text: FPn

text: wd(M)

text: for

text: all

text: M

text: n

text: Furthermore

text: if

text: n

text: then

text: we

text: have

text: the

text: following

text: statement:

text: R

text: is

text: if

text: FP

text: and

text: only

text: if

text: pd(M)

text: for

text: all

text: M

text: FP

text: Proof.

text: Suppose

text: R

text: is

text: an

text: n-herditary

text: ring

text: and

text: let

text: M

text: Consider

text: n

text: the

text: following

text: short

text: exact

text: sequence:

text: ΩM

text: Rk

text: M

text: FP

text: Since

text: ΩM

text: and

text: Rk

text: is

text: a

text: ﬁnitely

text: generated

text: and

text: projective

text: module,

text: then

text: n

text: ΩM

text: is

text: also

text: projective.

text: Thus

text: pd(M)

text: This

text: is

text: clear,

text: since

text: wd(M)

text: pd(M)

text: for

text: any

text: M

text: R-Mod.

text: FP

text: Suppose

text: that

text: N

text: is

text: a

text: submodule

text: of

text: a

text: ﬁnitely

text: generated

text: FPn

text: projective

text: module

text: P.

text: Then

text: P/N

text: and

text: so

text: wd(P/N)

text: hence

text: N

text: is

text: ﬂat.

text: FP

text: n

text: But

text: n

text: so

text: N

text: is

text: at

text: least

text: in

text: Thus,

text: Proposition

text: gives

text: that

text: N

text: is

text: projective,

text: showing

text: that

text: R

text: is

text: n-hereditary.

text: Finally,

text: for

text: the

text: last

text: statement,

text: observe

text: that

text: if

text: I

text: is

text: a

text: ﬁnitely

text: generated

text: ideal,

text: then

text: FP

text: R/I

text: and

text: so

text: I

text: is

text: projective;

text: thus

text: R

text: is

text: semi-hereditary,

text: or

text: For

text: the

text: converse,

text: note

text: that

text: the

text: proof

text: of

text: also

text: applies.

text: Using

text: this

text: last

text: we

text: give

text: an

text: example

text: of

text: a

text: (commutative)

text: hereditary

text: ring,

text: that

text: is

text: not

text: Z

text: Z

text: Z

text: Example

text: Let

text: R

text: with

text: addition

text: deﬁned

text: component

text: wise,

text: and

text: i

text: multiplication

text: given

text: (m,

text: a)

text: (n,

text: b)

text: (mn,

text: mb

text: ab)

text: Z

text: Z

text: Z

text: where

text: m,

text: n

text: a,

text: b

text: and

text: m

text: a

text: (ma

text: ma

text: ma

text: i


text: TORSION PAIRS OVER N-HEREDITARY RINGS 5 In the Appendix section we show that this ring is not semi-hereditary, or 1- hereditary. From [Cou03, Theorem 2.1] or [Vas76, Example 1.3(b)], we have that ≤ gl.wd(R) 1; here gl.wd(R) corresponds to the weak global dimension of the ring ≤ ∈ FP ≥ R. So in particular, wd(M) 1, for any M and any n 2. Thus by n Lemma 7 we have that R is 2-hereditary. ≤ Another immediate observation is that any ring such that gl.wd(R) 1 is 2- hereditary. The same proof as in the previous example works, and indeed we note ≥ that it is also n-hereditary for all n 2, but this is always the case as we observe next. As a consequence of Deﬁnition 6 and the chain (1.1), if R is n-hereditary, then ≥ R is also k-hereditary for all k n. Hence, if n-Her denotes the collection of all n-hereditary rings, then we get the following chain: ⊂ ⊂ ⊂ · · · ⊂ ⊂ · · · ⊂ ∞ 0-Her 1-Her 2-Her n-Her -Her, (2.1) ∞ FP where -Her is the corresponding deﬁnition using the class ∞. We have given examples of rings that are 0-hereditary, 1-hereditary and 2- hereditary. Next, we give an example which shows that there are rings that are not ∞ -Her. But to do that we need the following result. ≥ ∈ FP Corollary 9. Let n 0. If R is n-hereditary ring then every ideal I − is n 1 projective. Proof. The cases n = 0 and n = 1 are known and can be found in [CE99] and FP [Meg70] respectively; recall that we are allowing − = R-Mod. 1 ∈ FP Now let n > 1 and suppose R is n-hereditary. Then for any ideal I − , ∈ FP ≤ n 1 we have that R/I . Applying Lemma 7 gives us that pd(R/I) 1, which n implies that I is projective. (cid:3) Z Z Z Z FP Example 10. Let R = /4 . Then the ideal I = 2 /4 of R is in ∞ as the · · · → Z Z −·→2 Z Z −·→2 →− resolution /4 /4 I 0 shows. However, the ideal I is not ≥ projective, and thus by Corollary 9, we see that R is not n-Her for any n 0. ∞ We still would like to ﬁnd an explicit example of a ring that is -Her, but not ≥ n-Her for any n 0. Corollary 9 can be thought as a ﬁrst step in a characterization of n-hereditary rings in terms of its ideals. Since as noted in the begining of this section the reciprocal of this corollary works for n = 0, 1, thus it is natural to ask the following. Question 11. Is the reciprocal of Corollary 9 true? In other words, if every ideal ∈ FP I − is projective, then is it true that R is n-hereditary? n 1 Also related to the idea of ﬁnitely n-presented modules, is the notion of n- coherent rings, which generalizes that of coherent rings. Recall that a ring R is said to be left coherent if every ﬁnitely generated left ideal of R also is ﬁnitely presented. Another equivalent deﬁnition for coherent ring is as follows: R is a left coherent FP FP ring if, and only if, every module in is also in . 1 2 FP ⊆ FP Deﬁnition 12. A ring R is left n-coherent if . n n+1

text: TORSION

text: PAIRS

text: OVER

text: N-HEREDITARY

text: RINGS

text: In

text: the

text: Appendix

text: section

text: we

text: show

text: that

text: this

text: ring

text: is

text: not

text: semi-hereditary,

text: or

text: hereditary.

text: From

text: Theorem

text: or

text: Example

text: we

text: have

text: that

text: gl.wd(R)

text: here

text: gl.wd(R)

text: corresponds

text: to

text: the

text: weak

text: global

text: dimension

text: of

text: the

text: ring

text: FP

text: R.

text: So

text: in

text: particular,

text: wd(M)

text: for

text: any

text: M

text: and

text: any

text: n

text: Thus

text: by

text: n

text: Lemma

text: we

text: have

text: that

text: R

text: is

text: Another

text: immediate

text: observation

text: is

text: that

text: any

text: ring

text: such

text: that

text: gl.wd(R)

text: is

text: hereditary.

text: The

text: same

text: proof

text: as

text: in

text: the

text: previous

text: example

text: works,

text: and

text: indeed

text: we

text: note

text: that

text: it

text: is

text: also

text: n-hereditary

text: for

text: all

text: n

text: but

text: this

text: is

text: always

text: the

text: case

text: as

text: we

text: observe

text: next.

text: As

text: a

text: consequence

text: of

text: Deﬁnition

text: and

text: the

text: chain

text: if

text: R

text: is

text: n-hereditary,

text: then

text: R

text: is

text: also

text: k-hereditary

text: for

text: all

text: k

text: n.

text: Hence,

text: if

text: n-Her

text: denotes

text: the

text: collection

text: of

text: all

text: n-hereditary

text: rings,

text: then

text: we

text: get

text: the

text: following

text: chain:

text: n-Her

text: -Her,

text: FP

text: where

text: -Her

text: is

text: the

text: corresponding

text: deﬁnition

text: using

text: the

text: class

text: We

text: have

text: given

text: examples

text: of

text: rings

text: that

text: are

text: and

text: hereditary.

text: Next,

text: we

text: give

text: an

text: example

text: which

text: shows

text: that

text: there

text: are

text: rings

text: that

text: are

text: not

text: -Her.

text: But

text: to

text: do

text: that

text: we

text: need

text: the

text: following

text: result.

text: FP

text: Corollary

text: Let

text: n

text: If

text: R

text: is

text: n-hereditary

text: ring

text: then

text: every

text: ideal

text: I

text: is

text: n

text: projective.

text: Proof.

text: The

text: cases

text: n

text: and

text: n

text: are

text: known

text: and

text: can

text: be

text: found

text: in

text: and

text: FP

text: respectively;

text: recall

text: that

text: we

text: are

text: allowing

text: R-Mod.

text: FP

text: Now

text: let

text: n

text: and

text: suppose

text: R

text: is

text: n-hereditary.

text: Then

text: for

text: any

text: ideal

text: I

text: FP

text: n

text: we

text: have

text: that

text: R/I

text: Applying

text: Lemma

text: gives

text: us

text: that

text: pd(R/I)

text: which

text: n

text: implies

text: that

text: I

text: is

text: projective.

text: Z

text: Z

text: Z

text: Z

text: FP

text: Example

text: Let

text: R

text: Then

text: the

text: ideal

text: I

text: of

text: R

text: is

text: in

text: as

text: the

text: Z

text: Z

text: −·→2

text: Z

text: Z

text: −·→2

text: resolution

text: I

text: shows.

text: However,

text: the

text: ideal

text: I

text: is

text: not

text: projective,

text: and

text: thus

text: by

text: Corollary

text: we

text: see

text: that

text: R

text: is

text: not

text: n-Her

text: for

text: any

text: n

text: We

text: still

text: would

text: like

text: to

text: ﬁnd

text: an

text: explicit

text: example

text: of

text: a

text: ring

text: that

text: is

text: -Her,

text: but

text: not

text: n-Her

text: for

text: any

text: n

text: Corollary

text: can

text: be

text: thought

text: as

text: a

text: ﬁrst

text: step

text: in

text: a

text: characterization

text: of

text: n-hereditary

text: rings

text: in

text: terms

text: of

text: its

text: ideals.

text: Since

text: as

text: noted

text: in

text: the

text: begining

text: of

text: this

text: section

text: the

text: reciprocal

text: of

text: this

text: corollary

text: works

text: for

text: n

text: thus

text: it

text: is

text: natural

text: to

text: ask

text: the

text: following.

text: Question

text: Is

text: the

text: reciprocal

text: of

text: Corollary

text: true?

text: In

text: other

text: words,

text: if

text: every

text: ideal

text: FP

text: I

text: is

text: projective,

text: then

text: is

text: it

text: true

text: that

text: R

text: is

text: n-hereditary?

text: n

text: Also

text: related

text: to

text: the

text: idea

text: of

text: ﬁnitely

text: n-presented

text: modules,

text: is

text: the

text: notion

text: of

text: n-

text: coherent

text: rings,

text: which

text: generalizes

text: that

text: of

text: coherent

text: rings.

text: Recall

text: that

text: a

text: ring

text: R

text: is

text: said

text: to

text: be

text: left

text: coherent

text: if

text: every

text: ﬁnitely

text: generated

text: left

text: ideal

text: of

text: R

text: also

text: is

text: ﬁnitely

text: presented.

text: Another

text: equivalent

text: deﬁnition

text: for

text: coherent

text: ring

text: is

text: as

text: follows:

text: R

text: is

text: a

text: left

text: coherent

text: FP

text: FP

text: ring

text: if,

text: and

text: only

text: if,

text: every

text: module

text: in

text: is

text: also

text: in

text: FP

text: FP

text: Deﬁnition

text: A

text: ring

text: R

text: is

text: left

text: n-coherent

text: if

text: n


text: 8 DANIEL BRAVO AND CARLOS E. PARRA −→ h P M such that hg = f. (cid:48) g P P f h M ∈ FP Proof. Suppose that M has this lifting property. Let F , and consider → (cid:48) → → → n the short exact sequence 0 P P F 0, with P ﬁnitely generated free (cid:48) ∈ FP − and P − . Then applying Hom ( , M) to this short exact sequence gives n 1 R→ (cid:48) that Ext1(F, M) = 0, since Hom(P, M) Hom(P , M) is an epimorphism. Hence ∈ FP M -Inj. n ∈ FP Conversely the argument works similarlly, since for M -Inj we have that (cid:48) (cid:48) ∈ FP n → (cid:48) Ext1(P/P , M) = 0, given that P/P , and so Hom(P, M) Hom(P , M) n (cid:3) is an epimorphism. The following results are motivated from the work of H. Cartan and S. Eilenberg [CE99] and C. Megibben [Meg70]. Namely, we tackle the question regarding when FP FP -Inj is closed under quotients or when -Flat is closed under subobjects. n n FP For this matter we begin by focusing on n-hereditary rings and the class of -Inj. n ≥ Proposition 22. Let n 0. R is n-hereditary if and only if quotients of any FP -injective module is again FP -injective. n n Proof. We will consider the following diagram (cid:48) g P P (3.3) f (cid:48) M M h (cid:48) ∈ FP ∈ FP with P − , P ﬁnitely generated projective, and M -Inj. Suppose n 1 (cid:48) (cid:48) →−n that R is n-hereditary, then P is projective and so there is s : P M such that ∈ FP →− f = hs. Since M -Inj, then by Proposition 21, there is a map t : P M, n such that s = tg, as shown in the following diagram: (cid:48) g P P s t (cid:48) M M h → (cid:48) Consider the map ht : P M , and note that (ht)g = h(tg) = hs = f. Thus (cid:48) ∈ FP M -Inj by the same proposition. n Conversely, suppose that we have the same diagram (3.3) with M an injective (cid:48) ∈ FP module, and so M -Inj (since injective modules are FP -injective). Then n → (cid:48) n by the same proposition, we have a map s : P M , such that sg = f. Since P → is projective, then there is a map t : P M, such that ht = s, as shown in the following diagram: (cid:48) g P P s t (cid:48) M M h ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: DANIEL

text: BRAVO

text: AND

text: CARLOS

text: E.

text: PARRA

text: h

text: P

text: M

text: such

text: that

text: hg

text: f.

text: g

text: P

text: P

text: f

text: h

text: M

text: FP

text: Proof.

text: Suppose

text: that

text: M

text: has

text: this

text: lifting

text: property.

text: Let

text: F

text: and

text: consider

text: n

text: the

text: short

text: exact

text: sequence

text: P

text: P

text: F

text: with

text: P

text: ﬁnitely

text: generated

text: free

text: FP

text: and

text: P

text: Then

text: applying

text: Hom

text: M)

text: to

text: this

text: short

text: exact

text: sequence

text: gives

text: n

text: R→

text: that

text: M)

text: since

text: Hom(P,

text: M)

text: Hom(P

text: M)

text: is

text: an

text: epimorphism.

text: Hence

text: FP

text: M

text: -Inj.

text: n

text: FP

text: Conversely

text: the

text: argument

text: works

text: similarlly,

text: since

text: for

text: M

text: -Inj

text: we

text: have

text: that

text: FP

text: n

text: M)

text: given

text: that

text: P/P

text: and

text: so

text: Hom(P,

text: M)

text: Hom(P

text: M)

text: n

text: is

text: an

text: epimorphism.

text: The

text: following

text: results

text: are

text: motivated

text: from

text: the

text: work

text: of

text: H.

text: Cartan

text: and

text: S.

text: Eilenberg

text: and

text: C.

text: Megibben

text: Namely,

text: we

text: tackle

text: the

text: question

text: regarding

text: when

text: FP

text: FP

text: -Inj

text: is

text: closed

text: under

text: quotients

text: or

text: when

text: -Flat

text: is

text: closed

text: under

text: subobjects.

text: n

text: n

text: FP

text: For

text: this

text: matter

text: we

text: begin

text: by

text: focusing

text: on

text: n-hereditary

text: rings

text: and

text: the

text: class

text: of

text: -Inj.

text: n

text: Proposition

text: Let

text: n

text: R

text: is

text: n-hereditary

text: if

text: and

text: only

text: if

text: quotients

text: of

text: any

text: FP

text: -injective

text: module

text: is

text: again

text: FP

text: -injective.

text: n

text: n

text: Proof.

text: We

text: will

text: consider

text: the

text: following

text: diagram

text: g

text: P

text: P

text: f

text: M

text: M

text: h

text: FP

text: FP

text: with

text: P

text: P

text: ﬁnitely

text: generated

text: projective,

text: and

text: M

text: -Inj.

text: Suppose

text: n

text: →−n

text: that

text: R

text: is

text: n-hereditary,

text: then

text: P

text: is

text: projective

text: and

text: so

text: there

text: is

text: s

text: P

text: M

text: such

text: that

text: FP

text: f

text: hs.

text: Since

text: M

text: -Inj,

text: then

text: by

text: Proposition

text: there

text: is

text: a

text: map

text: t

text: P

text: M,

text: n

text: such

text: that

text: s

text: tg,

text: as

text: shown

text: in

text: the

text: following

text: diagram:

text: g

text: P

text: P

text: s

text: t

text: M

text: M

text: h

text: Consider

text: the

text: map

text: ht

text: P

text: M

text: and

text: note

text: that

text: (ht)g

text: h(tg)

text: hs

text: f.

text: Thus

text: FP

text: M

text: -Inj

text: by

text: the

text: same

text: proposition.

text: n

text: Conversely,

text: suppose

text: that

text: we

text: have

text: the

text: same

text: diagram

text: with

text: M

text: an

text: injective

text: FP

text: module,

text: and

text: so

text: M

text: -Inj

text: (since

text: injective

text: modules

text: are

text: FP

text: -injective).

text: Then

text: n

text: n

text: by

text: the

text: same

text: proposition,

text: we

text: have

text: a

text: map

text: s

text: P

text: M

text: such

text: that

text: sg

text: f.

text: Since

text: P

text: is

text: projective,

text: then

text: there

text: is

text: a

text: map

text: t

text: P

text: M,

text: such

text: that

text: ht

text: s,

text: as

text: shown

text: in

text: the

text: following

text: diagram:

text: g

text: P

text: P

text: s

text: t

text: M

text: M

text: h

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 1 In a chiral superconductor there is no energy difference between the two different chiralities set by the sign between the two order parameter components. These are simply the two different but equivalent choices for the superconducting order parameter when forming the intrinsically complex order parameter. This energy degeneracy between different chiral states naturally allows for domain wall formation inside the superconductor, between domains with different chiralities. Domain walls thus play an important role for the properties of chiral superconductors. In fact, for the p + ip -wave state in Sr RuO domain walls x y 2 4 have already been rather extensively investigated.22–24 For example, domain wall formation naturally limits the measurable edge currents carried by the edge states generated by the chiral topology.25–27 Chiral states have also gained increasing attention in spin-singlet superconductors. Notably, there exists vastly more known spin-singlet superconductors, ranging from conventional electron-phonon s-wave superconductors to strongly-correlated su- perconductors with d − -wave symmetry with the cuprates as the most prominent example.28 In fact, at surfaces of cuprate x2 y2 superconductors a subdominant id component has been proposed to be present in order to explain experimental results, such as xy a fully gapped state in cuprate nano-islands,29,30 split zero-energy conductance peaks in tunneling experiments,9,10 and thermal conductivity measurements.11 Even more generically, for d-wave superconductors with an underlying three- or six-fold lattice symmetry, the two different d-wave symmetries, d − and d , are necessarily degenerate. This very generically leads to a x2 y2 xy d − + id -wave chiral superconducting order parameter in such materials.6,14,15 x2 y2 xy Multiple different materials have already been proposed to be intrinsic d − + id superconductors due to their six-fold x2 y2 xy symmetric honeycomb lattice structure.6 Graphene, heavily doped to the van Hove singularity (VHS), is one example, where multiple (functional) renormalization group (f)RG calculations have found a d − + id -wave state due to electron-driven x2 y2 xy superconductivity.15–17 The superconducting pnictide SrAsPt with T = 2.4 K31 is also composed of honeycomb layers. Here c recent muon spin-rotation (µSR) experiments32 have revealed time-reversal symmetry breaking, which is in agreement with fRG calculations ﬁnding a chiral d-wave state.33 Also In Cu VO 34–38 and several different irridates,39,40 all with an effective 3 2 9 honeycomb structure, have been proposed to host a d − +id -wave superconducting states upon doping the magnetic ground x2 y2 xy state. Despite the growing interest and evidence for spin-singlet d − + id -wave superconductivity, relatively little is known ± x2 y2 xy ± about the properties of this state. The d − id state has a Chern6,41, or winding, number C = 2, which automatically x2 y2 xy gives rise to two topologically protected and chiral states at subgap energies at each edge.6,8 Recently, a more careful study of the edge states of a d − + id -wave superconductor on the honeycomb lattice has shown that the d component is actually x2 y2 xy xy heavily suppressed on all types of edges due to pair breaking effects.42 Despite this pair breaking, edge states were still found and also well localized to the edges. For a domain wall between the two different chiralities of the chiral d-wave state, the bulk-edge correspondence3,4,8,43 likewise dictates a total of four subgap states at the domain wall, since the Chern number changes by four across the wall.6,8 Very recent work has also calculated the total domain wall subgap spectrum semiclassically, conﬁrming the existence of domain wall states.44 However, beyond this, very little is known about either the explicit domain wall structure or the detailed properties of the subgap domain wall states. For example, the same mismatch between the honeycomb lattice and the d-wave symmetry giving rise to the chiral d-wave state in the ﬁrst place, also allows for multiple possible crystal orientations for domain walls in honeycomb superconductors, which might have very different properties. In this work we provide a fully self-consistent study of the superconducting state at generic domain walls in chiral d-wave superconductors with a honeycomb lattice structure. More speciﬁcally, we study domain walls formed along all different zigzag (ZZ) and armchair (AC) directions of the honeycomb lattice and also allow for a ﬁnite global phase shift across the domain wall, in addition to the change of chirality. We ﬁnd that the domain wall energy density depends not only on edge direction but also strongly on the global phase shift and the doping level. For domain walls along the AC direction, the lowest energy is found for x-direction domain walls, with no additional global phase shift. This is also the overall most stable domain wall conﬁguration for doping levels below the VHS. For the ZZ direction, the lowest domain wall energy instead occurs at a ﬁnite phase shift that changes with doping. Beyond the VHS, where ZZ domain walls have the overall lowest energy, the phase shift is around, but not exactly equal to, 2π/3. We also ﬁnd a ﬁnite suppression of superconductivity in the vicinity of the domain wall. We show that domain walls with a narrower suppression proﬁle are generally more energetically favorable. But notably, we ﬁnd that non-self-consistent results with a sharp order parameter proﬁle at the domain wall often predict the wrong lowest energy domain wall conﬁgurations. We also establish that the recovery length for superconductivity away from the domain wall is inversely related to the order parameter strength in the bulk and not dependent on domain wall orientation. We also study the induced subgap domain wall states. There are always four subgap domain wall states but their dispersion vary signiﬁcantly with domain wall orientation and global phase shift. These results are directly applicable to the d-wave superconducting state in heavily doped graphene, but also to other chiral d-wave honeycomb superconductors. The rest of the article is organized as follows: In Section II we introduce our model and discuss the bulk d-wave state. In Section IIIA we analyze all possible domain walls and establish the most energetically favorable conﬁgurations. Then in Section IIIB we determine the properties of the most favorable domain walls, focusing both on the domain wall subgap states and the order parameter at the domain wall. In Section IIIC we establish the generality of the superconducting recovery length. Finally, in Section IV we conclude our work.

text: In

text: a

text: chiral

text: superconductor

text: there

text: is

text: no

text: energy

text: difference

text: between

text: the

text: two

text: different

text: chiralities

text: set

text: by

text: the

text: sign

text: between

text: the

text: two

text: order

text: parameter

text: components.

text: These

text: are

text: simply

text: the

text: two

text: different

text: but

text: equivalent

text: choices

text: for

text: the

text: superconducting

text: order

text: parameter

text: when

text: forming

text: the

text: intrinsically

text: complex

text: order

text: parameter.

text: This

text: energy

text: degeneracy

text: between

text: different

text: chiral

text: states

text: naturally

text: allows

text: for

text: domain

text: wall

text: formation

text: inside

text: the

text: superconductor,

text: between

text: domains

text: with

text: different

text: chiralities.

text: Domain

text: walls

text: thus

text: play

text: an

text: important

text: role

text: for

text: the

text: properties

text: of

text: chiral

text: superconductors.

text: In

text: fact,

text: for

text: the

text: p

text: ip

text: -wave

text: state

text: in

text: Sr

text: RuO

text: domain

text: walls

text: x

text: y

text: have

text: already

text: been

text: rather

text: extensively

text: For

text: example,

text: domain

text: wall

text: formation

text: naturally

text: limits

text: the

text: measurable

text: edge

text: currents

text: carried

text: by

text: the

text: edge

text: states

text: generated

text: by

text: the

text: chiral

text: Chiral

text: states

text: have

text: also

text: gained

text: increasing

text: attention

text: in

text: spin-singlet

text: superconductors.

text: Notably,

text: there

text: exists

text: vastly

text: more

text: known

text: spin-singlet

text: superconductors,

text: ranging

text: from

text: conventional

text: electron-phonon

text: s-wave

text: superconductors

text: to

text: strongly-correlated

text: su-

text: perconductors

text: with

text: d

text: -wave

text: symmetry

text: with

text: the

text: cuprates

text: as

text: the

text: most

text: prominent

text: In

text: fact,

text: at

text: surfaces

text: of

text: cuprate

text: superconductors

text: a

text: subdominant

text: id

text: component

text: has

text: been

text: proposed

text: to

text: be

text: present

text: in

text: order

text: to

text: explain

text: experimental

text: results,

text: such

text: as

text: xy

text: a

text: fully

text: gapped

text: state

text: in

text: cuprate

text: split

text: zero-energy

text: conductance

text: peaks

text: in

text: tunneling

text: and

text: thermal

text: conductivity

text: Even

text: more

text: generically,

text: for

text: d-wave

text: superconductors

text: with

text: an

text: underlying

text: three-

text: or

text: six-fold

text: lattice

text: symmetry,

text: the

text: two

text: different

text: d-wave

text: symmetries,

text: d

text: and

text: d

text: are

text: necessarily

text: degenerate.

text: This

text: very

text: generically

text: leads

text: to

text: a

text: xy

text: d

text: id

text: -wave

text: chiral

text: superconducting

text: order

text: parameter

text: in

text: such

text: xy

text: Multiple

text: different

text: materials

text: have

text: already

text: been

text: proposed

text: to

text: be

text: intrinsic

text: d

text: id

text: superconductors

text: due

text: to

text: their

text: six-fold

text: xy

text: symmetric

text: honeycomb

text: lattice

text: Graphene,

text: heavily

text: doped

text: to

text: the

text: van

text: Hove

text: singularity

text: (VHS),

text: is

text: one

text: example,

text: where

text: multiple

text: (functional)

text: renormalization

text: group

text: (f)RG

text: calculations

text: have

text: found

text: a

text: d

text: id

text: -wave

text: state

text: due

text: to

text: electron-driven

text: xy

text: The

text: superconducting

text: pnictide

text: SrAsPt

text: with

text: T

text: is

text: also

text: composed

text: of

text: honeycomb

text: layers.

text: Here

text: c

text: recent

text: muon

text: spin-rotation

text: (µSR)

text: have

text: revealed

text: time-reversal

text: symmetry

text: breaking,

text: which

text: is

text: in

text: agreement

text: with

text: fRG

text: calculations

text: ﬁnding

text: a

text: chiral

text: d-wave

text: Also

text: In

text: Cu

text: VO

text: and

text: several

text: different

text: all

text: with

text: an

text: effective

text: honeycomb

text: structure,

text: have

text: been

text: proposed

text: to

text: host

text: a

text: d

text: +id

text: -wave

text: superconducting

text: states

text: upon

text: doping

text: the

text: magnetic

text: ground

text: xy

text: state.

text: Despite

text: the

text: growing

text: interest

text: and

text: evidence

text: for

text: spin-singlet

text: d

text: id

text: -wave

text: superconductivity,

text: relatively

text: little

text: is

text: known

text: xy

text: about

text: the

text: properties

text: of

text: this

text: state.

text: The

text: d

text: id

text: state

text: has

text: a

text: or

text: winding,

text: number

text: C

text: which

text: automatically

text: xy

text: gives

text: rise

text: to

text: two

text: topologically

text: protected

text: and

text: chiral

text: states

text: at

text: subgap

text: energies

text: at

text: each

text: Recently,

text: a

text: more

text: careful

text: study

text: of

text: the

text: edge

text: states

text: of

text: a

text: d

text: id

text: -wave

text: superconductor

text: on

text: the

text: honeycomb

text: lattice

text: has

text: shown

text: that

text: the

text: d

text: component

text: is

text: actually

text: xy

text: xy

text: heavily

text: suppressed

text: on

text: all

text: types

text: of

text: edges

text: due

text: to

text: pair

text: breaking

text: Despite

text: this

text: pair

text: breaking,

text: edge

text: states

text: were

text: still

text: found

text: and

text: also

text: well

text: localized

text: to

text: the

text: edges.

text: For

text: a

text: domain

text: wall

text: between

text: the

text: two

text: different

text: chiralities

text: of

text: the

text: chiral

text: d-wave

text: state,

text: the

text: bulk-edge

text: likewise

text: dictates

text: a

text: total

text: of

text: four

text: subgap

text: states

text: at

text: the

text: domain

text: wall,

text: since

text: the

text: Chern

text: number

text: changes

text: by

text: four

text: across

text: the

text: Very

text: recent

text: work

text: has

text: also

text: calculated

text: the

text: total

text: domain

text: wall

text: subgap

text: spectrum

text: semiclassically,

text: conﬁrming

text: the

text: existence

text: of

text: domain

text: wall

text: However,

text: beyond

text: this,

text: very

text: little

text: is

text: known

text: about

text: either

text: the

text: explicit

text: domain

text: wall

text: structure

text: or

text: the

text: detailed

text: properties

text: of

text: the

text: subgap

text: domain

text: wall

text: states.

text: For

text: example,

text: the

text: same

text: mismatch

text: between

text: the

text: honeycomb

text: lattice

text: and

text: the

text: d-wave

text: symmetry

text: giving

text: rise

text: to

text: the

text: chiral

text: d-wave

text: state

text: in

text: the

text: ﬁrst

text: place,

text: also

text: allows

text: for

text: multiple

text: possible

text: crystal

text: orientations

text: for

text: domain

text: walls

text: in

text: honeycomb

text: superconductors,

text: which

text: might

text: have

text: very

text: different

text: properties.

text: In

text: this

text: work

text: we

text: provide

text: a

text: fully

text: self-consistent

text: study

text: of

text: the

text: superconducting

text: state

text: at

text: generic

text: domain

text: walls

text: in

text: chiral

text: d-wave

text: superconductors

text: with

text: a

text: honeycomb

text: lattice

text: structure.

text: More

text: speciﬁcally,

text: we

text: study

text: domain

text: walls

text: formed

text: along

text: all

text: different

text: zigzag

text: (ZZ)

text: and

text: armchair

text: (AC)

text: directions

text: of

text: the

text: honeycomb

text: lattice

text: and

text: also

text: allow

text: for

text: a

text: ﬁnite

text: global

text: phase

text: shift

text: across

text: the

text: domain

text: wall,

text: in

text: addition

text: to

text: the

text: change

text: of

text: chirality.

text: We

text: ﬁnd

text: that

text: the

text: domain

text: wall

text: energy

text: density

text: depends

text: not

text: only

text: on

text: edge

text: direction

text: but

text: also

text: strongly

text: on

text: the

text: global

text: phase

text: shift

text: and

text: the

text: doping

text: level.

text: For

text: domain

text: walls

text: along

text: the

text: AC

text: direction,

text: the

text: lowest

text: energy

text: is

text: found

text: for

text: x-direction

text: domain

text: walls,

text: with

text: no

text: additional

text: global

text: phase

text: shift.

text: This

text: is

text: also

text: the

text: overall

text: most

text: stable

text: domain

text: wall

text: conﬁguration

text: for

text: doping

text: levels

text: below

text: the

text: VHS.

text: For

text: the

text: ZZ

text: direction,

text: the

text: lowest

text: domain

text: wall

text: energy

text: instead

text: occurs

text: at

text: a

text: ﬁnite

text: phase

text: shift

text: that

text: changes

text: with

text: doping.

text: Beyond

text: the

text: VHS,

text: where

text: ZZ

text: domain

text: walls

text: have

text: the

text: overall

text: lowest

text: energy,

text: the

text: phase

text: shift

text: is

text: around,

text: but

text: not

text: exactly

text: equal

text: to,

text: We

text: also

text: ﬁnd

text: a

text: ﬁnite

text: suppression

text: of

text: superconductivity

text: in

text: the

text: vicinity

text: of

text: the

text: domain

text: wall.

text: We

text: show

text: that

text: domain

text: walls

text: with

text: a

text: narrower

text: suppression

text: proﬁle

text: are

text: generally

text: more

text: energetically

text: favorable.

text: But

text: notably,

text: we

text: ﬁnd

text: that

text: non-self-consistent

text: results

text: with

text: a

text: sharp

text: order

text: parameter

text: proﬁle

text: at

text: the

text: domain

text: wall

text: often

text: predict

text: the

text: wrong

text: lowest

text: energy

text: domain

text: wall

text: conﬁgurations.

text: We

text: also

text: establish

text: that

text: the

text: recovery

text: length

text: for

text: superconductivity

text: away

text: from

text: the

text: domain

text: wall

text: is

text: inversely

text: related

text: to

text: the

text: order

text: parameter

text: strength

text: in

text: the

text: bulk

text: and

text: not

text: dependent

text: on

text: domain

text: wall

text: orientation.

text: We

text: also

text: study

text: the

text: induced

text: subgap

text: domain

text: wall

text: states.

text: There

text: are

text: always

text: four

text: subgap

text: domain

text: wall

text: states

text: but

text: their

text: dispersion

text: vary

text: signiﬁcantly

text: with

text: domain

text: wall

text: orientation

text: and

text: global

text: phase

text: shift.

text: These

text: results

text: are

text: directly

text: applicable

text: to

text: the

text: d-wave

text: superconducting

text: state

text: in

text: heavily

text: doped

text: graphene,

text: but

text: also

text: to

text: other

text: chiral

text: d-wave

text: honeycomb

text: superconductors.

text: The

text: rest

text: of

text: the

text: article

text: is

text: organized

text: as

text: follows:

text: In

text: Section

text: II

text: we

text: introduce

text: our

text: model

text: and

text: discuss

text: the

text: bulk

text: d-wave

text: state.

text: In

text: Section

text: IIIA

text: we

text: analyze

text: all

text: possible

text: domain

text: walls

text: and

text: establish

text: the

text: most

text: energetically

text: favorable

text: conﬁgurations.

text: Then

text: in

text: Section

text: IIIB

text: we

text: determine

text: the

text: properties

text: of

text: the

text: most

text: favorable

text: domain

text: walls,

text: focusing

text: both

text: on

text: the

text: domain

text: wall

text: subgap

text: states

text: and

text: the

text: order

text: parameter

text: at

text: the

text: domain

text: wall.

text: In

text: Section

text: IIIC

text: we

text: establish

text: the

text: generality

text: of

text: the

text: superconducting

text: recovery

text: length.

text: Finally,

text: in

text: Section

text: IV

text: we

text: conclude

text: our

text: work.


text: 12 42 A. M. Black-Schaffer, Phys. Rev. Lett. 109, 197001 (2012). 43 G. M. Graf and M. Porta, Commun. Math. Phys. 324, 851 (2013). 44 S. P. Mukherjee and K. V. Samokhin, Phys. Rev. B 93, 054525 (2016). 45 T. Lo¨thman and A. M. Black-Schaffer, Phys. Rev. B 90, 224504 (2014). 46 A. M. Black-Schaffer and S. Doniach, Phys. Rev. B 78, 024504 (2008). 47 M. Sigrist and D. F. Agterberg, Prog. Theor. Phys. 102, 965 (1999). 48 J. Schmidt, A. Bouhon, and A. M. Black-Schaffer, Phys. Rev. B 94, 104513 (2016).

text: A.

text: M.

text: Black-Schaffer,

text: Phys.

text: Rev.

text: Lett.

text: G.

text: M.

text: Graf

text: and

text: M.

text: Porta,

text: Commun.

text: Math.

text: Phys.

text: S.

text: P.

text: Mukherjee

text: and

text: K.

text: V.

text: Samokhin,

text: Phys.

text: Rev.

text: B

text: T.

text: Lo¨thman

text: and

text: A.

text: M.

text: Black-Schaffer,

text: Phys.

text: Rev.

text: B

text: A.

text: M.

text: Black-Schaffer

text: and

text: S.

text: Doniach,

text: Phys.

text: Rev.

text: B

text: M.

text: Sigrist

text: and

text: D.

text: F.

text: Agterberg,

text: Prog.

text: Theor.

text: Phys.

text: J.

text: Schmidt,

text: A.

text: Bouhon,

text: and

text: A.

text: M.

text: Black-Schaffer,

text: Phys.

text: Rev.

text: B