{'fraction_non_alphanumeric': 0.07410623084780388, 'fraction_numerical': 0.01108273748723187, 'mean_word_length': 3.4719652849149254, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 47, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Discrete Lagrangian and Hamiltonian Mechanics on Lie groupoids

The purpose of this paper is to describe geometrically discrete Lagrangian and Hamiltonian Mechanics on Lie groupoids. From a variational principle we derive the discrete Euler-Lagrange equations and we introduce a symplectic 2-section, which is preserved by the Lagrange evolution operator. In terms of the discrete Legendre transformations we define the Hamiltonian evolution operator which is a symplectic map with respect to the canonical symplectic 2-section on the prolongation of the dual of the Lie algebroid of the given groupoid. The equations we get include as particular cases the classical discrete Euler-Lagrange equations, the discrete Euler-Poincar\'e and discrete Lagrange-Poincar\'e equations. Our results can be important for the construction of geometric integrators for continuous Lagrangian systems.


Introduction
During the last decade, much effort has been devoted to construction of geometric integrators for Lagrangian systems using a discrete variational principle (see [21] and references therein). In particular, this effort has been concentrated for the case of discrete Lagrangian functions L on the cartesian product Q×Q of a differentiable manifold. This cartesian product plays the role of a "discretized version" of the standard velocity phase space T Q. Applying a natural discrete variational principle, one obtains a second order recursion operator ξ : Q × Q −→ Q × Q assigning to each input pair (x, y) the output pair (y, z). When the discrete Lagrangian is an approximation of a continuous Lagrangian function (more appropriately, when the discrete Lagrangian approximates the integral action for L) we obtain a numerical integrator which inherits some of the geometric properties of the continuous Lagrangian (symplecticity, momentum preservation). Although this type of geometric integrators have been mainly considered for conservative systems, the extension to geometric integrators for more involved situations is relatively easy, since, in some sense, many of the constructions mimic the corresponding ones for the continuous counterpart. In this sense, it has been recently shown how discrete variational mechanics can include forced or dissipative systems, holonomic constraints, explicitely time-dependent systems, frictional contact, nonholonomic constraints, multisymplectic fields theories... All these geometric integrators have demonstrated, in worked examples, an exceptionally good longtime behavior and obviously this research is of great interest for numerical and geometric considerations (see [8]).
On the other hand, Moser and Veselov [26] consider also discrete Lagrangian systems evolving on a Lie group. All this examples leads to A. Weinstein [31] to study discrete mechanics on Lie groupoids, which is a structure that includes as particular examples the case of cartesian products Q × Q as well as Lie groups.
A Lie groupoid G is a natural generalization of the concept of a Lie group, where now not all elements are composable. The product g 1 g 2 of two elements is only defined on the set of composable pairs G 2 = {(g, h) ∈ G × G | β(g) = α(h)} where α : G −→ M and β : G −→ M are the source and target maps over a base manifold M . This concept was introduced in differential geometry by Ch. Ereshmann in the 1950's. The infinitesimal version of a Lie groupoid G is the Lie algebroid AG −→ M , which is the restriction of the vertical bundle of α to the submanifold of the identities.
We may thought a Lie algebroid A over a manifold M , with projection τ : A → M , as a generalized version of the tangent bundle to M . The geometry and dynamics on Lie algebroids have been extensively studied during the past years. In particular, one of the authors of this paper (see [22]) developed a geometric formalism of mechanics on Lie algebroids similar to Klein's formalism [11] of the ordinary Lagrangian mechanics and more recently a description of the Hamiltonian dynamics on a Lie algebroid was given in [14,23] (see also [28]).
The key concept in this theory is the prolongation, P τ A, of the Lie algebroid over the fibred projection τ (for the Lagrangian formalism) and the prolongation, P τ * A, over the dual fibred projection τ * : A * −→ M (for the Hamiltonian formalism). See [14] for more details. Of course, when the Lie algebroid is A = T Q we obtain that P τ A = T (T Q) and P τ * A = T (T * Q), recovering the classical case. An alternative approach, using the linear Poisson structure on A * and the canonical isomorphism between T * A and T * A * was discussed in [7].
Taking as starting point the results by A. Weinstein [31], we elucidate in this paper the geometry of Lagrangian systems on Lie groupoids and its Hamiltonian counterpart. Weinstein gave a variational derivation of the discrete Euler-Lagrange equations for a Lagrangian L : G → R on a Lie groupoid G. We show that the appropriate space to develop a geometric formalism for these equations is the Lie algebroid P τ G ≡ V β ⊕ G V α → G (see section 3 for the definition of the Lie algebroid structure). Note that P τ G is the total space of the prolongation of the Lie groupoid G over the vector bundle projection τ : AG → M , and that the Lie algebroid of P τ G is just the prolongation P τ (AG) (the space were the continuous Lagrangian Mechanics is developed). Using the Lie algebroid structure of P τ G we may describe discrete Mechanics on the Lie groupoid G. In particular, -We give a variational derivation of the discrete Euler-Lagrange equations: for every section X of AG, where the right or left arrow denotes the induced right and left-invariant vector field on G. -We introduce two Poincaré-Cartan 1-sections Θ + L and Θ − L , and an unique Poincaré-Cartan 2-section, Ω L , on the Lie algebroid P τ G −→ G.
-We study the discrete Lagrangian evolution operator ξ : G −→ G and its preservation properties. In particular, we prove that (P τ ξ, ξ) * Ω L = Ω L , where P τ ξ is the natural prolongation of ξ to P τ G. -Reduction theory is stablished in terms of morphisms of Lie groupoids.
-The associated Hamiltonian formalism is developed using the discrete Legendre transformations F + L : G → A * G and F − L : G → A * G. -A complete characterization of the regularity of a Lagrangian on a Lie groupoid is given in terms of the symplecticity of Ω L or, alternatively, in terms of the regularity of the discrete Legendre transformations. In particular, Theorem 4.13 solves the question posed by Weinstein [31] about the regularity conditions for a discrete Lagrangian function on more general Lie groupoids than the cartesian product Q × Q. In the regular case, we define the Hamiltonian evolution operator and we prove that it defines a symplectic map. -We prove a Noether's theorem for discrete Mechanics on Lie groupoids. -Finally, some illustrative examples are shown, for instance, discrete Mechanics on the cartesian product Q×Q, on Lie groups (discrete Lie-Poisson equations), on action Lie groupoids (discrete Euler-Poincaré equations) and on gauge or Atiyah Lie groupoids (discrete Lagrange-Poincaré equations). We expect that the results of this paper could be relevant in the construction of new geometric integrators, in particular, for the numerical integration of dynamical systems with symmetry.
The paper is structured as follows. In Section 2 we review some basic results on Lie algebroids and Lie groupoids. Section 3 is devoted to study the Lie algebroid structure of the vector bundle P τ G ≡ V β ⊕ G V α → G. The main results of the paper appear in Section 4, where the geometric structure of discrete Mechanics on Lie groupoids is given. Finally, in Section 5, we study several examples of the theory.
In particular, if f : M −→ R is a real smooth function then df (X) = ρ(X)f, for X ∈ Γ(τ ). We may also define the Lie derivative with respect to a section X of A as the operator L X : Trivial examples of Lie algebroids are a real Lie algebra g of finite dimension (in this case, the base space is a single point) and the tangent bundle T M of a manifold M . Other examples of Lie algebroids are: i) the vertical bundle (τ P ) |V π : V π → P of a fibration π : P → M (and, in general, the tangent vectors to a foliation of finite dimension on a manifold P ); ii) the Atiyah algebroid associated with a principal G-bundle (see [14,17]); iii) the prolongation P π A of a Lie algebroid A over a fibration π : P → M (see [9,14]) and iv) the action Lie algebroid A ⋉ f over a map f : M ′ → M (see [9,14]). Now, let (A, [[·, ·]], ρ) (resp., (A ′ , [[·, ·]] ′ , ρ ′ )) be a Lie algebroid over a manifold M (resp., M ′ ) and suppose that Ψ : A → A ′ is a vector bundle morphism over the map Ψ 0 : M → M ′ . Then, the pair (Ψ, Ψ 0 ) is said to be a Lie algebroid morphism if and for all k, (2.5) where d (resp., d ′ ) is the differential of the Lie algebroid A (resp., A ′ ) (see [14]). In the particular case when M = M ′ and Ψ 0 = Id then (2.5) holds if and only if 2.2. Lie groupoids. In this Section, we will recall the definition of a Lie groupoid and some generalities about them are explained (for more details, see [3,17]). A groupoid over a set M is a set G together with the following structural maps: • A pair of maps α : G → M , the source, and β : G → M , the target. Thus, an element g ∈ G is thought as an arrow from x = α(g) to y = β(g) in M The maps α and β define the set of composable pairs • A multiplication m : G 2 → G, to be denoted simply by m(g, h) = gh, such that α(gh) = α(g) and β(gh) = β(h).
g −1 f f A groupoid G over a set M will be denoted simply by the symbol G ⇒ M . The groupoid G ⇒ M is said to be a Lie groupoid if G and M are manifolds and all the structural maps are differentiable with α and β differentiable submersions. If G ⇒ M is a Lie groupoid then m is a submersion, ǫ is an immersion and i is a diffeomorphism. Moreover, if x ∈ M , α −1 (x) (resp., β −1 (x)) will be said the α-fiber (resp., the β-fiber) of x.
Note that l −1 g = l g −1 and r −1 g = r g −1 . A vector fieldX on G is said to be left-invariant (resp., right-invariant) if it is tangent to the fibers of α (resp., β) andX(gh) = (T h l g )(X h ) (resp.,X(gh) = (T g r h )(X(g))), for (g, h) ∈ G 2 . Now, we will recall the definition of the Lie algebroid associated with G. We consider the vector bundle τ : AG → M , whose fiber at a point x ∈ M is A x G = V ǫ(x) α = Ker(T ǫ(x) α). It is easy to prove that there exists a bijection between the space Γ(τ ) and the set of left-invariant (resp., right-invariant) vector fields on G. If X is a section of τ : AG → M , the corresponding left-invariant (resp., right-invariant) vector field on G will be denoted ← − X (resp., (2.7) for g ∈ G. Using the above facts, we may introduce a Lie algebroid structure ([[·, ·]], ρ) on AG, which is defined by 10) (for more details, see [4,17]).
Given two Lie groupoids G ⇒ M and G ′ ⇒ M ′ , a morphism of Lie groupoids is a smooth map Φ : G → G ′ such that α, β and ǫ (resp., α ′ , β ′ and ǫ ′ ) being the source, the target and the identity section of G (resp., G ′ ).
Suppose that (Φ, Φ 0 ) is a morphism between the Lie groupoids G ⇒ M and G ′ ⇒ M ′ and that τ : AG → M (resp., τ ′ : (2.11) In fact, we have that the pair (A(Φ), Φ 0 ) is a morphism between the Lie algebroids τ : AG → M and τ ′ : AG ′ → M ′ (see [17]). Next, we will present some examples of Lie groupoids. 1.-Lie groups. Any Lie group G is a Lie groupoid over {e}, the identity element of G. The Lie algebroid associated with G is just the Lie algebra g of G.
2.-The pair or banal groupoid. Let M be a manifold. The product manifold M × M is a Lie groupoid over M in the following way: α is the projection onto the first factor and β is the projection onto the second factor; ǫ(x) = (x, x), for all x ∈ M , m((x, y), (y, z)) = (x, z), for (x, y), (y, z) ∈ M × M and i(x, y) = (y, x). M × M ⇒ M is called the pair or banal groupoid. If x is a point of M , it follows that . Thus, the linear maps 3.-The Lie groupoid associated with a fibration. Let π : P → M be a fibration, that is, π is a surjective submersion and denote by G π the subset of P × P given by G π = {(p, p ′ ) ∈ P × P/π(p) = π(p ′ )}. Then, G π is a Lie groupoid over P and the structural maps α π , β π , m π , ǫ π and i π are the restrictions to G π of the structural maps of the pair groupoid P × P ⇒ P .
If p is a point of P it follows that Thus, if (τ P ) |V π : V π → P is the vertical bundle to π then the linear maps induce an isomorphism (over the identity of M ) between the Lie algebroids (τ P ) |V π : V π → P and τ : AG π → P . 4.-Atiyah or gauge groupoids. Let p : Q → M be a principal G-bundle. Then, the free action, Φ : G × Q → Q, (g, q) → Φ(g, q) = gq, of G on Q induces, in a natural way, a free action Φ × Φ : G × (Q × Q) → Q × Q of G on Q × Q given by (Φ × Φ)(g, (q, q ′ )) = (gq, gq ′ ), for g ∈ G and (q, q ′ ) ∈ Q × Q. Moreover, one may consider the quotient manifold (Q × Q)/G and it admits a Lie groupoid structure over M with structural maps given bỹ This Lie groupoid is called the Atiyah (gauge) groupoid associated with the principal G-bundle p : Q → M (see [16]). If x is a point of M such that p(q) = x, with q ∈ Q, and p Q×Q : Q × Q → (Q × Q)/G is the canonical projection then it is clear that Thus, if τ Q |G : T Q/G → M is the Atiyah algebroid associated with the principal G-bundle p : G → M then the linear maps induce an isomorphism (over the identity of M ) between the Lie algebroids τ : 5.-The prolongation of a Lie groupoid over a fibration. Given a Lie groupoid G ⇒ M and a fibration π : P → M , we consider the set Then, P π G is a Lie groupoid over P with structural maps given by α π : P π G −→ P ; (p, g, p ′ ) −→ p, β π : P π G −→ P ; (p, g, p ′ ) −→ p ′ , ǫ π : P −→ P π G ; p −→ (p, ǫ(π(p)), p), m π : (P π G) 2 −→ P π G ; ((p, g, p ′ ), (p ′ , h, p ′′ )) −→ (p, gh, p ′′ ), i π : P π G −→ P π G ; (p, g, p ′ ) −→ (p ′ , g −1 , p).
P π G is called the prolongation of G over π : P → M . Now, denote by τ : AG → M the Lie algebroid of G, by A(P π G) the Lie algebroid of P π G and by P π (AG) the prolongation of τ : AG → M over the fibration π. If p ∈ P and m = π(p), then it follows that and, thus, one may consider the linear isomorphism In addition, one may prove that the maps (Ψ π ) p , p ∈ P , induce an isomorphism Ψ π : A(P π G) → P π (AG) between the Lie algebroids A(P π G) and P π (AG) (for more details, see [9]). 6.-Action Lie groupoids. Let G ⇒ M be a Lie groupoid and π : P → M be a smooth map. If P π × α G = {(p, g) ∈ P × G/π(p) = α(g)} then a right action of G on π is a smooth map P π × α G → P, (p, g) → pg, which satisfies the following relations π(pg) = β(g), for (p, g) ∈ P π × α G, (pg)h = p(gh), for (p, g) ∈ P π × α G and (g, h) ∈ G 2 , and pǫ(π(p)) = p, for p ∈ P.
On the other hand, note that P τ G ≡ V β ⊕ G V α is a real vector bundle over G. In this section, we will prove that the vector bundle π τ : P τ G → G admits an integrable Lie algebroid structure. In other words, we will prove that there exists a Lie groupoid H ⇒ G over G such that the Lie algebroid AH is isomorphic to the real vector bundle π τ : P τ G → G. In addition, we will see that the Lie groupoid H is isomorphic to the prolongations of G over α and β.
It is clear that the Lie algebroids of the Lie groupoids over G are just V β → G and V α → G, respectively. This fact suggests to consider the following manifold where β β : G β → G (respectively, α α : G α → G) is the target (respectively, the source) of the Lie groupoid G β ⇒ G (respectively, G α ⇒ G).
We will identify the space G β ⋆ G α with This space admits a Lie groupoid structure over G with structural maps given by are Lie groupoid morphisms and that the map is just the identity map. This implies that (G β , G α ) is a matched pair of Lie groupoids in the sense of Mackenzie [18] (see also [25]). Denote by ([[·, ·]], ρ) the Lie algebroid structure on τ : AG → M .
Proof. (i) If g ∈ G then, from (3.1), we deduce that the vector space V ǫ βα (g) α βα may be described as follows Now, we will define the linear map Ψ g : It is clear that Ψ g is a linear isomorphism and Therefore, the collection of the maps Ψ g , g ∈ G, induces a vector bundle isomor- (ii) A direct computation, using (3.1), proves that the linear map T ǫ βα (g) β βα : Consequently, from (2.8), (3.5) and (3.6), we deduce that (3.2) holds.
The above diagram shows the Lie groupoid and Lie algebroid structures of P τ G: Given a section X of AG −→ M , we define the sections X (1,0) , X (0,1) (the β and α-lifts) and X (1,1) (the complete lift) of X to π τ : P τ G −→ G as follows: We can easily see that and, as a consequence, Remark 3.2. From Theorem 3.1, we deduce that the canonical inclusions are Lie algebroid morphisms over the identity of G. In other words, (V β, V α) is a matched pair of Lie algebroids in the sense of Mokri [25]. This fact directly follows using the following general theorem (see [25]): if (G, H) is a matched pair of Lie groupoids then (AG, AH) is a matched pair of Lie algebroids. ⋄ Next, we will consider the prolongation P β G of the Lie groupoid G over the target β : G → M . We recall that and that P β G is a Lie groupoid over G with structural maps Moreover, we also have that the Lie algebroid of P β G may be identified with the prolongation P β (AG) of AG over β : G → M . We remark that is the corresponding Lie algebroid isomorphism then, under the identifications Proof. (i) A direct computation, using (3.1) and (3.9), proves the result.
Next, we will consider the prolongation P α G of the Lie groupoid G over the source α : G → M . We recall that and that P α G is a Lie groupoid over G with structural maps Moreover, we also have that the Lie algebroid of P α G may be identified with the prolongation P α (AG) of AG over α : G → M . We remark that is the corresponding Lie algebroid isomorphism then, under the canonical identifications Proof. Proceeding as in the proof of Theorem 3.3, we deduce the result.

Mechanics on Lie Groupoids
In this section, we introduce Lagrangian (Hamiltonian) Mechanics on an arbitrary Lie groupoid and we will also analyze its geometrical properties. This construction may be considered as a discrete version of the construction of the Lagrangian (Hamiltonian) Mechanics on Lie algebroids proposed in [22] (see also [14,23]). We first discuss discrete Euler-Lagrange equations following a similar approach to [31], using a variational procedure. Secondly, we intrinsically define and discuss the discrete Poincaré-Cartan sections, Legendre transformations, regularity of the Lagrangian and Noether's theorem. A discrete Lagrangian is a function L : G −→ R. Fixed g ∈ G, we define the set of admissible sequences with values in G: Given a tangent vector at (g 1 , . . . , g N ) to the manifold C N g , we may write it as the tangent vector at t = 0 of a curve in C N g , t ∈ (−ε, ε) ⊆ R −→ c(t) which passes through (g 1 , . . . , g N ) at t = 0. This type of curves is of the form , for all t, and h k (0) = ǫ(β(g k )) for k = 1, . . . , N − 1.
Therefore, we may identify the tangent space to C N g at (g 1 , . . . , g N ) with The curve c is called a variation of (g 1 , . . . , g N ) and (v 1 , v 2 , . . . , v N −1 ) is called an infinitesimal variation of (g 1 , . . . , g N ).
Define the discrete action sum associated to the discrete Lagrangian L : We now proceed, as in the continuous case, to derive the discrete equations of motion applying Hamilton's principle of critical action. For it, we consider variations of the discrete action sum.
Definition 4.1 (Discrete Hamilton's principle [31]). Given g ∈ G, an admissible sequence (g 1 , . . . , g N ) ∈ C N g is a solution of the Lagrangian system determined by Fist of all, in order to characterize the critical points, we need to calculate: where d • is the standard differential on G, i.e., d • is the differential of the Lie applying (2.6) and (2.7), we may rewrite this condition as where d is the differential of the Lie algebroid π τ : for every section X of AG. These equations will be called discrete Euler-Lagrange equations.
Thus, we may define the discrete Euler-Lagrange operator: where A * G is the dual of AG. This operator is given by In conclusion, we have characterized the solutions of the Lagrangian system determined by L : G −→ R as the sequences (g 1 , . . . , g N ), with (g k , g k+1 ) ∈ G 2 , for each k ∈ {1, . . . , N − 1}, and

4.2.
Discrete Poincaré-Cartan sections. Given a Lagrangian function L : G −→ R, we will study the geometrical properties of the discrete Euler-Lagrange equations.
Consider the Lie algebroid π τ : We also have that dL = Θ + L − Θ − L and so, using d 2 = 0, it follows that dΘ + L = dΘ − L . This means that there exists a unique 2-section Ω L = −dΘ + L = −dΘ − L , that will be called the Poincaré-Cartan 2-section. This 2-section will be important for studying symplecticity of the discrete Euler-Lagrange equations. and Proof. A direct computation proves the result.
Finally, we obtain some useful expressions of the Poincaré-Cartan 1-sections using the Lie algebroid isomorphisms introduced in Theorems 3.3 and 3.4.

4.2.1.
Poincaré-Cartan 1-sections: variational motivation. Now, we follow a variational procedure to construct the 1-sections Θ + L and Θ − L . We begin by calculating the extremals of SL for variations that do not fix the point g ∈ G. For it, we consider the manifold If c : (−ε, ε) → C N is a curve in C N and c(0) = (g 1 , . . . , g N ) then there exist N + 1 curves h k : (−ε, ε) → α −1 (β(g k )), for 0 ≤ k ≤ N, with h k (0) = ǫ(β(g k )) and for t ∈ (−ε, ε). Thus, the tangent space to C N at (g 1 , . . . , g N ) may be identified with the vector space Now, proceeding as in Section 4.1, we introduce the action sum Then, Therefore, if X 0 , . . . , X N are sections of τ : AG → M satisfying, X k (x k ) = v k , for all k, we have that Note that it is in the last two terms (that arise from the boundary variations) where appear the Poincaré-Cartan 1-sections.

4.3.
Discrete Lagrangian evolution operator. We say that a differentiable mapping ξ : G −→ G is a discrete flow or a discrete Lagrangian evolution operator for L if it verifies the following properties: -graph(ξ) ⊆ G 2 , that is, (g, ξ(g)) ∈ G 2 , ∀g ∈ G (ξ is a second order operator). -(g, ξ(g)) is a solution of the discrete Euler-Lagrange equations, for all g ∈ G, that is, (D DEL L)(g, ξ(g)) = 0, for all g ∈ G.
The second property follows from (i) by taking into account that dL = Θ + L − Θ − L . Finally, (iii) follows using (ii) and the fact that (P τ ξ, ξ) is a Lie algebroid morphism.
Remark 4.5. Now, we present a proof of the preservation of the Poincaré-Cartan 2section using variational arguments. Given a discrete Lagrangian evolution operator ξ : G −→ G for L, we may consider the function S ξ L : G → R given by (S ξ L)(g) = L(g) + L(ξ(g)), for g ∈ G.
If d is the differential on the Lie algebroid V β ⊕ G V α → G and X, Y are sections of τ : AG → M then, using (4.1), (4.9) and (4.12), we obtain that This implies that . Thus, we conclude that (P τ ξ, ξ) * Ω L = Ω L . ⋄ 4.5. Lie groupoid morphisms and reduction. Let (Φ, Φ 0 ) be a Lie groupoid morphism between the Lie groupoids G ⇒ M and G ′ ⇒ M ′ . The prolongation for every (V, W ) ∈ V g β ⊕ V g α. It is easy to see that (P τ Φ, Φ) is a morphism of Lie algebroids.
Theorem 4.6. Let (Φ, Φ 0 ) be a morphism of Lie groupoids from G ⇒ M to G ′ ⇒ M ′ . Let L and L ′ be discrete Lagrangian functions on G and G ′ , respectively, related by L = L ′ • Φ. Then: (i) for every (g, h) ∈ G 2 and every v ∈ A β(g) G we have that Proof. To prove the first we notice that, if (Φ, Φ 0 ) is a morphism of Lie groupoids, then we have that Φ where we have also used that For the proof of the second, we have that The proof of the third is similar to the second, and finally, for the proof of (iv) we just take the differential in (ii).
As an immediate consequence of the above theorem we have that The case when Φ is an inmersion may be useful to modelize holonomic mechanics on Lie groupoids, which is an imprescindible tool for explicitely construct geometric integrators (see [8,21]).
In a similar way, if V is an open subset of M such that β(g) ∈ V and {Y j } is a local basis of Γ(τ ) on V then Next, we consider the prolongation τ τ * : P τ * (AG) → A * G of the Lie algebroid τ : AG → M over the fibration τ * : A * G → M , that is, for v * ∈ A * G. Then, we may introduce the canonical section Θ of the vector bundle (τ τ * ) * : (P τ * AG) * → A * G as follows: for v * ∈ A * G and (v τ * (v * ) , X v * ) ∈ P τ * v * (AG). Θ is called the Liouville section. Moreover, we define the canonical symplectic section Ω associated with AG by Ω = −dΘ, where d is the differential on the Lie algebroid τ τ * : P τ * (AG) → A * G.
It is easy to prove that Ω is nondegenerate and closed, that is, it is a symplectic section of P τ * (AG) (see [14,23]). Now, let P τ F − L be the prolongation of F − L defined by where A(Φ α ) : P τ G ≡ V β ⊕ G V α → P α (AG) is the Lie algebroid isomorphism (over the identity of G) defined by (3.13) and (Id, T F − L) : P α (AG) → P τ * (AG) is the map given by for (v ǫ(α(h)) , X h ) ∈ P α h (AG). Since the pair ((Id, T F − L), F − L) is a morphism between the Lie algebroids P α (AG) → G and P τ * (AG) → A * G, we deduce that (P τ F − L, F − L) is also a morphism between the Lie algebroids P τ G ≡ V β ⊕ G V α → G and P τ * (AG) → A * G. The following diagram illustrates the above situation:

t t t t t t t M
We also have: Proposition 4.10. If Θ is the Liouville section of the vector bundle (P τ * (AG)) * → A * G and Ω = −dΘ is the canonical symplectic section of ∧ 2 (P τ * (AG)) * → A * G then Next, we will obtain necessary and sufficient conditions for a discrete Lagrangian on a Lie groupoid to be regular. a) The following conditions are equivalent: is a solution of the discrete Euler-Lagrange equations for L then there exist two open subsets U 0 and V 0 of G, with g 0 ∈ U 0 and h 0 ∈ V 0 , and there exists a (local) discrete Lagrangian evolution operator ξ L : U 0 → V 0 such that: Proof. a) First we will deduce the equivalence of the three conditions and Ω(F − L(h)) and Ω L (h) are nondegenerate. Therefore, we deduce that P τ h (F − L) is a linear isomorphism. This implies that Y h = 0. This proves that isomorphism. In the same way we deduce (i)⇒(iii) .
(ii)⇒(i) We will assume that F + L is a local diffeomorphism, so that On the other hand, if Ω is the canonical symplectic section of the vector bundle ∧ 2 (P τ * (AG)) * → A * G then, from Proposition 4.10, we deduce that (P τ g F + L) * (Ω(F + L(g))) = Ω L (g). Thus, since Ω(F + L(g)) is nondegenerate, we conclude that Ω L (g) is also nondegenerate, for all g ∈ G. Using the same arguments we deduce (iii)⇒(i) .
b) Using Remark 4.11, we have that Thus, from the first part of this theorem, it follows that there exit two open subsets U 0 and V 0 of G, with g 0 ∈ U 0 and h 0 ∈ V 0 , and an open subset W 0 of A * G such that µ 0 ∈ W 0 and F + L : are diffeomorphisms. Therefore, using Remark 4.11, we deduce that is a (local) discrete Lagrangian evolution operator. Moreover, it is clear that ξ L (g 0 ) = h 0 and, from the first part of this theorem, we have that ξ L is a diffeomorphism. Finally, if U ′ 0 is an open subset of G, with g 0 ∈ U ′ 0 , and ξ ′ L : U ′ 0 → G is another (local) discrete Lagrangian evolution operator then ξ ′ L|U0∩U ′ 0 : U 0 ∩ U ′ 0 → G is also a (local) discrete Lagrangian evolution operator. Consequently, using Remark 4.11, we conclude that Remark 4.14. Using Remark 4.3, we deduce that the Lagrangian L is regular if and only if for every g ∈ G and every local basis Let L : G → R be a regular discrete Lagrangian on G. If f : G → R is a real C ∞ -function on G then, using Theorem 4.13, it follows that there exists a unique ξ f ∈ Γ(π τ ) such that i ξ f Ω L = df, (4.21) d being the differential of the Lie algebroid π τ : P τ G ≡ V β ⊕ G V α → G. ξ f is called the Hamiltonian section associated to f with respect to Ω L . Now, one may introduce a bracket of real functions on G as follows: Note that, from (4.21) and Propositions 4.9 and 4.10, we obtain that is the prolongation of F ± L (see Section 4.6) and ξf is the Hamiltonian section associated to the real functionf on A * G with respect to the canonical symplectic section Ω on On the other hand, we consider the canonical linear Poisson bracket {·, ·} : [14]) (4.24) We have that (see [14]) Moreover, from (4.22), (4.23), (4.24) and Propositions 4.9 and 4.10, we deduce that Using the above facts, we may prove the following result.

4.9.
Noether's theorem. Recall that classical Noether's theorem states that a continuous symmetry of a Lagrangian leads to constants of the motion. In this section, we prove a discrete version of Noether's theorem, i.e., a theorem relating invariance of the discrete Lagrangian under some transformation with the existence of constants of the motion.
In this case, L is said to be quasi-invariant under X.
When dL(X (1,1) ) = − − → X L + ← − X L = 0, we will say that L is invariant under X or that X is an infinitesimal symmetry of the discrete Lagrangian L.
Remark 4.18. The infinitesimal invariance of the Lagrangian corresponds to a finite invariance property as follows. Let Φ s the flow of ← − X and γ(s) = Φ s (ǫ(x)) be its integral curve with γ(0) = ǫ(x), where x = β(g). Then, the integral curve of ← − X at g is s → r γ(s) g = gγ(s), and the integral curve of Using the above facts, we deduce that the integral curve µ of the vector field − − → X + ← − X on G satisfying µ(0) = g is µ(s) = γ(s) −1 gγ(s), for all s.
Thus, the invariance of the Lagrangian may be written as L γ(s) −1 gγ(s) = L(g), for all s.

⋄
If L : G → R is a regular discrete Lagrangian, by a constant of the motion we mean a function F invariant under the discrete Euler-Lagrange evolution operator ξ L , that is,  (X (1,1) ) − α * f is a constant of the motion for the discrete dynamics defined by L.
We substrate − → X (ξ L (g))(L) to both sides of the above expression, so that from where the result immediately follows using (4.9).
We also have Proof. Suppose that X and Y are Noether symmetries of L and that dL(X (1,1) with f, g ∈ C ∞ (M ). Then, using (2.9), (3.2) and (3.3), we have that On the other hand, from (2.6), (2.7), (4.28) and (4.29), we deduce that Thus, using (2.9) and (4.30), we obtain that Therefore, [[X, Y ]] is a Noether symmetry of L. We know that the Lie algebroid of G is isomorphic to the standard Lie algebroid τ M : T M → M and the map induces an isomorphism (over the identity of M ) between AG and T M . If X is a section of τ M : AG ≃ T M → M , that is, X is a vector field on M then − → X and ← − X are the vector fields on M × M given by for (x, y) ∈ M × M . On the other hand, if (x, y) ∈ M × M we have that the map induces an isomorphism (over the identity of M × M ) between the Lie algebroids π τM : In addition, if ξ : G = M × M → G = M × M is a discrete Lagrangian evolution operator then the prolongation of ξ is just the tangent map to ξ and, thus, we have that ξ * Ω L = Ω L , associated with L are the maps given by for (x, y) ∈ M × M . The Lagrangian L is regular if and only if the matrix ∂ 2 L ∂x∂y is regular. Finally, a Noether symmetry is a vector field X on M such that is a constant of the motion.
In conclusion, we recover all the geometrical formulation of the classical discrete Mechanics on the discrete state space M × M (see, for instance, [21]).

Lie groups.
We consider a Lie group G as a groupoid over one point M = {e}, the identity element of G. The structural maps are α(g) = e, β(g) = e, ǫ(e) = e, i(g) = g −1 , m(g, h) = gh, for g, h ∈ G.
The Lie algebroid associated with G is just the Lie algebra g = T e G of G. Given ξ ∈ g we have the left and right invariant vector fields: Thus, given a Lagrangian L : G −→ R its discrete Euler-Lagrange equations are: (T e l g k )(ξ)(L) − (T e r g k+1 )(ξ)(L) = 0, for all ξ ∈ g and g k , g k+1 ∈ G, or, (l * g k dL)(e) = (r * g k+1 dL)(e). Denote by µ k = (r * g k dL)(e) then the discrete Euler-Lagrange equations are written as where Ad : G × g −→ g is the adjoint action of G on g. These equations are known as the discrete Lie-Poisson equations (see [1,19,20]). Finally, an infinitesimal symmetry of L is an element ξ ∈ g such that (T e l g )(ξ)(L) = (T e r g )(ξ)(L), and then the associated constant of the motion is F (g) = (T e l g )(ξ)(L) = (T e r g )(ξ)(L). Observe that all the Noether's symmetries are infinitesimal symmetries of L.
If (x, h) ∈ G = M × H then the left-translation l (x,h) :α −1 π (xh) →α −1 π (x) and the right-translation r (x,h) :β −1 π (x) →β −1 π (xh) are given Note that if {η i } is a basis of h then {C ηi } is a global basis of Γ(pr 1 ). Next, suppose that L : G = M × H → R is a Lagrangian function and for every h ∈ H (resp., x ∈ M ) we will denote by L h (resp., L x ) the real function on M (resp., on H) given by L h (y) = L(y, h) (resp., L x (h ′ ) = L(x, h ′ )). Then, a composable pair As in the case of Lie groups, denote by µ k (x, h k ) = d(L x • r h k )(e). Then, the discrete Euler-Lagrange equations for L are written as In the particular case when M is the orbit of a ∈ V under a representation of G on a real vector space V , the resultant equations were obtained by Bobenko and Suris, see [1,2], and they were called the discrete Euler-Poincaré equations.
Finally, an element ξ ∈ h is an infinitesimal symmetry of L if where f : M −→ R is a real C ∞ -function on M . The associated constant of the motion is The heavy top. As a concrete example of a system on a transformation Lie groupoid we consider a discretization of the heavy top. In the continuous theory [22], the configuration manifold is the transformation Lie algebroid τ : where Ω ∈ R 3 ≃ so (3) is the angular velocity, Γ is the direction opposite to the gravity and e is a unit vector in the direction from the fixed point to the center of mass, all them expressed in a frame fixed to the body. The constants m, g and l are respectively the mass of the body, the strength of the gravitational acceleration and the distance from the fixed point to the center of mass. The matrix I is the inertia tensor of the body. In order to discretize this Lagrangian it is better to express it in terms of the matricesΩ ∈ so(3) such thatΩv = Ω × v. Then where I I = 1 2 Tr(I)I 3 −I. We can define a discrete Lagrangian L : G = S 2 ×SO(3) → R for the heavy top by which is obtained by the ruleΩ = R TṘ ≈ 1 The value of the action on an admissible variation is where Γ k+1 = W T Γ k (since the above pairs must be composable) and K ∈ so(3) is arbitrary. Taking the derivative at t = 0 and after some straightforward manipulations we get the DEL equations Remark 5.1. The above equations are to be solved as follows. From Γ k , W k we obtain Γ k+1 = W k Γ k and Π k fromΠ k = W k I I − I IW T k . The DEL equation gives Π k+1 in terms of the above data. Finally we get W k+1 as the solution of the equationΠ k+1 = W k+1 I I − I IW T k+1 , as in [26]. ⋄ In the continuous theory, the section X(Γ) = (Γ, Γ) of S 2 × so(3) → S 2 is a symmetry of the Lagrangian (see [22]). We will show next that such a section is also a symmetry of the discrete Lagrangian. Indeed, it is easy to see that the left and right vector fields associated to X coincide − → X = ← − X and are both equal to − → X (Γ, W ) = (Γ, 0), (W,ΓW )) ∈ T G = T S 2 × T SO(3).

