Common Multiples of Complete Graphs

A graph H is said to divide a graph G if there exists a setS of subgraphs of G, all isomorphic to H, such that the edgeset of G is partitioned by the edge sets of the subgraphs inS. Thus, a graph G is a common multiple of two graphs if eachof the two graphs divides G. This paper considers common multiples of a complete graph oforder m and a complete graph of order n. The complete graphof order n is denoted K_n. In particular, for all positive integersn, the set of integers q for which there exists a common multipleof K₃ and K_n having precisely q edges is determined. It is shown that there exists a common multiple of K₃ and K_nhaving q edges if and only if q 0 (mod 3), q 0 (mod n2) and (1) q 3 n2 when n 5 (mod 6); (2) q (n + 1) n2 when n is even; (3) q {36, 42, 48} when n = 4. The proof of this result uses a variety of techniques includingthe use of Johnson graphs, Skolem and Langford sequences, andequitable partial Steiner triple systems. 2000 MathematicalSubject Classification: 05C70, 05B30, 05B07.     

Fast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials

Consider the (n + 1) ? (n + 1) Vandermonde-like matrix P=[p_i-1(_j-1)],where the polynomials p_o(x), ..., p_n(x) satisfy a three-termrecurrence relation. We develop algorithms for solving the primaland dual systems, Px = b and P^Ta = f respectively, in O(n²)arithmetic operations and O(n) elements of storage. These algorithmsgeneralize those of Bj?rck & Pereyra which apply to themonomial case p_i(x). When the p_i(x) are the Chebyshev polynomials,the algorithms are shown to be numerically unstable. However,it is found empirically that the addition of just one step ofiterative refinement is, in single precision, enough to makethe algorithms numerically stable.     

Irregular,extremal perfect systems of difference sets II

An (m, n; u, v; c)-system is a collection of components,m of valencyu – 1 andn of valencyv – 1, whose difference sets form a perfect system with thresholdc. A necessary condition for the existence of an (m, n; u, v; c)-system foru = 3 or 4 is thatm 2c – 1; and there are (2c – 1,n; 3, 6;c)-systems for all sufficiently largec at least whenn = 1 or 2. It is shown here that if there is a (2c – 1,n; u, 6;c)-system thenn = 0 whenu = 4 andn 2c – 1 whenu = 3. Moreover, if there is a (2c – 1,n; 3, 6;c)-system with a certain splitting property thenn c – 1, this last result being of possible interest in connection with the multiplication theorem for perfect systems.     

Products of Consecutive Integers

In this paper, a number of results are deduced on the arithmeticstructure of products of integers in short intervals. By wayof an example, work of Saradha and Hanrot, and of Saradha andShorey, is completed by the provision of an answer to the questionof when the product of k out of k + 1 consecutive positive integerscan be an ‘almost’ perfect power. The main new ingredientin these proofs is what might be termed a practical method forresolving high-degree binomial Thue equations of the form axⁿ–byⁿ= ±1, based upon results from the theory of Galois representationsand modular forms. 2000 Mathematics Subject Classification 11D41,11D61.     

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     

Intersections of Symbolic Powers of Prime Ideals

Let (R,m) be a local ring with prime ideals p and q such that. If R is regular and containsa field, and dim(R/p)+dim(R/q)=dim(R), then it is proved thatp^(m) q⁽ⁿ⁾ m^m+n for all positive integers m and n. This isproved using a generalization of Serre's Intersection Theoremwhich is applied to a hypersurface R/fR. The generalizationgives conditions that guarantee that Serre's bound on the intersectiondimension (R/p)+(R/q)dim(R) holds when R is nonregular.     

Trialities and 1-Systems of Q <Superscript>+</Superscript>(7,q)

The image of a 1-system of Q7q under a triality of the D₄-geometry, attached to Q7q, will be investigated. Attention will mainly be paid to the case of a locally hermitian, semiclassical 1-system of a Q6 q, embedded in Q7q. It is found that its image under a triality is always locally hermitian and semiclassical as well. Moreover, it is a proper 1-system of Q7q whenever the original 1-system of Q6q is not a spread of some generalized hexagon Hq on Q6,q. Finally, some results concerning isomorphisms will be obtained.AMS classification : 51A50, 51E12, 51E30communicated by: S. Ball     

