Axel Antoine
email: axel.antoine@univ-lille.fr

Sylvain Malacria
email: sylvain.malacria@inria.fr

Nicolai Marquardt
email: n.marquardt@ucl.ac.uk

Géry Casiez
email: gery.casiez@univ-lille.fr

Esquisse: Using 3D Models Staging to Facilitate the Creation of Vector-based Trace Figures

Keywords: Trace figures, 3D models staging, Vector graphics, Blender BernardMinet24 BernardMinet24 Optimized templates Tools: anchor points, UI import, object manipulation Easy kinematic manipulation and automated posture traking Esquisse 3D Modelling Workflow Rendering

Trace figures are contour drawings of people and objects that capture the essence of scenes without the visual noise of photos or other visual representations. Their focus and clarity make them ideal representations to illustrate designs or interaction techniques. In practice, creating those figures is a tedious task requiring advanced skills, even when creating the figures by tracing outlines based on photos. To mediate the process of creating trace figures, we introduce the open-source tool Esquisse. Informed by our taxonomy of 124 trace figures, Esquisse provides an innovative 3D model staging workflow, with specific interaction techniques that facilitate 3D staging through kinematic manipulation, anchor points and posture tracking. Our rendering algorithm (including stroboscopic rendering effects) creates vector-based trace figures of 3D scenes. We validated Esquisse with an experiment where participants created trace figures illustrating interaction techniques, and results show that participants quickly managed to use and appropriate the tool.

Introduction

Trace figures are static illustrative figures created to capture the essence of a situation, removing unnecessary details by limiting the graphical representation to the most important contours/outlines of the shown objects and people (for example, the visual abstract of our Figure 1 includes several trace figures). Trace figures, even when augmented with graphical annotation overlays (such as text, arrows or circles), minimize visual clutter and are effective at describing the essence of an interactive scenario.

Likely because of their clarity and focus, trace figures are gaining popularity in the HCI community, especially for illustrating a novel interaction technique or interactive systems. As a result, they can be found in many papers, presentations or posters: over three years of UIST proceedings [START_REF]UIST '15: Proceedings of the 28th Annual ACM Symposium on User Interface Software and Technology[END_REF][START_REF]UIST '16: Proceedings of the 29th Annual Symposium on User Interface Software and Technology[END_REF][START_REF]UIST '17: Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology[END_REF] for instance, more than 25% of the published papers used trace figures, often used to demonstrate gestures, provide an overview of a system setup or illustrate a design space.

Producing trace figures from scratch without a model requires very good drawing skills. Therefore, many users have to rely on manual photo tracing in order to produce the outlines of devices and people shown in the illustrations [START_REF] Chi | Authoring illustrations of human movements by iterative physical demonstration[END_REF]. This manual tracing is a time-consuming and tedious task and eventually results in a limited workflow where even small changes of the drawn people, postures or devices might require starting again the manual tracing process from scratch. This is even more of a problem in cases where several hand postures must be produced or when users are required to change the point of view of the illustration. So far, research on the production of illustrations has been mostly focused on facilitating the production of new types of illustrations such as animated or interactive illustrations [START_REF] Kazi | Draco: Sketching animated drawings with kinetic textures[END_REF][START_REF] Kazi | Kitty: Sketching dynamic and interactive illustrations[END_REF], whether they illustrate interactive scenarios or not. However, despite the frequent use of trace figure to illustrate interactive scenarios, and the challenges of the process to produce them, we are lacking software tools that are targeted at facilitating their production.

In this paper, we support the hypothesis that 3D staging is a good alternative to mediate the production of static trace figures to illustrate interactive scenarios. More precisely, we present Esquisse, an open-source tool implementing an innovative 3D staging workflow for producing trace figures (Figure 1). In particular, the underlying idea behind Esquisse is to capitalize on the flexibility of a 3D modeling software for staging 3D scenes that are subsequently rendered as a trace-figure vector file that can still be post-edited in a vector-graphics software afterwards. We provide 3D models, tools and techniques to make this workflow accessible to every people even if they do not have previous experience with 3D modeling software.

The workflow implemented by Esquisse works as follows. Users open a 3D scene using one of the provided templates. If needed, they can directly modify the position and pose of the objects using interaction techniques provided by Esquisse that simplify the manipulation of these 3D objects. For instance, users can easily specify a hand posture using a Leapmotion hand tracking camera 4 , or by adding a contact point anchor which will snap a desired finger to this contact point and modify the hand pose according if the point is moved on the display. They can also add other avatars and objects to the scene if required. Users then position the camera in the 3D space according to their needs. They can also integrate interface screenshots in various displays. Optionally they can add a stroboscopic effect to illustrate the motion of a finger or object. A simple click to a Render button then calls Esquisse's rendering algorithm which generates a trace figure of the scene, integrating all added interface images, and outputs a vector-based file (examples of trace figures produced with Esquisse can be seen in Figure 1 and other figures throughout the paper; further renderings can be found in the Supplementary Material).

In summary, Esquisse's workflow facilitates the rapid production of trace figures, as well as the adaptation of existing figures. Our work makes the following contributions: (i) introducing a novel workflow for quickly creating vector based trace figures; (ii) presenting the design of interaction techniques to facilitate this workflow; (iii) developing an innovative rendering pipeline, adapted from existing techniques; (iv) implementing this workflow into a Blender add-on. To allow members of the HCI community to create trace figures with Esquisse, it is released as a free open-source5 add-on for the 3D modelling software Blender [START_REF] Hess | The Essential Blender: Guide to 3D Creation with the Open Source Suite Blender[END_REF].

The remainder of the paper is structured as follows. After presenting a taxonomy of illustrative figures for HCI scientific contribution, we discuss the existing workflows for creating trace figures. We then describe details of Esquisse's interaction techniques and its implementation, before discussing the evaluation and figures created by participants.

Taxonomy of Trace Figures

We define trace figures as graphical representations of the most essential features of a scene by using contours/outlines of objects, people and the environment. In this section, we will introduce a classification of different kinds of trace figures and discuss typical characteristics. To better understand the use of trace figures within the HCI community, we analysed the use of trace figures in the papers published over three years (2015-2017) of UIST proceedings [START_REF]UIST '15: Proceedings of the 28th Annual ACM Symposium on User Interface Software and Technology[END_REF][START_REF]UIST '16: Proceedings of the 29th Annual Symposium on User Interface Software and Technology[END_REF][START_REF]UIST '17: Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology[END_REF]. Many publications at UIST include details on gestural interaction techniques, use of interaction techniques and technical details on device use, and are a subset of the spectrum of publications published in the HCI community. Our initial sampling of proceedings indicated a common use of photo tracing in UIST papers, but our analysis below similarly translates to other HCI publications (e.g., Interact or ACM CHI), though the overall counts and percentages would probably differ.

Overall, we found 124 trace figures (often multiple per paper) in the 222 accepted UIST papers of these three years (trace figures in 29% of the papers).

We constrained our search so that all trace figures included in our sample set need to include at least one part of a person's body (e.g., a person's fingers, hand or full body), and therefore we did not include pure technical line drawing of components or devices. By following a systematic coding (by two researchers) and iterative thematic analysis of the figure sample set we identified the following five categories: Our categorization and identified characteristics are of course depending on our sample and the kind of publications at UIST, and it is likely that further categories and properties can be identified when widening the sample. However, our categories and characterizations are a first-order approximation of the kind of interaction technique trace figures created for publications within the HCI community.

We used this characterisation of trace figures to directly inform the design of Esquisse. We decided to support various hand gestures and full-body models in the application to capture much of the use cases for trace figures we found in the literature. Commonly used device types (such as phones, tablets and smartwatches) became part of our template library (explained shortly). We also decided to directly integrate different colouring and tracing mechanisms (e.g., see through lines, coloured areas), and to simplify the use of human body representations in the visualisations (through templates and automated hand tracking).

Practices for Creating Trace Figures

Model-based Methods

While producing trace figure is a common practice, especially for HCI researchers, surprisingly little work has been devoted to ease the production of such materials. The most commonly used method remains manual photo-tracing [START_REF] Chi | Authoring illustrations of human movements by iterative physical demonstration[END_REF][START_REF] Xie | Portraitsketch: Face sketching assistance for novices[END_REF] which can be described as follows. First, users stage the situation they want to illustrate using physical devices and other people standing in as actors, and take a photo of it. Then, they transfer this photo to a computer or a tablet, and open it as a background layer in an image editing software. Third, they sketch traces on top of the photo using their favourite input device and graphics editing software (usually Inkscape or Adobe Illustrator). Once the sketch is complete, they may add visuals such as overlaying an interface over a display or adding arrows, texts or contact points. Finally, they export the trace figure, most of the time as a vector graphic file so it can be resized at will. This manual photo-tracing workflow still suffers from several limitations. First, it is time consuming and relatively tedious. It also requires users to have devices as well as friends or colleagues available that can be used as models. It may also require users to build physical props, for instance to illustrate interaction with devices they do not actually own or that exist only as 3D models. Another limitation is that some "minor" modifications (for instance a change in hand posture) might require users to start the whole process from the beginning. Similarly, changing the angle of the illustration requires users to repeat the process with a new photo. Some of the vector graphics editing software provide tools to convert a photo into a drawing-like vector figure. However, these methods rely on juxtapositions of colour fills and result in a different visual quality than trace figures. Typically for a hand, the skin will result in several colour fills to recreate the gradient resulting of the lightning condition. Moreover, such an approach will vectorize the entire image, including background or elements that will ultimately be removed from the trace figure. A method letting the user perform local adjustment has thus been proposed [START_REF] Xie | Interactive vectorization[END_REF].

Edge detection algorithms, based on the seminal work by John Canny [START_REF] Canny | A computational approach to edge detection[END_REF], seem an alternative solution for tracing the contours of a model photography, but these algorithms usually fill pixels rather than producing a vector path, and may result in low-quality results depending on lighting conditions and quality of the source image. Mixed initiative [START_REF] Mortensen | Intelligent scissors for image composition[END_REF][START_REF] Neufeld | Mixed initiative interactive edge detection[END_REF] lets the human lead the edge detection, but still suffers from lighting conditions and blurry objects.

