On the minimum average distance of binary constant weight codes

Let β(n,M,w) denote the minimum average Hamming distance of a binary constant weight code with length n, size M and weight w. In this paper, we study the problem of determining β(n,M,w). Using the methods from coding theory and linear programming, we derive several lower bounds on the average Hamming distance of a binary constant weight code. These lower bounds enable us to determine the exact value for β(n,M,w) in several cases.     

Constructing permutation arrays from groups

Let M(n, d) be the maximum size of a permutation array on n symbols with pairwise Hamming distance at least d. We use various combinatorial, algebraic, and computational methods to improve lower bounds for M(n, d). We compute the Hamming distances of affine semilinear groups and projective semilinear groups, and unions of cosets of AGL(1, q) and PGL(2, q) with Frobenius maps to obtain new, improved lower bounds for M(n, d). We give new randomized algorithms. We give better lower bounds for M(n, d) also using new theorems concerning the contraction operation. For example, we prove a quadratic lower bound for \(M(n,n-2)\) for all \(n\equiv 2 \pmod 3\) such that \(n+1\) is a prime power.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

The curvature of the Sasaki metric of tangent sphere bundles

We study the sectional curvaturesK of the Sasaki metric of tangent sphere bundles over spaces of constant curvatureK(T ₁(M ⁿ, K)). We give precise bounds on the variation of the Ricci curvature and a bound on the scalar curvature ofT ₁ (M ⁿ, K) that is uniform onK. In an appendix we calculate and give lower bounds for the lengths of closed geodesics onT ₁ S ⁿ. titles.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 132–145.     

Explicit Cost Bounds of Algorithms for Multivariate Tensor Product Problems

We study multivariate tenser product problems in the worst case and average case settings. They are defined on functions of d variables. For arbitrary d, we provide explicit upper bounds on the costs of algorithms which compute an ϵ-approximation to the solution. The cost bounds are of the form (c(d) + 2)β₁(β₂ + β₃(ln 1/ϵ)/(d − 1))^{β₄(d − 1)}(1/ϵ)^β₅. Here c(d) is the cost of one function evaluation (or one linear functional evaluation), and β_i′s do not depend on d; they are determined by the properties of the problem for d = 1. For certain tensor product problems, these cost bounds do not exceed c(d)Kϵ^−p for some numbers K and p, both independent of d. However, the exponents p which we obtain are too large. We apply these general estimates to certain integration and approximation problems in the worst and average case settings. We also obtain an upper bound, which is independent of d, for the number, n(ϵ, d), of points for which discrepancy (with unequal weights) is at most ϵ, n(ϵ, d) ≤ 7.26ϵ^−2.454, ∀d, ϵ ≤ 1.     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

On reformulated Zagreb indices

The first and second reformulated Zagreb indices are defined respectively in terms of edge-degrees as EM₁(G)=∑_e∈Edeg(e)² and EM₂(G)=∑_e∼fdeg(e)deg(f), where deg(e) denotes the degree of the edge e, and e∼f means that the edges e and f are adjacent. We give upper and lower bounds for the first reformulated Zagreb index, and lower bounds for the second reformulated Zagreb index. Then we determine the extremal n-vertex unicyclic graphs with minimum and maximum first and second Zagreb indices, respectively. Furthermore, we introduce another generalization of Zagreb indices.     

Asymptotic estimates of sums involving the Moebius function

Let p(n) denote the smallest prime factor of an integer n>1 and let p(1)=∞. We study the asymptotic behavior of the sum M(x,y)=Σ_{1≤n≤x,p(n)>y}μ(n) and use this to estimate the size of A(x)=max_|f|≤1|Σ_2≤n<xμ(n)f(p(n))|, where μ(n) is the Moebius function. Applications of bounds for A(x), M(x,y) and similar quantities are discussed.     

On Cohen braids

For a general connected surface M and an arbitrary braid α from the surface braid group B _n?1(M), we study the system of equations d ₁ β = … = d _n β = α, where the operation d _i is the removal of the ith strand. We prove that for M ≠ S ² and M ≠ ?P², this system of equations has a solution β ∈ B _n (M) if and only if d ₁ α = … = d _n?1 α. We call the set of braids satisfying the last system of equations Cohen braids. We study Cohen braids and prove that they form a subgroup. We also construct a set of generators for the group of Cohen braids. In the cases of the sphere and the projective plane we give some examples for a small number of strands.     

Basis theorems for continuous n-colorings

This article is devoted to the study of continuous colorings of the n-element subsets of a Polish space.The homogeneity numberhm(c) of an n-coloring c:n[X]→2 is the least size of a family of c-homogeneous sets that covers X. An n-coloring is uncountably homogeneous if hm(c)>ℵ₀. Answering a question of B. Miller, we show that for every n>1 there is a finite family B of continuous n-colorings on ω² such that every uncountably homogeneous, continuous n-coloring on a Polish space contains a copy of one of the colorings from B. We also give upper and lower bounds for the minimal size of such a basisB.     

Lower bound inequalities for norms of symmetrized tensor powers

Let V be a complex inner product space of positive dimension m with inner product 〈·,·〉, and let T_n(V) denote the set of all n-linear complex-valued functions defined on V×V×?×V (n-copies). By S_n(V) we mean the set of all symmetric members of T_n(V). We extend the inner product, 〈·,·〉, on V to T_n(V) in the usual way, and we define multiple tensor products A₁⊗A₂⊗?⊗A_n and symmetric products A₁·A₂?A_n, where q₁,q₂,…,q_n are positive integers and A_i∈T_qi(V) for each i, as expected. If A∈S_n(V), then A^k denotes the symmetric product A·A?A where there are k copies of A. We are concerned with producing the best lower bounds for ‖A^k‖², particularly when n=2. In this case we are able to show that ‖A^k‖² is a symmetric polynomial in the eigenvalues of a positive semi-definite Hermitian matrix, M_A, that is closely related to A. From this we are able to obtain many lower bounds for ‖A^k‖². In particular, we are able to show that if ω denotes 1/r where r is the rank of M_A, and , then

     

An improvement of the Griesmer bound for some small minimum distances

In this paper we give some lower and upper bounds for the smallest length n(k, d) of a binary linear code with dimension k and minimum distance d. The lower bounds improve the known ones for small d. In the last section we summarize what we know about n(8, d).     

The Hilbert function of a maximal Cohen-Macaulay module

We study Hilbert functions of maximal CM modules over CM local rings. When A is a hypersurface ring with dimension d>0, we show that the Hilbert function of M with respect to is non-decreasing. If A=Q/(f) for some regular local ring Q, we determine a lower bound for e₀(M) and e₁(M) and analyze the case when equality holds. When A is Gorenstein a relation between the second Hilbert coefficient of M, A and S^A(M)= (Syz^A₁(M*))* is found when G(M) is CM and depthG(A)≥d−1. We give bounds for the first Hilbert coefficients of the canonical module of a CM local ring and analyze when equality holds. We also give good bounds on Hilbert coefficients of M when M is maximal CM and G(M) is CM.     

Multivariable monotonic optimization over multivalued logics and rectangular design lattices

A minimum dichotomous direct search procedure is given for finding the optimum combination of N variables, each having M(n) possible values, when a certain monotonicity condition is satisfied. The least upper bound on the number of objective function evaluations is 1 + Σ^N_n=1Q(n), where Q(n) is defined by 2^Q(n)-1<M(n) < 2^Q(n), whereas the total number of possibilities is Π^N_R=1M(n). An example shows where the procedure applies to restricted problems in multivalued logic and engineering design.     

A new class of multiset Wilf equivalent pairs

We say the pair of patterns (σ,τ) is multiset Wilf equivalent if, for any multiset M, the number of permutations of M that avoid σ is equal to the number of permutations of M that avoid τ. In this paper, we find a large new class of multiset Wilf equivalent pairs, namely, the pair (σ_n-2(n-1)n, σ_n-2n(n-1)), for n?3 and σ_n-2 a permutation of {1^x₁,2^x₂,…,(n-2)^x_n-2}. It is the most general multiset Wilf equivalence result to date.     

Expansions for the Distribution of the Maximum from Distributions with a Power Tail when a Trend is Present

We give expansions about the second type of extreme value (EV2 or Fréchet) distribution in inverse powers of the sample size, n?+?1, for the sample maximum M _n when the jth observation is μ(j/n)?+?e _j , μ(·) is any smooth trend function and the residuals e ₀, ..., e _n are independent with a common Pareto type distribution. We show that the distribution of the maximum has a triple expansion in inverse powers of n. We give the likelihood for this case and illustrate its practical value using simulated and real data sets.     

Sharp bounds for integral means

We introduce a bound M of f, ‖f‖_∞?M?2‖f‖_∞, which allows us to give for 0?p<∞ sharp upper bounds, and for −∞<p<0 sharp lower bounds for the average of |f|^p over E if the average of f over E is zero. As an application we give a new proof of Grüss's inequality estimating the covariance of two random variables. We also give a new estimate for the error term in the trapezoidal rule.     

Degrees of the Elliptic Teichmüller Lift

The purpose of this paper is to find upper bounds for the degrees, or equivalently, for the order of the poles at O, of the coordinate functions of the elliptic Teichmüller lift of an ordinary elliptic curve over a perfect field of characteristic p. We prove the following bounds:ord₀(x_n)?−(n+2)pⁿ+npⁿ⁻¹, ord₀(y_n)?−(n+3)pⁿ+npⁿ⁻¹. Also, we prove that the bound for x_n is not the exact order if, and only if, p divides (n+1), and the bound for y_n is not the exact order if, and only if, p divides (n+1)(n+2)/2. Finally, we give an algorithm to compute the reduction modulo p³ of the canonical lift for p≠2,3.     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.