text:
# Efficient linear feedback shift registers with maximal period

## 1. Linear feedback shift registers

Linear feedback shift registers (*LFSR*’s) are fundamental primitives in the theory and practice of pseudorandom number generation and coding theory (see, e.g., , , , , , , and references therein).

Figure 1 describes a typical LFSR over the two-element field $`𝔽_2=\{0,1\}`$, where each step consists of adding some of the state bits (we follow the convention that the elements of $`𝔽_2`$ are called *bits*), and the result is inserted to the register in a FIFO manner.

Such a construction is slow in the sense that it produces only one new bit per step. Moreover, it is difficult to implement in software, since many bit manipulations are required. In certain cases (but not always ), it is possible to use LFSR’s with only two feedback taps. This makes a slightly faster LFSR. (See also Section 7.)

In the 1994 conference on fast software encryption, a challenge was set forth to design LFSR’s which exploit the parallelism offered by the word oriented operations of modern processors \[8, §2.2\]. In this paper we suggest a solution and study its properties.

## 2. Linear transformation shift registers

Fix an arbitrary finite field $`F`$. A sequence $`\sigma =s_n_{n=0}^{\mathrm{}}`$ of elements from $`F`$ is *linear recurring with characteristic polynomial*

$$f(\lambda )=a_0+a_1\lambda +\mathrm{}+a_d\lambda ^dF[x]$$

if $`a_d=1`$, and

$$a_0s_n+a_1s_{n+1}+\mathrm{}+a_ds_{n+d}=0$$

for all $`n=0,1,2,\mathrm{}`$. The *minimal polynomial* of a linear recurring sequence $`\sigma `$ is the characteristic polynomial of $`\sigma `$ of least degree. Let $`\sigma `$ be a nonzero linear recurring sequence with an irreducible characteristic polynomial $`f(\lambda )`$. It is well known (cf. ) that the period of $`\sigma `$ is equal to the order of $`\lambda `$ in the multiplicative group of the field $`K=F[\lambda ]/f(\lambda )`$. If $`\lambda `$ generates the whole group, we say that $`f(\lambda )`$ is *primitive*. (In this case $`\sigma `$ has the maximal possible period $`|K|1=|F|^d1`$ where $`d=\mathrm{deg}f(\lambda )`$.) Likewise, for any natural number $`d`$, if $`T`$ is a linear transformation of $`F^d`$ and $`vF^d`$ is nonzero, then the sequence $`T^n(v)_{n=0}^{\mathrm{}}`$ of vectors in $`F^d`$ has period $`|F|^d1`$ if and only if the characteristic polynomial of the linear transformation $`T`$ is primitive over $`F[\lambda ]`$. If this is the case we say that $`T`$ is *primitive*.

We now introduce the family of *linear transformation shift registers* (TSR’s). For convenience of presentation, we pack $`mn`$-dimensional vectors in an array $`(v_0,\mathrm{},v_{n1})`$ of $`n`$ vectors in $`F^m`$ ($`n`$ and $`m`$ will be fixed throughout the paper). In the intended application, $`F=𝔽_2`$ and $`m`$ is the number of bits in the processor’s word. Typical values of $`m`$ are $`8`$, $`16`$, $`24`$, $`32`$, and $`64`$. This way, the array $`(v_0,\mathrm{},v_{n1})`$ is stored in $`n`$ processor words. Following this interpretation, elements of $`F^m`$ will be called *words*.

###### Definition 2.1.

Let $`T`$ be a linear transformation of $`F^m`$, and let $`S=a_0,\mathrm{},a_{n1}F^n`$. A *TSR step $`T,S`$* of the array $`R=(v_0,\mathrm{},v_{n1})M_{m\times n}(F)`$ is the linear transformation

$$T,S(R):=(v_1,v_2,\mathrm{},v_{n1},T(a_0v_0+a_1v_1+\mathrm{}+a_{n1}v_{n1})).$$

The system $`T,S,R`$ is called a *TSR*.

Figure 2 illustrates a typical example of a TSR. An obvious advantage over the standard LFSR is that here a whole new word (rather than a single bit) is produced per step.

Linear transformations on processor words can be performed very efficiently, either using lookup tables, or by using specific linear transformations which are efficient when working on processor words, e.g. Galois-type shift registers. The latter example has the advantage that no additional memory is required (see, e.g., \[9, pp. 378–379\]). Note further that choosing each of the $`a_i`$’s to be either $`0`$ or $`1`$ eliminates the complexity of the multiplications $`a_iv_i`$. One cannot, however, eliminate the complexity of the transformation $`T`$ as well by using the identity transformation $`T=I`$: In this case the period cannot be greater than $`|F|^n1`$, whereas in principle, memory of $`n`$ words can yield period $`|F|^{mn}1`$.

Simulations show that there exist choices for $`T`$ and $`S`$ such that the resulted TSR step is primitive, and thus yields a sequence of vectors with period $`2^{mn}1`$. In the following sections we provide necessary conditions on $`T`$ and $`S`$ in order that the resulted TSR step is primitive. Choosing $`T`$ and $`S`$ to satisfy these conditions increases the probability that the resulted TSR is primitive with respect to random choice of these parameters. Thus, we will get an efficient algorithm for generation of primitive TSR’s.

## 3. The characteristic polynomial of a TSR

Identify the linear transformation $`T`$ operating on words with the matrix $`TM_m(F)`$ such that $`Tv=T(v)`$, $`vF^m`$.

Let $`I`$ denote the $`m\times m`$ unit matrix. A TSR step $`T,S=a_0,\mathrm{},a_{n1}`$ of the array $`R=(v_0,\mathrm{},v_{n1})(F^m)^n`$ is equivalent to multiplication of $`(v_0,\mathrm{},v_{n1})^t`$ from the left by the block matrix $`[T,S]M_{nm}(F)`$, where

$$[T,S]=\left(\begin{array}{ccccc}0& I& 0& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& & \mathrm{}& \mathrm{}& 0\\ 0& \mathrm{}& \mathrm{}& 0& I\\ a_0T& a_1T& \mathrm{}& a_{n2}T& a_{n1}T\end{array}\right).$$

Let $`f_S(\lambda )=a_0+a_1\lambda +\mathrm{}+a_{n1}\lambda ^{n1}`$ (so that the characteristic polynomial of $`[T,S]`$ in the case $`m=1`$ and $`T=(1)`$ is $`\lambda ^nf_S(\lambda )`$), and let $`f_T(\lambda )=|\lambda IT|`$ denote the characteristic polynomial of $`T`$ (note that the degree of $`f_T(\lambda )`$ is $`m`$.)

###### Proposition 3.1.

Let $`T`$ be a linear transformation of $`F^m`$, and $`S=a_0,\mathrm{},a_{n1}F^n`$. Then the characteristic polynomial of the TSR step $`T,S`$ is

$$f_{T,S}(\lambda )=f_S(\lambda )^mf_T\left(\frac{\lambda ^n}{f_S(\lambda )}\right).$$

###### Proof.

We multiply each row block by $`\lambda `$, and add the result to the next one. Then we use the $`I`$ blocks to cancel the terms in the first column block.

