A complexity measure for families of binary sequences (Q1878610)

The authors introduce the notion of \(f\)-complexity of a family of binary sequences: The \(f\)-complexity \(\Gamma({\mathcal F})\) of a family \(\mathcal F\) of binary sequences \(E_N\in \{-1,+1\}^N\) is the greatest integer \(j\) such that for any specification \[ e_{i_1}=\varepsilon_1,\ldots,e_{i_j}=\varepsilon_j,\qquad i_1<\ldots<i_j \] of length \(j\) there is at least one \(E_N=(e_1,\ldots,e_N)\in {\mathcal F}\) which satisfies it. Let \(p>2\) be a prime. Let \({\mathcal F}\) be the family of sequences \(E_p=(e_1,\ldots,e_p)\) defined by \[ e_n=\begin{cases} \left(\frac{f(n)}{p}\right), & \text{if}\;f(n)\neq 0,\\ 1, & \text{if}\;f(n)=0,\end{cases} \] where \(f\) runs through all nonconstant polynomials over the finite field \(F_p\) of order \(p\) with degree at most \(K\) and no multiple zero in the algebraic closure of \(F_p\). The main result of the paper is the lower bound \[ \Gamma({\mathcal F})\geq K \] if \(K\) is sufficiently small with respect to \(p\). This complements earlier results on the distribution of a single sequence of \({\mathcal F}\) (see \textit{C. Mauduit} and \textit{A. Sárközy} [Acta Arith. 82, 365--377 (1997; Zbl 0886.11048)]). Moreover, the cardinality of the smallest family achieving a prescribed \(f\)-complexity and multiplicity is estimated.