BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Melvyn B. Nathanson

Melvyn B. Nathanson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NTmath.COmath.ACmath.AGmath.GRmath.HOmath.MGmath.QAmath.NANumerical Analysis

Catalog footprint

What is connected

77works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

77 published item(s)

preprint2026arXiv

Sumset size races for measurable sets

Let $G$ be a locally compact abelian group with Haar measure $μ$. For integers $n \geq 2$ and $H \geq 2$ and for any $n$-tuples $\mathbf{u}_1,\ldots, \mathbf{u}_H \in \mathbf{N}^n$, there exist measurable subsets $A_1,\ldots, A_n$ of $G$ such that the $n$-tuple $\left( μ(hA_1),\ldots, μ(hA_n) \right)$ has the same relative order as the $n$-tuple $\mathbf{u}_h$ for all $h = 1,\ldots, H$. For integers $m_{i,h}$ for $i =1,\ldots, n-1$ and $h = 1,\ldots, H$, there are Lebesgue measurable sets $A_1,\ldots, A_n$ in $\mathbf{R}$ such that $μ(hA_{i+1}) - μ(hA_i) = m_{i,h}$ for all $i$ and $h$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Exponential automorphisms and a problem of Mycielski

An exponential automorphism of $\mathbf{C}$ is a function $α: \mathbf{C} \rightarrow \mathbf{C}$ such that $α(z_1 + z_2) = α(z_1) + α(z_2)$ and $α\left( e^z \right) = e^{α(z)}$ for all $z, z_1, z_2 \in \mathbf{C}$. Jan Mycielski asked if $α(\ln 2) = \ln 2$ and if $α(2^{1/k}) = 2^{1/k}$ for $k = 2, 3, 4$ and for all exponential automorphisms $α$. These questions are answered modulo a multiple of $2πi$ and a root of unity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multiplicative representations of integers and Ramsey's theorem

Let $\mathcal{B} = (B_1,\ldots, B_h)$ be an $h$-tuple of sets of positive integers. Let $g_{\mathcal{B} }(n)$ count the number of representations of $n$ in the form $n = b_1\cdots b_h$, where $b_i \in B_i$ for all $i \in \{1,\ldots, h\}$. It is proved that $\liminf_{n\rightarrow \infty} g_{\mathcal{B} }(n) \geq 2$ implies $\limsup_{n\rightarrow \infty} g_{\mathcal{B} }(n) = \infty$.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Comparison estimates for linear forms in additive number theory

Let $R$ be a commutative ring $R$ with $1_R$ and with group of units $R^{\times}$. Let $Φ= Φ(t_1,\ldots, t_h) = \sum_{i=1}^h φ_it_i$ be an $h$-ary linear form with nonzero coefficients $φ_1,\ldots, φ_h \in R$. Let $M$ be an $R$-module. For every subset $A$ of $M$, the image of $A$ under $Φ$ is \[ Φ(A) = \{ Φ(a_1,\ldots, a_h) : (a_1,\ldots, a_h) \in A^h \}. \] For every subset $I$ of $\{1,2,\ldots, h\}$, there is the subset sum $ s_I = \sum_{i\in I} φ_i. $ Let $ \mathcal{S} (Φ) = \{s_I: \emptyset \neq I \subseteq \{1,2,\ldots, h\} \}. $ Theorem. Let $Υ(t_1,\ldots, t_g) = \sum_{i=1}^g \upsilon_it_i$ and $Φ(t_1,\ldots, t_h) = \sum_{i=1}^h φ_it_i$ be linear forms with nonzero coefficients in the ring $R$. If $\{0, 1\} \subseteq \mathcal{S} (Υ)$ and $\mathcal{S} (Φ) \subseteq R^{\times}$, then for every $\varepsilon > 0$ and $c > 1$ there exist a finite $R$-module $M$ with $|M| > c$ and a subset $A$ of $M$ such that $Υ(A \cup \{0\}) = M$ and $|Φ(A)| < \varepsilon |M|$.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Limits and decomposition of de Bruijn's additive systems

