On Intersection Problem for Perfect Binary Codes

The main result is that to any even integer q in the interval 0 ≤ q ≤ 2^{n+1-2log(n+1)}, there are two perfect codes C₁ and C₂ of length n = 2^m − 1, m ≥ 4, such that |C₁ ∩ C₂| = q.     

Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube

A snake-in-the-box code (or snake) of word length n is a simple circuit in an n-dimensional cube Q _n , with the additional property that any two non-neighboring words in the circuit differ in at least two positions. To construct such snakes a straightforward, non-recursive method is developed based on special linear codes with minimum distance 4. An extension of this method is used for the construction of covers of Q _n consisting of 2 ^m-1 vertex-disjoint snakes, for 2 ^m-1 < n ≤ 2 ^m . These covers turn out to have a symmetry group of order 2 ^m .      

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 Classification of Some Perfect Codes

Perfect 1-error correcting codes C in Z ₂ ⁿ , where n=2 ^m–1, are considered. Let ; denote the linear span of the words of C and let the rank of C be the dimension of the vector space . It is shown that if the rank of C is n–m+2 then C is equivalent to a code given by a construction of Phelps. These codes are, in case of rank n–m+2, described by a Hamming code H and a set of MDS-codes D _h , h H, over an alphabet with four symbols. The case of rank n–m+1 is much simpler: Any such code is a Vasil'ev code.     

The approximation of functions of many variables by their Féjér sums

We construct elliptic Féjér polynomials K_n(x) of m variables. We prove some of their properties: a) the Féjér polynomials are positive on the m-dimensional torus T^m, K_n(x)0, b) (x)=o(n^–1), as n, c) we calculate their norms in the spaces L[T^m] and C[T^m]. We estimate the deviation of the Féjér sum _n(x,f) from the functionf(x). For the space C[T^m]: where c_,m c_1,m are constants.Translated from Matematicheskie Zametki, Vol. 13, No. 6, pp. 817–828, June, 1973.In conclusion, the author wishes to express his gratitude to S. B. Stechkin for help with the paper.     

Cyclic Codes over the Integers Modulop

The purpose of this paper is twofold. First, we generalize the results of Pless and Qian and those of Pless, Solé, and Qian for cyclic ₄-codes to cyclic _p^m-codes. Second, we establish connections between this new development and the results on cyclic _p^m-codes obtained by Calderbank and Sloane. We produce generators for the cyclic _p^m-codes which are analogs to those for cyclic ₄-codes. We show that these may be used to produce a single generator for such codes. In particular, this proves that the ringR_n= _p^m[x]/(xⁿ− 1) is principal, a result that had been previously announced with an incorrect proof. Generators for dual codes of cyclic _p^m-codes are produced from the generators of the corresponding cyclic _p^m-codes. In addition, we also obtain generators for the cyclicp^m-ary codes induced from the idempotent generators for cyclicp-ary codes.     

关于Hall问题

Hall在T型差集的研究中,产生了如下问题:方程 q~m=p~n 2,p,q是素数,m>1,n>1,(1)除开p=5,n=2,q=3,m=3以外,是否还有其他的解?这是一个未决问题。最近,孙琦和周小明在研究不定方程 a~x b~y=c~z,a,b,c是不同的素数,max(a,b,c)=19时,顺便给出了方程(1)的一个结果,即     

Ovoids and spreads of finite classical polar spaces

LetP be a finite classical polar space of rankr, r2. An ovoidO ofP is a pointset ofP, which has exactly one point in common with every totally isotropic subspace of rankr. It is proved that the polar spaceW _n (q) arising from a symplectic polarity ofPG(n, q), n odd andn > 3, that the polar spaceQ(2n, q) arising from a non-singular quadric inPG(2n, q), n > 2 andq even, that the polar space Q^–(2n + 1,q) arising from a non-singular elliptic quadric inPG(2n + 1,q), n > 1, and that the polar spaceH(n,q ²) arising from a non-singular Hermitian variety inPG(n, q ²)n even andn > 2, have no ovoids.LetS be a generalized hexagon of ordern (1). IfV is a pointset of order n³ + 1 ofS, such that every two points are at distance 6, thenV is called an ovoid ofS. IfH(q) is the classical generalized hexagon arising fromG ₂ (q), then it is proved thatH(q) has an ovoid iffQ(6, q) has an ovoid. There follows thatQ(6, q), q=3^2h+1, has an ovoid, and thatH(q), q even, has no ovoid.A regular system of orderm onH(3,q ²) is a subsetK of the lineset ofH(3,q ²), such that through every point ofH(3,q ²) there arem (> 0) lines ofK. B. Segre shows that, ifK exists, thenm=q + 1 or (q + l)/2.If m=(q + l)/2,K is called a hemisystem. The last part of the paper gives a very short proof of Segre's result. Finally it is shown how to construct the 4-(11, 5, 1) design out of the hemisystem with 56 lines (q=3).     

