Constructing MSTD sets using bidirectional ballot sequences

A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S|>|S−S|. We construct a new dense family of MSTD subsets of {0,1,2,…,n−1}. Our construction gives Θ(n²/n) MSTD sets, improving the previous best construction with Ω(n²/n⁴) MSTD sets by Miller, Orosz, and Scheinerman.     

Explicit constructions of infinite families of MSTD sets

Text

We explicitly construct infinite families of MSTD (more sums than differences) sets, i.e., sets where |A+A|>|A−A|. There are enough of these sets to prove that there exists a constant C such that at least C/r⁴ of the r² subsets of {1,…,r} are MSTD sets; thus our family is significantly denser than previous constructions (whose densities are at most f(r)/²r/2 for some polynomial f(r)). We conclude by generalizing our method to compare linear forms ?₁A+?+?nA with ?i∈{−1,1}.

Video

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

Torsion units in integral group rings of some metabelian groups,II

We prove that any torsion unit of the integral group ring ZG is rationally conjugate to a trivial unit if G = A ⋊ X with both A and X abelian, |Xz.sfnc; < p for every prime p dividing |A| provided either |X| is prime or A ic cyclic.     

Torsion units in integral group rings of metacyclic groups

It is proved that if G is a split extension of a cyclic p-group by a cyclic p′-group with faithful action then any torsion unit of augmentation one of $\text{Z}$G is rationally conjugate to a group element. It is also proved that if G is a split extension of an abelian group A by an abelian group X with (|A|, |X|) = 1 then any torsion unit of $\text{Z}$G of augmentation one and order relatively prime to |A| is rationally conjugate to an element of X.     

Random sum-free subsets of abelian groups

We characterize the structure of maximum-size sum-free subsets of a random subset of an abelian group G. In particular, we determine the threshold above which, with high probability as |G| → ∞, each such subset is contained in some maximum-size sum-free subset of G, whenever q divides |G| for some (fixed) prime q with q ≡ 2 (mod 3). Moreover, in the special case G = ?_2n , we determine the sharp threshold for the above property. The proof uses recent ‘transference’ theorems of Conlon and Gowers, together with stability theorems for sum-free sets of abelian groups.     

A note on Freiman models in Heisenberg groups

Green and Ruzsa recently proved that for any s ≥ 2, any small squaring set A in a (multiplicative) abelian group, i.e., |A·A| < K|A|, has a Freiman smodel: it means that there exists a group G and a Freiman s-isomorphism from A into G such that |G| < f (s,K)|A|.     

Restricted sumsets and a conjecture of Lev

LetA, B, S be finite subsets of an abelian groupG. Suppose that the restricted sumsetC={α+b: α ∈A, b ∈B, and α − b ∉S} is nonempty and somec∈C can be written asa+b witha∈A andb∈B in at mostm ways. We show that ifG is torsion-free or elementary abelian, then |C|≥|A|+|B|−|S|−m. We also prove that |C|≥|A|+|B|−2|S|−m if the torsion subgroup ofG is cyclic. In the caseS={0} this provides an advance on a conjecture of Lev. This author is responsible for communications, and supported by the National Science Fund for Distinguished Young Scholars (No. 10425103) and the Key Program of NSF (No. 10331020) in China.     

Sets characterized by missing sums and differences

A more sums than differences (MSTD) set is a finite subset S of the integers such that |S+S|>|S−S|. We show that the probability that a uniform random subset of {0,1,…,n} is an MSTD set approaches some limit ρ>4.28×¹⁰−4. This improves the previous result of Martin and O?Bryant that there is a lower limit of at least 2×¹⁰−7. Monte Carlo experiments suggest that ρ≈4.5×¹⁰−4. We present a deterministic algorithm that can compute ρ up to arbitrary precision. We also describe the structure of a random MSTD set S⊆{0,1,…,n}. We formalize the intuition that fringe elements are most significant, while middle elements are nearly unrestricted. For instance, the probability that any “middle” element is in S approaches 1/2 as n→∞, confirming a conjecture of Miller, Orosz, and Scheinerman. In general, our results work for any specification on the number of missing sums and the number of missing differences of S, with MSTD sets being a special case.     

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.     

Group Connectivity of Bridged Graphs

Let G be a 2-edge-connected simple graph, and let A denote an abelian group with the identity element 0. If a graph G ^* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say G can be A-reduced to G*. A graph G is bridged if every cycle of length at least 4 has two vertices x, y such that d _G (x, y) < d _C (x, y). In this paper, we investigate the group connectivity number Λ _g (G) = min{n: G is A-connected for every abelian group with |A| ≥ n} for bridged graphs. Our results extend the early theorems for chordal graphs by Lai (Graphs Comb 16:165–176, 2000) and Chen et al. (Ars Comb 88:217–227, 2008).     

On the number of zero-sum subsequences

For a sequence S of elements from an additive abelian group G, let f(S) denote the number of subsequences of S the sum of whose terms is zero. In this paper we characterize all sequences S in G with f(S)>2^|S|-2, where |S| denotes the number of terms of S.     

On the maximum size of a k-zero-free set in an abelian group

