A Gilbert-Varshamov-type bound for lattice packings

A Gilbert-Varshamov-type bound for Euclidean packings was recently found by Nebe and Xing. In this present paper, we derive a Gilbert-Varshamov-type bound for lattice packings by generalizing Rush's approach of combining p-ary codes with the lattice pZn. Specifically, we will exploit suitable sublattices of Zn as well as lattices of number fields in our construction. Our approach allows us to compute the center densities of lattices of moderately large dimensions which compare favorably with the best known densities given in the literature as well as the densities derived directly via Rush's method.     

Measures of pseudorandomness of finite binary lattices,II. (The symmetry measures)

In an earlier paper Gyarmati introduced and studied the symmetry measure of pseudorandomness of binary sequences. The goal of this paper is to extend this definition to two dimensions, i.e., to binary lattices. Three different definitions are proposed to do this extension. The connection between these definitions is analyzed. It is shown that these new symmetry measures are independent of the other measures of pseudorandomness of binary lattices. A binary lattice is constructed for which both the pseudorandom measures of order ℓ (for every fixed ℓ) and the symmetry measures are small. Finally, the symmetry measures are estimated for truly random binary lattices.     

On the number of lattice points in a small sphere and a recursive lattice decoding algorithm

Let L be a lattice in ${\mathbb{R}^n}$ . This paper provides two methods to obtain upper bounds on the number of points of L contained in a small sphere centered anywhere in ${\mathbb{R}^n}$ . The first method is based on the observation that if the sphere is sufficiently small then the lattice points contained in the sphere give rise to a spherical code with a certain minimum angle. The second method involves Gaussian measures on L in the sense of Banaszczyk (Math Ann 296:625–635, 1993). Examples where the obtained bounds are optimal include some root lattices in small dimensions and the Leech lattice. We also present a natural decoding algorithm for lattices constructed from lattices of smaller dimension, and apply our results on the number of lattice points in a small sphere to conclude on the performance of this algorithm.     

Characters of symmetric groups: sharp bounds and applications

We provide new estimates on character values of symmetric groups which hold for all characters and which are in some sense best possible. It follows from our general bound that if a permutation σ∈S _n has at most n ^o(1) cycles of length <m, then |χ(σ)|≤χ(1)^1/m+o(1) for all irreducible characters χ of S _n . This is a far reaching generalization of a result of Fomin and Lulov. We then use our various character bounds to solve a wide range of open problems regarding mixing times of random walks, covering by powers of conjugacy classes, as well as probabilistic and combinatorial properties of word maps. In particular we prove a conjecture of Rudvalis and of Vishne on covering numbers, and a conjecture of Lulov and Pak on mixing times of certain random walks on S _n . Our character-theoretic methods also yield best possible solutions to Waring type problems for alternating groups A _n , showing that if w is a non-trivial word, and n≫0, then every element of A _n is a product of two values of w.     

Every finite lattice can be embedded in a finite partition lattice

Conclusions There are many questions, which arise in connection with the theorem presented. In general, we would like to know more about the class of embeddings of a given lattice in the lattices of all equivalences over finite sets. Some of these problems are studied in [4]. In this paper, an embedding is called normal, if it preserves 0 and 1. Using regraphs, our result can be easily improved as follows: THEOREM.For every lattice L, there exists a positive integer n ₀,such that for every n≥n ₀,there is a normal embedding π: L→Eq(A), where |A|=n. Embedding satisfying special properties are shown in Lemma 3.2 and Basic Lemma 6.2. We hope that our method of regraph powers will produce other interesting results. There is also a question about the effectiveness of finding an embedding of a given lattice. In particular, the proof presented here cannot be directly used to solve the following. Problem. Can the dual of Eq(4) be embedded into Eq(2¹⁰⁰⁰)? Presented by G. Gr?tzer.     

Reliability and efficiency of algorithms for computing the significance of the Mann–Whitney test

Motivated by recent applications of the Mann–Whitney U test to large data sets we took a critical look at current methods for computing its significance. Surprisingly, we found that the two fastest and most popular tools for exact computation of the test significance, Dinneen and Blakesley’s and Harding’s, can exhibit large numerical errors even in moderately large datasets. In addition, another method proposed by Pagano and Tritchler also suffers from a similar numerical instability and can produce inaccurate results. This motivated our development of a new algorithm, mw-sFFT, for the exact computation of the Mann–Whitney test with no ties. Among the class of exact algorithms that are numerically stable, mw-sFFT has the best complexity: O(m ² n) versus O(m ² n ²) for others, where m and n are the two sample sizes. This asymptotic efficiency is also reflected in the practical runtime of the algorithm. In addition, we also present a rigorous analysis of the propagation of numerical errors in mw-sFFT to derive an error guarantee for the values computed by the algorithm. The reliability and efficiency of mw-sFFT make it a valuable tool in compuational applications and we plan to provide open-source libraries for it in C++ and Matlab.     

