Polynomials from tilings of rectangles

arXiv:2605.03473 · math.CO · Submitted 2026-05-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.

Ada: I'm Ada.

Emmy: And I'm Emmy, here with Kolya.

Ada: We're looking at the paper: "Polynomials from tilings of rectangles".

Title and authors: Ada: So we’re talking about this paper today, "Polynomials from tilings of rectangles," by John Ahlberg and Per Alexandersson. It looks like they've taken tiling problems on rectangular boards, using unit squares and these big Ferrers diagrams, and turned them into generating functions for counting.

Emmy: Exactly. The main point is that they don't just count how many ways you can tile something; they derive polynomials that have some really cool properties, specifically being real-rooted and forming interlacing sequences when dealing with two-column Ferrers shapes <ref:2605.03473#pg2>.

Kolya: Real-rootedness and interlacing sequences sound a bit abstract for a tiling problem, but if it holds up across different shapes, that suggests there's a deep structural reason behind the enumeration, not just some random counting sequence.

Ada: Right. And they do this by showing that the transfer matrix used in their setup actually preserves those interlacing pairs <ref:2605.03473#pg2>. They’re connecting the combinatorial tiling problem to spectral properties of matrices.

Emmy: It’s a strong connection because it shows that the structure of these tilings is deeply constrained by algebraic geometry or linear algebra concepts, which is usually not where you expect to find such nice polynomial behavior.

Ada: The paper goes on to look at specific cases, like tilings involving L-triominoes on a three by n board <ref:2605.03473#pg3>. This leads them to a specific recursion for the number of tilings, A n equals A n minus one plus two A n minus two plus A n minus three <ref:2605.03473#pg3> <ref:2605.03473#pg2>.

Kolya: That recursion, An equals An minus one plus two An minus two plus An minus three is interesting because it immediately tells us that this counting problem is related to how you can tile the three by n board using squares of sizes one by one square, two by two square, and three by three square <ref:2605.03473#pg3> <ref:2605.03473#pg2>.

Emmy: That interpretation connects the tiling structure directly to a different set of geometric objects—the squares themselves—which gives us a different way to visualize what’s happening on the board <ref:2605.03473#pg3>.

Ada: Then they introduce this tool called an anchor square, which is basically a specific square in a tile that helps them build bijections to tilings using L-polyominoes <ref:2605.03473#pg5>. They define an anchor word based on certain inequalities for the letters in the sequence <ref:2605.03473#pg6>.

Title and authors: Kolya: So, they use these words and this anchor square idea to create a direct one-to-one mapping between these words and actual tilings involving Lh-polyominoes <ref:2605.03473#pg6>. That seems like a very robust way to connect combinatorics with symbolic sequences.

Ada: They then track how many of those Lh-polyominoes are used by defining this generating polynomial Qd n t <ref:2605.03473#pg6>, which just counts the number of Lh-polyominoes in a tiling.

Emmy: The main thrust of this paper seems to be moving from these specific examples, like the three by n board or two-column Ferrers shapes, to a general framework for arbitrary Ferrers diagrams <ref:2605.03473#pg2>.

Ada: And they do that by introducing row-refined tiling polynomials S mu d n s one s1 plus one s2 plus... plus sd x n equals one over one minus x minus sigma i s x two <ref:2605.03473#pg8>. That polynomial tracks tiles based on their anchor square row, which is a key distinction <ref:2605.03473#pg7>.

Kolya: That generating function for those row-refined polynomials looks like it’s designed to capture the complexity of tiling across different rows simultaneously, governed by that sum over i sigma s x two <ref:2605.03473#pg8>.

Ada: And they use that to prove real-rootedness for the two-column Ferrers tiles, which is a central result <ref:2605.03473#pg2>. They show that the transfer matrix in equation twenty two preserves those interlacing pairs <ref:2605.03473#pg2>.

