Fast iterative methods for symmetric sinc-Galerkin systems

The symmetric sinc-Galerkin method developed by Lund, when appliedto the second-order self-adjoint boundary value problem, givesrise to a symmetric coefficient matrix has a special structureso that it can be advantageously used in solving the discretesystem. In this paper, we employ the preconditioned conjugategradient method with banded matrices as preconditioners. Weprove that the condition number of the preconditioned matrixis uniformly bounded by a constant independent of the size ofthe matrix. In particular, we show that the solution of an n-by-ndiscrete symmetric sinc-Galerkin system can be obtained in O(nlog n) operations. We also extend our method to the self-adjointelliptic partial differential equation. Numerical results aregiven to illustrate the effectiveness of our fast iterativesolvers.     

Primitive densities of certain sets of primes

While it has already been demonstrated that the set of twin primes (primes that differ by 2) is scarce in the $\text{Σ}\text{1}\text{p}$ (all twin primes) converges whereas $\text{Σ}\text{1}\text{p}$ (all primes) diverges, this paper proves in Theorems 1 and 2 the scarcity of twin primes (and, in general, of primes p which differ by any even integer as well as primes p for which yp + z is prime, y positive, z nonzero, (y, z) = 1) in a novel and natural way — by showing that the natural density of such primes compared to the set of all primes is 0, that is, $\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{π′(n)}\text{π(n)}\text{) = 0}$, where π′(n) is the number of, say, twin primes between 1 and n for any n, and π(n) is the number of all primes between 1 and n. Theorem 3 then establishes that if a set of primes is scarce in the sense that the sum of the reciprocals of such primes converges, they are also scarce in the natural density sense outlined above.     

S-adic L-Functions Attached to the Symmetric Square of a Newform

In order to apply the ideas of Iwasawa theory to the symmetricsquare of a newform, we need to be able to define non-archimedeananalogues of its complex L-series. The interpolated p-adic L-functionis closely connected via a "Main Conjecture" with certain Selmergroups over the cyclotomic Z_p-extension of Q. In the p-ordinarycase these functions are well understood. In this article we extend the interpolation to an arbitraryset S of good primes (not necessarily satisfying ordinarityconditions). The corresponding S-adic functions can be characterisedin terms of certain admissibility criteria. We also allow interpolationat particular primes dividing the level of the newform. One interesting application is to the symmetric square of amodular elliptic curve E defined over Q. Our constructions yieldp-adic L-functions at all primes of stable or semi-stable reduction.If p is ordinary or multiplicative the corresponding analyticfunction is bounded; if p is supersingular our function behaveslike log²(1 + T). 1991 Mathematics Subject Classification: 11F67,11F66, 11F33, 11F30     

Cyclic group actions on polynomial rings

We consider a cyclic group of order pⁿ, acting on a module incharacteristic p, and show how to reduce the calculation ofthe symmetric algebra to that of the exterior algebra.     

Long Snakes in Powers of the Complete Graph with an Odd Number of Vertices

In [5] Abbott and Katchalski ask if there exists a constantc < 0 such that for every d 2 there is a snake (cycle withoutchords) of length at least c3^d in the product of d copies ofthe complete graph K₃. We show that the answer to the abovequestion is positive, and that in general for any odd integern there is a constant c_n such that for every d 2 there is asnake of length at least c_n n^d in the product of d copies ofthe complete graph K_n.     

Sums of primes and squares of primes in short intervals

Let H₂{\mathcal H_2} denote the set of even integers n \not o 1 mod 3{n \not\equiv 1 \pmod 3} . We prove that when H ≥ X ^0.33, almost all integers n ? H₂ ?(X, X + H]{n \in \mathcal H_2 \cap (X, X + H]} can be represented as the sum of a prime and the square of a prime. We also prove a similar result for sums of three squares of primes.     

On Closed Sets with Convex Projections

A shadow of a subset A of Rⁿ is the image of A under a projectiononto a hyperplane. Let C be a closed nonconvex set in Rⁿ suchthat the closures of all its shadows are convex. If, moreover,there are n independent directions such that the closures ofthe shadows of C in those directions are proper subsets of therespective hyperplanes then it is shown that C contains a copyof R^n–2. Also for every closed convex set B ‘minimalimitations’ C of B are constructed, that is, closed subsetsC of B that have the same shadows as B and that are minimalwith respect to dimension.     