Specifying the contours of an object is also typical from rotoscoping technique6 used in animation, which consists in drawing on top of consecutive images (typically a video). The traditional workflow for rotoscoping however differs from the manual photo-tracing as it still consists in creating several closed shapes for each object in order to ease subsequent manipulation [START_REF] Li | Roto++: Accelerating professional rotoscoping using shape manifolds[END_REF]. As a result, tools specifically designed for easing rotoscoping, such as Roto++ [START_REF] Li | Roto++: Accelerating professional rotoscoping using shape manifolds[END_REF], are less suitable for producing trace figures.

The comic book drawing tool ClipStudio Paint7 could facilitate the production of trace figure when a photo model cannot be provided, since it provides 3D avatars that can be used as support to manually photo trace on top of them. However, this tool is mostly targeted at drawing characters and is not adapted to the illustration of HCI scenarios . Finally, DemoDraw [START_REF] Chi | Authoring illustrations of human movements by iterative physical demonstration[END_REF] captures whole body movements from a user through a Microsoft Kinect and produces a minimalist illustration that can be overlaid with arrow annotations or using stroboscopic effects. Esquisse extends beyond this earlier related work by supporting the easy creation of vector-based photo tracings of both body movements, gestures and input devices.

Staging-based Methods

2D staging can be used to produce illustrations similar to trace figures, typically by using cliparts found online or suggested by Google AutoDraw8 (a tool based on machine learning that retrieves clipart images based on approximate sketches drawn by the user) to rapidly produce trace figures without relying on a photo model. Those approaches require the appropriate cliparts (which are not necessarily available in vector format), and the 2D nature of clipart does not allow changes to correct the perspective of the figure which can be essential for illustrating interactive scenarios involving multiple users in a smart living room, or interaction techniques on a smartphone based on device tilting (for example, see Figures 1 in [START_REF] Lander | Gazeprojector: Accurate gaze estimation and seamless gaze interaction across multiple displays[END_REF] and [START_REF] Ruiz | Doubleflip: A motion gesture delimiter for mobile interaction[END_REF]).

SketchStudio is a 2.5D staging tool for prototyping animated design scenarios, based on body avatars and graph nodes that depict the journey of that avatar in space and time [START_REF] Kim | Sketchstudio: Experience prototyping with 2.5dimensional animated design scenarios[END_REF], scenes that can be played back through a dedicated viewing interface. There are, however, limitations when using this tool for the creation of photo traces. First, it is focused on large scale interactive scenarios involving a user that moves around devices, making it more difficult to use for fine interactions such as touch-based interaction on a smartphone. Furthermore, all interactive devices and interfaces must still be sketched, thus requiring drawing skills from the user, and the tool does not produce a vector-graphics rendering of the scene. Finally, several participants in an experiment conducted with SketchStudio mentioned that it becomes limited for ideas that need to be illustrated in 3D form, which is why Kim et al. suggest to improve their system to support the use of 3D models.

Finally, ComiPo! 9 is a design tool that relies on 3D models to make it possible to design manga-like comic books. 3D staging to produce 2D renderings here solves many problems associated with perspective. However besides the type of rendering, this tools could not be used for the production of trace figures for HCI because of the lack of support for aspects like the inclusion of interfaces or the production of vector format. Moreover, it does not use a camera system, which means that changing the perspective of a scene requires users to independently rotate all the objects of that scene.

Esquisse Workflow and Interaction

To use Esquisse the user starts Blender with the Esquisse add-on10 previously installed. We chose Blender as it is a free and cross-platform software widely used to model, animate and render 3D scenes. However, as a complete 3D modelling environment, Blender provides controls with many degrees of freedom that are not needed for illustration production, which is why we overrode most default controls with simpler interaction techniques specifically implemented for Esquisse. These techniques are located in a dedicated panel located on the left side of the Blender interface (see Figure 2, left). To create a vector graphics illustration with Esquisse, users stage a 3D scene using one of the pre-existing templates as starting point or manually adding 3D objects to the scene. For objects featuring a screen (e.g. a smartphone) they can optionally load an external file with a screenshot image of the interface, which gets automatically rendered as part of the screen of the selected device. They then position and align the objects using the specific interaction techniques of Esquisse built to ease the manipulation of articulated objects (and in particular simplifying the modification of hand postures), but they can still use default Blender controls if they prefer. Next they orient the viewport to the desired point of view. If wanted, they can add a stroboscopic effect to illustrate the motion of a finger, for example. Last they render the scene to create the trace figure as a vector-based SVG file. Optionally, they can tweak or add graphical elements using any vector graphics editing software like Inkscape or Illustrator. Note that these steps do not necessarily have to be performed in that specific order. In the following we detail each step of this workflow.

Choosing a Template and Objects

We identified in our taxonomy (C1 and C2) that many trace figures only vary in details, which is why Esquisse provides Templates with pre-arranged sets of people and objects used in these typical scenarios. Each Template defines a 3D scene in Blender whose objects are loaded in the scene currently opened, for example two hands holding a phone, a person interacting with a smartwatch, or two people around an interactive tabletop. Templates can be easily selected from the gallery of thumbnail images of all currently available templates (Figure 2, (1) Esquisse Library tab). We created Templates based on the most commonly used postures and devices from our taxonomy, but new templates can be easily added by saving a scene and adding it to the Esquisse library. In a similar way, users can complete a 3D scene by adding new objects (e.g., phones, avatars) from the object library of Esquisse. Custom 3D objects can obviously also be added to the scene using the import feature from Blender.

Adding GUIs in the Scene

Esquisse allows users to insert UIs (which was the case of 31 figures from our taxonomy, see C3) on 3D objects featuring a screen. A screen is a 3D plane object with a specific tag on which a user interface (defined in an external file) can be imported and displayed on.

Common objects with displays (smartphones, tablets, TVs, smartwatches and tabletops) are already provided in Esquisse with a defined screen area. It is also possible to add a screen to any other 3D object directly in Esquisse, by adding a screen object to the scene and setting the corresponding 3D object as its parent.

Facilitating Object Positioning

Simple objects like smartphones or tabletops can be positioned in the 3D scene easily using the 3-axis manipulator already available in Blender for translating, rotating and scaling the objects. However, when it comes to complex objects like a person's hand or body, manipulating the global position, rotation and scale of the combined object is not enough as these models are more complex and the position and orientation of each of their sub-objects (e.g., bones for a hand model) need to be modified. Esquisse provides rigged models that take into account child-parent relationships between bones. That being said, modifying a body or hand posture while keeping a coherent visual appearance can be a difficult and a time-consuming process for novice users [START_REF] Achibet | Thing: Introducing a tablet-based interaction technique for controlling 3d hand models[END_REF][START_REF] Wu | Hand modeling, analysis and recognition[END_REF]. In the following, we introduce techniques to simplify this task. Fig. 3: 1) A red anchor is added to the screen of the tabletop.

2) The index of the right hand is linked to the anchor.

3) The anchor is moved and the arm follows.

Anchors. We define an anchor as a point on an object that can be used to constrain the posture of another 3D object (e.g. a hand model). For example, anchors allow users to specify a contact point on a display, attach a specific finger of a hand model to it, and then to modify the location of this contact while preserving the kinematic constraints of the hand (i.e., Esquisse makes sure that the fingers are touching the anchor points with a realistic hand posture when reachable). Once in anchor mode, anchors can be added on any object (e.g. a screen) by clicking on the desired locations on the object. The user then links anchors to parts of another another object (e.g. fingertips of a hand). The anchors define constrains between the two objects that are then used by the Blender inverse kinematic solver to compute the position and orientation of the armature when the anchors are moved in 3D. Esquisse also provides a mode to move a linked object with the anchors, to avoid changing the current pose of the armature.

Fingers Flexion and Extension. The manipulation of non-anchored fingers may remain difficult [START_REF] Achibet | Thing: Introducing a tablet-based interaction technique for controlling 3d hand models[END_REF][START_REF] Wu | Hand modeling, analysis and recognition[END_REF], therefore Esquisse provides two specific controls for modifying hand poses. Inspired by Achibet et al. who control the pose of a virtual hand using sliders on a tablet [START_REF] Achibet | Thing: Introducing a tablet-based interaction technique for controlling 3d hand models[END_REF], we added slider controls to manipulate the flexion of every finger of our hand model. Changing the value of a slider updates the flexion of the corresponding finger in the 3D scene in real time by adjusting the orientation of each bone of the finger. This method allows users to rapidly modify hand poses, for instance to describe a mid-air gestural vocabulary.

We also implemented a LeapMotion integration so the hand posture can be demonstrated. Similarly, body postures could be demonstrated using a Kinect like in DemoDraw [START_REF] Chi | Authoring illustrations of human movements by iterative physical demonstration[END_REF].

Snap to Camera Point of View

In Blender cameras can be moved and rotated like any other object. As rotations can be difficult to perform, we implemented a feature to snap the camera object to the current viewport position. In this way the user can simply move the viewport to the desired point of view and then 'teleport' the camera so it matches its location and orientation.

Stroboscopic Effect

Esquisse allows users to generate stroboscopic figures, used to convey the movement of objects over time [START_REF] Mccloud | Understanding Comics: The Invisible Art[END_REF], by rendering each step with an increasing amount of transparency (C7 in our taxonomy). Once the scene is set up (Figure 4, top left), the user can enter in stroboscopic mode by clicking on the appropriate button in the interface. This allows users to define different keyframes, each saving the positions of all the current objects in the scene. Esquisse uses keyframes to detect the objects that moved and create a version of the corresponding objects (i.e. a copy of the objects displayed in wireframe) as illustrated Figure 4, top right (a keyframe version of the anchor and the linked hand are created when the anchor is moved). Keyframe objects can also be manipulated in the scene if necessary. Additional frames can be defined between keyframes in Esquisse using linear interpolation (see Figure 4, bottom left, where two steps are defined using interpolation).

All of the presented techniques in this section are designed to allow users inexperienced with 3D modelling softwares to rapidly stage a scene with 3D models. Most importantly, the techniques allow rapid iteration and experimentation (e.g., quickly changing the posture of a hand or camera view of the scene), something that is not possible to do when manually creating trace figures.

Esquisse Rendering Process

From the 3D scene, Esquisse is rendering vector images focusing on the contours of the objects. One important requirement of our rendering approach is to create closed contours only, so users can modify if they want the rendered objects in a vector graphics editing software afterwards (e.g. moving objects or modifying the colour or opacity of an object).

