Generalized MacWilliams identities and their applications to perfect binary codes

We present generalized MacWilliams identities for binary codes. These identities naturally lead to the concepts of the local weight distribution of a binary code with respect to a word u and its MacWilliams u-transform. In the case that u is the all-one word, these ones correspond to the weight distribution of a binary code and its MacWilliams transform, respectively. We identify a word v with its support, and consider v as a subset of {1, 2,..., n}. For two words u,w of length n such that their intersection is the empty set, define the u-face centered at w to be the set . A connection between our MacWilliams u-transform and the weight distribution of a binary code in the u-face centered at the zero word is presented. As their applications, we also investigate the properties of a perfect binary code. For a perfect binary code C, the main results are as follows: first, it is proved that our local weight distribution of C is uniquely determined by the number of codewords of C in the orthogonal u-face centered at the zero word. Next, we give a direct proof for the known result, concerning the weight distribution of a coset of C in the u-face centered at the zero word, by A. Y. Vasil’eva without using induction. Finally, it is proved that the weight distribution of C in the orthogonal u-face centered at w is uniquely determined by the codewords of C in the u-face centered at the zero word.      

A construction of mutually disjoint Steiner systems from isomorphic Golay codes

It is well known that the extended binary Golay [24,12,8] code yields 5-designs. In particular, the supports of all the weight 8 codewords in the code form a Steiner system S(5,8,24). In this paper, we give a construction of mutually disjoint Steiner systems S(5,8,24) by constructing isomorphic Golay codes. As a consequence, we show that there exists at least 22 mutually disjoint Steiner systems S(5,8,24). Finally, we prove that there exists at least 46 mutually disjoint 5-(48,12,8) designs from the extended binary quadratic residue [48,24,12] code.     

An Enumeration of Binary Self-Dual Codes of Length 32

A binary self-dual code of length 2k is a (2k, k) binary linear code C with the property that every pair of codewords in C are orthogonal. Two self-dual codes, C ₁ and C ₂, are equivalent if and only if there is a permutation of the coordinates of C ₁ that takes C ₁ into C ₂. The automorphism group of a binary code C is the set of all permutations of the coordinates of C that takes C into itself.The main topic of this paper is the enumeration of inequivalent binary self-dual codes. We have developed algorithms that will take lists of inequivalent small codes and produce lists of larger codes where each inequivalent code occurs only a few times. We have defined a canonical form for codes that allowed us to eliminate the overenumeration. So we have lists of inequivalent binary self-dual codes of length up to 32. The enumeration of the length 32 codes is new. Our algorithm also finds the size of the automorphism group so that we can compute the number of distinct binary self-dual codes for a specific length. This number can also be found by counting and matches our total.     

Maximal Flow in Branching Trees and Binary Search Trees

A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal flow that can pass through a given path is the minimun capacity on the path. Antal and Krapivski (Phys Rev E 74:051110, 2006) study the distribution for the maximal flow from the root to a leaf in the case of a deterministic binary tree with independent and identically distributed random capacities. In this paper their result is extended to three classes of trees with a random number of children and dependent random capacities: binary trees with general capacities distribution, branching trees with exchangeable capacities and random binary search trees.     

An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable

The 0–1 linear knapsack problem with a single continuous variable (KPC) is an extension of the binary knapsack problem (KP). It is an NP-hard problem. In this paper, we show that KPC can be reduced to KP and a pseudo-knapsack problem (PKP), which is similar to the traditional knapsack problem except that the profits of items may be non-positive, and the weight sum has two sided limits on capacity. We use the Dynamic Programming algorithm COMBO (Martello et al., Manag Sci 45(3):414–424, 1999) to solve KP, and modify the branch and bound method EXPKNAP (Pisinger, Eur J Oper Res 87:175–187, 1995) for KP to solve the PKP. Numerical experiments show the efficiency of our method.     

Weak Reflections and Weak Factorization Systems

We describe a one-to-one correspondence between saturated weak factorization systems and weak reflections in categories C\mathcal{C} with finite products. This actually extends to an adjunction between the category of natural weak factorization systems on C\mathcal{C} (in the sense of Grandis and Tholen, Arch Math 42:397–408, 2006, and Garner, arXiv preprint, 2007) and the category of monads on C\mathcal{C}. Explicit comparisons are made with the parallel result of Cassidy et al. (J Aust Math Soc 38:287–329, 1985), linking factorization systems and reflective subcategories.     

The Euclidean Distortion of the Lamplighter Group

We show that the cyclic lamplighter group C ₂ ? C _n embeds into Hilbert space with distortion $\mathrm{O}(\sqrt{\log n})We show that the cyclic lamplighter group C ₂ ≀ C _n embeds into Hilbert space with distortion O(?{logn})\mathrm{O}(\sqrt{\log n}) . This matches the lower bound proved by Lee et al. (Geom. Funct. Anal., 2009), answering a question posed in that paper. Thus, the Euclidean distortion of C ₂ ≀ C _n is \varTheta(?{logn})\varTheta(\sqrt{\log n}) . Our embedding is constructed explicitly in terms of the irreducible representations of the group. Since the optimal Euclidean embedding of a finite group can always be chosen to be equivariant, as shown by Aharoni et al. (Isr. J. Math. 52(3):251–265, 1985) and by Gromov (see de Cornulier et. al. in Geom. Funct. Anal., 2009), such representation-theoretic considerations suggest a general tool for obtaining upper and lower bounds on Euclidean embeddings of finite groups.     

