text:
# The algebraic entropy of classical mechanics

## 1 Introduction. Classes of Lie algebras.

The class of ‘simple mechanical systems’ are defined by pairs $`(Q,V)`$, where the configuration space $`Q`$ is a real Riemannian manifold and the potential energy $`V`$ is a smooth real function on $`Q`$. The phase space $`T^{}Q`$ has a canonical Poisson bracket and a kinetic energy $`T:T^{}Q`$ associated with the metric on $`Q`$. In general, the smooth functions on a Poisson manifold form a Lie algebra under the Poisson bracket. In the case of a simple mechanical system, we are given two distinguished functions, namely the kinetic and potential energies, and one can ask what Lie algebra they generate under the Poisson bracket.

In this paper we study, not the Lie algebra generated by a particular $`V`$ and $`T`$, but the Lie algebra defined by the whole class of simple mechanical systems. That is, one should think of the dimension of $`Q`$ as being arbitrarily large, and the metric and potential energies also being arbitrary.

This question arose out of very practical considerations of the calculations required to derive high-order symplectic integrators by splitting and composition, used in applications including molecular, celestial, and accelerator dynamics . The vector field $`X`$ which is to be integrated is split as $`X=A+B`$, where $`A`$ and $`B`$ have the same properties (e.g. Hamiltonian) as $`X`$, but can be integrated exactly. We write $`\mathrm{exp}(tX)`$ for the time-$`t`$ flow of $`X`$. The most common such integrator is the leap-frog method

$$\phi (\tau ):=\mathrm{exp}(\frac{1}{2}\tau A)\mathrm{exp}(\tau B)\mathrm{exp}(\frac{1}{2}\tau A),$$

where the small parameter $`\tau `$ is the time step.

From the Baker-Campbell-Hausdorff formula , the map $`\phi (\tau )`$ can be represented (up to any power in $`\tau `$) as a flow $`\mathrm{exp}(\tau \stackrel{~}{X})`$, where

$$\stackrel{~}{X}=A+B+\tau ^2(\frac{1}{12}[B,[B,A]]\frac{1}{24}[A,[A,B]]))+𝒪(\tau ^4).$$
(1)
Because it is the flow of a vector field $`𝒪(\tau ^2)`$-close to the original one, the integrator is second order. The function $`\stackrel{~}{X}`$ is called the modified vector field in the numerical integration literature .

For simple mechanical systems, we split the Hamiltonian as $`H=T+V`$. The flow of (the Hamiltonian vector field of) $`V`$ can of course always be calculated easily, but calculating the flow of the kinetic energy $`T`$ requires that $`Q`$ have integrable (and even fairly simple) geodesics. Because the Lie algebras of Hamiltonian vector fields and of Hamiltonian functions are isomorphic under $`[X_T,X_V]=X_{\{V,T\}}`$, there is a series formally identical to Eq. (1) involving the Hamiltonians $`T`$ and $`V`$ with respect to the Poisson bracket.

In the series of Eq. (1) we see the Lie algebra generated by $`A`$ and $`B`$ entering. Such series, for example in the proof of the BCH formula, are usually considered in the context of the free Lie algebra $`L(A,B)`$ with two generators $`A`$ and $`B`$. One can in fact consider the more general composition

$$\underset{i=1}{\overset{s}{}}\mathrm{exp}(a_i\tau A)\mathrm{exp}(b_i\tau B)=\mathrm{exp}(Z)$$
(2)
where $`ZL(A,B)`$. Requiring $`Z=\tau (A+B)+O(\tau ^{p+1})`$ for some integer $`p>1`$ gives a system of equations in the $`a_i`$ and $`b_i`$ which must be satisfied for the method to have order $`p`$. In the case of general $`A`$ and $`B`$, then, at each order $`n=1,\mathrm{},p`$ there are $`dimL_n(A,B)`$ such order conditions. Here $`L_n(A,B)`$ is the subspace of $`L(A,B)`$ consisting of homogeneous elements of order $`n`$. Witt’s formula  states that

$$dimL_n(A,B)=\frac{1}{n}\underset{d|n}{}\mu (d)2^{n/d}$$
(3)
where $`\mu (d)`$ is the Möbius function defined by $`\mu (1)=1`$, $`\mu (d)=(1)^k`$ if $`d`$ is the product of $`k`$ distinct primes, and $`\mu (d)=0`$ otherwise. Notice that in this case

$$dimL_n(A,B)\frac{2^n}{n};$$

the dimensions grow exponentially with $`n`$. The base (2 in this case) of the exponent is called the entropy of $`L(A,B)`$. In general, the entropy of a graded vector space $`L_n`$ is

$$\underset{n\mathrm{}}{lim\; sup}(dimL_n)^{1/n},$$

if this limit exists . (We shall use generalizations of Witt’s formula  to calculate the dimensions and entropies of other free Lie algebras, see Eqs. (15), (17) below.)

In this approach it is assumed that there are no Lie identities satisfied by the vector fields $`A`$ and $`B`$. This is reasonable if one wants the method to work for all $`A`$ and $`B`$. However, in the case of simple mechanical systems, the Lie algebra is never free, regardless of $`T`$, $`V`$, or the dimension of the system. There are always identities satisfied by kinetic and potential energy. The simplest of these is

$$\{V,\{V,\{V,T\}\}\}0.$$
(4)
For, working in local coordinates $`(q,p)`$ with $`T=\frac{1}{2}p^TM(q)p`$, and recalling the canonical Poisson bracket $`\{A,B\}:=_i\frac{A}{q_i}\frac{B}{p_i}\frac{A}{p_i}\frac{B}{q_i},`$ we have that

$$\{V,T\}=\underset{i,j}{}\frac{V}{q_i}M_{ij}(q)p_j$$

is of degree 1 in $`p`$, and that

$$\{V,\{V,T\}\}=\underset{i,j}{}\frac{V}{q_i}M_{ij}\frac{V}{q_j}$$
(5)
is a function of $`q`$ only. So $`V`$ and $`\{V,\{V,T\}\}`$ commute.

