text:
# Topological Robotics: Motion Planning in Projective Spaces

## 1 Introduction

In this paper we study one of the most elementary problems of the topological robotics: rotation of a line, which is fixed by a revolving joint at a base point: one wants to bring the line from its initial position $`A`$ to a final position $`B`$ by a continuous motion in the space. The final goal is to construct a motion planning algorithm which will perform this task once the initial position $`A`$ and the final position $`B`$ are presented. This problem becomes hard when the dimension of the space is large.

Any such motion planning algorithm must have instabilities, i.e. the motion of the system will be discontinuous as a function of $`A`$ and $`B`$. These instabilities are caused by topological reasons. A general approach to study instabilities of robot motion was suggested recently in papers . With any path-connected topological space $`X`$ one associates in  a number $`\mathrm{𝐓𝐂}(X)`$, called the topological complexity of $`X`$. This number is of fundamental importance for the motion planning problem: $`\mathrm{𝐓𝐂}(X)`$ determines character of instabilities which have all motion planning algorithms in $`X`$.

The motion planning problem of moving a line in $`𝐑^{n+1}`$ reduces to a topological problem of calculating the topological complexity of the real projective space $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$, which we tackle in this paper. We compute the number $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ for all $`n23`$ (see the table in section 6). This will probably be useful for applications.

Surprisingly, the problem of finding a general formula for $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ turns out to be quit difficult. One of the main results of this paper claims that for $`n1,3,7`$, the number $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ coincides with the smallest integer $`k`$ such that the projective space $`\mathrm{𝐑𝐏}^n`$ admits an immersion into $`𝐑^{k1}`$. This means that our problem of finding $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ is equivalent to the immersion problem for real projective spaces. The latter is a famous, classical, well researched, topological problem, see  for a survey. A general answer to the immersion problem $`\mathrm{𝐑𝐏}^n𝐑^{k1}`$ is not known, but there are many important results in the literature.

For the remarkable special values $`n=1,3,7`$ the answer is very simple: $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)=n+1`$.

We show that for $`n8`$ explicit motion planning algorithms for lines in $`𝐑^n`$ can be build by using multiplication of the complex numbers, the quaternions, and the Cayley numbers.

## 2 The motion planning problem

In this section we recall some definitions and results from .

Let $`X`$ be a topological space $`X`$, thought of as the configuration space of a mechanical system. We will always assume that $`X`$ is a connected CW complex. Given two points $`A,BX`$, one wants to connect them by a path in $`X`$; this path represents a continuous motion of the system from one configuration to the other. A solution to this motion planning problem is a rule (algorithm) that takes $`(A,B)X\times X`$ as an input and produces a path from $`A`$ to $`B`$ as an output. Let $`PX`$ denote the space of all continuous paths $`\gamma :[0,1]X`$, equipped with the compact-open topology, and let $`\pi :PXX\times X`$ be the map assigning the end points to a path: $`\pi (\gamma )=(\gamma (0),\gamma (1))`$. The map $`\pi `$ is a fibration whose fiber is the based loop space $`\mathrm{\Omega }X`$. The motion planning problem consists of finding a section $`s`$ of this fibration.

The section $`s`$ cannot be continuous, unless $`X`$ is contractible, see . One defines $`\mathrm{𝐓𝐂}(X)`$, the topological complexity of $`X`$, as the smallest number $`k`$ such that $`X\times X`$ can be covered by open sets $`U_1,\mathrm{},U_k`$, so that for every $`i=1,\mathrm{},k`$ there exists a continuous section $`s_i:U_iPX,\pi s_i=\mathrm{id}`$.

According to , a motion planner in $`X`$ is defined by finitely many subsets $`F_1,\mathrm{},F_k`$ $`X\times X`$ and continuous maps $`s_i:F_iPX`$, where $`i=1,\mathrm{},k`$, such that:

1. the sets $`F_1,\mathrm{},F_k`$ are pairwise disjoint $`F_iF_j=\mathrm{}`$, $`ij`$, and cover $`X\times X`$;
2. $`\pi s_i=1_{F_i}`$ for any $`i=1,\mathrm{},k`$;
3. each $`F_i`$ is an ENR.

The subsets $`F_i`$ are local domains of the motion planner; the maps $`s_i`$ are local rules. Any motion planner determines a motion planning algorithm: given a pair $`(A,B)`$ of initial - final configurations, we determine the index $`i\{1,2,\mathrm{},k\}`$, such that the local domain $`F_i`$ contains $`(A,B)`$; then we apply the local rule $`s_i`$ and produce the path $`s_i(A,B)PX`$ in $`X`$ as an output.

The order of instability of a motion planner is defined as the largest $`r`$ such that the closures of some $`r`$ among the local domains $`F_1,\mathrm{},F_k`$ have a non-empty intersection:

$`\overline{F}_{i_1}\overline{F}_{i_2}\mathrm{}\overline{F}_{i_r}\mathrm{}\text{where}1i_1<i_2<\mathrm{}<i_rk.`$
The order of instability describes the character of discontinuity of the motion planning algorithm determined by the motion planner.

In  it is shown that: the minimal integer $`k`$, such that a smooth manifold $`X`$ admits a motion planner with $`k`$ local rules, equals $`\mathrm{𝐓𝐂}(X)`$. Moreover, the minimal integer $`r>0`$, such that $`X`$ admits a motion planner with order of instability $`r`$, equals $`\mathrm{𝐓𝐂}(X)`$.

This explains importance of knowing the number $`\mathrm{𝐓𝐂}(X)`$ while solving practical motion planning problems.

Let us mention some other results from , which will be used later in this paper. $`\mathrm{𝐓𝐂}(X)`$ depends only on the homotopy type of $`X`$. One has

$`\mathrm{cat}(X)\mathrm{𝐓𝐂}(X)2\mathrm{cat}(X)1,`$ (1)
where $`\mathrm{cat}(X)`$ is the Lusternik-Schnirelmann category of $`X`$. If $`X`$ is $`r`$-connected then

$`\mathrm{𝐓𝐂}(X)<{\displaystyle \frac{2\mathrm{dim}(X)+1}{r+1}}+1.`$ (2)
Next result provides a lower bound for $`\mathrm{𝐓𝐂}(X)`$ in terms of the cohomology ring $`H^{}(X)`$ with coefficients in a field. The tensor product $`H^{}(X)H^{}(X)`$ is also a graded ring with the multiplication

$$(u_1v_1)(u_2v_2)=(1)^{|v_1||u_2|}u_1u_2v_1v_2$$

where $`|v_1|`$ and $`|u_2|`$ are the degrees of the cohomology classes $`v_1`$ and $`u_2`$. The cohomology multiplication $`H^{}(X)H^{}(X)H^{}(X)`$ is a ring homomorphism. Let $`IH^{}(X)H^{}(X)`$ be the kernel of this homomorphism. The ideal $`I`$ is called the ideal of zero-divisors of $`H^{}(X)`$. The zero-divisors-cup-length is the length of the longest nontrivial product in the ideal of zero-divisors. It is shown in  that the topological complexity $`\mathrm{𝐓𝐂}(X)`$ is greater than the zero-divisors-cup-length of $`H^{}(X)`$.

In this estimate, one can equally well use extraordinary cohomology theories instead of the usual cohomology.

The topological complexity $`\mathrm{𝐓𝐂}(X)`$, as well as the Lusternik-Schnirelmann category $`\mathrm{cat}(X)`$, are particular cases of the notion of Schwarz genus (also known as sectional category) of a fibration; it was introduced and thoroughly studied by A.Schwarz in , see also .

## 3 Motion planning in simply connected symplectic manifolds

In this section we find the topological complexity of motion planning in any closed simply connected symplectic manifold:

###### Theorem 1

Let $`X`$ be a closed $`2n`$-dimensional simply connected symplectic manifold. Then $`\mathrm{𝐓𝐂}(X)=2n+1`$.

Proof. Since $`X`$ is simply connected, the inequality $`\mathrm{𝐓𝐂}(X)2n+1`$ follows from (2). On the other hand, let $`\omega `$ be the symplectic 2-form on $`X`$. If $`[\omega ]H^2(X;𝐑)`$ denotes the respective cohomology class then $`[\omega ]^n0`$. Hence $`[\omega ]11[\omega ]H^{}(X;𝐑)H^{}(X;𝐑)`$ is a zero-divisor (see the definition in §2) whose $`2n`$-th power

$$([\omega ]11[\omega ])^{2n}$$

does not vanish since it contains the term

$$(1)^n\left(\genfrac{}{}{0pt}{}{2n}{n}\right)[\omega ]^n[\omega ]^n.$$

The opposite inequality $`\mathrm{𝐓𝐂}(X)2n+1`$ now follows from Theorem 7 of . $`\mathrm{}`$

This result applies, in particular, to the complex projective space $`\mathrm{𝐂𝐏}^n`$:

###### Corollary 2

One has, $`\mathrm{𝐓𝐂}(\mathrm{𝐂𝐏}^n)=2n+1.`$

Theorem 1 also applies to other smooth simply connected algebraic varieties such as complex Grassmannians and flag varieties.

###### Remark 1

A similar result, $`\mathrm{cat}(X)=n+1`$, for any closed simply connected symplectic manifold $`X`$, is well known .

## 4 Motion planning in the real projective space: the initial discussion

In this section we start studying the problem of computing the topological complexity of real projective space $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$. This problem is much harder than finding the topological complexity of the complex projective space (Corollary 2). We will see below that the problem of finding the number $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ is equivalent to the problem of finding the smallest $`k`$ such that $`\mathrm{𝐑𝐏}^n`$ can be immersed into the Euclidean space $`𝐑^k`$.

We will begin this section by proving a general result relating the topological complexity of a space with the Schwarz genus of a covering.

###### Theorem 3

Let $`X`$ be a finite connected polyhedron and let $`p:\stackrel{~}{X}X`$ be a regular covering map with the group of covering transformations $`G`$. Let $`\stackrel{~}{X}\times _G\stackrel{~}{X}`$ be obtained from the product $`\stackrel{~}{X}\times \stackrel{~}{X}`$ by factorizing with respect to the diagonal action of $`G`$. Then the topological complexity $`\mathrm{𝐓𝐂}(X)`$ of space $`X`$ is greater than or equal to the Schwarz genus of the covering

$`q:\stackrel{~}{X}\times _G\stackrel{~}{X}X\times X.`$ (3)
Proof. We will use the notation from Section 2. In particular, $`\pi :PXX\times X`$ will denote the canonical fibration of the space of paths $`\pi (\gamma )=(\gamma (0),\gamma (1))`$, where $`\gamma PX`$, $`\gamma :[0,1]X`$.

Consider the following commutative diagram

$`\begin{array}{ccc}\hfill PX& \stackrel{f}{}& \stackrel{~}{X}\times _G\stackrel{~}{X}\hfill \\ & & \\ & \pi q& \\ & & \\ & X\times X& \end{array}`$
where the map $`f:PX\stackrel{~}{X}\times _G\stackrel{~}{X}`$ is defined as follows: given a continuous path $`\gamma :[0,1]X`$, let $`\stackrel{~}{\gamma }:[0,1]\stackrel{~}{X}`$ be any lift of $`\gamma `$, and we set

$$f(\gamma )=(\stackrel{~}{\gamma }(0),\stackrel{~}{\gamma }(1))\stackrel{~}{X}\times _G\stackrel{~}{X}.$$

The lift $`\stackrel{~}{\gamma }`$ of $`\gamma `$ depends on the choice of the initial point $`\stackrel{~}{\gamma }(0)\stackrel{~}{X}`$ but nevertheless the map $`f`$ is well defined and continuous. If $`U`$ is an open subset of $`X\times X`$ and $`s:UPX`$ is a continuous section of the fibration $`\pi `$ over $`U`$ then $`fs`$ is a continuous section of $`q`$ over $`U`$. If there exits an open covering $`U_1U_2\mathrm{}U_k`$ of $`X\times X`$ with a continuous section $`s_i`$ of $`\pi `$ over each open set $`U_i`$, then $`fs_i`$ is a continuous section of $`q`$ over $`U_i`$ and we see that the Schwarz genus of the covering $`q`$ is at most $`k`$. $`\mathrm{}`$

###### Remark 2

In general (3) is not a regular covering; it is regular if and only if the group $`G`$ is Abelian.

Next we are going to apply Theorem 3 to the case $`X=\mathrm{𝐑𝐏}^n`$:

###### Corollary 4

The number $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ is greater than or equal to the Schwarz genus of the two-fold covering $`S^n\times _{𝐙_2}S^n\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$.

