Hilbert-Galton Board

Arvind Ayyer
email: arvind@math.iisc.ernet.in

Sanjay Ramassamy
email: sanjay.ramassamy@ens-lyon.fr

THE

Introduction

The Galton board is a mechanical device introduced by Galton [START_REF] Galton | Natural inheritance[END_REF] in order to illustrate the central limit theorem. Balls fall through an array of regularly placed obstacles into a row of bins. At each obstacle, a ball may go left or right with the same probability, so that the abscissa of the bin into which the ball falls has a binomial distribution, which approximates the normal distribution when the number of obstacles and bins is large. See Figure 1 for a small example. Forgetting about the mechanical obstacles, one can simply consider the Galton board as a Markov chain on configurations of balls inside bins, where the rate at which a ball falls into a given bin is a function of the position of the bin. We generalise this by considering arbitrary rates of falling inside each bin, and in addition a shift operation as follows. Consider a row of n bins, labelled from 1 to n from left to right. Balls fall into bin number i at rate x i for any 1 ≤ i ≤ n. At rate x 0 , a shift to the right occurs, which means that the following events take place simultaneously:

(1) the rightmost bin gets deleted ;

(2) every bin of index 1 ≤ i ≤ n -1 gets shifted to the right by one unit, thus becomes indexed by i + 1 ; (3) an empty new bin is added at position 1. When a bin gets shifted, the number of balls it contains remains unchanged. See Figure 2 for an example of this shift operation. We denote this Markov chain by Z (n) and call it the Hilbert-Galton board, as a reference to the parable of the Hilbert hotel (see [START_REF] Gamow | Infinity: Facts and Speculations of Science[END_REF]). This continuous-time Markov chain is irreducible and we compute its stationary distribution (Theorem 2.2). We show the existence of a natural Markov chain X (n) on triangular arrays which projects down to the Hilbert-Galton board and for which we can compute the stationary distribution (Theorem 2.3). We call X (n) the enriched Hilbert-Galton board. We also introduce a finite-ball projection of (a variant of) the Hilbert-Galton board. Let Z(n) be the Markov chain defined as the Hilbert-Galton board, with the only difference being that whenever a new bin is added during a shift operation, it arrives containing a single ball (rather than arriving empty). The Markov chain Y (n) is defined by looking at the evolution of the leftmost n balls in Z(n) . We call Y (n) the n-ball projection of the Hilbert-Galton board. One can reformulate it as follows. We consider configurations of n balls placed inside a row of bins such that no bin is empty. For any i ≥ 1, at rate x i-1 we add one ball to the left of the i'th bin and we delete the rightmost ball, so that the total number of balls remains constant. If i = 1, we need to create a new leftmost bin where we add the new ball. If the rightmost bin becomes empty after deletion of the rightmost ball, we delete the bin.

With this formulation, the n-ball projection of the Hilbert-Galton board can be seen as a modification of the infinite-bin model introduced by Foss and Konstantopoulos [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF], where the new balls were added to the left of the i'th ball, rather than to the left of the i'th bin1 . A special instance of the infinite-bin model had already appeared in work of Aldous and Pitman [START_REF] Aldous | The asymptotic speed and shape of a particle system[END_REF]. The infinite-bin model was initially defined to study a model of random directed acyclic graphs called the Barak-Erdős model [START_REF] Amnon | On the maximal number of strongly independent vertices in a random acyclic directed graph[END_REF], but in recent years it has received quite a bit of attention as an interacting particle system. Properties of interest have been the speed of the front (rate of creation of new leftmost bins) [FK03, MR16, AP83] and the existence of a grand coupling [CR17], which makes it a renewal process and allows perfect sampling of the stationary measure using coupling from the past [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF][START_REF] Foss | Stochastic sequences with a regenerative structure that may depend both on the future and on the past[END_REF]. The stationary probabilities for the infinite-bin model are rational functions of the rates x i , but there is currently no general formula for them. The spectrum of the Markov chain is not known either.

By contrast, the n-ball projection of the Hilbert-Galton board is much more tractable. Although it is irreversible, we derive formulas for the stationary probabilities (Theorem 2.4) as well as for the spectrum of the chain (Theorem 2.11). Perfect sampling using coupling from the past is also possible and we derive a formula for the grand coupling time (Proposition 2.10). We note in passing that all the Markov chains studied in this work are irreversible. Very few families of irreversible Markov chains are known for which stationary distributions and spectra can be explicitly computed. One such class is that of R-trivial Markov chains [START_REF] Ayyer | R-trivial monoids and Markov chains[END_REF]. For these, the representation theory of monoids can be used to obtain the stationary distribution, the spectrum and the mixing time. This has been used effectively for sampling linear extension for posets using promotion [START_REF] Ayyer | Combinatorial Markov chains on linear extensions[END_REF] and for understanding nonabelian sandpile models on trees [START_REF] Ayyer | Directed nonabelian sandpile models on trees[END_REF].

Organization of the paper. In Section 2 we introduce the notation for triangular arrays and use it to state and discuss our main results. We compute in Section 3 the stationary distribution for the Hilbert-Galton board using two methods: first via a bi-infinite stationary version of the Markov chain, and then using a projection from the enriched Hilbert-Galton board. Finally, in Section 4, we focus on the n-ball projection of the Hilbert-Galton board. We compute its stationary distribution, its spectrum and give a formula for its grand coupling time.

Statement and discussion of the results

2.1. The Hilbert-Galton board and its enrichment. Fix an integer n ≥ 1. The state space of the Hilbert-Galton board Z (n) is the set Z n ≥0 , i.e. the set all the n-tuples of nonnegative integers (c 1 , . . . , c n ). The integer c i is interpreted as the number of balls in the i'th bin. For any 0 ≤ j ≤ n, we define the map

U j : Z n ≥0 → Z n ≥0 as follows: for any c = (c 1 , . . . , c n ) ∈ Z n ≥0 , set U j (c) = (0, c 1 , . . . , c n-1 ) if j = 0, (c 1 , . . . , c j-1 , c j + 1, c j+1 , . . . , c n ) if 1 ≤ j ≤ n.
The Hilbert-Galton board Z (n) is defined to be the continuous-time Markov chain on Z n ≥0 , where an n-tuple c ∈ Z n ≥0 makes a transition to U j (c) at rate x j for any 0 ≤ j ≤ n. Unless otherwise stated, we will assume in the remainder of this article that x 0 > 0 and x 1 > 0. The general formula for the stationary probability of any state of Z (n) uses the notion of triangular arrays, which we now define. Definition 2.1. For any n ≥ 0, a triangular array of size n is a collection of nonnegative integers A = (A k,j ) 1≤j≤k≤n . We denote by A n the set of all triangular arrays of size n. By convention, there exists a single triangular array of size 0, denoted by .

We represent a triangular array by aligning each row to the left. For example, a triangular array A of size 3 is represented as

A 1,1 A 2,1 A 2,2 A 3,1 A 3,2 A 3,3
There are three natural ways to take partial sums of elements in a triangular array: horizontally, vertically or diagonally. For any integers 1 ≤ i ≤ n and for any array A ∈ A n , we define these sums,

h i (A) := i j=1 A i,j , v i (A) := n k=i A k,i , d i (A) := i j=1
A n-i+j,j .

(2.1) See Figure 3 for an illustration of the various sums in an array.

h 1 h 2 h 3 v 1 v 2 v 3 d 1 d 2 d 3 Figure 3.
An illustration of horizontal, vertical and diagonal sums in a triangular array of size 3.

For any n-tuple of nonnegative integers (c 1 , . . . , c n ), we define

H n (c 1 , . . . , c n ) := {A ∈ A n | h i (A) = c i ∀i ∈ [1, n]}
to be the set of triangular arrays of size n with prescribed row sums.

Recall that for any nonnegative integers m 1 , . . . , m k , if we write

