A small embedding for partial even-cycle systems

Let m = 2k. We show that for some 0 ≤ ξ <1, a partial directed m-cycle system of order n can be embedded in a directed m-cycle system of order (mn)/2 + (2m² 1) √(8n + 1)/4 + 4m^{3 2} + 4 + 1/2. For fixed m, this is asymptotic in n to (mn)/2 and so for large n is roughly one-fourth the best known bound of 2mn + 1. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 205–215, 1999     

Semicyclic 4-GDDs and related two-dimensional optical orthogonal codes

The existence problem for a semicyclic group divisible design (SCGDD) of type m ⁿ with block size 4 and index unity, denoted by 4-SCGDD, has been studied for any odd integer m to construct a kind of two-dimensional optical orthogonal codes (2-D OOCs) with the AM-OPPW (at most one-pulse per wavelength) restriction. In this paper, the existence of a 4-SCGDD of type m ⁿ is determined for any even integer m, with some possible exceptions. A complete asymptotic existence result for k-SCGDDs of type m ⁿ is also obtained for all larger k and odd integer m. All these SCGDDs are used to derive new 2-D OOCs with the AM-OPPW restriction, which are optimal in the sense of their sizes.     

Nearly triply regular Drad’s ofRH type

Nearly triply regular (4m ², 2m ²−m,m ²−m) DRAD’s, wherem is an even power of 2, are constructed.     

Group‐divisible designs with block size k having k + 1 groups,for k = 4, 5

We investigate the spectrum for k‐GDDs having k + 1 groups, where k = 4 or 5. We take advantage of new constructions introduced by R. S. Rees (Two new direct product‐type constructions for resolvable group‐divisible designs, J Combin Designs, 1 (1993), 15–26) to construct many new designs. For example, we show that a resolvable 4‐GDD of type g⁵ exists if and only if g ≡ 0 mod 12 and that a resolvable 5‐GDD of type g⁶ exists if and only if g ≡ 0 mod 20. We also show that a 4‐GDD of type g⁴m¹ exists (with m > 0) if and only if g ≡ m ≡ 0 mod 3 and 0 < m ≤ 3g/2, except possibly when (g,m) = (9,3) or (18,6), and that a 5‐GDD of type g⁵m¹ exists (with m > 0) if and only if g ≡ m ≡ 0 mod 4 and 0 < m ≤ 4g/3, with 32 possible exceptions. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 363–386, 2000     

The monotone circuit complexity of boolean functions

Recently, Razborov obtained superpolynomial lower bounds for monotone circuits that cliques in graphs. In particular, Razborov showed that detecting cliques of sizes in a graphm vertices requires monotone circuits of size Ω(m ^s /(logm)^2s ) for fixeds, and sizem ^Ω(logm) form/4]. In this paper we modify the arguments of Razborov to obtain exponential lower bounds for circuits. In particular, detecting cliques of size (1/4) (m/logm)^2/3 requires monotone circuits exp (Ω((m/logm)^1/3)). For fixeds, any monotone circuit that detects cliques of sizes requiresm) ^s ) AND gates. We show that even a very rough approximation of the maximum clique of a graph requires superpolynomial size monotone circuits, and give lower bounds for some Boolean functions. Our best lower bound for an NP function ofn variables is exp (Ω(n ^1/4 · (logn)^1/2)), improving a recent result of exp (Ω(n ^1/8-ε)) due to Andreev. First author supported in part by Allon Fellowship, by Bat Sheva de-Rotschild Foundation by the Fund for basic research administered by the Israel Academy of Sciences. Second author supported in part by a National Science Foundation Graduate Fellowship.     

Regular<Emphasis Type="Italic">n</Emphasis>-simplices in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> with vertices in ℤ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In this paper theI andII regularn-simplices are introduced. We prove that the sufficient and necessary conditions for existence of anI regularn-simplex in ℝ ⁿ are that ifn is even thenn = 4m(m + 1), and ifn is odd thenn = 4m + 1 with thatn + 1 can be expressed as a sum of two integral squares orn = 4m - 1, and that the sufficient and necessary condition for existence of aII regularn-simplex in ℝ ⁿ isn = 2m ² - 1 orn = 4m(m + 1)(m ∈ ℕ). The connection between regularn-simplex in ℝ ⁿ and combinational design is given.     

The preparata codes and a class of 4-designs

An extension theorem for t-designs is proved. As an application, a class of 4-(4^m + 1,5,2) designs is constructed by extending designs related to the 3-designs formed by the minimum weight vectors in the Preparata code of length n = 4^m, m ≥ 2. © 1994 John Wiley & Sons, Inc.     

Ideal class groups and their subgroups of real quadratic fields

A necessary and sufficient condition is given for the ideal class group H(m) of a real quadratic field Q (√m) to contain a cyclic subgroup of ordern. Some criteria satisfying the condition are also obtained. And eight types of such fields are proved to have this property, e.g. fields withm=(z ⁿ +t−1)²+4t(witht|z ⁿ −1), which contains the well-known fields withm=4z ⁿ +1 andm=4z ²ⁿ +4 as special cases. Project supported by the National Natural Science Foundation of China.     

Group Divisible Designs with Block Size Four and Group Type gum1 with Minimum m

