Source-linked AI summary
A Borsuk-Ulam theorem for adaptive continuous measurements
Mario Ullrich
TL;DR
Classical Borsuk-Ulam does not directly address adaptive measurements, whose maps may be discontinuous. This paper proves an antipodal-indistinguishability result for adaptive continuous measurements and derives a measurement lower bound for learning vectors in a ball, within one measurement of a known upper bound.
Problem
Classical Borsuk-Ulam gives indistinguishable antipodes for nonadaptive continuous maps, but adaptive measurement maps can be discontinuous and are not covered directly.
Source: §1 · p. 2Method
The paper proves an adaptive Borsuk-Ulam theorem by relating the number of measurements that distinguish antipodes to the genus of the sphere.
Source: §1 · p. 2Results
Takeaways & Limitations
For vectors in a ball, the theorem gives a necessary measurement bound for achieving error smaller than the ball’s radius.
Source: §1 · p. 2For m not a power of two, the sphere-genus method cannot close the one-measurement gap, and whether antipodal coincidences are forced at the sharper threshold remains open.
Source: §3 · p. 5
Abstract
from arXiv · showhide
We prove a Borsuk-Ulam theorem for adaptive measurements: if $2^n\le m$, then any $n$ adaptively chosen continuous functionals take identical values at two antipodal points of any sphere in $\mathbb{R}^m$. Consequently, at least $\lceil\log_2(m+1)\rceil$ adaptive continuous measurements are needed to learn the vectors of a ball in $\mathbb{R}^m$ with an error smaller than its radius, which matches the recently obtained upper bound up to one measurement. The bound extends to Bernstein widths in Banach spaces. The main idea of the proof was found by Claude Fable 5, an AI model developed by Anthropic, and we document the development in a last section.
1 The problem and the result
The section establishes an antipodal-indistinguishability bound for adaptive continuous measurements, despite adaptive measurement maps generally being discontinuous. It derives a lower bound on measurements needed to approximate every vector in a ball, within one measurement of a known upper bound.
1 The problem and the result
- Classical Borsuk-Ulam gives indistinguishable antipodes for nonadaptive continuous maps, but adaptive maps can be discontinuous, so that theorem does not directly apply.The paper’s result supplies an adaptive counterpart.Source: §1 · p. 2
- 2^n ≤ m forces some antipodal pair on the radius-R sphere to receive identical values from any n adaptive continuous measurements.Equivalently, distinguishing every antipodal pair requires 2^n ≥ m + 1.Source: §1 · p. 2
- ⌈log2(m)⌉ + 1 measurements suffice for arbitrary precision, leaving the lower and upper bounds one measurement apart at most.The bounds coincide when m is a power of two.Source: §1 · p. 2
- Below the threshold, every algorithm on a set containing the radius-R sphere has worst-case error at least R.For the radius-R ball, this matches the error of the trivial algorithm that always returns zero.Source: §1 · p. 2
- The proof uses genus: an odd part of a measurement separates antipodes on a region of genus at most one, while even level sets continue with one fewer measurement.Adaptivity is invisible within a level set because antipodal points there share previous values and face the same next functional.Source: §1 · p. 2
2 Split sets and the genus
The section defines split sets and Krasnosel’skii’s genus, then characterizes genus through odd maps and records properties used for the Borsuk-Ulam argument.
2 Split sets and the genus
- A split set separates into disjoint closed halves exchanged by x ↦ −x, assigning a consistent sign to each antipodal pair.The genus lemma connects such coverings to odd maps without zeros, using the distance functions of the split halves.Source: §2 · p. 3
- γ(K) is the least number of split sets covering K, equivalently the least k admitting a continuous odd map K → R^k \ {0}.In the covering definition, γ(K)=0 exactly when K is empty.Source: §2 · p. 3
- The genus is monotone under inclusion or continuous odd maps, is a maximum over disjoint unions, and is unchanged on a sufficiently small neighborhood.These properties support transferring bounds from level sets and slabs to their neighborhoods.Source: §2 · p. 3
- The sphere S^{m−1}_R has genus m; accordingly, every continuous odd map from it to R^k has a zero when k < m.The paper identifies this genus statement with the Borsuk-Ulam theorem.Source: §2 · p. 3
3 Proof of Theorem 1
The proof bounds the genus of any compact symmetric set on which n adaptive continuous measurements distinguish antipodes. Applying that bound to a sphere yields the theorem, while the method leaves a gap for dimensions that are not powers of two.
Proposition 4 and Theorem 1
- γ(K) ≤ 2^n−1 whenever n adaptive continuous measurements distinguish every antipodal pair in compact symmetric K.The theorem applies this bound to the sphere, whose genus is m, ruling out antipodal distinction when m ≥ 2^n.Source: §3 · pp. 4–5
Proposition 4
- The induction starts with δ(x)=λ1(x)−λ1(−x): away from its zero set, its sign splits the set into two pieces.The zero set is symmetric, and the first measurement is even on it, allowing the remaining measurements to be analyzed on level sets.Source: §3 · p. 4
- Each level set and sufficiently narrow slab of the first measurement on the zero set has genus at most h=2^{n−1}−1.Partitioning the measurement range into such slabs and grouping disjoint slabs of the same parity bounds the zero set’s genus by 2h.Source: §3 · p. 4
Remark 5
- The proof covers the sphere with 2^n−1 split sets built from sign regions off the zero set and slabs within it, yielding an odd map to R^{2^n−1} without zeros.Distance functions of the split sets construct the odd map.Source: §3 · p. 5
Remark 6
- For m not a power of two, the theorem and leave a one-measurement gap; whether antipodal coincidence is forced at n=⌈log2 m⌉ remains open.The genus method cannot close the gap because every compact symmetric K ⊆ R^m \ {0} has γ(K) ≤ m; the paper also reports a torus-based proof that ⌈log2 m⌉+1 measurements suffice for learning ball vectors with sufficiently small error.Source: §3 · p. 5
4 Subsets of Banach spaces and linear operators
The section extends the adaptive-measurement argument to Bernstein widths in Banach spaces and compares the resulting bounds with nonadaptive and linear-measurement bounds. It also states a Hilbert-space optimality result and identifies an open Banach-space question.
Bernstein widths
- The Bernstein-width argument selects a 2^n-dimensional affine slice and uses the S-induced norm to obtain a sphere where antipodes cannot be distinguished.The resulting indistinguishable inputs produce the same algorithm output; taking the supremum over the slice, center, and radius proves the claimed bound.Source: §4 · pp. 5–6
Comparison with linear measurements
- Compared with adaptive linear measurements, continuous measurements shift the error-bound index from n to 2^n−1; the paper attributes the necessity of an exponential shift to the upper bound in.The linear-measurement comparison is given in [7, Prop. 10].Source: §4 · p. 6
Bernstein widths
- For F=B_X, the Bernstein numbers satisfy b_k(S) ≤ e_k^{non}(S) ≤ δ_k(S), relating them to nonadaptive error and manifold widths.The cited passage notes that these quantities coincide, up to indexing, when X and Y are Hilbert spaces.Source: §4 · p. 6
Hilbert-space consequence
- For Hilbert spaces, the exponential speed-up of adaption is optimal up to a factor of 8 in the index.The result is stated for n ≥ 2.Source: §4 · p. 6
Limitation
- Whether the corresponding lower bound holds with a constant in all Banach spaces remains open.The method detects indistinguishable pairs f and −f on spheres, yielding Bernstein numbers; the required factorization through a continuous nonadaptive map fails in general because measurement fibers inherit discontinuous choices.Source: §4 · p. 6
5 How this paper came about: working with an AI assistant
This section recounts how an open lower-bound question about adaptive continuous measurements developed into the paper’s proof, beginning with a dialogue with Claude Fable 5. The author checked the arguments and documented the process because such collaborations were new to the field.
5.1 History of the problem
- Before this work, adaptive continuous measurements had an upper bound of ⌈log2(m)⌉+1, while the known lower bound was only n ≥ 2 and the true threshold was unclear.The upper bound recovered vectors with arbitrary precision, exponentially fewer measurements than the m linear measurements necessary and sufficient in the classical setting.Source: §5.1 · p. 7
5.2 The first prompt and the first proof
- A prompt asking only to rule out log(m)/2 measurements led to a stronger antipodal-pair bound for every n ≤ log2(m + 1) − 1.The draft used the cohomological Z2-index: the odd part of a measurement removes one unit of index, while its level sets cost a factor of two; its relative cup-product argument was difficult for the author to check.Source: §5.2 · p. 7
5.3 Toward a proof to understand
- The final threshold emerged in the genus formulation: n adaptive queries resolve a double covering of Schwarz genus at most 2n − 1.The covering-based proof used Krasnosel’skii’s genus, whose properties were established by covering arguments, leaving Borsuk–Ulam as the only topological input.Source: §5.3 · p. 8
- The proof was recast analytically using odd Tietze extensions and bump functions, then with split sets and distance functions to construct the odd map.The latter construction replaced the earlier tools without a partition of unity.Source: §5.3 · p. 8
5.4 One theorem, several dialects
- Within a few sessions, the theorem had proofs in four mathematical languages, and the paper presents the genus version for its citable properties and elementary covering proof.The author chose questions, evaluated reformulations, and checked proofs; the model produced mechanisms and drafts, which required extensive later reading, rewriting, and hand editing.Source: §5.4 · p. 8