Sweedler’s duals and Schützenberger’s calculus

Gérard H. E. Duchamp et Christophe Tollu.^{∗}

Abstract

We describe the problem of Sweedler’s duals for bialgebras as essentially be the characterize the domain of the transpose of the multiplication. This domain is the set of what could be called “representative linear forms” which are the elements of the algebraic dual which are also representative on the multiplicative semigroup of the algebra. When the algebra is free, this notion is indeed equivalent to that of rational functions of automata theory. For the sake of applications, the range of coefficients has been considerably broadened i.e. extended to semirings, so that the results could be specialized to boolean and multiplicity cases. This requires some caution (use of “positive formulas” i.e. iteration replacing dimension and - Schein - rank replacing dimension). For the theory and its applications has been created a rational calculus which can, in return, be applied to harness Sweedler’s duals. A new theorem of rational closure and application to Hopf algebras of use in Physics and Combinatorics is provided. ^{0}

Representative functions on a semigroup

The aim of this paragraph is to discuss the dualization of bi-algebras and Hopf algebras. This problem, solved by Sweedler’s duals, is the following. Let (B, ., Δ, 1_{B}, ε) be a k-bialgebra ; we know that, if B is finite-dimensional (resp. graded in finite dimensions), the dual (resp. graded dual) endowed with the transpose elements is a bialgebra and that, in case B is a Hopf algebra this statement carries over. Now the question can be asked. What is the good notion of retricted dual for the general (i.e. ungraded finite or infinite dimensional case) ? Analysing the dualization of the elements (., Δ, 1_{B}, ε) of B, one sees at once that only the dualization of the multiplication is problematic as, in the general case, the codomain of the transpose of . is larger than B^{∗} ⊗ B^{∗}. The first result follows (and somehow extends) [1]. To state it, we need the notions of shifts of functions on a semigroup. Let k be a field, (S, .) a semigroup and f ∈ k^{S}. For each s ∈ S define f_{s} : x → f(sx) (right shift of f) and _{s}f : x → f(xs) (left shift of f), sf_{t} : x → f(txs) (bi-shift of f). Then, we have.

∗Institut Galilée, LIPN (CNRS UMR 7030), 99 Av. J.-B. Clement, F-93430 Villetaneuse, France.

0Version du 03.05.07 compilée le 28-05-2007 17:31

Proposition 1.1 (see also [1] paragraph 2.2) Let k be a field, (S, .) a semigroup and f ∈ k^{S}. The following are equivalent :

i) The family (f_{s})_{s∈S} is of finite rank in k^{S} ii) The family (_{s}f)_{s∈S} is of finite rank in k^{S} iii) The family (_{s}f_{t})_{s,t∈S} is of finite rank in k^{S} iv) There exists a double (finite) family (g_{i}, h_{i})_{1≤i≤n} of functions such that

(∀x, y ∈ S)(f(xy) = ∑_{i=1}^{n} g_{i}(x)h_{i}(y))  (1)

iv) There exists λ ∈ k^{1×n}, γ ∈ k^{n×1} and μ : (S, .) ↦ (k^{n×n}, ×) a morphim of semigroups such that (∀s ∈ S)(f(s) = λμ(s)γ). Moreover, if S admits a neutral (i.e. is a monoid), μ of (iv) above can be chosen to be the unity matrix.

Proof — cf Annex A. The elements of k^{S} which fulfill the above conditions will be called representative functions on S and denoted R(k, S, .).

Remark 1.2 vérifier i) When k is only a division algebra, theorem above still holds with the four equivalent conditions shifts end the (left, right) and ranks computed on the (left, right). ii) If S is finite, R(k, S, .) = k^{S} and if S is a group, one has

R(k, S, .) = k^{S} ⟺ S is finite

iii) If S is a semigroup, the above is false in general as shown by the following counterexample. Let G be a finite group and endow S = ℕ×G with the law (n, g)∗(m, h) = (0, gh). It can be easily checked that (S, ∗) is a semigroup and that R(k, S, .) = k^{S}. iv) When W is a shift-invariant space and f ∈ W ∩R(k, S, .), the families (f_{s})_{s∈S}, (_{s}f)_{s∈S}, (_{s}f_{t})_{s,t∈S} are of course in W ∩ R(k, S, .) (and are of finite rank). Two useful examples of such relative representative functional spaces are with W = C(S) (continuous functions) and W = S^{∗} (linear forms, S is an algebra).

