Density of constant radius normal binary covering codes

A binary code with covering radius R is a subset C of the hypercube Q_n={0,1}ⁿ such that every x∈Q_n is within Hamming distance R of some codeword c∈C, where R is as small as possible. For a fixed coordinate i∈[n], define to be the set of codewords with a b in the ith position. Then C is normal if there exists an i∈[n] such that for any v∈Q_n, the sum of the Hamming distances from v to and is at most 2R+1. We newly define what it means for an asymmetric covering code to be normal, and consider the worst-case asymptotic densities ν^*(R) and of constant radius R symmetric and asymmetric normal covering codes, respectively. Using a probabilistic deletion method, and analysis adapted from previous work by Krivelevich, Sudakov, and Vu, we show that and , giving evidence that minimum size constant radius covering codes could still be normal.     

Maximal order codes over number fields

We present constructions of codes obtained from maximal orders over number fields. Particular cases include codes from algebraic number fields by Lenstra and Guruswami, codes from units of the ring of integers of number fields, and codes from both additive and multiplicative structures of maximal orders in central simple division algebras. The parameters of interest are the code rate and the minimum Hamming distance. An asymptotic study reveals several families of asymptotically good codes.     

Harder–Narasimhan theory for linear codes (with an appendix on Riemann–Roch theory)

In this text we develop some aspects of Harder–Narasimhan theory, slopes, semistability and canonical filtration, in the setting of combinatorial lattices. Of noticeable importance is the Harder–Narasimhan structure associated to a Galois connection between two lattices. It applies, in particular, to matroids.We then specialize this to linear codes. This could be done from at least three different approaches: using the sphere-packing analogy, or the geometric view, or the Galois connection construction just introduced. A remarkable fact is that these all lead to the same notion of semistability and canonical filtration. Relations to previous propositions toward a classification of codes, and to Wei's generalized Hamming weight hierarchy, are also discussed.Last, we study the two important questions of the preservation of semistability (or more generally the behavior of slopes) under duality, and under tensor product. The former essentially follows from Wei's duality theorem for higher weights—and its matroid version—which we revisit in an appendix, developing analogues of the Riemann–Roch, Serre duality, Clifford, and gap and gonality sequence theorems. Likewise the latter is closely related to the bound on higher weights of a tensor product, conjectured by Wei and Yang, and proved by Schaathun in the geometric language, which we reformulate directly in terms of codes. From this material we then derive semistability of tensor product.     

Some remarks concerning kissing numbers,blocking numbers and covering numbers

This article shows an inequality concerning blocking numbers and Hadwiger's covering numbers and presents a strange phenomenon concerning kissing numbers and blocking numbers. As a simple corollary, we can improve the known upper bounds for Hadwiger's covering numbers ford-dimensional centrally symmetric convex bodies to 3 ^d –1.     

The view-obstruction problem for spheres in ℝ5

In the view-obstruction problem, congruent, closed convex bodies centred at the points in ⁿ are expanded uniformly until they block all rays from the origin into the open positive cone. The central problem is to determine the minimal blocking size. In the case of spheres of diameter 1 and cubes of side 1 these values are known forn=2, 3 and 4. Here we show that in ⁵, this value for the sphere of diameter 1 is .     

Riemann-Roch spaces of the Hermitian function field with applications to algebraic geometry codes and low-discrepancy sequences

This paper is concerned with two applications of bases of Riemann-Roch spaces. In the first application, we define the floor of a divisor and obtain improved bounds on the parameters of algebraic geometry codes. These bounds apply to a larger class of codes than that of Homma and Kim (J. Pure Appl. Algebra 162 (2001) 273). Then we determine explicit bases for large classes of Riemann-Roch spaces of the Hermitian function field. These bases give better estimates on the parameters of a large class of m-point Hermitian codes. In the second application, these bases are used for fast implementation of Xing and Niederreiter's method (Acta. Arith. 72 (1995) 281) for the construction of low-discrepancy sequences.     