We will present this result in a different form.

If $`n`$ is fixed we will always denote by $`\xi `$ the canonical real line bundle over $`\mathrm{𝐑𝐏}^n`$. The exterior tensor product $`\xi \xi `$ is a real line bundle over $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$. Its first Stiefel - Whitney class is

$$w_1(\xi \xi )=\alpha \times 1+1\times \alpha H^1(\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n;𝐙_2),$$

where $`\alpha H^1(\mathrm{𝐑𝐏}^n;𝐙_2)`$ is the generator. This last condition determines uniquely the bundle $`\xi \xi `$.

###### Corollary 5

The topological complexity $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ is not less than the minimal $`k`$ such that the Whitney sum $`k(\xi \xi )`$ of $`k`$ copies of $`\xi \xi `$ admits a nowhere vanishing section.

Proof. By Theorem 3 $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ is not less than the Schwarz genus of the unit sphere bundle $`q`$ of $`\xi \xi `$. By Theorem of Schwarz , the latter coincides with the smallest $`k`$ such that the $`k`$-fold fiberwise join $`qq\mathrm{}q`$ admits a section. But, clearly, the $`k`$-fold fiberwise join $`qq\mathrm{}q`$ coincides with the unit sphere bundle of the Whitney sum $`k(\xi \xi )`$. This implies our statement. $`\mathrm{}`$

We will see below that the lower bound given by Corollaries 4 and 5 are in fact precise.

The left inequality in (1) gives

$`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)n+1,`$ (5)
since the Lusternik - Schnirelman category of $`\mathrm{𝐑𝐏}^n`$ is $`n+1`$. We will show later in this paper that an equality holds in (5) if and only if $`n=1,3,7`$.

Applying Theorem 7 from  we obtain:

###### Theorem 6

If $`n2^{r1}`$ then $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)2^r`$.

Proof. Let $`\alpha H^1(\mathrm{𝐑𝐏}^n;𝐙_2)`$ be the generator. Then $`1\alpha +\alpha 1`$ is a zero-divisor (see §2), and we consider its power

$`(1\alpha +\alpha 1)^{2^r1}.`$ (6)
The binomial expansion of this class contains the term

$`\left({\displaystyle \genfrac{}{}{0pt}{}{2^r1}{n}}\right)\alpha ^k\alpha ^n.`$ (7)
where $`k=2^r1n<n`$. It is well known that the binomial coefficients $`\left(\genfrac{}{}{0pt}{}{2^r1}{i}\right)`$ are odd for all $`i`$. Hence (7) is a non-zero term, and so (6) does not vanish either. Applying Theorem 7 from , one finds that the topological complexity of $`\mathrm{𝐑𝐏}^n`$ is not less than $`2^r`$. $`\mathrm{}`$

###### Remark 3

A different proof of Theorem 6 can be based on Corollary 5. Let $`k_n`$ denote the least $`k`$ such that the top Stiefel - Whitney class $`w_k`$ of $`k(\xi \xi )`$ vanishes. Then $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)k_n`$ (since the top Stiefel - Whitney class of a vector bundle having a section, vanishes). We want to show that $`k_n2^r`$ for $`n2^{r1}`$. By Cartan’s formula $`w_k(k(\xi \xi ))=(\alpha _1+\alpha _2)^k,`$ where $`\alpha _1,\alpha _2H^1(\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n;𝐙_2)`$ denote the standard 1-dimensional generators. If $`k=2^r1`$, then all binomial coefficients $`\left(\genfrac{}{}{0pt}{}{k}{i}\right)`$ are odd and since $`2^r12n`$, the Stiefel - Whitney class $`w_k(k(\xi \xi ))`$ contains a nontrivial term $`\left(\genfrac{}{}{0pt}{}{k}{i}\right)\alpha _1^i\alpha _2^{ki}`$. Hence $`k_n2^r`$ and the result follows.

## 5 Nonsingular maps and axial maps

In this section we recall some notions and basic results concerning non-singular maps $`𝐑^{n+1}\times 𝐑^{n+1}𝐑^{k+1}`$ and axial maps $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$. These maps appear in the mathematical literature in relation with the immersion problem $`\mathrm{𝐑𝐏}^n𝐑^k`$, see below. The material of this section (except maybe Lemma 11) should be considered as well-known, although we were unable to find a proper reference.

###### Definition 1

A continuous map

$`f:𝐑^n\times 𝐑^n𝐑^k`$ (8)
is called nonsingular if it has the following two properties:

* $`f(\lambda u,\mu v)=\lambda \mu f(u,v)`$ for all $`u,v𝐑^n`$, $`\lambda ,\mu 𝐑`$, and
* $`f(u,v)=0`$ implies that either $`u=0`$, or $`v=0`$.

Our definition of a nonsingular map is not quite standard: we do not require $`f`$ to be bilinear. Bilinear nonsingular maps give immersions of projective spaces into the Euclidean space, see . Constructions of bilinear nonsingular maps are given in  and . In , K.Y. Lam considers maps $`f(u,v)`$ with property (b), which are linear only with respect to $`v`$ and satisfy a weaker property $`f(u,v)=f(u,v)`$ with respect to $`u`$; he calls such maps skew-linear.

We will show below (see proof of Proposition 17) that the nonsingular maps in the sense of Definition 1 provide a convenient tool for constructing explicit motion planning algorithms in projective spaces.

###### Lemma 7

There are no nonsingular maps $`f:𝐑^n\times 𝐑^n𝐑^k`$ with $`k<n`$.

Proof. We may apply the Borsuk - Ulam Theorem to the map $`uf(u,v)`$, where $`v0`$ is fixed and where $`u`$ varies on the unit sphere $`S^{n1}𝐑^n`$. By the Borsuk - Ulam Theorem, $`f(u,v)=f(u,v)`$ for some $`uS^{n1}`$, but the latter also is $`f(u,v)`$, and thus $`f(u,v)=0`$. This gives a contradiction with the nonsingularity property. $`\mathrm{}`$

###### Lemma 8

For $`n=1,2,4`$ or $`8`$, there exists a nonsingular map $`f:𝐑^n\times 𝐑^n𝐑^n`$ with the property that for any $`u𝐑^n`$, $`u0`$, the first coordinate of $`f(u,u)`$ is positive.

Proof. For $`n=1`$ we take $`f(u,v)=uv`$, the usual product of real numbers.

For $`n=2`$ we may take $`f(u,v)=u\overline{v}`$, the product of $`u`$ and the conjugate of $`v`$, viewed as complex numbers.

We identify $`𝐑^4`$ with the set of quaternions $`v=x_1+x_2i+x_3j+x_4k`$ and, for $`n=4`$, define the nonsingular map $`f`$ by $`f(u,v)=u\overline{v}𝐑^4`$, where the bar denotes the quaternionic conjugation: $`\overline{v}=x_1x_2ix_3jx_4k`$.

To construct $`f`$ for $`n=8`$, we identify $`𝐑^8`$ with the ring of Cayley numbers, which can be defined as follows, see . A Cayley number can be uniquely written in the form $`q+Qe`$, where $`q,Q`$ are quaternions and $`e`$ is a formal symbol. The multiplication is defined by the formula

$$(q+Qe)(r+Re)=(qr\overline{R}Q)+(Rq+Q\overline{r})e.$$

Here the bar denotes the conjugation of quaternions, as above. We define $`f:𝐑^8\times 𝐑^8𝐑^8`$ by

$$f(q+Qe,r+Re)=(q+Qe)(\overline{r}Re).$$

Then $`f(q+Qe,q+Qe)=q\overline{q}+Q\overline{Q}`$ is real and positive, assuming that the Cayley number $`q+Qe0`$ is nonzero. $`\mathrm{}`$

###### Lemma 9

For $`n`$ distinct from $`1,2,4,8`$ there are no nonsingular maps $`f:𝐑^n\times 𝐑^n𝐑^n`$.

Proof. The statement can be deduced from the Adams’ solution of the Hopf invariant one problem . Namely, suppose that $`f`$ as above exists, where $`n>2`$. Then we obtain a continuous map $`g:S^{n1}\times S^{n1}S^{n1}`$ given by

$$g(x,y)=\frac{f(x,y)}{|f(x,y)|},x,yS^{n1}.$$

$`g`$ satisfies $`g(x,y)=g(x,y)=g(x,y)`$. Restricting $`g`$ onto one factor $`S^{n1}\times `$ (where $``$ is a base point) gives a self map of $`S^{n1}`$ which commutes with the antipodal involution and hence has an odd degree (this is a theorem of Borsuk, see , pages 483 - 485). Similarly, the degree of $`g|_{\times S^{n1}}`$ is odd. Hence, the bidegree of $`g`$ is $`(k,\mathrm{})`$, where both integers $`k`$ and $`\mathrm{}`$ are odd. The existence of $`g`$ implies the vanishing of the Whitehead product

$`[k\iota ,\mathrm{}\iota ]=k\mathrm{}[\iota ,\iota ]\pi _{2n3}S^{n1},`$ (9)
where $`\iota \pi _{n1}S^{n1}`$ is the generator. If $`n`$ is odd, then $`[\iota ,\iota ]\pi _{2n3}S^{n1}`$ is of infinite order, hence the Whitehead product (9) cannot vanish. If $`n`$ is even and distinct from $`1,2,4,8`$, then the Whitehead product $`[\iota ,\iota ]\pi _{2n3}S^{n1}`$ is nonzero (as proven by Adams) and has order two, which again implies that (9) is nonzero as $`k\mathrm{}`$ is odd. $`\mathrm{}`$

###### Definition 2

Let $`n`$ and $`k`$ be two positive integers with $`n<k`$. A continuous map

$`g:\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$ (10)
is called axial of type $`(n,k)`$ if its restrictions to $`\times \mathrm{𝐑𝐏}^n`$ and $`\mathrm{𝐑𝐏}^n\times `$ are homotopic to the inclusions maps $`\mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$.

Here $``$ denotes a base point of $`\mathrm{𝐑𝐏}^n`$. Note that for $`n<k`$ any continuous map $`h:\mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$ is either homotopically trivial or it is homotopic to the inclusion map $`\mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$. If $`\alpha H^1(\mathrm{𝐑𝐏}^k;𝐙_2)`$ denotes the generator, then $`h^{}\alpha H^1(\mathrm{𝐑𝐏}^n;𝐙_2)`$ is either zero or equals $`\alpha `$. The map $`h`$ is homotopically trivial if and only if $`h^{}\alpha =0`$. This shows that the property of the axial map $`g`$, see (10), can be equivalently stated by the formula: $`g^{}\alpha =\alpha \times 1+1\times \alpha .`$ This last condition fixes the homotopy type of a map $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^{\mathrm{}}`$ and we are interested in finding the smallest $`k`$ such that this map can be factorized through the inclusion $`\mathrm{𝐑𝐏}^k\mathrm{𝐑𝐏}^{\mathrm{}}`$. This shows that there always exists an axial map $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^{2n}`$. In fact, we some extra effort, one shows that there always exists an axial map $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^{2n1}`$.

###### Lemma 10

Assume that $`1<n<k`$. There exists a bijection between nonsingular maps $`𝐑^{n+1}\times 𝐑^{n+1}𝐑^{k+1}`$ (viewed up to multiplication by a nonzero scalar) and axial maps $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$.

Proof. Given a nonsingular map $`f:𝐑^{n+1}\times 𝐑^{n+1}𝐑^{k+1}`$ one defines $`g:\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$, where for $`u,vS^n𝐑^{n+1}`$, the value $`g(u,v)`$ is the line through the origin containing the point $`f(u,v)𝐑^{k+1}`$. To show that $`g`$ is indeed axial, we fix $`vS^n`$ and vary only $`uS^n`$. We see that the obtained map $`\mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$ lifts to a map $`S^nS^k`$ given by $`uf(u,v)`$, and, the relation $`f(u,v)=f(u,v)`$ implies that $`\mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$ is not null-homotopic. Similarly, using $`f(u,v)=f(u,v)`$ we find that the restriction of $`g`$ onto $`\times \mathrm{𝐑𝐏}^n`$ is not null-homotopic.

