October 10, 2024 | Bharti Dharapuram and Amritanshu Prasad
“These things don’t happen very often, I still remember seeing that picture and this really clear pattern,” Amri recalls about an image that led to an unexpected insight into a four-decade-old equation.
“It was a memorable day as a mathematician.”
In early 2016, Amritanshu Prasad (Amri), a faculty at The Institute of Mathematical Sciences, Chennai was working with Arvind Ayyer (Indian Institute of Science Bangalore) and Steven Spallone (Indian Institute of Science Education and Research, Pune) to look into the properties of matrix representations of symmetric groups.
A group is an abstraction of the set of symmetries of a structure. Mathematicians may consider symmetries of graphs (or networks), physicists may look at symmetries of space-time, while chemists may be interested in the symmetries of a molecule. They can be regarded as transformations of the structure that keep its essential properties intact. For example, an equilateral triangle has six symmetries; three reflections, and three rotations (Figure 1).
Figure 1. The different kinds of actions that preserve the symmetry of a geometric object, a triangle in this case, constitute a symmetric group (left). These actions can combine to replicate another action from the group (right). Image adapted from the source and shared under a CC by 3.0 license.
Groups come with a composition (or product law). Following one transformation by a second one results in a new transformation called the composition. To study such transformations tractably, mathematicians use matrices to represent the transformations in a group. In a representation, the composition of transformations becomes matrix multiplication. Each group can have many different representations, whose understanding can lead to deep insights into the structure of the group. The atomic building blocks of representation are the irreducible ones.
The group of symmetries of n identical objects is called the symmetric group. Its irreducible representations were classified by Frobenius, Schur and Young more than 100 years ago. Amri and his collaborators were curious about representations of symmetric groups by matrices with an odd number of rows and columns.
Frobenius, Schur and Young had established that the irreducible representations of symmetric groups are indexed by integer partitions. An integer partition is a way of breaking down a positive integer into smaller ones: for example, the integer 4 can be broken down in five ways, namely 4, 3+1, 2+2, 2+1+1, and 1+1+1+1. We do not distinguish between the partitions 3+1 and 1+3, as their parts are the same. Thus an integer partition can be regarded as a finite sequence of positive integers, arranged in weakly decreasing order. For example, 5+3+3+1 is the integer partition of 12.
Integer partitions are among the most intriguing objects that come up in enumerative mathematics. Mathematicians have long sought a nice formula for the number of integer partitions, and sophisticated techniques following the work of Euler, Ramanujan and Rademacher allow us to easily show that the number of integer partitions of 1000 is 24061467864032622473692149727991, a number so large that it defies intuition. Even so, many subtle questions about integer partitions continue to intrigue mathematicians today.
Let’s pause to see integer partitions and play around with them. A useful visualization of an integer partition is a Young diagram introduced in 1900 by the British mathematician Alfred Young. In this diagram, a partition is drawn as a left-justified array, where rows are arranged in descending order of parts represented as boxes in each row. For example, the Young diagram of 5+3+3+1 is -
Figure 2. Young diagram for the integer partition 5+3+3+1.
One integer partition is said to cover another, if adding a box to one Young diagram results in the Young diagram of the other. For example, the integer partition 5+3+3+1 covers both 4+3+3+1 and 4+3+2+1. This gives rise to a network of connections between partitions of different integers, where each row displays the Young diagrams for that row number (Figure 3).
The network, called Young’s graph, grows very quickly. “Describing this growth was one of the beautiful results of Hardy and Ramanujan. They showed that it grows exponentially in the square root of n (the integer being partitioned),” Amri says about the famous partition function.
Figure 3. Young’s graph depicts how the different integer partitions of a given number, depicted as a specific arrangement of boxes, are related to each other. The permutations of these boxes in a given diagram are related to actions in a symmetric group.
Using this map of integer partitions, one can calculate the number of ways of arriving at a specific Young diagram by sequentially adding one box at a time. This can be done by adding the numbers associated with the partitions that are covered by a given Young diagram and following this through Young’s graph. However, as the integer becomes large, an exponential increase in the number of partitions makes them challenging to track. This is where the elegant Hook length formula, discovered in 1953 by the North American mathematicians Frame, Robinson and Thrall, comes in handy (Figure 4). “It is sort of miraculous that it works,” says Amri.
Amri and collaborators walked through these steps because the Hook length formula gives the dimensions of the irreducible representations of a symmetric group. In other words, the size of an atomic matrix representing the symmetric group – the object of their interest. “It is a fairly elementary set-up where you draw these pictures and put numbers in them, but it has a lot of mathematical significance,” Amri says about the Young’s graph linking integer partitions. “It is a rich source of very interesting mathematics.”
Figure 4. One can assign a number to the nodes in a Young’s graph by summing the numbers associated with their parents. This is derived using the elegant Hook length formula (inset), which gives important properties of symmetric groups.
Once they calculated Hook lengths and placed them on the Young’s graph, they drew a line connecting all the odd values. And the image they saw took them completely by surprise. It was the key that opened the doors to a relationship between symmetric groups and the enchanting world of fractals.
Fractals are patterns that show self-similarity across scales. Imagine viewing an image and zooming in for the same image to come into view again and again at different levels of magnification. Fractals usually arise in geometry, but sometimes they can also arise from enumerative problems. Amri likes to call such fractals combinatorial fractals. A well-known example is Pascal’s triangle where, starting from 1, the numbers in a row of a triangular array are derived by summing up adjacent numbers in the previous row (Figure 5). It has many important applications – it gives the coefficients of the expansion of (x + y)n and the number of ways of obtaining k combinations of n objects.
Figure 5. Pascal's triangle is obtained by summing up adjacent numbers in a row to give rise to the next row of values and has interesting mathematical properties.
Something interesting happens when we start tracking odd numbers across the Pascal’s triangle. One starts seeing repeating triangles, which reset at powers of 2 with larger triangles appearing as the tree expands. The lines enclosing a triangle arise from each odd number having a unique odd parent in the previous level and either one or two odd daughters in the next level. The number of odd instances in a row is always a power of 2, whose exponent can be easily calculated by summing up the binary expansion of the row number (Figure 6).
Figure 6. Tracing lines through the odd values in a Pascal’s triangle reveals a fractal (left), where the number of odd entries in any row can be simply calculated by summing up its binary expansion (right).
Amri’s image revealed an unexpected connection between Young's graph and Pascal's triangle.
“I was fooling around on my computer and plotting things,” recalls Amri. “I was thinking maybe it (irreducible representations of a symmetric group) has something to do with Young’s graph, so I wrote a small computer program in Sage and plotted it,” he adds. “I was completely shocked because I saw this tree with these repeating patterns just like in a Pascal’s triangle [Figure 7].”
Figure 7. Tracing the odd partitions in a Young’s graph reveals a fractal structure.
Since we know how to find the number of odd entries in the Pascal’s triangle, the same can be adapted for this sister fractal that Amri chanced upon. The number of odd partitions in a row is the weighted sum of the binary expansion of the row number (Figure 8). The group relied on this fractal perspective to derive the proof for the number of odd partitions in a Young’s graph. “Once we knew that the fractal nature was there, it was not so difficult to prove it. What others may have missed was the visual insight,” he says.
Figure 8. The similarity of the fractal in the Young’s graph and a Pascal’s triangle allows us to calculate the number of odd partitions in any row.
“We didn’t know at that time, but there was a well-known formula due to Macdonald, which gives how many odd guys there are in each row,” Amri says. Way back in 1971, the British mathematician Ian Macdonald had given a proof for this formula using very different methods. “Macdonald’s formula was there but that it arises from this fractal structure was not known,” Amri says, illustrating how disparate fields of mathematics offer alternate routes of reaching the same insight.
“This wasn’t even the problem we set out to solve, it was an easier version of that problem,” he laughs, talking about their accidental proof.
Ayyer, A., Prasad, A., & Spallone, S. (2018). Macdonald trees and determinants of representations for finite Coxeter groups (arXiv:1812.00608). arXiv. https://doi.org/10.48550/arXiv.1812.00608
--
Bharti thanks Viswanath Sankaran for introducing this work and for discussions related to symmetric groups and their irreducible representations.
