Kh Hessami Pilehrood

T Hessami Pilehrood

Simultaneous generation for zeta values by the Markov-WZ method

Keywords: Riemann zeta function, Apéry-like series, generating function, convergence acceleration, Markov-Wilf-Zeilberger method, Markov-WZ pair

By application of the Markov-WZ method, we prove a more general form of a bivariate generating function identity containing, as particular cases, Koecher's and Almkvist-Granville's Apéry-like formulae for odd zeta values. As a consequence, we get a new identity producing Apéry-like series for all ζ(2n + 4m + 3), n, m ≥ 0, convergent at the geometric rate with ratio 2 -10 .

Introduction

The Riemann zeta function is defined by the series

ζ(s) = ∞ n=1 1 n s , for Re(s) > 1. (1)
Apéry's irrationality proof of ζ(3) [START_REF] Van Der Poorten | A proof that Euler missed... Apéry's proof of the irrationality of ζ(3). An informal report[END_REF] operates with the faster convergent series

ζ(3) = 5 2 ∞ k=1 (-1) k-1 k 3 2k k (2)
first obtained by A. A. Markov in 1890 [START_REF] Markoff | Mémoire sur la transformation des séries peu convergentes en séries tres convergentes[END_REF]. The general formula giving analogous series for all ζ(2s+3), s ≥ 0, was proved by Koecher [7] (and independently in an expanded form by Leshchiner [START_REF] Leshchiner | Some new identities for ζ(k)[END_REF]). It reads

∞ s=0 ζ(2s + 3)x 2s = ∞ k=1 1 k(k 2 -x 2 ) = 1 2 ∞ k=1 (-1) k-1 k 3 2k k 5k 2 -x 2 k 2 -x 2 k-1 m=1 1 - x 2 m 2 . (3)
A similar identity generating fast convergent series for all ζ(4s + 3), s ≥ 0, which for s > 1 is different from Koecher's result [START_REF] Borwein | Empirically determined Apéry-like formulae for ζ(4n + 3)[END_REF], was experimentally discovered in [START_REF] Borwein | Empirically determined Apéry-like formulae for ζ(4n + 3)[END_REF] and proved by G. Almkvist and A. Granville in [START_REF] Almkvist | Borwein and Bradley's Apéry-like formulae for ζ(4n + 3)[END_REF]

∞ s=0 ζ(4s + 3)x 4s = ∞ k=1 k k 4 -x 4 = 5 2 ∞ k=1 (-1) k-1 2k k k k 4 -x 4 k-1 m=1 m 4 + 4x 4 m 4 -x 4 .
(4)

1365-8050 c 2008 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

There exists a bivariate unifying formula for identities (3) and (4),

∞ k=1 k k 4 -x 2 k 2 -y 4 = 1 2 ∞ k=1 (-1) k-1 k 2k k 5k 2 -x 2 k 4 -x 2 k 2 -y 4 k-1 m=1 (m 2 -x 2 ) 2 + 4y 4 m 4 -x 2 m 2 -y 4 , (5)
which was first conjectured by H. Cohen and then proved by D. Bradley [START_REF] Bradley | Hypergeometric functions related to series acceleration formulas[END_REF] and, independently, by T. Rivoal [START_REF]Simultaneous generation of Koecher and Almkvist-Grainville's Apéry-like formulae[END_REF]. This identity implies (3) if y = 0, and gives (4) if x = 0. The proof of [START_REF] Bradley | Hypergeometric functions related to series acceleration formulas[END_REF] given in [START_REF] Bradley | Hypergeometric functions related to series acceleration formulas[END_REF][START_REF]Simultaneous generation of Koecher and Almkvist-Grainville's Apéry-like formulae[END_REF] relies on Borwein and Bradley's method [START_REF] Borwein | Empirically determined Apéry-like formulae for ζ(4n + 3)[END_REF] and consists of reduction of ( 5) to a finite non-trivial combinatorial identity which can be proved on the basis of Almkvist and Granville's work [START_REF] Almkvist | Borwein and Bradley's Apéry-like formulae for ζ(4n + 3)[END_REF]. Recently, in [START_REF] Kh | Generating function identities for ζ(2n+2), ζ(2n+3) via the WZ-method[END_REF] it was shown that Koecher's formula (3), and similarly Leschiner's and the identities of Bailey, Borwein and Bradley [START_REF] Leshchiner | Some new identities for ζ(k)[END_REF][START_REF] Bailey | Experimental determination of Apéry-like identities for zeta(2n + 2)[END_REF] generating accelerated series for even zeta values ζ(2n + 2), can be proved by means of the WZ method.

Formulas (3)-( 5) generate accelerated series for odd zeta values and, in particular, series (2) for ζ(3) which converge at a geometric rate with ratio 1/4. Many other more rapidly convergent expressions for ζ(3) can be proved on the basis of the WZ method. The following series, for example, convergent at the geometric rate with ratio 2 -10 ,

ζ(3) = ∞ n=0 (-1) n n! 10 (205n 2 + 250n + 77) 64(2n + 1)! 5 (6)
was obtained by T. Amdeberhan and D. Zeilberger [START_REF] Amdeberhan | Hypergeometric series acceleration via the WZ method[END_REF] by application of WZ-pairs. There are even faster convergent representations for ζ(3) with ratios 10 -5 , 10 -8 (see [START_REF] Mohammed | Infinite families of accelerated series for some classical constants by the Markov-WZ method[END_REF]). In [START_REF] Kh | Generating function identities for ζ(2n+2), ζ(2n+3) via the WZ-method[END_REF] it was shown how to get such fast convergent series explicitly for other values ζ(n), n > 3. This can be accomplished by applying the WZ method not to the series (1) itself but to a generating function of a sequence of zeta values.

In this note, we prove a more general form of the bivariate identity (5) by application of the Markov-WZ method. We show that identity [START_REF] Bradley | Hypergeometric functions related to series acceleration formulas[END_REF] and the series (6) of Amdeberhan and Zeilberger can be proved with the help of the same Markov-WZ pair, but using different summation formulas. Moreover, we get a new identity generating accelerated series for all ζ(2n + 4m + 3), n, m ≥ 0, convergent at a geometric rate with ratio 2 -10 .

Statement of the main results

We start by giving several definitions, and by reviewing known facts related to the Markov-Wilf-Zeilberger theory (see [START_REF] Kondratieva | Markov's transformation of series and the WZ method[END_REF][START_REF] Markoff | Mémoire sur la transformation des séries peu convergentes en séries tres convergentes[END_REF][START_REF] Mohammed | Infinite families of accelerated series for some classical constants by the Markov-WZ method[END_REF][START_REF] Mohammed | The Markov-WZ method[END_REF]).

A function H(n, k), in the integer variables n and k, is called hypergeometric or closed form (CF) if the quotients

H(n + 1, k) H(n, k) and H(n, k + 1) H(n, k)
are both rational functions of n and k. A hypergeometric function that can be written as a ratio of products of factorials is called pure-hypergeometric. A pair of CF functions

F (n, k) and G(n, k) is called a WZ- pair if F (n + 1, k) -F (n, k) = G(n, k + 1) -G(n, k). (7)
A P-recursive function is a function that satisfies a linear recurrence relation with polynomial coefficients. If for a given hypergeometric function H(n, k), there exists a polynomial P (n, k) in k of the form

P (n, k) = a 0 (n) + a 1 (n)k + • • • + a L (n)k L ,
for some non-negative integer L, and P-recursive functions a 0 (n), . . . , a L (n) such that F (n, k) := H(n, k)P (n, k) satisfies ( 7) with some function G, then a pair (F, G) is called a Markov-WZ pair associated with the kernel H(n, k) (MWZ-pair for short). We call G(n, k) an MWZ mate of F (n, k).

In 2005, M. Mohammed [START_REF] Mohammed | Infinite families of accelerated series for some classical constants by the Markov-WZ method[END_REF] showed that for any pure-hypergeometric kernel H(n, k), there exists a non-negative integer L and a polynomial P (n, k) as above such that

F (n, k) = H(n, k)P (n, k) has an MWZ mate G(n, k) = F (n, k)Q(n, k), where Q(n, k) is a ratio of two P-recursive functions.
From relation (7) we get the following summation formulas.

Proposition 1 ([11, Theorem 2(b)]) Let (F, G) be an MWZ-pair. If lim n→∞ F (n, k) = 0 for every k ≥ 0, then ∞ k=0 F (0, k) -lim k→∞ ∞ n=0 G(n, k) = ∞ n=0 G(n, 0), (8)
whenever both sides converge.

Proposition 2 ([11, Cor. 2]) Let (F, G) be an MWZ-pair. If lim k→∞ ∞ n=0 G(n, k) = 0, then ∞ k=0 F (0, k) = ∞ n=0 (F (n, n) + G(n, n + 1)), (9)
whenever both sides converge.

Formulas ( 8), ( 9) with an appropriate choice of MWZ-pairs can be used to convert a given hypergeometric series into a different rapidly converging one.

Let (λ) ν be the Pochhammer symbol (or the shifted factorial) defined by

(λ) ν = Γ(λ + ν) Γ(λ) = 1, ν = 0; λ(λ + 1) . . . (λ + ν -1), ν ∈ N.
Let a, b be complex numbers such that |a| < 1, |b| < 1. In Section 3, we construct a Markov-WZ pair associated with the kernel

H(n, k) = (1 + a) k (1 -a) k (1 + b) k (1 -b) k (1 + a) n+k+1 (1 -a) n+k+1 (1 + b) n+k+1 (1 -b) n+k+1
and then apply Propositions 1, 2 to get the following two theorems.

Theorem 1 Let a, b be complex numbers, with |a| < 1, |b| < 1. Then for arbitrary complex numbers A 0 , B 0 , C 0 we have

∞ k=1 A 0 + B 0 k + C 0 k 2 (k 2 -a 2 )(k 2 -b 2 ) = ∞ n=1 d n n m=1 (m 2 -a 2 )(m 2 -b 2 )
, with

d n = (-1) n-1 B 0 (5n 2 -a 2 -b 2 ) 2n 2n n n-1 m=1 (m 2 -a 2 -b 2 ) 2 -4a 2 b 2 + 20n + 5 2(5n 2 -2a 2 -2b 2 ) L n + 35n 5 -35n 3 (a 2 + b 2 ) + 4n(3a 4 + 3b 4 -4a 2 b 2 ) 4(5n 2 -2a 2 -2b 2 ) L n-1 ,
where L n is a solution of the second order difference equation

4(4n + 3)(4n + 5)(5n 2 -2a 2 -2b 2 )L n+1 + 2(n + 1)p(n)L n -n(n + 1)(5(n + 1) 2 -2a 2 -2b 2 )q(n)L n-1 = 0, n = 1, 2, . . . with initial conditions L 0 = C 0 , L 1 = 1 3 - 2 15 (a 2 + b 2 ) A 0 + 1 6 (a 2 + b 2 ) - 2 15 (a 4 + b 4 -4a 2 b 2 ) - 1 30 C 0 ,
whose growth is described by the inequality

lim n→∞ |L n | n! 4 1 n ≤ 1 4 , and p(n
-14(a 2 + b 2 )) + (10(a 2 -b 2 ) 2 -2(a 2 + b 2 ) + 40a 2 b 2 (a 2 + b 2 ) -8(a 6 + b 6 )), (10)
q(n) = n 8 -6n 6 (a 2 + b 2 ) + n 4 (9(a 4 + b 4 ) + 30a 2 b 2 ) -n 2 (28a 2 b 2 (a 2 + b 2 ) + 4(a 6 + b 6 )) + 16a 2 b 2 (a 2 -b 2 ) 2 . ( 11
)
If in Theorem 1 we take B 0 = 1, A 0 = C 0 = 0, then L n = 0 for all n ≥ 0 and we get

∞ k=1 k (k 2 -a 2 )(k 2 -b 2 ) = ∞ n=1 (5n 2 -a 2 -b 2 )(1 + a + b) n-1 (1 + a -b) n-1 (1 -a + b) n-1 (1 -a -b) n-1 2(-1) n-1 n 2n n (1 + a) n (1 -a) n (1 + b) n (1 -b) n . ( 12
)
If we now put

a 2 = x 2 + x 4 + 4y 4 2 , b 2 = x 2 -x 4 + 4y 4 2 , (13)
we get the bivariate identity (5) conjectured by H. Cohen.

If A 0 = 1, B 0 = C 0 = a = b = 0,
ζ(4) = ∞ n=1 1 n! 4 4n + 1 2n 2 L n + 7n 3 4 L n-1 ,
where L 0 = 0, L 1 = 1/3, and

4(4n + 3)(4n + 5)L n+1 + 2(n + 1) 3 (6n 3 + 9n 2 + 5n + 1)L n -n 7 (n + 1) 3 L n-1 = 0, n ≥ 1.
Theorem 2 Let x, y be complex numbers such that

|x| 2 + |y| 4 < 1. Then ∞ k=1 k k 4 -x 2 k 2 -y 4 = 1 2 ∞ n=1 (-1) n-1 r(n) n 2n n n-1 m=1 ((m 2 -x 2 ) 2 + 4y 4 ) 2n m=n (m 4 -x 2 m 2 -y 4 ) , ( 14
)
where

r(n) = 205n 6 -160n 5 + (32 -62x 2 )n 4 + 40x 2 n 3 + (x 4 -8x 2 -25y 4 )n 2 + 10y 4 n + y 4 (x 2 -2). Since ∞ k=1 k k 4 -x 2 k 2 -y 4 = ∞ n=0 ∞ m=0 n + m n ζ(2n + 4m + 3)x 2n y 4m ,
the formula ( 14) generates Apéry-like series for all ζ(2n+4m+3), n, m ≥ 0, convergent at the geometric rate with ratio 2 -10 . So, for example, if x = y = 0, we get Amdeberhan and Zeilberger's series [START_REF] Kh | Generating function identities for ζ(2n+2), ζ(2n+3) via the WZ-method[END_REF] for

ζ(3), ζ(3) = 1 2 ∞ n=1
(-1) n-1 (205n 2 -160n + 32)

n 5 2n n 5
.

If y = 0, we recover Theorem 4 from [START_REF] Kh | Generating function identities for ζ(2n+2), ζ(2n+3) via the WZ-method[END_REF]. If x = 0, we find, in particular, the following expression for ζ (7) :

ζ(7) = 1 2 ∞ n=1 (-1) n (25n 2 -10n + 2) n 9 2n n 5 - 1 2 ∞ n=1 (-1) n (205n 2 -160n + 32) n 5 2n n 5 2n m=1 1 m 4 + n-1 m=1 3 m 4 .
3 Proof of Theorem 1.

Let a, b be complex numbers such that |a| < 1, |b| < 1. Let

H(n, k) = (1 + a) k (1 -a) k (1 + b) k (1 -b) k (1 + a) n+k+1 (1 -a) n+k+1 (1 + b) n+k+1 (1 -b) n+k+1
We are interested in finding a Markov-WZ pair associated with H(n, k). For this purpose, we define the function F (n, k) = H(n, k)P (n, k), where P (n, k) is a polynomial in k of degree L 1 with unknown coefficients as functions of n. Then

F (n + 1, k) -F (n, k) = (1 + a) k (1 -a) k (1 + b) k (1 -b) k (1 + a) n+k+2 (1 -a) n+k+2 (1 + b) n+k+2 (1 -b) n+k+2 P 1 (n, k), (15)
where P 1 (n, k) is a polynomial in k of degree L 1 + 4. From ( 15) it follows that we can determine a MWZ mate of

F (n, k) in the form G(n, k) = H(n, k)Q(n, k), where Q(n, k) is a polynomial in k of degree L 2
with unknown coefficients as functions of n. Indeed, for such a choice we have

G(n, k + 1) -G(n, k) = (1 + a) k (1 -a) k (1 + b) k (1 -b) k (1 + a) n+k+2 (1 -a) n+k+2 (1 + b) n+k+2 (1 -b) n+k+2 Q 1 (n, k),
where

Q 1 (n, k) is a polynomial in k of degree L 2 + 3. Therefore, (F, G) is a Markov-WZ pair if and only if P 1 (n, k) = Q 1 (n, k) identically for all n, k. (16)
This implies that L 2 = L 1 + 1. On the other hand, equating coefficients of powers of k on both sides of (16), we get a system of L 1 + 5 linear homogeneous equations with L 1 + L 2 + 2 = 2L 1 + 3 unknowns. In order to guarantee a solution, we should at least have that 2L 1 + 3 ≥ L 1 + 5 and hence L 1 ≥ 2, L 2 ≥ 3.

We now show that there is a non-zero solution of ( 16) with the optimal choice L 1 = 2, L 2 = 3. To see this, define two functions

F (n, k) = H(n, k)(A(n) + B(n)(k + 1) + C(n)(k + 1) 2 ), G(n, k) = H(n, k)(D(n) + E(n)k + K(n)k 2 + L(n)k 3 ), with 7 unknown coefficients A(n), B(n), C(n), D(n), E(n), K(n), L(n) as functions of n. We require that F (n + 1, k) -F (n, k) = G(n, k + 1) -G(n, k). (17)
Substituting F, G into (17) and cancelling common factors we get that (17) is equivalent to the following equation of degree 6 in the variable k :

((n + k + 2) 2 -a 2 )((n + k + 2) 2 -b 2 )(A(n) + B(n)(k + 1) + C(n)(k + 1) 2 ) -A(n + 1) -B(n + 1)(k + 1) -C(n + 1)(k + 1) 2 = ((n + k + 2) 2 -a 2 ) × ((n + k + 2) 2 -b 2 )(D(n) + E(n)k + K(n)k 2 + L(n)k 3 ) -((k + 1) 2 -a 2 ) × ((k + 1) 2 -b 2 )(D(n) + E(n)(k + 1) + K(n)(k + 1) 2 + L(n)(k + 1) 3 ). (18)
To satisfy condition (17), all the coefficients of the powers of (k + 1) in the equation ( 18) must be identically zero. This leads to a system of first order linear recurrence equations with polynomial coefficients for A

(n), B(n), C(n), D(n), E(n), K(n), L(n) C(n) = (4n 1 -3)L(n), B(n) = (4n 1 -2)K(n) -(10n 2 1 -3)L(n), n 1 = n + 1, (19)
A(n) = (4n 1 -1)E(n) -(10n 2 1 -1)K(n) + (20n 3 1 + 2n 1 (a 2 + b 2 ) -1)L(n), (20)
Finally, substitution of (25), (26) into (24) gives the second-order difference equation 20), ( 22), and polynomials p(n), q(n) defined in [START_REF] Markoff | Mémoire sur la transformation des séries peu convergentes en séries tres convergentes[END_REF], [START_REF] Mohammed | Infinite families of accelerated series for some classical constants by the Markov-WZ method[END_REF].

