IMO Shortlist, 2019

First, observe that if $n$ is a positive integer, then $n \in H$ exactly when
$$\left\{\frac{n}{\sqrt{2}}\right\}>1-\frac{1}{\sqrt{2}} \tag{1}$$
To see why, observe that $n \in H$ if and only if $0<i \sqrt{2}-n<1$ for some $i \in \mathbb{Z}_{>0}$. In other words, $0<i-n / \sqrt{2}<1 / \sqrt{2}$, which is equivalent to (1).

Now, write $A=\{a_{1}<a_{2}<\cdots<a_{k}\}$, where $k=|A|$. Observe that the set of differences is not altered by shifting $A$, so we may assume that $A \subseteq\{0,1, \ldots, n-1\}$ with $a_{1}=0$.

From (1), we learn that $\left\{a_{i} / \sqrt{2}\right\}<1-1 / \sqrt{2}$ for each $i>1$ since $a_{i}-a_{1} \notin H$. Furthermore, we must have $\left\{a_{i} / \sqrt{2}\right\}<\left\{a_{j} / \sqrt{2}\right\}$ whenever $i<j$; otherwise, we would have
$$-\left(1-\frac{1}{\sqrt{2}}\right)<\left\{\frac{a_{j}}{\sqrt{2}}\right\}-\left\{\frac{a_{i}}{\sqrt{2}}\right\}<0$$
Since $\left\{\left(a_{j}-a_{i}\right) / \sqrt{2}\right\}=\left\{a_{j} / \sqrt{2}\right\}-\left\{a_{i} / \sqrt{2}\right\}+1$, this implies that $\left\{\left(a_{j}-a_{i}\right) / \sqrt{2}\right\}>1 / \sqrt{2}> 1-1 / \sqrt{2}$, contradicting (1).

Now, we have a sequence $0=a_{1}<a_{2}<\cdots<a_{k}<n$, with
$$0=\left\{\frac{a_{1}}{\sqrt{2}}\right\}<\left\{\frac{a_{2}}{\sqrt{2}}\right\}<\cdots<\left\{\frac{a_{k}}{\sqrt{2}}\right\}<1-\frac{1}{\sqrt{2}}$$
We use the following fact: for any $d \in \mathbb{Z}$, we have
$$\left\{\frac{d}{\sqrt{2}}\right\}>\frac{1}{2 d \sqrt{2}} \tag{2}$$
To see why this is the case, let $h=\lfloor d / \sqrt{2}\rfloor$, so $\{d / \sqrt{2}\}=d / \sqrt{2}-h$. Then
$$\left\{\frac{d}{\sqrt{2}}\right\}\left(\frac{d}{\sqrt{2}}+h\right)=\frac{d^{2}-2 h^{2}}{2} \geqslant \frac{1}{2}$$
since the numerator is a positive integer. Because $d / \sqrt{2}+h<2 d / \sqrt{2}$, inequality (2) follows.

Let $d_{i}=a_{i+1}-a_{i}$, for $1 \leqslant i<k$. Then $\left\{a_{i+1} / \sqrt{2}\right\}-\left\{a_{i} / \sqrt{2}\right\}=\left\{d_{i} / \sqrt{2}\right\}$, and we have
$$1-\frac{1}{\sqrt{2}}>\sum_{i}\left\{\frac{d_{i}}{\sqrt{2}}\right\}>\frac{1}{2 \sqrt{2}} \sum_{i} \frac{1}{d_{i}} \geqslant \frac{(k-1)^{2}}{2 \sqrt{2}} \frac{1}{\sum_{i} d_{i}}>\frac{(k-1)^{2}}{2 \sqrt{2}} \cdot \frac{1}{n} . \tag{3}$$
Here, the first inequality holds because $\left\{a_{k} / \sqrt{2}\right\}<1-1 / \sqrt{2}$, the second follows from (2), the third follows from an easy application of the AM-HM inequality (or Cauchy-Schwarz), and the fourth follows from the fact that $\sum_{i} d_{i}=a_{k}<n$.

Rearranging this, we obtain
$$\sqrt{2 \sqrt{2}-2} \cdot \sqrt{n}>k-1$$
which provides the required bound on $k$.

Let $\alpha=2+\sqrt{2}$, so $(1 / \alpha)+(1 / \sqrt{2})=1$. Thus, $J=\{\lfloor i \alpha\rfloor: i \in \mathbb{Z}_{>0}\}$ is the complementary Beatty sequence to $H$ (in other words, $H$ and $J$ are disjoint with $H \cup J=\mathbb{Z}_{>0}$ ). Write $A=\{a_{1}<a_{2}<\cdots<a_{k}\}$. Suppose that $A$ has no differences in $H$, so all its differences are in $J$ and we can set $a_{i}-a_{1}=\lfloor\alpha b_{i}\rfloor$ for $b_{i} \in \mathbb{Z}_{>0}$.

For any $j>i$, we have $a_{j}-a_{i}=\lfloor\alpha b_{j}\rfloor-\lfloor\alpha b_{i}\rfloor$. Because $a_{j}-a_{i} \in J$, we also have $a_{j}-a_{i}=\lfloor\alpha t\rfloor$ for some positive integer $t$. Thus, $\lfloor\alpha t\rfloor=\lfloor\alpha b_{j}\rfloor-\lfloor\alpha b_{i}\rfloor$. The right hand side must equal either $\lfloor\alpha(b_{j}-b_{i})\rfloor$ or $\lfloor\alpha(b_{j}-b_{i})\rfloor-1$, the latter of which is not a member of $J$ as $\alpha>2$. Therefore, $t=b_{j}-b_{i}$ and so we have $\lfloor\alpha b_{j}\rfloor-\lfloor\alpha b_{i}\rfloor=\lfloor\alpha(b_{j}-b_{i})\rfloor$.

For $1 \leqslant i<k$ we now put $d_{i}=b_{i+1}-b_{i}$, and we have
$$\lfloor\alpha \sum_{i} d_{i}\rfloor=\lfloor\alpha b_{k}\rfloor=\sum_{i}\lfloor\alpha d_{i}\rfloor$$
that is, $\sum_{i}\{\alpha d_{i}\}<1$. We also have
$$1+\lfloor\alpha \sum_{i} d_{i}\rfloor=1+a_{k}-a_{1} \leqslant a_{k} \leqslant n$$
so $\sum_{i} d_{i} \leqslant n / \alpha$.

With the above inequalities, an argument similar to (3) (which uses the fact that $\{\alpha d\}= \{d \sqrt{2}\}>1 /(2 d \sqrt{2})$ for positive integers $d$ ) proves that $1>\left((k-1)^{2} /(2 \sqrt{2})\right)(\alpha / n)$, which again rearranges to give
$$\sqrt{2 \sqrt{2}-2} \cdot \sqrt{n}>k-1$$

Again, define $J=\mathbb{Z}_{>0} \backslash H$, so all differences between elements of $A$ are in $J$. We start by making the following observation. Suppose we have a set $B \subseteq\{1,2, \ldots, n\}$ such that all of the differences between elements of $B$ are in $H$. Then $|A| \cdot|B| \leqslant 2 n$.

To see why, observe that any two sums of the form $a+b$ with $a \in A, b \in B$ are different; otherwise, we would have $a_{1}+b_{1}=a_{2}+b_{2}$, and so $|a_{1}-a_{2}|=|b_{2}-b_{1}|$. However, then the left hand side is in $J$ whereas the right hand side is in $H$. Thus, $\{a+b: a \in A, b \in B\}$ is a set of size $|A| \cdot|B|$ all of whose elements are no greater than $2 n$, yielding the claimed inequality.

With this in mind, it suffices to construct a set $B$, all of whose differences are in $H$ and whose size is at least $C' \sqrt{n}$ for some constant $C'>0$.

To do so, we will use well-known facts about the negative Pell equation $X^{2}-2 Y^{2}=-1$; in particular, that there are infinitely many solutions and the values of $X$ are given by the recurrence $X_{1}=1, X_{2}=7$ and $X_{m}=6 X_{m-1}-X_{m-2}$. Therefore, we may choose $X$ to be a solution with $\sqrt{n} / 6<X \leqslant \sqrt{n}$.

Now, we claim that we may choose $B=\{X, 2 X, \ldots,\lfloor(1 / 3) \sqrt{n}\rfloor X\}$. Indeed, we have
$$\left(\frac{X}{\sqrt{2}}-Y\right)\left(\frac{X}{\sqrt{2}}+Y\right)=\frac{-1}{2}$$
and so
$$0>\left(\frac{X}{\sqrt{2}}-Y\right) \geqslant \frac{-3}{\sqrt{2 n}},$$
from which it follows that $\{X / \sqrt{2}\}>1-(3 / \sqrt{2 n})$. Combined with (1), this shows that all differences between elements of $B$ are in $H$.

As in Solution 3, we will provide a construction of a large set $B \subseteq\{1,2, \ldots, n\}$, all of whose differences are in $H$.

Choose $Y$ to be a solution to the Pell-like equation $X^{2}-2 Y^{2}= \pm 1$; such solutions are given by the recurrence $Y_{1}=1, Y_{2}=2$ and $Y_{m}=2 Y_{m-1}+Y_{m-2}$, and so we can choose $Y$ such that $n /(3 \sqrt{2})<Y \leqslant n / \sqrt{2}$. Furthermore, it is known that for such a $Y$ and for $1 \leqslant x<Y$,
$$\{x \sqrt{2}\}+\{(Y-x) \sqrt{2}\}=\{Y / \sqrt{2}\} \tag{4}$$
if $X^{2}-2 Y^{2}=1$, and
$$\{x \sqrt{2}\}+\{(Y-x) \sqrt{2}\}=1+\{Y / \sqrt{2}\} \tag{5}$$
if $X^{2}-2 Y^{2}=-1$. Indeed, this is a statement of the fact that $X / Y$ is a best rational approximation to $\sqrt{2}$, from below in the first case and from above in the second.

Now, consider the sequence $\{\sqrt{2}\},\{2 \sqrt{2}\}, \ldots,\{(Y-1) \sqrt{2}\}$. The Erdős-Szekeres theorem tells us that this sequence has a monotone subsequence with at least $\sqrt{Y-2}+1>\sqrt{Y}$ elements; if that subsequence is decreasing, we may reflect (using (4) or (5)) to ensure that it is increasing. Call the subsequence $\{y_{1} \sqrt{2}\},\{y_{2} \sqrt{2}\}, \ldots,\{y_{t} \sqrt{2}\}$ for $t>\sqrt{Y}$.

Now, set $B=\{\lfloor y_{i} \sqrt{2}\rfloor: 1 \leqslant i \leqslant t\}$. We have $\lfloor y_{j} \sqrt{2}\rfloor-\lfloor y_{i} \sqrt{2}\rfloor=\lfloor(y_{j}-y_{i}) \sqrt{2}\rfloor$ for $i<j$ (because the corresponding inequality for the fractional parts holds by the ordering assumption on the $\{y_{i} \sqrt{2}\}$ ), which means that all differences between elements of $B$ are indeed in $H$. Since $|B|>\sqrt{Y}>\sqrt{n} / \sqrt{3 \sqrt{2}}$, this is the required set.