Cathy Mc Fadden
email: cathy.mcfadden@ucd.ie

Marcus Greferath
email: marcus.greferath@ucd.ie

Jens Zumbrägel
email: jens.zumbragel@ucd.ie

Characteristics of Invariant Weights Related to Code Equivalence over Rings

Keywords: MacWilliams' Equivalence Theorem, Extension Theorem, Weights, Ring-Linear Codes

.

Introduction

Two linear codes of the same length over a given alphabet are said to be equivalent if there exists a (weight preserving) monomial transformation mapping one to the other. MacWilliams in her Equivalence Theorem [START_REF] Macwilliams | A theorem on the distribution of weights in a systematic code[END_REF] proved that when the alphabet is a finite field any linear Hamming isometry between linear codes will extend to a monomial transformation. Thus the equivalence question can be seen as an extension problem. A character theoretic proof of this Extension Theorem in [START_REF] Ward | Characters and the equivalence of codes[END_REF] led to a generalisation of this theorem for codes over finite Frobenius rings in [START_REF] Wood | Extension theorems for linear codes over finite rings, Applied algebra, algebraic algorithms and error-correcting codes[END_REF]. Indeed in [START_REF]Code equivalence characterizes finite Frobenius rings[END_REF] it was shown that linear Hamming isometries extend precisely when the ring is Frobenius.

In the seminal paper on ring linear coding [START_REF] Hammons | The Z4-linearity of Kerdock, Preparata, Goethals, and related codes[END_REF] it was already noticed that weights other than the Hamming weight would play a significant role, such as the Lee weight over Z 4 . The concept of a homogenous weight was first introduced in [START_REF] Constantinescu | Monomial extensions of isometries between codes over Zm[END_REF] where a combinatorial proof of the Extension Theorem for this weight and codes over Z m is provided. In [START_REF] Greferath | Finite-ring combinatorics and MacWilliams' equivalence theorem[END_REF] we see that every homogeneous isometry is a Hamming isometry yielding the Extension Theorem for homogeneous weight and codes over finite Frobenius rings. This paper followed the combinatorial tack of [START_REF] Constantinescu | Monomial extensions of isometries between codes over Zm[END_REF] for the Z m case. For the more general case of codes as quasi-Frobenius modules the Extension Theorem holds for Hamming weight as seen in [START_REF] Greferath | Finite quasi-Frobenius modules and linear codes[END_REF].

Following from the chain ring result of [START_REF] Greferath | On weights allowing for MacWilliams equivalence theorem[END_REF], obtained by examining the generation of invariant weights, in [START_REF]Monomial extensions of isometries of linear codes II: Invariant weight functions on Zm[END_REF] a complete characterisation of those weights for which the Equivalence Theorem holds for codes over Z m is supplied. Here we extend the ideas of that paper to more general rings, outlining a strategy for attaining necessary and sufficient conditions for a weight to satisfy the Extension Theorem.

We begin in Section 1 with defining codes, weights and the equivalence condition for the ring case. In Section 2 we revise some key properties of chain rings and provide a thorough introduction to the Möbius Function. In Section 3 we describe the structural context so crucial to the elegance and seeming simplicity of our results. Finally in Section 4 we provide a concise condition for an invariant weight to satisfy the generalised MacWilliams' Equivalence Theorem.

Weight Functions and the Equivalence Theorem

In all of our discussion let R be a finite associative ring with identity 1. Denote by R × the group of invertible elements of R. By a weight on R we mean any function w : R → C satisfying w(0) = 0. The left symmetry group of w is Sym L (w) := {u ∈ R × | w(x) = w(ux) ∀x ∈ R} and the right symmetry group is Sym R (w) := {u ∈ R × | w(xu) = w(x) ∀x ∈ R} . The weight w is called invariant if both of these symmetry groups are maximal, i.e. if they coincide with R × . Note if Sym L (w) = R × we have Rx = Ry implies w(x) = w(y). Definition 1. An invariant weight w on R is called homogeneous, if there exists a real number c ≥ 0 such that for all x ∈ R there holds:

y∈Rx w(y) = c |Rx| if x = 0 .
The concept of a homogeneous weight was originally introduced in [START_REF] Constantinescu | On the concept of code-isomorphy[END_REF] and further generalised in [START_REF] Greferath | Finite-ring combinatorics and MacWilliams' equivalence theorem[END_REF] in such a way that homogeneous weights exist for every finite ring. There are several definitions of homogeneous and prehomogeneous weights, particularly for more general codes as modules as given in [START_REF] Nechaev | Fully weighted modules and representations of codes[END_REF]. We now define the normalised homogeneous weight w hom . Definition 2. The normalised homogeneous weight w hom : R → R is given by

w hom (x) = 1 - µ(0, Rx) |R × x| ,
where µ is the Möbius function on the lattice of principal ideals of R, defined in the following section, and |R × x| counts the number of generators of the ideal Rx.

Given a positive integer n, any weight w : R → C shall be extended to a function on R n by defining w(x)

:= w(x 1 ) + w(x 2 ) + • • • + w(x n ) for x ∈ R n . Suppose that C is a linear code of length n over R , i. e. an R-submodule of R n . A linear map φ : C → R n is called a w-isometry if w(φ(x)) = w(x) for all x ∈ C.
A bijective module homomorphism φ : R n → R n is called a monomial transformation if there exists a permutation π of {1 . . . n} and units u 1 , . . . ,

u n ∈ R × such that φ(x) = (x π(1) u 1 , . . . , x π(n) u n ) for every x = (x 1 , . . . , x n ) ∈ R n . If all the units u i are contained in a subgroup G of R × we call it a G-monomial transformation.
Clearly any Sym R (w)-monomial transformation will be a w-isometry for any weight w and hence restricts to a w-isometry on every linear code C ⊆ R n . Conversely we may ask if a given linear w-isometry φ : C → R n , defined on a linear subcode C of R n is a restriction of an appropriate monomial transformation of R n . This is the essence of MacWilliams' Equivalence Theorem: Theorem 3 (MacWilliams [START_REF] Macwilliams | A theorem on the distribution of weights in a systematic code[END_REF]). Every linear Hamming isometry between linear codes of the same length over a finite field can be extended to a monomial transformation of the ambient vector space. Definition 4. Suppose w is an arbitrary weight. We say that MacWilliams' Equivalence Theorem (or the Extension Theorem) holds for w if for any positive integer n, any linear code C in R n and any linear w-isometry φ : C → R n there exists a Sym R (w)-monomial transformation of R n which extends φ.

An obvious necessary condition for MacWilliams' Equivalence Theorem to hold for a weight w on R is that all w-isometries are injective.

Chain Rings and Möbius Inversion

In the following sections we will harness the power of Möbius Inversion to prove our most vital results. For this reason we begin with a short primer, for more details see [START_REF] Roman | Coding and information theory[END_REF]. First we include a brief summary of the key properties of chain rings (c.f. [START_REF] Lang | Algebra[END_REF], [START_REF] Bernard | Finite rings with identity[END_REF], [START_REF] Kasch | Modules and rings[END_REF]). Definition 5. A ring R is called a left chain ring if the lattice of left ideals of R form a chain under the partial ordering of inclusion. Similarly for right chain ring. If R is both a left and right chain ring then it is called a chain ring.

The following theorem, combining Theorem 1.1 of [START_REF] Nechaev | Finite rings of principal ideals[END_REF] and Lemma 1 of [START_REF] Clark | Finite chain rings[END_REF], demonstrates the numerous equivalent definitions of a finite chain ring, so giving us a variety of different approaches to studying chain rings. Recall a principal left ideal ring is a ring with identity in which each left ideal is left principal, and a principal ideal ring is a ring which is both a principal left ideal ring and a principal right ideal ring. Theorem 6. The following are equivalent:

(i) R is a local principal ideal ring. (ii) R is a left chain ring. (iii) R is a chain ring.
(iv) R is a local ring and rad(R) is a left principal ideal.

(v) Every one-sided ideal of R is two-sided and belongs to the chain R ⊲ rad(R) ⊲ ... ⊲ rad(R) n-1 ⊲ rad(R) n = {0}, for some n ∈ N.

Remark 7. Note that in the above if n > 1, then we have rad(R

) i = Rπ i = π i R for any π ∈ rad(R)\rad(R) 2 , i ∈ {1 . . . n}. Also any element a ∈ R can be decomposed uniquely into a representation a = a 0 + a 1 π + • • • + a n-1 π n-1
, where the a i are from a co-ordinate set Γ . This is called the π-adic representation of a. Wood noted in [START_REF]Factoring the semigroup determinant of a finite commutative chain ring, Coding theory, cryptography and related areas[END_REF] that

rad(R) i \rad(R) i+1 = R × π i = π i R × .
This property extends in a natural way to finite direct products of chain rings and, combined with our structural approach, facilitates the proof of the main theorems herein.

It is fitting to begin our discussion of the Möbius function in the context of the incidence algebra. We describe the incidence algebra of a finite partially ordered set. Note that locally finite is sufficient for the following definitions. Definition 8. Let P be a finite partially ordered set and F a field. Set

A(P ) = {f : P × P -→ F | f (x, y) = 0 if x y} ,
with addition and scalar multiplication defined by (f + g)(x, y) = f (x, y) + g(x, y) (kf )(x, y) = kf (x, y) .

Also define multiplication by:

(f ⊙ g)(x, y) = x≤z≤y f (x, z)g(z, y) .

Then A(P ) is an algebra, called the incidence algebra of P , with identity δ(x, y) := 1 : x = y 0 : otherwise . Theorem 12. Let P , F, and µ be as above and let f, g be functions from P to F. If P has least element 0 then:

Theorem 9. An element f ∈ A(P ) has a multiplicative inverse if and only if

