On Linear Combinatorics II. Structure Theorems via Additive Number Theory

R with few compositions and/or small image sets. Here the fine structure of such sets of mappings will be described in terms of generalized arithmetic and geometric progressions, yielding Freiman–Ruzsa type results for a non-Abelian group. Received: November 28, 1996     

Generalized van der Waerden numbers

Certain generalizations of arithmetic progressions are used to define numbers analogous to the van der Waerden numbers. Several exact values of the new numbers are given, and upper bounds for these numbers are obtained. In addition, a comparison is made between the number of different arithmetic progressions and the number of different generalized arithmetic progressions.     

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.     

Powerful arithmetic progressions

We give a complete characterization of so-called powerful arithmetic progressions, i.e. of progressions whose kth term is a kth power for all k. We also prove that the length of any primitive arithmetic progression of powers can be bounded both by any term of the progression different from 0 and ±1, and by its common difference. In particular, such a progression can have only finite length.     

On a sequential model of the algebra of finite-valued logic

We consider basic postulates for an interpretation of the algebra of finite-valued logic in which prepositional variables are interpreted as variables whose values are sequences. We obtain an analytic representation of the operations of two-valued logic for a class of recursive sequences—generalized arithmetic progressions. We exhibit certain generalizations, modifications, and applications of the proposed model.Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, Issue 32, 1990, pp. 14–17.     

The higher dimensional analogue of certain estimates of Roth and Sárközy

In this paper we study the irregularities of distribution of subsets of integer vectors relative to higher dimensional arithmetic progressions. In particular we give one-sided estimate of the discrepancies of subsets of d-dimensional cubes, i.e. we show that these discrepancies have both large positive and small negative values.     

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].     

RANK DIFFERENCES FOR OVERPARTITIONS

In 1954, Atkin and Swinnerton-Dyer proved Dyson's conjectureson the rank of a partition by establishing formulae for thegenerating functions for rank differences in arithmetic progressions.In this paper, we prove formulae for the generating functionsfor rank differences for overpartitions. These are in termsof modular functions and generalized Lambert series.     

On arithmetic progressions on Pellian equations

We consider arithmetic progressions consisting of integers which are y-components of solutions of an equation of the form x ² ? dy ² = m. We show that for almost all four-term arithmetic progressions such an equation exists. We construct a seven-term arithmetic progression with the given property, and also several five-term arithmetic progressions which satisfy two different equations of the given form. These results are obtained by studying the properties of a parametric family of elliptic curves.     

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′).     

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.     

A note on maximal progression-free sets

Erd?s et al [Greedy algorithm, arithmetic progressions, subset sums and divisibility, Discrete Math. 200 (1999) 119-135.] asked whether there exists a maximal set of positive integers containing no three-term arithmetic progression and such that the difference of its adjacent elements approaches infinity. This note answers the question affirmatively by presenting such a set in which the difference of adjacent elements is strictly increasing. The construction generalizes to arithmetic progressions of any finite length.     

On the large sieve in algebraic number fields

In the present note Bombieri's central theorem concerning the average distribution of the prime numbers in arithmetic progressions is generalized to arbitrary algebraic number fields.Translated from Matematicheskie Zametki, Vol. 2, No. 6, pp. 673–680, December, 1967.Finally, I express my profound gratitude to B. V. Levin for setting the problem and the help he rendered and to A. I. Vinogradov for valuable suggestions.     

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.     

Forbidden arithmetic progressions in permutations of subsets of the integers

Permutations of the positive integers avoiding arithmetic progressions of length 5 were constructed in Davis et al. (1977), implying the existence of permutations of the integers avoiding arithmetic progressions of length 7. We construct a permutation of the integers avoiding arithmetic progressions of length 6. We also prove a lower bound of $\frac{1}{2}$ on the lower density of subsets of positive integers that can be permuted to avoid arithmetic progressions of length 4, sharpening the lower bound of $\frac{1}{3}$ from LeSaulnier and Vijay (2011).     

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.     

SOME ALMOST ALL RESULTS CONCERNINGTHE PJATECKII-SAPIRO PRIME NUMBERS

51.IntroductionSupposethatr>Oisafixednumberand[oldenotes,asusuaI,theintegralpartofo.LetForo1wasfirststudiedin1953byPjateckii-Sapiro[']whoprovedthat(1.1)holdsfor1相似文献   

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.     

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.     

Some multiplicative equations in finite fields

In this paper we consider estimating the number of solutions to multiplicative equations in finite fields when the variables run through certain sets with high additive structure. In particular, we consider estimating the multiplicative energy of generalized arithmetic progressions in prime fields and of boxes in arbitrary finite fields. We obtain sharp bounds in more general scenarios than previously known. Our arguments extend some ideas of Konyagin and Bourgain and Chang into new settings.