Actually nevermind, I think I see a counterexample to the exact formulation in the OP. I haven't fully formalized it, so there may be holes, but here it is:
Imagine a "toxic piece of shared information": some type of information such that it inextricably ties together some shared bits of information S with unique bits of information U, making it impossible to define a variable that contains only the shared bits from it. If all variables in a set X are "toxic" in this way, then any redund R, even ones that straight-up copy one of the Xj, would necessarily have I(R;X−i|Xi)≥U for all Xi except Xj.
Suppose we fix a specific ϵ2, i. e., state that only variables with fewer unique bits than that qualify as redunds.
Now consider a set of variables An each variable Ani in which is a set of n independent clones of toxic-information-containing variables {X1i,…,Xni}. Any variable which is a redund over only one set of clones is a valid redund over An, and so there are n redunds like this, all mutually independent.
What would a maximal redund Ωn look like? Well, to properly screen all other redunds off, it would need to include most of the information from each individual independent redund, and so its I(Ωn;An−i|Ani) would scale with n (probably roughly equaling nU?). We can then set n arbitrarily high, so that this quantity shoots well past any fixed ϵ2. And if we discard some D bits from each redund to try and manage this, this would increasingly work against our ability to screen off redunds from An−i, and we can again scale n to make any Ωn that tries to keep its I(Ω;An−i|Ani) under control fail arbitrarily hard at the screen-off task for all-but-a-few redunds.
Concrete example: I think a binary symmetric channel should work here? I. e., set X={X1,X2}, where X2=XOR(X1,Z), X1 is a fair coin, and Z is a biased coin with bias p. We get H(X1)=H(X2)=1, I(X1;X2)=plog2p+(1−p)log2(1−p)=K, H(X1|X2)=H(X2|X1)=1−K. Then an R=X1 has I(X1;X2|R)=0, so it contains K shared bits, and I(R;X1|X2)=1−K, so it qualifies as a redund if we set ϵ2≥1−K. Then, per the construction above, we design a set whose variables are sets of those basic variables' independent clones, and watch the maximal redund explode.
The subtle caveat here is that I think we need to prove that for any variable Ω, decreasing the amount of unique information (i. e., driving I(Ω;X1|X2) down) trades off against shared information (i. e., I(X1;X2|Ω) ends up increasing), which leads to I(X1;R|Ω) growing. Specifically, we need to prove that this happens at some nontrivial, non-asymptoting rate that leads Ωn's ϵ1 in the cloned construction to scale with n, well past any small constant multiple of ϵ2.
The counter here would be a continuum of Ωs which can drive I(Ω;X1|X2) arbitrarily low at flatlining decrease in I(X1;X2|Ω). The full counter would prove that this is possible in the general case, not only in the BSC setting.
That it's impossible seems intuitively obvious (consider if that worked, what possibilities it'd unlock! the universe isn't that kind), but maybe annoying to prove and the result wouldn't be very exciting, so it's a low priority to me.[1] Still, throwing this out here in case you find this reasoning convincing.
(My guess is that "maximal redunds are possible for any sets of random variables" is too strong and we need to explicitly limit it to sets of variables that are approximately structured as sparse hierarchical graphs or something. This is probably okay, see my previous thoughts about the universe's physics selecting for that.)
Here's o3's crack at it if you want a starting point. I've found it's sometimes helpful, but I'm currently fatigued from trying to paranoidally spot the place where it's trying to slip crap past me, so I've not verified it. Looks right at a glance, if you ignore some weird parts.
[EDIT August 22 2025: This bounty is now 500$ as the earlier bounty has now been claimed. (By us.)]
A lot of our work involves "redunds".[1] A random variable Γ is a(n exact) redund over two random variables X1,X2 exactly when both
X1→X2→Γ
X2→X1→Γ
Conceptually, these two diagrams say that X1 gives exactly the same information about Γ as all of X, and X2 gives exactly the same information about Γ as all of X; whatever information X contains about Γ is redundantly represented in X1 and X2. Unpacking the diagrammatic notation and simplifying a little, the diagrams say P[Γ|X1]=P[Γ|X2]=P[Γ|X] for all X such that P[X]>0.
The exact redundancy conditions are too restrictive to be of much practical relevance, but we are more interested in approximate redunds. Approximate redunds are defined by approximate versions of the same two diagrams:
Unpacking the diagrammatic notation, these two diagrams say
ϵred≥DKL(P[X,Γ]||P[X1]P[X2|X1]P[Γ|X2])
ϵred≥DKL(P[X,Γ]||P[X2]P[X1|X2]P[Γ|X1])
This bounty problem is about the existence of a(n approximate) maximal redund Ω: a redund which contains (approximately) all the information about X contained in any other (approximate) redund. Diagrammatically, a maximal redund Ω satisfies:
Finally, we'd like our maximal redund Ω to be an approximately deterministic function of X, i.e. ϵdet≥H(Ω|X), which is equivalent to the diagram
What We Want For The Bounty
This bounty pays out $500 for establishing that there always, over any two random variables X1, X2, exists an Ω satisfying the requirements above, i.e.
... with reasonable error bounds.
What counts as reasonable error bounds? We're expecting all the other ϵ's to scale with ϵ2 in the diagrams above, and ideally be small constant multiples of ϵ2. In other words: the higher the approximation error on allowable redunds Γ, the more approximation error we allow for all the conditions on Ω. Reasonableness of error bound is partially a judgement call on our part, but small constant (like e.g. 2 or 3) multiples of ϵ2 would definitely suffice.
Bounds should be global, i.e. apply even when ϵ2 is large. We're not interested in e.g. first or second order approximations for small ϵ2 unless they provably apply globally.
If the error bounds are sufficiently reasonable, a solution to this problem will also solve our other open bounty problem, paying out another $500, for a total of $1000.
If people post major intermediate steps which are load-bearing for an eventual solution, we might allocate the bounty based on our judgement of different peoples' relative contributions; the hope is to incentivize sharing intermediate results.
We might also partially pay out for counterexamples. That's a judgement call depending on how thoroughly the counterexample kills hope of any theorem vaguely along the lines intended.
In terms of rigor and allowable assumptions, roughly the level of rigor and assumptions in the posts linked above is fine.
Some Intuition From The Exact Case
A proof in the exact case is straightforward; we'll walk through it here to build some intuition.
The exact redundancy conditions say
P[Γ|X]=P[Γ|X1]=P[Γ|X2]
wherever P[X]>0. So, we can form a bipartite graph, where each vertex represents a value x1 of X1 or a value x2 of X2, and two vertices are connected iff P[X1=x1,X2=x2]>0. Then the definition of redundancy says that, for ANY redund Γ, P[Γ|X1] and P[Γ|X2] are the same for ANY values of X1 and X2 (respectively) in the same connected component.
So, let f(X) be defined as the connected component in which X falls. For any redund Γ, P[Γ|X] must be a function of f(X) (since two X-values in the same connected component have the same P[Γ|X]). Thus
X→f(X)→Γ
f(X) is therefore a(n exactly) deterministic function of X, and (exactly) mediates between X and any redund Γ. Thus, f(X) satisfies our requirements, in the exact case (i.e. when ϵ2=0).
Alas, this proof does not easily generalize to the approximate case.
Why We Want This
This is a conjecture which we've had on the back burner for a while, and it would be relevant in many places. It would solve our other open bounty problem, it would likely be our starting point for a new version of the Telephone Theorem which more explicitly connects to the natural latents framework, and it would directly simplify the problem of computing natural latents numerically. Probably there are other use-cases which we're not thinking about right at the moment.
A lot of our work involves "redunds".