f (x, x) = 0 ∀x ∈ P . If g is the inverse of f then g(x, x) = 1 f (x,
g(x) = y≤x f (y) for all x ∈ P ⇔ f (x) = y≤x g(y)µ(y, x) for all x ∈ P .
If additionally the partially ordered set P has a greatest element 1 then g(x) = x≤y f (y) for all x ∈ P ⇔ f (x) = x≤y g(y)µ(x, y) for all x ∈ P .

Convolution and Correlation

We now describe a structural context for proving the Extension Theorem. Two key operations, convolution and correlation, allow us to define a module of weights over an algebra of complex functions. Consider the set C R of all functions {f | f : R → C}. If for f, g elements of C R and for c ∈ C we define addition and scalar multiplication by

(f + g)(x) := f (x) + g(x) (cf )(x) := cf (x) . then V = [C R , +, 0; C] is a C-vector space.
Definition 13. Let f and g be elements of C R . We define the multiplicative convolution of f and g, f

* g : C R × C R -→ C R by (f * g)(x) := a,b∈R, ab=x f (a)g(b)
.

where g = f + Cδ 0 is any element of C 0 [R] and w ∈ V 0 . Similarly there exists a left action via ⊛ ′ . For any function f ∈ C[R] we can define left and right symmetry groups as we did for weights: Sym R (f

) := {u ∈ R × | f (xu) = f (x) ∀x ∈ R}. It follows Sym L (f * g) ⊇ Sym L (f ) and Sym R (f * g) ⊇ Sym R (g).
Lemma 20. Symmetry groups are inherited as follows for correlation

Sym L (w ⊛ g) ⊇ Sym R (g) Sym R (f ⊛ ′ w) ⊇ Sym L (f ). Lemma 21. Define S = {f ∈ C 0 [R] | f (xu) = f (x) ∀x ∈ R, u ∈ R × }
and let the invariant weights from Section 1 be denoted by W . Then W is a right S-module under correlation ⊛ in a naturally inherited way.

MacWilliams' Extension Theorem by Module Generation

We re-examine the Extension Theorem with this new perspective. We aim to classify all weights that generate W as a right S-module. This will then yield MacWilliams' Equivalence Theorem for these weights due to the following results, equivalent to those in [START_REF] Greferath | On weights allowing for MacWilliams equivalence theorem[END_REF].

Lemma 22. If φ is a w-isometry then φ is a (w ⊛ s)-isometry for all s ∈ S.

Remark 23. Let R be a Frobenius ring. If w ⊛ S = W then w ⊛ h = w H for some h ∈ S where w H denotes the Hamming weight. Since every w-isometry is a w ⊛ h isometry, by Lemma 22, we have that MacWilliams' Extension Theorem holds for w.

Let the ring R be a finite product of finite chain rings R i , say

R = R 1 × R 2 × • • • × R r ,
with Jacobson radicals generated by (distinct) p 1 , p 2 , . . . , p r of nilpotency d 1 , d 2 , . . . , d r respectively. We view elements of R as r-tuples of chain ring elements i.e. a ∈ R represented as a = (a 1 , a 2 , . . . , a r ) where each a i ∈ R i . Operations, including multiplication, are performed component-wise. The set of generators of the ideals of R is given by {R × e | e ∈ E} where E are the representatives

E = {p 1 e1 p 2 e2 . . . p r er = e | 0 ≤ e i ≤ d i }.
The lattice of principal left ideals of R may be described by

E( R R) = {Re | e ∈ E}.
We have for x, y ∈ E the relations x ≤ y ⇔ x i ≤ y i ∀i and hence Rx ≥ Ry ⇔ x i ≤ y i ∀i. The socle of any R-module M is the sum of the minimal submodules of M . When M is the ring itself this is the sum of the minimal ideals. Here the representative of the socle is s = p 1 d1-1 p 2 d2-1 . . . p r dr-1

since Soc(R × S) =Soc(R)×Soc(S).

Definition 24. For each e ∈ E define the basis element

δ e := 1 |R × e| a∈R × e δ a .
Denote by z/x ∈ E the representative generator a ∈ E with a i = z i -x i ∀i. We define a basis {η x | x ∈ E\{0}} by

η x := Rz≤Rx µ(0, Rz)δ z x ,
where µ is the Möbius function induced by the lattice of left principal ideals under the partial order of inclusion.

Lemma 25. The Möbius function elements contained in η x are, for all e ∈ E, µ(0, Re) = (-1) Σ(di-ei) : e ≤ s 0 : e s .

Since µ(0, Rz) = 0 for Rz Soc(R) we need only include those z with indices

z i = d i or z i = d i -1 in the sum.
Proposition 26.

(w ⊛ η x )(y) = z≤x µ(0, Rz)w( zy x ) : y ≤ x 0 : y x .

Thus the matrix of coefficients of the weight w with respect to the basis {η x | x ∈ E\{0}} is triangular. We require for w to generate W that the diagonal elements are nonzero, indeed this is sufficient. Combining all of these elements we arrive at our main theorem.

Theorem 27. Let R be a finite direct product of finite chain rings with E the set of representatives of the ideals of R. If w ∈ W with z≤x µ(0, Rz)w(z) = 0 for all x ∈ E\{0} , then MacWilliams' Equivalence Theorem holds for w.

We remark that a finite commutative ring is a direct product of chain rings if and only if it is a principal ideal ring. Hence the theorem applies in particular to finite commutative principal ideal rings.

Conclusion

By considering the module of invariant weights in terms of an algebra of complex functions we have determined the conditions an invariant weight defined on a direct product of chain rings must satisfy for MacWilliams' equivalence theorem to hold. Thus provided these conditions are satisfied all isometries of that weight will extend to monomial transformations.

Definition 10 .Definition 11 .

 1011 x) and g(x, y) = -g(x, x) x<z≤y f (x, z)g(z, y) . We define the zeta function ζ ∈ A(P ) to be ζ(x, y) := 1 : x ≤ y 0 : otherwise . Its inverse is called the Möbius function which we now define. Consider a field F and a locally finite partially ordered set P with partial ordering ≤. The Möbius function, µ : P × P -→ F, is defined by any of the four equivalent statements: (i) µ(x, x) = 1 and x≤z≤y µ(z, y) = 0 for x < y (ii) µ(x, x) = 1 and x≤z≤y µ(x, z) = 0 for x < y (iii) µ(x, x) = 1 and µ(x, y) = -x<z≤y µ(z, y) for x < y (iv) µ(x, x) = 1 and µ(x, y) = -x≤z<y µ(x, z) for x < y

⋆ This work was partially supported by the Science Foundation Ireland under Grants 06/MI/006 and 08/IN.1/I1950.

Consider the function δ A , where A is a subset of R, defined by: δ A (x) := 1 : x ∈ A 0 : otherwise . Lemma 16. Let f, g, w ∈ C R , then convolution and correlation have the following relationships: Definition 19. We define the set V 0 to be those functions w in V which satisfy w(0) = 0.

V

As w ⊛ δ 0 = 0 for all w ∈ V 0 this induces a natural right action of C 0 [R] on V 0 by w ⊛ (f + Cδ 0 ) := w ⊛ f,


Eimear Byrne
email: ebyrne@ucd.ie

Marcus Greferath
email: marcus.greferath@ucd.ie

Jaume Pernas
email: jaume.pernas@uab.cat

Jens Zumbrägel
email: jens.zumbragel@ucd.ie

Algebraic Decoding of Negacyclic Codes over Z 4

Keywords: negacyclic code, integers modulo 4, Lee metric, Galois Ring, decoding, Gröbner bases, key equation, solution by approximations, module of solutions

We investigate Berlekamp's negacyclic codes and discover that these codes, when considered over the integers modulo 4, do not suffer any of the restrictions on the minimum distance observed in Berlekamp's original papers [2, 3]. We present an algebraic decoding algorithm for this class of codes that corrects any error pattern of Lee weight ≤ t. Our treatment uses Gröbner bases, the decoding complexity is quadratic in t.

Introduction

In his seminal papers [2,3], Berlekamp introduced negacyclic codes over odd prime fields GF(p), and designed a decoding algorithm that corrects up to t ≤ p-1 2 Lee errors. The main idea in Berlekamp's contribution is to represent error patterns of weight w solely by error locator polynomials of degree w, where the error values are encoded essentially in the multiplicity of the respective error locations. Berlekamp's error locator polynomial satisfies some type of key equation that is solved during the decoding procedure. Its solution ultimately depends on the multiplicative invertibility of all odd integers i ≤ 2t-1 in (a field extension of) GF(p) where t is the maximum Lee weight of all correctable error patterns. This finally requires t < p+1 2 , which is the reason why this idea yields only a very small class of useful codes.

The project underlying this article revisits Berlekamp's work and starts with the observation that almost all of the algebra used in the quoted papers is still valid in a Galois ring, i.e. a Galois extension of the integers modulo p m where m might be greater than 1. The divisibility condition mentioned above causes problems if and only if p is odd, and this brought us to the idea to study codes over Z 2 m .

The paper at hand considers the simplest (non-trivial) case, namely the case where m = 2, which means we consider negacyclic codes over Z 4 under the Lee metric. We will show that a negacyclic code is indeed of minimum Lee distance at least 2t + 1 if its generator polynomial has roots α, α 3 , . . . , α 2t-1 for a primitive 2nth root of unity α in a Galois extension of Z 4 . No restriction on t will be imposed. We present an algebraic decoding algorithm for this class of codes that corrects any error pattern of Lee weight ≤ t. In fact, if the minimum Lee distance is at least 2r + 1 (where r ≥ t), we derive a key equation which has a unique solution in all error patterns of Lee weight r. Then we find the unique solution using Gröbner bases, provided at most t errors have occured.

An extended version of this paper including all proofs is available online [START_REF] Byrne | Algebraic Decoding of Negacyclic Codes over Z4[END_REF].

Preliminaries

Throughout this paper, let R denote the Galois ring GR(4, m) of characteristic 4, order 4 m , and residue field K = GF(2 m ). We let µ : R -→ K, a → a + 2R be the canonical map from R onto K.

The structure of R is well understood (cf. [START_REF] Raghavendran | Finite associative rings[END_REF]). Its multiplicative group R × has order 2 m (2 m -1) and contains a unique cyclic subgroup of order 2 m -1. This group, in union with zero, forms the so-called Teichmüller set of R, which we denote by T . The set T forms a complete set of coset representatives of 2R in R and so the image of T under µ is the residue field K. Each element a ∈ R can be expressed in the canonical form a := a 0 + 2a 1 for suitable a 0 , a 1 ∈ T . The automorphism group of R is cyclic of order m and with respect to the above canonical form is generated by the map π : R -→ R, a 0 + 2a 1 → a 2 0 + 2a 2 1 . Note that for an element θ of T we have π(θ) = θ 2 .

Negacyclic Codes Over Z 4

The following is a BCH-like description of negacyclic codes over Z 4 , and can be read as the obvious extension of Berlekamp's work in [2,3]. We outline the theory for the convenience of the reader, see [START_REF] Wolfmann | Negacyclic and Cyclic Codes over Z n 4[END_REF] for further details. Definition 1. Let n be a positive integer. A negacyclic code of length n over Z 4 is an ideal in the ring Z 4 [x]/ x n +1 .

We will henceforth assume that n is odd. Then there is a primitive 2nth root of unity α in R such that α n = -1, i.e., α = -β, where β is a primitive nth root of unity in R.

Any Z 4 -negacyclic code is a principal ideal in Z 4 [x]/ x n + 1 , in fact it is generated by a polynomial of the form a(b + 2) ∈ Z 4 [x] where x n + 1 = abc and a, b, c are pairwise coprime polynomials, in which case the code has size 4 δc 2 δb where δf denotes the degree of the polynomial f (cf. [9, Th. 2.7]). There is a natural correspondence between cyclic and negacyclic codes over Z 4 . This is given by the map

λ : Z 4 [x]/ x n -1 -→ Z 4 [x]/ x n +1 , a(x) → a(-x) .
Clearly, λ is ring isomorphism, from which it follows that any ideal C in Z 4 [x]/ x n -1 is mapped to an ideal λ(C) of Z 4 [x]/ x n + 1 . Moreover, λ is an isometry with respect to the Lee distance, since for every 1 which is obviously of the same Lee weight as c.

c = c 0 + c 1 x + • • • + c n-1 x n-1 ∈ Z 4 [x]/ x n -1 , we have λ(c) = c 0 -c 1 x ± • • • + c n-1 x n-
Theorem 1. Let C be a negacyclic code over Z 4 of odd length n whose generator polynomial g has the roots α, α 3 , . . . , α 2t-1 for some primitive 2nth root of unity α ∈ R such that α n = -1. Then C has minimum Lee distance d Lee at least 2t+1.

Proof. Let D be the pre-image of C under λ. Then D is a cyclic code of length n, with generator polynomial f satisfying λ(f

) = g ∈ Z 4 [x]. Then f has the roots β, β 3 , . . . , β 2t-1 where β = -α is a primitive nth root of unity in R. Now f ∈ Z 4 [x] is fixed by the automorphism π, so that 0 = π(f (θ)) = f (π(θ)) for any root θ of f in R. Since β is contained in the Teichmüller set of R, f also has the roots π j (β i ) = β 2 j i for i ∈ {1, 3 . . . , 2t -1}.
Therefore, f has the 2t consecutive roots β, β 2 , . . . , β 2t . Therefore a generalization of the well-known BCH bound (see for example [4, Th. IV.1]) shows that D has minimum Hamming distance at least 2t + 1. This gives a trivial lower bound on the minimum Lee distance of D. The claim now follows from the above isometry observation.

⊓ ⊔ Remark 1. The lower bound on the Lee distance of negacyclic codes given in Theorem 1 is in general not sharp. Indeed there are codes C with d Lee > 2t + 1, as Table 1 shows. If the actual Lee distance is at least 2r + 1 with r > t we will see in the next section that the key equation carries sufficient information to determine all error pattern of Lee weight at most r, thus being able to correct up to r errors. We will then present a concrete decoding algorithm for error patterns up to Lee weight t.

The key equation

Let C be a negacyclic code with roots α, α 3 , . . . , α 2t-1 and minimum Lee distance

d Lee ≥ 2r + 1. Let v ∈ Z 4 [z] be a received word satisfying d(v, C) ≤ r.
We will design a decoder to retrieve the unique error polynomial e satisfying e = v -c for some codeword c, where e has Lee weight at most r. Most of what follows will be reminiscent of the according steps in Berlekamp's papers [2,3]. We will amend the methods from those sources to the situation at hand. Let w denote the Lee weight. We define the error locator polynomial

σ = n-1 i=0 (1 -X i z) w(ei) ∈ R[z] , (1)
where

X i = 0 if e i = 0, X i = α i if e i ∈ {1, 2}
, and

X i = -α i = α i+n if e i = 3.
For each positive integer k, we let s k denote the sum of the kth powers of the reciprocals of the roots of σ, including repeated roots, i.e.

s k = n-1 j=0 w(e j )X k j , k ≥ 1 .
We note that w(e j )X k j = e j α jk holds for all odd k. Hence, for each k ∈ {1, 3, . . . , 2t -1}, the kth syndrome s k = e(α k ) = v(α k ) is known to the decoder. Let s denote the power series

∞ k=1 s k z k ∈ R(z). We have σ ′ (z) = - n-1 j=0 w(e j )X j i =j (1 -X i z) w(ei) (1 -X j z) w(ej )-1 ,
and thus

zσ ′ (z) = -z n-1 j=0 n-1 i=0 (1 -X i z) w(ei) w(e j )X j 1 -X j z = -σ(z) n-1 j=0 w(e j ) ∞ k=1 (X j z) k = -σ(z) ∞ k=1 n-1 j=0 w(e j )X k j z k = -σ(z) ∞ k=1 s k z k = -σ(z)s(z) . Therefore sσ + zσ ′ = 0 , (2)
where the coefficients s 1 , s 3 , . . . , s 2t-1 are known to the decoder. For any power series

