Skip to content

Erdős problem 1028

Start work

Let H(n)=min⁡fmax⁡X⊆{1,…,n}∣∑x<y∈Xf(x,y)∣,H(n)=\min_f \max_{X\subseteq \{1,\ldots,n\}} \left\lvert \sum_{x<y\in X} f(x,y)\right\rvert, where ff ranges over all functions f:{1,…,n}2→{−1,1}f:\{1,\ldots,n\}^2\to \{-1,1\}. Estimate H(n)H(n).

Sources

The source's own material, retained exactly.

4 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1028.lean

Retained formal statement1 of 4

Let H(n)=min⁡fmax⁡X⊆{1,…,n}∣∑x<y∈Xf(x,y)∣,H(n)=\min_f \max_{X\subseteq \{1,\ldots,n\}} \left\lvert \sum_{x<y\in X} f(x,y)\right\rvert, where ff ranges over all functions f:{1,…,n}2→{−1,1}f:\{1,\ldots,n\}^2\to \{-1,1\}. Estimate H(n)H(n).

Erdős [Er63d] proved n4≤H(n)≪n3/2.\frac{n}{4}\leq H(n) \ll n^{3/2}. Erdős and Spencer [ErSp71] proved that H(n)≫n3/2H(n)\gg n^{3/2}.

FormalConjectures/ErdosProblems/1028.leanErdos1028.erdos_10281 lineExact file
(fun n => ↑(Erdos1028.H n)) =Θ[Filter.atTop] fun n => ↑n ^ (3 / 2)
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.