Hélène Pasco

Leslie Carlyle

Marco Faustini

Helen Glanville

Clément Sanchez

Philippe Walter

Laurence De Viguerie

Affiliations

Investigating historical 19th century gel Mediums: from historical recipes to model systems

Gelled mediums were widely used during the 19 th century, added to paint on the palette to modify its rheological, optical and drying properties. Many variations of gelled mediums exist in the literature, all with the common basis of mastic resin or varnish, drying oil and a lead compound. With the aim of unveiling the chemistry of such systems, reconstructions were carried out not only following the historical recipes, but in addition, exploring variations and simplifications to get a better understanding of the key ingredients and interactions inducing gelation. Different parameters were tested to establish whether these have an impact on the gelation mechanisms: the influence of the nature and proportions of the ingredients and the preparation process. These reconstructions and their FTIR characterisation reveal the formation of metal-resin soaps, but also underline the specific role of lead in the gelation.

Introduction

The use of gelled mediums was recommended during the 19th century in Britain as additions to modify oil paint properties (Carlyle, 2001a and b). When prepared with oil and varnish some mediums formed a gel-like material. Megilp is one of such gelled mediums, made from lead-treated oil and mastic resin varnish. As Carlyle (2001a) points out, although these mediums had become popular with 19th century British artists, one can assume that such recipes were known earlier as all the ingredients would have been present in artists' studios.

One first-hand account of their use was in a 1767 notebook belonging to Sir Joshua Reynolds where he states that he "varnished with Gum Mast. dissolved in Oil with Sal Saturni" 1 [START_REF] Cormack | [END_REF], cited in Morrison, 2010). This is supported by Joseph Farington, a British painter who describes the use of "macguilp", "magylph" and "majellup" by himself and his teacher, Richard Wilson, during the 1760s [START_REF] Carlyle | No short mechanic road to fame: The implications of certain artists' materials for the durability of British painting 1770-1840[END_REF].

Chemical analyses of 19th century paintings [START_REF] Townsend | Painting Techniques and Materials of Turner and Other British Artists 1775-1875[END_REF][START_REF] Odlyha | Investigation of the binding media of paintings by thermoanalytical and spectroscopic techniques[END_REF][START_REF] Transcriber ; Morrison | Mastic and Megilp in Reynolds's" Lord Heathfield of Gibraltar": A Challenge for Conservation[END_REF] have confirmed the use of such systems by the identification of mastic resin mixed with the oil binder. Townsend et al. published an early investigation of reconstructions of gelled mediums; beginning with a survey of published recipes and descriptions of their properties, reconstructions were then prepared with linseed oil treated with lead oxide or lead acetate driers combined with mastic varnish in various proportions [START_REF] Townsend | Nineteenthcentury paint media: The formulation and properties of megilps[END_REF]. The reconstructed gel mediums alone, and mixed into oil paint were then characterised to better identify them in paintings using SEM 2 , FTIR 3 , TGA 4 , and DTMS 5 .

With the aim of revisiting the chemistry of such systems, reconstructions were carried out not only following the historical recipes, but in addition, exploring variations and simplifications to get a better understanding of the key ingredients inducing gelation [START_REF] Pasco | When 19th century painters prepared organic-inorganic hybrid gels: physico-chemical study of «gumtions[END_REF]. Different parameters were tested to establish whether these have an impact on the gelation process. For instance, one question was whether all the components (oil, triterpenic or polymeric fractions of the resin, and the lead compound) are needed to form the gel, and what is the nature of the impact of their relative proportions and of the addition process.

I. Experimental a) Materials

Three different "cold drawn" linseed oils were used, purchased from different suppliers (Laverdure, Kremer Pigmente and Schminke). Two different mastic resins were also employed (Laverdure 2015, and Kremer Pigmente 2016), both originally harvested in the island of Chios. To make the varnish, rectified spirit of turpentine from Sennelier was used.

The sugar of lead mentioned in the historical recipes refers to lead acetate [START_REF] Carlyle | Paint driers discussed in 19th-century British oil painting manuals[END_REF].

Lead acetate trihydrate Pb(CH 3 COO) 2 •3H 2 O (s) (PbOAc (s) ) (Sigma Aldrich, 99%) was chosen as the closest approximation. It has to be noted that this compound is modified quickly when exposed to air, and partially converts into lead subacetate [START_REF] Bryant | Carbon-13 CP/MAS NMR and crystallographic investigations of the structure and solid-state transformations of lead (II) acetate trihydrate[END_REF].

1 Sugar of lead, or lead acetate: the alchemical name of lead being Saturn 2 SEM: Scanning Electron Microscopy 3 FTIR: Fourier-Transform InfraRed spectroscopy 4 TGA: ThermoGravimetric Analysis 5 DTMS: Direct Temperature Resolved Mass Spectrometry To investigate the influence of the nature of the resin, colophony, sandarac and dammar resins were purchased from Laverdure. Different metallic compounds, from Sigma Aldrich, were also investigated: lead chloride (PbCl 2 ) lead nitrate (Pb(NO 3 ) 2 ), minium (lead tetroxide Pb 3 O 4 ), hydrocerussite (2PbCO 3 Pb(OH) 2 ), litharge (lead oxide PbO), and calcium, copper, manganese and zinc acetates (respectively Ca(

CH 3 COO) 2 •H 2 O, Cu 2 (CH 3 COO) 4 •H 2 O, Mn(CH 3 COO) 2 •4H 2 O, Zn(CH 3 COO) 2 •2H 2 O).
Oleanolic acid ( 97%) and lupeol were also purchased from Sigma Aldrich.

b) Experimental protocol

Detailed protocols were adapted from historical recipes to ensure consistent reproducibility of the reconstructions which could otherwise have been highly variable in terms of the viscosity and texture obtained [START_REF] Pasco | When 19th century painters prepared organic-inorganic hybrid gels: physico-chemical study of «gumtions[END_REF].

Ibbetson's recipe

A variation of the Megilps (made with lead treated oil and mastic resin dissolved in turpentine to form a varnish), was Gumtion which consisted of powdered mastic resin and powdered lead acetate ground together in linseed oil (Ibbetson (1828), cited in [START_REF] Carlyle | The Artist's Assistant: Oil Painting Instruction Manuals and Handbooks in Britain 1800-1900, with reference to selected eighteenth-century sources[END_REF] p.394).

Mastic resin was first ground in a mortar: 1 g of mastic resin for 1 min. Then lead acetate trihydrate (0.8 g), hereinafter referred to as PbOAc (s) , was added and the mixture ground again for 1 min. While continuously grinding, linseed oil was then poured in 0.5 mL at a time to a total of 2 g. The mixture was then placed on a slab and ground with a muller over 30 min.

Variations were then prepared with a simplified faster protocol: grinding on a slab with a muller was replaced by grinding the mixture in a mortar (from 1 to 10 min). The different concentrations of PbOAc (s) range from 9 wt% to 57 wt% (adding from 0.3 to 4 g). Each preparation was then stored in a sealed glass jar.

Model systems

Mastic varnish preparation

A varnish containing 33 wt % of mastic resin and 67 wt % of turpentine was prepared. The resin (15 g) was ground in a mortar and placed in a beaker into which 30 g of turpentine was poured. The mixture was heated to 70°C, and mixed for 15 minutes with a magnetic stirrer. It was then allowed to rest and filtered through laboratory grade filter paper so as to eliminate potential impurities.

Preparation of the mastic varnish + lead acetate mixture:

PbOAc (s) and mastic varnish were ground together with the following protocol: PbOAc (s) was first placed in a mortar (between 0.01 and 3 g) and mastic varnish was slowly added (2 g) while continuously grinding for 1 min. The different concentrations of PbOAc (s) ranged between 2.4 and 60 wt %. The preparations were then each stored in a sealed glass jar.

Removal of the polymeric fraction of the resin

The protocol followed is described in [START_REF] Dietemann | Towards more stable natural resin varnishes for paintings: The aging of triterpenoid resins and varnishes[END_REF]: first 5 g of mastic resin was ground and placed in a beaker. 15 mL of dichloromethane was added and the mixture stirred until complete dissolution of the resin. 40 mL of methanol was added and a white substance was observed. This polymeric fraction was removed by filtration. After evaporation of the solvents, the remaining fraction was re-dissolved in turpentine.

Preparation of a triterpenoid gel

Two commercial triterpenoids, oleanolic acid (> 97%) and lupeol (Figure 1) were chosen to investigate whether they could form a gel with the following protocol: 50 mg of triterpenoid is added to 1 g of turpentine in a beaker and magnetically stirred. Then the mixture is placed in a mortar and 45 mg of PbOAc (s) is added and ground for 1 min. The preparation was then stored in a sealed glass jar.

c) FTIR spectroscopy

Multi-reflexion ATR/FT-IR spectra were recorded at room temperature with a Cary 630 Agilent spectrometer. For each measurement, three spectra of the same film were recorded -to assess the reproducibility -as an accumulation of 32 scans, with a spectral resolution of 4 cm -1 .

III. Results and discussion a) Reconstructions of historical recipes

Many variations of gelled medium exist in the literature [START_REF] Carlyle | The Artist's Assistant: Oil Painting Instruction Manuals and Handbooks in Britain 1800-1900, with reference to selected eighteenth-century sources[END_REF]), all with the common basis of mastic resin or varnish, oil and a lead compound. The oil can be any type of drying oil (e.g. linseed or walnut oil) composed of saturated and unsaturated triglycerides in different proportions. Lead can be introduced as powder of litharge (PbO) during the heating of oil, or as powder or saturated solution of lead acetate in the so-called light Megilp/Gumtion gels (Table 1). Mastic resin can be added dissolved in turpentine as a varnish, or as a finely ground powder. We focus here on the light Megilp / Gumtion formulations. The invention of Gumtion is attributed to the artist, painting restorer and author Julius Caesar Ibbetson at the beginning of the 19th century [START_REF] Carlyle | The Artist's Assistant: Oil Painting Instruction Manuals and Handbooks in Britain 1800-1900, with reference to selected eighteenth-century sources[END_REF] p.106-107). Ibbetson recipe, 1828 p.16 (cited in Carlyle, 2001b, p. 394-5) "Take half an ounce of gum mastic, and carefully pick and scrape off every particle of sand or other matter which adheres to it. Add to it a little more than one-third sugar of lead, in quantity not weight, as the sugar of lead is much heavier than the gum mastic. Grind them together in raw linseed oil. In a short time it will become quite stiff; then add more oil, to make it so thin that it will spread and run on the slab. Take it up in a pot, and grind it again very fine, putting only a small quantity on the slab at once; after which, if it should seem too stiff for use, put a little more oil, and grind it again slightly. A good deal depends on practice, in preparing Gumtion, as well as other paints; but they cannot be ground too fine."

Historical recipes quoted in [START_REF] Carlyle | The Artist's Assistant: Oil Painting Instruction Manuals and Handbooks in Britain 1800-1900, with reference to selected eighteenth-century sources[END_REF] The first step of this study consisted of an exploration of Ibbetson's recipe, which is important for understanding the experimental constraints of the preparation of the Gumtion and to experience (as the painter would have done) the physical consistency of the material during its preparation, essential to the painter's final choice. Mastic varnish was first ground in a mortar with lead acetate, then oil was added and ground thoroughly on a slab with a muller over 30

min. An opaque creamy mixture is indeed obtained as specified (Figure 2a). To get a better understanding of the mechanism of gelation, the influence of each ingredient on the formation of the gel i.e., oil, lead and mastic resin/varnish was investigated. To do so, and for all the experiments presented below, a simplified protocol was adopted: ingredients were ground in a mortar (see Experimental section), then placed in a closed vial and the gelation time was identified as the moment when the material no longer flows when the vial is turned upside down (Figure 3).