P (z) = ∞ k=0 P k z k ∈ R(z)
we denote the even part and the odd part by P e = j≥0 P 2j z 2j and P o = j≥0 P 2j+1 z 2j+1 , respectively. Then the even part and the odd part of equation ( 2) read

s e σ e + s o σ o + z(σ e ) ′ = 0 , (3)
s e σ o + s o σ e + z(σ o ) ′ = 0 . (4)
Subtracting σ e times equation ( 4) from σ o times equation ( 3) results in the equation

s o (σ 2 o -σ 2 e ) + z (σ e ) ′ σ o -(σ o ) ′ σ e = 0 , (5)
which involves only the odd part of s, the latter being known modulo z 2t+1 . Now let u = σo σe ∈ R(z) and rewrite equation ( 5) to obtain

s o (u 2 -1) = zu ′ , (6)
from which we can recursively compute the coefficients u 1 , u 3 , u 5 , . . . u 2t-1 via the equations

u 1 = -s 1 , u 3 = 1 3 (-s 3 + u 2 1 s 1 ), u 5 = 1 5 (-s 5 + u 2 1 s 3 + 2u 1 u 3 s 1 )
, etc. The reader should notice that this is the point where Berlekamp's original approach can continue only by imposing a severe restriction on t. In our situation however all the above denominators are invertible in R.

Clearly, u is an odd function and so we may define the power series T by

T (z 2 ) = (1 + zu(z)) -1 -1 . (7)
Moreover, the coefficients T 1 , . . . , T t are all known to the decoder. Next, we define the polynomials ϕ, ω ∈ R[z] by the equations ω(z 2 ) = σ e (z) , and ϕ(z

2 ) = σ e (z) + zσ o (z) . (8)
Noting that 1 + T (z 2 ) = σe σe+zσo we finally arrive at a key equation:

(1 + T ) ϕ ≡ ω mod z t+1 , (9)
which is the main task of the decoder to solve. Knowledge of ϕ and ω is sufficient to recover the error locations along with their multiplicities. Using equation [START_REF] Raghavendran | Finite associative rings[END_REF] we may obtain σ. The decoder could then run through the 2n roots of unity 1, α, . . . , α 2n-1 and determine the error polynomial e by evaluating σ(α -j ) and σ(α -j+n ) for all j ∈ {0, . . . , n-1}. Now we will show that the key equation carries sufficient information to determine any error pattern of Lee weight at most r. Let B(0, r) denote the ball in Z n 4 centered in 0 with radius r, and let α : B(0, r) → R[z] be the function e → σ, mapping an error pattern to its error locator polynomial (see equation ( 1)), which is injective. Then we consider the function

f : α(B(0, r)) → R t , σ → (T 1 , . . . , T t ) ,
where the coefficients T 1 , . . . , T t of the power series T are obtained as outlined above (see equations ( 6) and ( 7)).

Lemma 1. The map f : σ → (T 1 , . . . , T t ) is injective on α(B(0, r)).

Proof. Consider the syndrome map

Z 4 [z]/ z n +1 → R t , v → (s 1 , . . . , s 2t-1 ), with s k = v(α k ).
Its kernel equals the code C of Lee distance at least 2r +1, hence the map is injective on B(0, r). Now we observe that the mappings (s 1 , . . . , s 2t-1 ) → (u 1 , . . . , u 2t-1 ) → (T 1 , . . . , T t ) of equations ( 6) and ( 7) are bijective.

⊓ ⊔ Proposition 1. Let S := R[z]/ z t+1 . For any T = t i=1 T i z i ∈ S there is at most one error locator polynomial σ ∈ α(B(0, r)) such that the corresponding key equation (1 + T ) ϕ = ω in S is satisfied, where ω(z 2 ) = σ e (z) and ϕ(z 2 ) = σ e (z) + zσ o (z).

Proof. Suppose that σ ∈ α(B(0, r)) satisfies (1 + T ) ϕ = ω. Now S is a local ring with maximal ideal z , and as σ(0) = 1 we have ϕ(0) = ω(0) = 1, so that ϕ and ω are units in S. This implies 1 + T = ωϕ -1 , in particular, T is uniquely determined by the key equation. As also f (σ) satisfies the key equation by construction we have thus T = f (σ). Since f is injective, it must hold σ = f -1 (T ), and σ is hence uniquely determined.

⊓ ⊔

In the view of Proposition 1 it remains an open problem to find the unique solution of the key equation efficiently. In the following we assume that e has Lee weight at most t, and we present an efficient decoding method for this case.

For the classical finite field case, there is a unique pair of coprime polynomials [a, b] ∈ GF(p m )[z] 2 satisfying the key equation ( 9) along with the constraints:

a(0) = b(0) = 1 , δa ≤ t+1 2 , δb ≤ t 2 . ( 10
)
For the Galois ring case, it is apparent that the required solution pair [ϕ, ω] satisfies the constraints (10). Although ϕ and ω are not necessarily coprime in R[z], we will show in the next section that 2 ∈ R[z]ϕ + R[z]ω. Now over the ring R, a solution [a, b] of the key equation ( 9) satisfying 2 ∈ R[z]a + R[z]b and the constraints (10) will still not be unique in general, but the modulo 2 solution [µa, µb] ∈ K[z] is unique, which will be sufficient for the decoding problem.

The Ideal Generated by ϕ and ω

We will show that 2 can be expressed as a R[z]-linear combination of ϕ and ω. First we note some useful observations. The proofs will be largely omitted, due to space considerations.

Let S be a commutative ring with identity 1. For f, g ∈ S we use the notation (f, g) := Sf + Sg to denote the ideal generated by f and g in S.

Lemma 2. Let f, g, h ∈ S. Then (a) (f, g) = (f, hf +g), (b) (h, g) = S implies (f, g) = (hf, g). Lemma 3. Let a, b, u, v ∈ S and let f = a + b, g = u + v. Suppose that 2b = 0, (f, g) = S, and (g, u) = S .
Then (f g, au+bv) = (f, a).

We now specialize to the case that S = R[z] where R is a Galois ring with residual field K. Consider the polynomial

Σ(z) := r i=1 (1 -Y i z) ai ∈ R[z] ,
for some a i ∈ {1, 2} and Y i ∈ R such that the µY i ∈ K × are pairwise distinct. We further let τ = s i=1 (1 -Y i z) 2 and ε = r i=s+1 (1 -Y i z) be the square and non-square part of Σ (under a suitable re-ordering of the Y i if necessary). As before, we denote the even and the odd part of a polynomial f ∈ R[z] by f e and f o , respectively. Lemma 4. Given the above notation, there holds

2τ o = 0, (τ, ε) = R[z], and (ε, ε e ) = R[z]. Corollary 1. (Σ, Σ e ) = (τ, τ e ).
Proof. We observe that Σ e = τ e ε e + τ o ε o . Combining Lemma 3 and Lemma 4 we obtain (Σ, Σ e ) = (τ ε, τ e ε e +τ o ε o ) = (τ, τ e ).

⊓ ⊔

With these preparations one can prove:

Proposition 2. 2 ∈ (Σ e , Σ o ). Corollary 2. 2 ∈ (ϕ, ω).
Proof. It is clear that σ has the same form as Σ, defined before, and thus 2 ∈ (σ o , σ e ). Moreover

The Solution Module of the Key Equation

In this section we investigate the module of solutions to the key equation ( 9),

M = {[a, b] ∈ R[z] 2 | a(1 + T ) ≡ b mod z t+1 }.
First we recall some basic facts on Gröbner basis in R[z] 2 , further details can be found in [1,[START_REF] Byrne | Hamming Metric Decoding of Alternant Codes Over Galois Rings[END_REF][START_REF] Byrne | Gröbner Bases over Commutative Rings with Applications to Coding Theory[END_REF].

Definition 2. Let ℓ be an integer. We define a term order Given a set of non-zero elements of R[z] 2 there exists in the set a (not necessarily unique) minimal element with respect to the quasi-order associated with <. We will refer to this element as being minimal with respect to <.

< ℓ on R[z] 2 by (a) [z i , 0] < ℓ [z j , 0] and [0, z i ] < ℓ [0, z j ] for i < j, (b) [0, z j ] < ℓ [z i , 0] if and only if j ≤ i + ℓ.
We say that lt Lemma 5. Let A be a submodule of R[z] 2 . Suppose that A has elements with leading terms on the left and elements with leading terms on the right. Then A has a (not necessarily minimal) Gröbner basis of the form

[a, b], [c, d], [g, h], [u, v] with lm[a, b] = [z i , 0], lm[c, d] = [2z j , 0], lm[g, h] = [0, z r ], lm[u, v] = [0, 2z s ]
satisfying i ≥ j and r ≥ s. Moreover, the integers i, j, r, s are uniquely determined.

In [4, Sec. VI] an efficient algorithm to compute a Gröbner basis for a submodule M of the form

M = {[a, b] ∈ R[z] 2 | a U ≡ b mod z r }, for some U ∈ R[z]
is given, the so-called method of Solution by Approximations. This algorithm generalizes one for the finite field case, derived in [START_REF] Fitzpatrick | On the Key Equation[END_REF], which can be viewed as the Gröbner basis equivalent of the Berlekamp-Massey algorithm [3,Alg. 7.4]. The Solution by Approximations method works by computing iteratively a Gröbner basis of each successive solution module

M (k) = {[a, b] ∈ R[z] 2 | a U ≡ b mod z k },
finally arriving at a basis of M = M (r) . The algorithm requires no searching at any stage of its implementation and has complexity quadratic in r.

In the next result we establish the minimality of [ϕ, ω] among the regular elements of the solution module of the key equation ( 9) with respect to the term order < -1 . The proof is omitted due to space constraints. satisfying the hypothesis of Theorem 2. One way to do this is to identify the minimal regular element of a Gröbner basis of the solution module M , relative to the term order < -1 . 5. Compute µσ(z) = µσ e (z) + µσ o (z) := µh(z 2 ) + z -1 (µg(z 2 ) -µh(z 2 )). 6. Evaluate µσ(µα -j ) for j = 0, . . . , n-1.

Theorem 2. Let M = {[a, b] ∈ R[z] 2 | a(1+T ) ≡ b mod z t+1 }. Let [a, b] ∈ M such that δa ≤ t+1 2 , δb ≤ t 2 , and 2 ∈ (a, b). Suppose further that lc(a) ∈ R × if δa > δb and lc(b) ∈ R × if δa ≤ δb. (a) Then [a, b] is minimal in M \ M ∩ 2R[z] 2 with respect to the term order < -1 . Moreover, if [a ′ , b ′ ] is minimal in M \ M ∩ 2R[z] 2 then [µa, µb] = ν[µa ′ , µb ′ ] for some ν ∈ K × . (b) If in addition (a, b) = R[z] holds, then [a, b] is minimal in M \ {0} with respect to the term order < -1 , and if [a ′ , b ′ ] is minimal in M \ M ∩ 2R[z] 2 then [a, b] = θ[a ′ , b ′ ] for some θ ∈ R × . Corollary 3. Let M = {[a, b] ∈ R[z] 2 | a (
-If µα -j is a double root of µσ then e j = 2.

-If µα -j is a single root of µσ then e j ∈ {±1}. 7. Let e 2 := j,ej =2 2z j , and let v ′ := v -e 2 . 8. Repeat Steps 1.-4. with v ′ in place of v, and compute σ ′ (z) = σ ′ e (z)+σ ′ o (z) := h(z 2 ) + z -1 (g(z 2 ) -h(z 2 )). 9. Compute e ′ by evaluating σ(α -j ) and σ(α -j+n ) for j = 0, . . . , n-1.

-If α -j is a root of σ then e ′ j = 1. -If α -j+n is a root of σ then e ′ j = 3. 10. Output c := v ′ -e ′ .

We will conclude our work by a concrete example. We use a code of length n = 15 with t = 2. Let the received word be v = 2 + z + 3z 2 + 2z 4 + z 5 + 2z 6 + 3z 7 + z 8 + 3z 9 + z 10 + 3z 13 .

1. The list of syndromes is [3α 3 + α 2 + 3α + 2, 2α 3 + α 2 + 2α + 1]. 3. The T polynomial of the key equation is T (z) = (2α 3 + α 2 + α)z 2 + (3α 3 + α 2 + 3α + 2)z + 1. 4. The solution of the key equation is [(α 3 + 2α 2 + 3α + 3)z + 3α 3 + 3α 2 + 2α + 3, z + 3α 3 + 3α 2 + 2α + 3)] ∈ R[z] 2 . 7. We find e 2 = 0. 9. Repeating the process with v ′ = v we find e ′ = z 4 -z 13 and c = v ′ -e ′ .

(ϕ(z 2 )Remark 2 .

 22 , ω(z 2 )) = (σ e (z) + zσ o (z), σ e (z)) = (zσ o (z), σ e (z)) = (σ o , σ e ) , since (z, σ e ) = R[z]. As 2 ∈ (σ o , σ e ) there exist a, b ∈ R[z] such that a ϕ(z 2 ) + b ω(z 2 ) = 2. It follows a e ϕ(z 2 ) + b e ω(z 2 ) = 2. Thus we have uϕ + vω = 2 with u, v ∈ R[z] such that u(z 2 ) = a e and v(z 2 ) = b e .⊓ ⊔ Suppose that no 'double-errors' occurred, i.e., there is no position j with e j = 2. Then we have τ = 1, and by Corollary 1, we have (σ, σ e ) = (τ, τ e ) = R[z]. From this it follows (ϕ, ω) = R[z], as before.

Let

  < denote an arbitrary fixed term order and let [a, b] ∈ R[z] 2 \ {0}. We denote the leading term of [a, b] by lt[a, b], its leading coefficient by lc[a, b], and its leading monomial by lm[a, b] = lc[a, b]lt[a, b]. For any [a, b], [c, d] ∈ R[z] 2 we say that [a, b] [c, d] if and only if lt[a, b] ≤ lt[c, d].

  [a, b] is on the left (resp. right) if lt[a, b] = [z i , 0] (resp. lt[a, b] = [0, z i ]) for some non-negative integer i. A subset B of a submodule A of R[z]2 is called Gröbner basis, if for all α ∈ A there exists β ∈ B such that lm(β) divides lm(α). The structure of a Gröbner basis in R[z] 2 is given by the following lemma (cf. [4, Th. V.3]).

4 .

 4 1+T ) ≡ b mod z t+1 }, and let [a ′ , b ′ ] be the minimal regular element of a Gröbner basis of M . Obtain a solution [g, h] ∈ R[z] 2 of the key equation a(1 + T ) = b mod z t+1