A subset A of elements in an abelian group G is called k-zero-free if the equation x ₁ + x ₂ + ... + x _k = 0 has no solution in A. A k-zero-free set A in G is called maximal if A ∪ {x} is k-zero-free for no x ∈ G\A. Some bounds for the maximum size of a k-zero free set are obtained. In particular, we determine the maximum speed of a k-zero-free arithmetic progression in the cyclic group Z _n and find the upper and lower bounds for the maximum size of a k-zero-free set in an abelian group G. We describe the structure of a maximal k-zero-free set A in the cyclic group Z _n provided that gcd(n, k) = 1 and k|A| ≥ n + 1.     

On sets with small doubling property

Suppose that G is an arbitrary Abelian group and A is any finite subset G. A set A is called a set with small sumset if, for some number K, we have |A + A| ≤ K|A|. The structural properties of such sets were studied in the papers of Freiman, Bilu, Ruzsa, Chang, Green, and Tao. In the present paper, we prove that, under certain constraints on K, for any set with small sumset, there exists a set Λ, Λ ? _? K log |A|, such that |A ν Λ| ? |A|/K ^1/2+? , where ? > 0. In contrast to the results of the previous authors, our theorem is nontrivial even for a sufficiently large K. For example, for K we can take |A| ^η , where η > 0. The method of proof used by us is quite elementary.     

Arbitrary torsion classes and almost free abelian groups

Using the set theoretical principle ? for arbitrary large cardinals κ, arbitrary large strongly κ-free abelian groupsA are constructed such that Hom(A, G)={0} for all cotorsion-free groupsG with |G|<κ. This result will be applied to the theory of arbitrary torsion classes for Mod-Z. It allows one, in particular, to prove that the classF of cotorsion-free abelian groups is not cogenerated by aset of abelian groups. This answers a conjecture of Göbel and Wald positively. Furthermore, arbitrary many torsion classes for Mod-Z can be constructed which are not generated or not cogenerated by single abelian groups.     

Progression-free sets in finite abelian groups

Let G be a finite abelian group. Write and denote by rk(2G) the rank of the group 2G.Extending a result of Meshulam, we prove the following. Suppose that A⊆G is free of “true” arithmetic progressions; that is, a₁+a₃=2a₂ with a₁,a₂,a₃∈A implies that a₁=a₃. Then |A|<2|G|/rk(2G). When G is of odd order this reduces to the original result of Meshulam.As a corollary, we generalize a result of Alon and show that if an integer k?2 and a real ε>0 are fixed, |2G| is large enough, and a subset A⊆G satisfies |A|?(1/k+ε)|G|, then there exists A₀⊆A such that 1?|A₀|?k and the elements of A₀ add up to zero. When G is of odd order or cyclic this reduces to the original result of Alon.     

Malliavin's theorem for weak synthesis on nonabelian groups

Malliavin's celebrated theorem on the failure of spectral synthesis for the Fourier algebra A(G) on nondiscrete abelian groups was strengthened to give failure of weak synthesis by Parthasarathy and Varma. We extend this to nonabelian groups by proving that weak synthesis holds for A(G) if and only if G is discrete. We give the injection theorem and the inverse projection theorem for weak X-spectral synthesis, as well as a condition for the union of two weak X-spectral sets to be weak X-spectral for an A(G)-submodule X of VN(G). Relations between weak X-synthesis in A(G) and A(G×G) and the Varopoulos algebra V(G) are explored. The concept of operator synthesis was introduced by Arveson. We extend several recent investigations on operator synthesis by defining and studying, for a V^∞(G)-submodule M of B(L²(G)), sets of weak M-operator synthesis. Relations between X-Ditkin sets and M-operator Ditkin sets and between weak X-spectral synthesis and weak M-operator synthesis are explored.     

Degree conditions for group connectivity

Let G be a 2-edge-connected simple graph on n≥13 vertices and A an (additive) abelian group with |A|≥4. In this paper, we prove that if for every uv∉E(G), max{d(u),d(v)}≥n/4, then either G is A-connected or G can be reduced to one of K_2,3,C₄ and C₅ by repeatedly contracting proper A-connected subgraphs, where C_k is a cycle of length k. We also show that the bound n≥13 is the best possible.     

On the Small Squaring and Commutativity

Let G be a group and let k > 2 be an integer, such that (k²– 3)(k – 1) < |G|/15 if G is finite. Supposethat the condition |A²| k(k + 1)/2 + (k – 3)/2 is satisfiedby every it-element subset A G. Then G is abelian. The proofuses the structure of quasi-invariant sets.     

Some results on minimal sumset sizes in finite non-abelian groups

Let G be a group. We study the minimal sumset (or product set) size μG(r,s)=min{|A⋅B|}, where A,B range over all subsets of G with cardinality r,s respectively. The function μG has recently been fully determined in [S. Eliahou, M. Kervaire, A. Plagne, Optimally small sumsets in finite abelian groups, J. Number Theory 101 (2003) 338-348; S. Eliahou, M. Kervaire, Minimal sumsets in infinite abelian groups, J. Algebra 287 (2005) 449-457] for G abelian. Here we focus on the largely open case where G is finite non-abelian. We obtain results on μG(r,s) in certain ranges for r and s, for instance when r?3 or when r+s?|G|−1, and under some more technical conditions. (See Theorem 4.4.) We also compute μG for a few non-abelian groups of small order. These results extend the Cauchy-Davenport theorem, which determines μG(r,s) for G a cyclic group of prime order.     

Degree conditions and degree bounded trees

We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σ_k(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σ_k(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σ_k−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that d_T(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp.