format: text

text:
# Performance evaluation of modulation methods: a combinatorial approach

## 1 Introduction

Modulating a numeric signal corresponds to the fact of transforming the digital sequence that represents it, into a wave form. Modulation is therefore clearly a technique of main interest in a number of ingeneering domains such as computer networks, mobile communications, satellite transmissions, television diffusion, etc.

Due to their practical importance, modulation methods were therefore widely studied in signal processing. The classical Proakis textbook devotes for instance a full chapter to this subject (cf Chapter 5 of ). One of the most important problem in this area is to be able to design and to evaluate the performance characteristics of the optimum receivers associated with a given modulation method. The performance analyses that occur in such a context, reduce in particular to the computation of various probability errors (see again  for more details).

Among the different modulation protocols, a rather important (in practice) class consists in methods where the modulation references (i.e. the wave forms associated with all possible digital sequences of a given length) are also modulated and hence submitted to the transmission noise. In this kind of situation, the demodulating decision needs by consequence to account two noisy informations (the transmitted signal and the transmitted references). The computation of the probability errors appearing in such contexts, involves therefore very often to compute the following type of probability:

$$P(U<V)=P\left(\underset{j=1}{\overset{N}{}}u_j^{}u_j<\underset{j=1}{\overset{N}{}}v_j^{}v_j\right),$$
(1)
where the $`u_i`$ and $`v_i`$’s stand for independent complex Gaussian random variables with arbitrary variances respectively denoted

$$E[u_j^{}u_j]=\chi _j,E[v_j^{}v_j]=\delta _j$$
(2)
for every $`j[1,N]`$ (see Section 3.1 for more details).

The problem of computing explicitely this last probability was hence studied by a number of researchers coming from signal processing (cf ). The most interesting result in this direction was obtained by Barett (cf ) who proved that one can express the probability defined by (1) as follows:

$$P(U<V)=\underset{k=1}{\overset{N}{}}\left(\underset{jk}{}\frac{1}{1\delta _k^1\delta _j}\underset{j=1}{\overset{N}{}}\frac{1}{1+\delta _k^1\chi _j}\right).$$
(3)
It appears that this last formula can in fact be interpreted in a purely combinatorial way, using Schur functions and Young tableaux (see Section 3.1 for the details). This new approach already lead to the obtention of the first, both algorithmically efficient and numerically stable, practical method for computing the probability $`P(U<V)`$ (see again Section 3.1 or  for more informations).

In this paper, we continue the combinatorial study of Barett’s formula by showing that it is in fact highly connected with a slight modification of a very classical bijection of Knuth (cf  or  for a more recent presentation) between pairs of Young tableaux of conjugated shapes and $`\{0,1\}`$-matrices. These new considerations give us clearly a better understanding of Barett’s result. They also allowed us to obtain the first results with respect to specializations of Barett’s formula that were still not known for the moment (see Section 4.4).

## 2 Background

### 2.1 Partitions

A partition is a finite nondecreasing sequence $`\lambda =(\lambda _1,\lambda _2,\mathrm{},\lambda _m)`$ of positive integers. Graphically each such partition can be represented by a diagram of $`\lambda _1+\mathrm{}+\lambda _m`$ boxes, called its Ferrers diagram, whose $`(mi+1)`$-th row contains $`\lambda _i`$ boxes for every $`1in`$. The partition $`\lambda =(2,2,4)`$ is for instance represented by the Ferrers diagram

$$\begin{array}{cc}\text{    }\hfill & \text{    }\hfill \\ \text{    }\hfill & \text{    }\hfill \\ \text{    }\hfill & \text{    }\hfill & \text{    }\hfill & \text{    }\hfill \end{array}.$$

A given partition is then called the shape of the associated Ferrers diagram.

Using this graphic representation, one can easily define the notion of conjugated partition. The conjugated partition $`\lambda \stackrel{~}{}`$ of a given partition $`\lambda `$ is indeed just the partition obtained by reading the heights of the columns of the Ferrers diagram associated with $`\lambda `$. One has here for instance $`\lambda \stackrel{~}{}=(1,1,3,3)`$ when $`\lambda =(2,2,4)`$ as it can be seen on the previous picture.

When $`\lambda `$ is a partition whose Ferrers diagram is contained into the square $`(N^N)`$ with $`N`$ rows (of length $`N`$), one can also associate with it its complementary partition, denoted by $`\overline{\lambda }`$, which is the conjugate of the partition $`\nu `$ whose Ferrers diagram is the complement (read from top to bottom) of the Ferrers diagram of $`\lambda `$ in the square $`(N^N)`$. For instance, for $`N=6`$ and $`\lambda =(1,1,2,3)`$, we have $`\nu =(3,4,5,5,6,6)`$ and $`\overline{\lambda }=(2,4,5,6,6,6)`$ as it can be checked on the following Figure 1. The Ferrers diagram associated with $`\lambda `$ is here represented by the boxes filled with $``$ and the boxes filled with $``$ correspond in the same way to the partition $`\nu `$ (that can be obtained by computing the number of such boxes per row) or to the complementary partition $`\overline{\lambda }`$ (that can be obtained by computing the number of such boxes per column).

We will call tabloid of shape $`\lambda `$ the filling of a Ferrers diagram of shape $`\lambda `$ with arbitrary positive integers. A filling of the boxes of a Ferrers diagram of shape $`\lambda `$ with positive integers is called a Young tableau (of shape $`\lambda `$) whenever the numbers are weakly increasing along all rows and strictly increasing along all columns. For example, the diagram

| $`3`$ | $`5`$ |
| --- | --- |
| $`2`$ | $`2`$ |
| $`1`$ | $`1`$ | $`1`$ | $`4`$ |

is a Young tableau of shape $`(2,2,4)`$.

Let $`X=\{x_i,\mathrm{\hspace{0.17em}1}in\}`$ be a set of $`n`$ variables. One associates then to any Young tableau $`T`$ filled by integers not greater than $`n`$, a monomial $`X^T`$ defined as the product of the factors $`x_i`$ for each entry $`i`$ of $`T`$. For the Young tableau $`T`$ of the above example, one has for instance

$$X^T=x_1^3x_2^2x_3x_4x_5$$

if we set $`X=\{x_1,x_2,x_3,x_4,x_5\}`$. The Schur function $`s_\lambda (X)`$ associated with the partition $`\lambda `$ is then defined as the sum of the monomials $`X^T`$, for $`T`$ running over all Young tableaux of shape $`\lambda `$, filled with numbers not greater than $`n`$. We recall that each Schur function is a symmetric polynomial over $`X`$ and that the Schur functions are a linear basis of the algebra of symmetric polynomials over $`X`$ (for more informations on these questions, the reader should refer to the classical textbook ).

### 2.2 Gaussian polynomials and the $`q`$Newton formula

Let $`q`$ be a variable. Then the expression

$$\left[n\right]_q=1+q+q^2+\mathrm{}+q^{n1}=\frac{1q^n}{1q}.$$

is called the $`q`$integer of order $`n`$ (this notation comes from the fact that the specialization of a $`q`$-integer at $`q=1`$ gives of course the usual corresponding integer). We recall that the $`q`$factorial is then defined by

$$\left[n!\right]_q=\left[1\right]_q\left[2\right]_q\mathrm{}\left[n\right]_q=\frac{{\displaystyle \underset{i=1}{\overset{n}{}}}(1q^i)}{(1q)^n}.$$

Finally the expression

$$\left(\begin{array}{c}n\\ m\end{array}\right)_q=\frac{\left[n!\right]_q}{\left[m!\right]_q\left[(nm)!\right]_q}$$

is known as the Gaussian polynomial of order $`(n,m)`$. It is clearly the $`q`$-analogue of the usual binomial coefficient of the same order. We refer to  for more informations about Gaussian polynomials.

We will however recall the $`q`$Newton formula (see ):

$$\underset{j=0}{\overset{N}{}}\left(\begin{array}{c}N\\ j\end{array}\right)_q(1)^jq^{\frac{j(j1)}{2}}z^j=\underset{k=0}{\overset{N1}{}}(1zq^k).$$
(4)
Note that the $`q`$-Newton formula specializes for $`z=q`$ to

$$\underset{j=0}{\overset{N}{}}\left(\begin{array}{c}N\\ j\end{array}\right)_q(1)^jq^{\frac{j(j+1)}{2}}=\underset{k=1}{\overset{N}{}}(1q^k).$$
(5)
### 2.3 Column bumping process and Knuth bijection

The column bumping (or column-insertion) and row bumping (or row-insertion) processes are classical dual constructions that provide algorithms to transform a given word on the alphabet $`\mathrm{}`$ of all integers into a Young tableau. Here we will give some brief informations on the mechanism of column bumping and present a famous bijection of Knuth, between pairs of Young tableaux and $`\{0,1\}`$-matrices, (cf ) which is, being a variation on the well known Robinson-Schensted correspondence, based on column bumping process in its construction. For a better overview of the subject, we refer to .

