Sub-Ramsey Numbers for Arithmetic Progressions

Let the integers 1, . . . ,n be assigned colors. Szemerédi's theorem implies that if there is a dense color class then there is an arithmetic progression of length three in that color. We study the conditions on the color classes forcing totally multicolored arithmetic progressions of length 3. Let f(n) be the smallest integer k such that there is a coloring of {1, . . . ,n} without totally multicolored arithmetic progressions of length three and such that each color appears on at most k integers. We provide an exact value for f(n) when n is sufficiently large, and all extremal colorings. In particular, we show that f(n)=8n/17+O(1). This completely answers a question of Alon, Caro and Tuza.     

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.     

Average distribution of k-free numbers in arithmetic progressions

We obtain a new bound on the average value of the error term in the asymptotic formula for the number of k-free numbers in arithmetic progressions. In particular, we improve the results of J. Gibson (2014) and C. Hooley (1975).     

A Hardy field extension of Szemerédi's theorem

In 1975 Szemerédi proved that a set of integers of positive upper density contains arbitrarily long arithmetic progressions. Bergelson and Leibman showed in 1996 that the common difference of the arithmetic progression can be a square, a cube, or more generally of the form p(n) where p(n) is any integer polynomial with zero constant term. We produce a variety of new results of this type related to sequences that are not polynomial. We show that the common difference of the progression in Szemerédi's theorem can be of the form [nδ] where δ is any positive real number and [x] denotes the integer part of x. More generally, the common difference can be of the form [a(n)] where a(x) is any function that is a member of a Hardy field and satisfies a(x)/xk→∞ and a(x)/xk+1→0 for some non-negative integer k. The proof combines a new structural result for Hardy sequences, techniques from ergodic theory, and some recent equidistribution results of sequences on nilmanifolds.     

A canonical restricted version of van der waerden’s theorem

It is shown that there is a subsetS of integers containing no (k+1)-term arithmetic progression such that if the elements ofS are arbitrarily colored (any number of colors),S will contain ak-term arithmetic progression for which all of its terms have the same color, or all have distinct colors.     

Twins of <Emphasis Type="Italic">k</Emphasis>-free numbers in arithmetic progressions

We give a new upper bound of Barban–Davenport–Halberstam type for twins of k-free numbers in arithmetic progressions.     

Nonvanishing of Kronecker coefficients for rectangular shapes

We prove that for any partition (λ₁,…,λd²) of size ?d there exists k?1 such that the tensor square of the irreducible representation of the symmetric group Sk?d with respect to the rectangular partition (k?,…,k?) contains the irreducible representation corresponding to the stretched partition (kλ₁,…,kλd²). We also prove a related approximate version of this statement in which the stretching factor k is effectively bounded in terms of d. We further discuss the consequences for geometric complexity theory which provided the motivation for this work.     

Maximal Collections of Intersecting Arithmetic Progressions

Let N _t (k) be the maximum number of k-term arithmetic progressions of real numbers, any two of which have t points in common. We determine N ₂(k) for prime k and all large k, and give upper and lower bounds for N _t (k) when t 3.* Research supported in part by NSF grant DMS-0070618.     

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

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.     

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.     

Discrepancy in generalized arithmetic progressions

Estimating the discrepancy of the set of all arithmetic progressions in the first N natural numbers was one of the famous open problems in combinatorial discrepancy theory for a long time, successfully solved by K. Roth (lower bound) and Beck (upper bound). They proved that D(N)=min_χmax_A|∑_xAχ(x)|=Θ(N^1/4), where the minimum is taken over all colorings χ:[N]→{−1,1} and the maximum over all arithmetic progressions in [N]={0,…,N−1}.Sumsets of k arithmetic progressions, A₁++A_k, are called k-arithmetic progressions and they are important objects in additive combinatorics. We define D_k(N) as the discrepancy of the set {P∩[N]:P is a k-arithmetic progression}. The second author proved that D_k(N)=Ω(N^k/(2k+2)) and Přívětivý improved it to Ω(N^1/2) for all k≥3. Since the probabilistic argument gives D_k(N)=O((NlogN)^1/2) for all fixed k, the case k=2 remained the only case with a large gap between the known upper and lower bounds. We bridge this gap (up to a logarithmic factor) by proving that D_k(N)=Ω(N^1/2) for all k≥2.Indeed we prove the multicolor version of this result.     

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 fine fractal properties of generalized infinite Bernoulli convolutions

The paper is devoted to the investigation of generalized infinite Bernoulli convolutions, i.e., the distributions μξ of the following random variables: where ak are terms of a given positive convergent series; ξk are independent random variables taking values 0 and 1 with probabilities p0k and p1k correspondingly.We give (without any restriction on {an}) necessary and sufficient conditions for the topological support of ξ to be a nowhere dense set. Fractal properties of the topological support of ξ and fine fractal properties of the corresponding probability measure μξ itself are studied in details for the case where ak?rk:=ak+1+ak+2+? (i.e., rk−1?2rk) for all sufficiently large k. The family of minimal dimensional (in the sense of the Hausdorff–Besicovitch dimension) supports of μξ for the above mentioned case is also studied in details. We describe a series of sets (with additional structural properties) which play the role of minimal dimensional supports of generalized Bernoulli convolutions. We also show how a generalization of M. Cooper's dimensional results on symmetric Bernoulli convolutions can easily be derived from our results.     

Higher integrality conditions, volumes and Ehrhart polynomials

A polytope is integral if all of its vertices are lattice points. The constant term of the Ehrhart polynomial of an integral polytope is known to be 1. In previous work, we showed that the coefficients of the Ehrhart polynomial of a lattice-face polytope are volumes of projections of the polytope. We generalize both results by introducing a notion of k-integral polytopes, where 0-integral is equivalent to integral. We show that the Ehrhart polynomial of a k-integral polytope P has the properties that the coefficients in degrees less than or equal to k are determined by a projection of P, and the coefficients in higher degrees are determined by slices of P. A key step of the proof is that under certain generality conditions, the volume of a polytope is equal to the sum of volumes of slices of the polytope.     

A szemerédi type theorem for sets of positive density inR k

Letk≧2 andA a subset ofR ^k of positive upper density. LetV be the set of vertices of a (non-degenerate) (k−1)-dimensional simplex. It is shown that there existsl=l(A, V) such thatA contains an isometric image ofl′. V wheneverl′>l. The casek=2 yields a new proof of a result of Katznelson and Weiss [4]. Using related ideas, a proof is given of Roth’s theorem on the existence of arithmetic progressions of length 3 in sets of positive density.     

On Finite Pseudorandom Binary Sequences, V.On ( n α) and ( n 2α) Sequences

 Let k be a positive integer and α be a real number, and for if the fractional part of is <1/2 and e _n =−1 if it is ≥1/2. The pseudorandom properties of the sequence are studied. As measures of pseudorandomness, the regularity of the distribution relative to arithmetic progressions and the correlation are used. Here the special cases k=1 and k=2 are studied (while the case k>2 will be studied in the sequel).     

Integral solutions in arithmetic progression for y2=x3+k

Integral solutions toy ²=x ³+k, where either thex's or they's, or both, are in arithmetic progression are studied. When both thex's and they's are in arithmetic progression, then this situation is completely solved. One set of solutions where they's formed an arithmetic progression of length 4 had already been constructed. In this paper, we construct infinitely many sets of solutions where there are 4x's in arithmetic progression and we disprove Mohanty's Conjecture [8] by constructing infinitely many sets of solutions where there are 4, 5 and 6y's in arithmetic progression.     

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.     

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.