The Oddtown problem modulo a composite number

2025/08/30 by Bukh, Boris, Chao, Ting-Wei, Zheng, Zeyu
#05B20 #05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2509.00586

Abstract

A family of subsets A of an n-element set is called an ℓ-Oddtown if the sizes of all sets are not divisible by ℓ, but the sizes of pairwise intersections are divisible by ℓ. Berlekamp and Graver showed that when is a ℓ is a prime, the maximum size of an ℓ-Oddtown is n. For composite moduli with ω distinct prime factors, the argument of Szegedy gives an upper bound of ωn-ωlog₂ n on the size of an ℓ-Oddtown. We improve this to ωn-(2ω+ε)log₂ n for most ℓ and n using a combination of linear algebraic and Fourier-analytic arguments.

Citations

• Low-complexity approximations for sets defined by generalizations of affine conditions
• The p-adic Kakeya conjecture

Related

• Covering systems with odd moduli
• On odd covering systems with distinct moduli
• Upper bounds on the second largest prime factor of an odd perfect number
• On the Mod-6 Town Rules
• Small Composite Numbers in Orbits of Linear Maps