Mixtures of oil with a lead compound, without resin, do not form gels (although they can be very thick/ viscous formulations); this means that resin is necessary to form a gel. However even without adding the oil, the mixture of resin and lead forms a gel (Figure 2b), as already discussed in Viguerie et al., 2017. Oil is not a pre-requisite for the gelation process, but, as it reacts with lead, it certainly also plays a role in the gelation process and the final structure of the gel. Moreover the addition of oil allows the adjustment of the flow properties of Gumtion and subsequently favours its proper mixing with the paint.

Various metallic compounds were experimented with to see whether their nature has an influence on gel formation: different lead compounds (PbCl 2 , Pb(NO 3 ) 2 , Pb 3 O 4 , 2PbCO 3 Pb(OH) 2 and PbO) and different acetate compounds (Ca(

CH 3 COO) 2 •H 2 O, Cu 2 (CH 3 COO) 4 •H 2 O, Mn(CH 3 COO) 2 •4H 2 O, Zn(CH 3 COO) 2 •2H 2 O).
Of these only three allowed the formation of a gel: PbO, Pb 3 O 4 and 2PbCO 3 Pb(OH) 2 (in addition to the lead acetate called for in the recipes). With these compounds, a homogeneous gel was obtained within few minutes (Figure 3), while the other preparations exhibited two phases and months later still remained in a liquid state (Figure 4). Indeed, the strong ionic character of the bond of the other lead compounds (chloride and nitrate) may limit their dispersion in the organic materials (oil or turpentine and mastic resin). It appears that the acetate function facilitates the reaction between the metal and the triterpenoids. However, the presence of lead seems to be necessary to the formation of an homogeneous gel, as the other acetate compounds without lead do not enable gelation to occur: in the case of Cu 2 (CH 3 COO) 4 H 2 O, Mn(CH 3 COO) 2 4H 2 O, and Zn(CH 3 COO) 2 2H 2 O, two phases were obtained and analysed via ATR-FTIR. Different resins were then investigated, first dissolved in turpentine and then added to linseed oil and lead acetate trihydrate. Colophony and sandarac (diterpenic resins) as well as dammar resin (triterpenic as mastic resin) were used. Only the mixture containing colophony formed a gel, in contrast to the ones containing dammar and sandarac.

c) Influence of the formulation: proportions and process

The amount of PbOAc (s) was also varied in two formulations (Ibbetson's original recipe, and the mixture between mastic varnish and PbOAc (s) ) to see whether there is a minimum quantity needed to form the gel. In the system without oil, a proportion of PbOAc (s) of around 2.5 wt% was required to form a gel. In contrast, in the original recipe which includes oil, a higher proportion of the lead compound was necessary (at least 6 wt%).

a) b) c)

It is interesting also to see that the amount of PbOAc (s) has an influence on the gelation time:

as one might expect the more PbOAc (s) was added, the shorter the gelation time. Table 2 presents the results obtained for mixtures without oil. Systems with oil exhibit much longer gelation time (when ground in a mortar according to the same protocol as the systems without oil); as a comparison, a system containing 20 wt% of PbOAc became a gel in 6 h and a system containing 40 wt% of PbOAc became a gel in 1 h (vs 5 min. for a system without oil).

The preparation processes

Although not always mentioned explicitly, in some historical recipes the importance of the grinding process is highlighted; for example Ibbetson states that the ingredients "cannot be ground too fine" (Ibbetson 1828 p.16, see above). The "grinding" step is of great importance in the process: we observed that no gelation is obtained if lead acetate is only mixed with the varnish. To investigate the influence of the grinding process on gelation, tests were carried out with mastic varnish and 20 wt% of PbOAc (s) , with grinding times between 1 and 10 min in a mortar. The gelation time is about 12, 6 and 5 min, when the grinding time is 1, 5 and 10 min respectively (Figure 5), confirming that the grinding time plays an important role in the gelation kinetics: grinding lead acetate to a fine powder increases its surface to bulk ratio probably leading to the enhancement of its reactivity. However, lead acetate has to be ground in the system as air exposure alters its reactivity as we observed grinding lead acetate prior to mixing it with the mastic varnish: 5 min grinding first in air leads to gel formation in about 25 min, vs. 5 min to form a gel when the lead acetate is ground directly into the varnish.

Exposing the ground lead acetate powder to air for a few hours before mixing it with varnish extends the gelation time even further (reaching more than 1 h after a 16 h exposure to the air, Figure 5).

Figure 5: Effect of the grinding process on the gelation time of a system made of PbOAc (s) and mastic varnish (PbOAc 20 wt%). Each experiment has been repeated 3 times. GBMV: Grinding Before Mixing in the Varnish.

The systems with oil showed the same behaviour, that it is possible to decrease the gelation time by increasing the grinding time. Moreover if the grinding is achieved with a muller, on a slab, and not in a mortar, a gel is obtained much faster and the mixture can be butter-like just after preparation. Most of all, grinding on the slab results in a system that is perfectly homogeneous whereas particles of mastic or lead acetate, which would be very reactive in the system, remain visible when grinding in a mortar only. When mixed with oil paint the presence of these particles in the medium could raise issues of long-term conservation.

d) Model systems to understand the gelation process

Polymeric part

To investigate which part of the mastic resin is involved in the gelation process, the polymeric fraction of the resin was removed, following the protocol described in [START_REF] Dietemann | Towards more stable natural resin varnishes for paintings: The aging of triterpenoid resins and varnishes[END_REF].

After removing the poly--myrcene from the mastic resin, a "triterpenoids varnish" was prepared adding turpentine, and ground with PbOAc (s) : a thick white gel was obtained very quickly, less than 1 min. It shows that the gelation depends on the interaction between the triterpenoids and the PbOAc (s) . As in the case of the oil, the polymeric part of the resin does not seem necessary to form the gel, but might have an impact on the gel texture.

Nature of the triterpenoid

Subsequently, two commercial triterpenoids known to be present (or at least structurally close) in mastic resin -oleanolic acid and lupeol -were used to investigate whether they also can form a gel (Figure 1). In the case of oleanolic acid, thick, opaque and white gels are obtained within a few minutes to 2 h, depending on the amount of lead compound present. In contrast, and despite the similarity of its structure to oleanolic acid, when lupeol is used as the commercial triterpenoid, no gelation is observed. One important difference between these two compounds lies in the presence of a carboxylic acid group, which may thus play a role in the gelation process: this observation suggests that the gel forms thanks to the interaction between the carboxylic acid functional group of the triterpenoids and the lead compound.

e) FTIR study

All formulations were analysed via FTIR spectroscopy. To shed new light on the gelation mechanism and confirm the previous assumption, we can focus first on the simplified formulations with mastic and PbOAc (s) (figure 6a and individual components in Figure S1):

the FTIR spectrum of the mixture "mastic resin + turpentine + PbOAc" shows the presence of two bands at 1576 and 1514 cm -1 in the range of carboxylates (asymmetric band). They can be inferred to the interaction between lead and the acidic part of the resin with subsequent lead-resin soap formation. The formation of lead-resin soaps has also been shown by [START_REF] Poli | Aging of Natural Resins in Presence of Pigments: Metal Soap and Oxalate Formation[END_REF] in paint mixtures containing resin and a metal-based pigment. A shoulder visible around 1410 cm -1 may be then assigned to the carboxylate symmetric band. To confirm that the band at ca. 1520 cm -1 is not due to remaining PbOAc (s) , we reproduced the experiment analysing the same mixture but with PbO (instead of PbOAc (s) ) which does not present any feature in this range. The FTIR spectrum of the gel obtained (figure 6b) clearly confirms the presence of a band in the range of carboxylates that cannot be inferred to any individual component. One can also see the presence of the mastic resin carbonyl stretching band (ca.

1710 cm -1 ), since the resin contains a lot of carboxylic acid and ketone groups; this band does not undergo noticeable change when the lead compound is added, suggesting that only a few carbonyl moieties interact with the lead. A small shoulder of the large carbonyl massif is also present at ca. 1750 cm -1 that can be assigned to the new chemical environment in the mixture.

FTIR spectra of the model system composed of oleanolic acid and a lead compound are presented in Supplementary Information. Similar observations can be made with the formation of new carboxylate species in the system confirming the reaction between triterpenoids of the resin bearing acidic functions and the lead compound. These spectra are detailed in [START_REF] Pasco | Shedding Light on Functional Hybrid Nanocomposites 19th Century Paint Medium[END_REF] with details on the possible structure of the lead-oleanolic acid complex. FTIR spectra of the preparations based on the historical recipes, with oil, mastic and lead acetate, also show this carboxylate band around 1520 cm -1 . This is difficult to interpret without the results from the simplified formulations (as noted in [START_REF] Townsend | Nineteenthcentury paint media: The formulation and properties of megilps[END_REF]Viguerie et al. 2017). It is interesting that the band is much more intense when the materials were ground together with a muller: the difference in the preparation process not only modified the texture and homogeneity of the system but also its chemical composition (and thus probably the structure and stability of the gel). As this band is quite large, it is not possible to state whether it has to be inferred only to the interaction of lead with resin or also with oil (lead soaps commonly found around 1530 cm -1 ). A possible contribution of lead soaps or even mixed lead oil-resin soaps cannot be discounted and requires further investigation. This opens-up a wide area of research in order to better understand the reactivity of such systems, possible interactions within a painting, and competition between resin-and oil-soap formation.

FTIR spectra of the mixtures of different resins and lead oxide (PbO) also provide unexpected information (Figure 6c). Formulations containing colophony also present a band in the range of carboxylates, very intense compared to the one obtained with mastic. It should be noted that the carbonyl band completely disappears in that case which would indicate that all the resin is involved in the carboxylate formation. More surprisingly, formulations containing dammar exhibit a broad band in the "soap" region, although a gel is not formed when this resin is employed in the preparation of gelled mediums. Sandarac resin seems less reactive as no band appears when it is used with PbO.

We also investigated the two phases which were obtained after grinding Cu, Mn and Zn acetates with mastic varnish. One example is given, with the mixture of mastic varnish (mastic + turpentine) and CuOAc, in Figure 6d: the lower "jelly" phase was compared to the upper liquid phase. Here again carboxylate bands are clearly visible in the "jelly" phase, due to the combination of the acid present in mastic resin and the metal acetates. In this case, although the soap band is high, the carbonyl seems almost unaffected. Despite the carboxylate features present in the jelly phase, it is interesting to note that these acetate compounds with Cu, Mn and Zn did not form homogenous gels. This investigation also indicates, that similar to the case with dammar-lead mixtures, the formation of soaps alone is not enough to form a gel; the gelation process requires the specific properties of lead [START_REF] Pasco | Shedding Light on Functional Hybrid Nanocomposites 19th Century Paint Medium[END_REF].

Conclusion

In summary, different variations of traditional recipes, based on oil, mastic resin and a lead compound, have been found to form a gel. Mixtures without oil do form a homogeneous gel, as well as systems prepared with colophony instead of mastic resin. Of all the metallic compounds investigated, only Pb compounds allow the formation of homogeneous gels, i.e., lead acetate, litharge (lead oxide), minium and lead white. Other acetates (based on copper, manganese or zinc) induce the formation of two phases, as well as the use of dammar or sandarac resins. According to these reconstructions and to their FTIR characterisation, the gelation process is based on the interaction of the acidic part of the terpenoids of the with the lead compound, forming lead-resin soap species. These carboxylate species are also found in unstable systems (presenting two phases) showing that their formation is necessary but not sufficient to ensure complete gelation.