Example 1 .

 1 Let R = GR(4, 4) = Z 4 [x]/ x 4 +2x 2 +3x+1 and let α = [x] ∈ R.

Table 1 .

 1 Parameters

	n t	k 2t+1 dLee
	15 1 11	3	3
	2	7	5	5
	3	5	7	10
	31 1 26	3	4
	2 21	5	7
	3 16	7	12
	5 11 11	16
	7	6	15	26

of negacyclic codes of length n, designed error-correcting capability t, and rank k (i.e., size 4 k ).

⋆ The work of E. Byrne, M. Greferath, and J. Zumbrägel was partially supported by the Science Foundation Ireland under Grants 06/MI/006, 08/RFP/MTH1181, and 08/IN.1/I1950. ⋆⋆ The work of J. Pernas was partially supported by the Spanish MICINN under Grants PCI2006-A7-0616 and TIN2010-17358, and by the Catalan AGAUR under Grant 2009SGR1224.

Decoding Z 4 -linear Negacyclic Codes

Let the Z 4 -linear negacyclic code C be given as in the previous sections, and let v, c, e ∈ Z 4 [z], σ, σ o , σ e , ϕ, ω ∈ R[z] and T ∈ R(z) be given as before. In particular, v = c + e with c ∈ C and the error vector e is of Lee weight at most t.

be the module of solutions to the key equation [START_REF] Wolfmann | Negacyclic and Cyclic Codes over Z n 4[END_REF]. We first compute a Gröbner basis of M relative to the term order < -1 , which contains an element [a, b] such that µa = µϕ and µb = µω. Then µϕ, µω can be used to determine µσ = Knowledge of µσ is not sufficient to recover the error pattern e, as errors of the form e j = ±1 cannot be distinguished. However, by examining the roots of µσ we find all error positions, and by examining the double roots we get all locations j where e j = 2 (i.e., the 'double-errors').

Let e 2 ∈ Z n 4 be defined by e 2 j = 2 if e j = 2 and e 2 j = 0 otherwise. Note that e 2 is completely determined by the roots of µσ. Now consider the word v ′ := v -e 2 = c + e ′ with e ′ := e -e 2 . Then e ′ does not contain double-errors and has Lee weight at most t. Then, using Corollary 3, the error pattern e ′ can be found by computing the minimal regular element of a Gröbner basis.

We outline the steps of the algorithm below.

Algorithm 1 (Algebraic Decoding of Z 4 Negacyclic Codes). Let C be a negacyclic code over Z 4 of length n, whose generator polynomial has roots α, α 3 , . . . , α 2t-1 for a primitive 2nth root of unity α ∈ R such that α n = -1.


Michael Kiermaier
email: michael.kiermaier@uni-bayreuth.de

Johannes Zwanzger
email: johannes.zwanzger@uni-bayreuth.de

New Ring-Linear Codes from Geometric Dualization

Introduction

History

In the 1960s and 1970s the Nordstrom-Robinson-Code [START_REF] Nordstrom | An optimum nonlinear code[END_REF] and subsequently the infinite series of the Preparata- [START_REF] Franco | A class of optimum nonlinear double-error-correcting codes[END_REF], , Delsarte-Goethals- [START_REF] Delsarte | Alternating bilinear forms over GFq[END_REF] and Goethals-Codes [START_REF] Goethals | Nonlinear codes defined by quadratic forms over GF(2), Inform[END_REF] were discovered. Apart from a few corner cases, all of these codes are non-linear binary block codes that have higher minimum distance than any known comparable (having equal size and length) linear binary code. We will call such codes better-than-known-linear or BTKL. In [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]Research Problem (15.4)] the question was raised if the Preparata and Kerdock codes are better than any comparable linear binary code (better-than-linear, BTL1 ). For the Preparata series this was shown in [START_REF] Brouwer | A sharpening of the Johnson bound for binary linear codes and the nonexistence of linear codes with Preparata parameters[END_REF]. Of the remaining above mentioned series still only the smaller codes are proven to be BTL.

Later the striking discovery was made [START_REF] Nechaev | Kerdock code in a cyclic form[END_REF][START_REF] Jr | The Z4-Linearity of Kerdock, Preparata, Goethals, and Related Codes[END_REF] that all these codes can be constructed as images of certain Z 4 -linear codes under the Gray map. Since then, a lot of research has been done on Z 4 -linear codes and on linear codes over more general finite rings. However, the examples on BTL-or BTKL-codes found since then are comparatively sparse. They include Gray images of QR-codes over Z 4 , the two Calderbank-McGuire-codes [START_REF] Calderbank | Construction of a (64, 2 37 , 12) code via Galois rings[END_REF][START_REF] Calderbank | Cyclic codes over Z4, locator polynomials, and Newton's identities[END_REF] and some quasi-cyclic codes over Z 4 [START_REF] Aydin | Quasi-cyclic codes over Z4 and some new binary codes[END_REF] 2 . Two further examples [START_REF] Hemme | Arcs in projective Hjelmslev spaces obtained from Teichmüller sets[END_REF][START_REF] Kiermaier | New Arcs in Projective Hjelmslev Planes Over Galois Rings[END_REF] come from a hyperoval in the projective Hjelmslev plane over the 16-element Galois ring GR [START_REF] Honold | On arcs in projective Hjelmslev planes[END_REF][START_REF] Calderbank | Cyclic codes over Z4, locator polynomials, and Newton's identities[END_REF] where a similar Gray map allows the comparison with F 4 -linear codes.

Overview

Our aim is the construction of new ring-linear BTL-and BTKL-codes. The class of base rings are the Galois rings GR(4 r , 4) of characteristic 4, which include Z 4 as its smallest and most important member. All these rings come with a generalized Gray map which allows the comparison with F q -linear codes. Associated with these rings are the Hjelmslev geometries, and the central tool for the construction is geometric dualization [START_REF]The dual construction for arcs in projective Hjelmslev spaces[END_REF]. Roughly speaking, it gives us the possibility to compute the parameters of a code which was constructed out of another code by selecting the information words of codewords of certain symmetrized weights and putting them as columns into a generator matrix.

Our first construction dualizes the Z 4 -linear preimages of the Kerdock codes. It turns out that the resulting codes can be extended while preserving their minimum distance. The final series K * r+1 of Z 4 -linear codes has high minimum Lee distance, the first two members are BTL-codes. For the second construction we start with a series related to the Kerdock codes we call Teichmüller codes, the result is a 2-parameter-series T * r,k . Both series K * r+1 and T * r,k consist of homogeneous 3-weight codes and have the property that the largest part of the codewords are minimum weight words. We also compute the symmetrized weight enumerator of the codes which enables us to derive the parameters of residuals.

The generalized Gray map translates our codes into ordinary, generally nonlinear codes in the Hamming space. For moderate lengths, the online tables [START_REF] Grassl | Code Tables: Bounds on the parameters of various types of codes[END_REF] can be used for the comparison with classical linear codes. In this way, we get the BTL-and BTKL-codes summarized in the table below. They are either new or give an alternative construction to already known code parameters. A preliminary report on this research containing the series K * (r + 1) was published in [START_REF]A new series of Z4-linear codes of high minimum Lee distance derived from the Kerdock codes[END_REF] 2 Galois rings

Here a brief introduction to Galois rings is given. For details, see for example [START_REF] Bernard | Finite Rings with Identity[END_REF].

Let p be prime and m be a positive integer. Let f ∈ Z p m [X] be a monic polynomial of degree r ≥ 1, such that its image modulo p is irreducible in

F p [X].
The ring Z p m [X]/(f ) is called the Galois ring GR(p mr , p m ) of order p mr and characteristic p m . It can be shown that up to ring isomorphism, the definition does not depend on the exact choice of f . In the case m = 1, R is the finite field F p m . R = GR(p mr , p m ) is a local ring with the unique maximal ideal Rp, which is principal. The residue class field R/pR is isomorphic to F q with q = p r . The unit group R * of order q(q -1) has a unique subgroup of order q -1, its set of Teichmüller units which will be denoted by T * . If the defining polynomial f of R is chosen as the Hensel lift of a primitive polynomial in Z p [X] of degree r, X + (f ) is a generator of T * . Furthermore, T = T * ∪ {0} is called set of Teichmüller elements in R. T forms a set of representatives of the residue class field.

GR(p mr , p m ) is a subring of GR(p ms , p m ) if and only if r divides s. In this way, for any positive integer k, GR(q mk , p m ) is a free R-module of rank k, and we can identify the elements of GR(q mk , p m ) with vectors in R k . This identification gives rise to the isomorphism R k ∼ = GR(q mk , p m ) as R-modules, providing an additional multiplicative structure on the vectors in R r .

We define the period π(x) of a Galois ring element x ∈ R as the smallest non-negative integer s such that xp s = 0. It holds that π(x) = 0 if and only if x = 0 and π(x) = m if and only if x is a unit in R.

Linear codes over Galois rings

Here the basic notions of the theory of linear codes over Galois rings are given. For a deeper discussion the reader is referred to [START_REF] Honold | Linear codes over finite chain rings[END_REF][START_REF]Linear Codes over Finite Chain Rings and Projective Hjelmslev Geometries, Codes over Rings[END_REF]. A good source for the theory of Z 4 -linear codes is [START_REF] Huffman | Fundamentals of error-correcting codes[END_REF]Chapter 12].

Let p be a prime, r be a positive integer, q = p r , R = GR(q m , p m ) and n be a positive integer. A subset

C of R n is called a block code over R of length n. If C is a submodule of the R-module R n , C is an R-linear code.
Let C be a block code over R and c ∈ R n be a codeword. for i ∈ {0, . . . , m} we define a i (c) as the number of components of c of period i, and the symmetrized weight w sym (c) = (a 0 (c), . . . , a m (c)). The symmetrized weight enumerator of C is

w sym (C) = c∈C X wsym(c) = c∈C m i=0 X ai(c) i ∈ Z[X 0 , . . . , X m ].
Symmetrized weight enumerators will often be given as a table, where each line corresponds to a single monomial, listing the coefficient and the exponents of the respective polynomial indeterminates. The exponent of X 0 may be skipped, since it can be recovered from the length and the other exponents.

The Hamming weight of a codeword c ∈ C is the number of non-zero components w The idea behind the homogeneous weight is that all non-zero ideals of R get the same average weight, which is γ = q -1. It admits the generalized Gray map, a distance preserving map (R, d hom ) → (F q m-1 q , q 2-m d Ham ), which allows the construction of -generally non-linear -codes over a q-ary alphabet from R-linear codes. For m = 1, w hom is just qw Ham . For m = 2, the Reed-Solomon map γ * in [START_REF] Nechaev | Linearly presentable codes[END_REF] is a suitable generalized Gray map. The homogeneous weight was introduced in [START_REF] Constantinescu | A metric for codes over residue class rings[END_REF] as a generalization of the Lee weight to integer residue rings Z k . For the case k = p 2 , p prime, also a generalized Gray map was given. A more general notion of the homogeneous weight and the Gray map can be found in [START_REF] Honold | Weighted modules and representations of codes[END_REF][START_REF] Greferath | Gray isometries for finite chain rings and a nonlinear ternary[END_REF][START_REF]Finite-ring combinatorics and MacWilliams' equivalence theorem[END_REF].

