The Fast Numerical Solution of Very Large Elliptic Difference Schemes

Let L_kv_k = g_k be a system of difference equations discretizingan elliptic boundary value problem. Assume the system to be"very large", that means that the number of unknowns exceedsthe capacity of storage. We present a method for solving theproblem with much less storage requirement. For two-dimensionalproblems the size of the needed storage decreases from O(h^–2)to (or even O(h^–5/4)). The computational work increasesonly by a factor about six. The technique can be generalizedto nonlinear problems. The algorithm is also useful for computerswith a small number of parallel processors.     

High Order Numerical Differentiation Type Formulas with an Off-step Point for Stiff Ordinary Differential Equations

Linear k-step implicit numerical differentiation (N.D.) formulaswhich are of order k are stable for k 6 (Henrici, 1962). Inthis paper N.D. type formulas are derived by introducing thevalue of the derivative at an off-step point. It is found thatthe resulting k-step implicit formulas have order k+2 and arestable for k 16. Stiff stability is achieved for k 7, by introducinga suitable corrector at the off-step point. The necessary predictorsare also derived.     

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.     

Cerf Theory for Graphs

We develop a deformation theory for k-parameter families ofpointed marked graphs with fixed fundamental group F_n. Applicationsinclude a simple geometric proof of stability of the rationalhomology of Aut(F_n), computations of the rational homology insmall dimensions, proofs that various natural complexes of freefactorizations of F_n are highly connected, and an improvementon the stability range for the integral homology of Aut(F_n).     

On Automorphisms of Polynomial Rings

Implicit in the work of Lane [1] is the result that if k isan algebraically closed field then every k-automorphism leavesa non-zero proper ideal of k[x, y] invariant. The purpose ofthis note is to show that this result does not hold for k[x,y, z].     

On the Small Squaring and Commutativity

Let G be a group and let k > 2 be an integer, such that (k²– 3)(k – 1) < |G|/15 if G is finite. Supposethat the condition |A²| k(k + 1)/2 + (k – 3)/2 is satisfiedby every it-element subset A G. Then G is abelian. The proofuses the structure of quasi-invariant sets.     

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.     

Permutative k-exponential epigroups

We prove that any permutative k-exponential epigroup is a normal band of unipotent epigroups. Moreover, we describe the least regular congruence on such semigroups. Finally, we give an example of a permutative epigroup which is not a band of unipotent epigroups.     

Anneaux de definition des dg-algebres propres et lisses

RÈSUMÈ: Soit k = colim_i k_i une colimite filtrante d’anneaux commutatifs.On montre que la théorie homotopique des dg-algèbrespropres et lisses sur k est la colimite des théorieshomotopiques des dg-algèbres propres et lisses sur lesk_i. Nous en déduisons en particulier que toute dg-algèbrepropre et lisse est définissable sur une -algèbrecommutative de type fini. Let k = colim_i k_i be a filtered colimit of commutative rings.We show that the homotopy theory of smooth and proper dg-algebrasover k is the colimit of the homotopy theories of smooth andproper dg-algebras over the k_i. We deduce, in particular, thatevery smooth and proper dg-algebra can be defined over a commutative-algebra of finite type.     

On a Question of Herman, Baker and Rippon Concerning Siegel Disks

Consider the family of exponential maps E_k(z) = exp(z)+k. Thispaper shows that any unbounded Siegel disk U of E_k containsthe singular value k on its boundary. By a result of Herman,this implies that k U if the rotation number is diophantine.2000 Mathematics Subject Classification 37F10, 30D05.     

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.     

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.     

On the anticipation phenomenon for implicit linear discrete-time systems on finite intervals

Implicit linear discrete-time systems are systems describedby the difference equation Ex_k+1 = Fx_k + Gu_k. It is well knownthat, for such systems, the current value of a trajectory (x_k)may be dependent on future values of an input sequence (u_k).This property, which is called the anticipation phenomenon,has previously been studied by the authors for k running throughthe whole set of nonnegative integers. In this paper, we studythis phenomenon for systems defined on finite intervals. Inparticular, we give a quantitative characterization of anticipationphenomenon by introducing the so-called anticipation index ofa system.     

The Strength of a Fabric

Consider fabrics in which every warp (and weft) strand passesover and under at least k weft (warp) strands. There is a 4kby 4k fabric of this kind that does not hang together. We provethat any n by n fabric of this kind, where n < 4k, does hangtogether. Moreover, we introduce a measure of how well a fabrichangs together, by defining the strength of a fabric, and twotheorems are proved that extend the preceding results.     

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.     

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.     

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

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.     

Economical Covers with Geometric Applications

A cover of a hypergraph is a collection of edges whose unioncontains all vertices. Let H = (V, E) be a k-uniform, D-regularhypergraph on n vertices, in which no two vertices are containedin more than o(D/e^2k log D) edges as D tends to infinity. Ourresults include the fact that if k = o(log D), then there isa cover of (1 + o(1))n/k edges, extending the known result thatthis holds for fixed k. On the other hand, if k 4 log D thenthere are k-uniform, D-regular hypergraphs on n vertices inwhich no two vertices are contained in more than one edge, andyet the smallest cover has at least (nk) log (k log D)) edges.Several extensions and variants are also obtained, as well asthe following geometric application. The minimum number of linesrequired to separate n random points in the unit square is,almost surely, (n^2/3 / (log n)^1/3). 2000 Mathematical SubjectClassification: 05C65, 05D15, 60D05.     

On Cohen-Macaulay Posets, Koszul Algebras and Certain Modules Associated to Schubert Varieties

In the first part of this paper, some cohomological propertiesof the incidence algebra A_k(X) of a finite poset X over a fieldk are studied. In particular, it is shown that A_k(X) is Koszulif and only if every open interval of X is Cohen-Macaulay overk. In the second part, certain categories of representationsof a Borel subgroup B of a semisimple connected algebraic groupG are studied. It is shown that these categories have the samecohomological properties as certain Cohen-Macaulay posets relatedto the Weyl group of G, and the higher Ext-groups between certainB-modules are then computed, using results from the first part.