v) If T ⊂ S is a subsemigroup with finite set-theoretical complement (S\T is finite) then f ∈ k^{S} is representative iff f|_{T} is so.

Semirings

Throughout the text “monoid” stands for “semigroup with unit”. Semirings are the structures adapted to matrix (with unity) computation. A semiring (k, +, ×) consists of the following data

- a set k

- two binary laws +, × on k

such that - (k, +) and (k, ×) are monoids, the first being commutative, their neutrals will be

denoted respectively 0_{k} and 1_{k}

- × is left and right distributive over +

- 0_{k} is an annihilator i. e. (∀x ∈ k)(0_{k}.x = x.0_{k} = 0_{k})

Example 2.3 i) Any ring. ii) The boolean semiring 𝔹 = {0, 1} endowed with the laws x ⊕ y = x + y − xy and x ⊗ y = xy. iii) The semiring ([−∞, +∞[, max, +), called in the literature “(max,plus)-semiring”. iv) In the semiring ([0, +∞[, +, ×), the laws are continuous at infinity and then can be completed. We obtain a semiring ([0, +∞], +, ×) which is suited for multiplicities arising in repeated additions of positive values during iterations.

Example 2.4 The following example is fundamental and will be used in the definition of CM-modules. Let (M, +) be a commutative monoid, then (End(M), +, ∘) (defined as for the case when M is a group) is a semiring. The units being respectively, as in the group case, the constant mapping M ↦ {0_{M}} for + and Id_{M} for ∘.

The structure of semiring defines a category larger than that of rings, the morphisms being defined similarly. Let (k_{i}, +_{i}, ×_{i}), i = 1, 2 be two semirings, a mapping ϕ : k_{1} ↦ k_{2} is called a morphism of semirings iff it is a morphim for the two structures of monoids (additive and multiplicative), then compatible with the laws and units of k_{1} and k_{2}. The definition of modules (here called CM-modules as they are constructed on Commutative Monoids as vector structure) follows also the classical pattern. The structure of a (left) k-CM-module is given by the following data

- a commutative monoid (M, +)

- a morphism (the scaling morphism) of semirings s : k ↦ End(M).

The structure of (right) k-CM-module is defined by replacing End(M) by End^{op}(M) the opposite semiring (constructed with the opposite multiplicative law). Bi- and multimodules are defined as in [3] and follow the general philosophy of “structures with operators”.

Example 2.5 Let S be a set, then k^{S}, the set of all functions X ↦ k is naturally endowed with a tructure of k − k bimodule defined as in the case when k is a ring. So is k^{(S)}, the set of finitely supported functions of k^{S}.

The free monoid generated by a set X (finite of infinite) is the set of words (i.e. finite sequences of elements of X comprising the empty one denoted by 1_{X^{∗}}) endowed with the concatenation law.

Shift operators and rational closure

Let (M, .) be a (commutative or not) monoid. For a function f : M ↦ k and a ∈ M, we define the following shift operators ([Reu, Eil, Abe])

- f_{a} : x → f(ax) (right shift)
- _{a}f : x → f(xa) (left shift)

We also have to describe the analog, for CM-algebras, of full subalgebras and full subalgebras closures (see [4] Ch. 1.1.4) and this requires the notion of summability [2].

Definition 2.6 A family {f_{i}}_{i∈I} of functions M ↦ k is called summable iff, for each m ∈ M, {f_{i}}_{i∈I} is finitely supported. Then, the mapping m ↦ ∑_{i∈I} f_{(}m) is denoted ∑_{i∈I} f_{i} and called the sum of {f_{i}}_{i∈I}.

As a consequence, it is easily checked that, if M is locally finite ([13] Vol. A VII.4) and f : M ↦ k is without constant term (i.e. f(1_{m}) = 0_{k}), then the family {f^{n}}_{n∈ℕ} (convolutional powers) is summable and its sum

∑_{n∈ℕ}f^{n}  (2)

will be denoted f^{∗} and called the star of f.

Note 2.7 There is a lot of literature about the star problem (see [18, 19]). For a general discussion of star-type solutions in a semiring, see [11].

Now, we are in the position of stating the Kleene-Schützenberger theorem.

Theorem 2.8 Let M = X^{∗} be a free monoid, k a semiring and f ∈ k^{M}. The following are equivalent

i) the family (f_{w})_{w∈M} belongs to a finitely generated shift-invariant left-submodule ii) the family (_{w}f)_{w∈M} belongs to a finitely generated shift-invariant right-submodule iii) there exists a row λ ∈ k^{1×n} a column γ ∈ k^{n×1} and a representation (of monoids) μ : M ↦ (k^{n×n}, ×) such that (∀w ∈ M)(f(w) = λμ(w)γ). iv) if X is finite, f lies in the rational closure of X (i.e. the smallest subalgebra of k << X >> closed by the star operation and containing X).

