Igor Boyarinov
email: i.boyarinov@mtu-net.ru

Three-Dimensional Fire Codes

Keywords: Burst-error-correcting codes, three-dimensional array codes, cyclic Fire codes, encoding and decoding

Binary cyclic three-dimensional array codes that can correct three-dimensional bursts (or clusters ) of errors are considered. The class of binary cyclic three-dimensional burst-error-correcting array codes, called three-dimensional Fire codes, is constructed. Several important properties such as the burst-error-correcting capability and the positions of the parity-check symbols are presented. Also, encoding and decoding algorithms are given.

Introduction

In some memory devices, information is stored in three dimensions. In such cases, errors usually take the form of three-dimensional bursts. For example, correction of three-dimensional error bursts is required in holographic storage. Three-dimensional array codes are very suitable for correcting error bursts in such data structures.

For integers n l , l = 1, 2, 3 we consider the linear space V (n 1 , n 2 , n 3 ) of all binary three-dimensional n 1 × n 2 × n 3 arrays. A linear k-dimensional (k ≤ n 1 n 2 n 3 ) subspace C(n 1 , n 2 , n 3 ) of the space V (n 1 , n 2 , n 3 ) is called a linear binary three-dimensional array [n 1 ×n 2 ×n 3 , k] code of size n 1 ×n 2 ×n 3 with k information symbols and r = n 1 n 2 n 3k parity-check symbols. Thus, a code word of the binary linear three-dimensional array code C(n 1 , n 2 , n 3 ) is a three-dimensional array c = (c i,j,h ) where c i,j,h = 0, 1 for i = 0, 1, . . . , n 1 -1; j = 0, 1, . . . , n 2 -1; h = 0, 1, . . . , n 3 -1.

A linear three-dimensional array code C(n 1 , n 2 , n 3 ) is said to be a threedimensional cyclic array code if and only if any cyclic shift of any codeword c = (c i,j,h ) is also a codeword of the code

C(n 1 , n 2 , n 3 ). The cyclic shift of c = (c i,j,h ) is n 1 × n 2 × n 3 array c = (c i+l1,j+l2,h+l3
) where l 1 , l 2 , l 3 are arbitrary integers and the subscripts m, t, u of c = (c m,t,u ) are calculated modulo n 1 , n 2 , n 3 , respectively.

A three-dimensional array e = (e i,j,h ) of size

n 1 × n 2 × n 3 is called a three-dimensional parallelepipedal b 1 × b 2 × b 3 -burst if
1) e u1+p1,u2+p2,u3+p3 = 0 or 1 for some 0 ≤ u l < n lb l and any 0 ≤ p l < b l , l = 1, 2, 3;

2) e u1+p1,u2,u3 e u1,u2+p2,u3 e u1,u2,u3+p3 = 1 for at least one triple p 1 , p 2 , p 3 ; 3) the others e i,j,h = 0. Thus, a b 1 × b 2 × b 3 -burst e = (e i,j,h ) can contain nonzero symbols only within submatrix e p = (e u1+p1,u2+p2,u3+p3 ), p l = 0, 1, . . . , b l -1, l = 1, 2, 3.

The triple u 1 , u 2 , u 3 and submatrix e p are called the starting position and the pattern of a three-dimensional parallelepipedal b

1 × b 2 × b 3 -burst e, respectively. A cyclic shift of a b 1 × b 2 × b 3 -burst is called a cyclic b 1 × b 2 × b 3 -burst. Of course, a b 1 × b 2 × b 3 -
burst is a cyclic burst, but the converse does not always hold. The starting position and the pattern of the cyclic burst are not necessarily unique. A necessary and sufficient condition for all cyclic b 1 × b 2 × b 3 -bursts e i,j,h to have unique starting positions and patterns is n l ≥ 2b l -1, l = 1, 2, 3 (see Lemma 1 in [START_REF] Abdel-Ghaffar | Two-dimensional burst identification codes and their use in burst correction[END_REF]).

The three-dimensional b 1 × b 2 × b 3 -bursts have a parallelepipedal shape. In some papers (see, for example, [START_REF] Blaum | Interleaving schemes for multidimensional cluster errors[END_REF] ), it is assumed that bursts can have an arbitrary shape. The approach in these papers is to use interleaving schemes. In this paper we consider parallelepipedal bursts.

A linear three-dimensional array code is a b

1 ×b 2 ×b 3 -burst-error-correcting code if it has no nonzero codeword which is a b 1 × b 2 × b 3 -burst or a sum of two b 1 × b 2 × b 3 -bursts. A linear three-dimensional cyclic array a b 1 × b 2 × b 3 - burst-error-correcting code corrects cyclic b 1 × b 2 × b 3 -bursts of errors.
The redundancy (the number of parity-check symbols) of a linear threedimensional array b 1 ×b 2 ×b 3 -burst-error-correcting code satisfies the inequality

r ≥ 2b 1 b 2 b 3 . (1)
There are some papers, devoted completely or partly three-dimensional array burst-error-correcting codes ([2] - [START_REF] Etzion | Error-correction of multidimensional bursts[END_REF]). In [START_REF] Blaum | Interleaving schemes for multidimensional cluster errors[END_REF] the construction of threedimensional interleaving schemes is given. In [START_REF] Boyarinov | Three-dimensional cluster-error-correcting array codes[END_REF] a class of linear three-dimensional b 1 × b 2 × b 3 -burst-error-correcting array codes with the redundancy 4b 1 b 2 b 3 is given. In [START_REF] Boyarinov | Three-dimensional array SCEC codes with small excess redundancy[END_REF], [START_REF] Boyarinov | Three-dimensional array codes correcting 2 × 2 × 2-clusters of errors[END_REF] the constructions of linear three-dimensional b 1 ×b 2 ×b 3 -bursterror-correcting array codes with the small excess redundancy are presented. In [START_REF] Etzion | Error-correction of multidimensional bursts[END_REF] the existence of almost optimal m-dimensional (m ≥ 3) burst-errorcorrecting array codes is shown.

In this paper we consider binary linear cyclic three-dimensional burst-errorcorrecting array codes. The class of binary cyclic three-dimensional burst-errorcorrecting array codes, called three-dimensional Fire codes, is constructed. Several important properties such as the burst-error-correcting capability and the positions of the parity-check symbols are presented. Also, encoding and decoding algorithms are given.

Three-Dimensional Cyclic Array Codes and Bursts

An one-dimensional binary cyclic (n, k) code is defined as an ideal of the residue class ring

R n = F 2 [x]/ x n -1 of the polynomial ring F 2 [x] over F 2 = GF (2)
with respect to an ideal x n -1 [START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]. The polynomial representation of codewords is used for description of cyclic two-dimensional array codes [START_REF] Abdel-Ghaffar | Two-dimensional burst identification codes and their use in burst correction[END_REF], [START_REF] Nomura | A theory of two-dimensional linear recurring arrays[END_REF]- [START_REF] Boyarinov | Two-dimensional array codes correcting rectangular burst errors[END_REF]. For the description of cyclic three-dimensional array codes it is also convenient to use a polynomial representation of codewords.

Let F 2 [x, y, z] be a polynomial ring in three variables x, y, z over

F 2 . Let c(x, y, z) = i∈I j∈J h∈H c i,j,h x i y j z h
where I, J, H are finite sets of integers.

We will suppose that monomials c i,j,h x i y j z h in c(x, y, z) are lexicographically ordered [START_REF] Cox | Ideals,Varieties,and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF]. Denote by deg x c(x, y, z), deg y c(x, y, z) and deg z c(x, y, z) the maximal degrees of variables x, y and z in monomials c i,j,h x i y j z h ∈ c(x, y, z), respectively.

If c i,j,h x i y j z h defines an isomorphism between V n1,n2,n3 and R n1,n2,n3 . If C n1,n2,n3 is a three-dimensional cyclic array code and c = (c i,j,h ) ∈ C n1,n2,n3 , then the cyclic shift c ′ = (c i+l1,j+l2,h+l3 ) ∈ C n1,n2,n3 . The cyclic shift c ′ = (c i+l1,j+l2,h+l3 ) corresponds the polynomial c ′ (x, y, z) = x l1 y l2 z l3 c(x, y, z). The residue class ring R n1,n2,n3 is a n 1 n 2 n 3 -dimensional linear space over F 2 . Thus, a linear cyclic three-dimensional array code

f 1 (x, y, z), . . . , f s (x, y, z) are polynomials in F 2 [x, y, z], then f 1 (x, y, z), . . . , f s (x, y, z) = { s l=1 a l (x, y, z)f l (x, y, z) : a l (x, y, z) ∈ F 2 [x, y, z] } (2) is the ideal in F 2 [x, y, z] and the set {f 1 (x, y, z), . . . , f s (x, y, z)} is the basis of the ideal. Let R n1,n2,n3 = F 2 [x, y, z]/ x n1 -1, y n2 -1, z n3 -1 be a residue class ring of F 2 [x, y, z] with respect to an ideal x n1 -1, y n2 - 1, z n3 -1 . All distinct polynomials c(x, y, z) ∈ F 2 [x,
C n1,n2,n3 is an ideal in the residue class ring R n1,n2,n3 = F 2 [x, y, z]/ x n1 -1, y n2 -1, z n3 -1 .
In the polynomial representation of a linear cyclic three-dimensional array code, a polynomial e(x, y, z) The polynomial e ′ (x, y, z) is a cyclic b 1 × b 2 × b 3 -burst if e ′ (x, y, z) = x v1 y v2 z v3 e(x, y, z) for some 0 ≤ v l < n l , l = 1, 2, 3 and e(x, y, z) is a b 1 × b 2 × b 3 -burst.

= n1-1 i=0 n2-1 j=0 n3-1 h=0 e i,j,h x i y j z h is a b 1 × b 2 × b 3 -burst if e(x, y, z) = x u1 y u2 z u3 b(x, y, z) for some 0 ≤ u l < n l -b l , l = 1, 2,

Definition of Three-Dimensional Fire Codes

Two approaches are used for description of binary two-dimensional cyclic codes of area n 1 × n 2 .

First approach is the concept of common zeros of code polynomials of cyclic two-dimensional codes [START_REF] Ikai | A theory of two-dimensional cyclic codes[END_REF], [START_REF] Imai | A theory of two-dimensional cyclic codes[END_REF]. The second approach is the representation of a cyclic two-dimensional code of area n 1 × n 2 as an ideal, that is defined by means of a certain basis [START_REF] Boyarinov | Two-dimensional array codes correcting rectangular burst errors[END_REF]. In this paper we use the second approach for the definition and constructing cyclic three-dimensional Fire codes.

First, let us recall ordinary Fire codes [START_REF] Fire | A class of multiple-error-correcting binary codes for non-independet errors[END_REF] - [START_REF] Lin | Error Control Coding: Fundamentals and Applications[END_REF]. The binary cyclic Fire code is defined as cyclic code generated by the polynomial g(x) = p(x)(x c -1) where p(x) is an irreducible polynomial over GF (2) of degree m whose roots have order e and c is a positive integer not divisible by e. The code is of length n = LCM (c, e) and is capable of correcting a burst of length b, if b ≤ (c + 1)/2 and b ≤ m. A cyclic Fire code is an ideal in R n and can be considered as the intersection of ideals x c -1 and p(x) .

By analogy with one-dimensional binary cyclic Fire codes we consider threedimensional cyclic array codes as ideals, which are the intersections of ideals x c1 -1, y c2 -1, z c3 -1 and p 1 (x), p 2 (y), p 3 (z) in the residue class ring

R n1,n2,n3 = F 2 [x, y, z]/ x n1 -1, y n2 -1, z n3 -1 . Lemma 1. Let A g1,g2,g3 (x, y, z) = g 1 (x), g 2 (y), g 3 (z) be an ideal in R n1,n2,n3 = F 2 [x, y, z]/ x n1 -1, y n2 -1, z n3 -1. Then (i) g 1 (x) divides x n1 -1, g 2 (y) divides y n2 -1 and g 3 (z) divides z n3 -1;
(ii) a(x, y, z) ∈ A g1,g2,g3 (x, y, z), if and only if

a(x, y, z) = a 1 (x, y, z)g 1 (x) + a 2 (x, y, z)g 2 (y) + a 3 (x, y, z)g 3 (z), (3)
where a l (x, y, z) ∈ R n1,n2,n3 ;

(iii) for any polynomial a(x, y, z) ∈ R n1,n2,n2 there exists a unique polynomial r(x, y, z) ∈ R n1,n2,n3 , such that deg x r(x, y, z) < deg x g 1 (x), deg y r(x, y, z) < deg y g 2 (y), deg z r(x, y, z) < deg z g 3 (z) and a(x, y, z) = a 1 (x, y, z)g 1 (x) + a 2 (x, y, z)g 2 (y) + a 3 (x, y, z)g 3 (z) + r(x, y, z), (4)

a l (x, y, z) ∈ R n1,n2,n3 , l = 1, 2, 3.
The statement (ii) of Lemma 1 is equivalent to the statement, that the basis {g 1 (x), g 2 (y), g 3 (z)} of the ideal A g1,g2,g3 (x, y, z) is a Gröbner basis [START_REF] Cox | Ideals,Varieties,and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF].

