Canonical factorization of continuous functions on the -torus

In this article we study the canonical factorization of continuous complex-valued functions on the -dimensional torus belonging to a weighted Wiener algebra with respect to a linear order on the -tuples of integers. It is proved that a function has a canonical factorization in this algebra if and only if it has a logarithm belonging to this algebra. A second characterization is given in terms of winding numbers. Moreover, the maximal ideal spaces of the relevant Banach algebras are identified.

     

On the number of SQSs,latin hypercubes and MDS codes

We establish that the logarithm of the number of latin d‐cubes of order n is and the logarithm of the number of sets of t ( is fixed) orthogonal latin squares of order n is . Similar estimations are obtained for systems of mutually strongly orthogonal latin d‐cubes. As a consequence, we construct a set of Steiner quadruple systems of order n such that the logarithm of its cardinality is as and .     

-saddle method and Beukers' integral

We give good non-quadraticity measures for the values of logarithm at specific rational points by modifying Beukers' double integral. The two-dimensional version of the saddle method, which we call -saddle method, is applied.

     

The low of the iterated logarithm for empirical processes under absolute regularity

The compact law of the iterated logarithm for empirical processes whose underlying sequence satisfies a -mixing condition is considered. In particular, we show a compact law of the iterated logarithm for VC subgraph classes of functions, for classes of functions which satisfy the bracketing condition in Doukhanet al. ⁽⁶⁾ and for some classes of smooth functions.Research partially supported by NSF Grant DMS-93-02583.     

Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem

In this paper, we present several baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. In this version of the discrete log problem, we are required to find a discrete logarithm in a finite group of order approximately , given that the unknown logarithm has a specified number of 1's, say , in its binary representation. Heiman and Odlyzko presented the first algorithms for this problem. Unpublished improvements by Coppersmith include a deterministic algorithm with complexity , and a Las Vegas algorithm with complexity

.

We perform an average-case analysis of Coppersmith's deterministic algorithm. The average-case complexity achieves only a constant factor speed-up over the worst-case. Therefore, we present a generalized version of Coppersmith's algorithm, utilizing a combinatorial set system that we call a splitting system. Using probabilistic methods, we prove a new existence result for these systems that yields a (nonuniform) deterministic algorithm with complexity . We also present some explicit constructions for splitting systems that make use of perfect hash families.

     

Arithmetic on superelliptic curves

This paper is concerned with algorithms for computing in the divisor class group of a nonsingular plane curve of the form which has only one point at infinity. Divisors are represented as ideals, and an ideal reduction algorithm based on lattice reduction is given. We obtain a unique representative for each divisor class and the algorithms for addition and reduction of divisors run in polynomial time. An algorithm is also given for solving the discrete logarithm problem when the curve is defined over a finite field.

     

Moderate deviation principles for trajectories of sums of independent Banach space valued random variables

Let be a sequence of i.i.d. random vectors with values in a separable Banach space. Moderate deviation principles for trajectories of sums of are proved, which generalize related results of Borovkov and Mogulskii (1980) and Deshayes and Picard (1979). As an application, functional laws of the iterated logarithm are given. The paper also contains concluding remarks, with examples, on extending results for partial sums to corresponding ones for trajectory setting.

     

An iterative substructuring method for Maxwell's equations in two dimensions

Iterative substructuring methods, also known as Schur complement methods, form an important family of domain decomposition algorithms. They are preconditioned conjugate gradient methods where solvers on local subregions and a solver on a coarse mesh are used to construct the preconditioner. For conforming finite element approximations of , it is known that the number of conjugate gradient steps required to reduce the residual norm by a fixed factor is independent of the number of substructures, and that it grows only as the logarithm of the dimension of the local problem associated with an individual substructure. In this paper, the same result is established for similar iterative methods for low-order Nédélec finite elements, which approximate in two dimensions. Results of numerical experiments are also provided.

     

The Law of the Iterated Logarithm over a Stationary Gaussian Sequence of Random Vectors

Let {X _j } _{j = 1} be a stationary Gaussian sequence of random vectors with mean zero. We give sufficient conditions for the compact law of the iterate logarithm of

The natural maximal operator on BMO

