A proof of Alon–Babai–Suzuki’s conjecture and multilinear polynomials

Let K={k1,k2,…,kr}K={k1,k2,…,kr} and L={l1,l2,…,ls}L={l1,l2,…,ls} be disjoint subsets of {0,1,⋯p−1}{0,1,⋯p−1}, where pp is a prime and F={F1,F2,…,Fm}F={F1,F2,…,Fm} be a family of subsets of [n][n] such that |Fi||Fi| (mod pp) ∈K∈K for all Fi∈FFi∈F and |Fi∩Fj||Fi∩Fj| (mod pp) ∈L∈L for i≠ji≠j. In 1991 Alon, Babai and Suzuki conjectured that if n≥s+max1≤i≤rkin≥s+max1≤i≤rki, then |F|≤ns+ns−1+⋯+ns−r+1. In this paper we prove this conjecture.