text:
# Finding The Sign Of A Function Value By Binary Cellular Automaton

## I Introduction

Cellular Automaton (CA) is a simple local interaction model of natural systems used extensively in various fields of physics. Besides, CA can be regarded as a computation model motivated by biological phenomenon. Various inequivalent definitions of CA exist in the community. In this paper, we restrict ourselves to consider the time evolution of CA to be governed by a local synchronous deterministic uniform rule. In other words, the state of each site in the next time step depends deterministically only on the states of its finite neighborhood, the states of all sites are updated in parallel, and the transformation CA rule table is covariant under translation of the background lattice. In this respect, CA can be regarded as a decentralized deterministic parallel computation model without central memory storage. It is useful to study its power and limitation. In fact, a recent renewal interest in CA computing makes such an investigation timely.

Since CA rules are local in nature, it is instructive to see if CA can perform tasks that involve global quantities. Perhaps the most well-known example is the so-called density classification problem. Considering a bit string of finite length $`N`$ with periodic boundary conditions, the problem is to change all bits in the string to $`0`$ if the number of $`0`$s is greater than the number of $`1`$s in the input bit string, and to change all bits to $`1`$ if the number of $`1`$s is greater than the number of $`0`$s. Clearly, the global quantity involved in this problem is the density of $`1`$s which is defined as the number of $`1`$s in the string divided by the string length $`N`$.

Various CA rules have been proposed to solve the density classification problem both by human and by genetic algorithm. But they only provide approximate solutions. In other words, these rules work for most but not all randomly chosen initial configurations. In fact, Land and Belew showed that density classification cannot be performed perfectly using a single one dimensional CA rule. Later on, Capcarrere and his collaborators proved that a single CA rule can solve the density classification and other related problems exactly if we modify either the required output of the automaton or the boundary conditions. However, in their approach, it has to scan through the states of all sites in the final configuration, in general, before knowing the answer. This requires global memories in the read out process. In contrast, read out in the original density classification problem can clearly be done by looking at the states of a few local sites, and hence can be done with an additional finite rule table whose size is independent of $`N`$.

Recently, Fukś pointed out that the density classification problem can be solved exactly if we apply two CA rules in succession. More precisely, he showed that by applying a CA rule a fixed number of times depending only on the lattice size and then followed by applying another CA rule a fixed number of times depending again only on the lattice size, the density classification problem can be solved exactly. Fukś further asked if it is possible to classify a rational density. That is, he questioned if it is possible to determine, using succession of CA rules, whether the density of $`1`$s in an arbitrary one dimensional array with periodic boundary conditions is less than, equal to or greater than a prescribed rational number $`p/q`$, called the critical density. Chau et al. answered his question affirmatively by showing that two CA rules are necessary and sufficient in solving the rational density classification problem exactly. His group further generalized their algorithm to find the majority state of an one dimensional array when each site may take on $`n`$ possible states . In addition, further constraints on the forms of certain CA rules that can be used in the rational density classification problem have also be reported.

In Section II, we shall spell out the details of the problem that we are interested in. Then after introducing some technical results in Section III, we shall solve the problem using a set of binary CAs with local synchronous deterministic uniform rules in Section IV. The general solution reported in Section IV can be simplified in a number of special but important cases. We report the efficient solutions to these special cases in Section V. Finally, we give a brief discussions on the significance of our result in Section VI.

## II Statement Of The Problem

In this paper, we propose another generalization of the density classification problem, called the generalized density classification problem (GDCP) and solve it using a sequence of CA rules. Before we discuss the significance of our generalization, let us first state our problem precisely.

Suppose we are given an input bit string $`\alpha `$ of length $`N`$ in periodic boundary conditions, as well as a continuous function $`f(x)`$ with finitely many discontinuous points of $`\text{sgn}(f(x))`$ in the interval $`[0,1]`$, where

