Erdős Problem #1194 — Growth forced by unique difference representations
Let be a set of positive integers such that every positive integer has exactly one ordered representation as a difference of two elements of . Thus, for each , there is a unique pair satisfying Erdős (1980)
The question is how slowly the larger term can grow relative to —equivalently, how small the ratio can be, subject to this unique-representation condition. Here denotes the larger element in the representation of , not the th element of an increasing enumeration of . Erdős (1980)
Background
Erdős posed the problem in his 1980 survey, observing that such sequences are easy to construct but that he could not determine how rapidly the larger representation term must grow. A set with the stated property is called a perfect difference set: each nonzero integer occurs exactly once as an ordered difference. The uniqueness condition also gives the set a Sidon-type sparsity constraint, which is useful for obtaining lower bounds on the representation terms. Erdős (1980) Erdős Problems #1194
A related line of work connects perfect difference sets with dense Sidon sets. Cilleruelo and Nathanson constructed dense perfect difference sets from dense Sidon sets; among their results, they proved that some such set satisfies , where . This concerns the counting function of the set, rather than directly determining the growth of . Cilleruelo and Nathanson (2008)
References
P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.