Algorithm for a sum of reciprocals

An algorithm is described for the approximate calculation of a collection of sums of the form _k= _j–1 ⁿ c_j/(_j+_k), 1kn, where 0<_j. The working time of the algorithm is 0(n(t+ log n)(t+log n)) if _k calculated to within 2^–t; here the function (l) denotes the time of multiplication of twoZ-bit numbers.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 3–6, 1984.In conclusion, the author expresses thanks to A. O. Slisenko and Yu. A. Kuznetsov, who drew the attention of the author to the problem considered.     

Elliptic genera,involutions, and homogeneous spin manifolds

We study the normalized elliptic genera (X)=(X)/ ^k/2 for 4k-dimensional homogeneous spin manifolds X and show that they are constant as modular functions. The basic tool is a reduction formula relating (X) to that of the self-intersection of the fixed point set of an involution on X. When (X) is a constant it equals the signature of X. We derive a general formula for sign(G/H), GH compact Lie groups, and determine its value in some cases by making use of the theory of involutions in compact Lie groups.Dedicated to Jacques Tits on the occasion of his sixtieth birthday     

On sums of two coprimek-th powers

Under the assumption of the Riemann Hypothesis, an asymptotic formula with a sharp error term is established for _{nx k} (n), where _k (n) denotes the number of ways to writen as a sum of twok-th powers of coprime positive integers (k3).     

A Local Approach to 1-Homogeneous Graphs

Let bea distance-regular graph with diameter d. For vertices x and y of at distancei, 1 i d, we define the setsC _i(x,y) = i–1(x) (y), A _i (x,y) = _i (x) (y) and B _i (x,y) = _i+1(x) (y).Then we say has the CAB_j property,if the partition CAB _i (x,y) = {C _i (x,y),A _i (x,y),B _i (x,y)}of the local graph of y is equitable for each pairof vertices x and y of at distance i j. We show that in with the CAB_j property then the parameters ofthe equitable partitions CAB i(x,y) do not dependon the choice of vertices x and y atdistance i for all i j. The graph has the CAB property if it has the CAB _d property. We show the equivalence of the CAB property and the1-homogeneous property in a distance-regular graph with a ₁ 0. Finally, we classify the 1-homogeneous Terwilligergraphs with c ₂ 2.     

Applications of matrix functions

A, ()=0, c(z)- T - TY=AY. A y(t)=y(, t) Ty=y Y(t). - c(T)y=0.     

On a Turán type problem of Erdös

Let L ^k be the graph formed by the lowest three levels of the Boolean lattice B _k , i.e.,V(L ^k )={0, 1,...,k, 12, 13,..., (k–1)k} and 0is connected toi for all 1ik, andij is connected toi andj (1i<jk).It is proved that if a graph G overn vertices has at leastk ^3/2 n ^3/2 edges, then it contains a copy of L ^k .Research supported in part by the Hungarian National Science Foundation under Grant No. 1812     

Estimates of the asphericity of sections of convex bodies

We define the function (n, k) to be the infimum of all such that any bounded centrally symmetric convex body inR ⁿ possesses an -asphericalk-dimensional central section. It is proved that (3, 2)=2–1 and (n, n-1)n-1-1. Several related functions are defined and their values on the pairs (n, n-1) are estimated.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 76–79.     

Randomly Weighted Sums of Subexponential Random Variables with Application to Ruin Theory

Let {X _k , 1 k n} be n independent and real-valued random variables with common subexponential distribution function, and let {k, 1 k n} be other n random variables independent of {X _k , 1 k n} and satisfying a _k b for some 0 < a b < for all 1 k n. This paper proves that the asymptotic relations P (max_{1 m n k=1} ^m _k X _k > x) P (sum _k=1 ⁿ _k X _k > x) sum _k=1 ⁿ P ( _k X _k > x) hold as x . In doing so, no any assumption is made on the dependence structure of the sequence { _k , 1 k n}. An application to ruin theory is proposed.     

Algebraic polynomial bases of space LP

Let (_n) be a system, close to the orthonormal complete system (x _n). An estimate is obtained for the deviation of the system {f_n}, obtained from {_n} by Schmidt's method, from the system {x_n}. This estimate is used to show that, in any L_P(–1,1), withp (1,4/3] [4,), and for any >e¦4 = i,13..., there exists an orthogonal algebraic system (P _n (x)) _n=0 , forming a basis in L_P and such that _n = degP _n (x) n for n>n_o(p,).Translated from Matematicheskie Zametki, Vol. 23, No. 2, pp. 223–230, February, 1978.     

On the boundedness of Weyl sums