Suppose now that we are given an axial map (10). Passing to the universal covers we obtain a continuous map $`\overline{g}:S^n\times S^nS^k`$ (defined up to a sign). As explained above, the axial property translates into $`\overline{g}(u,v)=\overline{g}(u,v)=\overline{g}(u,v)`$ for all $`u,vS^n`$. Now we may define a nonsingular map $`f:𝐑^{n+1}\times 𝐑^{n+1}𝐑^{k+1}`$ by

$$f(u,v)=|u||v|\overline{g}(\frac{u}{|u|},\frac{v}{|v|}),u,v𝐑^{k+1}\{0\}.$$

$`\mathrm{}`$

###### Lemma 11

Suppose that for a pair of integers $`1<n<k`$ there exists a non-singular map $`𝐑^{n+1}\times 𝐑^{n+1}𝐑^{k+1}`$. Then there exists a nonsingular map $`f:𝐑^{n+1}\times 𝐑^{n+1}𝐑^{k+1}`$ having the following additional property: for any $`u𝐑^{n+1}`$, $`u0`$, the first coordinate of $`f(u,u)𝐑^{k+1}`$ is positive.

Proof. Given a nonsingular map $`𝐑^{n+1}\times 𝐑^{n+1}𝐑^{k+1}`$, consider the corresponding axial map $`g:\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$, see Lemma 10. The axial property implies that the restriction of $`g`$ onto the diagonal $`\mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$ is null-homotopic. Hence we may find $`g^{}g`$ such that $`g^{}:\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$ is constant along the diagonal. Now, consider the nonsingular map $`f:𝐑^{n+1}\times 𝐑^{n+1}𝐑^{k+1}`$ corresponding to $`g^{}`$ by Lemma 10. We see that for all $`u𝐑^{k+1}`$ the values $`f(u,u)𝐑^{k+1}`$ lie on a ray emanating from the origin. By performing an orthogonal rotation we may assume that all nonzero vectors of this ray have positive first coordinates. This proves our claim. $`\mathrm{}`$

## 6 The main results

###### Theorem 12

For any $`n`$, the number $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ coincides with the smallest integer $`k`$ such that there exists a nonsingular map $`𝐑^{n+1}\times 𝐑^{n+1}𝐑^k`$. Moreover, if $`n`$ is distinct from $`1,3,7`$, then $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ coincides with the smallest $`k`$ such that $`\mathrm{𝐑𝐏}^n`$ admits an immersion into $`𝐑^{k1}`$.

We derive from Theorem 12, Lemma 9 and (5) the following Corollary:

###### Corollary 13

For all $`n`$ distinct from $`1,3,7`$, one has $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)>n+1`$. The equality $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)=n+1`$ takes place if and only if $`n`$ equals $`1,3`$ or $`7`$.

The second statement follows from Lemma 9 and Propositions 17, 18 below.

Here is another Corollary:

###### Corollary 14

For any $`n`$, one has: $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)2n`$. If $`n`$ is a power of 2 then it is an equality, i.e.

$`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^{2^{r1}})=2^r.`$ (11)
Proof. By the Whitney theorem the projective space $`\mathrm{𝐑𝐏}^n`$ (for $`n>1`$) admits an immersion into $`𝐑^{2n1}`$, and the inequality follows (for $`n1,3,7`$) from Theorem 12. If $`n`$ is $`1,3`$ or $`7`$ the inequality also holds since then $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)=n+12n`$. The equality (11) is implied by Theorem 6. $`\mathrm{}`$

###### Corollary 15

If $`nn^{}`$ then $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n^{})`$.

The proof of the first statement of Theorem 12 for $`n1,3,7`$ follows by combining Propositions 16 and 17 (see below) with Lemma 9 and Corollary 5. The special cases $`n=1,3,7`$ are treated as follows: we have the inequality (5) and for these values of $`n`$ we may explicitly construct motion planners with $`n+1`$ local rules (see below) which gives $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)=n+1`$.

###### Proposition 16

For $`n>1`$, let $`k`$ be an integer such that the rank $`k`$ vector bundle $`k(\xi \xi )`$ over $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$ (see §4) admits a nowhere vanishing section. Then there exists a nonsingular map $`𝐑^{n+1}\times 𝐑^{n+1}𝐑^k`$.

###### Proposition 17

If there exists a nonsingular map $`𝐑^{n+1}\times 𝐑^{n+1}𝐑^k,`$ where $`n+1<k`$, then $`\mathrm{𝐑𝐏}^n`$ admits a motion planner with $`k`$ local rules, i.e.

$`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)k.`$ (12)
###### Proposition 18

For $`n=1,3,7`$ one has $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)=n+1`$.

The proofs of Propositions 16, 17 and 18 are postponed until the next section.

Propositions 16 and 17 also imply:

###### Corollary 19

The number $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ equals the Schwarz genus of the two-fold covering $`S^n\times _{𝐙_2}S^n\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$. It also coincides with the smallest $`k`$ such that the vector bundle $`k(\xi \xi )`$ over $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$ admits a nowhere zero section.

Two statements of Corollary 19 are clearly equivalent, see the arguments in the proof of Corollary 5.

The second statement of Theorem 12 is obtained by comparing its first statement with the following Theorem of J. Adem, S. Gitler and I.M. James and using the one-to-one correspondence between the axial maps and the nonsinglular maps which we have described above:

###### Theorem 20

(See ) There exists an immersion $`\mathrm{𝐑𝐏}^n𝐑^k`$ (where $`k>n`$) if and only if there exists am axial map $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n\mathrm{𝐑𝐏}^k`$.

R. J. Milgram  constructed, for any odd $`n`$, a nonsingular map

$$𝐑^{n+1}\times 𝐑^{n+1}𝐑^{2n+1\alpha (n)k(n)}.$$

Here $`\alpha (n)`$ denotes the number of ones in the dyadic expansion of $`n`$, and $`k(n)`$ is a non-negative function depending only on the mod (8) residue class of $`n`$ with $`k(1)=0`$, $`k(3)=k(5)=1`$ and $`k(7)=4`$.

Applying Proposition 17 we obtain the following estimate:

###### Corollary 21

For any odd $`n`$ one has

$$\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)2n+1\alpha (n)k(n).$$

$`\mathrm{}`$

Using the table from  and our Theorem 12, one finds the topological complexity of $`\mathrm{𝐑𝐏}^n`$ for all $`n23`$:

| $`n`$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ | 2 | 4 | 4 | 8 | 8 | 8 | 8 | 16 | 16 | 17 | 17 | 19 |

| $`n`$ | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)`$ | 23 | 23 | 23 | 32 | 32 | 33 | 33 | 35 | 39 | 39 | 39 |

## 7 Proofs of Propositions 16, 17 and 18

Proof of Proposition 16. Note that the canonical bundle $`\xi `$ over $`\mathrm{𝐑𝐏}^n`$ can be represented as the projection $`S^n\times _{𝐙_2}𝐑S^n/𝐙_2`$. Here $`𝐙_2`$ acts as the antipodal involution on $`S^n`$ and by $`xx`$ on $`𝐑`$. Hence the bundle $`k(\xi \xi )`$ can be represented as the projection

$$(S^n\times S^n)\times _G𝐑^k(S^n\times S^n)/G,$$

where $`G`$ denotes $`𝐙_2𝐙_2`$ acting as two antipodal involutions on $`S^n\times S^n`$ with each summand $`𝐙_2`$ acting as $`xx`$ on $`𝐑^k`$. Consider the following commutative diagram

$`\begin{array}{ccc}S^n\times S^n\times 𝐑^k& \underset{q_1}{}& (S^n\times S^n\times 𝐑^k)/G=E(k(\xi \xi ))\\ & & \\ p_1& & p_2\\ & & \\ S^n\times S^n& \stackrel{q_2}{}& (S^n\times S^n)/G=\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n.\end{array}`$
Then $`q_1`$ and $`q_2`$ are regular $`G`$-covers, $`p_1`$ is the trivial $`k`$-plane bundle and $`p_2`$ can be identified with the bundle $`k(\xi \xi )`$.

Any continuous section $`s:\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^nE(k(\xi \xi ))`$ of $`p_2`$ determines a continuous map $`s_1:S^n\times S^nE(k(\xi \times \xi ))`$ which is invariant under $`G`$, i.e. $`s_1(g(x,y))=s_1(x,y)`$ for any $`gG`$. Since $`n>1`$ the space $`S^n\times S^n`$ is simply connected and so $`s_1`$ can be lifted into the covering $`q_1`$, which gives a continuous map $`s_2:S^n\times S^nS^n\times S^n\times 𝐑^k`$. The lift $`s_2`$ is not unique (there are exactly four lifts) but there is a unique lift $`\stackrel{~}{s}_2`$ having an additional property $`p_1\stackrel{~}{s}_2=\mathrm{id}`$, i.e. $`\stackrel{~}{s}_2`$ is a section of the trivial bundle $`p_1`$. Then it is easy to see that for any $`gG`$ one has $`g\stackrel{~}{s}_2=\stackrel{~}{s}_2g`$, i.e. $`\stackrel{~}{s}_2`$ is equivariant.

Let $`f:S^n\times S^n𝐑^k\{0\}`$ be the projection of $`s_2`$ onto $`𝐑^k`$. In other words, $`s_2(x,y)=(x,y,f(x,y))`$ for $`x,yS^n`$. The result is never zero since the section $`s`$ assumes no zero values. We have $`f(x,y)=f(x,y)=f(x,y)`$ for all $`x,yS^n`$. Hence $`f`$ determines a nonsingular map $`g:𝐑^{n+1}\times 𝐑^{n+1}𝐑^k`$ given by

$$g(x,y)=f(\frac{x}{|x|},\frac{y}{|y|}),x,y𝐑^{n+1}.$$

$`\mathrm{}`$

Proof of Proposition 17. We start with the following observation. Let $`\varphi :𝐑^{n+1}\times 𝐑^{n+1}𝐑`$ be a scalar continuous map such that $`\varphi (\lambda u,\mu v)=\lambda \mu \varphi (u,v)`$ for all $`u,vV`$ and $`\lambda ,\mu 𝐑`$. Let $`U_\varphi \mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$ denote the set of all pairs $`(A,B)`$ of lines in $`𝐑^{n+1}`$ such that $`AB`$ and $`\varphi (u,v)0`$ for some points $`uA`$ and $`vB`$. It is clear that $`U_\varphi `$ is open. We claim that there exists a continuous motion planning strategy over $`U_\varphi `$, i.e. there is a continuous map $`s`$ defined on $`U_\varphi `$ with values in the space of continuous paths in the projective space $`\mathrm{𝐑𝐏}^n`$ such that for any pair $`(A,B)U_\varphi `$ the path $`s(A,B)(t)`$, $`t[0,1]`$, starts at $`A`$ and ends at $`B`$. We may find unit vectors $`uA`$ and $`vB`$ such that $`\varphi (u,v)>0`$. Such pair $`u,v`$ is not unique: instead of $`u,v`$ we may take $`u,v`$. Note that both pairs $`u,v`$ and $`u,v`$ determine the same orientation of the plane spanned by $`A,B`$. The desired motion planning map $`s`$ consists in rotating $`A`$ toward $`B`$ in this plane, in the positive direction determined by the orientation.

