Thomas Garbay
email: thomas.garbay@lip6.fr

Orlando Chuquimia
email: orlando.chuquimia@lip6.fr

Andrea Pinna
email: andrea.pinna@lip6.fr

Hichem Sahbi
email: hichem.sahbi@lip6.fr

Xavier Dray
email: xavier.dray@aphp.fr

Bertrand Granado
email: bertrand.granado@lip6.fr

Distilling the knowledge in CNN for WCE screening tool

A way to improve the early detection of colorectal cancer is screening. Polyps are a marker of colorectal cancer and the best modality to detect them is the image. In 2003 Wireless Capsule Endoscopy was introduced and opened a way to integrate automatic image processing to realize a screening tool. Moreover, the capacity to detect polyp with Convolutional Neural Network was shown in many scientific studies, but one issue is the integration of these networks. In this article, we present our works to integrate CNN or image processing based on a CNN inside a WCE to realize a powerful screening tool. We apply the knowledge distillation method. We prove that knowledge distillation is efficient from VGG16 to Squeezenet in polyp detection context

I. INTRODUCTION

In 2018 Colorectal cancer (CRC) was the second highest cause of death by cancer worldwide. The mortality rate was 47.62% and corresponding to 880,792 deaths. [START_REF] Allison | A comparison of fecal occult-blood tests for colorectal-cancer screening[END_REF], [START_REF] Swain | Wireless capsule endoscopy[END_REF]. It is a public health problem. In about 95% of the cases, the beginning of CRC is a growth on the inner lining of the colon or rectum called polyp [START_REF] Ferlay | Cancer incidence and mortality worldwide: Sources, methods and major patterns in GLOBOCAN 2012[END_REF]. The European Code Against Cancer recommends an early detection to greatly improve outcomes through screening of gastrointestinal (GI) tract [START_REF] Halloran | European guidelines for quality assurance in colorectal cancer screening and diagnosis. First Edition Faecal occult blood testing[END_REF]. Indeed, in about 90% of the cases, CRC is treatable if it is detected before polyp become adenocarcinomas [START_REF] Qlqc | the european organization for research and treatment of cancer qlq-c30: a qualityof-life instrument for use in international clinical trials in oncology[END_REF].

Today, to find polyps, image is the modality for analyzing the colon. Screening, diagnosis, and therapy in the gastrointestinal tract are done with the same tool: the colonoscopy. However, it is a painful examination and poorly tolerated by patients. The colonoscopy is invasive and needs anesthesia, a specialist and a controlled environment. Furthermore, the colonoscopy doesn't allow the visibility of all the regions near the colon. Another method, the colorectal tomography (CTC), is non-invasive, but it can not detect polyps less than 1cm and patients are exposed to radiation [START_REF] Karargyris | Detection of small bowel polyps and ulcers in wireless capsule endoscopy videos[END_REF].

In many countries, the screening process starts with a test, a Faecal Occult Blood Test (FOBT) or a Fecal Immunochemical Test (FIT). The need for a colonoscopy is determined by these tests. However, FOBT has a poor sensitivity of only 38% [START_REF] Allison | A comparison of fecal occult-blood tests for colorectal-cancer screening[END_REF]. For the FIT test sensibility depends on the calibration of µg/g of blood. A study shows a variation from 89% for a FIT calibrated to detect less than 20 µg/g of blood to 70% if it is calibrated to detect 20 to 50 µg/g of blood [START_REF] Lee | Accuracy of fecal immunochemical tests for colorectal cancer: systematic review and meta-analysis[END_REF]. Decreasing the sensibility of FIT test increases its specificity and reduce the number of useless colonoscopies. Thus, it is preferred to increase the specificity and decrease the sensibility of the FIT test and realize a periodic screening.

As exposed, there is a need for a screening tool with high sensibility and high specificity. In 2003 Paul Swain and al [START_REF] Swain | Wireless capsule endoscopy[END_REF] have introduced Wireless Capsule Endoscopy (WCE), a simple pill that patient swallows and that transmits images of the gastrointestinal tract via a Radio Frequency communication through the body. More than 1.6 million patients worldwide have used this technology for the small bowel, esophagus, and colon (more than 125,000 procedures a year). The available WCEs for the colon [START_REF] Karargyris | Detection of small bowel polyps and ulcers in wireless capsule endoscopy videos[END_REF], example are visible in table I, has a length of 31 mm and diameter of 11 mm, battery life of 10 hours, a resolution of 256x256 pixels and an image sampling rate around 2 to 4 frames per second. As in many domains, Convolutional Neural Network (CNN) demonstrates its capacity to detect polyp lesions.

A. Polyps and CNN state of the art

In [START_REF] Hwang | Bag-of-visual-words approach based on surf features to polyp detection in wireless capsule endoscopy videos[END_REF], AlexNet model [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] pre-trained on the ILSVRC 2012 dataset was used to detect polyps. The input was modified to an image size of 96x96. Furthermore, the kernel size of the two first pooling layers is decreased from 3 to 2 and the last pooling layer is removed to modify the output layer for two outputs: polyp or non-polyp. They increased the number of examples applying random mirroring, rotation, up-and downscaling, cropping, and brightness adjustment in the original database. They use a sliding-window strategy to determine the polyp presence or absence in a video sequence. They evaluate their CNN performance in a dataset of 120 frames (60 with a polyp), they use 80 images (40 with a polyp) to train and the rest to testing, their experimentation has shown an accuracy of 60%.

In [START_REF] Zhao | A decision fusion strategy for polyp detection in capsule endoscopy[END_REF], authors use three CNN trained at different image scales (x1, x0.5, x0.25). They remove the last fully connected layer, the outputs of the convolutional layer of each CNN are fed as input to a single Multi-Layer Perceptron (MLP) network that is trained separately. The training was performed exclusively on the CVC-CLINIC(Computer Vision Center/Universitat Autonoma de Barcelona and Hospital Clinic from Barcelona, Spain) database composed by 1200 WCE images. Such a CNN achieves an accuracy classification of 90%.

Despite CNN achieve very good performance on polyp detection, all these methods are running on an external computer and contribute to helping the physician in his diagnosis. Unfortunately, they are not useable to be integrated inside a WCE. Indeed, they do not consider WCE constraints such as real-time execution, the form factor of the pill, energy consumption. Especially, CNN methods use a great number of parameters, that are not implantable in an 8x8 mm 2 chip inside a pill.

How it is possible to use CNN, such a powerful tool, to embed its processing inside an iWCE ?

B. Reducing a CNN

One potential solution is to reduce the number of parameters in CNN. In [START_REF] Lecun | Optimal brain damage[END_REF], Lecun and his team were among the first using pruning to reduce the network complexity and overfitting. The idea of pruning is to reduce the size of a network by deleting unnecessary weights. Recently, authors in [START_REF] Han | Learning both weights and connections for efficient neural network[END_REF], applied this method on state of the art CNN like AlexNet or VGG16, with no loss of accuracy on PASCAL, COCO, KITTI, and ImageNet datasets. Moreover, in [START_REF] Han | Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding[END_REF] quantization method and weight sharing compress the network through the reduction of the required number of bits to represent each weight. More than quantization, they also applied pruning and Huffman coding. They reduced the number of parameters of Alexnet by 9x, from 61 million to 6.7 million and the number of parameters of VGG16 by 13x, from 138 million to 10.3 million.

These parameter reduction examples of a CNN are focused on the software part, but improvement can also be done on the hardware part. In [START_REF] Han | Efficient Inference Engine on Compressed Deep Neural Network[END_REF] with their energy efficient inference engine, they accelerated the resulting sparse matrix-vector multiplication with the weight sharing method. They considerably improve the speed and energy efficiency compared to CPU and GPU.

Finally, a method named knowledge distillation, whose feasibility was first shown by the team of Bucilla [START_REF] Bucilu | Model Compression[END_REF], has been used on the resolution of eight problems with excellent results and negligible losses due to size reduction of the CNN.

The obtained compressed network, on average, was a thousand times smaller and a thousand times faster than the original network. It was trained by mimicking the output of the original network. The team of Hinton [START_REF] Hinton | Distilling the Knowledge in a Neural Network[END_REF] tested this methodology on the MNIST database and for the processing of natural language issues and achieved good results in applying the prediction of the teacher network as a soft label. Then, Chen [START_REF] Chen | Learning Efficient Object Detection Models with Knowledge Distillation[END_REF] used distillation for object detection on datasets as PASCAL, KITTI, ILSVRC2014 and MS-COCO. They reduced the required storage for AlexNet by a factor of 35 and the required storage for VGG16 by a factor of 49.

The purpose of this article is to describe our first work to study the possibility to integrate a CNN inside a WCE to detect polyps. We present our study based on a Deep Learning algorithm, a Convolutional Neural Network (CNN) and we apply the knowledge distillation method to a smaller CNN.

II. A CNN TO DETECT POLYPS

We first train a CNN, the VGGnet [START_REF] Simonyan | Very Deep Convolutional Networks for Large-Scale Image Recognition[END_REF], invented by Visual Geometry Group from the University of Oxford, to classify images in two classes: with polyps and without polyp. The architecture of this CNN is shown in Figure 1. This CNN was the first runner-up of the 2014 ILSVRC Contest, which is the first year that deep learning models obtained the error rate under 10%, with a Top-5 error-rate of 8.8% for VGG16. It has 138 million parameters. This state of the art network is one of the biggest and regards to the distillation method, it could be better to start with a big network, which should have a good performance on polyp classification.

We modify the last layer of VGG16, the fully-connected layer, with a structure with two outputs dedicated determining the presence of a polyp. To train this network we use a 11952 images database divided into 10023 images with polyp and 1929 images without polyp. These images are issued from 18 videos of endoscopic examinations of Hospital Clinic, Barcelona, Spain. This dataset was used in EndoVisSub2017-GIANA contest [START_REF] Bernal | Polyp Detection Benchmark in Colonoscopy Videos using GTCreator: A Novel Fully Configurable Tool for Easy and Fast Annotation of Image Databases[END_REF]. Each image is associated with a ground-truth: a binary-image that indicates the position of the polyp in the image.

We use 70% of the dataset to train VGG16, and the remaining 30% to test its performance. The result shows an accuracy of more than 98%. Although we have achieved very good accuracy, it is impossible to embed this convolutional neural network with one hundred and thirty height million parameters into a WCE.

We then propose to use the distillation method to do so for polyp detection.

III. PROPOSED METHOD

Previous works on the knowledge distillation method, [START_REF] Bucilu | Model Compression[END_REF], [START_REF] Chen | Learning Efficient Object Detection Models with Knowledge Distillation[END_REF], [START_REF] Hinton | Distilling the Knowledge in a Neural Network[END_REF], show that it is possible for a faster-compressed network to be able to approximate the function learned previously by a larger and slower network, but intrinsically more efficient. We apply the distillation method N times to observe the limit of accuracy we can obtain with state of the art CNN. The CNN generated by the distillation is named the student network and it will replace the teacher network, here VGG16, in each further iteration.

The efficiency of CNN was measured with two important metrics: sensibility (1), it is the image rate with polyp correctly predict and specificity [START_REF] Pinna | Connectionist retina: a neural networks system integrated into an electronic retina[END_REF], it is the image rate without polyp correctly predict.

Sensibility =

V P V P + F P

(1)

Specif icity = V N V N + F N (2)
Where :

• TP = True Positive, number of images with polyp which is correctly classified. • FP = False Positive, number of images with polyp which is not correctly classified. • TN = True Negative, number of images without polyp which is correctly classified. • FN = False Negative, number of images without polyp which is not correctly classified. We can compute the Accuracy, that is the global performance of the CNN, as:

Accuracy = T P + T N T P + T N + F P + F N (3)
A. The teacher network: VGG16

We have trained VGG16, the teacher network, which will allow the training of another small network. The training and validation dataset was composed as follow:

• training set: 5857 images including 4910 with polyp(s) and 947 without polyp. • validation set: 2509 images including 2106 with polyp(s) and 403 without polyp. It was tested on five test datasets. Each of these was randomly created from our polyp images database precedently described. Thanks to these five datasets, we did crossvalidation of the accuracy of our teacher network. These test datasets are composed of 3586 images, including 3008 with polyp(s) and 578 without polyp. It represents 30% of the entire database. Every test, even those on small networks will be done on these five test datasets to keep the same test reference. Test results are visible on table II for the teacher network VGG16: As shown on table II, VGG16 is excellent to detect polyp. The sensibility and the specificity are respectively 99% and 98.3%. As we wanted, this network could be a good teacher network to apply distillation.

B. The student network: Squeezenet

