Sumset phenomenon in countable amenable groups

Jin proved that whenever A and B are sets of positive upper density in Z, A+B is piecewise syndetic. Jin's theorem was subsequently generalized by Jin and Keisler to a certain family of abelian groups, which in particular contains Zd. Answering a question of Jin and Keisler, we show that this result can be extended to countable amenable groups. Moreover we establish that such sumsets (or — depending on the notation — “product sets”) are piecewise Bohr, a result which for G=Z was proved by Bergelson, Furstenberg and Weiss. In the case of an abelian group G, we show that a set is piecewise Bohr if and only if it contains a sumset of two sets of positive upper Banach density.     

The structure of sets with few sums along a graph

We present common generalizations of some structure results of Freiman, Ruzsa, Balog-Szemerédi and Laczkovich-Ruzsa. We also give some applications to Combinatorial Geometry and Algebra, some of which generalize the aforementioned structure results even further.     

Large sets in finite fields are sumsets

For a prime p, a subset S of Zp is a sumset if S=A+A for some A⊂Zp. Let f(p) denote the maximum integer so that every subset S⊂Zp of size at least p−f(p) is a sumset. The question of determining or estimating f(p) was raised by Green. He showed that for all sufficiently large p, and proved, with Gowers, that f(p)<cp2/3log1/3p for some absolute constant c. Here we improve these estimates, showing that there are two absolute positive constants c₁,c₂ so that for all sufficiently large p,

     

关于整数和集的定理的推广

本文主要利用加性数论的理论考察整数和集,稚广了Vscvolod F．Lev的关于整数和的定理：设n≥1,B增包含[1,n],｜B｜〉n/4,k=｜B｜＋1,则 （1）当1≤n≤2k-3时,有ia^s能写成两个不同B中元之和。 （2）当2k-2≤,1〈3k-3时,有ia^s能写成最多四个B中元之和。 （3）当3k-3≤n〈4k-4时,有ia^s能写成最多2h个B中元之和。 其中h=max[2k/4k-4-n],i=1,2,3,4,6     

Linked graphs with restricted lengths

A graph G is k-linked if G has at least 2k vertices, and for every sequence x₁,x₂,…,x_k,y₁,y₂,…,y_k of distinct vertices, G contains k vertex-disjoint paths P₁,P₂,…,P_k such that P_i joins x_i and y_i for i=1,2,…,k. Moreover, the above defined k-linked graph G is modulo (m₁,m₂,…,m_k)-linked if, in addition, for any k-tuple (d₁,d₂,…,d_k) of natural numbers, the paths P₁,P₂,…,P_k can be chosen such that P_i has length d_i modulo m_i for i=1,2,…,k. Thomassen showed that, for each k-tuple (m₁,m₂,…,m_k) of odd positive integers, there exists a natural number f(m₁,m₂,…,m_k) such that every f(m₁,m₂,…,m_k)-connected graph is modulo (m₁,m₂,…,m_k)-linked. For m₁=m₂=…=m_k=2, he showed in another article that there exists a natural number g(2,k) such that every g(2,k)-connected graph G is modulo (2,2,…,2)-linked or there is XV(G) such that |X|4k−3 and G−X is a bipartite graph, where (2,2,…,2) is a k-tuple.We showed that f(m₁,m₂,…,m_k)max{14(m₁+m₂++m_k)−4k,6(m₁+m₂++m_k)−4k+36} for every k-tuple of odd positive integers. We then extend the result to allow some m_i be even integers. Let (m₁,m₂,…,m_k) be a k-tuple of natural numbers and ℓk such that m_i is odd for each i with ℓ+1ik. If G is 45(m₁+m₂++m_k)-connected, then either G has a vertex set X of order at most 2k+2ℓ−3+δ(m₁,…,m_ℓ) such that G−X is bipartite or G is modulo (2m₁,…,2m_ℓ,m_ℓ+1,…,m_k)-linked, where

Our results generalize several known results on parity-linked graphs.     

On problems of Erdös and Rudin

A well-known conjecture of W. Rudin is that the set of squares is a ∧_p-set for all p>4. In particular, this implies that for all ε>0, there exists a constant c_ε such that

     

A sum-product theorem in semi-simple commutative Banach algebras

The following analogue of the Erdös-Szemerédi sum-product theorem is shown. Let A=f₁,?,f_N be a finite set of N arbitrary distinct functions on some set. Then either the sum set f_i+f_j or the product set has at least N^1+c elements, where c>0 is an absolute constant. We use Freiman's lemma and Balog-Szemerédi-Gowers Theorem on graphs and combinatorics.As a corollary, we obtain an Erdös-Szemerédi type theorem for semi-simple commutative Banach algebras R. Thus if A⊂R is a finite set, |A| large enough, then

|A+A|+|A.A|>|A|1+c,