Assume now additionally that $`\varphi :𝐑^{n+1}\times 𝐑^{n+1}𝐑`$ is positive in the following sense: for any $`u𝐑^{n+1}`$, $`u0`$, one has $`\varphi (u,u)>0`$. Then instead of $`U_\varphi `$ we may take a slightly larger set $`U_\varphi ^{}\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$, which is defined as the set of all pairs of lines $`(A,B)`$ in $`𝐑^{n+1}`$ such that $`\varphi (u,v)0`$ for some $`uA`$ and $`vB`$. Now all pairs of lines of the form $`(A,A)`$ belong to $`U_\varphi ^{}`$. Then for $`AB`$ the path from $`A`$ to $`B`$ is defined as above (rotating $`A`$ toward $`B`$ in the plane, spanned by $`A`$ and $`B`$, in the positive direction determined by the orientation), and for $`A=B`$ we choose the constant path at $`A`$. Continuity is not violated.

A vector-valued nonsingular map $`f:𝐑^{n+1}\times 𝐑^{n+1}𝐑^k`$ determines $`k`$ scalar maps $`\varphi _1,\mathrm{},\varphi _k:𝐑^{n+1}\times 𝐑^{n+1}𝐑`$ (the coordinates) and the described above neighborhoods $`U_{\varphi _i}`$ cover the product $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$ minus the diagonal. Since $`n+1<k`$ we may use Lemma 11. Hence we may replace the initial nonsingular map by such an $`f`$ that for any $`u𝐑^{n+1}`$, $`u0`$, the first coordinate $`\varphi _1(u,u)`$ of $`f(u,u)`$ is positive. The open sets $`U_{\varphi _1}^{},U_{\varphi _2},\mathrm{},U_{\varphi _k}`$ cover $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$. We have described explicit motion planning strategies over each of these sets. Therefore $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)k`$. $`\mathrm{}`$

Proof of Proposition 18. The upper bound $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)n+1`$ follows similarly to the proof of Proposition 17 and using the nonsingular maps $`𝐑^{n+1}\times 𝐑^{n+1}𝐑^{n+1}`$ of Lemma 8. The lower bound $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)n+1`$ is completely general, see (5). $`\mathrm{}`$

## 8 Motion planners and immersions

The following Theorem 22 is a part of Theorem 12. However in its proof we give a direct construction, starting from an immersion $`\mathrm{𝐑𝐏}^n𝐑^k`$, of an open covering $`\{U_i\}`$ of $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$ with continuous motion planning strategies $`s_i`$ over each open set $`U_i`$.

###### Theorem 22

Suppose that the projective space $`\mathrm{𝐑𝐏}^n`$ can be immersed into $`𝐑^k`$. Then $`\mathrm{𝐓𝐂}(\mathrm{𝐑𝐏}^n)k+1.`$

Proof. Imagine $`\mathrm{𝐑𝐏}^n`$ being immersed into $`𝐑^k`$. Fix a frame in $`𝐑^k`$ and extend it, by parallel translation, to a continuous field of frames. Projecting orthogonally onto $`\mathrm{𝐑𝐏}^n`$, we find $`k`$ continuous tangent vector fields $`v_1,v_2,\mathrm{},v_k`$ on $`\mathrm{𝐑𝐏}^n`$ such that the vectors $`v_i(p)`$ (where $`i=1,2,\mathrm{},k`$) span the tangent space $`T_p(\mathrm{𝐑𝐏}^n)`$ for any $`p\mathrm{𝐑𝐏}^n`$.

Let $`U_0\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$ denote the set of pairs of lines $`(A,B)`$ in $`𝐑^{n+1}`$ making an acute angle.

A nonzero tangent vector $`v`$ to the projective space $`\mathrm{𝐑𝐏}^n`$ at a point $`A`$ (which we understand as a line in $`𝐑^{n+1}`$) determines a line $`\widehat{v}`$ in $`𝐑^{n+1}`$, which is orthogonal to $`A`$, i.e. $`\widehat{v}A`$. The vector $`v`$ also determines an orientation of the two-dimensional plane spanned by the lines $`A`$ and $`\widehat{v}`$.

For $`i=1,2,\mathrm{},k`$ let $`U_i\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$ denote the open set of all pairs of lines $`(A,B)`$ in $`𝐑^{n+1}`$ such that the vector $`v_i(A)`$ is nonzero and the line $`B`$ makes an acute angle with the line $`\widehat{v_i(A)}`$.

The sets $`U_0,U_1,\mathrm{},U_k`$ cover $`\mathrm{𝐑𝐏}^n\times \mathrm{𝐑𝐏}^n`$. Indeed, given a pair $`(A,B)`$, there exist indices $`1i_1<\mathrm{}<i_nk`$ such that the vectors $`v_{i_r}(A)`$, where $`r=1,\mathrm{},n`$, span the tangent space $`T_A(\mathrm{𝐑𝐏}^n)`$. Then the lines

$$A,\widehat{v_{i_1}(A)},\mathrm{},\widehat{v_{i_n}(A)}$$

span the Euclidean space $`𝐑^{n+1}`$ and therefore the line $`B`$ makes an acute angle with one of these lines. Hence, $`(A,B)`$ belongs to one of the sets $`U_0,U_{i_1},\mathrm{},U_{i_k}`$.

Now we want to describe a continuous motion planning strategy over each set $`U_i`$, where $`i=0,1,\mathrm{},k`$. First we define it over $`U_0`$. Given a pair $`(A,B)U_0`$, we rotate $`A`$ towards $`B`$ with constant velocity in the two-dimensional plane spanned by $`A`$ and $`B`$ so that $`A`$ sweeps the acute angle. This clearly defines a continuous motion planning section $`s_0:U_0P(\mathrm{𝐑𝐏}^n)`$. Our continuous motion planning strategy $`s_i:U_iP(\mathrm{𝐑𝐏}^n)`$, where $`i=1,2,\mathrm{},k`$, is a composition of two motions: first we rotate line $`A`$ toward the line $`\widehat{v_i(A)}`$ in the in the 2-dimensional plane spanned by $`A`$ and $`\widehat{v_i(A)}`$ in the direction determined by the orientation of this plane (see above). On the second step we rotate the line $`\widehat{v_i(A)}`$ towards $`B`$ along the acute angle similarly to the action of $`s_0`$. $`\mathrm{}`$

The inverse statement of Theorem 12, allowing to construct an immersion $`\mathrm{𝐑𝐏}^n𝐑^{k1}`$ starting from a motion planner for $`\mathrm{𝐑𝐏}^n`$, is not very explicit; it is based on a long chain of constructions: Theorem 3, Corollary 5, Proposition 16, and then Theorem of J. Adem, S. Gitler, I.M. James .

## 9 Motion planners in $`\mathrm{𝐑𝐏}^n`$ with $`n7`$

Let us describe explicitly a motion planner in $`\mathrm{𝐑𝐏}^2`$ which may be used to solve the task of moving a line through the origin in $`𝐑^3`$.

We may view $`𝐑^3`$ as embedded into $`𝐑^4`$ (the set of quaternions) via the map $`(x_1,x_2,x_3)x_1+x_2i+x_3j`$, where $`i,j,k𝐑^4`$ are the imaginary units. Restricting the nonsingular map $`𝐑^4\times 𝐑^4𝐑^4`$ onto $`𝐑^3𝐑^4`$ we obtain a nonsingular map $`f:𝐑^3\times 𝐑^3𝐑^4`$. Explicitly it is given by the formula

$$f(x,y)=x,y\left|\begin{array}{cc}x_1& x_2\\ y_1& y_2\end{array}\right|i\left|\begin{array}{cc}x_1& x_3\\ y_1& y_3\end{array}\right|j\left|\begin{array}{cc}x_2& x_3\\ y_2& y_3\end{array}\right|k,$$

where $`x=(x_1,x_2,x_3)`$ and $`y=(y_1,y_2,y_3)`$ and $`x,y`$ denotes the scalar product of $`x`$ and $`y`$. Repeating the construction given in the proof of Proposition 17 we obtain 4 open subsets $`U_1,U_2,U_3,U_4`$ of $`\mathrm{𝐑𝐏}^2\times \mathrm{𝐑𝐏}^2`$, covering the product $`\mathrm{𝐑𝐏}^2\times \mathrm{𝐑𝐏}^2`$. Each $`U_\alpha `$, where $`\alpha =1,2,3,4`$, corresponds to the scalar pairing $`\varphi _\alpha `$ obtained from $`f`$ by considering only the $`\alpha `$-th coordinate:

$$f(x,y)=\varphi _1(x,y)+\varphi _2(x,y)i+\varphi _3(x,y)j+\varphi _4(x,y)k$$

The set $`U_1`$ consists of the pairs of lines in $`𝐑^3`$ making an acute angle. The set $`U_2`$ consists of pairs of lines in $`𝐑^3`$ such that their projections onto the $`x_1x_2`$-plane span this plane. $`U_3`$ and $`U_4`$ are defined similarly with the $`x_1x_2`$-plane replaced by the $`x_2x_3`$-plane and $`x_1x_3`$-plane, correspondingly.

Each functionals $`\varphi _\alpha `$ defines a continuous motion planning strategy over the set $`U_\alpha `$, see proof of Proposition 17. For example, the motion planning strategy over $`U_1`$ is obvious: if lines $`A`$ and $`B`$ make an acute angle we rotate $`A`$ towards $`B`$ in the 2-plane spanned by $`A`$ and $`B`$, so that $`A`$ sweeps the acute angle. If $`A=B`$ then $`A`$ stays fixed.

A continuous motion planning strategy over the set $`U_2`$ can be described as follows. Let $`A`$ and $`B`$ be two lines in $`𝐑^3`$ so that their projections onto the $`x_1x_2`$-plane span this plane. Fix an orientation of the $`x_1x_2`$-plane. For any pair $`(A,B)U_2`$ we obtain an orientation of the 2-plane spanned by $`A`$ and $`B`$. Then we rotate $`A`$ towards $`B`$ in this 2-plane in the direction of the orientation.

Over the sets $`U_3`$ and $`U_4`$ we act similarly.

This example illustrates how one may use the nonsingular maps of Lemma 8 to construct explicitly motion planners in projective spaces $`\mathrm{𝐑𝐏}^n`$ with $`n7`$. We skip the details.

Notice that $`\mathrm{𝐑𝐏}^3`$ is homeomorphic to the Lie group $`\mathrm{SO}(3)`$, the configuration space of the rigid body, fixed at a point in 3-space. The topological complexity of this problem was computed earlier in §8 of .

The immersion theory of projective spaces provides a rich variety of quite sophisticated nonsingular maps (see, for example, , ) which may be used to build, similarly to the above construction, explicit motion planners on higher dimensional projective spaces $`\mathrm{𝐑𝐏}^n`$.


format: text

text:
# Detection of small scale fluctuations in the near-IR cosmic infrared background from long exposure 2MASS fields

## Abstract

