Search

The Chow ring of the moduli space of stable marked curves is generated by Keel's divisor classes. The top graded part of this Chow ring is isomorphic to the integers, generated by the class of a single point. In this paper, we give an equivalent graphical characterization on the monomials in this Chow ring, as well as the characterization on the algebraic reduction on such monomials. Moreover, we provide an algorithm for computing the intersection degree of tuples of Keel's divisor classes — we call it the forest algorithm; the complexity of which is O (n 3) in the worst case, where n refers to the number of marks on the stable curves in the ambient moduli space. Last but not least, we introduce three identities on multinomial coefficients which naturally came into play, showing that they are all equivalent to the correctness of the base case of the forest algorithm. [ABSTRACT FROM AUTHOR]

This paper presents fundamental algorithms for the computational theory of quadratic forms over number fields. In the first part of the paper, we present algorithms for checking if a given non-degenerate quadratic form over a fixed number field is either isotropic (respectively locally isotropic) or hyperbolic (respectively locally hyperbolic). Next we give a method of computing the dimension of an anisotropic part of a quadratic form. The second part of the paper is devoted to algorithms computing two field invariants: the level and the Pythagoras number. Ultimately we present an algorithm verifying whether two number fields have isomorphic Witt rings (i.e. are Witt equivalent). [ABSTRACT FROM AUTHOR]

Mixed trigonometric-polynomials (MTPs) are functions of the form f (x , sin ⁡ x , cos ⁡ x) where f is a trivariate polynomial with rational coefficients, and the argument x ranges over the reals. In this paper, an algorithm "isolating" all the real roots of an MTP is provided and implemented. It automatically divides the real roots into two parts: one consists of finitely many roots in an interval [ μ − , μ + ] while the other consists of countably many roots in R ﹨ [ μ − , μ + ]. For the roots in [ μ − , μ + ] , the algorithm returns isolating intervals and corresponding multiplicities while for those greater than μ + , it returns finitely many mutually disjoint small intervals I i ⊂ [ − π , π ] , integers c i > 0 and multisets of root multiplicity { m j , i } j = 1 c i such that any root > μ + is in the set (∪ i ∪ k ∈ N (I i + 2 k π)) and any interval I i + 2 k π ⊂ (μ + , ∞) contains exactly c i distinct roots with multiplicities m 1 , i ,... , m c i , i , respectively. The efficiency of the algorithm is shown by experiments. The method used to isolate the roots in [ μ − , μ + ] is applicable to any other bounded interval as well. The algorithm takes advantages of the weak Fourier sequence technique and deals with the intervals period-by-period without scaling the coordinate so to keep the length of the sequence short. The new approaches can easily be modified to decide whether there is any root, or whether there are infinitely many roots in unbounded intervals of the form (− ∞ , a) or (a , ∞) with a ∈ Q. [ABSTRACT FROM AUTHOR]

Let M be a given positive integer and r = ( r δ ) δ | M a sequence indexed by the positive divisors δ of M . In this paper we present an algorithm that takes as input a generating function of the form ∑ n = 0 ∞ a r ( n ) q n : = ∏ δ | M ∏ n = 1 ∞ ( 1 − q δ n ) r δ and positive integers m , N and t ∈ { 0 , … , m − 1 } . Given this data we compute a set P m , r ( t ) which contains t and is uniquely defined by m , r and t . Next we decide if there exists a sequence ( s δ ) δ | N indexed by the positive divisors δ of N , and modular functions b 1 , … , b k on Γ 0 ( N ) (where each b j equals the product of finitely many terms from { q δ / 24 ∏ n = 1 ∞ ( 1 − q δ n ) : δ | N } ), such that: q α ∏ δ | N ∏ n = 1 ∞ ( 1 − q δ n ) s δ × ∏ t ′ ∈ P m , r ( t ) ∑ n = 0 ∞ a ( m n + t ′ ) q n = c 1 b 1 + ⋯ + c k b k for some c 1 , ⋯ , c k ∈ Q and α : = ∑ δ | N δ s δ 24 + ∑ t ′ ∈ P m , r ( t ) 24 t ′ + ∑ δ | M δ r δ 24 m . Our algorithm builds on work by Rademacher (1942) , Newman (1959) , and Kolberg (1957) . [ABSTRACT FROM AUTHOR]