0

I'm doing some archeology and trying to understand a claim. As summed up by David Roberts, on the FOM list in 2011:

Let the statement "every infinite sequence of rationals in [0,1] has an infinite Cauchy 1/n subsequence" be denoted CSR. I have seen [Friedman] make this similar statements involving CSR several times…

In this MO answer, Andrej Bauer notes that CSR is false in the effective topos:

Consider a Specker sequence which has no accumulation point in a strong sense, so it cannot have a convergent subsequence.

What I'm currently puzzling over is that CSR appears false classically, too. Let $F$ be the Fibonacci sequence, and let $p$ be the sequence of Padé approximants to the golden ratio $\phi$, or rather to the conjugate golden ratio $\phi - 1$:

$$p_i = \frac{F_i}{F_{i+1}}$$

$p$ satisfies CSR; it converges to $\phi - 1$. But now define the sequence $q$:

$$q_i = \sum_{0}^{i}{p_i} \pmod{1}$$

$q$ is quasirandom and should visit every Cauchy bucket infinitely often, just like $\phi$. I wrote some Python code to verify this claim; try something like asBuckets(f, 400, 8) to take $q_{400}$ with $2^8$ binary Cauchy buckets. At the same time, $q : \mathbb{N} \to \mathbb{Q}$ is an infinite sequence of rationals.

I think that Friedman knew all of this. So, what hidden assumptions are not stated in Friedman's wording of CSR?

Corbin
  • 424
  • 6
    I don’t follow why you think $(q_i)$ should be a counterexample to CSR. Here’s the simple classical proof outline for CSR: (1) any infinite sequence in $[0,1]$ has a convergent subsequence; then (2) for any specified modulus of converegence/Cauchyness, any Cauchy sequence has a subsequence converging at the specified rate. It seems clear how to apply these steps to your $(q_i)$? – Peter LeFanu Lumsdaine May 15 '22 at 16:12
  • 4
    Visiting every Cauchy bucket makes it easier to find convergent subsequences. – Noah Schweber May 15 '22 at 18:15
  • 2
    To clarify my previous comment: CSR doesn't assert that there is a unique such subsequence - in any sense. Having the initial sequence be "randomly spread out" just means it has lots of such rapidly-convergent subsequences, converging to lots of different things. (Separately, I think this would be more appropriate for MSE.) – Noah Schweber May 16 '22 at 17:30
  • @NoahSchweber: I have no problem with this being moved to MSE; I thought MO was the proper place for archeological queries, but I don't really care either way. – Corbin May 16 '22 at 18:39
  • I understand what Peter and Noah are saying. I think that my issue must be with selecting an infinite subsequence. The terms of $q_i$ do visit every Cauchy bucket, but they do not stay; arithmetic subsequences of $q_i$ drift in and out of buckets. So I'm not exactly sure how to select an infinite subsequence without AoC. But this is classical set theory, so AoC is fine. (And I'm voting to close.) – Corbin May 16 '22 at 18:45
  • 1
    @Corbin It doesn't matter that they don't stay (and AoC plays no role here). For example: pick the first element that lands in the first "level-1" Cauchy box $B_1$; now pick the first element after that one that lands in the first "level-2" Cauchy subbox $B_2$ of $B_1$; now pick the first element after that one that lands in the first "level-3" Cauchy subbox $B_3$ of $B_2$; etc. This process is totally choice-free due to the "pick the first" bit, and is quickly convergent. I think you might be thinking of "subsequence" in the more restrictive sense of just throwing away an initial segment? – Noah Schweber May 16 '22 at 18:50

0 Answers0