A new extension theorem for linear codes

For an [n,k,d]_q code with k3, gcd(d,q)=1, the diversity of is defined as the pair (Φ₀,Φ₁) with

All the diversities for [n,k,d]_q codes with k3, d−2 (mod q) such that A_i=0 for all i0,−1,−2 (mod q) are found and characterized with their spectra geometrically, which yields that such codes are extendable for all odd q5. Double extendability is also investigated.     

P.I.G-rings and the contractability of primes

LetR=F{x ₁, …, x_k} be a prime affine p.i. ring andS a multiplicative closed set in the center ofR, Z(R). The structure ofG-rings of the formR _s is completely determined. In particular it is proved thatZ(R _s)—the normalization ofZ(R _s) —is a prüfer ring, 1≦k.d(R _s)≦p.i.d(R _s) and the inequalities can be strict. We also obtain a related result concerning the contractability ofq, a prime ideal ofZ(R) fromR. More precisely, letQ be a prime ideal ofR maximal to satisfyQϒZ(R)=q. Then k.dZ(R)/q=k.dR/Q, h(q)=h(Q) andh(q)+k.dZ(R)/q=k.dz(R). The last condition is a necessary butnot sufficient condition for contractability ofq fromR.     

Bounds in Polynomial Rings over Artinian Local Rings

Let R be a (mixed characteristic) Artinian local ring of length l and let X be an n-tuple of variables. We prove that several algebraic constructions in the ring R[X] admit uniform bounds on the degrees of their output in terms of l, n and the degrees of the input. For instance, if I is an ideal in R[X] generated by polynomials g _i of degree at most d and if f is a polynomial of degree at most d belonging to I, then f = q ₁ f ₁ + ··· + q _s f _s , for some q _i of degree bounded in terms of d, l and n only. Similarly, the module of syzygies of I is generated by tuples all of whose entries have degree bounded in terms of d, l and n only.     

Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

Bounds in Polynomial Rings over Artinian Local Rings

Let R be a (mixed characteristic) Artinian local ring of length l and let X be an n-tuple of variables. We prove that several algebraic constructions in the ring R[X] admit uniform bounds on the degrees of their output in terms of l, n and the degrees of the input. For instance, if I is an ideal in R[X] generated by polynomials g _i of degree at most d and if f is a polynomial of degree at most d belonging to I, then f = q ₁ f ₁ + ··· + q _s f _s , for some q _i of degree bounded in terms of d, l and n only. Similarly, the module of syzygies of I is generated by tuples all of whose entries have degree bounded in terms of d, l and n only.     

Purity conjecture for reductive groups

The following problem was posed by J.-L. Colliot-Th èléne and J.-J. Sansuc in [1, p. 124, Problem 6.4]. Given a local regular ring R and a reductive group scheme G over R determine whether the functor S → H 44-01 (S, G) satisfies the property of purity for R. In this work, we study this problem in a number of interesting particular cases. Namely, let k be a characteristic zero field, and G be one of the following algebraic groups over k: PGL _n , SL_1,A , O(q), SO(q), Spin(q), SL _n /μ _d where d divides n (here, A is a central simple k-algebra). In this paper we prove that the functor R → H _ét¹ (R, G) satisfies the property of purity for the group G and a regular local ring containing the field. In view of this result, it would appear reasonable to suggest that the aforementioned functor possesses the property of purity for an arbitrary connected reductive group G over a zero characteristic field k and an arbitrary regular local ring containing the field k. For groups of the types G ₂ and F ₄ with a trivial g₃ invariant, this conjecture has been proved in [2] and [3]. The problem and conjecture formulated above appear to be an extension of the known conjectures proposed by A. Grothendieck and J.-P. Serre (see [5, Remark 3, pp. 26–27], [6, Remark 1.11.a], and [14, Remark on p. 31]).     

The Fine Structure of the n-Widths of H-Spaces in Lq(−1, 1)

The n-widths of the unit ball A_p of the Hardy space H^p in L_q( −1, 1) are determined asymptotically. It is shown that for 1 ≤ q < p ≤∞ there exist constants k₁ and k₂ such that [formula]≤ d_n(A_p, L_q(−1, 1)),dⁿ(A_p, L_q(−1, 1)), δ_n(A_p, L_q(−1, 1))[formula]where d_n, dⁿ, and δ_n denote the Kolmogorov, Gel′fand and linear n-widths, respectively. This result is an improvement of estimates previously obtained by Burchard and Höllig and by the author.     

On nonautonomous linear systems of differential and difference equations with -symmetric coefficient matrices

Let denote the set of continuous n×n matrices on an interval . We say that is a nontrivial k-involution if where ζ=e^-2πi/k, d₀+d₁++d_k-1=n, and with . We say that is R-symmetric if R(t)A(t)R^-1(t)=A(t), , and we show that if A is R-symmetric then solving x^′=A(t)x or x^′=A(t)x+f(t) reduces to solving k independent d_ℓ×d_ℓ systems, 0ℓk-1. We consider the asymptotic behavior of the solutions in the case where . Finally, we sketch analogous results for linear systems of difference equations.     

The non-existence of Griesmer codes with parameters close to codes of Belov type

Hill and Kolev give a large class of q-ary linear codes meeting the Griesmer bound, which are called codes of Belov type (Hill and Kolev, Chapman Hall/CRC Research Notes in Mathematics 403, pp. 127–152, 1999). In this article, we prove that there are no linear codes meeting the Griesmer bound for values of d close to those for codes of Belov type. So we conclude that the lower bounds of d of codes of Belov type are sharp. We give a large class of length optimal codes with n _q (k, d) = g _q (k, d) + 1.     

