A refinement of Cusick-Cheon bound for the second order binary Reed-Muller code

We prove a stronger form of the conjectured Cusick-Cheon lower bound for the number of quadratic balanced Boolean functions. We also prove various asymptotic results involving B(k,m), the number of balanced Boolean functions of degree ≤k in m variables, in the case k=2. Finally, we connect our results for k=2 with the (still unproved) conjectures of Cusick-Cheon for the functions B(k,m) with k>2.     

Covering the hypercube with a bounded number of disjoint snakes

We present a construction of an induced cycle in then-dimensional hypercubeI[n] (n2), and a subgroup _n ofI[n] considered as the group ₂ ⁿ , such that | _n |16 and the induced cycle uses exactly one element of every coset of _n . This proves that for anyn2 the vertices ofI[n] can be covered using at most 16 vertex-disjoint induced cycles.     

ContributionsOn binary k-paving matroids and Reed-Muller codes

A matroid M of rank r k is k-paving if all of its circuits have cardinality exceeding r − k. In this paper, we develop some basic results concerning k-paving matroids and their connections with codes. Also, we determine all binary 2-paving matroids.     

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

On the second weight of generalized Reed-Muller codes

Not much is known about the weight distribution of the generalized Reed-Muller code RM _q (s,m) when q > 2, s > 2 and m ≥ 2. Even the second weight is only known for values of s being smaller than or equal to q/2. In this paper we establish the second weight for values of s being smaller than q. For s greater than (m – 1)(q – 1) we then find the first s + 1 – (m – 1)(q–1) weights. For the case m = 2 the second weight is now known for all values of s. The results are derived mainly by using Gröbner basis theoretical methods.     

广义Gray码及其在数字图像置乱中的应用

以图像信息安全问题为背景，讨论了广义Gray码及其在数字图像中的置乱作用，推广了丁玮等人（1999年）的相关结果。给出了图像置乱变换的周期，得到了周期性的一个充分必要条件。     

Further results on the covering radius of small codes

The minimum number of codewords in a code with t ternary and b binary coordinates and covering radius R is denoted by K(t,b,R). In the paper, necessary and sufficient conditions for K(t,b,R)=M are given for M=6 and 7 by proving that there exist exactly three families of optimal codes with six codewords and two families of optimal codes with seven codewords. The cases M?5 were settled in an earlier study by the same authors. For binary codes, it is proved that K(0,2b+4,b)?9 for b?1. For ternary codes, it is shown that K(3t+2,0,2t)=9 for t?2. New upper bounds obtained include K(3t+4,0,2t)?36 for t?2. Thus, we have K(13,0,6)?36 (instead of 45, the previous best known upper bound).     

There exist Steiner triple systems of order 15 that do not occur in a perfect binary one‐error‐correcting code

The codewords at distance three from a particular codeword of a perfect binary one‐error‐correcting code (of length 2^m?1) form a Steiner triple system. It is a longstanding open problem whether every Steiner triple system of order 2^m?1 occurs in a perfect code. It turns out that this is not the case; relying on a classification of the Steiner quadruple systems of order 16 it is shown that the unique anti‐Pasch Steiner triple system of order 15 provides a counterexample. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 465–468, 2007     

New upper bounds on the minimum size of covering designs

Let D = {B₁, B₂,…, B_b} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998     

Factorizations of Self-similar Groups Associated to the First Grigorchuk Group

In this paper, we construct two self-similar groups factorizable by their locally finite 2-subgroups, generators of which are constructed from the generators of the first Grigorchuk group. Both groups contain the first Grigorchuk group, the second also contains the binary adding machine. The first group is a 2-group but not locally finite and the second group is neither locally finite nor a 2-group. Therefore each of them is a new example providing a negative answer to well-known solved problems. Surprisingly, definitions of both groups involve the Gray code.     

On the size of the symmetry group of a perfect code

It is shown that for every nonlinear perfect code C of length n and rank r with n−log(n+1)+1≤r≤n−1, where denotes the group of symmetries of C. This bound considerably improves a bound of Malyugin.     

Gray codes for column-convex polyominoes and a new class of distributive lattices

We introduce the problem of polyomino Gray codes, which is the listing of all members of certain classes of polyominoes such that successive polyominoes differ by some well-defined closeness condition (e.g., the movement of one cell). We discuss various closeness conditions and provide several Gray codes for the class of column-convex polyominoes with a fixed number of cells in each column. For one of our closeness conditions, a natural new class of distributive lattice arises: the partial order is defined on the set of m-tuples [S₁]×[S₂]××[S_m], where each S_i>1 and [S_i]={0,1,…,S_i−1}, and the cover relations are (p₁,p₂,…,p_m)(p₁+1,p₂,…,p_m) and (p₁,p₂,…,p_j,p_j+1,…,p_m)(p₁,p₂,…,p_j−1,p_j+1+1,…,p_m). We also discuss some properties of this lattice.     

Gray codes for non-crossing partitions and dissections of a convex polygon

In this paper we develop Gray codes for two families of geometric objects: non-crossing partitions and dissections of a convex polygon by means of non-crossing diagonals.     

None of the coronoid systems can be isometrically embedded into a hypercube

A graph that can be isometrically embedded into a hypercube is called a partial cube (or binary Hamming graph). Klavžar, Gutman and Mohar [S. Klavžar, I. Gutman, B. Mohar, Labeling of benzenoid systems which reflects the vertex-distance relations, J. Chem. Inf. Comput. Sci. 35 (1995) 590–593] showed that all benzenoid systems are partial cubes. In this article we show that none of the coronoid systems (benzenoid systems with “holes”) is a partial cube.     

The characters of some 2-blocks of the babymonster,its covering group and the monster

The double of a free nonabelian group over a subgroup of finite index greater than two is shown not to be coherent, answering a question of C. T. C. Wall.     

Meeting the Welch and Karystinos-Pados Bounds on DS-CDMA Binary Signature Sets

The Welch lower bound on the total-squared-correlation (TSC) of binary signature sets is loose for binary signature sets whose length L is not a multiple of 4. Recently Karystinos and Pados [6,7] developed new bounds that are better than the Welch bound in those cases, and showed how to achieve the bounds with modified Hadamard matrices except in a couple of cases. In this paper, we study the open cases.     

Sampling Sets and Quadrature Formulae on the Rotation Group

In this paper, we construct sampling sets over the rotation group SO(3). The proposed construction is based on a parameterization, which reflects the product nature ² × ¹ of SO(3) very well, and leads to a spherical Pythagorean-like formula in the parameter domain. We prove that by using uniformly distributed points on ² and ¹, we obtain uniformly sampling nodes on the rotation group SO(3). Furthermore, quadrature formulae on ² and ¹ lead to quadratures on SO(3), as well. For scattered data on SO(3), we give a necessary condition on the mesh norm such that the sampling nodes possess nonnegative quadrature weights. We propose an algorithm for computing the quadrature weights for scattered data on SO(3) based on fast algorithms. We confirm our theoretical results with examples and numerical tests.