An additive system for the nonnegative integers is a family (A_i)_{i\in I} of sets of nonnegative integers with 0 \in A_i for all i \in I such that every nonnegative integer can be written uniquely in the form \sum_{i\in I} a_i with a_i \in A_i for all i and a_i \neq 0 for only finitely many i. In 1956, de Bruijn proved that every additive system is constructed from an infinite sequence (g_i)_{i \in \N} of integers with g_i \geq 2 for all i, or is a contraction of such a system. This paper gives a complete classification of the "uncontractable" or "indecomposable" additive systems, and also considers limits and stability of additive systems.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

MSTD sets and Freiman isomorphisms

An MSTD set is a finite set with more pairwise sums than differences. $(Υ,Φ)$-ismorphisms are generalizations of Freiman isomorphisms to arbitrary linear forms. These generalized isomorphisms are used to prove that every finite set of real numbers is Freiman isomorphic to a finite set of integers. This implies that there exists no MSTD set $A$ of real numbers with $|A| \leq 7$, and, up to Freiman isomorphism, there exists exactly one MSTD set $A$ of real numbers with $|A| = 8$.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Trapezoidal numbers, divisor functions, and a partition theorem of Sylvester

A partition of a positive integer $n$ is a representation of $n$ as a sum of a finite number of positive integers (called parts). A trapezoidal number is a positive integer that has a partition whose parts are a decreasing sequence of consecutive integers, or, more generally, whose parts form a finite arithmetic progression. This paper reviews the relation between trapezoidal numbers, partitions, and the set of divisors of a positive integer. There is also a complete proof of a theorem of Sylvester that produces a stratification of the partitions of an integer into odd parts and partitions into disjoint trapezoids.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Weighted real Egyptian numbers

Let $\mathcal A = (A_1,\ldots, A_n)$ be a sequence of nonempty finite sets of positive real numbers, and let $\mathcal{B} = (B_1,\ldots, B_n)$ be a sequence of infinite discrete sets of positive real numbers. A weighted real Egyptian number with numerators $\mathcal{A}$ and denominators $\mathcal{B}$ is a real number $c$ that can be represented in the form \[ c = \sum_{i=1}^n \frac{a_i}{b_i} \] with $a_i \in A_i$ and $b_i \in B_i$ for $i \in \{1,\ldots, n\}$. In this paper, classical results of Sierpinski for Egyptian fractions are extended to the set of weighted real Egyptian numbers.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Commutative algebra and the linear diophantine problem of Frobenius

Let $A$ be a finite set of relatively prime positive integers, and let $S(A)$ be the set of all nonnegative integral linear combinations of elements of $A$. The set $S(A)$ is a semigroup that contains all sufficiently large integers. The largest integer not in $S(A)$ is the Frobenius number of $A$, and the number of positive integers not in $S(A)$ is the genus of $A$. Sharp and Sylvester proved in 1884 that the Frobenius number of the set $A = \{a,b\}$ is $ab-a-b$, and that the genus of $A$ is $(a-1)(b-1)/2$. Graded rings and a simple form of Hilbert's syzygy theorem are used to give a commutative algebra proof of this result.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Every finite set of integers is an asymptotic approximate group

A set $A$ is an $(r,\ell)$-approximate group in the additive abelian group $G$ if $A$ is a nonempty subset of $G$ and there exists a subset $X$ of $G$ such that $|X| \leq \ell$ and $rA \subseteq X+A$. The set $A$ is an asymptotic $(r,\ell)$-approximate group if the sumset $hA$ is an $(r,\ell)$-approximate group for all sufficiently large integers $h$. It is proved that every finite set of integers is an asymptotic $(r,r+1)$-approximate group for every integer $r \geq 2$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Every finite subset of an abelian group is an asymptotic approximate group

If $A$ is a nonempty subset of an additive group $G$, then the $h$-fold sumset is \[ hA = \{x_1 + \cdots + x_h : x_i \in A_i \text{ for } i=1,2,\ldots, h\}. \] The set $A$ is an $(r,\ell)$-approximate group in $G$ if $A$ is a nonempty subset of a group $G$ and there exists a subset $X$ of $G$ such that $|X| \leq \ell$ and $rA \subseteq XA$. We do not assume that $A$ contains the identity, nor that $A$ is symmetric, nor that $A$ is finite. The set $A$ is an asymptotic $(r,\ell)$-approximate group if the sumset $hA$ is an $(r,\ell)$-approximate group for all sufficiently large $h$. It is proved that every polytope in a real vector space is an asymptotic $(r,\ell)$-approximate group, that every finite set of lattice points is an asymptotic $(r,\ell)$-approximate group, and that every finite subset of an abelian group is an asymptotic $(r,\ell)$-approximate group.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Haight-Ruzsa method for sets with more differences than multiple sums

