Let @math denote the number of monic irreducible polynomials in @math of degree @math . We show that for a fixed degree @math , the sequence @math converges @math -adically to an explicitly determined rational function @math . Furthermore we show that the limit @math is related to the classic necklace polynomial @math by an involutive functional equation, leading to a phenomenon we call liminal reciprocity. The limiting first moments of factorization statistics for squarefree polynomials are expressed in terms of a family of symmetric group representations as a consequence of liminal reciprocity
The results in @cite_11 are expressed in terms of expected values of factorization statistics. In this paper we focus on first moments as they lead to a cleaner statement for Theorem . The only difference between expected values and first moments of factorization statistics is whether or not one divides by the total mass'' of the space of polynomials considered. This difference is simply a factor of @math for general univariate polynomials, but is more subtle for squarefree polynomials and multivariate polynomials as it affects the family of characters determining the coefficients. The equivalence between Theorem (2) and [Thm. 2.5] Hyde follows from [Prop. 4.2] Hyde Lagarias . Alternatively, Theorem (2) appears as stated in [Prop. 4.1] CEF .
@cite_11
2040922227 2067161429 2000931246 2168222442
Three theorems are presented that establish polynomial straight-line complexity for certain operations on polynomials given by straight-line programs of unbounded input degree. The first theorem shows how to compute a higher order partial derivative in a single variable. The other two theorems impose the degree of the output polynomial as a parameter of the length of the output program. First it is shown that if a straight-line program computes an arbitrary power of a multivariate polynomial, that polynomial also admits a polynomial bounded straight-line computation. Second, any factor of a multivariate polynomial given by a division-free straight-line program with relatively prime co-factor also admits a straight-line computation of length polynomial in the input length and the degree of the factor. This result is based on a new Hensel lifting process, one where only one factor image is lifted back to the original factor. As an application we get that the greatest common divisor of polynomials given by a division-free straight-line program has polynomial straight-line complexity in terms of the input length and its own degree. Abstract We study the problem of reconstructing a multivariate trigonometric polynomial having only few non-zero coefficients from few random samples. Inspired by recent work of Candes, Romberg and Tao we propose to recover the polynomial by Basis Pursuit, i.e., by l 1 -minimization. In contrast to their work, where the sampling points are restricted to a grid, we model the random sampling points by a continuous uniform distribution on the cube, i.e., we allow them to have arbitrary position. Numerical experiments show that with high probability the trigonometric polynomial can be recovered exactly provided the number N of samples is high enough compared to the “sparsity”—the number of non-vanishing coefficients. However, N can be chosen small compared to the assumed maximal degree of the trigonometric polynomial. We present two theorems that explain this observation. One of them provides the analogue of the result of Candes, Romberg and Tao. The other one is a result toward an average case analysis and, unexpectedly connects to an interesting combinatorial problem concerning set partitions, which seemingly has not yet been considered before. Although our proofs follow ideas of they are simpler. Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We derive an expected complexity bound of [email protected]?"B(d^6+d^[email protected]^2), where d is the polynomial degree and @t bounds the coefficient bit size, using a standard bound on the expected bit size of the integers in the continued fraction expansion, thus matching the current worst-case complexity bound for real root isolation by exact methods (Sturm, Descartes and Bernstein subdivision). Moreover, using a homothetic transformation we improve the expected complexity bound to [email protected]?"B(d^[email protected]). We compute the multiplicities within the same complexity and extend the algorithm to non-square-free polynomials. Finally, we present an open-source C++ implementation in the algebraic library synaps, and illustrate its completeness and efficiency as compared to some other available software. For this we use polynomials with coefficient bit size up to 8000 bits and degree up to 1000.