2007/12/28 by Peter Hegarty, Hegarty, Peter
Computer Science · Mathematics · #Digital Image Processing Techniques #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #math.NT #msc:11B05 #msc:11B13 #msc:11B34
paper · pdf · doi:10.48550/arxiv.0712.4399
15 pages, no figures
arxiv created 2007/12/28 · arxiv updated 2009/12/01
The inverse problem for representation functions takes as input a triple (X,f,L), where X is a countable semigroup, f : X --> N0 ∪ ∞ a function, L : a1 x1 + ... + ah xh an X-linear form and asks for a subset A ⊆ X such that there are f(x) solutions (counted appropriately) to L(x1,...,xh) = x for every x ∈ X, or a proof that no such subset exists. This paper represents the first systematic study of this problem for arbitrary linear forms when X = Z, the setting which in many respects is the most natural one. Having first settled on the "right" way to count representations, we prove that every primitive form has a unique representation basis, i.e.: a set A which represents the function f ≡ 1. We also prove that a partition regular form (i.e.: one for which no non-empty subset of the coefficients sums to zero) represents any function f for which f-1(0) has zero asymptotic density. These two results answer questions recently posed by Nathanson. The inverse problem for partition irregular forms seems to be more complicated. The simplest example of such a form is x1 - x2, and for this form we provide some partial results. Several remaining open problems are discussed.