(6) $`|\lambda IT,S|`$ $`=`$ $`\left|\begin{array}{ccccc}\lambda I& I& 0& \mathrm{}& 0\\ 0& \mathrm{}& \mathrm{}& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& 0\\ 0& \mathrm{}& 0& \lambda I& I\\ a_0T& a_1T& \mathrm{}& a_{n2}T& \lambda Ia_{n1}T\end{array}\right|=`$
(12) $`=`$ $`\left|\begin{array}{ccccc}\lambda I& I& 0& \mathrm{}& 0\\ \lambda ^2I& 0& \mathrm{}& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& 0\\ \lambda ^{n1}I& 0& \mathrm{}& 0& I\\ a_0T& a_1T& \mathrm{}& a_{n2}T& \lambda Ia_{n1}T\end{array}\right|=`$
(18) $`=`$ $`\left|\begin{array}{ccccc}0& I& 0& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}\\ \mathrm{}& & \mathrm{}& \mathrm{}& 0\\ 0& \mathrm{}& \mathrm{}& 0& I\\ \lambda ^nIf_S(\lambda )T& a_1T& \mathrm{}& a_{n2}T& \lambda Ia_{n1}T\end{array}\right|=`$
$`=`$ $`(1)^{m(n1)}\left|\begin{array}{ccccc}\lambda ^nIf_S(\lambda )T& a_1T& \mathrm{}& a_{n2}T& \lambda Ia_{n1}T\\ 0& I& 0& \mathrm{}& 0\\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& 0\\ \mathrm{}& & \mathrm{}& \mathrm{}& 0\\ 0& \mathrm{}& \mathrm{}& 0& I\end{array}\right|=`$
$`=`$ $`(1)^{m(n1)}|\lambda ^nIf_S(\lambda )T||I|^{n1}=`$
$`=`$ $`f_S(\lambda )^m\left|{\displaystyle \frac{\lambda ^n}{f_S(\lambda )}}IT\right|=f_S(\lambda )^mf_T\left({\displaystyle \frac{\lambda ^n}{f_S(\lambda )}}\right).`$
A naive algorithm for generation of a TSR with maximal period would be to choose the linear transformation $`T`$ and the set $`S`$ at random, calculate the characteristic polynomial $`f_{T,S}(\lambda )`$ using Proposition 3.1, and then check whether it is primitive, repeating this process until a primitive polynomial is found. In most of the cases, the polynomial will not be primitive for the reason that it is not even irreducible. The following corollary shows that much unnecessary work can be avoided.

###### Corollary 3.2.

If $`f_T(\lambda )`$ is reducible over $`F`$, then so is $`f_{T,S}(\lambda )`$.

###### Proof.

Suppose $`f_T(\lambda )=q_1(\lambda )q_2(\lambda )`$ is a nontrivial factorization of $`f_T(\lambda )`$ over $`F`$, $`m_i=\mathrm{deg}q_i(\lambda )`$. Then $`f_S(\lambda )^{m_i}q_i\left(\frac{\lambda ^n}{f_S(\lambda )}\right)`$ are polynomials, and $`f_{T,S}(\lambda )=\left(f_S(\lambda )^{m_1}q_1\left(\frac{\lambda ^n}{f_S(\lambda )}\right)\right)\left(f_S(\lambda )^{m_2}q_1\left(\frac{\lambda ^n}{f_S(\lambda )}\right)\right)`$ is a nontrivial factorization. ∎

###### Remark 3.3.

In general, the probability that a monic polynomial of degree $`m`$ chosen at random is irreducible is close to $`1/m`$. Thus, by Corollary 3.2, the probability that $`f_{T,S}(\lambda )`$ is irreducible provided that $`f_T(\lambda )`$ is irreducible should be about $`m`$ times larger than the probability when $`f_T(\lambda )`$ is arbitrary.

## 4. Irreducibility through extension fields

The algorithm stated in the previous section considered polynomials of a special form as candidates to be primitive. In this section we study polynomials of this form, with the aim of improving the algorithm.

Let $`F`$ be a fixed finite field. Let $`q(\lambda )=q_0+q_1\lambda +\mathrm{}+q_m\lambda ^mF[\lambda ]`$. We write $`𝔭_{q(\lambda )}(x,y)`$ for the homogeneous polynomial

$$x^mq(y/x)=q_0x^m+q_1x^{m1}y+\mathrm{}+q_my^m.$$

We wish to find necessary conditions for polynomials of the form $`𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$ to be irreducible. Clearly, if $`g(\lambda ),f(\lambda )F[\lambda ]`$ are not relatively prime, then the polynomial $`𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$ is reducible. Also, by Corollary 3.2, if $`q(\lambda )`$ is reducible, then so is $`𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$. We are thus interested in the following type of polynomials.

###### Definition 4.1.

We say that a polynomial

$$𝔭_{q(\lambda )}(g(\lambda ),f(\lambda )):=g(\lambda )^{\mathrm{deg}q(\lambda )}q\left(\frac{f(\lambda )}{g(\lambda )}\right)$$

is a *candidate* if:

1. $`g(\lambda ),q(\lambda ),f(\lambda )F[\lambda ]`$,
2. $`f(\lambda )`$ and $`g(\lambda )`$ are relatively prime, and
3. $`q(\lambda )`$ is monic and irreducible.

###### Theorem 4.2.

Assume that $`Q(\lambda )=𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$ is a candidate, and let $`\alpha `$ be a root of $`q(\lambda )`$ in the splitting field $`L`$ of $`q(\lambda )`$. Then the number of distinct irreducible factors of $`Q(\lambda )`$ over $`F`$ is equal to the number of distinct irreducible factors of $`f(\lambda )\alpha g(\lambda )`$ over $`L`$.

###### Proof.

Denote by $`\alpha _1,\mathrm{},\alpha _mL`$ the (distinct) roots of $`q(\lambda )`$ in $`L`$, so that $`q(\lambda )`$ has the form $`_{i=1}^m(\lambda \alpha _i)`$. We have that over $`L`$,

(25)
$$Q(\lambda )=g(\lambda )^mq\left(\frac{f(\lambda )}{g(\lambda )}\right)=\underset{i=1}{\overset{m}{}}\left(f(\lambda )\alpha _ig(\lambda )\right).$$

We can extend the standard norm map $`LF`$ to a norm $`N_{L/F}:L[\lambda ]F[\lambda ]`$ by $`N_{L/F}(h(\lambda ))=_{\sigma Gal(L/F)}\sigma (h(\lambda ))`$, where $`\sigma (\lambda )=\lambda `$ for all $`\sigma Gal(L/F)`$. Fix any $`\alpha \{\alpha _1,\mathrm{},\alpha _m\}`$. Using this notation, Equation (25) is

$$Q(\lambda )=N_{L/F}(f(\lambda )\alpha g(\lambda )).$$

We will use the following lemma.

###### Lemma 4.3.

Let the field $`L`$ be an extension of $`F`$. Assume that $`r(\lambda )L[\lambda ]`$ be irreducible. Then $`R(\lambda )=N_{L/F}(r(\lambda ))`$ is equal to an irreducible polynomial over $`F`$ raised to the power $`[L:L_0]`$, where $`L_0L`$ is the subfield generated by the coefficients of $`r(\lambda )`$ over $`F`$.