Theorem 1. Let p l (u) be an irreducible polynomial over F 2 of degree m l whose roots have order e l , l = 1, 2, 3. Let c l be a positive integer not divisible by e l and n l = LCM (c l , e l ). Then the intersection C n1,n2,n3 (x, y, z) of the ideals

A c1,c2,c3 (x, y, z) = x c1 -1, y c2 -1, z c3 -1 and A p1,p2,p3 (x, y, z) = p 1 (x), p 2 (y), p 3 (z) in the residue class ring R n1,n2,n3 = F 2 [x, y, z]/ x n1 -1, y n2 -1, z n3 -1 is a linear cyclic three-dimensional array code of size n 1 × n 2 × n 3 correcting b 1 × b 2 × b 3 -bursts of errors if b l ≤ (c l + 1)/2 and b l ≤ m l .
The code C n1,n2,n3 (x, y, z) is called a binary three-dimensional Fire code.

Let m 2 = m 3 = 1 and c 2 = c 3 = 1. Then C n1,n2,n3 (x, y, z) is reduced to the binary cyclic one-dimensional Fire code, generated by p 1 (x)(x c1 -1).

Encoding Three-Dimensional Fire Codes

Let code C n1,n2,n3 (x, y, z) be a binary three-dimensional Fire code and

c(x, y, z) = n1-1 i=0 n2-1 j=0 n3-1 h=0
c i,j,h x i y j z h be a codeword.

Let P 1 = {i, j, h : 0 ≤ i < c 1 , 0 ≤ j < c 2 , 0 ≤ h < c 3 }; P 2 = {i, j, h :

c 1 ≤ i < c 1 + m 1 , 0 ≤ j < m 2 , 0 ≤ h < m 3 }; P 3 = {i, j, h : 0 ≤ i < m 1 , c 2 ≤ j < c 2 + m 2 , 0 ≤ h < m 3 }; P 4 = {i, j, h : o ≤ i < m 1 , 0 ≤ j < m 2 , 0 ≤ h < c 3 + m 3 }.
We put coefficients c i,j,h of the code polynomial c(x, y, z) to be information symbols if triple i, j, h / ∈ P l and parity-check symbols if triple i, j, h ∈ P l , l = 1, 2, 3, 4. Let

c 0 (x, y, z) = n1-1 i=0 n2-1 j=0 n3-1 h=0 c (0) i,j,h x i y j z h (5)
be a polynomial whose coefficients c (0) i,j,h , i, j, h / ∈ P l are information symbols of the code polynomial and other coefficients are c (0) i,j,h = 0, i, j, h ∈ P l , l = 1, 2, 3, 4.

Dividing the polynomial c 0 (x, y, z) by the basis s { x c1 -1, y c2 -1, z c3 -1 } of the ideal A c1,c2,c3 (x, y, z), we obtain c 0 (x, y, z) = a 1 (x, y, z)(x c1 -1)+a 2 (x, y, z)(y c2 -1)+a 3 (x, y, z)(z c3 -1)+r 0 (x, y, z),

where deg x r 0 (x, y, z) < c 1 , deg y r 0 (x, y, z) < c 2 and deg z r 0 (x, y, z) < c 3 . Further, dividing the polynomials a l (x, y, z), l = 1, 2, 3 by the basis {p 1 (x), p 2 (y), p 3 (z)} of the ideal A p1,p2,p3 (x, y, z), we obtain

a l (x, y, z) = a (l) 1 (x, y, z)p 1 (x) + a (l) 2 (x, y, z)p 2 (y) + a (l) 3 (x, y, z)p 3 (z) + r l (x, y, z), (7)
where deg x r l (x, y, z) < m 1 , deg y r l (x, y, z) < m 2 and deg z r l (x, y, z) < m 3 .

Combining ( 6) and ( 7), we get

c 0 (x, y, z) -r 1 (x, y, z)x c1 -r 2 (x, y, z)y c2 -r 3 (x, y, z)z c3 -r 0 (x, y, z) + r 1 (x, y, z) + r 2 (x, y, z) + r 3 (x, y, z) = (a 1 (x, y, z) -r 1 (x, y, z))(x c1 -1) + (a 2 (x, y, z) -r 2 (x, y, z))(y c2 -1) + (a 3 (x, y, z) -r 3 (x, y, z))(z c3 -1) (8)
Since the right-hand side of ( 8) is a codeword of the code C n1,n2,n3 (x, y, z), the left-hand side of ( 8) is also a codeword of the code. Thus, we get the codeword c(x, y, z) = c 0 (x, y, z) + c 1 (x, y, z)

where the coefficients of the polynomial c 0 (x, y, z) are the information symbols and the coefficients of the polynomial c 1 (x, y, z) = r 1 (x, y, z) + r 2 (x, y, z) + r 3 (x, y, z)r 0 (x, y, z)r 1 (x, y, z)x c1r 2 (x, y, z)y c2r 3 (x, y, z)z c3 [START_REF] Ikai | A theory of two-dimensional cyclic codes[END_REF] are the parity-check symbols of the codeword c(x, y, z).

where the polynomials r c (x, y, z) and r p (x, y, z) are the remainders of dividing c ′ (x, y, z) by the basis { x c1 -1, y c2 -1, z c3 -1 } of the ideal A c1,c2,c3 (x, y, z) and the basis {p 1 (x), p 2 (y), p 3 (z)} of the ideal A p1,p2,p3 (x, y, z), respectively. Thus, c ′ (x, y, z) = a 1 (x, y, z)(x c1 -1)+a 2 (x, y, z)(y c2 -1)+a 3 (x, y, z)(z c3 -1)+r c (x, y, z), (13) and c ′ (x, y, z) = d 1 (x, y, z)p 1 (x)+d 2 (x, y, z)p 2 (y)+d 3 (x, y, z)p 3 (z)+r p (x, y, z). [START_REF] Peterson | Error-Correcting Codes[END_REF]

  y, z], such that deg x c(x, y, z) < n 1 , deg y c(x, y, z) < n 2 and deg z c(x, y, z) < n 3 , belong to distinct residue classes of R n1,n2,n3 . A residue class of R n1,n2,n3 will be represented by such an unique polynomial.The map c = (c i,j,h ) -→ c(x, y, z) =

  3 and a polynomial b(x, y, z), such that deg x b(x, y, z) < b 1 , deg y b(x, y, z) < b 2 , deg y b(x, y, z) < b 3 and b(x, 0, 0) = 0, b(0, y, 0) = 0, b(0, 0, z) = 0.

5

  Decoding Three-Dimensional Fire Codes Let c ′ (x, y, z) = c(x, y, z) + e(x, y, z),(11)where c(x, y, z) is a codeword of the three-dimensional Fire code and e(x, y, z)is b 1 × b 2 × b 3 -burst of errors.The syndrome of c ′ (x, y, z) is S c ′ = S e = (r c (x, y, z), r p (x, y, z)) ,

where deg x r c (x, y, z) < c 1 , deg y r c (x, y, z) < c 2 , deg z r c (x, y, z) < c 3 and deg x r p (x, y, z) < m 1 , deg y r p (x, y, z) < m 2 , deg z r p (x, y, z) < m 3 .

A decoding algorithm for three-dimensional Fire Codes can be described as follows.

1. Compute the syndrome S c ′ = S e = (r c (x, y, z), r p (x, y, z)) of the received word c ′ (x, y, z).

2. If S c ′ = (0, 0), there are no errors in c ′ (x, y, z) and c ′ (x, y, z) is a codeword.

If deg

, 0, 0) = 0, r c (0, y, 0) = 0, r c (0, 0, z) = 0 and r c (x, y, z) = r p (x, y, z), then there is the burst error e(x, y, z) = r c (x, y, z) in c ′ (x, y, z) and c(x, y, z) = c ′ (x, y, z)e(x, y, z) is a codeword. 4. For i ∈ I, j ∈ J, h ∈ H find the the remainders r (i,j,h) c (x, y, z) and r (i,j,h) c (x, y, z) of dividing the polynomial x i y j z h c ′ (x, y, z) by the basis (x,y,z) and the basis {p 1 (x), p 2 (y), p 3 (z)} of the ideal A p1,p2,p3 (x, y, z), respectively.

If deg

(0, 0, z) = 0 and r (i,j,h) c (x, y, z) = r (i,j,h) p (x, y, z), then e(x, y, z) = x n1-i y n2-j z n3-h r (i,j,h) c (x, y, z) and c(x, y, z) = c ′ (x, y, z)e(x, y, z).

5. In all other cases, the received word c ′ (x, y, z) has uncorrectable errors.


Torleiv Kløve
email: torleiv.klove@ii.uib.no

Jinquan Luo
email: jinquan.luo@ii.uib.no

Somaye Yari
email: somaye.yari@ii.uib.no

Some codes correcting single symmetric errors of limited magnitude

Keywords: Code, symmetric error, limited magnitude error

An error model with symmetric errors of limited magnitude is considered. Limited magnitude means that the size of any error is limited by a number smaller (usually much smaller) than the alphabet size. Several constructions of codes correcting single error are given. In some cases, the codes are perfect or quasi-perfect.

Introduction

In the symmetric error model, a symbol a over the alphabet Z q = {0, 1, . . . , q -1} may be modified during transmission into another symbol b ∈ Z q . For some applications, the error magnitude |b-a| is not likely to exceed a certain threshold λ. A model for an asymmetric channel with limited errors was introduced in [START_REF] Ahlswede | On qary codes correcting all unidirectional errors of a limited magnitude[END_REF]. A modified model, where wrap-around error are also possible, was considered in [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF] and [START_REF] Kløve | Systematic, single limited magnitude error correcting codes for Flash Memories[END_REF]. For this model, a can be changed to (a+e) (mod q), where 0 ≤ e ≤ λ (asymmetric errors) or 0 ≤ |e| ≤ λ (symmetric errors). In [START_REF] Kløve | Systematic, single limited magnitude error correcting codes for Flash Memories[END_REF] and [START_REF] Kløve | Some codes correcting asymmetric errors of limited magnitude[END_REF], classes of systematic codes correcting single asymmetric errors on this channel are given. The constructions are based on B[λ](q) sets. In [START_REF] Elarief | Optimal, systematic, q-ary codes correcting all asymmetric and symmetric errors of limited magnitude[END_REF] codes for correcting limited magnitude errors, symmetric and asymmetric, are studied.

In this paper, we consider construction of codes correcting single symmetric limited error. The construction is based on the analogue of B[λ](q) sets which we call C[λ](q) sets. We first give the definition of C[λ](q) sets and the code construction. Then we give several classes of C[λ](q) sets.

C[λ](q) sets and the code construction

For an integer

b ∈ [1, q -1], let Ψ (b) = {ab mod q | a ∈ [-λ, -1] ∪ [1, λ]}. (1)
A

C[λ](q) set of size m is a set of m distinct integers b 0 , b 1 , . . . , b m-1 ∈ [1, q-1]
such that all the sets Ψ (b j ), j = 0, 1, . . . , m -1 have 2λ nonzero elements, and they are disjoint.

In particular, it is necessary to have

q -1 ≥ m-1 j=0 Ψ (b j ) = 2λm. If m-1 j=0 Ψ (b j ) = [1, q -1]
, then we say that the C[λ](q) set is perfect. A necessary condition for a perfect C[λ](q) set to exist is of course that q ≡ 1 (mod 2λ).

In general, m ≤ (q -1)/(2λ) and so m ≤ ⌊(q -1)/(2λ)⌋. If q ≡ 1 (mod 2λ), then we call a C[λ](q) set of maximal size ⌊(q -1)/(2λ)⌋ quasi-perfect.

A B[λ](q) set is defined similarly, except that a in ( 1) is restricted to a ∈ [1, λ].

In [START_REF] Kløve | Systematic, single limited magnitude error correcting codes for Flash Memories[END_REF] it was shown that we can get a code correcting a single limited magnitude symmetric error based on a C[λ](q) set as follows: let

B = {b i | 0 ≤ i ≤ m -1} be a C[λ](q) set.
Let H be the r × n parity check matrix whose columns are all possible vectors over Z r q with the first non-zero element in B and let C be the null space of H T . Then this code can correct a single symmetric error of magnitude at most λ.

The goal of this paper is to give new constructions of C[λ](q) sets, some of them are modifications of the constructions of B[λ](q) sets given in [START_REF] Kløve | Systematic, single limited magnitude error correcting codes for Flash Memories[END_REF] and [START_REF] Kløve | Some codes correcting asymmetric errors of limited magnitude[END_REF].

Stein et al. [START_REF] Hickerson | Abelian groups and packing by semicrosses[END_REF], [START_REF] Stein | Factoring by subsets[END_REF], [START_REF] Stein | Packings of R n by certain error spheres[END_REF] studied C[λ](q) sets, which they called packings of crosses in Z q . In particular, [START_REF] Stein | Factoring by subsets[END_REF] considers perfect C[λ](q) sets, and it is mainly shown that perfect sets do not exist in some cases. But also some existence results are given. In our notations, [START_REF] Hickerson | Abelian groups and packing by semicrosses[END_REF] and [START_REF] Stein | Packings of R n by certain error spheres[END_REF] consider asymptotic expressions when l → ∞ for the smallest q such that there exists a C[λ](q) set of size m.

3 On perfect C[λ](p) sets for primes p Stein [START_REF] Stein | Factoring by subsets[END_REF] showed (Corollary 5.3) that if q is a prime, then a perfect C [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF](q) set exists if and only if 4 divides the order of 2 modulo q. Here, we will consider explicit constructions of perfect C[λ](q) sets for general λ.

For an odd prime p, a primitive root g modulo p, and an integer a not divisible by p, there exists a unique integer ι ∈ [0, p -2] such that g ι ≡ a (mod p). It is known as the index of a relative to the base g, and it is denoted by ind g (a). In particular, ind g (-1) = (p -1)/2. Let µ = µ λ,p = gcd (ind g (-1), ind g (2), ind g (3), . . . , ind g (λ)) .

We see that µ divides ind g (-1) + ind g (i)

≡ ind g (-i) (mod p -1) for i ∈ [1, λ]. Thus the set H = {g iµ mod p | i ≥ 0}
is the multiplicative subgroup of Z * p generated by the integers -1, 2, 3, . . . , λ. The size of H is n = (p -1)/µ. In particular, µ does not depend on g.

Theorem 1. Let λ ≥ 2 and let p > λ be a prime. If a perfect C[λ](p) set exists, then 2λ divides (p -1)/µ, that is p ≡ 1 (mod 2µλ).
Proof. Let S be a perfect C[λ](q) set. We decompose Z * p into the µ cosets of H. For any coset aH and any x ∈ aH, we have ix mod p ∈ aH for i ∈

[1, λ] ∪ [-λ, -1]. Therefore |S ∩ aH| ≤ ⌊n/(2λ)⌋. In total we get p -1 2λ = |S| ≤ n 2λ µ = n 2λ • p -1 n ≤ n 2λ • p -1 n = p -1 2λ which implies that 2λ divides n. ⊓ ⊔ Theorem 2. Let λ ≥ 2.
Let p be a prime such that p ≡ 1 (mod 2µλ), where µ = µ λ,p . Let g be a primitive root modulo p. If

ind g (j) µ mod λ | j ∈ [1, λ] = [0, λ -1],
and ν is a positive integer such that ν|µ and gcd(µ/ν, λ) = 1, then

X = g νλi+j mod p | i ∈ 0, p -1 2νλ -1 , j ∈ [0, ν -1] is a perfect C[λ](p) set.
Proof. First we note that since

ind g (j) ν = µ ν • ind g (j) µ and gcd(µ/ν, λ) = 1, we get ind g (j) ν mod λ | j ∈ [1, λ] = [0, λ -1]. (2)
Clearly, rg νλi+j ≡ 0 (mod p) for any r ∈ [1, λ]. Suppose that

rg νλi+j ≡ sg νλi ′ +j ′ (mod p) where r, s ∈ [-λ, -1] ∪ [1, λ], i, i ′ ∈ 0, p-1 2νλ -1 , and j, j ′ ∈ [0, ν -1]. Then ind g (r) + νλi + j ≡ ind g (s) + νλi ′ + j ′ (mod p -1). (3)
Modulo ν we get j ≡ j ′ (mod ν)

which implies that j = j ′ since j, j ′ ∈ [0, ν -1]
. Therefore, from (3) we obtain ind g (r) ≡ ind g (s) (mod νλ)

and so ind g (r)

ν mod λ = ind g (s) ν mod λ.
Combined with [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF], this implies that r = s or r = -s.

If r = s, (3) implies that i ≡ i ′ (mod p-1 νλ ) and so i = i ′ . Otherwise r = -s = 0. Therefore νλi ≡ p -1 2 + νλi ′ (mod p -1) which implies p-1 2 | νλ(i -i ′ ). Since 0 < |i -i ′ | ≤ p-1 2νλ -1 and 0 < |νλ(i -i ′ )| < p-1 2 , then we have i = i ′ which is a contradiction. ⊓ ⊔
Example 1. Let λ = 3 and p = 37. Then g = 2 is a primitive root and µ = 1.

Hence B = {2 3i mod 37 | 0 ≤ i ≤ 5} is a C[3](37) set. 4 A construction of C[λ](q) sets
C = {(2λ + 1)i + 1 | i ∈ [0, µ -1]} is a C[λ](q) set.
Proof. Let µ = νP λ + ω, where ω ∈ {1, -1}. Suppose that r((2λ + 1)i + 1) ≡ s((2λ + 1)j + 1) (mod (2λ + 1)µ),

where r, s ∈ [-λ, λ], (r, s) = (0, 0). Then r ≡ s (mod 2λ + 1)

and so r = s = 0. Then (4) implies that ri ≡ rj (mod µ).

Since gcd(r, µ) = 1, we get i ≡ j (mod µ)

which implies that i = j. ⊓ ⊔

On maximal C[2](p) sets

Define N 2 (q) to be the maximal size of a C [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF](q) set. In this section, we will construct maximal size C[2](q) sets for all q and determine N 2 (q) meanwhile. Denote by Z * q = {a | (a, q) = 1, 1 ≤ a ≤ q -1}. We have the following disjoint union decomposition.

Z q = {0} d>1,d|q Z q (d) with Z q (d) = {aq/d | a ∈ Z * d }. (5)

The case q is odd

In this subsection we assume that q is odd. Let d be any divisor of q. Then d is odd and let ord d (2) be the order of 2 in Z * d , that is,

ord d (2) = min{n| 2 n ≡ 1 (mod d), n > 0}.
For any positive integer n, the 2-adic exponent valuation of n, denoted by v 2 (n), is the exact power of 2 dividing n, that is, n = 2 v2(n) n ′ with n ′ odd. Suppose q has the prime factorization q = t i=0 q i where

q i = ri j=1 p ei,j i,j (6)
such that p i,j are distinct primes, e i,j ≥ 1, and v 2 (ord pi,j (2)) = i for 1 ≤ j ≤ r i .

In [START_REF] Kløve | Some codes correcting asymmetric errors of limited magnitude[END_REF] we showed the following result. (ii) For any odd prime p, suppose 2 ordp(2) = 1 + p up s p with p ∤ s p . Then

ord p k (2) = ord p (2), if k ≤ u p p k-up ord p (2), if k > u p .
For an odd integer d, define 2 d to be the cyclic subgroup of Z * d generated by 2. In order to construct maximal size C [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF](q) sets, we need to determine if -1 ∈ 2 d or not for each d with d|q. The following result provides an easy criterion.

Lemma 2. Suppose that d = n i=1 p ei i is odd, where p 1 , p 2 , . . . , p n are distinct primes, and e i ≥ 1 for

1 ≤ i ≤ n. Then -1 ∈ 2 d if and only if v 2 (ord p1 (2)) = v 2 (ord p2 (2)) = • • • = v 2 (ord pn (2)) ≥ 1. Proof. If -1 ∈ 2 d , then 2 h ≡ -1 (mod d) for some h which implies 2 h ≡ -1 (mod p i ) and 2 2h ≡ 1 (mod p i ). Hence ord pi (2) | 2h. Also, ord pi (2) ∤ h (otherwise 2 h ≡ 1 (mod p i )). Therefore v 2 (ord pi (2)) = v 2 (2h) = 1 + v 2 (h) ≥ 1 which is independent of i.
On the other hand, if

t := v 2 (ord p1 (2)) = v 2 (ord p2 (2)) = • • • = v 2 (ord pn (2)) ≥ 1, then we have t = v 2 (ord p e i i ( 2
)) for 1 ≤ i ≤ n by Lemma 1 (ii) and t = v 2 (ord d (2)) by Lemma 1 (i). Since the multiplicative group Z * p e i i is cyclic, we have 2 ord p e i i (2) 2 ≡ -1 (mod p ei i ) which implies that 2 ord d (2)/2 = 2 ord p e i i (2) 2 ord d (2)/ord p e i i (2)
≡ (-1)

ord d (2)/ ord p e i i (2) = -1 (mod p ei i ).
By the Chinese Remainder Theorem, it follows that 2 ord d (2)/2 ≡ -1 (mod d).

⊓ ⊔

Now we can present the main result of this subsection (the proof is not included in this abstract).

Theorem 4. For q odd, we have

N 2 (q) = q -1 4 - 1 4   d|q0 ϕ(d) ord d (2) + 2 d|q1 ϕ(d) ord d (2)  
where q 0 is defined in [START_REF] Kløve | Some codes correcting asymmetric errors of limited magnitude[END_REF].

Corollary 1. A C[2](q) perfect set exists if and only if v 2 (ord p (2)) ≥ 2 for any prime p dividing q.

The case q is even

In the following we consider the case when q is even. For the case q ≡ 2 (mod 4), an easy observation shows the following result.

Theorem 5. The set S = {1, 3, • • • , 2m -1} is a C[2](4m + 2)-set and N 2 (4m + 2) = m.
For the case 4 | q, we have a similar result as [5, Theorem 5].

Theorem 6. For m > 1, we have N 2 (4m) = ⌊ m 2 ⌋ + N 2 (m).
Proof. (Sketch) Let S m be a C [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF](m) set of size N 2 (m) and

T m = {1, 3, • • • , 2 • ⌊m/2⌋ -1}.
which implies that -1 is a quadratic residue. This is impossible since p ≡ 3 (mod 4). Case III: (r, s) = (λ, 0). In this case we have

a u ≡ 0 (mod p)
which is impossible. The case (r, s) = (0, -λ) is similar.

Case IV: r = s + λ with s = -σ, where σ, r

∈ [1, λ -1]. Then (λ -σ) ≡ -a v-u σ (mod p)
which leads to a contradiction since σ(λ -σ) is a quadratic residue and -a v-u is quadratic non-residue.

The condition (ii) and the quadratic reciprocity law give necessary congruences for p. These can be combined with the condition p ≡ 3 (mod 4). Numerical result indicates that if these conditions are satisfied, then we can always find a ≡ 1 (mod λ) satisfying (i).

For λ = 3, 4, 5 we get the following results: 7 Minimal q for which there exists a C[λ](q) set of size 2

• If λ = 3
Theorem 8. The minimal q for which a C[λ](q) set of size 2 exists is q = (λ + 1) 2 + 1 .

Proof. If {a, b} is a C 1 [λ](q) set, then for all x, y ∈ [0, λ], the positive residues ax + by (mod q) are different. Indeed, if

ax + by ≡ ax ′ + by ′ (mod q) for x, y, x ′ , y ′ ∈ [0, λ] with (x, y) = (x ′ , y ′ ), then a(x -x ′ ) ≡ b(y ′ -y) (mod q)
with x -x ′ , y ′ -y ∈ [-λ, λ] and (x -x ′ , y ′ -y) = (0, 0). Since there are (λ + 1) 2 distinct choices for x, y ∈ [0, λ], we have q ≥ (λ + 1) 2 .

If q = (λ + 1) 2 and {a, b} is a C[λ](q) set. Then

{ax + by (mod q) | x, y ∈ [0, λ]} = [0, q -1].
In particular, gcd(a, b, (λ + 1) 2 ) = 1.

Hence there exist x, y ∈ [0, λ] such that (λ + 1)a ≡ ax + by (mod (λ + 1) 2 ).

If x > 0, then (λ + 1 -x)a = yb (mod (λ + 1) 2 ) with λ + 1 -x, y ∈ [-λ, λ] and λ + 1 -x = 0 which is a contradiction. Therefore, x = 0 which implies that (λ + 1)a ≡ by (mod (λ + 1) 2 ). (9)

Similarly, there exists an x ∈ [0, λ] such that (λ + 1)b ≡ ax (mod (λ + 1) 2 ). ( 10) By ( 9) and (10) we have axy ≡ b(λ + 1)y ≡ a(λ + 1) 2 ≡ 0 (mod (λ + 1) 2 ) which implies that (λ + 1) 2 gcd(a, (λ + 1) 2 )

| xy.

In the same way, we have which leads to a contradiction. Similarly, y = 0 also leads to a contradiction. As a consequence, for q = (λ + 1) 2 , C[λ](q) sets of size 2 do not exist. Therefore, we must have q ≥ (λ + 1) 2 + 1. For q = (λ + 1) 2 + 1, it is easy to see that {1, λ + 1} is a C[λ](q) set:

{x • 1 | 1 ≤ |x| ≤ λ} ∪ {x • (λ + 1) | 1 ≤ |x| ≤ λ} = [1, λ] ∪ [λ 2 + λ + 2, λ 2 + 2λ + 1]
∪ {λ + 1, 2λ + 2, . . . , λ 2 + λ} ∪ {λ + 2, 2λ + 3, . . . , λ 2 + λ + 1}.

