Set Systems with Restricted Intersections modulo Prime Powers

We study set systems satisfying Frankl–Wilson-type conditions modulo prime powers. We prove that the size of such set systems is polynomially bounded, in contrast with V. Grolmuszʹs recent result that for non-prime-power moduli, no polynomial bound exists. More precisely we prove the following result. Theorem.Let p be a prime and q=pk. Let μ1, …, μsbe distinct integers, 0⩽μi⩽q−1. Let X be a set of n elements and let A1, A2, …, Ambe subsets of X with the following properties: • |Ai|≢μℓ (mod q) for alli, ℓ, 1⩽i⩽m, 1⩽ℓ⩽s. • For alli, j (1⩽i<j⩽m), there exists ℓ (1⩽ℓ⩽s) such that|Ai∩Aj|≡μℓ(mod q).Then[formula]where D ⩽2s−1.D is the minimum degree of polynomials “separating” the set {μ1, …, μs} from the sizes of the Ai modulo q (q=pk). Let D(s, k) be the maximum value of D for fixed s and k (L and p vary). The asymptotic behavior of the function D(s, k) turns out to be rather complicated; we establish polynomially related upper and lower bounds on D(s, k). These bounds give us an idea of the limitations of the method. Our results extend a theorem of Deza, Frankl, and Singhi, who studied the case of prime moduli. The main point we make is that our bound implies a polynomial bound of the form m⩽nc(s) for all prime power moduli q. In this sense the theorem complements a remarkable recent result of Grolmusz that no bound of this form holds for any q which is not a prime power.