While lead (-oil) soaps are widely described in the literature and studied by numerous groups with possible associated degradation defects, these lead-resin soaps were only recently highlighted in paintings [START_REF] Poli | Aging of Natural Resins in Presence of Pigments: Metal Soap and Oxalate Formation[END_REF]. Further investigation would be required to evaluate the long-term consequences of the presence of these species in the complex paint system. The exact role of oil would also have to be further investigated: although the oil is not necessary to form the gel, it may also be involved in the gelation process. Indeed, adding oil to the system should induce the formation of lead soaps or even "mixed" carboxylates (from a possible interaction oil-lead-resin).

Figure 1 :

 1 Figure 1: Commercial triterpenoids: oleanolic acid (a) and lupeol (b)

  Photographs

Figure 2

 2 Figure 2: a) Reconstruction of Gumtion gels according to Ibbetson's recipe (oil + mastic resin+ PbOAc (s) ); b) "model system": gel without oil (mastic varnish + PbOAc (s) ).

Figure 3 :

 3 Figure 3: Images showing the preparations that, in addition to PbOAc (s) , will form a gel with mastic varnish: a) lead oxide (PbO), b) lead tetroxide (Pb 3 O 4 ) and c) hydrocerusite (2PbCO 3 Pb(OH) 2 ).

Figure 4 :

 4 Figure 4: Images showing the preparations that do not form a gel with mastic varnish: Pb(NO 3 ) 2 , PbCl 2 , Ca(CH 3 COO) 2 H 2 O, Cu 2 (CH 3 COO) 4 H 2 O, Mn(CH 3 COO) 2 4H 2 O, Zn(CH 3 COO) 2 2H 2 O (respectively from a to f).

Figure 6 :

 6 Figure 6: ATR-FTIR spectra of a) Pb(CH 3 COO) 2 •3H 2 O (PbOAc (s) ) (pink), mastic varnish (blue) and the corresponding gel, with PbOAc (s) 33 wt% (red); b) PbO (pink), mastic varnish (blue) and the corresponding gel with PbO 33 wt% (red); c) mixtures of varnishes (resin + turpentine) and PbO 33 wt%; d) mixture of mastic varnish (mastic + turpentine) and Cu 2 (CH 3 COO) 4 , H 2 O (CuOAc) 33 wt%.

Table 1 :

 1 Comparison between Megilp and Gumtion recipes, according to the texts reported inCarlyle, 2001a and b.

  pp.394-398, give qualitative descriptions of the properties of Gumtion and its variations, such as: "consistency of butter" (Bulkley, 1821 p.54;

	Arnald, 1839 p.11), "white, creamy, opaque compound" (Reeves and Sons, 1852 p.61), "white
	creamy emulsion" (Edwards, 1856 pp.30-1), "opaque mixture" (Field, 1835 p.208). However,
	as commonly observed with paint materials, the mixture obtained can vary according to a

number of different parameters including whether the mastic resin and lead acetate are introduced as dry powders or predissolved in turpentine or water respectively. The care in preparation, particularly in grinding in Ibbetson's original recipe also plays a role, "A good deals depends on the practice, in preparing Gumtion […]" (Ibbetson, 1828 p.16, see above).

Table 2 :

 2 Influence of the amount of PbOAc (s) on the rate of the gelation of systems containing 2 g of mastic varnish (mastic resin + turpentine).

	Weight of	PbOAc (s) %wt	Gelation
	PbOAc (s) (g)		time
	0.01	0.5	No gelation
	0.05	2.4	6 h
	0.10	4.8	2 h
	0.50	20	15 min
	1.00	33.3	10 min
	1.50	42.9	5 min
	3.00	60	1 min

Acknowledgments

The PhD of Hélène Pasco was funded by the ED397 and the LabEx MiChem, part of the French state funds managed by the ANR within the investissements d'avenir program under reference ANR-11-10EX-0004-02.


Samuele Giraudo
email: samuele.giraudo@univ-eiffel.fr

The combinator M and the Mockingbird lattice

Keywords: 2020 Mathematics Subject Classification. 03B40, 05A19, 05E99, 06A07, 06A11 Partial orders, Lattices, Combinatory logic, Rewrite systems, Treelike structures, Formal power series

We study combinatorial and order theoretic structures arising from the fragment of combinatory logic spanned by the basic combinator M. This basic combinator, named as the Mockingbird by Smullyan, is defined by the rewrite rule Mx 1 → x 1 x 1 . We prove that the reflexive and transitive closure of this rewrite relation is a partial order on terms on M and that all connected components of its rewrite graph are Hasse diagram of lattices. This last result is based on the introduction of new lattices on duplicative forests, which are sorts of treelike structures. These lattices are not graded, not self-dual, and not semidistributive. We present some enumerative properties of these lattices like the enumeration of their elements, of the edges of their Hasse diagrams, and of their intervals. These results are derived from formal power series on terms and on duplicative forests endowed with particular operations.

Combinatory logic is a model of computation introduced by Schönfinkel [Sch24] and developed by Curry [Cur30] with the objective to abstain from the need of bound variables specific to the λ-calculus. Its combinatorial heart is formed by terms, which are binary trees with labeled leaves, and rules to compute a result from a term, which are rewrite relations on trees [BN98, BKdVT03] (clear and complete modern references about combinatory logic are [START_REF] Barendregt | The lambda calculus, its syntax and semantics, volume 103 of Studies in logic and the foundations of mathematics[END_REF]HS08,Bim11,Wol21]). An important instance of combinatory logic is the system containing the basic combinators K and S together with the two rewrite rules A lot of other basic combinators with their own rewrite rules have been introduced by Smullyan in [START_REF] Smullyan | To Mock a Mockingbird[END_REF] after -now widely used-bird names, forming the enchanted forest of combinator birds. For instance, K is the Kestrel and S is the Starling. Usual computer scienceoriented questions consist in considering a fragment of combinatory logic, that is a finite set of combinators with their rewrite rules which is not necessarily combinatorially complete, and ask for the following questions:

(a) Given two terms t and t ′ , can we decide if t and t ′ can be rewritten eventually in a same term? This is known as the word problem [BN98,Sta00]. This question admits a positive answer for some basic combinators like among others the Lark [Sta89,SWB93] and the Warbler [SWB93] but it still open for the Starling [START_REF] Barendregt | Dance of the starlings[END_REF]; (b) Given a term t, can we decide if all rewrite sequences starting from t are finite? This is known as the strong normalization problem. This question admits a positive answer for, among others, the Starling [Wal00] and the Jay [PS01]. Related to this, see also [DGK + 13, BGZ17] for a probabilistic and asymptotic study of strong normalizing terms.

Here, we decide to pursue this study in a different direction by asking questions from a combinatorial point of view, including the study of order theoretic structures and adopting an enumerative approach. In particular, by denoting by ≼ (resp. by ≡) the reflexive and transitive (resp. reflexive, symmetric, and transitive) closure of the rewrite relation, we ask the following questions: This work fits in this general project consisting in mixing combinatory logic with combinatorics. These enumerative questions, including the enumeration w.r.t. some size notions (like the height or the number of basic combinators of the terms) of some particular terms of a system (like its normal forms or the minimal or maximal elements of its partial order) lead to density properties of the counted terms among the terms of the same size. This gives information about the probability for a term of a given size generated uniformly at random to satisfy some property. Besides, some of the mentioned questions can be addressed by working with rewrite graphs, that are graphs labeled by terms and where there is a directed edge between two terms if the first can be obtained from the second by a rewriting step. Such graphs appear naturally in the study of term rewrite systems [START_REF] Berry | Minimal and optimal computations of recursive programs[END_REF]. Some different graphs have been considered in the literature, where vertices are no longer terms but rather sequences of rewriting steps (see for instance [START_REF] Berry | Minimal and optimal computations of recursive programs[END_REF][START_REF] Venturini Zilli | Reduction graphs in the lambda calculus[END_REF] and [Bar81, Exercise 12.4.2.]). These graphs, as well as some of their semilattice properties [BL79, Theorem 2.3.1.], have no direct links with the present work.

We choose here to start this project by studying the system made of a single combinator, the combinator M, known as the Mockingbird [START_REF] Smullyan | To Mock a Mockingbird[END_REF] or as the little omega. This combinator is a very simple and an important one (see for instance [Sta11b,Sta17]). By drawing the portions of the rewrite graph starting from terms on M, the first properties that stand out are that the graph does not contain any nontrivial loops and that its connected components are finite and have exactly one minimal and one maximal element. At this stage, driven by computer exploration, we conjecture that the relation ≼ on the terms on M is a partial order relation and that each ≡-equivalence class is a lattice w.r.t. this partial order relation. This lattice property is for us a good clue for the fact that this system contains rather rich combinatorial properties.

To prove this last property, we introduce new lattices on duplicative forests, that are kinds of treelike structures, and show that each maximal interval from any term on M is isomorphic as a poset to a maximal interval of a lattice of duplicative forests (Theorem 2.3.4). We define the Mockingbird lattice of order d ⩾ 0 as the lattice M(d) consisting in the closed terms on M equal as or greater than the right comb closed term on M of degree d. We prove that each interval of the poset of duplicative forests is contained as an interval in M(d) for a certain d ⩾ 0 (Theorem 2.3.5). Since any closed term on M can be seen as a binary tree, this provides a new lattice structure on these objects. A lot of similar lattices have been studied on binary trees such as, among others the very famous Tamari lattice [Tam62], the Kreweras lattice [START_REF] Kreweras | Sur les partitions non croisées d'un cycle[END_REF], the Stanley lattice [START_REF] Stanley | The Fibonacci lattice[END_REF], the phagocyte lattice [START_REF] Baril | The phagocyte lattice of Dyck words[END_REF], and the pruning-grafting lattice [BP08]. However, unlike these lattices having for each order d ⩾ 0 a cardinality equal to the d-th Catalan number, the lattices M(d) are enumerated by a different integer sequence. To obtain enumerative results about the Mockingbird lattices and all the posets of terms on M in general, we use formal power series on terms and on duplicative forests, and several products on these. In this way, we enumerate the minimal and maximal elements of the infinite poset of the closed terms on M (Propositions 3.2.1 and 3.2.2), the lengths of the shortest and longest saturated chains of M(d) (Proposition 3.3.1), the cardinality of M(d) (Proposition 3.4.3), the number of edges of the Hasse diagram of M(d) (Proposition 3.4.6), and the number of intervals of M(d) (Proposition 3.4.10). We also provide general results for systems of combinatory logic: we give in particular a necessary condition on the rewrite rules in order to have only finite connected components in the rewrite graph (Proposition 1.2.3). This relies on a combinatorial property on basic combinators, called the hierarchical property. We also discuss some consequences of this fact in order to construct models for systems having this property. These are in fact the algebras over a certain abstract clone [Tay93] defined from the system. When the relation ≼ is a partial order relation, such models have a potential nice algorithmic computational complexity.

This paper is organized as follows. Section 1 contains the preliminary notions and definitions about terms, rewrite relations, and combinatory logic systems. We show here some general properties of these systems. In Section 2, we study the combinatory logic system on M and the Mockingbird lattices. Finally, Section 3 contains our enumerative results about Mockingbird lattices. This text ends with the presentation of some open questions raised by this work.

This paper is an extended version of [START_REF] Giraudo | Mockingbird lattices[END_REF], announcing the main results without any proofs. The present version contains all proofs of the stated results, more examples, and presents new results as discussions about some models of the combinatory logic system on M and the enumeration of isolated elements of the poset of the closed terms on M. This version uses also the formalism of abstract clones in order to work with terms and rewrite systems.