⊓ ⊔

For

  integers a, b, where a ≤ b, we let [a, b] = {a, a + 1, a + 2, . . . , b}.

For λ ≥ 2 Theorem 3 .

 23 , let Π λ = {p | p is a prime and p ≤ λ}, If µ = νP λ + 1 or µ = νP λ -1, and q = (2λ + 1)µ, then the set

Lemma 1 .

 1 (i) For odd d = p e1 1 p e2 2• • • p es s , with p i distinct odd primes, we have ord d (2) = lcm(ord p e 1 1 (2), ord p e 2 2 (2), • • • , ord p es s (2)). In particular, v 2 (ord d (2)) = i if and only if max 1≤j≤s v 2 (ord p e j j (2)) = i.

(λ + 1

 1 ) 2 gcd(b, (λ + 1) 2 ) | xy. From (8) we conclude that (λ + 1) 2 | xy. Since x, y ∈ [0, λ], this implies that xy = 0. Hence x = 0 or y = 0. If x = 0, then from (10) we obtain (λ + 1)|b. Therefore λ • b ≡ (-1) • b (mod (λ + 1) 2 )

  we must have p ≡ 7 (mod 8). In particular, C[3](3p) sets exist for the primes p = 7, 23, 31, 47, 71, 79, 103, 127. • If λ = 4 we must have p ≡ 11 (mod 12). In particular, C[4](4p) sets exist for the primes p = 11, 23, 47, 59, 71, 83. • If λ = 5 we must have p ≡ 19, 23 (mod 24). In particular, C[5](5p) sets exist for the primes p = 19, 23, 43, 47, 67, 71.

Acknowledgement

This work is supported by the Norwegian Research Council under the grant 191104/V30. The research of Jinquan Luo is also supported by NSF of China under grant 60903036, NSF of Jiangsu Province under grant 2009182 and the open research fund of National Mobile Communications Research Laboratory, Southeast University (No. 2010D12).

We claim that the set T m {4c | c ∈ S m } is a C [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF](4m) set of size ⌊m/2⌋ + N 2 (m). First we have N 2 (4m) ≥ ⌊ m 2 ⌋ + N 2 (m). Next, let S be a C [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF](4m) set and c be an element of S such that c ≡ 2 (mod 4). Then there exists a unique d ∈ T m such that 2d ≡ c (mod 4m) or -2d ≡ c (mod 4m) (but not both). Replacing c by d, we get a new C [START_REF] Cassuto | Codes for asymmetric limited-magnitude errors with application to multi-level flash memories[END_REF](4m) set. Repeating this procedure, we can get a C[2](4m)-set S ′ without elements congruent to 2 modulo 4. It is easy to verify that the set

and the result follows.

⊓ ⊔

Combining Theorems 4, 5, and 6, we have a satisfactory answer on construction of maximal size C[2](q) sets for all q.

6

On quasi-perfect C[λ](λp) sets for primes p

An example of a construction of a quasi-perfect set is given by the following theorem.

Theorem 7. Let p ≡ 3 (mod 4) be a prime and a ≡ 1 (mod λ) be a positive integer. If

Proof. Suppose ra u ≡ sa v (mod λp)

for some r, s ∈ [-λ, λ], (r, s) = (0, 0) and u, v ∈ [0, (p -1)/2 -1]. Without loss of generality, we may assume that r ≥ s and r ≥ 0. From [START_REF] Stein | Factoring by subsets[END_REF] Case II: (r, s) = (λ, -λ). In this case we have a v-u ≡ -1 (mod p)


Irina Naydenova
email: irina@ii.uib.no

Generalized Bose-Lin Codes, a Class of Codes Detecting Asymmetric Errors of Limited Magnitude

Keywords: error detection, q-ary asymmetric channel, Generalized Bose-Lin codes, asymmetric

 this class was generalized and the Generalized Bose-Lin (GBL) codes were introduced. In this note, we describe a Generalized Bose-Lin codes of limited magnitude l. For these codes, the possible undetectable errors are characterized, the undetectable errors of minimum weight are determined and the number of undetectable errors of minimal weight is found.

Introduction

Bose and Lin introduced a class of binary systematic codes for detection of asymmetric errors. This class was generalized for any q and in [START_REF] Naydenova | Generalized Bose-Lin codes, a class of codes detecting asymmetric errors[END_REF] the Generalized Bose-Lin codes were presented. Using this generalization we consider Generalized Bose-Lin codes of limited magnitude. For these codes the transmission channel is asymmetric. The received word cannot contain a component larger than the transmitted one. Moreover, when the asymmetric error is of limited magnitude, say l, the value of the difference between a transmitted component and its received version is at most l. In this note we characterize the undetectable errors, find the minimum weight of undetectable errors and the number of undetectable errors of minimal weight. The considered codes are systematic, i.e., the information bits are separately identified from the check bits. It is shown how long should be the check sequence such that to have a maximum number of detected errors.

Notations and definitions

Let F = {0, 1, . . . , q -1}. In a q-ary asymmetric channel (which we denote by q-ASC), the symbols transmitted over the channel are symbols from F , and if a is transmitted only b ∈ {0, 1, . . . , a} can be received. In this note, we consider a special type of asymmetric errors in a q-ary channel, where the error magnitude (a -b) do not exceed a certain threshold l. So, if a is transmitted only b ∈ {a -l, . . . , a} can be received.

The following notations were introduced in [START_REF] Naydenova | Generalized Bose-Lin codes, a class of codes detecting asymmetric errors[END_REF], we repeat them for completeness. Let F k be the set of all sequences of length k with symbols from F . For x = (x 0 , x 1 , . . . , x k-1 ) ∈ F k , let

w(x) = k-1 i=0 x i , the weight of x, u(x) = k-1 i=0 (q -1 -x i ), the coweight of x.
Clearly, w(x) + u(x) = k(q -1).

For non-negative integers a and s, where a < q s , let

a s = (a s-1 , a s-2 , . . . , a 0 ) ∈ F s where a = s-1 i=0 a i q i , a i ∈ F,
that is, a s is essentially the q-ary expansion of a. Define

w(a) = w( a s ) = s-1 i=0 a i .
For two sequences x and y, y ⊆ x denotes that x covers y, that is, y i ≤ x i for all i.

For integers a and n, let [a] n denote the (least non-negative) residue of a modulo n.

For integers m ≥ 0 and n ≥ 0, let S(m, n) denote the number of sequences in F m of weight n. A discussion of expressions for and computation of S(m, n) is given in [START_REF] Naydenova | Generalized Bose-Lin codes, a class of codes detecting asymmetric errors[END_REF]. Here we will give the lemmas, which are used later in this note.

Generalized Bose-Lin codes

The Generalized Bose-Lin codes are systematic codes determined by four (integral) parameters, q ≥ 2 (symbol alphabet size), k (number of information symbols), r (number of check symbols), and ω where 0 ≤ ω ≤ r.

A codeword is a sequence in F k+r . It consists of an information sequence x with k information symbols concatenated by a check sequence c(x) with r check symbols. We use the notations ρ = r -ω, σ = S(ω, ⌊(q -1)ω/2⌋), where σ is the number of all sequences in F ω of weight ⌊(q -1)ω/2⌋ and let

{b ω,0 , b ω,1 , . . . , b ω,σ-1 },
be the listing of all these sequences. We denote by θ = q ρ , the number of sequences in F ρ . Finally, µ = σθ will be the number of all possible check sequences.

Let u = u(x), the coweight of x. The check sequence, which depends only on u modulo µ, that is, the integer [u] µ , is determined as

[u] µ = αθ + [u] θ where 0 ≤ [u] θ < θ and 0 ≤ α < σ. The check sequence is defined by c(x) = c 1 (x)|c 2 (x) where | denotes concatenation, c 1 (x) = b ω,α
(a sequence of length ω and weight ⌊(q -1)ω/2⌋), and

c 2 (x) = [u] θ ρ
(the q-ary expansion of the residue of u modulo θ).

In [START_REF] Naydenova | Generalized Bose-Lin codes, a class of codes detecting asymmetric errors[END_REF], the following results are proven.

Theorem 1. Let C be the GBL-code with parameters q, k, r, ω. A codeword x|c(x) ∈ C can be transformed to the codeword y|c(y) = x|c(x) by transmission over a complete q-ASC if and only if

y ⊂ x and λ ρ ⊆ [u(x)] θ ρ , where λ = [u(x) -u(y)] µ .
Theorem 2. Let C be the GBL-code with parameters q, k, r, ω, and assume that the transmission is over a complete q-ASC. The code C detects all errors of weight up to (σ -1)θ + (q -1)ρ, but there are undetectable errors of weight (σ -1)θ + (q -1)ρ + 1.

Generalized Bose-Lin Codes of Limited Magnitude

Generalized Bose-Lin codes of limited magnitude l are systematic. First we will characterize the possible undetectable errors and then we will determine the minimum weight of the undetectable errors for these codes. The number of the undetectable errors of the minimal weight is found too. We will consider the check sequence such that to have maximum number of detected errors. The first result is.

Theorem 3. Let C be the GBL-code of limited magnitude l with parameters q, k, r and ω. A codeword x|c(x) ∈ C can be transformed to the codeword y|c(y) = x|c(x) by transmission over a q-ASC if and only if

x -l ⊆ y ⊂ x and λ ρ ⊆ L ρ ,
where l = (l, l, ..., l) of length k, λ = [u(x) -u(y)] µ and L = l(θ -1)/(q -1).

Proof: The sent codeword is x|c 1 (x)|c 2 (x) and the received codeword is y|c 1 (y)|c 2 (y), where x = y. According to the construction of GBL codes, we see that this is possible if and only if

xl ⊆ y ⊂ x, where l = (l, l, ..., l) of length k,

c 1 (y) = c 1 (x), since w(c 1 (y)) = w(c 1 (x)) = ⌊(q -1)ω/2⌋ (1)
and

c 2 (x) -L ρ ⊆ c 2 (y) ⊆ c 2 (x). (3)
Further, by definition, c 2 (x) is the q-ary expansion of u(x) modulo θ and c 2 (y) is the q-ary expansion of u(y) modulo θ. Also, we note that if y ⊂ x, then u(y) > u(x). Hence, suppose that (1), (2), and (3) are satisfied, and let

u = u(x) and jµ -λ = u(y) -u(x), where 0 ≤ λ < µ and 1 ≤ j ≤ ⌊ kl µ ⌋, since 0 ≤ u(y) -u(x) ≤ kl. Note that λ = [u(x) -u(y)] µ . Let [u] µ = αθ + [u] θ and [u + jµ -λ] µ = βθ + [u + jµ -λ] θ . Since [u + (jµ -λ)] µ = [u -λ] µ and [u + (jµ -λ)] θ = [u -λ] θ ,
we get from the definition of the code that

c 1 (x) = b ω,α c 2 (x) = [u] θ ρ , c 1 (y) = b ω,β c 2 (y) = [u -λ] θ ρ .
Hence, (2) is satisfied if and only if b ω,α = b ω,β , that is, if and only if

β = α,

and (3) is satisfied if and only if

[u] θ -L ρ ⊆ [u -λ] θ ρ ⊆ [u] θ ρ . [u -λ] θ ρ ⊆ [u] θ ρ
was considered in more details in [START_REF] Naydenova | Generalized Bose-Lin codes, a class of codes detecting asymmetric errors[END_REF] and it was shown that we must have λ < θ and in particular, we must have λ ≤

[u] θ . Now we consider [u] θ -L ρ ⊆ [u -λ] θ ρ . Using the conclusions above we have [u] θ -L ρ ⊆ [u -λ] θ ρ is equivalent to [u] θ ρ -L ρ ⊆ [u] θ ρ -λ ρ , which is λ ρ ⊆ L ρ . Since L ρ ⊆ [u] θ ρ , λ ρ ⊆ L ρ is
stronger condition and this completes the proof of the theorem.

Our next result is.

Theorem 4. Let C be the GBL-code of limited magnitude l with parameters q, k, r and ω and assume that the transmission is over a q-ASC. The code C detects all errors of weight up to

µ -l θ -1 q -1 + lρ -1
but there are undetectable errors of weight

µ -l θ -1 q -1 + lρ.
Proof: The weight of the undetectable error is

w(x|c(x)) -w(y|c(y)) = w(x) -w(y) + w(c 2 (x)) -w(c 2 (y)) = w(x) -w(y) + w( [u] θ ρ ) -w( [u -λ)] θ ρ ) = u(y) -u(x) + w( [u] θ ρ ) -w( [u -λ)] θ ρ ) = jµ -λ + w( λ ρ ) = jµ -λ + w(λ).
Suppose that