Ham (c) = m i=1 a i (c) = n-a 0 (c). The homogeneous weight of a codeword c ∈ C is w hom (c) = qa 1 (c)+ m i=2 (q -1)a i (c). The homogeneous weight enumera- tor of C is w hom (C) = c∈C X w hom (c) = w sym (C)(1, q, q -1 . . . , q -1). For R = Z
The minimum homogeneous distance d hom (C) is the smallest homogeneous distance between two different codewords of C. We say that C is a (n, #C, d hom (C))code or a (n, #C, d hom (C)) #R -code. For R-linear codes C we have that d hom (C) equals the smallest non-zero homogeneous weight among the codewords.

Like in classical coding theory over finite fields, one of the main goals is to find a R-linear code for given length and size whose minimum homogeneous distance is as large as possible. As a special case of linear codes over finite chain rings, a table of R-linear codes of high minimum homogeneous distance can be found in [START_REF] Kiermaier | Online tables of linear codes over finite chain rings[END_REF].

R-linear codes and projective Hjelmslev geometry

For the theory of projective Hjelmslev geometries see [START_REF] Honold | On arcs in projective Hjelmslev planes[END_REF]. The connection to R-linear codes is described in [START_REF] Honold | Linear codes over finite chain rings[END_REF][START_REF]Linear Codes over Finite Chain Rings and Projective Hjelmslev Geometries, Codes over Rings[END_REF].

The rough idea is the following: Given a (k × n) generator matrix of an R-linear code such that each column contains a unit, the columns can be interpreted as an n-element multiset of points in the projective Hjelmslev geometry PHG(R, k -1). Vice versa, given a multiset of points in PHG(R, k) one can associate an R-linear code by putting coordinate vectors of the points as columns into a generator matrix. Up to isomorphism, these operations are inverse to each other.

Now assume that we have m = 2. The symmetrized weight enumerator of an R-linear code translates into the spectrum of a multiset of points, which counts for each hyperplane H the number of points on H, the number of points neighbor to H but not on H, and the number of points not neighbor to H. For a single hyperplane H, these numbers are called the type of H. Given a multiset of points in PHG(R, k), a new multiset of points can be defined by selecting the hyperplanes of certain types with a multiplicity depending on the type and interpreting these hyperplanes as a multiset of points in the dual geometry (which interchanges the role of points and hyperplanes). If the selection of the hyperplanes can be done in a linear way in the sense of [START_REF]The dual construction for arcs in projective Hjelmslev spaces[END_REF], then the spectrum of the dualized point set can be computed out of the original spectrum and the distribution of the points to the point classes.

The Kerdock codes

For r ≥ 3 odd the code K r+1 is defined as the Z 4 -linear code generated by the rows of the ((r + 1) × 2 r )-matrix

t 0 • • • t 2 r -1 1 • • • 1 ,
where t 0 , . . . , t 2 r -1 ∈ Z r 4 runs over the Teichmüller elements of GR(2 2r , 4) which are read as elements in Z r 4 . Up to a permutation of the coordinates, the Gray image of K r+1 is the Kerdock code as originally defined in [START_REF] Kerdock | A class of low-rate nonlinear binary codes[END_REF]. For simplicity, we will use the term Kerdock-code for K r+1 , too.

Fact 2 Let r ≥ 3 be odd. The code K r+1 is a Z 4 -linear code with the parameters

2 r , 2 2r+2 , 2 r -2 r-1 2
.

The symmetrized weight enumerator of K r+1 is:

#codewords a 0 a 1 a 2 w Lee A 2 2r+1 -2 r+1 2 r-2 + 2 r-3 2 2 r-2 -2 r-3 2 2 r-1 2 r -2 r-1 2 B 2 2r+1 -2 r+1 2 r-2 -2 r-3 2 2 r-2 + 2 r-3 2 2 r-1 2 r + 2 r-1 2 C 2 r+1 0 0 2 r 2 r D 2 r+1 -2 2 r-1 2 r-1 0 2 r E 1 0 2 r 0 2 r+1 F 1 2 r 0 0 0
Proof. In [20, Theorem 17.2.6], the Lee weight enumerator of K r+1 is given. The proof actually shows that the symmetrized weight enumerator is of the claimed form.

The Teichmüller Codes

Let r be a positive integer, q = 2 r and R = GR(4 r , 4) = GR(q 2 , 4). Let further k ≥ 3 be an odd integer and S = GR(4 rk , 4) = GR(q 2k , 4). In the following we consider R as a subring of S. The Teichmüller units of S are a cyclic group T of order q k -1. Its cyclic subgroup U of order q -1 is the group of Teichmüller units of R. Now we define the Teichmüller code T q,k as the R-linear code generated by a generator matrix, whose columns are set of representatives of the factor group T /U read as elements of R k .

Fact 3 Let k ≥ 3 be odd, r be a positive integer and q = 2 r . The code T q,k is a GR(q 2 , 4)-linear code with the parameters

q k -1 q -1 , q 2k , q k -q k-1 2
.

The symmetrized weight enumerator of T q,k is:

#codewords a 0 a 1 a 2 w Lee A 1 2 q k+1 2 q k-1 2 -1 q k -1 q k-2 -1 q-1 -q k-3 2 q k-2 + q k-3 2 q k-1 q k + q k-1 2 B 1 2 q k+1 2 q k-1 2 + 1 q k -1 q k-2 -1 q-1 + q k-3 2 q k-2 -q k-3 2 q k-1 q k -q k-1 2 C q k -1 q k-1 -1 q-1 q k-1 0 q k D 1 q k -1 q-1 0 0 0
Proof. In [14, Example II.3], it was shown that the corresponding Teichmüller point set T q,k in the projective Hjelmslev geometry PHG(R, k -1) is a 2intersection set with respect to point-hyperplane intersections, and the intersection numbers are (q k-2 -1)/(q -1) -q (k-3)/2 and (q k-2 -1)/(q -1) + q (k-3)/2 . Each point class of PHG(R, k) contains exactly 1 point of T q,k . A double counting argument gives the spectrum of T q,k , and from this the symmetric weight enumerator of T q,k can be derived.

In the planar case k = 3, the Teichmüller point sets are exactly the hyperovals discussed in [START_REF] Hemme | Arcs in projective Hjelmslev spaces obtained from Teichmüller sets[END_REF][START_REF] Honold | On arcs in projective Hjelmslev planes[END_REF]. In the case q = 2 we have #U = 1, and the Teichmüller codes are just the Kerdock codes shortened in a single coordinate and therefore very good codes. But also the generalized Gray image of T 3,4 is a BTKL-code. Its parameters (84, 4 6 , 60) 4 were first given in [START_REF] Hemme | Arcs in projective Hjelmslev spaces obtained from Teichmüller sets[END_REF].

4 Dualization of the Kerdock codes Lemma 4 Let r ≥ 3 be odd. The code K * r+1 is a Z 4 -linear code with parameters

2 2r -2 r , 4 r+1 , 2 2r -2 r -2 r-1 2
.

The symmetrized weight enumerator of K * r+1 shown below. The codewords of lines B, D, E and F form a submodule of K * r+1 of index 2.

#codewords

a 1 a 2 w Lee A 2 2r+1 -2 r+1 2 2r-2 -2 r-2 -2 r-3 2 2 2r-1 -2 r-1 2 2r -2 r -2 r-1 2 B 2 2r+1 -2 r+1 2 2r-2 -2 r-1 2 2r-1 2 2r -2 r C 2 r+1 2 2r-2 + 2 3r-3 2 -2 r-2 -2 r-3 2 2 2r-1 -2 r-1 2 2r -2 r + 2 3r-1 2 -2 r-1 2 D 2 r -1 2 2r-1 0 2 2r E 2 r 2 2r-1 -2 r-1 0 2 2r -2 r F 1 0 0 0

Examples and Derived Codes

By Theorem 5 the Gray image of K * 4 is a nonlinear binary code with the parameters (114, 2 8 , 56), which is BTL. The Gray image of the residual in a codeword of line E has the BTL-parameters (58, 2 7 , 28), Recently the authors constructed a Z 4 -linear code with these parameters using a hyperoval in the projective Hjelmslev plane over Z 4 [START_REF]A non-free Z4-linear code of high minimum Lee distance[END_REF].

The Gray image of K * 6 is a nonlinear (1988, 2 12 , 992)-code. It was possible to show computationally that this code is BTL, details will be published elsewhere.

The Gray image of the residual of K * 6 in a codeword of type B has the parameters (484, 2 Taking again the residual in a codeword of symmetrized weight (122, 120, 0) yields a Z 4 -linear code whose Gray image has the BTKL-parameters (244, 2 9 , 120).

Dualization of the Teichmüller codes

In the following let r be a positive integer, q = 2 r , R = GR(4 r , 4) = GR(q 2 , 4), k ≥ 3 and G be a generator matrix of T q,k . Furthermore, we take S as a set of projective representatives of information words x ∈ R k such that xG is a codeword of T q,k of symmetrized weight A. The vectors in S are put as columns into a matrix A, and the code generated by A is denoted by T * q,k .

Theorem 6 The code T * q,k is a R-linear code with parameters

1 2 q k-1 2 q k-1 2
-1 q k -1 q -1 , q 2k , 1 2 q 2k-1 -q 3k-1 2

-q k-1 .

The symmetrized weight enumerator of T * q,k is:

#codewords a 1 a 2 w hom A q k+1 -q 1 2 q 2k-3 -q k-2 1 2 q 2k-2 -q 3k-3 2 1 2 q 2k-1 -q 3k-1 2

+ q 3k-3 2

-q k-1 B q 2k -q k+1 -q k + q 1 2 q 2k-3 -q k-2 -q 3k-5 2 1 2 q 2k-2 -q 3k-3 2 1 2 q 2k-1 -q 3k-1 2

-q k-1 C q k -1 1 2 q 2k-2 -q 3k-3 2 0 1 2 q 2k-1 -q 3k-1 2 D 1 q k -1 q-1 0 0

  4 the homogeneous weight is better known as the Lee weight w Lee . Each of these weights has an associated distance function (d sym , d Ham , d hom or d Lee ), mapping a pair of codewords (c 1 , c 2 ) to the respective weight of c 1 -c 2 .

Fact 1 (

 1 [START_REF] Greferath | Lecture at Cimpa-Unesco-Tübitak Summer School Codes over Rings[END_REF]) Let C be an R-linear (n, #C, d)-code and c ∈ C with γw Ham (c) < d. Puncturing C in the support of c yields the residual of C in c, which is an R-linear code with parameters (n -w Ham (c), #C/#(Rc), ≥ d -γw Ham (c)).

4. 1

 1 The code K * r+1In the following let r ≥ 3 be odd and G ∈ Z (r+1)×2 r 4 be a generator matrix of K r+1 . Furthermore, we take S as a set of projective representatives of information words x ∈ Z r+1 4 such that xG is a codeword of symmetrized weight B in the symmetrized weight enumerator of K r+1 . The vectors in S are put as columns into a matrix A, and the code generated by A is denoted by K * r+1 . The size of S and therefore the length of the code K * r+1 is 2 2r -2 r .

  .

	No. gen. Gray image	construction	status already known?
	1 2 3 4 5 (244, 2 9 , 120) 2 res. of code No. 7 in (122, 120, 0) BTKL (58, 2 7 , 28) 2 residual of K * BTL 3 in E (60, 2 8 , 28) 2 residual of T * BTL 2,5 in A (114, 2 8 , 56) 2 K * BTL 3 (180, 2 9 , 88) 2 residual of T * BTKL 2,5 in C	[25] [1, Ex. 4] new new new
	6 (372, 2 10 , 184) 2 7 (484, 2 10 , 240) 2 8 (1988, 2 12 , 992) 2 9 (504, 4 6 , 376) 4	T * 2,5 residual of K * 5 in B K * 5 T * 4,3	BTL BTKL BTL BTKL	new new new [22]

  10 , 240). This code is BTKL, since an F 2 -linear [484, 10, 240]code would have a F 2 -linear residual with the parameters [244, 9, 120] which is not known.On the other hand, we can construct a Z 4 -linear code out of K * 6 whose Gray image has these parameters: We checked computationally that every residual in a codeword of type B has the symmetrized weight enumerator

	2X 30 0 X 92 1 X 120 2	+ 60X 46 0 X 76 1 X 120 2	+ 480X 58 0 X 56 1 X 128 2
		+ 450X 62 0 X 60 1 X 120 2	+ 15X 114 0 X 128 1	+ 16X 122 0 X 120 1	+ X 242 0 .

While BTL is a hard property of a binary block code, BTKL only describes the current state of knowledge.

We would like to mention that Ex. 5 and 6 in[START_REF] Aydin | Quasi-cyclic codes over Z4 and some new binary codes[END_REF] are not BTKL due to recently found linear binary codes.

⋆ Supported by Deutsche Forschungsgemeinschaft under Grant No. WA 1666 4/1

Proof. The construction corresponds to the duality construction in [START_REF]The dual construction for arcs in projective Hjelmslev spaces[END_REF]. Following this article, we define the function τ by setting

2 r and γ = 1 -2 r-1 2

2 r .

Dualizing the associated point set K in PHG(Z 4 , r) with this function τ yields a new point set K * , which generates K * r+1 . The formula in [START_REF]The dual construction for arcs in projective Hjelmslev spaces[END_REF] yields the spectrum of K * and subsequently the symmetrized weight enumerator of K * . The submodule statement follows from the fact that the point classes not containing any point of K r+1 form the neighbor class of a hyperplane in PHG(r, Z 4 ). coordinates in the following way: The codewords corresponding to the lines B, D, E and F in the symmetrized weight enumerator of K * r+1 are extended by zeros and the codewords corresponding to the lines A and C are extended by symbols 2. In this way, the minimum Lee weight

is raised to match the second smallest Lee weight 2 2r -2 r (lines B and E).

Theorem 5 Let r ≥ 3 be odd. The code K * r+1 is a Z 4 -linear code with parameters

The Lee weight enumerator of K * r+1 is

The symmetrized weight enumerator of K * r+1 is:

Proof. By Lemma 4, the codewords of the lines B, D, E and F in the symmetrized weight enumerator of K * r+1 form a submodule of K * r+1 of index 2. So the code K * r+1 is indeed Z 4 -linear. The statements about length and size of K * r+1 are clear, and the symmetrized weight enumerator of K * r+1 can be easily computed from the symmetrized weight enumerator of K * r+1 .

Proof. The construction corresponds to the duality construction in [START_REF]The dual construction for arcs in projective Hjelmslev spaces[END_REF]. Following this article, we define the function τ by setting

, γ = 0.

Dualizing the associated point set T in PHG(Z 4 , r) with this function τ yields a new point set T * , which generates T * q,r . The formula in [START_REF]The dual construction for arcs in projective Hjelmslev spaces[END_REF] yields the spectrum of T * and subsequently the symmetrized weight enumerator of T * .

The code T * 2,3 equals T 2,3 . To see that the Gray image of T * 2,5 with the parameters (372, 2 10 , 184) 2 is BTL, we look at the residual of a hypothetical F 2 -linear [372, 10, 184]-code. This would be an F 2 -linear [188, 9, 92]-code, and according to [START_REF] Grassl | Code Tables: Bounds on the parameters of various types of codes[END_REF], such a code does not exist. Similarly, the residual of a hypothetical F 4linear [504, 6, 376] code would be an F 4 -linear [128, 5, 94]-code, whose existence is not known. So the status of the Gray image of T * 4,3 which has the parameters (504, 4 6 , 376) 4 is BTKL. The code T * 4,3 was first given in [START_REF] Kiermaier | New Arcs in Projective Hjelmslev Planes Over Galois Rings[END_REF]. The Gray image of the residual of T * 2,5 in a codeword of symmetrized weight of type A is a non-linear (60, 2 8 , 28)-code, which is BTL. In [START_REF] Aydin | Quasi-cyclic codes over Z4 and some new binary codes[END_REF]Ex. 4] a quasicyclic Z 4 -linear construction for a code with these parameters was given. The Gray image of the residual of T * 2,5 in a codeword of symmetrized weight of type C is a non-linear (180, 2 9 , 88)-code, which is a new example of a BTL-code.


Alexander Pott
email: alexander.pott@ovgu.de

Yue Zhou
email: yue.zhou@st.ovgu.de

CCZ and EA Equivalence between Mappings over Finite Abelian Groups

Keywords: Abelian groups, Extended affine equivalence, Carlet-Charpin-Zinoviev equivalence

published or not. The documents may come

Introduction

In [START_REF] Carlet | Codes, bent functions and permutations suitable for des-like cryptosystems[END_REF], Carlet, Charpin and Zinoviev introduced an equivalence relation, as a generalization of the extended affine equivalence, on the set of vectorial Boolean functions used as S-boxes in cryptosystems. Later, in [START_REF] Budaghyan | New classes of almost bent and almost perfect nonlinear polynomials[END_REF] this equivalence is named after these three authors, and abbreviated to CCZ-equivalence. In [START_REF] Budaghyan | New classes of almost bent and almost perfect nonlinear polynomials[END_REF], Budaghyan, Carlet and Pott proved that CCZ-equivalence is strictly more general than EAequivalence , by exhibiting APN functions which are CCZ-equivalent to the APN function F (x) = x 3 on F 2 n , but which are provably EA-inequivalent to it and (for n odd) to its inverse (for APN functions, see the recent survey [START_REF] Carlet | Boolean Functions, volume 2, chapter Vectorial Boolean functions for cryptography[END_REF]). In [START_REF] Budaghyan | CCZ-equivalence of single and multi-output Boolean functions[END_REF] and [START_REF] Budaghyan | On isotopisms of commutative presemifields and ccz-equivalence of functions[END_REF], Budaghyan, Carlet and Helleseth further proved:

Result 1 Let p be a prime and n be a positive integer. Two functions from F p n to F 2 are CCZ-equivalent if and only if they are EA-equivalent;

Result 2 Let p be a prime, and C = 6, p = 2; 3, otherwise.

Let n ≥ C and k > 1 be the smallest divisor of n. Then for any m ≥ k, the CCZ-equivalence of functions from F p n to F p m , is strictly more general than their EA-equivalence.

In this paper, we generalize CCZ-and EA-equivalence to the mappings between finite abelian groups G and H, and consider whether CCZ-equivalence coincide with EA-equivalence for given G and H. Our results cover Result 1, and improve Result 2: we do not need the smallest divisor condition. This paper shows that the problems about the connection between CCZ and EA equivalence of functions f : G → H are related to the automorphisms of G × H and have nothing to do with the finite field or vector space structure of F n p . The purpose of this presentation is to show how to extend the CCZ and EA concept to finite abelian groups.

Let f be a mapping from G to H, we call the set

G f = {(x, f (x))|x ∈ G} ⊆ G × H the
graph of f . We can generalize CCZ-and EA-equivalence to mappings between groups.

Definition 1. Let f and g be two mappings from G to H, where G and H are abelian groups. Then f and g are called CCZ-equivalent, if there exists

ϕ ∈ Aut(G × H) and c ∈ G × H, such that ϕ(G f ) = G g + c.
Furthermore, f and g are called extended affine equivalent, which is abbreviated to EA-equivalent, if ϕ fixes {(0, y)|y ∈ H}, i.e., there exist

ϕ 1 ∈ Aut(G), ϕ 2 ∈ Aut(H), c 1 ∈ G, c 2 ∈ H and ψ ∈ Hom(G, H), such that g(x) = ϕ 2 (f (ϕ 1 (x) + c 1 )) + ψ(x) + c 2 .
If we take G and H to be linear spaces over F 2 , then it is easy to see that the definition of CCZ-equivalence (EA-equivalence) above coincides with the original one defined between vectorial Boolean functions. For any automorphism ϕ ∈ Aut(G × H), if ϕ(G f ) is the graph of some mapping from G to H, then we call ϕ a CCZ-transformation of f , and we define CCZ(f ) = {g | ϕ(G f ) = G g }, namely the mappings from G to H obtained by CCZ-transformations of f on G f . Furthermore, if ϕ fix {(0, y)|y ∈ H}, then we call ϕ an extended affine transformation (EA-transformation) of f , and we define EA(f

) = {g | ϕ(G f ) = G g , ϕ(0, H) = (0, H)}.
It is pointed out that CCZ equivalence preserves linear and differential properties of functions for the case of abelian groups as well, see Remark 1 of [START_REF] Budaghyan | New classes of almost bent and almost perfect nonlinear polynomials[END_REF], and [START_REF] Carlet | Highly nonlinear mappings[END_REF], [START_REF] Pott | Nonlinear functions in abelian groups and relative difference sets[END_REF].

Obviously, for any mapping f between two finite abelian groups G and H, CCZ(f ) ⊇ EA(f ). However, for some cases, they are the same. For example, -f (x) = ψ(x) + a, where ψ ∈ Hom(G, H) and a ∈ H; -f is a planar function over a finite field with odd characteristic, see [START_REF] Gohar | Some theorems on planar mappings[END_REF]; -As a generalization of the previous example, let f : F p n → F p m , and all its derivatives are surjective, see [START_REF] Budaghyan | New commutative semifields defined by new pn multinomials[END_REF].

Therefore, it is natural to ask, for given abelian groups G and H, whether there is a mapping f : G → H, such that CCZ(f ) = EA(f ). Obviously when gcd(|G|, |H|) = 1, any ϕ ∈ Aut(G × H) always fixes H, hence CCZ-equivalence coincides with EA-equivalence. Result 1 is another example. On the other hand, we expected that for most pairs of abelian groups (G, H) with gcd(|G|, |H|) = 1, there always exists mappings f, g : G → H, such that f and g are CCZ-equivalent but not EA-equivalent, for example:

f, g : Z/4Z → Z/4Z defined by

f = 0 1 2 3 0 0 1 1 , g = 0 1 2 3 0 1 0 1 ;
-Let n be an integer strictly greater than 8, and let mappings f and g be defined from Z/nZ to itself as follows:

f : 0 1 2 3 4 • • • n -2 n -1 2 0 1 -3 0 • • • 0 0 , g : 0 1 2 3 4 • • • n -2 n -1 -3 0 2 1 0 • • • 0 0 .
It is just elementary calculation to prove that the two examples above are CCZ but not EA-equivalent. Furthermore, for n = 6, 8, similar pairs of (f, g) can also be found. Moreover, for n = 3, 5, 7, we used MAGMA for an exhaustive search, and it showed that for any mapping f : Z/nZ → Z/nZ, we have CCZ(f ) = EA(f ). The organization of this paper is as follows: In next section, we show how to "extend" mappings f, g : G → H which are CCZ-equivalent but not EAequivalent to mappings f ′ , g ′ : G × K → H × L. As a corollary, Result 2 is improved. In section 3, we consider H = Z/2Z. Finally, we give the conclusions.

Extension Theorem

Our goal of this section is to prove the Extension Theorem as follows:

Theorem 1. Let G, H, G ′ and H ′ be finite abelian groups, and

G ′ = G × K, H ′ = H × L. Assume that f, g : G → H are CCZ-equivalent, but not EA-equivalent. Then there exist mappings f ′ , g ′ : G ′ → H ′ , which are CCZ- equivalent, but not EA-equivalent.
The following two lemmas are about how to get CCZ-equivalent but EAinequivalent mappings from G to H, by using some known mappings defined on two subgroups of G and H. Lemma 1. Let H, G and K be finite abelian groups, and

G ′ = G × K. Assume that mappings f, g : G → H are CCZ-equivalent, but not EA-equivalent.
Then the mappings f , ḡ : G ′ → H, which are defined as

f (x, y) = f (x), ḡ(x, y) = g(x)
for any (x, y) ∈ G × K, are CCZ-equivalent, but not EA-equivalent.

Proof. First, let us assume that G can not be expressed as a nontrivial direct product M × N , such that, for u ∈ M, v ∈ N , f (u, v) and g(u, v) are EAequivalent to some functions f ′ and g ′ respectively, which only depend on u.

Otherwise, when the above f ′ and g ′ exist, then we can consider the extension of f ′ , g

′ : M → H to M × (N × K) → H directly.
By the definition of CCZ-equivalence, there are some

ψ ∈ Aut(G × H) and c ∈ G × H, such that ψ(G f ) = G g + c.
Since there always exists some ψ ∈ Aut(G ′ × H), such that ψ| G×H = ψ, we have

ψ(G f ) = G ḡ + c.
which means f is CCZ-equivalent to ḡ. Without loss of generality, we assume that f (0) = g(0) = 0. Assume that f and ḡ are EA-equivalent, then there exist φ1

∈ Aut(G ′ ), ϕ 2 ∈ Aut(H), ψ1 ∈ Hom(G, H), ψ2 ∈ Hom(K, H), ā ∈ G ′ and b ∈ H, such that g(x) = ḡ(x, y) = ϕ 2 • f ( φ1 (x, y) + ā) + ψ1 (x) + ψ2 (y) + b, (1)
for any (x, y) ∈ G ′ . Denote φ1 (x, y) as ( φ(1)

1 (x, y), φ(2) 1 (x, y)), for any different y 1 , y 2 ∈ K, by (1) we have f ( φ(1) 1 (x, y 1 ) + a) -f ( φ(1) 1 (x, y 2 ) + a) = ϕ -1 2 • ψ2 (y 2 -y 1 ) , (2)
where

a is the G-component of ā ∈ G × K. Furthermore, denote φ(1) 1 (x, y) = ν(x) + ω(y)
, where ν ∈ Hom(G, G) and ω ∈ Hom(K, G). According to the definition of f , we have

f ( φ(1) 1 (x, y), φ(2) 1 (x, y)) = f ( φ(1) 1 (x, y)) = f (ν(x) + ω(y)) .
Therefore, when y 1 = y, y 2 = 0, (2) becomes

f (ν(x) + ω(y) + a) = f (ν(x) + a) + L(y), (3)
where

L = -ϕ -1 2 • ψ2 ∈ Hom(K, H).
Here ν can not be invertible, otherwise let y = 0 in (1), we have that f is EA-equivalent to g, which contradicts the assumption. Thus Im(ν) and Im(ω) contain subgroups M and {0} = N ∈ G respectively, such that G = M × N . By (3), f can be considered as

f (u + a 1 , v + a 2 ) = f (u + a 1 , a 2 ) + L ′ (v), where L ′ ∈ Hom(N, H) and a = (a 1 , a 2 ) ∈ M × N (L ′ is well-defined, since the value of L(y) does not depend on y, but on ω(y).) Therefore, f is EA- equivalent to f ′ (u + a 1 , v + a 2 ) := f (u + a 1 , a 2 )
, whose value only depends on u. Simultaneously, since g(x) = ϕ 2 • f (ν(x) + a) + ψ1 (x) + b, g is also EA-equivalent to some function g ′ (u, v) which only depends on the value of u. Hence, f and g contradict our assumption at the beginning of the proof.

⊓ ⊔

As a generalization of Proposition 2 for the binary fields case in [START_REF] Budaghyan | CCZ-equivalence of single and multi-output Boolean functions[END_REF], one can prove similar to [START_REF] Budaghyan | CCZ-equivalence of single and multi-output Boolean functions[END_REF]: Lemma 2. Let H, G and L be finite abelian groups, and H ′ = H × L. If mappings f, g : G → H are CCZ-equivalent, but not EA-equivalent, then the mappings f , ḡ : G → H ′ , which are defined as,

f (x) = (f (x), 0), ḡ(x) = (g(x), 0),
for any x ∈ G, are CCZ-equivalent, but not EA-equivalent.

By Lemma 1 and Lemma 2, we can easily prove Theorem 1. Furthermore, we can improve Result 2 as follows:

Corollary 1. There exists mapping f : F p n → F p m , such that CCZ(f ) = EA(f ), in the following cases:

p = 2, min{n, m} ≥ 4 or n ≥ 6 together with m ≥ 2;

-p = 3, n ≥ 4 and m > 1 or n = m = 3; -p = 5, 7, n ≥ 2, m ≥ 1; -p > 7, n and m ≥ 1.
For p = 2, we use the mappings f : [START_REF] Budaghyan | CCZ-equivalence of single and multi-output Boolean functions[END_REF] when n = m = 4 or n = 6 together with m = 2, as a "start point" to do extension. Then the result follows.

F 2 n → F 2 m with CCZ(f ) = EA(f ), constructed in
For p = 3, we do not find any start point better than Result 2. But we do not need the "smallest divisor of n" anymore by Theorem 1

For p = 5, 7, we can construct some mapping from (Z/pZ) 2 to Z/pZ, which will appear in the full version of this paper. Then by Theorem 1, the result follows.

For p > 7, the statement holds by Theorem 1 and the example listed at the end of Section 1 .

The case H = Z/2Z

It is well known that a finite abelian group is isomorphic to a product of cyclic groups by the fundamental theorem of finitely generated abelian groups. About the automorphism groups of finite abelian groups, the first complete characterization is contained in [START_REF] Ranum | The group of classes of congruent matrices with application to the group of isomorphisms of any abelian group[END_REF]. For an accessible and modern treatment, see [START_REF] Hillar | Automorphisms of finite abelian groups[END_REF] by Hillar and Rhea.

Let

H p = n i=1 Z/p ei Z, where p is a prime, 1 ≤ e 1 ≤ • • • ≤ e n .
Let π i : Z → Z/p ei Z be the standard quotient mapping π i (h) = h, and π : Z n → H p be the homomorphism given by

π(h 1 , . . . , h n ) = (π 1 (h 1 ), . . . , π n (h n )) = ( h1 , . . . , hn )
For convenience, sometimes we also use column vectors to express the element in H p , especially when we interpret a homomorphism by a matrix as follows: Lemma 3. [START_REF] Hillar | Automorphisms of finite abelian groups[END_REF] Let the set R p be defined as

R p = {(a ij ) ∈ Z n×n : p ei-ej divides a ij f or all i, j satisf ying 1 ≤ j ≤ i ≤ n}.
Then, the map ψ : R p → End(H p ) given by ψ(A)( h1 , . . . , hn ) T = π(A(h 1 , . . . , h n ) T ) is a surjective ring homomorphism. Furthermore, an endomorphism M = ψ(A) is an automorphism if and only if (A mod p) ∈ GL n (F p )

The lemma above shows that there is a close connection between linear mappings and automorphisms of abelian p-groups. Since it seems more common to use column vectors, when linear mappings are expressed by matrices, we decided to use "column notation" in this section.

As we mentioned in the introduction, Budaghyan and Carlet recently proved that for n-variable Boolean functions, CCZ-equivalence coincides with EA-equivalence [START_REF] Budaghyan | CCZ-equivalence of single and multi-output Boolean functions[END_REF]. In this section, we will generalize this result to mappings from finite abelian groups to Z/2Z, using another proof method.

Theorem 2. Let G be a finite abelian group, then there do not exist mappings f, g : G → Z/2Z, such that f and g are CCZ-equivalent, but not EA-equivalent. In other words, for the mappings from G to Z/2Z, CCZ-equivalence coincides with EA-equivalence.

Proof. Let f be a mapping from G to Z/2Z. For any CCZ-transformation of f , if we can prove that it can be expressed by the composition of several EAtransformations, then we prove the claim in the theorem.

Let µ be a CCZ-transformation of f , which can be expressed as

µ x y = ϕ 1 (x) + ψ 1 (y) ϕ 2 (x) + ψ 2 (y) ,
where ϕ 1 ∈ Hom(G, G), ϕ 2 ∈ Hom(G, Z/2Z), ψ 1 ∈ Hom(Z/2Z, G), and ψ 2 ∈ Hom(Z/2Z, Z/2Z).

Next, we consider two cases depending on the invertibility of ϕ 1 :

Case 1. If ϕ 1 is invertible, i.e. then we can define ν ∈ Aut(G × Z/2Z) as ν(x, y) T = (ϕ -1 1 (x), y -ϕ 2 • ϕ -1 1 (x)) T . Then we have, ν • µ x y = x + ϕ -1 1 • ψ 1 (y) ψ 2 (y) -ϕ 2 • ϕ -1 1 • ψ 1 (y) . Since ν • µ is an automorphism, ψ 2 -ϕ 2 • ϕ -1 1 • ψ 1 is the identity automorphism of Z/2Z. Denoting ϕ -1 1 • ψ 1 by ψ, we have ν • µ x f (x) = x + ψ(f (x)) f (x) .
If ψ is the zero homomorphism, then we have

µ(x, f (x)) T = ν -1 (x, f (x)) T ,
which means that µ (the CCZ-transformation of f ), can be achieved by an EAtransformation of f , since ν -1 is also an EA-transformation. If ψ is not the zero homomorphism, then we denote a = ψ(1), and obviously, ord(a) = 2. For any s ∈ G, if f (s) = 1 and s + a = t, then f (t) = 1, otherwise, x + ψ(f (x)) will not be a permutation of G (consider the value of x + ψ(f (x)) for x = s and x = s + a). Furthermore, t + a = s, since ord(a) = 2. That means, by adding ψ • f (x), we just permute the elements {s ∈ G|f (s) = 1} in G, and the graph is still that of f . Therefore, we have

ν • µ(G f ) = G f ,
which means again that µ can be achieved by an EA-transformation of f , since ν -1 is also an EA-transformation.

Case 2. If ϕ 1 / ∈ Aut(G), i.e. ϕ 1 is not invertible, then we have Im(ψ 1 ) ∼ = Z/2Z and G ∼ = Im(ϕ 1 ) × Im(ψ 1 ), since Z/2Z does not have a nontrivial subgroup.

First we assume that |G| is a power of 2, and

G ∼ = n i=1 (Z/2 ei Z), 1 = e 1 ≤ e 2 ≤ • • • ≤ e n .
By Lemma 3 and choosing proper "basis" of G, µ corresponds to an (n + 1) × (n + 1) matrix M ∈ R 2 , such that (M mod 2) ∈ GL n+1 (F 2 ), and

M =        t 1 t 2 t 3 • • • t n+1 1 0 0 • • • 0 s 2 m 21 m 22 • • • m 2n . . . . . . . . . • • • . . . s n m n1 m n2 • • • m nn        , which acts on Z/2Z × n i=1 (Z/2 ei Z) ∼ = Z/2Z × G. As M is in R 2 ,
which can be naturally considered as an (n + 1) × (n + 1) matrix over Z/2 en Z, we can do the elementary linear operations as those for the matrix over a field. Fix the first row of M , after a series of elementary row operations without interchanging of row i and row j, with e i = e j , we can get

       t 1 t 2 t 3 • • • t n+1 1 0 0 • • • 0 0 a 2 1 . . . . . . . . . 0 a n 1       
, where a i = 2 ei-1 or 0 mod 2 ei , for 2 ≤ i ≤ n. Finally, subtracting the rows 2, . . . , n + 1 from the first row, we get

N =        0 1 0 • • • 0 1 0 0 • • • 0 0 a 2 1 . . . . . . . . . 0 a n 1       
, since (M mod 2) is invertible. Moreover, it is easy to see that all these linear operations from M to N can also be expressed as a matrix A, which corresponds to an automorphism of Z/2Z × G, denoted by α. Furthermore, α is an EAtransformation, because all the elementary row operations we have applied above correspond to EA-transformations.

Let x = (x 1 , x 2 , • • • , x n ) ∈ n i=1 (Z/2 ei Z), then we have A • M f (x) x =        x 1 f (x) x 2 + a 2 x 1 . . . x n + a n x 1       
, which means that for fixed Let EA-transformation τ = (µ -1 1 , id), then τ •µ(k, l, f (k, l)) T = (k, µ 2 (l, f (k, l))) T . In the proof when G is a 2-group, we see that the EA-transformation α and x ′ only depend on µ 2 . Therefore, we can also find some α ∈ Aut(

x ′ i = x i + a i x 1 with 2 ≤ i ≤ n, there must be f (x) = x 1 or x 1 + 1 to ensure that α • µ is a CCZ-transformation. Notice that if f (x) = x 1 , then A • M (1, 1, x 2 , • • • , x n ) T = (1, 1, x ′ 2 , • • • , x ′ n ) T A • M (0, 0, x 2 , • • • , x n ) T = (0, 0, x ′ 2 , • • • , x ′ n ) T If f (x) = x 1 + 1, then A • M (0, 1, x 2 , • • • , x n ) T = (1, 0, x ′ 2 , • • • , x ′ n ) T A • M (1, 0, x 2 , • • • , x n ) T = (0, 1, x ′ 2 , • • • , x ′ n ) T Thus it is not difficult to see that A • M (f (x), x) T is just the graph of (f (x), x ′ ) T with x ′ = (x 1 , x ′ 2 , • • • , x ′ n ),
n i=1 (Z/2 ei Z)) here, such that (id, α) • τ • µ(k, l, f (k, l)) T = (k, l ′ , f (k, l)) T , which means that (id, α) • τ • µ is an EA-transformation of f , hence CCZ(f ) = EA(f ).
⊓ ⊔

Conclusions

In Theorem 1, we need the condition that the extension of G (or H) is splitting. Naturally, one question is: whether these splitting conditions are really needed? Namely, Question 1. Let G, H, G ′ and H ′ be finite abelian groups, and H ≤ H ′ , G ≤ G ′ . Assume that f, g : G → H are CCZ-equivalent, but not EA-equivalent. Is it true that we can always find mappings f ′ , g ′ : G ′ → H ′ , which are CCZ-equivalent, but not EA-equivalent?

One difficulty to extend the proof of Theorem 1 is: if G ′ or H ′ is not a splitting extension of G or H respectively, then it is possible that some automorphism ϕ of G × H is not induced, i.e. ϕ = ψ| G×H , for any ψ ∈ Aut(G ′ × H ′ ). Therefore, it is difficult to construct f ′ , g ′ from f, g, such that f ′ and g ′ are also CCZ-equivalent.

Let G and H be finite abelian groups, and gcd(|G|, |H|) > 1. For any mapping f : G → H, if G or H satisfies the following conditions, then CCZ(f ) = EA(f ):

1. G = Z/2Z, Z/3Z or (Z/2Z) 2 ; 2. H = Z/2Z; 3. H = (Z/2Z) n × L with |L| odd, when G = Z/4Z.
The proof is not difficult. For all the mappings f : Z/3Z → H, we can assume that f (0) = 0 without loss of generality (otherwise we can use EAtransformation to subtract f (x) by f (0)). Furthermore any CCZ-transformation can only permute 1 and -1 in Z/3, which can be also achieved by the unique non-identity automorphism of Z/3Z. Therefore, for any mapping here, CCZequivalence always coincides with EA-equivalence. It is the same for any f : Z/2Z → H.

For G = (Z/2Z) 2 , any f : G → H can be written as

  0 1 0 1 0 0 1 1 0 h 1 h 2 h 3   ,
by assuming that f (0) = 0 as in case 1. For any CCZ-transformation, there are corresponding ψ ∈ Hom(H, G) and ϕ ∈ Hom(G, G), such that ν := ((0, 0), ψ(h 1 ), ψ(h 2 ), ψ(h 3 )) + ((0, 0), ϕ(1, 0), ϕ(0, 1), ϕ(1, 1))

which contains all the elements of G as its entries. However, there always exists γ ∈ Aut(G), such that ((0, 0), γ(1, 0), γ(0, 1), γ(1, 1)) = ν, since there are totally 3! = 6 possible ν, and |Aut(G)| also equals 6. Case 2 is just Theorem 2.

For any mapping f from G = Z/4Z to H = (Z/2Z) n × L with 2 ∤ |L| and f (0) = 0, we should first notice that the CCZ-transformation of a given mapping f on it, could only permute 1 and 3 in G. However, Aut(G) also permute them in this way. Therefore CCZ(f ) = EA(f ).

In fact, this list is not complete. For example, we can use computer to show that CCZ(f ) = EA(f ) for any f : Z/5Z → Z/5Z. However, we expect that there are only finite pairs of (G, H) except for these three cases. This expectation is based on experience working with CCZ and EA equivalence problems, and it is not based on computational data. An asymptotic version of this question can be written as: Question 2. Let G and H be finite abelian groups, and gcd(|G|, |H|) > 1. Is there an integer B, such that when max{|G|, |H|} ≥ B, there always exist CCZequivalent but EA-inequivalent mappings f, g from G to H, except for the 3 cases mentioned above.

  which means that α • µ is an EA-transformation of f . Since α is also an EA-transformation, we have CCZ(f ) = EA(f ). Now, let G ∼ = K × n i=1 (Z/2 ei Z) with |K| odd, and we denote the elements of G by (k, l), where k ∈ K and l ∈ n i=1 (Z/2 ei Z). Since |K| is odd, we can write µ as µ(k, l, f (k, l)) T = (µ 1 (k), µ 2 (l, f (k, l))) T .

Acknowledgements

We are grateful to an anonymous referee for the valuable comments on the proof of Theorem 2. The second author is partially supported by China Scholarship Counsel.


Chi Vo-Van

Stefan Schumacher

Johann Coraux

Violetta Sessi

Olivier Fruchart

Nick B Brookes

Philippe Ohresser

Thomas Michely

Magnetism of cobalt nanoclusters on graphene on iridium

The structure and magnetic properties of Co clusters, comprising from 26 to 2700 atoms, selforganized or not on the graphene/Ir(111) moiré, were studied in situ with the help of scanning tunneling microscopy and X-ray magnetic circular dichroism. Surprisingly the small clusters have almost no magnetic anisotropy. We find indication for a magnetic coupling between the clusters. Experiments have to be performed carefully so as to avoid cluster damage by the soft X-rays.

A noticeable effort is focused at theory level on understanding the magnetic properties of graphene in the presence of transition metals like Fe, Co or Ni. For example, the graphene-mediated exchange interaction between adatoms or impurities each holding a net magnetic moment has been explored and unconventional scaling with distance has been anticipated. 1 Also, magnetic anisotropies as high as required for room-temperature magnetic storage have been predicted for Co dimers. 2 So far, experimentalists investigated simpler systems, most prominently the interface between a ferromagnetic layer and graphene. These are indispensable for basic information on proximity-induced magnetic moments in carbon 3 or the graphene/Co magnetic anisotropy. 4 A step towards low-dimensional systems are assemblies of equally sized Fe, Co or Ni clusters comprising a 10-10 3 atoms, which are well adapted to the study of the size-dependent magnetic properties. Such clusters can be prepared on epitaxial graphene, e.g. on Ir(111), 5 Rh(111), 6 or Ru(0001), 7 using graphene moirés as templates.

Using X-ray magnetic circular dichroism (XMCD), we explore the magnetism of Co clusters on graphene/Ir(111), which we relate to the cluster size and distribution by scanning tunneling microscopy (STM). Surprisingly, we find extremely weak magnetic anisotropies, although orbital moments are found to be slightly enhanced compared to bulk values. We also identify degradation of the clusters upon exposure to the X-ray beam.

Magnetic measurements and STM were performed in two interconnected ultra-high vacuum chambers; high resolution STM was performed using the same sample preparation in another system. Ir(111) was a) Electronic mail: Johann.Coraux@grenoble.cnrs.fr cleaned by cycles of Ar + sputtering and flash annealing to 1500 K. Graphene on Ir(111) was prepared by chemical vapor deposition of ethene following a two step procedure yielding a closed and perfectly oriented monolayer. 8 Co, Ir, and Pt evaporation was performed close to room temperature. The deposited amount θ [specified in ML, 1 ML being the surface atomic density of Ir(111)] was calibrated through STM for layers grown directly on Ir(111). XMCD was conducted at the ID08 beamline of the European Synchrotron Radiation Facility, monitored in the total electron yield (TEY) mode using (99±1%) circularly polarized light and up to ±5 T magnetic fields. Through seeding with Pt and Ir, for small θ < 1 ML ordered arrays of Co clusters with the moiré pitch of 2.5 nm are formed, while for large θ > 1 ML still dense arrays are obtained, but each clus-TABLE I. Orbital (mL), spin (mS) magnetic moments and their ratio (mL/mS) at 5 T with the X-ray beam perpendicular to the samples, which were prepared with different deposited amount of seeding and magnetic material (θ), and the average cluster distance (d) for each sample (except for Pt13Co26, where d is the moiré pitch). ter spans several moiré cells and is anchored by several seeds. 5 Deposition of Co without seeds leads to sparse, disordered cluster assemblies. Here we focus on three samples (Tab. I): triangular lattices of Co 26 (26 atoms in average) seeded by Pt 13 (Fig. 1a), Co 500 seeded by three to four Ir 15 , Ir 50 hereafter, (Fig. 1b), and pure Co 2700 (Fig. 1c). Results for Pt The TEY was measured at 10 K and ±5 T across the Co L 2,3 absorption edges for left-and right circular polarizations of an X-rays beam entering the sample under varying incidence from normal to grazing (70 • ). Subtracting the TEY measured for ±5 T or opposite polarizations yields the XMCD signal. Figure 2a shows the TEY of Pt 13 Co 26 at 5 T in normal incidence for both circular polarizations, while Figure 2b shows the XMCD signal for normal and grazing incidence. No sign of Co oxidation is seen. Magnetization versus field (M-H) loops were obtained by subtracting the TEY measured at the Co L 3 edge (779 eV) by the pre-edge value at 774 eV, and then normalizing to the pre-edge value. We used sum rules 9 with the number of holes value for bulk and followed the procedure described in Ref. 10 for deriving the orbital (m L ) and effective spin (m S , including a dipolar term) magnetic moments at 5 T, where the M-H loops are close to saturation (Fig. 3). We find m S = 1.5 ± 0.2 µ B , comparable to the bulk value of 1.62 µ B . On the contrary, m L /m S is larger than the 0.095 bulk value 11 . Increasing the cluster size (Ir 50 Co 500 and Co 2700 ) does not substantially modify m S , but results in a decrease of m L /m S towards the bulk value (see Tab. I). Within the limit of uncertainties, m L is found identical for all incidences and all sizes. M-H loops display very weak anisotropies for all cluster sizes (Fig. 3). For Pt 13 Co 26 clusters they do not seem to reach saturation and show no hysteresis down to 10 K (Fig. 3). A decrease of the zero-field susceptibility is observed as temperature increases (Fig. 3). Larger clusters have non-zero coercivity, which vanishes at 40±5 K.