The column bumping process is organized as follows. Take a positive integer $`x`$ and a Young tableau $`T`$. Put $`x`$ in a new box at the top of the first column if it is strictly larger than all the entries of the column. If it is not the case, bump the lowest (i.e., the smallest) entry in the column that is greater than or equal to $`x`$ and replace it by $`x`$. Move the bumped entry to the top of the next column if possible, or recursively bump one of the elements to the next column otherwise. The process continues until the bumped entry can go at the top of the next column, or until it becomes the only entry of a new column. Note, that the bumping here takes place in a zig-zag path that moves to the right, never moving up, and the result is always another tableau. If the location of the box that is added is known, the process can be reversed.

We are now in position to present the one-to-one correspondence (due to Knuth) between matrices $`M`$ whose entries are zeros and ones (or equivalently two-rowed arrays without repeated pairs) and pairs $`(P,Q)`$ of Young tableaux with conjugated shapes. The construction of this bijection can be reflected in the following steps.

1. Associate first with $`M`$ the array

$$A=\left(\begin{array}{cccc}u_1& u_2& \mathrm{}\mathrm{}& u_r\\ v_1& v_2& \mathrm{}\mathrm{}& v_r\end{array}\right),$$

that consists of all the indices (classified in the lexicographic order) corresponding to the $`1`$-entries of $`M`$ (all the entries $`u_i`$ of the first row are therefore in weakly increasing order and one has moreover $`v_{i1}v_i`$ in the second row whenever one has $`u_{i1}=u_i`$ in the first).
2. Perform column bumping with all the variables $`v_i`$ of the second row of the array $`A`$ begining from the first variable $`v_1`$ and moving one by one to the very last variable $`v_r`$. The result is a Young tableau $`P`$.
3. The second Young tableau $`Q`$ is just an encoding of the order in which the first Young tableau $`P`$ was constructed on the previous step. We first place the first element $`u_1`$ in the (conjugated of the) first box that appeared during the column bumping process that was used to construct $`P`$. The second element $`u_2`$ is placed in the same way in the box which is conjugated to the second box that appeared in this process, etc.

Applying the reversed column bumping process to the tableau $`P`$ and removing in the same time the corresponding boxes of the tableau $`Q`$, allows us to reconstruct the initial array $`A`$ by writing down in the order of their appearing the bumped out entries.

### 2.4 Columns and their complements

In this subsection, we will finally pay some attention to columns, i.e. to Young tableaux of shape $`1^k=(1,\mathrm{},1)`$. The number $`k`$ of 1’s is here equal to the length of the column. We will be only interested by columns of length less than some positive number $`N`$, filled with integers belonging to the set $`\{1,\mathrm{},N\}`$.

Introduce now some new notations. Let $`I=\{i_1<i_2<\mathrm{}<i_l\}`$ be a strictly increasing subsequence of $`\{1,\mathrm{},N\}`$. Denote then by $`c\left(I\right)`$ the column of length $`l`$ filled with all integer of $`I`$, increasing from bottom to top. We will also use in the sequel the notation $`c(I,J)`$ to denote the column of length $`l+m`$ filled with the elements of the sets $`I=\{i_1,i_2,\mathrm{},i_l\}`$ and $`J=\{j_1,j_2,\mathrm{},j_m\},`$ if the sequence

$$i_1<i_2<\mathrm{}<i_l<j_1<j_2<\mathrm{}<j_m$$

is a strictly increasing subsequence of $`\{1,\mathrm{},N\}.`$

Let $`K=\{k_1<k_2<\mathrm{}<k_t\}`$ be a strictly increasing subsequence of positive integers. The column $`c\left(K\right)`$ is then called the complement (within $`\{1,\mathrm{},N\}`$) of the column $`c\left(I\right)`$ if we have $`K=\{1,\mathrm{},N\}I`$. In the sequel, this column will be denoted

$$c\left(K\right)=\overline{c\left(I\right)}.$$

Let us again take two sets $`I=\{i_1,i_2,\mathrm{},i_l\}`$ and $`J=\{j_1,j_2,\mathrm{},j_m\}`$. We will say that the column $`c\left(I\right)`$ is less or equal than the column $`c\left(J\right)`$ and write $`c\left(I\right)c\left(I\right)`$ if one has $`mn`$ and $`i_kj_k`$ for every $`1km`$. In other words, a column $`c\left(I\right)`$ is less or equal to a column $`c\left(J\right)`$ if and only if one obtains a Young tableau when putting the column associated with $`J`$ at the right of the column associated with $`I`$.

## 3 Performance analysis of modulation protocols

### 3.1 Barret’s formula

The analysis of many practical digital transmission systems involves the computation of the probability that a given Hermitian quadratic form in complex normal variates is negative. Numerous such examples can be found in Proakis’s standard textbook (cf ). This kind of problem appears in particular in the context of performance analysis of classical demodulation protocols acting on modulated signals transfered on noisy Gaussian channels.

A first expression for the probability that a given Hermitian quadratic form in complex normal variates is negative, was first derived by Turin (see ) and used later by Barrett (see ) to unveil a closed form expression for this probability as a rational function of the eigenvalues of the corresponding covariance matrix. Barett showed indeed that the general problem discussed above can be reduced to the study of the probability $`P(U<V)`$ presented in the first section of this paper (cf formula (1) of section 1).

Barett gave also the explicit formula (3) that was, up to this year, the best known approach from computing the probability $`P(U<V)`$ from a practical point of view. Alternate methods involving either direct contour integration of the associated characteristic function along a carefully selected path so as to maximise numerical stability, or algebraic manipulations like in  (Annex B) or , provide other approaches involving numerical quadrature of trigonometric functions.

All these methods lead however to algorithms that are not numerically stable due to the presence of artificial singularities (such as the singularities $`\delta _i=\delta _j`$ of Barett’s formula (3)). It is therefore important to notice that the first efficient and stable method for computing $`P(U<V)`$ was very recently proposed by Dornstetter, Krob and Thibon (cf  or section 3.2), based initially on symmetric functions techniques. We recall below their algorithm for the sake of completeness (cf  for all details).

* Step 1. Consider the two polynomials defined by setting

$$X(z)=\underset{i=1}{\overset{N}{}}(1\chi _iz),\mathrm{\Delta }(z)=\underset{i=1}{\overset{N}{}}(1+\delta _iz).$$
* Step 2. Compute the unique polynomial $`\pi `$ of degree less or equal $`N1`$ such that one has

$$\pi (z)X(z)+\mu (z)\mathrm{\Delta }(z)=1$$

where $`\mu `$ stands for some other polynomial of degree less or equal to $`N1`$.
* Step 3. Evaluate $`P(U<V)=\pi (0).`$

The algorithmic efficiency and the numerical stability of this result comes then just from the fact that the second step of the above method can be made using the generalized Euclidean algorithm which is a very classical method which has the two above mentionned properties.

### 3.2 The combinatorial version of Barett’s formula

Barett’s formula in fact can be rewritten as a rational fraction, i.e.

$$P(U<V)=\frac{F(\chi ,\delta )}{{\displaystyle \underset{1i,jN}{}}(\chi _i+\delta _j)},$$
(6)
where $`F(\chi ,\delta )`$ is a symmetric polynomial with respect to the $`\chi _i`$ and to the $`\delta _j`$. Moreover can be proved (cf ) that $`F(\chi ,\delta )`$ can be expressed in terms of Schur functions, i.e.

$$F(\chi ,\delta )=\underset{\lambda (N^{N1})}{}s_{(\lambda ,N)}(\{\delta _1,\mathrm{},\delta _N\})s_\lambda ^{}(\{\chi _1,\mathrm{},\chi _N\}),$$
(7)
where $`\lambda ^{}`$ denotes the complement of the partition $`(\lambda ,N)`$ within the rectangle $`N^N`$.

Note now that each monomial that appear in the right hand side of equation (7) can be obtained by taking the product of all the elements of a square tableau of shape $`N\times N`$ consisting in two Young tableaux of complementary shapes (i.e. as given by Figure 1 of Section 2.1) that respect the two following constraints:

* Condition S1: the first tableau is only filled by variables that belong to the alphabet $`\delta =\{\delta _1,\mathrm{},\delta _N\}`$ and the length of its first row is equal to $`N`$,
* Condition S2: the second tableau is only filled by variables that belong to the alphabet $`\chi =\{\chi _1,\mathrm{},\chi _N\}`$.

A typical example of such a combinatorial structure is given in Figure 2. Note that the first tableau is written here in the usual way. On the other hand, the second tableau is organized a bit differently: its rows (resp. its columns) are placed from top to bottom (resp. from right to left) in the space corresponding to the complement of the first tableau within the square $`N\times N`$.

We will now proceed exploring the polynomial $`F(\chi ,\delta )`$, involved in formula (6) and given by formula (7), by calculating the number $`\alpha _N`$ of all square $`N\times N`$ tableaux filled as in the typical example of Figure 2. Knowing this last integer will give us the exact algorithmic complexity of the formula (6). One should indeed just notice that $`\alpha _N`$ is equal to the number of distinct monomials involved in $`F(\chi ,\delta )`$, from which one can easily deduce that the complexity of the computation of $`F(\chi ,\delta )`$ is exactly equal to $`N^2\alpha _N`$.

It appears unfortunately that $`\alpha _Nn=2^{N^21}`$, as proved in the next result, which implies that formula (6) can not be used in practice as soon as $`N`$ grows. The combinatorial formula (6) is however absolutely not useless (from a theoretical point of view) since it can be reformulated equivalently in the terms of the algorithm given at the end of Section 3.1, which is both practically very efficient (its complexity is quadratic as Barett’s formula) and numerically stable as already stated (cf  for all details).

###### Proposition 3.1

The number $`\alpha _N`$ of square tableaux of shape $`N\times N`$ filled by two complementary Young tableaux satisfying to conditions S1 and S2 is given by the formula:

$$\alpha _N=2^{N^21}.$$

Proof – Let us first notice that the conjunction of formulas (3) and (6) shows that one has:

$$\frac{F(\chi ,\delta )}{{\displaystyle \underset{1i,jN}{}}(\chi _i+\delta _j)}=\underset{k=1}{\overset{N}{}}\left(\underset{jk}{}\frac{1}{1\delta _k^1\delta _j}\underset{j=1}{\overset{N}{}}\frac{1}{1+\delta _k^1\chi _j}\right).$$
(8)
Let us begin by replacing everywhere $`\chi _i`$ and $`\delta _i`$ by $`t^i`$ in this last formula. This simple trick will allow us to avoid the singularities of Barett’s formula, corresponding to the situation when some of the $`\delta _i`$’s collapse to a common value. Note that this replacement of variables transforms the symmetric function $`F(\chi ,\delta )`$ into a polynomial $`P(t)`$ that provides the desired number $`\alpha _N`$ when $`t`$ equal $`1`$. Therefore it is sufficient to calculate $`P(1)`$ to get the value of $`\alpha _N`$.

Note now that formula (8) gives us immediately the following expression for $`P(t)`$:

$$P(t)=\underset{1i,jN}{}\left(t^i+t^j\right)\left(\underset{k=1}{\overset{N}{}}\left(\underset{1jkN}{}\frac{1}{1t^{jk}}\underset{j=1}{\overset{N}{}}\frac{1}{1+t^{jk}}\right)\right).$$
(9)
It appears that one can prove that the identity

$$\underset{k=1}{\overset{N}{}}\left(\underset{1jkN}{}\frac{1}{1t^{jk}}\underset{j=1}{\overset{N}{}}\frac{1}{1+t^{jk}}\right)=\frac{1}{2}$$
(10)
holds for every $`t`$ (see Lemma 3.2 below). Hence one gets

$$P(t)=\frac{1}{2}\left(\underset{1i,jN}{}(t^i+t^j)\right),$$

from which one can immediately conclude that $`\alpha _N=P(1)=2^{N^21}`$. Hence the proof of our proposition now reduces to the proof of the following lemma.

###### Lemma 3.2

For every $`t`$, one has:

$$\underset{k=1}{\overset{N}{}}\left(\underset{1jkN}{}\frac{1}{1t^{jk}}\underset{j=1}{\overset{N}{}}\frac{1}{1+t^{jk}}\right)=\frac{1}{2}.$$
(11)
Proof – We will perform a number of equivalent transformations of identity (11) in order to reduce it into a classical identity, which will finish our proof.

Taking first into account that

$$\underset{j=1}{\overset{N}{}}\frac{1}{1+t^{jk}}=\frac{1}{2}\left(\underset{1jkN}{}\frac{1}{1+t^{jk}}\right),$$

we can rewrite equation (11) in the equivalent way:

$$\underset{k=1}{\overset{N}{}}\left(\underset{1jkN}{}\frac{1}{1t^{jk}}\right)\left(\underset{1jkN}{}\frac{1}{1+t^{jk}}\right)=\underset{k=1}{\overset{N}{}}\underset{1jkN}{}\frac{1}{1t^{2(jk)}}=1.$$
(12)
Let us further develop the left hand side of the last equation. We then get

$$\underset{k=1}{\overset{N}{}}\underset{1jkN}{}\frac{1}{1t^{2(jk)}}=\underset{k=1}{\overset{N}{}}\underset{j=1}{\overset{k1}{}}\frac{1}{1t^{2(jk)}}\underset{j=k+1}{\overset{N}{}}\frac{1}{1t^{2(jk)}}$$

$$=\underset{k=1}{\overset{N}{}}\underset{j=1}{\overset{k1}{}}\frac{1}{1t^{(2j)}}\underset{j=1}{\overset{Nk}{}}\frac{1}{1t^{2j}}=\underset{k=1}{\overset{N}{}}\underset{j=1}{\overset{k1}{}}\frac{(1)t^{2j}}{1t^{2j}}\underset{j=1}{\overset{Nk}{}}\frac{1}{1t^{2j}}$$

$$=\underset{k=1}{\overset{N}{}}\frac{(1)^{k1}t^{2(1+2+\mathrm{}+(k1))}}{{\displaystyle \underset{j=1}{\overset{k1}{}}}(1t^{2j}){\displaystyle \underset{j=1}{\overset{Nk}{}}}(1t^{2j})}=\underset{k=1}{\overset{N}{}}\frac{(1)^{k1}t^{k(k1)}}{{\displaystyle \underset{j=1}{\overset{k1}{}}}(1t^{2j}){\displaystyle \underset{j=1}{\overset{Nk}{}}}(1t^{2j})}.$$

Substituting $`t^2=q`$ in the previous identity allows us therefore to rewrite identity (12) into the following alternate form:

$$\underset{k=1}{\overset{N}{}}\frac{(1)^{k1}q^{\frac{k(k1)}{2}}}{{\displaystyle \underset{j=1}{\overset{k1}{}}}(1q^j){\displaystyle \underset{j=1}{\overset{Nk}{}}}(1q^j)}=1.$$
(13)
Multiplying now both parts on this last identity by the polynomial $`\left[(N1)!\right]_q(1q)^{N1}`$ and using the definition of the Gaussian polynomials, we can rewrite identity (13) as

$$\left[(N1)!\right]_q(1q)^{N1}=\underset{k=1}{\overset{N}{}}\frac{(1)^{k1}q^{\frac{k(k1)}{2}}\left[(N1)!\right]_q}{\left[(k1)!\right]_q\left[(Nk)!\right]_q}=\underset{k=1}{\overset{N}{}}\left(\begin{array}{c}N1\\ k1\end{array}\right)_q(1)^{k1}q^{\frac{k(k1)}{2}}.$$

This last formula can therefore be equivalently rewritten as

$$\underset{i=1}{\overset{N1}{}}(1q^i)=\underset{j=0}{\overset{N1}{}}\left(\begin{array}{c}N1\\ j\end{array}\right)_q(1)^jq^{\frac{j(j+1)}{2}},$$

which is exactly the well known $`q`$Newton formula (see Section 2.2 or ). Hence the initial identity is true since it is just a transformation of this last classical identity.

## 4 A bijective proof of the combinatorial formula

The previous proof gave us the desired number $`\alpha _N`$ of monomials involved in $`F(\chi ,\delta )`$ in a purely analytic way. It however did not provide any insight, neither in the structure of $`F(\chi ,\delta )`$, nor in the simplicity of our result since the fact that $`\alpha _N=2^{N^21}`$ is indeed clearly remarcable.

We will devote now this section to the construction of a bijective proof of this last result. It will appear in fact that this construction will also help us in studying a number of specializations of Barett’s formula. Hence our bijective proof will be rather interesting both from a theoretical and a practical point of view.

### 4.1 A more general structure

In order to prove that $`\alpha _N=2^{N^21}`$ in a bijective way, we will introduce a slightly generalized version of the combinatorial structures that were involved in the description of $`F(\chi ,\delta )`$. These new combinatorial structures will just consist in the set, that we will denote by $`𝒯_N`$, of all $`N\times N`$ squares divided into two complementary Young tableaux (without any constraint on them) respectively filled by elements of the alphabets $`\delta `$ and $`\chi `$. The following picture shows two typical examples of an element of $`𝒯_6`$.

Note that the first tableau is again written in the usual way. On the other hand, the second tableau is organized again differently: its rows (resp. its columns) are placed from top to bottom (resp. from right to left) in the space corresponding to the complement of the first tableau within the square $`N\times N`$.

We will prove bijectively in the sequel that the cardinality of $`𝒯_N`$ is equal to $`2^{N^2}`$. This will immediately imply that $`\alpha _N=2^{N^21}`$ due to the fact that the number of elements of $`𝒯_N`$ whose first tableau has a first row of length $`N`$ is clearly equal to the number of elements of $`𝒯_N`$ whose second tableau has a first row of length $`N`$ (which corresponds to the case where the first tableau has a first row of length strictly less than $`N`$).

To get this last result, we will construct a bijection – presented in the next subsection – between $`𝒯_N`$ and the set $`_{N\times N}(\{0,1\})`$ of all $`\{0,1\}`$-matrices of size $`N\times N`$.

### 4.2 Construction of the bijection

We will now present our bijection between $`_{N\times N}(\{0,1\})`$ and $`𝒯_N.`$ Our construction is based on a slight variation of the well known Knuth’s bijection, presented in Section 2.3. We will see in the sequel that it has some deep and not obvious symmetry properties that will be fundamental for highlighting Barett’s formula in a totally new way.

Let therefore $`M`$ be a matrix of $`_{N\times N}(\{0,1\})`$. We associate then with $`M`$ the word $`w(M)`$ over the alphabet $`\{1,2,\mathrm{},N\}\times \{1,2,\mathrm{},N\}`$ defined as follows.

1. Construct first the $`2`$-row array $`A_N`$ which is equal to the sequence of the $`N^2`$ pairs $`(i,j)`$ of $`\{1,2,\mathrm{},N\}\times \{1,2,\mathrm{},N\}`$ taken in the lexicographic order, i.e.

$$A_N=\left(\begin{array}{cccccccccc}1& \mathrm{}& 1& 2& \mathrm{}& 2& \mathrm{}\mathrm{}& N& \mathrm{}& N\\ 1& \mathrm{}& N& 1& \mathrm{}& N& \mathrm{}\mathrm{}& 1& \mathrm{}& N\end{array}\right).$$
2. Select then in this array all the entries that correspond to the $`1`$’s of of $`M`$. We obtain then a word $`w(M)`$ on the alphabet $`\{1,2,\mathrm{},N\}\times \{1,2,\mathrm{},N\}`$ by reading all these entries from left to right.

###### Example 4.1

Let us consider the matrix

$$M=\left(\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 1\end{array}\right).$$

Then one has

$$A_3=\left(\begin{array}{ccccccccc}1& 1& \text{}& \text{}& 2& 2& 3& \text{}& \text{}\\ 1& 2& \text{}& \text{}& 2& 3& 1& \text{}& \text{}\end{array}\right)$$

where we squared the entries associated with the $`1`$’s of $`M`$. Hence we get

$$w(M)=\left(\begin{array}{c}1\\ 3\end{array}\right)\left(\begin{array}{c}2\\ 1\end{array}\right)\left(\begin{array}{c}3\\ 2\end{array}\right)\left(\begin{array}{c}3\\ 3\end{array}\right).$$

We apply now Knuth’s bijection to $`w(M)`$ in order to get two Young tableaux

$$(T_1,T_2)$$

of conjugated shapes $`\lambda _1`$ and $`\lambda _1\stackrel{~}{}`$. We will now associate with the tableau $`T_2`$ a new tableau $`\overline{T_2}`$ of shape $`\overline{\lambda _1}`$ (the complementary partition of $`\lambda _1`$ within $`N\times N`$) that is constructed as follows. Note first that one defines a unique tabloid $`\overline{T_2}`$ of shape $`\overline{\lambda _1}`$ by asking (for every $`i[1,N]`$) that the $`i`$-th column of $`\overline{T_2}`$ consists exactly of all the letters of $`\{\mathrm{\hspace{0.17em}1},\mathrm{},N\}`$ that do not appear in the $`(Ni+1)`$-th column of $`T_2.`$ It appears that this tabloid is in fact a Young tableau.

###### Proposition 4.2

The tabloid $`\overline{T_2}`$ is a Young tableau.

Proof – The proof will be made in three steps. In all lemmas that are involved in this proof, we will use the notations and definitions of Section 2.4. The proof of the two first lemmas will be found in the final version of this paper.

###### Lemma 4.3

Let $`c(I,J)`$ and $`c\left(I\right)`$ be the two columns such that $`c(I,J)c\left(I\right)`$. Then, for their complements $`\overline{c(I,J)}`$ and $`\overline{c\left(I\right)}`$ holds the following unequality:

$$\overline{c\left(I\right)}\overline{c(I,J)}.$$

###### Lemma 4.4

Let $`c\left(I\right)`$ and $`c\left(J\right)`$ be two columns of the same length such that $`c\left(I\right)c\left(J\right)`$. Then, for their complements $`\overline{c\left(I\right)}`$ and $`\overline{c\left(J\right)}`$, holds the following inequality:

$$\overline{c\left(J\right)}\overline{c\left(I\right)}.$$

Proposition 4.2 is now an immediate consequence of the next (and last) lemma.

###### Lemma 4.5

Let $`c(I,J)`$ and $`c(K)`$ be two columns that satisfy the inequality $`c(I,J)c\left(K\right)`$. Suppose also that the two subsets $`I`$ and $`K`$ of $`\{1,\mathrm{},N\}`$ have the same number of elements. Then, for the complements $`\overline{c(I,J)}`$ and $`\overline{c\left(K\right)}`$ of the two above columns, one has:

$$\overline{c\left(K\right)}\overline{c(I,J)}.$$

Proof – The statement of our lemma can be easily obtained by applying Lemma 4.3 and Lemma 4.4 in order to get the inequalities:

$$c(I,J)c\left(I\right)c\left(K\right).$$

This ends therefore both the proof of our lemma and of Proposition 4.2.

###### Example 4.6

Let us continue Example 4.1. Knuth’s bijection applied to the word $`w(M)`$, gives the pair of tableaux

$$(T_1,T_2)=\left(\text{ }\text{  3    2    1    3  }\text{ , }\text{  2    1    3    3  }\right)$$

of conjugated shapes $`\lambda _1=(1,1,2)`$ and $`\lambda _1\stackrel{~}{}=(1,3)`$. The shape $`\overline{\lambda _1}=(2,3)`$, complementary to the shape $`\lambda _1`$ of the tableau $`T_1`$ within the square 3$`\times `$3, provides then the shape of the tableau $`\overline{T_2}`$. Filling in its entries by taking (in the reverse order) the complements within $`\{1,2,3\}`$ of the columns of $`T2`$, we obtain

$$\overline{T_2}=\begin{array}{cc}\text{  2  }\hfill & \text{  2  }\hfill \\ \text{  1  }\hfill & \text{  1  }\hfill & \text{  3  }\hfill \end{array}.$$

The pair $`(T_1,\overline{T_2})`$ is then a pair of complementary Young tableaux within the square $`N\times N`$. To get an element of $`𝒯_N`$, it suffices now to associate with each entry $`i`$ of $`T_1`$ (resp. of $`T_2`$) the letter $`\delta _i`$ (resp. $`\chi _i`$) of the alphabet $`\delta `$ (resp. $`\chi `$). The element of $`𝒯_N`$ associated in such a way with the initial matrix $`M`$ of $`_{N\times N}(\{0,1\})`$, will be denoted by $`\mathrm{\Phi }(M)`$ in the sequel.

Since the mapping $`T_2\overline{T_2}`$ is one to one, it is now clear that we constructed in such a way a bijection $`\mathrm{\Phi }`$ between $`_N(\{0,1\})`$ and $`𝒯_N.`$ The problem is now to explore the properties of this bijection in order to be able to get some interesting enumerative consequences.

###### Example 4.7

Let us finish the previous example 4.6 which was itself a continuation of Example 4.1. The element of $`𝒯_3`$ which is associated with the pair $`(T_1,\overline{T_2})`$ is given below:

Φ(M)=

 δ3

 χ2

 χ3

 δ2

 χ2

 χ1

 δ1

 δ3

 χ1

Φ𝑀

 δ3

 χ2

 χ3

 δ2

 χ2

 χ1

 δ1

 δ3

 χ1

\Phi(M)\ \ =\ \ \vbox{\vskip 3.0pt plus 1.0pt minus 1.0pt\offinterlineskip\halign{&\vsquare{#}\cr\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\delta_{3}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt&\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\chi_{2}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt&\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\chi_{3}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt\cr\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\delta_{2}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt&\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\chi_{2}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt&\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\chi_{1}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt\cr\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\delta_{1}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt&\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\delta_{3}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt&\vbox{\hbox{\vrule width=0.5pt\vbox to14.0pt{\hrule height=0.5pt\vss\hbox to14.0pt{\hss$\chi_{1}$\hss}
\vss\hrule height=0.5pt}
\vrule width=0.5pt}
\kern-0.5pt}\kern-0.5pt\cr}}
where $`M`$ stands for the matrix introduced in Example 4.1.

### 4.3 Symmetry properties of our bijection

We will present here a very strong symmetry property of our bijection $`\mathrm{\Phi }`$. To this purpose, we give first another method for constructing it, presented below.

1. Construct again the two row array $`A_N`$ which is the sequence of the $`N^2`$ pairs $`(i,j)`$ of $`\{1,\mathrm{},N\}\times \{1,\mathrm{},N\}`$ taken in the lexicographic order, i.e.

$$A_N=\left(\begin{array}{cccccccccc}1& \mathrm{}& 1& 2& \mathrm{}& 2& \mathrm{}\mathrm{}& N& \mathrm{}& N\\ 1& \mathrm{}& N& 1& \mathrm{}& N& \mathrm{}\mathrm{}& 1& \mathrm{}& N\end{array}\right).$$

Select then in $`A_N`$ all the pairs corresponding to the $`1`$’s of $`M`$. We obtain then a first word $`w_1(M)`$ by reading the second component of the selected entries.
2. Construct then the two row array $`B_N`$ which is equal to the sequence of the $`N^2`$ pairs $`(i,j)`$ of $`\{1,\mathrm{},N\}\times \{1,\mathrm{},N\}`$ taken in the antilexicographic order (that is to say the lexicographic order with respect to the second entry), i.e.

$$B_N=\left(\begin{array}{cccccccccc}1& \mathrm{}& N& 1& \mathrm{}& N& \mathrm{}\mathrm{}& 1& \mathrm{}& N\\ 1& \mathrm{}& 1& 2& \mathrm{}& 2& \mathrm{}\mathrm{}& N& \mathrm{}& N\end{array}\right).$$

Select in this array all pairs corresponding to the $`0`$’s of $`M`$. We obtain then a second word $`w_2(M)`$ by reading the first component of the selected entries.

One construct then two Young tableaux $`(T_1^{},T_2^{})`$ by applying the column bumping process to the two previous words $`w_1(M)`$ and $`w_2(M)`$. It appears that these tableaux are exactly the two Young tableaux obtained by the bijection $`\mathrm{\Phi }`$, constructed in the previous subsection, applied to the matrix $`M`$.

###### Example 4.8

This example continues again Example 4.6. Since the first step of the both ways to construct bijection $`\mathrm{\Phi }`$ is the same, we will get here

$$A_3=\left(\begin{array}{ccccccccc}1& 1& \text{}& \text{}& 2& 2& 3& \text{}& \text{}\\ 1& 2& \text{}& \text{}& 2& 3& 1& \text{}& \text{}\end{array}\right).$$

For the second array, we have in the same way:

$$B_3=\left(\begin{array}{ccccccccc}\text{}& 2& \text{}& \text{}& \text{}& 3& 1& \text{}& 3\\ \text{}& 1& \text{}& \text{}& \text{}& 2& 3& \text{}& 3\end{array}\right).$$

Hence we get

$$w_1(M)=(3,1,2,3),w_2(M)=(1,3,1,2,2).$$

The column bumping process applied to $`w_1(M)`$ and $`w_2(M)`$ gives us then immediately the two following Young tableaux:

$$(T_1^{},T_2^{})=\left(\text{ }\text{  3    2    1    3  }\text{ , }\text{  2    2    1    1    3  }\right)=(T_1,\overline{T_2}).$$

We are now in position to state the following proposition which expresses the main symmetry property of our construction.

###### Proposition 4.9

For every matrix $`M`$ of $`_{N\times N}(\{0,1\})`$, one has :

$$\mathrm{\Phi }(M)=(T_1^{},T_2^{})$$

Proof – We will not give here the proof of this important result sicne it is rather technical. It is just worthwhile to note that our proof is based on the explicitation of the strong relations that exist between the Greene’s invariants of the two words $`w_1(M)`$ and $`w_2(M)`$.

### 4.4 Some specializations of Barett’s formula

As a consequence of the bijection, we can get some interesting combinatorial identities for several special cases of Barett’s formula. It is for instance obvious to see that our bijection leads immediately to the identity

$$F(\chi ,\delta )+F(\delta ,\chi )=\underset{k=0}{\overset{N^2}{}}\left(\begin{array}{c}N^2\\ k\end{array}\right)\delta ^k\chi ^{N^2k}$$

in the situation where one substitutes in the symmetric function $`F`$ all $`\delta _i`$ and $`\chi _i`$ by a single value respectively equal to $`\delta `$ and $`\chi `$.

In a more interesting level, it is also possible to use our bijection in order to get an explicit combinatorial interpretation (which was still an open problem) of the coefficients of the polynomial of two variables resulting from the substitution of the $`k`$ first variables $`\delta _i`$ and $`\chi _i`$ by single values and of all last $`Nk`$ variables $`\delta _j`$ and $`\chi _j`$ by $`1`$. This interpretation is however rather long to explain: it will therefore be only presented in the final version of this paper.


text:
# 1. INTRODUCTION

## 1. INTRODUCTION

The lattice approach to gauge theories allows the non-perturbative study of gauge systems without loosing the gauge invariance. Recently  it has been proposed a method to define on the lattice the gauge invariant effective action by using the Schrödinger functional .
In the continuum the Euclidean Schrödinger functional in Yang-Mills theories without matter fields reads:

$$𝒵[A^{(f)},A^{(i)}]=A^{(f)}\left|e^{HT}𝒫\right|A^{(i)}.$$
(1.1)
In Eq. (1.1) $`H`$ is the pure gauge Yang-Mills Hamiltonian in the fixed-time temporal gauge, $`T`$ is the Euclidean time extension, while $`𝒫`$ projects onto the physical states. $`A_k^{a(i)}(\stackrel{}{x})`$ and $`A_k^{a(f)}(\stackrel{}{x})`$ are static classical gauge fields, and the state $`|A`$ is such that

$$A|\mathrm{\Psi }=\mathrm{\Psi }[A],$$
(1.2)
$`\mathrm{\Psi }[A]`$ being a wavefunctional. Note that, by definition, $`𝒵[A^{(f)},A^{(i)}]`$ is invariant under gauge transformations of the gauge fields $`A^{(i)}`$ and $`A^{(f)}`$.
Using standard formal manipulations and the gauge invariance of the Schrödinger functional it is easy to rewrite $`𝒵[A^{(f)},A^{(i)}]`$ as a functional integral

$$𝒵[A^{(f)},A^{(i)}]=𝒟Ae^{_0^T𝑑x_4{\scriptscriptstyle d^3x_{YM}(x)}}$$
(1.3)
with the constraints:

$`A_\mu (x_4=0)=`$ $`A_\mu ^{(i)}`$
$`A_\mu (x_4=T)=`$ $`A_\mu ^{(f)}.`$
It is worthwhile to stress that in Eq. (1.3) we should sum over the topological inequivalent classes. However, it turns out  that on the lattice such an average is not needed because the functional integral in Eq. (1.3) is already invariant under arbitrary gauge transformation of $`A^{(i)}`$ and $`A^{(f)}`$. The lattice implementation of the Schrödinger functional Eq. (1.3) is given by :

$$𝒵[U^f,U^i]=𝒟Ue^S,$$
(1.5)
where the integrations over the links $`U_\mu (x)`$ are done with the fixed boundary conditions:

$$U(x)|_{x_4=0}=U^{(i)},U(x)|_{x_4=T}=U^{(f)}.$$
(1.6)
The links $`U^{(i)}`$ and $`U^{(f)}`$ are the lattice version of the continuum gauge fields $`A^{(i)}`$ and $`A^{(f)}`$.
In Ref.  we introduced the new functional:

$$\mathrm{\Gamma }[\stackrel{}{A}^{\mathrm{ext}}]=\frac{1}{T}\mathrm{ln}\left\{\frac{𝒵[U^{\mathrm{ext}}]}{𝒵(0)}\right\},$$
(1.7)
where

$$𝒵[U^{\mathrm{ext}}]=𝒵[U^{\mathrm{ext}},U^{\mathrm{ext}}],$$
(1.8)
and $`𝒵[0]`$ means the Schrödinger functional Eq. (1.8) without external background field ($`U_\mu ^{\mathrm{ext}}=\mathrm{𝟏}`$).
From the previous discussion it is evident that $`𝒵[U^{\mathrm{ext}}]`$ is invariant against lattice gauge transformations of the external link $`U^{\mathrm{ext}}`$. Moreover, it can be shown that :

$$\underset{T\mathrm{}}{lim}\mathrm{\Gamma }[\stackrel{}{A}^{\mathrm{ext}}]=E_0[\stackrel{}{A}^{\mathrm{ext}}]E_0[0]$$
(1.9)
where $`E_0[\stackrel{}{A}^{\mathrm{ext}}]`$ is the vacuum energy in presence of the external background field. Thus we see that $`\mathrm{\Gamma }[\stackrel{}{A}^{\mathrm{ext}}]`$ is the lattice gauge-invariant effective action for the static background field $`\stackrel{}{A}^{\mathrm{ext}}`$. It is worthwhile to stress that our lattice effective action is defined by means of the lattice Schrödinger functional Eq. (1.5) with the same boundary fields at $`x_4=0`$ and $`x_4=T`$. As a consequence we have :

$$𝒵[U^{\mathrm{ext}}]=𝒟Ue^{S_W},$$
(1.10)
where $`S_W`$ is the familiar Wilson action and the functional integral is defined over a four-dimensional hypertorus with the “cold-wall” at $`x_4=0`$:

$$U_\mu (x)|_{x_4=0}=U_\mu ^{\mathrm{ext}}.$$
(1.11)
In previous studies  we investigated the vacuum dynamics of the SU(2) lattice gauge theory by using an external constant Abelian chromagnetic field. In that case the relevant quantity is the density of effective action:

$$\epsilon [\stackrel{}{A}^{\mathrm{ext}}]=\frac{1}{\mathrm{\Omega }}\mathrm{ln}\left[\frac{𝒵[A^{\mathrm{ext}}]}{𝒵[0]}\right],$$
(1.12)
where $`\mathrm{\Omega }=VT`$, $`V`$ being the spatial volume.
The aim of the present paper is twofold. First, we extend the study of the effective action with an external Abelian chromomagnetic field to the lattice SU(3) gauge theory at zero temperature. Second, we consider both SU(2) and SU(3) gauge systems at finite temperature.
At finite temperature the relevant quantity is the partition function :

$$\text{Tr}\left[e^{\beta _TH}\right]=𝒟\stackrel{}{A}\stackrel{}{A}\left|e^{\beta _TH}𝒫\right|\stackrel{}{A},$$
(1.13)
where $`\beta _T`$ is the inverse of the physical temperature. The thermal partition function Eq. (1.13) can be written as a functional integral :

$$\text{Tr}\left[e^{\beta _TH}\right]=_{A_\mu (\beta _T,\stackrel{}{x})=A_\mu (0,\stackrel{}{x})}𝒟A_\mu (t,\stackrel{}{x})e^{_0^{\beta _T}𝑑x_4{\scriptscriptstyle d^3\stackrel{}{x}_{YM}(\stackrel{}{x},x_4)}}.$$
(1.14)
The lattice implementation of Eq. (1.14) is straightforward. We have:

$$\text{Tr}\left[e^{\beta _TH}\right]=_{U_\mu (\beta _T,\stackrel{}{x})=U_\mu (0,\stackrel{}{x})=U_\mu (\stackrel{}{x})}𝒟U_\mu (x_4,\stackrel{}{x})e^{S_W}.$$
(1.15)
Note that, by comparing Eq. (1.15) with Eqs. (1.10), we have:

$$\text{Tr}\left[e^{\beta _TH}\right]=𝒟U_\mu (\stackrel{}{x})𝒵[U_\mu (\stackrel{}{x})],$$
(1.16)
where $`𝒵[U_\mu (\stackrel{}{x})]`$ is the Schrödinger functional Eq. (1.10) defined on a lattice with $`L_4=\beta _T`$, and “external” links $`U_\mu (\stackrel{}{x})`$ at $`x_4=0`$.
We are interested in the thermal partition function in presence of a given static background field $`\stackrel{}{A}^{\mathrm{ext}}(\stackrel{}{x})`$. In the continuum this can be obtained by splitting the gauge field into the background field $`\stackrel{}{A}^{\mathrm{ext}}(\stackrel{}{x})`$ and the fluctuating fields $`\stackrel{}{\eta }(\stackrel{}{x})`$. So that we could write formally:

$$𝒵_T[\stackrel{}{A}^{\mathrm{ext}}]=𝒟\stackrel{}{\eta }\stackrel{}{A}^{\mathrm{ext}},\stackrel{}{\eta }\left|e^{\beta _TH}𝒫\right|\stackrel{}{A}^{\mathrm{ext}},\stackrel{}{\eta }.$$
(1.17)
The lattice implementation of Eq. (1.17) can be obtained from Eq. (1.15) if we write

$$U_k(\beta _T,\stackrel{}{x})=U_k(0,\stackrel{}{x})=U_k^{\text{ext}}(\stackrel{}{x})\stackrel{~}{U}_k(\stackrel{}{x}),$$
(1.18)
where $`U_k^{\text{ext}}(\stackrel{}{x})`$ is the lattice version of the external continuum field $`\stackrel{}{A}^{\mathrm{ext}}`$ and the $`\stackrel{~}{U}_k(\stackrel{}{x})`$’s are the fluctuating links. Thus we get:

$$𝒵_T[\stackrel{}{A}^{\mathrm{ext}}]=_{x_4=0}𝒟\stackrel{~}{U}_k(\stackrel{}{x})𝒟U_4(\stackrel{}{x})𝒵[U_k^{\text{ext}}(\stackrel{}{x}),\stackrel{~}{U}_k(\stackrel{}{x})].$$
(1.19)
Note that in Eq. (1.19) only the spatial links belonging to the hyperplane $`x_4=0`$ are written as the product of the external link $`U_k^{\text{ext}}(\stackrel{}{x})`$ and the fluctuating links $`\stackrel{~}{U}_k(\stackrel{}{x})`$. The temporal links $`U_4(x_4=0,\stackrel{}{x})`$ are left freely fluctuating. It follows that the temporal links $`U_4(x)`$ satisfy the usual periodic boundary conditions. We stress that the periodic boundary conditions in the temporal direction are crucial to retain the physical interpretation that the functional $`𝒵_T[\stackrel{}{A}^{\text{ext}}]`$ is a thermal partition function. In the following the spatial links belonging to the time-slice $`x_4=0`$ will be called “frozen links”, while the remainder will be the “dynamical links”. From the physical point of view we are considering the gauge system at finite temperature in interaction with a fixed external background field. As a consequence, in the Wilson action $`S_W`$ we keep only the plaquettes built up with the dynamical links or with dynamical and frozen links. With these limitations it is easy to see that in Eq. (1.19) we have:

$$𝒵[U_k^{\text{ext}}(\stackrel{}{x}),\stackrel{~}{U}_k(\stackrel{}{x})]=𝒵\left[U_k^{\text{ext}}(\stackrel{}{x})\right].$$
(1.20)
Indeed, let us consider an arbitrary frozen link $`U_k^{\text{ext}}(\stackrel{}{x})\stackrel{~}{U}_k^{\text{ext}}(\stackrel{}{x})`$. This link enters in the modified Wilson action by means of the plaquette:

$$P_{k4}(x_4=0,\stackrel{}{x})=\text{Tr}\left\{U_k^{\text{ext}}(\stackrel{}{x})\stackrel{~}{U}_k^{\text{ext}}(\stackrel{}{x})U_4(0,\stackrel{}{x}+\widehat{k})U_k^{}(1,\stackrel{}{x}+\widehat{k})U_4^{}(0,\stackrel{}{x})\right\}.$$
(1.21)
Now we observe that the link $`U_4(0,\stackrel{}{x}+\widehat{k})`$ in Eq. (1.21) is dynamical, i.e. we are integrating over it. So that, by using the invariance of the Haar measure we obtain:

$$P_{k4}(x_4=0,\stackrel{}{x})=\text{Tr}\left\{U_k^{\text{ext}}(\stackrel{}{x})U_4(0,\stackrel{}{x}+\widehat{k})U_k^{}(1,\stackrel{}{x}+\widehat{k})U_4^{}(0,\stackrel{}{x})\right\}.$$
(1.22)
It is evident that Eq. (1.22) in turns implies Eq. (1.20). Then, we see that in Eq. (1.19) the integration over the fluctuating links $`\stackrel{~}{U}_k(\stackrel{}{x})`$ gives an irrelevant multiplicative constant. So that we obtain:

$$𝒵_T\left[\stackrel{}{A}^{\text{ext}}\right]=_{U_k(\beta _T,\stackrel{}{x})=U_k(0,\stackrel{}{x})=U_k^{\text{ext}}(\stackrel{}{x})}𝒟Ue^{S_W},$$
(1.23)
where the integrations are over the dynamical links with periodic boundary conditions in the time direction. As concern the boundary conditions at the spatial boundaries, we keep the fixed boundary conditions $`U_k(\stackrel{}{x},x_4)=U_k^{\text{ext}}(\stackrel{}{x})`$ used in the Schrödinger functional Eq. (1.10). We stress that, if we send the physical temperature to zero, then the thermal functional Eq. (1.23) reduces to the zero-temperature Schrödinger functional Eq. (1.5) with the constraints $`U_k(x)|_{x_4=0}=U_k^{\mathrm{ext}}(\stackrel{}{x})`$ instead of Eq. (1.11). In our previous studies  we checked that in the thermodynamic limit both conditions agree as concern the zero-temperature effective action Eq. (1.7).
The plan of the paper is as follows. In Section 2 we consider the Abelian constant chromomagnetic background field for the pure gauge SU(3) lattice theory at zero temperature. Section 3 is devoted to the study of both SU(2) and SU(3) lattice theories at finite temperature in presence of the external background field. Finally our conclusions are drawn in Section 4.

## 2. SU(3) IN A CONSTANT CHROMOMAGNETIC FIELD

We are interested in the case of a constant Abelian chromomagnetic field which in the continuum reads:

$$\stackrel{}{A}_a^{\mathrm{ext}}(\stackrel{}{x})=\stackrel{}{A}^{\mathrm{ext}}(\stackrel{}{x})\delta _{a,3},\stackrel{}{A}_k^{\mathrm{ext}}(\stackrel{}{x})=\delta _{k,2}x_1H.$$
(2.1)
The lattice links corresponding to $`\stackrel{}{A}^{\mathrm{ext}}(\stackrel{}{x})`$ can be evaluated from:

