Worst-case complexity bounds for algorithms in the theory of integral quadratic forms

The problem of factoring an integer and many other number-theoretic problems can be formulated in terms of binary quadratic Diophantine equations. This class of equations is also significant in complexity theory, subclasses of it having provided most of the natural examples of problems apparently intermediate in difficulty between P and NP-complete problems, as well as NP-complete problems [2, 3, 22, 26]. The theory of integral quadratic forms developed by Gauss gives some of the deepest known insights into the structure of classes of binary quadratic Diophantine equations. This paper establishes explicit polynomial worst-case running time bounds for algorithms to solve certain of the problems in this theory. These include algorithms to do the following: (1) reduce a given integral binary quadratic form; (2) quasi-reduce a given integral ternary quadratic form; (3) produce a form composed of two given integral binary quadratic forms; (4) calculate genus characters of a given integral binary quadratic form, when a complete prime factorization of its determinant D is given as input; (5) produce a form that is the square root under composition of a given form (when it exists), when a complete factorization of D and a quadratic nonresidue for each prime dividing D is given as input.     

Arithmetic expressions of Selberg's zeta functions for congruence subgroups

In [P. Sarnak, Class numbers of indefinite binary quadratic forms, J. Number Theory 15 (1982) 229-247], it was proved that the Selberg zeta function for SL₂(Z) is expressed in terms of the fundamental units and the class numbers of the primitive indefinite binary quadratic forms. The aim of this paper is to obtain similar arithmetic expressions of the logarithmic derivatives of the Selberg zeta functions for congruence subgroups of SL₂(Z). As applications, we study the Brun-Titchmarsh type prime geodesic theorem and the asymptotic formula of the sum of the class number.     

Spinor equivalence of quadratic forms

Let f be an integral quadratic form in three or more variables and g any form in the genus of f. There exist an effectively determinable prime p and a form g′, belonging to the proper spinor genus of g, such that g′ is a p-neighbor of f in the graph of f. Using this, an alternative decision procedure for the spinor equivalence of quadratic forms is given.     

On generic and maximal k-ranks of binary forms

In what follows, we pose two general conjectures about decompositions of homogeneous polynomials as sums of powers. The first one (suggested by G. Ottaviani) deals with the generic k-rank of complex-valued forms of any degree divisible by k in any number of variables. The second one (by the fourth author) deals with the maximal k-rank of binary forms. We settle the first conjecture in the cases of two variables and the second in the first non-trivial case of the 3-rd powers of quadratic binary forms.     

Phantom holomorphic projections arising from Sturm’s formula

A (positive definite integral) quadratic form is called diagonally 2-universal if it represents all positive definite integral binary diagonal quadratic forms. In this article, we show that, up to equivalence, there are exactly 18 (positive definite integral) quinary diagonal quadratic forms that are diagonally 2-universal. Furthermore, we provide a “diagonally 2-universal criterion” for diagonal quadratic forms, which is similar to “15-Theorem” proved by Conway and Schneeberger.     

Represented value sets for integral binary quadratic forms and lattices

A characterization is given for the integral binary quadratic forms for which the set of represented values is closed under products. It is also proved that for an integral binary quadratic lattice over a Dedekind domain, the product of three values represented by the form is again a value represented by the form. This generalizes the trigroup property observed by V. Arnold in the case of integral binary quadratic forms.

     

Spinor genera of binary quadratic forms

Spinor genera are defined for binary quadratic forms with integer coefficients in such a way that the theory fits in with the Gaussian theory of genera. It is shown that spinor generic characters exist which distinguish the various spinor genera in the principal genus, and how they can be determined. It is known that each ambiguous class contains exactly two forms of the type [a, 0, c] or [a, a, c], each with its associate [c, 0, a], [4c ? a, 4c ? a, c]. Since the principal class contains such a form with a = 1, it is an interesting question whether one can predict the second form (not counting associates). This question includes that of Dirichlet about the representability of ?1 by the principal class. Methods are given for evaluating the spinor-generic characters of ambiguous forms in the principal genus for variable discriminants d, and are carried through in the eleven cases where d is fundamental, there are two or four genera, and two spinor genera in the principal genus. The problem of determining the “second form” is thus completely solved except when there is more than one ambiguous class in the principal spinor genus.     

Integral Apollonian circle packings and prime curvatures

It is shown that any primitive integral Apollonian circle packing captures a fraction of the prime numbers. Basically, the method consists of applying the circle method and considering the curvatures produced by a well-chosen family of binary quadratic forms.     

On primitively universal quadratic forms

In 1999, Manjul Bhargava proved the Fifteen Theorem and showed that there are exactly 204 universal positive definite integral quaternary quadratic forms. We consider primitive representations of quadratic forms and investigate a primitive counterpart to the Fifteen Theorem. In particular, we give an efficient method for deciding whether a positive definite integral quadratic form in four or more variables with odd square-free determinant is almost primitively universal.     

Local-global principles for representations of quadratic forms

We prove a local-global principle for the problem of representations of quadratic forms by quadratic forms over ℤ, in codimension ≥5. The proof uses the ergodic theory of p-adic groups, together with a fairly general observation on the structure of orbits of an arithmetic group acting on integral points of a variety.     

Rings of integral quaternions

