Entropy of fully packed hard rigid rods on $d$-dimensional hyper-cubic lattices

We first show that $N(L,M)$ is non-zero, if and only if at least one of $L$ and $M$ is divisible by $k$. The ‘if’ part is trivial. For the other part, clearly $LM$ has to be a multiple of $k$, for full coverage. We now argue that in this case, at least one of $L$ and $M$ has to be a multiple of $k$.

Assign one of the $k$ colors, called here $0,1,2,\ldots,(k-1)$ to each of the squares of the lattice, with square $(x,y)$ given color $q=(x-y)\mod k$. The coloring of the squares for the case $k=3$ is shown in Fig. 2. Then each $k$-mer covers exactly one square of each color. Let $L=k~{}\ell+\alpha$, $M=k~{}m+\beta$, with $0<\alpha,\beta\leq k-1$. Divide the rectangle into three smaller rectangles of sizes $k\ell\times M,\alpha\times km$ and $\alpha\times\beta$, as shown in Fig. 3. Then, clearly the rectangles of size $k\ell\times M$, and $\alpha\times km$ can be covered by $k$-mers, implying that the number of squares of different colors in these two rectangles are equal. However, the small rectangle of size $\alpha\times\beta$ has $\min(\alpha,\beta)$ squares of same color along the diagonal. To cover them would require at least $\min(\alpha,\beta)$ rods, with total area $k\min(\alpha,\beta)$. Equating this to the total area $\alpha\beta$, we obtain $k=\max(\alpha,\beta)$. This contradicts the assumption that $\alpha,\beta<k$. Hence, the rectangle can not be fully covered by $k$-mers, unless either $L$ or $M$ is divisible by $k$.

For simplicity of presentation, in the following, we shall assume that both $L$ and $M$ are multiples of $k$.

In this subsection, we show that all configurations of rods can be reached from any configurations by just using the flip move (defined below).

We define the standard tiling configuration of $k\ell\times M$ rectangle by $k$-mers as one using only horizontal $k$-mers. A basic flip move is defined as replacing a $k\times k$ square filled with vertical $k$-mers by one with horizontal $k$-mers, and vice versa, as illustrated in Fig. 4.

A combination of two flip moves defines a ‘slide’ move, where a vertical $k$-mer next to a $k\times k$ flippable square exchanges position (see Fig. 5), and the vertical $k$-mer will be said to slide across the flippable square.

We now argue that that any full tiling of $k\ell\times M$ rectangle by $k$-mers may be reached from the standard configuration by using only the basic flip and slide moves.

Proof: Look at the lowest row. If it consists of only horizontal $k$-mers, then we ignore this row, and the problem reduces to one with a smaller $M$. Else, it would have $\ell^{\prime}=\ell-\Delta$ horizontal $k$-mers, and $k\Delta$ vertical $k$-mers. In Fig. 6, we have shown an example of a $4$-mer tiling of a $48\times 12$ rectangle, where $\ell=12$, $\Delta=1$. We move to the left any $k\times k$ block of horizontal flippable rods we find between these $k\Delta$ vertical $k$-mers, using the slide move, and make the vertical rods closer to each other. If now there is any block of consecutive vertical $k$-mers, we can flip these to horizontal, and reduce the problem to one with fewer number of vertical $k$-mers.

If there is no such horizontal flippable block of rods, we look at the bottom row. Let us say that it has segments of $i_{1},i_{2},...i_{s}$ horizontal rods, interspersed with vertical rods. [In Fig. 6, there are $4$ segments, with $i_{1}=1$, $i_{2}=3$, $i_{3}=4$, $i_{4}=3$]. Clearly, these are bordered by vertical $k$-mers at the ends, unless the segment itself is at the end of the rectangle. Then we look at the sub-rectangles of sizes $i_{1}k\times M,i_{2}k\times M,..$ made up of these segments and bounded by vertical boundaries. In the example shown in Fig. 6, these rectangles are shown with orange boundaries.

We now argue that there will be a flippable $k\times k$ block within each of these small rectangles. This is clear if the width of the rectangle is exactly $k$. Then the sites just above can only be covered by a horizontal rod, or $k$ vertical rods. In the latter case, it forms a vertical flippable rectangle. If not, then eventually, we will have $k$ horizontal rods just above each other, and form a horizontal flippable rectangle.

If the width is greater than $k$, and the row just above is not made of all horizontal rods, then it will be made up of a number of horizontal segments, separated by vertical rods. And we can repeat the argument with this smaller set. This process can not continue for ever, as the total width is finite, and the width decreases at each step.

Thus, we will be able to find a flippable $k\times k$ box at each stage, and eventually, the number of vertical rods becomes zero, and the standard tiling of all horizontal $k$-mers is reached. Since all moves are reversible, and any valid configuration of full-packing can be changed to standard configuration, we can go from any full packing configuration on the rectangle to any other using only flip moves.

