Carathéodory interpolation on the non-commutative polydisk

The Carathéodory problem in the N-variable non-commutative Herglotz-Agler class and the Carathéodory-Fejér problem in the N-variable non-commutative Schur-Agler class are posed. It is shown that the Carathéodory (resp., Carathéodory-Fejér) problem has a solution if and only if the non-commutative polynomial with given operator coefficients (the data of the problem indexed by an admissible set Λ) takes operator values with positive semidefinite real part (resp., contractive operator values) on N-tuples of Λ-jointly nilpotent contractive n×n matrices, for all n∈N.     

Representation of group elements as subsequence sums

Let G be a finite (additive written) abelian group of order n. Let w₁,…,w_n be integers coprime to n such that w₁+w₂+?+w_n≡0 (mod n). Let I be a set of cardinality 2n-1 and let ξ={x_i:i∈I} be a sequence of elements of G. Suppose that for every subgroup H of G and every a∈G, ξ contains at most terms in a+H.Then, for every y∈G, there is a subsequence {y₁,…,y_n} of ξ such that y=w₁y₁+?+w_ny_n.Our result implies some known generalizations of the Erd?s-Ginzburg-Ziv Theorem.     

Convex integer maximization via Graver bases

We present a new algebraic algorithmic scheme to solve convex integer maximization problems of the following form, where c is a convex function on R^d and w₁x,…,w_dx are linear forms on Rⁿ,

max{c(w₁x,…,w_dx):Ax=b,x∈Nⁿ}.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

Oscillations of the system of linear nonautonomous difference equations

We consider the linear nonautonomous system of difference equations x_n+1−x_n+P(n)x_n−k=0, n=0,1,2,… , where k∈Z, P(n)∈R^rxr. We obtain sufficient conditions for the system to be oscillatory. The conditions based on the eigenvalues of the matrix coefficients of the system.     

Davenport constant with weights and some related questions, II

Let G be a finite abelian group of order n and let A⊆Z be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by DA(G), to be the least natural number k such that for any sequence (x₁,…,xk) with xi∈G, there exists a non-empty subsequence (xj₁,…,xjl) and a₁,…,al∈A such that . Similarly, for any such set A, EA(G) is defined to be the least t∈N such that for all sequences (x₁,…,xt) with xi∈G, there exist indices j₁,…,jn∈N,1?j₁<?<jn?t, and ?₁,…,?n∈A with . In the present paper, we establish a relation between the constants DA(G) and EA(G) under certain conditions. Our definitions are compatible with the previous generalizations for the particular group G=Z/nZ and the relation we establish had been conjectured in that particular case.     

On analytic equivalence of functions at infinity

In this paper we define the relation of analytic equivalence of functions at infinity. We prove that if the ?ojasiewicz exponent at infinity of the gradient of a polynomial f∈R[x₁,…,xn] is greater or equal to k−1, then there exists ε>0 such that for every polynomial P∈R[x₁,…,xn] of degree less or equal to k, whose coefficients of monomials of degree k are less or equal ε, the polynomials f and f+P are analytically equivalent at infinity.     

A singular boundary value problem for odd-order differential equations

The odd-order differential equation (−1)ⁿx⁽²ⁿ⁺¹⁾=f(t,x,…,x⁽²ⁿ⁾) together with the Lidstone boundary conditions x^(2j)(0)=x^(2j)(T)=0, 0?j?n−1, and the next condition x⁽²ⁿ⁾(0)=0 is discussed. Here f satisfying the local Carathéodory conditions can have singularities at the value zero of all its phase variables. Existence result for the above problem is proved by the general existence principle for singular boundary value problems.     

On the minimum number of completely 3-scrambling permutations

A family P={π₁,…,π_q} of permutations of [n]={1,…,n} is completely k-scrambling [Spencer, Acta Math Hungar 72; Füredi, Random Struct Algor 96] if for any distinct k points x₁,…,x_k∈[n], permutations π_i's in P produce all k! possible orders on π_i(x₁),…,π_i(x_k). Let N^*(n,k) be the minimum size of such a family. This paper focuses on the case k=3. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison.

     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

The inversion formulae for automorphisms of polynomial algebras and rings of differential operators in prime characteristic

Let K be an arbitrary field of characteristic p>0. We find an explicit formula for the inverse of any algebra automorphism of any of the following algebras: the polynomial algebra P_n?K[x₁,…,x_n], the ring of differential operators D(P_n) on P_n, D(P_n)⊗P_m, the n’th Weyl algebra A_n or A_n⊗P_m, the power series algebra K[[x₁,…,x_n]], the subalgebra T_k1,…,kn of D(P_n) generated by P_n and the higher derivations , 0≤j<p^k_i, i=1,…,n (where k₁,…,k_n∈N), T_k1,…,kn⊗P_m or an arbitrary central simple (countably generated) algebra over an arbitrary field.     

A residual transcendental extension of a valuation on K to K(x1, … , xn)

Let v be a valuation of a field K, G_v its value group and k_v its residue field. Let w be an extension of v to K(x₁, … , x_n). w is called a residual transcendental extension of v if k_w/k_v is a transcendental extension. In this study a residual transcendental extension w of v to K(x₁, … , x_n) such that transdegk_w/k_v = n is defined and some considerations related with this valuation are given.     

A sufficient condition for a polynomial to be stable

A real polynomial is called Hurwitz (stable) if all its zeros have negative real parts. For a given n∈N we find the smallest possible constant dn>0 such that if the coefficients of F(z)=a₀+a₁z+?+anzn are positive and satisfy the inequalities akak+1>dnak−1ak+2 for k=1,2,…,n−2, then F(z) is Hurwitz.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

Effective computation of singularities of parametric affine curves

Let k be a field of characteristic zero and f(t),g(t) be polynomials in k[t]. For a plane curve parameterized by x=f(t),y=g(t), Abhyankar developed the notion of Taylor resultant (Mathematical Surveys and Monographs, Vol. 35, American Mathematical Society, Providence, RI, 1990) which enables one to find its singularities without knowing its defining polynomial. This concept was generalized as D-resultant by Yu and Van den Essen (Proc. Amer. Math. Soc. 125(3) (1997) 689), which works over an arbitrary field. In this paper, we extend this to a curve in affine n-space parameterized by x₁=f₁(t),…,x_n=f_n(t) over an arbitrary ground field k, where f₁,…,f_n∈k[t]. This approach compares to the usual approach of computing the ideal of the curve first. It provides an efficient algorithm of computing the singularities of such parametric curves using Gröbner bases. Computational examples worked out by symbolic computation packages are included.     

Global stability in difference equations satisfying the generalized Yorke condition

We present several conditions sufficient for global stability of the zero solution of nonautonomous difference equation xn+1=qxn+fn(xn,…,xn−k), n∈Z, when the nonlinearities fn satisfy a sort of negative feedback condition. Moreover, for every k∈N, we indicate qk such that one of our stability conditions is sharp if q∈(0,qk]. We apply our results to discrete versions of Nicholson's blowflies equation, the Mackey-Glass equations, and the Wazewska and Lasota equation.     

Singular integral operators and norm ideals satisfying a quantitative variant of Kuroda's condition

A norm ideal C is said to satisfy condition (QK) if there exist constants 0<t<1 and 0<B<∞, such that ∥X^[k]∥_C?Bk^t∥X∥_C for every finite-rank operator X and every k∈N, where X^[k] denotes the direct sum of k copies of X. Let μ be a regular Borel measure whose support is contained in a unit cube Q in Rⁿ and let K_j be the singular integral operator on L²(Rⁿ,μ) with the kernel function (x_j-y_j)/|x-y|², 1?j?n. Let {Q_w:w∈W} be the usual dyadic decomposition of Q, i.e., {Q_w:|w|=?} is the dyadic partition of Q by cubes of the size 2^-?×?×2^-?. We show that if C satisfies (QK) and if ∥∑_w∈W2^|w|μ(Q_w)ξ_w⊗ξ_w∥_C^′<∞, where C^′ is the dual of C⁽⁰⁾ and {ξ_w:w∈W} is any orthonormal set, then K₁,…,K_n∈C^′. This is a very general obstruction result for the problem of simultaneous diagonalization of commuting tuples of self-adjoint operators modulo C.     

A note on properties of locally finitely convergent sequences with respect to median filter

Let F_k be a mapping from R^Z to R^Z, satisfying that for x∈R^Z and n∈Z, F_k(x)(n) is the (k+1)th largest value (median value) of the 2k+1 numbers x(n−k),…,x(n),…,x(n+k). In [3] [W.Z. Ye, L. Wang, L.G. Xu, Properties of locally convergent sequences with respect to median filter, Discrete Mathematics 309 (2009) 2775–2781], we conjectured that for k∈{2,3}, if there exists n₀∈Z such that x is locally finitely convergent with respect to F_k on {n₀,…,n₀+k−1}, then x is finitely convergent with respect to F_k. In this paper, we obtain some sufficient conditions for a sequence finitely converging with respect to median filters. Based on these results, we prove that the conjecture is true.     

Nontrivial lower bounds for the least common multiple of some finite sequences of integers

We present here a method which allows to derive a nontrivial lower bounds for the least common multiple of some finite sequences of integers. We obtain efficient lower bounds (which in a way are optimal) for the arithmetic progressions and lower bounds less efficient (but nontrivial) for quadratic sequences whose general term has the form un=an(n+t)+b with (a,t,b)∈Z³, a?5, t?0, gcd(a,b)=1. From this, we deduce for instance the lower bound: lcm{¹²+1,²²+1,…,n²+1}?0,32n(1,442) (for all n?1). In the last part of this article, we study the integer lcm(n,n+1,…,n+k) (k∈N, n∈N^∗). We show that it has a divisor dn,k simple in its dependence on n and k, and a multiple mn,k also simple in its dependence on n. In addition, we prove that both equalities: lcm(n,n+1,…,n+k)=dn,k and lcm(n,n+1,…,n+k)=mn,k hold for an infinitely many pairs (n,k).