text:
# On unavoidable sets of word patterns

## 1. Introduction

When defining or characterizing sets of objects in discrete mathematics, “languages of prohibitions” are often used to define a class of objects by listing the prohibited subobjects, i.e. subobjects that are not allowed to be contained in the objects of the class. The notion of a subobject is defined in different ways depending on the objects under consideration: a subword (a block or segment) for fragmentarily restricted languages, a subgraph for families of graphs, a subshape for two-dimensional shapes (e.g. a submatrix for matrices) and so on.

We collect all prohibited objects into a set that we call a set of prohibited objects, or simply a *set of prohibitions*. The idea of *unavoidable* (or *complete*111The word “complete” appears in e.g. , but the word “*unavoidable*” is of common use in contemporary literature (e.g. see \[15, Chapter 3\], ), so we decided to use the latest terminology in this paper.) set is as follows: if there exists a restriction on the size of an object, in other words, if large enough objects must contain prohibited subobjects, then the set of prohibitions is unavoidable.

In this paper, we are interested in unavoidable sets of *word patterns*, or just *patterns* (see Section 3 for definitions). These patterns are an extension of the *permutation patterns* studied extensively for the last twenty years (see  for a survey on the corresponding problems). Our unavoidable sets of patterns are refinements for those of words. Questions on unavoidability of sets of words appear, for instance, in algebra (sequences without repetitions), coding theory (chain codes), number theory (arithmetic progressions in partitions of the set of natural numbers), dynamical systems (motions of an object in a space with certain restrictions).

There is a number of numerical characteristics that are valuable for unavoidability criteria and the recognition algorithms based on them. Three such characteristics, namely $`M_w(n)`$, $`L_w(n)`$ and $`C_w(n)`$ (for definitions see Section 2), are considered in . We consider the similar characteristics $`M_p(n,m)`$, $`L_p(n,m)`$ and $`C_p(n,m)`$ for the case of prohibited patterns (for definitions see Section 3), where $`m`$ is the number of letters in the corresponding alphabet (we do not use this parameter for the functions $`M_w(n)`$, $`L_w(n)`$ and $`C_w(n)`$ to be consistent with ). Moreover, in Subsubsection 3.2.2 we discuss how finding a lower bound for $`C_p(n,m)`$ is related to the so-called *universal cycles for combinatorial structures* that have been studied intensively (e.g. see  and references therein). To get the lower bound, we prove that the *graph of pattern overlaps* (see definition in Section 3) is Hamiltonian, and derive as a corollary that there exists a universal cycle for word patterns of any length over any alphabet (see Corollary 3.11).

We remark that when considering patterns, the underlying alphabet must be ordered, as opposed to the objects considered in .

The paper is organized as follows. In Section 2 we review the main results on unavoidable sets of words in . The motivation for a relatively detailed review of these papers is the fact that they are available only in Russian (as far as we know), which caused, in particular, the rediscovery of some of those results in . Besides, the results obtained in  are of great interest in general and very useful in this paper in particular. In Section 3, we define the notion of a *pattern*, an *$`n`$-pattern word*, and study unavoidable sets of patterns.

## 2. Unavoidable sets of words

Let $`𝒜=\{a_1,\mathrm{},a_n\}`$ be an alphabet of $`n`$ letters. A *word* over the alphabet $`𝒜`$ is a finite sequence of letters of the alphabet. Any $`i`$ consecutive letters of a word $`X`$ generate a *subword* of length $`i`$. The set $`𝒜^{}`$ is the set of all words over the alphabet $`𝒜`$, and $`𝒜^n`$ is the set of all words over $`𝒜`$ of length $`n`$. Let $`S𝒜^{}`$ be a set of prohibited words or a set of prohibitions. A word that does not contain any words from $`S`$ as its subwords is said to be *free* from $`S`$ or *$`S`$-free*. The set of all $`S`$-free words is denoted by $`\widehat{S}`$.

If there exists a natural number $`k`$ such that the length of any word in $`\widehat{S}`$ is less than $`k`$, then $`S`$ is called an unavoidable set. This is straightforward to see that $`S`$ is unavoidable if and only if $`\widehat{S}`$ has finitely many of elements. Thus, for any unavoidable set $`S`$ we can define the function

$$L_w(\widehat{S})=\underset{X\widehat{S}}{\mathrm{max}}\mathrm{}(X),$$

where $`\mathrm{}(X)`$ is the length of a word $`X`$.

The basic problem in considering of sets of prohibitions is whether or not a given set $`S`$ of prohibitions is unavoidable. Other possible questions are: given an unavoidable $`S`$ find or estimate $`L_w(\widehat{S})`$; construct an $`S`$-free word of length $`L_w(\widehat{S})`$; find the number of elements in $`\widehat{S}`$. If $`S`$ is avoidable then some possible questions are: find an infinite $`S`$-free sequence; describe all such sequences; find the cardinality of the set of these sequences; find the cardinality of the set of finite $`S`$-avoiding sequences of a given length.

Let $`S`$ be a finite set of words over an alphabet $`𝒜`$, and let $`n`$ be the maximal length of a word in $`S`$. If a word $`X`$ is a subword of a word $`Y`$ then we say that $`Y`$ is a *superword* for $`X`$. Suppose now that a word $`XS`$ and $`\mathrm{}(X)<n`$. Remove $`X`$ from $`S`$ and adjoin to $`S`$ all superwords for $`X`$ of length $`n`$. If this procedure is performed for any such $`X`$, and all resulting repetitions are removed, we will get a set $`S^{^{}}`$ of distinct words of length $`n`$.

###### Proposition 2.1.

(\[6, Proposition 1\]) $`S`$ is unavoidable iff $`S^{^{}}`$ is unavoidable.

Thus, sets of prohibitions $`S𝒜^n`$ are of special interest, and for the most part, our considerations in this paper are related to these sets. More precisely, we will consider the functions

$$M_w(n)=\mathrm{min}|S|\text{and}L_w(n)=\mathrm{max}L_w(\widehat{S}),$$

where the extremum is taken with respect to all unavoidable $`S𝒜^n`$. These functions are examples of numerical characteristics that describe the bound between avoidable and unavoidable sets of prohibitions. To give an instance of such a bound, we consider the following example.

###### Example 2.2.

(\[6, Examples 1,2\]). Consider $`𝒜=\{0,1\}`$ and the sets of prohibitions

$$\begin{array}{c}\hfill S_1=\{000,001,101\underset{¯}{1},0101,1111\},\\ \hfill S_2=\{000,001,101\underset{¯}{0},0101,1111\}.\end{array}$$

Thus $`S_1`$ and $`S_2`$ differ only in one underlined letter. One can see that $`S_1`$ is unavoidable, and $`L_w(\widehat{S_1})=8`$. On the other hand, $`S_2`$ is avoidable. Indeed,

$$\underset{}{011}\underset{}{011}\mathrm{}\text{and}\underset{}{0111}\underset{}{0111}\mathrm{}$$

are $`S_2`$-free, and

$$\underset{}{011}\underset{}{0111}\text{and}\underset{}{0111}\underset{}{011}$$

are $`S_2`$-free. Hence, substituting $`0011`$ and $`10111`$ in any sequence over $`𝒜`$, we get an $`S_2`$-free sequence. Hence, the cardinality of $`\widehat{S_2}`$ is the continuum.

In what follows, we will need the following graph. A *de Bruijn graph* is a directed graph $`\stackrel{}{G}_n=\stackrel{}{G}_n(V,E)`$, where the set of vertices $`V`$ is the set of all words in $`𝒜^n`$, and there is an arc from $`u𝒜^n`$ to $`v𝒜^n`$ if and only if

$$u=aw\text{ and }v=wb\text{for some }w𝒜^{n1}\text{ and }a,b𝒜.$$

Figure 1 shows the de Bruijn graphs for a 2-letter alphabet and $`n=2,3`$.

The de Bruijn graphs were first introduced (for the alphabet $`𝒜=\{0,1\}`$) by de Bruijn in 1944 for finding the number of code cycles. However, these graphs proved to be a useful tool for various problems related to combinatorics on words (e.g. see ). It is known that the graph $`\stackrel{}{G}_n`$ can be defined recursively as $`\stackrel{}{G}_n=L(\stackrel{}{G}_{n1})`$, where $`L`$ indicates the operation of taking the line graph.

A *chord* of a directed simple path $`\stackrel{}{P}`$ in $`\stackrel{}{G}_n`$ is an arc that does not belong to $`\stackrel{}{P}`$ but connects two of its vertices in a such way that there is a circuit generated by this arch and the part of the path between the ends of the arc. For instance, on Figure 2 the arc $`\stackrel{}{BA}`$ is a chord for the path $`\stackrel{}{P}`$, whereas $`\stackrel{}{AB}`$ is not.

Let $`C_w(n)`$ denote the greatest length (the number of vertices) of a simple path in $`\stackrel{}{G}_n`$ that does not have chords and does not go through any vertex that has a loop. The following theorem was proved by considering the de Bruijn graph.

###### Theorem 2.3.

(\[6, Theorem 1\]) $`L_w(n)=C_w(n)+n1=|𝒜|^{n1}+n2.`$

The following theorem was proved using the cyclic structure of the de Bruijn graph (the main result of ) as well as the number of conjugacy classes of words with respect to a cyclic shift.

###### Theorem 2.4.

(\[6, Theorem 2\])

$$M_w(n)=\frac{1}{n}\underset{d|n}{}\phi (n/d)|𝒜|^d,$$

where $`\phi (n)`$ is the number of integers in $`\{1,2,\mathrm{},n1\}`$ relatively prime to $`n`$ (Euler’s $`\phi `$-function).

Since any set of prohibitions $`S`$ with $`|S|<M_w(n)`$ is avoidable, it is helpful to have a table for $`M_w(n)`$. For $`|𝒜|=2`$ and $`2n10`$, see Table 1.

In particular, any set of binary words of length 9 that has less than 60 words is avoidable. Also, it is obvious that $`M_w(n)|𝒜|^n/n`$, when $`n\mathrm{}`$. The last observation allows us to prove the following statement.

###### Proposition 2.5.

(\[7, Proposition 1\]) There exist at least $`2^{|𝒜|^n(1\epsilon _n)}`$ unavoidable sets $`S𝒜^n`$. Here $`\epsilon _n0`$ when $`n\mathrm{}`$.

## 3. Unavoidable sets of patterns

The alphabets considered in this section must be totally ordered, and without loss of generality they coincide with $`[m]=\{1,2,\mathrm{},m\}`$ for an appropriate $`m`$.