General notations and conventions. If S is a finite set #S is the cardinality of S. For any integers i and j, [i, j] denotes the set {i, i + 1, . . . , j}. For any integer i, [i] denotes the set [1, i] and i] denotes the set [0, i]. For any set A, A * is the set of all words on A. For any w ∈ A * , ℓ(w) is the length of w, for any i ∈ [ℓ(w)], w(i) is the i-th letter of w, and |w| a is the number of occurrences of the letter a ∈ A in w. The only word of length 0 is the empty word ε. For any statement P, the Iverson bracket [ [ [ P ] ] ] takes 1 as value if P is true and 0 otherwise.

TERMS, REWRITE RELATIONS, AND COMBINATORY LOGIC SYSTEMS

In this preliminary part, we set the main definitions and notations used in the sequel. We introduce also the central notion of combinatory logic systems, which are defined from special kinds of rewrite relations. We show also some general properties of these systems.

1.1. Terms, compositions, and rewrite relations. Let us start by presenting here the notions of terms, composition, and rewrite relations.

1.1.1. Terms. An alphabet is a finite set G. Its elements are called constants or basic combinators. Any element of the set X := n⩾1 X n , where X n := {x 1 , . . . , x n }, is a variable. The set T(G) of G-terms (or simply terms when the context is clear) is so that any variable of X is a G-term, any constant of G is a G-term, and if t 1 and t 2 are two G-terms, then (t 1 ⋆ t 2 ) is a G-term. For any n ⩾ 0, we denote by T n (G) the set of G-terms t having all variables belonging to X n .

From this definition, any term is a rooted planar binary tree where leaves are decorated by variables or by constants. We shall express terms concisely by removing superfluous parentheses by considering that ⋆ associates to the left and also by removing the symbols ⋆ (see the example given in (1.1.1), (1.1.2), and (1.1.3)).

4/30

2022 -10 -20 21 : 52

Let t be a G-term. The degree deg(t) of t is the number of internal nodes (the nodes decorated by ⋆) of t seen as a binary tree. For any a ∈ X ∪ G, deg a (t) is the number of nodes labeled by a in t. The depth of a node u of t is the number of internal nodes in the path connecting the root of t and u. The height ht(t) of t is the maximal depth among all the nodes of t. The frontier of t is the sequence of all the variables appearing in t from the left to the right. The term t is planar if its frontier is of the form x 1 x 2 . . . x n where n ⩾ 0. The term t is linear if there are no multiple occurrences of the same variable in its frontier. A closed term or combinator is a term of T 0 (G) having thus no occurrence of any variable. For instance, by setting G := {A, B}, the G-term t := ((

(A ⋆ x 3 ) ⋆(B ⋆((x 1 ⋆ x 3 ) ⋆ x 1 ))) ⋆(A ⋆ A)) (1.1.1)
draws as the binary tree

A x 1 A A x 3 B x (1.1.2)
and expresses concisely as

t = (A x 3 )(B(x 1 x 3 x 1 ))(A A). (1.1.3)
Its degree is 7, its height is 5, its frontier is x 3 x 1 x 3 x 1 , and is an element T n (G) for any n ⩾ 3. and by identifying variables with terms in a coherent way, whenever s → s ′ . For instance, for G := {A, B, C} and the rewrite relation → satisfying x 1 (A x 1 ) → x 1 x 2 , we have

x 3 B(A(x 3 B))(x 4 A) x 3 B C(x 4 A) (1.1.8) because x 3 B(A(x 3 B))(x 4 A) = x 1 (x 2 A) [x 1 (A x 1 ), x 4 ] [x 3 B, C, x 3 , x 4 ]
(1.1.9) and

x 3 B C(x 4 A) = x 1 (x 2 A) [x 1 x 2 , x 4 ] [x 3 B, C, x 3 , x 4 ].
(1.1.10)

Observe in this example that the variable x 2 occurs in the right member of → and not in the left member. For this reason, this variable can be replaced by any term in the context closure of → (it is replaced by C in the example).

1.1.4. Applicative term rewrite systems. An applicative term rewrite system (or ATRS for short) is a pair (G, →) such that G is an alphabet and → is a rewrite relation on T(G). Let T := (G, →) be an ATRS. We denote by ≼ the reflexive and transitive closure of . This relation ≼ is by construction a preorder. We denote by ≡ the reflexive, symmetric, and transitive closure of and by [t] ≡ the ≡-equivalence class of t ∈ T(G). This relation ≡ is by construction an equivalence relation. The rewrite graph G T of T is the digraph on the set T(G) of vertices where there is an arc from t ∈ T(G) to t ′ ∈ T(G) if t t ′ . For any t ∈ T(G), we also denote by G T (t) the subgraph of G T restrained on the set {t ′ ∈ T(G) : t ≼ t ′ } of vertices. The ATRS T is locally finite if for any term t, [t] ≡ is finite. This is equivalent to the fact that all the connected components of G T are finite. A G-term t is a normal form of T if there is no arc of source t in G T . We say that t is weakly normalizing if there is at least one normal form in G T (t) and that t is strongly normalizing if G T (t) is finite and acyclic. When all the G-terms are strongly normalizing, T is terminating. Besides, if for any t, s

1 , s 2 ∈ T(G), t ≼ s 1 and t ≼ s 2 implies the existence of t ′ ∈ T(G) such that s 1 ≼ t ′ and s 2 ≼ t ′ , then T is confluent.
1.1.5. Partial orders. When T := (G, →) is an ATRS such that ≼ is antisymmetric, ≼ is a partial order relation. In this case, T has the poset property and we shall denote by P T the poset (T(G), ≼). For any t ∈ T(G), let P T (t) be the subposet of P T having t as least element. Again in this case, a G-term t is minimal (resp. maximal) if t is a minimal (resp. maximal) element of P T . Observe that any normal form is maximal but the converse is false because a maximal element t could satisfy t t. A G-term t is isolated if t is both minimal and maximal.

When T has the poset property, T is rooted if for any term t, the subposet [t] ≡ of P T has a unique minimal element. Finally, T has the lattice property if T has the poset property and for all t ∈ T(G), all posets P T (t) are lattices.

6/30

2022 -10 -20 21 : 52 1.2. Combinatory logic systems. We begin by defining combinatory logic systems as particular ATRS and present some consequence of nonerasing and hierarchical combinatory logic systems (notions defined thereafter). We explain some of the consequences of the local finiteness, the poset property, and the lattice property on the models of combinatory logic systems.

1.2.1. Main definitions. A combinatory logic system (or CLS for short) is an ATRS C := (G, →) such that for each constant X of G, there is exactly one rewrite rule where X appears, and this rule is of the form

X x 1 . . . x n → t X (1.2.1)
where n ⩾ 1 and t X is a term having no constants and having all variables in X n . Moreover, all rewrite rules of C must be of the form (1.2.1). The integer n is the order of X in C. Some well-known terms t X appearing among others in [START_REF] Smullyan | To Mock a Mockingbird[END_REF] are,

• with order 1, t

I := x 1 (Identity bird), t M := x 1 x 1 (Mockingbird); • with order 2, t K := x 1 (Kestrel), t T := x 2 x 1 (Thrush), t M 1 := x 1 x 1 x 2 (Mockingbird 1), t W := x 1 x 1 x 2 (Warbler), t L := x 1 (x 2 x 2 ) (Lark), t O := x 2 (x 1 x 2 ) (Owl), t U := x 2 (x 1 x 1 x 2 ) (Turing Bird); • with order 3, t C := x 1 x 3 x 2 (Cardinal), t V := x 3 x 1 x 2 (Vireo), t B := x 1 (x 2 x 3 ) (Bluebird), t S := x 1 x 3 (x 2 x 3 ) (Starling); • with order 4, t J := x 1 x 2 (x 1 x 4 x 3 ) (Jay). The constant X is nonerasing if t X contains at least one occurrence of each variable x i for any i ∈ [n]. The constant X is hierarchical if for any i ∈ [n], x i appears in t X at depth n + 1 -i.
For instance, the terms t X such that X are hierarchical and of order 3 or less are

x 1 x 1 , x 1 x 1 x 2 , x 2 (x 1 x 1 ), x 1 x 1 x 2 x 3 , x 2 (x 1 x 1 )x 3 , x 3 (x 1 x 1 x 2 ), x 3 (x 2 (x 1 x 1 )). (1.2.2)
In particular, if X is hierarchical, then X is nonerasing. We say that C is nonerasing (resp. hierarchical) if all constants of G are nonerasing (resp. hierarchical). Other interesting properties of basic combinators are introduced in [Bim11] but they do not intervene directly in this work.

Consider for instance the CLS C := (G, →) where G contains only the constant I where t I is defined above. It is straightforward to show that C has the poset property. Nevertheless, C has not the lattice property, as suggested by the Hasse diagram shown in Figure 1a. On the other side, the CLS C := (G, →) where G contains only the constants K and S where t K and t S are defined above does not have the poset property. Indeed, ≼ is not antisymmetric because by setting t := S(S(KS)(K(SKK)))(K(SKK)), we have s ≼ s ′ and s ′ ≼ s where s := tt(ttt) and s ′ := ttt(ttt). This can be seen by noticing that t x 1 x 2 ≼ x 2 x 2 . Figure 1b shows a part of the rewrite graph of C.

Properties of CLS.

Let us state some properties of CLS related to their properties of confluence, termination, and local finiteness. admits exactly one minimal element. In this case, there is a one-to-one correspondence between the set of the minimal terms and the set of the maximal terms of C and this correspondence preserves the ≡-equivalence classes. The Mockingbird lattice S. Giraudo a general description of algebras over abstract clones). In more concrete terms, for this particular case of abstract clone, this is the data of a magma (M, ⋆) such that G ⊆ M and, for each rule X x 1 . . . x n → t X , the axiom (. . . ((X ⋆ x 1 ) ⋆ x 2 ) . . .) ⋆ x n = e X holds, where e X is the expression having t X as syntax tree. For instance, a model of the CLS on the constants K and S is a set M containing K and S, and endowed with an operation ⋆ : When C is hierarchical and has the poset property, as already noticed, each ≡-equivalence class contains exactly one maximal element. Therefore, the set M max of the maximal terms of T(G) is a set of representatives of the set of the ≡-equivalence classes and forms a model of C isomorphic to the trivial model. When additionally C is rooted, as already noticed, each ≡-equivalence class contains exactly one minimal element. For this reason, the set M min of the minimal terms of T(G) is a set of representatives of the set of the ≡-equivalence classes and forms a model of C isomorphic to the previous ones. Here also, for any n ⩾ 0, we define the model M max n (resp. M min n ) as the restriction of M max (resp. M min ) on T n (G). The interest of these two models M max and M min relies on considerations about algorithmic complexity for the computation of the product t 1 ⋆ t 2 where t 1 and t 2 are two terms of the models.

M 2 → M satisfying (K ⋆ x 1 ) ⋆ x 2 = x 1 and ((S ⋆ x 1 ) ⋆ x 2 ) ⋆ x 3 = (x 1 ⋆ x 3 ) ⋆(x 2 ⋆ x 3 ). Such

THE MOCKINGBIRD LATTICE

This central section of this work concerns the study of the poset associated with the CLS containing the basic combinator M. We shall prove that this CLS has the poset property, is rooted, and has also the lattice property by introducing new lattices on some kind of treelike structures, called duplicative forests.

2.1. The combinator M and its poset. Let the CLS C := (G, →) such that G := {M} and t M = x 1 x 1 . Since M is the Mockingbird basic combinator, we call C the Mockingbird CLS. Observe that M is hierarchical so that C satisfies the properties stated by Proposition 1.2.3 and is in particular locally finite. From now, we shall simply write G instead of G C . Figure 2 provides an example of a fragment of G.

