Let C = (ci;j )(i;j)2Z2 where ci;j are independently distributed Bernoulli variables with parameter (1 q). We study the law of the semiperimeter of the smallest rectangle for which all neighbours have value 0 and that contains the origin. Assuming symmetries on the distribution (for instance ci;j = cj;i) leads to a hierarchy of systems of equations describing the probability that the semiperimeter of this rectangle is n. We propose a probabilistic algorithm common to all symmetries, leading to these equations. This algorithm is related to a local bootstrap percolation model presented by Gravner and Holroyd. For cases with most symmetries, this probability is also described by statistics such as the number of inversions on (partial) permutations. As a byproduct, we propose a positivity result concerning a polynomial involving inv and maj statistics on some linear extensions of some partial orders and a symmetric statistic on partial permutation inherited from a simple symmetry on the algorithm.
0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 Fwiigthurteh1e: oSrmigainlleisnt bstlaacbkle rectangle J 3; 2K J 1; 2K sFyimgumreetr2i:es Exawmitphle cecrtoirrceaspteonwdiinthg all ptehremustqautaiorne (1; 6; 5; 9; 2; 11; 8; 4; 3; 7; 10)
This problem comes from a study on the sandpile model [Dha95] in the square lattice. A stable rectangle is related to the bounding box of the stabilization when 4 grains are placed to the origin in a random con guration where each vertex independently has 2 grains with probability q and 3 grains otherwise. Hough, Jerison and Levine [HJL17] list known results in a slightly di erent setting. This problem can also be seen as a percolation model presented by Gravner and Holroyd [GH08] as the local Frobose model. The related non-zero probability of unde ned stable rectangle is bounded by the [GH08][Theorem 1].
We consider here simpli ed models imposing some square's symmetries on the sampling of values. More explicitly, in these models, we restrict the original distribution of values toward i.i.d. Bernoulli only on a part of Z2 and repeat these values according to the symmetries on the remaining part. For example with all the square symmetries ( g. 3), for 0 j i the ci;j are independent Bernoulli with parameter 1 q and c j; i = c i; j (= ci;j ) (illustrated by the black boxes on the gure). Our main results are that the exact probabilities in several of these models are also described by classical statistics on some (partial) permutations.
A statistic on the permutations is an integer given to every permutation. A rst classical statistic on the permutation is the statistic counting the number of inversions, denoted inv = jf(i; j) j i < j; (i) > (j)gj. We de ne desc = fi j (i) > (i + 1)g the set of descents of and maj = Pi2desc i the major index of . MacMahon [Mac15] showed that the statistics inv and maj are equally distributed on the set Sn of permutations of size n, ie P qinv = P qmaj .
2Sn 2Sn
The main results are the following theorems (if needed, see section 2 for details on examples of symmetries). Proposition 1.1. When having the symmetries of axes x = y and y = 0 ( g. 3). The probability that the smallest stable rectangle has semi-perimeter 4n + 2 is qn+1(1 q)n X
qinv : 2Sn Proposition 1.2. The symmetries x = y and x = y ( g. 5), and the rotational symmetry by an angle of =2 ( g. 4) reveal xed point free involution. The probability that the smallest stable rectangle has semi-perimeter 4n + 2 is q2n+1(1 q)n X q inv 2 n where I2n is the set of xed point free involutions of S2n.
y ( g. 6), the probability that the smallest stable rectangle has semi
Roughly speaking, these results can be obtain by identify the expected permutations with runs of the algorithm computing the stable rectangle. We only present the algorithm in a specialization for the axial symmetry in the line x + y = 0 (see section 3.1). With the axes x = 0 and y = 0 ( g. 8), we similarly identify permutations of size n sorted in 2n 1 1 step^s by Homing sort from Elizalde and Winkler [EW09] but unlike the previous results, we didn't nd any statistic counted by q to get an expression of the probability of semi-perimeter 2n + 2. The rotational symmetry by ( g. 9) gives close results to the precedent case in terms of equation. The relation between those two is the same as the relation between the case with all symmetries and the case with the rotational symmetry by =2 (Propositions 1.1 and 1.2). But the rotational symmetry by does not lead us to relation with permutations. We have no result about the remaining axial symmetry in the line y = 0 ( g. 7).
This enumerative study also has two byproducts on the study of permutations.
First, the Theorem 1.1 may be re ned to take into account the relative position of the origin inside the stable rectangle via its distances to the top and right sides. Our proof translates these two distances into statistics on related permutations with a marked decreasing subsequence: stat1 := jfi j 9j i; (j) is marked ; (j) (i)gj and stat2 := jfi j 8j i; (j) is marked ; (j) > (i)gj. A compatibility not detailed here of our algorithm with the symmetry of axis x = y (see section 3.4), implies an involution on those permutations which exchange the two statistics while preserving the number of inversions.
Then still following Theorem 1.1, more work was given to the expression of the probability. We are interested in P 2Snd qinv ( ) where d is a subsequence of (n; n 1; : : : 2; 1) and Snd the set of permutations of Sn that contain the subsequence d. This kind of sum can be found in Bjorner and Wachs [?] with either the number of inversions or the major index statistic. The section 4 presents the following result.
Theorem 1.2. Let n 2 N, d is a subsequence of (n; n 1; : : : 2; 1) and D f1; 2; : : : n 1g, then the following sum is a polynomial with positive integer coe cients, where Snd;D is the set of permutations of Snd whose descent set of the inverse desc ( 1) is D.
X 2Snd;D qmaj 1 qinv q
In section 2 we sketch the proofs of Propositions 1.1 and 1.2. In section 3 we present the proof of Theorem 1.1 based on a parallel between runs of an algorithm and insertion rules on relevant permutations. 2
We let R(C) be the smallest stable rectangle with respect to C and jR(C)j its semiperimeter. Then the probability that the semiperimeter of the smallest stable rectangle of C is n 2 is P[jR(C)j = n].
When assuming all symmetries of the square, the smallest stable rectangle is a square with centre the origin. The problem is reduced to the rst octant.
Then P[jR(C)j = 4n + 2] is the probability that there is at least one 1 in each one of the n rst segments and that the n + 1 segment contains only 0's. Thus P[jR(C)j = 4n + 2] = qn+1 Pin=1(1 qi). The sum Pin=1 (11 qqi) is well known to be P 2Sn qinv .
We denote by certi cate the set of position of the rst 1's in each segment, from the bottom. This certi cate can be interpreted as an inversion table of a permutation on n elements. The gure 2 illustrates an example certi cate. The certi cate is the sequence of vertices of ordinates ci where c = (0; 0; 0; 1; 3; 4; 0; 3; 5; 0; 5). The probability to obtain it is q12 Qi1=1 1(1 q)qci = q12(1 q)11 Qi1=1 1 qci . The vector c is also the inversion table of the permutation = (1; 6; 5; 9; 2; 11; 8; 4; 3; 7; 10). Thus the probability to observe this certi cate c is q12(1 q)11qinv . In the general case we have the Proposition 1.1. 2.2
Axial symmetries in the lines x = y and x = y As the previous case, the smallest stable rectangle is square with centre the origin. Here, the problem is reduced to the sector f(x; y) j 0 jyj xg ( g. 5).
We have that P[jR(C)j = 4n + 2] = q2n+1 Pin=1(1 q2i 1).
We can de ne the certi cate the same way. Then there are (2n 1)!! di erent certi cates.
A subset of permutations of size (2n 1)!! is the set of xed point free permutations on f1 : : : 2ng. In the same way as before, we showed a bijection between certi cates and xed point free involutions with an insertion rule. This leads to the Proposition 1.2. 3
Axial symmetry in the line x + y = 0 In this case, we only consider the upper half-plane delimited by x = y ( g. 6). We prove the following theorem.
Theorem 1.1. P[jR(C)j = 2n + 2] = q2n+2(1 q)n X
First, we demonstrate that the probability P[jR(C)j = 2n + 2] follows a linear recurrence from a system of q-linear equations. Then we remark that this recurrence corresponds to a q analogue of the recurrence satis ed by the number of partial permutations. Finally we show that this q analogue counts the number of inversions of the permutations involving in the theorem. 3.1
In the previous cases, it is enough to read C on the right border. We read the grid from the origin to the right, expanding a rectangle until the right border contains only 0's. In the case of axial symmetry in the line x + y = 0, we have to read two border.
In order to compute the size of a rectangle R(C), we de ne the deterministic algorithm 1 running on the grid. The algorithm reads the right border and the top border. Starting from the rectangle [0; 0]2, at each step, if a 1 is found in the right border or the top border, we know that this border is in R(C) so we expand the rectangle by merging the border to it. The g. 10 shows an example of con guration with the segments (red boxes) and the associated certi cate (in blue) given by the algorithm.
The algorithm consists on 3 states describing the knowledge of the border of the expanding rectangle. In State A, we did not read the border. In State B, we read the right border and it contains only 0's. In State C, we read the right border and the top border and they contains only 0's. Algorithm 1 Axis symmetry x =
y
From State A, either the right border contains only 0's and we go to State B, or we read a 1 in the right border so we go back to State A. From State B, either the top border contains only 0's and we go to State C, or we read a 1 in the top border. Then since we expand the rectangle toward the top, the whole right border except its top vertex has been read. Either this vertex has value 0, then and we go to State B, or we read a 1 in the top-right corner and we go to State A. The State C is the nal state since we found a stable rectangle. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 H5 0 0 0 0 1 0 0 0 0
H4 0 1 0 1 1 1 1 0
H3 1 1 0 0 0 0 0
H2 0 0 1 0 0 0
H1 1 0 0 0 0 1 1 0 0 0
0 0 0 V1 0 0
V2 0
V3 We re ne the states Ai;j , Bi;j and Ci;j from the algorithm with the size of the expanding rectangle J j; iK Ji; jK. Then the probability to enter a state from another is straightforward.
From state Ai;j , we enter state Ai+1;j with probability (1 qi+j+1), and state Bi;j with probability qi+j+1 otherwise. From state Bi;j , we enter state Bi;j+1 with probability q(1 qi+j+1), state Ai+1;j+1 with probability (1 q)(1 qi+j+1), and state Ci;j with probability qi+j+1 otherwise. Hence we deduce this equations: Ai;j = (1 qi+j )Ai;j 1 + (1 qi+j 1)(1
q)Bi 1;j 1 Bi;j = q(1
qi+j )Bi 1;j + qi+j+1Ai;j and Ci;j = qi+j+1Bi;j where Ai;j and Bi;j are 0 if i or j are negative and A0;0 = 1 and B0;0 = q.
With two substitutions, we get a relation on Ci;j
Ci;j = q2(Ci 1;j + Ci;j 1)(1 qi+j ) q4Ci 1;j 1(1
qi+j 1)2 This probability corresponds to the probability that the percolation algorithm terminates on the square of side i + j + 1 with the right border at distance j of the origin.
Let Cn = Pn
i=0 Ci;n i = P[jR(C)j = 2n + 2] the probability to terminate in a square of semi-perimeter 2n + 2. Then Cn = 2q2(1 qn)Cn 1 q2(q(1 qn 1))2Cn 2 where C0 = q2 and C1 = 2q4(1 q). The polynomial Cn can be factored by (1 q)n: Cn = q2n+2(1 q)nPn where Pn satis es The recurrence (1) is a q analogue of the recurrence satis ed by the number of partial permutations of f1 : : : ng shown by Borwein, Rankin and Renner [BRR89], since its limit for q ! 1 is: jRnj = 2njRn 1j (n 1)2jRn 2j where we denote by Rn the set of partial permutations of f1 : : : ng. A partial permutation is an injective partial self-maps on a set of n elements.
In order to count the number of inversions to re ne the recurrence (2), we map bijectively each partial permutation to a permutation with a decreasing subsequence marked constructed by completing the holes in the partial permutation by the missing elements marked in decreasing order. Then we denote by the number of inversions of a partial permutation the number of inversions of the corresponding permutation with a decreasing subsequence marked. For instance, the partial permutation =?26?1? where question marks denote unde ned values maps to = 526413 since the missing values are f3; 4; 5g. We will note = 526413. The number of inversions of is 10.
Now, we re ne the proof of [BRR89] following the number of inversions. The sketch of the proof is to build Rn from Rn 1 by using three insertion rules and to count the number of inversions that are created by each rule. We denote by Tn the set of partial permutations that are not de ned in 1. We denote by rn and tn the q analogues of jRnj and jTnj de ned by: rn = P 2Rn qinv ( ) and tn = P 2Tn qinv ( ). For instance, r2 = 3+4q and t2 = 1 + 2q.
We rst get the following lemma.
0, then rn+1 = 1 qn+1
1 q rn + qnrn + 11 qqn tn.
Proof. Let 2 Rn seen as a marked permutation. The insertion rules de ned on permutations with a decreasing subsequence marked will be denoted by 1, 2 and 3, and de ned as follow (with some partial permutation): that are greater or equal to k and we insert k at the rst (1) (2) 1 Let k 2 f1 : : : n + 1g, we shift the value of position.
= 526413, the rule 1 with k = 2 leads to 2637514 2 We insert a marked n + 1 at the rst position.
Example: f = 526413, the rule 2 leads to 6526413 3 Let k 2 f2 : : : n + 1g, if 1 is marked, we insert n + 1 at position k in .
Example: f = 526413, the rule 3 with k = 4 leads to 5267413
We note that 3 is only de ned on Tn. The co-domains of the rules 1, 2 and 3 form a partition of Rn+1. Since the rules 1, 2 and 3 are bijective, we proved the relation jRn+1j = (n + 1)jRnj + jRnj + njTnj.
Moreover, we can follow the number of new inversions when we insert an value in a permutation of size n. The rule 1 with parameter k adds k 1 inversions. The rule 2 adds n inversions. The rule 3 with parameter k adds n + 1 k inversions. Thus, we have
n+1 n+1 rn+1 = X qk 1rn + qnrn + X qn+1 ktn: k=1 k=2
Noticing that the co-domains of 2 and 3 form a partition of Tn, we also get in the same way the following lemma.
Thus Pn and rn satisfy the same recurrence and the same initialization. That concludes the proof of the Theorem 1.1. We can construct a bijection from the set of certi cates to the partial permutations using the rules 1, 2 and 3. The rule 3 corresponds to the transition Ai;j ! Ai+1;j , 2 to the transitions Bi;j ! Ai+1;j+1 and Ai;j ! Ai+1;j and 1 corresponds to the transition Bi;j ! Bi;j+1.
We note that if we take the re ection across the line x = y, the algorithm produces the same certi cate up to a permutation and reads the same vertices ( g. 11). Thanks to the precedent bijection, we have an involution on the partial permutations exchanging the statistics stat1 and stat2 presented in the introduction, and preserving the number of inversions, which is also the number of read 0's. 4
Decreasing subsequences and q-positivity We let the word sn = (n; n 1; : : : ; 1). Given two words u and v, u is a subsequence of v if u derives from v by deleting some letters, denoted by u v. We reformulate the probability given by Theorem 1.1 by interchanging the summations:
P[jR(C)j = 2n + 2] = q2n+2(1 q)n X
= q2n+2(1 q)n X
2Sn dd sn d sn d2Sn
We let Snd the set of permutations in Sn such that d . For some d, the sum P 2Snd qinv factorizes according to a more general study of linear extensions of partial orders [?].
The number of inversions of permutations was extended by Bjorner and Wachs towards labelled forests. The [?, Theorem 1.1] gives a simple relation if d has no hole, d = [min d; max d], P 2Snd qinv = qjdj(jdj 1)=2 [[jndj]]qq!! . Otherwise, there is no known formula for other d. However, the [?, Theorem 1.2] gives a similar formula if the major index statistic replaces the number of inversions: P 2Snd qmaj = qjdj(jdj 1)=2 [[jndj]]qq!! This suggests to consider
2Snd = X qmaj 2Snd 0
X 2Snd qmaj qinv 1 A
The second term of the right hand side is a polynomial of which 1 is a root, thus it can be factored by (1 Moreover, it satis es the following theorem. q).
Theorem 4.1. Let n 2 N, d sn, then the following sum is a polynomial with positive integer coe cients.
X qmaj 2Snd 1 qinv q
In order to prove this a rmation, we use intermediate statistics on permutations. Let W = (wi;j )1 i;j n be an upper triangular matrix, Kadell [Kad85] de ned the weighted inversion number invW ( ) of with respect to the weight matrix W by invW ( ) = P1 i<j n wi;j ( (i) > (j)). We de ne for 1 k < l n, W (k;l) = (wi(;kj;l)) where wi(;kj;l) = 1 for 1
i < j < l, wi(;ki;+l)1 = i for l < i < n, wi(;kl;l) = 1 for k < i < l, wk(k;l;l) = k and wi(;kj;l) = 0 otherwise. The [Kad85][Corollary 2] holds so W (k;l) is equally distributed with the inversion number. Note that invW (1;n) = inv and invW (1;2) = maj . We can easily show that for any and any 1 < k < l n, invW (k;l) ( ) invW (k 1;l) ( ) = (k 1) [ ( (k) > (l)) ( (k 1) > (l))]. qinvW (k;l) ( ) qinvW (k 1;l) ( ) 1 q is a polynomial with positive integer coe Proof. We de ned the involution ! ? by ? = (k 1; k) if (k 1) < (l) < (k) or (k) < (l) < (k 1) and ? = otherwise. This is an instance of [Kad85][Lemma 1], thus for any we have invW (k;l) ( ) = invW (k 1;l) ( ?). Let 2 Snd such that (k 1) < (l) < (k), since (k 1) < (k), (k 1) and (k) are not both in d. Then ? still contains the subsequence d and ?(k) < ?(l) < ?(k 1). So, the sum is a sum on the permutations such that invW (k;l) ( ) < invW (k 1;l) ( ) and such that ? is not in Snd.
Proof of the Theorem 4.1. For 1 < l < n, W (1;l) = W (l;l+1). Then qinv
Since the involution used for lemma 4.1 preserves the descents of the inverse, the theorem can be re ned to the permutation with the same inverse descent set. This positivity result gives some leads to nd a structure in the Theorem 1.1 formula. Moreover, the proof holds if the permutations are not constrained by a decreasing subsequence but a set of decreasing pairs.