Nonexistence of [n, 5, d]q Codes Attaining the Griesmer Bound for q4 ?2q2 ?2q+1 ≤ d≤ q4?2q2 ?q

We prove that there does not exist a [q⁴+q³−q²−3q−1, 5, q⁴−2q²−2q+1]_q code over the finite field for q≥ 5. Using this, we prove that there does not exist a [g_q(5, d), 5, d]_q code with q⁴ −2q² −2q +1 ≤ d ≤ q⁴ −2q² −q for q≥ 5, where g_q(k,d) denotes the Griesmer bound.MSC 2000: 94B65, 94B05, 51E20, 05B25     

On minimal non-orientable matroids with elements and rank

We describe an infinite family M_n,k, with n≥4 and 1≤k≤n−2, of minimal non-orientable matroids of rank n on a set with 2n elements. For k=1,n−2, M_n,k is isomorphic to the Bland–Las Vergnas matroid M_n. For every 2≤k≤n−3 a new minimal non-orientable matroid is obtained. All proper minors of the matroids M_n,k are representable over .     

On Hankel Nonnegative Definite Sequences, the Canonical Hankel Parametrization, and Orthogonal Matrix Polynomials

This paper continues recent investigations started in Dyukarev et al. (Complex anal oper theory 3(4):759–834, 2009) into the structure of the set H_q,2n ³ {\mathcal{H}_{q,2n}^{\ge}} of all Hankel nonnegative definite sequences, (s_j)_j=0²ⁿ{(s_{j})_{j=0}^{2n}}, of complex q × q matrices and its important subclasses H_q,2n ^{3 ,e}{\mathcal{H}_{q,2n}^{\ge,{\rm e}}} and ${\mathcal{H}_{q,2n}^>}${\mathcal{H}_{q,2n}^>} of all Hankel nonnegative definite extendable sequences and of all Hankel positive definite sequences, respectively. These classes of sequences arise quite naturally in the framework of matrix versions of the truncated Hamburger moment problem. In Dyukarev et al. (Complex anal oper theory 3(4):759–834, 2009) a canonical Hankel parametrization [(C_k)_k=1ⁿ, (D_k)_k=0ⁿ]{[(C_k)_{k=1}^n, (D_k)_{k=0}^n]} consisting of two sequences of complex q × q matrices was associated with an arbitrary sequence (s_j)_j=0²ⁿ{(s_{j})_{j=0}^{2n}} of complex q × q matrices. The sequences belonging to each of the classes H_q,2n ³ , H_q,2n ^{3 ,e}{\mathcal{H}_{q,2n}^{\ge}, \mathcal{H}_{q,2n}^{\ge,{\rm e}}}, and ${\mathcal{H}_{q,2n}^>}${\mathcal{H}_{q,2n}^>} were characterized in terms of their canonical Hankel parametrization (see, Dyukarev et al. in Complex anal oper theory 3(4):759–834, 2009; Proposition 2.30). In this paper, we will study further aspects of the canonical Hankel parametrization. Using the canonical Hankel parametrization [(C_k)_k=1ⁿ, (D_k)_k=0ⁿ]{[(C_k)_{k=1}^n, (D_k)_{k=0}^n]} of a sequence (s_j)_j=0²ⁿ ? H_q,2n ³ {(s_{j})_{j=0}^{2n} \in \mathcal{H}_{q,2n}^{\ge}}, we give a recursive construction of a monic right (resp. left) orthogonal system of matrix polynomials with respect to (s_j)_j=0²ⁿ{(s_{j})_{j=0}^{2n}} (see Theorem 5.5). The matrices [(C_k)_k=1ⁿ, (D_k)_k=0ⁿ]{[(C_k)_{k=1}^n, (D_k)_{k=0}^n]} will be expressed in terms of an arbitrary monic right (resp. left) orthogonal system with respect to (s_j)_j=0²ⁿ{(s_{j})_{j=0}^{2n}} (see Theorem 5.11). This result will be reformulated in terms of nonnegative Hermitian Borel measures on \mathbbR{\mathbb{R}}. In this way, integral representations for the matrices [(C_k)_k=1ⁿ, (D_k)_k=0ⁿ]{[(C_k)_{k=1}^n, (D_k)_{k=0}^n]} will be obtained (see Theorem 6.9). Starting from the monic orthogonal polynomials with respect to some classical probability distributions on \mathbbR{\mathbb{R}}, Theorem 6.9 is used to compute the canonical Hankel parametrization of their moment sequences. Moreover, we discuss important number sequences from enumerative combinatorics using the canonical Hankel parametrization.     

