On arithmetic and asymptotic properties of up-down numbers

Let σ=(σ₁,…,σ_N), where σ_i=±1, and let C(σ) denote the number of permutations π of 1,2,…,N+1, whose up-down signature sign(π(i+1)-π(i))=σ_i, for i=1,…,N. We prove that the set of all up-down numbers C(σ) can be expressed by a single universal polynomial Φ, whose coefficients are products of numbers from the Taylor series of the hyperbolic tangent function. We prove that Φ is a modified exponential, and deduce some remarkable congruence properties for the set of all numbers C(σ), for fixed N. We prove a concise upper bound for C(σ), which describes the asymptotic behaviour of the up-down function C(σ) in the limit C(σ)?(N+1)!.     

Multiple positive solutions of nonhomogeneous elliptic systems with strongly indefinite structure and critical Sobolev exponents

In this paper, we study the existence of multiple positive solutions to some Hamiltonian elliptic systems −Δv=λu+u^p+εf(x), −Δu=μv+v^q+δg(x) in Ω;u,v>0 in Ω; u=v=0 on ∂Ω, where Ω is a bounded domain in R^N (N?3); 0?f, g∈L∞(Ω); 1/(p+1)+1/(q+1)=(N−2)/N, p,q>1; λ,μ>0. Using sub- and supersolution method and based on an adaptation of the dual variational approach, we prove the existence of at least two nontrivial positive solutions for all λ,μ∈(0,λ₁) and ε,δ∈(0,δ₀), where λ₁ is the first eigenvalue of the Laplace operator −Δ with zero Dirichlet boundary conditions and δ₀ is a positive number.     

Asymptotic behaviors of the solution to an initial-boundary value problem for scalar viscous conservation laws

This paper is concerned with the asymptotic behaviors of the solutions to the initial-boundary value problem for scalar viscous conservations laws u_t + f(u)_x = u_xx on [0, 1], with the boundary condition u(0, t) = u₋(t) → u₋, u(1, t) = u₊(t) → u₊, as t → +∞ and the initial data u(x,0) = u₀(x) satisfying u₀(0) = u₋(0), u₀(1) = u₊(1), where u± are given constants, u₋ ≠ u₊ and f is a given function satisfying f″(u) > 0 for u under consideration. By means of an elementary energy estimates method, both the global existence and the asymptotic behavior are obtained. When u₋ 〈 u₊, which corresponds to rarefaction waves in inviscid conservation laws, no smallness conditions are needed. While for u₋ > u₊, which corresponds to shock waves in inviscid conservation laws, it is established for weak shock waves, that is, |u₋−u₊| is small. Moreover, when u_±(t) ≡ u_±, t ≥ 0, exponential decay rates are both obtained.     

AnL 1 counting problem in ergodic theory

We give a negative solution to the following counting problem for measure preserving transformations. Forf∈L ₊ ¹ (μ), is it true that sup _n (N _n (f)(x)/n) <∞, μ a.e., where N _n (f)(x)=≠{k:f(T ^k x)/k >1/ n}? One of the consequences is the nonvalidity of J. Bourgain’s Return Time Theorem for pairs of (L ¹ ,L ¹ ) functions.     

Revisiting queueing output processes: a point process viewpoint

After some historical notes concerning queueing output processes N _dep??, the paper discusses methods for establishing asymptotic linear relations for var??N _dep??(0,t], whether in the crude form B ₁ t or the more detailed form B ₁ t+B ₀+o(1) for t→∞. The crude form holds whenever the process N _adm of customers admitted to service has a linear asymptote, and then (var??N _dep??(0,t])/t and (var??N _adm(0,t])/t share a common limit (that may be infinite) in stationary G/G/k/K systems. A standard integral formula for the variance of a stationary orderly point process shows that, if N _dep?? is a renewal process whose generic lifetime X has finite second moment, then B ₁=(var??X)/([E(X)]²), and the more detailed linear asymptote holds when E(X ³) is finite. Geometric ergodicity of the queue size process Q(?) in stationary M/M/k/K systems establishes that the more detailed linear asymptote is true for them. It is conjectured that var??N(0,t]～B ₁ t for any stationary point process N possessing an embedded regenerative structure.     

