Campopiano-type bounds in non-Hamming array coding

Campopiano [C.N. Campopiano, Bounds on burst error correcting codes, IRE Trans. IT-8 (1962) 257-259] obtained an upper bound for burst error correction in classical coding systems where codes are subsets/subspaces of the space , the space of all n-tuples with entries from a finite field F_q equipped with the Hamming metric. In [S. Jain, Bursts in m-metric array codes, Linear Algebra Appl., in press], the author introduced the notion of burst errors for m-metric array coding systems 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 and obtained some lower bounds for burst error correction. In this paper, we obtain various construction upper bounds 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.     

Three-dimensional cyclic Fire codes

Three-dimensional cyclic array codes over F _q that can correct single three-dimensional bursts (or clusters) of errors are considered. The class 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.     

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.     

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.     

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.     

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     

The minimum size of a finite subspace partition

A subspace partition of P=PG(n,q) is a collection of subspaces of P whose pairwise intersection is empty. Let σ_q(n,t) denote the minimum size (i.e., minimum number of subspaces) in a subspace partition of P in which the largest subspace has dimension t. In this paper, we determine the value of σ_q(n,t) for . Moreover, we use the value of σ_q(2t+2,t) to find the minimum size of a maximal partial t-spread in PG(3t+2,q).     

Some colouring problems for Paley graphs

The Paley graph P_q, where is a prime power, is the graph with vertices the elements of the finite field F_q and an edge between x and y if and only if x-y is a non-zero square in F_q. This paper gives new results on some colouring problems for Paley graphs and related discussion.     

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.     

Classifying Subspaces of Hamming Spaces

A linear code in F ⁿ _q with dimension k and minimum distance at least d is called an [n, k, d] _q code. We here consider the problem of classifying all [n, k, d] _q codes given n, k, d, and q. In other words, given the Hamming space F ⁿ _q and a dimension k, we classify all k-dimensional subspaces of the Hamming space with minimum distance at least d. Our classification is an iterative procedure where equivalent codes are identified by mapping the code equivalence problem into the graph isomorphism problem, which is solved using the program nauty. For d = 3, the classification is explicitly carried out for binary codes of length n 14, ternary codes of length n 11, and quaternary codes of length n 10.     

Solving sparse linear systems of equations over finite fields using bit-flipping algorithm

Let _Fq${\mathbb{F}}_q$ be the finite field with q   elements. We give an algorithm for solving sparse linear systems of equations over _Fq${\mathbb{F}}_q$ when the coefficient matrix of the system has a specific structure, here called relatively connected. This algorithm is based on a well-known decoding algorithm for low-density parity-check codes called bit-flipping algorithm. We modify and extend this hard decision decoding algorithm. The complexity of this algorithm is linear in terms of the number of columns n and the number of nonzero coefficients ω of the matrix per iteration. The maximum number of iterations is bounded above by m, the number of equations.     

The golden ratio and super central configurations of the n-body problem

In this paper, we consider the problem of central configurations of the n-body problem with the general homogeneous potential 1/rα. A configuration q=(q₁,q₂,…,qn) is called a super central configuration if there exists a positive mass vector m=(m₁,…,mn) such that q is a central configuration for m with mi attached to qi and q is also a central configuration for m^′, where m^′≠m and m^′ is a permutation of m. The main discovery in this paper is that super central configurations of the n-body problem have surprising connections with the golden ratio φ. Let r be the ratio of the collinear three-body problem with the ordered positions q₁, q₂, q₃ on a line. q is a super central configuration if and only if 1/r₁(α)<r<r₁(α) and r≠1, where r₁(α)>1 is a continuous function such that , the golden ratio. The existence and classification of super central configurations are established in the collinear three-body problem with general homogeneous potential 1/rα. Super central configurations play an important role in counting the number of central configurations for a given mass vector which may decrease the number of central configurations under geometric equivalence.     

Covering compacta by discrete subspaces

For any space X, denote by dis(X) the smallest (infinite) cardinal κ such that κ many discrete subspaces are needed to cover X. It is easy to see that if X is any crowded (i.e. dense-in-itself) compactum then dis(X)?m, where m denotes the additivity of the meager ideal on the reals. It is a natural, and apparently quite difficult, question whether in this inequality m could be replaced by c. Here we show that this can be done if X is also hereditarily normal.Moreover, we prove the following mapping theorem that involves the cardinal function dis(X). If is a continuous surjection of a countably compact T₂ space X onto a perfect T₃ space Y then .     

Quantum integers and cyclotomy

A sequence of functions satisfies the functional equation for multiplication of quantum integers if f_mn(q)=f_m(q)f_n(q^m) for all positive integers m and n. This paper describes the structure of all sequences of rational functions with coefficients in Q that satisfy this functional equation.     

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.     

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.