λ = ρ-1 i=0 a i q i , and λ ′ = ρ-1 i=0 a ′ i q i , where a i , a ′ i ∈ F and λ ρ ⊆ λ ′ ρ , that is, a i ≤ a ′ i for all i. Then (λ ′ -w(λ ′ )) -(λ -w(λ)) = ρ-1 i=0 (a ′ i -a i )(q i -1) ≥ 0. (4)
We note that L ρ = (l, l, . . . , l). Hence w( L ρ ) = lρ. By (4), if also λ ρ ⊆ L ρ , then

λ -w(λ) ≤ L -lρ = l (θ -1) q -1 -lρ.
Therefore, the weight of an undetectable error is lower bounded as follows:

jµ -(λ -w(λ)) ≥ µ -l θ -1 q -1 + lρ,
which proves the theorem. Next, we will determine the exact number of undetectable errors of minimal weight.

Theorem 5. For a GBL-code of limited magnitude l with parameters q, k, r and ω the number of all undetectable errors of minimal weight µ -l θ -

1 q -1 + lρ is t≥0 q-1-l δ=0 S(k, k(q -1) -tθ -L -δ) l ǫ=0 S(k, µ -L + ǫ)S(ρ, lρ -ǫ) .
are changed to (0, 0, ..., 0, δ + ǫ)

and the weight of the error sequence to the information part is µ-L+ǫ, 0 ≤ ǫ ≤ l.

A natural question is: given q, l and r, which value of ω maximizes A(q, l, r, ω) = µ -l θ -1 q -1 + lρ -1.

For q = 2 and l = q -1 it was shown by a simple proof in [START_REF] Kløve | The probability of undetected error for a class of asymmetric error detecting codes[END_REF] that the maximum is obtained for ω = 4 when r ≥ 5.

For q ≥ 3 the maximum is obtained for ω = 2. The result it stated in the following theorem. Theorem 6. Let q ≥ 3. We have A(q, l, r, 2) > A(q, l, r, 1) for r ≥ 3. For ω ≥ 3 we have A(q, l, r, ω -1) > A(q, l, r, ω) for r ≥ ω.

Proof: When ω = 1 we have

A(q, l, r, 1) = q r-1 1 - l q -1 + (r -1)l + l q -1 - 1
and when ω = 2, then

A(q, l, r, 2) = q r-2 q - l q -1 + (r -2)l + l q -1 - 1
Then A(q, l, r, 2) -A(q, l, r, 1) = q r-2 l -l ≥ 0, for r ≥ 2.

So, A(q, l, r, 2) > A(q, l, r, 1) for r ≥ 3. Next, we want to prove that:

A(q, l, r, ω -1) > A(q, l, r, ω),

for ω ≥ 3 ⇔ S ω -1, (q -1)(ω -1) 2 - l q -1 q r-(ω-1) + l(r -(ω -1)) + l q -1 -1 > S ω, (q -1)ω 2 - l q -1 q r-ω + l(r -ω) + l q -1 -1 ⇔ ⇔ q S ω -1, (q -1)(ω -1) 2 - l q -1 > S ω, (q -1)ω 2 - l q -1 .
We will prove the last inequality. In the Appendix in [START_REF] Naydenova | Generalized Bose-Lin codes, a class of codes detecting asymmetric errors[END_REF] the following Lemma is proven Lemma 1.

S(0, 0) = 1 and S(0, n) = 0 for n > 0.

Further, for m ≥ 1 we have

S(m, n) = q-1 j=0 S(m -1, n -j).
Using it, it follows that:

S ω, (q -1)ω 2 =

q-1 j=0

S ω -1, (q -1)ω 2 -j = S ω -1, (q -1)ω 2 + ............................................ + S ω -1, (q -1)ω 2 -(q -1) .

Another lemma from the Appendix in [START_REF] Naydenova | Generalized Bose-Lin codes, a class of codes detecting asymmetric errors[END_REF] says:

Lemma 2. If m ≥ 2 and 0 ≤ n 1 < n 2 ≤ (q -1)m/2, then S(m, n 1 ) < S(m, n 2 ).

Using it, for m = ω -1 ≥ 2 (which is ω ≥ 3), we have that for ⌊ q-1 2 ⌋ < j ≤ q -1, S ω -1, (q -1)ω 2 -j < S ω -1, (q -1)ω 2 -q -1 2 = S ω -1, (q -1)(ω -1) 2 , since:

If (q -1) is even we have (q -1)ω 2 -q -1 2 = (q -1)(ω -1) 2 = (q -1)(ω -1) 2 .

If (q -1) is odd and ω is odd, then (q -1)(ω -1) 2 = (q -1)ω -1 2 -q -2 2 = (q -1)ω 2 -q -1 2 .

If (q -1) is odd and ω is even, then (q -1)(ω -1) 2 = (q -1)(ω -1) -1 2 = (q -1)ω 2 -q -2 2 = (q -1)ω 2 -q -1 2 .

The function S(m, n) has symmetry, stated in [START_REF] Naydenova | Generalized Bose-Lin codes, a class of codes detecting asymmetric errors[END_REF], which is.

Proof: The weight of the undetectable error is w(x|c(x)) -w(y|c(y)) = jµ -λ + w(λ),

We have that

Consider the undetectable error of minimal weight we should have equality in both places. So, we have undetectable error of minimal weight in the cases when

We note that [u] θ = L + δ if and only if u = tθ + L + δ for some t ≥ 0, since L + δ < θ.

We have to find the number of sequences which have co-weight exactly u = tθ + L + δ, which is equivalent to have weight exactly k(q -1) -u = k(q -1) -tθ -L -δ. All these sequences have the same length k. So, the number is

For every such sequence we have undetectable error of minimal weight µ -L + lρ. From the definition of λ and using that j = 1 we have that u(y) -u(x) = µ-L+ǫ. So, the weight of the error sequence to the information part is µ-L+ǫ. Then, the weight of the error sequence of the last ρ bits will be lρ -ǫ. Hence, the number of all error sequences is S(k, µ -L + ǫ)S(ρ, lρ -ǫ), for 0 ≤ ǫ ≤ l.

The number of undetectable errors of minimal weight when u = tθ + L + δ is therefore

Then summing over all t ≥ 0 we receive that the number of undetectable errors of minimal weight for GBL codes of a limited magnitude l is

Undetectable errors of minimal weight occur exactly for codewords of coweight tθ + L + δ, 0 ≤ δ ≤ q -1 -l. For these codewords, an error is undetectable if the last ρ symbols of the check part, namely (l, l, ..., l, l + δ)

For 0 ≤ j < ⌊ q-1 2 ⌋ we have:

From Lemma 2 and for 0

, since:

If (q -1) is odd and ω is even, then

If (q -1) is odd and ω is odd, then

So, we have

We use the fact that l < q -1, so qS ω -1, (q -1)(ω -1) 2 -(q -1) < qS ω -1, (q -1)(ω -1) 2 -l ⇒ q S ω -1, (q -1)(ω -1) 2 -l q -1 > S ω, (q -1)ω 2 -l q -1 .

Therefore, A(q, l, r, ω), which is the number of detected errors, receives its maximum when ω = 2, for q ≥ 3. This result is valid also when l = q -1.


Lars Eirik Danielsen
email: larsed@ii.uib.no

Matthew G Parker
email: matthew@ii.uib.no

The selfnegadual properties of generalised quadratic Boolean functions

Keywords: Generalised Boolean functions, selfnegadual functions, negabent functions, bent functions, negaHadamard transform, Walsh Hadamard transform, Fourier eigenspectra, selfdual codes, quantum codes

We define and characterise selfnegadual generalised quadratic Boolean functions by establishing a link, both to the multiplicative order of symmetric binary matrices, and also to the Hermitian self-dual F4-linear codes. This facilitates a novel way to classify Hermitian selfdual F4-linear codes.

Introduction

In this paper an n-variable generalised quadratic Boolean function refers to a function in ZRM(2, n) (the quaternary Reed-Muller code). To be explicit, if f : F n 2 → Z 4 is of the form:

f (x) = 2( j<k a jk x j x k ) + 2( j b j x j + c) + j a jj x j + d (1)
where a jk , a jj , b j , c, d ∈ F 2 , then it is a function in ZRM (2, n). We consider f and its phase representation, i f , where i 2 = -1, and i f = (i f (k) ), k ∈ F n 2 , is interpreted as a column vector of 2 n elements. When a jj = d = 0, ∀j, then f is a quadratic Boolean function. We consider a map from f to an n × n binary symmetric matrix, A f = (a ij ), where the off-diagonal part refers to Boolean quadratic terms, the diagonal part refers to Z 4 -linear terms, and the binary linear coefficients, b i , together with the constant term, c, is called the binary affine offset, and is ignored for the map to a matrix. To simplify notation, and without loss of generality, we assume, throughout this paper, that c = d = 0.

Recent papers [START_REF] Carlet | Self-dual bent functions[END_REF][START_REF] Danielsen | The Rayleigh quotient of bent functions[END_REF] have classified and constructed Boolean functions that are selfdual, i.e. their phase representations are eigenvectors of the Walsh-Hadamard transform -such functions are therefore bent. Another direction is to classify and construct Boolean functions that are negabent or bent-negabent (both bent and negabent) [START_REF] Parker | On Boolean functions which are bent and negabent[END_REF][START_REF] Schmidt | Negabent Functions in the Maiorana-McFarland Class. Sequences and Their Applications -SETA[END_REF]. We show that a function in ZRM(2, n) can never be both selfdual and negabent. Let a function be called selfnegadual if its phase representation is an eigenvector of the negaHadamard transform -such functions are therefore negabent and it turns out that they are also bent. We show that there are no quadratic selfnegadual Boolean functions, but that there are selfnegadual functions in ZRM (2, n). So, in this paper, we answer the following question:

Question 1. Which functions in ZRM(2, n) are selfnegadual?
The main result of this paper is to characterise those functions in ZRM(2, n) that are selfnegadual.

We came at this problem from an unusual direction. Our initial question was in the context of the study of multiplicative orders of symmetric binary matrices. Let A be such a matrix, and let it have order p if A p = I, the identity, and A j = I, for 1 ≤ j < p. We say that ord(A) = p, where A can only have an [START_REF] Parker | On Boolean functions which are bent and negabent[END_REF]. However, if ord(A f ) = 2 then A f + I cannot have maximum rank. This motivates the question: Question 2. For which n×n symmetric binary matrices, A, is ord(A) and ord(A + I) jointly minimised to 3?

order if A has maximum rank. If f ∈ ZRM(2, n) is selfdual, then ord(A f ) = 2 [4]. If f is negabent then A f + I has maximum rank
An n × n symmetric binary matrix, A, represents an n-vertex undirected graph with possible loops. For ω primitive in F 4 , the rowspace of matrix A + wI is a Hermitian selfdual F 4 -additive code of blocklength n. The graphical interpretation has been used to aid in classifying all selfdual F 4 -additive codes up to blocklength 12 [START_REF] Danielsen | On the classification of all self-dual additive codes over GF(4) of length up to 12[END_REF]. A small subset of these matrices, A + ωI, generate selfdual F 4 -additive codes that are also selfdual F 4 -linear of blocklength n -all selfdual F 4 -linear codes can be represented in this way. So we have the question: Question 3. For which n × n symmetric binary matrices, A, is the F 4 -additive code generated by A + wI also F 4 -linear? Question 3 has been characterised by Van den Nest [START_REF] Van Den Nest | Local Equivalence of Stabilizer States and Codes[END_REF]. Our contribution is to show that questions 2 and 3 are the same question, and also the same as question 1 to within a binary affine offset.

In section 2 we characterise dualities of functions with respect to Walsh-Hadamard and negaHadamard transforms. In section 3 we look at orders of symmetric binary matrices, show how they relate to dualities of a function, and show that order is preserved by action of the orthogonal group. In section 4 we show how selfduality and selfnegaduality relate to linear selfdual codes over F 2 and F 4 , respectively, and also, by interpreting the symmetric matrix as an undirected graph, show how a modified form of local complementation [START_REF] Bouchet | Graphic presentations of isotropic systems[END_REF] on the graph preserves selfnegaduality. In section 5 we use graphical interpretation, and orthogonal equivalence, to classify all Hermitian selfdual F 4 -linear codes up to n = 18.

Bentness and selfdualities of functions -definitions

Let f : F n 2 → Z 4 be in ZRM(2, n). Let H = 1 √ 2 1 1 1 -1
be the 2 × 2 Hadamard matrix, and let

N = 1 √ 2 1 i
1 -i , i 2 = -1, be the 2 × 2 negaHadamard matrix. Let '⊗' indicate the tensor product of matrices. We summarise, in table 1, the dualities that we discuss in this paper, where s, r, r ′ ∈ F n 2 , and w(x) is the Hamming weight of x. For brevity, except in the case of selfdual and selfnegadual, we do not make explicit the global multiplicative constants or eigenvalues in these expressions, using symbols α and α ′ to indicate arbitrary constants that need only satisfy |α| = |α ′ | = 1. In [START_REF] Carlet | Self-dual bent functions[END_REF] the cases of α = 1 and α = -1 were used to distinguish between selfdual and anti-selfdual, respectively, but we refer, here to the union of these two simply as selfdual. For selfnegadual, observe that N 3 = e πi/4 I. For some eigenvalue, α, and eigenvector, v, of N ⊗n , we have (2, n) and selfnegadual restricts α to the alphabet {e hiπ/4 }, for some integer, h. Theorem 2 and lemma 11 will show that, for such an f , then n must be even. It then follows, uniquely, that α = e -niπ/4 .