On approximation of meromorphic functions having index-pair (<Emphasis Type="Italic">p</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)

The purpose of this paper is to generalize the results obtained by Winiarski (Ann. Polon. Math. 29:259–273, 1970) and Kasana and Kumar (Publ. Mat. 38:255–267, 1994) for the M ₀(C) of all entire functions onto the class M _m (C), m ≥ 0 of all meromorphic functions with exactly m poles on the complex plane C.     

Extensions and renormalized traces

It has been shown by Nistor (Doc Math J DMV 2:263–295, 1997) that given any extension of associative algebras over \mathbb C{\mathbb C}, the connecting morphism in periodic cyclic homology is compatible, under the Chern–Connes character, with the index morphism in lower algebraic K-theory. The proof relies on the abstract properties of cyclic theory, essentially excision, which does not provide explicit formulas a priori. Avoiding the use of excision, we explain in this article how to get explicit formulas in a wide range of situations. The method is connected to the renormalization procedure introduced in our previous work on the bivariant Chern character for quasihomomorphisms Perrot (J Geom Phys 60:1441–1473, 2010), leading to “local” index formulas in the sense of non-commutative geometry. We illustrate these principles with the example of the classical family index theorem: we find that the characteristic numbers of the index bundle associated to a family of elliptic pseudodifferential operators are expressed in terms of the (fiberwise) Wodzicki residue.     

Integral quadratic forms and Dirichlet series

A Dirichlet series with multiplicative coefficients has an Euler product representation. In this paper we consider the special case where these coefficients are derived from the numbers of representations of an integer by an integral quadratic form. At first we suppose this quadratic form to be positive definite. In general the representation numbers are not multiplicative. Instead we consider the average number of representations over all classes in the genus of the quadratic form. And we consider only representations of integers of the form tk ² with t square-free. If we divide the average representation number for these integers by a suitable factor, we do get a multiplicative function. Using results from Siegel (Ann. Math. 36:527–606, 1935), we derive a uniform expression for the Euler product expansion of the corresponding Dirichlet series. As a special case, we consider the standard quadratic form in n variables corresponding to the identity matrix. Here we use results from Shimura (Am. J. Math. 124:1059–1081, 2002). For 2≤n≤8, the genus of this particular quadratic form contains only one class, and this leads to a rather simple expression for the Dirichlet series, where the coefficients are just the number of representations of a square as the sum of n squares. Finally we consider the indefinite case, where we can get results similar to the definite case.     

Autour des formes quadratiques indécomposables de l’image de l’homomorphisme W(F) → W(F(φ))

Let F be a field of characteristic not 2. In this article, we treat the quadratic forms of Im(W(F) → W(F(φ))) which are indecomposable, i.e., those which are not isometric to a sum of two nonzero forms of this image, where W(F) is the Witt ring of F-quadratic forms, and F(φ) is the function field of the affine quadric given by φ. This is related to the descent problems studied in [12, 14]. More precisely, we will focus on indecomposable quadratic forms of minimal dimension, which we detail for φ of dimension less than or equal to 8. We also include other related results.     

A Characterization of the Riesz Probability Distribution

Bobecka and Wesolowski (Studia Math. 152:147–160, [2002]) have shown that, in the Olkin and Rubin characterization of the Wishart distribution (see Casalis and Letac in Ann. Stat. 24:763–786, [1996]), when we use the division algorithm defined by the quadratic representation and replace the property of invariance by the existence of twice differentiable densities, we still have a characterization of the Wishart distribution. In the present work, we show that when we use the division algorithm defined by the Cholesky decomposition, we get a characterization of the Riesz distribution.     

A census of highly symmetric combinatorial designs

As a consequence of the classification of the finite simple groups, it has been possible in recent years to characterize Steiner t-designs, that is t-(v,k,1) designs, mainly for t=2, admitting groups of automorphisms with sufficiently strong symmetry properties. However, despite the finite simple group classification, for Steiner t-designs with t>2 most of these characterizations have remained long-standing challenging problems. Especially, the determination of all flag-transitive Steiner t-designs with 3≤t≤6 is of particular interest and has been open for about 40 years (cf. Delandtsheer (Geom. Dedicata 41, p. 147, 1992 and Handbook of Incidence Geometry, Elsevier Science, Amsterdam, 1995, p. 273), but presumably dating back to 1965). The present paper continues the author’s work (see Huber (J. Comb. Theory Ser. A 94, 180–190, 2001; Adv. Geom. 5, 195–221, 2005; J. Algebr. Comb., 2007, to appear)) of classifying all flag-transitive Steiner 3-designs and 4-designs. We give a complete classification of all flag-transitive Steiner 5-designs and prove furthermore that there are no non-trivial flag-transitive Steiner 6-designs. Both results rely on the classification of the finite 3-homogeneous permutation groups. Moreover, we survey some of the most general results on highly symmetric Steiner t-designs.      

