Squaring Triangles

This post illustrates what Feynman praised as a beautiful facet of mathematics–abstraction from the concrete–as well as the fascinating synergy at one of its crossroads–that of algebra and enumerative geometry.

One day last fall in a class, several curious 12-th graders marvelled at the relationship I showed them between the Pascal triangle (OEIS A007318) and the enumerative geometry of triangles and squares and their n-dimensional extensions/abstractions the hypertriangles (HTs) and hypersquares (HSs) (or, equivalently, the tetrahedrons and hypertetrahedrons, and the cubes and hypercubes). By looking at certain physico-geometric ways of generating the n-dimensional extensions, we can relate simple algebraic manipulations–multiplication of polynomials and a matrix by itself–to counting the components of these geometric constructs, enumerated by their face-polynomials.

First, let’s tackle the HT beasties. The face-polynom, or f-polynom, of a polytope, such as a HT or HS, has coefficients enumerating the number of n-D faces of the polytope. For example, the 2-D HT is a triangle with the associated f-polynom


enumerating the 3 vertices (0-D faces), 3 edges (1-D faces), and 1 triangle (2-D face) of a triangle. The 3-D HT is a tetrahedron with f-polynom

T_3(x)= 4+6x+4x^2+x^3=[(1+x)^4-1]/x,

corresponding to the 4 vertices, 6 edges, 4 triangles, and 1 tetrahedron comprising its faces. (Note that in the general literature the (n-1)-D faces of either n-D polytope can be referred to as their facets.) The general formula that follows from the forthcoming method of constructing the HTs for the f-polynom of the n-D HT is


Now for the recursive physico-geometric construction of an n-D HT from an (n-1)-D HT, consider the 1-D HT, a line segment. Move from the 1-D HT in a direction perpendicular to it and place a point some distance from it. Then draw line segments connecting each vertex of the 1-D HT to the new vertex. We have generated an instance of the 2-D HT, a triangle.

To obtain the 3-D HT, the tetrahedron, just iterate on the algorithm for generating the triangle by replacing each ocurrence of n-D by (n+1)-D. That is, move in a direction perpendicular to the plane of the triangle, 2-D HT, place a point some distance away from it, and connect that new vertex to each old vertex, and you have a 3-D HT, a tetrahedron. For higher dimensions, repeat the procedure ad nauseum.

Now we are in a position to relate multiplication of P_{n+1}(x)= (1+x)^{n+1} by 1+x to obtain the formula for T_{n+1}(x), the f-polynom of the (n+1)-D hypertriangle. Note that the coefficients of the polynomial P_{n+1}(x) = 1 + v_nx+e_nx^2+t_nx^3+ ... (the elements of the (n+1)-th row of the Pascal triangle) alledgely enumerate the number of vertices, (v_n), edges (e_n), triangles (t_n), etc., that comprise the n-D HT. From the geometric construction, the new (n+1)-D HT has one more vertex than the old n-D HT. This is reflected in the multiplication M = P_{n+1}(x) \cdot (1+x) in the factors v_{n+1}x = v_nx \cdot 1 + 1 \cdot x. The new HT has as many edges as the old plus an edge for each old vertex giving e_{n+1}x^2 = e_n x^2 \cdot 1+ v_nx \cdot x. Similarly, the new HT has as many triangles as the old plus a new one for each old edge; i.e., t_{n+1} x^3 = t_n x^3\cdot 1 + e_n x^2 \cdot x. And so on for the higher dimensional faces.

Following this train of physico-geometric intuition mapped to this particularly simple algebraic recursion relation, we have established the general f-polynom is indeed

T_n(x)= [(1+x)^{n+1}-1]/x,

and in some sense defined what hypertriangles are.

Now we are ready to look at the f-polynoms of the hypersquares (HSs) and show that their coefficients are generated by squaring the Pascal matrix as a lower triangular matrix, i.e., by squaring a triangle. This is equivalent to umbral substitution of P_n(x) into itself; that is, the face-polynomial for the n-D HS is S_n(x) = P_n(P.(x)). For example,

S_2(x)= P_2(P.(x))= (1+P.(x))^2=(P.(x))^0+2(P.(x))^1+(P.(x))^2

=P_0(x)+2P_1(x)+P_2(x)= 1+ 2(1+x)+(1+x)^2=4+4x+x^2,

enumerating the faces of a square (4 vertices, 4 edges, and 1 square). This can be simplified as

S_n(x)= P_n(1+P.(x))=(1+(1+x))^n = (2+x)^n.

The method of physico-geometric construction of a new {n+1}-D HS from an old n-D HS is to drag the old through a dimension perpendicular to it letting the edges fill in new squares. For example, drag a line segment in a direction perpendicular to it and a square is obtained. Drag a square in a direction perpendicular to the plane of the square and a cube is obtained. Check that S_3(x) = (2+x)^3 correctly enumerates the faces of a cube, and develop algebraic arguments analogous to those for the hypertriangles to prove the general formula for S_n(x). Do a numerical check that squaring the Pascal matrix as a lower triangular matrix (i.e., a matrix with zeros above the main diagonal) gives the same result as the umbral substitution (cf. A038207).

From here paths meander through glades of analysis, geometry, and combinatorics, roamed by a hybrid of aspects of the hypertriangles and hypersquares–the Vandermonde matrix–and the ubiquitous Bernoulli polynomials and their elegant escorts, the reciprocal polynomials.

Related stuff and other trails in combinatorics:

1) Counting faces of polytopes by Lee. (The varying definitions and uses of the terms h–vector and h-polynomial–and even f-polynomial–in the vast literature are confusing. If we take the h-polynomial to be algebraically defined as h_n(x)=f_n(x-1) with the f-polynomials, f_n(x), described above, then for the hypertriangles, we obtain h_n(x) = [1-x^{n+1}]/(1-x) = 1+x+ x^2 +\cdots + x^n and for the hypercubes, h_n(x) = (1+x)^n.)

2) Keep it simplex, stupid!

3) The Vandermonde Matrix

4) Goin’ with the Flow: Logarithm of the Derivative

5) OEIS A074909

6) OEIS A135278

7) GeneratingFunctionology by Wilf

8) Analytic Combinatorics by Flajolet and Sedgwick

9) Enumerative Combinatorics Vol. I by Stanley

10) Algebraic and geometric methods in enumerative combinatorics by Ardila

11) A species approach to Rota’s twelvefold way by Claesson

12) Combinatorial Species–Bergeron

13) Computing the Discrete Continuously by Beck and Robins

14) Trianglations of Point Sets by De Loera, Rambau, Santos

15) Ch. 10: Topology Grows into a Branch of Mathematics in the book Never a Dull Moment: Hassler Whitney–Mathematics Pioneer by Kendig

16) Merging/identifying opposing facets of the n-hypercube gives us the n-torus, and truncating facets of the hypertriangles or hypercubes gives us permutahedra and associahedra and paths to other important and exciting fields of modern research in math and quantum physics.

This entry was posted in Math and tagged , , , , , , , , , , . Bookmark the permalink.

1 Response to Squaring Triangles

  1. Tom Copeland says:

    See also a short early paper on connections of generating function / formal series to enumerative combinatorics in the lingo of category theory: “A COMBINATORIAL THEORY OF FORMAL SERIES” by ANDRÉ JOYAL, translation and commentary by BRENT A. YORGEY of “Une théorie combinatoire des séries formelles” (http://ozark.hendrix.edu/~yorgey/pub/series-formelles.pdf)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s