Finite Projective Geometries and Classification of the Weight Hierarchies of Codes （Ⅰ）

The weight hierarchy of a binary linear [n,κ] code C is the sequence (d1,d2,...,dκ), where dr is the smallest support of an r-dimensional subcode of C. The codes of dimension 4 are collected in classes and the possible weight hierarchies in each class is determined by finite projective geometries.The possible weight hierarchies in class A, B, C, D are determined in Part (Ⅰ). The possible weight hierarchies in class E, F, G, H, I are determined in Part (Ⅱ).     

Weight Hierarchies of Linear Codes Satisfying the Chain Condition

The weight hierarchy of a linear [n,k;q] code C over GF(q) is the sequence (d₁,d₂,...,d_k) where d_r is the smallest support of an r–dimensional subcode of C. By explicit construction, it is shown that if a sequence (a₁,a₂,...,a_k) satisfies certain conditions, then it is the weight hierarchy of a code satisfying the chain condition.     

Monochromatic affine lines in finite vector spaces

Let d(k, q) be the smallest positive integer d such that if the d-dimensional vector space over the q-element field is k-colored, there exists a monochromatic affine line. It is shown that d(2, 4) = 3 and d(3, 3) = 4.     

A Lower Bound on the Greedy Weights of Product Codes

A greedy 1-subcode is a one-dimensional subcode of minimum (support) weight. A greedy r-subcode is an r-dimensional subcode with minimum support weight under the constraint that it contain a greedy (r - 1)-subcode. The r-th greedy weight e _r is the support weight of a greedy r-subcode. The greedy weights are related to the weight hierarchy. We use recent results on the weight hierarchy of product codes to develop a lower bound on the greedy weights of product codes.     

Recent results on designs with classical parameters

We report on recent results concerning designs with the same parameters as the classical geometric designs PG _d (n, q) formed by the points and d-dimensional subspaces of the n-dimensional projective space PG(n, q) over the field GF(q) with q elements, where 1 ???d ???n?1. The corresponding case of designs with the same parameters as the classical geometric designs AG _d (n, q) formed by the points and d-dimensional subspaces of the n-dimensional affine space AG(n, q) will also be discussed, albeit in less detail.     

Ternary codes of steiner triple systems

The code over a finite field F^q of a design ?? is the space spanned by the incidence vectors of the blocks. It is shown here that if ?? is a Steiner triple system on v points, and if the integer d is such that 3^d ≤ v < 3^d+1, then the ternary code C of ?? contains a subcode that can be shortened to the ternary generalized Reed-Muller code ?_F3(2(d ? 1),d) of length 3^d. If v = 3^d and d ≥ 2, then C_? ? ?_F3(1,d)? ? _F3(2(d ? 1),d) ? C. © 1994 John Wiley & Sons, Inc.     

Generic planes conjecture

In some particular cases we prove the density of the set of mappings of an n-dimensional compactum into an m-dimensional Euclidean space such that the set of all d-dimensional planes with the preimage cardinality ?? q has the dimension ?? qn - (q ? d ? 1)(m ? d).     

Tree Modules and Counting Polynomials

We give a formula for counting tree modules for the quiver S _g with g loops and one vertex in terms of tree modules on its universal cover. This formula, along with work of Helleloid and Rodriguez-Villegas, is used to show that the number of d-dimensional tree modules for S _g is polynomial in g with the same degree and leading coefficient as the counting polynomial $A_{S_g}(d, q)$ for absolutely indecomposables over $\mathbb{F}_q$ , evaluated at q?=?1.     

The small weight codewords of the functional codes associated to non-singular Hermitian varieties

This article studies the small weight codewords of the functional code C _Herm (X), with X a non-singular Hermitian variety of PG(N, q ²). The main result of this article is that the small weight codewords correspond to the intersections of X with the singular Hermitian varieties of PG(N, q ²) consisting of q + 1 hyperplanes through a common (N ? 2)-dimensional space Π, forming a Baer subline in the quotient space of Π. The number of codewords having these small weights is also calculated. In this way, similar results are obtained to the functional codes C ₂(Q), Q a non-singular quadric (Edoukou et al., J. Pure Appl. Algebra 214:1729–1739, 2010), and C ₂(X), X a non-singular Hermitian variety (Hallez and Storme, Finite Fields Appl. 16:27–35, 2010).     

Hamiltonian threshold graphs

The vertices of a threshold graph G are partitioned into a clique K and an independent set I so that the neighborhoods of the vertices of I are totally ordered by inclusion. The question of whether G is hamiltonian is reduced to the case that K and I have the same size, say r, in which case the edges of K do not affect the answer and may be dropped from G, yielding a bipartite graph B. Let d₁≤d₂≤…≤d_r and e₁≤e₂≤…≤e_r be the degrees in B of the vertices of I and K, respectively. For each q = 0, 1,…,r−1, denote by S_q the following system of inequalities: d_j⩾j + 1, j = 1,2,…,q, e_j⩾j + 1, j = 1, 2,…, r−1−1. Then the following conditions are equivalent:

• 1.(1) B is hamiltonian,
• 2.(2) S_q holds for some q = 0, 1,…, r−1,
• 3.(3) S_q holds for each q = 0, 1,…, r−1.

     

Schauder estimates for a class of second order elliptic operators on a cube

We consider a class of second order elliptic operators on a d-dimensional cube S_d. We prove that if the coefficients are of class C^k+δ(S_d), with k=0,1 and δ∈(0,1), then the corresponding elliptic problem admits a unique solution u belonging to C^k+2+δ(S_d) and satisfying non-standard boundary conditions involving only second order derivatives.     

Latin hypercubes and MDS codes