Leta be irrational and letf:[0,1] be Riemann-integrable with integral zero. Letf _n (x) denote the Weyl sumf _n (x):= _k=0 ^n–1 f({x k>}),x/[0,1[,n. We prove criteria for the boundedness of the sequence (f _n ) _n1 and discuss the relation of this question to irregularities of the distribution of sequences.     

Inequalities involving the inradii of simplexes

An inequality involving the inradii ofk-simplexes andl-simplexes (3 n) whose vertices lie in a finite set of points inE ⁿ has been proved in this paper.     

Lawless order

R. Baer asked whether the group operation of every (totally) ordered group can be redefined, keeping the same ordered set, so that the resulting structure is an Abelian ordered group. The answer is no. We construct an ordered set (G, ) which carries an ordered group (G, , ) but which islawless in the following sense. If (G, *, ) is an ordered group on the same carrier (G, ), then the group (G, *) satisfies no nontrivial equational law.Research partially supported by NSERC of Canada Grants #A4044 and A3040.Research partially supported by NSERC of Canada Grant #U0075.Research partially supported by a grant from the BSF.     

Estimation of distribution density

The article investigates the asymptotic properties of the estimators of the density P(x) derived using a sample X₁,...,X _n when the distance of the estimator from p(x) is measured in the metricL _p,2p2.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Institute im. V. A. Steklova AN SSSR, Vol. 98, pp. 61–85, 1980.     

Characterization of certain accessible dendrites

In [2] we calculated the number, up to homeomorphism, of saws in class D _n,m, where n2 and 0mn–2. In this paper we characterize accessible simple B-finite dendrites of finite order, and accessible saws. We also calculate the number, up to homeomorphism, of accessible saws in the family D _n.     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

Random k-Sat: A Tight Threshold For Moderately Growing k

We consider a random instance I of k-SAT with n variables and m clauses, where k=k(n) satisfies k—log₂ n. Let m ₀=2 ^k nln2 and let =(n)>0 be such that n. We prove that

LAN of extreme order statistics

Consider an iid sampleZ ₁,...,Z _n with common distribution functionF on the real line, whose upper tail belongs to a parametric family {F : }. We establish local asymptotic normality (LAN) of the loglikelihood process pertaining to the vector(Z _n–i+1n ) _i=1 ^k of the upperk=k(n) _n order statistics in the sample, if the family {F :} is in a neighborhood of the family of generalized Pareto distributions. It turns out that, except in one particular location case, thekth-largest order statisticZ _n–k+1n is the central sequence generating LAN. This implies thatZ _n–k+1n is asymptotically sufficient and that asymptotically optimal tests for the underlying parameter can be based on the single order statisticZ _n–k+1n . The rate at whichZ _n–k+1n becomes asymptotically sufficient is however quite poor.     

A superfast algorithm for multi-dimensional Padé systems

For a vector ofk+1 matrix power series, a superfast algorithm is given for the computation of multi-dimensional Padé systems. The algorithm provides a method for obtaining matrix Padé, matrix Hermite Padé and matrix simultaneous Padé approximants. When the matrix power series is normal or perfect, the algorithm is shown to calculate multi-dimensional matrix Padé systems of type (n ₀,...,n _k ) inO(n · log²n) block-matrix operations, where n=n ₀+...+n _k . Whenk=1 and the power series is scalar, this is the same complexity as that of other superfast algorithms for computing Padé systems. Whenk>1, the fastest methods presently compute these matrix Padé approximants with a complexity ofO(n²). The algorithm succeeds also in the non-normal and non-perfect case, but with a possibility of an increase in the cost complexity.Supported in part by NSERC grant No. A8035.Partially supported by NSERC operating grant No. 6194.     

On the distribution of comparisons in sorting algorithms

We considered the following natural conjecture: For every sorting algorithm every key will be involved in(logn) comparisons for some input. We show that this is true for most of the keys and prove matching upper and lower bounds. Every sorting algorithm for some input will involven–n /2+1 keys in at leastlog₂ n comparisons,>0. Further, there exists a sorting algorithm that will for every input involve at mostn–n ^/c keys in greater thanlog₂ n comparisons, wherec is a constant and>0. The conjecture is shown to hold for natural algorithms from the literature.     

Über den algorithmischen Nachweis von Ungleichungen I

We shall develop a method to prove inequalities in a unified manner. The idea is as follows: It is quite often possible to find a continuous functional : ⁿ , such that the left- and the right-hand side of a given inequality can be written in the form (u)(v) for suitable points,v=v(u). If one now constructs a map ^{n n} , which is functional increasing (i.e. for each x ⁿ (which is not a fixed point of ) the inequality (x)<((x)) should hold) one specially gets the chain (u)( u))( ²(u))... ⁿ (u)). Under quite general conditions one finds that the sequence { ⁿ (u)} _n converges tov=v(u). As a consequence one obtains the inequality (u)(v).