On consecutive quadratic non-residues: a conjecture of Issai Schur

Issai Schur once asked if it was possible to determine a bound, preferably using elementary methods, such that for all prime numbers p greater than the bound, the greatest number of consecutive quadratic non-residues modulo p is always less than p^1/2. This paper uses elementary methods to prove that 13 is the only prime number for which the greatest number of consecutive quadratic non-residues modulo p exceeds p^1/2.     

Limits of rank 4 Azumaya algebras and applications to desingularization

It is shown that the schematic image of the scheme of Azumaya algebra structures on a vector bundle of rank 4 over any base scheme is separated, of finite type, smooth of relative dimension 13 and geometrically irreducible over that base and that this construction base-changes well. This fully generalizes Seshadri’s theorem in [16] that the variety of specializations of (2 x 2)-matrix algebras is smooth in characteristic ≠ 2. As an application, a construction of Seshadri in [16] is shown in a characteristic-free way to desingularize the moduli space of rank 2 even degree semi-stable vector bundles on a complete curve. As another application, a construction of Nori over ℤ (Appendix, [16]) is extended to the case of a normal domain which is a universally Japanese (Nagata) ring and is shown to desingularize the Artin moduli space [1] of invariants of several matrices in rank 2. This desingularization is shown to have a good specialization property if the Artin moduli space has geometrically reduced fibers — for example this happens over ℤ. Essential use is made of Kneser’s concept [8] of ‘semi-regular quadratic module’. For any free quadratic module of odd rank, a formula linking the half-discriminant and the values of the quadratic form on its radical is derived.     

A result on the weight distributions of binary quadratic residue codes

Truong et al. [7]proved that the weight distribution of a binary quadratic residue code C with length congruent to −1 modulo 8 can be determined by the weight distribution of a certain subcode of C containing only one-eighth of the codewords of C. In this paper, we prove that the same conclusion holds for any binary quadratic residue codes.     

An <Emphasis Type="Italic">L</Emphasis><Subscript>\infty</Subscript>/<Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-Constrained Quadratic Optimization Problem with Applications to Neural Networks

Pattern formation in associative neural networks is related to a quadratic optimization problem. Biological considerations imply that the functional is constrained in the L _\infty norm and in the L ₁ norm. We consider such optimization problems. We derive the Euler–Lagrange equations, and construct basic properties of the maximizers. We study in some detail the case where the kernel of the quadratic functional is finite-dimensional. In this case the optimization problem can be fully characterized by the geometry of a certain convex and compact finite-dimensional set.     

Construction of pseudorandom binary lattices by using the multiplicative inverse

In an earlier work Hubert and the authors of this paper introduced and studied the notion of pseudorandomness of binary lattices. Later in another paper the authors gave a construction for a large family of “good” binary lattices by using the quadratic characters of finite fields. Here, a further large family of “good” binary lattices is constructed by using finite fields and the notion of multiplicative inverse.     

An analytic center quadratic cut method for the convex quadratic feasibility problem

 We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme. Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above. Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002 Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function     

整体函数域上不可分二次格的构作

构作了有理函数域F_(19)(x)上秩3到6的不可分格,回答了Gerstein关于整体函数域上是否存在秩5的不可分格的问题.     

Periodicity of hyperplane arrangements with integral coefficients modulo positive integers

We study central hyperplane arrangements with integral coefficients modulo positive integers q. We prove that the cardinality of the complement of the hyperplanes is a quasi-polynomial in two ways, first via the theory of elementary divisors and then via the theory of the Ehrhart quasi-polynomials. This result is useful for determining the characteristic polynomial of the corresponding real arrangement. With the former approach, we also prove that intersection lattices modulo q are periodic except for a finite number of q’s. This work was supported by the MEXT and the JSPS.     

Analytical solutions to the optimization of a quadratic cost function subject to linear and quadratic equality constraints

