Strang-type preconditioners for systems of LMF-based ODE codes

We consider the solution of ordinary differential equations(ODEs) using boundary value methods. These methods require thesolution of one or more unsymmetric, large and sparse linearsystems. The GMRES method with the Strang-type block-circulantpreconditioner is proposed for solving these linear systems.We show that if an A_k1,k2 -stable boundary value method is usedfor an m-by-m system of ODEs, then our preconditioners are invertibleand all the eigenvalues of the preconditioned systems are 1except for at most 2m(k₁ + k₂) outliers. It follows that whenthe GMRES method is applied to solving the preconditioned systems,the method will converge in at most 2m(k₁ + k₂) + 1 iterations.Numerical results are given to illustrate the effectivenessof our methods. Received 8 October 1999. Accepted 30 May 2000.     

Stability in the Sense of Bounded Average Power

An R^m-valued sequence (x_k): = (x_k : k = 1, 2, ...), e.g. generatedrecursively by x_k = f_k (x_k–_k, U_k), is called ‘averagepth power bounded’ if (1/K) is bounded uniformly in K= 1, 2,.... (The case p = 2 may correspond to ‘power’in the physical sense.) This is a notion of stability. Givenestimates of the form: f_k (x, u) < a x + ¶ _k conditionsare obtained on the coefficient sequence (a_k) and the inputestimates e_k:=¶_k (u_k) which ensure this form of stabilityfor the output (x_k). In particular, a condition (utilized inan application to adaptive control) is obtained which imposes(i) a bound b on (a_k) and a ‘sparsity measure’ m(K) on #{kK: a_k>} as K ( >1) (ii) average pth power boundednesson (e_k), and (iii) a growth condition on (e_k) related to b andm (•). This condition is sharp.     

Higher string topology on general spaces

In this paper, I give a generalized analogue of the string topologyresults of Chas and Sullivan, and of Cohen and Jones. For afinite simplicial complex X and k 1, I construct a spectrumMaps(S^k, X)^S(X), which is obtained by taking a generalizationof the Spivak bundle on X (which however is not a stable spherebundle unless X is a Poincaré space), pulling back toMaps(S^k, X) and quotienting out the section at infinity. I showthat the corresponding chain complex is naturally homotopy equivalentto an algebra over the (k + 1)-dimensional unframed little diskoperad C_{k + 1}. I also prove a conjecture of Kontsevich, whichstates that the Quillen cohomology of a based C_k-algebra (inthe category of chain complexes) is equivalent to a shift ofits Hochschild cohomology, as well as prove that the operadC_*C_k is Koszul-dual to itself up to a shift in the derived category.This gives one a natural notion of (derived) Koszul dual C_*C_k-algebras.I show that the cochain complex of X and the chain complex of^k X are Koszul dual to each other as C_*C_k-algebras, and thatthe chain complex of Maps(S^k, X)^S(X) is naturally equivalentto their (equivalent) Hochschild cohomology in the categoryof C_* C_k-algebras. 2000 Mathematics Subject Classification 55P48(primary), 16E40, 55N45, 18D50 (secondary).     

BENFORD'S LAW FOR THE 3x + 1 FUNCTION

Benford's law (to base B) for an infinite sequence {x_k : k 1} of positive quantities x_k is the assertion that {log_B x_k: k 1} is uniformly distributed (mod 1). The 3x + 1 functionT(n) is given by T(n) = (3n + 1)/2 if n is odd, and T(n) = n/2if n is even. This paper studies the initial iterates x_k = T^(k)(x₀)for 1 k N of the 3x + 1 function, where N is fixed. It showsthat for most initial values x₀, such sequences approximatelysatisfy Benford's law, in the sense that the discrepancy ofthe finite sequence {log_B x_k : 1 k N} is small.     

Determination of a Convex Body from Minkowski Sums of its Projections

For a convex body K in R^d and 1 K d – 1, let P_K (K)be the Minkowski sum (average) of all orthogonal projectionsof K onto k-dimensional subspaces of R^d. It is Known that theoperator P_k is injective if kd/2, k=3 for all d, and if k =2, d 14. It is shown that P_2k (K) determines a convex body K among allcentrally symmetric convex bodies and P_2k+1(K) determines aconvex body K among all bodies of constant width. Correspondingstability results are also given. Furthermore, it is shown thatany convex body K is determined by the two sets P_k (K) and P_k'(K) if 1 < k < k'. Concerning the range of P_k , 1 k d–2, it is shown that its closure (in the Hausdorff-metric)does not contain any polytopes other than singletons.     

Replacement of Factors by Subgroups in the Factorization of Abelian Groups

The above-titled paper of mine appeared in the Bulletin of theLondon Mathematical Society, 32 (2000) 297–304. Regrettably,there is a careless error in the proofs of Theorems 6 and 8.In line 6 of the proof of Theorem 6, it is claimed that a certainsubset must be a subgroup. For this to hold, the subset mustcontain the zero element. This need not be the case; the truededuction is that the subset is a coset, say M + h, of a subgroupM. Now M and M + h contain the same number of elements, andso the deduction that M has p elements is still correct. Similarly, in the proof of Theorem 8, the subgroup M_k must bereplaced by a coset M_k + h_k. This is the only change neededin this proof, since the sum M_k+h_k+(nBH) being direct impliesthat the sum M_k+(nBH) is also direct. Since the zero elementdoes belong to the sets (mAH) and (nBH), the statements aboutthese sets are correct. So the second paragraph of the Proofof Theorem 8 is correct, and is also a proof of Theorem 6. Now we present an example that, we hope, will clarify the situation,as well as showing that certain statements in the original ‘Proof’of Theorem 6 not only could be wrong but actually are wrong.The smallest numerical example occurs with p = 2, m = 3, n =5. Then G is a cyclic group of order 60, and may be representedas the integers modulo 60. Let A = {0, 1, 2, 3, 4} + {0, 15} and B = {0, 5, 10} + {0, 30}.It is easily verified that A + B = {0, 1,..., 59}. In the notationof Theorem 6, we see that H = {0, 15, 30, 45}, K = {0, 12, 24,36, 48}, L = {0, 20, 40}, and M = {0, 30}. Now we see that mA= {0, 3, 6, 9, 12} + {0, 45} M + K, and that nB = {0, 25, 50}+ {0, 30} M + L. We note, however, that A is a complete setof residues modulo 10; that is, that B can be replaced by M+ L.     

Mixed hp-DGFEM for incompressible flows II: Geometric edge meshes

We consider the Stokes problem of incompressible fluid flowin three-dimensional polyhedral domains discretized on hexahedralmeshes with hp-discontinuous Galerkin finite elements of typeQ_k for the velocity and Q_k–1 for the pressure. We provethat these elements are inf-sup stable on geometric edge meshesthat are refined anisotropically and non-quasiuniformly towardsedges and corners. The discrete inf-sup constant is shown tobe independent of the aspect ratio of the anisotropic elementsand is of O(k^–3/2) in the polynomial degree k, as in thecase of conforming Q_k–Q_k–2 approximations on thesame meshes.     

The Betti Numbers of the Free Loop Space of a Connected Sum

Let M₁ and M₂ be two simply connected closed manifolds of thesame dimension. It is proved that (1) if k is a coefficient field such that neither M₁ nor M₂has the same cohomology as a sphere, then the sequence (b_k)_k1of Betti numbers of the free loop space on M₁ #M₂ is unbounded; (2) if, moreover, the cohomology H*(M₁;k) is not generated asalgebra by only one element, then the sequence (b_k)_k1 has anexponential growth. Thanks to theorems of Gromoll and Meyer and of Gromov, thisimplies, in case 1, that there exist infinitely many closedgeodesics on M₁#M₂ for each Riemannian metric, and, in case2, that for a generic metric, the number of closed geodesicsof length t grows exponentially with t.     

On Artin's Conjecture, I: Systems of Diagonal Forms

As a special case of a well-known conjecture of Artin, it isexpected that a system of R additive forms of degree k, say [formula] with integer coefficients a_ij, has a non-trivial solution inQ_p for all primes p whenever [formula] Here we adopt the convention that a solution of (1) is non-trivialif not all the x_i are 0. To date, this has been verified onlywhen R=1, by Davenport and Lewis [4], and for odd k when R=2,by Davenport and Lewis [7]. For larger values of R, and in particularwhen k is even, more severe conditions on N are required toassure the existence of p-adic solutions of (1) for all primesp. In another important contribution, Davenport and Lewis [6]showed that the conditions [formula] are sufficient. There have been a number of refinements of theseresults. Schmidt [13] obtained N>>R²k³ log k, and Low,Pitman and Wolff [10] improved the work of Davenport and Lewisby showing the weaker constraints [formula] to be sufficient for p-adic solubility of (1). A noticeable feature of these results is that for even k, onealways encounters a factor k³ log k, in spite of the expectedk² in (2). In this paper we show that one can reach the expectedorder of magnitude k². 1991 Mathematics Subject Classification11D72, 11D79.     

On Waring's Problem in Number Fields

Let K be an algebraic number field of degree n over the rationals,and denote by J_k the subring of K generated by the kth powersof the integers of K. Then G_K(k) is defined to be the smallests1 such that, for all totally positive integers vJ_k of sufficientlylarge norm, the Diophantine equation (1.1) is soluble in totally non-negative integers _i of K satisfying N(_i)<<N(v)^1/k (1is). (1.2) In (1.2) and throughout this paper, all implicit constants areassumed to depend only on K, k, and s. The notation G_K(k) generalizesthe familiar symbol G(k) used in Waring's problem, since wehave G_Q(k) = G(k). By extending the Hardy–Littlewood circle method to numberfields, Siegel [8, 9] initiated a line of research (see [1–4,11]) which generalized existing methods for treating G(k). Thistypically led to upper bounds for G_K(k) of approximate strengthnB(k), where B(k) was the best contemporary upper bound forG(k). For example, Eda [2] gave an extension of Vinogradov'sproof (see [13] or [15]) that G(k)(2+o(1))k log k. The presentpaper will eliminate the need for lengthy generalizations assuch, by introducing a new and considerably shorter approachto the problem. Our main result is the following theorem.     

The BP<N> Cohomology of Elementary Abelian Groups

In this paper we define three elements of a certain generalisedcohomology ring BPm, n* BV_k. Here m, n and k are non-negativeintegers with k+mn+1, there is a fixed prime p not exhibitedin the notation, and V_k is an elementary Abelian p-group ofrank k. We show that these elements are equal; this is striking,because the three definitions are very different. The significanceof our equation is not yet entirely clear, but it makes contactwith other work in the literature in a number of fascinatingways.     

On a question of Sarkozy and Sos for bilinear forms

We prove that, if 2 k₁ k₂, then there is no infinite sequence of positive integers such that the representation functionr(n) = #{(a, a'): n = k₁a + k₂a', a, a' } is constant for nlarge enough. This result completes the previous work of Diracand Moser for the special case k₁ = 1 and answers a questionposed by Sárkozy and Sós.     

Solving Linear Partial Differential Equations by Exponential Splitting

Let A₁, A₂,...,A_N be square matrices which do not commute. Weconsider approximations to the matrix exponential M = exp [t(A₁+ A₂ + ... + A_N)] of the form where each Y_k is a positive multiplying factor, and each E_kis a product of terms having the form exp (tA_n) for some >0 and 1 nN. This form is relevant to semi-discretization methodsfor the solution of linear partial differential equations andit produces systems which are easy to solve. The accuracy andstability of the splitting approximation are studied. It isshown that, even if the number of terms and the value of K arechosen to be large, the highest order of a stable approximationis two. Numerical examples are given.     

Essentially infinite colourings of hypergraphs

We consider edge colourings of the complete r-uniform hypergraphK_n^(r)on n vertices. How many colours may such a colouring haveif we restrict the number of colours locally? The local restrictionis formulated as follows: for a fixed hypergraph H and an integerk we call a colouring (H, k)-local if every copy of H in thecomplete hypergraph K_n^(r) receives at most k different colours. We investigate the threshold for k that guarantees that every(H, k)-local colouring of K_n^(r) must have a globally boundednumber of colours as n , and we establish this threshold exactly.The following phenomenon is also observed: for many H (at leastin the case of graphs), if k is a little over this threshold,the unbounded (H, k)-local colourings exhibit their colourfulnessin a ‘sparse way’; more precisely, a bounded numberof colours are dominant while all other colours are rare. Hencewe study the threshold k₀ for k that guarantees that every (H,k)-local colouring n of K_n^(r) with k k₀ must have a globallybounded number of colours after the deletion of up to n^r edgesfor any fixed > 0 (the bound on the number of colours isallowed to depend on H and only); we think of such colouringsn as ‘essentially finite’. As it turns out, everyessentially infinite colouring is closely related to a non-monochromaticcanonical Ramsey colouring of Erdös and Rado. This secondthreshold is determined up to an additive error of 1 for everyhypergraph H. Our results extend earlier work for graphs byClapsadle and Schelp [‘Local edge colorings that are global’,J. Graph Theory 18 (1994) 389–399] and by the first twoauthors and Schelp [‘Essentially infinite colourings ofgraphs’, J. London Math. Soc. (2) 61 (2000) 658–670].We also consider a related question for colourings of the integersand arithmetic progressions.

---

2000 Mathematics Subject Classification 05D10 (primary), 05C35(secondary). The first author was partially supported by NSF grants CCR 0225610and DMS 0505550. The second author was partially supported byFAPESP and CNPq through a Temático–ProNEx project(Proc. FAPESP 2003/09925–5) and by CNPq (Proc. 306334/2004–6and 479882/2004–5). The third author was partially supportedby NSF grant DMS 0300529. The fourth author was partly supportedby the DFG within the European graduate program ‘Combinatorics,Geometry, and Computation’ (No. GRK 588/2) and by DFGgrant SCHA 1263/1–1. This work was supported in part bya CAPES/DAAD collaboration grant.     

Annular Functions and Gap Series

If f(z) = c_kz^nk, where n_k+1/n_k q > 1, and f(z) is analyticin |z| < 1, the f(z) is an annular function if and only ifsup |c_k| = . This answers a question posed by L. R. Sons andD.M. Campbell simplifies the proofs of many known examples ofannular functions. Present address: Dept. of Mathematical Sciences, McMaster University,Hamilton, Ontario, Canada L8S4K1     

Kazhdan-Lusztig Cells, q-Schur Algebras and James' Conjecture

We consider the Dipper–James q-Schur algebra S_q(n, r)_k,defined over a field k and with parameter q 0. An understandingof the representation theory of this algebra is of considerableinterest in the representation theory of finite groups of Lietype and quantum groups; see, for example, [6] and [11]. Itis known that S_q(n, r)_k is a semisimple algebra if q is nota root of unity. Much more interesting is the case when S_q(n,r)_k is not semisimple. Then we have a corresponding decompositionmatrix which records the multiplicities of the simple modulesin certain ‘standard modules’ (or ‘Weyl modules’).A major unsolved problem is the explicit determination of thesedecomposition matrices.     

Generating tuples of free products

Grushko's theorem [Mat. Sb. 8 (1940) 169–182] says thatany generating tuple (g₁, ..., g_m) of a free product H*K isNielsen-equivalent to a tuple (h₁, ..., h_l, k_l+1, ..., k_m) withh_i H and k_i K for all i. The h_i and k_i are clearly not unique.In this paper we address the extent of this non-uniqueness.     

Conversion of Polynomials between Different Polynomial Bases

The purpose of this paper is to derive a recursive scheme forthe evaluation of the coefficients in the expansion , in terms of the coefficients in the expansion , where both q_k(x) and Q_k(x) are polynomials in xof degree k, and where both q_k(x) and Q_k{x} satisfy recursionformulae of the type satisfied by orthogonal polynomials. Thesets {Q_k(x)} and {q_k(x)} need not be orthogonal polynomials,though they usually are in the applications. An applicationis made to the evaluation of integrals with oscillatory andsingular integrands.     

Supplementary Note on 'Rational Invariants of Certain Orthogonal and Unitary Groups'

Given a field k and a finite group G acting on the rationalfunction field k(X₁, ..., X_n) as a group of k-automorphisms,an important Noether's problem asks whether the invariant subfield [forumal] is purely transcendental over k. 1991 Mathematics Subject Classification12F20, 20G40.     

On an Extension Problem for Polynomials

Consider the following problem: given complex numbers a₁, ...,a_n, find an L function f of minimum norm whose Fourier coefficientsc_k(f) are equal to a_k for k between 0 and n. We show the uniquenessof this function, and we estimate its norm. The operator-valuedcase is also discussed. 2000 Mathematics Subject Classification30E05, 47A20, 47A56, 47A57.