Computing a pyramid partition generating function with dimer shuffling

We verify a recent conjecture of Kenyon/Szendr?i by computing the generating function for pyramid partitions. Pyramid partitions are closely related to Aztec Diamonds; their generating function turns out to be the partition function for the Donaldson-Thomas theory of a non-commutative resolution of the conifold singularity {x₁x₂−x₃x₄=0}⊂C⁴. The proof does not require algebraic geometry; it uses a modified version of the domino shuffling algorithm of Elkies, Kuperberg, Larsen and Propp [Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp, Alternating sign matrices and domino tilings. II, J. Algebraic Combin. 1 (3) (1992) 219-234].     

Arithmetical properties of a sequence arising from an arctangent sum

The sequence {xn} defined by xn=(n+xn−1)/(1−nxn−1), with x₁=1, appeared in the context of some arctangent sums. We establish the fact that xn≠0 for n?4 and conjecture that xn is not an integer for n?5. This conjecture is given a combinatorial interpretation in terms of Stirling numbers via the elementary symmetric functions. The problem features linkage with a well-known conjecture on the existence of infinitely many primes of the form n²+1, as well as our conjecture that (1+¹²)(1+²²)?(1+n²) is not a square for n>3. We present an algorithm that verifies the latter for n?¹⁰³²⁰⁰.     

Entire functions that share a small function with their derivatives

Let f be an entire function of finite order and a an entire function of order less than f's. If f−a and f^′−a have the same zeros with the same multiplicities, then f^′−a≡c(f−a) for some non-zero constant c.     

Multiple positive solutions to a singular boundary value problem for a superlinear Emden-Fowler equation

A multiplicity result for the singular ordinary differential equation y^″+λx⁻²yσ=0, posed in the interval (0,1), with the boundary conditions y(0)=0 and y(1)=γ, where σ>1, λ>0 and γ?0 are real parameters, is presented. Using a logarithmic transformation and an integral equation method, we show that there exists Σ^?∈(0,σ/2] such that a solution to the above problem is possible if and only if λγσ−1?Σ^?. For 0<λγσ−1<Σ^?, there are multiple positive solutions, while if γ=(λ⁻¹Σ^?)^1/(σ−1) the problem has a unique positive solution which is monotonic increasing. The asymptotic behavior of y(x) as x→⁰⁺ is also given, which allows us to establish the absence of positive solution to the singular Dirichlet elliptic problem −Δu=d⁻²(x)uσ in Ω, where Ω⊂RN, N?2, is a smooth bounded domain and d(x)=dist(x,∂Ω).     

Exact multiplicity results for a class of two-point boundary value problems

This paper is concerned with the exact number of positive solutions for boundary value problems ^′(|y^′|^p−2y^′)+λf(y)=0 and y(−1)=y(1)=0, where p>1 and λ>0 is a positive parameter. We consider the case in which the nonlinearity f is positive on (0,∞) and (p−1)f(u)−uf^′(u) changes sign from negative to positive.     

Adaptive Itô-Taylor algorithm can optimally approximate the Itô integrals of singular functions

We deal with numerical approximation of stochastic Itô integrals of singular functions. We first consider the regular case of integrands belonging to the Hölder class with parameters r and ?. We show that in this case the classical Itô-Taylor algorithm has the optimal error Θ(n^−(r+?)). In the singular case, we consider a class of piecewise regular functions that have continuous derivatives, except for a finite number of unknown singular points. We show that any nonadaptive algorithm cannot efficiently handle such a problem, even in the case of a single singularity. The error of such algorithm is no less than n^{−min{1/2,r+?}}. Therefore, we must turn to adaptive algorithms. We construct the adaptive Itô-Taylor algorithm that, in the case of at most one singularity, has the optimal error O(n^−(r+?)). The best speed of convergence, known for regular functions, is thus preserved. For multiple singularities, we show that any adaptive algorithm has the error Ω(n^{−min{1/2,r+?}}), and this bound is sharp.     

Orbits in max-min algebra

Properties of orbits in max-min algebra are described, mainly the properties of periodic orbits. An O(n³) algorithm computing the period of a periodic orbit is presented. As a consequence, an O(n³ log n) algorithm computing the period of arbitrary orbit is obtained, as the pre-periodic part of the orbit has length at most (n − 1)² + 1.     