The Weight Distribution of C 5(1, n)

In [2] the codes C _q (r,n) over were introduced. These linear codes have parameters , can be viewed as analogues of the binary Reed-Muller codes and share several features in common with them. In [2], the weight distribution of C ₃(1,n) is completely determined.In this paper we compute the weight distribution of C ₅(1,n). To this end we transform a sum of a product of two binomial coefficients into an expression involving only exponentials an Lucas numbers. We prove an effective result on the set of Lucas numbers which are powers of two to arrive to the complete determination of the weight distribution of C ₅(1,n). The final result is stated as Theorem 2.     

A Good Method of Combining Codes

Let q be an odd prime power, and suppose q?1 (mod8), Let C(q) and C(q)¹ be the two extended binary quadratic residue codes (QR codes) of length q+1, and let

$\text{T(q)={(a+x;b+x;a+b+x):a,b∈C(q),x∈C(q)}{}^1\text{}}$

. We establish a square root bound on the minimum weight in T(q). Since the same type of bound applies to C(q) and C(q)¹, this is a good method of combining codes.     

Parity patterns associated with lifts of Hecke groups

Let q be an odd prime, m a positive integer, and let Γ _m (q) be the group generated by two elements x and y subject to the relations x ^2m =y ^qm =1 and x ²=y ^q ; that is, Γ _m (q) is the free product of two cyclic groups of orders 2m respectively qm, amalgamated along their subgroups of order m. Our main result determines the parity behaviour of the generalized subgroup numbers of Γ _m (q) which were defined in Müller (Adv. Math. 153:118–154, 2000), and which count all the homomorphisms of index n subgroups of Γ _m (q) into a given finite group H, in the case when gcd (m,| H |)=1. This computation depends upon the solution of three counting problems in the Hecke group ℋ(q)=C ₂*C _q : (i) determination of the parity of the subgroup numbers of ℋ(q); (ii) determination of the parity of the number of index n subgroups of ℋ(q) which are isomorphic to a free product of copies of C ₂ and of C _∞; (iii) determination of the parity of the number of index n subgroups in ℋ(q) which are isomorphic to a free product of copies of C _q . The first problem has already been solved in Müller (Groups: Topological, Combinatorial and Arithmetic Aspects, LMS Lecture Notes Series, vol. 311, pp. 327–374, Cambridge University Press, Cambridge, 2004). The bulk of our paper deals with the solution of Problems (ii) and (iii). Research of C. Krattenthaler partially supported by the Austrian Science Foundation FWF, grant S9607-N13, in the framework of the National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.     

Codes with given distances

One of the main results says that ifC is a binary linear code of length 4t and of dimension greater than 2t, thenC contains a word of weight 2t and this bound is best possible. Several results of similar flavor are established both for linear and non-linear codes. For the proof a lemma introducing the binormal forms of binary matrices is needed. The results are applied to determine the coset chromatic number of Hadamard graphs, to solve a problem of Galvin and to give a short proof of a theorem of Gleason on self-dual doubly-even codes.     

Ring semigroups whose subsemigroups form a chain

A multiplicative semigroup S is called a ring semigroup if an addition may be defined on S so that (S,+,⋅) is a ring. Such semigroups have been well-studied in the literature (see Bell in Words, Languages and Combinatorics, pp. 24–31, World Scientific, Singapore, 1994; Jones in Semigroup Forum 47(1):1–6, 1993; Jones and Ligh in Semigroup Forum 17(2):163–173, 1979). In this note, we use Mihăilescu’s Theorem (formerly Catalan’s Conjecture) to characterize the ring semigroups whose subsemigroups containing 0 form a chain with respect to set inclusion.     

Distributive Lattices with a Generalized Implication: Topological Duality

In this paper we introduce the notion of generalized implication for lattices, as a binary function ⇒ that maps every pair of elements of a lattice to an ideal. We prove that a bounded lattice A is distributive if and only if there exists a generalized implication ⇒ defined in A satisfying certain conditions, and we study the class of bounded distributive lattices A endowed with a generalized implication as a common abstraction of the notions of annihilator (Mandelker, Duke Math J 37:377–386, 1970), Quasi-modal algebras (Celani, Math Bohem 126:721–736, 2001), and weakly Heyting algebras (Celani and Jansana, Math Log Q 51:219–246, 2005). We introduce the suitable notions of morphisms in order to obtain a category, as well as the corresponding notion of congruence. We develop a Priestley style topological duality for the bounded distributive lattices with a generalized implication. This duality generalizes the duality given in Celani and Jansana (Math Log Q 51:219–246, 2005) for weakly Heyting algebras and the duality given in Celani (Math Bohem 126:721–736, 2001) for Quasi-modal algebras.