Shalom Eliahou

Bruno Massé

Dominique Schneider

L M P A Joseph Liouville

On the mantissa distribution of natural and prime number powers

We study the mantissa distribution of the natural numbers, the prime numbers, and their respective powers to a fixed exponent. This is done with respect to three distinct notions of subsequence density: the natural density, the logdensity and the loglog-density. We first prove that the mantissa sequences of the natural numbers (n) n≥1 and of the prime numbers (p n ) n≥1 are distributed following the continuous Benford law, with respect to both the log-density and the loglog-density. We then show that the mantissa sequences of the powers (n r ) n≥1 and (p r n ) n≥1 , where r ≥ 1 is a fixed exponent, tend to be distributed following the continuous Benford law, with respect to the natural density, as r goes to infinity. Finally, we provide convergence speed estimates.

Introduction

Newcomb in 1881 [START_REF] Newcomb | Note on the frequency of use of the different digits in natural numbers[END_REF], then Benford in 1938 [START_REF] Benford | The law of anomalous numbers[END_REF] drew attention to the fact that, in most collections of numbers found in daily life (physical constants, prices, stock market, geographical data and so on), the proportion of those numbers with first significant digit 1 is much greater than the expected 11% if the digits 1, 2, . . . , 9 appeared equally often as the first digit in base 10 of these numbers. Indeed, the observed frequencies of 1, 2, . . . , 9 as first digit look closer to 0.301, 0.176, 0.125, 0.097, 0.079, 0.067, 0.058, 0.051, 0.046, respectively.

