← All problems

Erdős Problem #327 — Divisibility-avoiding sets for pair sums

47 years old · traced to

Let [N]={1,…,N}[N]=\{1,\ldots,N\}, and for k∈{1,2}k\in\{1,2\} define

fk(N)=max⁡{∣A∣:A⊆[N], a+b∤kab for all distinct a,b∈A}.f_k(N)=\max\bigl\{|A|:A\subseteq[N],\ a+b\nmid kab\text{ for all distinct }a,b\in A\bigr\}.

The first question asks whether such a set for k=1k=1 can be “substantially more” than the odd integers. The odd integers provide a lower bound of ⌈N/2⌉\lceil N/2\rceil; “substantially more” is not quantified in the question. The second question asks whether every k=2k=2 set has size o(N)o(N) as N→∞N\to\infty, equivalently whether f2(N)=o(N)f_2(N)=o(N). Here x∣yx\mid y means that yy is an integer multiple of xx. Erdős Problem #327 Yu Leon Liu, Upper Bounds for Erdős Problem #327 and Its k-Variant

Background

Erdős and Graham posed these questions in Old and New Problems and Results in Combinatorial Number Theory (1980). Their unit-fraction connection follows from

1a+1b=a+bab,\frac1a+\frac1b=\frac{a+b}{ab},

which is a unit fraction exactly when a+b∣aba+b\mid ab. Likewise, the average of 1/a1/a and 1/b1/b is a unit fraction exactly when a+b∣2aba+b\mid 2ab. Thus the two variants ask for large sets of unit fractions avoiding, respectively, a pair whose sum or whose average is a unit fraction. The odd integers give the stated lower bound for the first variant, since the sum of two odd integers is even while their product is odd. Erdős and Graham (1980) Erdős Problem #327

References

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.