$$U_\mu =\mathrm{P}\mathrm{exp}\left\{ig_0^1𝑑tA_\mu (x+t\widehat{\mu })\right\}$$
(2.2)
where $`\mathrm{P}`$ is the path-ordering operator, and $`A_\mu =A_\mu ^a\frac{\lambda ^a}{2}`$, the $`\lambda ^a`$’s being the Gell-Mann matrices. From Eqs. (2.1) and (2.2) we get:

$`U_1^{\mathrm{ext}}(\stackrel{}{x})=`$ $`U_3^{\mathrm{ext}}(\stackrel{}{x})=U_4^{\mathrm{ext}}(\stackrel{}{x})=\mathrm{𝟏}`$
$`U_2^{\mathrm{ext}}(\stackrel{}{x})=`$ $`\left[\begin{array}{ccc}e^{i\frac{gHx_1}{2}}& 0& 0\\ 0& e^{i\frac{gHx_1}{2}}& 0\\ 0& 0& 1\end{array}\right].`$ (2.3)
Our Schrödinger functional Eq. (1.10) is defined on a lattice with the hypertorus geometry, for it is natural to impose that:

$$U_2(x_1,x_2,x_3,x_4)=U_2(x_1+L_1,x_2,x_3,x_4),$$
(2.4)
where $`L_1`$ is the lattice extension in the $`x_1`$ direction (in lattice units). As a consequence the magnetic field $`H`$ turns out to be quantized:

$$\frac{gH}{2}=\frac{2\pi }{L_1}n_{\mathrm{ext}},$$
(2.5)
with $`n_{\mathrm{ext}}`$ integer.
According to the discussion of the previous Section, in evaluating the lattice functional integral Eq. (1.10) we impose that links belonging to the time slice $`x_4=0`$ are frozen to the configuration Eq. (2.). Moreover we impose also that the links at the spatial boundaries are fixed according to Eq. (2.). In the continuum this last condition amounts to the usual requirement that the fluctuations over the background fields vanish at infinity.
An alternative possibility is given by constraining the links belonging to the the time slice $`x_4=0`$ and those at the spatial boundaries to the condition

$$U_k(x)=U_k^{\mathrm{ext}}(\stackrel{}{x}),k=\mathrm{\hspace{0.17em}1},2,3$$
(2.6)
while the links $`U_4(x)`$ are unconstrained. Note that with the condition Eq. (2.6) the time-like plaquettes nearest the frozen hypersurface $`x_4=0`$ behave symmetrically in the update procedure. Moreover, in this way the Schrödinger functional Eq. (1.10) is the zero-temperature limit of the thermal partition functional Eq. (1.23). In our previous studies  we checked that in the thermodynamic limit both conditions agree as the effective action is concerned.
Our numerical simulations at zero temperature have been done on a lattice of size $`L_1L_2L_3L_4`$ with $`L_1=L_4=32`$, while the transverse size $`L_1=L_2=L_{}`$ has been varied from $`L_{}=8`$ up to $`L_{}=32`$. To avoid the problem of computing a partition function which is the exponential of an extensive quantity we consider the derivative of the density of effective action $`\epsilon [\stackrel{}{A}^{\mathrm{ext}}]`$ Eq. (1.12) with respect to $`\beta `$ by taking $`n_{\mathrm{ext}}`$ (i.e. $`gH`$) fixed. Indeed, we have

$`\epsilon ^{}[\stackrel{}{A}^{\mathrm{ext}}]={\displaystyle \frac{\epsilon [\stackrel{}{A}^{\mathrm{ext}}]}{\beta }}={\displaystyle \frac{1}{\mathrm{\Omega }}}[{\displaystyle \frac{1}{𝒵[U^{\mathrm{ext}}]}}{\displaystyle \frac{𝒵[U^{\mathrm{ext}}]}{\beta }}`$ (2.7)
$`{\displaystyle \frac{1}{𝒵[0]}}{\displaystyle \frac{𝒵[0]}{\beta }}]={\displaystyle \frac{1}{\mathrm{\Omega }}}{\displaystyle \underset{x,\mu >\nu }{}}{\displaystyle \frac{1}{3}}\mathrm{Re}\mathrm{Tr}U_{\mu \nu }(x)_0`$
$`{\displaystyle \frac{1}{\mathrm{\Omega }}}{\displaystyle \underset{x,\mu >\nu }{}}{\displaystyle \frac{1}{3}}\mathrm{Re}\mathrm{Tr}U_{\mu \nu }(x)_{\stackrel{}{A}^{\mathrm{ext}}},`$
where the subscripts on the average indicate the value of the external links at the boundaries, and the $`U_{\mu \nu }(x)`$’s are the plaquettes in the $`(\mu ,\nu )`$ plane. Actually, the contributions to $`\epsilon ^{}[\stackrel{}{A}^{\mathrm{ext}}]`$ due to the frozen time-slice at $`x_4=0`$ and the fixed links at the spatial boundaries must be subtracted. Accordingly, we define the derivative of the internal energy density:

$`\epsilon _{\mathrm{int}}^{}[\stackrel{}{A}^{\mathrm{ext}}]={\displaystyle \frac{1}{\mathrm{\Omega }_{\mathrm{int}}}}{\displaystyle \underset{x\stackrel{~}{\mathrm{\Lambda }},\mu >\lambda }{}}{\displaystyle \frac{1}{3}}\mathrm{Re}\mathrm{Tr}U_{\mu \nu }(x)_0`$ (2.8)
$`{\displaystyle \frac{1}{\mathrm{\Omega }_{\mathrm{int}}}}{\displaystyle \underset{x\stackrel{~}{\mathrm{\Lambda }},\mu >\lambda }{}}{\displaystyle \frac{1}{3}}\mathrm{Re}\mathrm{Tr}U_{\mu \nu }(x)_{\stackrel{}{A}^{\mathrm{ext}}},`$
where $`\stackrel{~}{\mathrm{\Lambda }}`$ is the ensemble of the internal lattice sites which occupy the volume $`\mathrm{\Omega }_{\mathrm{int}}`$.
To implement the constraint at the boundaries in the numerical simulations we update only the internal links, i.e. the links $`U_\mu (x)`$ with $`x\stackrel{~}{\mathrm{\Lambda }}`$. We use the over-relaxed heat-bath algorithm to update the gauge configurations. Simulations have been performed by means of the APE100 computer. Since we are measuring a local quantity such as the plaquette, a low statistics (from 1000 up to 5000 configurations) is required in order to get a good estimate of $`\epsilon _{\mathrm{int}}^{}`$.

In Figure 1 we display the derivative of the energy density normalized to the derivative of the external energy density:

$$\epsilon _{\mathrm{ext}}^{}=\frac{2}{3}[1\mathrm{cos}(\frac{gH}{2})]=\frac{2}{3}[1\mathrm{cos}(\frac{2\pi }{L_1}n_{\mathrm{ext}})]$$
(2.9)
versus $`\beta `$ for $`L_1=L_4=32`$ and $`8L_{}32`$. From Figure 1 we see that, as in the SU(2) gauge theory , both the peak and the perturbative plateau of $`\epsilon _{\mathrm{int}}^{}`$ decrease by increasing $`L_{}`$. In order to perform the thermodynamic limit we introduce the scaling variable:

$$x=\frac{a_H}{L_{\mathrm{eff}}},$$
(2.10)
where

$$a_H=\sqrt{\frac{2\pi }{gH}}$$
(2.11)
is the magnetic length, and

$$L_{\mathrm{eff}}=\mathrm{\Omega }_{\mathrm{int}}^{1/4}$$
(2.12)
is the lattice effective linear size. As in the SU(2) case  we try the scaling law:

$$x^\alpha \frac{\epsilon _{\mathrm{int}}^{}(\beta ,n_{\mathrm{ext}},L_{\mathrm{eff}})}{\epsilon _{\mathrm{ext}}^{}}=\kappa (\beta ).$$
(2.13)
Indeed, from Figure 2 we see that our numerical data can be arranged on the scaling curve $`\kappa (\beta )`$. It is remarkable that the value of the exponent $`\alpha =1.5`$ in Eq. (2.13) agrees with the one we found for the SU(2) gauge theory . From Eq. (2.13) we can determine the infinite volume limit of the vacuum energy density $`\epsilon _{\mathrm{int}}`$. We have:

$$\underset{L_{\mathrm{eff}}\mathrm{}}{lim}\epsilon _{\mathrm{int}}(\beta ,n_{\mathrm{ext}},L_{\mathrm{eff}})=\epsilon _{\mathrm{ext}}^{}_0^\beta 𝑑\beta ^{}\kappa (\beta ^{})\underset{L_{\mathrm{eff}}\mathrm{}}{lim}\left(\frac{a_H}{L_{\mathrm{eff}}}\right)^\alpha =0$$
(2.14)
in the whole range of $`\beta `$. As a consequence, in the continuum limit $`(L_{\mathrm{eff}}\mathrm{},\beta \mathrm{})`$ the SU(3) vacuum screens the external chromomagnetic Abelian field in accordance with the dual superconductivity scenario .