On the covering multiplicity of lattices

Let the lattice Λ have covering radiusR, so that closed balls of radiusR around the lattice points just cover the space. The covering multiplicityCM(Λ) is the maximal number of times the interiors of these balls overlap. We show that the least possible covering multiplicity for ann-dimensional lattice isn ifn≤8, and conjecture that it exceedsn in all other cases. We determine the covering multiplicity of the Leech lattice and of the latticesI _n, A_n, D_n, E_n and their duals for small values ofn. Although it appears thatCM(I _n)=2 ⁿ⁻¹ ifn≤33, asn → ∞ we haveCM(I _n)∼2.089... ⁿ . The results have application to numerical integration.     

A Shadow identity and an application to isoduality

The identity derived here from the theta transformation law replaces the “Atkin-Lehner identity” when the level decomposes into two factors which are not coprime. An application is given to the study of modular lattices of level 4, connected with modular forms for the classical theta group. CONWAY and Sloane have determined the maximal Hermite number of a self-dual lattice in ℝⁿ for alln ≤ 33, and their result generalizes to the isodual case considered here in most of these dimensions.     

Pareto memetic algorithm for multiple objective optimization with an industrial application

Multiple objective combinatorial optimization problems are difficult to solve and often, exact algorithms are unable to produce optimal solutions. The development of multiple objective heuristics was inspired by the need to quickly produce acceptable solutions. In this paper, we present a new multiple objective Pareto memetic algorithm called PMS^MO. The PMS^MO algorithm incorporates an enhanced fine-grained fitness assignment, a double level archiving process and a local search procedure to improve performance. The performance of PMS^MO is benchmarked against state-of-the-art algorithms using 0–1 multi-dimensional multiple objective knapsack problem from the literature and an industrial scheduling problem from the aluminum industry.     

A Survey of Methods Available for the Numerical Optimization of Continuous Dynamic Systems

There has been significant progress in the development of numerical methods for the determination of optimal trajectories for continuous dynamic systems, especially in the last 20 years. In the 1980s, the principal contribution was new methods for discretizing the continuous system and converting the optimization problem into a nonlinear programming problem. This has been a successful approach that has yielded optimal trajectories for very sophisticated problems. In the last 15–20 years, researchers have applied a qualitatively different approach, using evolutionary algorithms or metaheuristics, to solve similar parameter optimization problems. Evolutionary algorithms use the principle of “survival of the fittest” applied to a population of individuals representing candidate solutions for the optimal trajectories. Metaheuristics optimize by iteratively acting to improve candidate solutions, often using stochastic methods. In this paper, the advantages and disadvantages of these recently developed methods are described and an attempt is made to answer the question of what is now the best extant numerical solution method.     

Efficient algorithms on distributive lattices

We present several efficient algorithms on distributive lattices. They are based on a compact representation of the lattice, called the ideal tree. This allows us to exploit regularities in the structure of distributive lattices. The algorithms include a linear-time algorithm to reconstruct the covering graph of a distributive lattice from its ideal tree, a linear-time incremental algorithm for building the ideal lattice of a poset and a new incremental algorithm for listing the ideals of a poset in a combinatorial Gray code manner (in an code.)     

Hilbert Lattice Equations

There are five known classes of lattice equations that hold in every infinite dimensional Hilbert space underlying quantum systems: generalised orthoarguesian, Mayet’s E_A{\mathcal{E}_A}, Godowski, Mayet–Godowski, and Mayet’s E equations. We obtain a result which opens a possibility that the first two classes coincide. We devise new algorithms to generate Mayet–Godowski equations that allow us to prove that the fourth class properly includes the third. An open problem related to the last class is answered. Finally, we show some new results on the Godowski lattices characterising the third class of equations.     

Shape Optimization Under Width Constraint

We introduce new numerical methods to solve optimization problems among convex bodies which satisfy standard width geometrical constraints. We describe two different numerical approaches to handle width equality and width inequality constraints. To illustrate the efficiency of our method, our algorithms are used to approximate optimal solutions of Meissner’s problem and to confirm two conjectures of Heil.     

Planar subgroup lattices

In this paper we determine all finite groups with planar subgroup lattices. For this, by Kuratowski’s theorem, we have to study subdivisions of the Kuratowski graphs K_3,3 and K₅ in the covering graph of the subgroup lattice of a finite group. It turns out that such a graph is planar if and only if it contains no subdivision of K_3,3. Received April 28, 2005; accepted in final form August 28, 2005.     

Implicational subreducts of <Emphasis Type="Italic">n</Emphasis>-potent commutative residuated lattices

The implicational subreducts of n-potent commutative integral residuated lattices are axiomatized using a new embedding of a BCK-algebra into a commutative integral residuated lattice. The class of {→, 1, ≤ }-subreducts of commutative residuated lattices satisfying x ⁿ ≤ x ^m is also axiomatized, as are other subreduct classes. Presented by R. W. Quackenbush. Received February 3, 2006; accepted in final form May 12, 2006.     

On dual minimum cost flow algorithms

We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general problems (like submodular flow) and is likely to be more efficient in practice.  Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running time of our algorithm by a factor of n.     

Version of the Grothendieck theorem for subspaces of analytic functions in lattices

A version of Grothendieck’s inequality says that any bounded linear operator acting from a Banach lattice X to a Banach lattice Y acts from X(ℓ²) to Y (ℓ²) as well. A similar statement is proved for Hardy-type subspaces in lattices of measurable functions. Namely, let X be a Banach lattice of measurable functions on the circle, and let an operator T act from the corresponding subspace of analytic functions X_A to a Banach lattice Y or, if Y is also a lattice of measurable functions on the circle, to the quotient space Y/Y_A. Under certain mild conditions on the lattices involved, it is proved that T induces an operator acting from X_A(ℓ²) to Y (ℓ²) or to Y/Y_A(ℓ2), respectively. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 327, 2005, pp. 5–16.     

Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a homogeneous polynomial over the sphere; (ii) maximizing a multilinear form over a Cartesian product of spheres; and (iii) maximizing a multiquadratic form over a Cartesian product of spheres. Since these problems are generally intractable, our focus is on designing polynomial-time approximation algorithms for them. By reducing the above problems to that of determining the L ₂-diameters of certain convex bodies, we show that they can all be approximated to within a factor of Ω((log n/n) ^d/2–1) deterministically, where n is the number of variables and d is the degree of the polynomial. This improves upon the currently best known approximation bound of Ω((1/n) ^d/2–1) in the literature. We believe that our approach will find further applications in the design of approximation algorithms for polynomial optimization problems with provable guarantees.     

Local and parallel algorithms for fourth order problems discretized by the Morley–Wang–Xu element method

This paper systematically studies numerical solution of fourth order problems in any dimensions by use of the Morley–Wang–Xu (MWX) element discretization combined with two-grid methods (Xu and Zhou (Math Comp 69:881–909, 1999)). Since the coarse and fine finite element spaces are nonnested, two intergrid transfer operators are first constructed in any dimensions technically, based on which two classes of local and parallel algorithms are then devised for solving such problems. Following some ideas in (Xu and Zhou (Math Comp 69:881–909, 1999)), the intrinsic derivation of error analysis for nonconforming finite element methods of fourth order problems (Huang et al. (Appl Numer Math 37:519–533, 2001); Huang et al. (Sci China Ser A 49:109–120, 2006)), and the error estimates for the intergrid transfer operators, we prove that the discrete energy errors of the two classes of methods are of the sizes O(h + H ²) and O(h + H ²(H/h)^(d−1)/2), respectively. Here, H and h denote respectively the mesh sizes of the coarse and fine finite element triangulations, and d indicates the space dimension of the solution region. Numerical results are performed to support the theory obtained and to compare the numerical performance of several local and parallel algorithms using different intergrid transfer operators.     

Simplicial elimination schemes,extremal lattices and maximal antichain lattices

Fix a partial order P=(X, <). We first show that bipartite orders are sufficient to study structural properties of the lattice of maximal antichains. We show that all orders having the same lattice of maximal antichains can be reduced to one representative order (called the poset of irreducibles by Markowsky [14]). We then define the strong simplicial elimination scheme to characterize orders which have distributive lattice of maximal antichains. The notion of simplicial elimination corresponds to the decomposition process described in [14] for extremal lattices. This notion leads to simple greedy algorithms for distributivity checking, lattice recognition and jump number computation. In the last section, we give several algorithms for lattices and orders.