Skip to content

Erdős problem 848

Is the maximum size of a set A{1,,N}A\subseteq \{1,\ldots,N\} such that ab+1ab+1 is never squarefree (for all a,bAa,b\in A) achieved by taking those n7(mod25)n\equiv 7\pmod{25}? Resolved for all sufficiently large NN: any near-maximal AA is contained in {n7(mod25)}\{n\equiv 7\pmod{25}\} or {n18(mod25)}\{n\equiv 18\pmod{25}\}, leaving only a finite check.

Sources

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

848.lean

Retained formal statement1 of 2

Is the maximum size of a set A{1,,N}A ⊆ \{1, \dots, N\} such that ab+1ab + 1 is never squarefree (for all a,bAa, b ∈ A) achieved by taking those n7(mod25)n ≡ 7 \pmod{25}?

This asks whether Erdos848 N holds for all NN (formulated using A ⊆ Finset.range N).

This was solved for all sufficiently large NN by Sawhney in this note. In fact, Sawhney proves something slightly stronger, that there exists some constant c>0c>0 such that if A(125c)N\lvert A\rvert \geq (\frac{1}{25}-c)N and NN is large then AA is contained in either {n7(mod25)}\{ n\equiv 7\pmod{25}\} or {n18(mod25)}\{n\equiv 18\pmod{25}\}.

FormalConjectures/ErdosProblems/848.leanErdos848.erdos_8481 lineExact file
True ↔ ∀ (N : ℕ), Erdos848.Erdos848For N
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page