Erdős problem 817

Let $k \geq 3$ . Define $g_k(n)$ to be the minimal $N$ such that $\{1, ..., N\}$ contains some $A$ of size $|A| = n$ such that $\langle A\rangle = \left\{\sum_{a \in A} \epsilon_a a : \epsilon_a \in\{0, 1\}\right\}$ contains no non-trivial $k$ -term arithmetic progression. Estimate $g_k(n)$ . In particular, is it true that $g_3(n) \gg 3^n$

Sources

The source's own material, retained exactly.

2 retained statements36c6d0fef71a

FormalConjectures/ErdosProblems/

817.lean

Retained formal statement1 of 2

Let $k \geq 3$ . Define $g_k(n)$ to be the minimal $N$ such that $\{1, ..., N\}$ contains some $A$ of size $|A| = n$ such that $\langle A\rangle = \left\{\sum_{a \in A} \epsilon_a a : \epsilon_a \in\{0, 1\}\right\}$ contains no non-trivial $k$ -term arithmetic progression. Estimate $g_k(n)$ . In particular, is it true that $g_3(n) \gg 3^n$

FormalConjectures/ErdosProblems/817.leanErdos817.erdos_8171 lineExact file

1True ↔ (fun n => 3 ^ n) =O[Filter.atTop] fun n => ↑(Erdos817.g 3 n)

OpenStatement only, no proof