We report first results for the cosmic infrared background (CIB) fluctuations at 1.25, 1.65 and 2.17 $`\mu `$m obtained from long exposures constructed from 2MASS standard star fields. We have co-added and analyzed scans from one such field with a total exposure time $`>`$ 1 hour, and removed sources and other artifacts. The stars and galaxies were clipped out to K$`{}_{s}{}^{}`$19m leaving only high-$`z`$ galaxies (or possibly local low-surface-brightness systems). The residual component of the diffuse emission on scales from a few arc-sec to a few arc-min has a power-law slope consistent with emission produced by clustered galaxies. The noise (and residual artifacts) contribution to the signal is small and the colors of the signal are very different from Galactic stars or air-glow. We therefore identify the signal as CIB fluctuations from the faint unresolved galaxies. We show that the present-day galaxies with no evolution would produce a significant deficit in the observed CIB fluctuations. Thus the dominant contribution to the observed signal must come from high $`z`$ and may indicate high rates of star formation at those epochs.

Cosmology: observations - cosmology: diffuse radiation - cosmology: large-scale structure of Universe - galaxies: evolution

1. Introduction

The near-IR cosmic infrared background (CIB) ($`\lambda \genfrac{}{}{0pt}{}{_<}{^{}}3\mu `$m) arises mainly from the stellar component of galaxies and probes galactic star formation and evolution at early times. The recent surprising, and mutually consistent, discoveries of the near-IR CIB from the COBE/DIRBE and Japan’s IRTS datasets (see Hauser & Dwek 2001 for review) indicated the large amplitude of both the CIB fluctuations (Kashlinsky & Odenwald 2000a - hereafter KO, Matsumoto et al 2000,2002) and DC levels (Dwek & Arendt 1998, Gorjian & Wright 2000, Wright & Reese 2000, Cambresy et al 2001). It is hard to explain these measurements by the observed galaxy populations; e.g. at 2.2 $`\mu `$m (K band), the faintest observed galaxies give only 30-40% of the observed CIB (Kashlinsky & Odenwald 2000b, Madau & Pozzetti 2000). If these detections are true, and barring the possible existence of local undetected low surface brightness galaxies, the deficit CIB must come from fainter galaxies at high $`z`$ and inaccessible to telescopic studies until the launch of NGST.

In this Letter we report the first detection of small angular scale fluctuations in the near-IR CIB. We used long integration data constructed from 2MASS 222 This publication makes use of data products from the Two Micron All Sky Survey, which is a joint project of the University of Massachusetts and the Infrared Processing and Analysis Center/California Institute of Technology, funded by the National Aeronautics and Space Administration and the National Science Foundation. observations of one standard star field (SSF) with a total exposure $`\genfrac{}{}{0pt}{}{_>}{^{}}`$1 hour. The images were co-added to produce a $`8.6^{}\times 1^{}`$ field from which we removed resolved sources (both stars and distant galaxies) and other artifacts as described in Sec.2 and in more detail in the companion paper (Odenwald, Kashlinsky, Mather, Skrutskie & Cutri 2002 - OKMSC). We then computed the fluctuation spectrum of the residual diffuse emission; its slope in the co-added images is consistent with that of galaxy clustering. We estimated the contributions to the power spectrum from atmospheric fluctuations (AF), remaining Galactic stars (GS) and cirrus emission, zodiacal light (ZL), instrument noise (IN) and extinction. These components have different slopes and negligible amplitudes compared to the detected signal, suggesting that the diffuse component fluctuations in the final image are dominated by the CIB. If this identification is correct, the levels of the CIB from remaining faint (K$`{}_{s}{}^{}>`$18.5m-19m), and likely high-$`z`$, galaxies may imply significant star formation at early times.

2. Data analysis

2MASS conducted measurements with a 3-band camera observing the sky simultaneously at J, H and Ks (1.25, 1.65 and 2.17 $`\mu `$m). The 2MASS Atlas images have 7.8 sec exposure per pixel and are interpolated with 1′′ pixels. Our selected SSF, 90565, centered on the star P565-C has Galactic and Ecliptic coordinates (243$`{}_{}{}^{},27^{}`$) and ($`21^{},35^{}`$) respectively. The data analyzed here consisted of 2080 calibrated 8.6$`{}_{}{}^{}\times `$15 images covering an $`8.6^{}\times 1^{}`$ swath oriented north-south, obtained during observations at CTIO between Apr and Aug 1998. Calibration, co-adding and other details are given in the companion OKMSC paper. The final image had a total exposure $``$3,700 secs and the field was divided into seven square patches $`512^{\prime \prime }`$ on the side.

In each patch, individual stars and galaxies were removed by an iterative procedure where each pixel with surface brightness exceeding 3 standard deviations for the patch was excised along with 8 neighboring pixels. We computed the integrated magnitude limits of the removed sources from the surface brightness threshold. The peak surface brightness of unresolved sources was measured to be +2.5m fainter than the corresponding integrated flux reflecting the part of the beam response function within the central 1′′ 2MASS pixel. Because of the variation in background level and associated noise, the patches were clipped to different point source absolute flux levels. In Ks band these vary from 18.5m to 19m.

The clipping left $`>`$90% of the pixels in the patches, which provided a good basis for a Fourier analysis of the diffuse light. Each patch was Fourier transformed with pixels weighted by the number of observations. The final results are the same without the weighting. The blanked out pixels were assigned flux fluctuation $`\delta F(\stackrel{}{\theta })`$=0; i.e. no power is added to the diffuse light emission. After the initial FT of the clipped data, we removed the occasional stripe artifacts from diffraction and array row saturation by bright stars. These features produce excess power concentrated along each Fourier space axis. The stripes were handled by removing a narrow strip of pixels (2 pixels sufficed in practice) in the Fourier plane along each axis. The final 3-band color images can be viewed at http://www.gsfc.nasa.gov/gsfc/spacesci/pictures/2mass/2mass.jpg.

The clipped de-striped data have a very different distribution than AF. Fig. 1 shows $`\sqrt{q^2P(q)/2\pi }`$, a typical fluctuation on angular scale $`\theta \pi /q`$. The power spectra follow a power law $`P(q)q^n`$ with $`n1`$, as expected from sources clustered like galaxies. For a single standard exposure (7.8 sec) the diffuse emission of the clipped patches has white noise power spectrum from remaining GS and AF multiplied by the Gaussian beam of $`2.5^{\prime \prime }`$ FWHM. The variance of the clipped maps decreases $``$1/$`t`$ as expected for AF and the plotted power spectrum of AF in the final images was computed from the 7.8 sec image and rescaled to the total exposure time. AF have a white noise distribution ($`\sqrt{q^2P(q)/2\pi }q`$) and on the beam scale are typically $``$20 nWm-2sr-1 . The long exposure non-clipped patches also have a white noise power spectrum from GS and AF.

3. Fluctuations from CIB compared to other terms

The non-cosmological contributions to the final $`P(q)`$ are small and are as follows:

$``$ Instrument noise: This was estimated from difference maps for time-ordered string of measurements, each 7.8 sec long, in which alternating even and odd images are subtracted. The difference maps show a near white-noise power spectrum and the fluctuation in the difference map patches is $`<`$10% of the clipped co-added map. This means that the IN and time-dependent AF are small and in addition have a different power spectrum than the detected signal. To check for stray light effects, we selected from the standard 2MASS product at 7.8 sec exposure per pixel several regions in the Galactic plane with comparable number of stars to our field and processed these with the same clipping algorithm. The clipped power spectra are almost perfectly flat suggesting that stray light does not explain the slopes of our measured fluctuation power spectra.

$``$ Zodiacal light: Our field is above the asteroidal bands so only very small fluctuations in the ZL are expected (Kelsall et al 1998). Studies of the ZL arcminute-scale structure (Abraham et al 1998) with the ISO/ISOPHOT show that at 25$`\mu `$m no structure can be detected above 0.2% of the total ZL brightness. The 2MASS observations span a period from April to August and a solar elongation range from $`115^{}`$ to $`128^{}`$, so any persistent ZL structure would become uncorrelated during the data averaging process. The DIRBE based ZL model (Kelsall et al 1998) at Solar elongation of 120gives the mean ZL intensity of 136 nWm-2sr-1 in Ks band and 400 nWm-2sr-1 in J band. Based on the limit set by the structure at 25 $`\mu `$m we expect that ZL structure will contribute flux fluctuation $`<`$0.3 nWm-2sr-1 on arc-minute scales in the 2MASS bands.

$``$ Remaining Galactic stars: GS brighter than $`m_{\mathrm{cut}}(K_s)`$18.5-19m were clipped out. Non-clipped patches show that GS have a white noise spatial distribution, so over the 2MASS beam $`\omega _{\mathrm{beam}}`$ the flux fluctuation, $`\sigma _{}`$, from remaining GS is $`\sigma _{}^2`$=$`\omega _{\mathrm{beam}}^1_{m_{\mathrm{cut}}}^{\mathrm{}}F_\nu ^2(m)n(m)𝑑m`$, where $`n(m)dm`$ is the number of GS within $`dm`$ and $`F_\nu (m)`$=$`F_{\nu ,0}10^{0.4m}`$ is the flux density of a star of magnitude $`m`$. Using the DIRBE based Galaxy Faint Source Model (Arendt et al 1998) normalized to 2MASS we find that GS fainter than $`m_{\mathrm{cut}}`$18.5 contribute $`\sigma _{}<`$9 nWm-2sr-1 . This component adds in quadrature to the total dispersion, contributing $`\genfrac{}{}{0pt}{}{_<}{^{}}`$5 % of the total signal in Fig. 1. Stars are not clipped out completely and we checked by increasing the clipping mask size and using other clipping methods, that residual stellar artifacts do not mimic the observed signal.

$``$ Galactic cirrus: From COBE/DIRBE data Arendt et al (1998, Table 4) estimate that the cirrus flux at 3.5 $`\mu `$m is $``$5% of that at 100 $`\mu `$m. KO find the fluctuation in the DIRBE maps with 0.3o pixels in the (mainly) cirrus emission at 100 $`\mu `$m in the direction of P565-C to be $`<`$10 nWm-2sr-1 (see their Fig.22). Wright (1998) and KO show that the DIRBE data on the Galactic cirrus spatial distribution give a spectral index $`n2`$, consistent with the IRAS analysis of Gautier et al (1992), but very different from the slope of the signal we detect in the final co-adds. Combining these results and assuming the 3.5 $`\mu `$m flux to represent an upper limit on the emission at shorter 2MASS wavelengths gives $`\sigma _{\mathrm{cirrus}}`$ well below 1 nWm-2sr-1 .

$``$ Galactic extinction: The amount of extinction varies strongly with wavelength: the strongest fluctuations caused by a clumpy interstellar medium would occur in J-band, and with declining strength in H and Ks bands. No such wavelength-dependent variation in the power spectra in Fig. 1 is apparent. Furthermore, at Ks band, the DIRBE based models for the amount of interstellar extinction in the near-IR indicate $`A0.05^m`$ (Arendt et al 1998) and a differential extinction across our $`1^{}`$ field of $`0.005^m`$. This corresponds to an intensity gradient of 0.5% at the $`1^{}`$-scale or less than about 0.3 nWm-2sr-1 contribution to the total dispersion.

$``$ Atmospheric fluctuations: Stationary AF (or gradients) should correlate with the air column density along the line-of-sight. If important, these effects would introduce airmass-dependent correlations into the data during the five months of observations. We computed the flux dispersion in the individual scans finding no statistically significant correlation between the airmass and the flux dispersion. AF dominate the diffuse emission for 7.8 sec images and integrate down $`t^1`$, contributing a small fraction to the overall fluctuations (Fig. 1).

$``$ Color: in Fig. 2a the colors of the diffuse signal in the final images are compared with those of the 2MASS stars, the present day galaxies and the atmosphere. The various foreground components and the nearby galaxies have different colors from the signal in Fig. 1.

This discussion suggests that the CIB is the most likely source of the signal in Fig. 1. The largest angular scales probed here correspond to $`<`$1$`h^1`$Mpc where galaxy clustering is non-linear and the slope of the power spectrum is consistent with that from galaxy clustering.

4. Discussion

