Star of David theorem

The Star of David theorem is a combinatorial identity concerning the greatest common divisors (GCDs) of binomial coefficients arranged in Pascal's triangle to form a hexagram, or Star of David, pattern, stating that the GCD of the three coefficients at the vertices of one equilateral triangle equals the GCD of the three at the vertices of the interlocking triangle.^[1] This theorem emerged from observations in the arithmetic properties of binomial coefficients, with an initial product identity—where the product of the binomial coefficients at the vertices of the upward-pointing triangle equals that of the downward-pointing one—first noted by V. E. Hoggatt Jr. and C. T. Hansell in 1971.^[1] The GCD version was conjectured shortly thereafter by Henry W. Gould, who proposed that for binomial coefficients surrounding a central entry in Pascal's triangle, denoted as a_1, a_3, a_5 for one set and a_2, a_4, a_6 for the other, \gcd(a_1, a_3, a_5) = \gcd(a_2, a_4, a_6).^[1] This conjecture was proved and generalized by A. P. Hillman and V. E. Hoggatt Jr. in the same year, establishing the equality for specific hexagonal configurations of coefficients.^[1] Subsequent extensions, such as those by David Singmaster and Nobuyuki Sato in 1975, showed that the common GCD extends to twelve related binomial coefficients, including additional sets like \gcd(\binom{n-1}{k-2}, \binom{n}{k-1}, \binom{n+1}{k}).^[2] Further generalizations by researchers including E. G. Straus and Calvin T. Long expanded the theorem to larger convex hexagons and arbitrary side lengths, proving equality of GCDs for up to 18 or more coefficients under certain conditions on the parameters n and k.^[1] These results have applications in tiling problems and properties of Pascal's triangle, with ongoing research exploring extensions to q-binomial coefficients and f-trinomial analogs.^[3]

Background

Pascal's Triangle

Pascal's triangle is an infinite triangular array of numbers, beginning with row 0 consisting of a single entry: 1. Subsequent rows are generated by starting and ending each row with 1, while each interior entry is the sum of the two entries immediately above it from the previous row. This recursive construction ensures that the triangle builds progressively, with row n containing n+1 entries.^[4]^[5] The entries in Pascal's triangle correspond directly to binomial coefficients, where the entry in row n and position k (counting from 0 on the left) is \binom{n}{k}, the coefficient of x^k in the expansion of (1 + x)^n. This connection highlights the triangle's role in combinatorics, as \binom{n}{k} represents the number of ways to choose k elements from a set of n elements.^[4]^[6] Key properties of the triangle include its symmetry, given by \binom{n}{k} = \binom{n}{n-k}, which reflects the equal number of ways to choose k or n-k items from n. Another fundamental property is the hockey-stick identity:

\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1},

which relates the sum of binomial coefficients along a diagonal to another binomial coefficient. These properties emerge naturally from the additive structure of the triangle.^[5]^[6] As a visual tool, Pascal's triangle arranges binomial coefficients in a compact, triangular form that aids in recognizing patterns, such as row sums equaling powers of 2 or diagonals forming other sequences, facilitating intuitive exploration of combinatorial relationships.^[6]

Binomial Coefficients

Binomial coefficients, denoted \binom{n}{k}, represent the number of ways to choose k distinct items from a set of n items without regard to order, a fundamental concept in combinatorics.^[7] This combinatorial interpretation arises from the principle that the total number of subsets of size k from n elements is given by this quantity.^[8] Algebraically, for non-negative integers n \geq k \geq 0, the binomial coefficient is defined as

\binom{n}{k} = \frac{n!}{k!(n-k)!},