To be sure of the efficiency of distillation method on polyp detection, we first train and test on one of the state-of-theart convolutional neural networks, Squeezenet [START_REF] Iandola | Alexnet-level accuracy with 50x fewer parameters and ¡0[END_REF], by Deep-Scale, UC Berkeley and Stanford University. The architecture of Squeezenet is based on fire module, composed by a squeeze convolution layer with only 1x1 filters and expand layer that has a mix of 1x1 and 3x3 filters. This architecture is represented in figure 2. Moreover, this network has around one million parameters without compression, far less than VGG16. We first compare the validation results of Squeezenet between two datasets:

• our original dataset, precedently described • our original dataset, labeled by trained VGG16 We trained Squeezenet on both sets during 500 epochs to observe the behavior of the network on a large scale. Results show a better accuracy for Squeezenet trained on the dataset labeled by VGG16, namely 0.9829 compare to accuracy for Squeezenet trained on the original dataset, namely 0.9785. But the difference is only 0.0044 which is very small and shows that distillation allows training efficiently a student network. Figure 3 underline the influence of distillation on validation results.

The blue curve represents Squeezenet accuracy on validation set, previously trained on dataset labelled by VGG16. The orange curve represents Squeezenet accuracy on validation, previously trained on the original dataset. Both reach the beginning of convergence after twenty epochs but the blue curve needs around fifty epochs to reach stabilization compared to forty epochs for the other. As shown in table III, Squeezenet with distillation has a mean specificity of 93.82% and a mean sensibility of 98.73%. Performances demonstrate a good result for polyp detection with a complexity reduction of 2 order of magnitude. Even if there is still too much parameter to be embedded inside a pill, this result shows a clear way to define a smaller CNN that can be integrable inside a WCE.

IV. CONCLUSION

CNNs have demonstrated their powerful generalization capacity for the particular task of colorectal cancer detection. Integrated inside a WCE, CNNs are successfully used for efficient early diagnosis of this disease. However, creating embedded CNNs on limited hardware resources is not trivial and requires a careful design in order to reduce the complexity of the original CNNs. Our solution presented in this paper relies on distillation and makes it possible to reduce the complexity of CNNs by two orders of magnitude with only 1% loss of sensibility and 5% loss of specificity. This encouraging result opens the way to compress CNNs with at least one additional order of magnitude and to make them embeddable [START_REF] Pinna | Connectionist retina: a neural networks system integrated into an electronic retina[END_REF].

Fig. 1 .

 1 Fig. 1. The teacher network : VGG16

Fig. 2 .

 2 Fig. 2. The first student network : Squeezenet

  Figure 3 allows us to determine the right number of epochs to obtain the best performance

Fig. 3 .

 3 Fig. 3. Distillation influence on Squeezenet validation results


Jean Néraud
email: jean.neraud@univ-rouen.fr

Gray Cycles of Maximum Length Related to k-Character Substitutions

Keywords: Character, Complexity, Cycle, Gray, Substitution, Relation, Word

Given a word binary relation τ onto A * we define a τ -Gray cycle over a finite language X to be a permutation w [i] 0≤i≤|X|-1 of X ⊆ A * such that each word wi is an image of the previous word wi-1 by τ . In that framework, we introduce the complexity measure λ(n), equal to the largest cardinality of a language X having words of length at most n, and such that some τ -Gray cycle over X exists. The present paper is concerned with the relation τ = σ k , the so-called k-character substitution, where (u, v) belongs to σ k if, and only if, the Hamming distance of u and v is k. We compute the bound λ(n) for all cases of the alphabet cardinality and the argument n.

Introduction

In the framework of combinatorial algorithms, one of the most documented questions consists in the development of methods in order to generate, exactly once, all the objects in some specific class [START_REF] Lehmer | The machine tools of combinatorics[END_REF]. Many topics are concerned by such a problem: suffice it to mention sequence counting [START_REF] Bartucci | ECO: a methodology for the enumeration of combinatorial objects[END_REF], signal encoding [START_REF] Ludman | Gray code generation for MPSK signals[END_REF], and data compression [START_REF] Richard | Data compression and Gray-code sorting[END_REF].

The so-called binary Gray codes first appeared in [START_REF] Gilbert | Gray codes and paths on the N-cube[END_REF]: given a binary alphabet A and some positive integer n, they referred to sequences with maximum length of pairwise different n-tuples of characters (that is, words in A n ), provided that any pair of consecutive items differ by exactly one character. Shortly after, a similar study was drawn in the framework of non-binary alphabets [START_REF] Cohn | Affine m-ary Gray codes[END_REF][START_REF] Er | On generating the N-ary reflected gray codes[END_REF]. With regard to other famous combinatorial classes of objects, the term of combinatorial Gray code, for its part, appeared in [START_REF] Joichi | Combinatorial Gray codes[END_REF]: actually, the difference between successive items, although being fixed, need not to be small [START_REF] Savage | A survey of combinatorial Gray codes[END_REF]. Generating all permutations of a given n-element set constitutes a noticeable example [START_REF] Ehrlich | Loopless algorithms for generating permutations, combinations, and other combinatorial configurations[END_REF]. Subsets of fixed size are also concerned [START_REF] Eades | An algorithm for generating subsets of fixed size with a strong minimal change property[END_REF], as well as cross-bifix-free words [START_REF] Bernini | Prefix partitioned gray codes for particular cross-bifix-free sets[END_REF], Debruijn sequences [START_REF] Fredricksen | Necklaces of beads in k colors and k-ary de Bruijn sequences[END_REF], set partitions [START_REF] Kaye | A gray code for set partitions[END_REF], necklaces [START_REF] Ruskey | Generating necklaces[END_REF]: the list is far to be exhaustive. Combinatorial Gray sequences are often needed to be cyclic [START_REF] Chung | Universal cycles for combinatorial structures[END_REF], in the sense that the initial term itself can be retrieved as successor of the last one. Such a condition justifies the terminology of Gray cycle [START_REF] Knuth | The Art of Computer programming[END_REF]Sect. 7.2.1.1].

In view of some formal framework, we notice that each of the sequences we mentioned above involves some word binary relation τ ⊆ A * × A * , where A stands for a finite alphabet, and A * for the free monoid it generates. For its part, the combinatorial class of objects can be modelled by some finite langage X ⊆ A * . Given a sequence of words we denote in square brackets the corresponding indices: this will allow us to make a difference from w i , the character in position i in a given word w. We define a cyclic Gray sequence over X, with respect to τ (for short: τ -Gray cycle over X) as every finite sequence of words w