Assuming that the fluctuations in Fig. 1 are from the CIB, can they be produced by the observed non-evolving galaxy populations, or do they require high $`z`$ evolution? The CIB flux from evolving galaxies is given by $`\frac{dF}{dz}`$=$`\frac{c}{4\pi }\frac{dt}{dz}\frac{_\nu (\nu (1+z),z)}{1+z}`$, where $`_\nu `$ is the co-moving luminosity density from galaxies. As in Yoshii & Takahara (1988) we separate the $`z`$-dependence in $`_\nu (z)`$ into terms due to K-correction ($`𝒦_\nu `$), pure luminosity evolution ($`_\nu `$) and pure number density evolution ($`𝒩_\nu `$), i.e. $`_\nu (z)`$=$`10^{0.4[𝒦_\nu (z)+_\nu (z)+𝒩_\nu (z)]}_\nu (0)`$. We use the K-band for quantitative estimates and consider for now only the K-correction effects from the observed galaxies. The K-correction was taken from Fig. 1 of JK99. The luminosity density was normalized at $`z`$=0 using the present-day K-band luminosity function (Gardner et al 1997; Loveday 2000). At small angles, the CIB power spectrum is related to $`dF/dz`$ and the evolving 3-D power spectrum of galaxy clustering, $`P_3(k)`$ via (e.g. KO) $`P(q)`$=$`_0^{\mathrm{}}\left(\frac{dF}{dz}\right)^2\frac{1}{c\frac{dt}{dz}d_A^2(z)}P_3(qd_A^1(z);z)𝑑z`$, where $`d_A(z)`$ is the angular diameter distance.

Fig. 2b shows that the total CIB from the observed galaxies (K$`\genfrac{}{}{0pt}{}{_<}{^{}}`$24) is $``$8-10 nWm-2sr-1 (Gardner 1996, Madau & Pozzetti 2000, Kashlinsky & Odenwald 2000b), a factor of 2-3 smaller than the CIB levels of $`F_{\mathrm{K},\mathrm{total}}`$25 nWm-2sr-1 (Matsumoto et al 2000,2002, Gorjian & Wright 2000, Wright & Reese 2000). The deficit is similarly large at 1.25 $`\mu `$m (Cambresy et al 2001) and 3.5 $`\mu `$m (Dwek & Arendt 1998) and in the $``$degree scale fluctuation analysis of DIRBE data (KO). The vertical lines show the limiting K magnitude, $`\mathrm{K}_{\mathrm{cut}}`$ of excised galaxies. At $`z`$=1, the angular scale of $`1\text{.}^{\prime \prime }`$ subtends 10-15$`h^1`$Kpc, depending on cosmological parameters, so distant galaxies should have been excised almost completely by our clipping method. Galaxies up to the clipping threshold contribute only $``$5 nWm-2sr-1 to the total CIB. Hence, if the detections of the CIB are true the bulk of the flux must be emitted by much fainter galaxies.

Fig. 2c shows the rate of CIB production, $`dF/dz`$, assuming only non-evolving galaxies that were clipped out to $`\mathrm{K}_{\mathrm{cut}}`$. The K-correction is from Fig. 1 of JK99 and no-evolution is a fair assumption for the low-$`z`$ part of the figure (De Propis et al 1999). Because the brighter galaxies are removed, the bulk of the remaining CIB comes from high $`z`$ probing galaxies at early times. For comparison the median observed redshift of K$`19^m`$ galaxies is $`z`$0.7-0.8 (Cowie et al 1996). We assume that all faint galaxies are described by a Schechter-type luminosity function and hence are located at cosmological redshifts, but a possibility exists that at least some of the very faint galaxies are local low-surface brightness systems that can not be detected with the current techniques. From the K-correction evolution only for $`(\mathrm{\Omega },\mathrm{\Omega }_\mathrm{\Lambda })`$=(0.3,0.7),(1, 0) and (0.3,0) we get that the total flux for 24$`>`$K$`>`$19 is 3.7, 2.1 and 2.8 nWm-2sr-1 which compares well with Fig. 2b. Far-IR CIB studies from ISO also suggest strong evolution of high-$`z`$ galaxy populations (Elbaz et al. 1999, Dole et al 2001). Hence, if the DC measurements of the K-band CIB are correct, the excess flux must come from fainter and evolving galaxies likely at higher $`z`$.

Fig. 2d shows the fluctuation at $`1^{\prime \prime }`$ vs the magnitude $`m_{\mathrm{cut}}`$ of the clipped galaxies for the 2MASS bands. Because clipping was done before de-striping the value of $`\sigma `$ shown is before de-striping. The high numbers for $`P(q)`$ are consistent with other findings (KO, Matsumoto et al 2002) after accounting for the beam difference and the fact that in the large-beam DIRBE and IRTS studies no galaxies were removed. Fig. 1 shows the power spectrum of the diffuse CIB from IRTS (Matsumoto et al 2002) and the open diamond with error bar shows the fluctuation at $`0.5^{}`$ from the COBE DIRBE data (KO). The contribution from galaxies clipped out to Ks=18.5m can be estimated from the JK99 modeling and gives $`\delta F_{\mathrm{rms}}`$(2-3), (1-1.5) nWm-2sr-1 in J, K bands. When added to the 2MASS numbers extrapolated to the appropriate angular scale using the slope of Patch 2 this gives the total (J,K) CIB fluctuation at $`0.5^{}`$ of $``$(10-12, 2.5-3) nWm-2sr-1 consistent with the KO results. The largest angular scales probed by our analysis after de-striping are $`\pi /q1.5^{}`$ which at $`z`$=1 corresponds to $``$1$`h^1`$Mpc, where galaxy clustering is non-linear. Hence in Fig. 2d we evaluated the expected CIB fluctuations assuming only K-correction evolution and two extremes of galaxy clustering evolution: clustering stable in proper (thick solid line) and co-moving coordinates. The numbers are for $`(\mathrm{\Omega },\mathrm{\Omega }_\mathrm{\Lambda })`$=(0.3,0.7), but models with $`\mathrm{\Omega }_\mathrm{\Lambda }`$=0 would give smaller numbers. The deficit in the amplitude of the CIB fluctuation is of a similar factor as the DC component and likely implies strong galaxy evolution at high $`z`$.

The slope of the detected power spectrum depends on the magnitude cutoff as shown in Fig. 2e. If progressively fainter galaxies are removed the slope of the power spectrum flattens. This is consistent with fainter galaxies being at higher $`z`$ when the clustering pattern was less evolved. The slope of this dependence is similar in all three bands. The power spectrum of the present-day galaxy clustering on non-linear scales has $`n`$–1.3 (Groth & Peebles 1974, Maddox et al 1990), so it would appear that the J band patch with the lowest $`m_{\mathrm{cut}}`$ probes smaller $`z`$. In CDM models the non-linear power spectrum of galaxy clustering evolves toward steeper slope (higher $`|n|`$) at low $`z`$. This is consistent with the trend in Fig. 2d and it appears that H and K bands probe the farthest galaxy populations. This is supported by the colors: the solid line in Fig. 2a shows the evolution due to K-correction alone (with spectra from JK99) and assuming that all CIB fluctuations in all three bands are dominated by galaxies at the same $`z`$, in which case the colors would become bluer contrary to our observations. A simple way to make the color redder, shown with the filled circle in Fig. 2a, is if different bands, clipped to their respective $`m_{\mathrm{cut}}`$, probe different $`z`$ with K band probing the earliest times.

We thank Rick Arendt for fruitful discussions and comments on the manuscript.

REFERENCES
Abraham, P. et a. 1998,in ‘The Universe as seen by ISO’, eds. P. Cox & M.F. Kessler,pp 145-148.
Arendt, R. et al 1998,Ap.J., 508, 74
Cambresy, L. 2001,Ap.J.,555,563
Cowie, L. et al. 1996, AJ,112,839
Cutri, R.M. (IPAC/Caltech), Skrutskie, M.F. (UMASS), et al (IPAC/Caltech) http://www.ipac.caltech.edu/2mass/releases/second/doc/explsup.html
De Propis et al 1999, Ap.J.,118,719
Djorgovski, S. et al 1995, Ap.J., 438, L13
Dole, H. et al 2001, A & A, 372,364
Dwek, E. & Arendt, R. 1998,Ap.J.,508,L9
Elbaz, D. et al 1999, A & A, 351, L37
Gardner, J. 1996, in “Unveiling the cosmic infrared background”, ed. E. Dwek, p. 127
Gardner, J.P. 1997, Ap.J.,480,L99
Gautier, D. 1992,AJ,103,1313
Gorjian, V., Wright, E.L. & Chary, R.R. 2000,Ap.J.,536,550
Groth, E. & Peebles, P.J.E. 1977,Ap.J.,217,385
Hauser, M. & Dwek, E. 2001,ARAA,39,249
Jimenez, R. & Kashlinsky, A. 1999,Ap.J.,511,16 (JK99)
Kashlinsky & Odenwald 2000a, Ap.J., 528, 74
Kashlinsky & Odenwald 2000b, Science, 289,246
Kelsall, T. et al 1998,Ap.J.,508,44
Loveday, J. 2000,MNRAS,312,L281
Madau, P. & Pozzetti, L. 2000,MNRAS,312,L9
Matsumoto, M. et al 2000,in “ISO surveys of a dusty Universe”, eds. Lemke, D. et al. p.96.
Matsumoto, M. et al 2002, Ap.J., submitted.
Odenwald, Kashlinsky, Mather, Skrutskie and Cutri 2002, Ap.J.,submitted - OKMSC
Wright, E.L. 1998,Ap.J.,496,1
Wright, E.L. & Reese, E.D. 2000,Ap.J.,545,43
Yoshii, Y. & Takahara, F. 1988,Ap.J.,326,1

FIGURE CAPTIONS

Fig. 1 - The power spectrum of the diffuse emission in the final images is shown with crosses with errors. Patch number is shown in the upper left corner of the top panels. The number in the upper right corner of each panels shows the final $`\sigma `$ after de-striping. Open diamonds with 92% errors show the fluctuation on larger angular scale from KO analysis of COBE DIRBE data. Thick solid line shows the CIB result from IRTS analysis (Matsumoto et al 2002). Filled small diamonds show the atmospheric contribution evaluated from 7.8 sec exposure and divided by the average number of co-adds in the patch. The number in the lower right corner gives the limiting magnitude for removing sources from the clipped patch.

Fig. 2 - (a) H–K vs J–K colors. Crosses correspond to fluctuations in the final 2MASS images shown in Fig. 1. Square is the color of the atmosphere. Ellipse corresponds to the locus of $`10^5`$ high latitude Galactic field stars from 2MASS data. Plus denotes the position of the present day galaxies using SED from JK99. Solid line show the evolution of colors out to $`z`$=2 using K-correction and SED from JK99. Filled circle shows an example of colors from high-$`z`$ galaxies with SED from JK99 assuming that they are at different $`z`$: $`z`$=0.7 in J, 0.5 in H and 2 in K bands. (b) Cumulative flux distribution as function of K magnitude from galaxies from deep galaxy surveys (e.g. Djorgovski et al 1995). Vertical lines denote the range of limiting magnitudes of clipped point sources in the seven patches. (c) Rate of CIB flux production vs $`z`$ assuming only K-correction in the present-day population of galaxies. SED was taken from JK99. Solid, dashed and dotted lines are for $`(\mathrm{\Omega },\mathrm{\Omega }_\mathrm{\Lambda })`$ = (0.3,0.7), (0.3,0) and (1,0) respectively. Thin lines of each type correspond to the largest clipping magnitude galaxies (K=18.6 in Patch 2) and thick lines to the faintest (K=19 in Patch 3). (d) Amplitude of the rms CIB flux fluctuation from Fig. 1 vs $`\sigma `$ before de-striping. The magnitude of the clipped out galaxies (and stars), $`(m_J,m_H,m_K)`$=(24.3,23.5,22.8)–$`2.5\mathrm{log}\sigma `$, is shown on the top horizontal axis, where $`A_m=1.6,0.8,0`$ in J, H, K bands respectively. Triangles, squares and crosses correspond to J, H, K bands. (e) Power law index $`n`$ for the final power spectrum in Fig. 1 is plotted vs the $`\sigma `$ before de-striping. Same symbol notation as in (d).


