• ### On the notions of upper and lower density(1506.04664)

Aug. 9, 2019 math.CO, math.CA, math.NT
Let $\mathcal{P}({\bf N})$ be the power set of ${\bf N}$. We say that a function $\mu^\ast: \mathcal{P}({\bf N}) \to \bf R$ is an upper density if, for all $X,Y\subseteq{\bf N}$ and $h, k\in{\bf N}^+$, the following hold: (F1) $\mu^\ast({\bf N}) = 1$; (F2) $\mu^\ast(X) \le \mu^\ast(Y)$ if $X \subseteq Y$; (F3) $\mu^\ast(X \cup Y) \le \mu^\ast(X) + \mu^\ast(Y)$; (F4) $\mu^\ast(k\cdot X) = \frac{1}{k} \mu^\ast(X)$, where $k \cdot X:=\{kx: x \in X\}$; (F5) $\mu^\ast(X + h) = \mu^\ast(X)$. We show that the upper asymptotic, upper logarithmic, upper Banach, upper Buck, upper Polya, and upper analytic densities, together with all upper $\alpha$-densities (with $\alpha$ a real parameter $\ge -1$), are upper densities in the sense of our definition. Moreover, we establish the mutual independence of axioms (F1)-(F5), and we investigate various properties of upper densities (and related functions) under the assumption that (F2) is replaced by the weaker condition that $\mu^\ast(X)\le 1$ for every $X\subseteq{\bf N}$. Overall, this allows us to extend and generalize results so far independently derived for some of the classical upper densities mentioned above, thus introducing a certain amount of unification into the theory.
• ### Structural properties of subadditive families with applications to factorization theory(1706.03525)

Nov. 12, 2018 math.CO, math.NT, math.AC, math.RA
Let $H$ be a multiplicatively written monoid. Given $k\in{\bf N}^+$, we denote by $\mathscr U_k$ the set of all $\ell\in{\bf N}^+$ such that $a_1\cdots a_k=b_1\cdots b_\ell$ for some atoms $a_1,\ldots,a_k,b_1,\ldots,b_\ell\in H$. The sets $\mathscr U_k$ are one of the most fundamental invariants studied in the theory of non-unique factorization, and understanding their structure is a basic problem in the field: In particular, it is known that, in many cases of interest, these sets are almost arithmetic progressions with the same difference and bound for all large $k$, namely, $H$ satisfies the Structure Theorem for Unions. The present paper improves the current state of the art on this problem. More precisely, we show that, under mild assumptions on $H$, not only does the Structure Theorem for Unions hold, but there also exists $\mu\in{\bf N}^+$ such that, for every $M\in{\bf N}$, the sequences $$\bigl((\mathscr U_k-\inf\mathscr U_k)\cap[\![0,M]\!]\bigr)_{k\ge 1} \quad\text{and}\quad \bigl((\sup\mathscr U_k-\mathscr U_k)\cap[\![0,M]\!]\bigr)_{k\ge 1}$$ are $\mu$-periodic from some point on. The result applies, e.g., to (the multiplicative monoid of) all commutative Krull domains (e.g., Dedekind domains) with finite class group; a variety of weakly Krull commutative domains (including all orders in number fields with finite elasticity); some maximal orders in central simple algebras over global fields; and all numerical monoids. Large parts of the proofs are worked out in a "purely additive model", by inquiring into the properties of what we call a subadditive family, i.e., a collection $\mathscr L$ of subsets of $\bf N$ such that, for all $L_1,L_2\in\mathscr L$, there is $L\in\mathscr L$ with $L_1+L_2\subseteq L$.
• ### Power monoids: A bridge between Factorization Theory and Arithmetic Combinatorics(1701.09152)

