The Incidence Divisor of Cycles in Projective Space

For nonnegative integers a, b with a + b + 1 = n, we show the incidence locus has the structure of an effective Cartier divisor in the product of Chow varieties 𝒞 _a (? ⁿ ) × 𝒞 _b (? ⁿ ).     

Periodicity and attractivity for a rational recursive sequence

In this paper, the existence of periodic positive solution and the attractivity are investigated for the rational recursive sequencex _n+1=(A+ax _n?k )/(b+x _n?1), whereA, a andb are real numbers,k andl are nonnegative integer numbers.     

On generalizations of network design problems with degree bounds

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely laminar crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as matroid intersection and lattice polyhedra. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems. Our main result is a (1, b + O(log n))-approximation algorithm for the minimum crossing spanning tree (MCST) problem with laminar degree constraints. The laminar MCST problem is a natural generalization of the well-studied bounded-degree MST, and is a special case of general crossing spanning tree. We give an additive Ω(log ^c m) hardness of approximation for general MCST, even in the absence of costs (c > 0 is a fixed constant, and m is the number of degree constraints). This also leads to a multiplicative Ω(log ^c m) hardness of approximation for the robust k-median problem (Anthony et al. in Math Oper Res 35:79–101, 2010), improving over the previously known factor 2 hardness. We then consider the crossing contra-polymatroid intersection problem and obtain a (2, 2b + Δ ? 1)-approximation algorithm, where Δ is the maximum element frequency. This models for example the degree-bounded spanning-set intersection in two matroids. Finally, we introduce the crossing latticep olyhedron problem, and obtain a (1, b + 2Δ ? 1) approximation algorithm under certain condition. This result provides a unified framework and common generalization of various problems studied previously, such as degree bounded matroids.     

Dynamics of a family of piecewise-linear area-preserving plane maps III. Cantor set spectra

This paper studies the behavior under iteration of the maps T _ab (x,y) = (F _ab (x) ? y, x) of the plane ?², in which F _ab (x) = ax if x ≥ 0 and bx if x < 0. These maps are area-preserving homeomorphisms of ?² that map rays from the origin to rays from the origin. Orbits of the map correspond to solutions of the nonlinear difference equation x _n+2 = 1/2(a ? b)|x _n+1|+1/2(a+b)x _n+1 ? x _n . This difference equation can be rewritten in an eigenvalue form for a nonlinear difference operator of Schrödinger type ? x _n+2+2x _n+1 ? x _n +V _μ(x _n+1)x _n+1 = Ex _n+1, in which μ = (1/2)(a ? b) is fixed, and V _μ(x) = μ(sgn(x)) is an antisymmetric step function potential, and the energy E = 2 ? 1/2(a+b). We study the set Ω _SB of parameter values where the map T _ab has at least one bounded orbit, which correspond to l _∞-eigenfunctions of this difference operator. The paper shows that for transcendental μ the set Spec_∞[μ] of energy values E having a bounded solution is a Cantor set. Numerical simulations suggest the possibility that these Cantor sets have positive (one-dimensional) measure for all real values of μ.     

Testing integer knapsacks for feasibility

We present a new approach for determining whether there exist nonnegative integers x₁, x₂, …, x_n satisfying a₁x₁ + a₂x₂ + ? + a_nx_n = b, where a₁ < a₂ < ? < a_n and b are nonnegative integers. case time complexity is analyzed and compared with dynamic programming techniques. Computational results are given.     

An O(n 2) active set algorithm for the solution of a parametric quadratic program

In this paper, an O(n ²) active set method is presented for minimizing the parametric quadratic function (1/2)x′Dx-a′x + λmax(c - γ x,0) subject to l ⩽ x ⩽ b, for all nonnegative values of the parameter γ. Here, D is a positive diagonal n x n matrix, a and γ are arbitrary N-vectors, c is an arbitrary scalar, l and b are arbitrary n-vectors, such thatl ⩽ b. An extension of this algorithm is presented for minimizing the parametric function (1/2)x′Dx-a ^′ x + λ |γ′x - c| subject to l ⩽ x ⩽ b. It is also shown that these problems arise naturally in a tax programming problem. This revised version was published online in August 2006 with corrections to the Cover Date.     

Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations

We define a class of monotone integer programs with constraints that involve up to three variables each. A generic constraint in such integer program is of the form ax−by⩽z+c, where a and b are nonnegative and the variable z appears only in that constraint. We devise an algorithm solving such problems in time polynomial in the length of the input and the range of variables U. The solution is obtained from a minimum cut on a graph with O(nU) nodes and O(mU) arcs where n is the number of variables of the types x and y and m is the number of constraints. Our algorithm is also valid for nonlinear objective functions.Nonmonotone integer programs are optimization problems with constraints of the type ax+by⩽z+c without restriction on the signs of a and b. Such problems are in general NP-hard. We devise here an algorithm, relying on a transformation to the monotone case, that delivers half integral superoptimal solutions in polynomial time. Such solutions provide bounds on the optimum value that can only be superior to bounds provided by linear programming relaxation. When the half integral solution can be rounded to an integer feasible solution, this is a 2-approximate solution. In that the technique is a unified 2-approximation technique for a large class of problems. The results apply also for general integer programming problems with worse approximation factors that depend on a quantifier measuring how far the problem is from the class of problems we describe.The algorithm described here has a wide array of problem applications. An additional important consequence of our results is that nonmonotone problems in the framework are MAX SNP-hard and at least as hard to approximate as vertex cover.Problems that are amenable to the analysis provided here are easily recognized. The analysis itself is entirely technical and involves manipulating the constraints and transforming them to a totally unimodular system while losing no more than a factor of 2 in the integrality.     

On a conjecture of Butler and Graham

Motivated by a hat guessing problem proposed by Iwasawa, Butler and Graham made the following conjecture on the existence of a certain way of marking the coordinate lines in [k] ⁿ : there exists a way to mark one point on each coordinate line in [k] ⁿ , so that every point in [k] ⁿ is marked exactly a or b times as long as the parameters (a, b, n, k) satisfies that there are nonnegative integers s and t such that s + t = k ⁿ and as + bt = nk ^n?1. In this paper we prove this conjecture for any prime number k. Moreover, we prove the conjecture for the case when a = 0 for general k.     

Calculating the numbers of representations and the Garsia entropy in linear numeration systems

Given a ≥ b, let G ₀ = 1, G ₁ = a + 1, and G _n+2 = aG _n+1 + bG _n for n ≥ 0. For each choice of a and b, we have a linear recurrence that defines a numeration system. Every positive integer n may be written as the sum of the G _n , with alphabet A = {0,1, . . . , a}, in one or more different ways. Let R _(a,b)(n) be the function that counts the number of distinct representations of an integer as a sum of the G _n . We extend results of Berstel, Kocábová, Masáková, and Pelantová, and Edson and Zamboni and give two distinct methods for calculating R _(a,b)(n). One formula involves products of 2 × 2 matrices and the other sums of binomial coefficients modulo 2. For the main result, we consider the limiting measure μ _β of a convergent infinite convolution of measures (Bernoulli convolutions), where β is the dominating root of the characteristic equation of the recurrence above. We study the Garsia entropy of these measures and calculate explicitly the limiting entropy associated with μ _β . This result extends those of Alexander and Zagier, and Grabner, Kirschenhofer, and Tichy. We then see that all these results can be generalized further to confluent numeration systems.     

The Topkis-Veinott algorithm for solving nonlinear programs with lower and upper bounded variables

In this paper we consider a nonlinear programming problem of the form to minimize f(x) subject to a x b, where f is a differentiable function on E_n and a and b are fixed vectors in E_n. We develop a variation of the feasible direction algorithm of Topkis and Veinott for solving the above problem and provide explicit expressions of the optimal directions for a family of direction-finding problems using different normalization constraints. We show that the algorithm converges to a Kuhn-Tucker point. The reported computational results indicate efficiency of the algorithm. It also indicates the strong effect of the form of the normalization constraint on convergence properties.     

On the mean square of the error term for the asymmetric two-dimensional divisor problem (I)

Suppose a and b are two fixed positive integers such that (a, b) = 1. In this paper we shall establish an asymptotic formula for the mean square of the error term Δ _a,b (x) of the general two-dimensional divisor problem.     

On bounds for eigenvalues of real symmetric matrices

Let A=(a_ij) be a real symmetric matrix of order n. We characterize all nonnegative vectors x=(x₁,...,x_n) and y=(y₁,...,y_n) such that any real symmetric matrix B=(b_ij), with b_ij=a_ij, i≠jhas its eigenvalues in the union of the intervals [b_ij?y_i, b_ij+ x_i]. Moreover, given such a set of intervals, we derive better bounds for the eigenvalues of B using the 2n quantities {b_ii?y, b_ii+x_i}, i=1,..., n.     

A binary linear recurrence sequence of composite numbers

Let (a,b)∈Z², where b≠0 and (a,b)≠(±2,−1). We prove that then there exist two positive relatively prime composite integers x₁, x₂ such that the sequence given by xn+1=axn+bxn−1, n=2,3,… , consists of composite terms only, i.e., |xn| is a composite integer for each n∈N. In the proof of this result we use certain covering systems, divisibility sequences and, for some special pairs (a,±1), computer calculations. The paper is motivated by a result of Graham who proved this theorem in the special case of the Fibonacci-like sequence, where (a,b)=(1,1).     

Asymptotic behavior of the least common multiple of consecutive arithmetic progression terms

Let l and m be two integers with l > m ≥ 0, and let a and b be integers with a ≥ 1 and a + b ≥ 1. In this paper, we prove that log lcm _{mn < i ≤ ln} {ai + b} = An + o(n), where A is a constant depending on l, m and a.     

The asymptotic stability of difference equations

In this paper, the linear delay difference equation x_n+1 −x_n = −a_nx_n−k, where a_n ≥ 0 (n ≥ 0) any nonnegative coefficient sequence, is considered and its stability properties are investigated. The obtained result is extended to the nonlinear difference equation x_n+1 − x_n = f_n(x_n−k).     

Fast Growing Solutions of Linear Differential Equations in the Unit Disc

For $n \in \mathbb{N}$ , the n-order of an analytic function f in the unit disc D is defined by $$\sigma _{{{M,n}}} (f) = {\mathop {\lim \sup }\limits_{r \to 1^{ - } } }\frac{{\log ^{ + }_{{n + 1}} M(r,f)}} {{ - \log (1 - r)}},$$ where log⁺ x  =  max{log x, 0}, log ⁺ ₁ x  =  log ⁺ x, log ⁺ _n+1 x  =  log ⁺ log ⁺ _n x, and M(r, f) is the maximum modulus of f on the circle of radius r centered at the origin. It is shown, for example, that the solutions f of the complex linear differential equation $$f^{{(k)}} + a_{{k - 1}} (z)f^{{(k - 1)}} + \cdots + a_{1} (z)f^{\prime} + a_{0} (z)f = 0,\quad \quad \quad (\dag)$$ where the coefficients are analytic in D, satisfy σ _M,n+1(f)  ≤  α if and only if σ _M,n (a _j )  ≤  α for all j  =  0, ..., k ? 1. Moreover, if q ∈{0, ..., k ? 1} is the largest index for which $\sigma _{M,n} ( a_{q}) = {\mathop {\max }\limits_{0 \leq j \leq k - 1} }{\left\{ {\sigma _{{M,n}} {\left( {a_{j} } \right)}} \right\}}$ , then there are at least k ? q linearly independent solutions f of ( $\dag$ ) such that σ _M,n+1(f) = σ _M,n (a _q ). Some refinements of these results in terms of the n-type of an analytic function in D are also given.     

The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem

This paper deals with the quality of approximative solutions for the Subset-Sum-Maximization-Problem maximize $$\sum\limits_{i = l}^n {a_i x_i } $$ subject to $$\sum\limits_{i = l}^n {a_i x_i } \leqslant b$$ wherea _l,...,a_n,bεR⁺ andx _l,...x_nε{0,1}. produced by certain heuristics of a Greedy-type. Every heuristic under consideration realizes a feasible solution (x ₁, ..., x_n) whose objective value is less or equal the optimal value, which is of course not greater thanb. We use the gap between capacityb and realized value as an upper bound for the error made by the heuristic and as a criterion for quality. Under the stochastic model:a ₁, ..., a_n, b independent,a ₁...,a_n uniformly distributed on [0, 1], b uniformly distributed on [0,n] we derive the gap-distributions and the expected size of the gaps. The analyzed algorithms include four algorithms which can be done in linear time and four heuristics which require sorting, which means that they are done inO(nlnn) time.     

Real Zeros of Algebraic Polynomials with Dependent Random Coefficients

The expected number of real zeros of polynomials a ₀ + a ₁ x + a ₂ x ² +…+a _n?1 x ^n?1 with random coefficients is well studied. For n large and for the normal zero mean independent coefficients, irrespective of the distribution of coefficients, this expected number is known to be asymptotic to (2/π)log n. For the dependent cases studied so far it is shown that this asymptotic value remains O(log n). In this article, we show that when cov(a _i , a _j ) = 1 ? |i ? j|/n, for i = 0,…, n ? 1 and j = 0,…, n ? 1, the above expected number of real zeros reduces significantly to O(log n)^1/2.     

The Lower Socle and Finite Rank Elementary Operators

Abstract

We define the lower socle of a semiprime algebra 𝒜 as the sum of all minimal left ideals 𝒜e where e is a minimal idempotent such that the division algebra e𝒜e is finite dimensional. We study the connection between the condition that the elements a _k , b _k , 1 ≤ k ≤ n, lie in the lower socle of 𝒜 and the condition that the elementary operator x ? a ₁ xb ₁ + ? + a _n xb _n has finite rank. As an application we obtain some results on derivations certain of whose powers have finite rank.     

Permutation Polynomials Modulo 2w

We give an exact characterization of permutation polynomials modulo n=2^w, w≥2: a polynomial P(x)=a₀+a₁x +···+a_dx^d with integral coefficients is a permutation polynomial modulo n if and only if a₁ is odd, (a₂+a₄+a₆+···) is even, and (a₃+a₅+a₇+···) is even. We also characterize polynomials defining latin squares modulo n=2^w, but prove that polynomial multipermutations (that is, a pair of polynomials defining a pair of orthogonal latin squares) modulo n=2^wdo not exist.