###### Proof.

Since $`N_{L/F}=N_{L_0/F}N_{L/L_0}`$ and $`N_{L/L_0}(r(\lambda ))=r(\lambda )^{[L:L_0]}`$, it is enough to prove the claim in the case $`L_0=L`$.

Let $`R(\lambda )=R_1(\lambda )\mathrm{}R_t(\lambda )`$ be an irreducible factorization of $`R(\lambda )`$ over $`F`$. Obviously $`r(\lambda )`$ divides $`R(\lambda )`$ in $`L[\lambda ]`$, and since $`r(\lambda )`$ is irreducible we have that $`r(\lambda )`$ divides one of the factors, say $`r(\lambda )`$ divides $`R_1(\lambda )`$.

Let $`L_1`$ be the splitting field of $`R_1(\lambda )`$ over $`F`$. Note that $`LL_1`$, since the coefficients of $`r(\lambda )`$ (which divides $`R_1(\lambda )`$) generate $`L`$. Let $`L_2`$ be the splitting field of $`r(\lambda )`$ over $`L`$, then $`L_2L_1`$ and $`\mathrm{deg}R(\lambda )=[L:F]\mathrm{deg}r(\lambda )=[L_2:F]`$ divides $`[L_1:F]=\mathrm{deg}R_1(\lambda )`$. Thus $`R(\lambda )=R_1(\lambda )`$ and is irreducible. ∎

Let

$$f(\lambda )\alpha g(\lambda )=u_1(\lambda )^{s_1}\mathrm{}u_t(\lambda )^{s_t}$$

be a factorization into irreducible polynomials over $`L`$.

Taking the norm from $`L[\lambda ]`$ to $`F[\lambda ]`$, we get the factorization

$$Q(\lambda )=U_1(\lambda )^{s_1}\mathrm{}U_t(\lambda )^{s_t}$$

over $`F`$, where $`U_i(\lambda )=N_{L/F}(u_i(\lambda ))`$. By Lemma 4.3, The polynomials $`U_i(\lambda )`$ are irreducible (the coefficient of $`\lambda ^{\mathrm{deg}g(\lambda )}`$ in $`f(\lambda )\alpha g(\lambda )`$ generates $`L`$). It thus remains to show that the $`U_i(\lambda )`$ are relatively prime. We will show that $`u_i`$ is prime to $`\sigma (u_j)`$ for any $`\sigma Gal(L/F)`$ and $`ji`$. Indeed, if $`\sigma =1`$ then $`u_i`$ is prime to $`u_j`$ by the assumption. Otherwise, $`u_i`$ divides $`f\alpha g`$ and $`\sigma (u_j)`$ divides $`f\sigma (\alpha )g`$, but $`f\alpha g`$ and $`f\sigma (\alpha )g`$ are distinct and irreducible, thus relatively prime. ∎

###### Corollary 4.4.

Assume that $`Q(\lambda )=𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$ is a candidate, and let $`L`$ be the splitting field of $`q(\lambda )`$. Let $`\alpha `$ be a root of $`q(\lambda )`$ in $`L`$. Then $`Q(\lambda )`$ is irreducible over $`F`$ if, and only if, $`f(\lambda )\alpha g(\lambda )`$ is irreducible over $`L`$.

According to \[5, Chapter 4\], checking irreducibility of a degree $`d`$ polynomial amounts to performing gauss elimination of a matrix of size $`d\times d`$. In a finite field $`F`$ this requires roughly $`d^3`$ operations of multiplication and addition. Assume that $`Q(\lambda )=𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$ is a candidate, and set $`n=\mathrm{max}\{\mathrm{deg}f(\lambda ),\mathrm{deg}g(\lambda )\}`$. Checking the reducibility of $`Q(\lambda )`$ directly over $`F`$ requires roughly $`\mathrm{deg}Q(\lambda )^3=m^3n^3`$ operations. Checking its reducibility via Corollary 4.4 requires roughly $`n^3`$ operations, but here multiplication is more expensive: each multiplication in $`L`$ requires roughly $`m^2`$ multiplications in $`F`$. Thus, the algorithm implied by Corollary 4.4 is roughly $`m`$ times faster, where $`m=\mathrm{deg}q(\lambda )`$. See also Remark 6.3.

## 5. Primitivity

Assume that $`Q(\lambda )=𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$ is a candidate, $`L`$ is the splitting field of $`q(\lambda )`$, and $`\alpha `$ is a root of $`q(\lambda )`$ in $`L`$. By Corollary 4.4, $`Q(\lambda )`$ is irreducible over $`F`$ if, and only if, $`f(\lambda )\alpha g(\lambda )`$ is irreducible over $`L`$. The analogue result for primitivity follows: $`Q(\lambda )`$ is primitive if, and only if, it is irreducible and its roots generate $`K^{}`$, where $`K`$ is the splitting field of $`Q(\lambda )`$. Now, observe that $`K`$ is also the splitting field of $`f(\lambda )\alpha g(\lambda )`$, and that $`Q(\lambda )`$ and $`f(\lambda )\alpha g(\lambda )`$ share the same roots in $`K`$. This result, however, does not yield an improvement of the algorithm stated in the previous section.

In this section we show that if $`f(0)=0`$ and the base field is $`F=𝔽_2`$ (these assumptions hold in the intended environment for the TSR), then a candidate $`Q(\lambda )=𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$ is primitive only if $`q`$ is primitive. Thus, the TSR-generation algorithm should begin with *primitive* transformations $`T`$, yielding an additional speedup factor $`\varphi (|L^{}|)/|L^{}|`$, which is roughly $`2`$ when $`\mathrm{deg}q(\lambda )`$ is a power of $`2`$, cf. .

It will be convenient to use the following definition.

###### Definition 5.1.

Let $`L`$ be a finite field. The *index* of a nonzero element $`\alpha L`$ is the index $`|L^{}|/|\alpha |`$ of the cyclic group generated by $`\alpha `$ as a subgroup of $`L^{}`$.

An irreducible polynomial is primitive if, and only if, its roots have index $`1`$ in its splitting field. Note further that for $`d`$ dividing $`|L^{}|`$, $`\alpha L`$ has index $`d`$ if, and only if, $`\alpha =g^d`$ for some generator $`g`$ of the cyclic group $`L^{}`$.

###### Lemma 5.2.

Let $`h(\lambda )L[\lambda ]`$ be an irreducible monic polynomial of degree $`n`$ over $`L`$, with splitting field $`K`$ and a root $`\mu `$. Then $`\mu ^{|K^{}|/|L^{}|}=(1)^nh(0)`$.

###### Proof.

