Krein's strings,the symmetric moment problem,and extending a real positive definite function

The symmetric moment problem is to find a possibly unique, positive symmetric measure that will produce a given sequence of moments {M_n}. Let us assume that the (Hankel) condition for existence of a solution is satisfied, and let σ_n be the unique measure, supported on n points, whose first 2n moments agree with M₀,…,M_2n−1. It is known that σ_2n ⇒ σ₀ (weak convergence) and σ_2n+1 ⇒ σ_∞, where σ₀ and σ_∞ are solutions to the full moment problem. Moreover, σ₀ = σ_∞ if and only if the problem has a unique solution. In this paper we present an analogue of this theorem for Krein's problem of extending to ℝ a real, even positive definite function originally defined on [−T,T] where T < ∞. Our proof relies on the machinery of Krein's strings. As we show, these strings help explain the connection between the moment and the extension problems. © 1999 John Wiley & Sons, Inc.     

Codes associated with special linear groups and power moments of multi-dimensional Kloosterman sums

In this paper, we construct the binary linear codes C(SL(n, q)) associated with finite special linear groups SL(n, q), with both n,q powers of two. Then, via the Pless power moment identity and utilizing our previous result on the explicit expression of the Gauss sum for SL(n, q), we obtain a recursive formula for the power moments of multi- dimensional Kloosterman sums in terms of the frequencies of weights in C(SL(n, q)). In particular, when n = 2, this gives a recursive formula for the power moments of Kloosterman sums. We illustrate our results with some examples.     

Complementary Regions of Knot and Link Diagrams

An increasing sequence of integers is said to be universal for knots and links if every knot and link has a reduced projection on the sphere such that the number of edges of each complementary face of the projection comes from the given sequence. In this paper, it is proved that the following infinite sequences are each universal for knots and links: (3, 5, 7, . . .), (2, n, n + 1, n + 2, . . .) for each n ≥ 3, (3, n, n + 1, n + 2, . . .) for each n ≥ 4. Moreover, the finite sequences (2, 4, 5) and (3, 4, n) for each n ≥ 5 are universal for all knots and links. It is also shown that every knot has a projection with exactly two odd-sided faces, which can be taken to be triangles, and every link of n components has a projection with at most n odd-sided faces if n is even and n + 1 odd-sided faces if n is odd.     

Greedily Finding a Dense Subgraph

Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)² − O(n ^− 1/3) ≤ R ≤ (1/2 + n/2k)² + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k²) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming.     

Describing the symmetry of one-dimensional figures by power sums of point coordinates

The article examines the problem of describing the symmetry of a one-dimensional figure by power sums of the coordinates of its points. In case ofn points of unit mass, the figure symmetry requires [(n+1)/2] values of odd power sums; in case of massive points,n values are required in general. A one-to-one correspondence is established between the coordinates ofn points of the figure and the values of power sums to order (2n−1) inclusive. Translated from Prikladnaya Matematika i Informatika, No. 2, pp. 106–115, 1999.     

On the existence and nonexistence of global solutions for the porous medium equation with strongly nonlinear sources in a cone

In this paper, we study the initial-boundary value problem of the porous medium equation u _t  = Δu ^m  + V(x)u ^p in a cone D = (0, ∞) × Ω, where V(x) ~ (1 + |x|) ^σ . Let ω ₁ denote the smallest Dirichlet eigenvalue for the Laplace–Beltrami operator on Ω and let l denote the positive root of l ² + (n − 2)l = ω ₁. We prove that if m ≤ p ≤ m + (2 + σ)/(n + l), then the problem has no global nonnegative solutions for any nonnegative u ₀ unless u ₀ = 0; if p > m + (2 + σ)/n, then the problem has global solutions for some u ₀ ≥ 0.     

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n^{2 + max(α, β)}) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(n^max(α, β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a “Monge property” and that the SMAWK algorithm on monotone matrices can therefore be applied.     

Asymptotic properties of the algebraic moment range process

Let M _n denote the n-th moment space of the set of all probability measures on the interval [0, 1], P _n the uniform distribution on the set M _n and r _{n + 1} the maximal range of the (n + 1)-th moments corresponding to a random moment point C _n with distribution P _n on M _n . We study several asymptotic properties of the stochastic process (r _⌊nt⌋+1) _t∈[0,T] if n → ∞. In particular weak convergence to a Gaussian process and a large deviation principle are established.      

An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover

The constraint bipartite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k₁, k₂, is there a vertex cover taking at most k₁ vertices from one and at most k₂ vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999^{k₁ + k₂} + (k₁ + k₂)n) time. Our algorithm is efficient and practical for small values of k₁ and k₂, as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed; nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths (and hence the depth of the search tree as a whole) by a sort of bonus points.     

Prime and composite integers close to powers of a number

We prove that, for any real numbers ξ ≠ 0 and ν, the sequence of integer parts [ξ2 ⁿ  + ν], n = 0, 1, 2, . . . , contains infinitely many composite numbers. Moreover, if the number ξ is irrational, then the above sequence contains infinitely many elements divisible by 2 or 3. The same holds for the sequence [ξ( − 2) ⁿ  + ν _n ], n = 0, 1, 2, . . . , where ν ₀, ν ₁, ν ₂, . . . all lie in a half open real interval of length 1/3. For this, we show that if a sequence of integers x ₁, x ₂, x ₃, . . . satisfies the recurrence relation x _n+d  = cx _n  + F(x _n+1, . . . , x _n+d-1) for each n  ≥  1, where c ≠ 0 is an integer, F(z₁,...,z_d-1) ? \mathbb Z[z₁,...,z_d-1],{F(z_1,\dots,z_{d-1}) \in \mathbb {Z}[z_1,\dots,z_{d-1}],} and lim _{n→ ∞}|x _n | = ∞, then the number |x _n | is composite for infinitely many positive integers n. The proofs involve techniques from number theory, linear algebra, combinatorics on words and some kind of symbolic computation modulo 3.     

Supercritical biharmonic equations with power-type nonlinearity

We study two different versions of a supercritical biharmonic equation with a power-type nonlinearity. First, we focus on the equation Δ² u = |u| ^p-1 u over the whole space , where n > 4 and p > (n + 4)/(n − 4). Assuming that p < p _c, where p _c is a further critical exponent, we show that all regular radial solutions oscillate around an explicit singular radial solution. As it was already known, on the other hand, no such oscillations occur in the remaining case p ≥ p _c. We also study the Dirichlet problem for the equation Δ² u = λ (1 + u) ^p over the unit ball in , where λ > 0 is an eigenvalue parameter, while n > 4 and p > (n + 4)/(n − 4) as before. When it comes to the extremal solution associated to this eigenvalue problem, we show that it is regular as long as p < p _c. Finally, we show that a singular solution exists for some appropriate λ > 0.      

Analysis of Carry Propagation in Addition: An Elementary Approach

Our goal in this paper is to analyze carry propagation in addition using only elementary methods (that is, those not involving residues, contour integration, or methods of complex analysis). Our results concern the length of the longest carry chain when two independent uniformly distributed n-bit numbers are added. First, we show using just first- and second-moment arguments that the expected length C_n of the longest carry chain satisfies C_n = log₂n + O(1). Second, we use a sieve (inclusion–exclusion) argument to give an exact formula for C_n. Third, we give an elementary derivation of an asymptotic formula due to Knuth, C_n = log₂n + Φ(log₂ n) + O((logn)⁴/n), where Φ(ν) is a bounded periodic function of ν, with period 1, for which we give both a simple integral expression and a Fourier series. Fourth, we give an analogous asymptotic formula for the variance V_n of the length of the longest carry chain: V_n = Ψ(log₂ n) + O((logn)⁵/n), where Ψ(ν) is another bounded periodic function of ν, with period 1. Our approach can be adapted to addition with the “end-around” carry that occurs in the sign-magnitude and 1s-complement representations. Finally, our approach can be adapted to give elementary derivations of some asymptotic formulas arising in connection with radix-exchange sorting and collision-resolution algorithms, which have previously been derived using contour integration and residues.     

Local Solutions of Semilinear Wave Equations in Hs+1

The Cauchy problem for the wave equation with power type non-linearity ±∣u∣u and data in H^s+1(ℝⁿ)×H^s(ℝⁿ) is considered, where 0<s<(n/2)−1 and n≥3. Under the growth restriction σ_*⩽4/(n−2−2s) in many cases the existence of a local solution with u(t)∈H^s+1(ℝⁿ) is shown which is unique in a closely related class.     

<Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>-harmonic forms and stable hypersurfaces in space forms

We prove that a complete noncompact orientable stable minimal hypersurface in \mathbbSⁿ⁺¹{\mathbb{S}^{n+1}} (n ≤ 4) admits no nontrivial L ²-harmonic forms. We also obtain that a complete noncompact strongly stable hypersurface with constant mean curvature in \mathbbRⁿ⁺¹{\mathbb{R}^{n+1}} or \mathbbSⁿ⁺¹{\mathbb{S}^{n+1}} (n ≤ 4) admits no nontrivial L ²-harmonic forms. These results are generalized versions of Tanno’s result on stable minimal hypersurfaces in \mathbbRⁿ⁺¹{\mathbb{R}^{n+1}}.     

New Expressions for Repeated Upper Tail Integrals of the Normal Distribution

Expressions are given for repeated upper tail integrals of the univariate normal density (and so also for the general Hermite function) for both positive and negative arguments. The expressions involve moments of the form E(x + i N) ⁿ and E1 / (x ² + N ²) ⁿ , where N is a unit normal random variable. Laplace transforms are provided for the Hermite functions and the moments. The practical use of these expressions is illustrated.     

On the Paper "Asymptotics for the Moments of Singular Distributions"

In their 1993 paper, W. Goh and J. Wimp derive interesting asymptotics for the moments c_n(α) ≡ c_n = ∫¹₀tⁿdα(t), N = 0, 1, 2, ..., of some singular distributions α (with support [0, 1]), which contain oscillatory terms. They suspect, that this is a general feature of singular distributions and that this behavior provides a striking contrast with what happens for absolutely continuous distributions. In the present note, however, we give an example of an absolutely continuous measure with asymptotics of moments containing oscillatory terms, and an example of a singular measure having very regular asymptotic behavior of its moments. Finally, we give a short proof of the fact that the drop-off rate of the moments is exactly the local measure dimension about 1 (if it exists).     

Packing congruent hyperspheres into a hypersphere

The paper considers a problem of packing the maximal number of congruent nD hyperspheres of given radius into a larger nD hypersphere of given radius where n = 2, 3, . . . , 24. Solving the problem is reduced to solving a sequence of packing subproblems provided that radii of hyperspheres are variable. Mathematical models of the subproblems are constructed. Characteristics of the mathematical models are investigated. On the ground of the characteristics we offer a solution approach. For n ≤ 3 starting points are generated either in accordance with the lattice packing of circles and spheres or in a random way. For n > 3 starting points are generated in a random way. A procedure of perturbation of lattice packings is applied to improve convergence. We use the Zoutendijk feasible direction method to search for local maxima of the subproblems. To compute an approximation to a global maximum of the problem we realize a non-exhaustive search of local maxima. Our results are compared with the benchmark results for n = 2. A number of numerical results for 2 ≤ n ≤ 24 are given.     

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)