Thus, it was realized early on  that in deriving high-order integrators as in Eq. (2) for simple mechanical systems, the order conditions corresponding to $`\{V,\{V,\{V,T\}\}\}`$ and to all its higher Lie brackets can be dropped. This means that more efficient integrators can be designed for this class of systems. Much work has been done on this special case, both because of its intrinsic theoretical and practical importance, and because it allows such big improvements over the general case. For example, one can design special (‘corrector’ or ‘processor’) methods of the form $`\phi \psi \phi ^1`$ , special methods for nearly-integrable systems such as the solar system , special methods involving exact evaluation of the forces associated with the ‘modified potential’ (Eq. 5) , and so on—see  for a survey. All of these studies rely on the structure of the Lie algebra generated by kinetic and potential energy. Bases for this Lie algebra have been constructed, more or less by hand, for small orders . In particular, Murua  associates a unique tree of a certain type to each independent order condition of symplectic Runge-Kutta-Nyström methods (very closely related to the problem considered here), and enumerates these up to order 6. (Iserles et al.  extend this approach to some other classes of polynomial vector fields.) However, a systematic description of the entire Lie algebra is clearly preferred.

Not many classes of Lie algebras have been completely described. Here are two examples from the literature. First, Duchamp and Krob  completely describe all partially-commutative Lie algebras

$$L(A_1,\mathrm{},A_n;[A_i,A_j]=0,(i,j)C)$$

where $`C`$ specifies the pairs of commuting variables. Second, Kirillov, Kontsevich, and Molev  studied the Lie algebra $`L`$ generated by two vector fields on $``$ in general position, conjectured that

$$\underset{\sigma S_4}{}(1)^{sgn(\sigma )}[x_{\sigma (1)},x_{\sigma (2)},x_{\sigma (3)},x_{\sigma (4)},y]=0x_1,x_2,x_3,x_4,yL$$
(6)
generates all identities, and calculated the dimensions of its homogeneous subspaces and the asymptotic growth of their dimension. If their conjecture is true, $`L`$ is a PI-algebra , one which the identities which hold in the Lie algebra (such as Eq. (6)) are satisfied by all elements of the Lie algebra.

Returning to the case of simple mechanical systems, it is clear that every Lie bracket of $`T`$ and $`V`$ is a homogeneous polynomial in $`p`$. Furthermore, the degrees of these polynomials combine in a natural way. We therefore introduce the following class $`𝔓`$ of Lie algebras.

We use the notation $`[XY]:=[X,Y]`$, $`[XYZ]:=[X,[Y,Z]]`$, and for sets $`𝔛`$, $`𝒴`$, $`[𝔛𝒴]:=[𝔛,𝒴]:=\{[X,Y]:X𝔛,Y𝒴\}`$.

###### Definition 1

A Lie algebra $`L`$ is of class $`𝔓`$ (‘polynomially graded’) if it is graded, i.e. $`L=_{n0}L_n`$, and its homogeneous subspaces $`L_n`$ satisfy

| $`[L_n,L_m]L_{n+m1}\text{ if }n>0\text{ or }m>0\text{; and}`$ |
| --- |
| $`[L_0,L_0]=0`$ |

(7)
Note that this implies $`[(L_0)^{n+1}L_n]=0`$ for all $`n`$. We call the grading of $`L`$ its grading by degree.

For example, the Lie algebra generated by kinetic and potential energy is of class $`𝔓`$, where the grading is by total degree in $`p`$. The Lie algebra of all polynomial vector fields on a linear space is of class $`𝔓`$, where the grading is by total degree. We will give more examples later.

Such a grading is quite different from the natural grading of a free Lie algebra. Two important differences are that (i) It is not abelian. For, $`[L_2,[L_0,L_0]]=0`$ while $`[L_0,[L_0,L_2]]L_0`$. (ii) It is not finite, in the sense that elements of $`L_n`$ are Lie brackets of unboundedly many other elements of $`L`$. For example, the bracket of any number of elements of degree 1 is still of degree 1.

We also need the concept of a Lie algebra which is free in a certain class.

###### Definition 2

 Let $`F`$ be a Lie algebra of class $`𝔓`$ generated by a set $`𝔛`$. Then $`F`$ is called a free Lie algebra in the class $`𝔓`$, freely generated by the set $`𝔛`$, if for any Lie algebra $`R`$ of class $`𝔓`$, every mapping $`𝔛R`$ can be extended to a unique homomorphism $`FR`$. We write $`F=L_𝔓(𝔛)`$.

In addition to the grading by degree, $`L_𝔓(𝔛)`$ also carries the standard grading which we call the grading by order, generated by $`order(X)=1`$ for all generators $`X𝔛`$ and $`order([Y,Z])=order(Y)+order(Z)`$. (The term order is chosen here because it corresponds to order in the sense of numerical integrators, as in Eq. (1)).

Because of the importance of the grading by degree for Lie algebras generated by kinetic and potential energy, we make the following definition.

###### Definition 3

The Lie algebra $`L_𝔓(A,B)`$, free in the class $`𝔓`$, where $`A`$ has degree 2 and $`B`$ has degree 0, is called the Lie algebra of classical mechanics.

Two Lie algebras of class $`𝔓`$ are easy to describe. First, the Lie algebra with $`k`$ generators of degree $`1`$ which is free in the class $`𝔓`$ is just the standard free Lie algebra on $`k`$ generators—the degrees can never decrease if the Lie algebra has no elements of degree 0. Second, the Lie algebra with generators $`𝔛=\{X_1,\mathrm{},X_k\}`$ of degree 0 and generators $`𝒴=\{Y_1,\mathrm{},Y_l\}`$ of degree 1, free in the class $`𝔓`$, is $`𝒴_{n0}[𝒴^n𝔛]`$, and only contains elements of degree 0 and 1. (In both of these cases, the grading by degree is in fact abelian.)

However, we want to describe the Lie algebra of classical mechanics, $`L_𝔓(A,B)`$. This is the simplest nontrivial case as it includes the essential feature of $`𝔓`$ that degrees can both increase and decrease under Lie brackets.

The paper is organized as follows. In Section 2, we give a construction which describes $`L_𝔓(A,B)`$ as the direct sum of an abelian and a free Lie algebra, both with an infinite number of generators. In Section 3, we enumerate the dimensions of the homogeneous (by order) components of $`L_𝔓(A,B)`$ and hence in Section 4 numerically compute its entropy. Section 5 considers special cases (e.g., of mechanical systems with Euclidean metric; these turn out not to be free in the class $`𝔓`$) and other examples of polynomially-graded Lie algebras.

## 2 Structure of the Lie algebra of classical mechanics.

Let $`\psi :L(A,B)L_𝔓(A,B)`$ be the unique homomorphism from the free Lie algebra to the free Lie algebra of class $`𝔓`$. The kernel $`\mathrm{ker}\psi `$ can be thought of as the set of identities of $`L_𝔓(A,B)`$. For example, we showed above (Eq. (4)) that $`[BBBA]\mathrm{ker}\psi `$. This implies that $`[CBBBA]\mathrm{ker}\psi `$ for all $`CL(A,B)`$. However, we will see below that $`[BBBA]`$ is not the only generator of the ideal $`\mathrm{ker}\psi `$.

Our description of $`L_𝔓(A,B)`$ is based on the following two observations. First, suppose one wants to describe the Lie algebra with three generators $`A,B,C`$ which is free in the class of Lie algebras with $`C=0`$. Since $`C`$ generates all identities in this class, this Lie algebra is just $`L(A,B)`$: one merely has to drop the generator $`C`$. To generalize this idea, suppose the free Lie algebra $`L(A,B)`$ can be factored as $`_iL(𝔛_i)`$ for certain generating sets $`𝔛_i`$ with elements in $`L(A,B)`$, such that some subset $`𝒴`$ of $`_i𝔛_i`$ generates all the identities in $`𝔓`$. Then, we have

$$L_𝔓(A,B)\underset{i}{}L(𝔛_i\backslash (𝒴𝔛_i))$$
(8)
—again, we merely drop these generators.

If $`𝒴`$ only generates some of the identities of $`𝔓`$, then dropping these generators gives a sum of free Lie algebras which is surjectively homomorphic to $`L_𝔓(A,B)`$. This can be used to get upper bounds for the dimensions of the homogeneous subspaces of $`L_𝔓(A,B)`$.

Second, given a description of $`L_𝔓(A,B)`$ as such a sum (Eq. 8) of free Lie algebras, we can apply standard techniques to describe it in detail, for example to construct bases, to compute its dimensions with respect to degree and/or order, and to compute the asymptotic growth of these dimensions.

We begin by stating the crucial tool we shall use, the Lazard factorization of free Lie algebras.

###### Theorem 1

 Let $`𝔛`$ and $`𝒴`$ be sets of generators. Then

$$L(𝔛𝒴)L(𝒴)L(_{n0}[𝒴^n𝔛]).$$

Applying the Lazard factorization to $`L(A,B)`$ with $`𝔛=\{A\}`$, $`𝒴=\{B\}`$, gives

$$L(A,B)=BL(A,[BA],[BBA],[BBBA],\mathrm{})$$

where the elements $`[B^nA]`$ for $`n3`$ are all identities in $`𝔓`$. Thus, $`L_𝔓(A,B)`$ is surjectively homomorphic to $`BL(A,[BA],[BBA])`$. The three generators have degrees 2 ($`A`$), 1 ($`[BA]`$), and 0 ($`[BBA]`$). The idea now is to eliminate this new element of degree 0. (Formally, the generators $`[B^nA]`$, $`n3`$, do remain in the generating set; but they and all succeeding Lie brackets of them will be dropped at the final stage when we pass to $`L_𝔓(A,B)`$, so we do not need to keep track of them and just indicate them by $``$.) This gives

| $`L(A,B)`$ | $`BL(A,[BA],[BBA],)`$ |
| --- | --- |
|  | $`B[BBA]L(A,[BA],[BBA,A],[BBA,BA],[BBA,BBA,A]),)`$ |

where the generators now have degrees 2, 1, 1, 0, and 0 respectively. Continuing in this way we get the following.

###### Theorem 2

Let the degree of $`A`$ be 2 and the degree of $`B`$ be 0 with respect to the polynomial grading (Eq. 7). Then for all $`k0`$ we have the following isomorphism,

$$L(A,B)𝒵_kL(A,𝔛_k,𝒴_k,)$$

where

| $`𝔛_0=\mathrm{},𝔛_{k+1}`$ | $`=𝔛_k[𝒴_k,A],`$ |
| --- | --- |
| $`𝒴_0=\{B\},𝒴_{k+1}`$ | $`=[𝒴_k,𝔛_k][𝒴_k,𝒴_k,A]=[𝒴_k,𝔛_{k+1}],`$ |
| $`𝒵_0=\mathrm{},𝒵_{k+1}`$ | $`=𝒵_k𝒴_k,`$ |

(9)
and $``$ represents generators which are zero in $`𝔓`$, i.e., elements of the kernel of the homomorphism $`L(A,B)L_𝔓(A,B)`$. The generating sets have the following properties:

1. All elements of $`𝒴_k`$ and $`𝒵_k`$ have degree 0, and all elements of $`𝔛_k`$ have degree 1.
2. The Lie algebra spanned by $`𝒵_k`$ is abelian.
3. $`𝔛_k=[𝒵_k,A]`$.
4. All elements of $`𝒴_k`$ and $`𝒵_k`$ have odd order, and all elements of $`𝔛_k`$ have even order.
5. The element of smallest order in $`𝒴_k`$ is $`(1)^k[[BA]^kB]`$, with order $`2k+1`$.
6. The element of largest order in $`𝒴_k`$ is $`B_k`$, defined recursively by $`B_0=B`$, $`B_{k+1}=[B_k,[B_k,A]]`$. It has order $`2^{k+1}1`$.
7. The finite sets $`𝔛_k`$ and $`𝒵_k`$ converge to infinite sets $`𝒵`$ and $`𝔛=[𝒵,A]`$ in the sense that the sets

$$\{X:X𝔛_k,order(X)n\}$$

are all equal for $`kn/2`$. We have

$$L(A,B)𝒵L(A,𝔛,)$$

and

$$L_𝔓(A,B)𝒵L(A,𝔛).$$
(10)
8. The sizes of the sets $`𝔛_k`$ and $`𝒴_k`$ obey the iteration

| $`|𝔛_{k+1}|`$ | $`=|𝔛_k|+|𝒴_k|`$ |
| --- | --- |
| $`|𝒴_{k+1}|`$ | $`=|𝒴_k||𝔛_{k+1}|`$ |

(11)
with initial conditions $`|𝔛_0|=0`$, $`|𝒴_0|=1`$. This iteration generates the sequence of $`|𝔛_k|`$ values

$$0,1,2,4,12,108,10476,108625644,\mathrm{};$$
(12)
there is a constant $`\gamma 1.1555`$ such that for sufficiently large $`k`$, $`|𝔛_k|=[\gamma ^{2^k}]`$.

Proof The iteration results from successive elimination of elements of degree 0, each iteration introducing only a finite number of new elements nonzero in $`𝔓`$, which have degrees 0 and 1. The other points then follow easily. The final description of $`L_𝔓(A,B)`$, Eq. (10), follows because the generators of $`L(A,𝔛,)`$ have degree 2 ($`A`$), 1 ($`𝔛`$), or are identically zero ($``$). Therefore $`L(A,𝔛,)`$ contains no elements of degree 0, so $`L_𝔓(A,𝔛)=L(A,𝔛)`$. The sequence of Eq. (12) is Sloane’s sequence A001696 , which comes from the same iteration (Eq. 11); the reference there to  shows how to establish its doubly-exponential growth. $``$

The rapid growth of the sets $`𝔛_k`$ and $`𝒴_k`$ means that it is impossible to carry out the iteration exactly very far. In practice the generating set $`𝒵`$ can be found up to any order $`n`$ by dropping any terms of order $`>n`$ as soon they appear in $`𝒴_k`$ (i.e., by quotienting all Lie algebras by the ideal consisting of all elements of order $`>n`$). We then have $`𝒴_{[(n+1)/2]}=0`$ and the iteration terminates.

The results of the six iterations required when $`n=12`$ are shown in Table 1. We name the elements of $`𝒵`$ $`Z_1`$, $`Z_2,\mathrm{}`$ as they are successively generated by the algorithm. This gives a short description of the elements of $`(L_𝔓)_n(A,B)`$ of order $`12`$ in terms of 14 elements of degree 0, 14 elements of degree 1, and 1 element of degree 2, which generate a total of 283 elements of weight $`12`$ (see Tables 2 and 3).

## 3 Dimensions of the homogeneous components.

We now turn to the enumeration of $`𝔛_k`$ and $`𝒴_k`$ by order. We introduce the generating functions

| $`x_k(t)`$ | $`={\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}\left|\{X𝔛_k:order(X)=n\}\right|t^n`$ |
| --- | --- |
| $`\stackrel{~}{y}_k(t)`$ | $`={\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}\left|\{Y𝒴_k:order(Y)=n\}\right|t^n`$ |
| $`\stackrel{~}{z}_k(t)`$ | $`={\displaystyle \underset{n=1}{\overset{\mathrm{}}{}}}\left|\{Z𝒵_k:order(Z)=n\}\right|t^n`$ |

which from Eq. (9) obey

| $`x_0`$ | $`=0,`$ |
| --- | --- |
| $`\stackrel{~}{y}_0`$ | $`=0,`$ |
| $`\stackrel{~}{z}_0`$ | $`=t,`$ |
| $`x_{k+1}`$ | $`=x_k+t\stackrel{~}{y}_k,`$ |
| $`\stackrel{~}{y}_{k+1}`$ | $`=\stackrel{~}{y}_kx_{k+1},`$ |
| $`\stackrel{~}{z}_{k+1}`$ | $`=\stackrel{~}{z}_k+\stackrel{~}{y}_k.`$ |

We can eliminate the $`t`$-dependence of this map by introducing $`y_k=t\stackrel{~}{y}_k`$ and $`z_k=t\stackrel{~}{z}_k`$. Then $`z_kx_k`$ for all $`k`$ and the rest of the system is

| $`x_0`$ | $`=0,`$ |
| --- | --- |
| $`y_0`$ | $`=t^2,`$ |
| $`x_{k+1}`$ | $`=x_k+y_k,`$ |
| $`y_{k+1}`$ | $`=y_kx_{k+1}.`$ |

(13)
The polynomials $`x_k(t)`$ converge to a formal power series $`x(t)`$. The polynomials $`y_k(t)`$ converge, again in the sense of formal power series, to 0. The power series $`x(t)`$ completely determines the dimensions of the homogeneous components of $`(L_𝔓)_n(A,B)`$ (including its abelian part $`𝒵`$, because $`z_k(t)=x_k(t)/t`$). We find

$$\begin{array}{cc}\hfill x(t)=& t^2+t^4+t^6+2t^8+3t^{10}+6t^{12}+12t^{14}+24t^{16}+50t^{18}+107t^{20}+232t^{22}+\hfill \\ & 508t^{24}+1124t^{26}+2513t^{28}+5665t^{30}+12858t^{32}+29356t^{34}+67371t^{36}+\mathrm{}\hfill \end{array}.$$
(14)
(For example, the $`1+1+1+2+3+6=14`$ generators of weight $`12`$ are given in Table 1.) Amazingly, this power series has appeared before (apparently as a curiosity) from the same iteration (Eq. 13), and it appears as Sloane’s sequence A045761 .

The classical formula of Witt, Eq. (3), can be extended to free Lie algebras with more general generating sets . For any set $`𝒜`$ with generating function $`a(t)=_{n>0}|\{A𝒜:order(A)=n\}|t^n`$, the dimensions $`c_n=dimL_n(𝒜)`$ of the homogeneous components of the graded Lie algebra $`L(𝒜)=_{n>0}L_n(𝒜)`$ are given by

$$c_n=\underset{d|n}{}\frac{1}{d}\mu (d)b_{n/d},$$
(15)
where

$$\mathrm{log}(1a(t))=\underset{n>0}{}b_nt^n.$$

In Maple, one can compute the dimensions easily by c=EULERi(INVERT(a)) (these functions are available in ), where a and c are the sequences of coefficients of $`a(t)`$ and $`c(t)`$, respectively.

We apply Eq. (15) to $`L_𝔓(A,B)𝒵L(A,𝔛)`$. The generating function for the grading by order of $`\{A\}𝔛`$ is $`t+x(t)`$. This gives the dimensions listed in Table 2 for $`1n40`$. A dramatic reduction in the dimensions compared to those of the free Lie algebra of rank 2 is evident.

More generally still, Kang and Kim  consider the grading of a free Lie algebra by an abelian semigroup $`S`$ which satisfies the finiteness condition that any $`sS`$ is a sum of other elements of $`S`$ in only finitely many ways. Then we have

$$dimL_s(𝒜)=\underset{d|s}{}\frac{1}{d}\mu (d)b_{s/d}$$
(16)
where