A quaternion order derived from an integral ternary quadratic form f = Σa_ijx_ix_j of discriminant d = 4 det (a_ij) is m-maximal if m is not divisible by any prime p such that p² | d, or p 6; d and c_p = 1. If R is m-maximal and m is a product p₁ … p_r of primes, then any primitive element α of R has unique right-divisor ideals of each norm p₁ … p_k (k = 1, …, r). This generalizes Lipschitz's ninety-year-old theorem. We characterize m-maximal orders, study their ideals, and show how the preceding result yields formulas for the number of representations of integers by certain quaternary quadratic forms.     

Analysis of an algorithm for composition of binary quadratic forms

This note presents an algorithm which composes two reduced properly primitive binary quadratic forms of the same nonquadratic determinant D in O(M(log∥D∥)log log∥D∥) elementary operations.     

Representations of a p-Elementary Form by a Genus

We study the branching of representations of a p-elementary quadratic form by a genus of positive definite locally p-two-dimensional forms. A primitive representation of a p-elementary form is decomposed into a direct sum of minimal indecomposable representations; the latter representations are found in an explicit form. For the case of branching, we find local multipliers of the weight of representations of a form by a genus. As an application, we calculate the number of embeddings into the classical root lattices. The method of orthogonal complement is applied in constructing new genera of quadratic forms. Bibliography: 9 titles.     

A Hardy field extension of Szemerédi's theorem

In 1975 Szemerédi proved that a set of integers of positive upper density contains arbitrarily long arithmetic progressions. Bergelson and Leibman showed in 1996 that the common difference of the arithmetic progression can be a square, a cube, or more generally of the form p(n) where p(n) is any integer polynomial with zero constant term. We produce a variety of new results of this type related to sequences that are not polynomial. We show that the common difference of the progression in Szemerédi's theorem can be of the form [nδ] where δ is any positive real number and [x] denotes the integer part of x. More generally, the common difference can be of the form [a(n)] where a(x) is any function that is a member of a Hardy field and satisfies a(x)/xk→∞ and a(x)/xk+1→0 for some non-negative integer k. The proof combines a new structural result for Hardy sequences, techniques from ergodic theory, and some recent equidistribution results of sequences on nilmanifolds.     

Quasi-genera of quadratic forms

Let f be a quadratic form in n variables (n > 1) with nonzero determinant d. A prime p is said to be exceptional with respect to f if every automorph of f with rational elements, determinant ±1 and denominator prime to 2d has a denominator which is a quadratic residue of p. (Throughout, slight modifications must be made if p = 2.) Except for certain binary forms, each exceptional prime induces a splitting of the genus into two quasi-genera. Building on previous results, necessary and sufficient conditions are given that a prime p be exceptional for n = 2 and n = 3 and necessary conditions for n > 3. It is proved that there are no exceptional primes for n > 4 and only possibly in special cases for n = 4. A connection is shown between representations of integers by certain ternary forms and the existence of quasi-genera. Possible connections with spinor genera are mentioned and a few unanswered questions are posed.     

Number of Representations of p-One-Dimensional Forms by a Genus

We study branching of representations of a locally p-one-dimensional form by a genus of positive definite integral quadratic forms. We give a complete list of minimal representations by a genus for forms of square level. GaussMinkowski formulas are obtained for heights of representations over the ring of integers. As an application, we obtain formulas for heights of primitive representations by genera for specific forms constructed by the method of orthogonal complement. Bibliography: 6 titles.     

The ultratriangular form for prime-power lattice rules

A recent development in the theory of lattice rules has been the introduction of the unique ultratriangular D-Z form for prime-power rules. It is known that any lattice rule may be decomposed into its Sylow p-components. These components are prime-power rules, each of which has a unique ultratriangular form. By reassembling these ultratriangular forms in a defined way, it is possible to obtain a canonical form for any lattice rule. A special case occurs when the ultratriangular forms of each of the Sylow p-components have a consistent set of column indices. In this case, it is possible to obtain a unique canonical D-Z form. Given the column indices and the invariants for an ultratriangular form, we may obtain a formula for the number of ultratriangular forms, and hence the number of prime-power lattice rules, having these column indices and invariants.     

A stable range for quadratic forms over commutative rings

A commutative ring A has quadratic stable range 1 (qsr(A) = 1) if each primitive binary quadratic form over A represents a unit. It is shown that qsr(A) = 1 implies that every primitive quadratic form over A represents a unit, A has stable range 1 and finitely generated constant rank projectives over A are free. A classification of quadratic forms is provided over Bezout domains with characteristic other than 2, quadratic stable range 1, and a strong approximation property for a certain subset of their maximum spectrum. These domains include rings of holomorphic functions on connected noncompact Riemann surfaces. Examples of localizations of rings of algebraic integers are provided to show that the classical concept of stable range does not behave well in either direction under finite integral extensions and that qsr(A) = 1 does not descend from such extensions.     

Powerful arithmetic progressions

We give a complete characterization of so-called powerful arithmetic progressions, i.e. of progressions whose kth term is a kth power for all k. We also prove that the length of any primitive arithmetic progression of powers can be bounded both by any term of the progression different from 0 and ±1, and by its common difference. In particular, such a progression can have only finite length.