[i] i∈[0,|X|-1]
satisfying each of the three following conditions:

(G1) For every word x ∈ X, some i ∈ [0, |X| -1] exists such that we have x = w [i] ; (G2) For every i ∈ [1, |X| -1], we have w [i] ∈ τ w [i-1] ; in addition, the condition w [0] ∈ τ w [|X|-1] holds; (G3) For every pair i, j ∈ [0, |X| -1], i = j implies w [i] = w [j] .
With this definition, the set X need not to be uniform that is, in the Gray cycle the terms may have a variable length. For instance, given the alphabet A = {0, 1}, take for τ the word binary relation Λ 1 which, with every word w associates all the strings located within a Levenshtein distance of 1 from w (see e.g. [START_REF] Néraud | Variable-length codes independent or closed with respect to edit relations[END_REF]); with such a relation, the sequence (0, 00, 01, 11, 10, 1) is a

Λ 1 -Gray cycle over X = A ∪ A 2 .
Actually, in addition to the topics we mentioned above, two other famous topics are involved by those Gray cycles. Firstly, with regard to graph theory, a τ -Gray cycle over X exists if, and only if, there is some hamiltonian circuit in the graph of the relation τ (see e.g. [START_REF] Savage | A survey of combinatorial Gray codes[END_REF]). Secondly, given a binary word relation τ ⊆ A * × A * , and given X ⊆ A * , if some τ -Gray cycle exists over X, then X is τ -closed [START_REF] Néraud | Variable-length codes independent or closed with respect to edit relations[END_REF] that is, the inclusion τ (X) ⊆ X holds, where τ (X) stands for the set of the images of the words in X under the relation τ . Such closed sets actually constitute a special subfamily in the famous dependence systems (see [START_REF] Cohn | Universal Algebra[END_REF][START_REF] Jürgensen | Codes[END_REF]). Notice that, given a τ -closed set X ⊆ A * , there do not necessarily exist non-empty τ -Gray cycles over X. A typical example is provided by τ being id A * , the identity over A * , with respect to which every finite set X ⊆ A * is closed; however non-empty τ -Gray cycle can exist only over singletons.

In the present paper, given a positive integer n, and denoting by A ≤n the set of the words with length not greater than n, we consider the family of all sequences that can be a τ -Gray cycle over some subset X of A ≤n . This is a natural question to study those sequences of maximum length which, of course, correspond to subsets X of maximum cardinality; such a length, which we denote by λ A,τ (n), means introducing some complexity measure for the word binary relation τ . With regard to the preceding examples we have λ {0,1},Λ1 (2) = 6; moreover, for every alphabet A and positive integer n, the identity λ A,id A * (n) = 1 holds. We focus on the case where τ is σ k , the so-called k-character substitution: with every word with length at least k, say w, this relation associates all the words w ′ , with |w ′ | = |w|, and such that the character w ′ i differs from w i in exactly k values of i ∈ [1, |w|]. As commented in [START_REF] Jürgensen | Codes[END_REF][START_REF] Néraud | Variable-length codes independent or closed with respect to edit relations[END_REF], σ k has noticeable inference in the famous framework of error detection. On the other hand, by definition, w ′ ∈ σ k (w) implies |w ′ | = |w| therefore, if there is some σ k -Gray cycle over X, then X is a uniform set. From this point of view, the classical Gray codes, which allow to generate all n-tuples over A, correspond to σ 1 -Gray cycles over A n , furthermore we have λ A,σ1 (n) = |A| n . In addition, in the case where A is a binary alphabet, it can be easily proved that, for every n ≥ 3, we have λ A,σ2 (n) = 2 n-1 [14, Exercice 8, p. 77]. However, in the most general case, although an exhaustive description of σ k -closed variable-length codes has been provided in [START_REF] Néraud | Variable-length codes independent or closed with respect to edit relations[END_REF], the question of computing some σ k -Gray cycle of maximum length has remained open. In our paper we establish the following result:

Theorem Let A be a finite alphabet, k ≥ 1, and n ≥ k. Then exactly one of the following conditions holds:

(i) |A| ≥ 3, n ≥ k, and λ A,σ k (n) = |A| n ; (ii) |A| = 2, n = k, and λ A,σ k (n) = 2; (iii) |A| = 2, n ≥ k + 1, k is odd and λ A,σ k (n) = |A| n ; (iv) |A| = 2, n ≥ k + 1, k is even, and λ A,σ k (n) = |A| n-1 .
In addition, in each case some σ k -Gray cycle of maximum length can be explicitly computed.

We now shortly describe the contents of the paper. In Sect. 2, we recall the two famous examples of the binary (resp., |A|-ary) reflected Gray code. By applying some induction based methods, in Sect. 3 and Sect. 4, these sequences allow to compute special families of σ k -Gray cycles with maximum length. In Sect. 5, in the case where A is a binary alphabet, and k an even positive integer, we also compute a family of Gray cycles with maximum length; in addition some further development is raised.

Preliminaries

Several definitions and notation have already been fixed. In the whole paper, A stands for some finite alphabet, with |A| ≥ 2. Given a word w ∈ A * , we denote by |w| its length; in addition, for every a ∈ A, we denote by |w| a the number of occurrences of the character (or character) a in w.

The reflected binary Gray cycle

Let A = {0, 1}, and n ≥ 1. The most famous example of σ 1 -Gray cycle over A n is certainly the so-called reflected binary Gray code (see e.g. [START_REF] Gilbert | Gray codes and paths on the N-cube[END_REF] or [14, p. 6]): in the present paper we denoted it by g n,1 . It can be defined by the recurrent sequence initialized with g n,1

[0] = 0 n , and satisfying the following property: for every i ∈ [1, |A| n -1], a unique integer j ∈ [1, n] exists such that, in both words g n,1

[i] and g n,1

[i-1] the corresponding characters in position j differ; in addition, the position j is chosen to be maximum in such a way that g n,1

[i] / ∈ {g n,1 [0] , • • • , g n,1 [i-1] }. Example 1.
In what follows we provide a column representation of g 2,1 and g 3,1 : By construction, for every n ≥ 1, each of the following identities holds:

g 2,
g n,1 [0] = 0 n , g n,1 [1] = 0 n-1 1, g n,1 [2 n -2] = 10 n-2 1, g n,1 [2 n -1] = 10 n-1 (1)
The

