Error Correcting Sequence and Projective De Bruijn Graph

Let X be a finite set of q elements, and n, K, d be integers. A subset C ⊂ X ⁿ is an (n, K, d) error-correcting code, if #(C) = K and its minimum distance is d. We define an (n, K, d) error-correcting sequence over X as a periodic sequence {a _i } _i=0,1,... (a _i ∈ X) with period K, such that the set of all consecutive n-tuples of this sequence form an (n, K, d) error-correcting code over X. Under a moderate conjecture on the existence of some type of primitive polynomials, we prove that there is a error correcting sequence, such that its code-set is the q-ary Hamming code with 0 removed, for q > 2 being a prime power. For the case q = 2, under a similar conjecture, we prove that there is a error-correcting sequence, such that its code-set supplemented with 0 is the subset of the binary Hamming code [2 ^m  − 1, 2 ^m  − 1 − m, 3] obtained by requiring one specified coordinate being 0. Received: October 27, 2005. Final Version received: December 31, 2007     

Order and chaos in Hofstadter's Q(n) sequence

A number of observations are made on Hofstadter's integer sequence defined by Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), for n > 2, and Q(1) = Q(2) = 1. On short scales, the sequence looks chaotic. It turns out, however, that the Q(n) can be grouped into a sequence of generations. The k‐th generation has 2^k members that have “parents” mostly in generation k − 1 and a few from generation k − 2. In this sense, the sequence becomes Fibonacci type on a logarithmic scale. The variance of S(n) = Q(n) − n/2, averaged over generations, is ≅2^αk, with exponent α = 0.88(1). The probability distribution p*(x) of x = R(n) = S(n)/n^α, n ≫ 1, is well defined and strongly non‐Gaussian, with tails well described by the error function erfc. The probability distribution of x_m = R(n) − R(n − m) is given by p_m(x_m) = λ_m p*(x_m/λ_m), with λ_m → √2 for large m. © 1999 John Wiley & Sons, Inc.     

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.     

Solvability of nonlocal elliptic problems in weight spaces

In this paper we consider elliptic equations of order 2m in a bounded domainQ є R ⁿ with boundaryδQ and nonlocal conditions relating the traces of the solution and its derivatives on (n − 1)-dimensional smooth manifolds Γ _i (∪ _i =∂δQ) to their values on some compact setF ⊂Q, whereF ∩δQ ≠ Φ. The Fredholm solvability of these problems in the weight spacesV _{p, a} ^/l+2m (Q) is proved for arbitrary 1<p <∞. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 882–898, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00028.     

Cubature over the sphere in Sobolev spaces of arbitrary order

This paper studies numerical integration (or cubature) over the unit sphere for functions in arbitrary Sobolev spaces H^s(S²), s>1. We discuss sequences of cubature rules, where (i) the rule Q_m(n) uses m(n) points and is assumed to integrate exactly all (spherical) polynomials of degree ≤n and (ii) the sequence (Q_m(n)) satisfies a certain local regularity property. This local regularity property is automatically satisfied if each Q_m(n) has positive weights. It is shown that for functions in the unit ball of the Sobolev space H^s(S²), s>1, the worst-case cubature error has the order of convergence O(n^-s), a result previously known only for the particular case . The crucial step in the extension to general s>1 is a novel representation of , where P_ℓ is the Legendre polynomial of degree ℓ, in which the dominant term is a polynomial of degree n, which is therefore integrated exactly by the rule Q_m(n). The order of convergence O(n^-s) is optimal for sequences (Q_m(n)) of cubature rules with properties (i) and (ii) if Q_m(n) uses m(n)=O(n²) points.     

The generic division rings

LetA=k (X ₁, X₂..., X_m) be the division ring generated by genericn×n matrices over a fieldk; thenA is not a crossed product in the following cases: (i) there exists a primeq such thatq ³ℛn;(ii)[k:Q]=m, whereQ is the field of rationals, then if eitherq ³ℛn for someq for whichq-1ℛm, orq ²/nn for some other prime; (iii)k=Z _p ^r a finite field ofp ^r elements and eitherq ³ℛn for sameqℛp ^r-1 orq ²ℛn for some other primes. Other cases are also considered.     

Independent perfect domination sets in Cayley graphs

In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube Q_n has an independent perfect domination set if and only if Q_n is a regular covering of the complete graph K_n+1 if and only if n = 2^m ? 1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213–219, 2001     

A splitting theorem for the weighted measure

Let M be an n-dimensional complete noncompact Riemannian manifold, h be a smooth function on M and dμ = e ^h dV be the weighted measure. In this article, we prove that when the spectrum of the weighted Laplacian \triangle_m{\triangle_{\mu}} has a positive lower bound λ₁(M) > 0 and the m(m > n)-dimensional Bakry-émery curvature is bounded from below by -\fracm-1m-2l₁(M){-\frac{m-1}{m-2}\lambda_1(M)}, then M splits isometrically as R × N whenever it has two ends with infinite weighted volume, here N is an (n − 1)-dimensional compact manifold.     

Constant mean curvature hypersurfaces with two principal curvatures in a sphere

In this paper we consider a compact oriented hypersurface M ⁿ with constant mean curvature H and two distinct principal curvatures λ and μ with multiplicities (n − m) and m, respectively, immersed in the unit sphere S ⁿ⁺¹. Denote by f_ij{\phi_{ij}} the trace free part of the second fundamental form of M ⁿ , and Φ be the square of the length of f_ij{\phi_{ij}} . We obtain two integral formulas by using Φ and the polynomial P_H,m(x)=x²+ \fracn(n-2m)?{nm(n-m)}H x -n(1+H²){P_{H,m}(x)=x^{2}+ \frac{n(n-2m)}{\sqrt{nm(n-m)}}H x -n(1+H^{2})} . Assume that B _H,m is the square of the positive root of P _H,m (x) = 0. We show that if M ⁿ is a compact oriented hypersurface immersed in the sphere S ⁿ⁺¹ with constant mean curvatures H having two distinct principal curvatures λ and μ then either F = B_H,m{\Phi=B_{H,m}} or F = B_H,n-m{\Phi=B_{H,n-m}} . In particular, M ⁿ is the hypersurface S^n-m(r)×S^m(?{1-r²}){S^{n-m}(r)\times S^{m}(\sqrt{1-r^{2}})} .     

Laurent-Padé approximants to four kinds of Chebyshev polynomial expansions. Part II: Clenshaw-Lord type approximants

Laurent-Padé (Chebyshev) rational approximantsP _m (w, w ⁻¹)/Q _n (w, w ⁻¹) of Clenshaw-Lord type [2,1] are defined, such that the Laurent series ofP _m /Q _n matches that of a given functionf(w, w ⁻¹) up to terms of orderw ^±(m+n) , based only on knowledge of the Laurent series coefficients off up to terms inw ^±(m+n) . This contrasts with the Maehly-type approximants [4,5] defined and computed in part I of this paper [6], where the Laurent series ofP _m matches that ofQ _n f up to terms of orderw ^±(m+n ), but based on knowledge of the series coefficients off up to terms inw ^±(m+2n). The Clenshaw-Lord method is here extended to be applicable to Chebyshev polynomials of the 1st, 2nd, 3rd and 4th kinds and corresponding rational approximants and Laurent series, and efficient systems of linear equations for the determination of the Padé-Chebyshev coefficients are obtained in each case. Using the Laurent approach of Gragg and Johnson [4], approximations are obtainable for allm≥0,n≥0. Numerical results are obtained for all four kinds of Chebyshev polynomials and Padé-Chebyshev approximants. Remarkably similar results of formidable accuracy are obtained by both Maehly-type and Clenshaw-Lord type methods, thus validating the use of either.     

Multidimensional version of M. A. Krasnoseľskii’s generalized contraction principle

Let M be a complete K-metric space with n-dimensional metric ρ(x, y): M × M → R ⁿ , where K is the cone of nonnegative vectors in R ⁿ . A mapping F: M → M is called a Q-contraction if ρ (Fx,Fy) ⩽ Qρ (x,y), where Q: K → K is a semi-additive absolutely stable mapping. A Q-contraction always has a unique fixed point x* in M, and ρ(x*,a) ⩽ (I - Q)^-1 ρ(Fa, a) for every point a in M. The point x* can be obtained by the successive approximation method x _k = Fx _k-1, k = 1, 2,..., starting from an arbitrary point x ₀ in M, and the following error estimates hold: ρ (x*, x _k ) ⩽ Q ^k (I - Q)^-1ρ(x ₁, _x ⁰) ⩽ (I - Q)^-1 Q ^k ρ(x ₁, x ₀), k = 1, 2,.... Generally the mappings (I - Q)^-1 and Q ^k do not commute. For n = 1, the result is close to M. A. Krasnosel’skii’s generalized contraction principle.     

Optimal lower bounds for cubature error on the sphere

We show that the worst-case cubature error E(Q_m;H^s) of an m-point cubature rule Q_m for functions in the unit ball of the Sobolev space H^s=H^s(S²),s>1, has the lower bound , where the constant c_s is independent of Q_m and m. This lower bound result is optimal, since we have established in previous work that there exist sequences of cubature rules for which with a constant independent of n. The method of proof is constructive: given the cubature rule Q_m, we construct explicitly a ‘bad’ function f_mH^s, which is a function for which Q_mf_m=0 and . The construction uses results about packings of spherical caps on the sphere.     

On central division algebras

For any integern such that 8|n or for which there exists an odd primeq such thatq ²|n, there is a central division algebra of dimensionn ² over its center which is not a crossed product. The algebra constructed in this paper is the algebraQ(X ₁,…,X)_m, the algebra generated over the rationalQ bym(≧2) generic matrices. To the memory of A. A. Albert This paper was originally presented in November, 1971 for publication elsewhere in a volume in honor of Prof. A. A. Albert on the occasion of his 65th birthday. The volume was never published due to the death of Prof. Albert in June 1972.     

All-Pairs Small-Stretch Paths

Let G = (V, E) be a weighted undirected graph. A path between u, v  V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.It is easy to see that finding paths of stretch less than 2 between all pairs of vertices in an undirected graph with n vertices is at least as hard as the Boolean multiplication of two n × n matrices. We describe three algorithms for finding small-stretch paths between all pairs of vertices in a weighted graph with n vertices and m edges. The first algorithm, STRETCH₂, runs in Õ(n^3/2m^1/2) time and finds stretch 2 paths. The second algorithm, STRETCH_7/3, runs in Õ(n^7/3) time and finds stretch 7/3 paths. Finally, the third algorithm, STRETCH₃, runs in Õ(n²) and finds stretch 3 paths.Our algorithms are simpler, more efficient and more accurate than the previously best algorithms for finding small-stretch paths. Unlike all previous algorithms, our algorithms are not based on the construction of sparse spanners or sparse neighborhood covers.     

Thompson’s metric and global stability of difference equations

We apply the Thompson’s metric to study the global stability of the equilibium of the following difference equation

Laurent–Padé Approximants to Four Kinds of Chebyshev Polynomial Expansions. Part II: Clenshaw–Lord Type Approximants

Laurent–Padé (Chebyshev) rational approximants P _m (w,w ^–1)/Q _n (w,w ^–1) of Clenshaw–Lord type [2,1] are defined, such that the Laurent series of P _m /Q _n matches that of a given function f(w,w ^–1) up to terms of order w ^±(m+n), based only on knowledge of the Laurent series coefficients of f up to terms in w ^±(m+n). This contrasts with the Maehly-type approximants [4,5] defined and computed in part I of this paper [6], where the Laurent series of P _m matches that of Q _n f up to terms of order w ^±(m+n), but based on knowledge of the series coefficients of f up to terms in w ^±(m+2n). The Clenshaw–Lord method is here extended to be applicable to Chebyshev polynomials of the 1st, 2nd, 3rd and 4th kinds and corresponding rational approximants and Laurent series, and efficient systems of linear equations for the determination of the Padé–Chebyshev coefficients are obtained in each case. Using the Laurent approach of Gragg and Johnson [4], approximations are obtainable for all m0, n0. Numerical results are obtained for all four kinds of Chebyshev polynomials and Padé–Chebyshev approximants. Remarkably similar results of formidable accuracy are obtained by both Maehly-type and Clenshaw–Lord type methods, thus validating the use of either.     

The Evolution of Random Subgraphs of the Cube

be a random Qⁿ”-process, that is let Q₀ be the empty spanning subgraph of the cube Qⁿ and, for 1 ? t ? M = nN/2 = n2^n?1, let the graph Q_t be obtained from Q_t?1 by the random addition of an edge of Q_n not present in Q_t?1. When t is about N/2, a typical Q_t undergoes a certain “phase transition'': the component structure changes in a sudden and surprising way. Let t = (1 + ?) N/2 where ? is independent of n. Then all the components of a typical Q_t have o(N) vertices if ? < 0, while if ? > 0 then, as proved by Ajtai, Komlós, and Szemerédi, a typical Q_t has a “giant” component with at least α(?)N vertices, where α(?) > 0. In this note we give essentially best possible results concerning the emergence of this giant component close to the time of phase transition. Our results imply that if η > 0 is fixed and t ? (1 ? n^?η) N/2, then all components of a typical Q_t have at most n^β(η) vertices, where β(η) > 0. More importantly, if 60(log n)³/n ? ? = ?n = o(1), then the largest component of a typical Q_t has about 2?N vertices, while the second largest component has order O(n?^?2). Loosely put, the evolution of a typical Qⁿ process is such that shortly after time N/2 the appearance of each new edge results in the giant component acquiring 4 new vertices.     

On Hahn polynomial expansion of a continuous function of bounded variation

We consider the well-known method of least squares (cf., e.g., [1, p. 217]) on an equidistant grid with N + 1 nodes on the interval [−1, 1]. We investigate the following problem: For which ratio N/n, do we have pointwise convergence of the least square operator LS^N_n : C[−1,[1][→[P_n? To solve this problem we investigate the relation between the Jacobi polynomials P^α,β_k (cf., e.g., [2, p. 216]) and the Hahn polynomials Q_k (·; α, β, N) (cf., e.g., [2, p. 204]). In particular, we present the following result: Let f ∈ {g ∈ C¹[−1, 1] : g′∈ BV [−1, 1]} and let (N_n)_n be a sequence of natural numbers with n⁴/N_n → 0. Then the least square method LS^N_n [f] converges for each x ∈ [−1, 1]. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On reducibility of n-ary quasigroups

An n-ary operation Q:Σⁿ→Σ is called an n-ary quasigroup of order |Σ| if in the relation x₀=Q(x₁,…,x_n) knowledge of any n elements of x₀,…,x_n uniquely specifies the remaining one. Q is permutably reducible if Q(x₁,…,x_n)=P(R(x_σ(1),…,x_σ(k)),x_σ(k+1),…,x_σ(n)) where P and R are (n-k+1)-ary and k-ary quasigroups, σ is a permutation, and 1<k<n. An m-ary quasigroup S is called a retract of Q if it can be obtained from Q or one of its inverses by fixing n-m>0 arguments. We prove that if the maximum arity of a permutably irreducible retract of an n-ary quasigroup Q belongs to {3,…,n-3}, then Q is permutably reducible.     

Mixing properties of Markov operators and ergodic transformations,and ergodicity of cartesian products

LetT be a Markov operator onL ₁(X, Σ,m) withT*=P. We connect properties ofP with properties of all productsP ×Q, forQ in a certain class: (a) (Weak mixing theorem)P is ergodic and has no unimodular eigenvalues ≠ 1 ⇔ for everyQ ergodic with finite invariant measureP ×Q is ergodic ⇔ for everyu ∈L ₁ with∝ udm=0 and everyf ∈L _∞ we haveN ⁻¹Σ _n ^≠1/N |<u, P ⁿf>|→0. (b) For everyu ∈L ₁ with∝ udm=0 we have ‖T ⁿu‖₁ → 0 ⇔ for every ergodicQ, P ×Q is ergodic. (c)P has a finite invariant measure equivalent tom ⇔ for every conservativeQ, P ×Q is conservative. The recent notion of mild mixing is also treated. Dedicated to the memory of Shlomo Horowitz An erratum to this article is available at .