First properties.

Let us present some first properties of C. We begin by providing a recursive description of the rewrite relation .

Lemma 2.1.1. For any t, t ′ ∈ T(G), we have t t ′ if and only if

t = t 1 t 2 , t ′ = t ′ 1 t ′ 2 with t 1 , t 2 , t ′ 1 , t ′ 2 ∈ T(G)
, and at least one of the following assertions holds:

(i) t 1 t ′ 1 and t 2 = t ′ 2 ; (ii) t 2 t ′ 2 and t 1 = t ′ 1 ; (iii) t 1 = M and t 2 = t ′ 1 = t ′ 2 . Proof.
= t ′ 1 = t ′ 2 , then θ(t) = θ(t 2 ) +(1, -1) and θ(t ′ ) = θ(t 2 ) +θ(t 2 ) +(1, 0). Since t ̸ = t ′ , we have t 2 ̸ = M so that θ(t) < θ(t ′
). This implies that ≼ is antisymmetric, so that (ii) holds.

To prove that C is rooted, we consider the rewrite relation → ′ obtained by inverting →. Thus, → ′ satisfies x 1 x 1 → ′ Mx 1 . This ATRS (T(G), → ′ ) does not admit any overlapping term (see [START_REF] Bezem | Term Rewriting Systems[END_REF]Chapter 2]). Therefore, it is confluent. A consequence of (i), is that this ATRS has only finite ≡ ′ -equivalence classes. By using additionally [BKdVT03, Theorem 1.2.2], each ≡ ′ -equivalence class admits exactly one term t such that for any t ′ ∈ [t] ≡ ′ , t ′ ≼ ′ t. This implies that in C, each ≡-equivalence class admits exactly one minimal term. Therefore, (iii) holds. □ By Proposition 2.1.2, P C is a well-defined poset, called Mockingbird poset. From now, we shall simply write P instead of P C . We have the following recursive description of ≼. Lemma 2.1.3. For any t, t ′ ∈ T(G), we have t ≼ t ′ if and only if at least one of the following assertions holds: The Mockingbird lattice S. Giraudo 2.2. Duplicative lattices. We introduce here duplicative forests and a partial order relation on these objects. We show that this partial relation endow all intervals of this poset with lattice structures.

(i) t = M = t ′ ; (ii) t = x i = t ′ for an x i ∈ X; (iii) t = t 1 t 2 , t ′ = t ′ 1 t ′ 2 , t 1 ≼ t ′ 1 , and t 2 ≼ t ′ 2 where t 1 , t ′ 1 , t 2 , t ′ 2 ∈ T(G); (iv) t = Mt 2 , t ′ = t ′ 1 t ′ 2 , t 2 ≼ t ′ 1 ,

Duplicative forests.

A duplicative tree is a planar rooted tree such that each internal node is either a black node or a white node . A duplicative forest is a word f = f(1) . . . f(ℓ), ℓ ⩾ 0, of duplicative trees. In particular, the empty word ε is the empty forest. We denote by D (resp. D * ) the set of such trees (resp. forests). The height ht(f) of f is the number of internal nodes in a longest path following edges connecting a node to one of its child. In the sequel, we shall write expressions using some occurrences of : each such expression denotes the two expressions obtained by replacing simultaneously all either by or by . The grafting product is the unary operation on D * such that for any f ∈ D * , (f) is the duplicative tree obtained by grafting the roots of the duplicative trees of f on a common root node . The concatenation product is the binary operation on D * such that for any f 1 , f 2 ∈ D * , f 1 f 2 is the duplicative forest made of the trees of f 1 and then of the trees of f 2 .

A poset on duplicative forests.

Let be the binary relation on D * defined recursively as follows. For any f, f ′ ∈ D * , we have f f ′ if f and f ′ have the same length ℓ ⩾ 1 and

• either ℓ = 1, f = (g) and f ′ = (g g) where g ∈ D * ; • or ℓ = 1, f = (g), f ′ = (g ′ ) where g, g ′ ∈ D * and g g ′ ; • or ℓ ⩾ 2 and there is a j ∈ [ℓ] such that f(j) f ′ (j), and for all i ∈ [ℓ] \ {j}, f(i) = f ′ (i).
We observe that f f ′ if and only if f ′ can be obtained from f by selecting a white node of f, by turning it into black, and by duplicating its sequence of descendants. For instance, we have .

(2.2.1)

Observe also that in this case, there are more black nodes in f ′ than in f. Hence, the reflexive and transitive closure ≪ of is antisymmetric so that (D * , ≪) is a poset. We call this poset the duplicative forest poset. For any f ∈ D * , we denote by D * (f) the subposet of the duplicative forest poset on the set {f ′ ∈ D * : f ≪ f ′ }. Figure 3 shows the Hasse diagram of the poset D * (f) where f is a certain duplicative forest. According to this Hasse diagram, the duplicative forest poset is not graded. We have the following recursive description of ≪. Lemma 2.2.1. For any two duplicative forests f and f ′ , we have f ≪ f ′ if and only if f and f ′ have the same length ℓ ⩾ 0 and one of the following assertions holds:

(i) ℓ = 0; (ii) ℓ = 1, f = (g) and f ′ = (g ′ g ′′
) where g, g ′ , g ′′ ∈ D * , g ≪ g ′ , and g ≪ g ′′ ;

(iii) ℓ = 1, f = (g), f ′ = (g ′ ) where g, g ′ ∈ D * and g ≪ g ′ ; (iv) ℓ ⩾ 2 and f(i) ≪ f ′ (i) for all i ∈ [ℓ].
Proof. This is a direct consequence of the definitions of and of ≪.

□ A first consequence of Lemma 2.2.1 is that for any f, f ′ ∈ D * , f ≪ f ′ implies ht(f) = ht(f ′ ).
12/30

⩾ 0, f 1 , . . . , f ℓ ∈ D, f ′ 1 , . . . , f ′ ℓ ∈ D, and f, f ′ , f ′′ ∈ D * , by f 1 . . . f ℓ ∧ f ′ 1 . . . f ′ ℓ := f 1 ∧ f ′ 1 . . . f ℓ ∧ f ′ ℓ , (2.2.2a) (f) ∧ f ′ := f ∧ f ′ , (2.2.2b) (f) ∧ f ′ f ′′ := f ∧ f ′ ∧ f ′′ (2.2.2c) and f 1 . . . f ℓ ∨ f ′ 1 . . . f ′ ℓ := f 1 ∨ f ′ 1 . . . f ℓ ∨ f ′ ℓ , (2.2.3a) (f) ∨ f ′ := f ∨ f ′ , (2.2.3b) (f) ∨ f ′ f ′′ := f ∨ f ′ f ∨ f ′′ . (2.2.3c)
Proposition 2.2.2. Given a duplicative forest f, the poset D * (f) is a lattice for the operations ∧ and ∨.

Proof. This follows by structural induction on f by establishing the fact that for any Proof. This follows by structural induction on f by establishing the fact that pr is a one-to-one correspondence between the sets D * (f) and D * (pr(f)) and that pr is an order isomorphism. This uses Lemma 2.2.1 in order to have a recursive description of the order relation ≪. □ For any d ⩾ 0, the d-ladder is the duplicative forest l d defined recursively by l 0 := ε and, for any d ⩾ 1, by l d := (l d-1 ). Let also

f ′ , f ′′ ∈ D * (f), the duplicative forest f ′ ∧ f ′′ (resp. f ′ ∨ f ′′ ) is
L := d⩾0 D * (l d ). (2.2.6)
By definition, L is the set of the duplicative forests that are equal as or greater than a d-ladder for a d ⩾ 0.

Lemma 2.2.4. For any f ∈ D * , there exists g ∈ L such that pr(f) = pr(g).

Proof. This follows by structural induction on f by showing that there is a d ⩾ 0 such that l d ≪ g and pr(f) = pr(g). This uses Lemma 2.2.1. □ An important consequence of Lemmas 2.2.3 and 2.2.4 is that for any f ∈ D * , there exists d ⩾ 0 such that D * (f) is isomorphic as a poset to a maximal interval of D * (l d ).

2.3. Mockingbird lattices. We show here that each subposet P(t), t ∈ T(G), of P is a lattice. This is based on a poset isomorphism between P(t) and an interval of a lattice of duplicative forests. We also define for each d ⩾ 0 the Mockingbird lattice of order d as a particular maximal interval of P.

2.3.1.

From terms to duplicative forests. Let fr : T(G) → D * be the map defined recursively, for any x i ∈ X and t, t ′ ∈ T(G), by fr(

x i ) := ε, (2.3.1a) fr(M) := ε, (2.3.1b) fr tt ′ := (fr(t ′ )) if t = M and t ′ ̸ = M, (fr(t) fr(t ′ )) otherwise.
(2.3.1c)

For instance,

M x 1 x 1 M M M M M M x 3 x
Intuitively, fr(t) is the duplicative forest obtained from t by the following process: replace each internal node of t having M as left child and having a right child different from M by a , replace each other internal node of t by a , and remove all the leaves. Immediately from the definition, we observe that this map is not injective. Moreover, again directly from the definition, any duplicative forest f in the image of fr is such that each white node of f has no more than one child.

Lemma 2.3.1. For any t ∈ T(G), the restriction of the map fr on the domain P(t) is injective.

Proof. This follows by structural induction on t by establishing the fact that for any s, s (fr(t)). □

Figure 4 shows the poset P(t) for a G-term t and the isomorphic poset D * (fr(t)). Theorem 2.3.4. For any t ∈ T(G), the poset P(t) is a finite lattice.

M(x1(Mx2))(MM) M(x1(x2x2))(MM)

x1(Mx2)(x1(Mx2))(MM) x1(x2x2)(x1(Mx2))(MM) x1(Mx2)(x1(x2x2))(MM) x1(x2x2)(x1(x2x2))(MM) (A) Hasse diagram of P(t). (B) Hasse diagram of D * (fr(t)).
Proof. By Proposition 2.3.3, P(t) is isomorphic as a poset to D * (fr(t)). Hence, and since by Proposition 2.2.2, D * (fr(t)) is a lattice, P(t) also is. The finiteness of P(t) is a consequence of the fact that by Proposition 2.1.2, C is locally finite. □

15/30

The Mockingbird lattice S. Giraudo 3.1. Formal power series. We set here some notions about formal power series and generating series. For the rest of the text, K is any field of characteristic zero (as Q for instance).

3.1.1. Formal power series over sets. For any set X, let K⟨X⟩ be the linear span of X. The dual space of K⟨X⟩ is denoted by K⟨⟨X⟩⟩ and is by definition the space of the maps F : X → K, called X-series. The coefficient F(x) of any x ∈ X is denoted by ⟨x, F⟩. The support of F is the set Supp(F) := {x ∈ X : ⟨x, F⟩ ̸ = 0}. The characteristic series of any subset X ′ of X is the series c(X ′

) having X ′ as support and such that the coefficient of each x ∈ X ′ is 1. For any k ⩾ 0, T k K⟨⟨X⟩⟩ is the k-th tensor power of K⟨⟨X⟩⟩. Elements of this space are possibly infinite linear combinations of tensors

x 1 ⊗ • • • ⊗ x k , where for any i ∈ [k],
x i ∈ X. The tensor algebra of K⟨⟨X⟩⟩ is the space

T * K⟨⟨X⟩⟩ := k⩾0 T k K⟨⟨X⟩⟩. (3.1.1)
This space is endowed with the tensor product ⊗ so that (T * K⟨⟨X⟩⟩, ⊗) is a unital associative algebra, admitting 1 ∈ K as unit.