On the diophantine equationD 1 x 2+D 2 m =4y n

For anyD ₁,D ₂, leth(-D ₁ D ₂) denote the class number of the imaginary quadratic field . In this paper we prove that the equationD ₁ x ²+D ₂ ^m =4y ⁿ.D ₁,D ₂,x, y, m, n, gcd (D ₁x,D ₂y=1,2m,n an odd prime,nh(-D ₁ D ₂, has only a finite number of solutions (D ₁,D ₂,x,y,m,n) withn>5. Moreover, the solutions satisfy 4y ⁿ相似文献   

Some cyclic codes of length 2<Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Explicit expressions for 4n + 2 primitive idempotents in the semi-simple group ring $R_{2p^{n}}\equiv \frac{GF(q)[x]}{p and q are distinct odd primes; n ≥ 1 is an integer and q has order \fracf(2pⁿ)2{\frac{\phi(2p^{n})}{2}} modulo 2p ⁿ . The generator polynomials, the dimension, the minimum distance of the minimal cyclic codes of length 2p ⁿ generated by these 4n + 2 primitive idempotents are discussed. For n = 1, the properties of some (2p, p) cyclic codes, containing the above minimal cyclic codes are analyzed in particular. The minimum weight of some subset of each of these (2p, p) codes are observed to satisfy a square root bound.     

On nonsystematic perfect codes over finite fields

The nonsystematic perfect q-ary codes over finite field F _q of length n = (q ^m − 1)/(q − 1) are constructed in the case when m ≥ 4 and q ≥ 2 and also when m = 3 and q is not prime. For q ≠ 3, 5, these codes can be constructed by switching seven disjoint components of the Hamming code H _q ⁿ ; and, for q = 3, 5, eight disjoint components.     

Quaternionic Starters

Let m be an integer, m 2 and set n = 2^m. Let G be a non-cyclic group of order 2n admitting a cyclic subgroup of order n. We prove that G always admits a starter and so there exists a one–factorization of K_2n admitting G as an automorphism group acting sharply transitively on vertices. For an arbitrary even n > 2 we also show the existence of a starter in the dicyclic group of order 2n.Research performed within the activity of INdAM–GNSAGA with the financial support of the Italian Ministry MIUR, project Strutture Geometriche, Combinatoria e loro Applicazioni     

Induced operators on symmetry classes of tensors

LetV be ann-dimensional inner product space,T _i ,i=1,...,k, k linear operators onV, H a subgroup ofS _m (the symmetric group of degreem), a character of degree 1 andT a linear operator onV. Denote byK(T) the induced operator ofT onV (H), the symmetry class of tensors associated withH and . This note is concerned with the structure of the setK _{, m} ^H (T₁,...,T_k) consisting of all numbers of the form traceK(T ₁ U ₁...T _k U _k ) whereU _i ,i=1,...k vary over the group of all unitary operators onV. For V=ⁿ or ⁿ, it turns out thatK _{, m} ^H (T₁,...,T_k) is convex whenm is not a multiple ofn. Form=n, there are examples which show that the convexity of _{, m} ^H (T₁,...,T_k) depends onH and .The author wishes to express his thanks to Dr. Yik-Hoi Au-Yeung for his valuable advice and encouragement.     

The complexity of many cells in arrangements of planes and related problems

We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m ^2/3 n logn +n ²); we can calculatem such cells specified by a point in each, in worst-case timeO(m ^2/3 n log³ n+n ² logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m ^2/3 n logn+n ²), but this number is onlyO(m ^3/5– n ^4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m ^3/4– n ^3/4+3 +m) log² n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m ^3/4– n ^3/4+3 +m] log² n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m ^2/3 n ^d/3 logn+n ^d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. An abstract of this paper has appeared in theProceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147.     

The evaluation of Tornheim double sums. Part 2

We provide an explicit formula for the Tornheim double series T(a,0,c) in terms of an integral involving the Hurwitz zeta function. For integer values of the parameters, a=m, c=n, we show that in the most interesting case of even weight N:=m+n the Tornheim sum T(m,0,n) can be expressed in terms of zeta values and the family of integrals

The Embedding Theorem for Cantor Varieties

Let m and n be fixed integers, with 1 m < n. A Cantor variety C _m,n is a variety of algebras with m n-ary and n m-ary basic operations which is defined in a signature ={g₁,...,g_m,f₁,...,f_n} by the identities f_ig₁x₁,...,x_n),...,g_mx₁,...,x_n) = x_i, _i=1,...,n, g_jf₁x₁,...,x_m),...,f_nx₁,...,x_m)) = x_j, _j=1,...,m. We prove the following: (a) every partial C _m,n-algebra A is isomorphically embeddable in the algebra G= A; S(A) of C _m,n; (b) for every finitely presented algebra G= A; S in C _m,n, the word problem is decidable; (c) for finitely presented algebras in _{C m}, the occurrence problem is decidable; (d) _{C m,n} has a hereditarily undecidable elementary theory.     

Interpolating them-th power ofx at the zeros of then-th Chebyshev-polynomial yields an almost best Chebyshev-approximation

LetX={x ₁,x ₂,..., _n }I=[–1, 1] and . ForfC ₁(I) definef* byf–p _f =f*, wherep _f denotes the interpolation-polynomial off with respect toX. We state some properties of the operatorf f*. In particular, we treat the case whereX consists of the zeros of the Chebyshev polynomialT _n (x) and obtain x ^m –p _x ^m8eE _n–1(x ^m ), whereE _n–1(f) denotes the sup-norm distance fromf to the polynomials of degree less thann. Finally we state a lower estimate forE _n (f) that omits theassumptionf ⁽ⁿ⁺¹⁾>0 in a similar estimate of Meinardus.     

Combinatorial complexity bounds for arrangements of curves and spheres

We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is (m ^2/3 n ^2/3 +n), and that it isO(m ^2/3 n ^2/3 (n) +n) forn unit-circles, where(n) (and later(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m ^3/5 n ^4/5 (n) +n). The same bounds (without the(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m ^4/7 n ^9/7 (m, n) +n ²), in general, andO(m ^3/4 n ^3/4 (m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m ^3/2 (m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given.The research of the second author was supported by the National Science Foundation under Grant CCR-8714565. Work by the fourth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a research grant from the NCRD, the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988.     

REPRESENTATIONS OF A CLASS OF DRINFELD'S DOUBLES

Let k be a field and A_n(ω) be the Taft's n²-dimensional Hopf algebra. When n is odd, the Drinfeld quantum double D(A_n(ω)) of A_n(ω) is a ribbon Hopf algebra. In the previous articles, we constructed an n₄-dimensional Hopf algebra H_n(p, q) which is isomorphic to D(A_n(ω)) if p ≠ 0 and q = ω^?1 , and studied the irreducible representations of H_n(1, q) and the finite dimensional representations of H₃(1, q). In this article, we examine the finite-dimensional representations of H_n(l q), equivalently, of D(A_n(ω)) for any n ≥ 2. We investigate the indecomposable left H_n(1, q)-module, and describe the structures and properties of all indecomposable modules and classify them when k is algebraically closed. We also give all almost split sequences in mod H_n(1, q), and the Auslander-Reiten-quiver of H_n(1 q).     

Ramsey functions involving with large

For fixed integers m,k2, it is shown that the k-color Ramsey number r_k(K_m,n) and the bipartite Ramsey number b_k(m,n) are both asymptotically equal to k^mn as n→∞, and that for any graph H on m vertices, the two-color Ramsey number is at most (1+o(1))n^m+1/(logn)^m-1. Moreover, the order of magnitude of is proved to be n^m+1/(logn)^m if H≠K_m as n→∞.