Green's Open Problem 24

References:

• Green, Ben. "100 open problems." (2024).
• [Aa19] Aaronson, James. "Maximising the number of solutions to a linear equation in a set of integers." Bulletin of the London Mathematical Society 51.4 (2019): 577-594.
• [HaL28] Hardy, G. H., and J. E. Littlewood. "Notes on the theory of series (VIII): an inequality." Journal of the London Mathematical Society 1.2 (1928): 105-110.

noncomputable def Green24.max013AffineTranslates (n : ℕ) : ℕ

The maximum number of $\lbrace 0,1,3 \rbrace$ affine translates that a set of size $n$ can contain.

Equations

• One or more equations did not get rendered due to their size.

theorem Green24.green_24 (n : ℕ) : max013AffineTranslates n = sorry

If $A$ is a set of $n$ integers, what is the maximum number of affine translates of the set $\lbrace 0,1,3 \rbrace$ that $A$ can contain?

Conjectured in [Aa19] p.579: $\left({1}{3} + o(1)\right) n^2$.

A collection of associated bounds and conjectured values.

theorem Green24.variants.upper_trivial {n : ℕ} : max013AffineTranslates n ≤ n ^ 2

From [Aa19] p.577: the trivial upper bound is $n^2$ (non asymptotic)

noncomputable def Green24.variants.gamma : ℝ

The asymptotic constant $\gamma$ defined in [Aa19] p.579.

Equations

• Green24.variants.gamma = Filter.limsup (fun (n : ℕ) => ↑(Green24.max013AffineTranslates n) / ↑n ^ 2) Filter.atTop

theorem Green24.variants.upper_HL : gamma ≤ 3 / 4

Asymptotic upper bound (1.2) in [Aa19]. Named after Hardy and Littlewood [HaL28].

theorem Green24.variants.lower_HL : gamma ≥ 1 / 12

Asymptotic lower bound (1.2) in [Aa19]. Named after Hardy and Littlewood [HaL28].

theorem Green24.variants.conjecture : gamma = 1 / 3

Conjecture p.579 in [Aa19]: $\left({1}{3} + o(1)\right) n^2$.