A linear map φ :

T k 1 K⟨⟨X⟩⟩ → T k 2 K⟨⟨X⟩⟩, k 1 , k 2 ⩾ 0, is a (k 1 , k
2 )-operation on K⟨⟨X⟩⟩. To lighten the notation, when φ is a (2, 1)-operation on K⟨⟨X⟩⟩, we shall sometimes use φ as an infix operation by writing

F 1 φ F 2 instead of φ(F 1 ⊗ F 2 ) for any F 1 , F 2 ∈ K⟨⟨X⟩⟩.
The diagonal coproduct is the (1, 2)-operation ∆ on K⟨⟨X⟩⟩ satisfying ∆(x) = x ⊗ x for any x ∈ X. When X is endowed with an n-ary operation • :

X n → X, n ⩾ 0, for any k ⩾ 0, the k-linearization of • is the (nk, k)-operation • ⊗ k on K⟨⟨X⟩⟩ satisfying • ⊗ k (x 1,1 ⊗ • • • ⊗ x 1,k ⊗ • • • ⊗ x n,1 ⊗ • • • ⊗ x n,k ) = •(x 1,1 , . . . , x n,1 ) ⊗ • • • ⊗ •(x k
:= [ [ [ n 1 = n 2 ] ] ] z n 1 . (3.1.3)
The max product is the binary operation ↑ on K⟨⟨z⟩⟩ defined linearly for any n

1 , n 2 ⩾ 0 by z n 1 ↑ z n 2 := z max{n 1 ,n 2 }
. Observe that for any F ∈ K⟨⟨z⟩⟩ and n ⩾ 0,

⟨z n , F ↑ F⟩ = ⟨z n , F⟩ 2 + 2⟨z n , F⟩ i∈[n] z i-1 , F . (3.1.4)
3.1.3. Formal power series and enumeration. If X is endowed with a map ω : X → N, the ω-enumeration map is the partial map en ω : T * K⟨⟨X⟩⟩ → K⟨⟨z⟩⟩ defined linearly for any k ⩾ 1 and x 1 , . . . , x k ∈ X by

en ω (x 1 ⊗ • • • ⊗ x k ) := z ω(x 1 ) ↑ . . . ↑ z ω(x k ) . (3.1.5)
For any F ∈ T * K⟨⟨X⟩⟩, the generating series en ω (F) is the ω-enumeration of F.

In the sequel, we shall use the following strategy to enumerate a set X w.r.t. such a map ω: we shall provide a description of c(X), then deduce a description of en ω (c(X)), and finally deduce from this a formula to compute the coefficients ⟨z n , en ω (c(X))⟩, n ⩾ 0. 17/30 2022 -10 -20 21 : 52 Proposition 3.2.1. The characteristic series F max satisfies

F max = M + MM + F max ⋆ ⊗ F max -M ⋆ ⊗ F max .
(3.2.5) Proof. By using the description of Proposition 2.1.4 for the set S of closed maximal elements of P, we have

F max = M + s 1 ,s 2 ∈S s 1 s 2 - s 3 ∈S\{M} Ms 3 = M + F max ⋆ ⊗ F max -M ⋆ ⊗ (F max -M). ( 3
F iso = M + 2MM + F iso ⋆ ⊗ F iso -M ⋆ ⊗ F iso -⋆ ⊗ (∆(F iso )).
(3.2.9)

Proof. By using the description of Proposition 2.1.4 for the set S 1 (resp. S 2 ) of the closed maximal (resp. minimal) elements of P, the set of the closed isolated elements of P is the set S = S 1 ∩ S 2 and we have

F iso = M + s 1 ,s 2 ∈S s 1 s 2 - s 3 ∈S\{M} Ms 3 - s 4 ∈S\{M} s 4 s 4 = M + F iso ⋆ ⊗ F iso -M ⋆ ⊗ (F iso -M) -⋆ ⊗ (∆(F iso -M)).
( We deduce from this that the number of these terms of degree d ⩾ 0 is d iso (d) where d iso is the integer sequence satisfying d iso (0) = d iso (1) = 1 and, for any d ⩾ 2,

d min (d) = i∈ d-1] d min (i) d min (d -1 -i) -[ [ [ d is odd] ] ] d min d -1 2 . ( 3
d iso (d) = i∈ d-2] d iso (i) d iso (d -1 -i) -[ [ [ d is odd] ] ] d iso d -1 2 . ( 3
H iso = 1 + 2z + z(H iso ↑ H iso ) -2zH iso . (3.2.23)
We deduce from this and (3.1.4) that the number of these terms of height h ⩾ 0 is h iso (h) where h iso is the integer sequence satisfying h iso (0) = h iso (1) = 1 and, for any h ⩾ 2, where the integer decoration of each node refers to the image by ml of the duplicative tree rooted at this node.

h iso (h) = h iso (h -1) 2 -2h iso (h -1) + 2h iso (h -1) i∈[h-1] h iso (i -1). ( 3
Proposition 3.3.1. For any t ∈ T 0 (G), (i) a shortest saturated chain from t to the maximal element of P(t) has as length the number of in fr(t);

(ii) a longest saturated chain from t to the maximal element of P(t) has length ml(fr(t)).

Proof. Let f := fr(t). By Proposition 2.3.3, the posets P(t) and D * (f) are isomorphic. Therefore, to prove the statement, we consider the lengths of the shortest and longest saturated chains in D * (f) from f to g where g is the maximal element of D * (f).

First, immediately from the definition of ≪, a shortest saturated chain from f to g consists in selecting at each step a white node that has no white nodes as descendants and turn it into black. This establishes (i).

Let us prove (ii) by structural induction on f. We use Lemma 2.2.1 in order to exhibit a longest saturated chain from f to g. If f = f 1 . . . f ℓ , ℓ ⩾ 0, a longest saturated chain from f passes through the duplicative forest f ′ 1 f 2 . . . f ℓ and then passes through f ′ 1 f ′ 2 . . . f ℓ , . . . , and ends at f ′ 1 f ′ 2 . . . f ′ ℓ = g, where for any i ∈ [ℓ], f ′ i is the greatest element of D * (f i ). By induction hypothesis, ml(f i ) is the length of a longest saturated chain from f i to f ′ i . We deduce that the length of the former chain from f to g is 1 + i∈[ℓ] (ml(f i ) -1). Therefore, (3.3.1a) is consistent. If f = (f ′ ), f ′ ∈ D * , a longest saturated saturated chain from f to g has the same length as a longest saturated chain from f ′ to g ′ where g ′ is the greatest element of D * (f ′ ). Hence, by induction hypothesis, ml(f) is consistent with (3.3.1b). If f = (f ′ ), f ′ ∈ D * , a longest saturated chain from f to g passes through the covering (f ′ f ′ ) of f. Therefore, by induction hypothesis and by (3.3.1b) and (3.3.1a), a longest saturated chain from f to g has length 1 + ml(

(f ′ f ′ )) = 1 + 1 -2 + 2ml(f ′ ) = 2ml(f ′ ),

Introduction 1 .

 1 Terms, rewrite relations, and combinatory logic systems 1.1. Terms, compositions, and rewrite relations 1.2. Combinatory logic systems 2. The Mockingbird lattice 2.1. The combinator M and its poset 2.2. Duplicative lattices 2.3. Mockingbird lattices 3. Enumerative properties 3.1. Formal power series 3.2. Maximal, minimal, and isolated terms 3.3. Shortest and longest saturated chains 3.4. Elements, covering pairs, and intervals Open questions and future work References INTRODUCTION

  Determine if ≼ is a partial order relation; (b') In this case, determine if each interval of this poset is a lattice; (c') Enumerate the ≡-equivalence classes of terms w.r.t. the minimal degrees of their terms.

II

  Proposition 1.2.1. Any CLS is confluent. Proof. By definition, the underlying ATRS of any CLS is orthogonal [BN98, Chapter 6]. The statement follows from the fact that all orthogonal rewrite systems are confluent [Ros73]. □ 7/30 2022 -10 -20 21 : 52 The rewrite graph G → (II(III)).

  1.2.3. Models. Let C := (G, →) be a CLS. A model of C is an algebra over the abstract clone defined as the quotient of T(G) by the clone congruence ≡ (see for instance [Tay93] for 8/30 2022 -10 -20 21 : 52

FIGURE 2 .

 2 FIGURE 2. The fragment of the rewrite graph of C restrained to the terms reachable from closed terms of degrees 3 or less.

FIGURE 4 .

 4 FIGURE 4. A maximal interval of the Mockingbird poset from the term t := M(x 1( Mx 2 ))(MM) and its realization as a maximal interval in the duplicative forest poset.

  definition of the covering relation of ≪, it follows that for any ℓ ⩾ 0,f 1 , . . . , f ℓ ∈ D *, andf ∈ D * , cv(f 1 . . . f ℓ ) = i∈[ℓ] f 1 . . . f i-1 ⊗ cv(f i ) ⊗ f i+1 . . . f ℓ , (3.4.19a) cv( (f)) = ⊗ (cv(f)), (3.4.19b) cv( (f)) = ⊗ (cv(f)) + ⊗ (f f). (3.4.19c)Let ni be the (1, 1)-operation on K⟨⟨D * ⟩⟩ satisfying, for any f ∈ D * , ni(f) = cv(gr(f)).(3.4.20)By a straightforward computation, we obtainni(f) = f ′ ∈D * (f) #{f ′′ ∈ D * (f) : f ′′ f ′ } f ′ , (3.4.21) so that the coefficient of each f ′ ∈ D * (f) in ni(f) is the number of duplicative forests admitting f ′as covering in D * (f). For instance (see at the same time Figure3), For any ℓ ⩾ 0, f 1 , . . . , f ℓ ∈ D * , andf ∈ D * , ni(f 1 . . . f ℓ ) = i∈[ℓ] gr(f 1 . . . f i-1 ) ⊗ ni(f i ) ⊗ gr(f i+1 . . . f ℓ ), (3.4.23a) ni( (f)) = ⊗ (ni(f)), (3.4.23b) ni( (f)) = ⊗ (ni(f)) + ⊗ (ni(f f)) + ⊗ ⊗ (∆(gr(f))) . (3.4.23c) 24/30 2022 -10 -20 21 : 52

  (G) is finite. Since ≡ is the reflexive, symmetric, and transitive closure of , and since two terms t and t ′ are ≡-equivalent if and only if t and t ′ belong to the same connected component of G(C), the result follows. □ Let us use these results to state some properties of a CLS C. By Proposition 1.2.1 and [BKdVT03, Theorem 1.2.2], each ≡-equivalence class of terms of C admits at most one normal form. If C is hierarchical and has the poset property, it follows by Proposition 1.2.3 that for each term t of C, the subposet on [t] ≡ of P C admits exactly one maximal element. If additionally C is rooted, then for each term of C, the subposet on [t] ≡ of P C

	t ′ → provided by (1.1.7), the fact that all constants of G are hierarchical implies that ht(t) = ht(t ′ . From the definition of from ).
	Moreover, since C is also nonerasing, by Lemma 1.2.2, for any x i ∈ X, deg x i (t) ⩾ 1 if and
	only if deg x i (t

(B) The rewrite graph G → (SSK(SS)K). FIGURE 1. Some subgraphs of rewrite graphs of some CLS.

Lemma 1.2.2. Let C := (G, →) be a CLS. If C is nonerasing, then for any n ⩾ 0 and t ∈ T n (G),

[t] ≡ ⊆ T n (G).

Proof. Assume that t and t ′ are two G-terms such that t t ′ . From the definition of from → provided by (1.1.7), the fact that all constants of G are nonerasing implies that for any x i ∈ X,

deg x i (t) ⩾ 1 if and only if deg x i (t ′ ) ⩾ 1. Therefore, both t and t ′ belong to T n (G)

where n is an integer nonsmaller than the greatest index of the variables appearing in t and t ′ . Since ≡ is the reflexive, symmetric, and transitive closure of , the result follows. □ Proposition 1.2.3. Let C := (G, →) be a CLS. If C is hierarchical, then C is locally finite and all the G-terms of a same connected component of G C have the same height.

Proof. Assume that t and t ′ are two G-terms such that t ′ ) ⩾ 1. Observe moreover that for any n ⩾ 0, the number of terms of the same height in T n

  structures are known as combinatory algebras [HS08].The trivial model) of C is the magma (M, ⋆) where M is the set T(G)/ ≡ and, for any ≡ . Moreover, when C is nonerasing, for any n ⩾ 0, the n-trivial model of C is the trivial model restrained to ≡-equivalence classes of terms of T n (G). Thanks to Lemma 1.2.2, the n-trivial model is well-defined.

	[t	1 ] ≡ , [t	2 ] ≡ ∈ M, [t	1 ] ≡ ⋆[t 2 ] ≡ is the ≡-equivalence class of t	1 t	2 where t 1 is any element of [t 1 ] ≡
	and t	2 is any element of [t 2 ]

  -deg M (t)). We denote by ⩽ the lexicographic order on Z 2 and by + the pointwise addition on Z 2 . Let us prove by structural induction on T(G) that for any G-terms t and t ′ , t ̸ = t ′

	and t 2 for some G-terms t 1 t ′ = t ′ 1 , t t ′ 1 and t 2 = t ′ 2 , then θ(t) = θ(t t ′ 2 , t ′ 1 , and t ′ implies θ(t) < θ(t ′ 2 , and we have the three following cases. First, ). By Lemma 2.1.1, we have t = t 1 t 2 1 ) +θ(t 2 ) +(1, 0) and θ(t ′ ) = θ(t ′ 1 ) +θ(t 2 ) +(1, 0). Since, by induction hypothesis, θ(t and t ′ if t 1 1 ) < θ(t ′ 1 ), we have θ(t) < θ(t ′ ). Second, if t 2 t ′ 2 and t 1 = t ′ 1 , the same
	arguments as the previous ones (by interchanging the indices 1 and 2 in the concerned terms)
	apply. Finally, if t	1 = M and t 2

Proposition 2.1.2. The CLS C (i) is locally finite; (ii) has the poset property; (iii) is rooted. Proof. First, since M is hierarchical, by Proposition 1.2.3, C is locally finite. Therefore, (i) holds.

Let us prove that C has the poset property. For this, let θ : T(G) → Z 2 be the map defined for any t ∈ T(G) by θ(t) := (deg(t),

  By Lemma 2.1.1, this is equivalent to the fact t is maximal in P if and only if when t has an internal node having M as left subtree, this internal node admits necessarily M as right subtree. Therefore, (i) holds.The term t is minimal in P if and only if t ′ t implies that t ′ = t. By Lemma 2.1.1, this is equivalent to the fact t is minimal in P if and only if when t has an internal node such that its two children are equal, these two children are necessarily equal to M. Therefore, (ii) holds.

								and t 2 ≼ t ′ 2 where t ′ 1 , t 2 , t ′ 2 ∈ T(G).
	Proof. This is a direct consequence of Lemma 2.1.1 and of the fact that ≼ is the reflexive and
	transitive closure of .		□
	Proposition 2.1.4. Let t ∈ T(G).
		(i) The term t is a maximal element of P if and only if t avoids M(x 1 x 2 ) and suffix-avoids
			Mx 1 .
		(ii) The term t is a minimal element of P if and only if t avoids (x 1 x 2 )(x 1 x 2 ) and suffix-
			avoids x 1 x 1 .
		Besides, since C is hierarchical and has, by Proposition 2.1.2, the poset property, this CLS
	admits the model M max	described in Section 1.2.3. More specifically, this model is such that
	M max	is the set of the maximal elements of P, and, by Proposition 2.1.4, for any t 1 , t 2 ∈ M max	,
								t	1 ⋆ t	2 =	t t	2 t 2 2 1 t	if t 1 = M, otherwise.	(2.1.1)
	Since by Proposition 2.1.2, C is also rooted, C admits the model M min	described in Section 1.2.3.
	This model is such that M min	is the set of the minimal elements of P, and, by Proposition 2.1.4,
	for any t	1 , t	2 ∈ M min	,
								t	1 ⋆ t	2 =	Mt 2 t 2 1 t	if t otherwise. 1 = t 2 ,	(2.1.2)
	By representing G-terms directly has binary trees, the computations in M max	have a better
	time complexity than in M min	because to compute t	1 ⋆ t	2 in M min	, we need to decide if t	1 and
	t	2 are equal. Nevertheless, in return, the term t	1 ⋆ t	2 produced by a computation in M min	has
	a number of internal nodes equal as or smaller than the analogous computation in M max	.
	11/30

Proof. The term t is maximal in P if and only if t t ′ implies that t ′ = t. □ 2.1.2. Some models. We begin this discussion about models of C by a very simple observation: any idempotent monoid (M, •, e) is a model of C. Indeed, by identifying M with e (the unit of M) and by identifying ⋆ with •, we have for any

x ∈ M, M ⋆ x = e • x = x = x • x = x ⋆ x.

2022 -10 -20 21 : 52

  well-defined and is the meet (resp. the join) of f ′ and f ′′ . This uses Lemma 2.2.1 in order to describe f ′ andf ′′ from f knowing that f ≪ f ′ and f ≪ f ′′ .□ This forest has by construction no occurrence of any . For instance,

				pr -	.	(2.2.5)
	Lemma 2.2.3. For any f ∈ D * , the posets D *	(f) and D *	(pr(f)) are isomorphic.
	By Proposition 2.2.2, for any f ∈ D *	, each poset D *	(f) is a lattice. We call it the duplicative
	forest lattice of f.
	Let pr : D * → D *	be the map defined recursively, for any ℓ ⩾ 0, f 1 , . . . , f ℓ ∈ D *	, and f ∈ D *	,
	by
		pr(f			(2.2.4a)
		pr( (f)) := (pr(f)),	(2.2.4b)
		pr( (f)) := pr(f).	(2.2.4c)
	13/30

1 . . . f ℓ ) := pr(f 1 ) . . . pr(f ℓ ), 2022 -10 -20 21 : 52

The Mockingbird lattice

S. Giraudo

The duplicative forest pr(f) is the pruning of f.

  ′ ∈ P(t), fr(s) = fr(s ′) implies s = s ′ . This uses in particular Lemma 2.1.3 in order to describe s and s ′ from t knowing that t ≼ s and t ≼ s ′ . □

	Lemma 2.3.2. Let t ∈ T(G) and s, s ′ ∈ T(t) such that s ̸ = s ′ . We have s fr(s) fr(s ′ ).	s ′ if and only if
	Proof. This follows by structural induction on t. This uses in particular the definition of the binary relation on D

* , Lemma 2.1.3 in order to describe s and s ′ from t knowing that t ≼ s and t ≼ s ′ , and Lemma 2.1.1 in order to describe s ′ from s knowing that s ̸ = s ′ and s s ′ . □ Proposition 2.3.3. For any t ∈ T(G), the posets P(t) and D * (fr(t)) are isomorphic. Proof. Let D := {fr(t) : t ∈ P(t)}. By Lemma 2.3.1, the sets P(t) and D are in one-to-one correspondence. Moreover, by Lemma 2.3.2, we have that D = D * (fr(t)) and that fr is an order isomorphism between P(t) and D *

  Generating series. The space of the usual power series on the formal parameter z is denoted by K⟨⟨z⟩⟩. For anyF, F ′ ∈ K⟨⟨z⟩⟩, F[z := F ′] is the series of K⟨⟨z⟩⟩ obtained by substituting F ′ for z in F. The Hadamard product is the binary operation ⊠ on K⟨⟨z⟩⟩ defined linearly for any n

	,1 , . . . , x n,k ) (3.1.2)
	for any x i,j ∈ X, i ∈ [n], and j ∈ [k]. To lighten the notation, we shall write • ⊗	for • ⊗ 1	.
	3.1.2. 1 , n 2 ⩾ 0 by
	z n 1 ⊠ z n 2

  Motzkin tree is a planar rooted tree made of nodes of arity 0, 1, or 2. It is well-known that the sets of these trees having exactly d ⩾ 1 nodes are enumerated by Motzkin numbers (see [DP02] for instance). Given a closed maximal term t, it is easy to see that fr(t) contains only black nodes and that it is a Motzkin tree. It is also easy to check that fr is a bijection between the set of the closed maximal terms of degree d ⩾ 1 and the set of the Motzkin trees with d nodes.

							3.2.10)
	This leads to (3.2.9).					□
	3.2.3. deg-enumerations. A consequence of Proposition 3.2.1 and of (3.2.1) is that the deg-
	enumeration D max of F	max , enumerating the closed maximal elements of P w.r.t. their degrees,
	satisfies
				D max = 1 + z + zD 2 max -zD max .	(3.2.11)
	We deduce from this that the number of these terms of degree d ⩾ 0 is d	max (d) where d	max
	is the integer sequence satisfying d	max (0) = d	max (1) = 1 and, for any d ⩾ 2,
			d	max (d) =	d	max (i) d	max (d -1 -i).	(3.2.12)
						i∈ d-2]
	The first numbers are
						1, 1, 1, 2, 4, 9, 21, 51,	(3.2.13)
	form Sequence A001006 of [Slo], and are Motzkin numbers. A Besides, a consequence of Proposition 3.2.2, (3.2.1), and (3.2.3) is that the deg-enumeration
	D	min of F min , enumerating the closed minimal elements of P w.r.t. their degrees, satisfies
			D min = 1 + z + zD 2 min -z D min z := z 2 .	(3.2.14)
	We deduce from this that the number of these terms of degree d ⩾ 0 is d	min (d) where d	min is
	the integer sequence satisfying d	min (0) = d min (1) = 1 and, for any d ⩾ 2,

  Due to the fact that C is hierarchical and, by Proposition 2.1.2, P is rooted, Proposition 1.2.3 implies that P satisfies the properties exposed at the very end of Section 1.2.2. In particular, in each ≡-equivalence class of closed terms, there is exactly one closed maximal term, exactly one closed minimal term, and these terms have the same height. For this reason, the ht-enumerations of F max and F min are equal and enumerate also the ≡-equivalence classes of closed terms w.r.t. the heights of their elements.

						.2.18)
	The first numbers are
		1, 1, 1, 1, 3, 5, 13, 29, 71, 171, 427, 1067, 2709.		(3.2.19)
	This sequence does not appear in [Slo] for the time being.
	3.2.4. ht-enumerations. By denoting by
	H	mm this generating series, by Propositions 3.2.1 and 3.2.2, H mm satisfies
		H mm = 1 + z + z(H mm ↑ H mm ) -zH mm .			(3.2.20)
	We deduce from this and (3.1.4) that the number of these ≡-equivalence classes of terms of
	height h ⩾ 0 is h mm (h) where h mm is the integer sequence satisfying h	mm (0) = h mm (1) = 1
	and, for any h ⩾ 2,
		h mm (h) = h mm (h -1) 2 -h mm (h -1) + 2h	mm (h -1)	h	mm (i -1).	(3.2.21)
			i∈[h-1]
	The first numbers are
		1, 1, 2, 10, 170, 33490, 1133870930, 1285739648704587610	(3.2.22)
	and form Sequence A063573 of [Slo].
		Besides, a consequence of Proposition 3.2.3, (3.2.2), and (3.2.4) is that the ht-enumeration
	H	iso of F