We refer to  for a general survey of various pattern problems. However, in this paper we are concerned only with *word patterns* studied for the first time in . More precisely, we consider the word patterns *without internal dashes* (see ). For this paper, we can define a pattern to be a subword (of a word) that contains each of the letters $`1,2,\mathrm{},k`$ at least once for some $`k`$, and no other letters. For instance, the word 2613235 contains an occurrence of the pattern $`1323`$, but its subword 2613 is not a pattern. By analogy with Section 2, if a word does not contain a pattern $`p`$, it is *free* from $`p`$ or *$`p`$-free*. However, the crucial difference between this section and Section 2 is that instead of considering *words* free from a pattern $`p`$, we consider the objects that we call the *$`n`$-pattern words*. An $`n`$-pattern word is a word in which each subword of length $`n`$ is a pattern. Thus, constructing $`n`$-pattern words, we can restrict ourselves to alphabets having at most $`n`$-letters. Indeed, an occurrence of a letter $`m>n`$ in a subword $`A`$ of length $`n`$ of an $`n`$-pattern word $`W`$ contradicts the fact that $`A`$ must be a pattern ($`A`$ must contain each of the letters $`1,2,\mathrm{},m`$).

By analogy with Section 2, when dealing with sets of prohibited words, we can consider sets of prohibited patterns, or simply sets of prohibitions, when it is clear which prohibitions we mean. We can also define the notion of an unavoidable set here in the same way. However, in considering prohibited patterns and $`n`$-pattern words, we assume that all prohibitions are of length $`n`$. Hence, for patterns, we can define the functions $`L_p(n,m)`$ and $`M_p(n,m)`$ similarly to $`L_w(n)`$ and $`M_w(n)`$ (recall that $`m`$ is the number of letters in the alphabet). As in Section 2, the basic problem is whether or not a given set $`S_p`$ of prohibitions is unavoidable, and $`L_p(n,m)`$ and $`M_p(n,m)`$ are important numerical characteristics to study.

### 3.1. The function $`M_p(n,m)`$

Recall that the Möbius function is defined by

$$\mu (n)=\{\begin{array}{cc}0,\hfill & \text{if }n\text{ has one or more repeated prime factors},\hfill \\ 1,\hfill & \text{if }n=1,\hfill \\ (1)^k,\hfill & \text{if }n\text{ is a product of }k\text{ distinct primes},\hfill \end{array}$$

so $`\mu (n)0`$ indicates that $`n`$ is square-free.

The purpose of this subsection is to prove the following theorem.

###### Theorem 3.1.

For $`n`$-pattern words over $`[m]`$, we have

$$M_p(n,m)=\underset{i|n}{}\underset{j=0}{\overset{\mathrm{min}(i,m)1}{}}(1)^j\left(\genfrac{}{}{0pt}{}{\mathrm{min}(i,m)1}{j}\right)\frac{1}{i}\underset{d|i}{}\mu (d)(\mathrm{min}(i,m)j)^{\frac{i}{d}},$$

where $`M_p(n,m)=\mathrm{min}|S_p|`$, and the minimum is taken over all unavoidable sets $`S_p`$ of patterns of length $`n`$ over the alphabet $`[m]`$.

One can compare this result with that of Theorem 2.4.

###### Remark 3.2.

In Theorem 3.1, we can assume that $`nm`$, since if $`n<m`$ we can only use the first $`n`$ letters in $`[m]`$ to construct $`n`$-pattern words, which reduces to the case $`n=m`$.

###### Remark 3.3.

For $`n=m`$, we have $`\mathrm{min}(i,m)=i`$ in the formula of Theorem 3.1.

To prove Theorem 3.1, we introduce the *graph of pattern overlaps* $`\stackrel{}{P}_n=\stackrel{}{P}_n(V,E)`$, which is a subgraph of the de Bruijn graph $`\stackrel{}{G}_n`$, where the set of vertices $`V`$ contains all $`n`$-letter patterns over the underlying alphabet $`𝒜`$, and the set of arcs $`E`$ consists of all the arcs of $`\stackrel{}{G}_n`$ between vertices corresponding to the patterns. In Figure 3, we can see the graph of pattern overlaps in the case of a 3-letter alphabet and $`n=3`$ (we omit parentheses around the triples on the graph to indicate that we are dealing with $`\stackrel{}{P}_3`$, not $`\stackrel{}{G}_3`$).

Let $`T_p(n,m)`$ denote the number of conjugacy classes of patterns of length $`n`$ over the alphabet $`[m]`$ with respect to a cyclic shift. For instance, there are 5 conjugacy classes on Figure 3. They are $`\{111\}`$, $`\{112,121,211\}`$, $`\{221,212,122\}`$, $`\{321,213,132\}`$ and $`\{312,123,231\}`$. Thus, $`T_p(3,3)=5`$.

###### Lemma 3.4.

$`M_p(n,m)=T_p(n,m)`$

###### Proof.

To prove the lemma, we follow the proof of Theorem 2.4 in .

Suppose $`S_p`$ is an unavoidable set of patterns of length $`n`$ and $`X`$ is an arbitrary $`n`$-pattern word of length $`n`$ ($`X`$ is a pattern) over $`[m]`$. We form the sequence

$$X^{\mathrm{}}=XXX\mathrm{},$$

by repeating the word $`X`$ periodically. Since $`S_p`$ is unavoidable, $`X^{\mathrm{}}`$ contains a prohibited pattern $`pS_p`$. From the construction of the sequence, $`p`$ is either $`X`$ or a cyclic shift of $`X`$. Thus $`S_p`$ contains a pattern from each conjugacy class of patterns of length $`n`$ over $`[m]`$ with respect to a cyclic shift. Thus, $`|S_p|T_p(n,m)`$, and since $`S_p`$ is an arbitrary set, we have

$$M_p(n,m)T_p(n,m).$$

To prove that $`T_p(n,m)`$ is an upper bound, we need to find an unavoidable set of cardinality $`T_p(n,m)`$. We consider the graph $`\stackrel{}{P}_n`$ whose vertices correspond to the words over $`[m]`$. If $`V^{}V(\stackrel{}{P}_n)`$ and each circuit of $`\stackrel{}{P}_n`$ contains a vertex in $`V^{}`$ then we say that $`V^{}`$ *cuts* all circuits of $`\stackrel{}{P}_n`$. By deleting all such $`V^{}`$ with all incident arcs from $`\stackrel{}{P}_n`$, we get an acyclic graph on the vertex set $`V\backslash V^{}`$. The set of the patterns in $`[m]^n`$ corresponding to the vertices in $`V^{}`$ is unavoidable. Indeed, if not, a sequence free from $`V^{}`$ determines a self-intersecting walk in $`\stackrel{}{P}_n`$ and thus generates a circuit on the vertex set $`V\backslash V^{}`$, which is impossible.

Golomb  found a set of vertices $`V_c`$ that cuts all circuits of the de Bruijn graph $`\stackrel{}{G}_n`$ with $`|V_c|`$ equal to the number of conjugacy classes of the words. Thus $`V_c`$ cuts all circuits in $`\stackrel{}{G}_n`$ and has one vertex in each conjugacy class. Since $`\stackrel{}{P}_n`$ is a subgraph of $`\stackrel{}{G}_n`$, $`\stackrel{}{P}_n`$ will have no circuit after removing the vertices in $`V_c`$. The set of vertices in $`V_c`$ that belong to $`\stackrel{}{P}_n`$ corresponds to an unavoidable set, and thus

$$M_p(n,m)T_p(n,m).$$

This proves the lemma. ∎

###### Lemma 3.5.

$$T_p(n,m)=\underset{i|n}{}\underset{j=0}{\overset{\mathrm{min}(i,m)1}{}}(1)^j\left(\genfrac{}{}{0pt}{}{\mathrm{min}(i,m)1}{j}\right)\frac{1}{i}\underset{d|i}{}\mu (d)(\mathrm{min}(i,m)j)^{\frac{i}{d}}.$$

###### Proof.

Recall that a word $`x𝒜^{}`$, where $`𝒜`$ is any (ordered or unordered) alphabet, is called *primitive* if it is not a power of another word. Thus $`x\mathrm{}`$ is primitive if $`x=y^e`$ only for $`e=1`$. For instance, the words 121, 1221, 12121 are primitive, whereas the word 121212 is not. It is easy to show that each nonempty word is a power of a unique primitive word. Thus, $`x=r^e`$ for a unique primitive word $`r`$. The number $`e`$ is called the *exponent* of $`x`$. It is also easy to see that all words, and hence all patterns, in the same conjugacy class have the same exponent. Moreover, if $`x_1=r_1^e`$ and $`x_2=r_2^e`$ and $`|x_1|=|x_2|`$, then $`x_1`$ is conjugate to $`x_2`$ iff $`r_1`$ is conjugate to $`r_2`$. We define the notion of a *primitive pattern* in the same way as for words. Clearly, all properties of primitive words hold for primitive patterns as well.

So, in order to find $`T_p(n,m)`$, we need to find the number of conjugacy classes of primitive patterns of length $`i`$ over the alphabet $`[m]`$, where $`i|n`$, and then take a sum of these numbers. However, for a given $`i`$, we cannot use directly the well known formula for the number of conjugacy classes of primitive words over $`\mathrm{min}(i,m)`$-letter alphabet (a primitive word of length $`i`$ can have at most $`i`$ distinct letters, since we are dealing with patterns), given by

$$\frac{1}{i}\underset{d|i}{}\mu (d)(\mathrm{min}(i,m))^{\frac{i}{d}}.$$

Indeed, this formula counts, among others, primitive words which are not primitive patterns (when some letter $`j`$, $`2j\mathrm{min}(i,m)1`$, occurs in a primitive pattern whereas $`j1`$ does not). So, we need to use the standard inclusion-exclusion method (the sieve formula) to handle this situation. We define the property $`A_j`$ to be “the letter $`j`$ does not occur in a primitive word”. Clearly we may restrict ourselves to the case $`j\mathrm{min}(i,m)1`$, since the absence of the largest letter, namely $`\mathrm{min}(i,m)`$, is not a bad property when considering patterns. Now we easily get the number of primitive patterns of length $`i`$, which is given by

$$\underset{j=0}{\overset{\mathrm{min}(i,m)1}{}}(1)^j\left(\genfrac{}{}{0pt}{}{\mathrm{min}(i,m)1}{j}\right)\frac{1}{i}\underset{d|i}{}\mu (d)(\mathrm{min}(i,m)j)^{\frac{i}{d}}.$$

This proves the lemma. ∎

Now the truth of Theorem 3.1 follows from Lemmas 3.4 and 3.5.

### 3.2. The function $`L_p(n,m)`$

Let $`C_p(n,m)`$ denote the greatest length (the number of vertices) of a simple path in $`\stackrel{}{P}_n`$ that does not have chords (see the definition in Section 2) and does not pass through any vertex incident with a loop. Using exactly the same considerations as in the proof of Theorem 2.3 (see ), one can prove the following theorem.

###### Theorem 3.6.

$`L_p(n,m)=C_p(n,m)+n1`$.

Moreover, in the case $`m=2`$, the de Bruijn graph $`\stackrel{}{G}_n`$ almost coincides with the graph of pattern overlaps $`\stackrel{}{P}_n`$. Indeed, the only difference between these graphs is the vertex $`(22\mathrm{}2)`$ and all edges adjacent to that vertex ($`22\mathrm{}2`$ is the only binary non-pattern). However, the lemma to Theorem 2.3 (see ) provides that in the binary case $`C_w(n)=2^{n1}1`$, and since $`C_w(n)`$ is the maximal length of a path that, in particular, does not pass through the loop $`(22\mathrm{}2)`$, we have that in this case $`C_w(n)=C_p(n,2)`$. Thus the following theorem is true:

###### Theorem 3.7.

$`L_p(n,2)=2^{n1}+n2.`$

However, in the case $`m3`$, the only useful information we can extract from Theorem 2.3 is the following rough bound

$$L_p(n,m)<m^{n1}+n2.$$

So, according to Theorem 3.6 we need to find $`C_p(n,m)`$ in order to get $`L_p(n,m)`$. The purpose of the rest of the subsection is to find an upper and a lower bound for $`C_p(n,m)`$ for $`m3`$.

#### 3.2.1. An upper bound for $`C_p(n,m)`$

We only give a trivial upper bound. Clearly, in order to avoid chords, each conjugacy class (with respect to shift) which has $`i`$ words can have no more than $`i1`$ words in the path. Thus, we use the formula for $`T_p(m,n)`$ with a correction, namely the factor of $`i1`$, which indicates that each primitive word of length $`i`$ is responsible for a conjugacy class of $`i`$ elements, and we take $`i1`$ elements out of these $`i`$:

$$C_p(n,m)\underset{i|n}{}(i1)\underset{j=0}{\overset{\mathrm{min}(i,m)1}{}}(1)^j\left(\genfrac{}{}{0pt}{}{\mathrm{min}(i,m)1}{j}\right)\frac{1}{i}\underset{d|i}{}\mu (d)(\mathrm{min}(i,m)j)^{\frac{i}{d}}.$$

#### 3.2.2. A lower bound for $`C_p(n,m)`$

We observe that the line graph $`L(\stackrel{}{P}_{n1})`$ for the graph $`\stackrel{}{P}_{n1}`$ determines a subgraph of the graph $`\stackrel{}{P}_n`$. We get that by using the general properties of the de Bruijn graph (since $`\stackrel{}{P}_n`$ is its subgraph), as well as the fact that if $`x_1x_2\mathrm{}x_{n1}`$ and $`x_2x_3\mathrm{}x_n`$ are vertices in $`\stackrel{}{P}_{n1}`$, then the arc between them generates the vertex $`x_1x_2\mathrm{}x_n`$ in the line graph, and $`x_1x_2\mathrm{}x_n`$ is a pattern and thus belongs to $`\stackrel{}{P}_n`$. Moreover, from the considerations in the proof of Theorem 2.3 (see ), it follows that a simple path in $`\stackrel{}{P}_{n1}`$ determines a simple path without chords in $`\stackrel{}{P}_n`$ after removing the loop $`11\mathrm{}1`$.

So, in order to get a lower bound for $`C_p(n,m)`$, we need to construct a simple path in $`\stackrel{}{P}_{n1}`$ of as great a length as possible (ideally a Hamiltonian path). In order to get a Hamiltonian path or a path that is “close” to a Hamiltonian one, we can try to use the methods and techniques similar to those used in constructions of universal cycles for various combinatorial structures such as words, permutations, partitions, and others (e.g. see ).

We briefly discuss the general notion of a universal cycle (see ).

Suppose we are given a family $`_n`$ of combinatorial objects of “rank $`n`$” and let $`m:=|_n|`$ denote their number. We assume that each $`F_n`$ is “generated” or specified by some sequence $`x_1x_2\mathrm{}x_n`$, where $`x_i𝒜`$ for some fixed alphabet $`𝒜`$. We say that $`U=a_0a_1\mathrm{}a_{m1}`$ is a universal cycle (or a $`U`$-*cycle*) for $`_n`$ if $`a_{i+1}a_{i+2}\mathrm{}a_{i+n}`$, $`0i<m`$, runs through each element of $`_n`$ exactly once, where index addition is performed modulo $`n`$.

In our case the combinatorial objects are patterns of length $`n`$, and as in many other cases (e.g. *de Bruijn cycles*, permutations, partitions), but not in all cases (e.g. $`k`$-subsets of an $`n`$-set), it is possible to define a directed *transition graph*, namely the graph of pattern overlaps $`\stackrel{}{P}_n`$, and reduce the problem of constructing a U-cycle to constructing a Hamiltonian circuit for $`\stackrel{}{P}_n`$. Even though we do not need a Hamiltonian circuit (since we are concerned with paths of maximal length), but we can still try to use the same techniques as in  and in references therein.

However, it turns out that the abovementioned techniques work only for $`m=2`$, which we are not interested in since we have an explicit result in this case (see Theorem 3.7). The main problem is that the graph of pattern overlaps is not balanced, i.e. we have vertices where the indegree is not equal to the outdegree. Also, $`\stackrel{}{P}_n`$ is not the line graph of $`\stackrel{}{P}_{n1}`$. However, it is possible to prove the following statement.

###### Theorem 3.8.

The graph of pattern overlaps $`\stackrel{}{P}_n`$ contains a Hamiltonian circuit.

###### Proof.

We first observe that $`\stackrel{}{P}_n`$ is strongly connected. Indeed, suppose we are given two vertices of $`\stackrel{}{P}_n`$, namely $`X=x_1x_2\mathrm{}x_n`$ and $`Y=y_1y_2\mathrm{}y_n`$. If $`I`$ denotes the vertex $`11\mathrm{}1`$, then we can find a path $`\stackrel{}{P}_X`$ from $`X`$ to $`I`$. Indeed, If $`x_i`$ is the largest letter in $`X`$, then we consider the following path in $`\stackrel{}{P}_n`$:

$$X=x_1x_2\mathrm{}x_nx_2x_3\mathrm{}x_nx_1\mathrm{}x_ix_{i+1}\mathrm{}x_{i1}x_{i+1}\mathrm{}x_{i1}1=X^{}.$$

Thus, in $`X^{}`$ we get 1 in place of the largest letter of $`X`$. We observe that $`X^{}`$ is obviously a pattern. Clearly, we can continue this path by replacing the largest letters, one by one, with 1’s until we arrive at $`I`$. On the other hand, it is easy to see that the operation of changing a largest letter to 1 is invertible. For instance, in order to find a path from $`X^{}`$ to $`X`$, we may do the following sequence of steps:

$$X^{}=x_{i+1}\mathrm{}x_{i1}1x_{i+2}\mathrm{}1x_{i+1}\mathrm{}1x_{i+1}\mathrm{}x_nx_1\mathrm{}x_{i1}$$

$$x_{i+1}\mathrm{}x_nx_1\mathrm{}x_{i1}x_ix_{i+2}\mathrm{}x_ix_{i+1}\mathrm{}x_1x_2\mathrm{}x_n=X.$$

Thus, we can find a path from $`I`$ to $`Y`$, which together with the path $`\stackrel{}{P}_X`$, gives a path from $`X`$ to $`Y`$. Similarly, one can get a path from $`Y`$ to $`X`$, which proves that $`\stackrel{}{P}_n`$ is strongly connected.

The main property we use when proving $`\stackrel{}{P}`$ has a Hamiltonian circuit is illustrated in Figure 4A. It says that if $`C_1`$ and $`C_2`$ are two circuits corresponding to different conjugacy classes with respect to the shift, and there is an arc from $`C_1`$ to $`C_2`$ then there is an arc from $`C_2`$ to $`C_1`$ and vise versa. Moreover, in all cases but one (see discussion below), we can choose these arcs as in the Figure 4A, that is once we leave $`C_1`$ at the vertex $`xW`$, we can come back, after visiting $`C_2`$, at the vertex $`Wx`$, which is adjacent to $`xW`$ on the circuit $`C_1`$. The notation $`xW`$ (resp. $`Wx`$) is used to indicate a pattern of length $`n`$ with the first (resp. last) letter $`x`$. The only exception when the picture differs from that on Figure 4A is the loop $`11\mathrm{}1`$, and there is only circuit adjacent to it, namely the one generated by $`11\mathrm{}12`$. In this case $`xW`$ coincides with $`Wx`$, which however does not affect our considerations below.

The basic idea: We show the existence of a Hamiltonian circuit iteratively, starting from any circuit corresponding to a conjugacy class with respect to the shift, and on each following iteration creating a new circuit that contains the previous one and has more vertices since it covers additional circuits corresponding to some conjugacy classes (by covering here we mean containing all the vertices from a circuit in our big circuit). Moreover, we construct the big circuit so that once it arrives at a new circuit corresponding to a conjugacy class, it uses all the vertices from that circuit before leaving. We keep doing that using the fact that $`\stackrel{}{P}_n`$ is a disjoint union of the circuits corresponding to the conjugacy classes, until we create a Hamiltonian circuit.

Let $`H_1`$ be an arbitrary circuit corresponding to a conjugacy class with respect to the shift. Now assume we made $`i`$ iterative steps and obtained a circuit $`H_i`$. If $`H_i`$ covers all the vertices of $`\stackrel{}{P}_n`$, then we are done. Otherwise, on iteration $`i+1`$ we proceed as follows.

The fact that $`\stackrel{}{P}_n`$ is strongly connected ensures that there is an arc from a circuit $`C`$ covered by $`H_i`$ to a circuit which is not covered by $`H_i`$. Our strategy is to start from the vertex where $`H_i`$ arrived at $`C`$, then go around $`C`$ following $`H_i`$ vertex by vertex, until we reach the vertex in which $`H_i`$ leaves $`C`$, and at each step, checking if it is possible to extend $`H_i`$ according to the following considerations.

Assume we are in the vertex $`xW`$ in $`C`$. If there is only one arc coming out of $`C`$, namely the arc to the vertex $`Wx`$ belonging to $`C`$, then we cannot extend $`H_i`$ at this step, so we need to consider the next vertex $`Wx`$ instead. Otherwise, there are $`j1`$ arcs that come out from $`xW`$ to $`j`$ different circuits corresponding to some conjugacy classes (we denote the set of these circuits by $`B`$). The case $`j=1`$ is shown on Figure 4A, if we assume $`C=C_1`$. In this case there are two possibilities: either $`C_2`$ is covered by $`H_i`$ or not. In the first case we cannot extend $`H_i`$, so we need to consider the vertex $`Wx`$ belonging to $`C`$ to proceed further. In the second case, we can extend $`H_i`$ by going to the vertex $`Wy`$, then through the vertices belonging to $`C_2`$ until we reach $`yW`$, then we come back to $`C`$ at the vertex $`Wx`$.

When $`j>1`$, either all circuits from $`B`$ are already covered by $`H_i`$, or there is a number of circuits that are not covered by $`B`$ $`B`$ (we denote the set of these circuits by $`B_0`$). In the first cannot extend $`H_i`$ and we need to continue to proceed to the vertex $`Wx`$. We claim that in the second case there is a path starting from the vertex $`xW`$, going through all the vertices from the circuits from $`B_0`$ and coming to the vertex $`Wx`$. We can extend $`H_i`$ with this path. This claim is not hard to prove for any $`j`$, for instance by induction. However, we only give our proof in the case $`j=3`$ (see Figure 4B) as it is easily generalizable.

In Figure 4B, $`Wy`$, $`Wz`$, and $`Wu`$ are representatives from the circuits $`C_3`$, $`C_2`$ and $`C_1`$ respectively, which belong to $`B`$. The key observation here is that any other circuit in $`B`$ is as good as $`C`$, that is, e.g. we can go from $`xW`$ to any of the vertices $`yW`$, $`zW`$ and $`uW`$, but we can also go from, say, $`uW`$ to any of these vertices. If $`B=B_0`$, then we can start at $`xW`$, go to $`Wu`$, go to $`uW`$ through $`C_1`$, then to $`Wz`$, then go to $`zW`$ through $`C_2`$, to $`Wy`$, to $`yW`$ through $`C_3`$ and finally come to $`Wx`$, in which case we succeeded to extend $`H_i`$. If $`BB_0`$, we use the same procedure simply skipping the circuits not in $`B_0`$. E.g. if $`C_2B_0`$, we change the path above by going from $`uW`$ directly to $`Wy`$, again extending $`H_i`$.

Thus, we constructed the circuit $`H_{i+1}`$ that contains more vertices than $`H_i`$ does. Since $`\stackrel{}{P}_n`$ has finitely many vertices, $`\stackrel{}{P}_n`$ must contain a Hamiltonian circuit. ∎

###### Remark 3.9.

The proof of theorem 3.8 can be simplified, if we add exactly one circuit corresponding to a conjugacy class at each iteration. Indeed, in this case we do not need to consider the sets $`B`$ and $`B_0`$ used in the proof, as well as the illustration on Figure 4B. Thus, once we find a circuit to add to the big circuit, we can start a new iteration. However, we keep the more complicated proof since it helps understand the structure of the graph of pattern overlaps more deeply.

###### Remark 3.10.

One can test how the algorithm of finding a Hamiltonian circuit in $`\stackrel{}{P}_n`$ works in the case $`n=3`$ and $`m=3`$ on Figure 3.

As an immediate corollary to Theorem 3.8 we have the following:

###### Corollary 3.11.

For any $`m`$ and $`n`$, there exists a U-cycle for word patterns of length $`n`$ over an $`m`$-letter alphabet.

The following proposition is easy to prove using elementary combinatorics.

###### Proposition 3.12.

The number of different word patterns of length $`n`$ on $`m`$ letters is

$$\underset{i=1}{\overset{m}{}}\underset{\genfrac{}{}{0pt}{}{a_1+\mathrm{}+a_i=n}{a_11,\mathrm{},a_i1}}{}\left(\genfrac{}{}{0pt}{}{n}{a_1,\mathrm{},a_i}\right).$$

Now, using the discussion in the beginning of the subsubsection, Theorem 3.8 and Proposition 3.12, we obtain the following proposition.

###### Proposition 3.13.

$`C_p(n,m){\displaystyle \underset{i=1}{\overset{m}{}}}{\displaystyle \underset{a_1+\mathrm{}+a_i=n1}{}}\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{a_1,\mathrm{},a_i}}\right).`$

As a final remark, we observe, that another way to get the number of different word patterns of length $`n`$ on $`m`$ letters is using a correction in the formula for $`T_p(m,n)`$ like we did when we obtained the upper bound for $`C_p(n,m)`$. But in this case the correction is $`i`$ rather then $`i1`$, which says that we consider each conjugacy class with respect to shift and find the number of elements in it. Thus, $`i`$ and $`1/i`$ cancel each other, and we get a combinatorial proof of the following identity:

$$\underset{i=1}{\overset{m}{}}\underset{\genfrac{}{}{0pt}{}{a_1+\mathrm{}+a_i=n}{a_11,\mathrm{},a_i1}}{}\left(\genfrac{}{}{0pt}{}{n}{a_1,\mathrm{},a_i}\right)=\underset{i|n}{}\underset{j=0}{\overset{\mathrm{min}(i,m)1}{}}(1)^j\left(\genfrac{}{}{0pt}{}{\mathrm{min}(i,m)1}{j}\right)\underset{d|i}{}\mu (d)(\mathrm{min}(i,m)j)^{\frac{i}{d}}.$$


format: text

text:
# References

1. 14 August 1996 (final accepted version)
2. Non-collinear magnetism in distorted perovskite compounds
3. I.V.Solovyeva,∗, N.Hamadab, K.Terakurac
4. aJRCAT-ATP, 1-1-4 Higashi, Tsukuba, Ibaraki 305, Japan
bScience University of Tokyo, 2641 Yamasaki, Noda, Chiba 278, Japan
cJRCAT-NAIR, 1-1-4 Higashi, Tsukuba, Ibaraki 305, Japan
5. Abstract

Using results of the band structure calculations in the local-spin-density approximation we demonstrate how the crystal distortions affect the magnetic structure of orthorhombically distorted perovskites leading to a non-collinear spin arrangement. Our results suggest that the non-collinearity of the spin magnetic moments, being generally small in La$`M`$O3 series with $`M`$=Cr-Fe, is large in SrRuO3.
6. keywords: Heisenberg exchange, Dzyaloshinskii-Moriya exchange, perovskite transition metal oxides, band structure calculations
7. Corresponding author.
I.V. Solovyev
JRCAT-ATP, c/o NAIR
1-1-4 Higashi
Tsukuba, Ibaraki 305
JAPAN
Fax:+81-298-54-2788
E-mail: igor@jrcat.or.jp

Perovskite transition-metal oxides are known to be the most striking example of materials where magnetic, transport and structural properties are strongly coupled. The reciprocal influence of the spin and lattice degrees of freedom can be due to the spin-orbit interaction (SOI) or the orbital ordering effects . Both mechanisms can be responsible for the non-collinear magnetic arrangement through the antisymmetric Dzyaloshinskii-Moriya exchange interaction  or through strong dependence of the interatomic exchange on the orbital ordering  resulting in pronounced non-Heisenberg behavior . We consider the first possibility for several orthorhombically distorted perovskites with $`D_{2h}^{16}`$ structure where the non-collinear magnetism is allowed by symmetry . However, the magnitude of the effect itself depends on the relative strength of several magnetic interactions.

We use the LMTO Green’s function technique in the real space and perturbative approach both for small deviations of the spin magnetization near the scalar-relativistic equilibrium and SOI. Then, the total energy change can be expressed analytically as $`\delta E=E_H+E_{DM}+E_{MAE}`$. The first term $`E_H1/2_{\mathrm{𝑖𝑗}}J_{\mathrm{𝑖𝑗}}𝐞_i𝐞_j`$ ($`𝐞_i`$ is the direction of the spin magnetization at the site $`i`$) describes the isotropic Heisenberg exchange interaction and appears in the second order with respect to nonuniform rotations of spins . The magnetocrystalline anisotropy energy (MAE) firstly appears in the second order with respect to the SOI. The antisymmetric coupling $`E_{DM}_{i>j}𝐝_{\mathrm{𝑖𝑗}}[𝐞_i\times 𝐞_j]`$ corresponds to the mixed type perturbation with respect to spin rotations and SOI .

$`J_{\mathrm{𝑖𝑗}}`$ and $`𝐝_{\mathrm{𝑖𝑗}}`$ parameters for La$`M`$O3 series with $`M`$=Cr-Fe and SrRuO3 are shown in Tables 1 and 2. General tendencies of the nearest neighbor interactions $`J_{\mathrm{𝑖𝑗}}`$ can be understood by using simple tight-binding arguments given in . (i) $`J_{\mathrm{𝑖𝑗}}<0`$ at the half of the band filling: $`t_{2g}`$-type exchange interaction in LaCrO3 (formal atomic configuration of Cr is $`t_{2g}^3e_g^0`$), both $`t_{2g}`$ and $`e_g`$ interactions in LaFeO3 ($`t_{2g}^3e_g^2`$). (ii) $`J_{\mathrm{𝑖𝑗}}>0`$ at the beginning and at the end of the band filling: $`e_g`$ exchange interaction dominating in LaMnO3 ($`t_{2g}^3e_g^1`$) . (iii) $`J_{\mathrm{𝑖𝑗}}0`$ around 1/3 and 2/3 of the band filling: SrRuO3 case ($`t_{2g}^4e_g^0`$). On the other hand, $`𝐝_{\mathrm{𝑖𝑗}}`$ parameters being proportional to the SOI are generally larger in SrRuO3. The structural factor defined by rotations of the $`M`$O6 octahedra relative to each other is of the same order of magnitude for all compounds considered here. Thus, for La$`M`$O3 compounds the Heisenberg exchange interaction is clearly the strongest, whereas for SrRuO3 it is considerably smaller and comparable with the antisymmetric exchange.

It is particularly interesting in LaMnO3 that the interlayer exchange coupling $`J_{1B}=_{jB}J_{1j}`$ with $`j`$ running over Mn atoms in the plane $`B`$ in Fig.1 crucially depends on the Jahn-Teller distortion (JTD) and varies between ferro- (FM) and antiferromagnetic (AFM) . For the pure compound, the AFM interlayer coupling stabilized by JTD is large enough ($`J_{1B}1.4`$mRy ) to overcome the antisymmetric interactions and the magnetic spin structure is nearly collinear. Weak FM canting due to the $`𝐝_{12}`$ interaction and estimated as $`\mathrm{sin}^1|\alpha _𝐜/J_{1B}|`$ is less than $`2^{}`$ (see  for details). However, JTD is suppressed rapidly with the hole doping, directly affecting the interlayer coupling constant $`J_{1B}`$. At certain concentration of the holes one expects $`|J_{1B}||\alpha _𝐜|`$ and large non-collinearity. This tendency qualitatively explains the appearance of the spin-canted AFM phase accompanying the AFM-to-FM transition in the low-doped manganites .

In conclusion, the non-collinear spin structure, imposed by general symmetry rules, is suppressed in La$`M`$O3 oxides by the strong isotropic exchange interaction. The latter is reduced in SrRuO3 suggesting essentially non-collinear magnetic arrangement.

The work is partly supported by New Energy and Industrial Technology Development Organization (NEDO).


text:
# The Merger QSO 3C 48 and its Host Galaxy in the Near Infrared

## 1 Introduction

A key goal in understanding the connection between nuclear activity (accretion onto a super massive black hole) and host galaxy structure (e.g. morphology, stellar populations, etc.) is to find out about the physical conditions of quasars and the galaxy hosts they reside in.

Because of its large angular size and its brightness at the redshift of $`z0.37`$ boroson84 , 3C 48 is an ideal target for high-resolution imaging and spectroscopy with large telescopes. The near-infrared (NIR) is sensitive for the mass dominating stellar populations and at the same time it is less affected by extinction than the optical. The radio-loud galaxy shows an excess far-infrared (FIR) emission, $`L_{\mathrm{FIR}}=5\times 10^{12}L_{}`$ neug85 , and a one-sided radio jet extending about $`0.5^{\prime \prime }`$ to the north, fanning out to the east to about $`1^{\prime \prime }`$ wilk91 . The quasar is rich in molecular gas, $`M_{\mathrm{H}_2}2.7\times 10^{10}M_{}`$, as CO(1-0) observations show scoville93 ; wink97 . There is also morphological evidence for a recent merger event. Such are a possible double nucleus and a tidal tail extending several arcseconds to the northwest stockton91 ; chatzi99 ; canalizo2000 . Yet it is still unclear, whether the brightness peak about $`1^{\prime \prime }`$ northeast (NE) of the QSO is really the nucleus of the companion galaxy, or a region of interaction of the radio jet with the interstellar medium of the host galaxy inducing star formation canalizo2000 .

## 2 Near Infrared Properties of 3C 48

$`J`$, $`H`$, and $`Ks`$ band imaging as well as $`H`$ and $`K`$ band spectroscopy were carried out using the NIR camera-spectrometer ISAAC at the Very Large Telescope (VLT, ESO, Chile) zuther03 .

### 2.1 $`JHKs`$ Photometry

The images at 1.2, 1.65, and 2.2 $`\mu `$m ($`J`$, $`H`$, and $`Ks`$) show a morphology quite similar to the optical one stockton91 . A tidal tail like structure extends to the northwest of the quasar (Fig. 1). Another feature in the southeast of the quasar was previously thought to be a counter tidal tail canalizo2000 . Our two-color analysis of the host galaxy showed that this feature is most probable not associated with 3C 48. Instead, with colors typical for low-redshift galaxies, it seems to be a foreground galaxy (Fig. 2, aperture no. 12).

The two-color diagram in Fig. 2 shows that all colors of the host galaxy are reddened with respect to an old (10 Gyr) single starburst population (star). The nucleus itself is also heavily reddened (aperture no. 5; obscuration by circum nuclear material). The grey curve presents the color evolution of a single starburst population from zero (lower left end) to 10 Gyr. Young starbursts therefore have quite blue colors. It has been shown that there is a lot of star formation going on in the host canalizo2000 . Starbursts have quite blue NIR colors (cf. evolutionary curve in Fig. 2). Therefore a huge extinction seems to be at work (all data points are redder than the 10 Gyr color point).

In order to study the nuclear region, especially 3C 48A, the nuclear contribution has to be removed. This was done by subtracting a nearby star, scaled to the peak flux of the QSO. The result is presented in the right panel of Fig. 1, showing an excess brightness about $`1^{\prime \prime }`$ northeast of the QSO. The colors of this region are strongly reddened due to the presence of warm/hot dust (only in the $`HK`$ direction). Furthermore there appears to be an alignment of the radio jet with 3C 48A in the NIR. However, multi-particle simulations by scharw03  show, that the A component could still be the nucleus of the companion galaxy.

### 2.2 $`HK`$ Spectroscopy

Emission line spectroscopy allows to probe the interstellar medium (ISM) in the central region of the galaxy, e.g. via the recombination lines Pa$`\beta `$ and Pa$`\gamma `$. In our case we find a line ratio of about $`1.6(\pm 30\%)`$. This is a value typical for the ISM of active galaxies being excitated by the central-engine continuum emission ($`T10`$ K and $`n10`$ cm<sup>-3</sup>).

Absorption lines can be used to trace the stellar content. The depth of the CO(6-3) absorption line is a measure for a population of cool old stars origlia93 . In our case the depth of the line measured only as an upper limit corresponds to a stellar contribution of about 30%. This is consistent with the results from photometry. For details see zuther03 .

## 3 3C 48 revisited

Our NIR imaging and spectroscopy result in a first detection of 3C 48A in $`J`$, $`H`$, and $`Ks`$. The host galaxy, but especially 3C 48A, are strongly reddened. Both scenarios, a second nucleus or an interaction of the ISM with the radio jet, are still possible to explain the nature of 3C 48A. The presence of significant extinction is an important ingredient for future studies of the stellar populations of the host galaxy. Multi-particle simulations by scharw03  can explain the missing counter tidal tail as the result of a projection effect, consistent with the optical canalizo2000  and our NIR data. The merger morphology, its high FIR luminosity, and its large content of molecular gas put 3C 48 in an evolutionary scheme envisioned by sander88 . There it fits nicely as a transition objects between an ultra-luminous infrared galaxy (ULIRG) phase and a pure QSO phase, being still dominated by its FIR excess but also displaying QSO features like its luminosity and rather flat spectral energy distribution.

## Index


text:
# Stability Conditions For Topological D-branes: A Worldsheet Approach

## 1 Introduction

Supersymmetric D-branes play an important role in string theory and its mathematical applications, such as mirror symmetry. There are two rather different approaches to deriving the conditions for space-time supersymmetry in the presence of D-branes. The first approach uses the space-time viewpoint, where D-branes are regarded as “solitons,” whose low-energy dynamics is described by gauge fields, scalars, and fermions. One can deduce the conditions of unbroken space-time supersymmetry by studying the supersymmetric Born-Infeld action for these fields. The second approach uses the worldsheet viewpoint, where D-branes are regarded as boundary conditions for open strings. The condition of space-time supersymmetry is equivalent to the requirement that the boundary condition preserve a suitable chiral algebra.

The case which has been studied most thoroughly is when the gauge field on the D-brane is flat. In this case it is well-known that the two methods give equivalent results . In the case when the gauge field on the D-brane is not flat, the conditions of space-time supersymmetry have been analyzed in Ref.  using the Born-Infeld action.

In this paper we derive the supersymmetry conditions for D-branes from the worldsheet point of view. We limit ourselves to the case when the relevant worldsheet chiral algebra is an $`N=2`$ superconformal algebra plus a spectral flow operator. This corresponds to half-BPS D-branes on manifolds of $`SU(n)`$ holonomy.

There are several reasons why we think it is worthwhile to revisit this problem. First, the worldsheet derivation allows one to obtain the conditions of supersymmetry in all dimensions at once, while in the Born-Infeld approach one has to deal with spinors, whose properties depend on the dimension in a rather complex way. Second, in the analysis of Ref.  certain interesting cases have been missed. For example, it is possible to have a supersymmetric 5-cycle on a complex 3-fold if the gauge field on the cycle is not flat.

More generally, given a Calabi-Yau $`X`$, there may exist supersymmetric D-branes of type A which are not special Lagrangian submanifolds and carry non-flat gauge fields. The conditions on such branes coming from the requirement of $`N=2`$ worldsheet supersymmetry have been worked out in Ref. . In particular, such A-branes must be coisotropic, rather than Lagrangian, submanifolds. However, the conditions which ensure the preservation of the spectral flow operator have not yet been determined for such branes. From the point of view of topological string theory, a boundary condition which preserves $`N=2`$ worldsheet supersymmetry is a topological D-brane, while the preservation of the spectral flow operator is a stability requirement. Thus a supersymmetric D-brane is the same as a stable topological D-brane. But stability is important even if one stays within the confines of topological string theory. To explain this, recall that on the classical level every Lagrangian submanifold $`Y`$ of a Calabi-Yau $`X`$ gives rise to a topological A-brane. On the quantum level, this is not true because of anomalies in the worldsheet R-charge. In order for anomalies to vanish, a certain class in $`H^1(Y,)`$, the Maslov class, must vanish . The definition of the Maslov class is closely related to the notion of a special Lagrangian submanifold; in particular, it is easy to show that any special Lagrangian submanifold has zero Maslov class. On the other hand, the condition of being “special” is precisely the stability condition for Lagrangian A-branes. For coisotropic A-branes, the conditions of anomaly cancellation are not known, but we expect that they are related to stability conditions, in the same way as the vanishing of Maslov class is related to the condition of being “special.” Using this intuition, we propose in this paper an analogue of the Maslov class for coisotropic A-branes of Ref. . We also propose a coisotropic analogue of the notion of a “graded Lagrangian submanifold” introduced in Ref. .

The outline of the paper is as follows. In Section 2 we derive the stability conditions for D-branes of type B. Our results are in complete agreement with Ref. . In Section 3 we derive the stability conditions for D-branes of type A, allowing the gauge field on the branes to be non-flat. In Section 4 we discuss our results and propose definitions of the generalized Maslov class and grading for coisotropic A-branes.

## 2 Stability conditions for B-branes

Let $`X`$ be a Kähler manifold of dimension $`n`$ with a trivial canonical line bundle. We will denote by $`\mathrm{\Omega }`$ a non-vanishing holomorphic $`n`$-form on $`X`$; it is unique up to a constant multiple. The metric tensor on $`X`$ will be denoted $`G`$. Let $`Y`$ be a submanifold of $`X`$ carrying a line bundle $`E`$ with a unitary connection $``$. Let $`F`$ be the curvature 2-form of $``$. It is a real-valued 2-form on $`Y`$. The boundary condition for the fermions has the form

$$\psi _+=R\psi _{},$$

where $`R`$ is an orthogonal transformation of $`TX|_Y=NYTY`$ given by

$$R=\left(\begin{array}{cc}1& 0\\ 0& (gF)^1(g+F)\end{array}\right).$$
(1)
Here $`g`$ is the restriction of the Kähler metric to $`Y`$. The boundary condition for bosons can be determined by requiring $`N=1`$ supersymmetry, but we will not need it here. By definition, a D-brane of type B must preserve the sum of the left and right $`N=2`$ super-Virasoro generators. This requirement imposes a constraint on $`Y`$ and $`(E,)`$: $`Y`$ must be a complex submanifold of $`X`$, and $`F`$ must have type $`(1,1)`$. Thus $`(E,)`$ is a holomorphic line bundle. We will denote by $`k`$ the complex dimension of $`Y`$. Note that as a consequence of these requirements $`R`$ commutes with the complex structure tensor $`I`$. This can be seen more directly by recalling that the R-currents have the form

$$J_\pm G(\psi _\pm ,I\psi _\pm ).$$

Since $`R`$ is orthogonal and takes $`J_+`$ to $`J_{}`$, it must commute with $`I`$.

The spectral flow operators have the form

$$S_\pm =\mathrm{\Omega }(\psi _\pm ,\psi _\pm ,\mathrm{})=\frac{1}{n!}\mathrm{\Omega }_{i_1\mathrm{}i_n}\psi _\pm ^{i_1}\mathrm{}\psi _\pm ^{i_n}.$$

The matching of the spectral flow operators on the boundary requires

$$S_+=e^{i\alpha }S_{},$$

where $`\alpha `$ is a constant. Let $`R_h`$ be the holomorphic part of $`R`$, i.e. the part of $`R`$ which maps $`TX^{1,0}`$ to $`TX^{1,0}`$. Then the above condition becomes

$$detR_h=e^{i\alpha }.$$

Taking into account Eq. (1) and introducing the Kähler form $`\omega =GI`$, we can rewrite this condition in the following form:

$$det(\omega |_Y+iF)=e^{i\alpha +i(nk)\pi }det(g+F).$$

where $`g`$ is the restriction of the metric to $`Y`$. In terms of differential forms, we can write this as follows:

$$\frac{1}{k!}(\omega |_Y+iF)^k=i^{nk}e^{i\alpha /2}\sqrt{det(1+g^1F)}\mathrm{vol}_Y.$$

This condition agrees with the stability condition derived in Ref.  from the Born-Infeld action. For small $`F`$ it reduces to the Donaldson-Uhlenbeck-Yau equation:

$$F\omega ^{k1}=c\omega ^k,c.$$

## 3 Stability conditions for A-branes

By definition, a D-brane of type A is a boundary condition which preserves the sum of the left-moving $`N=2`$ super-Virasoro and the mirror of the right-moving $`N=2`$ super-Virasoro. Since the mirror automorphism maps the R-current to minus itself, this implies that the reflection operator $`R`$ must map $`J_+`$ to $`J_{}`$. Since $`R`$ is orthogonal, this means that it anti-commutes with $`I`$, i.e. it maps $`TX^{1,0}`$ to $`TX^{0,1}`$, and vice versa.

On the classical level, the necessary and sufficient conditions for a D-brane to be an A-branes have been determined in Ref. . These conditions are slightly more complicated than for B-branes. The first requirement is that $`Y`$ must be a coisotropic submanifold of $`X`$. This means that $`\mathrm{ker}\omega |_YTY^\omega TY`$ forms an integrable distribution of constant rank in $`TY`$. Denote the quotient bundle $`TY/TY^\omega `$ by $`FY`$. The second requirement then says that the curvature 2-form $`F`$ of the line bundle annihilates $`TY^\omega `$ and therefore descends to a section of $`^2FY^{}`$. Finally, for the boundary condition to be a topological A-brane, the endomorphism $`\omega ^1F|_{FY}`$ should be a complex structure on $`FY`$. It follows from these conditions that the complex dimension of $`FY`$ is even . We denote the complex dimension of $`FY`$ to be $`2k`$. If $`Y`$ is of real codimension $`r`$ in $`X`$, then the complex dimension of $`X`$ is $`n=r+2k`$.

We use the metric to decompose the bundle $`TX|_Y`$ as a direct sum:

$$TX|_YNYTY^\omega FY.$$

We can choose a local complex basis $`e_1,\mathrm{},e_n`$ for $`TX`$ such that $`e_1,\mathrm{},e_r,`$ and their complex-conjugates span $`NYTY^\omega `$, and $`e_{r+1},\mathrm{},e_n`$ and their complex-conjugates span $`FY`$. The dual basis for $`TX^{}`$ will be denoted $`f^1,\mathrm{},f^n`$. In such a basis the “holomorphic” part of $`R`$, i.e. the part which maps $`TX^{0,1}`$ to $`TX^{1,0}`$, can be represented by a matrix

$$R_\mathrm{h}=\left(\begin{array}{cc}1_{r\times r}& 0\\ 0& (GF)^1(G+F)|_{FY^{0,1}}\end{array}\right)$$
(2)
The lower right block can be simplified by writing

$$G|_{FY}=\left(\begin{array}{cc}0& g\\ g^t& 0\end{array}\right),F|_{TY}=\left(\begin{array}{cc}F_{2,0}& F_{1,1}\\ F_{1,1}^t& F_{0,2}\end{array}\right).$$

Then the condition $`(\omega ^1F|_{FY})^2=1`$ shows that both $`F_{2,0}`$ and $`F_{0,2}`$ are nondegenerate, and they satisfy

$$\begin{array}{c}g^1F_{2,0}=(1+g^1F_{1,1})(g_{}^{t}{}_{}{}^{1}F_{0,2})^1(1+g_{}^{t}{}_{}{}^{1}F_{1,1}^t)\hfill \\ g_{}^{t}{}_{}{}^{1}F_{0,2}=(1g_{}^{t}{}_{}{}^{1}F_{1,1}^t)(g^1F_{2,0})^1(1g^1F_{1,1})\hfill \end{array}$$
(3)
From this it follows that

$$(GF)^1(G+F)|_{FY^{0,1}}=g_{}^{t}{}_{}{}^{1}F_{0,2}(1g^1F_{1,1})^1.$$
(4)
The matching conditon for the spectral flow operator on the boundary is

$$S_+=e^{i\alpha }\overline{S}_{},$$

where again $`\alpha `$ is a constant. Writing out in components and making use of (2),(4), this becomes

$$\mathrm{\Omega }_{12\mathrm{}n}\mathrm{det}F_{0,2}=e^{i\alpha }\overline{\mathrm{\Omega }}_{12\mathrm{}n}\mathrm{det}(gF_{1,1}).$$
(5)
Recall that the holomorphic top form $`\mathrm{\Omega }`$ satisfies $`|\mathrm{\Omega }_{12\mathrm{}n}|^2=c\sqrt{detG}`$ where $`c`$ is a constant. Multiplying Eq. (5) by $`\mathrm{\Omega }_{12\mathrm{}n}`$, we get

$$(\mathrm{\Omega }_{12\mathrm{}n})^2detF_{0,2}e^{i\alpha }\sqrt{detG}det(gF_{1,1}).$$

The right hand side can actually be expressed in terms of the full metric tensor, by noting that

$$\frac{det(G+F)}{detG}=\mathrm{\hspace{0.33em}2}^{2k}det(1g^1F_{1,1}).$$

To derive this identity, one has to use Eq. (3). Thus the spectral flow matching condition can be written as

$$(\mathrm{\Omega }_{12\mathrm{}n})^2\mathrm{det}F_{0,2}e^{i\alpha }\frac{det(G+F)}{detG}\sqrt{detGdetG|_{FY}}$$
(6)
To see the geometric meaning of Eq. (6), we note that one may always assume that $`NY`$ is spanned by the imaginary parts of $`e_i,i=1,\mathrm{},r,`$ and $`TY^\omega `$ is spanned by the real parts of $`e_1,\mathrm{},e_r`$. Consider the following differential form on $`Y`$:

$$\begin{array}{c}\frac{1}{k!}\mathrm{\Omega }|_YF^k=\hfill \\ \hfill \mathrm{\Omega }_{12\mathrm{}n}\mathrm{Pf}(F_{0,2})\mathrm{}f^1\mathrm{}\mathrm{}f^rf^{r+1}\mathrm{}f^n\overline{f}^{r+1}\mathrm{}\overline{f}^n,\end{array}$$
(7)
where $`\mathrm{Pf}(F_{0,2})`$ is the Pfaffian of $`F_{0,2}`$. We can rewrite this as follows:

$$\frac{1}{k!}\mathrm{\Omega }|_YF^k\frac{\mathrm{\Omega }_{12\mathrm{}n}\mathrm{Pf}(F_{0,2})}{\sqrt{\mathrm{det}G|_Y}}\mathrm{vol}(Y)$$
(8)
Comparing (6) with (8), and noting that

$$detF_{0,2}=\mathrm{Pf}(F_{0,2})^2,detGdetG|_{FY}=\left(detG|_Y\right)^2,$$

we obtain

$$\frac{1}{k!}\mathrm{\Omega }|_YF^ke^{i\alpha /2}\sqrt{\frac{det(G+F)}{detG}}\mathrm{vol}(Y)$$

Let us compare this condition with known results. If the bundle on the brane is flat, $`F=0`$, then $`Y`$ is an A-brane if and only if it is Lagrangian. The above stability condition then becomes

$$\mathrm{\Omega }|_Ye^{i\alpha /2}\mathrm{vol}(Y).$$

This means that $`Y`$ is a special Lagrangian submanifold, in agreement with Refs. . For $`F0`$, we can compare with the results of Ref. . The physical range for $`n`$ is $`n=2,3,4`$. For $`n=2`$ $`k=1`$ (a 4-brane wrapped on a 2-fold) Marino et al. found a family of supersymmetric D-branes parametrized by a $`U(2)`$ matrix. A-branes correspond to the case when this matrix has zero elements on the diagonal. Then their stability condition reads

$$\mathrm{\Omega }Fe^{i\beta }\sqrt{\frac{det(G+F)}{detG}}\mathrm{vol}(Y),\beta $$

in complete agreement with our result. For $`n=4`$ we can have $`k=1`$ or $`k=2`$, i.e. a 6-brane or an 8-brane. (A Lagrangian 4-brane in a complex 4-fold is also possible, but then $`F=0`$). One can check that the conditions on the 6-brane found by Marino et al. agree with ours. We could not compare the conditions on the 8-brane, because in Ref.  they are stated only for B-branes.

The remaining case $`n=3`$, $`k=1`$ (5-brane in a complex 3-fold) has not been analyzed before. Stable A-branes of this kind are possible only if $`b_5(X)0`$, which means that $`X`$ is either a complex torus of dimension $`3`$ or a product of a $`T^2`$ and a K3-surface.

## 4 Discussion

The main result of this paper is the determination of the stability condition for A-branes in the case when $`F0`$. This condition can be reformulated in different ways. One convenient formulation, equivalent to the one given above, is that

$$\mathrm{Im}\left(e^{i\alpha /2}\mathrm{\Omega }|_YF^k\right)=0$$

Here $`k`$ is half the complex dimension of the bundle $`FY`$. We would like to emphasize that our analysis (as well as most other existing derivations of supersymmetry conditions for D-branes) applies only when the vector bundle on the brane has rank one.

Analogy with the case of Lagrangian A-branes  suggests that our stability condition ensures the absence of anomaly in the R-charge conservation for worldsheets ending on the D-brane $`(Y,E,)`$. It would be interesting to show this explicitly. In any case, our stability condition suggests a definition of the “generalized Maslov class” for coisotropic A-branes. For any A-brane, stable or not, we can consider the form $`\mathrm{\Omega }|_YF^k`$. This is a top form on $`Y`$, and therefore it is equal to the volume form of $`Y`$ times a complex-valued function $`f`$. From Eq. (7) and non-degeneracy of $`F_{0,2}`$ it follows that this function is non-zero everywhere on $`Y`$. Then the 1-form $`d\mathrm{log}f`$ defines a class in $`H^1(Y,)`$ which we take as the generalized Maslov class. As usual, one can do slightly better and define a class in $`H^1(Y,)`$ whose reduction to $``$ is the class of $`d\mathrm{log}f`$. One chooses an open cover of $`Y`$ such that all double overlaps are connected, chooses a branch of $`\mathrm{log}f`$ on each set of the cover, and considers the Cech 1-cocyle with values in $``$ which measures the obstruction to the existence of the global $`\mathrm{log}f`$. Its cohomology class is the integral version of the generalized Maslov class.

If the generalized Maslov class vanishes in $`H^1(Y,)`$, one can define the notion of a graded coisotropic A-brane which generalizes the notion of a graded Lagrangian submanifold defined by Kontsevich . Namely, a graded coisotropic A-brane is an A-brane together with a global choice of the branch of $`\mathrm{log}f`$. Presumably, there exists a coisotropic version of the $``$-graded Floer complex for any pair of graded coisotropic A-branes. The cohomology of this complex should compute the space of open topological strings stretched between the two branes. A formal definition of the generalized Floer homology in terms of a certain sheaf on the space of paths from one brane to the other has been proposed in Ref. .

## Acknowledgments

A. K. would like to thank Nigel Hitchin and Dmitri Orlov for discussions. This work was supported in part by the DOE grant DE-FG03-92-ER40701.


text:
# Oscillatory nonlinear conductance of an interacting quantum wire with an impurity

(August 8, 2003)

## Abstract

The nonlinear conductance of a one-dimensional quantum wire adiabatically coupled to Fermi liquid electron reservoirs is determined in presence of an impurity. We show that electron-electron interaction in connection with the finite length of the wire leads to characteristic oscillations in the current as a function of the applied voltage.

It is well known that Fermi Liquid (FL) theory is not appropriate to describe transport properties of one-dimensional (1D) electron systems. Correlation effects completely destroy Landau’s quasiparticle picture, and the elementary excitations of a 1D quantumwire (QW) can be modelled in terms of bosonic plasmon and spin density modes. An equivalent representation employs fractionally charged quasiparticles fisherGlazman ; lederer . The charge $`ge`$ depends on the parameter $`g<1`$ characterizing the electron-electron interaction strength, where $`g=1`$ corresponds to the non-interacting limit and $`g0`$ means strong correlations. An impurity potential in a 1D QW is strongly renormalized by the interaction kane92  and effectively acts as a back-scatterer of these fractionally charged quasiparticles fisherGlazman .

These well known properties of 1D fermions are a natural consequence of the Luttinger Liquid (LL) model haldane ; gogol98 , which generically describes the low energy physics of QWs. Despite these drastic departures from FL theory, the strong correlation effects are often disguised in transport measurements. For instance, the conductance of a clean QW is not affected at all by the electron-electron interaction within the wire safi95 ; maslo95 , and the shot noise of a wire with an impurity does not reflect the fractional charge of the backscattered quasiparticles ponom99 ; trauz02 . The reason lies in the coupling of the QW to the FL leads at its ends: experimentally only the chemical potential of electrons in the leads can be manipulated, while the chemical potential of the fractionally charged quasiparticles is not controllable. This represents the main difference with respect to the case of edge currents in fractional quantum Hall bars, where right and left movers are spatially separated (chiral LL), and the chemical potential of the Laughlin quasiparticles can be controlled by the upstream reservoir milli96 . In contrast, in a semiconductor QW or a nanotube right and left movers interact and interfere in the same channel resulting in a nontrivial influence of the contacts even for the case of ideal adiabatic coupling.

Due to the important effects of the leads, a finite length QW in many respects acts as a complicated scatterer in a FL wire, and transport properties obey FL behavior. Thus, experimental observations of LL behavior in semiconductor QWs taruc95 ; yacob96  and nanotubes dekker  are rather based on the temperature dependence of the conductance, or on modifications by the Coulomb interaction of resonant tunnelling through quantum dot structures doublekink . Here we show that due to the interaction within the wire, the nonlinear conductance of a QW with a single impurity shows oscillatory behavior. In contrast to oscillations in double impurity systems doublekink  or in wires with tunneling contacts to the leads liang01 ; peca03 , the oscillations predicted here are completely absent in a non-interacting wire. So we do not discuss modifications of an oscillatory effect already present in FL theory, but non-monotonic behavior of the conductance that is a signature of LL behavior.

To study a QW of finite length coupled to non-interacting reservoirs, we employ the inhomogeneous LL model safi95 ; maslo95 , where the interaction parameter has a spatial dependence. It varies from $`g(|x|>L/2)=1`$ in the leads to $`g(|x|<L/2)=g<1`$ in the QW. Although in real physical systems without backscattering at the contacts the variation of $`g(x)`$ from unity to $`g`$ must be smooth on a length scale $`L_s\lambda _F`$, where $`\lambda _F`$ is the Fermi wavelength, it turns out that, as long as $`L_sL`$, the simpler model of a $`g(x)`$ step-function already captures the important physical properties of a QW adiabatically connected to non-interacting electron reservoirs. Moreover, we have to keep in mind that only under the assumption $`L_sL`$ the QW has a well-defined length $`L`$. Throughout this article we treat the spin-polarized situation at zero temperature, leaving finite temperature aspects for a future publication.

For $`\mathrm{}1`$, the full Lagrangian of our model is $`=_0+_I+_U`$. In bosonization, see Ref. gogol98  for a recent review, the inhomogeneous LL Lagrangian of a clean system in terms of the phase field $`\theta (x,t)`$ reads

$$_0=\frac{1}{2}𝑑x\left[\frac{1}{v_F}\left(_t\theta \right)^2\frac{v_F}{g^2(x)}\left(_x\theta \right)^2\right],$$
(1)
where $`v_F`$ is the bare Fermi velocity of non-interacting right- and left-movers. The backscattering of an impurity at position $`x_0`$ yields the term

$$_I=\lambda \mathrm{cos}\left[\sqrt{4\pi }\theta (x_0,t)+2k_Fx_0\right]$$
(2)
with the ‘bare’ impurity strength $`\lambda `$, whereas the impurity forward scattering omitted here does not affect the current-voltage characteristics. A third term

$$_U=\frac{e}{\sqrt{\pi }}𝑑xU(x)_x\theta ,$$
(3)
describes the coupling to an electrostatic potential $`U(x)`$, with $`eU(x<L/2)=\mu _L`$, $`eU(x>L/2)=\mu _R`$, and $`U(x)=0`$ for $`|x|<L/2`$. Here, $`\mu _L`$ and $`\mu _R`$ are respectively the chemical potentials in the left and right reservoir, and we assume a symmetrically biased system with $`\mu _L=eU/2`$ and $`\mu _R=eU/2`$. $`U(x)`$ describes the shift of the band bottom due to electroneutrality in the FL leads trauz02 . In contrast, the QW itself does not remain electroneutral in presence of an applied voltage $`U`$ and the electrostatics within an interacting QW emerges naturally as a steady-state effect egger96 ; trauz02 .

In bosonization, the average current is given by $`I=(e/\sqrt{\pi })_t\theta (x,t)`$, and it is most convenient to decompose the field operator $`\theta (x,t)`$ as egger96  $`\theta (x,t)=\theta _p(x,t)+\varphi (x,t)`$, where $`\theta _p(x,t)`$ is a particular solution of the equation of motion following from the action $`𝒮[\theta ]=𝒮_0+𝒮_I+𝒮_U`$ that corresponds to Eqs. (1) to (3). On the other hand, $`\varphi (x,t)`$ can be regarded as the fluctuation operator which therefore has to fulfill

$$_t\varphi (x,t)=0.$$
(4)
Straightforward algebra shows that the particular solution may be written as

$$\theta _p(x,t)=\frac{e(UV)}{2\sqrt{\pi }}t+\{\begin{array}{cc}\hfill \frac{e(UV)}{2\sqrt{\pi }v_F}|x|,& |x|>\frac{L}{2}\hfill \\ \hfill \frac{eg^2V}{2\sqrt{\pi }v_F}|x|,& |x|<\frac{L}{2}\hfill \end{array}.$$
(5)
Consequently, the average current reads

$$I=\frac{e^2}{2\pi }(UV),$$
(6)
where $`V`$ is a parameter corresponding to the four-terminal voltage drop at the impurity site. In order to determine $`V`$, one has to impose the condition (4) defining the fluctuation field $`\varphi `$.

The effective action for $`\varphi `$ is easily found to read

$`S[\varphi ]`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle 𝑑t𝑑x\left[\frac{1}{v_F}\left(_t\varphi \right)^2\frac{v_F}{g^2(x)}\left(_x\varphi \right)^2\right]}`$
$``$ $`{\displaystyle \frac{eV}{\sqrt{\pi }}}{\displaystyle 𝑑t\varphi (x_0,t)}`$
$``$ $`\lambda {\displaystyle 𝑑t\mathrm{cos}\left[\sqrt{4\pi }\varphi (x_0,t)e(UV)t+2k_Fx_0\right]}.`$
For weak backscattering the terms related to the impurity, namely the second and third line of Eq. (Oscillatory nonlinear conductance of an interacting quantum wire with an impurity), can be treated as perturbations on the free boson part (first line) employing standard techniques. The conditions when such a perturbative approach is reliable will be discussed below. It is convenient to characterize the conductance in terms of the backscattered current $`I_{\mathrm{BS}}=I_0I=(e^2/2\pi )V`$, where $`I_0=(e^2/2\pi )U`$. As can easily be shown, the lowest order contribution to $`I_{\mathrm{BS}}`$ is of order $`\lambda ^2`$. Without loss of generality we assume $`U>0`$ and find, using the requirement (4), that the backscattered current takes the form

$$I_{\mathrm{BS}}=\frac{e\lambda ^2gL}{4v_F}_{\mathrm{}}^{\mathrm{}}𝑑\tau e^{iu\tau }e^{4\pi 𝒞(\xi _0,\xi _0,\tau )}$$
(8)
where $`u=eU/\omega _L`$ is the ratio of the voltage to the frequency $`\omega _L=v_F/gL`$ characterizing a ballistic traversal of the wire of length $`L`$. Here, the correlation function $`𝒞(\xi ,\eta ,\tau )=\varphi (\xi ,\tau )\varphi (\eta ,0)\varphi ^2(\eta ,0)_0`$ in the absence of an impurity is expressed in terms of the dimensionless variables $`\xi =x/L`$, $`\eta =y/L`$ and $`\tau =tv_F/gL`$. At the dimensionless impurity site $`\xi _0`$ one can show that

$`𝒞(\xi _0,\xi _0,\tau )={\displaystyle \frac{g}{4\pi }}\left\{{\displaystyle \underset{mZ_{\mathrm{even}}}{}}\gamma ^{|m|}\mathrm{ln}\left({\displaystyle \frac{(\alpha +i\tau )^2+m^2}{\alpha ^2+m^2}}\right)+{\displaystyle \underset{mZ_{\mathrm{odd}}}{}}\gamma ^{|m|}\mathrm{ln}\left({\displaystyle \frac{(\alpha +i\tau )^2+(m2\xi _0)^2}{\alpha ^2+(m2\xi _0)^2}}\right)\right\}`$ (9)
where $`\gamma =(1g)/(1+g)`$, and $`\alpha =\omega _L/\omega _c`$. Here $`\omega _c`$ is the standard high-energy cutoff of the LL model with $`\lambda `$, $`eU`$, $`\omega _L\omega _c`$.

Using Eqs. (8) and (9), the backscattered current can now be evaluated numerically for arbitrary values of the parameters $`g`$ (interaction strength), $`u`$ (voltage times length), and $`\xi _0`$ (impurity position). Fig. 1 depicts the result as a function of $`u`$ for two impurity positions (in the middle and at 1/4 of $`L`$), and for an interaction value $`g=0.25`$ characteristic for single-walled metallic carbon nanotubes egger97 . Apparently, the backscattered current oscillates as a function of $`u=eU/\omega _L`$, and the oscillations die out as $`u`$ increases.

Analytical expressions for the current can be obtained in special situations. For a very long wire ($`u\mathrm{}`$) one can perform an asymptotic expansion yielding

$$I_{\mathrm{BS}}=I_{\mathrm{BS}}^{\mathrm{st}}(U)[1+f_{\mathrm{BS}}^{\mathrm{osc}}(u;\xi _0)+\mathrm{}]$$
(10)
where $`I_{\mathrm{BS}}^{\mathrm{st}}`$ is the leading order term while $`f_{\mathrm{BS}}^{\mathrm{osc}}`$ describes the dominant oscillating correction. The dots represent further subleading orders. Explicitly one finds

$$I_{\mathrm{BS}}^{\mathrm{st}}(U)=\frac{\pi ^2𝒩(\alpha ;g)}{\mathrm{\Gamma }(2g)}\frac{e^2U}{2\pi }\frac{(\lambda /\omega _c)^2}{(eU/\omega _c)^{2(1g)}},$$
(11)
which is independent of the length $`L`$ of the wire and the impurity position, and exhibits a power-law behavior as a function of the applied voltage $`U`$ in accordance with the result for the homogeneous LL (see e.g. kane92 ). $`𝒩(\alpha ;g)`$ is a constant of order unity. In contrast, the corrections explicitly depend on both $`\xi _0`$ and $`L`$ (through $`u`$), clearly showing that oscillations are a finite-size effect. For $`0<|\xi _0|<1/2`$ the asymptotic expansion yields

$$f_{\mathrm{BS}}^{\mathrm{osc}}(u;\xi _0)=\frac{2\mathrm{\Gamma }(2g)}{\mathrm{\Gamma }(g\gamma )}\underset{s=\pm }{}𝒟(g;s|\xi _0|)\frac{\mathrm{cos}[(12s|\xi _0|)u\pi g(1+s\gamma /2)]}{u^{2g(1\gamma /2)}}\frac{(1+2s|\xi _0|)^{2g\gamma }}{(12s|\xi _0|)^{g(2\gamma )}(16|\xi _0|)^{g\gamma }},$$
(12)
where $`𝒟(g;s\xi _0)`$ is a numerical factor of order unity. A similar asymptotic expansion has been performed in Ref. ponom97 , where the crossover from LL to FL behavior was studied for a tunnel barrier.

The two frequencies appearing in the cosine terms of Eq. (12) are related to the distances of the impurity from the two contacts (in units of the wire length $`L`$). The phase shifts $`u_s=\pi g(1\pm \gamma /2)`$ as well as the decay factors of the oscillations directly depend on the electron-electron interaction strength. Importantly, when the interaction in the wire is switched off ($`g1`$), i.e., when one deals with a homogeneous system, the oscillations vanish since $`\mathrm{\Gamma }(g\gamma )\mathrm{}`$ in this limit. Clearly, $`I_{\mathrm{BS}}`$ also vanishes when there is no back-scatterer, i.e. $`\lambda 0`$.

One can understand the origin of these current oscillations in terms of interference effects of plasmon modes which are reflected both by the impurity and, in an Andreev-type process safi95 , by the wire-lead contacts. When varying either the length $`L`$ of the wire, or the voltage (which appears as a phase shift in the effective action (Oscillatory nonlinear conductance of an interacting quantum wire with an impurity)), one basically changes the interference conditions, which results in the oscillatory behavior of the current. The period of the oscillations is only independent of $`g`$ if the backscattered current is considered as a function of the dimensionless variable $`u`$; however, one has to keep in mind that $`u`$ ($`=eUgL/v_F`$) has an intrinsic $`v_F/g`$-dependence.

We also point out that the expression (12) is singular for $`\xi _00`$; this is just due to a mathematical complication when the distances of the impurity from the two contacts become equal. Then pairs of poles in the correlator merge. The full expression (8) for the current is however perfectly regular, and indeed one can still calculate the asymptotic expansion for this particular impurity position, obtaining

$$f_{\mathrm{BS}}^{\mathrm{osc}}=\frac{\mathrm{\Gamma }(2g)2^{12g\gamma }}{\mathrm{\Gamma }(2g\gamma )}\frac{\mathrm{cos}[u\pi g(1+\gamma )]}{u^{2g(1\gamma )}}\underset{n=2}{\overset{\mathrm{}}{}}(\frac{n^2}{n^21})^{2g\gamma ^n}.$$

It should be emphasized that in the asymptotic expansion (10) the further subleading orders (represented by dots) can be shown to become increasingly important the stronger the interaction is, i.e., the lower the value of $`g`$. In practice, retaining only $`I_{\mathrm{BS}}^{\mathrm{st}}`$ and $`f_{\mathrm{BS}}^{\mathrm{osc}}`$ is a very good approximation for $`g0.5`$ and $`u10`$. Nevertheless, also for $`g<0.5`$ and/or lower values of $`u`$ (not too close to $`u=1`$), Eq. (10) gives a qualitatively correct picture of the properties of the backscattered current as we have checked numerically.

We now discuss how the behavior of the backscattered current changes with the interaction strength $`g`$. In Fig. 2 the full numerical result of $`I_{\mathrm{BS}}`$, Eq. (8), is plotted in units of $`I_{\mathrm{BS}}^{\mathrm{st}}`$, Eq. (11), for three different values of $`g`$. For simplicity we have considered the case of an impurity located in the middle. The figure illustrates that the stronger the electron-electron interaction, the more pronounced the oscillations are. This is due to the fact that the Andreev-type reflections at the contacts are interaction-dependent with a reflection coefficient $`\gamma =(1g)/(1+g)`$ safi95 . Thus, interference effects are most pronounced in the limit $`g0`$. Furthermore, we see that the period of the oscillations is the same for any value of $`g`$, namely $`\mathrm{\Delta }u=2\pi `$ for $`\xi _0=0`$, but different values of $`g`$ yield different phase shifts.

In the opposite limit of a short wire ($`u0`$), the integral (8) can also be evaluated analytically, and we find for the backscattered current

$$I_{\mathrm{BS}}=(\lambda ,g)\frac{e^2}{2\pi }U$$
(13)
with the cut-off and interaction dependent ‘reflection coefficient’

$$(\lambda ,g)=\pi ^2𝒩_2(\alpha ;g)\frac{(\lambda /\omega _c)^2}{(\omega _L/\omega _c)^{2(1g)}},$$
(14)
where the constant $`𝒩_2(\alpha ;g)`$ is of order unity. The power law behavior of $`(\lambda ,g)`$ as a function of the system size $`L`$ agrees with the calculation of the linear conductance from the Kubo formula ines . Furthermore, Eq.(13) bears a resemblance to the usual Landauer formula. In the limit $`g1`$ the reflection coefficient approaches the expected value $`(\lambda ,1)=\pi ^2(\lambda /\omega _c)^2`$.

Finally we discuss the applicability of the perturbative approach. To be consistent, the backscattered current $`I_{\mathrm{BS}}`$ has to be small compared to the current $`I_0`$ in the absence of an impurity, i.e.,

$$|I_{\mathrm{BS}}|e^2U/2\pi .$$
(15)
The analytical expressions obtained in the limits of both large $`u`$, Eqs. (10)-(11), and small $`u`$, Eqs. (13)-(14), suggest that the consistency condition can be expressed in a simple and cut-off independent way, if we introduce an effective impurity strength $`\lambda ^{}=\omega _c(\lambda /\omega _c)^{1/(1g)}`$. Indeed, Eq. (15) then amounts to $`\lambda ^{}eU`$ for large $`u`$, and $`\lambda ^{}\omega _L`$ for small $`u`$, respectively. This is in accordance with general reasoning. It is well known that the backscattering term (2) is a relevant perturbation to the LL fixed point, and therefore the RG-flow would drive the system to two disconnected QWs, unless some energy-scale cuts off the flow of $`\lambda `$. In our case the applied voltage $`U`$ or the wire ballistic frequency $`\omega _L`$ can play such a role. Therefore, as long as $`\lambda ^{}`$ is much smaller than either $`eU`$ or $`\omega _L`$, the QW remains in the neighborhood of the LL fixed point and our perturbative treatment is justified. In the limit $`g1`$, the effective impurity strength $`\lambda ^{}`$ vanishes, and perturbation theory is always applicable if $`\lambda \omega _c`$.

In summary, we have investigated the backscattered current of an interacting QW of finite size $`L`$ that is coupled to non-interacting electron reservoirs. We have found that the interplay between electron-electron interaction and finite size gives rise to distinct features in the current-voltage characteristics. In particular, we have found an oscillation of the backscattered current as a function of $`u=eU/\omega _L`$. For carbon nanotubes one can estimate a typical ballistic frequency of the order of a few meV. From Figs. 1 and 2, one can see that the oscillations are visible for $`eU10\mathrm{}50`$ meV, a reasonable value, which is consistent with the cut-off of about 1 eV. Hence, the predicted effects should be observable.

We thank H. Bouchiat, R. Egger, D. C. Glattli, and W. Häusler for helpful discussions. Financial support by the CNRS, the DFG and the EU and are gratefully acknowledged.