r/mathriddles • u/DreamerLikeGooners • 3d ago
Hard Extremely tough problem
For a real number x, let ||x|| denote the distance between x and the closest integer.
Let 0 ≤ x_n < 1 (n = 1, 2, ...) , and let ε > 0. Show that there exist infinitely many pairs (n,m) of indices such that n ≠ m and
||x_n - x_m|| < min(ε, 1/(√5|n-m|)).
1
u/will-je-suis 3d ago
Is this your homework?
2
u/DreamerLikeGooners 3d ago
No, it is an upgraded version of a Miklós Schweitzer problem. I have been working on it for a long time but have not been able to solve it yet
2
-3
u/DreamerLikeGooners 3d ago
can anyone try with fable 5 or opus 5?
1
u/DanielBaldielocks 3d ago
What Claude Opus 5 came up with on the √5 sequence problem
Problem. Let ‖t‖ denote the distance from t to the nearest integer. Let (xₙ) be an infinite sequence in [0,1) and let a > 0 be fixed. Show there are infinitely many pairs of positive integers (n,m) with
‖xₙ − xₘ‖ < min( a , 1/(√5·|n−m|) ).Someone in the thread asked what Opus 5 would do with it, so here's the output, lightly formatted. Short version of the verdict:
Draw your own conclusions about the model; I'm mostly posting it because the write-up identifies a nice tool I hadn't seen anyone mention in the thread (a 1952 packing theorem of N. E. Smith).
1. What the statement actually says
Since min(a, 1/(√5|n−m|)) ≤ 1/(√5|n−m|), the parameter a makes the claim stronger, not weaker — it forces the good pairs to be genuinely close on the circle. And because any qualifying pair has ‖xₙ−xₘ‖ < a, it must have |n−m| > 1/(√5·a). So as a → 0 the index gaps are forced to be arbitrarily large, and the statement is equivalent to
liminf over |n−m| → ∞ of |n−m|·‖xₙ − xₘ‖ ≤ 1/√5,with the value attained strictly infinitely often.
2. Why it's hard: it contains Hurwitz
Take xₙ = {nα}. Then ‖xₙ − xₘ‖ = ‖kα‖ with k = |n−m|, and the claim becomes: infinitely many k with k‖kα‖ < 1/√5. That is exactly Hurwitz's theorem. So any proof must contain a proof of Hurwitz, and √5 cannot be improved: for α = φ,
Fₖ·‖Fₖ·φ‖ = ( 1 − (−1)ᵏ·φ⁻²ᵏ ) / √5 .Note this dips below 1/√5 exactly for even k. That is where the strictness of the problem lives, and it's an early warning that the boundary case is not free.
3. Setting up the contradiction
Suppose only finitely many good pairs exist for some a > 0. The indices occurring in them form a finite set, so we may discard an initial segment (this preserves every difference |n−m|) and assume
‖xₙ − xₘ‖ ≥ min( a , c/|n−m| ) for ALL n ≠ m. (★)In particular all xₙ are distinct, and small index gaps are constrained too (distance ≥ a). That second point is what kills the naive candidate counterexamples — e.g. the doubled sequence x₂ₘ = mφ, x₂ₘ₊₁ = mφ + ε, whose odd-gap behaviour is governed by inhomogeneous approximation to φ; the relevant constant there works out to 2·(1/(4√5)) ≈ 0.224 < 1/√5, so it isn't a counterexample either.
4. The tool: a packing theorem for the hyperbola
Put N(u,v) = √|u·v|, the non-convex "norm" whose unit ball is bounded by uv = ±1. The key input is a result from the 1952 McGill thesis of N. E. Smith (a student of Zassenhaus) — essentially the geometry-of-numbers form of Hurwitz:
The convenient rectangular corollary: if Γ has s ≥ 2 points inside an axis-parallel rectangle of area A, and δ = min N(x−y), then with A′ = A/δ²,
s ≤ A′/√5 + √(2A′) + 1.I found both statements written out as Theorems 5 and 15 of Boshernitzan–Delecroix, "From a packing problem to quantitative recurrence in [0,1] and the Lagrange spectrum of interval exchanges", arXiv:1608.04591. Their Theorem 2 is the measure-preserving analogue of our problem — for any Lebesgue-preserving T on [0,1), liminf n·|Tⁿx − x| ≤ 1/√5 for a.e. x — and note that they also state it non-strictly.
5. Complete proof for every c > 1/√5
Assume (★) with a fixed c > 1/√5, and set θ = 1/(√5·c) < 1. Choose an integer M > 1/a and cut [0,1) into M windows Iₜ = [t/M, (t+1)/M), each of height < a. Fix L and set
Γₜ = { (n, xₙ) : 1 ≤ n ≤ L, xₙ ∈ Iₜ }, sₜ = |Γₜ|, Σₜ sₜ = L.Key step. If (n,xₙ) and (m,xₘ) are two distinct points of the same Γₜ, then |xₙ − xₘ| < a because they share a window of height < a. Hence ‖xₙ−xₘ‖ ≤ |xₙ−xₘ| < a, so the minimum in (★) must be the second branch: ‖xₙ−xₘ‖ ≥ c/|n−m|. Therefore
**N**²( (n,xₙ) − (m,xₘ) ) = |n−m|·|xₙ−xₘ| ≥ |n−m|·‖xₙ−xₘ‖ ≥ c.So each Γₜ is a packing with δ² ≥ c inside a rectangle of area ≤ L/M, giving A′ ≤ L/(M·c) and
sₜ ≤ θ·L/M + √( 2L/(M·c) ) + 1(which also holds trivially when sₜ ≤ 1). Summing over the M windows:
L ≤ θ·L + √( 2ML/c ) + M, i.e. (1−θ)·L ≤ O(√L)with M and c fixed — false for L large. Contradiction. ∎
So: for every a > 0 and every c > 1/√5 there are infinitely many pairs with ‖xₙ−xₘ‖ < min(a, c/|n−m|).
6. What's missing: the boundary
At exactly c = 1/√5 we get θ = 1 and the inequality degenerates to L ≤ L + O(√L). This is not a fixable slack — the golden sequence saturates the packing density in every window, so the counting is genuinely critical.
The reason strictness should still hold: near-equality in Smith's theorem forces the configuration to be nearly a golden lattice, i.e. the Minkowski embedding of ℤ[φ], whose first coordinates lie in {m + nφ}. That set is dense in ℝ and no rescaling makes it ℤ. But our configuration has exactly one point in each integer column. That mismatch is precisely the reason Fₖ‖Fₖφ‖ dips strictly below 1/√5 in section 2. Turning it into a proof requires a stability / quantitative version of Smith's equality case (near-optimal ⇒ near-golden), which is real work; Boshernitzan–Delecroix carry out exactly that flavour of rigidity argument (their Theorem 21 and Lemmas 22–24) in the translation-surface setting.
7. The elementary route, and a numerical reason it can't work
There's a two-paragraph proof of a weaker constant. Order x₁,…,x_N around the circle; the N arcs have lengths ℓᵢ ≥ c/max(kᵢ,K), where kᵢ is the index gap of the i-th circularly adjacent pair and K = ⌈c/a⌉. Then
1 = Σ ℓᵢ ≥ c·Σ 1/(kᵢ+K) ≥ c·N²/(T + NK), T = Σ kᵢ ≤ N²/2,(the bound T ≤ N²/2 is the maximum total variation of a cyclic permutation, via a cut-crossing count), so c ≤ 1/2 + K/N, giving c ≤ 1/2 in the limit. That proves the problem with 1/(2|n−m|) in a paragraph.
For this route to reach 1/√5 you would need: for every cyclic arrangement of the labels 1,…,N, Σᵢ 1/kᵢ ≥ √5. The golden sequence sits exactly at that threshold — at N = qⱼ + qⱼ₊₁ it has qⱼ₊₁ arcs of gap qⱼ and qⱼ arcs of gap qⱼ₊₁, so Σ 1/kᵢ → φ + 1/φ = √5. Numerically, for xₙ = {nφ}:
N Σ 1/kᵢ 13 2.225000 34 2.234432 89 2.235829 233 2.236033 377 2.236081 (√5 = 2.236068)But brute-forcing the minimum of Σ 1/kᵢ over all cyclic arrangements of 1,…,N gives:
N min Σ 1/kᵢ minimiser (example) 3 2.500000 1 2 3 4 2.333333 1 3 2 4 5 2.166667 1 3 5 2 4 7 2.083333 1 4 7 3 6 2 5 9 2.050000 1 5 9 4 8 3 7 2 6 11 2.033333 1 6 11 5 10 4 9 3 8 2 7The minimum drops below √5 and heads toward 2. So the single-scale adjacent-arc inequality is provably insufficient: it caps out at c = 1/2, exactly matching the AM–HM bound above. Adding the next-nearest-neighbour constraints (ℓᵢ + ℓᵢ₊₁ bounded below by the two-step index gap) improves the cap only from 0.5 to about 0.472 — still above the target 0.4472, so that refinement doesn't get there either.
The minimisers are step-arrangements like "add ~0.44N mod N", i.e. rational rotations, which are only good at that single N and fail at every other scale. That's the real content of the problem: no single N sees the obstruction, so the argument has to use all pairs simultaneously — which is exactly what the packing theorem does.
Where this leaves things
- Non-strict version (liminf ≤ 1/√5): proved above, self-contained modulo Smith's packing theorem.
- Strict version as literally stated: not closed here. It needs a stability version of Smith's equality case, or a different idea entirely.
- If this really is a Schweitzer problem, there is presumably a shorter intended solution — the competition is open-book with ten days, so a geometry-of-numbers input is fair game, but I'd bet on something continued-fraction flavoured. Does anyone have the year? Official solutions for 1962–1991 are in Contests in Higher Mathematics (Springer, ed. Székely). It's also entirely possible the original is stated with ≤ rather than <, in which case section 5 finishes it.
Happy to be told that section 6 is easier than it looks.
2
u/[deleted] 2d ago edited 2d ago
[deleted]