iso , enumerating the closed isolated elements of P w.r.t. their heights, satisfies

  Let ml : D * → N be the statistics defined for any ℓ ⩾ 0, f 1 , . . . , f ℓ ∈ D * , and f ∈ D * by

	ml(f	1 . . . f ℓ ) := 1 -ℓ +	ml(f i ),	(3.3.1a)
					i∈[ℓ]
		ml( (f)) := ml(f),	(3.3.1b)
		ml( (f)) := 2ml(f).	(3.3.1c)
	For instance, we have
		8	2	2
	2	2	6	2	ml -10,	(3.3.2)
		2	2
		1
						.2.24)
	The first numbers are
	1, 1, 1, 3, 21, 651, 457653, 210065930571	(3.2.25)

and form Sequence A001699 of [Slo], which enumerates binary trees w.r.t. the height (but with a shift). Therefore, there is a one-to-one correspondence between the set of the closed isolated elements of P of height h ⩾ 1 and the set of the binary trees of height h -1. 20/30 2022 -10 -20 21 : 52 3.3. Shortest and longest saturated chains.

  which is consistent with (3.3.1c). □ By Proposition 3.3.1, for any d ⩾ 1, in M(d), shortest saturated chains are of length d and longest saturated chains are of length 2 d-1 . . Giraudo By Proposition 2.3.3, for any d ⩾ 1, the cardinality of M(d) is h gr (h) := z h , H gr ) where h = d -1. By Proposition 3.4.3, hgr is the integer sequence satisfying h gr (0) = 1 and, for any h ⩾ 1, A007018 of[Slo]. It is known that the sets of the planar rooted trees s made of nodes of arity 0, 1, or 2 and such that any path connecting the root of s to any leaf of s consists in d ⩾ 1 nodes are enumerated by the previous sequence. Let φ be the map sending any such planar rooted tree s to the duplicative tree obtained by replacing each node of s having a single child (resp. two children) by a white (resp. black) node and by removing all nodes which have no children. It is easy to see that φ is a bijection between the set of the planar rooted trees described above and D * (l h ) where h = d -1.3.4.3. Number of covering pairs.Let cv be the (1, 1)-operation on K⟨⟨D * ⟩⟩ satisfying, for any f ∈ D

	The Mockingbird lattice
	h gr (h) = h	gr (h -1) + h gr (h -1) 2 .	(3.4.16)
	The sequence of the cardinalities of M(d), d ⩾ 0, starts by
	1, 1, 2, 6, 42, 1806, 3263442, 10650056950806	(3.4.17)
	and forms Sequence
	21/30