4(4n + 3)(4n + 5)(5n 2 -2a 2 -2b 2 )L(n + 1) + 2(n + 1)p(n)L(n) -n(n + 1)(5(n + 1) 2 -2a 2 -2b 2 )q(n)L(n -1) = 0, n = 1, 2, . . . , with initial conditions L(0) = C(0), L(1) = 1 3 - 2 15 (a 2 + b 2 ) A(0) + 1 6 (a 2 + b 2 ) - 2 15 (a 4 + b 4 -4a 2 b 2 ) - 1 30 C(0), derived from (19), (
If we put l(n) = L(n)/(n!) 4 , n = 0, 1, 2, . . . , then it is easily seen that the sequence l(n) satisfies the following recurrence equation:

4(4n + 3)(4n + 5)(5n 2 -2a 2 -2b 2 )n 3 (n + 1) 3 l(n + 1) + 2n 3 p(n)l(n) -(5(n + 1) 2 -2a 2 -2b 2 )q(n)l(n -1) = 0, n = 1, 2, . . . . (28)
Its characteristic polynomial 64λ 2 + 12λ -1 = 0 has two different zeros λ 1 = -1/4, λ 2 = 1/16. Then, by Poincaré's theorem [START_REF] Poincaré | Sur les equations linéaires aux différentielles ordinaires et aux différences finies[END_REF], for each solution l(n), n = 0, 1, 2, . . . , of (28), either l(n) = 0 for all sufficiently large n ≥ n 0 , or the limit lim n→∞ l(n + 1)/l(n) exists and equals one of the roots of the characteristic polynomial. Therefore, in both cases we get that the limit lim n→∞ |l(n)| 1/n exists and does not exceed 1/4 or

lim n→∞ |L(n)| (n!) 4 1 n ≤ 1 4 . (29)
The limit inequality (29) implies

Since in this case L(n) = 0 for all n ≥ 0, an easy computation of the right-hand side of (30) by ( 19), (20), ( 25)-( 27), and substitution (13) lead to the desired conclusion. ✷

  ) = 30n 7 + 105n 6 + n 5 (145 -52(a 2 + b 2 )) + n 4 (100 -130(a 2 + b 2 )) + n 3 (35 -124(a 2 + b 2 ) + 56(a 4 + b 4 ) -208a 2 b 2 ) + n 2(5 -56(a 2 + b 2 ) + 84(a 4 + b 4 ) -312a 2 b 2 ) + n(80a 2 b 2 (a 2 + b 2 ) -16(a 6 + b 6 ) + 48(a 4 + b 4 -3a 2 b 2 )

FFF

  (n, k) = 0 for every k ≥ 0, and therefore, by Proposition 1, we have∞ k=0 (0, k) = ∞ n=0 G(n, 0), yielding the theorem with d n = D(n -1), L n = L(n), A 0 = A(0), B 0 = B(0), C 0 = C(0). ✷ 4 Proof of Theorem 2.To deduce (14) from (17), take A(0) = C(0) = 0, B(0) = 1, and apply Proposition 2 to obtain∞ k=0 (0, k) = ∞ n=0(F (n, n) + G(n, n + 1)).

  we get the following series for ζ(4) mentioned by Markov in[10, p.18]:

Acknowledgements

The authors wish to thank Shahrekord University for financial support.

2(4n 1 + 1)L(n + 1) = 2n 1 (5n

Now multiplying equation ( 22) by n 1 and subtracting from (23), we get

which yields

From (19) it follows that 2K(0) = B(0) + 7L(0), and therefore we have

Substitution of (25) into (22) yields the formula

Substitution of ( 25) and ( 26) into (21) gives the formula


Peter Hertling

Christoph Spandl

Shifts with Decidable Language and Non-Computable Entropy

Keywords: Shift spaces, topological entropy, language of a shift space, computability, computable real numbers, right computable real numbers

We consider subshifts of the full shift of all binary bi-infinite sequences. On the one hand, the topological entropy of any subshift with computably co-enumerable language is a right-computable real number between 0 and 1. We show that, on the other hand, any right-computable real number between 0 and 1, whether computable or not, is the entropy of some subshift with even polynomial time decidable language. In addition, we show that computability of the entropy of a subshift does not imply any kind of computability of the language of the subshift.

Introduction

An important numerical quantity associated with a dynamical system is its topological entropy. A natural question is then: under what circumstances can one compute the topological entropy of a dynamical systems? While for specific types of dynamical systems, one can often give an algorithm, for examples see, e.g., [START_REF] Milnor | Is entropy effectively computable? Remark[END_REF], there are also a number of negative results, e.g., for cellular automata by [START_REF] Hurd | The topological entropy of cellular automata is uncomputable[END_REF], for piecewise affine maps by [START_REF] Koiran | The topological entropy of iterated piecewise affine maps is uncomputable[END_REF], and for shift spaces by [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] as well as by the second author, [START_REF] Spandl | Computing the topological entropy of shifts[END_REF]. Shift spaces are an important, standard class of dynamical systems. For an introduction the reader is referred to [START_REF] Lind | Symbolic Dynamics and Coding[END_REF]. They are closed, shift invariant subspaces of the space of bi-infinite sequences over some alphabet, usually assumed to be finite. For simplicity we will consider only subshifts of the space of all bi-infinite binary sequences. Whenever we speak about a shift space or simply a shift in this paper, we will always mean a closed, shift invariant subspace of the space of bi-infinite binary sequences.

As is well known, for simple types of shifts one can compute the entropy, for example for shifts that can be defined by a finite set of forbidden words, and also for the larger class of so-called sofic shifts; see [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF]; [START_REF] Spandl | Computing the topological entropy of shifts[END_REF]. Furthermore, [START_REF] Simonsen | On beta-shifts having arithmetical languages[END_REF] obtained computability results for the entropy of β-shifts, [START_REF] Spandl | Computing the topological entropy of shifts[END_REF], as well as [START_REF] Hertling | Computability theoretic properties of the entropy of gap shifts[END_REF], for the entropy of S-gap shifts, and [START_REF] Spandl | Computing the topological entropy of shifts[END_REF] also for the entropy of shifts having the specification property. [START_REF] Hochman | A characterization of the entropies of multidimensional shifts of finite type[END_REF] gave a computability-theoretic characterization similar to our main result of the set of real numbers that are the entropy of a two-dimensional shift of finite type.

A natural way of describing a general shift is via its language, that is the set of all finite strings that appear as substrings of elements of the shift space. [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] and [START_REF] Spandl | Computing the topological entropy of shifts[END_REF] have shown that the entropy is not uniformly computable with respect to the language of the shift. To be precise, [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] has shown that there is no Turing machine which, given a decision algorithm for the language of some shift with decidable language, is able to compute the entropy of the shift with arbitrary precision. [START_REF] Spandl | Computing the topological entropy of shifts[END_REF] has shown that there is no oracle Turing machine which, given the language of some shift via an oracle, is able to compute the entropy of the shift with arbitrary precision. [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] posed the question whether there exists a shift with decidable language whose entropy is a noncomputable number, and noted that "then the results in this paper related to uncomputability would follow immediately". In this paper, we construct such a shift. In fact we will show more. The second author, [START_REF] Spandl | Computing the topological entropy of shifts[END_REF], showed that, given an enumeration of the complement of the language of some shift space, one can approximate the entropy effectively from the right. Hence, if the complement of the language of a nonempty shift is computably enumerable then the entropy of the shift is a right-computable real number (between 0 and 1). In particular, the entropy of any nonempty shift with decidable language is a right-computable real number between 0 and 1. We will show that conversely any right-computable real number between 0 and 1 is the entropy of a shift with decidable language. In fact, it is even the entropy of an irreducible shift with a polynomial time decidable language. Since the class of right-computable real numbers between 0 and 1 is known to be strictly larger than the class of computable real numbers between 0 and 1, this shows that there exist irreducible shifts with polynomial time decidable language that have non-computable entropy.

In the following section, we give some basic definitions about shifts, forbidden words, and the language of a shift. Note that another natural way of representing a shift space is by giving a so-called set of forbidden words for it. In view of the question whether, given some information about a shift, one can compute its entropy, it is of course interesting to have a clear picture of the relation between different kinds of information about a shift. Here, we analyze the relation between two different kinds of information about a general shift, namely: language or set of forbidden words, and strengthen the observation by [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] that knowing the language of a shift is better than knowing only a set of forbidden words for the shift. Then we define the topological entropy. We observe that the obstacle to computing the topological entropy of a shift from its language is a topological one. Then we state the main result of the paper. We finish the section by considering the inverse question: if the topological entropy of a shift is computable, does this imply that the language is decidable, at least if the complement of the language is known to be c.e.? We show that this is not the case. On the contrary, we show that there exist shifts with topological entropy zero whose language is of any desired degree of computability-theoretic complexity. In the penultimate section, we prove the main result. We conclude with a summary and some open problems.

Shifts, Sets of Forbidden Words, and Languages of Shifts

We write N = {0, 1, 2, . . .} for the set of natural numbers, i.e., of non-negative integers, Σ = {0, 1} for the binary alphabet, Σ * for the set of all finite binary strings, λ for the empty string, Σ n for the set of all binary strings of length n, for any n ∈ N. A subset of Σ * is called (binary) language. A subset of Σ * or of N is called computably co-enumerable (co-c.e.) if its complement is computably enumerable (c.e.). Furthermore, we write Σ ω := {p | p : N → Σ} for the set of all one-way infinite binary sequences, and A string w ∈ Σ * is a substring of some p ∈ Σ Z if there is an n ∈ Z with w = p[n + 1 . . . n + |w|]. For any sets X and Y , we write f :⊆ X → Y for a function whose domain dom(f ) is a subset of X and whose range is a subset of Y . In case dom(f ) = X we may write f : X → Y . Endowed with the product topology of the discrete topology on Σ, both Σ ω and Σ Z are compact topological spaces. The function

Σ Z := {p | p : Z → Σ}
σ : Σ Z → Σ Z defined by σ(p)[n] := p[n + 1] for p ∈ Σ Z and n ∈ Z is called the shift map. It is a homeomorphism. Definition 1 We call a subset X ⊆ Σ Z a shift or a shift space or a subshift of Σ Z if it is closed and satisfies σ(X) = X.
Examples of shift spaces are easily obtained.

Lemma 2 For an arbitrary set F ⊆ Σ * the set X F ⊆ Σ Z defined by

X F := {p ∈ Σ Z | no string in F is a substring of p} is a shift space.
Proof: See (Lind and Marcus, 1995, Definition 1.2.1 and Theorem 6.1.21).

✷ Definition 3 If F ⊆ Σ * is a set with X = X F , then F is called a set of forbidden words for X.
This poses the question whether every shift space can be defined via a set of forbidden words, i.e., whether for every shift space X there is a set F with X = X F . The answer is yes, as can be seen via the "language" of the shift space. Definition 4 For any set X ⊆ Σ Z the set L(X) := {w ∈ Σ * | w is a substring of some p ∈ X} is the language of X.

For any shift space X, the complement L(X) c of L(X) is a set of forbidden words for X, i.e., X = X L(X) c (indeed, X ⊆ X L(X) c is clear, and X L(X) c ⊆ X follows from the assumption that X is closed). In fact, it is the largest forbidden set of words for X since any other set of forbidden words for X is obviously a subset of L(X) c .

Example 5 For the shift space X := {0 Z } containing only the bi-infinite sequence containing only 0's, one sees L(X) = {0} * , hence, L(X) c = {0, 1} * \ {0} * . Any set F with {1} ⊆ F ⊆ {0, 1} * \ {0} * is a set of forbidden words for X. Also the sets {10, 11} and {01, 11} and so on are sets of forbidden words for X.

A particularly simple class of shifts are those that possess a finite set of forbidden words. But in general, a shift does not need to have a finite set of forbidden words. So, if one wishes to compute something associated with a shift, e.g., its entropy, one needs some kind of description of the shift as input for the algorithm. What is a natural description of a general shift X? One might assume that one knows the characteristic sequence of either a set of forbidden words for X or of L(X). Here the characteristic sequence χ S of a set S ⊆ Σ * is the binary sequence χ S ∈ Σ ω defined by

χ S (n) := 1 if ν(n) ∈ S, 0 if ν(n) ∈ S
where the bijection ν : N → Σ * is defined by the length-lexicographical ordering: order all strings in Σ * according to their length (short strings first), and strings of the same length in alphabetical order.

We have just seen that, given the language of a shift, one can easily compute a set of forbidden words for the shift: just take the complement of the language of the shift. But (Simonsen, 2006, Remark 17) showed that there is no Turing machine which, given a decision algorithm for some decidable set F ⊆ Σ * , computes a decision algorithm for the language L(X F ). The argument used by Simonsen in order to prove this statement is actually a topological one: the function mapping the characteristic sequence of an arbitrary forbidden set of a shift to the characteristic sequence of its language is not continuous and can therefore not be computable. Note that any function H :⊆ Σ ω → Σ ω that can be computed by a (Type-2) Turing machine is continuous; see, e.g., [START_REF] Weihrauch | Computable Analysis[END_REF].

Proposition 6 The function G : Σ ω → Σ ω , defined by G(χ F ) := χ L(XF ) is not continuous. Proof: A point of discontinuity is for example the sequence 0 ω = χ ∅ . Note that G(0 ω ) = 1 ω because L(X ∅ ) = L(Σ Z )
is the whole set Σ * . If G were continuous in 0 ω , there should be a finite prefix 0 n of 0 ω such that G(0 n Σ ω ) ⊆ 1Σ ω . But if F is the set of all binary strings of length greater than log 2 (n) then χ F also starts with 0 n , but

X F = ∅, hence L(X) = ∅, hence χ L(X) = 0 ω . ✷
We will strengthen Simonsen's remark (Simonsen, 2006, Remark 17) in the following way: in Corollary 11 we will see that there exists a decidable set F such that L(X F ) is not decidable. That means that there exists computable input for the function G in Proposition 6 which is mapped by this function to non-computable output. Note that any computable function H :⊆ Σ ω → Σ ω maps any computable binary sequence p ∈ dom H to a computable binary sequence; see, e.g., [START_REF] Weihrauch | Computable Analysis[END_REF]. Before we construct such a computable input, let us clarify what one can compute when one knows (an oracle for) some set F , i.e., if χ F for some set F is given. We will see that one can still enumerate L(X F ) c . In fact in order to be able to do that, it is sufficient to be able to enumerate F . We formulate only a non-uniform (not involving oracle Turing machines) version of this statement.

Proposition 7 If F ⊆ Σ * is a computably enumerable set, then L(X F ) c is computably enumerable as well.

Proof: If a set F is computably enumerable, then also the set of all strings in Σ * that have a substring in F is computably enumerable. The assertion follows now from the following lemma.

✷

Lemma 8 Fix some set F ⊆ Σ * . A string v is in L(X F ) c
if, and only if, there exists some n ∈ N such that each of the 2 2n strings uvw with u, w ∈ Σ n has a substring in F .

Proof: For a string v we set

K v := {p ∈ Σ Z | v = p[0 . . . |v| -1]}. A string v is in L(X F ) c
if, and only if, every p ∈ K v contains an element of F as a substring. And this is the case if, and only if, for any p ∈ K v there is some n ∈ N such that p[-n . . . |v| -1 + n] contains an element of F as a substring. Now, the claim follows easily from the compactness of the set K v , for any v. ✷

Especially, if a shift X has a decidable set of forbidden words, then L(X) c must be a c.e. set. The converse is true as well.

Theorem 9 If X is a shift such that L(X) c is c.e., then there exists a polynomial time decidable set F ⊆ Σ * with X = X F .

Proof: This is proved by a padding argument. Let X be a shift such that L(X) c is computably enumerable. Let M be a Turing machine that halts on input v ∈ Σ * after finitely many steps if, and only if,

v ∈ L(X) c . Let h :⊆ Σ * → N be defined by h(v) := number of steps until M halts on input v if v ∈ L(X) c , undefined if v ∈ L(X).
We define a set F ⊆ Σ * as follows:

F := v∈L(X) c {vw | w ∈ {0, 1} h(v) }.
We claim that this set F has the desired properties. "X = X F ": This is clear. "F is decidable in polynomial time": A Turing machine that decides for a given string x ∈ Σ * in time polynomial in |x| whether x belongs to F or not can work for example as follows. For every prefix v of x it starts M with input v, lets M run for at most |x| -|v| + 1 steps and accepts x if, and only if, there is a prefix v of x such that M stops on input v after exactly |x| -|v| steps. ✷

Corollary 10 For a shift X the following conditions are equivalent:

1. L(X) c is computably enumerable.

2. X has a c.e. set of forbidden words.

3. X has a polynomial time decidable set of forbidden words.

Proof: "3 ⇒ 2": This is trivial. "2 ⇒ 1": This is Proposition 7. "1 ⇒ 3": This is Theorem 9. ✷ Now we easily conclude that there is computable input for the function G in Proposition 6 which is mapped by G to non-computable output.

Corollary 11 There exists a polynomial time decidable set F ⊆ Σ * such that L(X F ) is not decidable.

Proof: In order to derive this from Theorem 9 it is sufficient to observe that there exist shifts whose language is co-c.e., but not decidable. For an infinite set S ⊆ N, define

F (S) := {10 n 1 | n ∈ N \ S}.
Fix some co-c.e., but not decidable set S ⊆ N (such a set must be infinite). Then N \ S and F (S) are c.e. and not decidable. By Proposition 7 also L(X F (S) ) c is computably enumerable. But L(X F (S) ) c is not decidable because a string of the form 10 n 1 is in L(X F (S) ) c if, and only if, n ∈ N \ S.

✷

Remark 12 For an infinite set S ⊆ N, the shift X F (S) defined in the proof is called S-gap shift (Lind and Marcus, 1995, Example 1.2.6). For a finite, nonempty set S ⊆ N, the shift X F (S) is called S-gap shift where

F (S) := {10 n 1 | n ∈ N \ S} ∪ {0 1+max(S) };
see (Lind and Marcus, 1995, Example 1.2.6).

Corollary 11 strengthens Simonsen's observation (Simonsen, 2006, Remark 17) that there can be no Turing machine which, given a decision algorithm for any decidable set F ⊆ Σ * , computes a decision algorithm for L(X F ).

The Entropy of Shifts with Decidable or with Computably Co-Enumerable Language

The following statement is Proposition 4.1.8 in [START_REF] Lind | Symbolic Dynamics and Coding[END_REF].

Proposition 13 If X is a shift, then lim n→∞ log 2 |L(X) ∩ Σ n | n
exists, and equals

inf n≥1 log 2 |L(X) ∩ Σ n | n
Here we use log 2 (0) := -∞.

Definition 14 For a shift X, the value h top (X) := lim n→∞

log 2 |L(X)∩Σ n | n is called the (topological) entropy of X.
The entropy of the empty shift is -∞. In the rest of the paper we will only consider nonempty shifts. It is clear that the entropy of a nonempty subshift of {0, 1} Z is always a real number between 0 and 1, i.e., a real number in the closed interval [0, 1]. The converse is true as well; one can even restrict oneself to irreducible shifts.

Definition 15 A shift X is called irreducible if for any two strings u, w ∈ L(X) there is a string v ∈ Σ * with uvw ∈ L(X).
The irreducible shifts form an important subclass of shifts; compare [START_REF] Lind | Symbolic Dynamics and Coding[END_REF].

Proposition 16

1. The entropy of a nonempty shift is a real number in the interval [0, 1].

Any real number in [0, 1] is the entropy of a nonempty, irreducible shift.

Proof: The first assertion is clear. The second assertion follows immediately from (Lind and Marcus, 1995, Exercise 4.3.7(d)) where it is stated that every real number in [0, 1] is the entropy of an S-gap shift, as defined in Remark 12, following (Lind and Marcus, 1995, Example 1.2.6). It is clear that any S-gap shift is irreducible. ✷

A different proof of the second statement will be given in the following section. In fact, the proof of our main result (see below) will show how, given a non-increasing sequence of rational numbers in [0, 1], one can construct an irreducible shift whose entropy equals the limit of this sequence.

Can one compute the entropy of a shift? What kind of information does one need to have about the shift in order to compute its entropy? By (Spandl, 2007, Theorem 6.3) one can effectively approximate the entropy from the right if one has an enumeration of L(X) c . We state a non-uniform version of this precisely. Therefore, we need the notion of a right-computable real number. We directly define also the (more basic) notion of a computable real number.

Definition 17

1. A sequence (q n ) n∈N of rational numbers is computable if there exist three total computable functions s, a, b :

N → N with b(n) = 0 and q n = (-1) s(n) • a(n)/b(n), for all n.
2. A real number x is computable if there exists a computable sequence (q n ) n∈N of rational numbers with |xq n | ≤ 2 -n , for all n ∈ N.

A real number

x is right-computable if there exists a computable sequence (q n ) n∈N of rational numbers with q n ≥ q n+1 for all n ∈ N (a sequence satisfying this condition will be called nonincreasing) and x = lim n→∞ q n .

Remark 18 Similarly, a real number is called left-computable if it is the limit of a computable nondecreasing sequence of rational numbers. Obviously, a real number x is right-computable if, and only if, -x is left-computable. And a real number is computable if, and only if, it is left-computable and rightcomputable. But it is well known that the class of left-computable real numbers is strictly larger than the class of computable real numbers; the same applies to the class of right-computable real numbers. If, e.g., K ⊆ N is a c.e., but undecidable set, then the number 1 -n∈K 2 -(n+1) is a right-computable but not computable real number between 0 and 1; see, e.g., [START_REF] Weihrauch | Computable Analysis[END_REF]. For an overview concerning left-computable real numbers and other classes of real numbers defined by computability properties, see [START_REF] Zheng | Recursive approximability of real numbers[END_REF].

Proposition 19 If X is a nonempty shift such that L(X) c is c.e., then the entropy of X is a rightcomputable real number.

Proof:

This follows from h top (X) = inf n≥1 log 2 |L(X)∩Σ n | n (Proposition 13).
It is also a direct consequence of (Spandl, 2007, Theorem 6.3).

✷

Corollary 20 If a nonempty shift X has a c.e. set of forbidden words, then its entropy is a right-computable real number.

Proof: By the previous proposition and Proposition 7. ✷

Of course, one would like not only to approximate the entropy from the right, but to compute it with any precision. [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] and the second author, [START_REF] Spandl | Computing the topological entropy of shifts[END_REF], have shown that the entropy is not uniformly computable with respect to the language of the shift. To be precise, [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] has shown that there is no Turing machine which, given a decision algorithm for the language of some shift with decidable language, is able to compute the entropy of the shift with arbitrary precision. In fact, [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] showed that this negative result is true even if one restricts oneself to the class of irreducible shifts. The second author, [START_REF] Spandl | Computing the topological entropy of shifts[END_REF], showed that there is no oracle Turing machine which, given the language of some shift via an oracle, is able to compute the entropy of the shift with arbitrary precision. In fact, as was noted by [START_REF] Spandl | Computing the topological entropy of shifts[END_REF] and by [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] as well, these negative statements are true for topological reasons, similarly as the negative statement of Proposition 6 in the previous section was true for topological reasons.

Proposition 21

The function

H :⊆ Σ ω → R with dom H = {χ L(X) | X is a nonempty, irreducible shift}, H(χ L(X) ) = h top (X) for any such shift X.
is discontinuous. It is even discontinuous if on R the weaker topology is considered whose open sets are the sets (a, ∞), with a ∈ R, and the sets ∅, R.

The proof will be given in the following section. The proposition says essentially that there is no algorithm, in fact not even a continuous function, which, given the characteristic function of the language of a shift, would deliver arbitrarily good lower bounds to the entropy of the shift.

Simonsen (Simonsen, 2006, Page 94) then asked the question whether there exists a shift with decidable language but non-computable entropy. We shall show that this is indeed the case. Note that this strengthens the negative results by [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] and [START_REF] Spandl | Computing the topological entropy of shifts[END_REF] about the noncomputability of the entropy when the language of a shift is known. In fact, we shall show more. We have already seen that the entropy of any nonempty shift X with decidable language (even with co-c.e. language) is a right-computable real number between 0 and 1. We shall show that any such number is the entropy of a shift with decidable language. It is even the entropy of an irreducible shift with a polynomial time decidable language. The following theorem is the main result of this paper.

Theorem 22 For every right-computable real number α ∈ [0, 1] there exists a nonempty, irreducible shift X with h top (X) = α and with polynomial time decidable language L(X).

The proof will be given in the following section.

Corollary 23 For a real number α the following conditions are equivalent.

1. α ∈ [0, 1] and α is right-computable.

2. There exists a shift X with co-c.e. language L(X) and entropy α.

3. There exists an irreducible shift X with polynomial time decidable language L(X) and entropy α.

Proof: "3 ⇒ 2": Trivial.

"2 ⇒ 1": By Proposition 19 and Proposition 16.1. "1 ⇒ 3": By Theorem 22. ✷

Corollary 24 There exists an irreducible shift X with polynomial time decidable language L(X) such that its entropy h top (X) is not a computable real number.

Proof: In Remark 18 we already mentioned that there exist right-computable real numbers between 0 and 1 that are not computable. ✷

Remark 25 Our main result, Theorem 22, can be considered as an effective version of Proposition 16.2. We will see that by simplifying the proof (by forgetting about effectivity properties) one obtains a second proof of Proposition 16.2.

One may now also ask the other way around whether it might not be possible to prove our main result by effectivizing the proof given above for Proposition 16.2, i.e., by effectivizing the statement of (Lind and Marcus, 1995, Exercise 4.3.7(d)) that any real number in [0, 1] is the entropy of an S-gap shift (compare Remark 12). Thus, the question arises whether for an arbitrary right-computable real number α ∈ [0, 1] there is an S-gap shift with entropy α and decidable language. The answer to this question is no, as was observed already by the second author in (Spandl, 2007, Section 7): for a nonempty set S ⊆ N, the language of the S-gap shift X F (S) is decidable if, and only if, S is decidable, and in that case the entropy h top (X F (S) ) is a computable real number.

We have seen that decidability of the language of a shift implies right-computability of the entropy, but not computability of the entropy. One might ask also the inverse question: does computability of the entropy of a shift imply any computability property of the language of the shift, e.g., that is is decidable, perhaps at least if the language is already known to be co-c.e.? The next result shows that this is not the case. In order to formulate it we remind the reader of some notions from computability theory. A language L ⊆ Σ * is many-one reducible to a set S ⊆ N if there is a total computable function h : Σ * → N with x ∈ L ⇐⇒ h(x) ∈ S, for any x ∈ Σ * . Conversely, a set S ⊆ N is many-one reducible to L ⊆ Σ * if there is a total computable function g : N → Σ * with x ∈ S ⇐⇒ g(x) ∈ L, for any x ∈ N. Finally, L ⊆ Σ * and S ⊆ N are called many-one equivalent to each other if L is many-one reducible to S and S is many-one reducible to L. If two sets are many-one equivalent to each other then they have the same computability-theoretic degree of difficulty. For example, if one of them is decidable resp. c.e. resp. co-c.e., then the other one has the same property.

Theorem 26 For any set S ⊆ N with S = ∅ and S = N there exists a shift over the binary alphabet whose topological entropy is equal to zero and whose language is many-one equivalent to S.

Proof:

For s ∈ N we define X per (s) := {c ∈ {0, 1} Z | c contains infinitely many 1's, and, for any k ∈ N, the string 10 k 1 is a substring of c if, and only if, k = s}.

In other words, X per (s) contains exactly the s + 1 bi-infinite binary periodic sequences of the form . . . 10 s 10 s 10 s 1 . . . .

For finite S ⊆ N with S = ∅, we define

X per (S) := s∈S X per (s),
and for infinite S ⊆ N, we define

X per (S) := {0 Z } ∪ {p ∈ Σ Z | p contains exactly one 1} ∪ s∈S X per (s).
Let us fix a set S ⊆ N with S = ∅. First, we show that X per (S) is a shift space. The set X per (S) is obviously invariant under the shift map σ, i.e., σ(X per (S)) = X per (S). Furthermore, it is closed. In the case of infinite S, we ensured that X per (S) is closed by adding the sequence 0 Z and the sequences in Σ Z containing exactly one 1. Now, we show that h top (X per (S)) = 0. Since X per (S) is nonempty and a subset of X per (N), it is sufficient to show that h top (X per (N)) = 0. Consider some n > 0. Let us give an upper bound on the number of strings in L(X per (N)) ∩ Σ n . Clearly,

L(X per (N)) ∩ Σ n = {0 n } ∪ n-1 s=0 (L(X per (s)) ∩ Σ n ) and, for any s ∈ N, |L(X per (s)) ∩ Σ n | ≤ s + 1, thus, |L(X per (N)) ∩ Σ n | ≤ 1 + n(n + 1) 2 , hence, 0 ≤ h top (X per (N)) ≤ lim n→∞ log 2 (1 + n(n + 1)/2) n = 0.
In the rest of the proof we assume not only S = ∅, but also S = N. We still have to show that L(X per (S)) is many-one equivalent to S. The set S is many-one reducible to L(X per (S)) because, for s ∈ N, s ∈ S ⇐⇒ 10 s 1 ∈ L(X per (S)).

For the inverse claim (that L(X per (S)) is many-one reducible to S) we distinguish two cases.

1. S is finite. Then L(X per (S)) is obviously decidable. Thus, both sets are decidable. Since furthermore ∅ S N and ∅ L(X per (S)) Σ * , they are many-one equivalent.

2. S is infinite. Then L(X per (S)) contains all strings that contain at most one 1. And a string w with two or more 1's is in L(X per (S)) if, and only if, it satisfies the following two conditions:

(A) w contains at least two 1's, and there is some s ≤ |w| such that w is a substring of the periodic bi-infinite sequence . . . 10 s 10 s 10 s 1 . . . , (B) this number s (if is exists, it is obviously uniquely determined) is an element of S.

Condition (A) can be checked directly, and Condition (B) can be checked by a many-one reduction to S. To complete the proof formally, we define a computable reduction function h L(Xper(S)),S : Σ * → N from L(X per (S)) to S. Fix some s yes ∈ S and some s no ∈ S (remember our assumptions S = ∅ and S = N). We define

h L(Xper(S)),S (w) :=         
s yes if w contains at most one 1, s no if w contains at least two 1's, but does not satisfy Condition (A), s if w satisfies Condition (A), and s is the number of 0's between any two 1's in w between which there is no other 1.

It is clear that this function is computable and reduces L(X per (S)) to S.

We have shown that X per (S) has all the desired properties. ✷

Corollary 27 There exists a shift over the binary alphabet whose entropy is zero and whose language is co-c.e., but not decidable.

Proof: By taking for S in Theorem 26 any co-c.e., but undecidable set, one obtains such a shift. ✷

Proofs

In this section, we prove Proposition 21 and Theorem 22. In addition, we give a new proof of Proposition 16.2. Certain sofic shifts (compare [START_REF] Lind | Symbolic Dynamics and Coding[END_REF]) will play an important role.

Definition 28

1. A finite Σ-labeled graph is a pair (V, E) consisting of a finite set V (the set of nodes) and a finite set E ⊆ V × V × Σ (the set of edges labeled with elements of Σ).

2. For a finite Σ-labeled graph (V, E), we define three functions start : E → V , end : E → V , and label : E → Σ giving the three components of a labeled edge as follows:

e = (start(e), end(e), label(e)),

for any e ∈ E.

3. A bi-infinite path through a finite Σ-labeled graph (V, E) is a function q : Z → E such that end(q(i)) = start(q(i + 1)), for all i ∈ Z.

Lemma 29 If (V, E) is a finite Σ-labeled graph, then the following set is a shift and called the sofic shift defined by the graph: {p ∈ Σ Z | there exists a bi-infinite path q : Z → E through the graph such that p[i] = label(q(i)), for all i ∈ N}.

For the proof see (Lind and Marcus, 1995, Section 3.1). By {0, * } + we denote the set of all nonempty strings over the alphabet {0, * }. Definition 30 For any w ∈ {0, * } + , let X(w) be the sofic shift defined by the graph defined as follows.

The graph has |w| nodes v 0 , . . . , v |w|-1 . For each i ∈ {0, . . . , |w| -1}, it has an edge labeled with 0 from v i to v i+1 mod |w| . Additionally, for i ∈ {0, . . . , |w| -1}, it has an edge labeled with 1 from v i to v i+1 mod |w| if, and only if,

w[i] = * (where w = w[0]w[1] . . . w[|w| -1]).
Example 31 The graph of X(w) for w = 00 * 0 * * 00 is depicted in Figure 1.

The shift X(w) can be described as follows: its elements are exactly all bi-infinite binary sequences of the form . . . v -2 v -1 v 0 v 1 v 2 . . . where, for every i ∈ Z, v i is a binary string of length |w| that matches w in the following sense: at every position where v i has a 1, w must have a * . It is equivalent to say that v i can be obtained from w by replacing every * in w either by a 0 or a 1. In the following we will call any element of {0, * } * a pattern. In the next lemma we collect several useful properties of the shifts X(w).

Lemma 32

1. For any w ∈ {0, * } + , 0 Z ∈ X(w). Hence, X(w) is nonempty.

2. For any w ∈ {0, * } + , X(w) is irreducible.

3. For any w ∈ {0, * } + , h top (X(w)) = # * (w) |w| (where # * (w) is the number of * 's in w).

4. For any w ∈ {0, * } + and any integer k ≥ 1, X(w k ) = X(w).

5. For any v, w ∈ {0, * } + , if |v| = |w| and if v can be obtained from w by replacing some * 's in w by 0's, then X(v) ⊆ X(w).

6. For any w ∈ {0, * } + , any integers a, b with a ≥ 2 and b ≥ 0, and any v ∈ Σ * with |v| ≤ |w|, one has v ∈ L(X(w)) ⇐⇒ v ∈ L(X(w a 0 |w|•b ).

Proof:

1. Clear.

2. Clear.

3. Left to the reader (compare, e.g., Lemma 20 and Theorem 21 in Simonsen ( 2006)).

4. Clear.

5. Clear.

6. Since by Statements 4 and 5 of this lemma, the set L(X(w a 0 |w|•b )) is a subset of L(X(w)), the direction from right to left is clear. For the other direction, assume that v ∈ L(X(w)) and |v| ≤ |w|.

Then v matches a subpattern of ww. Since a ≥ 2, we obtain v ∈ L(X(w a 0 |w|•b ).

✷

Proof of Proposition 21:

The function H defined in Proposition 21 is discontinuous for example in 1 ω , even with respect to the weaker topology on R, mentioned in Proposition 21. Note that

1 ω = χ Σ * = χ L(Σ Z )
, and that the full shift Σ Z = X( * ) has entropy 1 and is irreducible. If H were continuous in 1 ω with respect to the weaker topology on R, then there would be a finite prefix 1 n of 1 ω with n ≥ 2 such that the entropy of any shift X with the property that χ L(X) starts with 1 n would be strictly larger than 1/2. In that case, we set l := ⌈log 2 (n)⌉, and observe that by Lemma 32.3 the shift X( * l 0 l ) has entropy 1/2, but, obviously, all strings of length ≤ l are in the language of this shift, hence, the characteristic sequence of its language starts with 1 n as well. ✷

Before we come to the proof of Theorem 22, we need some more preparations. We had defined rightcomputable real numbers as the limits of computable, non-increasing sequences of rational numbers. In fact, one can restrict oneself to dyadic rational numbers, and one can ask that the sequence can be computed quite fast. A sequence (z n ) n∈N of natural numbers is computable in time polynomial in n if there is a Turing machine which, given a binary name of some n ∈ N, computes a binary name of z n in time bounded by a polynomial in n.

Lemma 33 A real number α ∈ [0, 1] is right-computable if, and only if, there is a sequence (z n ) n∈N of natural numbers computable in time polynomial in n such that z n ∈ {1, . . . , 2 n }, for all n, and such that the sequence (z n /2 n ) n∈N is non-increasing and converges to α.

For reasons which will become clear in the proof of Theorem 22, we do not allow z n = 0.

Proof:

The direction from right to left is clear: for a sequence (z n ) n∈N with the properties formulated in Lemma 33 the limit lim n→∞ z n /2 n is a right-computable real number in [0, 1].

We come to the direction from left to right. Let α ∈ [0, 1] be right-computable. Let us assume that a computable, non-increasing sequence (q n ) n∈N of rational numbers with lim n→∞ q n = α is known. The sequence (y n ) n∈N defined by

y n := min{i ∈ {1, . . . , 2 n } | i/2 n ≥ min{1, q n }}
is a computable sequence of integers y n ∈ {1, . . . , 2 n } such that the sequence (y n /2 n ) n∈N is nonincreasing and converges to α. The only problem why we cannot take y n for z n is that the sequence (y n ) n∈N might not be computable in time polynomial in n. Let M be a Turing machine which, without ever stopping, writes the one-way infinite sequence bin(y 0 )#bin(y 1 )#bin(y 2 )# . . . onto a one-way output tape, where, for an integer x, we denote its binary name by bin(x). We define the desired sequence (z n ) n∈N as follows.

For z n , perform the first n steps of the computation of M . Let m be the number of #'s written by M during these steps. In case m = 0, define z n := 2 n . In case m > 0, define

z n := y m-1 • 2 n+1-m .
Note that y 0 = 1 and that for any x, l ∈ N with x > 0 it is clear that bin(x • 2 l ) = bin(x)0 l . It is clear that the sequence (z n ) n∈N is computable in time polynomial in n. Furthermore, z n ∈ {1, . . . , 2 n } for all n, and the sequence (z n /2 n ) n∈N is non-increasing and converges to α. ✷

The strategy of the proof of Theorem 22 is to consider a computable sequence of integers (z n ) n∈N as in the previous lemma and to construct a decreasing sequence of (sofic) shifts X n with entropy equal to z n /2 n . Then the desired shift X will be defined as the limit of the shifts X n , as in the following lemma.

Lemma 34 Let (X n ) n∈N be a sequence of nonempty subshifts of Σ Z with X n+1 ⊆ X n for all n. Set X := n∈N X n . Then 1. X is a nonempty subshift of Σ Z as well, 2. L(X) = n∈N L(X n ), 3. h top (X) = lim n→∞ h top (X n ).
Proof: The first statement, that X is a subshift of Σ Z , is shown once we have shown that X is nonempty and closed and that σ(X) = X.

"X is nonempty": Consider an arbitrary sequence (x n ) n∈N of elements x n ∈ X n , for each n. Since Σ Z is compact, this sequence has an accumulation point in Σ Z . Let us call it x. Since for all n ∈ N and all m ≥ n we have x m ∈ X m ⊆ X n , we conclude that x is contained in the closure of X n for all n, hence in X n itself for all n, hence x ∈ X. Thus, X is nonempty.

"X is closed": For every n, X n is closed, and the intersection of arbitrarily many closed sets is closed again.

"σ(X) ⊆ X": From σ(X n ) ⊆ X n for all n we obtain σ( n∈N X n ) ⊆ n∈N X n , i.e., σ(X) ⊆ X. "σ(X) ⊇ X": Let us fix some y ∈ X. We have to show that there is some x ∈ X with σ(x) = y. Since y ∈ X n and σ(X n ) ⊇ X n , for all n, for every n ∈ N there is some x n ∈ X n with σ(x n ) = y. As in the proof of "X is nonempty" we can conclude that the sequence (x n ) n∈N has an accumulation point x, and that x is an element of X. The sequence (x n ) n∈N has a subsequence that converges to x. Since σ(x n ) = y for all n and since σ is continuous, we conclude that σ(x) = y.

"L(X) ⊆ n∈N L(X n )": For any subshifts Y, Z of Σ Z with Y ⊆ Z one has L(Y ) ⊆ L(Z). The assertion follows.

"L(X) ⊇ n∈N L(X n )": Let us fix some w ∈ n∈N L(X n ). For every n ∈ N there is some x n ∈ X n such that x n [0 . . . |w| -1] = w. As in the proof of "X is nonempty" we can conclude that the sequence (x n ) n∈N has an accumulation point x, and that x is an element of X. It is also clear that x[0, . . . , |w|-1] = w. This implies w ∈ L(X).

"h top (X) = lim n→∞ h top (X n )": Since for any subshifts Y, Z of Σ Z with Y ⊆ Z one has h top (Y ) ≤ h top (Z), the sequence h top (X n ) is non-increasing. Since it is bounded from below by 0, the limit lim n→∞ h top (X n ) exists. Furthermore, h top (X) ≤ h top (X n ), for all n, follows as well, hence h top (X) ≤ lim n→∞ h top (X n ). We still have to show that h top (X) cannot be strictly smaller than lim n→∞ h top (X n ).

In order to show this, let us fix some ε > 0. We show that h top (X n ) ≤ h top (X) + ε for almost all n. Remember that for an arbitrary subshift Y of Σ Z ,

h top (Y ) = lim k→∞ log 2 |L(Y ) ∩ Σ k | k = inf k≥1 log 2 |L(Y ) ∩ Σ k | k .
Therefore, there exists some k ≥ 1 with

log 2 |L(X)∩Σ k | k ≤ h top (X) + ε. Above we have seen L(X) = n∈N L(X n ). Especially, L(X) ∩ Σ k = n∈N (L(X n ) ∩ Σ k ). Since the sets L(X n ) ∩ Σ k are finite and L(X m ) ∩ Σ k ⊇ L(X n ) ∩ Σ k for any m, n ∈ N with m ≤ n, we conclude that there is some l ∈ N such that for all n ≥ l we have L(X n ) ∩ Σ k = L(X) ∩ Σ k . We conclude that for all n ≥ l h top (X n ) ≤ log 2 |L(X n ) ∩ Σ k | k = log 2 |L(X) ∩ Σ k | k ≤ h top (X) + ε.
This ends the proof. ✷

Proof of Theorem 22: Let α ∈ [0, 1] be a right-computable real number. By Lemma 33 there exists a sequence (z n ) n∈N of integers computable in time polynomial in n with z n ∈ {1, . . . , 2 n } such that the sequence (q n ) n∈N defined by q n := z n /2 n is non-increasing and converges to α. We define a sequence (w n ) n∈N of patterns w n ∈ {0, * } + recursively by (4zn-2zn+1) .

w 0 := * , w n+1 := w 2zn+1 n 0 |wn|•
Note that z n = 0 for all n and that the assumption that the sequence (q n ) n∈N is non-increasing implies that 4z n ≥ 2z n+1 for all n. We define a sequence (X n ) n∈N of sofic shifts by

X n := X(w n ).
By Lemma 32.1, X n is nonempty, for each n. Since w n+1 can be obtained from w 4zn n by replacing some * 's in w 4zn n by 0's, Lemma 32.4 and 32.5 tell us that X(w n+1 ) ⊆ X(w n ), for all n. We define

X := n∈N X n .
By Lemma 34.1, X is a nonempty subshift of Σ Z . We claim that it has all desired properties. "h top (X) = α": This is true by Lemma 34.3 because we have constructed X n so that h top (X n ) = q n for all n. We show this by induction. For n = 0 it is true because z 0 = 1, hence q 0 = 1, and X 0 = X(w 0 ) = X( * ) = Σ Z is the full shift, and the entropy of the full shift is equal to 1. For n + 1 we obtain by Lemma 32.3 and by the induction hypothesis

h top (X n+1 ) = # * (w n+1 ) |w n+1 | = # * (w n ) • 2z n+1 |w n | • 4z n = h top (X n ) • 2z n+1 4z n = q n • z n+1 2z n = z n 2 n • z n+1 2z n = z n+1 2 n+1 = q n+1 .
Thus, the subshift X has the desired entropy.

We still have to show that X is irreducible and that its language L(X) is decidable in polynomial time.

First, we observe that

|w 0 | = 1 and |w n+1 | = |w n | • 4 • z n ≥ |w n | • 4 for all n, hence |w n | ≥ 4 n for all n.
Secondly, we claim that for any n ∈ N and any

v ∈ Σ * with |v| ≤ |w n | v ∈ L(X(w n )) ⇐⇒ v ∈ L(X). (1)
Indeed, by Lemma 34.2 L(X) = m∈N L(X(w m )). Thus, the direction from right to left in (1) is clear.

For the direction from left to right, fix some n ∈ N and some v ∈ L(X(w n )) with |v| ≤ |w n |. By Lemma 32.6, v ∈ L(X(w n+1 )). Since |v| ≤ |w n | ≤ |w n+1 |, we can repeat this argument and obtain v ∈ L(X(w n+2 )), and so on. Thus, v ∈ L(X(w m )) for all m ≥ n. Since v ∈ L(X(w m )) for all m < n is clear anyway (due to L(X(w k )) ⊇ L(X(w k+1 )) for all k ∈ N), we obtain v ∈ L(X). This ends the proof of (1). "X is irreducible": Assume that x, z ∈ Σ * are two strings in L(X). Choose n large enough so that |w n | ≥ max{|x|, |z|}. By Lemma 34.2, we observe x, z ∈ L(X(w n )). This implies that x matches a subpattern of w n w n in the sense explained above, i.e., in the sense that it can be obtained from a subpattern of w n w n if the * 's in the subpattern are replaced appropriately by 0's or 1's. The same as for x is true for z. But then, since w n+1 contains w n w n as a subpattern, there is a string y ∈ Σ * such that xyz matches a subpattern of w n+1 w n+1 in the same sense, and, hence, by the same argument, matches a subpattern of w n+2 . By (1), this implies that xyz is an element of L(X). Hence, X is irreducible.

"L(X) is decidable in polynomial time": We claim that the following algorithm decides for an arbitrary input string v ∈ Σ * whether v belongs to L(X) or not. Furthermore, the algorithm can be implemented on a Turing machine that works in time polynomial in |v|. In the algorithm we use a Turing machine M which, given a binary name of any n ∈ N, computes in time polynomial in n the binary name of z n .

Algorithm: Assume that some v ∈ Σ * is the input. First part: For i = 0, 1, 2, . . . compute the binary name of z i (use M for this task) and the string w i until a number i has been found such that |w i | ≥ |v|. Second part: For this i, check whether v is an element of L(X(w i )) by checking whether v matches a subpattern of w i w i . (End of the description of the algorithm)

Due to |w n | ≥ 4 n , the search in the first part of the algorithm will be successful, and by (1) it is clear that this algorithm decides whether v is an element of L(X) or not. We show now that the algorithm (when implemented properly on a Turing machine) works in time polynomial in |v|.

Let i be the smallest number i with |w i | ≥ |v|. Since |w n | ≥ 4 n for all n, we obtain i = 0 for |v| ≤ 1 and i ≤ ⌈log 4 (|v|)⌉ ≤ 1 + log 4 (|v|) for |v| > 1. The computation of the numbers z 0 , . . . , z i in the first part of the algorithm can be done in time polynomial in i, hence, certainly in time polynomial in |v|. If, for some k < i, the string w k and the numbers z k , z k+1 are known, one can in time polynomial in the length of w k+1 compute the string w k+1 . Note that w 0 = * . Hence, if |v| ≤ 1, the algorithm will already stop with i = 0. Assume now that |v| > 1.

Then |w 0 | = | * | = 1 < |v|, hence i ≥ 1 and |w i-1 | < |v|, hence, |w i | = |w i-1 | • 4 • z i-1 ≤ |w i-1 | • 4 • 2 i-1 < |v| • 4 • 2 log 4 (|v|) = 4 • |v| • |v|.
This and |w k | ≤ |w i | for k ≤ i imply that the strings w 0 , . . . , w i can be computed in time polynomial in |v| (in the first part of the algorithm). Thus, the first part of the algorithm works in time polynomial in |v|. The checking in the second part can be done in detail as follow: for each position in w i w i , one checks whether v matches the subpattern of w i w i starting at this position with length |v| (of course, at the last |v| -1 positions of w i w i no subpattern of length |v| can start). For each position, this checking can be done in time linear in |v|. Since there are only 2 • |w i | positions, the second part takes only time polynomial in |v|. Thus, the whole algorithm works in time polynomial in |v|. This ends the proof of Theorem 22. ✷ Proof of Proposition 16.2, 2nd variant: For any real number α ∈ [0, 1] there exists a sequence (z n ) n∈N of numbers z n with z n ∈ {1, . . . , 2 n }, for each n, such that the sequence (z n /2 n ) n∈N is non-increasing and converges to α. By defining patterns w n and shifts X(w n ) and, finally, a shift X in exactly the same way as in the proof of Theorem 22, one obtains a nonempty, irreducible shift X with topological entropy α. ✷

Summary and Open Problems

We have answered positively the question by [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] whether there exists a shift with decidable language whose topological entropy is non-computable. In fact, the shift constructed by us is even irreducible and its language is polynomial time decidable. [START_REF] Simonsen | On the computability of the topological entropy of subshifts[END_REF] also suggested to study the class of shifts with primitive recursive language, a subclass of the shifts with decidable language. Since any polynomial time language is primitive recursive, our result shows that restriction to shifts with primitive recursive language does not help with respect to the topological entropy: there are even shifts in this smaller class whose topological entropy is non-computable.

In the second paragraph of the introduction we mentioned several positive results concerning the computability of the entropy for certain types of shift spaces. But there is still a gap between those positive results and the negative result of this paper. It remains an interesting task to narrow this gap and to identify more known classes of shifts such that the entropy is computable for the shifts in the class.

On the other hand, we have also shown that computability of the entropy of a shift does not imply any kind of computability of the language of the shift. Especially, it does not imply that the language is decidable, not even if the language happens to be computably co-enumerable. Thus, in a computability theoretic sense the language of a shift and the entropy of the shift are not closely related: decidability of the language does not imply computability of the entropy, and computability of the entropy does not imply decidability of the language.

We have not only shown that there exist shifts with (polynomial time) decidable language and noncomputable entropy. Actually, we have classified exactly the real numbers that can appear as the topological entropy of a subshift of the full shift of all binary bi-infinite sequences with co-c.e. resp. with decidable resp. with polynomial decidable language (the answer is in each case: exactly the right-computable real numbers between 0 and 1). Note that [START_REF] Hochman | A characterization of the entropies of multidimensional shifts of finite type[END_REF] showed an analogous result for multi-dimensional shifts of finite type: they showed that the real numbers that are the entropy of a multi-dimensional shift of finite type are exactly the non-negative right-computable real numbers. It would be interesting to ask the same question for other types of dynamical systems, modifying slightly two questions raised by [START_REF] Koiran | The topological entropy of iterated piecewise affine maps is uncomputable[END_REF]: which real numbers can be the entropy of a one-dimensional cellular automaton (note that [START_REF] Hurd | The topological entropy of cellular automata is uncomputable[END_REF] have shown that there is no algorithm which, given a one-dimensional cellular automaton, computes its entropy with any desired precision) or of a piecewise affine map as studied by [START_REF] Koiran | The topological entropy of iterated piecewise affine maps is uncomputable[END_REF]?

  for the set of all bi-infinite binary sequences. For p ∈ Σ Z and n ∈ Z, we write p[n] for the value of p on input n, and p[m . . . n] := p[m] . . . p[n], if m ≤ n, and p[m . . . n] := λ, if m > n. For w ∈ Σ * we set wΣ ω := {p ∈ Σ ω | w is a prefix of p} and denote by |w| the length of w.

Fig. 1 :

 1 Fig. 1: Graph for the sofic shift X(00 * 0 * * 00).

Acknowledgements

We thank one of the anonymous referee for informing us about the paper by Simonsen (2005) and the preprint by Hochman and Meyerovitch (2007).

this work the first author was partially supported by DFG (grants no. HE 2489/4-1, 446 CHV 113/240/0-1), by NSFC (grant no. 10420130638), and by JSPS (grant no. 16340028).

1365-8050


Marietjie Frick
email: frickm@unisa.ac.za

Peter Katrenič
email: peter.katrenic@upjs.sk

Progress on the Traceability Conjecture for Oriented Graphs

Keywords: longest path, oriented graph, nontraceable, k-traceable, Traceability Conjecture, Path Partition Conjecture

A digraph is k-traceable if each of its induced subdigraphs of order k is traceable. The Traceability Conjecture is that for k ≥ 2 every k-traceable oriented graph of order at least 2k -1 is traceable. The conjecture has been proved for k ≤ 5. We prove that it also holds for k = 6.

Introduction

The set of vertices and the set of arcs of a digraph D are denoted by V (D) and A(D), respectively, and the order of D is denoted n(D). A directed cycle (path, walk) in a digraph will simply be called a cycle (path, walk). A digraph is hamiltonian if it contains a cycle that visits every vertex, traceable if it contains a path that visits every vertex, walkable (or unilaterally connected) if it contains a walk that visits every vertex, and strong (or strongly connected) if it has a closed walk that visits every vertex.

The maximum number of vertices on a path in a digraph D is denoted by λ(D). A digraph D of order n is p-deficient if λ(D) = np.

A maximal strong subdigraph of a digraph D is called a strong component of D. We say that a strong component is trivial if has only one vertex.

If v is a vertex of a digraph D, we denote the sets of out-neighbours and in-neighbours of v by N + (v) and N -(v) and the cardinalities of these sets by d + (v) and d -(v), respectively. The minimum degree of D, δ(D), is defined as min v∈V (D) (d

+ (v) + d -(v)).
If D is a digraph and X ⊂ V (D), then X denotes the subdigraph induced by X in D.

A digraph of order n is k-traceable for some k ≤ n if each of its induced subdigraphs of order k is traceable. The main topic of this paper is the following conjecture, which was formulated by Morten Nielsen in 2006. It is stated in [START_REF] Frick | A Traceability conjecture for oriented graphs[END_REF].

Conjecture 1.1 (The Traceability Conjecture (TC)) For k ≥ 2, every k-traceable oriented graph of order at least 2k -1 is traceable.

The Traceability Conjecture was inspired by the Path Partition Conjecture for 1-deficient Oriented Graphs (called the OPPC(1)), which is treated in [START_REF] Frick | A Traceability conjecture for oriented graphs[END_REF] and [START_REF] Whitehead | Significant differences between path partitions in directed and undirected graphs[END_REF]. The OPPC( 1) is an important special case of the Path Partition Conjecture for Digraphs (DPPC), which is treated in [START_REF] Bang-Jensen | Longest path partitions in generalizations of tournaments[END_REF] and ( 4). The OPPC(1) may be stated as follows in terms of traceability (see [START_REF] Frick | A Traceability conjecture for oriented graphs[END_REF]).

Conjecture 1.2 (OPPC(1)) Let a and b be integers with

1 ≤ a ≤ b. If D is a 1-deficient oriented graph of order n = a + b + 1, then D is not (a + 1)-traceable or D is not (b + 1)-traceable.
The truth of the TC would obviously imply the truth of the OPPC [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. In particular, if the TC holds for k = t, it would follow that the OPPC(1) holds for a = t -1.

In the case of undirected graphs, it is an easy corollary of Dirac's degree condition for hamiltonicity that for k ≥ 2 every k-traceable graph of order at least 2k -1 is hamiltonian. The same is not true for oriented graphs, though we do have the following result, which is proved in [START_REF] Frick | A Traceability conjecture for oriented graphs[END_REF].

Theorem 1.3 For k = 2, 3 or 4, every strong k-traceable oriented graph of order greater than k is hamiltonian.

For k ≥ 5 the situation changes dramatically. As shown in [START_REF] Frick | A Traceability conjecture for oriented graphs[END_REF], for every n ≥ 5 there exists a nonhamiltonian strong oriented graph of order n that is k-traceable for every k ∈ {5, . . . , n}. However, no counterexample to the TC has yet been found. In fact, we do not even know if there exists a k-traceable oriented graph of order bigger than k + 1 that is nontraceable.

It is shown in ( 5) that the TC holds for k ≤ 5. In this paper we prove that the TC also holds for k = 6, i.e. every 6-traceable oriented graph of order at least 11 is traceable.

Auxiliary Results

First, we present some general properties of k-traceable oriented graphs. The following result concerning the minimum degree is proved in (5). Our next result concerns k-traceable oriented graphs that are nontraceable.

Lemma 2.2 Suppose D is a k-traceable oriented graph of order n > k. If D is nontraceable and v is a vertex of D with d + (v) = n -k + 1 then N + (v) is nontraceable. Similarly, if d -(v) = n -k + 1, then N -(v) is nontraceable.
Proof: Suppose N + (v) has a hamiltonian path x 1 x 2 . . . x n-k+1 . Then the graph D -{x 1 , . . . x n-k } has order k and therefore has a hamiltonian path P . If P contains the arc vx n-k+1 , then the path obtained from P by replacing the arc vx n-k+1 with the path vx 1 x 2 . . . x n-k x n-k+1 is a hamiltonian path of D. If P does not contain the arc vx n-k+1 , then v is the end-vertex of P . In this case

P x 1 x 2 . . . x n-k is a hamiltonian path of D. The proof that N -(v) is nontraceable if d -(v) = n -k + 1 is similar. ✷
The following easy observation is proved in (5).

Lemma 2.3 If D is an oriented graph of order n that is k-traceable for some k ∈ {2, . . . , n}, then D is walkable.

In view of Lemma 2.3 we shall be mainly concerned with walkable oriented graphs. The strong components of a digraph have an acyclic ordering, i.e. they may be labelled D 1 , . . . , D h such that if there is an arc from D i to D j , then i ≤ j (cf. (1), p. 17). If D is walkable then, for i = 1, . . . , h -1 there is at least one arc from D i to D i+1 , so in this case the acyclic ordering is unique. Throughout the paper we shall label the strong components of a walkable oriented graph in accordance with this unique acyclic ordering.

In the proof of our main result we shall consider oriented graphs that are strong and those that are not strong (but walkable) separately. The nonstrong case relies on the following three results concerning the strong components of k-traceable oriented graphs. The first is an obvious but useful result, proved in (5).

Proof: Suppose D has a nonhamiltonian nontrivial strong component X of order at most n-(k-4). Then |V (X)| ≥ 4 and |V (D)\V (X)| ≥ k -4. If |V (X)| = 4, then |V (D)\V (X)| = n-4 ≥ k -3. Theorem 1.3 implies that X is not 3-traceable and, if |V (X)| > 4, then X is also not 4-traceable. In either case, we can choose an induced subdigraph H of D of order k such that V (H) ∩ V (X) is nontraceable. But then it follows from Lemma 2.4 that H is nontraceable, contradicting our assumption that D is k-traceable. ✷
The following result, which is proved in [START_REF] Frick | A Traceability conjecture for oriented graphs[END_REF], is very useful in the case of k-traceable oriented graphs of large enough order.

Lemma 2.6 Suppose D is a k-traceable oriented graph of order at least 2k -1, k ≥ 2. If D is nontrace- able, then D has a nonhamiltonian nontrivial strong component.
For the proof of the strong case of our main result, we shall use the following theorem, proved in (3).

Theorem 2.7 (Chen and Manalastas) Every nontraceable strong digraph has independence number at least 3.

We shall also use the following result on k-traceable strong oriented graphs, which appears as part of the proof of Theorem 3.5 in (5). Lemma 2.8 Let D be a k-traceable strong oriented graph and let X = {x 1 , x 2 , x 3 } be an independent set of vertices in D. Let

A i = V (D) \ {X ∪ N -(x i )}, B i = V (D) \ {X ∪ N + (x i )}; i = 1, 2, 3.
Then |A i | ≤ 3k -12 and |B i | ≤ 3k -12 for i = 1, 2, 3.
Proof: Let i, j be any pair of distinct integers in {1, 2, 3}.

If |A i ∩ A j | ≥ k -3, let H be an induced subdigraph of D whose vertex set consists of x 1 , x 2 , x 3 and k -3 vertices of A i ∩ A j .
Then H has order k and is nontraceable, since both x i and x j have no in-neighbours in H. This contradiction shows that

|A i ∩ A j | ≤ k -4. Similarly, |B i ∩ B j | ≤ k -4. Now suppose |A 1 ∩ B 2 | ≥ 2k -7. Then, since |A 1 ∩ A 3 | ≤ k -4, at most k -4 vertices of A 1 ∩ B 2 are in A 3 , so at least k -3 vertices of A 1 ∩ B 2 are in B 3 , but then |B 2 ∩ B 3 | ≥ k -3. This contradiction proves that |A 1 ∩ B 2 | ≤ 2k -8. But A 1 = (A 1 ∩ A 2 ) ∪ (A 1 ∩ B 2 ). Hence |A 1 | ≤ (k -4) + 2k -8 = 3k -12. Similarly, |B 1 | ≤ 3k -12. ✷
Theorem 2.7 and Lemma 2.8 were used in [START_REF] Frick | A Traceability conjecture for oriented graphs[END_REF] to prove the following theorem. Theorem 2.9 For k ≥ 2 every k-traceable strong oriented graph of order at least 6k -20 is traceable.

We now turn our attention to k-traceable oriented graphs of small order. Knowledge of their structure is actually important when considering the traceability of k-traceable oriented graphs of large order.

Hypotraceable oriented graphs

A digraph D of order n is called hypotraceable if n ≥ 3 and D is (n -1)-traceable but not n-traceable.
Thus a hypotraceble digraph is nontraceable but the removal of any vertex leaves a traceable digraph. Our next result shows the importance of hypotraceable oriented graphs in connection with the TC. Lemma 3.1 If k > 2 and D is a nontraceable, k-traceable oriented graph of order n ≥ k + 1, then D has a hypotraceable induced subdigraph of order h for some k + 1 ≤ h ≤ n.

Proof: Suppose n = k + r. Then, for any set S consisting of r vertices of D, the oriented graph D -S is traceable. If D itself is not hypotraceable, then D has a vertex x 1 such that Dx 1 is nontraceable. We repeat this procedure until we obtain a subset {x 1 , . . . , x t } in D for some t ≤ r -1 such that D -{x 1 , . . . , x t } is hypotraceable. ✷

In view of Lemma 3.1 it is important to know the possible orders of hypotraceable oriented graphs. Grötschel, Thomassen and Wakabayashi constructed an infinite family of hypotraceable oriented graphs in [START_REF] Grötschel | Hypotraceable digraphs[END_REF]. These graphs are obtained from hypohamiltonian digraphs. The smallest hypotraceable oriented graph constructed by applying the construction in [START_REF] Grötschel | Hypotraceable digraphs[END_REF] to hypohamiltonian digraphs constructed by Thomassen in (9) has order 12. If there does not exist a hypotraceable oriented graph of order less than 12, then it would follow immediately from Theorem 2.9 and Lemma 3.1 that every 6-traceable oriented graph of order n, where 6 ≤ n ≤ 12 is traceable. However, the best that we've managed to do so far was to show that there does not exist a hypotraceable oriented graph of order less than 8. To prove this, we need the following result, which is stated in (6) without proof.

Lemma 3.2 If D is a hypotraceable digraph, then D does not have a vertex with indegree 1 or outdegree 1.

Proof: Let D be a hypotraceable digraph, x ∈ V (D) and suppose y is the only out-neighbour of x. Then every hamiltonian path of D -{y} must end in x, hence can be extended with y, which is a contradiction. ✷

A strong digraph of order at least 2 cannot have a vertex of indegree 0 or outdegree 0, so the following holds.

Corollary 3.3 If D is a strong hypotraceable digraph, then D has minimum indegree at least 2 and minimum outdegree at least 2.

We shall also use the following corollary of Lemma 2.2. Let x be the vertex in D 1 , let y be the vertex in D 3 and let 4 Oriented graphs that are 6-traceable

xv 5 v 1 v 6 v 2 v 3 v 4 is a hamiltonian path in D. Hence N + (v 1 ) = {v 2 , v 4 },
C = v 1 v 2 v 3 v 4 v 5 v 1 be a hamiltonian cycle of D 2 . If x has only one out-neighbour v i in D 2 , then D -v i cannot be traceable, so |N + (x) ∩ V (D 2 )| ≥ 2. Similarly, |N -(y) ∩ V (D 2 )| ≥ 2. Since D is nontraceable, no
In this section we prove that the TC holds for k = 6, i.e. that every 6-traceable oriented graph of order at least 11 is traceable. We first prove it for oriented graphs that are not strong.

Lemma 4.1 If D is a 6-traceable oriented graph of order n ≥ 11 that is not strong, then D is traceable.

Proof: It follows from Lemma 2.6 that D has a nontrivial strong component X that is nonhamiltonian, and from Lemma 2.5 that |V (X)| = n -1.

By symmetry we may assume that X = D 2 . Then D 1 has only one vertex x. Now D 2 is 5-traceable and of order n -1 ≥ 10. However, it is shown in (5) that the TC holds for k = 5, so D 2 is traceable. Let

v 1 v 2 . . . v n-1 be a hamiltonian path in D 2 . Let v i be a vertex in D 2 that is nonadjacent to x. If d -(v i ) ≤ n -6, then D -N -(v i ) has order at least 6. But if H is any subdigraph of D -N -(v i
) that has order 6 and contains both v i and x, then H is nontraceable, since neither x nor v i has any in-neighbour in H. This proves that every vertex in D that is not a neighbour of x has indegree at least n -5. In particular,

d -(v 1 ) ≥ n -5. Hence it follows from Lemma 2.2 that v 3 , v n-2 ∈ N -(v 1 ). Since X is strong, v n-1 has an out-neighbour v i such that 2 ≤ i ≤ n -3. If v n-1 ∈ N + (x), then xv n-1 v i . . . v n-2 v 1 . . . v i-1 is a hamiltonian path of D. This contradiction shows that v n-1 is not a neighbour of x and hence d -(v n-1 ) ≥ n -5. By Lemma 2.1, d + (x) ≥ n -5, so x has at least n -5 neighbours in the set v 2 . . . , , v n-2 . However, if 2 ≤ i ≤ n -2 and v i ∈ N + (x), then the predecessor v i-1 is not in N -(v n-1 ), otherwise D has the hamiltonian path xv i . . . v n-2 v 1 . . . v i-1 v n-1 . Thus at least n -5 vertices in D 2 are not in-neighbours of v n-1 , which implies that d -(v n-1 ) ≤ 3, contradicting that d -(v n-1 ) ≥ n -5 ≥ 6.
✷

For the proof of the strong case, we also need the following result concerning 6-traceable oriented graphs that are not strong. Lemma 4.2 If D is a 6-traceable oriented graph of order 8 that is not strong, then D is traceable.

Proof: Suppose D is nontraceable. Then, since we have shown that there does not exist a hypotraceable oriented graph of order 7, Lemma 3.1 implies that D itself is hypotraceable. We need to consider two cases.

Case 1. D has a nontrivial strong component X that is nonhamiltonian: It follows from Lemma 2.5 that X has order 7. By symmetry we may assume that D 1 has order 1 and D 2 = X. Let x be the vertex in D 1 and let v 1 . . . v 7 be a path in D 2 . It now follows exactly as in the proof of Lemma 4.1 that v 3 , v 6 ∈ N -(v 1 ) and also that v 1 and v 7 are not neighbours of x, and d -(v 1 ) ≥ 3 and d -(v 7 ) ≥ 3.

We now consider the possible neighbourhoods of x. By Lemma 2.1, d + (x) ≥ 3, and by Lemma 2.2, if

d + (x) = 3, then N + (x) is nontraceable. Moreover, if v i ∈ N + (x), then v i-1 ∈ N -(v 7 ). Suppose {v 2 , v 6 } ⊆ N + (x). Then N + (v 1 ) ⊆ {v 2 , v 4 , v 5 }. But if v 4 ∈ N + (v 1 ) then xv 2 v 3 v 1 v 4 v 5 v 6 v 7 is a hamiltonian path of D. Hence, by Lemma 3.2, v 5 ∈ N + (v 1 ). But then v 4 ∈ N -(v 1 ) and xv 2 v 3 v 4 v 1 v 5 v 6 v 7 is
a hamiltonian path of D. This proves that {v 2 , v 6 } ⊆ N + (x), so we need to consider four cases.

Case 1.

1 {v 2 , v 3 , v 5 } ⊆ N + (x): In this case v 1 , v 2 , v 4 ∈ N -(v 7 ). Hence N -(v 7 ) = {v 3 , v 5 , v 6 }. Since v 1 ∈ N + (v 7 ), this implies that N + (v 7 ) = {v 2 , v 4 }. But then xv 3 v 7 v 4 v 5 v 6 v 1 v 2 is a hamiltonian path of D. Case 1.2 {v 2 , v 4 , v 5 } ⊆ N + (x): In this case N -(v 7 ) = {v 2 , v 5 , v 6 }. But then N + (v 7 ) = {v 3 , v 4 }
(v 7 ) = {v 4 , v 5 }. Hence v 2 ∈ N + (v 7 ). Now if v 4 ∈ N -(v 1 ), then xv 5 v 6 v 7 v 2 v 3 v 4 v 1 is a hamiltonian path in D. But we have shown that d -(v 1 ) ≥ 3, hence v 5 ∈ N -(v 1 ). But then xv 6 v 7 v 2 v 3 v 4 v 5 v 1 is a hamiltonian path in D.
Case 2 Every strong component of D is hamiltonian. In this case D has at least three strong components, otherwise D would be traceable. By Lemma 3.5, every nontrivial strong component of D has order at least 5. Hence the only possibility is that N (D 1 ) = 1, N (D 2 ) = 6 and N (D 3 ) = 1.

Let x and y be the vertices in D 1 and D 3 , respectively, and let v 0 v 1 v 2 v 3 v 4 v 5 v 0 be a hamiltonian cycle of D 2 . If x has only two neighbours in D 2 , then removal of those two neighbours leaves a nontraceable subdigraph of D that has order 6. Hence x has at least 3 neighbours in D 2 and, similarly, y has at least three neighbours in D 2 . But if x is adjacent to v i and j = (i -1) mod 6, then v j cannot be adjacent to y. This implies that

|N + (x) ∩ V (D 2 )| = 3 and |N -(y) ∩ V (D 2 )| = 3 and N + (x) ∩ N -(y) = ∅. A similar argument to that used in Lemma 2.2 shows that both N + (x) ∩ V (D 2 ) and N -(y) ∩ V (D 2 ) are nontraceable. If |N + (x) ∪ N -(y)| ≤ 3,
+ (x) = {v 0 , v 1 , v 3 }, N -(y) = {v 1 , v 3 , v 4 } and N + (x) = {v 0 , v 1 , v 4 }, N -(y) = {v 1 , v 2 , v 4 }.
In the first case, since D -{v 0 , v 1 } must be traceable, D must contain the path xv 3 v 5 v 2 v 4 y. But then D -{v 3 , v 4 } cannot be traceable. In the second case, D -{v 1 , v 2 } is nontraceable, since D 2 -{v 1 , v 2 } does not have a path starting at v 0 and ending at v 4 . Thus either case contradicts the 6-traceability of D. ✷

We are now ready to prove our main theorem.

Theorem 4.3 Every 6-traceable oriented graph of order at least 11 is traceable.

Proof: Suppose, to the contrary that D is a 6-traceable oriented graph of order n that is nontraceable, for some n ≥ 11. By Lemma 4.1 we may assume that D is strong. Thus Theorem 2.9 implies that n ≤ 15. By Theorem 2.

Lemma 2 . 1

 21 If k ≥ 2 and D is a k-traceable oriented graph of order n ≥ k, then δ(D) ≥ nk + 1.

Lemma 2 . 4

 24 If P is a path in a digraph D, then the intersection of P with any strong component of D is either empty or a path. The next result follows from Theorem 1.3 and Lemma 2.4. Lemma 2.5 Let k ≥ 5 and suppose D is a k-traceable oriented graph of order n > k. Then every nonhamiltonian nontrivial strong component of D has order at least nk + 5.

2 . 2 . 2

 222 which implies that v 2 and v 4 are nonadjacent vertices. But then N + (v 4 ) = {v 5 }, which contradicts Lemma 3.Subcase Every nontrivial strong component of D is hamiltonian: In this case, if D had only two strong components, D would be traceable. Hence D has at least three strong components. By Lemma 3.5, each nontrivial strong component of D has order at least 5. Thus the only possibility is that n = 7 and D has two trivial strong components and one of order 5. The two trivial strong components cannot be consecutive, otherwise D would be traceable. Hence n(D 1 ) = 1, n(D 2 ) = 5 and n(D 3 ) = 1.

Corollary 3 . 7

 37 predecessor of a neighbour of x on C is a neighbour of y. Thus, at least one of x and y has at most two neighbours in D 2 . By symmetry, we may assume that x has only two out-neighbours in D 2 , say a and b. If ab is an arc in D, then any hamiltonian path xb . . . v j y of Da can be extended to a hamiltonian path xab . . . v j of D. Hence a and b are nonadjacent. We may assume, w.l.o.g. that a = v 2 and b = v 5 . Then v 1 , v 4 / ∈ N -(y). But then v 1 has only four possible neighbours, namely v 2 , v 3 , v 4 , v 5 . Hence, by Lemma 3.2 and Corollary 3.4, N + (v 1 ) = {v 2 , v 4 } and N -(v 1 ) = {v 3 , v 5 }. Now, if v 5 is adjacent to y, then xv 2 v 3 v 1 v 4 v 5 y is a hamiltonian path of D. Hence v 5 is not adjacent to y, so N -(y) = {v 2 , v 3 }, which contradicts Corollary 3.4. ✷ Lemmas 3.1 and 3.6 imply the following. If 2 ≤ k ≤ 7, then every k-traceable oriented graph of order n is traceable, where k ≤ n ≤ 7.

  then D has a subdigraph of order 6 that contains at most one vertex in N + (x) ∩ N -(y). But such a subdigraph cannot be traceable. Hence |N + (x) ∪ N -(y)| ≥ 4. There are two possibilities to consider: N

7 ,Corollary 4 . 4 5 . 4 . 5

 744545 D has three independent vertices x 1 , x 2 , x 3 . Let A = N + (x 1 ) and B = V (D) \ (A ∪ {x 1 , x 2 , x 3 }). Lemma 2.8 implies that |A| ≤ 6 and |B| ≤ 6. Hence, if n = 12, then |A| ≥ 3 and |B| ≥ 3. If n = 11, then it follows from Lemma 2.2 and the 6-traceability of D that |A| = 6 and |B| = 6, so in this case 3 ≤ |A| ≤ 5 and 3 ≤ |B| ≤ 5.If |B| = 3, then put S 1 = B ∪ {x 1 , x 2 , x 3 } and S 2 = {x 1 } ∪ A. If B ≥ 4, then put S 1 = B ∪ {x 1 , x 2 } and S 2 = {x 1 , x 3 } ∪ A. In either case, 6 ≤ |S 1 | ≤ 8 and 6 ≤ |S 2 | ≤ 8, S 1 ∪ S 2 = V (D)and S 1 ∩ S 2 = {x 1 }. Moreover, x 1 has no in-neighbours in S 2 and no out-neighbours in S 1 , so neither S 1 nor S 2 is strong. Hence, it follows from the 6-traceability of D and Theorem 3.6 and Lemma 4.2 that S 1 has a hamiltonian path ending in x 1 and S 2 has a hamiltonian path starting in x 1 . But then D has a hamiltonian path, contradicting our assumption.✷ The OPPC[START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] holds for a ≤Corollary The OPPC(1) holds for oriented graphs of order at most 12.

  , which contradicts Lemma 2.2, since D is hypotraceable. Case 1.3 {v 3 , v 4 , v 6 } ⊆ N + (x): In this case N -(v 7 ) = {v 1 , v 4 , v 6 }. If either v 2 or v 3 is in N + (v 7 ), then D would obviously be traceable. But then d + (v 7 ) ≤ 1, contradicting Lemma 3.2, since D is hypotraceable. Case 1.4 {v 3 , v 5 , v 6 } ⊆ N + (x): In this case N -(v 7 ) = {v 1 , v 3 , v 6 }. By Lemma 3.2, d + (v 7 ) ≥ 2. But by Corollary 3.4, N +

Acknowledgements

The collaborative research for this paper was conducted while the first author was on a research visit to the P.J. Safarik University, which was funded by the National Scholarship Programme of the Slovak Republic.

† This material is based upon work supported by the National Research Foundation of S.A. under Grant number 2053752 ‡ The research of the author is partially supported by Slovak VEGA Grant 1/3004/06 and Slovak VVGS UPJ Š Grant 11/07-08 1365-8050 c 2008

 Corollary 3.4Let D be a hypotraceable oriented graph. If D contains a vertex v, such that d + (v) = 2 (or d -(v) = 2), then the out-neighbours (or in-neighbours) of v are nonadjacent.

The following result is proved in [START_REF] Grötschel | Constructions of hypotraceable digraphs[END_REF]. It is stated in (6) (without proof) that there does not exist a hypotraceable digraph of order less than 7. We now use the lemmas above to extend this bound in the case of oriented graphs. Lemma 3.6 There does not exist a hypotraceable oriented graph of order less than 8.

Proof: Suppose D is a hypotracable oriented graph of order n, with 3 ≤ n ≤ 7.

Case 1. D is strong: In this case Theorem 2.7 implies that D has three independent vertices {x 1 , x 2 , x 3 } and it follows from Corollary 3.3 that d + (x 1 ) ≥ 2 and d -(x 1 ) ≥ 2. This is not possible if n ≤ 6, so assume n = 7.

Then we may assume w.l.o.g. that P is the path

Subcase 1.2 The initial vertex of P is a 1 : We have shown that D -{b 1 , b 2 } has no hamiltonian path, so we may assume w.l.o.g. that Db 1 has the hamiltonian path a 1 x 2 b 2 x 1 a 2 x 3 . Then b 1 ∈ N + (x 3 ), so

Case 2. D is not strong: Subcase 2.1 D has a nontrivial strong component X that is nonhamiltonian: By Lemma 3.5, |V (X)| ≥ 5, so n = 6 or 7. Since D is (n-1)-traceable, Lemma 2.5 now implies that |V (X)| = 6 and hence n = 7. By symmetry, we may assume that D 1 has order one and X = D 2 . Let x be the vertex in D 1 and let v 1 v 2 . . . v 6 be a path in D 2 . Then x, v 6 ∈ N -(v 1 ), so it follows from Lemma 3.2 and Corollary 3.4 that {v 3 , v 5 } ⊆ N -(v 1 ). Similarly, {v 2 , v 4 } ⊆ N + (v 6 ). Hence each of the vertices v 1 , v 4 and v 6 is an initial vertex of a hamiltonian path of D 2 , so x is not adjacent to v 1 , v 4 or v 6 . However, Lemma 3.2 implies that d + (x) ≥ 2 and, by Lemma 3.4, N + (x) = {v 2 , v 3 }, so v 5 ∈ N + (x). Then v 6 ∈ N + (v 1 ), otherwise