Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Some remarks on the Erdős Distinct subset sums problem
Let [Formula: see text] be a set of positive integers, [Formula: see text] denoting the largest element, so that for any two of the [Formula: see text] subsets the sum of all elements is distinct. Erdős asked whether this implies [Formula: see text] for some universal [Formula: see text]. We prove, slightly extending a result of Elkies, that for any [Formula: see text], [Formula: see text] with equality if and only if all subset sums are [Formula: see text]-separated. This leads to a new proof of the currently best lower bound [Formula: see text]. The main new insight is that having distinct subset sums and [Formula: see text] small requires the random variable [Formula: see text] to be close to Gaussian in a precise sense.  more » « less
Award ID(s):
2123224
PAR ID:
10528280
Author(s) / Creator(s):
Publisher / Repository:
World Scientific Publishing
Date Published:
Journal Name:
International Journal of Number Theory
Volume:
19
Issue:
08
ISSN:
1793-0421
Page Range / eLocation ID:
1783 to 1800
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Journal of Mathematical Logic)
    Fix a weakly minimal (i.e. superstable [Formula: see text]-rank [Formula: see text]) structure [Formula: see text]. Let [Formula: see text] be an expansion by constants for an elementary substructure, and let [Formula: see text] be an arbitrary subset of the universe [Formula: see text]. We show that all formulas in the expansion [Formula: see text] are equivalent to bounded formulas, and so [Formula: see text] is stable (or NIP) if and only if the [Formula: see text]-induced structure [Formula: see text] on [Formula: see text] is stable (or NIP). We then restrict to the case that [Formula: see text] is a pure abelian group with a weakly minimal theory, and [Formula: see text] is mutually algebraic (equivalently, weakly minimal with trivial forking). This setting encompasses most of the recent research on stable expansions of [Formula: see text]. Using various characterizations of mutual algebraicity, we give new examples of stable structures of the form [Formula: see text]. Most notably, we show that if [Formula: see text] is a weakly minimal additive subgroup of the algebraic numbers, [Formula: see text] is enumerated by a homogeneous linear recurrence relation with algebraic coefficients, and no repeated root of the characteristic polynomial of [Formula: see text] is a root of unity, then [Formula: see text] is superstable for any [Formula: see text]. 
    more » « less
  2. ; ; (, Journal of Mathematical Logic)
    We prove a number of results relating the concepts of Keisler measures, generic stability, randomizations and NIP formulas. Among other things, we do the following: (1)We introduce the notion of a Keisler–Morley measure, which plays the role of a Morley sequence for a Keisler measure. We prove that if [Formula: see text] is fim over [Formula: see text], then for any Keisler–Morley measure [Formula: see text] in [Formula: see text] over [Formula: see text] and any formula [Formula: see text], [Formula: see text]. We also show that any measure satisfying this conclusion must be fam.(2)We study the map, defined by Ben Yaacov, taking a definable measure [Formula: see text] to a type [Formula: see text] in the randomization. We prove that this map commutes with Morley products, and that if [Formula: see text] is fim then [Formula: see text] is generically stable.(3)We characterize when generically stable types are closed under Morley products by means of a variation of ict-patterns. Moreover, we show that NTP2theories satisfy this property.(4)We prove that if a local measure admits a suitably tame global extension, then it has finite packing numbers with respect to any definable family. We also characterize NIP formulas via the existence of tame extensions for local measures. 
    more » « less
  3. ; ; ; ; ; ; ; ; ; ; et al (, Journal of Knot Theory and Its Ramifications)
    Motivated by work of Kinoshita and Teraska, Lamm introduced the notion of a symmetric union, which can be constructed from a partial knot J by introducing additional crossings to a diagram of [Formula: see text] along its axis of symmetry. If both J and [Formula: see text] are partial knots for different symmetric union presentations of the same ribbon knot K, the knots J and [Formula: see text] are said to be symmetrically related. Lamm proved that if J and [Formula: see text] are symmetrically related, then [Formula: see text], asking whether the converse is true. In this paper, we give a negative answer to Lamm’s question, constructing for any natural number m a family of [Formula: see text] knots with the same determinant but such that no two knots in the family are symmetrically related. This result is a corollary to our main theorem, that if J is the partial knot in a symmetric union presentation for K, then for any odd prime p we have [Formula: see text], where [Formula: see text] denotes the number of p-colorings of a knot. 
    more » « less
  4. ; ; (, Journal of Mathematical Logic)
    Assume [Formula: see text]. If [Formula: see text] is an ordinal and X is a set of ordinals, then [Formula: see text] is the collection of order-preserving functions [Formula: see text] which have uniform cofinality [Formula: see text] and discontinuous everywhere. The weak partition properties on [Formula: see text] and [Formula: see text] yield partition measures on [Formula: see text] when [Formula: see text] and [Formula: see text] when [Formula: see text]. The following almost everywhere continuity properties for functions on partition spaces with respect to these partition measures will be shown. For every [Formula: see text] and function [Formula: see text], there is a club [Formula: see text] and a [Formula: see text] so that for all [Formula: see text], if [Formula: see text] and [Formula: see text], then [Formula: see text]. For every [Formula: see text] and function [Formula: see text], there is an [Formula: see text]-club [Formula: see text] and a [Formula: see text] so that for all [Formula: see text], if [Formula: see text] and [Formula: see text], then [Formula: see text]. The previous two continuity results will be used to distinguish the cardinalities of some important subsets of [Formula: see text]. [Formula: see text]. [Formula: see text]. [Formula: see text]. It will also be shown that [Formula: see text] has the Jónsson property: For every [Formula: see text], there is an [Formula: see text] with [Formula: see text] so that [Formula: see text]. 
    more » « less
  5. ; ; (, Journal of Mathematical Logic)
    For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance [Formula: see text] from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Text Encoded Conversion
  • XML
  • Save / Share this Record
  • Send to Email