An updated table of binary/ternary mixed covering codes

An updated table of K_2,3(b,t;R)—the minimum cardinality of a code with b binary coordinates, t ternary coordinates, and covering radius R—is presented for b + t ≤ 13, R ≤ 3. The results include new explanations of short binary and ternary covering codes, several new constructions and codes, and a general lower bound for R = 1. © 2004 Wiley Periodicals, Inc.     

On the minimum size of binary codes with length 2<Emphasis Type="Italic">R</Emphasis> + 4 and covering radius <Emphasis Type="Italic">R</Emphasis>

The minimum size of a binary code with length n and covering radius R is denoted by K(n, R). For arbitrary R, the value of K(n, R) is known when n ≤  2R +  3, and the corresponding optimal codes have been classified up to equivalence. By combining combinatorial and computational methods, several results for the first open case, K(2R +  4, R), are here obtained, including a proof that K(10, 3) =  12 with 11481 inequivalent optimal codes and a proof that if K(2R +  4, R) <  12 for some R then this inequality cannot be established by the existence of a corresponding self-complementary code.     

Heilbronn's conjecture on Waring's number (mod p)

Let p be a prime k|p−1, t=(p−1)/k and γ(k,p) be the minimal value of s such that every number is a sum of s kth powers . We prove Heilbronn's conjecture that γ(k,p)?k1/2 for t>2. More generally we show that for any positive integer q, γ(k,p)?C(q)k1/q for ?(t)?q. A comparable lower bound is also given. We also establish exact values for γ(k,p) when ?(t)=2. For instance, when t=3, γ(k,p)=a+b−1 where a>b>0 are the unique integers with a²+b²+ab=p, and when t=4, γ(k,p)=a−1 where a>b>0 are the unique integers with a²+b²=p.     

Homoclinic solutions for a class of the second order Hamiltonian systems

We study the existence of homoclinic orbits for the second order Hamiltonian system , where q∈Rⁿ and V∈C¹(R×Rⁿ,R), V(t,q)=-K(t,q)+W(t,q) is T-periodic in t. A map K satisfies the “pinching” condition b₁|q|²?K(t,q)?b₂|q|², W is superlinear at the infinity and f is sufficiently small in L²(R,Rⁿ). A homoclinic orbit is obtained as a limit of 2kT-periodic solutions of a certain sequence of the second order differential equations.     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

Derivations and right ideals of algebras

Let R be a K-algebra acting densely on V_D, where K is a commutative ring with unity and V is a right vector space over a division K-algebra D. Let ρ be a nonzero right ideal of R and let f(X₁,…,X_t) be a nonzero polynomial over K with constant term 0 such that μR≠0 for some coefficient μ of f(X₁,…,X_t). Suppose that d:R→R is a nonzero derivation. It is proved that if rankd(f(x₁,…,x_t))?m for all x₁,…,x_t∈ρ and for some positive integer m, then either ρ is generated by an idempotent of finite rank or d=ad(b) for some b∈End(V_D) of finite rank. In addition, if f(X₁,…,X_t) is multilinear, then b can be chosen such that rank(b)?2(6t+13)m+2.     

Heteroclinic solutions for a class of the second order Hamiltonian systems

We shall be concerned with the existence of heteroclinic orbits for the second order Hamiltonian system , where q∈Rn and V∈C¹(R×Rn,R), V?0. We will assume that V and a certain subset M⊂Rn satisfy the following conditions. M is a set of isolated points and #M?2. For every sufficiently small ε>0 there exists δ>0 such that for all (t,z)∈R×Rn, if d(z,M)?ε then −V(t,z)?δ. The integrals , z∈M, are equi-bounded and −V(t,z)→∞, as |t|→∞, uniformly on compact subsets of Rn?M. Our result states that each point in M is joined to another point in M by a solution of our system.     

Construction of determinantal representation of trigonometric polynomials

For a pair of n×n Hermitian matrices H and K, a real ternary homogeneous polynomial defined by F(t,x,y)=det(tI_n+xH+yK) is hyperbolic with respect to (1,0,0). The Fiedler conjecture (or Lax conjecture) is recently affirmed, namely, for any real ternary hyperbolic polynomial F(t,x,y), there exist real symmetric matrices S₁ and S₂ such that F(t,x,y)=det(tI_n+xS₁+yS₂). In this paper, we give a constructive proof of the existence of symmetric matrices for the ternary forms associated with trigonometric polynomials.     

Good equidistant codes constructed from certain combinatorial designs

An (n,M,d;q) code is called equidistant code if the Hamming distance between any two codewords is d. It was proved that for any equidistant (n,M,d;q) code, d?nM(q-1)/(M-1)q(=d_opt, say). A necessary condition for the existence of an optimal equidistant code is that d_opt be an integer. If d_opt is not an integer, i.e. the equidistant code is not optimal, then the code with d=⌊d_opt⌋ is called good equidistant code, which is obviously the best possible one among equidistant codes with parameters n,M and q. In this paper, some constructions of good equidistant codes from balanced arrays and nested BIB designs are described.     

Asymmetric Binary Covering Codes

An asymmetric binary covering code of length n and radius R is a subset of the n-cube Q_n such that every vector xQ_n can be obtained from some vector c by changing at most R 1's of c to 0's, where R is as small as possible. K⁺(n,R) is defined as the smallest size of such a code. We show K⁺(n,R)Θ(2ⁿ/n^R) for constant R, using an asymmetric sphere-covering bound and probabilistic methods. We show K⁺(n,n− )= +1 for constant coradius iff n ( +1)/2. These two results are extended to near-constant R and , respectively. Various bounds on K⁺ are given in terms of the total number of 0's or 1's in a minimal code. The dimension of a minimal asymmetric linear binary code ([n,R]⁺-code) is determined to be min{0,n−R}. We conclude by discussing open problems and techniques to compute explicit values for K⁺, giving a table of best-known bounds.     

Lower bounds on covering codes via partition matrices

Let Kq(n,R) denote the minimal cardinality of a q-ary code of length n and covering radius R. Let σq(n,s;r) denote the minimal cardinality of a q-ary code of length n, which is s-surjective with radius r. In order to lower-bound Kq(n,n−2) and σq(n,s;s−2) we introduce partition matrices and their transversals. Our approach leads to a short new proof of a classical bound of Rodemich on Kq(n,n−2) and to the new bound Kq(n,n−2)?3q−2n+2, improving the first iff 5?n<q?2n−4. We determine Kq(q,q−2)=q−2+σ₂(q,2;0) if q?10. Moreover, we obtain the new powerful recursive bound Kq+1(n+1,R+1)?min{2(q+1),Kq(n,R)+1}.     

Bass’ NK groups and cdh-fibrant Hochschild homology

The K-theory of a polynomial ring R[t] contains the K-theory of R as a summand. For R commutative and containing ?, we describe K _*(R[t])/K _*(R) in terms of Hochschild homology and the cohomology of Kähler differentials for the cdh topology. We use this to address Bass’ question, whether K _n (R)=K _n (R[t]) implies K _n (R)=K _n (R[t ₁,t ₂]). The answer to this question is affirmative when R is essentially of finite type over the complex numbers, but negative in general.     

Minimal tori with low nullity

The nullity of a minimal submanifold M⊂Sn is the dimension of the nullspace of the second variation of the area functional. That space contains as a subspace the effect of the group of rigid motions SO(n+1) of the ambient space, modulo those motions which preserve M, whose dimension is the Killing nullitykn(M) of M. In the case of 2-dimensional tori M in S³, there is an additional naturally-defined 2-dimensional subspace that contributes to the nullity; the dimension of the sum of the action of the rigid motions and this space is the natural nullitynnt(M). In this paper we will study minimal tori in S³ with natural nullity less than 8. We construct minimal immersions of the plane R² in S³ that contain all possible examples of tori with nnt(M)<8. We prove that the examples of Lawson and Hsiang with kn(M)=5 also have nnt(M)=5, and we prove that if the nnt(M)?6 then the group of isometries of M is not trivial.     

Bounds for short covering codes and reactive tabu search

Given a prime power q, c_q(n,R) denotes the minimum cardinality of a subset H in such that every word in this space differs in at most R coordinates from a multiple of a vector in H. In this work, two new classes of short coverings are established. As an application, a new optimal record-breaking result on the classical covering code is obtained by using short covering. We also reformulate the numbers c_q(n,R) in terms of dominating set on graphs. Departing from this reformulation, the reactive tabu search (a variation of tabu search heuristics) is developed to obtain new upper bounds on c_q(n,R). The algorithm is described and conclusions on the results are drawn; they identify the advantages of using the reactive mechanism for this problem. Tables of lower and upper bounds on c_q(n,R), q=3,4, n≤7, and R≤3, are also presented.     

Existence of fast positive wavefronts for a non-local delayed reaction-diffusion equation

We establish the existence of a continuous family of fast positive wavefronts u(t,x)=?(x+ct), ?(−∞)=0, ?(+∞)=κ, for the non-local delayed reaction-diffusion equation . Here 0 and κ>0 are fixed points of g∈C²(R₊,R₊) and the non-negative K is such that is finite for every real λ. We also prove that the fast wavefronts are non-monotone if .     

A construction of Gray codes inducing complete graphs

A binary Gray code G(n) of length n, is a list of all 2ⁿn-bit codewords such that successive codewords differ in only one bit position. The sequence of bit positions where the single change occurs when going to the next codeword in G(n), denoted by S(n)?s₁,s₂,…,s_2ⁿ-1, is called the transition sequence of the Gray code G(n). The graph G_G(n) induced by a Gray code G(n) has vertex set {1,2,…,n} and edge set {{s_i,s_i+1}:1?i?2ⁿ-2}. If the first and the last codeword differ only in position s_2ⁿ, the code is cyclic and we extend the graph by two more edges {s_2ⁿ-1,s_2ⁿ} and {s_2ⁿ,s₁}. We solve a problem of Wilmer and Ernst [Graphs induced by Gray codes, Discrete Math. 257 (2002) 585-598] about a construction of an n-bit Gray code inducing the complete graph K_n. The technique used to solve this problem is based on a Gray code construction due to Bakos [A. Ádám, Truth Functions and the Problem of their Realization by Two-Terminal Graphs, Akadémiai Kiadó, Budapest, 1968], and which is presented in D.E. Knuth [The Art of Computer Programming, vol. 4, Addison-Wesley as part of “fascicle” 2, USA, 2005].     

Optimal binary covering codes of length 2j

The minimum size of a binary covering code of length n and covering radius r is denoted by K(n,r), and codes of this length are called optimal. For j > 0 and n = 2^j, it is known that K(n,1) = 2 · K(n?1,1) = 2^{n ? j}. Say that two binary words of length n form a duo if the Hamming distance between them is 1 or 2. In this paper, it is shown that each optimal binary covering code of length n = 2^j, j > 0, and covering radius 1 is the union of duos in just one way, and that the closed neighborhoods of the duos form a tiling of the set of binary words of length n. Methods of constructing such optimal codes from optimal covering codes of length n ? 1 (that is, perfect single‐error‐correcting codes) are discussed. The paper ends with the construction of an optimal covering code of length 16 that does not contain an extension of any optimal covering code of length 15. © 2005 Wiley Periodicals, Inc. J Combin Designs     

The intersection of essential approximate point spectra of operator matrices

When A∈B(H) and B∈B(K) are given, we denote by MC the operator acting on the infinite-dimensional separable Hilbert space H⊕K of the form . In this paper, it is shown that there exists some operator C∈B(K,H) such that MC is upper semi-Fredholm and ind(MC)?0 if and only if there exists some left invertible operator C∈B(K,H) such that MC is upper semi-Fredholm and ind(MC)?0. A necessary and sufficient condition for MC to be upper semi-Fredholm and ind(MC)?0 for some C∈Inv(K,H) is given, where Inv(K,H) denotes the set of all the invertible operators of B(K,H). In addition, we give a necessary and sufficient condition for MC to be upper semi-Fredholm and ind(MC)?0 for all C∈Inv(K,H).     

Sharp bounds for the number of roots of univariate fewnomials

Let K be a field and t?0. Denote by Bm(t,K) the supremum of the number of roots in K^?, counted with multiplicities, that can have a non-zero polynomial in K[x] with at most t+1 monomial terms. We prove, using an unified approach based on Vandermonde determinants, that Bm(t,L)?t²Bm(t,K) for any local field L with a non-archimedean valuation v:L→R∪{∞} such that vZ≠0_|≡0 and residue field K, and that Bm(t,K)?(t²−t+1)(pf−1) for any finite extension K/Qp with residual class degree f and ramification index e, assuming that p>t+e. For any finite extension K/Qp, for p odd, we also show the lower bound Bm(t,K)?(2t−1)(pf−1), which gives the sharp estimation Bm(2,K)=3(pf−1) for trinomials when p>2+e.     

Infinite Multiplicity of Positive Entire Solutions for a Semilinear Elliptic Equation

We establish that the elliptic equation Δu+K(x)u^p+μf(x)=0 in Rⁿ has infinitely many positive entire solutions for small μ?0 under suitable conditions on K, p, and f.