A first possible approach consists in propagating virtual points along the edges of an object mesh, by considering their visibility, to form the contours of the 3D object [START_REF] Karsch | Snaxels on a plane[END_REF]. Unfortunately, this technique requires a high mesh density to accurately compute meshes' visibility, which yields to time consuming renderings. A second approach [START_REF] Grabli | Programmable style for npr line drawing[END_REF] consists in building a view map assigning properties to edges and then extracting contours by selecting specific edges based on their nature and visibility in order to chain them to form strokes. Unfortunately, extracted contours are split in several strokes which can be problematic to produce accurate polygons filling in a vector-based format. A third approach consists in creating layers containing full objects with the most effective cuts [START_REF] Eisemann | A visibility algorithm for converting 3d meshes into editable 2d vector graphics[END_REF]. This facilitates the edition of SVGs in a graphics editing software but at a cost of longer rendering times to compute the depth order of the different layers.

As a result we chose to adapt the approach proposed by Eisemann et al. [START_REF] Eisemann | Stylized vector art from 3d models with region support[END_REF] which provides fill regions support by using the 2D arrangement package of the CGAL11 library to extract 2D regions formed by 2D strokes. In that way, it is possible to extract at the same time line contours and fill polygons.

Esquisse 3D to SVG Rendering

This section explains how paths are calculated and how the final SVG rendering is performed.

From 3D to 2D paths We adapted the two approaches introduced in [START_REF] Eisemann | Stylized vector art from 3d models with region support[END_REF][START_REF] Grabli | Programmable style for npr line drawing[END_REF] to our needs and implemented them in Blender as follows.

Step 1: Computing a view map for the scene Similarly to [START_REF] Eisemann | Stylized vector art from 3d models with region support[END_REF][START_REF] Grabli | Programmable style for npr line drawing[END_REF], the first step iterates over all the edges of the objects to build a view map of the scene, by characterizing the nature of each edge (crease, silhouette, etc.) as well as its visiblity (visible or hidden). We use the Freestyle implementation already available as an extension in Blender.

Step 2: Selecting and grouping edges of interest Second step consists in organizing the edges by selecting all the edges that correspond to a silhouette, contour or a crease, and to group them depending on their visibility. Note that keeping hidden edges is crucial as it can be required to illustrate some interactive scenarios (typically instances of back-of-device interaction).

Step 3: Computing and associating filling regions Once all the edges of interest of the different objects have been grouped, we compute the regions formed by the 2D projection of the visible ones. As [START_REF] Eisemann | Stylized vector art from 3d models with region support[END_REF], we use the 2D arrangement package provided by CGAL, which provides the regions formed by the 2D projection of the edges.

Step 4: Associating 2D regions to their corresponding 3D objects We associate a region to its corresponding object in the scene by picking for a random point inside the region (using the GPC library 12 ) and raycasting this point to the 3D scene to identify the corresponding 3D object. This step is used to group regions of a same object, as well as select a default filling colour for each region.

From Paths to SVG rendering The SVG file produced by Esquisse comprises two main layers, one for fillings and visible strokes, and a second for hidden strokes (which must be drawn on top of fills to be visible). The first layer contains one sub-layer per object grouping all its fillings and visible strokes, which eases the post-editing using other softwares. The line style used for each type of contour, as well as the colour of each object can also be specified by the user in the Esquisse interface. Filled contour layers are produced to avoid stroke layers from overlapping.

Generating filled contours containing holes. To appear as a hole, the points of the inside contour have to be oriented counter-clockwise while the points of the outer contour should be clockwise 13 for a non-zero fill rule. As CGAL 2D arrangement package returns regions under a hierarchy, regions inside other regions can be considered as holes and thus, be drawn in a counter-clockwise way.

Projecting UIs on screens. Our algorithm also needs to project possible images of graphical user interfaces on their corresponding screens in the 3D scene. For that, we use numpy linear algebra solver to compute the planar homography from the four corners of the user interface to the four corners of the screen object in the scene. However, considering SVG does not currently support perspective matrix transformations, we apply the homography to all the geometric objects of the user interface by computing the new coordinates. Some elements like ellipses, arcs or text first need to be discretized into segments or Bezier curves in order to be projected. All the projected elements are then grouped and a clipping path is applied to this group using the visible contours of the screen object, in order to avoid overlapping artefacts (e.g. a finger in front of the smartphone's display).

Rendering a stroboscopic figure. To render a stroboscopic figure, we adapt the rendering pipeline as follows. First, it computes the four rendering steps for each keyframe. Then it iterates over these keyframes and computes the SVG rendering for an object only if it has moved since the previous keyframe.

Doing multiple renderings implies having multiple contours for some of the objects (keyframes and final), and thus, requires to carefully choose the z-index of each object in the SVG file.

First, all objects that did not move in the scene are positioned with a low z-index. Then, we iterate over each keyframe and draw its objects with increased transparency and z-index .

Note that these modifications marginally deter rendering time, which remains below 5 seconds for the Figures 3 and4, when running on the i7 4GHz computer described in the study section.

Study: Illustrating Interactions

We evaluated Esquisse by asking HCI students and researchers to produce visual illustrations of interaction techniques from the literature using our tool.

Method

Participants and apparatus. We recruited 8 participants (x=33, σ=10), all researchers in HCI. Three were academic researchers, three PhD students and two Post-graduate students. None of these participants had previous experience with the Blender software. The experiment was conducted with Blender v2.79 with the Esquisse add-on installed, running on an iMac 27' 5K display with i7 4Ghz. Three input devices were available: a Logitech G9 Laser computer mouse, an Apple Magic Trackpad 2 and a LeapMotion. Adobe Illustrator and Inkscape were also installed and available to use at anytime if the participants wanted to complete the vector graphics file produced with Esquisse.

Procedure. Participants were invited to sit in front of the computer and were instructed that the experiment consisted in producing trace figures. We first showed them a set of trace figures extracted from the taxomony to clearly explain what trace figures are. After this introduction, we introduced the main task which consisted in illustrating one interaction technique from a set of four published in the HCI community (AuraSense [START_REF] Zhou | Aurasense: Enabling expressive around-smartwatch interactions with electric field sensing[END_REF], Put-that-there [START_REF] Bolt | put-that-there": Voice and gesture at the graphics interface[END_REF], TiltReduction [START_REF] Chang | Understanding users' touch behavior on large mobile touch-screens and assisted targeting by tilting gesture[END_REF] and Stitching [START_REF] Hinckley | Stitching: Pen gestures that span multiple displays[END_REF]) that were described using the original accompanying videos. We chose these interaction techniques because they rely on a variety of devices (e.g. smartphone, smartwatch, large display) and input modalities (device motion, touch, skin and speech input).

Participants were first presented with a 10 minutes long video explaining Blender basic controls and Esquisse features, and were then given 30 minutes to illustrate one interaction using Esquisse. They were also told that they could edit the produced SVG file afterwards with a graphics editing software.

Since the experiment's main focus was not the production of 2D interfaces, we provided a set of 2D interfaces associated to the 4 interaction techniques, to be used as screen interfaces. We measured the time it took participants to create the tracing figure (up to 30 minutes) and made observer notes about the strategy used by each participant. This experiment employed a think aloud protocol [START_REF] Lewis | Task-centered user interface design[END_REF] encouraging participants to comment on Esquisse while producing the illustration. Figures produced by the participants can be found as additional material to this paper.

Interaction and Strategy in Esquisse

Templates. All participants but two started their illustration using one of the predefined templates. Interestingly, the two participants who did not [P3, P8] were producing illustrations for Stitching which consists of a pen gesture spanning over two interactive tablets, a situation for which Esquisse does not provide a template for. Both P3 and P8 manually added two mobile devices and one right hand with a stylus and placed them in the scene. In the other cases, Esquisse provides predefined templates close enough to the interactions to illustrate.

Anchors. As for templates, all participants used anchors except the two participants who had to illustrate Stitching [P3, P8]. In this case, all participants adopted a similar workflow: they simply moved the right hand with the stylus over the two devices on an axis without using anchors. Interestingly, one of these participants wanted to anchor the stylus [P8], which is not available in Esquisse but could be quickly implemented. His idea was to put an anchor on the tablet screen, then link the anchor to the stylus tip, and so, moving the stylus and the hand at the same time when moving the anchor. Overall, all participants understood and adopted the use of anchors very quickly.

Stroboscopic effect. All participants but one used the stroboscopic feature of Esquisse in order to illustrate motion. Two of them [P1,P2] who had to illustrate AuraSense used the interpolation feature in order to generate additional frames between the two defined keyframes. Once again, these participants exhibited a similar workflow, positioning the right hand with an anchor, adding a keyframe, moving the right hand to a different position and then set the interpolations. The participant who did not use the stroboscopic effect [P5], considered himself as figure expert, and did it intentionally to build instead a storyboard-like figure for TiltReduction using 3 distinct illustrations. 3D manipulations. All participants but two used the anchoring system and the 3axis translation manipulator to make all the displacements they wanted, without expressing difficulties. The only two participants [P5,P6] who rotated objects during staging had to illustrate TiltReduction, which involves a rotation from the wrist to tilt a smartphone. One of them [P6] was the only participant who had difficulties with Esquisse and failed to create what he wanted, commenting that "3D manipulations are too difficult for me". That being said, he ignored easier alternative strategies that could be used to rotate objects, such as anchoring all the fingers to force the hand pose, only move the camera to a different point of view, or to use the Leap Motion. The latter was adopted by [P5] to more easily change the hand orientation. Overall, only two participants used the Leap Motion for changing the hand posture, the other one [P2] was illustrating AuraSense and used it to define an index pointing posture for the right hand. Finally, all the participants used the camera snapping functionality and no one moved using the 3-axis manipulator.

SVG post-editing. While all participants were invited to do so, only three participants [P4,P5,P7] post-edited the figure produced with Esquisse in a vectorgrahics editing software. While two performed only minor adjustments, [P5] built a 3 images storyboard and overlaid an arrow depicting motion over one figure.

Participants Subjective Feedback.

Learning and use. Overall, participants appreciated Esquisse, reporting that it was "easy to use and fun" [P4, P5, P8] and "fast" [P5, P7, P8], even if Esquisse requires a learning phase for objects manipulation and Blender interface [P1, P3, P8]. Participants quickly understood all the functionalities by just watching the 10 minute tutorial video [P1, P3, P4, P5]. Even better, [P1] was "impressed" and said it was "fast to learn and master the different functionalities", making Esquisse "interesting considering [his] poor artistic skills". Post editing. Globally, participants were satisfied with the Esquisse rendering results, but some still prefer to refine the figure afterwards in a graphics editing software [P4, P5, P7]. More importantly, participants saw Esquisse as a rapid prototyping tool "for making quick illustrations using complex objects to be modified afterwards" [P5, P7].

Improvements. Participants were enthusiastic with Esquisse and commented on several additional features that could enrich its functionalities. [P2] commented that the capacity to control any object of the scene using motion sensing (as Yoon et al. did with a smartphone [START_REF] Yoon | Mobiature: 3d model manipulation technique for large displays using mobile devices[END_REF]) could be useful to make 3D staging even easier. [P4] would have liked to identify the keyframes objects in the scene, for example by using a different colour or a number associated to the keyframe index. [P8] commented that the ability to modify a User Interface file within Esquisse directly in the scene would optimize the workflow. Finally, two participants [P5, P8] commented that the capacity to overlay arrows "between here and there" directly within Esquisse, either using the anchors or optionally displaying arrows between the keyframes, would remove the need to open the produced SVG file in a graphics-editing software afterwards. These suggested improvements are not challenging and will be implemented in the future versions of Esquisse.

Discussion and Conclusion

Trace figures are powerful and frequently used materials for illustrating HCI research papers. Based on a characterization of trace figures used in the HCI community, we designed Esquisse, a tool that implements a novel workflow based on 3D objects manipulation to stage a 3D scene and export it as a vector trace figure. We contributed interaction techniques to facilitate this workflow (including the use of anchor points to help the manipulation of complex articulated objects such as hands and the integration of stroboscopic effects) and a rendering pipeline to extract the different contours, fill them and finally generate a vector-based SVG file. We implemented Esquisse as an add-on for the open source 3D modelling software Blender and evaluated its usability in a qualitative experiment with 8 participants. The results of this experiment suggest that users, even when not familiar with Blender nor used to produce trace figures, managed to quickly produce trace figures illustrating interaction techniques from the literature with little to no experience in the production of trace figures or use of a 3D modelling software.

Esquisse thus provides an alternative workflow to produce trace figures, that can be used by users who believe they do not have the skills required to perform manual photo-tracing. Esquisse can also benefit users who usually rely on manual photo-tracing, for instance, as a rapid-prototyping tool as reported by participants in our experiment. A 3D scene staged with Esquisse can also be exported as is as a model for manual photo-tracing, which could be useful in situations where one has to illustrate a "complex and heavy" interactive scenario (for instance involving tabletops, large displays, several users, etc.) without having to prepare the physical setup required to take a photo of the scene.

There are limitations when using Esquisse. Typically, while adding models to Esquisse is as easy as adding a scene to its template sub-folder, designing these templates still need basic 3D modeling and staging skills. We anticipate that in the future, progress in computer vision and computer graphics research will allow to extract 3D objects from a photography to automatically create templates [START_REF] Zheng | Interactive images: cuboid proxies for smart image manipulation[END_REF][START_REF] Chen | 3-sweep: Extracting editable objects from a single photo[END_REF][START_REF] Kholgade | 3d object manipulation in a single photograph using stock 3d models[END_REF].

An aspect of Esquisse that can be seen as both an advantage or a drawback is that it has been implemented as a Blender add-on. We made this decision because Blender provides a solid environment for 3D modelling and object manipulation that Esquisse benefits from, as well as because it simplifies its distribution and maintenance. Because of this, however, the interaction with Esquisse is constrained by what the Blender environment allows add-ons to do (e.g., the design of the user interface for add-ons is limited). In that respect, we designed Esquisse by trying to provide the best user experience and interaction that Blender allowed us to design. For example, we added dedicated slider controls to ease the definition of hand and body poses and implemented a direct LeapMotion integration to help users to manipulate hand poses. Similarly, inspired by DemoDraw [START_REF] Chi | Authoring illustrations of human movements by iterative physical demonstration[END_REF], we plan to implement a Microsoft Kinect integration to ease the manipulation of body poses.

Most trace figures overlay meta annotations (such as texts or arrows). Besides contact points, Esquisse does not currently support a way to add these annotations and the user still has to open the produced SVG file in a graphic editing software to add them afterwards. However, meta annotation are usually simple geometric shapes or text layers that should be straightforward to integrate in the add-on. Adding meta-annotation support to Esquisse could be added by mimicking how anchors are currently added: the meta-annotation would be a shape or text that would be positioned over an invisible plan that would not be rendered when the SVG file is produced.

We hope our open-source release of Esquisse will help the production of trace figures that are gaining popularity in the HCI community as they are effective in capturing the essence of interactive scenarios.

Fig. 1 :

 1 Fig. 1: Workflow of Esquisse: (left) facilitating staging of 3D scenes with templates, anchor points, direct UI import, kinematic manipulation and automated posture tracking, (center) Esquisse's algorithm rendering the tracing images, and (right) final vector-based trace figures.

Fig. 2 :

 2 Fig. 2: Blender with the Esquisse add-on. All controls specific to Esquisse are located in a dedicated panel located on the left side of the interface (1).The right side shows the 3D view of the scene with several objects from the Esquisse library such as a SmartWatch with its GUI (2) and hand models (3)), and the frame of the current camera view (4).

4 Fig. 4 : 1 )

 441 Fig.4:1) The index of the right hand is linked to a red anchor. 2) As soon as the hand moves in stroboscopic mode (a), a wireframe version of the object is created (b). 3) Esquisse rendering of the scene. 4) Esquisse rendering of the scene when 2 additional frames are defined by interpolation between the two keyframes.

1 .

 1 Demonstration of gestures (64): this most common type of trace figure illustrates a hand or body gesture (e.g., swiping, pressing, turning). Trace figures work well to clearly illustrate the accurate postures of hands or a person's body ([13, fig 13], [29, fig 1]). 2. Overview of system setup or assembly (26): these illustrations show, for example, the setup of tracking cameras, the setup of hardware (e.g., [9, fig 1d]) or the technical assembly of a wearable device. 3. Interaction sequences (14): these sequences show multiple frames of an interaction with a system (e.g., key steps of the interaction with a screen

	figures (e.g., [22, fig 1]) include traces lines delimiting the size of a room, or
	showing furniture and other objects in the environment. Since an important
	goal of photo traces is to reduce visual clutter, it seems that most figures
	strictly limit the traced details.
	-C5 -Use of colour: photo traces can be pure black-and-white line draw-
	ings (34) but many include colour: 45 drawings used coloured areas within
	the drawing (e.g., solid fill of a person's hand in a skin-coloured tone), and
	58 drawings used colour for making annotations and labels that stand out
	against the black and white trace figure (e.g., coloured arrows on top of the
	drawing, or coloured text labels).
	-C6 -Annotations: most of the trace figures (121) include meta anno-
	tations such as labels, text descriptions, arrows or motion path lines. Most
	common annotations (besides text labels) are arrows (63) and touch contact
	point visualisations (37), for example by showing a coloured circle at the
	position where a person's fingers are touching the screen ([13, fig 13] and
	interface). [16, fig 3]).
	4. Design space illustrations (13): this can be a technical design space -C7 -Static vs dynamic: most figures depict a static scene (e.g., a single (e.g., variations of a tangible form factor) or a design space of gestures (e.g., moment in time, a static setup), but a small number of figures (6) were de-a collection of 8 different hand postures). signed for illustrating motion or movement (e.g., moving arms for a body ges-5. Other (7): this includes any other uses of trace figures, for examples as part ture). Those usually used stroboscopic effect, where previous states/positions of tables, flow diagrams, etc. are drawn in different colours or line styles. McAweeney et al. made the
	same observation in their taxonomy focused on how gestures can be repre-By continuing our analysis and coding, we further identified the following characteristics of trace figure illustrations: sented [26].
	-C8 -Use of perspective: 55 trace figures in 43 papers use some sort -C1 -Person's body, hands or fingers: the most common drawn element of perspective (e.g., [25, fig 2] and [22, fig 1]) , which can be required to across all figures was a person's hand (total of 218 drawings of a person's illustrate specific interactive scenarios (e.g. users around a table top, device hand, often multiple per figure, in 43 papers). This corresponds to the high number of figures in HCI papers demonstrating gestures ([9, fig 1d]). A tilting).
	person's body (or most of the body, like the upper torso) was drawn as part
	of figures 158 times across 22 papers. Individual fingers were drawn 51 times
	in 7 papers ([13, fig 13]) and a person's head (without rest of the body) 16
	times (in 5 papers).
	-C2 -Devices and objects: phones/tablets (32) and wearable devices
	such as smartwatches (20) were the most commonly drawn devices in our
	sample. 37 of the trace figures included some kind of tangible devices or
	other physical objects (e.g. active tokens, door handles). Other less frequently
	drawn objects and devices included: white boards and interactive tabletops
	(12), VR/AR headsets (7), tracking cameras (4), and car interiors (2) for
	automotive UI interaction.
	-C3 -Screen user interfaces: 31 of the trace figures included screenshots
	of graphical user interfaces. For example, screenshots show the interface el-
	ements on mobile phones or smartwatch screens (see screenshots embedded
	in [13, fig 13] and [16, fig 3]).
	-C4 -Environment: most photo traces (116) do not include any drawn
	details of the physical environment (e.g., background, furniture). Only 8

LeapMotion -https://www.leapmotion.com/

Github Esquisse -http://ns.inria.fr/loki/esquisse/

Rotoscoping -https://en.wikipedia.org/wiki/Rotoscoping

ClipStudio Paint -https://www.clipstudio.net/en/

AutoDraw -https://www.autodraw.com/

ComiPo! -https://www.comipo.com/

Esquisse on GitHub -http://ns.inria.fr/loki/esquisse/

https://www.cgal.org

http://www.cs.man.ac.uk/ ∼ toby/gpc/

https://www.w3.org/TR/SVG/painting.html


Miguel Couceiro

Jimmy Devillet

Jean-Luc Marichal

Pierre Mathonet

REDUCIBILITY OF n-ARY SEMIGROUPS: FROM QUASITRIVIALITY TOWARDS IDEMPOTENCY

Keywords: 2010 Mathematics Subject Classification. Primary 20M10, 20N15; Secondary 16B99, 20K25 Semigroup, polyadic semigroup, Abelian group, reducibility, quasitriviality, idempotency

Let X be a nonempty set. Denote by F n k the class of associative operations F ∶ X n → X satisfying the condition F (x 1 , . . . , xn) ∈ {x 1 , . . . , xn} whenever at least k of the elements x 1 , . . . , xn are equal to each other. The elements of F n 1 are said to be quasitrivial and those of F n n are said to be idempotent. We show that

The class F n 1 was recently characterized by Couceiro and Devillet [2], who showed that its elements are reducible to binary associative operations. However, some elements of F n n are not reducible. In this paper, we characterize the class F n n-1 ∖ F n 1 and show that its elements are reducible. In particular, we show that each of these elements is an extension of an n-ary Abelian group operation whose exponent divides n -1.

INTRODUCTION

Let X be a nonempty set, let X be its cardinality, and let n ≥ 2 be an integer. An n-ary operation F ∶ X n → X is said to be associative if F (x 1 , . . . , x i-1 , F (x i , . . . , x i+n-1 ), x i+n , . . . , x 2n-1 ) = F (x 1 , . . . , x i , F (x i+1 , . . . , x i+n ), x i+n+1 , . . . , x 2n-1 ), for all x 1 , . . . , x 2n-1 ∈ X and all 1 ≤ i ≤ n -1. The pair (X, F ) is then called an n-ary semigroup. This notion actually stems back to Dörnte [START_REF] Dörnte | Untersuchungen über einen verallgemeinerten Gruppenbegriff[END_REF] and has led to the concept of n-ary group, which was first studied by Post [START_REF] Post | Polyadic groups[END_REF].

In [START_REF] Dudek | On n-ary semigroups with adjoint neutral element[END_REF] the authors investigated associative n-ary operations that are determined by binary associative operations. An n-ary operation F ∶ X n → X is said to be reducible to an associative binary operation G∶ X 2 → X if there are G m ∶ X m+1 → X (m = 1, . . . , n -1) such that G n-1 = F , G 1 = G, and G m (x 1 , . . . , x m+1 ) = G m-1 (x 1 , . . . , x m-1 , G(x m , x m+1 )), m ≥ 2.

The pair (X, F ) is then said to be the n-ary extension of (X, G). Also, an n-ary operation F ∶ X n → X is said to be • idempotent if F (x, . . . , x) = x for all x ∈ X,

• quasitrivial if F (x 1 , . . . , x n ) ∈ {x 1 , . . . , x n } for all x 1 , . . . , x n ∈ X. We observe that any quasitrivial n-ary operation is idempotent. However, the converse is not true. For instance, the ternary operation F ∶ R 3 → R defined by F (x, y, z) = x -y + z is idempotent but not quasitrivial.

Recall that an element e ∈ X is said to be neutral for F ∶ X n → X if F ((k -1) ⋅ e, x, (n -k) ⋅ e) = x, x ∈ X, k ∈ {1, . . . , n}.

Here and throughout, for any k ∈ {1, . . . , n} and any x ∈ X, the notation k ⋅ x stands for the k-tuple x, . . . , x. For instance, we have

F (3 ⋅ x, 0 ⋅ y, 2 ⋅ z) = F (x, x, x, z, z).
We also denote the set of neutral elements for an operation F ∶ X n → X by E F . The quest for conditions under which an associative n-ary operation is reducible to an associative binary operation gained an increasing interest since the pioneering work of Post [START_REF] Post | Polyadic groups[END_REF] (see, e.g., [START_REF] Ackerman | A characterization of quasitrivial n-semigroups[END_REF][START_REF] Couceiro | Every quasitrivial n-ary semigroup is reducible to a semigroup[END_REF][START_REF] Devillet | Characterizations of quasitrivial symmetric nondecreasing associative operations[END_REF][START_REF] Dudek | On n-ary semigroups with adjoint neutral element[END_REF][START_REF] Kiss | Associative idempotent nondecreasing functions are reducible[END_REF][START_REF] Lehtonen | On associative operations on commutative integral domains[END_REF]). For instance, Dudek and Mukhin [5, Theorem 1] proved that an associative operation F ∶ X n → X is reducible to an associative binary operation if and only if one can adjoin to X a neutral element e for F ; that is, there is an n-ary associative operation F ∶ (X ∪ {e})

n → X ∪ {e} such that e is a neutral element for F and F X n = F . In this case, a binary reduction G e of F can be defined by

G e (x, y) = F (x, (n -2) ⋅ e, y) x, y ∈ X.
Also, it was recently observed [2, Corollary 2.3] that all the quasitrivial associative n-ary operations are reducible to associative binary operations. On the other hand, the associative idempotent ternary operation F ∶ R 3 → R defined by F (x, y, z) = x -y + z is neither quasitrivial nor reducible (see, e.g., [START_REF] Szendrei | Clones in Universal Algebra[END_REF] or more recently [START_REF] Marichal | A description of n-ary semigroups polynomial-derived from integral domains[END_REF]).

In this paper, we are interested in studying conditions under which an idempotent nary semigroup is reducible to a semigroup. The observations above lead us to investigate certain subclasses of idempotent n-ary semigroups containing the quasitrivial ones, for instance by requiring the condition

F (x 1 , . . . , x n ) ∈ {x 1 , . . . , x n }
to hold on at least some subsets of X n . More precisely, for every set S ⊆ {1, . . . , n}, we define D n S = {(x 1 , . . . , x n ) ∈ X n ∶ x i = x j , ∀i, j ∈ S}. Also, for every k ∈ {1, . . . , n}, we set

D n k = ⋃ S⊆{1,...,n} S ≥k D n S = ⋃ S⊆{1,...,n} S =k D n S .
Thus, the set D n k consists of those tuples of X n for which at least k components are equal to each other. In particular, D n 1 = X n and D n n = {(x, . . . , x) ∶ x ∈ X}. For every k ∈ {1, . . . , n}, denote by F n k the class of those associative n-ary operations F ∶ X n → X that satisfy

F (x 1 , . . . , x n ) ∈ {x 1 , . . . , x n }, (x 1 , . . . , x n ) ∈ D n k .
We say that these operations are quasitrivial on D n k . Thus defined, F n 1 is the class of quasitrivial associative n-ary operations and F n n is the class of idempotent associative n-ary operations. Since the sets D n k are nested in the sense that

D n k+1 ⊊ D n k for 1 ≤ k ≤ n -1, the classes F n k clearly form a filtration, that is, F n 1 ⊆ F n 2 ⊆ ⋯ ⊆ F n n . It is easy to see that F n 1 = F n 2 = ⋯ = F n n if X ≤ 2.
Quite surprisingly, we have the following result, which shows that this filtration actually reduces to three nested classes only. The proof is given in the next section.

We observe that the class F n 1 = F n 2 = ⋯ = F n n-2 was characterized by Couceiro and Devillet [START_REF] Couceiro | Every quasitrivial n-ary semigroup is reducible to a semigroup[END_REF] who showed that all its elements are reducible. In particular, we have the following result. Proposition 1.2 (see [START_REF] Couceiro | Every quasitrivial n-ary semigroup is reducible to a semigroup[END_REF]Corollary 3.11]). An operation F ∶ X n → X is associative, quasitrivial, and has at most one neutral element if and only if it is reducible to an associative and quasitrivial binary operation G∶ X 2 → X. In that case, we have G(x, y) = F (x, y, . . . , y) for any x, y ∈ X.