Maximum distance separable (MDS) codes have special properties that give them excellent error correcting capabilities. Counting the number of q-ary MDS codes of length n and distance d, denoted by D_q(n,d)_MDS, is a very hard problem. This paper shows that for d=2, it amounts to counting the number of (n-1)-dimensional Latin hypercubes of order q. Thus, D_q(3,2)_MDS is the number of Latin squares of order q, which is known only for a few values of q. This paper proves constructively that D₃(n,2)_MDS=6·2^n-2.     

On the varieties of special divisors

Based on a relation between the varieties W_d^r(C) of special divisors on a curve C and subloci of effective divisors on C imposing a suitable number of conditions on a certain linear series we develop a tool for the construction of irreducible components of W_d^r(C). Using this we discover new irreducible components of W_d^r(C), for a general k-gonal curve C of genus g, and in some cases we can identify the duals of these components in K_C − W_d^r(C) = W_d′^r′(C)(d′ = 2g − 2 − d, r′ = g − 1 − d + r).     

Pappus type theorems for motions along a submanifold

We study the volumes volume(D) of a domain D and volume(C) of a hypersurface C obtained by a motion along a submanifold P of a space form Mⁿ_λ. We show: (a) volume(D) depends only on the second fundamental form of P, whereas volume(C) depends on all the ith fundamental forms of P, (b) when the domain that we move D₀ has its q-centre of mass on P, volume(D) does not depend on the mean curvature of P, (c) when D₀ is q-symmetric, volume(D) depends only on the intrinsic curvature tensor of P; and (d) if the image of P by the ln of the motion (in a sense which is well-defined) is not contained in a hyperplane of the Lie algebra of SO(n−q−d), and C is closed, then volume(C) does not depend on the ith fundamental forms of P for i>2 if and only if the hypersurface that we move is a revolution hypersurface (of the geodesic (n−q)-plane orthogonal to P) around a d-dimensional geodesic plane.     

A Note on the Complexity of Solving Poisson's Equation for Spaces of Bounded Mixed Derivatives

We study the complexity of solving the d-dimensional Poisson equation on ]0, 1[^d. We restrict ourselves to cases where the solution u lies in some space of functions of bounded mixed derivatives (with respect to the L_∞- or the L₂-norm) up to ∂^2d/∏^d_j=1 ∂x²_j. An upper bound for the complexity of computing a solution of some prescribed accuracy ε with respect to the energy norm is given, which is proportional to ε⁻¹. We show this result in a constructive manner by proposing a finite element method in a special sparse grid space, which is obtained by an a priori grid optimization process based on the energy norm. Thus, the result of this paper is twofold: First, from a theoretical point of view concerning the complexity of solving elliptic PDEs, a strong tractability result of the order O(ε⁻¹) is given, and, second, we provide a practically usable hierarchical basis finite element method of this complexity O(ε⁻¹), i.e., without logarithmic terms growing exponentially in d, at least for our sparse grid setting with its underlying smoothness requirements.     

Annealed survival asymptotics for Brownian motion in a scaled Poissonian potential

We consider d-dimensional Brownian motion evolving in a scaled Poissonian potential βϕ⁻²(t)V, where β>0 is a constant, ϕ is the scaling function which typically tends to infinity, and V is obtained by translating a fixed non-negative compactly supported shape function to all the particles of a d-dimensional Poissonian point process. We are interested in the large t behavior of the annealed partition sum of Brownian motion up to time t under the influence of the natural Feynman–Kac weight associated to βϕ⁻²(t)V. We prove that for d⩾2 there is a critical scale ϕ and a critical constant β_c(d)>0 such that the annealed partition sum undergoes a phase transition if β crosses β_c(d). In d=1 this picture does not hold true, which can formally be interpreted that on the critical scale ϕ we have β_c(1)=0.     

Ambient Spaces of Dimensional Dual Arcs

A d-dimensional dual arc in PG(n, q) is a higher dimensional analogue of a dual arc in a projective plane. For every prime power q other than 2, the existence of a d-dimensional dual arc (d 2) in PG(n, q) of a certain size implies n d(d + 3)/2 (Theorem 1). This is best possible, because of the recent construction of d-dimensional dual arcs in PG(d(d + 3)/2, q) of size ^d–1 _i=0 q ⁱ, using the Veronesean, observed first by Thas and van Maldeghem (Proposition 7). Another construction using caps is given as well (Proposition 10).     

Non-linear Approximations Using Sets of Finite Cardinality or Finite Pseudo-dimension

We investigate optimal non-linear approximations of multivariate periodic functions with mixed smoothness. In particular, we study optimal approximation using sets of finite cardinality (as measured by the classical entropy number), as well as sets of finite pseudo-dimension (as measured by the non-linear widths introduced by Ratsaby and Maiorov). Approximation error is measured in the L_q(T^d)-sense, where T^d is the d-dimensional torus. The functions to be approximated are in the unit ball SB^r_p, θ of the mixed smoothness Besov space or in the unit ball SW^r_p of the mixed smoothness Sobolev space. For 1<p, q<∞, 0<θ⩽∞ and r>0 satisfying some restrictions, we establish asymptotic orders of these quantities, as well as construct asymptotically optimal approximation algorithms. We particularly prove that for either r>1/p and θ⩾p or r>(1/p−1/q)₊ and θ⩾min{q, 2}, the asymptotic orders of these quantities for the Besov class SB^r_p, θ are both n^−r(log n)^{(d−1)(r+1/2−1/θ)}.     

On tricyclic graphs of a given diameter with minimal energy

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let G(n,d) be the class of tricyclic graphs G on n vertices with diameter d and containing no vertex disjoint odd cycles C_p,C_q of lengths p and q with p+q≡2(mod4). In this paper, we characterize the graphs with minimal energy in G(n,d).