Linear independence of automatic formal power series

We extend a result of J.-P. Allouche and O. Salon on linear independence of formal power series associated to polynomial extractions of quasistrongly p-additive sequences. The original result was on the F_p-linear independence and we extend it to the F_p[X]-linear independence.     

Unimodular eigenvalues, uniformly distributed sequences and linear dynamics

We study increasing sequences of positive integers (nk)_k?1 with the following property: every bounded linear operator T acting on a separable Banach (or Hilbert) space with supk?1‖Tnk‖<∞ has a countable set of unimodular eigenvalues. Whether this property holds or not depends on the distribution (modulo one) of sequences (nkα)_k?1, α∈R, or on the growth of nk+1/nk. Counterexamples to some conjectures in linear dynamics are given. For instance, a Hilbert space operator which is frequently hypercyclic, chaotic, but not topologically mixing is constructed. The situation of C₀-semigroups is also discussed.     

On the properties of Newton-Euler pairs

If and are two sequences such that a₁=b₁ and , then we say that (a_n,b_n) is a Newton-Euler pair. In the paper, we establish many formulas for Newton-Euler pairs, and then make use of them to obtain new results concerning some special sequences such as and B_n, where p(n) is the number of partitions of n, σ(n) is the sum of divisors of n, and B_n is the nth Bernoulli number.     

On the residue classes of integer sequences satisfying a linear three term recurrence formula

In this paper we investigate linear three-term recurrence formulae with sequences of integers (T(n))_n?0 and (U(n))_n?0, which are ultimately periodic modulo m, e.g.

     

Cubic and quartic congruences modulo a prime

Let p>3 be a prime, and denote the number of solutions of the congruence . In this paper, using the third-order recurring sequences we determine the values of N_p(x³+a₁x²+a₂x+a₃) and N_p(x⁴+ax²+bx+c), and construct the solutions of the corresponding congruences, where a₁,a₂,a₃,a,b,c are integers.     

Newtonian and Schinzel sequences in a domain

A Schinzel or F sequence in a domain is such that, for every ideal I with norm q, its first q terms form a system of representatives modulo I, and a Newton or N sequence such that the first q terms serve as a test set for integer-valued polynomials of degree less than q. Strong F and strong N sequences are such that one can use any set of q consecutive terms, not only the first ones, finally a very well F ordered sequence, for short, a V.W.F sequence, is such that, for each ideal I with norm q, and each integer s,{u_sq,…,u_(s+1)q−1} is a complete set of representatives modulo I. In a quasilocal domain, V.W.F sequences and N sequences are the same, so are strong F and strong N sequences. Our main result is that a strong N sequence is a sequence which is locally a strong F sequence, and an N sequence a sequence which is locally a V.W.F. sequence. We show that, for F sequences there is a bound on the number of ideals of a given norm. In particular, a sequence is a strong F sequence if and only if it is a strong N sequence and for each prime p, there is at most one prime ideal with finite residue field of characteristic p. All results are refined to sequences of finite length.     

Limit sets of automatic sequences

We show that for every k-automatic sequence there exists a natural number p>0 such that the sequences of the form (k^pn+j)_n?0 with j=0,…,p−1 are scaling sequences for f. Moreover, we demonstrate that every limit set is the union of certain basic limit sets.     

Quantum integers and cyclotomy

A sequence of functions satisfies the functional equation for multiplication of quantum integers if f_mn(q)=f_m(q)f_n(q^m) for all positive integers m and n. This paper describes the structure of all sequences of rational functions with coefficients in Q that satisfy this functional equation.     

A binary linear recurrence sequence of composite numbers

Let (a,b)∈Z², where b≠0 and (a,b)≠(±2,−1). We prove that then there exist two positive relatively prime composite integers x₁, x₂ such that the sequence given by xn+1=axn+bxn−1, n=2,3,… , consists of composite terms only, i.e., |xn| is a composite integer for each n∈N. In the proof of this result we use certain covering systems, divisibility sequences and, for some special pairs (a,±1), computer calculations. The paper is motivated by a result of Graham who proved this theorem in the special case of the Fibonacci-like sequence, where (a,b)=(1,1).     