Traversing Layered Graphs Using the Work Function Algorithm

The work function algorithm (WFA) is an on-line algorithm that has been studied mostly in connection with thek-server problem, but can actually be used on a wide variety of on-line problems. Despite being a simple algorithm, WFA has proven to be difficult to analyze, and until recently few interesting results were known. We analyze the performance of the generalized work function algorithm, denoted α-WFA, for on-line traversal of layered graphs. We show that for layered graphs of widthkand any α>1, α-WFA achieves competitive ratio (α+1)(2α/(α−1))^k−1−α. This gives anO(k2^k)-competitive ratio for appropriate choice of α, improving the previous upper bound ofO(k³2^k).     

Exact number of positive solutions for a class of semipositone problems

This paper is concerned with the boundary value problems y″+λ(y^p−y^q)=0 and y(−1)=y(1)=0, where p>q>−1 and λ>0 is a positive parameter. We discuss the existence of positive solutions and give a complete study.     

On an Riesz basis of generalized eigenvectors of the nonselfadjoint problem deduced from a perturbation method for sound radiation by a vibrating plate in a light fluid

In this paper we prove that the system of generalized eigenvectors of the operator (I+εK)⁻¹d⁴/dx⁴ forms a Riesz basis of L²(]−L,L[) where K is the integral operator with kernel the Hankel function of the first kind and order 0. This operator was introduced in J. Sound Vibration 177 (1994) 259-275. We give positive answers to the hypotheses posed in that article.     

Improved book-embeddings of incomplete hypercubes

In this paper, we show that any incomplete hypercube with, at most, 2ⁿ+2ⁿ⁻¹+2ⁿ⁻² vertices can be embedded in n−1 pages for all n≥4. For the case n≥4, this result improves Fang and Lai’s result that any incomplete hypercube with, at most, 2ⁿ+2ⁿ⁻¹ vertices can be embedded in n−1 pages for all n≥2.Besides this, we show that the result can be further improved when n is large — e.g., any incomplete hypercube with at most 2ⁿ+2ⁿ⁻¹+2ⁿ⁻²+2ⁿ⁻⁷ (respectively, 2ⁿ+2ⁿ⁻¹+2ⁿ⁻²+2ⁿ⁻⁷+2ⁿ⁻²³⁰) vertices can be embedded in n−1 pages for all n≥9 (respectively, n≥232).     

Concentration on minimal submanifolds for a singularly perturbed Neumann problem

We consider the equation −ε²Δu+u=up in Ω⊆RN, where Ω is open, smooth and bounded, and we prove concentration of solutions along k-dimensional minimal submanifolds of ∂Ω, for N?3 and for k∈{1,…,N−2}. We impose Neumann boundary conditions, assuming 1<p<(N−k+2)/(N−k−2) and ε→⁰⁺. This result settles in full generality a phenomenon previously considered only in the particular case N=3 and k=1.     

Self-similar singular solutions of a p-Laplacian evolution equation with absorption

We consider, for p∈(1,2) and q>1, self-similar singular solutions of the equation v_t=div(|∇v|^p−2∇v)−v^q in Rn×(0,∞); here by self-similar we mean that v takes the form v(x,t)=t^−αw(|x|t^−αβ) for α=1/(q−1) and β=(q+1−p)/p, whereas singular means that v is non-negative, non-trivial, and for all x≠0. That is, we consider the ODE problem

(0.1)     

Multiple solutions for a Hénon-like equation on the annulus

For the equation −Δu=||xα|−2|up−1, 1<|x|<3, we prove the existence of two solutions for α large, and of two additional solutions when p is close to the critical Sobolev exponent ^2∗=2N/(N−2). A symmetry-breaking phenomenon appears, showing that the least-energy solutions cannot be radial functions.     

The Riemann-Hilbert approach to strong asymptotics for orthogonal polynomials on [−1,1]

We consider polynomials that are orthogonal on [−1,1] with respect to a modified Jacobi weight (1−x)^α(1+x)^βh(x), with α,β>−1 and h real analytic and strictly positive on [−1,1]. We obtain full asymptotic expansions for the monic and orthonormal polynomials outside the interval [−1,1], for the recurrence coefficients and for the leading coefficients of the orthonormal polynomials. We also deduce asymptotic behavior for the Hankel determinants and for the monic orthogonal polynomials on the interval [−1,1]. For the asymptotic analysis we use the steepest descent technique for Riemann-Hilbert problems developed by Deift and Zhou, and applied to orthogonal polynomials on the real line by Deift, Kriecherbauer, McLaughlin, Venakides, and Zhou. In the steepest descent method we will use the Szeg? function associated with the weight and for the local analysis around the endpoints ±1 we use Bessel functions of appropriate order, whereas Deift et al. use Airy functions.     

Trotter-Kato product formula and fractional powers of self-adjoint generators

Let A and B be non-negative self-adjoint operators in a Hilbert space such that their densely defined form sum obeys dom(H^α)⊆dom(A^α)∩dom(B^α) for some α∈(1/2,1). It is proved that if, in addition, A and B satisfy dom(A^1/2)⊆dom(B^1/2), then the symmetric and non-symmetric Trotter-Kato product formula converges in the operator norm:

||(e−tB/2ne−tA/ne−tB/2n)n−e−tH||=O(n−(2α−1))||(e−tA/ne−tB/n)n−e−tH||=O(n−(2α−1))     

The minimum spanning strong subdigraph problem is fixed parameter tractable

A digraph D is strong if it contains a directed path from x to y for every choice of vertices x,y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k≤n−2 so that D contains a spanning strong subdigraph with at most 2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)n^c) algorithm for deciding whether a given strong digraph D on n vertices contains a spanning strong subdigraph with at most 2n−2−k arcs.We furthermore prove that if k≥1 and D has no cut vertex then it has a kernel of order at most (2k−1)². We finally discuss related problems and conjectures.     

One-point pseudospectral collocation for the one-dimensional Bratu equation

The one-dimensional planar Bratu problem is u_xx + λ exp(u) = 0 subject to u(±1) = 0. Because there is an analytical solution, this problem has been widely used to test numerical and perturbative schemes. We show that over the entire lower branch, and most of the upper branch, the solution is well approximated by a parabola, u(x) ≈ u₀ (1 − x²) where u₀ is determined by collocation at a single point x = ξ. The collocation equation can be solved explicitly in terms of the Lambert W-function as u(0) ≈ −W(−λ(1 − ξ²)/2)/(1 − ξ²) where both real-valued branches of the W-function yield good approximations to the two branches of the Bratu function. We carefully analyze the consequences of the choice of ξ. We also analyze the rate of convergence of a series of even Chebyshev polynomials which extends the one-point approximation to arbitrary accuracy. The Bratu function is so smooth that it is actually poor for comparing methods because even a bad, inefficient algorithm is successful. It is, however, a solution so smooth that a numerical scheme (the collocation or pseudospectral method) yields an explicit, analytical approximation. We also fill some gaps in theory of the Bratu equation. We prove that the general solution can be written in terms of a single, parameter-free β(x) without knowledge of the explicit solution. The analytical solution can only be evaluated by solving a transcendental eigenrelation whose solution is not known explicitly. We give three overlapping perturbative approximations to the eigenrelation, allowing the analytical solution to be easily evaluated throughout the entire parameter space.     

Zeros of a random algebraic polynomial with coefficient means in geometric progression

This paper provides the mathematical expectation for the number of real zeros of an algebraic polynomial with non-identical random coefficients. We assume that the coefficients {a_j}ⁿ⁻¹_j=0 of the polynomial T(x)=a₀+a₁x+a₂x²+?+a_n−1xⁿ⁻¹ are normally distributed, with mean E(a_j)=μ^j+1, where μ≠0, and constant non-zero variance. It is shown that the behaviour of the random polynomial is independent of the variance on the interval (−1,1); it differs, however, for the cases of |μ|<1 and |μ|>1. On the intervals (−∞,−1) and (1,∞) we find the expected number of real zeros is governed by an interesting relationship between the means of the coefficients and their common variance. Our result is consistent with those of previous works for identically distributed coefficients, in that the expected number of real zeros for μ≠0 is half of that for μ=0.     

Un lemme de prolongement holomorphe et ses applications

We prove that an holomorphic function defined in the neighborhood of an algebraic knot f⁻¹(0)∩S(0,ε) in dimension ?3, can be extended along the hypersurface f⁻¹(0)∩B(0,ε). As an application we give a new proof of the Malgrange's singular Frobenius theorem.