Emmy: That preservation property is what really locks everything down; it means that as you move from one tile to the next, this interlacing structure doesn't break down, which is a beautiful structural statement.

Ada: They also look at other variants like fault-free tilings and dense tilings <ref:2605.03473#pg2>, and they find that for certain conditions on the Ferrers shape mu and the parameter d, the conflict graph associated with these tilings is claw-free <ref:2605.03473#pg5>.

Kolya: A claw-free conflict graph suggests that there aren't many complex local interactions between tiles; it implies a certain level of simplicity in how these tiles can overlap or touch <ref:2605.03473#pg5>.

Title and authors: Ada: They also analyze fault lines in dense tilings using a generating function H mu d x s with real-rooted coefficient polynomials when B mu d x one has only real zeros <ref:2605.03473#pg47>. This connects the tiling structure to the zeroes of another polynomial, which is another way to prove stability <ref:2605.03473#pg10>.

Emmy: It seems they are building up a whole toolkit here: starting from simple recursion, moving to bijections with anchor words, then generalizing to arbitrary shapes and specific properties like claw-free graphs.

Ada: So what we have is a paper that starts with basic counting, uses structural tools like the anchor word bijection <ref:2605.03473#pg6>, and proves deep results about the polynomial behavior of these tilings for two-column Ferrers shapes <ref:2605.03473#pg2>.

Kolya: The real implication here for us probabilists is understanding what constraints on the structure of a tiling—like those claw-free conditions—translate into constraints on the analytic properties of these associated polynomials <ref:2605.03473#pg5>.

Ada: And as we move toward the end, they summarize how they use things like row-refined polynomials to analyze arbitrary Ferrers diagrams by introducing anchor words defined by implications <ref:2605.03473#pg17>.

Emmy: It’s a comprehensive approach; they aren't just proving one theorem about two-column shapes, they are establishing a general methodology for studying these tilings <ref:2605.03473#pg2>.

Ada: And that leads into the final wrap up where they discuss how the generating function F mu d x t is derived using those anchor words <ref:2605.03473#pg18>. It’s connecting all these pieces back to the initial counting problem.

Kolya: For someone just listening, what this means is that understanding a complex tiling pattern can be translated into studying the roots of a polynomial, which we know how to analyze better than direct enumeration <ref:2605.03473#pg2605>.three thousand four hundred seventy-three#pg2 <ref:2605.03473#pg1>.

Ada: So to wrap up our discussion on "Polynomials from tilings of rectangles," Ahlberg and Alexandersson have shown that tiling polynomials for two-column Ferrers shapes are real-rooted and form interlacing sequences <ref:2605.03473#pg2>.

Emmy: It’s a solid piece of work that connects geometry, combinatorics, and analysis through these tiling problems <ref:2605.03473#pg1>.

Kolya: I just think the connection they make between the structure of Lh-polyominoes and the counting sequence is quite elegant <ref:2605.03473#pg6>.

Ada: Indeed, and their use of anchor words as a primary tool for bijection is very helpful for seeing the underlying structure <ref:2605.03473#pg2>.

The paper's summary: Ada: So, to summarize this paper, Ahlberg and Alexandersson took tiling problems on rectangles—using unit squares and these big Ferrers shapes—and turned them into generating functions for counting those tilings <ref:2605.03473#pg2>.

Emmy: The real payoff here isn't just the count; they prove that for two-column rectangular Ferrers tiles, the polynomials you get from this setup are real-rooted and they form interlacing sequences <ref:2605.03473#pg2>.

Kolya: Real-rootedness is a big deal because it means the structure of those tilings isn't random; it’s tightly controlled by some underlying algebraic logic <ref:2605.03473#pg2>.

Ada: Exactly. They show that this happens because the transfer matrix used in their setup actually preserves those interlacing pairs, which is a strong structural statement <ref:2605.03473#pg2>.

Emmy: It connects the combinatorial world of fitting shapes together to something much more analytic, like spectral properties of matrices <ref:2605.03473#pg2>.

