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.     

Multiple blocking sets in finite projective spaces and improvements to the Griesmer bound for linear codes

Belov, Logachev and Sandimirov construct linear codes of minimum distance d for roughly 1/q ^k/2 of the values of d < q ^k-1. In this article we shall prove that, for q = p prime and roughly \frac38{\frac{3}{8}}-th’s of the values of d < q ^k-1, there is no linear code meeting the Griesmer bound. This result uses Blokhuis’ theorem on the size of a t-fold blocking set in PG(2, p), p prime, which we generalise to higher dimensions. We also give more general lower bounds on the size of a t-fold blocking set in PG(δ, q), for arbitrary q and δ ≥ 3. It is known that from a linear code of dimension k with minimum distance d < q ^k-1 that meets the Griesmer bound one can construct a t-fold blocking set of PG(k−1, q). Here, we calculate explicit formulas relating t and d. Finally we show, using the generalised version of Blokhuis’ theorem, that nearly all linear codes over \mathbb F_p{{\mathbb F}_p} of dimension k with minimum distance d < q ^k-1, which meet the Griesmer bound, have codewords of weight at least d + p in subcodes, which contain codewords satisfying certain hypotheses on their supports.     

On Optimal Codes Over the Field with Five Elements

In this paper, we prove the nonexistence of Griesmer codes over the field of five elements for k = 4 and d = 33, 83, 163, 164.     

Graphic sequences with a realization containing a generalized friendship graph

Gould, Jacobson and Lehel [R.J. Gould, M.S. Jacobson, J. Lehel, Potentially G-graphical degree sequences, in: Y. Alavi, et al. (Eds.), Combinatorics, Graph Theory and Algorithms, vol. I, New Issues Press, Kalamazoo, MI, 1999, pp. 451-460] considered a variation of the classical Turán-type extremal problems as follows: for any simple graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂+?+d_n≥σ(H,n) has a realization G containing H as a subgraph. Let F_t,r,k denote the generalized friendship graph on kt−kr+r vertices, that is, the graph of k copies of K_t meeting in a common r set, where K_t is the complete graph on t vertices and 0≤r≤t. In this paper, we determine σ(F_t,r,k,n) for k≥2, t≥3, 1≤r≤t−2 and n sufficiently large.     

A general approach to optimal control of a regression experiment

Let $\text{θ}\text{θ}\text{?}$ = ($\text{θ}\text{θ}\text{?}$₁, $\text{θ}\text{θ}\text{?}$₂, …, $\text{θ}\text{θ}\text{?}$_n)′ be the least-squares estimator of θ = (θ₁, θ₂, …, θ_n)′ by the realization of the process y(t) = Σ_{k = 1}ⁿθ_kf_k(t) + ξ(t) on the interval T = [a, b] with f = (f₁, f₂, …, f_n)′ belonging to a certain set X. The process satisfies E(ξ(t))≡0 and has known continuous covariance r(s, t) = E(ξ(s)ξ(t)) on T × T. In this paper, A-, D-, and D_s-optimality are used as criteria for choosing f in X. A-, D-, and D_s-optimal models can be constructed explicitly by means of r.     

Affine blocking sets, three-dimensional codes and the Griesmer bound

We construct families of three-dimensional linear codes that attain the Griesmer bound and give a non-explicit construction of linear codes that are one away from the Griesmer bound. All these codes contain the all-1 codeword and are constructed from small multiple blocking sets in AG(2,q).     

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.     

Projective codes which satisfy the chain condition

Binary linear codes with length at most one above the Griesmer bound were proven to satisfy the chain condition by Helleseth et al. [1]. Binary linear projective codes with length two above the Griesmer bound which satisfy the chain condition are found. Necessary conditions for binary linear codes for which the two-way chain condition holds are derived.     

Reconstructing Geometric Objects from the Measures of Their Intersections with Test Sets

Let us say that an element of a given family $\mathcal{A}$ of subsets of ? ^d can be reconstructed using n test sets if there exist T ₁,…,T _n ?? ^d such that whenever $A,B\in\mathcal{A}$ and the Lebesgue measures of A∩T _i and B∩T _i agree for each i=1,…,n then A=B. Our goal will be to find the least such n. We prove that if $\mathcal{A}$ consists of the translates of a fixed reasonably nice subset of ? ^d then this minimum is n=d. To obtain this we prove the following two results. (1) A translate of a fixed absolutely continuous function of one variable can be reconstructed using one test set. (2) Under rather mild conditions the Radon transform of the characteristic function of K (that is, the measure function of the sections of K), (R _θ χ _K )(r)=λ ^d?1(K∩{x∈? ^d :〈x,θ〉=r}) is absolutely continuous for almost every direction θ. These proofs are based on techniques of harmonic analysis. We also show that if $\mathcal{A}$ consists of the enlarged homothetic copies rE+t (r≥1,t∈? ^d ) of a fixed reasonably nice set E?? ^d , where d≥2, then d+1 test sets reconstruct an element of $\mathcal{A}$ , and this is optimal. This fails in ?: we prove that a closed interval, and even a closed interval of length at least 1 cannot be reconstructed using two test sets. Finally, using randomly constructed test sets, we prove that an element of a reasonably nice k-dimensional family of geometric objects can be reconstructed using 2k+1 test sets. An example from algebraic topology shows that 2k+1 is sharp in general.     