The enhancement of m L /m S for small clusters compared to the bulk is typical of small-size objects and arises from the local loss of symmetry (lower coordination or strain).The anisotropy of m L (data not shown for grazing incidence X-rays) is here neg-ligible. Within the Bruno model linking the magnetic anisotropy energy (MAE) with the anisotropy of m L (arising from crystal structure, strain and interface hybridization), 12 this is consistent with the nearly isotropic hysteresis loops. We do not consider dipolar anisotropy here, as the arrangement of the magnetic atoms in the seeded clusters is unknown. The observation of weak MAE whatever the environment (Pt or Ir seeding) and cluster size is surprising and contrasts with other low-dimensional magnetic systems on metal surfaces. 10,13,14 The absence of coercivity and the decrease of the zero-field susceptibility with increasing temperature are strong indications that the Pt 13 Co 26 cluster lattices are superparamagnetic, as often the case for nanoclusters. Given the close-to-isotropic magnetic properties of the clusters, the M-H loops were fitted with a Langevin function, i.e. assuming no magnetic anisotropy. An additional slope was included in the fits, as discussed latter. The resulting magnetic moment m = 107 ± 19 µ B was found mostly independent of temperature, confirming the relevance of the fitting function. Dividing m by the number of Co atoms per cluster gives 4.1 µ B per atom. This value is unphysical for metallic Co even in low coordination 13 and largely exceeds that derived from sum rules (applied at 5 T, i.e. beyond the [-1,+1] T field region where most variations of the Langevin function occur). The occasional coalescence of two or three clusters as visible in Fig. 1a cannot account for the high value of m as only 15 % of the islands are involved. The large m value hence points to correlated spin blocks significantly larger than a single cluster, due to magnetic coupling between neighboring clusters. The origin of this coupling, dipolar, magnetic exchange either direct between Co atoms from neighboring clusters, or indirect through graphene, is at this stage speculative.

