SOLVED - $500

If $f:\mathbb{N}\to \{-1,+1\}$ then is it true that for every $C>0$ there exist $d,m\geq 1$ such that
\[\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert > C?\]

The Erdős discrepancy problem. This is true, and was proved by Tao [Ta16], who also proved the more general case when $f$ takes values on the unit sphere.

In [Er81] it is further conjectured that \[\max_{md\leq x}\left\lvert \sum_{1\leq k\leq m}f(kd)\right\rvert \gg \log x.\]

In [Er85c] Erdős also asks about the special case when $f$ is multiplicative.

OPEN - $500

Let $\alpha\in[0,1/2)$ and $n,t\geq 1$. Let $F^{(t)}(n,\alpha)$ be the largest $m$ such that we can $2$-colour the edges of the complete $t$-uniform hypergraph on $n$ vertices such that if $X\subseteq [n]$ with $\lvert X\rvert \geq m$ then there are at least $\alpha \binom{\lvert X\rvert}{t}$ many $t$-subsets of $X$ of each colour.

For fixed $n,t$ as we change $\alpha$ from $0$ to $1/2$ does $F^{(t)}(n,\alpha)$ increase continuously or are there jumps? Only one jump?

For $\alpha=0$ this is the usual Ramsey function. A conjecture of Erdős, Hajnal, and Rado (see [562]) implies that
\[ F^{(t)}(n,0)\asymp \log_{t-1} n\]
and results of Erdős and Spencer imply that
\[F^{(t)}(n,\alpha) \gg_\alpha (\log n)^{\frac{1}{t-1}}\]
for all $\alpha>0$, and a similar upper bound holds for $\alpha$ close to $1/2$.

Erdős believed there might be just one jump, occcurring at $\alpha=0$.

Conlon, Fox, and Sudakov [CFS11] have proved that, for any fixed $\alpha>0$, \[F^{(3)}(n,\alpha) \ll_\alpha \sqrt{\log n}.\] Coupled with the lower bound above, this implies that there is only one jump for fixed $\alpha$ when $t=3$, at $\alpha=0$.

For all $\alpha>0$ it is known that \[F^{(t)}(n,\alpha)\gg_t (\log n)^{c_\alpha}.\] See also [563].

OPEN

Let $\alpha>0$ and $n\geq 1$. Let $F(n,\alpha)$ be the largest $k$ such that in any 2-colouring of the edges of $K_n$ any subgraph $H$ on at least $k$ vertices contains more than $\alpha\binom{\lvert H\rvert}{2}$ many edges of each colour.

Prove that for every fixed $0\leq \alpha \leq 1/2$, as $n\to\infty$, \[F(n,\alpha)\sim c_\alpha \log n\] for some constant $c_\alpha$.

It is easy to show with the probabilistic method that there exist $c_1(\alpha),c_2(\alpha)$ such that
\[c_1(\alpha)\log n < F(n,\alpha) < c_2(\alpha)\log n.\]

OPEN

Let $N(k,\ell)$ be the minimal $N$ such that for any $f:\{1,\ldots,N\}\to\{-1,1\}$ there must exist a $k$-term arithmetic progression $P$ such that
\[ \left\lvert \sum_{n\in P}f(n)\right\rvert\geq \ell.\]
Find good upper bounds for $N(k,\ell)$. Is it true that for any $c>0$ there exists some $C>1$ such that
\[N(k,ck)\leq C^k?\]
What about
\[N(k,2)\leq C^k\]
or
\[N(k,\sqrt{k})\leq C^k?\]

Spencer [Sp73] has proved that if $k=2^tm$ with $m$ odd then
\[N(k,1)=2^t(k-1)+1.\]
Erdős and Graham write that 'no decent bound' is known even for $N(k,2)$. Probabilistic methods imply that, for every fixed constant $c>0$, we have $N(k,ck)>C_c^k$ for some $C_c>1$.

OPEN

Find the smallest $h(d)$ such that the following holds. There exists a function $f:\mathbb{N}\to\{-1,1\}$ such that, for every $d\geq 1$,
\[\max_{P_d}\left\lvert \sum_{n\in P_d}f(n)\right\rvert\leq h(d),\]
where $P_d$ ranges over all finite arithmetic progressions with common difference $d$.

Cantor, Erdős, Schreiber, and Straus [Er66] proved that $h(d)\ll d!$ is possible. Van der Waerden's theorem implies that $h(d)\to \infty$. Beck [Be17] has shown that $h(d) \leq d^{8+\epsilon}$ is possible for every $\epsilon>0$. Roth's famous discrepancy lower bound [Ro64] implies that $h(d)\gg d^{1/2}$.

SOLVED

Let $A_1,A_2,\ldots$ be an infinite collection of infinite sets of integers, say $A_i=\{a_{i1}<a_{i2}<\cdots\}$. Does there exist some $f:\mathbb{N}\to\{-1,1\}$ such that
\[\max_{m, 1\leq i\leq d} \left\lvert \sum_{1\leq j\leq m} f(a_{ij})\right\rvert \ll_d 1\]
for all $d\geq 1$?

Erdős remarks 'it seems certain that the answer is affirmative'. This was solved by Beck [Be81]. Recently Beck [Be17] proved that one can replace $\ll_d 1$ with $\ll d^{4+\epsilon}$ for any $\epsilon>0$.

SOLVED

Let $z_1,z_2,\ldots \in [0,1]$ be an infinite sequence, and define the discrepancy
\[D_N(I) = \#\{ n\leq N : z_n\in I\} - N\lvert I\rvert.\]
Must there exist some interval $I\subseteq [0,1]$ such that
\[\limsup_{N\to \infty}\lvert D_N(I)\rvert =\infty?\]

The answer is yes, as proved by Schmidt [Sc68], who later showed [Sc72] that in fact this is true for all but countably many intervals of the shape $[0,x]$.

Essentially the best possible result was proved by Tijdeman and Wagner [TiWa80], who proved that, for almost all intervals of the shape $[0,x)$, we have \[\limsup_{N\to \infty}\frac{\lvert D_N([0,x))\rvert}{\log N}\gg 1.\]