Bursts in m-metric array codes

Fire [P. Fire, A class of multiple-error-correcting binary codes for non-independent errors, Sylvania Reports RSL-E-2, Sylvania Reconnaissance Systems, Mountain View, California, 1959] introduced the concept of bursts for classical codes where codes are subsets/subspaces of the space , the space of all n-tuples with entries from a finite field F_q. In this paper, we introduce the notion of bursts for m-metric array codes where m-metric array codes are subsets/subspaces of the space Mat_m×s(F_q), the linear space of all m × s matrices with entries from a finite field F_q, endowed with a non-Hamming metric. We also obtain some bounds (analogous to Fire’s bound [P. Fire, A class of multiple-error-correcting binary codes for non-independent errors, Sylvania Reports RSL-E-2, Sylvania Reconnaissance Systems, Mountain View, California, 1959], Rieger’s bound [S.H. Reiger, Codes for the correction of clustered errors, IRE-Trans., IT-6 (1960), 16-21] etc. in classical codes) on the parameters of m-metric array codes for the detection and correction of burst errors.     

CT bursts—from classical to array coding

R.T. Chien and D.T. Tang [On definition of a burst, IBM J. Res. Develop. 9 (1965) 292-293] introduced the concept of Chien and Tang bursts (CT bursts) for classical coding systems where codes are subsets (or subspaces) of the space , the space of all n-tuples with entries from a finite field F_q. In this paper, we extend the notion of CT bursts for array coding systems where array codes are subsets (or subspaces) of the space Mat_m×s(F_q), the linear space of all m×s matrices with entries from a finite field F_q, endowed with a non-Hamming metric [M.Yu. Rosenbloom, M.A. Tsfasman, Codes for m-metric, Problems Inform. Transmission 33 (1997) 45-52]. We also obtain some bounds on the parameters of array codes for the detection and correction of CT burst errors.     

Correction of CT burst array errors in the generalized-lee-RT spaces

In [Jain, S.： Array codes in the generalized-Lee-RT-pseudo-metric （the GLRTP-metric）, to appear in Algebra Colloq.], Jain introduced a new pseudo-metric on the space Matm×s（Zq）, the module space of all m × s matrices with entries from the finite ring Zq, generalized the classical Lee metric [Lee, C. Y.： Some properties of non-binary error correcting codes. IEEE Trans. Inform. Theory, IT-4, 77- 82 （1958）] and array RT-metric [Rosenbloom, M. Y., Tsfasman, M. A.： Codes for m-metric. Prob. Inf. Transm., 33, 45-52 （1997）] and named this pseudo-metric as the Generalized-Lee-RT-Pseudo-Metric （or the GLRTP-Metric）. In this paper, we obtain some lower bounds for two-dimensional array codes correcting CT burst array errors [Jain, S.： CT bursts from classical to array coding. Discrete Math., 308-309, 1489-1499 （2008）] with weight constraints under the GLRTP-metric.     

Path-kipas Ramsey numbers

For two given graphs F and H, the Ramsey number R(F,H) is the smallest positive integer p such that for every graph G on p vertices the following holds: either G contains F as a subgraph or the complement of G contains H as a subgraph. In this paper, we study the Ramsey numbers , where P_n is a path on n vertices and is the graph obtained from the join of K₁ and P_m. We determine the exact values of for the following values of n and m: 1?n?5 and m?3; n?6 and (m is odd, 3?m?2n-1) or (m is even, 4?m?n+1); 6?n≤7 and m=2n-2 or m?2n; n?8 and m=2n-2 or m=2n or (q·n-2q+1?m?q·n-q+2 with 3?q?n-5) or m?(n-3)²; odd n?9 and (q·n-3q+1?m?q·n-2q with 3?q?(n-3)/2) or (q·n-q-n+4?m?q·n-2q with (n-1)/2?q?n-4). Moreover, we give lower bounds and upper bounds for for the other values of m and n.     

Integral point sets in higher dimensional affine spaces over finite fields

We consider point sets in the m-dimensional affine space where each squared Euclidean distance of two points is a square in Fq. It turns out that the situation in is rather similar to the one of integral distances in Euclidean spaces. Therefore we expect the results over finite fields to be useful for the Euclidean case.We completely determine the automorphism group of these spaces which preserves integral distances. For some small parameters m and q we determine the maximum cardinality I(m,q) of integral point sets in . We provide upper bounds and lower bounds on I(m,q). If we map integral distances to edges in a graph, we can define a graph Gm,q with vertex set . It turns out that Gm,q is strongly regular for some cases.     

Optimal interleaving schemes for correcting two-dimensional cluster errors

We present an elementary theory of optimal interleaving schemes for correcting cluster errors in two-dimensional digital data. It is assumed that each data page contains a fixed number of, say n, codewords with each codeword consisting of m code symbols and capable of correcting a single random error (or erasure). The goal is to interleave the codewords in the m×n array such that different symbols from each codeword are separated as much as possible, and consequently, an arbitrary error burst with size up to t can be corrected for the largest possible value of t. We show that, for any given m, n, the maximum possible interleaving distance, or equivalently, the largest size of correctable error bursts in an m×n array, is given by if n?⌈m²/2⌉, and t=m+⌊(n-⌈m²/2⌉)/m⌋ if n?⌈m²/2⌉. Furthermore, we develop a simple cyclic shifting algorithm that can provide a systematic construction of an m×n optimal interleaving array for arbitrary m and n. This extends important earlier work on the complementary problem of constructing interleaving arrays that, given the burst size t, minimize the interleaving degree, that is, the number of different codewords in a 2-D (or 3-D) array such that any error burst with given size t can be corrected. Our interleaving scheme thus provides the maximum burst error correcting power without requiring prior knowledge of the size or shape of an error burst.     

Structural properties and enumeration of 1-generator generalized quasi-cyclic codes

Let F _q be a finite field of cardinality q, m ₁, m ₂, . . . , m _l be any positive integers, and \({A_i=F_q[x]/(x^{m_i}-1)}\) for i = 1, . . . , l. A generalized quasi-cyclic (GQC) code of block length type (m ₁, m ₂, . . . , m _l ) over F _q is defined as an F _q [x]-submodule of the F _q [x]-module \({A_1\times A_2\times\cdots\times A_l}\). By the Chinese Remainder Theorem for F _q [x] and enumeration results of submodules of modules over finite commutative chain rings, we investigate structural properties of GQC codes and enumeration of all 1-generator GQC codes and 1-generator GQC codes with a fixed parity-check polynomial respectively. Furthermore, we give an algorithm to count numbers of 1-generator GQC codes.     

Constructions and bounds on linear error-block codes

We obtain new bounds on the parameters and we give new constructions of linear error-block codes. We obtain a Gilbert–Varshamov type construction. Using our bounds and constructions we obtain some infinite families of optimal linear error-block codes over . We also study the asymptotic of linear error-block codes. We define the real valued function α _q,m,a (δ), which is an analog of the important real valued function α _q (δ) in the asymptotic theory of classical linear error-correcting codes. We obtain both Gilbert–Varshamov and algebraic geometry type lower bounds on α _q,m,a (δ). We compare these lower bounds in graphs.      

Fq-linear Cyclic Codes over $$ F{_q^m}$$ : D FT Approach

Codes over that are closed under addition, and multiplication with elements from F_q are called F_q-linear codes over . For m 1, this class of codes is a subclass of nonlinear codes. Among F_q-linear codes, we consider only cyclic codes and call them F_q-linear cyclic codes (F_q LC codes) over The class of F_q LC codes includes as special cases (i) group cyclic codes over elementary abelian groups (q=p, a prime), (ii) subspace subcodes of Reed–Solomon codes (n=q^m–1) studied by Hattori, McEliece and Solomon, (iii) linear cyclic codes over F_q (m=1) and (iv) twisted BCH codes. Moreover, with respect to any particular F_q-basis of , any F_qLC code over can be viewed as an m-quasi-cyclic code of length mn over F_q. In this correspondence, we obtain transform domain characterization of F_q LC codes, using Discrete Fourier Transform (DFT) over an extension field of The characterization is in terms of any decomposition of the code into certain subcodes and linearized polynomials over . We show how one can use this transform domain characterization to obtain a minimum distance bound for the corresponding quasi-cyclic code. We also prove nonexistence of self dual F_q LC codes and self dual quasi-cyclic codes of certain parameters using the transform domain characterization.AMS classification 94B05     

Expansions in non-integer bases: Lower, middle and top orders

Let q∈(1,2); it is known that each x∈[0,1/(q−1)] has an expansion of the form with an∈{0,1}. It was shown in [P. Erd?s, I. Joó, V. Komornik, Characterization of the unique expansions and related problems, Bull. Soc. Math. France 118 (1990) 377-390] that if , then each x∈(0,1/(q−1)) has a continuum of such expansions; however, if , then there exist infinitely many x having a unique expansion [P. Glendinning, N. Sidorov, Unique representations of real numbers in non-integer bases, Math. Res. Lett. 8 (2001) 535-543]. In the present paper we begin the study of parameters q for which there exists x having a fixed finite number m>1 of expansions in base q. In particular, we show that if q<q₂=1.71…, then each x has either 1 or infinitely many expansions, i.e., there are no such q in . On the other hand, for each m>1 there exists γm>0 such that for any q∈(2−γm,2), there exists x which has exactly m expansions in base q.     

Weighted differentiation composition operators from mixed-norm spaces to weighted-type spaces

Motivated by the recent paper [X. Zhu, Products of differentiation composition and multiplication from Bergman type spaces to Bers spaces, Integral Transform. Spec. Funct. 18 (3) (2007) 223-231], we study the boundedness and compactness of the weighted differentiation composition operator , where u is a holomorphic function on the unit disk D, φ is a holomorphic self-map of D and n∈N₀, from the mixed-norm space H(p, q, ?), where p,q > 0 and ? is normal, to the weighted-type space or the little weighted-type space . For the case of the weighted Bergman space , p > 1, some bounds for the essential norm of the operator are also given.     

On the variation of Tate-Shafarevich groups of elliptic curves over hyperelliptic curves

Let E be an elliptic curve over F=F_q(t) having conductor (p)·∞, where (p) is a prime ideal in F_q[t]. Let d∈F_q[t] be an irreducible polynomial of odd degree, and let . Assume (p) remains prime in K. We prove the analogue of the formula of Gross for the special value L(E⊗_FK,1). As a consequence, we obtain a formula for the order of the Tate-Shafarevich group Ш(E/K) when L(E⊗_FK,1)≠0.     

On the Number of Solutions of Polynomial Systems

We consider systems of homogenous polynomial equations of degreedin a projective space ^mover a finite field _q. We attempt to determine the maximum possible number of solutions of such systems. The complete answer for the caser= 2,d<q− 1 is given, as well as new conjectures about the general case. We also prove a bound on the number of points of an algebraic set of given codimension and degree. We also discuss an application of our results to coding theory, namely to the problem of computing generalized Hamming weights forq-ary projective Reed–Muller codes.     

Maximal integral point sets in affine planes over finite fields

Motivated by integral point sets in the Euclidean plane, we consider integral point sets in affine planes over finite fields. An integral point set is a set of points in the affine plane over a finite field F_q, where the formally defined squared Euclidean distance of every pair of points is a square in F_q. It turns out that integral point sets over F_q can also be characterized as affine point sets determining certain prescribed directions, which gives a relation to the work of Blokhuis. Furthermore, in one important sub-case, integral point sets can be restated as cliques in Paley graphs of square order.In this article we give new results on the automorphisms of integral point sets and classify maximal integral point sets over F_q for q≤47. Furthermore, we give two series of maximal integral point sets and prove their maximality.     

A functional equation arising from multiplication of quantum integers

For the quantum integer [n]_q=1+q+q²+?+qⁿ⁻¹ there is a natural polynomial multiplication such that [m]_q⊗_q[n]_q=[mn]_q. This multiplication leads to the functional equation f_m(q)f_n(q^m)=f_mn(q), defined on a given sequence of polynomials. This paper contains various results concerning the construction and classification of polynomial sequences that satisfy the functional equation, as well open problems that arise from the functional equation.     

On the length of the tail of a vector space partition

A vector space partition of a finite dimensional vector space V=V(n,q) of dimension n over a finite field with q elements, is a collection of subspaces U₁,U₂,…,U_t with the property that every non zero vector of V is contained in exactly one of these subspaces. The tail of consists of the subspaces of least dimension d₁ in , and the length n₁ of the tail is the number of subspaces in the tail. Let d₂ denote the second least dimension in .Two cases are considered: the integer q^d₂−d₁ does not divide respective divides n₁. In the first case it is proved that if 2d₁>d₂ then n₁≥q^d₁+1 and if 2d₁≤d₂ then either n₁=(q^d₂−1)/(q^d₁−1) or n₁>2q^d₂−d₁. These lower bounds are shown to be tight and the elements in the subspaces in tails of minimal length will constitute a subspace of V of dimension 2d₁ respectively d₂.In case q^d₂−d₁ divides n₁ it is shown that if d₂<2d₁ then n₁≥q^d₂−q^d₁+q^d₂−d₁ and if 2d₁≤d₂ then n₁≥q^d₂. The last bound is also shown to be tight.The results considerably improve earlier found lower bounds on the length of the tail.     

Colouring lines in projective space

Let V be a vector space of dimension v over a field of order q. The q-Kneser graph has the k-dimensional subspaces of V as its vertices, where two subspaces α and β are adjacent if and only if is the zero subspace. This paper is motivated by the problem of determining the chromatic numbers of these graphs. This problem is trivial when k=1 (and the graphs are complete) or when v<2k (and the graphs are empty). We establish some basic theory in the general case. Then specializing to the case k=2, we show that the chromatic number is q²+q when v=4 and (q^v-1-1)/(q-1) when v>4. In both cases we characterise the minimal colourings.