Joshua Erde

Gol Bruno

AND SYLVAIN Gol Énia
email: goleniab@compsci.bristol.ac.uk

Énia

THE CLOSED KNIGHT TOUR PROBLEM IN HIGHER DIMENSIONS

Keywords: Mathematics Subject Classification. 05C45, 00A08 . Chessboard, Hamiltonian cycle

HAL is

Introduction

On a chessboard, a knight moves by two squares in one direction and by one square in the other one (like a L). A classical challenge is the so-called knight tour. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. A knight's tour is called a closed tour if the knight ends on a square attacking the square from which it began. If the latter is not satisfied and the knight has visited each square exactly once, we call it an open tour.

Figure 1. A 6 × 6 closed tour Some early solutions were given by Euler, see [Eul] and also by De Moivre (we refer to Mark R. Keen for historical remarks, see [Kee]). The problem was recently considered for various types of chessboards: as a cylinder [START_REF] Watkins | Knight's tours on cylinders and other surfaces[END_REF], a torus [START_REF] Watkins | Knight's tours on a torus[END_REF], a sphere [Cai], the exterior of the cube [QiW], the interior of the cube [De],. . . It represents also an active field of research in computer science, e.g., [Pab] (see references therein). In this paper, we shall focus on rectangular boards.

In 1991, Schwenk considered the question of the closed knight tour problem in a 2-dimensional rectangular chessboard. He provided a necessary and sufficient condition on the size of the board in order to have a closed knight tour. He obtained:

Theorem 1.1 (Schwenk). Let 1 ≤ m ≤ n. The m × n chessboard has no closed knight tour if and only if one of the following assumption holds:

(a) m and n are both odd, (b) m ∈ {1, 2, 4}, (c) m = 3 and n ∈ {4, 6, 8}.

We refer to [Sch] (see also [Wat]) for a proof. When conditions (a),(b), and (c) are not fulfilled, he reduced the problem to studying a finite number of elementary boards. On each of them, he exhibited a closed tour and then explained how to "glue" the elementary boards together, in order to make one closed tour for the union out of the disjoint ones given by the elementary blocks. We explain the latter on an example. Say we want a closed tour for a 12 × 6 board. Write, side by side, two copies of Figure 1. Delete the connection between 21 and 22 for the left board and the connection between 28 and 29 for the right one. Then link 21 with 28 and 22 with 29. The Hamiltonian cycle goes as follows:

1[L] → 2[L] → . . . → 21[L] → 28[R] → 27[R] → . . . → 1[R] → → 36[R] → . . . → 29[R] → 22[L] → 23[L] → • • • → 36[L] → 1[L],
where [L] and [R] stand for left and right, respectively.

We turn to the question for higher dimensions. In dimension 3 or above, a knight moves by two steps along one coordinate and by one step along a different one. We refer to Section 2 for a mathematical definition. Stewart [Ste] and DeMaio [De] constructed some examples of 3-dimensional knight tours. Then, in 2011, in [DeM], DeMaio and Mathew extended Theorem 1.1 by classifying all the 3-dimensional rectangular chessboards which admit a knight tour. The strategy is the same as in Theorem 1.1. We give an alternative proof of this result in Appendix A.2.

In this paper we extend the previous results to higher dimensional boards. We rely strongly on the structure of the solutions for the case n = 3 to treat the case n ≥ 4. We proceed by induction. Before giving the main statement, we explain the key idea with Figure 1. We first extract two cross-patterns (cp). We represent them up to some rotation, see Figure 2. Note they are with disjoint support.

Figure 2. Two cross-patterns

We construct a tour for a 6 × 6 × 2 board first. We work with coordinates. The tour given in 1 is given by (a i ) i∈ [[1,36]] , with a 1 := (1, 6), a 2 := (3, 5), . . . We take two copies of the tour given in 1 and denote them by (a i , 1) i∈ [[1,36]] and (a i , 2) i∈ [[1,36]] for the first and second copy, respectively. We can construct a tour as follows:

(3, 2, 1) → (1, 2, 2) → (3, 3, 2) → . . . → (3, 1, 2) → (1, 1, 1) → . . . → (3, 2, 1).
We point out that we use coordinates in matrix way. To enhance the idea we rewrite it abusively by ("36", 1) → ("30", 2) → ("31", 2) → . . . → ("29", 2) → ("1", 1) → . . . → ("36", 1).

We explain how to treat a 6 × 6 × k board for k ≥ 3. As the proof is the same, we write the case k = 3. We use the two cp as follows:

("36", 1) → ("30", 2) → ("31", 2) → . . . → ("9", 2) → → ("19", 3) → ("20", 3) → . . . → ("18", 3) → → ("10", 2) → ("11", 2) → . . . → ("29", 2) → (1.1) → ("1", 1) → . . . → ("36", 1).

Note that we have use only one cp on the first copy and one on last one. Two of them are still free. We can therefore repeat the procedure and add inductively further dimensions. For instance, we can go from a tour for a 6 × 6 × k board to one for a 6 × 6 × k × l board, with k, l ≥ 2. One takes l copies of the tour. By noticing that there are two cp on the initial tour, we proceed as in (1.1) for the tour. Thus, we will get a tour for the 6 × 6 × k × l board, which contains in turn two cp. To prove all these facts, one can use coordinates. We refer to Section 3 for more details.

The strategy is now clear. We shall study the structure of the elementary boards, which are obtained in [DeM] and look for specific patterns into them. Then, we shall conclude by induction on the dimension. We obtain:

Theorem 1.3. Let 2 ≤ n 1 ≤ n 2 ≤ ... ≤ n k , with k ≥ 3. The n 1 × . . . × n k chessboard has no closed knight

tour if and only if one of the following assumption holds:

(a) For all i, n i is odd,

(b) n k-1 = 2, (c) n k = 3.
Note that the hypotheses are the same as the ones given in Theorem 1.2 when k = 3. In the same paper they asked about higher dimensional tours, This question was also asked by DeMaio [De] and Watkins [START_REF] Watkins | Across the board: the mathematics of chessboard problems[END_REF]. We mention that a conjecture for this theorem was given in [Kum].

The paper is organized as follows. In Section 2 we set the notation and define the graph structure induced by a knight on an n dimensional board. Then, in Section 3 we introduce the notion of crosspatterns and explain how to use them in order to gain a dimension. In Section 4.1, we start the proof of Theorem 1.3 and provide all the negative answers. After that, in Section 4.3, we finish the proof of Theorem 1.3. In Section 5 we show we can apply this technique to the problem of knight's tours with more general moves. Finally, in the appendix, we give an alternative proof of Theorem 1.2. Acknowledgments: We would like to thank Imre Leader for useful discussions and comments on the script.

Notation

Let n := (n 1 , . . . , n k ) be a multi-index where n i are with values in N \ {0}. We denote by |n| := k, the size of the multi-index n. Set also [[a, b]] := [a, b] ∩ Z. The chessboard associated to n is defined by

B n := [[1, n 1 ]] × . . . × [[1, n |n| ]].
We turn to the definition of the moves of the knight. We set:

C |n| :={(a 1 , . . . , a |n| ) ∈ Z |n| , such that |{i, a i = 0}| = |n| -2, |{i, a i ∈ {±1}}| = 1, and |{i, a i ∈ {±2}}| = 1}.
We endow B n with a graph structure, as follows. We set E n : B n ×B n → {0, 1} be a symmetric function defined as follows:

E n (a, b) := 1, if a -b := (a 1 -b 1 , . . . , a |n| -b |n| ) ∈ C |n| (2.1)
and 0 otherwise. In other words, a is linked to b by a knight move, if and only if E n (a, b) := 1. The couple G n := (B n , E n ) is the non-oriented graph corresponding to all the possible paths of a knight on the chessboard associated to n.

Set φ : B n → {-1, 1} given by φ(a 1 , . . . , a |n| ) := (-1) a1×...×a |n| , i.e., we assign the color black or white to each square. Then note that given a, b

∈ B n such that E n (a, b) = 1, one has φ(a) × φ(b) = -1. Therefore the graph G n := (B n , E n ) is bipartite.
Let {a i } i=1,...,|Bn| be some elements of B n . We say that {a i } i is a Hamiltonian cycle if the elements are two by two distinct and if E n (a i , a i+1 ) := 1 for all i ∈ {1, . . . , |B n |} and if E n (a 1 , a |Bn| ) := 1. Note that because of (2.1), B n has a closed knight tour is just rephrasing that fact that G n has a Hamiltonian cycle.

Remark 2.1. Given a multi-index n and ψ a bijection from [[1, |n|]] onto itself, we set m of size |n| given by m i := n ψ(i) for all i ∈ [[1, |n|]]. Since C |n| = C |m| is invariant under permutation, G n has a Hamiltonian cycle if and only G m has one.

Looking for patterns

In Proposition 3.7, see also Example 3.5 for 2-dimensional boards, we shall explain how to gain dimensions, for the question of closed tours, with the help of patterns.

Given an n × m board, we say that a pair of edges ((a 1 , b 1 ), (a 2 , b 2 )) and ((c

1 , d 1 ), (c 2 , d 2 )) in a tour is a site if (|a 1 -c 1 |, |b 1 -d 1 |) = (|a 2 -c 2 |, |b 2 -d 2 |) ∈ {(0, 2), (2, 0)} or if (|a 1 -c 2 |, |b 1 -d 2 |) = (|a 2 -c 1 |, |b 2 -d 1 |) ∈ {(0, 2), (2, 0)}.
Roughly speaking, both endpoints of the two edges are two squares away from each other. The three possible configurations are given in Figure 3. The first will be cross-pattern and the two others parallelpatterns.

a n+1 = a n + c and a m = a m+1 + c a m -a n+1 = a m+1 -a n ∈ {±2e i }. (3.1)
We denote this wopp by (a n , a n+1 , a m , a m+1 ).

We say that it contains the non-well-oriented parallel-pattern (nwopp) if there are c ∈ C |n| , n, m ∈ I, and i ∈ [[1, d]] so that:

a n+1 = a n + c and a m+1 = a m + c a m -a n = a m+1 -a n+1 ∈ {±2e i } (3.2)
We denote this nwocp by (a n , a n+1 , a m+1 , a m ). where δ X := 0 if X is empty and δ X := 1 otherwise. Note that: Definition 3.2. Given a Hamiltonian cycle (a i ) i∈I for G n , we say that it contains the well-oriented cross-pattern (wocp) if there are c ∈ C |n| and n, m ∈ I, so that:

c = c, e [c,1] e [c,1] + c, e [c,2] e [c,2] ∈ {±1e [c,1] + ±2e [c,2] },
a n+1 = a n + c and a m+1 = a m + c (3.3) a m -a n = c, e [c,1] e [c,1] .
We denote this wocp by (a n , a n+1 , a m , a m+1 ).

We say that it contains the non-well-oriented cross-pattern (nwocp) if there are c ∈ C |n| and n, m ∈ I, so that:

a n+1 = a n + c and a m = a m+1 + c (3.4) a m+1 -a n = c, e [c,1] e [c,1] .
We denote this nwocp by (a n , a n+1 , a m+1 , a m ). Definition 3.3. Given a Hamiltonian cycle (a i ) i∈I , we say that (a n , a n+1 , a m , a m+1 ) is a well-oriented site (or pattern) if it is a wocp or a wopp. we say that (a n , a n+1 , a m+1 , a m ) is a non-well-oriented site (or pattern) if it is a nwocp or a nwopp.

The Properties (3.1) and (3.2) are important and we present the equivalent for cross-patterns. It would be extensively used in Example 3.5 and in the Proposition 3.7.

Remark 3.4. In the case of the wocp (3.3), we have

a n+1 -a m = a m+1 -a n = c, e [c,2] e [c,2] .
In particular, if (a n , a n+1 , a m+1 , a m ) is a well-oriented site, then there is an i such that

a n+1 -a m = ±(a m+1 -a n ) ∈ {-2e i , 2e i }.
In the case of the nwocp (3.4), we get

a n+1 -a m+1 = a m -a n = c, e [c,2] e [c,2] .
This also yields that, if (a n , a n+1 , a m+1 , a m ) is a non-well-oriented site, then there is an i such that

a n+1 -a m+1 = ±(a m -a n ) ∈ {-2e i , 2e i }.
We now explain how to connect two Hamiltonian cycles and gain one dimension with the help of sites. We mention that, in the 2-dimensional case, the existence of sites will be discussed in Proposition 4.2.

Example 3.5. Take G n , with |n| = 2, such that it contains a Hamiltonian cycle (a i ) i∈I , see Theorem 1.1. Take now m := (n, 2). Note that G m contains two cycles:

(a i , 1) i∈I and (a i , 2) i∈I .
Suppose there is a well-oriented site (a n , a n+1 , a m , a m+1 ). Using Remark (3.4), we obtain immediately that E m ((a n , 1), (a m+1 , 2)) = 1 and E m ((a m , 2), (a n+1 , 1)) = 1. We can construct a Hamiltonian cycle as follows:

(a n , 1) → (a m+1 , 2) → (a m+2 , 2) → . . . → (a m , 2) → (a n+1 , 1) → . . . → (a n , 1).
Suppose now there is a non-well-oriented site (a n , a n+1 , a m+1 , a m ). Similarly, We construct a Hamiltonian cycle as follows:

(a n , 1) → (a m , 2) → (a m-1 , 2) → . . . → (a m+1 , 2) → (a n+1 , 1) → . . . → (a n , 1).
Note that we went backward on the second copy.

It is obvious that one can gain as many dimension as one has disjoint cross-patterns. However, the situation is much better: having solely two of them are enough to gain as many dimension as we want.

Definition 3.6. A tour would be called bi-sited if it contains two sites with disjoint support, i.e., such that the endpoints of the four pair of edges are two by two disjoint. Proof. As the demonstration is similar, we shall present only the case of two well-oriented sites. Set (a i ) i∈I the Hamiltonian cycle. Note that (a i , j) i∈I , for j ∈ [[1, k]], are k disjoint cycle in G m . Take two well-oriented sites (a n1 , a n1+1 , a m1 , a m1+1 ) and (a n2 , a n2+1 , a m2 , a m2+1 ). Let k be even. Using Remark 3.4, we obtain

(a n1 , 1) → (a m1+1 , 2) → (a m1+2 , 2) → . . . → (a n2 , 2) → → (a m2+1 , 3) → (a m2+2 , 3) → . . . → (a n1 , 3) → → (a m1+1 , 4) → (a m1+2 , 4) → . . . → (a n2 , 4) → . . . → (a m2+1 , k -1) → (a m2+2 , k -1) → . . . → (a n1 , k -1) → (3.5) → (a m1+1 , k) → (a m1+2 , k) → . . . → (a m1 , k) → (3.6) → (a n1+1 , k -1) → (a n1+2 , k -1) → . . . → (a m2 , k -1) → . . . (3.7) → (a n2+1 , 2) → (a n2+2 , 2) → . . . → (a m1 , 2) → (a n1+1 , 1) → (a n1+2 , 1) → . . . → (a n1 , 1).
Finally note that ((a n2 , j), (a n2+1 , j), (a m2 , j), (a m2+1 , j)) with j ∈ {1, k} are well-oriented sites for this Hamiltonian cycle in G m . When k is odd, we replace the lines (3.5), (3.6), and (3.7) by

→ (a m1+1 , k -1) → (a m1+2 , k -1) → . . . → (a n2 , k -1) → → (a m2+1 , k) → (a m2+2 , k) → . . . → (a m2 , k) → → (a n2+1 , k -1) → (a n2+2 , k -1) → . . . → (a m1 , k -1) → . . .
In this case, we get ((a n2 , 1), (a n2+1 , 1), (a m2 , 1), (a m2+1 , 1)) and ((a n1 , k), (a n1+1 , k), (a m1 , k), (a m1+1 , k)) are well-oriented sites associated to the Hamiltonian cycle in G m .

Into the proof

In this section we give the proof of Theorem 1. Proof. First, there is no closed tour on a 2 × k and on 4 × k boards. i) Case 3 × k, for k ≥ 10: Note that k is even. First one has (1, 1) which is linked to (3, 2) and to (2, 3). The possible neighbors of (1, 3) are (3, 2),(2, 1), (3, 4), (2, 5). As we have a cycle, exactly two of them are linked to (1, 3) and three of them are part of a pattern (the second one forms a cross-pattern and the two last one parallel patterns). Then, there is at least one site. Secondly we repeat the argument for the upper right corner and get a new site. Since k ≥ 10, the two sites are with disjoint supports. ii) Case k × l, for k ≥ 5, and l ≥ 6: We flip the board and consider l × k. We repeat twice the first part of the point i) for the sub-board of size 3 × k that contains the upper left corner and for the one that contains the lower left corner. We get two disjoint sites. This proposition will be very useful in Appendix A.2. Indeed, combining it with Proposition 3.7, we infer:

Corollary 4.3. If an n × m closed tour exists then so does an n × m × p 1 .... × p r closed tour for any p 1 , . . . , p r ∈ N \ {0}.

We were not able to obtain an analogue to Proposition 4.2 for 3 dimensional boards. However, for our purpose it is enough to prove the existence of specific bi-sited tours. In this section we will rely on the construction of [DeM] and in Appendix A.2, we will give a self-contained proof. Proof. Without going into details, we give a rough idea about the approach of [DeM]. Take n × m × p, that is not satisfying the hypotheses a), b) and c) of Theorem 1.2. Note that at least one of them is even (say n). Subsequently, one basically works modulus 4: An n × m × p block can be written as a union of the following ones:

2 × 4 × 4, 2 × 4 × 5, 2 × 4 × 6, 2 × 4 × 3, 2 × 5 × 5, 2 × 5 × 6, 2 × 5 × 3, 2 × 6 × 6, 2 × 6 × 3, 2 × 7 × 3, 4 × 3 × 3, 6 × 3 × 3.
The list is rather long since one has no Hamiltonian cycle for 2 × 2 × 3 and 2 × 3 × 3 boards. Then, the authors construct some Hamiltonian cycle for each elementary blocks. After that, given two compatible blocks, by deleting one edge from each block and by creating two edges that are "gluing" these blocks together, they construct a Hamiltonian cycle for the union, starting with the two disjoint ones.

First, we study the elementary blocks that are exhibited in [DeM]. For each of them, we give the list of well-oriented cross-patterns (wocp), non-well-oriented cross-patterns (nwocp) and also the edges that are used to combine two different blocks, in order to create a Hamiltonian cycle for the union. We will not exhibit parallel-patterns. For the latter, we indicate the other figure that is glued with and denote it between square brackets. We also strike out all the wocp and nwocp which are incompatible with the gluing operation of [DeM]. For instance, in Figure 6, we struck (2,3,21,20) (20, 21, 43, 42) (14, 15, 47, 48) (17, 18, 30, 31) Case of the Figure 20 : size 2 × 5 × 5 One has to be careful with the block 2 × 5 × 6 which is given in Figure 23 of [DeM]. Indeed, one sees that 1 cannot be reached from 60, therefore this is not a Hamiltonian cycle but just a path. To fix this, we propose to take:

We replace the table following the board, i.e., the table on the top of page 9. By (13, 14, 30, 31) (10, 11, 29, 28) (32, 33)[14], (44, 45) [23] ( 16, 17, 23, 22) (18, 19, 35, 34) (19, 20, 36, 35) (20, 21, 37, 36) (39, 40, 46, 45) (41, 42, 58, 57) (42, 43, 59, 58) (43, 44, 60, 59) Case of the new Figure 23 (11, 12, 28, 27) (12, 13, 29, 28) (13, 14, 30, 29) Case of the Figure 26 : size 2 × 5 × 3 4.3. Main result. We finish the proof of Theorem 1.3.

Proof of Theorem 1.3. The sufficient part was proved in Section 4.1. We deal with the necessary part by an induction on:

P k :="Given a multi-index n = (n 1 , n 2 , . . . , n k ), where 2 ≤ n 1 ≤ n 2 ≤ . . . ≤ n k and such that: (a) There is i 0 ∈ [[1, k]] such that n i0 is even, (b) n k-1 ≥ 3, (c) n k ≥ 4, then, G n contains a bi-sited Hamiltonian cycle."
for all k ≥ 3.

Basis: Theorem 4.4 yields P 3 .

Inductive step: Suppose that P k holds true for some k ≥ 3. Take n = (n 1 , n 2 , . . . , n k+1 ), where 2 ≤ n 1 ≤ n 2 ≤ . . . ≤ n k+1 , such that a), b) and c) hold true.

If all n i but one are odd, then, up to a permutation, we can always suppose that n 1 is odd. We set

n ′ = (n 2 , . . . , n k+1 ). (4.1)
Otherwise, without operating a permutation, we set (4.1).

Note that G n ′ satisfies the hypothesis a), b) and c) of P k and therefore, by P k , we get it contains a Hamiltonian cycle with at least well-oriented or two disjoint non-well-oriented cross-patterns. We apply Proposition 3.7 and get P k+1 is true.

Therefore, we have proved by induction that P k is true for all k ≥ 3. In particular, this proves the theorem.

Using Remark 4.1, we derive:

Corollary 4.5. For k ≥ 3 and n i ≥ 2. Set n := (n 1 , . . . , n k ). Suppose that some n i is even. Then, a closed tour exists on B n if and only if G n is connected.

Generalised knight's tours on a chessboard

The knight's tour is a specific case of many general questions. A natural one to ask would be, what about more general moves? For example instead of the knight being able to move (±1, ±2) or (±2, ±1) what if the knight could move (±α, ±β) or (±β, ±α)?

Given a chessboard B n and α, β ∈ N \ {0} we define as before

C α,β |n| :={(a 1 , . . . , a |n| ) ∈ Z |n| , such that |{i, a i = 0}| = |n| -2, |{i, a i ∈ {±α}}| = 1, and |{i, a i ∈ {±β}}| = 1}.
and we endow B n with a graph structure, as follows. We set E α,β n : B n × B n → {0, 1} to be the symmetric function defined as follows:

E α,β n (a, b) := 1, if a -b := (a 1 -b 1 , . . . , a |n| -b |n| ) ∈ C α,β |n| and 0 otherwise. The couple G α,β n := (B n , E α,β n
) is the graph corresponding to all the possible paths of a generalised knight on the chessboard associated to n. Note that it is bipartite. We define an (α, β)-tour on B n to be a Hamiltonian cycle on G α,β n . Knuth showed in [Knu]

that in 2 dimensions if α ≥ β then G α,β (n1,n2) is connected if and only if gcd(α + β, α -β) = 1, n 1 ≥ 2α, and n 2 ≥ α + β.
Remark 5.1. If an (α, β)-tour of B n exists then α and β must be coprime. Indeed, (1, 1, . . . , 1) is connected to (2, 1, 1 . . . , 1). Therefore, there are k, l ∈ Z such that kα + lβ = 1.

We extend the concept of sites to this setting and recall that (e j ) j∈ [[1,n]] denotes the canonical basis of R n . Definition 5.2. Given an (α, β)-tour (a i ) i∈I , we say that it contains a well-oriented α-site if there are n, m ∈ I and j

∈ [[1, n]], such that a n+1 -a m = ±(a m+1 -a n ) ∈ {-αe j , αe j }.
We denote it by (a n , a n+1 , a m , a m+1 ). Moreoever, we say that it contains a non-well-oriented α-site if there are n, m ∈ I and j ∈ [[1, n]], such that a n -a m = ±(a m+1 -a n+1 ) ∈ {-αe j , αe j }. We denote it by (a n , a n+1 , a m+1 , a m ). We define similarly β-sites.

As in Section 3 we can use α-sites and β-sites to join together two cycles. The difference is that it connects two copies which are β (α resp.) far from one another.

Example 5.3. More concretely, given an Hamiltonian (a i ) i∈I on G α,β n that contains a well-oriented αsite (a n , a n+1 , a m , a m+1 ), let m := (n, β + 1) so that

B m = (B n , 1) × (B n , 2) × . . . × (B n , β + 1). Noting that G α,β
m contains the two cycles, (a i , 1) i∈I and (a i , β + 1) i∈I , we see that

(a n , 1) → (a m+1 , β + 1) → (a m+2 , β + 1) → . . . → (a m , β + 1) → → (a n+1 , 1) → (a n+2 , 1) → . . . → (a n , 1)
is a cycle on (B n , 1) ∪ (B n , β + 1). The case for a non-well-oriented site is similar except that we reverse the orientation of the (β + 1)-th copy.

We first prove an analogue of Proposition 3.7 for (α, β)-sites.

Proposition 5.4. Suppose that G α,β n contains a Hamiltonian cycle which contains 2 α-sites and 2 βsites, which are two by two disjoint. Take now m := (n, k), with k ≥ α + β -1. Then G α,β m contains a Hamiltonian cycle which contains 2 α-sites and 2 β-sites, which are two by two disjoint.

Proof. Recall that by Remark 5.1 α and β are coprime. Set α > β. As the demonstration is similar, we shall present only the case where all 4 sites are well-oriented. Let (a i ) i∈I be the Hamiltonian cycle. Note that (a i , j) i∈I , for j

∈ [[1, k]], are k disjoint cycles in G α,β
m . We start with the two α-sites (a n1 , a n1+1 , a m1 , a m1+1 ) and (a n2 , a n2+1 , a m2 , a m2+1 ) in (a i ) i∈I . As in Proposition 3.7 and in the spirit of Example 5.3, for all i ∈ [[1, β]], we connect the i-th layer to the i + β-th layer with the help of the first α-site, then the i + 2β-th layer with the help of the second α-site . . . until we have a cycle on