In the area of broad-band antenna array signal processing, the global minimum of a quadratic equality constrained quadratic cost minimization problem is often required. The problem posed is usually characterized by a large optimization space (around 50–90 tuples), a large number of linear equality constraints, and a few quadratic equality constraints each having very low rank quadratic constraint matrices. Two main difficulties arise in this class of problem. Firstly, the feasibility region is nonconvex and multiple local minima abound. This makes conventional numerical search techniques unattractive as they are unable to locate the global optimum consistently (unless a finite search area is specified). Secondly, the large optimization space makes the use of decision-method algorithms for the theory of the reals unattractive. This is because these algorithms involve the solution of the roots of univariate polynomials of order to the square of the optimization space. In this paper we present a new algorithm which exploits the structure of the constraints to reduce the optimization space to a more manageable size. The new algorithm relies on linear-algebra concepts, basic optimization theory, and a multivariate polynomial root-solving tool often used by decision-method algorithms.This research was supported by the Australian Research Council and the Corporative Research Centre for Broadband Telecommunications and Networking.     

Studies on the squaring construction

The code formulas for the iterated squaring construction for a finite group partition chain, derived by Forney [2], are extended to the case with a bi-infinite group partition chain, and the derivation presented here is much simpler than the one given by Forney for the finite case. It is also proven that the iterated squaring construction indeed generates the Reed-Muller codes. Moreover, the generalization of the code formulas to the bi-infinite case is used to derive code formulas for the lattices Λ(r,n) andRΛ(r,n), which correct some errors in [2]. Further, Gaussian integer lattices are discussed. A definition of their dual lattices is given, which is more general than the definition given by Forney [1]. Using this definition, some interesting properties of dual lattices and the squaring construction are obtained and then formulas of the duals of the Barnes-Wall lattices and their principal sublattices are derived, and one assumption from the derivation given by Forney [2] can be eliminated.     

Orthogonal splitting and class numbers of quadratic forms

Orthogonal splitting for lattices on quadratic spaces over algebraic number fields is studied. It is seen that if the rank of a lattice is sufficiently large, then its spinor genus must contain a decomposable lattice. Also, splitting theory is used to obtain a lower bound for the class number of a lattice (in the definite case) in terms of its rank, via the partition function.     

The Anosov Relation for Nielsen Numbers of Maps of Infra-Nilmanifolds

The relative ranks of the monoid of endomorphisms of a strong independence algebra of infinite rank modulo two distinguished subsets are calculated. These subsets are the group of automorphisms and the endomorphisms α satisfying α² = α. The extra generators are characterised in each case.     

Deformations of Diophantine Systems for Quadratic Forms of the Root Lattices A n

The paper considers a method of deformation of Diophantine quadratic systems in the n-dimensional root lattices A_n, which allows one to obtain sections of matrix quadratic equations Q[X] = A for quadratic forms Q of the lattices A_n and formulas for the number of form representations by the corresponding sections. Bibliography: 10 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 314, 2004, pp. 5–14.     

Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations

In this work, we take advantage of the powerful quadratic programming theory to obtain optimal solutions of scheduling problems. We apply a methodology that starts, in contrast to more classical approaches, by formulating three unrelated parallel machine scheduling problems as 0–1 quadratic programs under linear constraints. By construction, these quadratic programs are non-convex. Therefore, before submitting them to a branch-and-bound procedure, we reformulate them in such a way that we can ensure convexity and a high-quality continuous lower bound. Experimental results show that this methodology is interesting by obtaining the best results in literature for two of the three studied scheduling problems.     

Randomness of the square root of 2 and the Giant Leap,Part 1