Some variations on Tverberg’s theorem

Define T(d, r) = (d + 1)(r - 1) + 1. A well known theorem of Tverberg states that if n ≥ T(d, r), then one can partition any set of n points in R^d into r pairwise disjoint subsets whose convex hulls have a common point. The numbers T(d, r) are known as Tverberg numbers. Reay added another parameter k (2 ≤ k ≤ r) and asked: what is the smallest number n, such that every set of n points in R^d admits an r-partition, in such a way that each k of the convex hulls of the r parts meet. Call this number T(d, r, k). Reay conjectured that T(d, r, k) = T(d, r) for all d, r and k. In this paper we prove Reay’s conjecture in the following cases: when k ≥ [d+3/2], and also when d < rk/r-k - 1. The conjecture also holds for the specific values d = 3, r = 4, k = 2 and d = 5, r = 3, k = 2.     

A generalization of k-Cohen–Macaulay simplicial complexes

For a positive integer k and a non-negative integer t, a class of simplicial complexes, to be denoted by k-CM _t , is introduced. This class generalizes two notions for simplicial complexes: being k-Cohen–Macaulay and k-Buchsbaum. In analogy with the Cohen–Macaulay and Buchsbaum complexes, we give some characterizations of CM _t (=1?CM _t ) complexes, in terms of vanishing of some homologies of its links, and in terms of vanishing of some relative singular homologies of the geometric realization of the complex and its punctured space. We give a result on the behavior of the CM _t property under the operation of join of two simplicial complexes. We show that a complex is k-CM _t if and only if the links of its non-empty faces are k-CM _t?1. We prove that for an integer s≤d, the (d?s?1)-skeleton of a (d?1)-dimensional k-CM _t complex is (k+s)-CM _t . This result generalizes Hibi’s result for Cohen–Macaulay complexes and Miyazaki’s result for Buchsbaum complexes.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Tridiagonal matrices with nonnegative entries

In this paper, we characterize the nonnegative irreducible tridiagonal matrices and their permutations, using certain entries in their primitive idempotents. Our main result is summarized as follows. Let d denote a nonnegative integer. Let A denote a matrix in R and let denote the roots of the characteristic polynomial of A. We say A is multiplicity-free whenever these roots are mutually distinct and contained in R. In this case E_i will denote the primitive idempotent of A associated with theta_i(0?i?d). We say A is symmetrizable whenever there exists an invertible diagonal matrix Δ∈R such that ΔAΔ^-1 is symmetric. Let Γ(A) denote the directed graph with vertex set {0,1,…,d}, where i→j whenever i≠j and A_ij≠0.Theorem.Assume that each entry ofAis nonnegative. Then the following are equivalent for0≤s,t≤d.

(i)

The graphΓ(A)is a bidirected path with endpointss,t:s↔*↔*↔?↔*↔t.

(ii)

The matrixAis symmetrizable and multiplicity-free. Moreover the(s,t)-entry ofE_itimes(θ_i-θ₀)?(θ_i-θ_i-1)(θ_i-θ_i+1)?(θ_i-θ_d)is independent of i for0≤i≤d, and this common value is nonzero.

Recently Kurihara and Nozaki obtained a theorem that characterizes the Q-polynomial property for symmetric association schemes. We view the above result as a linear algebraic generalization of their theorem.     

On Ranks of Polynomials

Let V be a vector space over a field k, P : V → k, d ≥?3. We show the existence of a function C(r, d) such that rank(P) ≤ C(r, d) for any field k, char(k) > d, a finite-dimensional k-vector space V and a polynomial P : V → k of degree d such that rank(?P/?t) ≤ r for all t ∈ V ??0. Our proof of this theorem is based on the application of results on Gowers norms for finite fields k. We don’t know a direct proof even in the case when k = ?.     

Higher Weights of Anticodes and the Generalized Griesmer Bound

We show that the minimum r-weight d_r of an anticode can be expressed in terms of the maximum r-weight of the corresponding code. As examples, we consider anticodes from homogeneous hypersurfaces (quadrics and Hermitian varieties). In a number of cases, all differences (except for one) of the weight hierarchy of such an anticode meet an analog of the generalized Griesmer bound.     

Classification and nonexistence results for linear codes with prescribed minimum distances

Starting from a linear [n, k, d] _q code with dual distance ${d^{\bot}}$ , we may construct an ${[n - d^\bot, k - d^\bot +1,\geq d]_q}$ code with dual distance at least ${\left\lceil\frac{d^\bot}{q}\right\rceil}$ using construction Y ₁. The inverse construction gives a rule for the classification of all [n, k, d] _q codes with dual distance ${d^{\bot}}$ by adding ${d^\bot}$ further columns to the parity check matrices of the smaller codes. Isomorph rejection is applied to guarantee a small search space for this iterative approach. Performing a complete search based on this observation, we are able to prove the nonexistence of linear codes for 16 open parameter sets [n, k, d] _q , q =  2, 3, 4, 5, 7, 8. These results imply 217 new upper bounds in the known tables for the minimum distance of linear codes and establish the exact value in 109 cases.     

The error term in Nevanlinna’s inequality

An upper bound is given for the error termS(r, |a _j |,f) in Nevanlinna’s inequality. For given positive increasing functions p and $ with ∫ ₁ ^∞ dr/p(r) = ∫ ₁ ^∞ dr/r ?(r) = ∞, setP(r) = ∫ ₁ ^r dt/p,Ψ(r) = ∫ ₁ ^r dt/t ?(t) We prove that $$S(r, \left\{ {a_j } \right\}, f) \leqslant \log \frac{{T(r, f)\phi (T(r, f))}}{{p(r)}} + O(1)$$ holds, with a small exceptional set of r, for any finite set of points |a _j | in the extended plane and any meromorphic function f such thatΨ(T(r, f)) =O(P(r)). This improves the known results of A. Hinkkanen and Y. F. Wang. The sharpness of the estimate is also considered.     

On the eigenvalues of the Sturm-Liouville operator with potentials from Sobolev spaces

We study the asymptotic behavior of the eigenvalues the Sturm-Liouville operator Ly = ?y″ + q(x)y with potentials from the Sobolev space W ₂ ^θ?1 , θ ≥ 0, including the nonclassical case θ ∈ [0, 1) in which the potential is a distribution. The results are obtained in new terms. Let s _2k (q) = λ _k ^1/2 (q) ? k, s _2k?1(q) = μ _k ^1/2 (q) ? k ? 1/2, where {λ _k } ₁ ^∞ and {μ _k } ₁ ^∞ are the sequences of eigenvalues of the operator L generated by the Dirichlet and Dirichlet-Neumann boundary conditions, respectively,. We construct special Hilbert spaces t ₂ ^θ such that the mapping F:W ₂ ^θ?1 →t ₂ ^θ defined by the equality F(q) = {s _n } ₁ ^∞ is well defined for all θ ≥ 0. The main result is as follows: for θ > 0, the mapping F is weakly nonlinear, i.e., can be expressed as F(q) = Uq + Φ(q), where U is the isomorphism of the spaces W ₂ ^θ?1 and t ₂ ^θ , and Φ(q) is a compact mapping. Moreover, we prove the estimate ∥Ф(q)∥_τ ≤ C∥q∥_θ?1, where the exact value of τ = τ(θ) > θ ? 1 is given and the constant C depends only on the radius of the ball ∥q∥_θ? ≤ R, but is independent of the function q varying in this ball.     

On Defining Sets of Full Designs with Block Size Three

A defining set of a t-(v, k, λ) design is a subcollection of its blocks which is contained in no other t-design with the given parameters, on the same point set. A minimal defining set is a defining set, none of whose proper subcollections is a defining set. The spectrum of minimal defining sets of a design D is the set {|M| | M is a minimal defining set of D}. We show that if a t-(v, k, λ) design D is contained in a design F, then for every minimal defining set d _D of D there exists a minimal defining set d _F of F such that \({d_D = d_F\cap D}\). The unique simple design with parameters \({{\left(v,k, {v-2\choose k-2}\right)}}\) is said to be the full design on v elements; it comprises all possible k-tuples on a v set. Every simple t-(v, k, λ) design is contained in a full design, so studying minimal defining sets of full designs gives valuable information about the minimal defining sets of all t-(v, k, λ) designs. This paper studies the minimal defining sets of full designs when t = 2 and k = 3. Several families of non-isomorphic minimal defining sets of these designs are found. For given v, a lower bound on the size of the smallest and an upper bound on the size of the largest minimal defining set are given. The existence of a continuous section of the spectrum comprising approximately v values is shown, where just two values were known previously.