Kolya: And they do this by looking at specific cases, like tilings on a three by n board using L-triominoes, which leads to a specific recurrence relation for counting those things <ref:2605.03473#pg3>.

Ada: That recurrence is interesting because it shows that the count of those L-triomino tilings is actually the same as counting how you can tile that three by n board using squares of size one by one square, two by two square, and three by three square <ref:2605.03473#pg3>.

Emmy: So they’re linking the tiling process to a different set of geometric objects—the squares themselves—which gives us a different way to visualize the counting problem <ref:2605.03473#pg3>.

Kolya: Then they introduce this anchor square idea, which is used as a primary tool for setting up bijections between words and tilings involving Lh-polyominoes <ref:2605.03473#pg6>.

Ada: They define an anchor word based on certain inequalities for the letters in the sequence, and that helps them establish a direct one-to-one mapping to those Lh-polyomino tilings <ref:2605.03473#pg6>.

Emmy: That bijection is key because it lets them track how many of those Lh-polyominoes are used by defining this generating polynomial called Q t n <ref:2605.03473#pg6>.

Kolya: So they’re building these tools step by step, from the simplest recursion to these more complex bijections that help them count the tiles in a tiling <ref:2605.03473#pg6>.

Ada: The central theme is moving from those specific tilings to a general framework for arbitrary Ferrers diagrams <ref:2605.03473#pg2>.

Emmy: And they do this using row-refined tiling polynomials, which are defined by tracking tiles based on their anchor square row, distinguishing them by s one plus s two plus... plus sd x n <ref:2605.03473#pg7>.

Kolya: That generating function looks like it’s designed to capture the complexity of tiling across different rows simultaneously, governed by that sum over i sigma s x two <ref:2605.03473#pg8>.

Ada: And they use that to prove real-rootedness for the two-column Ferrers tiles, which is a major result <ref:2605.03473#pg2>. They show that the transfer matrix in equation twenty two preserves those interlacing pairs <ref:2605.03473#pg2>.

Emmy: That preservation property is what really locks everything down; it means that as you move from one tile to the next, this interlacing structure doesn't break down, which is a beautiful structural statement <ref:2605.03473#pg2>.

Kolya: They also look at other variants like fault-free tilings and dense tilings, and they find that for certain conditions on the Ferrers shape mu and the parameter d, the conflict graph associated with these tilings is claw-free <ref:2605.03473#pg5>.

Ada: A claw-free conflict graph suggests that there aren't many complex local interactions between tiles; it implies a certain level of simplicity in how these tiles can overlap or touch <ref:2605.03473#pg5>.

Emmy: It seems they are building up a whole toolkit here: starting from simple recursion, moving to bijections with anchor words, then generalizing to arbitrary shapes and specific properties like claw-free graphs <ref:2605.03473#pg2>.

Kolya: And that leads into the final wrap up where they discuss how they use things like row-refined polynomials to analyze arbitrary Ferrers diagrams by introducing anchor words defined by implications <ref:2605.03473#pg17>.

Ada: It’s a comprehensive approach; they aren't just proving one theorem about two-column shapes, they are establishing a general methodology for studying these tilings <ref:2605.03473#pg2>.

Emmy: And that connects all these pieces back to the initial counting problem through the generating function F mu d x t <ref:2605.03473#pg18>.

Kolya: For someone just listening, what this means is that understanding a complex tiling pattern can be translated into studying the roots of a polynomial, which we know how to analyze better than direct enumeration <ref:2605.03473#pg2605> point three thousand four hundred seventy-three#pg2.

Ada: So to wrap up our discussion on "Polynomials from tilings of rectangles," Ahlberg and Alexandersson have shown that tiling polynomials for two-column Ferrers shapes are real-rooted and form interlacing sequences <ref:2605.03473#pg2>.

