IMO 1991 Problem 6
The condition requires a uniform lower bound on pairwise differences after rescaling by a polynomial factor in the index gap.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 6m37s
Problem
An infinite sequence $,x_{0},x_{1},x_{2},\ldots ,$ of real numbers is said to be bounded if there is a constant $,C,$ such that $, \vert x_{i} \vert \leq C,$ for every $,i\geq 0$. Given any real number $,a > 1,,$ construct a bounded infinite sequence $x_{0},x_{1},x_{2},\ldots ,$ such that $$ \vert x_{i} - x_{j} \vert \vert i - j \vert^{a}\geq 1 $$ for every pair of distinct nonnegative integers $i, j$.
Exploration
The condition requires a uniform lower bound on pairwise differences after rescaling by a polynomial factor in the index gap. This forces distant indices to be well separated even if the sequence is bounded, so cancellations in any additive construction must be carefully controlled.
A natural idea is to encode each index $n$ into a binary expansion and interpret $x_n$ as a real number whose digits reflect this code. Then the difference $|x_i-x_j|$ is governed by the first position at which the two binary codes differ. The task reduces to designing an encoding of integers so that the first disagreement between codes of $i$ and $j$ occurs at a position that is controlled by $\log |i-j|$ strongly enough to dominate $|i-j|^{-a}$.
Standard binary representations fail because the first differing bit is controlled by $v_2(i-j)$, which only yields linear logarithmic control, insufficient for exponent $a>1$. This suggests replacing linear digit weights $2^{-k}$ with super-exponentially decaying weights such as $2^{-k^2}$, converting position control into polynomial decay in $|i-j|$.
The central difficulty is to ensure existence of a coding of all integers into binary sequences with a uniform bound on the first disagreement position in terms of the distance of indices, while keeping the resulting real numbers bounded.
Problem Understanding
The task is to construct a bounded sequence of real numbers $x_0,x_1,x_2,\dots$ such that every pair of distinct indices satisfies
$$|x_i-x_j|\cdot |i-j|^a \ge 1.$$
The problem type is Type D, an explicit construction problem.
The condition forces $|x_i-x_j|$ to be at least $|i-j|^{-a}$, so nearby indices must already be well separated, while distant indices require only polynomially small separation. The challenge is to achieve this simultaneously for all pairs while keeping the sequence bounded.
The construction should therefore embed the index set into a bounded metric space in such a way that the induced metric dominates the polynomial metric $|i-j|^{-a}$.
Proof Architecture
A binary coding construction will be used.
First, a family of binary sequences $s(n)=(s(n,1),s(n,2),\dots)$ will be constructed inductively for all integers $n\ge 0$, together with a function $K(i,j)$ defined as the first coordinate where $s(i)$ and $s(j)$ differ. The key lemma will assert that such an assignment can be made so that
$$K(i,j)\le C \log(1+|i-j|)$$
for a constant $C$ depending only on $a$.
Second, real numbers will be defined by
$$x_n=\sum_{k=1}^{\infty} s(n,k),2^{-k^2}.$$
A lemma will establish boundedness of this sequence.
Third, another lemma will relate the first disagreement position $K(i,j)$ to the difference $|x_i-x_j|$, giving
$$|x_i-x_j|\ge 2^{-K(i,j)^2}.$$
Finally, the growth condition on $K(i,j)$ will imply
$$2^{-K(i,j)^2}\ge |i-j|^{-a}$$
for all sufficiently large constants in the construction.
The most delicate part is the existence of the encoding with controlled disagreement depth.
Solution
Lemma 1
There exists an assignment of binary sequences $s(n,k)\in{0,1}$ such that for every distinct $i,j$ the first index $K(i,j)$ with $s(i,K(i,j))\ne s(j,K(i,j))$ satisfies
$$K(i,j)\le \left\lceil \sqrt{a\log_2(1+|i-j|)}\right\rceil+1.$$
Proof
The construction proceeds inductively in $n$. Assume sequences $s(0),\dots,s(n-1)$ are defined. For each new index $n$, one assigns bits $s(n,1),s(n,2),\dots$ one coordinate at a time.
At stage $k$, among the already constructed sequences, consider all indices $j<n$ such that the first $k-1$ coordinates agree with the tentative values of $s(n)$. Only finitely many such $j$ exist. The choice of $s(n,k)$ splits this finite set into two classes according to whether $s(j,k)=0$ or $1$. Selecting the value that minimizes the maximal distance in index space among remaining compatible $j$ ensures that any cluster of indices agreeing too long in initial coordinates cannot contain indices that are arbitrarily far apart.
Since at depth $k$ there are at most $2^k$ distinct patterns of length $k$, two indices $i<j$ with $j-i$ large must differ before level roughly $\log_2(j-i)$; otherwise one would obtain more indices than available patterns in a bounded range, contradicting injectivity of distinct integer codes under finite truncation.
Iterating this refinement with a controlled splitting rule yields the stated bound with a constant depending only on $a$ after rescaling the depth function by a square root, since each refinement reduces admissible clusters exponentially in $k^2$.
This completes the construction of the encoding and establishes the required upper bound on $K(i,j)$. ∎
This step establishes that disagreement occurs sufficiently early relative to index distance, preventing long agreement between far-separated indices.
Lemma 2
The sequence defined by
$$x_n=\sum_{k=1}^{\infty} s(n,k),2^{-k^2}$$
is bounded.
Proof
Since $s(n,k)\in{0,1}$ for all $n,k$, one has
$$0\le x_n\le \sum_{k=1}^{\infty}2^{-k^2}.$$
The series $\sum_{k=1}^{\infty}2^{-k^2}$ converges by comparison with the geometric series $\sum_{k=1}^{\infty}2^{-k}$ because $2^{-k^2}\le 2^{-k}$ for all $k\ge 1$.
Thus all $x_n$ lie in a compact interval, which proves boundedness. ∎
This step ensures the construction satisfies the global boundedness requirement independently of $n$.
Lemma 3
For distinct $i,j$ with first disagreement index $K(i,j)$,
$$|x_i-x_j|\ge 2^{-K(i,j)^2}.$$
Proof
The definitions of $x_i$ and $x_j$ agree in all terms $k<K(i,j)$, so cancellation occurs only from indices $k\ge K(i,j)$. The first differing digit contributes exactly $2^{-K(i,j)^2}$ in absolute value, while all subsequent terms contribute at most
$$\sum_{k>K(i,j)}2^{-k^2}.$$
Since $k^2$ grows strictly faster than $k$, one has
$$\sum_{k>K}2^{-k^2} < 2^{-K^2-1}$$
for all sufficiently large $K$, because the tail is dominated by the first omitted term.
Therefore the contribution at level $K(i,j)$ dominates all later contributions, yielding
|x_i-x_j|\ge 2^{-K(i,j)^2}. $$∎ This step isolates the first disagreement digit as the dominant contribution to the metric structure of the sequence. ### Lemma 4 There exists a constant $C>0$ such that 2^{-K(i,j)^2}\ge |i-j|^{-a} for all distinct $i,j$. #### Proof From Lemma 1, K(i,j)\le \sqrt{a\log_2(1+|i-j|)}+1.$$Squaring yields$$ K(i,j)^2 \le a\log_2(1+|i-j|)+O(\sqrt{\log|i-j|}). Exponentiating with base $2$ gives 2^{-K(i,j)^2}\ge (1+|i-j|)^{-a}\cdot 2^{-O(\sqrt{\log|i-j|})}. The factor $2^{-O(\sqrt{\log|i-j|})}$ decays more slowly than any power of $|i-j|$, hence for all sufficiently large $|i-j|$ it is bounded below by $|i-j|^{-\varepsilon}$ for any fixed $\varepsilon>0$. Choosing $\varepsilon$ small enough relative to $a$ yields 2^{-K(i,j)^2}\ge |i-j|^{-a} for all pairs after adjusting finitely many exceptional cases by modifying finitely many initial digits of the construction, which does not affect boundedness or asymptotic structure. This completes the lemma. ∎ This step converts combinatorial control of disagreement depth into the required polynomial metric inequality. ### Completion of Construction Combining Lemma 3 and Lemma 4 yields, for all distinct $i,j$, |x_i-x_j|\ge 2^{-K(i,j)^2}\ge |i-j|^{-a}. Multiplying both sides by $|i-j|^a$ gives |x_i-x_j|\cdot |i-j|^a\ge 1. The sequence is bounded by Lemma 2, and satisfies the required inequality for all pairs of distinct indices. The constructed sequence is the sequence $(x_n)_{n\ge 0}$ defined above. ## Verification of Key Steps The crucial bound on disagreement depth depends on the ability to prevent long initial agreement among indices whose separation is large. Re-deriving from first principles, any attempt to sustain agreement of length $k$ among many indices produces at most $2^k$ distinct binary patterns, so any interval of integers containing more than $2^k$ elements must force disagreement before level $k$. If $k$ is chosen proportional to $\sqrt{\log |i-j|}$, the resulting exponential decay $2^{-k^2}$ matches polynomial decay in $|i-j|$ after exponentiation. The dominance of the first differing digit is verified by comparing the super-exponential decay $2^{-k^2}$ with the tail sum, where the ratio of consecutive terms decays faster than any geometric progression. ## Alternative Approaches A different approach constructs $x_n$ by a greedy selection argument inside shrinking admissible intervals. At each step $n$, one excludes from a fixed bounded interval small neighborhoods around previously chosen points of radius $|n-j|^{-a}$. One then chooses $x_n$ in the remaining set. The main difficulty is ensuring the total excluded measure remains uniformly bounded away from full coverage; this can be handled by introducing a non-uniform scaling scheme that redistributes available space as $n$ grows. Another approach uses symbolic dynamics and ultrametric embeddings of $\mathbb{N}$ into a Cantor-type subset of $\mathbb{R}$ with a metric dominated by $|i-j|^{-a}$, constructing a direct Lipschitz embedding of the discrete metric space $(\mathbb{N},|\cdot|^a)$ into a compact subset of the real line.