$$\mathrm{log}(1a(t))=\underset{sS}{}b_st^s$$

and $`d|s`$ means that there exists $`\tau S`$ such that $`d\tau =s`$, in which case we write $`s/d=\tau `$.

We can use this to calculate the dimensions of $`L_𝔓(A,B)`$ with respect to the bigrading by order and degree. We first simplify the grading by degree, Eq. (7), by introducing $`degree^{}(x):=degree(x)1`$. Then (as long as no elements of degree 0 enter, which now holds), the semigroup of the grading by degree is isomorphic to the nonnegative integers under addition. Including the grading by order gives $`S=^{>0}\times ^0`$. Note that the finiteness condition holds for $`S`$ since it holds for $`^{>0}`$. Since $`order(A)=2`$, $`degree^{}(A)=1`$, and $`degree^{}(X)=0`$ for all $`X𝔛`$, the generating function of $`\{A\}𝔛`$ is $`ut+x(t)`$ and we apply Eq. (16) with

$$b_{t,u}=[t^nu^m]\mathrm{log}(1utx(t)).$$

This gives the dimensions for $`n,m16`$ as shown in Table 3.

## 4 Asymptotics of the dimensions and calculation of the entropy.

From Eq. (15), the asymptotic growth of the dimensions $`c_n`$ is determined by the analytic structure—the location and type of the singularities—of $`\mathrm{log}(1a(t))`$. These correspond to zeros and singularities of $`1a(t)`$. In particular, if $`1a(t)`$ has a simple zero at $`t=\alpha `$ and no other zero with $`|t|\alpha `$, then

$$c_n\frac{1}{n}\left(\frac{1}{\alpha }\right)^n$$
(17)
and the Lie algebra has entropy $`1/\alpha `$.

The generating function of $`\{A\}𝔛`$ is $`t+x(t)`$. We therefore need to study the analytic structure of the function $`1(t+x(t))`$. We therefore study the map of Eq. (13) considered as a map

$$\phi :^2^2,(x,y)(x+y,y(x+y))$$

with initial conditions $`x=0`$, $`y=t^2`$. If the iterates of the map converge to $`(x^{},0)`$ say, then $`x(t)=x^{}`$. Curiously, the map preserves the area $`\frac{1}{y}dxdy`$, although this plays no role in the analysis.

The map $`\phi `$ has a line of degenerate fixed points $`(x,0)`$ with eigenvalues $`x`$ and 1. The fixed points with $`|x|>1`$ are unstable and one can show that the fixed points with $`|x|<1`$ are stable. The map ‘remembers’ its initial condition, and the function $`x(t)`$ is the $`x`$-coordinate of the fixed point reached from initial condition $`(0,t^2)`$.

We can see immediately that (i) for $`t`$ real and positive, $`x(t)`$ is strictly increasing; and (ii) if the map converges then $`|x(t)|1`$. For $`t`$ real and positive, the sequence $`\{y_k\}`$ is increasing, and if there is a $`k`$ such that $`y_k>1`$, then $`x_k\mathrm{}`$. Therefore we define

$$\beta =inf\{t^+:x_k(t)\mathrm{}\}.$$

Because

$$|x_{k+1}||x_k|+|z_k|,|z_{k+1}|=|z_k||x_{k+1}|,$$

the map converges in the disk $`\{t:|t|<\beta \}`$.

We can get a crude bound on $`\beta `$ immediately, but more detailed knowledge requires a numerical study of the map $`\phi `$. Let $`t`$ be real, let $`I(x,y)=y+x1+\sqrt{2y}`$, and suppose $`x>0`$, $`y>0`$, and $`I(x,y)<0`$. Then

| $`I\phi I`$ | $`=y(x+y)+x+y1+\sqrt{2y(x+y)}(y+x1+\sqrt{2y})`$ |
| --- | --- |
|  | $`=y(x+y)+\sqrt{2y}(\sqrt{x+y}1)`$ |
|  | $`y(1\sqrt{2y})+\sqrt{2y}\sqrt{1\sqrt{2y}}1)`$ |
|  | $`y(1\sqrt{2y})+\sqrt{2y}(1{\displaystyle \frac{1}{2}}\sqrt{2y})1)`$ |
|  | $`=\sqrt{2}y^{3/2}`$ |
|  | $`<0`$ |

Therefore, the orbit must stay in the bounded region $`x>0`$, $`y>0`$, $`I(x,y)<0`$, with $`x_k`$ increasing and $`y_k`$ decreasing. Therefore the orbit converges to some fixed point $`(x,0)`$. (Here the curve $`x=1\sqrt{2y}y`$ was chosen because it is a good approximation of the stable manifold of $`(1,0)`$.) Since $`I(0,t^2)<0`$ for $`0<t^2<2\sqrt{3}`$, we have $`\beta >\sqrt{2\sqrt{3}}>0.51`$. Better approximations of $`\beta `$ can be obtained as the roots of $`I\phi ^k(0,\beta ^2)=0`$ (i.e., by requiring the $`k`$th iterate to land in the trapping region), but these must be calculated numerically. On the other hand, $`x_2=t^2+t^4>1`$ if $`t>0.79`$, so we have the bounds $`0.51<\beta <0.79`$.

We have that $`dx(t)/dt>0`$ on $`[0,\beta )`$, with $`x(0)=0`$ and $`x(\beta )=1`$; and $`1t`$ is decreasing. Therefore $`1tx(t)`$ has exactly one zero in $`[0,\beta )`$, and it is simple. The zero is $`\alpha `$, the reciprocal of the required entropy of $`L_𝔓(A,B)`$. The numerical value of $`\alpha `$ can be determined by solving $`1tx(t)=0`$ numerically.<sup>1</sup><sup>1</sup>1In Matlab, by function x = f(t); x=0; y=t^2; while y\>1e-16, x=x+y; y=y\*x; end; x = 1-t-x; and alpha = fsolve(’f’,0.5). This gives the value of the entropy of $`L_𝔓(A,B)`$ as

$$1/\alpha =1.82542377420108\mathrm{}.$$
(18)
Are there any other solutions to $`1tx(t)=0`$? Because the coefficients of $`x(t)`$ are all nonnegative, there can be none in the disk $`|t|\alpha `$. To say more we have to proceed numerically. Firstly, if $`|x_k|`$ and $`|y_k|`$ get too large then the orbit blows up. Let