## 3. FINITE TEMPERATURE BACKGROUND FIELD EFFECTIVE ACTION

Let us consider the gauge systems in an external chromomagnetic Abelian field at finite temperature. According to the discussion in Section 1, we are interested in the thermal partition function $`𝒵_T\left[\stackrel{}{A}^{\text{ext}}\right]`$, Eq. (1.23). On the lattice the physical temperature $`T_{physical}`$ is given by:

$$\frac{1}{T_{physical}}=L_t$$
(3.1)
where $`L_t=L_4`$ is the linear extension in the time direction. In order to approximate the thermodynamic limit, the spatial extension $`L_s`$ should respect the relation:

$$L_sL_t.$$
(3.2)
To this end we perform our numerical simulation on $`32^3\times L_t`$ and $`64^3\times L_t`$ lattices by imposing:

$$\frac{L_t}{L_s}\mathrm{\hspace{0.17em}4}.$$
(3.3)
At finite temperature the effective action is defined through the free energy:

$$F[\stackrel{}{A}^{\mathrm{ext}}]=\frac{1}{L_t}\mathrm{ln}\left\{\frac{𝒵_T\left[\stackrel{}{A}^{\text{ext}}\right]}{𝒵_T(0)}\right\}.$$
(3.4)
Obviously, in the case of constant external chromagnetic field the relevant quantity is the density of effective action:

$$f[\stackrel{}{A}^{\mathrm{ext}}]=\frac{1}{V}F[\stackrel{}{A}^{\mathrm{ext}}].$$
(3.5)
As is well known, by increasing the temperature the pure gauge system undergoes the deconfinement phase transition. In the case of pure SU(N) gauge theories it is known that the expectation value of the Polyakov loop in the time direction

$$P=\frac{1}{V_s}\underset{\stackrel{}{x}}{}\frac{1}{N}\text{Tr}\underset{x_4=1}{\overset{L_t}{}}U_4(\stackrel{}{x},x_4)$$
(3.6)
is the order parameter for the deconfinement phase transition. As a preliminary step we look at the behavior of the temporal Polyakov loop versus the external applied field. We start with the SU(2) gauge system at $`\beta =2.5`$ on $`32^3\times 5`$ lattice at zero applied external field (i.e. $`n_{\mathrm{ext}}=0`$) that is known to be in the deconfined phase of finite temperature SU(2). If the external field strength is increased the expectation value of the Polyakov loop is driven towards the value at zero temperature (see Fig. 3). It is worthwhile to stress that this last result is consistent with the dual superconductor mechanism of confinement. Similar behavior has been reported by Authors of Refs.  within a different approach. If we now consider the SU(2) gauge system at zero temperature in a constant Abelian chromomagnetic background field of fixed strength ($`n_{\mathrm{ext}}=1`$) and increase the temperature, we find that the perturbative tail of the $`\beta `$-derivative of the free energy density $`f_{\mathrm{int}}^{}(\beta ,n_{\mathrm{ext}})/\epsilon _{\mathrm{ext}}^{}`$ increases with $`1/L_t`$ and tends towards the “classical” value $`f_{\mathrm{int}}^{}(\beta ,n_{\mathrm{ext}})/\epsilon _{\mathrm{ext}}^{}1`$ (see Fig. 4). Therefore we may conclude that, as the temperature increases, there is no screening effect in the free energy density, confirming that the zero-temperature screening of the external field is related to the confinement.

The knowledge of $`f_{\mathrm{int}}^{}(\beta ,n_{\mathrm{ext}})/\epsilon _{\mathrm{ext}}^{}`$ at finite temperature can be used to estimate the deconfinement temperature $`T_c`$. In Figure 5 we magnify the peak region for different values of $`L_t`$. We see clearly that the pseudocritical coupling $`\beta ^{}(L_t)`$ depends on $`L_t`$. To determine the pseudocritical couplings we parametrize $`f_{\mathrm{int}}^{}(\beta ,L_t)`$ near the peak as:

$$\frac{f_{\mathrm{int}}^{}(\beta ,L_t)}{\epsilon _{\mathrm{ext}}^{}}=\frac{a_1(L_t)}{a_2(L_t)[\beta \beta ^{}(L_t)]^2+1}.$$
(3.7)
We restrict the region near $`\beta ^{}(L_t)`$ until the fits Eq. (3.7) give a reduced $`\chi ^2/\text{d}.o.f.1`$.
Having determined $`\beta ^{}(L_t)`$ we estimate the deconfinement temperature as:

$$\frac{T_c}{\mathrm{\Lambda }_{\mathrm{latt}}}=\frac{1}{L_t}\frac{1}{f(\beta ^{}(L_t))},$$
(3.8)
where

$$f(\beta )=\left(\frac{\beta }{2Nb_0}\right)^{51/121}\mathrm{exp}\left(\beta \frac{1}{4Nb_0}\right),$$
(3.9)
where $`b_0=(11N)/(48\pi ^2)`$ and $`N`$ is the color number. In Figure 6 we display $`T_c/\mathrm{\Lambda }_{\mathrm{latt}}`$ for different temperatures. Following Ref.  we linearly extrapolate to the continuum our data for $`T_c/\mathrm{\Lambda }_{\mathrm{latt}}`$. In this way we obtain the following estimate of the critical temperature in the continuum limit

$$\frac{T_c}{\mathrm{\Lambda }_{\mathrm{latt}}}=\mathrm{\hspace{0.17em}28.36}\pm \mathrm{\hspace{0.17em}1.38}.$$
(3.10)
Equation (3.10) is to be compared with the continuum limit of the critical temperature available in the literature

$$\frac{T_c}{\mathrm{\Lambda }_{\mathrm{latt}}}=\mathrm{\hspace{0.17em}24.38}\pm \mathrm{\hspace{0.17em}2.18}.$$
(3.11)
Our result Eq. (3.10) agrees, within two standard deviations, with the result given in Eq. (3.11). Note, however, that the small discrepancy could be a true dynamical effect due to the external chromomagnetic field. Indeed, the behaviour of the Polyakov loop versus the external background field displayed in Fig. 3 seems to suggest that the critical temperature does depend on the applied background field. For dimensional reasons one expects that:

$$T_c^2H.$$
(3.12)
To check the expected behaviour Eq. (3.12) we need to vary the external chromomagnetic field. We plan to do this study in a future work.
For the time being, let us turn to the SU(3) pure gauge lattice theory at finite temperature. In this paper we limit ourselves to present our determination of the critical deconfinement temperature. In Figure 7 we display the peak region of the internal free energy density for different values of $`L_t`$, together with the fits Eq. (3.7). Having determined the pseudocritical couplings, the deconfinement temperature can be obtained from Eq.(3.8). Performing the linear extrapolation to the continuum limit we get:

$$\frac{T_c}{\mathrm{\Lambda }_{\mathrm{latt}}}=\mathrm{\hspace{0.17em}20.86}\pm \mathrm{\hspace{0.17em}3.02}.$$
(3.13)
Our estimate Eq. (3.13) is in fair agreement with the continuum limit of the SU(3) critical temperature available in the literature

$$\frac{T_c}{\mathrm{\Lambda }_{\mathrm{latt}}}=\mathrm{\hspace{0.17em}29.67}\pm \mathrm{\hspace{0.17em}5.47}.$$
(3.14)
However, we note once more that our data do not exclude a dependence of the critical temperature on the external chromomagnetic field.

## 4. CONCLUSIONS

We have studied the non-perturbative dynamics of the vacuum of SU(2) and SU(3) lattice gauge theories by means of a gauge-invariant effective action defined using the lattice Schrödinger functional.

At zero temperature our numerical results indicate that even for the more interesting case of the SU(3) theory, in the continuum limit $`L_{\mathrm{eff}}\mathrm{}`$, $`\beta \mathrm{}`$ we have:

$$\epsilon [\stackrel{}{A}^{\mathrm{ext}}]=0,$$
(4.1)
so that the SU(3) vacuum screens completely the external chromomagnetic Abelian field. In other words, the continuum vacuum behaves as an Abelian magnetic condensate medium in accordance with the dual superconductivity scenario.

The intimate connection between the screening of the external background field and the confinement is corroborated by the finite temperature results. Indeed our numerical data show that the zero-temperature screening of the external field is removed by increasing the temperature. Moreover, at finite temperature it seems that confinement is restored by increasing the strength of the external applied field.

At finite temperature we find that the $`\beta `$-derivative of the free energy density behaves like a specific heat. From the peak position of the $`\beta `$-derivative of the free energy density we obtained an estimate of the critical temperature $`T_c/\mathrm{\Lambda }_{\mathrm{latt}}`$ that extrapolates in the continuum limit to values in fair agreement with previous determinations in the literature. Moreover, our data are suggestive of a non-trivial dependence of the deconfinement critical temperature on the applied external chromagnetic field. We deserve to a future work the investigation of this interesting possibility.