S*

, cv(f) =

⋆ ⋆ ⋆ → x 1 x 3 x 2 x 3 ⋆ ⋆ ⋆ .(0.0.1)In this system, we have for instance the sequence of computationS S S K K S K ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ S K K S S ⋆ ⋆ ⋆ ⋆ K S S S K S ⋆ ⋆ ⋆ ⋆ ⋆ S S ⋆ (0.0.2)obtained by performing at each step one rewrite according to the previous rules. This system is important because it is combinatorially complete: each λ-term can be translated, by so-called bracket abstraction algorithms [Sch24, CF58], into a term over K and S emulating it.

x 3 ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆

x 2 M M ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ fr -.(2.3.2) 14/30

This research has been partially supported by the projects CARPLO (ANR-20-CE40-0007) and LambdaComb (ANR-21-CE48-0017) of the Agence nationale de la recherche.

§ Formal power series

The Mockingbird lattice S. Giraudo The Mockingbird lattice of order d ⩾ 0 is the lattice M(d) := P(r d ) where r d is the term recursively defined by r 0 := M and, for any d ⩾ 1, by r d := Mr d-1 . Figure 5 shows the Hasse diagrams of the first Mockingbird lattices.

(A) M(0).

(B) M(1).

(C) M(2).

(D) M(3).

(E) M(4). Theorem 2.3.5 justifies the fact that the study of the Mockingbird lattices is universal enough because these lattices contain as maximal interval all duplicative forest lattices.

The Mockingbird lattices are not graded and not self-dual. Since they are not graded, they are not distributive neither. Moreover, they are not semidistributive. For instance, in M(3), by setting t 1 := M(MM(MM)), t 2 := MM(MM)(M(MM)), and t 3 := M(MM)(MM(MM)), we have t

contradicting one of the required relations to have this property.

ENUMERATIVE PROPERTIES

In this last central part of this work, we present some enumerative results concerning the Mockingbird poset and lattices M(d), d ⩾ 0. We enumerate the maximal and minimal elements of the Mockingbird poset by degree and by height, the length of the shortest and longest saturated chains in M(d), the number of elements in M(d), the number of edges in the Hasse diagram of M(d), and the number of intervals of M(d). All this use the lattice isomorphism between the Mockingbird lattices and the duplicative forest lattices introduced in the previous sections and formal series on terms and on duplicative forests.

16/30

2022 -10 -20 21 : 52 § Three series of terms

The Mockingbird lattice S. Giraudo 3.2. Maximal, minimal, and isolated terms. We use here series on terms and some operations on these in order to enumerate the closed maximal, closed minimal, and closed isolated elements of the poset P w.r.t. their degrees or their heights. These enumerative results can be used to establish the probabilities for a term t of a given degree or of a given height generated uniformly at random to have one of these properties. In particular, the number of maximal (resp. minimal, isolated) closed terms gives information to compute the probability for the fact that t cannot be rewritten into a different term (resp. no term different from t rewrites into t, any sequence of rewriting steps involving t does not involve different other terms).

Series of terms and operations.

and

Observe also that for any F ∈ K⟨⟨T(G)⟩⟩,

(3.2.4) 3.2.2. Three series of terms. In order to achieve the objectives described above, we begin by providing equations satisfied by the characteristic series F max of the closed maximal terms of P, the characteristic series F min of the closed minimal terms of P, and the characteristic series F iso of the closed isolated terms of P. §

The Mockingbird lattice S. Giraudo 3.4. Elements, covering pairs, and intervals. We use here series on duplicative forests and a palette of operations on these to enumerate the elements, covering pairs, and intervals of the Mockingbird lattices. We obtain for these three recursive formulas leading to expressions for the generating series of these numbers. These enumerative results can be used to establish the probability for a pair (t 1 , t 2 ) of terms both of a given height and generated uniformly at random to have one of these properties. In particular, the number of covering pairs (resp. of intervals) gives information to compute the probability for the fact that t 1 can be rewritten in one step (resp. in any number of steps) into t 2 .

3.4.1. Series of duplicative forests and operations. We shall consider in the sequel the klinearization ⊗ k , k ⩾ 0, of the concatenation product of duplicative forests. Observe that for any F 1 , F 2 ∈ K⟨⟨D * ⟩⟩, we have in particular

We shall also consider the k-linearization ⊗ k , k ⩾ 0 of the grafting product . Observe that for any F ∈ K⟨⟨D * ⟩⟩, we have in particular

Intuitively, this product consists in grafting a onto one forest or a onto a forest and its right neighbor following the letters of u. Observe that for any u ∈ { , } * and F ∈ T k+|u| K⟨⟨D * ⟩⟩, we have en ht (mg u (F)) = z en ht (F).

(3.4.5)

Let us finally define the series of ladders as the D * -series

By definition, gr(f) is the characteristic series of D * (f) and is therefore also the formal sum of all duplicative forests f ′ such that f ≪ f ′ . For instance,

(3.4.24)

This establishes (3.4.23c). □

Observe that

and that the coefficient of each duplicative forest f of this set is the number of duplicative forests of this same set covered by f. Moreover, since for any h ⩾ 0, all elements of D * (l h ) have h as height, Contrary to what we have undertaken in Sections 3.4.2 and 3.4.3 where we have provided direct recursive expressions to compute gr(f) and ni(f), we fail to provide similar expressions for ns(f). The trick here consists in considering first a slightly different series depending on a parameter k ⩾ 1 which can be seen as a catalytic parameter. With this in mind, let for any k ⩾ 1, md k be the (1, k)-operation on K⟨⟨D * ⟩⟩ satisfying, for any

where ∧ is the meet operation of the duplicative forest lattices introduced in Section 2.2.3. We call md k (f) the k-meet decomposition of f. Observe that md 1 is the identity map.

26/30

2022 -10 -20 21 : 52

The Mockingbird lattice S. Giraudo Lemma 3.4.7. For any k ⩾ 1 and f ∈ D * ,

Proof. We have

showing the stated identity.

)

Proof. Relations (3.4.40a) and (3.4.40b) are direct consequences of Lemmas 2.2.1 and 3.4.7. By Lemmas 2.2.1 and 3.4.7,

where for any duplicative forest f, rts(f) is the word on { , } containing from left to right the roots of the trees forming f. This shows (3.4.40c). □

27/30

2022 -10 -20 21 : 52

The Mockingbird lattice

S. Giraudo

Observe that Supp(ns(ld)) = L and that the coefficient of each duplicative forest f of this set is the number of duplicative forests of this same set smaller than or equal as f. Moreover, since for any h ⩾ 0, all elements of D * (l h ) have h as height,

ns is the integer sequence satisfying h (k) ns (0) = 1 and, for any h ⩾ 1,

OPEN QUESTIONS AND FUTURE WORK

We have studied in this work a CLS having a lot of rich combinatorial properties despite its simplicity. This can be considered as the prototypical example for this kind of investigation. We could expect to have also similar combinatorial properties (related to poset and lattice properties, and quantitative data) for more complex CLS. In addition to the obvious possible future investigations consisting in studying in a similar fashion some other CLS, we describe here three open questions raised by this work.

The description of minimal and maximal elements of P uses a notion of pattern avoidance in terms (see Proposition 2.1.4). This is a general fact: when a CLS (G, →) has the poset property, its minimal (resp. maximal) elements are the terms avoiding some terms deduced from the ones appearing as right-hand (resp. left-hand) members of →. Such an enumerative problem has been considered in [START_REF] Khoroshkin | On generating series of finitely presented operads[END_REF][START_REF] Giraudo | Tree series and pattern avoidance in syntax trees[END_REF] for the particular case of linear terms. The question here concerns the general enumeration of terms avoiding a set of other terms wherein multiple occurrences of a same variable are allowed.

We have shown that the Mockingbird CLS has the poset property and is rooted (Proposition 2.1.2), and has the lattice property (Theorem 2.3.4) by employing some specific reasoning from the definition of the Mockingbird basic combinator M. A question here concerns the existence of a general criterion to decide if a CLS has the poset (resp. lattice) property and if it is rooted. All this seems independent from the property of a CLS to be hierarchical because, among others, the CLS containing a basic combinator X such that X has order 3 and t X := x 3 (x 1 x 1 x 2 ) has not the poset property because we have t t ′ and t ′ t with t := X X X(X X(X X)) and t ′ := X X(X X)(X X X) while X is hierarchical.

Finally, in Proposition 1.2.3, we have shown that being hierarchical is a sufficient condition for a CLS C to be locally finite. The question in this context consists in obtaining a necessary and sufficient condition for this last property. Observe that being nonerasing is necessary because, by assuming that C contains a basic combinator X such that X has order n ⩾ 2 and that there is i ∈ [n] such that x i does not appear in t X , we have X x 1 . . . x i-1 sx i+1 . . . x n t X for any term s, showing that the connected component of t X in G C is infinite.