Let $h$ be a positive integer and let $\varepsilon > 0$. The Haight-Ruzsa method produces a positive integer $m^*$ and a subset $A$ of the additive abelian group $\mathbf{Z}/m^*\mathbf{Z}$ such that the difference set is large in the sense that $A-A = \mathbf{Z}/m^*\mathbf{Z}$ and $h$-fold sumset is small in the sense that $|hA| < \varepsilon m^*$. This note describes, and in a modest way extends, the Haight-Ruzsa argument, and constructs sets with more differences than multiple sums in other additive abelian groups.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Cantor polynomials and the Fueter-Polya theorem

A packing polynomial is a polynomial that maps the set $\mathbf{N}_0^2$ of lattice points with nonnegative coordinates bijectively onto $\mathbf{N}_0$. Cantor constructed two quadratic packing polynomials, and Fueter and Polya proved analytically that the Cantor polynomials are the only quadratic packing polynomials. The purpose of this paper is to present a beautiful elementary proof of Vsemirnov of the Fueter-Polya theorem. It is a century-old conjecture that t

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Free monoids and forests of rational numbers

The Calkin-Wilf tree is an infinite binary tree whose vertices are the positive rational numbers. Each such number occurs in the tree exactly once and in the form $a/b$, where are $a$ and $b$ are relatively prime positive integers. This tree is associated with the matrices $L_1 = \left( \begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix} \right)$ and $R_1 = \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$, which freely generate the monoid $SL_2(\mathbf{N}_0)$ of $2 \times 2$ matrices with determinant 1 and nonnegative integral coordinates. For other pairs of matrices $L_u$ and $R_v$ that freely generate submonoids of $GL_2(\mathbf{N}_0)$, there are forests of infinitely many rooted infinite binary trees that partition the set of positive rational numbers, and possess a remarkable symmetry property.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Sums of sets of lattice points and unimodular coverings of polytopes

If $P$ is a lattice polytope (that is, the convex hull of a finite set of lattice points in $\mathbf{R}^n$), then every sum of $h$ lattice points in $P$ is a lattice point in the $h$-fold sumset $hP$. However, a lattice point in the $h$-fold sumset $hP$ is not necessarily the sum of $h$ lattice points in $P$. It is proved that if the polytope $P$ is a union of unimodular simplices, then every lattice point in the $h$-fold sumset $hP$ is the sum of $h$ lattice points in $P$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A forest of linear fractional transformations

The Calkin-Wilf tree is an infinite binary tree whose vertices are the positive rational numbers. Each number occurs in the tree exactly once and in the form $a/b$, where are $a$ and $b$ are relatively prime positive integers. For every $2\times 2$ matrix with nonnegative integral coordinates and nonzero determinant, it is possible to construct an analogous tree with this root. If the root is the identity matrix, then the tree consists all matrices with determinant 1, and this tree possesses the basic properties of the Calkin-Wilf tree of positive rational numbers. The set of all matrices with nonzero determinant decomposes into a forest of rooted infinite binary trees.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A problem of Rankin on sets without geometric progressions

A geometric progression of length $k$ and integer ratio is a set of numbers of the form $\{a,ar,\dots,ar^{k-1}\}$ for some positive real number $a$ and integer $r\geq 2$. For each integer $k \geq 3$, a greedy algorithm is used to construct a strictly decreasing sequence $(a_i)_{i=1}^{\infty}$ of positive real numbers with $a_1 = 1$ such that the set \[ G^{(k)} = \bigcup_{i=1}^{\infty} \left(a_{2i} , a_{2i-1} \right] \] contains no geometric progression of length $k$ and integer ratio. Moreover, $G^{(k)}$ is a maximal subset of $(0,1]$ that contains no geometric progression of length $k$ and integer ratio. It is also proved that there is a strictly increasing sequence $(A_i)_{i=1}^{\infty}$ of positive integers with $A_1 = 1$ such that $a_i = 1/A_i$ for all $i = 1,2,3,\ldots$. The set $G^{(k)}$ gives a new lower bound for the maximum cardinality of a subset of the set of integers $\{1,2,\dots,n\}$ that contains no geometric progression of length $k$ and integer ratio.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Forests of Gaussian numbers

The Calkin-Wilf tree is an infinite binary tree whose vertices are the positive rational numbers. Each number occurs in the tree exactly once and in the form $a/b$, where are $a$ and $b$ are relatively prime positive integers. In this paper, certain subsemigroups of the modular group are used to construct similar trees in the set $\mathcal{D}_0$ of positive complex numbers. Associated to each semigroup is a forest of trees that partitions $\mathcal{D}_0$. The set of cusps and the fundamental domain of the semigroup are defined and computed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Additive systems and a theorem of de Bruijn

This paper gives a complete proof of a theorem of de Bruijn that classifies additive systems for the nonnegative integers, that is, families $\mca = (A_i)_{i\in I}$ of sets of nonnegative integers, each set containing 0, such that every nonnegative integer can be written uniquely in the form $\sum_{i\in I} a_i$ with $a_i \in A_i$ for all $i$ and $a_i \neq 0$ for only finitely many $i$. All indecomposable additive systems are determined.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Cantor polynomials for semigroup sectors

A packing function on a set Omega in R^n is a one-to-one correspondence between the set of lattice points in Omega and the set N_0 of nonnegative integers. It is proved that if r and s are relatively prime positive integers such that r divides s-1, then there exist two distinct quadratic packing polynomials on the sector {(x,y) \in \R^2 : 0 \leq y \leq rx/s}. For the rational numbers 1/s, these are the unique quadratic packing polynomials. Moreover, quadratic quasi-polynomial packing functions are constructed for all rational sectors.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Growth polynomials for additive quadruples and $(h,k)$-tuples

Consider the interval of integers $I_{m,n} = \{m, m+1, m+2,\ldots, m+n-1 \}$. For fixed integers $h,k,m$, and $c$, let $Φ_{h,k,m}^{(c)}(n)$ denote the number of solutions of the equation $(a_1+\cdots + a_h)- (a_{h+1} + \cdots + a_{h+k})=c$ with $a_i \in I_{m,n}$ for all $i=1,\ldots, h+k$. This is a polynomial in $n$ for all sufficiently large $n$, and the growth polynomial is constructed explicitly.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Irrational numbers associated to sequences without geometric progressions

Let s and k be integers with s \geq 2 and k \geq 2. Let g_k^{(s)}(n) denote the cardinality of the largest subset of the set {1,2,..., n} that contains no geometric progression of length k whose common ratio is a power of s. Let r_k(\ell) denote the cardinality of the largest subset of the set {0,1,2,\ldots, \ell -1\} that contains no arithmetric progression of length k. The limit \[ \lim_{n\rightarrow \infty} \frac{g_k^{(s)}(n)}{n} = (s-1) \sum_{m=1}^{\infty} \left(\frac{1}{s} \right)^{\min \left(r_k^{-1}(m)\right)} \] exists and converges to an irrational number.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the fractional parts of roots of positive real numbers

Let [θ] denote the integer part and θ the fractional part of the real number θ. For θ> 1 and {θ^{1/n}} \neq 0, define M_θ(n) = [1/{θ^{1/n}}]. The arithmetic function M_θ(n) is eventually increasing, and \lim_{n\rightarrow \infty} M_θ(n)/n = 1/\log θ. Moreover, M_θ(n) is "linearly periodic" if and only if \log θis rational. Other results and problems concerning the function M_θ(n) are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Geometric group theory and arithmetic diameter

Let X be a group with identity e, let A be an infinite set of generators for X, and let (X,d_A) be the metric space with the word metric d_A induced by A. If the diameter of the space is infinite, then for every positive integer h there are infinitely many elements x in X with d_A(e,x)=h. It is proved that if P is a nonempty finite set of prime numbers and A is the set of positive integers whose prime factors all belong to P, then the diameter of the metric space (\Z,d_A) is infinite. Let λ_A(h) denote the smallest positive integer x with d_A(e,x)=h. It is an open problem to compute λ_A(h) and estimate its growth rate.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On a partition problem of Canfield and Wilf

Let A and M be nonempty sets of positive integers. A partition of the positive integer n with parts in A and multiplicities in M is a representation of n in the form n = \sum_{a\in A} m_a a, where m_a is in M U {0} for all a in A, and m_a is in M for only finitely many a. Denote by p_{A,M}(n) the number of partitions of n with parts in A and multiplicities in M. It is proved that there exist infinite sets A and M of positive integers whose partition function p_{A,M} has weakly superpolynomial but not superpolynomial growth. The counting function of the set A is A(x) = \sum_{a \in A, a\leq x} 1. It is also proved that p_{A,M} must have at least weakly superpolynomial growth if M is infinite and A(x) >> log x.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Bi-Lipschitz equivalent metrics on groups, and a problem in additive number theory

There is a standard "word length" metric canonically associated to any set of generators for a group. In particular, for any integers a and b greater than 1, the additive group of integers has generating sets {a^i}_{i=0}^{\infty} and {b^j}_{j=0}^{\infty} with associated metrics d_A and d_B, respectively. It is proved that these metrics are bi-Lipschitz equivalent if and only if there exist positive integers m and n such that a^m = b^n.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Shatrovskii's construction of thin bases

The set A of nonnegative integers is called a basis of order h if every nonnegative integer can be represented as the sum of exactly h not necessarily distinct elements of A. An additive basis A of order h is called thin if there exists c > 0 such that the number of elements of A not exceeding x is less than cx^{1/h} for all x > 0. This paper describes a construction of Shatrovskii of thin bases of order h.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Phase transitions in infinitely generated groups, and related problems in additive number theory

Let A be an infinite set of generators for a group G, and let L_A(r) denote the number of elements of G whose word length with respect to A is exactly r. The purpose of this note is to determine all growth functions L_A(r) associated to infinite generating sets for groups, and to describe a phase transition phenomenon associated with infinite generating sets. A list of open problems is also.included.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Supersequences, rearrangements of sequences, and the spectrum of bases in additive number theory

The set A = {a_n} of nonnegative integers is an asymptotic basis of order h if every sufficiently large integer can be represented as the sum of h elements of A. If a_n ~ alpha n^h for some real number alpha > 0, then alpha is called an additive eigenvalue of order h. The additive spectrum of order h is the set N(h) consisting of all additive eigenvalues of order h. It is proved that there is a positive number eta_h <= 1/h! such that N(h) = (0, eta_h) or N(h) = (0, eta_h]. The proof uses results about the construction of supersequences of sequences with prescribed asymptotic growth, and also about the asymptotics of rearrangements of infinite sequences. For example, it is proved that there does not exist a strictly increasing sequence of integers B = {b_n} such that b_n ~ 2^n and B contains a subsequence {b_{n_k}} such that b_{n_k} ~ 3^k.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Asymptotic estimates for phi functions for subsets of {m+1, m+2,...,n}

Let f(m,n) denote the number of relatively prime subsets of {m+1,m+2,...,n}, and let Phi(m,n) denote the number of subsets A of {m+1,m+2,...,n} such that gcd(A) is relatively prime to n. Let f_k(m,n) and Phi_k(m,n) be the analogous counting functions restricted to sets of cardinality k. Simple explicit formulas and asymptotic estimates are obtained for these four functions.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Binary linear forms over finite sets of integers

Let A be a finite set of integers. For a polynomial f(x_1,...,x_n) with integer coefficients, let f(A) = {f(a_1,...,a_n) : a_1,...,a_n \in A}. In this paper it is proved that for every pair of normalized binary linear forms f(x,y)=u_1x+v_1y and g(x,y)=u_2x+v_2y with integral coefficients, there exist arbitrarily large finite sets of integers A and B such that |f(A)| > |g(A)| and |f(B)| < |g(B)|.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Dense sets of integers with prescribed representation functions

Let A be a set of integers and let h \geq 2. For every integer n, let r_{A, h}(n) denote the number of representations of n in the form n=a_1+...+a_h, where a_1,...,a_h belong to the set A, and a_1\leq ... \leq a_h. The function r_{A,h} from the integers Z to the nonnegative integers N_0 U {\infty} is called the representation function of order h for the set A. We prove that every function f from Z to N_0 U {\infty} satisfying liminf_{|n|->\infty} f (n)\geq g is the representation function of order h for some sequence A of integers, and that A can be constructed so that it increases "almost" as slowly as any given B_h[g] sequence. In particular, for every epsilon >0 and g \geq g(h,epsilon), we can construct a sequence A satisfying r_{A,h}=f and A(x)\gg x^{(1/h)-epsilon}.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Heights in finite projective space, and a problem on directed graphs

Let $\F_p = \Z/p\Z$. The \emph{height} of a point $\mathbf{a}=(a_1,..., a_d) \in \F_p^d$ is $h_p(\mathbf{a}) = \min \left\{\sum_{i=1}^d (ka_i \mod p) : k=1,...,p-1\right\}.$ Explicit formulas and estimates are obtained for the values of the height function in the case $d=2,$ and these results are applied to the problem of determining the minimum number of edges the must be deleted from a finite directed graph so that the resulting subgraph is acyclic.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Inverse problems for linear forms over finite sets of integers

Let f(x_1,x_2,...,x_m) = u_1x_1+u_2 x_2+... + u_mx_m be a linear form with positive integer coefficients, and let N_f(k) = min{|f(A)| : A \subseteq Z and |A|=k}. A minimizing k-set for f is a set A such that |A|=k and |f(A)| = N_f(k). A finite sequence (u_1, u_2,...,u_m) of positive integers is called complete if {\sum_{j\in J} u_j : J \subseteq {1,2,..,m}} = {0,1,2,..., U}, where $U = \sum_{j=1}^m u_j.$ It is proved that if f is an m-ary linear form whose coefficient sequence (u_1,...,u_m) is complete, then N_f(k) = Uk-U+1 and the minimizing k-sets are precisely the arithmetic progressions of length k. Other extremal results on linear forms over finite sets of integers are obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Inverse Problems for Representation Functions in Additive Number Theory

For every positive integer h, the representation function of order h associated to a subset A of the integers or, more generally, of any group or semigroup X, counts the number of ways an element of X can be written as the sum (or product, if X is nonabelian) of h not necessarily distinct elements of X. The direct problem for representation functions in additive number theory begins with a subset A of X and seeks to understand its representation functions. The inverse problem for representation functions starts with a function f:X ->N_0 U {\infty} and asks if there is a set A whose representation function is f, and, if the answer is yes, to classify all such sets. This paper is a survey of recent progress on the inverse representation problem.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Representation functions of bases for binary linear forms

Let F(x_1,...,x_m) = u_1 x_1 + ... + u_m x_m be a linear form with nonzero, relatively prime integer coefficients u_1,..., u_m. For any set A of integers, let F(A) = {F(a_1,...,a_m) : a_i in A for i=1,...,m}. The representation function associated with the form F is R_{A,F}(n) = card {(a_1,...,a_m) in A^m: F(a_1,..., a_m) = n}. The set A is a basis with respect to F for almost all integers the set Z\F(A) has asymptotic density zero. Equivalently, the representation function of an asymptotic basis is a function f:Z -> N_0 U {\infty} such that f^{-1}(0) has density zero. Given such a function, the inverse problem for bases is to construct a set A whose representation function is f. In this paper the inverse problem is solved for binary linear forms.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Sums of products of congruence classes and of arithmetic progressions

Consider the congruence class R_m(a)={a+im:i\in Z} and the infinite arithmetic progression P_m(a)={a+im:i\in N_0}. For positive integers a,b,c,d,m the sum of products set R_m(a)R_m(b)+R_m(c)R_m(d) consists of all integers of the form (a+im)(b+jm)+(c+km)(d+\ell m) for some i,j,k,\ell\in Z. It is proved that if gcd(a,b,c,d,m)=1, then R_m(a)R_m(b)+R_m(c)R_m(d) is equal to the congruence class R_m(ab+cd), and that the sum of products set P_m(a)P_m(b)+P_m(c)P_m(d) eventually coincides with the infinite arithmetic progression P_m(ab+cd).

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Perfect difference sets constructed from Sidon sets

A set A of positive integers is called a perfect difference set if every nonzero integer has an unique representation as the difference of two elements of A. We construct dense perfect difference sets from dense Sidon sets. As a consequence of this new approach, we prove that there exists a perfect difference set A such that A(x) >> x^{\sqrt{2}-1-o(1)}. We also prove that there exists a perfect difference set A such that limsup_{x\to \infty}A(x)/\sqrt x\geq 1/\sqrt 2.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

The Caccetta-Haggkvist conjecture and additive number theory

The Caccetta-Haggkvist conjecture states that if G is a finite directed graph with at least n/k edges going out of each vertex, then G contains a directed cycle of length at most k. Hamidoune used methods and results from additive number theory to prove the conjecture for Cayley graphs and for vertex-transitive graphs. This expository paper contains a survey of results on the Caccetta-Haggkvist conjecture, and complete proofs of the conjecture in the case of Cayley and vertex-transitive graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Quadratic addition rules for quantum integers

For every positive integer $n$, the quantum integer $[n]_q$ is the polynomial $[n]_q = 1 + q + q^2 + ... + q^{n-1}.$ A quadratic addition rule for quantum integers consists of sequences of polynomials $\mathcal{R}' = \{r'_n(q)\}_{n=1}^{\infty}$, $\mathcal{S}' = \{s'_n(q)\}_{n=1}^{\infty}$, and $\mathcal{T}' = \{t'_{m,n}(q)\}_{m,n=1}^{\infty}$ such that $[m+n]_q = r'_n(q)[m]_q + s'_m(q)[n]_q + t'_{m,n}(q)[m]_q[n]_q$ for all $m$ and $n.$ This paper gives a complete classification of quadratic addition rules, and also considers sequences of polynomials \polf that satisfy the associated functional equation $f_{m+n}(q)= r'_n(q)f_m(q) + s'_m(q)f_n(q) + t'_{m,n}f_m(q)f_n(q).$

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Representation functions of additive bases for abelian semigroups

Let X = S \oplus G, where S is a countable abelian semigroup and G is a countably infinite abelian group such that {2g : g in G} is infinite. Let pi: X \to G be the projection map defined by pi(s,g) = g for all x =(s,g) in X. Let f:X \to N_0 cup infty be any map such that the set pi(f^{-1}(0)) is a finite subset of G. Then there exists a set B contained in X such that r_B(x) = f(x) for all x in X, where the representation function r_B(x) counts the number of sets {x',x''} contained in B such that x' \neq x'' and x'+x''=x. In particular, every function f from the integers Z into N_0 \cup infty such that f^{-1}(0) is finite is the representation function of an asymptotic basis for Z.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

A functional equation arising from multiplication of quantum integers

For the quantum integer $[n]_q = 1+q+...+q^{n-1}$ there is a natural polynomial multiplication $*_q$ such that $[m]_q *_q [n]_q = [mn]_q$. This multiplication leads to the functional equation $f_{mn}(q) = f_m(q)f_n(q^m),$ defined on a given sequence $\mathcal(F)=\{f_n(q)\}_{n=1}^{\infty}$ of polynomials. This paper contains various results concerning the classification and construction of polynomial sequences that satisfy the functional equation, as well as a list of open problems that arise fromthe classification.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

Every function is the representation function of an additive basis for the integers

Let A be a set of integers. For every integer n, let r_{A,h}(n) denote the number of representations of n in the form n = a_1 + a_2 + ... + a_h, where a_1, a_2,...,a_h are in A and a_1 \leq a_2 \leq ... \leq a_h. The function r_{A,h}: Z \to N_0 \cup \infty is the representation function of order h for A. The set A is called an asymptotic basis of order h if r_{A,h}^{-1}(0) is finite, that is, if every integer with at most a finite number of exceptions can be represented as the sum of exactly h not necessarily distinct elements of A. It is proved that every function is a representation function, that is, if f: Z \to N_0 \cup \infty is any function such that f^{-1}(0) is finite, then there exists a set A of integers such that f(n) = r_{A,h}(n) for all n in Z. Moreover, the set A can be arbitrarily sparse in the sense that, if ϕ(x) \to \infty, then there exists a set A with f(n) = r_{A,h}(n) such that card{a in A : |a| \leq x} < ϕ(x) for all sufficiently large x.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

Formal power series arising from multiplication of quantum integers

For the quantum integer [n]_q = 1+q+q^2+... + q^{n-1} there is a natural polynomial multiplication such that [mn]_q = [m]_q \otimes_q [n]_q. This multiplication is given by the functional equation f_{mn}(q) = f_m(q) f_n(q^m), defined on a sequence {f_n(q)} of polynomials such that f_n(0)=1 for all n. It is proved that if {f_n(q)} is a solution of this functional equation, then the sequence {f_n(q)} converges to a formal power series F(q). Quantum mulitplication also leads to the functional equation f(q)F(q^m) = F(q), where f(q) is a fixed polynomial or formal power series with constant term f(0)=1, and F(q)=1+\sum_{k=1}^{\infty}b_kq^k is a formal power series. It is proved that this functional equation has a unique solution F(q) for every polynomial or formal power series f(q). If the degree of f(q)is at most m-1, then there is an explicit formula for the coefficients b_k of F(q) in terms of the coefficients of f(q) and the m-adic representation of k. The paper also contains a review of convergence properties of formal power series with coefficients in an arbitrary field or integeral domain.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

Generalized additive bases, Konig's lemma, and the Erdos-Turan conjecture

Let A be a set of nonnegative integers. For every nonnegative integer n and positive integer h, let r_{A}(n,h) denote the number of representations of n in the form n = a_1 + a_2 + ... + a_h, where a_1, a_2,..., a_h are elements of A and a_1 \leq a_2 \leq ... \leq a_h. The infinite set A is called a basis of order h if r_{A}(n,h) \geq 1 for every nonnegative integer n. Erdos and Turan conjectured that limsup_{n\to\infty} r_A(n,2) = \infty for every basis A of order 2. This paper introduces a new class of additive bases and a general additive problem, a special case of which is the Erdos-Turan conjecture. Konig's lemma on the existence of infinite paths in certain graphs is used to prove that this general problem is equivalent to a related problem about finite sets of nonnegative integers.

0 citations0 reviewsNo code linkedOpen access
preprint2003arXiv

On the ubiquity of Sidon sets

A Sidon set is a set A of integers such that no integer has two essentially distinct representations as the sum of two elements of A. More generally, for every positive integer g, a B_2[g]-set is a set A of integers such that no integer has more than g essentially distinct representations as the sum of two elements of A. It is proved that almost all small sumsets of {1,2,...,n} are B_2[g]-sets, in the sense that if B_2[g](k,n) denotes the number of B_2[g]-sets of cardinality k contained in the interval {1,2,...,n}, then lim_{n\to\infty} B_2[g](k,n)/\binom{n}{k} = 1 if k = o(n^{g/(2g+2)}).

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

Polynomial growth of sumsets in abelian semigroups

Let S be an abelian semigroup, and A a finite subset of S. The sumset hA consists of all sums of h elements of A, with repetitions allowed. Let |hA| denote the cardinality of hA. Elementary lattice point arguments are used to prove that an arbitrary abelian semigroup has polynomial growth, that is, there exists a polynomial p(t) such that |hA| = p(h) for all sufficiently large h. Lattice point counting is also used to prove that sumsets of the form h_1A_1 + >... + h_rA_r have multivariate polynomial growth.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

Growth of sumsets in abelian semigroups

Let S be an abelian semigroup, written additively. Let A be a finite subset of S. We denote the cardinality of A by |A|. For any positive integer h, the sumset hA is the set of all sums of h not necessarily distinct elements of A. We define 0A = {0}. If A_1,...,A_r, and B are finite sumsets of A and h_1,...,h_r are nonnegative integers, the sumset h_1A + ... + h_rA_r + B is the set of all elements of S that can be represented in the form u_1 + ... + u_r + b, where u_i \in h_iA_i and b \in B. The growth function of this sumset is γ(h_1,...,h_r) = |h_1A + ... + h_rA_r + B|. Applying the Hilbert function for graded modules over graded algebras, where the grading is over the semigroup of r-tuples of nonnegative integers, we prove that there is a polynomial p(t_1,...,t_r) such that γ(h_1,...,h_r) = p(t_1,...,t_r) if min(h_1,...,h_r) is sufficienlty large.

0 citations0 reviewsNo code linkedOpen access