where n! denotes the factorial of n, the product of all positive integers up to n.^[7] This formula extends the combinatorial meaning by expressing the selection process through permutations divided by arrangements within the chosen subset.^[9] Binomial coefficients are always non-negative integers, with \binom{n}{k} = 0 when k > n or k < 0, ensuring the definition holds consistently outside the primary range.^[10] A key property is their role in the binomial theorem, which provides the generating function (1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k, linking them to expansions of powers.^[11] In the context of greatest common divisors, binomial coefficients appear in number-theoretic results such as Lucas' theorem, which determines \binom{m}{n} \mod p for a prime p using base-p digits of m and n.^[12] Similarly, Kummer's theorem gives the p-adic valuation of \binom{m+n}{m}, equal to the number of carries when adding m and n in base p, quantifying the highest power of p dividing the coefficient.^[13] These theorems highlight the interplay between binomial coefficients and divisibility properties essential for deeper algebraic identities.^[14]

Formulation

GCD Equality

The GCD equality constitutes a fundamental aspect of the Star of David theorem, establishing that the greatest common divisor of the three binomial coefficients in one triangular configuration equals that of the three in the opposing configuration. This property was first identified by Henry W. Gould in his 1972 paper on binomial coefficient divisibility.^[15] Specifically, for positive integers n > k \geq 1, the equality is given by

\gcd\left( \binom{n-1}{k-1}, \binom{n}{k+1}, \binom{n+1}{k} \right) = \gcd\left( \binom{n-1}{k}, \binom{n}{k-1}, \binom{n+1}{k+1} \right).

These binomial coefficients are well-defined and positive under the specified conditions, as k \geq 1 ensures non-negative lower indices and n > k guarantees the upper indices suffice.^[15]^[16] In the context of the theorem's geometric arrangement, the left-hand triplet \binom{n-1}{k-1}, \binom{n}{k+1}, \binom{n+1}{k} forms the vertices of the upward-pointing triangle, while the right-hand triplet \binom{n-1}{k}, \binom{n}{k-1}, \binom{n+1}{k+1} delineates the downward-pointing triangle, highlighting the symmetric divisor structure central to the star formation.^[16] This GCD relation parallels a distinct product equality for the same sets of coefficients, underscoring interconnected arithmetic identities in Pascal's triangle.^[15]

Product Equality

The product equality aspect of the Star of David theorem asserts that, within the hexagonal arrangement of six binomial coefficients centered at \binom{n}{k} in Pascal's triangle, the product of the binomial coefficients at the vertices of one equilateral triangle equals the product at the vertices of the interlocking triangle. Specifically, for integers n > k \geq 1,

\binom{n-1}{k-1} \binom{n}{k+1} \binom{n+1}{k} = \binom{n-1}{k} \binom{n}{k-1} \binom{n+1}{k+1}.

This equality was first noted by V. E. Hoggatt Jr. and W. Hansell in 1972.^[16] The relation can be understood through the factorial representations of the binomial coefficients, as both sides simplify to ratios involving consecutive factorials in numerator and denominator. For instance, expanding each term reveals that the equality stems from cancellations in the products of (n-1)!, n!, and (n+1)! against terms like (k-1)!, k!, (k+1)!, and analogous factors for n-k. This factorial-based perspective underscores the theorem's combinatorial nature without requiring deeper algebraic manipulation here.^[16] The common value of these products is given by

\frac{(n-1)! \, n! \, (n+1)!}{(k-1)! \, k! \, (k+1)! \, (n-k-1)! \, (n-k)! \, (n-k+1)!},

which holds universally for the specified range of n and k, highlighting the theorem's role in revealing multiplicative symmetries in binomial arrays. This product equality implies certain divisibility properties, such as equal greatest common divisors for the respective triples in some configurations.^[16]

Visual Representation

Arrangement in Pascal's Triangle

In Pascal's triangle, the Star of David theorem manifests through a specific arrangement of binomial coefficients centered on an entry \binom{n}{k}, where n and k are non-negative integers with $0 \leq k \leq n. This central coefficient is surrounded by six adjacent entries spanning rows n-1, n, and n+1, and columns k-1, k, and k+1. The upward-pointing equilateral triangle consists of the coefficients at positions \binom{n-1}{k-1}, \binom{n}{k+1}, and \binom{n+1}{k}, while the downward-pointing equilateral triangle is formed by \binom{n-1}{k}, \binom{n}{k-1}, and \binom{n+1}{k+1}. These positions create a compact, symmetric configuration that aligns with the discrete grid of the triangle, ensuring all indices remain valid for sufficiently large n.^[16]^[17] Visually, this arrangement forms a hexagon enclosing the central \binom{n}{k}, with the two interlocking triangles representing the Star of David shape. The hexagonal layout highlights the rotational symmetry of the pattern, where the vertices of the triangles lie at the hexagon's points, and the sides connect adjacent coefficients in the triangle's rows. This structure emphasizes the theorem's geometric essence within the triangular array, transforming the abstract binomial entries into a recognizable emblematic form. Graphical depictions often shade or connect these seven coefficients to illustrate the star, underscoring the theorem's aesthetic appeal in combinatorial visualization.^[16]^[17] As Pascal's triangle expands to larger rows, the Star of David pattern scales by shifting the center to higher n and appropriate k, preserving the hexagonal and triangular layout regardless of size. For instance, the configuration becomes more embedded within the broader structure, allowing multiple such stars to appear without overlap when centered at distinct positions. This scalability demonstrates the theorem's recurrence across the infinite triangle, where the local hexagonal motif repeats uniformly, facilitating exploration of similar patterns in extended combinatorial arrays.^[16]^[17]

Geometric Interpretation

The Star of David theorem derives its name from the visual resemblance of the selected binomial coefficients to the hexagram symbol, consisting of two equilateral triangles overlapping to form a six-pointed star. In Pascal's triangle, the six relevant binomial coefficients are positioned at the vertices of this hexagram, with one triangle pointing upward and the other downward, centered around a common entry. This arrangement highlights the theorem's equalities as inherent to the symmetric structure of the pattern.^[18] The geometric symmetry of the hexagram—featuring 60-degree rotational invariance and multiple reflection axes—mirrors the theorem's arithmetic properties, where the product of the coefficients at the vertices of one triangle equals that of the other, and similarly for their greatest common divisors. These symmetries underscore how the interlocking triangles embody balanced relationships among the coefficients, independent of their specific numerical values.^[16] Although the hexagram evokes the Star of David as a longstanding Jewish symbol, the theorem employs it purely as a mathematical motif to describe the configuration in Pascal's triangle. The naming convention was first introduced by V. E. Hoggatt Jr. in a 1970 letter, as noted by Henry W. Gould in his study of binomial coefficient products.^[18]

Proofs

Proof of Product Equality

The product equality in the Star of David theorem asserts that

\binom{n-1}{k-1} \binom{n}{k+1} \binom{n+1}{k} = \binom{n-1}{k} \binom{n}{k-1} \binom{n+1}{k+1}

for integers $1 \leq k \leq n-1.^[16] An algebraic proof proceeds by expressing each binomial coefficient in terms of factorials and verifying that both sides of the equality are identical. Recall that \binom{m}{j} = \frac{m!}{j! (m-j)!}. Substituting this into the left-hand side (LHS) yields

\text{LHS} = \frac{(n-1)!}{(k-1)! (n-k)!} \cdot \frac{n!}{(k+1)! (n-k-1)!} \cdot \frac{(n+1)!}{k! (n+1-k)!}.

The numerator is (n-1)! \cdot n! \cdot (n+1)!. For the denominator, note that (n+1-k)! = (n+1-k) (n-k)!, so it simplifies to

(k-1)! (n-k)! \cdot (k+1)! (n-k-1)! \cdot k! (n+1-k) (n-k)! = (k-1)! \, k! \, (k+1)! \cdot (n-k)!^2 \cdot (n-k-1)! \cdot (n-k+1),

since n+1-k = n-k+1. Now substitute into the right-hand side (RHS):

\text{RHS} = \frac{(n-1)!}{k! (n-1-k)!} \cdot \frac{n!}{(k-1)! (n-k+1)!} \cdot \frac{(n+1)!}{(k+1)! (n-k)!}.

The numerator is again (n-1)! \cdot n! \cdot (n+1)!. For the denominator, note that n-1-k = n-k-1, so (n-1-k)! = (n-k-1)!, and (n-k+1)! = (n-k+1) (n-k)!, yielding

k! (n-k-1)! \cdot (k-1)! (n-k+1) (n-k)! \cdot (k+1)! (n-k)! = (k-1)! \, k! \, (k+1)! \cdot (n-k-1)! \cdot (n-k+1) \cdot (n-k)!^2.

The denominators of LHS and RHS are identical, as are the numerators, so LHS = RHS. This cancellation demonstrates the equality directly through the symmetric structure of the factorial terms.

Proof of GCD Equality

The proof of the GCD equality in the Star of David theorem, originally established by Hillman and Hoggatt, can be approached using p-adic valuations of the binomial coefficients for each prime p.^[19] The GCD of the three binomial coefficients in one triangle is \prod_p p^{m_p}, where m_p is the minimum p-adic valuation among those three coefficients; the equality of the GCDs for the two triangles follows if m_p is the same for both sets of coefficients for every prime p. The p-adic valuation v_p\left(\binom{n}{k}\right) is provided by Kummer's theorem, which counts the number of carries occurring when adding k and n - k in base p. This count equals

v_p\left(\binom{n}{k}\right) = \frac{s_p(k) + s_p(n - k) - s_p(n)}{p - 1},

where s_p(\cdot) is the sum of the base-p digits of its argument. To show the minima match, observe that the indices for the coefficients in each triangle—\binom{n-1}{k}, \binom{n}{k-1}, \binom{n+1}{k+1} for one, and \binom{n-1}{k-1}, \binom{n}{k+1}, \binom{n+1}{k} for the other—are adjacent in Pascal's triangle. The base-p digit sums s_p of these nearby indices differ by at most 1 in each digit position relative to those of n and k, leading to valuations that differ by at most 1 across the six coefficients. The minimum valuation in each triangle is thus determined by the coefficient with the fewest carries in its computation, and the symmetric arrangement ensures this minimum is identical for both triangles.^[1]

Examples

Numerical Illustrations

The Star of David theorem can be verified through concrete computations of binomial coefficients for small parameters n and k, demonstrating both the product equality and the GCD equality. For n=5 and k=2, the upward-pointing triangle involves the coefficients \binom{4}{1} = 4, \binom{5}{3} = 10, and \binom{6}{2} = 15, with product $4 \times 10 \times 15 = 600. The downward-pointing triangle has coefficients \binom{4}{2} = 6, \binom{5}{1} = 5, and \binom{6}{3} = 20, with product $6 \times 5 \times 20 = 600. Additionally, \gcd(4, 10, 15) = 1 = \gcd(6, 5, 20). A more involved case is n=9 and k=3, where the upward triangle coefficients are \binom{8}{2} = 28, \binom{9}{4} = 126, and \binom{10}{3} = 120, yielding product $28 \times 126 \times 120 = 423360. The downward triangle coefficients are \binom{8}{3} = 56, \binom{9}{2} = 36, and \binom{10}{4} = 210, with product $56 \times 36 \times 210 = 423360. Here, \gcd(28, 126, 120) = 2 = \gcd(56, 36, 210). The following table summarizes these examples alongside a base case for n=3, k=1:

n	k	Upward coefficients	Upward product	Upward GCD	Downward coefficients	Downward product	Downward GCD
3	1	\binom{2}{0}=1, \binom{3}{2}=3, \binom{4}{1}=4	12	1	\binom{2}{1}=2, \binom{3}{0}=1, \binom{4}{2}=6	12	1
5	2	\binom{4}{1}=4, \binom{5}{3}=10, \binom{6}{2}=15	600	1	\binom{4}{2}=6, \binom{5}{1}=5, \binom{6}{3}=20	600	1
9	3	\binom{8}{2}=28, \binom{9}{4}=126, \binom{10}{3}=120	423360	2	\binom{8}{3}=56, \binom{9}{2}=36, \binom{10}{4}=210	423360	2

These calculations confirm the theorem's equalities hold for these instances.

Configurations in Larger Triangles

In larger sections of Pascal's triangle, configurations of the Star of David theorem extend beyond isolated hexagons to chained or overlapping structures, where multiple fundamental hexagons tile larger polygonal regions, often forming bands across consecutive rows for a fixed offset k as n varies. These chained hexagons maintain the core properties of the theorem, with the GCD of alternating vertex sets remaining equal across the larger boundary, demonstrating how the equality propagates through overlapping elements. For instance, a 2×2×2m hexagon can be tiled by m fundamental hexagons, where the GCD of the odd-indexed vertices equals the GCD of the even-indexed vertices, independent of the central position in Pascal's triangle.^[20] Such patterns are evident in bands for fixed k, where successive stars overlap, sharing vertices and edges that ensure consistent application of the theorem. The common GCD may vary across the chain but preserves equality within each subconfiguration and across the tiled structure, reflecting the theorem's robustness in extended arrays. For example, consider stars centered near k=4 to 5 for n=10 to 12, forming an overlapping chain along rows:

For n=10, k=4: The triangles involve binomial coefficients with GCD( \binom{9}{3}, \binom{10}{5}, \binom{11}{4} ) = GCD(84, 252, 330) = 6 and GCD( \binom{9}{4}, \binom{10}{3}, \binom{11}{5} ) = GCD(126, 120, 462) = 6, showing equality at 6.
For n=11, k=4: GCD( \binom{10}{3}, \binom{11}{5}, \binom{12}{4} ) = GCD(120, 462, 495) = 3 equals GCD( \binom{10}{4}, \binom{11}{3}, \binom{12}{5} ) = GCD(210, 165, 792) = 3.
For n=12, k=4: GCD( \binom{11}{3}, \binom{12}{5}, \binom{13}{4} ) = GCD(165, 792, 715) = 11 equals GCD( \binom{11}{4}, \binom{12}{3}, \binom{13}{5} ) = GCD(330, 220, 1287) = 11.

Shifting to k=5 in the same row range yields similar consistency, with GCDs of 42 for n=10, 6 for n=11, and 33 for n=12, each equal within their respective triangles. These examples illustrate how the GCD propagates with variation (decreasing or fluctuating based on row) but upholds the theorem's equality in the chained band, highlighting scalable patterns in broader triangular arrays.

History and Extensions

Discovery and Development

The product equality for the six binomial coefficients in the Star of David configuration was first noted by V. E. Hoggatt Jr. and W. Hansell in 1971.^[21] The analogous GCD property was conjectured by American mathematician Henry W. Gould in 1972, who named it the Star of David property. This conjecture was announced in the Notices of the American Mathematical Society (abstract 72T-A248) and detailed in the Fibonacci Quarterly.^[15] Gould's work built on longstanding interest in patterns of binomial coefficients, marking a significant contribution to combinatorial number theory. The conjecture was proved shortly thereafter in 1972 by A. P. Hillman and V. E. Hoggatt Jr.^[22] In 1975, British mathematician David Singmaster provided an independent proof and collaborated with Daihachiro Sato on an expansion that demonstrated equal GCDs among twelve binomial coefficients in an extended star configuration. Their preliminary report, delivered at a meeting of the American Mathematical Society, emphasized the theorem's robustness for larger symmetric arrangements and spurred further interest in its arithmetic implications.^[23] That same year, Japanese mathematician Sin Hitotumatu and Daihachiro Sato published generalizations of the theorem in the Fibonacci Quarterly, exploring broader applications of the equal product and GCD properties to related hexagonal patterns in binomial arrays.^[24] These developments solidified the theorem's foundational role in the 1970s, with additional comments from American mathematician Calvin T. Long on its connections to hexagonal structures appearing in contemporary discussions within combinatorial literature.

Generalizations

The Star of David theorem admits a q-analog in which the product and GCD equalities hold when binomial coefficients are replaced by Gaussian binomial coefficients \binom{n}{k}_q. In this setting, the common product of the six surrounding entries is given by the q-series expression

P = \frac{(q^k)_\infty (q^{k+1})_\infty (q^{k+2})_\infty (q^{n-k})_\infty (q^{n-k+1})_\infty (q^{n+k-2})_\infty}{(q)_\infty^3 (q^n)_\infty (q^{n+1})_\infty (q^{n+2})_\infty},

where (a)_\infty denotes the q-Pochhammer symbol.^[16] This extension preserves the structural identities of the original theorem within the framework of basic hypergeometric series. The GCD property of the theorem also generalizes to elliptic divisibility sequences (EDS), which are sequences E_n associated to rational points on elliptic curves satisfying \gcd(E_m, E_n) = E_{\gcd(m,n)} for positive integers m and n. This divisibility relation mirrors the key property used in proofs for binomial coefficients, allowing the equality of GCDs for the two interlocking triangles in the "Star of David" configuration to hold analogously in EDS. Such extensions highlight connections between combinatorial identities and arithmetic properties of elliptic curves. In higher dimensions, generalizations appear in Pascal's pyramid, the three-dimensional analog of Pascal's triangle constructed from trinomial coefficients. Specific GCD properties have been established for symmetric configurations in the pyramid, such as those corresponding to tetrahedral arrangements around a central entry. For instance, for a configuration C consisting of two symmetric sets S₁ and S₂ of trinomial coefficients, \gcd(S_1) = \gcd(S_2) holds, with duality to LCM equalities in the modified Pascal pyramid via p-adic valuations.^[25] These results extend the two-dimensional hexagon to polyhedral structures, though full analogs of the product equality remain conjectural in general tetrahedral cases.^[25]^[26] Further extensions connect the theorem to polygon tilings in Pascal's triangle, where hexagons exhibiting the GCD property can tile larger polygons while preserving the equality. Korntved showed that any polygon tiled by fundamental hexagons (simple closed curves with the Star of David GCD equality) inherits the property, provided the tiling is restricted (e.g., adjacent hexagons share at most one vertex).^[20] For example, larger hexagons like 2×4×4 or 4×2×4 configurations, tiled by up to four fundamental units, satisfy \gcd(\{a_1, a_3, \dots \}) = \gcd(\{a_2, a_4, \dots \}) for alternating vertex sets.^[20] This framework links combinatorial tiling to divisibility, enabling constructions of infinite families of such polygons.^[20] In 2010, C. T. Long and E. Korntved extended the theorem to configurations involving equalities of more than two GCDs.^[27]