New bounds of permutation codes under Hamming metric and Kendall’s $$\tau $$-metric

Permutation codes are widely studied objects due to their numerous applications in various areas, such as power line communications, block ciphers, and the rank modulation scheme for flash memories. Several kinds of metrics are considered for permutation codes according to their specific applications. This paper concerns some improvements on the bounds of permutation codes under Hamming metric and Kendall’s \(\tau \)-metric respectively, using mainly a graph coloring approach. Specifically, under Hamming metric, we improve the Gilbert–Varshamov bound asymptotically by a factor n, when the minimum Hamming distance d is fixed and the code length n goes to infinity. Under Kendall’s \(\tau \)-metric, we narrow the gap between the known lower bounds and upper bounds. Besides, we also obtain some sporadic results under Kendall’s \(\tau \)-metric for small parameters.     

On maximal Spherical codes II

We consider spherical codes attaining the Levenshtein upper bounds on the cardinality of codes with prescribed maximal inner product. We prove that the even Levenshtein bounds can be attained only by codes which are tight spherical designs. For every fixed n ≥ 5, there exist only a finite number of codes attaining the odd bounds. We derive different expressions for the distance distribution of a maximal code. As a by-product, we obtain a result about its inner products. We describe the parameters of those codes meeting the third Levenshtein bound, which have a regular simplex as a derived code. Finally, we discuss a connection between the maximal codes attaining the third bound and strongly regular graphs. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 316–326, 1999     

Polynomial techniques for investigation of spherical designs

We investigate the structure of spherical τ-designs by applying polynomial techniques for investigation of some inner products of such designs. Our approach can be used for large variety of parameters (dimension, cardinality, strength). We obtain new upper bounds for the largest inner product, lower bounds for the smallest inner product and some other bounds. Applications are shown for proving nonexistence results either in small dimensions and in certain asymptotic process. In particular, we complete the classification of the cardinalities for which 3-designs on exist for n = 8, 13, 14 and 18. We also obtain new asymptotic lower bound on the minimum possible odd cardinality of 3-designs.      

Error estimates for low rate codes

Summary Gallager [1] and Gallager, Shannon, Berlekamp [2] establish exponentially decreasing upper and lower bounds, respectively, on the error of the best codes for fixed code rates R smaller than the capacity for the standard channels (stationary finite alphabet channels without memory). These bounds happen to coincide up to the first order for rates near to the capacity.The authors of [2] regret that their proof of the lower bound cannot be extended to infinite alphabet channels or nonstationary channels because of the use of fixed composition codes (while the proofs of the upper estimate can be easily transferred to those channels).Changing parts of the proof in [2], we automatically obtain estimates of the same type as in [2] for the latter channels.Furthermore, as a matter of minor importance, we show that the order of coincidence of upper and lower bound for the high rates R can be rigorously improved.I would like to thank Johan H. B. Kemperman for a very stimulating discussion and for pointing out a gap in my original proof.     

Improved Bounds for Ternary Linear Codes of Dimension 8 Using Tabu Search

In this paper, new codes of dimension 8 are presented which give improved bounds on the maximum possible minimum distance of ternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Twenty three codes are given which improve or establish the bounds for ternary codes. In addition, a table of upper and lower bounds for d ₃(n, 8) is presented for n 200.     

A new asymptotic bound of the minimum possible odd cardinality of spherical (2k−1)-designs

We apply polynomial techniques to investigate the structure of spherical designs in an asymptotic process with fixed odd strength while the dimension and odd cardinality tend to infinity in a certain relation. Our bounds for the extreme inner products of special points in such designs allow new lower bounds on the minimum possible odd cardinality.     

Extremal polynomials for obtaining bounds for spherical codes and designs

We investigate two extremal problems for polynomials giving upper bounds for spherical codes and for polynomials giving lower bounds for spherical designs, respectively. We consider two basic properties of the solutions of these problems. Namely, we estimate from below the number of double zeros and find zero Gegenbauer coefficients of extremal polynomials. Our results allow us to search effectively for such solutions using a computer. The best polynomials we have obtained give substantial improvements in some cases on the previously known bounds for spherical codes and designs. Some examples are given in Section 6. This research was partially supported by the Bulgarian NSF under Contract I-35/1994.     

A o(n logn) algorithm for LP knapsacks with GUB constraints