Remark 1. We observe that the class of associative and quasitrivial operations G∶ X 2 → X was characterized in [9, Theorem 1].

In this paper, we provide a characterization of the class F n n-1 ∖ F n 1 and show that all its elements are also reducible to binary associative operations. This result is stated in Theorem 1.5 and Corollary 1.6. The proofs of these results are given in the next section.

Recall that an n-ary groupoid is a set equipped with an n-ary operation. Moreover, two n-ary groupoids (X, F ) and (Y, F ′ ) are said to be isomorphic if there exists a bijection φ∶ X → Y such that

φ(F (x 1 , . . . , x n )) = F ′ (φ(x 1 ), . . . , φ(x n )),
for every x 1 , . . . , x n ∈ X. In that case, the operations F and F ′ are said to be conjugate to each other.

The exponent of a group (X, G) with neutral element e is the smallest integer m ≥ 1 such that G m-1 (m ⋅ x) = e for any x ∈ X. Otherwise, (X, G) is said to have zero exponent. Remark 2. A group (X, G) has an exponent dividing n if and only if G n ((n + 1) ⋅ x) = x for any x ∈ X.

Let us recall the following important result, due to Prüfer and Baer (see, e.g., [12, Corollary 10.37]). Proposition 1.3 (see [START_REF] Rotman | An Introduction to the Theory of Groups. 4th Ed[END_REF]Corollary 10.37]). If (X, G) is an Abelian group of bounded exponent, then it is isomorphic to a direct sum of cyclic groups.

The following immediate corollary provides a characterization of the class of Abelian groups with nonzero exponents.

Corollary 1.4. Let m ≥ 1 be an integer. An Abelian group (X, G) is of exponent m if and only if it is isomorphic to a direct sum of cyclic groups whose exponent is m.

Recall that an element a ∈ X is said to be an

