Source-linked AI summary
The Oddtown problem modulo a composite number
Boris Bukh, Ting-Wei Chao, Zeyu Zheng
TL;DR
The paper asks whether the prime-power bound f_ℓ(n)≤n extends to composite moduli. It constructs large composite-modulus Oddtowns and develops algebraic and Fourier-analytic upper bounds, showing f_ℓ(n)=(ω+o(1))n while improving previous logarithmic savings for broad classes of moduli.
Problem
Babai and Frankl asked whether f_ℓ(n)≤n remains sharp when ℓ is not a prime power, an issue open even for ℓ=6.
Source: §1 · pp. 1–2Method
The paper combines projective-space hyperplane-complement constructions, low-rank superposition via the Chinese remainder theorem, and linear-algebraic and Fourier-analytic upper-bound arguments.
Source: §2.2 · p. 5Results
The construction proves f_ℓ(n)=(ω+o(1))n, while the upper bounds more than double Szegedy’s ω log n saving and add an ε log n improvement in a broad odd-prime-factor setting.
Source: §1 · p. 2Takeaways & Limitations
The leading constant ω in the composite-modulus upper bound cannot be improved, and stronger logarithmic savings are available for the stated modulus classes.
Source: §1 · p. 2The paper notes that making ε independent of ℓ would require improving the fraction 1/(36p^2) in Lemma 3.3 to an absolute constant.
Source: §1 · p. 3
Abstract
from arXiv · showhide
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 $\ell$ is a prime, the maximum size of an $\ell$-Oddtown is $n$. Babai and Frankl extended this to prime powers, and asked whether the maximum size is still $n$ when $\ell$ is not a prime power, a question that was open even for $\ell=6$. For square-free composite moduli with $\omega$ distinct prime factors, the argument of Szegedy gives an upper bound of $\omega n-\omega\log_2 n$ on the size of an $\ell$-Oddtown. We answer the question of Babai and Frankl in the negative by constructing $\ell$-Oddtowns of size $\omega n-o(n)$, which shows that the leading term $\omega n$ cannot be improved. We also improve Szegedy's upper bound to $\omega n-(2\omega +\varepsilon)\log_2 n$ for most $\ell$ and $n$ using a combination of linear algebraic and Fourier-analytic arguments.
1. Introduction
The paper studies maximum-size ℓ-Oddtown families for composite moduli, answering an open question by constructing near-ωn examples and sharpening known upper bounds. Its methods combine finite-field constructions, linear algebra over prime-power rings, orthogonality, and Fourier analysis.
Problem setting
- The paper studies families whose set sizes are nonzero modulo ℓ while pairwise intersection sizes vanish modulo ℓ, with f_ℓ(n) denoting the maximum family size.When ℓ is a prime power, the known sharp bound is f_ℓ(n)≤n.Source: §1 · pp. 1–2
- The motivating open problem asked whether the sharp prime-power bound f_ℓ(n)≤n persists for non-prime-power ℓ, even for ℓ=6.For one distinct prime factor, the bound remains sharp by basic linear algebra.Source: §1 · p. 2
New results
- For ℓ with at least two distinct prime factors, the construction gives f_ℓ(n)=(ω+o(1))n for sufficiently large n, so the leading constant ω is unavoidable.The result answers Babai and Frankl’s question negatively and shows that the trivial upper-bound constant cannot be improved.Source: §1 · p. 2
Construction
- The lower-bound construction superimposes ω ℓ-Oddtowns using low inner rank in the wrong characteristics and a Chinese-remainder-theorem gadget, at the cost of few extra elements.Each component uses complements of hyperplanes in projective spaces over fields of characteristic p^t.Source: §1 · p. 2
New results
- Theorem 1.2 more than doubles Szegedy’s ω log n saving and applies to general, including non-square-free, composite moduli.The stated theorem covers every n≥4 when ℓ has at least two distinct prime factors.Source: §1 · p. 2
- Theorem 1.3 further improves the upper bound by an ε log n term for moduli with at least two distinct odd prime factors, with ε depending on the odd prime divisors of ℓ.The parameter excludes the smallest odd prime divisor when defining the relevant product.Source: §1 · p. 2
Upper bounds
- The upper bounds exploit orthogonality between subspaces in Szegedy’s argument, extending the improvement from prime to prime-power moduli through Lemma 3.1.For square-free moduli, orthogonality replaces the ω log n saving by 2ω log n before the additional ε log n improvement.Source: §1 · p. 2
- A further ε log n improvement uses rank bounds for 0–1 matrices with distinct rows and columns, excluding cases where both log r and log c approach the rank.The paper’s main lemma strengthens the basic lower bound d≥max(log r,log c) in this setting.Source: §1 · p. 3
2. The lower bound
The lower-bound constructions combine prime-power blocks with correction gadgets to build ℓ-Oddtowns while controlling their matrix structure. For ℓ = 6, this gives a near-optimal bound of 2n − 4 log n + 11.
2.4. Superimposing the blocks.
- Superimposing the matrices M_i preserves their diagonal Gram blocks, and the mixed blocks can be canceled modulo ℓ because each has low rank after combining prime-power bounds via the Chinese remainder theorem.The resulting correction uses factorization ranks over the relevant rings; Lemma 2.7 relates the separate prime-power ranks to rank modulo ℓ.Source: §2 · p. 4, §2.1 · p. 4, §2.4 · p. 8
2.1. Inner rank.
- Inner rank is the minimum factorization dimension over a commutative ring, and estimates must use Z/p^αZ rather than only F_p because reduction modulo p can hide large factorization rank.The inner rank equals ordinary rank over fields and obeys invariance, product, tensor-product, and block-diagonal subadditivity properties.Source: §2.1 · p. 4
2.2. Complements of hyperplanes.
- Complements of projective hyperplanes form 0–1 matrices whose row weights and pairwise dot products are explicit, while their inner rank over Z/p^αZ grows polynomially in the projective dimension.For example, the rows of N(3,3) give a 6-Oddtown with 13 sets on 13 elements.Source: §2.2 · pp. 5–6
2.3. Blocks of a prescribed order.
- For every sufficiently large scale R and each prime-power factor index i, a square 0–1 matrix of order d with cR ≤ d ≤ R has ℓ-Oddtown rows and low inner rank modulo every other factor.Tensor products supply the required divisibility, while block-diagonal sums extend the construction to every sufficiently large order m with only O_ℓ(log m) blocks.Source: §2.3 · pp. 6–8
- For every sufficiently large m and each factor index i, block-diagonal assembly produces an m-by-m ℓ-Oddtown matrix M_i with controlled inner ranks modulo the other prime-power factors.The construction fills the remaining bounded size with 1-by-1 identity blocks, preserving the Oddtown condition.Source: §2.3 · p. 8
2.4. Superimposing the blocks.
- Lemma 2.8 converts any integer matrix of inner rank r into binary matrices with vanishing diagonal Gram matrices and mixed Gram matrix −W modulo ℓ, using at most (2ℓ−1)(ℓ−1)^2r columns.The gadget decomposes −W into at most r(ℓ−1)^2 binary outer products and concatenates corresponding column pairs.Source: §2.4 · p. 9
- Theorem 1.1 constructs an ℓ-Oddtown matrix with members on n ground elements by superimposing block matrices and correcting mixed blocks.The correction matrices satisfy UU^T ≡ VV^T ≡ 0 and UV^T ≡ −W modulo ℓ, making the final Gram congruence establish the Oddtown property.Source: §2.4 · p. 10
- For ℓ = 6, the construction gives f_6(n) ≥ 2n − O_6((log n)^3), while the accompanying upper bound yields f_6(n) ≤ 2n − 4 log n + 11.Here the exponent 3 follows from the maximum term in the relevant rank estimate plus the block-diagonal summation cost.Source: §2.4 · p. 10
3. The upper bounds
This section develops upper bounds for ℓ-Oddtowns by combining a prime-power linear-algebraic lemma with Fourier-analytic estimates. It bounds 0–1 vectors in finite-field subspaces through random linear images and admissible submatrices, yielding improved logarithmic deficits under the stated conditions.
3.1. Algebraic part: proof of the 2ω log n bound.
- Every ℓ-Oddtown satisfies |A| ≤ ωn − 2ω log n + 11 via a prime-power algebraic lemma and a Boolean-intersection dimension bound.The algebraic lemma bounds the dimension of the span of the v_j modulo p by k/2, while the Boolean-subspace lemma converts this into bounds on the classes A_i.Source: §3.1 · p. 11
3.2. Proof of Theorem 1.3.
- |A| ≤ ωn − (2ω + ε) log n for sufficiently large n, improving the upper bound when the prime-divisor conditions of Theorem 1.3 hold.The proof separates good and bad odd prime divisors; if at least two odd prime divisors are bad, it instead obtains |A| ≤ ωn − n^0.2 + ωℓ.Source: §3.2 · pp. 12–13
- If two odd prime divisors are bad, then |A| ≤ ωn − n^0.2 + ωℓ; otherwise, at most one odd prime divisor is bad.The argument identifies many repeated matrix columns and deletes blocks of ℓ elements without changing the ℓ-Oddtown property.Source: §3.2 · p. 13
3.3. Analytic part: Fourier-analytic argument.
- For an odd prime p, the Fourier-analytic main lemma shows Pr[Lᵀv ∈ {0,1}^c] ≤ 3 · 2^(-d/(36p^2)) for distinct-column matrices under 36 log p ≤ d ≤ 3 log c.This probabilistic estimate is used to prove the strengthening of the Boolean-subspace lemma required in the algebraic rank argument.Source: §3.3 · p. 14
- The proof first bounds the Fourier transform of the distribution induced by applying a matrix with distinct columns to a random 0–1 vector.The transform is controlled using convolution and a cosine-based exponential estimate.Source: §3.3 · pp. 14–15
- A maximal σ-admissible submatrix is extracted to retain enough columns for the Fourier estimate, after which Fourier inversion bounds the probability mass on the Boolean cube.The argument applies the admissible-submatrix lemma with σ = d/36 and then combines the resulting bounds.Source: §3.3 · pp. 15–16
- Pr[Lᵀv ∈ {0,1}^c] ≤ 3 · 2^(-d/(36p^2)) for a uniformly random v ∈ {0,1}^d.This is the concluding estimate of Lemma 3.5.Source: §3.3 · p. 17