Skip to content

Erdős problem 331

Let A,BNA,B\subseteq \mathbb{N} such that for all large NNA{1,,N}N1/2\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}andB{1,,N}N1/2.\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}. Is it true that there are infinitely many solutions to a1a2=b1b20a_1-a_2=b_1-b_2\neq 0 with a1,a2Aa_1,a_2\in A and b1,b2Bb_1,b_2\in B?

Sources

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

2 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

331.lean

Retained formal statement1 of 2

Let A,BNA,B\subseteq \mathbb{N} such that for all large NNA{1,,N}N1/2\lvert A\cap \{1,\ldots,N\}\rvert \gg N^{1/2}andB{1,,N}N1/2.\lvert B\cap \{1,\ldots,N\}\rvert \gg N^{1/2}. Is it true that there are infinitely many solutions to a1a2=b1b20a_1-a_2=b_1-b_2\neq 0 with a1,a2Aa_1,a_2\in A and b1,b2Bb_1,b_2\in B?

Ruzsa has observed that there is a simple counterexample: take AA to be the set of numbers whose binary representation has only non-zero digits in even places, and BB similarly but with non-zero digits only in odd places. It is easy to see AA and BB both grow like N1/2\gg N^{1/2} and yet for any n1n\geq 1 there is exactly one solution to n=a+bn=a+b with aAa\in A and bBb\in B.

This was formalized in Lean by van Doorn using Aristotle.

FormalConjectures/ErdosProblems/331.leanErdos331.erdos_3315 linesExact file
False  ∀ (A B : Set ℕ),    ((fun n => ↑n ^ (1 / 2)) =O[Filter.atTop] fun n => ↑(Nat.count A n)) →      ((fun n => ↑n ^ (1 / 2)) =O[Filter.atTop] fun n => ↑(Nat.count B n)) →        {(a₁, a₂, b₁, b₂) | a₁ ∈ Aa₂ ∈ Ab₁ ∈ Bb₂ ∈ Ba₁ ≠ a₂ ∧ a₁ + b₂ = a₂ + b₁}.Infinite
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Search problems.science

Find a Problem, Result, source, or page