$$\text{sgn}(y)=\{\begin{array}{cc}\hfill 1& \text{if }y>0,\hfill \\ \hfill 1& \text{if }y<0,\hfill \\ \hfill 0& \text{if }y=0.\hfill \end{array}$$
(1)
Moreover, those discontinuous points are rational and shall be denoted by $`p_i/q`$ where $`p_i,q^+\{0\}`$, and $`i`$ is the index for the discontinuous points. In addition, we have the freedom to choose the smallest positive $`q`$ for the denominators of all the expressions $`p_i/q`$. With this choice, $`p_i`$ and $`q`$ need not be relatively prime. Finally, we require that $`f(\frac{1}{2q})`$ and $`f(\frac{2q1}{2q})`$ are non-zero.

We define the density of $`1`$s of the bit string $`\alpha `$ as the total number of $`1`$s in the bit string divided by the string length $`N`$ and is denoted by the symbol $`\rho (\alpha )`$. We may simply write $`\rho `$ instead of $`\rho (\alpha )`$ when it is clear from the content which bit string we are referring to.

The task of GDCP is to evolve the bit string $`\alpha `$ to all $`1`$ (or $`0`$) if $`\text{sgn}(f(\rho (\alpha )))=1`$ (or $`\text{sgn}(f(\rho (\alpha )))=1`$). Besides, we have to preserve the density of $`1`$s of the bit string if $`\text{sgn}(f(\rho (\alpha )))=0`$. In addition, by inspecting a fixed portion of the final output string, we are able to distinguish between the above three cases with certainty. (We shall consider a slightly relaxed variant to this definition later on in Section V.) To solve the GDCP by a sequence of binary CA rules, we mean that every initial configuration can be correctly classified by applying some binary CA rule $`R_1`$ $`t_1`$ times followed by another binary CA rule $`R_2`$ $`t_2`$ times and so on up to the $`k`$th binary CA rule $`R_k`$ $`t_k`$ times, where $`k`$ is fixed and independent of the string length $`N`$. Besides, each CA rule $`R_i`$ must be independent of the input $`\alpha `$ and has a bounded rule table size that is also independent of $`N`$. Finally, the number of iterations $`t_i`$ is independent of the initial configuration, but may depend on $`N`$.

Clearly, the GDCP reduced to the rational density classification problem by choosing $`f(x)=x\rho _c`$ where $`\rho _c`$ is a rational number. Moreover, the GDCP can be solved trivially if we have a global counter.

In addition to naturally generalize the density classification problem, GDCP is interesting on its own right. First, by choosing

$$f(x)=\{\begin{array}{cc}x\rho _{c1}& \text{if }x<\rho _{c1},\hfill \\ 0& \text{if }\rho _{c1}x\rho _{c2},\hfill \\ x\rho _{c2}& \text{if }x>\rho _{c2},\hfill \end{array}$$
(2)
where $`\rho _{c1}<\rho _{c2}`$ both being rational, it determines if the density of $`1`$s is in the interval $`(\rho _{c1},\rho _{c2})`$ from a single copy of input bit string. (Note that it is more efficient to ask if $`\rho `$ is between $`1/10`$ and $`4/39`$ rather than to ask if $`\rho `$ equals $`0.10215`$ partly because of our result in Section IV that the former question requires smaller CA rule tables.) Thus, GDCP can be used to determine the coarse-grained density of $`1`$s efficiently, while in the rational density classification problem, the resolution is infinite in the sense that we can only determine whether $`\rho >\rho _c`$, $`\rho =\rho _c`$ or $`\rho <\rho _c`$, no matter how closed $`\rho `$ is to $`\rho _c`$. This reason alone is good enough to investigate the GDCP. Second, the GDCP has a more interesting flow diagram. While the rational density classification automata has two stable and one unstable fixed points in the density of 1s, the GDCP automata in general has at most two stable fixed points ($`\rho =1`$ and $`\rho =0`$), finitely many unstable fixed points (at where $`f(\rho )=0`$ but $`f`$ is not identical zero locally near $`\rho `$) and infinitely many neutral fixed points (at where $`f(\rho )=0`$ and $`f`$ is identical zero locally near $`\rho `$) in the limit of $`N\mathrm{}`$.

## III Some Useful Cellular Automaton Building Blocks

Let us first report several essential building blocks of our solution to the GDCP.

### A Car Hopping Automaton

The first step in solving the problem is to make the density of 1s uniform so as to make the local density of 1s a good estimation of the global density of 1s in the bit string. To measure the local density, we introduce the concept of $`k`$th order local number. It is just the number of 1s around the site we are interested. The CA rule $`𝐇_k`$ will move the 1s to the right according to the local density gradient. If we repeatedly apply $`𝐇_k`$ to an arbitrary bit string, eventually the density of 1s of the resulting string will be more or less uniform. Of course we cannot expect that all local numbers are equal, but we can prove that the difference between local numbers of different sites can only be less than or equal to one. This CA rule is the most important CA rule in this paper.

###### Definition 1

We denote a configuration in our bit string of length $`N`$, which can be identified with an one dimensional array of sites in periodic boundary conditions, by $`\alpha `$ and the state of the $`i`$th site by $`\alpha (i)`$. That is, $`\alpha (i)`$ is the value of the $`i`$th bit in the string counting from left to right. We define the $`k`$th order local number of the $`i`$th site in our one dimensional array by $`n_k(\alpha ,i)=_{j=0}^{k1}\alpha (i+j)`$ where the sum $`i+j`$ in the index here and elsewhere in this paper is understood to be modulo $`N`$.

In other words, the $`k`$th order local number is the number of sites with state $`1`$ among the $`k`$ consecutive sites starting from the site $`i`$. So, if we regard state $`0`$ as an empty site and state $`1`$ as a site with a car, the $`k`$th order local number gives the local number of cars near a site. From now on, we shall interchangeably describe the state $`1`$ as a car and the state $`0`$ as an empty site. Thus, the density of $`1`$s of a bit string can also be referred to as the car density.

In what follows, we shall write $`n_k(i)`$ instead of $`n_k(\alpha ,i)`$ when there is no confusion on which bit string we are referring to.

###### Rule 1 ($`k`$th order car hopping rule)

Let us denote this CA rule by $`𝐇_k`$. The state of site $`i`$ in the next time step $`𝐇_k[\alpha ](i)`$ is given by:

$`𝐇_k[\alpha ](i)=\{\begin{array}{cc}0& \text{if }\alpha (i)=1,\alpha (i+1)=0\text{ and }\hfill \\ & n_k(ik+1)>n_k(i+1),\hfill \\ 1& \text{if }\alpha (i)=0,\alpha (i1)=1\text{ and }\hfill \\ & n_k(ik)>n_k(i),\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}`$ (8)
This CA rule can be rewritten in another form as follows: we interchange the states in site $`i`$ and $`i+1`$ if and only if $`\alpha (i)=1,\alpha (i+1)=0`$ and $`n_k(ik+1)>n_k(i+1)`$. All other states remain unchanged. All updates are taken in parallel. In what follows, we shall sometimes refer to such an interchange as hopping of a car.

For example, $`𝐇_4(011001010010)=010100101010`$.

Note that the role of $`0`$ and $`1`$ in the above CA rule is symmetric in the sense that it is invariant under the interchange of state $`0`$ and $`1`$ plus the relabeling of $`i`$ as $`i`$. Following the spirit of particle physics, we shall refer to this property as the CP symmetry. Furthermore, the car density $`\rho `$ is conserved under this CA rule. In fact one way to interpret this CA rule is that cars are driven to move from left to right by local car density gradient. Or equivalently, empty sites are driven to move from right to left by local empty site density gradient. Therefore, we expect that the $`k`$th order local numbers in all recurrent states under the repeated iteration of $`𝐇_k`$ is evenly distributed. Nonetheless, a rigorous proof turns out to be rather involved partly because a car at site $`i`$ cannot hop whenever another car is occupying site $`i+1`$ even in the presence of a car density gradient. We now begin rigorous proof by first introducing a few technical lemmas.

We expect that for any bit string $`\alpha `$, the density of $`\beta 𝐇_k^l(\alpha )`$ will be uniform if $`l`$ is large enough. The first lemma shows that this is indeed the case when $`\beta `$ is a fixed point of $`𝐇_k`$.

###### Lemma 1

The $`k`$th order local number $`n_k(i)`$ is equal for all $`i`$ if and only if $`𝐇_k(\alpha )=\alpha `$ (that is, no car hops under the action of the $`k`$th order car hopping rule).

Proof: If $`𝐇_k(\alpha )\alpha `$, then some car in the bit string $`\alpha `$ hops under the action of $`𝐇_k`$. So clearly $`n_k(i)>n_k(i+k)`$ for some $`i`$.

Conversely, if $`𝐇_k(\alpha )=\alpha `$, then we may assume that $`\alpha `$ does not equal to all $`0`$ or all $`1`$, for otherwise the Lemma is trivially true. Now locally we have any one of the following three situations.

Case (a) $`\alpha (i1)=1`$ and $`\alpha (i)=0`$: in this case we clearly require $`n_k(ik)n_k(i)`$ in order to prevent the car located at site $`i1`$ from hopping.

Case (b) $`\alpha (i)=\mathrm{}=\alpha (i+j1)=1`$ and $`\alpha (i+j)=0`$ for some $`j>0`$: in this case we again conclude that $`n_k(ik)n_k(i)`$ for otherwise we have $`n_k(i+jk)n_k(i+jk1)\mathrm{}n_k(ik)>n_k(i)n_k(i+1)\mathrm{}n_k(i+j)`$ contradicting the assumption that the car located at site $`i+j1`$ does not move.

Case (c) $`\alpha (i)=\alpha (i1)=\mathrm{}=\alpha (ij)=0`$ and $`\alpha (ij1)=1`$ for some $`j>0`$: the CP symmetry of the CA rule $`𝐇_k`$ implies that we can use the same trick as in the proof of case (b) to show that $`n_k(ik)n_k(i)`$.

In summary, we conclude that $`n_k(ik)n_k(i)`$ for all $`i`$; and since we are working in a finite bit string with periodic boundary, this is possible only when $`n_k(ik)=n_k(i)`$ for all $`i`$.

Suppose that $`n_k(ik+1)>n_k(ik+2)`$ for some $`i`$, then $`\alpha (ik+1)=1`$ and $`\alpha (i+1)=0`$. However, this also implies that $`n_k(i+1)>n_k(i+2)`$ and hence $`\alpha (i+1)=1`$ and $`\alpha (i+k+1)=0`$ which is a contradiction. By the same token, it is absurd to have $`n_k(ik+1)<n_k(ik+2)`$. Thus, the only possibility is that $`n_k(i)=n_k(i+1)`$ for all $`i`$ and hence $`n_k(i)=n_k(j)`$ for all $`i,j`$. $`\mathrm{}`$

Lemma 1 gives an important property of fixed points of $`𝐇_k`$. To characterize the property of cycles of $`𝐇_k`$ with period greater than one, we need to work harder. In what follows, we show that whenever there is a fluctuation in the $`k`$th order local number $`n_k(i)`$ in a bit string string $`\alpha `$, at least one car in this string must hop under the action of the $`k`$th order car hopping rule $`𝐇_k`$.

###### Lemma 2

If $`n_k(\alpha ,ik+1)>n_k(\alpha ,i+1)`$, then there exists $`j`$ with $`ik+1j<i+k`$ with $`n_k(\alpha ,jk+1)n_k(\alpha ,ik+1)`$ such that there is a car located at site $`j`$ and this car hops by applying the rule $`𝐇_k`$. Moreover, a car will hop from site $`i`$ to $`i+1`$ in no more than $`k`$ time steps. That is to say, there exists $`rk`$ such that $`𝐇_k^{r1}[\alpha ](i)=1`$, $`𝐇_k^{r1}[\alpha ](i+1)=0`$ and $`𝐇_k^r[\alpha ](i)=0`$.

Proof: We divide the proof into the following three cases.

Case (a) $`\alpha (i)=1`$ and $`\alpha (i+1)=0`$: we choose $`j=i`$ as the car located at site $`i`$ hops by applying $`𝐇_k`$.

Case (b) $`\alpha (i+1)=1`$: since $`n_k(ik+1)>n_k(i+1)`$, we can always find $`1m<k`$ such that $`\alpha (i+1)=\alpha (i+2)=\mathrm{}=\alpha (i+m)=1`$ and $`\alpha (i+m+1)=0`$. Then it is easy to see that $`n_k(i+mk+1)n_k(ik+1)>n_k(i+1)n_k(i+m+1)`$. So the car located at site $`i+m`$ hops to $`i+m+1`$ when we apply $`𝐇_k`$. Hence, we choose $`j=i+m`$. Inductively, in the next time step, we may choose $`j=i+m1`$ and so on. Consequently, in no more than $`k`$ time steps, a car must hop from site $`i`$ to $`i+1`$.

Case (c) $`\alpha (i)=\alpha (i+1)=0`$: exploiting the CP symmetry of the $`k`$th order car hopping rule, this case can be proved in the same way as in case (b). $`\mathrm{}`$

We now introduce the fluctuation amplitude, which is the difference of the local numbers in different sites. It will be shown that the maximum fluctuation amplitude will not increase by the repeated application of $`𝐇_k`$.

###### Definition 2

Let $`\alpha `$ be a bit string of length $`N`$. We denote $`\mathrm{\Delta }_k(\alpha )=\mathrm{max}\{n_k(\alpha ,i)n_k(\alpha ,j):1i,jN\}`$ the maximum fluctuation amplitude of the $`k`$th order local number. We write the maximum and minimum $`k`$th order local numbers of a bit string by $`n_k^{(\mathrm{max})}(\alpha )=\mathrm{max}\{n_k(\alpha ,i):1iN\}`$ and $`n_k^{(\mathrm{min})}(\alpha )=\mathrm{min}\{n_k(\alpha ,i):1iN\}`$, respectively. In addition, we denote the number of sites with $`k`$th order local number equals $`m`$ by $`M_k(\alpha ,m)=|\{1iN:n_k(\alpha ,i)=m\}|`$.

For simplicity, we shall drop the label $`\alpha `$ in $`\mathrm{\Delta }_k`$, $`n_k^{(\mathrm{max})}`$, $`n_k^{(\mathrm{min})}`$ and $`M_k`$ when it is clear which bit string we are referring to in the text.

Now, we are ready to show that repeated application of $`𝐇_k`$ decreases the fluctuation amplitude of the $`k`$th order local number to its minimum possible value in $`\text{O}(N)`$ time steps. More precisely, we are going to prove the following lemma:

###### Lemma 3

Let $`\alpha `$ be a bit string of length $`N`$. Then $`\mathrm{\Delta }_k(𝐇_k^{\mathrm{}(k)}(\alpha ))1`$ where $`\mathrm{}\mathrm{}(k)2k(k2)\frac{1}{2}\frac{N}{k}`$. Besides, $`\mathrm{\Delta }_k(𝐇_k^{\mathrm{}(k)}(\alpha ))=0`$ if and only if $`\rho (\alpha )=r/k`$ for some $`r`$.

Proof: First of all, we show that if $`\mathrm{\Delta }_k(\beta )1`$, then $`\mathrm{\Delta }_k(\beta )=0`$ if and only if $`\rho (\beta )=r/k`$ for some $`r`$. Since the fluctuation of $`n_k(\beta ,i)`$ is less than 2, $`n_k(\beta ,i)`$ can either be $`k\rho (\beta )`$ or $`k\rho (\beta )`$. So, if $`\rho (\beta )=r/k`$ for some $`r`$, then $`\mathrm{\Delta }_k(\beta )=0`$. Conversely, if $`\rho (\beta )`$ is not in the form $`r/k`$ for some $`r`$, then there exist $`i`$ and $`j`$ such that $`n_k(\beta ,i)=k\rho (\beta )`$ and $`n_k(\beta ,j)=k\rho (\beta )`$. Hence, $`\mathrm{\Delta }_k(\beta )=1`$.

Since $`𝐇_k`$ conserves car density, the last statement of this Lemma is proved by setting $`\beta =𝐇_k^{\mathrm{}}(\alpha )`$.

To prove the first part of this Lemma, we may further assume that (a) $`𝐇_k^i(\alpha )𝐇_k^{i1}(\alpha )`$ for all $`i<\mathrm{}`$ and (b) $`\mathrm{\Delta }_k(\alpha )>1`$. For if (a) does not hold, then $`𝐇_k^{\mathrm{}}(\alpha )`$ is a fixed point of $`𝐇_k`$ and hence Lemma 1 tells us that $`\mathrm{\Delta }_k(𝐇_k^{\mathrm{}}(\alpha ))=0`$. In addition, Eq. (8) tells us that it is not possible to increase the $`k`$th order local number $`n_k(\beta ,i)`$ of a site $`i`$ in a bit string $`\beta `$ if $`n_k(\beta ,i)`$ equals $`n_k^{(\mathrm{max})}(\beta )`$. Hence, $`n_k^{(\mathrm{max})}(𝐇_k^i(\alpha ))`$ is a non-increasing function of $`i`$; and by CP symmetry of the $`k`$th order car hopping rule, $`n_k^{(\mathrm{min})}(𝐇_k^i(\alpha ))`$ is a non-decreasing function of $`i`$. As a result, the first part of this Lemma is trivially true if $`\mathrm{\Delta }_k(\alpha )1`$.

Eq. (8) also tells us that for any bit string $`\beta `$, $`n_k(𝐇_k(\beta ),i)=n_k(\beta ,i)+1`$ if and only if a car in $`\beta `$ hops from site $`i1`$ to $`i`$ while no car in $`\beta `$ hops from $`i+k1`$ to $`i+k`$ under the action of $`𝐇_k`$. Besides, $`n_k(𝐇_k(\beta ),i)=n_k(\beta ,i)1`$ if and only if a car in $`\beta `$ hops from site $`i+k1`$ to $`i+k`$ while no car in $`\beta `$ hops from $`i1`$ to $`i`$ under $`𝐇_k`$. Finally, $`n_k(𝐇_k(\beta ),i)=n_k(\beta ,i)`$ if and only if either no car in $`\beta `$ hops from sites $`i1`$ and $`i+k1`$ or cars in $`\beta `$ hop from both sites $`i1`$ and $`i+k1`$. We deduce from this observation together with Lemma 2 that at least one site with $`k`$th order local number $`n_k^{(\mathrm{max})}`$ hops under $`𝐇_k`$. Consequently, the number of cars with maximum value of $`k`$th order local number does not increase with time. In other words,

$$M_k(𝐇_k(\beta ),n_k^{(\mathrm{max})}(\beta ))M_k(\beta ,n_k^{(\mathrm{max})}(\beta ))$$
(9)
and the equality holds if and only if the number of sites $`i`$ with $`n_k(\beta ,i)=n_k^{(\mathrm{max})}(\beta )`$ and $`n_k(𝐇_k(\beta ),i)=n_k^{(\mathrm{max})}(\beta )1`$ equals the number of sites $`j`$ with $`n_k(\beta ,j)=n_k^{(\mathrm{max})}(\beta )1`$ and $`n_k(𝐇_k(\beta ),j)=n_k^{(\mathrm{max})}(\beta )`$. Eq. (8) demands that $`n_k(\beta ,jk)=n_k^{(\mathrm{max})}(\beta )`$ and hence no car can hop to the site $`jk`$, so we also have $`n_k(𝐇_k(\beta ),jk)=n_k^{(\mathrm{max})}(\beta )1`$. Therefore, the strict inequality holds in Eq. (9) if there exits a site $`i`$ such that $`n_k(\beta ,ik+1)=n_k^{(\mathrm{max})}(\beta )`$, $`n_k(\beta ,i+1)<n_k^{(\mathrm{max})}(\beta )1`$, $`\beta (i)=1`$ and $`\beta (i+1)=0`$.

Since we assume that $`\mathrm{\Delta }_k(\alpha )2`$, we claim that we can always find $`1iN`$ and $`j0`$ such that $`n_k^{(\mathrm{max})}(\beta )=n_k(\beta ,ik+1)>n_k^{(\mathrm{max})}(\beta )1=n_k(\beta ,i+1)=n_k(\beta ,i+k+1)=\mathrm{}=n_k(\beta ,i+jk+1)>n_k(\beta ,i+(j+1)k+1)`$. Otherwise, suppose that for some $`i^{\prime \prime }`$, $`n_k(\beta ,i^{\prime \prime }+mk+1)`$ is equal to either $`n_k^{(\mathrm{max})}(\beta )`$ or $`n_k^{(\mathrm{max})}(\beta )1`$ for all $`m`$. Hence, the density $`\rho `$ satisfies $`n_k^{(\mathrm{max})}(\beta )1k\rho n_k^{(\mathrm{max})}(\beta )`$. By the assumption that $`\mathrm{\Delta }_k(\alpha )2`$, there must be some $`i^{}`$ such that $`n_k(\beta ,i^{}+1)n_k^{(\mathrm{max})}(\beta )2`$. The conclusion on the density forces that for some $`m`$, $`n_k(\beta ,i^{}+mk+1)=n_k^{(\mathrm{max})}(\beta )`$. That is the claim.

Lemma 2 tells us that a car will hop from site $`i`$ to $`i+1`$ and hence $`n_k(ik+1)`$ is reduced in no more than $`k`$ time steps. That is, there exists $`r`$ with $`1rk`$ such that $`n_k(𝐇_k^r(\beta ),ik+1)<n_k(\beta ,ik+1)`$. Besides, $`n_k(𝐇_k^r(\beta ),i+1)=n_k^{(\mathrm{max})}(\beta )`$ if $`j2`$. Inductively, in no more than $`ak\frac{j+1}{2}`$ time steps, number of sites with local number equals $`n_k^{(\mathrm{max})}(\beta )`$ must be reduced by at least one. In other words, $`M_k(𝐇_k^a(\beta ),n_k^{(\mathrm{max})}(\beta ))<M_k(\beta ,n_k^{(\mathrm{max})}(\beta ))`$. In the above discussion, it is clear that a packet of cars with $`k`$th order local number $`n_k^{(\mathrm{max})}(\beta )`$ initially located around site $`i`$ is moving from left to right at a speed of at least 1 site per time step until it hops into a region with $`k`$th order local number less than $`n_k^{(\mathrm{max})}(\beta )1`$. Thus, this packet of cars may prevent another packet of $`k`$th order local number $`n_k^{(\mathrm{max})}`$ cars in its left hand side from moving at most $`k`$ times. Inductively, if $`n_k(\beta ,irk+1)=n_k^{(\mathrm{max})}(\beta )`$, then a car will begin to hop from site $`irk`$ to $`irk+1`$ in no more than $`rk`$ time steps. After that, this packet of cars will move at a speed of at least 1 site per time step from left to right provided that $`\mathrm{\Delta }_k`$ of the configuration is still greater than 1. By CP symmetry, a similar conclusion can be drawn for sites with $`k`$th order local number equals to $`n_k^{(\mathrm{min})}`$.

Since a site with $`k`$th order local number $`n_k^{(\mathrm{max})}`$ and another site with $`k`$th order local number $`n_k^{(\mathrm{min})}`$ separate by at most $`N1`$ sites, so the above discussions imply that in at most $`2k\frac{1}{2}\frac{N}{k}`$ time steps, $`\mathrm{\Delta }_k`$ is reduced by at least one until $`\mathrm{\Delta }_k1`$. Hence, within $`\mathrm{}2k(k1)\frac{1}{2}\frac{N}{k}`$ time steps, $`\mathrm{\Delta }_k<2`$. $`\mathrm{}`$

Combining Lemmas 1 and 3, we know that the maximum fluctuation amplitude in car density evolves towards the minimum possible value under the repeated action of $`𝐇_k`$. We remark that relaxation time estimate $`\mathrm{}`$ in the above Lemma is rather conservative. It is not difficult to reduce this estimation by a factor of two or more. Nevertheless, for the purpose of solving the GDCP, the present estimation which states that $`\mathrm{}=\text{O}(kN)`$ for $`k<N`$ is already enough.

Our investigation so far can be summarized in the following theorem.

###### Theorem 1

Let $`\alpha `$ be a bit string of length $`N`$ and $`\mathrm{}\mathrm{}(k)2k(k2)\frac{1}{2}\frac{N}{k}`$. Then the bit string $`\beta 𝐇_k^{\mathrm{}}(\alpha )`$ has the following properties:

(a) The $`k`$th order local number $`n_k(\beta ,i)`$ is equal to either $`k\rho `$ or $`k\rho `$;

(b) Suppose that $`𝐇_k(\beta )\beta `$. If $`\rho (\alpha )1/2`$, then $`\beta `$ does not contain two consecutive $`1`$s as its substring. Similarly, if $`\rho (\alpha )1/2`$, then $`\beta `$ does not contain two consecutive $`0`$s as its substring. Thus, if $`\rho (\alpha )1/2`$, a car at site $`i`$ in the string $`\beta `$ hops to the right under $`𝐇_k`$ if and only if $`k\rho =n_k(ik+1)>n_k(i+1)=k\rho `$. Similarly, if $`\rho 1/2`$, an empty site $`i`$ in the string $`\beta `$ hops to the left if and only if $`k\rho =n_k(ik)>n_k(i)=k\rho `$.

Proof: We only need to prove (b) as (a) is already contained in the proof of Lemma 3.

To prove (b), we use part (a) of this Theorem. It tells us that $`n_k(\beta ,i)`$ equals either $`k\rho `$ or $`k\rho `$. We denote the minimum distance between two successive cars in the bit string $`\beta `$ by $`d`$, that is, $`d=\mathrm{min}\{ij:\beta (i)=1,\beta (j)=1\text{ and }n_{ij}(\beta ,i)=1\}`$. Since $`\mathrm{\Delta }_k=1`$, Lemmas 1 and 3 imply that $`k\rho `$. Hence, the maximum distance between $`k\rho `$ cars in the string $`\beta `$ is greater than or equals to $`k+1`$. Thus, $`dk\rho k+1`$. For $`\rho 1/2`$,

$`d`$ $``$ $`{\displaystyle \frac{k+1}{k\rho }}`$ (10)
$``$ $`{\displaystyle \frac{k+1}{k/2+1/2}}`$ (11)
$`=`$ $`2.`$ (12)
As a result, we conclude that $`\beta `$ does not contain the substring $`11`$ if $`\rho 1/2`$. By CP symmetry, $`\alpha `$ does not contain the substring $`00`$ whenever $`\rho 1/2`$.

The remaining assertion of part (b) follows directly from Eq. (8). $`\mathrm{}`$

### B Separation Automaton

With the GDCP as stated, we need to distinguish the two cases, namely, (1) $`\alpha =0^N`$ and $`f(0)0`$, and (2) $`0<\rho (\alpha )`$ and $`f(\rho (\alpha ))>0`$. In order to do so, we need to tell if the bit string $`\alpha `$ is equal to $`0^N`$ or not. It can be done using the following automaton $`𝐒_k`$ together with $`𝐇_k`$. In a similar way, we also need to distinguish the case of $`\alpha =1^N`$ and $`\alpha 1^N`$. It can be done using a conjugate automaton $`\overline{𝐒}_k`$. These two automata $`𝐒_k`$ and $`\overline{𝐒}_k`$ are collectively known as the $`k`$th order separation automaton.

###### Rule 2 ($`k`$th order separation rule)

We denote this CA rule by $`𝐒_k`$. The state of site $`i`$ in the next time step $`𝐒_k[\alpha ](i)`$ is given by:

$`𝐒_k[\alpha ](i)=\{\begin{array}{cc}1& \text{if }\alpha (ik)=1\text{ and }n_k(ik)\hfill \\ & =1,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}`$ (17)
We denote its conjugate CA rule by $`\overline{𝐒}_k`$. That is,

$`\overline{𝐒}_k[\alpha ](i)=\{\begin{array}{cc}0& \text{if }\alpha (i)=0\text{ and }n_k(ik)=\hfill \\ & k1,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}`$ (21)
###### Theorem 2

Let $`\alpha `$ be a bit string of length $`N`$. Then

$$\{\begin{array}{cc}\rho (\beta )=0\hfill & \text{if }\rho (\alpha )=0,\hfill \\ \frac{1}{k}\rho (\beta )<\frac{2}{k}\hfill & \text{if }0<\rho (\alpha )<\frac{1}{k},\hfill \\ \beta =\gamma \text{ and }\rho (\beta )=\rho (\alpha )\hfill & \text{otherwise},\hfill \end{array}$$
(23)
where $`\beta 𝐒_k^{N/k}𝐇_k^{\mathrm{}}(\alpha )`$ and $`\gamma =𝐇_k^{\mathrm{}}(\alpha )`$. Similarly,

$$\{\begin{array}{cc}\rho (\delta )=1\hfill & \text{if }\rho (\alpha )=1,\hfill \\ \frac{k2}{k}\rho (\delta )<\frac{k1}{k}\hfill & \text{if }\frac{k1}{k}<\rho (\alpha )<1,\hfill \\ \delta =\gamma \text{ and }\rho (\delta )=\rho (\alpha )\hfill & \text{otherwise},\hfill \end{array}$$
(24)
where $`\delta \overline{𝐒}_k^{N/k}𝐇_k^{\mathrm{}}(\alpha )`$.

Proof: If $`\rho (\alpha )=0`$, then $`\alpha =0^N`$ (this notation denotes $`N`$ consecutive $`0`$s and we shall use similar notations for a bit string) and hence $`\beta =0^N`$ and $`\rho (\beta )=0`$.

If $`\rho (\alpha )1/k`$, then Theorem 1 tells us that $`n_k(\gamma ,i)>0`$ for all $`i`$. Hence, from Eq. (17), $`\beta =\gamma `$ and $`\rho (\beta )=\rho (\alpha )`$.

Finally, if $`0<\rho (\alpha )<1/k`$, then Theorem 1 implies that $`n_k(\gamma ,i)`$ is equal to either $`0`$ or $`1`$ for all $`i`$. Moreover, at least one bit in the string $`\gamma `$ is $`1`$. Thus, it is straight forward to check that applying $`𝐒_k^{N/k}`$ to $`\gamma `$ makes $`1n_k(\beta ,i)2`$ for all $`i`$ and $`1/k\rho (\beta )<2/k`$.

The proof for the conjugate separation rule $`\overline{𝐒}_k`$ is similar. $`\mathrm{}`$

Thus, $`𝐒_k^{N/k}𝐇_k^{\mathrm{}}`$ separates the string $`0^N`$ from the rest in the sense that no string in the form $`𝐒_k^{N/k}𝐇_k^{\mathrm{}}(\alpha )`$ has a density of $`1`$s in the interval $`(0,1/k)`$. This is the reason why we call $`𝐒_k`$ the $`k`$th order separation automaton.

### C Inversion Automaton

This CA rule and the next one (the exchange automaton) are two technical CA rules to transform the bit string to the form we desired. They are needed to correctly solve the GDCP for input strings $`0^N`$ and $`1^N`$.

###### Rule 3 ($`k`$th order inversion rule)

We denote this CA rule by $`𝐈_k`$. The state of site $`i`$ in the next time step $`𝐈_k[\alpha ](i)`$ is given by:

$`𝐈_k[\alpha ](i)=\{\begin{array}{cc}1& \text{if }n_k(i)=0,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}`$ (28)
We denote its conjugate CA rule by $`\overline{𝐈}_k`$. In other words,

$`\overline{𝐈}_k[\alpha ](i)=\{\begin{array}{cc}0& \text{if }n_k(i)=k,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}`$ (31)
A direct consequence of Theorem 1 and Eqs. (28)–(31) is:

###### Theorem 3

Let $`\alpha `$ be a bit string of length $`N`$ and $`\beta 𝐈_k𝐇_k^{\mathrm{}}(\alpha )`$. Then $`\rho (\beta )=1`$ if $`\rho (\alpha )=0`$, and $`\rho (\beta )=\rho (\alpha )`$ if $`\rho (\alpha )1/k`$. In fact, the bit string $`𝐇_k^{\mathrm{}}(\alpha )`$ is a fixed point of $`𝐈_k`$ provided that $`\rho (\alpha )1/k`$. Similarly, if $`\gamma \overline{𝐈}_k𝐇_k^{\mathrm{}}(\alpha )`$, then $`\rho (\gamma )=0`$ if $`\rho (\alpha )=1`$, and $`𝐇_k^{\mathrm{}}(\alpha )`$ is a fixed point of $`\overline{𝐈}_k`$ if $`\rho (\alpha )(k1)/k`$.

### D Exchange Automaton

###### Rule 4 ($`k`$th order exchange rule)

We denote this CA rule by $`𝐄_k`$. The state of site $`i`$ in the next time step $`𝐄_k[\alpha ](i)`$ is given by:

$`𝐄_k[\alpha ](i)=\{\begin{array}{cc}1& \text{if }n_k(i)=0,\hfill \\ 0& \text{if }n_k(i)=k,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}`$ (35)
The following theorem is a direct consequence of Theorem 1 and Eq. (35):

###### Theorem 4

Let $`\alpha `$ be a bit string of length $`N`$. Then $`\beta 𝐄_k𝐇_k^{\mathrm{}}(\alpha )=1^N`$ if $`\alpha =0^N`$, $`\beta =0^N`$ if $`\alpha =1^N`$. Moreover, $`𝐇_k^{\mathrm{}}(\alpha )`$ is a fixed point of $`𝐄_k`$ if $`1/k\rho (k1)/k`$.

### E Function Automaton

The two automata introduced in this subsection are derived from the continuous function in question. What we want it to achieve in the first automaton $`𝐅_f`$ is that after applying it once, there will be a substring of $`0^{2q}`$ or $`1^{2q}`$ according to the $`\text{sgn}(f(\rho ))`$ provided that $`\rho `$ is not in the form $`r/q`$ for some $`r`$. This substring will be further manipulated by the next automaton. The second automaton $`\stackrel{~}{𝐅}_f`$ is used to classify a bit string with $`\rho `$ in the form $`r/q`$ for some $`r`$.

###### Rule 5 (function rule)

Let $`f(x)`$ be the continuous function specified in GDCP. We denote the discontinuous points in $`[0,1]`$ by $`p_i/q`$, where $`p_i,q^+\{0\}`$. (Here we choose $`q`$ to be the smallest positive integral denominators of all the expressions $`p_i/q`$.) Recall in Section II that we require $`f(\frac{1}{2q})`$ and $`f(\frac{2q1}{2q})`$ to be non-zero. We denote the function CA rule associated with $`f(x)`$ by $`𝐅_f`$. The state of the site $`i`$ in the next time step $`𝐅_f[\alpha ](i)`$ is given by:

$`𝐅_f[\alpha ](i)=\{\begin{array}{cc}\theta (f(\frac{2k+1}{4q}))& \text{if }n_{4q}(ij)=2k+1\hfill \\ & \text{ for some }0j2q1,\hfill \\ & k\text{ and }f(\frac{2k+1}{4q})0,\hfill \\ \alpha (i)& \text{otherwise},\hfill \end{array}`$ (41)
where

$$\theta (x)=\{\begin{array}{cc}1\hfill & \text{if }x>0,\hfill \\ 0\hfill & \text{if }x0.\hfill \end{array}$$
(42)
In addition, we denote the associated function CA rule of $`f(x)`$ by $`\stackrel{~}{𝐅}_f`$. The state of site $`i`$ in the next time step is given by:

$`\stackrel{~}{𝐅}_f[\alpha ](i)=\{\begin{array}{cc}\theta (f(\frac{k}{2q}))& \text{if }n_{2q}(i)=k,0<k<2q,\hfill \\ & \text{and }f(\frac{k}{2q})0,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}`$ (46)
###### Theorem 5

We use the notations in the function rule. Let $`\alpha `$ be a bit string of length $`N`$. Then $`\beta 𝐅_f𝐇_{2q}^{\mathrm{}}(\alpha )`$ equals $`0^N`$ if $`\alpha =0^N`$, $`\beta =1^N`$ if $`\alpha =1^N`$. More importantly, if $`1/2q\rho (\alpha )(2q1)/2q`$ and $`\rho (\alpha )`$ is not in the form $`r/2q`$ for some integer $`r`$, then $`\beta `$ contains the substring $`0^{2q}`$ if and only if $`f(\rho (\alpha ))<0`$ while $`\beta `$ contains the substring $`1^{2q}`$ if and only if $`f(\rho (\alpha ))>0`$. Furthermore, $`𝐇_{2q}^{\mathrm{}}(\alpha )`$ is a fixed point of $`𝐅_f`$ provided that either $`f(\rho (\alpha ))=0`$ or $`\rho (\alpha )`$ is in the form $`r/2q`$ for some $`r=1,2,\mathrm{},2q1`$.

Proof: Clearly $`0^N`$ and $`1^N`$ are fixed points of both $`𝐇_{2q}`$ and $`𝐅_f`$. Moreover, Theorem 1 demands that $`n_{2q}(𝐇_{2q}^{\mathrm{}}(\alpha ),i)=r`$ for all $`i`$ provided that $`\rho (\alpha )=r/2q`$ for some $`r=1,2,\mathrm{},2q1`$. Thus Eq. (8) implies in this case that $`𝐇_{2q}^{\mathrm{}}(\alpha )`$ is a fixed point of $`𝐅_f`$. Similarly, Eq. (41) implies that $`𝐇_{2q}^{\mathrm{}}(\alpha )`$ is a fixed point of $`𝐅_f`$ provided that $`f(\rho (\alpha ))=0`$. So it remains for us to show the validity of this Theorem when $`1/2q\rho (\alpha )(2q1)/2q`$ and $`\rho (\alpha )`$ is not in the form $`r/2q`$ for some integer $`r`$.

Suppose $`\rho (\alpha )`$ is not in the form $`r/2q`$ for some integer $`r`$ and $`1/2q\rho (\alpha )(2q1)/2q`$. Theorem 1 together with the fact that periodic boundary conditions are imposed on the string $`\alpha `$ imply that we can always find $`i`$ and $`j`$ such that $`n_{2q}(𝐇_{2q}^{\mathrm{}}(\alpha ),i)=n_{2q}(𝐇_{2q}^{\mathrm{}}(\alpha ),i+2q)+1`$ and $`n_{2q}(𝐇_{2q}^{\mathrm{}}(\alpha ),j)=n_{2q}(𝐇_{2q}^{\mathrm{}}(\alpha ),j+2q)1`$. Hence, $`n_{4q}(𝐇_{2q}^{\mathrm{}}(\alpha ),i)`$ and $`n_{4q}(𝐇_{2q}^{\mathrm{}}(\alpha ),j)`$ are odd numbers. Since all the discontinuous points of $`\text{sgn}(f)`$ in the interval $`[0,1]`$ are in the form $`p_i/q`$, so for each fixed $`r=0,1,\mathrm{},2q1`$, $`\text{sgn}(f(x))=\text{sgn}(f(y))`$ for all $`x,y(r/2q,(r+1)/2q)`$. Therefore, from Eq. (41), either $`n_{2q}(𝐅_f𝐇_{2q}^{\mathrm{}}(\alpha ),i)`$ or $`n_{2q}(𝐅_f𝐇_{2q}^{\mathrm{}}(\alpha ),j)`$ equals $`2q`$ if $`f(\rho (\alpha ))>0`$. Besides, either $`n_{2q}(𝐅_f𝐇_{2q}^{\mathrm{}}(\alpha ),i)`$ or $`n_{2q}(𝐅_f𝐇_{2q}^{\mathrm{}}(\alpha ),j)`$ equals $`0`$ if $`f(\rho (\alpha ))<0`$. As $`1/2q\rho (\alpha )(2q1)/2q`$, Theorem 1 tells us that $`12q\rho (\alpha )n_{2q}(𝐇_{2q}^{\mathrm{}}(\alpha ),i)2q\rho (\alpha )2q1`$ for all $`i`$. Hence Eq. (41) implies that it is not possible for the string $`\beta `$ to contain both $`0^{2q}`$ and $`1^{2q}`$ as substrings. That is to say, the function rule maps a portion of $`𝐇_{2q}^{\mathrm{}}(\alpha )`$ to $`1^{2q}`$ if and only if $`f(\rho (\alpha ))>0`$ and similarly it maps a portion of $`𝐇_{2q}^{\mathrm{}}(\alpha )`$ to $`0^{2q}`$ if and only if $`f(\rho (\alpha ))<0`$. $`\mathrm{}`$

###### Theorem 6

We use the notations of the function rule. Let $`\alpha `$ be a bit string of length $`N`$. Then $`\beta \stackrel{~}{𝐅}_f𝐇_{2q}^{\mathrm{}}(\alpha )`$ equals $`0^N`$ if $`\rho (\alpha )=r/2q`$ for some $`r=1,2,\mathrm{},2q1`$ and $`f(r/2q)<0`$. Similarly, $`\beta =1^N`$ if $`\rho (\alpha )=r/2q`$ for some $`r=1,2,\mathrm{},2q1`$ and $`f(r/2q)>0`$. Moreover, $`𝐇_{2q}^{\mathrm{}}(\alpha )`$ is a fixed point of $`\stackrel{~}{𝐅}_f`$ if (a) $`\alpha =0^N`$, or (b) $`\alpha =1^N`$, or (c) $`0<\rho (\alpha )<1`$ and $`f(\rho (\alpha ))=0`$.

Proof: Direct application of Theorem 1 and Eq. (46). $`\mathrm{}`$

### F Propagation Automaton

After applying the function automaton $`𝐅_f`$, there will be a substring of $`0^{2q}`$ or $`1^{2q}`$ provided that $`\rho `$ is not in the form $`r/q`$ for some $`r`$ and $`f(\rho )0`$. To convert the whole bit string to the desired form, we have to propagate the substring to everywhere.

###### Rule 6 (propagation rule)

Let $`\alpha `$ be a bit string. We denote the propagation rule by $`𝐏_f`$. The effect of $`𝐏_f`$ on each bit is given by

$`𝐏_f[\alpha ](i)=\{\begin{array}{cc}1& \text{if }n_{2q}(i+1)=2q\hfill \\ 0& \text{if }n_{2q}(i+1)=0,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}`$ (50)
###### Theorem 7

We use the notations of the function rule. Let $`\alpha `$ be a bit string of length $`N`$ and $`\beta \stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f𝐇_{2q}^{\mathrm{}(2q)}(\alpha )`$.

(a) The strings $`0^N`$ and $`1^N`$ are fixed points of $`\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f𝐇_{2q}^{\mathrm{}(2q)}`$. Moreover, $`\beta =0^N`$ provided that $`0<\rho (\alpha )<1/2q`$ and $`f(\frac{1}{2q})<0`$. Similarly, $`\beta =1^N`$ provided that $`(2q1)/2q<\rho (\alpha )<1`$ and $`f(\frac{2q1}{2q})>0`$.

(b) Suppose $`1/2q\rho (\alpha )(2q1)/2q`$. Then $`\beta =0^N`$ if and only if $`f(\rho (\alpha ))<0`$. Moreover, $`\beta =1^N`$ if and only if $`f(\rho (\alpha ))>0`$. Finally, $`\beta =𝐇_{2q}^{\mathrm{}}(\alpha )`$ and hence $`\rho (\beta )=\rho (\alpha )`$ if and only if $`f(\rho (\alpha ))=0`$.

Proof: To show that $`0^N`$ and $`1^N`$ are fixed points of $`\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f𝐇_{2q}^{\mathrm{}}`$ is straight forward. Suppose $`0<\rho (\alpha )<1/2q`$ and $`f(1/2q)<0`$. Then, Theorem 1 implies that $`n_{2q}(𝐇_{2q}^{\mathrm{}}(\alpha ),i)1`$ with equality holds for some $`i`$. Since $`f(1/2q)<0`$, so by continuity of $`f`$ and the distribution of discontinuous points of $`\text{sgn}(f)`$, we know that $`f(x)<0`$ whenever $`0<x<1/q`$. Hence $`𝐅_f𝐇_{2q}^{\mathrm{}}(\alpha )`$ contains the substring $`0^{2q}`$ and does not contain the substring $`1^{2q}`$. Thus by Eq. (50) and Theorem 6, we conclude that $`\beta =0^N`$. The proof of $`\beta =1^N`$ provided that $`(2q1)/2q<\rho (\alpha )<1`$ and $`f(\frac{2q1}{2q})>0`$ is similar. So, we have proved the validity of part (a).

We know from Theorem 1 that $`𝐇_{2q}^{\mathrm{}}(\alpha )`$ is a fixed point of $`𝐏_f`$ provided that $`1/2q\rho (\alpha )(2q1)/2q`$. Therefore, part (b) of this Theorem follows directly from Theorems 5, 6 and Eq. (50). $`\mathrm{}`$

## IV Generalized Density Classification Automata

After introducing all the necessary building blocks in the last section, we are ready to report our solution of the GDCP.

###### Theorem 8

Let $`\alpha `$ be a bit string of length $`N`$. Let $`f(x)`$ be a continuous function. Denote the rational discontinuous points of $`\text{sgn}(f(x))`$ by $`p_i/q`$ with $`p_i,q^+\{0\}`$. (Here $`q`$ is chosen to be the smallest positive integral denominator for the expressions $`p_i/q`$.) Suppose further that $`f(\frac{1}{2q})`$ and $`f(\frac{2q1}{2q})`$ are both non-zero, then the following sequence of CA rules solves the GDCP for the function $`f(x)`$:

$`𝐂_f`$ $`=`$ $`\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f\left(𝐄_{2q}\right)^{a5}\left(\overline{𝐈}_{2q}\right)^{a4}\left(𝐈_{2q}\right)^{a3}`$ (53)
$`(𝐇_{2q}^{\mathrm{}(2q)}\overline{𝐒}_{2q}^{N/2q})^{a2}(𝐇_{2q}^{\mathrm{}(2q)}𝐒_{2q}^{N/2q})^{a1}`$
$`𝐇_{2q}^{\mathrm{}(2q)},`$
where $`a1=1`$ if $`f(\frac{1}{2q})>0`$, $`a1=0`$ otherwise; $`a2=1`$ if $`f(\frac{2q1}{2q})<0`$, $`a2=0`$ otherwise; $`a3=1`$ if $`f(0)>0`$ and $`f(1)0`$, $`a3=0`$ otherwise; $`a4=1`$ if $`f(1)<0`$ and $`f(0)0`$, $`a4=0`$ otherwise; $`a5=1`$ if $`f(0)>0`$ and $`f(1)<0`$ and $`a5=0`$ otherwise.

Before we prove this theorem, let us first informally explain how it works. The $`𝐇_{2q}^{\mathrm{}(2q)}`$ in the right-most part of Eq. (53) makes the density of car uniform. Then the $`\left(𝐇_{2q}^{\mathrm{}(2q)}𝐒_{2q}^{N/2q}\right)^{a1}`$ term first separates $`\rho =0`$ from $`0<\rho <1/2q`$ and then makes the resultant bit string uniform in car density whenever $`f(\frac{1}{2q})`$ and hence also $`f(x)>0`$ for all $`0<x<1/2q`$. Similarly, the $`\left(𝐇_{2q}^{\mathrm{}(2q)}\overline{𝐒}_{2q}^{N/2q}\right)^{a2}`$ term first separates $`\rho =1`$ from $`(2q1)/2q<\rho <1`$ and then makes the resultant bit string uniform in car density whenever $`f(\frac{2q1}{2q})`$ and hence also $`f(x)<0`$ for all $`(2q1)/2q<x<1`$. Next, notice that $`a3`$ and $`a5`$ will not simultaneously equal to one, and similarly $`a4`$ and $`a5`$ will not simultaneously equal to one, the $`\left(𝐄_{2q}\right)^{a5}\left(\overline{𝐈}_{2q}\right)^{a4}\left(𝐈_{2q}\right)^{a3}`$ term correctly deals with the GDCP for $`\rho =0`$ and $`1`$. This is followed by the term $`𝐏_f^{N2q}𝐅_f`$ which correctly classifies those $`\rho `$ not in the form $`r/2q`$. Finally, the term $`\stackrel{~}{𝐅}_f`$ settles the remaining case of $`\rho `$ in the form $`r/2q`$ with $`r0`$ or $`2q`$.

Proof: We divide the proof into the following four cases:

Case (a): $`\rho (\alpha )=0`$ or $`1`$, that is, $`\alpha =0^N`$ or $`1^N`$: in this case, $`𝐂_f=\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f\left(𝐄_{2q}\right)^{a5}\left(\overline{𝐈}_{2q}\right)^{a4}\left(𝐈_{2q}\right)^{a3}`$. So by Theorems 3 and 4, $`𝐂_f(0^N)=\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f(x^N)`$ where $`x=\text{sgn}(f(0))`$ and similarly $`𝐂_f(1^N)=\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f(y^N)`$ where $`y=\text{sgn}(f(1))`$. Hence, from Eqs. (41), (46) and (50), the theorem holds for $`\rho (\alpha )=0`$ or $`1`$.

Case (b): $`1/2q\rho (\alpha )(2q1)/2q`$: in this case, Theorems 2, 3 and 4 tell us that $`𝐂_f=\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f𝐇_{2q}^{\mathrm{}(2q)}`$. Hence, this case is settled by applying Theorem 7.

Case (c): $`0<\rho (\alpha )<1/2q`$: in this case, the continuity of $`f`$ together with our assumptions that $`f(1/2q)0`$ and discontinuous points of $`\text{sgn}(f(x))`$ are in the form $`r/q`$ for some $`r`$ demand that $`f`$ can be further divided into the following two subcases, namely, (1) $`f(x)>0`$ for all $`0<x<1/q`$, and (2) $`f(x)<0`$ for all $`0<x<1/q`$.

In subcase (1), $`a1=1`$. Theorem 2 tells us that $`1/2q\rho (𝐒_{2q}^{N/2q}𝐇_{2q}^{\mathrm{}}(\alpha ))<1/q`$. From Theorem 3, we know that $`𝐂_f(\alpha )=\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f𝐇_{2q}^{\mathrm{}(2q)}𝐒_{2q}^{N/2q}𝐇_{2q}^{\mathrm{}(2q)}(\alpha )`$. Combining with Theorem 7, $`𝐂_f(\alpha )=1^N=(\text{sgn}(f(\rho )))^N`$.

In subcase (2), the continuity of $`f`$ implies that $`a1=a3=a5=0`$ and hence $`𝐂_f(\alpha )=\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f𝐇_{2q}^{\mathrm{}(2q)}(\alpha )`$. So, applying Theorem 7 gives $`𝐂_f(\alpha )=0^N=(\text{sgn}(f(\rho )))^N`$.

Therefore, Eq. (53) correctly classifies bit string with $`0<\rho <1/2q`$.

Case (d): $`(2q1)/2q<\rho (\alpha )<1`$: The proof of this case is similar to that of case (c) and we are not going to write the details here.

In summary, $`𝐂_f(\alpha )=0^N`$ if $`f(\rho )<0`$, $`𝐂_f(\alpha )=1^N`$ if $`f(\rho )>0`$, and $`𝐂_f(\alpha )=𝐇_{2q}^{\mathrm{}(2q)}(\alpha )`$ if $`f(\rho )=0`$. Consequently, the result of the GDCP can be read out from any $`2q`$ consecutive sites of the final output bit string. More precisely, if we find that such substring equals $`0^{2q}`$, then either $`f(\rho )<0`$ or $`\rho =0`$ and $`f(0)=0`$. If such substring is $`1^{2q}`$, then either $`f(\rho )>0`$ or $`\rho =1`$ and $`f(1)=0`$. Lastly, if such substring contains both 0 and 1, then $`\rho 0`$, $`\rho 1`$ and $`f(\rho )=0`$. $`\mathrm{}`$

## V Simple Solutions To Certain Special Cases

Theorem 8 provides a solution to the GDCP involving all the nine automata introduced in Section III. Nonetheless, it does not mean that solution of *any* GDCP have to be that complicated. In this section, we report simple solutions to certain useful GDCPs. Comparing to the GDCP, solutions to the following problems are rather straight-forward. So the presentation in this section is brief.

### A Cases Related To Rational Density Classification

The simplest non-trivial case of GDCP is the rational density problem which chooses $`f(x)=x\rho _c`$ for a fixed rational number $`0<\rho _c<1`$. Chau *et al.* solved this problem by the following two automata .

###### Rule 7 (modified traffic rule)

Let $`\alpha `$ be a bit string of length $`N`$ and $`\rho _c=p/q`$ where $`p,q^+`$ with $`p`$ and $`q`$ are relatively prime. Then the modified traffic rule is give by

$$𝐓_\rho [\alpha ](i)=\{\begin{array}{cc}1& \text{if }\alpha (i)=0,\alpha (i1)=1,\text{ and}\hfill \\ & n_{q1}(i)p1,\hfill \\ 0& \text{if }\alpha (i)=1,\alpha (i+1)=0,\text{ and}\hfill \\ & n_{q1}(i+1)p1,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}$$
(54)
###### Rule 8 (Modified Majority Rule)

Let $`\alpha `$ be a bit string of length $`N`$ and $`\rho _c=p/q`$ where $`p,q^+`$ with $`p`$ and $`q`$ are relatively prime. Then the modified majority rule is give by

$$𝐌_\rho [\alpha ](i)=\{\begin{array}{cc}1\hfill & \text{if }n_{2q+1}(iq)2p+1,\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$
(55)
More precisely, they showed that $`𝐌^{N/2(q1)}𝐓^{N(\mathrm{max}(q,2p)1)\mathrm{max}(qp,p)/pq+q2}`$ solves the rational density classification problem with $`f(x)=x\rho _c`$.

By applying $`𝐈_q`$, $`\overline{𝐈}_q`$ or $`𝐄_q`$ once to the resultant state of the rational density classification automata, it is clear that we can solve a number of related problems using three CAs, including $`f(x)=\rho _cx`$, $`f(x)=(x\rho _c)^2`$ and $`f(x)=(x\rho _c)^2`$.

### B Cases Related To Coarse-Grained Rational Density Classification

Another interesting and useful problem we have briefly mentioned in Section I is the so-called approximate rational density classification. Let us recall that if $`\rho _c=p/q`$ is a rational number, then solution to the rational density classification problem either by the method reported in Section IV or in Ref.  requires a rule table whose range scales linearly with $`q`$. Thus, it is more cost effective to classify a coarse-grained rational density. To achieve this task, we are required to solve the GDCP with the function $`f`$ given by Eq. (2) with $`\rho _{c1}<\rho _c<\rho _{c2}`$. An effective way to choose $`\rho _{c1}`$ and $`\rho _{c2}`$ is to use the continued fraction approximation of $`\rho _c`$. If the output string is $`1^N`$, we know that $`\rho `$ is greater than $`\rho _{c2}`$ and hence also $`\rho _c`$. Similarly, we know that $`\rho <\rho _c`$ if the output is $`0^N`$. If $`\rho _{c1}<\rho <\rho _{c2}`$, then we do not know if the $`\rho `$ is greater than $`\rho _c`$ or not. Fortunately, $`\rho `$ is preserved by the automata in this case and hence we may feed our output bit string to say the full rational density classification CAs for fine-grained density determination. In this way, we can efficiently solve the rational density classification problem with small rule table size with high probability for a randomly given input bit string. Performing a CA which is a function of output of another CA leads us to the notion of CA programming. We shall explore the power and weakness of CA programming elsewhere .

After pointing out the significance of the coarse-grained rational density classification problem, we report a solution involving only two CA rules. We write $`\rho _{c1}=p_1/q`$ and $`\rho _{c2}=p_2/q`$ as usual. The first CA rule is our car hopping automaton $`𝐇_q`$. (Clearly we cannot use $`𝐓`$ as we have two critical densities here.) The second CA rule is a variation of the propagation rule, as stated below.

###### Rule 9 (modified propagation rule)

Let $`\alpha `$ be a bit string. Then the modified propagation rule is given by

$$\stackrel{~}{𝐏}_{p_1,p_2,q}[\alpha ](i)=\{\begin{array}{cc}1& \text{if }n_q(i+j)>p_2\text{ for some}\hfill \\ & 1jq,\hfill \\ 0& \text{if }n_q(i+1)<p_1\text{ for some}\hfill \\ & 1jq,\hfill \\ \alpha (i)& \text{otherwise}.\hfill \end{array}$$
(56)
Clearly, if $`\rho >\rho _{c2}`$, there is a site $`i`$ such that $`n_q(𝐇_q^{\mathrm{}}(\alpha ),i)>p_2`$. Thus, $`\rho `$ increases to $`1`$ under the repeated application of $`\stackrel{~}{𝐏}_{p_1,p_2,q}`$. Similarly, $`\rho `$ decreases to $`0`$ under the repeated application of $`\stackrel{~}{𝐏}_{p_1,p_2,q}`$ if $`\rho <\rho _{c1}`$. In summary, we know that $`𝐏_{p_1,p_2,q}^{N/q}𝐇_q^{\mathrm{}(q)}`$ solves the coarse-grained rational density classification problem.

In a similar way, problems with $`f(x)=(x\rho _{c1})(x\rho _{c2})`$, $`f(x)=(x\rho _{c1})(x\rho _{c2})^2`$ and so on can be solved using four CAs.

### C Variation Of The Theme

Because of the difficulties in distinguishing between the strings $`0^N`$ and $`0^{N1}1`$, we introduce the separation automaton $`𝐒_k`$. Unfortunately, $`𝐒_k`$ is not car density conserving. This is precisely the reason why we impose the technical conditions that $`f(1/2q)0`$ and $`f((2q1)/2q)0`$. We remark that the above technical conditions can be waived provided that we relax the GDCP a bit. Instead of requiring that the density of 1s of the output string $`\beta `$ equals to that of the input string $`\alpha `$ if $`f(\rho (\alpha ))=0`$, we replace it by requiring that $`|f(\rho (\beta ))f(\rho (\alpha ))|<1/q`$. By doing so, it is clear that the GDCP can be solved even when $`f(1/2q)`$ or $`f((2q1)/2q)=0`$ by the following sequence of automata:

$`\stackrel{~}{𝐅}_f𝐏_f^{N2q}𝐅_f\left(𝐄_{2q}\right)^{a5}\left(\overline{𝐈}_{2q}\right)^{a4}\left(𝐈_{2q}\right)^{a3}`$ (57)
$`𝐇_{2q}^{\mathrm{}(2q)}\overline{𝐒}_{2q}^{N/2q}𝐇_{2q}^{\mathrm{}(2q)}𝐒_{2q}^{N/2q}𝐇_{2q}^{\mathrm{}(2q)},`$ (58)
where $`a3=1`$ if $`f(0)>0`$ and $`f(1)0`$, $`a3=0`$ otherwise; $`a4=1`$ if $`f(1)<0`$ and $`f(0)0`$, $`a4=0`$ otherwise; $`a5=1`$ if $`f(0)>0`$ and $`f(1)<0`$ and $`a5=0`$ otherwise.

However, we do not encourage the use of this relaxed definition of GDCP for the density of 1s is not preserved in case $`f(\rho )=0`$.

## VI Discussions

A few remarks are in order. First, Theorem 8 provides a CA solution to the GDCP with at most eight CA rules each with rule table of range $`4q`$. (Note that the number eight comes from the observation that we can combine $`𝐅_f\left(𝐄_{2q}\right)^{a5}\left(\overline{𝐈}_{2q}\right)^{a4}\left(𝐈_{2q}\right)^{a3}`$ together to form one single CA rule whose rule table size is still independent of the string length $`N`$.) Moreover, the total run time required scales as $`\text{O}(qN)`$ whenever $`q<N`$, making it asymptotically optimal up to a constant factor. The main ingredient used to solve the GDCP is the $`k`$th order traffic rule $`𝐇_k`$ whose repeated application leads to a uniformly distributed $`1`$s in the bit string in the sense that fluctuation of the $`k`$th order local number $`n_k(i)`$ does not exceed $`1`$.

We stress that the solution to the GDCP using a sequence of CAs is not unique. We have also found that a slightly different traffic rule involving $`2k+1`$ sites together with a generalized majority vote rule based on the work in Ref.  can also do the job. Nevertheless, this alternative method requires in general more than eight CA rules in succession .

We are not sure if the GDCP can be solved using fewer than eight CA rules. What we know from the result of Fukś is that density classification, being a special case of GDCP, cannot be solved using a single CA rule. Although certain special cases of the GDCP, such as the original density classification problem can be solved using two CA rules, we feel that it is highly unlikely to solve the full GDCP using just two CA rules because of the difficulties involved in separating the cases with $`\rho `$ close to $`0`$ and $`\rho `$ equals $`0`$ although we have provided solutions of the rational density classification and coarse-grained rational density classification problems using two CA rules in Section V.

Finally, we remark that the CA solution to the GDCP shows a rich flow diagram. The flow of $`\rho `$ under the action of $`𝐂_f`$ exhibits at most two stable fixed points at $`\rho =0`$ and $`1`$ corresponding to $`f(\rho )0`$, finitely many fixed points corresponding to the rational isolated roots of the equation $`f(x)=0`$, together with possibly infinitely many neutral fixed points corresponding to the remaining non-isolated zeros of $`f(x)=0`$ in the limit of $`N\mathrm{}`$. In this respect, sequence of CAs may lead to very interesting flow diagrams that are distinctive from those resulting from conventional continuous dynamical systems.

###### Acknowledgements.

This work is supported in part by the Hong Kong SAR Government RGC grant HKU 7098/00P. H.F.C. is also supported in part by the Outstanding Young Researcher Award of the University of Hong Kong.


format: text

text:
# Reprocessing the Hipparcos data for evolved giant stars II. Absolute magnitudes for the R-type carbon starsBased on observations from the Hipparcos astrometric satellite operated by the European Space Agency (ESA 1997)

## 1 Introduction

The Harvard spectroscopic classification of stars for the Henry Draper Catalogue recognized the first examples of chemically-peculiar stars, the carbon and S giants. Carbon stars are immediately recognizable by the presence of absorption bands of $`\mathrm{C}_2`$ at 4383 Å and 4737 Å and the 4216 Å band of CN (Shane 1928), and are chemically characterized by having C/O $`>`$ 1. Pickering (1896, 1908) showed that the carbon stars further subdivide into two spectral classes, the ‘warm’ R stars and the ‘cool’ N stars, and in the intervening years it has become increasingly apparent that these stars do not represent a continuum of properties but rather belong to two distinct classes. Further, Keenan (1942) noted that some members of the R spectral class were metal-poor and had high radial velocities and proper motions. These are now separately classified as CH stars. Several low-concentration globular clusters contain CH stars (Bond 1975; McClure 1984b); they are generally considered to be halo carbon stars. The most recent list of CH stars is by Bartkevičius (1996). Several additional types of carbon star have been recognized, including R CrB stars and dwarf carbon stars.

The revised classification system of Keenan (1993) is an attempt to provide consistent temperature, luminosity and abundance sequences among the different types of carbon stars. Three main classes are defined in this scheme: C-R$`n`$, C-N$`n`$, and C-H$`n`$, corresponding to the old R, N and CH types respectively, with $`n`$ being a homogeneous temperature index for the three sequences, corresponding to the G-K-M temperature sequence in “oxygen” stars. Unfortunately, spectral types based on this scheme are available for only a small fraction of carbon stars.

Since C/O $`<1`$ everywhere in the interstellar medium, in the Sun, and in most stars, the excess carbon in carbon stars must be the result of stellar nucleosynthesis in the star itself or in a binary companion. The many varieties of carbon stars are thus stars in the late stages of evolution or with evolved binary companions, and are preferentially formed in systems whose intrinsic metallicities (including the oxygen abundance) are low.

The N stars are understood in a general sense. They are very luminous, cool stars with shell hydrogen and helium burning and with 3$`\alpha `$-produced $`{}_{}{}^{12}\mathrm{C}`$ mixed to the surface by deep convection (Iben & Renzini 1983), although the details of how that mixing occurs are far from well understood. Other stellar types with enhanced carbon abundance, like CH and barium stars, are observed to be members of binary systems (see the discussions by McClure 1984a, 1997a; Jorissen et al. 1998), and their peculiar abundances can be attributed to mass transfer. The R CrB stars are variable hydrogen-deficient stars, and have shed most of their envelope. The dwarf carbon stars (Dahn et al. 1977; Green & Margon 1994) and the R stars remain a mystery. Like the N stars, the R stars are red giants, but their average luminosity, determined by statistical parallax methods (Vandervoort 1958; Scalo 1976; Dean 1976) is too low for shell helium burning. Further, their oxygen abundances are similar to that of the Sun (Dominy 1984), they do not exhibit s-process overabundances, and no R star has been found so far in a binary system (McClure 1997b), a statistically unlikely and surprising result. It has therefore been suggested that R stars might actually be coalesced binary systems. The remaining hypothesis is that these stars are helium core-burning stars or post helium core burning stars, with carbon produced by helium burning somehow introduced into their atmospheres, perhaps at the helium core flash (Scalo 1976; Dominy 1984). There is little direct evidence for this hypothesis, though, because of lack of information about the intrinsic luminosity function of the R stars or of their spatial density. This paper sets out to derive the luminosities of the R stars to attempt to discover their location on the Hertzsprung-Russell diagram and establish their evolutionary status.

The Hipparcos project (ESA 1997) made it possible for the first time to make direct estimates of the distances to giant carbon stars. However, as noted by Knapp (2001), the parallax errors for these stars are often far larger than expected. In this paper, we use new parallaxes derived from a re-reduction of the Hipparcos Intermediate Astrometric Data to show that essentially all the (early) R stars have the same absolute magnitude and color, and are located in the red clump region of the HR diagram. The Hipparcos parallaxes also allow us to derive the spatial density of the red clump stars and the fraction of these which are R stars; we show that they are very rare, far less than 1% of the red clump stars (Sect. 4). The carbon enhancements in R stars may therefore originate in the helium-burning interiors, perhaps as the result of a mixing in a rapidly rotating star spun up by the accretion of its companion (see Sect. 5). Sect. 2 discusses the astrometric, photometric, spectroscopic and variability data on which the results presented in this paper are based. The absolute magnitudes and colors are examined in Sect. 3, the space densities in Sect. 4, and the implications and conclusions are discussed in Sect. 5. The details of the re-reduction of the Hipparcos data will be discussed by Pourbaix et al. (2001a, Paper III) and the results for N-type carbon stars by Pourbaix et al. (2001b, Paper IV).

## 2 The data

### 2.1 Overview

The basic data for R stars, including the new parallax data, are collected in Tables 1 & 2. Stars with enhanced carbon abundances come in many spectral types: the N stars, the R stars, carbon white dwarfs, carbon-rich Wolf-Rayet stars, carbon cepheids, R CrB stars, barium stars, CH stars, and dwarf carbon stars, among others. As pointed out above, their chemical peculiarities are due to nucleosynthesis within the star itself, or its companion, and the task is to identify chemical peculiarities with particular evolutionary paths. This is carried out in the first instance by associating like objects, classifying them by spectral type, luminosity, color, and variability, and is made difficult both by the wide variety of stars with carbon enhancements, and by the often uncertain observational information. A given star can be classified as several different spectral types in several different papers, causing confusion in attempts to evaluate the common properties of given classes of stars (see the discussions by McClure 1997a, b; Wallerstein & Knapp 1998). Examples include HIP 12028 (HD 161115) which is classified as R by Vandervoort (1958), as CH by Keenan (1993) and as J by Ohnaka & Tsuji (1999), while HIP 85750 (BD$`+02^{}3336`$) is classified as R2 by Vandervoort (1958), as CH by Yamashita (1975), and as N by Barnbaum et al. (1996). Thus it is far from straightforward to decide, from the available data, whether the presence of a star in a given variability class with a spectral type atypical of that class demonstrates a range of spectral types in that variability class or is due to inadequate data. The infrared color-color diagram $`(JH,HK)`$ (Fig. 1) may nevertheless be of some help in the process of identifying misclassified stars, as the different types of carbon stars occupy specific locations in that diagram (see Sect. 2.2).

Of the many varieties of carbon star, the cool luminous carbon stars are of interest because they are expelling carbon-enhanced mass into the interstellar medium. Knapp (2001) identified about 320 carbon stars in the Hipparcos catalogue. An attempt was made to be complete (as far as the members of the Hipparcos catalogue are concerned) for the luminous cool carbon stars, i.e., the R and N stars (because these are the stars which are, or may be, losing mass). Although the Hipparcos catalogue itself is based only partly on a complete input catalogue (the Input Catalogue contained both complete samples of stars – designed as ‘Hipparcos survey stars’111Only 3 such stars (HIP 12028, HIP 62944 and HIP 84266 discussed herein) are present in the sample of R stars – and additional samples of stars of particular interest), it turns out to be reasonably complete for carbon stars to Hipparcos magnitude $`Hp`$ 9.5 (Knapp 2001) or to $`K7`$ (Fig. 6).

### 2.2 Photometry

We use the $`V`$ magnitude given in the Hipparcos catalogue (field H5). We acquired $`J,H`$ and $`K`$ photometry from the literature, as listed in Tables 1 & 2 along with the bibliographic reference. This was found with the aid of the electronic version of the literature compilation catalogue of Gezari et al. (1999). In addition, we extracted $`K_s`$ photometry from the Two Micron All Sky Survey (2MASS) on-line data release (Skrutskie 1997). In many cases, the stars are bright enough that they are saturated in the 2MASS data and we use older photometry. There are no systematic offsets evident among the various photometric measures for a given star, and the measurements (including the narrower 2MASS $`K_s`$ band magnitudes) agree to better than about 0.2 mag in almost all cases. We were able to find $`K`$ magnitudes for all but 24 stars. Although these observations were made at different epochs, R stars are not in general variable (Sect. 2.3) and so there is little or no uncertainty introduced into the $`V`$ or $`K`$ magnitudes by variability.

Fig. 1 presents the $`(JH,HK)`$ color-color diagram. It is immediately apparent that R stars occupy a very specific region of that diagram, which is also populated by CH stars. A few R stars appear to occupy the same region as N-type carbon stars, which is not surprising as most – if not all – late R-type carbon stars may actually be N stars (see the discussion in Sects. 2.3 and 2.4).

### 2.3 Variability

N stars are in general long-period variables: irregular (Lb), semi-regular (SR or SRb) or Mira (Mira or SRa) – see Kerschbaum & Hron (1994) and Wallerstein & Knapp (1998) for a discussion of the SRa and SRb stars. R stars generally do not appear in variable star catalogues. Of the 83 R stars in our sample, 18 appear in the General Catalogue of Variable Stars (Kholopov et al. 1998), but most of these are late R stars, as listed in Table 2. Most of the R stars of variability types Mira and SR are also losing mass, as indicated by their excess 12 $`\mu `$m emission (Table 2), and are therefore probably closely related to N stars.

### 2.4 Spectral Types

There are two major studies of R stars. Vandervoort (1958) observed a sample of 98 R stars selected from an objective prism survey. McClure (1997b) discusses a sample of 22 R stars. We have also used spectral types from Keenan (1993), Barnbaum et al. (1996), and other references. In toto, we have a sample of 83 R stars. The data are listed in Tables 1 & 2. Where available, we have listed the spectral type from R0 to R8.

Many of the remaining 317 carbon stars are spectroscopically classified only as carbon stars, and some of these may be R stars also. However, as the $`(JH,HK)`$ diagram shows (Fig. 1), not many non-R stars, apart from the CH stars, occupy the location of R stars in that diagram. CH stars must be treated separately from the R stars, as all CH stars are believed to be binary systems (McClure 1997a), and must therefore be processed with a binary astrometric model, as presented in Paper I (Pourbaix & Jorissen 2000).

Further, since there is often disagreement in the various references as to the spectral type of a given star (examples were given in Sect. 2.1), the ‘spectral purity’ of the sample of R stars collected in Tables 1 & 2 is best assessed by looking at the $`(JH,HK)`$ diagram.

The main source of confusion appears to be the fact that several late-type R stars from Table 2 are located in the region occupied by N stars. This is not totally surprising, as late R stars bear similarities with, or might even be identical to, N stars. In the following analysis, it will therefore be necessary to treat separately R stars with $`HK<0.3`$ \[or $`(VK)_0<4`$; see Fig. 1\] from those with $`HK0.3`$. Finally, the few R stars also classified as R CrB variables should be treated separately as well.

To stress the fact that the early- and late-type R stars in the present sample must be considered separately, they have been split into two separate lists (Tables 1 & 2 respectively). The assignment of a star as an early- or late-type R star is mainly based on the $`(VK)_0`$ index, with the threshold set at 4. The $`(VK)_0`$ index has preference over the R spectral subtype in case of conflicting classifications. When the $`(VK)_0`$ index is not available, a criterion based on the spectral type is used (with the threshold set at R3.5). It will be shown below that, with this choice for the thresholds, the two subsamples of R stars present homogeneous properties with respect to the R spectral subtype, to mass loss and to variability type, most late-type R stars being long-period variable stars, with circumstellar dust emission indicative of mass loss. The $`K[12]`$ color index (with $`K[12]=K+2.5\mathrm{log}F12/28.3`$, $`F12`$ being the flux density in the IRAS 12 $`\mu `$m band, expressed in Jy) is considered as a good indicator of (dust) mass loss, according to e.g., Fig. 21 of Jorissen & Knapp (1998). Non-mass-losing stars have $`K[12]`$ 0.7.

Late-type R stars are thus likely to belong to the mass-losing AGB, and are therefore not considered further in the following discussion, which focuses on R stars with $`(VK)_0<4`$.

### 2.5 Parallaxes

The Hipparcos catalogue (ESA 1997) gives parallax values at the 2$`\sigma `$ level or better \[i.e. $`\varpi /ϵ(\varpi )>`$ 2, where $`ϵ(\varpi )`$ is the quoted parallax uncertainty\] for 17 R stars, of which 15 are of types R0 – R2. The resulting absolute visual magnitudes for the early R stars cover a range of $`M_\mathrm{V}=2.8`$ to +4.1 (Knapp 2001). However, the parallax errors for many of the stars are larger, sometimes much larger, than the errors expected for the magnitudes and ecliptic coordinates of the stars. Of the nearly 320 carbon stars in the sample of Knapp (2001), only 25% (and only 18% of the R stars) have “2$`\sigma `$” parallaxes.

The Hipparcos Intermediate Astrometric Data (IAD; van Leeuwen & Evans 1998) for the entire sample of carbon stars were therefore reprocessed as described and Papers I & III. Therefore, only a brief outline of the method is given here.

The position, distance modulus and proper motion are the five parameters in the model fit to be adjusted by $`\chi ^2`$ minimization of the IAD abscissa residuals. Included in this fitting procedure is the rejection of outliers, defined as having a fit residual greater than three times the average of the residuals. In practice, two or three observations at most were rejected. Fitting the distance modulus ensures that the derived parallax $`\varpi `$ is always positive, as described in Paper I, but at the expense of asymmetric error bars and of a bias on $`\varpi `$. This bias is of any importance only when $`ϵ(\varpi )/\varpi 1`$, as shown in Paper III. The distance modulus is better behaved, and must be used for computing average absolute magnitudes, as further discussed in Sect. 3.

Another major difference with respect to the reduction scheme applied by the Hipparcos consortia resides in the bootstrap algorithm used to reject those data points which yield inconsistent FAST and NDAC solutions, as described in detail in Paper III.

Monte-Carlo simulations have shown that this reprocessing scheme of the IAD fails when the noise on the IAD is too large with respect to the true parallax, in that it yields absolute magnitudes that are too faint by as much as 5 magnitudes (i.e., parallaxes come out too large). This is not really unexpected, as the bootstrap method will remove ‘discrepant’ observations until a solution passing through the remaining IAD is finally found. The parallax of that solution will clearly be of the order of the noise on the abscissa residuals, though the spurious nature of that solution may be noticed by the large uncertainty on the parallax. For the sample of R stars considered in the present paper, such a bias on the absolute magnitude becomes clearly apparent for stars with $`K>8`$, although the parallax of somewhat brighter stars is already biased as well, as seen in Fig. 2 (see also Sect. 3.1). In an attempt to keep as many unbiased stars as possible, the following criterion has been adopted to reject biased parallaxes: $`K>8`$ (or $`V>10.5`$ if no $`K`$ magnitude is available) or the star has a simulated absolute magnitude that lies further than 4$`\sigma `$ away from the true absolute magnitude of $`2`$ on Fig. 2, $`\sigma `$ being the standard deviation of the simulated absolute magnitudes for stars with $`K<7`$ (i.e., which are not biased). Therefore, Tables 1 & 2 list only those parallaxes that may be considered as unbiased according to the above criteria.

The results are listed in Tables 1 & 2, which provides the HIP number from the Hipparcos catalogue in the first column. The star number in the General Catalog of Cool Galactic Carbon Stars (GCGCS; Stephenson 1989) is listed in column 2. Columns 3 to 5 provide the parallax $`\varpi _0`$ derived from the $`\chi ^2`$ minimization on the distance modulus, the corresponding lower and upper bounds ($`\varpi _L`$ and $`\varpi _U`$) computed from Eq. (9) of Paper I. The following columns list the apparent $`V`$ magnitude (field H5 of the Hipparcos catalogue), the $`K`$ magnitude, the $`JH`$ and $`HK`$ color indices, their reference, and finally the spectral type and its reference.

## 3 The absolute magnitudes and colors of R stars

The absolute magnitudes $`M_\mathrm{V}`$ and $`M_\mathrm{K}`$ are calculated as follows:

$$d=\mathrm{\hspace{0.33em}1}/\varpi (^{\prime \prime })$$
(1)
$$M_\mathrm{X}=m_\mathrm{X}+55\mathrm{log}dA_\mathrm{X}\text{(where}\text{X = V}\mathrm{or}\text{K})$$
(2)
$$A_\mathrm{K}=\mathrm{\hspace{0.33em}0.114}A_\mathrm{V},$$
(3)
where $`d`$ is the distance in pc, and $`A_\mathrm{V}`$ and $`A_\mathrm{K}`$ are the interstellar absorptions in the $`V`$ and $`K`$ bands, respectively. We have adopted the extinction model of Hakkila et al. (1997) with the $`A_\mathrm{K}/A_\mathrm{V}`$ ratio from Cardelli et al. (1989). We do not attempt to include circumstellar extinction, since this is shown by infrared color to be small or non-existent for the R stars. The extinction corrections to the $`K`$ magnitudes are small, less than 0.2 mag.

Fig. 3 shows the color – absolute magnitude diagram, $`M_{\mathrm{K}_0}`$ versus $`(VK)_0`$, for the stars with available $`K`$ magnitudes. The error bars on $`M_\mathrm{K}`$ are calculated from the upper and lower bounds on the parallax listed in Tables 1 & 2. As noted in Paper I, the parallax uncertainties are computed so as to produce symmetric error bars on the magnitude. The resulting uncertainties in the absolute magnitudes are often larger than 1 mag (see Fig. 3), and dwarf the uncertainties on the measured apparent magnitudes and on the interstellar extinction.

Fig. 3 shows that the difference between late- and early-type R stars, assessed from their photometric, spectral, variability and mass-loss properties as discussed in Sect. 2.4, is also apparent in their luminosities: late-type R stars with $`(VK)_0>4`$ tend to be more luminous than early-type R stars. Late-type R stars thus clearly mark the bottom of the asymptotic giant branch.

### 3.1 Average absolute magnitude of early-type R stars

To derive an average absolute magnitude from a set of measured parallaxes is an operation plagued by many biases (e.g., Arenou & Luri 1999), and several simulations have been performed to identify their importance for the present sample.

More precisely, the simulations described below evaluate whether the reduction scheme used in the present work is able to correctly retrieve the absolute magnitude of the sample stars. In a first step, it is assumed that all the 59 stars from the present sample with a $`K`$ magnitude available have the same absolute magnitude, namely $`M_\mathrm{K}^0=2.0`$. In that framework, a true parallax may be assigned to each star of the sample, depending on its observed apparent $`K`$ magnitude according to the relation $`\mathrm{log}\varpi =0.2(M_\mathrm{K}^0K)1.`$ In the first simulation, the original abscissa residuals of the IAD file were replaced by residuals drawn from a normal distribution of zero mean and $`\sigma _v=1`$ mas (standard deviation of the residuals). To artificially increase the sample size, 32 different sets of residuals are drawn for the IAD file corresponding to each of the 59 R stars, totaling to 1888 simulated stars. In this test, the IAD file only serves to define the time sampling of the observations and the scanning angle on the sky for each observation. The reduction scheme outlined in Sect. 2.5 is then applied to the total sets of modified IAD files. Results are shown in the upper left panel of Fig. 4. In a second simulation, the reduction scheme is applied to the actual abscissa residuals which do not necessarily follow a normal distribution with a standard deviation of $`\sigma _v=1`$ mas. Any differences between the results of the first and second simulation will thus highlight the impact of the measurement errors.

The results are shown in the upper panel of Fig. 4, and the first three moments of the retrieved distributions are listed in Table 3, where the coefficient of skewness is defined as $`\mu _3/\sigma ^3`$ (and $`\mu _3`$ is the centered moment of order 3). The method is able to retrieve the true absolute magnitude when the uncertainties on the residuals have a standard deviation of 1 mas. If the actual residuals are used instead, the computed distribution is retrieved as well, except for a tail extending towards fainter $`M_\mathrm{K}`$, as apparent on Fig. 2. That tail is not visible in Fig. 4, though, since stars with $`K>8`$ have very large and noisy abscissa residuals and were not displayed.

Other simulations were carried out as above, except that Gaussian distributions with $`\sigma _0=0.5`$ and 1 mag were adopted for the true absolute magnitude distribution. Basically the same features as for the case $`\sigma _0=0`$ emerge, namely the fact that the retrieved distribution using the actual IAD residuals is skewed towards fainter absolute magnitudes, with a bias of 0.55 mag for the $`\sigma _0=1`$ mag case, which however reduces to 0.16 mag if only stars with $`K8`$ are kept (Table 3).

The distribution derived from the true distribution ($`\overline{M_K^0},\sigma _0)=(2.0,1.0)`$ provides a fair match to the observed distribution (bottom right panel of Fig. 4), characterized by a weighted-average absolute magnitude

$$\overline{M_\mathrm{K}}=\frac{\mathrm{\Sigma }_{i=1}^NM_{\mathrm{K},i}w_i}{\mathrm{\Sigma }_{i=1}^Nw_i}=1.54,$$
(4)
where $`M_{\mathrm{K},i}`$ is the individual absolute magnitude of R stars with $`(VK)_0<4`$ and $`K8`$, $`w_i=1/ϵ(M_{\mathrm{K},i})^2`$ and $`ϵ(M_{\mathrm{K},i})=5(\mathrm{log}\varpi _U\mathrm{log}\varpi _0)=5(\mathrm{log}\varpi _0\mathrm{log}\varpi _L)`$, and $`\varpi _0,\varpi _L,\varpi _U`$ as derived by our reduction scheme are given in Tables 1 & 2.

Thus it may be concluded that the early-type R stars have a true absolute-magnitude distribution close to ($`\overline{M_K^0},\sigma _0)=(2.0,1.0)`$. Since the present sample of R stars is basically magnitude-limited, it is subject to the Malmquist bias favoring high-luminosity stars. The Malmquist (1936) bias is probably responsible for the high-luminosity tail and the deficit of low-luminosity stars in the observed sample (bottom-right panel of Fig. 4), as compared to the simulated Gaussian population.

### 3.2 Early R stars as members of the red clump

Fig. 5 reproduces the color-magnitude diagram from Fig. 3 for R stars with $`(VK)_0<4`$ and $`K8`$, and compares them to 238 nearby red clump stars as compiled by Alves (2000). The error bars have been excluded for clarity. Red clump stars have become of renewed interest recently because Hipparcos has made possible the calibration of their absolute magnitudes via observations of nearby stars (Paczyński & Stanek 1998; Girardi et al. 1998), making them a powerful tool for distance measurements within the Galaxy and the Local Group. Physically, these objects are the analogues of the red horizontal branch stars seen in metal-rich globular clusters: helium core burning post-red-giant branch stars. Fig. 5 very strongly suggests that the R stars are members of the red clump, since the inferred true absolute magnitude $`M_K^0=2.0`$ (with an estimated intrinsic dispersion of 1.0 mag) of R stars (Sect. 3.1) is similar to the average $`M_K=1.61\pm 0.03`$ derived from the sample of Alves (2000). The $`VK`$ colors of R stars show a somewhat broader spread (but this may be due to contamination by a few N stars), and they are on average about 0.5 mag redder than the local clump stars, which have $`<VK>=2.35`$; this is likely to be due to the presence of weak to moderate $`\mathrm{C}_2`$ and CN band absorption in the blue region of the spectrum.

## 4 The space density of early R stars

In this section, the space density of R stars will be estimated and compared to that of red clump stars. To evaluate the completeness of the sample of early R stars, Fig. 6 displays the cumulative frequency distribution of early R stars as a function of distance. To circumvent the bias on the derived absolute magnitude distribution (see Fig. 4), the distances have been estimated by assigning the absolute magnitude $`M_K^0=2.0`$ to all early R stars. Under the assumption of a uniform density $`n_0`$ in the plane and an exponential distribution perpendicular to the plane with scale height $`z_0`$, the cumulative frequency distribution varies with distance $`d`$ as

$$\mathrm{log}N(d)=4\pi n_0d^3\times $$

$$\left[\left(\frac{1}{2}\frac{z_0}{d}\left(\frac{z_0}{d}\right)^3\right)+\left(\left(\frac{z_0}{d}\right)^2+\left(\frac{z_0}{d}\right)^3\right)\mathrm{exp}\left(\frac{d}{z_0}\right)\right]$$
(5)
The scale height and the space density of R stars can then be estimated from the values that must be assigned to the parameters $`z_0`$ and $`n_0`$ in order to fit the observed distribution. It is found to be about $`n_0\mathrm{4.5\hspace{0.33em}10}^8\mathrm{pc}^3`$ for $`z_0=300`$ pc. Fig. 6 reveals that, for this parameter set, early R stars follow the predicted uniform/exponential distribution up to about 600 pc (involving about 60% of the total sample). It needs not be emphasized that these values are very uncertain though, as $`z_0`$ is only poorly constrained by the fit and both $`z_0`$ and $`n_0`$ depend on the quite uncertain $`M_K^0`$ assignment. Adopting $`M_K^0=1`$ instead yields $`n_0\mathrm{1.5\hspace{0.33em}10}^7`$ pc-3 and $`z_0180`$ pc.

The sample of red clump stars by Alves (2000) contains 284 stars with 5% parallaxes from the Hipparcos catalogue and is roughly complete to 12 mas or about 83 pc. The volume density of the red clump stars is thus about $`\mathrm{1.14\hspace{0.33em}10}^4\mathrm{pc}^3`$ and the R stars form about 0.04% (or 0.13% if $`M_K^0=1`$) of the total. There are additional uncertainties because, for a given star, there is no way to tell whether it is a clump star or is on the red giant branch. Nevertheless, the qualitative conclusion is clear: a very small fraction of clump stars in the solar neighborhood is carbon-rich.

## 5 Conclusions

In this paper, we have re-analyzed the Hipparcos Intermediate Astrometric Data for a sample of 83 carbon stars of class R, the class of warm evolved carbon red giants. A special reprocessing scheme has been used, fitting the distance modulus instead of the parallax (thus ensuring its positiveness) and rejecting outliers within a bootstrap scheme ensuring consistency between the solutions obtained from the NDAC and FAST data. This reduction scheme is not free from biases: Monte-Carlo simulations have shown that it tends to produce parallaxes that are too large when $`ϵ(\varpi )/\varpi 1`$. Despite these biases, the simulations allow the identification of the true properties of the population.

We have shown that the early- and late-type R stars have different properties. Late-type R stars generally have subtypes later than R4, although a better definition uses their color indices $`(VK)_0>4`$ or $`(HK)>0.3`$. Most of these stars are long-period variables of the SR or Mira types, and they often exhibit excess emission at 12 $`\mu `$m due to dust, indicative of mass loss. In the HR diagram, these stars mark the bottom of the AGB, and are thus related, or even identical, to the N stars.

The early-type R stars form a rather homogeneous group, with most of its members populating the red clump. They are well represented by a population having a Gaussian distribution of absolute magnitudes such that $`(M_K^0,\sigma _0)=(2.,1.)`$. They are not variable and do not appear to suffer from substantial mass loss, as judged from the absence of 12 $`\mu `$m excess. They represent fewer than 0.1% of the clump stars. Their nature as carbon stars is not due to low metallicity: R stars have metal abundances which are close to solar (Dominy 1984), except for the carbon excess.

The location of the R stars in the red clump provides strong support for the formation scenario suggested by Dominy (1984): the helium core flash mixes carbon to the surface of the star. This mixing episode may perhaps be rotationally-induced as the star is spun up by the accretion of a former companion. This scenario has the advantage of accounting as well for the lack of binary systems among R stars (McClure 1997b), but it requires a braking mechanism (e.g. magnetic braking as advocated by Habets & Zwaan (1989)?) since R stars do not currently appear to be rapid rotators. The fraction of stars which become R stars is much smaller than the fraction (10% – 50%, see Wallerstein & Knapp 1998) of stars which become carbon stars on the AGB, and it is unlikely to have any significant influence on the number of carbon AGB stars. It suggests that a small fraction of the RR Lyrae stars and blue horizontal branch stars in the Galactic halo are also carbon rich – these stars however are too hot to have $`\mathrm{C}_2`$ in the atmosphere.

###### Acknowledgements.

We thank Bohdan Paczyński and Jim Gunn for useful discussions and advice, David Alves for a machine-readable copy of his red clump star data, and the National Aeronautics and Space Administration NASA who supported this work via grants NAG5-6734 and NAG5-8083. We also thank Frédéric Arenou, the referee, for his useful comments and suggestions. 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. This research has made use of the Simbad data base, operating at CDS, Strasbourg, France.


text:
# What Schrödinger’s Cat is Telling

## Appendix. What is the “physical reality” and how QM works?

Nature stands itself independent of mankinds’ consciousness. An object is something absolute, infinite and containing no information (“thing in itself”). But for cognizing it, we divide an individual from the whole, i.e., separate a system (quantum state) from its environment approximately by certain boundary condition. Only after some measurement performed by us on it does an observed phenomenon (“thing for us”) with some information occur. Being the probability amplitude of relevant fictitious measurement, the wave function in corresponding representation can predict in advance what will happen statistically if the measurement is really made. It is just the power of QM. See Fig. 1.

## Acknowledgement

The author wishes to thank Dr. Z.-Y. Shen for bringing the Refs.  to his attention as quickly as possible and relevant discussions.