Monochromatic sums equal to perfect powers

DefinitionErdős Problem 439 for squares#✓fully proved

The statement that for every colouring of the positive integers with finitely many colours there are distinct positive integers \(x\) and \(y\) of the same colour such that \(x + y\) is a perfect square.

def monochromaticSquareSum : Prop :=
  ∀ r : ℕ, ∀ c : ℕ → Fin r, ∃ x y : ℕ, 0 < x ∧ 0 < y ∧ x ≠ y ∧ c x = c y ∧ IsSquare (x + y)

Used by 1

Used byErdős Problem 439 for squares is true

DefinitionErdős Problem 439 for \(k\)-th powers#✓fully proved

The statement that for every integer \(k \ge 2\) and every colouring of the positive integers with finitely many colours there are distinct positive integers \(x\) and \(y\) of the same colour such that \(x + y = z^k\) for some natural number \(z\).

def monochromaticPowerSum : Prop :=
  ∀ k : ℕ, 2 ≤ k → ∀ r : ℕ, ∀ c : ℕ → Fin r,
    ∃ x y : ℕ, 0 < x ∧ 0 < y ∧ x ≠ y ∧ c x = c y ∧ ∃ z : ℕ, x + y = z ^ k

Used by 1

Used byErdős Problem 439 for \(k\)-th powers is true

TheoremErdős Problem 439 for squares is true#●ready to prove

For every colouring of the positive integers with finitely many colours there are distinct positive integers \(x\) and \(y\) of the same colour such that \(x + y\) is a perfect square.

This is the case \(f(z) = z^2\) of a theorem of Khalfalah and Szemerédi on monochromatic solutions of \(x + y = f(z)\); Erdős, Sárközy and Sós had proved the cases of \(2\) and \(3\) colours.

public theorem_wanted monochromaticSquareSum_holds : monochromaticSquareSum

Sources

• T. F. Bloom, Erdős Problems, Problem #439, https://www.erdosproblems.com/439 (status PROVED); resolution: A. Khalfalah and E. Szemerédi, On the number of monochromatic solutions of x + y = z², Combin. Probab. Comput. (2006), 213-227, main theorem (a conjecture of Erdős, Roth, Sárközy and Sós): for every nonconstant f ∈ ℤ[z] with 2 ∣ f(z) for some z ∈ ℤ, every finite colouring of the integers has x ≠ y of the same colour with x + y = f(z) (abstract; erdosproblems.com/439), https://doi.org/10.1017/S0963548305007169.

Uses 1

Statement usesErdős Problem 439 for squares

TheoremErdős Problem 439 for \(k\)-th powers is true#●ready to prove

For every integer \(k \ge 2\) and every colouring of the positive integers with finitely many colours there are distinct positive integers \(x\) and \(y\) of the same colour such that \(x + y = z^k\) for some natural number \(z\).

Khalfalah and Szemerédi proved the corresponding statement for \(x + y = f(z)\) for every nonconstant polynomial \(f\) with integer coefficients such that \(f(z)\) is even for some integer \(z\); the polynomial \(f(z) = z^k\) qualifies, since \(f(2) = 2^k\).

public theorem_wanted monochromaticPowerSum_holds : monochromaticPowerSum

Sources

• T. F. Bloom, Erdős Problems, Problem #439, https://www.erdosproblems.com/439 (status PROVED); resolution: A. Khalfalah and E. Szemerédi, On the number of monochromatic solutions of x + y = z², Combin. Probab. Comput. (2006), 213-227, main theorem (a conjecture of Erdős, Roth, Sárközy and Sós): for every nonconstant f ∈ ℤ[z] with 2 ∣ f(z) for some z ∈ ℤ, every finite colouring of the integers has x ≠ y of the same colour with x + y = f(z) (abstract; erdosproblems.com/439), https://doi.org/10.1017/S0963548305007169.

Uses 1

Statement usesErdős Problem 439 for \(k\)-th powers

2 fully proved2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.