skip to main content


Title: When Sets Can and Cannot Have MSTD Subsets
A finite set of integers A is a sum-dominant (also called a More Sums Than Differences or MSTD) set if |A+A| > |A−A|. While almost all subsets of {0, . . . , n} are not sum-dominant, interestingly a small positive percentage are. We explore sufficient conditions on infinite sets of positive integers such that there are either no sum-dominant subsets, at most finitely many sum-dominant subsets, or infinitely many sum-dominant subsets. In particular, we prove no subset of the Fibonacci numbers is a sum-dominant set, establish conditions such that solutions to a recurrence relation have only finitely many sum-dominant subsets, and show there are infinitely many sum-dominant subsets of the primes.  more » « less
Award ID(s):
1659037 1561945
NSF-PAR ID:
10092873
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
Journal of integer sequences
Volume:
21
ISSN:
1530-7638
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Abstract Let $K$ be an algebraically closed field of prime characteristic $p$ , let $X$ be a semiabelian variety defined over a finite subfield of $K$ , let $\unicode[STIX]{x1D6F7}:X\longrightarrow X$ be a regular self-map defined over $K$ , let $V\subset X$ be a subvariety defined over $K$ , and let $\unicode[STIX]{x1D6FC}\in X(K)$ . The dynamical Mordell–Lang conjecture in characteristic $p$ predicts that the set $S=\{n\in \mathbb{N}:\unicode[STIX]{x1D6F7}^{n}(\unicode[STIX]{x1D6FC})\in V\}$ is a union of finitely many arithmetic progressions, along with finitely many $p$ -sets, which are sets of the form $\{\sum _{i=1}^{m}c_{i}p^{k_{i}n_{i}}:n_{i}\in \mathbb{N}\}$ for some $m\in \mathbb{N}$ , some rational numbers $c_{i}$ and some non-negative integers $k_{i}$ . We prove that this conjecture is equivalent with some difficult diophantine problem in characteristic 0. In the case $X$ is an algebraic torus, we can prove the conjecture in two cases: either when $\dim (V)\leqslant 2$ , or when no iterate of $\unicode[STIX]{x1D6F7}$ is a group endomorphism which induces the action of a power of the Frobenius on a positive dimensional algebraic subgroup of $X$ . We end by proving that Vojta’s conjecture implies the dynamical Mordell–Lang conjecture for tori with no restriction. 
    more » « less
  2. This paper is a sequel to [Monatsh. Math. 194 (2021) 523–554] in which results of that paper are generalized so that they hold in the setting of inhomogeneous Diophantine approximation. Given any integers [Formula: see text] and [Formula: see text], any [Formula: see text], and any homogeneous function [Formula: see text] that satisfies a certain nonsingularity assumption, we obtain a biconditional criterion on the approximating function [Formula: see text] for a generic element [Formula: see text] in the [Formula: see text]-orbit of [Formula: see text] to be (respectively, not to be) [Formula: see text]-approximable at [Formula: see text]: that is, for there to exist infinitely many (respectively, only finitely many) [Formula: see text] such that [Formula: see text] for each [Formula: see text]. In this setting, we also obtain a sufficient condition for uniform approximation. We also consider some examples of [Formula: see text] that do not satisfy our nonsingularity assumptions and prove similar results for these examples. Moreover, one can replace [Formula: see text] above by any closed subgroup of [Formula: see text] that satisfies certain integrability axioms (being of Siegel and Rogers type) introduced by the authors in the aforementioned previous paper. 
    more » « less
  3. In this paper, we investigate the existence of Sierpi´nski numbers and Riesel numbers as binomial coefficients. We show that for any odd positive integer r, there exist infinitely many Sierpi´nski numbers and Riesel numbers of the form kCr. Let S(x) be the number of positive integers r satisfying 1 ≤ r ≤ x for which kCr is a Sierpi´nski number for infinitely many k. We further show that the value S(x)/x gets arbitrarily close to 1 as x tends to infinity. Generalizations to base a-Sierpi´nski numbers and base a-Riesel numbers are also considered. In particular, we prove that there exist infinitely many positive integers r such that kCr is simultaneously a base a-Sierpi´nski and base a-Riesel number for infinitely many k. 
    more » « less
  4. Abstract

    Let $k \leq n$ be positive integers, and let $X_n = (x_1, \dots , x_n)$ be a list of $n$ variables. The Boolean product polynomial$B_{n,k}(X_n)$ is the product of the linear forms $\sum _{i \in S} x_i$, where $S$ ranges over all $k$-element subsets of $\{1, 2, \dots , n\}$. We prove that Boolean product polynomials are Schur positive. We do this via a new method of proving Schur positivity using vector bundles and a symmetric function operation we call Chern plethysm. This gives a geometric method for producing a vast array of Schur positive polynomials whose Schur positivity lacks (at present) a combinatorial or representation theoretic proof. We relate the polynomials $B_{n,k}(X_n)$ for certain $k$ to other combinatorial objects including derangements, positroids, alternating sign matrices, and reverse flagged fillings of a partition shape. We also relate $B_{n,n-1}(X_n)$ to a bigraded action of the symmetric group ${\mathfrak{S}}_n$ on a divergence free quotient of superspace.

     
    more » « less
  5. null (Ed.)
    We develop a convex analytic framework for ReLU neural networks which elucidates the inner workings of hidden neurons and their function space characteristics. We show that neural networks with rectified linear units act as convex regularizers, where simple solutions are encouraged via extreme points of a certain convex set. For one dimensional regression and classification, as well as rank-one data matrices, we prove that finite two-layer ReLU networks with norm regularization yield linear spline interpolation. We characterize the classification decision regions in terms of a closed form kernel matrix and minimum L1 norm solutions. This is in contrast to Neural Tangent Kernel which is unable to explain neural network predictions with finitely many neurons. Our convex geometric description also provides intuitive explanations of hidden neurons as auto encoders. In higher dimensions, we show that the training problem for two-layer networks can be cast as a finite dimensional convex optimization problem with infinitely many constraints. We then provide a family of convex relaxations to approximate the solution, and a cutting-plane algorithm to improve the relaxations. We derive conditions for the exactness of the relaxations and provide simple closed form formulas for the optimal neural network weights in certain cases. We also establish a connection to ℓ0-ℓ1 equivalence for neural networks analogous to the minimal cardinality solutions in compressed sensing. Extensive experimental results show that the proposed approach yields interpretable and accurate models. 
    more » « less