Two new bounds on the size of binary codes with a minimum distance of three

We prove two new upper bounds on the size of binary codes with a minimum distance of three, namelyA(10, 3)76 andA(11, 3)152.     

Efficient Regular Polygon Dissections

We study the minimum number g(m,n) (respectively, p(m,n)) of pieces needed to dissect a regular m-gon into a regular n-gon of the same area using glass-cuts (respectively, polygonal cuts). First we study regular polygon-square dissections and show that n/2 -2 g(4,n) (n/2) + o(n) and n/4 g(n,4) (n/2) + o(n) hold for sufficiently large n. We also consider polygonal cuts, i.e., the minimum number p(4,n) of pieces needed to dissect a square into a regular n-gon of the same area using polygonal cuts and show that n/4 p(4,n) (n/2) + o(n) holds for sufficiently large n. We also consider regular polygon-polygon dissections and obtain similar bounds for g(m,n) and p(m,n).     

Improved Krasnosel'skii theorems for the dimension of the kernel of a starshaped set

We will establish the following improved Krasnosel'skii theorems for the dimension of the kernel of a starshaped set: For each k and d, 0 k d, define f(d,k) = d+1 if k = 0 and f(d,k) = max{d+1,2d–2k+2} if 1 k d.Theorem 1. Let S be a compact, connected, locally starshaped set in R^d, S not convex. Then for a k with 0 k d, dim ker S k if and only if every f(d, k) lnc points of S are clearly visible from a common k-dimensional subset of S.Theorem 2. Let S be a nonempty compact set in R^d. Then for a k with 0 k d, dim ker S k if and only if every f (d, k) boundary points of S are clearly visible from a common k-dimensional subset of S. In each case, the number f(d, k) is best possible for every d and k.     

Exact bounds for norms of differentiable periodic functions in L metric

Exact values are obtained for the upper bounds on the norms,fL, on the classes W ^(r) H(r =0, 1, 2,...) of r-fold differentiable functions f(x), of periodicity2, for which (f^(r);t)(t),where (t) is a given convex modulus of continuity.Translated from Matematicheskie Zametki, Vol. 2, No. 6, pp. 569–576, December, 1967.     

Bounds for binary multiple covering codes

We study codes that are multiple coverings of the Hamming space and discuss lower and upper bounds onK(n, r, ), the minimum cardinality of a binary code of lengthn such that the Hamming spheres of radiusr centered at the codewords cover at least times. We also study the similar problem of multiple coverings containing repeated words. A table of bounds forn16,r4, 4 is given.     

On Lower Bounds for the Redundancy of Optimal Codes

The problem of providing bounds on the redundancy of an optimal code for a discrete memoryless source in terms of the probability distribution of the source, has been extensively studied in the literature. The attention has mainly focused on binary codes for the case when the most or the least likely source letter probabilities are known. In this paper we analyze the relationships among tight lower bounds on the redundancy r. Let r _D,i(x) be the tight lower bound on r for D-ary codes in terms of the value x of the i-th most likely source letter probability. We prove that _D,i-1(x) _D,i(x) for all possible x and i. As a consequence, we can bound the redundancy when only the value of a probability (but not its rank) is known. Another consequence is a shorter and simpler proof of a known bound. We also provide some other properties of tight lower bounds. Finally, we determine an achievable lower bound on r in terms of the least likely source letter probability for D 3, generalizing the known bound for the case D = 2.     

On Large Values of the Divisor Function

Let d(n) denote the divisor function, and let D(X) denote the maximal value of d(n) for n X. For 0 < z 1, both lower and upper bounds are given for the number of integersn with n X, zD(X) d(n).     

Sur la répartition des valeurs de la fonction d'Euler

Let (x) denote the number of those integers n with (n) x, where denotes the Euler function. Improving on a well-known estimate of Bateman (1972), we show that (x)-Ax R(x), where A=(2)(3)/(6) and R(x) is essentially of the size of the best available estimate for the remainder term in the prime number theorem.     

A Characterization of Some Minihypers and its Application to Linear Codes

Any {f,r- 2+s; r,q}-minihyper includes a hyperplane in PG(r, q) if fr-1 + s 1 + q – 1 for 1 s q – 1, q 3, r 4, where i = (qi + 1 – 1)/ (q – 1 ). A lower bound on f for which an {f, r – 2 + 1; r, q}-minihyper with q 3, r 4 exists is also given. As an application to coding theory, we show the nonexistence of [ n, k, n + 1 – qk – 2 ]q codes for k 5, q 3 for qk – 1 – 2q – 1 < n qk – 1 – q – 1 when k > q – q - \sqrt q + 2$$ " align="middle" border="0"> and for when , which is a generalization of [18, Them. 2.4].     

Asymptotics of the Discrete Spectrum of the Three-Particle Schrödinger Difference Operator on a Lattice

We consider the Hamiltonian H (K) of a system consisting of three bosons that interact through attractive pair contact potentials on a three-dimensional integer lattice. We obtain an asymptotic value for the number N(K,z) of eigenvalues of the operator H₀(K) lying below z0 with respect to the total quasimomentum K0 and the spectral parameter z–0.     

Imbedding of pseudo-Riemannian manifolds in a pseudo-euclidean space

It is proved that every pseudo-Riemannian manifold M _{(p, q)} ⁿ with the C^k metric (3k) has an isometric C^k imbedding in the large in E _{(p, q)} ^{n(n+1)(3n+11)/2} , p(n+1)², q(n+1)².Translated from Matematicheskie Zametki, Vol. 9, No. 2, pp. 193–198, February, 1971.     

Some Upper Bounds on the Covering Radii of Linear Codes Over Fq and Their Applications

We show that the covering radius R of an [n,k,d] code over F_q is bounded above by R n-n _q(k, d/q). We strengthen this bound when R d and find conditions under which equality holds.As applications of this and other bounds, we show that all binary linear codes of lengths up to 15, or codimension up to 9, are normal. We also establish the normality of most codes of length 16 and many of codimension 10. These results have applications in the construction of codes that attain t[n,k,/it>], the smallest covering radius of any binary linear [n,k].We also prove some new results on the amalgamated direct sum (ADS) construction of Graham and Sloane. We find new conditions assuring normality of the ADS; covering radius 1 less than previously guaranteed for ADS of codes with even norms; good covering codes as ADS without the hypothesis of normality, from concepts p- stable and s- stable; codes with best known covering radii as ADS of two, often cyclic, codes (thus retaining structure so as to be suitable for practical applications).     

Approximation under an arc length constraint

Let f C[a, b]. LetP be a subset ofC[a, b], L b – a be a given real number. We say thatp P is a best approximation tof fromP, with arc length constraintL, ifA[p] _b ^a [1 + (p(x)) ²]dx L andp – f q – f for allq P withA[q] L. represents an arbitrary norm onC[a, b]. The constraintA[p] L might be interpreted physically as a materials constraint.In this paper we consider the questions of existence, uniqueness and characterization of constrained best approximations. In addition a bound, independent of degree, is found for the arc length of a best unconstrained Chebyshev polynomial approximation.The work of L. L. Keener is supported by the National Research Council of Canada Grant A8755.     

Order of the best spline approximations of some classes of functions

The rate of decrease of the upper bounds of the best spline approximations E_m,n(f)p with undetermined n nodes in the metric of the space L_p(0, 1) (1p) is studied in a class of functionsf(x) for which f ^m+1 (x)L_q(0, 1)1(1qt8) or var {f(m) (x); 0, 1}1 (m=1, 2, ..., the preceding derivative is assumed absolutely continuous). An exact order of decrease of the mentioned bounds is found as n , and asymptotic formulas are obtained for p= and 1q in the case of an approximation by broken lines (m=1). The simultaneous approximation of the function and its derivatives by spline functions and their appropriate derivatives is also studied.Translated from Matematicheskie Zametki, Vol. 7, No. 1, pp. 31–42, January, 1970.     

On measures that agree on balls

The fundamental result: if and v are two finite Borel measures, defined in the spaceL ^p[0, 1] (1p<) or in C(K) (K is a metric compactum without isolated points), then from the equalities (B)=v(B) for all balls B of radius 1 there follows that =v. In addition, in the spaces C(K) and _p (1p<) from the inequalities (B) v(B) there follows that v.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 177, pp. 122–128, 1989.     

i-perfectm-cycle systems,m ≤ 19

Summary For allm 19 and each meaningful value ofi (2 i m/2), the spectrum problem fori-perfectm-cycle systems is examined.     

Uniform estimates for certain multiplicative properties

Leta (n) denote a multiplicative function taking the values 0, 1 only, and suppose that the setP of primesp witha (p)=1 has density (P)(0<(P)<1). Using sieve results, upper and lower bounds of essentially the same order of magnitude are obtained for #{nxa(n)=1}, their dependence onP being made explicit. Bounds, uniform for squarefreed in an extensive range, for #{nx(d,f(n))=1} withf a multiplicative function in a class containing Euler's function are then deduced.     

On a theorem of lovász on covers inr-partite hypergraphs

A theorem of Lovász asserts that (H)/*(H)r/2 for everyr-partite hypergraphH (where and * denote the covering number and fractional covering number respectively). Here it is shown that the same upper bound is valid for a more general class of hypergraphs: those which admit a partition (V ₁, ...,V _k ) of the vertex set and a partitionp ₁+...+p _k ofr such that |eV _i |p _i r/2 for every edgee and every 1ik. Moreover, strict inequality holds whenr>2, and in this form the bound is tight. The investigation of the ratio /* is extended to some other classes of hypergraphs, defined by conditions of similar flavour. Upper bounds on this ratio are obtained fork-colourable, stronglyk-colourable and (what we call)k-partitionable hypergraphs.Supported by grant HL28438 at MIPG, University of Pennsylvania, and by the fund for the promotion of research at the Technion.This author's research was supported by the fund for the promotion of research at the Technion.     

Upper bound for transversals of tripartite hypergraphs

We prove 2 7/9v for 3-partite hypergraphs. (This is an improvement of the trivial bound 3v.)     

The Legendre transform of two replicas of the Sherrington-Kirkpatrick spin glass model

Summary We prove a variational inequality linking the values of the free energy per site at different temperatures. This inequality is based on the Legendre transform of the free energy of two replicas of the system. We prove that equality holds when1/ and fails when 1/ <1. We deduce from this that the mean entropy per site of the uniform distribution with respect to the distribution of the coupling _i ¹ _i ² = _i between two replicas is null when 01/ and strictly positive when 1/ <1. We exhibit thus a new secondary critical phenomenon within the high temperature region 01. We given an interpretation of this phenomenon showing that the fluctuations of the law of the coupling with the interactions remains strong in the thermodynamic limit when>1/ . We also use our inequality numerically within the low temperature region to improve (slightly) the best previously known lower bounds for the free energy and the ground state energy per site.