annihilator for F ∶ X n → X if F (x 1 , . . . , x n ) = a whenever a ∈ {x 1 , . . . , x n }. Theorem 1.5. Suppose that F n n-1 ∖ F n 1 ≠ ∅. An associative operation F is in F n n-1 ∖ F n 1
if and only if there exists a unique subset Y ⊆ X, with Y ≥ 3, such that the following assertions hold. (c') For any y ∈ Y and any x 1 , . . . , x n-1 ∈ X we have

F (x 1 , . . . , x n-1 , y) = F (x 1 , . . . , y, x n-1 ) = ⋯ = F (y, x 1 , . . . , x n-1 ).
(c") For any k ∈ {1, . . . , n -1}, any y 1 , . . . , y k ∈ Y , and any x 1 , . . . , x n-k ∈ X ∖ Y we have

F (y 1 , . . . , y k , x 1 , . . . , x n-k ) = F (x 1 , . . . , x i-1 , (k + 1) ⋅ x i , x i+1 , . . . , x n-k ), i ∈ {1, . . . , n -k}.
The proof is a little tedious but straightforward.

Corollary 1.6. Every operation in F n n-1 is reducible to a binary associative operation. A reformulation of Theorem 1.5 based on binary reductions is given in the following corollary.

Corollary 1.7. Suppose that F n n-1 ∖ F n 1 ≠ ∅. An operation F is in F n n-1 ∖ F n 1 if
and only if it is reducible to an associative operation G∶ X 2 → X and there exists a unique subset Y ⊆ X, with Y ≥ 3, such that the following conditions hold.

(a

) (Y, G Y ) is an Abelian group whose exponent divides n -1. (b) G (X∖Y ) 2 is quasitrivial. (c) Any x ∈ X ∖ Y is an annihilator for G ({x} ⋃ Y ) 2 . Moreover, we have that Y = E F .
Corollary 1.7 is of particular interest as it allows us to easily construct n-ary operations in

F n n-1 ∖ F n 1 .
For instance, for any integers n ≥ 3 and p ≥ 1, the operation associated with any (np + 1)-ary extension of

(Z n , +) is in F np+1 np ∖ F np+1 1
by Corollary 1.7. To give another example, consider the chain (X, ≤) = ({1, 2, 3, 4, 5}, ≤) together with the operation G∶ X 2 → X defined by the following conditions:

• ({1, 2, 3}, G {1,2,3} 2 ) is isomorphic to (Z 3 , +), • G {4,5} 2 = ∨ {4,5} 2
, where ∨∶ X 2 → X is the maximum operation for ≤,

• for any x ∈ {1, 2, 3}, G(x, 4) = G(4, x) = 4 and G(x, 5) = G(5, x) = 5. Then for any integer p ≥ 1 we have that the operation associated with any (3p + 1)-ary extension of ({1, 2, 3, 4, 5}, G) is in F 3p+1 3p ∖ F 3p+1 1 , again by Corollary 1.7. We also have the following corollary which follows from Theorem 1.5.

Corollary 1.8. Let n ≥ 3 and assume that any of the two following conditions holds.

• n = 3 and X ≥ 4.

• n ≥ 4 and X ≥ n -1.

Then F n 1 ⊊ F n n-1 . For instance, consider the operation F ∶ X 3 → X defined on X = Z 2 2 by F (x 1 , x 2 , x 3 ) = x 1 + x 2 + x 3 (mod 2),
where (mod 2) is understood componentwise. Then, for any x, y ∈ Z 2 2 , we have F (x, x, y) = y, and hence F ∈ F 3 2 . But we have

F 1 0 , 0 1 , 0 0 = 1 1 ,
which shows that F ∉ F 3 1 . However, the converse of Corollary 1.8 does not hold in general. For instance, the operation associated with the 7-ary extension of (Z 3 , +) is in F 7 6 ∖ F 7 1 . However, we have that Z 3 = 3.

Moreover, we observe that F n n-1 ⊊ F n n . For instance, if (X, ≤) is a lattice that is not a chain, then the ternary operation F ∶ X 3 → X defined by F (x, y, z) = x ∨ y ∨ z is in F 3 3 . However, it is not in F 3 2 since F (x, x, y) ∉ {x, y} whenever x and y are not comparable, i.e, x ∨ y ∉ {x, y}.

In proving Theorem 1.5 we will make use of the following characterization of the class of associative operations F ∶ X n → X for which the elements of X are all neutral. Theorem 1.9. Let F ∶ X n → X (n ≥ 3) be an associative operation. Then E F = X if and only if (X, F ) is the n-ary extension of an Abelian group whose exponent divides n -1.

Recall from [5, Lemma 1] that if an associative operation F ∶ X n → X has a neutral element e, then it is reducible to the associative operation G e ∶ X 2 → X defined by [START_REF] Ackerman | A characterization of quasitrivial n-semigroups[END_REF] G e (x, y) = F (x, (n -2) ⋅ e, y), x, y ∈ X.

We observe that e is the unique neutral element of G e .

Using this result, we can also show that all reductions of an associative operation F ∶ X n → X obtained from neutral elements are conjugate to each other. For instance, the ternary sum on Z 2 has two neutral elements, namely 0 and 1. By [5, Lemma 1] it is reducible to the operations G 0 , G 1 ∶ Z 2 2 → Z 2 2 defined by G 0 (x, y) = x + y (mod 2) and G 1 (x, y) = x + y + 1 (mod 2). It is easy to see that the semigroups (Z 2 , G 0 ) and (Z 2 , G 1 ) are isomorphic.

Proposition 1.10. Let F ∶ X n → X (n ≥ 3) be an associative operation and let e 1 , e 2 ∈ E F . Then (X, G e1 ) and (X, G e2 ) are isomorphic.

The proofs of the results above are given in Section 2. In Section 3, we discuss an alternative hierarchy, which provides variants of Theorem 1.5 and Corollary 1.7.

TECHNICALITIES AND PROOFS OF THE RESULTS

Let us start by providing the proofs of Propositions 1.1 and 1.10.

Proof of Proposition 1.1. We only need to prove that F n n-2 ⊆ F n 1 , and so we can assume that n ≥ 4. Let F ∈ F n n-2 and let us show by induction that for every k ∈ {1, . . . , n} we have

(2) F (k ⋅ x 1 , x k+1 , . . . , x n ) ∈ {x 1 , x k+1 , . . . , x n }, x 1 , x k+1 , . . . , x n ∈ X.
By hypothesis, condition (2) holds for any k ∈ {n -2, n -1, n}. Let us now assume that it holds for some k ∈ {2, . . . , n} and let us show that it still holds for k-1. Using associativity and idempotency, we have

F ((k -1) ⋅ x 1 , x k , . . . , x n ) = F (F (n ⋅ x 1 ), (k -2) ⋅ x 1 , x k , . . . , x n ) = F (k ⋅ x 1 , F ((n -2) ⋅ x 1 , x k , x k+1 ), . . . , x n ).
By induction assumption, the latter expression lies in {x 1 , x k , . . . , x n }. This completes the proof.

Proof of Proposition 1.10. The map ψ∶ X → X defined by

ψ(x) = F (e 1 , e 2 , x, (n -3) ⋅ e 1 )
is a bijection and we have ψ -1 (x) = F ((n -2) ⋅ e 2 , x, e 1 ). We then have Let us now prove Theorem 1.9. To this extent, we first state and prove some intermediate results.

Lemma 2.1. Let F ∶ X n → X be an associative operation and let e ∈ E F . Then, for any x 1 , . . . , x n-1 ∈ X we have F (x 1 , . . . , x n-1 , e) = F (x 1 , . . . , e, x n-1 ) = ⋯ = F (e, x 1 , . . . , x n-1 ).

Moreover, for any x ∈ X the restriction F ({x} ⋃ E F ) n is symmetric.

Proof. Let x 1 , . . . , x n-1 ∈ X and let G e be the reduction of F defined by [START_REF] Ackerman | A characterization of quasitrivial n-semigroups[END_REF]. Since E Ge = {e}, we have

F (x 1 , . . . , x n-1 , e) = G n-1 e (x 1 , . . . , x n-1 , e) = G n-1 e (x 1 , . . . , e, x n-1 ) = ⋯ = G n-1
e (e, x 1 , . . . , x n-1 ), which proves the first part of the statement. The second part is a direct consequence of the first part. Lemma 2.2. Let F ∶ X n → X be an associative operation such that E F ≠ ∅. Then F preserves E F , i.e., F (E n F ) ⊆ E F . Proof. Let e 1 , . . . , e n ∈ E F and let us show that F (e 1 , . . . , e n ) ∈ E F . By Lemma 2.1 and associativity of F , for any x ∈ X we have F ((n -1) ⋅ F (e 1 , . . . , e n ), x) = F (F (e 1 , (n -1) ⋅ e 2 ), F (e 1 , (n -1) ⋅ e 3 ), . . . , F (e 1 , (n -1) ⋅ e n ), x)

= F ((n -1) ⋅ e 1 , x) = x.
Similarly, for any x ∈ X we can show that

F (i ⋅ F (e 1 , . . . , e n ), x, (n -i -1) ⋅ F (e 1 , . . . , e n )) = x, i ∈ {1, . . . , n -2},
and the proof is now complete.

Combining Lemmas 2.1 and 2.2, we immediately derive the following result.

Corollary 2.3. If (X, F ) is an n-ary monoid, then (E F , F E n F ) is a symmetric n-ary monoid.
Proof of Theorem 1.9. (Sufficiency) Obvious.

(Necessity) Suppose that X = E F . Let e ∈ E F and G e ∶ X 2 → X be the corresponding reduction of F defined by [START_REF] Ackerman | A characterization of quasitrivial n-semigroups[END_REF]. By Corollary 2.3, we have that F is symmetric. Thus, we have that G e also is symmetric. Moreover, since G e is a binary reduction of F and

E F = X, it follows that G e (G n-2 e ((n -1) ⋅ x), y) = y = G e (y, G n-2 e ((n -1) ⋅ x)), x, y ∈ X,
which shows that G n-2 e ((n -1) ⋅ x) ∈ E Ge for any x ∈ X. However, since E Ge = {e}, we have that G n-2 e ((n -1) ⋅ x) = e for any x ∈ X. Thus, (X, G e ) is an Abelian group whose exponent divides n -1.

The following result follows immediately from Theorem 1.9.

Corollary 2.4. If (X, F ) is an n-ary monoid, then (E F , F E n F ) is the n-ary extension of an Abelian group whose exponent divides n -1.

Let us now prove Theorem 1.5. To this extent, we first state and prove some intermediate results. We have the following remarkable result, which characterizes the existence of a pair of neutral elements for F ∈ F n n-1 by means of two identities. Lemma 2.5.

Let F ∈ F n n-1 and let a, b ∈ X such that a ≠ b. Then a, b ∈ E F if and only if F ((n -1) ⋅ a, b) = b and F (a, (n -1) ⋅ b) = a.
Proof. (Necessity) Obvious.

(Sufficiency) For any x ∈ X, we have

F ((n -1) ⋅ a, x) = F ((n -2) ⋅ a, F (a, (n -1) ⋅ b), x) = F (F ((n -1) ⋅ a, b), (n -2) ⋅ b, x) = F ((n -1) ⋅ b, x),
which implies that F ((n -1) ⋅ a, x) = x = F ((n -1) ⋅ b, x) for any x ∈ X. Similarly, we can show that F (x, (n -1) ⋅ a) = x = F (x, (n -1) ⋅ b) for any x ∈ X. Also, we observe that for any k ∈ {1, . . . , n -2}, the maps ψ k , ξ k ∶ X → X defined by

ψ k (x) = F (k ⋅ a, x, (n -k -1) ⋅ a) ξ k (x) = F (k ⋅ b, x, (n -k -1) ⋅ b)
are bijections with inverse maps ψ n-k-1 and ξ n-k-1 . It then follows that, for any k ∈ {1, . . . , n -2}, we have

F (k ⋅ a, x, (n -k -1) ⋅ a) = x = F (k ⋅ b, x, (n -k -1) ⋅ b), x ∈ X, which shows that a, b ∈ E F .
Given an associative operation F ∶ X n → X, we can define the sequence (F q ) q≥1 of (qn -q + 1)-ary associative operations inductively by the rules F 1 = F and F q (x 1 , . . . , x qn-q+1 ) = F q-1 (x 1 , . . . , x (q-1)n-q+1 , F (x (q-1)n-q+2 , . . . , x qn-q+1 )), for any integer q ≥ 2 and any x 1 , . . . , x qn-q+1 ∈ X. Proposition 2.6. Let F ∈ F n n-1 . For any a 1 , . . . , a n ∈ X such that F (a 1 , . . . , a n ) ∉ {a 1 , . . . , a n }, we have that a 1 , . . . , a n , F (a 1 , . . . , a n ) ∈ E F . Moreover, F (X∖E F ) n is quasitrivial.

Proof. Let us prove by induction on k ∈ {1, . . . , n -1} that the condition

F ((n -k) ⋅ a 1 , a 2 , . . . , a k+1 ) ∉ {a 1 , . . . , a k+1 } implies that a 1 , . . . , a k+1 ∈ E F . For k = 1,
there is nothing to prove. We thus assume that the result holds true for a given k ∈ {1, . . . , n -2} and we show that it still holds for k + 1. Now, consider elements a 1 , . . . , a k+2 such that

(3) F ((n -k -1) ⋅ a 1 , a 2 , . . . , a k+2 ) ∉ {a 1 , . . . , a k+2 }.
We first prove that a 1 , a 2 ∈ E F .

If a 1 = a 2 , then a 1 , . . . , a k+2 ∈ E F by the induction hypothesis.

If a 1 ≠ a 2 , then we prove that F ((n -1) ⋅ a 1 , a 2 ) = a 2 and F (a 1 , (n -1) ⋅ a 2 ) = a 1 , which show that a 1 , a 2 ∈ E F by Lemma 2.5.

• For the sake of a contradiction, assume first that F ((n -1) ⋅ a 1 , a 2 ) = a 1 . Then, for ∈ {1, . . . , n -2} we have

F ((n -k -1) ⋅ a 1 , a 2 , . . . , a k+2 ) = F +1 (((n -k -1) + (n -2)) ⋅ a 1 , ( + 1) ⋅ a 2 , . . . , a k+2 ). (4)
Choosing = n -k -1 and using idempotency of F , we obtain

F ((n -k -1) ⋅ a 1 , a 2 , . . . , a k+2 ) = F 2 ((n -1) ⋅ a 1 , (n -k) ⋅ a 2 , a 3 , . . . , a k+2 ).
Since the left-hand side of this equation does not lie in {a 1 , . . . , a k+2 }, by (3) we obtain F ((n -k) ⋅ a 2 , a 3 , . . . , a k+2 ) ∉ {a 1 , . . . , a k+2 }. By the induction hypothesis, we have a 2 , . . . , a k+2 ∈ E F . Then choosing = n -2 in (4) and using idempotency and the fact that a 2 ∈ E F , we obtain

F ((n -k -1) ⋅ a 1 , a 2 , . . . , a k+2 ) = F n-1 (((n -k -1) + (n -2) 2 ) ⋅ a 1 , (n -1) ⋅ a 2 , . . . , a k+2 ) = F 2 ((n -k) ⋅ a 1 , (n -1) ⋅ a 2 , a 3 , . . . , a k+2 ) = F ((n -k) ⋅ a 1 , a 3 , . . . , a k+2 ).
By the induction hypothesis, we have a 1 ∈ E F . We then have

F ((n -1) ⋅ a 1 , a 2 ) = a 2 ≠ a 1 , a contradiction. • Assume now that F (a 1 , (n -1) ⋅ a 2 ) = a 2 . Then, for ∈ {1, . . . , n -2} we have F ((n -k -1) ⋅ a 1 , a 2 , . . . , a k+2 ) = F +1 ((n -k -1 + ) ⋅ a 1 , ( (n -2) + 1) ⋅ a 2 , . . . , a k+2 ).
For = k, using idempotency and the fact that k(n -2) + 1 = n -k + (k -1)(n -1), we obtain F ((n -k -1) ⋅ a 1 , a 2 , . . . , a k+2 ) = F 2 ((n -1) ⋅ a 1 , (n -k) ⋅ a 2 , a 3 , . . . , a k+2 ).

Thus, F ((n-k)⋅a 2 , a 3 , . . . , a k+2 ) ∉ {a 1 , . . . , a k+2 }. By the induction hypothesis, we have a 2 , . . . , a k+2 ∈ E F . It follows that F (a 1 , (n -1) ⋅ a 2 ) = a 1 ≠ a 2 , a contradiction. Now, since a 2 ∈ E F , it commutes with all other arguments of F by Lemma 2.1. Also, by [START_REF] Couceiro | Quasitrivial semigroups: characterizations and enumerations[END_REF] [START_REF] Ackerman | A characterization of quasitrivial n-semigroups[END_REF]. In the appendix we provide an alternative proof of Corollary 1.6 that does not make use of [START_REF] Couceiro | Every quasitrivial n-ary semigroup is reducible to a semigroup[END_REF]Corollary 2.3].

In [START_REF] Couceiro | Every quasitrivial n-ary semigroup is reducible to a semigroup[END_REF]Proposition 3.7], it was shown that a quasitrivial n-ary semigroup cannot have more than two neutral elements. The next result shows that an operation in F n n-1 is quasitrivial whenever it has at most two neutral elements. (Sufficiency) Suppose to the contrary that E F ≤ 2 and that F is not quasitrivial, i.e., there exist a 1 , . . . , a n ∈ X such that F (a 1 , . . . , a n ) ∉ {a 1 , . . . , a n }. By Proposition 2.6, we have that a 1 , . . . , a n , F (a 1 , . . . , a n ) ∈ E F . Thus, we must have {a 1 , . . . , a n , F (a 1 , . . . , a n )} ≤ 2, which contradicts the idempotency of F and the preservation of E F by F (see Lemma 2.2).

Proposition 2.8. Let F ∈ F n n-1 and suppose that E F ≥ 3. Then, any element x ∈ X ∖ E F is an annihilator of F ({x} ⋃ E F ) n . Moreover, F (X∖E F ) n is quasitrivial and has at most one neutral element.

Proof. Let x ∈ X ∖ E F and e ∈ E F and let us show that F (k ⋅ x, (n -k) ⋅ e) = x for any k ∈ {1, . . . , n -1}. If k = 1, then the latter identity follows from the definition of a neutral element. Now, suppose that there exists k ∈ {2, . . . , n-1} such that F (k ⋅x, (n-k)⋅e) ≠ x. Since x ∈ X ∖ E F , by Proposition 2.6 we must have F (k ⋅ x, (n -k) ⋅ e) = e. But then, using the associativity of F , we get

F ((n -1) ⋅ x, e) = F ((n -1) ⋅ x, F (k ⋅ x, (n -k) ⋅ e)) = F (k ⋅ x, (n -k) ⋅ e) = e,
and we conclude by Lemma 2.5 that x ∈ E F , which contradicts our assumption. Thus, we have which completes the proof by idempotency of F and Lemma 2.1. For the second part of the proposition, we observe that F (X∖E F ) n is quasitrivial by Proposition 2.6. Also, using (5) and the associativity of F , for any x, y ∈ X ∖ E F and any e ∈ E F we obtain

F ((n -1) ⋅ x, y) = F ((n -1) ⋅ x, F (e, (n -1) ⋅ y)) = F (F ((n -1) ⋅ x, e), (n -1) ⋅ y) = F (x, (n -1) ⋅ y),
which shows that F (X∖E F ) n cannot have more than one neutral element. ) is the n-ary extension of an Abelian group whose exponent divides n -1. Thus, since Y is unique, it follows that Y = E F . Finally, the quasitriviality of F on D n n-1 is straightforward to check.

idempotency of F we obtain G n-1 (x 1 , . . . , x n ) = F n-1 ((n -1) ⋅ x 1 , (n -1) ⋅ x 2 , . . . , (n -1) ⋅ x n-1 , x n ) = F n-1 ((2n -3) ⋅ x 1 , x 2 , (n -1) ⋅ x 3 , . . . , (n -1) ⋅ x n-1 , x n ) = ⋯ = F n-1 ((n(n -1) -2(n -1) + 1) ⋅ x 1 , x 2 , x 3 , . . . , x n-1 , x n ) = F (x 1 , . . . , x n ), which shows that F is reducible to G.

Remark 5. Let ≤ be a total ordering on X. An operation F ∶ X n → X is said to be ≤preserving if F (x 1 , . . . , x n ) ≤ F (x ′ 1 , . . . , x ′ n ) whenever x i ≤ x ′ i for any i ∈ {1, . . . , n}. One of the main results of Kiss and Somlai [START_REF] Kiss | Associative idempotent nondecreasing functions are reducible[END_REF]Theorem 4.8] is that every ≤-preserving operation F ∈ F n n is reducible to an associative, idempotent, and ≤-preserving binary operation. The reader can easily verify that the latter is an immediate consequence of Proposition 3.3 above.

The following result is the key for the alternative proof of Corollary 1.6. Proposition 3.4. Let F ∈ F n n-1 . The following assertions are equivalent. (i) F is reducible to an associative and quasitrivial operation G∶ X 2 → X. (ii) F is reducible to an associative and idempotent operation G∶ X 2 → X. (iii) F ((n -1) ⋅ x, y) = F (x, (n -1) ⋅ y) for any x, y ∈ X. (iv) E F ≤ 1.