Existence and uniqueness of positive solution for nonhomogeneous sublinear elliptic equations

In this paper, we study the existence and the uniqueness of positive solution for the sublinear elliptic equation, −Δu+u=p|u|sgn(u)+f in RN, N?3, 0<p<1, f∈L²(RN), f>0 a.e. in RN. We show by applying a minimizing method on the Nehari manifold that this problem has a unique positive solution in H¹(RN)∩Lp+1(RN). We study its continuity in the perturbation parameter f at 0.     

On the security analysis of an image scrambling encryption of pixel bit and its improved scheme based on self-correlation encryption

An image scrambling encryption scheme for pixel bits was presented by Ye [Ye GD. Image scrambling encryption algorithm of pixel bit based on chaos map. Pattern Recognit Lett 2010;31:347-54], which can be seen as one kind of typical binary image scrambling encryption considering from the bit-plain of size M × (8N). However, recently, some defects existing in the original image encryption scheme, i.e., Ye’s scheme, have been observed by Li and Lo [Li CQ, Lo KT. Optimal quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks. Signal Process 2011;91:949-54]. In the attack proposed by Li and Lo at least 3 + ⌈log₂(MN)⌉ plain images of size M × N are used to reveal the permutation matrix W = [w(i, k)] (i ∈ {1, 2, … , M}; k ∈ {1, 2, … , 8N}) which can be applied to recover the exact plain image. In the current paper, at first, one type of special plain image/cipher image is used to analyze the security weakness of the original image scrambling scheme under study. The final encryption vectors TM and TN or the decryption vectors TM′ and TN′ are revealed completely according to our attack. To demonstrate the performance of our attack, a quantified comparison is drawn between our attack and the attack proposed by Li and Lo. Compared with Li and Lo’s attack, our attack is more efficient in the general conditions. In particular, when the sizes of images satisfy the condition M = N or M ? 8N, the number of the used plain images/cipher images is at most 9, which is sharply less than 3 + ⌈log₂(MN)⌉ when M and N are of large size. To overcome the weaknesses of the original scheme, in this paper, an improved image scrambling encryption scheme is proposed. In the improved scheme, the idea of the “self-correlation” method is used to resist the chosen-plaintext attack/known-plaintext attack. The corresponding simulations and analyses illustrate that the improved encryption method has good cryptographic properties, and can overcome the weakness of the original image encryption scheme. Finally, farther improvement is briefly presented for the future work.     

On the enumeration of chains in regular chain-groups

Let N be a regular chain-group on E (see W. T. Tutte, Canad. J. Math.8 (1956), 13–28); for instance, N may be the group of integer flows or tensions of a directed graph with edge-set E). It is known that the number of proper Z_λ-chains of N (λ ∈ Z, λ ≥ 2) is given by a polynomial in λ, P(N, λ) (when N is the chain-group of integer tensions of the connected graph G, λP(N, λ) is the usual chromatic polynomial of G). We prove the formula: P(N, λ) = Σ_{[E′]∈O(N)⁺/～}Q(R_[E′](N), λ), where O(N)⁺ is the set of orientations of N with a proper positive chain, ～ is a simple equivalence relation on O(N)⁺ (sequence of reversals of positive primitive chains), and Q(R_[E′](N), λ) is the number of chains with values in [1, λ ? 1] in any reorientation of N associated to an element of [E′]. Moreover, each term Q(R_[E′](N), λ) is a polynomial in λ. As applications we obtain: P(N, 0) = (?1)^r(N)∥O(N)⁺/～∥; P(N, ?1) = (?1)^r(N)∥O(N)⁺∥ (a result first proved by Brylawski and Lucas); P(N, λ + 1) ≥ P(N, λ) for λ ≥ 2, λ ∈ Z. Our result can also be considered as a refinement of the following known fact: A regular chain-group N has a proper Z_λ-chain iff it has a proper chain in [?λ + 1, λ ? 1].     

A Liouville type theorem for polyharmonic elliptic systems

In this paper, we consider the polyharmonic system m(−Δ)U=Vq,m(−Δ)V=Up in RN, for m>1, N>2m, with p?1, q?1, but not both equal to 1, where m(−Δ) is the polyharmonic operator. Set α=2m(q+1)/(pq−1), β=2m(p+1)/(pq−1), for α,β∈[(N−2)/2,N−2m), we prove the nonexistence of positive solutions.     

On the Morse critical groups for indefinite sublinear elliptic problems

We consider the Dirichlet problem for the equation −Δu=αu+m(x)u|u|^q−2+g(x,u), where q∈(1,2) and m changes sign. We prove that the Morse critical groups at zero of the energy functional of the problem are trivial. As a consequence, existence and bifurcation of nontrivial solutions of the problem are established.     

A locally optimal fast obstacle-avoiding path-planning algorithm

Two algorithms to compute the shortest collision-free paths in the Euclidean plane are presented. The ƒ obstacles assumed to be described by disjoint convex polygons having N vertices in total. After preprocessing time O(N+flogN), a suboptimal shortest path between two arbitrary query points can be found in O(f+NlogN) time using Dijkstra's algorithm and in Θ(N) time using the A¹ algorithm. The space complexity is O(N+f).     

A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function

Consider the resource allocation problem:minimize ∑ⁿ_i=1 f_i(x_i) subject to ∑ⁿ_i=1 x_i = N and x_i's being nonnegative integers, where each f_i is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n²(log N)²] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.     

Monodromy groups of Hurwitz-type problems

We solve the Hurwitz monodromy problem for degree 4 covers. That is, the Hurwitz space H4,g of all simply branched covers of P¹ of degree 4 and genus g is an unramified cover of the space P2g+6 of (2g+6)-tuples of distinct points in P¹. We determine the monodromy of π₁(P2g+6) on the points of the fiber. This turns out to be the same problem as the action of π₁(P2g+6) on a certain local system of Z/2-vector spaces. We generalize our result by treating the analogous local system with Z/N coefficients, 3?N, in place of Z/2. This in turn allows us to answer a question of Ellenberg concerning families of Galois covers of P¹ with deck group ²(Z/N):S₃.     

Efficient Ritz-Galerkin Discretization of PDEs with Variable Coefficients in arbitrary Dimensions using Sparse Grids

Sparse grids can be used to discretize elliptic differential equations of second order on a d-dimensional cube. Using the Ritz-Galerkin discretization, one obtains a linear equation system with 𝒪 (N (log N)^d−1) unknowns. The corresponding discretization error is 𝒪 (N⁻¹ (log N)^d−1) in the H¹-norm. A major difficulty in using this sparse grid discretization is the complexity of the related stiffness matrix. To reduce the complexity of the sparse grid discretization matrix, we apply prewavelets and a discretization with semi-orthogonality. Furthermore, a recursive algorithm is used, which performs a matrix vector multiplication with the stiffness matrix by 𝒪 (N (log N)^d−1) operations. Simulation results up to level 10 are presented for a 6-dimensional Helmholtz problem with variable coefficients. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.     

Morse index of layered solutions to the heterogeneous Allen-Cahn equation

Let u? be a single layered radially symmetric unstable solution of the Allen-Cahn equation −?²Δu=u(u−a(|x|))(1−u) over the unit ball with Neumann boundary conditions. We estimate the small eigenvalues of the linearized eigenvalue problem at u? when ? is small. As a consequence, we prove that the Morse index of u? is asymptotically given by [μ^∗+o(1)]?−(N−1)/2 with μ^∗ a certain positive constant expressed in terms of parameters determined by the Allen-Cahn equation. Our estimates on the small eigenvalues have many other applications. For example, they may be used in the search of other non-radially symmetric solutions, which will be considered in forthcoming papers.     

Solvability of nonlocal boundary value problems for ordinary differential equations of higher order

In this paper, we prove existence results for a nonlocal boundary value problem concerning a higher order differential equation. Our method is based upon the coincidence degree theory of Mawhin. The interesting point is that the degree of some variables among x₀,x₁,…,x_n−1 in the function f(t,x₀,x₁,…,x_n−1) are allowable to be greater than 1. Some examples are given to illustrate the main results.