Remark 2.9 i) One can remove the hypothesis of freeness of M if k is a field. Indeed, in this case, the submodule can be taken as generated by the shifts (right or left) of f and the representation is automatically compatible with the relations of M. ii) Here the star is used as the localization at one (i.e. with positive formulas) of the inverse function. Indeed, with coefficients in a ring, if we are at the neighbourhood of 1, the condition (1 − x)(1 + y) = 1 is equivalent to y = x + xy (and y = x + yx). These self-reproducing positive conditions are taken as the definition of “y is a star of x” in a semiring (see [11]). iii) The condition (iv) is known under the name of Kleene-Schützenberger theorem as, when k is specialized to 𝔹 this is actually Kleene’s theorem. In this sense, this theorem links is at the frontier of harmonic analysis (the set of representative functions is dense in the Fourier space of compact groups), spectral theory (the notion of full subalgebra closure comes from this theory) and theoretical computer science (the notion of star was developped as a computational model of iteration and the notion of a semiring was developped to cope with general scalars as various as the ones arising in stochastic automata theory and the shortest path problem).

In the general case (X finite or not), Kleene-Schützenberger’s theorem has to be modified as follows.

Theorem 2.10 Let M = X^{∗} be a free monoid, k a semiring and f ∈ k^{M}. The following are equivalent

i) the family (f_{w})_{w∈M} belongs to a finitely generated shift-invariant left-submodule ii) the family (_{w}f)_{w∈M} belongs to a finitely generated shift-invariant right-submodule iii) it exists a row λ ∈ k^{1×n} a column γ ∈ k^{n×1} and a representation (of monoids) μ : M ↦ (k^{n×n}, ×) such that (∀w ∈ M)(f(w) = λμ(w)γ). iv) the function f lies in the rational closure of \overline{kX} = \{∑_{x∈X} α(x)x\}_{α∈k^{X}} (i.e. the smallest subalgebra of k << X >> closed by the star operation which contains \overline{kX}).

Remark 2.11 The rational closure of X is, in fact, the intersection of the set of elements characterized by (i-iii) i.e. Sweedlers dual of k⟨X⟩ and the algebra ⋃_{{F ⊂X \atop F finite}} k⟨⟨F ⟩⟩ of the series whose support involves a finite alphabet.

3 Rational expressions

The construction of [6] was localized at zero, we extend it here to any localisation i.e. for any mapping Λ : X ↦ k. As the rational closure involves a unitary law (the star) partially defined, the definition of universal formulas for this closure needs some caution. Indeed, we need to build in parallel a “character” (the constant term) const so that all proper expressions should have a star. One first defines, as in [6] the completely free expressions (or formulas) as the terms of the universal algebra defined on X ∪ {0_{E}} (0_{E}, which does not belong to X will serve as a null or void expression and be mapped to the zero series). This algebra will be denoted E^{cf}(X, k). More precisely

- If x ∈ X ∪ {0_{E}} then x ∈ E^{cf}(X, k).
- If E, E_{i} ∈ E^{cf}(X, k), i = 1, 2 and λ ∈ k then

\begin{matrix}E1 + E2 ∈ E^{cf}(X, k), E1 · E2 ∈ E^{cf}(X, k) \\ λE ∈ E^{cf}(X, k), Eλ ∈ E^{cf}(X, k). \end{matrix}

- If E ∈ E^{cf}(X, k) then E^{∗} ∈ E^{cf}(X, k).

The partial function const : E^{cf}(X, k) ↦ k (constant term) is constructed as follows from the values const(x) = Λ(x).