Theoretical and empirical convergence results for additive congruential random number generators

Additive Congruential Random Number (ACORN) generators represent an approach to generating uniformly distributed pseudo-random numbers that is straightforward to implement efficiently for arbitrarily large order and modulus; if it is implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.This paper briefly reviews existing results concerning ACORN generators and relevant theory concerning sequences that are well distributed mod 1 in k dimensions. It then demonstrates some new theoretical results for ACORN generators implemented in integer arithmetic with modulus M=2^μ showing that they are a family of generators that converge (in a sense that is defined in the paper) to being well distributed mod 1 in k dimensions, as μ=log₂M tends to infinity. By increasing k, it is possible to increase without limit the number of dimensions in which the resulting sequences approximate to well distributed.The paper concludes by applying the standard TestU01 test suite to ACORN generators for selected values of the modulus (between 2⁶⁰ and 2¹⁵⁰), the order (between 4 and 30) and various odd seed values. On the basis of these and earlier results, it is recommended that an order of at least 9 be used together with an odd seed and modulus equal to 2^30p, for a small integer value of p. While a choice of p=2 should be adequate for most typical applications, increasing p to 3 or 4 gives a sequence that will consistently pass all the tests in the TestU01 test suite, giving additional confidence in more demanding applications.The results demonstrate that the ACORN generators are a reliable source of uniformly distributed pseudo-random numbers, and that in practice (as suggested by the theoretical convergence results) the quality of the ACORN sequences increases with increasing modulus and order.     

Cancellation in a short exponential sum

Let q be an odd integer, let τ be the order of 2 modulo q and let ξ be a primitive qth root of unity. Upper bounds for are proved in terms of the parameters μ and ν when q diverges along sequences Sμ,ν for which the quotient τ/log₂q belongs to the interval [μ,ν], with 1?μ and ν close enough to 1.     

Minimal zero sum sequences of length four over finite cyclic groups

Text

Let G be a finite cyclic group. Every sequence S over G can be written in the form S=(n₁g)⋅…⋅(nlg) where g∈G and n₁,…,nl∈[1,ord(g)], and the index ind(S) of S is defined to be the minimum of (n₁+?+nl)/ord(g) over all possible g∈G such that 〈g〉=〈supp(S)〉. The problem regarding the index of sequences has been studied in a series of papers, and a main focus is to determine sequences of index 1. In the present paper, we show that if G is a cyclic of prime power order such that gcd(|G|,6)=1, then every minimal zero-sum sequence of length 4 has index 1.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=BC7josX_xVs.     

Pattern sequences in ‹q, r›- numeration systems

Let q ≥ 2 and 0 ≤ r ≤ q − 2 be integers. In this paper, we study pattern sequences for patterns in ‹q, r›-numeration systems through their generating functions. Our result implies that any nontrivial linear combination over ? of pattern sequences chosen from different ‹q, r›-numeration systems cannot be a linear recurrence sequence. In particular, pattern sequences in different ‹q, r›-numeration systems are linearly independent over ?, while within one ‹q, r›-numeration system they can be linearly dependent ?.     

Partitions of natural numbers with the same representation functions

For a set A of nonnegative integers the representation functions R₂(A,n), R₃(A,n) are defined as the number of solutions of the equation n=a+a^′,a,a^′∈A with a<a^′, a?a^′, respectively. Let D(0)=0 and let D(a) denote the number of ones in the binary representation of a. Let A₀ be the set of all nonnegative integers a with even D(a) and A₁ be the set of all nonnegative integers a with odd D(a). In this paper we show that (a) if R₂(A,n)=R₂(N?A,n) for all n?2N−1, then R₂(A,n)=R₂(N?A,n)?1 for all n?12N²−10N−2 except for A=A₀ or A=A₁; (b) if R₃(A,n)=R₃(N?A,n) for all n?2N−1, then R₃(A,n)=R₃(N?A,n)?1 for all n?12N²+2N. Several problems are posed in this paper.     

A complete determination of Rabinowitsch polynomials

Let m be a positive integer and fm(x) be a polynomial of the form fm(x)=x²+x−m. We call a polynomial fm(x) a Rabinowitsch polynomial if for and consecutive integers x=x₀,x₀+1,…,x₀+s−1, |fm(x)| is either 1 or prime. In this paper, we show that there are exactly 14 Rabinowitsch polynomials fm(x).     

The Scholz theorem in function fields

The Scholz theorem in function fields states that the l-rank difference between the class groups of an imaginary quadratic function field and its associated real quadratic function field is either 0 or 1 for some prime l. Furthermore, Leopoldt's Spiegelungssatz (= the Reflection theorem) in function fields yields a comparison between the m-rank of some subgroup of the class group of an imaginary cyclic function field L₁ and the m-rank of some subgroup of the class group of its associated real cyclic function field L₂ for some prime number m; then their m-ranks also equal or differ by 1. In this paper we find an explicit necessary condition for their m-ranks (respectively l-ranks) to be the same in the case of cyclic function fields (respectively quadratic function fields). In particular, in the case of quadratic function fields, if l does not divide the regulator of L₂, then their l-ranks are the same, equivalently if their l-ranks differ by 1, then l divides the regulator of L₂.     

Poisson statistics via the Chinese Remainder Theorem

We consider the distribution of spacings between consecutive elements in subsets of Z/qZ, where q is highly composite and the subsets are defined via the Chinese Remainder Theorem. We give a sufficient criterion for the spacing distribution to be Poissonian as the number of prime factors of q tends to infinity, and as an application we show that the value set of a generic polynomial modulo q has Poisson spacings. We also study the spacings of subsets of Z/q₁q₂Z that are created via the Chinese Remainder Theorem from subsets of Z/q₁Z and Z/q₂Z (for q₁,q₂ coprime), and give criteria for when the spacings modulo q₁q₂ are Poisson. Moreover, we also give some examples when the spacings modulo q₁q₂ are not Poisson, even though the spacings modulo q₁ and modulo q₂ are both Poisson.     

Polynomial Cunningham chains

A sequence of prime numbers p₁,p₂,p₃,…, such that pi=2pi−1+? for all i, is called a Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the smallest positive integer such that 2pk+? is composite, then we say the chain has length k. It is conjectured that there are infinitely many Cunningham chains of length k for every positive integer k. A sequence of polynomials f₁(x),f₂(x),… in Z[x], such that f₁(x) has positive leading coefficient, each fi(x) is irreducible in Q[x] and fi(x)=xfi−1(x)+? for all i, is defined to be a polynomial Cunningham chain of the first or second kind, depending on whether ?=1 or −1 respectively. If k is the least positive integer such that fk+1(x) is reducible in Q[x], then we say the chain has length k. In this article, for polynomial Cunningham chains of both kinds, we prove that there are infinitely many chains of length k and, unlike the situation in the integers, that there are infinitely many chains of infinite length, by explicitly giving infinitely many polynomials f₁(x), such that fk+1(x) is the only term in the sequence that is reducible.     

Dirichlet series associated with polynomials and applications

We consider the possibility of the analytic continuation of the Dirichlet series SP;Z(s) associated with a polynomial P(x) and auxiliary series Z(s). In fact, we derive a certain criterion for the analytic continuation for some class of polynomials and give examples such that SP;Z(s) cannot be continued meromorphically to the whole plane C. We also study the asymptotic behaviors of the sum MP(x)=_∑P(n₁,…,nk)?xΛ(n₁)?Λ(nk) considered first by M. Peter. Generalizations of this sum are also considered.