N ⊗n v = αv. Therefore (N ⊗n ) 3 v = α 3 v = e nπi/4 v. Therefore α ∈ {e (n+8k)πi/12 , k = 0, 1, 2}. Choosing f from ZRM
Table 1. Spectral dualities Property of f ∈ ZRM(2, n) equation satisfied by f bent i f = αH ⊗n i f negabent i f = αN ⊗n i f selfdual i f = ±H ⊗n i f selfnegadual i f = e -niπ/4 N ⊗n i f P-dual i f (x) = αH ⊗n i f (x+s)+r•x = α ′ H ⊗n i f (x)+r ′ •x P-negadual i f (x) = αN ⊗n i f (x+s)+r•x = α ′ N ⊗n i f (x)+r ′ •x
If f is bent then its dual, f , is also bent. But if f is negabent, then its dual, f , is only negabent if f is also bent. A selfdual function is bent and a selfnegadual function is bent-negabent, where bentness of the selfnegadual function follows because

H ⊗n i f (x) = e niπ/4 H ⊗n N ⊗n i f (x) = e niπ/4 i f (x)+ P j xj .
Selfdual and selfnegadual are special cases of P-dual and P-negadual, respectively. If f -f or f -f are binary affine then f is P-dual or P-negadual, respectively.

Matrix orders and function dualities

We wish to characterise the n × n binary symmetric matrices, A, such that both ord(A) and ord(A + I) are as small as possible. We call A a (p, q)-matrix if A has order p and A + I has order q, where p or q equals '-' if A or A + I, respectively, does not have maximum rank. Trivially, if ord(A) = 1, then A = I and A + I cannot have maximum rank, in which case A is a (1, -)-matrix. Likewise, if ord(A) = 2 then A + I cannot have maximum rank, as (A + I) 2 = A 2 + I = 0, in which case A is a (2, -)-matrix. So our first candidate of interest is for A to be a (3, 3)-matrix and, indeed, such symmetric binary matrices do exist. After some preliminary lemmas, we present, by considering the conditions on f ∈ ZRM(2, n) for selfduality and selfnegaduality, two theorems for (2, -) matrices (theorem 1), and (3, 3) matrices (theorem 2), respectively.

Let X = 0 1 1 0 and Z = 1 0 0 -1 .
The following lemma is easily verified.

Lemma 1. HX = ZH, HZ = XH, N X = iZXN, N Z = XN.
For r ∈ F n 2 , U a 2 × 2 matrix, U 0 = I, the identity, and U 1 = U , let U r = 0≤j<n U rj , be a 2 n × 2 n matrix constructed using the tensor product.

Lemma 2. For f bent,

H ⊗n i f (x+r) = αi f (x)+2r•x .

Proof. By lemma 1 and table 1,

H ⊗n i f (x+r) = H ⊗n X r i f (x) = Z r H ⊗n i f (x) = αZ r i f (x) = αi f (x)+2r•x .
Lemma 3. For f negabent,

N ⊗n i f (x+r) = αi f (x+r)+2r•x+w(r) ,
and

N ⊗n i f (x)+2r•x = αi f (x+r) .
Proof. By lemma 1 and table 1,

N ⊗n i f (x+r) = N ⊗n X r i f (x) = i w(r) Z r X r N ⊗n i f (x) = αZ r X r i f (x)+w(r) = αi f (x+r)+2r•x+w(r) .
For the second part,

N ⊗n i f (x)+2r•x = N ⊗n Z r i f (x) = X r N ⊗n i f (x) = αX r i f (x) = αi f (x+r) .
Lemma 4. For f ∈ ZRM(2, n), and for any r ∈ F n 2 , r = 0,

f (x + r) = f (x) + 2A f r • x + f (r).
Proof. To within a constant, f (x) = 2q(x) + 2b • x + l • x, where q is a homogeneous quadratic, and b, l ∈ F n 2 . Then 2q(x + r) = 2(q(x) + A q r • x + q(r)),

2b • (x + r) = 2b • x + 2b • r, and l • (x + r) = l • x + 2l • r • x + l • r. Therefore f (x + r) = 2q(x + r) + 2b • (x + r) + l • (x + r) = (2q(x) + 2b • x + l • x) + 2(A q r + l • r) • x + (2q(r) + 2b • r + l • r). Observe that A f r = A q r + l • r. Theorem 1. If f is selfdual or anti-selfdual then A f is a (2, -)-matrix, and f (r) = -f (A f r), ∀r ∈ F n 2 , r = 0. Conversely, if A f is a (2, -)-matrix, then A f = A f , i.e. f is P-dual, and f (r) = -f (A f r), ∀r ∈ F n 2 , r = 0.
Proof. Using table 1, lemmas 2 and 4,

H ⊗n i f (x+r) = H ⊗n i f (x)+2A f r•x+f (r) = αi f (x)+2r•x .
Similarly,

H ⊗n i f (x+A f r) = H ⊗n i f (x)+2A 2 f r•x+f (A f r) = αi f (x)+2A f r•x .
Then, as H ⊗n is self-inverse,

αi f (x)+2r•x-f (r) = αi f (x)+2A 2 f r•x+f (A f r) ,
from which A 2 f = I and f (r) = -f (A f r). For the converse, we have that

H ⊗n i f (x+r) = H ⊗n i f (x)+2A f r•x+f (r) = αi f (x)+2r•x ,
and

H ⊗n i f (x+A f r) = H ⊗n i f (x)+2A f A f r•x+ f (A f r) = αi f (x)+2A f r•x .
Combining gives

i f (x)+2r•x-f (r) = i f (x)+2A f A f r•x+ f (A f r) . Theorem 2. If f is selfnegadual then A f is a (3, 3)-matrix, and f (A f r) = w(r), ∀r ∈ F n 2 , r = 0. Conversely, if A f is a (3, 3)-matrix then A f = A f , f is P- negadual, and f (A f r) = f (r) -f (r) + w(r), ∀r ∈ F n 2 , r = 0.
Proof. Using table 1, lemmas 3 and 4,

N ⊗n i f (x)+2A f r•x = αi f (x+A f r) = αi f (x)+2A 2 f r•x+f (A f r) ,
Remark: The result of lemma 7 can also be deduced from the thesis of Van den Nest [START_REF] Van Den Nest | Local Equivalence of Stabilizer States and Codes[END_REF], in the context of F 4 -additive and F 4 -linear codes.

We identify an action which preserves the (p, q) property of a matrix. An orthogonal matrix, U , satisfies U U T = I. The set of n × n binary orthogonal matrices forms a group, O n , under multiplication. Lemma 8. For A a symmetric n × n matrix, and U ∈ O n , then U AU T is a (p, q)-matrix iff A is a (p, q)-matrix.

Proof. We have that (U AU T ) p = U A p U T = I. For 0 < j < p, we need to show that U A j U T = I. But if U A j U T = I then U A j is the matrix inverse of U T , and there is only one inverse of U T , namely U , so U j = I and U A j U T = I. The same argument holds if we replace A by A + I, and p by q. Moreover, if A f or A f + I are not of maximum rank, then neither are their orthogonal transformations, so non-order is also preserved by the action of O n .

Corollary 1. (of lemma 8) For U ∈ O n and f (x) ∈ ZRM(2, n), and by theorems 1 and 2, if f (x) is selfdual then so is f (U x) and, if f (x) is selfnegadual then so is f (U x).

Graphs and code dualities

Let A be an n × n symmetric binary matrix. Then A can be used to generate codes, and can also be interpreted as an adjacency matrix for an undirected graph, where the graph of A has loops if its diagonal is non-zero. The next lemma is well-known. Lemma 9. If A has zero diagonal, and if A 2 = I then the linear space generated by the rows of A+I is a self-orthogonal binary linear code of dimension rank(A+ I). In particular, if A is the adjacency matrix for a bipartite graph with equal-size partitions, then A + I generates a selfdual binary linear code.

Proof. The rows of A are pairwise orthogonal as A 2 = I. Therefore the rows of A + I are pairwise orthogonal as A is symmetric. The linear space generated by A + I is self-orthogonal because (A + I)(A + I) T = 0. For the last part, A = 0 P P T 0 , P square, so A + I spans a self-dual code. An additive code over

F 4 = {0, 1, ω, ω = ω + 1} of length n is a F 2 -linear subgroup of F n 4 .
We define the dual of the code C with respect to the trace inner product as

C ⊥ = {u ∈ F n 4 | n i=1 (u i c i + u i c i ) = 0
for all c ∈ C}, and say that it is selfdual if C = C ⊥ . A linear code over F 4 which is selfdual with respect to the Hermitian inner product, i.e., u • v, is also selfdual additive with respect to the trace inner product. However, most selfdual additive codes are not F 4linear. Two selfdual additive codes over F 4 are equivalent if we can obtain one from the other by permuting, scaling, and conjugating coordinates. Equivalence of selfdual linear codes is defined similarly, with the exception that conjugating single coordinates is not permitted.

It is known [START_REF] Van Den Nest | Local Equivalence of Stabilizer States and Codes[END_REF] that any selfdual additive code has a standard form n × n generator matrix of the form A + ωI, where I is the identity matrix and A is a binary symmetric matrix. It is also known [START_REF] Van Den Nest | Local Equivalence of Stabilizer States and Codes[END_REF] that two codes are equivalent iff the corresponding graphs are related via local complementation (LC) [START_REF] Bouchet | Graphic presentations of isotropic systems[END_REF]. Given a generator matrix of standard form, conjugating a coordinate is equivalent to complementing a diagonal element in A. Hence, for selfdual additive codes considered up to equivalence, this diagonal can always be set to zero. For selfdual linear codes (represented by overdefined n × n generator matrices), the diagonal is of importance and can in fact never be zero. Lemma 10. [START_REF] Van Den Nest | Local Equivalence of Stabilizer States and Codes[END_REF] For A and B symmetric, a Hermitian selfdual F 4 -additive code, generated by

A + ωB, is F 4 -linear iff AA T + BB T + AB T = 0. Moreover, if B = I, this condition reduces to A 2 + A + I = 0. Corollary 2. A + ωI is the codespace of a Hermitian selfdual F 4 -linear code iff A is a (3, 3) matrix.
Proof. Follows from lemma 10 as the condition A 2 + A + I = 0 immediately implies that both A and A + I have order 3.

Let G A be the n-vertex graph of A with an edge between i and j iff a ij = 1, and a loop at vertex j iff a jj = 1. Lemma 11. If A is a (3, 3) matrix, then all vertices of G A have odd degree, disregarding loops. In such a case, n, the number of vertices, must be even.

Proof. Since A is a (3, 3) function, A 2 = A + I. Hence the diagonal entries in A 2 must be the complements of the diagonal entries of A. This criterion is satisfied iff there is an odd number of 1s among the off-diagonal entries in each row of A. The number of edges of a graph equals the sum of the vertex degrees divided by 2. But, if all vertex degrees are odd, then n must be even. Remark: It is also a well-known fact that all codewords of selfdual F 4 -linear codes have even weight, which amounts to the same thing.

It is known [START_REF] Danielsen | On the classification of all self-dual additive codes over GF(4) of length up to 12[END_REF] that local complementation (LC) acting on G A , where loops are ignored, preserves, to within equivalence, the F 4 additive selfdual code generated by A + ωI. However, for those additive codes that are also linear codes, one has to modify local complementation to take account of loops, so that the additive code remains linear after local complementation. We first describe this modified form of local complementation (LC*) and then prove that it preserves linearity of the F 4 codespace. Let N j ⊂ {0, 1, . . . , n -1} be the set of vertices that are neighbours to vertex j in G A (not including j itself). Let LC* at vertex j of G A produce the graph G A ′ .

Modified local complementation (LC*):

LC* on G A at vertex j is realised by

a ′ ik = a ′ ki = a ik + 1 i, k ∈ N j , a ′ ik = a ′ ki = a ik otherwise. a ′ ii = a ii + 1 i ∈ j N j , a ′ ii = a ii otherwise.
Lemma 12. Let G A ′ be the graph resulting from LC* on G A at some vertex. If A is a (3, 3)-matrix, then A ′ is also a (3, 3)-matrix.

Proof. Let LC* act on G A at vertex j. Let D = (d ik ) and V = (v ik ) be n × n binary matrices such that d jj = 1 and d ik = 0 otherwise, and v ik = 1, ∀i, k ∈ N j , i = k, and v ik = 0 otherwise. Then, by the LC* rule, one can see that The modified local complementation proposed in [START_REF] Brijder | Pivot and Loop Complementation on Graphs and Set Systems[END_REF] differs crucially from ours -when doing a local complementation at vertex j, they do not flip the diagonal at j, whereas we do.