A Remark About the Lie Algebra of Infinitesimal Conformal Transformations of the Euclidean Space

Infinitesimal conformal transformations of Rⁿ are always polynomialand finitely generated when n > 2. Here we prove that theLie algebra of infinitesimal conformal polynomial transformationsover Rⁿ, n 2, is maximal in the Lie algebra of polynomial vectorfields. When n is greater than 2 and p, q are such that p +q = n, this implies the maximality of an embedding of so(p +1, q + 1, R) into polynomial vector fields that was revisitedin recent works about equivariant quantizations. It also refinesa similar but weaker theorem by V. I. Ogievetsky. 1991 MathematicsSubject Classification 17B66, 53A30.     

Minimal Submanifolds in a Sphere II

We use the method of H. Gauchman [2] to show that if the sectionalcurvature of a compact minimal n-dimensional submanifold ina unit sphere is everywhere bigger than n/2(n+1) then it mustbe totally geodesic. We also discuss some related results andconjectures.     

A Note on the WKB Method for Difference Equations

We consider the asymptotic solution of the second-order differenceequation y_n + 1 –2y_n + y_n–1 + Q_ny_n = 0, where Q_n= N^–Q(n/N), 0 < < 2, Q(s) being a differentiablefunction of s, and N a large parameter such that Q(n/N) variesby order unity as n varies by order N. A discrete WKB methodis proposed, the form of the asymptotic expansion being similarto that used in the conventional WKB method. A particular Q(s)is studied, for which results of the discrete WKB method arein agreement with the results from the approach due to Bremmer(1951).     

Polynomial systems supported on circuits and dessins d'enfants

We study polynomial systems in which equations have as commonsupport a set of n + 2 points in ⁿ called a circuit. We finda bound on the number of real solutions to such systems whichdepends on n, the dimension of the affine span of the minimalaffinely dependent subset of , and the rank modulo 2 of . Weprove that this bound is sharp by drawing the so-called dessinsd’enfants on the Riemann sphere. We also obtain that themaximal number of solutions with positive coordinates to systemssupported on circuits in ⁿ is n + 1, which is very small comparedto the bound given by the Khovanskii fewnomial theorem.     

Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes

We prove an asymptotic estimate for the number of m x n non-negativeinteger matrices (contingency tables) with prescribed row andcolumn sums and, more generally, for the number of integer-feasibleflows in a network. Similarly, we estimate the volume of thepolytope of m x n non-negative real matrices with prescribedrow and column sums. Our estimates are solutions of convex optimizationproblems, and hence can be computed efficiently. As a corollary,we show that if row sums R = (r₁, ..., r_m) and column sums C= (c₁, ..., c_n) with r₁ + + r_m = c₁ + + c_n = Nare sufficientlyfar from constant vectors, then, asymptotically, in the uniformprobability space of the m x nnon-negative integer matriceswith the total sum N of entries, the event consisting of thematrices with row sums R and the event consisting of the matriceswith column sums C are positively correlated.     

Vector Valued Inequalities for Hankel Transforms

The disc multiplier may be seen as a vector valued operatorwhen we consider its projections in terms of the spherical harmonics.We prove the boundedness of this operator, which in this formrepresents a vector valued Hankel Transform, on the spaces (r^n–1 dr) when 2n/(n + 1) <p, q < 2n/(n – 1).     

Turning Euler's Factoring Method into a Factoring Algorithm

An algorithm is presented which, given a positive integer n,will either factor n or prove it to be prime. The algorithmtakes O(n^1/3+) steps.     

Long-Time Behavior of Solutions of the Fast Diffusion Equations with Critical Absorption Terms

This paper is devoted to the long-time behavior of solutionsto the Cauchy problem of the porous medium equation u_t = (u^m)– u^p in Rⁿ x (0,) with (1 – 2/n)₊ < m < 1and the critical exponent p = m + 2/n. For the strictly positiveinitial data u(x,0) = O(1 + |x|)^–k with n + mn(2 –n + nm)/(2[2 – m + mn(1 – m)]) k < 2/(1 –m), we prove that the solution of the above Cauchy problem convergesto a fundamental solution of u_t = (u^m) with an additional logarithmicanomalous decay exponent in time as t .     

Negative Latin Square type Partial Difference Sets in Nonelementary Abelian 2-Groups

Combining results on quadrics in projective geometries withan algebraic interplay between finite fields and Galois rings,the first known family of partial difference sets with negativeLatin square type parameters is constructed in nonelementaryabelian groups, the groups x for all k when is odd andfor all k < when is even. Similarly, partial differencesets with Latin square type parameters are constructed in thesame groups for all k when is even and for all k< when is odd. These constructions provide the first example wherethe non-homomorphic bijection approach outlined by Hagita andSchmidt can produce difference sets in groups that previouslyhad no known constructions. Computer computations indicate thatthe strongly regular graphs associated to the partial differencesets are not isomorphic to the known graphs, and it is conjecturedthat the family of strongly regular graphs will be new.     

Sums of Connectivity Functions on Rn

A function f: Rⁿ R is a connectivity function if the graphof its restriction f|C to any connected C Rⁿ is connected inRⁿ x R. The main goal of this paper is to prove that every functionf: Rⁿ R is a sum of n + 1 connectivity functions (Corollary2.2). We will also show that if n > 1, then every functiong: Rⁿ R which is a sum of n connectivity functions is continuouson some perfect set (see Theorem 2.5) which implies that thenumber n + 1 in our theorem is best possible (Corollary 2.6). Toprove the above results, we establish and then apply the followingtheorems which are of interest on their own. For every dense G-subset G of Rⁿ there are homeomorphisms h₁,..., h_n of Rⁿ such that Rⁿ = G h₁(G) ... h_n(G) (Proposition2.4). For every n > 1 and any connectivity function f: Rⁿ R, ifx Rⁿ and > 0 then there exists an open set U Rⁿ such thatx U Bⁿ(x, ), f|bd(U) is continuous, and |(x) – f(y)|< for every y bd(U) (Proposition 2.7). 1991 MathematicsSubject Classification: 26B40, 54C30, 54F45.     

Conditions for the Solvability of Systems of Two and Three Additive Forms Over p-Adic Fields

This paper is concerned with non-trivial solvability in p-adicintegers of systems of two and three additive forms. Assumingthat the congruence equation ax^k + by^k + cz^k d (modp) has asolution with xyz 0(modp) we have proved that any system oftwo additive forms of odd degree k with at least 6k + 1 variables,and any system of three additive forms of odd degree k withat least 14k + 1 variables always has non-trivial p-adic solutions,provided p does not divide k. The assumption of the solubilityof the congruence equation above is guaranteed for example ifp > k⁴. In the particular case of degree k = 5 we have proved the followingresults. Any system of two additive forms with at least n variablesalways has non-trivial p-adic solutions provided n 31 and p> 101 or n 36 and p > 11. Furthermore any system of threeadditive forms with at least n variables always has non-trivialp-adic solutions provided n 61 and p > 101 or n 71 andp > 11. 2000 Mathematics Subject Classification 11D72, 11D79.     

Exceptional collections for Grassmannians of isotropic lines

We construct a full exceptional collection of vector bundlesin the derived categories of coherent sheaves on the Grassmannianof isotropic two-dimensional subspaces in a symplectic vectorspace of dimension 2n and in an orthogonal vector space of dimension2n + 1 for all n.     

The number of connected sparsely edged graphs. IV large nonseparable graphs

The number of nonseparable graphs on n labeled points and q lines is u(n, q). In the second paper of this series an exact formula for u(n, n + k) was found for general n and successive (small) k. The method would give an asymptotic approximation for fixed k as n → ∞. Here an asymptotic approximation to u(n, n + k) is found when k = O(n^1/2) and an approximation to logu(n, n + k) when k < (1 - ?)(1/3 n)1/2. The problem of finding an approximation to u(n, q) when (q - n)/n1/2 → + → and q/n - 1/2 logn - 1/2 log logn → - ∞ is open.