Representations for the first associated q-classical orthogonal polynomials

Let {p_k(x; q)} be any system of the q-classical orthogonal polynomials, and let be the corresponding weight function, satisfying the q-difference equation D_q(σ)=τ, where σ and τ are polynomials of degree at most 2 and exactly 1, respectively. Further, let {p_k⁽¹⁾(x;q)} be associated polynomials of the polynomials {p_k(x; q)}. Explicit forms of the coefficients b_n,k and c_n,k in the expansions

are given in terms of basic hypergeometric functions. Here _k(x) equals x^k if σ⁺(0)=0, or (x;q)_k if σ⁺(1)=0, where σ⁺(x)σ(x)+(q−1)xτ(x). The most important representatives of those two classes are the families of little q-Jacobi and big q-Jacobi polynomials, respectively.Writing the second-order nonhomogeneous q-difference equation satisfied by p_n−1⁽¹⁾(x;q) in a special form, recurrence relations (in k) for b_n,k and c_n,k are obtained in terms of σ and τ.     

Type II Hermite�CPad�� Approximations of Generalized Hypergeometric Series

We shall present short proofs for type II (simultaneous) Hermite–Padé approximations of the generalized hypergeometric and q-hypergeometric series

Extending MDS Codes

A q-ary (n, k)-MDS code, linear or not, satisfies n ≤ q + k − 1. A code meeting this bound is said to have maximum length. Using purely combinatorial methods we show that an MDS code with n = q + k − 2 can be uniquely extended to a maximum length code if and only if q is even. This result is best possible in the sense that there is, for example, a non-extendable 4-ary (5, 4)-MDS code. It may be that the proof of our result is as interesting as the result itself. We provide a simple necessary and sufficient condition for code extendability. In future work, this condition might be suitably modified to give an extendability condition for arbitrary (shorter) MDS codes.Received December 1, 2003     

The Lebesgue Constant for Higher Order Hermite-Fejér Interpolation on the Chebyshev Nodes

For a fixed integer m ≥ 0, and for n = 1, 2, 3, ..., let λ_{2m, n}(x) denote the Lebesgue function associated with (0, 1,..., 2m) Hermite-Fejér polynomial interpolation at the Chebyshev nodes {cos[(2k−1) π/(2n)]: k=1, 2, ..., n}. We examine the Lebesgue constant Λ_{2m, n} max{λ_{2m, n}(x): −1 ≤ x ≤ 1}, and show that Λ_{2m, n} = λ_{m, n}(1), thereby generalising a result of H. Ehlich and K. Zeller for Lagrange interpolation on the Chebyshev nodes. As well, the infinite term in the asymptotic expansion of Λ_{2m, n)} as n → ∞ is obtained, and this result is extended to give a complete asymptotic expansion for Λ_{2, n}.     

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.     

Prophet inequalities for cost of observation stopping problems

Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X₁, X₂, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max_{1 ≤ j ≤ n}(X_j − jc)) − sup_{t Tn} E(X_t − tc) ≤ 1/e, where T_n is the collection of all stopping times t which are less than or equal to n almost surely.     

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.     

Extremal Regular Graphs with Prescribed Odd Girth

The odd girth of a graph G gives the length of a shortest odd cycle in G. Let ƒ(k, g) denote the smallest n such that there exists a k-regular graph of order n and odd girth g. It is known that ƒ(k, g) ≥ kg/2 and that ƒ(k, g) = kg/2 if k is even. The exact values of ƒ(k, g) are also known if k = 3 or g = 5. Let x_e denote the smallest even integer no less than x, δ(g) = (−1)^{g − 1}/2, and s(k) = min {p + q | k = pq, where p and q are both positive integers}. It is proved that if k ≥ 5 and g ≥ 7 are both odd, then [formula] with the exception that ƒ(5, 7) = 20.     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

On Some Sets with Even Valued Partition Function