Let $`\mu _0,\mathrm{},\mu _{n1}`$ denote the (distinct) roots of $`h(\lambda )`$. Then $`h(\lambda )=(\lambda \mu _0)\mathrm{}(\lambda \mu _{n1})`$ is the factorization over $`K`$, thus $`h(0)=(1)^n\mu _0\mathrm{}\mu _{n1}`$. On the other hand, the Galois group of $`K/L`$ is generated by the Frobenius automorphism $`uu^{|L|}`$, thus the roots of $`h(\lambda )`$ are $`\mu ,\mu ^{|L|},\mathrm{},\mu ^{|L|^{n1}}`$, and $`\mu _0\mathrm{}\mu _{n1}=\mu ^{1+|L|+\mathrm{}+|L|^{n1}}=\mu ^{\frac{|L|^n1}{|L|1}}`$. ∎

###### Theorem 5.3.

Assume that $`F=𝔽_2`$ and $`Q(\lambda )=𝔭_{q(\lambda )}(g(\lambda ),f(\lambda ))`$ is an irreducible candidate with $`f(0)=0`$. If $`q(\lambda )`$ is not primitive then $`Q(\lambda )`$ is not primitive.

###### Proof.

Let $`K`$ be the splitting field of $`Q(\lambda )`$ over $`F`$, and $`LK`$ the splitting field of $`q(\lambda )`$. Let $`\mu K`$ be a root of $`Q(\lambda )`$, and $`\alpha L`$ a root of $`q(\lambda )`$.

Let $`d_\mu `$ denote the index of $`\mu `$ in $`K`$, and $`d_\alpha `$ the index of $`\alpha `$ in $`L`$. We will show that $`d_\alpha =(|L^{}|,d_\mu )`$. Thus, $`d_\mu =1`$ implies $`d_\alpha =1`$.

By Corollary 4.4, $`h(\lambda )=f(\lambda )\alpha g(\lambda )`$ is irreducible over $`L`$. Since every polynomial is monic over $`𝔽_2`$, we can apply Lemma 5.2 to get that $`h(0)=\mu ^{|K^{}|/|L^{}|}`$. But $`h(0)=f(0)(1)^n\alpha g(0)=\alpha g(0)`$. As $`f(\lambda )`$ and $`g(\lambda )`$ are relatively prime, $`g(0)0`$, thus $`g(0)=1`$, and $`h(0)=\alpha `$.

Let $`g`$ be a generator of $`K^{}`$ such that $`\mu =g^{d_\mu }`$.

Then $`\alpha =\mu ^{|K^{}|/|L^{}|}=g^{d_\mu |K^{}|/|L^{}|}`$, and its order in $`K^{}`$ is

$$|K^{}|/(|K^{}|,d_\mu |K^{}|/|L^{}|)=|L^{}|/(|L^{}|,d_\mu )\text{,}$$

as asserted. ∎

## 6. The final generation algorithm

In light of the results obtained in the previous sections, we end up with the following algorithm for TSR-generation over $`F=𝔽_2`$:

###### Algorithm 6.1 (Primitive TSR generation).

1. Choose at random a primitive transformation $`T`$ on $`𝔽_{2}^{}{}_{}{}^{m}`$.
2. Choose a random sequence $`S=a_0,\mathrm{},a_{n1}𝔽_{2}^{}{}_{}{}^{n}`$ such that $`a_00`$.
3. Choose a root $`\alpha `$ of $`f_T(\lambda )`$ in its splitting field $`L`$.
4. Check that $`\lambda ^n\alpha f_S(\lambda )`$ is irreducible over $`L`$ (otherwise return to step 1).
5. Check that $`Q(\lambda )=𝔭_{f_T(\lambda )}(f_S(\lambda ),\lambda ^n)`$ is primitive: Choose a root $`\mu `$ of $`Q(\lambda )`$ in its splitting field $`K`$, and check for all prime $`p`$ dividing $`|K^{}|`$ that $`\mu ^{|K^{}|/p}1`$ (in fact, as we show below, it is not needed to consider the cases where $`p`$ divides $`|L^{}|`$).
6. If $`Q(\lambda )`$ is not primitive, return to step 1.

###### Remark 6.2.

Assuming that generally, the probability that $`Q(\lambda )=𝔭_{f_T(\lambda )}(f_S(\lambda ),\lambda ^n)`$ is primitive is roughly the same for every primitive transformation $`T`$, it would be more efficient to repeat steps 2 to 5 of the algorithm several times before starting again from step 1. Thus, the complexity of step 1 will be negligible with respect to the total running time. Moreover, we argue below that step 5 usually occurs only once.

###### Remark 6.3.

In all of the mentioned algorithms, one can get a speedup factor of $`\stackrel{~}{m}`$, where $`\stackrel{~}{m}`$ is the size of the word in the processor where the search for the TSR is made (note that this need not be the same processor on which the TSR will be implemented, thus $`\stackrel{~}{m}`$ need not be equal to $`m`$). This is done by exploiting the processors word-oriented operations to define parallel versions of the basic operations used in the algorithms.

For a natural number $`n`$, we denote by $`C_n`$ the (multiplicative) cyclic group of order $`n`$. If $`g`$ is a generator of $`C_n`$, then $`g^x`$ is a generator as well if, and only if, $`(x,n)=1`$. This is why the number of generators of $`C_n`$ is exactly $`\varphi (n)`$, where $`\varphi `$ is Euler’s function, and the probability that a uniformly chosen element generates $`C_n`$ is $`\varphi (n)/n`$. An irreducible polynomial $`Q(\lambda )`$ is primitive if a root $`\mu `$ of $`Q(\lambda )`$ generates the multiplicative group of its splitting field $`K`$. There is a natural $`1`$ to $`[K:F]`$ correspondence between irreducible monic polynomials of degree $`[K:F]`$ and elements of $`K`$ which do not belong to a proper subfield of $`K`$. This correspondence implies that the probability that an irreducible $`Q(\lambda )`$ is primitive is close to $`\varphi (|K^{}|)/|K^{}|`$.

We now consider *irreducible candidates*. We wish to estimate the probability that a candidate passing the test in step 4 of the algorithm will also past the final test of step 5. A candidate $`Q(\lambda )=𝔭_{f_T(\lambda )}(f_S(\lambda ),\lambda ^n)`$ is *good* if $`T`$ is primitive and $`Q(\lambda )`$ is irreducible. We will find, heuristically, the probability that a good candidate is primitive. Let $`L`$ be the splitting field of $`f_T(\lambda )`$, and $`K`$ be the splitting field of $`Q(\lambda )`$. Factor $`|K^{}|=k_La`$, where $`k_L`$ is the product of all the prime factors of $`|K^{}|`$ which divide $`|L^{}|`$ (allowing powers of primes). Then the group $`K^{}`$ is isomorphic to $`C_{k_L}\times C_a`$, where a prime $`p`$ divides $`|L^{}|`$ if, and only if, it divides $`k_L`$. A root $`\mu `$ of $`Q(\lambda )`$ generates $`K^{}`$ if, and only if, its projections in $`C_{k_L}`$ and $`C_a`$ are both generators.