A remark on sets having the Steinhaus property

A point set satisfies the Steinhaus property if no matter how it is placed on a plane, it covers exactly one integer lattice point. Whether or not such a set exists, is an open problem. Beck has proved [1] that any bounded set satisfying the Steinhaus property is not Lebesgue measurable. We show that any such set (bounded or not) must have empty interior. As a corollary, we deduce that closed sets do not have the Steinhaus property, fact noted by Sierpinski [3] under the additional assumption of boundedness.     

Density of sets of natural numbers and the Lévy group

Let N denote the set of positive integers. The asymptotic density of the set A⊆N is d(A)=limn→∞|A∩[1,n]|/n, if this limit exists. Let AD denote the set of all sets of positive integers that have asymptotic density, and let SN denote the set of all permutations of the positive integers N. The group L^? consists of all permutations f∈SN such that A∈AD if and only if f(A)∈AD, and the group L^* consists of all permutations f∈L^? such that d(f(A))=d(A) for all A∈AD. Let be a one-to-one function such that d(f(N))=1 and, if A∈AD, then f(A)∈AD. It is proved that f must also preserve density, that is, d(f(A))=d(A) for all A∈AD. Thus, the groups L^? and L^* coincide.     

Exhaustive weakly wandering sequences

A sequence of integers {n_i : i = 0, 1…} is an exhaustive weakly wandering sequence for a transformation T if for some measurable set W, X=^∞_i=0TⁿⁱW(disj. We introduce a hereditary Property (H) for a sequence of integers associated with an infinite ergodic transformation T, and show that it is a sufficient condition for the sequence to be an exhaustive weakly wandering sequence for T. We then show that every infinite ergodic transformation admits sequences that possess Property (H), and observe that Property (H) is inherited by all subsequences of a sequence that possess it. As a corollary, we obtain an application to tiling the set of integers with infinite subsets.     

Covering and packing in ${\Bbb Z}^n$ and ${\Bbb R}^n$, (I)

Given a finite subset of an additive group such as or , we are interested in efficient covering of by translates of , and efficient packing of translates of in . A set provides a covering if the translates with cover (i.e., their union is ), and the covering will be efficient if has small density in . On the other hand, a set will provide a packing if the translated sets with are mutually disjoint, and the packing is efficient if has large density. In the present part (I) we will derive some facts on these concepts when , and give estimates for the minimal covering densities and maximal packing densities of finite sets . In part (II) we will again deal with , and study the behaviour of such densities under linear transformations. In part (III) we will turn to . Authors’ address: Department of Mathematics, University of Colorado at Boulder, Campus Box 395, Boulder, Colorado 80309-0395, USA The first author was partially supported by NSF DMS 0074531.     

Conservative weightings and ear-decompositions of graphs

A subsetJ of edges of a connected undirected graphG=(V, E) is called ajoin if |CJ||C|/2 for every circuitC ofG. Answering a question of P. Solé and Th. Zaslavsky, we derive a min-max formula for the maximum cardinality of a joint ofG. Namely, =(+|V|–1)/2 where denotes the minimum number of edges whose contraction leaves a factor-critical graph.To study these parameters we introduce a new decomposition ofG, interesting for its own sake, whose building blocks are factor-critical graphs and matching-covered bipartite graphs. We prove that the length of such a decomposition is always and show how an optimal join can be constructed as the union of perfect matchings in the building blocks. The proof relies on the Gallai-Edmonds structure theorem and gives rise to a polynomial time algorithm to construct the optima in question.     

Optimal tristance anticodes in certain graphs

For z₁,z₂,z₃∈Zⁿ, the tristance d₃(z₁,z₂,z₃) is a generalization of the L₁-distance on Zⁿ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeA_d of diameter d is a subset of Zⁿ with the property that d₃(z₁,z₂,z₃)?d for all z₁,z₂,z₃∈A_d. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z² for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z² where d(z₁,z₂)=1 if z₁,z₂ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z² is replaced by the hexagonal lattice A₂. We also investigate optimal tristance anticodes in Z³ and optimal quadristance anticodes in Z², and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go.     

On the Use of Cellular Automata in Symmetric Cryptography

In this work, pseudorandom sequence generators based on finite fields have been analyzed from the point of view of their cryptographic application. In fact, a class of nonlinear sequence generators has been modelled in terms of linear cellular automata. The algorithm that converts the given generator into a linear model based on automata is very simple and is based on the concatenation of a basic structure. Once the generator has been linearized, a cryptanalytic attack that exploits the weaknesses of such a model has been developed. Linear cellular structures easily model sequence generators with application in stream cipher cryptography.Work supported by Ministerio de Educación y Ciencia (Spain), Projects SEG2004-02418 and SEG2004-04352-C04-03.     

Some properties of the riesz charge associated with a δ-subharmonic function

The first property is a refinement of earlier results of Ch. de la Vallée Poussin, M. Brelot, and A. F. Grishin. Let w=u–v with u, v superharmonic on a suitable harmonic space (for example an open subset of R ⁿ ), and let [w]=[u]–[v] denote the associated Riesz charge. If w0, and if E denotes the set of those points of at which the lim inf of w in thefine topology is 0, then the restriction of [w] to E is 0. Another property states that, if e denotes a polar subset of such that the fine lim inf of |w| at each point of e is finite, then the restriction of [w] to e is 0.     

Solution-free sets for linear equations

We study the maximum size and the structure of sets of natural numbers which contain no solution of one or more linear equations. Thus, for every natural i and k?2, we find the minimum α=α(i,k) such that if the upper density of a strongly k-sum-free set is at least α, then A is contained in a maximal strongly k-sum-free set which is a union of at most i arithmetic progressions. We also determine the maximum density of sets of natural numbers without solutions to the equation x=y+az, where a is a fixed integer.     

Dense edge-magic graphs and thin additive bases

A graph G of order n and size m is edge-magic if there is a bijection l:V(G)∪E(G)→[n+m] such that all sums l(a)+l(b)+l(ab), ab∈E(G), are the same. We present new lower and upper bounds on M(n), the maximum size of an edge-magic graph of order n, being the first to show an upper bound of the form . Concrete estimates for ε can be obtained by knowing s(k,n), the maximum number of distinct pairwise sums that a k-subset of [n] can have.So, we also study s(k,n), motivated by the above connections to edge-magic graphs and by the fact that a few known functions from additive number theory can be expressed via s(k,n). For example, our estimate

     

A geometric perspective on counting non-negative integer solutions and combinatorial identities

We consider the effect of constraints on the number of non-negative integer solutions of x+y+z = n, relating the number of solutions to linear combinations of triangular numbers. Our approach is geometric and may be viewed as an introduction to proofs without words. We use this geometrical perspective to prove identities by counting the number of solutions in two different ways, thereby combining combinatorial proofs and proofs without words.     

A Weighted Erdős-Ginzburg-Ziv Theorem

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct so that they can be considered as sets. If S is a sequence of m+n−1 elements from a finite abelian group G of order m and exponent k, and if is a sequence of integers whose sum is zero modulo k, then there exists a rearranged subsequence of S such that . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when m = n and w_i = 1 for all i, and confirms a conjecture of Y. Caro. Furthermore, we in part verify a related conjecture of Y. Hamidoune, by showing that if S has an n-set partition A=A₁, . . .,A_n such that |w_iA_i| = |A_i| for all i, then there exists a nontrivial subgroup H of G and an n-set partition A′ =A′₁, . . .,A′_n of S such that and for all i, where w_iA_i={w_ia_i |a_i∈A_i}.     

Maximal Collections of Intersecting Arithmetic Progressions

Let N _t (k) be the maximum number of k-term arithmetic progressions of real numbers, any two of which have t points in common. We determine N ₂(k) for prime k and all large k, and give upper and lower bounds for N _t (k) when t 3.* Research supported in part by NSF grant DMS-0070618.