5.5.
Reduction of discrete Lagrangian systems. Next, we will present some examples of Lie groupoid epimorphisms which allow to do reduction.
• Let G be a Lie group and consider the pair groupoid G × G over G. Consider also G as a groupoid over one point. Then we have that the map is a Lie groupoid morphism, which is obviously a submersion. Thus, using Corollary 4.7, it follows that the discrete Euler-Lagrange equations for a left invariant discrete Lagrangian on G × G reduce to the discrete Lie-Poisson equations on G for the reduced Lagrangian. This case appears in [26] as was first noticed by [31], and also appear later in [1,2,19,20].
Alternatively, one can do reduction of a right-invariant Lagrangian by using the morphism Φ r : G × G −→ G (g, h) → gh −1 • Let G be a Lie group acting on a manifold M by the left. We consider a discrete Lagrangian on G × G which depends on the variables of M as parameters L m (g, h).
In general, the Lagrangian will not be invariant under the action of G, that is L m (g, h) = L m (rg, rh). Nevertheless, it can happen that L m (rg, rh) = L r −1 m (g, h).
In such cases we can consider the Lie groupoid G × G × M over G × M where accordingly one consider the elements in M as parameters. Then the Lagrangian can be considered as a function on the groupoid G × G × M given by L(g, h, m) ≡ L m (g, h) so that the above property reads L(rg, rh, rm) = L(g, h, m). Thus we define the reduction map where on G × M we consider the transformation Lie groupoid defined by the right action m · g = g −1 m. Since this map is a submersion, the Euler-Lagrange equations on G × G × M reduces to the Euler-Lagrange equations on G × M . This case occurs in the Lagrange top that was considered as an example in Section 5.3 (see also [2]).
• Another interesting case is that of a G-invariant Lagrangian L defined on the pair groupoid L : Q × Q −→ R, where p : Q −→ M is a G-principal bundle. In this case we can reduce to the Atiyah gauge groupoid by means of the map Thus the discrete Euler-Lagrange equations reduce to the so called discrete Lagrange-Poincaré equations.

Conclusions and outlook
In this paper we have elucidated the geometrical framework for discrete Mechanics on Lie groupoids. Using as a main tool the natural Lie algebroid structure on the vector bundle π τ : P τ G → G we have found intrinsic expressions for the discrete Euler-Lagrange equations. We introduce the Poincaré-Cartan sections, the discrete Legendre transformations and the discrete evolution operator in the Lagrangian and in the Hamiltonian formalism. The notion of regularity has been completely characterized and we prove the symplecticity of the discrete evolution operators. Moreover, we have studied the symmetries of discrete Lagrangians on Lie groupoids relating them with constants of the motion via Noether's Theorems. The applicablity of these developments has been stated in several interesting examples, in particular for the case of discrete Lagrange-Poincaré equations. In fact, the general theory of discrete symmetry reduction naturally follows from our results.
In this paper we have confined ourselves to the geometrical aspects of mechanics on Lie groupoids. In a forthcoming paper (see [10]) we will study the construction of geometric integrators for mechanical systems on Lie algebroids. We will introduce the exact discrete Lagrangian and we will discuss different discretizations of a continuous Lagrangian and its numerical implementation.
Another different aspect we will work on it in the future is to develop natural extensions of the above theories for forced systems and systems with holonomic and nonholonomic constraints.