Latin Squares and the Hall-Paige Conjecture

The Hall–Paige conjecture deals with conditions underwhich a finite group G will possess a complete mapping, or equivalentlya Latin square based on the Cayley table of G will possess atransversal. Two necessary conditions are known to be: (i) thatthe Sylow 2-subgroups of G are trivial or non-cyclic, and (ii)that there is some ordering of the elements of G which yieldsa trivial product. These two conditions are known to be equivalent,but the first direct, elementary proof that (i) implies (ii)is given here. It is also shown that the Hall–Paige conjecture impliesthe existence of a duplex in every group table, thereby provinga special case of Rodney's conjecture that every Latin squarecontains a duplex. A duplex is a ‘double transversal’,that is, a set of 2n entries in a Latin square of order n suchthat each row, column and symbol is represented exactly twice.2000 Mathematics Subject Classification 05B15, 20D60.     

An Enumerative Geometry for Magic and Magilatin Labellings

A magic labelling of a set system is a labelling of its points by distinct positive integers so that every set of the system has the same sum, the magic sum. Examples are magic squares (the sets are the rows, columns, and diagonals) and semimagic squares (the same, but without the diagonals). A magilatin labelling is like a magic labelling but the values need be distinct only within each set. We show that the number of n × n magic or magilatin labellings is a quasipolynomial function of the magic sum, and also of an upper bound on the entries in the square. Our results differ from previous ones because we require that the entries in the square all be different from each other, and because we derive our results not by ad hoc reasoning but from a general theory of counting lattice points in rational inside-out polytopes. We also generalize from set systems to rational linear forms. Dedicated to the memory of Claudia Zaslavsky, 1917–2006 Received August 10, 2005     

On the Representations of a Number as the Sum of Four Fifth Powers

It is known from Vaughan and Wooley's work on Waring's problemthat every sufficiently large natural number is the sum of atmost 17 fifth powers [13]. It is also known that at least sixfifth powers are required to be able to express every sufficientlylarge natural number as a sum of fifth powers (see, for instance,[5, Theorem 394]). The techniques of [13] allow one to showthat almost all natural numbers are the sum of nine fifth powers.A problem of related interest is to obtain an upper bound forthe number of representations of a number as a sum of a fixednumber of powers. Let R(n) denote the number of representationsof the natural number n as a sum of four fifth powers. In thispaper, we establish a non-trivial upper bound for R(n), whichis expressed in the following theorem.     

INVARIANT FIELDS AND LOCALIZED INVARIANT RINGS OF p-GROUPS

It is well known that for a p-group, the invariant field ispurely transcendental (T. Miyata, Invariants of certain groupsI, Nagoya Math. J. 41 (1971), 69–73). In this note, weshow that a minimal generating set of this field can be chosenas homogeneous invariants from the invariant ring. As a result,we show that the invariant ring localized at one suitable invariantis the localization of a polynomial subring at this same invariant.This second result is a generalization of a recent result ofthe first author for cyclic groups of order p (H. E. A. Campbell,Rings of invariants of representations of C_p in characteristicp, preprint, 2006). As well, we specialize these results tothis latter case.     

The sum of the Mobius function

We derive from the Riemann Hypothesis an estimate for M(x) =_nxµ(n). This is the first improvement of the bound thatTitchmarsh established in 1927.     

An Application of Network Flows to Rearrangement of Series

For each permutation f of the set of positive integers, alltriples s, t, u are determined such that t and u are the lowerand upper limits of the sequence of partial sums of the ‘f-rearrangement’a_f(n) of some real series a_n with sum s.     

Skeletons and Central Sets

Let be an open proper subset of Rⁿ. Its skeleton is the setof points with more than one nearest neighbour in the complementof its central set is the set of centres in maximal open ballsincluded in . Intuitively, if we think of as a land mass inwhich height is proportional to distance from the sea, its skeletonand central set can be thought of as corresponding to ridgesin the mountains of . In this note I discuss the metric andtopological properties of such sets. I show that any skeletonin Rⁿ is F, and has dimension at most n – 1, by any ofthe usual measures of dimension; that if is bounded and connected,its skeleton and central set are connected; and that separatesRⁿ iff its skeleton does iff its central set does. Any centralset in Rⁿ is a G set of topological dimension at most n –1. In the plane, I show that both skeletons and central setsare locally path-connected, and indeed include many paths offinite length. For any , its central set includes its skeleton;I give examples to show that the central set can be significantlylarger than the skeleton. 1991 Mathematics Subject Classification:54F99.     

