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 statement4 of 4

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

FormalConjectures/ErdosProblems/1028.leanErdos1028.erdos_1028.variants.upper_bound1 lineExact file
(fun n => ↑(Erdos1028.H n)) =O[Filter.atTop] fun n => ↑n ^ (3 / 2)
SolvedStatement only, no proof