m = m 1 + • • • + m k , then the multinomial coefficient associated with the k-tuple (m 1 , . . . , m k ) is defined by m m 1 , . . . , m k := m! k i=1
m i ! Given a vector x = (x 0 , . . . , x n ) of nonnegative reals such that x 0 > 0, we define the weight function w x : A n → R ≥0 as follows. For any

A ∈ A n , (2.2) w x (A) := x n 0 n k=1 d k (A) A n-k+1,1 , . . . , A n,k x v k (A) k y d k (A)+1 k , where y k := x 0 + x 1 + • • • + x k .
By an abuse of notation, if the vector x has more than n + 1 elements, we can still define the function w x on A n by restricting the vector x to its first n + 1 elements. By convention, when n = 0, we have w x ( ) = 1. Using this notation, we can now express the stationary probabilities for the Hilbert-Galton board.

Theorem 2.2. Fix n ≥ 1. Then the Hilbert-Galton board Z (n) is an irreducible positive recurrent Markov chain and the stationary probability of any state

(c 1 , . . . , c n ) ∈ Z n ≥0 is (2.3) π Z (n) (c 1 , . . . , c n ) = A∈Hn(c 1 ,...,cn) w x (A).
More generally, for any 1 ≤ ≤ n, the stationary probability that the i'th bin contains exactly c i balls for 1 ≤ i ≤ is given by

(2.4) π Z (n) (c 1 , . . . , c ) = A∈H (c 1 ,...,c ) w x (A).
Since the stationary probabilities for Z (n) are expressed as sums over triangular arrays, it is natural to ask for the existence of an enriched Markov chain on triangular arrays which would project down to the Hilbert-Galton board. It turns out that such a Markov chain on A n indeed exists.

We call this the enriched Hilbert-Galton board and denote it by X (n) . It acts on A n as follows. For any A = (A k,j ) 1≤j≤k≤n ∈ A n , there are n + 1 transitions out of A:

A -→                                                  0 A 1,1 0 A 2,1 A 2,2 0 . . . . . . . . . . . . A n-1,1 A n-1,2 . . . A n-1,n-1 0, with rate x 0 , A 1,1 A 2,1 A 2,2 . . . . . . A i,1 . . . . . . A i,i + 1 . . . . . . A n,1 . . . . . . . . . A n,n .
with rate x i for 1 ≤ i ≤ n.

We have the following result for the chain X (n) .

Theorem 2.3. Fix n ≥ 1 and assume that x i > 0 for all 0 ≤ i ≤ n. Then the Markov chain X (n) is irreducible and positive recurrent.

Moreover, for any A ∈ A n the stationary probability of A is given by

(2.5) π X (n) (A) = w x (A).
Furthermore, defining the map

p n : A ∈ A n → (h 1 (A), . . . , h n (A)) ∈ Z n ≥0 , the projection p n (X (n)
) is a Markov chain with the same law as Z (n) .

Theorem 2.2 follows immediately as a corollary of Theorem 2.3. The proofs of these results are given in Section 3.

2.2. The finite-ball projection. We now move on to the n-ball projection of the Hilbert-Galton board. For any n ≥ 1, the state space of Y (n) is the set C n of all compositions of the integer n, i.e the set of all -tuples (c 1 , . . . , c ) of positive integers, with 1 ≤ ≤ n. The integer is called the length of the composition (c 1 , . . . , c ). It is well-known that #C n = 2 n-1 . For any integer 0 ≤ j ≤ n -1, define the map

T j : C n → C n as follows: for any composition c = (c 1 , . . . , c ) ∈ C n , we set T j (c) =      (1, c 1 , . . . , c -1 , c -1) if j = 0, (c 1 , . . . , c j-1 , c j + 1, c j+1 , . . . , c -1 , c -1) if 1 ≤ j ≤ -1, c if j ≥ ,
where the last part should be deleted in the first two cases if c = 1. The chain Y (n) (t) is defined as the continuous-time Markov chain on C n , where a composition c ∈ C n makes a transition to T j (c) at rate x j for any 0 ≤ j ≤ n -1. From the stationary distribution of Z (n) one can deduce the stationary distribution of Y (n) .

Theorem 2.4. The n-ball projection of the Hilbert-Galton board Y (n) is irreducible. Furthermore, fix c = (c 1 , . . . , c ) ∈ C n and set γ i = c i -1 for any 1 ≤ i ≤ . Then we have the following two equivalent expressions for the stationary probability of c for Y (n) :

π Y (n) (c) = A∈H -1 (γ 1 ,...,γ -1 ) w x (A) - γ -1 s=0 A∈H (γ 1 ,...,γ -1 ,s) w x (A) (2.6) = ∞ s=γ A∈H (γ 1 ,...,γ -1 ,s) w x (A) (2.7)
In formula (2.6), there are a finite number of terms, but some are present with a minus sign. In formula (2.7) all terms have positive coefficients, but there are an infinite number of terms. In this case too, it is possible to construct a Markov chain on triangular arrays which projects down to Y (n) . The enriched chain is similar to X (n) with a result similar to that of Theorem 2.3, but the case analysis is a little more complicated.

Let us illustrate the computation of the stationary distribution of Y (n) by an example.

Example 2.5. Consider the composition c = (2, 3). In this case, = 2, γ 1 = 1 and γ 2 = 2. Let us compute π Y (5) (c) using formula (2.6). The first sum is over a single element, the array of size 1 made up of the number 1. The second sum runs over the following three arrays of size 2:

1 0 0 , 1 1 0 , 1 0 1 . Hence π Y (n) (2, 3) = x 0 x 1 y 2 1 - x 2 0 x 1 y 1 y 2 2 - x 2 0 x 2 1 y 2 1 y 2 2 -2 x 2 0 x 1 x 2 y 1 y 3 2 = x 0 x 1 (x 3 1 + x 0 x 2 1 + 3x 2 1 x 2 + 3x 1 x 2 2 + 2x 0 x 1 x 2 + x 3 2 + 3x 0 x 2 2 ) y 2 1 y 3 2 .
One can deduce from the stationary distributions of the chains Z (n) and Y (n) a series of properties of the n-ball projection of the Hilbert-Galton board. Since Y (n) is a finite state chain, the stationary probabilities are multivariate rational functions of the indeterminates x 1 , . . . , x n . We define the partition function Z(Y (n) ) to be the least common multiple of the denominators in the stationary probabilities. Then we have the following results.

Corollary 2.6. The partition function of the n-ball projection of the Hilbert-Galton board is given by

Z(Y (n) ) = n-1 k=1 y n-k k .
One can also compute the stationary distribution for Y (n) of the number of balls in the leftmost bin.

Corollary 2.7. For the n-ball projection of the Hilbert-Galton board Y (n) , the probability that the first bin contains j balls at stationarity is given by

         x 0 x j-1 1 y j 1 if j < n, x 1 y 1 n-1 if j = n.
As a last application of Theorem 2.4, we identify some instances when the stationary probability is given by a single monomial. For any α ≥ 1 and ≥ 2, denote by c (α) the composition of length , whose first part equals α and whose other parts are all equal to 1. For example, c 3 (5) = (5, 1, 1). Then the following holds.

Corollary 2.8.

(1) For any α ≥ 1 and ≥ 2, we have

π Y (n) (c (α)) = x -1 0 x α-1 1 y α -1 -2 k=1 y k .
(2) When x 2 = • • • = x n-1 = 0, the stationary probability of a composition (c 1 , . . . , c ) only depends on n and and is given by

x -1 0 x n- 1 y n-1 1 .
We will prove Corollary 2.6 in Section 4. Corollary 2.7 easily follows from the coupling of Y (n) with Z (n) . Corollary 2.8 follows from a careful but elementary analysis of formula (2.6). We omit the proofs of the last two corollaries.

Given a sequence of transitions, the grand coupling time associated with this sequence is defined to be the first time that the 2 n-1 copies of the Markov chain Y (n) starting from all the possible states and evolving according to that sequence of transitions collapse to a single state. Starting the n-ball projection of the Hilbert-Galton board from any state and applying transition T 0 n times produces the state (1, . . . , 1). Because of the existence of these coupling events when applying the transitions T j , it is possible to sample exactly from the stationary distribution π Y (n) using Propp and Wilson's coupling from the past technique [START_REF] Gary | Exact sampling with coupled Markov chains and applications to statistical mechanics[END_REF]. Given a sequence (u i ) i≥1 of nonnegative integers, one can naturally associate the sequence of transitions (

T u i ) i≥1 on Y (n) .
Example 2.9. Take n = 3 and the sequence (u i ) i≥1 to be 1, 2, 0, 1, . . .. Then here is how the four possible Markov chains starting from the four possible initial states behave when they use (u i ) i≥1 as a source of randomness.

T 1 T 2 T 0 T 1 (3) → (3) → (3) → (1, 2) → (2, 1) (2, 1) → (3) → (3) → (1, 2) → (2, 1) (1, 2) → (2, 1) → (2, 1) → (1, 2) → (2, 1) (1, 1, 1) → (2, 1) → (2, 1) → (1, 2) → (2, 1)
Hence, the grand coupling time associated with the sequence

(u i ) is τ = 3.
It is not hard to see that the coupling time is linear in n in expectation, and hence logarithmic in the number of states of the chain. Indeed, the coupling time is at least (resp. at most) equal to the time needed to have n -1 transitions of any type (resp. of type 0 or 1) in the chain. We go further and provide a way to compute exactly the grand coupling time associated with a given sequence of transitions. For any i ≥ 1, we say that an element u i of the sequence is ineffective if u i ≥ 2 and there are at most u i -2 zeros to the left of u i . All the other elements of the sequence are called effective. Then the following holds.

Proposition 2.10. The grand coupling time τ associated to a sequence (u i ) i≥1 is the position of the (n-1)'th effective element in the sequence.

One last remarkable property of the n-ball projection of the Hilbert-Galton board is that one can compute its full spectrum. Let M n be the (column-stochastic) generator of Y (n) . Then we have the following result.

Theorem 2.11. For any 1 ≤ j ≤ n -1, -y j appears as an eigenvalue of M n exactly n-1 j times. In addition, 0 is the Perron eigenvalue.

Remark 2.12. In the course of the proof of Theorem 2.11, we will prove that for any n ≥ 3, the matrix M n is not diagonalizable and we will provide 2 n-2 independent eigenvectors of M n .

Example 2.13. In the ordered basis {(1, 1, 1), (1, 2), (2, 1), (3)}, the transition matrix for the Y (3) is given by

M 3 =     -x 1 -x 2 x 0 0 0 x 2 -x 0 -x 1 x 0 x 0 x 1 x 1 -x 0 -x 1 0 0 0 x 1 -x 0     ,
and the eigenvalues of M 3 are 0, -x 0 -x 1 , -x 0 -x 1 and -x 0 -x 1 -x 2 , in agreement with Theorem 2.11.

3. The Hilbert-Galton board Z (n) and its enrichment X (n) In this section we provide two proofs of Theorem 2.2. The first one is more probabilistic and uses a coupling of the Hilbert-Galton board with a bi-infinite stationary version of the process. The second one is more combinatorial and relies on the proof of Theorem 2.3 giving the stationary distribution of the enriched Hilbert-Galton board which projects down to the Hilbert-Galton board.

3.1. Coupling with a bi-infinite stationary version. We start by proving the irreducibility and positive recurrence of the Hilbert-Galton board.

Lemma 3.1. The Markov chain Z (n) is irreducible and positive recurrent.

Proof. Starting from any state c ∈ Z n ≥0 , one can get to any given state c = (c 1 , . . . , c n ) by applying the following sequence of transitions of type U 0 and U 1 , which have positive probability since x 0 > 0 and x 1 > 0: apply U 0 followed by c n times U 1 then U 0 followed by c n-1 times U 1 , etc, until U 0 followed by c 1 times U 1 . Thus Z (n) is irreducible.

Let c e = (0, . . . , 0) be the state with all the bins empty. We will show that the return time to c e has finite expectation. Assume that Z (n) (0) = c e and set

τ e = inf t ≥ 0 | Z (n) (t) = c e .
Then the return time to c e is given by

R e = inf t ≥ τ e | Z (n) (t) = c e .
For any integer k ≥ 1, let E k be the event that between times k -1 and k, a single transition U 1 followed by n transitions U 0 have occurred and no other transition has occurred. Then all the events E k have a common probability denoted by η. Since x 0 and x 1 are positive, we have η > 0. Furthermore,

0 ≤ R e ≤ min {k ≥ 1 | E k is realized} .
Since R e is dominated by a geometric random variable, it has finite expectation, which implies that Z (n) is positive recurrent.

We first provide a proof of Theorem 2.2 based on a coupling of Z (n) with an bi-infinite stationary version Ẑ(n) . Consider the following n + 1 independent Poisson point processes on the real line: for any 0 ≤ j ≤ n, let Q j be a Poisson point process of intensity x j . On the one hand, one can use the restrictions of these Poisson point processes to R ≥0 to define the Markov chain (Z (n) (t)) t≥0 : Z (n) (0) is distributed according to some initial probability distribution, and at every time t > 0 belonging to some Q j with 0 ≤ j ≤ n, a transition U j occurs. The Poisson point process Q j corresponds to the times at which a ball falls into bin number j (resp. a shift occurs) if 1 ≤ j ≤ n (resp. if j = 0). On the other hand, we use the Poisson point processes on the whole line to define the process ( Ẑ(n) (t)) t∈R as follows. Fix t ∈ R, set τ 0 (t) = t and define by induction on 1

≤ i ≤ n τ i (t) := sup{Q 0 ∩ (-∞, τ i-1 (t))}.
The sequence (τ i (t)) 1≤i≤n corresponds the last n shift times before time t. Set also for any 1 ≤ i ≤ n and 1 ≤ k ≤ n -i + 1

(3.1) B i,k (t) = #(Q k ∩ (τ i (t), τ i-1 (t)))
The integer B i,k (t) represents the number of balls that fall between the i'th shift before time t and the (i -1)'th shift before time t in the bin that is at that time at position k. We then set

( Ẑ(n) (t)) := ( Ẑ(n) 1 (t), . . . , Ẑ(n) n (t))
, where for any 1 ≤ i ≤ n,

(3.2) Ẑ(n) i (t) := i j=1 B i+1-j,j (t).
Lemma 3.2. For any t ∈ R, the random variable

Ẑ(n) (t) is distributed according to the stationary distribution π Z (n) of Z (n) . Proof. If t ≥ 0 is such that (3.3) #(Q 0 ∩ (0, t)) ≥ n
this means that at least n shifts have occurred between time 0 and time t thus the state Z (n) (t) can be reconstructed only from the knowledge of the realization of the Poisson point processes between times 0 and t (not requiring any knowledge of the state at time 0), exactly in the same way that Ẑ(n) (t) was defined. Since the processes ( Ẑ(n) (t)) t∈R and (Z (n) (t)) t≥0 are coupled by the use of the same Poisson point processes for their definition, this means that if t ≥ 0 is such that condition (3.3) is satisfied, then Z (n) (t) = Ẑ(n) (t) a.s. So for any t ≥ 0, (3.4) P(Z (n) (t) = Ẑ(n) (t)) ≤ P(#(Q 0 ∩ (0, t)) < n). Since x 0 > 0, the right-hand side of (3.4) tends to zero as t goes to infinity. As a consequence of Lemma 3.1, the distribution of Z (n) (t) converges to its stationary distribution π Z (n) , thus the distribution of Ẑ(n) (t) converges to π Z (n) too. We conclude from the fact that the distribution of Ẑ(n) (t) is the same for every t ∈ R because the distributions of the Poisson point processes used to define Ẑ(n) (t) are invariant by translation. Now we can use the bi-infinite stationary process Ẑ(n) to derive a formula for the distribution π Z (n) .

Proof of Theorem 2.2. In this proof we set t = 0 and to simplify notation we will write simply τ i and B i,k instead of τ i (0) and B i,k (0) respectively. Fix c = (c 1 , . . . , c n ) ∈ Z n ≥0 and 1 ≤ ≤ n. By the definition (3.2) of Ẑ(n) (0), for any 1 ≤ i ≤ n,

P( Ẑ(n) i (0) = c i ) = (A i,1 ,...,A i,i )∈Z i ≥0 A i,1 +•••+A i,i =c i P(B i+1-j,j = A i,j for all 1 ≤ j ≤ i).
More generally, we can express the probability of a distribution of balls in the leftmost bins in terms of triangular arrays as

(3.5) P( Ẑ(n) i (0) = c i for all 1 ≤ i ≤ ) = A∈H (c 1 ,...,c ) P(B i+1-j,j = A i,j for all (j, i) such that 1 ≤ j ≤ i ≤ ).
Set t i := τ i-1 -τ i for all 1 ≤ i ≤ n. Conditioned on the value of the τ i 's, the random variables (B i,k ) are independent and B i,k is distributed like a Poisson random variable of parameter t i x k . We can compute the summand of the right-hand side of (3.5) conditionally on Q 0 , ie conditioned on the t i 's by the formula

P(B i+1-j,j = A i,j for all (j, i) such that 1 ≤ j ≤ i ≤ | Q 0 ) = i=1 i j=1
e -t i+1-j x j (t i+1-j x j ) A i,j A i,j ! Since the t i 's are iid exponential random variables with rate parameter x 0 , we deduce that

P(B i+1-j,j = A i,j for all (j, i) such that 1 ≤ j ≤ i ≤ ) = (t 1 ,...t )∈R ≥0 i=1 e -x 0 t i x 0 dt i i j=1 e -t i+1-j x j (t i+1-j x j ) A i,j A i,j ! = x 0 j=1 x v j (A) j (t 1 ,...t )∈R ≥0 i=1 e -y +1-i t i t d +1-i (A) i -i+1 j=1 A i-1+j,j ! dt i = x 0 j=1 x v j (A) j i=1 t i ∈R ≥0 e -y +1-i t i t d +1-i (A) i -i+1 j=1 A i-1+j,j ! dt i = x 0 j=1 x v j (A) j i=1 1 y 1+d +1-i (A) +1-i d +1-i (A)! -i+1 j=1 A i-1+j,j ! = w x (A).
Since the distribution of Ẑ(n) (0) is π Z (n) by Lemma 3.2, this concludes the proof.

The enriched Hilbert-Galton board.

In this subsection we will assume that x i > 0 for all 0 ≤ i ≤ n. We now provide an alternate proof of Theorem 2.2 by obtaining it as a corollary of Theorem 2.3 on the stationary distribution of the enriched Hilbert-Galton board X (n) . We begin by showing irreducibility and positive recurrence.

Lemma 3.3. The Markov chain X (n) on A n is irreducible and positive recurrent.

Proof. Starting from any array A , one can reach an arbitrary array A by the following sequence of transitions which all have positive probability: first make a transition of type 0 followed by A n,1 transitions of type 1, then make a transition of type 0 followed by A n-1,1 transitions of type 1 and A n,2 transitions of type 2. In this way continue filling up the array diagonally until one arrives at A. Therefore, X (n) is irreducible. By the same argument as in the proof of Lemma 3.1, if A e denotes the array filled with zeros, the expected return time to A e is finite and hence the chain X (n) is positive recurrent. Now we prove that the Markov chain X (n) indeed projects down to the Markov chain Z (n) . Lemma 3.4. Defining the map

p n : A ∈ A n → (h 1 (A), . . . , h n (A)) ∈ Z n
≥0 , the projection p n (X (n) ) is a Markov chain with the same law as Z (n) .

Proof. Fix A ∈ A n . Then for 1 ≤ i ≤ n, at rate x i the integer h i (A) increases by 1 and at rate x 0 the n-tuple (h 1 (A), . . . , h n (A)) gets turned into (0, h 1 (A), . . . , h n-1 (A)). This is exactly the law of Z (n) .

Remark 3.5. The numbers A i,j have the following interpretation in terms of balls and bins. Call an epoch the time between two consecutive shifts and count the epochs backwards: the current epoch is indexed by 1, the epoch just before the current epoch is indexed by 2, etc. Then A i,i+1-j is the number of balls that are in the bin currently indexed by i which arrived during epoch j. In the notation of the previous subsection, we have A i,j = B i+1-j,j .

We will need the following identity to complete the proof of Theorem 2.3. Lemma 3.6. Let δ 1 , . . . , δ n-1 be n -1 nonnegative integers. Then

(α 1 ,...,αn)∈Z n ≥0 n-1 k=1 δ k + α k+1 α k+1 n k=1 x k y k α k = y δ n-1 +1 n x 0 y δ 1 1 n-1 k=2 y δ k-1 -δ k k .
Proof. From the generalized binomial theorem, we have that for any real number δ and for any real number 0 ≤ z < 1,

∞ α=0 δ + α α z α = (1 -z) -δ-1 .
The sum on the left-hand side splits into n such sums (with δ = 0 when k = 1). Recalling that y k-1 + x k = y k and rearranging the terms gives the right-hand side.

Lemma 3.7. For any n ≥ 1, the measure

w x : A n → R ≥0 is a proba- bility measure, that is A∈An w x (A) = 1.
Proof. The proof proceeds by induction. When n = 1, it is easy to check that A∈A 1 w x (A) = 1 because it is a geometric series. Now we want to perform the sum for general n. Let A denote the triangular array A restricted to the first n -1 rows. We split the sum into two parts,

A ∈A n-1 (A n,1 ,...,An,n)∈Z n ≥0 w x (A) = x n 0 y 1 • • • y n A ∈A n-1 (A n,1 ,...,An,n)∈Z n ≥0 n k=1 d k (A) A n-k+1,1 , . . . , A n,k x v k (A) k y d k (A) k .
After rewriting the multinomial coefficient and shifting the indices, the sum above becomes

x n 0 y 1 • • • y n A ∈A n-1 n-1 k=1 d k (A ) A n-k,1 , . . . , A n-1,k x v k (A ) k y d k (A ) k+1 × (A n,1 ,...,An,n)∈Z n ≥0 n-1 k=1 d k (A ) + A n,k+1 A n,k+1 n k=1 x k y k A n,k
.

We are now in a position to use Lemma 3.6 to evaluate the inner sum, for which we obtain

y d n-1 (A )+1 n x 0 y d 1 (A ) 1 n-1 k=2 y d k-1 (A )-d k (A ) k .
After combining these factors with the outer sum, we obtain exactly A ∈A n-1 w x (A ), which by the induction assumption is 1, completing the proof.

Proof of Theorem 2.3. Since X (n) is irreducible and positively recurrent by Lemma 3.3, the stationary distribution is unique. Furthermore, w x is a probability distribution by Lemma 3.7. It is therefore sufficient to verify that w x (A) satisfies the master equation, that is to say, the total outgoing rate from A is the same as the total incoming rate into A. Fix n ≥ 1. Since A has size n, the total outgoing rate is always y n w x (A). There are two cases depending on the value of d n (A).

Case I:

d n (A) = 0 : Therefore A 1,1 = • • • = A n,n = 0.
The only incoming transitions into A are with rate x 0 from the set (3.6)

S(A) =            A 2,1 A 3,1 A 3,2 . . . . . . . . . A n,1 A n,2 . . . A n,n-1 α 1 α 2 . . . . . . α n : (α 1 , . . . , α n ) ∈ Z n ≥0            .
Let A ∈ A n-1 be the array obtained from A by deleting its top diagonal:

A 2,1 A 3,1 A 3,2 . . . . . . . . . A n,1 A n,2 . . . A n,n-1
Then by the same computation as in the proof of Lemma 3.7, we have Ã∈S(A) w x ( Ã) = w x (A ). Since the top diagonal of A contains only 0's, we also have w x (A) = w x (A ) × x 0 /y n . So finally we have

x 0 Ã∈S(A) w x ( Ã) = y n w x (A),
which is exactly the master equation for A.

Case II:

d n (A) > 0 : Let I(A) = {i ∈ [1, n] : A i,i > 0}.
Let A (i) be the same array as A, with the sole difference being that A i,i is replaced by A i,i -1. Note that A (i) makes a transition to A with rate x i for each i ∈ I(A). Using the definition (2.2) of w x (A), it is clear that

x i w x (A (i) ) = y n w x (A) A i,i d n (A)
.

Summing over all i ∈ I and using the fact that i∈I(A) A i,i = d n (A) gives the master equation at A.

Theorem 2.2 follows as a corollary of Theorem 2.3 in the case when x i > 0 for all i ≥ 0. Since the master equation for the chain Z (n) is rational in the x i 's, one can actually pass to the limit when x i goes to 0 for all i ≥ 2 and recover Theorem 2.2 in full generality. Proof. Starting from any composition c ∈ C n , one gets to the composition c = (c 1 , . . . , c ) ∈ C n by the following sequence of transitions, each having positive probability: T 0 followed by c -1 times T 1 , then T 0 followed by c -1 -1 times T 1 , etc, until T 0 followed by c 1 -1 times T 1 .

One can couple Y (n) with Z (n) as follows. Define the maps

f n :(c 1 , . . . , c n ) ∈ Z n ≥0 → (c 1 + 1, . . . , c n + 1) ∈ Z n >0 n :(c 1 , . . . , c n ) ∈ Z n >0 → min {1 ≤ i ≤ n | c 1 + • • • + c i ≥ n} g n :(c 1 , . . . , c n ) ∈ Z n >0 → (c 1 , . . . , c n(c)-1 , n -(c 1 + • • • + c n(c)-1 ))
, where in the last definition c was shorthand for (c 1 , . . . , c n ). Let Z(n) be the pushforward of Z (n) by f n and Ỹ (n) be the pushforward of Z(n) by g n . Then Ỹ (n) has the same law as Y (n) , so that one can use Theorem 2.2 to study Y (n) . In particular, the stationary distribution π Y (n) is obtained as a pushforward by g n • f n of the stationary distribution π Z (n) .

Proof of Theorem 2.4. Fix c = (γ 1 + 1, . . . , γ + 1) ∈ C n to be a composition of n of length . Then

π Y (n) (c) = π Y (n) (Y (n) 1 = γ 1 + 1, . . . , Y (n) = γ + 1) (4.1) = π Z (n) (Z (n) 1 = γ 1 , . . . , Z (n) -1 = γ -1 , Z (n) ≥ γ ). (4.2) Writing π Y (n) (c) = π Z (n) (Z (n) 1 = γ 1 , . . . , Z (n) -1 = γ -1 ) - γ -1 s=0 π Z (n) (Z (n) 1 = γ 1 , . . . , Z (n) -1 = γ -1 , Z (n) = s)
and applying formula (2.4), we obtain (2.6). Writing

π Y (n) (c) = ∞ s=γ l π Z (n) (Z (n) 1 = γ 1 , . . . , Z (n)
-1 = γ -1 , Z (n) = s)
and applying formula (2.4), we obtain (2.7).

We now prove the formula for the partition function.

Proof of Corollary 2.6. Fix a composition c = (γ 1 + 1, . . . , γ + 1) ∈ C n and consider the formula for π Y (n) (c) given by formula (2.6). For any 1 ≤ k ≤ ≤ n, denote by µ k (c) the maximal power with which y k appears in the denominator of any of the monomials in the formula for π Y (n) (c). We will show that µ k (c) ≤ n -k. If k = = n, then this means that the composition c is equal to c n (1) and by Corollary 2.8, we have µ n (c) = 0. Assume next that k = < n. Then y does not appear in a monomial in the first sum, thus

µ (c) ≤ 1 + max 0≤s≤γ -1 max A∈H (γ 1 ,...,γ -1 ,s) d k (A) ≤ 1 + γ -1 + -1 j=1 γ -j ≤ n -. Finally, if 1 ≤ k ≤ -1, then k (c) ≤ 1 + max max A∈H -1 (γ 1 ,...,γ -1 ) d k (A), max 0≤s≤γ -1 max A∈H (γ 1 ,...,γ -1 ,s) d k (A) ≤ 1 + max k j=1 γ -j , γ -1 + k-1 j=1 γ -j ≤ 1 + n - ≤ n -k.
On the other hand, by Corollary 2.8, for any 1 ≤ k ≤ n -1, c k+1 (n -k) is a composition of n whose stationary probability consists of a single monomial, and the power of y k in the denominator is equal to n -k. We conclude that the power of y k in the least common multiple of the denominators of the stationary probabilities of compositions of length n is equal to n -k.

Remark 4.2. By analyzing the expression for µ k (c), , one can show that if c = (γ 1 + 1, . . . , γ + 1) ∈ C n :

• for any 1 ≤ k ≤ -1, µ k (c) = max (γ -k + 1, γ ) + k-1 j=1 γ -j • when k = , µ (c) = 0 if γ = 0 n - if γ > 0 .
4.2. Grand coupling time. In this subsection we prove Proposition 2.10 giving an expression for the grand coupling time associated with a given sequence of transitions.

Proof of Proposition 2.10. We say a bin is recent (resp. ancient) if it is the leftmost bin of the configuration at time 0 or if it is created after time 0 (resp. if it already existed at time 0, but was not the leftmost bin at that time). It then follows that effective (resp. ineffective) elements of the sequence are those that create a ball in a recent (resp. ancient) bin. By looking at the two initial configurations (n) and (1, n -1), it is easy to see that one needs exactly n -1 transitions to couple them. Moreover, for any initial configuration, the leftmost bin contains at least one ball. Therefore, once one knows how n -1 balls have been added in recent bins, one knows the entire configuration, regardless of what the initial configuration was. So n -1 effective elements are enough to couple any pair of initial configurations.

4.3. Spectrum. The main idea of the proof of Theorem 2.11 is that M n , when written in a different basis, becomes block upper-triangular, with one of its diagonal blocks being a diagonal matrix and the other one being M n-1 . In order to observe this, we first need to define an order on the elements of C n making it compatible with that on C n-1 . We define the maps L and R from C n to C n+1 for any n ≥ 1 as follows. The maps L and R both add a single ball to the right of the configuration, either in a new rightmost bin or in the current rightmost bin. We also define the map D : C n → C n-1 which erases the rightmost ball: for any

c = (c 1 , . . . , c ) ∈ C n , D(c) := (c 1 , . . . , c -1) if c ≥ 2 (c 1 , . . . , c -1 ) if c = 1 .
We proceed by induction on n ≥ 1 to assign a rank to each composition in C n . We set s

(1)

1 := (1) and for any n ≥ 2 and 1 ≤ i ≤ 2 n-2 , we set s

(n) 2i-1 := L(s (n-1) i ) (4.3) s (n) 2i := R(s (n-1) i ) (4.4)
These compatibility relations can be illustrated by the rooted plane binary tree on Figure 4, where the order on C n can be read from left to right on the n'th row. By construction, we have for any n ≥ 2 and

(1)

(1, 1) (2) (1, 1, 1) (1, 2) (2, 1) (3)
L L R R L R
1 ≤ i ≤ 2 n-2 , (4.5) D(s (n) 2i-1 ) = D(s (n) 2i ) = s (n-1) i
Remark 4.3. It is not hard to show that this order on C n defined inductively is actually the lexicographic order on C n , where a composition c = (c 1 , . . . , c ) ∈ C n can be seen as a word of letters on the alphabet N equipped with its usual order.

We now define two bases on R Cn . The first one is the basis B n = (e(s (n) i )) 1≤i≤2 n-1 , where each basis vector is indexed by a composition. The second basis is B n = (f

(n) 1 , . . . , f (n) 2 n-2 , g (n) 1 , . . . , g (n)
2 n-2 ) where for any 1 ≤ i ≤ 2 n-2 , we define

f (n) i := e(s (n) 2i ) -e(s (n) 2i-1 ) (4.6) g (n) i := e(s (n) 2i-1 ) + e(s (n) 2i ) (4.7)
Let u n be the endomorphism of R Cn whose matrix in the basis B n is given by M n . Denote by M n the matrix of u n in the basis B n . Then we can find the eigenvalues of M n by induction on n, using the following result.

Lemma 4.4. For any n ≥ 2, write

M n = A n,1 A n,2 A n,3 A n,4 ,
where the blocks A n,i are all square matrices of size 2 n-2 . Then the following holds:

(1) A n,1 is a diagonal matrix, where for every 1 ≤ j ≤ n -1, the entry -y j appears exactly n-2 j-1 times as a diagonal element ; (2) A n,3 = 0 ;

(3) A n,4 = M n-1 .

Proof of Theorem 2.11. Assuming Lemma 4.4, we have that M n is a block upper triangular matrix. By induction, we know that eigenvalues of M n-1 are -y j with multiplicity n-2 j for any 1 ≤ j ≤ n -2, and 0 with multiplicity 1. Thus, we deduce that the eigenvalues of M n are -y j with multiplicity n-1 j for any 1 ≤ j ≤ n -1, and 0 with multiplicity 1. It also immediately follows from Lemma 4.4 that for any n ≥ 3, the matrix M n is not diagonalizable : we easily check that the matrix M 3 (see Example 2.13) is not diagonalizable and we conclude by induction, since M n appears as a block of the block triangular matrix M n+1 .

To complete the proof of the theorem, it remains to prove Lemma 4.4.

Proof of Lemma 4.4. Recall that the map T j : C n → C n is given for any 0 ≤ j ≤ n -1 by

T j (c) =     
(1, c 1 , . . . , c -1 , c -1) if j = 0, (c 1 , . . . , c j-1 , c j + 1, c j+1 , . . . , c -1 , c -1) if 1 ≤ j ≤ -1, c if j ≥ .

The action of endomorphism u n on the basis B n is given by (4.8) u n (e(s

(n) i )) = n-1 j=0
x j e(T j (s

(n) i )) -e(s (n) i )
for any 1 ≤ i ≤ 2 n-1 . Fix 1 ≤ i ≤ 2 n-2 . Denote by the length of the composition s (n)

2i . Then by construction, the composition s

(n)
2i-1 has length + 1. Pick 1 ≤ j ≤ n -1. The following equalities hold.

T j (s (n) 2i-1 ) = T j (s (n) 2i )
if j ≤ , (4.9)

T j (s (n) 2i-1 ) = s (n) 2i-1 if j ≥ + 1, (4.10) T j (s (n) 2i ) = s (n) 2i if j ≥ . (4.11)
Combining equations (4.8), (4.9), (4.10) and (4.11), we deduce that (4.12)

u n (f

(n) i ) = -y f (n) i . Thus for any 1 ≤ i ≤ 2 n-2 , f (n) i
is an eigenvector of u n , and the corresponding eigenvalue is -y , where is the length of the composition s (n) 2i . Using the map R as a length-preserving bijection from C n-1 to the subset s

(n) 2i 1≤i≤2 n-2
of compositions of n of even rank, we deduce the number of compositions of n of even rank that have length equals the number of compositions of n -1 that have length , which is well-known to be n-2 -1 . Statements 1 and 2 of the lemma follow.

Combining equations (4.8), (4.9), (4.10) and (4.11) again, we obtain that (4.13) u n (g

(n) i ) = -1 j=0
x j 2e(T j (s

(n) 2i )) -g (n) i + x f (n) i
It is not hard to see that for any 0 ≤ j ≤ -1, )), R(T j (s (n-1) i

)) .

If for any 0 ≤ j ≤ -1, we call τ j (i) the integer such that T j (s

(n-1) i ) = s (n-1)
τ j (i) , then 2e(T j (s i) . Thus u n (g

(n) 2i )) = g (n) τ j (i) ± f (n) τ j (
(n) i ) = -1 j=0 x j g (n) τ j (i) -g (n) i + -1 j=0 ±x j f (n) τ j (i) + x f (n) i
Observing that the matrix A n,4 is obtained by considering the projection of u n (g )) = -1 j=0

x j e(T j (s (n-1) i

)) -e(s

(n-1) i ) = -1 j=0
x j e(s (n-1)

τ j (i) )
) -e(s (n-1) i

) we conclude that statement 3 holds true.

As an immediate consequence of Theorem 2.11, we obtain the relaxation time and the spectral gap.

Corollary 4.5. The spectral gap of the chain is given by (x 0 + x 1 )/y n and the relaxation time is y n /(x 0 + x 1 ).

Figure 1 .

 1 Figure 1. An illustration of the Galton board, with obstacles marked by black dots.

Figure 2 .

 2 Figure 2. An example of the shift transition on Z (4) .

4.

  The n-ball projection of the Hilbert-Galton board 4.1. Stationary distribution. Lemma 4.1. The n-ball projection of the Hilbert-Galton board, Y (n) , is irreducible.

  For any c = (c 1 , . . . , c ) ∈ C n , L(c) := (c 1 , . . . , c , 1) R(c) := (c 1 , . . . , c + 1)

Figure 4 .

 4 Figure 4. Compatibility between the orders.

  0 ≤ j ≤ -1, T j (s (n) 2i ) ∈ L(T j (s (n-1) i

To be precise, this is actually the finite-dimensional projection of the infinite-bin model, which may involve configurations with infinitely many balls.

Acknowledgements

We thank Bastien Mallein for fruitful discussions. The first author was partially supported by the UGC Centre for Advanced Studies. The first author also acknowledges support from the Fondation Sciences Mathématiques de Paris for a visit to the Institut Henri Poincaré and from DST grant DST/INT/SWD/VR/P-01/2014. The second author acknowledges the support and hospitality of the Institut Henri Poincaré, where this work was initiated during the program on "Combinatorics and interactions", as well as the support of the Fondation Simone et Cino Del Duca.


Pavel Středa

Thibaut Jonckheere

Thierry Martin

Electron polarizability of crystalline solids in quantizing magnetic fields and topological gap numbers

Keywords: numbers: 73.43.-f, 73.43.Cd, 77.22.Ej

A theory of the static electron polarizability of crystals whose energy spectrum is modified by quantizing magnetic fields is presented. The polarizability is strongly affected by non-dissipative Hall currents induced by the presence of crossed electric and magnetic fields: these can even change its sign. Results are illustrated in detail for a two dimensional square lattice. The polarizability and the Hall conductivity are respectively linked to the two topological quantum numbers entering the so-called Diophantine equation. These numbers could in principle be detected in actual experiments.

The polarizability is usually presented as an important property of insulators [START_REF] Ashcroft | Solid State Physics[END_REF]. An electric field imposed between the plates of a capacitor penetrates into their interior, and charge redistribution is induced within the system. This effect is characterized by the polarizability: the ratio of induced dipole moments per unit volume and the local field. In metals this charge redistribution is non-uniform because of the charge mobility and the local electric field is non-uniform as well. In the particular case that the distribution of the atomic cores is not affected by the applied electric field, it is the electronic charge redistribution only which determines the polarizability of insulators as well as metals.

Crystalline solids have an energy spectrum composed of energy bands. They become insulators whenever the Fermi energy is located within an energy gap between these bands. Additional energy gaps can be opened by applying strong magnetic fields to two-dimensional (2D) as well as to three-dimensional crystals [START_REF] Hofstadter | [END_REF]3,4]: the energy spectrum of 2D crystals is separated in an integer number of subbands whenever the number of flux quanta contained in the unit cell corresponds to a rational number [START_REF] Hofstadter | [END_REF]. The number of electrons per subband is specified by two topological gap numbers, one of which has been linked to the Hall conductance [5]. The present work establishes that for electrons in a "strong" periodic potential subject to a magnetic field, the remaining gap number is directly linked to the polarizability. We thus limit our attention to the static electron polarizability and its dependence on the electron concentration, i.e. on the Fermi energy µ. This limitation allows to exclude dissipative processes from the consideration: no current flow is allowed along the applied electric field. For the sake of simplicity, an ensemble of spinless electrons at zero temperature is considered. We will also limit our treatment to "ideal" crystals with a rectangular unit cell of volume a z A 0 , where a z is the lattice constant along the ẑ-direction and A 0 ≡ a x a y is the area in the xŷ plane.

In the considered geometry, the magnetic field is applied along the ẑ-direction, parallel with capacitor plates as well as with the z-th crystallographic axis. The external field due to the voltage drop between capacitor plates is applied along the ŷ-direction. The system is assumed to be open along the x-direction, (i.e. periodic boundary conditions) allowing non-dissipative current flow. This condition allows the direct comparison of the polarizability with the topological gap numbers. Such condition could be realized in a Corbino geometry with cylindrical capacitor plates of large radius.

We start with the case of a vanishing magnetic field. Generally, electrons are not equally distributed over energy bands. The electron occupation s(0) i (µ) of the i-th band per volume a z A 0 obeys the sum rule a z A 0 N (µ) = i s(0) i (µ) ≡ s(0) (µ). Here N (µ) denotes the electron concentration (the integrated density of states). Whenever the Fermi energy is located within an energy gap, s(0) (µ) = s (s integer). The wave functions of each band are assumed to be of Bloch-like form (i.e. extended) along the x-direction while along the ŷ-direction we consider a Wannier-like form (i.e. localized). With this choice the mass-center positions of the electrons along the ŷdirection are well defined by the expectation values of the y-coordinate. Averaging over occupied states belonging to the i-th band gives an average value of the mass-center positions Y i (µ) . An electric field along the ŷ-direction, E y , leads to a redistribution of the electron charge, which can be characterized by the shifts of the mass-center positions ∆Y i (µ) . These shifts are controlled by the balance of the electric force and of the gradient force, due to the background crystalline potential, which acts in opposite direction to bring the electrons back into their equilibrium positions. Within linear response in E y , the latter is characterized by a force constant K i (µ), so that:

- s(0) i (µ) eE y -K i (µ) ∆Y i (µ) = 0 . (1)
The resulting static electron polarizability α (0) (µ) is given as follows

α (0) (µ) ≡ - e i ∆Y i (µ) a z A 0 E y = e 2 a z A 0 i s(0) i (µ) K i (µ) . (2)
The above expressions are applicable even in the case of a non-uniform electric field along the ŷ-direction if the charge redistribution does not affect the values of the force constants K i . Strictly speaking, for real metallic systems it might be a crude approximation.

Next, an external magnetic field splits the bands into subbands [START_REF] Hofstadter | [END_REF]3,4]. Because the geometry allows electrons to flow along the x-direction, the crossed electric E y and magnetic B fields give rise to a Hall current density j H . Consequently, an additional force -the Lorentz forceacts on the electron ensemble. The new balance condition along the ŷ-direction becomes:

-eN (µ) E y - B c j H - 1 a z A 0 i K i (µ) ∆Y i (µ) = 0 , (3)
where the index i now counts available sub-bands. The Hall current density has the standard form

j H = - e 2 h σ(µ) a z E y , (4)
where σ(µ) is dimensionless. Introducing s(µ) to express the mass-center shifts ∆Y i (µ) in the form given by Eq. ( 1), the force balance Eq. ( 3) becomes:

N (µ) = s(µ) a z A 0 + σ(µ) a z 2πl 2 B , (5)
where l B = c/(eB) is the magnetic length. The effect of a strong magnetic field on Bloch electrons is more pronounced in 2D systems, which motivates our choice of a crystal formed by 2D planes, perpendicular to the magnetic field, which are separated along the ẑdirection by a z . The lattice constant a z is large enough that electron transitions between planes are ruled out. We thus consider a single layer only: a 2D crystal with electron concentration a z N (µ). As was first noticed by Wannier [6] and recently proved by Kellendonk [7], the necessary condition for the appearance of an energy gap in such systems reads

N (µ) = s/(a z A 0 ) + σ/(a z 2πl 2 B )
, where s and σ are integers, often called topological gap numbers, and σ determines the value of the quantum Hall conductance [5]. The comparison of this so-called Diophantine equation with its general form Eq. ( 5) leads to the conclusion that s is related to the system polarizability.

The relation between polarizability and Hall current is now illustrated with a tight-binding model on a square lattice, A 0 = a 2 , assuming non-zero overlap between the nearest neighbor sites only. At zero magnetic field it gives a single energy band with cosine dispersion. The effect of the magnetic field is included with the Peierls substitution [START_REF] Hofstadter | [END_REF]8]. This model was first used to obtain the "Hofstadter butterfly" energy spectrum [START_REF] Hofstadter | [END_REF]. For rational magnetic fields, satisfying:

A 0 2πl 2 B = p q , q = 2i + 1 (6)
(where p and i are integers), the energy spectrum is composed of q sub-bands well separated by energy gaps for which topological gap numbers are uniquely defined [5,9]. Choosing the Landau gauge A ≡ (-By, 0, 0), the Hamiltonian of the system remains periodic in the xdirection. Zero-order wavefunctions of each row of atomic orbitals φ a (x -am, y -an) along the x-direction are thus of the following standard form:

Ψ (0) n,kx ( r) = m e ikxam φ a (x -am, y -an) , (7)
where k x is the wave number. The vector potential between atomic sites belonging to different rows differs by ∆A x = -Ba∆n, and the Peierls substitution suggests to shift k x entering the zero-field eigenenergies as follows:

k x → k x -2π p q n a , (8)
so that phase factors in the overlap integrals arise between orbitals of the neighboring rows. Assuming zeroorder eigenfunctions in the form of a linear combination of row-eigenfunctions, Eq. ( 7), the coefficients c n (k x ) have to satisfy the following Harper's equation [8,10]:

c n (k x ) 2 cos k x a -2π np q + E -E a ∆V + c n-1 (k x ) + c n+1 (k x ) = 0 , (9)
where E a is the energy of the atomic orbitals (chosen to be zero) and ∆V is the overlap strength (the zero field band width is 8∆V ). The modulus of the c n coefficients are periodic with a period q, but their amplitude differs by a phase β: c n+q = e iβ c n [11]. For a given β ∈ [0, 2π], Eq. (9) gives a system of q equations, and the c n (k x , β) are eigenvectors of a q×q matrix. The eigenvalues E β (k x ) give the q sub-bands, each of them composed of energy branches determined by the phase β, which are periodic in k x with period 2π/a. Because of the periodicity of the |c n (k x , β)|, it is natural to define Wannier-like functions, which are extended (localized) along the x (ŷ) direction:

w n,kx,β ( r) = +i λ=-i c n+λ (k x , β) Ψ (0) n+λ,kx ( r) . (10)
The average mass-center position in the ŷ-direction reads:

Y n,β (k x ) ≡ y|w n,β,kx ( r)| 2 dr = an + Y (B) β (k x ) , (11)
where

Y (B) β (k x ) = a +i λ=-i λ|c λ (k x , β)| 2 , (12)
which vanishes at zero magnetic field. (kx) (in units of the lattice constant) for the fraction p/q = 1/3, shown for β = 0 (down triangles), β = π/2 (circles) and β = π (up triangles). Empty (filled) symbols correspond to positive (negative) velocity along the x axis. The left and right sides show the magnetic edge states inside the energy gaps.

-0.4 -0.2 0 0.2 0.4 Y β (B) (k x ) E β (k x ) -3 -2 -1 0
The eigenvalue problem is mathematically equivalent to the one found for a weak periodic potential in a strong magnetic field [12], and leads to the same spectrum as a function of k x , except that the values of p and q are interchanged. However, the spectrum presented as a function of the mass center position differs substantially from that of the weak periodic potential. For the ratio p/q = 1/3, the energy spectrum is composed of three subbands, each of them formed by the branches obtained for all values of β. The spectrum is symmetric with respect to zero energy because of electron-hole symmetry. This is illustrated in Fig. 1, where only three values β = 0, π/2 and π are shown. The branches β = 0, π correspond to the subband edges, while β = π/2 characterizes the central branch. At the crystal edges, determined by the values n L and n R of the row index n, the natural condition that c nL-1 = c nR+1 = 0 leads to the appearance of edge states formed by contributions from each of the energy branches β. Two types of edge states appear, non-magnetic edge states and magnetic ones [8,13] which are responsible for the quantum Hall effect. The latter have opposite velocities at opposite edges, and are shown in Fig. 1 for p/q = 1/3. Note that in the thermodynamic limit, the mass-center positions of edge states can be identified with the edges of the physical system.

Next, we switch on E y , which shifts the position of the atomic orbitals. The force trying to return electrons back to their original positions is assumed to be linear in this shift, with a proportionality ("force") constant K ≡ m 0 Ω 2 0 , with a confinement frequency Ω 0 (m 0 is the free electron mass). Within linear response with respect to E y the mass-center positions of atomic orbitals are shifted along the ŷ-direction by the distance -eE y /(m 0 Ω 2 0 ) from their equilibrium positions na. This shift enters the Peierls substitution, Eq. ( 8), giving rise to an additional shift of k x → k x + ∆k x :

∆k x ≡ ω 2 c Ω 2 0 eE y ω c , (13)
where ω c = eB/m 0 c is the cyclotron frequency. The resulting shift of the mass-center position reads:

∆Y β (k x ) = - eE y m 0 Ω 2 0 1 -l -2 B dY (B) β (k x ) dk x . (14)
The electric field E y also gives rise to a potential energy, and up to the lowest order the eigenenergies are modified simply by an additive contribution eE y Y n,β (k x ). As a result the expectation value of the velocity along the xdirection changes as:

∆v x (β, k x ) = eE y dY (B) β (k x ) dk x . (15)
Consequently, a non-zero current density along xdirection (the Hall current) is induced by E y . It can be expressed in the form of Eq. ( 4) with σ(µ) given as:

σ(µ) = N -1 β N β β=1 dk x f 0 (E β (k x ) -µ) dY β (k x ) dk x , (16)
where f 0 (E -µ) denotes Fermi-Dirac distribution function and N β denotes number of branches. When the Fermi energy µ lies within the energy gaps, σ approaches an integer value σ, which can differ from zero due to the presence of magnetic edge states. Using the Eq. ( 14) defining the average shift of the mass-center positions and the identity Eq. ( 5), the electron polarizability can be written as:

α(µ) = e 2 m 0 Ω 2 0 N (µ) - σ(µ) a z 2πl 2 B = e 2 m 0 Ω 2 0 s(µ) a z A 0 . (17)
For the tight-binding model considered here, the dependence of α(µ) is fully specified by the effective topological number s(µ). The latter is plotted as a function of the filling factor of the tight-binding band, ν b ≡ a z A 0 N (µ) in Fig. 2 for several values of the ratio p/q. The case p/q = 0 corresponds to the zero magnetic field, for which s → s(0) = ν b as follows from Eq. ( 5). For non-zero ratios a rich behavior is induced by the applied magnetic field. q/p=1/3 q/p=3/5

FIG. 2: Dependence of the effective topological number s, on the band filling factor ν b for the ratio p/q = 0, 1/3 and 3/5.

Whenever the Fermi energy is located within the energy gap between subbands, i.e. if ν b is given by integer multiples of 1/q, the effective topological number s(µ) takes an integer value which is just equal to the topological gap number. As seen in Fig. 2, for p/q = 1/3, the total contribution of the lower and the upper sub-bands to the polarizability vanishes. In this particular case the applied electric force acting on carriers belonging to these subbands is fully compensated by the Lorentz force due to the induced non-dissipative edge Hall currents. For the case p/q = 3/5 the magnetic field even changes the sign of s and consequently the sign of the polarizability. At half-filling of the band (ν b = 1/2), the Hall current vanishes and s approaches its zero-field value 1/2. The central symmetry of all curves around this half-filling point (ν b = 1/2, s = 1/2) is a consequence of the electron-hole symmetry of the single tight-binding band.

In this letter we have analyzed the interplay between the Hall current and the electron polarizability for the tight-binding model of a crystalline solid. This interplay is controlled by the compensation of the external electric force with the two other forces acting on the electrons: the gradient force, due to the periodic background potential, which is related to the polarizability, and on the other hand the Lorentz force, which determines the nondissipative Hall current. The presence of the quantizing magnetic field induces a rich and complex behavior for the electron polarizability, which can even change sign as a function of the electron concentration.

Most importantly, we provide an answer to the longstanding question: what measurable quantity is determined by the topological gap number s entering the Diophantine equation? While it has been understood for a long time that σ determines the quantum Hall effect, a similar interpretation of s has so far remained unclear. We have shown that s is directly linked to the static electron polarizability. Contrary to the quantum Hall effect, the proportionality constant between the polarizability and the topological number s is a material dependent quantity rather than an universal constant, which can even depend on the magnetic field. The independence of the force constant m 0 Ω 2 0 on the magnetic field considered here is a mere consequence of the use of the Peierls substitution which is justified when Ω 0 ≫ ω c . A shrinking of atomic orbitals by the magnetic field, which leads to a suppression of the overlap strength and thus to a decrease of the overall band width, could be included by the substitution Ω 2 0 → Ω 2 0 + ω 2 c /4. The predicted effect requires that a few flux quanta penetrate the lattice area A 0 . Even for solids with a lattice constant of the order of 10 Å, this requires exceedingly large fields (∼ 10 3 T). If, however, the magnetic field is tilted with respect to the high-symmetry crystallographic directions (here ẑ), an effective area (which is larger than A 0 ) can accomodate a few flux quanta, so that the above condition can be reached with experimentally available fields [4]. This condition can also be reached in 2D arrays of quantum dots or antidots with a lattice constant ∼ 100 nm. However, such (anti) dots need to be weakly coupled in order to reproduce a tight binding energy spectrum. Their size reduction (which implies a weak overlap and well separated atomic states) is thus a necessary condition for observing the predicted effect, and it still represents an experimental challenge.

3 FIG. 1 :

 31 FIG. 1: Energy spectrum E β (kx) (in units of the overlap strength ∆V ) as a function of the center of mass coordinate Y (B) β

The authors acknowledge support from Grant No. GACR 202/05/0365 of the Czech Republic. P.S. acknowledges support from the Institutional Research Plan No. AV0Z10100521, and thanks CPT (UMR6207 of CNRS) for its hospitality.