Proof. The equivalence (i) ⇔ (ii) and the implication (iii) ⇒ (iv) are straightforward. Also, the equivalence (ii) ⇔ (iii) follows from Proposition 3.3. Now, let us show that (iv) ⇒ (iii). So, suppose that E F ≤ 1 and suppose to the contrary that there exist x, y ∈ X with x ≠ y such that F ((n -1) ⋅ x, y) ≠ F (x, (n -1) ⋅ y). We have two cases to consider. If F ((n-1)⋅x, y) = y and F (x, (n-1)⋅y) = x, then by Lemma 2.5 we have that x, y ∈ E F , which contradicts our assumption on E F . Otherwise, if F ((n -1) ⋅ x, y) = x and F (x, (n -1) ⋅ y) = y, then we have

(

  a) (Y, F Y n ) is the n-ary extension of an Abelian group whose exponent divides n-1. (b) F (X∖Y ) n is quasitrivial and has at most one neutral element. (c) Any x ∈ X ∖ Y is an annihilator for F ({x} ⋃ Y ) n . Moreover, we have that Y = E F . Remark 3. The associativity assumption can be removed in Theorem 1.5 if we replace condition (c) by the following two conditions.

G

  e2 (ψ(x), ψ(y)) = F (F (e 1 , e 2 , x, (n -3) ⋅ e 1 ), (n -2) ⋅ e 2 , F (e 1 , e 2 , y, (n -3) ⋅ e 1 )) = F (F (e 1 , e 2 , x, (n -3) ⋅ e 1 ), F ((n -2) ⋅ e 2 , e 1 , e 2 ), y, (n -3) ⋅ e 1 ) = F (F (e 1 , e 2 , x, (n -3) ⋅ e 1 ), e 1 , y, (n -3) ⋅ e 1 ) = F (e 1 , e 2 , F (x, (n -2) ⋅ e 1 , y), (n -3) ⋅ e 1 ) = ψ(G e1 (x, y)), which completes the proof.

Corollary 2 . 7 .

 27 An operation F ∈ F n n-1 is quasitrivial if and only if E F ≤ 2.Proof. (Necessity) This follows from [2, Proposition 3.7].

( 5 )

 5 F (k ⋅ x, (n -k) ⋅ e) = x, k ∈ {1, . . . , n -1}. Now, let us show that F (k ⋅ x, e k+1 , . . . , e n ) = x for any k ∈ {1, . . . , n -1} and any e k+1 , . . . , e n ∈ E F . To this extent, we only need to show that F (k ⋅ x, e k+1 , . . . , e n ) = F ((k + 1) ⋅ x, e k+2 , . . . , e n ), for any k ∈ {1, . . . , n -1} and any e k+1 , . . . , e n ∈ E F . So, let k ∈ {1, . . . , n -1} and e k+1 , . . . , e n ∈ E F . Using (5) and the associativity of F we get F (k ⋅ x, e k+1 , . . . , e n ) = F ((k -1) ⋅ x, F (2 ⋅ x, (n -2) ⋅ e k+1 ), e k+1 , . . . , e n ) = F (k ⋅ x, F (x, (n -1) ⋅ e k+1 ), e k+2 , . . . , e n ) = F ((k + 1) ⋅ x, e k+2 , . . . , e n ),

x

  = F ((n -1) ⋅ x, y) = F ((n -1) ⋅ x, F (n ⋅ y)) = F (F ((n -1) ⋅ x, y), (n -1) ⋅ y) = F (x, (n -1) ⋅ y) = y,which contradicts the fact that x ≠ y.Proof of Corollary 1.6. This follows from Proposition 3.4 and [5,Lemma 1].

  we have F ((n -k -1) ⋅ a 1 , a 3 , . . . , a k+2 , a 2 ) ∉ {a 1 , . . . , a k+2 }, and thus a 3 ∈ E F . Repeating this argument, we have that a 1 , . . . , a k+2 ∈ E F . Furthermore, F (a 1 , . . . , a n ) ∈ E F by Lemma 2.2. The second part is straightforward. Remark 4. In the proof of Corollary 1.6 we used [2, Corollary 2.3] which is based on results obtained by Ackerman

	Proof of Corollary 1.6. This follows from [2, Corollary 2.3], Proposition 2.6, and [5, Lemma
	1].

  It is not difficult to see that Y ⊆ E F . By Corollary 2.7, we also have that E F ≥ 3. By Corollary 2.4, the pair (E F , F E n F

	Proof of Theorem 1.5. (Necessity) This follows from Corollaries 2.4 and 2.7 and Proposi-
	tion 2.8.
	(Sufficiency)

Proof of Corollary 1.7. This follows from Theorem 1.5, Corollary 1.6, and Proposition 1.2.

AN ALTERNATIVE HIERARCHY

For any integer k ≥ 1, let S n k be the set of n-tuples (x 1 , . . . , x n ) ∈ X n such that {x 1 , . . . , x n } ≤ k. Of course, we have D n k ⊆ S n n-k+1 for k ∈ {1, . . . , n}. Now, denote by G n k the class of those associative n-ary operations F ∶ X n → X satisfying F (x 1 , . . . , x n ) ∈ {x 1 , . . . , x n }, (x 1 , . . . , x n ) ∈ S n k . We say that these operations are quasitrivial on

, and hence we only need to consider operations in G n 2 . The analog of Theorem 1.5 can then be stated as follows. ) is the n-ary extension of an Abelian group whose exponent divides n -1. In particular, for any e ∈ E F , we have that (E F , G e ) is an Abelian group whose exponent divides n -1. However, since the neutral element is the only idempotent element of a group and since G e (e ′ , e ′ ) ∈ {e, e ′ } for any e, e ′ ∈ E F , it follows that G e (e ′ , e ′ ) = e for any e, e ′ ∈ E F , i.e., for any e ∈ E F we have that (E F , G e ) is a group of exponent 2. (Recall that an element x ∈ X is said to be idempotent for an operation F ∶ X n → X if F (n ⋅ x) = x.) Therefore, we conclude that (E F , F E n F ) is the n-ary extension of an Abelian group of exponent 2. Also, since 2 divides n -1 we conclude that n is odd.

(Sufficiency) It is not difficult to see that Y ⊆ E F . Now, let e ∈ E F and let us show that e ∈ Y . Suppose to the contrary that e ∉ Y , i.e., e ∈ X ∖ Y . But then by (c) we have

which contradicts the definition of a neutral element. Thus, we have Y = E F . Also, since (Y, F ) is the n-ary extension of an Abelian group of exponent 2 and n is odd, it follows that F ∈ G n 2 . The remaining properties follow from Theorem 1.5.

The following corollary follows from Theorem 3.1, Proposition 1.2, and Corollary 1.6.

and only if it is reducible to an associative operation G∶ X 2 → X, n is odd, and there exists a unique subset Y ⊆ X, with Y ≥ 3, such that the following conditions hold.

Corollary 3.2 is particularly interesting as it allows to construct easily n-ary operations in G n

2 ∖ G n n . For instance, consider the set X = {1, 2, 3, 4, 5, 6} together with the operation G∶ X 2 → X defined by the following conditions: 2 , where π 1 ∶ X 2 → X is defined by π 1 (x, y) = x for any x, y ∈ X, • for any x ∈ {1, 2, 3, 4}, G(x, 5) = G(5, x) = 5 and G(x, 6) = G(6, x) = 6.

Then for any integer p ≥ 1, we have that the operation associated with any (2p + 1)-ary extension of ({1, 2, 3, 4, 5, 6},

2p+1 by Corollary 3.2.

CONCLUDING REMARKS

In this paper we characterized the class F n n-1 ∖ F n 1 , i.e., the class of those associative operations F ∶ X n → X that are not quasitrivial but satisfy the condition F (x 1 , . . . , x n ) ∈ {x 1 , . . . , x n } whenever at least n -1 of the elements x 1 , . . . , x n are equal to each other (Theorem 1.5). Moreover, we proved that any such operation is reducible to a binary operation (Corollary 1.6). This led to an alternative characterization of the class F n n-1 ∖F n 1 based on binary reductions (Corollary 1.7). Finally, we characterized the class G n 2 ∖G n n , i.e., the class of those associative operations F ∶ X n → X that are not quasitrivial but satisfy the condition F (x 1 , . . . , x n ) ∈ {x 1 , . . . , x n } whenever {x 1 , . . . , x n } ≤ 2 (Theorem 3.1 and Corollary 3.2).

The main results of this paper thus characterize several relevant subclasses of associative and idempotent n-ary operations. However, the characterization of the class F n n of associative and idempotent n-ary operations still eludes us. This and related enumeration results [START_REF] Couceiro | Every quasitrivial n-ary semigroup is reducible to a semigroup[END_REF][START_REF] Couceiro | Quasitrivial semigroups: characterizations and enumerations[END_REF] constitute a topic of current research.

ACKNOWLEDGMENTS

The second author is supported by the Luxembourg National Research Fund under the project PRIDE 15/10949314/GSM. APPENDIX: ALTERNATIVE PROOF OF COROLLARY 1.6 We provide an alternative proof of Corollary 1.6 that does not use [START_REF] Couceiro | Every quasitrivial n-ary semigroup is reducible to a semigroup[END_REF]Corollary 2.3]. To this extent, we first prove the following general result.

The following assertions are equivalent. (i) F is reducible to an associative and idempotent operation G∶ X 2 → X. (ii) F ((n -1) ⋅ x, y) = F (x, (n -1) ⋅ y) for any x, y ∈ X.

Proof. The implications (i) ⇒ (ii) is straightforward. Now, let us show that (ii) ⇒ (i). So, suppose that [START_REF] Dörnte | Untersuchungen über einen verallgemeinerten Gruppenbegriff[END_REF] F ((n -1) ⋅ x, y) = F (x, (n -1) ⋅ y)

x, y ∈ X, and consider the operation G∶ X 2 → X defined by G(x, y) = F ((n-1)⋅x, y) for any x, y ∈ X. It is not difficult to see that G is associative and idempotent. Now, let x 1 , . . . , x n ∈ X and let us show that G n-1 (x 1 , . . . , x n ) = F (x 1 , . . . , x n ). Using repeatedly [START_REF] Dörnte | Untersuchungen über einen verallgemeinerten Gruppenbegriff[END_REF] and the