An Improved Upper Bound for Recovering Pairs

Abstract

We prove that every recovering pair $(\mathcal{A},\mathcal{B})$ of nonempty families of subsets of an $n$-element set satisfies $$|\mathcal{A}||\mathcal{B}|\le {\left(\frac{223949}{100000}\right)}^n=(2.23949{)}^n.$$ A result of Mond, Souza and Versteegen, combined with the sharp $(9/4{)}^n$ bound of Fang and Huang for cancellative pairs, gives $(2.2499{)}^n$ for recovering pairs. We improve this to $(2.23949{)}^n$. The proof combines two entropy inequalities. One is derived directly from the recovering property, while the other applies the Fang-Huang bound to families obtained from the original pair by a construction of Mond, Souza and Versteegen. The two inequalities are then combined by a convex combination.

arXiv commentComputational supplement, verifiers and outputs are available at https://doi.org/10.5281/zenodo.23093260