$$D=\{(x,y)^2:|y|>2|x|>2\}.$$

Suppose $`(x_k,y_k)D`$. Then

$$|x_{k+1}|||y_k||x_k||>|x_k|>1$$

and

$$|y_{k+1}|=|x_{k+1}||y_k|>2|x_{k+1}|,$$

i.e., we have $`(x_{k+1},y_{k+1})D`$. The orbit then stays in $`D`$ and cannot converge—in fact, it must blow up doubly exponentially. The first iterate $`(x_1,y_1)=(t^2,t^4)`$ is in $`D`$ if $`|t|>\sqrt{2}`$, and the second iterate $`(x_2,y_2)=(t^2+t^4,t^4(t^2+t^4))`$ is in $`D`$ if $`|t|>1.27202`$. In practice, if an iterate enters this region one can immediately stop the calculation and report that the map diverges.

Using this criterion we computed the function $`x(t)`$ numerically. See Figures 1 and 2.

We have made the following numerical observations:

1. The singularity of $`x(t)`$ closest to the origin is at

$$t=\beta =1/1.58207912734\mathrm{}.$$
(19)
2. There are no zeros of $`1tx(t)`$ in the disk $`|t|<\beta `$.
3. The map converges only in a connected, simply-connected region with a fractal boundary.
4. The function $`x(t)`$ is analytic everywhere inside this region but has a square root singularity everywhere on its boundary.
5. For each point $`z`$ on the boundary, $`x(t)1a(tz)^{1/2}`$ for some constant $`a`$ depending on $`z`$, as $`tz`$.
6. There is only one zero of $`1tx(t)`$ in $`|t|\beta `$.
7. The other zeros of $`1tx(t)`$ form two infinite sequences $`\alpha _n`$, $`\overline{\alpha }_n`$, with $`Re(\alpha _n)>\beta `$ for all $`n`$ and $`lim_n\mathrm{}\alpha _n=\beta `$.

Because of the fractal nature of the boundary, we are unlikely to be able to ‘solve’ the map $`\phi `$ or find $`\alpha `$ in closed form. Observation (4) would imply that this boundary forms a natural boundary for the function $`x(t)`$. Observation (5) would imply that the number of modified potentials of order $`n`$, $`[t^{n+1}]x(t)`$, is $`𝒪(n^{3/2}\beta ^n)`$. Observation (6) would imply that the next term in the asymptotic growth of $`c_n=dim(L_𝔓)_n(A,B)`$ comes from the square root singularity at $`t=\beta `$. Indeed, by computing $`c_n`$ numerically for $`n<80`$ we find that