We introduce a generalization of the Hardy-Littlewood maximal operator, the natural maximal operator , in some sense the maximal operator which most naturally commutes pointwise with the logarithm on . This commutation reveals the behavior of to directly correspond to that of ; the boundedness of is an immediate consequence.

     

Some heuristics and results for small cycles of the discrete logarithm

Brizolis asked the question: does every prime have a pair such that is a fixed point for the discrete logarithm with base ? The first author previously extended this question to ask about not only fixed points but also two-cycles, and gave heuristics (building on work of Zhang, Cobeli, Zaharescu, Campbell, and Pomerance) for estimating the number of such pairs given certain conditions on and . In this paper we extend these heuristics and prove results for some of them, building again on the aforementioned work. We also make some new conjectures and prove some average versions of the results.

     

On random walks for Pollard's rho method

We consider Pollard's rho method for discrete logarithm computation. Usually, in the analysis of its running time the assumption is made that a random walk in the underlying group is simulated. We show that this assumption does not hold for the walk originally suggested by Pollard: its performance is worse than in the random case. We study alternative walks that can be efficiently applied to compute discrete logarithms. We introduce a class of walks that lead to the same performance as expected in the random case. We show that this holds for arbitrarily large prime group orders, thus making Pollard's rho method for prime group orders about faster than before.

     

Matchings and independent sets of a fixed size in regular graphs

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size ℓ in a d-regular graph on N vertices. For bounded away from 0 and 1, the logarithm of the bound we obtain agrees in its leading term with the logarithm of the number of matchings of size ℓ in the graph consisting of disjoint copies of K_d,d. This provides asymptotic evidence for a conjecture of S. Friedland et al. We also obtain an analogous result for independent sets of a fixed size in regular graphs, giving asymptotic evidence for a conjecture of J. Kahn. Our bounds on the number of matchings and independent sets of a fixed size are derived from bounds on the partition function (or generating polynomial) for matchings and independent sets.     

The index calculus method using non-smooth polynomials

We study a generalized version of the index calculus method for the discrete logarithm problem in , when , is a small prime and . The database consists of the logarithms of all irreducible polynomials of degree between given bounds; the original version of the algorithm uses lower bound equal to one. We show theoretically that the algorithm has the same asymptotic running time as the original version. The analysis shows that the best upper limit for the interval coincides with the one for the original version. The lower limit for the interval remains a free variable of the process. We provide experimental results that indicate practical values for that bound. We also give heuristic arguments for the running time of the Waterloo variant and of the Coppersmith method with our generalized database.

     

Recursive method for arma model estimation (I)

In this paper a recursive method is given for estimating model under the natural conditions that the best linear predictor is the best predictor (in the mean square sense). Under these conditions we can prove the estimators ofp ₀ andq ₀ are strongly consistent. The asymptotic normality and the law of iterated logarithm for the estimators of _k 's and _j 's can also be proved.     

Euclidean distortion and the sparsest cut

We prove that every -point metric space of negative type (and, in particular, every -point subset of ) embeds into a Euclidean space with distortion , a result which is tight up to the iterated logarithm factor. As a consequence, we obtain the best known polynomial-time approximation algorithm for the Sparsest Cut problem with general demands. If the demand is supported on a subset of size , we achieve an approximation ratio of .

     

Polynomial Interpolation of the Discrete Logarithm

Recently, Coppersmith and Shparlinski proved several results on the interpolation of the discrete logarithm in the finite prime field by polynomials modulo p and modulo p-1, respectively. In this paper most of these results are extended to arbitrary .     

Linear functionals of eigenvalues of random matrices

Let be a random unitary matrix with distribution given by Haar measure on the unitary group. Using explicit moment calculations, a general criterion is given for linear combinations of traces of powers of to converge to a Gaussian limit as . By Fourier analysis, this result leads to central limit theorems for the measure on the circle that places a unit mass at each of the eigenvalues of . For example, the integral of this measure against a function with suitably decaying Fourier coefficients converges to a Gaussian limit without any normalisation. Known central limit theorems for the number of eigenvalues in a circular arc and the logarithm of the characteristic polynomial of are also derived from the criterion. Similar results are sketched for Haar distributed orthogonal and symplectic matrices.