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.     

基于文本挖掘的民声通道短信分类研究

根据短信可转化为文本的特性,将文本分类算法运用到短信处理技术之中。通过对短信文本进行预处理、特征选择及分类器等步骤,将短信文本按不同领域进行分类,最后分析意见所涉及的领域分类,有针对性地为政府决策提供可靠依据。     

When almost all sets are difference dominated

We investigate the relationship between the sizes of the sum and difference sets attached to a subset of {0,1,…,N}, chosen randomly according to a binomial model with parameter p(N), with N^?1 = o(p(N)). We show that the random subset is almost surely difference dominated, as N → ∞, for any choice of p(N) tending to zero, thus confirming a conjecture of Martin and O'Bryant. The proofs use recent strong concentration results. Furthermore, we exhibit a threshold phenomenon regarding the ratio of the size of the difference to the sumset. If p(N) = o(N^?1/2) then almost all sums and differences in the random subset are almost surely distinct and, in particular, the difference set is almost surely about twice as large as the sumset. If N^?1/2 = o(p(N)) then both the sum and difference sets almost surely have size (2N + 1) ? O(p(N)^?2), and so the ratio in question is almost surely very close to one. If p(N) = c · N^?1/2 then as c increases from zero to infinity (i.e., as the threshold is crossed), the same ratio almost surely decreases continuously from two to one according to an explicitly given function of c. We also extend our results to the comparison of the generalized difference sets attached to an arbitrary pair of binary linear forms. For certain pairs of forms f and g, we show that there in fact exists a sharp threshold at c_f,g · N^?1/2, for some computable constant c_f,g, such that one form almost surely dominates below the threshold and the other almost surely above it. The heart of our approach involves using different tools to obtain strong concentration of the sizes of the sum and difference sets about their mean values, for various ranges of the parameter p. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009