|A|-ary reflected Gray cycle

The preceding construction can be extended in order to obtain the so-called |A|ary reflected Gray code [START_REF] Cohn | Affine m-ary Gray codes[END_REF][START_REF] Er | On generating the N-ary reflected gray codes[END_REF], a σ 1 -Gray cycle over A n , which we denote by h n,1 . Set A = {0, • • • , p-1} and denote by θ the cyclic permutation (0, 1, . . . p-1). The sequence h n,1 is initialized with h n,1

[0] = 0 n . In addition, for every i ∈ [1, |A| n -1], a unique integer j exists such that c and d, the characters respectively in position j in h n,1

[i-1] and h n,1

[i] , satisfy both the following conditions:

(i) d = θ(c); (ii) j is the greatest integer in [1, n] such that h n,1 [i] / ∈ {h n,1 [0] , • • • , h n,1 [i-1] }.
Example 2. For A = {0, 1, 2} the sequence h 3,1 is the concatenation in this order of the three following subsequences: 3 The case where we have k ≥ 1 and |A| ≥ 3

h 3,
Let n ≥ k ≥ 1, p ≥ 3, and A = {0, 1, • • • , p-1}.
We will indicate the construction of a peculiar σ k -Gray cycle over A n , namely h n,k . This will be done by applying some induction over k ≥ 1: in view of that we set n 0 = n -k + 1. The starting point corresponds to h n0,1 , the p-ary reflected Gray code over A n0 as reminded in Sect. 2. For the induction stage, starting with some σ k-1 -Gray cycle over A n-1 , namely h n-1,k-1 , we compute the sequence h n,k as indicated in what follows: let i ∈ [0, p n -1], and let q ∈ [0, p -1], r ∈ [0, p n-1 -1] be the unique pair of non-negative integers such that i = qp n-1 + r. We set:

h n,k [i] = h n,k [qp n-1 +r] = θ q+r (0)h n-1,k-1 [r] (2)
As illustrated by Example 3, the resulting sequence h n,k is actually the concatenation in this order of p subsequences namely C 0 , . . . , C p-1 , with

C q = h n,k [qp n-1 +r] 0≤r≤p n-1 -1 , for each q ∈ [0, p -1]. Since θ is one-to-one, given a pair of different integers q, q ′ ∈ [0, p -1], for every r ∈ [0, p n-1 -1]
, in each of the subsequences C q , C q ′ , the words h n,k [qp n-1 +r] and h n,k [q ′ p n-1 +r] only differ in their initial characters, which respectively are θ q+r (0) and θ q ′ +r (0). In addition, since

h n-1,k-1 is a σ k-1 -Gray cycle over A n-1 , we have h n,k = p h n-1,k-1 = p n . Example 3. Let A = {0, 1, 2}, n = 3, k = 2, thus p = 3, n 0 = 2. By starting with the sequence h n-1,k-1 = h 2,1 , h n,k is the concatenation of C 0 , C 1 , and C 2 : h n-
Proposition 1. h n,k is a σ k -Gray cycle over A n .
Proof. We argue by induction over k ≥ 1. With regard to the base case, as indicated above h n0,1 is the |A|-ary reflected Gray sequence. In view of the induction stage, we assume that the finite sequence h n-1,k-1 is a σ k-1 -Gray cycle over A n-1 , for some k ≥ 2. (i) We start by proving that h n,k satisfies Condition (G2). This will be done through the three following steps:

(i.i) Firstly, we prove that, for each q ∈ [0, p -1], in the subsequence C q two consecutive terms are necessarily in correspondence under σ k . Given r ∈ [0, p n-1 -1], by definition, we have

θ r+q (0) ∈ σ 1 θ r+q-1 (0) . Since h n-1,k-1 sat- isfies Condition (G2), we have h n-1,k-1 [r] ∈ σ k-1 h n-1,k-1 [r-1]
. We obtain θ r+q (0

)h n-1,k-1 [r] ∈ σ k θ r+q-1 (0)h n-1,k-1 [r-1]
, thus according to (2):

h n,k [qp n-1 +r] ∈ σ k h n,k [qp n-1 +r-1] . (i.
ii) Secondly, we prove that, for each q ∈ [1, p-1], the last term of C q-1 and the initial term of C q are also connected by σ k . Take r = 0 in Eq. ( 2): it follows from θ p n-1 = id A that we have h n,k

[qp n-1 ] = θ q (0)h n-1,k-1 [0] = θ p n-1 +q (0)h n-1,k-1 [0]
.

In (2) take r = p n-1 -1, moreover substitute q -1 ∈ [0, p -2] to q ∈ [1, p -1]: we obtain h n,k [qp n-1 -1] = θ q+p n-1 -2 (0)h n-1,k-1 [p n-1 -1] . It follows from p = |A| ≥ 3 that θ(0) = θ -2 (0): since θ is one-to-one this implies θ q+p n-1 (0) = θ q+p n-1 -2 (0), thus θ q+p n-1 (0) ∈ σ 1 θ q+p n-1 -2 (0) . By induction we have h n-1,k-1 [0] = σ k-1 h n-1,k-1 [p n-1 -1] , thus h n,k [qp n-1 ] ∈ σ k θ q+p n-1 -2 (0)h n-1,k-1 [qp n-1 -1] that is, h n,k [qp n-1 ] ∈ σ k h n,k [qp n-1 -1]
. (i.iii) At last, we prove that the first term of C 0 is an image under σ k of the last term of C p-1 . In Eq. ( 2), take q = 0 and r = 0: we obtain h n,k

[0] = 0h n-1,k-1

[0]
.

Similarly, by setting q = p -1 and r = p n-1 -1, we obtain h n,k

[(p-1)p n-1 +p n-1 -1] = θ p n-1 +p-2 (0)h n-1,k-1 [p n-1 -1] , thus h n,k [p n -1] = θ -2 (0)h n-1,k-1 [p n-1 -1] . Since h n-1,k-1 is a σ k-1 - Gray cycle over A n-1 , we have h n-1,k-1 [0] ∈ σ k-1 h n-1,k-1 [p n-1 -1]
. In addition, it follows from p ≥ 3, that θ -2 (0) = 0, thus 0 ∈ σ 1 θ -2 (0) . We obtain

h n,k [0] ∈ σ k θ -2 (0)h n-1,k-1 [p n-1 -1] , thus h n,k [0] ∈ σ k h n,k [p n -1]
that is, the required property. (ii) Now, we prove that, in the sequence h n,k all terms are pairwise different.

Let i, i ′ ∈ [0, p n -1] such that h n,k [i] = h n,k [i ′ ] and consider the unique 4-tuple of integers q, q ′ ∈ [0, p -1], r, r ′ ∈ [0, p n-1 -1] such that i = qp n-1 + r and i ′ = q ′ p n-1 + r ′ . According to (2) we have θ q+r (0)h n-1,k-1 [r] = θ q ′ +r ′ (0)h n-1,k-1 [r ′ ]
, thus

θ q+r (0) = θ q ′ +r ′ (0) ∈ A and h n-1,k-1 [r] = h n-1,k-1 [r ′ ]
. Since h n-1,k-1 satisfies (G3), the second equation implies r = r ′ , whence the first one implies θ q (0) = θ q ′ (0), thus q = q ′ mod p. Since we have q, q ′ ∈ [0, p -1] we obtain q = q ′ , thus i = i ′ .

(iii) Finally, since h n,k satisfies (G3), we have 0≤i≤p n -1 {h n,k [i] } = p n , hence h n,k satisfies Condition (G1). [START_REF] Cohn | Affine m-ary Gray codes[END_REF] The case where A is a binary alphabet, with k odd Let A = {0, 1} and n ≥ k. Classically, the cyclic permutation θ, which was introduced in Sect. 2, can be extended into a one-to-one monoid homomorphism onto A * : in view of this, we set θ(ε) = ε and, for any non-empty n-tuple of characters a

1 , • • • , a n ∈ A, θ(a 1 • • • a n ) = θ(a 1 ) • • • θ(a n ).
Trivially, in the case where we have n = k, if a non-empty σ k -Gray code exists over X ⊆ A n , then we have X = {x, θ(x)}, for some x ∈ A n . In the sequel of the paper, we assume n ≥ k + 1. In what follows, we indicate the construction of a peculiar pair of σ k -Gray cycles over A n , namely γ n,k and ρ n,k . This will be done by induction over k ′ , the unique non-negative integer such that k = 2k ′ +1. Let n 0 = n-2k ′ = n-k+1.

-For the base case, γ n0,1 and ρ n0,1 are computed by applying some reversal (resp., shift) over the sequence g n0,1 from Sect. 2:

γ n0,1 [0] = g n0,1
[0] and γ n0,1

[i] = g n0,1 [2 n 0 -i] (1 ≤ i ≤ 2 n0 -1); (3) ρ n0,k [0] = g n0,1 [2 n 0 -1] and ρ n0,k [i] = g n0,1 [i-1] (1 ≤ i ≤ 2 n0 -1). ( 4
)
By construction, γ n0,1 and ρ n0,1 are σ 1 -Gray cycles over A n0 . Moreover we have:

γ n0,1 [0] = g n0,1 [0] = 0 n0 and ρ n0,1 [0] = g n0,1 [2 n 0 -1] = 10 n0-1 ; (5) γ n0,1 [2 n 0 -1] = g n0,1 [1] = 0 n0-1 1 and ρ n0,1 [2 n 0 -1] = g n0,1 [2 n 0 -2] = 10 n-2 1. ( 6
)
Example 4. For n 0 = 3 we obtain the following sequences: -In view of the induction step, we assume that we have computed the σ k -Gray cycles γ n,k and ρ n,k . Notice that we have

g 3,
n+ 2 = n 0 + 2(k ′ + 1) = n 0 + (k + 2)-1:
below we explain the construction of the two corresponding 2 n+2 -term sequences γ n+2,k+2 and ρ n+2,k+2 . Let i ∈ [0, 2 n+2 -1], and let q ∈ [0, 3], r ∈ [0, 2 n -1] be the unique pair of integers such that i = q2 n + r. Since we have r ∈ [0, 2 n -1], taking for q the value q = 0 (resp., 1, 2, 3), we state the corresponding equation (7a) (resp., (7b),(7c),(7d) ):

γ n+2,k+2 [r] = θ r (00)γ n,k [r] ; (7a) γ n+2,k+2 [2 n +r] = θ r (01)ρ n,k [r] ; (7b) γ n+2,k+2 [2.2 n +r] = θ r (11)γ n,k [r] ; (7c) γ n+2,k+2 [3.2 n +r] = θ r (10)ρ n,k [r] . (7d)
Similarly the sequence ρ n+2,k+2 is computed by substituting, in the preceding equations, the 4-tuple (10, 11, 01, 00) to (00, 01, 11, 10):

ρ n+2,k+2 [r] = θ r (10)γ n,k [r] ; (8a) ρ n+2,k+2 [2 n +r] = θ r (11)ρ n,k [r] ; (8b) ρ n+2,k+2 [2.2 n +r] = θ r (01)γ n,k [r] ; (8c) ρ n+2,k+2 [3.2 n +r] = θ r (00)ρ n,k [r] . ( 8d
)
Example 5. (Example 4 continued) γ 5,3 is the concatenation, in this order, of the 4 following subsequences: Lemma 1. γ n,k and ρ n,k satisfy both the conditions (G1) and (G3).

γ 3,
Proof. We argue by induction over k ′ ≥ 0, with k = 2k ′ + 1. the base case corresponds to k ′ = 0 that is, k = 1 and n = n 0 : as indicated above, γ n0,1 and ρ n0,1 are σ 1 -Gray cycles over A n . In view of the induction step we assume that, for some k ′ ≥ 0, both the sequences γ n,k and ρ n,k are σ k -Gray cycles over A n . (i) In order to prove that γ n+2,k+2 satisfies Condition (G3), let

i, i ′ ∈ [0, 2 n+2 -1] such that γ n+2,k+2 [i]
= γ n+2,k+2

[i ′ ]
, and

q, q ′ ∈ [0, 3], r, r ′ ∈ [0, 2 n -1] such that i = q2 n + r, i ′ = q ′ 2 n + r ′ . According to Eqs. (7a)-(7d), words x, x ′ ∈ A 2 , w, w ′ ∈ A n exist such that γ n+2,k+2 [i] = θ r (x)w and γ n+2,k+2 [i ′ ] = θ r ′ (x ′ )w ′ that is, θ r (x) = θ r ′ (x ′ ) ∈ A 2 and w = w ′ .
By the definition of θ, this implies either x, x ′ ∈ {00, 11} or x, x ′ ∈ {01, 10} that is, by construction, either q, q ′ ∈ {0, 2},

x, x ′ ∈ {00, 11}, w = γ n,k [r] = γ n,k [r ′ ] , or q, q ′ ∈ {1, 3}, x, x ′ ∈ {01, 10}, w = ρ n,k [r] = ρ n,k [r ′ ]
. Since γ n,k and ρ n,k satisfies (G3), in any case we have r = r ′ . This implies θ r (x) = θ r (x ′ ), thus x = x ′ . With regard to Eqs. (7a)-(7d), this corresponds to q = q ′ , thus i = q2 n + r = q ′ 2 n + r = i ′ , therefore γ n+2,k+2 satisfies Condition (G3). (ii) By substituting [START_REF] Gilbert | Gray codes and paths on the N-cube[END_REF][START_REF] Joichi | Combinatorial Gray codes[END_REF], 01, 00) to (00, 01, 11, 10), according to (8a)-(8d), similar arguments prove that ρ n+2,k+2

[i] = ρ n+2,k+2 [i ′ ]
implies i = i ′ , thus ρ n+2,k+2 also satisfies (G3). (iii) Since γ n+2,k+2 satisfies (G3), we have 0≤i≤2 n+2 -1 {γ n+2,k+2 i } = A n+2 , hence it satisfies (G1). Similarly, since ρ n+2,k+2 satisfies (G3) it satisfies (G1).

In order to prove that our sequences satisfy (G2), we prove the following property:

Lemma 2. We have γ n,k [0] ∈ σ k+1 ρ n,k [2 n -1] and ρ n,k [0] ∈ σ k+1 γ n,k [2 n -1] .
Proof. We argue by induction over the integer k ′ ≥ 0. The case k ′ = 0 corresponds to k = 1 and n = n 0 : with such a condition, our property comes from the identities ( 5) and [START_REF] Eades | An algorithm for generating subsets of fixed size with a strong minimal change property[END_REF]. For the induction step, we assume that, for some k ′ ≥ 0,

we have γ n,k [0] ∈ σ k+1 ρ n,k [2 n -1] and ρ n,k [0] ∈ σ k+1 γ n,k [2 n -1]
. (i) In (7a), by taking r = 0 we obtain γ n+2,k+2

[0] = 00γ n,k

[0] , hence by induction:

γ n+2,k+2 [0] ∈ 00σ k+1 ρ n,k [2 n -1] ⊆ σ k+3 11ρ n,k [2 n -1]
. By setting r = 2 n -1 in (8d), we obtain ρ n+2,k+2

[2 n+2 -1] = 11ρ n,k [2 n -1] , thus γ n+2,k+2 [0]
∈ σ k+3 ρ n+2,k+2 [2 n+2 -1] . (ii) Similarly, by setting r = 0 in (8a), and by induction we have: ρ n+2,k+2

[0] = 10γ n,k [0] ∈ σ k+3 01ρ n,k [2 n -1] . By taking r = 2 n -1 in (7d) we obtain γ n+2,k+2 [2 n+2 -1] = 01ρ n,k [2 n -1] , thus ρ n+2,k+2 [0] ∈ σ k+3 γ n+2,k+2 [2 n+2 -1] .
Since Eqs. (7a)-(8d) look alike, one may be tempted to compress them thanks to some unique generic formula. Based on our tests, such a formula needs to introduce at least two additionnal technical parameters, which would make their handling tedious. In the proof of the following result, we have opted to report some case-by-case basis argumentation: this has the advantage of making use of arguments which, although being similar, actually are easily readable.

Proposition 2. Both the sequences γ n,k and ρ n,k are σ k -Gray cycles over A n .

Proof sketch For the full proof, once more we argue by induction over k ′ ≥ 0. Since γ n0,1 and ρ n0,1 are σ 1 -Gray cycles over A n , the property holds for k ′ = 0. In view of the induction stage, we assume that, for some k ′ ≥ 0 both the sequences γ n,k and ρ n,k are σ k -Gray cycles over A n . According to Lemma 1, it remains to establish that γ n+2,k+2 and ρ n+2,k+2 satisfy Condition (G2) that is:

(∀q ∈ {0, 1, 2, 3})(∀r ∈ [1, 2 n -1]) γ n+2,k+2 [q2 n +r] ∈ σ k+2 γ n+2,k+2 [q2 n +r-1] ; (9)
(∀q ∈ {1, 2, 3}) γ n+2,k+2

[q2 n ] ∈ σ k+2 γ n+2,k+2 [q2 n -1] ; (10)
γ n+2,k+2 [0] ∈ σ k+2 γ n+2,k+2 [2 n+2 -1] . (11)
(∀q ∈ {0, 1, 2, 3})(∀r ∈ [1, 2 n -1]) ρ n+2,k+2 [q2 n +r] ∈ σ k+2 ρ n+2,k+2 [q2 n +r-1] ; (12)
(∀q ∈ {1, 2, 3}) ρ n+2,k+2 [q2 n ] ∈ σ k+2 ρ n+2,k+2 [q2 n -1] ; (13)
ρ n+2,k+2 [0] ∈ σ k+2 ρ n+2,k+2 [2 n+2 -1] . (14)
Condition [START_REF] Fredricksen | Necklaces of beads in k colors and k-ary de Bruijn sequences[END_REF]. (i) At first assume q = 0. According to (7a), and since γ n,k satisfies (G2), we have γ n+2,k+2

[r]

= θ r (00)γ n,k [r] ∈ θ r (00)σ k γ n,k [r-1] , thus γ n+2,k+2 [r] ∈ σ k+2 θ r-1 (00)γ n,k [r-1] . In (7a), substitute r -1 to r (we have 0 ≤ r -1 ≤ 2 n -2): we obtain γ n+2,k+2 [r-1] = θ r-1 (00)γ n,k [r-1] , thus γ n+2,k+2 [r] ∈ σ k+2 γ n+2,k+2 [r-1]
.

(ii) Now assume q = 1. According to (7b), and since ρ n,k satisfies (G2), we have

γ n+2,k+2 [2 n +r] = θ r (01)ρ n,k [r] ∈ σ k+2 θ r-1 (01)ρ n,k [r-1]
. In (7b), susbtitute r -1 to r: we Since k -1 is an odd integer, according to Proposition 2, the sequence γ n-1,k-1 is a σ k-1 -Gray cycle over A n-1 . We set:

(∀i ∈ [0, 2 n-1 -1]) γ n,k [i] = θ i (0)γ n-1,k-1 [i] and γ n,k [i] = θ i (1)γ n-1,k-1 [i] (15)
For instance, we have γ 6,4

[0] = 000000, γ 6,4

[0] = 100000, γ 6,4

[1] = 111100..

Proposition 3. γ n,k (resp., γ n,k ) is a σ k -Gray cycle over Even n 1 (resp., Odd n 1 ).
Proof. (i) According to Eq. ( 15), since γ n-1,k-1 satisfies (G3), both the sequences γ n,k and γ n,k also satisfy (G3).

(ii) By Lemma 3, we have 0≤i≤2 n -1 γ n,k ⊆ Even n 1 and 0≤i≤2 n -1 γ n,k ⊆ Odd n 1 . In addition, according to (15), we have

γ n,k = γ n,k = γ n-1,k-1 = 2 n-1 . This implies 0≤i≤2 n -1 γ n,k = Even n 1 and 0≤i≤2 n -1 γ n,k = Odd n 1 that is, γ n,k and γ n,k satisfy (G1). (iii) Let i ∈ [1, 2 n-1 -1]. Since γ n-1,k-1 satisfies (G2), we have γ n-1,k-1 [i] ∈ σ k-1 γ n-1,k-1 [i-1]
. According to [START_REF] Lehmer | The machine tools of combinatorics[END_REF], the initial characters of γ n,k

[i] and γ n,k

[i-1] (resp., γ n,k [i] and γ n,k [i-1] ) are different, hence we have γ n,k [i] ∈ σ k γ n,k [i-1] and γ n,k [i] ∈ σ k γ n,k [i-1]
. In addition, once more according to [START_REF] Lehmer | The machine tools of combinatorics[END_REF] it follows from γ n-1,k-1

[0] ∈ σ k-1 γ n-1,k-1 [2 n-1 -1] that γ n,k [0] = 0γ n-1,k-1 [0] ∈ σ k 1γ n-1,k-1 [2 n-1 -1] ⊆ σ k γ n,k [2 n-1 -1]
, hence γ n,k satisfies (G2). Similarly, γ n-1,k-1

[0] ∈ σ k-1 γ n-1,k-1 [2 n-1 -1] implies γ n,k [0] ∈ σ k γ n,k
[2 n-1 -1] , hence γ n,k satisfies (G2).

The following statement provides the description of the complexity λ A,τ : (iv) |A| = 2, n ≥ k + 1, k is even, and λ A,σ k (n) = 2 n-1 . In addition, in each case some σ k -Gray cycle of maximum length can be explicitly computed.

Proof. Recall that if some σ k -Gray cycle exists over X ⊆ A ≤n , necessarily X is a uniform set that is, X ⊆ A m holds for some m ≥ n; hence, in any case we have λ A,σ k (n) ≤ |A| n . According to Proposition 1, if we have |A| ≥ 3 and n ≥ k, a σ k -Gray cycle exists over A n , hence Property (i) holds. Similarly, (iii) comes from Proposition 2. As indicated in the preamble of Sect. 3, Property (ii) trivially holds. Finally, according to Lemma 3, given a binary alphabet A, if k is even we have λ A,σ k (n) ≤ 2 n-1 , hence (iv) comes from Proposition 3.

Further development Since our Gray cycles were constructed by applying recursive processes, it is legitimate to ask whether some method could exist for computing γ n,k

[i] by directly starting with γ n,k [i-1] , as in the case of the classical reflected Gray cycles. In view of some of our more recent studies, we strongly believe that such algorithms can actually be devised: we hope to develop this point in a further paper.

On the other hand, it could be of interest to study the behaviour of Λ A,τ in the framework of other word binary relations τ , even in restraining to special families of sets X ⊆ A * , such as variable-length codes.

Theorem 1 .

 1 Given a finite alphabet A and n ≥ k ≥ 1, exactly one of the four following properties holds:(i) |A| ≥ 3, n ≥ k, and λ A,σ k (n) = |A| n ; (ii) |A| = 2, n = k, and λ A,σ k (n) = 2; (iii) |A| = 2, n ≥ k + 1, k is odd and λ A,σ k (n) = 2 n ;

obtain γ n+2,k+2

[2 n +r-1] = θ r-1 (01)ρ n,k [r-1] , thus γ n+2,k+2

∈ σ k+2 γ n+2,k+2 [2 n +r-1] . (iii) For q = 2, the arguments are similar to those applied in (i) by substituting γ n+2,k+2

[2•2 n +r] to γ n+2,k+2

[r]

, Eqs. (7c) to (7a), and 11 to 00.

(iv) Similarly, for q = 3 the proof is obtained by substituting in (ii) γ n+2,k+2

[2 n +r] , (7d) to (7b), and 10 to 01. Condition [START_REF] Gilbert | Gray codes and paths on the N-cube[END_REF]. (i) Assume q = 1 and take r = 0 in (7b). According to Lemma 2, we obtain γ n+2,k+2

.

(ii) Now, assume q = 2, and set r = 0 in Eq. (7c). According to Lemma 2 we have

, Eq. (7d) to Eq. ( 7b), (7c) to (7a), 10 to 01 and 00 to 11: similar arguments prove that γ n+2,k+2

Condition [START_REF] Joichi | Combinatorial Gray codes[END_REF]. Take r = 0 in (7a). According to Lemma 2, we have γ n+2,k+2

According to the structures of Eqs. (8a)-(8d), for proving the conditions ( 12)-( 14), the method consists in substituting the word ρ n+2,k+2

[r]

to γ n+2,k+2

[r]

, the 4-uple (10, 11, 01, 00) to (00, 01, 11, 10), and Eq. (8a) (resp., (8b), (8c), (8d)) to Eq. (7a) (resp., (7b), (7c), (7d)).

5

The case where we have |A| = 2 and k even Beforehand, we remind some classical algebraic interpretation of the substitution σ k in the framework of the binary alphabet A = {0, 1}. Denote by ⊕ the addition in the group Z/2Z with identity 0. Given a positive integer n, and w, w ′ ∈ A n , define w ⊕ w ′ as the unique word of A n such that, for each i ∈ [1, n]:

With this notation the sets A n and (Z/2Z) n are in oneto-one correspondence. Moreover we have w ′ ∈ σ k (w) if, and only if, some word u ∈ A n exists such that |u| 1 = k and w = w ′ ⊕u, therefore if k is even we have