We prove that the “quadratic irrational rotation” exhibits a central limit theorem. More precisely, let α be an arbitrary real root of a quadratic equation with integer coefficients; say, α = $ \sqrt 2 $ \sqrt 2 . Given any rational number 0 < x < 1 (say, x = 1/2) and any positive integer n, we count the number of elements of the sequence α, 2α, 3α, …, nα modulo 1 that fall into the subinterval [0, x]. We prove that this counting number satisfies a central limit theorem in the following sense. First, we subtract the “expected number” nx from the counting number, and study the typical fluctuation of this difference as n runs in a long interval 1 ≤ n ≤ N. Depending on α and x, we may need an extra additive correction of constant times logarithm of N; furthermore, what we always need is a multiplicative correction: division by (another) constant times square root of logarithm of N. If N is large, the distribution of this renormalized counting number, as n runs in 1 ≤ n ≤ N, is very close to the standard normal distribution (bell shaped curve), and the corresponding error term tends to zero as N tends to infinity. This is the main result of the paper (see Theorem 1.1). The proof is rather complicated and long; it has many interesting detours and byproducts. For example, the exact determination of the key constant factors (in the additive and multiplicative norming), which depend on α and x, requires surprisingly deep algebraic tools such as Dedeking sums, the class number of quadratic fields, and generalized class number formulas. The crucial property of a quadratic irrational is the periodicity of its continued fraction. Periodicity means self-similarity, which leads us to Markov chains: our basic probabilistic tool to prove the central limit theorem. We also use a lot of Fourier analysis. Finally, I just mention one byproduct of this research: we solve an old problem of Hardy and Littlewood on diophantine sums.     

An L \infty/ L 1-Constrained Quadratic Optimization Problem with Applications to Neural Networks

Pattern formation in associative neural networks is related to a quadratic optimization problem. Biological considerations imply that the functional is constrained in the L_\infty norm and in the L₁ norm. We consider such optimization problems. We derive the Euler–Lagrange equations, and construct basic properties of the maximizers. We study in some detail the case where the kernel of the quadratic functional is finite-dimensional. In this case the optimization problem can be fully characterized by the geometry of a certain convex and compact finite-dimensional set.     

A note on termination of the Baer construction of the prime radical

The well known Baer construction of the prime radical shows that the prime radical of an arbitrary ring is the union of the chain of ideals of the ring, constructed by transfinite induction, which starts with 0 and repeats the procedure of taking the sum of ideals that are nilpotent modulo ideals in the chain already constructed. Amitsur showed that for every ordinal number α there is a ring for which the construction stops precisely at α. In this paper we construct such examples with some extra properties. This allows us to construct, for every countable non-limit ordinal number α, an affine algebra for which the construction terminates precisely at α. Such an example was known due to Bergman for α = 2.     

Closed-form solution of a maximization problem

According to the characterization of eigenvalues of a real symmetric matrix A, the largest eigenvalue is given by the maximum of the quadratic form 〈xA, x〉 over the unit sphere; the second largest eigenvalue of A is given by the maximum of this same quadratic form over the subset of the unit sphere consisting of vectors orthogonal to an eigenvector associated with the largest eigenvalue, etc. In this study, we weaken the conditions of orthogonality by permitting the vectors to have a common inner product r where 0 ≤ r < 1. This leads to the formulation of what appears—from the mathematical programming standpoint—to be a challenging problem: the maximization of a convex objective function subject to nonlinear equality constraints. A key feature of this paper is that we obtain a closed-form solution of the problem, which may prove useful in testing global optimization software. Computational experiments were carried out with a number of solvers. We dedicate this paper to the memory of our great friend and colleague, Gene H. Golub.     

Even Unimodular Gaussian Lattices of Rank 12

We classify even unimodular Gaussian lattices of rank 12, that is, even unimodular integral lattices of rank 12 over the ring of Gaussian integers. This is equivalent to the classification of the automorphisms τ with τ²=−1 in the automorphism groups of all the Niemeier lattices, which are even unimodular (real) integral lattices of rank 24. There are 28 even unimodular Gaussian lattices of rank 12 up to equivalence.     

Construction of pseudorandom binary lattices by using the multiplicative inverse

In an earlier work Hubert and the authors of this paper introduced and studied the notion of pseudorandomness of binary lattices. Later in another paper the authors gave a construction for a large family of “good” binary lattices by using the quadratic characters of finite fields. Here, a further large family of “good” binary lattices is constructed by using finite fields and the notion of multiplicative inverse. Authors’ addresses: Christian Mauduit, Institut de Mathématiques de Luminy, CNRS, UMR 6206, 163 avenue de Luminy, Case 907, F-13288 Marseille Cedex 9, France; András Sárk?zy, Department of Algebra and Number Theory, E?tv?s Loránd University, Pázmány Péter sétány 1/C, H-1117 Budapest, Hungary