T i := c∈ 0,⌊ k-i β ⌋β (B n , βc + i), for all i ∈ [[1, β]]. Note that ∪ i∈[[1,β]] T i is a partition of B m .
More concretely, for the first layer and when ⌊ k-1 β ⌋ is even, this gives:

(a n1 , 1) → (a m1+1 , β + 1) → (a m1+2 , β + 1) → . . . → (a n2 , β + 1) → → (a m2+1 , 2β + 1) → (a m2+2 , 2β + 1) → . . . → (a n1 , 2β + 1) → → (a m1+1 , 3β + 1) → (a m1+2 , 3β + 1) → . . . → (a n2 , 3β + 1) → . . .

→ (a m2+1 , (⌊ k-1 β ⌋ -1)β + 1) → (a m2+2 , (⌊ k-1 β ⌋ -1)β + 1) → . . . → (a n1 , (⌊ k-1 β ⌋ -1)β + 1) → → (a m1+1 , ⌊ k-1 β ⌋β + 1) → (a m1+2 , ⌊ k-1 β ⌋β + 1) → . . . → (a m1 , ⌊ k-1 β β⌋ + 1) → → (a n1+1 , (⌊ k-1 β ⌋ -1)β + 1) → (a n1+2 , (⌊ k-1 β ⌋ -1)β + 1) → . . . → (a m2 , (⌊ k-1 β ⌋ -1)β + 1) → . . . → (a n2+1 , β + 1) → (a n2+2 , β + 1) → . . . → (a m1 , β + 1) → (a n1+1 , 1) → (a n1+2 , 1) → . . . → (a n1 , 1)
Note that (a n2 , 1), (a n2+1 , 1), (a m2 , 1), (a m2+1 , 1) and (a n2 , ⌊ k-1 β ⌋β + 1), (a n2+1 , ⌊ k-1 β ⌋β + 1), (a m2 , ⌊ k-1 β ⌋β + 1), (a m2+1 , ⌊ k-1 β ⌋β + 1) are two "free" α-sites. When ⌊ k-1 β ⌋ is odd, we replace the latter by (a n1 , ⌊ k-1 β ⌋β + 1), (a n1+1 , ⌊ k-1 β ⌋β + 1), (a m1 , ⌊ k-1 β ⌋β + 1), (a m1+1 , ⌊ k-1 β ⌋β + 1) . We now use the two β-sites (a p1 , a p1+1 , a q1 , a q1+1 ) and (a p2 , a p2+1 , a q2 , a q2+1 ) in (a i ) i∈I to join T 1 , . . . , T β into a Hamlitonian cycle. To lighten notation we denote by [p 1 , i] (resp. [p 2 , i]) for i ∈ [[1, k]], the i-th copy of the first (resp. the second) β-site. Let d 1 := 1 and, for i ∈ [[2, β]] we set d i ∈ [[1, β]] such that d i = d i-1 + α mod β. Since α and β are coprime, we stress that d i is well-defined and that the map i → d i is a bijection onto [[1, β]].

Using

[p 1 , d 1 ] = [p 1 , 1] with [p 1 , d 1 + α],
we connect (B n , 1) to (B n , 1 + α). We have then constructed a Hamiltonian cycle for T d1 ∪T d2 . The β-sites [p 2 , d 1 ] and [p 2 , d 1 + α] will not be used anymore. Inductively, we connect

T i-1 to T i for all i ∈ [[2, β]] using [p 1 , d i-1 ] with [p 1 , d i-1 + α]. Note that it is possible since k ≥ α + β -1 and since d i = d i-1 + α, recall that α > β. We conclude by recalling that ∪ i∈[[1,β]] T i = ∪ i∈[[1,β]] T di .
We turn to the main result of this section. As in the (1, 2)-tour case, it is sufficient to construct tours in a low dimension to show the existence of tours on all, sufficiently large, chessboards in higher dimensions.

Theorem 5.5. Given α > β, n 1 , n 2 ≥ 2α + 1 and n 3 , . . . , n k ≥ α + β -1, if an (α, β)-tour on an n 1 × n 2 chessboard exists then an (α, β)-tour on an n 1 × n 2 × . . . × n k chessboard exists.

Proof. We proceed by induction on:

P k :="Given a multi-index n = (n 1 , n 2 , . . . , n k ), such that (a) G α,β (n1,n2) contains a Hamiltonian cycle, (b) n 1 , n 2 ≥ 2α + 1, (c) n i ≥ α + β -1 for all i ∈ [[3, k]],
then, G α,β n contains a Hamiltonian cycle which has at least 2 α-sites and 2 β-sites." for all k ≥ 2.

Basis: It is a straightforward generalization of Proposition 4.2 that for n 1 , n 2 ≥ 2α + 1 every (α, β)-tour on an n 1 × n 2 chessboard will contain 2 α-sites and 2 β-sites, hence P 2 holds.

Inductive step: Suppose that P k holds true for some k ≥ 2. Take n = (n 1 , n 2 , . . . , n k+1 ) such that that a), b) an c) hold true. We set

n ′ = (n 1 , n 2 . . . , n k ).
We see that n ′ satisfies the hypotheses of P k and therefore, by P k , we see that G α,β n ′ contains a Hamiltonian cycle which has at least 2 α-sites and 2 β-sites. . We apply Proposition 5.4 and get that P k+1 is true.

Therefore, we have proved by induction that P k is true for all k ≥ 2. In particular, this proves the theorem.

It is not known in general for which α, β (α, β)-tours exist on sufficiently large chessboards. In light of the conditional nature of Theorem 5.5 it seems natural to conjecture Proof. For all p ∈ N\{0}, Theorem A.1 and Proposition 3.7 ensure the existence of 3-dimensional bi-sited tours for all n × m × p when an n × m chessboard admits a knight's tour. Moreover, using Remark 2.1, this also holds true for any permutation of n, m and p. We will split the remaining tours into cases. Notice the sites in the top left corners of the top and bottom layers of each of them, that is the lines 1 -32, 29 -30, 18 -17 and 20 -21 in the 4 × 4 × 2 tour and the lines 1 -48, 45 -46, 24 -25 and 28 -29 in the 4 × 4 × 3 tour. So we can stack any number of these on top of each other to form bi-sited 4 × 4 × k tours for all k. More concretely we can form a 4 × 4 × 4 tour by removing the line 20 -21 from a copy of the 4 × 4 × 2 tour and placing it on top of another copy with the line 1 -32 removed, then add in the lines 1-20 and 32-21. In a similar fashion we can add any number of 4×4×2 and 4×4×3 tours together.

iii) Case 4 × 3 × k, for k ≥ 2: Again below we exhibit a 3 × 4 × 2 and a 3 × 4 × 3 bi-sittted tour. Recall that they are equivalent to a 4 × 3 × 2 and a 4 × 3 × 3 tour.

Note that they have sites in the top left corners of the top and bottom layers. Proceeding as in ii), we obtain bi-sited 4 × 3 × k tours for all k ≥ 2.

  Theorem 1.2 (DeMaio and Mathew). Let 2 ≤ m ≤ n ≤ p. The m × n × p chessboard has no closed knight tour if and only if one of the following assumption holds: (a) m, n, and p are all odd, (b) m = n = 2, (c) m = 2 and n = p = 3.

Figure 3 .

 3 Figure 3. Sites in dimension 2.

Figure 4 .

 4 Figure 4. A wopp and a nwopp.

  where •, • denotes the Euclidean scalar product in R |n| . We now flip c with respect to e [c,1] . More precisely, we set c := -c, e [c,1] e [c,1] + c, e [c,2] e [c,2] .

Figure 5 .

 5 Figure 5. A wocp and a nwocp.

Figure 6 .

 6 Figure 6. A bi-sited closed tour We rely on the next Proposition. Proposition 3.7. Take G n . Suppose that it contains a bi-sited Hamiltonian cycle. Take now m := (n, k), with k ≥ 2. Then G m contains a bi-sited Hamiltonian cycle.

  3 and consider boards associated to a multi-index n := (n 1 , . . . , n |n| ), where n i ≥ 2 and |n| ≥ 3. 4.1. Forbidden boards. We start with the sufficient part of Theorem 1.3. It is a straightforward generalization of the dimension 3. There are three main cases: a) n i ∈ (2N + 1), for all i. A bipartite graph cannot have a Hamiltonian cycle if its cardinality is odd. b) n := (2, 2, . . . , 2, k), with k ≥ 2. Set a 0 := (2, 2, . . . , 2) ∈ B n . Let (a i ) i≥0 , be the elements of a Hamiltonian cycle. Note that (a 0 -a i ) ∈ ({1, 2}, . . . , {1, 2}, 2Z), for all i ≥ 0. Then, (1, 1, . . . , 1) is never reached. Contradiction. c) n := (n 1 , . . . , n |n| ), with 2 ≤ n 1 ≤ . . . ≤ n |n| ≤ 3. Set a := (2, . . . , 2) ∈ B n and note that there is no b ∈ C |n| , such that a + b ∈ B n . Therefore, the graph G n := (B n , E n ) has no closed tour. Remark 4.1. Note that the two last cases correspond to disconnected boards. 4.2. Bi-sited boards in dimension 2 and 3. We start by the existence in dimension 2. Proposition 4.2. Every closed tour on an n × m board is bi-sited.

Theorem 4. 4 .

 4 Let 2 ≤ m ≤ n ≤ p. The m × n × p chessboardhas a bi-sited closed tour if and only if one of the following assumption holds:(a) m, n, or p is even, (b) n ≥ 3, (c) p ≥ 4.

Figure 7 .

 7 Figure 7. A 5 × 6 × 2 bi-sited open tour replacing Figure 23 of [DeM].

Figure 8 .

 8 Figure8. A 10 (2, 3)-tour constructed by A. H. Frost[Fro]

Figure 10 .

 10 Figure 10. An extending pattern.

Figure 11 .

 11 Figure 11. How to extend a closed seeded tour

Figure 12 .

 12 Figure 12. A 3 × 10 seeded tour.

Figure 13 .

 13 Figure 13. A 3 × 12 seeded closed tour

Figure 17 .

 17 Figure 17. A 8 × 8 seeded closed tour

Figure 18 .

 18 Figure 18. A 5 × 5 and a 5 × 7 seeded and bi-sited open tour

  .

Figure 19 .

 19 Figure 19. A 7 × 5 and a 7 × 7 seeded and bi-sited open tour

Figure 22 .

 22 Figure 22. A 4 × 3 × 2 bi-sited tour

  out, because the edge (20, 21) is already used when one glues Figure35.

	Wocp		Nwocp	Used edges [with Figure]
	(4, 5, 11, 12)	(1, 2, 22, 21)	(3, 4)[6, 11, 14, 17], (8, 9)[6]
	(7, 8, 28, 29)	(2, 3, 21, 20)	(10, 11)[6], (14, 15)[6],
		(13, 14, 18, 17)	(20, 21)[35], (25, 26)[6],
				(27, 28)[6]
	Case of the Figure 6 : size 2 × 4 × 4
	Wocp		Nwocp	Used edges [with Figure]
	(1, 2, 30, 31)	(14, 15, 35, 34)	(4, 5)[20], (8, 9)[20],
	(4, 5, 31, 32)	(16, 17, 23, 22)	(10, 11)[11], (11, 12)[23],
	(12, 13, 39, 40)			(16, 17)[11], (17, 18)[26],
	(19, 20, 24, 25)		(31, 32)[11], (37, 38)[11], (39, 40)[6]
	Case of the Figure 11 : size 2 × 4 × 5
	Wocp		Nwocp	Used edges [with Figure]
	(1, 2, 3, 4)		(14, 15, 47, 46)	(4, 5)[29], (9, 10)[32],
	(7, 8, 26, 27)		(28, 29)[14], (29, 30)[14],
	(8, 9, 25, 26)		(30, 31)[14], (36, 37)[6],
	(10, 11, 31, 32)		(39, 40)[14], (43, 44)[29],
	(11, 12, 44, 45)		(47, 48)[23]
	(13, 14, 32, 33)
	(15, 16, 34, 35)
	(18, 19, 39, 40)
	(48, 1, 37, 38)
	Case of the Figure 14 : size 2 × 4 × 6
	Wocp	Nwocp	Used edges [with Figure]
	(8, 9, 21, 22)	(2, 3, 7, 6)	(4, 5)[17], (5, 6)[17],
	(9, 10, 16, 17)	(7, 8)[17], (11, 12)[6],
	(10, 11, 15, 16)	(20, 21)[17, 26, 32, 35]
	Case of the Figure 17 : size 2 × 4 × 3
	Wocp		Nwocp	Used edges [with Figure]
	(3, 4, 38, 39)	(9, 10, 24, 23)	(20, 21)[11], (43, 44)[20],
	(5, 6, 28, 29)	(18, 19, 33, 32) (47, 48)[11], (49, 50)[20]
	(8, 9, 25, 26)	(19, 20, 50, 49)
	(12, 13, 45, 46)

Conjecture 5.6. Take α, β such that gcd(α+β, α-β) = 1. Then, there exists M such that an (α, β)-tour exists on all n 1 × n 2 chessboards, where n 1 is even and n 1 , n 2 ≥ M . Appendix A. An alternative construction of Tours in dimension 3 A.1. Around the construction of Schwenk. For the sake of completeness, we discuss the Theorem of Schwenk. At the end of the section, we give a proof for the existence of closed tours in the setting of Theorem 1.1. We refer to [Sch, Wat] for the proof of the non-existence of tours. Note that by Proposition 4.2, their structure would be used to reduce the number of cases to study in dimension 3. We start with two definitions. Proof. By Theorem 1.1, we get m, n = 1, 2 or 4. Then, there exists a seeded 4 × m extender. Now if we place a seeded 4 × m extender to the left of a seeded n × m tour, as in Figure 11. By removing the line ((6, m), (5, m -2)) and adding in the two lines ((4, m), (5, m -2)) and ((6, m), (4, m -1)) we form


Foreigner's image in ancient egyptian magicals texts.

Often cultures affirm themselves by confronting with others. During this process, ideology plays a basic role. The other's image is linked with an ideology which induce it as J. Baines stated 1 . In ancient Egypt, history is ritual or better festive, as it is an extension or a renewal of creation 2 . The numerous images of the ennemy overthrown by the King, which were studied by R.K. Ritner 3 , would mean that the foreigner express the disorder's forces of the unorganised world.

This frequent interpretation was expressed recently by J. Baines, according to whom : « Those who were not included within the normative of the cosmos -that is, those who were not ethnic Egyptians or were excludes on somme grounds -would belong with the uncreated world 4 ». But, as far as magical texts are concerned, they reveal that the egyptian conception is more complicated. In fact, as soon as the execrations texts of the Ancient Kingdom, as the Giza's texts 5 , there is no doubt that the execrations figures do concern Egyptians as well as 1

representation of the Book of the Gates in which all the ethnic groups are placed by the Egyptians on the same level, all being created by the same sun god. Also, the bound prisoner thema did represent a foreigner but also an Egyptian or a dangerous divinity 9 . There is no rejection of the foreigner in egyptian ideology and the foreigners go to the egyptian paradise, even if they need interpreters to be understood 10 , traditionnaly Egypt consider itself as an empire which borders exceed the border of the moment and extend as far as the limits of the universe. But it's a religious duty for the king to destroy or subdue what is contrary to the order wanted by the creator, and the whole humanity is liable to revolt. Therefore an execration's ritual is performed to « immobilise the humanity 11 » (rth p't). The word pat had first an aristocratic flavour, but finally applied to the whole humanity, which must be bewitched so there is no rebellion. 22/04/2012

With the Edfu's text, we possesss a good description of this ritual ; we know that some figures were put into a net to be burnt, after a simulacre of fishing has been accomplished.

In the same perspective, the traditionnal representation of the nine bows which were to be subdued by the King, concern the whole humanity, includind upper and lower Egypt. Of course we are in the level of ideological representations, which d'ont imply that the practice was such. And in fact representations of rebelling foreigners are far more frequent than Egyptians. The fact that foreingner didn't belong to uncreated world is consistent with egyptians beliefs. The world was created by the god, who also created the ethnic groups. This aspect of the egyptian thought being more apparent after the Amarna period. Once he rebells, the ennemies were assimilated to « human beasts », the descendants of which would revolt against the gods, then becoming the criminals and asocials of egyptian society [START_REF] Meeks | Dictionnaire et lexicographie[END_REF] . In this way people who would revolt against the authority of the king participate congenitaly to the nature of primordials beings who did revolt against Re. That is why during the New Kingdom, the usual expression « rebels children » (msw bstw) was assimilated with another one, the « downfall children » (msw bdst), the word bdst being the expression of 'chaos' forces 13 . Every rebel being is assimilated with the cosmic ennemy. By the execrations rituals of rebels had a precise intend : to hinder the expression of chaos in the organised world ruled by the King, and for the Egyptians, what is meant by the end of the world is precisely a return to the original chaos 14 . Rebels do express Chaos as Apopis, and in the Bremner-Rhind papyrus the officiating priest declares to Re : « Go to Pharaoh, so that you repel for him all his ennemies, as he overthrowed for you Apopis, may he destroys you the wretched one 15 ».

With the New Kingdom numerous foreign influences exerted on Egypt, and it was a real fashion to use semitic words. The magical texts followed the general trend, as for example the Leiden's papyrus published by A. Massart 16 . This ramesside papyrus show some interesting features. First, its language is New Egyptian, which is quite rare for magical texts, and second it's main concern is to cure a disease named whether akhou or samana. The word akhou (« burning substance ») being the egyptian equivalent for the mesopotamian demon samana. [START_REF] Meeks | Dictionnaire et lexicographie[END_REF] See J. Both words refer to skin diseases which, without being the sames , display some common features 17 .

During this period magicians d'ont hesitate to use formulas written in foreign languages. By invoking a god in a foreign language 18 , the magician wanted to hinder malignants forces of exotic origin. Renown for its magic, Nubia benefits of a real fame, and alluding to it increase the efficacity of formulas. The more so since, a well attested tradition during the New Kingdom, located the birth place of Amon in Nubia, this also explains the frequent use of Nubians names of the god. The magician try to seize the nature of the god under all its aspects, all its forms or names, according to the egyptian belief, the name expresses the essence of the thing. If to write a formula into a foreign language is by no way an offense, all the languages are not on the same level. For the Egyptians, only the egyptian language do really express the reality, because the creator used this language to create the realia of the universe, in the begining. The foreigners are the « others », the « ignorants » ; but the Egyptians are the « hearts », those who are aware of the will of the god. This also means that a god is really named only by egyptian language, and that the foreigns gods are just aspects of egyptians gods 19 . So language is also considered as an important criterium of distinctions between the differents ethnics groups, as Janet H. Johnson stated 20 .

In a way, such invocations of the god Amon are exceptions founded on the nubian origin of this god. We find in a limited group of texts : the magical papyrus Boulaq 6, and the supplementaries chapters of the Book of the Dead 21 , which are magicals texts. All this is linked with the expansion of Egypt into Nubia and the assimilation of the ram god Saka from Kerma with Amon at the begining of the XVIIIth dynasty which led to the cult of Amon in the temple of Gebel Barkal 22 . The egyptianised Nubia is not felt as a foreign country, and the Pharaos of the XXVth dynasty will pretend to be the best defenders of egyptians traditions. King Piankhi will forbid the access of his palace to princes who were not circumcised and ate 17 See T. Bardinet 21 These formulas were composed in a theban milieu, and used a magical amulets during the XXIth dynasty or included in little compositions. 22 See recently the study of C. Bonnet, Lr temple principal de la ville de Kerma et son quartier religieux, Errance (ed), Paris 2004, p. 158-159 and references. The Gebel Barkal became a southern Heliopolis and the original mound on which the creator created the world.See also Mark L. Troy, Patterns of Queenship in AncientEgyptians Myths and History, Uppsala 1986, p. 15-16. 22/04/2012 fish « which is an abomination for the king's palace. » Foreigns gods are generaly assimilated with Seth or to Hathor, according to their mythologicals settings. By consequence, there is a large tolerancy for foreign gods and their cults. A good example of a succesful acculturation is given by the egyptian version of the struggle between Baal-Seth and the Sea, and during the same period, the canaanite god Baal became the warlike model of egyptian kingship [START_REF] Schneider | Foreign Egypt : Egyptology and the Concept of cultural appropriation[END_REF] . The Leiden's papyrus shows how this myth could be used in a magical context 24 : « Other formula, the rage of Seth is directed against the akhu disease ! The fury of Seth is directed against you ! The rage of the tempest as it is greedy of water from the sky, is directed against you ! Then he will end the violence, having layed his arms on you. Then you will endure what the sea did endure by his hand. » This is to be compared with a passage of Medical Papyrus Hearst 25 , of the begining of the XVIIIth, before the Leiden papyrus : « Just as Seth subdued the Sea, Seth will subdue you, the Asiatic, and then you will certainly not enter the body of so born of so ». In this text, the Sea and the disease are subdued by Seth, and for the sea, the medical papyrus has « the great green », while in the Leiden's tex the neologism ym [START_REF] Posener | La légende égyptienne de la mer insatiable[END_REF] is used. In another text of the XIXth dynasty, the magician stresses the efficacity of the magical formulas which are compared with the voice of Seth on the sea 27 .

The accultured myth of the struggle between Baal and the Sea, becomes the struggle of Seth against the disease [START_REF] Leiden | Collombert and L. Coulon, « Les dieux contre la mer[END_REF] . Seth,as a god of thunderstorm, did correspond with an aspect of the god Baal, and Seth-Baal did play an important role in the royal ideology of the New Kingdom. So this acculturation of asiatics features did rely on a forehand theme in egyptian mythology.

Not only Seth was a god who was able to create or to apease a thunderstorm, but also in egyptian culture an old mythological theme decribes the « avidity » of water. In the Teaching of Merikare 29 , the creator's merits are praised : « Men, god's cattle, are well provided ; he created sky and earth for them ; he repressed water's avidity, he created air so that their noses could live. » Here the god Re assumes the function of Seth 30 . This is not to surprise us, since precisely the positive aspect of Seth as a fighter, make him able to protect the sun god in his 22/04/2012 boat and to repel Apopis who symbolise the unorganised chaos' forces. This is a very old and important mythological theme ; the Nun as primordial ocean has a double aspect, it is a place where the gods and the deads regenerate themselves, but being unorganised it is also dangerous for the organised world and the god must fight constantly against its perpetual agressions : « Cette convoitise, cette avidité, fureur résiduelle de l'Océan Primordial, est vaincue chaque matin dans la personne du serpent ; elle est maintenue à la périphérie du monde par l'action bénéfique du soleil [START_REF] Meeks | La vie quotidienne des dieux égyptiens[END_REF] . »

The question is : how far is there a borrowing ? Could the story of the fight agains the water be purely egyptian as G. Posener supposed ? The answer is complicated. According to T.

Schneider, the general trend of the New Kingdom is an opening to foreign influences 32 . But for A. Caquot, who was a good specialist of western semitic culture, there is a discrepancy between the themes of the semitic culture and was is actually attested in the egyptian culture [START_REF] Caquot | Problèmes d'histoire religieuse in : La Siria nel tardo Bronzo p. 64[END_REF] . This fact would lessen the part of borrowings, also G. Posener and A. Roccati mimize the influence of semitic culture, for them the influence is undirect and the produce of a free adaptation by the Egyptians. For A. Roccati the legend of Seth and Anat, which origin lie in the eastern Delta, is an egyptian product which was influenced by the multicultural culture of the ramesside period and the exotics themes were freely adapted by cultivated Egyptians [START_REF] Roccati | Une légende égyptienne d'Anat[END_REF] . In this framework, the borrowing of mythologicals themes is assumed during the New Kingdom, only if it does fit with a forehand theme in the egyptian culture. This point seems to be confirmed by what T.Bardinet explains about the medical texts and the relation between semitic diseases and egyptian diseases : « Il n'y a jamais de véritable correspondance entre les nosologies médicales et, surtout, les contextes magiques ne sont pas superposables 35 . » Nevertheless, it does not exclude the fact that the two diseases (akhou and samana for example), must have something in common. The borrowing does not imply adequacy, but there must be something in common. A certain « cultural adequation » is a necessary requisite which allow the borrowing. For example, a foreign god is only assumed if he corresponds to an aspect of an egyptian god, this aspect may in turn become an independent divinity. This problematic seems to differ from the Late Period's one, when the assimilation between egyptian gods and greek gods led to the creation of new gods with their specific 22/04/2012 characteristics. The degree of acculturation seems greater in the Leiden papyrus of the ramesside period than in the Medical papyrus and finally the Astarte's papyrus might reveal a still greater level of acculturation although founded on egyptian features. So in fact, we have an evolution towards a greater acculturation even if it was made possible by the forehand presence of egyptian mythologicals themes. And the more we proceed in time, the less the egyptian reference appears, this movement must be appreciated in correlation with the ramesside infatuation for semitic culture. The replacement of the term « great green », by the semitics terms like « ym » for the sea, or the semitic word for armour 36 , do testify of this cultural process which display of a real opening to foreign cultures as stated by T. Schneider, On the contrary, during the Third Intermediate Period, the situation of the foreigner in the egyptian culture seems to reveal a drastic change. The Assyrians' invasions have been considered as a turning point, which reflect itself « in the worship and execration of Seth » 37 . This invasion preluded to waves of invaders till the end of egyptian civilisation and they affected deeply the country creating a paranoiac feeling of insecurity, this was also the background which allow the development of an apocalyptic literature 38 in which the invasions were considered as the expression af a divine punishment. Here also, it seems necessary to distinguish between two levels : the official level of priestly ideology and reality. If we consider for example the persians invasions, there are in the Demotic Chronicle some features clearly hostiles to persians ; the persian ruler is qualified of « ennemy », and the term for foreigner is negatively connoted. But in the same time, an important part of the demotic magical papyrus of London an Leiden was written for the persian king Darios 39 , this interpenetration of cultures seem to be confirmed by a funerary stela discovered in Saqqara (1994), belonging to a man born from a persian father and an egyptian mother, in which an 35 T. Bardinet, « Remarques sur les maladies de peau », RdE 39, 1988, p. 13. 36 « tryn »,see also P. Collombert, L. Coulon, art. cit., BIFAO 100, 2000, p. 80-82. 37 H. Te Velde, Seth, p. 145 and note 1. The « diabolisation » of Seth increase with invasions, see also R. Meyer, « Collective Guilt and National Suffering », in J. Assmann and Guy G. Stroumsa (ed.), Transformations of the inner Self in ancient Religions, Brill 1999, p. 246. Also new kind of names appear with an imprecatory function, perhaps against foreigners, see M. Guentch-Olgoueff, « Noms propres imprécatoires », BIFAO 40, 1941, p. 133. 38 See : Apocalypticism in the Mediterranean World and the Near East, proceedings of the International Colloquium on Apocalypticism (Uppsala, August 12-17, 1979). More particularly the communications of J. Assmann, J. Bergman and also of J. Gwyn Griffiths and the « Prediction of the Lamb », p. 285 which relates catastrophics events in connection with the Assyrian conquest. 39 See G. L. Griffiths and H. Thompson, The Demotic Magical Papyrusof London ans Leiden, Oxford 1921, p. 86-87 and note of line 26 = col. XII, 26. Darius was reputed to be a magician, see Porphyr, De Abst., IV, 16. It's not impossible also that in fact the magical papyrus of London and Leyden was in fact, at least partly, a traduction from greek. 22/04/2012 egyptian scene alternate with a persian one [START_REF] Mathieson | A stela of the Persian period from Saqqara[END_REF] . This flexibility is characteristic of Persian Empire, which was far less closed to Achemenids influences as what affirms traditionnal historiography or some egyptologists : « Le problème n'est donc plus de se demander si la création et le fonctionnement de l'empire ont eu des effets sur les pays et les populations. Il est de comprendre comment les innovations impériales se sont greffées sur les traditions locales [START_REF] Briant | This is confirmed also by the excavations of Ayn-Manawir in Khargah's Oasis[END_REF] . » This new approache of the period is confirmed by recent studies, for example an important article of Janet H. Johnson shows that according to their fluidity ethnical considerations were of little importance in Persian Egypt. Some opposing arguments developped by J. Yoyotte in a communcation [START_REF] Yoyotte | L'Égypte ancienne et les origines de l'antijudaïsme[END_REF] reveal to be quite weaks. For exemple, it is not certain that Seth received the nickname of « Median » since the word could also mean the « Medja [START_REF] Kurth | Über Horus, Isis und Osiris[END_REF] », and a famous representation of Seth on a magical stela from Hanovre [START_REF]Magie et magiciens[END_REF] is not obviously directed against the great Persian king, this is only a free interpretation. The allusion might be more general as in the Demotic Chronicle, the allusion to the « great god », supposed to be Alexander the Great. Both allusions could refer to general ennemy as in the apocalyptic literature, also its origin lie in historical events, these are treated in a general way according to a conception of history, and the reprensentation of Seth could be emblematic or symbolic [START_REF]Hermèsen Haute Égypte II, BCNH[END_REF] . Even the famous execration of Seth shows its limits, since if well attested in the valley and above all in the theban area, it's not at all the case in the Oasis which are atraditionnal places of worship for the god Seth, the positive representation of Seth in the Hibis temple is famous and this positive character of the god survived in magical texts of imperial period [START_REF] Frankfurter | Religion in Roman Egypt[END_REF] . As a confirmation of this interpenetration, we may underline the discovery in the Wadi Hammammat of a magical formula against scorpions written in archaic demotic and in aramaic, which implies to masterise both writings [START_REF] Vittman | Ägypten und die Fremden, Kulturgeschichte der Antike Welt 97[END_REF] . This use of aramaic can be compared with the use of foreign languages in magical texts of the New Kingdom, and in the same way as there was a special consideration for Nubia, there may be in this period also a 22/04/2012 special consideration for aramaic writing, since G. Vittmann point out the existence in nowdays Egypt of a « Syrian language », which is not considered to be a human language, but the language of demons 48 .

But it is sure that a ritual to overthrow Seth and his confederates, known by a papyrus of the XXXth dynasty [START_REF] Urk | Urkunden Mythologischen Inhalts[END_REF] , relates how the god once expulsed by the sun god from Asia, came back to Egypt to destroy its temples and kill the sacred animals :« L'analogie avec les Perses est patente » as J. Yoyotte said. This is a good example of a text strongly connoted ideologically as the temples and their priests could produce, the text apply clearly to the second persian invasion and not to the first [START_REF]This is confirmed by the favorable attitude of the Egyptians for Alexander considered as[END_REF] . This fact is attested by others texts of same priestly origin which underline the fact that foreigners were not pures, because they did not respect egyptians taboos. leit-motiv is attested also in Herodot's description of Egypt. Also the occupation of the country by foreigns troops might contribute to develop an hostile feeling for foreigners.

All this induced a « Verschärfung der kulturellen Grenzen 51 » in the Late Period. So, even if the hostility againt the Persians is far less important than what has been said, there is a clear evolution and even a rupture since the second Persian invasion. This rupture, nevertheless is consistent with the egyptian's conception of the foreigner. As we have seen, the foreigner is an ennemy only if he acts so, but with the invasions of invaders clearly felt as non egyptians there is an open revolt against the order of the gods, and Seth became the « prototype et patron des conquérants étrangers » et « l'Asiatique, impur par excellence, se verra donc interdire l'accès des temples de façon expresse. Parce que la pureté était ressentie comme essentielle à la bonne marche du monde, l'impur aura fini par devenir synonyme de non-égyptien, ou même d'anti-égyptien. » Of course the purity of the Egyptians was ritual, this fact corresponds with what M. Weber named « magical ascesis [START_REF] Meyer | Magical Ascesis and Moral Purity in Ancient Egypt[END_REF] ». This hostility against the foreigner which may have been exasperated by the permanent presence of foreign troops in Egypt [START_REF]haben wie in unserer Zeit die Stationnierung amerikanischer Soldaten in Saudi-Arabien une im Irak bei den Muslimen…[END_REF] , did concern of course also the foreign ruler, this reactivated an old egyptian literay 22/04/2012 theme [START_REF] Assmann | Königsdogma und Heilserwartung[END_REF] : the « messianic » expectation of the arrival of an egyptian king who will reestablish order, purity and temples. The purity became an obsession against the supposed impurity of the foreigners, and another religious theme will be stirred : the skin diseases. The fact that skin diseases were often considered to be connected with foreigners and more particulary with Asiatics is traditionnal, since skin diseases are as expressing a ritual uncleanness caused by the anger of the gods or by the execration of a magician [START_REF] Bardinet | Remarques sur les maladies de la peau[END_REF] . They are mentionned in a group of magical texts of the Ramesside and Third Intermediate Period [START_REF] Edwards | HPBM 4 th series, Oracular Amuletic Decrees of the New Kingdom[END_REF] , in which by the expression « canaanite disease » the lepra is probably meant, and in fact it began to spread into Egypt coming from western semitic area. In the Graeco Roman period an Esna's text published by Sauneron reveals that the entrance of temples of the area was forbidden to those who were afflicted by it : « Ne laisse pénétrer au temple aucun homme qui soit dansd l'état d'un homme qui est sous l'influence de la colère (baou), d'un mort, ou d'un dieu, ou sous l'influence d'un sort (hemet-sa) [START_REF] Sauneron | Les Possédés[END_REF] . » But these words are determined by the pustule, and should probably refer to people sufferings of skins diseases which were considered to be the expressions of hidden influences.

In this context, Nubia did preserve a privileged status on account of the fact that this country was considered to be the birthplace of Amon as in the Brooklyn's magical papyrus which date can be situated between the saite and the ptolemaic period. In the same text, there are several mentions of a dangerous being which has a semitic name, still in use nowdays : « Khenzirah », which means the « sow » [START_REF]On this question[END_REF] . Some others magical texts establish a relation between Osiris and Pnoubs in Nubia (Doukki Gel) 59 . This difference between the semitic world and Nubia is important, altough there is a mention of the « Napata's rebels » in an execration text from Edfu, this is probably an allusion to events which were linked with the end of the XXVth dynasty and the begining of the 22/04/2012 XXVIth 60 . A magical demotic text from the roman period which relates the story of Setne, testify that in this period Nubia had still the reputation of a country of magic and magicians [START_REF]Setne II and recently the translation of[END_REF] .

Of course, execration rituals till occupied a great part of the ritual activity of the temples and while reading the rituals of this period « on en retire l'impression que les prêtres passaient une partie de leur temps à cracher sur des poupées figurant l'ennemi de leur dieu et à les fouler du pied gauche [START_REF] Posener | À propos de la pluie miraculeuse[END_REF] ». This activity is linked with a basic preoccupation of the Egyptians of this period : to protect the country against invaders, since for them there is an ontological relation between political disorder and mythological conflict ; this clearly expressed in the Jumilhac papyrus 63 : « Si on néglige toutes les cérémonies d'Osiris en leur temps dans le nome, ainsi que toutes les fêtes du calendrier civil, alors le pays sera privé de ses lois…Si on ne décapite pas l'ennemi quon a devant soi…, suivant toutes les prescriptions du rituel, les habitants du désert se révolteront contre l'Égypte… » The structure of this passage was studied by P.

Derchain who showed its relationships with apocalyptic literature and the prediction of the hermetic Asclepius.

In fact, in pertubating the rites which were performed in the temples, the invasions threatened the very existence of the world, since the gods need the rites to exist, the lack of rites in a way « kill » the gods who are unable to actualise themselves and are reduced to their virtuality [START_REF]See the analysis of D. Meeks, « la notion de 'dieu[END_REF] . This also axplain why, during the Late Period, period of invasions, the priest past a great of their time to perform execrations rituals to maintain the very survival of the country and show a compulsive need of purity to lessen their anxiety. Robert Meyer who studied these texts is right in observing that this purity was correlated with the fact that Egypt was considered as the « templum totius mundi », the temple of the whole world, expression which we meet in the hermetic texts [START_REF] Meyer | Magical Ascesis and Moral Purity in Ancient Egypt[END_REF] . Neglecting the cultuals acts mignt endanger the country, weaken the gods and favorise the invasions. For example in the Nectanebo's dream, some fragments of which were recently found in demotic script, the king declares : « As I did neglect my (cultual) work, Egypt will be neglected by the gods…The (Persians) ennemies will conquer the country [START_REF] Koenen | The Dream of Nektanebos[END_REF] . » 22/04/2012

The egyptian conception is consistent ; and if now the foreigners are considered to be ennemies, the reason of this is simple : the invaders by opposing themselves to the rule of the egyptian King, acted as rebels to the authority and introduced disorder and impurity in the country, from the point of view of the egyptians priests of course. The « story of Osarsiph », which was studied by T. Schneider [START_REF] Schneider | Ausländer in ägypten während des Mittleren Reiches und der Hyksoszeit I, Die ausländischen Kônige[END_REF] is relevant of this evolution, the core of the story refers to the Hyksos invasion, around this core some later additions and modifications were added and it is obvious that the thema of the impurity of foreigners did play an important role during the constitution of the story. So it's very naturally that, for historicals reasons, the thema of the impurity of the foreigners did apply to the Jewish community of Alexandria [START_REF] Yoyotte | L'Égypte ancienne et les origines de l'antijudaïsme[END_REF] . The introduction of the hyphothesis of a collective unconscious through « repressed traumatics memories [START_REF] Assmann | For example when he supposes the existency of repressed memories of a real pest at the end of the amarnian period. 70 That is the signs which caracterise a sacred animal[END_REF] », as does J. Assmann is useless. This impurity of the foreigners is still present in Herodote's description when he tells us that the Egyptians considered the foreigners as impures, because they sacrified and ate sacred animals « that is why, no Egyptian or Egyptian woman would kiss a Greek on his mouth, nor use a Greek's knife nor his spits nor his cauldron, nor eat the flesh of a steer free from signs 70 , if it has been cut by a greek knife 71 . » And this idea is still present in the Asclepius « O Egypt, Egypt, nothing will be left of yours cults only fables and your children later will not believe them : nothing will survive except words engraved on stones which will relate yours pious achievements. The Scythian, or the Indian, or the like, that is to say a barbarian neighbour will settle into Egypt 72 . » If this conception of the impure foreigner is broadly attested during the Late Period, with the spreading of christianim the new converted will express the opposite conception. They will strongly reject their previous beliefs and consider them as demoniacs. This new conception of egyptian culture will prevail in Christian Egypt, caracterised by its lavish demonology. As D.

Frankfurter stated : « When local cultures begin to understand themselves within a supralocal universe (such as Hellenism offered), they often find more value in gods capable of

See J. Osing, MDAIK 32, 1976, p. 153-154.

G. Posener, Annuaire du Collège de France 74, 1974, p. 401

See G. Posener, « Nouvelles listes de proscription (Ächtungstexte) datant du Moyen Empire », CdE 27, 1939, p. 39-46. Originally the rekhyts were not a class of egyptian population, but an ethnic group precisely located living in the Nile's Delta as stated by J.J. Clère, « Fragments d'une nouvelle représentation égyptienne du monde », MDAIK 16, 1958, p. 44 and note 5.

See G. Posener, Les empreintes magiques de Gizeh et les morts dangereux, MDAIK 16, 1958, p. 256.

D. Meeks, « La notion de 'dieu' », RHR CCV, 1998, p. 443-444 and notes 77-78.

See G. Posener, Annuaire du Collège de France 75, 1975, p. 409-410.


A Fraysse

Generic validity of the multifractal formalism

The multifractal formalism is a conjecture which gives the spectrum of singularities of a signal using numerically computable quantities. We prove its generic validity by showing that almost every function in a given function space is multifractal and satises the multifractal formalism.

Introduction

One motivation of multifractal analysis was the study of fully developed turbulent ows. Indeed, some experimental results obtained in wind-tunnels showed that the regularity of the velocity of a turbulent uid changes wildly from point to point. This quantity is therefore hardly computable. Hence, rather than measure the exponent at some point one rather estimates the fractal dimension of sets where it takes a given value H.

The spectrum of singularities d(H) is the function which gives the Hausdor dimension of those sets. From its denition, it is also almost impossible to obtain numerically the spectrum of singularities.

In [START_REF] Frisch | On the singularity structure of fully developed turbulence[END_REF], two physicists U. Frisch and G. Parisi proposed an algorithm in order to derive the spectrum of singularities from quantities that are eectively computable on a signal. They proposed to use the L p modulus of continuity of the velocity, used in the theory * Laboratoire d'analyse et de mathématiques appliquées, Université Paris XII, 61 Avenue du Général de Gaulle, 94010 Créteil Cedex, FRANCE. Email: fraysse@univ-paris12.fr 1 of turbulent ows since Kolmogorov, [START_REF] Kolmogoro | The local structure of turbulence in incompressible viscous uid for every large Reynold's numbers[END_REF]. This average quantity is called the scaling function, or scaling exponent and is denoted ξ f . It is dened by |f (x + l) -f (x)| p dx ∼ |l| ξ f (p) , where ∼ means that |f (x + l) -f (x)| p dx is of the order of magnitude of |l| ξ f (p) when l tends to 0 (assuming that the limit exists). Numerical estimations and further results about the scaling function and its wavelet decomposition can be found in [START_REF] Abry | Ondelettes et turbulences. Multirésolutions, algorithmes de décomposition, invariance d'échelle et signaux de pression[END_REF][START_REF] Arnéodo | The thermodynamics of fractals revisited with wavelets[END_REF].

Frisch and Parisi proposed that the spectrum of singularities of a function can be obtained as follows:

d(H) = inf p∈R (pH -ξ f (p) + d), (1)
see [START_REF] Frisch | On the singularity structure of fully developed turbulence[END_REF] for the derivation of this formula. First, we state the mathematical framework of multifractal analysis. The main notion we need to dene is the Hölder exponent. Denition 1. Let α ≥ 0; a function f : R d → R is C α (x 0 ) if for all

x ∈ R d such that |x -x 0 | ≤ 1 there exists a polynomial P of degree less than [α] and a constant C such that,

|f (x) -P (x -x 0 )| ≤ C|x -x 0 | α .
(

The Hölder exponent of f at x 0 is

h f (x 0 ) = sup{α : f ∈ C α (x 0 )}.
It is proved in [START_REF] Jaard | Multifractal formalism for functions[END_REF] that for p ≥ 1, the scaling function ξ f (p) is closely related with Sobolev or Besov smoothness. It is thus natural for us to replace the scaling function as follows.

If p > 0 η f (p) = sup{s : f ∈ B s/p,∞ p }.

(

So (1) applied to η f can at most give the increasing part of the spectrum. Dening, as in [START_REF]On the Frisch-Parisi conjecture[END_REF], an auxiliary function s(1/p) = η(p)/p, the Besov domain of a function f is the set of (q, t) such that f ∈ B t,1/q 1/q . The boundary of the Besov domain of f is then given by the graph of s. And by Sobolev embeddings, the Besov domain of a function is a convex set. Thus, functions η satisfying (3) are increasing and concave functions. Furthermore the auxiliary function s is such that 0 ≤ s (q) ≤ d. Those conditions lead us to the following denition. Denition 2. A function η is admissible if s(q) = qη(1/q) is concave and satises 0 ≤ s (q) ≤ d. It is strongly admissible if furthermore s(0) > 0.

The following important result from [START_REF]On the Frisch-Parisi conjecture[END_REF] allows us to dene a metric space using admissible functions. Proposition 1. Any concave function s satisfying 0 ≤ s (q) ≤ d denes the Besov domain of a distribution f . Thanks to Proposition 1, to each admissible function η, a metric space V can be associated by taking

V = ε>0,0<p<∞ B (η(p)-ε)/p,p p,loc .
To be as complete as possible, we also recall the denition of Legendre transform. Denition 3. Let f be a lower semi-continuous function dened in a normed vector space E. Then the Legendre transform of f is

f * (x) = sup y∈E (f (y) -xy). ( 4
)
This function is convex and lower semi-continuous.

In the present paper, we propose to study the validity of (1) for η f (p). An equivalent form of this heuristic formula is satised by a large class of invariant measures, see [START_REF] Barral | Multifractal products of cylindrical pulses[END_REF][START_REF] Brown | On the multifractal analysis of measures[END_REF][START_REF] Olsen | A multifractal formalism[END_REF]. In the context of signal analysis, this conjecture is often satised if we add particular assumptions on f , such as self-similarity. On the other hand, there exist counterexamples to the general validity of this formula. If it does not hold for every function, what is its range of validity? Our purpose here is to show that the validity of formula (1) is not an exceptional phenomenon but it is satised for a large class of functions, without any additional assumption. More precisely, we study the validity of this formula for "almost every" functions, i.e. in a measure-theoretic sense.

In a nite dimensional space, the notion of "almost every" means "for the Lebesgue measure". The particular role played by this measure is justied by the fact that this is the only one which is σ-nite and invariant under translation. In a metric innite dimensional space no measure enjoys this properties. The following denition, see [START_REF] Benyamini | Geometric nonlinear functional analysis[END_REF][START_REF] Christensen | On sets of Haar measure zero in Abelian Polish groups[END_REF][START_REF] Hunt | Prevalence: A translation invariant "almost every" on innite dimensional spaces[END_REF] can thus replace the notion of vanishing Haar measure. Denition 4. Let V be a complete metric vector space. A Borel set B in V is called Haar null if there exists a probability measure µ with compact support such that

µ(B + v) = 0 ∀v ∈ V. ( 5
)
In this case the measure µ is said transverse to B.

A subset of V is called Haar null if it is contained in a Borel Haar null set.

The complement of a Haar null set is called a prevalent set.

With a slight abuse of language we will say that a property is satised almost everywhere when it holds on a prevalent set.

Let us recall some properties of Haar null sets, see [START_REF] Christensen | On sets of Haar measure zero in Abelian Polish groups[END_REF][START_REF] Hunt | Prevalence: A translation invariant "almost every" on innite dimensional spaces[END_REF].

Proposition 2. Several kinds of measures can be used as transverse measures of a Borel set. Here, we will only use the following notion. Denition 5. A nite dimensional space P is called a probe for the set T ⊂ V if the Lebesgue measure on P is transverse to the complement of T .

Those measures are not compactly supported probability measures. However one immediately checks that Denition 5 is equivalent to the same one stated with the Lebesgue measure dened on the unit ball of P . Note that in this case, the support of the measure is included in the unit ball of a nite dimensional subspace. The compactness assumption is therefore fullled.

The study of generic regularity for a "large" set of functions goes back to S. Banach [START_REF] Banach | Über die Baire'sche Kategorie gewisser Funktionenmengen[END_REF], who gave dierentiability properties of continuous functions, for quasi-all functions in the Baire's categories sense. Later B. Hunt [START_REF] Hunt | The prevalence of continuous nowhere dierentiable function[END_REF] proved the same result in the measure-theoretic sense of prevalence.

In [START_REF]On the Frisch-Parisi conjecture[END_REF], S. Jaard studied properties of generic functions, in the Baire's categories sense, in Sobolev spaces. He also proved that in the sense of Baire's categories quasi-all functions in V satisfy:

d(H) = inf p≥p c (pH -η(p) + d) (6)
where p c is the only critical point such that η(p) = d.

In this paper we will study the validity of the Frisch-Parisi conjecture for almost every function in the prevalence setting. The aim of this paper is to prove the following theorem.

Theorem 1. Let η be a strongly admissible function and let V be the space dened by

V = ε>0,0<p<∞ B (η(p)-ε)/p,p p,loc ; (7)
then, in the sense of prevalence, almost every function f in V satises the following two conditions:

1. For all p > 0,

η f (p) = η(p)
2. The spectrum of singularities is dened on the interval s(0),

d p c
where it is given by:

d f (H) = inf p≥p c (pH -η f (p) + d) (8)
where p c is the only critical point such that η(p c ) = d.

Remark. We have to impose that η is strongly admissible else, according to [START_REF] Fraysse | How smooth is almost every function in a Sobolev space?[END_REF], almost every function in V is nowhere locally bounded.

In section 2 we will solve a simpler problem. We will prove that almost every function in a given intersection of a Sobolev or a Besov space and an Hölder space satises a slight modication of the Frisch and Parisi conjecture. We will rst establish their spectrum of singularities.

Theorem 2. If γ > 0 and s -d p < 0 the spectrum of singularities of almost every function in B s,q p C γ or in L p,s C γ is given by:

d(H) = d+(γ-s)p γ H if H ∈ γ, dγ d+(γ-s)p -∞ otherwise.
Remarks. 1. Using the Sobolev embeddings B s,1 p → L p,s → B s,∞ p , the same result holds in Sobolev and in Besov spaces. As Besov spaces have a very simple wavelet expansion, we will only prove the result in those spaces. To obtain the Sobolev case, we only need to pick q = ∞ in the following.

2. In Theorem 2 we only state the spectrum of singularities of functions in the case B s,q p ∩C γ where s-d p < 0. Other cases are proved in [START_REF]How smooth is almost every function in a Sobolev space?[END_REF]. To be complete, we recall the following result from [START_REF]How smooth is almost every function in a Sobolev space?[END_REF].

Proposition 3. • If s -d/p ≤ 0, then almost every function in L p,s or in B s,q
p is nowhere locally bounded, and therefore its spectrum of singularities is not dened.

• If s -d/p > 0, then the Hölder exponent of almost every function f of L p,s , or of B s,q p takes values in [s -d/p, s] and ∀H ∈ [s -d/p, s] , d f (H) = Hp -sp + d; (9)
furthermore, for almost every x, h f (x) = s.

Our purpose here is to expand the result of [START_REF]How smooth is almost every function in a Sobolev space?[END_REF] in two directions.

On one hand, we will work with an intersection of Besov spaces.

On the other hand, we will see in the last part another stronger generic result, in the topological sense mentioned above.

The main tool that we will use in the following is the wavelet expansion of functions. First, it yields a simple characterization of functional spaces and it oer a simple condition for pointwise regularity. Let us recall some properties of wavelet expansion.

There exist 2 d -1 oscillating functions (ψ (i) ) i∈{1,...,2 d -1} in the Schwartz class such that the functions

2 dj ψ (i) (2 j x -k), j ∈ Z, k ∈ Z d form an orthonormal basis of L 2 (R d ), see [19]. Wavelets are indexed by dyadic cubes λ = [ k 2 j ; k+1 2 j [ d . Thus, any function f ∈ L 2 can be written: f (x) = c (i) j,k ψ (i) (2 j x -k)
where

c (i) j,k = 2 dj f (x)ψ (i) (2 j x -k)dx.
(Note that we use an L ∞ normalization instead of an L 2 one, which simplies the formulas). If p > 1 and s > 0, Sobolev space have thus the following characterization, see [START_REF] Meyer | Ondelettes et opérateurs[END_REF]:

f ∈ L p,s ⇔ λ∈Λ |c λ | 2 (1 + 4 js )χ λ (x) 1/2 ∈ L p (R d ), (10)
where χ λ (x) denotes the characteristic function of the cube λ and Λ is the set of all dyadics cubes. Homogeneous Besov spaces, which will also be considered, are characterized (for p, q > 0 and s ∈ R) by

f ∈ B s,q p ⇐⇒ j   λ∈Λ j |c λ | p 2 (sp-d)j   q/p ≤ C ( 11
)
where Λ j denotes the set of dyadics cubes at scale j, see [START_REF] Meyer | Ondelettes et opérateurs[END_REF]. Note that, if p ∈]0, 1[, Besov spaces are not Banach spaces since they are not locally convex but nonetheless are separable complete metric vector spaces.

Pointwise regularity can also be expressed in terms of a condition on wavelet coecients, see [START_REF] Jaard | Multifractal formalism for functions[END_REF]. Proposition 4. Let x be in R d . If f is in C α (x) then there exists c > 0 such that for all λ:

|c λ | ≤ c2 -αj (1 + |2 j x -k|) α . ( 12
)
2 Multifractal formalism in a given Besov space

The Frisch-Parisi conjecture gives the spectrum of singularities as the Legendre transform of the scaling function. We will determine the validity of this formula for measure theoretic generic functions in a given Besov space, in two steps. First we will prove Theorem 2, which one gives the spectrum of singularities of almost every function. Afterwards, we will give the prevalent scaling function. This allows us to merge the spectrum obtained with formula (1) applied to the scaling function.

Proof of Theorem 2

Proposition 3 states that if s -d p < 0, almost every function in B s,q p is nowhere locally bounded and the spectrum of singularities is not dened for any H. To dene this spectrum, we need to assume a minimum uniform regularity. That is why, in the following, we choose s -d p < 0 and 0 < γ < s and we study almost every function in B s,q p ∩ C γ .

Theorem 2.1 from [START_REF] Jaard | Wavelet methods for pointwise regularity and local oscillations of functions[END_REF], yields an upper bound of the spectrum of singularities.

Lemma 1. Let s -d p < 0. For all functions f ∈ B s,q p C γ , the Haus-

dor dimension of the set {x : f / ∈ C α (x)} is bounded by d+(γ-s)p γ α.
We need also the following denition.

Denition 6. Let α ∈ [1, d d+(γ-s)p ]. A point x 0 belongs to J α if there exists an innite sequence (j, k) ∈ N × {0, ..., 2 j -1} d , k = (k 1 , ..., k d )
such that for each i = 1, ..., d k i can be written l i 2 j-L and:

1 2 j + x 0 - k 2 j < 1 2 αL ( 13
)
where L := (d+(γ-s)p)j d . We dene the exponent of approximation of x as α (x) = sup{α : x ∈ J α }.

In [START_REF]Old friends revisited: The multifractal nature of some classical functions[END_REF], it is proved that the Hausdor dimension of J α is d α .

Let α ∈ 1, d d+(γ-s)p , ε > 0 and n ∈ N such that N = 2 dn > d εα +1 be xed. We denote H(α) = dγ α(d+(γ-s)p) and β(α) = H(α) + ε. Each dyadic cube of size 2 -dj can be split into 2 dn subcubes i(λ) with side 2 -(j+n) . We dene the probe P spanned by N functions g r with the following wavelet coecients d r λ :

d r λ = j -2/q 2 -γj if each k i is a multiple of 2 j-L and r = i(λ) 0 elsewhere ( 14
)
where for each j we denote L = (d+(γ-s)p)j d .

One can check that these functions g r belong to B s,q p ∩C γ , see [START_REF]On the Frisch-Parisi conjecture[END_REF].

Let J α (i, l) = l 2 i + -1 2 αL 1 2 αL d .
Let us rst check that the set of points S c (α) dened by

S c (α) = {f = c λ ψ λ ∈ B s,q p ∩C γ : ∃x ∈ J α ∀j, k |c λ | ≤ c2 -β(α)j (1+|2 j x-k|) β(α) }.
is a Haar null Borel set. Indeed this set can be included in the lim sup on i of the countable union over l of sets:

S c (α) i,l = {f = c λ ψ λ ∈ B s,q p ∩C γ : ∃x ∈ J α (i, l) ∀j, k |c λ | ≤ c2 -β(α)j (1+|2 j x-k|) β(α) }.
which are closed sets.

We pick a sequence of functions f n in S c (α) i,l and such that f n converges to f in B s,q p ∩ C γ . For each n, there exists x n in J α (i, l) such that f n satises condition (12) at x n . But J α (i, l) is a compact set, so there exists x ∈ J α (i, l) and a subsequence (x n(i) ) i∈N such that x n(i) converges to x. As the mapping which gives wavelet coecients of a function is continuous, f satises also [START_REF] Hunt | The prevalence of continuous nowhere dierentiable function[END_REF]

at x. Let f ∈ B s,q p ∩ C γ be xed. Consider the ane subset M = {δ ∈ R N ; f + δ i g i ∈ S c (α)}.
Let δ 1 and δ 2 be in M . There exists x 1 ∈ J α and x 2 ∈ J α such that for l = 1, 2:

|c λ + δ i l d i λ | ≤ c2 -β(α)j (1 + |2 j x -k|) β(α) ≤ c2 -αβ(α)L . ( 15
)
Furthermore H(α) > γ and, if λ is such that each k is a multiple of 2 j-L .

|d i λ | > 1 j 2/q 2 -H(α)L . ( 16
)
So, taking [START_REF]Old friends revisited: The multifractal nature of some classical functions[END_REF] and ( 16) we obtain:

δ 1 -δ 2 R N ≤ 2c2 -αβ(α)L 2 H(α)L j 2/q = 2cj 2/q 2 -αεL .
When j tends to innity, the Lebesgue measure of S c (α) tends to zero. Now, we take the countable union over c and ε n → 0. As Haar null set are stable under inclusion, we obtain:

∀α ∈ [1, d d + (γ -s)p ] a.e. in B s,q p ∩ C γ ∀x ∈ J α h f (x) ≤ H(α). Let (α n ) be a dense sequence in [1, d d+(γ-s)p ].
As a countable union of Haar null sets is still a Haar null set, for almost every function in

B s,q p ∩ C γ , h f (x) ≤ H(α n ) ∀n ∀x ∈ J αn . ( 17
)
Let f be a function satisfying [START_REF] Jaard | Wavelet methods for pointwise regularity and local oscillations of functions[END_REF]. Let α be xed, there exists a nondecreasing subsequence (α ϕn ) which converges to α and the intersection of the subsets J α ϕn (:= Jα ) contains J α . Furthermore there exist a measure such that any set of dimension less than d/α is of measure zero. And the measure of J α is positive. If G H = {x : h f (x) ≤ H}, with Lemma 1 we have that the Hausdor dimension of G H is d+(γ-s)p γ H. And the d α Hausdor measure of the set {x : h f (x) < H} equals zero. This way for almost every function in B s,q p ∩ C γ ,

d(H) = d + (γ -s)p γ H for H ∈ γ, dγ d + (γ -s)p

The scaling function

Let us now determine the scaling function of almost every function in a given Besov space. We will now show the following result. Proposition 5. Let s 0 and p 0 be xed such that s 0 -d p 0 > 0. Outside a Haar null set in B s 0 ,∞ p 0 , we have:

η f (p) = ps 0 p ≤ p 0 d + p(s 0 -d p 0 ) p ≥ p 0 . ( 18
)
Let 0 < γ < s be xed. If s 0 -d p 0 < 0, then outside a countable union of compact set in B s 0 ,p 0 p 0 C γ :

η f (p) = ps 0 p ≤ p 0 γp + p 0 (s 0 -γ) p ≥ p 0 . ( 19
)
Proof : In each case, we can nd in [START_REF] Stein | Singular integrals and dierentiability properties of functions[END_REF] the lower bound. Indeed, this bound is given by the Sobolev embedding.

To prove the upper bound, we will rst consider the case s 0 -d p 0 > 0. Let ε > 0 be xed and denote

s(p) = ps 0 + ε p ≤ p 0 d + p(s 0 -d p 0 ) + ε p ≥ p 0 .
. Let 0 < p < ∞ be xed. We want to show that the set of functions belonging to B s(p),∞ p for all 0 < p < ∞ is Haar null. This set is clearly closed and Borel. Let j ≥ 1 and k ∈ {0, ..., 2 j -1} d . We dene J ≤ j and

K ∈ Z d such that K 2 J = k 2 j
is an irreducible fraction. Let a > 3 p 0 . We dene a probe spanned by the function F with the following wavelet coecients:

d λ = j -a 2 ( d p 0 -s 0 )j 2 -d p 0 J .
This function belongs to B s 0 ,p 0 p 0 . Let f be in B s 0 ,p 0 p 0 and consider the ane subset

M = {α ∈ R; f + αF ∈ B s(p),∞ p }.
Suppose that there exist α 1 and α 2 in M . We have then three cases, following position of p.

• If p = p 0 , then s(p) = p 0 + ε and f + α 1 F -(f + α 2 F ) B s(p),∞ p = sup j k∈{0,...,2 j -1} d | α 1 -α 2 j a 2 (s-d p 0
)j 2

( d p 0 -s 0 )j 2 -d p 0 J | p 0 = sup j | α 1 -α 2 j a |2 p 0 εj j J=0 K∈{0,...,2 J -1} d 2 -dJ = sup j |α 1 -α 2 | j a 2 p 0 εj .
But if α 1 and α 2 belong to M , this implies that

f + α 1 F -(f + α 2 F ) belong to B s(p),∞ p . This is possible only if α 1 = α 2 . • If p > p 0 , then s(p) = d + p(s 0 -d p 0 ) + ε. In this case, f + α 1 F -(f + α 2 F ) ∈ B s(p),∞
p implies that there exist c > 0 such that:

f +α 1 F -(f +α 2 F ) B s(p),∞ p ≤ f +α 1 F B s(p),∞ p + f +α 2 F B s(p),∞ p ≤ c.
We have then the following inequalities:

∀j > 0 k∈{0,...,2 j -1} d | α 1 -α 2 j a 2 (s-d p )j 2 ( d p 0 -s 0 )j 2 -d p 0 J | p ≤ c ∀j > 0 | α 1 -α 2 j a | p 2 (s-d p )pj 2 ( d p 0 -s 0 )pj j J=0 K∈{0,...,2 J -1} d 2 -dp p 0 J ≤ c
By denition of J. And

∀j > 0 α 1 -α 2 j a p j J=0 2 (d-dp p 0 )J ≤ c2 (-s+ d p -d p 0 +s 0 )pj ∀j > 0 α 1 -α 2 j a ≤ c2 (-s+ d p -d p 0 +s 0 )j 1 1 -2 j(d-d p p 0 ) 1 p ( 20
)
As p > p 0 , 1 -2

j(d-d p p 0
) is equivalent to 1 for large j and (2.2)

implies |α 1 -α 2 | ≤ cj a 2 -εj
which tends to zero when j tends to innity.

• If p < p 0 , then s(p) = s 0 + ε and 1 -2 j(d-d p p 0
) is equivalent to

2 j(d-d p p 0
) when j tends to innity. Thus in (2.2), we obtain again

|α 1 -α 2 | ≤ cj a 2 -εj .
In each case we have obtained that M is of Lebesgue measure zero. Taking countable union over ε → 0, and over p, we obtain the desired scaling exponent.

The second case, for s 0 -d p 0 < 0 can be treated the same way for p ≤ p 0 . The case p > p 0 is obtained taking the function which coecients are given by ( 14) instead of F .

2

From Theorem 2 and Proposition 5, we obtain the following Legendre transform of the scaling function of almost every function in a given Besov space. Proposition 6. Let s 0 > 0 and 0 ≤ p 0 < ∞.

• If s 0 -d p 0 > 0, then for almost every function in B s,q p :

∀H ∈ s 0 - d p 0 , s 0 inf p>0 (d -η(p) + Hp) = d -p 0 s 0 + Hp 0 .
(21) • If s 0 -d p 0 < 0, then for almost every function in B s,q p C γ we have:

∀H ∈ [γ, s 0 ] inf p>0 (d -η(p) + Hp) = d -p 0 s 0 + Hp 0 . ( 22
)
This proposition shows that for s 0 -d p 0 > 0, the increasing part of the spectrum given by Frisch-Parisi conjecture is valid for almost every function. But for s 0 -d p 0 < 0, this Legendre transform does not correspond to the spectrum of singularities given by Theorem 2.

3 The Frisch-Parisi conjecture

We will now prove Theorem 1. Instead of B s 0 ,q 0 p 0 we will now work with:

V = ε>0,0<p<∞ B (η(p)-ε)/p,p p,loc .
This set V can also be written as a countable intersection over

B (η(p n )-ε n )/p n ,p n p n ,loc
Note that V is a topological vector space. For p < 1 Besov spaces are only quasi-Banach spaces, as the triangle inequality is only satised up to a constant, V is not a Banach space but a complete metric space. Indeed, if p ≥ 1 we take for distance between two functions f and g in B s,q p :

d(f, g) = j≥0   k∈{0,...,2 j -1} d (c j,k -d j,k )2 (s-d p )j p   q p
where c j,k are the wavelet coecients of f and d j,k are those of g. If p < 1 Besov spaces are not Banach spaces, but complete metric space with the following distance:

d(f, g) =    j≥0   k∈{0,...,2 j -1} d |(c j,k -d j,k )2 (s-d p )j | p   q p    min(p,q) q .
Thus, we obtain a distance in V taking:

∀f, g ∈ V d(f, g) = n 2 -n d n (f, g) 1 + d n (f, g)
where

d n denotes the distance in B (η(p n )-ε n )/p n ,p n p n ,loc
. With this distance V is clearly a complete space. Note that the measure used is the Lebesgue measure in the unit ball of a probe, so this is a probability measure with compact support.

In the following subsection we prove that the spectrum of singularities of almost every function in V satises:

d(H) = inf p≥pc (pH -η(p) + d).

Proof of Theorem 1

Let us now study the spectrum of singularities on a prevalent set of functions in V . Proposition 7. For almost every function f ∈ V , the spectrum of singularities satises:

∀H ∈ [s(0), d p c ] d(H) = inf p≥pc (Hp -η(p) + d). ( 23
)
Proof :

We will rst construct the probe. Denote:

a(j, k) = inf p d(j -J) -η(p)j p
and dene g via its wavelet coecients:

d λ = 1 j a 2 a(j,k) (24)
where we denote a = a j = log j and J ≤ j is such that there exists K ∈ Z d and k 2 j = K 2 J is an irreducible form. First, we check that g belongs to V . Let p > 0 be xed. Thus we have to show that g ∈ B

η(p)/p,∞ p . Let s = η(p) p . Since a(j, k) ≤ d(j-J) p -sj, pa(j, k) + (η(p) -p)j = -Jd and g ∈ B η(p)/p,∞ p
. For further details upon this function g, we refer to [START_REF]On the Frisch-Parisi conjecture[END_REF]. Denition 7. Let α be xed. We denote

F α = x : ∃ a sequence ((k n , j n )) n∈N x - k n 2 j n ≤ 1 2 αj n . ( 25
)
The dyadic exponent of x is dened by α(x 0 ) = sup{α : x 0 is αapproximable by dyadics}

As it is stated in [START_REF]On the Frisch-Parisi conjecture[END_REF], the Hausdor dimension of the set F α is at least d α .

First, let α ∈ (1, ∞) be xed and let F α be the set given by Denition 7. Let ε > 0 be xed, and let

H(α) = 1 α sup ω≥α ω sup q>0 (s(q) -d(1 - 1 ω )q)
and γ = γ(α) = H(α) + ε.

Let n ∈ N be such that N = 2 dn > d ε + 1 be xed. The probe P is spanned by N functions g i which are deduced from g by taking its wavelets coecients only over some sub-cubes i(λ) with size 2 -d (j+n) . The aim of this part is to prove that the set of functions f such that there exist a point in F α where f is C γ is a Haar null set. This set is included in the countable union of:

S c (α) = {f = c λ ψ λ : ∃x ∈ F α ∀j, k |c λ | ≤ c2 -γ(α)j (1+|2 j x-k|) γ(α) }.
We can nd a subsequence (j, k) such that J ≤ αj and:

H(α) = 1 α sup ω≥α ω sup q>0 (s(q) -d(1 - 1 ω )q) ≥ -a(j, k).
If x ∈ F α is xed and λ is such that |x -λ| ≤ A for A > 2N , the wavelet coecients of g i satisfy:

|d i λ | ≥ c(A) j a 2 -H(α)j . ( 26
)
We will now prove that the set S c (α) is a Borel Haar null set. First, this set is included in the countable union over λ of:

S c (α) j,k = {f = c λ ψ λ : ∃x ∈ F j,k α ∀j, k |c λ | ≤ c2 -γ(α)j (1+|2 j x-k|) γ(α) }.
Where F j,k α = {x : x -k 2 j ≤ 1 2 αj }. This set S c (α) j,k is a closed set and S c (α) is a Borel set. Let f be in V and β 1 and β 2 be such that the functions f + β i 1 g i and f + β i 2 g i are in S c (α). There exist two points x 1 and x 2 in F α such that in the cone of inuence above x 1 and x 2 :

|c λ + β i 1 d i λ -(c λ + β i 2 d i λ )| ≤ 2c2 -γ(α)j . Or, |c λ + β i 1 d i λ -(c λ + β i 2 d i λ )| = | β i 1 d i λ -β i 2 d i λ | but, using (26), | β i 1 d i λ -β i 2 d i λ | ≥ | β i 1 -β i 2 | c(A) j a 2 -H(α)j .
Thus,

β 1 -β 2 R N ≤ cj a 2 -εj .
So the Lebesgue measure in R N of the set {β :

f + βg ∈ S c (α) j,k } is bounded by (cj a ) N 2 -N εj .
The Lebesgue measure of the set of β such that f + β i g i belongs to S c (α) vanishes. Therefore S c (α) is Haar null. Taking a countable union over c n > 0 of sets S c (α),the set of functions in V with a pointwise Hölder exponent greater than γ(α) at a point of F α is also Haar null. If ε n → 0, taking the union over ε n it follows that for all α ≥ 1 the set of functions in V with an Hölder exponent greater than H(α) at some point of F α is Haar null. Let α n be a dense sequence in (1, ∞). By countable intersection:

M = {f ∈ V : ∀n ∀x ∈ F α n h f (x) ≤ H(α)} ( 27
)
is prevalent. Let f ∈ M and let α ≥ 1. There exist a subsequence α φ(n) which is nondecreasing and tends to α. If we denote Fα the intersection of sets F αn , it follows that Fα contains F α . Furthermore, the Hausdor dimension of Fα is greater than d α and for all x ∈ Fα , h f (x) ≤ H(α). Finally we obtain To conclude the second point of Theorem 1, we rewrite H(α) in the following form

H(α) = 1 α inf a≥α G(a)
where G(a) = sup q (a(-qd + s(q)) + qd) = a sup q (qd(-1

+ 1 a ) + s(q)) = a s * d 1 -1 a .
Here s * is the Legendre transform of s. By denition of the Legendre transform, this is a convex function. Furthermore it satises s

* (h) = +∞ if h < s (+∞) s * (h) = s(0) if h > s (0) . ( 28
)
And if s * is twice dierentiable (we refer to [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms[END_REF] for a general case), G is also twice dierentiable and its derivative is

G (a) = s * d 1 - 1 a + d a (s * ) d 1 - 1 a and: G (a) ≥ 0.
Thus G is also convex and there exists a 0 such that G(a 0 ) = inf a≥0 G(a), a 0 being such that G (a 0 ) = 0. We also deduce from (28) that:

G(a) = +∞ si a < d d-s (+∞) G(a) = as(0) si a > d d-s (0) . ( 29
)
By denition of s and with the hypothesis that η is an admissible function we have 0 ≤ s (q) ≤ d, for all q > 0. It follows from (29) that a 0 belongs to the interval (

d d-s (+∞) , d d-s (0) ) which is included in [0, ∞).
Another way to treat G is to write G(a) = sup q (s(q)) where s(q) = a(s(q) -qd) + qd. And if s is also twice dierentiable, s (q) = -da + as (q) + d and s (q) = as (q) < 0. Thus s is a concave function, and there exists an upper bound q 0 which satises s (q 0 ) = -da + as (q 0 ) + d = 0, and s (q 0 ) = da-d a . The value of q 0 also depends of a so we write now q 0 = q(a).

We can nally write G(a) = a(-q(a)d + s(q(a))) + q(a)d. This function is twice dierentiable and its derivative satises:

G (a) = s(q(a)) -dq(a).
If a = a 0 is the lower bound of G, we obtain G (a 0 ) = s(q(a 0 ))dq(a 0 ) = 0 ⇒ s(q(a 0 )) = dq(a 0 ), that is q(a 0 ) = q c = 1/p c . Furthermore, G is decreasing for a ≤ a 0 and increasing for a ≥ a 0 . The following cases are now possible:

• If α ≥ d d-s (0) , then for all a ≥ α, G(a) = as(0) and H(α) = s(0). So, dim H ({x : h f (x) ≤ s(0)}) = d + s (0). • If 1 ≤ α ≤ a 0 then inf a≥α G(a) = G(a 0 ) = (a 0 (-q c d + s(q c )) + q c d) = dq c .
and the corresponding value of H is

H(α) = 1 α inf a≥α G(a) = dq c α
Thus, the spectrum of singularities is dened on the interval [ dq c a 0 , dq c ] and for almost every function, and for all H ∈ dq c a 0 , dq c dim H ({x :

h f (x) ≤ H}) = H q c .
Furthermore, we have already seen that :

s (q(a)) = da -d a
which is an increasing function. As s is decreasing, the application a → q(a) is itself decreasing. So, for α ≤ a 0 , q ≥ q c = 1 We obtain :

H(α) = sup q -qd + s(q) + qd α .

So for almost every function, for all H ∈ [s(0), dq c a 0 ],: Furthermore, see [START_REF]On the Frisch-Parisi conjecture[END_REF], the spectrum of singularities of all functions of V satises:

d(H) ≤ inf p≥p c (pH -η(p) + d). ( 30
)
This implies that the Hausdor dimension of the set {x : h f (x) < H} is strictly less than d α . As proved in [START_REF] Jaard | Multifractal formalism for functions[END_REF], there exists a measure m α , for any f ∈ V the scaling function is greater than η(p) for all p. Let τ > 0 and p > 0 be xed. We denote τ (p) = η(p) p + τ . We rst prove that the set

M (p) = {f ∈ V ; f ∈ B τ (p),∞
p } is a Haar null set. Let g be the function dened by wavelet coecients given by (24) and P be the probe spanned by g. First, we check that g does not belong to B τ (p),∞ p

. We write β j = d(1 -j J ), where J is dened as in (24). This term β j takes discrete values, spaced by d j and between 0 and d. As the function s is a concave function and 0 ≤ s (q) ≤ d for all q, there exists, for j large enough, a β j near from s (q) such that the line given by τ (p) + β j Taking countable union over τ → 0 and p > 0, we obtain that for almost every f in V , η f (p) ≤ η(p) for all p > 0.

  dim H ({x : h f (x) ≤ H}) ≤ inf p≥p c (pH -η(p) + d) . • If a 0 ≤ α ≤ d d-s (0) , which is equivalent to inf a≥α G(a) = G(α) = α sup q -qd + s(q) + qd α .

  dim H ({x : h f (x) ≤ H}) = inf p≥pc (pH -η(p) + d) ≤ inf p≥pc (pH -η(p) + d) .

2 Proposition 8 .

 28 such that m α ({x : h f (x) ≤ H}) > 0. But by denition of the Hausdor dimension, m α ({x :h f (x) < H}) = 0. Then, m α ({x : h f (x) = H) > 0 and d(H) ≥ inf p≥pc (pH -η(p) + d).For almost every function f in V , the scaling function of f satisfy:η f (p) = η(p), ∀0 < p < ∞.Proof : As we have V = ε>0,0<p<∞ B (η(p)-ε)/p,p p,loc

1 p - 1 p

 11 is always above the graph of s. Thus∀p > 0 τ (p) + β j 1 p -1 p > s(1/p).But a(j, k) = j inf p (β j p -s(1/p)), and this inmum is attained for a p 0 ∈ (0, ∞). Therefore,a(j, k) ≥ j( β j p -τ (p)),andg B τ (p),∞ p ≥ sup j j -a j p 2 τ jp . Thus g ∈ B τ (p),∞ p .Let f be in V . Suppose that there exist α 1 and α 2 such that the functionsf 1 = f + α 1 g and f 2 = f + α 2 g belong to B τ (p),∞ p . Then f 1 -f 2 also belongs to B τ (p),∞ p . But f 1 -f 2 = (α 1 -α 2 )g.As g does not belong to B τ (p),∞ p , we have then α 1 = α 2 . Thus M (p) is Haar null.

  1. If S is Haar-null, then ∀x ∈ V , x + S is Haar-

	null.
	2. If dim(V ) < ∞, S is Haar-null if and only if meas(S) = 0
	(where meas denotes the Lebesgue measure).
	3. Prevalent sets are dense.
	4. If S is Haar null and S ⊂ S then S is Haar null.
	5. The union of a countable collection of Haar null sets is Haar
	null.
	6. If dim(V ) = ∞, compact subsets of V are Haar-null.