text:
# A Wilson Group of Non-Uniformly Exponential Growth

## 1. Introduction

The purpose of this note is to construct in an as short and elementary way as possible a group of non-uniformly exponential growth, i.e. a group of exponential growth with a family of generating sets for which the growth rate tends to $`1`$. The “limit” of these generating sets generates a group of intermediate growth.

This construction is an adaptation of \[Bar02\], which describes a family of groups of intermediate growth. It came after John Wilson announced he had produced such a group; my method is similar to his, and indeed only claims to be somewhat shorter and more explicit than his recent preprint \[Wil02\].

The reader is directed to \[Har00\] for a survey on uniform growth of groups.

## 2. A Group of Non-Uniformly Exponential Growth

First consider the group $`A=\mathrm{𝖯𝖲𝖫}(3,2)`$ acting on the $`7`$-point projective plane $`P`$ over $`\mathrm{𝔽}_2`$. The group $`A`$ is generated by $`3`$ reflections $`x,y,z`$ in $`P`$, as in Figure 1.

In symbolic notation, we write

$$x=(\mathbb{𝟙},\mathbb{𝟝})(\mathbb{𝟛},\mathbb{𝟟}),y=(\mathbb{𝟚},\mathbb{𝟛})(\mathbb{𝟞},\mathbb{𝟟}),z=(\mathbb{𝟜},\mathbb{𝟞})(\mathbb{𝟝},\mathbb{𝟟}).$$

Next we let $`A`$ act on the sequences $`P^{}`$ over $`P`$ by

$$(p_1p_2\mathrm{}p_n)a=(p_1a)p_2\mathrm{}p_n,$$

and we let an isomorphic copy $`\overline{A}`$ of $`A`$ act on $`P^{}`$ by

$$(p_1\mathrm{}p_mp_{m+1}\mathrm{}p_n)\overline{a}=p_1\mathrm{}p_m(p_{m+1}a)p_{m+2}\mathrm{}p_n,$$

where $`p_1=\mathrm{}=p_{m1}=\mathbb{𝟙}`$, $`p_m=\mathbb{𝟚}`$. Alternatively, given $`g_1,\mathrm{},g_7W`$ and $`aA`$, we introduce the notation $`g=g_1,\mathrm{},g_7a`$ for the permutation $`g`$ of $`P^{}`$ defined by

$$(p_1p_2\mathrm{}p_n)g=(p_1a)((p_2\mathrm{}p_n)g_{p_1}).$$

In this notation, we have $`\overline{a}=\overline{a},a,1,1,1,1,1`$.

We then define the group $`W=A,\overline{A}`$ by its action on $`P^{}`$.

Let $`G`$ be a group generated by a finite generating set $`S`$. Its *growth rate* is

$$\lambda (G,S)=\underset{n\mathrm{}}{lim}\sqrt[n]{\mathrm{\#}B_{G,S}(n)},$$

where $`B_{G,S}(n)=\{gG|g=s_1\mathrm{}s_n\text{ for some }s_iS\}`$ is the ball of radius $`n`$ in $`G`$, with the word metric induced by $`S`$. (This limit exists because $`\mathrm{log}\mathrm{\#}B_{G,S}(n)`$ is a subadditive function.)

The group $`G`$ has *exponential growth* if $`\lambda (G,S)>1`$ for one, or equivalently for any, generating set, and has *subexponential growth* otherwise. If $`\lambda (G,S)=1`$ and $`\mathrm{\#}B_{G,S}(n)`$ is not bounded by any polynomial function of $`n`$, then $`G`$ has *intermediate growth*. It is non-trivial to construct groups of intermediate growth, and the first example was produced by Grigorchuk \[Gri83\] in 1983.

Note that if $`\lambda _{G,S}>1`$, then there exist other generating sets $`S^{}`$ for $`G`$ with $`\lambda (G,S^{})`$ arbitrarily large — for instance, $`\lambda (G,B_{G,S}(k))=\lambda (G,S)^k`$. On the other hand, it is not obvious that $`\lambda (G,S)`$ can be made arbitrarily close to $`1`$.

The group $`G`$ has *uniformly exponential growth* if $`inf_{\text{finite }S}\lambda (G,S)>1`$.

Note that free groups, and more generally hyperbolic groups, have uniformly exponential growth as soon as they have exponential growth. Solvable groups \[Osi00\], and linear groups \[EMO02\] in characteristic $`0`$, also have uniformly exponential growth as soon as they have exponential growth.

Mikhael Gromov asked in 1981 whether there exist groups of exponential, but non-uniformly exponential growth \[Gro81, Remarque 5.12\]. This was answered positively by John Wilson \[Wil02\], and is the main result of this note:

###### Theorem 2.1.

$`W`$ is a group of exponential growth, but not of uniformly exponential growth.

The proof relies on the following propositions:

###### Proposition 2.2.

$`W`$ satisfies the decomposition111By $`WA`$ we mean the wreath product $`\{f:PW\}A`$. $`W=WA`$.

###### Proposition 2.3.

$`W`$ contains a free monoid on $`2`$ generators.

Given a triple $`\{a,b,c\}`$ of involutions acting on $`P^{}`$, we define a new triple $`\{a^{},b^{},c^{}\}`$ of involutions acting on $`P^{}`$ by

$$a^{}=1,1,1,a,1,1,1x,b^{}=b,1,1,1,1,1,1y,c^{}=1,c,1,1,1,1,1z.$$

###### Proposition 2.4.

If $`G`$ is a perfect group generated by $`3`$ involutions $`a,b,c`$, then $`\{a^{},b^{},c^{}\}`$ generates $`GA`$.

###### Proposition 2.5.

$`W`$ is generated by $`3`$ involutions.

###### Proposition 2.6.

Let $`G`$ be generated by a triple of involutions $`S=\{a,b,c\}`$, and set $`S=\{a^{},b^{},c^{}\}`$ and $`H=S^{}`$. Then

($``$)
$$\lambda (H,S^{})\underset{\eta (0,1)}{inf}\mathrm{max}\{\lambda (G,S)^{1\eta },\frac{30^\eta }{\eta ^\eta (1\eta )^{1\eta }}\}.$$

###### Proof of Theorem 2.1.

$`W`$ has exponential growth by Proposition 2.3.

Pick by Proposition 2.5 a generating set $`S_1=\{a,b,c\}`$ of $`W`$ consisting of involutions; then $`\lambda (G,S_1)2`$. For all $`n1`$ apply Propositions 2.6 and 2.4 to $`(W,S_n)`$ to obtain $`(W,S_{n+1})`$. Define inductively $`\mathrm{\Lambda }_1=2`$, and $`\mathrm{\Lambda }_{n+1}`$ by solving for the unique $`\eta _n(0,1)`$ such that

(\*)
$$\mathrm{\Lambda }_{n+1}=\mathrm{\Lambda }_n^{1\eta _n}=30^{\eta _n}\eta _n^{\eta _n}(1\eta _n)^{\eta _n1}.$$

It is clear that $`1<\mathrm{\Lambda }_{n+1}<\mathrm{\Lambda }_n`$, so $`\mathrm{\Lambda }=lim_n\mathrm{}\mathrm{\Lambda }_n`$ and $`\eta =lim_n\mathrm{}\eta _n`$ exist. From (*2) we have $`\mathrm{\Lambda }=\mathrm{\Lambda }^{1\eta }`$, so either $`\mathrm{\Lambda }=1`$ or $`\eta =0`$, which again implies $`\mathrm{\Lambda }=1`$. Since $`\lambda (W,S_n)\mathrm{\Lambda }_n`$ for all $`n\mathrm{}`$, we have $`lim_n\mathrm{}\lambda (W,S_n)=1`$. ∎

## 3. A Group Of Intermediate Growth

Consider next the set $`\stackrel{~}{S}=\{\stackrel{~}{x},\stackrel{~}{y},\stackrel{~}{z}\}`$ of transformations of $`P^{}`$ defined inductively by

$$\stackrel{~}{x}=1,1,1,\stackrel{~}{x},1,1,1x,\stackrel{~}{y}=\stackrel{~}{y},1,1,1,1,1,1y,\stackrel{~}{z}=1,\stackrel{~}{z},1,1,1,1,1z,$$

and consider the group $`V=\stackrel{~}{S}`$.

###### Theorem 3.1.

$`V`$ is a group of intermediate growth.

$`V`$ is locally isomorphic to $`W`$, in that for any $`R\mathrm{}`$, there is $`n\mathrm{}`$ such that $`B_{V,\stackrel{~}{S}}(R)`$ and $`B_{W,S_n}(R)`$ are isomorphic graphs, as seen as subsets of their respective group’s Cayley graph.

(Note that $`V`$ is not perfect; indeed $`V/V^{}(\mathrm{}/2)^3`$. Hence $`V`$ does not decompose as a wreath product like $`W`$.)

###### Proof.

Apply Proposition 2.6 to $`(V,\stackrel{~}{S})`$ to obtain $`(V,\stackrel{~}{S}^{})`$, and notice $`\stackrel{~}{S}^{}=\stackrel{~}{S}`$; hence $`\lambda (V,\stackrel{~}{S})=\lambda (V^{},\stackrel{~}{S}^{})`$, so $`\lambda (V,\stackrel{~}{S})=1`$ by ($``$2.6).

The groups $`V`$ and $`W`$ are contracting, i.e. there are constants $`\rho =\frac{1}{2}`$ and $`M=1`$ such that for $`G\{V,W\}`$ the decomposition of $`B(G,R)`$ is a subset of $`B(G,\rho R+M)A`$ for all $`R\mathrm{}`$.

Pick now $`R\mathrm{}`$. There exists therefore $`n\mathrm{}`$ such that the $`n`$-fold decomposition of $`B(G,R)`$ is a subset of $`(\mathrm{}(B(G,1)A)A\mathrm{}A)`$. Since the generators $`\stackrel{~}{S}`$ and $`S_1`$ agree on a ball of radius $`1`$, this implies that the generators $`\stackrel{~}{S}`$ and $`S_n`$ agree on a ball of radius $`R`$. ∎

## 4. Proofs

We will use repeatedly the following facts on $`A`$: it has order $`168`$, and is simple, hence perfect. It is generated by $`\{x,y,z\}`$, and also by $`\{xy,yz,zx\}`$.

###### Proof of Proposition 2.2.

Since $`A`$ acts $`2`$-transitively on $`P`$, there is $`uA`$ that fixes $`\mathbb{𝟙}`$ and moves $`\mathbb{𝟚}`$ to another point, and $`vA`$ that fixes $`\mathbb{𝟚}`$ and moves $`\mathbb{𝟙}`$ to another point.

Then $`W`$ contains $`[\overline{a},\overline{b}^u]=[\overline{a},\overline{b}],1,\mathrm{},1`$ for any $`a,bA`$, and since $`A`$ is perfect $`W`$ contains $`\overline{A},1,\mathrm{},1`$. Similarly, $`W`$ contains $`[\overline{a},\overline{b}^v]=1,[a,b],1,\mathrm{},1`$ for any $`a,bA`$, so $`W`$ contains $`1,A,1,\mathrm{},1`$. Combining these, $`W`$ contains $`W,\mathrm{},W`$ and $`A`$, so $`W`$ contains $`WA`$. The converse inclusion is obvious. ∎

###### Proof of Proposition 2.3.

Pick $`uvA`$ such that $`\mathbb{𝟙}u=\mathbb{𝟙}v=\mathbb{𝟚}`$ and $`\mathbb{𝟚}u=\mathbb{𝟚}v=\mathbb{𝟙}`$. Consider the elements $`a=\overline{u}u,b=\overline{u}v,c=\overline{v}u,d=\overline{v}v`$. They admit the decompositions

($``$) $`a`$ $`=\overline{u},u,1,\mathrm{},1(\mathbb{𝟙},\mathbb{𝟚})\sigma ,`$ $`b`$ $`=\overline{u},u,1,\mathrm{},1(\mathbb{𝟙},\mathbb{𝟚})\tau ,`$
$`c`$ $`=\overline{v},v,1,\mathrm{},1(\mathbb{𝟙},\mathbb{𝟚})\sigma ,`$ $`d`$ $`=\overline{v},v,1,\mathrm{},1(\mathbb{𝟙},\mathbb{𝟚})\tau ,`$
for some permutations $`\sigma \tau `$ of $`P\{\mathbb{𝟙},\mathbb{𝟚}\}`$. I claim that $`M=\{a,d\}^{}`$ is a free monoid; actually, we will show something slightly stronger, namely that $`\{a,b,c,d\}^{}/(a=b,c=d)`$ is freely generated by $`\{a,d\}`$.

Consider two words $`X,Y`$ over $`a,b,c,d`$, that are not equivalent under $`(a=b,c=d)`$; we will prove by induction on $`|X|+|Y|`$ that they act differently on $`P^{}`$. We may assume that $`X`$ and $`Y`$ are both non-empty, and that $`X`$ starts by $`a`$ or $`b`$, and $`Y`$ starts by $`c`$ or $`d`$. If $`|X|=|Y|=1`$ then the decompositions ($``$4) show that $`X`$ and $`Y`$ act differently on $`P^{}`$. Otherwise, we have $`|X||Y|mod2`$, by considering the action on $`\mathbb{𝟙}`$; and furthermore we may assume $`|X||Y|0mod2`$, by multiplying both $`X`$ and $`Y`$ by $`a`$ on the right. Consider the decompositions

$$X=X_1,\mathrm{},X_7\alpha ,Y=Y_1,\mathrm{},Y_7\beta .$$

Then $`X_1,Y_1\{a,b,c,d\}^{}`$, and $`X_1`$ starts by $`a`$ or $`b`$, and $`Y_1`$ starts by $`c`$ or $`d`$. We have $`|X_1|=|X|/2`$ and $`|Y_1|=|Y|/2`$, so by induction $`X_1`$ and $`Y_1`$ act differently on $`P^{}`$, and hence so do $`X`$ and $`Y`$. ∎

###### Proof of Proposition 2.4.

Set $`H=a^{},b^{},c^{}`$. Then $`H`$ contains $`(a^{}b^{}c^{}b^{})^3=1,1,ac,ac,1,1,ca`$, $`(b^{}c^{}a^{}c^{})^3=ba,1,1,1,1,ba,ab`$ and $`(c^{}a^{}b^{}a^{})^3=1,cb,1,1,cb,1,bc`$; so $`H`$ contains

$$v=[(a^{}b^{}c^{}b^{})^3,(b^{}c^{}a^{}c^{})^3]=1,\mathrm{},1,[ca,ac]1.$$

Now $`ac,cb,ba=G`$ because $`G`$ is perfect, so we may conjugate $`v`$ by $`(b^{}c^{}a^{}c^{})^3`$ etc. to see that $`H`$ contains $`G,\mathrm{},G`$.

Therefore $`H`$ contains $`x=1,1,1,a,1,1,1a^{}`$, and similarly $`y`$ and $`z`$, so $`H=GA`$. ∎

###### Proof of Proposition 2.5.

Define $`a,b,cW`$ by

$$a=1,\overline{x},1,x,1,1,1x,b=y,1,1,\overline{y},1,1,1y,c=\overline{z},z,1,1,1,1,1z.$$

Then $`(ab)^4=1,\overline{x},\overline{x},(x\overline{y})^4,1,\overline{x},\overline{x}=1,\overline{x},\overline{x},1,1,\overline{x},\overline{x}`$, and similarly $`(bc)^4=1,1,1,\overline{y},\overline{y},\overline{y},\overline{y}`$ and $`(ca)^4=\overline{z},1,\overline{z},1,\overline{z},1,\overline{z}`$.

Therefore $`G=a,b,c`$ contains

$$u=[[(ab)^4,(bc)^4],(ca)^4]=1,\mathrm{},1,[[\overline{x},\overline{y}],\overline{z}]1,$$

so $`G`$ contains all of $`u`$’s conjugates by $`(ab)^4,(bc)^4,(ca)^4`$, and since $`A`$ is perfect $`G`$ contains $`1,\mathrm{},1,\overline{A}`$; conjugating by $`a,b,c`$, we see that $`G`$ contains $`\overline{A},\mathrm{},\overline{A}`$.

Next, $`G`$ contains $`a^{}=1,\overline{x},1,1,1,1,1a=1,1,1,x,1,1,1x`$, and similarly $`b^{}=y,1,1,1,1,1,1y`$ and $`c^{}=1,z,1,1,1,1,1z`$, so by Proposition 2.4 $`G`$ contains $`AA`$; therefore $`W=G=a,b,c`$. ∎

###### Proof of Proposition 2.6.

Consider a word $`w\{a^{},b^{},c^{}\}^{}`$ representing an element in $`H`$, and compute its decomposition $`w_1,\mathrm{},w_7\sigma `$. Each of the $`w_i`$’s is a word over $`\{a,b,c\}`$, and the total length of the $`w_i`$ is at most the length of $`w`$, since each $`a^{},b^{},c^{}`$ contributes a single $`a,b,c`$-letter to one of the $`w_i`$’s.

A *reduced* word is a word with no two identical consecutive letters; we shall always assume the words we consider are reduced. Therefore all $`aa`$-, $`bb`$\- and $`cc`$-subwords of the $`w_i`$’s should be cancelled; and such subwords appear in a $`w_i`$ whenever $`w`$ has a subword belonging to

$$\mathrm{\Delta }=\{a^{}b^{}a^{},b^{}c^{}b^{},c^{}a^{}c^{},a^{}c^{}b^{}a^{}c^{}a^{}b^{}c^{}a^{},b^{}a^{}c^{}b^{}a^{}b^{}c^{}a^{}b^{},c^{}b^{}a^{}c^{}b^{}c^{}a^{}b^{}c^{}\};$$

indeed

$$a^{}b^{}a^{}=1,1,1,1,b,1,1xyx,$$

$$a^{}c^{}b^{}a^{}c^{}a^{}b^{}c^{}a^{}=a,cb,1,1,bc,a,cyzxzy.$$

###### Lemma 4.1.

For any $`n\mathrm{}`$, there are at most $`30`$ reduced words $`w`$ of length $`n`$ that contain no subword belonging to $`\mathrm{\Delta }`$.

###### Proof.

If $`w`$ contains $`a^{}c^{}a^{}`$, $`b^{}a^{}b^{}`$ or $`c^{}b^{}c^{}`$ as a subword, then this subword occurs either among the first $`5`$ or the last $`5`$ letters of $`w`$, and $`w`$ is a subword of $`(xyz)^{\mathrm{}}y(zyx)^{\mathrm{}}`$, where $`x,y,z`$ is a cyclic permutation of $`a^{},b^{},c^{}`$. This gives $`24`$ possibilities: $`3`$ for the choice of the cyclic permutation and $`8`$ for the position of $`zyz`$ subword in $`w`$.

If $`w`$ does not contain any such subword, then $`w`$ must be a subword of $`(xyz)^{\mathrm{}}`$ or $`(zyx)^{\mathrm{}}`$, and this gives $`6`$ possibilities: $`3`$ for the choice of the cyclic permutation and $`2`$ for the choice of $`xyz`$ or $`zyx`$. ∎

Fix now for every $`hH`$ a word $`w_h`$ of minimal length representing $`h`$; and for all $`n\mathrm{}`$ let $`F_n`$ denote the set of such words of length $`n`$. We wish to estimate $`\mathrm{\#}F_n`$.

For any $`\eta (0,1)`$, define the following sets:

$`F_n^{>\eta }`$ $`=\{wF_n|w\text{ contains at least }\eta n\text{ subwords belonging to }\mathrm{\Delta }\},`$
$`F_n^{<\eta }`$ $`=\{wF_n|w\text{ contains at most }\eta n\text{ subwords belonging to }\mathrm{\Delta }\}.`$
Note that any $`wF_n^{<\eta }`$ factors as a product of at most $`\eta n`$ pieces $`u_1\mathrm{}u_m`$, where each $`u_i`$ does not contain any subword from $`\mathrm{\Delta }`$. We therefore have

$$\mathrm{\#}F_n^{<\eta }\eta n30^{\eta n}\left(\genfrac{}{}{0pt}{}{n}{\eta n}\right);$$

the $`\eta n`$ accounting for all numbers of pieces between $`1`$ and $`\eta n`$, the $`30^{\eta n}`$ counting (according to the Lemma) the possible choices of each piece, and the binomial term counting for the respective lengths of the pieces — they are determined by a selection of $`\eta n`$ “separation points” among $`n`$.

Estimating the binomial coefficient $`\left(\genfrac{}{}{0pt}{}{n}{\eta n}\right)\left(\eta ^\eta (1\eta )^{1\eta }\right)^n`$, we get

$$\underset{n\mathrm{}}{lim}\sqrt[n]{\mathrm{\#}F_n^{<\eta }}\frac{30^\eta }{\eta ^\eta (1\eta )^{1\eta }}.$$

Next, every $`wW_n^{>\eta }`$ gives by decomposition $`7`$ words $`w_1,\mathrm{},w_7`$ of total length at most $`(1\eta )n`$, after cancellation of the $`aa`$-, $`bb`$\- and $`cc`$-subwords.

For any $`ϵ>0`$, there is a constant $`K`$ such that $`\mathrm{\#}B_{G,S}(n)K(\lambda (G,S)+ϵ)^n`$ for all $`n\mathrm{}`$. Therefore

$$\mathrm{\#}F_n^{>\eta }\mathrm{\#}A\left(\genfrac{}{}{0pt}{}{n+7}{7}\right)K^7(\lambda (G,S)+ϵ)^{(1\eta )n};$$

the binomial term majoring all possible partitions of the total length of the $`w_i`$’s in $`7`$ parts, and the other terms counting the number of values the $`w_i`$’s may assume. It follows that $`lim_n\mathrm{}\sqrt[n]{\mathrm{\#}F_n^{>\eta }}(\lambda (G,S)+ϵ)^{1\eta }`$ for all $`ϵ>0`$, and therefore

$$\underset{n\mathrm{}}{lim}\sqrt[n]{\mathrm{\#}F_n^{>\eta }}\lambda (G,S)^{1\eta }.$$

Now $`\mathrm{\#}B_{H,S^{}}(n)n\left(\mathrm{\#}F_n^{<\eta }+\mathrm{\#}F_n^{>\eta }\right)`$, and

$`\lambda (H,S^{})`$ $`=\underset{n\mathrm{}}{lim}\sqrt[n]{\mathrm{\#}B_{H,S^{}}(n)}\underset{n\mathrm{}}{lim}\sqrt[n]{\mathrm{\#}F_n^{<\eta }+\mathrm{\#}F_n^{>\eta }}`$
$`\underset{n\mathrm{}}{lim}\mathrm{max}\{\sqrt[n]{\mathrm{\#}F_n^{<\eta }},\sqrt[n]{\mathrm{\#}F_n^{>\eta }}\}`$
$`\mathrm{max}\{\lambda (G,S)^{1\eta },{\displaystyle \frac{30^\eta }{\eta ^\eta (1\eta )^{1\eta }}}\}.`$