gpt pro 5.2 attempt on Math-5781

Problem 633. Let $t\ge 1$ and $A\subseteq\{1,\dots,N\}$ satisfy: if $a,b\in A$ with $b-a\ge t$ then $(b-a)\nmid b$. How large can $|A|$ be? Is $|A|\le (\tfrac12+o_t(1))N$?

1) [Formal restatement]

Fix an integer $t\ge 1$. Let $A\subseteq [N]:=\{1,2,\dots,N\}$ be such that for all $a<b$ in $A$ with $d:=b-a\ge t$, we have $d\nmid b$.

Define \[ M_t(N):=\max\{|A|: A\subseteq [N]\text{ satisfies the above divisibility-avoidance condition}\}. \] The questions ask (i) determine/estimate $M_t(N)$, and (ii) decide whether $M_t(N)\le (\tfrac12+o_t(1))N$ as $N\to\infty$ for fixed $t$.

2) [Quick literature/context check (if browsing is available)]

The prompt attributes to Erdős:

• For $t=1$, taking all odd numbers gives $|A|\ge \lceil N/2\rceil$, and this is optimal.
• For $t=2$, one can take all odd numbers together with powers $2^{2k+1}$, giving $|A|=\frac12N+\Omega(\log N)$.

The problem is referenced in surveys/collections associated with Erdős and Ruzsa (e.g. Ruzsa's 1999 paper "Erdős and the integers") as an open extremal question.

3) [Attack plan]

1. Rephrase the forbidden configuration in a more structural way ("consecutive multiples" viewpoint).
2. Establish sharp behavior for $t=1$.
3. Give a clean general lower bound construction for all $t$ (always $\ge \lceil N/2\rceil$) and explain Erdős' logarithmic improvement mechanism.
4. Provide partial upper bounds obtainable from simple constraints, and isolate what would be needed to prove the conjectured $(\tfrac12+o_t(1))N$ upper bound.

4) [Work]

4.1. Equivalent "consecutive multiples" formulation.

A forbidden pair $(a,b)$ with $a<b$ occurs exactly when there exists an integer $d\ge t$ and an integer $k\ge 1$ such that \[ a=kd,\qquad b=(k+1)d. \] Indeed, $b-a=d$ and $d\mid b$.

Therefore the condition on $A$ can be restated as:

For every integer $d\ge t$, the set $\{k\ge 1: kd\in A\}$ contains no two consecutive integers.

Equivalently, for each $d\ge t$, among the multiples of $d$ in $[N]$ the set $A$ may not contain two consecutive multiples.

4.2. The case $t=1$ (exact).

If $t=1$, then for any $b\in A$ we cannot have $b-1\in A$ because $b-(b-1)=1\mid b$. Thus $A$ contains no two consecutive integers, so $|A|\le \lceil N/2\rceil$. Taking $A$ to be the odd numbers achieves $\lceil N/2\rceil$, hence \[ M_1(N)=\lceil N/2\rceil. \]

4.3. A universal lower bound for all $t$.

For any $t\ge 1$, the set of all odd numbers in $[N]$ satisfies the condition: if $a<b$ are odd then $b-a$ is even, hence cannot divide the odd integer $b$. Therefore \[ M_t(N)\ge \lceil N/2\rceil\qquad\text{for all }t\ge 1. \]

4.4. Logarithmic extra elements for $t\ge 2$ (Erdős' mechanism).

Still for $t\ge 2$, one may try to add some even numbers to the odd set. If an even $b$ has no odd divisor $\ge t$, then for any odd $a$ with $b-a\ge t$ the difference $b-a$ is odd and cannot divide $b$ (since every odd divisor of $b$ is $<t$).

In particular, for $t=2$ the powers of $2$ have no odd divisors $\ge 2$; choosing a subset of powers of $2$ that avoids forbidden differences among themselves (e.g. $2^{2k+1}$) yields the stated $\frac12N+\Omega(\log N)$ construction.

More generally, for fixed $t$, any number of the form $2^k m$ with $m$ odd and $m<t$ has all odd divisors $<t$, so such numbers can be appended to the odd set subject only to avoiding forbidden relations among the appended even numbers themselves. The total number of such candidates is $O_t(\log N)$.

4.5. Upper-bound obstacles.

The conjectured upper bound $M_t(N)\le (\tfrac12+o_t(1))N$ would follow from showing that every admissible set of density $>\tfrac12+\varepsilon$ necessarily contains a forbidden consecutive-multiples configuration for some $d\ge t$.

A natural graph-theoretic model is: let $G_{t,N}$ be the graph on $[N]$ with an edge between $kd$ and $(k+1)d$ for every $d\ge t$ and $k\ge 1$ with $(k+1)d\le N$. Then admissible $A$ are exactly independent sets in $G_{t,N}$. Proving $M_t(N)\le (\tfrac12+o_t(1))N$ is equivalent to proving that the independence number $\alpha(G_{t,N})\le (\tfrac12+o_t(1))N$.

I do not complete such an upper bound here.

5) [Verification]

• The equivalence with forbidding consecutive multiples $kd,(k+1)d$ for all $d\ge t$ is immediate from $b-a=d$.
• For $t=1$, the "no consecutive integers" argument is correct and gives the exact optimum $\lceil N/2\rceil$.
• The "all odds" lower bound is valid for every $t$.
• The logarithmic construction principle is valid in that numbers with all odd divisors $<t$ do not create forbidden pairs with the odd set at differences $\ge t$; additional checking is required only for interactions among the added even numbers.

6) [Final]

LABEL: UNRESOLVED
SUBLABEL: Exact for $t=1$; for $t\ge 2$, lower bounds known, conjectured $\tfrac12$-density upper bound not proved here.
I determined $M_1(N)=\lceil N/2\rceil$ and gave the general lower bound $M_t(N)\ge \lceil N/2\rceil$ (all odds), with Erdős' mechanism producing $\frac12N+\Omega(\log N)$ when $t=2$ (and $O_t(\log N)$ possible extra candidates for fixed $t\ge 2$). I do not prove (nor disprove) the conjectured upper bound $M_t(N)\le (\tfrac12+o_t(1))N$ for fixed $t\ge 2$.

7) [Completion estimate]

About 40% complete: the problem is solved for $t=1$ and the standard constructions/reformulations are provided, but the main asymptotic upper bound question for fixed $t\ge 2$ remains open.