Babai and Frankl's Oddtown Question for Composite Moduli
An -Oddtown is a family of subsets of an -element set whose set sizes are not divisible by while all pairwise intersection sizes are. Berlekamp and Graver showed the maximum size is for prime , Babai and Frankl extended this to prime powers and asked whether still holds for other moduli, a question open even for . Bukh, Chao and Zheng answer it negatively with an explicit superlinear construction, complemented by new upper bounds.
- Result
- Disproved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Construction
- Field
- Extremal set theory
- Posed by
- László Babai, Péter Frankl
- Year posed
- 1992
- Years open
- 33y
- Solved
- 2025-08-30
- Model
- GPT-5.6 Sol
- Vendor
- OpenAI
- Collaborators
- Boris Bukh, Ting-Wei Chao, Zeyu Zheng
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 20 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The lower-bound construction in Section 2 was first proposed by GPT-5.6 Sol in response to prompts from the authors; the upper-bound results were obtained without AI assistance. (The disclosure was added in the paper's second version.)