Group constructions cannot refute the Set Cover Conjecture, including tensor powers
Pratt (STOC 2024, arXiv:2311.02774, Corollary 1.12) showed that if the Set Cover Conjecture holds, then for every k the asymptotic rank of the balanced tripartitioning tensor T_k is at least tau_k = 8^k * C(3k,k) * C(2k,k) / 27^k. A natural way to bound this rank, and Pratt's own route to rank at most 8^k/2, is a group construction: maps f1, f2, f3 from k-subsets of a 3k-set to a group G with f1(A) f2(B) f3(C) = 1 exactly when A, B, C are pairwise disjoint (a partition analogue of the Cohn-Umans triple product property). We formalise that no such construction, in any finite group, abelian or…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-10-28-000017
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-28-000017/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-28-000017/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'