$$c_nn^1\alpha ^n\{\begin{array}{cc}1.51n^{1/2}\beta ^n& n\text{ odd}\\ 1.61n^{3/2}\beta ^n& n\text{ even}\end{array}$$

and

$$[t^{n+1}]x(t)0.9628n^{3/2}\beta ^n$$

for $`n`$ even. These are all consistent with the observed singularity structure of $`1tx(t)`$.

## 5 Discussion

### 5.1 Physical interpretation of the generators

There is a particularly nice interpretation of $`L_𝔓(A,B)𝒵L(A,𝔛)`$ in the specific case of simple mechanical systems. In local coordinates, let $`A=T(p)=\frac{1}{2}p^TM(q)p`$ be the kinetic energy, where $`M(q)`$ is the inverse of the metric (or mass matrix), and and $`B=V(q)`$ be the potential energy. The set $`𝒵`$ consists of functions of $`q`$ only, and we think of them as ‘modified potentials’. Elements of the span of $`𝒵`$,

$$\underset{Z𝒵}{}a_Z\tau ^{degree(Z)}Z=a_1\tau V+a_2\tau ^3M(V^{},V^{})+\mathrm{},$$

and their flows, can be evaluated explicitly and used to construct high-order integrators of the full system $`T+V`$ (see Eq. (23) for more terms). Now consider the generator $`X=[Z,A]𝔛`$. It is the cotangent lift of the gradient flow of the modified potential $`Z`$; we have $`X=M(q)(Z(q),p)`$ and Hamilton’s equations are

| $`\dot{q}`$ | $`=M(q)Z^{}(q)=\mathrm{div}_{M^1(q)}Z=:f(q)`$ |
| --- | --- |
| $`\dot{p}`$ | $`=f^{}(q)^\mathrm{T}p.`$ |

So in a sense the modified potentials and the kinetic energy together contain a complete description of the Lie algebra.

### 5.2 Euclidean mechanical systems

Recall that on each manifold $`M`$, each simple mechanical system (say with kinetic energy $`T`$ and potential energy $`V`$) generates a Lie algebra of class $`𝔓`$. Therefore there is a homomorphism $`\psi (M,T,V)`$ from $`L_𝔓(A,B)`$ onto this Lie algebra. One can ask whether the system $`(M,T,V)`$ is in general position, i.e. if the two Lie algebras are actually isomorphic and $`\mathrm{ker}\psi (M,T,V)=0`$. This is unlikely, because of the existence of identities such as Eq. (6) in Lie algebras of vector fields. One can therefore consider larger classes of systems and ask whether they are in general position. That is, does the class satisfy any identities other than those corresponding to the grading by degree, Eq. (7)? We conjecture that for the class of all simple mechanical systems, it does not.

###### Conjecture 1

The only identities satisfied by all simple mechanical systems are those due to the grading by degree. That is,

$$\underset{M,T,V}{}\mathrm{ker}\psi (M,T,V)=0.$$

This is best discussed by introducing a smaller class which we shall see is not in general position. Namely, let $`M=^n`$ with the Euclidean metric. Then in coordinates the kinetic energy is $`T(p)=\frac{1}{2}_{i=1}^np_i^2`$. The first few modified potentials are then

| $`Z_1`$ | $`=V`$ |
| --- | --- |
| $`Z_2`$ | $`=[BBA]=V^{}(V^{})`$ |
| $`Z_3`$ | $`=[BBA,BA]=2V^{\prime \prime }(V^{},V^{})`$ |
| $`Z_4`$ | $`=[BBA,[BBA,A]]=4V^{\prime \prime }(V^{\prime \prime }(V^{}),V^{})`$ |
| $`Z_5`$ | $`=[[BBA,BA],BA]=2V^{\prime \prime \prime }(V^{},V^{},V^{})+4V^{\prime \prime }(V^{\prime \prime }(V^{}),V^{})`$ |

where we regard the $`k`$th derivative of $`V`$ as a real-valued symmetric linear function on $`k`$ vectors. Each modified potential of order $`2n1`$ is a linear combination of the scalar elementary differentials of order $`n`$ of $`V`$. Each such differential can be associated to a free tree with $`n`$ nodes. (See, for example,  for a discussion of elementary differentials and trees.) The number of such trees for $`n1`$ is (Sloane’s A000055, ) 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, …. This should be compared with the number of modified potentials in Eq. (14), namely 1, 1, 1, 2, 3, 6, 12, 24, 50, 107, 232, …. There are three interesting consequences:

* For $`n6`$, the sequences are the same. In fact, one can check that in the modified potentials of orders $`2n111`$, all trees appear, in invertible linear combinations, so these modified potentials are in general independent.
* For $`n=7,8,9`$, there are more modified potentials than free trees. In particular, only 11 of the 12 modified potentials of order 13 can be linearly independent. This proves that the class of Euclidean mechanical systems is not in general position.
* For $`n10`$, there are fewer modified potentials than free trees. In fact, the former have entropy $`1/\beta =1.582\mathrm{}`$ while the latter (since the free trees have entropy given by Otter’s constant, 2.955…) have entropy $`\sqrt{2.955\mathrm{}}=1.719\mathrm{}`$. Thus, for large $`n`$, only certain combinations of the trees appear in $`𝒵`$.

So far we have only considered the modified potentials $`𝒵`$ themselves. If these are independent, then $`𝔛=[𝒵,A]`$ is independent too. However, there is still a possibility for extra identities to hold in the Lie algebra generated by $`A`$ and $`𝔛`$. A term of order $`n`$ and degree $`m`$ is a sum of elementary differentials of $`V`$ and $`p`$, corresponding to trees with $`(n+m+1)/2`$ nodes, of which $`m`$ leaves are labelled $`p`$ and the remaining nodes are labelled $`V`$. In this case we find that for $`(n+m+1)/27`$ there are always sufficient labelled free trees to prevent forced dependencies among the Lie brackets. For example, of the 11 free trees with 7 nodes, there are 12, 20, 24, 18, 9, 3, and 1 trees in which $`m=0`$, 1, 2, 3, 4, 5, and 6 leaves are coloured $`p`$, respectively. The dimensions of the corresponding homogeneous subspaces of $`L_𝔓(A,B)`$ with $`(n+m+1)/2=7`$ are (from Table 3) 12, 18, 20, 14, 8, 3, and 1, respectively. Thus, only in the case $`m=0`$, corresponding to the modified potentials themselves, is a dependency forced in this way.

The algorithm for $`L_𝔓(A,B)`$, Eqs. (9) and (13), can be modified to take into account the dependencies amongst the Lie brackets in the Euclidean case. To get an upper bound on the dimensions and entropy of the Lie algebra in this case, we assume that the dependency appears only when forced. Let $`c_n`$ be the number of free trees with $`n`$ nodes. At iteration $`k`$, we already have $`z_{k,2n}:=[t^{2n}]\stackrel{~}{z}_k`$ elements of order $`2n1`$ in $`𝒵_k`$, and $`y_{k,2n}:=[t^{2n}]\stackrel{~}{y}_k`$ elements of order $`2n1`$ have just been created in $`𝒴_k`$. If $`z_{k,2n}+y_{k,2n}>c_n`$, we replace $`𝒴_k`$ by a smaller set, of $`c_nz_{k,2n}y_{k,2n}`$ elements, which together with the order $`2n1`$ elements of $`𝒵_k`$, forms a basis of the $`c_n`$ elementary differentials. In terms of the generating functions, we add the final step to the iteration of Eq. (13):

$$y_{k+1}\underset{n1}{}\mathrm{min}(y_{k+1,2n},c_nz_{k+1,2n})t^{2n}$$
(20)
Let the resulting limiting formal series be $`x_E(t)`$, $`y_E(t)`$, and $`z_E(t)`$. The generating function for $`x_E(t)`$ is then computed to be

| $`x_E(t)=`$ | $`t^2+t^4+t^6+2t^8+3t^{10}+6t^{12}+11t^{14}+23t^{16}+47t^{18}+102t^{20}+221t^{22}+`$ |
| --- | --- |
|  | $`484t^{24}+1069t^{26}+2386t^{28}+5364t^{30}+12143^{32}+27645t^{34}+63259t^{36}+\mathrm{}`$ |

(21)
which should be compared with Eq. (14). At order 14, 16, and 18 the dimensions are limited by the number of elementary differentials, but for $`n>9`$, $`[t^{2n}]x_E(t)<[t^{2n}]x(t)<c_n`$. Because the new map on generating functions, Eq. (20), is not analytic, it is harder to determine the location of its smallest singularity. We found the smallest root of successive polynomial truncations of $`1tx_E(t)`$ and extrapolated these results to obtain

$$1/\alpha _E=1.8250339\mathrm{},1/\beta _E=1.574\mathrm{}.$$
(22)
These are upper bounds for the entropy of the class of Euclidean mechanical systems and their modified potentials, respectively.

(Murua  has also considered this case, in the context of order conditions for Hamiltonians of the form $`\frac{1}{2}p_i^2+V(q)`$. He finds a unique independent tree of a certain type for each order condition, and enumerates these up to order 6. It would be interesting to compare the two approaches at higher order.)

The situation is quite different for non-Euclidean, i.e. general, mechanical systems. Repeating the above calculation for a general kinetic energy $`T(p)=\frac{1}{2}p^TM(q)p`$, we get the following modified potentials. The associated trees will be explained below.

| $`Z_1`$ | $`=V=\text{}`$ |
| --- | --- |
| $`Z_2`$ | $`=[BBA]=M(V^{},V^{})=\text{}`$ |
| $`Z_3`$ | $`=[BBA,BA]=2M(V^{},V^{\prime \prime }(M(V^{})))+M^{}(V^{},V^{},M(V^{}))=2\text{}+\text{}`$ |
| $`Z_4`$ | $`=[BBA,[BBA,A]]`$ |
|  | $`=4V^{}(M(V^{\prime \prime }(M(V^{\prime \prime }(M(V^{})))))+3V^{}(M(V^{\prime \prime }(M(M^{}(V^{},V^{})))))+`$ |
|  | $`M(M^{}(V^{},V^{}),M^{}(V^{},V^{}))`$ |
|  | $`=4\text{}+3\text{}+\text{}`$ |
| $`Z_5`$ | $`=[[BBA,BA],BA]`$ |
|  | $`=4V^{}(M(V^{\prime \prime }(M(V^{\prime \prime }(M(V^{}))))))+2V^{\prime \prime \prime }(M(V^{}),M(V^{}),M(V^{}))+`$ |
|  | $`6M^{}(V^{},M(V^{}),V^{\prime \prime }(M(V^{})))+M^{}(V^{},V^{},M(V^{\prime \prime }(M(V^{}))))+`$ |
|  | $`M^{}(V^{},M(V^{}),M^{}(V^{},V^{}))+M^{\prime \prime }(M(V^{}),M(V^{}),V^{},V^{})`$ |
|  | $`=4\text{}+2\text{}+6\text{}+\text{}+\text{}+\text{}`$ |

(23)
In this case each modified potential of order $`2n1`$ is a scalar elementary differential of $`V`$ and $`M`$. These correspond to bicoloured free trees with $`2n1`$ nodes, of which $`n`$ nodes are labelled $`V`$ (shown as solid circles above) and $`n1`$ nodes are labelled $`M`$ (shown as open circles above); the latter must have at least 2 branches since a derivative of $`M`$ has at least 2 indices. Of the 1, 1, 3, 11, 47, and 235 free trees of order 1, 3, 5, 7, 9, and 11 respectively, exactly 1, 1, 2, 8, 34, and 175 of them can be coloured (labelled) in this way. The calculation above shows that of these colourable trees, precisely one colouring of 1, 1, 2, and 7 of these colourable trees occur in the modified potentials of orders $`7`$. (The other colourings of these trees do not occur, because of the way in which the trees at each order are built from the trees of lower order. The colourable 7-node tree also does not occur.) It is clear that there is enormously much more freedom in this case than in the (‘Euclidean’, $`T(p)=\frac{1}{2}p_i^2`$) case considered previously. Therefore, we believe that all the modified potentials are independent in this case. This supports Conjecture 1.

### 5.3 Other polynomially graded Lie algebra

We close with a list of some other Lie algebras of class $`𝔓`$. In each case one can consider the case of two generators $`A`$ and $`B`$ of degrees 2 and 0 and the induced homomorphism from $`L_𝔓(A,B)`$.

1. The case of classical mechanics. The objects are real functions on a cotangent bundle, homogeneous polynomial in $`p`$. This can be specialized to the following cases.

1. $`Q`$ any Riemannian manifold, any potential energy, $`degree(X)`$ is the total degree of $`X`$ in $`p`$. Entropy is $`1.8254\mathrm{}`$, Eq. (18), with Conjecture 1 implying equality.
    2. $`Q=^n`$ with the Euclidean metric. Entropy is $`1.8250\mathrm{}`$, Eq. (22). It is remarkable that these two Lie algebras, not previously distinguished from each other in the literature, differ starting at order 13, and have slightly different entropy.
    3. $`Q=^n`$, functions polynomial in $`p`$ and $`q`$. We can then introduce a bigrading by degree in $`p`$ and by degree in $`q`$. To get a new Lie algebra, one of the generators has to be degree 0 in each grading, which forces $`Q`$ Euclidean, $`A=\frac{1}{2}p_i^2`$, $`B=V(q)`$ polynomial. For example, we have computed the dimensions of the Lie algebra generated by cubic potentials for small $`n`$ in Table 2—they are remarkably small. See  for an analysis of this case in terms of special types of trees.
2. Homogeneous polynomial vector fields on $`^m`$ graded by total degree in $`x_1,\mathrm{},x_k`$ for some $`1km`$. In the case $`k=m`$, the vector fields in $`𝔛`$ associated with $`L(A,B)`$ ($`degree(A)=2`$, $`degree(B)=0`$) are associated with free trees in which each node has degree at most 2 (since only the first two derivatives of $`A`$ are nonzero). Their numbers are 1, 1, 1, 2, 3, 6, 11, 23 (so far the same as for the free trees), then 46, 98, 207, 451, …. (Sloane’s A001190 ), which gives an upper bound for the number of independent elements of $`𝒵`$ of each odd order. These grow more slowly than the free trees, and even more slowly than $`𝒵`$, with entropy 1.5758, compared to 1.5821 (Eq. (19)) for $`𝒵`$. Perhaps in this case the trees $`𝔗`$ generate the Lie algebra as $`𝔗L(A,[𝔗,A])`$?
3. As the previous item, but multigrading by total degree in different subsets of the variables.
4. Homogeneous polynomial vector fields with the variables partitioned $`(x,y)`$ with $`x^k`$, $`y^m`$, and the vector fields of the form $`p\frac{}{x}+q\frac{}{y}`$ with either $`degree_y(q)degree_y(p)+1`$, or $`p0`$ and $`degree_y(q)=0`$. Simple mechanical systems form examples of this class. So do high-order ODEs of the form $`y^{(n)}=f(y,\mathrm{},y^{(n2)})`$ when re-written as first-order systems

| $`\dot{x}_i`$ | $`=x_{i+1},i=0,\mathrm{},n2,`$ |
| --- | --- |
| $`\dot{x}_{n1}`$ | $`=f(x_1,\mathrm{},x_{n2}),`$ |

with $`x_i=y^{(i)}`$, $`k=n1`$, and $`m=1`$.
5. Consider the Schrödinger equation

$$i\dot{\psi }=^2\psi +V(x)\psi ,$$

where $`^2`$ is the Euclidean Laplacian. The two operators $`^2`$ and $`V(x)`$ generate a Lie algebra of class $`𝔓`$, where the grading is by degree of the differential operators. For example,

$$[^2,V]\psi =(V\psi )+V\psi $$

is of degree 1,

$$[V,V,^2]\psi =((V^2))\psi $$

is of degree 0, and

$$[V,V,V,^2]\psi 0.$$

Acknowledgements. We would like to thank Mark Sofroniou and Reinout Quispel for pointing out the connection to free trees. RM would like to thank Ernst Hairer and Gerhard Wanner for their hospitality at the University of Geneva where this paper was written.