The Oddtown problem modulo a composite number
Preprint
Abstract
A family of subsets $\mathcal{A}$ of an $n$-element set is called an $\ell$-Oddtown if the sizes of all sets are not divisible by $\ell$, but the sizes of pairwise intersections are divisible by $\ell$. Berlekamp and Graver showed that when is a $\ell$ is a prime, the maximum size of an $\ell$-Oddtown is $n$. For composite moduli with $ω$ distinct prime factors, the argument of Szegedy gives an upper bound of $ωn-ω\log_2 n$ on the size of an $\ell$-Oddtown. We improve this to $ωn-(2ω+\varepsilon)\log_2 n$ for most $\ell$ and $n$ using a combination of linear algebraic and Fourier-analytic arguments.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- The 𝑝-adic Kakeya conjectureJournal of the American Mathematical Society, 2023
- Proof of the Kakeya set conjecture over rings of integers modulo square-free NCombinatorial Theory, 2021
- A Note on Explicit Ramsey Graphs and Modular SievesCombinatorics, Probability and Computing, 2003
- Superpolynomial Size Set-systems with Restricted Intersections mod 6 and Explicit Ramsey GraphsCombinatorica, 2000
- On set intersectionsJournal of Combinatorial Theory, Series A, 1980
- Boolean designs and self-dual matroidsLinear Algebra and its Applications, 1975
- On Subsets with Intersections of Even CardinalityCanadian Mathematical Bulletin, 1969