Nonstandard arithmetic and recursive comprehension

First order reasoning about hyperintegers can prove things about sets of integers. In the author’s paper Nonstandard Arithmetic and Reverse Mathematics, Bulletin of Symbolic Logic 12 (2006) 100-125, it was shown that each of the “big five” theories in reverse mathematics, including the base theory , has a natural nonstandard counterpart. But the counterpart of has a defect: it does not imply the Standard Part Principle that a set exists if and only if it is coded by a hyperinteger. In this paper we find another nonstandard counterpart, , that does imply the Standard Part Principle.     

Toward an arithmetic of polynomials

Summary ForR a commutative ring, which may have divisors of zero but which has no idempotents other than zero and one, we consider the problem of unique factorization of a polynomial with coefficients inR. We prove that, if the polynomial is separable, then such a unique factorization exists. We also define a Legendre symbol for a separable polynomial and a prime of commutative ring with exactly two idempotents in such a way that the symbols of classical number theory are subsumed. We calculate this symbol forR = Q in two cases where it has classically been of interest, namely quadratic extensions and cyclotomic extensions. We then calculate it in a situation which is new, namely the so called generalized cyclotomic extensions from a paper by S. Beale and D. K. Harrison. We study the Galois theory in the general ring situation and in particular define a category of separable polynomials (this is an extension of a paper by D. K. Harrison and M. Vitulli) and a cohomology theory of separable polynomials.     

Note on the local growth of iterated polynomials

The local behavior of the iterates of a real polynomial is investigated. The fundamental result may be stated as follows: THEOREM. Let x_i, for i=1, 2, ..., n+2, be defined recursively by x_i+1=f(x_i), where x₁ is an arbitrary real number and f is a polynomial of degree n. Let x_i+1?x_i≧1 for i=1, ..., n + 1. Then for all i, 1 ≦i≦n, and all k, 1≦k≦n+1?i, $$ - \frac{{2^{k - 1} }}{{k!}}< f\left[ {x_1 ,... + x_{i + k} } \right]< \frac{{x_{i + k + 1} - x_{i + k} + 2^{k - 1} }}{{k!}},$$ where f[x_i, ..., x_i+k] denotes the Newton difference quotient. As a consequence of this theorem, the authors obtain information on the local behavior of the solutions of certain nonlinear difference equations. There are several cases, of which the following is typical: THEOREM. Let {x_i}, i = 1, 2, 3, ..., be the solution of the nonlinear first order difference equation x_i+1=f(x_i) where x₁ is an arbitrarily assigned real number and f is the polynomial \(f(x) = \sum\limits_{j = 0}^n {a_j x^j } ,n \geqq 2\) . Let δ be positive with δ^n?1=|2^n?1/n!a_n|. Then, if n is even and a_n<0, there do not exist n + 1 consecutive increments Δx_i=x_i+1?x_i in the solution {x_i} with Δx_i≧δ. The special case in which the iterated polynomial has integer coefficients leads to a “nice” upper bound on a generalization of the van der Waerden numbers. Ap _k -sequence of length n is defined to be a strictly increasing sequence of positive integers {x ₁, ...,x _n } for which there exists a polynomial of degree at mostk with integer coefficients and satisfyingf(x _j )=x _j+1 forj=1, 2, ...,n?1. Definep _k (n) to be the least positive integer such that if {1, 2, ...,p _k (n)} is partitioned into two sets, then one of the two sets must contain ap _k -sequence of lengthn. THEOREM. p_n?2(n)≦(n!)^(n?2)!/2.     

A law of the iterated logarithm for arithmetic functions

Let be a sequence of centered iid random variables. Let be a strongly additive arithmetic function such that and put . If and satisfies a Lindeberg-type condition, we prove the following law of the iterated logarithm:

We also prove the validity of the corresponding weighted strong law of large numbers in .

     

Galois groups of some iterated polynomials over cyclotomic extensions

Let \(\varphi _p(z)=(z-1)^p+2-\zeta _p\), where \(\zeta _p\in \bar{\mathbb {Q}}\) is a primitive pth root of unity. Building on previous work, we show that the nth iterate \(\varphi _p^n(z)\) has Galois group \([C_p]^n\), an iterated wreath product of cyclic groups, whenever p is not a Wieferich prime.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

Splitting fields of characteristic polynomials of random elements in arithmetic groups

We discuss rather systematically the principle, implicit in earlier works, that for a “random” element in an arithmetic subgroup of a (split, say) reductive algebraic group over a number field, the splitting field of the characteristic polynomial, computed using any faitfhful representation, has Galois group isomorphic to the Weyl group of the underlying algebraic group. Besides tools such as the large sieve, which we had already used, we introduce some probabilistic ideas (large deviation estimates for finite Markov chains) and the general case involves a more precise understanding of the way Frobenius conjugacy classes are computed for such splitting fields (which is related to a map between regular elements of a finite group of Lie type and conjugacy classes in the Weyl group which had been considered earlier by Carter and Fulman for other purposes; we show in particular that the values of this map are equidistributed).     

On sums of coefficients of Borwein type polynomials over arithmetic progressions

The Ramanujan Journal - We obtain asymptotic formulas for sums over arithmetic progressions of coefficients of polynomials of the form $$ prod _{j=1}^nprod _{k=1}^{p-1}(1-q^{pj-k})^s, $$ where p...     

The density of prime divisors in the arithmetic dynamics of quadratic polynomials

Let f [x], and consider the recurrence given by a_n = f(a_{n –1}), with a₀ . Denote by P(f, a₀) the set of prime divisorsof this recurrence, that is, the set of primes dividing at leastone non-zero term, and denote the natural density of this setby D(P(f, a₀)). The problem of determining D(P(f, a₀)) whenf is linear has attracted significant study, although it remainsunresolved in full generality. In this paper, we consider thecase of f quadratic, where previously D(P(f, a₀)) was knownonly in a few cases. We show that D(P(f, a₀)) = 0 regardlessof a₀ for four infinite families of f, including f = x² + k,k \{–1}. The proof relies on tools from group theoryand probability theory to formulate a sufficient condition forD(P(f, a₀)) = 0 in terms of arithmetic properties of the forwardorbit of the critical point of f. This provides an analogy toresults in real and complex dynamics, where analytic propertiesof the forward orbit of the critical point have been shown todetermine many global dynamical properties of a quadratic polynomial.The article also includes apparently new work on the irreducibilityof iterates of quadratic polynomials.     

On an iterated construction of irreducible polynomials over finite fields of even characteristic by Kyuregyan

We deal with the construction of sequences of irreducible polynomials with coefficients in finite fields of even characteristic. We rely upon a transformation used by Kyuregyan in 2002, which generalizes the Q-transform employed previously by Varshamov and Garakov (1969) as well as by Meyn (1990) for the synthesis of irreducible polynomials. While in the iterative procedure described by Kyuregyan the coefficients of the initial polynomial of the sequence have to satisfy certain hypotheses, in the present paper these conditions are removed. We construct infinite sequences of irreducible polynomials of nondecreasing degree starting from any irreducible polynomial.     

An arithmetic formula for certain coefficients of the Euler product of Hecke polynomials

In 1997 the author found a criterion for the Riemann hypothesis for the Riemann zeta function, involving the nonnegativity of certain coefficients associated with the Riemann zeta function. In 1999 Bombieri and Lagarias obtained an arithmetic formula for these coefficients using the “explicit formula” of prime number theory. In this paper, the author obtains an arithmetic formula for corresponding coefficients associated with the Euler product of Hecke polynomials, which is essentially a product of L-functions attached to weight 2 cusp forms (both newforms and oldforms) over Hecke congruence subgroups Γ₀(N). The nonnegativity of these coefficients gives a criterion for the Riemann hypothesis for all these L-functions at once.     

A law of the iterated logarithm for Markov chains on ℕ0 associated with orthogonal polynomials

We derive laws of the iterated logarithm for Markov chains on the nonnegative integers whose transition probabilities are associated with a sequence of orthogonal polynomials. These laws can be applied to a large class of birth and death random walks and random walks on polynomial hypergroups. In particular, the results of our paper lead immediately to a law of the iterated logarithm for the growth of the distance of isotropic random walks on infinite distance-transitive graphs as well as on certain finitely generated semigroups from their starting points.     

Primes representable by polynomials and the lower bound of the least primes in arithmetic progressions

Letf (m) be an irreducible quadratic polynomial with integral coefficients and positive leading coefficient. Under the assumption of Extended Riemann Hypothesis, we obtain new remainder terms in the upper bounds on primes represented byf(m) orf(p) which greatly improve Bantle's recent results. As an application, we obtain, in the second part of the paper, a new result on the lower bound of the least primes in arithmetic progressions with some difference.