On the density of integers of the form 2 k + p in arithmetic progressions

Consider all the arithmetic progressions of odd numbers, no term of which is of the form 2^k ＋ p, where k is a positive integer and p is an odd prime. ErdSs ever asked whether all these progressions can be obtained from covering congruences. In this paper, we characterize all arithmetic progressions in which there are positive proportion natural numbers that can be expressed in the form 2^k ＋ p, and give a quantitative form of Romanoff＇s theorem on arithmetic progressions. As a corollary, we prove that the answer to the above Erdos problem is affirmative.     

Connections between connected topological spaces on the set of positive integers

In this paper we introduce a connected topology T on the set ? of positive integers whose base consists of all arithmetic progressions connected in Golomb’s topology. It turns out that all arithmetic progressions which are connected in the topology T form a basis for Golomb’s topology. Further we examine connectedness of arithmetic progressions in the division topology T′ on ? which was defined by Rizza in 1993. Immediate consequences of these studies are results concerning local connectedness of the topological spaces (?, T) and (?, T′).     

Discrepancy of Arithmetic Progressions in Higher Dimensions

K. F. Roth (1964, Acta. Arith.9, 257-260) proved that the discrepancy of arithmetic progressions contained in [1, N]={1, 2, …, N} is at least cN^1/4, and later it was proved that this result is sharp. We consider the d-dimensional version of this problem. We give a lower estimate for the discrepancy of arithmetic progressions on [1, N]^d and prove that this result is nearly sharp. We use our results to give an upper estimate for the discrepancy of lines on an N×N lattice, and we also give an estimate for the discrepancy of a related random hypergraph.     

The complement of certain recursively defined sets

An RD-set (recursively defined) is a minimal set of positive integers containing a given seed and closed under a given set of unary linear operations (x → ax + b). We examine conditions under which the complement of an RD-set may be expressed as the disjoint union of infinite arithmetic progressions.     

Some new results on k-free numbers

In this paper we obtain an improved asymptotic formula on the frequency of k-free numbers with a given difference. We also give a new upper bound of Barban-Davenport-Halberstam type for the k-free numbers in arithmetic progressions.     

On mixed joint discrete universality for a class of zeta-functions. II

We investigate the mixed joint discrete value distribution and the mixed joint discrete universality for the pair consisting of a rather general form of zeta-function with an Euler product and a periodic Hurwitz zeta-function with transcendental parameter. The common differences of relevant arithmetic progressions are not necessarily the same. Also some generalizations are given. For this purpose, certain arithmetic conditions on the common differences are used.

     

An upper bound for van der Waerden-like numbers usingk colors

Functions analogous to the van der Waerden numbers w(n, k) are considered. We replace the class of arithmetic progressions,A, by a classA′, withA ? A′; thus, the associated van der Waerden-like number will be smaller forsi’. We consider increasing sequences of positive integers x₁,…, x_n which are either arithmetic progressions or for which there exists a polynomial φ(x) with integer coefficients satisfying φ(xi) = x_i+1, i = 1,…,n - 1. Various further restrictions are placed on the types of polynomials allowed. Upper bounds are given for the corresponding functions w′(n, k) for the general pair (n,k). A table of several new computer-generated values of these functions is provided.     

Tessellating polyominos in the plane

Let the R² space be divided into unit squares where a polyomino is a finite, connected set of unit squares. In this paper, we give a necessary and sufficient condition on tessellating polyominos by observing an unexpected relation between such tessellations and systems of arithmetic progressions.     

Arithmetic Progressions in Linear Combinations of <Emphasis Type="Italic">S</Emphasis>-Units

M. Pohst asked the following question: is it true that every prime can be written in the form 2^u ± 3^v with some non-negative integers u, v? We put the problem into a general framework, and prove that the length of any arithmetic progression in t-term linear combinations of elements from a multiplicative group of rank r (e.g. of S-units) is bounded in terms of r, t, n, where n is the number of the coefficient t-tuples of the linear combinations. Combining this result with a recent theorem of Green and Tao on arithmetic progressions of primes, we give a negative answer to the problem of M. Pohst.     

Infinite families of infinite families of congruences for k-regular partitions

Let k∈{10,15,20}, and let b _k (n) denote the number k-regular partitions of n. We prove for half of all primes p and any t≥1 that there exist p?1 arithmetic progressions modulo p ^2t such that b _k (n) is a multiple of 5 for each n in one of these progressions.     

Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles

We study the upper tail of the number of arithmetic progressions of a given length in a random subset of {1,..., n}, establishing exponential bounds which are best possible up to constant factors in the exponent. The proof also extends to Schur triples, and, more generally, to the number of edges in random induced subhypergraphs of ‘almost linear’ k-uniform hypergraphs.     

On the distribution of square-full numbers in arithmetic progressions

A positive integer n is called a square-full number if p ² divides n whenever p is a prime divisor of n. In this paper we study the distribution of square-full numbers in arithmetic progressions by using the properties of Riemann zeta functions and Dirichlet L-functions.     

Discrepancy One among Homogeneous Arithmetic Progressions

We investigate a restriction of Paul Erd?s’ well-known problem from 1936 on the discrepancy of homogeneous arithmetic progressions. We restrict our attention to a finite set S of homogeneous arithmetic progressions, and ask when the discrepancy with respect to this set is exactly 1. We answer this question when S has size four or less, and prove that the problem for general S is NP-hard, even for discrepancy 1.     

Long arithmetic progressions in critical sets

Given a density 0<σ?1, we show for all sufficiently large primes p that if S⊆Z/pZ has the least number of three-term arithmetic progressions among all sets with at least σp elements, then S contains an arithmetic progression of length at least log^1/4+o(1)p.     

Finding Sum of Powers on Arithmetic Progressions with Application of Cauchy’s Equation

In this paper we introduce a method to find the sum of powers on arithmetic progressions by using Cauchy’s equation and obtain a general formula. Then we apply our results to show how to determine some other sums of powers and sums of products. Our results are more general than those in [9]. Finally we discuss the sum of powers on arithmetic progressions in commmutative rings with characteristic 2 and find ‘full polynomials’.     

On the arithmetic of the hyperelliptic curve y2 = xn + a

We study the arithmetic properties of hyperelliptic curves given by the affine equation y² = xⁿ+a by exploiting the structure of the automorphism groups. We show that these curves satisfy Lang’s conjecture about the covering radius (for some special covering maps).     

The closures of arithmetic progressions in the common division topology on the set of positive integers

In this paper we characterize the closures of arithmetic progressions in the topology T on the set of positive integers with the base consisting of arithmetic progressions {an + b} such that if the prime number p is a factor of a, then it is also a factor of b. The topology T is called the common division topology.     

Arithmetic progressions on Pell equations

In this paper we consider arithmetic progressions on Pell equations, i.e. integral solutions (X,Y) whose X-coordinates or Y-coordinates are in arithmetic progression.     

The segmented sieve of eratosthenes and primes in arithmetic progressions to 1012

The sieve of Eratosthenes, a well known tool for finding primes, is presented in several algorithmic forms. The algorithms are analyzed, with theoretical and actual computation times given. The authors use the sieve in a refined form (the dual sieve) to find the distribution of primes in twenty arithmetic progressions to 10¹². Tables of values are included.     

An uncertainty principle for function fields

In a recent paper, Granville and Soundararajan (2007) [5] proved an “uncertainty principle” for arithmetic sequences, which limits the extent to which such sequences can be well-distributed in both short intervals and arithmetic progressions. In the present paper we follow the methods of Granville and Soundararajan (2007) [5] and prove that a similar phenomenon holds in Fq[t].