A specialization of the dual simplex method is developed for solving the linear programming (LP) knapsack problem subject to generalized upper bound (GUB) constraints. The LP/GUB knapsack problem is of interest both for solving more general LP problems by the dual simplex method, and for applying surrogate constraint strategies to the solution of 0–1 Multiple Choice integer programming problems. We provide computational bounds for our method of o(n logn), wheren is the total number of problem variables. These bounds reduce the previous best estimate of the order of complexity of the LP/GUB knapsack problem (due to Witzgall) and provide connections to computational bounds for the ordinary knapsack problem.We further provide a variant of our method which has only slightly inferior worst case bounds, yet which is ideally suited to solving integer multiple choice problems due to its ability to post-optimize while retaining variables otherwise weeded out by convex dominance criteria.     

Flat tori, lattices and bounds for commutative group codes

We show that commutative group spherical codes in R ⁿ , as introduced by D. Slepian, are directly related to flat tori and quotients of lattices. As consequence of this view, we derive new results on the geometry of these codes and an upper bound for their cardinality in terms of minimum distance and the maximum center density of lattices and general spherical packings in the half dimension of the code. This bound is tight in the sense it can be arbitrarily approached in any dimension. Examples of this approach and a comparison of this bound with Union and Rankin bounds for general spherical codes is also presented.     

Discrepancy, separation and Riesz energy of finite point sets on the unit sphere

For $d \geqslant 2,$ we consider asymptotically equidistributed sequences of $\mathbb S^d$ codes, with an upper bound $\operatorname{\boldsymbol{\delta}}$ on spherical cap discrepancy, and a lower bound Δ on separation. For such sequences, if 0?<?s?<?d, then the difference between the normalized Riesz s energy of each code, and the normalized s-energy double integral on the sphere is bounded above by $\operatorname{O}\big(\operatorname{\boldsymbol{\delta}}^{1-s/d}\,\Delta^{-s}\,N^{-s/d}\big),$ where N is the number of code points. For well separated sequences of spherical codes, this bound becomes $\operatorname{O}\big(\operatorname{\boldsymbol{\delta}}^{1-s/d}\big).$ We apply these bounds to minimum energy sequences, sequences of well separated spherical designs, sequences of extremal fundamental systems, and sequences of equal area points.     

Bounds on the Dimensions of 2‐Spontaneous Emission Error Designs

Quantum jump codes are quantum error‐correcting codes which correct errors caused by quantum jumps. A t‐spontaneous emission error design (t‐SEED) was introduced by Beth et al. in 2003 [T. Beth, C. Charnes, M. Grassl, G. Alber, A. Delgado, and M. Mussinger, A new class of designs which protect against quantum jumps, Des Codes Cryptogr 29 (2003), 51–70.] to construct quantum jump codes. The number of designs (dimension) in a t‐SEED corresponds to the number of orthogonal basis states in a quantum jump code. A nondegenerate t‐SEED is optimal if it has the largest possible dimension. In this paper, we investigate the bounds on the dimensions of 2‐SEEDs systematically. The exact dimensions of optimal 2‐ SEEDs are almost determined, with five possible exceptions in doubt. General upper bounds on dimensions of 2‐ SEEDs are demonstrated, the corresponding leave graphs are described, and several exceptional cases are studied in details. Meanwhile, we employ 2‐homogenous groups to obtain new lower bounds on the dimensions of 2‐ SEEDs for prime power orders v and general block sizes k.     

Bounds and constructions of <Emphasis Type="Italic">t</Emphasis>-spontaneous emission error designs

The combinatorial aspects of quantum codes were demonstrated in the study of decay processes of certain quantum systems used in the newly emerging field of quantum computing. Among them, the configuration of t-spontaneous emission error design (t-SEED) was proposed to correct errors caused by quantum jumps. The number of designs (dimension) in a t-SEED corresponds to the number of orthogonal basis states in a quantum jump code. In this paper the upper and lower bounds on the dimensions of 3-\((v,\,4;\,m)\) SEEDs are studied and the necessary and sufficient conditions for 3-SEEDs attaining the upper bounds are described. Several new combinatorial constructions are presented for general t-SEEDs and lots of t-SEEDs of new parameters with \(t\ge 3\) are shown to exist.     

Nodal Domains of Maass Forms I

This paper deals with some questions that have received a lot of attention since they were raised by Hejhal and Rackner in their 1992 numerical computations of Maass forms. We establish sharp upper and lower bounds for the L ²-restrictions of these forms to certain curves on the modular surface. These results, together with the Lindelof Hypothesis and known subconvex L ^∞-bounds are applied to prove that locally the number of nodal domains of such a form goes to infinity with its eigenvalue.     

Johnson type bounds on constant dimension codes

Very recently, an operator channel was defined by Koetter and Kschischang when they studied random network coding. They also introduced constant dimension codes and demonstrated that these codes can be employed to correct errors and/or erasures over the operator channel. Constant dimension codes are equivalent to the so-called linear authentication codes introduced by Wang, Xing and Safavi-Naini when constructing distributed authentication systems in 2003. In this paper, we study constant dimension codes. It is shown that Steiner structures are optimal constant dimension codes achieving the Wang-Xing-Safavi-Naini bound. Furthermore, we show that constant dimension codes achieve the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures. Then, we derive two Johnson type upper bounds, say I and II, on constant dimension codes. The Johnson type bound II slightly improves on the Wang-Xing-Safavi-Naini bound. Finally, we point out that a family of known Steiner structures is actually a family of optimal constant dimension codes achieving both the Johnson type bounds I and II.      

Estimating linear functionals of a sparse family of Poisson means

Assume that we observe a sample of size n composed of p-dimensional signals, each signal having independent entries drawn from a scaled Poisson distribution with an unknown intensity. We are interested in estimating the sum of the n unknown intensity vectors, under the assumption that most of them coincide with a given “background” signal. The number s of p-dimensional signals different from the background signal plays the role of sparsity and the goal is to leverage this sparsity assumption in order to improve the quality of estimation as compared to the naive estimator that computes the sum of the observed signals. We first introduce the group hard thresholding estimator and analyze its mean squared error measured by the squared Euclidean norm. We establish a nonasymptotic upper bound showing that the risk is at most of the order of \(\sigma ^2(sp+s^2\sqrt{p}\log ^{3/2}(np))\). We then establish lower bounds on the minimax risk over a properly defined class of collections of s-sparse signals. These lower bounds match with the upper bound, up to logarithmic terms, when the dimension p is fixed or of larger order than \(s^2\). In the case where the dimension p increases but remains of smaller order than \(s^2\), our results show a gap between the lower and the upper bounds, which can be up to order \(\sqrt{p}\).     

Mystery of point charges

We discuss the problem of finding an upper bound for the numberof equilibrium points of a potential of several fixed pointcharges in ⁿ. This question goes back to J. C. Maxwell and M.Morse. Using fewnomial theory we show that for a given numberof charges there exists an upper bound independent of the dimension,and show it to be at most 12 for three charges. We conjecturean exact upper bound for a given configuration of non-negativecharges in terms of its Voronoi diagram, and prove it asymptotically.     

Bounds for codes and designs in complex subspaces

We introduce the concepts of complex Grassmannian codes and designs. Let $\mathcal{G}_{m,n}$ denote the set of m-dimensional subspaces of ? ⁿ : then a code is a finite subset of $\mathcal{G}_{m,n}$ in which few distances occur, while a design is a finite subset of $\mathcal{G}_{m,n}$ that polynomially approximates the entire set. Using Delsarte’s linear programming techniques, we find upper bounds for the size of a code and lower bounds for the size of a design, and we show that association schemes can occur when the bounds are tight. These results are motivated by the bounds for real subspaces recently found by Bachoc, Bannai, Coulangeon and Nebe, and the bounds generalize those of Delsarte, Goethals and Seidel for codes and designs on the complex unit sphere.     

A Paradox Concerning Shrinkage Estimators: Should a Known Scale Parameter Be Replaced by an Estimated Value in the Shrinkage Factor?

When estimating, under quadratic loss, the location parameterθof a spherically symmetric distribution with known scale parameter, we show that it may be that the common practice of utilizing the residual vector as an estimate of the variance is preferable to using the known value of the variance. In the context of Stein-like shrinkage estimators, we exhibit sufficient conditions on the spherical distributions for which this paradox occurs. In particular, we show that it occurs fort-distributions when the dimension of the residual vector is sufficiently large. The main tools in the development are upper and lower bounds on the risks of the James–Stein estimators which are exact atθ=0.     

O the volume growth of the hyperbolic regular $$\varvec{}$$-simplex

In this paper we give lower and upper bounds for the volume growth of a regular hyperbolic simplex, namely for the ratio of the n-dimensional volume of a regular simplex and the \((n-1)\)-dimensional volume of its facets. In addition to the methods of U. Haagerup and M. Munkholm we use a third volume form based on the hyperbolic orthogonal coordinates of a body. In the case of the ideal, regular simplex our upper bound gives the best known upper bound. On the other hand, also in the ideal case our general lower bound, improved the best known one for \(n=3\).