The paper's improvements: Kolya: So, looking at the paper again, they suggest a lot of ways to use these ideas for other kinds of problems <ref:2605.03473#pg17>.

Ada: They’re proposing using anchor words defined by implications as a way to analyze arbitrary Ferrers diagrams <ref:2605.03473#pg17>. This lets you get the generating function F mu d x t <ref:2605.03473#pg18>, which is really useful because it handles shapes that aren't just simple rectangles or two-column ones.

Emmy: That means they’re generalizing the structural insights they found for two-column tiles to work for any shape, as long as you use these anchor word definitions <ref:2605.03473#pg17>. The structure of the tile becomes more flexible, but the mathematical machinery stays put.

Kolya: I'm curious about how this helps with things we haven't even touched yet, like fault lines in dense tilings <ref:2605.03473#pg47>. They talk about using a generating function H mu d x s with real-rooted coefficient polynomials when the B mu d x one has only real zeros <ref:2605.03473#pg10>.

Ada: That connection is interesting because it links the tiling structure to the zeroes of another polynomial, which is another way to prove stability in these dense arrangements <ref:2605.03473#pg10>. It’s about showing that a certain condition on the tiling leads to a property about an associated function's roots.

Emmy: So they are using these analytic tools, like real-rootedness of coefficient polynomials, to probe the combinatorial constraints of tiling configurations <ref:2605.03473#pg2605> point three thousand four hundred seventy-three#pg2. It’s using analysis to verify combinatorics.

Kolya: And they also have this idea about computing how many fault-free anchor words contain exactly m big tiles using Lemma eight <ref:2605.03473#pg8>, which leads to the generating function B mu d x t <ref:2605.03473#pg44>. That sounds like it could give us a direct count for specific tiling problems.

Ada: That’s right, it gives you a counting tool for those specific fault-free configurations <ref:2605.03473#pg8>. It connects the anchor word structure directly to enumerating tiles with exactly m big tiles <ref:2605.03473#pg10>.

Emmy: So, they are suggesting that by focusing on these structural elements like anchor words and their implications, we can build tools that work across a much wider range of tiling problems than just the ones they initially studied <ref:2605.03473#pg2>.

Kolya: It seems like the future work here is taking this general method and applying it to even more complex systems, maybe those involving cylindric boundary conditions or other constraints <ref:2605.03473#pg2>.

Ada: That’s right, they’re opening up the door for applying these polynomial tools to other tiling variants like cylindric tilings <ref:2605.03473#pg2>. It shows that the methods developed here aren't just for two-column shapes; they can be extended.

Conclusion: Ada: So, to wrap up "Polynomials from tilings of rectangles," we've seen how Ahlberg and Alexandersson used tiling problems to derive real-rooted polynomials for two-column Ferrers shapes <ref:2605.03473#pg2>.

Emmy: They showed that the structure of these tilings is highly constrained, and this constraint translates directly into the analytic property of the polynomials being real-rooted and forming interlacing sequences <ref:2605.03473#pg2>.

Kolya: From a probabilistic side, it suggests that for certain tiling structures, you can analyze the underlying counting problem using tools from spectral analysis rather than just brute force counting <ref:2605.03473#pg2>.

Ada: They did this by using transfer matrices to preserve those interlacing pairs, which is a very strong structural statement <ref:2605.03473#pg2>.

Emmy: It’s an elegant connection between geometry and linear algebra, showing that the way tiles fit together dictates the properties of the resulting polynomials <ref:2605.03473#pg2>.

Kolya: I just think that this approach of using real-rootedness to constrain combinatorial objects is something we could apply to other areas, maybe even in dynamical systems where stability depends on spectral gaps <ref:2605.03473#pg2>.

Ada: Exactly. And they did a lot more than just two-column shapes; they explored fault-free tilings and dense tilings, finding that certain conditions make the conflict graph claw-free <ref:2605.03473#pg5>.

