Source-linked AI summary
On cancellative pairs of families of subsets
Yijia Fang, Hao Huang
TL;DR
The paper asks how large the product of two cancellative families of subsets can be. Using Sinkhorn scaling and an entropy proof, it establishes the optimal upper bound |A||B| ≤ 2.25^n, matching Tolhuizen’s (2.25−o(1))^n construction and separating cancellative from recovering pairs.
Problem
The central problem is determining the optimal growth rate of |A||B| for cancellative pairs of families of subsets.
Method
The paper applies the entropy method, using Sinkhorn’s theorem to construct a suitable distribution over the two families.
Results
2.25^n is the optimal upper bound for cancellative pairs, matching Tolhuizen’s (2.25−o(1))^n construction.
Takeaways & Limitations
The result determines μ_can = 2.25 and yields μ_rec < 2.25 = μ_can for recovering pairs.
Takeaways & Limitations
The paper leaves open whether the symmetric optimum G(n) is always attained by a linear-algebraic construction and whether the technique can settle the Sandglass Conjecture.
Abstract
from arXiv · showhide
A pair $(\mathcal{A}, \mathcal{B})$ of families of subsets of $[n]$ is cancellative if whenever $A, A' \in \mathcal{A}, B \in \mathcal{B}$ satisfy $A \cup B=A' \cup B$, then $A=A'$, and whenever $A \in \mathcal{A}, B, B' \in \mathcal{B}$ satisfy $A \cup B=A \cup B'$, then $B=B'$. We show that for every cancellative pair $(\mathcal{A}, \mathcal{B})$, the inequality $|\mathcal{A}||\mathcal{B}| \le 2.25^n$ holds, matching Tolhuizen's $(2.25-o(1))^n$ lower bound construction.
1 Introduction
The paper settles the cancellative-pair problem by proving an upper bound of 2.25^n, matching Tolhuizen’s lower-bound construction. It also separates cancellative and recovering pairs, with the latter having strictly smaller optimal growth.
- Related concepts: Recovering pairs are stronger than cancellative pairs, but the converse fails; a cancellative example can have |A||B| = 9 > 8 = 2^3.
- Prior work: Prior bounds for non-symmetric cancellative pairs improved from 2.3264^n to 2.2682^n before this paper’s 2.25^n result.
- Main result: Tolhuizen’s (2.25−o(1))^n construction matches the upper bound asymptotically, so μ_can = 2.25.
- Consequences: The result implies μ_rec < 2.25 = μ_can, creating a positive separation between the optimal growth rates.
2 The proof
The proof combines Sinkhorn scaling with an entropy argument. A carefully constructed joint distribution makes the chosen sets uniform and conditionally independent, while cancellativity supplies the entropy identities needed to derive the 2.25^n bound.
- Sinkhorn scaling: Sinkhorn’s theorem scales the positive matrix K with entries K_A,B = 3^−|A∪B| so its row and column sums are uniform.Positive weights r_A and s_B define the scaled matrix and the associated joint distribution.
- Random construction: The resulting random variables X and Y are uniform on A and B, though generally dependent before conditioning.
- Random construction: Adding M as a random superset of U = X∪Y makes X and Y conditionally independent given M.The factorization of the joint probability into an A-only and B-only part yields the conditional independence.
- Entropy argument: Cancellativity means that U together with either X or Y determines the other set, producing the entropy equalities used in the proof.
- Entropy argument: Coordinatewise entropy inequalities are established through a binary-variable Markov-chain lemma and then combined to complete the theorem.The construction gives R → U → M, allowing Lemma 2.2 to finish the required inequality.
3 Tolhuizen’s construction
Tolhuizen’s construction uses a carefully chosen binary matrix to build a symmetric cancellative pair whose size reaches (2.25−o(1))^n. Random matrix analysis and an anti-concentration argument explain both the construction’s scale and why concentrated column sums cannot improve it.
- Construction: Tolhuizen constructs a symmetric pair A = B = F_M,w using a carefully chosen k × n matrix M over F2 and a most popular vector w.The family is defined through invertible k-column submatrices and their column sums.
- Construction: For k = n/3, M_S is the submatrix indexed by S, and σ(S) is the sum of its columns in F_2^k.These objects determine membership in F_M,w and support the cancellativity proof.
- Cancellativity: The pair is cancellative because B∆C ⊂ A and invertibility of M_A forces the zero column sum on B∆C to imply B = C.The same argument applies symmetrically because the construction sets A = B.
- Size analysis: A random binary matrix has, in expectation, at least a γ proportion of k-subsets with invertible M_S, yielding a matrix with many such subsets.The entries of M are chosen independently as 0 or 1 with probability 1/2, and linearity of expectation gives the existence claim.
- Size analysis: (1.5 + o(1))^n is the resulting family-size scale, obtained from the invertible-subset count and Stirling’s approximation.Since the pair is symmetric, this corresponds to a product size of (2.25 − o(1))^n.
- Limitation of concentration: The anti-concentration result rules out obtaining a larger family by making column sums unusually concentrated among mostly invertible submatrices.If most k × k submatrices are invertible, no column-sum value has more than a subexponential-factor multiple of uniform mass.
4 Concluding Remarks
The concluding remarks identify open questions about the structure of optimal cancellative constructions and whether the probabilistic technique can settle the Sandglass Conjecture.
- Open questions: For n ≤8, computer search suggests the symmetric optimum is always attained by a linear algebraic construction.The paper leaves whether this holds for every n as an open question.
- Open questions: At n = 4, the optimal non-symmetric construction found by computer search has |A||B| = 18.It uses A = {{1}, {2}, {3}} and B = {{1}, {2}, {3}, {1, 4}, {2, 4}, {3, 4}}.
- Open questions: The Sandglass Conjecture asserts that recovering pairs satisfy |A||B| ≤2^n under unique determination by A ∪B and A ∩B.The conjecture is presented as an expected result for recovering pairs.
- Method outlook: The proof can incorporate additional random variables and entropy constraints related to intersections, potentially extending the probabilistic method beyond the current argument.Introducing V = X ∩Y yields constraints involving U, V, X, and Y.
- Method outlook: Choosing λ = 1/3 optimizes the current bound, while other λ values may provide further entropy inequalities; extending the method to settle the Sandglass Conjecture remains open.The paper specifically identifies this extension as a direction for future work.