1. If x ∈ X const(x) = Λ(x) and const(0_{E}) = 0_{k}.

2. If E, E_{i} ∈ E^{cf}(X, k), i = 1, 2 and λ ∈ k then

\begin{matrix}const(E1 + E2) = const(E1) + const(E2), const(E1 · E2) = const(E1) · const(E2) \\ const(λE) = λconst(E), const(Eλ) = const(E)λ. \end{matrix}

3. If const(E) = 0_{k} then const(E^{∗}) = 1_{k}.

The domain of const will be called rational expressions and denoted E_{Λ}(X, k). For example 0_{k}^{∗} ∈ E_{Λ}(X, k). Let now Θ : X ↦ k⟨⟨A⟩⟩ be a mapping such that,

(∀x ∈ X)(Θ(x)[1_{A^{∗}}] = Λ(x))

Following recursively (1-2-3) above, we can construct a polymorphism ϕ_{Θ} : E_{Λ}(X, k) ↦ k⟨⟨A⟩⟩ which is a morphism for the laws (2 internal and 2 external) and the star. Moreover δ_{1_{A^{∗}}} ∘ ϕ_{Θ} = const (i.e. const can be considered as a “constant term function” for the expressions). The image of ϕ_{Θ} is exactly the rational closure of the set {Θ(x)}_{x∈X}.

4 Dual laws

Let Δ : A ↦ A × A be any comultiplication (i.e. A is a k-coalgebra). It is known that its dual (A^{∗},^{t} Δ) is an algebra and if A is coassociative (resp. cocomutative, counital), A is associative (resp. comutative, unital) [1]. We would likre here to enlarge the framework of [12]. If A is a algebra, let us call dual law on A^{∗} a law of the form ^{t}Δ for some (not necessarily coassociative) comultiplication on A. In [12] were considered the dual laws on k⟨⟨X⟩⟩ ≃ k⟨X⟩^{∗} in order to prove that the Hadamard and Infiltration products, which were known to preserve rationality, were essentially the only (along with an interpolation between the two) alphabetic (associative and unital) dual laws between series. As we will see, the notion of dual law provides an implementation scheme for the automata so that the rationality preservation is naturally effective.

Theorem 4.1 Let A be a k-algebra and Δ : A ↦ A ⊗ A be a comultiplication which is a morphism of algebras. Then

i) If k is a field, Sweedler’s dual A^{∘} of A is closed under the dual law ^{t}Δ. ii) If k is a semiring and A = k⟨X⟩, k⟨⟨X⟩⟩^{∘} is closed under the dual law ^{t}Δ.

Note 4.2 Tout vérifier i) The theorem is no longer true if Δ : A ↦ A ⊗ A is arbitrary (i.e. not necessarily a morphism) as shows the following counterexample. With Δ : ℚ[x] ↦ ℚ[x] ⊗ ℚ[x] such that Δ(x) = \frac{x^{n}}{n!} ⊗ \frac{x^{n}}{n!} , one has

tΔ(\frac{1}{1 − x}, \frac{1}{1 − x}) = exp(x).

ii) In (i) above, the restriction on scalars (to be a field) can be extended to inductive limits of PIDs. iii) Other coproducts than morphisms can preserve rationality. For example, let Δ : k⟨X⟩ ↦ k⟨X⟩ ⊗ k⟨X⟩ be a morphism and Δ_{1} : k⟨X⟩ ↦ k⟨X⟩ ⊗ k⟨X⟩ be a linear mapping which coincides with Δ except for a finite number of words of X^{⋆}. It can be checked that Δ_{1}, although not a morphism, preserves rationality.

5 Bialgebras

Let us now return to the case of a bialgebra (B, ., Δ, 1_{B}, ε). The above proposition says that, if a linear form on B is transformed by ^{t}m (m : B ⊗B ↦ B is just the multiplication mapping) into an element of B^{∗} ⊗ B^{∗}, it must be of the (iv) form. It is, as we will see in the next paragraph, exactly the automaton linear representation. For the moment, let us state this in a precise form.

Proposition 5.1 Let (B, m, Δ, 1_{B}, ε) be a bialgebra and f ∈ B^{∗}.

1) The following are equivalent

i) ^{t}m(f) ∈ B^{∗} ⊗ B^{∗} (for the canonical embedding B^{∗} ⊗ B^{∗} ↪ (B ⊗ B)^{∗}) ii) f ∈ R(k, B, .) iii) ker(f) contains a finite-codimension one-sided ideal iv) ker(f) contains a finite-codimension two-sided ideal

v) There exists λ ∈ k^{1×n}, γ ∈ k^{n×1} and μ : (B, +, .) ↦ (k^{n×n}, +, ×) a morphim of k-algebras (associative with units) such that (∀x ∈ B)(f(x) = λμ(x)γ).

2) Moreover, let B^{0} be the set of linear forms as above, then (B^{0},^{t} Δ,^{t} m,^{t} ε,^{t} 1_{B}) is a bialgebra and if B admits an antipode σ (i.e. is a Hopf algebra), one has ^{t}σ(B^{0}) ⊂ B^{0} and (B^{0},^{t} Δ,^{t} m,^{t} ε,^{t} 1_{B},^{t} σ) is a Hopf algebra.

6 Concluding remarks References

[1] E. Abe Hopf algebras. Cambridge (1980), reprint ??

[2] J. Berstel, C. Reutenauer Rational series and their languages EATCS Monographs on Theoretical Computer Science. Springer (1988).

[3] Bourbaki N., Algebra, chapter III, Springer

[4] Bourbaki N., Théories spectrales, Hermann

[5] A. Cayley, On certain results related to quaternions. Phil. Mag. 26, 141-145 (1845).

[6] Champarnaud J.-M., Duchamp G. Derivatives of rational expressions and related theorems, T.C.S. 313 31 (2004).

[7] V. Chari, A. Pressley, A guide to quantum groups. Cambridge (1994).

[8] P.M. Cohn, Free rings and their relations. Acad. Press (1985).

[9] A. Connes, Noncommutative geometry. Acad. Press (1994).

[10] G. Cauchon, Séries de Malcev-Neumann sur le groupe libre et questions de rationalité, TCS, 98, pp79-97 (1992).

[11] Gérard Duchamp, Hatem Hadj Kacem, Eric Laugerotte, Algebraic elimination of ϵ-transitions, DMTCS, Volume 7, (2005), pp. 51-70

[12] Duchamp G., Flouret M., Laugerotte É., Luque J-G., Direct and dual laws for automata with multiplicities T.C.S. 267, 105-120 (2001).

[13] S. Eilenberg, Automata, languages and machines, (Acad. Press, New-York, 1974).

[14] M. Fliess, Sur le plongement de l’algèbre des séries rationnelles non commutatives dans un corps gauche. CRAS Ser. A 271 pp 926-927 (1970).

[15] M. Fliess, Matrices de Hankel, Jour. of Pure and Appl. Math. 53, 197-222, (1994).

[16] I.M. Gelfand, V.S. Retakh, A theory of non-commutative determinants and characteristic functions of graphs, Funct. Anal. Appl. 26 (1992).

[17] I,M. Gelfand, D. Krob, A. Lascoux, B. Leclerc B, V.S. Retakh and J.- Y.Thibon, Noncommutative symmetric functions, Adv. in Math. 112, 218–348 (1995).

[18] Golan J. S., Power Algebras over Semirings: With Applications in Mathematics and Computer science. Kluwer Academic Publishers (1999).

[19] Golan J. S., Semirings and Affine Equations over Them: Theory and Applications. Kluwer Academic Publishers (2003).

[20] A. Heyting, Die Theorie der linearen Gleichungen in einer Zahlenspezies mit nichtkommutativer Multiplikation, Math. Ann., 98, 465-490 (1927).

[21] G. Jacob, Représentations et substitutions matricielles dans la théorie matricielle des semigroupes. Thèse, Univ. de Paris (1975).

[22] J. Lewin, Fields of fractions for group algebras of free groups, Trans. Amer. Math. Soc. 192, 339-346, (1974).

[23] D.S. Passman, The algebraic structure of group rings, John Wiley - Interscience (1977).

[24] A.R. Richardson Simultaneous linear equations over a division ring. Proc. Lond. Math. Soc., 28, 395-420 (1928).

[25] M.P. Schützenberger, On the definition of a family of automata, 4, Information and Control, 275-270, (1961).

[26] M.P. Schützenberger, On a theorem of R. Jungen, Proc. Amer. Math. Soc. 13, 885-889, (1962).