Disturbing the Dyson Conjecture (in a GOOD Way)

Andrew V. Sills and Doron Zeilberger^{∗}

Department of Mathematics, Rutgers University Hill Center, Busch Campus, Piscataway, NJ 08854-8019

2000 AMS Subject Classification 05-04 KEY WORDS: Dyson’s conjecture, constant term

submitted August 2, 2005; minor revisions November 22, 2005

Dedicated to Freeman John Dyson and Irving John Good

Abstract

We present a case study in experimental yet rigorous mathematics by describing an algorithm, fully implemented in both Mathematica and Maple, that automatically conjectures, and then automatically proves, closed-form expressions extending Dyson’s celebrated constant term conjecture.

1 Introduction

Let

F_{n}(x; a; b) := ∏_{h=1}^{n} x_{h}^{−b_{h}} ∏_{1≦i≠j≦n} (1 − \frac{x_{i}}{x_{j}} )^{a_{j}}

where x = ⟨x_{1}, x_{2}, …, x_{n}⟩, a = ⟨a_{1}, a_{2}, …, a_{n}⟩, b = ⟨b_{1}, b_{2}, …, b_{n}⟩ and

c_{n}(a, b) = CT(F_{n}(x; a; b)),

where CT(X) denotes the constant term, i.e. the coefficient of x_{1}^{0}x_{2}^{0} ⋯ x_{n}^{0}, in the expression X. The following conjecture is due to Freeman Dyson [Dyson 62, p. 152, Conjecture C]:

Dyson’s conjecture. For positive integers n and nonnegative integers a_{i}, 1 ≦ i ≦ n,

CT (F_{n}(x; a; 0)) = \frac{(a_{1} + a_{2} + ⋯ + a_{n})!}{a_{1}!a_{2}! ⋯ a_{n}!},

∗Partially supported by NSF grant DMS 0401124

where 0 = ⟨0, 0, …, 0⟩. Dyson noted that the n = 1, 2 cases are trivial and that the n = 3 case is equivalent to a hypergeometric summation formula due to A.C. Dixon [Dixon 03]. Dyson proved the n = 4 case [Dyson 62, pp. 155–156, Appendix B], and indicated that a similar argument could be used to prove n = 5, but that his argument would not work for n > 5, and accordingly left n > 5 as a conjecture. The conjecture was quickly proved independently by J. Gunson [Gunson 62] and K. Wilson [Wilson 62]. The most compact and elegant proof, however, was supplied by I. J. Good [Good 70]. A combinatorial proof was later given by Zeilberger [Zeilberger 82].

In this paper, we concern ourselves with variations on Dyson’s original conjecture where b can assume (fixed) values other than 0. In particular, we have automated, in the accompanying Mathematica package GoodDyson.m and analogous Maple package GoodDyson, both the act of conjecturing an explicit formula for c_{n}(a; b) (where b is a vector of specific integers), and the production of a proof of the conjectured form, based on a generalization of Good’s ideas. The accompanying Mathematica and Maple packages are avail-

able from the authors’ web sites http://www.math.rutgers.edu/~asills and
http://www.math.rutgers.edu/~zeilberg.

2 Automating the Conjecturing Process

Given b = ⟨b_{1}, …, b_{n}⟩, we guess that the coefficient of x_{1}^{b_{1}}x_{2}^{b_{2}} ⋯ x_{n}^{b_{n}} in F_{n}(x; a; 0), or equivalently, the constant term of F_{n}(x; a; b), which we denote by c_{n}(a; b), can be expressed in the form d_{n}(a; b), where

d_{n}(a; b) = R_{b}(a)\frac{(a_{1} + a_{2} + ⋯ + a_{n})!}{a_{1}!a_{2}! ⋯ a_{n}!},

and R_{b}(a) is a rational function in the a_{i}’s. Of course, if ∑_{i=1}^{n} b_{i} ≠ 0, then R_{b}(a) = 0, and in the case of Dyson’s original conjecture, we have R_{0}(a) = 1 for all n.

We programmed a Mathematica function/Maple procedure GuessRat, which takes as input a function f, a set of variables {a_{1}, … a_{n}}, and an integer t, and tries to match f to a rational function R in which the sum of the degrees of the numerator and denominator (let us call this the total degree of R) is t, using internally generated data. Of course, if no such R of total degree t is found, then the procedure is repeated with a larger t. GuessRat could potentially be useful in a wide variety of settings, but for this project we restricted f to the function which extracted the constant term from F (x; a; b)/\frac{(a_{1}+···+a_{n})!}{a_{1}!···a_{n}!} for a specific b in order to conjecture R_{b}(a). This is done via the auxiliary function

GuessDysonCoeff.

Empirical evidence gathered while testing a prototype version of GuessDysonCoeff suggested that for each b_{i} < 0, the R_{b}(a) contained a factor of

\frac{1}{(1 + a_{i})_{⌊b_{i}/2⌋}(1 + a_{1} + a_{2} + ⋯ + a_{i−1} + a_{i+1} + ⋯ + a_{n})_{|b_{i}|}} ,

where (y)_{h} denotes the rising factorial, which is defined by

(y)_{h} := \{ \begin{matrix}y(y + 1)(y + 2) ⋯ (y + h − 1), & if h > 0, \\ 1, & if h = 0, \\ \frac{1}{(y−1)(y−2)···(y−h)}, & if h < 0. \end{matrix}

For example, closed form representation of the constant term of F_{4}(x; a; ⟨−3, b_{2}, −1, 4 − b_{2}⟩) contains the factor

\frac{a_{1}(a_{1} − 1)a_{3}}{(1 + a_{2} + a_{3} + a_{4})(2 + a_{2} + a_{3} + a_{4})(3 + a_{2} + a_{3} + a_{4})(1 + a_{1} + a_{2} + a_{4})}.

Accordingly, we modified the f which was sent as input into GuessRat via the GuessDysonCoeff function, resulting in the output R being of lower total degree, and therefore greatly reducing the time Mathematica/Maple needs to supply a conjecture. For a vector b whose components sum to zero, let us define the complexity of b, Comp(b), to be the sum of its positive components, or equivalently,

Comp(b) := \frac{1}{2} ∑_{i=1}^{n} |b_{i}|.

When the complexity of of b is close to zero, the modified algorithm worked over twenty times faster than the original. For larger complexity, the speedup was even more significant. For instance, in the case ⟨b_{1}, b_{2}, b_{3}⟩ = ⟨4, −2, −2⟩, the modified algorithm was over one hundred times faster than the original.

3 The Generalized Good Proof

For some fixed n and b, we want to show that for all a,

c_{n}(a; b) = d_{n}(a; b),  (3.1)

where an explicit closed form expression d_{n}(a; b) for c_{n}(a; b) has been conjectured using Mathematica or Maple. Since the n = 1 case is trivial, and the n = 2 case

c_{2}(⟨a_{1}, a_{2}⟩; ⟨b_{1}, b_{2}⟩) = \{ \begin{matrix}(−1)^{b_{1}} \frac{(a_{1} + a_{2})!}{(a_{1} + b_{1})!(a_{2} − b_{1})!}, & if b_{1} = −b_{2} \\ 0, & otherwise \end{matrix}  (3.2)

follows from the binomial theorem, we restrict our attention to n > 2.

As in Good’s proof [Good 70], for a_{1}, a_{2}, …, a_{n} ≧ 1, F_{n}(x; a; b) satisfies the recursion

F_{n}(x; a; b) = ∑_{i=1}^{n} F_{n}(x; ⟨a_{1}, …, a_{i−1}, a_{i} − 1, a_{i+1}, …, a_{n}⟩; b).  (3.3)

Applying the constant term operator to both sides of (3.3), we obtain

c_{n}(a; b) = ∑_{i=1}^{n} c_{n}(⟨a_{1}, …, a_{i−1}, a_{i} − 1, a_{i+1}, …, a_{n}⟩; b).  (3.4)

Next, we note that for any fixed k, 1 ≦ k ≦ n,

F_{n}(x; ⟨a_{1}, …, a_{k−1}, 0, a_{k+1}, …, a_{n}⟩; b) = F_{n−1}(x̂^{(k)}, â^{(k)}, 0) [x_{k}^{−b_{k}}_{∏_{i=1}^{n} ; i≠k} \frac{(x_{i} − x_{k})^{a_{i}}}{x_{i}^{a_{i}+b_{i}}} ] ,

(3.5)

where x̂^{(k)} = ⟨x_{1}, …, x_{k−1}, x_{k+1}, … x_{n}⟩ and â^{(k)} = ⟨a_{1}, …, a_{k−1}, a_{k+1}, … a_{n}⟩. Notice that on the right hand side of (3.5), we have managed to segregate the factors involving x_{k} (those in brackets) from those which do not involve x_{k}. We can therefore let Mathematica or Maple find the explicit Taylor series expansion of \begin{matrix}∏ & {n \atop i=1} \\ i≠k \end{matrix} \frac{(x_{i}−x_{k})^{a_{i}}}{x_{i}^{a_{i}+b_{i}}} about x_{k} = 0. And so, by extracting the coefficient of x_{k}^{0} on

both sides of (3.5), we have, for 1 ≦ k ≦ n,

coeff of x_{k}^{0} in [F_{n}(x; ⟨a_{1}, …, a_{k−1}, 0, a_{k+1}, …, a_{n}⟩; b)]  (3.6)

= coeff of x_{k}^{0} in [(x_{k}^{−b_{k}}_{∏_{i=1}^{n} ; i≠k} \frac{(x_{i} − x_{k})^{a_{i}}}{x_{i}^{a_{i}+b_{i}}} ) F_{n−1}(x̂^{(k)}, â^{(k)}, 0)] .

Finally, we apply the constant term operator to both sides of (3.6) to obtain

c_{n}(⟨a_{1}, …, a_{k−1}, 0, a_{k+1}, …, a_{n}⟩; b)  (3.7)
= P_{k} c_{n−1}(â^{(k)}, 0),

where P_{k} is the coefficient of x_{k}^{b_{k}} in the Taylor expansion of \begin{matrix}∏ & {n \atop i=1} \\ i≠k \end{matrix} \frac{(x_{i}−x_{k})^{a_{i}}}{x_{i}^{a_{i}+b_{i}}} about

x_{k} = 0. Notice that P_{k} is a Laurent polynomial in x_{1}, …, x_{k−1}, x_{k+1}, …, x_{n}, whose coefficients depend on a_{1}, …, a_{k−1}, a_{k+1}, …, a_{n}. (In the case where b = 0, we have P_{k} = 1, making Good’s proof very tidy indeed!) Finally, we note the initial condition

c_{n}(0; b) = \{ \begin{matrix}1, & if b = 0 \\ 0, & otherwise. \end{matrix}  (3.8)

The equation (3.4), the set of n boundary conditions (3.7), together with (3.8) fully determine c_{n}(a; b). Thus, to prove (3.1), it suffices to show that our conjectured formula d_{n}(a; b) also satisfies (3.4), (3.7), and (3.8). The equations (3.7) will, in general, depend on c_{n−1}(a; b) for various values of b, and so the boundary conditions will need to be iterated n − 2 times until (3.7) is expressed fully in terms of c_{2}’s which is given by (3.2).

4 Example

The coefficient of \frac{x_{1}^{2}}{x_{2}x_{3}} in the expansion of the Laurent polynomial

[(1 − \frac{x_{2}}{x_{1}} ) (1 − \frac{x_{3}}{x_{1}} )]^{a_{1}} [(1 − \frac{x_{1}}{x_{2}} ) (1 − \frac{x_{3}}{x_{2}} )]^{a_{2}} [(1 − \frac{x_{1}}{x_{3}} ) (1 − \frac{x_{2}}{x_{3}} )]^{a_{3}}

is

d_{3}(⟨a_{1}, a_{2}, a_{3}⟩; ⟨2, −1, −1⟩) = \frac{a_{2}a_{3}(2 + 2a_{1} + a_{2} + a_{3})(a_{1} + a_{2} + a_{3})!}{(1 + a_{1} + a_{2})(1 + a_{1} + a_{3})(1 + a_{1})a_{1}!a_{2}!a_{3}!}.

Good style proof. It is easily verified that for a_{1}, a_{2}, a_{3} ≧ 1,

F_{3}(x; a; ⟨2, −1, −1⟩) = F_{3}(x; ⟨a_{1} − 1, a_{2}, a_{3}⟩; ⟨2, −1, −1⟩)  (4.1)
+F_{3}(x; ⟨a_{1}, a_{2} − 1, a_{3}⟩; ⟨2, −1, −1⟩)
+F_{3}(x; ⟨a_{1}, a_{2}, a_{3} − 1⟩; ⟨2, −1, −1⟩)

Applying the constant term operator to both sides of (3.3), we immediately obtain

c_{3}(a; ⟨2, −1, −1⟩) = c_{3}(⟨a_{1} − 1, a_{2}, a_{3}⟩; ⟨2, −1, −1⟩)  (4.2)
+c_{3}(⟨a_{1}, a_{2} − 1, a_{3}⟩; ⟨2, −1, −1⟩)
+c_{3}(⟨a_{1}, a_{2}, a_{3} − 1⟩; ⟨2, −1, −1⟩)

The boundary conditions are found by GoodDyson to be

c_{3}(⟨0, a_{2}, a_{3}⟩; ⟨2, −1, −1⟩) = \frac{a_{3}(a_{3} − 1)}{2}c_{2}(⟨a_{2}, a_{3}⟩; ⟨−1, 1⟩)

+\frac{a_{2}(a_{2} − 1)}{2}c_{2}(⟨a_{2}, a_{3}⟩; ⟨1, −1⟩)

+a_{2}a_{3}c_{2}(⟨a_{2}, a_{3}⟩; ⟨0, 0⟩)  (4.3)
c_{3}(⟨a_{1}, 0, a_{3}⟩; ⟨2, −1, −1⟩) = 0  (4.4)
c_{3}(⟨a_{1}, a_{2}, 0⟩; ⟨2, −1, −1⟩) = 0  (4.5)

Finally,

c_{3}(⟨0, 0, 0⟩; ⟨2, −1, −1⟩) = 0  (4.6)

Since c_{3}(a; ⟨2, −1, −1⟩) is uniquely determined by (4.2)–(4.6), and it is easily verified that, in light of (3.2), our conjectured expression d_{3}(a; ⟨2, −1, −1⟩) also satisfies (4.2)–(4.6), the proof is complete.

Full proofs, analogous to the above, can be generated automatically with our Mathematica function/Maple procedure WritePaper.

5 Exploiting Symmetry and Algebraic Relations

Suppose d_{n}(a; b) is known for some particular b. It is then a simple matter to determine d_{n}(a; b′) for all vectors b′ whose components are a permutation of the components of b: if π_{b} permutes the indices of b = ⟨b_{1}, b_{2}, …, b_{n}⟩, so that π_{b}b = b′, then d_{n}(a; b′) = d_{n}(π_{a}a; b). For example, given

d_{3}(a; ⟨−1, 0, 1⟩) = −\frac{(a_{1} + a_{2} + a_{3})!a_{1}}{a_{1}!a_{2}!a_{3}!(1 + a_{2} + a_{3})},

we immediately know that

d_{3}(a; ⟨1, 0, −1⟩) = −\frac{(a_{1} + a_{2} + a_{3})!a_{3}}{a_{1}!a_{2}!a_{3}!(1 + a_{2} + a_{1})},

d_{3}(a; ⟨0, −1, 1⟩) = −\frac{(a_{1} + a_{2} + a_{3})!a_{2}}{a_{1}!a_{2}!a_{3}!(1 + a_{1} + a_{3})},

etc.

Also, notice that

F_{n}(x; a+⟨0, 0, …, 0, 1⟩; b) = F_{n}(x; a; b) [(1 − \frac{x_{1}}{x_{n}} ) (1 − \frac{x_{2}}{x_{n}} ) ⋯ (1 − \frac{x_{n−1}}{x_{n}} )] .

By expanding out the Laurent polynomial in brackets, distributing it over the F_{n}(x; a; b) and applying the constant term operator, one can often express a d_{n}(x; a; b) with a b of higher complexity as a linear combination of d_{n}(x; a; b)’s with b’s that have previously been calculated and/or have lower complexity. For example,

F_{3}(x; a + ⟨0, 0, 1⟩; b)
= F_{3}(x; a; b) (1 − \frac{x_{1}}{x_{3}} ) (1 − \frac{x_{2}}{x_{3}} )
= F_{3}(x; a; b) (1 − \frac{x_{1}}{x_{3}} − \frac{x_{2}}{x_{3}} + \frac{x_{1}x_{2}}{x_{3}^{2}} )
= F_{3}(x; a; b) − F_{3}(x; a; b + ⟨−1, 0, 1⟩) − F_{3}(x; a; b + ⟨0, −1, 1⟩) + F_{3}(x; a; b + ⟨−1, −1, 2⟩)

After applying the constant term operator to both sides and solving for the last term, we find that

d_{3}(a; b+⟨−1, −1, 2⟩) = d_{3}(⟨a_{1}, a_{2}, 1+a_{3}⟩; b)−d_{3}(a; b)+d_{3}(a; b+⟨−1, 0, 1⟩)+d_{3}(a; b+⟨0, −1, 1⟩)

By systematically taking advantage of the above observations, the procedure TurboDyson can find d_{n}(a; b) for a given n and all b’s of complexity less than or equal to a given complexity C rather quickly. Furthermore, TurboDyson stores its findings in an indexed global variable for future use, e.g. a subsequent call to the WritePaper procedure.

6 Conclusion

Experimental mathematics, as it is commonly understood, consists of computerassisted gathering of data (usually numeric, but recently also symbolic) that stimulates and inspires human-made conjectures, that, in turn, require humanmade proofs. The novelty of the present research is that all these phases are done by machine, once the initial effort of designing an algorithm, and implementing it, are done by humans. Of course, at present, the general framework for the conjecture, and the idea of proof, are still human-made (in our case by two very illustrious humans: Dyson and Good), but all the rest is automatic. We believe that this methodology should be applicable to many other problems.

References

[Dixon 03] A. C. Dixon. “Summation of a certain series.” Proc. London Math Soc. (1) 35 (1903), 285–289.

[Dyson 62] F. J. Dyson. “Statistical theory of the energy levels of complex systems I.” J. Math. Phys. 3 (1962), 140–156.

[Good 70] I. J. Good. “Short proof of a conjecture of Dyson.” J. Math. Phys. 11 (1970), 1884.

[Gunson 62] J. Gunson. “Proof of a conjecture of Dyson in the statistical theory of energy levels.” J. Math. Phys. 3 (1962), 752–753.

[Wilson 62] K. Wilson. “Proof of a conjecture by Dyson.” J. Math. Phys. 3 (1962), 1040–1043.

[Zeilberger 82] D. Zeilberger. “A combinatorial proof of Dyson’s conjecture.” Discrete Math. 41 (1982), 317–332.