Precise asymptotics in some strong limit theorems for multidimensionally indexed random variables

Consider Z₊^d (d2)—the positive d-dimensional lattice points with partial ordering , let {X_k,kZ₊^d} be i.i.d. random variables with mean 0, and set S_n=∑_knX_k, nZ₊^d. We establish precise asymptotics for ∑_n|n|^r/p−2P(|S_n||n|^1/p), and for

Full-size image

, (0δ1) as 0, and for

Full-size image

as .     

L1-optimal estimates for a regression type function in R

Let X₁, X₂, …, X_n be random vectors that take values in a compact set in R^d, d ≥ 1. Let Y₁, Y₂, …, Y_n be random variables (“the responses”) which conditionally on X₁ = x₁, …, X_n = x_n are independent with densities f(y | x_i, θ(x_i)), i = 1, …, n. Assuming that θ lives in a sup-norm compact space Θ_q,d of real valued functions, an optimal L₁-consistent estimator of θ is constructed via empirical measures. The rate of convergence of the estimator to the true parameter θ depends on Kolmogorov's entropy of Θ_q,d.     

One-dimensional Tilings Using Tiles with Two Gap Lengths

Let n,p,k,q,l be positive integers with n=k+l+1. Let x₁,x₂, . . . ,x_n be a sequence of positive integers with x₁<x₂<···<x_n. A set {x₁,x₂, . . . ,x_n} is called a set of type (p,k;q,l) if the set of differences {x₂–x₁,x₃–x₂, . . . ,x_n–x_n–1} equals {p, . . . ,p,q, . . . ,q} as a multiset, where p and q appear k and l times, respectively. Among other results, it is shown that for any p,k,q, there exists a finite interval I in the set of integers such that I is partitioned into sets of type (p,k;q,1).     

On the connectivity of proper colorings of random graphs and hypergraphs

Let Ω_q=Ω_q(H) denote the set of proper [q]‐colorings of the hypergraph H. Let Γ_q be the graph with vertex set Ω_q where two colorings σ,τ are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=H_n,m;k, k ≥ 2, the random k‐uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p. Γ_q is connected if d is sufficiently large and . This is optimal up to the first order in d. Furthermore, with a few more colors, we find that the diameter of Γ_q is O(n) w.h.p., where the hidden constant depends on d. So, with this choice of d,q, the natural Glauber dynamics Markov Chain on Ω_q is ergodic w.h.p.     

Power Values of Derivations with Annihilator Conditions on Lie Ideals in Prime Rings

Let R be a prime ring of char R ≠ 2, d a nonzero derivation of R, U a noncentral Lie ideal of R, and a ∈ R. If au ^{n ₁} d(u) ^{n ₂} u ^{n ₃} d(u) ^{n ₄} u ^{n ₅} … d(u) ^{n _k?1} u ^{n _k}  = 0 for all u ∈ U, where n ₁, n ₂,…,n _k are fixed non-negative integers not all zero, then a = 0 and if a(u ^s d(u)u ^t ) ⁿ  ∈ Z(R) for all u ∈ U, where s ≥ 0, t ≥ 0, n ≥ 1 are some fixed integers, then either a = 0 or R satisfies S ₄, the standard identity in four variables.     

The intersection of the powers of the radical in Noetherian P.I. rings

LetR be a ring and J its radical. DefineJ ₁=∩Jⁿ, J₂=∩J ₁ ⁿ ,…,… J_k=∩J _k−1 ⁿ .... It is shown that in a ringR satisfying a polynomial identity and the ascending chain condition on ideals,J _k =0 for some appropriatek. The work of the first author was supported by an NSF grant at the University of Chicago. The work of the second author was supported by an NSF grant at the University of California, San Diego.     

Resolutions of monomial almost complete intersections and generalizations

Let S=K[x₁,…,x_n] be a polynomial ring over a field kand let / be a monomial ideal of S. The main result of this paper is an explicit minimal resolution of kover R= S/Iwhen / is a monomial almost complete intersection ideal of S. We also compute an upper bound on the multigraded resolution of k over a generalization of monomial almost complete intersection ring.     

Cyclic Difference Packing and Covering Arrays

Let n and k be positive integers. Let C_q be a cyclic group of order q. A cyclic difference packing (covering) array, or a CDPA(k, n; q) (CDCA(k, n; q)), is a k × n array (a_ij) with entries a_ij (0 ≤ i ≤ k−1, 0 ≤ j ≤ n−1) from C_q such that, for any two rows t and h (0 ≤ t < h ≤ k−1), every element of C_q occurs in the difference list at most (at least) once. When q is even, then n ≤ q−1 if a CDPA(k, n; q) with k ≥ 3 exists, and n ≥ q+1 if a CDCA(k, n; q) with k ≥ 3 exists. It is proved that a CDCA(4, q+1; q) exists for any even positive integers, and so does a CDPA(4, q−1; q) or a CDPA(4, q−2; q). The result is established, for the most part, by means of a result on cyclic difference matrices with one hole, which is of interest in its own right.     

On the expected number of k-sets

Given a setS ofn points inR ^d , a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE _d (k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR ^d . WhenP is spherically symmetric we prove thatE _d (k, n)≤cn ^d−1 WhenP is uniform on a convex bodyK⊂R ² we prove thatE ₂ (k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR ² for whichE ₂((n−2)/2,n) iscn logn. The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

A Generalization of Engel Conditions with Derivations in Rings

Let R be a prime ring of characteristic different from 2 with Z the center of R and d a nonzero derivation of R. Let k, m, n be fixed positive integers. If ([d(x ^k ), x ^k ] _n ) ^m  ∈ Z for all x ∈ R, then R satisfies S ₄, the standard identity in 4 variables.