A ′ = A + D + V . A ′ is a (3, 3)-matrix iff A ′2 = A ′ + I. But A ′2 = (A + D + V ) 2 = (A 2 + D 2 + V 2 ) + (AD + DA) + (AV + V A) + (DV + V D). But A 2 = A + I as A is a (3, 3

Code classification

Selfdual linear codes over F 4 have been classified up to length 16 [START_REF] Conway | Self-dual codes over GF(3) and GF(4) of length not exceeding 16[END_REF][START_REF] Macwilliams | Self-dual codes over GF(4)[END_REF]. As a consequence of lemma 10 and corollary 2, we can use the correspondence to [START_REF] Brijder | Pivot and Loop Complementation on Graphs and Set Systems[END_REF][START_REF] Brijder | Pivot and Loop Complementation on Graphs and Set Systems[END_REF] matrices to devise a new algorithm and classify codes of length 18. During the process of extending the result to length 20, we became aware that codes of length 18 and 20 have already been classified independently in two preprints recently made available online [START_REF] Harada | Classification of generalized Hadamard matrices H(6,3) and quaternary Hermitian self-dual codes of length 18[END_REF][START_REF] Harada | Classification of quaternary Hermitian self-dual codes of length 20[END_REF]. However, we still give an overview of our approach, since it gives different theoretical insights and highlights the connection between selfdual codes and selfnegadual Boolean functions. By our classification, we verify this conjecture numerically for n ≤ 18. Also note that it has been shown by Janusz [START_REF] Janusz | Parametrization of self-dual codes by orthogonal matrices[END_REF] that all selfdual binary codes of length n are equivalent under the action of O n . It is known [START_REF] Janusz | Parametrization of self-dual codes by orthogonal matrices[END_REF] that O n is generated by all matrices of the form P M , where P is a permutation matrix and M = In-4 0 0 I4+J4 , where J 4 is the 4 × 4 all-one matrix. As a canonical representative for selfdual F 4 -linear codes of length 2n, we choose the matrix C = ( 0 1 1 1 ) ⊗ I n . Starting from C, we then apply orthogonal transforms until one representative from each equivalence class has been found. (Which is verified by checking the mass formula [START_REF] Macwilliams | Self-dual codes over GF(4)[END_REF].) In practice, we achieve this by generating C ′ = (P M )C(P M ) T for all the n 4 non-trivial permutations P . C ′ is then treated as a graph with loops and checked for isomorphism against all previously seen graphs. If C ′ is new, the corresponding code is output, and the complete LC*-orbit of C ′ , using modified local complementation, is generated and stored. (This is not strictly necessary, but speeds up the algorithm, since LC*-operations are faster than orthogonal transforms.) We proceed recursively, generating matrices (P M )C ′ (P M ) T , and so on, until all codes are found. With this algorithm, classifying all codes of length n ≤ 18 was achieved in about two hours of CPU time on a standard desktop computer.

  )-matrix. Moreover it is easily verified that D 2 = D. Using lemma 11, V 2 = V , and AD + DA = AV + V A. D and V are row/column disjoint, so DV + V D = 0. Therefore, A ′2 = A + I + D + V = A ′ + I, as required.

Conjecture 1 .

 1 Given two n × n (3,3) matrices A and A ′ , there always exists an orthogonal matrix U ∈ O n such that A ′ = U AU T .

Table 2 .

 2 Number of selfdual linear codes over F4 of length n[START_REF] Conway | Self-dual codes over GF(3) and GF(4) of length not exceeding 16[END_REF][START_REF] Harada | Classification of generalized Hadamard matrices H(6,3) and quaternary Hermitian self-dual codes of length 18[END_REF][START_REF] Harada | Classification of quaternary Hermitian self-dual codes of length 20[END_REF][START_REF] Macwilliams | Self-dual codes over GF(4)[END_REF]

and N ⊗n i f (x+r) = αi f (x+r)+2r•x+w(r) = αi f (x)+2(A f +I)r•x+f (r)+w (r) .

But, by lemma 4, we can equate these equations and the first part of the theorem follows. For the second part we obtain, in a similar fashion,

The argument is completed by constraining ord(A f ) = 3, and A f + I to be of maximum rank, in which case A f is a (3, 3) matrix and A 2 f + A f + I = 0. Before continuing, we summarise function dualities of f in terms of the associated orders of A f . property of:

Remarks: The condition in the proof of theorem 2 that A + I has maximum rank is important, as both (3, -) and (-, 3) matrices exist. For A of order 3, (A 3 + I) = (A 2 + A + I)(A + I), and the condition that (A + I) has maximum rank is equivalent to the condition that A 2 + A + I = 0. In the full paper we discuss the binary offsets, b in (1), required to make a P-dual or P-negadual function, f , selfdual or selfnegadual, respectively, for A f a (2, -) or (3, 3) matrix, respectively. For A f a given (2, -) matrix the set of valid b vectors is of size the binary eigenspace of A f but, for A f a given (3, 3) matrix, there is only one valid b vector, as follows from condition f (A f r) = w(r), ∀r = 0, in theorem 2.

Lemma 5. [START_REF] Albert | Symmetric and alternating matrices in an arbitrary field[END_REF][START_REF] Macwilliams | Orthogonal Matrices Over Finite Fields[END_REF] An invertible binary symmetric matrix can be factored in the form M M T iff it has at least one nonzero term on the main diagonal. . But, B is symmetric as A f is symmetric so A f = BB T which, by lemma 5, is impossible as A f has no ones on its diagonal. Lemma 7. There are no selfnegadual quadratic Boolean functions.

Proof. By theorem 2, A f has order 3 if f ∈ ZRM(2, n) is selfnegadual. Therefore, by lemma 6, f cannot be a quadratic Boolean function.


Wilfried Meidl
email: wmeidl@sabanciuniv.edu

Alev Topuzoglu

Quadratic functions with prescribed spectra

Keywords: Quadratic Boolean functions, s-plateaued functions, nearbent functions, self-reciprocal polynomials, linear complexity

We study quadratic Boolean functions f from F2n to F2, which are well-known to have plateaued Fourier spectrum F s,f , i.e., their Fourier coefficients are in the set {0, ±2 (n+s)/2 } for some integer 0 ≤ s ≤ n -1. For various types of integers n, we determine possible values of s, construct f with F s,f for a prescribed s, and present enumeration results in case n is a power of 2. Our work generalizes some of the earlier results of Khoo et. al. ([5]) on near-bent functions and provides a simple proof of a result of Fitzgerald ([2]) on degenerate quadratic forms.

Introduction

We study quadratic functions

f (x) = Tr n   ⌊(n-1)/2⌋ i=0 a i x 2 i +1   (1)
from F 2 n to F 2 , with coefficients in F 2 .

It is well known that any quadratic function is plateaued i.e., it has (plateaued) Fourier spectrum

F s,f
, in other words, its Fourier coefficients lie in {0, ±2 (n+s)/2 } for some integer 0 ≤ s ≤ n -1. In this case we call f s-plateaued. 1-plateaued functions have been widely studied, and are called near-bent or semi-bent (when n is odd), see for instance [START_REF] Charpin | On bent and semi-bent quadratic Boolean functions[END_REF][START_REF] Leander | Construction of bent functions from near-bent functions[END_REF].

One of the problems, that [START_REF] Khoo | A new characterization of semi-bent and bent functions on finite fields[END_REF] focuses on, is to characterize integers n, for which all f from F 2 n to F 2 of the form (1) are near-bent.

The more general question we address here is the following: Given an integer n, characterize those integers s, for which s-plateaued functions from F 2 n to F 2 of the form (1) exist. We obtain the characterization when n is a squarefree integer or is a power of 2. For these classes of integers n, we give methods for constructing s-plateaued functions for all possible s. We also enumerate the s-plateaued functions in case n = 2 m , m ≥ 1.

Using standard Welch-squaring techniques one can see that the integer s is the dimension over F 2 of the kernel of the linear transformation defined on F 2 n by

L(x) = ⌊(n-1)/2⌋ i=0 a i x 2 i + a 2 n-i i x 2 n-i ,
i.e., gcd(x 2 n +x, L(x)) has degree 2 s . Equivalently ker(L) has dimension s if and only if the associates A(x) and x n + 1 of L(x) and x 2 n + x, respectively, satisfy (see [7, p.118])

deg(gcd(A(x), x n + 1)) = s. The associate A(x) corresponding to f in (1) is A(x) = ⌊(n-1)/2⌋ i=0 a i x i + a i x n-i = x i0 g(x), (2)
where i 0 is the smallest integer such that a i0 = 0, and

g(x) ∈ F 2 [x] is the self-reciprocal polynomial g(x) = ⌊(n-1)/2⌋ i=i0 a i (x i-i0 + x n-i0-i ) of degree n -2i 0 .
Note that gcd(

⌊(n-1)/2⌋ i=0 a i x i + a i x n-i , x n + 1) = gcd(( ⌊(n-1)/2⌋ i=1
a i x i + a i x n-i ) + a 0 (x n + 1), x n + 1), i.e., a 0 does not effect the value of s. Hence we can suppose that the degree of A(x) is at most n -1.

We recall that the linear complexity L(S) of an n-periodic sequence S = s 0 , s 1 , . . . over F 2 is determined by

L(S) = n -deg(gcd(x n + 1, S(x)))
where S(x) is the generating polynomial of S, i.e., the polynomial of degree at most n -1 given by S(x) = s 0 + s 1 x + • • • + s n-1 x n-1 . Therefore the calculation of the values in the Fourier spectrum of a quadratic function (1) is equivalent to the determination of the linear complexity of an n-periodic sequence with generating polynomial of the form (2). More precisely s = n -L if L is the linear complexity of the corresponding n-periodic sequence.

Main Results

The case n = 2 m

In this subsection we will employ the well known Games-Chan algorithm (see [START_REF] Games | A fast algorithm for determining the complexity of a binary sequence with period 2 n[END_REF]) to enumerate the functions (1) from F 2 2 m to F 2 that yield s-plateaued functions. The algorithm also leads to a tool of constructing s-plateaued functions for a given s.

The following example describes how one can calculate s.

Example 1. For m = 4 consider f (x) = Tr n (x 2 + x 3 + x 2 4 +1 + x 2 5 +1 ), then A(x) = 1 + x + x 4 + x 5 + x 11 + x 12 + x 15 + x 16 . For our purpose we consider this polynomial modulo x 16 + 1 and put

A(x) = x + x 4 + x 5 + x 11 + x 12 + x 15
and obtain the corresponding 16-periodic binary sequence

S = (0100110000011001) ∞ . 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 L = 8 0 1 0 1 0 1 0 1 0 0 0 0 L = 8 0 1 0 1 0 0 L = 8 0 1 1 L = 9 L = L + 1 = 10.
As the 16-periodic sequence S corresponding to A(x) has linear complexity L = 10, the quadratic function f is s-plateaued with s = 16 -10 = 6.

The Games-Chan algorithm motivates the definition of a mapping

ϕ m from F 2 m 2 to F 2 m-1 2 , m ≥ 1, as follows: ϕ m ((s 0 , s 1 , . . . , s 2 m -1 )) = (s 0 + s 2 m-1 , s 1 + s 2 m-1 +1 , . . . , s 2 m-1 -1 + s 2 m -1 ).
In the following proposition we collect some simple observations for 2 m -periodic sequences corresponding to polynomials A(x) in ( 2) with n = 2 m . As remarked above we can assume that a 0 = 0, thus deg(A) ≤ n -1. The strings s (m) = s 0 , s 1 , . . . , s 2 m -1 of our interest can easily be seen to satisfy s 0 = s n/2 = 0, s i = s n-i , i = 1, . . . , n/2 -1. We will call a string satisfying these properties antisymmetric. Accordingly, we call the corresponding sequence antisymmetric 2 m -periodic sequence.

Proposition 1. Let s (m) = s 0 , s 1 , . . . , s 2 m -1 be a string, m ≥ 1.

(i) An antisymmetric string s (m) is determined by the bits s 1 , . . . , s 2 m-1 -1 . There are

2 2 m-1 -1 distinct antisymmetric strings of length 2 m . (ii) If s (m) is antisymmetric, then ϕ m (s (m) ) is also. (iii) The set of antisymmetric preimages ϕ -1 m (s (m-1)
) of an antisymmetric string s (m-1) has cardinality 2 2 m-2 . (iv) Let s (m) be an antisymmetric string satisfying ϕ m (s (m) ) = 0, 0, . . . , 0. Then either s 0 , s 1 , . . . , s 2 m-1 -1 is itself antisymmetric, or the string

s 0 , s 1 , . . . , s 2 m-2 + 1, . . . , s 2 m-1 -1
is antisymmetric.

In the first case ϕ m-1 (s 0 , s 1 , . . . , s 2 m-1 -1 ) = t 0 , t 1 , . . . , t 2 m-2 -1 is antisymmetric, and in the second case the string t 0 -1, t 1 , . . . , t 2 m-2 -1 is antisymmetric.

