Tame and wild subspace problems

Assume thatB is a finite-dimensional algebra over an algebraically closed fieldk, B _d =Spec k[(B _d ] is the affine algebraic scheme whoseR-points are theB _k k[B_d]-module structures onR ^d, and M_d is a canonical B_k k[B_d]-module supported by k[B_d]^d. Further, say that an affine subscheme of B_d isclass true if the functor F_gn X M_{d k[B]} X induces an injection between the sets of isomorphism classes of indecomposable finite-dimensional modules over k[] andB. If B_d contains a class-true plane for somed, then the schemes B_e contain class-true subschemes of arbitrary dimensions. Otherwise, each B_d contains a finite number of classtrue puncture straight linesL(d, i) such that for eachn, almost each indecomposableB-module of dimensionn is isomorphic to someF _{L(d, i)} (X); furthermore,F _{L(d, i)} (X) is not isomorphic toF _{L(l, j)} (Y) if(d, i) (l, j) andX 0. The proof uses a reduction to subspace problems, for which an inductive algorithm permits us to prove corresponding statements.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 3, pp. 313–352, March, 1993.     

A Remarkable q,t-Catalan Sequence and q-Lagrange Inversion

We introduce a rational function C _n(q, t) and conjecture that it always evaluates to a polynomial in q, t with non-negative integer coefficients summing to the familiar Catalan number . We give supporting evidence by computing the specializations and C _n (q) = C _n(q,1) = C _n(1,q). We show that, in fact, D _n(q) q-counts Dyck words by the major index and C _n(q) q-counts Dyck paths by area. We also show that C _n(q, t) is the coefficient of the elementary symmetric function e _nin a symmetric polynomial DH_n(x; q, t) which is the conjectured Frobenius characteristic of the module of diagonal harmonic polynomials. On the validity of certain conjectures this yields that C _n(q, t) is the Hilbert series of the diagonal harmonic alternants. It develops that the specialization DH_n(x; q, 1) yields a novel and combinatorial way of expressing the solution of the q-Lagrange inversion problem studied by Andrews [2], Garsia [5] and Gessel [11]. Our proofs involve manipulations with the Macdonald basis {P (x; q, t)} which are best dealt with in -ring notation. In particular we derive here the -ring version of several symmetric function identities.Work carried out under NSF grant support.     

On the minimum length of ternary linear codes

From the geometrical point of view, we prove that [g ₃(6, d) + 1, 6, d]₃ codes exist for d = 118–123, 283–297 and that [g ₃(6, d), 6, d]₃ codes for d = 100, 341, 342 and [g ₃(6, d) + 1, 6, d]₃ codes for d = 130, 131, 132 do not exist, where ${g_3(k,\,d)=\sum_{i=0}^{k-1}\left\lceil d/3^i \right\rceil}$ . These determine the exact value of n ₃(6, d) for d = 100, 118–123, 130, 131, 132, 283–297, 341, 342, where n _q (k, d) is the minimum length n for which an [n, k, d] _q code exists.     

Error-Correcting Codes over an Alphabet of Four Elements

The problem of finding the values of A_q(n,d)—the maximum size of a code of length n and minimum distance d over an alphabet of q elements—is considered. Upper and lower bounds on A₄(n,d) are presented and some values of this function are settled. A table of best known bounds on A₄(n,d) is given for n 12. When q M < 2q, all parameters for which A_q(n,d) = M are determined.     

New linear codes over GF(8)

Let [n, k, d; q]-codes be linear codes of length n, dimension k and minimum Hamming distance d over GF(q). Let d₈(n, k) be the maximum possible minimum Hamming distance of a linear [n, k, d; 8]-code for given values of n and k. In this paper, eighteen new linear codes over GF(8) are constructed which improve the table of d₈(n, k) by Brouwer.     

Classifying Subspaces of Hamming Spaces

A linear code in F ⁿ _q with dimension k and minimum distance at least d is called an [n, k, d] _q code. We here consider the problem of classifying all [n, k, d] _q codes given n, k, d, and q. In other words, given the Hamming space F ⁿ _q and a dimension k, we classify all k-dimensional subspaces of the Hamming space with minimum distance at least d. Our classification is an iterative procedure where equivalent codes are identified by mapping the code equivalence problem into the graph isomorphism problem, which is solved using the program nauty. For d = 3, the classification is explicitly carried out for binary codes of length n 14, ternary codes of length n 11, and quaternary codes of length n 10.     

The second and the third smallest distances on the sphere

Let s₁ (n) denote the largest possible minimal distance amongn distinct points on the unit sphere . In general, let s_k(n) denote the supremum of thek-th minimal distance. In this paper we prove and disprove the following conjecture of A. Bezdek and K. Bezdek: s₂(n) = s₁([n/3]). This equality holds forn > n₀ however s₂(12) > s₁(4).We set up a conjecture for s_k(n), that one can always reduce the problem of thek-th minimum distance to the function s₁. We prove this conjecture in the casek=3 as well, obtaining that s₃(n) = s₁([n/5]) for sufficiently largen.The optimal construction for the largest second distance is obtained from a point set of size [n/3] with the largest possible minimal distance by replacing each point by three vertices of an equilateral triangle of the same size . If 0, then s₂ tends to s₁([n/3]). In the case of the third minimal distance, we start with a point set of size [n/5] and replace each point by a regular pentagon.     

Random polytopes in thed-dimensional cube

LetC ^d be the set of vertices of ad-dimensional cube,C ^d ={(x ₁, ...,x _d ):x _i =±1}. Let us choose a randomn-element subsetA(n) ofC ^d . Here we prove that Prob (the origin belongs to the convA(2d+x2d))=(x)+o(1) ifx is fixed andd . That is, for an arbitrary>0 the convex hull of more than (2+)d vertices almost always contains 0 while the convex hull of less than (2-)d points almost always avoids it.     

Some New Optimal Ternary Linear Codes

Let d₃(n,k) be the maximum possible minimum Hamming distance of a ternary [ n,k,d;3]-code for given values of n and k. It is proved that d₃(44,6)=27, d₃(76,6)=48,d₃(94,6)=60 , d₃(124,6)=81,d₃(130,6)=84 , d₃(134,6)=87,d₃(138,6)=90 , d₃(148,6)=96,d₃(152,6)=99 , d₃(156,6)=102,d₃(164,6)=108 , d₃(170,6)=111,d₃(179,6)=117 , d₃(188,6)=123,d₃(206,6)=135 , d₃(211,6)=138,d₃(224,6)=147 , d₃(228,6)=150,d₃(236,6)=156 , d₃(31,7)=17 and d₃(33,7)=18 . These results are obtained by a descent method for designing good linear codes.     

Lower Bounds For Multidimensional Zero Sums

Let f(n, d) denote the least integer such that any choice of f(n, d) elements in contains a subset of size n whose sum is zero. Harborth proved that (n-1)2 ^d +1 f(n,d) (n-1)n ^d +1. The upper bound was improved by Alon and Dubiner to c _d n. It is known that f(n-1) = 2n-1 and Reiher proved that f(n-2) = 4n-3. Only for n = 3 it was known that f(n,d) > (n-1)2 ^d +1, so that it seemed possible that for a fixed dimension, but a sufficiently large prime p, the lower bound might determine the true value of f(p,d). In this note we show that this is not the case. In fact, for all odd n 3 and d 3 we show that .     

Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

On the minimum length of some linear codes

We determine the minimum length n _q (k, d) for some linear codes with k ≥ 5 and q ≥ 3. We prove that n _q (k, d) = g _q (k, d) + 1 for when k is odd, for when k is even, and for . This work was supported by the Korea Research Foundation Grant funded by the Korean Government(MOEHRD). (KRF-2005-214-C00175). This research has been partially supported by Grant-in-Aid for Scientific Research of Japan Society for the Promotion of Science under Contract Number 17540129.     

On the Achievement of the Griesmer Bound

The main theorem in this paper is that there does not exist an [n,k,d]_q code with d = (k-2)q ^k-1 - (k-1)q^k-2 attaining the Griesmer bound for q k, k=3,4,5 and for q 2k-3, k 6.     

The Smallest Parallelepiped of n Random Points and Peeling

Let n random points be given with uniform distribution in the d-dimensional unit cube [0,1]^d. The smallest parallelepiped A which includes all the n random points is dealt with. We investigate the asymptotic behavior of the volume of A as n tends to . Using a point process approach, we derive also the asymptotic behavior of the volumes of the k-th smallest parallelepipeds A _n ^(k) which are defined by iteration. Let A _n = A _n ⁽¹⁾ . Given A _n ^(k,-,1) delete the random points X _i which are on the boundary A _n ^(k,-,1) , and construct the smallest parallelepiped which includes the inner points of A _n ^(k,-,1) , this defines A _n ^(k) . This procedure is known as peeling of the parallelepiped A_n.     

Even diameters of the classes W(r)H ω in the space C2π

For even values of n we find the exact values of the diameters d_n(W^(r)H) of the classes of 2-periodic functions ((t) is an arbitrary convex upwards modulus of continuity) in the space C₂. We find that d_2n(W^(r)H)=d_2n–1(W^(r)H) (n=1, 2, ... r=0, 1, 2, ...).Translated from Matematicheskie Zametki, Vol. 15, No. 3, pp. 387–392, March, 1974.The author expresses his thanks to N. P. Korneichuk for his interest in my work.     

A Bose-Burton Theorem for Elliptic Polar Spaces

In bose&burton, Bose and Burton determined the smallest point sets of PG(d, q) that meet every subspace of PG(d, q) of a given dimension c. In this paper an equivalent result for quadrics of elliptic type is obtained. It states the folloing. For 0 c n - 1 the smallest point set of the elliptic quadric Q ^-(2n + 1, q) that meets every singular subspace of dimension c of Q ^-(2n + 1, q) has cardinality (q ⁿ⁺¹ + q ^c )(q ^n-c - 1)/(q - 1). Furthermore, the point sets of the smallest cardinality are classified.     

Multiple Exponential Sums with Monomials and Their Applications in Number Theory

Fouvry and Iwaniec's method ([6], [11]) for exponential sums with monomials uses, in a crucial way, a spacing lemma for t(m, q) := (m + q) – (m – q). By introducing a technique on integer points close to a family of curves, we are able to improve their result and to treat the spacing problem for u(m, n, q) := t(m, q)n . Finally we choose four classic arithmetic problems to illustrate our new results.     

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.     

Some Characterizations of Finite Hermitian Veroneseans

We characterize the finite Veronesean of all Hermitian varieties of PG(n,q²) as the unique representation of PG(n,q²) in PG(d,q), d n(n+2), where points and lines of PG(n,q²) are represented by points and ovoids of solids, respectively, of PG(d,q), with the only condition that the point set of PG(d,q) corresponding to the point set of PG(n,q²) generates PG(d,q). Using this result for n=2, we show that is characterized by the following properties: (1) ; (2) each hyperplane of PG(8,q) meets in q²+1, q³+1 or q³+q²+1 points; (3) each solid of PG(8,q) having at least q+3 points in common with shares exactly q²+1 points with it.51E24     

Some inequalities of the V. A. Markov type

Let B be a domain in the complex plane, let p_n(z) and P_n(z) be polynomials of degree n where the zeros of P_n(z) lie in , let(z) be a finite function,(z) 0, z . We consider the problem of estimating from above the functions L[p_n(z)]=(z)p_n(z) – wp_n(z), z , if ¦p_n(z)¦ ¦P_n(z)¦ for zB. Under some very general conditions on B, z, (z), and w we prove the inequality ¦L[p_n(z)]¦ ¦L[P_n(z)]¦.Translated from Matematicheskie Zametki, Vol. 3, No. 4, pp. 431–440, April, 1968.