A Hardy field extension of Szemerédi's theorem

In 1975 Szemerédi proved that a set of integers of positive upper density contains arbitrarily long arithmetic progressions. Bergelson and Leibman showed in 1996 that the common difference of the arithmetic progression can be a square, a cube, or more generally of the form p(n) where p(n) is any integer polynomial with zero constant term. We produce a variety of new results of this type related to sequences that are not polynomial. We show that the common difference of the progression in Szemerédi's theorem can be of the form [nδ] where δ is any positive real number and [x] denotes the integer part of x. More generally, the common difference can be of the form [a(n)] where a(x) is any function that is a member of a Hardy field and satisfies a(x)/xk→∞ and a(x)/xk+1→0 for some non-negative integer k. The proof combines a new structural result for Hardy sequences, techniques from ergodic theory, and some recent equidistribution results of sequences on nilmanifolds.     

On rational approximation of algebraic functions

We construct a new scheme of approximation of any multivalued algebraic function f(z) by a sequence {r_n(z)}_n∈N of rational functions. The latter sequence is generated by a recurrence relation which is completely determined by the algebraic equation satisfied by f(z). Compared to the usual Padé approximation our scheme has a number of advantages, such as simple computational procedures that allow us to prove natural analogs of the Padé Conjecture and Nuttall's Conjecture for the sequence {r_n(z)}_n∈N in the complement CP¹?D_f, where D_f is the union of a finite number of segments of real algebraic curves and finitely many isolated points. In particular, our construction makes it possible to control the behavior of spurious poles and to describe the asymptotic ratio distribution of the family {r_n(z)}_n∈N. As an application we settle the so-called 3-conjecture of Egecioglu et al. dealing with a 4-term recursion related to a polynomial Riemann Hypothesis.     

Extraneous fixed points,basin boundaries and chaotic dynamics for Schröder and König rational iteration functions

Summary The Schröder and König iteration schemes to find the zeros of a (polynomial) functiong(z) represent generalizations of Newton's method. In both schemes, iteration functionsf _m (z) are constructed so that sequencesz _n+1 =f _m (z _n ) converge locally to a rootz ^* ofg(z) asO(|z _n –z ^*|^m). It is well known that attractive cycles, other than the zerosz ^*, may exist for Newton's method (m=2). Asm increases, the iteration functions add extraneous fixed points and cycles. Whether attractive or repulsive, they affect the Julia set basin boundaries. The König functionsK _m (z) appear to minimize such perturbations. In the case of two roots, e.g.g(z)=z ²–1, Cayley's classical result for the basins of attraction of Newton's method is extended for allK _m (z). The existence of chaotic {z _n } sequences is also demonstrated for these iteration methods.     

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).     

The inverse of a matrix polynomial

An explicit representation is obtained for P(z)^?1 when P(z) is a complex n×n matrix polynomial in z whose coefficient of the highest power of z is the identity matrix. The representation is a sum of terms involving negative powers of z?λ for each λ such that P(λ) is singular. The coefficients of these terms are generated by sequences u_k, v_k of 1×n and n×1 vectors, respectively, which satisfy u₁≠0, v₁≠0, ∑^k?1_h=0(1?h!)u_k?hP^(h)(λ)=0, ∑^k?1_h=0(1?h!)P^(h)(λ)v_k?h=0, and certain orthogonality relations. In more general cases, including that when P(z) is analytic at λ but not necessarily a polynomial, the terms in the representation involving negative powers of z?λ provide the principal part of the Laurent expansion for P(z)^?1 in a punctured neighborhood of z=λ.     

The transcendental meromorphic solutions of a certain type of nonlinear differential equations

In this paper, we study the differential equations of the following form w²+R(z)²(w(k))=Q(z), where R(z), Q(z) are nonzero rational functions. We proved the following three conclusions: (1) If either P(z) or Q(z) is a nonconstant polynomial or k is an even integer, then the differential equation w²+P²(z)²(w(k))=Q(z) has no transcendental meromorphic solution; if P(z), Q(z) are constants and k is an odd integer, then the differential equation has only transcendental meromorphic solutions of the form f(z)=acos(bz+c). (2) If either P(z) or Q(z) is a nonconstant polynomial or k>1, then the differential equation w²+(z−z₀)P²(z)²(w(k))=Q(z) has no transcendental meromorphic solution, furthermore the differential equation w²+A(z−z₀)²(w^′)=B, where A, B are nonzero constants, has only transcendental meromorphic solutions of the form , where a, b are constants such that Ab²=1, a²=B. (3) If the differential equation , where P is a nonconstant polynomial and Q is a nonzero rational function, has a transcendental meromorphic solution, then k is an odd integer and Q is a polynomial. Furthermore, if k=1, then Q(z)≡C (constant) and the solution is of the form f(z)=Bcosq(z), where B is a constant such that B²=C and q^′(z)=±P(z).     

Complexity Estimates for the Schmüdgen Positivstellensatz

LetKbe a closed basic set inRⁿgiven by the polynomial inequalities φ₁≥ 0, . . . , φ_m≥ 0 and let Σ be the semiring generated by the φ_kand the squares inR[x₁, . . . ,x_n]. Schmüdgen has shown that ifKis compact then any polynomial function strictly positive onKbelongs to Σ. Easy consequences are (1)f≥ 0 onKif and only iff∈R⁺+ Σ (Positivstellensatz) and (2) iff≥ 0 onKbutf∈ Σ then asdtends to 0⁺, in any representation off + das an element of Σ in terms of the φ_k, the squares and semiring operations, the integerN(d) which is the minimum over all representations of the maximum degree of the summands must become arbitrarily large. A one-dimensional example is analyzed to obtain asymptotic lower and upper bounds of the formcd^−1/2≤N(d) ≤Cd^−1/2log (1/d).     

The order dimension of two levels of the Boolean lattice

LetB _n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B _n(k, n–k))=n–2 for 3k<(1/7)n ^1/3. The proof uses extremal hypergraph theory.     

Quasi-convex sequences in the circle and the 3-adic integers

In this paper, we present families of quasi-convex sequences converging to zero in the circle group T, and the group J₃ of 3-adic integers. These sequences are determined by increasing sequences of integers. For an increasing sequence , put gn=an+1−an. We prove that

(a)

the set {0}∪{±³−(an+1)|n∈N} is quasi-convex in T if and only if a₀>0 and gn>1 for every n∈N;

(b)

the set {0}∪{±an³|n∈N} is quasi-convex in the group J₃ of 3-adic integers if and only if gn>1 for every n∈N.

Moreover, we solve an open problem from [D. Dikranjan, L. de Leo, Countably infinite quasi-convex sets in some locally compact abelian groups, Topology Appl. 157 (8) (2010) 1347-1356] providing a complete characterization of the sequences such that {0}∪{±²−(an+1)|n∈N} is quasi-convex in T. Using this result, we also obtain a characterization of the sequences such that the set {0}∪{±²−(an+1)|n∈N} is quasi-convex in R.     

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 inequality for polynomials with a prescribed zero

Let p_n(z)=∑_(k-0)~n a_kz~k be a polynomial of degree n such that |p_n(z)|≤M for |z|≤1. It is well.known that for 0≤u相似文献   

On the roots of independence polynomials of almost all very well-covered graphs

If s_k denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G^*. Under certain conditions, any well-covered graph equals G^* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G^*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G^*;x) different from -1, which appears as a root of multiplicity α(G^*)-α(G) for I(G^*;x). We also prove that the real roots of I(G^*;x) are in [-1,-1/2α(G^*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.     

A q-analogue of the Riordan group

The Riordan group consisting of Riordan matrices shows up naturally in a variety of combinatorial settings. In this paper, we define a q-Riordan matrix to be a q  -analogue of the (exponential) Riordan matrix by using the Eulerian generating functions of the form _∑n?0fnzⁿ/n_!q${\sum }_{n?0}{f}_n{z}^n/n{!}_q$. We first prove that the set of q-Riordan matrices forms a loop (a quasigroup with an identity element) and find its loop structures. Next, it is shown that q-Riordan matrices associated to the counting functions may be applied to the enumeration problem on set partitions by block inversions. This notion leads us to find q-analogues of the composition formula and the exponential formula, respectively.     

Van der waerden and ramsey type games

Let us consider the following 2-player game, calledvan der Waerden game. The players alternately pick previously unpicked integers of the interval {1, 2, ...,N}. The first player wins if he has selected all members of ann-term arithmetic progression. LetW*(n) be the least integerN so that the first player has a winning strategy. By theRamsey game on k-tuples we shall mean a 2-player game where the players alternately pick previously unpicked elements of the completek-uniform hypergraph ofN verticesK _N ^k , and the first player wins if he has selected allk-tuples of ann-set. LetR _k*(n) be the least integerN so that the first player has a winning strategy. We prove (W* (n))¹/n → 2,R ₂*(n)<(2+ε) ⁿ andR _k ^* n<2 ^nk / ^k! fork ≧3.     

On the successive coefficients of close-to-convex functions

Let f∈S, f be a close-to-convex function, f_k(z)=[f(z^k)]^1/k. The relative growth of successive coefficients of f_k(z) is investigated. The sharp estimate of ||c_n+1|−|c_n|| is obtained by using the method of the subordination function.     

Para-orthogonal Laurent polynomials and associated sequences of rational functions

On the space, , of Laurent polynomials (L-polynomials) we consider a linear functional which is positive definite on (0, ) and is defined in terms of a given bisequence, { _k } _– . Two sequences of orthogonal L-polynomials, {Q _n (z) ₀ and , are constructed which span in the order {1,z ^–1,z,z ^–2,z ²,...} and {1,z,z ^–1,z ²,z ^–2,...} respectively. Associated sequences of L-polynomials {P _n (z) ₀ , and are introduced and we define rational functions , wherew is a fixed positive number. The partial fraction decomposition and integral representation of,M _n (z, w) are given and correspondence of {M _n (z, w)} is discussed. We get additional solutions to the strong Stieltjes moment problem from subsequences of {M _n (z, w)}. In particular when { _k } _– is a log-normal bisequence, {M _2n (z, w)} and {M _2n+1 (z, w)} yield such solutions.Research supported in part by the National Science Foundation under Grant DMS-9103141.     

The Cardinality of Sets of <Emphasis Type="Italic">k</Emphasis>-Independent Vectors over Finite Fields

A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind _q (n, k) of a k-independent set of vectors in the n-dimensional vector space F _q ⁿ over the finite field F _q of order q. Namely, we give a necessary and sufficient condition for Ind _q (n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes. Supported, in part by grants EP/C000285, NSF-DMS-0439734 and NSF-DMS-0555839. S. B. Damelin thanks the Institute for Mathematics and Applications for their hospitality.     

Two results on homogeneous Hessian nilpotent polynomials

Let z=(z₁,…,z_n) and , the Laplace operator. A formal power series P(z) is said to be Hessian Nilpotent (HN) if its Hessian matrix is nilpotent. In recent developments in [M. de Bondt, A. van den Essen, A reduction of the Jacobian conjecture to the symmetric case, Proc. Amer. Math. Soc. 133 (8) (2005) 2201-2205. [MR2138860]; G. Meng, Legendre transform, Hessian conjecture and tree formula, Appl. Math. Lett. 19 (6) (2006) 503-510. [MR2170971]. See also math-ph/0308035; W. Zhao, Hessian nilpotent polynomials and the Jacobian conjecture, Trans. Amer. Math. Soc. 359 (2007) 249-274. [MR2247890]. See also math.CV/0409534], the Jacobian conjecture has been reduced to the following so-called vanishing conjecture (VC) of HN polynomials: for any homogeneous HN polynomialP(z) (of degreed=4), we haveΔ^mP^m+1(z)=0for anym?0. In this paper, we first show that the VC holds for any homogeneous HN polynomial P(z) provided that the projective subvarieties Z_P and Z_σ2 of CPⁿ⁻¹ determined by the principal ideals generated by P(z) and , respectively, intersect only at regular points of Z_P. Consequently, the Jacobian conjecture holds for the symmetric polynomial maps F=z−∇P with P(z) HN if F has no non-zero fixed point w∈Cⁿ with . Secondly, we show that the VC holds for a HN formal power series P(z) if and only if, for any polynomial f(z), Δ^m(f(z)P(z)^m)=0 when m?0.     

On the Asymptotic Behavior of Faber Polynomials for Domains With Piecewise Analytic Boundary

Let φ(z) be an analytic function on a punctured neighborhood of ∞, where it has a simple pole. The nth Faber polynomial F _n (z) (n=0,1,2,…) associated with φ is the polynomial part of the Laurent expansion at ∞ of [φ(z)] ⁿ . Assuming that ψ (the inverse of φ) conformally maps |w|>1 onto a domain Ω bounded by a piecewise analytic curve without cusps pointing out of Ω, and under an additional assumption concerning the “Lehman expansion” of ψ about those points of |w|=1 mapped onto corners of ∂ Ω, we obtain asymptotic formulas for F _n that yield fine results on the limiting distribution of the zeros of Faber polynomials.