In this paper, we continue to investigate the spectrum for {4}-GDDs of type g^u m¹ with m as small as possible. We determine, for each admissible pair (g,u), the minimum values of m for which a {4}-GDD of type g^um¹ exists with four possible exceptions.Gennian Ge-Researcher supported by NSFC Grant 10471127.Alan C. H. Ling-Researcher supported by an ARO grant 19-01-1-0406 and a DOE grant.classification Primary 05B05     

Compromise 4<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> plans with clear two-factor interactions

This paper gets some necessary conditions for the existence of some kinds of clear 4^m2^n compromise plans which allow estimation of all main effects and some specified two-factor interactions without assuming the remaining two-factor interactions being negligible. Some methods for constructing clear 4^m2^n compromise plans are introduced.     

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.     

Extremal Homogeneous Polynomials on Real Normed Spaces

IfPis a continuousm-homogeneous polynomial on a real normed space andPis the associated symmetricm-linear form, the ratio P/P always lies between 1 andm^m/m!. We show that, as in the complex case investigated by Sarantopoulos (1987,Proc. Amer. Math. Soc.99, 340–346), there areP's for which P/P=m^m/m! and for whichPachieves norm if and only if the normed space contains an isometric copy of ℓ^m₁. However, unlike the complex case, we find a plentiful supply of such polynomials providedm4.     

Gruppo delle terne quasi pitagoriche primitive

We study the groupG _m of primitive solution of the diophantine equationx ²+my²=z² (m>1, squarefree). Form∈3 this group is torsion free, form=3 it has a torsion element of order 3; moreover for a finite number of values ofm we prove thatG _m is a direct sum of infinite cyclic groups and we give the generators ofG _m in terms of the primes represented by the quadratic forms of discriminant Δ=−4m.      

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.     

Homogeneous Schr?dinger Operators on Half-Line

The differential expression L_m=-?_x²+(m²-1/4)x^-2{L_m=-\partial_x^2+(m^2-1/4)x^{-2}} defines a self-adjoint operator H _m on L ²(0, ∞) in a natural way when m ² ≥ 1. We study the dependence of H _m on the parameter m show that it has a unique holomorphic extension to the half-plane Re m > −1, and analyze spectral and scattering properties of this family of operators.     

Perfect Mendelsohn designs with equal-sized holes and block size four

Let M = {m₁, m₂, …, m_h} and X be a v-set (of points). A holey perfect Mendelsohn designs (briefly (v, k, λ) - HPMD), is a triple (X, H, B), where H is a collection of subsets of X (called holes) with sizes M and which partition X, and B is a collection of cyclic k-tuples of X (called blocks) such that no block meets a hole in more than one point and every ordered pair of points not contained in a hole appears t-apart in exactly λ blocks, for 1 ≤ t ≤ k − 1. The vector (m₁, m₂, …, m_h) is called the type of the HPMD. If m₁ = m₂ = … = m_h = m, we write briefly m^h for the type. In this article, it is shown that the necessary condition for the existence of a (v, 4, λ) - HPMD of type m^h, namely, is also sufficient with the exception of types 2⁴ and 1⁸ with λ = 1, and type m⁴ for odd m with odd λ. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 203–213, 1997     

Extensions of p-adic vector measures

For R being a separating algebra of subsets of a set X, E a complete Hausdorff non-Archimedean locally convex space and m: R → E a bounded finitely additive measure, it is shown that:

a If m is σ-additive and strongly additive, then m has a unique σ-additive extension m^σ on the σ-algebra R^σ generated by R.

b If m is strongly additive and τ-additive, then m has a unique τ-additive extension m^τ on the α-algebra R^bo of all τ_R-Borel sets, where τ_R is the topology having R as a basis.

Also, some other results concerning such measures are given.     

On (2<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript> + 1)-variable symmetric Boolean functions with submaximum algebraic immunity 2<Superscript><Emphasis Type="Italic">m</Emphasis>−1</Superscript>

All (2 ^m + 1)-variable symmetric Boolean functions with submaximal algebraic immunity 2 ^m−1 are described and constructed. The total number of such Boolean functions is 3² · 2^2m−3 +3 ^m−2 · 2⁴ − 2 for m ⩾ 2. This work was supported by the Major State Basic Research Development Program of China (Grant No. 2004CB3180004) and National Natural Science Foundation of China (Grant No. 60433050)     

On Group-Divisible Designs with Block Size Four and Group-Type g u m 1

We investigate the spectrum for {4}-GDDs of type g ^u m ¹. Wedetermine, for each even g, all values of m for which a {4}-GDD of typeg ^u m ¹ exists, for every fourth value of u. We similarlydetermine, for each odd g 11 or 17, all values of m for which a {4}-GDD of typeg ^u m ¹ exists, for every third value of u. Finally, weestablish, up to a finite number of values of u, the spectrum for {4}-GDDs of typeg ^u m ¹ where gu is even, g {11, 17}.     

Another Note on the Greatest Prime Factors of Fermat Numbers

For every positive integer k > 1, let P(k) be the largest prime divisor of k. In this note, we show that if F_m = 2^2m + 1 is the mth Fermat number, then P(F_m) 2^m+2(4m + 9) + 1 for all m 4. We also give a lower bound of a similar type for P(F_a,m), where F_a,m = a^2m + 1 whenever a is even and m a¹⁸.AMS Subject Classification (1991) 11A51 11J86