Constructing Large Set Systems with Given Intersection Sizes Modulo Composite Numbers (Q4796016)

Let \(q\in\mathbb{Z}\), \(L\subseteq\mathbb{Z}\). Following \textit{L. Babai, P. Frankl, S. Kutin} and \textit{D. Štefankovič} [J. Comb. Theory, Ser. A 95, 39-73 (2001; Zbl 0971.05107)] the author writes \(r\in L\pmod{q}\) if \(r\equiv\ell\pmod{q}\) for some \(\ell\in L\), and \(r\notin L\pmod{q}\) if \(r\not\equiv\ell\pmod{q}\) for every \(\ell\in L\) ; the set system consisting of all subsets of \(X\) of size \(k\) is denoted by \(X\choose k\). A set system \({\mathcal F}\) is \(L\)-avoiding mod \(q\) if, for all \(E\in{\mathcal F}\), \(|E|\notin L\pmod{q}\); \({\mathcal F}\) is \(L\)-intersecting mod \(q\) if, for all pairs of distinct subsets \(E,F\in{\mathcal F}\), \(|E\cap F|\in L\pmod{q}\). Consider all systems \({\mathcal F}\) of subsets of a universe of size \(n\) which are, for some \(L\) with \(|L|=s\), both \(L\)-avoiding mod \(q\) and \(L\)-intersecting mod \(q\); the maximum of \(|{\mathcal F}|\) is denoted by \(m(n,s,q)\). \textit{N. Alon, L. Babai}, and \textit{H. Suzuki} [J. Comb. Theory, Ser. A 58, 165-180 (1991; Zbl 0751.05009)] proved that, for prime \(p\), \(m(n,s,p)=O(n^s)\) as \(n\to\infty\); and Babai, Frankl, Kutin, and Štefankovič [opus cit.] showed that, for prime powers \(q\), \(m(n,s,q)\leq n^{2^{s-1}}\). From the author's introduction: ``Our main result (Theorem 1.2) is a simpler proof of (Theorem 1.1, due to Grolmusz) with an improved constant \dots. The proof uses a technique of \textit{P. Frankl} [Ann. Discrete Math. 17, 289-291 (1983; Zbl 0523.05002)] for applying polynomials to set systems \dots. Frankl's technique gives a natural context for using the Barrington-Beigel-Rudich (BBR) polynomials [Comput. Complexity 4, 367-382 (1994; Zbl 0829.68057)]. We discuss the BBR polynomials in Section 3, and our proof of Theorem 1.1 appears in Section 4. Remark 1. After Grolmusz published his original proof, but before our work presented in this note, Grolmusz [\S 3.3 of `Constructing set-systems with prescribed intersection sizes', Technical report 2001-03, DIMACS] independently found the same simplified argument.'' Theorem 1.1 [\textit{V. Grolmusz}, Combinatorica 20, 71-86 (2000; Zbl 0949.05083)]. Let \(q\) be an integer with at least \(r\) distinct prime factors, \(r\geq 2\). Then, for infinitely many \(n\), \(m(n,2^r-1,q)\geq \exp(c_q(\log n)^r(\log\log n)^{1-r})\), where \(c_q\) is a constant depending on \(q\). Theorem 1.2. Let \(q\) be an integer with at least \(r\) distinct prime factors, \(r\geq 2\). Then, for any constant \(c<r^{-r}\), and for infinitely many \(n\), \(m(n,2^r-1,q)\geq \exp(c(\log n)^r(\log\log n)^{1-r})\). Theorem 1.3. For any \(\varepsilon>0\), for infinitely many \(s\), as \(q\) ranges over all prime powers, \[ \sup_q\limsup_{n\to\infty}\frac{\log m(n,s,q)}{\log n}>s+ \Omega(s^{1-\varepsilon}). \] Section 9 contains a list of questions and a conjecture.