Let IN be the set of positive integers, = {b₁ < ⋅s < b_h}⊂IN, N∊IN and N≥ b_h. = ₀( ,N) is the set (introduced by J.-L. Nicolas, I.Z. Ruzsa and A. Sárközy) such that {1,..., N} = and p( ,n)≡ 0 (mod 2) for n∊IN and n > N, where p( ,n) denotes the number of partitions of n with parts in . Let us denote by σ ( ,n) the sum of the divisors of n belonging to . In a paper jointly written with J.-L. Nicolas, we have recently proved that, for all k≥ 0, the sequence (σ( ,2^k n))_{n≥ 1}mod 2^k+1 is periodic with an odd period q_k. In this paper, we will characterize for any fixed odd positive integer q, the sets and the integers N such that q₀ = q, and those for which q_k = q for all k≥ 0. Moreover, a set = ₀( ,N) is constructed with the property that its period, i.e. the period of (σ( ,n))_{n≥ 1}mod 2, is 217, and for which the counting function is asymptotically equal to that of ₀({1,2,3,4,5},5) which is a set of period 31.Dedicated to Professor J.-L. Nicolas on the occasion of his 60th birthday2000 Mathematics Subject Classification: Primary—11P81, 11P83Research supported by MIRA 2002 program n^o 0203012701, Number Theory, Lyon-Monastir.     

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.     

Companions of the inequalities of Fejér--Jackson and Young

Summary Applications of some well-known theorems of Jackson and Young lead to the sharp inequalities -1<ⁿ_k-1Σ(cos(kx)+sin(kx))/k (n ≥1; 1<x<π) and -1/2Si(π)<ⁿ_k-1Σ(cos(kx)·sin(kx))/k (n ≥1; xЄR) We prove that the following counterpart is valid for all integers n ≥1 and real numbers xЄ (0, π): -3/2≤ⁿ_k-1Σ(cos(kx)-sin(kx))/k where the sign of equality holds if and only if n =2 and x = π /2.     

Linear programming and operator means

The shorted operator, the geometric mean, and the cascade limit are all examples of operations that are of the form sup{X¦C + K X ≥ 0}, where K X denotes the Kronecker product of the matrix K with the matrix X, K is a given n by n self-adjoint matrix, and C is a given positive semidefinite matrix. The supremum is taken with respect to the partial order generated by the positive semidefinite matrices. In all of the above examples the matrix K has exactly one negative eigenvalue. We show by linear programming techniques that if K has this property, and X_max = sup{X¦C + K X ≥ 0}, then (X_maxc, c) = inf tr(AY), subject to: −∑_{i,j = 1}ⁿk_ijY_ij ≥ cc^*, Y = {Y_ij)_{i,j = 1}ⁿ ≥ 0} In the case of the geometric mean A#B of two positive semidefinite matrices, this implies the new result that (A#Bc, c) = inf{tr(AY₁₁ + BY₂₂¦Y₁₂ + Y₂₁ ≥ cc^*, Y ≥ 0}.     

Greedily Finding a Dense Subgraph

Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)² − O(n ^− 1/3) ≤ R ≤ (1/2 + n/2k)² + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k²) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.     

Moments of Brownian Motions on Lie Groups

Let (B_t)_{t ≥ 0} be a Brownian motion on GL(n,\Bbb R)GL(n,{\Bbb R}) with the corresponding Gaussian convolution semigroup (μ_t)_{t ≥ 0} and generator L. We show that algebraic relations between L and the generators of the matrix semigroups (ò_{GL(n,\Bbb R)} x^?k dm_t(x))_{t 3 0}(\int_{GL(n,{\Bbb R})} x^{\otimes k}\ d\mu_t(x))_{t \ge 0} lead to E((B_t-B_s)_i,j^2k) = O((t-s)^k)E((B_t-B_s)_{i,j}^{2k}) =O((t-s)^k) for t → s, k ≥ 1, and all coordinates i,j. These relations will form the basis for a martingale characterization of (B_t)_{t ≥ 0} in terms of generalized heat polynomials. This characterization generalizes a corresponding result for the Brownian motion on \Bbb R{\Bbb R} in terms of Hermite polynomials due to J. Wesolowski and may be regarded as a variant of the Lévy characterization without continuity assumptions.     

Extremal problems concerning Kneser graphs

Let and be two intersecting families of k-subsets of an n-element set. It is proven that | | ≤ (_k−1ⁿ⁻¹) + (_k−1ⁿ⁻¹) holds for , and equality holds only if there exist two points a, b such that {a, b} ∩ F ≠ for all F . For an example showing that in this case max | | = (1−o(1))(_kⁿ) is given. This disproves an old conjecture of Erdös [7]. In the second part we deal with several generalizations of Kneser's conjecture.