July 2, 2018 math.CO, math.NT, math.AC, math.RA
We extend a few fundamental aspects of the classical theory of non-unique factorization, as presented in Geroldinger and Halter-Koch's 2006 monograph on the subject, to a non-commutative and non-cancellative setting, in the same spirit of Baeth and Smertnig's work on the factorization theory of non-commutative, but cancellative monoids [J. Algebra 441 (2015), 475-551]. Then, we bring in power monoids and, applying the abstract machinery developed in the first part, we undertake the study of their arithmetic. More in particular, let $H$ be a multiplicatively written monoid. The set $\mathcal P_{\rm fin}(H)$ of all non-empty finite subsets of $H$ is naturally made into a monoid, which we call the power monoid of $H$ and is non-cancellative unless $H$ is trivial, by endowing it with the operation $(X,Y) \mapsto \{xy: (x,y) \in X \times Y\}$. Power monoids are, in disguise, one of the primary objects of interest in arithmetic combinatorics, and here for the first time we tackle them from the perspective of factorization theory. Proofs lead to consider various properties of finite subsets of $\mathbf N$ that can or cannot be split into a sumset in a non-trivial way, which gives rise to a rich interplay with additive number theory.
• ### On the Arithmetic of Power Monoids and Sumsets in Cyclic Groups(1804.10913)

April 29, 2018 math.CO, math.NT, math.RA
Let $H$ be a multiplicatively written monoid (in particular, a group). We denote by $\mathcal P_{\rm fin,\times}(H)$ the monoid obtained by endowing the collection of all finite subsets of $H$ containing a unit of $H$ with the operation of setwise multiplication $(X,Y) \mapsto \{xy: x \in X, y \in Y\}$, and we study fundamental features of the arithmetic of this structure. In particular, we show that $\mathcal{P}_{\text{fin},\times}(H)$ is atomic (that is, each non-unit is a product of irreducibles) if and only if $H$ has no non-identity element $x$ with $x^2=1$ or $x^2 = x$. As a corollary, we obtain that $\mathcal{P}_{\text{fin},\times}(H)$ is BF if and only if $H$ is torsion-free. Also, we introduce a suitable notion of "minimal factorization" to account for the fact that $\mathcal P_{\text{fin},\times}(H)$ may contain non-trivial idempotents, in which case standard definitions from Factorization Theory degenerate and lose their significance. Accordingly, we characterize when $\mathcal{P}_{\text{fin},\times}(H)$ is a "minimal BF-monoid" (respectively, "minimal HF-monoid"), i.e., each of its elements has minimal factorizations of bounded (respectively, unique) length. Many proofs boil down to considering sumset decompositions in $(\mathbf{Z}/n\mathbf{Z}, +)$ or $(\mathbf N, +)$, which gives rise to an intriguing interplay with Additive Combinatorics.
• ### On the number of distinct prime factors of a sum of super-powers(1511.08784)

Nov. 18, 2017 math.NT
Given $k, \ell \in {\bf N}^+$, let $x_{i,j}$ be, for $1 \le i \le k$ and $0 \le j \le \ell$, some fixed integers, and define, for every $n \in {\bf N}^+$, $s_n := \sum_{i=1}^k \prod_{j=0}^\ell x_{i,j}^{n^j}$. We prove that the following are equivalent: (a) There are a real $\theta > 1$ and infinitely many indices $n$ for which the number of distinct prime factors of $s_n$ is greater than the super-logarithm of $n$ to base $\theta$. (b) There do not exist non-zero integers $a_0,b_0,\ldots,a_\ell,b_\ell$ such that $s_{2n}=\prod_{i=0}^\ell a_i^{(2n)^i}$ and $s_{2n-1}=\prod_{i=0}^\ell b_i^{(2n-1)^i}$ for all $n$. We will give two different proofs of this result, one based on a theorem of Evertse (yielding, for a fixed finite set of primes $\mathcal S$, an effective bound on the number of non-degenerate solutions of an $\mathcal S$-unit equation in $k$ variables over the rationals) and the other using only elementary methods. As a corollary, we find that, for fixed $c_1, x_1, \ldots,c_k, x_k \in \mathbf N^+$, the number of distinct prime factors of $c_1 x_1^n+\cdots+c_k x_k^n$ is bounded, as $n$ ranges over $\mathbf N^+$, if and only if $x_1=\cdots=x_k$.
• ### Commutativity of integral quasi-arithmetic means on measure spaces(1703.03938)

April 12, 2017 math.CA
Let $(X, \mathscr{L}, \lambda)$ and $(Y, \mathscr{M}, \mu)$ be finite measure spaces for which there exist $A \in \mathscr{L}$ and $B \in \mathscr{M}$ with $0 < \lambda(A) < \lambda(X)$ and $0 < \mu(B) < \mu(Y)$, and let $I\subseteq \mathbf{R}$ be a non-empty interval. We prove that, if $f$ and $g$ are continuous bijections $I \to \mathbf{R}^+$, then the equation $$f^{-1}\!\left(\int_X f\!\left(g^{-1}\!\left(\int_Y g \circ h\;d\mu\right)\right)d \lambda\right)\! = g^{-1}\!\left(\int_Y g\!\left(f^{-1}\!\left(\int_X f \circ h\;d\lambda\right)\right)d \mu\right)$$ is satisfied by every $\mathscr{L} \otimes \mathscr{M}$-measurable simple function $h: X \times Y \to I$ if and only if $f=c g$ for some $c \in \mathbf{R}^+$ (it is easy to see that the equation is well posed). An analogous, but essentially different, result, with $f$ and $g$ replaced by continuous injections $I \to \mathbf R$ and $\lambda(X)=\mu(Y)=1$, was recently obtained in [Indag. Math. 27 (2016), 945-953].
• ### Arithmetic of commutative semigroups with a focus on semigroups of ideals and modules(1612.03116)

March 4, 2017 math.CO, math.NT, math.AC, math.RA
Let $H$ be a commutative semigroup with unit element such that every non-unit can be written as a finite product of irreducible elements (atoms). For every $k \in \mathbb N$, let $\mathscr U_k (H)$ denote the set of all $\ell \in \mathbb N$ with the property that there are atoms $u_1, \ldots, u_k, v_1, \ldots, v_{\ell}$ such that $u_1 \cdot \ldots \cdot u_k = v_1 \cdot \ldots \cdot v_{\ell}$ (thus, $\mathscr U_k (H)$ is the union of all sets of lengths containing $k$). The Structure Theorem for Unions states that, for all sufficiently large $k$, the sets $\mathscr U_k (H)$ are almost arithmetical progressions with the same difference and global bound. We present a new approach to this result in the framework of arithmetic combinatorics, by deriving, for suitably defined families of subsets of the non-negative integers, a characterization of when the Structure Theorem holds. This abstract approach allows us to verify, for the first time, the Structure Theorem for a variety of possibly non-cancellative semigroups, including semigroups of (not necessarily invertible) ideals and semigroups of modules. Furthermore, we provide the very first example of a semigroup (actually, a locally tame Krull monoid) that does not satisfy the Structure Theorem.
• ### Upper and lower densities have the strong Darboux property(1510.07473)

Dec. 29, 2016 math.CA, math.FA, math.NT
Let $\mathcal{P}({\bf N})$ be the power set of $\bf N$. An upper density (on $\bf N$) is a non\-decreasing and subadditive function $\mu^\ast: \mathcal{P}({\bf N})\to\bf R$ such that $\mu^\ast({\bf N}) = 1$ and $\mu^\ast(k \cdot X + h) = \frac{1}{k} \mu^\ast(X)$ for all $X \subseteq \bf N$ and $h,k \in {\bf N}^+$, where $k \cdot X + h := \{kx + h: x \in X\}$. The upper asymptotic, upper Banach, upper logarithmic, upper Buck, upper P\'olya, and upper analytic densities are examples of upper densities. We show that every upper density $\mu^\ast$ has the strong Darboux property, and so does the associated lower density, where a function $f: \mathcal P({\bf N}) \to \bf R$ is said to have the strong Darboux property if, whenever $X \subseteq Y \subseteq \bf N$ and $a \in [f(X),f(Y)]$, there is a set $A$ such that $X\subseteq A\subseteq Y$ and $f(A)=a$. In fact, we prove the above under the assumption that the monotonicity of $\mu^\ast$ is relaxed to the weaker condition that $\mu^\ast(X) \le 1$ for every $X \subseteq \bf N$.
• ### Multivariate Delta Goncarov and Abel Polynomials(1608.05836)

Aug. 20, 2016 math.CO, math.CA
Classical Gon\v{c}arov polynomials are polynomials which interpolate derivatives. Delta Gon\v{c}arov polynomials are polynomials which interpolate delta operators, e.g., forward and backward difference operators. We extend fundamental aspects of the theory of classical bivariate Gon\v{c}arov polynomials and univariate delta Gon\v{c}arov polynomials to the multivariate setting using umbral calculus. After introducing systems of delta operators, we define multivariate delta Gon\v{c}arov polynomials, show that the associated interpolation problem is always solvable, and derive a generating function (an Appell relation) for them. We show that systems of delta Gon\v{c}arov polynomials on an interpolation grid $Z \subseteq \mathbb{R}^d$ are of binomial type if and only if $Z = A\mathbb{N}^d$ for some $d\times d$ matrix $A$. This motivates our definition of delta Abel polynomials to be exactly those delta Gon\v{c}arov polynomials which are based on such a grid. Finally, compact formulas for delta Abel polynomials in all dimensions are given for separable systems of delta operators. This recovers a former result for classical bivariate Abel polynomials and extends previous partial results for classical trivariate Abel polynomials to all dimensions.
• ### On the commutation of generalized means on probability spaces(1503.01139)

June 29, 2016 math.CA
Let $f$ and $g$ be real-valued continuous injections defined on a non-empty real interval $I$, and let $(X, \mathscr{L}, \lambda)$ and $(Y, \mathscr{M}, \mu)$ be probability spaces in each of which there is at least one measurable set whose measure is strictly between $0$ and $1$. We say that $(f,g)$ is a $(\lambda, \mu)$-switch if, for every $\mathscr{L} \otimes \mathscr{M}$-measurable function $h: X \times Y \to \mathbf{R}$ for which $h[X\times Y]$ is contained in a compact subset of $I$, it holds $$f^{-1}\!\left(\int_X f\!\left(g^{-1}\!\left(\int_Y g \circ h\;d\mu\right)\right)d \lambda\right)\! = g^{-1}\!\left(\int_Y g\!\left(f^{-1}\!\left(\int_X f \circ h\;d\lambda\right)\right)d \mu\right)\!,$$ where $f^{-1}$ is the inverse of the corestriction of $f$ to $f[I]$, and similarly for $g^{-1}$. We prove that this notion is well-defined, by establishing that the above functional equation is well-posed (the equation can be interpreted as a permutation of generalized means and raised as a problem in the theory of decision making under uncertainty), and show that $(f,g)$ is a $(\lambda, \mu)$-switch if and only if $f = ag + b$ for some $a,b \in \mathbf R$, $a \ne 0$.
• ### Cauchy-Davenport type inequalities, I(1604.02136)

May 4, 2016 math.CO, math.NT, math.GR
Let $\mathbb G = (G, +)$ be a group (either abelian or not). Given $X, Y \subseteq G$, we denote by $\langle Y \rangle$ the subsemigroup of $\mathbb G$ generated by $Y$, and we set $$\gamma(Y) := \sup_{y_0 \in Y} \inf_{y_0 \ne y \in Y} {\rm ord}(y - y_0)$$ if $|Y| \ge 2$ and $\gamma(Y) := |Y|$ otherwise. We prove that if $\langle Y \rangle$ is commutative, $Y$ is non-empty, and $X+2Y \neq X + Y + y$ for some $y \in Y$, then $$|X+Y| \ge |X|+\min(\gamma(Y), |Y| - 1).$$ Actually, this is obtained from a more general result, which improves on previous work of the author on sumsets in cancellative semigroups, and yields a comprehensive generalization, and in some cases a considerable strengthening, of various additive theorems, notably including the Chowla-Pillai theorem (on sumsets in finite cyclic groups) and the specialization to abelian groups of the Hamidoune-Shatrowsky theorem.
• ### Plots and Their Applications - Part I: Foundations(1311.3524)

April 4, 2016 math.CT, math.CO, math.FA, math.LO
The primary goal of this paper is to abstract notions, results and constructions from the theory of categories to the broader setting of plots. Loosely speaking, a plot can be thought of as a non-associative non-unital category with a "relaxed" composition law: Besides categories, this includes as a special case graphs and neocategories in the sense of Ehresmann, Gabriel's quivers, Mitchell's semicategories, and composition graphs, precategories and semicategories in the sense of Schr\"oder. Among other things, we formulate an "identity-free" definition of isomorphisms, equivalences, and limits, for which we introduce regular representations, punctors, $\mathcal M$-connections, and $\mathcal M$-factorizations. Part of the material will be used in subsequent work to lay the foundation for an abstract theory of "normed structures" serving as a unifying framework for the development of fundamental aspects of the theory of normed spaces, normed groups, etc., on the one hand, and measure spaces, perhaps surprisingly, on the other.
• ### A unified approach to the theory of normed structures - Part I: The single-sorted case(1205.2988)

April 4, 2016 math.CT, math.FA, math.RA
We introduce the concept of a prenormed model of a particular kind of finitary single-sorted first-order theories, interpreted over a category with finite products. These are referred to as prealgebraic theories, for the fact that their signature comprises, together with arbitrary function symbols (of finite ariety), only relation symbols whose interpretation, in any possible model, is a reflexive and transitive binary relation, namely a preorder. The result is an abstract approach to the very concept of norm and, consequently, to the theory of normed structures.
• ### Generalized Goncarov polynomials(1511.04039)

Nov. 12, 2015 math.CO, math.CA
We introduce the sequence of generalized Gon\v{c}arov polynomials, which is a basis for the solutions to the Gon\v{c}arov interpolation problem with respect to a delta operator. Explicitly, a generalized Gon\v{c}arov basis is a sequence $(t_n(x))_{n \ge 0}$ of polynomials defined by the biorthogonality relation $\varepsilon_{z_i}(\mathfrak d^{i}(t_n(x))) = n! \;\! \delta_{i,n}$ for all $i,n \in \mathbf N$, where $\mathfrak d$ is a delta operator, $\mathcal Z = (z_i)_{i \ge 0}$ a sequence of scalars, and $\varepsilon_{z_i}$ the evaluation at $z_i$. We present algebraic and analytic properties of generalized Gon\v{c}arov polynomials and show that such polynomial sequences provide a natural algebraic tool for enumerating combinatorial structures with a linear constraint on their order statistics.
• ### The Davenport constant of a box(1405.4363)

Feb. 16, 2015 math.CO, math.NT
Given an additively written abelian group $G$ and a set $X\subseteq G$, we let $\mathscr{B}(X)$ denote the monoid of zero-sum sequences over $X$ and $\mathsf{D}(X)$ the Davenport constant of $\mathscr{B}(X)$, namely the supremum of the positive integers $n$ for which there exists a sequence $x_1 \cdots x_n$ of $\mathscr{B}(X)$ such that $\sum_{i \in I} x_i \ne 0$ for each non-empty proper subset $I$ of $\{1, \ldots, n\}$. In this paper, we mainly investigate the case when $G$ is a power of $\mathbb{Z}$ and $X$ is a box (i.e., a product of intervals of $G$). Some mixed sets (e.g., the product of a group by a box) are studied too, and some inverse results are obtained.
• ### Sums of dilates in ordered groups(1403.0934)

Feb. 16, 2015 math.CO, math.NT, math.GR
We address the "sums of dilates problem" by looking for non-trivial lower bounds on sumsets of the form $k \cdot X + l \cdot X$, where $k$ and $l$ are non-zero integers and $X$ is a subset of a possibly non-abelian group $G$ (written additively). In particular, we investigate the extension of some results so far known only for the integers to the context of torsion-free or linearly orderable groups, either abelian or not.
• ### Cauchy-Davenport type theorems for semigroups(1307.8396)

Jan. 30, 2015 math.CO, math.NT, math.GR
Let $\mathbb{A} = (A, +)$ be a (possibly non-commutative) semigroup. For $Z \subseteq A$ we define $Z^\times := Z \cap \mathbb A^\times$, where $\mathbb A^\times$ is the set of the units of $\mathbb{A}$, and $$\gamma(Z) := \sup_{z_0 \in Z^\times} \inf_{z_0 \ne z \in Z} {\rm ord}(z - z_0).$$ The paper investigates some properties of $\gamma(\cdot)$ and shows the following extension of the Cauchy-Davenport theorem: If $\mathbb A$ is cancellative and $X, Y \subseteq A$, then $$|X+Y| \ge \min(\gamma(X+Y),|X| + |Y| - 1).$$ This implies a generalization of Kemperman's inequality for torsion-free groups and strengthens another extension of the Cauchy-Davenport theorem, where $\mathbb{A}$ is a group and $\gamma(X+Y)$ in the above is replaced by the infimum of $|S|$ as $S$ ranges over the non-trivial subgroups of $\mathbb{A}$ (Hamidoune-K\'arolyi theorem).
• ### On a system of equations with primes(1212.0802)

May 13, 2014 math.NT
Given an integer $n \ge 3$, let $u_1, \ldots, u_n$ be pairwise coprime integers $\ge 2$, $\mathcal D$ a family of nonempty proper subsets of $\{1, \ldots, n\}$ with "enough" elements, and $\varepsilon$ a function $\mathcal D \to \{\pm 1\}$. Does there exist at least one prime $q$ such that $q$ divides $\prod_{i \in I} u_i - \varepsilon(I)$ for some $I \in \mathcal D$, but it does not divide $u_1 \cdots u_n$? We answer this question in the positive when the $u_i$ are prime powers and $\varepsilon$ and $\mathcal D$ are subjected to certain restrictions. We use the result to prove that, if $\varepsilon_0 \in \{\pm 1\}$ and $A$ is a set of three or more primes that contains all prime divisors of any number of the form $\prod_{p \in B} p - \varepsilon_0$ for which $B$ is a finite nonempty proper subset of $A$, then $A$ contains all the primes.
• ### Small doubling in ordered semigroups(1208.3233)

April 10, 2014 math.CO, math.GR
Let $\mathbb{A} = (A, \cdot)$ be a semigroup. We generalize some recent results by G. A. Freiman, M. Herzog and coauthors on the structure theory of set addition from the context of linearly orderable groups to linearly orderable semigroups, where we say that $\mathbb{A}$ is linearly orderable if there exists a total order $\le$ on $A$ such that $xz < yz$ and $zx < zy$ for all $x,y,z \in A$ with $x < y$. In particular, we find that if $S$ is a finite subset of $A$ generating a non-abelian subsemigroup of $\mathbb{A}$, then $|S^2| \ge 3|S|-2$. On the road to this goal, we also prove a number of subsidiary results, and most notably that for $S$ a finite subset of $A$ the commutator and the normalizer of $S$ are equal to each other.
• ### A Cauchy-Davenport theorem for semigroups(1210.4203)

Sept. 19, 2013 math.CO, math.GR
We generalize the Davenport transform and use it to prove that, for a (possibly non-commutative) cancellative semigroup $\mathbb A = (A, +)$ and non-empty subsets $X,Y$ of $A$ such that the subsemigroup generated by $Y$ is commutative, we have $|X + Y| \ge \min(\omega(Y), |X| + |Y| - 1)$, where $\omega(Y) := \sup_{y_0 \in Y \cap \mathbb A^{\times}} \inf_{y \in Y \setminus \{y_0\}} |<y - y_0>|$. This carries over the Cauchy-Davenport theorem to the broader setting of semigroups, and it implies, in particular, an extension of I. Chowla's and S.S. Pillai's theorems for cyclic groups and a notable strengthening of another generalization of the same Cauchy-Davenport theorem to commutative groups, where $\omega(Y)$ in the above is replaced by the minimal order of the non-trivial subgroups of $\mathbb A$.
• ### On the divisibility of $a^n \pm b^n$ by powers of $n$(1301.0131)

Sept. 3, 2013 math.NT
We determine all triples $(a,b,n)$ of positive integers such that $a$ and $b$ are relatively prime and $n^k$ divides $a^n + b^n$ (respectively, $a^n - b^n$), when $k$ is the maximum of $a$ and $b$ (in fact, we answer a slightly more general question). As a by-product, it is found that, for $m, n \in \mathbb N^+$ with $n \ge 2$, $n^m$ divides $m^n + 1$ if and only if $(m,n)=(2,3)$ or $(1,2)$, which generalizes problems from the 1990 and 1999 editions of the International Mathematical Olympiad. The results are related to a conjecture by K. Gy\H{o}ry and C. Smyth on the finiteness of the sets $R_k^\pm(a,b) := \{n \in \mathbb N^+: n^k \mid a^n \pm b^n\}$, when $a,b,k$ are fixed integers with $k \ge 3$, $\gcd(a,b) = 1$ and $|ab| \ge 2$.