In the proof of Theorem 5.3 we showed that $`d_\alpha `$, the co-order of a root $`\alpha `$ of $`f_T(\lambda )`$ in $`L`$, is equal to $`(|L^{}|,d_\mu )`$, where $`d_\mu `$ is the co-order of $`\mu `$ in $`K`$. As $`T`$ is primitive (i.e. $`d_\alpha =1`$), we have that $`d_\mu `$ is prime to $`|L^{}|`$. Thus, $`d_\mu `$ is prime to $`k_L`$, that is, $`k_L`$ divides the order of $`\mu `$ in $`K^{}`$. Therefore, the projection of $`\mu `$ in $`C_{k_L}`$ is a generator of that group. We assume, *herusitically*, that the projection of $`\mu `$ on $`C_a`$ is (close to being) uniformly distributed. Thus, the probability of its being a generator of $`C_a`$ is close to $`\varphi (a)/a`$. In general,

$$\frac{\varphi (n)}{n}=\underset{p|n}{}\left(1\frac{1}{p}\right)\text{,}$$

and as a prime $`p`$ divides $`a`$ if, and only if, $`p`$ divides $`|K^{}|`$ but not $`|L^{}|`$, we have that

$$\frac{\varphi (a)}{a}=\frac{\varphi (|K^{}|)/|K^{}|}{\varphi (|L^{}|)/|L^{}|}.$$

We thus have a heuristic justification for the following claim.

###### Claim 6.4.

Assume that $`Q(\lambda )=𝔭_{f_T(\lambda )}(f_S(\lambda ),\lambda ^n)`$ is an irreducible candidate over $`𝔽_2`$, where $`f_T(\lambda )`$ is primitive. Then the probability that $`Q(\lambda )`$ is primitive is close to

$$\frac{\varphi (|K^{}|)/|K^{}|}{\varphi (|L^{}|)/|L^{}|}.$$

###### Example 6.5.

The probability at Claim 6.4 is usually close to 1. We give here a few examples:

1. When the word’s size is $`8`$ bits and the number of words is $`7`$, we have that $`\varphi (2^{56}1)/(2^{56}1)0.465`$, $`\varphi (2^81)/(2^81)0.502`$, and the division yields probability close to $`0.927`$.
2. When the word’s size is $`16`$ bits and the number of words is $`4`$, we get probability close to $`0.998`$.
3. For values $`24`$ and $`3`$, respectively, we get $`0.898`$.
4. For values $`32`$ and $`2`$ we get $`0.998`$.

## 7. Concluding remarks

We have presented the family of linear transformation shift registers which is efficient in software implementations. The theory we developed enabled us to get an efficient algorithm for generation of primitive transformations of this type (i.e., which have maximal period), thus answering a challenge raised in .

Variants of our construction can be found more appropriate for certain applications. Arguments similar to the ones we have presented here may be found useful in the study of these variants as well. A noteworthy variant of the LFSR type that we have studied is the *internal-xor*, or *Galois*, shift register (See, e.g., ). The number of new bits generated in one step of an internal-xor shift register is equal on average to half of the number of taps in that LFSR. Our construction suggests an obvious analogue internal-xor TSR. We get exactly the same results for this case, since the characteristic polynomial of an internal-xor TSR is equal to that of the corresponding external-xor TSR, which we have studied in this paper.


format: text

text:
# Generalized dynamical entropies in weakly chaotic systems

## 1 Introduction

Dynamical entropies measure rates at which information may be gained by observing a system of interest subjected to some law of temporal evolution. For deterministic dynamics one considers the time evolution of an initial ensemble of systems distributed uniformly inside a small compact box of diameter $`ϵ`$ (typically a ball or a cube) within the phase space characterizing the possible states of the system. One then asks how many boxes of size $`ϵ`$ are at least needed to cover the image of the initial box after a time $`t`$ has elapsed. If, in the limit $`ϵ0`$, the natural logarithm of this number increases as $`h_{top}t`$ asymptotically for $`t\mathrm{}`$, the quantity $`h_{top}`$ is called the topological entropy. In physical applications usually the Kolmogorov-Sinai entropy, designated as $`h_{KS}`$ is more relevant. This is defined in similar way, but the covering set is not required to contain the full image of the initial box; it only has to cover this up to a subset of measure $`\mu (t)`$ satisfying $`lim_t\mathrm{}\mu (t)=0`$. To interpret this, assume $`ϵ`$ is the minimal resolution with which one may distinguish phase space points by physical observation. Then by repeating the observations at regular time intervals the number of distinguishable initial boxes increases as $`\mathrm{exp}h_{KS}t`$ for a typical large but not exhaustive number of observed systems and it increases as $`\mathrm{exp}h_{top}t`$ for an exhaustive search in which also rare events are weighted properly for the full time range of observation.

For chaotic dynamical systems that are closed (no points escape from phase space) Pesin’s theorem equates the KS-entropy to the sum of the positive Lyapunov exponents. Intuitively this result is not hard to understand. Each positive Lyapunov exponent $`\lambda _i`$ corresponds to an independent direction in phase space with a smooth expansion by a factor of roughly $`\mathrm{exp}\lambda _it`$ over a time $`t`$. So the overall expansion factor, and thereby the number of boxes needed to cover the image of the initial box, increases as $`\mathrm{exp}_i\lambda _it`$. A priori one could expect though, that, at least in part, this may be offset by shrinkage in the contracting directions. However, this contraction typically takes place towards a fractal set with a striated structure on increasingly finer length scales. Once the typical length scale of separation between striation sheets falls below the box size $`ϵ`$ the number of boxes required to cover the set does not decrease any more. For comparison: consider the number of intervals of length $`ϵ`$ needed to cover successive approximations of the middle-third Cantor set. Once the length of the subintervals that are erased at the next iteration falls below $`ϵ`$ the number of covering intervals essentially does not change any more. The difference between topological and KS-entropy may be understood again by observing that on subsets of phase space of measure zero the Lyapunov exponents may differ from the ”bulk” Lyapunov exponents, which for an ergodic system are constant almost everywhere.

There exist dynamical systems that are not chaotic, in the ususal sense of having at least one positive Lyapunov exponent, but still show a fairly rapid decay to equilibrium, related to motion in phase space that appears very random. Simple examples of these are wind tree models, in which light particles without any mutual interaction move elastically among fixed polygonal scatterers. Lepri et al. numerically studied such a model consisting of diamond shaped scatterers with corner angles that are irrational fractions of $`\pi `$ on a triangular lattice with bounded free paths between collisions. They found this model equilibrates rapidly on the projection to the unit cell in space times the unit sphere for the velocities, and on large time and length scales it is described by normal diffusion. Dettmann et al. looked at Ehrenfests original wind tree model, in which the scatterers are randomly distributed parallel squares and the velocities of the light particles always point along the diagonals of the squares. In this case the velocities equilibrate among the four allowed directions and, in finite volume the density of a cloud of light particles becomes uniform. Again, on large time and length scales the dynamics becomes diffusive, provided the scatterers are not allowed to overlap each other. Another variation, studied by Li et al., consists of a channel lined by triangular scatterers, through which light particles move, giving rise again to diffusive motion on large scales. Other non-chaotic systems leading to macroscopically stochastic looking motion are mixtures of point particles of different masses in one dimension. These, for $`N`$ particles, may be viewed as a type of wind tree model on a $`2N`$-dimensional phase space bounded by flat hyperplanes. The intersections between these hyperplanes take the role of the corners; ”hitting the other side of a corner” translates to an interchange in the sequence of two subsequent collisions. Livi et al. and Grassberger et al. found that such systems show anomalous hydrodynamics, which is typical for one-dimensional systems. As a last example I would like to mention systems of many moving parallel oriented polygons (in 2d) or polyhedra (in 3d), which in collisions exchange the velocity components normal to the plane of collision. These systems too may be viewed as wind tree like models in a high dimensional phase space. No doubt they will show normal hydrodynamics (up to the usual nonlinearities in 2d, see e.g. ) although they are obviously non-chaotic. But to my knowledge no detailed investigations have been done for such systems so far.

For the systems described above, according to Pesin’s theorem the KS-entropy equals zero. Yet, it is clear that information may be gained by repeated observation, only the number of distinguishable initial boxes will not increase exponentially with time, but rather as a power law. Zaslavsky and Edelman refer to this situation as pseudochaos. I will use the term ”weak chaos” in the sequel, without giving a precise definition. For quantifying the power law increase of the information on the initial distribution Tsallis’ formalism seems suitable, as it is precisely meant to define an entropy for systems in which the countable number of states (here distinguishable initial boxes) does not increase exponentially with system size (here time) but rather as a power law. But there are some subtleties here to deal with. As we will see, the dynamical entropy as defined usually, will become dependent on the coarse graining lengths in the system. It has to be multiplied by powers of these to allow for taking the limit $`ϵ0`$. In addition, even very regular systems, such as an ideal gas in a periodic box, or a weakly anharmonic oscillator, will turn out to give rise to a positive dynamic Tsallis entropy, thereby excluding this property by itself as an indicator of weak chaos. Keeping track of the power law by which the information increases may help to recognize weak chaos. Even this requires a lot of care, because the powers of time resulting from integrable degrees of freedom may vary, depending on the type of motion they represent.

In the next sections we will consider dynamical Tsallis entropies and look at wind tree models in detail. In the discussion the feasibility of using a dynamical Tsallis entropy to characterize weak chaos will be discussed further.

## 2 Dynamical Tsallis entropies

Supose the phase space of a class of dynamical systems is divided into subsets $`C_i`$ such that the probability of finding a system in $`C_i`$ equals $`p_i`$. Then the Tsallis entropies are defined through.

$$S_q=\frac{1_ip_i^q}{q1.}$$
(1)
Here $`q`$ is a free parameter the choice of which should be dictated by the properties of the system considered. In the limit $`q1`$ the Tsallis entropy reduces to the usual entropy.

In the case of dynamical systems evolving in time from the interior of an initial set of diameter $`ϵ`$ one may choose for the $`C_i`$ a covering set of non-intersecting subsets of diameter $`ϵ`$ and define $`p_i(t)`$ as the fraction of initial phase points that end up inside $`C_i`$ after the time evolution over time $`t`$. The number of $`C_i`$ with non-vanishing $`p_i(t)`$ will increase as a power of $`t`$. Now let us suppose that on this subset $`p_i(t)`$ for large $`t`$ behaves as

$$p_i(t)=\frac{w_i}{Ct^\alpha },$$
(2)
with $`w_i`$ distributed according to some probability distribution with a mean value of unity. Then, in order for $`S_q(t)`$ to increase proportionally to $`t`$ one has to choose $`q=11/\alpha `$. In this case the entropy behaves as

$$S_{11/\alpha }(t)=\alpha C^{1/\alpha }<w_i^{(11/\alpha )}>,$$
(3)
with the brackets indicating an average over the distribution of $`w_i`$. In case this is an exponential distribution, $`p(w)=\mathrm{exp}w`$, one finds $`<w_i^{(11/\alpha )}>=\mathrm{\Gamma }(21/\alpha )`$.

A further remark is required here. As time increases one should choose increasingly smaller values of $`ϵ`$ in order to avoid $`C_i`$’s containing parts of the image of several initial boxes. For fixed $`ϵ`$ this will always occur after sufficiently long time. In principle one should take a limit $`ϵ0`$ followed by the limit $`t\mathrm{}`$. We will see however that the generalized dynamical entropies one would like to define are dependent on $`ϵ`$, so one cannot take these limits in a straightforward way. In fact, as we will see, it can only be done after redefining the dynamical entropies in an appropriate way.

## 3 Wind tree models

Here I will consider a wind tree model in two dimensions with square scatterers of side length $`a`$ that are randomly oriented and distributed randomly over a rectangle with periodic boundary conditions.

The scatterers are not allowed to overlap each other. I will assume that the density $`\rho `$ of scatterers is small, that is $`\rho a^21`$, so subsequent collisions of a light particle are to a very good approximation uncorrelated. For the subsets $`C_i`$ of the phase space let us choose small rectangular blocks of side lengths $`ϵ_r`$ in position space and $`ϵ_v`$ in velocity space. Over a time $`t`$ the dynamics stretches out these blocks into parallellopipida. For large $`t`$, in the direction parallel to the velocity these obtain an extension of length $`ϵ_vt`$. In the direction orthogonal to the velocity the front width covered by the parallellopipidum also grows as $`ϵ_vt`$. In addition the block is split into two subblocks, as illustrated in Fig. 2, as soon as its front hits a corner of one of the scatterers.

Next, when one of the two subblocks hits another corner it is split up likewise and so on. The total front width of all the propagating subblocks increases with time as $`ϵ_vt`$, independent of the number of splittings that have taken place. Therefore the average number of splittings during a long time $`t`$ is given by

$$N(t)=\frac{3}{2}\rho vϵ_vt^2.$$
(4)
Here $`v`$ is the average speed of a light particle. The average area swept out by the total front of all the subblocks is $`vϵ_vt^2/2`$ and this is multiplied by $`3\rho `$ to obtain the average number of visible corners in this area. The average number of resulting subblocks is almost equal to $`N(t)`$. To obtain the number of subsets $`C(i)`$ needed to cover all of the subblocks at $`t`$ one has to multiply $`N(t)`$ by $`ϵ_vt/ϵ_r`$, the number of subsets needed to cover the extension in the parallel direction. So in Eq. (2) $`\alpha =3`$ and $`C=3\rho vϵ_v^2/2ϵ_r`$. The positions of the corners with which the collisions take place follow a Poisson distribution along the front, hence the distribution of $`w_i`$ is an exponential one indeed. Using the results of the preceding section we find

$$S_{2/3}(t)=\alpha t\left(\frac{3\rho vϵ_v^2}{2ϵ_r}\right)^{2/3}\mathrm{\Gamma }\left(\frac{5}{3}\right).$$
(5)
## 4 Discussion

The first thing that draws the attention in Eq. (5) is the dependence of the entropy on the coarse graining lengths $`ϵ_v`$ and $`ϵ_r`$. This is a striking difference from the result found by Borges et al. for the logistic map at the onset of chaos. Here too the number of boxes increases algebraically with time, but this is due to a power law separation between infinitesimally close trajectories in phase space. In the wind tree models infinitesimally close trajectories typically just separate linearly with time, due to the infinitesimal velocity difference, but the interesting power law behavior in the time dependence of the number of covering sets needed is caused by the corner induced splitting of trajectories at arbitrarily small, but always finite distances from each other. The same is true for all the other examples mentioned in the introduction. As mentioned at the end Sec. 2 a sharp definition of dynamical entropies involves taking a limit $`ϵ0`$ followed by the limit $`t\mathrm{}`$. Obviously this makes no sense for the entropy obtained in Eq. (5). The limit $`ϵ0`$ is not well-defined. Apparently the only way to repair this is by defining still another dynamical entropy as

$$\stackrel{~}{S}_q=\left(\frac{ϵ_r}{ϵ_v^2}\right)^qS_q.$$
(6)
An alternative way of obtaining this is by requiring $`ϵ_r=ϵ_v^2`$. For wind tree like models in $`d`$ dimensions the prefactor $`ϵ_r/ϵ_v^2`$ should be raised to the power $`d1`$. This solution is not very elegant, e.g. there seems to be no obvious choice for making the $`ϵ`$’s dimensionless. But at least it seems to give a proper limiting behavior for $`ϵ0`$ for all wind tree like models.

A second point of concern is the entropy of an ideal gas in a periodic box. One easily sees that, with the same type of covering sets as for the wind tree model, the number of sets needed to cover the time evolved initial set increases in $`d`$ dimensions as $`(ϵ_vt/ϵ_r)^d`$. So for $`q=11/d`$ one now has a dynamical entropy that increases linearly with time. The same occurs for other integrable systems in which the periods of the angle variables depend on the values of the action variables. This is usually the case, with harmonic oscillators being the notable exception. For $`d`$-dimensional wind tree models the power of $`t`$ by which the number of needed covering sets increases with time is $`2d1`$. So it looks like one could use the condition $`q>11/d`$ as a criterion for weak chaos in a $`d`$-dimensional hamiltonian system. Here too care is needed. For example in a three-dimensional system that is a wind tree model in the $`xy`$ plane but in addition performs a harmonic oscillation in the $`z`$-direction, one has $`q=1/3`$, just as for a three-dimensional ideal gas. A distinction between the two cases may still be found in the dependence of $`S_{2/3}`$ on $`ϵ_r`$ and $`ϵ_v`$. The powers of $`ϵ_v`$ and $`ϵ_r`$ by which one has to multiply $`S_q`$ in order to obtain a $`\stackrel{~}{S}`$ with a proper limit for $`ϵ0`$ obviously are different for integrable systems of various types, for wind tree like models and for mixed systems.

It is not hard constructing generalizations of the wind tree model to higher dimensions. One just has to replace the scatterers by polyhedra of appropriate dimension. And indeed for each direction orthogonal to the velocity one picks up a factor $`t^2`$ in the growth factor of $`N(t)`$. Similar observations can be made for the moving polygons.

To conclude: Dynamical Tsallis entropies may be useful for characterizing weakly chaotic systems in which the information on initial conditions increases as a power law rather than an exponential. For wind tree like systems however, the precise value of this entropy depends on the choice of the coarse-graining lengths, which basically sets the smallest scales on which one may distinguish different systems in a single observation. To obtain a dynamical entropy with a proper limit when these coarse graining lengths are sent to zero, one first has to multiply the ”straightforward” dynamical entropy with appropriate powers of the coarse graining lengths. Further, the generalized entropies typically assume non-zero values also for integrable systems. In many cases the $`q`$-values needed to find an entropy that increases linearly with time will allow one to distinguish wind tree like systems from integrable ones, but this too is not always the case. If not, the dependence on the coarse graining lengths may be used for a further distinction.

HvB acknowledges support by the Mathematical physics program of FOM and NWO/GBE.


text:
# NGC 1883: a neglected intermediate-age open cluster located in the outskirts of the Galactic diskBased on observations carried out at Mt Ekar, Asiago, Italy. All the photometry is available at WEBDA database: http://obswww.unige.ch/webda/navigation.html

## 1 Introduction

NGC 1883 (C 0522+465, OCL 417) is a northern open cluster, located toward the anti-center direction ($`\alpha =05^\mathrm{h}25^\mathrm{m}.9`$, $`\delta =+46^{}29^{}`$, $`l=163^{}.08`$, $`b=+06^{}.16`$, J2000.). This cluster was never studied insofar. The only information we have come from Trumpler (1931) who suggests that this cluster is quite well detached from the field, shows a clear central concentration with a radius of about 3 arcmin, and is moderately rich (I2m Trumpler class). The same kind of information can be derived by consulting Collinder (1931) work.
This paper presents the first photometric study of the cluster, and it is part of a series dedicated at improving the photometry of northern open clusters at Asiago Observatory (see Carraro et al. 2002, and references therein)

The plan of the paper is as follows. Sect. 2 illustrates the observation and reduction strategies. An analysis of the geometrical structure and star counts in the field of NGC 1883 are presented in Sect. 3, whereas a discussion of the Color-Magnitude Diagram (CMD) is performed in Sect. 4. Sect. 5 deals with the determination of cluster reddening, distance and age. Finally, Sect. 6 summarizes our findings.

## 2 Observations and Data Reduction

CCD $`BVI`$ observations were carried out with the AFOSC camera at the 1.82 m Copernico telescope of Cima Ekar (Asiago, Italy), in the photometric night of November 8, 2002. AFOSC, with a pixel size of $`0^{\prime \prime }.473`$, samples a $`8^{}.14\times 8^{}.14`$ field in a $`1K\times 1K`$ nitrogen-cooled thinned CCD.

Details of the observations are listed in Table 2 where the observed field is reported together with the exposure times, the typical seeing values and the air-masses. Fig. 1 shows the finding chart NGC 1883 region taken from the DSS-2111Second generation Digitized Sky Survey, http://cadcwww.dao.nrc.ca/cadcbin/getdss archive. The data has been reduced with the IRAF222IRAF is distributed by NOAO, which are operated by AURA under cooperative agreement with the NSF. packages CCDRED, DAOPHOT, and PHOTCAL using the point spread function (PSF) method (Stetson 1987). The calibration equations obtained by observing Landolt (1992) PG 0231+051 and PG 2213-006 fields observed along the night, are:

| $`b=B+b_1+b_2(BV)+b_3X`$ | (1) |
| --- | --- |
| $`v=V+v_{1bv}+v_{2bv}(BV)+v_3X`$ | (2) |
| $`v=V+v_{1vi}+v_{2vi}(VI)+v_3X`$ | (3) |
| $`i=I+i_1+i_2(VI)+i_3X`$ | (4) |

where $`BVI`$ are standard magnitudes, $`bvi`$ are the instrumental ones, $`X`$ is the airmass and the derived coefficients are presented at the bottom of Table 2. As for $`V`$ magnitudes, when $`B`$ magnitude was available, we used expression (2) to compute them, elsewhere expression (3) was used. The standard stars in these fields provide a very good color coverage. For the extinction coefficients, we assumed the typical values for the Asiago Observatory (Desidera et al. 2002).

Finally, Fig. 2 presents the run of photometric errors as a function of magnitude. These errors take into account fitting errors from DAOPHOT and calibration errors, and have been computed following Patat & Carraro (2001). It can be noticed that stars brighter than $`V21`$ mag have photometric errors lower than 0.10 mag in magnitude and lower than 0.15 mag in colour. The final photometric data are available in electronic form at the WEBDA333http://obswww.unige.ch/webda/navigation.html site.

## 3 Star counts and cluster size

Lyngå (1987) and Dias et al. (2002) report a preliminary estimate of NGC 1883 radius, amounting to 2.5-3.0 arcmin. This is basically confirmed by the appearance of the cluster in the finding chart (Fig. 1), from which one can readily see that we were able to cover all the cluster region. We perform star counts by using our CCD data to obtain a new estimate of the cluster size. We derive the surface stellar density by performing star counts in concentric rings around stars $`\mathrm{\#}12`$ (the present numbering) selected as the approximate cluster center, and then dividing by their respective surfaces. The final density profile and the corresponding Poisson error bars are shown in Fig. 3, where we take into account all the measured stars brighter than $`V19.5`$ mag.
The surface density has a value of 10-12 stars/acrmin2 within 2.5 arcmin, and a value of 4-6 stars/acrmin2 outside this radius. From this sharp density variation we argue that the cluster population is dominant within 2.5 arcmin, whereas outside the general Galactic disk field dominates the star counts (see also Fig. 1).
The precise value of the cluster radius is however difficult to be obtained, and we consider 2.5 arcmin as a lower limit. Obviously, we expect that some cluster stars are located out of this radius, which we simply consider as the distance from the cluster center where the cluster dominates over the field.

## 4 The Colour-Magnitude Diagrams

The CMDs of NGC 1883 are shown in Fig. 4. To facilitate the interpretation we consider the distribution of the stars in the CMD as a function of the distance from the cluster center. In the left panel of Fig. 4 we plot all the detected stars. Here the cluster exhibits a well defined Main Sequence (MS) extending from $`V`$=20 to $`V`$=14.5. Interestingly, there are a few stars in the red part of the CMD, which resemble a Red Giant Branch (RGB). The MS is significantly wide, and some hints for a substantial population of unresolved binary stars is visible - particularly in the upper MS - in the form of a parallel redder sequence. The Turn Off Point (TO) is roughly located at $`V`$=16, $`(BV)`$= 0.60. The group of stars above the TO ( between $`V`$=12.5 and $`V`$=13.5) can be either blue stragglers belonging to the cluster or field stars. Finally the brightest star (see also Fig. 1), located southwest of the cluster center, and recorded as GSC 03358-01188 and TYC 3358 -1188 -1, is quite probably an interloper.
Much better information can be obtained by looking at the middle and right panels in Fig. 4. The middle panel contains only the stars located inside the estimated cluster radius (2.5 arcmin), whereas the right panel contains all the stars located outside the cluster radius. The following considerations can be done:

* The MS and the TO region in the middle panel are much better defined;
* almost all the probable RGB stars are inside the inner region, which implies by the way that the cluster underwent some dynamical relaxation;
* the stars above the TO are probably field stars, since they lie all out of the cluster radius (see right panel).

In particular the fine shape of the TO deserves some attention. In fact the shape of the TO is that one typical of intermediate-age open clusters, with a blue and red hook clearly visible notwithstanding the field stars contamination. This is a clear indication of an age in the range 1-1.5 Gyr, depending on the precise metal content of the cluster (Carraro & Chiosi 1994, Carraro et al. 1999).

## 5 Cluster fundamental parameters

In this section we try to provide some estimates of the cluster basic parameters. To achieve this result, we make use of the comparison between the stars distribution in the CMDs and a set of theoretical isochrones from the Padova group (Girardi et al. 2000). We already have an indication of the cluster age, but we do not know anything about the reddening, the distance and the metallicity. The results of the fitting are shown in Fig. 5 and 6.

In details, in Fig. 5 we present the CMDs for the stars withing 2.5 arcmin from the cluster center, with over-imposed an isochrone of 1.2 billion years for a solar (Z=0.019) metallicity. The fit is quite good in the $`V`$ vs $`(BV)`$ plane (left panel), but the shape of the MS is not very well reproduced in the $`V`$ vs $`(VI)`$ plane (right panel). Moreover the precise location of the RGB is not well matched. We achieved this results by shifting the isochrone with E$`(BV)=0.23`$, E$`(VI)=0.30`$, and $`(mM)=14.00`$ and by adopting $`R_V=3.1`$.
We tried to improve the fit by lowering the metal abundance, on the base of the fact that a cluster located toward the anti-center might have a lower than solar metal abundance (Friel 1995). The result is shown in Fig. 6. Here the isochrone has an age of 1.0 billion years for the Z=0.008 metal content. The global fit is quite good, and has been obtained by shifting the isochrone with E$`(BV)=0.35`$, E$`(VI)=0.50`$, and $`(mM)=14.50`$ ($`R_V=3.1`$).
In conclusion, a lower than solar metal abundance seems to be favored. If this is the case, NGC 1883 turns out to be located 4.8 kpc from the Sun toward the anti-center direction. This implies a distance from the Galactic center somewhat larger than 13 kpc, by assuming $`R_{}`$=8.5 kpc, and a height above the Galactic plane of about 500 pc. According to Friel (1995, Table 1), NGC 1883 turns out to be one of the few intermediate-age or old open clusters located in the outskirts of the Galactic disk. In fact we know only other 3 clusters (Tombaugh 2, Berkeley 20 and Berkeley 29) located more distant than NGC 1883. Therefore NGC 1883 might play an important role in defining the precise shape of the radial abundance gradient in the external regions of the Galactic disk, which is one of the fundamental constrains of models of chemical evolution (Chiappini et al. 2001). Moreover NGC 1883 lies significantly above the Galactic plane. The position, together with its compactness, are probably the main reasons for which the cluster survived until the present time.

## 6 Conclusions

We have presented the first CCD $`BVI`$ photometric study of the open cluster NGC 1883. The CMDs we derive allow us to infer estimates of the cluster basic parameters. In detail, we find that:

$``$ the age of NGC 1883 is around 1.0 Gyr;

$``$ the reddening $`E_{BV}`$ turns out to be 0.23$`\pm `$0.10 by adopting a metal abundace Z=0.019, or 0.35$`\pm `$0.10 mag if one assumes Z=0.008;

$``$ we place the cluster at about 4.8 kpc from the Sun toward the anti-center direction;

$``$ this way NGC 1883 turns out to be one of the most distant intermediate-age open cluster.

Future work should concentrate to obtain an estimate of the cluster metal abundance through spectra of the RGB stars. The knowledge of the cluster metallicity, which we could not constrain very well, is of paramount importance to better probe the trend of the metallicity in the outer parts of the Galactic disk (Friel & Janes 1993).

## Acknowledgements

We acknowledges the kind night assistance by Asiago Observatory technical staff and in particular dr. Stefano Ciroi who secured part of the observations discussed in this work. This study has been financed by the Italian Ministry of University, Scientific Research and Technology (MURST) and the Italian Space Agency (ASI), and made use of Simbad and WEBDA databases.


text:
# 1 The properties of the critical points

## Acknowledgements

This project was in part supported by NNSFC under Grant Nos. 10175070 and 10047004 as well as also by NKBRSF G19990754.