For a real number x > 0, we shall denote by D(x) its first significant digit in base 10, by M(x) ∈ [1, 10[ its mantissa, by x its floor (that is, the largest integer not exceeding x), and by {x} its fractional part. Thus, we have x = M(x)10 k for some integer k, D(x) = M(x) , and {x} = x -x . Moreover, we shall denote by p n the n-th prime number (so that p 1 = 2, p 2 = 3 and so on), by log the neperian logarithm and by log 10 the logarithm in base 10.

Considerations on the invariance under scale change of the above phenomenon lead Newcomb and Benford to conclude that the mantissa of these numbers is necessarily distributed following a law with a density of type t → ct -1 , i.e. according to the continuous Benford law µ B , defined as the probability measure on the interval [1, 10[ characterized by µ B ([1, a[) = log 10 a (1 ≤ a < 10).

Note that µ B is the unique probability measure on the interval [1, 10[ which is invariant by product modulo 10, since the Lebesgue measure is the unique probability measure on [0, 1[ which is invariant by translation modulo 1. They deduced that the first digit must be distributed following ν B , where ν B is the discrete law of Benford on the set {1, . . . , 9} defined, for c = 1, . . . , 9, by

ν B (c) = µ B ( [c , c + 1[ ) = log 10 1 + 1 c .
Work in this subject developed in two directions. The first one looks for conditions on a random variable X ensuring that the mantissa M(X) is of law µ B . See [START_REF] Janvresse | From uniform distributions to Benford's law[END_REF] and [START_REF] Hill | A statistical derivation of the significant digit law[END_REF] for example, and also [START_REF] Miller | The modulo one Central Limit Theorem and Benford's law for products[END_REF] or [START_REF] Sharpe | Limit Laws and Mantissa Distributions[END_REF] for limit theorems on this subject. The second one, that we follow in this paper, looks for classical sequences (u n ) n≥1 such that the sequence (M(u n )) n≥1 is distributed following µ B with respect to the natural density if possible, or else to some other densities. See Section 2 for the subsequence densities that we shall consider in this paper, in particular the log-density and the loglog-density.

Let the nth Fibonacci number be denoted by

F n . The sequences (M(F n )) n≥1 , (M(2 n )) n≥1 , (M(3 n )) n≥1 , (M(n n ))
n≥1 and (M(n!)) n≥1 are distributed, with respect to the natural density, following µ B (see [START_REF] Posch | A Survey of Sequences and Distribution Functions satisfying the First-Digit-Law[END_REF]). Therefore the sequences

(D(F n )) n≥1 , (D(2 n )) n≥1 , (D(3 n )) n≥1 , (D(n n )) n≥1 and (D(n!)) n≥1 are all distributed following ν B .
In contrast, the sequence (D(n)) n≥1 is not distributed following ν B (or any other law) since the proportion of natural numbers whose first significant digit is 1, for example, oscillates indefinitely between the values 5 9 and 1 9 . Fuchs and Letta [START_REF] Fuchs | Le problème du premier chiffre décimal pour les nombres premiers, (French) [The first digit problem for primes[END_REF] deduce from that, with a technique of their own, that the sequence (D(p n )) n≥1 is also not distributed following ν B . Note that this result can also be obtained directly by combining the properties in Section 4 of this paper and the fact that the sequence of fractional parts ({log 10 p n }) n≥1 is not distributed following the uniform law U (see [START_REF] Parent | Exercises in Number Theory[END_REF] where it suffices to replace log by log 10 and e by 10). Recall that the uniform law

U on [0, 1[ is defined by U ([0, a[) = a (0 ≤ a < 1).
In this paper, we first deal with the sequences (M(n)) n≥1 and (M(p n )) n≥1 with respect to the log-and the loglog-density. On this theme, certain partial results are already known. In particular, Fuchs and Letta [START_REF] Fuchs | Le problème du premier chiffre décimal pour les nombres premiers, (French) [The first digit problem for primes[END_REF] show that the sequence (D(n)) n≥1 is log-distributed following ν B and they deduce from this that the sequence (D(p n )) n≥1 is loglog-distributed following ν B . Whitney [START_REF] Whitney | Initial digits for the sequence of primes[END_REF] obtains this last result by direct computations, and Duncan [START_REF] Duncan | Note on the Initial Digit Problem[END_REF] obtains it with respect to the log-density (see also [START_REF] Kanemitsu | On Benford's law: The first digit problem[END_REF], [START_REF] Cohen | Prime Numbers and the First Digit Phenomenon[END_REF] and [START_REF] Akiyama | Almost Uniform Distribution modulo 1 and the distribution of primes[END_REF] who treat close subjects). We show, in what is a stronger result (see above), that the sequences (M(n)) n≥1 and (M(p n )) n≥1 are log-distributed and loglog-distributed following µ B , and we study the speed of convergence. We then consider the sequences (M(n r )) n≥1 and (M(p r n )) n≥1 (r ∈ N * ) with respect to the natural density. We show, in a sense made precise in Section 3, that these sequences tend to be distributed, still with respect to the natural density, following µ B when r → +∞. This phenomenon is illustrated in Figure 1 below. Again, we study the speed of convergence. To the best of our knowledge, the only preceding results on Benford's law concerning sequences of sequences, or arrays of numbers, are due to Diaconis [START_REF] Diaconis | The Distribution of Leading Digits and Uniform Distribution mod 1[END_REF] and concern the binomial coefficients.

All our results are presented in base 10, but they hold in any other numeration base b, and some thoughts about this can be found in the conclusion of this paper.

Notation and definitions

We denote by N * the set of positive integers, by Z * the set of non-zero integers, and, for all h ∈ Z * and all real number x, we set

e h (x) = exp(2iπhx)
where i 2 = -1 .

Subsequence density

Given a subsequence A of a sequence of numbers (u n ) n≥1 , the natural density of A inside (u n ) n≥1 is defined by

lim N →+∞ Card{n ≤ N : u n ∈ A} N = lim N →+∞ 1 N N n=1 1 A (u n ),
when this limit exists1 . More generally, let (w n ) n≥1 be a sequence of positive weights summing to infinity. The density of A inside (u n ) n≥1 , with respect to the w n 's, is then defined by

lim N →+∞ 1 ( N n=1 w n ) N n=1 w n 1 A (u n ) ,
when this limit exists. The natural density corresponds to the case w n = 1 for all n.

We shall also consider the cases w n = 1 n and w n = 1 pn , corresponding to what we shall call the log-density and the loglog-density, respectively, by reference to the fact that, when N → +∞, we have When u n = w n = p n , some authors (see [START_REF] Fuchs | Le problème du premier chiffre décimal pour les nombres premiers, (French) [The first digit problem for primes[END_REF] or [START_REF] Whitney | Initial digits for the sequence of primes[END_REF] for example) speak of logarithmic density relative or conditioned to the prime numbers. Note that, if A admits a natural density inside (u n ) n≥1 , then it also admits a log-density, and these two densities coincide [22, p. 272 . This can be viewed as the weak convergence to µ of the sequence of discrete probability measures (Q N ) N ≥1 where

Q N = 1 N n=1 w n N n=1 w n δ vn ,
and where δ x denotes the Dirac measure at point x.

Let us note at the outset that, if the sequence (M(u n )) n≥1 is distributed following µ B , then the sequence (D(u n )) n≥1 is distributed following ν B , and that the converse does not hold. We may also deduce that the density of the set of members of (u n ) n≥1 whose kth significant digit equals d ∈ {0, . . . , 9} is

log 10   n=10 k-1 -1 n=10 k-2 1 + 1 10n + d   ,
and that the density of the set of members whose first m significant digits give the integer N is log 10 1 + 1 N . This holds for the natural density, the log-density and the loglog-density. Therefore, when it is possible, the study of the distribution of the mantissa of the u n is much more general than that of the first significant digit.

For the above notions of density, the set of even numbers admits 1 2 as density inside the sequence (n) n≥1 of natural integers and, more generally, the set hN * admits 1 h as density inside (n) n≥1 . Therefore, these densities appropriately account for the place that A occupies inside (u n ) n≥1 .

Discrepancy

Let S = (v n ) n≥1 be a sequence of real numbers, N ∈ N * and (w n ) n≥1 a sequence of non-negative weights summing to infinity. The discrepancy modulo 1 of order N of S (see [START_REF] Drmota | Sequences, discrepancies and applications[END_REF][START_REF] Rivat | Inégalités d'Erdős-Turán[END_REF]), associated to (w n ) n≥1 , is the number

D (wn) N (S) := sup 0<a<b<1 1 ( N n=1 w n ) N n=1 w n 1 [a, b[ ({v n }) -(b -a) .
It represents in a way the distance between the uniform distribution U and the distribution, with respect to (w n ) n≥1 , of the first N terms of ({v n }) n≥1 . For the weights

w n = 1, w n = 1
n and w n = 1 pn , these numbers will be denoted D N (S), D log N (S) and D loglog N (S) , respectively. If v n = log 10 u n (n ≥ 1) where (u n ) n≥1 is a sequence of positive reals, this number is also the distance between µ B and the distribution, with respect to (w n ) n≥1 , of the first N terms of (M(u n )) n≥1 because, if v n = log 10 u n , then

D (wn) N (S) := sup 1<c<d<10 1 ( N n=1 w n ) N n=1 w n 1 [c, d[ (M(u n )) -log 10 d c .
(See the corollary in Section 4 for the link between U and µ B .) Note that, if we replace the intervals

Results

We present here the main results of this paper. See above for the link between the discrepancy of (log 10 u n ) n≥1 and the convergence speed in the study of the distribution of (M(u n )) n≥1 . We denote by O the standard big O of Landau. Let us recall that, when a sequence is log-distributed following a probability measure µ, it is then also loglog-distributed following µ (see Section 2.1).

D log N (S 2 ) = O (log N ) -1 (log log N ) 2 and D loglog N (S 2 ) = O (log log N ) -1 2 (log log N ) 2 .
Theorem 3. [START_REF] Cohen | Prime Numbers and the First Digit Phenomenon[END_REF] The sequence (M(p n )) n≥1 is log-distributed following the continuous law of Benford µ B . Moreover, setting S 3 = (log 10 p n ) n≥1 , we have

D log N (S 3 ) = O (log N ) -1 2 (log log N ) 2 and D loglog N (S 3 ) = O (log log N ) -1 2 (log log log N ) 2 .
We say that the mantissa of the terms in the rows of the array of positive real numbers (v r,n ) r,n≥1 tends to be distributed following µ B when r → +∞ if there exists a non-decreasing function φ from N * to N * , of infinite limit, such that

lim r→+∞ sup 1<b<10 Card {n ≤ φ(r) : M(v r,n ) < b} φ(r) -log 10 b = 0 .
This definition is most useful when the rows of the array (M(v r,n )) r,n≥1 do not admit any distribution (like in the sequel). The introduction of a truncation function φ as above is then necessary.

Theorem 3.4 The mantissa of the terms in the rows of the arrays {n r : r ≥ 1 , n ≥ 1} and {p r n : r ≥ 1 , n ≥ 1} tends to be distributed following µ B when r → +∞. Moreover, setting φ(r) = [e r ] and S r = (log 10 n r ) n≥1 or S r = (log 10 p r n ) n≥1 (r ∈ N * ), we have

D φ(r) (S r ) = O(r -1 ) .

Preliminaries

We present here the properties, already known or purely technical, used in the proofs of the results in the preceding section. The first two properties hold for the three sequences of weights (w n ) n≥1 that concern us here:

w n = 1, w n = 1 n and w n = 1 pn .
The Weyl criterion. The sequence of real numbers (v n ) n≥1 is distributed (with respect to w n ) modulo 1 following U if and only if

∀ h ∈ Z * , lim N →+∞ 1 ( N n=1 w n ) N n=1
w n e h (v n ) = 0 .

See for instance [START_REF] Kuipers | Uniform Distribution of Sequences (Dover Publications[END_REF] or [START_REF] Drmota | Sequences, discrepancies and applications[END_REF] for a proof in the case of the natural density. The proofs for the log-density and the loglog-density follow the same lines.

Corollary 4.1 Let (u n ) n≥1 be a sequence of positive real numbers. Given the sequence of weights (w n ) n≥1 , the following four properties are equivalent:

1. the sequence (M(u n )) n≥1 is distributed (with respect to w n ) following the continuous law of Benford;

2. the sequence (log 10 M(u n )) n≥1 of elements in [0, 1[ is distributed (with respect to w n ) following the uniform law;

3. the sequence (log 10 u n ) n≥1 is distributed (with respect to w n ) modulo 1 following the uniform law;

4. ∀ h ∈ Z * , lim N →+∞ 1 ( N n=1 w n ) N n=1
w n e h (log 10 u n ) = 0 .

Proof. Properties 1 and 2 are equivalent since the function log 10 is strictly monotonous as well as a → 10 a . Properties 2 and 3 are equivalent because log 10 M(x) = log 10 x (modulo 1). The equivalence between properties 3 and 4 is a direct consequence of the Weyl criterion.

The following result appears in various guises in the literature, in particular due to the still ongoing search for the best possible constants. We shall use those found in [START_REF] Drmota | Sequences, discrepancies and applications[END_REF] and [START_REF] Rivat | Inégalités d'Erdős-Turán[END_REF]. We want to point out the fact that, in the next three inequalities, the choice of the integer H ≥ 1 is free.

The Erdős-Turán inequality. Let S = (v n ) n≥1 be a sequence of elements in [0, 1[ and let N be a natural number. Then, for every natural number H, we have

D N (S) ≤ 1 H + 1 + H h=1 1 h 1 N N n=1 e h (v n ) , D log N (S) ≤ 3 2 2 H + 1 + H h=1 1 h 1 ( N n=1 1 n ) N n=1 e h (v n ) n and D log log N (S) ≤ 3 2 2 H + 1 + H h=1 1 h 1 ( N n=1 1 pn ) N n=1 e h (v n ) p n .
Proof. See [START_REF] Rivat | Inégalités d'Erdős-Turán[END_REF] for the first inequality and [START_REF] Drmota | Sequences, discrepancies and applications[END_REF] for the other two.

The following property may be found, for instance, in [START_REF] Ribenboim | The Little Book of Bigger Primes[END_REF].

Lemma 4.2 For all n ∈ N * , p n ≥ n log n and there exists a real number C 0 > 0 such that, for all integer n ≥ 3, Proof. Fix n ≥ 1 and θ = 0. Then

|p n -n log n| ≤ C 0 n log log n .
1 n n j=1 j 2iπθ = n 2iπθ R n (f )
where R n (f ) is the Riemann sum of f : t → t 2iπθ on [0, 1] with n regular steps of length

n -1 . Since 1 0 f (t) dt = 1 2iπθ + 1
, thanks to the mean value inequality, we have

R n (f ) - 1 2iπθ + 1 = n-1 j=0 j+1 n j n j + 1 n 2iπθ -t 2iπθ dt ≤ 1 n 0 1 n 2iπθ -t 2iπθ dt + n-1 j=1 j+1 n j n j + 1 n -t 2π|θ| j n dt ≤ 1 n 2iπθ 2iπθ + 1 + 2π|θ| n-1 j=1 1 2jn
.

All our proofs rely on lemma 4.7 below. To prove it we need two famous estimates that we now recall. The first one is Lemma 4.10 in [23, p. 76]. Here is the second estimate. To prove it, it suffices to rewrite the proof of Lemma 2.43 in [5, p. 253] for a non-integer parameter θ. Lemma 4.5 Fix θ = 0. For all integer ν and all real number B > 1, we have

B 1 exp(2iπ(θ log x -νx)) x dx ≤ C |θ| -1 + |θ| -1 2 ,
where C is an absolute constant.

Lemma 4.6 There exists C 1 > 0 and an integer n 0 ≥ 1 such that, for all integer n ≥ n 0 and all θ = 0, we have

n j=n 0 exp(2iπθ log j) j ≤ C 1 |θ| -1 + |θ| -1 2 + |θ| 1 2 n 0 .
Proof. Without loss of generality, we may assume θ > 0. We apply Lemma 4.4 with a = n 0 , b = n, g(x) = 1/x and f (x) = θ log x. This gives

n j=n 0 1 j exp(2iπθ log j) = θ/n-1/2<ν<θ/n 0 +1/2 n n 0 exp(2iπ(θ log x -νx)) x dx + O (1/n 0 log (θ(1/n 0 -1/n) + 2)) + O(1/n 2 0 ) . Observing that log (θ(1/n 0 -1/n) + 2) ≤ θ 1 2 /n 0 1 2 + 2 1 2 /n 0 1 2 , that 1 ≤ θ -1 2 + θ 1 2 and that n 0 ≥ 1 we obtain O (1/n 0 log (θ(1 -1/n) + 2)) + O(1/n 2 0 ) ≤ C θ -1 2 + θ 1 2 n 0 ,
where C is a constant. Applying Lemma 4.5, and observing that the number of terms in the above sum does not exceed 1 + θ(1/n 0 -1/n), it follows that there exists an absolute constant, still denoted C, such that

θ/n-1/2<ν<θ/n 0 +1/2 n n 0 exp(2iπ(θ log x -νx)) x dx ≤ C θ -1 + θ -1 2 (1 + θ(1/n 0 -1/n)) ≤ 2C θ -1 + θ -1 2 + θ 1 2 n 0 .
This concludes the proof. exp(2iπθ h log j) j .

Using Lemma 4.7, we obtain (|h| ≥ 1)

n j=|h|+1 exp(2iπθ h log j) j ≤ C 1 log b + log b 1 2 + log b -1 2 .
Finaly observes that |h| Proof. For all integer n ≥ 3 and all θ ∈ R, we have

exp(2iπθ log p n ) -exp(2iπθ log(n log n)) = p n n log n 2iπθ -1 = 1 + p n -n log n n log n 2iπθ -1 ≤ 2π|θ| |p n -n log n| n log n
as follows from the mean value inequality and taking Lemma 4.2 into account. Therefore, we may choose C 2 = 2πC 0 , where C 0 is the constant involved in Lemma 4.2.

Lemma 4.9 There exists C 3 > 0 such that, for all integer N ≥ 3 and all sequence (θ n ) n≥3 of real numbers, we have

N n=3 exp(iθ n ) n log n - exp(iθ n ) p n ≤ C 3 .
Proof. Let N ≥ 3 and a sequence (θ n ) n≥3 be fixed. Then we have

N n=3 exp(iθ n ) n log n - exp(iθ n ) p n ≤ C 0 N n=3

Proofs

We shall now prove the results stated in Section 3. Set S 1 = (log 10 n) n≥1 , S 2 = (log 10 n log n) n≥2 , S 3 = (log 10 p n ) n≥1 and, for h ∈ Z * and n ≥ 1, θ h = h log 10 , B n = n j=1 j 2iπθ h -1 and

γ h = C 1 log |h| log 10 + log 10 + 1 √ log 10 .
The following estimates will be useful:

H h=1 θ h h = O(H) , H h=1 γ h h = O(log H) 2 and H h=1 θ h γ h h = O (H log H) . (1)
Recall that Lemma 4.7 gives an upper bound of |B n | by γ h which is independent of n.

Proof of Theorem 3.1

1) Let us first study the sequence (M(n)) n≥1 with respect to the log-density, that is with

w n = 1 n . Fix h ∈ Z * .
Then, for all N ∈ N * , we have from Lemma 4.7:

N n=1 e h (log 10 n) n ≤ γ h . (2)
It remains only to divide by log N and to apply Weyl's criterion in order to prove that the sequence (M(n)) n≥1 is log-distributed following µ B .

Relations ( 2) and (1) also show that, for all N ∈ N * ,

H h=1 1 h N n=1 e h (log 10 n) n = O(log H) 2
and the Erdős-Turán inequality then gives

D log N (S 1 ) ≤ 3 2 O(H -1 ) + O(log H) 2 log N .
By choosing H = log N , we obtain a convergence speed of D log N (S 1 ) to 0 at least as fast as that of (log log N ) 2 log N .

2) Let us now study the sequence (M(n)) n≥1 with respect to the loglog-density, that is with w n = 1 pn . Let us fix h ∈ Z * and the integer N ≥ 3. Observe first that, for all n ≥ 2, we have

1 log n - 1 log(n + 1) = n+1 n -1 x(log x) 2 dx ≤ 1 n(log n) 2 . (3)
Then, thanks to Abel's transformation and Lemma 4.7, we have

N n=2 e h (log 10 n) n log n = N n=2 n 2iπθ h -1 (log n) -1 = B N (log N ) 2iπθ h -B 1 (log 2) 2iπθ h + N -1 n=2 B n 1 log n - 1 log(n + 1) ≤ |B N | + 1 + N -1 n=2 |B n | 1 n(log n) 2 ≤ γ h + 1 + γ h log 2 .
This, together with Lemma 4.9, implies

N n=2 e h (log 10 n) p n ≤ C 3 + γ h + 1 + γ h log 2 . (4)
Relations ( 4) and [START_REF] Akiyama | Almost Uniform Distribution modulo 1 and the distribution of primes[END_REF] show that, for all N ∈ N * ,

H h=1 1 h N n=1 e h (log 10 n) p n = O(log H) 2
and the Erdős-Turán inequality then gives

D log log N (S 1 ) ≤ 3 2 O(H -1 ) + O(log H) 2 log log N .
Choosing H = log log N leads to the announced bound. This concludes the proof of Theorem 3.1.

Proof of Proposition 3.2

1) Let us first study the sequence (M(n log n)) n≥2 with respect to the log-density. Let us fix h ∈ Z * and the integer N ≥ 3. Then, thanks to Abel's transformation, relation

and Lemma 4.7, we have

N n=2 e h (log(n log n)) n = N n=2 n 2iπθ h -1 (log n) 2iπθ h = B N (log N ) 2iπθ h -B 1 (log 2) 2iπθ h + N -1 n=2 B n (log n) 2iπθ h -(log(n + 1)) 2iπθ h ≤ |B N | + 1 + N -1 n=2 |B n | 2π|θ h | n log n ≤ γ h + 1 + 2π|θ h |γ h (log log N -log log 2) . (5)
It remains to divide by log N and to apply Weyl's criterion in order to prove that the sequence

(M(n log n)) n≥2 is log-distributed following µ B .
The Erdős-Turán inequality and relations ( 5) and ( 1) give

D log N (S 2 ) ≤ 3 2 O(H -1 ) + O(log H) 2 + O(log H) + (1 + log log N )O(H log H) log N . Choosing H = (log N ) 1 2
leads to the announced bound.

2) Let us now study the sequence (M(n log n)) n≥2 with respect to the loglog-density. Let us fix h ∈ Z * and the integer N ≥ 3 and observe that, for all n ≥ 2, we have

(log n) 2iπθ h -1 -(log(n + 1)) 2iπθ h -1 = n+1 n (2iπθ h -1) (log x) 2iπθ h -2 x dx ≤ |2πθ h -1| n(log n) 2 .
Therefore, because of Abel's transformation and Lemma 4.7, we have

N n=2 e h (log 10 (n log n)) n log n = N n=2 n 2iπθ h -1 (log n) 2iπθ h -1 = B N (log N ) 2iπθ h -1 -B 1 (log 2) 2iπθ h -1 + N -1 n=2 B n (log n) 2iπθ h -1 -(log(n + 1)) 2iπθ h -1 ≤ |B N | log N + 1 log 2 + N -1 n=2 |B n | |2πθ h -1| n(log n) 2 ≤ γ h log N + 1 log 2 + |2πθ h -1| γ h log 2 .
This, together with Lemma 4.9, implies

N n=2 e h (log 10 (n log n)) p n ≤ C 3 + γ h log N + 1 log 2 + |2πθ h -1| γ h log 2 . ( 6
)
The Erdős-Turán inequality and relations (1) and [START_REF] Duncan | Note on the Initial Digit Problem[END_REF] give

D log log N (S 2 ) ≤ 3 2 O(H -1 ) + O(log H) 2 + O(log H) + O (H log H) log log N .
It remains only to fix H = (log log N )

) n ≤ γ h + 1 + γ h 2π|θ h |(1 + log log N ) + C 2 |θ h | N n=3 log log n n log n . (7)
Since, when N → +∞, we have

N -1 n=3 log log n n log n ∼ (log log N ) 2 2 ,
it only remains to divide by log N and to apply Weyl's criterion in order to prove that the sequence (M(p n )) n≥1 is log-distributed following µ B .

The Erdős-Turán inequality and relations [START_REF] Fuchs | Le problème du premier chiffre décimal pour les nombres premiers, (French) [The first digit problem for primes[END_REF] and [START_REF] Akiyama | Almost Uniform Distribution modulo 1 and the distribution of primes[END_REF] give

D log N (S 3 ) ≤ 3 2 O(H -1 ) + O(log H) 2 + O(log H) + O (H log H) (1 + log log N ) + O(H)(log log N ) 2 log N .
Choosing H = (log N )

1 2
leads to the announced bound.

2) Let us now study the sequence (M(n log n)) n≥2 with respect to the loglog-density.

Let us fix h ∈ Z * and the integer N ≥ 3. Then, from relation ( 6) and Lemma 4.8, we have

N n=3 e h (p n ) p n ≤ C 3 + γ h log N + 1 log 2 + |2πθ h -1| γ h log 2 + C 2 |θ h | N n=3 log log n p n log n . (8)
The Erdős-Turán inequality and relations ( 1) and ( 8) give

D log log N (S 3 ) ≤ 3 2 O(H -1 ) + O(log H) 2 + O(log H) + O (H log H) + O(H) log log N .
Then, by fixing H = (log log N )

1 2 , we get the announced bound. The proof of Theorem 3.3 is now complete.

Proof of Theorem 3.4

In the computations that follow, the term O(1) 1 r appears in each upper bound of the discrepancy. Therefore, these upper bounds can only converge to 0 if r goes to infinity.

1)

Let us first study the rows of the array (n r ) r,n≥1 with respect to the natural density (and hence, here, S r = (log 10 n r ) n≥1 for r ∈ N * ). Let us fix the integers N ≥ 1, h ≥ 1 and r ≥ 1. From Lemma 4.3, we have The Erdős-Turán inequality then gives

D N (S r ) ≤ O(H -1 ) + O(1) 1 r + O(log H) N + O(H)r log N N . (9)
We have infinitely many choices for the values of N = φ(r) and values of H depending on r that lead to lim r→+∞ D φ(r) (S r ) = 0.

In particular, taking H = r and N = φ(r) = e r , we obtain D φ(r) (S r ) = O(r -1 ), which is the best that can be expected from relation [START_REF] Hill | A statistical derivation of the significant digit law[END_REF].

2) Let us now study the rows of the array (n r log r n) r,n≥1 with respect to the natural density (and hence, here, S r = (log 10 (n r log r n)) n≥1 ). Let us fix the integers N ≥ 3, h ≥ 1 and r ≥ 1, and set θ = rh(log 10) -1 and, for n ≥ 1, A n = n j=1 j 2iπθ and v n = log 10 (n r log r n). We first remark that, for n ≥ 2, we have

(log n) 2iπθ -(log(n + 1)) 2iπθ = 2π|θ| n+1 n (log x) 2iπθ x log x dx ≤ 2π|θ| n log n .
Therefore, because of Abel's transformation and Lemma 4.3, we have

N n=2 e h (v n ) = N n=2 n 2iπθ (log n) 2iπθ = A N (log N ) 2iπθ -A 1 (log 2) 2iπθ + N -1 n=2 A n (log n) 2iπθ -(log(n + 1)) 2iπθ ≤ N 2π|θ| + 2 + π|θ| log N + N -1 n=2 n 2π|θ| + 1 + π|θ| log n 2π|θ| n log n .
Thus, from the properties of the integral logarithm function, there exists a constant K > 0 such that

N n=1 e h (v n ) ≤ N 2π|θ| + 3 + KN log N + π|θ|(log N + 2 log log N ) + 2π 2 θ 2 log N .
Therefore, for all integer r ≥ 1 and all N ≥ 3,

H h=1 1 h N n=1 e h (v n ) = O(1) N r + O(log H) N log N + O(H)r log N + O(H 2 )r 2 log N . (10)
This, together with the Erdős-Turán inequality, gives

D N (S r ) ≤ O(H -1 ) + O(1) 1 r + O(log H) log N + O(H)r log N N + O(H 2 )r 2 log N N .
And, for H = r and N = φ(r) = e r , we again obtain D φ(r) (S r ) = O(r -1 ).

3) Finally, let us study the rows of the array (p r n ) r,n≥1 with respect to the natural density (and hence, S r = (log 10 (p r n )) n≥1 here). Let us fix the integers N ≥ 3, h ≥ 1 and r ≥ 1, and set again v n = log 10 (n r log r n). Applying Lemma 4.8 to θ = rh(log 10) -1 and using the properties of the integral logarithm, we obtain This concludes the proof of Theorem 3.4.

Conclusion

All [START_REF] Raimi | The first digit problem[END_REF] and [START_REF] Knuth | The Art of Computer Programming volume[END_REF]). Note that, in our proofs, we have shown that, when r → +∞, the mantissa of the row terms of the array ((n log n) r ) r,n≥1 tends to be distributed following µ B .

It is very easy to verify that if (M(u n )) n≥1 is distributed (log-distributed and loglogdistributed, respectively) following µ B , then (M(u r n )) n≥1 also is for all r ∈ N * . Therefore, for all r ∈ N * , the sequences (M(n r )) n≥1 , (M(p r n )) n≥1 and (M((n log n) r )) n≥2 are log-distributed and loglog-distributed following µ B .

It is well known to the arithmeticians that, for a real number α, the sequence of fractional parts ({αn}) n≥1 is distributed following U if and only if α is an irrational number. Because of the properties recalled in Section 4, we deduce from this that the mantissa of the terms of each column of the array (p r n ) r,n≥1 (and, up to rare exceptions, of each column of (n r ) r,n≥1 ) is distributed following µ B with respect to the natural density. Moreover, the diagonal of the array (n r ) r,n≥1 is the sequence (n n ) n≥1 whose mantissa are distributed, still with respect to the natural density, following µ B [START_REF] Posch | A Survey of Sequences and Distribution Functions satisfying the First-Digit-Law[END_REF].

Figure 1 :

 1 Figure 1: Frequency of 1, 2, . . . , 9 as first digit of p r i for i ≤ 10000 and r = 1, 2 and 20. The unmarked curve is Benford's law.

  [a, b[ and [c, d[ by the intervals [0, b[ and [0, d[, we obtain the so-called star-discrepancy [5, p. 5] which is exactly, in our situation, the Kolmogorov distance between µ B and the probability measure Q N defined above with M(u n ) instead of v n .

Theorem 3 . 1

 31 The sequence (M(n)) n≥1 is log-distributed following the continuous law of Benford µ B . Moreover, setting S 1 = (log 10 n) n≥1 , we have D log N (S 1 ) = O (log N ) -1 (log log N ) 2 and D loglog N (S 1 ) = O (log log N ) -1 (log log log N ) 2 . Proposition 3.2 The sequence (M(n log n)) n≥1 is log-distributed following the continuous law of Benford µ B . Moreover, setting S 2 = (log 10 n log n) n≥2 , we have

Lemma 4 . 3

 43 For all integer n ≥ 1 and all θ = 0, we haven j=1 exp(2iπθ log j) ≤ n 2π|θ| + 1 + π|θ| log n .

Lemma 4 . 4

 44 Let f (x) and g(x) be two functions with continuous derivatives in the interval [a, b] such that f (x) and |g (x)| are non-increasing and g is positive and decreasing. Then a≤j≤b g(j) exp(2iπf (j)) = α-η<ν<β+η b a g(x) exp(2iπ(f (x) -νx)) dx + O(g(a) log(β -α + 2)) + O(|g (a)|) where β = f (a), α = f (b) and η is an arbitrary constant such that 0 < η ≤ 1.

Lemma 4 . 7

 47 There exists C > 0 (depending only on b > 1) such that, for all integer n ≥ 1 and all h ∈ Z * , we have n j=1 exp(2iπh log b j) j ≤ C + log |h|. Proof. Without loss of generality, we assume that n ≥ |h| + 1. Fix θ h = h log b .

j=1 1 j

 1 ≤ C + log |h|. This concludes the proof. Lemma 4.8 There exists C 2 > 0 such that, for all integer n ≥ 3 and all θ ∈ R, we have exp(2iπθ log p n ) -exp(2iπθ log(n log n)) ≤ C 2 |θ| log log n log n .

1 2 . 5 . 3 3 1)

 2533 This concludes the proof of Proposition 3.2. Proof of Theorem 3.Let us first study the sequence (M(p n )) n≥2 with respect to the log-density. Let us fix h ∈ Z * and the integer N ≥ 3. Then, thanks to Abel's transformation, relation (5) and Lemma 4.8, N n=3 e h (log 10 p n

πhr log N log 10 .e

 10 Thus, for all N ≥ 1 and all r ≥ 1, h (log10 n r ) = O(1) N r + O(log H) + O(H)r log N .

  (log 10 p r n ) -e h (v n )) = O(H)r N log log N log N .Relation[START_REF] Janvresse | From uniform distributions to Benford's law[END_REF] and the Erdős-Turán inequality then implyD N (S r ) ≤ O(H -1)+O(H = r and N = φ(r) = e r , we again obtain D φ(r) (S r ) = O(r -1 ).

  our results and proofs remain valid with an arbitrary numeration base b > 1, even a non-integral one. It suffices to replace log 10 by log b , the usual mantissa M by the mantissa M b in base b, and µ B by the probability µ B,b on [1, b[ defined by µ B,b ([1, a[) = log b a. This is all the more remarkable since, for example, the sequence (M b (2 n )) n≥1 is distributed following µ B,b only if b is not a rational power of 2 and there exists no random variable X such that the law of M b (X) is µ B,b for all b > 1 ([

  ]. The converse is false, in general, as shown by the set of integers whose first digit is 1 (see above). Moreover, in view of the fact that p n is equivalent to n log n as n → ∞, Theorem 14 in [8, p. 58] (or Lemma 7.1 in[13, p. 63]) proves that, if A admits a log-density inside (u n ) n≥1 , then it also admits a loglog-density, and these two densities coincide.Let (v n ) n≥1 be a sequence of elements in an interval [a, b[ and µ a probability on [a, b[. For c ∈ ]a, b[, denote A c = {v n : n ∈ N * , a ≤ v n < c}. Then we say that (v n ) n≥1 is distributed (log-distributed, loglog-distributed, respectively) following µ when, for all c ∈ [a, b[, A c admits µ([a, c[) as natural density (log-density, loglogdensity, respectively) inside (v n ) n≥1

The symbol 1 A denotes the indicator function of A.

Authors' addresses:

Shalom Eliahou a,b,c , Bruno Massé a,b,c , Dominique Schneider a,b,c , a Univ Lille Nord de France, F-59000 Lille, France b ULCO, LMPA J. Liouville, B.P. 699, F-62228 Calais, France c CNRS, FR 2956, France e-mail: {eliahou, bmasse, dominique.schneider}@lmpa.univ-littoral.fr


Nicole Vincent

Jean-Marc Ogier

Shall deep learning be the mandatory future of document analysis problems?

Keywords: Features, Machine Learning, Deep methods, Handcraft approach

As the use of deep methods become widespread in the scientific community, causing major changes in systems architecture and position in terms of knowledge acquisition, we report here our insights about how document analysis systems are built. Where does the expertise really lie? In the features, in the decision making step, in the system design, in the data illustrating the problem to be solved? The examination of the practices of researchers in this field, and their evolution, allows us to conclude that the tools that are used, and related issues, have become more and more complex over time. Nevertheless, human skill is needed to activate these tools and to imagine new ones.

Introduction

The widespread use of electronic documents including the digitally native documents is made easier today through effective means of electronic management. In the late 20th century, the main issue was to turn content on paper, or more precisely images of paper documents into digital and editable documents.

It took many years for the struggling scientific community to implement reading systems that would be able to process a huge variability of documents going from forms [START_REF] Ramdane | Classification of forms with handwritten fields by planar hidden markov models[END_REF], bank checks [START_REF] Gorski | A2ia check reader: a family of bank check recognition systems[END_REF].... to the management of mail and financial documents [START_REF] Rusiñol | Multimodal page classification in administrative document image streams[END_REF].

Even though industrial systems are generally operational, the natural use of e-documents, which in fact are hybrid documents, is not actually obtained and may still be improved in many ways. If a document can be natively in a digital format, such as proprietary doc format or free pdf format, then it can be printed, scanned or snapped with a camera. The processing of hybrid documents, both paper and digital, represents a real scientific challenge for the document analysis community, despite the fact that most documents are now digitally produced. New processing must consider the hybrid nature of documents. It is also important to note that document analysis has evolved: it is not just about reading [START_REF] Tang | Automatic document processing: A survey[END_REF], managing or understanding a paper document from a screenshot [START_REF] Christy | Mass digitization of early modern texts with optical character recognition[END_REF] [START_REF] He | Beyond ocr: Multi-faceted understanding of handwritten document characteristics[END_REF]. The aim is now to make the document "smart". Indeed, through the print-and-scan processes, the initial structure as well as the content of the document may be lost. This explains the constant need for new document analysis algorithms, especially in the preprocessing phase. actually more complex than a "simple" reading task. For the reader, indeed, understanding the content of a document requires interpreting various elements such as printed or handwritten notes, text, tables, graphics or even images, as well as text contents, global document apparearance. These elements are sometimes mentioned as contextual information. Nevertheless, closer analysis shows that reading involves many different and difficult tasks, due tovariability of document types, content and layout :

• At first, character recognition in English or any Latin languages. The Asian and Arabic alphabets were considered later and more recently southerneastern languages. Should the recognition methods remain the same for these different contexts? The universal aspect of a method is questionnable in various contexts, when the reading concerns forms, addresses, full text or graphical documents or even text inside images capturing natural scenes.

Are language models really needed? Besides, the recognition process focused initially on segmented printed characters. Studies today aim to address the issues of constraint-free modern and historical handwritten documents, which appears to be a great scientific challenge. for the understanding of the document context.

• Layout, text or image extraction, graphical drawing interpretation.

• Alphabet separation as a preprocessing of text reading.

• Authentication, writer identification.

• Old documents analysis, classification or reading.

• Information retrieval, through multimodality queries.

• Security involving different levels, especially in a print-and-scan workflow process: are the content meanings of two documents equivalent or should the doucment be an occurrence of a hybrid document, as presented in the introduction?

Simple or Complex features

In order to achieve these various applications, the image content has to be analyzed. The systems rely on a common design structure, first comes the choice of a representation space and then the decision step chosen according to the application. In this section, we focus on the representation space that has long been a matter of debate when it comes to achieve best results. We try to give a coarse outline of the most classical features.

The first simplest representation is the representation of the image. At its core, the representation of an image is an array of pixels depicting the real world.

Then, the simplest feature is the color (or grey level) of a single pixel, that can be extended to the whole image, forming a feature vector. Time going on, Through time, the single pixel approach has been replaced by a multiple pixels approach, a zone approach, such as the content of fixed or adaptive rectangular zones or some straight or curved lines in the image. From these geometrical fixed analyzed windows some algorithms have been developed to extract some significant zones in the binary images. For instance, connected components were studied for their size, geometric or density properties/features. In color images, superpixels have been defined. One of the difficulties of image analysis with respect to signal processing lies in the 2D dimension of the image signal. There have been attempts to transfer image content to chain representation. This is the case using the connected component contours and the Freeman code [START_REF] Freeman | Computer processing of line-drawing images[END_REF] in a binary image. Another way of doing it was to consider the image skeleton [START_REF] Stefanelli | Some parallel thinning algorithms for digital pictures[END_REF], with 1D contribution but fundamentaly a 2D object. The aim is to decrease the complexity of an image content. Nevertheless, the image is considered as a 2D object, either features can be extracted for describing its content or characteristic vectors can be considered as a way to get more information.

Both are used to perform comparisons. In this modeling approach handcrafted features are obtained from the expert perception of the image content. Some features are derived from the general knowledge in pattern recognition, based on solid mathematical thorems, such as a decomposition of multivariate functions (images are defined in a two-dimensional space). In this category of features, can be considered all the moments, (geometric, Zernike, Fourier-Mellin), the discrete Fourier transform. These features have been largely used. Since the works of Hu in 1961, invariant moments [START_REF] Hu | Visual pattern recognition by moment invariants[END_REF], which are based on combinations of regular geometric moments, have been very frequently used [START_REF] Rothe | The method of normalization to determine invariants[END_REF]. Among the various moments, one can thus cite Zernike moments [START_REF] Teague | Image analysis via the general theory of moments[END_REF], [START_REF] Khotanzad | Rotation invariant image recognition using features selected via a systematic method[END_REF], [START_REF] Khotanzad | Invariant image recognition by Zernike moment[END_REF], [START_REF] Liao | On the accuracy of Zernike moments for image analysis[END_REF], [START_REF] Hu | Orthogonal moments based on exponent functions: Exponent-fourier moments[END_REF].

They consitute a reference in the domain, giving pseudo-Zernike moments [START_REF] Teague | Image analysis via the general theory of moments[END_REF],

Bamieh moments [START_REF] Bamieh | A general moment-invariant/attributed graph method for three dimensional object recognition for a single image[END_REF], and Legendre moments [START_REF] Chen | Perfecting vectorized mechanical drawings[END_REF]. These invariant moments, which can be extracted from a binary or a grey-scale image, generally offer properties of reconstructibility, thus ensuring that extracted features contain all the information, at least enough information, about the shape under study. This completeness property shows the coarseness of description for such invariants.

Good comparative studies about invariant moment can be found in [START_REF] Teh | On image analysis by method of moments[END_REF] and [START_REF] Belkasim | Pattern recognition with moment invariants : A comprative study and new results[END_REF],

showing the superiority of Zernike moments in terms of recognition accuracy.

The most frequent description models deal with Fourier descriptors [START_REF] Pei | Normalisation of rotationally symetric shapes for pattern recognition[END_REF] or elliptic Fourier descriptors [START_REF] Lin | New forms of shape invariants from elliptic fourier descriptors[END_REF]. Taxt [START_REF] Taxt | Recognition of handwritten symbols[END_REF] proposed a comparative study between these descriptors. This study highlights the potentialities of these descriptors, in terms of simplicity and robustness. Taxt [START_REF] Taxt | Recognition of handwritten symbols[END_REF] in particular, proposed to use elliptic Kuhl moments [START_REF] Kuhl | Elliptic fourier features of closed contour[END_REF] when characters orientation is known. This technique is also used by Trier [START_REF] Trier | Extraction methods for character recognition a survey[END_REF] for character recognition on hydrographic maps. Authors claim to obtain a good recognition rate of 78 % for only 2,3% of misclassification on a test set of 1760 hand-written characters. The standard recognition rate has improved a lot since that time! The features were basic including template matching.

On the other hand, in the context of optical character recognition, structural invariant features can also be extracted from characters or thinned characters [START_REF] Shimotsuji | Robust drawing recognition based on based-guided segmentation[END_REF]. For instance, one can cite the number of occlusions, the number of T-joints or X-joints, the number of bend points. However, it has been shown that such features used alone do not lead to robust recognition systems [START_REF] Mori | Historical review of ocr research and development[END_REF]. Graph representations are then introduced [START_REF] Shaw | Parsing of graph-representable pictures[END_REF]. This period corresponds to the beginning of the opposition between statistical methods and Artificial Intelligence that advo-6 cated description which were natively invariant using elementary features and relations between them. Graphs were one of the mathematical tools enabling this kind of representation and the decision step was relying on graph similarity, among which graph edit distance, graph isomorphisms for instance. The theoretical aspect was attractive but the results at that time were not robust enough from an industrial point of view, especially because of complexity questions. In fact, the descriptions were too simple to cope with the shape variability, and the machine capacities could not allow to manage graph with too many vertices.

Nowadays, larger graphs are used and comparison is achieved by some graph embedding methods [START_REF] Riesen | Graph classification based on vector space embedding[END_REF] or based on graph kernel function [START_REF]Recent advances in graph-based pattern recognition with applications in document analysis[END_REF] or on graph edit distance [START_REF] Fischer | Improved quadratic time approximation of graph edit distance by combining Hausdorff matching and greedy assignment[END_REF].

More recently, and in the same trend linked to the principle of the decomposition of a function according to a function basis. There have been various

wavelet transforms leading to some sets of coefficients characterizing the image content. These transforms do not only consider the initial image but also different observation scales, leading to numerous possibilities of coefficients. A limited number of coefficents have to be selected among these coefficients in order to be considered as features. Many contributions have focused on the exploitation of wavelet theory for pattern recognition. A wavelet transform differs from a

Fourier transform in that it is able to provide both a frequency and time representation of a 1D or a 2D signal. It allows to perform a local and global analysis of a shape [START_REF] Daubechies | the wavelet transform, time-frequency localization and signal analysis[END_REF], [START_REF] Daubechies | Ten lectures on wavelets[END_REF]. It is therefore particularly adapted to the extraction of a model of discriminant shape thanks to this multi-resolution aspect [START_REF] Deng | Document segmentation using polynomial spline wavelets[END_REF]. Among the works exploiting this wavelet theory, two can be cited, Shen [START_REF] Shen | Discriminative wavelet shape descriptors for recognition of 2-d patterns[END_REF] and Chen [START_REF] Chen | Invariant Fourier-Wavelet descriptors for pattern recognition[END_REF] approaches.

In Shen approach [START_REF] Shen | Discriminative wavelet shape descriptors for recognition of 2-d patterns[END_REF], the authors first present a general framework of invariant shape recognition with respect to rotation. By analyzing the different works presented in the literature, the authors infer that all moment-based approaches can be expressed through formula 1 .

F pq = S q (r).g p (r)rdr with S q (r)= f(rcosθ, rsinθ)e iqθ dθ

In this expression, F pq denotes an invariant moment of order pq (p and q are integers), and g p denotes a function of the radial variable, let us say r in formula 1. By way of example, if g p (r)=r p , it is possible, by imposing constraints on p and q, to express the Hu moments. The author proposes also a formulation of g p (r) allowing the computation of the moments of Zernike, without however expressing all the compelling constraints on p and q. From this proposition of a unified moment extraction framework, the authors replace the function g p with a basic function of wavelets, considering the family defined by formula 2.

ψ a,b (r)= 1 √ a ψ( r -b a ) ( 2 )
The mother wavelet used in the article is the Cubic B-Spline wavelet, whose formulation, proposed in [Unser 1996], is given by formula 3

(r)= 4a n+1 2π(n +1) σ w cos(2πf 0 (2r -1))exp(- (2r -1) 2 2σ 2 w (n +1) )=g n (r)( 3 )
To model the shapes contained in the image, the authors then use the magnitude of F pq , making it possible to obtain a shape description, which is invariant with respect to rotation. Invariance to a change of scale is obtained by means of a standard process of normalization comparable to regular moments.

Chen's approach [START_REF] Chen | Invariant Fourier-Wavelet descriptors for pattern recognition[END_REF] differs somewhat from the previous one. Indeed, starting from the qualities and defects of the Fourier transform and the wavelet transform, the author uses them both. The principle used can be described by the synoptic in figure 1. The first step in this model extraction is to normalize the shape and change the cartesian variables into the polar domain. To do this, the authors use a zoning of their shape, based on concentric circles and on radial probes. An averaging in each zone makes it possible to change Cartesian coordinates to polar coordinates. Then, a 1D Fourier transform is applied along the angular axis ( θ ), to obtain invariance regarding rotation, embedding the famous transfer theorem in Fourier analysis. A wavelet transform is then applied, this time following the radial variable r in order to take advantage of the multi-resolution aspect of the wavelets. The use of this approach is still quite frequent in the community [START_REF] Suryani | The handwritten sundanese palm leaf manuscript dataset from 15th century[END_REF] Stone-Weierstrass theorem [START_REF] Rudin | Real and Complex Analysis[END_REF], ensure the theoretical convengence. Of course, the convergence speed is very important in a computer science application. Besides, theoretical properties most often hold for continuous function whereas computation is performed in a discrete space. Thus, some different sources of approximation as well as the number of efficient coefficients yield some variations in the use of these feature vectors according to the developped applications.

The selection of coefficients is achieved by maximizing the information provided at the right level for any given application. This may be the reason why this more signal processing approach did not received wide acclaim in the document community more prone to pattern recognition approaches. Besides, the use of continous functions tends to introduce discretisation errors. Discontinous functions, peacewise constant functions, are more appropriate as in Harr transform or Harr Wavelets. In [START_REF] Ghorbel | A segmentation free word spotting for handwritten documents[END_REF], the optimum observation scale is looked for before application of an Harr transform.

Some features bear similarities with the Human Visual System. Implementing those features led to some pioneering work by Marr [START_REF] Marr | Vision: A Computational Investigation into the Human Representation and Processing of Visual Information[END_REF]. Marr's work served as a basis for the use of Gabor transform [START_REF] Gabor | Theory of communication[END_REF] that is supposed to correspond to cabled operators present in the human nervous system [START_REF] Sharma | Word-wise script identification from video frames[END_REF]. Features can also be deduced from some perception theories such as Gestalt theory. In this case, alignment properties are looked for as well as distance from elements to their nearest neighbors. From this approach, one of the greatest lessons that has emerged is the concept of interest points, also known as keypoints. Two aspects are tightly linked to this notion, with respectively (i) key point detectors based for instance on Harris cover detection [START_REF] Harris | A combined corner and edge detector[END_REF] or on SIFT keypoints (scale-invariant feature transform) [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] and (ii) key point descriptors that allow to describe image content around the keypoint [53][54]. This discriminates between methods relying only on the presence of characteristic points and dense methods that analyze all points in the image. For point description many solutions have been proposed that cannot all be mentioned here. Among them, one can cite shape context [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF], SIFT and all their variations, HOG (Histogram of oriented gradients) [START_REF] Hangarge | Word retrieval from kannada document images using HOG and morphological features[END_REF], [START_REF] Berenguel | e-counterfeit: a mobileserver platform for document counterfeit detection[END_REF], LBP (Local binary patterns) [START_REF] Dey | Local binary pattern for word spotting in handwritten historical document[END_REF], [START_REF] Mohammed | Normalised local nave bayes nearest-neighbour classifier for offline writer identification[END_REF] [60] which all serve the same global purpose. Features can be used in themself or some histogram structures can be associated in spatial domains.

So far, we have presented the features that are studied in the literature.

To improve results, researchers have tried to use those features in an optimal way. But as their primary goal is to obtain as much information as possible, there is a tendency to accumulate characteristics in large dimensional vectors, which may not be enough. In fact, this appears to be not so efficient in most occasions. Indeed, in a representation space with a dimension far too large, the famous curse of dimensionality holds and makes computation and comparison unrealistic. Besides, each characteristic may bring noisy information, some of which being more noisy than others, some others being redundant and making the process run longer than necessary. The aim of any system is to select the most relevant features and the most diverse ones. A selection process reduces the number of efficient features and makes the system more robust: many approaches have been proposed for solving this question, such as filter, wrapper and hybrid procedures, which are among the most common methods. Wrapper methods are more efficient but are generally too time consuming; hybrid methods tend to optimize the efficiency and the computation work. For these approaches, the characteristics are not modified [61] [62]. Another approach is to try to define better features than the initial ones, based on a combination of the initially chosen features. This is the case when considering a Principal

Component Analysis (PCA), trying to decrease the redundancy inherent to hancraft features or Independant Component Analysis (ICA). At the same time, it is possible to limit the number of features without damaging the result accuracy as the properties of the new representation axis are ordered. However, the new features are more difficult to understand since they correspond to a linear combination of the initial ones.

Knowledge or Learning

F e a t u r e sc a nbec o n s i d e r e da sa ne x t r a c t i o no fi n f o r m a t i o nf r o mw h i c hd e c ision making has to be achieved. We have considered the two main approaches that have been used in document analysis applications. Some are based on implicit or explict knowledge. The others applications are based on a learning phase that is supposed more objective.

Knowledge-based approach

Since the 1950s, document understanding has gone through multiple cycles alternating between knowledge-based approaches and learning-based approaches. Originally, systems were tightly linked to the expert, the knowledge of whom was modelled on the basis of more or less explicit formalisms: This knowledge could be introduced through parameters of the system (thresholds, rules, ....) or through theoretical formalisms such as semantic networks, graphs, grammars, and more recently ontologies. For all those systems, the document analysis was often based on a sequential ordering of processes aiming at extracting the information from a document, so that the process could fit with the expert knowledge. Often, these approaches rely on an attempt to model the human visual system. Among the most famous systems, is ANON system proposed by Joseph in 1992 [START_REF] Joseph | Knowledge-directed interpretation of line drawing images[END_REF]. These context modellings suppose that the physical representations of a document are part of a visual language that has a reasonably formal grammar associated with it. The assumption is that the meaning of the message is fully embedded in the document and that the knowledge of the language in which it was expressed is sufficient to recover the meaning of the document. In the graphic recognition context, this is usually considered as the core domain of graphical document analysis. For these systems, the knowledge is implicit and used in an internal way often introduced as heuristics (in the algorithms) or externally (outside of algorithms), generating systems that are more or less generic. The external knowledge generally relies on knowledge representation methods. These approaches use many knowledge representation formalisms, such as rules, graphs, frames, semantic networks [START_REF] Antoine | Analysis of technical documents: The redraw system, Structured Document Image Analysis[END_REF],

graph based representation [START_REF] Llados | Symbol recognition by error-tolerant subgraph matching between region adjacency graphs[END_REF] and more recently ontologies [66] [67]. A number of other alternatives can be found in the literature (languages, databases, algebra, list, matrix, and so on). Also, other studies look into the neuroscience analysis, based on oculomotor studies or other models. Here Marr and Gestalt theory can be cited [START_REF] Desolneux | Gestalt theory and computer vision[END_REF]. This was the foundation of original studies such as Ogier in 2000 [START_REF] Ogier | Semantic coherency: the basis of an image interpretation device-application to the cadastral map interpretation[END_REF]. Ogier proposed a complete cadastral map interpretation system based on a perception cycle principle. In the same way, one can also find pure rule based systems that use the advances in artificial intelligence , which are modelling expert knowledge through agents that are able to decide through argumentation and rounds of dialogues [START_REF] Cloppet | An agent-based system for printed/handwritten text discrimination[END_REF]. All these knowledge-based systems are involving an explicit learning. Whatever the systems may be, there are explicit and implict parameters involved, the most obvious ones being thresholds that are fixed and tuned according to experiments, so that the system accuracy is maximized.

Deep Learning

Totally different from knowledge-based approaches are learning-based approaches. Their principle consists in extracting the knowledge from some annotated datasets (such as annotated images for instance). These data are introduced as inputs for a training system. Here, the aim is not to recall the principle of deep learning nor to give an overview of the development studies defining the different architectures in terms of layers number. The objective is neither to present their family or the different objective functions that were proposed in the literature. In past times, artificial networks (ANN) were introduced [START_REF] Mcculloch | A logical calculus of ideas immanent in nervous activity[END_REF] but became really popular but only after theoretical and practical methods to train networks, mostly based on the backpropagation algorithm designed by Y.

Lecun, had been developed [START_REF] Lecun | Learning processes in an asymmetric threshold network[END_REF] or [START_REF] Becker | Improving the convergence of back-propagation learning with second-order methods[END_REF]. In the following years, Lecun introduced the convolutional networks (CNN) [START_REF] Lecun | Handwritten zip code recognition with multilayer networks[END_REF]. In 1990, he already used a five-layer network but at that time, it was not yet called a deep structure. The term deep network emerged in the noughties in the field of character recognition [START_REF] Ranzato | Unsupervised learning of invariant feature hierarchies with applications to object recognition[END_REF].

The complexity of the networks architecture systems is constantly increasing and with this complexity, the number of parameters and hyper parameters that have to be tuned during a learning phase. This implies to gather a large amount [79], ResNet 101 [START_REF] He | Deep residual learning for image recognition[END_REF], GoogLeNet [START_REF] Szegedy | Going deeper with convolutions[END_REF], AlexNet [START_REF] Krizhevsky | ImageNet classification with deep convolutional neural networks[END_REF], VGGNet [START_REF] Simonyan | Very deep convolutional networks for largescale image recognition[END_REF], HCCR-CNN12Layer [START_REF] Xiao | Building fast and compact convolutional neural networks for offline handwritten chinese character recognition[END_REF], PHOCNet [START_REF] Sudholt | PHOCNet : A deep convolutional neural network for word spotting in handwritten documents[END_REF], YOLOv2 [START_REF] Redmon | YOLO9000: Better, faster, stronger[END_REF], CaffeNet [START_REF] Jia | Caffe: Convolutional architecture for fast feature embedding[END_REF], LocNet [START_REF] Gidaris | Locnet: Improving localization accuracy for object detection[END_REF],

DeconvNet [START_REF] Noh | Learning deconvolution network for semantic segmentation[END_REF], DictNet [START_REF] Jaderberg | Synthetic data and artificial neural networks for natural scene text recognition[END_REF], LeNet [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF] or ConvNet [START_REF] Zeiler | Visualizing and understanding convolutional networks[END_REF], PixelCNN [START_REF] Bansal | Pixelnet: Representation of the pixels, by the pixels, and for the pixels[END_REF]. Because of these problems, the need for new strategies, the knowledge to be acquired were essentially problematic in the field of document analysis, alternative ways of using deep neural networks had to be explored. Today, mainly adaptations of already existing systems are performed or very basic architectures of deep methods are used. The approaches fall into two main categories: methods relying on transfer learning at different levels and proposal of methods involving the combination of one or several deep structures combined in complex architectures. Among the first category, the extraction of features that have proven to be efficient in some different problems dealing with image processing is the most frequent. The initial deep system, although it has been trained in an end to end fashion for solving another problem, has all the parameters already fixed. In fact, the system is seen as being made of two independent parts. The first part comprises of convolutional layers. It is considered as a feature extraction part whereas the second part corresponds to a classification part. The features that have been tuned for another problem are considered as "good" features, they are defined by the fixed weights in the left part. So this left part of the system is no longer modified. Besides, depending on the application, the classification part can take two aspects. Either the second part architecture is kept and parameters are learnt on the dataset available in the actual application or the second part is switched to another decision structure, for example a simple SVM. In this case, a learning step must be applied, as illustrated in Figure 2. Then come the architectures with a large number of layers used successfully in previous applications. Further more, not only is the architecture used but the weights fixed in a previous application serve as a foundation to initialize the new system to be trained. The learning is further processed with the available data specific to the actual problem to be solved. Thus, the weights are modified through some rounds of optimization of the new system. Then, the problem of over fitting is emphasized as the quantity of data is usually limited. The principle is illustrated in Figure 3.

The use of Deep Learning is evolving

The first studies based on deep neural network architectures, and specially on convolutional networks appeared quite a long time ago, if we refer to the computer science time scale. The use of such models is more recent in the domain of document analysis and recognition. However, it is important to note the very rapidly-increasing use of such models. This is examplified by the examination of two international conferences (2016, 2017).

According to the traditional features that were chosen according to the system developer's expertise. To benefit from the different levels of computation performed in the network, deep-features are extracted at different levels of the convolutional layers. It seems that the selection of these levels is handcrafted but not engineered during the learning phase. It is obvious that the process increases the quality of the results in a significant way. In those studies, one trend to still increase the evaluation rates, is to multiply the inputs to the CNN computing deep-features.

For example, a gray level image and the binary image are also fed to the network.

Then, if the features are no longer handcrafted, some handcrafted transforms are applied to the material to be studied. There is no machine learning in the process because the transforms do not belong to a family of transforms, they are not obtained varying a hyper parameter but they are here to bring some complementary information difficult to compute in a finite CNN (however deep) in which first layers are linear convolutional layers. The limitation of the linear character of the convolutional operations is one of the problems that are considered in the community of the deep theoretical researchers.

Many studies attempt to achieve some transfer learning. They use some architectures that happen to give some good results in "similar" applications and retrain them, either from scratch or using as initialization the weights obtained in a training phase of a previous application. This trend was confirmed in 19% of the papers presented at ICDAR 2017. It seems that in most cases several known architectures were chosen, but in the end the researchers' choice was essentially empirical. While in the early days, our community's choice went for either Zernike or Hu decomposition, now it is between Alexnet or VGG19 or any other architecture that we listed in previous section 4.2.

Finally, some other studies propose new architectures involving several deep structures or modifying the architecture of an already used network. Nowadays, these choices are only justified by the quality of their results on the specific applications. Based on these observations, we may safely state that some handcraft involvements remain present, but at a different level.

Comparing the content of ICPR2016 and ICDAR2017 theroretical papers provided an overview of evaluations on various applications.The overall impression was that the quality of the results is improving, even though it proves difficult to objectively appreciate those improvements. Then comparing results

in the framework of competitions may make more sense. We considered three different tasks: i) classifying medieval writing ii) extracting layout and iii) binarizing document image. In these three cases, competitions were maintained for several years on equivalent testing sets and similar competitions, which allowed for a more objective assessment of the evolution of the community.

First, let us compare the competition on the Classification of Medieval Handwritings in Latin Script that took place at the ICFHR2016 (International Conference on Frontiers of Handwriting Recognition) [START_REF] Cloppet | ICFHR2016 competition on the classification of medieval handwritings in latin script[END_REF] and ICDAR 2017 [START_REF] Cloppet | ICDAR 2017 competition on the classification of medieval handwritings in latin script[END_REF].

For each competition, seven and six systems were proposed respectively. In 2016, three of the seven systems relied on deep structures whereas the ratio was reversed in 2017 as four out of the six systems were relying on deep structures.

Even though several deep systems were proposed, the winner in 2016 based the system on some local handcrafted features. As can be seen in Figure 4 (left handside), there is little difference between the winner and the second partici-pant's results. The following year, the winner used a deep system based on the enhancement of the previous deep system, which improved its results. However, it is important to note that the second best competitor is still an "old" fashion system. We observe that the difference between the two best results has increased, as illustrated in Figure 4 (central part). For each deep system used in the competition, a reference deep system was used and empirically modified to adapt it to the data. In one case, the architecture of the network was chosen from some paper in arXiv, a recent but non-reviewed paper. In 2017, the competition comprised of a second task involving the classification of some images which were more difficult to process than those involved in the first task. The image contents were not as much homogeneous as those proposed in the first task but the training data was the same. The layout competition on recognition of document layout is an older competition that has been open in all ICDAR conferences since 2001. But, in 2017 [START_REF] Clausner | ICDAR2017 competition on recognition of documents with complex layouts RDCL[END_REF], no participant relied on a deep structure but used a multi-step procedure on rule-based decisions instead. Nevertheless, in the conference, one paper [START_REF] Tsutsui | A data driven approach for compound figure separation using convolutional neural networks[END_REF] segments document images to extract images and relies on a deep architecture. The last competition we studied are the DIBCO competitions that have been organized in recent years. However we only considered the last two competitions on either printed or handwritten historical documents. In the 2016 competition [START_REF] Pratikakis | Handwritten document image binarization contest (H-DIBCO[END_REF] 12 systems were proposed and none of them relied on a deep method. In 2017, the organizers [START_REF] Pratikakis | Proc. International Conference on Document Analysis and Recognition (ICDAR2017)[END_REF] received 26 participant systems. Seven of them only relied on a deep method. These belong to the machine learning methods whereas the other methods were more traditional. Results show that the seven methods were ranked in the top eight results. The first unsupervised method is ranked seven. This is illustrated in Figure 5.

In this section, we report the emerging of deep methods and the high quality of their associated results. All applications follow this trend, even though they can be used in various ways. These trends bring hope for the future.

Conclusion

After synthesing and examing the various steps of the community evolution, we may conclude that deep methods must not be opposed to other methods, and more specifically to heavily handcraft methods, for which everything is chosen by the system designer.

Hardware evolution, year after year, has led to increase both memory size and computation speed. The CPUs are more efficient and now GPU are necessary to handle the deep architecture working with very large databases. Then, from the analysis of the results, we can see a good synergy between hard and soft advances and this is good news for future developments. Besides, if human expertise was once turned towards the finding of features, it is obvious now that it has to turn to higher levels in systems design. The level of abstraction has increased. From initial values, the objects of interest are now more like operators and sets of operators. The functions are replaced by families of functions and parameters give way to hyper-parameters. However human expertise is still needed. Researchers must not worry about losing their jobs as there is much to be discovered. Databases cannot yet handle all the natural or man-made variability and human will always be intelligent enough to propose cases that mislead the machine as it is the case in generative adversarial machine learning.

Besides, tricks have to be found to adapt systems to low energy, to embed them in systems. Few works are tackling the problems of distributed resources. These points open up a large set of fascinating questions for future research.

Figure 1 :

 1 Figure1: synoptic of Chen approach[START_REF] Chen | Invariant Fourier-Wavelet descriptors for pattern recognition[END_REF]

  [START_REF] Turki | Text detection based on mser and cnn features[END_REF]. It is important to note that with these wavelet based approaches, all associated coefficients are linked to the projection of the image function on specific function families. Some properties of orthogonality among the couples of functions in the family render the properties of the coefficients more or less efficient. Most wavelet basis are chosen to optimize the number of coefficients to be retained. Indeed, what is important is the convergence speed of the truncated function model towards the initial image function. Mathematical theorems similar to

  of annotated data according to the problem to be solved. The availability of the ImageNet[START_REF] Deng | ImageNet: A largescale hierarchical image database[END_REF] database released by Stanford Vision Lab from 2009 and its regular updating process has made developments in the field possible. ImageNet contains more than 14 million images with manual annotations consistent with WordNet hierarchy. Then it is a very large image database and it enables a real training of the networks. Since 2010, an ImageNet Large Scale Visual Recognition Challenge (ILSVRC) is organized each year. The tasks are evolving but are always linked to classification of images and of objects in those images. In 2012, for the first time, deep neural networks were used by the participants. If the competition winner optimized 60 million of parameters [77], the old-style methods were still competitive [78]. From 2013 until today, most participants have used deep convolutional neural networks with architecture which are increasingly complex. In 2017 all participants used deep convolutional neural networks. As we write these lines, several deep CNN architectures have become popular. Such architectures may either be modified and integrated into various applications or embedded in much larger architectures. Those deep CNN architectures are widely used currently, as shown in the studies presented at the ICDAR2017 conference. The design of the process has become the important thing. Some CNN or ANN are designed involving several layers for a specific application. When architectures are new, they usually increase the complexity of the wohle system by combining some basic classical architectures. The most famous deep current classical architectures have been named as ResNet

  The term "deep learning" is associated with quite different studies. The global philosophy for using deep learning or deep approaches, is similar to that which prevailed with original ANN. Any multivariate function can be approximated by an ANN where the inputs are the variables and the outputs take the desired values. The number of parameters depends on the function to be approximated. The task of the architecture of neural networks is to provide the possibility to learn the function through available data. The input layer receives the image raw pixel values. Although the early development of ANN has been hindered by the lack of efficient learning algorithms, the number of hidden layers in ANN is in longer limited today because the back-propagation learning mode is still applicable. The explosion of computation time has been overcome by the availability of GPU that enables accelerating the learning process in a reasonable time. Within this context, the number of parameters to learn is tremendous and the number of labeled data involved in the learning process must be high, generally more important than what is available. This means researchers have to imagine strategies in order to artificially increase the number of annotated images in an automatic way. For this, they introduce transforms that they apply to the images available from the database. The choice of the transforms requires know-how in the field.

Figure 2 :

 2 Figure 2: The deep learning method uses features from a deep CNN. The initial system is on the first line in green and in brown is the new architecture trained on a new problem.

Figure 3 :

 3 Figure 3: A transfer learning process: in (a) a pre-trained method and in (b) the use of the same architecture and same initial weights to train on new samples

Figure 4 (

 4 right handside) illustrates the accuracy loss between the two datasets. One possible conclusion is that the deep systems have learnt too much.They overfit the learning database and lack generalization capability. This is obvious when one compares the outcomes obtained from the use of features built by experts on handwriting examination. Such features, for instance, model the materials from medieval documents scrutinized by paleographers.

Figure 4 :

 4 Figure 4: comparison of the results obtained in Clamm competitions in recent years

Figure 5 :

 5 Figure 5: comparison of the results obtained in DIBCO competitions in recent years

  to the proceedings of the 2016 International Conference on Pattern Recognition(ICPR2016), 61% of the total number of papers did not refer to deep architecture for the document processing domain alone. At the ICDAR 2017 (International Conference on Document Analysis and Recognition), this number was down to 34%. This means that most papers referred to deep architecture. This evolution is visible in all the application domains but, as we mentioned in our previous section, the deep concept is used in different ways according to the studies. Furthermore, deep concepts are used but we must mention that they are not developed in the same way since they are presented in conferences such as Neural Information Processing Systems (NIPS) or Computer Vision and Pattern Recognition (CVPR). Only 19% of the papers referring to deep systems presented at the ICDAR 2017 mentionned the architecture of deep features, which are automatically fixed through the learning phase taking place to solve a problem different from the one raised at the onset.The most typical example for such a context is the use of the ImageNet database instead of documents. The trend is to see in these features some objectivity with respect

September 21, 2018 Accepted Manuscript

Accepted Manuscript