Emmy: So, structural simplicity in the tiling pattern—the lack of a claw—is tied to nice algebraic properties of the associated graphs <ref:2605.03473#pg5>.

Kolya: That tells us something about how complex those interactions can be; if they aren't claw-free, the counting polynomials might lose that real-rootedness property <ref:2605.03473#pg2>.

Ada: They also developed row-refined tiling polynomials, which let you analyze arbitrary Ferrers diagrams by tracking tiles based on their anchor square row <ref:2605.03473#pg7>.

Emmy: And this leads to a generating function that tracks those tiles based on the sum of their anchor square rows, which is a powerful way to handle general shapes <ref:2605.03473#pg8>.

Kolya: So, for someone just listening, the takeaway is that you can translate complex spatial arrangements into studying polynomial roots <ref:2605.03473#pg2605> point three thousand four hundred seventy-three#pg2.

Ada: The paper's main contribution is proving this real-rootedness for two-column Ferrers tiles and establishing a general methodology using anchor words for arbitrary shapes <ref:2605.03473#pg18>.

Emmy: It’s a solid piece of work that links geometry, combinatorics, and analysis through these tiling problems <ref:2605.03473#pg1>.

Kolya: I'm just excited to see how they use this framework to tackle those cylindric tilings or other boundary conditions we discussed earlier <ref:2605.03473#pg2>.

Ada: Exactly. This opens up a lot of new avenues for applying these polynomial tools to other complex tiling variants <ref:2605.03473#pg2>.

John Ahlberg, Per Alexandersson

math.CO

Submitted: 2026-05-05

Updated: 2026-11-18

Comments: 37 pages, comments welcome

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

The gist: We study tilings of rectangular boards using unit squares together with a single type of big tile shaped as a Ferrers diagram and derive generating functions for these tilings <ref:2605.03473#pg2>.

Key concepts

Tiling Polynomials
These are mathematical functions that count the number of ways a specific shape can be perfectly covered (tiled) by a set of given tiles. The paper focuses on proving that for certain rectangular shapes, these polynomials have special properties, specifically being 'real-rooted' and forming 'interlacing sequences,' which is important for understanding their structure.
Anchor Word
An anchor word is a specific type of sequence used to represent tilings involving L-polyominoes. It's defined by a condition where the value of each element, when it's infinite, must be greater than or equal to the next element. This concept allows researchers to establish a direct one-to-one correspondence (bijection) between these words and actual tilings.
Real-Rootedness
A polynomial is 'real-rooted' if all of its roots (the values of x that make the polynomial equal to zero) are real numbers. Proving this property for tiling polynomials means that the underlying combinatorial structure has a very stable and predictable mathematical behavior, often simplifying complex counting problems.
Conflict Graph
The conflict graph is a diagram created to analyze potential overlaps or conflicts between different tilings or tile placements. The paper investigates when this graph is 'claw-free,' meaning it avoids a specific forbidden structure. This analysis helps classify the geometric constraints under which certain tiling conditions can be met.

Terminology

Summary

We study tilings of rectangular boards using unit squares together with a single type of big tile shaped as a Ferrers diagram and derive generating functions for these tilings <ref:2605. p. 003473#pg2>. The paper proves that tiling polynomials for two-column Ferrers shapes are real-rooted and form interlacing sequences <ref:2605. p. 003473#pg2>.

Tilings involving L-polyominoes

The study begins with tilings of the 3×n-board using L-triominoes and unit squares <ref:2605.03473#pg3>. A recursion is derived for the number of such tilings, which is given by An = An−1 + 2An−2 + An−3 <ref:2605. p. 103473#pg3>. This sequence has an interpretation as the number of tilings of the 3×n-board using squares of sizes 1×1, 2×2 and 3×3 <ref:2605. p. 103473#pg3>.

Words from tilings with L-polyominoes

