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.
Source: §1 · p. 1Method
The paper applies the entropy method, using Sinkhorn’s theorem to construct a suitable distribution over the two families.
Source: §2 · p. 2Results
2.25^n is the optimal upper bound for cancellative pairs, matching Tolhuizen’s (2.25−o(1))^n construction.
Source: §1 · p. 2Takeaways & Limitations
The result determines μ_can = 2.25 and yields μ_rec < 2.25 = μ_can for recovering pairs.
Source: §1 · p. 2The 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.
Source: §4 · pp. 6–7
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.Source: §1 · p. 1
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.Source: §1 · p. 1
Main result
- Tolhuizen’s (2.25−o(1))^n construction matches the upper bound asymptotically, so μ_can = 2.25.Source: §1 · p. 2
Consequences
- The result implies μ_rec < 2.25 = μ_can, creating a positive separation between the optimal growth rates.Source: §1 · p. 2
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.Source: §2 · pp. 2, 4
Random construction
- The resulting random variables X and Y are uniform on A and B, though generally dependent before conditioning.Source: §2 · p. 4
- 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.Source: §2 · p. 4
Entropy argument
- Cancellativity means that U together with either X or Y determines the other set, producing the entropy equalities used in the proof.Source: §2 · p. 5
- 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.Source: §2 · pp. 4–5
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.Source: §3 · pp. 5–6
- 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.Source: §3 · p. 6
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.Source: §3 · p. 6
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.Source: §3 · p. 6
- (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.Source: §3 · pp. 5–6
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.Source: §3 · p. 6
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.Source: §4 · p. 6
- 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}}.Source: §4 · p. 7
- 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.Source: §4 · p. 7
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.Source: §4 · p. 7
- 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.Source: §4 · p. 7