Let us also address the linear susceptibility (linear slope), dominating M-H loops above ±2 T (Fig. 3), which was taken into account in the fitting as an additional slope. The slope is independent from temperature, hinting at an origin different from superparamagnetism. Such linearity up to fields much higher than the expected spontaneous magnetization cannot be ascribed to dipolar energy. It may instead indicate exchange interactions favoring antiparallel or non-collinear magnetization arrangements. Whether this non-collinearity arises within each cluster in a hedge-hog fashion 15 or from a block of neighboring clusters remains speculative with the present data.

For larger clusters (Ir 50 Co 500 and Co 2700 ), the vanishing of coercivity (40±5 K) is presumably dom-inated by the blocking temperature of the largest clusters, around 10 nm in diameter and 3 nm in height for Co 2700 assemblies.

Finally, we discuss the degradation of the clusters upon exposure to X-rays. As documented by the inset of Fig. 2b, the XMCD signal decreases through

FIG. 1 .

 1 FIG. 1. STM topographs of metal clusters on graphene/Ir(111): (a) Co26 seeded by Pt11, (b) Co500 seeded by Ir50, and (c) pure Co2700.

  Sampleθ (ML) d (nm) mS (µB) mL (µB) mL/mS Pt13Co26 0.13/0.25 2.51.5 ± 0.2 0.22 ± 0.02 0.15±0.04 Ir50Co500 0.17/1.70 4.8 1.7 ± 0.2 0.20 ± 0.02 0.12±0.03 Co2700 0.25 30 1.7 ± 0.2 0.18 ± 0.02 0.11±0.03

FIG. 2 .

 2 FIG. 2. (a) TEY from Pt13Co26 clusters across the L2,3 Co absorption edges, for left and right circularly polarized X-rays in perpendicular (⊥) incidence, at 5 T and 10 K. (b) XMCD signals for ⊥ and 70 • incidence (vertically shifted for clarity). Inset: XMCD signal normalized to absorption for Ir4Co8, at the beginning and after eight hours of irradiation.

FIG. 3 .

 3 FIG. 3. Normalized M-H loops (upper horizontal axis) at 10 K for samples of Table I for in-plane (70 • ) and perpendicular (⊥) incidence. Temperature-dependent M-H loops (lower horizontal axis) and Langevin fits for Pt13Co26 at ⊥ incidence. Curves are vertically shifted.

h irradiation by 40%, as derived from sum rules. Surfaces measured after the same waiting time, but not exposed to the beam, did not show any reduction of moment. Therefore surface contamination may be excluded. Consequently, the beam induces damage to the sample. Such a degradation is common for fragile magnetic species16,17 but is usually not observed for metal clusters. We surmise that the X-ray beam promotes the decomposition of graphene by the clusters, similar to what happens at elevated temperature.18 Then, carbon enrichment of the clusters might be liable for the reduction of the Co XMCD signal.

We thank A. Fondacaro for technical assistance. T. M. and S. S. acknowledge financial support from the Deutsche Forschungsgemeinschaft (MI581/17-2), C.V.-V. from the Nanosciences Fondation. Research supported by the French ANR contract ANR-2010-BLAN-1019-NMGEM.