The construction of irreducible normalized representations of the general linear group

A method is described for constructing in an explicit form an irreducible representation T of M_n(F), the set of all n × n matrices over the real or complex field F, satisfying the condition T(A^*)=T^*(A) for all A∈M_n(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 .     

On the Equation n_1n_2= n_3n_4 Restricted to Factor Closed Sets

We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.     

Weak stability for matrices

An n×n complex matrix A is called weak stable if there exists a matrix W such that W+W^* is positive definite and such that AW+W^*A^* is positive definite. In this note several characterizations for weak stability of a matrix are given, and conditions (on A) allowing W to be a diagonal matrix are also considered. A consequence of our results here is a characterization for nonsingular M-matrices.     

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.     

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.     

Harnack Differential Inequalities for the Parabolic Equation ut=LF(u) on Riemannian Manifolds and Applications

In this paper, let(M~n, g) be an n-dimensional complete Riemannian manifold with the mdimensional Bakry–mery Ricci curvature bounded below. By using the maximum principle, we first prove a Li–Yau type Harnack differential inequality for positive solutions to the parabolic equation u_t= LF(u)=ΔF(u)-f·F(u),on compact Riemannian manifolds Mn, where F∈C~2(0, ∞), F0 and f is a C~2-smooth function defined on M~n. As application, the Harnack differential inequalities for fast diffusion type equation and porous media type equation are derived. On the other hand, we derive a local Hamilton type gradient estimate for positive solutions of the degenerate parabolic equation on complete Riemannian manifolds. As application, related local Hamilton type gradient estimate and Harnack inequality for fast dfiffusion type equation are established. Our results generalize some known results.     

The thermal equilibrium state of semiconductor devices

The thermal equilibrium state of two oppositely charged gases confined to a bounded domain , m = 1,2 or m = 3, is entirely described by the gases' particle densities p, n minimizing the total energy (p, n). it is shown that for given P, N > 0 the energy functional admits a unique minimizer in {(p, n) ε L²(Ω) x L ²(Ω) : p, n ≥ 0, _Ωp = P, _Ωn = N} and that p, n ε C(Ω) ∩ L^∞(Ω).

The analysis is applied to the hydrodynamic semiconductor device equations. These equations in general possess more than one thermal equilibrium solution, but only the unique solution of the corresponding variational problem minimizes the total energy. It is equivalent to prescribe boundary data for electrostatic potential and particle densities satisfying the usual compatibility relations and to prescribe V^e and P, N for the variational problem.     

A homotopy equivalence that is not homotopic to a topological embedding

An open subset W of Sⁿ, n 6 or N = 4, and a homotopy equivalence ƒ: S² × S^{n − 4} → W are constructed having the property that ƒ is not homotopic to any topological embedding.     

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

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

On infinite area for complex exponential function

This paper shows via a reduced family of examples, the relaxed Newton's method is applied to complex exponential function F(z)=ze^z and F(z)=ze^z2, the basin of roots has infinite area. In addition, we examined their computer pictures which are fractals for the relaxed Newton's basin. In fact, computer experiments F(z)=P(z)e^z and F(z)=P(z)e^z2, indicate this to hold for arbitrary non-constant polynomial P(z).     

Dynamic motion planning in low obstacle density environments

A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n²(n) log² n) can be computed in O(n²(n) log² n) time. The dynamic motion planning problem is then solved in O(n²(n) log³ n) time. We also show that these results are close to optimal.     

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.     

On parallel rectilinear obstacle- avoiding paths

We give improved space and processor complexities for the problem of computing, in parallel, a data structure that supports queries about shortest rectilinear obstacle-avoiding paths in the plane, where the obstacles are disjoint rectangles. That is, a query specifies any source and destination in the plane, and the data structure enables efficient processing of the query. We now can build the data structure with O(n²/log n) CREW PRAM processors, as opposed to the previous O(n²), and with O(n²) space, as opposed to the previous O(n²(log n)²). The time complexity remains unchanged, at O((log n)²). As before, the data structure we compute enables a query to be processed in O(log n) time, by one processor for obtaining a path length, or by O(k/log n) processors for retrieving a shortest path itself, where k is the number of segments on that path. The new ideas that made our improvement possible include a new partitioning scheme of the recursion tree, which is used to schedule the computations performed on that tree. Since a number of other related shortest paths problems are solved using this technique as a subroutine our improvement translates into a similar improvement in the complexities of these problems as well.     

Popular distances in 3-space

Let m(n) denote the smallest integer m with the property that any set of n points in Euclidean 3-space has an element such that at most m other elements are equidistant from it. We have that cn^1/3 log log n m(n) n^3/5 β(n), where c> 0 is a constant and β(n) is an extremely slowly growing function, related to the inverse of the Ackermann function.     

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 approximation of the product of the square root of a matrix with a vector

Given an n×n symmetric positive definite matrix A and a vector , two numerical methods for approximating are developed, analyzed, and computationally tested. The first method applies a Newton iteration to a specific nonlinear system to approximate while the second method applies a step-control method to numerically solve a specific initial-value problem to approximate . Assuming that A is first reduced to tridiagonal form, the first method requires O(n²) operations per iteration while the second method requires O(n) operations per iteration. In contrast, numerical methods that first approximate A^1/2 and then compute generally require O(n³) operations per iteration.     

Commuting pairs and triples of matrices and related varieties

In this note, we show that the set of all commuting d-tuples of commuting n×n matrices that are contained in an n-dimensional commutative algebra is a closed set, and therefore, Gerstenhaber's theorem on commuting pairs of matrices is a consequence of the irreduciblity of the variety of commuting pairs. We show that the variety of commuting triples of 4×4 matrices is irreducible. We also study the variety of n-dimensional commutative subalgebras of M_n(F), and show that it is irreducible of dimension n²−n for n4, but reducible, of dimension greater than n²−n for n7.     

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