Theorem 1. For n = 2 m , let N m (s) denote the number of strings

(a 1 , a 2 , . . . , a (n/2)-1 ) ∈ F (n/2)-1 2
for which the quadratic function f from F 2 n to F 2 , given by

f (x) = Tr n   (n/2)-1 i=1 a i x 2 i +1   is s-plateaued. Then N m (s) = 2 2 m-1 -1-k : s = 2k, k = 1, . . . , 2 m-1 -1, 0 : s = 0 or s odd.
Proof. We use induction. One can easily see that the assertion holds for small m.

Now suppose that N m-1 (s) = 2 2 m-2 -1-k for s = 2k, k = 1, . . . , 2 m-2 -1, i.e.
, for these values of s, there are 2 2 m-2 -1-k sequences, which are 2 m-1 -periodic with linear complexity 2 m-1s, corresponding to antisymmetric strings. By Proposition 1 (iii), for each of these stings we have 2 2 m-2 antisymmetric preimages giving rise to antisymmetric 2 m -periodic sequences with linear complexity 2 ms. Proposition 1 (ii) implies that these are all such sequences. Consequently, we get

N m (s) = 2 2 m-2 2 2 m-2 -1-k = 2 2 m-1 -1-k when s = 2k, k = 1, . . . , 2 m-2 -1.
It remains to show that the formula holds for s = 2k with k = 2 m-2 , . . . , 2 m-1 -1.

We therefore have to enumerate the antisymmetric 2 m -periodic sequences with a given linear complexity 2 ms ≤ 2 m-1 . First observe that these are the sequences corresponding to antisymmetric strings s (m) = s 0 , . . . , s 2 m -1 such that (a) ϕ m (s (m) ) = 0, 0, . . . , 0, or (b) the sequence corresponding to s 0 , . . . , s 2 m-1 -1 has linear complexity 2 ms.

By Proposition 1 (iv), (a) implies that s 0 , . . . , s 2 m-1 -1 or s 0 , s 1 , . . . , s 2 m-2 + 1, . . . , s 2 m-1 -1 is antisymmetric. Moreover it is easily seen that for any such string there is exactly one corresponding antisymmetric string s (m) for which (a) holds. Having an odd number of 1's, the 2 m-2 -1 strings of the second type yield 2 m-1 -periodic sequences with linear complexity L = 2 m-1 (thus s = 2 m -L = 2 m-1 ). Among the 2 m-2 -1 strings of the first type, by our hypothesis, precisely 2 2 m-2 -1-κ yield 2 m-1 -periodic sequences with linear complexity L = 2 m-1 -2κ, κ = 1, . . . , 2 m-2 -1. Substituting κ by k -2 m-2 we obtain 2 2 m-1 -1-k for the number of antisymmetric 2 m -periodic sequences with linear complexity

L = 2 m -2k (thus s = 2k) for k = 2 m-2 + 1, . . . , 2 m-1 -1, hence N m (s) = 2 2 m-2 2 2 m-2 -1-k = 2 2 m-1 -1-k
for these values of k, and s = 2k. Note that from the above arguments we also see that N m (s) = 0 when s = 0 and when s is odd. However one can also see directly that N m (0) = 0 since antisymmetric strings contain an even number of 1's, and the statement for odd s simply follows from the Fourier transform being an integer. ✷

Note that the arguments in the proof also enable the construction of s-plateaued quadratic functions from F 2 2 m to F 2 for a prescribed value of s.

The case n

= p 1 p 2 • • • p r
The results in this subsection are obtained with a different approach, namely by analysing the factorization of x n + 1 into self-reciprocal polynomials. With the observation that gcd(

x n +1, A(x)) is again self-reciprocal if A(x) is self-reciprocal,
one obtains the following general theorem, which is valid for arbitrary integers n.

Theorem 2. Let n be arbitrary.

(i) If n is odd, then there exists an s-plateaued function of the form (1) if and only if s is odd and x n + 1 has a self-reciprocal factor h(x) of degree s (in which case x n + 1 is always divisible by x + 1).

(ii) If n is even then there exists an s-plateaued function of the form (1) if and only if s is even and x n + 1 has a self-reciprocal factor h(x) of degree s divisible by (x + 1) 2 .

Note that if n = 2 v n 1 , n 1 odd, then x n + 1 = (x n1 + 1) 2 v . Thus it is sufficient to analyse the factorization of x n +1 for odd n. Here we only consider the case of n being square-free. Our main tool for studying the factorization of x n + 1 into self-reciprocals is, as expected, the use of cyclotomic cosets modulo n relative to powers of 2.

We denote the n-th cyclotomic polynomial by Q n , and denote the 2-adic valuation of an integer k by ν(k) , i.e., 2 ν(k) is the largest power of 2 which divides k. The following lemma describes for which squarefree integers n

= p 1 p 2 • • • p r the irreducible factors of Q n are self-reciprocal. Note that Q n has d irreducible factors where d = lcm(d 1 , . . . , d r ) = ord n 2. Lemma 1. Let n = p 1 p 2 • • • p r , d i = ord pi 2 and d = ord n 2. Suppose the irre- ducible factors of Q n are f 1 , . . . , f ϕ(n)/d . Then (i) The polynomials f 1 , . . . , f ϕ(n)/d are self-reciprocal if and only if ν(d 1 ) = ν(d 2 ) = • • • = ν(d r ) > 0. In particular, if n is a prime p, then f 1 , . . . , f (p-1)/d are self-reciprocal if and only if d is even. (ii) If ν(d i ) = ν(d j ) for some 1 ≤ i, j ≤ ϕ(n)/d, then none of the polynomials f t , 1 ≤ t ≤ ϕ(n)/d, is self-reciprocal, and for each t, 1 ≤ t ≤ ϕ(n)/d, there exists a unique t ′ = t, 1 ≤ t ′ ≤ ϕ(n)/d such that the product f t f t ′ is self-reciprocal.
Idea of Proof. First observe that the irreducible factors of Q n are self-reciprocal if every cyclotomic coset modulo n relative to powers of 2 containing the element a also contains the element -a. Therefore an irreducible factor of Q n is selfreciprocal if the cyclotomic coset of 1 also contains -1, i.e., 2 k ≡ -1 mod n for some integer k. This is equivalent to A simple consequence of the above lemma is also the main result of [START_REF] Khoo | A new characterization of semi-bent and bent functions on finite fields[END_REF]: All functions of the form (1) from F 2 n to F 2 are 1-plateaued (near-bent) only when n = p is a prime, satisfying p ≡ 3 mod 4 with ord p 2 = (p -1)/2, or 2 is a primitive root modulo p. Note that the self-reciprocal factors of x n + 1 are exactly x + 1 and 1 + x • • • + x n-1 only for such n.

2 k ≡ -1 mod p 1 , i ≤ i ≤ r,
In order to determine the possible values of s that a function of the form (1) has Fourier spectrum F s,f , we consider all cyclotomic polynomials Q m , m|n and apply Lemma 1 accordingly: Similarly it is easy to see that x 105 + 1 has one self-reciprocal factor of degree 6, and two irreducible self-reciprocal factors; one of degree 4, and one of degree 2.

As n + s must be even, the maximal possible value for s is s = n -2. We have to choose a self-reciprocal divisor h(x) of x n + 1 of degree n -2. The only possible choices for h(x) are (i) h(x) = (x n + 1)/(x + 1) 2 . (ii) h(x) = (x n + 1)/(x 2 + x + 1). Now (i) implies that n is even and since then (x + 1) 2 must divide h(x), we need 4|n, and (ii) implies that 3|n. The step 2 in the above procedure can not be carried out, thus g(x) = h(x), and i 0 = 1. We then get A(x) = xh(x) = x + x 3 + x 5 + • • • + x n-1 in case (i), and A(x) = xh(x) = x + x 2 + x 4 + x 5 + x 7 + x 8 + • • • + x n-2 + x n-1 in case (ii).

The following corollary easily follows from the argument used in the above example.

Conclusion

We enumerate quadratic s-plateaued functions from F 2 2 m to F 2 , given by (1). For squarefree integers n = p 1 p 2 • • • p r we characterize the integers s, for which s-plateaued functions from F 2 n to F 2 of the form (1) exist. Methods for constructing such functions are also described. Our results generalize earlier work on the case s = 1, see [START_REF] Khoo | A new family of Gold-like sequences[END_REF][START_REF] Khoo | A new characterization of semi-bent and bent functions on finite fields[END_REF].

  which holds if and only if d i divides 2k but not k for each i. This leads to the condition ν(d 1 ) = ν(d 2 ) = • • • = ν(d r ) > 0. ✷ By Lemma 1 and [7, Exercise 3.15] the polynomial x n + 1 factors into selfreciprocal irreducible polynomials if and only ν(d 1 ) = ν(d 2 ) = • • • = ν(d r ) > 0. Example 2. I. n = 5 • 13 = 65, then d 1 = 4, d 2 = 12, hence ν(d 1 ) = ν(d 2 ). Consequently x 65 + 1 factors into self-reciprocal irreducible polynomials. II. n = 3 • 5 • 7 = 105, then d 1 = 2, d 2 = 4, d 3 = 3 and ν(d 1 ) = ν(d 2 ). Hence not all the irreducible factors of x 105 + 1 are self-reciprocal.

Example 2 .

 2 II. continued: n = 3 • 5 • 7 = 105, d 1 = 2, d 2 = 4, d 3 = 3. ϕ(n) = 48, d = gcd(2, 4, 3) = 12, and ν(d 1 ) = ν(d 2 ). Hence x 105 + 1 has 2 self-reciprocal factors of degree 24. ϕ(35) = 24, gcd(d 2 , d 3 ) = gcd(4, 3) = 12, and ν(4) = ν(3), which yields 2 cyclotomic classes of cardinality 12, and hence one self-reciprocal factor of degree 24. ϕ(21) = 12, gcd(2, 3) = 6. There are 2 cyclotomic classes of cardinality 6 corresponding to one self-reciprocal factor of degree 12. ϕ(15) = 8, gcd(2, 4) = 4, ν(2) = ν(4). There are 2 cyclotomic classes of cardinality 4, giving one self-reciprocal factor of degree 8.

Corollary 3 .

 3 The quadratic function f of the form[START_REF] Charpin | On bent and semi-bent quadratic Boolean functions[END_REF] is (n -2)-plateaued if and only if (i) 4|n and f (x) = Tr n εx 2 + x 2+1 + x 2 3 +1 + x 2 5 +1 + • • • + x 2 n/2-1 +1 , ε ∈ {0, 1}, or (ii) 3|n and f (x) = Tr n εx 2 + ⌊n-1/2⌋ i=1,i ≡0 mod 3 x 2 i +1 , ε ∈ {0, 1}.Compare our Corollary 3 with Theorem 2.4 in[START_REF] Fitzgerald | Highly degenerate forms over finite fields of characteristic 2[END_REF].

Therefore s can be any integer less than 105 of the form s = 24k 1 + 12k 2 + 8k 3 + 6k 4 + 4k 5 + 2k 6 + 1, 0 ≤ k 1 ≤ 3 and 0 ≤ k i ≤ 1 for 2 ≤ i ≤ 6.

We list the possible values of s in two special cases: Corollary 1. Let n be an odd prime with ord n 2 = d.

(i) If d is even, then there exists an s-plateaued function of the form (1) from F 2 n to F 2 if and only if s = kd + 1 for some 0 ≤ k ≤ (n -1)/d -1.

(ii) If d is odd, then there exists an s-plateaued function of the form (1) from F 2 n to F 2 if and only if s = 2kd + 1 for some 0 ≤ k ≤ (n -1)/(2d) -1.

Corollary 2. Let n = pq for two odd primes p and q and let ord p 2 = d p , ord q 2 = d q . The integers s for which there exists an s-plateaued function of the form (1) from F n 2 to F 2 are given as follows: s < n and

Now the methods of constructing s-plateaued functions of the form (1) with prescribed s are obvious:

1. Among the self-reciprocal factors of x n + 1 select some, whose degrees add up to s and form their product h(x). We remark that s must be odd if n is odd, thus x + 1 must divide h(x). If n is even then also s must be even, hence h(x) will always be divisible by (x + 1) g for some even integer g ≥ 2.

2. Multiply h(x) with a self-reciprocal polynomial of even degree, which is relatively prime to (x n + 1)/h(x). The resulting product g(x) must be of degree at most n -1.

3. Multiply g(x) with x i0 , where i 0 is the unique integer such that A(x) = x i0 g(x) is of the form (2). Note that a 0 = 0 for any A(x), obtained this way. 4. The polynomial f (x) of the form (1) corresponding to a A(x) is then splateaued. Note that a 0 can be chosen as 0 or 1.

The following example leads to an easy proof of a result of [START_REF] Fitzgerald | Highly degenerate forms over finite fields of characteristic 2[END_REF].

Example 3. Construction of s-plateaued functions with maximal possible value for s: