An Extension Theorem for Linear Codes

One of the first results one meets in coding theory is that a binary linear [n,k,d] code, whose minimum distance is odd, can be extended to an [n + 1, k, d + 1] code. This is one of the few elementary results about binary codes which does not obviously generalise to q-ary codes. The aim of this paper is to give a simple sufficient condition for a q-ary [n, k, d] code to be extendable to an [n + 1, k, d + 1] code. Applications will be given to the construction and classification of good codes, to proving the non- existence of certain codes, and also an application in finite geometry.     

On the Achievement of the Griesmer Bound

The main theorem in this paper is that there does not exist an [n,k,d]_q code with d = (k-2)q ^k-1 - (k-1)q^k-2 attaining the Griesmer bound for q k, k=3,4,5 and for q 2k-3, k 6.     

Regular simplices, symmetric polynomials and the mean value property

LetP be ann-dimensional regular simplex in ℝⁿ centered at the origin, and let P(k) be thek-skeleton ofP fork = 0, 1,…,n. Then the set of all continuous functions in ℝⁿ satisfying the mean value property with respect to P(k) forms a finite-dimensional linear space of harmonic polynomials. In this paper the function space is explicitly determined by group theoretic and combinatorial arguments for symmetric polynomials.     

Elliptic Regularity and Quantitative Homogenization on Percolation Clusters

We establish quantitative homogenization, large‐scale regularity, and Liouville results for the random conductance model on a supercritical (Bernoulli bond) percolation cluster. The results are also new in the case that the conductivity is constant on the cluster. The argument passes through a series of renormalization steps: first, we use standard percolation results to find a large scale above which the geometry of the percolation cluster behaves (in a sense, made precise) like that of euclidean space. Then, following the work of Barlow [8], we find a succession of larger scales on which certain functional and elliptic estimates hold. This gives us the analytic tools to adapt the quantitative homogenization program of Armstrong and Smart [7] to estimate the yet larger scale on which solutions on the cluster can be well‐approximated by harmonic functions on ℝ^d. This is the first quantitative homogenization result in a porous medium, and the harmonic approximation allows us to estimate the scale on which a higher‐order regularity theory holds. The size of each of these random scales is shown to have at least a stretched exponential moment. As a consequence of this regularity theory, we obtain a Liouville‐type result that states that, for each k ∊ ℕ, the vector space of solutions growing at most like o(|x|^k+1) as |x| → ∞ has the same dimension as the set of harmonic polynomials of degree at most k, generalizing a result of Benjamini, Duminil‐Copin, Kozma, and Yadin from k ≤ 1 to k ∊ ℕ. © 2018 Wiley Periodicals, Inc.     

On the code generated by the incidence matrix of points and k-spaces in and its dual

In this paper, we study the p-ary linear code C_k(n,q), q=p^h, p prime, h1, generated by the incidence matrix of points and k-dimensional spaces in PG(n,q). For kn/2, we link codewords of C_k(n,q)C_k(n,q) of weight smaller than 2q^k to k-blocking sets. We first prove that such a k-blocking set is uniquely reducible to a minimal k-blocking set, and exclude all codewords arising from small linear k-blocking sets. For k<n/2, we present counterexamples to lemmas valid for kn/2. Next, we study the dual code of C_k(n,q) and present a lower bound on the weight of the codewords, hence extending the results of Sachar [H. Sachar, The F_p span of the incidence matrix of a finite projective plane, Geom. Dedicata 8 (1979) 407–415] to general dimension.     

Codes that attain minimum distance in every possible direction

The following problem motivated by investigation of databases is studied. Let be a q-ary code of length n with the properties that has minimum distance at least n − k + 1, and for any set of k − 1 coordinates there exist two codewords that agree exactly there. Let f(q, k)be the maximum n for which such a code exists. f(q, k)is bounded by linear functions of k and q, and the exact values for special k and qare determined.      

An introduction to the k-defect polynomials

The 0-defect polynomial of a graph is just the chromatic polynomial. This polynomial has been widely studied in the literature. Yet little is known about the properties of k-defect polynomials of graphs in general, when 0 < k ≤ |E(G)|. In this survey we give some properties of k-defect polynomials, in particular we highlight the properties of chromatic polynomials which also apply to k-defect polynomials. We discuss further research which can be done on the k-defect polynomials.     

Large-Scale Analyticity and Unique Continuation for Periodic Elliptic Equations

We prove that a solution of an elliptic operator with periodic coefficients behaves on large scales like an analytic function in the sense of approximation by polynomials with periodic corrections. Equivalently, the constants in the large-scale C^{k, 1} estimate scale exponentially in k , just as for the classical estimate for harmonic functions, and the minimal scale grows at most linearly in k . As a consequence, we characterize entire solutions of periodic, uniformly elliptic equations that exhibit growth like O(exp(δ| x| )) for small δ > 0 . The large-scale analyticity also implies quantitative unique continuation results, namely a three-ball theorem with an optimal error term as well as a proof of the nonexistence of L² eigenfunctions at the bottom of the spectrum. © 2020 Wiley Periodicals LLC.     

Higher Mahler measure for cyclotomic polynomials and Lehmer’s question

The k-higher Mahler measure of a non-zero polynomial P is the integral of log  ^k |P| on the unit circle. In this note, we consider Lehmer’s question (which is a long-standing open problem for k=1) for k>1 and find some interesting formulas for 2- and 3-higher Mahler measure of cyclotomic polynomials.     

Vekua theory for the Helmholtz operator

Vekua operators map harmonic functions defined on domain in \mathbb R²{\mathbb R^{2}} to solutions of elliptic partial differential equations on the same domain and vice versa. In this paper, following the original work of I. Vekua (Ilja Vekua (1907–1977), Soviet-Georgian mathematician), we define Vekua operators in the case of the Helmholtz equation in a completely explicit fashion, in any space dimension N ≥ 2. We prove (i) that they actually transform harmonic functions and Helmholtz solutions into each other; (ii) that they are inverse to each other; and (iii) that they are continuous in any Sobolev norm in star-shaped Lipschitz domains. Finally, we define and compute the generalized harmonic polynomials as the Vekua transforms of harmonic polynomials. These results are instrumental in proving approximation estimates for solutions of the Helmholtz equation in spaces of circular, spherical, and plane waves.     

On the classification of perfect codes: side class structures

The side class structure of a perfect 1-error correcting binary code (hereafter referred to as a perfect code) C describes the linear relations between the coset representatives of the kernel of C. Two perfect codes C and C′ are linearly equivalent if there exists a non-singular matrix A such that AC = C′ where C and C′ are matrices with the code words of C and C′ as columns. Hessler proved that the perfect codes C and C′ are linearly equivalent if and only if they have isomorphic side class structures. The aim of this paper is to describe all side class structures. It is shown that the transpose of any side class structure is the dual of a subspace of the kernel of some perfect code and vice versa; any dual of a subspace of a kernel of some perfect code is the transpose of the side class structure of some perfect code. The conclusion is that for classification purposes of perfect codes it is sufficient to find the family of all kernels of perfect codes.     

Properties of Codes from Difference Sets in 2-Groups

A ( v, k, λ)-difference set D in a group G can be used to create a symmetric 2-( v, k, λ) design, , from which arises a code C, generated by vectors corresponding to the characteristic function of blocks of . This paper examines properties of the code C, and of a subcode, C ^o=JC, where J is the radical of the group algebra of G over . When G is a 2-group, it is shown that C^o is equivalent to the first-order Reed-Muller code, , precisely when the 2-divisor of C^o is maximal. In addition, ifD is a non-trivial difference set in an elementary abelian 2-group, and if D is generated by a quadratic bent function, then C^o is equal to a power of the radical. Finally, an example is given of a difference set whose characteristic function is not quadratic, although the 2-divisor of C^o is maximal.     

Codes of Small Defect

The parameters of a linear code C over GF(q) are given by [n,k,d], where n denotes the length, k the dimension and d the minimum distance of C. The code C is called MDS, or maximum distance separable, if the minimum distance d meets the Singleton bound, i.e. d = n-k+1 Unfortunately, the parameters of an MDS code are severely limited by the size of the field. Thus we look for codes which have minimum distance close to the Singleton bound. Of particular interest is the class of almost MDS codes, i.e. codes for which d=n-k. We will present a condition on the minimum distance of a code to guarantee that the orthogonal code is an almost MDS code. This extends a result of Dodunekov and Landgev Dodunekov. Evaluation of the MacWilliams identities leads to a closed formula for the weight distribution which turns out to be completely determined for almost MDS codes up to one parameter. As a consequence we obtain surprising combinatorial relations in such codes. This leads, among other things, to an answer to a question of Assmus and Mattson 5 on the existence of self-dual [2d,d,d]-codes which have no code words of weight d+1. Actually there are more codes than Assmus and Mattson expected, but the examples which we know are related to the expected ones.     

Thom polynomials, symmetries and incidences of singularities

As an application of the generalized Pontryagin-Thom construction [RSz] here we introduce a new method to compute cohomological obstructions of removing singularities — i.e. Thom polynomials [T]. With the aid of this method we compute some sample results, such as the Thom polynomials associated to all stable singularities of codimension ≤8 between equal dimensional manifolds, and some other Thom polynomials associated to singularities of maps N ⁿ ?P ^n+k for k>0. We also give an application by reproving a weak form of the multiple point formulas of Herbert and Ronga ([H], [Ro2]). As a byproduct of the theory we define the incidence class of singularities, which — the author believes — may turn to be an interesting, useful and simple tool to study incidences of singularities. Oblatum 4-II-1999 & 19-VII-2000?Published online: 30 October 2000     

On the maximality of linear codes

We show that if a linear code admits an extension, then it necessarily admits a linear extension. There are many linear codes that are known to admit no linear extensions. Our result implies that these codes are in fact maximal. We are able to characterize maximal linear (n, k, d) _q -codes as complete (weighted) (n, n − d)-arcs in PG(k − 1, q). At the same time our results sharply limit the possibilities for constructing long non-linear codes. The central ideas to our approach are the Bruen-Silverman model of linear codes, and some well known results on the theory of directions determined by affine point-sets in PG(k, q).      

Generalized balanced tournament designs and related codes

A generalized balanced tournament design, or a GBTD(k, m) in short, is a (km, k, k − 1)-BIBD defined on a km-set V. Its blocks can be arranged into an m × (km − 1) array in such a way that (1) every element of V is contained in exactly one cell of each column, and (2) every element of V is contained in at most k cells of each row. In this paper, we present a new construction for GBTDs and show that a GBTD(4, m) exists for any integer m ≥ 5 with at most eight possible exceptions. A link between a GBTD(k, m) and a near constant composition code is also mentioned. The derived code is optimal in the sense of its size.      

A New Approach to the Main Conjecture on Algebraic-Geometric MDS Codes

The Main Conjecture on MDS Codes statesthat for every linear [n, k] MDS code over q, if 1 <k < q, then n q+1,except when q is even and k=3 or k=q-1,in which cases n q +2. Recently, there has beenan attempt to prove the conjecture in the case of algebraic-geometriccodes. The method until now has been to reduce the conjectureto a statement about the arithmetic of the jacobian of the curve,and the conjecture has been successfully proven in this way forelliptic and hyperelliptic curves. We present a new approachto the problem, which depends on the geometry of the curve afteran appropriate embedding. Using algebraic-geometric methods,we then prove the conjecture through this approach in the caseof elliptic curves. In the process, we prove a new result aboutthe maximum number of points in an arc which lies on an ellipticcurve.     

A remark on full rank perfect codes

Any full rank perfect 1-error correcting binary code of length n=2^k-1 and with a kernel of dimension n-log(n+1)-m, where m is sufficiently large, may be used to construct a full rank perfect 1-error correcting binary code of length 2^m-1 and with a kernel of dimension n-log(n+1)-k. Especially we may construct full rank perfect 1-error correcting binary codes of length n=2^m-1 and with a kernel of dimension n-log(n+1)-4 for m=6,7,…,10.This result extends known results on the possibilities for the size of a kernel of a full rank perfect code.