On the fourth power moment of Fourier coefficients of cusp form

Let a(n)be the Fourier coefficients of a holomorphic cusp form of weightκ=2n≥12 for the full modular group and A(x)=∑_(n≤x)a(n).In this paper,we establish an asymptotic formula of the fourth power moment of A(x)and prove that ∫T1A~4(x)dx=3/(64κπ~4)s_4;2()T~(2κ)+O(T~(2κ-δ_4+ε))with δ_4=1/8,which improves the previous result.     

Efficient Energy-preserving Methods for General Nonlinear Oscillatory Hamiltonian System

In this paper, we propose and analyze two kinds of novel and symmetric energy-preserving formulae for the nonlinear oscillatory Hamiltonian system of second-order differential equations Aq"(t)+ Bq(t)=f(q(t)), where A ∈ R^m×m is a symmetric positive definite matrix, B ∈ R^m×m is a symmetric positive semi-definite matrix that implicitly contains the main frequencies of the problem and f(q)=-▽_qV(q) for a real-valued function V(q). The energy-preserving formulae can exactly preserve the Hamiltonian H(q', q)=(1)/2q'^τ Aq' + (1)/2q^τ Bq + V(q). We analyze the properties of energy-preserving and convergence of the derived energy-preserving formula and obtain new efficient energy-preserving integrators for practical computation. Numerical experiments are carried out to show the efficiency of the new methods by the nonlinear Hamiltonian systems.     

Efficient visibility queries in simple polygons

We present a method of decomposing a simple polygon that allows the preprocessing of the polygon to efficiently answer visibility queries of various forms in an output sensitive manner. Using O(n³logn) preprocessing time and O(n³) space, we can, given a query point q inside or outside an n vertex polygon, recover the visibility polygon of q in O(logn+k) time, where k is the size of the visibility polygon, and recover the number of vertices visible from q in O(logn) time.

The key notion behind the decomposition is the succinct representation of visibility regions, and tight bounds on the number of such regions. These techniques are extended to handle other types of queries, such as visibility of fixed points other than the polygon vertices, and for visibility from a line segment rather than a point. Some of these results have been obtained independently by Guibas, Motwani and Raghavan [18] .     

Homogenization of Elliptic Problems with Neumann Boundary Conditions in Non-smooth Domains

We consider a family of second-order elliptic operators {L_ε} in divergence form with rapidly oscillating and periodic coefficients in Lipschitz and convex domains in R~n. We are able to show that the uniform W~(1,p) estimate of second order elliptic systems holds for 2n/(n+1)-δ p 2n/(n-1)+ δ where δ 0 is independent of ε and the ranges are sharp for n = 2, 3. And for elliptic equations in Lipschitz domains, the W~(1,p) estimate is true for 3/2-δ p 3 + δ if n ≥ 4, similar estimate was extended to convex domains for 1 p ∞.     

Computing rectangle enclosures

The rectangle enclosure problem is the problem of determining the subset of n iso-oriented planar rectangles that enclose a query rectangle Q. In this paper, we use a three layered data structure which is a combination of Range and Priority search trees and answers both the static and dynamic cases of the problem. Both the cases use O(n> log² n) space. For the static case, the query time is O(log² n log log n + K). The dynamic case is supported in O(log³ n + K) query time using O(log³ n) amortized time per update. K denotes the size of the answer. For the d-dimensional space the results are analogous. The query time is O(log^2d-2 n log log n + K) for the static case and O(log^2d-1 n + K) for the dynamic case. The space used is O(n> log^2d-2 n) and the amortized time for an update is O(log^2d-1 n). The existing bounds given for a class of problems which includes the present one, are O(log^2d n + K) query time, O(log^2d n) time for an insertion and O(log^2d-1 n) time for a deletion.     

Partitions of finite affine geometries into caps

In a finite geometry of order q² we define a (q^mq^r)-affine cap to be a set of cardinality q^m which is a disjoint union ot q^m affine subgeometrics AG(r,q). such that no three points are coliinear unless contained in the same AG(r,q).

Given a PG(n,q²), where n = 2t + 1 or 2t + 2, and an n + 1 by n + 1 Hermitian matrix H over Gh(q²) with minimal polynomial (x - λ)^{n + 1}. we show that H induces a partition of the AG(n, q²) obtained by deleting a distinguished hyperplane from the PG, into (qⁿ,q^{l + 1})-affine caps; these caps can be viewed as the "large points" of an AG (n,q) with a natural incidence relation. It is also shown that H induces another partition of AG(n,q²), into q^{n - l 1}-caps, constituting the "large points" of an affine geometry AG(n + t + 1,q).

Also, the collineation C of PG(n, q²) given by x^c = H^Tx induces collineations on the AG(n,q) and AG(n + t + 1,q).     

On the generalized Erdös-Szekeres Conjecture — a new upper bound

We prove the following result: For every two natural numbers n and q, n q + 2, there is a natural number E(n, q) satisfying the following:

1. (1) Let S be any set of points in the plane, no three on a line. If |S| E(n, q), then there exists a convex n-gon whose points belong to S, for which the number of points of S in its interior is 0 (mod q).

2. (2) For fixed q, E(n,q) 2^c(q)·n, c(q) is a constant depends on q only.

Part (1) was proved by Bialostocki et al. [2] and our proof is aimed to simplify the original proof. The proof of Part (2) is completely new and reduces the huge upper bound of [2] (a super-exponential bound) to an exponential upper bound.     

On the growth of components with non-fixed excesses

Denote by an l-component a connected graph with l edges more than vertices. We prove that the expected number of creations of (l+1)-component, by means of adding a new edge to an l-component in a randomly growing graph with n vertices, tends to 1 as l,n tends to ∞ but with l=o(n^1/4). We also show, under the same conditions on l and n, that the expected number of vertices that ever belong to an l-component is (12l)^1/3n^2/3.     

Biased partitions and judicious <Emphasis Type="Italic">k</Emphasis>-partitions of graphs

Let G = (V,E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1- p, let m_p(G) be the minimum of qe(V₁) +pe(V₂) over partitions V = V₁ ∪ V₂, where e(V_i) denotes the number of edges spanned by V_i. We show that if mp(G) = pqm-δ, then there exists a bipartition V₁, V₂ of G such that e(V₁) ≤ p²m - δ + p√m/2 + o(√m) and e(V₂) ≤ q²m - δ + q √m/2 + o(√m) for δ = o(m^2/3). This is sharp for complete graphs up to the error term o(√m). For an integer k ≥ 2, let fk(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk(G) = (1 - 1/k)m + α, then G admits a k-partition such that each vertex class spans at most m/k² - Ω(m/k^7.5) edges for α = Ω(m/k⁶). Both of the above improve the results of Bollobás and Scott.     

Cohomology of the Universal Enveloping Algebras of Certain Bigraded Lie Algebras

Let p be an odd prime and q = 2(p-1).Up to total degree t-s max{(5p~3+ 6p~2+ 6 p +4)q-10,p~4q},the generators of H~(s,t)(U(L)),the cohomology of the universal enveloping algebra of a bigraded Lie algebra L,are determined and their convergence is also verified.Furthermore our results reveal that this cohomology satisfies an analogous Poinare duality property.This largely generalizes an earlier classical results due to J.P.May.     

Proof of a conjecture of Fiedler and Markham

Let A be an n×n nonsingular M-matrix. For the Hadamard product AA⁻¹, M. Fiedler and T.L. Markham conjectured in [Linear Algebra Appl. 10l (1988) 1] that q(AA⁻¹)2/n, where q(AA⁻¹) is the smallest eigenvalue (in modulus) of AA⁻¹. We considered this conjecture in [Linear Algebra Appl. 288 (1999) 259] having observed an incorrect proof in [Linear Algebra Appl. 144 (1991) 171] and obtained that q(AA⁻¹)(2/n)(n−1)/n. The present paper gives a proof for this conjecture.     

A new infinite series of regular uniformly geodetic code graphs

We construct vertex-transitive graphs Γ, regular of valency k=n²+n+1 on vertices, with integral spectrum, possessing a distinguished complete matching such that contracting the edges of this matching yields the Johnson graph J(2n, n) (of valency n²). These graphs are uniformly geodetic in the sense of Cook and Pryce (1983) (F-geodetic in the sense of Ceccharini and Sappa (1986)), i.e., the number of geodesics between any two vertices only depends on their distance (and equals 4 when this distance is two). They are counterexamples to Theorem 3.15.1 of [1], and we show that there are no other counterexamples.     

The growth of laguerre matrix polynomials on bounded intervals

Let A be a matrix in ^r×r such that Re(z) > −1/2 for all the eigenvalues of A and let {π_n^(A,1/2) (x)} be the normalized sequence of Laguerre matrix polynomials associated with A. In this paper, it is proved that π_n^(A,1/2) (x) = O(n^(A)/2ln^r−1(n)) and π_n+1^(A,1/2) (x) − π_n^(A,1/2) (x) = O(n^((A)−1)/2ln^r−1(n)) uniformly on bounded intervals, where (A) = max{Re(z); z eigenvalue of A}.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

Numerical method for solving 3D inverse scattering problems

Let q(x) L²(D), D R³ is a bounded domain, q = 0 outside D, q is real-valued. Assume that A(\Gj;\t';,\Gj;,k) A(\Gj;\t';,\Gj), the scattering amplitude, is known for all \Gj;|t',\Gj; S², S² is the unit sphere, an d a fixed k \r>0. These data determine q(x) uniquely and a numerical method is given for computing q(x).     

Full quadrature sums for pth powers of polynomials with Freud weights

In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate

1 p < ∞, for every polynomial P of degree at most n + rn^1/3, where W² is a Freud weight such as exp(−¦x¦), > 1, λ_jn are the Christoffel numbers, x_jn are the zeros of the orthonormal polynomials for the weight W², and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξ_nn^1/3, where ξ_n → ∞ as n → ∞. Previous estimates could sum only over those x_jn with ¦x_jn¦ σx_1n, some fixed 0 < σ < 1.     

On the angular distribution of Gaussian integers with fixed norm

We study the distribution of lattice points a + 1b on the fixed circle a² + b² = n. Our results apply p.p. to the representable integers n, and we supply bounds for the discrepancy of the distribution, and for the maximum and minimum of the angles between consecutive points. As a corollary, we are able to show that when n is representable then it is almost surely representable with min(a, b) small, with an explicit bound.     

Factorizations of root-based polynomial compositions

Let denote the finite field of order q=p^r, p a prime and r a positive integer, and let f(x) and g(x) denote monic polynomials in of degrees m and n, respectively. Brawley and Carlitz (Discrete Math. 65 (1987) 115–139) introduce a general notion of root-based polynomial composition which they call the composed product and denote by fg. They prove that fg is irreducible over if and only if f and g are irreducible with gcd(m,n)=1. In this paper, we extend Brawley and Carlitz's work by examining polynomials which are composed products of irreducibles of non-coprime degrees. We give an upper bound on the number of distinct factors of fg, and we determine the possible degrees that the factors of fg can assume. We also determine when the bound on the number of factors of fg is met.     

Diagonal flips in pseudo-triangulations on closed surfaces

Negami has already shown that there is a natural number N(F²) for any closed surface F² such that two triangulations on F² with n vertices can be transformed into each other by a sequence of diagonal flips if nN(F²). We investigate the same theorem for pseudo-triangulations with or without loops, estimating the length of a sequence of diagonal flips. Our arguments will be applied to simple triangulations to obtain a linear upper bound for N(F²) with respect to the genus of F².     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .