First-order decidability and definability of integers in infinite algebraic extensions of the rational numbers

We extend results of Videla and Fukuzaki to define algebraic integers in large classes of infinite algebraic extensions of Q and use these definitions for some of the fields to show the first-order undecidabilitv. We also obtain a structural sufficient condition for definability of the ring of integers over its field of fractions. In particular, we show that the following propositions hold: (1) For any rational prime q and any positive rational integer m. algebraic integers are definable in any Galois extension of Q where the degree of any finite subextension is not divisible by q^m. (2) Given a prime q, and an integer m > 0, algebraic integers are definable in a cyclotomic extension (and any of its subfields) generated by any set \(\{ {\zeta _{{p^l}}}|l \in {Z_{ > 0,}}P \ne q\) is any prime such that q^{m +1} ∧(p — 1)}. (3) The first-order theory of Any Abelina Extension of Q With Finitely Many Rational Primes is undecidable and rational integers are definable in these extensions.We also show that under a condition on the splitting of one rational Q generated elliptic curve over the field in question is enough to have a definition of Z and to show that the field is undecidable.     

On the solutions of a functional equation arising from multiplication of quantum integers

This paper is the first of several papers in which we prove, for the case where the fields of coefficients are of characteristic zero, four open problems posed in the work of Melvyn Nathanson (2003) [1] concerning the solutions of a functional equation arising from multiplication of quantum integers q[n]=qn−1+qn−2+?+q+1. In this paper, we prove one of the problems. The next papers, namely [002], [003] and [004] by Lan Nguyen, contain the solutions to the other 3 problems.     

Calculating formula and divisibility for relative class numbers of abelian function fields

In this paper abelian function fields are restricted to the subfields of cyclotomic function fields. For any abelian function field K/k with conductor an irreducible polynomial over a finite field of odd characteristic, we give a calculating formula of the relative divisor class number of K. And using the given calculating formula we obtain a criterion for checking whether or not the relative divisor class number is divisible by the characteristic of k.     

Lifting of solutions of an exponential congruence

In the present paper, a polynomial algorithm is suggested for reducing the problem of taking the discrete logarithm in the ring of algebraic integers modulo a power of a prime ideal to a similar problem with the power equal to one. Explicit formulas are obtained; instead of the Fermat quotients, in the case of residues in the ring of rational integers, these formulas use other polynomially computable logarithmic functions, like the $\mathfrak{p}$ -adic logarithm.     

Short rational generating functions for lattice point problems

We prove that for any fixed the generating function of the projection of the set of integer points in a rational -dimensional polytope can be computed in polynomial time. As a corollary, we deduce that various interesting sets of lattice points, notably integer semigroups and (minimal) Hilbert bases of rational cones, have short rational generating functions provided certain parameters (the dimension and the number of generators) are fixed. It follows then that many computational problems for such sets (for example, finding the number of positive integers not representable as a non-negative integer combination of given coprime positive integers ) admit polynomial time algorithms. We also discuss a related problem of computing the Hilbert series of a ring generated by monomials.

     

Uniform existential interpretation of arithmetic in rings of functions of positive characteristic

We show that first order integer arithmetic is uniformly positive-existentially interpretable in large classes of (subrings of) function fields of positive characteristic over some languages that contain the language of rings. One of the main intermediate results is a positive existential definition (in these classes), uniform among all characteristics p, of the binary relation “ $y=x^{p^{s}}$ or $x=y^{p^{s}}$ for some integer s≥0”. A natural consequence of our work is that there is no algorithm to decide whether or not a system of polynomial equations over $\mathbb {Z}[z]$ has solutions in all but finitely many polynomial rings $\mathbb {F}_{p}[z]$ . Analogous consequences are deduced for the rational function fields $\mathbb {F}_{p}(z)$ , over languages with a predicate for the valuation ring at zero.     

NP-complete problems for systems of Linear polynomial’s values divisibilities

The paper studies the algorithmic complexity of subproblems for satisfiability in positive integers of simultaneous divisibility of linear polynomials with nonnegative coefficients. In the general case, it is not known whether this problem is in the class NP, but that it is in NEXPTIME is known. The NP-completeness of two series of restricted versions of this problem such that a divisor of a linear polynomial is a number in the first case, and a linear polynomial is a divisor of a number in the second case is proved in the paper. The parameters providing the NP-completeness of these problems have been established. Their membership in the class P has been proven for smaller values of these parameters. For the general problem SIMULTANEOUS DIVISIBILITY OF LINEAR POLYNOMIALS, NP-hardness has been proven for its particular case, when the coefficients of the polynomials are only from the set {1, 2} and constant terms are only from the set {1, 5}.     

A rational reciprocity law over function fields

In the classical case, reciprocity laws for power residue symbols are called rational, which means that the power residue symbols only assume the values \({\pm 1}\) and have entries in \({\mathbb{Z}}\). We establish a rational reciprocity law over function fields.     

On the cyclotomic polynomial

For a given positive integer m and an algebraic number field K necessary and sufficient conditions for the mth cyclotomic polynomial to have K-integral solutions modulo a given integer of K are given. Among applications thereof are: that the solvability of the cyclotomic polynomial mod an integer yields information about the class number of related number fields; and about representation of integers by binary quadratic forms. The latter extends previous work of the author. Moreover some information is obtained pertaining to when an integer of K is the norm of an integer in a given quadratic extension of K. Finally an explicit determination of the pqth cyclotomic polynomial for distinct primes p and q is provided, and known results in the literature as well as generalizations thereof are obtained.     

Definability of Frobenius orbits and a result on rational distance sets

We prove that the first order theory of (possibly transcendental) meromorphic functions of positive characteristic \(p>2\) is undecidable. We also establish a negative solution to an analogue of Hilbert’s tenth problem for such fields of meromorphic functions, for Diophantine equations including vanishing conditions. These undecidability results are proved by showing that the binary relation \(\exists s\ge 0, f=g^{p^s}\) is positive existentially definable in such fields. We also prove that the abc conjecture implies a solution to the Erdös–Ulam problem on rational distance sets. These two seemingly distant topics are addressed by a study of power values of bivariate polynomials of the form F(X)G(Y).     

Non-existence of Some Nearly Perfect Sequences,Near Butson–Hadamard Matrices,and Near Conference Matrices

In this paper we study the non-existence problem of (nearly) perfect (almost) m-ary sequences via their connection to (near) Butson–Hadamard (BH) matrices and (near) conference matrices. We refine the idea of Brock on the unsolvability of certain equations in the case of cyclotomic number fields whose ring of integers is not a principal ideal domain and get many new non-existence results for near BH matrices and near conference matrices. We also apply previous results on vanishing sums of roots of unity and self conjugacy condition to derive non-existence results for near BH matrices and near conference matrices.     

Kawahara equation and modified Kawahara equation with time dependent coefficients: symmetry analysis and generalized ‐expansion method

In this paper, variable coefficients Kawahara equation (VCKE) and variable coefficients modified Kawahara equation (VCMKE), which arise in modeling of various physical phenomena, are studied by Lie group analysis. The similarity reductions and exact solutions are derived by determining the complete sets of point symmetries of these equations. Moreover, some exact analytic solutions are considered by the power series method. Further, a generalized ‐expansion method is applied to VCKE and VCMKE for constructing some new exact solutions. As a result, hyperbolic function solutions, trigonometric function solutions and some rational function solutions with parameters are furnished. Copyright © 2012 John Wiley & Sons, Ltd.     

On zeros of characteristic p zeta function

The location and multiplicity of the zeros of zeta functions encode interesting arithmetic information. We study the characteristic p zeta function of Goss. We focus on “trivial” zeros and prove a theorem on zeros at negative integers, showing more vanishing than that suggested by naive analogies. We also compute some concrete examples providing the extra vanishing, when the class number is more than one.Finally, we give an application of these results to the non-vanishing of certain class group components for cyclotomic function fields. In particular, we give examples of function fields, where all the primes of degree more than two are “irregular”, in the sense of the Drinfeld-Hayes cyclotomic theory.     

On Cyclotomic Numbers and the Reduction Map for the K-Theory of the Integers

We apply the recently proven compatibility of Beilinson and Soulé elements in K-theory to investigate density of rational primes p, for which the reduction map K _2n+1() K_{2n+1}(F_p)is nontrivial. Here n is an even, positive integer and F_p denotes the field of p elements. In the proof we use arithmetic of cyclotomic numbers which come from Soulé elements. Divisibility properties of the numbers are related to the Vandiver conjecture on the class group of cyclotomic fields. Using the K-theory of the integers, we compute an upper bound on the divisibility of these cyclotomic numbers.     

On realizability of sign patterns by real polynomials

The classical Descartes’ rule of signs limits the number of positive roots of a real polynomial in one variable by the number of sign changes in the sequence of its coefficients. One can ask the question which pairs of nonnegative integers (p, n), chosen in accordance with this rule and with some other natural conditions, can be the pairs of numbers of positive and negative roots of a real polynomial with prescribed signs of the coefficients. The paper solves this problem for degree 8 polynomials.     

Group invariant weighing matrices

We investigate the existence problem of group invariant matrices using algebraic approaches. We extend the usual concept of multipliers to group rings with cyclotomic integers as coefficients. This concept is combined with the field descent method and rational idempotents to develop new non-existence results.     

On semiconjugate rational functions

We investigate semiconjugate rational functions, that is rational functions A, B related by the functional equation \({A \circ X = X \circ B}\), where X is a rational function. We show that if A and B is a pair of such functions, then either A can be obtained from B by a certain iterative process, or A and B can be described in terms of orbifolds of non-negative Euler characteristic on the Riemann sphere.     

Well-posedness of the Cauchy problem for multidimensional difference equations in rational cones

The Cauchy problem is studied for a multidimensional difference equation in a class of functions defined at the integer points of a rational cone. We give an easy-to-check condition on the coefficients of the characteristic polynomial of the equation sufficient for solvability of the problem. A multidimensional analog of the condition ensuring stability of the Cauchy problem is stated on using the notion of amoeba of an algebraic hypersurface.