Erdős problem 844 · problems.science

Let $A\subseteq \{1,\ldots,N\}$ be such that, for all $a,b\in A$ , the product $ab$ is not squarefree.

Sources

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

1 retained statement2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

844.lean

Retained formal statement1 of 1

Let $A\subseteq \{1,\ldots,N\}$ be such that, for all $a,b\in A$ , the product $ab$ is not squarefree.

Is the maximum size of such an $A$ achieved by taking $A$ to be the set of even numbers and odd non-squarefree numbers?

A problem of Erdős and Sárközy.

Weisenberg has provided the following positive proof. It is clear that such a maximal $A$ must contain all non-squarefree numbers. It therefore suffices to find the largest size of a subset of all squarefree numbers in $\{1,\ldots,N\}$ such that any two have at least one prime factor in common. By the result of Chvátal [Ch74] discussed in [701] this is maximised by the set of all even squarefree numbers.

An alternative proof was independently found by Alexeev, Mixon, and Sawin [AMS25].

FormalConjectures/ErdosProblems/844.leanErdos844.erdos_8444 linesExact file

1True ↔2  ∀ (N : ℕ),3    IsGreatest {k | ∃ A ⊆ Finset.Icc 1 N, (∀ a ∈ A, ∀ b ∈ A, ¬Squarefree (a * b)) ∧ A.card = k}4      (Erdos844.evenOrOddNonSquarefree N).card

SolvedStatement only, no proof

Sources

Search problems.science