← All problems

Erdős Problem #1194 — Growth forced by unique difference representations

46 years old · traced to

Let A⊆NA\subseteq\mathbb{N} be a set of positive integers such that every positive integer has exactly one ordered representation as a difference of two elements of AA. Thus, for each n≥1n\geq 1, there is a unique pair (xn,yn)∈A2(x_n,y_n)\in A^2 satisfying Erdős (1980)

n=xn−yn,xn>yn.n=x_n-y_n,\qquad x_n>y_n.

Erdős (1980)

The question is how slowly the larger term xnx_n can grow relative to nn—equivalently, how small the ratio xn/nx_n/n can be, subject to this unique-representation condition. Here xnx_n denotes the larger element in the representation of nn, not the nnth element of an increasing enumeration of AA. 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 A(x)≫x2−1−o(1)A(x)\gg x^{\sqrt{2}-1-o(1)}, where A(x)=∣A∩[1,x]∣A(x)=|A\cap[1,x]|. This concerns the counting function of the set, rather than directly determining the growth of xnx_n. Cilleruelo and Nathanson (2008)

References

P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.

Source: P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115.

Progress summary

Never refreshed

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.