Least Squares Smoothing of Univariate Data to achieve Piecewise Monotonicity

If measurements of a univariate function include uncorrelatederrors, then it is usual for the first-order divided differencesof the measurements to show far more sign changes than the correspondingdifferences of the underlying function. Therefore we addressthe problem of making the least sum of squares change to thedata so that the piecewise linear interpolant to the smootheddata is composed of at most k monotonic sections, k being aprescribed positive integer. The positions of the joins of thesections are integer variables whose optimal values are determinedautomatically, which is a combinatorial problem that can haveO(n^k) local minima, where n is the number of data. Fortunatelywe find that a dynamic programming procedure can calculate theglobal minimum of the sum of squares in at most O(n² + kn logn) computer operations. Further, the complexity reduces to onlyO(n) when k = 1 or k = 2, this result being well known in themonotonic case (k = 1). Algorithms that achieve these efficienciesare described. They perform well in practice, but a discussionof complexity suggests that there is still room for improvementwhen k 3.     

Infinite Simple (2, 3, n)-Groups and Congruence Hulls in the Modular Group

We prove that if n > 66 and (n, 30) = 1, then there existuncountably many infinite simple (2, 3, n)- groups, that is,groups generated by a pair of elements x, y, say, where theorders of x, y and xy are 2, 3 and n, respectively. This extendsprevious results of Schupp and the authors. These results are used to prove the existence of subgroups ofthe modular group with special arithmetic properties. 1991 MathematicsSubject Classification 20F06.     

Ordinal sums and idempotents of copulas

We prove that the ordinal sum of n-copulas is always an n-copula and show that every copula may be represented as an ordinal sum, once the set of its idempotents is known. In particular, it will be shown that every copula can be expressed as the ordinal sum of copulas having only trivial idempotents. As a by-product, we also characterize all associative copulas whose n-ary forms are n-copulas for all n.     

On RSA moduli with almost half of the bits prescribed

We show that using character sum estimates due to H. Iwaniec leads to an improvement of recent results about the distribution and finding RSA moduli M=pl, where p and l are primes, with prescribed bit patterns. We are now able to specify about n bits instead of about n/2 bits as in the previous work. We also show that the same result of H. Iwaniec can be used to obtain an unconditional version of a combinatorial result of W. de Launey and D. Gordon that was originally derived under the Extended Riemann Hypothesis.     

Minimal vanishing sums of roots of unity with large coefficients

A vanishing sum , where_n is a primitive nth root of unity and the a_is are non-negativeintegers is called minimal if the coefficient vector (a₀, ..., a_n–1) does not properly dominate the coefficient vectorof any other such non-zero sum. We show that for every c thereis a minimal vanishing sum of nth roots of unity with its greatestcoefficient equal to c, where n is of the form 3pq for odd primesp, q. This solves an open problem posed by Lenstra Jr.     

On Hill's Equation with a Singular Complex-Valued Potential

In this paper Hill's equation y' + qy = Ey, where q is a complex-valuedfunction with inverse square singularities, is studied. Resultson the dependence of solutions to initial value problems onthe parameter E and the initial point x₀, on the structure ofthe conditional stability set, and on the asymptotic distributionof (semi-)periodic and Sturm-Liouville eigenvalues are obtained.It is proved that a certain subset of the set of Floquet solutionsis a line bundle on a certain analytic curve in C². We establishnecessary and sufficient conditions for q to be algebro-geometric,that is, to be a stationary solution of some equation in theKorteweg-de Vries (KdV) hierarchy. To do this a distinctionbetween movable and immovable Dirichlet eigenvalues is employed.Finally, an example showing that the finite-band property doesnot imply that q is algebro-geometric is given. This is in contrastto the case where q is real and non-singular. 1991 MathematicsSubject Classification: 34L40, 14H60.