The notion of an anchor square is introduced as a helpful tool for analyzing tilings <ref:2605.03473#pg5>. An anchor word is defined as a word a1, a2,. p. 3.., an in the alphabet and satisfying the condition ai! p. 3= ∞ => ai+1 >= ai + 1 for all i = 1, 2 <ref:2605. p. 003473#pg6>. A bijection is established between anchor words and tilings using Lh-polyominoes <ref:2605. p. 103473#pg6>. The generating polynomial Qd,n(t) tracks the number of Lh-polyominoes used <ref:2605. p. 203473#pg6>.

Where the gains come from

The central theme is the real-rootedness of tiling polynomials <ref:2605.03473#pg2>. For two-column rectangular Ferrers tiles µ = (k, k) with d ≤ k, the tiling polynomials are real-rooted and form interlacing sequences <ref:2605. p. 003473#pg2>. This is proven by showing that the transfer matrix in (22) preserves interlacing pairs <ref:2605. p. 903473#pg2>.

Pruning redundant reasoning tokens

The paper explores various variants of tilings, including fault-free tilings, dense tilings, and cylindric tilings <ref:2605.03473#pg2>. The generating function for a tiling with a Ferrers tile µ is given by Fµ,d(x, t) = 1 / (1 − Bµ,d(x, t)) <ref:2605. p. 703473#pg3>. The paper also investigates the conflict graph associated with these tilings and shows that for certain conditions on µ and d, the conflict graph is claw-free <ref:2605. p. 803473#pg5>.

How the training signal is built

The study introduces row-refined tiling polynomials Sµ,d,n(s1,..., sd) which distinguish tiles by their anchor square row <ref:2605. p. 703473#pg7>. For µ = (k, k) and d ≤ k, the generating function for these polynomials is given by Xn≥0 S(k,k),d,n(s1,. p. 4.., sd) x n = 1 / (1 − x − (s1 + s2 + · · · + sd) x 2 <ref:2605. p. 003473#pg8>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved system can derive generating functions for tiling problems using L-polyominoes based on a linear recursion (Equation 6). This allows for efficient counting of tilings with a fixed number of big tiles and fault lines, as shown in Theorem 2.

  2. Improved system can establish connections between tiling enumeration results and sequences in the OEIS by recovering known sequences like Fibonacci numbers (A000045) and deriving new ones from larger Ferrers shapes or cylindric boundary conditions (Table 1).

  3. Improved system can determine the real-rootedness of tiling polynomials for two-column Ferrers tiles using Theorem 6, which proves that the tiling polynomials are real-rooted and form interlacing sequences.

  4. Improved system can utilize anchor words as a primary bijective tool to establish a bijection between anchor words and tilings (Lemma 2), leading to the definition of the independence polynomial of a conflict graph (Lemma 4).

  5. Improved system can prove that tiling polynomials for two-column Ferrers tiles are real-rooted by verifying conditions in Theorem 4, showing that the required inequalities hold for all entries in the transfer matrix derived from Equation 16.

  6. Improved system can analyze tiling problems involving arbitrary Ferrers diagrams by introducing anchor words defined by implications (Equation 17), allowing the derivation of a generating function Fmu,d(x, t) (Equation 18).

  7. Improved system can classify Ferrers tiles and parameters d for which the conflict graph is claw-free using Lemma 6, which shows that for µ = (k, k) with d <= k, the conflict graph is claw-free.

  8. Improved system can determine when tiling polynomials Pmu,d,n(t) are real-rooted for all n by analyzing the transfer matrix in Equation 16 and verifying conditions from Theorem 4.

  9. Improved system can analyze fault lines in dense tilings by using the generating function Hmu,d(x, s) (Equation 47), which is shown to have real-rooted coefficient polynomials when Bmu,d(x, 1) has only real zeros (Theorem 10).

  10. Improved system can compute the number of fault-free anchor words containing exactly m big tiles using Lemma 8 and leads to the generating function Bmu,d(x, t) (Equation 44).

Related papers