Combinatorial calculations in the tree quotient modules of the Grossman-Larson algebra.

David Wright gives [1] an inversion formula for the symmetric case of the Jacobian Conjecture and relates it to the Grossman-Larson Hopf Algebra [2, 3, 4]. Wright uses these tools to prove the symmetric Jacobian Conjecture for the case $F = X-H$ with $H$ homogeneous and $JH^3 = 0$, and poses a combinatorial statement which would imply the Jacobian Conjecture. Central to the proofs of Wright's results are explicit combinatorial computations in the tree quotient modules of the Grossman-Larson algebra.

Our program automates the aforementioned combinatorial computations. This involves the implementation of efficient algorithms for the enumeration of free and rooted trees with degree and geodesic bounds, as well as algorithms for algebraic computations within the Grossman-Larson Algebra. As a consequence of our computations, the Jacobian Conjecture is shown to hold in the cubic symmetric case when $JH^4 = 0$. The program is implemented in Java, and its size currently stands at 1800 lines of code.

To generate all free trees of a given size, we use a constant amortized algorithm described in [5]. Implentations of the Li-Rusky algorithm in C can be found on the Combinatorial Object Server (COS). We also use the Java linear algebra package JAMA extensively for our computations (particularly for rank calculations), and it is needed in order to execute our code. JAMA is freely available online; you may download the package, as well as access the documentation here.

More Information

Please contact Li-Yang Tan for more information.

References

[1] David Wright, The Jacobian Conjecture as a problem in combinatorics, arXiv.org/math.CO/0511214
[2] An introduction to the Grossman-Larson Algebra: http://www.rgrossman.com/trees.html. Contains references to recent work.
[3] R. Grossman and R. Larson, Hopf algebraic structures of families of trees, Journal Algebra, Vol. 26, 1989, pp. 184-210. [PDF]
[4] R. Grossman and R. Larson, Hopf-algebraic structure of combinatorial objects and differential operators, Israel Journal Mathematics, Vol. 72, 1990, pp. 109-117. [PDF]
[5] G. Li and F. Ruskey, The Advantages of Forward Thinking in Genearating Rooted and Free Trees, ACM-SIAM Symposium on Discrete Algorithms 1999.