We can easily obtain a better lower bound on $S_{2}(k)$. Break the $L\times kM$ lattice in $M$ strips of width $k$ each. Let $N(L,k)$ be denoted by $F_{L}$. Since by breaking into strips of width $k$, we disallow configurations where rods cross the boundary, leading to undercounting, we obtain the inequality

$F_{L}$ obeys a simple recursion relation. Consider the packing of a $k\times L$ rectangle. The first row can be covered by a horizontal $k$-mer (reducing $L$ by one) or the first $k\times k$ square can be covered $k$ parallel vertical $k$-mers (reducing $L$ by $k$). Thus, $F_{L}$’s satisfy the recursion relation

This implies that $F_{L}$ increases as $\lambda^{L}$ where $\lambda$ is the largest root of the equation

For large $k$, to leading order $\lambda=1$. A little bit of algebra shows that In the limit of large $k$, the subleading terms take the form

where $W(k)$ is the solution of the equation

The function $W(k)$ is called the Lambert function [71]. To leading order, $W(k)\sim\ln k$ for large $k$ (to see this, take logarithm on both sides of Eq. (7) and compare the terms of leading order). The sub-leading term can be similarly obtained to give for large $k$

with corrections that only grow slower than $\ln(\ln k)$. Thus we obtain

The entropy per site for the $k\times\infty$ strip is $(\ln\lambda)/k$. Thus,

Since $S_{k\times\infty}$ is a lower bound for $S_{2}(k)$, we obtain the leading behavior:

In this subsection, we describe the exact calculation of the entropy of tilings of the semi-infinite $2k\times\infty$ stripe with $k$-mers, where the $y$-coordinate is $\geq 1$, and the $x$-coordinate lies in the range $[1,2k]$. We define the generating function $\Omega_{2k}(x)$ as the sum over all covering of rectangles of size $2k\times r$, summed over all positive integer values of $r$, where the weight of a covering with $n$ tiles is $z^{n}$. Then, we have

We also define a partial covering of the strip with rods to the bottom of some reference line $y=s>0$, so that no site with $y$-coordinate less than $s$ is left uncovered (see Fig. 8), and all rods must cover at least one site with $y$-coordinate less than $s$. Clearly, all rods that do not lie completely to the bottom of the $y=s$ must be vertical. A partial covering is a rectangular covering iff no site with $y$-coordinate larger than $s$ is covered.

A partial covering may be characterized by its top boundary $\{h_{x}\}$, for $x=1$ to $2k$, where $h_{x}$ specifies how many sites to the top of the reference line $y=s$ are covered in the column with coordinate $x$. We will choose $s$ to be as large as possible, so that at least one of the $h_{x}$’s has to be zero, and $h_{x}\leq k-1$, for all $x$. For example, the boundary of the configuration shown in Fig. 8 is specified by $\{0,0,3,3,3,3,0,0\}$. In a more compact notation, we will write this as $\{0^{2}3^{4}0^{2}\}$.

Not all height configurations are allowed. A bit of thought shows that for a partial covering of the $2k\times L$ stripe, the only allowed height configurations are $\{0^{2k}\}$, $\{h^{k}0^{k}\}$, $\{0^{k}h^{k}\}$, $\{h^{j}0^{k}h^{k-j}\}$ or $\{0^{j}h^{k}0^{k-j}\}$, with $h$ and $j$ taking values from $1$ to $k-1$.

We define the generating functions $\psi(\{h_{j}\})$ as the generating function of all possible ways of completing a partial tilings with a given height profile $\{h_{j}\}$, where the completed covering is rectangular, and the weight of tiling in which we add $n$ extra rods is $z^{n}$. Therefore, for example,

Consider a particular height configuration $\{h_{x}\}$. We can write recursion equations for the corresponding generating function $\psi(\{h_{x}\})$, by considering all possible ways of filling the column of sites immediately to the top of the reference line by $k$-mers, such that the top edge of the full tiling is horizontal, and no sites are left uncovered.

For example, it is easily seen that (see Fig. 9)

The different terms in this equation correspond to the cases where the next row is left empty, or filled by two horizontal rods, or by $2k$ vertical rods, or by first $j$ vertical rods, then a horizontal rod, then $k-j$ vertical rods.

Writing such generating functions for all possible height configurations, we obtain a set of inhomogeneous linear equations in approximately $2k^{2}$ variables. This may be written as a transfer matrix of dimension $2k^{2}\times 2k^{2}$. However, using the symmetries of the problem, this number can be considerably reduced.

We note that the recursion equations for the generating function $\Psi(\{h^{j}0^{k}h^{k-j}\}$ is

This equation has no $j$-dependence. Hence, we may expect that $\Psi(\{h^{j}0^{k}h^{k-j}\}$ is independent of $j$. It can be checked that this ansatz is consistent with the remaining recursion equations. Similarly, we find that $\Psi(\{0^{j}h^{k}0^{k-j}\})$ is also independent of $j$. With this simplification, the number of independent variables reduces to approximately $2k$.

The remaining recursion equations are easily written down, we obtain for all $1\leq h\leq k-1$,

and

Substituting for $\Psi(\{0^{j}(k-h)^{k}0^{k-j}\})$ in Eq. (16) from Eq. (17), we obtain

which is immediately solved to give

Substituting for $\Psi(\{(k-1)^{j}0^{k}(k-1)^{k-j}\})$ in Eq. (III.2) from Eq. (20) and simplifying, we obtain

To close the equations, we have to determine $\Psi(\{0^{k}h^{k}\})$ in terms of $\Psi(\{0^{2k}\})$. The values of $\Psi(\{0^{k}h^{k}\})$ for one value of $h$ are related by Eq. (18) to arguments $(h-1)$ and to $(k-h)$. This seems complicated, but it is easily checked that the ansatz

satisfies Eq. (18), so long as

Eliminating $C/D$ from Eq (23), we obtain

This is a quadratic equation in $\alpha$, and determines $\alpha$ for any given value of $z$. Explicitly, we obtain

Using Eq. (23), we can express $C$ and $D$ in terms of a single variable $\kappa$ :

The actual values of $C$ and $D$ can be determined from the boundary condition at $h=0$:

We obtain

Substituting for $\kappa$ in Eqs. (26) and (27), we obtain $C$ and $D$ in terms of $z$.

Finally, substituting the value of $C$ and $D$ in Eq. (22), we obtain

Equation (32) may be simplified by substituting for $z^{k}$ from Eq. (24):

Note the explicit symmetry of the expression under the exchange of $\alpha\leftrightarrow 1/\alpha$.

Substituting the expressions for $\alpha$, $\Psi(\{0^{k}(k-1)^{k}\})$ in Eq. (21), we obtain an explicit expression for $\Psi(\{0^{2k}\})$ of the form

where the denominator $E(z)$ equals

The entropy $S_{2k\times\infty}$ is given by $-k^{-1}\ln z_{2k}^{*}$, where $z_{2k}^{*}$ is the singularity of $\Psi(\{0^{2k}\})$ that is closest to the origin. We will show below that asymptotic behavior of entropy for strips of width $2k$ is the same as that of strips of width $k$. The explicit values of the entropies for strips $k\times\infty$ and $2k\times\infty$ for $k$ upto $2^{31}$ are given in Table 1, and compared with the asymptotic result $k^{-2}\ln k$ in Eq. (1).

We now determine the leading singularity $z_{2k}^{*}$ of $\Psi(\{0^{2k}\})$ in the limit $k\gg 1$. To do so, consider the denominator $E(z)$. It has a square root singularity at $z_{c}$ when the discriminant in Eq. (25) equals zero. By factorising the discriminant and writing in terms of the modulus of $z_{c}$, we obtain that $z_{c}$ satisfies the equation

identical to that satisfied by $z^{*}$ for the strip $k\times\infty$ [see Eq. (5) with $\lambda=1/z$]. For large $k$, it has the solution

We now show that $E(z)$ has a zero at $z_{2k}^{*}\lesssim z_{c}$. Following a bit of algebra, it can be shown that

Clearly, $E(z_{c})<0$, as $z_{c}<1$. At the same time, it is clear that $E(0)=1$ since $\Psi(\{0^{2k}\})|_{z=0}=1$. Therefore, there must be a zero $z_{2k}^{*}$ in $(0,z_{c})$, leading to a higher entropy for strips $2k\times\infty$, as evident in Table 1. Also as $E(z_{c})\to 0$ for large $k$, we expect that $z_{2k}^{*}\to z_{c}$ for large $k$.

We now show that the leading behavior of $z_{2k}^{*}$ and $z_{c}$ are identical for large $k$. We look for solutions

where $\eta/k^{\theta}\to 0$ for any $\theta>0$, and $\eta\to\infty$ for $k\gg 1$. In this limit, $\alpha\approx 1+\sqrt{4\eta/k}$, and after some algebra, $E(z^{*})$ may be simplified to give

Equating $E(z_{2k}^{*})$ to zero, we obtain

From direct substitution, it is straightforward to check that Eq. (41) is satisfied to leading order by $\eta=\ln k[1-\ln(\ln k)/(2\ln k]$. Equation (39) then gives

Since the entropy is given by $-\ln z_{2k}^{*}/k$, we obtain

The leading behaviour of $S_{2k\times\infty}$ coincides with that of $S_{k\times\infty}$ [see Eq. (10)]. The subleading term is different. We thus obtain the same lower bound as given in Eq. (11).

For general $L\times\infty$, though one can write down the recursion relations obeyed by different generating functions, it is not possible to find a closed form solution for them. Here, we provide an alternate analysis by determining a lower bound for the asymptotic behaviour of entropy of $L\times\infty$ strips, which will happen to coincide with the exact results for the strips $k\times\infty$ and $2k\times\infty$

We define the generating function

with $N(L,0)=1$, by convention. Then, by direct enumeration,

$\Omega_{L}(z)$ is sum of weights of all configurations of rods on a semi-infinite strip of width $L$, with the weight of a configuration of $n$ rods being $z^{n}$. We have the further constraint that all rods must lie fully in a rectangular region, with both bottom and top edge horizontal, and no uncovered regions within the rectangle. As a slightly more complicated example, it is easily seen that $\Omega_{k}(z)$ is the generating function for $k\times\infty$ strips, and hence,

In determining admissible tilings, a useful concept is that of concatenation. Given two tilings of rectangles of sizes $L\times M_{1}$ and $L\times M_{2}$, we define the vertical concatenation of these tilings as the tiling of size $L\times(M_{1}+M_{2})$, obtained by just putting the rectangles on top of each other in the order of concatenation. An illustration of vertical concatenation of three tilings is shown in Fig. 10. A horizontal concatenation is defined similarly.

A tiling is said to be vertically indecomposable, if it cannot be expressed as a vertical concatenation of two admissible tilings. For a vertically decomposable tiling, there is a horizontal line that divides the rectangle into two smaller tilings, such that no rod crosses the horizontal line.

We now define $R_{L}(z)$ as the sum of weights of all vertically indecomposable tilings of rectangles of width $L$. Clearly, $R_{L}(z)$ is a series in powers of $z$, with all coefficients as non-negative integers. Then, we have

Let the radius of convergence of the power series of $\Omega_{L}(z)$ be $z_{L}^{*}$. Then,

Since $R_{L}(z)$ is a series of positive coefficients, we may truncate the series at any order, and obtain an upper bound estimate of $z_{L}^{*}$, and hence of $z^{*}$, the limit of $z_{L}^{*}$, for large $L$. This, in turn, will provide a lower bound for the entropy.

We will take $L$ to be a multiple of $k$, as these give the best bounds. The simplest case is $L=k$. In this case, $R_{k}(z)$ is a finite polynomial, and we have

We see that this is consistent with Eq. (47).

Now, let us consider the more complicated case $L=2k$. In this case, $R_{2k}(z)$ is not a finite polynomial. But it has an interesting structure: the lowest order term is $z^{2}$, corresponding to a configuration of two horizontal k-mers side by side. But, then terms of order $z^{4},z^{6},\ldots$ are all zero, as the corresponding tilings are decomposable. The first non-zero term is of order $z^{2k}$, which corresponds to configurations consisting of a plaquette of $k$ aligned horizontal rods and $k$ vertical rods tiling the remaining area, and another of $2k$ vertical $k$-mers. With a small amount of brute force enumeration, it is easily seen that the plaquette can be placed in $(k+1)$ ways to give

If we truncate the equation at order $z^{2k}$, we obtain an upper bound estimate for $z_{2k}^{*}$. It turns out that for large $k$, the terms that have been dropped make only a negligible contribution to $R_{2k}(z)$ at $z=z_{2k}^{*}$. We will verify this claim later. First, we solve the truncated equation for $z_{2k}^{*}$:

Writing $z_{2k}^{*}=\exp(-B/k)$, we see that $(1-z_{2k}^{*2})\approx 2B/k$, if $k$ is large, to leading order in $k$, $B$ satisfies the equation

which has the solution $B\approx(1/2)W(k(k+2))$ [$W(z)$ being the Lambert function], which for large $k$ has the leading behavior

Since $S_{2k\times\infty}\geq-\ln(z_{2lk}^{*})/k$, we obtain

This is a bit larger than the estimate using strips of width $k$ [see Eq. (10)], but for large $k$, the leading behavior remains the same with the difference showing only in the sub-leading correction of order $(\ln\ln k)/k$. We also note that the bound for $S_{2k\times\infty}$ obtained by truncation coincides with the exact analysis [see Eq. (43)].

Now, the term of order $z^{2k+2}$ in $R_{2k}$ is only $2z^{2k+2}$, and its contribution to sum is smaller than that of the term of order $z^{2k}$ by a factor $(1/k)$. At higher orders, the term of order $z^{6k}$ has a coefficient of order $k^{3}$. Using the fact that $z^{k}$ is of order $1/k$, the net contribution of this term decreases as $1/k^{3}$. This also does not change the leading order $k$-dependence of $z_{2k}^{*}$.